Optimal Online Discrepancy Minimization in Linear Time

Ishaq Aden-Ali

Optimal Online Discrepancy Minimization in Linear Time

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An online algorithm assigns signs so every prefix sum is three standard Gaussians, giving optimal discrepancy in linear time.

desk verdict Linear-time optimal online Komlós via a clean three-Gaussian coupling; the math checks out and closes the exponential-time gap. read the letter →

arxiv 2607.04388 v1 pith:5VCTJSKE submitted 2026-07-05 cs.DS

Ishaq Aden-Ali This is my paper · ORCID

classification cs.DS MSC 68W2068Q2560G50

keywords onlinediscrepancyKomlósproblemGaussianfixed-pointwalkprefixsubgaussianconcentrationlinear-timealgorithmvectorbalancing

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper gives a fast online method for signing unit vectors so that no partial sum gets large in the infinity norm. When vectors arrive one by one and each must be signed immediately, the algorithm keeps three carefully coupled Gaussian walks whose updates always add to a genuine ±1 sign. Because the prefix sum equals the sum of three standard Gaussians, ordinary concentration yields the optimal O(√ log T) bound with high probability, matching the best previous (but exponentially slow) result. The same procedure also supplies a linear-time algorithmic version of Banaszczyk’s classical offline bound. A sympathetic reader cares because optimal online discrepancy is now practical rather than merely existential.

What carries the argument

The Gaussian triplet walk: three copies of a balanced Gaussian fixed-point walk are coupled by a three-way sampler so that the sum of their fractional updates is always a genuine ±1 while each coordinate remains marginally N(0,I).

What would settle it

Run the algorithm on a sequence of unit vectors for which the optimal online discrepancy is known to be Ω(√ log T) and check whether the observed max-norm of the prefix sums exceeds the stated O(√ log T) high-probability bound, or verify that after any step the three auxiliary states fail to be standard Gaussian.

Watch

Extended reading notes

Core claim

For any sequence of vectors with Euclidean norm at most 1, the Gaussian triplet walk produces random signs ε_t such that every prefix sum equals G_{t,1} + G_{t,2} + G_{t,3} where each G_{t,j} is marginally a standard Gaussian; the algorithm runs in O(dT) time and therefore achieves max_t ||∑_{i=1}^t ε_i v_i||_∞ = O(√ log T) with high probability.

Load-bearing premise

When every vector has Euclidean length at most 1, none of the three transition probabilities of the fixed-point walk ever exceeds one-third and their sum is always at least one-third, which is exactly what lets the three-way coupling force a real sign.

Editorial extensions

If this is right

The optimal O(√ log T) online Komlós bound is now achievable in linear time rather than exponential time.
Banaszczyk’s O(√ log min{d,T}) offline bound admits a simple O(dT)-time randomized algorithm.
Any norm whose unit ball has Gaussian measure concentration inherits the same online guarantee by the same sub-Gaussian argument.
The construction supplies an explicit coupling that keeps three invariant Gaussians while forcing signed updates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same balanced fixed-point walk may admit couplings with more than three copies, potentially improving the constant in front of √ log T.
Because the method is purely online and linear-time, it can be dropped into streaming or distributed discrepancy settings where exponential-time algorithms cannot run.
If the balance condition can be restored for vectors longer than 1 by rescaling or rejection, the algorithm would extend beyond the Komlós regime.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper gives the first O(dT) online algorithm that matches the optimal O(√log T) prefix discrepancy of Kulkarni–Reis–Rothvoss. The device is simple: run three carefully balanced Gaussian fixed-point walks, couple their fractional updates so their sum is always a genuine sign, and keep each walk marginally standard Gaussian. Prefix sums are therefore 3-subgaussian and the concentration is immediate.

