Exact Universality of Online Discrepancy
We study online vector balancing with $N$ random vectors in $\mathbb{R}^M$ revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected $\ell^\infty$ norm of the final signed sum. For i.i.d. entries with mean zero, variance one, and a finite fourth moment, we prove that, as $M/N\toα\in(0,\infty)$, the optimal value divided by $\sqrt N$ converges to a limit $R_α$ independent of the entry distribution. This limit is the stochastic control value identified for Gaussian inputs by Fiedler, Jackson, Lacker, and Niles-Weed. In…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.00103
curl -X POST /api/v1/records/arxiv/2610.00103/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.00103/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'