Acceleration Methods

Alexandre d'Aspremont; Damien Scieur; Adrien Taylor

Source-linked AI summary

Acceleration Methods

Alexandre d'Aspremont, Damien Scieur, Adrien Taylor

arXiv:2101.09545v4Jan 23, 2021math.OCcs.LGmath.NA

TL;DR

Large-scale convex optimization still has unresolved questions about the efficiency and complexity of first-order methods. This monograph systematically analyzes acceleration techniques and shows that optimized gradient methods attain the O(N^-2) rate while addressing identified drawbacks.

Problem
For large-scale convex optimization, the complexity of first-order methods remains incompletely understood and efficiency remains a concern.
Method
The monograph systematically studies momentum, nested, proximal, and restart acceleration techniques through principled algorithm-design and convergence-proof templates.
Results
O(N^-2) methods can match the optimized gradient rate while resolving the optimized gradient method’s identified issues.
Takeaways & Limitations
Acceleration can be treated as an explicit design objective, with optimal convergence guarantees emerging from the resulting algorithmic structure.
Takeaways & Limitations
The monograph is selective rather than exhaustive, focusing on acceleration techniques that received substantial attention since the early 2000s.

Abstract

from arXiv · show

This monograph covers some recent advances in a range of acceleration techniques frequently used in convex optimization. We first use quadratic optimization problems to introduce two key families of methods, namely momentum and nested optimization schemes. They coincide in the quadratic case to form the Chebyshev method. We discuss momentum methods in detail, starting with the seminal work of Nesterov and structure convergence proofs using a few master templates, such as that for optimized gradient methods, which provide the key benefit of showing how momentum methods optimize convergence guarantees. We further cover proximal acceleration, at the heart of the Catalyst and Accelerated Hybrid Proximal Extragradient frameworks, using similar algorithmic patterns. Common acceleration techniques rely directly on the knowledge of some of the regularity parameters in the problem at hand. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates while adapting to unobserved regularity parameters.

Introduction

The monograph surveys recent acceleration techniques for large-scale convex optimization, organizing them around direct momentum methods and nested schemes. It uses systematic design and convergence-proof templates to explain and develop accelerated first-order methods, while also covering Chebyshev, proximal, and adaptive restart approaches.

Motivation: Large-scale convex optimization remains efficiency-limited despite mature methods for medium-scale problems, motivating recent accelerated algorithms and sharper complexity bounds.These developments were driven particularly by applications in statistics, machine learning, and signal processing, building on Nesterov’s path-breaking algorithm from the 80’s.
Direct acceleration: Direct acceleration methods derive optimal worst-case gradient variants from regularity assumptions, with performance estimation selecting parameters and optimality conditions shaping both algorithms and proofs.The framework is used to analyze classical variants by Nesterov (1983; 2003), Beck and Teboulle (2009a), and Tseng (2008), alongside newer analyses by Kim and Fessler (2016).
Nested acceleration: Nested acceleration uses an outer acceleration loop around classical inner optimization methods, including nonlinear extrapolation, proximal-point acceleration, and restart schemes.The Chebyshev method spans gradient and outer-iteration viewpoints; approximate strongly convex proximal subproblems yield accelerated gradient methods, while restarts adapt to unknown Hölderian error-bound parameters.
Content and organization: The monograph focuses on influential first-order convex-optimization acceleration techniques since the early 2000s, presents the authors’ perspective, and explicitly does not aim to be exhaustive.Its sections are designed to be read nearly independently, with several complementary pairings among Chebyshev, nonlinear, Nesterov, proximal, and restart acceleration.
Prerequisites and complementary readings: Readers are expected to know basic linear algebra and convex analysis, including subdifferentials, because the monograph omits corresponding technical details.For general-purpose convex optimization, it refers readers to Boyd and Vandenberghe (2004), Bonnans et al. (2006), and Nocedal and Wright (2006), while related convex-analysis references include Rockafellar (1970), Rockafellar and Wets (2009), and Hiriart-Urruty and Lemaréchal (2013).

Chebyshev Acceleration

This section examines Chebyshev acceleration for smooth strongly convex and bounded-spectrum quadratic problems, using approximation theory to develop accelerated first-order methods and convergence guarantees. It also considers the role of spectral-bound knowledge and contrasts these guarantees with conjugate-gradient methods.

2.3 The Chebyshev Method: Chebyshev minimization produces linear combinations of past gradients and an iterative method that is worst-case optimal for quadratics with spectrum in [µ, L].The method traces to Nemirovsky and Polyak (1984), while its recurrence asymptotically matches heavy-ball.
2.1 Introduction: For quadratic objectives, any first-order method whose iterates span previous gradients has errors represented by degree-k residual polynomials P_k with P_k(0) = 1.This equivalence enables designing algorithms by minimizing worst-case polynomial bounds over a matrix class, with coefficients depending only on that class.
2.3.1 Shifted Chebyshev Polynomials: Shifted Chebyshev polynomials solve the interval minimax problem on [µ, L], retain P(0) = 1, and attain their maximum through equioscillation across the interval.Their maximum decreases rapidly with polynomial degree, implying accelerated convergence.
2.3.2 Chebyshev Algorithm: The Chebyshev semi-iterative method combines variable-step gradient updates with variable momentum, while its straightforward recurrence can have numerical stability issues.Numerically more stable first-order alternatives based on Chebyshev polynomials are available.
2.3.3 Chebyshev and Polyak’s Heavy-Ball Methods: As k →∞, the Chebyshev method’s recursion coefficients converge to Polyak’s heavy-ball coefficients, and replacing δ_k with δ_∞ yields the heavy-ball method.Both methods therefore share the same asymptotic convergence rate up to a multiplicative factor, which improves on gradient descent.
2.3.4 Worst-case Convergence Bounds: Theorem 2.1 gives a worst-case convergence guarantee for Chebyshev’s method on quadratics with µI ⪯ H ⪯ LI, and its simplified bound is better than gradient descent’s.Corollary 2.2 compares the iteration counts required by gradient descent and Chebyshev’s method to reach accuracy ǫ.
2.3.4 Worst-case Convergence Bounds: Chebyshev is κ faster than gradient descent, with a speedup factor of 100 for condition number 104.
2.3.4 Worst-case Convergence Bounds: For sufficiently large dimension, Chebyshev’s worst-case guarantee is essentially unimprovable among first-order methods under the span assumption.The lower bound applies to quadratic Hessians satisfying µI ⪯ H ⪯ LI and is formalized for d ≥ N + 1 by Nemirovsky (1994, Proposition 12.3.2).
2.4 Notes and References: The Chebyshev method is worst-case optimal for quadratic functions with Hessian spectrum bounded by µI ⪯ H ⪯ LI, but its optimal bounds require knowing µ and L.Further treatments are cited in Nemirovsky and Yudin (1983a), Nemirovsky (1992), Nesterov (2003), and Nemirovsky (1994, Chapter 10).
2.4 Notes and References: Conjugate-gradient methods are instance-optimal for unconstrained quadratic minimization, while CG, MINRES, GMRES, and Anderson-type schemes do not retain the same guarantees beyond quadratics.CG achieves the lower bound from Theorem 2.3; GMRES also applies when H is nonsymmetric or noninvertible.

