PaperlayerView exact revision on arXiv

Source-linked AI summary

Black-Box Reductions for Parameter-free Online Learning in Banach Spaces

Ashok Cutkosky, Francesco Orabona

arXiv:1802.06293v2cs.LGmath.OCstat.ML

TL;DR

Parameter-free online learning needs regret guarantees under adversarial losses without tuning parameters, while existing approaches can be norm-specific or computationally burdensome. The paper introduces three black-box reductions connecting parameter-free learning, exp-concave optimization, one-dimensional optimization, and constrained domains. These reductions simplify analyses, improve regret or runtime in several applications, and extend the approach to arbitrary norms.

  • Problem

    Adversarial online learning seeks low regret without parameter tuning, but prior methods can be limited to Hilbert spaces, have suboptimal comparator dependence, or require costly constrained optimization.

  • Method

    The paper develops three black-box reductions from exp-concave optimization to parameter-free OLO, from arbitrary-norm Banach-space optimization to one dimension, and from constrained to unconstrained optimization.

  • Results

    The reductions produce simpler algorithms with improved regret or runtime, including improved parameter-free bounds and results for arbitrary norms.

  • Takeaways & Limitations

    The reductions provide reusable tools for designing parameter-free and adaptive online learning algorithms beyond the standard Euclidean setting.

  • Takeaways & Limitations

    The main parameter-free analysis assumes a known Lipschitz bound, with L = 1 used for simplicity.

Abstract

from arXiv · show

We introduce several new black-box reductions that significantly improve the design of adaptive and parameter-free online learning algorithms by simplifying analysis, improving regret guarantees, and sometimes even improving runtime. We reduce parameter-free online learning to online exp-concave optimization, we reduce optimization in a Banach space to one-dimensional optimization, and we reduce optimization over a constrained domain to unconstrained optimization. All of our reductions run as fast as online gradient descent. We use our new techniques to improve upon the previously best regret bounds for parameter-free learning, and do so for arbitrary norms.

1 Parameter Free Online Learning

The paper frames parameter-free online learning as adversarial online convex optimization and introduces three black-box reductions that simplify algorithm design across norms and domains. These reductions yield improved regret guarantees, broader applicability, and additional algorithms with favorable runtime.

  • Problem setting: Online learning selects w_t, observes losses, and measures cumulative performance by regret against a comparator w̌.The framework includes online convex optimization and its reduction to linearized regret through subgradients.
  • Problem setting: The paper assumes a known 1-Lipschitz bound because removing it leads to catastrophically bad lower bounds.For arbitrary Lipschitz constant L, gradients can be rescaled; the paper sets L = 1 for simplicity.
  • Three reductions: The three reductions connect exp-concave optimization to parameter-free OLO, arbitrary-norm optimization to one-dimensional optimization, and constrained optimization to unconstrained optimization.The reductions are designed to avoid parameter tuning and can be combined to construct new algorithms.
  • Generality: The reductions apply to arbitrary norms and Banach-space domains without assumptions about base-algorithm internals.Each reduction is also presented as independently useful beyond parameter-free learning.
  • Results: The new parameter-free algorithm improves prior dependence on the dual-gradient norm, and the paper states that this can lower regret for smooth losses.Earlier analyses were often limited to the 2-norm and more complicated, whereas the proposed techniques are simpler and more general.
  • Applications: The applications include improved multi-scale-experts guarantees and runtime, near-square-root regret for general convex losses, logarithmic regret for strongly convex losses, and Banach-space bounds.The strongly-convex result uses first-order information and matches gradient-descent runtime; the Banach-space result extends prior work to unconstrained domains.

2 Online Newton Step to Online Linear Optimization via Betting Algorithms

The paper turns the choice of coin-betting fractions into a one-dimensional exp-concave optimization problem. Using Online Newton Step, it obtains high wealth efficiently, which translates into low regret for parameter-free learning.

  • Betting formulation: Coin-betting algorithms wager a signed fraction of current wealth, with wealth updates determined by the observed outcome g_t.The algorithm plays w_t = v_t Wealth_{t−1} and updates wealth after receiving g_t ∈ [−1,1].
  • Betting formulation: High wealth is equivalent to low regret, so the analysis lower-bounds wealth rather than directly optimizing against the comparator.This removes the comparator from the wealth lower-bound problem and makes the analysis conceptually simpler.
  • Guarantee: Online Newton Step obtains logarithmic regret for the betting-fraction problem, enabling a high wealth lower bound and the resulting regret guarantee.The construction is summarized in Algorithm 1, which updates the betting fraction through ONS after each wealth update.
  • Banach-space extension: The same argument extends to Banach spaces by replacing scalar betting fractions with vectors and scalar outcomes with dual-space vectors of norm at most one.Exact constants are deferred to the general Banach-space theorem.
  • Proof strategy: The method begins from regret-reward duality: a wealth lower bound is converted through a convex conjugate into a regret bound.The proof defines wealth for a fixed reference betting fraction and then uses the induced optimization regret.
  • Exp-concave reduction: The betting-fraction problem has losses −ln(1 − g_t v), which are exp-concave and therefore amenable to Online Newton Step.The resulting one-dimensional ONS problem can be restricted to [−1/2, 1/2], where projection is simple truncation.

