Precise Error Analysis of Regularized M-estimators in High-dimensions

1.1 Motivation

• The framework addresses structured-signal recovery from noisy linear measurements in the proportional regime, including compressed measurements where m < n.Signals are modeled through distributions encoding structures such as sparsity, block-sparsity, and low-rankness.Source: §1.1 · pp. 1–2

1.2 Contribution

• The squared error converges in probability to the unique minimizer of a deterministic convex optimization over four scalar variables, with loss and noise summarized by the Expected Moreau Envelope.The characterization explicitly includes the measurement ratio δ and regularization parameter λ, while the regularizer and signal distribution enter through an analogous summary functional.Source: §1.2 · p. 2
• The Expected Moreau Envelope is the central summary parameter, remaining smooth regardless of loss smoothness and generalizing geometric quantities such as Gaussian width and statistical dimension.It determines how the loss and regularizer affect error performance under the proposed characterization.Source: §1.2 · p. 2
• The theorem permits arbitrary convex regularizers and minimal generic assumptions, including non-smooth or non-separable losses and regularizers and noise distributions with unbounded moments.This generality subsumes existing performance results for specific M-estimators as special cases.Source: §1.2 · pp. 2–3, §1.3 · p. 4
• The Convex Gaussian Min-max Theorem strengthens Gordon’s comparison inequality by making bounds tight under convexity, providing the proof’s transparent and broadly applicable framework.Applying CGMT to regularized M-estimators requires additional ideas introduced in this work.Source: §1.2 · p. 3

1.3 Related Work

• Prior compressed-sensing bounds are often only order-wise, whereas this work provides precise error characterizations for general convex losses, regularizers, and signal and noise distributions under Gaussian designs.The noisy setting requires predicting estimation error values that depend on both measurement count and signal/noise statistics, rather than only exact-recovery thresholds.Source: §1.3 · pp. 3–4

1.4 Organization

• The paper proceeds from problem setup and the main theorem to separable specializations, examples and simulations, proof mechanics including CGMT, related work, and future directions.Proofs are deferred to Appendices A–E.Source: §1.4 · pp. 4–5

2.1 Notation

• The analysis uses standard convex-analytic objects, including subdifferentials, Fenchel conjugates, Moreau envelopes, and proximal operators.It also defines conventions for one-sided limits, partial derivatives, probability, convergence in probability, Gaussian variables, and Gaussian vectors.Source: §2.1 · p. 5

2.2 Setup

• The problem dimensions m and n grow proportionally to infinity, with a Gaussian measurement matrix whose entries are iid N(0, 1/n).This normalization makes the rows approximately unit-norm and supports a well-defined signal-to-noise ratio.Source: §2.2 · p. 5
• The unknown signal may be structured and need not have iid entries, while remaining independent of the measurement matrix; the noise has n-independent one-dimensional marginals and is also independent of that matrix.Signal structure is encoded by its joint density, and the noise is specified through its probability distribution.Source: §2.2 · pp. 5–6
• The estimator uses proper continuous convex regularizers and losses, with the loss normalized to have minimum zero and satisfy a bounded-subgradient growth condition.The regularizer parameter λ is fixed and positive.Source: §2.2 · p. 6
• The estimator is evaluated by empirical squared error, a random quantity whose high-probability limit is precisely evaluated as n → infinity.The randomness comes from A, z, and x0, and the framework applies to sequences of problem instances satisfying the stated conditions.Source: §2.2 · p. 6

3.1 Key Assumption

• Assumption 1 defines continuous summary functionals L and F through in-probability convergence of normalized Moreau-envelope differences, with growth conditions accommodating unbounded noise moments.These functionals are essential ingredients in the error prediction, while additional continuity and growth properties are imposed by the master theorem.Source: §3.1 · p. 6

3.2 Theorem

• Theorem 3.1 predicts the estimator’s asymptotic error in probability from the unique minimizer of a four-variable convex-concave Scalar Performance Optimization problem.The result applies as dimensions grow with m/n → δ ∈ (0, ∞), over randomness in the design, noise, and signal.Source: §3.2 · p. 7

3.3 Separable M-estimators

• For separable M-estimators, L and F become Expected Moreau envelopes, which are smooth and strictly convex even when the underlying loss is nonsmooth or not strictly convex.These properties help guarantee uniqueness of the SPO minimizer; the framework also permits heavy-tailed noise under a primitive integrability condition.Source: §3.3 · p. 8

3.4.1 On Assumption 1

