MENU 
Theory Seminar
Victor Reis: Optimal Online Discrepancy Minimization
Victor ReisInstitute for Advanced Study
WHERE:
3941 Beyster BuildingMap
WHEN:
Friday, October 20, 2023 @ 2:00 pm - 3:00 pm
This event is free and open to the publicAdd to Google Calendar
This event is free and open to the publicAdd to Google Calendar
WEB: Event Website
SHARE:
PASSCODE: 430018
We prove that there exists an online algorithm that for any sequence of vectors v_1, …, v_T in R^n of Euclidean norm at most 1, arriving one at a time, decides random signs x_1,…, x_T ∈ {−1,1} so that for every t ≤ T, their signed prefix sum is 10-subgaussian.
This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums O(sqrt(log(nT)))-subgaussian, and gives a O(sqrt(log T)) bound on the discrepancy max_{t \le T} \|\sum_{i=1}^t x_i v_i\|_\infty.
Our proof combines a generalization of Banaszczyk’s prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching Ω(sqrt(log T)) strategy for an oblivious adversary.