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

Convex optimization requires algorithms that approximately minimize a convex function over a convex set. This monograph organizes complexity theorems and corresponding algorithms across black-box, structural, non-Euclidean, and stochastic settings, showing that non-black-box methods can achieve a quadratic iteration improvement over optimal black-box methods.

  • Problem

    The central problem is designing algorithms that approximately minimize a convex function over a convex set.

  • Method

    The monograph synthesizes complexity theorems and corresponding algorithms spanning black-box, structural, non-Euclidean, and stochastic convex optimization.

  • Results

    Non-black-box methods can provide a quadratic improvement in iteration count relative to optimal black-box methods.

  • Takeaways & Limitations

    The monograph provides a structured reference for selecting convex optimization methods according to oracle model, geometry, curvature, noise, and structure.

  • Takeaways & Limitations

    The black-box treatment excludes derivative-free optimization when only a zeroth-order oracle is available.

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 introduction defines convex optimization and motivates its algorithmic importance through local-to-global properties, machine-learning applications, and oracle-based complexity analysis. It then outlines structured optimization methods, the monograph’s central complexity results, and deliberate scope limitations.

  • Introduction: Convex optimization minimizes a convex function over a convex set, with convexity defined by closure under segments and lying below chords.The algorithms considered take a convex set X and convex function f as input and return an approximate minimum of f over X.
  • 1.1 Some convex optimization problems in machine learning: Standard machine-learning problems fit convex empirical-loss objectives with convex regularization, including SVM, logistic regression, least squares, ridge regression, LASSO, sparse covariance estimation, and matrix completion.The objective represents data-dependent costs plus a simplicity-promoting regularizer, while matrix formulations cover sparse inverse covariance estimation and low-rank completion.
  • 1.3 Why convexity: Convexity supports optimization because subgradients provide global linear lower bounds and every local minimum is global, with 0 ∈∂f(x) characterizing unconstrained optimality.For differentiable convex functions, the gradient is a subgradient; constrained first-order optimality extends this condition to feasible directions.
  • 1.4 Black-box model: The black-box model accesses an unknown objective through zeroth- and first-order oracles and studies the queries needed to find an ε-approximate minimum.Its theory seeks matching upper and lower oracle-complexity bounds, while separation oracles handle unknown constraint sets and algorithms are also evaluated by elementary-operation cost.
  • 1.5 Structured optimization: Structured optimization exploits global knowledge of objectives and constraints, using methods such as interior point methods, FISTA, and Mirror Prox for problems including LPs and SDPs.This approach is motivated by the artificiality of restricting known structured objectives, such as the LASSO objective, to local oracle queries.
  • 1.6 Overview of the results and disclaimer: The monograph centers on optimal cutting-plane oracle complexity, curvature-dependent first-order complexity, non-Euclidean first-order methods, non-black-box iteration improvements, and noise robustness.It also emphasizes dimension-free and noise-robust oracle algorithms, while omitting derivative-free optimization and several practical, non-convex, distributed, heuristic, and adaptive-parameter directions.
  • 1.6 Overview of the results and disclaimer: For simplicity, the text assumes regularity and curvature parameters are known for algorithm tuning, although parallel guesses reduce the theoretical cost to logarithmic factors.This parameter-guessing observation does not apply in Chapter 6, and practical line-search methods are referenced separately.

Convex optimization in finite dimension