3 From 1D Algorithms to Dimension-Free Algorithms

The paper introduces a black-box reduction from one-dimensional online learning to optimization in arbitrary-dimensional Banach spaces. It separates each prediction into a learned magnitude and direction, preserving regret guarantees while enabling dimension-free, parameter-free algorithms with online-gradient-descent-like runtime.

  • Motivation: Prior dimensionality extensions were algorithm-specific and generally limited to Hilbert spaces, whereas this reduction applies to any Banach space.The reduction is presented as a short, general argument rather than a separate analysis for each one-dimensional algorithm.
  • Reduction: The reduction combines a one-dimensional algorithm A1D on magnitudes with a unit-ball algorithm AS on directions, outputting wt = ztyt.The scalar feedback is st = ⟨gt, yt⟩ for A1D, while AS receives gt.
  • Guarantee: Theorem 2 bounds the combined regret by the one-dimensional regret at ∥˚w∥ plus ∥˚w∥ times the unit-ball regret at ˚w/∥˚w∥.The construction also guarantees |st| ≤ ∥gt∥⋆, including the zero-competitor convention for normalization.
  • Guarantee: The reduction applies to spaces including Hilbert spaces and ℓp spaces for p ∈ (1, 2], with λ = 1 for the 2-norm and λ = p−1 for the p-norm.These are examples of (2, λ)-uniformly convex spaces covered by the resulting algorithm.
  • Runtime: The runtime equals the sum of the runtimes of A1D and AS and, in many cases, matches online gradient descent.This includes Rd with the 2-norm and Hilbert spaces.
  • Result: The resulting parameter-free algorithm is the fastest known for an arbitrary norm and depends on ∥gt∥2⋆ rather than ∥gt∥⋆.The improved gradient dependence can yield lower regret for smooth losses with small loss values at the comparator.

4 Reduction to Constrained Domains

The constrained-domain reduction converts online optimization over a convex set W into unconstrained optimization over a larger space V. It projects predictions onto W and adds a distance-to-W barrier, preserving regret up to a factor of two while not increasing dual-gradient norms.

  • Motivation: The reduction addresses constrained optimization, whose classical Mirror Descent and Follow-the-Regularized-Leader analyses have drawbacks for unbounded domains.It assumes a reflexive Banach space and a convex constraint set W contained in the base algorithm’s domain V.
  • Reduction: Given zt from an unconstrained algorithm, the method predicts with wt ∈ ΠW(zt) and supplies the surrogate loss ⟨gt, ·⟩ + ∥gt∥⋆SW.The distance term SW acts as a Lipschitz barrier penalizing predictions outside W.
  • Guarantee: The surrogate subgradients satisfy ∥˜gt∥⋆ ≤ ∥gt∥⋆.This follows from the 1-Lipschitz property of the distance-to-set function.
  • Implementation: For a unit-ball constraint, projection and a subgradient of SW are easy to compute, and a general subgradient formula is given using the normalized dual vector of x − p.The general formula applies under the stated uniqueness condition for the dual vector.

5 Reduction for Multi-Scale Experts

The multi-scale experts reduction combines one-dimensional parameterized algorithms with coordinate-wise updates and the constrained-domain reduction. It improves prior runtime and regret trade-offs while preserving scale-sensitive regret guarantees.

  • Motivation: The prior approach had mildly sub-optimal prior dependence, while another required O(T) time per update and quadratic total runtime.The proposed algorithm matches the latter method’s regret bound while running in online-gradient-descent time.
  • Problem: The multi-scale experts problem optimizes over the probability simplex with coordinate losses bounded by known scales ci.The target regret scales with each expert’s ci and comparator weight, under a prior distribution π.
  • Reduction: The construction first applies coordinate-wise updates to a family of one-dimensional algorithms, then uses the unconstrained-to-constrained reduction after an affine rescaling.The rescaling makes the transformed losses ∥gt∥∞-bounded by 1.
  • Guarantee: Theorem 6 applies when |gt,i| ≤ ci and the comparator lies in the probability simplex, yielding the stated scale-sensitive regret bound.The transformed comparator is ˜wi = ci˚wi and the transformed gradients satisfy ∥˜gt∥∞ ≤ 1.
  • Runtime: Projection onto the constraint set and a subgradient of its distance function can be computed in O(N) time per update.A simple greedy algorithm provides these operations for the simplex construction.

