Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model

DOI10.1214/18-AOS1766MaRDI QIDQ2328061zbMATH OpenFDO

Authors Iosif Pinelis, Aryeh Kontorovich

Publication date 9 October 2019

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.08920, https://projecteuclid.org/euclid.aos/1564797865

zbMATH Keywords

Bayes decision rulesbinomial distributionclassificationempirical estimatorsgeneralization errorminimax decision rulesPAC learning theory

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: 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_{i}nfty/sqrtu$ as $uoinfty$, where $c_{i}nfty=0.16997dots$ is a universal constant, $u=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_{i}nfty/sqrtu$ even for rather small values of the ratio $u=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.

Recommendations

• Strong minimax lower bounds for learning
• Risk bounds for statistical learning
• A general lower bound on the number of examples needed for learning
• Sharper lower bounds on the performance of the empirical risk minimization algorithm

Cites work

• A CONVEXITY PROPERTY OF POSITIVE MATRICES
• A finite sample analysis of the naive Bayes classifier
• A theory of the learnable
• Active nearest-neighbor learning in metric spaces
• Concentration inequalities. A nonasymptotic theory of independence
• Criterion for complete determinacy for concave-convexlike games
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Efficient distribution-free learning of probabilistic concepts
• Fast learning rates in statistical inference through aggregation
• General bounds on the number of examples needed for learning probabilistic concepts
• scientific article; zbMATH DE number 4094511 (Why is no real title available?)
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 3246773 (Why is no real title available?)
• Neural Network Learning
• On general minimax theorems
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Optimal binomial, Poisson, and normal left-tail domination for sums of nonnegative random variables
• Sharper bounds for Gaussian and empirical processes
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• The complexity of learning according to two models of a drifting environment
• Toward efficient agnostic learning
• Understanding machine learning. From theory to algorithms

Cited in

(8)

• Strong minimax lower bounds for learning
• Statistical estimation of ergodic Markov chain kernel over discrete state space
• Best lower bound on the probability of a binomial exceeding its expectation
• Optimal quantum sample complexity of learning algorithms
• A Lower Bound for Agnostically Learning Disjunctions
• A remark about a learning risk lower bound
• Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation
• PACMAN: PAC-style bounds accounting for the mismatch between accuracy and negative log-loss

This page was built for publication: Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328061)