{'fraction_non_alphanumeric': 0.04728617776593577, 'fraction_numerical': 0.016127768286757677, 'mean_word_length': 3.8955727767973607, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
High-dimensional estimation with geometric constraints

Consider measuring an n-dimensional vector x through the inner product with several measurement vectors, a_1, a_2, ..., a_m. It is common in both signal processing and statistics to assume the linear response model y_i =+ e_i, where e_i is a noise term. However, in practice the precise relationship between the signal x and the observations y_i may not follow the linear model, and in some cases it may not even be known. To address this challenge, in this paper we propose a general model where it is only assumed that each observation y_i may depend on a_i only through. We do not assume that the dependence is known. This is a form of the semiparametric single index model, and it includes the linear model as well as many forms of the generalized linear model as special cases. We further assume that the signal x has some structure, and we formulate this as a general assumption that x belongs to some known (but arbitrary) feasible set K. We carefully detail the benefit of using the signal structure to improve estimation. The theory is based on the mean width of K, a geometric parameter which can be used to understand its effective dimension in estimation problems. We determine a simple, efficient two-step procedure for estimating the signal based on this model -- a linear estimation followed by metric projection onto K. We give general conditions under which the estimator is minimax optimal up to a constant. This leads to the intriguing conclusion that in the high noise regime, an unknown non-linearity in the observations does not significantly reduce one's ability to determine the signal, even when the non-linearity may be non-invertible. Our results may be specialized to understand the effect of non-linearities in compressed sensing.


Introduction
An important challenge in the analysis of high-dimensional data is to combine noisy observations-which individually give uncertain information-to give a precise estimate of a signal. One key to this endeavor is to utilize some form of structure of the signal. If this structure comes in a low-dimensional form, and the structure is aptly used, the resulting dimension reduction can find a needle of signal in a haystack of noise. This idea is behind many of the modern results in compressed sensing [19].
To make this more concrete, suppose one is given a series of measurement vectors a i , paired with observations y i . It is common to assume a linear data model y i = a i , x + ε i , relating the response to an unknown signal, or parameter vector, x. However, in many real problems the linear model may not be justifiable, or even plausible-consider binary observations. Such data can be approached with the semiparametric single index model, in which one models the data as for some unknown function f : R → R. The goal is to estimate the signal x despite the unknown non-linearity f . In fact, one may take a significantly more general approach as described in the next section.
It is often the case that some prior information is available on the structure of the signal x. Structure may come in many forms; special cases of interest include manifold structure, sparsity, low-rank matrices and compressible images. We consider a general model, assuming only that x ∈ K for some closed star-shaped 1 set K ⊂ R n .
This includes cones and convex sets containing the origin. We focus on three goals in this paper: 1) determine general conditions under which the signal can be well estimated; 2) give an efficient method of estimation; 3) determine precisely what is gained by utilizing the feasible set K that encodes signal structure. Let us outline the structure of this paper. In the rest of this section, we carefully specify our model, describe the proposed estimator, and analyze its performance for general K; the main result is Theorem 1.3 in Section 1.5. In Section 2, we specialize our results to a number of standard feasible sets K, including sparse vectors and low-rank matrices. In Section 3, we specialize our results to specific versions of the semiparametric single-index model. We include the linear model, the binary regression model, and a model with explicit non-linearity. In Section 4, we discuss the optimality of the estimator. We show that it is minimax optimal up to a constant under fairly general conditions. In Section 5.1 we illustrate the connection between our results and a deep classical estimate from geometric functional analysis, called the low M * estimate. This estimate tightly controls the diameter of a random section of an arbitrary set K. Section 6 gives an overview of the literature on the semiparametric single-index model, emphasizing the differences between the more geometric approach in this paper and the classical approaches used in statistics and econometrics. We give some concluding remarks in Section 7. Sections 8-10 contain the technical proofs. In Section 8 we give the proofs of the results from Section 1, including our main result; in Section 9 we state and prove a version of our main result which holds with high probability rather than in expectation; and in Section 10 we give proofs of the optimality results from Section 4.
Throughout this paper, we use notation common in the compressed sensing literature. However, because we expect our results to be of interest to a wider statistical audience, we provide a dictionary of notation in Section 6, Table 1. 1.1. Model. Let x ∈ R n be a fixed (unknown) signal vector, and let a i ∈ R n be independent random measurement vectors. We assume that observations y i are independent real-valued random variables such that each observation y i may depend on a i only through a i , x . (1.1) In other words, we postulate that, given a i , x , the observation y i and the measurement vector a i are conditionally independent. We are interested in recovering the signal vector x using as few observations as possible. Furthermore, we will usually assume some a priori knowledge about x of the form x ∈ K for some known set K ⊂ R n . Note that the norm of x is sacrificed in this model since it may be absorbed into the dependence of y i on a i , x . Thus, it is of interest to estimate x up to a scaling factor. Unless otherwise specified, we assume that a i are independent standard normal vectors in R n . We lift this assumption in several places in the paper: see the matrix completion problem in Section 2.5, and the lower bounds on all possible estimators in Section 4. We make further suggestions of how this assumption may be generalized in Section 7.
1.2. Linear estimation. The first and simplest approach to estimation is to ignore the feasible set K for a moment. One may then employ the following linear estimator It is not difficult to see that x lin is an unbiased estimator of the properly scaled vector x, and to compute the mean squared error. This is the content of the following proposition whose proof we defer to Section 8. Here µ = E y 1 a 1 ,x , σ 2 = Var(y 1 a 1 ,x ), η 2 = E y 2 1 . (1.2) By rotation invariance of a i , the parameters µ, σ and η depend on the magnitude x 2 but not on the directionx = x/ x 2 of the unknown vector x or on the number of observations m. These properties make it simple to compute or bound these parameters in many important cases, as will be clear from several examples below. For now, it is useful to think of these parameters as constants.
The second part of Proposition 1.1 essentially states that We can express this informally as follows: Linear estimation is accurate for m = O(n) observations. (1.4) 1.3. Projection onto the feasible set. Although estimate (1.3) on the accuracy of linear estimation is sharp, it can be significantly improved if some prior information is available about the vector x. A rigorous way to encode the prior information would be to assume that x ∈ K where K ⊂ R n is some fixed, closed, and known feasible set. Because the scaling of x may be absorbed into the semiparametric single-index model, it is actually more natural to assume that µx ∈ K (1.5) in the notation of Proposition 1.1. 2 Recall that x lin is an unbiased estimator of µx, a vector that lies in K. So to incorporate the feasible set K into estimation, a natural step is to metrically project the linear estimator x lin onto K. In other words, we define (1.6) As we will see shortly, this non-linear estimator outperforms the linear one, often by a big margin.

