Convex Optimization: Algorithms and Complexity

By Sébastien Bubeck. 2014

2,173 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Training Compute-Optimal Large Language Models (2022, neutral): “This convergence rate is expected to be dimension free (see e.g. Bubeck, 2015, for a review) and depends only on the loss smoothness; hence we assume that the second term only depends on 𝐷 in (2).”
Privacy Amplification via Random Check-Ins (2020, positive): “One can view this line of reasoning to be analogous to privacy-preserving deep learning research, in that the theoretical guarantees for convex models acted as guiding principles for non-convex (deep learning) models [9, 1, 29].”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, background): “It is well known that the condition number measures how quickly methods such as gradient descent can find a minimizer of a strongly convex function (see Chapter 3 of (Bubeck, 2017) for reference).”
Personalized Federated Learning with Moreau Envelopes (2020, background): “O (√ κ log ( d ν ))) [50], where d is the diameter of the search space, ν is an accuracy level, and O(·) hides constants.”
Natural Compression for Distributed Deep Learning (2019, methodology): “There are several stochastic gradient-based methods [38, 6, 12, 31] for solving (1) that are compatible with compression operators C ∈ B(ω), and hence also with our natural compression (Cnat) and natural”
Privacy Amplification by Iteration (2018, background): “In order to analyze the performance of the noisy projected gradient descent algorithm for this problem we will need the following classical result about stochastic convex optimization (e.g., [Bub15]).”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “The work of Chen et al. (2017) considers only strongly convex losses, and seeks to circumvent the above issue by grouping the worker machines into mini-batches; however, their rate Õ( √ α √ n + 1 √ nm ) still falls short of being optimal, and in particular their algorithm fails even when there is on”
QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks (2016, methodology): “We describe the method below, following the presentation of Bubeck [6].”
Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, methodology): “It is generally impossible to find an exact analytical expression to relate τ and K with F (w), because it depends on the convergence property of gradient descent (for which only upper/lower bounds are known [40]) and the impact of the global aggregation frequency on the convergence.”
Scheduling Policies for Federated Learning in Wireless Networks (2019, background): “The advantage of using the dual formulation in (6) is that it allows us to better separate the global problem into a number (4)In this paper, we follow the convention and write the definition of strong convexity using gradient [30].”
Learngene: From Open-World to Your Learning Task (2021, background): “Judgement Criterion For the optimization of the objective function L(W;S), the optimality will be achieved at W when ∇L(W;S) = 0 (Boyd, Boyd, and Vandenberghe 2004; Bubeck 2014).”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “This is a well-known fact in optimization, and most convergence bounds for stochastic-gradient based methods, including minibatch, involve upper bounds on E[‖ĝ(wk)‖](2)2, in a multiplicative form, for both convex and nonconvex setups [39, 40, 41, 42, 42, 43, 44, 45, 46, 47].”
Introduction to Online Convex Optimization (2016, neutral): “8 is taken from [24] Theorem 3.”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, methodology): “[18]) is used to obtain a lower bound on the local computation time of individual machines.”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, methodology): “The proof of Theorem 1 relies on splitting the function used by Nesterov to prove oracle complexities for strongly convex and smooth optimization [8, 22] on two nodes at distance ∆ .”
Towards Practical Differentially Private Convex Optimization (2019, background): “Convex optimization in the non-private setting has a long history, with several excellent resources providing a good overview [20], [21].”