Fetching the paper…

Reading the bibliography…

2018

Near-optimal method for highly smooth convex optimization

Bubeck, Sébastien, Jiang, Qijia, Lee, Yin Tat et al.

Original
PDF
Post on X

Understand

We propose a near-optimal method for highly smooth convex optimization.

More precisely, in the oracle model where one obtains the $p^{th}$ order Taylor expansion of a function at the query point, we propose a method with rate of convergence $\tilde{O}(1/k^{\frac{ 3p +1}{2}})$ after $k$ queries to the oracle for any convex function whose $p^{th}$ order derivative is Lipschitz.

Near-optimal method for highly smooth convex optimization · Around

Built on

Orth-method for smooth convex optimization
A. Nemirovski · 1982
Earlier work this paper cites.
Problem Complexity and Method Efficiency in Optimization
A. Nemirovski and D. Yudin · 1983
Earlier work this paper cites.
A method of solving a convex programming problem with convergence rate o( 1 / k 2 1/k^{2} )
Y. Nesterov · 1983
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course
Y. Nesterov · 2004
Earlier work this paper cites.

Similar

An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
R. D. C. Monteiro and B. F. Svaiter · 2013
Cited alongside, same era.
Lower bounds for higher-order convex optimization
N. Agarwal and E. Hazan · 2018
Cited alongside, same era.
Oracle complexity of second-order methods for smooth convex optimization
Y. Arjevani, O. Shamir, and R. Shiff · 2018
Cited alongside, same era.

Then

The global rate of convergence for optimal tensor methods in smooth convex optimization
Original
A. Gasnikov, E. Gorbunov, D. Kovalev, A. Mohhamed, and E. Chernousova · 2018
Closest in time.
An optimal high-order tensor method for convex optimization
Original
B. Jiang, H. Wang, and S. Zhang · 2018
Closest in time.
Implementable tensor methods in unconstrained convex optimization
Y. Nesterov · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…