Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives

Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, César A. Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford

Research output: Contribution to journalConference articlepeer-review

30 Scopus citations


In this merged paper, we consider the problem of minimizing a convex function with Lipschitz-continuous p-th order derivatives. Given an oracle which when queried at a point returns the first p-derivatives of the function at that point we provide some methods which compute an ε approximate minimizer in O (ε - 2/3p+1) iterations. These methods match known lower bounds up to poly-logarithmic factors for constant p.

Original languageEnglish (US)
Pages (from-to)1392-1393
Number of pages2
JournalProceedings of Machine Learning Research
StatePublished - 2019
Event32nd Conference on Learning Theory, COLT 2019 - Phoenix, United States
Duration: Jun 25 2019Jun 28 2019

Bibliographical note

Funding Information:
The authors are grateful to Yurii Nesterov for fruitful discussions. The work of A. Gasnikov was supported by RFBR 18-29-03071 mk and was prepared within the framework of the HSE University Basic Research Program and funded by the Russian Academic Excellence Project ’5-100’. The work of P. Dvurechensky and E. Vorontsova was supported by RFBR 18-31-20005 mol-a-ved. The work of E. Gorbunov was supported by the grant of Russian’s President MD-1320.2018.1. The work of Bo Jiang was supported by NSFC grant 11771269. The work of Yin Tat Lee was supported by NSF Awards CCF-1740551, CCF-1749609, and DMS-1839116. The work of Aaron Sidford was supported by NSF CAREER Award CCF-1844855.

Publisher Copyright:
© 2019 A. Gasnikov et al.


Dive into the research topics of 'Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives'. Together they form a unique fingerprint.

Cite this