The Squared-Error of Generalized LASSO: A Precise Analysis

1.2. Motivation

• The motivating connections are noiseless compressed sensing, which asks how many measurements ensure recovery, and proximal denoising, which estimates from noisy uncompressed observations.The introduction presents generalized LASSO as bringing these problems together.Source: §1.2 · p. 4, §1.2.1 · p. 4, §1.2.2 · p. 4

1.2.3 The “merger" LASSO

• The paper targets precise NSE bounds for arbitrary convex regularizers, a gap left by analyses that had focused on narrower settings.The introduction identifies the NSE as the natural performance measure when signals may have arbitrary structure.Source: §1.2.3 · p. 5

1.3. Three Versions of the LASSO Problem

• The framework treats constrained LASSO, a residual-plus-penalty estimator, and the original squared-loss LASSO, and establishes useful connections among them.It assumes independent standard normal entries in A and Gaussian noise with covariance σ²I_m.Source: §1.3 · p. 5
• For the constrained estimator, prior knowledge of f(x0) simplifies the analysis; the penalized formulations use a tuning parameter to compensate for lacking that knowledge.The constrained form minimizes the residual subject to f(x) ≤ f(x0).Source: §1.3 · p. 5

1.4. Relevant Literature

• The closest cited exact analyses focus on sparse recovery, while this work builds on Stojnic’s Gaussian-process framework and extends it in multiple directions.Earlier cited work also connects LASSO mean-squared error to approximate message passing.Source: §1.4 · p. 6

1.5. Contributions

• The paper generalizes constrained-LASSO analysis to arbitrary convex penalties, extends small-noise NSE bounds to penalized variants, maps the penalized forms, gives tuning recipes, and analyzes unstable recovery.The stated contribution includes sharp bounds for constrained LASSO as σ → 0, and a precise small-noise NSE formula for the squared-loss version.Source: §1.5 · p. 6

1.6. Motivating Examples

• The NSE formulas depend on summary parameters D_f(x0, R+) and D_f(x0, λ), Gaussian squared-distances that capture signal structure and penalty choice.The distances are to the conic hull of the subdifferential and to the λ-scaled subdifferential, respectively.Source: §1.6 · p. 7
• The introduction describes sparse, low-rank, and block-sparse estimation as settings where structure-specific penalties illustrate the general analysis.Examples include ℓ1 penalization for sparse signals and the nuclear norm for low-rank matrices.Source: §1.6 · p. 7

2.1. First-Order Approximation

• Linearizing f around x0 yields an approximated LASSO whose analysis transfers to the original estimator when the estimation error vanishes, as it does for C-LASSO when σ→0.The approximation is tight as the estimate approaches x0, enabling precise original-problem results in the small-noise regime.Source: §2.1 · p. 8

2.2. Importance of σ →0

• For C-LASSO, the small-σ NSE formula also upper-bounds NSE at arbitrary noise levels; the analogous guarantee for ℓ2-LASSO variants is not proved.The paper says higher-order terms may be needed for precise arbitrary-noise results.Source: §2.2 · p. 8

2.3. Gordon’s Lemma

• Gordon’s Lemma relates the approximated LASSO to a simpler optimization over independent standard-Gaussian vectors, making probabilistic analysis more tractable.The simplified problem provides a probabilistic lower bound for the LASSO’s optimal cost.Source: §2.3 · pp. 8–9

2.4.1 Deterministic Analysis

• For fixed Gaussian vectors, optimizing over vectors of fixed norm reduces the lower key optimization to a scalar problem involving distance to λ∂f(x0).The resulting minimizer norm has a closed form when ∥g∥ exceeds that distance.Source: §2.4.1 · p. 9

2.4.2 Probabilistic Analysis

• Gaussian concentration turns the deterministic quantities ∥g∥² and dist²(h, λ∂f(x0)) into high-probability results under bounds on D_f(x0, λ).Lemma 2.3 assumes D_f(x0, λ) stays between fixed positive fractions of m.Source: §2.4.2 · p. 10

2.5. Connecting back to the LASSO: The “Predictive Power of Gordon’s Lemma”

• The lower key optimization predicts the approximated LASSO’s cost and error norm, while further bounds show its cost concentrates around ση.The paper uses this predictive connection in its analysis of C-LASSO’s worst-case NSE.Source: §2.5 · p. 10

