Adaptive Online Gradient Descent

Peter L. Bartlett, Elad Hazan, Alexander RakhlinNeurIPS 2007 · OpenReview

Overview

This paper introduces Adaptive Online Gradient Descent (AOGD), an algorithm that automatically adjusts to the "curviness" of loss functions in online optimization. It bridges the gap between the slow $O(\sqrt{T})$ regret of general convex functions and the fast $O(\log T)$ regret of strongly convex functions, all without requiring prior knowledge of the function's properties.

The Problem: Online Convex Optimization

In Online Convex Optimization (OCO), a player repeatedly chooses actions to minimize a sequence of loss functions revealed sequentially by an adversary. The primary goal is to minimize regret: the difference between the player's total accumulated loss and the loss of the best fixed action chosen in hindsight.

Historically, optimization in this setting has been divided into two main regimes:

  1. General Convex Functions: Standard algorithms like Zinkevich’s Online Gradient Descent achieve a regret bound of $O(\sqrt{T})$.
  2. Strongly Convex Functions: If the functions exhibit a "bowl shape"—specifically, possessing a known lower bound $H$ on their second derivative—algorithms can achieve a much faster $O(\log T)$ regret.
Algorithm 1: Standard Online Gradient Descent

The catch lies in the requirement for prior knowledge. To achieve the faster $O(\log T)$ rate, standard algorithms must know the value of $H$ in advance to properly calibrate the step size $\eta_t$. If $H$ is unknown, or if the functions turn out not to be strongly convex, these algorithms can fail catastrophically. This paper asks a fundamental question: Can we design a single algorithm that adapts to the curvature of the data on the fly, achieving the best possible regret rate for any given sequence?

Methods: Adaptive Regularization

To solve this, the authors propose a technique called Adaptive Regularization. Instead of performing standard gradient descent on the raw loss functions, they modify the loss functions by adding a time-varying quadratic penalty (regularization):

$$\tilde{f}_t(x) = f_t(x) + \frac{1}{2}\lambda_t \|x\|^2$$

Key components of this approach include:

  • Dynamic Balancing: The algorithm intelligently chooses the regularization parameter $\lambda_t$ by balancing two competing terms in the regret bound: a "bias" term introduced by the regularization itself, and a "flatness" term related to the gradients of the loss functions.
  • Adaptive Step Sizes: The step size $\eta_t$ is dynamically set based on the cumulative curvature observed so far ($H_{1:t}$) combined with the cumulative regularization applied ($\lambda_{1:t}$).
  • Generalization to Norms: While the primary algorithm is formulated using Euclidean distance, the authors extend their theory to general norms using Bregman Divergences. This makes the results applicable to a wider variety of geometry-specific optimization problems, akin to Mirror Descent.
Algorithm 3: General-Norm Online Gradient Descent

Key Insights and Results

The "Oracle" Property

The most striking theoretical insight is that AOGD satisfies a type of "oracle inequality." The algorithm performs within a constant factor (specifically, a factor of 6) of the best possible regret bound that could have been achieved if an omniscient oracle had provided the optimal sequence of regularization parameters in advance.

Seamless Interpolation and Optimality

The algorithm does not merely switch between a "slow" mode and a "fast" mode. Instead, it provides a seamless spectrum of intermediate regret rates depending on how the curvature of the functions evolves over time:

  • For linear or general convex functions, it naturally recovers the $O(\sqrt{T})$ rate.
  • For strongly convex functions, it recovers the optimal $O(\log T)$ rate.
  • For functions with decaying curvature (e.g., $H_t = t^{-\alpha}$), it achieves an intermediate $O(T^\alpha)$ regret.

Furthermore, the authors prove that the algorithm is "strongly optimal." Its performance remains robust even when the adversary provides an adversarial mix of easy (highly curved) and hard (flat) functions.

Removing Prior Knowledge

A crucial contribution of the paper is demonstrating that even for standard "log-regret" algorithms, the strict requirement to know the lower bound of the second derivative ($H$) beforehand can be relaxed. Practitioners can simply use the observed curvature at each step to set the step size, maintaining strong theoretical guarantees.

Limitations and Future Work

While theoretically robust, the approach has a few limitations:

  • Knowledge of Curvature: The algorithm assumes the player can compute or observe $H_t$ (the lower bound on the second derivative of the current loss function). In complex "black-box" optimization scenarios, estimating this value on the fly might be difficult.
  • Constant Factors: The proven regret bound is 6 times the "optimal" oracle bound. While theoretically sound, a factor of 6 can be large in practical applications. Future work could focus on tightening this constant.
  • Computational Overhead: Calculating the optimal $\lambda_t$ requires solving a quadratic equation at each step. While this is computationally cheap ($O(1)$), it does add a minor layer of complexity compared to vanilla Stochastic Gradient Descent (SGD).

Summary updated

Abstract

We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates T and log T . Furthermore, we show strong optimality of the algorithm. between Finally, we provide an extension of our results to general norms.
BibTeX
@inproceedings{bartlett2007adaptive,
  author = {Peter L. Bartlett and Elad Hazan and Alexander Rakhlin},
  title = {{Adaptive Online Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2007},
  url = {https://openreview.net/forum?id=HJbQjdb_bB},
}
Figure