PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite-Precision Gram-Schmidt Walks

Emile Anand, Jan van den Brand, Peter Chen

arXiv:2610.08562v1cs.DS

TL;DR

The Gram-Schmidt Walk’s concentration guarantees assume exact arithmetic, while finite-precision errors can change which coordinates freeze. This paper analyzes the walk under bounded perturbations, establishing a modified concentration bound and showing that update errors can produce bias of order min{n^2 ε_iter, n}.

  • Problem

    Existing concentration guarantees for the Gram-Schmidt Walk assume exact arithmetic and do not quantify finite-precision error tolerance, despite numerical errors potentially changing which coordinates freeze.

    Source: §1 · p. 2

  • Method

    The paper analyzes bounded, biased, history-dependent errors using a phase-based concentration analysis that separates least-squares, coordinate-update, and sampling errors.

    Source: §1 · p. 2, §2.1 · p. 5

  • Results

    min{n^2 ε_iter, n} bias is unavoidable under bounded update errors, and experiments corroborate that discrepancy varies with precision and problem size.

    Source: §1 · p. 3, §5 · p. 10

  • Takeaways & Limitations

    Empirical discrepancy tails indicate when approximate arithmetic preserves output quality and when it is a limitation.

    Source: §1 · p. 3

    Applications to experimental design or data compression require separate consideration of privacy, representativeness, and the consequences of resulting decisions.

    Source: ETHICS STATEMENT · p. 10

Abstract

from arXiv · show

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 $n$ 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 $\min\{n^2\varepsilon,n\}$, 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.

1 INTRODUCTION

The paper studies whether the Gram-Schmidt Walk’s discrepancy guarantees survive finite-precision arithmetic, which can alter updates and freezing decisions. It analyzes biased, history-dependent errors and reports experiments on precision and matrix conditioning.

1 INTRODUCTION

  • Discrepancy assigns signs to vectors to make their signed sum small, and the Gram-Schmidt Walk produces colorings with subgaussian discrepancy.Balanced partitions can support representative data subsets and applications including coresets and experimental design.Source: §1 · p. 1
  • Finite-precision errors in directions, updates, and sampling can change which coordinates freeze, alter later least-squares problems, and undermine guarantees proved for exact arithmetic.The paper models bounded update, least-squares image, and conditional branch-probability errors, allowing biased, history-dependent perturbations and changes to the freezing trajectory.Source: §1 · p. 2
  • A phase-based analysis controls accumulated conditional drift under biased, history-dependent perturbations without requiring proximity to an ideal execution.The resulting concentration bounds retain the exact-arithmetic quadratic term in the log moment-generating function and depend on arithmetic precision, bit complexity, and least-squares solver error.Source: §1 · p. 2
  • Experiments show that finite precision can degrade discrepancy, and examine how that degradation depends on precision and matrix conditioning.Empirical discrepancy tails are used to assess when approximate arithmetic preserves output quality and when it becomes a limitation.Source: §1 · p. 3

1.1 RELATED WORKS

  • Unlike prior stability work focused on numerical subroutines or small output changes under input perturbations, this analysis permits changed trajectories and colorings while controlling discrepancy.Its concentration guarantees for the Gram-Schmidt primitive can be propagated into bounds for repeated compression or learning pipelines.Source: §1.1 · p. 3

2 PRELIMINARIES AND NOTATION

The section reviews the exact-arithmetic Gram-Schmidt Walk and develops a finite-precision error model, a modified concentration guarantee, and a lower bound on accumulated update error.

2 PRELIMINARIES AND NOTATION

  • In the exact-arithmetic walk, adaptive endpoint updates have conditional mean zero, freeze coordinates at ±1, and yield 1-subgaussian outputs.The walk selects a pivot, computes a least-squares direction with pivot entry one, and recomputes the direction over remaining coordinates as pivots shrink.Source: §2 · pp. 4–5

