Highly smooth minimization of non-smooth problems

Brian Bullins

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

Download PDF