Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
Authors: Michal Dereziński, Daniel LeJeune, Deanna Needell, Elizaveta Rebrova
JMLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main technical contribution is the new analysis of the first and second moments of the random projection matrix that arises in Sketch-and-Project... Our fine-grained analysis is well-motivated by many established statistical models of data matrices... Our main result shows that the O(κℓ n2) time complexity of iteratively solving a linear system can be directly improved... Our algorithms are built on the Sketch-and-Project framework... Our main technical contributions are new sharp characterizations of the first and second matrix moments of P for a class of ultra-sparse sketching matrices S... In this paper, we developed a nuanced framework for analyzing iterative linear system solvers that allows us to obtain sharper convergence guarantees than classical perspectives. |
| Researcher Affiliation | Academia | Micha l Derezi nski EMAIL 2260 Hayward St., Department of Electrical Engineering and Computer Science University of Michigan, Ann Arbor, MI, 48109 USA Daniel Le Jeune EMAIL 390 Jane Stanford Way, Department of Statistics Stanford University, Palo Alto, CA, 94305 USA Deanna Needell EMAIL 520 Portola Plaza, Department of Mathematics University of California, Los Angeles, CA, 90095 USA Elizaveta Rebrova EMAIL 98 Charlton St., Department of Operations Research and Financial Engineering Princeton University, Princeton, NJ, 08540 USA |
| Pseudocode | Yes | Algorithm 1 Sketch-and-Project with Nesterov s acceleration 1: Input: matrix A Rm n, vector b Rm, p.d. matrix B Rn n, sketch size k, iterate x0, iteration tmax, β = 1 q µ ν , γ = 1 µν , α = 1 1+γν ; 3: for t = 0, 1, . . . , (tmax 1) do 4: yt αvt + (1 α)xt; 5: Generate sketching matrix S; 6: Solve (SAB 1A S )ut = SAyt Sb for ut Possibly inexactly, see Section 7 7: wt B 1A S ut; 8: xt+1 yt wt; xt+1 = argminx x yt B s.t. SAx = Sb 9: vt+1 βvt + (1 β)yt γwt; 10: end for 11: return x = xtmax; Solves Ax = b. |
| Open Source Code | No | The paper does not contain any explicit statement about making the code available, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper discusses various machine learning tasks and models (e.g., "least squares," "kernel ridge regression," "spiked covariance model") and theoretical properties of data matrices. However, it does not describe any experiments using specific datasets, nor does it provide access information for any dataset. The paper mentions "real-world matrices" and "data" in a general context but does not use them for evaluation. |
| Dataset Splits | No | The paper focuses on theoretical algorithmic analysis and does not conduct empirical experiments with datasets. Therefore, there is no mention of training/test/validation splits. |
| Hardware Specification | No | The paper focuses on theoretical algorithmic analysis and does not describe any empirical experiments. Consequently, no specific hardware details (like GPU models, CPU types, or cloud resources) are mentioned. |
| Software Dependencies | No | The paper primarily presents theoretical work and algorithms. There are no mentions of specific software packages or libraries with version numbers used for implementation or experimentation. |
| Experiment Setup | No | The paper focuses on theoretical analysis and algorithm design, not empirical experimentation. As such, there are no details regarding hyperparameter values, model initialization, or training schedules. |