PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Universality of Online Mirror Descent

Nathan Srebro, Karthik Sridharan, Ambuj Tewari

arXiv:1107.4080v1cs.LG

TL;DR

The paper asks whether general convex online learning problems can be solved with near-optimal regret using one broadly applicable method. It proves that an appropriate Online Mirror Descent distance-generating function always exists for online-learnable problems, while noting that computing it and its prox-map may be impractical. Thus, Mirror Descent is theoretically universal and near-optimal, but practical efficiency depends on tractable problem-specific choices.

  • Problem

    Prior results mainly treated settings where the constraint set and data domain are dual balls, leaving the more general non-dual convex setting to be analyzed.

  • Method

    The paper combines refined Mirror Descent regret bounds, generalized martingale type for constraint–data-domain pairs, and uniformly convex distance-generating functions.

  • Results

    For every online-learnable problem in the considered general class, an appropriate distance-generating function makes Mirror Descent achieve near-optimal regret.

  • Takeaways & Limitations

    A simple first-order method can theoretically suffice for online learning across a very broad class of convex problems, subject to suitable problem-specific geometry.

  • Takeaways & Limitations

    The required distance-generating functions and their prox-maps may be difficult to derive or compute, making non-optimal or non-Mirror-Descent methods preferable in practice.

Abstract

from arXiv · show

We show that for a general class of convex online learning problems, Mirror Descent can always achieve a (nearly) optimal regret guarantee.

1 Introduction

The paper studies whether Online Mirror Descent is universally near-optimal for general convex online learning problems, beyond matching dual-ball settings. It develops this result through refined regret analysis, generalized martingale type, and uniformly convex distance-generating functions.

  • 1 Introduction: Mirror Descent generalizes Gradient Descent to non-Euclidean geometries through a geometry-specific distance-generating function.Standard Gradient Descent corresponds to the squared ℓ2-norm, while other geometries yield other online algorithms.
  • 1 Introduction: Online Mirror Descent is nearly optimal for any online-learnable convex online problem of the paper’s general form.The result gives a near-optimal regret strategy using an appropriate distance-generating function.
  • 1 Introduction: The analysis first refines Mirror Descent regret bounds for non-dual constraint and data domains using uniformly convex distance-generating functions.This establishes an upper-bound framework for Online Mirror Descent.
  • 1 Introduction: The paper relates online-game value to a generalized martingale type that depends jointly on the constraint set and data domain.This extends the usual Banach-space martingale-type perspective to non-matching pairs.
  • 1 Introduction: The paper extends prior optimality results from dual Banach-ball settings to arbitrary convex constraint sets and data domains.Earlier work considered matching dual balls, whereas this paper analyzes the non-dual case.

2 Online Convex Learning Problem

The online convex learning problem is formulated as a repeated game in which a learner chooses predictors and an adversary supplies convex costs. The paper reduces several convex cost classes to a linear game while allowing arbitrary, non-dual constraint and data domains.

  • 2 Online Convex Learning Problem: Each round, the learner selects w_t from a closed convex set W, then incurs a convex cost f_t chosen by the adversary.The learner’s algorithm maps prior cost-function information to the next predictor.
  • 2 Online Convex Learning Problem: The learner’s objective is to minimize worst-case regret over every number of rounds.Regret compares cumulative learner cost with the best fixed comparator in W.
  • 2 Online Convex Learning Problem: For convex function classes whose subgradients lie in X, the game value equals the value for linear functionals, including Lipschitz and supervised-learning classes.The proposition states V_n(F_Lip, X, W) = V_n(F_sup, X, W) = V_n(F_lin, X, W).
  • 2 Online Convex Learning Problem: The formulation covers supervised learning, multitask learning, and matrix completion through convex losses with subgradients restricted to the data domain.The data domain X specifies the admissible subgradients.
  • 2 Online Convex Learning Problem: The framework permits arbitrary convex constraint sets W and data domains X rather than requiring W and X to be dual unit balls.The paper uses Minkowski functionals to associate norms with convex centrally symmetric sets.

3 Mirror Descent and Uniform Convexity

