ISyE Seminar Series: Bartolomeo Stellato
"Data-Driven Algorithm Design and Verification for Parametric Convex Optimization"
Bartolomeo Stellato
Assistant Professor in the Department of Operations Research and Financial Engineering
Princeton University
About the Seminar:
We present computational tools to analyze and design first-order methods in parametric convex optimization. First-order methods are popular for their low per-iteration cost and warm-starting capabilities. However, precisely quantifying the number of iterations needed to compute a high-quality solution remains a key challenge, especially in safety-critical applications where real-time execution is crucial. In the first part of the talk, we introduce a numerical framework for verifying the worst-case performance of first-order methods in parametric quadratic optimization. We formulate the verification problem as a mathematical optimization problem that maximizes the fixed-point residual at the last iteration, subject to constraints representing the algorithm used. Our framework can encode many proximal algorithms as variations of two primitive steps: affine steps and element-wise maximum steps. We show that the verification problem is NP-hard, and we construct convex semidefinite programming relaxations. Numerical examples show a significant reduction in pessimism compared to standard worst-case convergence analyses and performance estimation techniques. In the second part of the talk, we present a data-driven approach to analyze the performance of first-order methods using statistical learning theory. We build generalization guarantees for classical optimizers, using sample convergence bounds, and for learned optimizers, using the Probably Approximately Correct (PAC)-Bayes framework. We then use this framework to learn accelerated first-order methods by minimizing the PAC-Bayes bound directly over the key parameters of the algorithms (e.g., gradient steps, and warm-starts). Several numerical experiments show that our approach provides strong generalization guarantees for both classical and learned optimizers with statistical bounds that are very close to the true out of sample performance.
About the Speaker:
Bartolomeo Stellato is an Assistant Professor in the Department of Operations Research and Financial Engineering at Princeton University. Previously, he was a Postdoctoral Associate at the MIT Sloan School of Management and Operations Research Center. He holds a DPhil (PhD) in Engineering Science from the University of Oxford, a MSc in Robotics, Systems and Control from ETH Zürich, and a BSc in Automation Engineering from Politecnico di Milano. He developed OSQP, a widely used solver in mathematical optimization. His awards include the Beale — Orchard-Hays Prize, the ONR Young Investigator Award, the NSF CAREER Award, the Princeton SEAS Howard B. Wentz Jr. Faculty Award, the Franco Strazzabosco Young Investigator Award from ISSNAF, the Princeton SEAS Innovation Award in Data Science, the Best Paper Award in Mathematical Programming Computation, and the First Place Prize Paper Award in IEEE Transactions on Power Electronics. His research focuses on data-driven computational tools for mathematical optimization, machine learning, and optimal control.
If you wish to be added to the ISyE Graduate Seminar Series emailing list, please email Event Coordinator Emily Rice at [email protected].