2.6. Synopsis of the Technical Framework

• The framework bounds the approximated LASSO cost from below and above using Gordon’s Lemma, with bounds made arbitrarily close to ση.It also uses a further application of Gordon’s Lemma to relate deviation of the minimizer norm from γ to increased optimal cost.Source: §2.6 · p. 11

2.7. Gaussian Squared Distance and Related Quantities

• C-LASSO analysis uses D_f(x0, R+), whereas ℓ2-LASSO also uses D_f(x0, λ) and C_f(x0, λ); the former quantities summarize Gaussian distances tied to the problem’s geometry.D_f(x0, λ) is strictly convex in λ and differentiable for λ>0.Source: §2.7 · p. 11

3.1. Setup

• The results assume the subdifferential at x0 excludes the origin and hold with high probability over the measurement matrix and noise.The setup also recalls D_f(x0, λ), C_f(x0, λ), and D_f(x0, R+) as the relevant quantities.Source: §3.1 · p. 12

3.2. C-LASSO

• C-LASSO’s NSE is sharply characterized, and the theorem indicates its worst case occurs as σ→0.The theorem assumes D_f(x0, R+) lies between fixed positive fractions of m and gives a high-probability result.Source: §3.2 · p. 12, §3.6 · p. 14

3.3. ℓ2-LASSO

• For ℓ2-LASSO, Theorem 3.2 characterizes the small-noise NSE for penalty values in RON, subject to stated bounds on the Gaussian-distance quantities.RON is defined by a condition involving m−D_f(x0, λ) and C_f(x0, λ).Source: §3.3 · p. 13

3.4. ℓ22-LASSO

• The map from RON to positive τ values is strictly increasing, continuous, and bijective; the associated NSE expression is presented as a small-noise prediction.The paper says it believes the expression also upper-bounds NSE at arbitrary σ, but does not have a rigorous proof of Formula 1.Source: §3.4 · p. 13, §3.6 · p. 14

3.5. Converse Results

• When m<D_f(x0, R+), the paper’s converse result establishes failure of robust recovery in the small-noise regime.The remarks relate this boundary to the minimum measurement count required for recovery.Source: §3.5 · p. 14, §3.6 · p. 14

3.6. Remarks

• The paper does not prove that the worst-case-at-σ→0 result extends to ℓ2-LASSO variants, and says their formulas lack that guarantee.It also notes that the ℓ2-LASSO NSE depends on λ and is sharply characterized at small σ for λ in RON.Source: §3.6 · p. 14

3.7. Paper Organization

• The paper lays out separate sections for the framework, estimator-specific results, converse regime, simulations, and future directions.The simulations are described as supporting the analytical predictions.Source: §3.7 · pp. 14–15

4.1. C-LASSO

• For m>D f(x0, R+), the C-LASSO is characterized by D f(x0, R+); its NSE increases as m approaches that value and diverges at equality.For arbitrary σ, the stated relation holds with ≈ replaced by ≲.Source: §4.1 · p. 15

4.1.1 Relation to Proximal Denoising

• The linear-measurement NSE exceeds the corresponding proximal-denoising normalized MSE by a factor m/(m−D f(x0, R+)).The paper interprets this factor as the penalty paid in estimation error for using linear measurements.Source: §4.1.1 · p. 15

4.2.1 Regions Of Operation

• The ℓ2-LASSO has three λ-regions: ROFF for λ≤λcrit, RON for λcrit<λ<λmax, and R∞ for λ≥λmax.λbest minimizes D f(x0, λ), while λmax solves m=D f(x0, λ) above λbest; λcrit is defined by m−D f(x0, λ)=C f(x0, λ) when a solution exists.Source: §4.2.1 · pp. 15–16

4.2.2 Characterizing the NSE in each Region

• In RON, the ℓ2-LASSO NSE is characterized for sufficiently small σ and is minimized at λbest; ROFF and R∞ behavior is partly empirical.The paper observes that stable recovery is not possible in R∞; for ROFF it proves the noiseless-fit reduction for sufficiently small λ and reports empirical support for the whole region.Source: §4.2.2 · pp. 16–17, §4.2.3 · p. 17

4.3.1 Connection to ℓ2-LASSO