Nonlinear Acceleration

This section develops nonlinear acceleration beyond quadratic minimization, extending it to online first-order, proximal, constrained, and composite settings. It also examines regularization and globalization safeguards to address instability and local convergence behavior, while relating these methods to broader acceleration techniques.

Nonlinear Acceleration: Nonlinear acceleration adapts Chebyshev’s argument beyond quadratic minimization by extrapolating sequences through nonlinear averages, including approaches known as Anderson acceleration.The framework assumes a twice continuously differentiable convex objective locally approximated by a quadratic with Hessian bounded between µI and LI.
3.2 Nonlinear Acceleration for Quadratic Minimization: The method forms an extrapolated point as a linear combination of past iterates, choosing coefficients to minimize the extrapolated gradient norm.For quadratic objectives, this reduces to a small quadratic program involving past gradients and a linear system of k + 1 equations.
3.2.1 Worst-case Convergence Bounds: Every iterate generated by a nondegenerate first-order method admits a degree-exactly-i polynomial representation of its gradient, enabling the instance-optimal extrapolation result.Nondegeneracy requires the method to use each gradient non-trivially when generating the next iterate.
3.2.1 Worst-case Convergence Bounds: For nondegenerate first-order sequences, nonlinear acceleration is instance-optimal, matches Chebyshev’s worst-case convergence rate, and requires no smoothness or strong-convexity parameters.It adaptively selects the best polynomial for the specific quadratic instance, whereas Chebyshev’s method uses one class-wide worst-case polynomial.
3.2.2 Computational Complexity: The offline algorithm has complexity O(dk2 + k3), typically O(dk2) when k is much smaller than d, and low-rank updates can reduce per-iteration cost to O(dk).Limited-memory variants restrict extrapolation to the most recent m iterate-gradient pairs.
3.2.3 Online Nonlinear Acceleration: Because offline nonlinear acceleration is not itself a nondegenerate first-order method, it cannot be applied recursively without modification.A mixing parameter converts it into a nondegenerate first-order method while preserving worst-case performance, enabling recursive online acceleration.
nonlinear acceleration.: With a properly chosen step size h, mixing gradient steps with previous iterates slightly improves nonlinear acceleration’s worst-case convergence speed.The mixing strategy introduces one tunable hyper-parameter, h.
nonlinear acceleration.: Online nonlinear acceleration with unlimited memory is no worse in worst-case performance than the offline method, while limited memory enables practical recursive use.The online method uses the offline procedure as a subroutine and retains the offline guarantee when m = ∞.
3.3 Regularized Nonlinear Acceleration Beyond Quadratics: Beyond quadratics, nonlinear acceleration is numerically unstable because ill-conditioned Krylov-structured systems make small gradient perturbations substantially affect its coefficients.For gradient-descent-derived systems, the condition number can exceed 10^16 after three iterations; regularizing the linear system yields RNA (Scieur et al., 2016).
3.3.1 Regularized Nonlinear Acceleration: RNA regularizes coefficient selection toward a reference vector, with uniform averaging or last-iterate weighting as alternatives, and simplifies under uniform averaging.Algorithms 6 and 7 solve regularized linear systems before extrapolating gradient steps, and can be used online as subroutines.
3.3.2 Perturbed Linear Gradients: For twice continuously differentiable objectives, gradients equal a strongly convex quadratic model plus a Taylor-remainder perturbation, making nonlinear minimization a perturbed quadratic problem.The model uses H satisfying 0 ≺ µI ⪯ H ⪯ LI, with the perturbation representing second-order gradient error.
3.3.3 Convergence Bound: RNA’s convergence bound formalizes a stability–acceleration tradeoff: regularization stabilizes extrapolation but slows convergence, interpolating between Chebyshev weighting and iterate averaging.Larger regularization moves coefficients toward 1/k and improves stability under substantial noise, whereas small regularization preserves near-Chebyshev acceleration when noise is negligible.
3.3.4 Asymptotic Convergence Rate: When perturbations decrease sufficiently quickly near the solution, appropriately tuned RNA achieves an asymptotic convergence rate comparable to Chebyshev’s method on quadratic problems.This follows because the objective approaches its quadratic approximation around x⋆, allowing regularization to vanish at an appropriate rate.
3.4. EXTENSIONS: The asymptotic guarantee requires perturbation decay with α > 1; for gradient descent this is achievable, with perturbations decreasing as O(∥x0 − x⋆∥2).The regularization scale must decrease, but not faster than the perturbation magnitude, requiring 0 < s < 2(α − 1).
3.4 Extensions: With stochastic gradients, RNA’s finite-iteration bound holds in expectation under bounded-noise assumptions, but asymptotic acceleration can fail for fixed-step SGD and generally works for variance-reduced methods.The cited examples of variance-reduced methods include SAG, SAGA, and SVRG.
3.4 Extensions: Mai and Johansson (2020) accelerate an alternate sequence with swapped gradient and proximal steps, avoiding domain and span obstacles in naive iterate acceleration.This modification yields proximal nonlinear-acceleration convergence bounds with few algorithmic changes.
3.5. GLOBALIZATION STRATEGIES AND SPEEDING-UP HEURISTICS: With Clarke generalized Jacobians and suitable twice-differentiability assumptions, proximal operators do not change Algorithm 8’s convergence analysis.The assumptions include twice epi-differentiability of h and twice-differentiability around x⋆.
3.5 Globalization Strategies and Speeding-up Heuristics: Because RNA has only local guarantees beyond quadratics, globalization safeguards limit performance deterioration when extrapolation leaves its guaranteed range.A descent condition can reject an extrapolated point that is worse than previous iterates, including under poor parameters or large errors.
3.5 Globalization Strategies and Speeding-up Heuristics: A line search can select the nonlinear-acceleration mixing parameter by approximately minimizing f(xextr(h)), reducing the need to tune it manually.This addresses the practical difficulty of choosing the mixing parameter.
3.6 Notes and References: Anderson acceleration matches online nonlinear acceleration without regularization, while related extrapolation variants face conditioning difficulties for nonlinear functions.Convergence has nevertheless been established when the underlying linear system is well-conditioned.

Nesterov Acceleration

This section develops Nesterov acceleration and its proof frameworks for smooth, strongly convex, nonsmooth, composite, and constrained minimization. It covers optimized and practical variants, including momentum, backtracking, restarts, monotonicity, Bregman steps, and continuous-time interpretations.

