Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments

• URL: http://arxiv.org/abs/2106.09913v1
• Date: Fri, 18 Jun 2021 04:39:19 GMT
• Title: Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments
• Authors: Yining Chen, Elan Rosenfeld, Mark Sellke, Tengyu Ma, Andrej Risteski
• Abstract summary: Domain generalization aims at performing well on unseen test environments with data from a limited number of training environments. We present a new algorithm based on performing iterative feature matching that is guaranteed with high probability to yield a predictor that generalizes after seeing only $O(logd_s)$ environments.
• Score: 55.24895403089543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. Moreover, recent 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 a new algorithm based on performing iterative feature matching that is guaranteed with high probability to yield a predictor that generalizes after seeing only $O(\log{d_s})$ environments.

Related papers

• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. We propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP) We show that LOOP achieves a sublinear $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret, where $d$ and $beta$ correspond to AGEC and log-covering number of the hypothesis class respectively
  arXiv  Detail & Related papers  (2024-04-19T06:24:22Z)
• Invariant-Feature Subspace Recovery: A New Class of Provable Domain Generalization Algorithms [14.248005245508432]
  Domain generalization asks for trained models over a set of training environments to generalize well in unseen test environments. We propose Subspace Recovery (ISR): a new class of algorithms to achieve provable regression problems. ISR can be used as post-processing methods for neural nets such as neural nets Empirically, we demonstrate the superior performance of our ISRs on synthetic benchmarks.
  arXiv  Detail & Related papers  (2023-11-02T03:24:55Z)
• EM for Mixture of Linear Regression with Clustered Data [6.948976192408852]
  We discuss how the underlying clustered structures in distributed data can be exploited to improve learning schemes. We employ the well-known Expectation-Maximization (EM) method to estimate the maximum likelihood parameters from $m$ batches of dependent samples. We show that if properly, EM on the structured data requires only $O(1)$ to reach the same statistical accuracy, as long as $m$ grows up as $eo(n)$.
  arXiv  Detail & Related papers  (2023-08-22T15:47:58Z)
• Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data [4.971690889257356]
  We introduce an adaptation of the alternating minimization-descent scheme proposed by Collins and Nayer and Vaswani. We show that vanilla alternating-minimization descent fails catastrophically even for iid, but mildly non-isotropic data. Our analysis unifies and generalizes prior work, and provides a flexible framework for a wider range of applications.
  arXiv  Detail & Related papers  (2023-08-08T17:56:20Z)
• Probable Domain Generalization via Quantile Risk Minimization [90.15831047587302]
  Domain generalization seeks predictors which perform well on unseen test distributions. We propose a new probabilistic framework for DG where the goal is to learn predictors that perform well with high probability.
  arXiv  Detail & Related papers  (2022-07-20T14:41:09Z)
• A Relational Intervention Approach for Unsupervised Dynamics Generalization in Model-Based Reinforcement Learning [113.75991721607174]
  We introduce an interventional prediction module to estimate the probability of two estimated $hatz_i, hatz_j$ belonging to the same environment. We empirically show that $hatZ$ estimated by our method enjoy less redundant information than previous methods.
  arXiv  Detail & Related papers  (2022-06-09T15:01:36Z)
• Provable Domain Generalization via Invariant-Feature Subspace Recovery [18.25619572103648]
  In this paper, we propose to achieve domain generalization with Invariant- Subspace Recovery (ISR) Unlike training IRM, our algorithms bypass non-variantity issues and enjoy global convergence. In addition, on three real-world image datasets, we show that ISR- can be used as a simple yet effective post-processing method.
  arXiv  Detail & Related papers  (2022-01-30T21:22:47Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.