Optimal minimization of an unknown function in a nonparametric multivariate regression model thanks to a dimension reduction approach

C\'edric Adam (ANDRA; C\'eline L\'evy-Leduc (LPSM (UMR\_8001)); Ilaria Giulini (LPSM (UMR\_8001)); LPSM (UMR\_8001))

REVIEW 3 major objections 5 minor 27 references

Optimal minimization of an unknown function in a nonparametric multivariate regression model thanks to a dimension reduction approach

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that Lasso-based variable selection plus projected gradient descent on the estimated subspace estimates the minimum and minimizer of a smooth noisy function at the same nonparametric rates as if the active variables were…

desk verdict A real two-step combination with clean rates for the unknown-active-set problem, but the 'optimal' claim and the (A6) identifiability condition need referee scrutiny before the paper's scope is accepted as stated. read the letter →

arxiv 2608.04566 v1 pith:KCBLAZ5I submitted 2026-08-05 math.ST stat.TH

Cédric Adam (ANDRA , LPSM (UMR_8001)) , Ilaria Giulini (LPSM (UMR_8001)) , Céline Lévy-Leduc (LPSM (UMR_8001)) This is my paper · ORCID

classification math.STstat.TH MSC 62G0862G20

keywords multivariateregressionvariableselectiondimensionreductionfunctionminimizationlocalpolynomialestimationprojectedgradientdescentHöldersmoothnessLambert

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies passive-design nonparametric regression where the unknown regression function depends on $d$ coordinates but only on $r < d$ unknown 'active' coordinates. It proposes a two-step estimator: first locate the active coordinates with a Lasso on local polynomial coefficients at a reference point; then run projected gradient descent on the estimated active subspace using local polynomial estimates of the gradient, and finally evaluate the local-polynomial estimator at the resulting point. The central claim is that the expected squared error of the minimizer estimate and the absolute error of the minimum estimate match, up to a factor smaller than a power of a logarithm, the minimax rates one would get if the active set were known: $(W(n)/n)^{2(\beta-1)/(2\beta+r)}$ and $(W(n)/n)^{\beta/(2\beta+r)}$. A sympathetic reader should care because the method achieves dimension reduction automatically, without being told which coordinates matter.

What carries the argument

