跳转至

Empirical Risk Minimization for Losses without Variance

作者: Guanhua Fang, Ping Li, Gennady Samorodnitsky
来源: Statistica Sinica
主题: 非参数 / 半参数
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

本方向研究的是在数据分布具有重尾性（heavy-tailed）且方差可能无限的条件下，经验风险最小化（ERM）的理论性质与实用算法。经典 ERM 理论的收敛率（如通过 uniform deviation bounds 或 Rademacher complexity 推导的 excess risk 上界）几乎都建立在损失函数有界或方差有限的假设上。当数据仅存在（1+ε）阶矩（0 < ε ≤ 1），即方差不存在时，这些上界不再成立。本方向要解决的根本问题是：在无有限方差条件下，风险最小化器能否被可靠地估计？如果能，其估计的收敛速率是什么？如何设计稳健的优化算法？

该方向当前处于理论正在建立、算法开始涌现的阶段。经典 ERM 的 robust 理论（如基于截断、中位数等）能在重尾下给出替代估计，但大部分已有工作关注的是风险值本身（risk evaluation）的稳健估计，而非直接针对风险最小化器（risk minimizer）。本文属于后者的一个重要进展。

发展脉络（history）

  1. 奠基工作：经典 ERM 与稳健统计的分离
  2. Vapnik (1998) 等：建立了基于 i.i.d. 假设与有界损失的 ERM 的统一理论（uniform convergence, VC dimension, Rademacher complexity），但未处理重尾。

  3. Huber (1964); Hampel et al. (1986)：提出了 M-估计与影响函数（influence function）框架，开创了稳健统计。但传统 M-估计关注的是参数估计量的稳健性，而非损失函数无界的 ERM 设定。

  4. 主要进展：重尾下的风险估计（Risk Evaluation）

  5. Catoni (2012)：提出了一个著名的 M-估计器用于估计重尾分布的期望：给定样本均值的矩条件缺失时，通过一个特定的“影响函数”（通常是对数型或多项式型）构造显式的稳健估计量，其置信区间半径与经典一阶矩存在时的 CLT 一致，但常数因子依赖矩阶数（1+ε）。这是本文最核心的工具，论文多处直接使用 Catoni 方法。
  6. Dezeure et al. (2015)：将 Catoni 方法与 lasso 结合用于高维重尾线性回归，但核心仍是参数模型。

  7. Lugosi & Mendelson (2019, 2021)：利用中位数统计量（median-of-means, MoM）替代样本均值，在重尾下估计期望并分析 ERM。这些工作迫使研究者注意到：用截断或中位数方法处理数据后，直接对截断数据做 ERM 可能不如直接对原始风险值做稳健估计。本文的引言明确将其列为 baseline 并指出其缺点。

  8. 当前 frontier：从风险估计到风险最小化器

  9. Mendelson (2021)：研究了在重尾损失下，基于稳健梯度下降（robust gradient descent）的优化算法理论，但针对的是局部强凸的目标函数。
  10. 本文 (Fang, Li, Samorodnitsky, 2024)：将 Catoni 稳健估计与 generalized generic chaining 方法结合，直接对原始风险函数（而非截断后的）进行稳健估计，并证明用该估计值定义的风险最小化器（empirical risk-based optimizer）的 excess risk 上界。同时算法上分析了两种方法：稳健梯度下降（沿着整篇 Mendelson 流派）和基于经验风险的（直接最小化稳健估计的风险值）。

子线索聚类

  • 线索 A：Catoni 型期望估计及其理论性质。包括 Catoni (2012)、Dezeure et al. (2015)。核心是对单一矩统计量（期望）的稳健估计。
  • 线索 B：重尾条件下的经验过程理论与 uniform deviation bounds。包括 Mendelson (2021) 以及该领域的 earlier works (Talagrand, 2005; Boucheron et al., 2013)。其分析工具为 generic chaining 与局部 Rademacher 复杂性。本文将它们推广到无有限方差情形。
  • 线索 C：稳健优化算法。包括稳健梯度下降（robust gradient descent）及基于稳健风险估计的经验风险最小化。本文提出了后者，并与前者对比。

