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

Shyamal Patel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4022-4049, 2026.

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 concept 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 {\em 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-patel26a, title = {Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift}, author = {Patel, Shyamal and Klivans, Adam and Stavropoulos, Konstantinos and Vasilyan, Arsen}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {4022--4049}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/patel26a/patel26a.pdf}, url = {https://proceedings.mlr.press/v336/patel26a.html}, 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 concept 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 {\em 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. } }
Endnote
%0 Conference Paper %T Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift %A Shyamal Patel %A Adam Klivans %A Konstantinos Stavropoulos %A Arsen Vasilyan %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-patel26a %I PMLR %P 4022--4049 %U https://proceedings.mlr.press/v336/patel26a.html %V 336 %X 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 concept 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 {\em 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.
APA
Patel, S., Klivans, A., Stavropoulos, K. & Vasilyan, A.. (2026). Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:4022-4049 Available from https://proceedings.mlr.press/v336/patel26a.html.

Related Material