{'fraction_non_alphanumeric': 0.0535635602555629, 'fraction_numerical': 0.015587133729896454, 'mean_word_length': 3.838507661558961, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Complete Lasso Diagram

A fundamental problem in the high-dimensional regression is to understand the trade-off between type I and type II errors or, equivalently, false discovery rate (FDR) and power in variable selection. To address this important problem, we offer the first complete diagram that distinguishes all pairs of FDR and power that can be asymptotically realized by the Lasso with some choice of its penalty parameter from the remaining pairs, in a regime of linear sparsity under random designs. The trade-off between the FDR and power characterized by our diagram holds no matter how strong the signals are. In particular, our results improve on the earlier Lasso trade-off diagram of arXiv:1511.01957 by recognizing two simple but fundamental constraints on the pairs of FDR and power. The improvement is more substantial when the regression problem is above the Donoho--Tanner phase transition. Finally, we present extensive simulation studies to confirm the sharpness of the complete Lasso trade-off diagram.


Introduction
Consider a data matrix X ∈ R n×p with p features and n rows, and a response y ∈ R n from the standard linear model y = Xβ + z, (1.1) where z ∈ R n is the noise term. In this paper, we study the Lasso, which, given a penalty parameter λ > 0, finds the solution to the convex optimization problem [20]: A variable j is selected by the Lasso if β j (λ) = 0 and the selection is false if the variable is a noise variable in the sense that β j = 0. The Lasso is perhaps the most popular method in high-dimensional setting where the number of features p is very large and therefore sparse solutions are wished for. Here the sparsity, defined as k = #{j : β j = 0}, indicates that only k < p out of the sea of all the explanatory variables are in effect and have non-zero regression coefficients. Owing to the sparsity of its solution, the Lasso is also widely recognized as a feature selection tool in practice. Therefore, one particularly interesting and important question is to understand how well the Lasso performs as a feature selector. The best-case scenario is that one can find a well-tuned λ such that the Lasso estimator can discover all the true variables and only the true variables, resulting in zero type I error and full power. This is known as the feature selection consistency. In theory, when the signals are strong enough, and when the sparsity is small enough, consistency can be guaranteed asymptotically [21]. In practice, nevertheless, the model selection consistency is usually a pipe dream: for example, even in a moderately sparse regime, consistency is impossible [19], and thus the trade-off between the type I error and the statistical power is unavoidable. Therefore, it is much more sensible to evaluate the performance of the Lasso not at some single "best" point (since there is no such point), but rather to focus on the entire Lasso path { β(λ) : λ ∈ (0, ∞)} and evaluate the overall trade-off between the type I error and the statistical power. To assess the quality of each selected model {1 ≤ j ≤ p : β j (λ) = 0} at some λ, we use the false discovery proportion (FDP) and the true positive proportion (TPP) as measures. Formally, the FDP and TPP are defined as: In this paper, we characterize the exact region in the TPP-FDP diagram where the Lasso trade-off curves locate. A complete theoretical study of such a diagram will surely enhance our understanding of the advantages and limitations of Lasso. It can be used to theoretically guide the data analysis procedure and explain why Lasso has good empirical performance in certain scenarios.

Prior Art and Our Contribution
In [19], Su et al. proved that under the linear sparsity regime, where the ratio n/p is roughly constant, it is impossible for the Lasso to achieve the feature selection consistency and a tight lower boundary of the trade-off curves was established. Moreover, they showed that when n/p is less than 1 (i.e., in the high-dimensional setting) and when the sparsity k is large enough, the TPP of Lasso is always bounded away from 1, regardless of λ. This phenomenon is closely related to the Donoho-Tanner (DT) phase transition [8,14,13,9,11,1]. The results in [19] can be visualized in the schematic plots in Figure 1. However, the dichotomy offered by their lower boundary does not give a complete picture: it is clear that the red region is unachievable, yet the lower boundary says little about the entire "Possibly Achievable" region above it. This ambiguity is resolved in this paper.
In a more recent paper [22], the authors recognized a region in the TPP-FDP diagram termed as the "Lasso Crescent" in the noiseless case, which is enclosed by sharp upper boundary and lower boundary. To gain more insights into those two boundaries, a new notion term as the "effect size heterogeneity" is proposed: while all the other conditions remain unchanged, the more heterogeneous the magnitudes of the effect sizes are, the better the Lasso performs. As a result, the upper boundary (or the worst trade-off curve) in the noiseless case is given by the homogeneous effect sizes, while the lower boundary (or the best trade-off of TPP-FDP) is achieved asymptotically by the most heterogeneous effect sizes. Though the achievability is not the primary focus in [22], they partially refine the achievable region from the entire white region in Figure 1 to the Lasso Crescent. But their scenario is limited to the case without taking the DT phase transition into account, and it is still unclear whether the entire region enclosed in the Lasso Crescent is achievable or not. Possibly Achievable Figure 1: The dichotomy of achievability by the Lasso [19]. The sparsity ratio is fixed to k/p = 0.3. Left: sampling ratio is n/p = 1 (low dimension), and it is below the DT phase transition. Middle: sampling ratio is n/p = 0.7 (high dimension), and it is below the DT phase transition. Right: sampling ratio is n/p = 0.5 (high dimension), and it is above the DT phase transition. The dashed line represents the upper limit of TPP.
In this paper, we study the exact achievable region, taking into account the cases below and above the DT phase transition. We depict the complete Lasso achievability diagrams in terms of the TPP-FDP trade-off in all possible scenarios. On top of [19], we specifically find three inherently different diagrams as shown in Figure 2: We enclose the achievable region by exact upper boundaries, and notably, we identify two distinct sub-cases (Left and Middle panels of Figure 2) when it is below the DT phase transition, as opposed to the corresponding panels (Left and Middle panels) in Figure 1. Our work provides a worthwhile understanding of the DT phase transition, in the sense that we consider not only the possible region of the TPP (i.e., power), but also the possible region of (TPP, FDP) jointly. The complete Lasso diagrams for the same setting as in Figure 1. The sparsity ratio is fixed to k/p = 0.3. Left: sampling ratio is n/p = 1 (low dimension), and it is below the DT phase transition. Middle: sampling ratio is n/p = 0.7 (high dimension), and it is below the DT phase transition. Right: sampling ratio is n/p = 0.5 (high dimension), and it is above the DT transition. The dashed line represents the upper limit of TPP, passing through the intersection point of the upper and the lower boundaries.
To establish the theoretical results of our work, we leverage the powerful Approximate Message Passing (AMP) theory that has been developed recently [12,2,3,10]. We also use a homotopy argument to show the asymptotic achievability of every point within the claimed region.

Main Results
We start presenting our results by laying out the working assumptions as follows.
1. We assume that X consists of i.i.d. N (0, 1/n) entries so that each column has approximately unit 2 norm. As the index l → ∞, we assume n l , p l → ∞ with n l /p l → δ in the limit for some positive constant δ ∈ (0, ∞). The index l is often omitted for the sake of simplicity.
3. The noise z i is i.i.d. drawn from N (0, σ 2 ), where σ ≥ 0 is any fixed constant. For the completeness of our definition, X, β, and z are jointly independent.
From now on, we consider the trade-off between the TPP and FDP as λ varies in (0, ∞), i.e., along the Lasso path. Notation-wise, we use fdp and tpp to denote values in [0, 1], and reserve TPP and FDP for the corresponding random variables.

The Complete Lasso Diagram
In this subsection, we characterize the feasible region of the Lasso on the TPP-FDP diagram. We provide a set of constraints that any Lasso path must satisfy, and further show that any point in the region defined by the constraints is achievable asymptotically. We term such a region as the feasible region of Lasso.
The function q in the above definition is a deterministic increasing function of , δ, which is defined in (3.7) and is first proposed in [19]. Recall k is the sparsity k := #{i : β i = 0}. We now state our main theorem. To avoid any confusion, we say that a point (tpp, fdp) is asymptotically achievable, if there exists some Π, σ and a sequence of (possibly adaptive) {λ l }, such that (TPP l (λ l ), FDP l (λ l ))−(tpp, fdp) P → 0. 1 Theorem 1 (The complete Lasso diagram). For any 0 < < 1 and δ > 0 , under the working assumptions, the following conditions hold: (a) Any Lasso trade-off curve lies inside the region D ,δ asymptotically.
(b) Any point in D ,δ is asymptotically achievable by the Lasso.
Theorem 1 provides a complete characterization of the location of the Lasso solution on the TPP-FDP diagram. It can be seen from this theorem that the region D ,δ is essentially the union of all the Lasso paths asymptotically: We pause here to explain the intuition behind the constraints that define D ,δ : constraint (1) directly comes from the definition; constraint (2) is from the fact that the Lasso outperforms the random guess, and hence selects no more than 1 − fraction of false signals; constraint (3) is from the main result from [19, Theorem 2.1]; constraint (4) comes from the fact that the number of selected variables do not exceed n.
In Figure 2, we plot three different cases of the Lasso diagrams with different δ and , where the region D ,δ is marked in blue. The difference between these diagrams comes from different active constraints defining D ,δ .
We rewrite the boundary lines of the constraints (2) and (4) of Definition 2.1 as and then we can describe the three diagrams accordingly.
Case 1: When δ ≥ 1 and 0 ≤ ≤ 1, we obtain that l 2 is always above l 1 in the interval (0, 1), and thus only the constraint from l 1 is active. We note that this case is below the DT phase transition. This case corresponds to the left plot in Figure 2.
Case 2: When δ < 1 and is sufficiently small, we see that l 1 and l 2 intersects. Hence both constraints from l 1 and l 2 are active. However, l 2 is always above and thus never intersects with q on (0, 1). Similar to Case 1, it is below the DT phase transition. This case corresponds to the middle plot of Figure 2.
Case 3: When δ < 1 and is sufficiently large, again l 1 and l 2 intersect, and l 2 also intersects with q within (0, 1). We observe the DT phase transition. This case corresponds to the right plot of Figure 2. Surprisingly, the maximum TPP achievable by the Lasso is exactly where l 2 and q intersect.
In particular, when δ < 1 (i.e., Case 2 or 3), consider the following equation in t from [19, There is a unique positive such that when = , (2.3) has a unique positive root in t. When > there is no positive root t. This is known as the DT phase transition point. With , we can define the maximum achievable TPP as in [19 When ≤ , Lasso can have power arbitrarily close to 1, which falls into Case 2 in our discussion above. When > , the power is at most u and bounded away from 1, and this corresponds to Case 3. We can show in the following lemma an equivalent characterization of the DT phase transition.
Lemma 2.2. The curve q intersects with l 2 in (0, 1) if and only if > (δ), and in the intersecting scenario, the intersection point is at TPP = u .
This lemma provides an alternative view of the DT phase transition: the setting is above the DT phase transition if and only if the curve q and line l 2 intersect with each other. From this perspective, the maximum power is not a magic output of some mysterious machine, but is indeed the power when exactly n discoveries are made by Lasso when it is on the lower boundary q . The proof of this lemma can be found in Appendix A.
Before we end this section, we emphasize the difference between our findings in Theorem 1 with the results in [19]. We prove here that all asymptotically achievable points indeed constitute D ,δ , while [19] only showed that all Lasso paths are above the curve q without further specification of the achievable region nor the unachievable one. Furthermore, when it is below the DT phase transition, we separate the Case 1 and Case 2 (the Left and Middle panels in Figure 2) which is not distinguished therein. Those two diagrams are very different. The case in the Middle panel guarantees that one cannot make too many mistakes with full power, since the FDP has a non-trivial upper bound.
To elaborate on the last point, we demonstrate three more trade-off diagrams below, focusing on the case when n ≤ p. As it is clear from Figure 3, our complete Lasso diagrams show that the achievable region is relatively narrow in its vertical direction when the TPP is large (close to 1). In the left and right panel, we see that it is above the DT phase transition in both cases, and thus there is a single value of FDP (around 21% and 16%) when the TPP achieves its maximum. From the middle panel, we see that the range of the FDP is also narrow (36% ∼ 41%) when the TPP is close to 1. We want to emphasize that according to the result in [19], the lower bounds of FDP in all cases (21%, 36%, and 16%) are the best possible value achievable when the TPP is close to its maximum. However, our complete Lasso diagram also guarantees that it is impossible to have a much worse FDP than the best possible ones when the TPP is large.  Figure 3: The complete Lasso diagrams, in which high TPP guarantees low FDP. Left: sparsity ratio is k/p = 0.722, and sampling ratio is n/p = 0.95. It is just above the DT phase transition, and the maximum FDP is around 0.21 when the TPP is close to 1. Middle: sparsity is ratio k/p = 0.5, and sampling ratio is n/p = 0.85. It is below the DT phase transition, and the maximum FDP is no more than 0.41 when the TPP is close to 1. Right: sparsity ratio is k/p = 0.8, and sampling ratio is n/p = 0.85. It is above the DT phase transition. The dashed line represents the upper limit of TPP, which is 0.89 in this case, and the maximum FDP is around 0.16 when the TPP is close to 0.89.

Proofs
In this section, we establish part (a) of Theorem 1. To this end, we first show the fact that under our assumptions, the TPP and FDP have uniform limits. As will be clear in subsection 3.1, it is not hard to check that such limits of pairs (TPP, FDP) are indeed within D ,δ . To prove part (b) of Theorem 1, we first show that the boundary of D ,δ can be achieved by a sequence of priors and noises. Then, we extend the achievability result from the boundary to the entire interior of the region by a homotopy argument.

Proof of Part (a) of Theorem 1
In this subsection, we first invoke the following lemma to derive uniform limits of TPP and FDP over λ's. We denote Π to be the conditional distribution of the prior given it is not zero, that is, the distribution Π|Π = 0.  [19], see also Theorem 1 in [6] and Theorem 1.5 in [4]). Fix any δ, , Π , σ, and 0 < λ min < λ max . When n/p → δ and k/p → , we have the following uniform convergence, sup and sup where the two deterministic functions are

4)
and where W ∼ N (0, 1) independent of Π. In addition, τ > 0, α > 0 is the unique solution 2 to The guarantee of uniform convergence of TPP and FDP along the Lasso path allows us to directly deal with the two deterministic functions tpp ∞ and fdp ∞ , instead of considering TPP and FDP as random variables for each finite n and p, which depends on the realizations of the signal, the noise, and the design matrix. Thus, we can focus on the properties of tpp ∞ and fdp ∞ .
To prove the part (a) of the Theorem 1, we will prove any (tpp ∞ , fdp ∞ ) pair satisfies all the four constraints of Definition 2.1. The constraint (1) is trivial, since TPP is bounded between 0 and 1 by definition, and so is tpp ∞ . We now prove the constraints from Definition 2.1 in the order (4)(2)(3). We start proving by constraint (4). 2 We note the first equation is known as the state evolution equation, and the second is the calibration equation. The notation ηα(·) is the soft-thresholding operator defined as ηα(x) = sign(x)(|x| − t)+. We note that the solution α also satisfies α > α0, where α0 is the unique root to t in ( Lemma 3.2. For any , δ, Π, and σ, we have δ tpp ∞ + fdp ∞ ≤ 1. Proof of Lemma 3.2. Let V = #{i : β i (λ) = 0, β i = 0} be the number of false discoveries, and D = #{i : β i (λ) = 0} be the number of total discoveries. Recall the sparsity is k = #{i : β i = 0}. By definition, we have FDP = V D and TPP = D−V k . So, δ TPP + FDP = δ . We view f V,n (D) as a function of D, and treat V, n as fixed. Note that by definition, V ≤ D, and the number of discoveries made by the Lasso is less than or equal to n, so V ≤ D ≤ n always holds. It is not hard to see that, at the two endpoints D = n and D = V , f V,n (D) attains its maximum f V,n (n) = 1 = f V,n (V ). Hence, for any V, n, and D, f V,n (D) ≤ 1. By the uniform convergence of TPP and FDP in (3.1)(3.2), we finally have δ tpp ∞ + fdp ∞ ≤ 1.
The key element of this lemma is simply that "the Lasso never selects more than n variables", which results in δ TPP + FDP ≤ 1. This is a simple corollary of the KKT condition of the Lasso.
The next lemma proves the constraint (2) in Definition 2.1 of D ,δ . To see why this lemma should be intuitively true, recall that = k p , and if we select signals uniformly at random, each variable that we select is false with probability p−k p = 1 − . As a result of randomly selecting variables, we end up with FDP= 1 − on average. It is natural for the Lasso to produce a better result. Therefore, this lemma is a sanity check on the Lasso, claiming that the Lasso performs no worse than a random guess. Consequently, 1 − serves as a simple upper bound for FDP.
Proof on Lemma 3.3. Observe the probability P(|Π , where the inequality holds as the standard normal distribution is unimodal at the origin and α > 0. Therefore, by (3.3) we have Next, we proceed to prove constraint (3) in Definition 2.1. We introduce the lower boundary q of any Lasso trade-off curve as follows: let t (u) be the largest solution to where Φ(·) and φ(·) denote the cumulative density function and probability density function of the standard normal distribution, respectively. Then q is defined as With the definition of q , we can now state the fundamental trade-off between tpp ∞ and fdp ∞ , which serves as a lower bound for FDP.
Combining all those pieces, we can now prove part (a) of Theorem 1.

Proof of Part (b) of Theorem 1
In the previous subsection, we have shown that, asymptotically, all (TPP, FDP) pairs along the Lasso path locate inside the region D ,δ . We now proceed to prove that every point in D ,δ is indeed asymptotically achievable by some Lasso solution.
We note that for each prior Π, each specific noise level σ, and each fixed λ, the pair (TPP, FDP) is asymptotically a fixed point specified as the (tpp ∞ , fdp ∞ ) in Lemma 3.1. Therefore, given and δ, the entire achievable region is composed by the trajectory of (tpp ∞ , fdp ∞ ) resulting from the variation of the three parameters: Π, σ and λ. To simplify the analysis of the trajectory of (tpp ∞ , fdp ∞ ), we will always fix some of these parameters.
Following the proposal in the preceding paragraph, we first "fix" the penalty parameter λ and consider the variation of the noise and the prior. We focus on two extreme scenarios that are easy to analyze, namely when λ is large enough and when λ → 0. We can make the λ large enough so that the Lasso makes no discovery 3 for any fixed prior and noise, and hence the trajectory of (tpp ∞ , fdp ∞ ) is a vertical line of the form tpp ∞ = 0. In the other case when λ → 0, there is almost zero shrinkage. Thus, the Lasso tends to make the maximum possible amount of discoveries. Notice that when n is larger than p, the tpp ∞ → 1 almost surely, since Lasso eventually behaves as the least square regression. However, when n is less than p, the Lasso selects at most n variables, and thus the maximum of tpp ∞ can either be 1 or strictly less than 1, depending on the sparsity k. Therefore, with different sampling ratio δ = n/p and sparsity ratio = k/p, one expects the pairs (tpp ∞ , fdp ∞ ) to have different trajectories when we vary the prior and the noise. Another useful extreme case corresponds to "fixing" the prior to be some (sequence of) Π, such that when we vary σ from 0 to ∞, the corresponding Lasso path approaches the lower boundary of D ,δ (i.e., the curve q ) and the upper boundary of D ,δ (i.e., fdp ∞ = 1 − ).
We will prove that the four trajectories in the above discussion jointly constitute the boundary of D ,δ , whose achievability is guaranteed asymptotically. Therefore, it is just a stone's throw to prove the achievability of the interior of D ,δ by the homotopy theory.
We start with the following lemma, which analyzes the trajectory of (tpp ∞ , fdp ∞ ) when λ → ∞ and λ → 0, separately. Recall that we define in equation (2.3).
Next, we need to find some specific priors to approach the upper and lower boundary when σ varies. However, a single prior isn't enough to attain the boundary. Instead, we show in the following lemma that there exists a sequence of priors, such that when σ = 0, the Lasso trade-off curves approximate the lower boundary q in (3.7). Lemma 3.6 (Lemma 4.8 in [22]). Suppose σ = 0, then there exists a sequence of priors Π (m) , such that as m → ∞, q Π (m) converges uniformly to q .
This lemma finds a sequence of priors that achieves the lower boundary when σ = 0. We now need to show when σ → ∞, the trade-off curves of the same sequence of priors approach the upper boundary fdp ∞ = 1− . This claim is intuitively correct: in the presence of infinite noises, the fdp ∞ should be 1 − for any prior, since the signal to noise ratio is infinitely small, and any discovery of the Lasso is equivalent to the discovery of a random guess. Formally, we have the following lemma. Combining Lemma 3.5, Lemma 3.6, and Lemma 3.7, it is easy to check that in those extreme cases, the (tpp ∞ , fdp ∞ ) points form the entire boundary of D ,δ . Now we introduce a homotopy lemma to bridge from the achievability of the boundary of D ,δ to the achievability of the interior of D ,δ . The idea of homotopy is pretty intuitive: suppose there are two curves, Curve A and Curve B, and a continuous transformation f move A to B. It is easy to imagine that the trajectories of the two endpoints of Curve A during the transformation f form two other curves, say Curve C, and Curve D. Then there is a region surrounded by Curve A, B, C, and D. It is a region defined by Curve A, B, and the transformation f . The homotopy theory guarantees that every point in this region is passed by the transforming curve during the transformation.
We formalize this idea in the following lemma. Since its form is similar in spirit to the onedimensional intermediate value theorem, we term it as an intermediate value theorem on the plane. Its proof is given in Appendix B.
Following our proposal at the beginning of this section, we are now equipped with all we need to prove part (b) of Theorem 1.
By Lemma 3.6, there exists a sequence of priors Π (m) such that the lower boundary q is the uniform limit of q Π (m) when σ = 0. Combining this with our definition of g, we know that lim m→∞ g(λ, 0, Π (m) ) is exactly the curve (u, q (u)). By Lemma 3.7, we have g 2 (λ, ∞, Π (m) ) = 1 − for any m, and thus lim m→∞ g 2 (λ, ∞, Π (m) ) = 1 − , which is the upper boundary. We can view the lower boundary as curve C 1 and the upper boundary as curve C 2 in the Lemma 3.8. Given this, our goal is to find a transformation f such that f transforms C 1 to C 2 and encloses exactly the region D ,δ .
We define the transformation f as f (λ, t) = lim m→∞ g(λ, tan(t/ π 2 ), Π (m) ). From the uniform convergence, we know f itself is continuous. It is direct to verify that C 1 = {f (λ, 0) : l ≤ λ ≤ r} is the lower boundary and C 2 = {f (λ, 1) : l ≤ λ ≤ r} is the upper boundary. 5 Now, consider the trade-off curve of q t (λ) ≡ f (λ, t) where λ ∈ [l, r]. Notice that for each t, the curve q t is continuous and bounded on any [l, r], and from Proposition 3.5 we know q t has a welldefined limit as λ → 0 + , and λ → ∞. Therefore, we can make a continuous extension of q t from λ ∈ [l, r] to λ ∈ [0, ∞] using the natural compactification. So, without loss of generality, we can think of [r, l] = [0, ∞] as a compact interval on the extended real line. Let Now, we observe that the curve C 2 corresponds to the case that σ → ∞, or effectively Π → 0. Therefore by Lemma 3.7, it is just the line {(x, 1 − ) : x ∈ [0, x ]}, where x = min{1, δ} is the intersection of fdp ∞ = 1 − and fdp ∞ + δ tpp ∞ = 1. By Lemma 3.6, curve C 2 is just the curve q in the range [0, u ]. By the part (1) of Proposition 3.5, f (0, t) is always on the segment joining (0, 0) and (0, 1 − ), so C 3 is just this segment. Similarly, by the part (2-4) of Proposition 3.5, f (∞, t) is always on the poly-line joining from (x , 1 − ) down to the endpoint of curve C 2 (u ).
We observe that C = C 1 ∪ C 2 ∪ C 3 ∪ C 4 is the boundary of the region D ,δ . Therefore, every point in D ,δ is achievable by some f (λ, t) by the homotopy Lemma 3.8.

Simulations
To better illustrate our theoretical results and understand the proof of Theorem 1(b), we present the following simulations where we fix the signals β and vary the sampling ratio and the magnitude of the noise z. As indicated by Theorem 1, the Lasso path indeed 'swipes' the complete achievable region enclosed by the upper and lower boundaries in (2.1),(2.2), and (3.7), when σ varies from 0 to ∞. In the simulations, we fix p = 1000, k = 300, and set n = 1000, 700, and 500, respectively. Consequently, the sparsity ratio is fixed to 0.3 while the sampling ratio δ is 1, 0.7, and 0.5. We note that these are the same parameters as we used in Figure 1 and Figure 2. Across all simulations, we fix β to be a 300-sparse vector with 5 different levels of magnitudes: β j = 0.01, 0.1, 1, 10 or 100, and each level contains k/5 = 60 variables. When σ = 0, the Lasso path is close to the lower boundary. As σ increases, the Lasso path gradually moves upward and becomes worse -as for each fixed TPP, the FDP is larger. When σ is sufficiently large, the Lasso trade-off curve approaches the upper boundary and behaves similarly to the random guess. We plot the Lasso trade-off curves for 8 levels of σ in Figure 4. From the results, it is not hard to see the alignment of our theoretical results and the real simulations: our theoretical achievable TPP-FDP regions D ,δ indeed enclose all Lasso paths (up to small random errors) and the boundaries are tight. The R codes for the simulations and for plotting Lasso Diagrams are available at https: //github.com/HuaWang-wharton/CompleteLassoDiagram.

Conclusions and Future Works
Our result provides the first complete discussion of the Lasso trade-off diagram between the TPP and FDP under all possible circumstances. In contrast to the previous works, we focus on quantifying the exact achievable region of (TPP, FDP) pairs asymptotically, and therefore resolved the unanswered question of determining the achievability of points in the trade-off diagram. Notably, we discover that even for the case below the DT phase transition, there is a finer sub-classification of the case n < p and the case n ≥ p (compare the Left and Middle panels in Figure 2 to those in Figure 1). Furthermore, comparing Figure 2 to Figure 4, we confirm that our result is asymptotically exact and aligns with simulations with a moderate sample size. In closing, we introduce several directions for future research. First, it would be of interest to extend the results to other penalized regression-based models, including but not limited to the SLOPE [5], the SCAD [15], the group Lasso [16] and the sparse group Lasso [16,18]. We believe that the homotopy tool can be applied in the search of the exact trade-off diagrams of these methods. Such diagrams are of great theoretical interest and would surely enhance our understanding of the advantages and limitations of different methods. Second, it is interesting and important to leverage our understanding of the complete diagram to better analyze practical problems and guide more informed fine-tuning of parameters. As illustrated in Figure 3, we can have a very narrow estimate of the false discoveries when we know Lasso has large power. A complete diagram can be used to theoretically guide our analysis and to explain why certain methods have good empirical performance in certain scenarios. This can be a good scaffold to develop better methods.
where the first inequality is due to the well-known fact φ(t) ≥ ( 1 t − 1 t 3 )Φ(−t) for t > 0. So h(t) is strictly decreasing when t > 0, and thus h(t) < h(0) = 1 < 1 + t 2 for all t > 0. Now, suppose (A.1) does not hold, and thus we can find some t such that Since > , we know But g(0) = 1 > δ and lim t→∞ g(t) = ∞. By the continuity of g(t), we know there is a root for g(t) = δ in (0, t) and (t, ∞), contradicting with the definition of , or the fact that g(t) = δ has a unique positive root.
Lemma A.4. for δ < 1 and > (δ), we have Proof of Lemma A.4. We prove by contradiction and suppose lim λ→0 + τ = 0. By Lemma A.2, we know the only regime for this to hold is when τ monotonically decreases as λ decreases. By easy calculation, we have lim We also note that for any Π = 0, Π τ → ∞ as τ → 0. Therefore, by (A.1) in Lemma A.3, there exists some η > 0 such that This inequality implies that when τ is small enough, we must have For this τ , from the state evolution equation (3.5), we have which is clearly a contradiction.
Given the lemmas above, we can now prove the Lemma 3.5.
As we have shown in Lemma A.4, when ≥ (δ) only case (b) happens, and thus we have proven (3); while when < (δ), both cases (a) and (b) are possible, and thus we have proven (4).
Next, we prove Lemma 2.2, which is a new characterization of the DT phase transition. It is useful to observe the following facts about t , the unique positive root of equation (2.3) with = .
Lemma A.5. Let t be the unique positive root of equation (2.3) with = . We have Proof of Lemma A.5. By Lemma C.2 in [19], δ and (δ) satisfies the following function form of t .
To prove (1), we observe Similarly, we can prove (2) by To prove (3), we plug in t = t into equation (3.6) with u = u . The right-hand side of the equation becomes So to verify t is the solution to the equation, we only need to prove which is equivalent to show This is true by the definition of t , which is the solution to (2.3).
Given this result, we can now prove Lemma 2.2.
Proof of Lemma 2.2. We first observe that although q is originally defined on the interval (0, 1), it can be extended to a function on (0, ∞) with exactly the same form in (3.7). We consider this extended function and denote it still as q for convenience of notation. Since q is monotone, there is only one intersection point with l 2 on the (0, ∞). We will verify the following fact: The extended curve q (u) intersects with Suppose we are given this fact, then we know ≥ implies u ≥ 1, so the original q does not intersect with l 2 in (0, 1); and when < , we have 0 < u < 1, so q intersects with l 2 in (0, 1). Now, to verify Fact (A.5), we use Lemma A.5 to calculate the function values of both q and l 2 at u = u . The function value of l 2 at TPP = u is Since t = t (u ) by Lemma A.5, the value of q (u ) is These two quantities are equal, and therefore we know that q and l 2 intersect at u .

B End-point Homotopy Lemmas
In this section, we will give a brief review of some basic topological concepts and facts that allow us to prove Lemma 3.8. We first state the definition of the winding number.
Definition B.1 (Winding number). Any closed continuous curve on the x − y plane that does not pass through the origin have a continuous polar form parameterization r = r(t), θ = θ(t), for 0 ≤ t ≤ 1.
Since the function r(t) and θ(t) are continuous and the curve starts and ends at the same point, θ(0) and θ(1) must differ by an integer multiple of 2π. We define the winding number of the curve with respect to the origin by: By translating the coordinate system, it extends to the definition of winding number around any point p.
As an easy calculus exercise, one can prove that the winding number is well-defined and generic to the curve, meaning that the winding number is the same for any parameterization. In topological terminology, the winding number of the curve with respect to the origin is also known as the degree of continuous mapping from the curve to S 1 , the unit circle in R 2 . Now we define the homotopic function: Definition B.2. Suppose X and Y are topological spaces, and f and g are two continuous functions from X to Y . A homotopy between f and g is a continuous function H : X × [0, 1] → Y , such that H(x, 0) = f (x) and H(x, 1) = g(x) for all x ∈ X. Such f and g are called to be homotopic.
It is easy to see the homotopic relation between functions is an equivalence relation. This can extend to an equivalence relation between topological spaces. Definition B.3. Two topological spaces X and Y are homotopy equivalent, if there exist continuous maps f : X → Y and g : Y → X, such that g • f is homotopic to the identity map on Id X and g • f homotopic to Id Y .
A famous result given by [7] is the following lemma relates the homotopy equivalence and the winding number.
Lemma B.4. [Degree is homotopy invariant] If f, g : S 1 → R 2 are homotopic, then the degree of f and g are the same, in other words, the winding numbers of the curves f (S 1 ) and g(S 1 ) are the same.
To prove Lemma 3.8, we need the following classical result on the topological characterization of a simple closed curve.
Lemma B.5. [Jordan-Schoenflies theorem] Every simple closed curve on the plane separates the plane into two regions, one (the "inside") bounded and the other (the "outside") unbounded; further these two regions are homeomorphic (and thus homotopic) to the inside and outside of a standard circle S 1 on the plane. Specifically, the "inside" region is contractible, i.e., homotopy equivalent to a point. Proof of Lemma 3.8. We prove by contradiction and suppose there is some point p ∈ D that is not in the image of f . Denote the domain as A = I × [0, 1]. Consider a contraction map of the domain, that is, g : A → A such that g(A) = {q} for some point q ∈ A. By the fact that the simply connected region A is contractible, we know g is homotopic to Id A , the identity map on A. Thus, by the fact that composition of homotopic functions is still homotopic, we know f = f • Id A is homotopic to f = f • g, where f maps the whole domain to one point f (q) ∈ D. Now, we consider the confined maps of f and f on the boundary of domain ∂A. By assumption, f (∂A) ∈ D is just the boundary curve C, while f • g(A) = {f (q)} ∈ D is just a point in D. Since those two continuous maps are homotopic, they have the same degree, i.e., they have the equal winding number with respect to point p. Note that the two winding numbers with respect to p must be well-defined, since, by assumption, p is not in the image of f , so p ∈ C and q = p.
By Jordan-Schoenflies theorem B.5, we know the winding number of C with respect to p is 1, since it equals to the winding number of S 1 with respect to the origin. On the other hand, the winding number of trivial curve {q} with respect to p is 0, since p = q. This leads to a contradiction.