How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization

The success of gradient descent in ML and especially for learning neural\nnetworks is remarkable and robust. In the context of how the brain learns, one\naspect of gradient descent that appears biologically difficult to realize (if\nnot implausible) is that its updates rely on feedback from later layers to\nearlier layers through the same connections. Such bidirected links are\nrelatively few in brain networks, and even when reciprocal connections exist,\nthey may not be equi-weighted. Random Feedback Alignment (Lillicrap et al.,\n2016), where the backward weights are random and fixed, has been proposed as a\nbio-plausible alternative and found to be effective empirically. We investigate\nhow and when feedback alignment (FA) works, focusing on one of the most basic\nproblems with layered structure -- low-rank matrix factorization. In this\nproblem, given a matrix $Y_{n\\times m}$, the goal is to find a low rank\nfactorization $Z_{n \\times r}W_{r \\times m}$ that minimizes the error\n$\\|ZW-Y\\|_F$. Gradient descent solves this problem optimally. We show that FA\nconverges to the optimal solution when $r\\ge \\mbox{rank}(Y)$. We also shed\nlight on how FA works. It is observed empirically that the forward weight\nmatrices and (random) feedback matrices come closer during FA updates. Our\nanalysis rigorously derives this phenomenon and shows how it facilitates\nconvergence of FA*, a closely related variant of FA. We also show that FA can\nbe far from optimal when $r < \\mbox{rank}(Y)$. This is the first provable\nseparation result between gradient descent and FA. Moreover, the\nrepresentations found by gradient descent and FA can be almost orthogonal even\nwhen their error $\\|ZW-Y\\|_F$ is approximately equal. As a corollary, these\nresults also hold for training two-layer linear neural networks when the\ntraining input is isotropic, and the output is a linear function of the input.\n