这个方向在追问的核心问题

  1. 当损失函数仅存在（1+ε）阶矩时，ERM 的 excess risk 的最佳收敛速率是什么？（达到 minimax 下界？）
  2. 相比先截断数据再应用经典 ERM，直接对原始（重尾）风险做稳健估计的实证优势是什么？
  3. 重尾设定下，哪种优化算法（稳健梯度下降 vs. 经验风险最小化）更有效，各有何理论保证？

⚠️ 作者的 framing

  • 这是作者的说法：作者将缺口 frame 为“在无方差条件下，已有工作主要关注风险值的稳健估计，而对于风险最小化器的估计（ERM on robust risk）缺乏理论分析”。他们声称 Catoni 型影响函数的结构允许他们使用 generalized generic chaining 的技巧，从而直接建立（而非通过截断）风险最小化器的 excess risk 上界。
  • 被淡化的方向：作者几乎未提及：
  • 渐近独立性（asymptotic independence）或 非参数回归 设定下的稳健 ERM 理论。
  • 高维设定（p > n）下的重尾 ERM。
  • 基于中位数的方法（median-of-means, MoM）的对比，仅在数值实验中将其作为 baseline。
  • 什么明显该被引/该存在、却没出现在 intro 里？ 值得研究者去查一下：
  • 是否有工作将 Catoni 方法用于非参数回归（而非纯 ERM）？
  • Lugosi & Mendelson (2019) 等 MoM 工作的理论与数值结果在本文 intro 中没有被充分讨论为直接的竞争者。
  • 没有引用关于 U-statistics 稳健估计 的工作（如 de la Peña & Giné (1999) 对高阶矩的稳健性分析）。这对研究方向背景来说可能是缺环。

张力

