PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex Optimization: Algorithms and Complexity

Sébastien Bubeck

arXiv:1405.4980v2math.OCcs.CCcs.LGmath.NAstat.ML

TL;DR

The monograph addresses how to understand and solve convex optimization problems through complexity theorems and corresponding algorithms. It develops black-box, structural, non-Euclidean, stochastic, and related methods, with results spanning optimal oracle complexity and improved iteration complexity. Its scope is bounded by computational bottlenecks, projection costs, slow nonsmooth convergence, and several deliberately omitted settings.

  • Problem

    The monograph studies how many oracle queries and what algorithms are needed to find ε-approximate minima of convex functions over convex sets.

  • Method

    It develops a theory and algorithmic treatment spanning black-box oracles, cutting-plane and first-order methods, non-Euclidean mirror methods, structural optimization, stochastic optimization, and related convex formulations.

  • Results

    Non-black-box methods can give a quadratic improvement in iteration count over optimal black-box methods, alongside optimal oracle-complexity and curvature-dependent results.

  • Takeaways & Limitations

    The monograph provides a structured reference connecting convex optimization complexity theorems with algorithms across black-box, structural, stochastic, and machine-learning settings.

  • Takeaways & Limitations

    The treatment assumes known regularity and curvature parameters and excludes derivative-free optimization, while center-of-gravity computation can itself be computationally difficult.

Abstract

from arXiv · show

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.

Introduction

The monograph develops convex optimization from foundational definitions and black-box complexity theory to algorithms, applications, and stated scope boundaries. It emphasizes complexity theorems, oracle-based methods, and convex formulations used in machine learning.

  • Foundations: Convex optimization studies convex functions and sets, seeking algorithms that output an approximate minimum of a convex function over a convex set.Convexity is defined through containment of line segments and the requirement that functions lie below their chords.
  • Applications: Convex formulations cover machine-learning problems including SVM, regularized logistic regression, least squares, ridge regression, LASSO, sparse inverse covariance estimation, and matrix completion.These formulations combine data-dependent convex losses with regularization or structural constraints such as positive semidefiniteness and observed-entry matching.
  • Foundations: Subgradients provide global linear lower bounds, and convex functions have subgradients in the interior while gradients are subgradients wherever differentiability holds.The monograph connects these local-to-global properties to the algorithmic tractability of convex minimization.
  • Black-box optimization: The black-box model studies oracle-query requirements for finding ε-approximate minima and supports matching upper and lower bounds for subclasses of convex functions.The model treats the constraint set as known and the objective as accessible through oracle queries, while also tracking elementary computational operations.
  • Scope and results: The monograph organizes five major results around optimal cutting-plane oracle complexity, curvature-dependent first-order complexity, non-Euclidean methods, non-black-box iteration improvements, and noise robustness.It also identifies convex optimization as a broad framework because many important optimization problems admit convex reformulations.
  • Scope and results: The selection excludes duality-based methods, convex optimization for non-convex settings, practical large-scale algorithms, and derivative-free optimization.The authors also assume relevant regularity and curvature parameters are known for algorithm tuning, while noting that parameter guessing costs only logarithmic factors in theory outside Chapter 6.

Convex optimization in finite dimension

The chapter develops finite-dimensional convex optimization methods, emphasizing oracle complexity, geometric cutting-plane procedures, and computational trade-offs. It presents center-of-gravity, ellipsoid, and Vaidya methods, along with their convergence guarantees and limitations.

  • The chapter assumes a convex body X contained in a radius-R Euclidean ball and containing a radius-r Euclidean ball, with a continuous convex function bounded by B.
  • Cutting-plane algorithms require only a separation oracle for X, while their oracle complexity is linear or quadratic in the dimension.
  • Center of gravity method: The center-of-gravity method achieves O(n log(2B/ε)) queries to both first- and zeroth-order oracles, matching an Ω(n log(1/ε)) lower bound up to constants.
  • Center of gravity method: The center-of-gravity method has an exponentially fast, or linear, convergence rate, but computing each center of gravity is generally computationally difficult.
  • Ellipsoid method: The ellipsoid method uses O(n^2 log(1/ε)) oracle calls, versus O(n log(1/ε)) for the center-of-gravity method, but is computationally more tractable through efficient separation oracles.
  • Vaidya’s method: Vaidya’s method combines O(n log(n)) oracle complexity with O(n^4) computational complexity, later reducible essentially to O(n^3) up to logarithmic factors.

Dimension-free convex optimization

