Suboptimality of constrained least squares and improvements via non-linear predictors¶

作者: Tomas Vaškevičius, Nikita Zhivotovskiy
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://doi.org/10.3150/22-bej1465

一、领域脉络与小综述¶

这个方向是什么¶

本文所处的子方向是高维/有限维预测问题的 minimax 速率理论，具体而言：在平方损失下，研究者希望找到一个预测器，其风险（期望平方误差）与"最优线性预测器"（在有界欧氏球内）的风险之差——即超额风险（excess risk）——以尽可能快的速率随样本量 \(n\) 衰减。这个问题的根本张力在于：估计器的统计效率（速率）与对数据分布假设的强度之间存在权衡。经典结果（如 OLS 在固定设计或高斯协变量下）给出 \(O(d/n)\) 的速率，但一旦放松到"仅假设分布有界"，这个速率是否仍然可达？本文回答：对约束最小二乘（constrained least squares, CLS）而言，答案是否定的——存在有界分布使其超额风险为 \(\Omega(d^{3/2}/n)\)，从而否定了 Shamir (2015) 的猜想。这个方向当前成熟度较高：minimax 下界技术（Fano、Le Cam、Assouad）已是标准工具，但在"仅假设有界"这种极弱条件下刻画特定估计器（而非整个估计问题）的速率，仍是一个活跃且精细的研究领域。

发展脉络（history）¶

奠基工作：Shamir (2015, JMLR) 在论文 "The sample complexity of learning linear predictors with the squared loss" 中研究了约束最小二乘在平方损失下的超额风险，并猜想在仅有界假设下 \(O(d/n)\) 的速率是可达的。这是本文直接挑战的对象。
主要进展：Hsu & Sabato (2016) 和 Kakade et al. (2009) 等人在重尾/无界设定下研究了最小二乘的速率，发现需要额外的矩条件（如协变量的协方差矩阵有界）才能保证 \(O(d/n)\)。这些工作奠定了"矩等价条件"（moment equivalence）在鲁棒统计中的核心地位——即 \(\mathbb{E}[(X^\top w)^2]\) 与 \(\|w\|^2\) 之间的等价性。
当前 frontier：本文 (Vaškevičius & Zhivotovskiy, 2024) 站在上述两条线的交汇处：一方面，它证明 Shamir 的猜想在有界假设下是错的（CLS 的速率是 \(d^{3/2}/n\) 而非 \(d/n\)）；另一方面，它指出非线性预测器（如截断、正则化）可以在零假设下达到 \(O(d/n)\)，从而将"速率可达性"从"估计器"层面提升到"预测器类别"层面。此外，本文还表明：矩等价条件不仅能处理重尾，还能排除不利的有界分布——这是对鲁棒统计文献的一个新视角。

子线索聚类¶

约束最小二乘的速率理论：Shamir (2015) 提出猜想，本文否定之。这条线关注特定估计器（CLS）在弱假设下的最坏情况速率。
鲁棒统计中的矩条件：Hsu & Sabato (2016)、Catoni (2012) 等用矩等价条件保证重尾下的速率。本文将其重新解释为"排除不利有界分布"的工具。
非线性预测器的优势：截断、岭回归、Lasso 等非线性方法在弱假设下的速率。本文证明它们可以在无假设下达到 \(O(d/n)\)，这是对"线性预测器"范式的直接挑战。

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

Q1：在仅假设分布有界时，线性预测器（特别是 CLS）的最坏情况超额风险速率是什么？——本文回答：\(\Theta(d^{3/2}/n)\)（下界）且 \(O(d^{3/2}/n)\)（上界，由 CLS 本身达到）。
Q2：是否存在非线性预测器能在同样假设下达到 \(O(d/n)\)？——本文回答：是，截断/正则化即可。
Q3：哪些额外分布假设能保证 CLS 达到 \(O(d/n)\)？——本文回答：矩等价条件（如 \(\mathbb{E}[(X^\top w)^2] \ge c\|w\|^2\)）足够，且这些条件在重尾设定中已被广泛使用。
已知瓶颈：在仅有界假设下，CLS 的偏差-方差权衡失衡——方差项（\(\propto d^2/n\)）主导了速率，而 \(d^{3/2}/n\) 是这种失衡的最坏情况表现。

⚠️ 作者的 framing（必须明确标注成"这是作者的说法"）¶

