Stochastic Composite Mirror Descent: Optimal Bounds with High Probabilities

Yunwen Lei, Ke TangNeurIPS 2018 · OpenReview

Introduction

While Stochastic Gradient Descent (SGD) remains the workhorse of modern machine learning, our theoretical understanding of its performance often relies on "average-case" analysis, yielding bounds only in expectation. In practice, however, practitioners require high-probability bounds to understand how an algorithm performs in a single run, accounting for the inherent variability and randomness of data sampling.

Furthermore, existing theoretical proofs frequently depend on unrealistic "boundedness assumptions"—presuming that gradients or iterates never exceed a certain magnitude, which rarely holds true in unbounded optimization domains. Finally, there is a persistent theoretical gap in explaining why multi-pass SGD (iterating over the same dataset multiple times) resists overfitting far better than traditional theory suggests. Previous bounds indicated that estimation error grows polynomially with the number of passes. This paper addresses these gaps by establishing high-probability convergence rates for Stochastic Composite Mirror Descent (SCMD) that are optimal up to a logarithmic factor, proving that multi-pass SGD is remarkably resistant to overfitting.

Methodology: Overcoming Boundedness Assumptions

The authors focus on SCMD, a generalized variant of SGD that utilizes a "mirror map" to adapt to the specific geometry of a problem (e.g., using $p$-norms for sparse problems) while seamlessly handling "composite" objectives where a data-fitting term and a regularizer are treated separately.

To move beyond restrictive boundedness assumptions, the research employs two innovative mathematical techniques:

  1. Self-Bounding Property: The authors introduce an assumption relating the norm of the subgradients to the function values themselves. This establishes that if the function value is small, the gradient is inherently constrained from becoming excessively large.
  2. Variance Offsetting: Through rigorous martingale analysis, the authors demonstrate that the conditional variances of the "noise" in the gradients can be partially offset by other terms within the algorithm's progress inequality.

Key Theoretical Insights

The theoretical analysis yields several profound insights into the behavior of SCMD and multi-pass SGD:

  • Naturally Bounded Iterates: A striking finding is that explicit boundedness assumptions are unnecessary. The authors prove that SCMD iterates automatically remain within a bounded ball—whose radius grows only logarithmically—with high probability, provided the step sizes are "square-summable" (meaning they decrease rapidly enough that the sum of their squares is finite).
  • Immunity to Overfitting: The paper provides robust theoretical justification for the empirical success of multi-pass SGD. By demonstrating that the estimation error scales logarithmically ($\log T$) rather than polynomially with the number of passes, the authors show that the algorithm remains highly resistant to overfitting over extended training periods.
  • Optimal Convergence Rates: The derived bounds match the known "minimax" lower bounds (the theoretical optimal rates) up to a small logarithmic factor. Specifically, for general convex objectives, the error scales at $O(T^{-1/2})$, and for strongly convex objectives, it scales at $O(T^{-1})$, both with high-probability confidence.
  • Generalization Performance: In a non-parametric setting utilizing Reproducing Kernel Hilbert Spaces (RKHS), the generalization error matches the best available bounds for Tikhonov regularization, a gold standard for algorithmic stability.

Empirical Validation

To validate these theoretical findings, the authors conducted simulations using several standard binary classification datasets from the LIBSVM library, including ADULT, GISETTE, IJCNN, MUSHROOMS, PHISHING, and SPLICE. These datasets encompass a wide variety of feature dimensions and sample sizes, providing a robust testbed.

The empirical results strongly supported the theory: when using appropriate step sizes (e.g., $\eta_t = 5t^{-0.51}$), the test error remained stable even after 1,000 passes over the data, practically confirming the predicted logarithmic resistance to overfitting.

Limitations and Future Directions

While this work significantly advances optimization theory, several avenues for future research remain:

  • Convexity Constraints: The current analysis strictly applies to convex and strongly convex landscapes. Extending these high-probability, unbounded guarantees to non-convex settings—such as deep neural networks—remains a formidable challenge.
  • Mirror Map Smoothness: The proofs rely on the assumption of a differentiable mirror map. Investigating mirror descent dynamics with non-differentiable maps is a promising next step.
  • The Logarithmic Gap: Although the established bounds are nearly optimal, a minor logarithmic factor gap still exists between these results and the absolute theoretical floor. Closing this gap would finalize the theoretical framework for SCMD.

Summary updated

Abstract

We study stochastic composite mirror descent, a class of scalable algorithms able to exploit the geometry and composite structure of a problem. We consider both convex and strongly convex objectives with non-smooth loss functions, for each of which we establish high-probability convergence rates optimal up to a logarithmic factor. We apply the derived computational error bounds to study the generalization performance of multi-pass stochastic gradient descent (SGD) in a non-parametric setting. Our high-probability generalization bounds enjoy a logarithmical dependency on the number of passes provided that the step size sequence is square-summable, which improves the existing bounds in expectation with a polynomial dependency and therefore gives a strong justification on the ability of multi-pass SGD to overcome overfitting. Our analysis removes boundedness assumptions on subgradients often imposed in the literature. Numerical results are reported to support our theoretical findings.
BibTeX
@inproceedings{lei2018stochastic,
  author = {Yunwen Lei and Ke Tang},
  title = {{Stochastic Composite Mirror Descent: Optimal Bounds with High Probabilities}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=9PJRkVVZSyJ},
}
Figure