Consider the problem of estimating a binary vector β ∈ {-1, 1} p from noisy linear measurements in the form of y = Aβ + w.
(1)
Here, A ∈ R n×p is a known sensing matrix and w ∼ N (0, σ 2 p I n ) denotes an unknown noise vector. This is a prototypical model for multi-user detections in MIMO communication systems [1], [2]. It also arises in other applications such as compressed sensing [3], source separation [4], and image processing [5].
H. Hu and Y. M. Lu are with the John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA (e-mails: honghu@g.harvard.edu and yuelu@seas.harvard.edu). This work was supported by the Harvard FAS Dean's Fund for Promising Scholarship, and by the US National Science Foundation under grants CCF-1718698 and CCF-1910410.
Various algorithms have been proposed to solve (1). Examples include sphere decoding [6], zero-forcing [7], approximate message passing [8], Markov chain Monte Carlo methods [9], and semidefinite programming [10]. Among them, a convex-optimization based method, known as the box-relaxation decoder [11]- [13], is popular in practice due to its simplicity and efficiency.
The method consists of merely two steps: (1) solve a box-constrained least squares problem
and ( 2) obtain an estimate of β by taking the sign of x * , i.e., β = sign(x * ).
The performance of this algorithm can be measured by the bit error rate (BER):
where 1 {•} denotes the indicator function. The achievable BER depends on two key parameters:
the noise variance σ 2 p , and the sampling ratio δ p def = n/p.
Under the assumption that the sensing matrix A has i.i.d. normal entries, the authors of [12], [13] analyzed the asymptotic BER achieved by the box-relaxation decoder. They show that, as n, p → ∞ with δ p → δ ∈ ( 1 2 , ∞) and σ 2 p ≡ σ 2 > 0, the BER converges in probability to a deterministic limit, i.e., BER P -→ E(δ, σ 2 ) ∈ 0, 1 2 .
(
This means that for any σ 2 > 0 and δ > 1 2 , the algorithm can asymptotically achieve a weak recovery of β: it is better than random guess, but β always contains a nonzero fraction of errors.
Moreover, one can show that
The expressions in (5), together with (4), suggest that the asymptotic BER can be made arbitrarily small if we increase the number of measurements or reduce the noise variance. This then raises a tantalizing question: is there a regime of (δ p , σ 2 p ) such that the box-relaxation decoder can perfectly recover the target signal? Existing results in [12], [13] cannot answer this question, for two reasons. First, BER p→∞ -→ 0 only guarantees that the number of error bits
is sublinear in p, but it contains no information about the actual distribution of N e , including
whether N e = 0. The second issue is subtle but important. It has to do with the specific order with which the limits are taken in (4) and (5). There, we first send the dimension p → ∞ before letting δ p → ∞ or σ 2 p → 0. In practice, p is large but always finite, and thus the speed with which δ p → ∞ and σ 2 p → 0 [e.g., σ 2 p = O(1/p) vs. σ 2 p = O(1/ log p)] makes all the difference. The goal of this paper is to present a precise asymptotic characterization of the probability distribution of N e . We show that, in certain scaling regimes of (δ p , σ 2 p ), the distribution of N e converges to a Poisson law. Moreover, we derive conditions under which the exact recovery of β is possible and provide an asymptotic formula for P(N e = 0) in the form of a Gumbel distribution.
We make the following assumptions throughout the paper.
(A.1) The elements of A are drawn from the i.i.d. Gaussian distribution:
∼ N (0, 1 p ). (A.2) β = -1 p , where 1 p denotes the all-ones vector.
(A.3) The noise is Gaussian: w ∼ N (0, σ 2 p I n ). (A.4) lim inf p→∞ δ p > 1/2 and lim sup p→∞ δ p / log p < ∞.
(A.5) lim inf p→∞ σ 2 p log 2 p > 0 and lim sup p→∞ σ 2 p < ∞. In (A.2), we assume that each coordinate of true signal is -1 to simplify our derivations.
All the results still hold for arbitrary β, due to the rotational symmetry of A. In (A.4), the requirement that lim inf p→∞ δ p > 1/2 is related to the fundamental limits of convex relaxation for structural signal reconstruction. In [14], it is shown that, if lim sup p→∞ δ p ≤ 1 2 , the box-relaxation decoder cannot successfully recover β even in the noiseless case. In (A.5), we essentially require σ 2 p > c/ log 2 p for some c > 0. This restriction is due to the limitations of our current proof techniques. We expect that many of our results still hold without this restriction.
To state our main results, we first need to introduce the following potential function:
where Φ is the CDF of the standard normal distribution. One can verify that F p is a strictly convex function of τ ∈ (0, ∞). (See Appendix B for details.) Thus, one can uniquely define
Another quantity that will be crucial in our analysis is
where d TV is the total variation (TV) distance and P(λ) denotes a Poisson distribution with parameter λ.
The theorem, whose proof can be found in Section II-D, characterizes the asymptotic distribution of N e under certain scaling regimes of (δ p , σ 2 p ). It shows that the law of N e converges to that of a Poisson random variable with parameter λ p , if λ p grows no faster than √ log p. This requirement on λ p is not satisfied in the setting studied in [12] where both δ p and σ 2 p are kept as fixed constants and consequently λ p = O(p). In that case, one can expect that √ p[ Ne p -Φ(-1 τp )] converges to a Gaussian distribution. The fact that N e can have a limiting Poisson law is not surprising. Recall from its definition in (6) that N e is a sum of p Bernoulli random variables {1 { β i =β i } }. Moreover, one can show that
τp ) and that these Bernoulli random variables are close to being independent. Consequently, the law of N e is approximately a Binomial distribution B(p, Φ(-1 τp )) with an expected value equal to λ p . As p → ∞ with λ p = O( √ log p), it is well-known that the Binomial distribution converges to a Poisson distribution (i.e., the "law of small numbers"). The technical contribution of this paper is to make the above arguments precise and rigorous. The main tool we use is the leave-one-out approach (see, e.g., [15]), also known as the cavity method in statistical physics [16], [17]. It allows us to carry out a detailed probabilistic analysis of the random optimization problem in (2).
In our proof of Theorem 1, we did not attempt to optimize the rate of convergence shown on the right-hand side of (10). The actual rate is likely to be faster. In Figure 1, we compare the empirical distribution of N e , obtained after averaging over 10 4 independent trials, against the limiting Poisson distribution for three different problem dimensions. We can see that, even at a moderate dimension of p = 200, the Poisson approximation is already accurate.
The characterization given in Theorem 1 allows us to study the conditions under which the box-relaxation decoder can perfectly recover the target signal. Let P correct def = P(N e = 0) denotes the probability of perfect recovery. We can show that a phase transition of P correct emerges when the following quantity
is near 1.
If α * = 1, a more refined characterization is available. Specifically, assume that
for some constant x ∈ R (and thus α p (x) p→∞ -→ 1), then
where the right-hand side is the CDF of the Gumbel distribution.
The above proposition, proved in Section II-E, characterizes the scaling regimes of (δ p , σ 2 p ) over which perfect recovery is achievable. The possible scalings are also flexible. For example, if we keep the sampling ratio δ p at a fixed value δ > 1/2, it then follows from (11) and ( 12) that σ 2 p = δ-1/2 2 log p is the critical noise variance threshold for perfect recovery to happen. Alternatively, if we fix the noise variance σ 2 p ≡ σ 2 , then the critical threshold for the sampling ratio is δ p = 1/2 + 2σ 2 log p.
To illustrate Proposition 1, we show some results from numerical experiments. In Figure 2a, we plot the phase diagram of the empirical values of P correct under different choices of (δ p , σ 2 p ), as well as the theoretical phase transition boundary separating the regimes of perfect/nonperfect recovery. In Figure 2b, we plot P correct as a function of α p (by fixing δ p = 1 and varying σ 2 p ). A transition indeed takes place near α p = 1, and the transition becomes sharper as we increase the problem dimension p. When p is not very large, a more accurate approximation of P correct is given by the Gumbel distribution. This is illustrated in Figure 2c, where we zoom in the region near the phase transition and compare the empirical success probability against the theoretical prediction given in (14).
The precise analysis of high-dimensional signal estimation has already been the subject of a vast literature. Underpinning these rich results are several powerful techniques developed over the years, including the nonrigorous replica method from statistical physics [18]- [20], approximate message passing (AMP) [21]- [23], the cavity method [16], [17] and leave-one-out analysis [15],
Gaussian min-max theorem (GMT) [24], [25], as well as the geometric framework based on
Gaussian width [14] and statistical dimensions [26].
The box-constrained least square problem in (2) has been previously analyzed in [12], [13] using GMT techniques. Analysis of similar problems can also be carried out by AMP [8].
However, these existing studies consider the setting where both the sampling ratio δ p and the noise variance σ 2 p are kept as constants as p → ∞. Under such scalings, one can establish that the empirical measure of x * , defined as µ(x * ) def = 1 p p i=1 δ x * i , converges to some deterministic limiting measure. However, the convergence of the empirical measure is insufficient for our purpose: flipping the signs of o(p) entries of x * will completely change the number of error bits N e , but it has no effect on the limiting empirical measure. In view of this, we choose to use the leave-one-out approach, which allows us to construct a surrogate of x * , denoted by x, in our analysis. We show that x *x ∞ → 0 but the statistical properties of x are much easier to obtain. We will elaborate on this point in Sec. II.
Our work considers settings where (δ p , σ 2 p ) can scale with the problem dimension p. Similar settings with flexible scalings have been explored in other contexts, including, e.g., sparse linear regression [27]- [29], spiked matrix estimation [30], and low-rank matrix recovery [31]. These studies established the precise conditions under which perfect recovery in these problems is achievable. In our work, we go one step further by establishing the asymptotic distribution of the number of error bits N e .
This section provides a general roadmap to our proof of Theorem 1, which is given in Section II-D. To emphasize readability, we only highlight the main ideas and key intermediate results here, leaving heavier technical details to the subsequent sections and to the appendix.
To analyze N e , we need to understand the statistical properties of x * , i.e., the optimal solution of (2). A basic challenge lies in the fact x * is a high-dimensional vector with no closed-form expressions. The key idea behind the cavity approach [16], [17] or the leave-one-out analysis [15] is to circumvent this issue by focusing instead on a single coordinate of x * . Specifically, to study the ith coordinate x i , we can first rewrite the original problem (2) as arg min
=arg min
where x \i is the vector formed by removing x i (and β \i is defined in the same way), a i is the ith column of A, A \i denotes the matrix formed by removing a i from A, y \i = A \i β \i + w, and
In reaching (16), we have also used Sion's minimax theorem [32] to swap the inner minimization and maximization in (15).
Let u * \i = arg min u L i (u) and define a function
We can then check that the optimization problem ( 16) has the same solution as arg min
Thus, starting from the original problem (2) and after optimizing over all the "nuisance" variables
x \i , we have reached in (19), an equivalent scalar optimization problem over x i .
To nonspecialists, the reformulations leading to ( 19) might look slightly mysterious, but there are several good reasons for doing so. First, note that ( 19) is obtained by subtracting -L i (u * \i ) from ( 16). This manipulation does not change the minimizer of ( 16), but it sets the magnitude of (19) to be O(1), which facilitates our later analysis. Second, we explicitly pull out a ⊺ i u * \i in (19), since its distribution is much easier to characterize than a ⊺ i u * in ( 16), due to the independence between a i and u * \i . This is in fact a major benefit of the leave-one-out analysis. Third, as we will show next g p,i (x iβ i ), which is a random one-dimensional function g p,i (v) evaluated at v = x iβ i , has a particularly simple limiting form as p → ∞.
The following proposition, whose proof is given in Section III-A, shows that g i (v) uniformly converges to a simple quadratic function.
Proposition 2: Under (A.1)-(A.5), there exists c > 0 such that for any i ∈ [p] and ε > 0,
where
Moreover, for γ > 2 and all large enough p, |A p -A * p | < cp -1/(2γ) , where
and f p and τ p are the quantities defined in (8).
There is a simple intuitive explanation for why g p,i (v) is approximately a quadratic function.
Recall that u * \i is the minimizer of L i (u). Thus, in a local neighborhood near u * \i , we can approximate L i (u) by a second-order Taylor expansion:
, where δ = uu * \i and H i corresponds to the Hessian of L i (u) at u * \i . Substituting this approximation into (18), we can immediately obtain that g p,i (v) ≈
and it is independent of H i due to the leave-one-out construction, we can expect a ⊺ i H -1 i a i to concentrate near a constant as p → ∞. Of course, the above explanation is not rigorous in that L i (u) is not smooth and H i may not exist. This is one technical challenge we address in the proof. Since 1 2 A * p v 2 is a good approximation of g p,i (v), we can now approximate the optimization problem in (19) by
where Prox [-1,1] denotes the proximal operator of the indicator function on [-1, 1]. Its solution, denoted by x i , provides a good surrogate of x * i , as shown in the following proposition. Proposition 3: Under (A.1)-(A.5), for any γ > 2, there exists c > 0, such that, for any i ∈ [p] and ε ∈ (0, 1),
We prove this result in Section III-B. Here, we demonstrate the accuracy of the approximations stated in ( 20) and ( 24) via numerical results shown in Figure 3.
Thanks to the independence between a i and u * \i , the surrogate solution x i is much easier to analyze than x * i . Accordingly, we can consider the following approximations of β and N e :
Applying a union bound to (24) gives us max i |x * ix i | P -→ 0, i.e., the surrogate vector x is close to x * in ℓ ∞ distance. This then allows us to show that P( β = β) → 0, which also implies
Theory Empirical
and accordingly,
The proof of Proposition 4 can be found in Section III-C. It shows that the distribution of N e is well captured by that of N e . Therefore, to obtain the limiting distribution of N e , we just need to analyze N e , which is what we are going to do next.
To derive the distribution of N e , we need to know the joint distribution of
are correlated, but the correlations are weak. In fact, we can prove something stronger.
The following result, proved in Section IV-A, shows that any size-k subset of {a ⊺ i u * \i } i∈[p] are approximately independent, provided that k is not too large.
where Φ(•) is the CDF of the standard Gaussian and ∆ p,k
It follows from ( 23) and ( 25) that
(Recall that we have assumed that β i = -1 for all i.) By taking b i = -A * p in (28), we can conclude that the k events
) are also approximately independent. This is made precise by the following proposition, whose proof can be found in Appendix E.
, there exists c > 0, such that
Moreover, if σ 2 p ≥ c ′ log 2 p for some c ′ > 0, then for all large enough p,
We are now ready to prove Theorem 1 by showing that the limiting distribution of N e converges to Poisson. Recall that N e = p i=1 1 β i =β i . The approximate independence of {1 β i =β i } makes the analysis tractable. Classical results on Poisson approximation of rare events deal with the sum of p i.i.d. Bernoulli random variables with success probability λ/p. As p → ∞, the sum converges in distribution to a Poisson random variable with rate λ. Things are slightly different in our case, since N e is a summation of p weakly correlated Bernoulli random variables. The following proposition, proved in Section IV-B, shows that the Poisson convergence still holds under the weaker condition of approximate independence.
where P(λ) denotes a Poisson distribution with parameter λ.
Finally, since the TV distance is a metric, the statement of Theorem 1 immediately follows from ( 27), (31) and the triangle inequality.
Using the Gaussian tail bounds (133) and (134) given in Appendix F, we can get
Therefore, if α * > 1, it directly follows from Theorem 1 that P(N e = 0) = 1.
The case that α * < 1 is more complicated. One can show that λ p ≥ p c(α * ) , where c(α * ) is some constant, so it is possible lim p→∞ d TV ( N e , N e ) → 0. Instead, we can look at a subset
Define N e,K as the number of error bits in K. and λ p,K def = |K|Φ(-τ -1 p ). We can find K satisfying λ p,K ≍ √ log p. Then following same steps of proving Proposition 4 and Proposition 10 in Appendix G, we can show lim p→∞ P(N e,K = 0) = 0, which indicates that
Finally, we prove (14). If α p satisfies (13), then for large p, σ 9) and (10) gives us
where step (a) follows from m(-τ -1 p ) τp → 1, step (b) follows from 2α p τ 2 p log p → 1 and we use (13) in step (c).
The goal of this technical section is to make the approximations shown in Figure 3 rigorous.
To lighten notation, we will sometimes omit the leave-one-out subscript as used in Sec. II-A.
For example, A \i will be replaced by A, and a i by a, as long as doing so causes no confusion.
Let us first introduce the following function:
where
Using G p (s) and omitting subscript i, scalar function g p,i (v) defined in (18) can be also expressed as:
and correspondingly, we re-write (19) as:
It can be seen that G p (s) is related with the conjugate function of L(u), which is a strongly convex function. Therefore, G p (s) and g p (v) possess some nice properties that will be useful in our proof. We gather them together in Appendix A.
We first show that g p (v) concentrates around its expectation, which is the following proposition.
Proposition 8: There exists c > 0, s.t. for any ε > 0,
The next result shows that Eg p (v) is essentially a quadratic function in the large p limit.
where A p is defined in (21).
Proof: First we introduce the following auxiliary functions:
where a ∼ N (0, I n ), independent of A, w. Clearly, the original problem (2) is the special case when θ = 0. For notational convenience, we also define the expectation of Q p (θ) as:
where L(u) is given in (33). Note that the connection between Q p (θ) and Eg p (v) is:
i.e., Eg p (v) can be approximated by the derivative of Q p (θ) at θ = 0. To make this intuition rigorous, we need to study the analytical properties of Q p (θ).
First, we show that Q p (θ) is differentiable on [0, ∞) and Q ′ p (θ) is Lipschitz continuous. Indeed, from (33) and (38),
where w ∼ N (0, I n ) and ûθ corresponds to the optimal solution of (40). In step (a), we use dominated convergence theorem (DCT) to interchange derivative and expectation. By the same argument of (77) in Appendix A, we have for any b, c ≥ 0,
On the other hand, for any θ ≥ 0,
Combining ( 41), ( 42) and ( 43), for any b > c ≥ 0, we can get
Therefore,
Now we are ready to analyze Eg p (v). By the mean value theorem, we get from (39) that
where κ p ∈ [0, 1]. From (44) and (45), we deduce that
On the other hand, from (41),
It can be checked from (15) that u * = Ax *y. Combining (46) and (47), we get (36).
Remark 3: It will be shown later [c.f. (59)] that A p ≥ Cδ p , for some constant C > 0.
Therefore, we know from (36) that the quadratic approximation of Eg p (v) is accurate for large p, if σ p ≫ p -1/2 . We will prove that, when σ p < c √ log p for some constant c, perfect recovery is achieved with high probability. This means that σ p ≫ p -1/2 already covers the regime where we are most interested in. In the following, we will take σ p ≥ 1 log p . Proposition 8 and 9 immediately implies the first part of Proposition 2, i.e., (20). Next we show A p converges to A * p in the high-dimensional limit. From (47),
Hence, it boils down to analyzing Q ′ p (θ) and its limit, which can be done as follows. 1) Convergence of Q p (θ): The CGMT framework in [13], [33] can be readily applied to computing the limit of Q p (θ) in high dimensions.
Lemma 1: There exists c > 0, s.t., for any ε > 0 and θ ∈ [0, 1],
where
with F p defined in (7). Also for any γ > 2, there exists c > 0 such that
Remark 4: The proof of Lemma 1 will be given in Appendix D. We can find
, where f p is defined in (8). This can be understood from (37) and (49), since Q * p (θ) is the limiting value of the squared fitting error when the noise variance is θ + σ
and
Then together with bound (84) shown in Appendix B, we know there exists C > 0, s.t., Q * p ′′ (θ) ≤
C, for all θ ≥ 0.
3) Convergence of A p to A * p : Now we can show the convergence of the curvature A p , which also implies the simple limiting form of g p (v).
Lemma 3: There exists c > 0 such that
Proof: For γ > 2, there exists C > 0, s.t. for θ ∈ (0, 1],
where in step (a), we use ( 22), ( 48) and ( 52) and in step (b), we use (44), (51) and Lemma 2.
Therefore, taking θ = p -1 2γ and using Assumptions (A.4) and (A.5), we can get (54).
Proposition 2 indicates that the original scalar problem (34) can be well approximated by
which has an explicit optimal solution:
Note that the difference between x and x should be small, as implied by ( 23), ( 57) and (54). In fact, we can directly prove x → x * without considering x. The reason for us to introduce this intermediate variable is to achieve a better convergence rate in our proof.
The first lemma below shows that the objective function of (56), i.e.,
is strongly convex.
Lemma 4: There exists K > 0, s.t., A p ≥ Kδ p for all p large enough. Therefore, ℓ p (x) is Kδ p -strongly convex.
Proof: By (8) and the definition of A * p , we have
Then from assumption (A.5) and (54), we know there exists K > 0 s.t. A p ≥ Kδ p > 0 and ℓ p (x) is Kδ p -strongly convex.
Then together with uniform convergence proved in Proposition 2, we can show x * → x.
Lemma 5: There exists c > 0 s.t., for ε ∈ (0, 1),
Proof: Since ℓ p (x) is Kδ p -strongly convex,
Let ℓ p (x) be the objective function in (19). From (20) we know there exists c > 0, s.t., for
From ( 61) and (62), we can get there exists c > 0 s.t. for all ε ∈ (0, 1),
. Then changing √ ε to ε in the above, we get (60).
Furthermore, using (54) we can also show x → x.
Lemma 6: For γ > 2, there exists c > 0, s.t., for ε ∈ (0, 1),
Proof: By the non-expansiveness of proximal operator Prox [-1,1] (•), from ( 23) and (57) we know there exists C > 0, s.t.,
where we have used (54) and (59). Recall that u * = Ax *y, so similar to (104) and (105), we obtain that there exists c > 0, s.t., for all ε > 0, P
. Since a and u * are independent, then from (63) it is not hard to show there exists c > 0, s.t., for all ε ∈ (0, 1), P (|x -x| > ε) ≤ c ε e -p 1/γ ε 2 /c . Lemma 5 and 6 imply Proposition 3, based on which we can now prove Proposition 4.
Our strategy is to show that P( β = β) is small, which implies P( N e = N e ) is small and so is d TV ( N e , N e ). Recall that N e and N e are in the same probability space, and we have assumed
Then the following simple relation holds: 5 ) and A * p (-1p -1 5 ), k = 1 and ε = p -1 5 in (28), we can show
By union bound,
Since d TV ( N e , N e ) ≤ P( N e = N e ) ≤ P( β = β), we obtain (27).
This is another technical section. Our main goal here is to derive the asymptotic distribution of { x i } and that of N e .
By the exchangeability of a ⊺ i u * \i i∈[p] , we just need to consider the joint distribution of a ⊺ i u * \i i∈[k] , i.e., the first k coordinates. A key result we are going to establish is that
are approximately independent, provided that k is not too large.
Let u * \[k] be the optimal solution of
where A \[k] is the matrix formed by removing the first k columns of A and β \[k] is defined in the same way. In other words, u * \[k] is the leave-k-out solution of min u L(u). Also define
Our proof of approximate independence of
. This is proved in Lemma 9.
, which are mutually independent. This is proved in Lemma 12.
Details of the proof can be found in Appendix E.
Before presenting the actual proof, it would help to first show some heuristic derivations.
We employ the following general inclusion-exclusion principle [34, p.106]: for any k ∈ [p], the probability P k that exactly k among p events A 1 , . . . , A p occur is
where
where λ p is defined in (9). Then combining (69) and (71), we have
which implies that the PMF of N e is approximately Poisson with rate λ p .
We now quantitatively analyze the error of approximation in (72). First, we approximate the right-hand side of (69) by a truncated sum: L m=k m k (-1) m-k S m , with L ≤ p. The reason for this operation is that S [m] ≈ Φ m -1 τp may not be accurate for large m, since we only have approximate finite event independence. We then need to control the error caused by the truncation. Accordingly, we can apply Bonferroni's inequality [34, p.110], stated as follows.
Under the same setting as (69), for k + 1 ≤ L ≤ p, we have
Therefore, we need to choose a reasonably large L to attain a good trade-off between the approximation error of (71) and the truncation error of ( 73) and ( 74), such that they are both properly bounded. Our proof of Proposition 7 follows this idea. The details can be found in Appendix H.
1) G p (s) is convex and differentiable in R n , with
where
or equivalently,
3) g p (v) is convex and differentiable with
we get (75) and (76).
Since g p (v) = G p (av), g p (v) is also convex and differentiable with g ′ p (v) = a ⊺ ∇G p (av). From (75) and (76), we know ∇G p (av) ≤ a v. Therefore, (78) follows from Cauchy-Schwartz inequality and the fact that |v| ≤ 2. (8) In this section, we collect some useful properties of the one-dimensional optimization (8), which was first studied in [13]. For our purpose, we consider a slightly more general setting:
where t > 0 is a parameter. Note that (8) and the inline optimization of (50) are the cases where t = σ 2 p and t = (1 + θ) 2 σ 2 p , respectively. Also we define the squared loss function: R p (t)
and evidently,
1) Uniqueness of Optimal Solution: Let τ (t) be the minimizer of (79), which is the solution of stationary equation:
By direct differentiation of h(τ ) above, we can show h
so it is a strictly increasing function. Also lim τ →0 h(τ ) = -∞ and lim τ →∞ h(τ ) = δ p > 0. This also establishes that the strict convexity of f p (t). Therefore, τ (t) is unique for any t > 0. Besides, we can directly check that τ (t) is differentiable with
so τ (t) is strictly increasing.
2) Upper and Lower Bounds of τ (t): Since h
and evidently, v p < 1/2. Therefore, τ (t) can be bounded as:
3) Properties of f p (t): From (79) we get f p (t) ≥ 0, f ′ p (t) = 1 2τ (t) > 0 and f ′′ p (t) = -τ ′ (t) 2τ 2 (t) < 0, so f p (t) is nonnegative, strictly increasing and concave. On the other hand, letting τ = t δp in (79) we can get f p (t) ≤ C √ tδp 2
+ 1 , where C is some constant.
Therefore, R p (t) is strictly increasing and convex. From (80), we can show R ′ p (t) is bounded:
On the other hand, R ′′ p (t) satisfies: R ′′ p (t) ≤ ϕ(-2/τ (t)) 2τ (t)t , where ϕ(x) is the PDF of standard Gaussian. Then using (82) and Assumption (A.4), we know there exists C > 0, s.t., for t > 0,
We first prove the pointwise convergence of g p (v) to Eg p (v): there exists c > 0, s.t., for any v ∈ [0, 2] and ε > 0,
Recall that g p (v) = G p (av), so it is equivalent to prove |G p (av) -EG p (av)| → 0. We first control the moment generating function of G p (av) -EG p (av). Let b be an i.i.d. copy of a. For all |λ| ≤ p 2 √ 2π , we can apply Theorem 2.2 of [36, p.176] to get
In step (a), we take expectation over b and use |v| ≤ 2 and ∇G p (av) ≤ 2 a , as implied by (76); In step (b), we use the inequality log(1 + x) ≥ x 1+x , for x > -1 and the condition that |λ| ≤ p 2 √ 2π . As a result, for any ε ≥ 0 and λ ∈ 0, p
After minimizing the exponent on the RHS of (86
2π . The other direction also holds by the same reasoning. Thus,
To show uniform convergence (35), it suffices to prove the Lipschitz continuity of g p (v) and Eg p (v). From Lemma 1 of [37], we have for all x > 0, P a
Let x = n( √ y + 1 -1) 2 , we have for y ≥ 2, P a 2 δp -1 ≥ y ≤ exp -ny 4 . Therefore, by taking y = K/δ p , we get for any K ≥ 2δ p ,
Combining it with (78), we know for K ≥ 2δ p , g p (v) is 2K-Lipschitz with probability greater than 1exp(-pK 4 ). From (78), we can also get
Combining the Lipschitz continuity of g p (v) and Eg p (v) with (85),
we can obtain (35) by a standard epsilon-net argument as follows. We need to consider different values of ε:
1) If ε ≥ δ p , we construct an epsilon-net of [0, 2] formed by the following points:
where we have used the Lipschitz continuity of g p (v) and Eg p (v), as well as ε ≥ δ p . Then
2) If ε < δ p , we construct an epsilon-net of [0, 2] formed by the following points:
Combining ( 90) and (91), together with symmetry and the union bound, we directly get (35).
The proof follows the CGMT framework [12], [13]. The optimization in (37) is equivalent to
where w ∼ N (0, I n ). The corresponding auxiliary problem (AO) of ( 92) is
where (x) + def = max{x, 0}, g ∼ N (0, I n ), h ∼ N (0, I p ), h 0 ∼ N (0, 1) and they are mutually independent.
Now we analyze the inline optimization problem of (93), which can be simplified as:
where in (95) we make a change of variable: τ √ δp → τ and the parametric function v (h; τ, g) is defined as:
Denote τ * AO (θ) as the optimal solution in (95). From (94) and the fact that we did a change of variable in (95), it can be seen τ * AO (θ) =
. Note that this is consistent with (82).
We now show objective function F (τ ; θ, g, h) in (95) converges to F (τ ; θ) def = F p (τ ; θ + σ 2 p , δ p ) with high probability over τ ∈ Ω(σ p , δ p ). The first and third term in RHS of (95) is relatively easy to deal with. By the concentration of g √ n (e.g. [38, p.44]) and h 0 √ p , there exists c > 0, s.t., for any ε > 0 and τ ∈ Ω(σ p , δ p ),
and
Here in (97), we have used the fact that for τ ∈ Ω(σ p , δ p ), τ δp 2 + θ+σ 2 p 2τ ≤ C δ p , where C is some constant. For the second term, define the following function: V (h; τ, g)
where v (h; τ, g) is given in (96). We now show there exists c > 0, s.t., for any ε ≥ 0,
where
First, note that for any fixed g, v (h; τ, g) is 2-Lipschitz continuous, so V (h; τ, g) is 2 √ p -Lipschitz continuous w.r.t. h. Also we can verify that E h v(h; τ, g) = f (τ g ), with τ g def = τ √ n g . Then using Theorem 2.1 in [36, p.176], we have for any g and ε > 0,
It can be checked that f (t) in (100) satisfies f (t) ∈ [-1, 0] for any t > 0. Combining this with (100) and (101), we know (99) holds for ε > 1 2 . On the other hand, by a direct differentiation, we have f
, for all t > 0. Therefore, for any ε ∈ (0, 1/2), on the event E ε = g √ n -1 < ε , which happens with probability P(E ε ) ≥ 1ce -nε 2 /c , there exists c > 0, s.t., |τ gτ | ≤ cε. As a result, there exists c > 0, s.t., for ε ∈ (0, 1/2), P(|f (τ g )f (τ )| > ε) ≤ ce -nε 2 /c . This together with (101) implies there exists c > 0, s.t., for ε ∈ (0, 1/2), inequality (99) still holds.
Combining (97) and (99), we get that there exists c > 0, s.t., for any ε > 0, τ ∈ Ω(σ p , δ p ) and θ ∈ [0, 1],
On the other hand, it can be verified from definition that there exists C > 0, s.t., F (τ ; θ, g, h)
and F (τ ; θ) are both Cδ p -Lipschitz over τ ∈ Ω(σ p , δ p ). Then by a similar epsilon-net argument as in the proof of Proposition 8, we can get:
Since φ(θ, g, h) = min τ ∈Ω(σp,αp) F (τ ; θ, g, h) and 2Q * p (θ) = min τ ∈Ω(σp,αp) F (τ ; θ), from (103) we know there exists c > 0, s.t., for any ε > 0,
Since 2Q AO,p (θ) = max{φ(θ, g, h), 0}, from (104) we have
Taking into account the fact Q * p (θ) ≤ Cδ p (as shown in Appendix B), we can further obtain the following Bernstein's type inequality: there exists c > 0, s.t., for any ε > 0 and θ ∈ [0, 1],
Then by CGMT (e.g., [33,Corollary 5.1]), (106) implies that there exists c > 0, s.t.,
Finally, from (107) we know there exists c > 0, s.t., for any η > 0 and θ ∈ [0, 1],
Then for γ > 2, letting η = p -1/γ in (109) and taking into account Assumption (A.4), we can get E|Q p (θ) -Q * p (θ)| ≤ cp -1/γ for some c > 0 and all the sufficiently large p. As a result,
Since the constant c above does not depend on θ, we get (51).
To prove this, we can show a
, for any i ∈ [k] and use the fact that a ⊺ i u * \i and a ⊺ i u * \[k] are in the same probability space. Lemma 8: There exists c > 0, s.t., for any ε > 0 and i = 1, 2, . . . , p -1,
Proof: To lighten notation, define
. Denote the objective function in (66) as L \[i] (u), (with k replaced by i here). By strong convexity of L \[i] (u), we have
and
where we use the fact |β i | = 1 and Cauchy-Schwartz inequality in the last step. From (111) and
(112), we can get ∆ [i] ≤ 2 a i+1 . Therefore, there exists c > 0, s.t., for any ε, D > 0,
where (x) + def = max{x, 0}. Then by choosing D ≍ δ p for small ε and D ≍ δ p ε for large ε, we can get (110).
Lemma 9: There exists c > 0, s.t., for any b i ∈ R, i = 1, 2, . . . , k and ε > 0,
and
Proof: From Lemma 8, for any k ∈ [p], there exists c > 0, s.t., for any ε > 0,
By the exchangeability of a
, we have for any i ∈ [k], it holds that
Therefore, we have for any ε > 0,
which is (114). The other direction (115) can be obtained in the same way.
2)
Lemma 10: When k ≤ p 2 , there exist C, c > 0, s.t. for any ε > 0,
.
(116)
Proof: By the definition of u * \[k] , we can get
where F p is defined in (7). Similar to (104), we can get for k ≤ p 2 , ∃c > 0, s.t., ∀ε > 0, Proof: Using (116) and following the similar steps as (113), we can get:
where in step (a), we use (127), in step (b), we use (82) and step (c) follows from inequality (131) and conditions k ≤ p 1 8 and σ 2 p ≥ c ′ log 2 p . The other directions of ( 129) and (130) can be derived similarly, which lead to (29) and (30).
Here we gather some properties of the Gaussian tail bounds that will be used in our proof.
Let Φ(x) and ϕ(x) be the CDF and PDF of the standard Gaussian distribution, respectively. It is well known that (see [38, p.14] for a proof), for any x > 0,
where m(x) def = Φ(-x) ϕ(-x) is known as the Mills ratio. Correspondingly, the inverse Mills ratio is defined as h(x) def = 1/m(x). This provides us a way to approximate the tail probability Φ(-x) by ϕ(x), which has an explicit form. In view of (82) and ( 131
On the other hand, if α p < 2, then for large enough p, it holds that σ p ≥ 1 log p . Choose L in (73) to be L = ⌊5 log p⌋ . Without loss of generality, assume Lk is odd (otherwise we add L by