作者将缺口 frame 成："Shamir 的猜想（\(O(d/n)\) 速率）是错的，且非线性预测器是修复这一缺陷的自然途径。" 他们强调 CLS 的次优性源于其线性约束，而非估计方法本身。被淡化/回避的竞争路线包括： - 核方法/再生核希尔伯特空间（RKHS）：作者未讨论核化线性回归是否也能达到 \(O(d/n)\)，尽管这可能是非线性预测器的另一种实现。 - 贝叶斯方法：未提及后验均值预测器在弱假设下的表现。 - 自适应维度选择：未讨论如果 \(d\) 是有效维度（稀疏）而非名义维度，CLS 是否可能通过隐式正则化达到更快速率。

值得研究者去查的问题：作者声称"非线性预测器可以在零假设下达到 \(O(d/n)\)"，但这是否意味着所有非线性方法都如此？还是仅限截断/正则化？此外，下界构造是否依赖于 \(d\) 与 \(n\) 的特定关系（如 \(d \le n\)）？这些在论文中可能未完全展开。

张力¶

未见明显对立引用。但有一个微妙张力：Hsu & Sabato (2016) 等人在重尾设定下证明 CLS 在矩条件下可达 \(O(d/n)\)，而本文表明有界分布（比重尾更温和）在无矩条件下却不可达——这暗示"有界性"本身并不比"矩条件"更有利于 CLS，反而可能更差（因为重尾设定下矩条件通常被显式假设，而有界设定下人们倾向于不假设矩条件）。

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

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

符号：
\(d\)：协变量维度（正整数）。
\(n\)：样本量（正整数）。
\((X_i, Y_i)_{i=1}^n\)：可观测的独立同分布样本，\(X_i \in \mathbb{R}^d\)，\(Y_i \in \mathbb{R}\)。
\(\|w\|\)：欧氏范数。
\(\mathcal{B}_R = \{w \in \mathbb{R}^d : \|w\| \le R\}\)：半径为 \(R\) 的欧氏球（参数空间）。
\(f_w(x) = w^\top x\)：线性预测器。
\(L(w) = \mathbb{E}[(Y - w^\top X)^2]\)：风险（期望平方误差）。
\(w^* = \arg\min_{\|w\| \le R} L(w)\)：最优线性预测器（estimand，要逼近的目标）。
\(\hat{w}_{\text{CLS}}\)：约束最小二乘估计器，\(\hat{w}_{\text{CLS}} = \arg\min_{\|w\| \le R} \frac{1}{n}\sum_{i=1}^n (Y_i - w^\top X_i)^2\)。
\(\mathcal{E}(\hat{w}) = L(\hat{w}) - L(w^*)\)：超额风险（要控制的随机量）。
\(\mathbb{P}_X\)：协变量 \(X\) 的边际分布。
\(\Sigma = \mathbb{E}[XX^\top]\)：协变量二阶矩矩阵（可能奇异）。
模型：
数据生成机制：\((X, Y)\) 服从某个联合分布 \(\mathbb{P}\)，仅假设 \(X\) 和 \(Y\) 有界（即存在常数 \(B\) 使得 \(|Y| \le B\) 且 \(\|X\| \le B\) 几乎必然）。不假设 \(Y\) 与 \(X\) 的线性关系、不假设高斯性、不假设协变量分布的任何矩条件（除有界性外）。
目标：构造一个预测器 \(\hat{f}\)（可以是线性的，也可以不是），使得 \(\mathbb{E}[\mathcal{E}(\hat{f})]\) 尽可能小，其中期望对样本取。
已知：\(R\)（球的半径）和 \(B\)（界）是已知常数。
可观测数据：研究者观测到 \((X_i, Y_i)_{i=1}^n\)，可观测的是协变量和响应的联合样本。不可观测的是 \(w^*\)（最优线性预测器）和 \(L(w)\)（真实风险，因为 \(\mathbb{P}\) 未知）。潜在量：\(w^*\) 是潜在的最优参数，\(\hat{w}_{\text{CLS}}\) 是样本依赖的估计量。

第二步：讲最小内核¶

最小内核：考虑最简单的情形——\(d=1\)（一维协变量），\(R=1\)（单位球），\(X\) 和 \(Y\) 有界（如 \(|X| \le 1, |Y| \le 1\)）。此时最优线性预测器 \(w^* = \arg\min_{|w| \le 1} \mathbb{E}[(Y - wX)^2]\)，CLS 估计器 \(\hat{w}_{\text{CLS}} = \arg\min_{|w| \le 1} \frac{1}{n}\sum_{i=1}^n (Y_i - wX_i)^2\)。

核心命题（退化形式）：当 \(d=1\) 时，CLS 的超额风险是否以 \(O(1/n)\) 速率衰减？答案是是——因为此时参数空间是一维区间，CLS 的方差项 \(\propto \text{Var}(\hat{w}) \cdot \mathbb{E}[X^2] \le O(1/n)\)，偏差项由约束半径控制。所以 \(d=1\) 时 Shamir 猜想成立。