Gradient descent variants achieve dimension-free oracle complexity for convex optimization, while projected subgradient descent handles nonsmooth constrained problems through subgradients and projection. Its black-box rate is unimprovable, but projection and step-size selection create practical bottlenecks.

  • Gradient descent: Gradient descent uses a fixed-step update in the negative gradient direction, following the steepest descent direction of a local Taylor approximation.The method starts from an initial point and iteratively updates using step size η > 0.
  • Gradient descent: Dimension-free oracle complexity makes gradient-descent methods attractive for optimization in very high dimension.The computational cost remains at least linear in dimension because gradients must be manipulated.
  • Projected subgradient descent: Projected subgradient descent replaces gradients with subgradients and projects each updated point back onto the feasible set X.This modification accommodates convex functions that may be nondifferentiable while preserving feasibility.
  • Projected subgradient descent: Θ(1/ε^2) oracle calls are necessary for ε-optimality in the nonsmooth black-box setting, independently of ambient dimension n.The rate is described as unimprovable from a black-box perspective, although R and L may depend on dimension.
  • Smoothness: Smoothness permits more aggressive steps because gradients decrease near the optimum, motivating faster methods with dimension-independent and logarithmic accuracy scaling.The chapter contrasts this goal with the slower nonsmooth rate.
  • Practical limitations: Projection can itself be a convex optimization bottleneck, while the recommended step size depends on the planned number of iterations.Some feasible sets, including Euclidean and ℓ1-balls, admit easier projection procedures.

3.2. Gradient descent for smooth functions

For convex β-smooth functions, gradient descent obtains a faster convergence rate than in the nonsmooth case. The analysis relies on smoothness inequalities that quantify one-step improvement and control distance to the optimum.

  • Smooth gradient descent: Gradient descent attains a much faster convergence rate for convex β-smooth functions than for nonsmooth convex functions.The unconstrained analysis uses the update x_t+1 = x_t − η∇f(x_t).
  • Analysis: The smoothness lemmas provide inequalities that evaluate the improvement produced by one gradient-descent step.These inequalities combine smoothness with convexity and support the convergence proof.
  • Analysis: The proof establishes convergence by showing that the distance from each iterate to the optimum decreases with the iteration index.This monotonicity is combined with the smoothness inequalities to derive the rate.

3.2. Gradient descent for smooth functions

The constrained smooth case uses projected gradient descent and a progress measure adapted to the possibility that projection truncates a step. The resulting theorem extends smooth-gradient analysis to optimization over X.

  • Constrained gradient descent: Projected gradient descent updates by taking a gradient step and projecting the result onto X.The method is the constrained analogue of gradient descent for smooth functions.
  • Constrained analysis: Projection can prevent the unconstrained one-step decrease bound from applying, so the constrained analysis uses a different quantity to measure progress.The projected step may be cut short by the constraint set.
  • Rate refinement: The analysis notes that incorporating the initial error δ1 can improve the derived rate.This refinement follows from the smoothness inequality and the stated bound on δ1.
  • Constrained analysis: The constrained proof combines smoothness inequalities with decreasing distance to the optimum to establish the convergence bound.The argument uses the projected-gradient progress quantity and an induction on the error sequence.

3.3 Conditional gradient descent, aka Frank-Wolfe

Conditional gradient descent, or Frank–Wolfe, minimizes smooth convex functions without projections by solving linear optimization problems over the feasible set. It also supports arbitrary norms and sparse iterates, enabling structured high-dimensional applications.

  • Conditional gradient method: Conditional gradient descent replaces projected-gradient projection with linear optimization over X, which can be substantially simpler in some cases.The method performs a constraint-dependent steepest-descent step using a fixed sequence of coefficients.
  • Norm-free analysis: The method adapts to smoothness measured in an arbitrary norm, with convergence controlled by β and the diameter R of X in that norm.The dual norm is used to measure gradient differences.
  • Sparsity: Conditional gradient descent produces sparse iterates on polytopes, complementing its projection-free and norm-free properties.A polytope is represented as the convex hull of finitely many vertices, and the iterates use sparse convex combinations.
  • Sparsity: t nonzero coordinates suffice for an approximate minimizer on the simplex with suboptimality f(x) − f(x*) = O(1/t).The passage states that this sparsity guarantee is best possible in general.
  • Structured least squares: For structured dictionaries, conditional gradient descent exploits sparse minimizers and efficient linear optimization to avoid explicitly storing vectors of size N.The application targets least-squares optimization over an ℓ1-ball when N may be exponential in n.
  • Structured least squares: The structured least-squares application reaches ε-optimality with computational effort O(m^2p(n)/ε + m^4/ε^2).The complexity uses the dictionary-oracle cost p(n) and the smoothness bound derived for the objective.