1.4.
Measuring the size of the feasible set by mean width. The quality of the non-linear estimator (1.6) should depend on the size of the feasible set K. It turns out that there is a simple geometric notion that captures the size of K for this purpose. This notion is the local mean width. At first reading, one may replace it with a slightly simpler concept of global mean width.
where g ∼ N (0, I n ). The local mean width of a subset K ⊂ R n is a function of scale t ≥ 0, and is defined as Note that w t (K) ≤ w(K) trivially holds for all t. The concepts of mean width, both global and local, originate in geometric functional analysis and asymptotic convex geometry, see e.g. [23]. Quantities equivalent to mean width appear also in stochastic processes under the name of γ 2 functional (see [49]), and in statistical learning theory under the name of Gaussian complexity (see [5]).
More recently, the role of mean width (both local and global) was recognized in the area of signal recovery [36,42,40,3,1]. To interpret these developments as well as this paper, it is often helpful to think of the square of the mean width of the properly scaled feasible set K as an essential dimension (as opposed to the algebraic dimension, which typically equals n). A notable benefit of this method of measuring dimension is that it is robust to perturbations: If K is slightly increased, the mean width only changes slightly. 2 Passing between assumptions x ∈ K and µx ∈ K in practice should be painless by rescaling K, as the scaling factor µ is usually easy to estimate. Further, if K is a cone, then there is no difference between the assumptions.

Main result.
Theorem 1.3 (Non-linear estimation). Letx = x/ x 2 . Assume that µx ∈ K where K is a fixed star-shaped closed subset of R n . Then the non-linear estimator x defined in (1.6) satisfies the following for every t > 0: Here µ, σ and η are the numbers defined in (1.2).
In Section 4, we will give general conditions under which the error achieved in this theorem is minimax optimal up to a constant factor-thus the theorem gives a precise, non-asymptotic, characterization of the benefit of using the signal structure K to improve the estimation. In Section 9 we will state a version of Theorem 1.3 whose conclusion is valid with high probability rather than in expectation. In the next two sections we will simplify Theorem 1.3 in special cases, show how it is superior to Proposition 1.1, and illustrate it with a number of examples.

Feasible sets K: consequences and examples
In this section we state a simpler version of Theorem 1.3, compare Theorem 1.3 with Proposition 1.1, and illustrate it with several classes of feasible sets K that may be of interest in applications.
2.1. General sets: error bounds via global mean width. Let us state a simpler conclusion of Theorem 1.3, in terms of global mean width w(K) and without the parameter t.
Let K be an arbitrary compact star-shaped subset of R n . Replacing in (1.7) the local mean width w t (K) by the bigger quantity w(K) and optimizing in t, we obtain While this conclusion is less precise than (1.7), it may be sufficient in some applications. We note the unusual rate O(m −1/4 ) in the right hand side, which nevertheless can be sharp for some signal structures such as the ℓ 1 -ball. See Sections 2.6, 4.3 and also [44].