The paper bounds Mirror Descent regret using uniformly convex distance-generating functions defined on the constraint set, even when the governing norm and constraint set do not match. It then characterizes the best such function and relates its guarantee to the game value.

  • 3 Mirror Descent and Uniform Convexity: Mirror Descent recovers Gradient Descent with Ψ(w) = 1/2∥w∥_2^2 and multiplicative weights on the simplex with an entropic Ψ.The distance-generating function determines the geometry and update rule.
  • 3 Mirror Descent and Uniform Convexity: A q-uniformly convex distance-generating function on W yields a regret bound for Mirror Descent under the data-domain norm.The analysis requires uniform convexity only inside W, not a matching norm ball.
  • 3 Mirror Descent and Uniform Convexity: The optimal Mirror Descent guarantee lies between the game value and twice the quantity D_p: V_p ≤ MD_p ≤ 2D_p.This connects the algorithmic bound to the best possible worst-case guarantee.
  • 3 Mirror Descent and Uniform Convexity: Uniform convexity supplies the mechanism for obtaining diminishing regret when an appropriate distance-generating function exists.The unresolved question is when such functions exist and what rates they provide.
  • 3 Mirror Descent and Uniform Convexity: The paper defines the best admissible function as the nonnegative q-uniformly convex function minimizing the Mirror Descent bound.If no such function exists, the corresponding optimum is defined as infinity.

4 Martingale Type and Value

The paper extends martingale type to pairs consisting of a constraint set and data domain, then connects this notion to online-game value and regret. These relationships provide the bridge needed to characterize online learnability in the non-dual setting.

  • 4 Martingale Type and Value: Martingale type is generalized from a Banach space to a pair (W⋆, X) so that it accounts for both constraint and data domains.The generalized definition uses sequences of mappings indexed by sign vectors.
  • 4 Martingale Type and Value: The pair (W, X) has martingale type p when signed sequences satisfy the corresponding growth inequality with constant C.The definition extends the usual martingale-type condition to non-matching domains.
  • 4 Martingale Type and Value: Prior results imply that martingale type bounds online-game value, including for non-matching W and X: V_p ≤ 2C_p.The value is therefore controlled by the martingale-type constant.
  • 4 Martingale Type and Value: The paper’s main direction is that low online regret implies martingale type by relating game value to martingale convergence rates.It extends Pisier’s result to the non-matching setting.
  • 4 Martingale Type and Value: A martingale-type consequence follows from the paper’s growth condition for every p′ < p, with C_p′ bounded by 1104 V_p.This supplies the reverse connection from online-game value to martingale type.

5 Uniform Convexity and Martingale Type

The paper extends Martingale type from Banach spaces to pairs of constraint and data domains, linking this notion to uniformly convex distance-generating functions.

  • 5 Uniform Convexity and Martingale Type: Martingale type of a pair (W⋆, X) is related to the existence of uniformly convex functions tailored to both domains.This extends the classical connection between Banach-space Martingale type and uniformly convex functions.
  • 5 Uniform Convexity and Martingale Type: If (W⋆, X) has Martingale type p, a convex function Ψ exists that is q-uniformly convex with respect to the relevant norm.The construction satisfies Ψ(0) = 0 and provides the function required for the Mirror Descent analysis.
  • 5 Uniform Convexity and Martingale Type: Dp ≤ Cp for any p ∈ [1, 2], connecting the optimal distance-generating-function parameter to the generalized Martingale-type constant.The proof also gives a specific uniformly convex function establishing this bound.

6 Optimality of Mirror Descent

The paper combines Mirror Descent bounds, generalized Martingale type, and game-value lower bounds to obtain near-optimal regret for online-learnable convex problems.

  • 6 Optimality of Mirror Descent: If Vn(W, X) ≤ V n^(−1/q) for q ∈ [2, ∞), an appropriate regularizer Ψ and step size η yield a bounded-regret Mirror Descent algorithm.The guarantee applies for n > e^(q−1).
  • 6 Optimality of Mirror Descent: The result follows by combining the Mirror Descent guarantee with the uniformly convex-function construction and a lower bound on the repeated-game value.This establishes near-optimal rates whenever the problem is online learnable.
  • 6 Optimality of Mirror Descent: Mirror Descent achieves regret at most a factor of 6002 log(n) from the best possible worst-case upper bound.The constant V enters linearly, with no other problem- or space-dependent hidden constants in the bound.
  • 6 Optimality of Mirror Descent: A suitable q-uniformly convex norm can be sought between the data-domain dual norm and a scaled version of the constraint-set norm.This provides a practical guideline for selecting Ψ.
  • 6 Optimality of Mirror Descent: Figure 1 summarizes the relationships among the constants used in the optimality analysis.The arrow from Cp′ to Cp indicates that the quantities are within a log^2 n factor for any n.

