💻 computer science

Empirical risk minimization for risk-neutral composite optimal control with applications to bang-bang control

This paper develops a Monte Carlo-based empirical risk minimization framework with theoretical guarantees for solving risk-neutral composite optimal control problems involving nonsmooth objectives, and demonstrates its effectiveness in addressing bang-bang control problems using a conditional gradient method.

Original authors: Johannes Milz, Daniel Walter

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Johannes Milz, Daniel Walter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a ship trying to navigate through a foggy ocean to reach a specific island. You have a map (your mathematical model), but the weather (the "randomness" or uncertainty) is unpredictable. Sometimes the wind blows hard, sometimes the currents shift. Your goal is to find the best steering angle (the "control") that gets you to the island with the least amount of fuel, even though you don't know exactly what the weather will be like on any given day.

This paper is about a sophisticated way to solve that navigation problem when the rules of the game are a bit tricky. Here is the breakdown in everyday language:

1. The Problem: A Foggy Map with a "Bumpy" Goal

Usually, when we try to find the best path, we assume the terrain is smooth and predictable. But in real-world engineering (like designing groundwater cleanup systems or placing sensors), the terrain is bumpy and uncertain.

The Uncertainty: You can't know the exact wind or current. So, instead of guessing one weather pattern, you simulate thousands of possible weather scenarios.
The "Bumpy" Goal: The authors are dealing with a specific type of problem where the "cost" of your decision isn't a smooth curve. It's like trying to find the lowest point in a landscape that has sharp cliffs and flat plateaus. In math terms, this is called a nonsmooth problem.
The "Bang-Bang" Twist: In some of these problems, the best solution isn't a gentle turn; it's an extreme one. You either push the throttle to 100% forward, 100% backward, or you cut the engine completely. There is no "halfway." This is called bang-bang control. It's like a light switch: it's either ON or OFF, never dim.

2. The Solution: The "Sample Average" Guessing Game

Since you can't calculate the perfect answer for every possible weather scenario (there are infinite possibilities), the authors use a clever trick called Sample Average Approximation (SAA).

The Analogy: Imagine you want to know the average height of everyone in a giant city. You can't measure every single person. Instead, you pick a random group of 100 people, measure them, and take the average. You assume that this small group represents the whole city.
In the Paper: The computer simulates a specific number of random weather scenarios (say, 100, 1,000, or 10,000). It solves the navigation problem for each of these specific scenarios and then averages the results. This average becomes the "best guess" for the real-world problem.

3. The Big Question: How Many Samples Do We Need?

The paper asks a critical question: "How big does our group of 100 people need to be to get a good answer?"

The Challenge: Because the goal is "bumpy" (nonsmooth) and the terrain is complex (involving partial differential equations, which are like the physics of fluid flow or heat), it's hard to know how many samples are enough.
The Breakthrough: The authors developed a mathematical formula to tell you exactly how many samples you need to get a reliable answer.
- If you want to be very precise, you need more samples.
- If the problem is "convex" (the landscape is bowl-shaped, even if bumpy), you get a "super-convergence" bonus: your answer gets incredibly accurate very quickly as you add more samples.
- If the problem is "non-convex" (the landscape has many hills and valleys), they proved that your answer will still eventually settle on the right path, provided you keep adding samples.

4. The "Bang-Bang" Application

The authors tested their theory on a specific type of problem where the solution naturally wants to be "all or nothing" (bang-bang).

The Metaphor: Think of a thermostat. A standard thermostat might try to find a perfect temperature by adjusting the heat by tiny fractions. A "bang-bang" thermostat is like a primitive one: it blasts full heat until the room is hot, then turns completely off until it's cold.
The Result: The authors showed that their method works perfectly for these "all-or-nothing" problems. They used a specific algorithm (a "conditional gradient method") that is like a hiker who knows to only walk in the direction of the steepest slope, ignoring the flat, confusing parts of the terrain.

5. The Proof: Simulations

To prove their math wasn't just theory, they ran computer simulations.

They created a virtual world with random weather.
They ran their algorithm with small sample sizes, then medium, then huge ones.
The Result: As they added more samples, the error in their solution dropped exactly as their math predicted. The "bumpy" solutions they found looked exactly like the "all-or-nothing" solutions they expected.

Summary

In short, this paper provides a rulebook for navigating uncertainty when the rules are sharp and the solutions are extreme. It tells engineers:

You can approximate complex, uncertain problems by simulating random scenarios.
Here is the exact math to tell you how many simulations you need to trust your answer.
This works even when the best solution is a drastic "on/off" switch rather than a gentle adjustment.

It's a bridge between abstract math and real-world engineering, ensuring that when we design systems to handle chaos, we know exactly how much data we need to feel safe.

1. Problem Statement

The paper addresses risk-neutral composite optimal control problems under uncertainty, specifically those governed by Partial Differential Equations (PDEs). The general mathematical formulation is:

$\min_{u \in U} G(u) := F(Bu) + \psi(u)$

Where:

$U$ : A separable Hilbert space (control space).
$W$ : A separable Banach space.
$B: U \to W$ : A linear, compact operator (often representing the solution map of a PDE).
$F(w) = \mathbb{E}[f(w, \xi)]$ : An expectation function where $f$ is a smooth integrand and $\xi$ is a random variable representing uncertainty.
$\psi(u)$ : A proper, closed, convex, but potentially nonsmooth function (e.g., an $L^1$ -norm penalty).

