Finite precision impacts accuracy of randomized vector balancing methods
Finite-Precision Gram-Schmidt Walks
Data Structures and Algorithms
Summary
Randomized methods that balance vectors well work perfectly in ideal math, but computers use limited precision that causes small errors. These errors can accumulate and change the method’s step-by-step decisions, affecting the final outcome. The authors studied how these errors build up and showed mathematically how much the method changes when using finite precision. They also tested their findings by changing the number of bits used and the size of the problem.
What this means in practice
- •For data compression engineers: Improve numerical reliability of compression algorithms using randomized vector balancing under finite precision settings.
- •For experimental design teams: Ensure controlled error bounds when implementing randomized experimental designs with finite-precision arithmetic.
Authors
Emile Anand, Jan van den Brand, Peter Chen
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 $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.