Online Discrepancy for Sub-Exponential Product Distributions via Regularization
We study online discrepancy minimization for independent random vectors in $\mathbb{R}^n$ with independent coordinates. Our deterministic algorithms require no knowledge of the horizon, and their guarantees hold at every prescribed deterministic terminal time $T$. For unit-variance sub-exponential coordinates with $ψ_1$-norms at most $σ$, we obtain terminal discrepancy $O(σ^4\sqrt n)$ with failure probability $\exp(-Ω(σ^3\sqrt n))$. Independently masking centered unit-variance marks from the same class with retention probability $k/n$ gives $O(σ^4\sqrt k)$ discrepancy with failure…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.10040
curl -X POST /api/v1/records/arxiv/2608.10040/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.10040/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'