Positive Distribution Shift as a Framework for Understanding Tractable Learning

• URL: http://arxiv.org/abs/2602.08907v2
• Date: Thu, 12 Feb 2026 07:19:47 GMT
• Title: Positive Distribution Shift as a Framework for Understanding Tractable Learning
• Abstract summary: We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x)<n>We argue that with a well-chosen D'(x) the shift can be positive and make learning easier.
• Score: 43.34621580435111
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training distribution D'(x), labeled by the true target f(x). Such a distribution shift (here in the form of covariate shift) is usually viewed negatively, as hurting or making learning harder, and the traditional distribution shift literature is mostly concerned with limiting or avoiding this negative effect. In contrast, we argue that with a well-chosen D'(x), the shift can be positive and make learning easier -- a perspective called Positive Distribution Shift (PDS). Such a perspective is central to contemporary machine learning, where much of the innovation is in finding good training distributions D'(x), rather than changing the training algorithm. We further argue that the benefit is often computational rather than statistical, and that PDS allows computationally hard problems to become tractable even using standard gradient-based training. We formalize different variants of PDS, show how certain hard classes are easily learnable under PDS, and make connections with membership query learning.

Related papers

• Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift [21.679363840452087]
  We give an efficient black-box reduction from PQ learning to TDS learning for any Boolean concept class.<n>This equivalence implies the first hardness results for distribution-free TDS learning of basic classes such as halfspaces.<n>We also show that giving a learner access to membership queries sidesteps these hardness results and allows for efficient, distribution-free PQ learnability of halfspaces.
  arXiv  Detail & Related papers  (2026-05-07T22:37:29Z)
• Distributional Training Data Attribution: What do Influence Functions Sample? [25.257922996567178]
  We introduce distributional training data attribution (d-TDA)<n>The goal of d-TDA is to predict how the distribution of model outputs depends upon the dataset.<n>We find that influence functions (IFs) are'secretly distributional'
  arXiv  Detail & Related papers  (2025-06-15T21:02:36Z)
• Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees [13.936051653540144]
  We give the first.<n>efficient algorithms for learning neural networks with a distribution shift.<n>We work in the Testable Learning with Distribution Shift framework.
  arXiv  Detail & Related papers  (2025-02-22T00:48:03Z)
• Tolerant Algorithms for Learning with Arbitrary Covariate Shift [18.37181965815327]
  We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially adversarially generated test distribution. We focus on two frameworks: PQ learning [Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS 2020], allowing abstention on adversarially generated parts of the test distribution, and TDS learning [Klivans, Stavropoulos, Vasilyan COLT 2024], permitting abstention on the entire test distribution if distribution shift is detected.
  arXiv  Detail & Related papers  (2024-06-04T19:50:05Z)
• Diagnosing Model Performance Under Distribution Shift [9.143551270841858]
  Prediction models can perform poorly when deployed to target distributions different from the training distribution. Our approach decomposes the performance drop into terms for 1) an increase in harder but frequently seen examples from training, 2) changes in the relationship between features and outcomes, and 3) poor performance on examples infrequent or unseen during training.
  arXiv  Detail & Related papers  (2023-03-03T15:27:16Z)
• Learnable Distribution Calibration for Few-Shot Class-Incremental Learning [122.2241120474278]
  Few-shot class-incremental learning (FSCIL) faces challenges of memorizing old class distributions and estimating new class distributions given few training samples. We propose a learnable distribution calibration (LDC) approach, with the aim to systematically solve these two challenges using a unified framework.
  arXiv  Detail & Related papers  (2022-10-01T09:40:26Z)
• Domain Adaptation meets Individual Fairness. And they get along [48.95808607591299]
  We show that algorithmic fairness interventions can help machine learning models overcome distribution shifts. In particular, we show that enforcing suitable notions of individual fairness (IF) can improve the out-of-distribution accuracy of ML models.
  arXiv  Detail & Related papers  (2022-05-01T16:19:55Z)
• Agree to Disagree: Diversity through Disagreement for Better Transferability [54.308327969778155]
  We propose D-BAT (Diversity-By-disAgreement Training), which enforces agreement among the models on the training data. We show how D-BAT naturally emerges from the notion of generalized discrepancy.
  arXiv  Detail & Related papers  (2022-02-09T12:03:02Z)
• KL Guided Domain Adaptation [88.19298405363452]
  Domain adaptation is an important problem and often needed for real-world applications. A common approach in the domain adaptation literature is to learn a representation of the input that has the same distributions over the source and the target domain. We show that with a probabilistic representation network, the KL term can be estimated efficiently via minibatch samples.
  arXiv  Detail & Related papers  (2021-06-14T22:24:23Z)
• DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction [96.90215318875859]
  We show that bootstrapping-based Q-learning algorithms do not necessarily benefit from corrective feedback. We propose a new algorithm, DisCor, which computes an approximation to this optimal distribution and uses it to re-weight the transitions used for training.
  arXiv  Detail & Related papers  (2020-03-16T16:18:52Z)

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.