2/9/23 | 4:15pm | E25-111

Robert Kleinberg

Professor
Cornell

Abstract: Consider a seller experimenting with posted prices to estimate the distribution of consumers' willingness to pay, or a participant in an advertising auction varying their bid to learn the distribution of winning bids. Both of these parties face the problem of estimating a univariate distribution, given the ability to ask one threshold query per sample. This talk will tackle the problem in a challenging setting where samples could be generated by an arbitrary (potentially even adaptive) process. Our main result quantifies, to within a constant factor, the threshold query complexity of estimating the empirical CDF of a sequence of elements of [n], up to a given error tolerance in Kolmogorov distance, using one query per sample. The complexity depends only logarithmically on n, and our result can be interpreted as extending existing logarithmic complexity results for noisy binary search to the more challenging non-stochastic setting. A key feature of our solution is the use of Blackwell's Approachability Theorem to solve a related estimation problem in which simultaneous queries are allowed.

This is joint work with Princewill Okoroafor, Vaishnavi Gupta, and Eleanor Goh.

Bio: Bobby Kleinberg is a Professor of Computer Science at Cornell University, currently on sabbatical as a Visiting Faculty Researcher at Google. His research concerns algorithms and their applications to machine learning, economics, networking, and other areas. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies; he and his co-workers received the 2018 SIGCOMM Networking Systems Award for pioneering the first Internet content delivery network. He is a Fellow of the ACM and a recipient of the Microsoft Research New Faculty Fellowship, an Alfred P. Sloan Foundation Fellowship, and an NSF CAREER Award.