Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC)
  Machine Learning Model   We provide an exact non-asymptotic lower bound on the minimax expected excess
risk (EER) in the agnostic probably-ap\-proximately-correct (PAC) machine
learning classification model and identify minimax learning algorithms as
certain maximally symmetric and minimally randomized "voting" procedures. Based
on this result, an exact asymptotic lower bound on the minimax EER is provided.
This bound is of the simple form $c_\infty/\sqrt{\nu}$ as $\nu\to\infty$, where
$c_\infty=0.16997\dots$ is a universal constant, $\nu=m/d$, $m$ is the size of
the training sample, and $d$ is the Vapnik--Chervonenkis dimension of the
hypothesis class. It is shown that the differences between these asymptotic and
non-asymptotic bounds, as well as the differences between these two bounds and
the maximum EER of any learning algorithms that minimize the empirical risk,
are asymptotically negligible, and all these differences are due to ties in the
mentioned "voting" procedures. A few easy to compute non-asymptotic lower
bounds on the minimax EER are also obtained, which are shown to be close to the
exact asymptotic lower bound $c_\infty/\sqrt{\nu}$ even for rather small values
of the ratio $\nu=m/d$. As an application of these results, we substantially
improve existing lower bounds on the tail probability of the excess risk. Among
the tools used are Bayes estimation and apparently new identities and
inequalities for binomial distributions.

4
The categories of this paper are: cond-mat
31
The categories of this paper are: ao-sci
23
The categories of this paper are: solv-int
36
The categories of this paper are: cmp-lg
12
The categories of this paper are: nucl-th
3
The categories of this paper are: physics
25
The categories of this paper are: patt-sol
30
The categories of this paper are: q-alg
10
The categories of this paper are: q-bio
35
The categories of this paper are: mtrl-th
24
The categories of this paper are: dg-ga
37
The categories of this paper are: supr-con
27
The categories of this paper are: comp-gas
19
The categories of this paper are: eess
26
The categories of this paper are: bayes-an
15
The categories of this paper are: nucl-ex