Iterative Chow Filtering for Learning with Distribution Shift
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917505256128512 |
|---|---|
| author | Chandrasekaran, Gautam Gkrinias, Georgios Klivans, Adam R. Stavropoulos, Konstantinos Vasilyan, Arsen |
| author_facet | Chandrasekaran, Gautam Gkrinias, Georgios Klivans, Adam R. Stavropoulos, Konstantinos Vasilyan, Arsen |
| contents | Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled training examples, unlabeled test examples, and must make correct predictions on the test set but is allowed to abstain from predicting on out-of-distribution points. Their results rely on ${\cal L}_2$ sandwiching approximations, a strong requirement that leads to poor bounds for several basic function classes such as DNF formulas.
Here, we show that the weaker notion of ${\cal L}_1$ sandwiching suffices for efficient PQ learning. As a consequence, we obtain the first quasipolynomial-time PQ learning algorithm for DNFs under the uniform distribution and essentially match the guarantees known for ordinary PAC learning. More broadly, our bounds provide exponential improvements for several classes including constant depth circuits and constant degree polynomial threshold functions.
Our main technical ingredient is Iterative Chow Filtering, a new procedure that uses low-degree Chow parameters to identify and remove test points incompatible with the training distribution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17251 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Iterative Chow Filtering for Learning with Distribution Shift Chandrasekaran, Gautam Gkrinias, Georgios Klivans, Adam R. Stavropoulos, Konstantinos Vasilyan, Arsen Data Structures and Algorithms Machine Learning Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled training examples, unlabeled test examples, and must make correct predictions on the test set but is allowed to abstain from predicting on out-of-distribution points. Their results rely on ${\cal L}_2$ sandwiching approximations, a strong requirement that leads to poor bounds for several basic function classes such as DNF formulas. Here, we show that the weaker notion of ${\cal L}_1$ sandwiching suffices for efficient PQ learning. As a consequence, we obtain the first quasipolynomial-time PQ learning algorithm for DNFs under the uniform distribution and essentially match the guarantees known for ordinary PAC learning. More broadly, our bounds provide exponential improvements for several classes including constant depth circuits and constant degree polynomial threshold functions. Our main technical ingredient is Iterative Chow Filtering, a new procedure that uses low-degree Chow parameters to identify and remove test points incompatible with the training distribution. |
| title | Iterative Chow Filtering for Learning with Distribution Shift |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2605.17251 |