What is new is the coupling itself (Lemma 6 + Algorithm 1). Earlier Gaussian walks either stayed fractional or needed large variance to force integer signs with high probability; here the unit-norm balance condition (Prop. 5) guarantees that the three transition probabilities never put too much mass on any single choice, so a short, explicit three-way coupling can force ε_t ∈ {±1} while preserving the exact marginals. The invariance proof (Prop. 4) is a one-line density-ratio calculation, the induction is deterministic once the coupling exists, and the whole argument is self-contained. Runtime is literally linear: three inner products and a constant-time sample per step.

Soft spots are minor. The concrete constant 18 in the final bound is a bit loose (Hölder + a crude projection/union bound), and the greedy construction of the coupling point x is only sketched, but both are easy to tighten or implement. No free parameters, no circular definitions, and the AI-use disclosure is transparent. The offline corollary recovers Banaszczyk in linear time, which is already useful even if Bansal–Jiang later improved the offline exponent.

This is for people who care about algorithmic discrepancy, online balancing, or constructive versions of Banaszczyk-type results. The proofs are short enough that a careful referee can verify them in an afternoon. I would send it to peer review without hesitation; it is a clean, correct closing of a known gap.

Referee Report

0 major / 4 minor

Summary. The paper gives a linear-time online algorithm (the Gaussian triplet walk) for the online Komlós problem. For any fixed sequence of vectors with Euclidean norm at most 1, the algorithm assigns each arriving vector a random sign so that every prefix sum equals the sum of three coupled standard Gaussians. Consequently the prefix discrepancy is O(√log T) with high probability, matching the optimal bound of Kulkarni–Reis–Rothvoss while improving their exponential runtime to O(dT). The same construction yields a linear-time algorithmic version of Banaszczyk’s bound for the offline Komlós problem. The argument rests on a carefully balanced Gaussian fixed-point walk (Propositions 4–5), a three-way coupling that forces the sum of three fractional signs to be ±1 while preserving the prescribed marginals (Lemma 6 / Algorithm 1), and a short induction that keeps each auxiliary walk marginally standard Gaussian.

Significance. The result closes a clear complexity gap: the optimal online prefix-discrepancy bound was previously known only via an exponential-time construction, while the best linear-time algorithms achieved only O(log T). The new algorithm is elementary, fully self-contained, and runs in optimal linear time. The same technique immediately supplies a linear-time algorithmic realization of Banaszczyk’s theorem, improving on a long line of polynomial-time algorithms. The explicit three-way coupling and the balance condition under the unit-norm assumption are clean contributions that may be reusable for other online discrepancy or online vector-balancing problems. The manuscript also records that the algorithm and main proof were discovered with the aid of a large language model; the mathematical content itself is independent of that provenance and stands on its own.

minor comments (4)

In the proof of Theorem 2 the inequality exp(−x/a) ≤ a exp(−x) is invoked for a = ∥P_t e_k∥₂² ≤ 1 and x ≥ 1. While correct, a one-line justification (or a reference to the elementary inequality t e^{1−t} ≤ 1 for t ∈ (0,1]) would make the step fully transparent.
Algorithm 1 asserts that a feasible point x can be found greedily, but the concrete implementation of the greedy step is only sketched. Adding a short pseudocode fragment or an explicit loop would remove any residual ambiguity for implementers.
The constant 18 appearing in the final discrepancy bound can be tightened slightly by a more careful application of Hölder (or by using the exact sub-Gaussian parameter of the sum of three independent Gaussians). The improvement is cosmetic but worth a remark.
A few typographical inconsistencies remain (e.g., “Koml´ os” vs. “Komlós”, occasional missing spaces around math operators). A final pass would polish the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Gaussian invariance, probability balance, and three-way coupling are proved from first principles inside the paper.

full rationale