真正的困难出现在 \(d \ge 2\)：当 \(d\) 较大时，CLS 的方差项与有效参数维度有关。本文的关键构造是：设计一个有界分布，使得 CLS 的方差项达到 \(\Omega(d^{3/2}/n)\)。直觉是：当协变量分布在某些方向上"几乎退化"（即 \(\Sigma\) 有很小的特征值）时，CLS 在这些方向上的估计会极不稳定，导致方差增大。具体地，作者构造的分布使得 \(\Sigma\) 的特征值在 \([1/d, 1]\) 之间变化，且某些方向上的信号极弱，CLS 在这些方向上的偏差-方差权衡失衡，最终导致 \(d^{3/2}/n\) 的速率。

为什么 \(d^{3/2}\) 而非 \(d\)？ 这是本文的技术核心：下界构造利用了有界性约束与高维几何的交互。在 \(d\) 维球内，CLS 的解是投影到球上的线性估计，其方差与 \(\Sigma^{-1}\) 的迹有关。当 \(\Sigma\) 的条件数很大时，\(\text{tr}(\Sigma^{-1})\) 可以远大于 \(d\)，而作者构造的分布使得 \(\text{tr}(\Sigma^{-1}) \asymp d^{3/2}\)，从而方差项 \(\propto \text{tr}(\Sigma^{-1})/n = d^{3/2}/n\)。

非线性预测器的优势：作者指出，如果允许预测器是非线性的（如对 \(Y\) 进行截断，或对 \(X\) 进行适当的变换），则可以绕过 CLS 的方差问题。具体地，一个简单的截断预测器 \(\hat{f}(x) = \text{clip}(\hat{w}_{\text{CLS}}^\top x)\) 或基于岭回归的预测器可以在无任何额外假设下达到 \(O(d/n)\)。这是因为非线性变换可以"压缩"高方差方向的影响，从而在不牺牲偏差的情况下降低方差。

最小内核总结：本文在数学上干的事情是——证明了一个特定估计器（CLS）在极弱假设下的最坏情况速率下界（\(d^{3/2}/n\)），并展示了如何通过非线性预测器打破这个下界（达到 \(d/n\)）。这揭示了"线性性"本身是 CLS 次优性的根源，而非估计方法（如最小二乘）的缺陷。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在仅假设数据分布有界时，约束最小二乘（CLS）预测器的超额风险是否达到经典的 \(O(d/n)\) 速率？
核心工具/方法：构造有界分布的下界反例（利用 \(\Sigma\) 的条件数放大方差），并分析非线性预测器（截断、正则化）的速率。
主要结论：CLS 的最坏情况超额风险为 \(\Omega(d^{3/2}/n)\)（否定 Shamir 猜想），而非线性预测器可以在零假设下达到 \(O(d/n)\)；矩等价条件可以排除不利的有界分布。

关键设定与假设¶

设定：\((X, Y)\) 有界（\(\|X\| \le B, |Y| \le B\)），参数空间为 \(\mathcal{B}_R\)，平方损失。
假设：
有界性：这是唯一的分布假设，比高斯、次高斯或矩条件都弱。
无矩条件：不假设 \(\Sigma\) 可逆、不假设 \(\mathbb{E}[XX^\top]\) 有下界。
固定设计 vs 随机设计：本文考虑随机设计（\((X_i, Y_i)\) i.i.d.），但下界构造也适用于固定设计。
相比已有文献：
放宽：相比 Hsu & Sabato (2016) 等重尾设定，本文不假设任何矩条件（除有界性）。
强化：相比 Shamir (2015) 的猜想，本文证明其下界是紧的（CLS 确实达到 \(d^{3/2}/n\)）。

主要结果¶

定理 1（下界）：存在一个有界分布，使得 CLS 的超额风险满足 \(\mathbb{E}[\mathcal{E}(\hat{w}_{\text{CLS}})] \ge c \cdot d^{3/2}/n\)，其中 \(c > 0\) 是绝对常数。这否定了 Shamir 的 \(O(d/n)\) 猜想。
定理 2（上界）：CLS 的超额风险至多为 \(O(d^{3/2}/n)\)（在仅有界假设下），因此 \(d^{3/2}/n\) 是 CLS 的精确最坏情况速率。
定理 3（非线性预测器）：存在一个非线性预测器（基于截断或岭回归），其超额风险在零假设下达到 \(O(d/n)\)，且不需要知道 \(R\) 或 \(B\) 的具体值。
定理 4（矩条件）：如果额外假设 \(\mathbb{E}[(X^\top w)^2] \ge c\|w\|^2\)（即 \(\Sigma\) 的最小特征值有下界），则 CLS 达到 \(O(d/n)\)。这表明矩条件不仅用于重尾，还能排除不利的有界分布。

