579. Data-driven Analysis of First-order Methods via Distributionally Robust Optimization
Invited abstract in session TC-8: Systematic and computer-aided analyses V: Tools for systematic studies of first-order algorithms, stream Systematic and computer-aided analyses of optimization algorithms.
Tuesday, 14:00-16:00Room: B100/7007
Authors (first author is the speaker)
| 1. | Jisun Park
|
| Operations Research and Financial Engineering, Princeton University | |
| 2. | Vinit Ranjan
|
| Princeton | |
| 3. | Bartolomeo Stellato
|
| Operations Research and Financial Engineering, Princeton University |
Abstract
In this talk, we present a tractable formulation using convex optimization for the probabilistic analysis of first-order methods. We introduce a tractable conic linear program which combines the performance estimation problem (PEP) with the distributionally robust optimization (DRO) approach. Solving this program provides probabilistic performance guarantees in terms of the expectation or conditional value-at-risk (CVaR) of the chosen performance measure, assuming the problem instances follow distribution accessible only through samples. Our framework bridges the worst-case and average-case analyses of first-order methods, by incorporating the data-driven information of the optimization problems. We provide numerical experiments including the probabilistic analysis of convex quadratic minimization or smooth convex minimization, obtaining significant reductions in pessimism compared to classical worst-case analysis.
Keywords
- Computer-aided algorithm analysis
- First-order optimization
- Distributionally robust optimization
Status: accepted
Back to the list of papers