• The assumptions are designed to be generic and minimal, translating in separable settings into easier sufficient conditions while also covering non-separable losses and regularizers.Assumption 1 does not require separability; examples include square-root lasso and another non-separable regularizer.Source: §3.4.1 · p. 8

3.4.2 On Assumption 2

• For unbounded-moment noise, Assumption 2 requires sub-linear growth of L in its smoothing parameter, a condition typically inherited from corresponding Moreau-envelope properties.This regime often corresponds to L0 = +∞.Source: §3.4.2 · p. 9

3.4.3 On the theorem

• The SPO objective is jointly convex in α and τg and concave in β and τh, enabling efficient numerical solution; strict convexity of L commonly yields uniqueness of α∗.The four-scalar formulation can also be replaced by first-order stationary equations.Source: §3.4.3 · p. 9, §3.4.4 · p. 9

3.4.4 Further Discussions

• The master theorem covers nonsmooth and non-separable models with potentially unbounded-moment noise, characterizes optimal cost as well as error, and relies on CGMT for Gaussian designs.Its characterization exposes dependence on f, ℓ, λ, and δ, supporting future performance and optimality analyses; simulations indicate accuracy at dimensions of a few hundreds or sometimes tens.Source: §3.4.4 · p. 10

4 Separable M-estimators

• The separable specialization assumes closed proper convex scalar loss and regularizer functions, together with iid entries for the noise vector and signal.These assumptions specialize the general theorem to coordinatewise separable M-estimators.Source: §4 · p. 11

4.1.1 Loss function and Noise Distribution

• For the loss and noise, Assumptions 1 and 2 reduce to an Expected Moreau-envelope integrability condition, supplemented by bounded-subdifferential requirements when the noise has unbounded second moments.The condition ensures the envelope difference is absolutely integrable and L is well-defined; examples include absolute-value and Huber losses.Source: §4.1 · p. 11, §4.1.1 · p. 11

4.1.2 Regularizer and Signal Distribution

• For the regularizer and signal, analogous Expected Moreau-envelope and mild feasibility and moment conditions ensure the assumptions required by the general theorem.These conditions are expressed through expectations over iid X0 and Gaussian H, alongside finite regularizer values at positive and negative points.Source: §4.1.2 · p. 12

4.2 The Expected Moreau Envelope

• The Expected Moreau envelopes L and F determine separable M-estimator error, are differentiable despite potentially non-smooth ℓ and f, and L is jointly strictly convex under nondegenerate noise conditions.Strict convexity of L guarantees uniqueness of the minimizer α* in the scalar optimization problem.Source: §4.2 · p. 12

4.3 Error Prediction

• Under the stated integrability, convexity, and bounded-minimizer conditions, the squared error converges in probability to the unique optimizer α* of the separable M-estimator problem.The result applies when ℓ, pZ, f, and px satisfy conditions (8), (10)–(12), with L and F defined as Expected Moreau envelopes.Source: §4.3 · p. 13
• With regularization, bounded-error requirements can permit δ > Df,x0, potentially below one, where Df,x0 matches the noiseless compressed-sensing phase-transition threshold.By contrast, unregularized M-estimators require δ > 1 in the cited example.Source: §4.3 · p. 13, §4.3.1 · p. 13

4.3.1 As a system of nonlinear equations

• The error optimizer α* can equivalently be found from four nonlinear stationary equations in α, β, τg, and τh, with boundary derivatives interpreted by one-sided limits.When the relevant variables are strictly positive, the optimality conditions hold with equalities.Source: §4.3.1 · p. 13

4.3.2 Remarks

• The four-equation system can be reformulated using proximal operators, solved empirically by simple recursion, and extended naturally to block-separable losses or regularizers such as ℓ1,2 regularization.Block-sparse extensions use growing numbers of blocks with fixed block length in the proportional regime.Source: §4.3.2 · p. 14

5.1 No Regularization

• In the absence of regularization, stable recovery requires at least as many measurements as ambient dimension (m ≥ n, δ ≥ 1), and κ* = 1/(δ − 1).Source: §5.1 · p. 15

5.2 Ridge Regularzation

• Optimally tuned ridge-regularized least squares achieves the asymptotic MMSE for Gaussian signals and reduces to the unregularized formula as λ → 0.The ridge specialization gives a unique scalar minimizer; its λ → 0 limit agrees with the ordinary least-squares result.Source: §5.2 · pp. 16–17

5.3.1 Motivation

