Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913703183515648 |
|---|---|
| author | Chandrasekaran, Gautam Klivans, Adam R. Lee, Lin Lin Stavropoulos, Konstantinos |
| author_facet | Chandrasekaran, Gautam Klivans, Adam R. Lee, Lin Lin Stavropoulos, Konstantinos |
| contents | We give the first provably efficient algorithms for learning neural networks with distribution shift. We work in the Testable Learning with Distribution Shift framework (TDS learning) of Klivans et al. (2024), where the learner receives labeled examples from a training distribution and unlabeled examples from a test distribution and must either output a hypothesis with low test error or reject if distribution shift is detected. No assumptions are made on the test distribution.
All prior work in TDS learning focuses on classification, while here we must handle the setting of nonconvex regression. Our results apply to real-valued networks with arbitrary Lipschitz activations and work whenever the training distribution has strictly sub-exponential tails. For training distributions that are bounded and hypercontractive, we give a fully polynomial-time algorithm for TDS learning one hidden-layer networks with sigmoid activations. We achieve this by importing classical kernel methods into the TDS framework using data-dependent feature maps and a type of kernel matrix that couples samples from both train and test distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16021 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees Chandrasekaran, Gautam Klivans, Adam R. Lee, Lin Lin Stavropoulos, Konstantinos Data Structures and Algorithms Machine Learning We give the first provably efficient algorithms for learning neural networks with distribution shift. We work in the Testable Learning with Distribution Shift framework (TDS learning) of Klivans et al. (2024), where the learner receives labeled examples from a training distribution and unlabeled examples from a test distribution and must either output a hypothesis with low test error or reject if distribution shift is detected. No assumptions are made on the test distribution. All prior work in TDS learning focuses on classification, while here we must handle the setting of nonconvex regression. Our results apply to real-valued networks with arbitrary Lipschitz activations and work whenever the training distribution has strictly sub-exponential tails. For training distributions that are bounded and hypercontractive, we give a fully polynomial-time algorithm for TDS learning one hidden-layer networks with sigmoid activations. We achieve this by importing classical kernel methods into the TDS framework using data-dependent feature maps and a type of kernel matrix that couples samples from both train and test distributions. |
| title | Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2502.16021 |