PaperlayerView exact revision on arXiv

Source-linked AI summary

Lipschitz and Comparator-Norm Adaptivity in Online Learning

Zakaria Mhammedi, Wouter M. Koolen

arXiv:2002.12242v2cs.LGstat.ML

TL;DR

Online convex optimization in unbounded settings requires regret guarantees that adapt to both gradients and comparator size without knowing the gradient scale. The paper builds scale-free, parameter-free learners and reductions for this setting; its unbounded-set guarantee includes explicit additional penalties, and the methods also yield scale-invariant linear-model prediction.

  • Problem

    The paper seeks online regret guarantees that adapt to comparator size even when the prediction set is unbounded and the maximum gradient norm is unknown.

    Source: §1 · p. 1

  • Method

    The paper develops scale-free, parameter-free learners with hints and applies reductions to obtain algorithms that do not require hints.

    Source: §1 · p. 2, §2.3 · p. 5

  • Results

    For unbounded sets, the guarantee includes additional terms involving L max_t B_t and L||w||^3, and the paper gives a matching lower bound under an rO(√T) requirement.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The methods yield scale-invariant online linear-model predictions invariant to coordinate-wise scaling of input features, with improved regret bounds over prior algorithms in that setting.

    Source: §1 · p. 2

    The matrix-free bound requires γ > 1; at γ = 1, ρ(γ) = 0 and the lower-order term would explode.

    Source: §3.2 · p. 9

Abstract

from arXiv · show

We study Online Convex Optimization in the unbounded setting where neither predictions nor gradient are constrained. The goal is to simultaneously adapt to both the sequence of gradients and the comparator. We first develop parameter-free and scale-free algorithms for a simplified setting with hints. We present two versions: the first adapts to the squared norms of both comparator and gradients separately using $O(d)$ time per round, the second adapts to their squared inner products (which measure variance only in the comparator direction) in time $O(d^3)$ per round. We then generalize two prior reductions to the unbounded setting; one to not need hints, and a second to deal with the range ratio problem (which already arises in prior work). We discuss their optimality in light of prior and new lower bounds. We apply our methods to obtain sharper regret bounds for scale-invariant online prediction with linear models.

1. Introduction

The paper targets online convex optimization without bounded predictions or prior knowledge of the maximum gradient norm, seeking algorithms that adapt to both gradients and comparator size. It develops scale-free, parameter-free guarantees and applies them to scale-invariant linear prediction.

1. Introduction

  • The goal is regret control against any comparator, even when the prediction set is unbounded and the maximum gradient norm L is unknown.The paper calls L the Lipschitz constant.Source: §1 · p. 1
  • Earlier algorithms adapting to L and comparator norm were not scale-free and required an advance choice of ε that could make their bounds arbitrarily large relative to unknown L.Their predictions changed when losses were positively rescaled, and their bounds included ε-dependent terms.Source: §1 · p. 2
  • For unbounded W, the algorithm achieves the same guarantee with an additive O_p(L max_{t≤T} B_t + L||w||^3), where B_t is defined using gradient norms normalized by L_t.Source: §1 · p. 2
  • A second scale-invariant algorithm replaces the leading comparator-norm and total-gradient-variance term with a full-matrix expression involving w^T V_T w and ln det V_T.V_T is defined as the sum of gradient outer products.Source: §1 · p. 2
  • The methods yield scale-invariant online linear-model predictions under coordinate-wise feature scaling and improve regret bounds over prior algorithms in that setting.The paper names Kotłowski (2017) and Kempka et al. (2019) as the prior algorithms.Source: §1 · p. 2

2. Preliminaries

The preliminaries formulate the unbounded OCO objective and explain how hint-based algorithms can be converted into algorithms that do not know the gradient scale. The reductions also expose the extra costs and conditions that matter for their guarantees.

2. Preliminaries

  • The section’s objective is to design scale-free algorithms that adapt to both the Lipschitz constant L and comparator norm ||w||.The stated plan is to introduce the setting, discuss reductions, and identify what is needed to reach that objective.Source: §2 · p. 3