• Constrained M-estimators replace regularization by membership in a structure-inducing set, while conic relaxation yields a tangent-cone estimator analyzable with general loss functions.The constrained formulation is related to regularized estimation through Lagrangian duality, and the cone relaxation is exact in the previously studied high-SNR setting.Source: §5.3.1 · p. 17

5.3.2 Error Performance

• When the cone’s statistical dimension D_K scales proportionally with dimension, the cone-constrained estimator’s squared error is predicted by a unique scalar minimizer.The cone constraint is represented as a non-separable indicator regularizer, with the error characterization depending on D_K.Source: §5.3.2 · p. 18

5.3.3 Remarks

• Cone constraints lower the stable-recovery threshold from δ ≥ 1 to δ ≥ D_K; least-squares attains the corresponding error formula, and LAD can achieve perfect recovery under condition (40).For Gaussian noise, the Fisher-information lower bound coincides with least-squares, establishing its optimality; the lower bound does not apply when the optimal error is zero.Source: §5.3.3 · pp. 18–20

5.4 Generalized LASSO

• The generalized LASSO has a unique scalar error characterization under finite-variance noise, is novel in this stated generality, and cannot achieve perfect recovery for any regularizer.The impossibility follows from the optimality conditions forcing a Gaussian variable into a fixed subdifferential relation.Source: §5.4 · p. 20

5.5 Square-root LASSO

• The square-root LASSO uses a non-separable, √n-normalized loss, and Theorem 3.1 predicts its squared error through a unique scalar minimizer for admissible regularizers.The required assumptions are verified for the square-root loss and finite-moment noise setting described in the passage.Source: §5.5 · p. 21
• The square-root LASSO squared-error prediction is derived as a corollary of Theorem 3.1, extending an earlier square-root LASSO result [TAH15].The derivation reduces the optimization by minimizing over τg and exploiting monotonicity in β.Source: §5.5 · p. 21

5.6.1 LAD

• For Cauchy noise, regularized LAD satisfies the assumptions needed for the theorem because its absolute-value loss has linear growth despite undefined EZ2.The absolute-value loss is nondifferentiable at zero, and the stated conditions make Theorem 4.1 applicable.Source: §5.6 · p. 21, §5.6.1 · p. 22

5.6.2 Huber-loss

• For Cauchy noise, the Huber loss satisfies Theorem 4.1’s assumptions, and Figure 3 validates its numerical error prediction.The validation is obtained by numerically solving the corresponding nonlinear system using the iterative scheme in Remark 4.3.3.Source: §5.6.2 · p. 22, Figure 3 · p. 23, §5.7 · p. 24

5.7 Numerical Simulations

• With sufficiently many measurements, an appropriate regularizer range yields perfect recovery, while accurate predictions persist for Bernoulli ({±1}) measurement matrices.The consistency observation relates to the cone-constrained LAD result and the measurement requirement quantified in (40); the Bernoulli result suggests universality.Source: §5.7 · pp. 23–24
• For sparse noise, ℓ1-regularized LAD can far outperform LASSO for well-tuned λ, although LASSO is better over another substantial λ range.The comparison uses the same sparse model for both estimators and highlights the importance of tuning λ.Source: Figure 2 · p. 23, §5.7 · p. 24
• The simulations also validate predictions for Huber-loss and non-separable square-root LASSO with ℓ1,2-regularization.The Huber prediction uses the nonlinear-equation system, while the square-root LASSO prediction is obtained by solving (47).Source: Figure 3 · p. 23, §5.7 · p. 24, Figure 4 · p. 24

6 Proof Highlights

• The proof uses the Convex Gaussian Min-max Theorem (CGMT) to replace the original optimization with an auxiliary problem while preserving information about optimal costs and solutions.The CGMT also yields the needed solution-concentration conclusion when the auxiliary and restricted auxiliary costs converge to separated limits.Source: §6 · p. 24, §6.2 · pp. 25–26

6.1 Starting Idea

• The starting idea translates convergence of the optimizer’s error into separation between the optimal cost over a target set and its complement.This indirect route is used because directly proving convergence for the original objective is difficult.Source: §6.1 · p. 25

6.2 The CGMT

• The CGMT compares a Gaussian primary optimization with a simplified auxiliary optimization and provides probability bounds for their optimal costs under compactness, continuity, and convex-concavity conditions.Its novel third statement handles arbitrary open subsets and all problem dimensions, strengthening the corresponding result in [TOH15, Thm. 3].Source: §6.2 · p. 26

6.3 Applying the CGMT

