Chi Jin

activity

20142023

most citedHow to Escape Saddle Points Efficiently

229 citations · 2.2k across the 66 of their papers we have counts for

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2016★ 32 cited

Faster Eigenvector Computation via Shift-and-Invert Preconditioning

Dan Garber, Elad Hazan, Chi Jin +4

We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix $Σ$ -- i.e. computing a unit vector $x$ such that $x^{T} Σ x \geq (1 - ε) λ_{1} (Σ)$ …

cs.DS2015★ 14 cited

Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation

Chi Jin, Sham M. Kakade, Cameron Musco +2

We provide faster algorithms and improved sample complexities for approximating the top eigenvector of a matrix. Offline Setting: Given an $n \times d$ matrix $A$ , we show how to c…