• The ℓ2-LASSO penalty λ and the squared-loss ℓ2-LASSO penalty τ are related by a bijective map over RON, where their NSEs behave the same.The proposed mapping translates the NSE characterization for λ in RON to the corresponding result for τ>0, under the stated measurement condition.Source: §4.3.1 · p. 17, §4.3.2 · p. 17

4.3.3 A rule of thumb for the optimal penalty parameter

• The optimal squared-loss penalty is τbest=map(λbest); under reasonable assumptions, the paper gives a simpler approximation using λbest and D f(x0, R+).The approximation relies on D f(x0, λbest)≈D f(x0, R+).Source: §4.3.3 · p. 17

4.4. Closed Form Calculations of the Formulae

• For sparse, low-rank, and block-sparse signals, available bounds or formulas for the geometry summaries yield closed-form NSE bounds.The discussion also describes exact formulas for D f(x0, λ) and C f(x0, λ) for these signal models.Source: §4.4 · p. 18, Table 3 · p. 19

4.5. Translating the Results

• When measurement signal power is reduced by m, the proposed NSE upper bound is amplified m-fold, with penalty mappings τ↔mτ′ and λ↔√mλ′.This translates the results to the discussed non-unit-variance measurement setting.Source: §4.5 · p. 19

5.1. Introducing the Error Vector

• Writing w=x−x0 makes the estimation error the optimization variable, and the paper introduces perturbation functions and approximate C-LASSO and ℓ2-LASSO problems.The rewrite gives the residual norm as ∥Aw−σv∥.Source: §5.1 · p. 20, §5.2 · p. 20

5.3. Technical Tool: Gordon’s Lemma

• A modified Gordon’s Lemma adapts the Gaussian-process comparison to the paper’s setup.Its proof parallels Gordon’s original argument, with the statement modified for this analysis.Source: §5.3 · pp. 20–21

5.4. Simplifying the LASSO objective through Gordon’s Lemma

• Applying Gordon’s Lemma three times yields key optimizations for lower bounds, upper bounds, and deviation analysis instead of analyzing the original LASSO objective directly.The analysis uses these simplified problems for the original and approximate constrained and penalized formulations.Source: §5.4 · p. 21

5.4.2 Upper Bound

• The upper-bound derivation restricts the dual maximization to a compact set, preserving a valid bound and allowing the restriction to be chosen for tightness.The paper applies Gordon’s Lemma to the dual formulation of the objective.Source: §5.4.2 · p. 22

5.4.4 Summary

• The section summarizes lower-, upper-, and deviation-bound comparisons as probabilistic statements involving the corresponding key optimizations.The summary drops specified noise-dependent terms from the earlier corollaries.Source: §5.4.3 · p. 22, §5.4.4 · p. 23

6.1. Preliminaries

• The constrained and penalized problems share a generic analysis, with the set C chosen as the subdifferential cone or the λ-scaled subdifferential.The section defines Gaussian distance-related quantities for these sets and uses them in the subsequent optimization analysis.Source: §6.1 · pp. 23–24, §6.2 · p. 24

6.3. Analysis

• For each key optimization, the analysis proceeds from a scalar reduction to a deterministic optimum and then a probabilistic statement.The lemmas are structured to show how these steps yield results usable in the preceding comparison bounds.Source: §6.3 · p. 24

6.3.1 Lower Key Optimization

• The lower-key-optimization probabilistic result assumes m≥D(C)+εLm.The lemma supplies the lower optimization’s probability statement under this measurement condition.Source: §6.3.1 · p. 25

6.3.2 Upper Key Optimization

• The upper-key-optimization result assumes m≥max{D(C), D(C)+C(C)}+εLm.The lemma gives a probabilistic bound under this condition.Source: §6.3.2 · p. 25

6.3.3 Deviation Key Optimization

• The deviation-key-optimization result is stated under a range condition placing D(C) between fixed fractions of m.The supplied condition is (1−εL)m>D(C)>εLm.Source: §6.3.3 · p. 26

6.4. Going Back: From the Key Optimizations to the Squared Error of the LASSO

• Combining the key-optimization lemmas with Gordon’s comparisons yields bounds for the approximate objective and its optimizer’s norm.The combined result is stated under measurement and dimension conditions involving D(C) and C(C).Source: §6.4 · pp. 26–27

7. The NSE of the C-LASSO

• Under the theorem’s dimension assumptions, the original C-LASSO NSE concentrates around D f(x0, R+)/(m−D f(x0, R+)) for sufficiently small σ.The approximate C-LASSO concentrates around the same quantity for arbitrary σ.Source: §7 · p. 28

