Timezone: »

The Fast Convergence of Incremental PCA
Akshay Balsubramani · Sanjoy Dasgupta · Yoav Freund

Sat Dec 07 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
We prove the first finite-sample convergence rates for any incremental PCA algorithm using sub-quadratic time and memory per iteration. The algorithm analyzed is Oja's learning rule, an efficient and well-known scheme for estimating the top principal component. Our analysis of this non-convex problem yields expected and high-probability convergence rates of $\tilde{O}(1/n)$ through a novel technique. We relate our guarantees to existing rates for stochastic gradient descent on strongly convex functions, and extend those results. We also include experiments which demonstrate convergence behaviors predicted by our analysis.

Author Information

Akshay Balsubramani (Ucsd)
Sanjoy Dasgupta (UC San Diego)
Yoav Freund (UC San Diego)

More from the Same Authors