We consider the problem of learning from distributed data and analyze fundamental algorithmic and communication complexity questions involved. Broadly, we consider a framework where information is distributed between several locations, and our goal is to learn a low-error hypothesis with respect to the overall data by using as little communication, and as few rounds of communication, as possible. As an example, suppose k research groups around the world have collected large scientific datasets, such as genomic sequence data or sky survey data, and we wish to perform learning over the union of all these different datasets without too much communication.
In this talk, I will first discuss a general statistical or PAC style framework for analyzing communication complexity issues involved when doing distributed supervised machine learning, i.e., learning from annotated data distributed across multiple locations. I will discuss general lower bounds on the amount of communication needed to learn a given class and broadly-applicable techniques for achieving communication-efficient learning, as well as efficient learning algorithms with especially good communication performance for specific interesting classes.
I will also discuss algorithms with good communication complexity for unsupervised learning and dimensionality reduction problems, with interesting connections to efficient distributed coreset construction.

An effective technique for solving optimization problems over massive data sets is to partition the data into smaller pieces, solve the problem on each piece and compute a representative solution from it, and finally obtain a solution inside the union of the representative solutions for all pieces. Such an algorithm can be implemented easily in 2 rounds of MapReduces or be applied in an streaming model. This technique can be captured via the concept of {\em composable core-sets}, and has been recently applied to solve diversity maximization problems as well as several clustering problems. However, for coverage and submodular maximization problems, impossibility bounds are known for this technique. In this talk, after a initial discussion about this technique and applications in diversity maximization and clustering problems, we focus on the submodular maximization problem, and show how to apply a randomized variant of composable core-set problem, and achieve 1/3-approximation for monotone and non-montone submodualr maximization problems. We prove this result by applying a simple greedy algorithm and show that a large class of algorithms can be deployed in this framework. Time-permitting, we show a more involved algorithm that achieves 54% of the optimum in two rounds of MapReduces.
The main part of the talk is to appear in STOC 2015 and is a joint work with Morteza ZadiMoghaddam. The initial parts are from two recent papers that appeared in PODS 2014 and NIPS 2014.

The research on parallel algorithms for modern massive computation systems has identified minimizing the number of computation rounds as one of the main challenges. In the case of graph algorithms, it has encountered a natural barrier in the form of the connectivity problem. This problem is widely believed to require a large, super-constant number of computation rounds if the number of nodes is significantly larger than the amount of memory of a single machine. Moreover, a lower bound on the number of computation rounds for connectivity would imply a similar lower bound for a number of graph problems.
I will present a few graph algorithms that require a constant number of computation rounds as long as the number of nodes is at most polynomially larger than the amount of memory of a single machine. The algorithms either take advantage of a natural assumption on the input data or solve a slightly relaxed version of the problem. The set of applied techniques ranges from geometric random partitioning to graph exploration methods developed for sublinear-time algorithms.
(The talk will include results obtained in collaboration with Alexandr Andoni, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Aleksandar Nikolov, Piotr Sankowski, and Grigory Yaroslavtsev.)

Modern massively parallel computation systems using MapReduce/Hadoop and related primitives make specific assumptions about the local computations available per round of computation. We consider a complexity model that relaxes these assumptions. We identify the memory required per processor (or equivalently the amount of communication required per processor per step) as a key parameter of such computations, a parameter we term the load. This yields a communication complexity-based model, like a simplified version of Valiant's Bulk Synchronous Parallel model, in which we consider complexity tradeoffs between the number of processors, the load, and number of rounds required to solve specific problems.

In this model, we consider the complexity of solving families of database query problems that correspond to (hyper)-graph algorithms on multipartite graphs and hypergraphs, including problems like triangle-enumeration and path-finding. For single round computation, in many instances we show that simple well-known MapReduce algorithms provide optimal tradeoffs between processors and the load. We also analyze how the best algorithms become more complicated as the distribution of degrees in the input graphs and hypergraphs becomes more skewed.

For multiple rounds, analyzing the general model requires understanding of circuit complexity over non-standard bases. However, in a more restricted version of the model (which is still sufficiently general to simulate MapReduce) we show some of the first lower bounds for multi-round computations on MapReduce-like models.

Joint work with Paraschos Koutris and Dan Suciu.

We present constant-factor approximation algorithms for two graph clustering problems---densest subgraph and correlation clustering---that are easily implementable in computational models such as MapReduce and streaming, and run in a small number of rounds.

MapReduce has been widely considered for optimizing submodular functions over large data sets and several techniques have been developed. In this talk, we will discuss the Sample and Prune procedure. Sample and Prune is a distributed sampling method used to efficiency discover a small set of representative elements from a large data set. We discuss how Sample and Prune can be used for submodular optimization in MapReduce. In particular, we show how this procedure can be utilized to simulate a class of greedy sequential algorithms for submodular optimization in MapReduce. We will further discuss its use to construct new distributed algorithms for submodular optimization and how it could possibly be extended to construct efficient algorithms for a wide range of problems in the distributed setting.