We propose an extension of Yao's standard two-party communication model, where Alice and Bob respectively hold probability distributions p and q over inputs to a function f, rather than singleton inputs. Their goal is to estimate E[f(x,y)] to within additive error eps where x is drawn from p and y is drawn (independently) from q. We refer to this as the distributed estimation problem for f. We motivate this problem by showing that communication problems studied in sketching, databases and learning are instantiations of distributed estimation for various functions f. Our goal is to understand how the communication scales with the complexity of f and the error parameter eps.
The naive sampling protocol achieves communication that scales as O(1/eps^2). We design a new debiasing protocol for arbitrary bounded functions that requires communication only linear in 1/\eps, and gives better variance reduction than random sampling. We develop a novel spectral technique to show lower bounds for distributed estimation, and use it to show that the Equality function is the easiest full rank Boolean function for distributed estimation. This technique yields tight lower bounds for most functions, with set-disjointness being the notable exception. Based on joint work with Raghu Meka (UCLA), Prasad Raghavendra (UC Berkeley), Mihir Singhal (UC Berkeley) and Avi Wigderson (IAS).
Short Bio: I am a machine learning researcher at
Apple where I work on the foundations of machine learning. I aspire to do fundamental theoretical research that impacts practical problems. My current focus is on the interplay between multigroup fairness, loss minimization and indistinguishability. I am also interested in questions related to calibration, distribution drift and anomaly detection.I have broad interests in theoretical computer science, having worked on coding and information theory, pseudorandomness and computational complexity. On the applied side, I have worked on systems for storing and interactively visualizing large datasets.In the past, I have been a researcher at
VMware Research,
Microsoft Research in Redmond and Silicon Valley, a graduate student at
Georgia Tech and an undergraduate at
IIT Bombay
