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

Wireless Network Intelligence at the Edge (2018, background): “This missing block can be addressed by the Bayesian learning theory [125] and the probably approximately correct (PAC) framework [126].”
Multi-Fidelity Automatic Hyper-Parameter Tuning via Transfer Series Expansion (2019, methodology): “According to PAC learning theorem (Valiant 1984), the evaluation will approach real generalization performance when the training dataset is large enough.”
Boolean Decision Rules via Column Generation (2018, background): “[47, 32, 24]) focuses on the ideal noiseless setting (sometimes allowing arbitrary queries) and is less relevant to the practice of learning compact models from noisy data.”
Learning Theory for Distribution Regression (2014, background): “Long and Tan (1998) proved the PAC learnability (probably approximately correct; Valiant, 1984) of the APR hypothesis class, if all instances in each bag are 4.”
Reinforcement Learning: A Survey (1996, background): “For example, in the well-known PAC framework (Valiant, 1984), there is a learning period during which mistakes do not count, then a performance period during which they do.”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, methodology): “Private learning was introduced in [14] as a combination of Valiant’s PAC learning model [21] and differential privacy (applied to the examples used by the learner).”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “5 Generalization Guarantees for Metric Learning The derivation of guarantees on the generalization performance of the learned model is a wide topic in statistical learning theory (Vapnik and Chervonenkis, 1971; Valiant, 1984).”
Mining association rules between sets of items in large databases (1993, background): “The work of Valiant [12] [13] deals with learning boolean formulae.”
Characterizing the sample complexity of private learners (2013, background): “[16] defined in 2008 private learning as a combination of probably approximately correct (PAC) learning [19] and differential privacy [11].”
Interactive machine learning for health informatics: when do we need the human-in-the-loop? (2016, background): “The underlying principle is bias learning based on probable approximately correct learning (PAC learning) [79].”
Simultaneous Private Learning of Multiple Concepts (2015, background): “One family of such analyses that has received a lot of attention is PAC learning [28].”
Multiple Instance Learning: Algorithms and Applications (2008, background): “In particular, several researchers focused on developing Probably Approximately Correct (PAC) [14] learning algorithms, and showing sample complexity bounds.”
PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification (2003, unknown): “PAC stands for probably approximately correct, the framework was introduced by Valiant (1984). In this paper, we use the term PAC bound as synonym for “distribution-free large deviation bound”: a bound on the probability that an i.”