Abstract
Greedy algorithms which use only function evaluations are applied to convex optimization in a general Banach space \(X\). Along with algorithms that use exact evaluations, algorithms with approximate evaluations are treated. A priori upper bounds for the convergence rate of the proposed algorithms are given. These bounds depend on the smoothness of the objective function and the sparsity or compressibility (with respect to a given dictionary) of a point in \(X\) where the minimum is attained.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.M. Borwein and A.S. Lewis, Convex Analysis and Nonlinear Optimization. Theory and Examples, Canadian Mathematical Society, Springer, 2006.
V. Chandrasekaran, B. Recht, P.A. Parrilo, and A.S. Willsky, The convex geometry of linear inverse problems, Proceedings of the 48th Annual Allerton Conference on Communication, Control and Computing, 2010, 699–703.
K.L. Clarkson, Coresets, Sparse Greedy Approximation, and the Frank–Wolfe Algorithm, ACM Transactions on Algorithms, 6 (2010), Article No. 63.
M. Dudik, Z. Harchaoui, and J. Malick, Lifted coordinate descent for learning with trace-norm regularization, In AISTATS, 2012.
M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), 95–110.
M. Jaggi, Sparse Convex Optimization Methods for Ma- chine Learning, PhD thesis, ETH Zürich, 2011.
M. Jaggi, Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization, Proceedings of the \(30^{th}\) International Conference on Machine Learning, Atlanta, Georgia, USA, 2013.
M. Jaggi and M. Sulovský, A Simple Algorithm for Nuclear Norm Regularized Problems. ICML, 2010.
V.G. Karmanov, Mathematical Programming, Mir Publishers, Moscow, 1989.
A. Nemirovski, Optimization II: Numerical methods for nonlinear continuous optimization, Lecture Notes, Israel Institute of Technology, 1999.
Yu. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, Boston, 2004.
H. Nguyen and G. Petrova, Greedy strategies for convex optimization, arXiv:1401.1754v1 [math.NA] 8 Jan 2014.
S. Shalev-Shwartz, N. Srebro, and T. Zhang, Trading accuracy for sparsity in optimization problems with sparsity constrains, SIAM Journal on Optimization, 20(6) (2010), 2807–2832.
V.N. Temlyakov, Greedy Algorithms and \(m\)-term Approximation With Regard to Redundant Dictionaries, J. Approx. Theory 98 (1999), 117–145.
V.N. Temlyakov, Greedy-Type Approximation in Banach Spaces and Applications, Constr. Approx., 21 (2005), 257–292.
V.N. Temlyakov, Greedy approximation, Cambridge University Press, 2011.
V.N. Temlyakov, Greedy approximation in convex optimization, IMI Preprint, 2012:03, 1–25; arXiv:1206.0392v1, 2 Jun 2012 (to appear in Constructive Approximation).
V.N. Temlyakov, Greedy expansions in convex optimization, Proceedings of the Steklov Institute of Mathematics, 284 (2014), 244–262 ( arXiv:1206.0393v1, 2 Jun 2012).
A. Tewari, P. Ravikumar, and I.S. Dhillon, Greedy Algorithms for Structurally Constrained High Dimensional Problems, prerint, (2012), 1–10.
T. Zhang, Sequential greedy approximation for certain convex optimization problems, IEEE Transactions on Information Theory, 49(3) (2003), 682–691.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Michael Overton.
This research was supported by the Office of Naval Research Contracts ONR-N00014-08-1-1113, ONR N00014-09-1-0107; the NSF Grants DMS 0915231 and DMS-1160841. This research was initiated when the second author was a visiting researcher at TAMU.
Rights and permissions
About this article
Cite this article
DeVore, R.A., Temlyakov, V.N. Convex Optimization on Banach Spaces. Found Comput Math 16, 369–394 (2016). https://doi.org/10.1007/s10208-015-9248-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-015-9248-x