Abstract
The standard Probably Approximately Correct (PAC) learning model relies on the strong assumption that the target function belongs to a predefined hypothesis class. This seminal 1994 paper by Kearns, Schapire, and Sellie formalizes the "Agnostic Learning" framework, which relaxes this assumption to better model real-world scenarios where the target function may be complex or noisy. We investigate the computational complexity of finding the best-fitting hypothesis within a class, proving that agnostic learning is generally NP-hard even for simple classes like conjunctions. However, we identify specific tractable cases, including piecewise functions learnable via dynamic programming and certain problems involving hidden variables.
Introduction
In the foundational PAC model of machine learning, a learner is typically guaranteed success only if the data-generating process (the "target function") resides within the learner's chosen hypothesis class. In practice, this assumption is often violated: the true relationship may be more complex than the model, or the data may contain significant noise.
Kearns, Schapire, and Sellie introduced the "Agnostic Learning" framework to address these limitations. In this model, the learner makes no assumptions about the target function and instead aims to find a hypothesis from a given class that minimizes disagreement with the observed data. This shifts the objective from finding the "correct" function to finding the "best possible approximation."
The Agnostic Learning Framework
The core challenge of agnostic learning is "disagreement minimization." Given a hypothesis class $\mathcal{H}$ and a set of labeled examples, the goal is to find $h \in \mathcal{H}$ that minimizes the error rate relative to the underlying distribution.
The authors introduce the concept of a touchstone class $\mathcal{T}$. The learner's performance is measured against the best possible function in $\mathcal{T}$. If the target function is actually in $\mathcal{T}$, the model reduces to standard PAC learning. If not, the learner must still perform nearly as well as the best member of $\mathcal{T}$.
Methodology and Theoretical Framework
The paper utilizes several key techniques to explore the boundaries of agnostic learnability:
- Empirical Loss Minimization: The strategy of using a sufficiently large sample to ensure that the hypothesis with the lowest training error also has low true error.
- Reductions from Combinatorial Optimization: To establish hardness results, the authors reduce known NP-hard problems, such as Minimum Set Cover, to the problem of finding optimal hypotheses.
- Dynamic Programming (DP): For piecewise functions—where the domain is divided into intervals, each governed by a simple rule—the authors develop a DP approach to optimize both the partition boundaries and the local hypotheses simultaneously.
- Probabilistic Decision Lists (PDLs): These are used to model scenarios with hidden variables, showing that certain boolean formulas can be efficiently learned even when some data is missing.
Key Findings and Hardness Results
The primary contribution of the paper is the demonstration that agnostic learning is significantly more difficult than standard PAC learning.
The Hardness of Conjunctions
A striking result is that agnostically learning conjunctions is NP-hard. Even if the learner is informed that the target is a simple Disjunctive Normal Form (DNF) formula, finding the single best conjunction to approximate it remains computationally intractable. This suggests that having a perfect description of a complex source does not necessarily simplify the task of finding a "rule of thumb" approximation.
Equivalence to Malicious Noise
The authors prove that agnostic learning is essentially equivalent to learning in the presence of a "malicious adversary" who can corrupt a fraction of the training data. This formalizes the intuition that agnostic learning provides robustness against arbitrary deviations from the model.
Tractable Cases
Despite the general hardness results, the paper identifies specific scenarios where efficient agnostic learning is possible.
Piecewise Functions
The authors show that if a base class (such as constant functions or low-degree polynomials) is easy to minimize, then the class of piecewise versions of those functions is also efficiently learnable. Their dynamic programming algorithm finds the optimal $s$-piecewise partition in polynomial time.
Hidden Variables
The paper addresses the problem of learning $k$-term DNF formulas when some variables are "hidden" (unobserved). They demonstrate that if the hidden and visible variables are independent, these formulas can be represented as PDLs and learned efficiently.
Conclusion
"Toward Efficient Agnostic Learning" provides a rigorous theoretical foundation for understanding the limits of learning without restrictive assumptions. While the general problem of finding the best approximation is often NP-hard, the identification of tractable subclasses like piecewise functions offers a path forward for practical algorithm design. The work highlights a fundamental trade-off: as we move toward more realistic, "agnostic" models of the world, the computational burden of learning increases significantly, necessitating clever algorithmic strategies to find optimal approximations.
Summary updated