arxiv: 2605.14149 · v1 · pith:XYXST5G7new · submitted 2026-05-13 · 🧮 math.PR · math.OC

The Mean-Field Limit of Online Stochastic Vector Balancing

Christian Fiedler , Joe Jackson , Daniel Lacker , Jonathan Niles-Weed This is my paper

Pith reviewed 2026-05-15 01:56 UTC · model grok-4.3

classification 🧮 math.PR math.OC

keywords vector balancingmean-field limitstochastic controlBrownian motiononline algorithmsdiscrepancyFöllmer drift

0 comments

The pith

The optimal value for online vector balancing converges exactly to the value of a mean-field problem for steering Brownian motion under an L2 drift constraint.

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

The paper studies an online balancing task in which n-dimensional Gaussian vectors arrive one by one and signs must be chosen on the fly to minimize the expected infinity-norm of the signed sum scaled by 1 over square-root n. It proves that this minimal expected imbalance V^n converges as dimension n tends to infinity to a limiting constant V^∞. The limit equals the infimum, over all admissible controls, of the expected length of the smallest terminal interval that can contain a Brownian motion whose drift satisfies a uniform-in-time L2 bound. The lower bound on the limit holds for any i.i.d. mean-zero unit-variance entries with finite fourth moments, while the matching upper bound uses Gaussian structure through a coupling with the Föllmer drift and dynamic programming.

Core claim

The optimal value V^n of the online stochastic vector balancing problem converges to V^∞ as n approaches infinity, where V^∞ is the value of the mean-field control problem that finds the narrowest terminal interval into which a Brownian motion can be steered adaptively subject to a uniform-in-time L2 constraint on the drift.

What carries the argument

The mean-field stochastic control problem of adaptively steering a Brownian motion to minimize the expected width of its terminal interval under a uniform L2 bound on the drift.

If this is right

The minimal achievable imbalance in high dimensions is governed by the solution of the Brownian steering control problem.
The lower bound on V^∞ applies to any i.i.d. entries satisfying mean zero, unit variance, and finite fourth moment.
Dynamic programming yields a characterization of the optimal control and the value V^∞.
The Föllmer-drift coupling provides an explicit construction that achieves the limiting performance for Gaussians.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

An explicit solution of the control problem would immediately give the precise asymptotic constant for the balancing task.
The same mean-field steering formulation may apply to online balancing under other norms or with additional constraints.
The compactness argument used for the lower bound suggests that similar mean-field limits exist for related online discrepancy problems.

Load-bearing premise

The random vectors have i.i.d. mean-zero unit-variance entries; the matching upper bound further requires the entries to be Gaussian.

What would settle it

Numerical computation of V^n for large n that fails to approach the independently solved value of the Brownian steering control problem would disprove the claimed convergence.

read the original abstract

We study an online vector balancing problem, in which $n$ independent Gaussian random vectors $\boldsymbol{\zeta}(1),\dots,\boldsymbol{\zeta}(n) \sim \mathcal{N}(0, I_n)$, each of dimension $n$, arrive one at a time. The goal is to choose signs $\varepsilon(1),\dots,\varepsilon(n) \in \{\pm 1\}$ with $\varepsilon(k)$ depending only on $\boldsymbol{\zeta}(1),\dots,\boldsymbol{\zeta}(k)$, so as to minimize the expected $\ell^{\infty}$ norm of the signed sum $\frac{1}{\sqrt{n}}\sum_{k = 1}^n \varepsilon(k) \boldsymbol{\zeta}(k)$. Prior work showed that the optimal value $V^n$ is $O(1)$, at least for Rademacher $\boldsymbol{\zeta}(k)$'s, by constructing specific algorithms. Our main contribution is to determine the exact limit $V^{\infty} = \lim_{n\to\infty} V^n$ as the value of a nonstandard stochastic control problem of mean-field type: find the narrowest terminal interval into which a Brownian motion can be adaptively steered under a uniform-in-time $L^2$ constraint on the drift. The proof of the lower bound $V^{\infty} \leq \liminf_{n \to \infty} V^n$ uses probabilistic compactness arguments, and is very flexible. In fact, we show that the lower bound is universal, in that it holds as long as the entries of the $\boldsymbol{\zeta}(k)$ vectors are i.i.d. with mean zero, variance 1, and finite fourth moment. The proof of the upper bound $\limsup_{n \to \infty} V^n \leq V^{\infty}$ is more delicate, relying on dynamic programming principles and a priori bounds obtained from a coupling procedure involving the F\"ollmer drift, which makes explicit use of the Gaussian structure. In addition to our main convergence result, we provide some analysis and asymptotics for the limiting mean-field control problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down the exact asymptotic for online vector balancing as the value of a mean-field control problem, with a general lower bound via compactness and a Gaussian upper bound via Föllmer coupling.

