Exact Performance Verification of First‑Order Methods in Parametric Convex Optimization
summary
A computational framework quantifies finite‑iteration performance of first‑order methods for parametric convex problems by modeling algorithms as fixed‑length computational graphs and turning verification into an optimization that maximizes a performance metric (fixed‑point residual) over instance sets. The paper proves verification is NP‑hard, supplies semidefinite programming relaxations and exact mixed‑integer linear formulations with tight polyhedral encodings of proximal/projection steps, adds bound‑tightening using operator theory to scale (reports up to ~40 iterations), and shows numerics that closely match true worst‑case and substantially reduce pessimistic standard bounds.
AI-written summary · about
chapters (8)
- 0:00First-order methods intro
- 1:04Parametric convex optimization apps
- 13:30Performance estimation problem
- 21:41Worst-case analysis
- 37:50Exact verification with MIP
- 44:17Probabilistic guarantees from data
- 51:08Acknowledgments
- 54:45Q&A
related talks
22mExecution Time Program Verification With Tight Bounds
21mSupermartingales for Unique Fixed Points: A Unified Approach to Lower Bound Verification
59mThe Proof Complexity of Integer Programming
49mAlgorithmic Mechanism Design with Investment
18mOn the Verification of a Subgraph Construction Algorithm
58mA New Perspective on Commutativity in Verification
21mArchitecture-Preserving Provable Repair of Deep Neural Networks
28mGradual Verification: Assuring Software Incrementally