Toward Efficient Agnostic Learning

By Michael Kearns, Robert E. Schapire, Linda Sellie. 1992

In this paper we initiate an investigation of generalizations of the Probably Approximately Correct (PAC) learning model that attempt to significantly weaken the target function assumptions. The ultimate goal in this direction is informally termed agnostic learning, in which we make virtually no assumptions on the target function. The name derives from the fact that as designers of learning algorithms, we give up the belief that Nature (as represented by the target function) has a simple or succinct explanation. We give a number of positive and negative results that provide an initial outline of the possibilities for agnostic learning. Our results include hardness results for the most obvious generalization of the PAC model to an agnostic setting, an efficient and general agnostic learning method based on dynamic programming, relationships between loss functions for agnostic learning, and an algorithm for a learning problem that involves hidden variables.

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

Differential Privacy Has Disparate Impact on Model Accuracy (2019, background): “Prior work on subgroup fairness aims to achieve good accuracy on all subgroups [21] using agnostic learning [22, 29].”
Robust Support Vector Machine Training via Convex Outlier Ablation (2006, background): “The hinge loss is a well motivated proxy for misclassification error, which itself is non-convex and NP-hard to optimize ( Kearns, Schapire, & Sellie 1992; Hoeffgen, Van Horn, & Simon 1995).”
The power of localization for efficiently learning linear separators with noise (2013, methodology): “We note that the results from our theorems in this model translate immediately into similar guarantees for the agnostic model of [34] (used commonly both in passive and active learning (e.”
Learning Kernel-Based Halfspaces with the 0-1 Loss (2011, methodology): “Following the agnostic probably approximately correct (PAC) learning framework [17], we say that an algorithm ( , δ)-learns a concept class H of classifiers using m examples if with probability of at least 1 − δ over a random choice of m examples the algorithm returns a classifier ĥ that satisfies”
Learning geometric concepts with nasty noise (2017, methodology): “In the agnostic (adversarial label noise) PAC model [21, 27], the L1-regression algorithm of Kalai et al.”
On agnostic boosting and parity learning (2008, methodology): “In Appendix A, we illustrate through the class of unions of n intervals on X = R. While this class is already known to be learnable [ KSS94a ], it serves the purpose of demonstrating how our agnostic boosting theorem can be used to get fully polynomial-time learners.”
Rationality and Intelligence (1995, unknown): “It is to be expected that the topic of agnostic learning [Kearns et al., 1992], which analyses the convergence of inductive learning algorithms working in arbitrary environments within a fixed hypothesis language, will be an important adjunct to the theory of bounded optimal agent design.”
Learning Halfspaces with Malicious Noise (2009, background): “Malicious noise. General-purpose tools developed by Kearns and Li [12, 13 ] directly imply that halfspaces can be learned for any distribution over the domain in randomized poly(n,1/� ) time with malicious noise at a rate Ω(�/n ); the algorithm repeatedly picks a random subsample of the training da”
Exponentiated Gradient Versus Gradient Descent for Linear Predictors (1997, methodology): “Obviously, if no assumptions are made concerning the relation between the instances and outcomes, there is not much a prediction algorithm can do. To set a reasonable goal, we measure the performance of the algorithm against the performances of predictors from some fixed comparison class P. (The com”
Clustering with qualitative information (2003, background): “In fact the minimum value of the second expression is 3/4 + �/8 for all �2 [0, 1 ] and is achieved when � = �/2.”
On-line Algorithms in Machine Learning (1996, methodology): “The Mistake Bound model is equivalent to the "extended equivalence query" model of Angluin [1], and is known to be strictly harder for polynomialtime algorithms than the PAC learning model of Valiant [34, 22] in which (among other differences) the adversary is required to select examples from a fixe”
Learning with Annotation Noise (2009, background): “Theorem 1 suggests that annotation noise as defined here is qualitatively different from more malicious types of noise analyzed in the agnostic learning framework (Kearns and Li, 1988; Haussler, 1992; Kearns et al., 1994), where an adversary can not only choose the placement of the hard cases, but a”
Reinforcement Learning with Immediate Rewards and Linear Hypotheses (2003, methodology): “Following [ 23 ], we refer to this as the agnostic case.”
Rationality and Intelligence: A Brief Update (2013, background): “Results from statistical lerning theory, particularly in the agnostic learning and empirical risk minimizat on models (Kearns et al, 1992; Vapnik, 2000), can provide learning methods—such as support vector machines—with the required properties.”
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation (1997, background): “However, in the more realistic unrealizable (or agnostic; Kearns, Schapire, & Sellie, 1994 ) case, the notion of hypothesis stability may simply be too strong to be obeyed by many natural learning algorithms.”