GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra
Pratik Rathore, Zachary Frangella, Parth Nobel, Xuning Hu, Madeleine Udell
cs.LG · math.OC · stat.ML
Quick verdict
rlaopt packages GPU Nyström-preconditioned CG/ADMM/SAPPHIRE behind a CVXPY-like syntax; benchmarks are honest but SAPPHIRE trails JAXopt; GeNIOS unbenchmarked.
Summary
The paper introduces rlaopt, an open-source PyTorch package for large-scale optimization built on randomized numerical linear algebra (RandNLA). It provides three GPU-enabled solvers — NyströmPCG for symmetric positive-definite linear systems, NysADMM for constrained convex problems via operator splitting, and SAPPHIRE for preconditioned stochastic variance-reduced optimization — behind a CVXPY-inspired modeling language that automatically decomposes problems for the chosen solver and supports differentiation through solver iterations for tasks like hyperparameter tuning. Experiments are unusually candid: on synthetic ridge problems up to n=p=2^16, NyströmPCG beats CG by up to 7.23x on GPU when spectra decay fast and regularization is weak (but only 0.81x in the opposite regime), with 57-128x GPU-over-CPU speedups. On bounded multinomial logistic regression, SAPPHIRE is outperformed by JAXopt's APG and L-BFGS-B even with JIT disabled. On bounded elastic net, GPU NysADMM is the only solver to finish two large dense instances (~1.66M x 1000 and ~464K x 4367) where SCS/Clarabel fail, while conic solvers win on sparse data. Main limitations: the SAPPHIRE advantage claimed for settings where full gradients are expensive is never demonstrated, GeNIOS — the direct ancestor of the NysADMM implementation — is not benchmarked, CPU NysADMM timed out on all datasets (so GPU speedups are lower bounds), and the differentiable-solver demo is toy-scale (29 training points).
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- rlaopt unifies GPU-enabled RandNLA solvers (NyströmPCG, NysADMM, SAPPHIRE) behind a CVXPY-like modeling language with automatic problem decomposition and differentiable solver iterations.
- Randomized Nyström preconditioning helps CG exactly when spectra decay fast and regularization is weak: 7.23x speedup at alpha=2, lambda=1e-6, but only 0.81x at alpha=0.5, lambda=1e-2 (n=p=2^16, GPU).
- GPU execution yields 57–128x speedups for NyströmPCG on large dense ridge problems, and GPU NysADMM is the only tested solver to finish two large dense bounded elastic-net instances (acsincome-rf ~3093 s; yearpredictionmsd-rf ~811 s).
- SAPPHIRE benefits from GPU (3.23x–>7.35x) but is outperformed by JAXopt APG and L-BFGS-B on every multinomial instance it solves, even with JIT disabled.
Strengths
Unusually honest negative results
Section 6 explicitly reports that SAPPHIRE loses to JAXopt APG on all three GPU instances it solves, that JIT-on baselines are an order of magnitude faster (Fig. 16), that conic solvers beat NysADMM on sparse data (e2006: 53 s vs timeout; realsim: 8 s vs 579 s), and Fig. 2 shows preconditioning hurting (0.81x) in the easy regime.
Rigorous, transparent evaluation protocol
Common accuracy checks independent of native stopping criteria (B.2: relative residual <=1e-6 ridge; stationarity <=1e-4, feasibility <=1e-6 bounded problems), tolerance calibration (B.3, Table 12), documented rerun policy (13 LSQR/LSMR reruns at 1e-10; SCS-direct-GPU honestly reclassified as timeout), pinned software revisions (Table 13).
Controlled characterization of when preconditioning pays
Complete solver specification enabling reimplementation
Automatic problem decomposition machinery
Weaknesses
SAPPHIRE's value proposition is asserted, not shown
GeNIOS absent from benchmarks despite direct lineage
CPU reference missing for the flagship elastic-net result
Differentiability demonstrated only at toy scale
Intro framing slightly overclaims GPU novelty
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a software paper introducing rlaopt 0.1.0, a PyTorch package for GPU-accelerated large-scale optimization using randomized numerical linear algebra (RandNLA). It ships three solver families: NyströmPCG for symmetric positive-definite linear systems, NysADMM for constrained composite convex problems (ADMM with Nyström-preconditioned inexact x-subproblems), and SAPPHIRE for preconditioned stochastic variance-reduced ERM. A DCP/CVXPY-inspired modeling language (Section 4, Table 1 atoms) performs automatic smooth/nonsmooth partitioning and consensus-form splitting (Section 5), and solvers support backpropagation through iterations when `detach=False` (Section 4.2). Central claims: (i) the package closes a gap between RandNLA algorithms and usable GPU implementations; (ii) randomized preconditioning pays off precisely when spectra decay fast and regularization is weak; (iii) GPU execution yields order-of-magnitude speedups; (iv) NysADMM uniquely handles large dense constrained problems. Claim (i) is softened by the paper's own related work (GPU FALKON, GPyTorch, cuPDLP, cuClarabel), so the defensible novelty is the unified modeling-plus-solving combination, not GPU support per se.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is rlaopt and what can it solve?
rlaopt is an open-source, Apache-licensed Python package (v0.1.0 on PyPI, from Stanford's Udell group) built on PyTorch for large-scale optimization using randomized linear algebra on CPU or GPU. It solves symmetric positive-definite linear systems (Nyström-preconditioned conjugate gradient), constrained convex problems (NysADMM), and regularized empirical risk minimization (SAPPHIRE). Problems are written in a CVXPY-like mathematical syntax, and solvers optionally support automatic differentiation through their iterations for hyperparameter tuning.
When does Nyström preconditioning actually speed up conjugate gradient?
Per this paper's controlled synthetic experiments, when the matrix spectrum decays quickly and regularization is weak. At n=p=2^16 on GPU, NyströmPCG was 7.23x faster than CG with fast decay (alpha=2) and weak regularization (lambda=1e-6), but only 0.81x (i.e., slightly slower) with slow decay (alpha=0.5) and strong regularization (lambda=1e-2). Preconditioner construction time is included in these numbers.
Is rlaopt faster than CVXPY-style conic solvers like SCS and Clarabel, or than JAXopt?
It depends on the problem. On large dense bounded elastic-net problems (~1.66M x 1000 and ~464K x 4367), GPU NysADMM was the only solver to finish, while SCS/Clarabel ran out of memory or timed out. On sparse problems, conic solvers won decisively (e.g., SCS-direct solved e2006 in 53 s vs NysADMM's timeout). On bounded multinomial logistic regression, JAXopt's APG and L-BFGS-B beat rlaopt's SAPPHIRE on every dataset SAPPHIRE solved, even with JIT disabled.
Does rlaopt support differentiating through the solver?
Yes. Solvers are implemented functionally in PyTorch, and passing detach=False enables backpropagation through the optimization iterations, so outer objectives (e.g., validation loss for tuning a regularization parameter) can be optimized by gradient descent. The paper demonstrates this only on a small lasso problem (29 training points, 26 features); large-scale behavior of the differentiable path is not evaluated.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figure interiors are extracted as flattened/garbled text (axis labels, speedup grids); quantitative figure claims here rely on the prose restatements in Sections 6.1–6.4 and Fig. 15/16 captions, which are internally consistent.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.