Finite Step Performance of First-order Methods Using Interpolation Conditions Without Function Evaluations

Bruce Lee, Peter SeilerarXiv 2020 · arXiv

Introduction

Determining the worst-case performance of first-order optimization algorithms is a fundamental task in algorithm design. While tools like the Performance Estimation Problem (PEP) offer exact bounds, they typically require tracking function values ($f_i$) in addition to gradients ($\nabla f_i$). For many algorithms and metrics, function values are extraneous, yet "gradient-only" interpolation conditions have historically faced a "factorial explosion" of constraints ($N!$), rendering them computationally intractable for more than a few steps. This paper introduces a method to bypass this complexity, enabling exact performance analysis using only gradient information.

Efficient Interpolation via Doubly Hyperdominant Matrices

The core contribution of this work is a mathematical framework that reduces the number of constraints required for gradient-only interpolation from $O(N!)$ to $O(N^2)$. By leveraging the properties of doubly hyperdominant matrices, the authors condense the cyclic monotonicity requirements into a single Semidefinite Program (SDP). This transformation relies on the Birkhoff/von-Neumann decomposition, which links permutation matrices—the source of factorial growth—to doubly stochastic and hyperdominant matrices.

The resulting workflow represents the algorithm as a linear time-varying system and applies the S-procedure to derive a Linear Matrix Inequality (LMI). Solving this SDP yields the smallest possible performance bound $b$ for a given class of functions, such as $m$-strongly convex functions with $L$-Lipschitz continuous gradients ($S_{m,L}$).

Performance Analysis of the Heavy-Ball Method

The authors validate their approach by analyzing the Heavy-Ball algorithm, comparing finite-step results against asymptotic convergence rates. The method accurately distinguishes between convergent and divergent regimes based on the condition number $L/m$.

Finite step vs. asymptotic performance bounds for the Heavy-Ball algorithm in convergent (top) and divergent (bottom) regimes.

As illustrated in Figure 1, the finite-step bounds (represented by blue markers) align closely with the tighter asymptotic bounds (the $T=3$ red line) as the number of steps $N$ increases. In the convergent case ($L/m < 9 + 4\sqrt{5}$), the bounds decrease with $N$, while in the divergent case ($L/m > 9 + 4\sqrt{5}$), the bounds grow, correctly identifying the algorithm's failure to converge under those parameters. This demonstrates a clear bridge between short-term finite-step analysis and long-term stability.

Conclusion and Future Directions

This research provides a numerically tractable way to obtain exact performance bounds for first-order methods without needing function evaluations. While currently restricted to unconstrained optimization of strongly convex functions, the efficiency gains from $O(N!)$ to $O(N^2)$ open new avenues for algorithm analysis. Future work may extend this "gradient-only" approach to broader function classes, constrained problems, or non-smooth optimization. Additionally, the high accuracy of low-order asymptotic approximations (e.g., $T=3$) warrants further investigation into their underlying effectiveness.

Summary updated

Abstract

We present a procedure to numerically compute finite step worst case performance guarantees on a given algorithm for the unconstrained optimization of strongly convex functions with Lipschitz continuous gradients. The solution method provided serves as an alternative approach to that derived by Taylor, Hendrickx, and Glineur in [Math. Prog. 161 (1-2), 2017]. The difference lies in the fact that our solution uses conditions for the interpolation of a set of points and gradient evaluations by the gradient of a function in the class of interest, whereas their solution uses conditions for the interpolation of a set of points, gradient evaluations, and function evaluations by a function in the class of interest. The motivation for this alternative solution is that, in many cases, neither the algorithm nor the performance metric of interest rely upon function evaluations. The primary development is a procedure to avoid suffering from the factorial growth in the number of these conditions with the size of the set to be interpolated when solving for the worst case performance.
BibTeX
@misc{lee2020finite,
  author = {Bruce Lee and Peter Seiler},
  title = {{Finite Step Performance of First-order Methods Using Interpolation Conditions Without Function Evaluations}},
  year = {2020},
  eprint = {2005.01825},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.01825},
}
Figure