Convergence and rate of convergence of some greedy algorithms in convex optimization

V. N. Temlyakov

Informatics and Automation, Function spaces, approximation theory, and related problems of mathematical analysis, Tome 293 (2016), pp. 333-345.

Résumé

The paper gives a systematic study of the approximate versions of three greedy-type algorithms that are widely used in convex optimization. By an approximate version we mean the one where some of evaluations are made with an error. Importance of such versions of greedy-type algorithms in convex optimization and approximation theory was emphasized in previous literature.

Bibliographie

[1] Barron A.R., “Universal approximation bounds for superpositions of a sigmoidal function”, IEEE Trans. Inf. Theory, 39:3 (1993), 930–945 | DOI | MR | Zbl

[2] Chandrasekaran V., Recht B., Parrilo P.A., Willsky A.S., “The convex algebraic geometry of linear inverse problems”, Communication, control, and computing, Proc. 48th Annu. Allerton Conf., IEEE Press, Piscataway, NJ, 2010, 699–703

[3] Clarkson K.L., “Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm”, ACM Trans. Algorithms, 6:4 (2010), 63 | DOI | MR

[4] Demyanov V.F., Rubinov A.M., Approximate methods in optimization problems, Elsevier, New York, 1970 | MR | Zbl

[5] DeVore R.A., Temlyakov V.N., Convex optimization on Banach spaces, IMI Preprint N 01., Univ. South Carol., Columbia, SC, 2014, arXiv: 1401.0334v1 | MR | Zbl

[6] Dudik M., Harchaoui Z., Malick J., “Lifted coordinate descent for learning with trace-norm regularization”, Proc. 15th Int. Conf. on Artificial Intelligence and Statistics (AISTATS 2012), JMLR Workshop Conf. Proc., 22, Microtome Publ., Brookline, MA, 2012, 327–336

[7] Dunn J.C., Harshbarger S., “Conditional gradient algorithms with open loop step size rules”, J. Math. Anal. Appl., 62 (1978), 432–444 | DOI | MR | Zbl

[8] Frank M., Wolfe P., “An algorithm for quadratic programming”, Nav. Res. Logist. Q., 3 (1956), 95–110 | DOI | MR

[9] Jaggi M., Sparse convex optimization methods for machine learning, PhD Thesis, ETH, Zürich, 2011

[10] Jaggi M., “Revisiting Frank–Wolfe: Projection-free sparse convex optimization”, Proc. 30th Int. Conf. on Machine Learning (Atlanta, GA, 2013), JMLR Workshop Conf. Proc., 28, no. 1, Microtome Publ., Brookline, MA, 2013, 427–435

[11] Jaggi M., Sulovský M., “A simple algorithm for nuclear norm regularized problems”, Proc. 27th Int. Conf. on Machine Learning, Haifa, 2010, Madison, WI, 2010, 471–478

[12] Jones L.K., “A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training”, Ann. Stat., 20 (1992), 608–613 | DOI | MR | Zbl

[13] Shalev-Shwartz S., Srebro N., Zhang T., “Trading accuracy for sparsity in optimization problems with sparsity constraints”, SIAM J. Optim., 20:6 (2010), 2807–2832 | DOI | MR | Zbl

[14] Temlyakov V.N., “Greedy algorithms and $m$-term approximation with regard to redundant dictionaries”, J. Approx. Theory, 98 (1999), 117–145 | DOI | MR | Zbl

[15] Temlyakov V.N., “Greedy-type approximation in Banach spaces and applications”, Constr. Approx., 21:2 (2005), 257–292 | DOI | MR | Zbl

[16] Temlyakov V., Greedy approximation, Cambridge Univ. Press, Cambridge, 2011 | MR | Zbl

[17] Temlyakov V.N., Greedy approximation in convex optimization, IMI Preprint N 03, Univ. South Carol., Columbia, SC, 2012, arXiv: 1206.0392v1 | MR

[18] Temlyakov V.N., “Gridi-razlozheniya v vypukloi optimizatsii”, Tr. MIAN, 284 (2014), 252–270 | MR | Zbl

[19] Tewari A., Ravikumar P., Dhillon I.S., “Greedy algorithms for structurally constrained high dimensional problems”, Adv. Neural Inf. Process. Syst., 24 (2011), 882–890

[20] Zhang T., “Sequential greedy approximation for certain convex optimization problems”, IEEE Trans. Inf. Theory, 49:3 (2003), 682–691 | DOI | MR | Zbl