×
Gasnikov, A. V.; Nesterov, Yu. E.

Universal method for stochastic composite optimization problems. (English. Russian original) Zbl 1457.90099

Comput. Math. Math. Phys. 58, No. 1, 48-64 (2018); translation from Zh. Vychisl. Mat. Mat. Fiz. 58, No. 1, 52-69 (2018).
Summary: A fast gradient method requiring only one projection is proposed for smooth convex optimization problems. The method has a visual geometric interpretation, so it is called the method of similar triangles (MST). Composite, adaptive, and universal versions of MST are suggested. Based on MST, a universal method is proposed for the first time for strongly convex problems (this method is continuous with respect to the strong convexity parameter of the smooth part of the functional). It is shown how the universal version of MST can be applied to stochastic optimization problems.

Cited in 27 Documents

MSC:

90C15 Stochastic programming
90C25 Convex programming

Keywords:

fast gradient method; composite optimization; universal method; strongly convex case; stochastic optimization; method of similar triangles

Software:

NESUN
Cite Review PDF
Full Text: DOI

References:

[1] Yu. Nesterov, “Smooth minimization of nonsmooth function,” Math. Prog. Ser. A 103 (1), 127-152 (2005). · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5
[2] Yu. Nesterov, “Gradient methods for minimizing composite functions,” Math. Prog. 140 (1), 125-161 (2013). · Zbl 1287.90067 · doi:10.1007/s10107-012-0629-5
[3] O. Devolder, PhD Thesis (CORE UCL, 2013)
[4] O. Devolder, F. Glineur, and Yu. Nesterov, “First order methods of smooth convex optimization with inexact oracle,” Math. Prog. Ser. A 146 (1-2), 37-75 (2014). · Zbl 1317.90196 · doi:10.1007/s10107-013-0677-5
[5] Devolder, O.; Glineur, F.; Nesterov, Yu., Intermediate gradient methods for smooth convex problems with inexact oracle (2013)
[6] Yu. Nesterov, “Universal gradient methods for convex optimization problems,” Math. Prog. 152 (1-2), 381-404 (2015). · Zbl 1327.90216 · doi:10.1007/s10107-014-0790-0
[7] Devolder, O.; Glineur, F.; Nesterov, Yu., First order methods with inexact oracle: The smooth strongly convex case (2013)
[8] A. V. Gasnikov and P. E. Dvurechensky, “Stochastic intermediate gradient method for convex optimization problems,” Dokl. Math. 93 (2), 148-151 (2016). arXiv:1411.2876. · Zbl 1342.90131 · doi:10.1134/S1064562416020071
[9] A. V. Gasnikov, P. E. Dvurechensky, and Yu. E. Nesterov, “Stochastic gradient methods with an inexact oracle,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (1), 41-91 (2016). arXiv:1411.4218. · Zbl 1351.90150
[10] A. V. Gasnikov, D. I. Kamzolov, and M. A. Mendel’, “Basic constructions over convex optimization algorithms and applications to the derivation of new estimates for strongly convex problems,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (3), 25-42 (2016). arXiv:1603.07701.
[11] A. Nemirovski, Lectures on Modern Convex Optimization Analysis, Algorithms, and Engineering Applications (SIAM, Philadelphia, 2013). · Zbl 0986.90032
[12] A. S. Nemirovski and D. B. Yudin, Complexity of Problems and Efficiency of Optimization Methods (Nauka, Moscow, 1979) [in Russian]. · Zbl 0501.90061
[13] Yu. Nesterov, “Primal-dual subgradient methods for convex problems,” Math. Prog. Ser. B 120 (1), 261-283 (2009). · Zbl 1191.90038 · doi:10.1007/s10107-007-0149-x
[14] A. S. Anikin, A. V. Gasnikov, P. E. Dvurechensky, A. I. Tyurin, and A. V. Chernov, “Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints,” Comput. Math. Math. Phys. 57 (8), 1262-1276 (2017). · Zbl 1380.49046 · doi:10.1134/S0965542517080048
[15] A. Juditsky and Yu. Nesterov, “Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization,” Stoch. Syst. 4 (1), 44-80 (2014). · Zbl 1297.90097 · doi:10.1287/10-SSY010
[16] A. V. Gasnikov, E. V. Gasnikova, Yu. E. Nesterov, and A. V. Chernov, “Efficient numerical methods for entropy-linear programming problems,” Comput. Math. Math. Phys. 56 (4), 514-524 (2016). arXiv:1410.7719. · Zbl 1354.65121 · doi:10.1134/S0965542516040084
[17] A. S. Anikin, A. V. Gasnikov, and A. Yu. Gornov, “Efficient nonaccelerated methods for solving sparse quadratic optimization problems,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (2), 44-59 (2016). arXiv:1602.01124.
[18] Yu. E. Nesterov, Introduction to Convex Optimization (MTsNMO, Moscow, 2010) [in Russian].
[19] B. O’Donoghue and E. Candes, “Adaptive restart for accelerated gradient schemes,” Foundations Comput. Math. 15, 715-732 (2015). · Zbl 1320.90061 · doi:10.1007/s10208-013-9150-3
[20] C. Guzman and A. Nemirovski, “On lower complexity bounds for large-scale smooth convex optimization,” J. Complexity 31, 1-14 (2015). arXiv:1307.5001. · Zbl 1304.65155 · doi:10.1016/j.jco.2014.08.003
[21] J. Nocedal and S. Wright, Numerical Optimization (Springer, Berlin, 2006). · Zbl 1104.65059
[22] Tyurin, A., Mirror version of similar triangles method for constrained optimization problems (2017)
[23] A. V. Gasnikov, P. E. Dvurechensky, D. I. Kamzolov, Yu. E. Nesterov, V. G. Spokoinyi, P. I. Stetsyuk, A. L. Suvorikova, and A. V. Chernov, “Search for equilibria in multistage traffic flow models,” Tr. Mosk. Fiz.- Tekh. Inst. 7 (4), 143-155 (2015).
[24] A. V. Gasnikov, P. E. Dvurechensky, V. G. Spokoinyi, P. I. Stetsyuk, and A. L. Suvorikova, “Superposition of the balancing and universal gradient methods for finding an entropy-smoothed Wasserstein barycenter and equilibria in multistage traffic flow models,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (3), 5-24 (2016). arXiv:1506.00292.
[25] Guiges, V.; Juditsky, A.; Nemirovski, A., Nonasymptotic confidence bounds for the optimal value of a stochastic program (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.