arXiv:2411.15972cs.LGcs.SY2024-11被引 1

解析低秩矩阵分解的梯度流稳定性,揭示过参数化下的慢速收敛机制。

Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem

  • 通过非线性变量变换,将复杂动力系统分解为三个子系统。
  • 在过参数化下,目标矩阵主特征空间的Schur补以O(1/t)速率趋零。
  • 结合李雅普诺夫方法,证明其余部分指数收敛,适合研究过参数化学习动力学。

对称低秩矩阵分解是矩阵恢复和神经网络训练中的基础问题。尽管近期研究众多,但在过参数化情形(拟合秩高于目标矩阵真实秩)下,基于非凸因子化梯度下降法的训练动态仍不清晰。本文刻画了梯度流动力系统的平衡点,并分析其局部与全局稳定性。为实现精确的全局分析,引入非线性变量变换,使系统转化为三个子系统的级联结构,较原系统更简单。我们证明:目标矩阵主特征空间的Schur补遵循一个与其余动态解耦的自治系统。在过参数化情况下,该Schur补以O(1/t)速率趋于零,捕捉了由冗余参数引起的慢速动态。其余两个子系统通过李雅普诺夫方法证明指数收敛。通过分离快慢动态,本工作为局部搜索算法轨迹形状提供了新见解,并完整刻画了平衡点及其全局稳定性。此类基于非线性控制技术的分析,或可推广至其他过参数化问题。

原文摘要 · Abstract (English)

The symmetric low-rank matrix factorization serves as a building block in many learning tasks, including matrix recovery and training of neural networks. However, despite a flurry of recent research, the dynamics of its training via non-convex factorized gradient-descent-type methods is not fully understood especially in the over-parameterized regime where the fitted rank is higher than the true rank of the target matrix. To overcome this challenge, we characterize equilibrium points of the gradient flow dynamics and examine their local and global stability properties. To facilitate a precise global analysis, we introduce a nonlinear change of variables that brings the dynamics into a cascade connection of three subsystems whose structure is simpler than the structure of the original system. We demonstrate that the Schur complement to a principal eigenspace of the target matrix is governed by an autonomous system that is decoupled from the rest of the dynamics. In the over-parameterized regime, we show that this Schur complement vanishes at an $O(1/t)$ rate, thereby capturing the slow dynamics that arises from excess parameters. We utilize a Lyapunov-based approach to establish exponential convergence of the other two subsystems. By decoupling the fast and slow parts of the dynamics, we offer new insight into the shape of the trajectories associated with local search algorithms and provide a complete characterization of the equilibrium points and their global stability properties. Such an analysis via nonlinear control techniques may prove useful in several related over-parameterized problems.

矩阵分解梯度流过参数化稳定性分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。