read the letter

The main takeaway is that this work identifies the precise limit of the online balancing value V^n as n goes to infinity. It equals the value of a stochastic control problem where you steer a Brownian motion adaptively under an L2 drift constraint to minimize the length of the terminal interval it reaches. The lower bound holds for general i.i.d. mean-zero unit-variance vectors with finite fourth moments using probabilistic compactness, while the upper bound matches it for Gaussians through dynamic programming and a coupling to the Föllmer drift. This is new because earlier papers only produced O(1) bounds without the exact constant. The separation between the flexible lower bound and the structure-specific upper bound is clean, and the mean-field formulation looks reusable for other high-dimensional adaptive problems. The arguments appear internally consistent with no circularity or obvious gaps in the sketched steps. A soft spot is that the upper bound relies on Gaussian structure, so we do not yet know if the same limit holds for Rademacher or other distributions. The additional analysis of the control problem is described as partial, which leaves some room for further work on explicit solutions or numerics. This paper is aimed at researchers in discrepancy theory, online algorithms, and stochastic control who care about sharp constants rather than just existence of bounded algorithms. It shows clear thinking on the literature and deserves a serious referee because the result is sharp and the methods are worth checking in detail.

Referee Report

0 major / 3 minor

Summary. The paper studies the online vector balancing problem in which n independent n-dimensional Gaussian vectors arrive sequentially and adaptive signs are chosen to minimize the expected ℓ^∞ norm of the normalized signed sum. It proves that the optimal value V^n converges as n→∞ to a limit V^∞ given by the value of a mean-field stochastic control problem: adaptively steering a Brownian motion to the narrowest possible terminal interval subject to a uniform-in-time L² constraint on the drift. The lower bound V^∞ ≤ liminf V^n holds under mild i.i.d. moment conditions via probabilistic compactness arguments and is distribution-robust; the matching upper bound limsup V^n ≤ V^∞ uses Gaussian-specific coupling via the Föllmer drift together with dynamic programming. Additional analysis and asymptotics are provided for the limiting control problem.

Significance. If the convergence result holds, the paper supplies the first exact asymptotic constant for this online balancing problem and introduces a new mean-field control formulation that captures the limiting behavior. The separation between a flexible, universal lower bound and a Gaussian-specific upper bound is a notable strength, as is the explicit link to a well-posed stochastic control problem. The additional asymptotics for the limiting object further enhance the contribution by providing concrete insight into the value V^∞.

minor comments (3)

[Introduction] The introduction would benefit from a short table or explicit list contrasting the finite-n objects (V^n, the discrete processes) with their mean-field counterparts to improve readability for readers unfamiliar with the compactness arguments.
[Dynamic Programming and Coupling] In the dynamic-programming section, the a-priori bounds obtained from the Föllmer-drift coupling are stated without an explicit reference to the moment estimates used; adding a short lemma or remark citing the precise fourth-moment assumption would clarify the dependence.
[Asymptotics of the Mean-Field Problem] The numerical illustrations of the limiting control problem would be strengthened by reporting the discretization step size and a brief convergence diagnostic for the computed value of V^∞.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive assessment. We are pleased that the referee finds the convergence result, the mean-field control formulation, and the separation between the universal lower bound and Gaussian-specific upper bound to be significant contributions, and we appreciate the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes V^∞ as the value of a mean-field stochastic control problem via two independent arguments: a distribution-robust lower bound obtained from probabilistic compactness (valid for any i.i.d. mean-zero unit-variance finite-fourth-moment entries) and a Gaussian-specific upper bound obtained from dynamic programming combined with Föllmer-drift coupling. Neither direction reduces the claimed limit to a fitted parameter, a self-referential definition, or a load-bearing self-citation; the control problem is introduced as the explicit limit object rather than being presupposed. The derivation is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard i.i.d. moment assumptions for the lower bound and Gaussian structure for the upper bound; no free parameters or invented entities are introduced.

axioms (2)

domain assumption Entries of zeta(k) are i.i.d. with mean zero, variance one, and finite fourth moment
Invoked for the universal lower bound via probabilistic compactness
domain assumption Vectors are Gaussian for the upper bound
Required to apply the Föllmer drift coupling and dynamic programming

pith-pipeline@v0.9.0 · 5696 in / 1321 out tokens · 48316 ms · 2026-05-15T01:56:54.790325+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel (J-cost uniqueness) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

V^∞ := inf { ||∫_0^1 α(t) dt + B(1)||_∞ : ||α(t)||_2 ≤ √(2/π) ∀t } (mean-field control with L² drift constraint)
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lower bound via tightness of empirical measures of coordinate trajectories and characterization of limit points in A_w (weak controls)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