Nesterov Acceleration: The analysis begins with smooth unconstrained convex minimization and combines regularity inequalities into potential functions, with additional ingredients introduced incrementally for more advanced settings.The framework later incorporates strong convexity, constraints, nonsmooth regularization, line searches, unknown parameters, and non-Euclidean geometries.
4.1 Introduction: Worst-case analyses for smooth strongly convex first-order methods can be performed using an interpolation inequality evaluated at specific points.The section also notes that this inequality has limitations and uses the basic smoothness and strong-convexity bounds whenever possible.
4.2.1 Gradient Descent: Gradient descent uses step size 1/L when L is known, while line-search techniques handle unknown smoothness parameters.Its convergence proof recursively maintains a nonincreasing potential obtained from weighted convexity and smoothness inequalities.
4.2.3 How Conservative is this Worst-case Guarantee?: Gradient descent has worst-case accuracy O(N^-1), equivalently requiring O(ε^-1) iterations, and this rate is attained on simple nearly linear functions such as the Huber loss.The potential-function proof reduces the analysis over N iterations to a one-step inequality.
Nesterov Acceleration: The section motivates Nesterov’s accelerated methods by showing that gradient descent’s rate is unimprovable for the basic method, then optimizing worst-case performance over richer method families.The optimized gradient method also inspires variants including Nesterov’s accelerated methods and FISTA.
4.3 Optimized Gradient Method: The optimized gradient method is obtained by solving a minimax problem over a broad first-order family, then expressed in factorized forms that avoid storing all previous gradients.Its recursive parameters are constructed through a sequence θk,N, and equivalent formulations support implementation and proof.
4.3 Optimized Gradient Method: Optimized gradient methods achieve an O(N^-2) worst-case rate on smooth convex functions, improving on gradient descent’s O(N^-1) rate.The optimized method is derived by minimizing worst-case performance and is supported by a potential-function analysis.
4.3.1 A Potential for the Optimized Gradient Method: The OGM potential is a reusable template for acceleration, although its nonintuitive structure was found using computer-assisted proof-design techniques.The proof forms weighted sums of smoothness and convexity inequalities and chooses the θ parameters recursively.
4.3.2 Optimality of Optimized Gradient Methods: The optimized gradient method achieves the smallest possible worst-case function-value ratio among black-box first-order methods with N gradient evaluations.Its guarantee is matched by a black-box lower bound, so the method is optimal in this setting.
4.3.3 Optimized Gradient Method: Summary: The optimized gradient method provides a reusable template of sequence structures and potential proofs for designing accelerated gradient variants.Related methods can retain the O(N^-2) rate while using less aggressive step sizes and accepting slightly weaker worst-case guarantees.
4.3.3 Optimized Gradient Method: Summary: The OGM is finely tuned to unconstrained smooth convex minimization and does not readily extend to constrained settings.Its practical limitations motivate alternative accelerated methods that follow the same proof template.
4.4 Nesterov’s Acceleration: The section presents Nesterov acceleration using a potential-based proof and then interprets the method through estimate sequences, extending the discussion to strongly convex minimization.The presentation follows the optimized gradient method’s algorithmic template to obtain simple algebraic proofs.
4.4.1 Nesterov’s Method, from Potential Functions: Nesterov’s method attains the optimal O(N^-2) rate for L-smooth convex minimization through a potential whose growth controls the convergence rate.The potential proof selects parameters to increase A_k, with A_N growing at least quadratically in N.
4.4.2 Estimate Sequence Interpretation: Nesterov’s three equivalent formulations differ in sequence representation but coincide for unconstrained smooth convex minimization, while estimate sequences organize iterates, model updates, and candidate solutions.The formulations use model minimizers, points supplying first-order information, and iterates representing the best available objective value.
Estimate Sequences: Estimate sequences maintain increasingly accurate convex models of the objective, with convergence governed by the decay of A_k^-1.Their conditions ensure model control and relate potential-function arguments to explicit objective-function approximations.
Potential Functions as Estimate Sequences: Potential functions and estimate sequences share scalar convergence control, but estimate sequences approximate f globally whereas potentials may need only approximate f⋆.Gradient descent and Nesterov’s first method admit estimate-sequence interpretations, while the optimized gradient method’s potential exploits optimality at x⋆ and does not directly correspond to one.
4.5 Acceleration under Strong Convexity: Strong convexity adds a contraction factor (1−γµ) to gradient descent, but restricts the function class beyond smoothness alone.The assumptions are described as sandwiched between two quadratic functions.
4.5.1 Gradient Descent and Strong Convexity: For smooth strongly convex minimization, gradient descent achieves geometric convergence with rate governed by the inverse condition ratio, and its iteration complexity is essentially tight.Quadratic lower bounds imply no black-box first-order method can improve the corresponding geometric dependence; Nesterov acceleration reaches the lower complexity bound up to a constant factor.
4.5.2 Acceleration for Smooth Strongly Convex Objectives: Theorem 4.12 and Corollary 4.13 provide guarantees for L-smooth, μ-strongly convex functions, including μ=0, while z_k may serve as an approximate solution when μ>0.Because y_N is a convex combination of x_N and z_N, the same conclusion holds for ∥y_N−x⋆∥².
4.5.3 A Simplified Stationary Method with Constant Momentum: Taking the stationary limit of Nesterov’s strongly convex method yields equivalent constant-momentum Algorithms 15 and 16.Their Lyapunov analysis follows by dividing the preceding potential by A_k and taking the limit, producing a corresponding worst-case guarantee.
4.6 Recent Variants of Accelerated Methods: The section then presents the information-theoretic exact method of Taylor and Drori (2021) as a recent accelerated-method variant.This subsection begins by extending the potential-function reasoning to its limit.
4.6.1 An Optimal Method for Strongly Convex Minimization: ITEM is doubly optimal for smooth strongly convex minimization, achieving lower complexity bounds for both its stated criterion and f(y_N)−f⋆.It reduces to OGM when µ = 0 and is non-improvable among black-box first-order methods under the stated dimensional condition.
4.6.2 The Triple Momentum Method: Triple momentum is the asymptotic, constant-parameter limit of ITEM, but it inherits OGM and ITEM caveats and is defined only for µ > 0.Its analysis uses a potential function based on the same smoothness and strong-convexity inequality as ITEM.
4.6.3 Quadratic Averaging and Geometric Descent: Quadratic averaging and geometric descent generate the same iterates by combining dynamically weighted quadratic lower bounds, equivalently tracking x⋆ through intersecting balls.Quadratic averaging chooses coefficients to maximize the lower bound, whereas geometric descent chooses them to minimize the enclosing-ball radius.
4.7 Practical Extensions: Practical extensions preserve accelerated proof structures by adding a small number of inequalities for constraints, nonsmoothness, adaptation, non-Euclidean geometry, and numerical stability.Simple modifications can enforce monotonicity at low technical and computational cost.
4.7.1 Handling Nonsmooth Terms/Constraints: For minimizing a smooth convex f plus a convex closed proper h, proximal steps act as implicit subgradient steps, while forward-backward splitting applies gradient steps to f and proximal steps to h.When h is an indicator of a closed convex set, its proximal operator is the orthogonal projection onto that set.
4.7.2 Adaptation to Unknown Regularity Parameters: Unknown smoothness and strong-convexity parameters prevent direct use of earlier methods and obscure better local regularity, motivating line-search adaptation and restart schemes.Smoothness is adapted with line searches, whereas efficiently estimating strong convexity while preserving reasonable worst-case guarantees remains open without restarts.
4.7.2 Adaptation to Unknown Regularity Parameters: Unknown strong convexity is typically handled by restarts because the required inequalities involve the unknown optimum and cannot be tested during execution.In contrast, smoothness-related pairwise inequalities can be checked at runtime for the current estimate of L.
An Accelerated Forward-backward Methods with Backtracking: Backtracking extends Nesterov acceleration to nonsmooth composite objectives through FISTA and a strongly convex variant whose descent condition can be checked at runtime.The procedure increases the smoothness estimate until the descent inequality holds, with at most ⌈log_α(L/L_0)⌉ wasted gradient steps when L_0 underestimates L.
Another Accelerated Proximal Gradient Method: A proximal accelerated gradient method fixes FISTA’s potential infeasibility of y_k by applying one proximal operation to z_k while maintaining feasible iterates.Its guarantee assumes smoothness only on dom h and uses convex combinations of feasible points; the resulting complexity bound uses ℓ = max{αL, L_0}.
4.7.3 Monotone Accelerated Methods: A simple output-selection trick makes common accelerated methods monotone by maintaining a sequence whose objective values decrease monotonically, while preserving worst-case guarantees.The construction does not apply to the optimized gradient, information theoretic exact, or triple momentum methods because their potential functions have different structures.
4.7.3 Monotone Accelerated Methods: Monotone wrappers preserve the chosen algorithm’s worst-case guarantee while ensuring the objective sequence F(˜x_k) decreases monotonically.The construction enforces both F(˜x_{k+1}) ≤ F(x_{k+1}) and F(˜x_{k+1}) ≤ F(˜x_k).
4.7.4 Beyond Euclidean Geometries using Mirror Maps: Bregman proximal gradient extends accelerated methods to non-Euclidean norms using a strongly convex distance-generating function and its Bregman divergence.The framework assumes convex h, smooth f, and a 1-strongly convex function w with dom h ⊆ dom w; its Euclidean specialization uses w(x) = 1/2∥x∥_2^2.
4.7.4 Beyond Euclidean Geometries using Mirror Maps: Entropy geometry on the simplex can improve the final dimension dependence from d to ln d, while the benefit also depends on the gradient’s Lipschitz constant under the chosen norm.For the simplex, the entropy distance satisfies Dw(x⋆, x0) ≤ ln d; the ℓ1 Lipschitz constant may be up to d times smaller than the Euclidean one.
4.8 Continuous-time Interpretations: Continuous-time analyses connect first-order methods to ODEs, with discretization affecting implementation while gradient-flow convergence is controlled by the growth of a(t).Gradient descent arises from explicit Euler discretization, and for convex objectives the gradient-flow theorem uses a(t) = t.
4.8.2 An Ordinary Differential Equation for Nesterov’s Method: Nesterov’s ODE arises as the continuous-time limit of a discretized Nesterov scheme, with convergence established through a potential function whose derivative is nonpositive.The analysis considers convex objectives and derives a resulting bound from φ(t) ≤ φ(0).
4.8.3 Continuous-time Approaches to Acceleration: Summary: Continuous-time analyses simplify convergence proofs but may misrepresent digital algorithms because numerical integration can break their convergence properties.Different algorithms, including heavy-ball, Nesterov acceleration, and triple momentum, can also share the same limiting ODE.
4.8.3 Continuous-time Approaches to Acceleration: Summary: Continuized methods address implementation difficulties by using randomized discretizations of continuous-time processes while retaining their continuous-time benefits.Other integration schemes recover or generate accelerated discrete methods, including heavy-ball-type and symplectic discretizations.
4.9 Notes and References: The notes relate acceleration to estimate sequences, mirror descent, lower bounds, gradient-norm criteria, stochastic and higher-order methods, optimized methods, and performance-estimation proofs.Acceleration beyond Euclidean geometries remains unresolved under relative smoothness and relative strong convexity without additional assumptions, while performance estimation can provide tight certificates and matching worst-case instances.