This section examines finite-dimensional convex optimization through black-box methods based on separation oracles and cutting-plane techniques, alongside the analysis of the volumetric barrier and conjugate gradient for convex quadratic optimization.

  • 2.1 The center of gravity method: The center of gravity method reaches an ε-optimal point using O(n log(2B/ε)) first- and zeroth-order oracle queries, matching the Ω(n log(1/ε)) lower bound up to constants.Its convergence is exponentially fast, also called a linear rate.
  • 2.1 The center of gravity method: The center of gravity method is computationally difficult because finding each center is generally intractable, motivating randomized approximate-center algorithms.The method assumes a convex body X and convex continuous f bounded in [−B, B].
  • 2.2 The ellipsoid method: The ellipsoid method uses only a separation oracle, handles feasibility and optimization, and requires O(n^2 log(1/ε)) oracle calls rather than the center of gravity method’s O(n log(1/ε)).For LPs and SDPs, the resulting overall complexities are O(max(m, n)n^3 log(1/ε)) and O(max(m, n^2)n^6 log(1/ε)), respectively.
  • 2.3 Vaidya’s cutting plane method: Vaidya’s cutting-plane method achieves O(n log(n)) oracle complexity and O(n^4) computational complexity, with the latter reducible essentially to O(n^3) up to logarithmic factors by Lee et al. [2015].It combines the best oracle complexity of the center of gravity method with the ellipsoid method’s computational tractability.
  • 2.3.1 The volumetric barrier: Vaidya’s algorithm maintains a containing polytope, minimizes its volumetric barrier, and adds or removes constraints according to leverage scores, using Newton steps for efficient minimization.A constraint is removed when its minimum leverage score is below ε; otherwise a separating constraint is added.
  • 2.3.3 Analysis of Vaidya’s method: Vaidya’s analysis shows termination after O(n log(nR/r)) steps by controlling volumetric-barrier changes and shrinking the maintained polytope until its volume falls below exp(n log(r)).The volumetric barrier is tied to Dikin-ellipsoid volume, while the constraint-addition and deletion inequalities provide the iteration bound.
  • 2.3.4 Constraints and the volumetric barrier: The analysis bounds the suboptimality gap by invoking Theorem 2.6 to upper-bound the approximate Newton decrement, using Hessian comparison and a calculation attributed to Vaidya [1996].For ε ≤ 0.006, the right-hand side of (2.15) is upper bounded by ε.
  • 2.4 Conjugate gradient: For f(x) = 1/2 x⊤Ax − b⊤x, conjugate gradient reaches the exact optimum x∗ in at most n steps by minimizing sequentially along A-orthogonal directions.The quadratic problem is equivalent to solving Ax = b.
  • 2.4 Conjugate gradient: The method constructs A-orthogonal directions from gradient evaluations, yielding a linear black-box algorithm and motivating nonlinear conjugate-gradient variants such as Fletcher–Reeves and Polak–Ribière.The linear recurrence is stated using gradients at previous points; the nonlinear variants apply the form to arbitrary convex functions.
  • 2.4 Conjugate gradient: Conjugate gradient attains an ε-optimal point for a positive-definite quadratic in order √κ log(1/ε) iterations, often far fewer than n.Here κ is the ratio of A’s largest to smallest eigenvalues.

Dimension-free convex optimization … 3.2 Gradient descent for smooth functions

The chapter develops gradient-based methods whose oracle complexity can be independent of dimension, progressing from basic gradient descent to projected subgradient methods and smooth unconstrained optimization. It emphasizes the tradeoffs among accuracy, projection cost, step-size selection, and smoothness assumptions.

  • Dimension-free convex optimization: Gradient descent updates along the steepest-descent direction using a fixed step size, and can achieve oracle complexity independent of dimension, attractive in very high dimensions.The computational cost remains at least linear in dimension because gradients must be manipulated.
  • 3.1. Projected subgradient descent for Lipschitz functions: Projected subgradient descent replaces unavailable gradients with subgradients and projects each update back onto the feasible set X.The method assumes bounded subgradients, which implies that f is L-Lipschitz on X.
  • 3.1. Projected subgradient descent for Lipschitz functions: For Lipschitz convex functions, reaching an ε-optimal point requires Θ(1/ε2) oracle calls, a dimension-independent but unimprovable black-box rate.The quantities R and L may nevertheless depend on dimension.
  • 3.1 Projected subgradient descent for Lipschitz functions: The chapter seeks stronger assumptions that retain dimension-independent oracle complexity while improving accuracy dependence from 1/ε2 toward log(1/ε).This motivates the analysis of smooth functions in the following section.
  • 3.1 Projected subgradient descent for Lipschitz functions: Projected subgradient descent can be computationally bottlenecked by projection, although Euclidean-ball and ℓ1-ball constraints admit analytical or fast combinatorial solutions.A projection-free algorithm is introduced later under an additional smoothness assumption.
  • 3.1 Projected subgradient descent for Lipschitz functions: The projected-subgradient rate uses very small or horizon-dependent step sizes, while time-varying steps preserve the rate up to a log t factor.Smoothness permits more aggressive, self-adjusting steps because gradients vanish near the optimum.
  • 3.2 Gradient descent for smooth functions: A continuously differentiable function is β-smooth when its gradient is β-Lipschitz; the section studies gradient descent for convex β-smooth functions on unconstrained Rn.For twice-differentiable functions, this condition is equivalent to Hessian eigenvalues being at most β.

