Distribution-Specific Agnostic Boosting

By Vitaly Feldman. 2009

60 citations recorded by the source corpus.

We consider the problem of boosting the accuracy of weak learning algorithms in the agnostic learning framework of Haussler (1992) and Kearns et al. (1992). Known algorithms for this problem (Ben-David et al., 2001; Gavinsky, 2002; Kalai et al., 2008) follow the same strategy as boosting algorithms in the PAC model: the weak learner is executed on the same target function but over different distributions on the domain. We demonstrate boosting algorithms for the agnostic learning framework that only modify the distribution on the labels of the points (or, equivalently, modify the target function). This allows boosting a distribution-specific weak agnostic learner to a strong agnostic learner with respect to the same distribution. When applied to the weak agnostic parity learning algorithm of Goldreich and Levin (1989) our algorithm yields a simple PAC learning algorithm for DNF and an agnostic learning algorithm for decision trees over the uniform distribution using membership queries. These results substantially simplify Jackson's famous DNF learning algorithm (1994) and the recent result of Gopalan et al. (2008). We also strengthen the connection to hard-core set constructions discovered by Klivans and Servedio (1999) by demonstrating that hard-core set constructions that achieve the optimal hard-core set size (given by Holenstein (2005) and Barak et al. (2009)) imply distribution-specific agnostic boosting algorithms. Conversely, our boosting algorithm gives a simple hard-core set construction with an (almost) optimal hard-core set size.

Subfields: Artificial Intelligence

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

Citations in the corpus

Fairness Through Computationally-Bounded Awareness (2018, neutral): “Additionally, distribution-specific learners and learners with query access to the function have been studied [12, 7].”
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].”
Multicalibration: Calibration for the (Computationally-Identifiable) Masses (2018, methodology): “We describe the distribution-specific learner of (Feldman, 2010), where the samples and inner product in the definition are taken over the fixed data distribution D.”