Proximal Acceleration and Catalysts

This section develops accelerated and inexact proximal frameworks, including Catalyst and A-HPE, using approximate proximal operations and classical inner methods. It analyzes their potential functions, computational tradeoffs, complexity across convexity and stochastic settings, and use as meta-algorithms for accelerating first-order methods.

Proximal Acceleration and Catalysts: Approximate proximal operations yield accelerated gradient methods through conceptual accelerated proximal-point schemes whose proximal points are computed by linearly converging gradient methods, as in Catalyst and A-HPE.The outer proximal framework improves convergence guarantees while classical iterative methods approximate the proximal subproblems.
5.2. PROXIMAL POINT ALGORITHM AND ACCELERATION: Proximal-point methods admit potential-function analyses and can achieve arbitrarily strong single-step progress with large step sizes, but proximal evaluations may be nearly as difficult as the original problem.The same framework connects proximal minimization to gradient methods on the Moreau envelope, which preserves minimizers and adds smoothness.
5.2. PROXIMAL POINT ALGORITHM AND ACCELERATION: Güler acceleration improves constant-step proximal convergence from O(N −1) to O(N −2), while remaining robust to computation errors and supporting varying step sizes.Increasing step sizes can yield arbitrarily fast convergence when proximal subproblems are solved efficiently, because proximal oracles are stronger than gradient steps.
5.3 Güler and Monteiro-Svaiter Acceleration: The inexact accelerated proximal-point method of Monteiro and Svaiter tolerates relative proximal errors, preserves optimality when started at an optimum, and retains the exact method’s potential-based convergence analysis.The relative error condition scales allowable error with the distance between the starting point and approximate proximal solution, while requiring tighter accuracy near solutions.
5.4 Exploiting Strong Convexity: For µ-strongly convex objectives, the section refines proximal-point potentials and acceleration recurrences, recovering the earlier results when µ = 0.The strong-convexity analysis uses modified potential functions and the recurrence Ak+1 = Ak(1 + λkµ) + λk.
5.4. EXPLOITING STRONG CONVEXITY: The proximal point algorithm has a final worst-case guarantee for closed, proper, µ-strongly convex functions, recovering the µ = 0 case as strong convexity vanishes.With constant step sizes, the section contrasts the resulting iteration complexity with the non-strongly-convex case.
Proximal acceleration and inexactness under strong convexity: The accelerated proximal point method requires fewer inexact proximal iterations than the previous proximal point algorithm to reach a target accuracy with constant step sizes.Its guarantee follows from a potential analysis and the growth of the sequence {A_k}.
5.5 Application: Catalyst Acceleration: Catalyst embeds a base first-order method inside an accelerated proximal point method to approximately solve successive proximal subproblems, extending the approach to any suitable inner solver.The presented instance targets L-smooth convex minimization and uses gradient-based approximate solutions.
5.5.2 Detailed Complexity Analysis: Each proximal subproblem is (L + 1/λ)-smooth and 1/λ-strongly convex, and the detailed analysis bounds N_inner(k) by ensuring the prescribed gradient-based error criterion.The bound is independent of k, motivating a uniform notation for the inner computational cost.
Preliminaries: Catalyst assumes the inner method M converges linearly on smooth strongly convex proximal subproblems, while warm starts and separate outer, inner, and total iteration counters organize the computation.Approximate proximal solutions may instead be defined through other criteria, including primal-dual gap control.
Overall complexity: The combined method’s complexity is controlled by the outer accelerated iterations and the per-subproblem burden B_M,λ, measured in total calls to the inner method M.The resulting iterate after N_outer outer iterations is equivalently obtained after N_total inner iterations.
Overall complexity: Inexact accelerated proximal schemes yield accelerated rates for linearly convergent first-order methods, but practical tuning, especially step sizes, critically affects performance.The framework can also provide acceleration for non-strongly-convex objectives because proximal subproblems are strongly convex.
5.5.2 Detailed Complexity Analysis: The total iteration complexity equals the accelerated proximal-point bound multiplied by the cost of solving one proximal subproblem with M.The inner-loop count is bounded by a method- and regularization-dependent constant, yielding Ninner(k) < (Nouter + 1)BM,λ.
5.5.3 Catalyst for Strongly Convex Problems: For strongly convex problems, Catalyst retains the same overall complexity structure, with modest improvements from the stronger parameter µ + 1/λ and relaxed error tolerance.The regularization parameter λ is selected by optimizing the combined outer and inner iteration complexity.
5.5.4 Catalyst for Randomized/Stochastic Methods: Stochastic Catalyst uses the deterministic inexact accelerated proximal-point scheme with stochastic inner solves, yielding expected complexity multiplied by B^(stoch)_M,λ.The expected inner-loop burden is bounded using Markov’s inequality, and stochastic Catalyst variants were studied by Kulunchakov and Mairal (2019).
5.6 Notes and References: The notes relate Catalyst to accelerated and inexact proximal-point, hybrid proximal extragradient, stochastic, and optimized proximal methods, while noting practical implementations often use fixed inner-loop counts.Catalyst implementations commonly use absolute rather than relative inaccuracy criteria; its origins and applications include Lin et al. (2015) and stochastic methods such as SVRG and SAGA.

