Performance Estimation for Smooth and Strongly Convex Sets

Abstract

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 interior point conditions 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 and linear optimization oracles of smooth/strongly convex sets. As applications of this computer-assisted machinery, we identify a minimax optimal separating hyperplane method and areas for improvement in the theory of Frank-Wolfe and non-Lipschitz Smooth Optimization.

32 pages, 9 figures