7.2.2 Proof of Theorem 3.1: Small σ regime

• The small-noise threshold σ0 is deterministic and depends on m, n, f, x0, and the proof tolerance.The theorem states that σ0 is independent of A and v.Source: §7 · p. 28, §7.2.2 · p. 31

7.1. Approximated C-LASSO Problem

• The approximate C-LASSO corresponds to the generic analysis with C=cone(∂f(x0)), and its cone geometry gives C(C)=0.The section invokes Moreau’s decomposition in establishing the mapping of the generic quantities.Source: §7.1 · pp. 28–29

7.2.1 Tangent Cone and Cone of the Subdifferential

• For a convex descent set, the section relates its tangent cone at x0 to the cone of the subdifferential when x0 is not a minimizer of f.This convex-analysis relation supports the transfer from the approximate problem to the original constrained problem.Source: §7.2.1 · p. 29

7.2.2 Proof of Theorem 3.1: Small σ regime

• The small-σ proof uses feasible directions and a projection of the approximate solution to compare its residual with the approximate optimum.A contradiction argument rules out a substantial gap between the projected point’s residual and that optimum.Source: §7.2.2 · p. 31

8. ℓ2-LASSO: Regions of Operation

• The analysis divides λ≥0 into ROFF, RON, and R∞, whose performance is analyzed separately.The section states that the performance characterization applies across penalty values and that values in each region share performance characteristics.Source: §8 · p. 31, §8.3 · p. 33

8.1. Properties of Distance, Projection and Correlation

• D_f(x0, λ)+2C_f(x0, λ)+P_f(x0, λ)=n.At λ=0, D_f(x0,0)=n while P_f and C_f are zero; as λ tends to infinity, D_f and P_f tend to infinity and C_f tends to negative infinity.Source: §8.1 · p. 32
• D_f(x0, λ) is strictly convex and has a unique minimizer, λbest.It is differentiable for λ>0 and continuous on λ≥0; the projection P_f(x0, λ) is increasing.Source: §8.1 · p. 32

8.2.1 λbest

• λbest uniquely minimizes D_f(x0, λ), and the section assumes D_f(x0, λbest)<m for robust estimation to be possible.Since D_f(x0,0)=n, its minimum is no greater than n.Source: §8.2.1 · p. 32

8.2.2 λmax

• λmax is the unique λ≥λbest satisfying D_f(x0, λ)=m, provided D_f(x0, λbest)<m.Existence follows from continuity and the divergence of D_f as λ tends to infinity; uniqueness follows from strict increase beyond its minimizer.Source: §8.2.2 · p. 32

8.2.3 λcrit

• When m≤n, λcrit is the unique λ≤λbest satisfying m−D_f(x0, λ)=C_f(x0, λ); when m>n, λcrit=0.The stated uniqueness for m≤n follows from the decreasing function used in the argument.Source: §8.2.3 · p. 33

8.3. Regions of Operation: ROFF, RON, R∞

• In ROFF, m−D_f(x0, λ)≤C_f(x0, λ); in RON it exceeds both 0 and C_f(x0, λ); in R∞, m≤D_f(x0, λ).The section identifies RON as the interval from λcrit to λmax.Source: §8.3 · p. 33

9.1.2 Original ℓ2-LASSO: Proof of Theorem 3.2

• The RON result is first established for an approximated ℓ2-LASSO problem, then translated to the original problem for sufficiently small noise.The proof uses a uniform first-order approximation of f around x0 to relate the two problems.Source: §9.1 · p. 34, §9.1.1 · p. 34, §9.1.2 · pp. 34–35

9.1. RON

• In RON, the asymptotic NSE formula is D_f(x0,λ)/(m−D_f(x0,λ)).The theorem’s stated conditions require the relevant distance quantities to remain below m by a fixed margin and D_f(x0, λ) to be bounded below by a fixed fraction of m.Source: §9.1 · p. 34, §9.1.3 · p. 36

9.1.3 A Property of the NSE Formula

• The asymptotic NSE formula is convex in λ over RON.The proof composes the convex D_f(x0, λ) with the increasing convex function x/(m−x) on the region’s stated range.Source: §9.1.3 · p. 36

9.2. ROFF

