Highly smooth minimization of non-smooth problems

Brian Bullins
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 $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 $\tilde{O}_p\pa{\eps^{-\frac{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 $\tilde{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-bullins20a, title = {Highly smooth minimization of non-smooth problems}, author = {Bullins, Brian}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {988--1030}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/bullins20a/bullins20a.pdf}, url = {https://proceedings.mlr.press/v125/bullins20a.html}, 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 $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 $\tilde{O}_p\pa{\eps^{-\frac{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 $\tilde{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.} }
Endnote
%0 Conference Paper %T Highly smooth minimization of non-smooth problems %A Brian Bullins %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-bullins20a %I PMLR %P 988--1030 %U https://proceedings.mlr.press/v125/bullins20a.html %V 125 %X 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 $\tilde{O}_p\pa{\eps^{-\frac{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 $\tilde{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.
APA
Bullins, B.. (2020). Highly smooth minimization of non-smooth problems. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:988-1030 Available from https://proceedings.mlr.press/v125/bullins20a.html.

Related Material