Universality in halting time and its applications in optimization
Universality in halting time and its applications in optimization
复制标题
停止时间的普遍性及其在优化中的应用
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Yann LeCun
中科院分区：
文献类型：
--
作者：
Levent Sagun;T. Trogdon;Yann LeCun
作者提出了应用于两个随机系统（自旋玻璃和深度学习）的优化算法的停止时间（通过达到给定精度的迭代次数来衡量）的经验通用分布。给定一个算法，我们将其视为优化例程和随机景观的形式，停止时间的波动遵循一个分布，即使输入发生巨大变化，该分布也保持不变。我们观察到两个主要的普遍性类别，一种出现在 Google 搜索、人类决策时间、QR 分解和自旋眼镜中的类 Gumbel 分布，以及出现在共轭梯度法、具有 MNIST 输入数据的深度网络和具有随机输入数据的深度网络中的类高斯分布。
The authors present empirical universal 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 remains unchanged even when the input is changed drastically. We observe two main universality classes, a Gumbel-like distribution that appears in Google searches, human decision times, QR factorization 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.
Toda 算法计算随机矩阵最大特征值的通用性
影响因子：
3
作者：
Deift, Percy;Trogdon, Thomas
通讯作者：
Trogdon, Thomas