Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
This improves efficiency for large-scale PCR problems, though it is incremental as it builds on existing ridge regression methods.
The paper tackles principal component regression (PCR) by reducing it to fewer black-box ridge regression calls, achieving a multiplicative accuracy of 1+γ with Õ(γ⁻¹) calls, compared to previous Õ(γ⁻²) calls, without explicitly computing principal components.
We solve principal component regression (PCR), up to a multiplicative accuracy $1+γ$, by reducing the problem to $\tilde{O}(γ^{-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}(γ^{-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.