Source-linked AI summary
Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods
Adrien B. Taylor, Julien M. Hendrickx, François Glineur
TL;DR
The paper asks how to determine exact finite-iteration worst-case performance for fixed-step black-box first-order methods on smooth convex function classes. It develops constructive interpolation conditions and an equivalent semidefinite formulation, yielding exact worst-case values together with functions that attain them. Numerical applications generate worst-case conjectures and tight gradient-method step-size estimates.
Problem
Exact numerical worst-case performance is usually unknown because method-specific upper and lower bounds can leave a substantial gap.
Method
The paper derives necessary and sufficient smooth strongly convex interpolation conditions and reformulates performance estimation as an equivalent finite-dimensional semidefinite optimization problem.
Results
The constructive formulation provides exact worst-case guarantees and explicit functions reaching them, while numerical tests support bounds and optimal step-size estimates for several fixed-step methods.
Takeaways & Limitations
Performance estimation becomes a unified tool for analyzing fixed-step first-order methods on smooth convex and smooth strongly convex functions.
Takeaways & Limitations
Exact worst-case values require solving a semidefinite program whose size grows quadratically with the iteration count, potentially becoming prohibitive for large iteration counts.
Abstract
from arXiv · showhide
We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop closed-form necessary and sufficient conditions for smooth (strongly) convex interpolation, which provide a finite representation for those functions. This allows us to reformulate the worst-case performance estimation problem as an equivalent finite dimension-independent semidefinite optimization problem, whose exact solution can be recovered up to numerical precision. Optimal solutions to this performance estimation problem provide both worst-case performance bounds and explicit functions matching them, as our smooth (strongly) convex interpolation procedure is constructive. Our works build on those of Drori and Teboulle in [Math. Prog. 145 (1-2), 2014] who introduced and solved relaxations of the performance estimation problem for smooth convex functions. We apply our approach to different fixed-step first-order methods with several performance criteria, including objective function accuracy and gradient norm. We conjecture several numerically supported worst-case bounds on the performance of the fixed-step gradient, fast gradient and optimized gradient methods, both in the smooth convex and the smooth strongly convex cases, and deduce tight estimates of the optimal step size for the gradient method.
1 Introduction to performance estimation
The paper addresses the difficulty of determining exact finite-iteration worst-case performance for black-box first-order methods by formulating it as an exact finite-dimensional convex optimization problem. Its framework unifies smooth convex and smooth strongly convex functions, supports multiple criteria, and produces matching worst-case functions.
- The framework targets uncertainty caused by gaps between upper and lower performance bounds for specific first-order methods.Such gaps can create substantial uncertainty about concrete method behavior.
- Exact finite-iteration worst-case performance is formulated and solved as a finite-dimensional convex optimization problem.The work explicitly focuses on exact values rather than asymptotic convergence rates.
- The exact formulation becomes a semidefinite optimization problem whose dimension grows proportionally to the square of the iteration count.Dual feasible solutions yield upper bounds, while primal feasible solutions yield lower bounds on worst-case performance.
- Optimal solutions can be converted into concrete functions exhibiting the corresponding performance, making the formulation exact.The constructive interpolation procedure also supports explicit worst-case functions.
- The formulation unifies smooth convex and smooth strongly convex functions and accommodates many fixed-step first-order methods and performance criteria.Examples include objective function accuracy, gradient norm, and distance to an optimal solution.
- The performance estimation problem is represented through interpolation constraints and an equivalent finite-dimensional formulation.The interpolation constraint requires the sampled points, gradients, and function values to come from a function in the target class.
- Numerical tests cover gradient, fast gradient, and optimized gradient methods and produce conjectures on worst-case bounds and optimal gradient-method step sizes.The tests include smooth convex and smooth strongly convex settings and criteria involving objective accuracy and gradient norms.
2 Smooth strongly convex interpolation
The paper develops necessary and sufficient conditions for smooth strongly convex interpolation, enabling finite exact reformulations of performance estimation problems.
- Definitions and problem statement: Smooth strongly convex interpolation asks whether data triples (x_i, g_i, f_i) can be realized by a function with matching values and subgradients.The function class combines Lipschitz-gradient smoothness with strong convexity.
- Necessity and sufficiency of conditions for smooth convex interpolation: Naively discretizing conditions valid on the whole domain is insufficient: it may accept data that no smooth convex function interpolates.Such relaxations can produce only upper bounds in performance estimation.
- Necessity and sufficiency of conditions for smooth convex interpolation: The one-dimensional data pair (−1, −2, 1) and (0, −1, 0) satisfies sampled conditions with L = 1 but has unavoidable nondifferentiability at x1.Therefore, those conditions do not guarantee smooth convex interpolation.
- Convex interpolation: The paper first constructs a necessary and sufficient interpolation characterization for general convex functions, using a constructive piecewise-linear interpolant.This convex interpolation result is then used as a building block for the smooth strongly convex case.
- Smooth strongly convex interpolation: Theorem 4 gives necessary and sufficient pairwise conditions for a finite set of triples to be F_µ,L-interpolable.The framework also yields corresponding conditions for smooth convex and nonsmooth strongly convex special cases.
- Extensions: The interpolation framework extends to finite and continuous integration problems without function values by summing inequalities over cyclic sequences.This provides interpolation conditions for integrated gradient information.
3 A convex formulation for performance estimation
The paper converts fixed-step performance estimation into a dimension-independent semidefinite program using interpolation conditions and a Gram matrix, with primal and dual solutions retaining exact worst-case meaning.
- 3 A convex formulation for performance estimation: Performance estimation is expressed using only iterates, gradients, function values, and an optimal point, constrained by the interpolation theorem.Translation and function-value invariances allow x* = 0, f* = 0, and g* = 0 without loss of generality.
- 3 A convex formulation for performance estimation: For fixed-step methods, the nonconvex performance problem becomes a convex semidefinite program because the Gram matrix constraint is convex.The original formulation contains nonconvex quadratic constraints, which the reformulation replaces with semidefinite structure.
- 3.1 Fixed-step first-order methods: Fixed-step methods generate iterates by adding gradients with fixed scalar coefficients, including the gradient and fast gradient methods.An N-step method is encoded by a lower triangular N × N coefficient matrix H.
- 3.2 A convex reformulation using a Gram matrix: A symmetric positive semidefinite Gram matrix represents inner products among the initial iterate and gradients, eliminating dependence on the ambient dimension.Its entries suffice to formulate the constraints together with function values.
- 3.3 Exact worst-case performance of fixed-step first-order methods as a semidefinite program: When N ≤ d − 2, the semidefinite program exactly equals the worst-case performance for linear performance criteria involving function values and quadratic iterate or gradient terms.For any d ≥ N + 2, its optimum gives the exact worst-case value.
- 3.3 Exact worst-case performance of fixed-step first-order methods as a semidefinite program: The dimension-independent formulation is exact in the large-scale setting, and the worst case is achieved by an N + 2-dimensional function.For smaller dimensions, exactness is recovered by adding the nonconvex constraint rank G ≤ d.
- 3.4 A dual semidefinite program to generate upper bounds: Dual feasible solutions yield theoretical upper bounds and explicit proofs, while primal feasible solutions yield lower bounds on worst-case performance.Under the stated assumptions, strong duality and attainment follow from Slater’s condition.
- 3.6 A simple example: A dual solution can be converted into a fully explicit, independently checkable proof of the worst-case performance.The proof is represented by valid inequalities associated with dual feasibility.
4 Numerical performance estimation of standard first-order algorithms
The exact performance-estimation formulation is applied to gradient, fast-gradient, and optimized-gradient methods, yielding numerically supported worst-case conjectures and step-size estimates. Experiments also compare last-iterate and best-iterate gradient-norm behavior.
- Gradient method: The gradient method’s smooth convex worst case is conjectured to be attained by either f1 or f2, depending on the normalized step size and iteration count.f1 produces non-overshooting approach, whereas f2 produces oscillation around the optimum.
- Gradient method: The optimal gradient-method step size increases with N, satisfies 3/2 ≤ hopt(N) < 2, and tends to 2 as N →∞.Using hopt(N) instead of h = 1 is predicted to improve the asymptotic worst-case bound by a factor of 2.
- Fast and optimized gradient methods: For FGM and OGM, numerical results support separate conjectures for primary and secondary iterates, improving transient worst-case estimates by approximately 1.15 after 30 iterations.The asymptotic behaviors remain well captured by the existing analytical bounds.
5 Conclusion
The paper develops a generic performance estimation framework that computes exact worst-case guarantees and explicit matching functions for fixed-step first-order methods. Its main limitations are computational growth with iteration count and incomplete coverage of more general algorithmic settings.
- The paper presents necessary and sufficient conditions for smooth strongly convex interpolation through an explicit construction of interpolating functions.
- Exact worst-case performance for fixed-step first-order algorithms can be formulated as a convex problem, with interpolation providing explicit functions that attain the computed bounds.
- The approach suggests tight estimates of the gradient method's optimal constant step size depending on iteration count and condition number.
- The performance estimation problem provides a unified tool for analyzing smooth convex and smooth strongly convex functions across fixed-step first-order methods.
- The exact semidefinite program grows quadratically with the number of iterations, potentially becoming prohibitive; iteration-independent bounds avoid this cost but weaken guarantees.
- Future extensions include line-search and projected-gradient methods, as well as optimizing step sizes within the performance estimation formulation.