Sequential Preconditioned Conjugate Gradient Method for Linear Statistical Models
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).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Models
We propose a novel randomized framework for the estimation problem of large-scale linear statistical models, namely Sequential Least-Squares Estimators with Fast Randomized Sketching (SLSE-FRS), which integrates Sketch-a…
An Efficient Multilevel Preconditioned Nonlinear Conjugate Gradient Method for Incremental Potential Contact
Incremental Potential Contact (IPC) guarantees intersection-free simulation but suffers from high computational costs due to the expensive Hessian assembly and linear solves required by Newton's method. While Preconditio…
Nonlinear Conjugate Gradients For Scaling Synchronous Distributed DNN Training
Nonlinear conjugate gradient (NLCG) based optimizers have shown superior loss convergence properties compared to gradient descent based optimizers for traditional optimization problems. However, in Deep Neural Network (D…
16kGeneral ClassificationLeveraging Operator Learning to Accelerate Convergence of the Preconditioned Conjugate Gradient Method
We propose a new deflation strategy to accelerate the convergence of the preconditioned conjugate gradient(PCG) method for solving parametric large-scale linear systems of equations. Unlike traditional deflation techniqu…
Multidirectional Conjugate Gradients for Scalable Bundle Adjustment
We revisit the problem of large-scale bundle adjustment and propose a technique called Multidirectional Conjugate Gradients that accelerates the solution of the normal equation by up to 61%. The key idea is that we enlar…