mlsanityData to 7 Oct 2026

Discrepancy Minimization via a Self-Balancing Walk

arXiv 2006.14009 ↗First posted 24 Jun 2020cs.DS cs.DM math.PRcited by 22

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 2; 2023: 6; 2024: 2; 2025: 5; 2026: 5.

22 papers.

Sort:

  1. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  2. 2021Kernel Thinningcited by 47
  3. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
  4. 2022GraB: Finding Provably Better Data Permutations than Random Reshufflingcited by 18
  5. 2023Binary perceptrons capacity via fully lifted random duality theorycited by 13
  6. 2025Provable Post-Training Quantization: Theoretical Analysis of OPTQ and Qronoscited by 13
  7. 2023Fl RDT based ultimate lowering of the negative spherical perceptron capacitycited by 11
  8. 2025Streaming Attention Approximation via Discrepancy Theorycited by 9
  9. 2023Coordinating Distributed Example Orders for Provably Accelerated Trainingcited by 7
  10. 2025Low-Rank Thinningcited by 7
  11. 2025Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDTcited by 5
  12. 2024Injectivity capacity of ReLU gatescited by 4
10 more
  1. 2026Nearly Optimal Attention Coresetscited by 4
  2. 2024Unified Stochastic Framework for Neural Network Quantization and Pruningcited by 3
  3. 2025Binary perceptron computational gap -- a parametric fl RDT viewcited by 3
  4. 2026Parametric RDT approach to computational gap of symmetric binary perceptroncited by 1
  5. 2022Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practicalcited by 0
  6. 2023SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantizationcited by 0
  7. 2023GraB-sampler: Optimal Permutation-based SGD Data Sampler for PyTorchcited by 0
  8. 2026Ultrametric OGP - parametric RDT symmetric binary perceptron connectioncited by 0
  9. 2026Express Language Modelingcited by 0
  10. 2026Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructionscited by 0