An optimal algorithm for stochastic strongly-convex optimization

Elad Hazan, Satyen KalearXiv 2010 · DOI · arXiv

Abstract

We consider stochastic convex optimization with a strongly convex (but not necessarily smooth) objective. We give an algorithm which performs only gradient updates with optimal rate of convergence.

Introduction

In the field of machine learning, many core problems—such as training Support Vector Machines (SVMs)—rely on minimizing a loss function that is strongly convex. Strong convexity implies the function has a "bowl" shape at least as curved as a specific quadratic function, a property that theoretically allows for faster convergence than general convex optimization.

While Stochastic Gradient Descent (SGD) is the standard tool for these problems, traditional implementations using a smooth $1/t$ learning rate decay often fail to reach the theoretical "speed limit" of optimization. This paper introduces Epoch-GD, a simple, gradient-only algorithm that achieves the optimal convergence rate of $O(1/\epsilon)$, bridging the gap between simple heuristics and theoretical optimality.

The Epoch-GD Algorithm

The core innovation of this research is the organization of iterations into "epochs" with a discrete, exponentially decreasing learning rate schedule. Unlike standard SGD, which updates the learning rate at every step, Epoch-GD maintains a constant learning rate for the duration of an epoch.

Algorithm Structure

  1. Fixed-Length Epochs: The algorithm operates in stages. Within each stage (epoch), the learning rate remains fixed.
  2. Exponential Scaling: At the conclusion of an epoch, the algorithm initiates a new one where the learning rate is halved (or scaled down exponentially) and the number of iterations is doubled.
  3. Iterate Averaging: Rather than using the final point of an epoch as the starting point for the next, the algorithm uses the average of all points visited during that epoch. This helps to "smooth out" the stochastic noise inherent in gradient estimates.

High Probability Variant

For applications requiring strict guarantees, the authors provide a modified version of the algorithm. This variant includes a projection step that ensures the current iterate does not stray too far from the epoch's starting point. By projecting the guess back into a ball of radius $V_k$, the algorithm can guarantee an error of $\epsilon$ with probability $1-\delta$, incurring only a minimal logarithmic penalty ($ \log(1/\delta)$).

Key Results and Insights

The primary contribution of this work is the proof that Epoch-GD is theoretically optimal.

  • Optimal Complexity: The algorithm reaches an error of $\epsilon$ in $O(\frac{G^2}{\lambda \epsilon})$ steps, where $G$ is the gradient bound and $\lambda$ is the strong convexity parameter. This matches the known lower bounds for this class of problems.
  • Efficiency Gains: This rate is significantly faster than the $O(1/\epsilon^2)$ rate required for general convex functions, demonstrating the power of leveraging strong convexity.
  • Simplicity: The results show that complex second-order methods (like those using Hessians) or complicated proximal mappings are unnecessary to achieve peak efficiency; well-scheduled gradient updates are sufficient.

Limitations and Future Directions

While Epoch-GD is theoretically optimal, it requires prior knowledge of the strong convexity parameter ($\lambda$) and the gradient bound ($G$) to set the epoch lengths and learning rates correctly. In practical settings, these parameters are often unknown and must be estimated or tuned via cross-validation.

Future research may explore extending these results to non-Euclidean geometries or investigating whether stopping epochs at a random point (rather than a fixed end-point) could yield further constant-factor speedups in convergence.

Summary updated

Abstract

We consider stochastic convex optimization with a strongly convex (but not necessarily smooth) objective. We give an algorithm which performs only gradient updates with optimal rate of convergence.
BibTeX
@misc{hazan2010optimal,
  author = {Elad Hazan and Satyen Kale},
  title = {{An optimal algorithm for stochastic strongly-convex optimization}},
  year = {2010},
  eprint = {1006.2425},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1006.2425},
}
Figure