The specific focus is on PDE-constrained optimization where the objective includes a tracking-type functional and a nonsmooth regularizer. A primary application discussed is bang-bang control, where the regularizer $\psi(u)$ (often an $L^1$ -norm plus an indicator function for box constraints) encourages solutions where the control $u(x)$ takes values only at the boundaries of the feasible set (e.g., $\{-1, 0, 1\}$ ).

2. Methodology

To solve these infinite-dimensional stochastic problems numerically, the authors employ the Sample Average Approximation (SAA) method, also known as Empirical Risk Minimization (ERM).

Approximation: The expected value $F(w)$ is approximated by the sample mean over $N$ independent and identically distributed (i.i.d.) samples $\xi_1, \dots, \xi_N$ :
$\hat{F}_N(w) = \frac{1}{N} \sum_{i=1}^N f(w, \xi_i)$
The resulting SAA problem is: $\min_{u \in U} \hat{G}_N(u) = \hat{F}_N(Bu) + \psi(u)$ .
Analytical Framework:
- Gap Functional: Since the problem is nonconvex and nonsmooth, the authors analyze critical points rather than just global minimizers. They define a gap functional $\Psi(u)$ (and its SAA counterpart $\hat{\Psi}_N(u)$ ) based on the first-order necessary subdifferential inclusion. A point is critical if the gap is zero.
- Compactness: The analysis heavily relies on the compactness of the operator $B$ . This property is crucial for establishing uniform convergence laws and deriving covering numbers for the image of the feasible set.
- Assumptions: The paper assumes the integrand is sufficiently smooth, the gradient satisfies Lipschitz conditions, and the random variables have light-tailed (sub-Gaussian) distributions.

3. Key Contributions

The paper makes three primary theoretical contributions:

Asymptotic Consistency:
- Proves that as the sample size $N \to \infty$ , the optimal values, solutions, and critical points of the SAA problem converge almost surely to those of the true risk-neutral problem.
- Establishes that the gap functional evaluated at SAA critical points converges to zero.
Non-Asymptotic Sample Size Estimates (General Case):
- Derives bounds on the expected error of the gap functional for nonconvex problems.
- The bound depends on the covering number of the set $B(D(\psi))$ (the image of the feasible set under the compact operator).
- Provides a formula for the required sample size $N$ to ensure the expected gap error is within $\epsilon$ , explicitly linking $N$ to the metric entropy (covering numbers) of the problem.
Enhanced Convergence Rates (Convex Case):
- For problems where the integrand is convex and a growth condition (Hölder-type inequality) holds at the minimizer, the authors derive stronger results.
- They prove that the expected distance between the SAA solution and the true solution converges at the standard Monte Carlo rate ( $O(1/\sqrt{N})$ ).
- Crucially, they show superconvergence for the objective function value and the gap functional, which converge at a rate of $O(1/N)$ . This result holds even without requiring the operator $B$ to be compact, provided specific embedding conditions are met.

4. Results and Applications

The theoretical framework is applied to two specific classes of PDE-constrained problems:

Affine-Linear PDEs: The state equation is linear in the control (e.g., $-\Delta y + u = \text{source}$ ). The authors verify that the smoothness and regularity assumptions hold for elliptic equations with random diffusion coefficients.
Bilinear PDEs: The state equation involves a product of control and state (e.g., $-\Delta y + uy = \text{source}$ ). This is more challenging due to the nonlinearity. The authors establish the necessary regularity of the control-to-state map and verify the Lipschitz conditions required for the theoretical bounds.

Numerical Illustrations:

The authors present numerical experiments for both affine-linear and bilinear cases with bang-bang type regularization ( $L^1$ -norm).
Findings:
- The empirical convergence rates of the optimality gap and the distance to the reference solution match the theoretical predictions ( $O(1/N)$ for the gap, $O(1/\sqrt{N})$ for the solution distance).
- In the bilinear case, the observed convergence was even faster than the theoretical lower bound, suggesting that the covering number approach might be conservative and does not fully exploit local curvature or higher-order regularity.

5. Significance

Handling Nonsmoothness: The paper bridges a gap in the literature by providing rigorous convergence analysis for nonsmooth (specifically $L^1$ -regularized) stochastic optimal control problems, which are essential for sparse and bang-bang controls but difficult to analyze due to the lack of strong convexity.
Relaxing Convexity Requirements: Unlike many previous works that require strong convexity of the regularizer (e.g., Tikhonov $L^2$ ), this framework accommodates general convex, nonsmooth regularizers by leveraging the compactness of the PDE solution operator.
Practical Guidance: The derived sample size estimates provide practitioners with quantitative guidelines on how many Monte Carlo samples are needed to achieve a desired accuracy in the gap functional, depending on the dimensionality and regularity of the problem.
Reproducibility: The authors provide open-source code (using FEniCS and Moola) to reproduce the numerical experiments, ensuring the results are verifiable.

In summary, this work provides a robust theoretical foundation for using Monte Carlo-based SAA methods to solve complex, nonsmooth, risk-neutral optimal control problems governed by PDEs, with specific and successful application to the challenging class of bang-bang control problems.