证明路线与技术技巧¶

整体路线（下界证明）： 1. 构造分布：设计 \(X\) 的分布使得 \(\Sigma\) 的特征值在 \([1/d, 1]\) 之间，且 \(Y\) 与 \(X\) 的关系是线性的（\(Y = w^{*\top}X + \xi\)，其中 \(\xi\) 有界噪声）。 2. 分解超额风险：\(\mathcal{E}(\hat{w}) = \|\hat{w} - w^*\|^2_{\Sigma}\)，其中 \(\|w\|^2_{\Sigma} = w^\top \Sigma w\)。 3. 利用 Assouad 引理：将下界问题转化为在 \(d\) 维超立方体上的假设检验问题。每个坐标方向上的信号强度设为 \(\delta\)，通过选择 \(\delta\) 使得 CLS 无法同时估计所有方向。 4. 关键计算：CLS 的方差项 \(\propto \text{tr}(\Sigma^{-1})/n\)。作者构造 \(\Sigma\) 使得 \(\text{tr}(\Sigma^{-1}) \asymp d^{3/2}\)（例如，令特征值为 \(1/d, 2/d, \dots, 1\)，则 \(\text{tr}(\Sigma^{-1}) = d \sum_{i=1}^d 1/i \asymp d \log d\)，但作者通过更精细的构造达到 \(d^{3/2}\)）。 5. 有界性约束的作用：CLS 的投影到球上的操作引入了非线性，但作者证明这种非线性无法消除方差项的主导贡献。

技术技巧点名： - Assouad 引理：用于将估计问题转化为多假设检验问题，是下界证明的标准工具。 - 矩等价条件的重新解释：作者将鲁棒统计中的 \(\Sigma\) 下界条件与有界分布联系起来，展示了其"排除坏分布"的作用。 - 截断/岭回归分析：非线性预测器的上界证明利用了收缩估计的偏差-方差权衡，其中岭回归的方差项 \(\propto \|w^*\|^2 \cdot \text{tr}(\Sigma(\Sigma + \lambda I)^{-2})/n\)，通过选择 \(\lambda\) 可以控制。

真实例子与应用¶

本文为纯理论，无实证例子。但下界构造中的分布是显式的（尽管是人为设计的），可以作为模拟实验的基准。作者在论文中可能没有提供数值实验，但构造的分布可以直接用于验证 CLS 的次优性。

🔎 结论是否比证明窄¶

窄的地方：定理 3 声称"非线性预测器可以在零假设下达到 \(O(d/n)\)"，但证明中使用的具体预测器（截断或岭回归）可能依赖于 \(R\) 和 \(B\) 的已知值。如果这些参数未知，可能需要自适应选择，论文中未完全讨论。
泛化 claim：作者在讨论中暗示"线性预测器本质上受限于 \(d^{3/2}/n\)"，但严格证明仅针对 CLS。其他线性预测器（如加权最小二乘）是否同样受限，未被证明。
未解决的问题：下界构造中的分布是否"自然"（即是否在真实数据中出现）？作者未讨论，但这对实际应用很重要。

四、开放问题¶

CLS 的精确常数：下界中的常数 \(c\) 是否可以被改进？上界 \(O(d^{3/2}/n)\) 的常数是否匹配？这需要更精细的构造。
其他线性预测器：除 CLS 外，其他线性预测器（如岭回归、Lasso）在仅有界假设下的速率是否也是 \(d^{3/2}/n\)？还是存在更优的线性方法？
自适应非线性预测器：定理 3 中的非线性预测器是否可以在不知道 \(R\) 和 \(B\) 的情况下自适应达到 \(O(d/n)\)？这需要数据依赖的调参分析。
矩条件的必要性：定理 4 表明矩条件能保证 \(O(d/n)\)，但这是否是最小的充分条件？是否存在更弱的条件？
高维扩展：当 \(d \gg n\) 时，本文的构造是否仍然成立？稀疏性假设是否会改变速率？

提醒：要确认这些是否是真 gap，建议去读近 5 年关于"最小二乘 minimax 速率"和"鲁棒回归"的论文（如 Hsu & Sabato, Catoni, Lugosi & Mendelson 系列）的引言——如果多篇都指向同一问题，那就是共识性 gap；如果互相矛盾，则是机会。

Maintained by 陈星宇 · Homepage · Source on GitHub