2.1. Setting and Notation

  • OCO is reduced to controlling linearized regret, and scale-freeness requires predictions to remain invariant under common positive scaling of losses and applicable hints.The learner may use a hint h_t at least as large as the running maximum gradient norm L_t.Source: §2.1 · p. 3

2.2. Helpful Reductions

  • The hint-removal reduction adds a term involving max_t L_t||w_t||, which may be arbitrarily large on unbounded W even for fixed w, L, and T.For bounded W, the same reduction can preserve the regret guarantee up to an additive 2DL.Source: §2.2 · p. 4
  • For unbounded W, restricting predictions to growing bounded sets incurs a projection penalty; choosing their diameters controls the trade-off with the L D_T term.The construction uses a non-decreasing sequence of bounded convex subsets.Source: §2.2 · p. 4
  • A time-varying diameter choice yields a penalty involving L max_t B_t, and the paper says this cannot be improved to √V_T under the stated setup.It also states that the L||w||^3 penalty is essentially unavoidable when requiring an rO(√T) regret bound.Source: §2.2 · p. 5

2.3. Outlook

  • The outlook is to design a scale-free learner using hints h_t ≥ L_t, then use the reductions to obtain algorithms without hints; the same learner is used for scale-invariant linear-model learning.For bounded sets, the unconstrained-to-constrained reduction gives the corresponding bound up to an additive LD.Source: §2.3 · p. 5

3. Scale-Free, Parameter-Free Algorithms for OCO

The section develops scale-free, parameter-free OCO algorithms under scale-compatible gradient hints, then extends them to address range ratios and directional variance. FREEGRAD’s potential yields comparator-adaptive regret, while MATRIX-FREEGRAD measures variance in the comparator direction.

3.1. FREEGRAD: An Adaptive Scale-Free Algorithm

  • FREEGRAD chooses iterates that make its potential non-increasing for every gradient sequence, which yields a regret bound against any comparator in R^d.The derivation uses regret-reward duality and bounds the resulting Fenchel-dual expression.Source: §3.1 · pp. 6–7
  • The FREEGRAD regret bound retains scale-ratio terms that can become arbitrarily large when the initial hint is small relative to later hints.FREERANGE addresses this issue with restarts; the bounded-set restart trick does not directly apply when W is unbounded.Source: §3.1 · p. 7
  • FREERANGE extends the restart repair for problematic scale ratios to unbounded decision sets, at an additive lower-order rO(||w||L) regret cost.The hints must be non-decreasing, upper-bound the gradient norms, and scale with the gradients.Source: §3 · p. 6, §3.1 · p. 7

3.2. MATRIX-FREEGRAD: Adapting to Directional Variance

  • MATRIX-FREEGRAD measures variance in the comparator direction, using a full-matrix variant of FREEGRAD that can be computed in O(d^3) time per round.Its regret bound is scale-free, and the restart wrapper can also remove problematic scale ratios for this algorithm.Source: §3.1 · p. 7, §3.2 · pp. 8–9
  • The directional-variance bound’s advantage may be offset when ln det Q reaches d ln T, and γ must exceed 1 to keep the lower-order term finite.The analysis uses a hard norm constraint and a multiplicative slack factor γ to make the potential controllable.Source: §3.2 · pp. 8–9
  • The section’s algorithms can serve as the base algorithm in reductions that adapt to comparator norm and Lipschitz constant without hints, for bounded or unbounded sets.Source: §3.2 · p. 9

4. Lower Bounds

The lower bounds examine the costs of removing hints and adapting to both the comparator norm and gradient scale. They show that specified penalty terms and comparator-norm exponents cannot generally be reduced under the stated regret requirements.

4. Lower Bounds

  • The no-hint reduction incurs penalties LT||w||^3 and LT max_{t≤T} B_t, and the section states that the latter cannot generally be replaced by √V_T.Here B_t is the cumulative sum of ||g_s||/L_s.Source: §4 · p. 10
  • For the stated regret form, Theorem 14 rules out algorithms adapting to L and ||w|| with comparator-norm exponent ν≥1 under its specified conditions.Source: §4 · pp. 10–11
  • The exponent 3 in ||w|| is unimprovable: for any ν in [1,3) and c > 0, no algorithm guarantees the stated regret bound, even up to multiplicative log-factors in ||w|| and T.Source: §4 · p. 11