2.2.
General sets: comparison with linear estimation. Let us compare the qualities of the linear and non-linear estimators. Let K be an arbitrary star-shaped closed subset of R n . The definition of local mean width implies that (Here and below, B n 2 is the n-dimensional Euclidean ball.) Substituting this bound into (1.7) and letting t → 0, we deduce the following estimate from Theorem 1.3: Note that this is the same upper bound as Proposition 1.1 gives for linear estimation, up to an absolute constant factor. We can express this conclusion informally as follows: Projecting the linear estimator x lin onto the feasible set K can only improve the accuracy of estimation. We will shortly see that such improvement is often significant.
2.3. General cones. Let K be a fixed closed cone in R n , so tK = K is satisfied for all t ≥ 0. Then w t (K) = t w 1 (K). Substituting this into (1.7) and letting t → 0, we can state Theorem 1.3 in this case as follows.
To further simplify the bound (2.3), note that term containing w 1 (K) essentially dominates there. This is based on the following observation.
Proof. Note that K −K contains a line, so (K −K)∩B n 2 contains a pair of antipodal points on the unit sphere. Therefore w 1 (K) = w((K − K) ∩ B n 2 ) is bounded below by the first absolute moment of the standard normal distribution, which equals 2/π.
Using Lemma 2.2, we see that (2.3) implies that In particular, we arrive at the following informal conclusion: Linear estimation followed by projection onto the feasible cone K is accurate for m = O(w 1 (K) 2 ) observations. Remark 2.3 (Essential dimension). This result becomes especially transparent if we think of w 1 (K) 2 as the essential dimension of the cone K. A good estimation is then guaranteed for the number of observations proportional to the essential dimension of K. This paradigm manifested itself in a number of recent results in the area of signal recovery [36,42,40,3,1]. Among these we especially note [3] where the results are explicitly stated in terms of a "statistical dimension", a very close relative of w 1 (K).
Remark 2.4 (Projecting onto S n−1 ). Since magnitude information about x is irrecoverable in the semiparametric model, and K has a conic, scale-invariant structure in this subsection, it is natural to rephrase our theorem in terms of the estimation of x, unscaled. One may then normalize x to come to the following conclusion: Indeed, this follows because where the last step follows since x/ x 2 is the closest point in S n−1 to x/µ.
A quick computation similar to (2.2) shows that the essential dimension of a cone is always bounded by its algebraic dimension. Thus the non-linear estimator x outperforms the linear estimator x lin discussed in (1.4), and the improvement is dramatic in cases where w 1 (K) 2 ≪ n. We give examples of such situations below.
2.4. The set of sparse vectors. Sparsity is a key signal structure used in many modern applications. For example, it is common to assume that only a small subset of coefficients are significant in a regression model. As another example, images are generally compressible in some dictionary, i.e., up to a linear transformation an image is sparse. The compressed sensing model (see the book [19]) is based on sparsity, and one may use the results in this paper as a treatment of unknown non-linearities in compressed sensing.
The sparsity model takes K = {x ∈ R n : |supp(x)| ≤ s}, i.e., K is the set of vectors with at most s nonzero entries. Fortunately, projecting onto K is computationally efficient: one only needs to retain the s largest entries of the vector, replacing all other entries by 0. This is referred to as hard thresholding. Thus, the projection estimator is quite amenable to large data.
Further, when s is significantly smaller than n, projecting onto K gives a fruitful dimension reduction. This is evident from the calculation c s log(2n/s) ≤ w 1 (K) ≤ C s log(2n/s) which is given in [42,Lemma 2.3]. Thus, m ∼ s log(2n/s) observations are sufficient to estimate an s-sparse vector in R n .
Sparse in a dictionary. In many applications, the signal may be sparse in a dictionary, rather than canonically sparse, e.g., images are often compressible in a wavelet basis. In this case, the feasible set K ⊆ R q is defined as where the matrix D ∈ R q×n is referred to as a dictionary. A computation of the essential dimension of K can be made through a slight generalization of [42, Lemma 2.3] (via a covering argument), which shows that once again w 1 (K) ≤ C s log(2n/s).
While projection onto K can pose a challenge, we will consider signals which are approximately sparse in a dictionary in Section 2.6; in this case projection can be done efficiently through convex programming.
2.5. The set of low-rank matrices. The low-rank signal structure is prevalent in statistical applications, thus leading to the popularity of principal component analysis; for many examples, see [30]. Reconstructing a low-rank matrix from linear combinations of entries arises in various applications such as quantum state tomography or recommender systems [45,26]. Recently, there has been quite a bit of interest and new theory on the problem of matrix completion: reconstruction of a low-rank matrix from a subset of its entries [11,10], with binary non-linearities given special consideration [18,47]. In this subsection, we first specialize our theory to the low-rank structure and then adjust our theory to the matrix completion model.
Here we take the cone K to be the set of d 1 × d 2 matrices with rank bounded by some small r. Projection onto K requires only taking the singular value decomposition and keeping the largest r singular values and singular vectors. This procedure is referred to as hard thresholding of singular values. The mean width of K is easy to estimate (see e.g. [42]); one has Thus, m ∼ r(d 1 + d 2 ) observations are sufficient to estimate a d 1 × d 2 matrix of rank r.
We now move away from the assumption of Gaussian measurement vectors in order to accommodate the matrix completion model. In this case, one observes a random sample of the entries of the matrix X (linear observations); that is, the measurement "vectors" (matrices) a i are uniformly distributed on the set of matrices with exactly one nonzero entry, and we take y i = a i , X . Projection-based estimators have been considered for matrix completion in [31,32,12]. These papers take general models, which require a somewhat more complicated theory. We consider a simple projection-based estimator and prove that it is quite accurate under a simple model, recovering best-known theory for this model. The proof takes much in common with known matrix completion theory; the purpose of putting it here is to emphasize it's shortness under a simple model. Further, this gives an intuition as to how to extend our results in general to non-Gaussian measurements.
Let us consider the following simple matrix completion model. Take d 1 = d 2 = d and consider a random subset Ω ⊂ {1, . . . , d} × {1, . . . , d}, which includes each entry (i, j) with probability p, independently of all other entries. Let the observations y i give the entries of the matrix X contained in Ω. Further, assume that X satisfies the following incoherence condition: each entry of X is bounded by a parameter ζ.
Let us specify the estimator of X. Define the mask matrix ∆ Ω with 0, 1 entries by Then the linear estimator discussed in Section 1.2, 1 m m i=1 y i a i , is naturally replaced with the Hadamard (entry-wise) product 1 p ∆ Ω •X. Clearly, this is a rough estimator of X, but nevertheless it is an unbiased estimator. Fortunately, the projection step can significantly improve the rough estimator. As above, project 1 p ∆ Ω • X onto the set of rank-r matrices, and call this X.
Under this model, we prove that the estimator is accurate, thereby recovering best-known theory for this model.
Remark 2.6 (The benefit of projection). Despite the non-Gaussian form of the measurements, the estimation error in matrix completion is proportional to w 1 (K)/m = rd/m. Remark 2.7. As is evident from the proof below, if the observations are corrupted with i.i.d. N (0, ν 2 ) noise, the error bound becomes When ν ≥ ζ, this error is known to be minimax optimal up to a constant. The noise is easily incorporated and carried through the proof. At the end it is simply necessary to replace the scaled Rademacher matrix ζ · R by the sum of ζ · R and a noise matrix.
Proof of Proposition 2.5. Note that rank( X − X) ≤ 2r. It follows that The operator norm may be bounded as follows: where the last step follows since X is the closest rank-r matrix to p −1 ∆ Ω • X in operator norm. The right-hand side is the operator norm of a matrix with independent, mean-zero entries and may be controlled directly in many ways. To give an optimal result without log factors, one may use techniques from empirical process theory and random matrix theory. By symmetrization [34, Lemma 6.3] followed by the contraction principle [34,Theorem 4.4], where R is a matrix whose entries are independent Rademacher random variables (i.e. R ij = 1 or −1 with probability 1/2). Thus, R • ∆ Ω has independent, identically distributed entries. Seginer's theorem [46] then gives where C is a numerical constant. For the above inequality to hold, we must have p ≥ log(d)/d, i.e., on average at least log(d) observations per row. Putting all of this together gives Divide through by d and recall m = pd 2 to conclude.
2.6. The set of approximately sparse vectors: ℓ 1 -ball. In real applications, exact sparsity is unusual, and is usually replaced with approximate sparsity. A clean way to do this is to assume that the signal belongs to a scaled ℓ p ball in R n with 0 < p ≤ 1. The ℓ 1 -ball, denoted B n 1 , is an especially useful signal structure due to its convexity, see, e.g., [42].
To see the connection between sparsity and the ℓ 1 -ball, consider an s-sparse vector x, with Euclidean norm bounded by 1. Then, by Cauchy-Schwartz inequality, x 1 ≤ √ s x 2 ≤ √ s and thus x ∈ √ sB n 1 . However, one may take a slight perturbation of x, without significantly changing the ℓ 1 norm, and thus the set accommodates approximately sparse vectors.
For simplicity, we compute the global (as opposed to local) mean width, which is The last inequality comes from the well-known fact E g ∞ ≤ 2 √ 2 log n. Plugging into (2.1) gives Thus, m ∼ s log n observations are sufficient to estimate an approximately s-sparse vector in R n . In Section 4.3 we give a careful treatment of the ℓ 1 -ball using local mean width. We will do a (well known) calculation showing that this improves the above error bound slightly (roughly, log n can be replaced by log(2n/s)). We will find that the true error rate is minimax optimal for many models of the functional dependence of y i on a i , x when m is not too large (m ≤ C √ n). We emphasize the unusual dependence m −1/4 in this non-asymptotic regime.
Approximately sparse in a dictionary. Consider a dictionary D (see Section 2.4). By replacing B n 1 , with DB n 1 , one has a set encoding approximate sparsity in the dictionary D. Fortunately, due to its convexity, projection onto this set may be performed efficiently. Further, it is straightforward to bound the mean width. Indeed, Slepian's inequality [34] gives In other words, if the operator norm of D is bounded, then the set DB n 1 has similar essential dimension-and therefor error bound-as the set B n 1 . Summarizing, we find that m ∼ s log n observations are sufficient to estimate a vector that is s-sparse in a dictionary of n elements.

Observations y i : consequences and examples
We specialize our results to some standard observation models in this section.
3.1. Linear observations. The simplest example of y i are linear observations (3.1) The parameters in (1.2) are then Substituting them into (1.7) and (2.4), we obtain the following result.

Corollary 3.1 (Estimation from linear observations).
Assume that x ∈ K where K is a star-shaped set in R n . Assume the observations y i are given by (3.1). Then for every t > 0, If K is a cone, then Note that here we estimate the signal x itself, rather than its scaled version as in our previous results.

Noisy linear observations. A more general class of examples includes noisy linear observations of the form
where ε i are mean-zero, variance ν 2 , random variables which are independent of each other and of a i . Clearly, such observations follow the single-index model (1.1). A straightforward computation of the parameters in (1.2) shows that Substituting them into (1.7) and (2.4), we obtain the following result.

