Pith. sign in

REVIEW 3 major objections 5 minor 2 cited by

GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Sketch-and-precondition with sparse sign sketches and LSQR is a practical, GPU-native route to large least-squares problems, and the paper's rejection-sampling sketch generator keeps the whole pipeline parallel.

desk verdict Solid GPU engineering paper on sparse sign sketch-and-precondition with a real contribution (rejection-sampling generator), undercut by an overstated strong-scaling claim that its own data contradict. read the letter →

arxiv 2506.03070 v2 pith:ROCDS4FV submitted 2025-06-03 cs.DS cs.DCcs.NAmath.NA

Tyler Chen , Pradeep Niroula , Archan Ray , Pragna Subrahmanya , Marco Pistoia , Niraj Kumar This is my paper
classification cs.DScs.DCcs.NAmath.NA MSC 65F1065F2065Y0568W20
keywords randomizednumericallinearalgebrasketch-and-preconditionsparsesignsketchesLSQRGPUparallelcomputingleastsquaresrejectionsamplingsubspaceembedding
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to show that the sketch-and-precondition recipe for overdetermined least squares, using sparse sign sketches and the LSQR iterative method, is especially well suited to GPU hardware. If that is right, a fast, black-box solver for very tall regression problems (millions of rows, hundreds to thousands of columns) could be assembled almost entirely from embarrassingly parallel operations. The authors contribute a rejection-sampling construction for sparse sign sketching matrices that is easy to parallelize, then benchmark the resulting solver on single- and multi-GPU systems. Their experiments indicate strong scaling through eight GPUs with no saturation, and weak-scaling communication costs that are mostly overlapped once two devices are used.

What carries the argument

The central object is the sparse sign sketching matrix $S \in \mathbb{R}^{d \times m}$ with sparsity parameter $\zeta$: each column is independent and contains exactly $\zeta$ random signs placed in uniformly random coordinates, scaled by $\sqrt{m/\zeta}$. The paper's implementation contribution is a rejection-sampling generator that draws $\zeta$ row indices per column with replacement, sorts each column, identifies duplicate indices, and resamples only those until every column is duplicate-free; since the probability a column is collision-free is at least $1-\zeta^2/d$, the method is efficient in the regimes recommended by theory. The sketch plays two roles in Algorithm 1: it builds the preconditioner $M = R^{-1}$ from the QR factorization of $SA$, and it supplies an initial guess by solving the sketched least-squares problem. Standard embedding arguments give $\mathrm{cond}(AM) \le (1+\eta)/(1-\eta)$ when $S$ has distortion $\eta$, and LSQR's convergence bound then converts this into an iteration count. The paper combines these facts with the empirical estimate $\eta \approx \sqrt{n/d}$ to obtain the runtime-balance model (4.1)-(4.2), which trades the $O(d n^2)$ preconditioner build against the per-iteration $O(\mathrm{nnz}(A))$ cost; the multi-GPU implementation distributes the tall matrix by rows so that vector additions and norms are local, and only matrix-vector products require communication.

What would settle it

Run the paper's heuristic on the $5e5\_500\_identity$ matrix (the first 500 columns of an identity matrix) with $\zeta = 8$ and $d/n$ around 100: the measured distortion is larger than $\sqrt{n/d}$, so the predicted LSQR iteration count from (4.1) is too low and the embedding dimension recommended by (4.2) will not be the runtime minimizer. A concrete check is whether the total runtime at that recommended $d$ is actually below the runtimes at neighboring values of $d$ on that matrix.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that sparse sign sketches are not just a theoretical shortcut but the right sketching distribution in the GPU regime. A sparse sign sketch has each column containing exactly $\zeta$ random signs in uniformly random coordinates, scaled by $\sqrt{m/\zeta}$; the paper shows such a matrix can be generated by a rejection-sampling scheme whose collision-free probability per column is at least $1 - \zeta^2/d$, making generation efficient in the recommended regime $d = O(n \log n)$, $\zeta = O(\log n)$. When the sketch is a subspace embedding with distortion $\eta$, the preconditioned matrix $AM$ has condition number at most $(1+\eta)/(1-\eta)$, and LSQR converges at the corresponding rate; the paper's experiments find that the Gaussian-like estimate $\eta \approx \sqrt{n/d}$ predicts convergence accurately on most fixed problems, even with $\zeta = 8$. The overall theoretical guarantee is that Algorithm 1 with sparse sign sketches and LSQR solves the regression problem to accuracy $\varepsilon$ in $\widetilde{O}((\mathrm{nnz}(A)+n^2)\log(1/\varepsilon)+n^3)$ operations, and the numerical work shows the same pipeline scales well across multiple GPUs.

