Mind the Duality Gap: Logarithmic regret algorithms for online optimization

Shai Shalev-Shwartz, Sham M. KakadeNeurIPS 2008 · OpenReview

Introduction

In the realm of online learning, a learner iteratively makes predictions and incurs a loss based on the environment's response. The primary objective is to minimize regret—the difference between the learner's cumulative loss and the loss of the best fixed decision chosen in hindsight.

For general convex functions, the optimal regret typically scales as $O(\sqrt{T})$, where $T$ is the number of rounds. However, many practical machine learning problems involve strongly convex functions (such as squared loss or log loss), which theoretically allow for a much faster logarithmic regret rate of $O(\log T)$. Historically, algorithms achieving this logarithmic regret were analyzed on a case-by-case basis, lacking a unified theoretical foundation. This paper introduces a comprehensive primal-dual framework that provides a universal template for designing and analyzing online strongly convex optimization algorithms, bridging the gap between computational simplicity and optimal performance.

The Primal-Dual Framework

The authors shift the focus from purely primal loss functions to a primal-dual perspective. By maintaining dual variables, the framework systematically increases a dual objective function at each step.

A core component of this approach is the strong convexity decomposition. The authors demonstrate that any $\sigma$-strongly convex function can be expressed as a fixed strongly convex "complexity" function plus a varying convex function. This perspective treats strong convexity as a resource that accumulates over time, elegantly explaining why the optimal learning rate for these problems is $1/(\sigma t)$ (decaying over time) rather than the $1/\sqrt{t}$ rate used in general convex optimization.

By incrementally increasing the dual objective value, the algorithm effectively closes the duality gap. The authors prove that any algorithm increasing the dual objective by a sufficient margin at each step guarantees $O(\log T)$ regret.

The Aggressiveness Spectrum

A major breakthrough of this framework is the unification of seemingly disparate algorithms through the lens of duality. The authors identify an "aggressiveness spectrum" based on how rigorously an algorithm maximizes the dual objective:

  • Gradient Descent (GD): Represents the "least aggressive" update, making the smallest permissible increase to the dual objective.
  • Follow-The-Leader (FTL): Represents the "most aggressive" approach, fully optimizing the dual objective at every single step.

Bridging the Gap: Online Coordinate-Dual-Ascent

Recognizing that FTL is often computationally prohibitive due to the need for full optimization at every round, the authors propose a novel intermediate algorithm: Online Coordinate-Dual-Ascent. This method optimizes the dual objective only with respect to the most recent variable. It offers a pragmatic middle ground, sharing the computational simplicity of Gradient Descent while achieving the lower regret typically associated with more aggressive methods.

Key Theoretical Results

The framework yields the tightest known logarithmic regret bounds for both FTL and the specific gradient descent algorithm previously proposed by Hazan et al. (2006). Through formal proofs (Theorems 1 and 2), the authors establish that any algorithm derived from their primal-dual template—including extensions for generalized strongly convex functions and arbitrary norms—will satisfy the $O(\log T)$ regret bound.

Furthermore, the paper identifies two primary "knobs" for tuning online algorithms:

  1. Style: Dictated by the choice of the complexity function, such as $L_2$ norm versus KL-divergence.
  2. Aggressiveness: The degree to which the algorithm attempts to maximize the dual objective at each step.

Limitations and Future Directions

As a purely theoretical work, the paper focuses on establishing mathematical bounds and algorithmic foundations rather than empirical benchmarks. The $O(\log T)$ regret guarantees strictly depend on the strong convexity assumption; if the loss functions are merely convex, the regret reverts to the standard $O(\sqrt{T})$ rate.

Additionally, while FTL provides excellent regret bounds, its computational cost remains a barrier for large-scale applications. Future research directions include applying the Online Coordinate-Dual-Ascent method to high-dimensional machine learning tasks to empirically validate its performance gains over standard Gradient Descent in practical scenarios.

Summary updated

Abstract

We describe a primal-dual framework for the design and analysis of online strongly convex optimization algorithms. Our framework yields the tightest known logarithmic regret bounds for Follow-The-Leader and for the gradient descent algorithm proposed in HazanKaKaAg06. We then show that one can interpolate between these two extreme cases. In particular, we derive a new algorithm that shares the computational simplicity of gradient descent but achieves lower regret in many practical situations. Finally, we further extend our framework for generalized strongly convex functions.
BibTeX
@inproceedings{shalevshwartz2008mind,
  author = {Shai Shalev-Shwartz and Sham M. Kakade},
  title = {{Mind the Duality Gap: Logarithmic regret algorithms for online optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=ry4eA_ZdbS},
}
Figure