Minimax estimation of linear and quadratic functionals on sparsity classes

Olivier Collier — Université Paris Ouest Nanterre La Défense (Modal’X)
vendredi 20 novembre 2015

(Work done in collaboration with A. Tsybakov)

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 B0(s) of s-sparse vectors θ = (θ1,...,θd), for which we also provide completely adaptive estimators (independent of s and of the noise variance σ) having only logarithmi- cally slower rates than the minimax ones. Furthermore, we obtain the minimax rates on the lq-balls Bq(r) with q in ]0,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 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 class B0(s), the rates of estimation of the linear functional and of the l2-norm have a simple elbow at s = d (boundary between the sparse and the dense zones) and exhibit similar performances, whereas the estimation of the quadratic functional Q(θ) reveals more complex effects and is not possible only on the basis of sparsity described by the condition θ in B0(s).











ESANN 2016 : European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning


ICOR 2016