[YPNG] YPNG 6 May 2016

[Sekhar Tatikonda]

Hi Everyone,


This Friday Yuchen Zhang from Berkeley will talk about:


Title: Communication complexity of statistical estimation and linear
algebraic computation

Abstract: We study two distributed data processing tasks where
communication is an efficiency bottleneck. The first task is distributed
statistical estimation, where the data points are i.i.d. sampled from an
underlying distribution, but stored across separate locations. The goal is
to estimate a parameter of the distribution. We demonstrate that there is a
fundamental trade-off between the statistical accuracy and the number of
bits exchanged across the network, no matter how the algorithm is designed. The
trade-off holds for a variety of problems, including location estimation in
several families and parameter estimation in different types of regression
models.

The second task is to compute the generalized rank of an n-by-n matrix
whose entries are stored across separate locations. The algorithm can
output approximate solutions, but the goal is to communicate as little as
possible. We show that any deterministic algorithm solving this problem
must communicate Ω(n^2) bits, which is order-equivalent to transmitting the
whole matrix. In contrast, we present a randomized algorithm that
communicates only O(n) bits to compute good approximate solutions. The
upper bound is matched by an Ω(n) lower bound on the randomized
communication complexity.

See you Friday at 11am in the Stat's classroom.

Regards,
sekhar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/ypng/attachments/20160503/a23c9ab5/attachment.html