Corollary 3.2 (Estimation from noisy linear observations).
Assume that x ∈ K where K is a star-shaped subset of R n . Assume that the observations y i are given by (3.2). Then Remark 3.3 (Signal buried in noise). One observes that both the size of the signal, x 2 , and the size of the noise, ν, contribute to the error bound. When the noise is larger than the signal, the estimate may still be quite accurate because of the dimension reduction gained by projecting onto K. In fact, we will show that the error is minimax optimal up to a multiplicative constant under general conditions on K in Section 4. When the signal is larger than the noise, the proposed estimator may not be optimal, depending on K. Indeed, if K = R n , m ≥ n, and ν = 0, the minimax error is 0. However, as a general theme in this paper we concentrate on rough observations for which 0 error is impossible-noiseless linear observations being the exception to this rule.
Remark 3.4 (Generalizing assumptions). We also note that the corollary could be adapted to the case when the random variables ε i expressing the noise are not mean zero, and do depend on x (but only through a i , x ).
Here f : R → R is a fixed link function, which may be unknown. In particular, f may be discontinuous and not one-to-one (like the sign function), or even nonmonotonic in its argument (like the sine function).
The rotation invariance of a i allows us to express the parameters in (1.2) as functions of f and x 2 only. Indeed, where g ∼ N (0, 1). Substituting this into Theorem 1.3 or Theorem 2.1, we can bound the error of estimation in terms of f , the magnitude of signal x 2 , and the local mean width of K; we are leaving this to the interested reader. It is important and surprising that our estimation procedure-computing x from the observations y i -does not depend on the function f . In words, Any knowledge of the non-linearity f defining the observations y i is not needed to estimate x from these observations. The quality of estimation must of course depend on f , and the exact dependence is encoded in the parameters µ, σ and η in (3.5). However, one does not need to know f exactly to compute reasonable bounds for these parameters. In fact, in Section 4.2 we derive uniform error bounds for a fairly large class of functions f .
Here ε i are random variables independent of each other and of a i , and the same is assumed about δ i . (However, ε i may be correlated with δ i .) This is a variation on the generalized linear model, which assumes for some known function f . 3 In contrast, we take the semiparametric approach and assume that the non-linearity, f , is unknown. (On the other hand, GLMs typically assume more general noise models than we do; we discuss the connections between single-index models and GLMs further in Section 6.) To specialize Theorem 1.3 to this case, we need only control µ, σ, and η.
3.5. Binary observations and logistic regression. An important class of examples is formed by binary observations-those satisfying the model (1.1) and such that Denoting g ∼ N (0, 1) (the standard normal variable), we can compute the parameters in (1.2) as follows: (The computation for σ follows by replacing the variance by the second moment.) Substituting this into (2.4), we obtain the following result.
Corollary 3.5 (Estimating from binary observations). Assume that x ∈ K where K is a fixed cone in R n . Assume the observations y i satisfy (1.1) and (3.6). Let Binary observations are important in both signal processing and statistics. We outline the connections between our model and the literature below.
1-bit compressed sensing. The noiseless 1-bit compressed sensing model [6] takes observations These form a particular case for which Corollary 3.5 applies with µ = E |g| = 2/π. This type of observations is motivated as a way of understanding the combination of extreme quantization with low-dimensional, or structured signals. The s-sparse signal set described in Section 2.4 is of key interest. We note that the magnitude of x is completely lost in the observations (even with the non-linearity known), and thus it is standard in this literature to estimate the directionx. We may normalize our estimator to give This recovers the following result from the literature (see [42,29]): m ∼ s log(2n/s) 1-bit observations are sufficient to estimate an s-sparse vector in R n .
Logistic regression. Logistic regression is a common statistical model for binary data, and takes the form where ε i is logit noise. We note that other forms of noise lead to other binary statistical models. For example, if ε i is Gaussian, this recovers the probit model. There is a recent influx of statistical literature on combining sparsity with binary observations, see [4] and references therein. The standard method is ℓ 1 -penalized maximum likelihood estimation. To perform maximum likelihood estimation, it is vital to know the likelihood function-this is equivalent to knowing the form of the noise. However, in practice, given binary observations, it is often unclear which binary model to choose, and one is chosen arbitrarily. In the present paper we emphasize that estimation can be done accurately without precise knowledge of relationship between a i , x and y i .

Optimality
In this section we determine general conditions under which the projection estimator gives an optimal result up to a numerical constant, i.e., there is no estimator which significantly improves on the projection estimator. We begin by considering the the noisy linear model described in (3.2). This will automatically give a lower bound in the case when the observations include a non-linearity. We will come to the following intriguing conclusion.
When the measurements are noisy, an unknown, noninvertible nonlinearity in the measurements often does not significantly decrease one's ability to estimate the signal.

4.1.
Lower bound in the linear model. We begin by considering the linear model with Gaussian noise y i = a i , x + ε i (4.1) where the noise variables ε i ∼ N (0, ν 2 ) are independent of each other and the a i . (The parameter ν is the level of noise.) For compact notation, let y ∈ R m be the vector of observations and A ∈ R m×n be the matrix whose i-th row is a T i . Our goal is to determine conditions on K and the noise which imply that the projection estimator is minimax up to a numerical constant. For simplicity, we refer to numerical constants as C if they are greater than 1, and c if they are less than 1. These constants may change from instance to instance, but each is bounded by an absolute numerical value. We refer to the projection estimator (1.6) as x proj in this section.
The local packing number, which we define as follows, plays a key role in estimation error.
Definition 4.1 (Local packing number, P t ). Given a set K ⊂ R n , the local packing number P t is the packing number 4 of K ∩ tB n 2 with balls of radius t/10. We now give a lower bound on the minimax error in the noisy linear model.
Then there exists an absolute constant c > 0 such that any estimator x which depends only on the observations y i and measurements a i satisfies Let us compare this to the upper bound achieved by the projection estimator, as derived in Corollary 3.2: We now determine conditions under which the two match up to a constant. Observe that the two match most closely when the noise is large. In particular, when ν ≥ x 2 , we have the simplified error bound: Further, since the estimator projects onto K, the upper bound may be tightened: The only difference between lower and upper bounds is that √ log P t is replaced by w t (K)/t. While these quantities may be in general different, for many sets they are comparable. To compare them, let us introduce the following geometric parameter: It follows by definition of α that the lower bound of Theorem 4.2 satisfies The following corollary follows immediately.
Corollary 4.4. Assume that x ∈ K where K is a star-shaped subset of R n . Assume that the observations y i are given by 4.1. Let Then any estimator x satisfies where c α = c/α for the numerical constant c defined in Theorem 4.2 and α defined in (4.3).
Thus, in the high-noise regime, the difference between upper and lower bounds is a factor of (numerical constant times) α. Fortunately, for many sets of interest, α is itself bounded (on both sides) by a numerical constant. In particular, this holds true for sparse vectors, low-rank matrices and the ℓ 1 -ball, as described in Section 4.3. Thus, in this case, the minimax error satisfies and the result of the Corollary still holds.
Remark 4.6 (General measurement vectors). Theorem 4.2 and Corollary 4.4 hold for a general class of random (or deterministic) measurement vectors. The theory only requires that A does not stretch out signals too much in any one direction, that is, Note that for the special case of a Gaussian measurement matrix 1 m E A * A = I n and the above requirement is met; similarly if A contains i.i.d. entries with variance 1, or, more generally, if the rows are in isotropic position. If one wishes to generalize further, a look at the proof implies that we only require Further, the number 1 on the right-hand side could be replaced by any numerical constant without significantly affecting the result.
Remark 4.7 (Signal-to-noise ratio assumption). Our optimality assumption requires x 2 ≤ ν, which places a bound on the norm of the signal. To give a precise minimax accounting of the error, this assumption can be incorporated into Theorem 4.2 by replacing K by K ∩ νB n 2 . In this case, the theorem implies the lower bound Of course, if ν is known then this information can be taken into account in the projection estimator, giving it a mirroring error bound. One may check that the geometric assumption on K need not be adjusted. This follows from a rescaling argument and since K is star-shaped.

