Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 1,001

The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.

Convex Optimization: Algorithms and Complexity

Bubeck, Sébastien·2015·Foundations and Trends® in Machine Learning
DOI 10.1561/2200000050
Open this paper in CoChat — free account

Abstract

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’s seminal book and Nemirovski’s 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’s alternative to Nesterov’s 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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1561/2200000050

Cites

7 of 7 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 7 references

Research works printed but not linked: 63

  1. Agarwal, 2014, A lower bound for the optimization of finite sums, Arxiv preprint arXiv:1410.0723 · arXiv
  2. Allen-Zhu, 2014, Linear coupling: An ultimate unification of gradient and mirror descent, Arxiv preprint arXiv:1407.1537 · arXiv
  3. Anstreicher, 1998, Towards a practical volumetric cutting plane method for convex programming, SIAM Journal on Optimization, 9, 190, 10.1137/S1052623497318013 · doi:10.1137/s1052623497318013
  4. Audibert, 2011, Optimization for Machine Learning
  5. Audibert, 2014, Regret in online combinatorial optimization, Mathematics of Operations Research, 39, 31, 10.1287/moor.2013.0598 · DOI
  6. Bach, 2013, Learning with submodular functions: A convex optimization perspective, Foundations and Trends® in Machine Learning, 6, 145, 10.1561/2200000039 · DOI
  7. Bach, 2013, Non-strongly-convex smooth stochastic approximation with convergence rate o(1/n), Advances in Neural Information Processing Systems (NIPS)
  8. Bach, 2012, Optimization with sparsity-inducing penalties, Foundations and Trends® in Machine Learning, 4, 1
  9. Ben-Tal, 2001, Society for Industrial and Applied Mathematics (SIAM), Lectures on modern convex optimization: analysis, algorithms, and engineering applications, 10.1137/1.9780898718829 · DOI · Paper page
  10. Bertsimas, 2004, Solving convex programs by random walks, Journal of the ACM, 51, 540, 10.1145/1008731.1008733 · DOI
  11. Bubeck, 2012, Regret analysis of stochastic and nonstochastic multi-armed bandit problems, Foundations and Trends® in Machine Learning, 5, 1, 10.1561/2200000024 · DOI · Paper page
  12. Bubeck, 2014, The entropic barrier: a simple and optimal universal self-concordant barrier, Arxiv preprint arXiv:1412.1587 · arXiv
  13. Bubeck, 2015, Sampling from a log-concave distribution with projected langevin monte carlo, Arxiv preprint arXiv:1507.02564 · arXiv
  14. Bubeck, 2015, A geometric alternative to nesterov’s accelerated gradient descent, Arxiv preprint arXiv:1506.08187 · arXiv
  15. Candès, 2009, Exact matrix completion via convex optimization, Foundations of Computational mathematics, 9, 717, 10.1007/s10208-009-9045-5 · DOI · Paper page
  16. Cauchy, 1847, Méthode générale pour la résolution des systemes d’équations simultanées, Comp. Rend. Sci. Paris, 25, 536
  17. Chambolle, 2011, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40, 120, 10.1007/s10851-010-0251-1 · DOI · Paper page
  18. Clarkson, 2012, Sublinear optimization for machine learning, Journal of the ACM, 10.1145/2371656.2371658 · DOI
  19. Conn, 2009, Introduction to Derivative-Free Optimization, 10.1137/1.9780898718768 · DOI · Paper page
  20. Cover, 1992, IEEE information theory society newsletter, 42
  21. d’Aspremont, 2008, Smooth optimization with approximate gradient, SIAM Journal on Optimization, 19, 1171, 10.1137/060676386 · DOI
  22. Defazio, 2014, Saga: A fast incremental gradient method with support for non-strongly convex composite objectives, Advances in Neural Information Processing Systems (NIPS)
  23. Dekel, 2012, Optimal distributed online prediction using mini-batches, Journal of Machine Learning Research, 13, 165
  24. Duchi, 2010, Composite objective mirror descent, Proceedings of the 23rd Annual Conference on Learning Theory (COLT)
  25. Dunn, 1978, Conditional gradient algorithms with open loop step size rules, Journal of Mathematical Analysis and Applications, 62, 432, 10.1016/0022-247X(78)90137-3 · DOI
  26. Friedlander, 2007, Exact regularization of convex programs, SIAM Journal on Optimization, 18, 1326, 10.1137/060675320 · DOI
  27. Grigoriadis, 1995, A sublinear-time randomized approximation algorithm for matrix games, Operations Research Letters, 18, 53, 10.1016/0167-6377(95)00032-0 · doi:10.1016/0167-6377(95)00032-0
  28. Grünbaum, 1960, Partitions of mass-distributions and of convex bodies by hyperplanes, Pacific J. Math, 10, 1257, 10.2140/pjm.1960.10.1257 · doi:10.2140/pjm.1960.10.1257
  29. Jaggi, 2013, Revisiting frank-wolfe: Projection-free sparse convex optimization, Proceedings of the 30th International Conference on Machine Learning (ICML), 427
  30. Jain, 2013, Low-rank matrix completion using alternating minimization, Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC ’13, 665, 10.1145/2488608.2488693 · DOI · Paper page
  31. Johnson, 2013, Accelerating stochastic gradient descent using predictive variance reduction, Advances in Neural Information Processing Systems (NIPS)
  32. Jones, 1992, A simple lemma on greedy approximation in hilbert space and convergence rates for projection pursuit regression and neural network training, Annals of Statistics, 608
  33. Lacoste-Julien, 2012, A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method, arXiv:1212.2002 · arXiv
  34. Le Roux, 2012, A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets, Advances in Neural Information Processing Systems (NIPS)
  35. Lee, 2013, Path finding i :solving linear programs with ÃŢ(sqrt(rank)) linear system solves, Arxiv preprint arXiv:1312.6677 · arXiv
  36. Lee, 2015, A faster cutting plane method and its implications for combinatorial and convex optimization, 10.1109/FOCS.2015.68 · DOI
  37. Levin, 1965, On an algorithm for the minimization of convex functions, Soviet Mathematics Doklady, 160, 1244
  38. Lovász, 1998, Hit-and-run mixes fast, Math. Prog., 86, 443
  39. Lugosi, 2010, Comment on: ℓ-penalization for mixture regression models, Test, 19, 259, 10.1007/s11749-010-0199-x · doi:10.1007/s11749-010-0199-x
  40. Maculan, 1989, A linear-time median-finding algorithm for projecting a vector on the simplex of rn, Operations research letters, 8, 219, 10.1016/0167-6377(89)90064-3 · doi:10.1016/0167-6377(89)90064-3
  41. Nemirovski, 1982, Orth-method for smooth convex optimization, Izvestia AN SSSR, Ser. Tekhnicheskaya Kibernetika, 2
  42. Nemirovski, 1995, Information-based complexity of convex programming, Lecture Notes
  43. Nemirovski, 2004, Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM Journal on Optimization, 15, 229, 10.1137/S1052623403425629 · DOI · Paper page
  44. Nemirovski, 2004, Interior point polynomial time methods in convex programming, Lecture Notes
  45. Nesterov, 1983, A method of solving a convex programming problem with convergence rate o(1/k2), Soviet Mathematics Doklady, 27, 372
  46. Nesterov, 2004, Smooth minimization of non-smooth functions, Mathematical programming, 103, 127, 10.1007/s10107-004-0552-5 · DOI · Paper page
  47. Nesterov, 1994, Interior-point polynomial algorithms in convex programming, 10.1137/1.9781611970791 · DOI · Paper page
  48. Newman, 1965, Location of the maximum on unimodal surfaces, Journal of the ACM, 12, 395, 10.1145/321281.321291 · doi:10.1145/321281.321291
  49. Parikh, 2013, Proximal algorithms, Foundations and Trends® in Optimization, 1, 123
  50. Richtárik, 2012, Parallel coordinate descent methods for big data optimization, Arxiv preprint arXiv:1212.0873 · arXiv
  51. Rockafellar, 1970, Convex Analysis, 10.1515/9781400873173 · DOI · Paper page
  52. Rudelson, 1999, Random vectors in the isotropic position, Journal of Functional Analysis, 164, 60, 10.1006/jfan.1998.3384 · DOI · Paper page
  53. Schmidt, 2011, Convergence rates of inexact proximalgradient methods for convex optimization, Advances in neural information processing systems, 1458
  54. Shalev-Shwartz, 2013, Stochastic dual coordinate ascent methods for regularized loss minimization, Journal of Machine Learning Research, 14, 567
  55. Shalev-Shwartz, 2013, Accelerated mini-batch stochastic dual coordinate ascent, Advances in Neural Information Processing Systems (NIPS)
  56. Su, 2014, A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights, Advances in Neural Information Processing Systems (NIPS)
  57. Tibshirani, 1996, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society. Series B (Methodological), 58, 267, 10.1111/j.2517-6161.1996.tb02080.x · DOI · Paper page
  58. Tsybakov, 2003, Optimal rates of aggregation, Conference on Learning Theory (COLT), 303
  59. Vaidya, 1989, A new algorithm for minimizing convex functions over convex sets, Foundations of Computer Science, 1989., 30th Annual Symposium on, 338, 10.1109/SFCS.1989.63500 · DOI
  60. Vaidya, 1996, A new algorithm for minimizing convex functions over convex sets, Mathematical programming, 73, 291, 10.1007/BF02592216 · doi:10.1007/bf02592216
  61. Wright, 2009, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57, 2479, 10.1109/TSP.2009.2016892 · DOI · Paper page
  62. Xiao, 2010, Dual averaging methods for regularized stochastic learning and online optimization, Journal of Machine Learning Research, 11, 2543
  63. Zhang, 2014, Stochastic primal-dual coordinate method for regularized empirical risk minimization, Arxiv preprint arXiv:1409.3257 · arXiv

Cited by

Metadata

Authors
Bubeck, S.
Affiliations
Theory Group, Microsoft Research
Venue
Foundations and Trends® in Machine Learning
Publisher
Emerald
Published
2015-11-12
Volume
8
Issue
3-4
Pages
231-357
ISSN
  • 1935-8237
  • 1935-8245
DOI
10.1561/2200000050
Cited by
1,001
References
7
Language
en

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.