Load-bearing premise

The load-bearing premise is that a sparse sign sketch with constant sparsity $\zeta$ behaves like a Gaussian sketch on any fixed problem, so that distortion $\eta \approx \sqrt{n/d}$ can be used to predict LSQR iteration counts and choose the embedding dimension; the paper's own experiments show this fails on structured examples such as the identity-like matrix, where small $\zeta$ and large $d$ give distortion worse than predicted.

Editorial extensions

If this is right

  • A GPU-resident least-squares solver for tall dense or sparse regression problems can be built around sparse sign sketches and LSQR, with strong scaling through at least eight GPUs and weak-scaling overhead mostly overlapped beyond two GPUs.
  • Sketch generation and application cost scale with $\zeta$ rather than $d$, so a small sparsity like $\zeta = 8$ or $12$ keeps the whole pipeline cheap while matching Gaussian-sketched distortion on most problems.
  • The embedding dimension can be selected from $n$, $m$, and the target accuracy via the Lambert-W balance in (4.2), eliminating hand-tuned sketch sizes on dense problems.
  • Other randomized linear-algebra algorithms that rely on sketching can reuse the same GPU-friendly sparse-sign generation and row-distributed matrix products, as the paper notes for randomized SVD and randomized Cholesky-QR settings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A coherence-aware version of the embedding-dimension heuristic could repair the identity-matrix failure mode: when the data matrix has near-standard-basis columns, the heuristic should force a larger $\zeta$ or larger $d$ than the $\sqrt{n/d}$ model suggests.
  • The rejection sampler's measured collision probability gives a cheap online signal for whether the current $(\zeta, d)$ pair is too aggressive, enabling a self-tuning sketch construction during the run.
  • The flattening strong-scaling curve points to the non-parallelized QR preconditioner build as the next bottleneck; overlapping or parallelizing that $O(d n^2)$ step is the natural route to near-perfect scaling.
  • A theoretical explanation of why constant-$\zeta$ sparse sign sketches track Gaussian distortion on typical data, which the paper explicitly leaves open, would turn the empirical parameter choice into a provable one.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. This paper presents a GPU implementation and benchmarking study of sketch-and-precondition for tall dense and sparse least-squares problems, using sparse sign sketches and LSQR. The contributions are a rejection-sampling method for generating sparse sign sketching matrices that exploits GPU-friendly primitives, a systematic experimental study of sketch distortion as a function of sparsity and embedding dimension, a heuristic for choosing the embedding dimension based on Gaussian-sketch asymptotics (Eqs. 4.1 and 4.2), and strong/weak scaling experiments on up to 8 A100 GPUs. The authors conclude that sketch-and-precondition with sparse sign sketches is particularly well-suited for GPUs and may be suitable for black-box least-squares solvers.

Significance. If the numerical claims hold, the paper makes a useful practical contribution: it provides one of the first systematic GPU-oriented studies of sparse sign sketching, with an embarrassingly parallel generation scheme, concrete implementation details (Algorithm 3), and extensive validation on real and synthetic matrices including a deliberately hard identity-like example. The experiments are carefully conducted (medians of 100 runs with 5-95% bands), and the paper is candid about the hard case and about the missing theory for zeta = O(1). The main qualifications are the overstated strong-scaling claim and the limited domain of the embedding-dimension heuristic; these do not negate the value of the benchmark data but they do require revision of the paper's central conclusions.

