Occam's Hammer: a common perspective over randomized estimation and FDR control in multiple testing

Gilles Blanchard

Fraunhofer FIRST (IDA)


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).
Maintained by: Fei Sha