Sequential Preconditioned Conjugate Gradient Method for Linear Statistical Models

Abstract

We propose a randomized iterative method for the ordinary least-squares estimation problem in large-scale linear statistical models, namely the Sequential Preconditioned Conjugate Gradient Method (SPCG). SPCG constructs a sequence of sketched least-squares subproblems with increasing sketch sizes, applies PCG as the inner solver, and warm-starts each subproblem from the previous solution. A final refinement stage is then performed on the full-scale problem. Since most iterations are carried out on smaller subproblems, the overall computational cost is significantly reduced. We establish the convergence theory, prove that SPCG attains OLS prediction accuracy, and derive per-subproblem iteration bounds and complexity estimates. Numerical experiments show that SPCG reaches the target prediction accuracy with fewer iterations and less CPU time than full-data PCG and Iterative Double Sketching (IDS).