2.1 TECHNICAL CONTRIBUTIONS

  • The error model separately tracks least-squares error εLS, step-and-clamping arithmetic error εiter, and sampling-distribution perturbation εpr.Appendix B gives sufficient working-precision conditions for a specified implementation under assumptions on solver stability, conditioning, and exponent range.Source: §2.1 · p. 5
  • The perturbed walk retains the original quadratic MGF term with an explicit linear penalty that vanishes with error, including an n^3/2(2εpr + εiter) drift contribution.The drift analysis tracks the realized trajectory; the resulting MGF bound also implies subgaussianity in the Orlicz-norm formulation and Gaussian-like directional tails.Source: §2.1 · pp. 5–6
  • Bounded coordinate-update errors can cause worst-case bias of order min{n^2ε, n}, even with exact least-squares directions and branch probabilities.The lower-bound construction uses a full-column-rank matrix, preserves frozen coordinates, and terminates within n iterations.Source: §2.1 · p. 6
  • Figure 4 illustrates the predicted quadratic accumulation of bounded update errors as arithmetic precision and problem size vary.The supplied passage reports this numerical study but gives no quantitative results.Source: §2.1 · p. 6

3 FINITE-PRECISION GRAM-SCHMIDT WALK

Finite-precision errors break key exact-arithmetic steps in prior Gram-Schmidt Walk analyses. The section adapts the analysis with a drift-dependent MGF bound and a pivot-phase penalty.

3 FINITE-PRECISION GRAM-SCHMIDT WALK

  • Bansal et al. (2017)’s martingale properties and Harshaw et al. (2024)’s exact-solution decomposition no longer hold under numerical errors, which also disrupt the conditional-expectation bound.The exact decomposition applies to ut, not the computed direction, and the inexact step can have nonzero expected increment.Source: §3 · pp. 6–7
  • The error model separates approximate least-squares directions, sampling-probability error, and arithmetic, clamping, and freezing errors in the update, which preserves feasibility and freezes at least one additional coordinate.The discrepancy increment separates the computed-direction contribution, its difference from the exact direction, and the final update error.Source: §3 · pp. 6–7
  • For analysis, the walk’s reverse coordinate-decision order defines a conceptual Gram-Schmidt orthogonalization of B, whose vectors are used only in the proof.The analysis allows rank-deficient B, so this orthogonalization may produce zero vectors.Source: §3 · p. 7
  • γ = n(2εpr + εiter) bounds drift in Lemma 3.2’s MGF guarantee for non-noise updates; a pivot-phase penalty restores the needed inequality despite noise along the pivot unit.The penalty is Et = γ Σ_{r∈Qs,p} |αrβr|; assembling the bounds yields Theorem 2.3.Source: §3 · p. 8

4 NUMERICAL EXPERIMENTS

The experiments show that finite-precision discrepancy inflation generally worsens with problem size, especially at low precision, while retaining more bits brings empirical statistics closer to the float64 reference. Additional sweeps examine directional concentration, scaling, arithmetic, and least-squares implementation behavior.

Arithmetic model

  • The main sweeps emulate reduced precision by rounding each elementary operation to b retained fraction bits, while reductions round products and accumulate in float64.The fp8-E5M2, bf16, and fp16 labels use b = 2, 7, and 10, respectively.Source: §4 · p. 8

Directional concentration

  • On the Higgs matrix, the lowest-precision formats show substantial growth in centered-moment and empirical ψ2 diagnostics with n, while higher-precision curves depend more weakly on n.The rising median diagnostic at the lowest precisions indicates deterioration across a substantial portion of tested directions.Source: Figure 3 · p. 9, §4 · p. 9

Scaling collapse

  • On the Higgs matrix, ˆS collapses onto a curve in n · 2^-b; on the lower-bound matrix, it follows n^2 · 2^-b before departing as the bound saturates or reaches the float64 plateau.Open markers violate a < 1/(8n).Source: Figure 4 · p. 9, §4 · p. 9

Findings

  • Discrepancy inflation generally grows with n at fixed precision, with the strongest deterioration at the lowest precisions; retaining more bits brings empirical statistics closer to float64.The findings suggest larger instances need higher precision to maintain comparable performance.Source: §4 · pp. 9–10

Implementation details

  • Among tested least-squares implementations, QR is most robust, while the explicit-inverse scheme is more sensitive to ill-conditioning.Refactoring every ten steps reduces fp16 Cholesky downdate failures to at most 1.75%, but ψ2 inflation persists among successful runs; QR median image error is less conditioning-sensitive than coefficient error.Source: §4 · p. 10

5 CONCLUSION

