Parametric Rates for Nonparametric Conditional-Moment Bilevel Optimization

Abstract

We study functional bilevel optimization with conditional moments, where plug-in hypergradients can inherit first-order errors from nonparametrically learned conditional expectations. We introduce OBiGrad, an orthogonalized hypergradient estimator whose bias is a product of nuisance errors. Under our regression and complexity conditions, projected gradient descent with the direct plug-in hypergradient yields expected stationarity error O(T^−1/2+n^−1/2+n^−ν/b) for the best iterate, whereas OBiGrad achieves O(T^−1/2+n^−1/2+n^−2ν/b), where b=ν(2+p)+γ combines the approximation and complexity exponents. Consequently, when ν(2−p)≥γ, OBiGrad attains the parametric statistical rate O(T^−1/2+n^−1/2), improving the sufficient sample-size bound relative to the direct plug-in bound for a fixed iteration budget. We illustrate these gains on instrumental-variable and fitted-Q-regression problems, examining stationary-point estimation, returned population stationarity, and regularization sensitivity.

Recursive moment updates for scalable Bayesian nonparametric regression
Peter Liu, Andrew Yiu, Edwin Fong
arXiv24 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
Víctor Bucarey López, Sophia Calderón, Gonzalo Muñoz +1
Computational Optimization and Applications7 Aug 2026Peer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
Daniel Cortild, Mathias Staudigl, Juan Peypouquet +1
arXiv6 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
A Theoretical Analysis of a Bilevel Optimization Formulation for Combined Local-Global Optical Flow Models
El Mostafa Kalmoun
arXiv5 Nov 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
An Ω(κ_y⁸ε⁻⁶) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
Zhihao Gu, Qilong Wu, Junchi Yang
arXiv18 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{khoury2026parametric,
  title = {{Parametric Rates for Nonparametric Conditional-Moment Bilevel Optimization}},
  author = {Fares El Khoury and Houssam Zenati and Nathan Kallus and Michael Arbel and Aurélien Bibaut},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2605.21341},
  eprint = {2605.21341},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.21341},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Parametric Rates for Nonparametric Conditional-Moment Bilevel Optimization
AU  - Fares El Khoury
AU  - Houssam Zenati
AU  - Nathan Kallus
AU  - Michael Arbel
AU  - Aurélien Bibaut
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2605.21341
UR  - https://arxiv.org/abs/2605.21341
AB  - We study functional bilevel optimization with conditional moments, where plug-in hypergradients can inherit first-order errors from nonparametrically learned conditional expectations. We introduce OBiGrad, an orthogonalized hypergradient estimator whose bias is a product of nuisance errors. Under our regression and complexity conditions, projected gradient descent with the direct plug-in hypergradient yields expected stationarity error O(T^−1/2+n^−1/2+n^−ν/b) for the best iterate, whereas OBiGrad achieves O(T^−1/2+n^−1/2+n^−2ν/b), where b=ν(2+p)+γ combines the approximation and complexity exponents. Consequently, when ν(2−p)≥γ, OBiGrad attains the parametric statistical rate O(T^−1/2+n^−1/2), improving the sufficient sample-size bound relative to the direct plug-in bound for a fixed iteration budget. We illustrate these gains on instrumental-variable and fitted-Q-regression problems, examining stationary-point estimation, returned population stationarity, and regularization sensitivity.
ER  -

Abstract

Related

Cite