Memory, Communication, and Statistical Queries

By Jacob Steinhardt, Gregory Valiant, Stefan Wager. 2016

90 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “7 We observe that the unifying treatment based on chi-square distance is reminiscent of the lower bounds for learning under statistical queries (SQ) derived in [24], [25], [47].”
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].”
Provable limitations of deep learning (2018, background): “ther discussion below and in Sections2.3and7. In [Raz16], it is shown that one needs either quadratic memory or an exponential number of samples in order to learn parities, settling a conjecture from [SVW15]. This gives a rst non-trivial lower bound on the number of samples needed for a learning pro”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, background): “Time-Space Tradeoffs for Learning Another related line of work (beginning with [37, 33]; see [22] for a more recent summary of results) establishes time-space tradeoffs for learning: problems where any learning algorithm requires either a large memory or a large number of samples.”
Statistical algorithms and a lower bound for detecting planted cliques (2012, methodology): “[Zhang et al., 2013, Steinhardt and Duchi, 2015, Steinhardt et al., 2016].”
A General Characterization of the Statistical Query Complexity (2016, methodology): “In this context it is known that access to an SQ oracle is equivalent (up to polynomial factors) to being able to extract only a limited number of bits from each data sample (Ben-David and Dichterman, 1998; Feldman et al., 2012; Steinhardt et al., 2016).”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “…in a large number of other theoretical and practical contexts, such as distributed data access (Chu et al. [20], Roy et al. [78], Sujeeth et al. [90]), evolvability (Feldman [35, 36], Valiant [92]), and memory-/communication-limited machine learning (Balcan et al. [4], Steinhardt et al. [87]).”