Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift

• URL: http://arxiv.org/abs/2605.07005v1
• Date: Thu, 07 May 2026 22:37:29 GMT
• Title: Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
• Abstract summary: 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.
• Score: 21.679363840452087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al. (2024)). Algorithms for TDS learning are allowed to reject a test set entirely if distribution shift is detected. In contrast, PQ learners may only reject points that are deemed out-of-distribution on an individual basis. Our main result is a surprising equivalence between these two models in the distribution-free setting. In particular, we give an efficient black-box reduction from PQ learning to TDS learning for any Boolean concept class. This equivalence implies the first hardness results for distribution-free TDS learning of basic classes such as halfspaces. The main technical contribution underlying our equivalence is a method for boosting, via branching programs, the weak distinguishing power of TDS learners that have rejected the target domain. 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. Our algorithm iteratively recovers large-margin separators obtained by applying successive Forster transforms on the training data.

Related papers

• Iterative Chow Filtering for Learning with Distribution Shift [25.270503886184795]
  We show that the weaker notion of $cal L$ sandwiching suffices for efficient PQ learning.<n>We obtain the first quasipolynomial-time PQ learning algorithm for DNFs under uniform distribution.
  arXiv  Detail & Related papers  (2026-05-17T04:18:17Z)
• Positive Distribution Shift as a Framework for Understanding Tractable Learning [43.34621580435111]
  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.
  arXiv  Detail & Related papers  (2026-02-09T17:08:10Z)
• 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)
• Efficient Discrepancy Testing for Learning with Distribution Shift [17.472049019016524]
  We provide the first set of provably efficient algorithms for testing localized discrepancy distance. Results imply a broad set of new, efficient learning algorithms in the recently introduced model of Testable Learning with Distribution Shift.
  arXiv  Detail & Related papers  (2024-06-13T17:51:10Z)
• 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)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• A Hard-to-Beat Baseline for Training-free CLIP-based Adaptation [121.0693322732454]
  Contrastive Language-Image Pretraining (CLIP) has gained popularity for its remarkable zero-shot capacity. Recent research has focused on developing efficient fine-tuning methods to enhance CLIP's performance in downstream tasks. We revisit a classical algorithm, Gaussian Discriminant Analysis (GDA), and apply it to the downstream classification of CLIP.
  arXiv  Detail & Related papers  (2024-02-06T15:45:27Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  We study two basic statistical tasks in non-interactive local differential privacy (LDP): learning and refutation. Our main result is a complete characterization of the sample complexity of PAC learning for non-interactive LDP protocols.
  arXiv  Detail & Related papers  (2022-10-26T03:19:24Z)
• 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)
• CAFA: Class-Aware Feature Alignment for Test-Time Adaptation [50.26963784271912]
  Test-time adaptation (TTA) aims to address this challenge by adapting a model to unlabeled data at test time. We propose a simple yet effective feature alignment loss, termed as Class-Aware Feature Alignment (CAFA), which simultaneously encourages a model to learn target representations in a class-discriminative manner.
  arXiv  Detail & Related papers  (2022-06-01T03:02:07Z)
• 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)
• You Only Need End-to-End Training for Long-Tailed Recognition [8.789819609485225]
  Cross-entropy loss tends to produce highly correlated features on imbalanced data. We propose two novel modules, Block-based Relatively Balanced Batch Sampler (B3RS) and Batch Embedded Training (BET) Experimental results on the long-tailed classification benchmarks, CIFAR-LT and ImageNet-LT, demonstrate the effectiveness of our method.
  arXiv  Detail & Related papers  (2021-12-11T11:44:09Z)

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.