Worst-case Nonlinear Regression with Error Bounds

这是一份关于论文《Worst-case Nonlinear Regression with Error Bounds》（具有误差界的最坏情况非线性回归）的详细技术总结。

1. 问题背景与定义 (Problem Statement)

在控制系统工程中，函数近似方法（如使用神经网络）被广泛用于获取控制导向模型或简化复杂的非线性控制律（如显式模型预测控制 MPC）。然而，传统的回归方法（如最小化均方误差 MSE）通常关注平均误差，无法保证最坏情况近似误差（Worst-Case Error, WCE）。

在鲁棒控制设计、约束满足保证以及闭环稳定性分析中，量化并最小化真实函数 $f(x)$ 与近似模型 $\hat{f}(x)$ 之间的最大偏差至关重要。

核心问题：
给定一个定义在紧集 $X \subset \mathbb{R}^n$ 上的非线性函数 $f$，寻找一个参数化模型 $\hat{f}(x; \theta)$（如前馈神经网络），以最小化 $X$ 上的最大绝对近似误差：
$$\theta^* \in \arg \min_{\theta} \left( r(\theta) + \max_{x \in X} |f(x) - \hat{f}(x; \theta)| \right)$$
其中 $r(\theta)$ 是正则化项。

该问题面临两个主要挑战：

1. 双层优化（Bilevel Optimization）：内层是一个在连续域 $X$ 上的最大化问题。
2. 非光滑性（Non-smoothness）：最大算子（max operator）导致目标函数不可微，难以使用高效的拟牛顿法（如 L-BFGS）进行训练。
3. 样本依赖性：解的质量高度依赖于训练样本的选择，随机采样可能无法捕捉到误差最大的“角落情况”（corner cases）。

2. 方法论 (Methodology)

作者提出了一种结合平滑近似与**主动学习（Active Learning）**的框架，旨在最小化最坏情况误差并提供严格的误差界。

2.1 平滑 $L_\infty$ 近似

为了解决最大算子的非光滑性，作者用平滑的 Log-Sum-Exp 函数近似最大算子。对于有限样本集 $\{x_k, y_k\}_{k=1}^{N_0}$，将原始问题转化为：
$$\theta^* \approx \arg \min_{\theta} \left( r(\theta) + \frac{1}{\gamma} \log \left( \sum_{k=1}^{N_0} \left( e^{\gamma(y_k - \hat{f}(x_k; \theta))} + e^{\gamma(\hat{f}(x_k; \theta) - y_k)} \right) \right) \right)$$
其中 $\gamma$ 是平滑参数。当 $\gamma \to +\infty$ 时，该问题收敛于原始的 $L_\infty$ 回归问题。这使得可以使用自动微分和 L-BFGS 等高效优化器。

2.2 基于全局优化的主动学习策略

为了减少训练样本对 WCE 的依赖，算法迭代地添加误差最大的样本点：

1. 训练：在当前数据集上求解平滑后的 $L_\infty$ 回归问题，得到模型参数 $\theta$。
2. 查询（Query）：使用全局优化算法（如 DIRECT）在整个输入域 $X$ 上寻找使 $|f(x) - \hat{f}(x; \theta)|$ 最大化的点 $x^*$。
3. 更新：将 $(x^*, f(x^*))$ 加入训练集，重复上述步骤，直到最大误差低于阈值 $\epsilon_{err}$ 或达到计算预算。

2.3 误差界量化 (Error Bounds)

训练完成后，算法不仅提供模型，还提供误差界：

• 全局均匀界：通过全局优化直接计算 $\bar{e}^* = \max_{x \in X} |f(x) - \hat{f}(x; \theta^*)|$。
• 非对称界：分别计算上界和下界，比对称界更紧。
• 输入相关界（Input-dependent Bounds）：
  • 训练一个额外的神经网络 $\varepsilon(x; \psi)$ 作为“包络函数”，使其在训练点上覆盖误差 $|e_k|$。
  • 通过全局优化计算缩放因子 $\kappa$，确保 $\kappa \cdot \varepsilon(x; \psi)$ 在整个 $X$ 上覆盖真实误差。
  • 这允许误差界随输入变化（异方差），比常数界更不保守。

