Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data
Authors: Youssef Chaabouni
David Gamarnik
Venue: ICLR 2026 Poster (2026)
Keywords: High-dimensional Statistics
Machine learning theory
sparse regression
Lasso
heterogeneous noise
LLM annotations
Primary area: learning theory
TL;DR: Sufficient conditions for sparse linear regression when observations come from mixed-quality samples.

Abstract: We study sparse recovery when observations come from mixed-quality sources: a small collection of high-quality measurements with small noise variance and a larger collection of lower-quality measurements with higher variance. For this heterogeneous-noise setting, we establish sample-size conditions for information-theoretic and algorithmic recovery. On the information-theoretic side, we show that it is sufficient for $(n_1, n_2)$ to satisfy a linear trade-off defining the _Price of Quality_: the number of low-quality samples needed to replace one high-quality sample. In the agnostic setting, where the decoder is completely agnostic to the quality of the data, it is uniformly bounded, and in particular one high-quality sample is never worth more than two low-quality samples for this sufficient condition to hold. In the informed setting, where the decoder is informed of per-sample variances, the price of quality can grow arbitrarily large. On the algorithmic side, we analyze the LASSO in the agnostic setting and show that the recovery threshold matches the homogeneous-noise case and only depends on the average noise level, revealing a striking robustness of computational recovery to data heterogeneity. Together, these results give the first conditions for sparse recovery with mixed-quality data and expose a fundamental difference between how the information-theoretic and algorithmic thresholds adapt to changes in data quality.