The method is carried by two objects. First, the selection step solves a Lasso on the coefficients of a degree-one local polynomial at a fixed reference point $x_0$ with a uniform kernel; the nonzero coefficient of $\partial_j f(x_0)$ flags variable $j$, and Lemma 5.1 (drawn from the paper's cited selection theorem) bounds the mis-selection probability. Second, minimization uses projected gradient descent with step size $\eta_k = 1/k$ on the estimated subspace, where the gradient is replaced by a local polynomial regression estimator; the bandwidth and regularization are chosen as $h_n = (W(n)/n)^{1/(2\beta+r)}$ and $\lambda_n = (W(n)/n)^{\beta/(2\beta+r)}$. The Lambert-function inequalities of Lemma 5.4 convert the usual $\log n$ factors into $W(n)$, tightening the bounds below any power of a logarithm while remaining within a logarithmic order.

What would settle it

Simulate the model with $d=2$, $r=2$, $f(x) = (x_1 - a)^2 + \epsilon (x_2 - b)^2$, with $\epsilon$ chosen so that $|\partial_2 f(x_0)|$ is below the threshold $C$ at the chosen reference point, and compute the empirical risk of the two-step estimator over many replications. If the risk does not decay at the claimed rate once $\hat J$ starts omitting variable 2, the theorem's validity is exactly limited to the range where (A6)(1) holds.

Watch

Extended reading notes

Core claim

The paper's central claim is that unknown active variables can be identified and the function minimized at the same statistical rate as if those variables were known beforehand. Concretely, the set estimator $\hat J$ from the Lasso step satisfies $\mathbb{P}(\hat J \neq J) \le c_0 \exp(c_0 d) \exp(-c_1 n h^{d+2})$, so with overwhelming probability the optimization runs on the correct subspace. On that event, projected gradient descent with local polynomial gradient estimates yields $E\|W(x^*-\hat x)\|^2 \le B (W(n)/n)^{2(\beta-1)/(2\beta+r)}$ and $E|f(x^*)-\hat f^*| \le B' (W(n)/n)^{\beta/(2\beta+r)}$, matching the known-active-variable minimax rates up to the Lambert factor $W(n)$, which is smaller than $\log n$ at the first order. The paper states this as an improvement over the case where the active variables are unknown.

Load-bearing premise

The load-bearing premise is Assumption (A6)(1): at the reference point $x_0$, every active variable must satisfy $|\partial_j f(x_0)| \ge C$ with $C \ge 1512\,(p_M/p_m)\,L\sqrt{r}$, and there is no data-dependent way to verify it. If a truly active variable has a smaller or vanishing first derivative at $x_0$, the Lasso step can omit it, and the minimization is performed on a wrong subspace, so the claimed rates no longer apply.

Editorial extensions

If this is right

The minimizer estimator reaches the rate $(W(n)/n)^{2(\beta-1)/(2\beta+r)}$ regardless of the ambient dimension $d$, so the curse of dimensionality is confined to the exponentially small probability of selecting the wrong active set.
The minimum estimator reaches $(W(n)/n)^{\beta/(2\beta+r)}$, the same rate as if the active set were known.
The required number of gradient iterations $N$ only needs to exceed $N_{n,\beta}$ times a constant depending on $|\Theta|^2$ and the strong-convexity ratio, so the computational cost grows only polynomially in $n$.
If the Hölder exponent $\beta$ is unknown, taking $\beta=2$ in the bandwidth choice yields a valid procedure with rates in powers of $(W(n)/n)$, per Remark 1 of the paper.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper's own claims, the distinguishability condition means the method selects variables from first-order behavior at a single reference point; a natural testable extension is to use a degree-two local polynomial in the selection step to catch variables that enter only through second-order terms.
Because the mis-selection probability contains $\exp(c_0 d)$, the method is best suited to moderate ambient dimension; for very high-dimensional problems, the same two-step logic would need an additional screening or sparsity assumption to control the $d$-dependence.
The risk bound in Theorem 3.2 holds explicitly for every number of iterations $N$, which suggests one could tune $N$ by monitoring the estimated gradient rather than using the theoretical $N_{n,\beta}$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the paper does something real. It combines Bertin-Lecué's Lasso-based variable selection with Akhavan et al.'s projected gradient descent and proves risk bounds for the unknown-active-set problem. The rates match the known-active-variable minimax rates up to a Lambert-function factor, which is a genuine extension. The main proofs are coherent; I checked the structure of Theorems 3.1–3.3 and the lemmas they rest on, and the bounds do follow from the stated assumptions. The Lambert refinement over the usual log factor is a nice touch. Credit where due: the variable-selection probability bound is imported correctly, and the decomposition in the proof of Theorem 3.1 is clean.

The soft spots are two. First, the "optimal" claim is not fully supported. The paper compares its upper bounds to lower bounds for the known-active-variable problem. That gives the right rate for the wider class, but the class actually restricted by (A6) — active partial derivatives at x0 bounded away from zero by C ≥ 1512 (p_M/p_m) L sqrt(r) — is smaller. No lower bound is proved for that restricted class, so "optimal" is an overreach, though a modest one; the rates are likely right, but that requires proof.

Second, (A6)(1) is load-bearing and not cosmetic. The stress-test example lands: f(x1,x2)=2x1^2+2(x2-1)^2+x1x2 at x0=(0,0) satisfies (A1)–(A5) after scaling, but the partial derivative in x1 vanishes at x0. Then the Lasso step in (8)–(10) cannot distinguish that variable from an inactive one, \hat J misses it, and the minimization runs in the wrong subspace, giving a constant positive error. Strong convexity plus Hölder smoothness does not rule this out, and the paper gives no way to check (A6) from data. That is not fatal — the assumption is explicit — but it narrows the scope considerably, and the authors should present it that way.

Third, several appendix lemmas are sketches referring to Akhavan et al. Full independent verification requires that paper at hand. Acceptable for a research article, but the authors should mark clearly which proofs are new and which are adaptations.

Bottom line: a solid, useful paper for people working on sparse nonparametric estimation and black-box optimization in passive designs. It deserves a serious referee. I would send it to review and ask for a revision that either relaxes (A6), proves a lower bound for the restricted class, or at least removes the unqualified "optimal" and adds an identifiability discussion. The math on its own terms is coherent.

Referee Report

3 major / 5 minor

Summary. The paper studies estimation of the minimizer and minimum value of a regression function f on a compact convex set Θ, in a passive-design nonparametric model where f depends on an unknown subset J of r active variables among d. The proposed method first estimates J by a Lasso-type local polynomial fit at a reference point x0 (Section 2.1), then runs a projected gradient descent on the estimated active subspace using local polynomial gradient estimates (Section 2.2). The main results, Theorems 3.1 and 3.3, give non-asymptotic upper bounds of order (W(n)/n)^{2(β-1)/(2β+r)} for the squared error of the estimated minimizer and (W(n)/n)^{β/(2β+r)} for the absolute error of the estimated minimum, where W is the Lambert function. The proofs combine a variable-selection lemma from Bertin and Lecué (2008) with gradient/minimum estimation lemmas adapted from Akhavan et al. (2024).

Significance. If the results are correct, the paper makes a valuable contribution: it shows that in a passive design one can identify the active variables and optimize the function at rates that, up to a Lambert-function factor, match the minimax rates for the problem where the active subspace is known. The explicit choice of bandwidth and regularization in (26) and the detailed proofs of the main theorems are strengths, as is the use of the Lambert function to sharpen the logarithmic factor in prior bounds. However, the main optimality claim is not fully supported because the class of functions considered is restricted by a strong, unverifiable distinguishability condition, and the lower bounds cited do not cover that restricted class.

major comments (3)

[Assumption (A6)(1), Section 2.1; Lemma 5.1]
[Section 3, optimality claims after Theorems 3.1 and 3.3]
[Section 6, Lemmas 6.1-6.4, 6.5-6.6, 6.10-6.11]

minor comments (5)

[Section 2.1, text after (11)]
[Lemmas 6.3 and 6.4]
[Assumption (A6)(2) and Lemma 5.1]
[Equation (11) and Lemma 5.1]
[Theorem 3.1, condition on N]

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the rates follow from external theorems (Bertin–Lecué; Akhavan et al.) and explicit parameter choices; no fitted quantity is renamed as a prediction.

full rationale

The derivation chain is self-contained in the relevant sense. Variable selection is an application of Theorem 1 of Bertin and Lecué (2008), restated as Lemma 5.1; this is an external theorem with stated assumptions, not a result of the present authors. The optimization risk bounds are proved via Theorem 3.2, whose proof uses Lemmas 6.1–6.4 adapted from Akhavan et al. (2024) with explicit bandwidth and regularization choices in (26); no parameter is fitted to the data and then presented as a prediction. The identifiability condition (A6)(1) is a genuine assumption on the function, not a disguised consequence of the estimators, and its strength is a correctness/robustness concern rather than circularity. The optimality comparisons rely on external minimax rates for the known-active-variable problem, so the claimed rates are benchmarked against independent lower bounds rather than being obtained from the paper's own equations. The authors' own Lemmas 5.2–5.5 are analytic facts about Hölder composition and the Lambert function, and are not restatements of the main theorems. No self-citation chain is load-bearing, and no fitted input is renamed as a prediction. Therefore no circular step is exhibited.

Assumptions & free parameters 3 free parameters · 8 assumptions · 0 invented entities

The central claims rest on a standard nonparametric regression model plus smoothness, strong convexity, density, noise, and the coordinate-sparse active-variable structure. The most fragile input is (A6), the lower bound on active partial derivatives at the reference point, which is needed for the Lasso to recover J and is not implied by the other assumptions. The paper also imports two external toolboxes: the variable-selection theorem of Bertin and Lecue and the local polynomial risk lemmas of Akhavan et al. No new physical or model entities are introduced.

free parameters (3)

Variable selection bandwidth h = unspecified small positive constant
Used in the Lasso criterion (8). It is only constrained by h < min(pm/(32(d+1)M_K Ltilde), eta) and by (A6)(2); the recovery probability decays as exp(-c1 n h^{d+2}), so h controls the n threshold. No data-driven choice is given.
Variable selection regularization lambda = 8 sqrt(3 M_K p_M L) h
Lambda is fixed by Lemma 5.1 once h and the constants are known. It is a theoretically chosen tuning parameter, not estimated from data.
Minimization bandwidth h_n and regularization lambda_n = (W(n)/n)^{1/(2 beta + r)} and (W(n)/n)^{beta/(2 beta + r)}
Explicit formulas in (26), not fitted to data; included for completeness because they are tuning choices required by the algorithm.

assumptions (8)

domain assumption The regression function has the coordinate-sparse structure f(x) = g(W x), with W an r x d matrix containing exactly one 1 per row (Equations (4)-(5)).
The method identifies active coordinates but cannot handle general linear dimension reduction subspaces. If f depends on a linear combination of inputs, the set J may be overestimated and the rate in r is not the true intrinsic dimension.
domain assumption Kernel K is Lipschitz, compactly supported in the unit ball, nonnegative, integrates to 1, and is bounded (A1).
Used in both the local polynomial estimator and the variable-selection criterion; standard for local smoothing.
domain assumption f is in the Holder class F_beta(L), beta >= 2, Hessian bounded on Theta, g is alpha-strongly convex on W Theta with alpha > 1, and f is bounded on Theta' (A3).
These conditions drive both the bias of the local polynomial gradient and the contraction of the projected gradient descent.
domain assumption Noise xi_i are centered, independent of the design, sub-Gaussian with E exp(|xi_i|/sigma) < infinity; the variable-selection theorem additionally requires Gaussian noise (A4).
Sub-Gaussianity is used in Bernstein-type concentration; Gaussianity enters only through Lemma 5.1.
domain assumption Design density p is Lipschitz near x0 and bounded below and above on relevant sets (A5).
Guarantees the projected density of z_i = W x_i is bounded below and that local polynomial estimators are well behaved.
domain assumption Distinguishability: |partial_j f(x0)| >= C for j in J and |f(x0)| > C h (A6).
This is the most fragile premise: active variables must have nonzero partial derivatives at the reference point, otherwise the Lasso step can set them to zero.
standard math Theorem 1 of Bertin and Lecue (2008) gives the active-set recovery probability bound in Lemma 5.1.
The paper cites rather than reproves this theorem; it is the source of the P(hat J = J) control.
standard math The local polynomial gradient and value estimation lemmas in Section 6, adapted from Akhavan et al. (2024), are valid.
Some appendix proofs are sketches referring to Akhavan et al.; the current paper does not fully re-derive all of them.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal minimization of an unknown function in a nonparametric multivariate regression model thanks to a dimension reduction approach." pith.science (2026). https://pith.science/paper/KCBLAZ5I

@misc{pith2026260804566,
  author       = {Pith},
  title        = {Pith review of: Optimal minimization of an unknown function in a nonparametric multivariate regression model thanks to a dimension reduction approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KCBLAZ5I}},
  note         = {Machine review of arXiv:2608.04566}
}

