Minimax estimation of linear and quadratic functionals on sparsity classes

Abstract

For the Gaussian sequence model, we obtain non-asymptotic minimax rates of estimation of the linear, quadratic and the L2-norm functionals on classes of sparse vectors and construct optimal estimators that attain these rates. The main object of interest is the class s-sparse vectors for which we also provide completely adaptive estimators (independent of s and of the noise variance) having only logarithmically slower rates than the minimax ones. Furthermore, we obtain the minimax rates on the Lq-balls where 0 < q < 2. This analysis shows that there are, in general, three zones in the rates of convergence that we call the sparse zone, the dense zone and the degenerate zone, while a fourth zone appears for estimation of the quadratic functional. We show that, as opposed to estimation of the vector, the correct logarithmic terms in the optimal rates for the sparse zone scale as log(d/s^2) and not as log(d/s). For the sparse class, the rates of estimation of the linear functional and of the L2-norm have a simple elbow at s = sqrt(d) (boundary between the sparse and the dense zones) and exhibit similar performances, whereas the estimation of the quadratic functional reveals more complex effects and is not possible only on the basis of sparsity described by the sparsity condition on the vector. Finally, we apply our results on estimation of the L2-norm to the problem of testing against sparse alternatives. In particular, we obtain a non-asymptotic analog of the Ingster-Donoho-Jin theory revealing some effects that were not captured by the previous asymptotic analysis.

32 pages

References in corpus (7)

• Higher criticism for detecting sparse heterogeneous mixtures
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Nonquadratic estimators of a quadratic functional
• Goodness-of-fit testing and quadratic functional estimation from indirect observations
• Adaptive estimation of linear functionals in the convolution model and applications
• Minimax estimation of linear functionals over nonconvex parameter spaces
• On adaptive estimation of linear functionals

Cited by in corpus (13)

• Uncertainty Quantification for Sparse Deep Learning
• Dualizing Le Cam's method for functional estimation, with applications to estimating the unseens
• Randomized tests for high-dimensional regression: A more efficient and powerful solution
• Minimax testing and quadratic functional estimation for circular convolution
• Optimal estimation of functionals of high-dimensional mean and covariance matrix
• A Fourier Analytical Approach to Estimation of Smooth Functions in Gaussian Shift Model
• Estimation of the $l_2$-norm and testing in sparse linear regression with unknown variance
• Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions
• Optimal Estimation of Simultaneous Signals Using Absolute Inner Product with Applications to Integrative Genomics
• Adaptive minimax testing in inverse Gaussian sequence space models
• Optimal Estimation of Schatten Norms of a rectangular Matrix
• Minimax rates for sparse signal detection under correlation
• Minimax optimal estimators for general additive functional estimation