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

By Ohad Shamir. 2013

113 citations recorded by the source corpus.

Many machine learning approaches are characterized by information constraints on how they interact with the training data. These include memory and sequential access constraints (e.g. fast first-order methods to solve stochastic optimization problems); communication constraints (e.g. distributed learning); partial access to the underlying data (e.g. missing features and multi-armed bandits) and more. However, currently we have little understanding how such information constraints fundamentally affect our performance, independent of the learning problem semantics. For example, are there learning problems where any algorithm which has small memory footprint (or can use any bounded number of bits from each example, or has certain communication constraints) will perform worse than what is possible without such constraints? In this paper, we describe how a single set of results implies positive answers to the above, for several different settings.

Subfields: Artificial Intelligence, Management Science and Operations Research, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Scaling & Learning Theory

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, background): “…these vector representations can only eﬀectively be produced on GPU systems, as the underlying processes either have high arithmetic complexity and/or high data bandwidth demands [28], or cannot be eﬀectively partitioned without failing due to communication overhead or representation quality [38].”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “This is along the line of recent work on distributed mean estimation under communication constraints [14], [28], [45], [55], [58], although some of these works consider more general communication models than what we allow.”
Distributed Simulation and Distributed Inference (2018, background): “The problem described above has itself received signiﬁcant attention lately in various communities (see, for instance, [BPC + 11, BBFM12, Sha14, DGL + 17, HÖW18]), with the objective of performing parameter or density estimation while minimizing the number of players (or, equivalently, the amount of”
Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, background): “acterize inf Π BB inf ˆθ sup θ∈Θ Eθkθˆ−θk2 2. Distributed parameter estimation and function computation has been considered in many recent works; we refer to Duchi et al. (2013); Zhang et al. (2013); Shamir (2014); Garg et al. (2014); Braverman et al. (2016); Xu and Raginsky (2017) and the reference”
Deep learning with Elastic Averaging SGD (2014, background): “This paper focuses on the problem of reducing the parameter communication overhead Shamir (2014) 1989) is a more general problem and is not addressed in this work (we explain the details of sampling the entire dataset in parallel in Section 7).”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “Finally, optimal convergence rates for distributed algorithms were investigated in [8] for smooth and strongly-convex objective functions, and [16, 17] for totally connected networks.”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, background): “In several related ﬁelds, complexity lower bounds were recently investigated, including the sequential optimization of a sum of functions [15, 16], distributed optimization in ﬂat (i.e. totally connected) networks [17, 18], or distributed stochastic optimization [19].”
Information-Theoretic Lower Bounds on Bayes Risk in Decentralized Estimation (2016, background): “The lower bounds will also depend on the a priori uncertainty about W , measured either by its small ball probability or by its differential entropy.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “The problem of distributed density estimation, too, has gathered recent interest in various statistical settings [5], [9], [14], [22], [33], [42], [43], [48]–[50].”
On the Randomized Complexity of Minimizing a Convex Quadratic Function (2018, background): “Other works have considered lower bounds which hold when the optimization algorithm is subject to memory constraints [28, 27, 25].”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, background): “[31] considers the problem of detecting the biased coordinate of product Bernoulli distributions under communication constraints, which can be viewed as a 1-sparse detection problem.”
Minimax rates for memory-bounded sparse linear regression (2015, methodology): “…have investigated privacy (Kasiviswanathan et al., 2011; Duchi et al., 2013), communication and memory (Zhang et al., 2013; Garg et al., 2014; Shamir, 2014), and computational constraints (Berthet and Rigollet, 2013)—and study bounds on the performance of regression estimators under memory…”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “The lower bound in [27], too, allows sequentially interactive protocols.”
Swayam: distributed autoscaling to meet SLAs of machine learning inference services with resource efficiency (2017, background): “ML inference requests tend to have large memory footprints and are CPU-bound [4, 13, 27].”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “…optimal convergence rates for distributed algorithms were investigated by Scaman et al. (2017) for smooth and strongly convex objective functions, Shamir (2014); Arjevani and Shamir (2015) for totally connected networks, and more recently by Dvin-skikh and Gasnikov (2019) who derive optimal…”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, background): “From a fundamental perspective, studying the tradeoff between communication complexity (Yao, 1979; Abelson, 1980) and learning/optimization error has recently attracted some interest (Balcan et al., 2012; Daumé III et al., 2012; Shamir, 2014).”
Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “While statistical similarities of local objective functions and the statistics/communication trade-off have been investigated and exploited in centralised server-clients setup, typically in the analysis and design of divide-and-conquer schemes [60, 28, 20, 32, 26, 1, 62, 46, 45, 61, 2], only recentl”
Distributed stochastic optimization for deep learning (thesis) (2016, unknown): “We will focus on the problem of reducing the parameter communication overhead between the master and the local workers [50, 16, 60, 43, 48].”