7 Examples

The paper applies its framework to non-dual norm pairs, matrix completion, interpolation norms, Schatten norms, and group norms, deriving problem-specific regret guarantees and scope boundaries.

  • 7 Examples: The examples cover non-dual ℓp, Schatten, group, max-norm, and interpolation-norm pairs, demonstrating how the framework selects appropriate regularizers.These settings include applications such as matrix completion and multitask learning.
  • 7 Examples: The table identifies scenarios where r = 2 permits a D2/√n rate and gives corresponding D2 values up to a numeric constant of at most 16.The first two rows are dimension free, while other cases require finite dimension for finite D2.
  • 7 Examples: When d is infinite, p1 > 2, and q2 ≥ p1, D2 = ∞, so an O(1/√n) rate is not expected; however, Dp2 < 16 remains available.This illustrates how the framework provides a different finite-rate guarantee when the D2 condition fails.
  • 7 Examples: For max-norm matrix completion, the derived online regret bound matches the stochastic PAC guarantee and is presented as the first known guarantee for this setting.The construction uses a uniformly convex regularizer based on the max-norm geometry.
  • 7 Examples: Interpolation-norm bounds are obtained by controlling the relevant D2 quantity through the component norms used in the interpolation.The resulting bounds apply to examples including structured linear prediction and matrix-completion settings.
  • 7 Examples: The interpolation results are only upper bounds, and the paper leaves tighter analysis and interpolation among more than two norms open.This is stated as a limitation of the presented treatment.

8 Conclusion and Discussion

The paper concludes that an appropriate distance-generating function makes Mirror Descent nearly regret-optimal for a broad class of convex online problems, while practical use depends on computable choices and prox-maps. It also identifies convexity and the chosen subgradient-based cost-class formulation as important scope conditions, and leaves stochastic optimality open.

  • Conclusion: An appropriate distance-generating function always exists for the considered convex online problems, giving Mirror Descent a near-optimal regret guarantee.The resulting method requires gradient and prox-map computations at each iteration.
  • Practical limitations: Efficient use may require non-optimal distance-generating functions or a different method when the theoretically appropriate prox-map is not efficiently computable.The paper also notes that sparsity or other desired properties can favor alternative methods.
  • Scope conditions: The analysis requires a convex constraint set W, while the role of convexity for the data domain X remains less settled in relevant non-convex applications.The paper discusses sparse data, indicator-valued data, and total-variation regularization as examples motivating this issue.
  • Scope conditions: The cost class is constrained through convex cost functions and their subgradients, covering supervised learning with arbitrary convex losses in the stated worst-case setting.Under this formulation, restricting subgradients corresponds to restricting the data domain.
  • Open questions: Whether Mirror Descent is universally optimal for stochastic convex optimization or convex statistical learning remains an open question.The paper motivates this question through the efficiency of online methods and online-to-batch conversion, especially in high-dimensional settings.

Appendix

The appendix develops the technical bridge from martingale-type assumptions to uniformly convex distance-generating functions and the resulting Mirror Descent guarantees. Its lemmas establish the required smoothness, convexity, and martingale-type properties through a sequence of probabilistic and convex-analytic steps.

  • Mirror Descent analysis: The appendix relates the Bregman divergence and convex conjugate to the uniformly convex potential required in the Mirror Descent guarantee.The Bregman divergence is the divergence associated with Ψ and appears in the proof of the update bound.
  • Distance-generating function: A convex function Ψ* is constructed with p-uniform smoothness, and convex duality yields a q-uniformly convex conjugate Ψ for the Mirror Descent analysis.The construction is tied to the equivalence between martingale-type inequalities and uniformly convex potentials.
  • Proof construction: The proof handles sign-indexed sequences by truncating them to finite support, introducing stopping times, and applying successive lemmas to control the resulting processes.These steps are used to derive the inequalities needed for the martingale-type conclusion.
  • Martingale-type argument: The appendix proves that the relevant pair (W, X) has martingale type p, completing the central structural implication used by the analysis.This result is reached after a sequence of lemmas controlling finite sign-indexed sequences and passing to the limit.
  • Supporting result: A proposition from prior work supplies the probabilistic inequality used in the later lemma connecting the value bound V_n(W, X) to martingale type.The proof then invokes the preceding lemmas to complete the stated implication.
Loading 1107.4080v1…