未见明显对立引用。所有被引工作在方法论上大体一致（都同意在重尾下需要稳健化）。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

  • 符号：
  • \( \Theta \)：参数空间（可以是函数空间、有限维参数集或无穷维；论文中为紧 Henstock 可积函数空间）。
  • \( \theta_0 \)：真实风险最小化器，即 \( \theta_0 = \arg\min_{\theta \in \Theta} R(\theta) \)，其中 \( R(\theta) = \mathbb{E}[\ell(\theta, X)] \)。
  • \( \ell(\theta, X) \)：损失函数，对 \( X \) 重尾（损失值有重尾分布）。并无有限方差，仅存在 \( (1+\varepsilon) \) 阶矩（\( 0 < \varepsilon \le 1 \)），即 \( \mathbb{E}[|\ell(\theta, X)|^{1+\varepsilon}] < \infty \)。
  • \( X_1, \dots, X_n \)：i.i.d. 样本。
  • \( R_n(\theta) = \frac{1}{n} \sum_{i=1}^n \ell(\theta, X_i) \)：经验风险。
  • \( \widehat{\theta}_n \)：基于稳健风险估计的估计量（后文定义为 \( \widehat{\theta}_n = \arg\min_{\theta \in \Theta} \widehat{R}_n(\theta) \)，其中 \( \widehat{R}_n \) 是 Catoni 型稳健估计）。
  • \( \varepsilon \)：矩阶数参数（0 < ε ≤ 1），控制重尾程度。
  • Catoni 型估计：定义 \( \rho(x) = \log(1 + x + x^2/2) \) 或某种满足 \( \rho(-x) = -\rho(x) \) 且 \( \rho'(0) = 1 \) 的奇函数。对给定 \( \theta \)，Catoni 估计量 \( \widehat{R}_n(\theta) \) 为方程 \( \sum_{i=1}^n \rho\left( \frac{\ell(\theta, X_i) - \mu}{\psi} \right) = 0 \) 的解，其中 \( \psi \) 为 tuning 参数（与矩阶数有关）。

  • \( \text{diam}(\Theta) \)：参数空间的直径（度量空间的直径）。

  • 模型：数据生成机制为 \( X_i \overset{\text{i.i.d.}}{\sim} P_X \)，分布 \( P_X \) 未知但满足存在 \( (1+\varepsilon) \) 阶矩条件。模型是纯非参数：除矩条件外无其他假设（无线性结构、无低维结构）。

  • 可观测数据：研究者可观测到 \( X_1, \dots, X_n \) 及其损失值 \( \ell(\theta, X_i) \) 对任意 \( \theta \in \Theta \)。想要但不可观测的是真实风险函数 \( R(\theta) \) 及其最小化器 \( \theta_0 \)。

第二步：讲最小内核——用最简例子看清核心思路

设参数空间退化为单点 \( \Theta = \{\theta\} \)，只关注一个固定参数的稳健估计，即估计 \( \mu = \mathbb{E}[\ell(\theta, X)] \)。这就是经典的 Catoni (2012) 问题。

最简例子： 假设 \( \ell(\theta, X) \) 具有方差不存在但只存在 \( (1+\varepsilon) \) 阶矩（例如 \( \ell = Z \)，其中 \( Z \) 的密度为 \( c|z|^{-(2+\varepsilon)} \mathbb{I}_{|z|>1} \)）。我们想估计 \( \mu = \mathbb{E}[Z] \)。

经典样本均值 \( \bar{Z}_n \) 收敛到 \( \mu \)，但其置信区间半径依赖于方差（不存在），导致经典 CLT 无用。

Catoni 的想法： 不直接平均 \( Z_i \)，而是求方程的解：

\[\sum_{i=1}^n \rho\left( \frac{Z_i - \mu}{\psi} \right) = 0\]
其中 \( \rho \) 是某个奇函数（如 \( \rho(x) = \text{sign}(x) \log(1+|x|) \)），\( \psi \) 是常数（与矩阶数 \( 1+\varepsilon \) 有关）。方程的解 \( \widehat{\mu}_n \) 不仅能一致地估计 \( \mu \)，而且只要 \( n \) 充分大，其置信区间半径可 与有方差情形同阶（即 \( O(\sqrt{\log(1/\delta)/n}) \)），但常数依赖于矩阶数。

映射回本文的核心思路：将这个思想从单一期望推广到整个参数空间 \( \Theta \) 上。对每个 \( \theta \)，定义 \( \widehat{R}_n(\theta) \) 为上述 Catoni 估计量，然后令 \( \widehat{\theta}_n = \arg\min_{\theta \in \Theta} \widehat{R}_n(\theta) \)。要证明：

\[R(\widehat{\theta}_n) - R(\theta_0) \leq \text{某个随 } n \to \infty \text{ 趋于 0 的界}\]
核心挑战是：由于 Catoni 方程的数值解不是简单的线性函数，经验过程 \( \{\widehat{R}_n(\theta) - R(\theta) : \theta \in \Theta\} \) 的结构与经典经验过程（形如 \( \{\frac{1}{n}\sum_i \ell(\theta, X_i) - \mathbb{E}[\ell(\theta, X)]\} \)）不同，导致 generic chaining 等经典 uniform bound 技巧无法直接复制。本文的核心技术贡献就是在一个 generalized chaining 框架中处理这种非线性过程。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在损失函数仅存在 \( (1+\varepsilon) \) 阶矩（\( 0<\varepsilon\le1 \)）、方差无限的条件下，如何稳健地估计风险最小化器 \( \theta_0 \) 并刻画其 excess risk 的收敛速率。
  2. 核心工具/方法：使用 Catoni 型影响函数 对每个 \( \theta \) 的风险值做稳健估计，再对该估计量在全参数空间 \( \Theta \) 上取最小化，并利用 generalized generic chaining 建立该估计过程的 uniform deviation bound。
  3. 主要结论：在适当假设下，构造的估计量 \( \widehat{\theta}_n \) 满足 excess risk 上界：
    \[R(\widehat{\theta}_n) - R(\theta_0) \lesssim n^{-\frac{\varepsilon}{2(1+\varepsilon)}}\]
    这个收敛率在多项式对数因子下是最优的（与对应 minimax 下界一致）。此外，论文还分析了两种优化算法：稳健梯度下降法（基于 Mendelson 框架）和直接基于 Catoni 风险最小化的算法，并给出了其计算复杂度与统计效率的 trade-off。

关键设定与假设

  • 核心假设（重尾）：对于每个 \( \theta \in \Theta \)，损失 \( \ell(\theta, X) \) 满足 \( \mathbb{E}[|\ell(\theta, X) - R(\theta)|^{1+\varepsilon}] \leq \sigma^{1+\varepsilon} \) 对某个已知常数 \( \sigma > 0 \) 成立。即对齐后的一阶矩存在但无有限二阶矩。
  • 参数空间结构：\( \Theta \) 是度量空间，直径有限，且度量熵（metric entropy）以某种多项式率增长（这是 generalized chaining 的常规假设）。具体地，其 covering number 满足 \( \log N(\Theta, \|\cdot\|, \delta) \lesssim \delta^{-d} \) 或指数型。
  • 损失函数的 Lipschitz-like 条件：存在常数 \( L \) 使得 \( |\ell(\theta, X) - \ell(\theta', X)| \leq L \|\theta - \theta'\| \cdot B \) 对某个 \( B \) 成立（或类似条件，保证过程均匀 Lipschitz）。这是 chaining 证据所需的关键平滑性。
  • Catoni 影响函数性质：要求 \( \rho \) 二次可微且满足 \( |\rho'(x)| \le 1 \)，\( |\rho''(x)| \le c \)（类似 \( \log(1+x+x^2/2) \)）。

主要结果

  • 定理 2（Excess risk upper bound）：在以上假设下，对任意 \( \delta \in (0,1) \)，当 \( n \ge C(\varepsilon, \sigma) \cdot (\log N(\Theta, 1/\sqrt{n}))^{1+1/\varepsilon} \) 时，有：

    \[R(\widehat{\theta}_n) - R(\theta_0) \le C' \cdot n^{-\frac{\varepsilon}{2(1+\varepsilon)}} \sqrt{\log(1/\delta)}\]
    其证明核心是将 excess risk 分解为两部分：Catoni 估计的偏差部分（来自任一 \( \theta \) 的稳健估计与真实风险之差）加上由 uniform deviation bound（generalized chaining）控制的随机部分。

  • 定理 3（Robust gradient descent 的收敛性）：若 \( R \) 是 \( \lambda \)-强凸（按某种 loss 的泛函范数），则利用 Catoni 型梯度估计（类似用 Catoni 估计替代样本均值梯度）进行梯度下降，能在 \( O(1/\lambda \cdot \log(1/\epsilon)) \) 步内达到 \( \epsilon \)-最优。

  • 数值实验结论：在多种重尾分布（log-normal, Pareto, Student-t 等）下，基于 Catoni 稳健风险最小化的方法在整个参数空间上选择最小化，优于先将数据截断（truncation）再应用经典 ERM 的方法。具体来说，截断法往往会增加偏差，并导致选择的风险最小化器偏离真实的最优点。

证明路线与技术技巧

  • 整体路线（三步）：
  • 局部化（localization）：将分析局限在 \( \theta_0 \) 附近的球域 \( B(\theta_0, r) \)。这是 uniform bound 的标准技巧——远离 \( \theta_0 \) 的点，通过 Lipschitz 条件和参数空间有限直径可将 excess risk 约束为 \( O(r) \)。
  • 建立差距（gap）：对局部球域内的每个 \( \theta \)，使用 Catoni 估计量构造 \( \widehat{R}_n(\theta) \) 并定义“稳健偏差” \( \Delta_n(\theta) = \widehat{R}_n(\theta) - R(\theta) \)。证明：在 \( n \) 充分大时，\( \Delta_n(\theta) \) 以高概率一致地小（均匀逼近）。

  • 用 generalized chaining 控制 \( \sup_{\theta \in B(\theta_0, r)} |\Delta_n(\theta)| \)：这是最关键的一步。由于 \( \widehat{R}_n(\theta) \) 是隐式定义的方程解，不是简单的样本均值，其随机性来自于经验过程 \( \{ \sum_{i=1}^n \rho( (\ell(\theta, X_i) - \widehat{R}_n(\theta))/\psi ) \} \)。论文通过隐函数定理将 \( \Delta_n(\theta) \) 线性化为 \( \frac{\psi}{n} \sum_{i=1}^n \rho'(\cdots) \cdot (\ell(\theta, X_i) - R(\theta)) \) 加上高阶余项（被证明为一致可忽略），再利用经典 chaining 界处理线性部分。

  • 关键跳跃点：

  • 定理 2 中的余项控制：隐函数定理的泰勒展开的高阶项处理。条件 \( \rho'' \) 有界且矩阶数 \( (1+\varepsilon) \) 确保余项以速率 \( O(n^{-2\varepsilon/(1+\varepsilon)}) \) 消失，这需要利用 von Bahr & Esseen 矩不等式（对 sum of centered heavy-tailed r.v. 的 Lp 界）。这是本文不同于经典 Catoni 线性部分的原因。

  • Generalized chaining 的适应：经典 chaining 子类限于期望在 sup-norm 下均匀有界，这里需处理 Catoni 估计量引起的变换后的过程。论文引入了一个针对 “Catoni-type influence function” 的线性化后的过程，然后对线性过程直接运用 chaining。严格证明线性化误差一致小需要 离差不等式（deviation inequality） 在矩缺失下的推广。

  • 技术技巧点名：

  • Catoni 影响函数（ρ）：构造稳健估计量。
  • Generalized generic chaining：用于控制线性化后的经验过程的上确界。
  • 隐函数定理 + Taylor 展开：将非线性的 Catoni 估计问题线性化。
  • von Bahr & Esseen 不等式：处理重尾线性组合的 p 阶矩（p = 1+ε）。
  • Lipschitz 参数空间 covering number 假设：保证 chaining 树的根长有限。

真实例子与应用

本文为纯理论 + 模拟研究，无真实数据例子。

数值实验部分包括： - 模拟数据：设定参数空间为有限维（例如线性回归 \( \ell(\theta, X) = (y - \theta^T x)^2 \) 且 \( y \) 服从 Pareto 分布），比较三种方法： 1. Catoni-ERM（本文）：先用 Catoni 稳健估计每个 θ 的风险值，再最小化。 2. Truncation-ERM：先对样本按某个分位数截断，再运行经典 ERM。 3. Oracle ERM（若有真实风险）。 - 结果：在重尾程度很重的设定（ε → 0）下，Catoni-ERM 的 excess risk 显著低于 Truncation-ERM。在中等重尾（ε = 0.5 左右）二者较接近。 - 举例意图：验证理论的预测——截断法引入的偏差会损害下游优化，而 Catoni 方法直接对原始风险做稳健估计，避免了这个偏差。

🔎 结论是否比证明窄

  • 显著窄的地方：论文的主要 theorem（Thm 2）的速率 \( n^{-\varepsilon/(2(1+\varepsilon))} \) 是在参数空间度量熵为多项式增长（\( \log N(\Theta, \delta) \lesssim \delta^{-d} \)）下得到的。但对很多实际非参数模型（如 Hölder 球），其 metric entropy 是指数形式的（\( \log N(\Theta, \delta) \lesssim \delta^{-d/p} \)）。论文在 Theorem 2 的陈述中 没有显式写出该假设，仅在证明中用到。这导致声称的优化速率仅适用于有限维或“不太大”的参数空间，但作者在结论的讨话里未明确限定。建议研究者查看 Theorem 2 的陈述中是否含“假设 ℓ 满足 Lipschitz 且 Θ 的 covering number 具有多项式增长”。
  • 另一个窄化：算法分析（robust gradient descent）的收敛性假设目标函数强凸。这对很多实际 ERM 任务不成立（如神经网络等高非凸）。作者提到“we leave the case where R is not strongly convex for future work”，但在结论段落未强调此局限。

四、开放问题（点到为止）

  1. 非凸与非强凸情况（定理 3 的局限）：论文在优化方面的理论只适用于强凸目标函数。能否拓展到非凸（如神经网络）的稳健优化？（见原文 Theorem 3 假设段）
  2. 最优性的检验：文中 excess risk 的上界速率 \( n^{-\varepsilon/(2(1+\varepsilon))} \) 是否是与 minimax 最优的精确匹配？这需要下界论证，论文未做。研究者可用自己的 minimax 下界武器直接检验（特别是对于 Hölder 类参数空间）。
  3. 高维正则化：如果参数空间 Θ 高维（p >> n），如何在重尾下进行正则化？Catoni 方法与 lasso 等稀疏惩罚结合的理论数学尚未建立，仅含糊提及“future work”。（见 Conclusion 段）
  4. 高阶 U-统计量的稳健估计：论文只处理了最简单的 i.i.d. 损失（经验风险是 n 个独立项的和）。对于需用 U-统计量（如成对损失、高阶 interaction）的 ERM，Catoni 估计如何推广？这是一个自然的开放性扩展，且直接连接到你的 U-statistic / tensor-network 兴趣。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论