3.2. Gradient descent for smooth functions

For convex β-smooth functions, gradient descent uses the update x_{t+1} = x_t − η∇f(x_t) and achieves a faster rate than in the non-smooth case. The analysis derives this rate from smoothness inequalities and a decreasing-distance argument.

  • Gradient descent for smooth functions: Gradient descent for convex β-smooth functions uses x_{t+1} = x_t − η∇f(x_t) and attains a faster rate than in the non-smooth case.
  • Gradient descent for smooth functions: Smoothness yields inequalities that quantify the improvement from one gradient-descent step and characterize smooth convex functions through condition (3.4).
  • Gradient descent for smooth functions: The proof combines the one-step inequality with convexity and shows that the distance ∥x_s − x*∥ decreases with s.
  • Gradient descent for smooth functions: The resulting recurrence is δ_{s+1} ≤ δ_s − 1 2β∥x_1 − x*∥^2 δ_s^2.

3.2. Gradient descent for smooth functions

The section analyzes gradient descent for smooth convex optimization and extends the method to constrained domains through projected updates. For the constrained case, it replaces unconstrained function-decrease reasoning with a projection-aware progress quantity and proves a corresponding guarantee.

  • 3.2. Gradient descent for smooth functions: The unconstrained proof concludes by showing that the distance to an optimum decreases along the iterates, completing the preceding convergence argument.
  • The constrained case: For constrained smooth convex optimization, projected gradient descent iterates x_{t+1} = Π_X(x_t − η∇f(x_t)).
  • The constrained case: Projection can truncate a step, so the unconstrained decrease bound 1/(2β)||∇f(x)||^2 no longer directly measures constrained progress.
  • The constrained case: The constrained analysis establishes a theorem for projected gradient descent on convex, β-smooth functions with a specified step size, using a projection-aware inequality and a decreasing-distance argument.

3.3 Conditional gradient descent, aka Frank-Wolfe

Conditional gradient descent minimizes smooth convex functions over compact convex sets by replacing projection with linear optimization, enabling arbitrary-norm analysis and sparse iterates. Applied to structured dictionary regression, it yields polynomial-time ε-optimal solutions when linear optimization over the dictionary is efficient.

  • 3.3 Conditional gradient descent, aka Frank-Wolfe: Conditional gradient descent replaces projected gradient descent’s projection with linear optimization over X, which can be substantially simpler computationally.It moves in the steepest descent direction permitted by the constraint set.
  • 3.3 Conditional gradient descent, aka Frank-Wolfe: For convex β-smooth functions under an arbitrary norm, the method has a convergence guarantee using diameter R and step sizes γ_s = 2/(s+1).The analysis is explicitly norm-adaptive and uses the corresponding dual norm.
  • 3.3 Conditional gradient descent, aka Frank-Wolfe: When X is a polytope, the tth iterate is a convex combination of at most t vertices, making iterates sparse when t ≪ n.On the simplex, this implies sparse approximate minimizers with t nonzero coordinates and error O(1/t).
  • An application of conditional gradient descent: Least-squares regression with structured sparsity: O(m^2p(n)/ε + m^4/ε^2) computational effort suffices for an ε-optimal structured dictionary-regression solution using conditional gradient descent.The method exploits polynomial-time linear optimization over the dictionary and sparse iterates, avoiding explicit representation of the potentially exponential-dimensional coefficient vector.

3.4 Strong convexity

