Minimax Rates of Convergence for Nonparametric Regression Under Adversarial Attacks¶
作者: Jingfu Peng, Yuhong Yang
来源: Statistica Sinica
主题: 非参数 / 半参数
相关性: 8/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么： 这个子方向研究的是：当统计估计的输入数据遭受敌手刻意构造的微小扰动时，非参数估计的极小风险下界会恶化到什么程度。它把经典非参数统计中的 minimax 收敛速率理论，与机器学习中对抗鲁棒性理论结合，试图回答一个根本问题——在敌手按某种范数（如 sup-norm）修改输入的前提下，任何统计方法所能达到的最优收敛速率是否存在一个可解析表达的“惩罚项”，以及这个惩罚项的结构是什么。当前该方向处于早期理论建构阶段：已有零散工作给出特定模型（如线性回归、参数模型）下的速率或下界，但非参数设定下的一般性速率分解公式与可达性证明刚刚出现。
发展脉络： 1. 奠基工作（参数 / 线性设定下的对抗风险）：早期工作主要在参数模型或线性回归中刻画对抗扰动的影响。例如，Javanmard & Soltanolkotabi (2020) 与 Hassani & Javanmard (2022) 针对线性回归与 logistic 回归，给出了对抗设定下 excess risk 的精确阶或 minimax rate。这些工作确立了“对抗风险 = 标准风险 + 扰动导致的线性/非线性偏差”这一加法结构在参数设定下的存在性，但留下的口子是：非参数函数类（如 Hölder 类）下，函数的无界性与局部曲率使得偏差项不再能简单表为参数范数与扰动半径的乘积，速率结构是否仍保持加法形式未知。 2. 主要进展（对抗估计的一般框架与下界）：随后工作试图将对抗风险形式化。例如，Ribeiro et al. (2020) 提出了 adversarial risk 的严格定义（敌手在约束集内选取扰动以最大化损失），并讨论了其与标准风险的关系；Pydi & Jog (2021) 在分类设定下给出了对抗 Bayes risk 的下界。这些工作留下的口子是：下界往往只针对特定损失（如 0-1 损失）或特定分布假设，且未给出与标准 minimax rate 的显式数值连接，更未构造能达到下界的估计量。 3. 当前 frontier（非参数设定下的极小极大速率）：本文作者在 intro 中明确指出，当前文献在非参数回归的对抗 minimax rate 上存在空白——既没有一般性的速率表达式，也没有证明可达性的统一构造。作者引用了上述参数设定工作，并指出非参数设定下敌手扰动导致的偏差依赖于函数类的局部振荡性质，而非全局参数范数，因此需要新的分析。 4. 本文的位置：本文填补了上述空白，给出了非参数回归在对抗 sup-norm 扰动下 minimax rate 的显式分解公式（标准速率 + 函数类在扰动下的最大偏差），并证明该速率可通过“对抗性 plug-in 程序”达到。
子线索聚类： - 线索 A：参数 / 线性模型的对抗 minimax 理论（Javanmard & Soltanolkotabi 2020, Hassani & Javanmard 2022）：在强凸或线性设定下，对抗 minimax rate 可表为“标准速率 + \(\epsilon \cdot\) 参数范数”的加法形式，偏差项与参数空间直径直接挂钩。 - 线索 B：对抗风险的形式化与 Bayes 风险下界（Ribeiro et al. 2020, Pydi & Jog 2021）：侧重于定义对抗风险并给出分类设定下的 Bayes 下界，但未触及非参数回归的收敛速率与可达性。 - 线索 C：非参数统计的 minimax 速率经典理论（如 Stone 1982, Tsybakov 2009）：本文的基准线，标准设定下 Hölder 类等的 minimax rate 已有完备结论，本文在此基础上叠加对抗扰动。
这个方向在追问的核心问题： 1. 非参数设定下，对抗 minimax rate 是否仍具有加法结构（标准速率 + 扰动偏差）？偏差项的具体表达式是什么？ 2. 达到对抗 minimax rate 的估计量是否需要全新构造，还是可以直接从标准 minimax optimal estimator 出发进行修正？ 3. 扰动范数的选择（sup-norm vs. \(L_p\)-norm）如何改变偏差项的结构与速率阶？
当前主流方法与已知瓶颈： 主流方法是在参数设定下推导 excess risk 或 minimax rate 的加法分解，瓶颈在于非参数函数类的局部振荡性质使得偏差项无法用全局参数（如半径）刻画，必须引入函数类在扰动半径下的最大函数值差（即本文定义的 \(\Delta(\epsilon, \mathcal{F})\)），且 sup-norm 扰动下该偏差项可能随 \(\epsilon\) 增长极快（如 Hölder 类下为 \(\epsilon^{\alpha}\)），导致对抗速率可能被偏差项主导、而非标准估计误差主导。
⚠️ 作者的 framing（这是作者的说法）： 作者把缺口 frame 为“非参数回归下对抗 minimax rate 的一般性表达式与可达性尚未建立”，并强调参数设定下的加法结构在非参数下是否成立是未知的。这使得本文的“加法分解 + plug-in 可达性”成为“显然的下一步”。 被淡化或回避的竞争路线：intro 中未提及 \(L_p\)-norm（\(p < \infty\)）扰动下的 minimax rate 问题——sup-norm 扰动是最严苛的敌手约束，偏差项最大；若敌手受 \(L_2\) 约束，偏差项可能更小甚至消失（如 Lipschitz 类下 \(L_2\) 扰动偏差可被积分平滑掉），速率结构可能不再是简单加法。作者也未讨论随机扰动与对抗扰动的速率差异。 明显该被引却未出现的：关于 distributionally robust optimization (DRO) 或 Wasserstein robustness 的 minimax 理论工作（如 Sinha et al. 2018, Blanchet & Murthy 2019）——这些工作在分布扰动而非输入扰动下给出了类似的风险分解，且其偏差项涉及函数类在 Wasserstein 球内的振荡，与本文的 sup-norm 扰动偏差有结构相似性。作者未引用它们，可能是因为本文严格限定在“输入扰动”而非“分布扰动”，但这两者的数学结构高度同源，值得研究者去查。
张力： 未见明显对立引用。参数设定下的工作（线索 A）与本文的非参数结论在“加法结构”上是一致的，但偏差项的刻画方式不同（参数范数 vs. 函数类局部振荡），这不算矛盾，而是不同设定下的不同表达。
二、最核心、最简单的例子 / 数学问题¶
第一步：符号、模型、可观测数据交代清楚
- \(X\)：输入变量，取值于 \(\mathcal{X} \subset \mathbb{R}^d\)。
- \(Y\)：响应变量，取值于 \(\mathbb{R}\)。
- \(f\)：真实回归函数，\(f \in \mathcal{F}\)（目标函数类），\(Y = f(X) + \xi\)，其中 \(\xi\) 为噪声，假设 \(\mathbb{E}[\xi | X] = 0\)，\(\xi\) 有有限方差。
- \(\mathcal{F}\)：非参数函数类，本文主要考虑 Hölder 类 \(\mathcal{H}(\alpha, L)\)（光滑度 \(\alpha > 0\)，Lipschitz 常数 \(L\)）。
- \(\epsilon\)：敌手扰动半径，\(\epsilon > 0\)，敌手可在 sup-norm 约束 \(\|u\|_\infty \leq \epsilon\) 下选择扰动 \(u \in \mathbb{R}^d\)。
- \(\Delta(\epsilon, \mathcal{F})\)：函数类 \(\mathcal{F}\) 在扰动半径 \(\epsilon\) 下的最大函数值偏差，定义为 \(\Delta(\epsilon, \mathcal{F}) = \sup_{f \in \mathcal{F}} \sup_{x \in \mathcal{X}} \sup_{\|u\|_\infty \leq \epsilon} |f(x+u) - f(x)|\)。这是本文的核心新数量。
- \(n\)：样本量。
- \((X_i, Y_i), i=1,\ldots,n\)：可观测的 i.i.d. 样本，来自模型 \(Y_i = f(X_i) + \xi_i\)。注意：敌手扰动作用于估计阶段的输入（即对测试点或估计量输入施加扰动），而非训练样本的生成过程——训练数据是未被扰动的。
- \(\hat{f}_n\)：基于样本 \((X_i, Y_i)\) 构造的回归函数估计量。
- \(R_A(\hat{f}_n, f, \epsilon)\)：对抗 sup-norm 风险，定义为 \(\sup_{\|u\|_\infty \leq \epsilon} \mathbb{E}_{X}[(\hat{f}_n(X+u) - f(X))^2]\)（或类似形式，敌手选 \(u\) 以最大化期望平方误差）。这是本文要最小化的目标。
- \(R_S(\hat{f}_n, f)\)：标准风险（无扰动），\(\mathbb{E}_{X}[(\hat{f}_n(X) - f(X))^2]\)。
- \(\mathcal{R}_A^*(n, \mathcal{F}, \epsilon)\)：对抗 minimax rate，\(\inf_{\hat{f}_n} \sup_{f \in \mathcal{F}} R_A(\hat{f}_n, f, \epsilon)\)。
- \(\mathcal{R}_S^*(n, \mathcal{F})\)：标准 minimax rate，\(\inf_{\hat{f}_n} \sup_{f \in \mathcal{F}} R_S(\hat{f}_n, f)\)。
第二步：最小内核——\(d=1\)、Hölder 类 \(\mathcal{H}(\alpha, L)\)、sup-norm 扰动下的速率分解
剥掉所有一般性设定，考虑最简特例：\(d=1\)，\(\mathcal{X} = [0,1]\)，\(\mathcal{F} = \mathcal{H}(\alpha, L)\)（\(\alpha\)-阶 Hölder 连续函数类），敌手扰动半径 \(\epsilon\)，噪声 \(\xi\) 为高斯且方差 \(\sigma^2\)。
在这个特例下，本文要证的核心命题退化成：
为什么成立？直觉与证明骨架： 1. 偏差项 \(\epsilon^{2\alpha}\) 的来源：对 Hölder 类 \(\mathcal{H}(\alpha, L)\)，由定义有 \(|f(x+u) - f(x)| \leq L |u|^\alpha\)（当 \(\alpha \leq 1\) 时；\(\alpha > 1\) 时涉及导数，但局部振荡仍受 \(\epsilon^\alpha\) 控制）。因此 \(\Delta(\epsilon, \mathcal{H}(\alpha, L)) \leq L \epsilon^\alpha\)。敌手选 \(u\) 使得 \(|u| = \epsilon\)，可将估计量在 \(x+u\) 处的预测偏离真值 \(f(x)\) 至多 \(L\epsilon^\alpha\)。平方后，偏差贡献为 \((L\epsilon^\alpha)^2 = L^2 \epsilon^{2\alpha}\)。这是敌手能制造的最坏偏差，任何估计量都无法避免（因为敌手总能在测试点附近找到使函数值跳变 \(\asymp \epsilon^\alpha\) 的 \(f\)）。 2. 加法结构的证明： - 下界：取两个函数 \(f_0, f_1 \in \mathcal{H}(\alpha, L)\)，使得 \(f_1(x) = f_0(x) + c n^{-\alpha/(2\alpha+1)} \phi(x)\)（局部 perturbation，\(\phi\) 为 bump function），这是标准 minimax 下界的构造（Fano's lemma 或 Le Cam）。在对抗设定下，敌手可进一步在测试点 \(x\) 处施加扰动 \(u\)，使得 \(f_0(x+u)\) 与 \(f_1(x+u)\) 的差从 \(c n^{-\alpha/(2\alpha+1)} \phi(x)\) 扩大为 \(c n^{-\alpha/(2\alpha+1)} \phi(x) + \Delta(\epsilon, \mathcal{H})\) 的量级（敌手选 \(u\) 使 \(f_0\) 与 \(f_1\) 在 \(x+u\) 处的差最大化）。由此，对抗风险的下界为标准下界 \(n^{-2\alpha/(2\alpha+1)}\) 与偏差下界 \(\epsilon^{2\alpha}\) 之和。 - 上界（可达性）：取标准 minimax optimal estimator \(\hat{f}_n^*\)（如局部多项式估计），构造对抗性 plug-in 估计量 \(\hat{f}_n^A(x) = \hat{f}_n^*(x)\)（即不做任何修正！）。其对抗风险为 \(\sup_{\|u\|_\infty \leq \epsilon} \mathbb{E}[(\hat{f}_n^*(x+u) - f(x))^2]\)。展开平方：\((\hat{f}_n^*(x+u) - f(x+u) + f(x+u) - f(x))^2 = (\hat{f}_n^*(x+u) - f(x+u))^2 + (f(x+u) - f(x))^2 + 2(\hat{f}_n^*(x+u) - f(x+u))(f(x+u) - f(x))\)。第一项的期望由 \(\hat{f}_n^*\) 的标准 minimax 性质控制（阶为 \(n^{-2\alpha/(2\alpha+1)}\)）；第二项由 Hölder 性质控制（阶为 \(\epsilon^{2\alpha}\)）；第三项由 Cauchy-Schwarz 控制为前两项的乘积的根号，阶低于加法主项。因此上界亦为 \(n^{-2\alpha/(2\alpha+1)} + \epsilon^{2\alpha}\)。
核心思路：对抗 minimax rate = 标准 minimax rate + 函数类在扰动下的最大平方偏差。证明的关键跳跃在于：不需要构造新的对抗鲁棒估计量，标准 minimax optimal estimator 直接就是对抗 minimax optimal estimator——敌手造成的偏差是任何估计量都无法消除的“硬壁”，而标准最优估计量在偏差存在时仍保持其估计误差的最优性，因此加法结构自然成立。
三、这篇论文做了什么¶
三句话： ①研究了非参数回归在输入遭受对抗性 sup-norm 扰动时的 minimax 收敛速率。 ②核心工具是风险分解（对抗风险 = 标准风险 + 扰动偏差）与标准 minimax optimal estimator 的直接继承。 ③主要结论是：对抗 minimax rate 等于标准 minimax rate 与函数类最大平方偏差 \(\Delta^2(\epsilon, \mathcal{F})\) 之和，且该速率可通过对抗性 plug-in 程序（直接取标准最优估计量）达到。
关键设定与假设： - 设定：非参数回归模型 \(Y = f(X) + \xi\)，\(f \in \mathcal{F}\)，\(\xi\) 为零均值、有限方差噪声，\((X_i, Y_i)\) i.i.d.。 - 对抗风险定义：\(R_A(\hat{f}_n, f, \epsilon) = \sup_{\|u\|_\infty \leq \epsilon} \mathbb{E}_{X}[(\hat{f}_n(X+u) - f(X))^2]\)。注意敌手扰动 \(u\) 作用于估计量的输入（测试点），真值 \(f(X)\) 不受扰动——这对应“敌手攻击预测阶段”的现实场景。 - 函数类假设：本文主要考虑两类： 1. Hölder 类 \(\mathcal{H}(\alpha, L)\)：\(\alpha\)-阶光滑，Lipschitz 常数 \(L\)。此时 \(\Delta(\epsilon, \mathcal{H}(\alpha, L)) \asymp \epsilon^\alpha\)。 2. 有界变差类或更一般的非参数类（文中提及但未作为主例）。 - 分布假设：\(X\) 的分布 \(P_X\) 在 \(\mathcal{X}\) 上有密度且支撑集满足一定条件（如边界光滑，确保扰动后 \(X+u\) 仍在支撑集内或概率可控）。 - 噪声假设：\(\xi\) 的条件方差有界，\(\text{Var}(\xi | X) \leq \sigma^2\)。 - 与已有文献的对比：相比参数设定下的工作（Javanmard & Soltanolkotabi 2020），本文的偏差项 \(\Delta(\epsilon, \mathcal{F})\) 依赖于函数类的局部振荡而非全局参数范数，这是非参数设定下的新结构；相比 DRO 文献（未引用），本文的扰动作用于输入而非分布，偏差项是 sup-norm 下的最大函数值差而非 Wasserstein 距离下的积分偏差。
主要结果：
定理 1（对抗 minimax rate 的加法分解）：
定理 2（对抗性 plug-in 程序的可达性）： 设 \(\hat{f}_n^*\) 为标准设定下的 minimax optimal estimator（即 \(R_S(\hat{f}_n^*, f) \leq C \mathcal{R}_S^*(n, \mathcal{F})\) 对所有 \(f \in \mathcal{F}\)）。则对抗性 plug-in 估计量 \(\hat{f}_n^A(x) = \hat{f}_n^*(x)\) 满足：
实例 1（Hölder 类）： 对 \(\mathcal{F} = \mathcal{H}(\alpha, L)\)，\(\mathcal{X} = [0,1]^d\)，有：
实例 2（文中另一函数类，如单调函数类或更一般类）： 对单调函数类或具有特定振荡性质的类，\(\Delta(\epsilon, \mathcal{F})\) 的阶可能不同于 \(\epsilon^\alpha\)（如单调类下 \(\Delta\) 可能与 \(\epsilon\) 成线性关系），此时对抗速率的偏差项相应变化。文中给出此例以说明 \(\Delta(\epsilon, \mathcal{F})\) 的表达式需针对具体函数类计算。
证明路线与技术技巧：
整体路线（下界）： 1. 构造两个函数 \(f_0, f_1\)：在标准 minimax 下界构造的基础上（如局部 bump perturbation），使得 \(f_0\) 与 \(f_1\) 在无扰动时难以区分（距离 \(\asymp n^{-\alpha/(2\alpha+d)}\)）。 2. 引入敌手扰动：敌手选 \(u\) 使 \(f_0(x+u)\) 与 \(f_1(x+u)\) 的差最大化，利用 \(\Delta(\epsilon, \mathcal{F})\) 的定义，确保扰动后两函数在测试点的差至少为 \(\Delta(\epsilon, \mathcal{F})\) 的量级。 3. 应用 Fano's lemma 或 Le Cam 方法：在扰动后的分布下计算估计量区分 \(f_0\) 与 \(f_1\) 的难度，得出对抗风险下界 \(\geq c_1 \mathcal{R}_S^*(n, \mathcal{F}) + c_2 \Delta^2(\epsilon, \mathcal{F})\)。
整体路线（上界 / 可达性）： 1. 取标准 minimax optimal estimator \(\hat{f}_n^*\)（如局部多项式、核估计）。 2. 展开对抗风险：\((\hat{f}_n^*(x+u) - f(x))^2 = (\hat{f}_n^*(x+u) - f(x+u))^2 + (f(x+u) - f(x))^2 + 2(\hat{f}_n^*(x+u) - f(x+u))(f(x+u) - f(x))\)。 3. 控制三项：第一项由 \(\hat{f}_n^*\) 的标准 minimax 性质控制（阶 \(\mathcal{R}_S^*\)）；第二项由 \(\Delta^2(\epsilon, \mathcal{F})\) 控制；第三项由 Cauchy-Schwarz 控制为前两项乘积的根号，阶低于加法主项。 4. 取 sup over \(u\)：由于 \(\hat{f}_n^*\) 的风险在 \(x+u\) 处的一致性（或局部性质），sup 不恶化阶。
关键跳跃点： - 下界中估计误差与敌手偏差的叠加：需证明敌手扰动不会使标准下界构造失效（即扰动后 \(f_0\) 与 \(f_1\) 在样本分布上仍难以区分，但在测试点风险上差增大）。这是通过将扰动作用于测试点而非训练点实现的——训练数据分布不变，标准下界构造仍适用；敌手只在风险评估阶段制造偏差。 - 上界中 \(\hat{f}_n^*(x+u)\) 的风险控制：需证明标准最优估计量在扰动输入 \(x+u\) 处的风险不恶化。这依赖于 \(\hat{f}_n^*\) 的风险在 \(x\) 附近的一致性（如核估计在局部邻域内的风险一致有界），或整体风险的期望形式天然包含对 \(x\) 的积分从而平滑掉局部扰动。
技术技巧点名： - Fano's lemma / Le Cam method：用于下界构造，计算区分两个相近函数的难度。 - Cauchy-Schwarz 分解：用于上界展开，将对抗风险分解为估计误差与敌手偏差的加法结构，交叉项被控制为低阶。 - 局部 bump perturbation 构造：标准 minimax 下界的经典工具，构造 \(f_1 = f_0 + c n^{-\alpha/(2\alpha+d)} \phi\)。 - 函数类振荡量 \(\Delta(\epsilon, \mathcal{F})\) 的计算：针对 Hölder 类，利用光滑度定义直接得 \(\Delta \leq L \epsilon^\alpha\)；针对其他类需具体分析。
真实例子与应用： 本文为纯理论工作，无真实数据例子或模拟实验。文中给出的“实例”是具体的函数类（Hölder 类、单调类）下的速率计算，属于理论特例而非实证应用。
🔎 结论是否比证明窄： 本文的定理陈述在一般函数类 \(\mathcal{F}\) 下给出加法分解，但证明中上界的可达性依赖于“标准 minimax optimal estimator \(\hat{f}_n^*\) 在扰动点 \(x+u\) 处的风险仍受 minimax rate 控制”这一条件。文中未显式陈述此条件为独立假设，而是隐含在“取标准最优估计量即可”的论证中。对于某些函数类或估计量，此条件可能不成立（如估计量在边界点附近风险恶化，而敌手恰好将测试点推向边界），此时对抗性 plug-in 程序可能不达上界。文中在分布假设中要求支撑集边界光滑以规避此问题，但未在定理陈述中显式标注此依赖。研究者需核查定理 2 的证明细节，确认“\(\hat{f}_n^*\) 在扰动点风险不恶化”是否需要额外假设（如估计量的局部一致性或支撑集的内点条件）。
四、开放问题（点到为止，扎根具体语句）¶
- \(L_p\)-norm 扰动（\(p < \infty\)）下的 minimax rate：本文严格限定在 sup-norm 扰动（\(p=\infty\)），此时偏差项 \(\Delta(\epsilon, \mathcal{F})\) 为最大局部振荡。若敌手受 \(L_2\) 约束，偏差项可能涉及函数类在 \(L_2\) 球内的平均振荡（如 \(\sup_f \mathbb{E}_X[\sup_{\|u\|_2 \leq \epsilon} (f(X+u) - f(X))^2]\)），速率结构可能不再是简单加法。扎根点：intro 中仅提及 sup-norm，未讨论 \(L_p\) 扰动，且定理 1 的 \(\Delta\) 定义依赖 sup-norm。
- 训练数据亦受扰动的设定：本文假设训练数据未被扰动，敌手仅攻击测试点。若敌手亦可在训练阶段注入扰动（即 \((X_i + u_i, Y_i)\) 可观测），则样本分布改变，标准 minimax 下界构造失效，需新的下界工具。扎根点：intro 中明确假设“敌手扰动作用于估计阶段的输入”，未讨论训练扰动。
- 分布扰动（Wasserstein / DRO）与输入扰动的速率统一：本文的 \(\Delta(\epsilon, \mathcal{F})\) 与 DRO 文献中函数类在 Wasserstein 球内的振荡有结构相似性，但本文未引用 DRO 工作，也未讨论两者是否可统一为更一般的“扰动 minimax 理论”。扎根点：intro 缺少 DRO 引用，且定理 1 的加法分解是否在分布扰动下仍成立未探。
- 高维设定下偏差项的主导性：对 Hölder 类 \(\mathcal{H}(\alpha, L)\) 在 \(d\) 维时，标准速率 \(n^{-2\alpha/(2\alpha+d)}\) 随 \(d\) 指数恶化，而偏差项 \(\epsilon^{2\alpha}\) 与 \(d\) 无关。当 \(d\) 大且 \(\epsilon\) 不极小时，偏差项主导速率，此时“对抗鲁棒性”几乎无统计意义（速率被敌手偏差锁定）。扎根点：实例 1 的速率表达式中 \(n^{-2\alpha/(2\alpha+d)} + \epsilon^{2\alpha}\)，当 \(d \to \infty\) 时偏差项主导，文中未讨论此情形下的统计-计算权衡或是否需降维。
要确认某条是否真 gap，建议读同子领域近期约 5 篇的 intro——若都指向“\(L_p\) 扰动 / 训练扰动 / DRO 统一”则为共识真 gap，若互相打架则为机会。
Maintained by 陈星宇 · Homepage · Source on GitHub