Provable non-accelerations of the heavy-ball method

Polyak BT (1964) Some methods of speeding up the convergence of iteration methods. USSR computational mathematics and mathematical physics

1964

Earlier work this paper cites.

Gray RM (2006) Toeplitz and circulant matrices: A review. Foundations and Trends® in Communications and Information Theory 2(3):155–239, original publication 1971

1971

Earlier work this paper cites.

Nemirovsky AS, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization. Willey-Interscience, New York

1983

Earlier work this paper cites.

Nesterov Y (1983) A method of solving a convex programming problem with convergence rate O ⁡ ( 1 / k 2 ) {O}(1/k^{2}) . Soviet Mathematics Doklady 27(2):372–376

1983

Earlier work this paper cites.

Polyak BT (1987) Introduction to optimization. Optimization Software New York

1987

Earlier work this paper cites.

Nemirovskii AS (1994) Information-based complexity of convex programming. Lecture notes ( link )

1994

Earlier work this paper cites.

Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM review 38(1):49–95

1996

Earlier work this paper cites.

Rockafellar RT (1997) Convex analysis, vol 11. Princeton university press

1997

Earlier work this paper cites.

Nesterov Y (2003) Introductory Lectures on Convex Optimization. Springer

2003

Earlier work this paper cites.

Bottou L, Bousquet O (2007) The tradeoffs of large scale learning. In: Advances in Neural Information Processing Systems (NIPS)

2007

Earlier work this paper cites.

Brézis H (2011) Functional analysis, Sobolev spaces and partial differential equations, vol 2. Springer

2011

Earlier work this paper cites.

Fischer B (2011) Polynomial based iteration methods for symmetric linear systems. SIAM

2011

Cited alongside, same era.

Drori Y, Teboulle M (2014) Performance of first-order methods for smooth convex minimization: a novel approach. Math. Programming 145(1):451–482

2014

Cited alongside, same era.

Bubeck S (2015) Convex optimization: Algorithms and complexity. Found and Trends in Machine Learning 8(3-4):231–357

2015

Cited alongside, same era.

Ghadimi E, Feyzmahdavian HR, Johansson M (2015) Global convergence of the heavy-ball method for convex optimization. In: European control conference (ECC)

2015

Cited alongside, same era.

Lessard L, Recht B, Packard A (2016) Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization 26(1):57–95

2016

Cited alongside, same era.

Gupta C, Balakrishnan S, Ramdas A (2021) Path length bounds for gradient descent and flow. The Journal of Machine Learning Research 22(1):3154–3216

2021

Later among the works it cites.

Drori Y, Taylor A (2022) On the oracle complexity of smooth strongly convex minimization. Journal of Complexity 68:101590

2022

Later among the works it cites.

Wang JK, Lin CH, Wibisono A, Hu B (2022) Provable acceleration of heavy ball beyond quadratics for a class of Polyak-Lojasiewicz functions when the non-convexity is averaged-out. In: International Conference on Machine Learning (ICML)

2022

Later among the works it cites.

Dobson P, Sanz-Serna JM, Zygalakis K (2023) On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights. arXiv preprint arXiv:230508658

2023

Closest in time.

Goujaud B, Dieuleveut A, Taylor A (2023) Counter-examples in first-order optimization: a constructive approach. IEEE Control Systems Letters (See arXiv 2303 10503 for complete version with appendices)