read the original abstract

In this paper, we propose a novel approach for estimating the minimum of a smooth function and its location from observations corresponding to a multivariate regression function depending a priori on d variables but actually only on r < d active variables and corrupted by some additional noise. Our method consists of two steps: The rst one is a variable selection approach which is used for identifying the r active variables on which f depends and the second one consists in estimating the minimum of the function and its location. The estimation of the minimizers is obtained by using a projected gradient descent where the gradient is estimated using a local polynomial approximation of the regression function limited to its active variables obtained in the rst step. The estimation of the minimum is obtained by evaluating the estimator of the regression function using a local polynomial approach at the estimator of one of the minimizers previously obtained. We establish non asymptotic upper bounds for the quadratic risk of the estimators of the minimizers and of the minimum and prove that they reach the optimal rate that could be expected as if the active variables were known beforehand up to a factor smaller than a power of a logarithmic term.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 23 canonical work pages

[1]

Gogolashvili, and A

Akhavan, A., D. Gogolashvili, and A. B. Tsybakov (2024). Estimating the minimizer and the minimum value of a regression function under passive design. J. Mach. Learn. Res.\/ 25\/ (1), 580--616

work page 2024
[2]

Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits

Akhavan, A., M. Pontil, and A. B. Tsybakov (2022). Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Technical report, Istituto Italiano di Tecnologia. Arxiv 2006.07862