Published as a conference paper at ICLR 2026
PRICE OF QUALITY: SUFFICIENT CONDITIONS FOR SPARSE RECOVERY USING MIXED-QUALITY DATA
Youssef Chaabouni
David Gamarnik
Operations Research Center
Operations Research Center
Massachusetts Institute of Technology Cambridge, MA 02139, USA youss 4 4emit. edu
Massachusetts Institute of Technology Cambridge, MA 02139, USA gama rn iemii. edu
ABSTRACT
We study sparse recovery when observations come from mixed-quality sources: small collection of high-quality measurements with small noise variance and a larger collection of lower-quality measurements with higher variance. For this heterogeneous-noise setting, we establish sample-size conditions for information- theoretic and algorithmic recovery. On the Informationntheoreel side, we show that it is sufficient for (21, to satisfy a linear trade-off defining the Price of Quality: the number of low-quality samples needed to replace high-quality sample. In the agnostic setting, where the decoder is completely agnostic to the high-quality
quality of the data, it is uniformly bounded, and in particular sample is never worth more than two low-quality samples for this sufficient con- dition to hold. In the informed setting, where the decoder informed of per- sample variances, the price of quality can grow arbitrarily large. On the algorith- mic side, we analyze the LASSO in the agnostic setting and show that the recovery threshold matches the homogeneous noise case and only depends on the average noise level, revealing a striking robustness of computational recovery data het- erogeneity. Together, these results give the first conditions for sparse recovery with mixed-quality data and expose a fundamental difference between how the informatiion-thorrde and algorithmic thresholds adapt changes in data quality.
INTRODUCTION
1.1 OVERVIEW AND PREVIOUS WORK
1.1.1 SPARSE RECOVERY
Sparse recovery is a central problem in high-dimensional statistics and machine learning. Its ap- plications include compressive sensing (Foucart al., 2013 Candès al. 2006 Donoho 2006).
signal denoising (Chen et al., 2001) sparse regression (Miller (002), data-stream algorithms (Cor-
mode & Hadjieleftheriou [009 Indyk 2007 Muthukrishnan et al. 2005). and combinatorial group
testing (Du & Hwang] 1999). Other applications range from medical imaging to communications
and compression (Foucart et al. 2013 Chap. 1).
We formulate the problem as follows. A high-dimensional signal 8 R (also called model or ground truth), unknown but a-priori s-sparse, is transmitted through noisy channel that projects onto collection of n random vectors {a: (1=)ve(m) in R". This is expressed as:
Y XB=
where X = (I1...., "n)) is called measurements. design or features; Y observations, annotations or labels; and Z noise. Specifically, we consider the setting of additive Gaussian noise, which is standard in the compressive sensing and sparse linear regression literatures. On the other end of the channel, a decoder who observes (X, Y) is interested recovering the support of the original signal 8* i.e. the subset S* {i [p] 3 f 0} [p), known a-priori to be of cardinality s. How many observations n (as a function of p and s) does the decoder need to recover the support of the signal the dimension of the problem grows infinity?

---

Published as a conference paper at ICLR 2026
Previous works have shown that the sparse recovery problem exhibits two phase transitions two thresholds, one information- theoretic and one algorithmic:
2s log (p/s) and nALG = 2x log (p - 5) +
TINF
log 8
leading to three regimes:
TINF: Signal support recovery is informationn-heoreiin theoretically impossible. (Reeves al. 2019
VINF < < PALG: The maximum likelihood estimator (MLE) recovers S*. However, it is believed that no algorithm can do in polynomial time since the problem exhibits an Overlap Gap Property (OGP) (Gamarnik & Zadik (022). structural property of the solution space known to often imply the failure of tractable algorithms to find optimal solutions.
n > nALG: The éi-regularized least-squares estimator (also known as the LASSO Tibssiranii 1996)) recovers S* (Wainwright 2009).
Of particular interest is the signal-to-noise ratio (SNR), known to be an important quantity for characterizing the difficulty of sparse recovery problems (Wang et al. 2010; Reeves et al. 2019 Chaabouni & Gamarnik). It's defined as follows:
EJ 3 SNR
B1 2
1.1.2 MIXED QUALITY DATA
A recent body of work has explored how low-quality data, e.g. labeled by LLM weak annotator (Ratner et al.) 2017; Frénay & Verleysen 2013). should be combined with fewer but higher-quality data, e.g. labeled by humans experts. prediction and inference tasks (Gligorié al. 2024| Li
ct al. 2023 Zhang et al. 2023 Egami et al. 2023).
In this paper, we formalize the mixed-quality data setting for sparse signal recovery: the decoder has access to пı noisy projections of the signal 8 with small noise level of >> 0 that we denote {(y,, == and call high-quality data. addition, the decoder also observes larger set of no > n1 noisy projections of the same signal 8*, but with higher noise level o of, that we denote {1,, 2; ==n and call low-quality data. We distinguish two settings:
Agnostic setting: The decoder lacks access to observation-level noise variances and treats all measurements if drawn from single homogeneous model. This occurs when heterogeneous data sources lose provenance: for example in web-scale text corpora (Ratner et al. 2017 Frénay & Verleysen 2013) or citizen-science campaigns lacking sensor calibration (Silvertown) 2009). The decoder simply applies standard sparse-recovese methods without noise estimation or reweighting.
Informed setting: where the decoder has access to the per-sample noise variance of the data. This regime captures situations where provenance information accompanies each observation, so the decoder knows which measurements are high- or low-quality. Examples include multi-site clinical trials or sensor networks that log calibration statistics (Loh & Wainwright, 201T]] Delaigle al., 2008), and medical medical-imaging datasets with per-rater confidence scores (Rajpurkar et al. 2018).
1.2
OUR WORK
In this paper, we consider the sparse recovery problem described above ( Specifically, we study the setting where the measurements are drawn i.i.d. from standard normal Gaussian distribution, and the noise is unbiased and drawn independently from Gaussian distributions of variance of for the high-quality samples and of > of for the low low-quality ones:
(Xi) iid. N (0,1) and Z EW; where = =011
0 o N o2Ino
(4) Although much of the literature on sparse recovery in the homogeneous noise setting assumes con- stant noise level ² don't assume in this work that of and of are constant. In fact, the reason
2

---

Published as a conference paper at ICLR 2026
previous work can assume constant noise variance without loss of generality is that the model I could be scaled down by a when the noise is homogeneous with variance o² to make it constant. However, it is not the anymore when the noise is heterogeneous. While our results naturally extend to sub-Gaussian errors, the sufficient conditions derived herein are not universal for general additive noise distributions.
The assumptions we impose (Gaussian design, exact sparsity, and additive noise) are standard in the sparse recovery literature (e.g. WWanwwrigt (2009); Reeves et al. (2019); Gamarnik & Zadik (2022)) ) and are adopted here to isolate the effect of heterogeneous noise while retaining the canonical struc- ture of the recovery problem.
Our analysis allows for arbitrary scalings of of and 0 with respect to p and s. Since data come from two different sources with different scalings, we define in addition ( two signal-to-noise ratios: SNR, for high-quality observations and SNR₂ corresponding to low-quality observations.
We are interested in the two following questions:
Sampling complexity of sparse recovery:
How large do the sample sizes (21, n2) need to be for the decoder to be able, information-thhorrtiiclly to recover the support of the signal?
Algorithmic recovery: How large do the sample sizes (72, n22) need to be for the decoder to be able recover the support of the signal using polynomial algorithm?
We summarize below our findings on each of these questions in the agnostic and informed settings.
1.2.1 SAMPLING COMPLEXITY OF SPARSE RECOVERY
In the first part of our work (section we focus on the question of sampling complexity. For simplicity, we assume the signal is binary, i.e. 8* E {0, 1]." Note that in this case, recovering the support is equivalent to recovering the signal. This assumption is very common in the literature (Aeron et al. 2010, Reeves et al.) 2019 Gamarnik & Zadik 2022, Chaabouni & Gamarnik). Intu- itively, detecting a component of size is at least as hard as detecting a stronger component, so the resulting thresholds representative of signals with non-zero entries bounded away from zero. We discuss this assumption in more detail in Remark(3.]
Our main results, Theorem || for the agnostic setting and Theorem 2 for the informed one, each provide a sufficient condition 16 on the sample sizes (2) for support recovery. In both results, the condition has the form 0 + 02222 > n²" for some coefficients 02 0 depending on of, oz and 8, and having different expressions in the agnostic and informed settings. In par- ticular, note that if (n1,712) verify this condition (i.e. are together large enough), then do (n1 - n2 + a1/a2). In this sense, we say that one unit of high-quality data is worth:
(s.
01
(5)
a2
units of low-quality data for the sufficient condition to hold. We label y the Price of Quality and study its behavior in the agnostic and informed settings and for different regimes of SNR; and SNR2. In the agnostic setting, it is uniformly bounded. In particular, under our sufficient condition, one high-quality sample is never worth more than two low-quality samples [4) for the sufficient condition. In the informed setting, where the decoder is informed of per-sample variances, the price of quality goes to infinity the low SNR, & high SNR, regime (20). and can be arbitrarily large in both low and high SNR regimes
19 21
1.2.2 ALGORITIMIC RECOVERY
In the second part of our work (section 4) we focus on the question of algorithmic recovery. Unlike for sampling complexity, we don't assume that the signal is binary, but still require non-zero com- ponents to be bounded away from zero, i.e. there exists p > O such that min;es- 1.3.1 p. This is standard in the literature (Aeron et al. 2010; Ndaoud & Tsybakov 2020 Wang et al. 2010) since can't 't' hope detect non-zero signal components if they can have arbitrarily small amplitude.
Specifically, we study the question of signed support recovery, that is, recovering not only the indices of the non-zero components of the signal but also their sign (+ or -). This is usual in the algorithmic
support
3

---

Published as a conference paper at ICLR 2026
sparse recovery literature (Wainwright 2009 Wang et al. 2010: Omidiran & Wainwright 2008), as it follows naturally from the standard proof techniques.
Our main result, Theorem 3 provides necessary and sufficient conditions for the Ei-reuularized least- squares estimator (known as the LASSO) to recover the signed support of 3 in the agnostic setting. Our result reveals that the problem behaves like the homogeneous-noke setting (Wainwright) 2009) with a homogeneous noise level equal to the average noise level of Z:
Rioi + n20
(6)
avg
n
In particular, the sample size conditions condition on the LASSO regularization parameter 28 only depends of and 0 through o and
26
27
do not depend on the noise levels of.03. The
the same as the one for homogeneous noise The (see equation (28) in Wainwright (2009) We
further provide necessary and sufficient condition on noise scaling (Proposition 4.1)
This shows that, unlike in sampling complexity. high-quality and low-quality data contribute equally to the sample size condition under which the LASSO recovers the support of the signal.
Although we don't address algorithmic recovery in the informed setting, we briefly discuss it in Remark 4.2 where we discuss why the proof of aeceorem@canne be easily extended to the informed case.
1.3 CONTRIBUTIONS, OUTLINE AND NOTATIONS
To the best of our knowledge, this paper is the first to:
Provide a sufficient condition for sparse recovery the heterogeneous noise case, and quantify the trade-off between high-quality and low-quality data in the agnostic and informed settings.
Extend necessary and sufficient conditions for LASSO sparse recovery to the heterogencous- noise, agnostic setting and show that high-quality and low-quality data contribute equally to reaching the algorithmic threshold.
We organize the rest of the paper as follows. Section 2 ies the sampling complexity of sparse recovery under heterogeneous noise. Section algorithmic recovery using the LASSO. Section concludes and outlines directions for future work.
introduces the problem setup. Section 3 stud-
4 investigates
Throughout this document, we will use the following notations:
We say that f (z) 2 g (I) as x +
(-00, +00) if and only if f (x) = g() (1 (1+
We denote by h (-) the binary entropy: h (æ)) - log r - (1 log (1 x). 2 1).
We call lo-orm the number of non-zero coordinates of RRd that is |>||| := Σ 1 (x; + 40)
We use uppercase letters (e.g. X, Y, Z) to indicate random quantities, and lowercase letters (e.g. 3) denote deterministic parameters.
2 PRELIMINARIES
The problem of sparse signal recovery is defined above ( The decoder a-priori knows that 3t is s-sparse and belongs to known set A RP. The design and noise are random with
(Xw) iid. N (0, 1) and Z == EW with Σ and W defined as in (4) and n1 + n2 = n.
2
We define Z = -Z,.... ........... Zmy yTH and Z (Zns+1 ...... ..........
Za that Z
The signal-
7.2
to-noise ratio
3
writes:
SNR X 2
ns
EE 2
oo + n20
2
4

---

Published as a conference paper at ICLR 2026
where L.g denotes the average noise level 66. In addition, define the high- SNR and the low-quality SNR respectively by:
SNR1 = E [1s xx.3*
m1 im
12
E
xx 3
n2
8 of
i=
SNR, =
E
E E|ZZ11
02
In particular, we always have SNR2 < 1 which reveals three regimes of interest:
High SNR: when 1NR1, 2 + +oo, or equivalently o2 = os))
Low S2Rg, High SNR;: SNR₂ + 0, SNR; - too or equivalently ož = w of o
Low SNR: when i SNR2 - O, or equivalently of = w (s).
SAMPLING COMPLEXITY OF SPARSE RECOVERY
In this section, we are interested in determining whether it is possible, information-theerrtiiall to recover the support of the signal, depending on the sample size n. We assume that 3 is binary and priori s-sparse, that is: A = pp.a = (3 {0, 1)"" || = s)
Remark 3.1 (Binary-signal assumption). Our results for sparse recovery can be viewed as ap- plying to signals whose non-zero components are at least 1 in magnitude, i.c. 9 Cp.s (1) = { E Idd minl | 2 1}. Assuming that the non-zero entries are exactly equal to 1 serves only to simplify computations. Intuitively, detecting a component of magnitude is at least as hard detecting stronger component, so stronger signals can only make recovery casier. Conversely, detecting a signal in cp.s (1) is at least as hard as detecting a binary signal, since (0. 1}.8 S Cp.s (1). More generally, recovering any signal whose non-zero entries bounded below by some p can be reduced to the case of Cp.s (1) by rescaling the model I by p.
Let ABD (AUB) (AnD) B) denote the symmetric difference between any two finite sets A and B, and Supp (8) = ii E [p]: : 8, + 0} denote the support of any vector / E RP. Let (0, 1). We say that A E Bp.s recovers the support of 3* up to error 5 if (Supp (3) A Supp (B+) 25s.
3.1 AGNOSTIC SETTING
In the agnostic setting where the decoder ignores the quality of each observation, the sample sizes (2) and the noise levels oz). Motivated by the maximum likelihood estimator in the homoscedastic setting (see Gamarnik & Zadik 2022)), we define an estimator such that:
3 E arg min || -x BeB,..
(8)
Theorem (Sufficient condition for support recovery in the agnostic setting).
1. Assume = o and + 400 as p +00. Then let n² = 2s log (p/s).
2. Assune op for some constant a E (0, 1). Then let n² = 2h (a) p.
In both settings described above, if there exists e >> 0 such that:
8 (203 - of) s
ös
log
1+
n2 log
[+
2 (1+#)n',
(9)
20
20
then 3 recovers the support of 3* up to error 8 w.h.p.
F Suuupp (8*) A Supp ( < 26s) 2 ex-eep/ exp (- (E
p 1.
(10)
Proof Sketch. The proof of Theorem i in appendix A and uses standard techniques. We control the probability that a high-error support attains a lower objective value in (8) than the ground truth and then take union bound over such supports. For any B, we have:
Y - -3133 |Y x
Σ (X,, 8* 8)2 -8))
(11)
5

---

Published as a conference paper at ICLR 2026
Applying Chermoff bound to the RHS above and analyzing the MGF of the summands yields an exponent that factorizes across two blocks (see Proposition A.I). We conclude using a union bound over supports S with |S A | > 20s (there are most (*) of them).
We interpret Theorem as follows.
Sample Complexity. In our setup, the decoder knows that 5* is exactly s-sparse. When or p. the support is fully determined and there is no ambiguity, making recovery trivial and requiring no samples. For intermediate values of s, the decoder must distinguish among many candidate supports, whose cardinality is (2). This combinatorial ambiguity renders the recovery problem non-trivial and leads to the sample complexity characterized by Theorem !
Price of Quality. The sufficient condition for recovery equivalent linear combination of the sample size n1 and n2 being larger than the threshold n". The coefficients of the sample sizes reveal that one unit of high-quality data is worth:
log (1 + (20 - of) s/ (204)
>
(12)
log + 6s/ (2a2))
units of low-quality data for the sufficient condition to hold. We call the Price of Quality. In fact, one unit of high-quality data can be replaced by y units of low-quality data: that is, if (ni, n2) are large enough for the sufficient condition to hold (and are hence sufficient for recovering (*), then so are (n11 1, n2 + 7))
High SNR, regime. Assume = w (az). The price of quality
12
writes:
log (ōs/ (2o + log (2 /f/03) = 1, log (ōs/ (202))
(13)
which means that when of o o (s). the high-quality and low-quality data contribute equally to the recovery condition (
Low SNR, regime. Assume o (a²). The price of quality
12
writes:
(203 of) s/ (20 y ~ 6s/ (20
2
(14)
Note that 7 2 for any oz We conclude, in the low SNR regime, that under sufficient condition, one high-quality sample can be replaced by up to two low-quality samples.
Remark 3.2 (Limitations).
The condition in Theorem iss sufficient and is not expected to be iioommation-thhoetiialll sharp. The potential looseness arises from relaxation in the Chernoff bound used to control the proba- bility of support misidentification. In the heterogencous-noot noise setting, optimizing the Chernoff ex- ponent leads to cubic equation (see (37) whose exact solution yields tighter but less tractable condition. To retain a closed-form and interpretable sufficient condition, we rely on a relaxation of this equation. In the homogeneous-noiss case, solving the analogous equation is known to recover the sharp threshold, and we expect that optimizing (37) would similarly lead to a tighter characterization here, though do not pursue this direction in the present work.
Even under the assumption that the decoder is agnostic to the quality of the data, the estimator / 8). might not constitute the best approach to recover the support of f*. For instance, especially in the low SNR regime, the decoder might re-weight the loss of each observation by the magnitude its observed label, i.e.:
arg min Σ BEB
Ys ( (xx, (1)r, Y? 1=1
1
attempt to rescale each of data by its noise level. In fact, in the low SNR regime we have EY² > of where of denotes the noise level corresponding to the observation, which motivates the use of y proxy for of when the noise levels unknown.

---

Published as a conference paper at ICLR 2026
Classical approaches to heteroscedastic regression either assume known noise levels explicitly acknowledge heteroscedasticity as part of the statistical modeling assumptions (see, e.g. Buja jet al. (2019)). Extending such considerations setting introduces an additional layer of difficulty, since one must control both the accuracy of variance-related modeling and its impact
sparse support recovery in the mixed-quality
support identification. While variance-aware proce- dures may improve performance when the noise levels differ significantly, a rigorous analysis of such methods is beyond the scope of this work and constitutes interesting direction for future research.
3.2 INFORMED SETTING
In this section, we assume that the decoder knows the distribution of each noise entry: / (0, af or W (0, oz). Recall the distributions of and from 44. The MLE is define by (see appendix for proof):
MILE E arg | (Y (Y-x))]
x
(15)
SEB,,
Theorem (Sufficient condition for support recovery in the informed setting).
Assume s o (p) and +oo as p +00. Then let n* log (p/s).
Assume s = op for some constant a E (0, 1). Then let n* = 2h (a.)
In both settings described above, if there exists >> 0 such that:
ôs
8s
n, log
1+
+ nn log 1+
2 (1+E)nn'
(16)
207
20
then BALE recovers the support of 3* up to error w.h.p.:
P ((Suup (B*) A Supp (MMLE)
20s) 2 1 - exp { (E +
p2t00 1.
(17)
Proof Sketch. The proof of Theorem is given in appendix C and follows similar argument as Theorem I1 Here, the rescaled loss (T5) leads a Chernoff bound that can be optimized in closed-fome form, yielding sharp convergence rate.
We interpret Theorem as follows.
Price of Quality. In the informed setting, the expression of the price of quality is different from the one in the agnostic case (12). writes:
8s
/ log
8s 20
7 log 1
1+
(18)
20
Low SNR regime, Assume of (s). Then:
7 = /
(19)
Low SNR,, High SNR, regime. Assume of w (s) and of os)). Then:
7= log (s/o
log SNR)
1-20000 +00.
(20)
8/02
SNR,
High SNR regime. Assume oz = (s). Then:
> log (s/of) /log (s/oz) log SNR, log SNR,.
(21)
Remark 3.3.
Compared to the agmostic setting (Theorem T}. the appropriate rescaling of the loss in the MLE (15) constitutes better of the high-quality data, in the sense that it leads to higher price of quality 7. particular, y is infinite the low SNR, & high SNR, setting (20) and can be arbitrarily large in both low and high SNR regimes 19 21

---

Published as a conference paper at ICLR 2026
The sufficient condition (16) is obtained by optimizing the Chernoff exponent exactly (see (39) and (4)) ). In homogeneous-noöke noise settings, analogous optimizations are known to yield necessary
and sufficient thresholds (Gamarnik & Zadik 2022; Wang al. 2010. Chaabouni & Gamarnik). Establishing full necessity in the heterogeneous setting remains an interesting direction for future
work.
Remark 3.4 (Generalizations of Theorem 1 and Theorem 2.
Generalization to signed support recovery. The large-deviation bound the proofs of Theo-
rem] T and Theorem 2 suggests a potential extension of the sufficient conditions, respectively (
and (T6). to the setting where the non-zero components of the signal / are not necessarily +7 but rather in {-1,+11 +1]. and the decoder is interested in the signed support recovery, where they
recover not only the indices of the non-zero components of 3", but also their sign. In this setting,
the error measure expressed by the symmetric difference of supports in (TO) and (17) extends to the number of 'wrong' components in 3. given by ||3 8* The threshold n² log (?) would increase by an additive factor of log 2 to account for the increase in the size of the search space (since 3 E {3 E 0, 13" || = s). which has cardinality 2 (z)) Asymptotically. this does not change the leading-order scaling in the sub-linear regime when o (p), and adds an extra a log term to the h (a) factor in the linear regime when
app
Generalization to arbitrary noise structures. Theorem I and Theorem 2 are stated in the simple setting where the data comes from two sources, one good and one bad, motivated by the high- and low- quality data problem. The proof strategy suggests that these results extend to non-singular noise. fact, we only assume that E is invertible, but not necessarily having the form then the sufficient condition (9) in Theorem extends to:
8 (20 (2)) of (2)))
n
log
1+
2 (1+
(22)
max (2)*
where {a; (Σ)} denote the g-values of E, max
( max; 1 Oi (2) and a (Σ)
=
min;=1..... 0, (2). Similarly, the sufficient condition
16 in Theorem extends to:
8s
log
1
2 (1 ssnn"
(23)
20, (Σ)²
A
ALGORITHMIC RECOVERY
In this section, we are interested in the existence of tractable algorithm to recover the support the underlying signal. We assume that the components of the signal 8 take real values and are bounded away from zero: that is,
Cp.s (p) {B E R": ||8110 s, min.ggapp((s)) |&,|| 2 p}. for some R.. We say that / IR" recovers the signed support of 3 if sign( = sign( ). where the function is defined by sign (0) and sign (x) = x/ [a<| for all x * O, and is applied coordinate-wist A common approach to recovering the signed support of the signal is using the solution to the following & conoostradeeed quadratic program, also known as the LASSO:
sign: - (-1,
BLASSO
arg min BERY
||
X
X
Ap 1131112
(24)
2n
where Ao 2 denotes a sequence of regularization parameters converging to as -> +00. We interested in characterizing the regime where the LASSO recovers the signed support of the true signal. Specifically, we call "recovery" the event:
R (X, 3* Z, = { :LASSO: sign (8)
sign (8))-
(25)
In the homogeneous noise setting, Wainwright (009)) showed that the performance of the LASSO in estimating the signed support of 8 exhibits phase transition with respect to the sample size. In fact, there exists a threshold BALG such that:
If n. BALG: then the LASSO correctly recovers the signed support of 1
8

---

Published as a conference paper at ICLR 2026
If n RALG: then the LASSO fails to recover the signed support of 1"..
In addition, it widely believed that no algorithm can recover the support of 8 in polynomial time when n < MALG. Indeed. Gamarnik & Zadik 2022) showed that the problem exhibits an OGP. This motivates the use of (24) to estimate 3 in the agnostic setting where the decoder treats the data impartially. Our main result of this section, Theorem [ extends the result mentioned above on the LASSO threshold (by Wainwright (2009)) to the heterogeneous, agnostic noise setting.
Theorem 3 (Lasso recovery phase transition). Assume that, as p + to0; goes to infinity, s o (p) and n1, n2 (s). Let NALG = 2s (p- s) +
i. If there exists e > O such that:
(1 E) nALGS
(26)
then, for any sequence Ap > such that moottnoo has limit in Rzo U {+00}, we have 23n
Px,z R (x, L, x,) + O.
If there exists E > 0 such that:
(1 (1+83 e) naiG.
(27)
and (2p)p21 is chosen such that:
+ to0, and A + p
1
oang log s
+ 0,
(28)
2 log (p 8)
then Px.z (X. 8" Z.Xp)) 1.
The full proof of Theorem 3 is given in Appendix D and follows the core LASSO threshold argument of Wainwright (2009). We use the same argument but generalize to the heterogeneous-noiss set- ting, where the presence of the matrix 2, no longer a scalar multiple of the identity, causes key steps of the classical proof to fail. We overcome this by applying a Gram Craam-chmiitt (QR) decomposition of Xs (49) and analyzing the resulting orthogonal matrix using properties of the Haar measure on the orthogonal group (e.g. see Lemma 6.6). The monograph of Meckes (2019) on Htar-distributed matrices was particularly valuable understanding this component from random-matris theory.
Proof Sketch of Theorem ditions of the LASSO
We express the recovery property
25 via the first-order optimality
(Hx (H Ew Ap sign (82)) <B3
R (X, 8* Ew, Xp)
X (xfxs) 4 Ap sign (35))
LXT Ew
S Ap
8-
(29)
where absolute values and incqualities taken component-wise. This well-known result (Wain- wright 2009 Fuchs 2004 Meinshausen Bühlmann, 2006 Tropp 2006 Zhao & Yu 2006) is
stated in Proposition D.1 When (27) and (28) hold, the random variables inside the absolute values on the RHS of (29) concentrate below their respective upper bounds, establishing sufficiency. When
26 holds, the second absolute value in 29 concentrates above Ap. showing necessity.
Although Theorem 3 does not explicitly state any condition on the scaling on the noise, the existence of Xp -> 0 such that (28) holds requires that the noise does not scale arbitrarily large. The next result explicitly states this condition.
Proposition 4.1 (Necessary and sufficient condition on noise scaling). If there exists (Ap)p21 + such that 28 holds, then:
2 = ( s/p²) log (p
(30)
Conversely, if 30 holds, let:
1/4
arg log (p -
Ap
(31)
(1 s/p2)
Then Xo 0 and 28 holds.

---

Published as a conference paper at ICLR 2026
Proof. See appendix
E
Remark 4.1 (Correlated features). Theorem is stated for independent features (i.e. 24 ~ N (O,00 1p) for all i E [n]). In the homogeneous noise setting, analogous results for correlated designs under suitable regularity conditions on the covariance matrix were established by Wainwright (2009). Ex- tending the heterogeneous-noine analysis to correlated designs requires additional tools and is left for future work. In this paper, we therefore focus on the independent-featur case.
Remark 4.2 (Informed setting). Although we establish the phase transition for the LASSO only in the agnostic setting. a natural extension in the informed setting is the rescaled estimator defined by minimizing
- -Xx33 instead of |Y x in 24 Extending the proof of Theorem 3 and Wainwright (209) this setting is nontrivial, as the presence of X-- factors alongside the design matrix in (29) destroys the Wishart structure X Xg ~ WW...n) used to control the moments of its inverse via classical Tiverse-Wishal arguments (Anderson et al. [958; Siskind 1972). An analysis would therefore require controlling the moments of (X (xs) whhich remains an interesting direction for future work.
CONCLUSION AND FUTURE WORK
We study the problem of sparse recovery when observations come from mixed-quality sources. We establish sufficient conditions on the sample sizes (M1, n2) ) for both information-theoree and algorithmic recovery purposes and in two settings, one when the decoder is completely agnostic to noise and one where they are informed of the per-sample noise variance.
At the level of the information-theoree low-quality samples, and label the number of low-quality samples required to replace one high- quality sample when our sufficient condition holds the Price of Quality. In the agnostic setting, we reveal that this entity is quite low: in particular, under our sufficient condition, one high-quality sample is never worth more than two low-quality samples. However, in the informed setting, the price of quality can grow arbitrarily large depending on the noise variances and the signal-tonoiss regime. This highlights a key practical implication of our results: whenever possible, quantify uncertainty in the annotations and rescale the loss accordingly.
threshold, study the trade-off between high-quality and
At the algorithmic threshold, we show in the agnostic setting that the classical LASSO recovery results from the homogeneous setting remain valid in the heterogeneous case and depend only the total sample size nı + n2. First, the threshold itself is independent of the individual noise lev- els. Second, the sufficient condition the penalization coefficient involves the noise only through its average, exactly as if all observations had that average noise. Consequently, high-quality and low-quality samples contribute equally the sample-size requirement for LASSO recovery. This reveals an unexpected difference in the effect of data heterogeneity on the information-theorrtie and algorithmic thresholds for recovery.
Within the Gaussian design framework considered here, the informed information-theons thresh- old and the LASSO threshold are sharp, whereas the agnostic information-theoreee condition is sufficient but not proven tight.
In broader discussion on how the information-theoreti and algorithmic thresholds interact across different problem settings, our result further emphasizes that the algorithmic threshold seems to be more "robust" changes in the traditional problem settings (Gamamik Zadik] 2022; Wainwright) 2009). In fact, Wang et al. (2010) and Chaabouni & Gamarnik observed that when the noise is homogeneous but the design is sparse (i.e. X,, set to uniformly random) the information- thcoretic threshold increases, while Omidiran & Wainwright (2008) showed that the algorithmic threshold remains the same and is unaffected by changes in the sparsity level of the data (although this was shown only for the sufficient condition, with no corresponding result necessity).
Although we do not study LASSO recovery in the informed setting, this remains a promising di- rection for future work. It would be interesting study the price of quality there, and compare it to LASSO recovery the agnostic setting on one hand, and to the price quality of information- theoretic recovery on the other.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by the National Science Foundation (NSF) under grant CISE-2233897. Youssef Chaabouni thanks Mehdi Makni, Marouane Nejjar, Panos Tsimpos, Malo Lahogue, and Alexandre Misrahi for insightful discussions and valuable feedback.
REFERENCES
Shuchin Aeron, Venkatesh Saligrama, and Manqi Zhao. Information theoretic bounds for com- pressed sensing. IEEE Transactions Information Theory, 56(10)55111-57 2010. doi:
10.109//TT2010225999..
Theodore Wilbur Anderson, Theodore Wilbur Anderson, Theodore Wilbur Anderson, Theodore Wilbur Anderson, and Etats-Unis Mathématicien. An introduction to multivariate sta- fistical analysis, volume 2. Wiley New York, 1958.
Andreas Buja, Lawrence Brown, Richard Berk, Edward George, Emil Pitkin, Mikhail Traskin, Kai Zhang, and Linda Zhao. Models as approximations Statistical Science, 34(4):523-544 2019.
Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489-509, 2006.
Youssef Chaabouni and David Gamarnik. The price of sparsity: Sufficient conditions for sparse recovery using sparse and spansified measurements. In The Thirty-ninth Annual Conference on Neural Information Processing Systems.
Scott Shaobing Chen, David L Donoho, and Michael Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):122-115)) 159, 2001.
Graham Cormode and Marios Hadjjelcfttheriou. Finding the frequent items in streams of data. Com- munications of the ACM, (CMM,2((1))9))))))) 52(10)997-105, 2009.
Laurens De Haan and Ana Ferreira. Extreme value theory: introduction. Springer, 2006.
Aurore Delaigle, Peter Hall, and Alexander Meister. On deconvolution with repeated measurements. 2008.
David L Donoho. Compressed sensing. IEEE Transactions information theory, 52(4):1289- 1306, 2006.
Ding-Zhu Du and Frank Kwang-ming Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 1999.
Naoki Egami, Musashi Hinck, Brandon Stewart, and Hanying Wei. Using imperfect surrogates for downstream inference: basign-based supervised learning for social science applications of large language models. Advances in Neural Information Processing Systems, 36:68589-68601 2023.
Simon Foucart, Holger Rauhut, Simon Foucart, and Holger Rauhut. An invitation compressive sensing. Springer, 2013.
Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: a survey, IEEE transactions on neural networks and learning systems, 25(5):845-869, 2013.
J-J Fuchs. Recovery exact sparse representations in the presence of noise. 2004 IEEE Inter- national Conference Acoustics, Speech, and Signal Processing, volume 2, pp. ii-53.. IEEE, 2004.
David Gamarnik and Ilias Zadik. Sparse high-dimensions linear regression. estimating squared error and a phase transition. The Annals of Statistics, 50(2):880-903: 2022.
Kristina Gligoric, Tijana Zmnce Cinoo Lee, Emmanuel J Candès, and Dan Jurafsky. Can unconfident Ilm annotations be used for confident conclusions? arXiv preprint arXiv:2408, 15204, 2024.

---

Published as a conference paper at ICLR 2026
Yinzheng Gu. Moments of random matrices and. 2013.
Piotr Indyk. Sketching, streaming and sublinear-space algorithms. Graduate course notes, available at, 33:617, 2007.
Michel Ledoux. The concentration of measure phenomenon. Number 89. American Mathematical Soc., 2001.
Minzhi Li, Taiwei Shi, Caleb Ziems, Min- Yen Kan, Nancy Chen, Zhengyuan Liu, and Diyi Yang. Coannotating: Uncertainty-guit work allocation between human and large language models for data annotation. arXiv preprint arXiv:23 /5638, 2023.
Po-Ling Loh and Martin Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. Advances in neural information processing systems, 24, 2011.
Pascal Massart. Concentration inequalities and model selection: Ecole d' Eté de Probabilités de Saint-Flour XXXIII-2003. Springer, 2007.
Elizabeth S Meckes. The random matrix theory of the classical compact groups, volume 218. Cam- bridge University Press, 2019.
Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and variable selection with the lasso. 2006.
Alan Miller. Subset selection in regression. chapman and hall/CRC, 2002.
Shanmugavelayutham Muthukrishnan et Data streams: Algorithms and applications. Founda- fions and Trends@ in Theoretical Computer Science, 1(2):117-236, 2005.
Mohamed Ndaoud and Alexandre B Tsybakov. Optimal variable selection and adaptive noisy com- pressed sensing. IEEE Transactions on Information Theory, 6644)22517-253. 2020.
Dapo Omidiran and Martin J Wainwright. High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency. arXiv preprint arXiv:0805.3005, 2008
Pranav Rajpurkar, Jeremy Irvin, Robyn L Ball, Kaylie Zhu, Brandon Yang. Hershel Mehta, Tony Duan, Daisy Ding, Aarti Bagul, Curtis Langlotz, et al. Deep learning for chest radiograph diagnosis: A retrospective comparison of the chexnext algorithm to practicing radiologists. PLoS medicine, 15(1 (5111))e000268, 2018.
Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. Proceedings of the VLDB en- dowment. International conference on very large data bases, volume 11, pp. 269, 2017.
Galen Reeves, Jiaming Xu, and Ilias Zadik. The all all-or-nothing phenomenon in sparse linear regres- sion. In Conference on Learning Theory, pp. 2652-2666 PMLR, 2019.
Alvin Rencher and G Bruce Schaalje. Linear models in statistics. John Wiley & Sons, 2008.
Jonathan Silvertown. A new dawn for citizen science. Trends in ecology & evolution, 24(9):467- 471, 2009.
Victor Siskind. Second moments of inverse wishart-matrix elements. Biometrika, 5993)699--69,, 1972.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
Joel A Tropp. Just relax: Convex programming methods for identifying sparse signals in noise. IEEE transactions information theory, 5203):1030-1051, 2006.
Martin J Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using l constraained quadratic programming (lasso). IEEE transactions on information theory, 55(5): 2183-2201. 2009.
12

---

Published as a conference paper at ICLR 2026
Wei Wang, Martin Wainwright, and Kannan Ramchandran. informatiionthhoretii limits on sparse signal recovery: Dense versus sparse measurement matrices. IEEE Transactions on Information Theory, 5666))2976666 2010.
Ruoyu Zhang, Yanzeng Li, Yongliang Ma, Ming Zhou, and Lei Zou. Llmaaa: Making large language models as active annotators. arXiv preprint arXiv:2310. 19596, 2023.
Peng Zhao and Bin Yu. On model selection consistency of lasso. The Journal of Machine Learning Research, 7:2541 1266,, 2006.
13

---

Published as a conference paper at ICLR 2026
A PROOF OF THEOREM 1
Proof of Theorem 7
We denote by S = Supp (8*), Let Sp,s = {S c b |S| = s}. We define
the function:
L: Sp. - Rz0
S IY x11sl22
where 1s denotes the vector in {0, 1j such that [1s]] 1 E S) for all j E [p]. In particular, note from (8) that:
B = gg
where
$ arg min L (5). SESp.
For every S E Sp.s. we define: M (S)= = SS |* /2, and let U (S) S* (S)
Note that, since | = |S*| = 8, we have (S) V (5) M (S). We also define:
A Sp.. + R
S - L (S) L(*)..
Proposition A.1. For any S E Sp.e if M (S) 2 ōs. then:
8 (20g - of) 8
-n1/2
8s
-22/2
P (() < 1+
1 +
20
20
Proof. See section A.I
Hence we have, for any support S E Sp.s such that |S S
2 26s:
8 {20 - of)
-n1/2
58
-n2/2
P P X1s
Y X1s- 113 s 1
1 +
(32)
202
20
Using 32 and a union bound over (S E Sp.s
SSA 2 25x) we have:
Px,2 ( Supp
(3) A Supp (8*)
< 28s
2 Px.z
Y
X1sl3
||Y X15- 11, VS Sp..: 1SAS 2 20s)
=1 =
35
Sp.s: ISAS 2 25s, Y -X11l $ I -11s 11)))
U.B.
2
1
Σ
Px,z || -1ss12 1|l
X1s -x1s- 12)
SESp. : |S 1226s
8 (203 - of) s
-n1/2
5s
-n2/2
Σ
1+
1 +
202
20
SESp.x: 18 S5A8-1226
8 8(20} - -f) 8
-n
88
-2//2
2 1 - /Spmo
1
1 1
202
20
= - - (
8 $202 of) s
-21/2
8s
-22/2
1
1 +
20
20
Case 1: Assume o (p). We use the corollary of Stirling:
(P) = exp (slog (p/s) (1 + (1)),
14

---

Published as a conference paper at ICLR 2026
which yields:
Fx,2 (Supp ( A Supp (8*) < <20s)
2 1 exp
log (p/s) (1 (1+
11
log
1+ (203 - of)
n12
log
1 +
08 20
2
203
2
Now using ( in above, we have:
Px,z Supp
3 A Supp (8*) <26s)
> 1 exp s log (p/ 5) (1 (1)) (1+ soo (p/s)}
2 1 exp (-e8 log (p/8) (s log (p/6))}
Finally we conclude:
< 20s 2 exp (- (1))n' " 1, Px,z Suup ( A Supp (8*)
where n² = 2s 2og (p/s).
Case 2: Assume a (p) for some constant (0, We use the corollary of Stirling:
(0) cxp (b(())((++(1)))
which yields:
Px,2 Supp
3 A Supp (8t) <20s)
1 exp h (1(a)p(++0(1))))
711
log
1+
8 (203
of)
12 log
1 +
8s
2
20
2
20
Now using in above, we have:
Px.2 Supp 3 Supp (0*) < 258
2 1 - exp h (a) pl +o - (()+))
2 1 exp e -
Finally we conclude:
Fx,2 Supp (8)
A Supp (8*) < 20s) 21
32 1,
where n²* = 2h (a:) p-
A. PROOF OF PROPOSITION A.
Proof of Proposition A.1
Fix E Sp.s such that M (S) 2 ös. We have:
(S) L.(S) (S*)
= -|Y 1X111 || - x1
||x,** + - |x3" + Z 1x1ss
= =|[X (1.s - 1s)1 + 2(2, (Ils - 1s))
Σ (X,, 1. 1s)² 1s)² Σ Z((X, 1g - 1s))
Let Xi REIxp, X2 E R02xx such that:
X X
X₂
15

---

Published as a conference paper at ICLR 2026
Then the above expression of A (S) writes:
R1 A (8)
Σ
(x), Is. - : - -1s)}
122
(x? 1. -1) 22 1s. [1s)}
i=1
We denote by (4!) kE(m.) and (A sE(mzl
the terms of the sums above, that is:
A = (X) 1s. -1) (X) 1s- - 1s)
A = (X; - 1s) 22 1s. 19)
Note that each of the elements of each of { : i [mi]] and {AZ : i [nel] are iid. and:
131
12
A (S) Σ 4 + Σ A?
Recalling the Chernoff bound:
P A (S) = =0 (0)))0)) 20)
inf P 020
(0A(S)) 21)
(Markov's inequality)
< inf E 820
in
EN
0A A47]
020
122
inf
E
04
E 04?
i=1
1=1
=inf 820
MMMay -. (0)
M
II
M A? (0)
(=1
{ M (0))
{ { AM (0) m
inf
020
Therefore:
(P < 0) s inf [M
(01) "1
n2
(33)
820
Now have for any 0 0:
e (XX],X -2)
M (0) = Ex! 2!
e -IX Ezi E -282 -222 -0(S1) xx!]
Ext
e -1x ((9)) MzZix! (-20(x), 8 8- 3 3 (S)))
Ex!
-x o3 (-20(x)--'--(19))
Ex!
(- of) (x) --
Ex,
=Ex, [e( (- () X Ejev x!)
where we write U and V for U (S) and V (S), respectively, for simplicity. We know that:
Σ x Σ X L Σ X ~N,,UU,
JEU
JEV
JEUUV
16

---

Published as a conference paper at ICLR 2026
Hence:
M (0) Ex (e(-0+200f) Xi -Ezer x
= Ex, (clovr(--0200
where:
EjEu X - -EEE X xx)
T=
VIUM
Therefore:
if FUUV 202 < <1/2
M (0)
(1-2)
(34)
else.
Similarly to 34 obtain the following expression for M-);(0):
if IU +02 < <1/2
V1-a1our((-01200)
M (0))
(35)
else.
Therefore, for any
-11/2
(1-2 x (1- (1-2 21U UV (-0+ -72/2
M M (M)
U (- 10020000 < 1/2
if
U ( 10-0+200000 < 1/2
+00
else.
Remark A.1 (Best Chernoff bound). To find the best Chernoff bound optimization problem in (33). defined by:
33
we need to solve the
{ (Ma {M (0)) n2
inf 020
(36)
Using the First Order Optimality Condition, 36 reduces to finding the roots of g (0) 0 is closed
form, where & (-) is defined by:
( = (0)= (0)
Using the closed-form solution of (.) obtained above, we conclude that solving 36 reduces to finding the positive roots of the following third-degree polynomial in A:
ni (4o 1) -
2 UVU +2)+0)) na (4o20 1) (1- 20
(37)
To the best of our knowledge, this doesn't 't lead any "reasonable" closed-form expression for the minimizer . Instead, we note that:
{0: IU (-0 + (-0+20% 1/23 S (0: (-+-2(-)) 1/2]] and choose to the middle of the LHS interval.
In partieular, setting 0+*
1 have;
107
UU (-0- 20 = - 0* -0VV - -0UUUV/2<000012
and:
UU (-0- + 220 = - 1U
(11
of 20
<0 <0< (since of <,,))
17

---

Published as a conference paper at ICLR 2026
Therefore:
M 2= (0 M (2000)
1 1 2UUUU (-0"
+20
- +0-000----000
-ni/
(-0)
+.202 -204223)
(-1 +
-21/2
1
oo
4
-/am
x11 x11-21
1
2
2
402
4
1+ |U+UU
20 -
of
11/2
-n2/2
1
402
403
1+ (203 - of) 201
1112
8s
-na/2
+
20
where the last inequality holds because 1U UV conclude:
2M (5) 2 20s. Finally, using this in
we -n2/2
33
-m12
8 8202 - oî) 8
(SA
50)
1+
1+
2012
20
B
PROOF OF (15
Proof of 15 Let 8 Bp.s. We know from I that:
Y TIX,B~N(X8.>>
Its pdf writes:
f (v) = (2x) -n/2 det (Σ) exp { - x (y- x3)
The MLE is defined as:
ML arg max fY |x,9 (Y)
SEB,
arg min (x3)) I x- 2Y -V-X9
BEBp
arg min (Y xx3)² (M-1) I (Y X3)
BEB,
arg min BEBp,>
C PROOF OF THEOREM 2
Proof of Theorem the E-rescaled loss:
2
We denote by S* Supp (B+). Let Sp.s (S [p] |S| = s). We define
L3: Sp.s - Ry0
S S || (X)
where 1 g denote the vector in (0, 1)2 such that [1s (j S) for all [p]. In particular, note
from (5) that:
3MLE 1 SYEE" where SMLE arg min Lg (S). SeSp.
18

---

Published as a conference paper at ICLR 2026
For every S E Sp.s. we define: M (S) = |SAS /,, and let U (S) = S" 1. (S)) = S\S'
Note that, since [S| = |S*| = 8, we have [U] - IV (5)l = M (S). We also define:
: Sp - IR
S - T (S) L (S*).
Proposition C.1. For any S E Sp.s: if M (S) 2 ös, then:
òs
R1/2
ôs
-na/2
P(A (S) 0) 1
1 +
1 +
2
20
Proof. See section C.1
Hence have, for any support S E Sp,s such that |S S*
2 20s:
PI (Y
x1s) s (Y - x1ss - - 1
ôs
-ns/2
1+
ôs
-22/2
(38)
2
20
Using
38 and a union bound over (S E Sp.s: |SA S+1 > 20s} we have:
Px.2 2
Supp ( A Supp (B*) < 25s)
|| 1 (Y- - X1 X1s) 11 > | (Y - X1s. ) AS E Sp.s: |S 2 26s)
2 Px.z
=1 -1- Px 78 E Sp S* 2 20s, || (Y x1s>)11 - |0 (V X1s. 112)
U.B.
2 1
Σ
Px,z || (Y- - X1s) 1/2 S - (Y x1ss >11))
SESpie
18 12266
38
ds
-R1/2
ôs
-n2/2
Σ
1 +
1+
207
20
SESp.
1S 8 1228s
8s
-m//2
-2g
2 1 Sp,s
+
+ 20
20
p
8s
-n1/2
ôs
-22/2
=1
1
1 +
2
20²
Case 1: Assume s = o (p). We use the corollary of Stirling:
(p) = cxp (p/s) (1
which yields:
P Px,z Supp
3 A Supp (B*) < <25s)
2 1 - exp
s log (p/s) (1+00 (1))
71
log 1
ôs
n2
log
1+
8s 20
}
2
20
2
Now using 16 in above, we have:
Px Supp ( A Supp (3t) < 26s)
2 1 - exp s log (p/s s) (1)) - (1+ log (p/s)}
21 1 exp { (ss log (p/s) - (s log (p/s))}
Finally we conclude:
Fx.z Supp
(8) A Supp (8*)
< 28s) 2 1 - exp f- (e "0 1,
19

---

Published as a conference paper at ICLR 2026
where n² 2s log (p/s).
Case 2: Assume s = h (a) p. for some constant a E (0, 1). We use the corollary of Stirling:
8 (e) = exp (h(0)p(1+0(1)))
which yields:
2x Supp
( A Supp (8*)
< <200)
2 1 - exp
cxp
h h())
n1 log
1 207
ôs
n2
log
1+
203 }
8s
2
2
Now using 16 in above, we have:
P x Supp ( A Supp (3") < 20s)
2 1 - exp h (a) + - (10)))))-+++++)1) -(1+))((0)p)
2 1 exp -- (a)
Finally we conclude:
Fx,z Supp (3) Supp (8*) < <20s) 2 1 o= "0 1,
Supp
where n²' = 2h (a:) p-
C.I PROOF OF PROPOSITION C.1
Proof of Proposition C.7
Fix S E Sp.s such that M (S) 2 8s. We have:
A (S)= Ly (5) L (S")
(Y (Y-
(X-
"X + +x X1s)]l - |X + - X1g. )
| (Iss- - -1s) -2(E- X (1s.-1.5) -1s))
-
m
n2
1
Σ
(X, 1s. - 1s)²+
Σ
(X 1s - -1)²
of
02
i=
+ 2 n1
n2
1
Z, 1ss 18) +2
Σ
Z 1s. 1s)-
of
02
i=1++1
Let X1 E RP1
X2 E X such that:
Xi X
X2
Then the above expression of A (S) writes:
(s) = 7 Σ
(x] 1s - -19)² + (x),, 1s. - -1s)
n2
(X2, 1s. - -1s) 1s. - 1ss)
We denote by (A!) ke(m)) and (A?) sE[nz] the terms of the sums above, that is:
A (X), 1s. -1s)2 + +2, (X}, 1s 1s)
A (X2,1s- - 1s)² 11 1s)
20

---

Published as a conference paper at ICLR 2026
Note that each of the elements of each of {4}
e [ni]} and { i [nel] are iid. and:
( o 2=1
- A
1
Σ 4
Using the Chernoff bound, we have:
P (S) = (P-A (5) 2
inf P
-BA(S) 21)
820
inl E
(S(
020
Eis
04 1/ Eis $2,
inf E
e
o3
020
1/2
ind.
inf
/
E
820
0
12/
inf
M
M
A
020
02
id.
0
M_A A!
M_
820
Therefore:
0 T
12
P ((A S 0) S inf
M M-A:
M M-A:
(39)
020
Now we have, for any 0 2 0:
M M-a:(0/0f (0/o7) = Ex x] ?
(x) - 965))//077 e -(x (x}
-x) 9" -20 - [x
Ex!
8'0 - / MZHIx! (-20(X), 8 ((S))/o))
Ex;
-0 -(S)) -19))/o0)))
Ex!
Ex, ( (-0+20 (x2
Ex, c 8428)) (Ejev x Ejev xt))
where we write U and V for U (S) and V (S), respectively, for simplicity. We know that:
Σ x
Σ
x XO,NNOO,UUVI).
JEU
jEV
JEUUV
Hence:
M M-) (0) Ex, [el ((-0+20)(
20
X1. -Ssevv xt 100
Ex; [JUUV (-0+26))r/of
where:
Ejeu X1,, - EJEv X1 VIDvv
T=
x1)
Therefore:
if UUVV 20000+202)/000 < <1/2
M s! (8/07) =
V (- 0+202)/0
(40)
400
else.
21

---

Published as a conference paper at ICLR 2026
Similarly 40
obtain the following expression for M-
if LUUVI +20) /02 1/2
M (0/02)
VI-
84
(41)
to0
else.
From above, we clearly have:
arg min M - 2,(0/o}) arg min M 2;(0003) - arg min { - + 20 1 #20
020
020
and, taking 0+ = 1/4 we have:
(0//(0/of)
and M-az(8/03)
V1 +
uuv 4m,
V1
uuv 4n
Therefore:
(220 } o7
03 ) =
0
0+
inf
M a
M M-
M-s!
M M-A3
020
o7
192
DOV 407
BUA
4
Therefore:
inf M 020
07)
}
8 N2 M-a: (
(2))
(1+
1+
( 1+
UUV
U
-22/2
03
407
403
(42)
Since I UUVV = 2M (5) 2 20s, the above yields:
inf { M Maas -
0
}
8s
121/2
8s
12222
M Ma
+
+
020
20
20
Finally, using this (39) we conclude:
5s
-21/2
ōs
-22/2
(S)
1
20
20
D PROOF OF THEOREM
Proof of Theorem
We define Σ E ggxn and W random vector in R such that:
Z WW,
where:
Σ onlni
W ~
02In2)
Let S = Supp (3*) and S (p) S. The following proposition characterizes the recovery property in more tractable way that will help us in the proof.
Proposition D.1. Assume that the matrix X3 X is invertible. Then, for any given Xo and noise Ew E T we have:
(xxTxs) -1 (X A, sign (82)) (833
R (X, 8t Ew, Ap)
X5.Xs (xfXs)
(2 spgign (33)) _XT -. Ew S Ap
where the absolute values and inequalities are taken component-wise.
22

---

Published as a conference paper at ICLR 2026
Proof. The equivalence follows from the First Order Optimality Condition of the LASSO (24
was used in the proof of the LASSO threshold Wainwright 2009) and previously by Fuchs (0044);
Meinshausen & Bühlmann (2006); Tropp 2006); Zhao & Yu (2006). See appendix D.1 for the
complete proot.
Let sign (3*). We define:
U U:=ú; of n
(xxxXs)
[ ES -2pb)
(43)
and
Vi V===3 x3 { Xs (xzxxs) -1 Ap5 Xs (xfXs) X3 In
EW
(44)
n
for all S and j E S" Let p minks |851. Note that:
-1 UU! <p (Hxxxx 70
( 2fE Ap sign (95)
(1 n
max iES
(,35),
(45)
and
_ X Ap sign (83)
max JES-
S = X5. (xzXs)
x Ew
S Ap.
(46)
In addition, note that when 8 < X is full-rank a.s., and hence X X is invertible a.s. Therefore, the equivalence in Proposition 3.1 holds a.s. The proof of Theorem relies of the two following propositions:
Proposition D.2.
i. Under the sample size condition 26 we have:
max JES"
VV S
A
p=te0 0.
i. Under the sample size condition
27 and the regularization condition 28
have:
P max JESt
|V Vi
S Xp
p 1.
Proof. See appendix D.2
Proposition D.3. Under the sample size condition 27
and the regularization condition
28 we
have:
U$| < p 1.
max iES
Proof. See appendix D.3
Necessity: assume 26 holds. Then conclude by Proposition D.2 ii] and 46)
Sufficiency: assume 27 and 28 hold. Then we conclude by Proposition D.2 [ii], Proposition
D.3
and (45) (46).
23

---

Published as a conference paper at ICLR 2026
D.1 PROOF OF PROPOSITION D.1
Proof of Proposition D. Let 3 E RR. By First Order Optimality Condition of the LASSO, 3 is optimal if and only if the exits z IR such that:
2 E 02 8
2 E
R.: 2,
sign (..) for B, + 0, |2/| S otherwise }.
1
X
+ Ap2== 0. Y
The condition above can be equivalently written as:
29 sign (8s)
I=8= 1 X x - + Ap2 =
Substituting Y = =X3" + Ew, the condition writes:
2s sign (8s)
|RSe| S 1.
1 X (8-8)
1 + Ap² O.
Splitting on and S we get:
29 = sign {s)
|=80| S 1.
1 1xTx X
- 3*
n 1 + A sign [Bs) = 0,
Xx X
3 8r
x Ew + Ap = 0.
Now the LASSO recovers the support of 3r if and only if there exits & IR such that sign (8)
sign (f*) and:
28 sign (8s)
|28e| S 1,
3 E I2 such that
n XX X
3 - 8r
1 Ex An sign (8s) 0.
n
xx. X
B - 8r
X Ew + Ap=s= = 0.
Which is equivalent to:
sign 3
sign (B*),
29 = sign (8s)
3 2, 3 E R2 such that
Izse I 1,
X x (3 - 8r)
n 1 Ew + Ap sign ($9) = 0,
x X (3 - 8r
X Ew Ap2s- = 0.
which is equivalent to
sign 8 = sign (3*).
28 sign (33),
3 z, 9 E IRP such that
| < 1.
Xx X
Bs - /3
1 EXTE Ap sign (83) 0,
Xy. Xs
BBs - 83
Lx Ew + >p = 0.
24

---

Published as a conference paper at ICLR 2026
which is equivalent to
Age 0,
29 sign ($3) sign (93) + 0,
3 2, E IRP such that
|z50| S 1,
Bs B3
( Ewe
Ap sign (85))
X Xs
(As $3
1X Ew $ Ap
which is equivalent to
(+x3Xs) (1 X Ap sign (85)) < 11811,
Xs (x]Xs) - (HX - Xo sign (83)) 1/2 Xx S.
Ew
S Xp.
D.2 PROOF OF PROPOSITION D.2
D.2.1 PRELIMINARY RESULTS
Lemma D.1 (Moments of (V Xs, W)). Conditionally on Xg and W, V is Gaussian vector. In addition, we have:
[V Xs, W] 0,
and:
Cov [V Xs. W] Mpd1s-1
where:
Mp = Xs (X5xs) 2n In - Xs (x3xss) "xx' EW
2
= 236" (X3Xs) -1 -o+ WTS In- In- -ia (X3
x3 EW.
Proof. See section D.2.4
Lemma D.2 (Bounding the second moment of (V Xs, W)). We have:
X3
(n 8) (nlof + n20
[Mp]
11 - |bb1| +
n23
In addition, for any constant ô 0. we have:
P PIM, - E [M,]] 2 SE (M,)) + 0,
as p +00.
Proof. See Section D.2.5
D.2.2 SHOWING THAT P (maxzes= [V S Ap) + 0:
Proof of Proposition D.2 part (i.) Let:
(6) {I, E. [Mp]] 2 dT [M₂]]-
We have, by total probability:
max |V 1p) <
max jES
V S A IT P(T (8)).
(47)
JEST
Conditioning on Xs and W:
TP max V S Xp (0))
E
PP (P(max
S Xs:W) (6))
JESc
Jest
25

