Faster Principal Component Regression and Stable Matrix Chebyshev Approximation

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.

arXiv commenttitle changed and minor revisions

References in corpus (6)

• Numerical Methods for the QCD Overlap Operator: I. Sign-Function and Error Bounds
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain
• Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
• Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations

Cited by in corpus (2)

• The ZipML Framework for Training Models with End-to-End Low Precision: The Cans, the Cannots, and a Little Bit of Deep Learning
• Error bounds for Lanczos-based matrix function approximation