Rate Minimaxity of the Lasso and Dantzig Selector for the lq Loss in lr Balls

Fei Ye; Cun-Hui Zhang

We consider the estimation of regression coefficients in a high-dimensional linear model. For regression coefficients in l_r balls, we provide lower bounds for the minimax l_q risk and minimax quantiles of the l_q loss for all design matrices. Under an l₀ sparsity condition on a target coefficient vector, we sharpen and unify existing oracle inequalities for the Lasso and Dantzig selector. We derive oracle inequalities for target coefficient vectors with many small elements and smaller threshold levels than the universal threshold. These oracle inequalities provide sufficient conditions on the design matrix for the rate minimaxity of the Lasso and Dantzig selector for the l_q risk and loss in l_r balls, 0≤ r≤ 1≤ q≤ ∞. By allowing q=∞, our risk bounds imply the variable selection consistency of threshold Lasso and Dantzig selectors.

Rate Minimaxity of the Lasso and Dantzig Selector for the l_q Loss in l_r Balls

Abstract