High Probability Convergence for Accelerated Stochastic Mirror Descent
This work provides a more robust convergence guarantee for stochastic optimization algorithms, which is incremental but addresses a specific limitation in existing methods.
The paper tackles the problem of achieving high probability convergence for stochastic convex optimization, presenting a method that yields bounds based on initial distance to the optimum rather than domain diameter, applicable to Lipschitz and smooth functions.
In this work, we describe a generic approach to show convergence with high probability for stochastic convex optimization. In previous works, either the convergence is only in expectation or the bound depends on the diameter of the domain. Instead, we show high probability convergence with bounds depending on the initial distance to the optimal solution as opposed to the domain diameter. The algorithms use step sizes analogous to the standard settings and are universal to Lipschitz functions, smooth functions, and their linear combinations.