Derivative-free stochastic bilevel optimization for inverse problems

Mathias Staudigl, Simon Weißmann, Tristan van Leeuwen

TL;DR

This paper introduces a derivative-free stochastic approach to solve complex bilevel optimization problems in the context of inverse problems, such as medical imaging and signal processing. By using a zeroth-order gradient estimator based on Gaussian smoothing, the authors provide a way to automatically learn optimal regularization parameters and experimental designs without needing to calculate explicit gradients of the "hyperobjective."

What Problem Does This Paper Address?

Inverse problems involve reconstructing a hidden signal or image from noisy, indirect measurements. To get good results, researchers use "regularization"—mathematical constraints that prevent the solution from becoming too noisy. However, choosing the right regularization parameters (like the weight of a penalty term) is traditionally a manual, "trial-and-error" process.

Bilevel optimization offers a way to automate this: the "lower level" solves the reconstruction problem, while the "upper level" finds the parameters that minimize the error over a training dataset. The catch? The relationship between the parameters and the final image is often non-smooth and non-convex. Standard gradient-based methods (which require "differentiating through" the lower-level solver) are mathematically daunting and computationally fragile. This paper tackles the challenge of optimizing these parameters when you can only observe the final error (function values) but cannot easily compute its gradient.

Methods

The authors propose a Derivative-free Randomized Proximal Gradient Method. Key components include:

  • Bilevel Framework: They model the task as a stochastic bilevel problem where the lower level is a variational reconstruction (like Total Variation denoising) and the upper level is the learning task.
  • Gaussian Smoothing: To handle the non-smoothness of the hyperobjective, they apply Gaussian smoothing. This transforms the jagged objective function into a differentiable one by convolving it with a Gaussian kernel.
  • Zeroth-Order Gradient Estimation: Instead of calculating a true gradient, the algorithm estimates it by sampling function values at random directions (finite differences). This makes the method "black-box" compatible with various lower-level solvers.
  • Inexactness Handling: Crucially, the theory accounts for the fact that lower-level problems are rarely solved perfectly. They prove that the algorithm still converges even when the reconstruction is only an approximation.
  • Complexity Analysis: The paper provides a rigorous proof of iteration complexity, showing that the number of calls to the stochastic oracle scales as $O(\epsilon^{-3})$ to reach a stationary point.

Datasets

The method was evaluated on two primary synthetic benchmarks:

  1. 1D Signal Denoising: Reconstructing piece-wise constant signals corrupted by Gaussian white noise. The goal was to learn the optimal Tikhonov and Total Variation (TV) regularization weights.
  2. 2D Image Reconstruction (Radon Transform): A dataset of randomly generated triangles of varying sizes, rotations, and gray levels. This was used for Optimal Experimental Design (OED), where the algorithm had to learn which measurement angles (out of 64 possible) provide the best reconstruction quality.

Key Insights and Ideas

  • The "Hypergradient" is Optional: You don't actually need to differentiate through your solver to optimize hyperparameters. Sampling function values is enough if you use the right smoothing and estimation techniques.
  • Smoothing as a Bridge: Gaussian smoothing isn't just a trick for the estimator; it provides a theoretical bridge that allows the authors to relate the "fuzzy" stationary points of the smoothed function back to the original non-smooth problem.
  • Robustness to Inexactness: Many bilevel algorithms assume the lower-level problem is solved exactly. This paper’s explicit modeling of "computational errors" in the lower level makes it much more applicable to real-world, large-scale imaging problems where exact solutions are impossible.

Key Results

  • Superior Tuning: In 1D denoising, the parameters learned by the algorithm significantly outperformed hand-tuned parameters, achieving lower mean-square error on unseen validation data.
  • Smart Sampling: In the Radon transform experiment, the algorithm successfully learned an optimal "policy" for selecting measurement angles. The reconstructions using these learned angles were visibly sharper and more accurate than those using uniform or random sampling.
  • Generalization: The authors demonstrated that parameters learned on a small training set generalize well to completely new, unseen data samples, proving the statistical validity of the approach.

Limitations and Future Work

  • Saddle Points: Like most first-order (or zeroth-order) methods, the algorithm aims for stationary points. It doesn't yet have a mechanism to guarantee it won't get stuck in a "saddle point" rather than a local minimum.
  • Sampling Efficiency: The current method uses i.i.d. Gaussian directions. The authors suggest that using Quasi-Monte Carlo or multi-level sampling could further reduce the number of function evaluations needed.
  • Higher-Order Extensions: The authors plan to explore stochastic Newton-type methods (second-order) to speed up convergence in highly non-convex landscapes.
  • Theory Constraints: The current complexity analysis relies on the hyperobjective being Lipschitz continuous; weakening this assumption is an open area for future theoretical development.

Summary updated

Abstract

Inverse problems are key issues in several scientific areas, including signal processing and medical imaging. Data-driven approaches for inverse problems aim for learning model and regularization parameters from observed data samples, and investigate their generalization properties when confronted with unseen data. This approach dictates a statistical approach to inverse problems, calling for stochastic optimization methods. In order to learn model and regularisation parameters simultaneously, we develop in this paper a stochastic bilevel optimization approach in which the lower level problem represents a variational reconstruction method formulated as a convex non-smooth optimization problem, depending on the observed sample. The upper level problem represents the learning task of the regularisation parameters. Combining the lower level and the upper level problem leads to a stochastic non-smooth and non-convex optimization problem, for which standard gradient-based methods are not straightforward to implement. Instead, we develop a unified and flexible methodology, building on a derivative-free approach, which allows us to solve the bilevel optimization problem only with samples of the objective function values. We perform a complete complexity analysis of this scheme. Numerical results on signal denoising and experimental design demonstrate the computational efficiency and the generalization properties of our method.
BibTeX
@inproceedings{staudigl2025derivative,
  author = {Mathias Staudigl and Simon Weißmann and Tristan van Leeuwen},
  title = {{Derivative-free stochastic bilevel optimization for inverse problems}},
  booktitle = {Computational},
  year = {2025},
  doi = {10.1007/s10589-025-00745-1},
}
Figure