The derivation chain is self-contained. Proposition 4 establishes that the Gaussian fixed-point walk preserves N(0,I_d) via an elementary density-ratio calculation that rewrites the transition probabilities in terms of the Gaussian density γ and substitutes to recover f(x)=γ(x). Proposition 5 then verifies the balance conditions 0≤p^{+},p^{-}≤1/3 and p^{+}+p^{-}≥1/3 whenever ∥v∥_{2}≤1 by a short case analysis on the inner product ⟨x,v⟩; these bounds are not assumed but derived. Lemma 6 constructs an explicit coupling on {−1,0,1}^{3} whose coordinates sum to ±1 while matching the prescribed marginals, again by elementary probability arithmetic (no external uniqueness theorem). The induction in the proof of Theorem 1 simply chains these three facts: the balance conditions feed the coupling, the coupling feeds the invariance proposition, and the sum of the three walks therefore remains the signed prefix sum. Prior citations (ALS21, LSS22, KRR24) appear only for motivation, comparison of runtimes, and optimality lower bounds; none is load-bearing for the existence of the walk or the O(√ log T) guarantee. No parameter is fitted to data and later re-presented as a prediction, and no quantity is defined in terms of the target discrepancy bound. Consequently the central claims of Theorems 1–2 do not reduce to their inputs by construction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

Pure constructive algorithmics. No numerical parameters are fitted to data. The only background facts are standard Gaussian density ratios and elementary concentration; the unit-norm hypothesis is the natural domain assumption of the Komlós setting; the three-walk coupling is proved rather than postulated.

assumptions (3)

standard math A standard Gaussian remains standard after a random fractional update δ∈{-1,0,1} with the stated Metropolis-style probabilities (Proposition 4).
Classic density-ratio calculation for Gaussians; proved in full inside the paper.
domain assumption If ||v||_2 ≤ 1 then the three transition probabilities satisfy 0 ≤ p^+,p^- ≤ 1/3 and p^++p^- ≥ 1/3 for every state (Proposition 5).
Direct elementary verification under the Komlós unit-norm hypothesis; load-bearing for the coupling.
ad hoc to paper Any triple of probability pairs obeying the balance conditions of Proposition 5 admits a coupling on {-1,0,1}^3 whose coordinates sum to ±1 and have the prescribed marginals (Lemma 6).
Constructive combinatorial lemma proved by exhibiting an explicit sampling procedure; the algorithmic heart of the paper.

invented entities (2)

Gaussian triplet walk independent evidence
purpose: Maintain three coupled standard Gaussians whose sum is always a genuine signed prefix sum.
Algorithmic construction, not a physical postulate; fully specified by Algorithm 2.
Three-way coupling (Algorithm 1) independent evidence
purpose: Sample three fractional updates with given marginals that are forced to sum to ±1.
Explicit randomized procedure whose correctness is proved in Lemma 6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal Online Discrepancy Minimization in Linear Time." pith.science (2026). https://pith.science/paper/5VCTJSKE

@misc{pith2026260704388,
  author       = {Pith},
  title        = {Pith review of: Optimal Online Discrepancy Minimization in Linear Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5VCTJSKE}},
  note         = {Machine review of arXiv:2607.04388}
}

abstract

We provide an online algorithm with the following guarantee: for any fixed sequence of vectors $v_1,\dots,v_T \in \mathbf{R}^d$ with $\|v_i\|_2\le 1$, the algorithm assigns each arriving vector $v_t$ a random sign $\varepsilon_t$ such that every prefix sum $\sum_{i=1}^t \varepsilon_i v_i $ can be written as the sum of three coupled standard Gaussian vectors. Our algorithm runs in $O(dT)$ time and achieves the optimal prefix discrepancy bound \[ \max_{1 \le t \le T}\left\| \sum_{i=1}^t \varepsilon_i v_i \right\|_\infty = O\left( \sqrt{\log T} \right), \] with high probability. This recovers the optimal bound of Kulkarni, Reis, and Rothvoss, whose algorithm runs in time exponential in $T$ and $d$. The algorithm and main proof were discovered in a GPT-5.5 Pro Extended conversation prompted by the author.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Online Beck--Fiala Down to Logarithmic Sparsity
math.CO 2026-07 conditional novelty 7.0 of 10

