On Gradient Descent Convergence beyond the Edge of Stability
On Gradient Descent Convergence beyond the Edge of Stability
复制标题
超越稳定边缘的梯度下降收敛
DOI：
10.48550/arxiv.2206.04172
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Joan Bruna
中科院分区：
文献类型：
--
作者：
Lei Chen;Joan Bruna
梯度下降（GD）是现代机器学习的强大主力，这要归功于它在高维空间中的可扩展性和效率。它找到局部最小值的能力只保证损失与Lipschitz梯度，在那里它可以被看作是一个“真正的”离散化的基础梯度流。然而，许多涉及过参数化模型的ML设置并不属于这类问题，这激发了超越所谓的“稳定边缘”（EoS）的研究，其中步长跨越与上述Lipschitz常数成反比的容许阈值。也许令人惊讶的是，GD已被经验观察到仍然收敛，而不管局部不稳定性和振荡行为。这种现象的初期理论分析主要集中在overparametrised制度，其中选择一个大的学习率的影响可能与“SharpnessMinimisation”隐式正则化的流形内的极小化，在适当的渐近限制。相比之下，在这项工作中，我们直接检查这种不稳定收敛的条件，专注于简单，但有代表性的学习问题。具体而言，我们描述了一个局部条件，涉及三阶导数，稳定振荡的GD以上的EOS，并利用这种属性在师生设置，人口损失。最后，专注于矩阵分解，我们建立了一个非渐近的“局部隐式偏置”的GD以上的EoS，准对称初始化收敛到对称的解决方案-其中锐度是最小的所有极小化。
Gradient Descent (GD) is a powerful workhorse of modern machine learning thanks to its scalability and efficiency in high-dimensional spaces. Its ability to find local minimisers is only guaranteed for losses with Lipschitz gradients, where it can be seen as a ‘bona-fide’ discretisation of an underlying gradient flow. Yet, many ML setups involving overparametrised models do not fall into this problem class, which has motivated research beyond the so-called “Edge of Stability” (EoS), where the step-size crosses the admissibility threshold inversely proportional to the Lipschitz constant above. Perhaps surprisingly, GD has been empirically observed to still converge regardless of local instability and oscillatory behavior. The incipient theoretical analysis of this phenomena has mainly focused in the overparametrised regime, where the effect of choosing a large learning rate may be associated to a ‘SharpnessMinimisation’ implicit regularisation within the manifold of minimisers, under appropriate asymptotic limits. In contrast, in this work we directly examine the conditions for such unstable convergence, focusing on simple, yet representative, learning problems. Specifically, we characterize a local condition involving third-order derivatives that stabilizes oscillations of GD above the EoS, and leverage such property in a teacher-student setting, under population loss. Finally, focusing on Matrix Factorization, we establish a non-asymptotic ‘Local Implicit Bias’ of GD above the EoS, whereby quasi-symmetric initializations converge to symmetric solutions — where sharpness is minimum amongst all minimisers.
大学习率抑制同质性：收敛和平衡效应
DOI：
--
发表时间：
2022
期刊：
The International Conference on Learning Representations
影响因子：
--
作者：
Wang, Yuqing;Chen, Minshuo;Zhao, Tuo;Tao, Molei
通讯作者：
Tao, Molei
DOI：
--
发表时间：
2022
期刊：
PMLR
影响因子：
--
作者：
Ahn, Kwangjun;Zhang, Jingzhao;Sra, Suvrit
通讯作者：
Sra, Suvrit