Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness

A method of solving a convex programming problem with convergence rate O ⁡ ( 1 / k 2 ) O(1/k^{2})

Yu. E. Nesterov · 1983

Earlier work this paper cites.

Problem complexity and method efficiency in optimization

Arkadiĭ Nemirovsky and David Borisovich Yudin · 1983

Earlier work this paper cites.

On parallel complexity of nonsmooth convex optimization

Arkadi Nemirovski · 1994

Earlier work this paper cites.

An elementary introduction to modern convex geometry

Keith Ball · 1997

Earlier work this paper cites.

Strengths and weaknesses of quantum computing

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997

Earlier work this paper cites.

Accelerating the cubic regularization of newton’s method on convex problems

Yu. Nesterov · 2008

Earlier work this paper cites.

Estimate sequence methods: extensions and approximations

Michel Baes · 2009

Earlier work this paper cites.

Infimal Convolution

Heinz H. Bauschke and Patrick L. Combettes · 2011

Earlier work this paper cites.

An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods

Renato D. C. Monteiro and B. F. Svaiter · 2013

Cited alongside, same era.

On lower complexity bounds for large-scale smooth convex optimization

Cristóbal Guzmán and Arkadi Nemirovski · 2014

Cited alongside, same era.

Lower bounds for higher-order convex optimization

Naman Agarwal and Elad Hazan · 2018

Cited alongside, same era.

Oracle complexity of second-order methods for smooth convex optimization

Yossi Arjevani, Ohad Shamir, and Ron Shiff · 2019

Cited alongside, same era.

Complexity of highly parallel non-smooth convex optimization

Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford · 2019

Cited alongside, same era.

Near-optimal method for highly smooth convex optimization

Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford · 2019

An optimal high-order tensor method for convex optimization

Bo Jiang, Haoyue Wang, and Shuzhong Zhang · 2019

Later among the works it cites.

Implementable tensor methods in unconstrained convex optimization

Yurii Nesterov · 2019

Later among the works it cites.

Convex optimization using quantum oracles

Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf · 2020

Later among the works it cites.

Highly smooth minimization of non-smooth problems

Brian Bullins · 2020

Later among the works it cites.

Quantum algorithms and lower bounds for convex optimization

Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu · 2020

Later among the works it cites.

Lower bounds for parallel and randomized convex optimization

Jelena Diakonikolas and Cristóbal Guzmán · 2020

Later among the works it cites.