• Dualizing the M-estimator puts it into CGMT form, producing an auxiliary objective with Gaussian linear terms and a convex-concave function of the primal and dual variables.The analysis then proceeds by reducing this auxiliary problem to scalar random variables and studying their convergence in two stages.Source: §6.3 · pp. 26–27

6.4.1 Scalarization

• Fenchel duality and optimization over variable directions reduce the auxiliary problem’s dependence on w and u to their magnitudes α and β.An asymptotic minimax argument justifies exchanging optimization order, after which separability introduces two additional scalar variables and Moreau envelopes for the loss and regularizer.Source: §6.4.1 · pp. 27–28

6.4.2 Convergence

• Pointwise convergence of normalized Moreau-envelope terms is upgraded to uniform convergence on compact sets, while convexity and level-boundedness control the scalar optimizers.For unbounded noise moments, subtracting L(z) from the loss envelope can restore convergence.Source: §6.4.2 · p. 28

6.5 Concluding

• Uniqueness of the scalar optimization’s minimizer separates the restricted auxiliary cost from the unrestricted one, allowing the asymptotic CGMT corollary to establish the desired error concentration.The scalar α represents the magnitude of the estimation error w.Source: §6.5 · p. 29

Phase transitions

• Phase-transition research progressed from ℓ1 recovery bounds to asymptotically tight thresholds for general convex regularizers via Gaussian width, statistical dimension, AMP, and conic integral geometry.Early work showed ℓ1-minimization recovers sparse signals below the ambient dimension [CT06],; later results established tight phase transitions for general convex regularizers, [ALMT13].Source: §7 · pp. 29–30

Precise reconstruction error

• AMP precisely analyzed LASSO and related estimators, but prior extensions imposed separability, smoothness, strong convexity, or restricted measurement regimes.AMP results covered LASSO across regularization and SNR values [DMM11, BM12], extensions to separable regularizers [TMSB13], and broader losses under restrictive assumptions [DM13, BC15].Source: §7 · p. 30
• The CGMT line evolved from upper bounds to tight error characterizations, culminating in this paper’s unified treatment of general convex losses, regularizers, signal statistics, and noise statistics.Stojnic’s duality-based tightening [Sto13a], subsequent extensions [OTH13] [TPGH15], and the refined CGMT framework motivated the paper’s direct analysis and strengthened theorem for performance measures beyond mean-square error.Source: §7 · pp. 30–31
• Random-matrix and leave-one-out analyses accurately treated ridge-regularized estimators with broader design models, but required smooth separable losses; this paper removes those restrictions.El Karoui’s approach handles noise with unbounded moments and designs beyond iid Gaussian, including elliptical models [Kar13], while retaining smoothness and separability requirements.Source: §7 · p. 31

Universality

• Universality extends phase transitions and some constrained-LASSO error bounds beyond Gaussian designs, but universality for arbitrary losses and regularizers remains open.Results include general convex regularizers and broad entry distributions [OT15], while the current paper’s full setting remains an unresolved universality challenge.Source: §7 · p. 31
• Reconstruction error depends on the measurement design: LASSO behaves differently for isotropically random orthogonal and Gaussian matrices, unlike the apparent universality of phase transitions.This distinction also appears for elliptical designs considered by El Karoui.Source: §7 · p. 31

Conclusions

• Theorem 3.1 characterizes squared error through the loss, regularizer, noise and signal distributions, regularizer parameter, and normalized measurement count.The result applies when measurements and signal dimension grow proportionally.Source: §8 · p. 32

Other instances

• The framework supports analyzing additional loss, regularizer, and noise choices satisfying Theorems 3.1 or 4.1, including ℓ∞ loss with bounded noise.The examples studied in Section 5 are not exhaustive.Source: §8 · p. 32

Optimal tuning and comparisons

• Theorem 3.1 can guide optimal λ selection, while Figure 2 shows that incorrect λ choices can significantly deteriorate performance and that LAD can outperform LASSO for appropriate λ.Its error expressions also enable analytic comparisons across general M-estimators and settings.Source: §8 · p. 32

Optimal loss/regularizer functions

• The Expected Moreau envelope is proposed as the central quantity for optimizing loss and regularizer functions with random signals, non-least-squares losses, and nonvanishing noise.It generalizes statistical dimension, whose optimal-regularizer role is established in noiseless and certain high-SNR settings [ALMT13] [OTH13].Source: §8 · p. 32

Consistency

