Stochastic composite mirror descent: Optimal bounds with high probabilities

Lei，Yunwen; Tang，Ke

2018

1049-5258

Advances in Neural Information Processing Systems

2018-December

1519-1529

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 loga-rithmical 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.

First ; Corresponding

English

Research and Development[2017YFB1003102];National Natural Science Foundation of China[61672478];National Natural Science Foundation of China[61806091];Shenzhen Graduate School, Peking University[KQTD2016112514355531];Innovation and Technology Commission[ZDSYS201703031748284];

2-s2.0-85064828146

Scopus

Shenzhen Key Laboratory of Computational Intelligence,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China

Lei，Yunwen,Tang，Ke. Stochastic composite mirror descent: Optimal bounds with high probabilities[C],2018:1519-1529.