Tutorial

Performance Estimation Problems (PEP) [1], [2] offer a systematic framework for analyzing optimization algorithms. Instead of proving convergence rates on a case-by-case basis, PEP reformulates the search for the worst-case performance of an algorithm as a tractable optimization problem accessible to numerical solvers. Solving these problems numerically provides two complementary benefits:

• numerical evidence that illustrates the convergence behavior of the algorithm, and

• quantitative insights that can guide and support the derivation of analytical proofs.

PEPFlow is a Python package that offers a streamlined workflow for applying the PEP framework in practice. Its interactive environment allows users to move seamlessly from formulating PEP to obtaining numerical evidence of convergence and even extracting analytical proofs. The overall workflow is summarized in the diagram below:

In this tutorial, we will walk through the complete PEP workflow, demonstrating how PEPFlow complements the PEP theory and serves as a practical tool for learning, experimentation, and research.

The rest of this tutorial is organized as follows.

• Verifying numerical rates of convergence
• Deriving analytical proofs
  • PEP theory
  • Step 1 dual weight identification
  • Step 2 SOS verification
  • Symbolic calculation
• Summary

---

[1]

Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming, 145(1-2):451–482, 2014.

[2]

B. Goujaud, A. Dieuleveut, and A. B. Taylor. On fundamental proof structures in first-order optimization. In 62nd IEEE Conference on Decision and Control (CDC), 2023.