Rubinfeld & Vasilyan recently introduced the framework of testable learning
as an extension of the classical agnostic model. It relaxes distributional
assumptions which are difficult to verify by conditions that can be checked
efficiently by a tester. The tester has to accept whenever the data truly
satisfies the original assumptions, and the learner has to succeed whenever the
tester accepts. We focus on the setting where the tester has to accept standard
Gaussian data. There, it is known that basic concept classes such as halfspaces
can be learned testably with the same time complexity as in the
(distribution-specific) agnostic model. In this work, we ask whether there is a
price to pay for testably learning more complex concept classes. In particular,
we consider polynomial threshold functions (PTFs), which naturally generalize
halfspaces. We show that PTFs of arbitrary constant degree can be testably
learned up to excess error $\varepsilon > 0$ in time
$n^{\mathrm{poly}(1/\varepsilon)}$. This qualitatively matches the best known
guarantees in the agnostic model. Our results build on a connection between
testable learning and fooling. In particular, we show that distributions that
approximately match at least $\mathrm{poly}(1/\varepsilon)$ moments of the
standard Gaussian fool constant-degree PTFs (up to error $\varepsilon$). As a
secondary result, we prove that a direct approach to show testable learning
(without fooling), which was successfully used for halfspaces, cannot work for
PTFs.

该研究论文介绍了可测试学习的概念，并研究了在测试者接受标准高斯数据的情况下，多项式阈值函数的可测试学习。研究结果表明，任意常数阶的多项式阈值函数在多项式时间内可以以超出误差 ε 的程度可测试地学习，与测试属性的典型模型相匹配。同时，该研究证明了直接证明可测试学习（而非愚弄测试者）的方法在多项式阈值函数上是行不通的。

多项式阈值函数可测学习

Testably Learning Polynomial Threshold Functions

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 学习工具库。

学习带有分布偏移的半空间交集：改进算法和 SQ 下界

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

We revisit the fundamental problem of learning with distribution shift, in
which a learner is given labeled samples from training distribution $D$,
unlabeled samples from test distribution $D'$ and is asked to output a
classifier with low test error. The standard approach in this setting is to
bound the loss of a classifier in terms of some notion of distance between $D$
and $D'$. These distances, however, seem difficult to compute and do not lead
to efficient algorithms.
We depart from this paradigm and define a new model called testable learning
with distribution shift, where we can obtain provably efficient algorithms for
certifying the performance of a classifier on a test distribution. In this
model, a learner outputs a classifier with low test error whenever samples from
$D$ and $D'$ pass an associated test; moreover, the test must accept if the
marginal of $D$ equals the marginal of $D'$. We give several positive results
for learning well-studied concept classes such as halfspaces, intersections of
halfspaces, and decision trees when the marginal of $D$ is Gaussian or uniform
on $\{\pm 1\}^d$. Prior to our work, no efficient algorithms for these basic
cases were known without strong assumptions on $D'$.
For halfspaces in the realizable case (where there exists a halfspace
consistent with both $D$ and $D'$), we combine a moment-matching approach with
ideas from active learning to simulate an efficient oracle for estimating
disagreement regions. To extend to the non-realizable setting, we apply recent
work from testable (agnostic) learning. More generally, we prove that any
function class with low-degree $L_2$-sandwiching polynomial approximators can
be learned in our model. We apply constructions from the pseudorandomness
literature to obtain the required approximators.

在学习分布转移的基本问题中，我们提出了一个新模型，称为可测试学习，可以通过一个相关的测试来得到分类器在测试分布上的性能证明，并证明了对于一些常见概念类别如半空间、半空间的交、决策树等，以及具有低次 $L_2$- 夹逼多项式逼近器的任何函数类别都可以在这个模型下学习。