Dimension-Free Exponentiated Gradient

Francesco OrabonaNeurIPS 2013 · OpenReview

Introduction

In online learning, an algorithm makes sequential predictions and updates its hypothesis as true labels are continually revealed. The primary goal is to minimize regret—the difference between the algorithm's cumulative loss and that of the best fixed "competitor" vector $u$ chosen in hindsight.

Historically, two main families of algorithms have dominated this space, each with distinct trade-offs:

  1. Gradient Descent (GD) variants: These algorithms yield regret bounds proportional to the $L_2$ norm of the competitor ($\|u\|_2$). While they function well in any dimension, they require prior knowledge of $\|u\|_2$ to optimally tune the learning rate.
  2. Exponentiated Gradient (EG) variants: Utilizing multiplicative updates, these algorithms achieve regret bounds that scale logarithmically with the dimension $d$ (e.g., $\sqrt{T \log d}$). They excel in high-dimensional, sparse problems but fail entirely in infinite-dimensional settings (such as those leveraging the "kernel trick") because $\log(\infty)$ is undefined.

Francesco Orabona introduces the Dimension-Free Exponentiated Gradient (DFEG), a novel online learning algorithm designed to bridge this gap. DFEG brings the aggressive learning benefits of multiplicative updates to infinite-dimensional spaces. It is both dimension-free (like GD) and parameter-free (requiring no prior knowledge of $\|u\|_2$), automatically adapting to the scale of the optimal competitor.

Methods: Time-Varying Online Mirror Descent

To achieve these properties, DFEG is derived by instantiating the Online Mirror Descent (OMD) framework with a carefully designed time-varying regularizer.

Time-varying Online Mirror Descent Algorithm.
  • The Regularizer: Instead of relying on the standard squared Euclidean norm or an entropic regularizer over individual coordinates, DFEG employs a regularizer based on the norm of the weight vector itself: $f_t(w) = \alpha_t \|w\| (\ln(\beta_t \|w\|) - 1)$.
  • Time-Variation: The parameters $\alpha_t$ and $\beta_t$ are dynamically updated based on the cumulative norm of the gradients encountered so far. This mechanism allows the algorithm to "self-tune" its learning rate on the fly.
  • Local Smoothness: Standard OMD analysis typically relies on global strong convexity, which this new regularizer lacks. To overcome this, the paper introduces a "local smoothness" analysis of the dual function, providing a tighter method to bound regret when the regularizer evolves over time.
  • Kernelization: Because the algorithm only requires inner products between vectors, it can be seamlessly kernelized to operate in infinite-dimensional Hilbert spaces.

Key Insights

The core "aha moment" of DFEG is applying the entropic regularizer to the norm of the weight vector rather than its individual components. This effectively treats the overall "magnitude" of the hypothesis as a budget to be managed multiplicatively, entirely bypassing any dependency on the number of dimensions.

By making the regularizer time-varying based on observed data, the algorithm implicitly estimates the scale of the optimal competitor. The author also proves a theoretical lower bound: if an algorithm is designed to have zero regret against a zero-norm competitor (a "null" model), it must incur a $\sqrt{\log(UT)}$ penalty in the regret bound for other competitors. DFEG successfully hits this theoretical limit, rendering it nearly optimal.

Empirical and Theoretical Results

Theoretical Bound

DFEG achieves a regret bound of $O(\|u\| \log(\|u\| T + 1)\sqrt{T})$. This bound is strictly "dimension-free" as the dimension $d$ does not appear in the formula. Furthermore, this bound is optimal up to the logarithmic term for linear and Lipschitz losses.

Empirical Performance

The algorithm was evaluated on a synthetic 1D dataset (testing the trade-off between competing against zero-norm vs. non-zero norm vectors) and real-world regression datasets from the LIBSVM repository (cadata and cpusmall) using a Gaussian kernel.

Empirical performance of DFEG compared to Kernel GD across synthetic and real-world datasets.

In these experiments, DFEG performed competitively with a perfectly tuned Kernel Gradient Descent. While Kernel GD can technically outperform DFEG if its learning rate $\eta$ is tuned flawlessly using the unknown $\|u\|$, DFEG proves vastly more robust. If $\eta$ is tuned even slightly incorrectly, Kernel GD's performance collapses. DFEG, on the other hand, remains stable and highly effective without requiring any manual hyperparameter tuning.

Limitations and Future Work

While DFEG represents a significant step forward, a few limitations remain:

  • Data-Dependent Bounds: The current regret bound depends on the specific sequence of input vectors $x_t$. While a looser data-independent version can be derived, tighter bounds are preferable.
  • Smooth Losses: The current paper focuses primarily on Lipschitz losses. Deriving a "gradient-adaptive" bound—one that depends on the sum of squared gradients rather than just the number of rounds $T$—remains an open challenge for this specific regularizer.
  • Computational Complexity: Like all kernel methods, DFEG's computational complexity grows with the number of rounds $T$. Future implementations will likely need to incorporate sparsification techniques to scale to massive datasets.

Summary updated

Abstract

We present a new online learning algorithm that extends the exponentiated gradient to infinite dimensional spaces. Our analysis shows that the algorithm is implicitly able to estimate the $L_2$ norm of the unknown competitor, $U$, achieving a regret bound of the order of $O(U \log (U T+1))\sqrt{T})$, instead of the standard $O((U^2 +1) \sqrt{T})$, achievable without knowing $U$. For this analysis, we introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, we also show that the algorithm is optimal up to $\sqrt{\log T}$ term for linear and Lipschitz losses.
BibTeX
@inproceedings{orabona2013dimension,
  author = {Francesco Orabona},
  title = {{Dimension-Free Exponentiated Gradient}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=S1ZeL_ZdZr},
}
Figure