Guedj, B;
Pujol, L;
(2021)
Still no free lunches: the price to pay for tighter PAC-Bayes bounds.
Entropy
, 23
(11)
, Article 1529. 10.3390/e23111529.
Preview |
Text
entropy-23-01529-v2.pdf Download (428kB) | Preview |
Abstract
“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.
Type: | Article |
---|---|
Title: | Still no free lunches: the price to pay for tighter PAC-Bayes bounds |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.3390/e23111529 |
Publisher version: | https://doi.org/10.3390/e23111529 |
Language: | English |
Additional information: | This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
Keywords: | statistical learning theory; PAC-Bayes theory; no free lunch theorems |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
URI: | https://discovery.ucl.ac.uk/id/eprint/10083912 |




Archive Staff Only
![]() |
View Item |