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

We study the problem of learning Single-Index Models under the $L_2^2$ loss
in the agnostic model. We give an efficient learning algorithm, achieving a
constant factor approximation to the optimal loss, that succeeds under a range
of distributions (including log-concave distributions) and a broad class of
monotone and Lipschitz link functions. This is the first efficient constant
factor approximate agnostic learner, even for Gaussian data and for any
nontrivial class of link functions. Prior work for the case of unknown link
function either works in the realizable setting or does not attain constant
factor approximation. The main technical ingredient enabling our algorithm and
analysis is a novel notion of a local error bound in optimization that we term
alignment sharpness and that may be of broader interest.

在罚函数为 $L_2^2$ 的超验模型中，我们研究了学习单指数模型的问题，并提出了一种高效的学习算法，它在一系列分布和广泛类别的单调和 Lipschitz 链函数下，能够以常数因子逼近最优损失。这是第一个高效的常数因子逼近超验学习器，甚至适用于高斯数据和任何非平凡的链函数类别。我们算法与分析的主要技术要素是优化中的一种新概念，我们称之为对齐锐度，这可能具有更广泛的兴趣。

通过对齐锐度强大地学习单指数模型

Robustly Learning Single-Index Models via Alignment Sharpness

$ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a
concept class $C$ is the most common way to measure its "richness." In the PAC
model $$ \Theta\Big(\frac{d}{\eps} + \frac{\log(1/\delta)}{\eps}\Big) $$
examples are necessary and sufficient for a learner to output, with probability
$1-\delta$, a hypothesis $h$ that is $\eps$-close to the target concept $c$. In
the related agnostic model, where the samples need not come from a $c\in C$, we
know that $$ \Theta\Big(\frac{d}{\eps^2} + \frac{\log(1/\delta)}{\eps^2}\Big)
$$ examples are necessary and sufficient to output an hypothesis $h\in C$ whose
error is at most $\eps$ worse than the best concept in $C$.
Here we analyze quantum sample complexity, where each example is a coherent
quantum state. This model was introduced by Bshouty and Jackson, who showed
that quantum examples are more powerful than classical examples in some
fixed-distribution settings. However, Atici and Servedio, improved by Zhang,
showed that in the PAC setting, quantum examples cannot be much more powerful:
the required number of quantum examples is $$
\Omega\Big(\frac{d^{1-\eta}}{\eps} + d + \frac{\log(1/\delta)}{\eps}\Big)\mbox{
for all }\eta> 0. $$ Our main result is that quantum and classical sample
complexity are in fact equal up to constant factors in both the PAC and
agnostic models. We give two approaches. The first is a fairly simple
information-theoretic argument that yields the above two classical bounds and
yields the same bounds for quantum sample complexity up to a $\log(d/\eps)$
factor. We then give a second approach that avoids the log-factor loss, based
on analyzing the behavior of the "Pretty Good Measurement" on the quantum state
identification problems that correspond to learning. This shows classical and
quantum sample complexity are equal up to constant factors.

在本文中，我们研究了量子样本复杂性，使用了二种方法证明了量子和经典样本复杂性在 PAC 和 agnostic 模型上差不多，其中第一种方法可以得到与经典边界相同或仅相差一个对数的量子边界，而第二种方法可以不丧失对数因子的情况下完成分析。