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 $p^{th}$ order Taylor expansion of a emph{smoothed} version of the function, we show how to achieve $eps$-optimality for the emph{original} problem in $ilde{O}_ppa{eps^{-rac{2p+2}{3p+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 $ilde{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 $ell_infty$ regression and $ell_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.
展开▼