• Consistency reduces to identifying conditions under which α* = 0 solves the scalar optimization problem, including sufficiently many measurements and a correctly ranged regularizer parameter.A specific consistent M-estimator example is discussed under suitable noise and signal distributions.Source: §8 · pp. 32–33

Beyond squared error

• The CGMT-based auxiliary-optimization approach can characterize alternative metrics such as ℓp error and the fraction of negative estimated coordinates, not only squared error.Different sets S can be selected in the CGMT theorem to target these metrics.Source: §8 · p. 33

Beyond Gaussian Designs

• Theorem 3.1 may extend beyond Gaussian designs: simulations suggest universality for iid sub-Gaussian entries, while IRO and elliptical-like designs remain directions for broader analysis.Related results cover ridge-regularized estimators and LASSO with IRO designs [TH15].Source: §8 · p. 33

A Proof of Theorem 3.1

• The appendix proves Theorem 3.1 through several intermediate lemmas, whose proofs are deferred to Appendix B.Source: A Proof of Theorem 3.1 · p. 39

A.1 Preliminaries

• The analysis targets the nontrivial limiting behavior of ∥ˆx −x0∥2/√n.Source: §A.1 · p. 39
• Introducing w := (x −x0)/√n makes the estimation error vector explicit.Source: §A.1 · p. 39
• Dividing the objective by n normalizes the optimization cost to constant order.Source: §A.1 · p. 39
• The proof replaces the Primary Optimization in (64) with a tightly related Auxiliary Optimization analyzed through the CGMT.Source: §A.1 · p. 39

A.2 The CGMT for M-estimators

• Applying the CGMT requires rewriting (64) as a convex-concave minimax with A in bilinear form and addressing its unbounded constraints.Source: §A.2 · p. 39

A.2.1 Boundedness of the Error

• The bounded optimization is asymptotically equivalent to the original problem: if its optimizer norm converges to α∗, so does the unconstrained optimizer’s norm.The artificial constraint is retained thereafter because Lemma A.1 establishes that it does not change the limiting error.Source: §A.2.1 · p. 39

A.2.2 Identifying the (PO)

• Under Assumption 1(b), sufficiently large bounds on the dual variable make the bounded primal optimization equivalent to the original with probability approaching one.The resulting objective has the required bilinear random-matrix term and convex-concave structure for CGMT analysis.Source: §A.2.2 · p. 40

A.2.3 The (AO)

• The auxiliary optimization is obtained from the bounded primal problem through the CGMT, with the analysis targeting convergence of the optimizer norm to α∗.The auxiliary problem is introduced as the object whose optimizer behavior will establish the desired error limit.Source: §A.2.3 · p. 40

A.2.4 Asymptotic min-max property of the (AO)

• Because the auxiliary objective is not generally convex, directly exchanging min-max order is unjustified; CGMT transfers primal convexity to an asymptotically valid reordered auxiliary problem.Lemma A.3 supports using the reordered problem in place of the original auxiliary formulation with high probability in high dimensions.Source: §A.2.4 · pp. 40–41

A.3 Scalarization

• The scalarization keeps vector magnitudes fixed while optimizing directions, exploiting the auxiliary bilinear split and the Fenchel-conjugate representation of the regularizer.These transformations reduce the vector optimization to scalar variables, with the norm of w retained as a key quantity.Source: §A.3 · p. 41
• The auxiliary problem reduces to a convex-concave minimax optimization over four scalar variables.Lemma A.4 states that the scalar and auxiliary formulations have the same optimal cost.Source: §A.3 · p. 42
• The scalar objective is continuous, jointly convex in (α, τg), jointly concave in (β, τh), and permits exchanging infimum and supremum without changing the optimization.These properties provide the final convex minimax form used for subsequent analysis.Source: §A.3 · p. 42

A.4 Convergence Analysis

• Convexity upgrades pointwise convergence of R_n to local uniform convergence, enabling convergence of the sequence’s minimax values to the limiting scalar problem.The proof requires uniform convergence to exchange convergence with minimax optimization.Source: §A.4 · p. 42
• The random objective R_n converges in probability pointwise to a deterministic convex-concave limit D under Assumptions 1(a) and 2.D is convex in (α, τ_g) and concave in (β, τ_h).Source: §A.4 · p. 43
• When the deterministic program has a unique minimizer α*, the limiting objective remains strictly separated outside every neighborhood S_ϵ of α*.For sufficiently large finite K_α and K_β, the separation holds with probability approaching one.Source: §A.4 · p. 43

