A fundamental notion of distance between train and test distributions from
the field of domain adaptation is discrepancy distance. While in general hard
to compute, here we provide the first set of provably efficient algorithms for
testing localized discrepancy distance, where discrepancy is computed with
respect to a fixed output classifier. These results imply a broad set of new,
efficient learning algorithms in the recently introduced model of Testable
Learning with Distribution Shift (TDS learning) due to Klivans et al. (2023).
Our approach generalizes and improves all prior work on TDS learning: (1) we
obtain universal learners that succeed simultaneously for large classes of test
distributions, (2) achieve near-optimal error rates, and (3) give exponential
improvements for constant depth circuits. Our methods further extend to
semi-parametric settings and imply the first positive results for
low-dimensional convex sets. Additionally, we separate learning and testing
phases and obtain algorithms that run in fully polynomial time at test time.

提供了可靠与高效的算法来测试本地化的差异距离，进一步扩展了 TDS 学习模型并改进了之前相关的工作，同时提供了针对常数深度电路的指数级改进，与低维凸集的首个正面结果。

学习中的分布偏移的高效差异性测试

Efficient Discrepancy Testing for Learning with Distribution Shift

We study the problem of learning under arbitrary distribution shift, where
the learner is trained on a labeled set from one distribution but evaluated on
a different, potentially adversarially generated test distribution. We focus on
two frameworks: PQ learning [Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS
2020], allowing abstention on adversarially generated parts of the test
distribution, and TDS learning [Klivans, Stavropoulos, Vasilyan COLT 2024],
permitting abstention on the entire test distribution if distribution shift is
detected. All prior known algorithms either rely on learning primitives that
are computationally hard even for simple function classes, or end up abstaining
entirely even in the presence of a tiny amount of distribution shift.
We address both these challenges for natural function classes, including
intersections of halfspaces and decision trees, and standard training
distributions, including Gaussians. For PQ learning, we give efficient learning
algorithms, while for TDS learning, our algorithms can tolerate moderate
amounts of distribution shift. At the core of our approach is an improved
analysis of spectral outlier-removal techniques from learning with nasty noise.
Our analysis can (1) handle arbitrarily large fraction of outliers, which is
crucial for handling arbitrary distribution shifts, and (2) obtain stronger
bounds on polynomial moments of the distribution after outlier removal,
yielding new insights into polynomial regression under distribution shifts.
Lastly, our techniques lead to novel results for tolerant testable learning
[Rubinfeld and Vasilyan STOC 2023], and learning with nasty noise.

研究在任意分布转移下的学习问题，重点关注 PQ 学习、TDS 学习两个框架以及谱异常移除技术对多项式回归及容忍可测试学习的影响。

处理任意协变量偏移学习的容错算法

Tolerant Algorithms for Learning with Arbitrary Covariate Shift

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/\epsilon)^{O(1)}} \mathsf{poly}(d)$-time algorithm
for TDS learning intersections of $k$ homogeneous halfspaces to accuracy
$\epsilon$ (prior work achieved $d^{(k/\epsilon)^{O(1)}}$). We work under the
mild assumption that the Gaussian training distribution contains at least an
$\epsilon$ fraction of both positive and negative examples
($\epsilon$-balanced). We also prove the first set of SQ lower-bounds for any
TDS learning problem and show (1) the $\epsilon$-balanced assumption is
necessary for $\mathsf{poly}(d,1/\epsilon)$-time TDS learning for a single
halfspace and (2) a $d^{\tilde{\Omega}(\log 1/\epsilon)}$ lower bound for the
intersection of two general halfspaces, even with the $\epsilon$-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.

针对高斯训练分布的交叉半空间集的可测试学习，证明了一种新的上界算法，能在多项式时间内实现 TDS 学习，且达到精确度 e，扩展了 TDS 学习工具库。