Convex Optimization
By Stephen P. Boyd, Lieven Vandenberghe. 2010
40,693 citations recorded by the source corpus.
This textbook is based on lectures given by the authors at MIPT (Moscow), HSE (Moscow), FEFU (Vladivostok), V.I. Vernadsky KFU (Simferopol), ASU (Republic of Adygea), and the University of Grenoble-Alpes (Grenoble, France). First of all, the authors focused on the program of a two-semester course of lectures on convex optimization, which is given to students of MIPT. The first chapter of this book contains the materials of the first semester ("Fundamentals of convex analysis and optimization"), the second and third chapters contain the materials of the second semester ("Numerical methods of convex optimization"). The textbook has a number of features. First, in contrast to the classic manuals, this book does not provide proofs of all the theorems mentioned. This allowed, on one side, to describe more themes, but on the other side, made the presentation less self-sufficient. The second important point is that part of the material is advanced and is published in the Russian educational literature, apparently for the first time. Third, the accents that are given do not always coincide with the generally accepted accents in the textbooks that are now popular. First of all, we talk about a sufficiently advanced presentation of conic optimization, including robust optimization, as a vivid demonstration of the capabilities of modern convex analysis.
Subfields: Applied Mathematics, Computational Theory and Mathematics, Numerical Analysis, 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 Applied Mathematics
- Robert Tibshirani
- Yonina C. Eldar
- Rui Zhang
- Richard Baraniuk
- Martin J. Wainwright
- Adam D. Smith
- Simon Lacoste-Julien
- Bernhard Schölkopf
In Computational Theory and Mathematics
- Sergey Levine
- Peter Richtárik
- Simon Lacoste-Julien
- Michael I. Jordan
- Ofir Nachum
- Yoshua Bengio
- Nicolas Loizou
- Martin Jaggi
In Numerical Analysis
- Peter Richtárik
- Simon Lacoste-Julien
- Michael I. Jordan
- Martin Jaggi
- Fabian Pedregosa
- Martin J. Wainwright
- Brendan O'Donoghue
- Stephen P. Boyd
In Optimization & Training
- Peter Richtárik
- Simon Lacoste-Julien
- Martin Jaggi
- Francis R. Bach
- Michael I. Jordan
- Sebastian U. Stich
- Jakub Konecný
- Nicolas Loizou
Citations in the corpus
- On Empirical Comparisons of Optimizers for Deep Learning (2019, methodology): “In the theory of convex optimization, metaparameter choices are well-understood for the most common methods on many classes of convex functions (Rockafellar, 1970; Nesterov, 2018; Boyd and Vandenberghe, 2004).”
- Evaluating Lossy Compression Rates of Deep Generative Models (2020, background): “The convexity of R p ( D ) follows from the fact that the perturbation function of any convex optimization problem is a convex function (Boyd & Vandenberghe, 2004).”
- Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints (2022, methodology): “Commonly used methods for solving constrained convex optimization problems [1, 11, 21] make assumptions on the properties of the objective function, constraints or feasible set.”
- Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Self-concordant functions enable an affine-invariant analysis of Newton’s method and have convergence rates similar to that of smooth and strongly-convex functions, but without problem-dependent constants (Nesterov, 2018; Boyd and Vandenberghe, 2004).”
- A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, background): “So let us write the Lagrangian of this problem: The Lagrangian is convex and quadratic so its minimum with respect to t, a 0 , . . . , a k 1 , z 1 , . . . − Moreover, if there is no solution to the first order condition, its minimum is −∞ (see for instance Boyd and Vandenberghe (2004, Example 4.5)).”
- Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, background): “…a vector ( x ∗ , y ∗ ) ∈ X × R d is said to be a saddle point if the following is verified for all ( x , y ) Our assumptions (convexity of f and X , feasibility of M x = 0 , and crucially boundedness of X ) are sufficient for strong duality to hold (Boyd and Vandenberghe, 2004, Exercise 5.25(e)).”
- Editing Factual Knowledge in Language Models (2021, methodology): “Given a objective to minimize in the form of can be solved with Lagrangian relaxation (Boyd et al., 2004) using a multiplier α ∈ R ≥ 0 and be approximated by sampling y ∼ p ( y ) to Equation 5 can be evaluated with automatic differentiation and optimized via gradient descent.”
- A Variational Inequality Perspective on Generative Adversarial Networks (2018, background): “Let Ω a convex set, the projection mapping P Ω : R d → Ω is nonexpansive, i.e., P Ω ( ω ) This is standard convex analysis result which can be found for instance in (Boyd and Vandenberghe, 2004).”
- Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “There are standard choices for it; see, for example, [BV04, Chapter 9].”
- Adaptive Gradient-Based Meta-Learning Methods (2019, neutral): “[9] Stephen Boyd and Lieven Vandenberghe.”
- CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, neutral): “The conjugate is given by: For details, see, e.g., Dünner et al. (2016) or Boyd and Vandenberghe (2004, Example 3.26).”
- Deep Learning for Distributed Optimization: Applications to Wireless Resource Management (2019, positive): “In the following sections, a constrained training algorithm is first developed for solving (P1) with the long-term constraints based on the primal-dual method [6], [28].”
- Privacy Aware Learning (2012, neutral): “Gradients of the loss " are asymptotically sufficient [18] (in an asymptotic sense, gradients contain all of the statistical information for risk minimization problems), stochastic gradient-based estimation procedures are (sample) minimax optimal and Bahadur efficient [23, 1, 27, Chapter 8], many es”
- Yes, Machine Learning Can Be More Secure! A Case Study on Android Malware Detection (2017, methodology): “fier sensitivity to feature changes, one can minimize the ‘ 1-norm of w. This in turn tends to promote solutions which exhibit the same absolute weight values (a well-known effect of ‘ 1regularization [13]). This is a very interesting result which has never been pointed out in the field of adversarial”
- Wasserstein Fair Classification (2019, background): “The result follows immediately from the subgra-dient rule for a pointwise max function (see Boyd and Vandenberghe (2004)).”
- All Models are Wrong, but Many are Useful: Learning a Variable’s Importance by Studying an Entire Class of Prediction Models Simultaneously (2018, background): “This problem is well-studied, and is related to the trust region problem (Boyd and Vandenberghe, 2004; Pólik and Terlaky, 2007; Park and Boyd, 2017).”
- Learning Optimized Risk Scores (2016, background): “As we discuss in Section 3.1, stalling affects many cutting plane algorithms, including variants that are not considered in machine learning (see Boyd and Vandenberghe, 2004, for a list).”
- Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, positive): “Optimization of (2) is a semi-definite programming problem (Boyd and Vandenberghe, 2004) and can be solved efficiently for small problems, using modern convex optimization software like SeDuMi and SDPT3 (Grant and Boyd.”