A.5 Putting all the Pieces Together

• Theorem 3.1 is completed by combining Lemma A.4’s auxiliary optimization representation with Lemma A.5’s convergence and separation conclusions.This identifies the required asymptotic behavior of the primary optimization through the established auxiliary problem.Source: §A.5 · p. 43
• The proof of Theorem 3.1 transfers this separation from the auxiliary optimization to the primary problem, showing its optimal minimizer lies in S in probability.The auxiliary costs converge to constants φ and φ_Scϵ with φ_Scϵ > φ, satisfying Lemma A.3.Source: §A.5 · p. 43

B.1 Proof of Theorem 6.1(iii)

• For Theorem 6.1(iii), assumption (a) yields Φ_Sc > Φ, equivalently w_Φ ∈ S, on a suitable event.The remaining task is to show that this event occurs with probability at least 1 − 4p.Source: §B.1 · p. 43
• Statements (i) and (ii), together with assumptions (c) and (b), establish the event bounds whose combination proves Theorem 6.1(iii) by a union bound.The proof explicitly combines the preceding displays to obtain the claimed probability guarantee.Source: §B.1 · p. 43

B.2 Proof of Corollary 6.1

• Corollary 6.1 follows by applying Theorem 6.1(iii) on two high-probability events, yielding w_Φ(G) ∈ S with probability at least 1 − 4p.The argument holds for every p > 0 and sufficiently large n.Source: §B.2 · p. 44

B.3 Proof of Lemma A.1

• Lemma A.1 begins by restricting the optimizer to the annulus D around norm α and assuming an optimal solution lies outside D with probability approaching one.The set D is defined by α − ε ≤ ∥w∥_2 ≤ α + ε, with α + ε < Kα.Source: §B.3 · p. 44
• If the assumed optimizer belongs to S_w, its optimality for (66) and condition (76) contradict the assumption that it lies outside D.Source: §B.3 · p. 44
• Otherwise, a convex combination with w_B produces w_θ ∈ S_w outside D, and convexity of F makes it optimal for (66), again contradicting (76).This completes the contradiction-based proof of Lemma A.1.Source: §B.3 · p. 44

B.4 Proof of Lemma A.2

• Lemma A.2 reduces to proving equivalence of (67) and (68) by showing the optimizer satisfies u* ∈ S_u, equivalently ∥u*∥_2 ≤ Kβ, with probability approaching one.Source: §B.4 · p. 44
• When subgradients of L are globally bounded, the desired bound on u* follows directly from the first-order optimality relation (78).Source: §B.4 · p. 44
• Otherwise, high-probability bounds on z and the Gaussian matrix spectral norm, together with bounded w* and (79), imply ∥v*∥_2 ≤ C3√n.The matrix norm bound is attributed to [Ver10].Source: §B.4 · p. 44
• The normalization condition on subgradients over ∥v∥_2 ≤ c√n then yields ∥u*∥_2 ≤ C with probability approaching one as n → ∞.Source: §B.4 · p. 44

Boundedness of the optimizer

• The optimal solution w* belongs to S in probability, proving Lemma A.3 via the asymptotic equivalence of the bounded and original problems and the condition α* < Kα.Lemma A.1 and the assumption α* < Kα imply that the original optimizer lies in S with probability tending to one.Source: §B.5 · p. 44

Cost separation

• The argument reduces w* ∈ S to proving that the restricted optimal cost ΦSc strictly exceeds the unrestricted cost Φ with probability approaching one.Here Φ and ΦSc are the optimal costs of the bounded problem without and with the additional constraint w ∈ Sc, respectively.Source: §B.5 · p. 44

CGMT comparison

• The proof relates the primary optimization to an auxiliary optimization through the CGMT, using min-max reformulations and a dual problem to enable the required simplifications.The preferred optimization order is chosen because it supports the simplifications developed in Section A.3; the comparison also uses the min-max inequality [Roc97, Lem. 36.1].Source: §B.5 · pp. 44–45

High-probability separation

• With η := (φSc − φ)/3 > 0, CGMT bounds imply that ΦSc ≥ φSc − η and Φ ≤ φ + η with probability tending to one.The probability bound P(Φ > φ + η) ≤ 2P(φD ≥ φ + η) ≤ 2P(φ ≥ φ + η) vanishes as n → ∞.Source: §B.5 · p. 45

Conclusion

• On the resulting high-probability event, ΦbSc > Φb, so the optimal minimizer satisfies w* ∈ S and the lemma follows.The strict inequality follows from ΦSc − η > φ + η together with the CGMT comparisons and assumption (a).Source: §B.5 · p. 45

