Performance Estimation Programming for Optimization Algorithms

141 concepts70 papers

Proving that an optimization algorithm converges efficiently has historically been a manual, highly specialized task. To guarantee that an algorithm approaches an optimal solution, theorists have traditionally had to construct "Lyapunov functions" or "potential functions"—mathematical quantities that decrease at every iteration.

This process often felt like a "black art," relying heavily on human intuition. If a proof failed, it was unclear whether the algorithm itself was genuinely flawed or if the researcher simply had not found the right potential function.

Performance Estimation Programming (PEP) and related automated frameworks change this paradigm. Instead of searching for a proof by hand, these frameworks turn the task of proving a theorem into a structured optimization problem that a computer can solve. By treating an algorithm's worst-case performance as an objective function and the mathematical properties of the optimization landscape as constraints, researchers can use Semidefinite Programming (SDP) to automatically find tight convergence rates, discover optimal parameters, and design entirely new algorithms.

Turning Functions into Constraints

To analyze an algorithm computationally, we must translate abstract functional properties (such as convexity, smoothness, or cocoercivity) into a form a computer can process. The key insight lies in interpolation conditions and quadratic constraints.

Suppose an algorithm generates a sequence of iterates $x_0, x_1, \dots, x_N$ with corresponding gradients $g_0, g_1, \dots, g_N$. We do not need to model the entire continuous function $f(x)$; we only need to ensure that there exists a valid function within our target class that matches these specific discrete points.

For example, if $f$ is convex, the standard first-order inequality must hold for all pairs of iterates $i$ and $j$:

$$f(x_j) \ge f(x_i) + \langle g_i, x_j - x_i \rangle$$

Because these inequalities are linear with respect to the function values $f(x_i)$ and the inner products of the gradients and iterates $\langle g_i, x_j \rangle$, we can collect these inner products into a symmetric matrix known as a Gram matrix, $G$. Since $G$ represents the inner products of vectors, it must be positive semidefinite ($G \succeq 0$). This requirement transforms the search for worst-case behavior into a Semidefinite Program (SDP).

Two Methodological Pillars: PEP and IQC

The literature generally approaches automated convergence analysis from two distinct but complementary perspectives: Performance Estimation Problems (PEP) and Integral Quadratic Constraints (IQC).

Performance Estimation Problems (PEP)

First formalized by Adrien B. Taylor et al. in "Exact Worst-Case Convergence Rates of the Proximal Gradient Method for Composite Convex Minimization", the PEP framework maximizes a performance error metric (such as the suboptimality $f(x_N) - f(x^*)$) over a fixed number of steps $N$. This maximization is subject to the initial distance boundaries and the function's interpolation constraints.

Because this formulation is exact and tight, the resulting numerical bound represents the absolute worst-case scenario for that algorithm. If the SDP solver outputs a specific convergence rate, it is mathematically guaranteed to be reachable by a worst-case function. This approach was extended to operator splitting methods (OSPEP) by Ernest K. Ryu et al. to find tight contraction factors for methods like Douglas–Rachford splitting.

Integral Quadratic Constraints (IQC)

Borrowing from robust control theory, researchers such as Ribeiro Alejandro et al. and Robert Nishihara et al. reframe optimization algorithms as discrete-time linear dynamical systems. The algorithm is viewed as a linear system connected in a feedback loop with a non-linear operator (the gradient).

By bounding the operator's behavior using quadratic inequalities, the search for a valid quadratic Lyapunov function reduces to solving a Linear Matrix Inequality (LMI). While PEP optimizes over a fixed horizon $N$, the IQC framework searches for a single, step-independent Lyapunov function. This makes it highly scalable and effective for analyzing steady-state behavior and stochastic algorithms, as demonstrated by Bin Hu et al. in the analysis of variance-reduction methods like SVRG and Katyusha.

From Analysis to Automated Design

Once convergence analysis is automated, the framework can be inverted to design optimal algorithms. By treating step sizes or momentum coefficients as tunable variables within the meta-optimization problem, computers can synthesize optimal parameters.

For instance, Donghwan Kim et al. used PEP to optimize step coefficients, re-deriving the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA) and discovering new, more efficient proximal gradient variants. Similarly, Jisun Park et al. in "Exact Optimal Accelerated Complexity for Fixed-Point Iterations" leveraged PEP to establish the exact theoretical speed limits for fixed-point iterations, introducing optimal algorithms like OC-Halpern.

+-----------------------------------------------------------------+
|                   Performance Estimation (PEP)                  |
|                                                                 |
|  Maximize:  Performance Error (e.g., f(x_N) - f(x*))            |
|  Subject to:                                                    |
|    - Algorithm Update Steps (Dynamics)                          |
|    - Function Interpolation Conditions (Gram Matrix G >= 0)     |
+-----------------------------------------------------------------+
                                |
                                v
+-----------------------------------------------------------------+
|                    Semidefinite Solver (SDP)                    |
+-----------------------------------------------------------------+
                                |
        +-----------------------+-----------------------+
        |                                               |
        v                                               v
+-------------------------------+               +-------------------------------+
|       Worst-Case Bounds       |               |   Optimal Parameter Design    |
|  Provides exact, tight bounds |               |  Discovers optimal step sizes |
|  and worst-case trajectories. |               |  and momentum coefficients.   |
+-------------------------------+               +-------------------------------+

Furthermore, this computer-assisted approach helps theorists break through long-standing analytical bottlenecks. Eduard Gorbunov et al. used PEP to numerically observe worst-case trajectories, providing the vital structural clues needed to manually prove the $O(1/K)$ last-iterate convergence of the Optimistic Gradient method for monotone variational inequalities.

Expanding the Horizon

The reach of performance estimation programming continues to expand into more complex domains:

  • Non-convex Constraints: To handle scenarios where standard SDP relaxations fall short, Shuvomoy Das Gupta et al. introduced a global branch-and-bound methodology within performance estimation programming, enabling global solutions for non-convex structures.
  • Online Learning: Julien Weibel applied these SDP frameworks to online learning, computing exact worst-case regret bounds and optimizing parameters for projection-free algorithms like Online Frank-Wolfe.
  • Infeasibility Detection: Jisun Park et al. in "Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations" extended PEP to operators without fixed points, allowing researchers to formally analyze how algorithms behave when applied to impossible or divergent problems.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 87 papers
  2. Version 1 · 2026-10-04 · 123 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_performance_estimation_problems_b6b66c7a,
  title = {performance estimation problems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/performance-estimation-problems/rdr_b6b66c7a5fe04bc1b251e8498f3c71f3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_performance_estimation_problems_b6b66c7a_v2,
  title = {performance estimation problems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/performance-estimation-problems/rdr_b6b66c7a5fe04bc1b251e8498f3c71f3/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake