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.
Bibliographical noteFunding 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.
© 2019 A. Gasnikov et al.