{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T16:17:03Z","timestamp":1784132223600,"version":"3.55.0"},"reference-count":89,"publisher":"Emerald","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,11,12]]},"abstract":"<jats:p>This monograph presents the main complexity theorems in convex optimization and their corresponding algorithms. Starting from the fundamental theory of black-box optimization, the material progresses towards recent advances in structural optimization and stochastic optimization. Our presentation of black-box optimization, strongly influenced by Nesterov\u2019s seminal book and Nemirovski\u2019s lecture notes, includes the analysis of cutting plane methods, as well as (accelerated) gradient descent schemes. We also pay special attention to non-Euclidean settings (relevant algorithms include Frank-Wolfe, mirror descent, and dual averaging) and discuss their relevance in machine learning. We provide a gentle introduction to structural optimization with FISTA (to optimize a sum of a smooth and a simple non-smooth term), saddle-point mirror prox (Nemirovski\u2019s alternative to Nesterov\u2019s smoothing), and a concise description of interior point methods. In stochastic optimization we discuss stochastic gradient descent, minibatches, random coordinate descent, and sublinear algorithms. We also briefly touch upon convex relaxation of combinatorial problems and the use of randomness to round solutions, as well as random walks based methods.<\/jats:p>","DOI":"10.1561\/2200000050","type":"journal-article","created":{"date-parts":[[2015,11,12]],"date-time":"2015-11-12T05:57:51Z","timestamp":1447307871000},"page":"231-357","source":"Crossref","is-referenced-by-count":895,"title":["Convex Optimization: Algorithms and Complexity"],"prefix":"10.1108","volume":"8","author":[{"given":"S\u00e9bastien","family":"Bubeck","sequence":"first","affiliation":[{"name":"Theory Group, Microsoft Research","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"2026033014113402000_ref001","article-title":"A lower bound for the optimization of finite sums","author":"Agarwal","year":"2014","journal-title":"Arxiv preprint arXiv:1410.0723"},{"key":"2026033014113402000_ref002","article-title":"Linear coupling: An ultimate unification of gradient and mirror descent","author":"Allen-Zhu","year":"2014","journal-title":"Arxiv preprint arXiv:1407.1537"},{"issue":"1","key":"2026033014113402000_ref003","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1137\/S1052623497318013","article-title":"Towards a practical volumetric cutting plane method for convex programming","volume":"9","author":"Anstreicher","year":"1998","journal-title":"SIAM Journal on Optimization"},{"key":"2026033014113402000_ref004","volume-title":"Optimization for Machine Learning","author":"Audibert","year":"2011"},{"key":"2026033014113402000_ref005","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1287\/moor.2013.0598","article-title":"Regret in online combinatorial optimization","volume":"39","author":"Audibert","year":"2014","journal-title":"Mathematics of Operations Research"},{"issue":"2-3","key":"2026033014113402000_ref006","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1561\/2200000039","article-title":"Learning with submodular functions: A convex optimization perspective","volume":"6","author":"Bach","year":"2013","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"2026033014113402000_ref007","article-title":"Non-strongly-convex smooth stochastic approximation with convergence rate o(1\/n)","author":"Bach","year":"2013","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"issue":"1","key":"2026033014113402000_ref008","first-page":"1","article-title":"Optimization with sparsity-inducing penalties","volume":"4","author":"Bach","year":"2012","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"2026033014113402000_ref009","article-title":"Sum of squares upper bounds, lower bounds, and open questions. Lecture Notes","author":"Barak","year":"2014"},{"issue":"3","key":"2026033014113402000_ref010","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","article-title":"Mirror Descent and nonlinear projected subgradient methods for convex optimization","volume":"31","author":"Beck","year":"2003","journal-title":"Operations Research Letters"},{"issue":"1","key":"2026033014113402000_ref011","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1137\/080716542","article-title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems","volume":"2","author":"Beck","year":"2009","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"2026033014113402000_ref012","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718829","article-title":"Society for Industrial and Applied Mathematics (SIAM)","author":"Ben-Tal","year":"2001","journal-title":"Lectures on modern convex optimization: analysis, algorithms, and engineering applications"},{"key":"2026033014113402000_ref013","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1145\/1008731.1008733","article-title":"Solving convex programs by random walks","volume":"51","author":"Bertsimas","year":"2004","journal-title":"Journal of the ACM"},{"key":"2026033014113402000_ref014","author":"Boyd","year":"2004"},{"issue":"1","key":"2026033014113402000_ref015","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000016","article-title":"Distributed optimization and statistical learning via the alternating direction method of multipliers","volume":"3","author":"Boyd","year":"2011","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"2026033014113402000_ref016","article-title":"Introduction to online optimization","author":"Bubeck","year":"2011"},{"issue":"1","key":"2026033014113402000_ref017","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000024","article-title":"Regret analysis of stochastic and nonstochastic multi-armed bandit problems","volume":"5","author":"Bubeck","year":"2012","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"2026033014113402000_ref018","article-title":"The entropic barrier: a simple and optimal universal self-concordant barrier","author":"Bubeck","year":"2014","journal-title":"Arxiv preprint arXiv:1412.1587"},{"key":"2026033014113402000_ref019","article-title":"Sampling from a log-concave distribution with projected langevin monte carlo","author":"Bubeck","year":"2015","journal-title":"Arxiv preprint arXiv:1507.02564"},{"key":"2026033014113402000_ref020","article-title":"A geometric alternative to nesterov\u2019s accelerated gradient descent","author":"Bubeck","year":"2015","journal-title":"Arxiv preprint arXiv:1506.08187"},{"issue":"6","key":"2026033014113402000_ref021","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","article-title":"Exact matrix completion via convex optimization","volume":"9","author":"Cand\u00e8s","year":"2009","journal-title":"Foundations of Computational mathematics"},{"issue":"1847","key":"2026033014113402000_ref022","first-page":"536","article-title":"M\u00e9thode g\u00e9n\u00e9rale pour la r\u00e9solution des systemes d\u2019\u00e9quations simultan\u00e9es","volume":"25","author":"Cauchy","year":"1847","journal-title":"Comp. Rend. Sci. Paris"},{"key":"2026033014113402000_ref023","author":"Cesa-Bianchi","year":"2006"},{"issue":"1","key":"2026033014113402000_ref024","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","article-title":"A first-order primal-dual algorithm for convex problems with applications to imaging","volume":"40","author":"Chambolle","year":"2011","journal-title":"Journal of Mathematical Imaging and Vision"},{"key":"2026033014113402000_ref025","doi-asserted-by":"crossref","DOI":"10.1145\/2371656.2371658","article-title":"Sublinear optimization for machine learning","author":"Clarkson","year":"2012","journal-title":"Journal of the ACM"},{"key":"2026033014113402000_ref026","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718768","article-title":"Introduction to Derivative-Free Optimization","author":"Conn","year":"2009"},{"issue":"4","key":"2026033014113402000_ref027","article-title":"IEEE information theory society newsletter","volume":"42","author":"Cover","year":"1992"},{"issue":"3","key":"2026033014113402000_ref028","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1137\/060676386","article-title":"Smooth optimization with approximate gradient","volume":"19","author":"d\u2019Aspremont","year":"2008","journal-title":"SIAM Journal on Optimization"},{"key":"2026033014113402000_ref029","article-title":"Saga: A fast incremental gradient method with support for non-strongly convex composite objectives","author":"Defazio","year":"2014","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"key":"2026033014113402000_ref030","first-page":"165","article-title":"Optimal distributed online prediction using mini-batches","volume":"13","author":"Dekel","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014113402000_ref031","article-title":"Composite objective mirror descent","author":"Duchi","year":"2010","journal-title":"Proceedings of the 23rd Annual Conference on Learning Theory (COLT)"},{"issue":"2","key":"2026033014113402000_ref032","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1016\/0022-247X(78)90137-3","article-title":"Conditional gradient algorithms with open loop step size rules","volume":"62","author":"Dunn","year":"1978","journal-title":"Journal of Mathematical Analysis and Applications"},{"issue":"1-2","key":"2026033014113402000_ref033","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/nav.3800030109","article-title":"An algorithm for quadratic programming","volume":"3","author":"Frank","year":"1956","journal-title":"Naval research logistics quarterly"},{"issue":"4","key":"2026033014113402000_ref034","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1137\/060675320","article-title":"Exact regularization of convex programs","volume":"18","author":"Friedlander","year":"2007","journal-title":"SIAM Journal on Optimization"},{"issue":"6","key":"2026033014113402000_ref035","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"Journal of the ACM"},{"key":"2026033014113402000_ref036","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0167-6377(95)00032-0","article-title":"A sublinear-time randomized approximation algorithm for matrix games","volume":"18","author":"Grigoriadis","year":"1995","journal-title":"Operations Research Letters"},{"issue":"4","key":"2026033014113402000_ref037","doi-asserted-by":"crossref","first-page":"1257","DOI":"10.2140\/pjm.1960.10.1257","article-title":"Partitions of mass-distributions and of convex bodies by hyperplanes","volume":"10","author":"Gr\u00fcnbaum","year":"1960","journal-title":"Pacific J. Math"},{"key":"2026033014113402000_ref038","author":"Hastie","year":"2001"},{"key":"2026033014113402000_ref039","first-page":"287","author":"Hazan","year":"2011"},{"key":"2026033014113402000_ref040","first-page":"427","article-title":"Revisiting frank-wolfe: Projection-free sparse convex optimization","author":"Jaggi","year":"2013","journal-title":"Proceedings of the 30th International Conference on Machine Learning (ICML)"},{"key":"2026033014113402000_ref041","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/2488608.2488693","article-title":"Low-rank matrix completion using alternating minimization","author":"Jain","year":"2013","journal-title":"Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC \u201913"},{"key":"2026033014113402000_ref042","article-title":"Accelerating stochastic gradient descent using predictive variance reduction","author":"Johnson","year":"2013","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"key":"2026033014113402000_ref043","first-page":"608","article-title":"A simple lemma on greedy approximation in hilbert space and convergence rates for projection pursuit regression and neural network training","author":"Jones","year":"1992","journal-title":"Annals of Statistics"},{"key":"2026033014113402000_ref044","first-page":"121","author":"Juditsky","year":"2011"},{"key":"2026033014113402000_ref045","first-page":"149","author":"Juditsky","year":"2011"},{"key":"2026033014113402000_ref046","first-page":"373","article-title":"A new polynomial-time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984"},{"key":"2026033014113402000_ref047","article-title":"A simpler approach to obtaining an o (1\/t) convergence rate for the projected stochastic subgradient method","author":"Lacoste-Julien","year":"2012","journal-title":"arXiv:1212.2002"},{"key":"2026033014113402000_ref048","article-title":"A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets","author":"Le Roux","year":"2012","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"key":"2026033014113402000_ref049","article-title":"Path finding i :solving linear programs with \u00c3\u0162(sqrt(rank)) linear system solves","author":"Lee","year":"2013","journal-title":"Arxiv preprint arXiv:1312.6677"},{"key":"2026033014113402000_ref050","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS.2015.68","article-title":"A faster cutting plane method and its implications for combinatorial and convex optimization","author":"Lee","year":"2015"},{"key":"2026033014113402000_ref051","first-page":"1244","article-title":"On an algorithm for the minimization of convex functions","volume":"160","author":"Levin","year":"1965","journal-title":"Soviet Mathematics Doklady"},{"key":"2026033014113402000_ref052","first-page":"443","article-title":"Hit-and-run mixes fast","volume":"86","author":"Lov\u00e1sz","year":"1998","journal-title":"Math. Prog."},{"issue":"2","key":"2026033014113402000_ref053","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/s11749-010-0199-x","article-title":"Comment on: \u2113-penalization for mixture regression models","volume":"19","author":"Lugosi","year":"2010","journal-title":"Test"},{"issue":"4","key":"2026033014113402000_ref054","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0167-6377(89)90064-3","article-title":"A linear-time median-finding algorithm for projecting a vector on the simplex of rn","volume":"8","author":"Maculan","year":"1989","journal-title":"Operations research letters"},{"key":"2026033014113402000_ref055","article-title":"Orth-method for smooth convex optimization","volume":"2","author":"Nemirovski","year":"1982","journal-title":"Izvestia AN SSSR, Ser. Tekhnicheskaya Kibernetika"},{"key":"2026033014113402000_ref056","article-title":"Information-based complexity of convex programming","author":"Nemirovski","year":"1995","journal-title":"Lecture Notes"},{"issue":"1","key":"2026033014113402000_ref057","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1137\/S1052623403425629","article-title":"Prox-method with rate of convergence o (1\/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems","volume":"15","author":"Nemirovski","year":"2004","journal-title":"SIAM Journal on Optimization"},{"key":"2026033014113402000_ref058","article-title":"Interior point polynomial time methods in convex programming","author":"Nemirovski","year":"2004","journal-title":"Lecture Notes"},{"key":"2026033014113402000_ref059","article-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovski","year":"1983"},{"issue":"2","key":"2026033014113402000_ref060","first-page":"372","article-title":"A method of solving a convex programming problem with convergence rate o(1\/k2)","volume":"27","author":"Nesterov","year":"1983","journal-title":"Soviet Mathematics Doklady"},{"key":"2026033014113402000_ref061","article-title":"Quality of semidefinite relaxation for nonconvex quadratic optimization. CORE Discussion Papers 1997019, Universit\u00e9 catholique de Louvain, Center for Operations Research and Econometrics (CORE)","author":"Nesterov","year":"1997"},{"key":"2026033014113402000_ref062","author":"Nesterov","year":"2004"},{"issue":"1","key":"2026033014113402000_ref063","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","article-title":"Smooth minimization of non-smooth functions","volume":"103","author":"Nesterov","year":"2004","journal-title":"Mathematical programming"},{"key":"2026033014113402000_ref064","article-title":"Gradient methods for minimizing composite objective function. Core discussion papers, Universit\u00e9 catholique de Louvain, Center for Operations Research and Econometrics (CORE)","author":"Nesterov","year":"2007"},{"key":"2026033014113402000_ref065","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/100802001","article-title":"Efficiency of coordinate descent methods on huge-scale optimization problems","volume":"22","author":"Nesterov","year":"2012","journal-title":"SIAM Journal on Optimization"},{"key":"2026033014113402000_ref066","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","author":"Nesterov","year":"1994","journal-title":"Interior-point polynomial algorithms in convex programming"},{"issue":"3","key":"2026033014113402000_ref067","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1145\/321281.321291","article-title":"Location of the maximum on unimodal surfaces","volume":"12","author":"Newman","year":"1965","journal-title":"Journal of the ACM"},{"key":"2026033014113402000_ref068","article-title":"Numerical Optimization","author":"Nocedal","year":"2006"},{"issue":"3","key":"2026033014113402000_ref069","first-page":"123","article-title":"Proximal algorithms","volume":"1","author":"Parikh","year":"2013","journal-title":"Foundations and Trends\u00ae in Optimization"},{"key":"2026033014113402000_ref070","article-title":"Lecture notes on online learning","author":"Rakhlin","year":"2009"},{"key":"2026033014113402000_ref071","article-title":"A mathematical view of interior-point methods in convex optimization","volume":"3","author":"Renegar","year":"2001"},{"key":"2026033014113402000_ref072","article-title":"Parallel coordinate descent methods for big data optimization","author":"Richt\u00e1rik","year":"2012","journal-title":"Arxiv preprint arXiv:1212.0873"},{"key":"2026033014113402000_ref073","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1214\/aoms\/1177729586","article-title":"A stochastic approximation method","volume":"22","author":"Robbins","year":"1951","journal-title":"Annals of Mathematical Statistics"},{"key":"2026033014113402000_ref074","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","author":"Rockafellar","year":"1970","journal-title":"Convex Analysis"},{"key":"2026033014113402000_ref075","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1006\/jfan.1998.3384","article-title":"Random vectors in the isotropic position","volume":"164","author":"Rudelson","year":"1999","journal-title":"Journal of Functional Analysis"},{"key":"2026033014113402000_ref076","first-page":"1458","article-title":"Convergence rates of inexact proximalgradient methods for convex optimization","author":"Schmidt","year":"2011","journal-title":"Advances in neural information processing systems"},{"key":"2026033014113402000_ref077","author":"Sch\u00f6lkopf","year":"2002"},{"key":"2026033014113402000_ref078","author":"Shalev-Shwartz","year":"2014"},{"key":"2026033014113402000_ref079","first-page":"567","article-title":"Stochastic dual coordinate ascent methods for regularized loss minimization","volume":"14","author":"Shalev-Shwartz","year":"2013","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014113402000_ref080","article-title":"Accelerated mini-batch stochastic dual coordinate ascent","author":"Shalev-Shwartz","year":"2013","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"key":"2026033014113402000_ref081","article-title":"A differential equation for modeling nesterov\u2019s accelerated gradient method: Theory and insights","author":"Su","year":"2014","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"issue":"1","key":"2026033014113402000_ref082","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","article-title":"Regression shrinkage and selection via the lasso","volume":"58","author":"Tibshirani","year":"1996","journal-title":"Journal of the Royal Statistical Society. Series B (Methodological)"},{"key":"2026033014113402000_ref083","article-title":"On accelerated proximal gradient methods for convex-concave optimization","author":"Tseng","year":"2008"},{"key":"2026033014113402000_ref084","first-page":"303","article-title":"Optimal rates of aggregation","author":"Tsybakov","year":"2003","journal-title":"Conference on Learning Theory (COLT)"},{"key":"2026033014113402000_ref085","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1109\/SFCS.1989.63500","article-title":"A new algorithm for minimizing convex functions over convex sets","author":"Vaidya","year":"1989","journal-title":"Foundations of Computer Science, 1989., 30th Annual Symposium on"},{"issue":"3","key":"2026033014113402000_ref086","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF02592216","article-title":"A new algorithm for minimizing convex functions over convex sets","volume":"73","author":"Vaidya","year":"1996","journal-title":"Mathematical programming"},{"issue":"7","key":"2026033014113402000_ref087","doi-asserted-by":"crossref","first-page":"2479","DOI":"10.1109\/TSP.2009.2016892","article-title":"Sparse reconstruction by separable approximation","volume":"57","author":"Wright","year":"2009","journal-title":"IEEE Transactions on Signal Processing"},{"key":"2026033014113402000_ref088","first-page":"2543","article-title":"Dual averaging methods for regularized stochastic learning and online optimization","volume":"11","author":"Xiao","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014113402000_ref089","article-title":"Stochastic primal-dual coordinate method for regularized empirical risk minimization","author":"Zhang","year":"2014","journal-title":"Arxiv preprint arXiv:1409.3257"}],"container-title":["Foundations and Trends\u00ae in Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftmal\/article-pdf\/8\/3-4\/231\/11158692\/2200000050en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftmal\/article-pdf\/8\/3-4\/231\/11158692\/2200000050en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:10:58Z","timestamp":1777486258000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftmal\/article\/8\/3-4\/231\/1332647\/Convex-Optimization-Algorithms-and-Complexity"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,12]]},"references-count":89,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2015,11,12]]}},"URL":"https:\/\/doi.org\/10.1561\/2200000050","relation":{},"ISSN":["1935-8237","1935-8245"],"issn-type":[{"value":"1935-8237","type":"print"},{"value":"1935-8245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,12]]}}}