4.2.
Optimality in the non-linear model. Now we extend our discussion of optimality to non-linear observations. Let us now assume that the noisy linear data is passed through an unknown non-linearity: Then the non-linear estimator x defined in (1.6) satisfies the following for every t > 0: Here µ, σ and η are the numbers defined in (1.2).
Proof. The unscaled version, Theorem 1.3, gives Now multiply both sides of the inequality by λ, substitute t for λt, and note that w λt (λK) = λw t (K) to complete the rescaling argument.
Comparing to the estimation error from noisy linear observations (3.3), we find that the non-linearity increases the error by at most a constant factor provided Below, we give some general conditions on f which imply this inequality for all signals x and noise levels ν.

Lemma 4.9 (Conditions on the non-linearity). Suppose that f is odd and nondecreasing. Further, suppose that f is sub-multiplicative on
Then, for the model defined in (4.6), the parameters λ = µ −1 x 2 , σ, η defined in (1.2) and the noise level ν satisfy where with g ∼ N (0, 1). In particular, C f does not depend on x 2 or ν.
Below are a few examples of non-linearities f that satisfy the conditions of Lemma 4.9: (1) The identity function, f (x) = x; C f ≈ 2.36.
where all C j are positive (so that C j f j is still monotonic). It is not hard to see that λ, σ, η, and ν satisfy where C f j are defined as in Lemma 4.9. This allows us to obtain uniform error bounds for finite linear combinations of any of the functions satisfying the conditions of Lemma 4.9, such as odd nondecreasing polynomials of degree at most k.
We summarize our findings in the following corollary: Corollary 4.11 (Summary or optimality results). Consider the nonlinear model (4.6), and suppose the nonlinearity takes the form f = k j=1 C j f j , where the functions f j are odd, nondecreasing, and sub-multiplicative. Let C f j be the constants defined in Lemma 4.9. Let the signal set K satisfy α(K) < C 1 , for α defined in (4.5). Suppose the noise level ν is comparable to the signal level x 2 : ν ≥ c 2 x 2 . Define Let x proj be the projection estimator defined in (1.6), and let x opt be the optimal estimator of x. Then there exists an absolute numeric constant c, and constants C(f j ) depending only on f j , such that and

Sets satisfying the Geometric Condition.
In this section we show that for the three commonly used signal sets discussed in Sections 2.4-2.6, the relationship holds for all resolutions t (with t < 1 in the case of the ℓ 1 -ball), for some universal constant C. Thus, α(K) ≤ C for these sets. The condition (4.9) is essentially asserting that Sudakov's minoration inequality (see [34,Theorem 3.18]) is reversible for (K − K) ∩ tB n 2 at scale t/10. Indeed, applying Sudakov's minoration inequality to the Gaussian process X x = g, x , g ∼ N (0, I n ), defined on (K − K) ∩ tB n 2 shows E sup X x = w t (K) ≥ ct √ log P t for some numeric constant c. (Note that the packing number of (K − K) ∩ tB n 2 is at least as great as the packing number of K ∩ tB n 2 .) Sparse vectors. Let S n,s ⊂ R n be the set of s-sparse vectors, i.e., the set of vectors in R n with at most s nonzero entries. Note that S n,s is a cone, so if (4.9) is satisfied for S n,s at some level t, then it is satisfied at all levels. Thus, without loss of generality we take t = 1.
For K = S n,s we have K − K = S n,2s . As shown in Section 2.4, for some constant C. On the other hand, we show that there exists a 1/10-packing for some (possibly different) constant c. Such a packing exists when s > n/4, because then S n,s contains an (n/4)-dimensional unit ball, whose packing number is exponential in n. Thus, we may assume s < n/4. Consider the set Q of vectors x, where each x ∈ Q has exactly s nonzero coordinates, and the nonzero coordinates are equal to exactly s −1/2 . Thus, Q ⊂ S n,s ∩ B 2 , and |Q| = n s . Q itself is not the packing, but we will show that we can pick a large subset X 1 of Q such that any two vectors x, y ∈ X 1 satisfy x − y 2 > 1/10. Consider picking vectors from Q uniformly at random. For two uniformly chosen vectors x, y ∈ Q, we have P x − y 2 2 ≤ 1 100 = P x, y disagree on at most s 100 coordinates .
This requires y to have at least 99 100 s of the same nonzero coordinates as x. Given x, and assuming without loss of generality that 0.01s is an integer (rounding will not make a significant effect in the end), this happens for exactly s 0.99s n − 0.99s 0.01s out of n s values of y ∈ Q. Using Stirling's approximation (and the assumption s < n/4), Now let X 1 ⊆ Q contain c exp(s log 2n s ) uniformly chosen elements of Q. Then with positive probability x − y 2 > 1/10 for all pairs x, y ∈ X 1 . In particular, there exists at least one 1/10-packing X 1 of S n,s ∩ B 2 of size c exp(s log 2n s ).
Low-rank matrices. Let M d 1 ,d 2 ,r be the set of d 1 × d 2 matrices with rank (at most) r; clearly r ≤ min(d 1 , d 2 ). This is again a cone, so it suffices to show that (4.9) is satisfied at a single level t = 1. Now, for K = M d 1 ,d 2 ,r , we have K −K = M d 1 ,d 2 ,2r , so (see [42,Section 3.3] or Section 2.5 of this paper) For the packing number, note that M d 1 ,d 2 ,r contains all matrices whose last d 2 − r rows are identically zero, and also all matrices whose last d 1 − r rows are identically zero. Thus, M d 1 ,d 2 ,r contains a copy of R d 1 r and a copy of R d 2 r . Since the packing number of a unit ball in Euclidean space is exponential in its dimension, we conclude for the packing number of K Approximately sparse signals: ℓ 1 -ball. For the set of approximately sparse signals contained in the ℓ 1 -ball B n 1 , we will show that condition (4.9) is satisfied at all levels t < 1. Note that for K = B n 1 , K − K ⊂ 2B n 1 . We first derive precise bounds on the local mean width of K, . It is easy to see that, for all t, w 2 t (B n 1 ) ≤ C ′ min(t 2 n, log n). The former will apply when t is very small (t ≤ Cn −1/2 ); the latter will apply when t is very large (t ≥ c).