Strong convexity measures function curvature through an improved subgradient inequality and can substantially accelerate first-order methods. It improves nonsmooth oracle complexity to O(1/(αε)) and, with β-smoothness, yields a linear rate of O((β/α) log(1/ε)).

  • Strong convexity is defined by an improved subgradient inequality and does not require differentiability, since gradients can be replaced by subgradients.
  • A function is α-strongly convex exactly when subtracting α/2 times the squared norm preserves convexity; for twice-differentiable functions, its Hessian eigenvalues are at least α.The parameter α measures curvature: linear functions have α = 0, while larger α produces larger gradients farther from the optimum.
  • O(1/(αε)) oracle complexity replaces O(1/ε2) for nonsmooth strongly convex optimization, provided step sizes remain relatively small.
  • O((β/α) log(1/ε)) oracle complexity follows for gradient descent with a constant step size when the function is also β-smooth, enabling high-accuracy optimization in very large dimensions.

3.4. Strong convexity

The section interprets strong convexity as providing quadratic lower bounds dual to the quadratic upper bounds supplied by smoothness. It then presents convergence results for projected subgradient descent and gradient descent under increasingly strong combinations of convexity, Lipschitzness, and smoothness.

  • 3.4. Strong convexity: Strong convexity supplies a convex quadratic lower bound, whereas β-smoothness supplies a convex quadratic upper bound; thus the assumptions are dual in the Fenchel framework, with β ≥ α.
  • 3.4.1 Strongly convex and Lipschitz functions: For α-strongly convex and L-Lipschitz functions, projected subgradient descent with the specified time-varying step size achieves the bound stated in Theorem 3.9.
  • 3.4.2 Strongly convex and smooth functions: For α-strongly convex and β-smooth functions, projected gradient descent yields a substantially improved convergence rate governed by the condition number κ = β/α.
  • 3.4.2 Strongly convex and smooth functions: In the unconstrained case, a larger step size improves the oracle-complexity factor from κ to (κ + 1)/4, using a stronger gradient-coercivity inequality.
  • 3.4.2 Strongly convex and smooth functions: Gradient descent with η = 2/(α+β) is analyzed for β-smooth and α-strongly convex functions on Rn using the strengthened gradient inequality.

3.5 Lower bounds

This section establishes oracle-complexity lower bounds for black-box procedures, following simplified presentations of Nemirovski and Yudin [1983] and Nesterov [2004a]. It covers non-smooth, smooth, and condition-number-dependent settings under a linear-span query assumption.

  • Oracle model: Black-box procedures map query histories and subgradients to new points, with x_1=0 and each subsequent query restricted to the span of observed subgradients.These assumptions define the procedure class used throughout the lower-bound arguments.
  • Non-smooth lower bounds: For t≤n, Theorem 3.13 gives lower bounds for both convex Lipschitz and strongly convex Lipschitz optimization against every procedure in this class.The construction applies to the two non-smooth cases and yields polynomial-in-1/t limitations.
  • Smooth lower bounds: For t≤(n−1)/2, Theorem 3.14 constructs a β-smooth convex function on which every such black-box procedure has a nonzero optimization error.The proof uses quadratic functions and the fact that the iterates remain in progressively larger coordinate spans.
  • Condition-number lower bounds: Theorem 3.15 extends the lower bound to β-smooth, α-strongly convex functions on ℓ2, expressing the difficulty in terms of the condition number κ=β/α.For large κ, the section also states a corresponding simplified form of the lower bound.

3.6 Geometric descent

Geometric descent closes the smooth-optimization complexity gaps between gradient descent and known lower bounds. The section situates it among earlier optimal methods requiring progressively weaker oracle assumptions.

  • Motivation: Gradient descent has oracle complexity O(1/ε), or O(κ log(1/ε)) when strongly convex, versus lower bounds Ω(1/√ε) and Ω(√κ log(1/ε)).
  • Geometric descent: Geometric descent, recently introduced in Bubeck et al. [2015b], closes these smooth-optimization complexity gaps.
  • Historical context: Earlier optimal methods progressed from plane-search oracles in Nemirovski and Yudin [1983], to line-search oracles in Nemirovski [1982], and finally first-order access in Nesterov [1983].