Vector-to-scalar reduction

• Optimizing over the directions of u and w reduces the vector problem to scalar norms α and β and a max-min formulation.The reductions use max_{∥u∥2=β} u^Tt = β∥t∥2 and an analogous minimization over the direction of w.Source: §B.6 · p. 45

Min-max interchange

• Convexity-concavity and convex bounded constraint sets justify exchanging the max-min order, while the optimization order between v and s is immaterial.The objective is jointly convex in (α,v) and jointly concave in (β,s), enabling the order swap.Source: §B.6 · p. 46

Moreau-envelope identification

• The final objective is rewritten using Moreau-envelope properties, with the α = 0 branch reducing to −λf(x0).For α > 0, algebra and Moreau-envelope identities yield the transformed summand; for α = 0, conjugacy gives −λf(x0).Source: §B.6 · p. 46

Regularity of (72)

• The scalar objective in (72) is continuous and convex in the relevant variables, with continuity at α → 0 ensured by the Moreau-envelope limit.After minimizing auxiliary variables, the objective remains convex in (α,τg,τh) and concave in β, with the sign of the final term preserving these properties.Source: §B.6 · p. 46

B.7 Proof of Lemma A.5

• Pointwise convergence plus convexity and level-boundedness yields convergence of the random minimax value, while uniqueness of α∗ identifies the asymptotic minimizer.The argument uses uniform convergence on compact subsets and bounds the optimizing β over compact α-sets.Source: §B.7 · pp. 47, 48, 50

B.8 Auxiliary Lemmas

• Lemma B.1 proves convergence of infima for proper convex stochastic functions under pointwise convergence and a level-boundedness condition.Its proof relies on convexity preserving lower bounds and uniform convergence on compact subsets, preventing minimizing sequences from escaping to infinity.Source: §B.7 · p. 48, §B.8 · pp. 51–52

B.7 Proof of Lemma A.5

• The limiting objective D is convex-concave with compact α and β domains, so Sion’s minimax theorem permits arbitrary reordering of the four optimization variables.The τ_g and τ_h optimizations are separable, and the same ordering property holds for the corresponding random optimizations.Source: §B.7 · p. 51

B.8 Auxiliary Lemmas

• Lemma B.2 characterizes level-bounded convex functions by divergence to +∞, while Lemma B.3 transfers saddle-point values between compact domains.These results support the boundedness and minimax steps used in the proof.Source: §B.8 · pp. 52–53
• The function h(α, τ, v) = 1/(2τ)∥αx + z − v∥2_2 is jointly convex in all arguments.This follows from joint convexity in α and v and the perspective-function construction, including the shifted form.Source: §B.8 · p. 53

C.1.1 Proof of Lemma 4.1

• The proof establishes integrability of ℓ(αG + Z) − ℓ(Z) and eℓ(αG + Z; τ) − ℓ(Z) for the stated α and τ ranges.The Moreau-envelope difference is bounded by the envelope-to-loss difference plus the corresponding loss difference, enabling expectation arguments.Source: §C.1.1 · p. 54
• Under Assumption 1(a), the normalized empirical Moreau-envelope expression converges in probability to its expectation by the weak law of large numbers.Integrability is supplied by the preceding bound.Source: §C.1.1 · p. 54
• The function L(α, τ) is jointly convex and continuous, with convexity inherited from the Moreau envelope and continuity following from convexity.The proof also derives the τ→∞ behavior using dominated convergence and monotonicity of the envelope.Source: §C.1.1 · p. 54
• The remaining limiting cases τ→∞ and τ→0+ are justified through dominated convergence, derivative identities, and boundedness arguments under the stated assumptions.These steps include exchanging differentiation and expectation and using standard Moreau-envelope proximal properties.Source: §C.1.1 · pp. 54–55

• Assumption 1(a) holds for F(c, τ) = E[ef(cH + X0; τ) − f(X0)] by the same argument as Lemma 4.1.Source: §C.1.2 · p. 55
• The limit limτ→0+ F(τ, τ) = 0 follows from Moreau-envelope continuity and the Dominated Convergence Theorem.Source: §C.1.2 · p. 55
• The proof establishes limc→∞ c^2/(2τ) − E[ef(cH + X0; τ) − f(X0)] = ∞ using convexity, Jensen’s inequality, and conjugate-function growth.Source: §C.1.2 · p. 56
• When f is finite at a positive argument, f*(x) and the associated Moreau envelope diverge as x→∞; if f is also finite at a negative argument, the same holds as x→−∞.Source: §C.1.2 · p. 56

