Geodesic
Accelerated and Unaccelerated Stochastic Gradient Descent in Model Generality
Matematičeskie zametki, Tome 108 (2020) no. 4, pp. 515-528.

Voir la notice de l'article provenant de la source Math-Net.Ru

A new method for deriving estimates of the rate of convergence of optimal methods for solving problems of smooth (strongly) convex stochastic optimization is described. The method is based on the results of stochastic optimization derived from results on the convergence of optimal methods under the conditions of inexact gradients with small noises of nonrandom nature. In contrast to earlier results, all estimates in the present paper are obtained in model generality.
Keywords: stochastic optimization, accelerated gradient descent, model generality, composite optimization. 
@article{MZM_2020_108_4_a3,
     author = {D. M. Dvinskikh and A. I. Turin and A. V. Gasnikov and S. S. Omelchenko},
     title = {Accelerated and {Unaccelerated} {Stochastic} {Gradient} {Descent} in {Model} {Generality}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {515--528},
     publisher = {mathdoc},
     volume = {108},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2020_108_4_a3/}
}
TY  - JOUR
AU  - D. M. Dvinskikh
AU  - A. I. Turin
AU  - A. V. Gasnikov
AU  - S. S. Omelchenko
TI  - Accelerated and Unaccelerated Stochastic Gradient Descent in Model Generality
JO  - Matematičeskie zametki
PY  - 2020
SP  - 515
EP  - 528
VL  - 108
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2020_108_4_a3/
LA  - ru
ID  - MZM_2020_108_4_a3
ER  - 
%0 Journal Article
%A D. M. Dvinskikh
%A A. I. Turin
%A A. V. Gasnikov
%A S. S. Omelchenko
%T Accelerated and Unaccelerated Stochastic Gradient Descent in Model Generality
%J Matematičeskie zametki
%D 2020
%P 515-528
%V 108
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2020_108_4_a3/
%G ru
%F MZM_2020_108_4_a3
D. M. Dvinskikh; A. I. Turin; A. V. Gasnikov; S. S. Omelchenko. Accelerated and Unaccelerated Stochastic Gradient Descent in Model Generality. Matematičeskie zametki, Tome 108 (2020) no. 4, pp. 515-528. http://geodesic.mathdoc.fr/item/MZM_2020_108_4_a3/

[1] A. V. Gasnikov, Sovremennye chislennye metody optimizatsii. Metod universalnogo gradientnogo spuska, MFTI, M., 2018

[2] O. Devolder, Exactness, Inexactness and Stochasticity in First-Order Methods for Large-Scale Convex Optimization, PhD Thesis, Université Catholique de Louvain, Louvain-la-Neuve, 2013

[3] G. Lan, Lectures on Optimization. Methods for Machine Learning, , 2019 http://pwp.gatech.edu/guanghui-lan/wp-content/uploads/sites/330/2019/08/LectureOPTML.pdf

[4] M. Assran, M. Rabbat, On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings, 2020, arXiv: 2002.12414

[5] A. V. Gasnikov, A. I. Tyurin, “Bystryi gradientnyi spusk dlya zadach vypukloi minimizatsii s orakulom, vydayuschim $(\delta,L)$-model funktsii v zaproshennoi tochke”, Zh. vychisl. matem. i matem. fiz., 59:7 (2019), 1137–1150 | DOI | Zbl

[6] E. Gorbunov, D. Dvinskikh, A. Gasnikov, Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization, 2020, arXiv: 1911.07363

[7] F. S. Stonyakin, D. Dvinskikh, P. Dvurechensky, A. Kroshnin, O. Kuznetsova, A. Agafonov, A. Gasnikov, A. Tyurin, C. A. Uribe, D. Pasechnyuk, S. Artamonov, “Gradient methods for problems with inexact model of the objective”, Mathematical Optimization Theory and Operations Research. MOTOR 2019, Lecture Notes in Comput. Sci., 11548, Springer, Cham, 2019, 97–114 | DOI | Zbl

[8] B. Woodworth, J. Wang, A. Smith, B. McMahan, N. Srebro, Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization, 2018, arXiv: 1805.10222

[9] Yu. Nesterov, Lectures on Convex Optimization, Springer, Cham, 2018 | MR | Zbl

[10] A. Juditski, A. S. Nemirovski, Large Deviations of Vector-Valued Martingales in $2$-Smooth Normed Spaces, 2008, arXiv: 0809.0813

[11] Yu. Nesterov, “Gradient methods for minimizing composite functions”, Math. Program., 140:1, Ser. B (2013), 125–161 | MR | Zbl

[12] F. S. Stonyakin, “Adaptatsiya k velichinam pogreshnostei dlya nekotorykh metodov optimizatsii gradientnogo tipa”, Tr. IMM UrO RAN, 25, no. 4, 2019, 210–225 | DOI

[13] F. S. Stonyakin, E. A. Vorontsova, M. Alkousa, “New version of mirror prox for variational inequalities with adaptation to inexactness”, Optimization and Applications. OPTIMA 2019, Commun. in Comput. and Inform. Sci., 1145, Springer, Cham, 2020, 427–442 | DOI