技术摘要：在线可实现回归及其在 ReLU 网络中的应用

问题陈述

本文研究了对抗设置下的可实现在线回归（realizable online regression），其中不施加任何随机假设或间隔（margin）条件。核心问题是确定何时“可实现性”（即存在一个目标假设 $h^* \in \mathcal{H}$ 能完美生成标签）能够蕴含无视界（horizon-free，即有限的）累积损失界限，并识别控制该界限的复杂度参数。

作者将其与在线分类进行对比：在分类中，即使是像感知机（Perceptron）这样简单的类，在没有间隔假设的情况下也可能具有无限的错误界限。然而在回归中，即使在类似度量（metric-like）的损失函数下，可实现性也能强制实现有限的总损失，即便与之类似的分类问题是不可学习的。本研究关注满足近似三角不等式（近似伪度量）的损失函数 $\ell$，这一条件对于防止出现以下退化场景至关重要：即学习者尽管在假设空间中存在巨大差距，却能以极小的损失预测中间标签。

方法论

本文引入了一种通用势函数法（generic potential method）来上界化缩放后的 Littlestone 维度（scaled Littlestone dimension, $D_{\text{onl}}$），这是一个由 Attias 等人 [2] 引入的抽象维度，用于表征极小极大（minimax）可实现累积损失。

熵势框架（The Entropy Potential Framework）

由于直接计算 $D_{\text{onl}}$ 可能非常困难，作者利用基于假设类 $\mathcal{H}$ 在诱导超伪度量 $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$ 下的覆盖数（covering numbers）的 Dudley 型熵积分来上界化它。

1. 熵势定义： 对于具有有限直径的假设类 $\mathcal{H}$，熵势定义为：
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   其中 $N(\mathcal{H}, \varepsilon)$ 是 $\mathcal{H}$ 关于 $d_\ell$ 的 $\varepsilon$-覆盖数。

2. 主定理： 作者证明，对于任何 $c$-近似伪度量损失，缩放后的 Littlestone 维度由熵势上界化：
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   证明过程采用了对可实现缩放 Littlestone 树的分支界限（branch bound）论证。通过分析每个节点处的版本空间（version spaces），他们表明近似三角不等式强制要求：当 $\varepsilon < \gamma/(2c)$ 时，任何 $\varepsilon$-覆盖都会跨越具有间隙 $\gamma$ 的子节点。通过在不同尺度上对这种“覆盖分裂”（cover splitting）进行积分，可以得到一个与间隙成正比的势能下降，从而将任何分支上的总间隙限制在 $\Phi(\mathcal{H})$ 之内。

3. 含义： 如果 $\mathcal{H}$ 具有多项式覆盖数（即 $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$），则 $\Phi(\mathcal{H}) < \infty$，这意味着存在无视界的实现累积损失界限。

核心贡献与结果

1. $\ell_q$ 损失下的 Lipschitz 回归

作者将其框架应用于 $[-1, 1]^d$ 上 $L$-Lipschitz 函数类 $\mathcal{H}_L$，损失函数为 $\ell_q(y, y') = |y - y'|^q$。他们确立了一个基于 $q$ 与维度 $d$ 关系的锐利相变（sharp phase transition）：

• 可学习区间 ($q > d$)： 熵势是有限的。极小极大可实现累积损失为 $\Theta_{d,q}(L^d)$。作者提供了一种基于 Lipschitz 包络（下界和上界）的高效确定性适当算法（efficient deterministic proper algorithm），该算法达到了此界限。
• 不可学习区间 ($q \leq d$)： 熵势发散。
  • 若 $q < d$，极小极大累积损失随视界 $T$ 多项式增长。
  • 若 $q = d$，损失随 $T$ 对数增长。
  • 在两种情况下，$D_{\text{onl}}(\mathcal{H}) = \infty$。
• 最终可学习性： 对于任何满足 $\ell(y,y)=0$ 的连续损失 $\ell$，作者表明对于 $L$-Lipschitz 函数，瞬时损失 $\ell(\hat{y}_t, y_t)$ 都会随着 $t \to \infty$ 收敛到 0，无论总累积损失是否有限。

2. 有界 $k$-ReLU 网络

本文研究了 $[-1, 1]^d$ 上有界 $k$-ReLU 网络类 $\mathcal{H}_{k,d}$（权重有界的 $k$ 个 ReLU 之和）在平方损失下的情况。

• 回归与分类的分离：
  • 分类： 在 0/1 损失下，对于 $\mathcal{H}_{2,1}$（两个隐藏神经元，1D 输入），可实现在线分类是不可能的，因为即使权重有界，其 Littlestone 维度也是无限的。
  • 回归： 在平方损失下，可实现在线回归具有有限的总损失。
• 上界：
  • 存在一个（信息论意义上的）在线算法，其累积损失为 $O(k^2 \log^4 d) = \tilde{O}(k^2)$。
  • 对于单个 ReLU ($k=1$)，存在一个累积损失为 $O(1)$ 的高效算法，且与维度 $d$ 无关。
• 下界：
  • 证明了 $\Omega(k^2 \log(d/k^2))$ 的下界，表明对 $k$ 和 $\log d$ 的依赖是必要的。
• 计算复杂度：
  • 假设 Gap-ETH 假设成立，作者排除了对于 $k \geq 2$ 的高效适当（efficient proper）在线学习器在多项式时间内达到 $e^{o(d)}$ 累积损失的可能性。这表明虽然从信息论角度看有限损失是可能的，但通过适当学习器高效地计算出该损失可能是困难的。

3. 向深度网络的推广

结果被扩展到了深度为 $L$、宽度为 $k$ 的网络。研究表明，极小极大可实现累积平方损失为 $\tilde{O}(k^L)$，当 $d/k^L \to \infty$ 时，对应的下界为 $\Omega(k^L \log(d/k^L))$。

意义与主张

本文声称，可实现性从根本上改变了在线学习的格局（相对于不可知/agnostic 设置）。具体而言：

1. 度量熵作为复杂度度量： 作者确立了对于近似伪度量下的可实现回归，度量熵（通过熵势 $\Phi$）是一个充分且通常是紧致的 $D_{\text{onl}}$ 代理。这提供了一个具体的、可计算的工具，用于分析那些抽象维度难以处理的场景下的可学习性。
2. 非参数回归中的相变： 本研究识别了使非参数 Lipschitz 回归实现无视界（horizon-free）的精确条件 ($q > d$)，这与 $q \leq d$ 时分类或回归的不可学习性形成了鲜明对比。
3. 神经网络的可学习性： 本文强调了 ReLU 网络在分类与回归之间的显著分离。虽然有界 ReLU 网络在分类设置下是不可学习的（Littlestone 维度无限），但在回归设置下却可以实现有限的累积损失。然而，这种可学习性带有约束：对于 $k \geq 2$，通过适当学习器高效地实现这种损失在计算上可能是难以处理的。
4. 局限性： 作者指出熵势界限并不总是紧致的；存在一些类，其 $\Phi(\mathcal{H}) = \infty$ 但 $D_{\text{onl}}(\mathcal{H}) < \infty$。因此，$\Phi$ 是作为一个显式的上界代理，而非在所有情况下的完整特征描述。

这项工作依赖于在线维度理论 [2] 的最新进展，并将来自随机过程（Dudley 积分）的技术应用于对抗性在线设置，由于可实现性的假设，避免了使用顺序链式法则（sequential chaining），转而使用标准的覆盖。