work page Pith review arXiv 2022
[3]

Ghosal, and H

Belitser, E., S. Ghosal, and H. van Zanten (2012). Optimal two-stage procedures for estimating location and size of the maximum of a multivariate regression function . The Annals of Statistics\/ 40\/ (6), 2850 -- 2876

work page 2012
[4]

Bertin, K. and G. Lecu \'e (2008). Selection of variables and dimension reduction in high-dimensional non-parametric regression . Electronic Journal of Statistics\/ 2 , 1224 -- 1241

work page 2008
[5]

Blum, J. R. (1954). Multidimensional Stochastic Approximation Methods . The Annals of Mathematical Statistics\/ 25\/ (4), 737 -- 744

work page 1954
[6]

Breiman, L. (2001). Random forests. Machine learning\/ 45 , 5--32

2001
[7]

Cauchy, A. (1847). M\'ethode g\'en\'erale pour la r\'esolution des syst \`e mes d'\'equations simultan\'ees. Comp. Rend. Sci. Paris\/ 25 , 536--538

work page
[8]

Dupac, V. (1957). On the Kiefer - Wolfowitz approximation method. C as. P e stov \'a n \' Mat.\/ 82 , 47--75

work page 1957

Show all 27 references

[9]

Fabian, V. (1967). Stochastic Approximation of Minima with Improved Asymptotic Speed . The Annals of Mathematical Statistics\/ 38\/ (1), 191 -- 200

1967
[10]

Feng, J. and N. Simon (2017). Sparse-input neural networks for high-dimensional nonparametric regression and classification. arXiv preprint arXiv:1711.07592

2017 arXiv
[11]

Friedman, J. H. (1991). Multivariate adaptive regression splines. The Annals of Statistics\/ 19\/ (1), 1--67

1991
[12]

H \"a rdle, W. and R. Nixdorf (1987). Nonparametric sequential estimation of zeros and extrema of regression functions. IEEE Transactions on Information Theory\/ 33\/ (3), 367--372

1987
[13]

Zhang, S

He, K., X. Zhang, S. Ren, and J. Sun (2016, June). Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)

2016
[14]

Ibragimov, I. A. and R. Z. Khas'minskii (1982). Estimation of the maximum value of a signal in gaussian white noise. Mathematical Notes of the Academy of Sciences of the USSR\/ 32\/ (4), 746--750

1982
[15]

Kiefer, J. and J. Wolfowitz (1952). Stochastic Estimation of the Maximum of a Regression Function . The Annals of Mathematical Statistics\/ 23\/ (3), 462 -- 466

1952
[16]

Lemhadri, I., F. Ruan, L. Abraham, and R. Tibshirani (2021). Lassonet: A neural network with feature sparsity. The Journal of Machine Learning Research\/ 22\/ (1), 5633--5661

2021
[17]

Lepskii, O. V. (1994). Estimation of the maximum of a nonparametric signal to within a constant. Theory of Probability & Its Applications\/ 38\/ (1), 152--158

1994
[18]

Chen, and W

Li, Y., C.-Y. Chen, and W. W. Wasserman (2016). Deep feature selection: theory and application to identify enhancers and promoters. Journal of Computational Biology\/ 23\/ (5), 322--336

2016
[19]

Lin, Y. and H. H. Zhang (2006). Component selection and smoothing in multivariate nonparametric regression. The Annals of Statistics\/ 34\/ (5), 2272--2297

2006
[20]

Mokkadem, A. and M. Pelletier (2007). A companion for the Kiefer–Wolfowitz–Blum stochastic approximation algorithm . The Annals of Statistics\/ 35\/ (4), 1749 -- 1772

2007
[21]

Polyak, B. and A. Tsybakov (1990). Optimal order of accuracy for search algorithms in stochastic optimization. Problems of Information Transmission\/ 26\/ (2), 45--53

1990
[22]

Robbins, H. and S. Monro (1951). A Stochastic Approximation Method . The Annals of Mathematical Statistics\/ 22\/ (3), 400 -- 407

1951
[23]

Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological)\/ 58\/ (1), 267--288

1996
[24]

Tsybakov, A. B. (1990). Locally-polynomial algorithms of passive stochastic approximation. Problems of Control and Information Theory\/ 19\/ (3), 181--195

1990
[25]

Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press

2018
[26]

Jitkrittum, L

Yamada, M., W. Jitkrittum, L. Sigal, E. P. Xing, and M. Sugiyama (2014, 01). High-dimensional feature selection by feature-wise kernelized lasso. Neural Computation\/ 26\/ (1), 185--207

2014
[27]

Zou, H. and T. Hastie (2005). Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society. Series B (Statistical Methodology)\/ 67\/ (2), 301--320

2005

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Gogolashvili, and A

Akhavan, A., D. Gogolashvili, and A. B. Tsybakov (2024). Estimating the minimizer and the minimum value of a regression function under passive design. J. Mach. Learn. Res.\/ 25\/ (1), 580--616

work page 2024

[2] [2]

Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits

Akhavan, A., M. Pontil, and A. B. Tsybakov (2022). Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Technical report, Istituto Italiano di Tecnologia. Arxiv 2006.07862

work page Pith review arXiv 2022

[3] [3]

Ghosal, and H

Belitser, E., S. Ghosal, and H. van Zanten (2012). Optimal two-stage procedures for estimating location and size of the maximum of a multivariate regression function . The Annals of Statistics\/ 40\/ (6), 2850 -- 2876

work page 2012

[4] [4]

Bertin, K. and G. Lecu \'e (2008). Selection of variables and dimension reduction in high-dimensional non-parametric regression . Electronic Journal of Statistics\/ 2 , 1224 -- 1241

work page 2008

[5] [5]

Blum, J. R. (1954). Multidimensional Stochastic Approximation Methods . The Annals of Mathematical Statistics\/ 25\/ (4), 737 -- 744

work page 1954

[6] [6]

Breiman, L. (2001). Random forests. Machine learning\/ 45 , 5--32

2001

[7] [7]

Cauchy, A. (1847). M\'ethode g\'en\'erale pour la r\'esolution des syst \`e mes d'\'equations simultan\'ees. Comp. Rend. Sci. Paris\/ 25 , 536--538

work page

[8] [8]

Dupac, V. (1957). On the Kiefer - Wolfowitz approximation method. C as. P e stov \'a n \' Mat.\/ 82 , 47--75

work page 1957