Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion
Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion
复制标题
DOI：
10.48550/arxiv.2208.11246
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
G. Zhang;Hong-Ming Chiu;Richard Y. Zhang
中科院分区：
文献类型：
--
作者：
G. Zhang;Hong-Ming Chiu;Richard Y. Zhang
矩阵补全问题寻求从其单个元素的观测恢复低秩$r\ll d$的$d\times d$地面真值矩阵。现实世界中的矩阵补全通常是一个大规模的优化问题，$d$如此之大，以至于即使是最简单的全维向量运算，时间复杂度为O（d）$，也变得非常昂贵。随机梯度下降（SGD）是少数几个能够大规模解决矩阵完备化的算法之一，也可以自然地处理不断发展的地面事实上的流数据。不幸的是，当底层的地面真值是病态的时，SGD经历了戏剧性的减速;它需要至少$O（\kappa\log（1/\k））$迭代来获得$\k $-接近条件数为$\kappa$的地面真值矩阵。在本文中，我们提出了一个预处理版本的SGD，保留了所有有利的实用品质的SGD大规模在线优化，同时也使其不可知的$\kappa$。对于一个对称的地面真理和均方根误差（RMSE）的损失，我们证明了预处理SGD收敛到$\kappa $-精度在$O（\log（1/\kappa））$迭代，快速的线性收敛速度，如果地面真理是完美的条件与$\kappa=1$。在我们的实验中，我们观察到MovieLens 25 M数据集上的项目-项目协同过滤通过成对排序损失的类似加速，其中有1亿个训练对和1000万个测试对。[See https：//github.com/Hong-Ming/ScaledSGD上的支持代码。
The matrix completion problem seeks to recover a $d\times d$ ground truth matrix of low rank $r\ll d$ from observations of its individual elements. Real-world matrix completion is often a huge-scale optimization problem, with $d$ so large that even the simplest full-dimension vector operations with $O(d)$ time complexity become prohibitively expensive. Stochastic gradient descent (SGD) is one of the few algorithms capable of solving matrix completion on a huge scale, and can also naturally handle streaming data over an evolving ground truth. Unfortunately, SGD experiences a dramatic slow-down when the underlying ground truth is ill-conditioned; it requires at least $O(\kappa\log(1/\epsilon))$ iterations to get $\epsilon$-close to ground truth matrix with condition number $\kappa$. In this paper, we propose a preconditioned version of SGD that preserves all the favorable practical qualities of SGD for huge-scale online optimization while also making it agnostic to $\kappa$. For a symmetric ground truth and the Root Mean Square Error (RMSE) loss, we prove that the preconditioned SGD converges to $\epsilon$-accuracy in $O(\log(1/\epsilon))$ iterations, with a rapid linear convergence rate as if the ground truth were perfectly conditioned with $\kappa=1$. In our experiments, we observe a similar acceleration for item-item collaborative filtering on the MovieLens25M dataset via a pair-wise ranking loss, with 100 million training pairs and 10 million testing pairs. [See supporting code at https://github.com/Hong-Ming/ScaledSGD.]