REVIEW 1 major objections 5 minor 38 references
Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper claims that every well-behaved multi-index model is robustly learnable with polynomial-in-dimension sample complexity, backed by a nearly matching statistical-query lower bound.
desk verdict Strong SQ lower-bound paper; the main learner has a gap in the cube-discretization step that the authors need to close. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the iterative subspace-approximation loop of Algorithm 1 (LearnMIMs). At each iteration it holds a subspace $V$, partitions $V$ and the label line $\mathbb{R}$ into cubes and intervals, and inside each cell runs degree-$m$ polynomial regression of the indicator $1(y\in I)$ against the coordinates $x_{V^\perp}$. The gradients of these regression polynomials are aggregated into an influence matrix $U = \sum_{S,I} \mathbb{E}[\nabla p_{S,I}\nabla p_{S,I}^\top \mid x\in S] \Pr[S]$. The progress step, Proposition 2.2, states that if the piecewise-constant hypothesis on $V$ has error above $\tau + \mathrm{OPT} + \epsilon$, then some eigenvector of $U$ with eigenvalue above threshold has non-trivial projection onto the hidden subspace $W$; adding that vector decreases the potential $\sum_i \|w^{(i)}_{V^\perp}\|^2$. On the lower-bound side, the paper develops relativized non-Gaussian component analysis: the conditional distributions of $x_{V^\perp}$ given $(x_V,y)$ are rotated by a random orthogonal map, and because they match $m$ moments of the standard Gaussian, a Fourier--Hermite analysis shows every bounded SQ query is almost unchanged under the rotation, forcing either a query of tolerance $d^{-\Omega(m)}$ or exponentially many queries.
What would settle it
Take a concrete $K$-MIM $f$ with bounded variation and a proper subspace $V$ such that no function of $x_V$ approximates $f$ within $\tau$, and numerically estimate every conditional moment $\mathbb{E}[p(x_U) \mid x_V = z,\, y=f(x)]$ for degree-$\le m$ polynomials $p$. If all such moments are below $\sigma$ on almost all $z$ while the $L^2$ error of the best function of $x_V$ remains above $\tau$, the well-behaved property fails, and the paper's own SQ theorem predicts that any SQ learner requires query tolerance $d^{-\Omega(m)}$. One could settle the matter by simulating an SQ learner on this distribution and checking whether error $\tau + \mathrm{OPT} + \epsilon$ is attainable with $d^{o(m)}$ query cost.
Extended reading notes
Core claim
At the center is Theorem 1.4: for any distribution with standard-Gaussian $x$-marginal and any well-behaved MIM $f$ in the class $\mathcal{F}(K,m,\zeta,\tau,\sigma)$ with $\zeta \ge \mathrm{OPT}+\epsilon$, there is an agnostic PAC learner that draws $d^{O(m)} 2^{\mathrm{poly}(K/(\epsilon\sigma))}$ samples, runs in polynomial time, and returns $h$ with $\mathrm{err}_D(h) \le \tau + \mathrm{OPT} + \epsilon$. The class is defined so that for every subspace $V$, either $f$ is already $\tau$-close to a function of the projection $x_V$, or the joint distribution of $(x,y)$ has a degree-$m$ distinguishing moment in the directions of the hidden subspace outside $V$. The discovery is that this local, moment-based condition is both sufficient for a $d^{O(m)}$-sample robust learner and, in the SQ model, essentially necessary: if some subspace $V$ has no such distinguishing moments, any SQ learner requires roughly $d^{\Omega(m)}$ query complexity. The paper then proves the well-behaved condition for concrete classes, most notably positive-homogeneous $L$-Lipschitz $K$-MIMs, obtaining a learner using $d^2 2^{O(K^3 L^2/\epsilon^2)}$ samples and, as a corollary, a ReLU-network learner with complexity independent of the network size.
Load-bearing premise
Everything hinges on condition (2b) of Definition 1.3: for every subspace $V$ reached, either the target is already $\tau$-close to a function of the projection $x_V$, or the conditional law of $x$ in the missing directions, given $x_V$ and the label, has a degree-$m$ moment at least $\sigma$ on a non-trivial fraction of inputs; if this fails for some $V$, no new direction is found and the argument stalls.
Editorial extensions
If this is right
- Agnostic robust regression for well-behaved MIMs runs in $d^{O(m)} 2^{\mathrm{poly}(K/(\epsilon\sigma))}$ samples and returns error $\tau + \mathrm{OPT} + \epsilon$.
- In the realizable and independent-noise settings, the same learner uses $d^{O(m)} 2^{\mathrm{poly}(K)} (1/\epsilon)^{O(K)}$ samples, with exponential dependence only on $K$.
- If some subspace has no degree-$m$ distinguishing moments, any SQ learner for the corresponding MIM class requires queries of accuracy $d^{-\Omega(m)}$ or exponentially many queries, so the upper bound is qualitatively tight in $m$.
- Positive-homogeneous $L$-Lipschitz $K$-MIMs are learnable with $\mathrm{poly}(d) 2^{\mathrm{poly}(KL/\epsilon)}$ samples, the first such guarantee for this nonparametric class.
- As a direct corollary, Lipschitz homogeneous ReLU networks are PAC learnable with complexity independent of the network size $S$, removing the exponential dependence in $S$ of prior work.
Reading between the lines
- The guarantee is for square-loss PAC learning, not parameter recovery: two different hidden subspaces that induce the same labels are not separated, so the result leaves open whether this conditional-moment search can be sharpened into recovery guarantees for identifiable models.
- For the special case $m=2$, the paper's own remark suggests that replacing polynomial regression by covariance estimation in operator norm could reduce the $d^2$ sample dependence to $O(d)$; validating that refinement would make the positive-homogeneous MIM learner nearly linear in dimension.
- The SQ threshold being exactly the absence of distinguishing moments suggests that any algorithm that succeeds where this one fails would have to operate outside the statistical-query model, since the lower bound applies to all SQ learners for such classes.
- Because the returned hypothesis is piecewise constant on the recovered subspace, the ReLU-network corollary does not assert that gradient-based training finds the network; it leaves open whether optimization over networks achieves the same sample bound.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies PAC learning of real-valued multi-index models (MIMs) under Gaussian marginals with square loss, in the presence of adversarial label noise. The main algorithmic result, Theorem 1.4, claims a learner for a class of 'well-behaved' MIMs with sample complexity d^{O(m)} 2^{poly(K/(εσ))} and error τ + OPT + ε. The appendices develop an iterative subspace-finding algorithm (LearnMIMs / Algorithm 3), prove a progress lemma (Proposition D.9), and derive applications to positive-homogeneous Lipschitz MIMs, including homogeneous ReLU networks, and to low-rank polynomials. The paper also proves an SQ lower bound, Theorem 1.10 / Theorem C.19, based on a new relativized non-Gaussian component analysis (RNGCA) lower bound that avoids chi-squared finiteness assumptions.
Significance. If the main claims are correct, this is a substantial contribution: it would give the first polynomial-in-dimension learner for Lipschitz homogeneous K-MIMs with complexity independent of network width and depth, and a nearly matching SQ lower bound of d^{Ω(m)}. The SQ lower bound part appears technically substantial and self-contained: it extends [DKRS23] to a relativized setting without chi-squared assumptions, using truncation, reweighting, and Hermite/Fourier analysis. The applications are also well motivated and the structural lemmas for homogeneous Lipschitz functions (Lemma D.25 and Claim D.26) are plausible and interesting. However, the central algorithmic progress lemma contains a nontrivial gap in the cube-discretization argument, and the formal theorem statements do not match the advertised error guarantee. These issues affect the main algorithmic claim and require significant repair.
major comments (1)
- [Appendix D.1.3, Theorem D.5 versus Theorem 1.4] The error guarantee stated in the introduction and abstract, err_D(h) ≤ τ + OPT + ε, is not what is proved. Theorem D.5 establishes only err_D(h) ≤ (√τ + ε + √OPT)^2 + ε = τ + OPT + 2√(τ OPT) + 2(√τ+√OPT)ε + ε^2 + ε. When OPT is large relative to τ and ε, the extra cross terms can exceed ε by an unbounded factor, so the advertised bound does not follow by a constant rescaling of ε. The same squared-sum form appears in Proposition 2.2 and Proposition D.9. This is a load-bearing discrepancy between the paper's central claim and its formal algorithmic results; the statements and proof need to be aligned, or the stronger bound needs to be proved.
minor comments (5)
- [Appendix D.3.1, Proof of Theorem D.22] The proof says 'Fact D.32 and lemmas D.27 and D.28 together imply...' but Fact D.32 is stated later in Section D.3.2 for the class of low-rank polynomials P^α_{K,m}, not for the Lipschitz homogeneous class H_{K,L}. The correct structural ingredient for H_{K,L} appears to be Lemma D.25. Please correct the reference.
- [Appendix D.1.2, Lemma D.7] In the displayed chain after 'by expanding the square', the term 'E[(f^2(x)-y)^2]' appears to be a typo for 'E[(f(x)-y)^2]'.
- [Appendix D.1.2, Lemma D.6] The final sentence of the proof states 'Ex∼Nd[(f(x)−hS(x))2] = τ + ǫ' but the preceding argument only supports an inequality of the form '≤ τ + O(ǫ)'.
- [Appendix C.1.1, Definition C.12] The notation 'Bm(B)' in Definition C.12 should be 'B_k(B)' or similar; as written it is confusing.
- [Appendix C.1.2, Proof of Proposition C.7] The final line contains a stray bracket: 'completes the proof of Proposition C.7]' should be 'completes the proof of Proposition C.7.'
Circularity Check
No significant circularity: the main theorem is a conditional guarantee whose defining condition is independently verified for the applications, and the SQ lower bound is a genuine converse rather than a restatement.
full rationale
The paper's central claims are conditional theorems, not derivations that collapse into their own inputs. Theorem 1.4 holds for functions in F(K, m, zeta, tau, sigma) as defined by Definition 1.3; that 'well-behaved' condition is an explicit assumption of the theorem, and the algorithm's guarantees (err_D(h) <= tau + OPT + eps) are proven from it in Appendix D rather than being equivalent to it by construction. The lower bound (Theorem 1.10 / C.19) is arguably the opposite of circular: it shows that when the distinguishing-moment condition fails for some subspace, no SQ learner can succeed, so the upper-bound hypothesis is shown necessary up to SQ equivalence. The applications (positive-homogeneous Lipschitz MIMs, low-rank polynomials) do not import the target result: they supply self-contained structural lemmas (D.25, D.28, D.32) verifying the well-behaved condition, with the ReLU-network corollary improving on [CKM22] by removing the S-dependence. Self-citations are present but not load-bearing: [DIKZ25] is cited as the discrete analogue whose approach is followed, yet the real-valued adaptation (definition D.1, cube-interval discretization, L2-loss analysis) is developed in this paper with its own proofs; [DKRS23] is cited for Fourier-analytic facts (Facts C.9, C.11, C.16, C.17) whose stated assumptions (distribution bounds, Hermite tensor norms) do not include the target learning result, and the paper explicitly states Theorem 3.3 cannot be derived from [DKRS23] as a black-box and proves it in Appendix C.1. No parameter is fitted to data and then reported as a prediction; the algorithm is a standard sample-based PAC learner. The skeptical concern about Lemma D.7 (the independence claim 'since y' is independent of z_V when conditioned on its cube S_{z_V}') is a potential correctness gap in a proof step, not a circularity: it alleges that a probabilistic assertion is unjustified, not that a prediction is equivalent to its inputs by definition. Under the hard rules, correctness concerns of that kind fall outside the circularity rubric, so they do not raise the score. Overall the derivation chain is self-contained against external benchmarks, and the self-citations play a supporting role only.
Assumptions & free parameters
assumptions (6)
- domain assumption Well-Behaved MIM condition (Definition 1.3 / D.1): for any subspace V and any noise level zeta, either V approximates W within tau or there exist degree-m conditional distinguishing moments of strength sigma.
- domain assumption Bounded variation and bounded norm: E[||grad f||^2] <= L, E[f^2] <= M, and f is rho-close to a B-bounded function.
- domain assumption Input marginal is standard Gaussian and loss is squared error.
- domain assumption For the SQ lower bound, the concept class C is rotationally invariant and the hard distribution matches degree-m moments relative to a subspace.
- domain assumption Technical condition in lower bound: labels have bounded contribution from extreme values (E[y^2 1(|y|>B)] <= delta).
- standard math Standard mathematical background: Hermite tensor orthogonality, Gaussian concentration, hypercontractivity, Carbery-Wright anti-concentration, and the decomposition lemma of [DKRS23].
Cite this review
Pith. "Pith review of Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models." pith.science (2026). https://pith.science/paper/DXZUKRFM
@misc{pith2026250521475,
author = {Pith},
title = {Pith review of: Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models},
year = {2026},
howpublished = {\url{https://pith.science/paper/DXZUKRFM}},
note = {Machine review of arXiv:2505.21475}
}
abstract
We study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution. A $K$-MIM is a function $f:\mathbb{R}^d\to \mathbb{R}$ that depends only on the projection of its input onto a $K$-dimensional subspace. We give a general algorithm for PAC learning a broad class of MIMs with respect to the square loss, even in the presence of adversarial label noise. Moreover, we establish a nearly matching Statistical Query (SQ) lower bound, providing evidence that the complexity of our algorithm is qualitatively optimal as a function of the dimension. Specifically, we consider the class of bounded variation MIMs with the property that degree at most $m$ distinguishing moments exist with respect to projections onto any subspace. In the presence of adversarial label noise, the complexity of our learning algorithm is $d^{O(m)}2^{\mathrm{poly}(K/\epsilon)}$. For the realizable and independent noise settings, our algorithm incurs complexity $d^{O(m)}2^{\mathrm{poly}(K)}(1/\epsilon)^{O(K)}$. To complement our upper bound, we show that if for some subspace degree-$m$ distinguishing moments do not exist, then any SQ learner for the corresponding class of MIMs requires complexity $d^{\Omega(m)}$. As an application, we give the first efficient learner for the class of positive-homogeneous $L$-Lipschitz $K$-MIMs. The resulting algorithm has complexity $\mathrm{poly}(d) 2^{\mathrm{poly}(KL/\epsilon)}$. This gives a new PAC learning algorithm for Lipschitz homogeneous ReLU networks with complexity independent of the network size, removing the exponential dependence incurred in prior work.
Reference graph
Works this paper leans on
-
[1]
the joint distribution of (U⊤z′, y′) is A; and
-
[2]
We next give the generalization of Definition 3.2
z′ U ⊥ is distributed according toN (0, Π U ⊥ ) independent of the value of (U⊤z′, y′), where U is the column space of U andN (0, Π U ⊥ ) is the standard Gaussian projected onto U ⊥. We next give the generalization of Definition 3.2. Definition C.2 (Hypothesis Testing V ersion of RNGCA; Generalization of De finition 3.2 ) . Let d > k ≥ 1 be integers. For a j...
-
[3]
the function f (·, y) is a polynomial of degree at most m for any y∈Y ; and
-
[4]
‖f‖Nk⊗Ay≤ 1, where Ay is the y-marginal of A andNk⊗ Ay is the product distribution ofNk and Ay, it holds that ⏐ ⏐E(x,y)∼A[f (x, y)]− E(x,y)∼Nk⊗Ay [f (x, y)] ⏐ ⏐≤ ν . With this context, we are ready to state our main SQ lower boun d theorem for RNGCA. Roughly speaking, we show that for any regular distribution A that satisfies Condition C.5, there is an SQ ...
-
[5]
dTV(A, A′) = O ( 2m/2 √ Γ( m+k/2) Γ( k/2) ) B−m; and 21
-
[6]
F or any i∈ Z+, ‖ ‖ ‖Ex∼A′ x|y [H(x)] ‖ ‖ ‖ A′ y = 2O(i) ( 2m/2 √ Γ( m+k/2) Γ( k/2) ) Bi−m + ( 1 + O ( 2m/2 √ Γ( m+k/2) Γ( k/2) ) B−m ) ν, i < m ; 2O(i) ( 2m/2 √ Γ( m+k/2) Γ( k/2) ) Bi−m, i ≥ m . Proof of Lemma C.13. We first bound dTV(A, A′). For convenience of the analysis, we define the distribution ¯A as the distribution of (x, y)∼ A c...
-
[7]
The distribution D ν -matches degree-m moments relative to the subspace V× R, where the extra R contains the label
-
[8]
Any function h : Rd→ R has E(x,y)∼D[(h(xV )− y)2]≥ τ ; and
Show all 38 references
-
[9]
There exist B, δ∈ R+ such that Ey[y21(|y| > B )]≤ δ. Then, for m, K ≤ dλ for some λ∈ (0, 1), dim(V )≤ d/2, c∈ (0, (1− λ)/4) and d at least a sufficiently large constant depending on c, the following holds: any SQ algorithm that learns C within error τ− 7δ− 3ζB 2 given OPT≤ inf ...
-
[10]
There exists an f∈C and a subspace V ⊆ Rd such that (a) the joint distribution of (x, f(x)) with x∼N d matches degree-m moments relative to the subspace V (with the standard Gaussian projected onto V ⊥); and (b) for any function h : V → R, Ex∼Nd [(f (x)− h(xV ))2]≥ τ
-
[11]
There exists an f∈C with Generative exponent strictly greater than m such that the variance of f (x) with x∼N d is at least τ . Proof. Notice that it suffices for us to fix a f∈ C and prove the equivalence. For convenience of analysis, let w∈ Sd−1 be the relevent direction of f ...
-
[12]
There exists a subspace V ⊆ Rd such that (a) D matches degree- m moments relative to the subspace V (with the standard Gaussian projected onto V ⊥); and (b) for any function h : V → R, E(x,y)∼D[(y− h(xV ))2]≥ τ
-
[13]
The direction that Condition 2 implies Condition 1 is immedi ate
f has Generative exponent strictly greater than m and the variance of f (x) with x∼N d is at least τ . The direction that Condition 2 implies Condition 1 is immedi ate. We simply take V = {0}. Then Condition 1(b) follows directly from the fact that inf c∈R E(t,y)∼A[(y− c)2] ≥ ...
-
[14]
If W⊆ V , then taking h(xV ) = fxW is well-defined and we have Ex∼Nd [(f (x)−h(xV ))2] = 0 , which implies that Condition 1 (b) does not hold
-
[15]
Let u = wV ⊥/‖wV ⊥‖2 and w′ = uW /‖uW‖2
If W ⁄⊆V , we assume that Condition 1 (b) holds for the purpose of contr adiction. Let u = wV ⊥/‖wV ⊥‖2 and w′ = uW /‖uW‖2. We now consider the polynomial p : V ⊥→ R defined as p(xV ⊥) = hk(⟨u, x⟩). Notice that Ex∼Dx|y=y0 [p(xV ⊥ )] =Ex∼Dx|y=y0 [hk(⟨u, x⟩)] =Ex0∼N (0,Π V ) [Ex∼...
-
[16]
There exists a K-dimensional subspace W of Rd such that f (x) = f (xW ) for all x∈ Rd
-
[17]
f is continuous everywhere and continuously differentiable almost everywhere, with Ex∼Nd[‖∇f (x)‖2]≤ L
-
[18]
f has bounded norm Ex∼Nd [f 2(x)]≤ M and is ρ-close to a B-bounded function, i.e., there exists fB : Rd→ [−B, B] such that Ex∼Nd [(f (x)− fB(x))2]≤ ρ. 7
-
[19]
For any subspace V of Rd and any distribution D on Rd× R with Dx = Nd such that E(x,y)∼D[(f (x)− y)2]≤ ζ the following hold: (a) either Ex∼Nd[(f (x)− g(xV ))2]≤ τ for some g : V → R. (b) or with probability α over z ∼ Nd independent of x there exists a degree at most m, zero-m...
-
[20]
Let T be a sufficiently large constant-degree polynomial in 1/α, 1/ǫ, 1/σ, K, L, M, B, 2m, and let C be a sufficiently large universal constant
-
[21]
Let L1←∅ , N← dCm 2T C log(1/δ), ǫ1← 1/T, η← 1/T, ǫ2← ǫ2/(CM ), λ← (aσǫ/(M BK2m))C
-
[22]
, T (a) Draw a set St of N i.i.d
For t = 1, . . . , T (a) Draw a set St of N i.i.d. samples from D. (b)Et← Algorithm 4(η, ǫ1, ǫ2, B, λ, span(Lt), St, θ). (c) Lt+1← Lt∪E t
-
[25]
Algorithm 3: Robustly Learning Well-Behaved MIMs FindDirection: Estimating a relevant direction Input: η, ǫ1, ǫ2, B, λ>0, a subspace V⊆ Rd, samples{(x(i), yi)}N i=1 from a distr
Return hS. Algorithm 3: Robustly Learning Well-Behaved MIMs FindDirection: Estimating a relevant direction Input: η, ǫ1, ǫ2, B, λ>0, a subspace V⊆ Rd, samples{(x(i), yi)}N i=1 from a distr. D over Rd× R. Output: A set of unit vectorsE
-
[26]
Construct an (ǫ1, ǫ2, B)-approximating discretization of V× R, (S,I) (see Definition D.3)
-
[27]
For each S∈S and each I∈I , find a polynomial pS,I(x) such that E(x,y)∼D[(1(y∈ I)− pS,I(xV ⊥))2| x∈ S] ≤ min p′∈Pm E(x,y)∼D[(1(y∈ I)− p′(xV ⊥ ))2| x∈ S] + η2
-
[28]
Let ˆU =∑ S∈S,I∈I Ex∼Dx[∇pS,I(xV ⊥)∇pS,I (xV ⊥)⊤| x∈ S]Pr(x,y)∼ ˆD[S]
-
[29]
Algorithm 4: Estimating a relevant direction Lemma D.6 (Piecewise constant approximation suffices)
Return the set E of unit eigenvectors of ˆU with corresponding eigenvalues at least λ. Algorithm 4: Estimating a relevant direction Lemma D.6 (Piecewise constant approximation suffices) . Let ǫ, L, M, τ ∈ R+, k, d∈ Z+ with τ ≤ M and c > 0 be a sufficiently small absolute constan...
-
[30]
There exists a subspace W⊆ Rd of dimension at most K such that y depends on x only through the projection onto W , i.e., Pr(x,y)∼D[y = z| x = u] = Pr(x,y)∼D[y = z| xW = uW ], for all u∈ Rd, z∈ R
-
[31]
The label has bounded variance, i.e., E(x,y)∼D[y2]≤ M
-
[32]
For any subspace V ⊆ Rd with dim(V )≤ K and for any (η1, η2)-approximating discretization (S,I) with η1≤ ǫ1, η2≤ ǫ2 (a) either E(x,y)∼D[(hS (xV )− y)2]≤ τ , where hS denotes the piecewise constant approxima- tion of D according to Definition D.4. (b) or there is a subset T ⊆ Ss...
-
[33]
Let C be a sufficiently large universal constant
-
[34]
Let L1 =∅, N← (dm)Cm (mK/(ǫ1ǫ2α))CK (M/(ǫσ))C log(1/δ)
-
[35]
, T (a) Draw a set St of N i.i.d
For t = 1, . . . , T (a) Draw a set St of N i.i.d. samples from D. (b)Et← Algorithm 4((K|I|/(σǫα))C , ǫ1/K 4, ǫ2, 1/ǫ2 2, (σα/K )C , span(Lt), St, θ). (c) Construct Lt+1 by adding one vector ofEt to Lt
-
[36]
Construct S, an ǫ1-approximating partition with respect to span(Lt) (see Definition D.2)
-
[37]
samples from D and construct the piecewise constant function hS as follows: For each S∈S , assign the median of O(log(1/δ)) means of the labels from the samples falling in S
Draw N i.i.d. samples from D and construct the piecewise constant function hS as follows: For each S∈S , assign the median of O(log(1/δ)) means of the labels from the samples falling in S
-
[38]
Algorithm 5: Learning Well-Behaved MIM distributions
Return hS. Algorithm 5: Learning Well-Behaved MIM distributions. approximation of D, with respect to S. There exists N = ( dm)O(m)(K/ǫ1)O(k) log(|I|/δ)/ηO(1) such that if E(x,y)∼D[(hS(x)− y)2] > τ + ǫ, then Algorithm 4, when given N i.i.d. samples from D and parameters η≤ (ǫσǫ...
-
[39]
F or any t > 0, it holds e−t2/2/4≤ Prz∼N [z > t ]≤ e−t2/2/2
-
[40]
Fact E.3 (Gaussian Annulus Theorem see e.g., [V er18])
F or any a, b∈ R with a≤ b, it holds Prz∼N [a≤ z≤ b]≤ (b− a)/ √ 2π. Fact E.3 (Gaussian Annulus Theorem see e.g., [V er18]). If x∼N d, with probability at least 1− τ we have that ⏐ ⏐ ⏐‖x‖2− d ⏐ ⏐ ⏐ ≲ log 1 τ + √ d log 1 τ . Fact E.4 (Gaussian Hypercontractivity; see e.g., [O’D1...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.