Toward efficient agnostic learning

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

452 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

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.”
Adversarially Robust Generalization Requires More Data (2018, background): “, see [7, 27, 28]), we are not aware of similar work on test time robustness.”
Robust Estimators in High Dimensions without the Computational Intractability (2016, neutral): “Keywords-unsupervised learning, statistical learning, density estimation robust algorithm I. INTRODUCTION”
Multiaccuracy: Black-Box Post-Processing for Fairness in Classification (2018, background): “Both works [13, 16] connect the task of learning a model that satisfies the notion of fairness to the task of (weak) agnostic learning [9, 14, 15, 17].”
Agnostic Learning of Monomials by Halfspaces Is Hard (2009, methodology): “‡Computer Science Department, Carnegie Mellon University, Pittsburgh, PA. guruswami@cmu.edu.”
Learnability, Stability and Uniform Convergence (2010, background): “It is a direct generalization of agnostic PAC-learnability (Kearns et al., 1992) to Vapnik " s General Setting of Learning as studied by Haussler (1992) and others.”
Distribution-Specific Agnostic Boosting (2009, methodology): “A natural model of learning without the PAC model assumptions on the target function is the agnostic learning model of Haussler [16] and Kearns, Schapire and Sellie [25].”
When optimizing nonlinear objectives is no harder than linear objectives (2018, methodology): “We begin by defining a standard notion of computationally efficient learning called Agnostic learning (Kearns et al., 1992).”
A unifying framework for computational reinforcement learning theory (2009, methodology): “Motivated by the agnostic PAC model [Kearns et al. 1994], a natural way to define the problem is to compare the prediction error of the learner to the prediction error of the best hypothesis in H.”
A General Characterization of the Statistical Query Complexity (2016, background): “The characterization in (Feldman, 2012) was also extended to a more general agnostic learning model (Kearns et al., 1994) and has lead to better understanding of complexity of several learning problems (Feldman et al., 2011; Gupta et al., 2011; Dachman-Soled et al., 2015).”
Theory of Disagreement-Based Active Learning (2014, background): “This type of condition was first introduced by Mammen and Tsybakov [1999] and Tsybakov [2004], and is referred to in the literature variously as Tsybakov noise, Mammen-Tsybakov noise, a margin condition, or as a low noise condition.”
Knows what it knows: a framework for self-aware learning (2008, unknown): “This is sometimes called agnostic learning (Kearns et al. 1994).”