Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Boosting in the Presence of Massart Noise   We study the problem of boosting the accuracy of a weak learner in the
(distribution-independent) PAC model with Massart noise. In the Massart noise
model, the label of each example $x$ is independently misclassified with
probability $\eta(x) \leq \eta$, where $\eta<1/2$. The Massart model lies
between the random classification noise model and the agnostic model. Our main
positive result is the first computationally efficient boosting algorithm in
the presence of Massart noise that achieves misclassification error arbitrarily
close to $\eta$. Prior to our work, no non-trivial booster was known in this
setting. Moreover, we show that this error upper bound is best possible for
polynomial-time black-box boosters, under standard cryptographic assumptions.
Our upper and lower bounds characterize the complexity of boosting in the
distribution-independent PAC model with Massart noise. As a simple application
of our positive result, we give the first efficient Massart learner for unions
of high-dimensional rectangles.

25
The categories of this paper are: patt-sol
21
The categories of this paper are: adap-org
5
The categories of this paper are: gr-qc
9
The categories of this paper are: nlin
34
The categories of this paper are: chem-ph
23
The categories of this paper are: solv-int
37
The categories of this paper are: supr-con
11
The categories of this paper are: hep-lat
35
The categories of this paper are: mtrl-th
31
The categories of this paper are: ao-sci
15
The categories of this paper are: nucl-ex
36
The categories of this paper are: cmp-lg
12
The categories of this paper are: nucl-th
22
The categories of this paper are: chao-dyn
4
The categories of this paper are: cond-mat
6
The categories of this paper are: astro-ph