A new online random-walk algorithm achieves O(√d) prefix discrepancy for d-sparse vectors whenever d ≥ log(T)(log log T)^{2+η}, proving Beck–Fiala in that regime and resolving the online Spencer conjecture.
Online balancing of vectors with small coordinates
math.CO 2026-08 accept novelty 6.0 of 10

This paper achieves constant prefix discrepancy for online signed balancing of small-coordinate vectors with failure probability about T exp(-c d / ln^2(ed)), and proves the ln^2 scale is a barrier for the compact-pot...

Reference graph

Works this paper leans on

32 extracted references · cited by 2 Pith papers

[1]

Optimal Online Discrepancy Minimization , booktitle =

Janardhan Kulkarni and Victor Reis and Thomas Rothvoss , editor =. Optimal Online Discrepancy Minimization , booktitle =
[2]

Decoupling via Affine Spectral-Independence:

Nikhil Bansal and Haotian Jiang , editor =. Decoupling via Affine Spectral-Independence:. Proceedings of the 58th Annual
[3]

Joel Spencer , title =. J. Comb. Theory
[4]

Liu and Mehtaab Sawhney , editor =

Ryan Alweiss and Yang P. Liu and Mehtaab Sawhney , editor =. Discrepancy minimization via a self-balancing walk , booktitle =
[5]

Liu and Ashwin Sah and Mehtaab Sawhney , editor =

Yang P. Liu and Ashwin Sah and Mehtaab Sawhney , editor =. A. 13th Innovations in Theoretical Computer Science Conference,
[6]

Random Struct

Wojciech Banaszczyk , title =. Random Struct. Algorithms , volume =
[7]

Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method , booktitle =

Avi Levy and Harishchandra Ramadas and Thomas Rothvoss , editor =. Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method , booktitle =
[8]

Theory Comput

Daniel Dadush and Shashwat Garg and Shachar Lovett and Aleksandar Nikolov , title =. Theory Comput. , volume =

Show all 32 references

[9]

Nikhil Bansal and Daniel Dadush and Shashwat Garg , title =
[10]

Theory Comput

Nikhil Bansal and Daniel Dadush and Shashwat Garg and Shachar Lovett , title =. Theory Comput. , volume =
[11]

Vempala , editor =

Nikhil Bansal and Aditi Laddha and Santosh S. Vempala , editor =. A Unified Approach to Discrepancy Minimization , booktitle =
[12]

Discrepancy Minimization via Regularization , booktitle =

Lucas Pesenti and Adrian Vladu , editor =. Discrepancy Minimization via Regularization , booktitle =
[13]

Spencer , title =

Nikhil Bansal and Joel H. Spencer , title =. Random Struct. Algorithms , volume =
[14]

Altschuler and Konstantin E

Dylan J. Altschuler and Konstantin E. Tikhomirov , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2509.02432 , eprinttype =

2025 doi
[15]

Online vector balancing and geometric discrepancy , booktitle =

Nikhil Bansal and Haotian Jiang and Sahil Singla and Makrand Sinha , editor =. Online vector balancing and geometric discrepancy , booktitle =
[16]

Online Discrepancy Minimization for Stochastic Arrivals , booktitle =

Nikhil Bansal and Haotian Jiang and Raghu Meka and Sahil Singla and Makrand Sinha , editor =. Online Discrepancy Minimization for Stochastic Arrivals , booktitle =
[17]

Liu, and Mehtaab Sawhney

Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney. Discrepancy minimization via a self-balancing walk. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 14...

2021
[18]

Altschuler and Konstantin E

Dylan J. Altschuler and Konstantin E. Tikhomirov. A threshold for online balancing of sparse i.i.d. vectors. CoRR , abs/2509.02432, 2025

2025
[19]

Balancing vectors and Gaussian measures of n-dimensional convex bodies

Wojciech Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Struct. Algorithms , 12(4):351--360, 1998

1998
[20]