Altschuler and Konstantin Tikhomirov.A threshold for online balancing of sparse i.i.d

Dylan J. Altschuler and Konstantin Tikhomirov.A threshold for online balancing of sparse i.i.d. vectors. 2025. arXiv:2509.02432 [math.PR]

work page arXiv 2025
[2]

Discrepancy Minimization via a Self-Balancing Walk

Ryan Alweiss, Yang P. Liu, and Mehtaab S. Sawhney. “Discrepancy Minimization via a Self-Balancing Walk”. In:SIAM Journal on Computing0.0 (0), STOC21-211-STOC21– 224.doi:10.1137/21M1442450.url:https://doi.org/10.1137/21M1442450

work page doi:10.1137/21m1442450.url:https://doi.org/10.1137/21m1442450
[3]

Springer, 2019

Paul Dupuis Amarjit Budhiraja.Analysis and Approximation of Rare Events. Springer, 2019

work page 2019
[4]

Constructive algorithms for discrepancy minimization

Nikhil Bansal. “Constructive algorithms for discrepancy minimization”. In:2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE. 2010, pp. 3–10

work page 2010
[5]

On-line balancing of random inputs

Nikhil Bansal and Joel H. Spencer. “On-line balancing of random inputs”. In:Random Structures & Algorithms57.4 (2020), pp. 879–891.doi:https://doi.org/10.1002/ rsa.20955. eprint:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa. 20955.url:https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20955

work page doi:10.1002/rsa 2020
[6]

Online discrepancy minimization for stochastic arrivals

Nikhil Bansal et al. “Online discrepancy minimization for stochastic arrivals”. In:Pro- ceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2021, pp. 2842–2861

work page 2021
[7]

Online vector balancing and geometric discrepancy

Nikhil Bansal et al. “Online vector balancing and geometric discrepancy”. In:Proceed- ings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing(2019). url:https://api.semanticscholar.org/CorpusID:208910783

work page 2019
[8]

Conditioned stochastic differential equations: theory, examples and application to finance

Fabrice Baudoin. “Conditioned stochastic differential equations: theory, examples and application to finance”. In:Stochastic Processes and their Applications100.1-2 (2002), pp. 109–145

work page 2002
[9]

Patrick Billingsley.Convergence of Probability Measures. 2nd ed. John Wiley & Sons, 1999

work page 1999
[10]

Borwein and Qiji J

Jonathan M. Borwein and Qiji J. Zhu.Techniques of Variational Analysis. Springer New York, NY, 2005

work page 2005
[11]

Mimicking an Itˆ o process by a solution of a stochas- tic differential equation

Gerard Brunick and Steven Shreve. “Mimicking an Itˆ o process by a solution of a stochas- tic differential equation”. In:The Annals of Applied Probability23.4 (2013), pp. 1584– 1628.doi:10.1214/12-AAP881.url:https://doi.org/10.1214/12-AAP881

work page doi:10.1214/12-aap881.url:https://doi.org/10.1214/12-aap881 2013
[12]

Carmona and F

R. Carmona and F. Delarue.Probabilistic theory of mean field games with applications. I. Mean field FBSDEs, control, and games. Vol. 83. Probability Theory and Stochastic Modelling. Springer, Cham, 2018, pp. xxv+713

work page 2018
[13]

Carmona and F

R. Carmona and F. Delarue.Probabilistic theory of mean field games with applications. II. Vol. 84. Probability Theory and Stochastic Modelling. Mean field games with com- mon noise and master equations. Springer, Cham, 2018, pp. xxiv+697

work page 2018
[14]

The Brunn-Minkowski inequality for the first eigenvalue of the Ornstein-Uhlenbeck operator and log-concavity of the relevant eigenfunction

Andrea Colesanti et al. “The Brunn-Minkowski inequality for the first eigenvalue of the Ornstein-Uhlenbeck operator and log-concavity of the relevant eigenfunction”. In: arXiv preprint arXiv:2407.21354(2024)

work page arXiv 2024
[15]

Fleming and Halil Mete Soner.Controlled Markov processes and viscosity solutions

Wendell H. Fleming and Halil Mete Soner.Controlled Markov processes and viscosity solutions. Springer, 1992

work page 1992
[16]

Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces

E. D. Gluskin. “Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces”. In:Mathematics of the USSR-Sbornik64.1 (Feb. 1989), p. 85.doi:10.1070/SM1989v064n01ABEH003295.url:https://doi.org/10. 1070/SM1989v064n01ABEH003295. 80 REFERENCES

work page doi:10.1070/sm1989v064n01abeh003295.url:https://doi.org/10 1989
[17]

