Stochastic composite mirror descent: Optimal bounds with high probabilities
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
Research and Development[2017YFB1003102];National Natural Science Foundation of China;National Natural Science Foundation of China;Shenzhen Graduate School, Peking University[KQTD2016112514355531];Innovation and Technology Commission[ZDSYS201703031748284];
|Document Type||Conference paper|
|Department||Department of Computer Science and Engineering|
Shenzhen Key Laboratory of Computational Intelligence,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China
|First Author Affilication||Department of Computer Science and Engineering|
|Corresponding Author Affilication||Department of Computer Science and Engineering|
|First Author's First Affilication||Department of Computer Science and Engineering|
Lei，Yunwen,Tang，Ke. Stochastic composite mirror descent: Optimal bounds with high probabilities[C],2018:1519-1529.
|Files in This Item:||There are no files associated with this item.|
|Recommend this item|
|Export to Endnote|
|Export to Excel|
|Export to Csv|
|Similar articles in Google Scholar|
|Similar articles in Baidu Scholar|
|Similar articles in Bing Scholar|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.