5. Application to Learning Linear Models with Online Algorithms

The paper applies its unbounded OCO algorithms to linear models, where predictions are inner products and the loss is convex and 1-Lipschitz in the prediction. It gives scale-invariant algorithms with regret bounds against any comparator, including a rotation- and scale-invariant variant.

Application to linear models

  • The algorithms yield scale-free—and, for one variant, rotation-free—linear-model predictions with regret bounds against any comparator, matching optimally tuned OGD up to log-factors.The comparison is stated without prior knowledge of the comparator or its predictions on the features.Source: §5 · p. 11
  • Because the feature vector is observed before prediction and the loss is 1-Lipschitz, its norm provides an available upper bound on the subgradient norm for the hint-based algorithms.The section's model uses a fixed loss convex and 1-Lipschitz in its second argument.Source: §5 · pp. 11–12

Improvement over Current Algorithms

  • The coordinate-wise scale-invariant algorithm improves on SCLNOL1, the current state-of-the-art scale-invariant algorithm, although the supplied passage does not give the improvement's magnitude.Its regret bound uses coordinate-specific feature norms; combining coordinate bounds adds a factor d to the lower-order term, which can be avoided by dividing predictions by d at the cost of a factor d inside logarithms.Source: §5 · pp. 12–13

Rotation-Invariant Algorithm

  • The rotation- and scale-invariant variant replaces the feature covariance matrix S_T with V_T, which can give a smaller bound when the subgradient scalars δ_t are small, as may occur near convergence.The variant uses MATRIX-FREEGRAD rather than FREEGRAD.Source: §5 · pp. 12–13

A Scale-Invariant Algorithm

  • The scale-invariant one-dimensional algorithm scales FREEGRAD outputs using the current epoch's initial hint and a cumulative feature-to-hint ratio.This additional scaling addresses the analysis issue caused by removing dependence on the initial hint from a lower-order regret term.Source: §5 · p. 12

Appendix A. Proof of Theorem 5

The proof of Theorem 5 establishes that its potential does not increase after an update. It reduces the update bound to a scalar inequality and verifies that inequality using a polynomial derivative argument.

Appendix A. Proof of Theorem 5

  • The scalar inequality Θ(G,V,g) ≤ 0 for V > 0 and g in [-1,1] is the key result used to bound the potential change.The proof establishes it by showing an associated Γ increases in V and tends to zero as V grows.Source: Appendix A · pp. 16, 19
  • The derivative argument verifies nonnegativity of its denominator and polynomial coefficients, using Mathematica FullSimplify for the coefficient check.The resulting derivative is nonnegative, yielding Γ ≤ 0.Source: Appendix A · pp. 16–17
  • The authors report that the proof gives no insight into potential design and that they do not know a similar potential for the multidimensional case in Section 3.2.They describe the verification as tedious and suggest Sum-of-Squares techniques might streamline it.Source: Appendix A · pp. 17–18
  • The update proof reduces the potential change to a scalar inequality by showing that a maximizing update vector aligns with the accumulated gradient.The argument fixes the inner product with the accumulated gradient, then uses the minimum-norm maximizer within that hyperplane.Source: Appendix A · pp. 18–19

B.1. Proof of Theorem 6

The proof of Theorem 6 obtains FREEGRAD's regret bound through a scaled-output theorem. It uses the potential bound and Fenchel duality to derive the comparator-dependent bound.

B.1. Proof of Theorem 6

  • Theorem 20 gives a regret bound for FREEGRAD outputs scaled by any positive ε, under Assumptions 1 and 2.Theorem 6 follows by setting ε = 1.Source: §B.1 · pp. 19–20
  • The proof divides the potential inequality by ε and uses Fenchel duality to obtain a bound for every comparator w.It relates the dual potential to the scaled potential before combining the inequalities.Source: §B.1 · pp. 19–20
  • The proof bounds the conjugate using the Lambert function and its stated inequality, then combines those bounds to obtain the regret bound.The passage identifies the Lambert function as the principal solution of W(x)e^W(x) = x.Source: §B.1 · p. 20