In the intermediate regime Cn
Assume for simplicity that s is an integer; rounding s will not affect the results substantially. Now, by [ Consequently, We now consider packings of B n 1 ∩ tB n 2 by balls of radius t/10. Clearly, for t < n −1/2 , the packing number is at least exponential in n, because the set contains an n-dimensional ball of radius t; and for c < t < 1 the packing number is at least 2n, because we can simply pack the vertices. It remains to treat the intermediate regime n −1/2 < t < c. Note that the problem is equivalent to packing t −1 B n 1 ∩ B n 2 by balls of radius 1/10. Let √ s = t −1 ; assuming s is an integer, we have S n,s ⊂ t −1 B n 1 ∩ B n 2 , so we may apply the packing bounds for sparse vectors: It is not hard to put these bounds together to conclude that indeed, cn, t ≤ Cn −1/2 ; ct −2 log(nt), Cn −1/2 < t < c; ct −2 log n, c ≤ t ≤ 1.

5.
Related results: Low M * estimate, Chatterjee's least squares estimate 5.1. Low M * estimate from geometric functional analysis. The function t → w t (K) t that appears in Theorem 1.3 has been studied in geometric functional analysis. It is known to tightly control the diameter of random sections of K. An upper bound on the diameter is known as the low M * estimate (see [37,38,39,25]) and lower bounds have been established in [21,20,22,24]. The following is a simplified version of the low M * estimate, see [36].
Theorem 5.1 (Low M * estimate). There exists an absolute constant c > 0 such that the following holds. Let K be a star-shaped subset of R n . Let A be an n × m random matrix whose entries are independent N (0, 1) random variables. Assume that t > 0 is such that Then with probability at least 1 − exp(−cm), we have The conclusion (5.1) can be interpreted in a geometric way as follows. All sections of K parallel to the random subspace E = ker(A) have diameter at most t, i.e.
The relevance of the low M * estimate to the estimation problems was first observed in [36]. Suppose one wants to estimate a vector x ∈ K from linear observations as in Section 3.1, i.e. y i = a i , x , i = 1, . . . , m.
Choose an arbitrary vector x 0 ∈ K which is consistent with the observations, i.e. such that a i , x 0 = y i , i = 1, . . . , m. For convex feasible sets K, computing a vector x 0 this way is an algorithmically tractable convex feasibility problem.
To bound the error of this estimate, we can apply the low M * estimate (5.1) for A the m × n matrix with rows a T i . Since x, x 0 ∈ K and x − x 0 ∈ ker(A), it follows that with high probability, x 0 − x 2 ≤ t. To summarize, In particular, if K is a cone then w t (K)/t = w 1 (K), and we can let t → 0. In this case, the low M * estimate guarantees exact recovery once w 1 (K) ≤ c √ m.
To compare (5.2) with the error bound of the non-linear estimation, we can state the conclusion of Theorem 1.3 as follows: The two additional terms in the right hand side can be explained by the fact that the the exact recovery is impossible in the single-index model (1.1), in particular because of the noise and due to the unknown non-linear dependence of y i on a i , x .

5.2.
Chatterjee's least squares under convex constraint. As this paper was being written, [13] proposed a solution to a closely related problem. Suppose that an unknown vector x ∈ R n lies in a known closed convex set K. We observe the noisy vector y = x + g, where g ∈ N (0, I n ). We would like to estimate x from y. This is very similar to the linear estimation problem (3.2), which can be written in the form y = Ax + g. An important difference is that in Chatterjee's model, A is the identity matrix; so one needs to take n observations of an n-dimensional vector x (given as coordinates y i of y). In contrast, the current paper assumes that A is an m × n Gaussian matrix (essentially a projection), so one is allowed to take m observations where usually m ≪ n.
The estimator proposed in [13] is the least-squares estimator, which clearly equals the metric projection of y onto K, that is Note that this coincides with the second step of our estimator. (The first step-a linear estimator-is clearly not needed in Chatterjee's model where A is identity.) The performance of the least-squares estimator is quantified in [13] using a version of the local mean width of K; this highlights one more similarity with the current paper.

Connections to statistics and econometrics
The single-index model we consider is widely used in econometrics; the monograph of [27] gives a good introduction to the subject. In this section, we discuss connections and differences between our method and some of the literature. For this section only, we will use notation more common in statistics literature; Table 1 below summarizes the translation between the two worlds.
x ∈ R n β ∈ R p dimension of parameter space n p number of observations m n We note that much of the work on single-index models considers a broader formulation, namely Our work relies crucially on the additional structural assumption that ε i and X i are conditionally independent given β, X i . The single-index model is similar to generalized linear models (GLMs) in regression analysis, and contains many of the widely used regression models; for example, linear, logistic, or Poisson regressions. Our results apply directly to those models, with the added advantage that we do not need to know in advance which of the models is appropriate for a specific dataset. (Note especially that Corollary 4.11 guarantees uniform error bounds e.g., for most cubic functions f .) In addition, Section 3.5 demonstrates the optimality of our approach for a rather general model of sparse binary-response data, which encompasses the logit or probit models for specific distributions of ε i .
However, we remark that there is no containment between single-index models and GLMs; for example, the negative binomial model is a commonly used GLM which does not fit in the single-index framework. (There is also no reverse containment, as single-index models do not require the distribution of Y i to come from an exponential family.) The literature on single-index and more general semiparametric models is large and growing, so we can only outline some of the connections here. The primary appeal of single-index models to statisticians has been that it allows estimation of β at the parametric rate ( √ n(β n − β) is tight) as well as estimation of f at the same rate as if the one-dimensional input β, X i were observable. Estimation of an unknown function is notoriously difficult when the domain is high-dimensional, so the latter feature is particularly attractive when p is large. We note that much of the analysis of these results is focused on the asymptotic rates of convergence, although some recent papers [28,2,17] also provide nonasymptotic (finite n) guarantees. However, in contexts where the primary concern is with the index β, the classical approaches (such as [48,43,28]) can be unduly restrictive with regards to the link function. This is because they tend to be based on the average derivative method, i.e. the observation that Naturally, methods based on this idea require the link function f to be (at least) differentiable, whereas we can allow f (·) = sign(·). To our knowledge, the only fundamentally different approach to recovery of β alone (without f ) was taken by Li and Duan [35]. The authors considered observations X i with an elliptically symmetric distribution (e.g., correlated normal). They then demonstrated under some mild conditions that any method based on minimization of a convex criterion function (e.g., least squares) would achieve one of its minima at β * ∝ β. Thus, essentially any method for which the minimizer happens to be unique can be used to consistently recover (a multiple of) β; under some additional assumptions, √ n(β n − β) is asymptotically normal. The major advantage of this method is that it does not in any way rely on the smoothness of the link function f . The above discussion applies to low-dimensional settings, in which all that is known about β is β ∈ R n (perhaps with β 2 = 1). Recently, a lot of work has been devoted to the analysis of high-dimensional data (p > n) with additional structural assumptions about β, for example sparsity. In the case of linear link function f , sparse high-dimensional regression is well-studied (see [7] and references therein).
On the other end of the complexity spectrum, the work of Comminges and Dalayan [15] considers a sparse nonparametric model where at most s of the components of the X i are relevant to the model. They ask the question of when the set J of relevant components can be recovered, and find that the necessary number of measurements is n ≥ C 1 exp(C 2 s) log(p/s).
We compare this to our result on recovering a single index β belonging to the cone K of s-sparse vectors, for which (w 1 (K)) 2 ≤ s log(p/s).
We see that going from a single-index to a nonparametric model involves an exponentially larger number of measurements (but the number is exponential in the underlying sparsity, not in the full dimension of the parameter space).
We mention also some of the recent work on the estimation of the link function f in high-dimensional settings. Alquier et al. [2] and Cohen et al. [14] consider the model of a link function f which depends on at most s of the components of x. More generally, Dalayan et al. [17] allow all link functions that can be decomposed as the sum of at most m "nice" functions f V , with each f V depending on at most s coordinates of x. (A special case of all of these models, including ours, is f (x) = f ( x, β ), where β s-sparse andf comes from a nice function class.) The recent work of Dalayan et al. [17] obtain general bounds on the quality of estimation of f , uniformly over classes containing f V .

Discussion
We have analyzed the effectiveness of a simple, projection-based estimator in the semiparametric single index model. We showed that by projecting onto the set encoding the signal structure, rough, unspecified observations could be combined to give an accurate description of the signal. The gain from this dimension reduction was described by a geometric parameter-the mean width. When the noise is large and under mild assumptions on the rest of the model, we showed that the estimator is minimax optimal up to a constant. We came to the surprising conclusion that an unknown, noninvertible non-linearity often does not significantly effect one's ability to estimate the signal, aside from a loss of scaling information and an extra numerical constant in the error bound.
By comparing to what was known in the classic literature on the semiparametric single-index model, we believe our results a) give a simple method of testing whether estimation is possible based on easily computable parameters of the model, b) allow for non-invertible, discontinuous, and unknown linearities and c) give a careful accounting of the benefit of using a low-dimensional signal structure. Nevertheless, our model takes the measurement vectors to be standard normal, and it is important to understand whether this assumption may be generalized, and whether the theory in this paper matches practice. We discuss this challenge in the rest of this section. We pause to note that the lower bounds take a very general model for the measurement vectors, which may even be deterministic, thus it is the model used for the upper bounds which requires generalization.
There is a simple key observation that gives the first step to the theory in this paper: The linear estimator described in Section 1.2 is an unbiased estimate of the signal, up to scaling. It may be surprising at first that this holds regardless of a non-linearity in the observations. This fortunate fact follows from the Gaussianity of the measurements, as described in the next section.
It is straightforward to generalize the theory to the case a i ∼ N (0, Σ), provided Σ is known or can be estimated. One only needs to multiply the linear estimator by Σ −1 to give an unbiased estimator; as long as Σ is well-conditioned, our theory remains essentially unchanged. The next question is the applicability of other random measurement ensembles. We see two avenues towards this research: 1) As we illustrated with the matrix completion example of Section 2.5, if the observations are linear, then the linear estimator can be unbiased for non-Gaussian measurement vectors. All that is needed is for the measurement vectors to be in isotropic position, that is, E a i a * i = I n . This is a common assumption in the compressed sensing literature [9]. Of course, a slight non-linearity can be accounted for by a Taylor series approximation. 2) A central idea in high-dimensional estimation is that non-Gaussian measurement vectors often give similar behavior to Gaussian measurement vectors. For example, this is made explicit with the universality phenomenon in compressed sensing. Such arguments have been applied to a special case of this semiparametric single-index model in [1] focused on binary observations with non-Gaussian measurement vectors. We believe that similar comparison arguments may be applied in the more general setting of this paper.
In conclusion, we emphasize that the assumption of Gaussian measurements has allowed a very clean theory, with relatively few assumptions in a general model, and we hope that it can be a first step towards such theory with other models of the measurement vectors.
The first term in the right hand side equals µx by definition of µ. The second term equals zero since by the independence property (iv) in Lemma 8.1 and and since E b 1 = 0. We proved the first part of the proposition, E x lin = µx.
To prove the second part, we express where Z i = y i a i − µx are independent and identically distributed random vectors with zero mean. Thus Using orthogonal decomposition (8.1) again, we can express Z 1 as follows: Note that E X, Y = 0. (8.4) To see this, X, Y = [y 2 1 a 1 ,x − µy 1 ] · b 1 ,x . The two terms forming this product are independent by properties (iii) and (iv) in Lemma 8.1. Moreover, E b 1 = 0, which yields E b 1 ,x = 0, and as a consequence, (8.4) follows.
Property (8.4) implies that We have E X 2 2 = σ 2 by definition of σ and since x 2 = 1. Next, E Y 2 2 = η 2 E b 1 2 2 by the independence property (iv) in Lemma 8.1 and by definition of η. Recalling that b 1 is a standard normal random variable in the hyperplane x ⊥ , we get E b 1 2 2 = n − 1. It follows that E Z 1 2 2 = σ 2 + η 2 (n − 1).
Putting this into (8.3), we complete the proof. 8.3. Metric projection and dual norm. For a subset T of R n , we define It is a semi-norm if T is symmetric. We define also T d = (T − T ) ∩ dB n 2 . Lemma 8.2. Let K be an arbitrary subset of R n and let z ∈ K, w ∈ R n . Then the distance d := P K (w) − z 2 satisfies the inequality Proof. By definition, P K (w) is the closest vector to w in K, so We write this as (P K (w) − z) + (z − w) 2 2 ≤ z − w 2 2 , expand the left hand side and cancel the terms z − w 2 2 on both sides. This gives The left hand side of (8.6) equals d 2 by definition. To estimate the right hand side, note that vectors P K (w) and z lie in K and they are d apart in Euclidean distance. Therefore P K (w) − z ∈ (K − K) ∩ dB n 2 = K d . Thus the right hand side of (8.6) is bounded by 2 w − z K • d as claimed. Corollary 8.3. Let K be a star-shaped set and let z ∈ K, w ∈ R n . Then for every t > 0 we have Proof. The proof relies on the following fact, which is well known in geometric functional analysis.
Claim. For any fixed x ∈ R n , the function 1 t x K • t is non-increasing in t ∈ R + . To prove this claim, we express the function as Since K is star-shaped, K − K is star-shaped, too. Then the set 1 t (K − K) is non-increasing (with respect to inclusion) in t ∈ R + . Thus the same is true about This and the identity (8.8) prove the claim. To deduce (8.7), denote d = P K (w) − z 2 . If d ≤ t then (8.7) holds. If d > t, we apply Lemma 8.2 followed by the claim above. We obtain