3.4 Strong convexity

Strong convexity adds curvature to convex optimization, enabling faster convergence guarantees for first-order methods. With smoothness as well, strongly convex functions can be optimized to high accuracy in very large dimensions.

  • Definition: Strong convexity strengthens the subgradient inequality by introducing a curvature parameter α.The definition does not require differentiability and can use any subgradient g ∈∂f(x).
  • Interpretation: α measures curvature: linear functions have α = 0, while larger α produces larger gradients away from the optimum.For nonsmooth functions, step sizes still need careful tuning despite the stronger curvature.
  • Convergence: Strong convexity improves nonsmooth oracle complexity from O(1/ε^2) to O(1/(αε)).
  • Convergence: With β-smoothness, gradient descent with a constant step size achieves oracle complexity O(β/α log(1/ε)).This establishes optimization to high accuracy in very large dimension for strongly convex and smooth functions.

3.4. Strong convexity

Strong convexity and smoothness admit complementary quadratic interpretations and yield progressively sharper convergence guarantees for projected and unconstrained gradient methods.

  • Geometric interpretation: Strong convexity provides a quadratic lower bound, while β-smoothness provides a quadratic upper bound, making the assumptions dual in the Fenchel framework.The parameters satisfy β ≥ α.
  • Projected subgradient descent: Projected subgradient descent with η_s = 2/(α(s+1)) has a strong-convexity-based convergence guarantee for α-strongly convex, L-Lipschitz functions.The proof sums the per-iteration inequalities and applies Jensen’s inequality.
  • Projected gradient descent: Projected gradient descent improves the condition-number dependence for functions that are both α-strongly convex and β-smooth.The section denotes κ = β/α and states the improved result in Theorem 3.10.
  • Unconstrained gradient descent: In the unconstrained case, a larger step size replaces κ by (κ + 1)/4 in the oracle-complexity bound.The improvement is a constant-factor gain based on a sharper coercivity-of-the-gradient inequality.
  • Unconstrained gradient descent: Gradient descent with η = 2/(α+β) obtains a convergence theorem for β-smooth, α-strongly convex functions on R^n.The proof uses the strengthened gradient inequality from Lemma 3.11.

3.5 Lower bounds

The lower-bound analysis constructs adversarial convex functions against black-box first-order procedures, establishing limitations across nonsmooth, smooth, and strongly convex settings.

  • Black-box framework: The lower bounds follow the Nemirovski–Yudin framework and restrict black-box procedures to query points generated from previous oracle information.The exposition assumes x_1 = 0 and each next query lies in the span of preceding subgradients.
  • Nonsmooth lower bounds: For convex L-Lipschitz optimization over B_2(R), an adversarial function forces a positive error after t ≤ n oracle calls.A corresponding α-strongly convex and L-Lipschitz construction is also provided.
  • Nonsmooth lower bounds: The restriction t ≤ n is necessary for polynomial-in-1/t lower bounds because more than n oracle calls can yield exponential convergence in finite dimension.
  • Smooth lower bounds: For smooth convex optimization, a tridiagonal quadratic construction yields a lower bound for every admissible black-box procedure when t ≤ (n − 1)/2.The construction exploits that the t-th query has zero coordinates from position t onward.
  • Strongly convex smooth lower bounds: In ℓ2, β-smooth and α-strongly convex functions with condition number κ = β/α yield lower bounds for any number of oracle calls.For large κ, the theorem states an asymptotic form of the resulting limitation.

3.6 Geometric descent

Geometric descent closes the complexity gaps left by gradient descent and existing lower bounds for smooth convex optimization.

  • 3.6 Geometric descent: Gradient descent has oracle complexity O(1/ε) for smooth optimization and O(κ log(1/ε)) in the strongly convex case.
  • 3.6 Geometric descent: The lower bounds in the section are Ω(1/√ε) and Ω(√κ log(1/ε)) for the corresponding settings.
  • 3.6 Geometric descent: Geometric descent closes these gaps with optimal oracle complexity, following an approach introduced in Bubeck et al. [2015b].The text also notes that the first optimal method historically appeared in Nemirovski and Yudin [1983].

3.6. Geometric descent

