We study the problem of learning predictors that are robust to adversarial
examples with respect to an unknown perturbation set, relying instead on
interaction with an adversarial attacker or access to attack oracles, examining
different models for such interactions. We obtain upper bounds on the sample
complexity and upper and lower bounds on the number of required interactions,
or number of successful attacks, in different interaction models, in terms of
the VC and Littlestone dimensions of the hypothesis class of predictors, and
without any assumptions on the perturbation set.

研究在未知扰动集合情况下，通过与攻击者的交互或访问攻击预测器来学习对抗性示例下的鲁棒性预测器问题，并考虑不同交互模型，对预测器假设类的 VC 和 Littlestone 维度进行样本复杂度上界，以及所需交互或成功攻击次数的上下界，无需对扰动集合进行任何假设。

未知扰动集下的对抗性鲁棒学习

Adversarially Robust Learning with Unknown Perturbation Sets

As algorithms increasingly inform and influence decisions made about
individuals, it becomes increasingly important to address concerns that these
algorithms might be discriminatory. The output of an algorithm can be
discriminatory for many reasons, most notably: (1) the data used to train the
algorithm might be biased (in various ways) to favor certain populations over
others; (2) the analysis of this training data might inadvertently or
maliciously introduce biases that are not borne out in the data. This work
focuses on the latter concern.
We develop and study multicalbration -- a new measure of algorithmic fairness
that aims to mitigate concerns about discrimination that is introduced in the
process of learning a predictor from data. Multicalibration guarantees accurate
(calibrated) predictions for every subpopulation that can be identified within
a specified class of computations. We think of the class as being quite rich;
in particular, it can contain many overlapping subgroups of a protected group.
We show that in many settings this strong notion of protection from
discrimination is both attainable and aligned with the goal of obtaining
accurate predictions. Along the way, we present new algorithms for learning a
multicalibrated predictor, study the computational complexity of this task, and
draw new connections to computational learning models such as agnostic
learning.

针对算法可能存在的歧视问题，该研究提出了一种新的算法公平度量标准，名为 multicalibration，保证对每个子人群的预测都准确，从而实现更加精准的预测和防止歧视问题的出现。