The paper analyzes the Gram-Schmidt Walk under bounded, potentially biased and history-dependent perturbations, deriving a concentration bound and a construction showing update-error bias can accumulate quadratically before saturation. Experiments corroborate how numerical discrepancy varies with fixed precision and problem size.

5 CONCLUSION

  • The concentration bound separates least-squares image, coordinatewise update, and conditional sampling errors while retaining the exact-arithmetic quadratic term in the log-MGF.It applies to bounded, potentially biased and history-dependent perturbations.Source: §5 · p. 10
  • A full-column-rank construction produces bias of order min{n^2 ε_iter, n}, showing quadratic accumulation of update error is unavoidable before saturation.Source: §5 · p. 10
  • Experiments corroborate the theoretical findings on how numerical discrepancy varies with fixed precision and problem size.Source: §5 · p. 10

AI DISCLOSURE · Outline of the Appendix · A AUXILIARY LEMMAS

The supplied material records AI assistance and its review, sketches the appendix contents, and states auxiliary lemmas used in the concentration analysis.

AI DISCLOSURE

  • The authors disclose using Cognition’s Devin agent to run experiments and Anthropic’s Claude Fable 5.1 to suggest improvements to an earlier theoretical result.They state that AI-assisted work was reviewed, generated code was verified and tested, and they take responsibility for the final content.Source: AI DISCLOSURE · p. 10

ETHICS STATEMENT

  • The ethics statement frames the work as studying worst-case numerical reliability of the Gram-Schmidt Walk and says applications require separate consideration of privacy, representativeness, and decision consequences.It notes that finite-precision analysis clarifies circumstances in which numerical errors can compromise output quality.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

  • The reproducibility statement documents experimental procedures, precision settings, random seeds, evaluation metrics, compute setup, and code with thorough documentation.It says the main body specifies theoretical assumptions and perturbation models, while appendices provide proofs.Source: REPRODUCIBILITY STATEMENT · p. 10

Outline of the Appendix

  • The appendix outline assigns single-pivot phase analysis and the proof of Theorem 2.3 to Appendix B, the lower-bound construction to C, and experimental details to D.Appendix B.2 combines phase concentration estimates with bounds on accumulated numerical errors; Appendix C establishes worst-case bias from bounded update errors, and D gives setup and additional results.Source: Outline of the Appendix · p. 13

A AUXILIARY LEMMAS

  • Lemma A.1, attributed to Harshaw et al. (2024), states that f_x is Loewner-order decreasing on 2 × 2 positive semidefinite matrices for x ∈ [−1, 1].If M ⪯ N, then f_x(M) ≥ f_x(N).Source: A AUXILIARY LEMMAS · p. 13
  • Lemma A.2 converts an MGF bound for X into an Orlicz-norm bound, with its proof deriving projection tails and setting K=6σ.The proof uses the definition via one-dimensional projections, Markov’s inequality, and a tail bound for the positive part of |Y|−a.Source: A AUXILIARY LEMMAS · pp. 13–14

B MISSING PROOFS · B.1 SINGLE PIVOT PHASE ANALYSIS (PROOF OF LEMMA 3.2)

The proof of Lemma 3.2 decomposes the analysis by pivot phase and reduces each phase’s contribution to a bound in Lemma B.1. It conditions on the pivot’s history and handles the random phase endpoint by extending the sums to a fixed endpoint.

B.1 SINGLE PIVOT PHASE ANALYSIS (PROOF OF LEMMA 3.2)

  • Conditioning on the history Δp fixes the pivot, its start iteration, and the positions decided at its start; zeroing phase errors outside the phase permits a fixed endpoint n.The proof represents phase sums using the positions Qs,p decided in each iteration.Source: §B.1 · p. 14
  • Lemma B.1 bounds the contribution of pivot phase p to equation 9, which yields the phase-wise step in proving Lemma 3.2.The proof then conditions on each pivot’s history to apply this bound.Source: §B.1 · p. 14
  • The proof’s result holds for any fixed pivot ordering, and the full result follows by marginalizing over all orderings.Source: §B.1 · p. 15
  • The pivot phase’s decided vectors form an orthonormal basis for the subspace projected onto by Pp, connecting the phase contribution to the projection of v.The proof uses the mutually orthogonal subspaces of the projections Pp in the subsequent bound.Source: §B.1 · p. 15
  • The proof establishes g(n) ≤ g(n−1) and then g(R) ≤ g(R−1) down to g(tp−1) ≤ 1, bounding the pivot-phase expression.For intermediate R, it conditions on the first R iterations and uses iterated expectations to recover g(R−1).Source: §B.1 · pp. 16, 18, 19
  • The remaining pivot increments telescope to one of 1−x or −1−x, and bounded, potentially biased noise is represented by a surrogate x̃ with |x̃−x| ≤ γ.Here γ = (2εpr + εiter)n, and the bound on |x̃−x| follows from Lemma B.2.Source: §B.1 · pp. 16–17

