Department Colloquium
Nov
30
2026
Nov
30
2026
Description
Abstract (text only): This talk will be about recent joint work with Christian Fiedler, Daniel Lacker, and Jonathan Niles-Weed, in which we derive a mean-field scaling limit for a class of combinatorial optimization problems. In particular, we study a stochastic online version of the vector balancing problem: n independent standard Gaussian random vectors, each of dimension n, arrive one at a time. The goal is to assign a sign to each vector, based only on the vectors observed so far, so as to minimize the expected maximum norm of the signed sum. Prior work showed that the optimal value is O(sqrt(n)), at least for vectors with independent Rademacher entries, by constructing and analyzing specific algorithms. Our main contribution is to prove that, after rescaling by sqrt(n), it converges to the value of a nonstandard stochastic control problem of mean-field type.