8.4.1.
Decomposition of the error. We apply Corollary 8.3 for w = x lin and z = µx; note that the requirement that z ∈ K is satisfied by assumption. We obtain Recall that x lin = 1 m m i=1 y i a i and use the orthogonal decomposition of a i from (8.1). By triangle inequality, we obtain By definition, K t ⊆ tB n 2 andx ∈ B n 2 , so x K • t ≤ t. Further, ξ i are independent and identically distributed random variables with zero mean. Therefore where the last equality follows by the definition of ξ 1 above and the definition of σ in (1.2).

8.4.3.
Estimating E 2 . We will estimate Recall that y i and b i are independent by property (iv) in Lemma 8.1. Let us condition on y i . Rotation invariance of the normal distribution implies that In order to extend the support of the distribution of h from x ⊥ to R n , we recall the following elementary and well known fact.
Claim. For a subspace E of R n , let g E denote a random vector with distribution N (0, I E ). Let Φ : R n → R be a convex function. Then To prove the claim, consider the orthogonal decomposition F = E ⊕ L for an appropriate subspace L. Then g F = g E + g L in distribution, where g L ∼ N (0, I L ) is independent of g E . Jensen's inequality yields as claimed.
In the notation of the claim, we can estimate the expectation of h K • t (still conditionally on the g i 's) as follows: where the last equality follows by the definitions of the dual norm and local mean width. Therefore, unconditionally we have where the last equality follows from the definition of η in (1.2). It remains to plug estimates (8.11) for E 1 and (8.12) for E 2 into (8.10), and we obtain Finally, substituting this estimate into (8.9) and taking expectation of both sides completes the proof of Theorem 1.3.

9.
High-probability version of Theorem 1.3 Using standard concentration inequalities, we can complement Theorem 1.3 with a similar result that is valid with high probability rather than in expectation.
To this end, we will assume that the observations y i have sub-gaussian distributions. This is usually expressed by requiring that E exp(y 2 i /ψ 2 ) ≤ 2 for some ψ > 0. (9.1) Basic facts about sub-gaussian random variables can be found e.g. in [50].
Theorem 9.1 (Non-linear estimation with high probability). Letx = x/ x 2 . Assume that µx ∈ K where K is a fixed star-shaped closed subset of R n . Assume that observations y i satisfy the sub-gaussian bound (9.1). Let t > 0 and 0 < s ≤ √ m. Then the non-linear estimator x defined in (1.6) satisfies with probability at least 1− 2 exp(−cs 2 η 4 /ψ 4 ). Here µ and η are the numbers defined in (1.2), and c > 0 is an absolute constant.
Proof. The conclusion follows by combining the proof of Theorem 1.3 and standard concentration techniques which can be found in [50]. So we will only outline the argument. Let ε = s/(2 √ m); then ε < 1/2 by assumption.
First we bound E 1 . Since y i are sub-gaussian as in (9.1) and a i ,x is N (0, 1), the random variables ξ i are sub-exponential. More precisely, we have E exp(ξ i /Cψ) ≤ 2, where C > 0 denotes an absolute constant here and thereafter. A Bernstein-type inequality (see [50,Corollary 5.17]) implies that 1 m m i=1 ξ i ≤ εη, and thus E 1 ≤ εηt, (9.2) with probability at least In the last inequality we used that η = E y 2 i ≤ Cψ by definition of ψ and that ε ≤ 1 by assumption.
Turning to E 2 , we need to bound m i=1 y 2 i and g K • t . A similar application of a Bernstein-like inequality for the sub-exponential random variables y 2 i − η 2 shows that Next, we bound g K • t using Gaussian concentration. Since K t ⊆ tB n 2 , the function x → x K • t on R n has Lipschitz norm at most t. Therefore, the Gaussian concentration inequality (see e.g. [33]) implies that with probability at least 1 − exp(−cε 2 m). (9.5) If both m i=1 y 2 i and g K • t are bounded as above, then If also E 1 is bounded as in (9.2), then we conclude as in the proof of Theorem 1.3 that Recalling (9.3), (9.4) and (9.5), we see that this happens with probability at least for an appropriate absolute constant c ′ > 0. (Here we used again that η/ψ < 1 and ε < 1.) The conclusion of Theorem 9.1 follows by definition of ε.
In this section, for a set K ⊂ R n we use the notation K t = K ∩ tB n 2 . (Note that we do not symmetrize K first.) 10.1. Proof of Theorem 4.2. The theorem is proven with a careful application of Fano's inequality, an information theoretic method which is useful for determining minimax estimation rates. We state a version of Fano's inequality synthesized for lower-bounding expected error in the linear model (the steps needed to specialize Fano's inequality can be seen in [44,8], for example). For the general version see [16]. In all that follows, X t is a t/10-packing of K t with maximal cardinality. Thus, |X t | = P t . Then there exists a constant c > 0 such that for any estimator x(A, y), Theorem 4.2 will be proven by conditioning on A and applying Fano's inequality. We begin to control the left-hand side of (10.1) by showing that A does not significantly increase the average distance between points in our packing. Indeed, The last step follows since X t ⊂ tB n 2 . Thus, by Markov's inequality, We pause to note that the above inequality is the only property of A that is needed. By conditioning on the good event that the Inequality (10.2) holds, the following Corollary gives a significant simplification of Theorem 10.1. We are now in position to prove Theorem 4.2.
Proof. Let c 0 be a small numerical constant, whose value will be chosen at the end of the proof, and let δ := c 0 δ * = c 0 inf t t +ν 1 + log P t .
We split the proof into two cases, depending on the relative size of δ andν. Case 1: δ ≥ν.
This case contains the meat of the proof, but nevertheless it can be proven quite quickly with the tools we have gathered. Since δ is the infimum in (10.4), it satisfies δ ≤ c 0 δ +ν 1 + log P δ .
We now check that δ satisfies Inequality (10.3) as required for Fano's inequality. Since δ ≥ν, one has δ 2 ν 2 + 1 ≤ 2 The inequality now follows if we take c 0 such that 2c 2 1 < c. We now move to the second case. Case 2: δ ≤ν. This is an unusual case; it only occurs when K is quite small, e.g., a 1-dimensional subspace. Fano's inequality, which is more applicable for higher dimensional sets, may not give the optimal answer, but we may use much simpler methods. We give a bare-bones argument.
Consider any two signals, w, v ∈ K satisfying w − v 2 ≤ cν. We will show that these two points are indistinguishable based on the noisy observations y. Consider the hypothesis testing problem of determining which of the two points generate y, i.e., either y = Aw + ε or y = Av + ε. As seen from (10.2), with probability at least 3/4 A(v − w) 2 ≤ c √ mν ≤ cν. Thus, the difference between the two candidate signals is much smaller than the noise level. It follows from a quick analysis of the likelihood ratio test, which is optimal by Neyman-Pearson lemma, that the that hypotheses are indistinguishable, i.e., there is no estimator which has a more than 3/4 chance of determining the original signal. This gives the lower bound By taking the maximum distance between signals v, w ∈ K ∩νB n 2 , this gives sup x∈K E x − x 2 ≥ c min(diam(K),ν) ≥ c min(diam(K), δ). where c α = c/α for a numerical constant c and α defined in (4.5).