High Probability Convergence for Accelerated Stochastic Mirror Descent

Stochastic convex optimization is a well-studied area with numerous applications in algorithms, machine learning, and beyond. Various algorithms have been shown to converge for many classes of functions including Lipschitz functions, smooth functions, and their linear combinations. However, one curious gap remains in the understanding of their convergence with high probability compared with convergence in expectation. Classical results show that in expectation, the function value gap of the final solution is proportional to the distance between the original solution and the optimal solution. On the other hand, classical results for convergence with high probability could only show that the function value gap of the final solution is proportional to the diameter of the domain, which could be much larger or even unbounded.