Timezone: »
Poster
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
-
2018 Poster: Interactive Structure Learning with Structural Query-by-Committee »
Christopher Tosh · Sanjoy Dasgupta -
2018 Spotlight: Interactive Structure Learning with Structural Query-by-Committee »
Christopher Tosh · Sanjoy Dasgupta -
2016 Poster: An algorithm for L1 nearest neighbor search via monotonic embedding »
Xinan Wang · Sanjoy Dasgupta -
2015 Poster: Scalable Semi-Supervised Aggregation of Classifiers »
Akshay Balsubramani · Yoav Freund -
2015 Spotlight: Scalable Semi-Supervised Aggregation of Classifiers »
Akshay Balsubramani · Yoav Freund -
2014 Poster: Rates of Convergence for Nearest Neighbor Classification »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2014 Spotlight: Rates of Convergence for Nearest Neighbor Classification »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2010 Poster: Rates of convergence for the cluster tree »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2009 Poster: A Parameter-free Hedging Algorithm »
Kamalika Chaudhuri · Yoav Freund · Daniel Hsu -
2007 Spotlight: A general agnostic active learning algorithm »
Sanjoy Dasgupta · Daniel Hsu · Claire Monteleoni -
2007 Session: Session 3: Theory and Sequential Decision Making »
Sanjoy Dasgupta -
2007 Poster: A general agnostic active learning algorithm »
Sanjoy Dasgupta · Daniel Hsu · Claire Monteleoni -
2007 Poster: Learning the structure of manifolds using random projections »
Yoav S Freund · Sanjoy Dasgupta · Mayank Kabra · Nakul Verma -
2007 Poster: A learning framework for nearest neighbor search »
Lawrence Cayton · Sanjoy Dasgupta