3.6. Geometric descent

Geometric descent gives a simple geometric route to accelerated optimization of smooth, strongly convex functions. The section develops its ball-shrinking intuition, basic method, acceleration, and complexity guarantees.

  • 3.6. Geometric descent: The section first obtains a geometric method with oracle complexity O(κ log(1/ε)), then explains its acceleration and gives the precise analyzed geometric descent method.Its geometric interpretation is loosely inspired by the ellipsoid method, while the accelerated construction addresses the basic method’s gradient-descent-like dependence on κ.
  • 3.6. Geometric descent: Geometric descent achieves oracle complexity O(√κ log(1/ε)) for unconstrained smooth, strongly convex optimization, improving basic gradient descent by a factor √κ.For smooth objectives, applying the method to x 7→ f(x) + ε∥x∥2 yields an almost optimal rate O(log(1/ε)/√ε).
  • 3.6.1 Warm-up: a geometric alternative to gradient descent: The warm-up method encloses the minimizer in a ball using zeroth- and first-order information, then uses smoothness to shrink that ball before repeating.The geometric strategy maintains an enclosing ball and constructs a smaller ball containing its intersection with a new ball derived from the function information.

3.6. Geometric descent

Geometric descent iteratively shrinks an enclosing ball around the optimum, yielding linear convergence that matches gradient descent. An accelerated variant reuses prior ball constraints and a line search to improve the radius-shrinkage factor.

  • 3.6. Geometric descent: The enclosing ball’s squared radius shrinks geometrically by a factor 1 − 1/κ per iteration, matching gradient descent’s convergence rate.The procedure iterates by replacing A with B, producing linear convergence.
  • 3.6.2 Acceleration: Reusing intersections of previous balls can shrink the new ball by 1 − 1/√κ instead of 1 − 1/κ, provided the new function value is smaller than earlier values.A line search handles this caveat and the resulting shift of the new ball, using a strengthened set-inclusion lemma.
  • 3.6.3 The geometric descent method: The geometric descent method maintains centers c_t and squared radii R_t^2 for balls containing the optimum, updating them through the line-search construction and Lemma 3.16.The update formulas for c_{t+1} and R_{t+1}^2 are derived from the lemma, with the proof proceeding by induction.

3.7 Nesterov’s accelerated gradient descent

This section presents Nesterov’s accelerated gradient descent as an optimal-oracle method for smooth convex optimization, covering both strongly convex and non-strongly convex settings. It also outlines the potential-based proof in the strongly convex case and the time-varying sequence construction used in the smooth case.

  • 3.7 Nesterov’s accelerated gradient descent: Nesterov’s accelerated gradient descent attains optimal oracle complexity for smooth convex optimization and is developed for both strongly convex and non-strongly convex objectives.The method is illustrated in Figure 3.6; related interpretations connect it to differential equations and mirror descent [2014].
  • 3.7.1 The smooth and strongly convex case: For α-strongly convex and β-smooth functions, the method starts from x1 = y1 and uses a potential-function induction to establish its convergence guarantee.The proof tracks lower approximations Φs to f, bounds their distance below f, and exploits their quadratic structure to derive the accelerated rate.
  • 3.7.2 The smooth case: When α = 0, the accelerated method uses time-varying combinations of the primary sequence, with updates defined from an arbitrary initial point x1 = y1.Theorem 3.19 gives the resulting guarantee for convex β-smooth functions; the proof combines inequalities across iterations and sums them over time, following Beck and Teboulle [2009].

non-Euclidean spaces

