pipette
ESEspañol

An Optimal First-Order Active-Hull Method for Convex Composite H\"older Smooth Optimization

Renbo Zhao

Preprint

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 .

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 17 pages