6 Reduction to Adapt to Curvature

The curvature-adaptation reduction makes a generic online learning algorithm responsive to loss curvature in a Banach space. It yields logarithmic regret for strongly convex losses and retains the base algorithm’s runtime while improving gradient dependence and extending the guarantee to adversarial settings.

  • Goal: The reduction targets online optimization over a convex closed set of diameter D and adapts a generic algorithm to the curvature of the losses.Its stated guarantees include O(log(TD)^2/µ) regret for online µ-strongly convex problems and O(log(TD)^2D) regret for linear problems.
  • Reduction: The method follows the intuition of adding a weighted average of previous predictions to the outputs of a base algorithm as a momentum term.The implementation maintains an auxiliary point and sends modified subgradients back to the base algorithm.
  • Guarantee: The resulting guarantees are only logarithmic factors from the optimal guarantees for both strongly convex and online linear optimization problems.The supplied theorem states the generic base-algorithm conditions under which the reduction applies.
  • Efficiency: The reduction improves gradient dependence from ∥gt∥⋆ to ∥gt∥2⋆ and preserves the base algorithm’s running time.This avoids the potentially slow optimization step required by earlier algorithms with similar regret.
  • Scope: The argument establishes logarithmic regret for adversarial strongly convex problems, whereas cited similar results had shown it only for stochastic strongly convex problems.The paper describes this extension as a two-line argument.

7 Banach-space betting through ONS

The section presents Banach-space betting through ONS as a general formulation of the one-dimensional algorithm, with regret that adapts to changing norms. It applies to arbitrary norms and supports unbounded domains and convex losses through subgradients.

  • Algorithm: Algorithm 7 extends one-dimensional betting through ONS to arbitrary real Banach spaces.The formulation uses an initial operator and wealth-based betting fractions updated through ONS losses.
  • Special case: For R^d with the p-norm, the operator L can be the identity and the ONS component becomes standard d-dimensional ONS.This gives a simpler special case of the general Banach-space formulation.
  • Regret guarantee: Theorem 8 provides a regret guarantee for any unit vector and any comparator in a d-dimensional Banach space.The theorem asserts existence of a suitable linear operator L for Algorithm 7.
  • Regret guarantee: The bound adapts to any sequence of norms rather than only competing with a fixed norm.The paper contrasts this flexibility with prior many-norm adaptivity, while noting a factor-d worse bound than the cited comparison.
  • Scope and runtime: The approach handles unbounded W and arbitrary convex losses through subgradients, while its update complexity is O(d^2).The cited comparison states that the related algorithms, including this one, have O(d^2) complexity per update.

8 Conclusions

The paper concludes that three black-box reductions connect parameter-free learning, arbitrary-norm optimization, and constrained optimization to simpler online optimization problems. The reductions simplify analyses and can improve regret or runtime.

  • Contributions: The paper introduces three reductions: parameter-free learning to exp-concave optimization, arbitrary-norm optimization to one-dimensional optimization, and constrained optimization to unconstrained optimization.These reductions are presented as the central concluding contribution.
  • Scope: The reductions apply to optimization in Banach spaces and therefore cover arbitrary norms, including familiar finite-dimensional examples.Banach spaces include Euclidean and p-norm spaces, while Hilbert spaces are a special case.
  • Implications: The reductions simplify arguments and can improve regret bounds or runtime.The conclusion states these benefits without restricting them to a single reduction.
  • Supporting analysis: The appendix develops supporting results on Banach-space geometry, ONS analysis, Fenchel conjugates, constrained optimization, computation, and stochastic-curvature adaptation.The listed appendix sections identify the technical components supporting the paper's theorems.

B Proof of the regret bound of ONS in Banach spaces

