PaperlayerView exact revision on arXiv

Source-linked AI summary

MetaGrad: Multiple Learning Rates in Online Learning

Tim van Erven, Wouter M. Koolen

arXiv:1604.08740v3cs.LG

TL;DR

Online convex optimization needs adaptive methods that can exploit easier functions without requiring the user to select a method for the function class or data distribution in advance. MetaGrad combines multiple learning rates to cover a broader set of function types, and its variance-sensitive bound yields faster-than-square-root regret rates, often logarithmic, in favorable cases.

  • Problem

    The appropriate OCO algorithm can depend on the function class and data distribution, making advance selection difficult and motivating methods that adapt across easy cases.

    Source: §1 · p. 2

  • Method

    MetaGrad runs multiple learning rates in a hierarchical master-and-slave construction, with the master learning which rate performs best empirically.

    Source: §1 · p. 2, §4 · p. 7

  • Results

    The variance-sensitive bound yields faster-than-O(√T) regret rates, often logarithmic, in favorable cases across the function classes considered.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The bound applies to exp-concave and strongly convex functions as well as some functions without curvature, including stochastic functions satisfying a Bernstein condition.

    Source: §1 · p. 2

    The authors identify speeding up MetaGrad in high dimensions and extending adaptivity to more practically relevant easy-function types as open directions.

    Source: §6 · p. 12

Abstract

from arXiv · show

In online convex optimization it is well known that certain subclasses of objective functions are much easier than arbitrary convex functions. We are interested in designing adaptive methods that can automatically get fast rates in as many such subclasses as possible, without any manual tuning. Previous adaptive methods are able to interpolate between strongly convex and general convex functions. We present a new method, MetaGrad, that adapts to a much broader class of functions, including exp-concave and strongly convex functions, but also various types of stochastic and non-stochastic functions without any curvature. For instance, MetaGrad can achieve logarithmic regret on the unregularized hinge loss, even though it has no curvature, if the data come from a favourable probability distribution. MetaGrad's main feature is that it simultaneously considers multiple learning rates. Unlike previous methods with provable regret guarantees, however, its learning rates are not monotonically decreasing over time and are not tuned based on a theoretically derived bound on the regret. Instead, they are weighted directly proportional to their empirical performance on the data using a tilted exponential weights master algorithm.

1 Introduction

MetaGrad is designed to adapt across a broader range of easy online convex optimization problems than methods limited to strongly convex and general convex functions. It combines multiple learning rates and obtains faster regret rates when its variance-sensitive bound is favorable.

1 Introduction

  • Choosing an algorithm in advance is difficult because the appropriate method can depend on the function class and data distribution.The paper contrasts this with existing adaptive methods that interpolate between strongly convex and general convex functions.Source: §1 · p. 2
  • MetaGrad covers exp-concave, strongly convex, general convex functions that do not change between rounds, and stochastic functions satisfying a Bernstein condition, including unregularized hinge loss.The hinge-loss example can have no curvature.Source: §1 · p. 2
  • The full version maintains a d × d covariance matrix, while diagonal MetaGrad maintains only its d diagonal elements.The diagonal version is presented as a faster approximation.Source: §1 · pp. 2–3
  • The variance-sensitive regret bound can yield faster-than-O(√T) rates, often logarithmic, when its variance measure is favorable.The bound’s variance measure depends on the distance between the iterates and the comparator; stable convergence to the optimum is one favorable case.Source: §1 · p. 3
  • For strongly convex functions, the regret-rate dependence on dimension has an extra factor d, whose necessity or analytical origin remains open.The paper notes that the dependence on d matches expectations in most other cases.Source: §1 · p. 3
  • MetaGrad runs multiple slaves at different learning rates and uses a master algorithm to learn which rate performs best empirically.Each slave uses exponential weights over continuous parameters with a surrogate loss; the resulting distributions are multivariate Gaussians.Source: §1 · p. 3

2 Setup

The setup defines online convex optimization over a closed convex domain and specifies the learner’s first-order feedback. It also states convexity and boundedness conditions used in the analysis.

2 Setup

  • The protocol has the learner choose an iterate, then receive a convex loss and observe its value and subgradient.The domain U is closed and convex and is assumed to contain the origin, with translation allowed otherwise.Source: §2 · pp. 4–5
  • Convexity gives the per-round inequality f_t(w_t) − f_t(u) ≤ (w_t − u)^T g_t for a comparator u.If the loss is nondifferentiable at w_t, any subgradient is allowed.Source: §2 · pp. 4–5
  • The analysis assumes exp-concavity and bounded quantities; vector norms are ℓ2 norms in the full version.For full MetaGrad, the text bounds (u − v)^T g_t by D_full G_full.Source: §2 · p. 5

3 Fast Rate Examples

MetaGrad’s adaptive regret bound yields fast rates under directional and stochastic conditions, including settings without curvature. In particular, a Bernstein condition can give logarithmic expected regret for unregularized hinge loss on i.i.d. data.

