CDM-MTEI Seminars: Performance Optimization Programming: Methodology, Algorithms and Insights
Abstract:
The design of efficient optimization algorithms has long relied on intuition and hand-crafted analysis. A newer paradigm -- Performance Optimization Programming (POP) -- reframes the question of algorithm analysis as a metaoptimization problem, enabling a computer-assisted, systematic search for optimal methods. We introduce Branch-and-Bound Performance Estimation Programming (BnB-PEP), a unified methodology for constructing certifiably optimal first-order methods for both convex and nonconvex optimization. Prior PEP-based approaches formulate worst-case performance as a convex semidefinite program, but this convexity is simultaneously a limitation: only a narrow class of problem setups admit such tractable reformulations. BnB-PEP overcomes this barrier by directly embracing nonconvexity. BnB-PEP is applied to several settings that were previously intractable: constructing the optimal gradient method without momentum, deriving optimal methods for reducing gradient norms of smooth nonconvex functions, and designing efficient methods for weakly convex nonsmooth optimization. In each case, the methodology yields new state-of-the-art convergence bounds. Finally, we show how the analysis generalizes to settings with gradient corruption and allows for the discovery of an entirely novel class of first-order optimization algorithms which enjoy optimal corruption protection.
References:
Short bio: Bart van Parys is a senior researcher in the Stochastics groupt at the Dutch National Institute for Mathematics and Computer Science (CWI). Bart has played a pioneering role in developing distributionally robust optimization (DRO) as a practical tool for decision-making in uncertain environments. His doctoral work pioneered DRO formulations in stochastic control theory and power systems. Key innovations were an extension of the inequality of Gauss from 1821 in terms of tractable convex optimization problems.
More recently, Bart formalized the search for statistically efficient data-driven decisions by advancing a novel meta-optimization framework via large-deviations theory. Bart's current research is primarily methodological and revolves around fundamental concerns when making decisions based on wild data sets and the automated design of better optimization algorithms.
The design of efficient optimization algorithms has long relied on intuition and hand-crafted analysis. A newer paradigm -- Performance Optimization Programming (POP) -- reframes the question of algorithm analysis as a metaoptimization problem, enabling a computer-assisted, systematic search for optimal methods. We introduce Branch-and-Bound Performance Estimation Programming (BnB-PEP), a unified methodology for constructing certifiably optimal first-order methods for both convex and nonconvex optimization. Prior PEP-based approaches formulate worst-case performance as a convex semidefinite program, but this convexity is simultaneously a limitation: only a narrow class of problem setups admit such tractable reformulations. BnB-PEP overcomes this barrier by directly embracing nonconvexity. BnB-PEP is applied to several settings that were previously intractable: constructing the optimal gradient method without momentum, deriving optimal methods for reducing gradient norms of smooth nonconvex functions, and designing efficient methods for weakly convex nonsmooth optimization. In each case, the methodology yields new state-of-the-art convergence bounds. Finally, we show how the analysis generalizes to settings with gradient corruption and allows for the discovery of an entirely novel class of first-order optimization algorithms which enjoy optimal corruption protection.
References:
- [Das Gupta, van Parys, Ryu: Branch-and-Bound Performance Estimation Programming](https://arxiv.org/pdf/2203.07305)
- [Gösgens, van Parys: Subgradient Methods for Nonsmooth Convex Functions with Adversarial Errors](https://arxiv.org/abs/2510.03072)
Short bio: Bart van Parys is a senior researcher in the Stochastics groupt at the Dutch National Institute for Mathematics and Computer Science (CWI). Bart has played a pioneering role in developing distributionally robust optimization (DRO) as a practical tool for decision-making in uncertain environments. His doctoral work pioneered DRO formulations in stochastic control theory and power systems. Key innovations were an extension of the inequality of Gauss from 1821 in terms of tractable convex optimization problems.
More recently, Bart formalized the search for statistically efficient data-driven decisions by advancing a novel meta-optimization framework via large-deviations theory. Bart's current research is primarily methodological and revolves around fundamental concerns when making decisions based on wild data sets and the automated design of better optimization algorithms.
Practical information
- Informed public
- Registration required
Organizer
- Prof. Daniel Kuhn