B.2. Proof of Theorem 7

The proof of Theorem 7 sums regret bounds over epochs and handles the last two epochs separately. Combining these bounds yields the stated final inequality.

B.2. Proof of Theorem 7

  • For each epoch, the proof applies Theorem 6 to bound regret by a term involving that epoch's feature-gradient quantity and the next epoch's hint.It sums these bounds over all but the last two epochs.Source: §B.2 · p. 21
  • The bound in (36) is at most h_T(8/||w|| ln+(2b_T/||w||)+2/||w||+1), expressed using terminal hint h_T and cumulative quantity b_T.Source: §B.2 · p. 21
  • Adding the summed earlier-epoch bound to the final-two-epoch bound gives the concluding regret inequality.The proof uses h_τk ≤ h_T when combining the terms.Source: §B.2 · pp. 21–22

Appendix C. Proofs for Section 3.2

The appendix postpones Section 3.2’s tuning while proving the result needed for Section 5. For Lemma 9, it bounds the potential change using a minimizer and a choice of ρ(γ) tailored to the hardest case.

Appendix C. Proofs for Section 3.2

  • The appendix postpones Section 3.2’s tuning so the result needed for Section 5 can be proved in one pass.Source: Appendix C · p. 22

C.1. Proof of Lemma 9

  • For Lemma 9, the proof compares successive potentials using a minimizer λ* and matrix determinant and Sherman–Morrison identities.Source: §C.1 · pp. 22–23
  • ρ(γ) is chosen so the hardest case, r = −ρ(γ), holds with equality, while |r| ≤ ρ(γ) ≤ 1.Source: §C.1 · p. 23

C.2. Proof of Theorem 10

The proof derives a complexity bound whose expression changes with comparator size, then relates it to a model-complexity function. A separate lower-bound construction uses one-dimensional power-law gradients.

C.2. Proof of Theorem 10

  • The proof telescopes the potential because Ψ(G,V,h) decreases in h, bounding cumulative predictions by the initial-minus-final potential.Source: §C.2 · p. 24
  • The regret conversion uses a convex conjugate and the model-complexity function X(θ), expressible through the Lambert function W.Source: §C.2 · p. 24
  • The derived expression takes a maximum between w⊺Qw and an average involving that term and a quantity growing super-linearly with ||w||².Source: §C.2 · p. 25

D.1. Proof of Lemma 13

  • For Lemma 13, the proof uses d = 1 and g_t = t^γ with −1 < γ < −1/α, giving L_t = 1 for all t.Source: §D.1 · p. 26

D.2. Proof of Theorem 15

Theorem 15 is proved via a lower bound: under the stated output-growth restriction, some gradient sequence and comparator force substantial regret. The construction uses constant gradients in one dimension.

D.2. Proof of Theorem 15

  • For ν ∈ [1,3), Lemma 23 gives a sequence and comparator forcing the stated lower bound on regret for outputs satisfying its growth restriction.Source: §D.2 · p. 27
  • The lower-bound proof specializes to d = 1 with g_t = 1 and L_t = 1 throughout.Source: §D.2 · p. 27
  • Theorem 15 concludes that algorithms with the specified output-growth restriction cannot achieve the desired regret bound.Source: §D.2 · p. 27

Appendix E. Proof of Section 5

The proof of Section 5 analyzes a modified FREERANGE wrapper that scales FREEGRAD outputs. Its epoch-wise analysis supplies bounds that are then combined across epochs.

Appendix E. Proof of Section 5

  • The modified FREERANGE wrapper scales the outputs of FREEGRAD.Source: Appendix E · p. 28
  • Within each epoch, the proof applies Theorem 20 in one dimension to obtain a bound of 2|w| for the cumulative comparator gap.Source: Appendix E · p. 28
  • The epoch bounds are combined using the restart condition and h_{τk} ≤ h_T to reach the final inequality.Source: Appendix E · pp. 28–30
Loading 2002.12242v2…