major comments (3)
  1. [Abstract, §2.3, §4.4.1] The paper repeatedly claims that strong scaling 'never saturates' (Abstract and §2.3), but §4.4.1 states that 'the total runtime begins to flatten out as the cost of the iterative method, which is parallelized, becomes small relative to the cost of the preconditioner build.' Since §3.3 and Appendix B indicate that the preconditioner build (QR factorization and R^{-1}) is not parallelized, Amdahl's law implies that total speedup is capped by the serial fraction. The data in Figure 6 therefore do not support the 'never saturate' claim; the claim should be corrected, and the paper should report parallel efficiency or the serial fraction for the preconditioner build.
  2. [§4.3, Eqs. (4.1)–(4.2)] The runtime heuristic assumes that sparse sign sketches achieve distortion eta ≈ sqrt(n/d) as in Gaussian theory. Figure 3 explicitly shows that this assumption fails for the 5e5_500_identity problem when zeta is small and d/n is large, and §C.3.1 confirms a spectral deviation for that problem. Equation (4.2) is therefore not a generally valid prescription for choosing d; it can under-predict the number of LSQR iterations and under-select the embedding dimension. The paper should state the regime of validity (e.g., matrices with 'nice' left singular vectors) and either test the heuristic on the identity-like case or exclude it from the generality claim.
  3. [§4.4.2, Figure 6] The weak-scaling experiment stacks copies of Asmall to form the larger problem, producing a block-diagonal data matrix. This structure makes communication patterns more favorable than for a general dense matrix of the same size, so the conclusion that 'communication overhead is mostly overlapped' is not established for general dense problems. The paper should acknowledge this limitation or run a weak-scaling test with a single unstructured matrix to support the conclusion.
minor comments (5)
  1. [§4.4.1] There is a typographical corruption in the sentence 'becomes small relative to the cost ofwow, the of the preconditioner build'; it should read 'becomes small relative to the cost of the preconditioner build.'
  2. [Figure 6 caption] The caption swaps the ideal scaling rates: for strong scaling the ideal rate is approximately 1/(#GPUs), while for weak scaling it is approximately 1; the paper states the opposite, and this should be corrected.
  3. [Appendix D.5.1] In the reorganized LSQR iteration, the displayed formulas contain typos: on line 4, beta_{t+1} = ||hat{u}_{t-1}|| should be beta_{t+1} = ||hat{u}_{t+1}||, and on line 6, alpha_{t=1} should be alpha_{t+1}.
  4. [§2.1, §3.1.2, §4.3] There are several minor typos: 'repsectively' in §2.1, 'primatives' in §3.1.2, and 'LQSR' in §4.3 should be 'LSQR'.
  5. [§4.3.2] The phrase 'a sequence of test matrices with height m = 6e5 and increasing with n ranging from 3e2 to 5e3' is unclear; it should say something like 'with height m = 6e5 and with n increasing from 3e2 to 5e3.'

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; central claims derive from external theory and cost models, with only a tangential self-citation and some internal reporting inconsistencies.

full rationale

The paper's central derivation chain is self-contained in the direction theory → implementation → benchmark. Theorem 2.1 is assembled from Proposition 2.6, an external subspace-embedding theorem due to Cohen, and Proposition 2.7, the standard LSQR error bound; no parameter is fitted from the paper's own experiments and no equation is defined in terms of the quantity it is used to predict. The convergence heuristic (4.1) is explicitly derived from Proposition 2.7 plus the asymptotic Gaussian-sketch distortion estimate η ≈ sqrt(n/d), as the text states: 'This estimate is obtained by using the convergence bound Proposition 2.7 for LSQR, and the condition number bound cond(AM) ≤ (1+η)/(1−η), and then estimating η ≈ sqrt(n/d).' Equation (4.2) is the closed-form minimizer of the resulting cost model. The subsequent experiments validate these predictions rather than being used to construct them, so the direction is not circular. The only self-citation is [CT24], used in Appendix D.2 to support a side remark that Lanczos/CG convergence is nearly deterministic for well-conditioned Wishart-type spectra; that claim is not load-bearing for the GPU-suitability conclusions and is accompanied by external references ([Dei+14; DT20]). The paper itself flags the main limitations: Section 5 states that 'a theoretical understanding for this is missing' for ζ = O(1) behavior, and Section 4.4.1's admission that 'the total runtime begins to flatten out... relative to the cost of the preconditioner build' conflicts with the abstract's 'never saturate' wording. Those are correctness/reporting concerns, not circularity: they do not make any prediction reduce to its input by construction. Overall, the strongest central claim is an empirical suitability claim checked by benchmarking against standard external problems (SuiteSparse, MNIST, synthetic), with no fitted parameter renamed as a prediction.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new entities. Its central claim rests on standard subspace embedding theory, one heuristic proxy for distortion, and a standard Krylov convergence bound. The only hand-chosen quantities are zeta and d, which are algorithmic hyperparameters, not fitted physical or empirical constants.

free parameters (2)
  • sparsity parameter zeta = 8, 12, 24
    Chosen by hand for the experiments; the paper notes that zeta = O(1) works in practice but gives no principled selection method.
  • embedding dimension d (as a multiple of n) = 8n to 12n in scaling tests; d/n from 1 to 100 in parameter sweeps
    Hand-set for most experiments or set via the heuristic (4.2), which itself is derived, not fitted to data.
assumptions (3)
  • standard math Sparse sign sketches with d = O(n log n) and zeta = O(log n) give a constant-distortion subspace embedding (Proposition 2.6 from [Coh15]).
    Invoked in Section 2.1 to justify Theorem 2.1; this is existing theory from the literature.
  • ad hoc to paper The Gaussian-sketch distortion estimate eta approximately sqrt(n/d) is a good proxy for sparse sign sketch distortion on most problems.
    Used in equations (4.1) and (4.2) to predict LSQR convergence and to select the embedding dimension. The paper itself shows the 5e5_500_identity matrix violates this, so it is a heuristic assumption local to this paper's runtime model.
  • domain assumption LSQR optimality and convergence bound (Proposition 2.7) holds in finite precision on GPU hardware.
    Standard Krylov subspace theory invoked in Section 2.2; finite-precision behavior is not re-validated here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches." pith.science (2026). https://pith.science/paper/ROCDS4FV

@misc{pith2026250603070,
  author       = {Pith},
  title        = {Pith review of: GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ROCDS4FV}},
  note         = {Machine review of arXiv:2506.03070}
}
read the original abstract

