In the world of stochastic convex optimization, there has long been a nagging discrepancy between what we can prove happens on average and what we can prove happens almost certainly. While we have excellent bounds for convergence "in expectation," proving that an algorithm works with "high probability" has traditionally required assuming the search space is bounded—a restriction that doesn't always hold in the real world.
In this paper, Alina Ene and Huy L. Nguyen bridge this gap. They present a generic approach to show high-probability convergence for both Stochastic Mirror Descent (SMD) and its accelerated counterpart, with bounds that depend only on the distance from the starting point to the optimal solution, rather than the diameter of the entire domain.
TL;DR
The authors provide a novel analysis framework that proves stochastic optimization algorithms converge with high probability on potentially unbounded domains. By using a weighted martingale concentration argument, they achieve convergence rates that match the best-known results in expectation while depending only on the initial distance to the optimum.
What Problem Does This Paper Address?
In stochastic gradient descent (SGD), we don't have access to the true gradient of a function; we only have a noisy estimate.
Standard proofs show that, in expectation, the gap between our current function value and the minimum decreases at a rate proportional to the distance between our starting point ($x_1$) and the optimal point ($x^*$). However, if you want to guarantee that the algorithm succeeds with high probability (say, $1 - \delta$), classical results often produce bounds that depend on the diameter of the domain.
This is a problem because:
- The domain might be huge or even infinite (unbounded).
- The diameter is often much larger than the actual distance you need to travel, leading to overly pessimistic guarantees.
The authors set out to prove that you can get high-probability bounds that look just like the "in expectation" bounds—depending only on the initial distance to the solution.
Methods
The paper analyzes two primary algorithms: Stochastic Mirror Descent and Accelerated Stochastic Mirror Descent.
The core innovation isn't a new algorithm, but a new proof technique based on concentration inequalities for martingales.
- The Standard Approach: Usually, researchers analyze the sum of the errors in the gradient estimates. If the domain is bounded, they use standard martingale inequalities to show this sum doesn't grow too large.
- The New Approach: The authors analyze a weighted sum of these errors. They introduce a sequence of non-increasing weights ($w_t$). These weights decrease over time to account for the fact that as the algorithm progresses, our "grip" on the distance to the optimal solution becomes looser relative to the noise.
By carefully choosing these weights and analyzing the moment-generating function of the resulting random variable, they show that the progress made in reducing the function value can "absorb" the variance of the stochastic noise.
Datasets
This is a theoretical paper focused on proving convergence rates and mathematical properties. Consequently, no datasets were used for training or empirical evaluation.
Key Insights and Ideas
- Distance vs. Diameter: The most significant "aha moment" is realizing that high-probability bounds don't have to depend on the domain's diameter. By changing how we weight the history of the algorithm's progress, we can make the math work for unbounded spaces.
- Weighting the Martingale: The use of the sequence $\{w_t\}$ is the key technical lever. It allows the proof to "telescope" correctly, effectively canceling out error terms that would otherwise blow up in an unbounded domain.
- Universality: The proposed analysis is "universal," meaning it applies to Lipschitz functions (non-smooth), smooth functions, and linear combinations of both, without needing to change the underlying proof structure.
Key Results
The authors demonstrate that their approach yields rates that match the "best-in-class" expected rates, but with high-probability guarantees:
- Stochastic Mirror Descent: Achieves a convergence rate of $O\left(\sqrt{\frac{D_\psi(x^*, x_1)(G^2 + \sigma^2 \ln(1/\delta))}{T}}\right)$. This matches the standard $1/\sqrt{T}$ rate for non-smooth stochastic optimization.
- Accelerated Stochastic Mirror Descent: For smooth functions, it achieves a rate of $O\left(\frac{\beta D_\psi}{T^2} + \sqrt{\frac{D_\psi (G^2 + \sigma^2 \ln(1/\delta))}{T}}\right)$. This recovers the famous $1/T^2$ acceleration for the deterministic part while maintaining the optimal $1/\sqrt{T}$ rate for the stochastic noise.
- Logarithmic Dependence on Failure: The bounds depend on $\ln(1/\delta)$, which is the ideal scaling. It means that to make the failure probability exponentially small, you only need a logarithmic increase in the number of iterations.
Limitations and Future Work
- Sub-Gaussian Assumption: The analysis assumes that the stochastic noise is "sub-Gaussian" (meaning it has "thin tails"). While this is a standard assumption in the field, it doesn't cover "heavy-tailed" noise often seen in some modern machine learning applications.
- Convexity: The work is strictly limited to convex optimization. Extending these high-probability, diameter-independent bounds to non-convex landscapes (like those found in deep learning) remains a major open challenge.
- Parameter Tuning: The specific choice of weights $\{w_t\}$ used in the proof suggests specific step-size regimes. While these match standard practice, the practical impact of these specific weight-derived step sizes on real-world performance (versus standard SGD) isn't explored here.
Summary updated