• The analysis does not prove an NSE characterization in ROFF; the authors report numerical experiments indicating the optimal estimate reduces to the noiseless compressed-sensing approach.For sufficiently small λ, the residual term dominates, and Lemma 9.2 formalizes a reduction under its stated assumptions.Source: §9.2 · p. 36
• The authors identify λcrit as the transition point at which ℓ2-LASSO reduces to the noiseless compressed-sensing approach.The supplied text contrasts this claim with a lemma that supports small-λ behavior but does not locate the exact transition.Source: §9.2 · p. 36

9.3. R∞

• In R∞, where m≤D_f(x0, λ), the authors expect no noise robustness.They state that the NSE diverges as σ→0 under the stricter condition m<D_f(x0,R+), and leave the wider regime m<D_f(x0, λ) for future work.Source: §9.3 · p. 37

10. Constrained-LASSO Analysis for Arbitrary σ

• The constrained-LASSO worst-case NSE is achieved as σ → 0, so the exact small-noise bounds upper-bound squared error for arbitrary noise variance.The proof again relies on the proper application of Gordon’s Lemma.Source: §10 · p. 37

10.2. Lower Key Optimization

• Under ∥g∥ > dist_R+(h), the lower key optimization’s minimizing error vector has norm no larger than the approximated problem’s minimizer.This is the critical property established for the original C-LASSO lower key optimization.Source: §10.2 · p. 37

10.3. Upper Key Optimization

• Applying Gordon’s Lemma to the dual C-LASSO yields an upper key optimization, whose optimal cost and associated upper bound are Lipschitz functions.The section introduces the upper bound as a high-probability bound for the original C-LASSO optimal cost.Source: §10.3 · p. 39

10.4. Matching Lower and Upper key Optimizations

• With high probability, both lower and upper key optimizations lie within ϵσ√m of the same expected upper-optimization cost when D_f(x0, R+) is bounded away from 0 and m.The lemma assumes ϵ0m ≤ D_f(x0, R+) ≤ (1 − ϵ0)m for sufficiently large m; its probability bound is 1 − exp(−cm).Source: §10.4 · p. 40

10.5. Deviation Bound

• Restricting the error-vector norm yields a high-probability deviation-cost increase under conditions that keep D_f(x0, R+) bounded away from 0 and m.Lemma 10.6 asserts a positive deviation threshold δdev under these proportional bounds for sufficiently large m, with probability 1 − exp(−O(m)).Source: §10.5 · p. 41

10.5.1 Deterministic Result

• If ηs(g, h) ≤ (1 + ϵdev)ηd, the restricted optimization’s cost exceeds the lower key optimization by at least the stated difference of L terms.For ∥g∥ > dist_R+(h), the bound is L((1 + ϵdev)ηd; ∥g∥, dist_R+(h)) − L(ηs(g, h); ∥g∥, dist_R+(h)).Source: §10.5.1 · p. 42
• The deterministic argument uses convexity of L(α;∥g∥,dist_R+(h)), which is minimized at η_s, to support its lower-bound comparison.Source: §10.5.1 · p. 42

10.5.2 Probabilistic result

• With probability 1−exp(−O(m)), ∥g∥² and dist_R+(h)² lie within εm of m and D_f(x_0,R_+), respectively.These concentration bounds make Lemma 10.7 applicable in the proof of the probabilistic result.Source: §10.5.2 · pp. 42–43

11.1. Mapping the ℓ2-penalized to the ℓ22-penalized LASSO problem

• The section derives the mapping between ℓ2- and squared-ℓ2-penalized LASSO by estimating the residual norm using a first-order approximation.The derivation substitutes the approximation into the optimality-based relation to obtain the mapping formula (3.4).Source: §11.1 · pp. 44–45

11.2. Properties of map(λ)

• The map map(λ)=λ·calib(λ) is continuous and strictly increasing from 0 at λ_crit to infinity as λ approaches λ_max, so it is bijective onto the nonnegative reals.The stated properties hold when m>D_f(x_0,λ_best).Source: §11.2 · p. 46

11.3. On the stability of ℓ22-LASSO

• Under the stated Gaussian-design, Lipschitzness, and sample-size assumptions, squared-ℓ2 LASSO has estimation error proportional to the noise variance with high probability.The theorem assumes x_0 is not a minimizer of f and D_f(x_0,R_+)≤(1−ε_L)m; its constant is independent of σ.Source: §11.3 · pp. 47–48