A litany of theoretical and numerical results have established the sketch-and-precondition paradigm as a powerful approach to solving large linear regression problems in standard computing environments. Perhaps surprisingly, much less work has been done on understanding how sketch-and-precondition performs on graphics processing unit (GPU) systems. We address this gap by benchmarking an implementation of sketch-and-precondition based on sparse sign-sketches on single and multi-GPU systems. In doing so, we describe a novel, easily parallelized, rejection-sampling based method for generating sparse sign sketches. Our approach, which is particularly well-suited for GPUs, is easily adapted to a variety of computing environments. Taken as a whole, our numerical experiments indicate that sketch-and-precondition with sparse sign sketches is particularly well-suited for GPUs, and may be suitable for use in black-box least-squares solvers.

Figures

Figures reproduced from arXiv: 2506.03070 by the authors.

Figure 1
Figure 1. Comparison of accuracy/runtime for a direct solver ( ), iterative method without a preconditioner ( ), and sketch-and-precondition ( ), on a dense, moderately sized, moderately conditioned least squares problem (𝑚 = 105 , 𝑛 = 6 × 102 , cond(A) = 103 ). While sketch-and-precondition requires some time to construct the preconditioner (indicated by the vertical dotted line), this is more than made up for by the improve… view at source ↗
Figure 2
Figure 2. Time to generate and apply the sparse sign sketching matrix as a function of embedding dimension, for several choices of sparsity: 𝜁 = 8 ( ), 𝜁 = 12 ( ), 𝜁 = 24 ( ). 4.2.2 Distortion Next, we study how the distortion of the sketch (see Definition 2.3) changes with the parameters 𝜁 and 𝑑. In [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Distortion as a function of relative embedding dimension 𝑑/𝑛 for sparse sign sketches with several choices of sparsity: 𝜁 = 8 ( ), 𝜁 = 12 ( ), 𝜁 = 24 ( ). Note that sparse sketches behave remarkably similarly to the asymptotic theory for Gaussian sketches which have distortion √︁ 𝑛/𝑑 ( ). 4.3 Embedding dimension As observed in [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Total runtime of sketch-and-precondition (𝜁 = 12) as a function of embedding dimension ( ) and individual components: iteration time ( ), preconditioner build time ( ), sketch apply time ( ), and sketch generate time ( ). 4.3.2 Selecting the embedding dimension The ups…
Figure 5
Figure 5. Figure 5: Comparison of procedures for selecting the sketch-and-precondition (𝜁 = 12) embedding dimension for 𝑚 = 6 × 105 and 𝑛 ranging from 3 × 102 to 5 × 103 : fixed embedding dimension (left) and heuristic optimization (4.2) (right). The top panels show the total runtime ( ) …
Figure 6
Figure 6. Figure 6: Strong and weak scaling experiment indicating total runtime ( ), total iteration time ( ), sketch generate/apply time ( ), and preconditioner build time ( ). Ideal scaling rate ∼1/(# GPUs) for weak scaling and (∼1) for strong scaling ( ). less than the ideal 2× speedup…
Figure 7
Figure 7. Figure 7: Time to generate (single GPU) and apply sketching matrices. Gaussian ( ), subsampled trig ( ), and sparse sign sketch with 𝜁 = 8 ( ) and 𝜁 = 24 ( ). For large embedding dimension, the Gaussian sketch required too much memory to generate, and is therefore not reported. …
Figure 8
Figure 8. Figure 8: Distortion as a function of relative embedding dimension 𝑑/𝑛 for different sketching distributions: Gaussian ( ), subsampled trig ( ), and sparse sign sketch with 𝜁 = 8 ( ) and 𝜁 = 24 ( ). All sketches behave remarkably similarly to the asymptotic theory for Gaussian s…
Figure 9
Figure 9. Figure 9: Spectrum of sketched subspace SU on two test problems for various sketching distributions: Gaussian ( ), subsampled trig ( ), and sparse sign sketch with 𝜁 = 8 ( ) and 𝜁 = 24 ( ). Each histogram is constructed using 500 independent sketches. D Krylov subspace methods I…
Figure 10
Figure 10. Figure 10: Error as a function of runtime for various iterative methods: LSQR ( ), Gradient Descent ( ), and Heavy ball momentum ( ). 29 [PITH_FULL_IMAGE:figures/full_fig_p029_10.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Faster Linear Algebra Algorithms with Structured Random Matrices

    cs.DS 2025-08 accept novelty 8.0 of 10

    Randomized sketching needs only the new OSI property, not the full subspace embedding, and multiple structured matrices satisfy it with near-optimal cost.

  2. Distributed Sketching on Data Partitions for OLS Regression

    cs.LG 2026-07 conditional novelty 5.0 of 10

    Partitioned Gaussian sketching for distributed OLS has exact excess loss B_θ that is comparable to whole-data sketching when subset-covariance divergence D is near d.

Reference graph

Works this paper leans on

5 extracted references · 1 canonical work pages · cited by 2 Pith papers

  1. [161]

    Fast and Forward Stable Randomized Algorithms for Linear Least-Squares Problems

    issn: 1552-4485. doi: 10.1090/qam/1574. [EMN24] Ethan N. Epperly, Maike Meier, and Yuji Nakatsukasa. Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers. 2024. arXiv: 2406.03468 [math.NA]. [Epp23] Ethan Epperly. Which sketch should I use? 2023. [Epp24] Ethan N. Epperly. “Fast and Forward Stable Randomized A...

    arXiv 2024

  2. [509]

    Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality

    doi: 10.1016/j.procs.2012.04.009. [IM98] Piotr Indyk and Rajeev Motwani. “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality”. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC ’98. Dallas, Texas, USA: Association for Computing Machinery, 1998, pp. 604–613. isbn: 0897919629. doi: 10.1145/276698.276...

    arXiv 2020

  3. [1236]

    Mixed Precision Randomized Low-Rank Approximation with GPU Tensor Cores

    issn: 1095-7197. doi: 10.1137/090767911. [Bab+24] Marc Baboulin et al. “Mixed Precision Randomized Low-Rank Approximation with GPU Tensor Cores”. In: Euro-Par 2024: Parallel Processing. Springer Nature Switzerland, 2024, pp. 31–44. isbn: 9783031695834. doi: 10.1007/978-3-031-69583-4_3 . [Bal22] Oleg Balabanov. Randomized Cholesky QR factorizations. 2022. ...

    arXiv 2024

  4. [1804]

    A Mixed Precision Randomized Preconditioner for the LSQR Solver on GPUs

    issn: 1095-7162. doi: 10.1137/23m1616790. [Epp25] Ethan Epperly. Note to self: How accurate is sketch and solve?2025. [FGL21] Yuwei Fan, Yixiao Guo, and Ting Lin. A Novel Randomized XR-Based Preconditioned CholeskyQR Algorithm. 2021. arXiv: 2111.11148 [math.NA]. [Geo+23] Vasileios Georgiou et al. “A Mixed Precision Randomized Preconditioner for the LSQR S...

    arXiv 2011

  5. [1879]

    A fast randomized algorithm for overdetermined linear least-squares regression

    issn: 1532-4435. [RT08] Vladimir Rokhlin and Mark Tygert. “A fast randomized algorithm for overdetermined linear least-squares regression”. In: Proceedings of the National Academy of Sciences 105.36 (Sept. 2008), pp. 13212–13217. issn: 1091-6490. doi: 10.1073/pnas.0804869105. [Saa03] Yousef Saad. Iterative Methods for Sparse Linear Systems . Society for I...

    work page arXiv 2008

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.