Efficient noise-tolerant learning from statistical queries

By Michael Kearns. 1998

Subfields: Optimization & Training, Statistical 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 Optimization & Training

In Statistical Learning Theory

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “This problem is well-known for separating PAC learning from the Statistical Query (SQ) learning model [32].”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, methodology): “As observed in Blum et al. (2005), binary summation is of particular interest in ML since it is sufficient for implementing any learning algorithm based on statistical queries (Kearns, 1998), which includes most of the known PAC-learning algorithms.”
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model (2019, background): “That is, every learning problem solvable using a small number of statistical queries [13] can be solved privately and efﬁciently in the shufﬂed model.”
Distributed Differential Privacy via Shuffling (2018, methodology): “These protocols are sufficient to implement any algorithm in the statistical queries model [22], which includes methods such as gradient descent.”
Local, Private, Efficient Protocols for Succinct Histograms (2015, methodology): “from a distribution, then every LDP learning algorithm can be simulated in the statistical queries model [16].”
Privacy Aware Learning (2012, neutral): “Before doing so, we require some formalization of our notions of privacy and error measures, which we now provide.”
Algorithmic stability for adaptive data analysis (2015, background): “Although statistical queries are surprisingly general [Kea93], we would like to be able to ask more general queries on the distribution P that capture a wider variety of machine learning and data mining tasks.”
Fairness Through Computationally-Bounded Awareness (2018, neutral): “In general, agnostic learning is considered a notoriously hard computational problem [15, 17, 8]; that said, in the context of fairness in machine learning, [16] show that using heuristic methods to agnostically learn linear hypotheses seems to work well in practice.”
Machine Unlearning (2019, background): “2Kearns [16] shows that any PAC learning algorithm has a corresponding SQ learning equivalent.”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “We now briefly show that SVM learning does not generally fit the Statistical Query model (Kearns, 1998) and so cannot simply be made differentially private by directly applying the existing pattern of making Statistical Query model learners privacy preserving (Blum et al.”
Towards Making Systems Forget with Machine Unlearning (2015, background): “It is general because the summation form is from statistical query (SQ) learning [48].”
Preserving Statistical Validity in Adaptive Data Analysis (2014, background): “Next, a request for such an estimate is referred to as a statistical query in the context of the well-studied statistical query model [30, 21], and it is known that using statistical queries in place of direct access to data it is possible to implement most standard analyses used on i.”
Adversarial examples from computational constraints (2018, methodology): “The statistical query (SQ) model of computation from Kearns (1998) is a particularly successful instance of approach (ii) for learning theory: (a) most known learning algorithms fall in the framework, including in particular logistic regression, SVM, stochastic gradient descent, etc; and (b) SQ-hard”
A reliable effective terascale linear learning system (2011, methodology): “In general, any statistical query algorithm (Kearns, 1993) can be parallelized with AllReduce with only a handful of additional lines of code.”
A Simple and Practical Algorithm for Differentially Private Data Release (2010, methodology): “The algo-rithm is a combination of the Multiplicative Weights approach of [16, 15], maintaining and correcting an approximating dataset through queries on which the approximate and true datasets diﬀer, and the Exponential Mechanism [22], which selects the queries most informative to the…”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, background): “In [23], Kearns gave an efficient (noise resistant) non-private learner for this class.”