Fast Rates for Exp-concave Empirical Risk Minimization

Tomer Koren, Kfir Y. LevyNeurIPS 2015 · OpenReview

Introduction

Empirical Risk Minimization (ERM) is the foundational workhorse of machine learning. A central question in statistical learning theory is how quickly a model's performance on training data (empirical risk) converges to its performance on unseen data (expected risk). For generic convex functions, this generalization gap typically shrinks at a rate of $O(1/\sqrt{n})$. For strongly convex functions, it accelerates to a "fast rate" of $O(1/n)$.

This paper investigates exp-concave loss functions—a broader, more complex class that includes linear regression, logistic regression, squared hinge-loss SVMs, and portfolio selection. The authors provide the first proof that ERM achieves an optimal fast generalization rate of $O(d/n)$ for exp-concave and smooth losses, where $d$ is the dimensionality and $n$ is the number of samples.

The Theoretical Gap

Previously, it was known that specific, computationally expensive online algorithms (like the Online Newton Step) could achieve a fast rate of $O(d/n)$ for exp-concave losses. However, it remained unclear if the simpler and widely used ERM approach could match this performance. Prior bounds for ERM on exp-concave losses were either stuck at the slow $O(1/\sqrt{n})$ rate or burdened by an extraneous $\log n$ factor.

By eliminating this ubiquitous $\log n$ penalty, the authors demonstrate that ERM is not only statistically optimal but also practically advantageous. Because ERM can be solved using highly efficient, state-of-the-art solvers (like SVRG or SDCA), proving its statistical optimality justifies using these fast solvers for large-scale exp-concave problems instead of relying on complex online-to-batch conversions.

Methodological Innovations

The authors analyze a slightly regularized ERM procedure. Instead of the standard "heavy" penalty of $O(1/\sqrt{n})$, they apply a "light" penalty of $O(1/n)$—just enough to ensure a unique solution without washing out the underlying signal.

The core proof relies on Stability Analysis. A model is considered stable if removing a single random data point from the training set does not significantly alter the resulting model. The technical breakthrough lies in leveraging Local Strong Convexity. While exp-concave functions are not strongly convex everywhere, they exhibit strong convexity locally when evaluated through a "local norm" based on the curvature (Hessian) at a specific point.

By bounding the average leave-one-out stability using these local norms and the Sherman-Morrison identity (a technique for updating matrix inverses), the authors strictly control the model's fluctuations. Notably, they prove that "average stability" is sufficient for exp-concave functions, bypassing the much stricter requirement of "uniform stability" used in previous proofs.

Key Results and Implications

  • Optimal $O(d/n)$ Bound: For $\alpha$-exp-concave and $\beta$-smooth losses, the expected excess risk of the regularized ERM solution is strictly bounded by $O(d/n)$.
  • Matching Lower Bounds: In specific cases like squared loss (linear regression), this result perfectly matches the known theoretical lower bound of $\Omega(d/n)$, confirming ERM's absolute optimality in this setting.
  • State-of-the-Art Improvement: The findings improve upon the best-known rates for the Online Newton Step by a factor of $\log n$, and for algorithms like Vovk-Azoury-Warmuth by a factor of $\log(n/d)$.
  • Oblivious Adaptivity: ERM naturally adapts to the "easiness" of the problem without requiring prior knowledge of the specific data distribution properties.

Limitations and Future Directions

As a purely theoretical work, the paper relies on mathematical proofs rather than empirical benchmarks. The authors note several open challenges for future research:

  1. The Smoothness Requirement: The current proof necessitates a smooth loss function (Lipschitz continuous gradient). It remains an open question whether ERM can achieve fast rates for non-smooth exp-concave losses, a setting where some online algorithms currently succeed.
  2. High-Probability Bounds: The established rates hold "in expectation." Extending these $O(1/n)$ rates to high-probability guarantees (e.g., proving the rate holds with 99% certainty) without sacrificing the fast convergence rate is a significant next step.
  3. Regularization-Free ERM: While the $O(1/n)$ regularizer is minimal, proving that ERM can achieve these rates without any regularization across all exp-concave functions remains an open problem.

Summary updated

Abstract

We consider Empirical Risk Minimization (ERM) in the context of stochastic optimization with exp-concave and smooth losses---a general optimization framework that captures several important learning problems including linear and logistic regression, learning SVMs with the squared hinge-loss, portfolio selection and more. In this setting, we establish the first evidence that ERM is able to attain fast generalization rates, and show that the expected loss of the ERM solution in $d$ dimensions converges to the optimal expected loss in a rate of $d/n$. This rate matches existing lower bounds up to constants and improves by a $\log{n}$ factor upon the state-of-the-art, which is only known to be attained by an online-to-batch conversion of computationally expensive online algorithms.
BibTeX
@inproceedings{koren2015fast,
  author = {Tomer Koren and Kfir Y. Levy},
  title = {{Fast Rates for Exp-concave Empirical Risk Minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=HyZ7cLbdbB},
}
Figure