B.2 PROOF OF THEOREM 2.3

The proof bounds the output difference by combining a modified Harshaw et al. (2024) MGF argument for the first term with bounds on the remaining finite-precision errors. It then controls the split error terms and chooses γ to obtain the theorem’s bound.

B.2 PROOF OF THEOREM 2.3

  • The proof rewrites Bz − Bz0 using equation 8 and applies a modified Harshaw et al. (2024) argument to bound the first term’s MGF.ε_iter is used as an upper bound on the infinity norm of ε_t.Source: §B.2 · p. 19
  • The remaining perturbation is bounded by update, ε_t, and pivot-coordinate error terms, using ∥Bu_t∥≤1 and ∥Bε_t∥≤nε_iter.The proof also uses |δ̂_t|≤2.Source: §B.2 · p. 19
  • The split error terms have MGF bound exp((2nε_LS + n(n + 1)ε_iter)∥v∥); the proof then sets γ=(2ε_pr + ε_iter)n before applying Lemma 3.2.The passage does not provide the resulting bound’s formula.Source: §B.2 · p. 19

B.3 CHOOSING CONSTANTS

This section turns the walk’s error parameters into bounds tied to machine precision and solver conditioning, then gives sufficient conditions for a target additive MGF penalty. It also notes that the least-squares bound relies on full column rank and a backward-stable solver.

Choosing γ

  • The perturbation in a pivot-phase branch probability is bounded by |x̃ − x| ≤ n(2εpr + εiter), where x̃ shifts the ideal value x by conditional-mean error.The bound permits history-dependent update errors, including errors dependent on the sampled branch.Source: §B.3 · p. 20

Bounding sampling error

  • On a floating-point machine with b random bits, the branch-probability error satisfies εpr ≤ 2u/(1 − 2u) + 2^-b, where u denotes unit roundoff.The arithmetic assumes binary floating-point with L significand bits, rounding to nearest, and no overflow or underflow; u = 2^-L.Source: §B.3 · pp. 20–21

Least-squares image error

  • For deterministic η ≥ 0 with ∥Et∥2 ≤ η∥Mt∥2 and ∥ft∥2 ≤ η∥b∥2, if ηκB < 1, then ∥B(ût − ut)∥2 ≤ εLS for every t, where εLS ≤ 3ηκB/(1 − ηκB).Source: §B.3 · p. 21

Corollary B.7

  • For target penalty τ, Corollary B.7 gives sufficient precision conditions ensuring the linear MGF penalty A is at most τ and yields a discrepancy guarantee.The result assumes exactly representable z0, a uniform active-system conditioning bound, a solver error bound, and the specified arithmetic and sampling implementation.Source: §B.3 · p. 23

C LOWER BOUND

The section constructs a full-column-rank instance where bounded update errors produce terminal discrepancy bias of order min{n^2ε, n}.

C LOWER BOUND

  • For every n ≥ 8 and ε ≥ 0, a full-column-rank instance with unit-norm columns admits bounded update errors yielding bias of order min{n^2ε, n}.The construction uses exact step-selection probabilities and starts from z0 = 0.Source: C LOWER BOUND · pp. 24–25
  • The admissible errors are deterministic functions of the iteration, active set, and pivot, preserve frozen coordinates, and the walk remains feasible and terminates within n iterations.During the initial perturbed steps, each pivot alone freezes; afterward the process continues as an exact Gram-Schmidt Walk.Source: C LOWER BOUND · p. 24

D EXPERIMENTAL DETAILS

