|
This article is cited in 1 scientific paper (total in 1 paper)
NUMERICAL METHODS AND THE BASIS FOR THEIR APPLICATION
Ellipsoid method for convex stochastic optimization in small dimension
E. L. Gladinabc, K. E. Zainullinaa a National Research University Moscow Institute of Physics and Technology,
9, Institutskiy per., Dolgoprudny, Moscow Region, 141701, Russia
b Institute for Information Transmission Problems RAS,
9, B. Karetny lane, Moscow, 127051, Russia
c Skolkovo Institute of Science and Technology,
30/1, Bolshoy Boulevard, Moscow, 121205, Russia
Abstract:
The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a variety of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are usually used to solve such problems. We propose to use the ellipsoid method with mini-batching, which converges linearly and can be more efficient than SGD for a class of problems. This is verified by our experiments, which are publicly available. The algorithm does not require neither smoothness nor strong convexity of the objective to achieve linear convergence. Thus, its complexity does not depend on the conditional number of the problem. We prove that the method arrives at an approximate solution with given probability when using mini-batches of size proportional to the desired accuracy to the power -2. This enables efficient parallel execution of the algorithm, whereas possibilities for batch parallelization of SGD are rather limited. Despite fast convergence, ellipsoid method can result in a greater total number of calls to oracle than SGD, which works decently with small batches. Complexity is quadratic in dimension of the problem, hence the method is suitable for relatively small dimensionalities.
Keywords:
stochastic optimization, convex optimization, ellipsoid method, mini-batching.
Received: 09.11.2020 Revised: 15.11.2021 Accepted: 16.11.2021
Citation:
E. L. Gladin, K. E. Zainullina, “Ellipsoid method for convex stochastic optimization in small dimension”, Computer Research and Modeling, 13:6 (2021), 1137–1147
Linking options:
https://www.mathnet.ru/eng/crm940 https://www.mathnet.ru/eng/crm/v13/i6/p1137
|
Statistics & downloads: |
Abstract page: | 91 | Full-text PDF : | 32 | References: | 14 |
|