Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds

arXiv:2404.02364v1 Announce Type: cross
Abstract: 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 …

abstract algorithms arxiv cs.ds cs.lg distribution samples shift study test training type work