Restart Schemes

This section examines restart schemes for adapting first-order and accelerated methods across smoothness and error-bound settings when regularity parameters are unknown. It covers their extension to Hölder-smooth and relatively smooth problems, other first-order methods, and compressed sensing, along with the resulting nearly optimal convergence guarantees and logarithmic adaptation overhead.

6.2. HÖLDERIAN ERROR BOUNDS: Hölderian error bounds generalize strong convexity through local growth conditions that hold for broad classes, including almost generically under continuity and subanalyticity.For subanalytic functions, the Łojasiewicz factorization lemma yields the relevant local growth bound around the optimum.
6.1 Introduction: Restarting periodically refreshes accelerated methods’ models, counteracting convergence tails and discarding outdated information as iterates approach the optimum.Restart schemes address how often to restart, attainable complexity, and the regularity properties governing performance.
6.1.1 The Strongly Convex Case: For strongly convex objectives, restarting fixed-step gradient descent changes the bound from sublinear to linear convergence even without knowing the strong-convexity parameter.The basic gradient method itself has no memory, so restart improves the complexity guarantee rather than its per-iteration numerical behavior.
6.3 Optimal Restart Schemes: When r > 2, optimal restart schedules use geometrically increasing inner-iteration counts, while constant schedules are optimal in the strongly convex case.The resulting bounds recover linear convergence when τ = 0 and are faster than accelerated methods for non-strongly convex functions when 0 < τ < 1.
6.4.1 Grid Search Complexity: A logarithmic grid search over restart parameters achieves nearly optimal performance without prior knowledge of the Hölderian error-bound parameters.It uses (log2 N)^2 restart schemes, with total complexity (log2 N)^2 times the parameter-known optimum and convergence slowed by roughly a factor four.
Hölder Smooth Gradient: The restart results extend to Hölder-smooth gradients, where the optimal convergence rate depends on the gradient’s smoothness exponent.For s ∈ [1, 2], the general class has an optimal rate bounded as O(1/N^ρ).
Hölder Smooth Gradient: For Hölder-smooth functions, the universal fast gradient method achieves rates governed by ρ = 2 in the smooth case and ρ = 1/2 in the non-smooth case.The method requires both a target accuracy ǫ and a starting point x0.
6.5. EXTENSIONS: The universal scheduled-restart extension combines geometrically decreasing target accuracies with selected run lengths to provide a final-iterate precision guarantee under Hölder smoothness and Hölderian error bounds.Its complexity depends on parameters including ρ, κ, and τ, with τ measuring the tightness of upper and lower bound models.
Relative Smoothness: Relative smoothness replaces Euclidean distance with a Bregman divergence, allowing the restart complexity results to accelerate proximal gradient methods.The construction uses a strongly convex reference function h and a Bregman-form Hölderian error bound.
6.6 Calculus Rules: Kurdyka-Łojasiewicz calculus rules estimate error-bound exponents for minima, compositions, and separable sums, with HEB exponent relation α = 1 − 1/r.Li and Pong (2018) provides the cited calculus rules, while Bolte et al. (2007) establishes the exponent correspondence.
6.7 Restarting Other First-Order Methods: Restart arguments extend to methods whose complexity depends directly on distance to optimality, including Frank-Wolfe through the strong Wolfe gap and its associated primal bound.The strong Wolfe primal bound upper-bounds the primal gap, unlike the lower-bound form of the Hölderian error bound.
6.7 Restarting Other First-Order Methods: Restarting Fractional Away-Step Frank-Wolfe achieves linear complexity for r = 2 and improved linear rates for 1 ≤ r < 2, fully adaptively without parameter knowledge or grid search.The result assumes a strong Wolfe primal bound and relates performance to away curvature.
6.8 Application: Compressed Sensing: Under the null space property, ℓ1 recovery guarantees signal optimality and a Hölderian error bound with µ = α−1, while compressed sensing gives r = 1 and computable µ.The null space property is necessary and sufficient for recovery up to a sparsity threshold.
6.9 Notes and References: Restart schemes trace to Nemirovsky and Nesterov (1985), achieve near-optimality through logarithmic grid searches, and also extend to stochastic algorithms with geometric step decay.Davis et al. (2019) shows linear convergence under Hölderian error bounds in the stochastic setting.

