证明Nesterov加速梯度可显著提升矩阵分解与线性网络的收敛速度。
Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks
- 采用非平衡初始化，使梯度下降和NAG方法更高效。
- NAG实现O(κ log(1/ε))迭代复杂度，为当前最优。
- 适用于低宽网络，无需依赖输入数据的条件数。
研究矩形矩阵分解这一典型非凸优化问题的一阶方法收敛速率。给定一个秩为r的矩阵A∈ℝ^{m×n}，我们证明梯度下降（GD）可在T=O(κ² log(1/ε))次迭代内以高概率找到一对ε-最优解X_T∈ℝ^{m×d}和Y_T∈ℝ^{n×d}（d≥r），满足‖X_T Y_T^⊤ - A‖_F ≤ ε‖A‖_F，其中κ为A的条件数。进一步证明，Nesterov加速梯度（NAG）达到O(κ log(1/ε))的迭代复杂度，是目前矩形矩阵分解一阶方法的最佳已知结果。不同于现有文献中的小规模平衡随机初始化，本文采用非平衡初始化：X₀较大，Y₀为0。该初始化及分析可推广至线性神经网络，证明在仅需网络宽度≥输出标签矩阵的秩时，NAG仍能实现加速线性收敛。此前同类结果要求过大的网络宽度，且额外依赖输入数据矩阵的条件数与秩。
原文摘要 · Abstract (English)
We study the convergence rate of first-order methods for rectangular matrix factorization, which is a canonical nonconvex optimization problem. Specifically, given a rank-$r$ matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$, we prove that gradient descent (GD) can find a pair of $ε$-optimal solutions $\mathbf{X}_T\in\mathbb{R}^{m\times d}$ and $\mathbf{Y}_T\in\mathbb{R}^{n\times d}$, where $d\geq r$, satisfying $\lVert\mathbf{X}_T\mathbf{Y}_T^\top-\mathbf{A}\rVert_\mathrm{F}\leqε\lVert\mathbf{A}\rVert_\mathrm{F}$ in $T=O(κ^2\log\frac{1}ε)$ iterations with high probability, where $κ$ denotes the condition number of $\mathbf{A}$. Furthermore, we prove that Nesterov's accelerated gradient (NAG) attains an iteration complexity of $O(κ\log\frac{1}ε)$, which is the best-known bound of first-order methods for rectangular matrix factorization. Different from small balanced random initialization in the existing literature, we adopt an unbalanced initialization, where $\mathbf{X}_0$ is large and $\mathbf{Y}_0$ is $0$. Moreover, our initialization and analysis can be further extended to linear neural networks, where we prove that NAG can also attain an accelerated linear convergence rate. In particular, we only require the width of the network to be greater than or equal to the rank of the output label matrix. In contrast, previous results achieving the same rate require excessive widths that additionally depend on the condition number and the rank of the input data matrix.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。