2.4 约束满足与特殊结构

• 约束保持：若需近似约束 $f(x) \le 0$，通过平滑符号函数训练，并计算 $\Delta_f = \min_{x: f(x)>0} \hat{f}(x)$，构造 $\bar{f}(x) = \hat{f}(x) - \Delta_f + \epsilon$，确保 $\bar{f}(x) \le 0 \implies f(x) \le 0$。
• 饱和与特定形式：支持在训练过程中强制模型满足特定区域的行为（如线性区域）或输出范围（饱和函数）。

3. 主要贡献 (Key Contributions)

1. 平滑 $L_\infty$ 回归框架：提出了一种可微的平滑近似方法，使得利用现代深度学习优化器（L-BFGS）直接最小化最坏情况误差成为可能。
2. 主动学习策略：不同于依赖启发式采集函数的传统主动学习，该方法利用全局优化显式地寻找最大误差点（Corner-case detection），显著提高了样本效率。
3. 严格的误差界保证：
   • 提供了常数和非对称的误差界。
   • 提出了输入依赖的误差界（Input-dependent bounds），利用辅助神经网络学习误差分布，并通过全局优化缩放因子保证全局有效性，显著降低了保守性。
4. 广泛的适用性验证：
   • 非线性函数近似。
   • 非凸集合的凸内近似（用于可行域近似）。
   • 非线性动力学的离散时间不确定模型（带加性扰动）。
   • 显式 MPC 律的近似（包括 mpQP 和线性 MPC）。

4. 实验结果 (Results)

论文在 Python 库 maxfit 中实现了该方法，并在多个基准测试中进行了验证：

• 非线性函数近似：
  • 在 Gaussian 函数和复杂振荡函数上，主动学习策略在约 30-50 次迭代内将 WCE 降至极低水平（如 $10^{-3}$ 量级）。
  • 对比显示，最小化 MSE 并不能保证最小的 WCE，甚至可能导致较大的最坏情况误差。
• 非凸集合的凸内近似：
  • 成功找到了非凸集合 $S$ 的凸多面体和输入凸神经网络（ICNN）内近似，保证了近似集合完全包含在原集合内。
• 不确定动力学建模：
  • 对带有摩擦和非线性刚度的摆模型进行离散化建模，计算出的加性扰动界（WCE）分别为状态 1 的 2.82% 和状态 2 的 5.67%，证明了该方法能有效量化模型不确定性。
• MPC 近似：
  • mpQP 近似：在 162 个区域的参数化二次规划问题上，近似误差在无约束区域接近零，且整体 WCE 极小。
  • 线性 MPC 闭环仿真：在控制非最小相位系统时，基于主动学习最小化 WCE 的模型，其闭环性能与精确 MPC 几乎一致（WCE $\approx 0.06$），而仅最小化 MSE 的模型 WCE 高达 0.4，导致控制性能显著下降。

5. 意义与局限性 (Significance & Limitations)

意义：

• 控制理论价值：为基于数据驱动的控制（如近似 MPC、鲁棒控制）提供了严格的理论保证。通过量化最坏情况误差，可以直接用于鲁棒控制器的设计，确保在近似误差存在的情况下系统仍满足稳定性和约束条件。
• 方法论创新：将全局优化与主动学习结合，解决了 $L_\infty$ 回归中非光滑和样本选择困难的问题。
• 工具开源：提供了 Python 库 maxfit，便于社区复现和应用。

局限性：

• 维度灾难：该方法依赖于全局优化来寻找最大误差点。随着输入维度 $n$ 的增加，全局优化的计算成本呈指数级增长，限制了该方法在超高维问题上的直接应用。
• 计算开销：虽然训练模型本身很快，但每一步主动学习迭代都需要运行一次全局优化，总体计算时间较长（如线性 MPC 示例中耗时约 2200 秒）。

总结：
这篇论文提出了一种严谨且实用的框架，用于训练具有可证明的最坏情况误差界的非线性代理模型。它填补了传统统计回归（关注平均误差）与控制工程需求（关注最坏情况保证）之间的空白，特别适用于对安全性要求极高的控制应用。