acceptodds
Under review as a conference paper at ICLR 2027

Finite-Precision Gram-Schmidt Walks

Abstract

The Gram–Schmidt Walk is a randomized vector-balancing algorithm whose subgaussian guarantees support applications in discrepancy, experimental design, and data compression; however, these theoretical guarantees are established in exact arithmetic, whereas implementations must approximate least-squares directions, boundary updates, and sampling probabilities in finite precision. This is important because small numerical errors can change which coordinates freeze and thereby alter the subsequent trajectory. We analyze the concentration of the perturbed Gram-Schmidt walk directly under bounded, potentially biased and history-dependent errors. For input vectors of Euclidean norm at most one, we obtain a modified MGF bound depending on key error sources which recovers the original result as the error goes to zero. We also construct a full-column-rank instance in which bounded update errors produce bias of order , showing that updates accumulate error unavoidably under this model. Finally, we validate our findings in a variety of settings by ablating on the bit precision and problem size.

Primary area:
learning theory
Keywords:
Gram–Schmidt walk, numerical stability, discrepancy minimization, vector balancing, finite-precision arithmetic

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 2 reviews, above 68% of the others.
Reviewer_DmfHOpenReview ↗
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.

Reviewer_vayrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the Gram–Schmidt Walk under bounded errors in least-squares directions, coordinate updates, and branch probabilities. Unlike a trajectory-coupling analysis, it analyzes the realized perturbed execution, allowing biased, history-dependent errors and changes in the freezing order. The paper also constructs a full-column-rank instance exhibiting bias of order min⁡{n2εiter,n}\min{n^2\varepsilon_{\mathrm{iter}},n}min{n2εiter​,n}. Experiments study reduced-mantissa arithmetic, problem-size scaling, and the reliability of different least-squares implementations.

Critical strengths
  1. Numerical errors can change which coordinate freezes and therefore change all subsequent least-squares problems. This makes ordinary pathwise comparison with one exact execution potentially inappropriate. Analyzing concentration directly along the perturbed trajectory is a sensible response to this difficulty.
  2. Appendix D.1 goes beyond mantissa-only emulation and compares dtype-based QR, Cholesky/Woodbury, and explicit-inverse implementations. The observation that refactoring can greatly reduce breakdowns without eliminating discrepancy inflation is practically interesting. The authors also explicitly disclose implementation limitations, unequal sample sizes, and conditioning of distributional statistics on successful runs.
Critical weaknesses

Appendix D, lines 1272–1277, explicitly states that the implementation does not satisfy all assumptions of Section 3. It does not enforce the downward pivot caps, uses tolerance-based activity and snapping, permits early termination, and converts the terminal state to signs. It also solves using a rounded input matrix, replaces nonfinite coefficients with zero, and evaluates discrepancy using the original matrix.

These are not merely implementation details: they can affect the number of steps, error magnitudes, and output distribution. Inspection of gsw.py confirms these differences. A small check of the supplied routine on a two-row, twelve-column instance produced executions with fourteen iterations, illustrating that the theorem’s per-iteration freezing property is not automatic.

The observations remain useful as a study of a particular numerical implementation. However, they are not direct validation of Theorem 2.3 without additional accounting. Figure 8 also measures coefficient error along a float64 reference trajectory, whereas the theorem requires image-error control along the realized perturbed trajectory. The supplementary dtype study includes more relevant diagnostics, which is helpful, but does not close this gap for the principal figures.

Questions for authors
  1. What fraction of the principal experimental runs violate the step caps, per-step freezing requirement, or assumed error budgets? How much discrepancy inflation remains after enforcing these conditions?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.