Performance Estimation for Smooth and Strongly Convex Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910703951020032 |
|---|---|
| author | Luner, Alan Grimmer, Benjamin |
| author_facet | Luner, Alan Grimmer, Benjamin |
| contents | We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions--known as performance estimation--to apply to structured sets. We prove "interpolation theorems" for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered as a limit of our set interpolation theory. Our theory provides finite-dimensional formulations of performance estimation problems for algorithms utilizing separating hyperplane oracles, linear optimization oracles, and/or projection oracles of smooth/strongly convex sets. As direct applications of this computer-assisted machinery, we identify the minimax optimal separating hyperplane method and several areas for improvement in the theory of Frank-Wolfe, Alternating Projections, and non-Lipschitz Smooth Optimization. While particular applications and methods are not our primary focus, several simple theorems and numerically supported conjectures are provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14811 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Performance Estimation for Smooth and Strongly Convex Sets Luner, Alan Grimmer, Benjamin Optimization and Control 90C22, 90C25, 65K05 We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions--known as performance estimation--to apply to structured sets. We prove "interpolation theorems" for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered as a limit of our set interpolation theory. Our theory provides finite-dimensional formulations of performance estimation problems for algorithms utilizing separating hyperplane oracles, linear optimization oracles, and/or projection oracles of smooth/strongly convex sets. As direct applications of this computer-assisted machinery, we identify the minimax optimal separating hyperplane method and several areas for improvement in the theory of Frank-Wolfe, Alternating Projections, and non-Lipschitz Smooth Optimization. While particular applications and methods are not our primary focus, several simple theorems and numerically supported conjectures are provided. |
| title | Performance Estimation for Smooth and Strongly Convex Sets |
| topic | Optimization and Control 90C22, 90C25, 65K05 |
| url | https://arxiv.org/abs/2410.14811 |