Convergence Analysis for Biological Oja's Rule in Solving Streaming PCASpeaker: Brabeeba Wang
Title: Convergence Analysis for Biological Oja's Rule in Solving Streaming PCA
Date: 19 Aug 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 323
Audience background: Probability
Abstract: Biological Oja’s rule is a biologically feasible algorithm using Hebbian-type synaptic update that solves the streaming PCA problem. Despite being one of the most fundamental neural algorithms, there have 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 convergence rate bound for biological Oja’s rule in solving streaming PCA. The complexity we get is only 1/eps away from the optimal streaming PCA algorithm where eps is the multiplicative error. 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 ODE and dynamical systems. 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.