12. Converse Results

• When m < D_f(x0,R+), the NSE approaches infinity as σ → 0, identifying D_f(x0,R+) as the noiseless compressed-sensing threshold.The converse analysis focuses on this low-measurement regime.Source: §12 · p. 49

12.1. Converse Result for C-LASSO

• At small m, C-LASSO can have multiple minimizers, including a feasible minimizer far from x0.The stated converse holds with high probability for sufficiently small noise under Assumption 12.1.Source: §12.1 · p. 49

12.2. Converse Results for ℓ2-LASSO and ℓ22-LASSO

• For ℓ2-LASSO, the converse shows NSE diverges as σ → 0 under the stricter condition m < D_f(x0,R+).The authors note this condition is weaker than the upper-regime threshold m ≥ D_f(x0,λ), and leave a sharper converse for future work.Source: §12.2 · p. 50
• ℓ2^2-LASSO does not recover x0 stably when m < D_f(x0,R+).Source: §12.2 · p. 51

13.1. Sparse Signal Estimation

• The small-σ NSE formula matches the sparse simulations; NSE is flat on one side of the penalty range and rises as λ approaches λmax.Source: §13.1 · p. 51
• Figure 6 tracks normalized optimization cost and observation fit; in ROFF, λ ≤ λcrit ≈ 0.76 yields y = Ax* for the ℓ2-LASSO estimate.The observation-fit panel corresponds to calib(λ) on RON.Source: Figure 6 · p. 52
• Both ℓ2-LASSO and ℓ2^2-LASSO reach the same minimum NSE, around 1.92, in the sparse-signal simulations.The estimated D_f(x0,λbest) is around 330 for this setup.Source: §13.1 · p. 52

13.2. Low-Rank Matrix Estimation

• 2.63 is the estimated best-case NSE for the low-rank ℓ2-LASSO setup, and simulations are consistent with the analytical predictions.The setup uses d = 45, rank 6, and m = 0.6d² = 1215.Source: §13.2 · p. 52, Figure 7 · p. 53

13.3. C-LASSO with varying σ

• 560 is the estimated D_f(x0,R+) for the low-rank C-LASSO setup; for σ² ≤ 10^-2, NSE is noticeably high when m is below this threshold.At σ² = 1, the change around the threshold is less apparent and NSE remains relatively small.Source: §13.3 · p. 53

14. Future Directions

• A rigorous proof of the ℓ2^2-LASSO formula is described as the paper’s most important missing point.Such a proof would extend results of to arbitrary convex functions.Source: §14 · p. 53
• For C-LASSO, the small-σ formula upper bounds NSE at arbitrary σ, but the corresponding claim for ℓ2 and ℓ2^2-LASSO remains unproved.The paper reports only empirical support for the latter claim.Source: §14 · p. 54
• The analysis covers a single signal, while a proposed extension treats mixtures such as low-rank plus sparse components or sparse corruptions.For sparse-corruption measurements, prior work gives noiseless recovery guarantees but not precise noise analysis [32] [33].Source: §14 · p. 54
• Application-specific guarantees beyond NSE, such as estimate sparsity or matrix rank, are proposed as a useful direction.The generic framework can yield NSE upper bounds when an upper bound on D_f(x0, λ) or D_f(x0, R+) is available.Source: §14 · p. 54
• The paper leaves open measurement ensembles beyond independent standard Gaussian entries and noise settings such as adversarial noise.Subgaussian matrices are cited as a possible alternative; compressed-sensing phase-transition literature reports behavior like Gaussian matrices [35,36].Source: §14 · p. 54
• The authors suggest extending error analysis to expected NSE, potentially with additional assumptions.The paper instead focuses on squared ℓ2 error and high-probability guarantees.Source: §14 · p. 54

A. Useful Facts

• Moreau’s decomposition states that a vector splits into projections onto a closed convex cone and its polar, with orthogonal components.Projection is the unique nearest point in a nonempty closed convex set, and projection is 1-Lipschitz.Source: A. Useful Facts · p. 58
• For a Gaussian input, an L-Lipschitz function has variance at most L^2.The appendix also introduces a Gaussian concentration inequality for Lipschitz functions.Source: A. Useful Facts · p. 58

B. Auxiliary Results