Fast Rate Examples

  • The examples derive fast rates from either a directional-derivative condition or a Bernstein condition on stochastic gradients.The Bernstein condition is standard in offline statistical learning when applied to linearized excess loss, and is weaker here than imposing it on the original excess loss.Source: §3 · pp. 5, 7

Directional Derivative Condition

  • A quadratic lower bound on directional derivatives gives O(d ln T) regret for any method with adaptive regret bound (1).The condition applies to a given comparator u.Source: §3 · p. 6
  • For a fixed convex function, the directional condition holds even without curvature, with a = 2 and b = 1/(GfullDfull).The argument uses convexity alone.Source: §3 · p. 6

Bernstein Stochastic Gradients

  • Under the (B, β)-Bernstein condition, the adaptive regret bound yields expected regret between logarithmic and square-root dependence on T as β varies.At β = 1, the rate is O(d ln T).Source: §3 · p. 7
  • For hinge loss on the unit ball with i.i.d. data, β = 1 gives O(d ln T) regret without ℓ2-regularization.The passage states that the data satisfy the Bernstein condition.Source: §3 · p. 7

4 MetaGrad Algorithm

MetaGrad combines a master that aggregates predictions across a grid of learning rates with a slave for each rate. Full and diagonal slaves trade computational cost against regret guarantees, while the master weights rates by empirical performance.

4 MetaGrad Algorithm

  • The algorithm is a two-level construction: a master learns the rate while a slave runs for each rate in a finite grid.The recommended grid is given in equation (8).Source: §4 · p. 7

Master

  • The master aggregates predictions from a discrete grid of learning rates and tracks empirical performance without tuning rates from a theoretical regret bound.Its tilted exponential-weights predictions give larger weight to larger learning rates.Source: §4 · p. 7, Master · pp. 8–9

Slaves

  • Each slave controls surrogate regret at a fixed learning rate; full covariance gives the best regret bound, while diagonal covariance reduces high-dimensional runtime.Full MetaGrad maintains a d × d matrix; diagonal MetaGrad maintains d non-zero entries.Source: Slaves · p. 9
  • With m slaves, full and diagonal updates cost O(md^2) and O(md) per round and in memory, respectively.The analysis indicates m = 1 + ⌈1/2 log2 T⌉ slaves suffice, with m ≤ 16 for T ≤ 10^9.Source: Slaves · p. 9

5 Analysis

The analysis bounds the master, each learning-rate slave, and their composition to establish MetaGrad’s adaptive regret guarantee. It also specifies a learning-rate grid for the final bound.

5 Analysis

  • The analysis proceeds by bounding the master, the slaves, and their composition, then optimizing the learning rate.The master guarantees hold simultaneously for all η; each η-slave learns u, and the bounds are combined.Source: §5 · p. 10

5.1 Master

  • The master combines the slaves with a non-increasing potential, Φ0 ≥ Φ1 ≥ ··· ≥ ΦT.The analysis views this as the master’s guarantee for aggregating slave predictions.Source: §5.1 · p. 10

5.2 Slaves

  • Each slave has O(d ln T) regret in its surrogate loss; the diagonal case uses directional exp-concavity despite lacking joint exp-concavity.The projections tying dimensions together do not invalidate the diagonal bound.Source: §5.2 · pp. 10–11

5.3 Composition

  • An exponentially spaced grid with a heavy-tailed prior supports the composition bound; full MetaGrad achieves Theorem 1’s adaptive guarantee.The diagonal version behaves like running full MetaGrad separately per dimension, but with one shared learning rate.Source: §5.3 · pp. 11–12

6 Discussion and Future Work

The discussion identifies high-dimensional speed and broader adaptivity as future directions. Supplementary simulations illustrate logarithmic regret without curvature in two one-dimensional settings.

6 Discussion and Future Work

  • High-dimensional speed and adaptation to additional practically relevant easy-function classes remain directions for future work.The authors suggest sketching as one possible way to speed up MetaGrad in high dimensions.Source: §6 · p. 12

A Extra Material Related to Section 3

A.1 Simulations: Logarithmic Regret without Curvature

  • In two one-dimensional examples, MetaGrad achieves O(ln T) regret while AdaGrad follows O(√T); the authors caution that higher-dimensional behavior may differ because MetaGrad shares rates across dimensions.The examples use a fixed absolute-value function and stochastic absolute-value losses with unequal outcome probabilities.Source: §A.1 · p. 15

A.2 Proof of Theorem 2

The proof applies condition (3) at the algorithm’s choices and invokes Theorem 1. Figure 1 reports logarithmic regret for MetaGrad and linear regret for AdaGrad in its examples.

A.2 Proof of Theorem 2

  • The proof applies condition (3) with w = wt and Theorem 1 to obtain an eventual bound with a constant depending on a.Source: §A.2 · p. 15
  • Figure 1 reports O(ln T) regret for MetaGrad and O(T) regret for AdaGrad, matching AdaGrad’s bound.Source: Figure 1 · p. 16

