# Discrepancy Minimization via a Self-Balancing Walk

arXiv: https://arxiv.org/abs/2006.14009 · HTML: https://mlsanity.com/paper/2006.14009/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2020.

## Built on by (most cited first, 22 of 22)

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Provable Post-Training Quantization: Theoretical Analysis of OPTQ and Qronos](https://mlsanity.com/paper/2508.04853/) (2025)
- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [Injectivity capacity of ReLU gates](https://mlsanity.com/paper/2410.20646/) (2024)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [Unified Stochastic Framework for Neural Network Quantization and Pruning](https://mlsanity.com/paper/2412.18184/) (2024)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)
- [SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantization](https://mlsanity.com/paper/2309.10975/) (2023)
- [GraB-sampler: Optimal Permutation-based SGD Data Sampler for PyTorch](https://mlsanity.com/paper/2309.16809/) (2023)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)
- [Express Language Modeling](https://mlsanity.com/paper/2606.10944/) (2026)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

We study discrepancy minimization for vectors in ℝn under various settings. The main result is the analysis of a new simple random process in multiple dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for several problems in online vector balancing posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as linear time algorithms for logarithmic bounds for the Koml'os conjecture.