The proof establishes the Banach-space ONS regret bound by constructing a positive, invertible self-adjoint operator and translating the analysis into Euclidean coordinates via an Auerbach basis.

  • Operator properties: The operator A(x)=τΣ_t⟨g_t,x⟩g_t is shown to be invertible, self-adjoint, and positive definite.Invertibility follows from the basis spanning the dual space, while positivity follows from the quadratic form.
  • Algorithm: The proof states ONS in Banach spaces with a convex domain, an initial operator L, and parameters τ and β.Algorithm 8 initializes v_1=0 and iterates over the losses.
  • Coordinate construction: An Auerbach basis supplies primal and dual coordinates with unit norms and biorthogonality.These coordinates define L and make the subsequent analysis tractable.
  • Coordinate construction: The Banach-space quantities are transferred to R^d, where the Euclidean ONS analysis bounds the accumulated sum terms.The coordinate representation preserves dual-vector action, and the transformed gradients have 2-norm at most d.
  • Regret bound: For α-exp-concave losses, choosing β using the domain diameter, gradient bound, and horizon yields the stated regret guarantee.The proof combines the Banach-space ONS results with the standard exp-concavity inequality.

C Proofs of Theorems 1 and 8

The proofs of Theorems 1 and 8 use ONS on logarithmic losses, then convert wealth lower bounds into regret bounds through Fenchel-conjugate calculations.

  • Proof strategy: The proof first shows that ONS achieves logarithmic regret on losses of the form ln(1+⟨g_t,β⟩).This intermediate guarantee is then linked to wealth and comparator regret.
  • Logarithmic losses: For the betting construction, the losses are ℓ_t(v)=−ln(1−⟨g_t,v⟩) on the unit ball with ∥g_t∥⋆≤1.The specified ONS parameter β is used for this logarithmic loss sequence.
  • Technical bounds: The argument uses logarithmic inequalities valid under bounded inner products and concludes after substituting the prescribed β.The proof explicitly invokes ln(1+x)≥x−x^2 for |x|≤1/2.
  • Wealth-to-regret conversion: The proof relates the logarithm of wealth to regret against an arbitrary unit vector through a decomposition involving comparator and algorithmic betting terms.This is the role of Lemma 21 in the proof of Theorem 8.
  • Wealth-to-regret conversion: Fenchel-conjugate calculations convert the wealth lower bounds into regret upper bounds.The proof uses exponential-function conjugates and a numerical bound before applying the final comparator substitution.

D Proof of Proposition 1 and Theorem 4

The section proves that distance to a closed convex set is convex and 1-Lipschitz, then characterizes its subgradient and develops an O(N)-time projection procedure for the weighted simplex.

  • Proof of Proposition 1: Proposition 1 establishes that SW is convex and 1-Lipschitz for every closed convex set W in a reflexive Banach space.The Lipschitz guarantee is |SW(x) − SW(x + δ)| ≤ ∥δ∥.
  • Proof of Proposition 1: Under unique norming dual vectors, the subgradient of SW at x outside W is the singleton {(x − p)⋆}, where p is a nearest point in W.The proof uses 1-Lipschitzness and the subgradient inequality to force unit dual norm and equality with x − p.
  • Projection computation: For the weighted simplex Wk, an optimal projection can be chosen coordinatewise according to whether xi is negative, within [0, kci], or above kci.The coordinates are processed after ordering c1 ≥ c2 ≥ ··· ≥ cN.
  • Projection computation: The recursive projection structure reduces the computation of ΠW1(x) to a greedy procedure that selects coordinates in increasing order and runs in O(N) time.The residual mass ki+1 is updated after each coordinate, and the resulting vector is returned by Algorithm 9.

F Proof of Theorem 7

The proof of Theorem 7 transfers an online linear optimization guarantee to the constrained setting using the distance function and Proposition 1, then bounds the remaining terms through telescoping and bias–variance arguments.

  • Theorem 7 proof: Theorem 23 assumes an online linear optimization algorithm on a closed convex domain W of diameter D with a stated regret guarantee.The theorem provides the base guarantee used in the reduction.
  • Theorem 7 proof: A random vector Xt weighted by ∥˜gt∥⋆ is used with bias–variance decomposition to relate the analysis to VT(˚w).The construction yields ZT E[∥XT − ˚w∥²] = VT(˚w).
  • Theorem 7 proof: Proposition 1 converts the constrained comparison ⟨gt, xt − ˚w⟩ into a surrogate involving zt and the distance SW, enabling application of algorithm A’s regret bound.The key inequality is ⟨gt, xt − ˚w⟩ ≤ ⟨˜gt, zt − ˚w⟩.
  • Theorem 7 proof: Lemma 24 supplies the upper bound for the second term after the first term is controlled by algorithm A’s regret guarantee.The proof then combines this bound with the preceding inequalities to obtain the stated result.
  • Theorem 7 proof: The remaining analysis uses telescoping sums, Cauchy–Schwarz, and standard inequalities to control terms involving Zt and PT.These estimates are assembled before the final bound is stated.
Loading 1802.06293v2…