Timezone: »

Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
Yujia Jin · Aaron Sidford

Wed Dec 11 10:35 AM -- 10:40 AM (PST) @ West Ballroom A + B

Given a n-by-d data matrix A, principal component projection (PCP) and principal component regression (PCR), i.e. projection and regression restricted to the top-eigenspace of A, are fundamental problems in machine learning, optimization, and numerical analysis. In this paper we provide the first algorithms that solve these problems in nearly linear time for fixed eigenvalue distribution and large n. This improves upon previous methods which had superlinear running times when either the number of top eigenvalues or gap between the eigenspaces were large.

We achieve our results by applying rational polynomial approximations to reduce the problem to solving asymmetric linear systems which we solve by a variant of SVRG. We corroborate these findings with preliminary empirical experiments.

Author Information

Yujia Jin (Stanford University)
Aaron Sidford (Stanford)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors