Minimax-Optimal Univariate Function Selection in Sparse Additive Models: Rates, Adaptation, and the Estimation-Selection Gap
Authors: Shixiang Liu
Venue: NeurIPS 2025 spotlight ()
Keywords: sparse additive model
variable selection
minimax separation rate
FDR + FNR control
Hamming loss control
Primary area: theory
TL;DR: We establish non-asymptotic minimax separation rates for univariate function selection in sparse additive models, and discuss the difference between optimal estimation and selection.

Abstract: The sparse additive model (SpAM) offers a trade-off between interpretability and flexibility, and hence is a powerful model for high-dimensional research.
This paper focuses on the variable selection, i.e., the univariate function selection problem in SpAM.
We establish the minimax separation rates from both the perspectives of sparse multiple testing (FDR + FNR control) and support recovery (wrong recovery probability control).
We further study how adaptation to unknown smoothness affects the minimax separation rate, and propose an adaptive selection procedure.
Finally, we discuss the difference between estimation and selection in SpAM: Procedures achieving optimal function estimation may fail to achieve optimal univariate function selection.

Minimax-Optimal Univariate Function Selection in Sparse Additive Models: Rates, Adaptation, and the Estimation-Selection Gap
Shixiang Liu School of Statistics Remmin University of China Liushixiang_stateel statilnnnngsttttteeeeeeeee edu.
Abstract
The sparse additive model (SpAM) offers trade-off between interpretability and flexibility, and hence is a powerful model for high-dimensional research. This paper focuses on the variable selection, i.c., the univariate function selection problem in SpAM. We establish the minimax separation rates from both the perspectives sparse multiple testing (FDR FNR control) and support recovery (wrong recovery probability control). We further study how adaptation to unknown smoothness affects the minimax separation rate, and propose an adaptive selection procedure. Finally, we discuss the difference between estimation and selection in SpAM: Procedures achieving optimal function estimation may fail to achieve optimal univariate function selection.
Introduction
The Sparse Additive Model (SpAM) is a pivotal topic of recent statistical research Ravikumar et al.
2009 Meier al. 2009 Koltchinskii and Yuan 2010 Raskutti et al. 2012 Dalalyan al. [014
Yuan and Zhou 2016 Lyagi et al., 2016, Tan and Zhang 2019 Haris et al. 2022 extends the
generalized additive model Hastie and Tibshirani 1987] balancing interpretability and flexibility
while avoiding the curse of dimensionality and adapting to high-dimensional settings.
In this paper, we focus on the variable selection, i.e., univariate function selection problem of the SpAM, which is a fundamental problem with broad implications in multi-channel detection [Ingster and Lepski| 2003), multi-task learning [Wang et al. 22020) sparse neural network eXu al. 2023 and so on. We consider a Gaussian white noise (GWN) model with p covariates æ -I Ip) E XP,
which takes the form
dY, = f + odB, = Σ fz(z))dz, + odB,,
j=1
where X' is the domain of each covariate Zj, B, a standard Wiener process on X", and o measures the intensity of the white noise. We assume f, is the univariate function corresponding to variable zy. Under the setting of sparsity, the response Y, influenced by no more than s covariates, and hence f can be expressed as f(x) EEes, fı;z) where Sy C -1, .P} is the index set of these support covariates. In this continuous-time SpAM framework, the index set Sy. i.e., to select which fú * O. This paper studies the univariate function selection in SpAMs from two perspectives nanelly recovery problem. We employ the truncated procedures and establish the asymptiii minimax separation rates, delivering, to knowledge, the first optimal finite-sample guarantees for univariate function selection in SpAMs.
main goal
recover
sparse multiple testing problem and as support
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 Related work
The variable selection problem has attracted significant interest recently [Butucea et al. 2018 Rabinovich et al., 2020 Belitser and Nurushev [022 Song and Cheng
Background of variable selection
2023 Butucea et al., 2023a Abraham et al. [0244]. The general assumption is that the response depends on only a few covariates, and the main aim is to find them. This problem can be framed as
either a sparse multiple testing problem (controlling False Discovery Rate (FDR), False Negative
2024]. support recovery problem (controlling Hamming loss) [Wainwright 2007] [Btucea al. 2018 Gao
Rate (FNR), etc.) (Rabinovich et al., 2020 Song and Cheng, 2023 Abraham et al.
and Stoev 2020 Butucea et al.) 2023a]. based different setting of the loss function. Much of the existing studies concentrated on the sparse sequence model X; = Bi+ i= =,,,... ,P independently,
with assuming Σ 1(3 & 0) < and each e; drawn from distributions like Gaussian [Butucea
iet al. 2018, Song and Cheng 2023] or generalized Gaussian [Gao and Stoev) 2020 Rabinovich
et al. 2020 Abraham al. 2024]. Though these studies demonstrated interesting thase-transitic
phenomena and established the asymptotically sharp minimax separation rate, they cannot be directly applied to the univariate function selection in SpAM.
Background of univariate function selection in SpAM Univariate function selection in SpAM
stands as a pivotal problem in statistical learning [Lin and Zhang 2006 Ravikumar et al.] 2009
Huang et al. 2010 Chouldechova and Hastie 2015 Xu et a Wood et al. 2015 Butucea and
Stepanova 2017 Dai et al. 2023]. Most existing studies firstly provided minimax-optinnl estimators for the function via M-estimation with croup-lasso-tyee
penalties on each fn. Then, by utilizing the estimation results, the selection performances were often established by-products (Ravikumar et al. 2009 Huang et al., 2010, Dai et al. [023]] Although these methods ensured asymptotic variable selection consistency [Ravikumar al. 2009 Huang et al. (0100) or FDR control [Dai et al. [2023). they did not guarantee minimax optimality for the univariate function selection problem. This implics that their minimum signal conditions, typically quantified by "minjes, II 2 some rate", are sufficient but not necessary: Their signal strength assumptions may be overly restrictive.
Existing optimal univariate function selection in SpAM From the viewpoint of support recovery with Hamming loss, Ingster and Stepanova 2014) and Butucea and Stepanova [2017] provided the minimax optimal (i.e., necessary and sufficient) signal condition for exact support recovery and almost-full support recovery, respectively. Comminges and Dalalyan 2012 analyzed support recovery in p-dimensional nonparametric regression with intrinsic s-variate underlying function. In an additive model allowing k-dimensional interaction effects, (Stepanova and Turcicoval [2025a] b) provided the optimal signal condition for exact support recovery. These studies offered asymptotically minimax optimal results in some specific function classes, but may not be persuasive in the general function space with finite sample size. For instance, they rely certain additional assumptions, like log o(a 22(2211) and a + 0, in the Sobolev space with smoothness parameter a.
Inspiration from cutting-edge work Building on the monotone likelihood ratio property, Butuceal et al. [2023a] recently established rate-optimal signal conditions for support recovery under group sparsity, improving upon conclusions from Lounici et al. [201T). Kotekal and Gao [2024] extended the
hard-thresholding estimator of Collier et al. 2017 to develop a minimax optimal goodness-of test for SpAM (i.e., testing whether f =EEE, fy 0). These advances motivate the development of non-asymptotic minimax optimal univariate function selector within a generalized SpAM framework,
covering Sobolev-smooth, analytic, and other function classes.
1.2 Main contributions and organization
This paper answers the following questions:
In a generalized SpAM framework, can we achieve non-asymptotic and minimax optimal univariate function selection? What is the difference between function estimation and univariate function selection?
The main contributions are threefold:
Minimax separation rates From both the viewpoints of sparse multiple testing (FDR+FNR control) and support recovery (wrong recovery probability control), we establish

---

the non-ar -a--mmmttttic minimax separation rates for univariate function selection in a gener- alized SpAM framework. This result is, to our knowledge, the first optimal mnite-sample guarantees. We also develop truncated-type selectors to achieve the minimax rate-optimality, respectively.
2. Minimax adaptation We provide rate-optimal selection procedure that adapts to the smoothness parameter of the Sobolev spaces. We show that an additional log (log(o ?)) term in the signal condition is required for this adaptation.
3. Difference between estimation and selection Within the class of truncated-type estima- tors, demonstrate that the optimal function estimations can not yield optimal univariate function selection in some cases. This gap underscores the necessity to proceed differently in selection versus estimation, a finding with deep statistical implications.
The rest of the paper is organized as follows: Section I establishes the notation used throughout the paper. Section Doctionn[introde introuuuess the model setup and the background of our problem. Section 3 establishes the minimax separation rates for univariate function selection from two viewpoints. Section 4 provides rate-optimal selector adaptive to the smoothness parameter in the Sobolev space. Section S in-depth discussion about the difference between estimation and selection in SpAMs. The limitations, future directions, numerical experiments, and all technical proofs are provided in the appendices.
Sloffers an
1.3 Notation
For the given sequences an and ou. we write that a, Obb,) and an S bn (resp. an (b,,.) and On 2 by,) if an I cb,, (resp. an 2 cb,,) for some absolute positive constant c. We write that an X bn if 0₂ O(b,) and bn O(a)). Denote by [m] the set {1, ... m), and 1(-) the indicator function. Denote by x V the maximum of x and and x A the minimum of a and Denote by S {j E [p] f, + 0} S [p] the support univariate function set of a SpAM function f.
For square intergral function f with support X' denote by [| (Jx (z)) 1/2 its Le norm. Let C, Co, C₁, ... denote absolute positive constants whose values may change from one occurrence the next.
2 Preliminary and problem setup
Let us recall that we observe Y2 and æ E x" such that
dY E [1z))d odBa.
jES,
To ensure the identifiability of univariate functions, we assume Jx Lat 0 for each j E [p]. In theoretical research, the GWN model and nonparametric regression model are asymptotically equivalent, as shown by Brown and Low 1996] Reiß 2008 Moreover, the GWN model simplifies the analysis by avoiding unnecessary technical complexities while keeping the focus on the statistical essence [Kotekal and Gao 2024]. Consequently, many foundational nonparametric statistics theories
are developed based on the GWN model [Fan 1991 Donoho and Johnstone
1998 Baraud 2002
Tsybakov | [oomiinge and Dalalyan| 2012] Johnnstoone Han al. 2020 Therefore, to
maintain this theory-driven tradition, we conduct our analysis based on the GWN model
2.1 Function settings
We propose a general smoothness assumption based on the series expansion of univariate functions. For each j E [p], assume that fy : X' + R can be decomposed from an orthonormal basis {3/s Wiei as (x,,)
i (x,)) where O.y (fy(fs) == fx (xxx)) (rr,,, is the coefficient of s/s for each E N+ Define 0,, 0,5(5)) = (OijivEN. We assume that each fj is sufficiently smooth and belongs to the ellipsoid class
3 ==
fz
Ogg thy
(2)
AAss see Section 1.10 of Tsybakov regression.
2009 for the connection between the GWN and nonparametric
3

---

where {pilis is non- mon--onnneeete increasing sequence of positive numbers, i.e., #l 2 f2 2 and we assume Ai x 1 ensure fj has finite L2 norm. This ellipsoid setting a broad smoothness assumption that renders our theoretical results applicable to Reproducing Kernel Hilbert Space (RKHS) |Raskutti al. 2012 Yuan and Zhou 2016, Kotekal and G 2024]. Fourier basis [Comminges and Dalalyan 2012 Ingster and Stepanova 2014 Butucea and Stepanova 2017]. etc. The function space of SpAM
is defined as
P Σ
F=:= [(x) - (w)==n(o)) [(,))
101 #0) 8, 13 E for all j E [w] 1=1
==1
Each f E Fs corresponds uniquely a a O()) (0.))))) O.p(sp)) ( E TR Therefore, f F. and θ E Fs will be used interchangeably in the subsequent text. For every f F and every iE E (p], based on the continuous process Y, in model ( have access to the following random variables
Xij = J vs(z))dY, = =0is + / vilx,)ddB,, ((0ig,
By orthogonality, the X (XigheN Jelp) is collection of independent random observations.
2.2 Problem setup
Within the SpAM space F., our primary task is establish minimax optimal (i.c., necessary and sufficient) signal condition of each support fj. for the univariate function selection. Before delving into our analysis, we revisit the function estimation problem in SpAM, where Raskutti et al. 2012 established the minimax rate as:
inf sup E,, (1ixx)- - x f JEF
o² log(ep/s)
+8 x
max (lo*k) A pk)
KEN+
dignediinesioonal selection
infy, sup se B,, (x,111((,,)111
which is composed of times the "high-dimente ditb-dimnnsional selection error" and times the "minimax estimation rate of single univariate function", with no interplay between these two parts. This result shows that the first term o²s (cpp))) ) is independent of the univariate function space E, and the estimation term (the second term) is dimension is natural to speculate that the univariate function selection shares similar property, with its optimal signal condition, quantified by the squared L2 norm, of the rate:
(p-free) (Kotekal and Gao [024]. Therefore,
a log (eg/sp/))
((oPVK)A
max
KEN+
High-dimensional selection error
where the second term the minimax separation rate for the goodness-of fit test a single univariate function in & [Baraud] 2002].
However, in Section 3 we prove that this the case. In univariate function selection, there an interplay between the nigh-dimension sparse structure (selection error) and the ellipsoid space E, complicating the form of its minimax rate.
3 Main result: optimal univariate function selection
In this section, we demonstrate that the truncated-type selectors lead to minimax optimal results.
Define the decoder πy (f) = 1(f, * 0), and the corresponding vector 7) = 17()) := (m (f1). ... mpp (f))))
10.1)" We also define the selector, i.e., the estimation of 77, as f ((X) = (în (X), ... hp (X)) E 13, and Š (j E [p] f }} as the estimated support set corresponding to ij. Deñine the SpAM space with the signal strength condition as
F.(r2)= = f Σ FEF.
11 2 for all fy #0 20.
(6)
JE(N)

---

indicating that each support f, has a signal separated from 0. Here r² is a positive value and we additionally assume , I μl to ensure Fe(r²) * 0 (since | S μ1 E S μl based f E). In the next two subsections, derive the minimax separation rates from viewpoints, sparse multiple testing and support recovery, respectively.
3.1 From sparse multiple testing: FDR FNR control
Preliminary setup
From the viewpoint of testing, the selection can be realized as a multiple-testing
problem
Hoj f, = H1s # 0, for all j E [p].
under the exactly s-sparse function space
{1
SE FEF=.(13)
110; +0)
jElp
jElp
We consider the multiple testing risk combined with the false discovery rate (FDR) plus the false negative rate (FNR), which is of the form
Ejss, i JELN 9
+ Ejes, (1 11)
R(f. E,
(1V 1
This combined risk balances the proportion of type I and type II errors, and is frequently used in the sparse testing [Arias-Castro and Chen 2017 Rabinovich al. 2020 Abraham al. 2024].
Definition (Minimax separation rate of sparse multiple testing) We say Clest is the non-
asymptotic minimax separation rate of the sparse multiple testing problem for ① if:
(1) For all 8 E (0, 1), there exists co 0 depending only on such that for all 0 < c <<cc
inf " (EF
sup
R(S, 1-
(2) For all 8 E (0, 1), there exists C3 depending only on such that for all
Cs.
inf 1eFen(C
sup
R(f. < 8,
where infç denotes the infimum over all selector fi(X): R xp + 10.
K K-truncated selector corresponding selector
For each sequence X.j, we truncate by the first K entries and construct the
K Σ
1 (X.;) =
x 2 o2 +X²(K) j E [p].
where the truncation == min f KENN: us S 0² log(p/s) and the parameter X²(K) will
be determined Theorem Denote by grest (ffest ... sssttt E {0, 1). the corresponding selector vector. The following theorem employs an analysis to control the combined risk at a low level.
Theorem (Upper bound for sparse multiple testing) Let be an arbitrary number in (0, 1), and assume that o -2 Ca. log(p/s)
p/s 2 C5.2. and 2 C5.3. Then, assuming
6 (V10+ 1 +2) V2
36 0² log(p/s)
2
(o2Vklog(p//)) pk)
(8)
Vo
KEN!
and taking
X²(X) = 20²
(v5K log
P
+ 5log
55
)
P
80
5

---

we have
sup R(f. sfeat S
(r
where Ca C8,2, Co,3 are positive constants only determined by 6.
The next theorem shows that the rate in (8) also necessary for controlling the testing risk.
Theorem (Lower bound for sparse multiple testing) Let be an arbitrary number in (0, 1), and assume that o
Ca.1 log(n/s)
p/s 2 Co.2. and Cs,3. Then, for all r² satisfies
111
max (o² (kV/klog(p/s) p12) 1
oz log(p/s) 0 < 2 S..A
KENT
we have
inf sup (EF=.(ra)
21
where Ca,1, C8.2, C.,3 and ça are four positive constants only determined by 6.
Therefore. combining Theorem
and we establish the minimax separation rate for the sparse
multiple testing the SpAM
Eest x o² log(p/s) + max KEN+ (o²Vklog(D//) mx).
(9)
We also illustrate that a truncated-type selector possesses such minimax optimality.
reveals that our initial speculation (). in the end of Section 2.2 is inaccurate: The high-ddmensional sparsity structure influences both terms in the minimax separation rate. This is because the selection problem is related the shi-squared distribution, whose heavy tail leads to the selection error of the rate a² (og(p/s) s) + /K log(p/s) Therefore, we have to choose an appropriate truncation level to balance the residual signal strength PK with this composite error bound, i.e., Hk X d² {log(p/s) / (og(p/s) Consequently, the high-dimensional structure affects the choice of trancation, revealing interplay that is not only sufficient but also necessary.
Remark (Truncation) far, the equation 9
Remark 2 (SpAM and GSM) The Gaussian sequence model (GSM, mentioned in Section I.I can be seen as a simplified SpAM, where 0ıj = and 0ig = 0 for each 2 2 and E Sy. Therefore, in GSM, we can just choose truncation K 1, and analyze the selection
caused by the
Gaussian distribution (Butucea el al.) 2018 Song and Cheng 2023). In contrast, to get an optimal trancation K in general SpAM space, our selector ( requires trading off the truncation bias against sub-exponential error. Both the analysis and outcome demonstrate that univariate function selection in SpAM more challenging than variable selection in GSM.
Additionally, our theoretical results can be extended to the following specific cases.
Corollary Assume that all assumptions Theorem and Theorem Theorem[holdd. Then we have:
Take μ4 x 2- with smoothness parameter o,, the minimax separation rate for multiple lesting is
Sobolev
Cest o² log(p/s) + (o* log(p/s) r
20 for some positive
Finite dimension Take μM =... Pm um++1 Mm+2 integer m, the minimax separation rate for multiple testing is
É o² log(p/s) + (0² mollog//ss
Exponential decay Take pr x exp(-cc where e₁ a positive constant and 7 > the minimax separation rate for multiple testing
2est x 0² log(p/s) + o Vlo(lp/s) log (1ogp//))

---

Remark 3 (Finite dimension case) We now give further discussion of the finite dimension case.
Under the assumption
log(p/e) the minimax separation rate exhibits two regimes:
P1
1. If pi E o² m log(p/s), then we derive that y Ym log(p/s)
log(p/s)
leading
P1
m Z u0 1. In this case éeest x o² log(p/s) + 11
2. If p1 > -22 log(p/s), then we get éeett o² log(p/s) + 2 log(p/s), with the minimax separation rate in the group sparsity setting (utuuca et al.
which aligns
2023a
Combining these cases gives a more intuitive separation rate
Gest min {o² (log(p/s) + v /mllo(p/s))
m1).
Here the minimum reflects our ellipsoid space constraint: by definition of & and Fs(r2) in Section 2.1 every active univariate function f obeys ||5 pi EieN+ upper bounded by P1-
μl, leading its L2 norm P.
In the case μi S o² V log(p/s), we have éjest x pt. In other words, to control FDR+FNR, we would need each fj to satisfy [|f Z Cи for some large constant C > O. However, each support fj obeys Ilf S f1. Hence, there are basically no fj that can attain detectable norm, and the support recovery problem is essentially trivial in this case.
3.2 From support recovery: wrong recovery probability control
Preliminary setup The univariate function selection can also be viewed as support recovery problem. We measure the selection error between the estimated support Š and the true support S by (fi * v([)), where the probability of wrong recovery
using the Hamming loss
p (5(x) # s()) = Py (M(X) + n()) = ((1(((() # m(())
serves as the risk function, which characterizes how we can exactly recover the support set [Wain wright 2007 Butucea et al. 2023a].
Definition 2 (Minimax separation rate of support recovery) We say ofe is the non-asymptotic minimax separation rate of support recovery for T if:
(1) For all 8 E (0, 1), there exists co >> depending only on such that for all 0 < c
inf 1 (et,
sup
Ps (fi(X) # n(f)) 2 1-
(2) For all 8 E (0, there exists Cs depending only on such that for all > Cs.
inf sup (CF.(C)).)
Py (i(X) + v(()) S 5,
where inf denotes the infimum over all selector ii(): N + {0,
Similar to Section 3.1 we next establish the minimax separation rate for the support recovery problem
SpAM IT.
Theorem (Minimax separation rate of support recovery) Let be arbitrary number in
(0, 1). and assume that o Cs.1 log p 2 Cs and 2 Cs.3. Then the minimax separation rate for the support recovery problem with respect to the wrong recovery probability P. (x) + nff)) is
(0² (o2Vklogg A 11)).
éec
logp
max KEN+
(10)
The minimax separation rate for support recovery 10 a little greater than that for sparse multiple testing in (9) (log p versus (og(p/s)), showing that controlling the wrong recovery probability is

---

more demanding than controlling the combined risk (FDR + FNR). Indeed, sparse testing requires [$AS] o(s), while exact recovery requires |$AS| = o(1), necessitating slightly stronger signal condition. In addition, this discrepancy leads to higher thresholding level for optimal selection in support recovery, as detailed in the following.
Remark (Rate-optimal selector)
Under assumptions in Theorem 3 and the signal condition
f 0² logp + max (o² (ooloogpN }
7 2 C8
KEN
the selector
x2 20 20 (V (VK'log(2p/0) log(2p/))) ). jE [p]
() =1
Σ
(11)
controls the wrong recovery probability effectively:
sup
Py (1r + nf)) - 5,
SEF,(r2)
where K' ;- min (k E mh S 0² klogp) and Cs 0 is constant only determined by 6.
Remark (Relation to existing work) For the Sobolev space with smoothness parameter a, we (10) for exact support recovery as:
rewrite the minimax separation rate
(logp)
if log E σ 20+7
2 Frec
(12)
logo
if 2 Z logp こ 3041
Therefore, in the case log p
match the rate derived from Ingster and Stepanova Additionally, our findings establish the non-asymptotic minimax separation rate for the a-2 Z logp > 2afi, which was provided in previous studies. In this case, the selection error exhibits Gabb-Gassiinn behavior, resulting in the rate aligning
(2014), Butucea and Stepanova (2017).
with that in the Gaussian sequence model (Butucea al. 2018 Song and Cheng) 2023
4 Adaptation to the smoothness
Thus far, our analysis has assumed full knowledge of the smoothness sequence {14 (un)e which often unrealistic. This section investigates how adaptation to unknown smoothness affects the minimax separation rate. For simplicity, we consider the Sobolev space with μ4, = i-a a > 0, and rewrite the original space F, (r²) F, (r² a). The wrong recovery probability (f(( + (f)) used as the risk function.
A selector adaptive to the unknown a Define the truncation set
IoRa
Kree = 2, 2,4 ...
For every 8 (0, 1) and ls Krees denote (x) the selector vector with respect to k, where
(. (k)
111
(X),
1p
(k) (x))
(0,, 1lp as
(2)
X 1s + 2 klog
8p loloo(o -2)
+ 2og
Sp Soggo(o 2)
8
8
Now, we define the adaptive selector
7nd(() max (k) keKr
/
max (i(h)
[0,
(13)
keKroc
For each fj. our selector (33 firstly construets individual tests for each k E Kree- and then aggregates them by taking the maximum over Krees Equivalently, J, is declared supported as soon as identified as nonzero under any candidate & E Krea; conversely, fj is declared non-supported only if is identified as zero for all Kree- We next establish the sufficient signal condition for the wrong recovery probability control.

---

Theorem (Upper bound for adaptation) Let 5 be an arbitrary number in (0, 1), and assume that
C5.1 logg Then, for all y² satisfies
f1
2² 122/2 + 1) a log IT4a ( + 18022og
Sp Splog -2)
we have
Py (frd * 7) S6.
sup a20 (19,)))))))
sup
Compared 122. additional log (log(o-2)) term in the signal strength condition is required. The following theorem shows that log (log( 2)) is also necessary for the adaptation the smoothness.
Theorem (Lower bound for adaptation) Let be an arbitrary number in (0, 1). and assume that Ca.1 log and 2 Cs.2. Then, for all r² satisfies
0 S c5.3 foii 8y
(plog(o- 2)) + o² log (plog(o 2)) logit4a 1440
20
have
inf sup a>o (rt,())
sup
py (i(X) + 7) 2 -
Theorem 5 esttablish the adaptive minimax separation rate
2ur log 114m (plog(o 3)) + o² log (plog(o~2))
(14)
In the high-ding diaeeniieniionll case log Z log (log(o-2)) 2)), the log (log(o 2)) term becomes negligible and (I4) achieves the same rate as (12), indicating that adaptation incurs no additional cost on the
rate. However, when is large constant that is much smaller than o-2 (14) indicates that, with the
smoothness unknown, achieving support recovery requires a stronger signal strength compared to
(12).
5 Discussion: difference between optimal estimation and selection
We finally end this paper by discussing the difference between estimation and selection. For simplicity, assume 1p-/" where 3 e (0, 1) is constant, therefore (og(ep/s) x log p. Next, establish
a minimax-optimal estimator for ff E Fe through a truncated hard-thresholding procedure:
iij = ((
> Kg + VCK, logp + C' loog
(15)
Truncation
Hard thresholding
where we define K. == min(k E N+ : ph S o²k), and C>
> 0 is a fixed constant.
Theorem (Optimal truncation for function estimation) Assume a-2 canstant C in (15) satisfies C 2 4. Then the estimator
log and the
(15) is rate-optimal:
sup E)llf( fl12 sup E e(f So's log + JEF,
(()2k)
max KEN+
feF.
Combined with (4. Theorem 6 implies that by only using the first Ke entries in each observation sequence (i.e., only using X [|K]]xpo] : {X,) (Xiy)issk,_.t 1Sjsp) one can achieve minimax optimal function estimation. However, it may fail guarantee optimal univariate function selection by only using these truncated observations, as shown below.
Theorem (Suboptimal selection) Assume o -- Cj log and 2 Cz. Then, for all y2 satisfies i1
0 2 < c3
{
{ loooo + max kE[Ke]
(02 logg A M2) + [Kot1
(16)

---

we have lower bound as
inf *( MX seF,(r?)
sup Ps (f(X # #n) 2 2
where the infinum inf i( (xxxxx))))( takes over all restricted selectors that only use observations X [[k]]xpp) and C₁, C2 Cg Oare absolute constants.
This theorem demonstrates that the family of truncation estimators, optimal estimation sometimes leads to a suboptimal univariate function selection. For example, consider the Sobolev space with
14g = i- in the case logp
To exactly recover the support set, the necessary signal
strength (16) (by only using {|k_|((p) of the rate 1420 which exceeds the minimax separation rate 7x41 (log p) I as illustrated in (2).. This gap directly shows that optimal univariate function selection cannot be treated as byproduct optimal SpAM function estimation. See Figure | for clearer difference.
Signal strength y
h- 2a
o2
I+26
0² V klogp
2a (log p)
Truncation for optimal estimation
Truncation for optimal selection (log p) 1744
k
Kozo 1iz5
Kzo
Figure 1: The difference between optimal estimation and selection in the case logp = o (
Appendix A discusses some future directions for this paper, and Appendix B provides the numerical experiment to confirm our thcoretical findings.
Acknowledgments and Disclosure of Funding
This work was partially supported by the Academic Scholarship Program of Renmin University of China. The author thanks Cristina Butucea, Jianxin Yin, and Zhifan Li for helpful discussions.
10

---

References
Pradeep Ravikumar, John Lafferty, Han Liu, and Larry Wasserman. Sparse Additive Models. Journal of the Royal Statistical Sociery Series B: Statistical Methodology, 7165):100- 1030, 10 2009. ISSN 1312-7412. 10.111/111/// 1467-99988866 1467-9866. 1467-9868 2009. 00718.x
2009.007888
URL /
Lukas Meier, Sara van de Geer, and Peter Bühlmann. High-dimensional additive modeling. The Annals of Statistiics, 37(69) 3821, 2009, 1o.11...2119991055000 URL httthttp://// :/doi
Vladimir Koltchinskii and Ming Yuan. Sparsity in multiple kernel learning. The Annals of Statistics, 38(6):3660 3695, 2010. doi [0.1214/1O-AOS825 URL https: 10-A0SB25
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. Journal of machine learning research, 13(2), 2012.
Arnak Dalalyan, Yuri Ingster, and Alexandre B Tsybakov. Statistical inference in compound functional models. Probability Theoor and Related Fields, 158(3):513-55 2014.
Ming Yuan and Ding- Xuan Zhou. Minimax optimal rates of estimation in high dimensional additive models. The Annals of Statistics, 44(6):2564 2593, 2016. do110..214/5-A0OS1442 URL
https://dos .ww.iioogg/..... 1211112111511
422
Hemant Tyagi. Anastasios Kyrillidis, Bemnd Gärtner, and Andreas Krause. Learning sparse additive models with interactions high dimensions. Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 11 11-120, Cadiz, Spain, 09-11 May 2016. PMLR. URL http:::::://roceeedrgg/
ml press.pres.....m v51 ttagi 16 htm
Zhiqiang Tan and Cun-Hui Zhang. Doubly penalized estimation in additive regression with high- dimensional data. The Annals of Statistics, 47(5):2567 - 2600, 2019. doi
URL https:: //detts:://o...oo / org/ 10,
757
Asad Haris, Noah Simon, and Ali Shojaie. Generalized sparse additive models. Journal of machine learning research, 23(70):1-56, 2022.
Trevor Hastie and Robert Tibshirani.
Generalized additive models: Some appli-
cations. Journal of the American Statistical Association, 82(398):371-386 1987. doi [000000000000121159999/
URL http:://wwwww.affoloo...... com//oii........oooooooo...m.oo.
abs 0bs/11..108/001221441 1987, 104784440
Yu Ingster and O Lepski. Multichannel nonparametric signal detection. Mathematical Methods of Statistics, 12(3):24-27555 2003.
Yingjie Wang, Hong Chen, Feng Zheng, Chen Xu, Tieliang Gong, and Yanhong Chen. Multi-task additive models for robust estimation and automatic structure discovery. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems. volume 33. pages 1774-11755. Curran Asso- ciates, Inc., 2020. URL
neurips wwt.rriss....pppeeeeee papperrrr_p..e..epeeeeeeeeerrr fi files/paper)
Shiyun Xu, Zhiqi Bu, Pratik Chaudhari, and Ian Barnett. Sparse neural additive model: Inter- pretable deep learning with feature selection via group sparsity. In Danai Koutra, Claudia Plant, Manuel Gomez Rodriguez, Elena Baralis, and Francesco Bonchi, editors, Machine Learning and Knowledge Discovery in Databases: Research Track, pages 343-359 Cham, 2023. Springer Nature Switzerland. ISBN 978-3-031-44418-11
Cristina Butucea, Mohamed Ndaoud, Natalia A. Stepanova, and Alexandre B. Tsybakov. Variable selection with hamming loss. The Annals of Statistics, 46(5);1837 1875, 2018. T0. AOS1572SUPP URL ht htsps: : /oi org http://1.11.11111 1214/17 ACS1572
11

---

Maxim Rabinovich, Aaditya Ramdas, Michael I Jordan, and Martin Wainwright. Optimal rates and trade-offs in multiple testing. Statistica Sinica, 30(2):741-762, 2020.
Eduard Belitser and Nurzhan Nurushev. Uncertainty quantification for robust variable selection and multiple testing. Electronic Journal of Statistics, 16(2):5555 5979, 2022. doi [0.
EJS2088
Qifan Song and Guang Cheng. Optimal false discovery control minimax estimators. Bernoulli, Bernoull 29(3):1959 1982, 2023. do:110.315022--BJ11522 URL http::://6.l..rr//....333 22-BEJ1527
Cristina Butucea, Enno Mammen, Mohamed Ndaoud, and Alexandre B. Tsybakov. Variable selection, monotone likelihood ratio and group sparsity. The Anmals of Statisties, 51(1):312 333, 2023a. do1110.111/22-A052551 URLhttpss://dan 2ttp://o0...rr111.112//222222222
Kweku Abraham, Ismaël Castillo, and Étienne Roquain. Sharp multiple testing boundary for sparse sequences. The Annals of Statistics, 52(4):1564 1591, 2024. doi |0.1214/24-A052444 URL
https: / www.oo/ggg......o. 1214/24 A0S2404
Martin Wainwright. information-theorele bounds on sparsity recovery in the high-dimensional and noisy setting. In 2007 IEEE International Symposium on Information Theory, pages 961-965, 2007. doi 1 100/1119///ST10000 455744553348
Zheng Gao and Stilian Stoev. Fundamental limits of exact support recovery in high dimensions. Bermoulli, 26(4):2605 2638, 2020. do:110.3150/00-BE1117 URL htttps://dbi.org/11
#150/20-BFJJ11
Yi Lin and Hao Helen Zhang. Component selection and smoothing in multivariate nonparametric
regression. The Annals of Statistics, 34(5):2272 2297, 2006. doi 10. 100221000000366000000072222 URL
1 http.///.....21/0000000000000000
Jian Huang, Joel L. Horowitz, and Fengrong Wei. Variable selection in nonparametric additive
models. The Annals of Statistics, 38(4):2282 2313, 2010. do1:10.2214099-00738) URL
hnttps://doi... wtwpii.rr111... 10..0.12214 1214/01 A08781
Alexandra Chouldechova and Trevor Hastie. Generalized additive model selection. arXiv preprint 10X.v:1506.03850, 2015.
Min Xu, Minhua Chen, and John Lafferty. Faithful variable screening for high hign-dimensional convex regression. The Annals of Statistics, 44(6):2624- 2660, 2016. 1001110124/15 URI.
https://dof lttt::::///oii.r////000 http:/oo.//.11.1../1.... -
Simon N Wood, Yannig Goude, and Simon Shaw. Generalized additive models for large data sets.
Journal of the Royal Statistical Society Series C: Applied Statistics, 64(1): 2015.
Cristina Butucea and Natalia Stepanova, Adaptive variable selection nonparametric sparse additive
models. Electronic Journal Statistics,, 11(1):2321 2357, 2017. 1o1:10..244177 URL
huttps://das wtt.b/o..rr....11111111111111111
Xiaowu Dai, Xiang Lyu, and Lexin Li. Kernel knockoffs selection for nonparametric addi- tive models. Journal of the American Statistical Association, 1186543)2155--11))) -170, 2023. doi 10. 1080/016214459 202999.02222222 203277039671 2022. 2039671
URL
PMID: 38143786.
Yu Ingster and Natalia Stepanova. Adaptive variable selection in nonparametric sparse regression. Journal of Mathematical Sciences, 199: 184-21,,, 2014.
Lačtitia Comminges and Arnak S. Dalalyan. Tight conditions for consistency of variable selec- tion in the context of high dimensionality. The Annals of Statistics, 40(5):2667 2696, 2012. doi 11110.1121/12-AOST044
wwt.tttps://do..rr 1211122-01222111100000000
Natalia Stepanova and Marie Turcicova. Exact variable selection in sparse nonparametric models.
Electronic Journal of Statisties, 19(1):2001 - 2032, 2025a. doi 10.1214/25-F1S22774
URI.
https: pops://dor /ooii. wwo.oogg/.0... 1214/1111//2.2. -
12

---

Natalia Stepanova and Marie Turcicova. Adaptive exact recovery in sparse nomparammttiii models. Statistical Inference for Stochastic Processes, 28(3):15, 2025b. db0100...077/1122200033003333333 URL https: /ttp://....011111110111111000100
Karim Lounici, Massimiliano Pontil, Sara van de Geer, and Alexandre B. Tsybakov. Oracle inequali-
ties and optimal inference under group sparsity, The Annals of Statistics, 39(4):2164 2204, 2011.
1ooi100.21440 1211//111-0S8800 URL https: http://ttt.o..g..////// 111.////....11111000001111011110
Subhodh Kotekal and Chao Gao. Minimax signal detection in sparse additive models. IEEE
Transactions on Information Theory, 70(12):8822-8928, 2024. 000110.100//111222444377777
Olivier Collier, Laëtitia Comminges, and Alexandre B. Tsybakov. Minimax estimation of linear and quadratic functionals on sparsity classes. The Annals of Statisticx, 45(3):923 - 958, 2017. doi|10. 111.0.211115-AAOSI.0
URL PRRtttts:://oo/ http::///..oo......./....o1 12141...1111111 AOS1432
equivaaleieeuevvveeeeee Lawrence D. Brown and Mark G. Low. Asymptotic equivalence of nonparametric regression and
white noise. The Annals of Statistics, 24(6):2384 2398, 1996. doi /00.1214/as//0022181111
URL httphhtss///oi.rrrtttt
Markus ReiB. Asymptotic equivalence for nonparametric regression with multivariate and random
design. The Anmals of Statistics, 36(4) 1982, 2008. 10110.221407 URL
https: http/oo.ccoo www...orr11..0. http:/....111/1111111 12110/020..114
Alexandre B. Tsybakov. Introductiion to nonparametric estimation. Springer Ser. Stat. New York,
NY: Springer, 2009, ISBN 978-0-387-79051--0.
Jianqing Fan. On the Estimation of Quadratic Functionals. The Annals of Statistics, 19(3):1273
1294, 1991. doi Too10.0114/0xx//173333333 1176348249
URL https:
David L.
Donoho and lain M. Johnstone, Minimax estimation via wavelet shrinkage. The Annals of Statistics, 26(3):879 921, 1998. 4A000:12244/////2444100 URL https:t/////m /ttp:::/ddoooooooo 1214/aos 10244991110249108
Yannick Baraud. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8(5):
577-606, 2002. ISSN 13507265. URLptttp://wwe jstor org. wtt.:/aaaaeaae///e33333
lain M. Johnstone. Gaussian estimation: Sequence and wavelet models. 2017.
Yanjun Han, Jiantao Jiao, and Rajarshi Mukherjee. On estimation of l,-norms in gaussian white noise models. Probability Theory and Related Fields, 177(3):1243-11) 2020.
Ery Arias-Castro and Shiyun Chen. Distribution-free multiple testing. Electronic Journal of Statistics, 11(1):1983 - 2001, 2017. 10110.2214//7 URL
EJS1277
T Tony Cai and Mark G Low. Nonquadratic estimators of quadratic functional. The Annals of Statistics, 336602293, 2005.
Tony Cai and Mark G. Low. Optimal adaptive estimation of a quadratic functional. The Annals of Statistics, 34(5) 2325, 2006.
URL BRRhhtts:: /doi
Cristina Butucea, Amandine Dubois, and Adrien Saumard. Phase transitions for support recovery under local differential privacy. Mathematical Statistics and Learning, 6(1):1-50, 2023b.
Cristina Butucea, Amandine Dubois, Martin Kroll, and Adrien Saumard. Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids. Bernoulli, 26(3):1727 1764, 2020. 100110.3150/99-BJ1116 URL https:://oo. 19 (9-BEJ1165]
Cristina Butucea, Angelika Rohde, and Lukas Steinberger. Interactive versus noninteractive locally differentially private estimation: Two elbows for the quadratic functional. The Annals of Statistics, 51(2):464 486, 2023c. 160100.2214/22-0052254 URL. httpt::///// //ooi .ot.//.....0.111
22 A0$2254
13

---

Chao Gao, Fang Han, and Cun-Hui Zhang. On estimation of isotonic piecewise constant signals.
The Amnals of Statistics, 48(2):629 654, 2020. doi110.121478-AA0ST722 URL https
1214/1211--1 A0S1199
Anru R. Zhang and Yuchen Zhou. On the non-asymptotic and sharp lower tail bounds of ran- dom variables. Stat, 9(1)xe314, 2020. doi.httss///oi.og//00000222zz222
URL https
//onlinelibrary wi www.ww.lcccmm cwm/ htt///oo///b///// 10. 1001 sta.. 314 e314 sta4.314.
Malay Ghosh. Exponential tail bounds for chisquared random variables. Journal of Statistical Theory and Practice, 15(2):35, 2021.
Lucien Birgé, An alternative point of view on lepski's method. Lecture Notes-Monograph Series, pages 113-133, 2001.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [Yes] The abstract of this paper precisely outlines our contributions in terms minimax separation rates for univariate function selection sparse additive models. We also discuss the adaptation to the smoothness and the difference between the optimal function estimation and univariate function selection. Section T also present the main contributions and assumptions in this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [Yes] This paper sets certain limitations on the model. Our analysis is based on the Gaussian white noise model instead of the empirical nonparametric regression model, which means our results cannot be directly used in a real application. However, as we point up in Section 2 the Gaussian white noise model simplifies the analysis by avoiding unnecessary technical complexities while keeping the focus on the statistical essence, and our results are asymptotically applied to the nonparametric regression model. We also provide an in-depth discussion of our limitations and future directions in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
15

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: [Yes] Each theorem in this paper comes with detailed assumptions. All formal proofs of all theorems are provided in Appendix C and the formal proofs of auxiliary lemmas are provided in Appendix K
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: [Yes] This paper provides rate-optimal selectors and an adaptive selection procedure. We thoroughly outline the experimental parameter settings and simulation proce- dures in Appendix B Additionally, we upload all the R code required for the experiments in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
16

---

reproducible, they (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: [Yes] The supplementary material includes all code used in our experiments, covering data generation, preprocessing, truncation selection, effectiveness analysis, and so on. The code provides specific parameter settings and random seeds to ensure the complete reproducibility of all results shown in Appendix B
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (bttps://nips... oc/
public/ gu des / CCodeSummee ss onPolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https?
httpssccppppccccceecceee.ccccccs gwwgddiie//////ee CooeeSumm' as iisiooPoll Pooolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: [Yes] In Appendix B we present comprehensive introductions to our procedure and data, covering data generation, preprocessing. truncation selection, performance metrics, and so on. Furthermore, the supplementary material includes all the code used in our experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
17

---

The full details can be provided either with the code, in appendix, or as supplemental
material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: [Yes] The simulation results in this paper report I-sigma error bars based on standard errors from 300 Monte Carlo simulations (see figures in Appendix B). The variability of error bars arises from the randomness of error terms in simulations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: [Yes] We provide the information on the computer resources in Appendix All simulations conducted using R and executed personal laptop equipped with AMD Ryzen 7 5800H processor operating at 3.20 GHz and 16.00GB of RAM.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpti/ttt/////pppppppppp/ppaatt
Answer: [Yes]
18

---

Justification: [Yes] This paper consists solely of theoretical analysis and simulation ex- periments, with all data being randomly generated. It does not engage human subjects or participants, nor does it raise data security concerns such as personal privacy. Additionally, the supplemental material contains all the code for our experiments, ensuring the repro- ducibility of our results. Therefore, the research presented in this paper adheres to the NeurIPS Code of Ethics in all respects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [NA] In this paper, we purely discuss the theoretical minimax separation rates of univariate function selection in sparse additive models. belongs the domain of statistical theory research, and therefore does not involve societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA] In this paper, we purely discuss the theoretical minimax separation rates of univariate function selection sparse additive models. Therefore, belongs the domain of statistical theory research and poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
19

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: [Yes] We cite all the papers that inspired this work, and also provide citations for the techniques used in the proofs.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, ppaperswithee wwwerrwwihcceeee com/ dat aset has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: [Yes] We upload all the code in the supplementary materials as a zipped file, covering data generation, proppccessiing and so on. The code provides speeific hyperparam- eter settings and random seeds to ensure the complete reproducibility of all results.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
20

---

Answer: [NA]
Justification: [NA] This paper purely discusses the theoretical minimax separation rates of univariate function selection in sparse additive models. Therefore, it does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA] This paper purely discusses the theoretical minimax separation rates of univariate function selection in sparse additive models. Therefore, it does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: [NA] This paper purely discusses the theoretical minimax separation rates of univariate function selection in sparse additive models. Therefore, does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy http::////eerrrsscc//ceeeeeeeeee
LLM) for what should or should not be described.
21

---

selectors for SpAMs remains an important and challenging These appendices provide the future directions, numerical experiments and the technical proofs of the main manuscript. For notational convenience, throughout all appendices we define = to represent the noise intensity.
A Limitations and future directions
Besov ball or Lg ball One key direction for future work is extend our univariate function selection results from the T-z-ellipsoid (2) to richer nonparametric classes such as Besov balls Bi,g or, more generally, T. -.g-ellipooids. These spaces naturally align with wavelet bases and are foundational to practical methods in signal processing and denoising. However, under the high-dimensional setting, the techniques in [araudd (202) may not be useful anymore. Perhaps a more viable approach is to construct selectors based on the nonquadratic estimation procedure in Cai and Low [0005 2006).
which may also lead to a minimax adaptation result simultaneously.
Univariate function selection under local differential privacy Integrating the differential privacy (DP) mechanism into univariate function selection for SpAM represents direction for future research. DP ensures rigorous protection of individual data while allowing valid statistical inference; therefore is welcomed by the computer science, machine learning, and statistics communities recently. In the local DP setting, Butucea al. [2023b] established phase transitions for support recovery in the sparse mean model, deriving minimax separation rates for exact recovery and for almost-full recovery. Butucea et al. [2020] 2023c] studied the funetion estimation and the quadratic functional estimation in the nonparametric univariate function, respectively, where the latter plays an important role in goodness-of of-fit testing. All these works demonstrated that DP leads some markedly different minimax rates compared to non-private benchmarks.
Consequently, when extending univariate function selection in SpAM to local DP constraints, one should expect that the minimax separation rates will differ from the results this paper: the optimal truncation should be recalibrated to account for the additional privacy-induced noise. Designing and analyzing such problem.
general conclusion about estimation and selection Another significant extension lies in gener- alizing the minimax lower bound in Theorem 7 which currently restricts the infimum to selectors relying solely on truncated observations X [[K.]x())- To this end, we define the minimax optimal estimation class
Eopt == f. N* [pl
+ N [[p]
sup E, [(x) - -1 S o²s log + x max (lo2k) A px)
SEF,
KEN+
The general version of Theorem shoull focus the necessary signal condition for selectors induced by estimation class Fopt:
inf inf sup Py (i()) + Eeg f=i()) (EF,
Ideally, this lower bound could quantify how the minimax optimal estimations perform in the support recovery problem. It could also lead to a more comprehensive realization of the difference between estimation and selection.
Establishing such result will likely require some new analytic tools, and we think the techniques in Song and Cheng 2023 may give some help. We leave this interesting problem for future research.
B Numerical experiment
We conduct three simulation studies to evaluate the performance of our truncated-type selectors in sparse additive models. For ease of display, we define -2
1. Compare the performance of our proposed method across varying dimension and signal strength ,
2. Compare the performance of different selection methods across varying variance 1/n.
22

---

3. Compare the performance of different selection methods across varying smoothness parame- ters.
In all experiments, take X' [0, 1], 5, and let the support covariates be j ....., centered functions
,,, with
f1(z) x x2 - (x 0.5) 0.5424,
f2(2) 12(r 0.5) 12,
[a(x) 3x²² 2--1 cos( ( 15x) 0.1002,
fa(z) 2x - 1,
[s(x) 8(x: -0.7) + 0.4640,
which all belong to the Sobolev space with 1/2. Performance is measured by the Hamming loss
1 ( # ((f))
and the combined FDR plus FNR loss
Ejes, fj V E}E
Ejes, (1- -fg)
For each simulation, we execute 300 repetitions, with I-sigma error bars provided in the figures. All simulations are conducted using R and executed on personal laptop equipped with an AMD Ryzen 7 5800H processor operating 3.20 GHz and 16.00GB of RAM.
B.1 Simulation 1: dimension and signal strength
We fix n = 300, and vary p E {10, 100, 1000, 10000). We take fj as the support function, for j 1, 1.... 5, where 0 quantifies the effect of the signal strength.
Figure shows that, as the signal strength a increases, the selection errors (both Hamming loss and FDR plus FNR loss) for each decay toward relatively low level, but larger demands higher to reach the same error level. Moreover, controlling FDR FNR requires weaker signal strengths: at 0.5 suffices to keep FDR FNR = 0.5, whereas the Hamming loss drops below 0.5 until a = 0.7. This behavior reflects the fundamental difference between sparse multiple testing and discussed after Theorem
y 10000,
exact support recovery,
Support R Recoerry
Sparse Multiple Testing
1.25
1.00
1.00-
Hamming Loss
0.75
FNR +DD Loss
0.75
0.25
0.25
0.00
0.00
0.25
0.50
0.75
1.00
0.50
0.75
1.00
Signal Strength
Signal Strength a
Dimension
p=10
p=100
p=1000
p=10000
Figure 2: Selection performance with different dimensions and signal strength.
23

---

B.2 Simulation 2: noise variance 1/n
fix p = 500 and vary n from 20 to 300. Four types of selectors are considered in this simulation:
1. Optimal
The rate-optimal selector
2. Adaptation
The adaptive selector
d n The selector that takes truncation at K,, = min { E ENENN: pa S
3. Univariate
4. Suboptimal
The selector that takes truncation Kg min NEN+= Ju S }
Figure 3 iillssrates that, as grows, all methods see error decay, but the Optimal and Adaptation methods maintain the lowest selection errors across most regimes. Additionally, as we discussed in Remark 5 for X (logp)++2s the minimax separation rate is logp/n, under which the Ke- truncation remains rate-optimal, giving the Suboptimal selector a temporary advantage (for n < 100).
2a Once n 2 (log p) 1+2xx the minimax separation rate becomes n x6 p) 1o4 and truncation at Ke cannot be optimal anymore.
Support R Recoerry
parse Multiple Testing
1.00
0.9
Hamming Loss
0.75
FNR +FDR Loss
0.6
0.50
0.25
100
200
300
100
200
300
Method Adaptation
Optimal
Suboptimal
Univariate
Figure 3: Selection performance of the four methods with different noise level n.
B.3 Simulation 3: smoothness parameter
We fix 500 and n 300, and assess the effect of smoothness univariate function selection. First, for j .......5 5, we compute the original basis coefficients of each fy, denoted by (0ty heen. We next reweight these coefficients and get the new functions
f/00) = Σ 13 23- 1=
SEN+
so that each ((9 lies in the Sobolev ball with smoothness parameter 3. We vary [0.2, 1] and compare the performance of the four methods.
As shown in Figure 4 only the Adaptation method consistently achieves low error across all B, demonstrating its optimality and robustness to unknown smoothness and verifying our theoretical guarantees in Section
C Proof of Theorem 3
We first introduce the proof of the lower bound and upper bound in Theorem These proofs are instructive and lead to clearer proofs of Theorem I and Theorem 2

---

Support R Recovrry
Sparse Multiple Testing
0.20
0.4
FDR +FNR Loss
Hamming Loss
0.15
I
0.2
0.10
0.1
0.05
0.0
0.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
Smoothness beta
moothness beta
Method - Adaptation Optimal
Suboptimal + Univariate
Figure 4: Selection performance of the four methods with different smoothness parameter B.
We first define the Hamming distance
H(i()),(()) Σ Mi 72
(ū 1;),
which can upper-bound the wrong classification probability
P
(H( m)) Σ
wP (H =w) P
(17)
For notational convenience, throughout all proofs we set = -2 to represent the noise intensity.
C.1 The lower bound
To better clarify the truncation construction, define
((k) (r²2 0 B =,,= = Vk for all ki 0, = for all i k c E.
The SPAM function set induced by (T²) is:
f (FF((r)): E ()) for all ʃj $ Σ
E
2=1
Now consider:
inf
sup
Py (f(x) & (((x))++(())
inf
sup
Py ()(((() + f(())
1:NNt (r9)
p:bnt x x [0.1)* (EF (n2)
inf -
sup (er!") (r2)
P ((((X))))) # n(t))
(18)
which means that (r2), we only need to consider those selectors o based on the first observations in each univariate function fz.j ip).
Now, for some fixed N+, we set least favorable subset of F/hh (r2). and then derive its lower bound of the minimax separation rate.
25

---

C.1.1 The least favorable subset
For every fixed (0, 1), N+ which satisfy 14 2 (au A 1) max
log(p-s)
klo((pp
(where C₁ > 0 is constant defined in Lemma 2. consider the subset:
(r²) { O O (1)) Σ 1(0,, + 0)
(19)
Therefore, for each f F& (r²), (r²), if its j-th univariate function f = 0, the random variable Σ X follows from a central x > with & degrees of freedom (note that Xij ~ (0.... If Jj + 0, E X follows from a non-central x²-distribution with degrees of freedom and with non-centrality parameter nr?. Let fo and fi be the densities of these two distributions with respect to the Lebesgue measure:
2/2-11 e=2/2 fo(2)
O,
2 ((k/2)
(20)
k/2
2 2//2+i-1 e-
f1
nr?
0.
2
il (k/2++))
Once the positive integer is fixed, by Lemma we only need to consider the selector based on the norm || which we call them the norm selectors. Then conclude
inf R (0.1) (e2)))
sup
Py (Xxxp) # n(f))
inf
sup
p ([xxp) + n(f)
(U,1))
SEFth (12)
Py (1X 111 # m(()
inf
sup (r2)
(21)
f: norm selector
(80
Si (mllx1:tts11))
Po(e)
min j=1,-. * fo
(n (111:x1sss113) j=stl.- fo
max
(188)
P((s)
min
max n nl|x2tts113)
j=luw
jmst 1mst
where inequality (i) follows from Lemma I inequality (ii) follows from Theorem in Butucea et al. [2023a], where we denote by P Po(s) a probability measure in which only the first univariate functions non-zero, i.e., f, 0 j [s]. Equality (iii) follows from the monotonic increasing property of the likelihood ratio
fo (z)
+
C.1.2 The tail probabilities
With the fixed 5 (0, 1), & N+ which satisfy μa 2 (5:ó A 1) max
lug(p-s) y (olo((n-s) x2
aim to prove that the last probability in (1T) is greater than 8 if log(p
log log (2/6)
C2
2 log log (2/5)
and 2
log(p-s) 9 1) max
y K log(p-s) n
where ci and C2
n
(0. 1) are two positive constants defined in Lemma
2
Firstly, by taking x log cp 12g(2
0, we
26

---

conclude
Pe(s) p
max
n x 11 2 k +1 + c1 kr
=1 1 P (x2(0) 2 + c + + vkr
(1 c2e
(2g(2/6)
=1
1
-
8
2 1
2
(22)
where inequality (i) follows from (59) in Lemma
2 inequality (ii) follows from the assumption
p- p-3 8 [og(2/6) 2
12/(2/6) 1.
Besides, by taking 2 - 25 max log(p-s) v (po((pss)) and log(p 8) 2 log log(2/8)
we
conclude x 2 1 log(p - 8) > log(p s) and
2c1
201
nr² 222n22
x + v kx
+ +2
x vkr
x v kz
(23)
25
25
where the last inequality follows from C1 vkr
z led by log(p -s) s)
8/c1- Then, by conclude 16/c7. therefore
assuming 2 log(2/6) and log(p $) N of
+ log
lo2(2/6)
nr² + 2/ (k: + 2nr log l2g()
2 1lo((2/0)
Snr² + 2/ k 21r +2
Enr² 2 + 2nr +2 (Vi +
(1))
2 + ke
+ Ci
V (vk++) (T++1)
2
<q
+ v kz
where inequality (i) follows from Therefore, we conclude
P (((s)
min j=
n x s k +tga+ava
P (2(2 k c }
-1
x2(n1²) 1 + nr² 2 2/ (k 2nr2) log(2/8)
2 loog(2) (2/0)
(24)
21
P
8
21 exp log(2/0)
2'
where inequality (i) follows from (61 in Lemma 2 with non-centrality parameter B nr Combin- ing (T.). (22) and (24). we conclude that
inf
sup Ps ((() n(1) > >P Po(c) 9 (EF,(12)
11a0 < j=l,-.,
min
|
j=st1... p
> P c(s)
min
n// X1 S k - 2 + ci v kx
-=,--,
x P c(3)
xlI 2 k + ci + c Vo kr j=stl,"
max
2
1
> 1-8.
27

---

C.1.3 The optimal truncation K
By the definition of F (r²), F!h (r²) and (r²), the minimax separation rate is lower bounded by the constrained maximum:
log(p - 8) v log(p 8)
max max
log(p - s) k log(p - 8)
(25)
subject to max
S
k E N
where
c1 25
A1 E (0,1). 1]. For ease of display, we define
k KENt : S Ca Goy/log(p
((c)) = -min
(26)
k KEN+ p Cs esvk kog(p - 8)
(((s)) = max
By assuming es log(p-e) derive that [(ea) K((s)) < ((s)) + 1. Then analyze the μ4
maximum into two cases:
Case A: When ()o((p=a)) 2)1 2 Cs [log(p-e)) a)1 log(p-e) We derive that T,(es) Mlg(p s)
hence esy (1g)) log(p-s) oa loR(p-s) s) Then the maximum of
12 is 6&y L(ra) log(n-8)
Case B: When ([oa(n-s)) +)1
[oglp-sp -5) log(p-s)
We derive that < ((s))
[log(p [)] hence ca / lok(n-s) log(p-s)
log(p-s) Then the maximum of 25
Therefore, we establish the lower bound of the minimax separation rate as:
log(p 8) / L(css) log(p-
log(p 8) / WKles) log(p 8)
C3 max
max
n
n
n
n
log(p
5)
/ /klllp
max
max KEN
pk
n
7
log(p
klogpp
max KEN+
Mk
n1
(27)
where equality (i) follows from S [os)) K(ss) < L (os) + and equality (ii) follows from By (7 we derive the lower bound of the minimax separation rate.
Lemma
C.2
The upper bound
By
17
we only need to prove that sup supJeF. E, (H(((X), 8. For ease of display, we
denote X²(K") = (VK'log(2p/5) + (og(2p/)))
28

---

C.2.1 Preliminary
For fixed SPAM E Fr(2),, we use Sj C [p] the index set of the support univariate functions f3 # O. Then we have
E, (((((()))))) =E,
Σ
(x()) # ns(ss))
j=1
(X) # (n((si))
1=1
Σ P
K' Σ
K'
+X(K)
+
P
Σ x
K'
K' +
+*P(K))
JES,
j4S
(28)
Therefore, we will discuss the Hamming loss on the support and non-support separately.
C.2.2 Support
With signal condition
v Vologg
36 log
Ilf
1
N
24
+
22
max keN
A p4
+
8
8n
holds for all Sy have
R' Σ
02
10.k'
0
211
MK
Hi
K' log(p)
36
12
+
uk
8n
(29)
(86)
2 / K" log pP)
36 log p
12
n
5n
(M)) 12 / K' log 22p/0)
18 llog(2p/0)
n
n
where inequality (i) follows from the signal condition and a proof strategy similar to 63 in Lemma
inequality (ii) follows from the definition of K' and inequality (iii) follows from (2/8) log 2
log (2pp))) when p > 2.
29

---

We decompose Xij = =Oi + Eig with each Exy ~ (O, 1/n) independently. Then we get
K'
K
+ X2
n2
i=1
K' + x2(x))
PPs
[KE 110 1. s 11 + (f 01.3))) <
(
Ss ({ 116.KK0022 |01.KK 12 + 2 (. (1.K))
+ +P,, (49) + X((50) nAi)
8log(2p/6)
K + x2)
Sp,,
|k1:' + +10.0..'s 10 1
+ texp (- log(2p/6))
(1)
K SPs |k1,0o12 + 51101.k. 12 <
1
+ x²((K))
5
+
n
2p
(10) P,
S
(nlli: <K'- 22 K' log(2p)))
2p
8
<-
p
(30) where
where in inequality (i) we define event A₁ = (EI. 01.05)) >
-2 2210 ,,13 log(2p/d) 28/
(LI.K.. (1: ~ N (0.
Inequality (ii) and (iii) follow from 29 and the last inequal-
ity follows from (60) in Lemma
C.2.3 Non-support
We now focus on the Hamming loss on the non-support. For every j & S, we have n Σ X? ~
x (0), therefore
K
K
5
+
I
(31)
2p
where the last inequality follows from
61
in Lemma
2
Combining
28
30
and
(31
we conclude
K'
K'
E, ((((()))
Σ
P
x2
K
+ X2(3')
+ Σ P
Σ
x
2
K
+
x²(KK)
JES,
jES,
(p- 18
p
2p
(p + 1s,1)
< 8,
2p
where in inequality (i), we use |Sy| to denote the cardinal number of the support index set Sr, hence 1 < | < 8 < p. Therefore, we complete the proof the upper bound and also Theorem
D Proof of Theorem
In the proof of the upper bound, we first recall our signal condition
Ilf, 12 (V10+2 + v2
max KEN+
Vklog(p/s)
A pk
+
36
log(p/s) ss)
ön
and the selector
1 1
n1
22
>
K + 22 5K log(p/(s0)) 10 10log(e/<56))
i=1
30

---

v log(p/s)
where K min ENN p4 I
and n o 0= We assume p/s 2 /12 V v6/6.
Ca log(///))
16 V Cs and 2
where Cs is positive constant solely determined by 8 E (0,
D.1 FNR control
Similar to 29 in the proof of Theorem 3 we get
10 12 2 6 V5+ v2)
v K log(pp(s())
36 + (gg(p/(s0)).
Then for j E Sy. similar to (30p we get
Ejes, (1 fts))
E
E (1 (1a)
<P
(k) + 10.K,, 113 K 2 5K (og(p((55)) 10log(p/(s8))
2n (fi.K.j. (1.K)) S -4v - m
10g(p//(ss)))
(32)
(
S 1/ (0)
(0) < K - V8K (oklo(//((0)))
< 9 6,
which also leads to
2
E
Σ JESs
2
2s
8
8.
p1
Besides, by Hoeffding's 's inequality, get
P
Σ
n
Σ
$ 3/4
$ <exp (-2/s).
JES,
jES;
yielding
8 2
Σ JES₁
i
S s 28
8 33/1
S Sexp <exp (-2/8).
(33)
D.2 FDR control
By Markov's inequality, we conclude
(p/s)
P
Σ
is
Σ
P
X
K
+255K log(p/(so)) + 10 100og(p/ (No))
{p/s)²
145
S4S;
8
8.
p
(34)
which yields
Σ Ejes, nj
(
E
Σ jElp) 11
Σ
i
>
2s
p
8- 3/4
11 Σ
n
S
(p/s)2
s
jES,
145,
(p/07
(35)
S 2s (s/p)² 3/4
(p/e]
(8)
28
<
3
[p/s
31

---

where inequality (i) follows from p/s 2 V12 and 2 16, and the last inequality follows from p/s 2 (20). Besides, by similar technique, we have
Ejes, 4 I > JElP nj
1
Σ i jes,
SPP
Σ
nJ
8,
(36)
(w/8)²
(p/8)2
J4S,
Σ f
where the last inequality follows from We also get
34 and the first inequality holds because
S 1.
IV
TV
Ejes, nj EjEN F3
2
Σ /ES,
fp
S
28
3//
Σ J4Sy
iBs
S
8
(p/s)²
2
P
Σ
i S
2s
8
3/4
(37)
(p/s)²
p
JESJ
se 2V5 2/5
2
6.
(p/s)2
where inequality (i) follows from 33). and the last inequality is based on that the function g(z)
ze 2 is monotonically decreasing and tends on (1, 20). and hence for every (0, 1), there exists a corresponding C3 such that Cs yields se 2/a < 8.
D.3 Conclusion
Combining
32
35 36
and 37 we get
Σ j4s, 1B
+ Ejes, (1 (73)
E
V Ejew) !1j
Σ iASy
E
1
Σ
ijj > 28
8
8 - 3/1
11 Σ 1 S
V E EjElPl 45j
p
(p/8)2
JES
jES,
Ejesy Ai V EEENl !ij
+ E
11
Σ
i1 S s 2s
8
5 3/4
1 Σ
8
(p/b)2
p
jES;
j$S,
Σ j4ss 1i
+ E
1
Σ
iB >
8
V Σ 5EEP 11j
(p/s)²
jæS;
Σ Jes, (1 (-1i))
E
26
2 +
8
8 8,
p
where the last inequality follows from fromp/s/20 2 V2.. Therefore we get an upper bound of the combined risk sparse multiple testing with a rate-optimal signal condition, which completes the proof of Theorem
E Proof of Theorem 2
The proof of Theorem
uses similar technique to Section C.I in the proof of Theorem 3
Recall the decoder ni
Tf{ss) = 1(f, # 0) and the corresponding vector 7j = n(f)
(m (fi),, (p))) (T
[0.1)P This proof focuses the SPAM space =(k) F((k) (r?), which is
32

---

defined in (19). For every / E (r2), its specific form is only determined by decoder E {0, IjP, therefore a prior of 7) can also realized as a prior of the function space F (v²), and in next we may use the notation / f(1)).
We assume log c2(1p/=1-1) 2 max log(1=Cmmxx00) Cs log(p/s), where Cmax and x(8) are functions solely determined by 6 (0, 1) and will be clarified later.
32 log 1- 1-cmax(6)) 1).
1og(1-VI-) and n 2 ex (d)ct
(
E.1 Preliminary
For any prior и on {0, 1)", we denote by Px the prior distribution of 17. Then, similar to the proof of Theorem we get
inf sup (r²)
R(f.1)
inf
sup
R(
0: 1 (0,1) 14 (12)
inf (:: norm selector
(x2) R(
sup
(18)
M(1 R.) M( k)
(1 (1-e-orMM) pP
Σ
2P, (f(1) (1))
MJ
>
jEipl
where inequality (i) follows from Lemma 1 and the last inequality (ii) follows from Lemma with
M = Σ P-
= 1
f1j 1,
2
JEPN
where Z = (|]X il................ 1 E Rr. This formulation is justified by Lemma I which indicates that we can focus solely on the norms of each column in X1:K., with X1.K. denoting the first K rows of X. In particular, inequality (ii) holds with every K E (0, 1) and every prior on (0, 1}2. Next, we will construct block prior distribution n to conduct the lower bound of the minimax separation rate.
E.2 The block prior
We consider block prior which has often been used [Butucea al. 2023a Abraham et al. 2024 Take prior π as product prior over s+1 blocks of consecutive coordinates B (1,2,-. 2) B2
{q + 1,... 2-),- B, {(s 1) I.... )/), where g = [p/s] and p' qs. We write B.+
for the (possibly empty) set (p' 1.... ..). In each block B,, b E [s]. we uniformly choose an
index i B, and set i and ny 0 for all j E Bd and j + i. For every i Ba+1, just set
= 0. With this prior, we have
P
Σ n > jElp]
=
(f()) $ F!!) = 0.
P
33

---

Then we have
M = Σ P
nni
1,P x (1 = 0/2) > 1/2)
jE
= EuEBiitt) Pr (1u = =1, 11 EuEB, P7 (M = =1, Z)
Σ
Σ
1/2
x
bE[d]
ΣE
P
ni =1 E
4 (nll (2)
f
(n (ntlIXa=tt:113)
fo
fo
JEB.
NEBo\(A
Σ E
P X
Σ NEBO)(s)
(mlI
11 =1 (nl 122
P.d (1g 1)
Jo
Jo
JEBB
JEB
ΣΣ bE(
P
B, Xle;
max x aEB
where equality (i) follows the same notation (20). and in the last inequality we focus on the
probability on the block Br, where "X "lee"" means we assume T/. = 1 and f) 0 for all u E Bd \ (i).
Therefore, we transform the problem into the one we dealt with in Section C.T.2
Recall we denote by (m and k6)) two functions of 8 E (0, 1) independent of p. s, k and n, which ca will be determined later. By taking x log log(1 (8]= follow a proof strategy similar to
and get
PB x
max n| XI + + civkkz
2 Cmax (6).
(E)
Additionally, when nr² S e
v kx we define L = log I-cmae(0) I and have
nr² + 2/ + 2tr + 21 Snr?
+ + 2nr + 2vkt + 21
C1
x
Vkz
+ +22 cat (x+ Vkz) + 2 (Vk+1)
4
(1)
C2 V (vk+1)
2
2
Sa vkr
where
inequality
ii) follows the assumption
log log(
c2(4-1)
Canax
(8))
(16 32 log
-- (z) 1) Therefore, we follow a proof strategy similar to 24
max
c
and
get
P (x2(nr²) tk+cr tk+c takk)) 2 (n)
which leads that
mmn (8)(1- x(0))
(1 (1- -c-ee can (csx (0)
inf sup ① (1²
R(f + max (8) - x())
Note that we can always choose suitable Cmaxx( (6) and k()) to let then by assuming
14 (8)(1 xx(1] = vI o, and
cana ( (1)(1-x(1))
-log(1 (1-6) cx- (o)co (0) we conclude inf, supfesu R(F, 2
The optimal truncation & follows a similar analysis as Section C.I.3 which proves that we cannot control the FDR plus FNR well when
log(p/s)
Vklog(p/s) A pi: }
2 < c8
max KEN+
n
which completes the proof of Theorem 2
34

---

Proof of Theorem 4
The proof of Theorem
is similar Section C.2 For simlpicity, we assume μı ka- Recall
Krec= :- 2, 4, ...
loga log
we conclude |Kreal S loga
vi"
+ 1 S 4 4logn. n.
log
F1 Support
rrwm lona loge So
For every
Omin-
we
define
K
2
By 0
<
loga
n
S loga
n² log
we conclude K Kree. Now with the signal condi-
I+1a tion
log(
Bylos
115112 Z (12v2+1)
(log(8p/0
logn)
194a
18 log (Sp/6 log
n²
7
holding for all E Sy. have
10 a112
03
logg 8p logn
114a
18 log( Sp
2 12v2+11
(K*) -2x
(38)
n²
m
( 12 Kt log( Sp
18 log Splogn
where inequality (i) follows from j E S, conclude that
n² log( Bo
K 5
n² log( Bploon)
Then for every
(1gg
(X) +1}
KK
0)
K"
K" < Kolog log 8pp
8p
-PA f1
11
X2
K*
2 log
(39)
P
X (0) < K 2 K* log(2p/0) +
8
p
where inequality (i) follows from
38 and uses similar technique in 330 from the proof of Theorem
F22
Non-support
For every j & Sy, by the subadditivity of the probability measure, we have
Eg {1 (1ggd (X) {0}
Splog
18p log
=P
Σ Ex + 2 & log
+ 2 2log
8
8
kEKree
(40)
8p log n
Sp log n
Σ P
(0) 2 k: + 21
llog
2 log
8
kEKroc
(6)
8
/Crecl
<
8plogn
2p
35

---

where inequality (i) follows from
61 in Lemma 2 and the last inequality follows from [Kree - we conclude that
4 log n. Combining 39 and 40
Ey {H (104 (X),
f {1 (1g (X) 1)}
Σ
BJg {1 (1 (X) #0)
jES,
jE8,
|
(p- |
8
p
2p
which completes the proof of Thheorm
G Proof of Theorem
G.1 Lower bound with truncation
Preliminary Firstly, construct a prior uniform distribution of as
n² log clop(p Ing mj
) Krreel for each k E Krees
1 a
P
4 -1
log k
where the constant >> will be determined later. The prior of a corresponds to uniformly distributed truncation K in Kree as
P(K =
for each E Kree-
Kreea
We next construct prior distribution of function E a:) for the given a (i.e., for the given 1 E Kree). Specifically, we assume that only 0 or 1 univariate function can be the support, that is, f= 0, or f fj for j [p). For the support fj. i S ki assume that its i-th entry is drawn from uniform distribution as
A(K) 1/2
-X(e))
0i.5
1/2
where X(k) 112 (clogip logn)) &
1/4
Otherwise just take fij 0. Conversely, f 0 directly indicates 0g 0 for each i E N+ and E [p]. After get an {OigJveNt .iE(s] assume Xij N (0,g. 1/n), indepedently.
Finally, for given derived from k, we get ΣiENi & S 11+20(4). A(k)² 1, indicating the setting of X(k) is valid. Therefore, name the distribution with respect the truncation & and support fj as Pj, and
(XL)).//((L.) + (0 [E(
PIAA (X)
II
II (X i>k
X II
j'AjiEEt
For j (p). we define P, Threel ΣtEK jiki and we also denote by Po the distribution with j = 0, i.e., Xi (0, 1/n) for each (i,j) N+ x lp].
Based on these settings, we transform the minimax lower bound into:
inf sup sup Py (f(X) (23
+ n) > inf sup sup P (f(X) * n)
SEKrenJE(O)Up)
inf sup P, (f(X) + n)
jE(O)Uμg)
x2 divergences calculation For j (p), consider
dP KCreel keXrec
k A(k)
(X)
exp
II
cosh (nX,, A(k)),
dP
2/n
1E k
36

---

which leads that
(x) 2
Ep.
dPo
k: A(k) + 2(K)2)
Eoshh (nXis (nXis X(K)) cosh (nXis X(K)) } knnk'
exp
Kreel
2/n
RVK--RAN
Ecosh (nX,,, (A(R) A(K(I) }
(1)
Σ
cosh [mA(k)A(H')
RAK
Kreel
N, E,Ree
(16)
n². (RAP(A)) (KX
Σ
|Krecl*
2
exp
2 W
E
Ank k' Vk:
[Kreel k,ke
exp
2
log(p lo
where equality (i) follows from Lemma 6 incquality (ii) follows from cosh(x) S exp(2>/2) for every x E and the last equality follows from the definition of A(k).
We now define q = |Kreal
logg
n=a log
log n, and then conclude
1 S
clog(plogn
(P,
Σ M,
exp
2
q
2
Control the wrong recovery probability Inspired by Gao et al. 2020 we divide the set [q] x [g]
into two subset as = {(u, v) [g] x [q] Iu v
log, y) and T2 = {(u, v) E [a] [g]
Iu v > 2 2log 4). therefore [Ti| S 5g loga and [T2]
S q²
We then have
clog(p p log n)
c clog(p log n)
1 1+ x P Po)
exp
exp
2
2q
(u,D)T
(u,e)ET2
log
c clog(p log
clog(p (plggg) logn)
exp
+ exp
2
2q
8'p
8ºp
8
where the last inequality follows from & log(plogr) < log
82
and clog(p log n)
S
40 logg logg
2 Log(5"p/8) log2 n, both of which hold under sufficiently large n. and sufficiently small constant c. Therefore, by Lemma 7 prove that with signal strength
(clog(plogn) n²
0 0< 22 = k. A(K)²
(41)
the wrong recovery probability is out of control, i.e..
inf sup ii a>U (r
sup Py (f(X) + n) 2 inf sup (0)UUp)
Py (f(X) + m) > 1 1 8.
(42)
G.2 Lower bound with sparse structure
Since
log(plog n))
Ai
log(p log n)
(Log(p log n)
2n log logllogu n)
max
n²
n22
n
20
log(p log n))
144a
n 142a
log(p logn).
log(p log m)
< log(p log n),
37

---

we only need to verify the necessity of the separation rate logiplogn) under the condition n 1=1= < log(p log This condition indicates that log log Z logn, n, which leads to ca log(p log n) S log p for some constant Ca determined only by o..
In Theorem strength y²
3. we prove that the wrong recovery probability can be lower bounded by 1 1- if the signal ea logg, Hence, for any valid smoothness parameter a", if n < log log n),, we
have
inf sup 4 a>0 JEF,
sup 28t logty log
Py (f(X)) + 1) 2 inf
sup tolo
Py (f(( + n)
EEF
(43)
21
Therefore, combining
41..
(42 and
(43). we complete the proof of Theorem 5
H Proof of Theorem
This section proves the minimax optimality of the estimator 115
We begin by defining
2²(k) = 1 n2
(VCklogp + +Clog)).
(44)
therefore 0.j = Xij 1iis Ko) E X3 2 Ko/n+t + +X((K))) where recall Kg == min(k E N+ :R S kk/n).
Support For each f E Fe, we denote by Sy the index set of the support covariates in f. For every j E Sy, we have
K
E
f
fz
E
Oig
0is
2
+
Σ
02
1=1
K>
(i)
K2
K2
X2 < Ke/n+ (c/n++>(KK)) xP(ks) 2 + P.a.
E
Xij 0ij
Xij 1
Σ
i=1
K.
Kr
K₂
X2 < K./n + x((k)) + uK.
<2E
(Xig 025) + 2E
x² 1
Σ
1=1
i=1
V=1
4Ke
+ (Ke) + +MKe
n
(45)
where inequality (i) follows from Σisk. K. Og S MK. Eisk. K. 0z/Pz S MK.
Non-support For every j & Sj, we have
E
f
fz
2 2 EE
K
X2
1
Σ
Ke
x3
2
Ke
+ x((xa))
7
n
7/11
Ke
Ka
Ke
+ X2 (
+
E
1
X3 2
(8)
D
Σ
K₂
X3
P
x² jj
Ke
x²((K)
(46)
n
Ke
Ke
Ke
+ n
P
Σ
X2
+ x²{
[==1
(10)
/2Kg
C
Ke
C
3K.
exp
logp p
+
exp
log p
<
4
2
np
38

---

where in inequality (i) follows from Cauchy-Schwaar inequality, inequality (ii) follows from Lemma with taking the constant 2 4.
61 in
Combining the definition of X (k)..
45 and 46 we conclude
/ f
E
fo
+
Σ
E
f
13
JES;
J&S,
4ke
3Kg np
+ 2222(KK,
MK.
+
n
(47)
sKe
8yKe logp
s slogp
n
$log?
k A
max KEN+
ukk
n
n
where the last equality follows from Ke/n + μ.K = maxken+ complete the proof of Theorem 6
( pz). Therefore, by 47 we
I Proof of Theorem 7
This section establishes necessary signal condition for univariate function selection, under the case that we have to only leverage the first Ke entries in X.y for each j E [p]. that is, only use observations [[x]
Iiisk. where Kg min {k: E N+ p & k/n} is the optimal truncation for minimax function estimation, and n =
L1 Lower bound with truncation
Preliminary We first construct prior distribution of function f f F.(22.. Specifically, this prior, only or univariate function can be the support, that is, either f = 0, fy for [p].
In the case = 0, we take 0,₃ = 0 for each (i,j) E N+ [p]. and thus assume X1j ~ (0, 1/n). indepedently. We name the distribution as
Po
II JElPl
00.1/n(X1,j)
In the case / fz. we take 0,,- = 0 for each E N+,J" E [p] \ (i). For the support fjx we introduce two additional parameters À > < k < Ke, which will be determined later. If [k]] assume that its i-th entry is drawn as P (0t.) A) = P (0 = -X) = 1/2. If = K, + 1, we take
8k.+1.j V |KK +2/2 For other we just take 0.,, = O. We name the distribution with respect to the support fg as p,. and (X)
0x.1/m (Xig) + (
II kE(k)
VFKet1/21/0 (x.+1.))
II
/n.1/n(X,)
iEN ((
Distribution of the (K&+1) +11+ entry in
Distribution entries f;
Distribation residual
x II
(x.1/
*JJEEN
Distribation of other fy:
for every E [p]. Based on these settings, we transform the minimax lower bound into:
inf SEF.(r2)
sup Py (I(X(x.)x()) # n)
sup (E
inf 1(X (0.11
P, (?(X(x,)x()) # in)
(e(
inf sup P PyKK.IIM (f(X # n)
jε(O)U[p)
where Pa[K]]x(]] is the marginal distribution of X(Ko)x(p)-
39

---

Control the wrong recovery probability via marginal x2 divergences
For j E [p], consider
exp dP J.K.]xpll (x(x)
1xa 2/n
expp
II aE|k]
cosh (n\Xis),
dP x
which leads that
x² |
dP J.K.]xxpl
(X(r.)xto))
dP 0.[K.]x(pl
nn²**
=cosh (nd²) - v exp
Recall that we only focus on those restricted selectors based on observations X xp]] and hence only focus on the marginal distribution of [[]] Then our aim is to find proper (λ, k)) E RR [K,]
such that:
max A²k;
(48)
subject to: exp
C1
(49)
^² < μKK
(50)
2
< k: < Ke.
(51)
where 49 controls the average x2 divergence and ej is sufficiently small positive constant,
(50)
ensures our construction is in the ellipsoid &, and (51) ensures that the truncation k is valid. Therefore, by Lemma] 7 we prove that with signal strength
< :" k X2
M.
C2
Voloog A Ms) + [KKot1 n
(52)
2
[E(K.)
the wrong recovery probability is lower bounded by 1/2:
inf MX [X
sup Ps (f(X(x))b)) + 1)
(E2,
(53)
inf ((
sup P Pac.aab (i(X(K))xb)) fn) 2 jE(0)up)
1.2 Lower bound with sparse structure
We now quantify the influence the sparse structure on the necessary signal condition. Similarly to Section [.1 first construct prior distribution of function Fr where only 0 univariate function can be the support.
In the case f 0, we still take
Po = II
00.1/m(Xi.j)
VEK+
JElP
For every j E [p), in the case f = [J+ only take the first entry 01,5 X, and take other 0,,y' 0. The distribution is described as
(x(X)=
0x,1/n (X1,))
II (Xis 122
II
(0.1//((i.)))
*jJJeN-
Distribution of the first entry in fy
Distribation of the residual entries in
Distribation other f
Based these settings, transform the minimax lower bound into:
inf sup Py (#(XIx.)xl)) & n)
R(X (E
(EF.(r?)
inf sup P P.I.IIill je(o)U[p]
# 1)
((00))
40

---

It is straightforward to check that
x² (P (Pal Po.K.) = exp (n12) 1.
Therefore, our aim find proper R such that:
max : X²,
(54)
subject to: exp (nd2) S C4 P.
(55)
X² S pl,
(56)
where (55) controls the average x2 divergence and c₃ is sufficiently small positive constant, (56)
ensures our construction is in the ellipsoid & Under assumption n that with signal strength
logg, by Lemma 7 prove
p S CB log
(57)
the wrong recovery probability is lower bounded by 1/2:
inf sup M0K
f (f (f(xXI.))bb)) + n)
SEF.
(58)
inf ( and (8). we complete the proof of Theorem
sup [E]Up]p
Paciiib (f(X # 1) 2
Therefore, combining
52 53
57
Some extended conclusions
This appendix discusses theoretical results obtained under assumptions more general than those in the main text.
J.1 Violating the separate rate
In more realistic setting where the true signal strength || may fall below the minimax threshold, our selectors still have some useful properties:
1. The selector from Theorem D selects most 2s variables with probability at least 1 d (proved by following equation (34) in Appendix(D.2
2. The selector from equation guarantees zero false positives (proved by following Appendix C.2.3).
II ensures Š S with probability at least - 6, i.e.,
These guarantees hold without knowing the signal strength of each fy advance, showing that our selectors remain both sparse and interpretable under a practical condition.
We also provide specific example in which procedures appropriate. Consider system with channels, some of which carry a true signal while the rest are pure white noise, and we aim to identify those channels with signal. Then the selector (11) achieves that, with high probability, noise-only channel is selected, and any channel whose signal strength exceeds the minimax separation rate (IO) will be selected. In this way, selector provides sille-positive-free method for this problem.
J.2 Heterogeneous univariate functions
We now extend our framework heterogeneous settings where E H. and H, might be different across j E [p]. This setting was considered in Raskutti et al. 2012 for function estimation. Define the parameter space:
F.
1=
J3 jE(p)
ΣE:
Σ JELN
10, s ( U (0) for all j E [p]
where
Hr = fg Σ ch
Σ
1
Mij
Heterogeneity across H, is captured via distinct sequence {m4 for for every j lp).
41

---

Upper bound
We apply component wise selector
th =
x 2 Kj + 2 K, log(2p/6) log(2p/))
n
where Ky = min k N+
Maj S
Vloogr
and recall n 0_ If the condition
n
log
Vologg
A (1s))) }}
2 2 Co
max
n
KEN+
n2
holds for every j E [p], we have the exact support recovery guarantee
Ps (S(X)= (S))))sss)>>>>)) 2 1 6.
inf
fE
The proof proceeds analogously to that given in Appendix
Lower bound
We next prove that, there exists some
E
[p]
with r3
logg + max V'oggg A pus) for sufficiently small constant then no selector can
achieve consistent support recovery.
Define
{ f- Σ Ogti:: Og E {), -M; if kj, 0i = - kg
Fleasti ==
where >z. k will be clarified later. We then design the least favorable
Fleast U UVs
jElPI
The set Fleast assumes that at most one univariate function could be the support, and the very support has weak signal strength r3 = X2kg. Then get
inf sup P (S(X) +())) 2 inf max P, (S(X) +(1)) JEFienet
9 j=0.-.
where P, follows similar definition in Appendix
I.I Then, if
8²p
-1)
< 2(2 - 8)
1,
jE(2]
we obtain
inf sup P, (5())+ 2 fEFienst
for arbitrary constant 5 E (0, 1). Therefore, it suffices consider the optimization problem
max : 22ky,
n A²
subject to: exp
Sa Pp
X7k3 S pK,,
for every [p]. The result shows that r3 27kg I emaNNeN+ selection.
(Vkloge 1
pkj) leads unreliable
log On the other hand, by assuming -2 minjety #iy and following the proof technique in Appendix 1.2 we can prove that 23 < %clog logg also leads unreliable selection, therefore we prove the matching lower bound.
42

---

K
Technical Lemma
The following Lemma shows that, f E F it suffices only consider those selectors depending on || V
iim1 x
Lemma (Norm selector) Assume K is positive integer satisfying pk 2 For every measur- able function w(:--) and for every selector ij (Xxxp) = (in (Nxxp),"" A1p (Xxxp)) E {0, 13.
there exists randomized selector i7 (11x,,112," pl12) such that
Ey(w(h,((f))) 2 sup Ef(w(),((f)))- (-F
sup
(EF(K)(2))
Taking w(x, v) 1x + y). we get
sup f fEF!") (12)
sup py(ī+((1)) SEF (r2)
The proof Lemma D is as similar as the proof of Lemma
Butucea et al. (2023a], with additional checking that 2 < 110,XI = ||I: 112 < μж holds for every orthogonal matrix Oj E R. k every X. E Fi:k (r²) and every index j E (j f
Lemma 2 (Chi-squared inequalities) Let (B) denote x2 random variable with k degrees of freedom and non-centrality parameter 2 0. Then for every a > O, there exist absolute constants 0 and 02 (0, 1) such that
P (x210) k Vvv 61
2020
(59)
xx2
P (x2(0) - x) expp
(60)
4k
P ((2(BB) 2 k+ (xx
2 2/ 2B) 2x
SE
(61)
Inequalities 15.,.
60 and (61 are proved in Corollary 3 in Zhang and Zhou 2020], Theorem 2 in
Ghosh 2021| and Lemma 8.I Birge [2007] respectively.
Lemma 3 (Minimax lower bound based on combined risk, Abraham et al. [2024) Assume we observe X Pe.6 8 E IPP For any prior क (of 0) on RP, we denote by P., the distribution of (X, 0) in the Bayesian model. Then, for all < S all (0, and all measurable e C R?, we have:
inf sup R(0,)) 2 + 1111 (1-
nPr (l[@llo s) -2P 2P $ 0),
ip dee
for some universal constant
0, where
P 00 O. P. (0, 0| 1
Lemma is derived from Theorem S-3 in the supplementary of p and the combined risk
Abraham et al. 2024 with taking
En,0= I V jEEpp Pg
Ei 99))
R(0, sp) = Eg
Lemma 4 (Truncation for classification) Assume C 0 is postive constant and K(C)
min k E N+ pak S CCV/looli then under assumption n Clog(p-s) we have
Pi
/ R(O)
log(p 8)
le log(p s)
x max KEN
Hk A
71
43

---

C Cykloggp-s)
K(C) -1 K(O)
v log(p-s)
C CVK(O) K(o) log(p-s) 8]
Figure 5: A guide
show
and
(y(Ro)) (og(p-s)
max ( n
Proof (Proof of Lemma 4) The proof is inspired by Lemma 2.1 in Kotekal and Gao (2024]. By
taking 1 and n Cllo(pps)) we have μl
C log(p-=) Vlog(p-o) 8) which shows K(C) 2
n
n
For every k 2 K(O), by definition of K(C), we conclude Pe I pkics S CVKiCilogte log(p-s) S
() which leads that p4 Cv/log(o-s) Mi S pK(0), For every S S K(O)
we conclude μı 2 11 -1
Cvklog(p-s) which leads that pu A
C /v/k log(m=s) C Co/logiope)
CV(KiO)- (1) 1)0((p0=>) Therefore, we conclude that
C Cv k log(p
CV(KI)) 11) log(p
max
μk A
max [KKOO)
KEN+
n
n
see Figure for clear demonstration. And it is straightforward that
C K(C) log(p - s) 2 max
C (V(I))) log(p 8)
(62)
n
Besides, from K(C) 2 2, we get K(0) < 2(((()) - 1), therefore
C ((K()))og(p - 8) CV2(K(() - 1) log(p -
< max (KI0), CV(K(O) 1) log(p 8)
(63)
C Cyklog(p - 8)
= max KEN
14 A
From 62 and 63
we conclude
((C) log(p
C "Vklog(p 8)
klog(p 8)
max
14 A
max
KENI
T1
KEN
which completes the proof of Lemma
Following the same proof technique, get the following results.
44

---

Lemma 5 (Truncation for joint estimation and multiple testing) Assume C > is positive con-
stant and K(C)- == min NT pk S C C.V (log(p/e)
then under assumption Cloípp/s)
we
have
Cylllo(pps)
CVKiO log(p/s)
CV Cvllog(pp/ s)
max KENT
PA
2 max AEN+
PR A
n
n
n2
which means
K(C) log(p/8)
v log(p/s)
max KEN
p4 A
n
Besides, define K" = min k EN pe I
then under assumption n. >
p12" we have
Vk
K
VE
max
Pk A
/ max
1k A
KEN
KENT
Lemma (Expectation with hyperbolic cosine) Assume X ~ N(0, 1/n), k1, k2 are two positive integers, then we have
} A1
As ki
{ E cosh (nXA(k))) cosh (nxX)(k2))
x Ecosh [nX (A(k)) A A(k2))]
= cosh coshh&Ahk (nA(ks))A())) x exp
(kg [K) k2) A(ka V 122 + (ks A K2) A(ki 1b2))))
where X() can be arbitrary non-increasing function on N+
Proof 2 (Proof of Lemma By cosh(z1) cosh((2) =
1 2 (cosh(21 + x22) + cosh(a1 x22) and
(o,)((,1) cosh(Ax) ex²12 we derive that
E Eosh (nx)())))) cosh (nX)(ka))
and
Eosh [nx (A(k)) A A(k2)) = AA0A)))
Therefore
[Ecohh (mXA((s)) cosh (nx((ks)) } K1
ks K
E Eosh [nX (A(k1) A A(k2)))
-osh (mA(k1)2(H2))
exp (5( + A(k2))) (k1 A k2) A(k2 k2g) (k1 V k2 k, ^ k2)
bo (nA(k)) exp 2
n
(h1 V v2) A(ka k2)² + (kn A k2) A(ks kz))
which completes the proof of Lemma
6
Lemma 7 (Minimax lower bound in x² divergence) For a given constant 8 E (0, 1), assume that
Po. P,....,,PP be p probability measures satisfying p 2 4/8² and
82p
(P, < 3(2-8) Σ p
Then
inf sup 21 5/2)3 8- 5,
o5iSp
where inf represents the infimum over all tests of the form 1 X - 1. ,p} with X ~ P.-.
The proof of Lemma 7 follows from Proposition 2.4 of Tsybakov 2009 with taking M p.
82p
and 2-5
O.
2]
45


Reviews:
[{"review_id": "rTVdbST6C5", "reviewer": "Reviewer_hVsu", "summary": "This paper considers variable selection in a sparse additive model. Assuming the existence of an orthonormal basis, the  problem is reformulated as follows: For each $1\\leq j\\leq p$, we observe an infinite sequence $X_{ij}\\sim N(\\theta_{ij}, 1/n)$, where $\\theta_{ij}$ is the true coefficient of the $j$th function on the $i$th basis, satisfying that $\\sum_i \\frac{\\theta^2_{ij}}{\\mu_i}<1$. It is assumed that for most $j$, the infinite sequence {$\\theta_{ij}$}$_{i\\geq 1}$ is a zero sequence (i.e., the $j$th function $f_j$ is a zero function). The variable selection goal is to identify those $j$ such that $f_j$ is nonzero. \n\nThe authors consider two loss metrics, the sum of FDR and FNR, and the wrong recovery probability. For loss metric, the minimax order of signal strength for success has been derived. Compared to the previous work on estimation, the authors found that the minimax order has a factor of $\\log(p/s)$ or $\\log(p)$, which is considered as the ``interplay\" between high-dimensional selection error and estimation error of each individual function $f_j$.", "questions": "When $\\mu_k$'s are unknown, how to implement the selector?", "limitations": "No numerical work and real applications.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "1. There is a gap here transiting from the sparse additive model to the model of $X_{ij}=\\theta_{ij}+N(0,1/n)$ for infinite $j$. For people who are familiar with this problem, it may be straightforward. But for general readers, it is better to explain it. For example, there is no sample size $n$ in the current setting. The readers may get confused why $n$ appears here (it is actually a re-parametrization, right?). \n\n2. The \"interplay\" discovered here is a result of the loss function for variable selection. I don't really understand why this is a \"subtle and critical\" phenomenon. For example, in Gaussian sequence model, we need to set the threshold at $\\log(p/s)$ or $\\log(p)$ to achieve successful selection. What is special here? \n\n3. In a remark, the authors mention that the non-trivial part is due to the truncated chi-square statistics, in which we need to choose the truncation parameter $K$. However, is there any particular technical difficulty here? The novelty of the theory compared to those for Gaussian sequence model needs to be clarified. \n\n4. A major limitation of this work is that there is completely no numerical work and applications.", "was_revised": true, "final_justification": "Based on the author rebuttal, I am more convinced that the paper contains some technically significant result. Even though I still think this paper is more of a theoretical statistical journal paper than a conference paper, I'm willing to raise my score.", "rebuttal": "We sincerely appreciate your thoughtful summary and evaluation of our work. Below, we will provide a response that centers around weaknesses and questions related to our paper.\n\n# Weaknesses: \n\n## 1. There is a gap here transiting from the sparse additive model to the model of $X_{ij} = \\theta_{ij} + N(0,1/n)$ for infinite $j$...\n\n**Reply:** We illustrate the connection between these two models through a simple example: consider $N$ i.i.d. observations $(X_1^k,\\cdots, X_p^k, Y^k)\\_{k\\in[N]}$ follow the sparse additive model \n$$Y^k = \\sum_{j\\in[p]} f_j(X_j^k)+\\epsilon^k = \\sum_{j\\in[p]} \\sum_{i\\in \\mathbb N^+} \\theta_{ij} \\psi_i(X_j^k) + \\epsilon^k,$$\nwhere $\\\\{\\psi_i \\\\}\\_{i\\in \\mathbb N^+}$ is an orthonormal basis on $[0,1]$, each $X_j^k\\sim\\mathrm{Unif}(0,1)$ independently, and $\\epsilon^k\\sim N(0,\\sigma^2)$. Define the projection estimator\n$$\n\\hat\\theta_{ij} = \\frac1N \\sum_{k\\in[N]} \\psi_i(X_j^k)\\cdot Y^k\n$$\nBy orthonormality and independence, we have \n$\\hat\\theta\\_{ij}\\approx \\theta\\_{ij} + \\frac1N \\sum\\_{k\\in[N]} \\psi_i(X_j^k)\\cdot \\epsilon^k$, and therefore $\\hat\\theta_{ij}$ approximately follows from the distribution $N(\\theta_{ij}, \\sigma^2/N)$.\n\nBy a re-parametrization $n := N/\\sigma^2$, we then establish the link between the sparse additive model and the Gaussian white noise model $X_{ij} = \\theta_{ij} + N(0,1/n)$. For a rigorous account of this relationship, see, e.g., Tsybakov[1] and Reiß[2]. We will add the above analysis to the appendix. The Gaussian white noise model simplifies the analysis by avoiding technical complexities (e.g., variable correlations) while preserving focus on essential structures (e.g., sparsity and smoothness constraints). Therefore, we adopt this model for our study.\n\n## 2. The \"interplay\" discovered here is a result of the loss function for variable selection. I don't really understand why this is a \"subtle and critical\" phenomenon. For example, in Gaussian sequence model, we need to set the threshold at $\\log(p/s)$ or $\\log p$ to achieve successful selection. What is special here?\n\n**Reply:** To illustrate why the interplay between sparsity and truncation is subtle and critical, we use the Sobolev setting ($\\mu_k = k^{-2\\alpha}$) as an example and answer from two aspects:\n\n**How sparse structure affects the truncation.**\nWe revisit the function estimation problem in SpAM, where Raskutti et al.[3] established the minimax rate as\n$$\n\\inf_{\\hat{f}} \\sup_{f \\in \\mathcal F_s} \\mathbf E_f \\\\| \\hat{f}(X) - f  \\\\|_2^2  \\asymp s \\times \\frac{\\log(ep/s)}{n}  + s  \\times \\max\\_{k \\in \\mathbb N^+} \\left( \\frac{k}{n} \\wedge \\mu_k \\right),\n$$\nhence the optimal truncation $K$ satisfies $K \\asymp n^{\\frac1{1+2\\alpha}}$, independent of the sparsity structure $\\log(p/s)$.\n\nReturning to the variable selection problem in SpAM, in equation (8) we show that the optimal truncation level satisfies $\\frac{\\sqrt{K \\log(p/s)}}{n} \\asymp K^{-2\\alpha}$, i.e., $K \\asymp \\left(\\frac{n^2}{\\log(p/s)} \\right)^{\\frac{1}{1+ 4 \\alpha}}$. By contrast, the term $\\log(p/s)$ does not affect the truncation $K$ for optimal function estimation, while it directly affects the truncation $K$ for optimal variable selection: the higher the term $\\log(p/s)$, the fewer basis terms are needed. \nThis phenomenon appears under both the FDR+FNR loss (Section 3.1) and the Hamming loss (Section 3.2), highlighting a fundamental distinction between function estimation and variable selection. Exploiting this insight, we propose Theorem 7 and demonstrate that an optimal function estimation can be suboptimal for the variable selection in SpAM.\n\n**How sparse structure affects the threshold.** Consider the selector $\\hat \\eta_j^{test} (X_{\\cdot j}) = \\mathbf1 \\left( \\sum_{i=1}^{K } X_{ij}^2 - \\frac{K}{n}  \\ge  \\lambda^2 \\right)$ with $K \\asymp \\left(\\frac{n^2}{\\log(p/s)} \\right)^{\\frac{1}{1+ 4 \\alpha}}$. By Theorems 1 and 2, we reveal a phase transition in the optimal threshold $\\lambda^2$: If $n\\prec \\log^{1+2\\alpha}(p/s)$, then $\\lambda^2\\asymp\\tfrac{\\log(p/s)}n$; if $n\\gtrsim\\log^{1+2\\alpha}(p/s)$, then $\\lambda^2 \\asymp n^{-\\frac{4\\alpha}{4\\alpha+1}} \\log ^{\\frac{2\\alpha}{4\\alpha+1}}(p/s)$. No such phase transition phenomenon appears in the Gaussian sequence model (Butucea et al.[4]; Abraham et al.[5]).\n\nIn summary, we do not merely \"found that the minimax order has a factor of $\\log(p/s)$ or $\\log p$\"; we derive a general and nonasymptotic minimax separation rate for variable selection, which in turn reveals the fundamental distinction between function estimation and variable selection in SpAM.\n\n \n## 3. In a remark, the authors mention that the non-trivial part is due to the truncated chi-square statistics, in which we need to choose the truncation parameter $K$. However, is there any particular technical difficulty here? The novelty of the theory compared to those for Gaussian sequence model needs to be clarified.\n\n**Reply:** We will discuss our technical difficulty and novelty from the perspectives of upper and lower bounds, respectively:\n\n**Upper bounds:** \n\n**(i)** We finely balance the truncation level $K$ against the signal strength (in equation (28) and Lemma 4), ensuring that the signal after truncation remains large enough for reliable selection. \n\n**(ii)** Controlling the missed selection probability in SpAM requires more complex probabilistic tools (in Appendix C.2.2) than in the Gaussian sequence model. \n\n**(iii)** To bound the false discovery rate, we have to partition the expectation into three cases and analyze each separately (in Appendix D.2), which increases the technical difficulty.\n\n**Lower bounds:** \n\n**(i)** Rather than relying on classical Le Cam's or Fano's method, we adopt a novel probabilistic technique (inspired by Butucea et al.[6]) that leverages the monotonicity of likelihood ratios to analyze the selection lower bound (in Appendix C.1). We believe this technique could also be effective for other complex variable selection problems. \n\n**(ii)** In handling adaptation to the Sobolev smoothness parameter $\\alpha$ in Theorem 5, we construct joint priors on $\\alpha$ and the element-wise signal strengths with inherent dependence. This coupling complicates the calculations and scaling arguments of the chi-square divergence (in Appendix G.1). Therefore, the lower bound analysis is more involved than in the Gaussian sequence model, as the latter does not involve smoothness parameters or truncation levels.\n\nAdditionally, Theorem 7 reveals a novel \"**estimation-selection gap**\" in SpAM: some estimators that are optimal for function estimation cannot yield optimal variable selection performance. This divergence does not occur in the Gaussian sequence model, where a proper thresholding estimator simultaneously guarantees minimax optimality in both estimation and variable selection (Butucea et al.[4]; Ndaoud[7]). \n\n\n## 4. A major limitation of this work is that there is completely no numerical work and applications.\n\n**Reply:** In Appendix B, we have presented three sets of numerical experiments, all evaluated via FDR+FNR loss and Hamming loss, that respectively examine: \n\n**(i)** The impact of dimension $p$ and signal strength $r^2$.\n\n**(ii)** The impact of $n$ and different truncation locations.\n\n**(iii)** The impact of unknown smoothness parameters.\n\nThese experiments confirm the minimax optimality of our methods and illustrate that, in sparse additive models, an estimator that is minimax optimal for function estimation may not achieve minimax optimal variable selection (see results in Appendix B.2). We believe these numerical results could reinforce our theoretical contributions.\n\n\n# Questions:\n\n## 1. When $\\mu_k$'s are unknown, how to implement the selector?\n\n**Reply:** Thank you for this question. In Section 4, we handle the adaptation problem by working on a Sobolev space ($\\mu_k\\asymp k^{-2\\alpha}$) with unknown smoothness parameter $\\alpha>0$. We then introduce a fully data-driven selector (equation (12)) that adapts to the unknown smoothness $\\alpha$. Theorems 4 and 5 establish that this adaptive procedure attains the minimax separation rate up to an extra $\\log(\\log n)$ term, which is also the necessary cost of adaptation. Since Sobolev spaces are a canonical model in nonparametric statistics (Tsybakov[1]) and deep learning theory (Li and Lin[8]), our approach provides a practical implementation when $\\mu_k$'s are unknown.\n\n\n**Reference**\n\n[1] Alexandre B. Tsybakov. Introduction to nonparametric estimation. Springer Ser. Stat. New York, NY: Springer, 2009.\n\n[2] Markus Reiß. (2008). Asymptotic equivalence for nonparametric regression with multivariate and random design. The Annals of Statistics, 36(4), 1957-1982.\n\n[3] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. Journal of machine learning research, 13(2), 2012.\n\n[4] Cristina Butucea, Mohamed Ndaoud, Natalia A. Stepanova, and Alexandre B. Tsybakov. Variable selection with Hamming loss. The Annals of Statistics, 46(5):1837-1875, 2018.\n\n[5] Kweku Abraham, Ismaël Castillo, and Étienne Roquain. Sharp multiple testing boundary for sparse sequences. The Annals of Statistics, 52(4):1564-1591, 2024.\n\n[6] Cristina Butucea, Enno Mammen, Mohamed Ndaoud, and Alexandre B. Tsybakov. Variable selection, monotone likelihood ratio and group sparsity. The Annals of Statistics, 51(1):312-333, 2023.\n\n[7] Mohamed Ndaoud. Interplay of minimax estimation and minimax support recovery under sparsity. volume 98 of Proceedings of Machine Learning Research, 647-668, 2019.\n\n[8] Li, Yicheng, and Qian Lin. On the asymptotic learning curves of kernel ridge regression under power-law decay. Advances in Neural Information Processing Systems 36 (2023): 49341-49364."}, {"review_id": "RGqsHctQzE", "reviewer": "Reviewer_BfNF", "summary": "This paper studies the model selection problem in sparse additive model (SpAM), under a gaussian white noise (GWN) observation model. More specifically, it assumes that the dependence of the response on each of the relevant coordinates is modeled by a function belonging to an ellipsoid, and studies the problem of determining which coordinates of the input vector affect the output. \nUnder a separation assumption between relevant and irrelevant coordinates, it determines minimax rates for this model selection problem.", "questions": "General question:\n- Can you describe some concrete examples in which this exact recovery criterion (and the associated minimum strength assumption) are appropriate, and the work presented here provides some insights?\n\nA couple of minor points:\n-Above the (speculation) formula in Section 2.2. Here you did not yet define formally the problem, so it is unclear what does this speculation refer to.\n-Above Theorem 1: Please avoid \"sophisticated analysis\", this is a judgement that you are expressing about your own work.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths. The problem is quite canonical and the gives a complete answer for what concern rates. \nThe paper is also clear and easy to read.\n\nWeaknesses: Technically, the treatment is quite standard. \nAlso, such exact support  recovery questions require to assume a separation condition (either y is independent of coordinate x_i, or the dependence is above a minimum value). This separation is typically considered unrealistic, so other forms of recoveries are of greater relevance.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your recognition of the value, completeness, and readability of our work.\nBelow, we will provide a response that centers around weaknesses and questions related to our paper.\n\n# Weaknesses: \n\n## 1. Technically, the treatment is quite standard. Also, such exact support recovery questions require to assume a separation condition (either y is independent of coordinate $x_i$, or the dependence is above a minimum value). This separation is typically considered unrealistic, so other forms of recoveries are of greater relevance.\n\n**Reply:** We acknowledge that some elements in our paper, such as the loss function settings and the definition of the minimax separation rates, are standard.\n However, the results we obtain within this framework are novel and offer fresh insights: \n \n **(i)** We propose general and non-asymptotic minimax separation rates of the variable selection problem in the SpAM, which is, to our knowledge, the first optimal finite-sample guarantee. \n \n **(ii)** We provide a selection procedure adaptive to the unknown smoothness parameter of the Sobolev spaces, and prove that an additional $\\log(\\log n)$ term is necessary for this adaptation.\n \n **(iii)** We demonstrate that the optimal function estimators can be suboptimal in univariate function selection, highlighting the distinction between function estimation and variable selection in SpAM.\n\nAdditionally, in a more realistic setting where **the true signal may fall below the minimax threshold**, our selectors still have some useful properties: \n\n**(i)** The selector from Theorem 1 selects at most $2s$ variables with probability at least $1-\\delta$ (proved by following equation (33) in Appendix D.2). \n\n**(ii)** The selector from equation (10) ensures $\\hat S \\subseteq S$ with probability at least $1-\\delta$, i.e., it guarantees zero false positives (proved by following Appendix C.2.3).\n\nThese guarantees hold without knowing the signal strength of each $f_j$ in advance, showing that our selectors remain both sparse and interpretable under a realistic condition. We hope these results could address your concern about the unrealistic assumptions.\n\n# Questions:\n\n## 1. Can you describe some concrete examples in which this exact recovery criterion (and the associated minimum strength assumption) are appropriate, and the work presented here provides some insights?\n\n**Reply:** Thank you for the question. We will illustrate the value of our selectors through two examples:\n\n**Multi-channel signal selection.** Consider a system with $p$ channels, some of which carry a true signal while the rest are pure white noise, and we aim to identify those channels with a signal. Then our selector (equation (10)) achieves that, with high probability: **(i)** no noise-only channel is selected; **(ii)** any channel whose signal strength exceeds the minimax separation rate (equation (9)) will be selected. In this way, our selector provides a false-positive-free method for this problem.\n\n**Norm estimation.** Consider estimating the $L_2$ norm of each univariate function, i.e., jointly estimating $N(f) = (\\\\| f\\_1 \\\\|\\_2, \\cdots, \\\\| f\\_p \\\\|\\_2 ) \\in \\mathbb R^p$. These norms quantify each covariate’s strength and play a key role in confidence interval construction. By using our thresholding selector (equation (6)), we define the norm estimator for each $f_j$ as\n $$\n\\hat N_j = \\sqrt{ \\sum\\_{i=1}^{K } X\\_{ij}^2 - K/n } \\cdot \\mathbf1 \\left( n\\sum\\_{i=1}^{K } X\\_{ij}^2-K \\ge 2\\sqrt{K \\log(p/s)} +2\\log(p/s)\\right), \\text{ for all } j \\in [p],\n$$\nwhere $K= \\min \\left\\\\{ k \\in \\mathbb{N}^+: \\mu_k \\le \\frac{\\sqrt{k \\log(p/s)}}{n} \\right\\\\}$. We can show that the minimax estimation rate\n$$\n\\inf_{\\hat N} \\sup_{f \\in \\mathcal F_s} \\mathbf E_f \\left\\\\| \\hat N - N(f) \\right\\\\|_2^2 \n\\asymp \\frac{s \\log(p/s)}{n} + s \\times \\max\\_{k \\in \\mathbb N^+}\\left( \\frac{ \\sqrt{k \\log(p/s)} }{n } \\wedge \\mu_k \\right),\n$$\nand our norm estimator is minimax rate-optimal.\nHowever, a naive plug-in estimator based on the optimal function estimation (in Section 5) may fail to attain the minimax optimality.  \n\nThese two examples illustrate both the practical relevance and theoretical insights offered by our truncation-based selectors.\n\n\n## 2. Above the (speculation) formula in Section 2.2. Here you did not yet define formally the problem, so it is unclear what does this speculation refer to. \n\n**Reply:** Thank you for the suggestion. We agree that the speculation formula is clearer when presented after the formal problem definition. We have moved the speculation formula to appear immediately after Definition 1 in the revised manuscript. This formula conjectures that the minimax separation rate (for sparse multiple testing) is the sum of: **(i)** the high‑dimensional selection error $\\tfrac{\\log(ep/s)}{n}$ (Abraham et al.[1]), and **(ii)** the univariate detection rate $\\max_{k\\in\\mathbb N^+}\\bigl(\\tfrac{\\sqrt{k}}{n}\\wedge\\mu_k\\bigr)$ (Baraud[2]). Then Theorems 1 and 2 show that this conjecture is incorrect, and Remark 1 explains why.\n    \n## 3.  Above Theorem 1: Please avoid \"sophisticated analysis\", this is a judgement that you are expressing about your own work.\n\n**Reply:** Thank you for pointing this out. We have removed this subjective phrasing and reviewed the manuscript to ensure no similar expressions remain.\n\n**Reference**\n\n[1] Kweku Abraham, Ismaël Castillo, and Étienne Roquain. Sharp multiple testing boundary for sparse sequences. The Annals of Statistics, 52(4):1564-1591, 2024.\n\n[2] Yannick Baraud. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8(5): 577-606, 2002."}, {"review_id": "7gtJ8tG1XC", "reviewer": "Reviewer_8MUY", "summary": "This work establishes minimax separation rates for sparse additive models with Gaussian white noise, from the perspectives of sparse multiple testing and support recovery.", "questions": "1. Since variable selection in additive models is well-studied, could you elaborate on the proposed truncation method's strengths over existing approaches, such as its ease of tuning?  \n\n2. In Corollary 1 for the finite-dimensional case, the setting resembles the detection boundary in signal testing. Could you derive a more specific bound on the relationship between $\\epsilon_{\\text{test}}$ and the number of non-zero components $m$, together with $\\mu_1>0$?  \n\n3. For the selector's truncation set  $\\mathcal{K}_{rec}$  that adapts to unknown smoothness parameters, can bases other than 2 be chosen (e.g., base 3)? What is the essential impact of using base 2?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: 1. Establishes minimax rates that integrate smoothness conditions, providing theoretical bounds for sparse additive models under Gaussian noise.  2. Proposes adaptive schemes to accommodate varying smoothness levels, enhancing practical applicability.   3. Clarifies key distinctions between optimal estimation and variable selection to avoid conceptual confusion.\n\nWeaknesses:  While variable selection in additive models is a well-studied, the study lacks experimental comparisons between the proposed truncation method and existing selection approaches.", "was_revised": true, "final_justification": "I am satisfied with this paper. The authors have thoroughly addressed all the further questions I raised regarding the work, providing clear and insightful responses that effectively resolved my concerns. The rebuttal is also of high quality and I have decided to maintain my original score.", "rebuttal": "We sincerely appreciate your recognition of the minimax separation rates, adaptation, and the key distinctions between estimation and selection.\nBelow, we will provide a response that centers around weaknesses and questions related to our paper.\n\n# Weaknesses: \n\n## 1. While variable selection in additive models is a well-studied, the study lacks experimental comparisons between the proposed truncation method and existing selection approaches.\n\n**Reply:** While we did not directly benchmark against other existing selection approaches, Appendix B.2 provides a comprehensive comparison of four methods based on truncation: \n\n**(i)** the rate-optimal selector proposed in Section 3 (Optimal method);\n\n**(ii)** the adaptive selector proposed in Section 4 (Adaptation method);\n\n**(iii)** the selector based on the optimal truncation in the single univariate function detection problem (Baraud[1], Univariate method); \n\n**(iv)** the selector based on the optimal truncation in the function estimation problem (Birgé and Massart[2], Suboptimal method). \n\nUnder both FDR+FNR loss and Hamming loss, the “Optimal” and “Adaptation” methods maintain the lowest selection errors across most regimes. These simulations also confirm the finding from Section 5 that a minimax-optimal function estimation may fail to guarantee optimal variable selection.\n\nMoreover, Appendix B.1 examines the impact of dimension $p$ and signal strength $r^2$, and Appendix B.3 examines the impact of unknown smoothness parameters. In each case, the experimental results align closely with our theoretical results. We hope these comparisons could address your concerns.\n\n# Questions:\n\n## 1. Since variable selection in additive models is well-studied, could you elaborate on the proposed truncation method's strengths over existing approaches, such as its ease of tuning?\n\n**Reply:** Our truncation-based selector offers three key advantages:\n\n**Minimax optimality.** In Section 3, we establish that our method achieves consistent variable selection precisely at the minimax separation rate, which is the necessary and sufficient signal strength for reliable selection. In contrast, most existing methods require signal levels substantially above the minimax separation rate (Dai et al.[3]).\nAdditionally, in Section 5, we demonstrate that some function-estimation-based selectors---even achieving minimax optimal estimation---may fail to attain optimal variable selection performance, thereby underscoring the superiority of our direct-selection-based procedure.\n\n**Adaptation to smoothness.** In Section 4, we consider the Sobolev classes $\\mu_k=k^{-2\\alpha}$ with smoothness parameter $\\alpha>0$, and derive the minimax separation rate when $\\alpha$ is unknown. Our adaptive method remains rate-optimal without prior knowledge of $\\alpha$, thereby demonstrating adaptive robustness unavailable in most existing methods.\n\n**Ease of tuning and extensibility.** Our algorithm involves only two tuning parameters: the truncation location and the universal threshold, making it more straightforward to calibrate than those penalty-based methods. Besides, our method is built on the fundamental concept of hard-thresholding operator, which we believe endows our method with broad extensibility (see Appendix A).\n\n\n## 2. In Corollary 1 for the finite-dimensional case, the setting resembles the detection boundary in signal testing. Could you derive a more specific bound on the relationship between $\\epsilon_{test}$ and the number of non-zero components $m$, together with $\\mu_1>0$?\n\n**Reply:** For clarity, we set $\\mu_1 =\\cdots = \\mu_m>0$, and $\\frac{\\log(p/s)}n \\le \\mu_1$. Then we discuss the minimax separation rate of the finite dimension case in two regimes:\n\n**(a)** If $\\mu_1 \\lesssim \\frac{\\sqrt{m \\log(p/s)}}{n}$, then we derive that $\\mu_1\\vee \\frac{ \\log(p/s)}{n} \\lesssim \\frac{\\sqrt{m \\log(p/s)}}{n}$, leading $m \\gtrsim n\\mu_1$. In this case $\\epsilon_{test}^2 \\asymp \\frac{ \\log (p/s)}{n} + \\mu_1 \\asymp \\mu_1$.\n\n**(b)** If $\\mu_1 \\succ \\frac{\\sqrt{m \\log(p/s)}}{n}$, then we get $\\epsilon_{test}^2 \\asymp \\frac{ \\log (p/s)}{n} + \\frac{\\sqrt{m \\log (p/s)}}{n}$, which aligns with the minimax separation rate in the group sparsity setting (Butucea et al.[4]).\n\nCombining these cases gives a more precise separation rate $\\epsilon_{test}^2 \\asymp \\min\\left(\\frac{ \\log (p/s)+\\sqrt{m \\log (p/s)}}{n} ,~ \\mu_1\\right)$. Here the minimum reflects our ellipsoid space constraint: Since $\\\\|f_j \\\\|_2^2 = \\sum\\_{i \\in \\mathbb N^+} \\theta\\_{ij}^2 \\le \\mu_1 \\sum\\_{i \\in \\mathbb N^+} \\frac{\\theta\\_{ij}^2}{\\mu_i} \\le \\mu_1$, each $f_j$ has its squared $L_2$ norm upper bounded by $\\mu_1$. \n    \nIn addition, there are two remarks:\n\n**Remark I.** In case (a) we have $\\epsilon_{test}^2\\asymp \\mu_1$. In other words, to control FDR+FNR, we would need every active univariate function $f_j$ to satisfy $\\\\|f\\_j\\\\|\\_2\\ge C\\mu_1$ for some large constant $C>0$. However, by definition of $\\mathcal E$ and $\\mathcal F_s(r^2)$ (in Section 2.1), every $f_j$ obeys $\\\\|f\\_j\\\\|\\_2\\le \\mu_1$. Hence, there are basically no $f_j$ that can attain a detectable norm, and the support recovery problem is essentially trivial in this case.\n\n**Remark II.** To ensure our results (e.g., equations (8) and (9)) hold for any choice of smoothness sequence $\\\\{\\mu_k\\\\}\\_{k \\in \\mathbb N^+}$, the constants in our separation rates are not optimized for sharpness. In contrast, several variable selection studies derived asymptotically exact constants (Butucea et al.[5]) and showed the phase diagrams of signal strength for support recovery (Jin and Zheng[6]). We conjecture that, by employing more refined asymptotic techniques, our results can similarly attain constant-sharp minimax optimality.\n\n\n## 3. For the selector's truncation set $\\mathcal K_{rec}$ that adapts to unknown smoothness parameters, can bases other than 2 be chosen (e.g., base 3)? What is the essential impact of using base 2?\n\n**Reply:** Thank you for this question. Using base 2 is purely for notational convenience---actually any constant base $a>1$ (e.g., $3,4,\\cdots$) can be used as long as $\\log_a n \\asymp \\log_e n$. Essentially, the process of our adaptive method is to: **(i)** build a representative and geometric grid $\\mathcal K_{rec}$ of candidate truncation levels $K$, **(ii)** compute the selectors corresponding to each $K$, and **(iii)** take the maximum over them for each coordinate (see equation (12)). This procedure remains minimax rate-optimality provided the common ratio of the geometric grid is any absolute constant greater than 1.\n\n\n**Reference**\n\n[1] Yannick Baraud. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8(5): 577–606, 2002.\n\n[2] Birgé, Lucien, and Pascal Massart. Gaussian model selection. Journal of the European Mathematical Society 3(3): 203-268, 2001.\n\n[3] Xiaowu Dai, Xiang Lyu, and Lexin Li. Kernel knockoffs selection for nonparametric additive models. Journal of the American Statistical Association, 118(543):2158–2170, 2023.\n \n[4] Cristina Butucea, Enno Mammen, Mohamed Ndaoud, and Alexandre B. Tsybakov. Variable selection, monotone likelihood ratio and group sparsity. The Annals of Statistics, 51(1):312–333, 2023.\n\n[5] Cristina Butucea, Mohamed Ndaoud, Natalia A. Stepanova, and Alexandre B. Tsybakov. Variable selection with Hamming loss. The Annals of Statistics, 46(5):1837–1875, 2018.\n\n[6] Jin, Jiashun, and Zheng Tracy Ke. Rare and weak effects in large-scale inference: methods and phase diagrams. Statistica Sinica, 26(1):1-34, 2016."}, {"review_id": "bCWvyaYEKs", "reviewer": "Reviewer_FqYP", "summary": "The paper addresses the problem of variable selection in the nonparametric Gaussian white noise model, where the unknown signal is assumed to be a smooth multivariate function. This function is modeled as a sum of a small number of univariate components, each belonging to an ellipsoid defined via a quadratic constraint on its Fourier coefficients. The proposed selection procedure relies on (group) thresholding the Fourier coefficients of the noisy observed signal. The authors establish the minimax rates of separation for detecting the relevant variables. Additionally, they explore the case of unknown smoothness and propose an adaptive detection strategy.", "questions": "Can the proposed detection methods be easily adapted to deal with the case of unknown $n$ ?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The problem of variable selection is one of the central challenges in nonparametric statistics and learning theory.\n2. The approach based on establishing minimax rates of separation is a highly relevant and principled way of quantifying the difficulty of the task.\n3. The paper establishes matching upper and lower bounds, which significantly strengthens the theoretical contribution.\n4. The writing is clear and the paper is pleasant to read.\n\n**Weaknesses**\n\n1. While this paper would be a perfect fit for a statistics journal, I am concerned that only a small portion of the NeurIPS audience will find these results directly relevant.\n2. The noise level is assumed to be known and fixed at $1/\\sqrt{n}$. A more general and practically relevant setting would allow the noise level to be an unknown parameter $\\sigma$.\n\n**Minor Remarks**\n\n1. Some important references are missing:\n   - [Comminges and Dalalyan, AoS 2012] and [Min Xu, Minhua Chen, John Lafferty, AoS 2016] studied variable selection in the same problem under different conditions.\n   - [Dalalyan, Ingster, Tsybakov, PTRF 2014] and [Tyagi et al., AISTATS 2016] considered a closely related model where the components of the additive model are not necessarily univariate. These works derived minimax rates for estimation.\n\n2. In the main theorems, the phrasing ''for every $\\delta$'' should be revised. As currently written, it may suggest that the assumptions on $n$ and other parameters must hold uniformly for all $\\delta$. A clearer formulation would be to begin the theorem with: \"Let $\\delta$ be an arbitrary number in...\" and then state the result. This makes it explicit that $\\delta$ is fixed within the statement.", "was_revised": true, "final_justification": "I find the paper interesting and appreciate the authors’ responses to my remarks and questions.", "rebuttal": "We sincerely appreciate your recognition of the minimax optimal variable selection and your positive remarks on the clarity of our presentation.\nBelow, we will provide a response that centers around weaknesses, remarks, and questions related to our paper.\n\n# Weaknesses: \n\n## 1. While this paper would be a perfect fit for a statistics journal, I am concerned that only a small portion of the NeurIPS audience will find these results directly relevant.\n\n**Reply:** Thank you for this feedback. We think our work offers several insights of direct interest to the NeurIPS audience:\n\n**Information-theoretic limits.** We derive minimax lower bounds for support set recovery in SpAM, showing that no algorithm---including modern deep-learning methods---can reliably select variables once the true signal strengths are below the minimax separation rate (see Theorems 2,3, and 5). This key finding can guide ML researchers in understanding the necessity of the signal strength requirement.\n\n**Adaptation.** In Section 4, we propose a selector that is adaptive to the unknown smoothness parameter $\\alpha>0$ in Sobolev classes $\\mu_k = k^{-2\\alpha}$, and quantify the extra $\\log\\log n$ cost for adaptation. Our adaptive method and analytical framework can inspire principled hyperparameter tuning in some more complex models. \n\n**Trade-off between estimation and selection.** In Theorem 7, we prove that some estimators that are optimal for function estimation can be suboptimal for variable selection. This offers a negative but objective suggestion to ML researchers studying generalization, model selection, and interpretability: good prediction cannot always guarantee good variable selection.\n\nAdditionally, in Appendix A, we discuss the variable selection problem in SpAM under local differential privacy constraints, demonstrating the extensibility of our work. We hope these points highlight the relevance and potential impact of this paper for the broader NeurIPS audience.\n\n\n## 2. The noise level is assumed to be known and fixed at $\\sqrt{1/n}$. A more general and practically relevant setting would allow the noise level to be an unknown parameter $\\sigma$. **And also from Question Part:** Can the proposed detection methods be easily adapted to deal with the case of unknown $n$ ?\n\n**Reply:** We can replace $\\sqrt{1/n}$ with a general noise level $\\sigma$ to obtain more flexible statements and results. For instance, the selector (equation (10)) in Remark 3 then becomes\n$$\n\\hat \\eta_j^{rec} (X) = \\mathbf1 \\left( \\frac1{\\sigma^2} \\sum_{i=1}^{K'} X_{ij}^2 \\ge K'  + 2\\sqrt{K'\\log(2p/\\delta)} + 2 \\log(2p/\\delta) \\right)  , \\text{ for every } j \\in [p],\n$$\nwhere $K' := \\min \\left\\\\{k \\in \\mathbb N^+: \\mu_k \\le \\sigma^2 \\sqrt{k \\log p} \\right\\\\}$. Under this formulation, the minimax separation rate for support recovery (Theorem 3) becomes $ \\sigma^2 \\log p + \\max\\_{k \\in \\mathbb N^+} \\left\\\\{ \\left(\\sigma^2\\sqrt{k\\log p}\\right)\\wedge \\mu_k  \\right\\\\}$. In particular, for a Sobolev ellipsoid $\\mu_k\\asymp k^{-2\\alpha}$, it simplifies to $\\epsilon\\_{rec}^2 \\asymp \\sigma^2 \\log p + \\sigma^{\\frac{8\\alpha}{1+4\\alpha}} (\\log p)^{\\frac{2\\alpha}{1+4\\alpha}}$.\n\n**Adaptation to unknown $\\sigma$.** We now outline a simple approach to adapt to the unknown $\\sigma$. Denote $X_{1\\cdot}:=(X_{11},\\cdots, X_{1p}) \\in \\mathbb R^p$, and $ \\theta_{1\\cdot} := \\mathbf E (X_{1\\cdot}) = (\\theta_{11}, \\cdots, \\theta_{1p}) \\in \\mathbb R^p$. Under the SpAM setting, the vector $\\theta_{1\\cdot}$ is $s$-sparse. We then fit a Square-Root Lasso estimator (Belloni et al.[1])\n$$\n\\hat\\theta\\_{1\\cdot} = \\arg\\min\\_{\\gamma \\in \\mathbb R^p} \\left\\\\{ \\\\|X\\_{1\\cdot}- \\gamma \\\\|\\_2 + C\\sqrt{\\frac{\\log p}{p}} \\\\| \\gamma\\\\|\\_1 \\right\\\\} .\n$$\nWith a probability greater than $1-O(e^{-c s\\log p})$, one has $\\\\|\\hat\\theta\\_{1\\cdot} - \\theta\\_{1\\cdot} \\\\|\\_2^2 \\lesssim \\sigma^2 s\\log p$ and $\\\\|\\hat\\theta\\_{1\\cdot} - \\theta\\_{1\\cdot} \\\\|\\_1 \\lesssim \\sigma s \\sqrt{\\log p}$ (Derumigny[2]). We then construct an estimator of $\\sigma$ as $\\hat\\sigma = \\frac{\\\\|X\\_{1\\cdot}- \\hat\\theta\\_{1\\cdot}\\\\|\\_2}{\\sqrt{p}}$. Following the proof of Proposition 2 in Carpentier et al.[3], with a probability greater than $1-O(e^{-c s\\log p})$, one has $\\bigl|\\hat\\sigma^2/\\sigma^2 - 1\\bigr|\\lesssim\\sqrt{(s\\log p)/p} $. Hence, as long as $\\sigma^2\\log p\\lesssim\\mu_1$ and $K'\\lesssim \\max\\left( \\frac{p}{s},  \\sqrt{\\frac{p\\log p}{s}} \\right)$, we can replace $\\sigma$ by $\\hat\\sigma$ in our selector and retain the theoretical guarantees. \n\nWe will include the above analysis in the appendix. And we hope this addresses your concern about the noise level assumption.\n\n\n# Minor Remarks:\n\n## 1. Some important references are missing: [Comminges and Dalalyan, AoS 2012] and [Min Xu, Minhua Chen, John Lafferty, AoS 2016] studied variable selection in the same problem under different conditions. [Dalalyan, Ingster, Tsybakov, PTRF 2014] and [Tyagi et al., AISTATS 2016] considered a closely related model where the components of the additive model are not necessarily univariate. These works derived minimax rates for estimation.\n\n**Reply:** Thank you for highlighting these important works. We have now cited all four papers in Sections 1 and 2 of the revised manuscript. Dalalyan et al.[4] and Tyagi et al.[5] studied function estimation and variable selection in sparse additive models that permit low-dimensional interactions. Comminges and Dalalyan[6] and Xu et al.[7] analyzed support recovery in a $d$-dimensional nonparametric regression with an intrinsic $s$-variate underlying function. Additionally, the framework in Comminges and Dalalyan[6] can also be interpreted as an additive model allowing $s$-dimensional interaction (but there is only ONE $s$-variate support function). \n\n## 2. In the main theorems, the phrasing ''for every $\\delta$'' should be revised. As currently written, it may suggest that the assumptions on $n$ and other parameters must hold uniformly for all $\\delta$. A clearer formulation would be to begin the theorem with: \"Let $\\delta$ be an arbitrary number in...\" and then state the result. This makes it explicit that $\\delta$ is fixed within the statement.\n\n**Reply:** We appreciate your rigorous review. As you pointed out, we first fix a $\\delta \\in (0,1)$ before deriving the corresponding theoretical results. We have revised the manuscript to clarify this point.\n\n\n**Reference**\n\n[1] A. Belloni, V. Chernozhukov, L. Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):791–806, 2011.\n\n[2] Alexis Derumigny. Improved bounds for Square-Root Lasso and Square-Root Slope. Electronic Journal of Statistics, 12(1): 741-766, 2018.\n\n[3] Alexandra Carpentier, Olivier Collier, Laetitia Comminges, Alexandre B. Tsybakov, Yuhao Wang. Estimation of the $\\ell_2$-norm and testing in sparse linear regression with unknown variance. Bernoulli, 28(4):2744-2787, 2022.\n\n[4] Arnak Dalalyan, Yuri Ingster, and Alexandre B Tsybakov. Statistical inference in compound functional models. Probability Theory and Related Fields, 158(3):513–532, 2014.\n\n[5] Hemant Tyagi, Anastasios Kyrillidis, Bernd Gärtner, and Andreas Krause. Learning sparse additive models with interactions in high dimensions. volume 51 of Proceedings of Machine Learning Research, 111–120, 2016.\n\n[6] Laëtitia Comminges and Arnak S. Dalalyan. Tight conditions for consistency of variable selection in the context of high dimensionality. The Annals of Statistics, 40(5):2667 – 2696, 2012.\n\n[7] Min Xu, Minhua Chen, and John Lafferty. Faithful variable screening for high-dimensional convex regression. The Annals of Statistics, 44(6):2624 – 2660, 2016."}, {"review_id": "dpER4mCImv", "reviewer": "Reviewer_oppP", "summary": "The authors study variable selection in sparse additive models and establish minimax separation rates under both Hamming loss and a multiple testing loss (FDR + FNR). They obtain sharp results and show the problem is fundamentally different from the problem of estimating the model. Specializing to the case of $\\alpha$-smooth component functions, the authors also address adaptation to $\\alpha$ and demonstrate an unavoidable cost in the rate.", "questions": "- Can the authors address adaptation to sparsity? Currently, the variable selection procedure under the FDR + FNR loss requires choosing the truncation $K$ depending on $s$. The sparsity level $s$ may not typically be known. Can adaptation be done here? Is there some unavoidable cost that must also be paid?\n\n- Can the authors address adaptation more generally besides just Sobolev space? A major finding of the work by Kotekal and Gao cited in the paper was that, in the signal detection problem, there are different adaptation costs depending on the underlying function space. Some spaces impose an unavoidable cost, whereas others do not. Is there a similar phenomenon in the variable selection problem?\n\n- The selectors the authors study are essentially component-wise. Can the authors handle the more general setting where the component functions might live in different spaces? For example, $f_j \\in \\mathcal{H}_j$ where the $\\mathcal{H}_j$ might be different across $j$? This is the setting considered by Raskutti, Wainwright, and Yu.\n\n- Line 769: \"taht\" should be \"that\"", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths__\nSparse additive models are a popular and important topic in machine learning, so these results are quite welcome. The variable selection problem is quite important, and the authors obtain sharp theoretical results of a very fundamental nature. Furthermore, the setting is fairly general, allowing the component functions to live in a generic RKHS (not just e.g. Sobolev space).\n\n__Weaknesses__\nThere are no major weaknesses. One might nitpick and say the white noise model is too abstract, but the paper's focus is theoretical and there is a long tradition in the statistics literature of relying on asymptotic equivalence to focus on the essence.", "was_revised": true, "final_justification": "My questions have been addressed and I retain my score.", "rebuttal": "We sincerely appreciate your recognition of our results on minimax optimal variable selection and the general function space setting. Below, we will provide a response that centers around weaknesses and questions related to our paper.\n\n# Weaknesses: \n\n## 1. One might nitpick and say the white noise model is too abstract, but the paper's focus is theoretical and there is a long tradition in the statistics literature of relying on asymptotic equivalence to focus on the essence.\n\n**Reply:** Thank you for recognizing the theoretical focus of our work. We agree that the Gaussian white noise model provides an abstract but powerful framework to study the fundamental statistical limits of our problem. This approach aligns with our goal of delivering rigorous theoretical insights.\n\n# Questions:\n\n## 1. Can the authors address adaptation to sparsity? Currently, the variable selection procedure under the FDR + FNR loss requires choosing the truncation $K$ depending on $s$. The sparsity level $s$ may not typically be known. Can adaptation be done here? Is there some unavoidable cost that must also be paid?\n\n**Reply:** We demonstrate that Lepski's method can be used to adapt to the unknown sparsity level $s$: Suppose we know an upper bound $M\\ge s$ with $p/M\\ge C$ for some constant $C>1$. Define the dyadic grid $\\mathcal S := \\left\\\\{1,2,4, \\dots,2^{\\lfloor\\log_2M\\rfloor}\\right\\\\}$. For each $s\\_m \\in \\mathcal S$, define \n$$\n\\tilde \\eta^{s\\_m}\\_j := \\mathbf1 \\left(n \\sum\\_{i=1}^{K(s_m)} X\\_{ij}^2 \\ge K(s_m) + 2\\sqrt{K(s_m)\\cdot \\log \\left( \\frac{8p}{s_m\\delta} \\right)} + 2\\log\\left( \\frac{8p}{s_m\\delta} \\right) \\right),\n$$ \nwhere $K(s_m)=\\min\\left\\\\{k\\in\\mathbb N^+: \\mu_k^2\\le\\tfrac{k\\log(p/s_m)}{n^2}\\right\\\\}$. Then we consider the adaptive selector $\\tilde\\eta^{\\hat s} = \\left(\\tilde\\eta^{\\hat s}\\_1, \\cdots, \\tilde\\eta^{\\hat s}\\_p \\right) \\in \\{0,1\\}^p$, with \n$$\n\\hat s = \\min\\left\\\\{ s_m \\in \\mathcal S: \\sum\\_{j\\in [p]} |\\tilde \\eta_j^{s_m} - \\tilde \\eta_j^{s_\\ell}| \\le \\delta \\cdot s_\\ell, \\text{    for all } s_\\ell\\in \\mathcal S \\text{ and }s_\\ell \\ge s_m \\right\\\\}.\n$$\nBy following the proof procedure of Theorem 1 in our manuscript and Theorem 5.2 in Butucea et al.[1], as long as $c \\le (\\log s)/(\\log p)  \\le C$ for two constants $0<c<C<1$, this adaptive selector $\\tilde\\eta^{\\hat s}$ achieves the same minimax separation rate under FDR+FNR loss, with no additional cost for not knowing $s$ in advance.\n\nWe can also understand this conclusion from another perspective: when $0<c \\le (\\log s)/(\\log p) \\le C<1$, we have $\\log(p/s) \\asymp \\log p$. Hence, one may simply replace $\\log(p/s)$ with $\\log p$ in the selector $\\hat \\eta_j^{test}$ (in equation (6)) to adapt to the unknown $s$, while preserving the minimax rate-optimal signal strength requirement.\n\n\n## 2. Can the authors address adaptation more generally besides just Sobolev space? A major finding of the work by Kotekal and Gao cited in the paper was that, in the signal detection problem, there are different adaptation costs depending on the underlying function space. Some spaces impose an unavoidable cost, whereas others do not. Is there a similar phenomenon in the variable selection problem?\n\n**Reply:** Thank you for this question. There are two types of parameters that require adaptation, and we discuss each of them separately:\n\n**Adaptation to sparsity $s$.** As shown in our previous reply, whenever  $0<c \\le (\\log s)/(\\log p) \\le C<1$, by applying Lepski's method, we could provide a procedure adaptive to unknown $s$ without any additional rate cost, regardless of the underlying function space.\n\n**Adaptation to $\\\\{\\mu\\_k\\\\}\\_{k \\in \\mathbb N^+}$.**  In Section 4 we handle Sobolev ellipsoids ($\\mu_k=k^{-2\\alpha}$) with unknown smoothness parameter $\\alpha>0$, showing our adaptive truncation remains minimax rate-optimal and there is an unavoidable $\\log\\log n$ term as the cost for unknown $\\alpha$. Similarly, for the finite dimension or exponential decay ellipsoids, the adaptation cost (for the unknown smoothness parameter) should be worked out on a case-by-case basis. And we believe our adaptive selector from equation (12) provides a valuable blueprint for these specific settings.\n\nFinally, we provide a remark: the work by Kotekal and Gao[2] examined: **(i)** the adaptation cost for unknown sparsity $s$ in different underlying function spaces (their Section III), and **(ii)** the adaptation cost for unknown Sobolev smoothness $\\alpha$ (their Section IV). They did not address the general problem of adapting to an arbitrary sequence $\\\\{\\mu\\_k\\\\}\\_{k \\in \\mathbb N^+}$, underscoring that the adaptation to smoothness should be analyzed on a case-by-case basis. Moreover, because their focus is on testing $f\\equiv0$ while we address support set recovery of nonzero components $f_j$, the incurred adaptation costs are inherently different.\n\n\n## 3. The selectors the authors study are essentially component-wise. Can the authors handle the more general setting where the component functions might live in different spaces? For example, $f_j \\in \\mathcal H_j$  where the $\\mathcal H_j$ might be different across $j$? This is the setting considered by Raskutti, Wainwright, and Yu.\n\n**Reply:** Thank you for this insightful question. We can indeed extend our framework to heterogeneous settings where $f_j \\in \\mathcal H_j$ and $\\mathcal H_j$ might be different across $j \\in [p]$. Define the parameter space: \n$$\n\\mathcal F\\_s (r_1^2,\\cdots ,r_p^2) :=  \\left\\\\{ f = \\sum\\_{j \\in [p]} f\\_j :\\quad  \\sum\\_{j\\in [p]}\\mathbf 1(f\\_j \\ne 0) \\le s, \\quad f_j \\in \\mathcal H\\_j(r\\_j^2)\\cup\\\\{ \\mathbf 0\\\\} \\text{ for all } j\\in [p] \\right\\\\},\n$$\nwhere\n$$\n\\mathcal H_j(r_j^2) := \\left\\\\{ f_j=\\sum\\_{i=1}^\\infty \\theta_{ij} \\psi_i:\\quad  \\sum\\_{i =1}^\\infty \\frac{\\theta_{ij}^2}{\\mu_{ij}}\\le 1 ,\\quad   \\sum\\_{i =1}^\\infty \\theta_{ij}^2 \\ge r_j^2 \\right\\\\}.\n$$\nHeterogeneity across $\\mathcal H_j(r_j^2)$ is captured via distinct sequence $\\\\{\\mu\\_{ij} \\\\}\\_{i\\in\\mathbb N^+}$for every $j \\in [p]$.\n\n**Upper bound.** We apply a component‑wise selector\n$$\n\\hat \\eta_{j}^{heter} := \\mathbf1 \\left(n \\sum_{i=1}^{K_j} X_{ij}^2 \\ge K_j + 2\\sqrt{K_j \\log (2p/\\delta )} + 2\\log (2p/\\delta ) \\right),\n$$ \nwhere $K_j := \\min \\left\\\\{k \\in \\mathbb N^+: \\mu_{kj} \\le \\frac{\\sqrt{k \\log p}}{n} \\right\\\\}$.\nIf the condition $r_j^2 \\ge C_\\delta \\left[ \\frac{\\log p }{n} + \\max\\_{k \\in \\mathbb N^+} \\left(\\frac{\\sqrt{k\\log p}}{n} \\wedge \\mu_{kj}  \\right) \\right]$ holds for every $j \\in [p]$, we have the exact support recovery guarantee\n$$\n\\inf\\_{f\\in \\mathcal F_{s}(r_1^2,\\cdots ,r_p^2)} \\mathbf P_f \\left(\\hat S(X) = S(f) \\right) \\ge 1-\\delta.\n$$\nThe proof proceeds analogously to that given in Appendix C.2.\n\n**Lower bound.** If there exists some $j\\in[p]$ with $r_j^2 \\le c \\left[ \\frac{\\log p }{n} + \\max\\_{k \\in \\mathbb N^+} \\left(\\frac{\\sqrt{k\\log p}}{n} \\wedge \\mu_{kj}  \\right) \\right]$ for a sufficiently small constant $c$, then no selector can achieve consistent support recovery. This lower bound proof follows Theorem 5's framework, but requires a finer control of chi-square divergences due to component-dependent truncation levels and signal strengths settings.\n\n\n## 4. Line 769: \"taht\" should be \"that\".\n\n**Reply:** Thank you for identifying the typo, and we have corrected it accordingly.\n\n\n**Reference**\n\n[1] Cristina Butucea, Mohamed Ndaoud, Natalia A. Stepanova, and Alexandre B. Tsybakov. Variable selection with Hamming loss. The Annals of Statistics, 46(5):1837-1875, 2018.\n\n[2] Subhodh Kotekal and Chao Gao. Minimax signal detection in sparse additive models. IEEE Transactions on Information Theory, 70(12):8892–8928, 2024."}]

Author rebuttal:

Meta-review: Consider the problem of univariate function selection in a continuous-time sparse additive model with white Gaussian noise. This paper characterizes the minimax risk for both multiple testing and support recovery. The case of support recovery under unknown smoothness is also studied. Finally, the paper presents an example where optimal estimation does not lead to optimal support recovery, demonstrating that the two tasks are fundamentally different.

The paper is well written. The problem studied is fundamental, and the minimax risk results are clean. The reviewers, several of whom are experts in related research topics, are all positive toward this paper, and the authors satisfactorily addressed the questions raised. Reviewer BfNF believes the technical novelty of this paper is limited; nevertheless, I think such a fundamental and novel result already deserves publication.

Given the above, I suggest accepting this paper as a spotlight.
Decision: Accept (spotlight)