Geodesic
Vaidya's Method for Convex Stochastic Optimization Problems in Small Dimension
Matematičeskie zametki, Tome 112 (2022) no. 2, pp. 179-187.

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

The paper deals with a general problem of convex stochastic optimization in a space of small dimension (for example, 100 variables). It is known that for deterministic problems of convex optimization in small dimensions, the methods of centers of gravity type (for example, Vaidya's method) provide the best convergence. For stochastic optimization problems, the question of the possibility of applying Vaidya's method can be reduced to the question of how it accumulates inaccuracies in the subgradient. A recent result of the authors stating that there is no accumulation of inaccuracies at the iterations of Vaidya's method allows the authors to propose its analog for solving stochastic optimization problems. The main technique is to replace the subgradient in Vaidya's method by its batched analogue (the arithmetic mean of stochastic subgradients). In the present paper, this plan is implemented, which results in an efficient method (under conditions of the possibility of parallel calculations with batching) for solving problems of convex stochastic optimization in spaces of small dimensions. The work of the algorithm is illustrated by a numerical experiment.
Keywords: stochastic optimization, convex optimization, mini-batching, cutting plane method. 
@article{MZM_2022_112_2_a2,
     author = {E. L. Gladin and A. V. Gasnikov and E. S. Ermakova},
     title = {Vaidya's {Method} for {Convex} {Stochastic} {Optimization} {Problems} in {Small} {Dimension}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {179--187},
     publisher = {mathdoc},
     volume = {112},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2022_112_2_a2/}
}
TY  - JOUR
AU  - E. L. Gladin
AU  - A. V. Gasnikov
AU  - E. S. Ermakova
TI  - Vaidya's Method for Convex Stochastic Optimization Problems in Small Dimension
JO  - Matematičeskie zametki
PY  - 2022
SP  - 179
EP  - 187
VL  - 112
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2022_112_2_a2/
LA  - ru
ID  - MZM_2022_112_2_a2
ER  - 
%0 Journal Article
%A E. L. Gladin
%A A. V. Gasnikov
%A E. S. Ermakova
%T Vaidya's Method for Convex Stochastic Optimization Problems in Small Dimension
%J Matematičeskie zametki
%D 2022
%P 179-187
%V 112
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2022_112_2_a2/
%G ru
%F MZM_2022_112_2_a2
E. L. Gladin; A. V. Gasnikov; E. S. Ermakova. Vaidya's Method for Convex Stochastic Optimization Problems in Small Dimension. Matematičeskie zametki, Tome 112 (2022) no. 2, pp. 179-187. http://geodesic.mathdoc.fr/item/MZM_2022_112_2_a2/

[1] B. E. Woodworth, J. Wang, A. Smith, B. McMahan, N. Srebro, “Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization”, Advances in Neural Information Processing Systems 31, 2018

[2] S. Bubeck, Q. Jiang, Y. T. Lee, Y. Li, A. Sidford, “Complexity of highly parallel non-smooth convex optimization”, Advances in Neural Information Processing Systems 33, 2019

[3] J. Diakonikolas, C. Guzmán, “Lower bounds for parallel and randomized convex optimization”, J. Mach. Learn. Res., 21 (2020), Art no. 5 | MR

[4] S. Bubeck, “Convex optimization: algorithms and complexity”, Foundations and Trends in Machine Learning, 8:3-4 (2015), 231–357 | DOI | Zbl

[5] A. S. Nemirovskii, D. B. Yudin, Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, M., 1979 | MR

[6] E. L. Gladin, K. E. Zainullina, “Metod ellipsoidov dlya zadach vypukloi stokhasticheskoi optimizatsii maloi razmernosti”, Kompyuternye issledovaniya i modelirovanie, 13:6 (2021), 1137–1147 | DOI

[7] O. Dekel, R. Gilad-Bachrach, O. Shamir, L. Xiao, “Optimal Distributed Online Prediction Using Mini-Batches”, J. Mach. Learn. Res., 13 (2012), 165–202 | MR | Zbl

[8] D. M. Dvinskikh i dr., “Uskorennyi i neuskorenyi stokhasticheskii gradientnyi spusk v modelnoi obschnosti”, Matem. zametki, 108:4 (2020), 515–528 | DOI | MR | Zbl

[9] P. M. Vaidya, “A new algorithm for minimizing convex functions over convex sets”, 30th Annual Symposium on Foundations of Computer Science, 1989, 338–343 | DOI

[10] Y. T. Lee, A. Sidford, “Path finding methods for linear programming: Solving linear programs in $O(\sqrt{\operatorname{rank}}\,)$ iterations and faster algorithms for maximum flow”, 55th Annual IEEE Symposium on Foundations of Computer Science – FOCS 2014, IEEE Computer Soc., Los Alamitos, CA, 2014, 424–433 | DOI | MR

[11] M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 2012 | DOI

[12] E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov, M. Alkousa, “Solving smooth min-min and min-max problems by mixed oracle algorithms”, Mathematical Optimization Theory and Operations Research – Recent Trends, Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021 | MR

[13] J. A. Blackard, D. J. Dean, C.Ẇ. Anderson, Covertype binary dataset, http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/

[14] E. L. Gladin, A. V. Gasnikov, E. S. Ermakova, Iskhodnyi kod eksperimentov, https://github.com/egorgladin/stochastic_vaidya | Zbl

[15] A. Agafonov A. al., An Accelerated Second-Order Method for Distributed Stochastic Optimization, 2021, arXiv: 2103.14392

[16] S. Shalev-Shwartz, O. Shamir, N. Srebro, K. Sridharan, Stochastic Convex Optimization, 2009 | Zbl