Machine learning algorithms are often used in environments which are not
captured accurately even by the most carefully obtained training data, either
due to the possibility of `adversarial' test-time attacks, or on account of
`natural' distribution shift. For test-time attacks, we introduce and analyze a
novel robust reliability guarantee, which requires a learner to output
predictions along with a reliability radius $\eta$, with the meaning that its
prediction is guaranteed to be correct as long as the adversary has not
perturbed the test point farther than a distance $\eta$. We provide learners
that are optimal in the sense that they always output the best possible
reliability radius on any test point, and we characterize the reliable region,
i.e. the set of points where a given reliability radius is attainable. We
additionally analyze reliable learners under distribution shift, where the test
points may come from an arbitrary distribution Q different from the training
distribution P. For both cases, we bound the probability mass of the reliable
region for several interesting examples, for linear separators under nearly
log-concave and s-concave distributions, as well as for smooth boundary
classifiers under smooth probability distributions.

本文讨论机器学习算法在环境未完全准确的情况下的应用，尤其是面对对抗攻击和分布变化的情况下，引入新的鲁棒性可靠性保证，并提供优秀的学习方案，分析了可靠性区域，同时分别分析了近似对数凹分布和平滑概率分布下的线性分类器和光滑边界分类器的可靠性区域中可靠性区域的概率质量上界。