[edit]
Highly smooth minimization of non-smooth problems
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:988-1030, 2020.
Abstract
We establish improved rates for structured \emph{non-smooth} optimization problems by means of near-optimal higher-order accelerated methods. In particular, given access to a standard oracle model that provides a pth order Taylor expansion of a \emph{smoothed} version of the function, we show how to achieve \eps-optimality for the \emph{original} problem in ˜Op\pa\eps−2p+23p+1 calls to the oracle. Furthermore, when p=3, we provide an efficient implementation of the near-optimal accelerated scheme that achieves an O(\eps−4/5) iteration complexity, where each iteration requires ˜O(1) calls to a linear system solver. Thus, we go beyond the previous O(\eps−1) barrier in terms of \eps dependence, and in the case of ℓ∞ regression and ℓ1-SVM, we establish overall improvements for some parameter settings in the moderate-accuracy regime. Our results also lead to improved high-accuracy rates for minimizing a large class of convex quartic polynomials.