An Introduction to Computational Learning Theory

By Michael Kearns, Umesh V. Vazirani. 1994

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

Interpreting support vector machine models for multivariate group wise analysis in neuroimaging (2015, positive): “Since learning is ultimately based on data compression Kearns and Vazirani (1994) we may conjecture, for random permutations no compression will be achieved by the SVM.”
Fairness in Criminal Justice Risk Assessments: The State of the Art (2017, neutral): “This is a common approach in computer science, especially for machine learning (Bishop 2006: section 1.5; M. J. Kearns 1994:section 1.2), and also can be found in econometrics (White 1980) and statistics (Buja et al. 2018a; Freedman 1981).”
Introduction to Online Convex Optimization (2016, neutral): “, [65].”
Calibration for the (Computationally-Identifiable) Masses (2017, neutral): “Standard generalization arguments [KV94] show that if the set of queries we might ask is ﬁxed in advance, then we could bound the sample complexity needed to answer these non-adaptive queries as ˜ O (log |C| /ω 2 ).”
The Set Covering Machine (2003, unknown): “|) sets (Chvátal, 1979, Kearns and Vazirani, 1994).”
The Complexity of Differential Privacy (2017, unknown): “[70]) tells us that with high probability over x1 · · ·xn, we have”
Learning Adversary Behavior in Security Games: A PAC Model Perspective (2015, unknown): “Our first contribution is using the Probably Approximately Correct (PAC) model [16, 2] to analyze the learning problem at hand.”
Ambiguous chance constrained problems and robust optimization (2006, unknown): “…are N independent, identically distributed (IID) samples from the distribution Q. de Farias and Van Roy [14] consider the special case where and f (x, h) = f (x, ( ¯ h, h 0 )) = ¯ h T x + h 0 and use results from Computational Learning Theory [1] [31] [45] to show that for all N ≥ 4n ln 12 + 4 ln 2”
The Dependence of Effective Planning Horizon on Model Accuracy (2015, unknown): “This is analogous to a standard generalization bound [6], and implies that an intermediate value of γ will generally be optimal; moreover, as the amount of data (n) increases, so does the optimal γ.”
Exact Rule Learning via Boolean Compressed Sensing (2013, unknown): “…widely used by analytics practitioners today precisely due to their interpretability, rely on greedy, heuristic training procedures because rule learning is inherently combinatorial and notoriously difficult from the perspective of the theory of computation (Valiant, 1985; Kearns & Vazirani, 1994).”
FloatBoost learning and statistical face detection (2004, unknown): “Originating from the PAC (probably approximately correct) learning theory [2], [3], AdaBoost provably achieves arbitrarily good bounds on its training and generalization errors [1], [4] provided that weak classifiers can perform slightly better than random guessing on every distribution over the…”
Multicalibration: Calibration for the (Computationally-Identifiable) Masses (2018, unknown): “Standard uniform convergence arguments (Kearns & Vazirani, 1994) show that if the set of queries we might ask is fixed in advance, then we could bound the sample complexity needed to answer these non-adaptive queries as Õ(log |C|/ω2).”