Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913357429211136 |
|---|---|
| author | Klivans, Adam R. Stavropoulos, Konstantinos Vasilyan, Arsen |
| author_facet | Klivans, Adam R. Stavropoulos, Konstantinos Vasilyan, Arsen |
| contents | Recent work of Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift (TDS learning), where a learner is given labeled samples from training distribution $\mathcal{D}$, unlabeled samples from test distribution $\mathcal{D}'$, and the goal is to output a classifier with low error on $\mathcal{D}'$ whenever the training samples pass a corresponding test. Their model deviates from all prior work in that no assumptions are made on $\mathcal{D}'$. Instead, the test must accept (with high probability) when the marginals of the training and test distributions are equal.
Here we focus on the fundamental case of intersections of halfspaces with respect to Gaussian training distributions and prove a variety of new upper bounds including a $2^{(k/ε)^{O(1)}} \mathsf{poly}(d)$-time algorithm for TDS learning intersections of $k$ homogeneous halfspaces to accuracy $ε$ (prior work achieved $d^{(k/ε)^{O(1)}}$). We work under the mild assumption that the Gaussian training distribution contains at least an $ε$ fraction of both positive and negative examples ($ε$-balanced). We also prove the first set of SQ lower-bounds for any TDS learning problem and show (1) the $ε$-balanced assumption is necessary for $\mathsf{poly}(d,1/ε)$-time TDS learning for a single halfspace and (2) a $d^{\tildeΩ(\log 1/ε)}$ lower bound for the intersection of two general halfspaces, even with the $ε$-balanced assumption.
Our techniques significantly expand the toolkit for TDS learning. We use dimension reduction and coverings to give efficient algorithms for computing a localized version of discrepancy distance, a key metric from the domain adaptation literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02364 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds Klivans, Adam R. Stavropoulos, Konstantinos Vasilyan, Arsen Data Structures and Algorithms Machine Learning Recent work of Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift (TDS learning), where a learner is given labeled samples from training distribution $\mathcal{D}$, unlabeled samples from test distribution $\mathcal{D}'$, and the goal is to output a classifier with low error on $\mathcal{D}'$ whenever the training samples pass a corresponding test. Their model deviates from all prior work in that no assumptions are made on $\mathcal{D}'$. Instead, the test must accept (with high probability) when the marginals of the training and test distributions are equal. Here we focus on the fundamental case of intersections of halfspaces with respect to Gaussian training distributions and prove a variety of new upper bounds including a $2^{(k/ε)^{O(1)}} \mathsf{poly}(d)$-time algorithm for TDS learning intersections of $k$ homogeneous halfspaces to accuracy $ε$ (prior work achieved $d^{(k/ε)^{O(1)}}$). We work under the mild assumption that the Gaussian training distribution contains at least an $ε$ fraction of both positive and negative examples ($ε$-balanced). We also prove the first set of SQ lower-bounds for any TDS learning problem and show (1) the $ε$-balanced assumption is necessary for $\mathsf{poly}(d,1/ε)$-time TDS learning for a single halfspace and (2) a $d^{\tildeΩ(\log 1/ε)}$ lower bound for the intersection of two general halfspaces, even with the $ε$-balanced assumption. Our techniques significantly expand the toolkit for TDS learning. We use dimension reduction and coverings to give efficient algorithms for computing a localized version of discrepancy distance, a key metric from the domain adaptation literature. |
| title | Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2404.02364 |