Stochastic Composite Mirror Descent: Optimal Bounds with High Probabilities

Although much theoretical analysis has been performed to understand the practical behavior of SGD and SCMD, the existing theoretical results are still not quite satisfactory. Firstly, most of the existing theoretical results are stated in expectation which inevitably ignore some information on high-order moments of the random variable we are interested in.