A.3 Proof of Theorem 3

The proof bounds expected linearized regret using Jensen’s inequality and the Bernstein condition. It then applies an inequality with selected parameters to complete the derivation.

A.3 Proof of Theorem 3

  • Jensen’s inequality and the Bernstein condition yield an upper bound on expected linearized regret for sufficiently large T.Source: §A.3 · p. 16
  • The proof repeatedly applies inequality (9), first with α = 1/2 and later with α = β when β < 1.Source: §A.3 · p. 16
  • For β < 1, the proof further optimizes over γ2 by applying inequality (9) with α = 1/(2−β).Source: §A.3 · p. 17

A.4 Unregularized Hinge Loss Example

For unregularized hinge loss on the unit ball, the Bernstein condition holds with exponent β = 1 when ∥µ∥ > 0. This yields logarithmic regret without adding ℓ2-regularization.

A.4 Unregularized Hinge Loss Example

  • For unit-ball hinge loss, the (B, β)-Bernstein condition holds with β = 1 and B = 2λmax/∥µ∥ when ∥µ∥ > 0.Here λmax is the maximum eigenvalue of E[XX⊺], and µ = E[YX].Source: §A.4 · p. 17
  • Except when ∥µ∥ = 0, the hinge-loss condition implies an O(d ln T) rate; at ∥µ∥ = 0, expected hinge loss is 1 for every u.The passage identifies this excluded case as one where there is nothing to learn.Source: §A.4 · p. 17
  • Adding ℓ2-regularization to make hinge loss strongly convex is not necessary to obtain logarithmic regret.For uniformly distributed sphere inputs with noiseless hyperplane labels, the passage further states B ≤ c for an absolute constant c.Source: §A.4 · p. 17

B Master Regret Bound (Proof of Lemma 4)

The proof establishes that the potential does not increase, using a tangent bound on the exponential term. The bound uses different α values for the full and diagonal cases.

B Master Regret Bound (Proof of Lemma 4)

C Slave Regret Bound (Proof of Lemma 5)

The slave-regret proof represents predictions with Gaussian distributions, updates them by exponential weights, and bounds regret through KL divergence. The following theorem-proof step expands the surrogate losses to obtain its claim.

C Slave Regret Bound (Proof of Lemma 5)

  • The algorithm plays the mean of a Gaussian prior N(0, D²I), then applies exponential weights and projects onto distributions whose means lie in U.The proof verifies that the Gaussian update preserves the stated form under projection.Source: C Slave Regret Bound (Proof of Lemma 5) · pp. 18–19
  • The proof bounds distribution-space regret using KL divergence and a telescoping sum, then relates it to the regret of interest.It restricts the comparator to Gaussians with mean in U and positive covariance, and optimizes the resulting bound in Σ.Source: C Slave Regret Bound (Proof of Lemma 5) · pp. 19–20

D.1 Proof of Theorem 6

  • The proof of Theorem 6 expands the surrogate losses from (6) and divides by η to obtain the claim..Source: §D.1 · p. 20

D.2 Proof of Theorem 7

The proofs derive bounds for the full and diagonal versions, discuss a prior over learning rates, and establish supporting Gaussian-projection and Bernstein-condition results. These results constrain the Gaussian argument and connect stochastic excess loss to its linearized form.

D.2 Proof of Theorem 7

  • Theorem 7’s proof handles the intractable η-dependent log-determinant bound through a variational form and comparator covariance choices.The full-case bound involves rk(ST); the proof also gives a second claim using the prior covariance as comparator.Source: §D.2 · pp. 20–22

E Discussion of the Choice of Grid Points and Prior Weights

  • A prior density proportional to 1/η is approximately uniform in ln η; integrating it between grid points gives discrete prior masses.Grid points within a constant factor guarantee the same bound up to a constant factor, and the density includes a factor for rescaling invariance.Source: E Discussion of the Choice of Grid… · pp. 22–23

F Projection of Gaussians

  • Projecting a Gaussian onto distributions with mean in convex U preserves its covariance, while the projected mean minimizes a covariance-weighted distance..Source: F Projection of Gaussians · pp. 23–24

G Gaussian Exp-concavity

  • The Gaussian exp-concavity argument is stated for Gaussians with mean in U and arbitrary positive covariance in the full case, or diagonal covariance in the diagonal case.The passage cautions that the property does not hold for general distributions supported outside U.Source: G Gaussian Exp-concavity · p. 24

H Bernstein for Linearized Excess Loss

  • A Bernstein condition on stochastic excess loss transfers with the same exponent β to the linearized excess loss, when the latter is bounded and pointwise at least the former.The linearized excess loss is bounded above by DfullGfull.Source: H Bernstein for Linearized Excess Loss · p. 25

Related papers

Loading 1604.08740v3…