An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization

Elan Rosenfeld, Pradeep Ravikumar, Andrej Risteski – CMU
Elan Rosenfeld 的代表作与对抗样本、分布外样本均相关:《Certified adversarial robustness via randomized smoothing》,《The Risks of Invariant Risk Minimization》。

解决问题及难点

本文从在线学习 (Online learning) 的角度考虑了域泛化 (Domain generalization) 问题:将域泛化问题分为内拓 (Interpolation) 与外延 (Extrapolation) 两个方向,并分别分析了在线学习对这两个任务的遗憾界 (Regret)。本文试图替换域泛化问题常用的单回合极大极小游戏 (Single-round min-max game) 的框架,更深入地分析此问题的统计和算法性质。

核心贡献

  • 将域泛化问题刻化为在线学习问题,定义为一个对抗出现的测试分布和一个最小化积累遗憾 (Cumulative regret) 的玩家。
  • 理论上证明了在计算层面,外延比内拓指数级别地复杂;在统计层面,两者的遗憾界并没有显著的差别(指\(\Theta(\sqrt{T})\) 与\(\Theta(\log T)\))。
  • ERM 对于内拓与外延都能够到达极大极小最优。

解决方案及创新点

内拓与外延

内拓 Interpolation

内拓等价于优化现有环境分布集合\(\mathcal{E}\) 的凸组合\(Conv(\mathcal E)\),即内拓的测试环境在已有环境组成的凸包内部或边界上:

\[\min _{f \in \mathcal{F}} \max _{e \in \operatorname{Conv}(\mathcal{E})} \mathbb{E}_e[\ell(f)]=\min _{f \in \mathcal{F}} \max _{e \in \mathcal{E}} \mathbb{E}_e[\ell(f)]
\]

因此,内拓是一个离散的单回合游戏。

外延 Extrapolation

外拓将测试环境分布定义为已有环境线性组合\(Extr(\mathcal E)\),系数只和必须为\(1\) 却允许某些组合系数是较小的负数 (系数满足\(\lambda>-\alpha\)),即外延的环境在已有环境组成的凸包附近:

\[\begin{aligned}
&\min _{f \in \mathcal{F}} \max _{e \in \operatorname{Extr}_\alpha(\mathcal{E})} \mathbb{E}_e[\ell(f)]= \\
&\min _{f \in \mathcal{F}} \max _{e \in \mathcal{E}}\left[(1+E \alpha) \mathbb{E}_e[\ell(f)]-\alpha \sum_{e^{\prime} \in \mathcal{E}} \mathbb{E}_{e^{\prime}}[\ell(f)]\right]
\end{aligned}
\]

本文发现这个损失等价于平均的损失加上最坏情况下的损失,因此,外延变为一个离散的单回合游戏。

Extrapolation

在线学习

每回合玩家选择一个参数\(\hat{\beta}\in B\),对手选择一组环境的系数\(\lambda_t\in \Delta\),定义损失函数为\(f_t(\beta):=\mathbb{E}_{(x, y) \sim p^{\lambda_t}}[\ell(\beta,(x, y))]=\sum_{e \in \mathcal{E}} \lambda_{t, e} \mathbb{E}_{(x, y) \sim p^e}[\ell(\beta,(x, y))]\)。

定义 T 轮之后的遗憾总和为:

\[\begin{aligned}
V_T:=& \min _{\hat{\beta}_1 \in B} \max _{\lambda_1 \in \Delta_E} \cdots \\
& \min _{\hat{\beta}_T \in B \lambda_T \in \Delta_E}\left(\sum_{t=1}^T f_t\left(\hat{\beta}_t\right)-\min _{\beta \in B} \sum_{t=1}^T f_t(\beta)\right)
\end{aligned}
\]

在理想的强凸条件下,\(V_t=\sum_{s=1}^t \frac{G_s^2}{2 s \sigma_{\min }}\),即遗憾界为\(\Theta(\log t)\)。其中,\(G_s\) 是\(f_s\) 的 Lipshitz 常数,\(\sigma_{min}\) 是\(f\) 的最小曲率。

本文的定理 1 证明了遗憾界的下界也是\(\Theta(\log t)\) 的,并可以通过 FTL 算法得到。这证明了在已知环境的条件下,使用 ERM 算法能够为内拓得到可证明的 Min-max 最优。

本文的定理 2 证明了在外拓的情形下没有算法能够达到次线性的遗憾界。因此,需要削弱对抗的对手使其选择整个损失函数序列。在这个情形下,定理 3 证明了达到次线性的遗憾界依旧是 NP-Hard。
从统计学的角度来看,使用 FTPL 算法(即基于扰动的 ERM)能够得到\(\Omega(\sqrt{T})\) 的下届,同时,定理 4 证明了对于这个问题可得到的下界就是\(\Omega(\sqrt{T})\) 的。因此,ERM 配合合适的正则化是可以得到好的域外泛化性的。

局限性和改进空间

感觉也没怎么看懂这个文章,就是证明了其实 ERM 算法能够得到很好的域外泛化性能。本文也给出了一些未来方向:

  • 利用在线学习的框架研究分布外泛化问题
  • 更有效更针对的定义内拓与外延

发表回复

您的电子邮箱地址不会被公开。