Brabeeba Wang: The First at All-Time Convergence Analysis for Biological Oja's Rule to Solve Streaming PCA

Friday, October 11, 2019 - 1:00pm to 2:30pm
Brabeeba Wang

Biological Oja’s rule is a biologically feasible algorithm using Hebbian-type local synaptic update that solves the streaming PCA problem. Despite being one of the most fundamental neural algorithms, there has been very limited understanding in the convergence behavior of the biological Oja’s rule. Prior to this work, only convergence in the limit guarantee had been proved.  In this work, we prove the first at all time convergence rate bound for biological Oja’s rule in solving streaming PCA. The complexity we get is optimal in terms of eps, gap, delta where eps is the multiplicative error, gap is the difference between first two eigenvalues and delta is the failure probability. The for all time convergence should be surprising at first because it is hard to imagine a random walk stays at all time when the learning rate is constant. The analysis itself is also very interesting in the sense that we basically “discretize” the analysis of the continuous version of the biological Oja’s rule using tools from SDE, dynamical systems, and stopping time. We believe this general framework of transforming the analysis in the continuous dynamics to the discrete dynamics is of independent interest since it is powerful and has been highly underestimated.