Smoothed Analysis with Adaptive Adversaries

Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. “Smoothed Analysis with Adaptive Adversaries”. In:Journal of the ACM71.3 (2024), pp. 1–34.doi:10.1145/ 3656638. arXiv:2102.08446

work page arXiv 2024
[18]

Algorithmic threshold for high-dimensional projection pursuit II: asymptotics in constraint satisfaction problems

Brice Huang and Mark Sellke. “Algorithmic threshold for high-dimensional projection pursuit II: asymptotics in constraint satisfaction problems”. In preparation. 2026

work page 2026
[19]

Algorithmic threshold for high-dimensional projection pursuit I: general theory

Brice Huang, Mark Sellke, and Nike Sun. “Algorithmic threshold for high-dimensional projection pursuit I: general theory”. In preparation. 2026

work page 2026
[20]

Brownian local times and taboo processes

Frank B Knight. “Brownian local times and taboo processes”. In:Transactions of the American Mathematical Society143 (1969), pp. 173–185

work page 1969
[21]

A deterministic-control-based approach motion by curvature

Robert Kohn and Sylvia Serfaty. “A deterministic-control-based approach motion by curvature”. In:Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences59.3 (2006), pp. 344–407

work page 2006
[22]

InProceedings of the 56th Annual ACM Symposium on Theory of Computing (Vancouver, BC, Canada)(STOC 2024)

Janardhan Kulkarni, Victor Reis, and Thomas Rothvoss. “Optimal Online Discrepancy Minimization”. In:Proceedings of the 56th Annual ACM Symposium on Theory of Com- puting (STOC 2024). 2024, pp. 1832–1840.doi:10.1145/3618260.3649720. arXiv: 2308.01406

work page doi:10.1145/3618260.3649720 2024
[23]

Limit theory for controlled McKean–Vlasov dynamics

Daniel Lacker. “Limit theory for controlled McKean–Vlasov dynamics”. In:SIAM Jour- nal on Control and Optimization55.3 (2017), pp. 1641–1672

work page 2017
[24]

Ladyˇ zenskaja, V.A

O.A. Ladyˇ zenskaja, V.A. Solonnikov, and N.N. Ural’ceva.Linear and Quasi-linear Equations of Parabolic Type. American Mathematical Society, 1968

work page 1968
[25]

Representation formula for the entropy and functional inequalities

Joseph Lehec. “Representation formula for the entropy and functional inequalities”. In: Annales de l’IHP Probabilit´ es et statistiques. Vol. 49. 3. 2013, pp. 885–899

work page 2013
[26]

Constructive discrepancy minimization by walking on the edges

Shachar Lovett and Raghu Meka. “Constructive discrepancy minimization by walking on the edges”. In:SIAM Journal on Computing44.5 (2015), pp. 1573–1582

work page 2015
[27]

Representation of Itˆ o Integrals by Lebesgue/Bochner Integrals

Qi L¨ u, Jiongmin Yong, and Xu Zhang. “Representation of Itˆ o Integrals by Lebesgue/Bochner Integrals”. In:Journal of the European Mathematical Society14.6 (2012), pp. 1795– 1823

work page 2012
[28]

The strong log-concavity for first eigenfunction of the Ornstein-Uhlenbeck operator in the class of convex bodies

Lei Qin. “The strong log-concavity for first eigenfunction of the Ornstein-Uhlenbeck operator in the class of convex bodies”. In:arXiv preprint arXiv:2507.00819(2025)

work page arXiv 2025
[29]

Moment Inequalities for Sums of Dependent Random Variables under Projective Conditions

Emmanuel Rio. “Moment Inequalities for Sums of Dependent Random Variables under Projective Conditions”. In:Journal of Theoretical Probability22 (2009), pp. 146–163

work page 2009
[30]

L. C. G. Rogers and David Williams.Diffusions, Markov Processes and Martingales: Volume 1, Foundations. Second edition. Cambridge University Press, 2000

work page 2000
[31]

Balancing games

Joel Spencer. “Balancing games”. In:Journal of Combinatorial Theory, Series B23.1 (1977), pp. 68–74.issn: 0095-8956.doi:https://doi.org/10.1016/0095-8956(77) 90057-0.url:https://www.sciencedirect.com/science/article/pii/0095895677900570

work page doi:10.1016/0095-8956(77 1977
[32]

Well-posedness of multidimensional diffusion processes with weakly differentiable coefficients

Dario Trevisan. “Well-posedness of multidimensional diffusion processes with weakly differentiable coefficients”. In:Electronic Journal of Probability21 (Jan. 2016).doi: 10.1214/16-EJP4453. REFERENCES 81 C. Fiedler, IEOR Department, Columbia University, 500 W. 120th Street, New York, NY 10027, USA Email address:christian.fiedler@columbia.edu J. Jackson, D...

work page doi:10.1214/16-ejp4453 2016