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

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

Industrial and Systems Engineering

Research output: Contribution to journal › Conference article › peer-review

44 Scopus citations

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

Publisher Copyright:
© 2019 A. Gasnikov et al.

Find It

Find It at U of M Libraries

Cite this

@article{4509a952f14640279cd814ead6099e32,

title = "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 ε approximate minimizer in O (ε - 2/3p+1) iterations. These methods match known lower bounds up to poly-logarithmic factors for constant p.",

author = "Alexander Gasnikov and Pavel Dvurechensky and Eduard Gorbunov and Evgeniya Vorontsova and Daniil Selikhanovych and Uribe, \{C{\'e}sar A.\} and Bo Jiang and Haoyue Wang and Shuzhong Zhang and S{\'e}bastien Bubeck and Qijia Jiang and Lee, \{Yin Tat\} and Yuanzhi Li and Aaron Sidford",

note = "Publisher Copyright: {\textcopyright} 2019 A. Gasnikov et al.; 32nd Conference on Learning Theory, COLT 2019 ; Conference date: 25-06-2019 Through 28-06-2019",

year = "2019",

language = "English (US)",

volume = "99",

pages = "1392--1393",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

publisher = "ML Research Press",

}

TY - JOUR

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

AU - Gasnikov, Alexander

AU - Dvurechensky, Pavel

AU - Gorbunov, Eduard

AU - Vorontsova, Evgeniya

AU - Selikhanovych, Daniil

AU - Uribe, César A.

AU - Jiang, Bo

AU - Wang, Haoyue

AU - Zhang, Shuzhong

AU - Bubeck, Sébastien

AU - Jiang, Qijia

AU - Lee, Yin Tat

AU - Li, Yuanzhi

AU - Sidford, Aaron

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85160854483

UR - https://www.scopus.com/pages/publications/85160854483#tab=citedBy

M3 - Conference article

AN - SCOPUS:85160854483

SN - 2640-3498

VL - 99

SP - 1392

EP - 1393

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 32nd Conference on Learning Theory, COLT 2019

Y2 - 25 June 2019 through 28 June 2019

ER -

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

Abstract

Bibliographical note

Find It

Other files and links

Fingerprint

Cite this