• Gaussian concentration bounds for norms, projections, and distances follow by applying a Lipschitz-function lemma to these 1-Lipschitz quantities.Their squared expectations are identified with dimension, projected Gaussian squared norm, and squared distance, respectively.Source: B. Auxiliary Results · pp. 58–59
• For a closed convex set, the larger of C(C) and P(C) is bounded by 2(n + D(C)).The proof uses this bound to control an auxiliary probability term.Source: B. Auxiliary Results · p. 59
• When D(C) lies a fixed fraction below m, the appendix establishes high-probability comparisons between Gaussian norms and distances.One stated comparison is ∥g∥ > dist(h, C), with probability 1 − exp(−O(m)).Source: B. Auxiliary Results · p. 59

C. Proof of (modified) Gordon’s Lemma

• The modified Gordon lemma extends a minimax probability comparison to continuous processes over compact sets.The proof passes from finite coverings to compact sets using continuity and concentration.Source: C. Proof of (modified) Gordon’s Lemma · pp. 61–62

D. The Dual of the LASSO

• The LASSO dual is derived by reformulating the primal and optimizing over the residual variable; strong duality is invoked under strict feasibility.The text states that the primal and dual have the same optimal cost when the stated feasibility condition holds.Source: D. The Dual of the LASSO · pp. 62–63

E.1.1 Scalarization

• The proof of Lemma 6.1 reduces optimization over vectors with fixed norm to a one-dimensional optimization.A convex-set observation is applied to perform this scalarization.Source: §E.1.1 · pp. 63–64

E.1.2 Deterministic Result

• The scalarized deterministic problem is solved by setting the objective derivative to zero under the stated assumption.This yields the lemma’s second statement.Source: §E.1.2 · p. 64

E.1.3 Probabilistic Result

• The probabilistic lower bound is obtained from Gaussian concentration when m exceeds D(C) by a fixed margin.The argument gives probability at least 1 − 8 exp(−c0δ^2m).Source: §E.1.3 · pp. 64–65

E.2.2 Deterministic Result

• The convex objective φ is minimized at α = 1, since φ(α) ≥ φ(1) for every α in [0, 1].This establishes α* = 1.Source: §E.2.2 · p. 66

E.2.3 Probabilistic Result

• With high probability, condition (E.14) holds at rate 1 − exp(−O(γ(m,n))), where γ(m,n) = m for cone C and min{m^2/n, m} otherwise.The proof also establishes h ∉ C with probability 1 − exp(−O(m)) and uses these events to obtain the stated high-probability lower bound for Û.Source: §E.2.3 · p. 67

E.3.1 Scalarization

• The reduction of L̂dev(g,h) to a one-dimensional optimization follows the same steps as the reduction of L̂(g,h) in Section E.1.1.Source: §E.3.1 · p. 68

E.3.2 Deterministic Result

• Because L is strictly convex and its unconstrained minimizer lies outside Sdev, its minimum over Sdev occurs at a boundary point, giving L̂dev(g,h) = L((1 ± δdev)Cdev).Source: §E.3.2 · p. 68

E.3.3 Probabilistic Result

• The probabilistic proof applies perturbation analysis to L around parameter values √m and √D(C), then establishes the claimed bound (6.10) with high probability.It first verifies assumption (6.9) with high probability and uses the deterministic result to express L̂dev at a boundary point.Source: §E.3.3 · p. 69

F. Deviation Analysis: Key Lemma

• For parameters satisfying (1 − ϵ)a > b > ϵa, the auxiliary function L(x; a, b) is strictly convex, and its minimizer is controlled under sufficiently small relative perturbations of a and b.The lemma also analyzes restricted minimization over x ≥ clow.Source: F. Deviation Analysis: Key Lemma · p. 70
• Combining (F.6), (F.7), and (F.8) yields the existence of a sufficiently small constant ϵ1 > 0.Source: F. Deviation Analysis: Key Lemma · p. 72
• For the sixth statement, given γ > 0, the proof chooses ϵ1 sufficiently small using the fourth and fifth statements; for the seventh, it uses a > b.Source: F. Deviation Analysis: Key Lemma · p. 72
• A triangle-inequality step lower-bounds L(x; a′, b′) − L(x∗(a, b), a, b) by the difference at (a′, b′) minus an absolute change in L.The comparison is stated explicitly in the proof.Source: F. Deviation Analysis: Key Lemma · p. 72

