numericaluniversality
Universality in numerical computations with random data. The authors present evidence for universality in numerical computations with random data. Given a (possibly stochastic) numerical algorithm with random input data, the time (or number of iterations) to convergence (within a given tolerance) is a random variable, called the halting time. Two-component universality is observed for the fluctuations of the halting time -- i.e., the histogram for the halting times, centered by the sample average and scaled by the sample variance, collapses to a universal curve, independent of the input data distribution, as the dimension increases. Thus, up to two components -- the sample average and the sample variance -- the statistics for the halting time are universally prescribed. The case studies include six standard numerical algorithms as well as a model of neural computation and decision-making. A link to relevant software is provided for readers who would like to do computations of their own. par See also the related work of the first two authors with {it C. W. Pfrang} [Math. Sci. Res. Inst. Publ. 65, 411--442 (2014; Zbl 1326.65050)].
Keywords for this software
References in zbMATH (referenced in 11 articles )
Showing results 1 to 11 of 11.
Sorted by year (- Deift, Percy; Trogdon, Thomas: The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic (2021)
- Bakhtin, Yuri: Universal statistics of incubation periods and other detection times via diffusion models (2019)
- Deift, Percy A.: Three lectures on “Fifty years of KdV: an integrable system” (2019)
- Deift, Percy; Trogdon, Thomas: Universality in numerical computation with random data: case studies and analytical results (2019)
- Sagun, Levent; Trogdon, Thomas; LeCun, Yann: Universal halting times in optimization and machine learning (2018)
- Damanik, David (ed.); Gesztesy, Fritz (ed.); Yuditskii, Peter (ed.): Mini-workshop: Reflectionless operators: the Deift and Simon conjectures. Abstracts from the mini-workshop held October 22--28, 2017 (2017)
- Deift, Percy: Some open problems in random matrix theory and the theory of integrable systems. II (2017)
- Deift, Percy; Trogdon, Thomas: Universality for eigenvalue algorithms on sample covariance matrices (2017)
- Menon, Govind; Trogdon, Thomas: Smoothed analysis for the conjugate gradient algorithm (2016)
- Menon, Govind; Trogdon, Thomas; Deift, Percy A.: On the condition number of the critically-scaled Laguerre unitary ensemble (2016)
- Deift, Percy A.; Menon, Govind; Olver, Sheehan; Trogdon, Thomas: Universality in numerical computations with random data (2014)