Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
Abstract
Variational regularization techniques are dominant in the field of mathematical imaging. The expressiveness of these methods heavily depends on the adopted regularization formulation which usually involves a number of parameters which have to be fine-tuned by the user. To circumvent the heavy computational costs associated with this parameter tuning, data-driven learning strategies have turned out to be a useful strategy. Selecting parameters by learning from data gives rise to a hierarchical (bilevel) optimization problem, which is in general computationally hard to solve. Our aim in this paper is to develop a data-efficient solution strategy for the bilevel learning problem. To that end, we propose a multilevel Monte Carlo derivative-free optimization method that couples Gaussian smoothing of the upper-level objective (parameter selection) with a hierarchy of lower-level (variational regularization) solution accuracies. Being agnostic towards the specific way the lower-level problem is solved, we derive explicit oracle complexity and computational cost statements for approximately solving the entire bilevel learning problem. Our statements are parameterized by the employed lower-level solution method, thus allowing for a direct cost accounting from the variational reconstruction method to the parameter selection problem. This enables us to give a universal end-to-end complexity analysis of bilevel learning, valid for the most important optimization routines in inverse problems, rather than for a specific choice of methods.
Related
- Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Stochastic Lie-Bracket Approximations for Zeroth-Order Optimization on Manifolds
- Training with ML-labeled Data via Stochastic First- and Zeroth-Order Optimization
- Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
BibTeX
@misc{chada2026multilevel,
title = {{Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves}},
author = {Neil K. Chada and Mohammad S. Salehi and Mathias Staudigl and Simon Weissmann},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15047},
eprint = {2610.15047},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15047},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
AU - Neil K. Chada
AU - Mohammad S. Salehi
AU - Mathias Staudigl
AU - Simon Weissmann
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.15047
UR - https://arxiv.org/abs/2610.15047
AB - Variational regularization techniques are dominant in the field of mathematical imaging. The expressiveness of these methods heavily depends on the adopted regularization formulation which usually involves a number of parameters which have to be fine-tuned by the user. To circumvent the heavy computational costs associated with this parameter tuning, data-driven learning strategies have turned out to be a useful strategy. Selecting parameters by learning from data gives rise to a hierarchical (bilevel) optimization problem, which is in general computationally hard to solve. Our aim in this paper is to develop a data-efficient solution strategy for the bilevel learning problem. To that end, we propose a multilevel Monte Carlo derivative-free optimization method that couples Gaussian smoothing of the upper-level objective (parameter selection) with a hierarchy of lower-level (variational regularization) solution accuracies. Being agnostic towards the specific way the lower-level problem is solved, we derive explicit oracle complexity and computational cost statements for approximately solving the entire bilevel learning problem. Our statements are parameterized by the employed lower-level solution method, thus allowing for a direct cost accounting from the variational reconstruction method to the parameter selection problem. This enables us to give a universal end-to-end complexity analysis of bilevel learning, valid for the most important optimization routines in inverse problems, rather than for a specific choice of methods.
ER -