We consider, in the modern setting of high-dimensional statistics, the classic problem of optimizing the objective function in regression using M-estimates when the error distribution is assumed to be known. We propose an algorithm to compute this optimal objective function that takes into account the dimensionality of the problem. Although optimality is achieved under assumptions on the design matrix that will not always be satisfied, our analysis reveals generally interesting families of dimension-dependent objective functions. robust regression | prox function I n this article, we study a classical statistical problem: how to pick optimally (among regression M-estimates) the objective to be minimized in a parametric regression when we know the error distribution. Our study is carried out in the modern setting where the number of predictors is proportional to the number of observations. The classical answer to the problem we posed at the beginning, maximum likelihood, was given by Fisher (1) in the specific case of multinomial models and then at succeeding levels of generality by Cramér (2), Hájek (3), and, above all, Le Cam (4). For instance, for p fixed or p=n → 0 fast enough, least squares is optimal for Gaussian errors, whereas least absolute deviations (LAD) is optimal for double-exponential errors. We shall show that this is no longer true in the regime we consider with the answer depending, in general, on the limit of the ratio p=n as well as the form of the error distribution. Our analysis in this paper is carried out in the setting of Gaussian predictors, although as we explain below, this assumption should be relaxable to a situation in which the distribution of the predictors satisfy certain concentration properties for quadratic forms. We carry out our analysis in a regime that has been essentially unexplored, namely 0 p=n < 1, where p is the number of predictor variables and n is the number of independent observations. Because in most fields of application, situations in which p as well as n are large have become paramount, there has been a huge amount of literature on the case where p=n 0 but the number of "relevant" predictors is small. In this case, the objective function, quadratic (least squares) or otherwise (ℓ 1 for LAD) has been modified to include a penalty (usually ℓ 1 ) on the regression coefficients, which forces sparsity (5). The price paid for this modification is that estimates of individual coefficients are seriously biased and statistical inference, as opposed to prediction, often becomes problematic. In ref. 6, we showed † that this price need not be paid if p=n stays bounded away from 1, even if the regression does not have a sparse representation. We review the main theoretical results from this previous paper in Result 1 below. Some of our key findings were as follows: (i) Surprisingly, when 0 p=n < 1 − e, it is no longer true that LAD is necessarily better than least squares for heavy-tailed errors. This behavior is unlike that in the classical regime p bounded or p=n → 0 fast enough studied, for instance, in ref. 7. (ii) Linear combinations of regression coefficients are unbiased and still asymptotically Gaussian at rate ‡ 1= ffiffiffi n p . This article contains three main parts: Background and Main Results contains needed background and a description of our findings. In Computing the Optimal Objective, we give two examples of interest to statisticians: the case of Gaussian errors and the case of double-exponential errors. We present our derivations in the last section. We consider a problem in which we observe n independent, identically distributed pairs ðX i ; Y i Þ, where X i is a p-dimensional vector of predictors, and Y i is a scalar response. We call the problem highdimensional when the ratio p=n is not close to 0. In effect, we are considering an asymptotic setting where lim inf p=n is not 0. We also limit ourselves to the case in which lim sup p=n < 1. As far as we know, all of the very large body of work developed in robust regression (following ref. 7) is concerned with situations in which p=n tends to 0, as n tends to infinity. Let us briefly recall the details of the robust regression problem. We consider the estimator
For the special case of unregularized M-estimation (σ ¼ 0), the error q s and the form of the optimal loss function were characterized in a recent work REF , using mathematical arguments that are reminiscent of the cavity method in statistical physics.
Optimal M-estimation in high-dimensional regression
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Medicine Mathematics