2021-07-21-huang21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Streaming k-PCA: Efficient guarantees for Oja’s algorithm, beyond rank-one updates	We analyze Oja’s algorithm for streaming $k$-PCA, and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. $d \times d$ symmetric matrices, we show that Oja’s algorithm can obtain an accurate approximation to the subspace of the top $k$ eigenvectors of their expectation using a number of samples that scales polylogarithmically with $d$. Previously, such a result was only known in the case where the updates have rank one. Our analysis is based on recently developed matrix concentration tools, which allow us to prove strong bounds on the tails of the random matrices which arise in the course of the algorithm’s execution.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	huang21a	0	Streaming k-PCA: Efficient guarantees for Oja’s algorithm, beyond rank-one updates	2463	2498	2463-2498	2463	false	Huang, De and Niles-Weed, Jonathan and Ward, Rachel	given family De Huang given family Jonathan Niles-Weed given family Rachel Ward	2021-07-21		Proceedings of Thirty Fourth Conference on Learning Theory	134	inproceedings	date-parts 2021 7 21	http://proceedings.mlr.press/v134/huang21a/huang21a.pdf