Understand
The authors present empirical distributions for the halting time (measured by the number of iterations to reach a given accuracy) of optimization algorithms applied to two random systems: spin glasses and deep learning.
- Given an algorithm, which we take to be both the optimization routine and the form of the random landscape, the fluctuations of the halting time follow a distribution that, after centering and scaling, remains unchanged even when the distribution on the landscape is changed.
- We observe two qualitative classes: A Gumbel-like distribution that appears in Google searches, human decision times, the QR eigenvalue algorithm and spin glasses, and a Gaussian-like distribution that appears in conjugate gradient method, deep network with MNIST input data and deep network with random input data.
- This empirical evidence suggests presence of a class of distributions for which the halting time is independent of the underlying distribution under some conditions.
Built on
Method of Conjugate Gradients for solving Linear Systems
Magnus Rudolph Hestenes and Eduard Stiefel · 1952
Earlier work this paper cites.
Behavior of slightly perturbed lanczos and conjugate-gradient recurrences
Anne Greenbaum · 1989
Earlier work this paper cites.
Predicting the behavior of finite precision lanczos and conjugate gradient computations
Anne Greenbaum and Zdenek Strakos · 1992
Earlier work this paper cites.
Random fields and geometry
Robert J Adler and Jonathan E Taylor · 2009
Earlier work this paper cites.
A neural computation model for decision-making times
Yuri Bakhtin and Joshua Correll · 2012
Earlier work this paper cites.
Similar
Random matrices and complexity of spin glasses
Antonio Auffinger, Gérard Ben Arous, and Jiří Černý · 2013
Cited alongside, same era.
Universality in numerical computations with random data
Percy Deift, Govind Menon, Sheehan Olver, and Thomas Trogdon · 2014
Cited alongside, same era.
How long does it take to compute the eigenvalues of a random symmetric matrix?
Christian W Pfrang, Percy Deift, and Govind Menon · 2014
Cited alongside, same era.
Explorations on high dimensional landscapes
Levent Sagun, V Uğur Güney, Gérard Ben Arous, and Yann LeCun · 2014
Cited alongside, same era.
Then
On the condition number of the critically-scaled laguerre unitary ensemble
Percy Deift, Govind Menon, and Thomas Trogdon · 2015
Closest in time.
Universality for the Toda algorithm to compute the eigenvalues of a random matrix
Percy Deift and Thomas Trogdon · 2016
Closest in time.
Universality for eigenvalue algorithms on sample covariance matrices
Percy Deift and Thomas Trogdon · 2017
Closest in time.
Mnist database
Yann LeCun, Corinna Cortes, and Burges Christopher J. C · 2017
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…