Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation

Information constraints play a key role in machine learning. Of course, the main constraint is the availability of only a finite data set, from which the learner is expected to generalize. However, many problems currently researched in machine learning can be characterized as learning with additional information constraints, arising from the manner in which the learner may interact with the data. Some examples include: - Communication constraints in distributed learning: There has been much work in recent years on learning when the training data is distributed among several machines (with [14, 2, 28, 47, 25, 31, 9, 17, 38] being just a few examples). Since the machines may work in parallel, this potentially allows significant computational speedups and the ability to cope with large datasets. On the flip side, communication rates between machines is typically much slower than their processing speeds, and a major challenge is to perform these learning tasks with minimal communication.