G. Proof of Lemma 8.1

• The proof states that D_f(x0, λ) diverges to infinity as λ grows, and consequently C_f(x0, λ) tends to negative infinity.It uses the identity D_f + P_f + 2C_f = n for the latter conclusion.Source: G. Proof of Lemma 8.1 · p. 73
• The projection quantity P_f(x0, λ) vanishes as λ approaches zero, with |P_f(x0, λ) − P_f(x0, 0)| bounded by R^2λ^2.The proof also states P_f(x0, 0) = 0.Source: G. Proof of Lemma 8.1 · p. 73
• The proof uses Lemma G.1 to show that D_f(x0, λ) is nonincreasing in λ, while P_f(x0, λ) is increasing.At λ = 0, D_f(x0, 0) = 0; the proof also states that D_f(x0, λ) is nonnegative.Source: G. Proof of Lemma 8.1 · pp. 74–75
• Lemma G.1 compares projections of z and αz onto a closed convex set, and its proof reduces the geometry to the plane through O, P1, and Z.The proof then establishes the desired comparison by cases based on the angle at P1.Source: G. Proof of Lemma 8.1 · pp. 74–75
• For λ between zero and λ_best, D_f(x0, λ) is strictly decreasing and C_f(x0, λ) is nonnegative; at λ_best, C_f(x0, λ_best) equals zero.For λ at or above λ_best, the proof states C_f(x0, λ) is nonpositive.Source: G. Proof of Lemma 8.1 · p. 75
• For 0 ≤ λ1 < λ2 ≤ λ_best, the proof establishes D_f(x0, λ1) + C_f(x0, λ1) > D_f(x0, λ2) + C_f(x0, λ2).It combines inequalities using the decrease of D_f and increase of P_f.Source: G. Proof of Lemma 8.1 · p. 75

H.1. ℓ1 minimization

• For ℓ1 minimization, the distance calculation uses soft-thresholding of Gaussian entries and expectations over nonzero and zero coordinates.The appendix refers readers to [26] for further details on ℓ1 phase-transition formulas.Source: §H.1 · p. 76, §H.1.1 · p. 76

H.1.1 Closed form bound

• The ℓ1 distance formula separates the k nonzero coordinates, contributing (λ^2 + 1)k, from the soft-thresholded Gaussian terms on the remaining coordinates.A Gaussian tail bound is used to control the soft-thresholded term.Source: §H.1.1 · p. 76
• D_f(x0, λ) ≤ (λ^2 + 3)k for a k-sparse signal under the stated ℓ1 bound.The bound follows from the soft-thresholded Gaussian-distance calculation.Source: §H.1.1 · pp. 76–77

H.2. Nuclear norm minimization

• For a rank-r d × d signal, the asymptotic formula for D_f(x0, λ) is expressed using β and the tail moments Ψ0, Ψ1, and Ψ2.The formula is given for the regime r/d described in the subsection.Source: §H.2 · p. 77

H.2.1 Closed form bounds

• For a rank-r d × d signal, D_f(x0, λ) ≤ (λ^2 + 2d)r + 2d.This is the stated closed-form upper bound for nuclear-norm minimization.Source: §H.2.1 · p. 78

H.3. Block sparse signals

• For block sparsity with k nonzero blocks of size b, the appendix gives formulas for D_f, P_f, and C_f in terms of Ψ tail functions.The expressions depend on λ and the number t − k of zero blocks.Source: §H.3 · p. 78

H.3.1 Closed form bound

• For block-sparse signals, the closed-form bound calculation estimates the Gaussian shrinkage term using a χ^2 tail bound and a lemma.The nonzero blocks contribute (λ^2 + b)k to D_f(x0, λ).Source: §H.3.1 · p. 79

• The section presents a Gaussian-width characterization for the widened tangent cone of a convex function at x0.The cone is defined for a convex f when x0 is not a minimizer.Source: §I · p. 79
• The width analysis decomposes each vector into tangent-cone and subdifferential-cone components, then bounds the latter using the widening parameter and Rmin.Rmin is the minimum norm of a subgradient at x0.Source: §I · pp. 79–80
• The stability argument combines Gaussian-width bounds with Gordon’s result and a concentration step for a Gaussian measurement matrix.The stated setup takes A to have i.i.d. standard normal entries.Source: §I · pp. 80–81