Adaptive Minimax Regression Estimation over Sparse $ell_q$-Hulls

摘要

Given a dictionary of $M_n$ predictors, in a random designregression setting with $n$ observations, we constructestimators that target the best performance among all the linearcombinations of the predictors under a sparse $ell_q$-norm ($0leq q leq 1$) constraint on the linear coefficients. Besidesidentifying the optimal rates of convergence, our universalaggregation strategies by model mixing achieve the optimal ratessimultaneously over the full range of $0leq q leq 1$ for any$M_n$ and without knowledge of the $ell_q$-norm of the bestlinear coefficients to represent the regression function. Toallow model misspecification, our upper bound results areobtained in a framework of aggregation of estimates. A strikingfeature is that no specific relationship among the predictors isneeded to achieve the upper rates of convergence (hencepermitting basically arbitrary correlations between thepredictors). Therefore, whatever the true regression function(assumed to be uniformly bounded), our estimators automaticallyexploit any sparse representation of the regression function (ifany), to the best extent possible within the$ell_q$-constrained linear combinations for any $0 leq q leq1$. A sparse approximation result in the $ell_q$-hulls turnsout to be crucial to adaptively achieve minimax rate optimalaggregation. It precisely characterizes the number of termsneeded to achieve a prescribed accuracy of approximation to thebest linear combination in an $ell_q$-hull for $0 leq q leq1$. It offers the insight that the minimax rate of$ell_q$-aggregation is basically determined by an effectivemodel size, which is a sparsity index that depends on $q$,$M_n$, $n$, and the $ell_q$-norm bound in an easilyinterpretable way based on a classical model selection theorythat deals with a large number of models. color="gray">