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$.
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