Appendices · Useful Inequalities

This appendix collects basic inequalities for smooth strongly convex functions, primarily to build intuition and support comparisons with the literature, although most are not used in the main developments.

Useful Inequalities: The appendix proves basic inequalities involving smooth strongly convex functions.These results are presented as useful background rather than core ingredients of the paper’s developments.
Useful Inequalities: Most of the inequalities are not used in the paper’s main developments.
Useful Inequalities: The inequalities provide intuition about smooth strongly convex functions and enable comparisons with the literature.
Useful Inequalities: These inequalities are standard, as noted with reference to Nesterov (2003, Theorem 2.1.5).

A.1 Smoothness and Strong Convexity in Euclidean spaces · A.2. SMOOTHNESS FOR GENERAL NORMS AND RESTRICTED SETS · Variations on Nesterov Acceleration

The section characterizes Euclidean smoothness and strong convexity through equivalent gradient and quadratic inequalities, including an interpolation inequality useful for worst-case analysis. It also extends smoothness to general norms and restricted convex domains while identifying domain-dependent limitations.

A.1 Smoothness and Strong Convexity in Euclidean spaces: For differentiable convex functions, several inequalities are equivalent characterizations of L-smoothness, although some encode convexity only when combined with an explicit convexity assumption.Theorem A.1 identifies equivalent conditions, while noting that conditions (iii) and (iv) encode both smoothness and convexity.
A.1. SMOOTHNESS AND STRONG CONVEXITY IN EUCLIDEAN SPACES: In Euclidean spaces, smoothness yields quadratic upper bounds, and conversely the resulting inequalities imply Lipschitz continuity of the gradient.The proof derives the quadratic upper bound from first-order expansion and concludes ∥∇f(x)−∇f(y)∥2 ≤L∥x−y∥2.
A.1. SMOOTHNESS AND STRONG CONVEXITY IN EUCLIDEAN SPACES: For closed convex proper functions, strong convexity adds inverse-Lipschitz gradient and quadratic lower-bound conditions to the corresponding smoothness inequalities.Theorem A.2 states equivalent conditions for membership in Fµ,L, including Lipschitz and inverse-Lipschitz gradient behavior and lower and upper quadratic bounds.
A.1. SMOOTHNESS AND STRONG CONVEXITY IN EUCLIDEAN SPACES: An interpolation inequality jointly encodes L-smoothness and µ-strong convexity and is particularly useful for proving worst-case guarantees.Theorem A.3 gives the if-and-only-if characterization of differentiable L-smooth µ-strongly convex functions.
A.2. SMOOTHNESS FOR GENERAL NORMS AND RESTRICTED SETS: Some Euclidean inequalities require dom f = Rd, whereas standard inequalities extend to restricted domains; additional twice-continuous differentiability can restore validity for certain exceptions.The restriction specifically affects Theorems A.1(iii–iv), A.2(iii–iv), and A.3, while Theorem A.1(iv) and A.2(iv) hold under the stated differentiability assumption.
A.2 Smoothness for General Norms and Restricted Sets: On an open convex set C, Lipschitz continuity of ∇f under any norm and its dual norm implies a quadratic upper bound on f over C.Theorem A.4 establishes this implication by first-order expansion and upper bounding the integral term.

B.1 Relations between Acceleration Methods · B.1.1 Optimized Gradient Method: Forms I & II · B.1.2 Nesterov’s Method: Forms I, II, and III

This section establishes equivalence among alternative formulations of the optimized gradient method and Nesterov’s method by showing that their generated sequences coincide. These reformulations therefore produce identical iterates despite differing algorithmic presentations.

B.1.1 Optimized Gradient Method: Forms I & II: Algorithms 9 and 10 generate identical {y_k} sequences, and consequently identical {x_k} sequences through gradient steps on {y_k}.Thus, the two optimized gradient method formulations produce the same iterates.
B.1.1 Optimized Gradient Method: Forms I & II: The optimized gradient method’s Form II is a reformulation of Form I, preserving the generated sequence {y_k}.The proof begins by showing identical initialization and algebraically reorganizes each iteration into Form II’s format.
B.1.1 Optimized Gradient Method: Forms I & II: The optimized gradient method equivalence follows by expressing z_k as θ_k,N y_k + (1 − θ_k,N)x_k and substituting this identity across iterations.Term reorganization yields the same update format as Algorithm 10.
B.1.2 Nesterov’s Method: Forms I, II, and III: Nesterov’s Forms I and II generate identical {x_k} and {y_k} sequences.Because both formulations obtain x_k through gradient steps on y_k, proving equality of the y_k sequences suffices.
B.1.2 Nesterov’s Method: Forms I, II, and III: The Nesterov Form I–II equivalence uses the identities A_{k+1} = a_k^2 + a_{k+1} and matching initialization at y_1 = x_0 − 1/L∇f(x_0).The proof then establishes equality inductively for subsequent iterations.
B.1.2 Nesterov’s Method: Forms I, II, and III: Nesterov’s Form III also generates the same z_k, x_k, and y_k sequences as Form I.The section states that the same relationship extends to Algorithm 13.

B.1. RELATIONS BETWEEN ACCELERATION METHODS · B.1.3 Nesterov’s Accelerated Gradient Method (Strongly Convex Case): Forms I, II, and III

The section establishes equivalence among several acceleration-method formulations by matching their iterates and update rules. For strongly convex Nesterov acceleration, it shows that Algorithms 14, 28, and 29 generate identical sequences.

B.1. RELATIONS BETWEEN ACCELERATION METHODS: The broader relations section proves that the compared acceleration methods produce the same iterates by induction from common initial values.After matching y_k and z_{k+1}, it simplifies the x_{k+1} update using the identity (A_{k+1} − A_k)^2 = A_{k+1}.
B.1.3 Nesterov’s Accelerated Gradient Method (Strongly Convex Case): Forms I, II, and III: The section presents Form II and Form III as alternate equivalent formulations of Algorithm 14.Both formulations retain the same approximate-solution output x_N while using different update representations.
B.1.3 Nesterov’s Accelerated Gradient Method (Strongly Convex Case): Forms I, II, and III: The strongly convex formulations take as input an L-smooth, µ-strongly convex function and initialize from x_0.Form II additionally initializes z_0 = x_0, q = µ/L, A_0 = 0, and A_1 = (1 − q)^−1.
B.1.3 Nesterov’s Accelerated Gradient Method (Strongly Convex Case): Forms I, II, and III: Algorithms 14 and 28 generate identical {x_k} and {y_k} sequences for Nesterov’s strongly convex method.The proof matches the initial values, gradient-step updates, and subsequent coefficients, using β_k = τ_{k+1}(δ_k − 1).
B.1.3 Nesterov’s Accelerated Gradient Method (Strongly Convex Case): Forms I, II, and III: The equivalence proof for Form II treats z_k as an auxiliary sequence and matches x_{k+1} as a gradient step from y_k.It then compares the y_{k+1} updates and reduces the remaining condition to the identity used to select A_{k+1}.
B.1.3 Nesterov’s Accelerated Gradient Method (Strongly Convex Case): Forms I, II, and III: Algorithms 14 and 29 generate identical {z_k}, {x_k}, and {y_k} sequences.The equivalence follows by verifying that the coefficient discrepancy vanishes under the definitions of β_k, τ_k, and δ_k.

