Beyond Sub-Gaussian Measurements: High-Dimensional Structured Estimation with Sub-Exponential Designs
We consider the problem of high-dimensional structured estimation with normregularized estimators, such as Lasso, when the design matrix and noise are drawn from sub-exponential distributions. Existing results only consider sub-Gaussian designs and noise, and both the sample complexity and non-asymptotic estimation error have been shown to depend on the Gaussian width of suitable sets. In contrast, for the sub-exponential setting, we show that the sample complexity and the estimation error will depend on the exponential width of the corresponding sets, and the analysis holds for any norm. Further, using generic chaining, we show that the exponential width for any set will be at most √ log p times the Gaussian width of the set, yielding Gaussian width based results even for the sub-exponential case. Further, for certain popular estimators, viz Lasso and Group Lasso, using a VCdimension based analysis, we show that the sample complexity will in fact be the same order as Gaussian designs. Our general analysis and results are the first in the sub-exponential setting, and are readily applicable to special sub-exponential families such as log-concave and extreme-value distributions.
The author considers the regression problem, where one is given$$ y = X \theta^* + \omega $$for some design matrix $X$ and noise vector $\omega$. The goal is to recover some estimate $\hat{\theta}$ of $\theta^*$ such that $\|\hat{theta} - \theta^*\|_2$ is small with high probability (over the noise vector $\omega$ as well as randomness in the design matrix $X$). The author considers the standard approach of recovering $\hat{\theta}$ as the solution to an optimization problem (a norm-regularized least squares regression).Much attention has been given to this problem in the past when $X$ and $\omega$ have subgaussian entries. In that case, the number of rows $n$ of the design matrix $X$ that is needed relates to the gaussian mean width of the "error set" $A$ defined in lines 108-113 of the paper. In this submission, attention is given to the case when "subgaussian" is replaced with "subexponential". In this case, $n$ relates to the exponential width of $A$. A theorem is given (Theorem 1) stating that exponential width is at most gaussian width times $\sqrt{\log p}$ for any subset T of $\mathbb{R}^p$. This theorem is a simple corollary of two theorems from Talagrand's book after computing the exponential width of the unit $\ell_1$ ball, which is very standard (Theorems 1.2.7 and 2.6.2 in that book; Theorem 5.2.7 is also cited in the submission, but it is irrelevant, it provides the lower bound on the exponential width in terms of the $\gamma$-functionals, but that lower bound is never used in any of the proofs in the submission, and furthermore the lower bound is only true anyway when the r.v.'s *are* exponential and not merely subexponential, unlike this submission).Technically, I found the jump from analyzing the gaussian case in previous work to the subexponential case in this submission to be quite a small jump. The new main theorem, Theorem 1, follows essentially immediately from the two theorems cited in Talagrand's book.In any case, not having a big technical contribution is perfectly OK. More importantly, I think the submission could benefit greatly from more time spent on motivation in the introduction. My perhaps wrong impression is that one can sometimes choose their design matrix, and in those cases they can choose their entries to be subgaussian to get away with few measurements (depending on the gaussian width of the error set). In these cases where a choice is present, it seems there is no motivation to choose to use a design matrix with subexponential entries since the width parameter only gets worse. The question then is: are there strong motivating examples when you cannot choose your design matrix (it is simply given to you by the real world) *AND* it makes sense to model the entries in that design matrix as being subexponential? As far as I can see, the main motivation for this submission hinges upon a positive answer to this question, yet this question does not seem to be addressed adequately in the introduction. (The answer may very well be yes, but I have no idea, and the author should spend considerable time on concrete such examples in the introduction if they exist, since it justifies the importance of the whole paper.)OTHER COMMENTS:FROM THE MAIN PAPER: * line 070: "Note that sub-exponentials are the class of distributions which have heavier tails compared to sub-Gaussians and for which all moments exist.". I don't agree with the word "the" here before "class", since it is one of many. The distribution with pdf e^{-|x|^{1.5}} has heavier tails than sub-gaussians with all moments existing also.* line 071: "Distributions having heavier tails than sub-exponentials start losing moments." This doesn't sound right to me. What about a distribution with pdf e^{-sqrt(|x|)}? The integral of x^p e^{-sqrt(x)} from 0 to infinity converges for any constant p greater than 0 (i.e. all moments exist). * Lines 084 and 085, $A$ is used without yet being defined and is thus somewhat confusing. It is only clear later in line 109 what $A$ was referring to. * I'm confused by line 115 which presents an inequality for $\lambda_n$. $\lambda_n$ is something you set in (2) so that the solution to the optimization problem has some desired property (e.g. it's close to $\theta^*$ in some norm with high probability). Are you saying it should be set to satisfy the given inequality? And are you saying there's a *specific* $\beta$ bigger than 1 for which it should be set this way? I cannot understand what this line means as written (although I guessed the earlier part of this bullet based on line 108). * Lines 199-201, it states (4) holds for any g whose entries have subgaussian decay. This is false. The upper bound of (4) is indeed true as long as there is subgaussian decay, but the lower bound only holds for gaussian decay, not subgaussian. e.g. Rademachers are subgaussian, but gamma_2 is not a lower bound for Rademachers (example: gamma_2 of the ell_1 ball in p dimensions is $\Theta(\sqrt{\log p})$, but the Rademacher width equals $1$). * Lines 210-212 claim that (5) holds for any subexponential r.v.'s. This is again false for the same reason as the last bullet (also see my last comment below from the supplementary file).FROM THE SUPPLEMENTARY FILE: * In line 124, "lose" should be "loose". Also, "For e.g." is redundant; it should just be "e.g." without the "for". * Equation (16) is slightly confusing. The "K" here is an absolute constant and should not be confused with the K from Lemma 1 (it seems the K from Lemma 1 is assumed to equal 1 here). * Below line 215, it states "the result is applicable to any process that has concentration inequality (16)". This is false. The upper bound of (17) is indeed true as long as (16) holds, but the lower bound is only true for the case when the entries of X are exactly exponential (as opposed to subexponential). For example, gaussians are subexponential, but the lower bound is wrong if the entries of X are actually gaussians (the gamma_1 term shouldn't be there). For a more trivial example, the distribution that is supported only on the number "zero" is subexponential, and the lower bound is obviously false for it (although I guess this trivial example doesn't quite work if you assume all variances are 1).