Adapting to unknown sparsity by controlling the false discovery rate

By Felix Abramovich, Yoav Benjamini, David L. Donoho, Iain M. Johnstone. 2005

515 citations recorded by the source corpus.

We attempt to recover an n-dimensional vector observed in white noise, where n is large and the vector is known to be sparse, but the degree of sparsity is unknown. We consider three different ways of defining sparsity of a vector: using the fraction of nonzero terms; imposing power-law decay bounds on the ordered entries; and controlling the lp norm for p small. We obtain a procedure which is asymptotically minimax for l r loss, simultaneously throughout a range of such sparsity classes. The optimal procedure is a data-adaptive thresholding scheme, driven by control of the False Discovery Rate (FDR). FDR control is a relatively recent innovation in simultaneous testing, ensuring that at most a certain fraction of the rejected null hypotheses will correspond to false rejections. In our treatment, the FDR control parameter qn also plays a determining role in asymptotic minimaxity. If q = lim qn ∈ [0,1/2] and also qn > γ/log(n) we get sharp asymptotic minimaxity, simultaneously, over a wide range of sparse parameter spaces and loss functions. On the other hand, q = lim qn ∈ (1/2,1], forces the risk to exceed the minimax risk by a factor growing with q. To our knowledge, this relation between ideas in simultaneous inference and asymptotic decision theory is new. Our work provides a new perspective on a class of model selection rules which has been introduced recently by several authors. These new rules impose complexity penalization of the form 2 � log( potential model size / actual model size ). We exhibit a close connection with FDR-controlling procedures under stringent control of the false discovery rate.

Subfields: Artificial Intelligence, Biophysics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f5b003540ea1b8de08bc1c8388b6ae30cf7b5ec5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Biophysics

In Statistics and Probability

Citations in the corpus

FDR-CONTROLLING STEPWISE PROCEDURES AND THEIR FALSE NEGATIVES RATES (2004, methodology): “…simple compared to the traditional Familywise Error Rate (FWER) and seems appropriate in many practical situations (Abramovich and Benjamini, 1996; Abramovich et al., 2000; Basford and Tukey, 1997; Drigalenko and Elston, 1997; Efron et al., 2001; Storey and Tibshirani, 2001; Williams et al.,…”
Minimal Penalties for Gaussian Model Selection (2007, result): “Penalties of the same order of magnitude as the one given in (34) have been introduced recently by several authors among which George and Foster [17], Barron, Birgé and Massart [7], Birgé and Massart [11], Efron, Hastie, Johnstone and Tibshirani [15] — see the discussion by Loubes and Massart [28] f”
Minimax estimation of linear functionals over nonconvex parameter spaces (2004, methodology): “with maximum at 0 and f is Lip( 1 ) over [− 1 ,0]}”
On the false discovery rate and an asymptotically optimal rejection curve (2009, methodology): “Crossing point, extended Glivenko–Cantelli theorem, false discovery proportion, false discovery rate, familywise error rate, least favorable configurations, multiple comparisons, multiple test procedure, order statistics, positive regression dependent, step-up-down test, step-up test.”
A Selective Overview of Variable Selection in High Dimensional Feature Space (2009, background): “See also Efron et al. (2001), Abramovich et al. (2006), Donoho and Jin (2006), and Clarke and Hall (2009).”
Asymptotically minimax empirical Bayes estimation of a sparse normal mean vector (2013, methodology): “, Abramovich et al. 2006; Brown and Greenshtein 2009; Castillo and van der Vaart 2012; Donoho and Johnstone 1994; Donoho et al. 1992; Jiang and Zhang 2009). With only a single observation Xi for each θi, accurate estimation is not possible without some structure. Assuming θ is sparse, in the sense t”
Wavelets, Ridgelets, and Curvelets for Poisson Noise Removal (2008, background): “Minimaxity of FDR has also been studied in various settings (see [38], [39] for details).”
SPADES AND MIXTURE MODELS (2009, methodology): “Corollary 3 can be viewed as an analogue for density estimation of the adaptive minimax results for L0 classes obtained in the Gaussian sequence model [1, 23] and in the random design regression model [13].”
Optimal Model Assessment, Selection, and Combination (2006, methodology): “Abramovich et al. (2006) proposed a datadependent λ, determined by controlling the false-discovery rate for testing simultaneously n hypotheses of zero wavelet coefficient. Shen and Ye (2002) proposed data-adaptive selection of λ.”
SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax (2015, methodology): “In a second step, [2] argues that the FDR thresholding estimate is sufficiently close to this penalized MLE so that the estimation properties carry over.”
Optimal rates of convergence for estimating the null density and proportion of nonnull effects in large-scale multiple testing (2010, methodology): “Since the seminal paper by Benjamini and Hochberg (1995) on false discovery rate (FDR) control, research in this area has been very active. See, for example, Efron et al. (2001), Storey (2002), Genovese and Wasserman (2004), van der Laan, Dudoit and Pollard (2004) and Sun and Cai (2007). Properties ”
The Bayes oracle and asymptotic optimality of multiple testing procedures under sparsity (2010, methodology): “[9] and [1] consider a range of sparsity given by p m ∝ m − β , with β 1.”
On optimality of Bayesian testimation in the normal means problem (2007, background): “BY FELIX ABRAMOVICH, VADIM GRINSHTEIN AND MARIANNA PENSKY1 Tel Aviv University, The Open University of Israel and”
Distribution-free Multiple Testing (2016, background): “Although not as directly related, [1] consider the problem of estimating the mean vector (μ1, .”