The chapter develops mirror descent for optimization in non-Euclidean norms, where Euclidean gradient methods can lose dimension-free rates. It introduces mirror maps, Bregman projections, and related methods including dual averaging and mirror prox.

  • non-Euclidean spaces: Euclidean projected gradient descent can degrade to n/t, whereas mirror descent over the ℓ1-ball achieves log(n)/t.The contrast motivates adapting the geometry to the norm and constraint set.
  • 4.1 Mirror maps: Mirror maps are strictly convex, differentiable functions whose gradients cover Rn and diverge at the domain boundary, enabling primal-dual updates.The mirror gradient maps points to dual coordinates; Bregman divergence then defines the projection back onto the constraints.
  • 4.2 Mirror descent: Mirror descent maps a primal point to dual space, takes a gradient step, and projects back using Bregman divergence, with convergence controlled by mirror-map strong convexity.The method’s analysis uses telescoping Bregman divergences and applies to convex Lipschitz objectives under the theorem’s stated assumptions.
  • 4.3 Standard setups for mirror descent: The Euclidean quadratic setup recovers projected subgradient descent, while negative entropy on the simplex gives R2 = log n and improves the convergence dependence to the stated logarithmic rate.For the simplex, Bregman projection is renormalization and strong convexity is with respect to the ℓ1 norm.
  • 4.3 Standard setups for mirror descent: On the spectrahedron, negative von Neumann entropy yields matrix-exponential updates and trace renormalization, with the same convergence rate as on the simplex.The geometry uses the Schatten 1-norm and achieves R2 = log n.
  • 4.4 Lazy mirror descent, aka Nesterov’s dual averaging: Dual averaging averages gradients in dual space before mapping back to the primal, preserving the mirror-descent theorem while potentially improving efficiency in distributed settings.The basic mirror descent scheme remains important for later saddle-point and stochastic extensions.
  • 4.5 Mirror prox: Mirror prox performs two mirror steps, evaluating the second gradient at the intermediate point, and attains the stated 1/t rate for smooth functions.Its broader role includes smooth representations of nonsmooth functions and stochastic-oracle settings.
  • 4.6 The vector field point of view on MD, DA, and MP: The analyses extend from fixed-function gradients to arbitrary vector fields, supporting online learning and later generalizations to saddle-point and stochastic optimization.Mirror descent, dual averaging, and mirror prox can be formulated for vector sequences or Lipschitz vector fields.

Beyond the black-box model

This section examines how structural knowledge enables optimization beyond the black-box model, covering composite optimization, saddle-point methods, and interior-point methods. It develops ISTA/FISTA, SP-MD/SP-MP, and Newton-based self-concordant and path-following approaches, including barrier constructions and equality-constraint adaptations.

  • Beyond the black-box model: Structural knowledge can restore fast convergence for nonsmooth objectives: composite structure enables a 1/t2 rate, while smooth saddle-point representations enable a 1/t rate.Interior-point methods instead place the structural assumption on the constraint set rather than the objective.
  • 5.1 Sum of a smooth and a simple non-smooth term: Composite optimization assumes a β-smooth convex f accessible by a first-order oracle and a convex, known simple g, including separable functions and the ℓ1-norm.In non-Euclidean settings, the corresponding approaches are Composite Mirror Descent and Regularized Dual Averaging.
  • FISTA (Fast ISTA): FISTA combines ISTA with accelerated gradient descent and achieves a convergence rate on f + g similar to accelerated gradient descent on f.ISTA has the same rate as gradient descent, while its updates are practical when the proximal problem for g is simple; for ℓ1 regularization, the update uses shrinkage.
  • 5.2 Smooth saddle-point representation of a non-smooth function: When a nonsmooth function is a maximum of smooth functions, Nemirovski’s saddle-point alternative uses the structural representation to attain a 1/t rate.The construction evaluates saddle-point solutions through the duality gap and applies mirror descent to the product space X × Y.
  • 5.2.2 Saddle Point Mirror Descent (SP-MD): SP-MD applies mirror descent on X × Y with a weighted product mirror map and a convex-concave vector field.SP-MP applies mirror prox when the saddle function is smooth, making the associated vector field Lipschitz under an appropriate norm.
  • Minimizing a maximum of smooth functions: For minimizing a maximum of smooth functions, SP-MP exploits the max representation to obtain a much better rate than black-box procedures requiring Ω(1/ε2) iterations.The formulation uses the simplex with negentropy and combines weighted evaluations of the component functions.
  • Matrix games: For zero-sum matrix games, SP-MP with negentropy on both simplices computes an ε-optimal Nash equilibrium, with iteration cost dominated by O(nm) matrix-vector multiplications.For linear classification, the same framework uses the Euclidean geometry on the unit ball and negentropy on the simplex, with iteration and total complexities given in the stated bounds.
  • 5.3 Interior point methods: Interior-point methods assume a self-concordant barrier with computable gradient and Hessian, follow the central path, and use Newton’s method for fast local convergence.Newton’s method is quadratically convergent when initialized sufficiently close to a strict local minimum with positive Hessian and Lipschitz Hessian.
  • 5.3.2 Traditional analysis of Newton’s method: Traditional Newton analysis uses Hessian Lipschitzness and an induction argument to establish the local convergence result.
  • 5.3.3 Self-concordant functions: Newton’s method is affine invariant, motivating self-concordance as an inner-product-independent replacement for Euclidean Hessian-Lipschitz assumptions.Self-concordant functions are barriers, with standard example f(x) = −log x for x > 0.
  • 5.3.3 Self-concordant functions: If the Newton decrement satisfies λf(x0) ≤1/4, standard self-concordance gives λf(xk+1) ≤2λf(xk)2, defining the quadratic-convergence region.
  • 5.3.4 ν-self-concordant barriers: ν-self-concordant barriers enable quadratic convergence after increasing the penalization parameter, and every closed convex set with non-empty interior has a (c n)-self-concordant barrier.The logarithmic function −log x is a 1-self-concordant barrier for R+.
  • 5.3.5 Path-following scheme: The path-following scheme maintains proximity to the central path and reaches an ε-optimal point after the iteration bound stated in Theorem 5.6, with initialization obtainable in O(√ν log ν) iterations.
  • 5.3.6 IPMs for LPs and SDPs: For LPs and SDPs, efficient interior-point complexity depends on computable self-concordant barriers, while equality constraints require reparameterization or constrained Newton directions.The constrained Newton direction can be obtained in closed form using Lagrange multipliers.

