How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization
How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization
复制标题
DOI：
--
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Shivam Garg;S. Vempala
中科院分区：
文献类型：
--
作者：
Shivam Garg;S. Vempala
梯度下降在ML中的成功，特别是在学习神经网络方面的成功是显着和鲁棒的。在大脑如何学习的背景下，梯度下降的一个方面在生物学上似乎很难实现（如果不是难以置信的话），那就是它的更新依赖于通过相同的连接从后面的层到前面的层的反馈。这种双向连接在大脑网络中相对较少，即使存在互惠连接，它们也可能不是等权重的。随机反馈比对（Lillicrap等人，2016），其中后向权重是随机和固定的，已经被提出作为生物合理的替代方案，并被发现是有效的经验。我们研究了反馈对齐（FA）如何以及何时工作，重点是分层结构中最基本的问题之一-低秩矩阵分解。在这个问题中，给定一个矩阵Y_{n\times m}$，目标是找到一个低秩分解Z_{n \times r}W_{r \times m}$，使误差ZW-Y\|_F$最小化。梯度下降最优地解决了这个问题。我们证明了FA收敛到最优解时，$r\ge \mbox{rank}（Y）$。我们还阐明了FA是如何工作的。根据经验观察到，前向权重矩阵和（随机）反馈矩阵在FA更新期间变得更接近。我们的分析严格推导出这种现象，并显示它如何促进收敛的FA*，一个密切相关的变体FA。我们还表明，FA可以远离最优时，$r<\mbox{rank}（Y）$。这是梯度下降和FA之间的第一个可证明的分离结果。此外，当梯度下降法和FA法的误差ZW-YF近似相等时，它们的表示几乎是正交的.作为推论，当训练输入是各向同性的，并且输出是输入的线性函数时，这些结果也适用于训练两层线性神经网络。
The success of gradient descent in ML and especially for learning neural networks is remarkable and robust. In the context of how the brain learns, one aspect of gradient descent that appears biologically difficult to realize (if not implausible) is that its updates rely on feedback from later layers to earlier layers through the same connections. Such bidirected links are relatively few in brain networks, and even when reciprocal connections exist, they may not be equi-weighted. Random Feedback Alignment (Lillicrap et al., 2016), where the backward weights are random and fixed, has been proposed as a bio-plausible alternative and found to be effective empirically. We investigate how and when feedback alignment (FA) works, focusing on one of the most basic problems with layered structure -- low-rank matrix factorization. In this problem, given a matrix $Y_{n\times m}$, the goal is to find a low rank factorization $Z_{n \times r}W_{r \times m}$ that minimizes the error $\|ZW-Y\|_F$. Gradient descent solves this problem optimally. We show that FA converges to the optimal solution when $r\ge \mbox{rank}(Y)$. We also shed light on how FA works. It is observed empirically that the forward weight matrices and (random) feedback matrices come closer during FA updates. Our analysis rigorously derives this phenomenon and shows how it facilitates convergence of FA*, a closely related variant of FA. We also show that FA can be far from optimal when $r<\mbox{rank}(Y)$. This is the first provable separation result between gradient descent and FA. Moreover, the representations found by gradient descent and FA can be almost orthogonal even when their error $\|ZW-Y\|_F$ is approximately equal. As a corollary, these results also hold for training two-layer linear neural networks when the training input is isotropic, and the output is a linear function of the input.