B.2. CONJUGATE GRADIENT METHOD

The section establishes an exact connection between conjugate gradients and accelerated methods: CG and OGM admit identical worst-case proofs, while efficient CG implementations are specific to quadratic problems. Both achieve optimal worst-case complexity for smooth convex minimization under the stated condition.

B.2 Conjugate Gradient Method: CG and OGM share an identical worst-case analysis that achieves the lower bound for smooth convex minimization.The section presents their connection as exact, with both methods satisfying the condition that yields Theorem 4.7’s optimal complexity.
B.2 Conjugate Gradient Method: CG computes each iterate by minimizing over the affine span of the initial point and preceding gradients.This span-search formulation is given explicitly in Algorithm 30, which outputs y_N after N iterations.
B.2 Conjugate Gradient Method: For quadratic optimization, CG has an efficient implementation that avoids generally impractical span-searches, whereas no such efficient reformulation is generally available beyond quadratics.Other methods, including OGM, can retain the same worst-case analysis beyond quadratics, while Nesterov’s accelerated gradient follows from a weakened CG analysis.
B.2 Conjugate Gradient Method: CG enforces the key complexity condition through orthogonality of successive search directions, while OGM enforces it through its own update mechanism.The passages attribute CG’s guarantee to span-searches and identify OGM as another method satisfying the same condition.

Optimized and Conjugate Gradient Methods: Worst-case Analyses

The section applies the optimized-gradient-method potentials to worst-case analysis and states a theorem covering conjugate gradient and all methods satisfying (B.1). The guarantee is formulated for every initial point y0.

Optimized and Conjugate Gradient Methods: Worst-case Analyses: Theorem B.1 analyzes conjugate gradient (CG, Algorithm 30) and every method whose iterates satisfy (B.1).
Optimized and Conjugate Gradient Methods: Worst-case Analyses: The analysis assumes that f is an L-smooth convex function with a minimizer x⋆.
Optimized and Conjugate Gradient Methods: Worst-case Analyses: The resulting statement holds for all y0 ∈ R^d.

B.2. CONJUGATE GRADIENT METHOD · B.3 Acceleration Without Monotone Backtracking

The conjugate-gradient analysis derives the desired inequalities by weighted combinations of smoothness and convexity relations, selecting parameters to recover the OGM potential and final bound. It also connects this perspective to practical accelerated methods developed in prior work.

B.2. CONJUGATE GRADIENT METHOD: Weighted smoothness and convexity inequalities between y_{k−1}, y_k, and x⋆ form the basis of the conjugate-gradient proof.The construction uses weights λ1 = 2θ^2_{k−1,N} and λ2 = 2θ_{k,N}.
B.2. CONJUGATE GRADIENT METHOD: The weighted sum is a valid inequality that can be reformulated after substituting z_{k+1}.This reformulation provides the intermediate expression used to establish the desired inequality.
B.2. CONJUGATE GRADIENT METHOD: Choosing θ_{k,N} ≥ θ_{k−1,N} yields the same potential as in Theorem 4.4.The parameter choice completes the potential-based argument for the conjugate-gradient construction.
B.2. CONJUGATE GRADIENT METHOD: A second weighted combination of smoothness and convexity inequalities provides the technical lemma needed to bound f(y_N)−f⋆.Here the weights are λ1 = 2θ^2_{N−1,N} and λ2 = θ_{N,N}.
B.2. CONJUGATE GRADIENT METHOD: Selecting θ_{N,N} ≥ θ_{N−1,N} yields the desired inequality and allows the potential argument from Corollary 4.6 to apply.The conclusion follows by chaining the resulting inequalities.
B.2. CONJUGATE GRADIENT METHOD: The conjugate-gradient viewpoint has been used to design practical accelerated methods in settings such as Nesterov (1983).Related developments include (Karimi and Vavasis, 2016; Karimi and Vavasis, 2017; Diakonikolas and Orecchia, 2019a), while the CG–OGM link is due to Drori and Taylor (2020).

B.3.1 FISTA without Monotone Backtracking

This section extends FISTA to backtracking sequences that may decrease, while preserving the potential-based analysis and complexity guarantees. The method uses the current approximate Lipschitz constant at each iteration and incorporates prior estimates through the potential scaling.

B.3.1 FISTA without Monotone Backtracking: FISTA can accommodate nonmonotone backtracking by rescaling the potential so L_k enters only through B_k.This modification applies to both backtracking methods discussed earlier.
B.3.1 FISTA without Monotone Backtracking: Each iteration uses only the current estimate L_{k+1}, while previous estimates affect the computation only through B_k.The updates replace A_k by L_{k+1}B_k and A_{k+1} by L_{k+1}A_{k+1}.
B.3.1 FISTA without Monotone Backtracking: Algorithm 31 provides strongly convex FISTA with general initialization of L_{k+1}, accepting iterates when the backtracking condition holds.It assumes an L-smooth convex function, optionally μ-strongly convex, a proximable convex h, and L_0 > μ.
B.3.1 FISTA without Monotone Backtracking: Theorem B.2 establishes the resulting iterate inequality for accepted iterates under full-domain smoothness and convexity assumptions.Its proof combines weighted strong-convexity, smoothness, and convexity inequalities for f and h.
B.3.1 FISTA without Monotone Backtracking: The potential argument yields a smooth-convex complexity guarantee because B_{k+1} decreases with L_{k+1}, while the growth rate of B_k remains unchanged.Corollary B.3 states the corresponding guarantee for any N ≥ 1 under the full-domain assumptions.

B.3.2 Another Accelerated Method without Monotone Backtracking · On Worst-case Analyses for First-order Methods · C.1 Principled Approaches to Worst-case Analyses

The section develops Algorithm 32, a proximal accelerated method using non-monotone Lipschitz estimates, and establishes its convergence through a potential-based proof. It then frames worst-case convergence analysis as finding feasible points of linear matrix inequalities, connecting this viewpoint to related performance-estimation and control-theoretic approaches.

