mlsanityData to 7 Oct 2026

Convex Optimization: Algorithms and Complexity

arXiv 1405.4980 ↗First posted 20 May 2014math.OC cs.CC cs.LGcited by 569

Not on the map. Why?

Abstract (arXiv)

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, mini-batches, 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.

Key facts. Cited by 569 papers in the map (data through 7 Oct 2026). First posted on arXiv 20 May 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 2; 2020: 1; 2021: 115; 2022: 104; 2023: 120; 2024: 97; 2025: 87; 2026: 43.

569 papers.

Sort:

By area:

  1. 2022Training Compute-Optimal Large Language Modelscited by 2,927
  2. 2021Remember What You Want to Forget: Algorithms for Machine Unlearningcited by 360
  3. 2026Reinforcement Learning via Self-Distillationcited by 285
  4. 2023Nash Learning from Human Feedbackcited by 220
  5. 2021Federated Multi-Task Learning under a Mixture of Distributionscited by 189
  6. 2024Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferencescited by 176
  7. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  8. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 130
  9. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  10. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  11. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  12. 2022Tutorial on amortized optimizationcited by 83
38 more
  1. 2021FedCM: Federated Learning with Client-level Momentumcited by 77
  2. 2021Learning with User-Level Privacycited by 72
  3. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  4. 2023How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representationscited by 72
  5. 2021Towards Robustness Against Natural Language Word Substitutionscited by 68
  6. 2021Improved OOD Generalization via Adversarial Training and Pre-trainingcited by 66
  7. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  8. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 61
  9. 2024Active Preference Optimization for Sample Efficient RLHFcited by 61
  10. 2021Graph Neural Networks Inspired by Classical Iterative Algorithmscited by 60
  11. 2022Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Losscited by 60
  12. 2024Gradient Guidance for Diffusion Models: An Optimization Perspectivecited by 59
  13. 2021Blockchain Assisted Decentralized Federated Learning (BLADE-FL): Performance Analysis and Resource Allocationcited by 55
  14. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 54
  15. 2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 53
  16. 2022MM-BD: Post-Training Detection of Backdoor Attacks with Arbitrary Backdoor Pattern Types Using a Maximum Margin Statisticcited by 53
  17. 2021Semi-Decentralized Federated Learning with Cooperative D2D Local Model Aggregationscited by 50
  18. 2022Making SGD Parameter-Freecited by 50
  19. 2023Toward Understanding Why Adam Converges Faster Than SGD for Transformerscited by 50
  20. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 50
  21. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  22. 2024Why Warmup the Learning Rate? Underlying Mechanisms and Improvementscited by 45
  23. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  24. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  25. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  26. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  27. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  28. 2023The SSL Interplay: Augmentations, Inductive Bias, and Generalizationcited by 40
  29. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
  30. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  31. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  32. 2021Understanding the role of importance weighting for deep learningcited by 38
  33. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 38
  34. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  35. 2023Test-Time Training on Video Streamscited by 37
  36. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  37. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  38. 2023Fast Rates for Maximum Entropy Explorationcited by 32

50 most cited of 569 All 569 (JSON)