---

Published as a conference paper at ICLR 2026
iid Note that, conditionally on (Xs, W), we have V ~ N (0. Mp), for j e S We know the bound on expectation of Gaussian maxima (see Theorem 5.3.1 in (De Haan & Ferreira 2006));
E
max
V
Xs: W
22 (p s) M, (1))
JES-
Conditionally T (8)", we have:
M, 21 -0 [Mp)
Hence, conditionally on T (6)::
1
E
max JES
Xs, W
Ap
V log (p (1 6) [M] (1+)(1))
V1-8
2X9 s log s)
+ 2(n - 8) (m10} + n203) log (p - s)
2 (1+)
Ap V
8 ---1
n
8 2s log (p- 8) 2 2 8) onioî 22
log (p 8)
o1) V1
Xan
We consider two cases, depending on the asymptotic behavior of n2 o
Case I: limp-+te
0. oid 4
Case 2: lim too
0.
Xnn²
Case 1: Assume limp-++oo
11
+nza
O. By the above inequality, we have:
2s log (p s)
E
max
VV
V1 Xs. W 2 (1+0
8V
X
JES
72 8
Using condition (6 the above gives:
2x log (p 8)
E
max
Vil
Xs, W
2 (1 (1)
Ap
JES
1
2s log (p- 8)
(1+0 V
(1 - E) (2s log (p 3) + s + 1) - - s-1
2s log (p 8)
= =(1+0(1)vV] VT- V
2s (1 E) log (p 8) - E +1)
2s log (p
2 21+0 5
2s (1 5) log (p 8)
= =1+o(1))
Taking the liminf as p + to0 we get, conditionally on T (8)
1 8
lim inf - E +0+ Xp
max [V5]
Xs, W
>
JES=
Therefore, for n large enough we have:
5
E max JES
Xs,
W
1 1
2
2
2
1-8
26

---

Published as a conference paper at ICLR 2026
Taking 8 = E/2, get:
1
8/2
I
JESc
max
xs
W
2
2
+
2
1 -
=: K 1.
Next, we use the following the result on concentration of Gaussian maxima:
Lemma D.3 (Concentration of Gaussian maxima). Let l E N and (N.) i itd
N (0, Then for
any 1) > 0, we have:
P (maxiE(M) N; E [max[e[M]] No} n) s exp
"
2r
(max)E(H) N; E [max No. < <nn) s exp
112
2T
Proof. See appendix D.2.6
Using Lemma D.3 gives, for all v) 0:
1)2
P
max jESc
VV]
E
max
VVl
17)
eexp
Jes=
2(1 E Mpp
Setting 77 (Is 2p/
get:
P
max VV S Ap (8)) jESc
P
max
[V]
(x+ 1) Ap/2
T I())²
jES
<P max
[V]
E
max Vi3
(Is - 1) 1p2p/2 T(6)))
jESc
jESc
(x - 1) 2 X2
S exp
(2 + 8) E [Mp]]
(n 1)2 X2
p
cxp
>3
(n-
5) (1 m20 n
4 4 +6)
n-s-1
(k 1)²
exp
4 42 + +6)
+ n- nio 120
n-
X
morttaee
Now note that, because lim
0, the above RHS goes to 0 as p - +00. Hence,
x
we get:
max V S Ap T()8
12t00 0.
jESe
Taking the limit in 47 and using the fact that P(T (6)) p O, we conclude:
lim
P
max
& Xp = 0. |V
+
JESc
27

