Skip to yearly menu bar Skip to main content


Poster

Faster Principal Component Regression and Stable Matrix Chebyshev Approximation

Zeyuan Allen-Zhu · Yuanzhi Li

Gallery #44

Abstract: We solve principal component regression (PCR), up to a multiplicative accuracy $1+\gamma$, by reducing the problem to $\tilde{O}(\gamma^{-1})$ black-box calls of ridge regression. Therefore, our algorithm does not require any explicit construction of the top principal components, and is suitable for large-scale PCR instances. In contrast, previous result requires $\tilde{O}(\gamma^{-2})$ such black-box calls. We obtain this result by developing a general stable recurrence formula for matrix Chebyshev polynomials, and a degree-optimal polynomial approximation to the matrix sign function. Our techniques may be of independent interests, especially when designing iterative methods.

Live content is unavailable. Log in and register to view live content