C.2 Strict Convexity of the Expected Moreau Envelope

• Under condition (8), L is differentiable; under conditions (a) and (b) of Lemma 4.4, L is jointly strictly convex in R>0 × R>0; and if ℓ(x) ≥ ℓ(0) = 0 and ℓ(x+) > 0 for some x+ > 0, F(α) = E[ℓ(αG + Z) − ℓ(Z)] is strictly convex for α > 0.Source: §C.2 · pp. 56–57

C.3 Strict convexity =⇒uniqueness of α∗

• Strict convexity of L and F, together with boundedness and level-boundedness arguments, makes the optimization objective strictly convex in α and yields a unique optimal minimizer α∗.The proof handles boundary minimizers through extensions at τg=0 and excludes β∗=0 using Lemma C.6, after which minimization over α has a unique solution.Source: §C.3 · pp. 60–61

D Useful Properties of Moreau Envelopes

• For a proper, closed, convex function ℓ and τ>0, the Moreau-envelope framework uses the proximal operator proxℓ(χ;τ) defined by minimizing a quadratic term plus ℓ(v).These standard and tailored Moreau-envelope properties support the proofs in Appendix C.Source: D Useful Properties of Moreau Envelopes · p. 62
• The proximal operator proxℓ(χ; τ) is single-valued and continuous, while eℓ(χ; τ) is jointly convex and continuously differentiable in its arguments.The envelope’s gradients are explicitly characterized in the section.Source: D Useful Properties of Moreau Envelopes · p. 62
• For fixed x, eℓ(x; τ) is non-increasing in τ and converges as τ→∞ to min_v ℓ(v).These properties follow from the envelope’s derivative and its decreasing behavior in the smoothing parameter.Source: D Useful Properties of Moreau Envelopes · pp. 62–63
• If 0 ∈ arg min_v ℓ(v), then proxℓ(x; τ) has the same sign as x, satisfies |proxℓ(x; τ)| ≤ |x|, and obeys corresponding subgradient bounds.The result uses proximal-operator monotonicity and monotonicity of the subdifferential.Source: D Useful Properties of Moreau Envelopes · pp. 62, 64
• The envelope is continuous in the vanishing-parameter limit: eℓ(x_n; τ_n) → ℓ(x) when x_n → x and |x_n−x|/τ_n remains suitably controlled.The stated result is cited to [RW09, Thm. 1.25].Source: D Useful Properties of Moreau Envelopes · pp. 62, 64

E.1 On Remark 5.3.4

• Under α→0, τ→0, and ρ→0, equations (156) reduce to consistency conditions that bound β from above and below.Equation (156c) is automatically satisfied in this limit, while (156a) and (156b) yield the remaining constraints.Source: §E.1 · p. 64
• If the maximum right-hand side of (158) over κ exceeds DK, the optimum occurs with α*=0; conditions (159) and (40) ensure such a κ exists.The proof then verifies (159) using the first-order condition for the optimal κ and substitutions from (160).Source: §E.1 · p. 65

E Proofs for Section 5

• When the maximum of the right side of (158) over κ exceeds DK, variables satisfy (36), the optimum has α → 0, τ → 0, and τ αβ → κ, yielding α*=0; concavity implies non-increasing behavior for β > 0.Source: §E.1 · p. 65, §E.2.1 · p. 66, §E.2.2 · p. 66

E.2.1 Satisfying Assumptions 1(a) and 2(b)-(d)

• The appendix checks finite-variance and convergence properties needed for Assumptions 1(a) and 2(b)–(d), including convergence in probability of ∥αg+z∥/√m.The argument also establishes the required convexity and boundedness properties of the associated function.Source: §E.2.1 · p. 65
• Conditions 2(b) and 2(c) follow from the derived bounds on the limiting function, while condition 2(d) requires no further verification because δ is finite.The passage explicitly identifies the bounds used for conditions (b) and (c) and states that finite δ settles (d).Source: §E.2.1 · p. 66

E.2.2 Proving (45)⇔(47)

• For the separable function f of Theorem 4.1, the relevant function is non-increasing in β>0 because its derivative limit at c→0+ is zero and H is concave.The proof uses the representation F(c,τ)=E[e_f(cH+X_0;τ)−f(X_0)] together with independence of h and x_0.Source: §E.2.2 · p. 66