Near-optimal method for highly smooth convex optimization

Sébastien Bubeck; Qijia Jiang; Yin Tat Lee; Yuanzhi Li; Aaron Sidford

Near-optimal method for highly smooth convex optimization

Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford

Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:492-507, 2019.

Abstract

We propose a near-optimal method for highly smooth convex optimization. More precisely, in the oracle model where one obtains the

$p^{th}$ order Taylor expansion of a function at the query point, we propose a method with rate of convergence

$\tilde{O}(1/k^{\frac{ 3p +1}{2}})$ after

$k$ queries to the oracle for any convex function whose

$p^{th}$ order derivative is Lipschitz.

Cite this Paper

BibTeX


@InProceedings{pmlr-v99-bubeck19a,
  title = 	 {Near-optimal method for highly smooth convex optimization},
  author =       {Bubeck, S{\'e}bastien and Jiang, Qijia and Lee, Yin Tat and Li, Yuanzhi and Sidford, Aaron},
  booktitle = 	 {Proceedings of the Thirty-Second Conference on Learning Theory},
  pages = 	 {492--507},
  year = 	 {2019},
  editor = 	 {Beygelzimer, Alina and Hsu, Daniel},
  volume = 	 {99},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {25--28 Jun},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v99/bubeck19a/bubeck19a.pdf},
  url = 	 {https://proceedings.mlr.press/v99/bubeck19a.html},
  abstract = 	 {We propose a near-optimal method for highly smooth convex optimization. More precisely, in the oracle model where one obtains the $p^{th}$ order Taylor expansion of a function at the query point, we propose a method with rate of convergence $\tilde{O}(1/k^{\frac{ 3p +1}{2}})$ after $k$ queries to the oracle for any convex function whose $p^{th}$ order derivative is Lipschitz.}
}

Endnote

%0 Conference Paper
%T Near-optimal method for highly smooth convex optimization
%A Sébastien Bubeck
%A Qijia Jiang
%A Yin Tat Lee
%A Yuanzhi Li
%A Aaron Sidford
%B Proceedings of the Thirty-Second Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2019
%E Alina Beygelzimer
%E Daniel Hsu	
%F pmlr-v99-bubeck19a
%I PMLR
%P 492--507
%U https://proceedings.mlr.press/v99/bubeck19a.html
%V 99
%X We propose a near-optimal method for highly smooth convex optimization. More precisely, in the oracle model where one obtains the $p^{th}$ order Taylor expansion of a function at the query point, we propose a method with rate of convergence $\tilde{O}(1/k^{\frac{ 3p +1}{2}})$ after $k$ queries to the oracle for any convex function whose $p^{th}$ order derivative is Lipschitz.

APA


Bubeck, S., Jiang, Q., Lee, Y.T., Li, Y. & Sidford, A.. (2019). Near-optimal method for highly smooth convex optimization. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:492-507 Available from https://proceedings.mlr.press/v99/bubeck19a.html.

Related Material

Download PDF