Convex optimization and randomness

This section develops stochastic and randomized methods for convex optimization, covering first-order, coordinate-descent, and saddle-point approaches under assumptions including smoothness and strong convexity. It examines how oracle fluctuations, variance reduction, and directional curvature shape convergence behavior and computational tradeoffs.

  • Convex optimization and randomness: Stochastic first-order oracles return random subgradients whose conditional expectation belongs to ∂f(x); convergence additionally requires bounded fluctuations, with different assumptions for non-smooth and smooth cases.The chapter distinguishes unbiased from biased oracles and gives expected-loss and finite-sum examples, noting that finite-sum objectives permit repeated passes while expected-loss access may allow only one data pass.
  • 6.1 Non-smooth stochastic optimization: Stochastic mirror descent achieves convergence for non-smooth convex optimization under a 1-strongly convex mirror map and a bounded second moment of the stochastic oracle.The Euclidean strongly convex specialization yields the corresponding stochastic gradient descent guarantee under the theorem’s oracle-moment condition.
  • 6.2 Smooth stochastic optimization and mini-batch SGD: For smooth stochastic optimization, generic noise prevents the deterministic acceleration available with exact gradients, although acceleration can occur for particular losses and oracles.The text contrasts stochastic smooth optimization with deterministic smooth rates and cites square-loss and logistic-loss exceptions.
  • 6.2 Smooth stochastic optimization and mini-batch SGD: Mini-batch SGD averages independent oracle queries, interpolating between stochastic and deterministic behavior and becoming advantageous when gradient computations can be distributed or reused.Its convergence guarantee follows by applying the smooth stochastic result to the averaged oracle, with oracle-call accounting based on t/m iterations.
  • 6.3 Sum of smooth and strongly convex functions: For sums of smooth strongly convex functions, SGD is preferable for low accuracy, whereas gradient descent is more suitable for high accuracy; SAG, SDCA, and SVRG target both regimes.The cited complexity comparison gives gradient descent O(mκ log(1/ε)), accelerated gradient descent O(m√κ log(1/ε)), SGD O(1/(αε)), and SAG/SDCA O((m + κ) log(1/ε)).
  • 6.3 Sum of smooth and strongly convex functions: SVRG reduces stochastic-gradient variance by replacing ∇fi(x) with ∇fi(x) − ∇fi(y) + ∇f(y), where y is updated less often because computing ∇f(y) requires m gradient computations, in an epoch-based algorithm.Theorem 6.5 considers β-smooth convex fi and an α-strongly convex f with η = 1/(10β) and k = 20κ.
  • 6.4 Random coordinate descent: Random coordinate descent is an SGD instance using an unbiased coordinate oracle, but it needs n times more iterations than gradient descent for comparable accuracy without directional smoothness.The method selects a coordinate uniformly at random and updates only that coordinate.
  • 6.4.1 RCD for coordinate-smooth optimization: Under directional smoothness, nonuniform RCD(γ) uses coordinate-specific step sizes and sampling; RCD(1) can match gradient descent’s iteration count while making each iteration potentially cheaper, and strong convexity yields a linear rate.The directional result is based on coordinate smoothness parameters β_i, while the strongly convex extension applies strong convexity in the corresponding weighted norm.
  • 6.4.2 RCD for smooth and strongly convex optimization: The randomized-coordinate-descent proof invokes strong convexity, Hölder’s inequality, and elementary calculations before concluding the stated theorem.
  • 6.5 Acceleration by randomization for saddle points: Stochastic Saddle Point Mirror Descent replaces true saddle-point subgradients with outputs from an oracle whose conditional expectations are valid subgradients.The resulting method is introduced as S-SP-MD, with a theorem stated under assumptions on the stochastic oracle.

