Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 1392-1393 |
| Number of pages | 2 |
| Journal | Proceedings of Machine Learning Research |
| Volume | 99 |
| State | Published - 2019 |
| Event | 32nd Conference on Learning Theory, COLT 2019 - Phoenix, United States Duration: Jun 25 2019 → Jun 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.