A theory of the learnable

By Leslie G. Valiant. 1984

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “The generalization error of a hypothesis h : X → { 0 , 1 } w.r.t. a target concept c and a distribution D is deﬁned as Deﬁnition 2.6 (PAC Learning [63]) .”
Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, background): “Maximizing margin is known to have a regularizing effect and is said to improve generalization (Valiant, 1984; Cortes & Vapnik, 1995).”
Stealing Machine Learning Models via Prediction APIs (2016, background): “Our results highlight the need for careful ML model deployment and new model extraction countermeasures.”
Fairness Through Computationally-Bounded Awareness (2018, background): “The connection between learning and pseudorandom functions [23, 11] is well-established; under stronger cryptographic assumptions as in [2], the reduction implies that a running time of ⌦(|C|) is necessary for some constant ↵ > 0.”
Machine Unlearning (2019, background): “It takes in a dataset, a hypothesis space, and an objective: • Dataset: Consistent with the probably approximately correct (PAC) learning setting [23], we assume there is an underlying distribution on Z that describes the data; the learner has no direct knowledge of the distribution but has access…”
A Model of Inductive Bias Learning (2000, methodology): “In this paper we introduce and analyze a formal model ofbias learning that builds upon the PAC model of machine learning and its variants (Vapnik, 1982; Valiant, 1984; Blumer, Ehrenfeucht, Haussler, & Warmuth, 1989; Haussler, 1992).”
Domain Adaptation: Learning Bounds and Algorithms (2009, methodology): “In the standard PAC model (Valiant, 1984) and other theoretical models of learning, training and test instances ar assumed to be drawn from the same distribution.”
On the mathematical foundations of learning (2001, methodology): “We mention as examples the theory of Neural Networks going back to McCulloch and Pitts [25] and Minsky and Papert [27], the PAC learning of Valiant [40], Statistical Learning Theory as developed by Vapnik [42], and the use of reproducing kernels as in [17] among many other mathematical developments.”
Continual Learning for Robotics (2019, background): “In any learning problem (be it classification, RL or unsupervised learning), the ability to adapt to new concepts to be learned (from the probably approximately correct (PAC) ML framework (Valiant, 1984)), as well as new instances of each concept, should be accounted.”
Introduction to Online Convex Optimization (2016, methodology): “The foundations of statistical and computational learning theory were put forth in the seminal works of Vapnik (106) and Valiant (105) respectively.”
Learning in the presence of malicious errors (1988, methodology): “By applying this technique to the algorithm of Valiant [23] for the class of monomials in the error-free model, we obtain the following corollary:”
Inductive Logic Programming: Theory and Methods (1994, methodology): “In contrast, Valiant's [140] PAC (ProbablyApproximately-Correct) framework is aimed at providing complexity results for machine learning algorithms.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “Indeed, how to obtain a result that does not depend on the data distribution, but only on the concept class itself, lies in the center of PAC-learning which is one of the foundations of machine learning theory [48].”
Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems (2015, background): “Valiant [45] showed that DNFs could be learned in polynomial time in the PAC (probably approximately correct) setting, and recent work has improved those bounds via polynomial threshold functions [23] and Fourier analysis [14].”
Multiple Source Adaptation and the Rényi Divergence (2009, methodology): “This assumption forms the basis of common learning frameworks such as the PAC model [17].”
The ethics of algorithms: Mapping the debate (2016, neutral): “Statistical learning theory (James et al., 2013) and computational learning theory (Valiant, 1984) are both concerned with the characterisation and quantiﬁcation of this uncertainty.”