TL;DR
PEPit is a Python package that automates the worst-case analysis of first-order optimization algorithms by casting the analysis as a solvable Semidefinite Program (SDP). It allows researchers to rigorously verify convergence rates and discover tight performance bounds for complex algorithms using code that looks almost identical to a standard implementation.
What Problem Does This Paper Address?
In the world of numerical optimization, first-order methods (like Gradient Descent or Nesterov’s Accelerated Gradient) are ubiquitous due to their low computational cost per iteration. However, proving how fast these methods converge—especially in the "worst-case"—is a notoriously difficult task.
Traditionally, these analyses are done manually by experts using pencil-and-paper proofs involving complex inequalities. This process is not only tedious and error-prone but often results in bounds that are not "tight" (meaning the algorithm might actually perform better than the proof suggests). PEPit addresses this gap by providing a "computer-assisted" framework that makes rigorous, tight worst-case analysis accessible to anyone who can write basic Python code.
Methods
The package is built on the Performance Estimation Problem (PEP) framework. The core idea is to treat the search for a worst-case scenario as an optimization problem itself:
- Objective: Maximize a performance measure (e.g., the distance to the optimum after $n$ steps).
- Constraints: The function must belong to a specific class (e.g., $L$-smooth and convex), and the steps must follow a specific algorithm.
To make this tractable, PEPit uses interpolation conditions. These mathematical theorems allow the package to represent an infinite-dimensional search over all possible functions using only a finite set of points and gradients. This transformation turns the analysis into a Semidefinite Program (SDP).
What’s new: While the PEP theory existed, PEPit automates the "modeling" phase. A user simply declares a function class and writes a loop for the algorithm's iterations. PEPit then automatically builds the underlying Gram matrix and linear constraints, passes them to a solver (like MOSEK or CVXPY), and returns the numerical worst-case bound.
Datasets
As a theoretical tool, PEPit does not use traditional training datasets. Instead, it is evaluated against theoretical benchmarks. The authors demonstrate the tool's accuracy by reproducing (and sometimes improving) known worst-case bounds for:
- Standard Gradient Descent.
- Nesterov’s Accelerated Gradient Method.
- Douglas-Rachford Splitting.
- Point-SAGA (a stochastic method).
The package comes bundled with over 75 such examples, serving as a library of verified optimization analyses.
Key Insights and Ideas
- Code as a Proof: The most striking feature is that the "proof" of a convergence rate is essentially the Python script itself. If the SDP returns a value $\tau$, it is a numerically certain upper bound on the algorithm's error.
- Numerical Tightness: Because it solves an optimization problem to find the worst case, the results are often tighter than those found in classical literature, which may rely on loose intermediate inequalities.
- Oracle Abstraction: PEPit supports a wide variety of "oracles"—not just gradients, but proximal operators, projections, linear optimization oracles (for Frank-Wolfe), and even approximate/inexact versions of these.
- Dual Reconstructions: By looking at the dual of the SDP, PEPit can help researchers identify which specific constraints are "active," guiding them toward writing human-readable analytical proofs.
Key Results
- Tightness Verification: For simple Gradient Descent, PEPit perfectly matches the theoretical contraction factor $\max(|1-\gamma L|, |1-\gamma \mu|)$.
- Improving Literature: For the Accelerated Gradient Method, PEPit provided numerical bounds that were slightly better than some established analytical results in the literature (e.g., those from d'Aspremont et al., 2021).
- Complex Methods: The authors successfully analyzed point-SAGA, a stochastic method, by using PEPit to verify the decrease of a "Lyapunov function" (a mathematical energy function) across iterations.
Limitations and Future Work
- Computational Scaling: The size of the SDP grows with the number of iterations ($n$). Analyzing a method for hundreds of iterations can become computationally expensive and may hit the limits of current SDP solvers.
- Non-Convexity: While PEPit supports some non-convex function classes (like smooth non-convex functions), the underlying PEP framework is most robust for convex settings where interpolation conditions are well-defined.
- Future Directions: The authors aim to extend the tool to automatically search for optimal Lyapunov functions, assist in disproving convergence for certain methods, and handle decentralized/distributed optimization settings. They also envision a "proof assistant" mode that could output symbolic, human-readable proofs.
Summary updated