OSGA: a fast subgradient algorithm with optimal complexity. (English) Zbl 1346.90671

Summary: This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex, finite-dimensional domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst case number of iterations needed to achieve a given accuracy is independent of the dimension and – apart from a constant factor – best possible under a variety of smoothness assumptions on the objective function.


90C25 Convex programming
90C60 Abstract computational complexity for mathematical programming problems
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity


Full Text: DOI arXiv


[1] Ahookhosh, M.: Optimal subgradient algorithms with application to large-scale linear inverse problems, Submitted. http://arxiv.org/abs/1402.7291 (2014) · Zbl 1231.90313
[2] Ahookhosh, M., Neumaier, A.: High-dimensional convex optimization via optimal affine subgradient algorithms. In: ROKS workshop, 83-84 (2013)
[3] Ahookhosh, M., Neumaier, A.: An optimal subgradient algorithm with subspace search for costly convex optimization problems. Submitted. http://www.optimization-online.org/DB_FILE/2015/04/4852 (2015) · Zbl 1412.90105
[4] Ahookhosh, M., Neumaier, A.: Solving nonsmooth convex optimization with complexity \[O(\varepsilon^{-1/2})O\](ε-1/2). Submitted. http://www.optimizationonline.org/DB_HTML/2015/05/4900.html (2015) · Zbl 1391.90466
[5] Ahookhosh, M., Neumaier, A.: An optimal subgradient algorithms for large-scale bound-constrained convex optimization. Submitted. http://arxiv.org/abs/1501.01497 (2015) · Zbl 1380.90215
[6] Ahookhosh, M., Neumaier, A.: An optimal subgradient algorithms for large-scale convex optimization in simple domains. Submitted. http://arxiv.org/abs/1501.01451 (2015) · Zbl 1411.90261
[7] Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16, 697-725 (2006) · Zbl 1113.90118
[8] Axelsson, O., Lindskog, G.: On the rate of convergence of the conjugate gradient method. Numer. Math. 48, 499-523 (1986) · Zbl 0564.65017
[9] Aybat, N.S., Iyengar, G.: A first-order augmented Lagrangian method for compressed sensing. SIAM J. Optim. 22(2), 429-459 (2012) · Zbl 1251.90303
[10] Beck, A., Ben-Tal, A., Guttmann-Beck, N., Tetruashvili, L.: The CoMirror algorithm for solving nonsmooth constrained convex problems. Oper. Res. Lett. 38, 493-498 (2010) · Zbl 1202.90209
[11] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183-202 (2009) · Zbl 1175.94009
[12] Becker, S.R., Candès, E.J., Grant, M.C.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3, 165-218 (2011) · Zbl 1257.90042
[13] Chen, J., Burer, S.: A first-order smoothing technique for a class of large-scale linear programs. SIAM J. Optim. 24, 598-620 (2014) · Zbl 1301.65042
[14] Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146, 37-75 (2014) · Zbl 1317.90196
[15] Fountoulakis, K., Gondzio, J., Zhlobich, P.: Matrix-free interior point method for compressed sensing problems. Math. Program. Comput. 6, 1-31 (2014) · Zbl 1304.90137
[16] Gonzaga, C.C., Karas, E.W.: Fine tuning Nesterov’s steepest descent algorithm for differentiable convex programming. Math. Program. 138, 141-166 (2013) · Zbl 1297.90118
[17] Gonzaga, C.C., Karas, E.W., Rossetto, D.R.: An optimal algorithm for constrained differentiable convex optimization. SIAM J. Optim. 23, 1939-1955 (2013) · Zbl 1288.65087
[18] Gu, M., Lim, L.-H., Wu, C.J.: PARNES: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals. Numer. Algorithm. 64, 321-347 (2013) · Zbl 1284.65055
[19] Juditsky, A., Nesterov, Y.: Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stoch. Syst. 4(1), 44-80 (2014) · Zbl 1297.90097
[20] Lan, G.: Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization. Mathematical Programming (2013). doi:10.1007/s10107-013-0737-x · Zbl 1321.90104
[21] Lan, G., Lu, Z., Monteiro, R.D.C.: Primal-dual first-order methods with \[O(1/\varepsilon )O\](1/ε) iteration-complexity for cone programming. Math. Program. 126, 1-29 (2011) · Zbl 1208.90113
[22] Meng, X., Chen, H.: Accelerating Nesterov’s method for strongly convex functions with Lipschitz gradient, Arxiv preprint arXiv:1109.6058 (2011) · Zbl 1287.90067
[23] Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)
[24] Nesterov, Y.: A method of solving a convex programming problem with convergence rate \[O(1, k^2)O\](1,k2) (in Russian), Doklady AN SSSR 269 (1983), 543-547. Engl. translation: Soviet Math. Dokl. 27(1983), 372-376 · Zbl 0535.90071
[25] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, Dordrecht (2004) · Zbl 1086.90045
[26] Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127-152 (2005) · Zbl 1079.90102
[27] Nesterov, Y.: Rounding of convex sets and efficient gradient methods for linear programming problems. Optim. Method. Softw. 23, 109-128 (2008) · Zbl 1192.90119
[28] Nesterov, Y.: Unconstrained convex minimization in relative scale. Math. Oper. Res. 34, 180-193 (2009) · Zbl 1214.65035
[29] Nesterov, Y.: Primal-dual subgradient methods for convex problems. Math. Program. 120, 221-259 (2009) · Zbl 1191.90038
[30] Nesterov, Y.: Gradient methods for minimizing composite objective function. Math. Program. 140, 125-161 (2013) · Zbl 1287.90067
[31] Nesterov, Y.: Universal gradient methods for convex optimization problems. Math. Programming (2014). doi:10.1007/s10107-014-0790-0 · Zbl 1327.90216
[32] Richtarik, P.: Improved algorithms for convex minimization in relative scale. SIAM J. Optim. 21, 1141-1167 (2011) · Zbl 1231.90313
[33] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization, Technical report, Math. Dept., Univ. of Washington. http://pages.cs.wisc.edu/ brecht/cs726docs/Tseng.APG (2008)
[34] Yu, J., Vishvanathan, S.V.N., Günter, S., Schraudolph, N.N.: A Quasi-Newton approach to nonsmooth convex optimization problems in machine learning. J. Mach. Learn. Res. 11, 1145-1200 (2010) · Zbl 1242.90296
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.