Source-linked AI summary
Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
Adrien B. Taylor, Julien M. Hendrickx, François Glineur
TL;DR
The paper addresses how to obtain exact worst-case performance guarantees for broad oracle-based first-order methods on composite convex problems. It extends performance estimation through convex interpolation and semidefinite programming, producing tight guarantees and attaining instances. The resulting analyses improve bounds for several algorithms, including a proximal optimized gradient method with roughly twice better worst-case performance than fast proximal-gradient variants.
Problem
Exact worst-case guarantees and matching instances are sought for broad oracle-based first-order methods solving composite convex optimization problems.
Method
The framework combines convex interpolation conditions with a tractable semidefinite-program formulation of worst-case performance for composite objectives and first-order methods.
Results
The paper gives a new proximal-point guarantee twice better than previously known, improves the conditional-gradient guarantee by more than a factor of two, and extends optimized gradient with projection or a proximal operator.
Takeaways & Limitations
The framework provides tight analyses and explicit worst-case instances for a broad range of composite first-order methods, including projected, proximal, conditional, and inexact subgradient schemes.
Takeaways & Limitations
The tractable semidefinite-program formulation relies on the large-scale assumption; without it, the performance-estimation problem is generally a rank-constrained, NP-hard problem.
Abstract
from arXiv · showhide
We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this worst-case. We achieve this by reducing the computation of the worst-case to solving a convex semidefinite program, generalizing previous works on performance estimation by Drori and Teboulle [13] and the authors [43]. We use these developments to obtain a tighter analysis of the proximal point algorithm and of several variants of fast proximal gradient, conditional gradient, subgradient and alternating projection methods. In particular, we present a new analytical worst-case guarantee for the proximal point algorithm that is twice better than previously known, and improve the standard worst-case guarantee for the conditional gradient method by more than a factor of two. We also show how the optimized gradient method proposed by Kim and Fessler in [22] can be extended by incorporating a projection or a proximal operator, which leads to an algorithm that converges in the worst-case twice as fast as the standard accelerated proximal gradient method [2].
1. Introduction.
The paper extends performance estimation to composite convex optimization and broad oracle-based first-order methods, aiming to compute exact worst-case guarantees alongside attaining instances. Its framework uses convex interpolation and semidefinite programming to analyze methods including projected, proximal, conditional, and inexact subgradient schemes.
- Motivation: Composite convex optimization represents constrained and regularized problems while allowing algorithms to exploit problem structure.The framework covers examples including constrained, ℓ1-regularized, and ℓ2-regularized convex optimization problems.
- Problem and scope: The study targets exact global worst-case guarantees and corresponding optimization instances for fixed-step linear first-order methods.The considered methods include fixed-step projected, proximal, conditional, and inexact (sub)gradient methods.
- Framework extension: The framework generalizes earlier performance-estimation work from single smooth convex objectives to multiple composite components and broader function classes.It supports standard first-order oracles and extends the framework to composite objectives with multiple functional components.
- Performance estimation: Performance estimation reduces worst-case analysis to a tractable semidefinite program whose feasible solutions provide bounds and explicit instances.Primal feasible solutions yield lower bounds through instances, while dual feasible solutions yield upper bounds and proof certificates.
- Interpolation: Convex interpolation conditions cover function classes with smoothness, strong convexity, bounded domains, bounded subgradients, indicator functions, and support functions.These conditions eliminate infinite-dimensional functional variables from the performance estimation problem and enable tractable formulations.
- Applications: The approach is applied to concrete algorithms, improving analyses of methods such as the proximal point, conditional gradient, and proximal-gradient algorithms.The applications include an optimized-gradient extension incorporating projection or a proximal operator for constrained and composite problems.
2. Performance estimation framework for first-order algorithms.
The framework encodes first-order optimization information in function-value and Gram-matrix variables, enabling tractable worst-case analysis through Gram-representability and semidefinite programming. Under a sufficiently large dimension, this formulation is exact and yields worst-case-achieving instances.
- Gram representations: The framework gathers iterates and oracle outputs into a Gram matrix whose size is independent of the ambient dimension.The matrix records inner products among iterates, the optimum, and oracle outputs.
- Gram representations: Gram-representability expresses interpolation, method, performance, and initialization conditions using convex constraints on the Gram matrix and function values.Linear Gram-representability specializes these constraints to linear ones.
- Supported classes and criteria: The framework covers linearly Gram-representable smooth, strongly convex, bounded-gradient, bounded-domain, support, and indicator function classes.It also handles standard function-value, residual-norm, and best-iterate performance measures.
- Tractable formulation: When d ≥ (n+1)(N+2), the worst-case problem is convex; otherwise, it includes the nonconvex constraint Rank GN ≤ d.The rank constraint is generally difficult to solve globally.
- Tractable formulation: For linearly Gram-representable objectives, methods, criteria, and initializations, worst-case computation becomes an SDP in FN and GN.The formulation uses FN ∈ R^n(N+2) and GN ∈ S^(n+1)(N+2) as variables.
- Exactness and scope: A worst-case-achieving function exists in dimension at most (n+1)(N+2), and the resulting guarantees are dimension-free under the large-scale assumption.The dimension bound is typically conservative for standard algorithms.
3. Convex interpolation.
The section develops interpolation conditions for several convex-function classes so their performance-estimation formulations remain tractable and tight.
- Interpolation framework: The framework characterizes finite sets of points, subgradients, and function values that can be interpolated by functions in specified convex classes.Interpolation requires a function reproducing both the listed function values and subgradients.
- Function classes: The considered classes combine smoothness, strong convexity, gradient boundedness, and domain boundedness under compatible parameterizations.The paper excludes incompatible combinations such as gradient boundedness with strong convexity and domain boundedness with smoothness.
- Duality: Conjugate duality converts interpolation between smoothness and strong convexity, and between gradient and domain boundedness, into corresponding dual conditions.These correspondences are used to derive interpolation conditions for bounded-gradient classes.
- Indicator functions: Indicator-function interpolation requires additional care because imposing zero function values does not automatically ensure that the interpolated function vanishes throughout its domain.Indicator functions are relevant because their proximal steps equal projections onto their domains.
- Performance estimation: The resulting interpolation conditions are linearly Gram-representable, enabling tractable performance-estimation formulations with tightness guarantees.This is the stated motivation for using the selected function classes in the performance-estimation framework.
- Nonconvex extension: The interpolation development also covers smooth nonconvex functions and produces conditions usable for tight nonconvex performance-estimation problems.The smooth nonconvex conditions are likewise linearly Gram-representable.
4. Algorithm analysis.
The algorithm-analysis section introduces a simple model containing one convex, possibly nonsmooth objective term.
- Model problem: The first algorithm-analysis example considers an objective with only one convex, possibly nonsmooth term.
4.1. A proximal point algorithm.
The proximal point algorithm is represented as an implicit first-order method, and the performance-estimation framework yields tight convergence guarantees with one-dimensional worst-case instances.
- Algorithm representation: A proximal step for a convex function can be written as an implicit subgradient step, placing the proximal point algorithm within the fixed-step linear first-order-method class.The implicit form uses a subgradient evaluated at the next iterate.
- Function-value convergence: The PEP analysis halves the standard proximal-point function-value convergence bound for any positive step-size sequence and initial distance bounded by R.The improved bound applies in the general inner-product setting considered by the framework.
- Tightness: The improved function-value bound is unimprovable, even in one dimension.A one-dimensional l1-shaped function attains the bound.
- Residual subgradient: The residual-subgradient analysis conjectures a bound for some subgradient at every iterate of the proximal point algorithm.The conjecture is supported by numerical evidence from a related performance-estimation problem.
- Interpretation: The residual-subgradient measure is relevant to dual methods because dual residual gradient norms correspond to primal distances to feasibility.
4.2. Fast gradient methods.
The section compares fast proximal gradient variants across unconstrained, constrained, and nonsmooth composite settings, introducing FPGM2 and POGM-related numerical analysis. FPGM2 avoids feasibility and boundedness issues associated with FPGM1's secondary sequence while achieving slightly better worst-case guarantees.
- FPGM methods are evaluated for smooth unconstrained, constrained, and nonsmooth composite convex minimization.The comparison uses FPGM1 and FPGM2 across the three cases.
- FPGM2 is introduced as a variant with slightly better guarantees than standard FPGM1.The study also introduces two inertial-parameter policies for FPGM2.
- After 100 iterations, the two FPGM1 inertial policies behave about the same, and their behavior is well captured by the standard guarantee.For FPGM2, α(b) performs slightly better than α(a).
- FPGM1's secondary sequence can become infeasible for constrained problems or have unbounded objective values for proximal problems.These drawbacks motivate the design of FPGM2.
- The finite convergence results correspond to identified worst-case functions and are conjectured to equal the exact guarantees for L = R = 1 and 1 ≤ N ≤ 100.The functions provide rigorous lower bounds for the reported finite results.
- Numerically identified worst-case functions include Huber-shaped functions for the unconstrained case and one-dimensional linear constructions for constrained and proximal cases.The proximal construction uses a linear smooth component and a piecewise-linear nonsmooth component.
4.3. A proximal optimized gradient method.
The section extends optimized gradient ideas to composite problems by proposing POGM, which combines OGM with FPGM2's proximal-operator placement. POGM improves worst-case performance numerically but requires the iteration count in advance.
- POGM combines OGM ideas with FPGM2's nonstandard proximal-operator placement for composite optimization.Its design preserves OGM behavior in the smooth unconstrained case and stays at an optimal point once reached.
- A standard proximal placement for generalizing OGM does not yield a converging algorithm, motivating FPGM2-style proximal placement.Numerical worst-case functions show that the candidate bound does not decrease after each iteration.
- POGM has worst-case performances about twice better than FPGM1 and FPGM2 between 1 and 100 iterations.The comparison is numerical and uses the worst-case performances shown in Fig. 2.
- POGM is approximately 12% worse than OGM in the smooth unconstrained worst-case.POGM is equivalent to OGM when F (2) = 0.
- POGM requires the number of iterations in advance because its final coefficient uses a different rule.Updating the final coefficient by the ordinary rule degrades performance by a nonnegligible factor.
4.4. A conditional gradient method.
The conditional gradient method is analyzed through the performance-estimation framework without requiring projections onto the constraint set. Its numerical worst-case guarantees are between two and three times better than the standard guarantee.
- The conditional gradient method avoids projections onto a bounded closed convex set by performing linear optimization instead.The method is also known as the Frank–Wolfe method.
- Numerical guarantees from performance estimation are between two and three times better than the standard guarantee through 100 iterations.The comparison uses the exact bound provided by PEP in Fig. 3(a).
- The analysis compares the standard conditional gradient method with its PEP-derived worst-case bound.The method fits the fixed-step linear first-order method format.
4.5. Alternate projection and Dykstra methods.
The section applies performance estimation to alternating projection and Dykstra methods for finding points in intersections of convex sets. Both exhibit the expected O(1/√N) behavior, while APM has a smaller worst-case than DAPM under the stated assumptions.
- APM and DAPM are analyzed for finding, respectively, an intersection point and the closest point in the intersection of two convex sets.APM is a subgradient-type method in this formulation.
- Both methods show the expected O(1/√N) convergence behavior.The performance measure is the distance from the final iterate to the first convex set.
- DAPM has a worst-case about 18% larger than APM, making APM more advisable when no additional structure is assumed.This comparison concerns worst-case performance for finding a point in the intersection.
- Both APM and DAPM have worst-cases about twice better than the standard lower bound for explicit nonsmooth schemes.The comparison uses the standard subgradient lower bound as reference.
- The broader framework extends performance estimation to larger classes of composite objectives and first-order algorithms.The paper applies the approach to alternating projection methods among other algorithms.
5. Conclusion.
The paper develops a methodology for exact worst-case analysis of fixed-step first-order methods and applies it to sharpen several algorithmic guarantees. It also identifies extensions to dynamic step sizes and easier-to-solve performance-estimation programs as future directions.
- The methodology combines interpolation conditions, exact worst-case formulations, and tight analyses for fixed-step linear first-order methods.
- The proximal point guarantee is twice better than previously known, while the conditional gradient guarantee improves by more than a factor of two.
- Future work includes refining analyses of fixed-step methods and extending the methodology to dynamic step-size rules, including line-search procedures.
- Performance-estimation analyses are limited by the numerical and analytical difficulty of solving semidefinite programs, especially for many iterations.
- An easy-to-use MATLAB implementation of the approach is available in the Performance-Estimation-Toolbox.