Geometric descent encloses the minimizer in progressively smaller balls using smoothness and strong convexity. Its basic form matches gradient descent, while the section motivates an accelerated variant.

  • Geometric descent: Geometric descent targets unconstrained smooth, strongly convex optimization and achieves oracle complexity O(√κ log(1/ε)).The method improves basic gradient descent by a factor √κ.
  • Geometric descent: The method constructs an enclosing ball for the minimizer from zeroth- and first-order information at the current point.Strong convexity supplies an enclosing ball, while smoothness permits shrinking it.
  • Geometric descent: Each iteration intersects the current enclosing ball with a new ball and replaces it by a ball containing that intersection.When the new radius is a fraction of the old radius, iteration yields linear convergence.

3.6. Geometric descent

Acceleration reuses the function value at the current point to tighten earlier enclosing balls, achieving a faster radius contraction than the basic strategy. A line search addresses the resulting value-ordering caveat.

  • Geometric descent: Reusing a smaller current function value can reduce the radii of previous enclosing balls and tighten the minimizer region.This opportunity is available because the current enclosing ball arose from intersections of earlier balls.
  • Geometric descent: The accelerated construction shrinks the radius by a factor 1 − 1/√κ instead of 1 − 1/κ.This is the key contraction improvement over the basic geometric strategy.
  • Geometric descent: A line search handles the requirement that the current function value be smaller than values used to build earlier balls.The line search can shift the new ball, motivating a strengthened set-inclusion lemma.
  • Geometric descent: The algorithm updates the ball center and squared radius using formulas derived from the strengthened geometric lemma.The construction tracks the center and radius through successive iterations and proves the invariant by induction.

3.7 Nesterov’s accelerated gradient descent

Nesterov’s accelerated gradient descent is presented as an optimal method for smooth convex optimization, with separate strongly convex and non-strongly convex analyses. The proof uses recursively defined auxiliary functions and sequences.

  • 3.7 Nesterov’s accelerated gradient descent: Nesterov’s accelerated gradient descent attains the optimal oracle complexity for smooth convex optimization.The section gives the method and details for both strongly convex and non-strongly convex cases.
  • 3.7 Nesterov’s accelerated gradient descent: The algorithm starts from x1 = y1 and iterates coupled sequences defined by Nesterov’s update equations.The method is illustrated in Figure 3.6 and uses time-varying combinations in the non-strongly convex case.
  • 3.7 Nesterov’s accelerated gradient descent: The convergence proof combines lower approximations Φs with smoothness, convexity, and an induction argument.The resulting inequalities are assembled to obtain the rate stated in the theorem.
  • 3.7 Nesterov’s accelerated gradient descent: For the strongly convex case, the proof tracks auxiliary functions Φs whose curvature remains tied to α and whose minimizers are updated recursively.The analysis derives the sequence relations needed to establish the theorem’s convergence inequality.
  • 3.7 Nesterov’s accelerated gradient descent: The non-strongly convex adaptation uses a time-varying combination of primary-sequence elements and sequences with γt ≤ 0.The resulting method satisfies the theorem stated for convex β-smooth functions.

non-Euclidean spaces

Mirror descent extends dimension-free optimization beyond Euclidean geometry by adapting updates to the norm and domain. Its convergence guarantees depend on the mirror map’s geometry, yielding improved rates in simplex and related settings.

  • Motivation and geometry: When Euclidean geometry loses dimension-free rates, mirror descent can optimize over the ℓ1-ball at rate log(n)/t.The chapter motivates the method through non-Euclidean norms and Banach-space optimization.
  • Mirror descent: Mirror descent uses a mirror map to move from primal coordinates to dual coordinates, take a gradient step, and return through the inverse gradient map.A Bregman-divergence projection handles points that leave the constraint set.
  • Mirror descent: The method’s general convergence guarantee is controlled by the mirror map’s strong convexity, the domain diameter R2, and the objective’s regularity.Theorem 4.2 states the bound under convexity and a ρ-strongly convex mirror map.
  • Simplex setup: With negative entropy on the simplex, the update becomes a multiplicative-style renormalization and has R2 = log n.The associated Bregman divergence is the Kullback–Leibler divergence, and projection is simple renormalization.
  • Applications and alternatives: On the simplex with ℓ∞-bounded subgradients, negative-entropy mirror descent achieves a rate of order log(n)/t, versus a slower order for regular subgradient descent.The chapter also applies analogous geometry to spectrahedra through negative von Neumann entropy.
  • Applications and alternatives: Dual averaging and mirror prox preserve the mirror-map framework while extending it to settings such as distributed optimization, saddle points, and stochastic oracles.The text presents both as alternatives or extensions of the basic mirror descent scheme.

Beyond the black-box model