---

Published as a conference paper at ICLR 2026
nio 1512
Case 2: Assume 1om
0. Note that this could be +00. We have:
1 E
max JES
Vil
Xs, W
Ap
28 log (p 8)
2(n 5) (ni07 + 22233)
log (p 8)
2 (1++ (1)
12103
n
2 (n 8) (nlof + n203) log (p 5)
vI- vl
25n2
ni
+ n2
=1+
V1
2
v log (p
X2
n
+00.
Therefore, for large enough, we have:
E
max JES
|V]
Xs, W
2 4Ap
Now using Lemma D.3 on concentration of Gaussian maxima, we have for all >> O:
n?
P
max jES
|V]
E
max V5l JES
-1)
exp
2 E M
Fixing = [ms [V]] /2 and 8 e/2 get, for large enough:
P max |V S Ap (8))
SP
max JES
< 22p
T (B))
jESc
max V2,
max [V]
T [())=
JES:
2
jEESe
(())))
=P max JESS
< E
max V
E
max JES-
Vij
JESc
E [max je |V
S exp
4 4 + E) [Mp]
E [[maxjes= jes |V511 /13
exp
4 4( E) [Mp /A?
[maxjes= |V,13 /23 (n 5) (n t2gm3)
exp
AAS 4 4( +s)
123
n---I
n3
E [maxxee' /V 2
= exp
4 +E)
n---1 + n- aooe +2
Since:
n- 8 nio + 122
E
max
VVl
Xss, W 2 (1++ v1 - -0/2
log (p s).
Axp
jesc
n
22n²
28

---

Published as a conference paper at ICLR 2026
the above yields:
(1 n- nio
log (p 8)
P max jES
S Ap
[6)) < exp
(2++ n---1 + a m 2g0n
Apmn
2 2 + (1)) R=2 mon + moo
log (p 8)
exp
(2++))11+0)
nid 2ogn
(1 - 8) log (p s)
22 (1+ +
exp
p p 0.
Hence, we get:
T (6) 1= 0. max |V] S Ap
JES-
Taking the limit in (47) and using the fact that P(T (6)) t,0
O, conclude:
lim
P
max JES
|V S Ap O.
D.2.3 SHOWING THAT P (maxyes- [g] Ap) -
Proof of Proposition D.2 part (ii.) Let:
(8) = {I - E [Mpll 2 SE [MP]].
We have, by total probability:
Ap (T(T)) + +P)(
P
max VV
X/
$ P
max jESt
(48)
JES
Conditioning on Xss and W:
P max
Ap T (0)²
E P max
[Vg]
Xp
Xs, W
T (8)
JESC
Note that, conditionally (Xs, W), we have V, iid.
N (0. Mp). for j E S Using the bound on
expectation Gaussian maxima (see Theorem 5.3.1 in (De Haan & Ferreira (006)):
E
max [Vg] JES
Xs. W
2 2og (2 8)) Mp.
Conditionally T (8) have:
M, S (1 [Mp]
Hence, conditionally T (
E
max
Vil
Xs. W
Xp
jes-
S A
V
2 log (2 (1+
1
X3s
+ (n - 8) (nio² + n202)
2og (2 (p s)) (1+8) 8)
Ap V
n
n
log (2 (p- - 8))
log (2 (p 8)) (n 8) (ni +203)
/2 + 26
1
/2 + 28
s slog2 2
log (p 8)
(mo) n20 log (p 8)
(moff + n203) ) log 2
+
+
n -
n 8
n
23n²
N,n²
29

---

Published as a conference paper at ICLR 2026
Taking the limsup as p - too and using conditions
27 and 28
we get, conditionally on T (6)%
1
sup sup
E
max
Vil
Xs. W
p ++ Ap
jiES
2s log (p- 0-s) 5)
< limsup p++
(1+ 5)
(1+s) (2s log (p 8) + s + 1)
2s lol (p sp
I sup 0
(1+
(1+ (2s log (p 8) + s 1)
1 1
I+E
Fix 8 = 6/4. By the above, we know that for large enough n,, we have:
1 + E/2
E
max
V
Xs,
W
S Ap1
JES
1+s
V
/ I+e
For simplicity of notation, set tion of Gaussian maxima, for all 17 > 0:
O. In addition, we by Lemma D.3 on concentra-
1/²
P
max JESS
VVl
7 E
max
[V]||
Xs, W) S exp
jESc
2(1 + 5) E M,]
Let 17 = Ddp. Then get, for large enough:
P
max jES
[Vgl
Ap
Xs. W
P
max
[V > 17 + E
max jES
[V
Xs, W
JES
1/² 2(1 + 8) [M
S exp
X2
cxp
2(1 21++8/2)
A3a
(n-s) (n107 +
n-8-1
exp
2(1+5/2)
n- 7
n-
Substituting in the above, we get:
P max T
Vy
Ap
(6)
E
P
max (EE
VV > Xp Xs, X) (())
JESc
22
< E
exp
n2 +
2(1+ E/22)
8
+
n-8
nn---1
x
exp
2(1 + s//2)
8
+
n-s nio +
8---1
p p= 0,
since, by condition 28 we have:
o + n20z
(n1of + n203) log (p 8) p 0.
X3R²
X32²
Taking the limit in 48 and using the fact that P (T (6)) + O. we conclude:
I
max
VV, S Ap)
p 1.
JESc
30

---

Published as a conference paper at ICLR 2026
D.2.4 PROOF OF LEMMA [.]
Proof of Lemma D.1 Recall from 44 that:
EW
V,
Xs (xzXs) Ap [s (x5Xs)
X3 In
Xj+
n
for all E 8 Conditionally on Xs and W, the first term of the RHS above is constant and ltd (Xx) Jes- ~ N (0, I.). Therefore:
Vgl W ~ ~V (O,
where:
EW
== xs xx5 Xp Xs (x3 Xs) X Im
E RR..
Expanding the expression of A" A, we get:
A 125" (x)Xs) In addition, we have:
b+ 12 WT In 1 Xs -ss Xx3Xs)
x3] E.W
Cov (X j1s X3x) 81152tn
therefore:
Cov (V,, V22) = 6 A.
We conclude:
V Xs, W ~ N (0, (plss))
where M = AT A = ||All2-
D.2.5 PROOF OF LEMMA
Proof of Lemma D.2 Recall from Lemma D.1 that:
M, A (x5xs) -1 ++
WTS Io - (x -1 X3 EW.
n
By expectation of inverse Wishart matrices, we have:
23
E 125 (x3
Xs)
5)
|16|
By SraamSShhidh decomposition of Xs Meckes 2019).
we write:
Xs QR gaxe
(49)
with R. > and Q'Q I. where R E Rex is upper triangular (hence invertible) Q Raxs corresponds to 8 columns of a n x matrix of Haar distribution over the orthogonal group 0 (n). which we define follows:
U == IP
P
Q ~ Haar on O (n).
Then we have:
Xs (XFXs)
X3 QR (R"QQQQQ QR) RTQ
QR R) R Q²
QRR (R²) R² Q"
QQT.
Therefore;
J XX3xx -1 XT = T, TT-QQT PPT = PP Q)
In-s
0 s)xs
P
UNDU
Oex(n-9)
0sxs
Q
31

---

Published as a conference paper at ICLR 2026
where:
In-s (sx((ns)
0 xnn=s)x
D
0axs
Note that unlike U, D is deterministic. Since W-
N (0, In), we have:
E
E In- Xs (x3xs) -1 X3
EW
Xs
1
{ In Xs Xx)Xs) - x3] }}
n
π²
1 n
tr (E"UDU"
Hence, by total expectation:
E
Ln-
Xs Xx) -1 x3] "xp] EW
= Exx
1
tr
(E"
n
n2
1
(Exs
[E"UDUTT]]
n?
1
[UDU**] 2).
n2
By properties of the Haar distribution (see Example 1.8 of (Gu 2013
we have:
tr (D)
Haa-a))( [UT DU
I.
n
Substituting in the above, we get:
E
1 W In
Xs (X3xs)
X3] EW
n tr
EBu (UDUT] 2)
n
tr (D) ΣI
tr
n²
n
tr (D)
(y"" 1,
n13
n
tr (M Σ)
n²
(n-s)
(oln} + 120
n
Hence, we conclude:
X3
(n- 8) (oinf + n202)
E [Mp]
n1 - 5 - ||b|1 +
n2
We now compute Var (Mp). For simplicity, we write A = -n Xx (XIXs) X = UDDT.. so that:
Mp = 1257 (xxXs) -1 b n?
1 WTAW..
Therefore:
12 +2
M² = X/ 6T (xxXs)
6] + गe (w (AAWW)
o" (XFXs) "18] (WTTAWW)
np
Let:
Ti = 8e (X3 -1 -10"
T= = (W"EEWW)² T= & (xFXx) (WTΣAEW).
so that:
1
22
M₁ M + n
T2 + 2
TT3 n²
We start by computing E [T)]. Recall that XT.55 W. (I, We use the following result for second moments of inverse Wishart matrices from (isskidd 1972).
32

---

Published as a conference paper at ICLR 2026
Lemma D.4 (Second moment of inverse Wishart matrices, (Siskind 1972)). Let a, N with a b Lert E R and M E R and ~ Wo (T,b). Then:
(b ab a - A - = tt T + T T (t (b a -11. 1).
Setting b : n: = 6; : 1 and A = X5 Xs in Lemma D.4 get:
(n - s) (n 1 -- 3) L (x 66hh (x3Xs) | 66" + /// Le/ (n - -1). (50)
Multiplying by the LHS by 6dd on the left and by on right we get:
(1+ n (DTD)²
E [
(n 8) (n
s-3) 3)
Hence:
1 (n () sn s -3
(1+ n - s 1) |
E E[i
(51)
Now let us compute E [22). Since W N (0, have by moments of the multivariate normal distribution (see Theorem 5.2a and Theorem 5.2b in (Rencher & Schaalje, 2008) )
E T22 Xs] 2t (ΣAΣ)]] [tr (ΣΛE)}²
Lemma D.5.
We have:
E (EAE)))))
(n + 1) (n 8)
1
{
-moof n202)
(n 1) n (n 2) 1
n1
n 1+1
+ (ornf + )oozn
(n 8) (n s
+ 1) (n ((--s)
(x+1)
n (n 1 2)
(n 1) n2 (n + 2)
and:
E tr [ΣAΣ)?
+ (ornf n203)² )202)
2
s - s) (n 1) (n +
+ foln) +
n
n (n 2)
Proof. See appendix D.2.7
33

---

Published as a conference paper at ICLR 2026
Substituting in the expression of E [Tg] Xs] and using total expectation, we get:
E
[
= E E T2 Xsl]
EE tr (ΣAΣ)² 21
tr [ΣA]]² [3]
= -2 [r (ΣAΣ)*]
+ E [ir (ΣAΣ)]²
- imiof - n203) 2
28 (n - 5)
(n 1) (n +
+ (m1of + n205)
2 (n 8)
11 8 +
n2 - $
n (n + 2)
n2 n-1
+ foin) + ) 2
(n + 1) (n 5)
2
11 8
(n 1) (n 2)
m+1
imof) +
+ )202)
(n- 8) (n -888 +)
+n 1) (n - 5)
(n+1)
+2)
(n 1) n (n + 2)
=miof =
no02n 2
n-8
2s + (n+1)
n 2
(n nn + 2)
+ foow + n202)
n1
(n + 2)
(n 1++1)
n
2
(n --1)
[n+1]
x
2n 28
2
+ n +
n n-1
12
1 28 + (n (1+
= (niop - n202)
2
n
n-
(n - 1) (n + 2)
n +
+ (m + n202)
n1
n (n + 2)
(n + 1) -n---- (x+1)
2 2(n -s- -
x
3n 3s +4+
n-1
n-1
Therefore:
1
2
E [T2] (oin) + 2202)
2s + (n 11)
n n n
(n 1) n (n + 2)
(o1n) + +20
n (n + 2)
(n 1) nn 11-8 (m+1)
2 (n 5 1)
x 3n 38 +4+
(52)
n n-1
n
Finally, we compute E [Ts]. We have:
Xs] E { 60 (XFXs) -1 (WTEAEW) (s]
E T3
lo (xfXs) -1 E [TTAAWW Xs}
(x5Xs) 10] tr (ΣAz).
Recall from 449 that:
Xg QR.
34

---

Published as a conference paper at ICLR 2026
where Q E R and R E R* are independent, R is upper triangular with Ra 0 and Q²Q
Ig. Therefore, by total expectation:
E [Ts)
E
R [Ta Xs]
E
(xg Xs) 0 tr (ΣAΣ)
E
8e Xx) tr Σ In - Xs (x)Xs) - x3)
xx33 {}}
(RTTO QR) 1 tr Σ In QR QR QR)) RT² }/}
E
(R"R) tr (R- RT )1}}
E
ir E TT 1 QRR (R²) R² x0)=
E
(RFR) tr 2 (1n 2i}}
E
87 (RTR) (8 B(T EL (1) QQ") E|}
E
E
8 (R*R)
(8 t [E QQ7) m}}
07 (xzxs)
10 ] (ITUUUUU }
By expectation of inverse Wishart matrices (Anderson et al. 1958), we have:
B E{T T (xg
{ n- s -
5
Using this in the above expression of TE [T3] yields:
E [T3] = E {
6 (x Xs)
E { tr (ZUD)
1
h (r EU SUTDUT
8
1
EE [EUDD
tr
1
tr (D) In E Σ
n 8
2
n
tr (D)
(I²)
n (n - s 1)
(n-s) 8) (n1 of + n20 ?
n (n - 1)
Therefore:
(n - 8) (n + n2
|:,
E [
(53)
(n 1)
Now we have:
E [ (E [M,))
2
2X2 n
(n 8) (olof + n203n
E [Ti] + n
E [T2]
+
E [33
1 +
n
n
x2
E [gg
(n 5)²
poru) + n20
E [T]
(n - 8 1)²
n
n
212
8 sn - 8)
noios + n202
+ 3
E T3l
35

---

Published as a conference paper at ICLR 2026
Let:
8²
H1 = X/
[[Ti]]
(n 1)
E [72]
(n - 3)² (nioî + n20ž)²
H2
n²
n
and:
2X3 H3 =
s s(n 3) (nio} + n20
E[a3]
3
Then we have, using (51):
Hi
E [i
(1-3
E [M
(n- +non??
n n-
1122
[n=s)[n-8-3
12 ----1
(n-s-1)-
(n-8-1)²
= (n - 5 - -1)
1+ n
(n 8) - 90---33)
(n - s - 1)
(n 1)2
1+ n
-1
(n-s) 8) (n -3)
(1)
Similarly, using 522
H2
E [T2] n
(n - 8)² (n1of + n203)²
n
2s (n 8)
(n- 8) (n
2
(n 8)²
=(nio + n202))
+
(n- 1) (n + 2)
(n- 1) no (n 2)
n n
n
(n
(n + 1)
+ (ailf + )20z)
3n 3s + +4+
2 (n 1)
(x++1)
n3 (n + 2)
n
11
We have:
(n - s)² (oto} + n2
(E [M,))² >
n
36

---

Published as a conference paper at ICLR 2026
Hence:
H2 (E (M,1)
no
2s (n - 8)
(n 8) (n +
2
)
(n s)²
n n
(n 8)²
(n 1) (n +
(n - 1) no (n +
n +++1
n6
moo + 1202
n6
1
(n --s) 8)
(oln) + n203)²
( (n-ss) s)²
n5 (n + 2)
(n 1) n2 8
2
2 (n s - 1)
(x+1)/
x 3n 38 + 4+
n - 1
n1 - 1
2sn
(n + 1)
2
-11
n-
(n 1) (n 8) (n 22
(n - 8) (n - 1) (n + 2)
n2 + 1
+ 1101 + 12222
n
(nin} + m203g)
(n + 2) [n - 8)
(n + +] n (0-s-ratt) 2
2 2nn - 8 - 1)
(a+1)
x 3n 38 + 4+
n-1
n-
2sn
(nn+1) + 1)
nn-s- 2
-1] -
n m+1 1 -1]
[((n 1) (n 8) (n 2) + (n s) (n 1) (n + 2)
+ 110 + +120g
(n1n7 + n2222)
3n
4n
(nn - 8- 1)
a + 1) n2 8 8 (ut1)
(n
X
+
+
(n + 2)
(n + 2) (n s)
(n (n- 8) (n 10--))(m (n
(n- 8) (n 1) (n (n++2 2)
2nn
(n (n++1) 1)
2 -1}
13
n n-
(n
1) (n 8) (n + 2)
(n- 8)
1) (n 2)
n n+
niot
1202
io + +2203)²
(o1np + +2222)
n (n + 1) (n - (afa)))
3n
4n
2 2 1-1) 1)n
x
+
+
(n + 2)
(n + 2) (n -s) 8)
(n 5) (n 1) (n+
(n 8) (n 1) (n + 2)
2sn
(n + 1)
n n 1 -1}
2
+ (n 8) (n - 1) (n + 2)
11
1)
(n
8) (n + 2)
1
1
+
11
n2
(n 11) n - Tatt)) (n - 8) (n 1) (n + 2)
3n
4n
2 (n 5-
1)n s-1)n
x
+
(n + 2)
(n + 2)
(n - 8)
(n - 8) (n 1) (n 2
(1)
37

---

Published as a conference paper at ICLR 2026
For H3, using 5
2X Hg =
s(n 5) (oinp + m203) [Ts) n
n
n - -
2X3
s) sn1ng + n202)
8 (n 8) (mii + n203)
n²
n (n
1)
n 8-1
0.
Therefore, we conclude:
[MP]
(E [M,))
H1
H2 (E (M,))
H3
(1).
(E [M,))
(E [M,)))
(E [M,])²
D.2.6 PROOF OF LEMMA D.3
Proof of Lemma D.3
Define:
f: R
max Wi. RE
Note that for any u, v E R
(1))
max UN
max U/
[E[R]
KE(k]
S max (4 val EE
(u: 2z))
[k]
v
Therefore f is 1-Lipschitz. Assume 72 = 1. By Gaussian concentration of measure for Lipschitz Leeooux 2001 Massart 2007), have for all > 0:
functions
P [ N; E maxie(t) No] t) s exp (-f/2). N, E max4e[M) No t) S exp (-t2
P (max
The result for general 72 follows by substituting i == n/T.
38

---

Published as a conference paper at ICLR 2026
D.2.7
PROOF OF LEMMA D.3
Proof of Lemma D.5
We have, by Einstein notation:
tr [
2
DUDU Σ
EasUro [UT] de Dea
b=
C
Ea Dec
c=1
2
n a
Doa U =io
Du U rd aa
+
Σ Σ
Dan ac U2
D2 ac br an E +
Σ
D r2
aa [n] cm
Therefore:
E of [tr (IAΣ))
2 y E [Udc] aa
DonDarEua U
(n)
D2 2
E U2
asee [m] c=l
Σ
Σ
DoeDas 2M U
a#bE [m] cfde
We use the following result from Meckes 2019 on
Haar(n) matrices:
Lemma D.6 (Fourth-moment of Haar(n) matrices, Lemma 2.22 in (Meckes 2019 Let Haar (n). Then all i, r. 8, at B, X, p E [n]] we have:
E LUgUrsUUguunn
da + b + d100r10550p.
nn 1) n (n + 2)
+ t + 6er 8,0 sex d
n +1
+ (n 1) (n 2)
dindardssōg + d + derdra
39

---

Published as a conference paper at ICLR 2026
Substituting: i, a, = a; and j. = get:
[Uee]
deoder daadandedo + dooda
(n - 1) ri (n + 2)
+ daadaa dea daaded + Faddan
12 +
+ (n 1) (n 2)
Gaadaadodde + Pandaa + daoded
3 +1
+ (n- 1) (n +
(n (n
3
ni (n + 2)
Thus:
3
E [ ac
(54)
n (n + 2)
Now substituting i, a;j; j. c; and 3 d, get:
IE [Uac Vadl
Ban Fadded + Daa Sadded + daadaadedds
(n 1 (n + 2)
+ dandaadedde dandandeddas + daadaa
n++1 1
daadandecded Saadaadedded + dea deadaddodded
(n 1) n) (n + 22
2
11 n+
(n - 1)n (n
2
(n - (n-)) 2)
n (n (n++2) 2)
Thus:
U2d
(55)
ni (n + 2)
Now substituting i, = az 8,8, c: and a, À = b. get:
[
8an Sandeeee + Bandrsdande + dasdabdendec
(n - 1) (n + 2)
+ dasdusdeedee + dasdasdeeBec + de
n
+
daodrsdeddec + dapdasderd + dasdardeedee)
(n 1)n (n
n n+
+
daodaadeodas + daddedd + dasdaa
(n 1)n (n + 2)
2
n +
+
(n n (n 2)
(n 1) n (n +
n (n + 2)
Thus:
E [ bc
(56)
(n 2)
40

---

Published as a conference paper at ICLR 2026
Now substituting i, a; j. c; == b; and B. == d. get:
E [U20UPd Und
Sna Oradreddd + dnddaaed + dabdardeedaa + dasdabderdá + dardasdendaa + dabdardeadeed
(n 1)n (n
n++1 1
+ (n - 1) (n + 2)
Saadssdecdis + da + Sasdabdedded
+ 1
(n 1) (n +2
Thus:
n n
E 3[U2U22]
(57)
(n 1)n (2+2) 2)
41

---

Published as a conference paper at ICLR 2026
Substituting (54). (55) . (5)) and (7) in the expression of E { [tx (ΣAΣ)]*} above, we get:
E {(rr (EAΣ)]*}
Da -
[Uad]
+ +Σ
Σ
Da E
[ [nd]
cc
a=1 cade(1)
Σ
De
Uhd]
+ E
Σ
Dec an En Uhd]
an
a7DE(n] cml
atdE[nl axde(()
3 n nn +2)
Σ
Id
n Σ
D2
1
Σna
Σ cFdE/nl
DecDad
n n 2)
+
aa b6
2
Σ D2
n (n + +2)
[a/bE(M)
+
12 + 1
Σ Ens
Σ Deu Dad
(n 1) n (n 2)
ba (n]
(n + 2)
1
n
aa
3
Σ
D2c cc
+
Σ
Dod
crfid mm]
+ (n (n-13 11-1)n(e (n
n +
Σ
I 5
aa 4b
n
D2 00
+
Σ (etdE(n)
Dec Dus
n+ 1
[
a 54
12
D2
+
Dec
n nn + 2)
aaa
0c
aa=1
2
+ (n 1a--10 1) n (n +2
12 11 1
n1
Σ
D4
n 111
2
n
D2
cn
+
Σ
n
cc
tr (E:4)
(2tr (D²) + tr (D)}}
n(n+
+ (n 1) (n + 2) |rr (1r(22)² - to -1x=)))
n 1+1
2tr (D2)
n m1 + tr (D)²
mot + 220
2 (n 8) + (n - =s²}
n n(n+ + 2)
n +1
[o1w} + ) 2 (niof + f
1 1 (n - s)
+ (n - s)²
+ (n- 1) (n 2)
n a+1
= =mM10f + n203)² 2
(n + 1) (n 5) 1
{
(n 1) (n - 2) /
n2 - 3
n n+
+ io )ooz)
(n - 8) - 17n-822 2)
(n + 1) (n - 5) 12
(x+1)
2
n (n
(n 1) n (n + 2)
42

---

Published as a conference paper at ICLR 2026
Now have, by Einstein notation: tr [EAE)]]
= tr DUDDTE
1
Eas Des [U=] de
[= .es Dog [U"]ng Ing Eja
Lea Un Doo
eeo
=2 Ueh Dar
Die 2 E2
D2 pd U1
Σ
D& ac cc 22
+E Σ
Da U2. ah
a=1
a#eE[n] c=1
a=1 ctheln)
DoeDan E2 Ee
Ucc
a#FE[n] chh//n]
Therefore:
n
E Bfir tr (ΣΛΣ)E}
D2 5
cc na
ac
a=1
B
Σ
r 22 52 U2
affe[[n
Σ DeeDin E
E [U2c
Σ
afee [n] cthE|n]
Recall that:
3 n (n + 2)
E
Ut
and:
E
1 ec
=
E
[22 U2
ac
n (n + 2)
Now substituting i, i == a: j.j. r, e; and 3, == h in Lemma D.6 we get:
E Lec
1
daodendordor + dacdenderden + daodeadeodn
(n - 1) (n + 2)
+ Baedeaderhr
+ de
+2+1 1
Sac Saedeedcedni deedeaderden + den
(n- 1) n (n + +2) 1
(n 1)n 22)
Therefore:
E
=
(58)
(n 1) n (n 2)
43

---

Published as a conference paper at ICLR 2026
Substituting (54). (56). (55) and 58) in the expression of { tr (ΣAE)*
}
above, we get:
E tr {
1
n
D2 D
cc oe +
Σ
Σ
D2 22 22
n (n + 2)
n (n +2
cc au
a=1 c=1
afeE[n) c=1
Σ
DeoDin
n n(n 2)
a= apthe(n)
Σ
Σ
Der D2 D2
(n - (n 2)
affE(n) apthe(n)
3
Σ
D
+
Σ
D Dga D2
Σ
n
D2
n (n + 2)
(n + 2)
\a=1
asteE(n)
1
Σ
Σ
DooDih
11 on+ 2)
-aa
a==
52 x
Σ Dun
(n (n
Lee
Σ
D
3
4 aa
+
E2
x Lee
52
n (n + 2)
a=1
aFFE[[n
Σ
rd
Due
D2
n 22
ana
a=11
C=
c=
2
2
7
2
D2
(n (n 2)
aa
aa
cc
cc
4=1
c=1
c=1
2
n
a
D
+
n (n + 2)
a=1
1
n
D
D2
11 (n 1 2)
00
2
Σ
5
5
D
D2
(n 1) (n 22)
c=
44

---

Published as a conference paper at ICLR 2026
Thus:
E ( }
tr (D9)
{ 2tr (2:1) + (1127)*) + tr (E
n (1 + (D( tr (D9}
n(++2) 2)
(n 1) (n (n+ +2 tr (1<2=)- (Σ9) } to tr (D?)}
n
2 (n1of + n205) (moo n203)²}
oo + 2ggn n (n + 2)
{ {(1 5)3
(n [s)
nnn + 2)
(oiN) + ) 2 - (oru) + (202) } { (n 8)² (n {s}
(n- - 1) (n +2) 2)
= (mi) + n20z) 2
12 - 8
1 n -
(n + 2)
2 (n - s)
(n 8) (n 8 1) (n 8) (n s-11
+ (miof + m20z)
(n + 2)
n nn + 2)
(n - 1) 12 (n + 2)
= imid) + 220 2
8 (n s)
(n 1) n (n +
+ (#jo + 220z)
n -
n -
(n + 2)
D.3 PROOF OF PROPOSITION D.3
Proof of Proposition
D.3 Recall that:
U: U===e e n
(=xTXs
- XFEW 1pb
Note that conditionally on Xs, Ug is Gaussian for each i E S and:
[x (xxxx)
Y = LU Xs] - Apep
b,
1 T no
[ xxyXs)
1 [_xXX5 ex. X5
Y = Var U Xs]
Lemma D.7.
(a) The random variables Y; and Y have means:
Ap
nio + n
E E
n n c, and E E
(n s 1)
(b) Moreover, each pair (Y,, Y!) concentrated such that:
ndpvs
1 1 SK
P Y1
n 21122E1X.1)
111
122
where is a universal constant.
Proof. See appendix D.3.I
Now define the event:
ndps Y2
U
1 or Y
2
2E [Y1
n
n
45

---

Published as a conference paper at ICLR 2026
By union bound and statement (b) of Lemma D.7 we have:
ndpvs
(TT) -
[
or |r 2 2E [Y:]]
n n-
8
iE8
1 +
1
S sK
1/2
= K
11
which converges to 0 as + toc Conditionning on T, we have by total probability:
P
max iE8
U 2
P
P
max U3 2 p T iES
+P (T)
S P
max U₁ 2 pl |T iES
+ K
8
711
112
In addition:
P max U. 2
T
= E
max U. 2 pj TT iES
iES
E
E
max Us 2 2p] 1 1 Xs
IES
U, 2 p 2 T", .Xs)) ]
E
PP
max iES
Now we have:
max U, 2 p T", Xs IES
S TP
N; NY(.Y)
max N₂ 2 p T
iES
max N; 2 P) iES
S IP Ni No ndpus 2(zle7+nze())
2P)
i----1 a(--z-))
where:
The first inequality holds because the maximum of independent Gaussians has heavier positive tail than the maximum of correlated ones (under the same distributions).
The second inequality holds because Gaussian with larger mean and variance has heavier positive tail than one with a smaller mean and variance (therefore each of the Nus would have a heavier tail if its mean and variance were equal to their respective upper bounds).
For simplicity, we drop the long subscript and assume N₂ iid N Markov's inequality in the above, have:
udv 2(m19++2003) n---1 n(n-s-1)
Using
E [maaxies No]
IP
max U, 2 p T TxXXs SP IP
max N₂ 2
(59)
FES
VES
Using the formula for expectation of Gaussian (see Theorem 5.3.1 in De Haan & Ferreira maxima, we have:
2006
nd nXpV5 n s
2 [n + nz03) n (n $ - 1) (n1of + n20 log (s)
max N iES
S
+ V
2 log (og) (s)
ndpvs 5
+ 2
n 8
n (n 8 --1 1)
46

---

Published as a conference paper at ICLR 2026
Therefore, have:
IP
max U² IES
P)
SP
max Uj 2 P (3) K
iES
n1 n22
max Uj 2 p T (xx Xs )] iES
E
p
K
+
12
112
59
ndpV5 + +2/
(nioî n20 log (s)
-
+ K
n1 (n
- 1)
n1
122
Hence we have:
IP max Us 2 p) - ApV8+ + / /m109 + n203) log (8)
(1 (1+ op (1)) + op (1),
(60)
IES
n²
which converges to 0 as p + too under condition same bound for { (-Uihes that:
28
Using a similar argument, we establish the
mmof n203) log (s)
P max iES
(-U,}
S Ap/s+
(1 op (1)) + 0 (1). (61)
2
Bringing together (60) and
66 and using a union bound, we conclude:
P max U.I <D) p- 1.
D.3.1 PROOF OF LEMMA D.7
Proof of Lemma D.7
Mean of Y, Recall that:
Y Axpe (Hxxxs) -1 -= (xFXx) -
Note that X5-Xs W. (Ls, n). Using properties of the Wishart distribution (see Lemma 7.7.1 of (Anderson et al. 1958)), we have:
E [xxxx)
12 1 Is.
1
Therefore, we get:
A nl
E
e
(62)
n
1
Mean of Y. Recall that:
Y n²
1
of
L (xx3Xs
X
(xxxx)
n
1
Ci
n
e (XFXs) x5 X x5) ex.
Now recall from (4) in the proof of Lemma D.2 the matrices Q E Raxs R E RK*K, U E Rax such that:
X5 = QR, U = [P Q] where Q'Q = l.. R is upper triangular and U ~ Haar (n). We have:
Y of (x
- X (X 6,
= c R² R) e;
47

---

Published as a conference paper at ICLR 2026
Note that:
p2_] Q²] Σ
5T QTEE
E2 QTEPP
p QTE
UT
Q
[P
Q
Therefore:
E P
E Q [QTT'O]
E -
E
On the other hand, we know by the properties of the Haar distribution (see Example 1.8 of (Gu. 2013) that:
E E tr 2
11 + 220
In
Hence:
on +
m20 1.
E
n
Therefore:
E [Y,] = Eq.
c R
6q]
E E
1
E
[
(R*) c
E
[
(RT) -1 e:
1107 + 2o5n
(H²?) 11 43
n
moot + n20
E of (R" R) [.]
n
ooot + 222
T (R. R) I- E.
E
n
noo + 220
E e (xF
noo? + n
of e
(n 1)
mo + 2
(n 1)
Concentration of Y, Recall that:
Y, == -> (X5Xs) -1g.
Thus:
Y2 =Y, = Xnnee (XF -1 66 (XFXx) es.
Taking the expectation and recalling
(50) we have:
E | = X5n2 e
(x Xs)
15T (XTXs) -11
|b1 Is/ (n (n-
s -- -1) ei
3) (n 8)
X312
824 +
b
(n - s 1)
(n - 3) (n s)
2
2,12
1
(n 3) (n s)
n
48

---

Published as a conference paper at ICLR 2026
where the last equality above holds because i = sign (3*) and i E S = Supp (8*). Thus:
X2 (n 1)
E [
(n (n-s- 10-s-3) 3) (n - s 1) (n - ss
Recalling (62). wc get:
X²1² (n -0-1
- Ap 1/ TT
Var [Y]]
(n - 3) (n- - 1) (n 5)
Xzn² (n - 1)
X3n
(n (n-8 8 - 3) (n - 1) (n 8)
(n - 8 - 1) 2
Xnn2
(n - 1)
1
(n 8 - 1)
(n-8 8 3) (n 8)
Therefore:
Var [V]]
(n 8 - 1)²
X3n²
(n in-1) 1)
1
X
(E (Y1)2
2
s s23n²
(n- 8 - 1)
(n-s 3 - 3) (n - s)
- 8 -
1 (n 1) (n 8 1)
1
8
(n 3) (n 8)
n2²
n18 + 11 + 1 n²² + 118 + 118 5² + 3n -35
(n 3) (n- - 8)
1+ ns - 52 + n 2s
8 (n - 8 - 3) (n 8)
θ
Now using inclusion and Chebyshev's inequality, we have:
P
Yil N n- 8--
ndp/s
62
P Y [x]] 2 [x.] (Vs- - 1))
1
Var [Y]]]
(V3 1)² (E (Y:))
Var [YG]
-
(E [X2)2
+ 17
In particular, the above implics:
Y 71 /3
(
+
1
P
0
n 1
n1
m
Therefore, the exists a universal constant K1 > 0 such that:
P Mil ndpV3 n - I Ki
1
1
+
(63)
11
712
Concentration of Y.. We have:
2 (x:)² 2 R E (6"=-10'=" e,²²
R
=B ((=' 2
R
49

---

Published as a conference paper at ICLR 2026
We have, by Einstein notation:
R ia
[Q]]
ab [>> be Qce [1²²)
-1
oi
R [Q']
[> br Qce (R-1)²)
Jes
ab
R [07] ab [>a]] be Qan [R[ 60
R1
Qca 2ea2220 Qoe [1 iee
[R [R 1R-1 ie Qca
cc
Therefore:
(1-))) )²
2 R 1ma [R_ ie QcaPco
2 [ ia [R-1] QeaQec) Qce) 2
cc R [R-1] "1o Qealen) (I 1 [R iss Qca QoaQes)
/E|
"
E2 [R-1 la
[R 11 Qce) (Ecc [R-1] 11 lie QctQon)
BY (s)
Σ
( [R_1] Jia [R Qca) (2e [R [R QeaQes)
Sa [RT"] Qca (2i2 [R Ina " Qae) [R-"]
crde (n] d=l
1 [ "] i] R ]] in Qca Ein R "1, [R Qua
onde a=1 fE(s)
[R-1] in R [R- Qce)
(E2d [ -1 [R'1] 2] QuoQua ie QceQ
cdde [n] at [s]
Σ Σ
(>2 [ ia
[
(22e [ "1. [ ' Qw)
c#de(n) a fE(+)
50

---

Published as a conference paper at ICLR 2026
R [R112
2
[
2
O Qac
in
ie
M
Lc [1-1)22 R
[ Jf Dea QeoQes
fff
[R-
[R- [R-
ie Qct
ia
affbE
R [R ie [R Iss Qcl R [R]
cc
c=1 a eff
Σ
20
[R-1]2
[R_1]
[se Qda
iaa
ode [n]
X 52
[R [ [R-1]
[R' [R "lis Qda
0c de
La
e#dE|n] a=l c=le//En EElo]
Σ
Σ
De dd
[R
[R-
R ie
Qca Qath
ia
(de[in axbE((s [8]
Σ
2 2.2
[R-1
R
[ R I) Q
cc
@ddEin axb cffE(s
R-1
R-
[
Q² Q2
00
la
in
4
R
R
R
"les Qea Rce
la
lie
Σ
E4 [R-
[R-
R
[R
11 [R [R' ") Qea
la
abb [s] effE
2 R--1
1-112
R-
Qca Qco Qaa
ia
ie
og [n]
+2 Σ
2 2 [1- 120
[R [
'l Quaa
Die
c a=1 exf
Σ Σ
Σ x2 [
[
ie [
R
1
QcaRoe
la
cædE(n] ( (f((
51

---

Published as a conference paper at ICLR 2026
Taking the expectation of the above conditionally R and by independence of Q and R, get:
E (y?)²
=E
-1
R
R
R Ii E
[Q 0
M [ [
iic [R 1, E 1ea 2ot
e= @= e
N [R-]]
[A_1]]
[R [R]]]
1ie [R''] "Iss E Qe
-id
16b
af ( (+))((s)
Σ
20 [ 11
[ 1] E
La
eddE|n a=le=1
2 Σ
E [R']]
[R- "1
R "I, E [Qaa Qce Qaa
odd[(n] a=1 fC
Σ Σ
Σ
2 2
R-1
R
R "0-1
lic R "I, EIQ.aa
0c dd
cfdE|n] axbb[[s]
fffE
Now recall from Lemma D.6 above (by Meckes 2019)) that for all 8, [n] have:
E
UU UaDUUsu
o 0ar + d + dia 810
(n- 1) (n + 2)
+ & 8128ra818834 dudra
+ (n - 1) (n + O + d + dixdradja
n+1
Also, recall from 49 that:
U U P Q).
hence for any a E [m]. 8 E [s]:
Qas = Ua(n-sta
(64)
Since the above fourth-order formula only depends indices through Kronecker deltas, holds that for any i, a, X E [n], j. a, 3, [s]:
E Prs QAy)
oepdardnode + drpdrrrn + drabr20
(n - 1) (n +
+ t 63. + 8 dix 6000eu
n ++11
8indardra 61a d d
(n- 1)n (n 22)
52

---

Published as a conference paper at ICLR 2026
In addition, note that the expression above is equal to when one of {j. a. a. fu} is different than
all the others. This observation simplifies the expression of E (Y:)) R above as follows:
E
(Y;)²
|
R R
[R-
Jsc E
[Qeh 2z1
oc
ia
cm
Md cc
R-1
[R-1]
ie ib [
[R-"),
[R
E
c=1 azbE (s] (f(E(M)
R
R
112 ic
E
[Qca
Qde
di
cdd 6=1
Σ
D de
R
R
[R E
R
ib
oFdE[n] azbE[d] [E|{]
Thus:
E (Y/)²
Σ4 R
E
[tta]
in
2cc R 12
E [R-
[R
[Q2 Sae
in
c=1 a
Σ
Σ
ib R 1ia [
RR!
iic [ [
a#bE|a c#fE[s]
x E 1 Ces
Qen 2all
((aab) = (e,
ΣΣ
R
R 1,,
cc
5h
[s]b cffE(s)
E Q eb Q 00 Qoll ((abb) (f,e))
2
114 E [ 03
"00 dil
eddein a=1
Σ
2
R
2
[R
')² E
[Qca
00 dd
Jia
cdde|n] [f)
Σ
Σ2 E
R
R
R
1cc R "),
Ad
cdd][n] cebE[s)
x E
Qua
Qarl {a, b) = (e,
ΣΣ Σ cfdE(n) axbE((s)
Σ Σ2 52
R
R 11 ih
R Ii [R *]
E
Qua
Qus se ((a.b) (f.e))
53

---

Published as a conference paper at ICLR 2026
Thus:
E
(x7)²
R =
[R1
RR-
B [
cm
a
M
cc
[R
R
Jsa
[R
[Re
lee
E
[ 0
a
R
Lia
R
E
[Qe Qab
a#bE(s)
E4
R
112
[
E
Q2 S
00
ia
ib
a=bE(s)
2 2
cc dd
[R
R
lia
E
[ Q
ofdE [z] a=1
2 2
[R-1]
[
R 1 E Qdc
oz dil
oFd n| a
> 2d
[R [
[R-1] " E [ 2aol
og [n] (s)
2
R 12 E 1Q Qes [R-1]2
dd
cftie n] agEDE(s)
Hence:
E (Y:)) R
11 [R-1]
E [[O0
in
+
4
R 1
R 1 E
10 Q²
c=1 ag/bE|a]
2 dd
R
1 in
E
122 2do
oF [n]
2
1
R "
ER [Q Cun
00 dd
lin
of [n] af
+2
Σ Σ
2 2
R--12
R 112 E EiQca Qe 1b
oz de
c#dE|n] axbE((s)
Now recalling (5))
155
56
57
58 and using (64) we have:
E [+4]]
n (n + 2)
1
E
[Q P2t
= E [Qaa Q
(n 2)
E Q2 Q2.l = (n 1) n (n + 2)
n1 +1
1
E
2e Qdal
(n 1) n (n+ 2)
54

---

Published as a conference paper at ICLR 2026
Therefore:
E
(x7)²
2
R
2e [R
[
Tea E [Qom]
c=
a=1
+
Σ
R 1 2
[ [R_ E [ L.h.]
cc
lia
cm ay
0c dd
dil
R
in
E
[ Paol
Σ
22
R
R 11 E [Q2 Pao
dd
ofdE(a [n] a
+
E
Σ
Σ وの
[R-1]
[R 1 [R-
ia
ofd mn] as)
Thus:
E (v?)² |R]
3
R 114
(n 2)
c 1=1
3
A R
[R-
Jia
[R_
n(n+ + 2)
c=1 astbE [s]
1
2 2 cn dd
R 114 4
n n + 2)
of [n]] a=1
12 n+1
[R-1]2
La [
(n - 1) + 2)
cødE(n) axbb[[s)
2
Σ
2 c0 dd
[1-1]
[R
12a [
2 100
(n n (n + 2)
cfdE(1) a*bE(s)
Thus:
E [x:)² RR]
3
End
R 1]= + Σ
[
[R-1]]
n (n + 2)
in
+ n (n +
Σ cdde[[)
E 52
R +
Σ
111122
R
2
[
1
2
10
n 3
44
2 52 40 dd
R
12 [
2 ah
n nn +
0c
c=
cddE(n)
2
n
3
+
Σ
22 Lcc
R
n (n +
cc
cc
c=1
1
f2th (E*) + tr [Σ))²]
R
n (n 22)
ia
1==1
55

---

Published as a conference paper at ICLR 2026
Now note that:
of (x]Xs) -1
(1tT R) -1
R- (R ")"]
1s6
[R 11
[ 77
|
RR1 1 im
R
a=1
R
2
ia
On the other hand, recall that X5Xx Xg Wo (J. Setting b = n; == 8; == 65; T == Is and
A == X3 Xs in Lemma D.4 we get:
E (XFxs) cxe_ (x5Xs) -1
1
(aee + (cf Is/ (n - 1))
(n 8) (n --3) 3)
1
1 1,
ceee"
n ----1 1 11
(n 8) (n
3)
Therefore:
E
( (X3xs) -1a ") e (X5Xs)
exc_ Xs)
7 C2
E (x e.c (x5Xs)
'I1
1
1
cee
n - 11)
(n (n- 8) (n - s 3)
Hence:
27
E Σ
R
112
= E [el (xīxs) Xs) -1 {
(1
nn 5) (n s 3-3) 3)
a=1
Hence, we get:
[X:)) 2
E
E
E
(Y:)² | [R]
E
1
21r (IA4 + tr (I9)²)
Σ R 11-
n nnn + 2)
1
2t (I*) + tr (Σ9)
E
R
112
n (n + 2)
in
a==1
1+
n1 s )
(2tr (2*) + tr (22))2}
(n (n-s) 8) (n - 3) n (n + 2)
2 ( + m20z) + (ni0s + n203)²
2
1
1+ n n 17-
(n s) (n -3) (n + 2)
56

---

Published as a conference paper at ICLR 2026
Therefore:
E (V!))
(E [
Var (Y?)
(E [X]])
(E (E])
A(moot+nz0 +mao))
1 m
+ng02
(m-s)(m- ()+(+22)
n(n---1)
a(n-s-1)
2m1o (m +220
n-s-I -
tn3o 2
(n-s)(m-- 3]x(n+2)
m(n-s-1) 5-1)
nyo t2za
a(n-s-1)
n (n 8- 1)
(niof + n20z) + (mrof + n20z)
nn 8) (n 3) (n + +2
(mlof + o200))
x 1+
-1
11
n2 (n - 3-11 1)
2 (njot + n20z) +1 -1
(n-8- (0-8-3) (n+ 2)
(n1n) 220
n n --1 1)
2m + 2nz
+1
(n-s- s 3) (n 2)
niot
n20 + 2n 22
n n 1)
2
2
1
-
(n (----3) (n 2)
71
n2
n - 8- 1)
2
2
(n - 1)
+
3) (n+ 2) 1
(n s 3) (n + 2)
11
122
(n
n (n -
2
2
(n - s 3) (n + 2)
71
722
n
n
+
ns
3n
2n + 2s +
(n - 8
3)
(n + 2)
n (n -
2 2
2(s + 3)
nn 8 - 3) (n 2)
71 n2
(n 8 - 3) (n + 2)
Hence there exists universal constant K₂ such that:
Var (Y?)
S K₂
E [Y?1)²
121
n22
By Chebyshev's inequality, we conclude:
P (Y 2 22 K₂
(65)
n1
n22
Bringing together (63) and constant K > 0 such that:
665 and using union bound, we conclude that there exists a universal
ndpV
or X 2x:1) s K
++ -
IP
(66)
n
112
E PROOF OF PROPOSITION
Proof of Proposition First, assume there exists (Ap) p21 - such that (28 holds. By the first
part of 28). we have:
Lug log (p s) = 0 (2?)
(67)
57

---

Published as a conference paper at ICLR 2026
Using 67 and (22)p21 0, get:
avg log (p 8)
0.
(68)
In addition, by the second part of 28 we have:
pz
x = 0
(69)
Using 67 and 669. get:
2 avg
log (p- - 8)8 0.
(70)
np²
Taking the sum of (68) and 70 we obtain:
0 Fvg
log (p-
5) (1 + s/p²) 0.
Hence, we conclude:
G = o
n
(1 + 8/ p2)
log (p 5)
Second, assume (30) holds and let:
1/4
ong log (p - 5) (1 s/22//2)))))
Ap =
Then we have:
Rug log (p- 5)
X2 V (1 + 8/ p²)
By 30 we have:
ni log (p 5)
12 = (V
(1 22)² log (p 8)
= 0
1+p/p2
thus:
X (1 + 8/p²) - 0.
Therefore
Ap 0 and ApVá
(71)
In addition, we have by definition of Xpp
nx
T log (p - 5) n²
2 log (p- s)
1 avg log (p x)² (1 + s/ ) n
V 2ig (1 (1+ s/p²) ) log (p - s)
Therefore we have, by 30
n
+00
(72)
a2 avg
log (p- - 8)
Finally, by 30 it holds that:
log
n log
npp
np2 (1 + s/p²)
log (p 8)
1
1
= 0
p²
+
Therefore:
1
2 log 0. ave
(73)
Bringing together (71).
72p and conclude that Xp 0 and 28 holds.
58


Reviews:
[{"review_id": "5mh6W4PSRu", "reviewer": "Reviewer_dyNa", "summary": "The paper studies the problem of support recovery from noisy observations in a linear regression setting with Gaussian design. The design is assumed to be centered and isotropic, while the noise is Gaussian with zero mean and a diagonal covariance matrix that takes two possible values: $\\sigma_1$ and $\\sigma_2$.\n\nThe paper focuses on two types of results: first, sufficient conditions for the maximum likelihood estimator (computationally inefficient) to consistently recover the support, considering both the ill-specified and well-specified noise covariance matrix cases; second, sufficient conditions ensuring that the Lasso estimator consistently identifies both the support and the sign of the regression vector.", "questions": "- Since in Thm 3 it is required that $s=o(p)$, can we replace $n_{Alg}$ by its asymptotic equivalent $2s\\log (p)$?\n\n- Can we generalize Theorem 2 to arbitrary matrices $\\Sigma$, just by replacing the LHS of (15) by $\\sum_{i=1}^n \\log(1+\\frac{\\delta s}{2\\lambda_i(\\Sigma)})$?\n\n - What would happen if, in **Theorems 1 and 2**, we replaced the condition that nonzero elements are equal to one with the condition that they are either $1$ or $-1$? Would sign recovery still hold under the same conditions?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem of recovering the support of an unknown vector is a fundamental challenge in statistics, frequently regarded as a prototypical case for mathematical results on variable selection. Exploring the information-theoretic and algorithmic limitations of this problem holds, in my opinion, significant interest for the ICLR audience. \n\n - The mathematical proofs, as far as I could check, appear to be correct. \n\n - The proof of Theorem 3 overcomes some non-trivial technical challenges.", "weaknesses": "- I suspect that **Theorem 1** is not sharp, for two main reasons:\n  - When $n_2 = 0$ (i.e., no low-quality data is present), the theorem's condition requires $n_1$ to exceed a quantity involving $\\sigma_2$. Intuitively, $\\sigma_2$ should not appear in this condition under these circumstances.\n  - As noted in lines 265–269, if $\\sigma_2 = o(s)$, the condition becomes independent of $\\sigma_1$, which seems counterintuitive.\n\n- The conclusion at the top of page 6, *\"one unit of high-quality data is worth at most 2 units of low-quality data,\"* does not seem justified by **Theorem 1**. The theorem provides only a **sufficient condition** for recovery, but it does not rule out the possibility that the maximum likelihood estimator could detect the support with a smaller value of $n_1$.\n\n- The conditions under which the results are proved, although similar to those required in many papers on this topic, are quite restrictive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1bHMIoUVcn", "reviewer": "Reviewer_zQsn", "summary": "The paper studies the problem of sparse signal recovery in the mixed-quality data setting: where a subset of the data is observed with low noise, and the complement observed with different (higher, w.l.o.g) noise. They study the information theoretic thresholds of the problem, and demonstrate that the maximum likelihood estimator in the gaussian noise setting has significantly different behaviour depending on whether one is agnostic or not to the noise variances. They also analyze the LASSO and prove that it is robust under this model.", "questions": "Questions asked in the “Weaknesses” section", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is original, they study a timely problem and do so with an original look at a new variable called the price of quality. I must mention that such problems were already considered in the heterogeneous statistics literature, but they were moreso concerned about inferring the heterogeneities themselves, rather than quantifying downstream implications of standard models on mixed quality data. In this regard, I find this work novel. \n\nThe work is clear, and is of high quality as the authors investigate various aspects of the problem thoroughly. \n\nThe work is significant, especially in the era of AI, where models can often be trained using a mix of real and synthetic data. In particular, the authors clarify their findings and present them as important and non-trivial rules of thumb for machine learning, such as that in the agnostic setting, where one high-quality sample is never worth more than two low-quality samples.", "weaknesses": "I found no major weaknesses in the paper. Following were minor comments/questions: \n\n- The information-theoretic and algorithmic thresholds in (2) are mainly for Gaussian noise right? Or have these been proven for additive noise more broadly? Please clarify this, and maybe state earlier on in the work that you consider additive independent Gaussian noise.\n- Typos: First paragraph after 1.2.1, “In the first part of [our] work ([S]ection 3) …”. In the next paragraph: “, the condition requires that a linear combination of [?] has the form …”\n- A bit more clarification as to how \\sigma_1, \\sigma_2 scale w.r.t other parameters, and remind this throughout the paper.\n- Your results in Theorem 1 are mostly relevant for additive (sub)-Gaussian noise, please clarify this and that your sufficient conditions (and therefore findings) are not universal over general additive noise.\n- End of page 7, you mention “OGP” but do not explain/state the full name or what it is. It would be good to get more background on that.\n- Could you comment on how this relates to existing statistical work on heteroscedastic regression, and whether you expect improvements for algorithms which first estimate the heterogeneities, then proceed to weight samples accordingly?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dvKhwqvWhj", "reviewer": "Reviewer_QshA", "summary": "In this paper, the authors study sparse recovery from noisy linear observations of mixed quality. To be more precise, they seek to recover an $s$-sparse ground-truth $\\beta_* \\in \\mathbb R^p$ from $n$ observations\n\n$Y = X\\beta_* + Z \\in \\mathbb R^n,$\n\nwhere the measurement process is modelled by a Gaussian matrix $X$, and the entries of $Z$ model random noise and are zero-mean Gaussians. For $n_1+n_2=n$, the first $n_1$ observations $Y_1,…,Y_{n_1}$ are of high quality (modelled by noise variance $\\sigma_1^2$) whereas the remaining $n_2$ observations $Y_{n_1+1},…,Y_n$ are of low quality (modelled by noise variance $\\sigma_2^2 > \\sigma_1^2$). The authors consider the agnostic setting in which the recovery method has no information on the data quality, and the informed setting in which the recovery method knows which noise level applies to which observation.\n\nTheorem 1 provides sufficient conditions on $n_1,n_2,n$ for asymptotic support recovery in the agnostic setting. The result shows that asymptotically a high-quality observation is never worth more than two low-quality observations.\n\nTheorem 2 is the counterpart of Theorem 1 in the informed setting and shows that depending on the ratio between $\\sigma_1$ and $\\sigma_2$ a high-quality observation can be worth more than any number of low-quality observations.\n\nFinally, Theorem 3 analyzes sufficient and necessary conditions on $n$ to achieve support recovery algorithmically.", "questions": "Since the results are interesting and the derivation appears to be rigorous, I do recommend this paper to be accepted. Due to the limited reviewing time, I have only loosely screened parts of the supplementary material, so I cannot confirm correctness of the presented results. They appear to be reasonable though.\n\nWhile the paper is well-written and easy to read, the notation can be improved at certain points and there are some points that should be corrected:\n\n- X,Y,Z are all upper-case although X is a matrix and Y,Z are vectors. In contrast $\\beta$ is lower case. This is confusing.\n- l. 126: „… a linear combination of ??? has the …“\n- l. 199: Maybe I missed it, but I think Z_1,Z_2 are used without being defined\n- l. 235: Can you comment on the fact that your required size of n_* is smaller for s=p than for s=0.5p? Clearly, there is less ambiguity in the possible supports, nevertheless, this is rather counter-intuitive and should be properly discussed in the paper.\n- l. 251: „…Chernoff bound to the LHS…“ -> Shouldn’t this be RHS?\n- Eq (11): $\\sigma_4^2$ -> $\\sigma_2^4$\n- Remark 3.2, second bullet point: It would make sense to mention that the proposed estimator is motivated by the MLE discussed afterwards in Section 3.2\n- Eq (20): This should be argmin and not min\n- l. 604: $\\hat S$ is only an element of the argmin not necessarily the only solution.\n- l. 725: If I'm not mistaken, you apply Markov’s inequality here, and not a Chernoff bound. This would need to be adapted all over the document.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ Rigorous results\n+ Study well-motivated via mixed quality data in learning problems", "weaknesses": "- Algorithmic recovery is not analyzed in the informed setting", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gcuZgPpRi9", "reviewer": "Reviewer_6vxY", "summary": "Sparse recovery has typically been discussed under the assumption that noise variance is constant (homogeneous noise). However, real data often contains a mixture of a small number of \"high-quality (low-noise)\" observations (e.g., expert measurements) and a large number of \"low-quality (high-noise)\" observations (e.g., crowdsourcing or LLM labels).\nThis paper theoretically analyzes the support recovery problem for a sparse signal $\\beta$ under mixed-quality data and defines two bounds:\ni) Information-theoretic bounds: What sample size (n₁, n₂) is theoretically necessary for recovery?\nii) Algorithmic bounds: To what extent can LASSO recover the signal?", "questions": "I understand that this paper is theoretical and not intended the practical usefulness. But, I would like to ask about its practical relevance. I could not imagine example problems for which the setup assumed in this paper are realistic. Can you raise up some?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: This paper  newly introduced the viewpoint that the Kronecker product structure is equivalent to \"measuring a multidimensional signal at multiple stages.\" Based on this idea, it developed a signal recovery algorithm that operates with low computational complexity.\nQuality: The developed algorithm reduces the run time for the recovery by $O(10^2)--O(10^3)$. In addition, theoretical guarantees are presented mathematically. The performance is also validated numerically. In summary, this paper is of high quality. \nClarity: The writing is well structured and the results are clear. \nSignificance: The results obtained in this paper are expected to bring significant advances to the problem of compressed sensing with Kronecker structures.", "weaknesses": "For problems where compressed sensing with a Kronecker structure is useful, the sparsity structure must be independent for each dimension. In the introduction, this paper mentions that there are examples of this in radar imaging and wireless communications, but does not provide specific examples. It is unclear how useful it is for practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)