An Optimal First-Order Active-Hull Method for Convex Composite H\"older Smooth Optimization
In the authors' words
We consider the problem (P): under the Euclidean geometry, where is convex and -H\"older smooth on , and is proper, closed and convex on , admits a generalized linear minimization oracle (GLMO), and has bounded domain with diameter . An first-order active-hull (AH) method has access to both the first-order oracle (FO) of and the GLMO of , and outputs a point that lies in the convex hull of all the past GLMO returns. We propose a new first-order AH method for solving (P), which is based on our newly developed "recentered homotopy smoothing framework". We show that in the high-dimensional regime, this method achieves the optimal FO and GLMO complexties simultaneously for all .
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 17 pages