⚡ electrical engineering

Worst-case Nonlinear Regression with Error Bounds

This paper proposes an active-learning method for nonlinear minimax regression that fits surrogate models by minimizing the maximum absolute error through a smooth $L_\infty$ approximation and iterative global optimization, while deriving rigorous worst-case error bounds validated across various nonlinear applications.

Original authors: Alberto Bemporad

Published 2026-04-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alberto Bemporad

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 a master chef trying to teach a robot to bake the perfect chocolate cake. You have the original recipe (the "true function"), and you want the robot to learn how to bake it so well that it tastes identical every time.

Most machine learning methods are like a student who takes a test, gets a score of 95%, and says, "Great, I'm good enough!" They minimize the average error. But in the world of engineering and safety (like controlling a self-driving car or a nuclear reactor), an average score isn't enough. You need to know: "What is the worst possible cake this robot could bake?" If the robot burns the cake once in a thousand tries, that's a disaster waiting to happen.

This paper, by Alberto Bemporad, introduces a new way to train these "robots" (mathematical models) that focuses entirely on that worst-case scenario.

Here is the breakdown of their approach using simple analogies:

1. The Goal: The "Worst-Case" Safety Net

Instead of trying to make the robot's average performance perfect, the goal is to minimize the maximum possible mistake.

The Analogy: Imagine you are building a bridge. You don't just want the bridge to hold the average weight of cars. You need to know the absolute heaviest truck that could ever drive over it, and ensure the bridge doesn't collapse. This paper builds a "safety net" that guarantees the model will never be more wrong than a specific amount, no matter what input it gets.

2. The Problem: The "Jagged" Mountain

Mathematically, finding this "worst-case" error is like trying to find the highest peak in a mountain range that is covered in jagged, sharp rocks.

The Issue: Standard computer training tools (like gradient descent) are like hikers who slide down smooth slopes. They get stuck or confused when they hit a sharp, jagged peak (a "non-smooth" mathematical problem). They can't easily calculate which way to go to find the absolute highest point.
The Solution: The authors invented a "smoothie" version of those jagged rocks. They replaced the sharp, jagged math with a smooth, slippery approximation. This allows the computer to slide down the slopes easily and find the solution, while still being accurate enough to represent the original jagged problem.

3. The Strategy: "Active Learning" (The Treasure Hunt)

Usually, you train a model by giving it a big pile of random data (like throwing darts at a map). But if you throw darts randomly, you might miss the most dangerous cliffs.

The Old Way: Throw 1,000 darts randomly. Hope you hit the worst spots.
The New Way (Active Learning): The authors treat this like a treasure hunt for the "worst-case" errors.
1. The robot makes a guess.
2. The computer acts like a detective, searching the entire map to find the one single spot where the robot made the biggest mistake.
3. They add only that specific spot to the training data.
4. They retrain the robot.
5. They repeat this until the biggest mistake is tiny.

This is much more efficient. Instead of guessing where the errors are, the computer actively hunts them down and fixes them one by one.

4. The Result: The "Guaranteed" Bounds

Once the training is done, the paper doesn't just say, "Here is the model." It gives you a guarantee.

The Analogy: It's like a weather forecast that doesn't just say, "It will be 75°F." It says, "It will be 75°F, and I guarantee it will never be hotter than 80°F or colder than 70°F, no matter what."
The paper provides a mathematical "envelope" (a box) around the model. Inside this box, the true answer is guaranteed to be. This is crucial for safety-critical systems like Model Predictive Control (MPC), where you need to prove the system won't crash even if the model is slightly wrong.

5. Real-World Applications

The authors tested this on several tricky problems:

Approximating Complex Laws: Simplifying complex control laws (like how a drone flies) so a cheap computer can run them, while guaranteeing the drone won't crash.
Uncertain Models: Learning how a pendulum swings when you don't know exactly how much friction there is, and calculating exactly how much "wiggle room" (uncertainty) you have.
Set Approximations: Drawing a simple shape (like a polygon) inside a complex, weirdly shaped blob to ensure you stay inside the safe zone.

Summary

In short, this paper is about stop guessing and start guaranteeing.

Instead of training AI to be "mostly right" on average, they built a system that:

Hunts down the specific scenarios where the AI is most likely to fail.
Trains specifically to fix those failures.
Calculates a hard, mathematical limit on how wrong the AI can ever be.

It's the difference between a driver who says, "I usually drive safely," and a driver who has a certificate proving, "I will never exceed 5 mph over the speed limit, even in a blizzard." For engineering and safety, that guarantee is everything.

1. Problem Statement

The paper addresses the challenge of approximating nonlinear functions (or control laws) where guaranteed worst-case error bounds are critical, particularly in control systems engineering (e.g., Model Predictive Control, robust control design).

Limitation of Standard Methods: Traditional regression methods (like training Neural Networks with Mean Squared Error) minimize average error. A low average error does not guarantee a small worst-case error, which can lead to instability or constraint violations in safety-critical control applications.
The Core Objective: Given a known nonlinear function $f(x)$ over a compact set $\mathcal{X}$ , the goal is to find a parametric surrogate model $\hat{f}(x; \theta)$ (e.g., a Neural Network) that minimizes the Worst-Case Error (WCE):
$\bar{e}^* = \max_{x \in \mathcal{X}} |f(x) - \hat{f}(x; \theta)|$
Furthermore, the method must provide rigorous upper and lower bounds on this error over the entire domain, not just on the training data.

