Fetching the paper…
Reading the bibliography…
A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers.
Über homogene polynome in L 2 L^{2}
S. Banach · 1938
Earlier work this paper cites.
On richardson’s method for solving linear systems with positive definite matrices
David Young · 1953
Earlier work this paper cites.
Printszip nelokalnogo poiska v sistemah avtomatich, optimizatsii, dokl
IM Gelfand and M Zejtlin · 1961
Earlier work this paper cites.
Gradient methods for minimizing functionals
Boris Teodorovich Polyak · 1963
Earlier work this paper cites.
Some methods of speeding up the convergence of iteration methods
Boris T Polyak · 1964
Earlier work this paper cites.
A method for solving the convex programming problem with convergence rate O ( 1 / k 2 ) O(1/k^{2})
Yu. Nesterov · 1983
Earlier work this paper cites.
Error bounds and convergence analysis of feasible descent methods: a general approach
Z.-Q. Luo and P. Tseng · 1993
Earlier work this paper cites.
Identifiable surfaces in constrained optimization
Stephen J Wright · 1993
Earlier work this paper cites.
The 𝒰 \mathcal{U} -lagrangian of a convex function
Claude Lemaréchal, François Oustry, and Claudia Sagastizábal · 2000
Earlier work this paper cites.
Active sets, nonsmoothness, and sensitivity
Adrian S Lewis · 2002
Earlier work this paper cites.
A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
Samuel Burer and Renato DC Monteiro · 2003
Earlier work this paper cites.
On a class of nonsmooth composite functions
Alexander Shapiro · 2003
Earlier work this paper cites.
Local minima and convergence in low-rank semidefinite programming
Samuel Burer and Renato DC Monteiro · 2005
Earlier work this paper cites.
A V U {VU} -algorithm for convex minimization
Robert Mifflin and Claudia Sagastizábal · 2005
Earlier work this paper cites.
The analysis of linear partial differential operators III: Pseudo-differential operators
Lars Hörmander · 2007
Earlier work this paper cites.
The restricted isometry property and its implications for compressed sensing
Emmanuel J Candes · 2008
Earlier work this paper cites.
Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo · 2010
Earlier work this paper cites.
Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements
Emmanuel J Candes and Yaniv Plan · 2011
Earlier work this paper cites.
Universal low-rank matrix recovery from pauli measurements
Yi-Kai Liu · 2011
Earlier work this paper cites.
Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
Steven T Flammia, David Gross, Yi-Kai Liu, and Jens Eisert · 2012
Earlier work this paper cites.
Smooth manifolds
John M Lee · 2013
Earlier work this paper cites.
Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods
Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter · 2013
Earlier work this paper cites.
Optimality, identifiability, and sensitivity
Dmitriy Drusvyatskiy and Adrian S Lewis · 2014
Earlier work this paper cites.
Yudong Chen and Martin J Wainwright · 2015
Earlier work this paper cites.
Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition
Hamed Karimi, Julie Nutini, and Mark Schmidt · 2016
Earlier work this paper cites.
Low-rank solutions of linear matrix equations via procrustes flow
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht · 2016
Earlier work this paper cites.
Generic minimizing behavior in semialgebraic optimization
Dmitriy Drusvyatskiy, Alexander D Ioffe, and Adrian S Lewis · 2016
Earlier work this paper cites.
Global optimality of local search for low rank matrix recovery
Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro · 2016
Earlier work this paper cites.
A unified approach to error bounds for structured convex optimization problems
Zirui Zhou and Anthony Man-Cho So · 2017
Cited alongside, same era.
No spurious local minima in nonconvex low rank problems: A unified geometric analysis
Rong Ge, Chi Jin, and Yi Zheng · 2017
Cited alongside, same era.
An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis
Yuandong Tian · 2017
Cited alongside, same era.
Globally optimal gradient descent for a convnet with gaussian inputs
Alon Brutzkus and Amir Globerson · 2017
Cited alongside, same era.
When is a convolutional filter easy to learn?
Simon S Du, Jason D Lee, and Yuandong Tian · 2017
Cited alongside, same era.
Implementable tensor methods in unconstrained convex optimization
Yurii Nesterov · 2021
Later among the works it cites.
From the ravine method to the nesterov method and vice versa: a dynamical system perspective
Hedy Attouch and Jalal Fadili · 2022
Later among the works it cites.
Understanding the acceleration phenomenon via high-resolution differential equations
Bin Shi, Simon S Du, Michael I Jordan, and Weijie J Su · 2022
Later among the works it cites.
Proximal methods avoid active strict saddles of weakly convex functions
Damek Davis and Dmitriy Drusvyatskiy · 2022
Later among the works it cites.
Kabir Aladin Chandrasekher, Mengqi Lou, and Ashwin Pananjady · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Error bounds, quadratic growth, and linear convergence of proximal methods
Dmitriy Drusvyatskiy and Adrian S Lewis · 2018
Cited alongside, same era.
Global optimality in low-rank matrix optimization
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin · 2018
Cited alongside, same era.
No spurious local minima in a two hidden unit relu network
Chenwei Wu, Jiajun Luo, and Jason D Lee · 2018
Cited alongside, same era.
Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang · 2018
Cited alongside, same era.
Greed, hedging, and acceleration in convex optimization
Jason Altschuler · 2018
Cited alongside, same era.
Spurious local minima are common in two-layer relu neural networks
Itay Safran and Ohad Shamir · 2018
Cited alongside, same era.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen · 2018
Cited alongside, same era.
Nonsmooth rank-one matrix factorization landscape
Cédric Josz and Lexiao Lai · 2022
Later among the works it cites.
Algorithmic regularization in model-free overparametrized asymmetric matrix factorization
Liwei Jiang, Yudong Chen, and Lijun Ding · 2022
Later among the works it cites.
A validation approach to over-parameterized matrix and image recovery
Lijun Ding, Zhen Qin, Liwei Jiang, Jinxin Zhou, and Zhihui Zhu · 2022
Later among the works it cites.
Gavin Zhang, Salar Fattahi, and Richard Y Zhang · 2022
Later among the works it cites.
Big-step-little-step: Efficient gradient methods for objectives with multiple scales
Jonathan Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, and Honglin Yuan · 2022
Later among the works it cites.
Over-parameterization exponentially slows down gradient descent for learning a single neuron
Weihang Xu and Simon S Du · 2023
Later among the works it cites.
Asymptotic normality and optimality in nonsmooth stochastic approximation
Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang · 2023
Later among the works it cites.
Geometric analysis of noisy low-rank matrix recovery in the exact parametrized and the overparametrized regimes
Ziye Ma, Yingjie Bi, Javad Lavaei, and Somayeh Sojoudi · 2023
Later among the works it cites.
Asymmetric matrix sensing by gradient descent with small random initialization
Johan S Wind · 2023
Later among the works it cites.
Global convergence of sub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and over-parameterization
Jianhao Ma and Salar Fattahi · 2023
Later among the works it cites.
Understanding incremental learning of gradient descent: A fine-grained analysis of matrix sensing
Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Shaolei Du, and Jason D Lee · 2023
Later among the works it cites.
The power of preconditioning in overparameterized low-rank matrix sensing
Xingyu Xu, Yandi Shen, Yuejie Chi, and Cong Ma · 2023
Later among the works it cites.
Mahdi Soltanolkotabi, Dominik Stöger, and Changzhi Xie · 2023
Later among the works it cites.
Nuoya Xiong, Lijun Ding, and Simon S Du · 2023
Later among the works it cites.
Convergence of alternating gradient descent for matrix factorization
Rachel Ward and Tamara Kolda · 2023
Later among the works it cites.
Acceleration by stepsize hedging i: Multi-step descent and the silver stepsize schedule
Jason M Altschuler and Pablo A Parrilo · 2023
Later among the works it cites.
Acceleration by stepsize hedging ii: Silver stepsize schedule for smooth convex optimization
Jason M Altschuler and Pablo A Parrilo · 2023
Later among the works it cites.
A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth
Damek Davis and Liwei Jiang · 2024
Closest in time.
Decentralized matrix sensing: statistical guarantees and fast convergence
Marie Maros and Gesualdo Scutari · 2024
Closest in time.
Fast and accurate estimation of low-rank matrices from noisy measurements via preconditioned non-convex gradient descent
Jialun Zhang, Richard Y Zhang, and Hong-Ming Chiu · 2024
Closest in time.
Provably faster gradient descent via long steps
Benjamin Grimmer · 2024
Closest in time.
Accelerated objective gap and gradient norm convergence for gradient descent via long steps
Benjamin Grimmer, Kevin Shu, and Alex Wang · 2024
Closest in time.