2019/10/10 by Benjamin Guedj, Louis Pujol
Computer Science · Engineering · Mathematics · #Advanced Statistical Methods and Models #Artificial intelligence #Bayes' theorem #Bayesian probability #Computer science #Econometrics #Economics #Fault Detection and Control Systems #Gaussian #Impossibility #Machine Learning and Algorithms #Machine learning #Mathematical economics #Mathematical optimization #Mathematics #Statistical Methods and Inference #Value (mathematics) #Variance (accounting) #Yield (engineering) #cs.LG #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.3390/e23111529
published as Entropy 2021
arxiv created 2019/10/10 · openalex publication_date 2021/11/18 · arxiv updated 2021/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
"No free lunch" results state the impossibility of obtaining meaningful bounds on the error of a learning algorithm without prior assumptions and modelling, which is more or less realistic for a given problem. Some models are "expensive" (strong assumptions, such as sub-Gaussian tails), others are "cheap" (simply finite variance). As it is well known, the more you pay, the more you get: in other words, the most expensive models yield the more interesting bounds. Recent advances in robust statistics have investigated procedures to obtain tight bounds while keeping the cost of assumptions minimal. The present paper explores and exhibits what the limits are for obtaining tight probably approximately correct (PAC)-Bayes bounds in a robust setting for cheap models.