Occam's Hammer: a common perspective over randomized estimation and FDR control in multiple testing
The union bound is perhaps the most elementary probabilistic tool
available in learning theory to control estimation error uniformly
over a (discrete) space of models, when an individual bound is known
for each fixed model. It is also used in multiple testing to control
the family-wise error rate (FWER) of a collection of tests. This goes
by the name of "Occam's razor" bound in learning theory and as
Bonferroni's correction for multiple testing. Despite its coarse
nature the appeal of Occam's razor (or Bonferroni's correction) is its
simplicity since any arbitrary initial family of error bounds
(resp. single tests) can be just plugged in.
Recently, new approaches for error control have been put forward in
these two fields: randomized estimation and so-called PAC-Bayes bounds for
learning theory, resp. false discovery rate (FDR) control for multiple
testing. The goal of this talk is to introduce an new elementary
probabilistic lemma, dubbed "Occam's hammer", that can be seen as a
sort of randomized union bound. It allows to cast a common light over
some basic results of both these approaches and to infer some new results.
In the estimation framework, it can be seen as generalization of
Occam's Hammer to possibly continuous families of models and
randomized model selection, also generalizing the PAC-Bayes error bounds.
In the case of (distribution-free) FDR control we can recover the
so-called Benjamini-Yekutieli procedure and extend it to a family of
procedures depending on two prior distributions,
whereby prior knowledge about the typical size of the set
of rejected hypotheses can be used to improve the power.
joint work with F. Fleuret (EPFL, Switzerland).