We present a transductive learning algorithm that takes as input training
examples from a distribution $P$ and arbitrary (unlabeled) test examples,
possibly chosen by an adversary. This is unlike prior work that assumes that
test examples are small perturbations of $P$. Our algorithm outputs a selective
classifier, which abstains from predicting on some examples. By considering
selective transductive learning, we give the first nontrivial guarantees for
learning classes of bounded VC dimension with arbitrary train and test
distributions---no prior guarantees were known even for simple classes of
functions such as intervals on the line. In particular, for any function in a
class $C$ of bounded VC dimension, we guarantee a low test error rate and a low
rejection rate with respect to $P$. Our algorithm is efficient given an
Empirical Risk Minimizer (ERM) for $C$. Our guarantees hold even for test
examples chosen by an unbounded white-box adversary. We also give guarantees
for generalization, agnostic, and unsupervised settings.

介绍了一种基于跨学科学习和选择性分类器的学习算法，该算法可以适用于没有标签的测试集，同时保证了学习的分类器在测试集上的误差率和拒绝率。

超越扰动：使用任意敌对测试示例学习保证

Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial  Test Examples

A selective classifier (f,g) comprises a classification function f and a
binary selection function g, which determines if the classifier abstains from
prediction, or uses f to predict. The classifier is called
pointwise-competitive if it classifies each point identically to the best
classifier in hindsight (from the same class), whenever it does not abstain.
The quality of such a classifier is quantified by its rejection mass, defined
to be the probability mass of the points it rejects. A "fast" rejection rate is
achieved if the rejection mass is bounded from above by O(1/m) where m is the
number of labeled examples used to train the classifier (and O hides
logarithmic factors). Pointwise-competitive selective (PCS) classifiers are
intimately related to disagreement-based active learning and it is known that
in the realizable case, a fast rejection rate of a known PCS algorithm (called
Consistent Selective Strategy) is equivalent to an exponential speedup of the
well-known CAL active algorithm.
We focus on the agnostic setting, for which there is a known algorithm called
LESS that learns a PCS classifier and achieves a fast rejection rate (depending
on Hanneke's disagreement coefficient) under strong assumptions. We present an
improved PCS learning algorithm called ILESS for which we show a fast rate
(depending on Hanneke's disagreement coefficient) without any assumptions. Our
rejection bound smoothly interpolates the realizable and agnostic settings. The
main result of this paper is an equivalence between the following three
entities: (i) the existence of a fast rejection rate for any PCS learning
algorithm (such as ILESS); (ii) a poly-logarithmic bound for Hanneke's
disagreement coefficient; and (iii) an exponential speedup for a new
disagreement-based active learner called ActiveiLESS.

本研究提出了改进的 PCS 算法 ILESS，它可以在不需要任何假设的情况下实现快速拒绝率，并证明了 Hanneke 不一致系数的多对数界与任何 PCS 学习算法（如 ILESS）存在快速拒绝率以及新的基于不一致性的主动学习算法 ActiveiLESS 的指数加速之间具有等价性。