B.3.2 Another Accelerated Method without Monotone Backtracking: Algorithm 32 extends FISTA-style acceleration by incorporating non-monotone estimates of the Lipschitz constant, with an essentially unchanged proof structure.
B.3.2 Another Accelerated Method without Monotone Backtracking: Theorem B.4 provides the central convergence inequality for Algorithm 32 under its acceptance condition and proximal initialization.
B.3.2 Another Accelerated Method without Monotone Backtracking: The algorithm preserves feasibility because proximal updates remain in dom h, while subsequent iterates are convex combinations of feasible points.
B.3.2 Another Accelerated Method without Monotone Backtracking: Its proof combines weighted strong-convexity, convexity, smoothness, and proximal-function inequalities, with weights determined by successive B_k values.
B.3.2 Another Accelerated Method without Monotone Backtracking: Corollary B.5 gives the final convergence bound for Algorithm 32, with ℓ = max{αL, L_0}.
C.1 Principled Approaches to Worst-case Analyses: Worst-case convergence guarantees can be formulated as feasible points of linear matrix inequalities, yielding a principled analysis framework for gradient and accelerated methods.The section provides a full base-case derivation, examples for selected methods, pointers to related literature, and notebooks for corresponding LMIs.
C.1 Principled Approaches to Worst-case Analyses: The LMI viewpoint is related to performance-estimation methods and to control-theoretic integral quadratic constraints, which are largely analogous and often dual in formulation.The presentation draws on Taylor and Bach (2019), Taylor, Hendrickx and Glineur (2017), Drori and Teboulle (2014), and Lessard, Recht and Packard (2016), among others.

C.2. WORST-CASE ANALYSIS AS OPTIMIZATION/FEASIBILITY PROBLEMS · C.3 Analysis of Gradient Descent via Linear Matrix Inequalities · C.3.1 Linear Convergence of Gradient Descent

The section frames worst-case guarantees as optimization or feasibility problems, then develops LMIs for gradient descent and uses them to characterize one-step linear convergence.

C.2. WORST-CASE ANALYSIS AS OPTIMIZATION/FEASIBILITY PROBLEMS: Performance estimation selects inequalities from the worst-case definition so that either a desired guarantee is certified or a counterexample invalidates it.Worst-case analysis and feasibility verification are presented as two facets of the same underlying approach.
C.2 Worst-case Analysis as Optimization/Feasibility Problems: Worst-case scenarios for first-order methods can be formulated as convex linear semidefinite programs, whose dual feasible points certify upper bounds through weighted inequalities.The dual multipliers provide the weights in convergence proofs.
C.2 Worst-case Analysis as Optimization/Feasibility Problems: The LMI construction scales its dual variables with the number of points requiring function or gradient evaluations, giving n(n −1) variables for n points.The basic gradient-descent example uses two dual variables because it evaluates gradients at xk and x⋆.
C.2. WORST-CASE ANALYSIS AS OPTIMIZATION/FEASIBILITY PROBLEMS: Changing the Lyapunov or potential function changes the LMI, which can be solved numerically to guide the selection of analytical weights.The displayed LMIs are presented in raw form, while weaker sufficient versions may be easier to solve analytically.
C.3 Analysis of Gradient Descent via Linear Matrix Inequalities: The gradient-descent analysis provides full details for deriving LMIs, while accelerated-method analyses use the same technique more briefly.The section’s examples illustrate how LMIs are obtained for worst-case guarantees.
C.3.1 Linear Convergence of Gradient Descent: For smooth strongly convex functions, gradient descent is analyzed through a one-iteration worst-case guarantee measuring distance to an optimum.The iteration is xk+1 = xk −γk∇f(xk), with f L-smooth and µ-strongly convex and ∇f(x⋆) = 0.
C.3.1 Linear Convergence of Gradient Descent: The smallest valid convergence factor τ⋆ is defined by an optimization over worst-case scenarios and admits an equivalent linear semidefinite-program formulation.τ⋆ omits dependence on γk, µ, and L for convenience.

C.3. ANALYSIS OF GRADIENT DESCENT VIA LINEAR MATRIX INEQUALITIES … C.5. NOTES AND REFERENCES

The section reformulates worst-case analyses of gradient and accelerated methods as semidefinite programs using interpolation inequalities, then surveys related LMI/SDP frameworks, optimized methods, applications, and reproducible solution tools.

C.3. ANALYSIS OF GRADIENT DESCENT VIA LINEAR MATRIX INEQUALITIES: Gradient-descent analysis samples function values and gradients, replaces interpolation existence with quadratic inequalities, and derives an equivalent convex semidefinite reformulation linear in G and F.Homogeneity permits normalization G1,1 = 1, after which Lagrangian duality yields the desired LMI; strong duality follows from a Slater point.
C.3. ANALYSIS OF GRADIENT DESCENT VIA LINEAR MATRIX INEQUALITIES: The dual reformulation directly proves Theorem C.1, providing both sufficient upper bounds and necessary worst-case instances through weak and strong duality.Other inequalities can be analyzed by changing the objective, while analytical LMI solutions may require numerical inspiration in complicated cases.
C.3. ANALYSIS OF GRADIENT DESCENT VIA LINEAR MATRIX INEQUALITIES: Weaker LMIs based on necessary but insufficient interpolation inequalities simplify analytical solutions but lose a priori tightness and can miss otherwise attainable guarantees.This tradeoff is also discussed for IQC-based analyses, whereas tight guarantees and Lyapunov or potential functions can sometimes be sought simultaneously.
C.3.2 Potential Function for Gradient Descent: Verifying a gradient-descent potential function uses the same sampled-function reformulation with three points—x⋆, xk, and xk+1—and six dual variables.The resulting LMI certifies φk+1 ≤ φk over all dimensions, functions in Fµ,L, and compatible iterates; a symbolic-computation notebook is provided.
C.4 Accelerated Gradient Descent via Linear Matrix Inequalities: Accelerated-gradient potential verification follows the same SDP construction with four samples—x⋆, xk, xk+1, and yk—and includes the µ = 0 case via Theorem C.3.The maximum is taken over the dimension, function, iterates, and optimum while checking φk+1 ≤ φk.
C.5 Notes and References: The notes trace SDP/LMI worst-case analysis from Drori and Teboulle (2014) and Taylor et al. (2017c), through IQC links, extensions, and the PESTO toolbox.The approaches have been applied to gradient, accelerated, nonsmooth, stochastic, coordinate-descent, nonconvex, proximal, splitting, monotone-inclusion, fixed-point, and distributed optimization.
C.5 Notes and References: Optimized gradient methods originated from SDP/LMI worst-case optimization in Drori and Teboulle (2014), with later analytical and Lyapunov-based recoveries including OGM and TMM.Optimized methods were also developed for gradient norms, fixed-point iterations, and monotone inclusions.
C.5. NOTES AND REFERENCES: Standard semidefinite-optimization packages solve the LMIs, while provided notebooks support symbolic formulation, numerical solution, and reproducibility.The notebooks are available at the monograph’s cited GitHub repository.