2. Methodology

The proposed approach combines Minimax Regression (Chebyshev approximation), Smooth Optimization, and Active Learning.

A. Smooth Minimax Formulation

The standard minimax problem involves a non-smooth $\max$ operator, which hinders the use of efficient gradient-based optimizers (like L-BFGS).

Solution: The author replaces the non-smooth $\max$ operator with a smooth, arbitrarily accurate approximation using the Log-Sum-Exp (softmax) function.
$\max_k |y_k - \hat{f}(x_k)| \approx \frac{1}{\gamma} \log \left( \sum_{k=1}^{N} e^{\gamma(y_k - \hat{f}(x_k))} + e^{\gamma(\hat{f}(x_k) - y_k)} \right)$
As the smoothing parameter $\gamma \to \infty$ , this converges to the true $L_\infty$ norm, enabling the use of automatic differentiation and quasi-Newton methods.

B. Active Learning Strategy

To ensure the model generalizes well and the WCE is minimized over the entire domain $\mathcal{X}$ (not just the training set), an active learning loop is employed:

Train: Fit the model on the current dataset using the smooth minimax loss.
Identify Worst Case: Use global optimization (specifically the DIRECT algorithm) to find the point $x^* \in \mathcal{X}$ where the current model has the maximum approximation error.
Enrich: Add $(x^*, f(x^*))$ to the training dataset.
Iterate: Repeat until the maximum error falls below a threshold $\epsilon_{err}$ or a computational budget is exhausted.

Key Distinction: Unlike standard active learning that uses heuristic acquisition functions, this method explicitly queries the "corner cases" (points of maximum error) via global optimization.

C. Error Bound Quantification

After training, the method provides rigorous bounds on the error:

Global Bounds: Computing the global maximum error $\bar{e}^*$ via global optimization.
Input-Dependent Bounds: Learning a separate "envelope function" $\varepsilon(x)$ (also a Neural Network) that bounds the error locally. This allows for tighter, non-uniform bounds (e.g., the error might be larger in certain regions of the state space).
Asymmetric Bounds: The framework supports separate upper and lower bounds ( $e_{min}(x)$ and $e_{max}(x)$ ), reducing conservativeness.

D. Specialized Constraints

The paper extends the framework to handle specific structural requirements:

Functional Constraints: Enforcing $\hat{f}(x) = w(x)$ on specific subsets (e.g., linear behavior in certain regions).
Saturation: Bounding the output of the model within specific limits.
Constraint Satisfaction: Transforming the regression problem to ensure that a simplified constraint $\bar{f}(x) \leq 0$ implies the original constraint $f(x) \leq 0$ , crucial for safety verification.

3. Key Contributions

Smooth $L_\infty$ Regression: A differentiable formulation of minimax regression that enables efficient training of complex models (NNs) using standard deep learning tools.
Active Learning for Worst-Case: A novel strategy that iteratively queries the global optimizer to find maximum error points, directly targeting the reduction of the worst-case error rather than average error.
Rigorous Uncertainty Quantification: Derivation of constant and input-dependent error bounds that are mathematically guaranteed (assuming the global optimizer is sufficiently accurate).
Versatility: The framework is demonstrated on diverse tasks:
- Approximating nonlinear functions.
- Finding convex inner approximations of nonconvex sets.
- Learning uncertain discrete-time models of nonlinear dynamics.
- Approximating explicit Model Predictive Control (MPC) laws.

4. Results and Validation

The approach was validated using a Python library (maxfit) on several benchmarks:

Nonlinear Function Approximation: Successfully approximated a complex Gaussian function. The method achieved a significantly lower Worst-Case Error (WCE) compared to standard MSE training, even though the MSE was slightly higher.
Nonconvex Set Approximation: Generated convex polyhedral and input-convex neural network approximations of a nonconvex set, guaranteeing that the approximated set is strictly contained within the original set.
Uncertain System Identification: Learned a discrete-time model of a pendulum with friction and nonlinear stiffness. The resulting additive disturbance bounds were tight (max relative error ~2.8% and 5.7%).
Explicit MPC Approximation:
- mpQP: Approximated a multiparametric QP solution with 162 regions. The error was near-zero in unconstrained regions.
- Linear MPC: Approximated a control law for a non-minimum phase system.
- Comparison: A model trained with the proposed active-learning minimax approach achieved a WCE of 0.064, whereas a model trained with 100,000 random samples using standard MSE or minimax loss (without active learning) resulted in a WCE of ~0.40. This highlights the inefficiency of random sampling for worst-case guarantees.

5. Significance

Safety-Critical Control: The ability to provide guaranteed error bounds is essential for deploying learned controllers in real-world systems where safety is paramount. It bridges the gap between data-driven learning and robust control theory.
Efficiency: By focusing on "corner cases" via active learning, the method achieves high accuracy with fewer data points compared to random sampling, which is computationally expensive for global optimization.
Practical Implementation: The release of the maxfit library makes these advanced techniques accessible to the control and machine learning communities.
Limitation: The reliance on global optimization for finding the worst-case error means the method scales poorly with high-dimensional input spaces, limiting it currently to low-to-medium dimensional problems (e.g., $n < 10-20$ ).

In summary, this paper presents a robust framework for training surrogate models where the worst-case performance is the primary metric, ensuring that approximations used in control systems are safe, reliable, and mathematically verified.