Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments
Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Yining Chen;Elan Rosenfeld;Mark Sellke;Tengyu Ma;Andrej Risteski
中科院分区：
文献类型：
--
作者：
Yining Chen;Elan Rosenfeld;Mark Sellke;Tengyu Ma;Andrej Risteski
领域泛化的目的是利用来自有限数量的训练环境的数据在看不见的测试环境中表现良好。尽管用于此任务的提议算法激增，但从理论上和经验上评估其性能仍然非常具有挑战性。分布式匹配算法，例如（条件）域对抗网络 [Ganin et al., 2016, Long et al., 2018] 很受欢迎，并且取得了经验上的成功，但它们缺乏正式的保证。其他方法，例如不变风险最小化 (IRM)，需要大量的训练环境——在伪特征空间 $d_s$ 的维度上呈线性——即使是在 [Rosenfeld 等人，2021] 提出的简单数据模型上也是如此。在该模型的一个变体下，我们表明 ERM 和 IRM 都不能泛化于 $o(d_s)$ 环境。然后，我们提出一种迭代特征匹配算法，该算法保证以高概率产生一个在仅看到 $O(\log d_s)$ 环境后进行泛化的预测器。我们的结果为在具体的非平凡数据模型下在实践中广泛使用的一系列分布匹配算法提供了第一个理论依据。
Domain generalization aims at performing well on unseen test environments with data from a limited number of training environments. Despite a proliferation of proposal algorithms for this task, assessing their performance both theoretically and empirically is still very challenging. Distributional matching algorithms such as (Conditional) Domain Adversarial Networks [Ganin et al., 2016, Long et al., 2018] are popular and enjoy empirical success, but they lack formal guarantees. Other approaches such as Invariant Risk Minimization (IRM) require a prohibitively large number of training environments -- linear in the dimension of the spurious feature space $d_s$ -- even on simple data models like the one proposed by [Rosenfeld et al., 2021]. Under a variant of this model, we show that both ERM and IRM cannot generalize with $o(d_s)$ environments. We then present an iterative feature matching algorithm that is guaranteed with high probability to yield a predictor that generalizes after seeing only $O(\log d_s)$ environments. Our results provide the first theoretical justification for a family of distribution-matching algorithms widely used in practice under a concrete nontrivial data model.