The experiments use finite-sample diagnostics to examine how precision, problem size, and error mechanisms affect Gram-Schmidt walks. They report directional trends, tail behavior, and coefficient errors while noting limits on what the diagnostics can establish.

D EXPERIMENTAL DETAILS

  • For distributional experiments, 1,000 independent walks per configuration are split equally into selection and evaluation sets, so the selected direction is evaluated on independent walks.The experiments use a finite tested direction set; Figure 6’s standardized tails instead select and rescale a direction using the same samples, and show broadly similar behavior over part of the observed range with far-tail deviations.Source: D EXPERIMENTAL DETAILS · pp. 25–26, Figure 6 · p. 27
  • Discrepancy measured against the original input matrix includes input-representation error, while the scaling-collapse statistic combines centered fluctuations and bias rather than diagnosing one projection.The input is represented at working precision, and the experiments are finite-sample diagnostics over tested directions, not exact certificates of population subgaussian parameters or maxima over the full unit sphere.Source: D EXPERIMENTAL DETAILS · p. 26
  • At fixed n = 500, the worst-direction moment estimate plateaus near b ≈ 8; the quadrature fit is consistent with the n-sweep, and the ψ2 norm is about 1.4× higher.The three one-parameter fits describe the low-precision side nearly equally well.Source: Figure 5 · p. 26, D EXPERIMENTAL DETAILS · p. 26
  • In the adversarial stress test, a = 2^-b is injected on active non-pivot coordinates for the first ⌊n/4⌋ steps, while directions, probabilities, and updates are rounded at b bits.The test omits the cap a < 1/(8n) in violated cells and reports B0z even for runs that terminate with unfrozen coordinates, measuring adversarial bias combined with rounding error.Source: D EXPERIMENTAL DETAILS · p. 26
  • Rounding error grows like nε and collapses on the nε axis, whereas independent noise grows like √n ε and does not collapse (Figure 7).The comparison injects i.i.d. noise of magnitude 2^-b per step; the rounding arithmetic instead reuses errors coherently.Source: D EXPERIMENTAL DETAILS · p. 27, Figure 7 · p. 27
  • With m = 2, n = 200, and five retained fraction bits, coefficient differences spike by orders of magnitude near k ≈ m, where BA\p becomes nearly singular.The diagnostic uses 150 walks on float64 reference trajectories and reports medians and interquartile ranges because rare blowups dominate the mean; it measures coefficient differences, not image error.Source: D EXPERIMENTAL DETAILS · p. 26, Figure 8 · p. 27

D.1 DTYPE-BASED SOLVER COMPARISONS

The subsection compares dtype-based Gram-Schmidt walk solvers across precision levels and matrix families, finding that refactoring reduces failures while finite precision still affects successful outputs. It also reports a precision knee for clustered matrices and an exact-step identity control.

D.1 DTYPE-BASED SOLVER COMPARISONS

  • The experiments use float64, float32, and float16 arithmetic with pairwise reductions, testing Gaussian, controlled-condition, near-collinear, and Harshaw matrices at n ∈ {50, 200, 500}.Walks count as failures for nonfinite directions or branch probabilities, Cholesky or rank-one downdate breakdowns, or exhausting the step budget before a complete signing.Source: §D.1 · pp. 27–28
  • For clustered matrices, the precision knee occurs near b ≈ 5, matching the nε scaling observed on Higgs; identity matrices have exact least-squares steps at every precision.The identity control’s direction scale remains flat across n and bit precision because the error vector is orthogonal to the active block.Source: §D.1 · p. 28, Figure 9 · p. 28
  • Refactoring substantially reduces float16 Harshaw walk failures but does not eliminate discrepancy inflation among successful walks.At n = 500, 35 failures comprised 26 Cholesky and 9 downdate breakdowns; across 36 refactored configurations, the largest failure rate was 1.75%, with all others at most 0.05%.Source: §D.1 · p. 28, Table 1 · p. 28
  • Failure rates include all attempted walks, whereas Orlicz and bias diagnostics condition on successful walks, and discrepancy is evaluated using the original float64 matrix.Table 1 reports selected stored EPYCgrid configurations; complete configuration tables are available in the repository.Source: §D.1 · p. 28, Table 1 · p. 28
Loading 2610.08562v1…