Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-Th Derivatives
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 $\e$ approximate minimizer in $O\left(\e^{-\frac{2}{3p+1}} \right)$ iterations. These methods match known lower bounds up to polylogarithmic factors for constant $p$.
Cite
Text
Gasnikov et al. "Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-Th Derivatives." Conference on Learning Theory, 2019.Markdown
[Gasnikov et al. "Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-Th Derivatives." Conference on Learning Theory, 2019.](https://mlanthology.org/colt/2019/gasnikov2019colt-near/)BibTeX
@inproceedings{gasnikov2019colt-near,
title = {{Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-Th Derivatives}},
author = {Gasnikov, Alexander and Dvurechensky, Pavel and Gorbunov, Eduard and Vorontsova, Evgeniya and Selikhanovych, Daniil and Uribe, César A. and Jiang, Bo and Wang, Haoyue and Zhang, Shuzhong and Bubeck, Sébastien and Jiang, Qijia and Lee, Yin Tat and Li, Yuanzhi and Sidford, Aaron},
booktitle = {Conference on Learning Theory},
year = {2019},
pages = {1392-1393},
volume = {99},
url = {https://mlanthology.org/colt/2019/gasnikov2019colt-near/}
}