- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The Gram-Schmidt Walk (GSW) of Bansal et al./Harshaw et al. outputs a signing whose discrepancy B(z − z0) is exactly 1-subgaussian, but the guarantee assumes exact arithmetic. This paper analyzes the walk under a finite-precision error model with three error sources: coordinatewise update error ‖ε_t‖∞ ≤ ε_iter (rounding, clamping, freezing corrections), least-squares image error ‖B(û_t − u_t)‖₂ ≤ ε_LS, and branch-probability error |p̂ − p_comp| ≤ ε_pr. The main result (Thm 2.3) is an MGF bound E[exp⟨B(z−z0), v⟩] ≤ exp(½‖v‖² + (n^{3/2}(2ε_pr + ε_iter) + 2n·ε_LS + n(n+1)ε_iter)‖v‖) that retains the sharp exact-arithmetic quadratic term while adding an explicit linear penalty. The key technical device absorbs the pivot-coordinate error into the scalar step so that per-phase sums telescope to the true pivot displacement, preserving Harshaw's phase structure under biased conditional probabilities. A lower bound (Thm 2.4) constructs a full-column-rank instance where admissible errors force bias and uncentered ψ₂-norm of order min{n²ε, n}, matching the upper bound's ε_iter-dependence up to constants and saturating at the trivial bound ‖Bz‖₂ ≤ n. Machine-precision corollaries (ε_pr ≤ 2u/(1−2u) + 2^{−b}; ε_LS ≤ 3ηκ_B/(1−ηκ_B) for backward-stable solvers) connect the model to float implementations. Experiments over four matrix ensembles ablate mantissa bits and n, observing an n·2^{−b} collapse on benign data and n²·2^{−b} on adversarial data, with a knee near n ≈ 10·2^b.
Critical strengths
S1 — A correct, tight, and reusable robustification of a delicate analysis. The upper bound preserves the sharp ½‖v‖² quadratic term while separating three error sources with explicit n-scalings, and the lower bound matches the ε_iter-dependence (n²) and saturates at n — this pairing converts a qualitative worry about finite precision into a quantitative bit budget, which is exactly what implementers of discrepancy-based thinning (e.g., the cubic-time GSW of Carrell et al.) need. I verified the construction is admissible and its analysis airtight, which makes the tightness claim credible rather than conjectural.
S2 — Unusually honest and reproducible empirics. Appendix D's limitations list (including that the implementation violates the theory's hypotheses and that the diagnostics are not certified bounds), the anonymous code repository, the failure taxonomy, and the E-THREAD-grade compute disclosure (6-core laptop/1–3 CPU-hours for main sweeps; 32 workers/211 CPU-hours for the solver grid) are model practice. My own small-scale replication reproduces the precision-knee picture (inflation grows with n at 4 fraction bits; flat at 12), increasing my confidence that the phenomena are real.
Critical weaknesses
W1 — Statement-level defects in the flagship results. Lemma 3.2 as printed (√(nγ)) does not match its proof or Theorem 2.3 (γ√n); Theorem 2.3's statement contains meta-language; δ/δ̂ notation is inconsistent across statement and proof. None of this changes the mathematics — the proof is right — but the theorem-and-lemma layer is what readers cite, and right now it requires proof archaeology to use correctly. A revision must fix these; they are one-day fixes.
W2 — The experiments illustrate rather than validate the theory, and this is only partly acknowledged. The headline figures measure a process (directions from rounded B̂, discrepancy against B₀, tolerance-based activity and snapping, repaired breakdowns) that the theorems do not cover; Appendix D discloses each deviation but the abstract/introduction still say the experiments "validate our findings." My independent checks validate the theory only in the drift-only and construction-specific regimes. Until the B̂-vs-B₀ term is bounded or the wording is softened, the empirical contribution overclaims relative to its provenance.
Questions for authors
Q1 (clarification, affects soundness of citation). Lemma 3.2 states the linear term as √(nγ)‖v‖, while the proof of Lemma 3.2 (equation (10)) and Theorem 2.3 use γ√n‖v‖ = n^{3/2}(2ε_pr + ε_iter)‖v‖; the two agree only when n(2ε_pr + ε_iter) = 1. I verified the γ√n form is what the proof delivers (and the numerics are consistent with it). Is the intended statement γ√n?
Q2 (clarification, affects experimental interpretation). Directions are computed from a rounded copy B̂ of the input but discrepancy is reported against the original B₀. Can you bound or empirically quantify ‖(B̂ − B₀)z‖ relative to the finite-precision effects being studied, or restate the experiments so that the measured object matches the analyzed one?
Q3 (clarification, affects scope). The model requires every iteration to produce an admissible update (feasible, freezing at least one coordinate), yet real runs experience downdate breakdowns repaired by refactoring, and failed coefficients replaced by zero. Do Theorems 2.3–2.4 cover runs containing such repairs? If only failure-free runs are covered, please state the effective coverage (e.g., the ≤1.75% failure rate) alongside the guarantee.
Q4 (question, affects tightness). The lower bound uses exact step-selection probabilities, so the n^{3/2}ε_pr drift term has no matching lower bound. Can probability perturbation alone force bias Ω(n^{3/2}ε_pr) (or a higher power of n), or is the true accumulation smaller?
Q5 (suggestion). Specializing Lemmas B.3–B.4 to the Cholesky/Woodbury maintenance of the cubic-time implementation you benchmark (GSWDESIGN/screening scheme) would yield a concrete bit-budget table (bits vs. n, κ) — the most actionable form of the theory for practitioners. Citing the Sankar–Spielman–Teng smoothed-analysis tradition would also place the worst-case κ_B dependence in its typical-case context.