Y. Then S-SP-MD

The section applies S-SP-MD to matrix games and then develops convex-relaxation and randomized-rounding methods for MAXCUT, followed by randomized center-of-gravity methods based on random walks. It establishes sublinear dependence for stochastic matrix-game optimization, approximation guarantees for MAXCUT, and conditions and complexity bounds for randomized cutting-plane methods.

  • Y. Then S-SP-MD: S-SP-MD obtains an ε-optimal Nash equilibrium for matrix games in O((n + m) log(n + m)/ε^2) overall complexity, sublinear in the matrix size.Its iteration count is O(max(n + m) log(n + m)/ε^2), with O(n + m) work per step; the ε dependence is worse than SP-MP, but the dimension dependence improves from eO(nm) to eO(n + m).
  • 6.6. Convex relaxation and randomized rounding: MAXCUT is NP-hard because of its hypercube constraint, whereas replacing the hypercube by a Euclidean sphere yields an efficiently solvable maximal-eigenvalue problem.The discussion also notes a Nesterov [1997] result extending the approach to any positive semi-definite matrix with a weaker approximation constant.
  • 6.6. Convex relaxation and randomized rounding: For MAXCUT, uniformly sampled hypercube signs yield a 1/2-approximation in expectation and approach that ratio with probability approaching 1 under repeated sampling.A single sample is a (1/2 − ε)-approximate solution with probability at least ε.
  • 6.6. Convex relaxation and randomized rounding: The Goemans-Williamson SDP relaxation and Gaussian sign rounding achieve E ζ⊤Lζ ≥ 0.878 max x∈{−1,1}n x⊤Lx for MAXCUT.The SDP can be solved efficiently with interior-point methods, and the rounding uses ξ ∼ N(0, Σ) followed by ζ = sign(ξ).
  • 6.7. Random walk based methods: Randomized center-of-gravity methods retain the original convergence speed when the current set is near-isotropic and the estimated center has Euclidean error below 0.1.With N = O(n) samples, the method makes progress on a constant fraction of iterations.
  • 6.7. Random walk based methods: The randomized center-of-gravity method requires eO(n) oracle calls and eO(n^5) random-walk steps, using hit-and-run sampling that mixes in O(n^3) steps from a suitable starting distribution.Putting each set in near-isotropic position requires eO(n) samples per iteration, and the initialization uses S1 = [−L, L]n ⊃ X with separation-oracle calls when the estimated center lies outside X.
Loading 1405.4980v2…