An algorithm for Koml \' o s conjecture matching Banaszczyk 's bound

Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An algorithm for Koml \' o s conjecture matching Banaszczyk 's bound. SIAM J. Comput. , 48(2):534--553, 2019

2019
[21]

The Gram-Schmidt walk: A cure for the Banaszczyk blues

Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The Gram-Schmidt walk: A cure for the Banaszczyk blues. Theory Comput. , 15:1--27, 2019

2019
[22]

Decoupling via affine spectral-independence: Beck-Fiala and Koml \' o s bounds beyond Banaszczyk

Nikhil Bansal and Haotian Jiang. Decoupling via affine spectral-independence: Beck-Fiala and Koml \' o s bounds beyond Banaszczyk . In Aditya Bhaskara and Artur Czumaj, editors, Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT,...

2026
[23]

Online discrepancy minimization for stochastic arrivals

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. Online discrepancy minimization for stochastic arrivals. In D \' a niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2...

2021
[24]

Online vector balancing and geometric discrepancy

Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha. Online vector balancing and geometric discrepancy. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theor...

2020
[25]

Nikhil Bansal, Aditi Laddha, and Santosh S. Vempala. A unified approach to discrepancy minimization. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, University of Ill...

2022
[26]

Nikhil Bansal and Joel H. Spencer. On-line balancing of random inputs. Random Struct. Algorithms , 57(4):879--891, 2020

2020
[27]

Towards a constructive version of Banaszczyk 's vector balancing theorem

Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a constructive version of Banaszczyk 's vector balancing theorem. Theory Comput. , 15:1--58, 2019

2019
[28]

Optimal online discrepancy minimization

Janardhan Kulkarni, Victor Reis, and Thomas Rothvoss. Optimal online discrepancy minimization. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 , p...

2024
[29]

Deterministic discrepancy minimization via the multiplicative weight update method

Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Deterministic discrepancy minimization via the multiplicative weight update method. In Friedrich Eisenbrand and Jochen K \" o nemann, editors, Integer Programming and Combinatorial Optimization - 19th International Conferen...

2017
[30]

Liu, Ashwin Sah, and Mehtaab Sawhney

Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney. A Gaussian fixed point random walk. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Berkeley, CA, USA, January 31 - February 3, 2022 , volume 215 of LIPIcs , pages 101:1--101:10. S...

2022
[31]

Discrepancy minimization via regularization

Lucas Pesenti and Adrian Vladu. Discrepancy minimization via regularization. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 1734--1758. SIAM , 2023

2023
[32]

Balancing games

Joel Spencer. Balancing games. J. Comb. Theory B , 23(1):68--74, 1977

1977

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.

[1] [1]

Optimal Online Discrepancy Minimization , booktitle =

Janardhan Kulkarni and Victor Reis and Thomas Rothvoss , editor =. Optimal Online Discrepancy Minimization , booktitle =

[2] [2]

Decoupling via Affine Spectral-Independence:

Nikhil Bansal and Haotian Jiang , editor =. Decoupling via Affine Spectral-Independence:. Proceedings of the 58th Annual

[3] [3]

Joel Spencer , title =. J. Comb. Theory

[4] [4]

Liu and Mehtaab Sawhney , editor =

Ryan Alweiss and Yang P. Liu and Mehtaab Sawhney , editor =. Discrepancy minimization via a self-balancing walk , booktitle =

[5] [5]

Liu and Ashwin Sah and Mehtaab Sawhney , editor =

Yang P. Liu and Ashwin Sah and Mehtaab Sawhney , editor =. A. 13th Innovations in Theoretical Computer Science Conference,

[6] [6]

Random Struct

Wojciech Banaszczyk , title =. Random Struct. Algorithms , volume =

[7] [7]

Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method , booktitle =

Avi Levy and Harishchandra Ramadas and Thomas Rothvoss , editor =. Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method , booktitle =

[8] [8]

Theory Comput

Daniel Dadush and Shashwat Garg and Shachar Lovett and Aleksandar Nikolov , title =. Theory Comput. , volume =