Structural assumptions let first-order methods overcome black-box limitations: FISTA exploits a smooth-plus-simple nonsmooth decomposition, while saddle-point and interior-point methods address other forms of structure.

  • Structural optimization: Nonsmooth optimization can improve from the black-box 1/t rate when the objective’s nonsmoothness has identifiable structure.The text highlights smooth-plus-simple decompositions and maxima of smooth functions as exploitable cases.
  • FISTA: The proximal update is computationally practical when the simple term is separable; for ℓ1 regularization, it reduces to one-dimensional shrinkage problems.The improved rate depends on the proximal subproblem being tractable.
  • FISTA: FISTA combines accelerated gradient descent with ISTA to optimize a smooth function plus a simple nonsmooth term at a 1/t2 rate.ISTA retains the gradient-descent rate, whereas FISTA inherits the accelerated rate under the same structural setup.
  • Saddle-point methods: For maxima of smooth functions, the monograph presents saddle-point mirror prox as an alternative to smoothing and obtains a better rate than black-box nonsmooth procedures.The comparison is against the Ω(1/ε2) iteration requirement for potentially nonsmooth black-box optimization.
  • Interior-point methods: Interior-point methods use self-concordant barriers and Newton steps, which are affine invariant and converge quadratically inside a Newton decrement ball.The path-following scheme reaches an ε-optimal point after the stated iteration bound.

Convex optimization and randomness

The monograph develops stochastic first-order methods based on unbiased noisy gradients, then analyzes mini-batches, variance effects, variance reduction, and coordinate updates.

  • Stochastic oracles: A stochastic oracle returns a random vector whose conditional expectation is a subgradient of the objective.Convergence additionally requires assumptions controlling oracle fluctuations.
  • Stochastic oracles: The canonical machine-learning oracles estimate expected loss gradients from sampled examples or empirical-loss gradients from randomly selected data points.These two settings differ in how data may be reused across queries.
  • Stochastic descent: Stochastic mirror descent and stochastic gradient descent provide convergence guarantees under bounded second moments, including strongly convex objectives.The results are stated for mirror maps and for the Euclidean strongly convex specialization.
  • Smooth stochastic optimization: For general stochastic smooth optimization, smoothness alone does not guarantee acceleration, although specific losses and oracles can admit acceleration.The text contrasts this with exact-oracle acceleration and cites square and logistic loss as exceptions.
  • Mini-batches: Mini-batch SGD can improve the oracle-based rate by averaging independent gradients and is especially useful with distributed computation.The text also identifies serial settings where mini-batches may be advantageous.
  • Coordinate descent: Random coordinate descent can require n times more iterations than gradient descent, but directional smoothness can greatly improve this comparison and strong convexity yields a linear rate.With directional smoothness, coordinate updates can have comparable accuracy with potentially cheaper iterations.

Y. Then S-SP-MD

The chapter connects convex optimization with randomized approximation: stochastic mirror prox yields sublinear matrix-game algorithms, while SDP relaxations and randomized rounding approximate MAXCUT.

  • Y. Then S-SP-MD: For matrix games, stochastic mirror prox samples matrix indices according to the current mixed strategies instead of performing full matrix-vector products.The stochastic subgradients use one sampled column and one sampled row.
  • Y. Then S-SP-MD: S-SP-MD obtains an ε-optimal Nash equilibrium in O(max log(n + m)/ε2) iterations, with each step costing O(n + m).The resulting overall complexity is O(max(n + m) log(n + m)/ε2).
  • Y. Then S-SP-MD: Its dimension dependence is eO(n + m) rather than eO(nm), making the method sublinear in the size of the matrix A.The ε-dependence is worse than for SP-MP.
  • Convex relaxation: MAXCUT is NP-hard because of the hypercube constraint, whereas replacing the hypercube with a Euclidean sphere gives an efficiently solvable eigenvalue problem.This motivates convex relaxation before randomized rounding.
  • Randomized rounding: Uniform random signs provide a 1/2-approximation to MAXCUT in expectation, and repeated sampling approaches this guarantee with high probability.A sampled solution is a (1/2 − ε)-approximation with probability at least ε as stated in the passage.
  • Randomized rounding: The Goemans-Williamson strategy solves an SDP relaxation and rounds a Gaussian vector with covariance equal to the SDP solution, achieving a 0.878 approximation for MAXCUT.The SDP can be solved efficiently with interior-point methods.
  • Random-walk methods: Randomized center-of-gravity methods replace exact centers with sampled approximations, retaining comparable progress when the body is near isotropic and the center error is small.The informal complexity summary is eO(n) oracle calls and eO(n5) random-walk steps.
Loading 1405.4980v2…