在监督的学习中，已经表明，在许多情况下，数据中的标签噪声可以插值而不会受到测试准确性的处罚。我们表明，插值标签噪声会引起对抗性脆弱性，并证明了第一个定理显示标签噪声和对抗性风险在数据分布方面的依赖性。我们的结果几乎是尖锐的，而没有考虑学习算法的电感偏差。我们还表明，感应偏置使标签噪声的效果更强。

Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high "standard" accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of "standard" learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

众所周知，现代神经网络容易受到对抗例子的影响。为了减轻这个问题，已经提出了一系列强大的学习算法。但是，尽管通过某些方法可以通过某些方法接近稳定的训练误差，但所有现有的算法都会导致较高的鲁棒概括误差。在本文中，我们从深层神经网络的表达能力的角度提供了对这种令人困惑的现象的理论理解。具体而言，对于二进制分类数据，我们表明，对于Relu网络，虽然轻度的过度参数足以满足较高的鲁棒训练精度，但存在持续的稳健概括差距，除非神经网络的大小是指数的，却是指数的。数据维度$ d $。即使数据是线性可分离的，这意味着要实现低清洁概括错误很容易，我们仍然可以证明$ \ exp（{\ omega}（d））$下限可用于鲁棒概括。通常，只要它们的VC维度最多是参数数量，我们的指数下限也适用于各种神经网络家族和其他功能类别。此外，我们为网络大小建立了$ \ exp（{\ mathcal {o}}（k））$的改进的上限，当数据放在具有内在尺寸$ k $的歧管上时，以实现低鲁棒的概括错误（$） k \ ll d $）。尽管如此，我们也有一个下限，相对于$ k $成倍增长 - 维度的诅咒是不可避免的。通过证明网络大小之间的指数分离以实现较低的鲁棒训练和泛化错误，我们的结果表明，鲁棒概括的硬度可能源于实用模型的表现力。

后门数据中毒攻击是一种对抗的攻击，其中攻击者将几个水印，误标记的训练示例注入训练集中。水印不会影响典型数据模型的测试时间性能;但是，该模型在水印示例中可靠地错误。为获得对后门数据中毒攻击的更好的基础认识，我们展示了一个正式的理论框架，其中一个人可以讨论对分类问题的回溯数据中毒攻击。然后我们使用它来分析这些攻击的重要统计和计算问题。在统计方面，我们识别一个参数，我们称之为记忆能力，捕捉到后门攻击的学习问题的内在脆弱性。这使我们能够争论几个自然学习问题的鲁棒性与后门攻击。我们的结果，攻击者涉及介绍后门攻击的明确建设，我们的鲁棒性结果表明，一些自然问题设置不能产生成功的后门攻击。从计算的角度来看，我们表明，在某些假设下，对抗训练可以检测训练集中的后门的存在。然后，我们表明，在类似的假设下，我们称之为呼叫滤波和鲁棒概括的两个密切相关的问题几乎等同。这意味着它既是渐近必要的，并且足以设计算法，可以识别训练集中的水印示例，以便获得既广泛概念的学习算法，以便在室外稳健。

我们考虑使用对抗鲁棒性学习的样本复杂性。对于此问题的大多数现有理论结果已经考虑了数据中不同类别在一起或重叠的设置。通过一些实际应用程序，我们认为，相比之下，存在具有完美精度和稳健性的分类器的分类器的良好分离的情况，并表明样品复杂性叙述了一个完全不同的故事。具体地，对于线性分类器，我们显示了大类分离的分布式，其中任何算法的预期鲁棒丢失至少是$ \ω（\ FRAC {D} {n}）$，而最大边距算法已预期标准亏损$ o（\ frac {1} {n}）$。这表明了通过现有技术不能获得的标准和鲁棒损耗中的间隙。另外，我们介绍了一种算法，给定鲁棒率半径远小于类之间的间隙的实例，给出了预期鲁棒损失的解决方案是$ O（\ FRAC {1} {n}）$。这表明，对于非常好的数据，可实现$ O（\ FRAC {1} {n}）$的收敛速度，否则就是这样。我们的结果适用于任何$ \ ell_p $ norm以$ p> 1 $（包括$ p = \ idty $）为稳健。

“良性过度装备”，分类器记住嘈杂的培训数据仍然达到良好的概括性表现，在机器学习界造成了很大的关注。为了解释这种令人惊讶的现象，一系列作品在过度参数化的线性回归，分类和内核方法中提供了理论典范。然而，如果在对逆势实例存在下仍发生良性的过度，则尚不清楚，即欺骗分类器的微小和有意的扰动的例子。在本文中，我们表明，良性过度确实发生在对抗性培训中，是防御对抗性实例的原则性的方法。详细地，我们证明了在$ \ ell_p $普发的扰动下的子高斯数据的混合中的普遍培训的线性分类器的风险限制。我们的结果表明，在中度扰动下，尽管过度禁止嘈杂的培训数据，所以发生前列训练的线性分类器可以实现近乎最佳的标准和对抗性风险。数值实验验证了我们的理论发现。

解决机器学习模型的公平关注是朝着实际采用现实世界自动化系统中的至关重要的一步。尽管已经开发了许多方法来从数据培训公平模型，但对这些方法对数据损坏的鲁棒性知之甚少。在这项工作中，我们考虑在最坏情况下的数据操作下进行公平意识学习。我们表明，在某些情况下，对手可能会迫使任何学习者返回过度偏见的分类器，无论样本量如何，有或没有降解的准确性，并且多余的偏见的强度会增加数据中数据不足的受保护组的学习问题，而数据中有代表性不足的组。我们还证明，我们的硬度结果紧密到不断的因素。为此，我们研究了两种自然学习算法，以优化准确性和公平性，并表明这些算法在损坏比和较大数据限制中受保护的群体频率方面享有订单最佳的保证。

State-of-the-art results on image recognition tasks are achieved using over-parameterized learning algorithms that (nearly) perfectly fit the training set and are known to fit well even random labels. This tendency to memorize the labels of the training data is not explained by existing theoretical analyses. Memorization of the training data also presents significant privacy risks when the training data contains sensitive personal information and thus it is important to understand whether such memorization is necessary for accurate learning.We provide the first conceptual explanation and a theoretical model for this phenomenon. Specifically, we demonstrate that for natural data distributions memorization of labels is necessary for achieving closeto-optimal generalization error. Crucially, even labels of outliers and noisy labels need to be memorized. The model is motivated and supported by the results of several recent empirical works. In our model, data is sampled from a mixture of subpopulations and our results show that memorization is necessary whenever the distribution of subpopulation frequencies is long-tailed. Image and text data is known to be long-tailed and therefore our results establish a formal link between these empirical phenomena. Our results allow to quantify the cost of limiting memorization in learning and explain the disparate effects that privacy and model compression have on different subgroups.

Existing generalization bounds fail to explain crucial factors that drive generalization of modern neural networks. Since such bounds often hold uniformly over all parameters, they suffer from over-parametrization, and fail to account for the strong inductive bias of initialization and stochastic gradient descent. As an alternative, we propose a novel optimal transport interpretation of the generalization problem. This allows us to derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the earned prediction function in the data space. Therefore, our bounds are agnostic to the parametrization of the model and work well when the number of training samples is much smaller than the number of parameters. With small modifications, our approach yields accelerated rates for data on low-dimensional manifolds, and guarantees under distribution shifts. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.

对对抗性示例强大的学习分类器已经获得了最近的关注。标准强大学习框架的主要缺点是人为强大的RADIUS $ R $，适用于所有输入。这忽略了数据可能是高度异构的事实，在这种情况下，它是合理的，在某些数据区域中，鲁棒性区域应该更大，并且在其他区域中更小。在本文中，我们通过提出名为邻域最佳分类器的新限制分类器来解决此限制，该分类通过使用最接近的支持点的标签扩展其支持之外的贝叶斯最佳分类器。然后，我们认为该分类器可能会使其稳健性区域的大小最大化，但受到等于贝叶斯的准确性的约束。然后，我们存在足够的条件，该条件下可以表示为重量函数的一般非参数方法会聚在此限制，并且显示最近的邻居和内核分类器在某些条件下满足它们。

当前，随机平滑被认为是获得确切可靠分类器的最新方法。尽管其表现出色，但该方法仍与各种严重问题有关，例如``认证准确性瀑布''，认证与准确性权衡甚至公平性问题。已经提出了依赖输入的平滑方法，目的是克服这些缺陷。但是，我们证明了这些方法缺乏正式的保证，因此所产生的证书是没有道理的。我们表明，一般而言，输入依赖性平滑度遭受了维数的诅咒，迫使方差函数具有低半弹性。另一方面，我们提供了一个理论和实用的框架，即使在严格的限制下，即使在有维度的诅咒的情况下，即使在存在维度的诅咒的情况下，也可以使用依赖输入的平滑。我们提供平滑方差功能的一种混凝土设计，并在CIFAR10和MNIST上进行测试。我们的设计减轻了经典平滑的一些问题，并正式下划线，但仍需要进一步改进设计。

We establish a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in the sense that they retain accuracy even if a constant fraction of the samples they receive are adversarially corrupted. Since optimal mechanisms typically achieve these high success probabilities, our results imply that optimal private mechanisms for many basic statistics problems are robust. We investigate the consequences of this observation for both algorithms and computational complexity across different statistical problems. Assuming the Brennan-Bresler secret-leakage planted clique conjecture, we demonstrate a fundamental tradeoff between computational efficiency, privacy leakage, and success probability for sparse mean estimation. Private algorithms which match this tradeoff are not yet known -- we achieve that (up to polylogarithmic factors) in a polynomially-large range of parameters via the Sum-of-Squares method. To establish an information-computation gap for private sparse mean estimation, we also design new (exponential-time) mechanisms using fewer samples than efficient algorithms must use. Finally, we give evidence for privacy-induced information-computation gaps for several other statistics and learning problems, including PAC learning parity functions and estimation of the mean of a multivariate Gaussian.

可实现和不可知性的可读性的等价性是学习理论的基本现象。与PAC学习和回归等古典设置范围的变种，近期趋势，如对冲强劲和私人学习，我们仍然缺乏统一理论;等同性的传统证据往往是不同的，并且依赖于强大的模型特异性假设，如统一的收敛和样本压缩。在这项工作中，我们给出了第一个独立的框架，解释了可实现和不可知性的可读性的等价性：三行黑箱减少简化，统一，并在各种各样的环境中扩展了我们的理解。这包括没有已知的学报的模型，例如学习任意分布假设或一般损失，以及许多其他流行的设置，例如强大的学习，部分学习，公平学习和统计查询模型。更一般地，我们认为可实现和不可知的学习的等价性实际上是我们调用属性概括的更广泛现象的特殊情况：可以满足有限的学习算法（例如\噪声公差，隐私，稳定性）的任何理想性质假设类（可能在某些变化中）延伸到任何学习的假设类。

We show how to turn any classifier that classifies well under Gaussian noise into a new classifier that is certifiably robust to adversarial perturbations under the 2 norm. This "randomized smoothing" technique has been proposed recently in the literature, but existing guarantees are loose. We prove a tight robustness guarantee in 2 norm for smoothing with Gaussian noise. We use randomized smoothing to obtain an ImageNet classifier with e.g. a certified top-1 accuracy of 49% under adversarial perturbations with 2 norm less than 0.5 (=127/255). No certified defense has been shown feasible on ImageNet except for smoothing. On smaller-scale datasets where competing approaches to certified 2 robustness are viable, smoothing delivers higher certified accuracies. Our strong empirical results suggest that randomized smoothing is a promising direction for future research into adversarially robust classification. Code and models are available at http: //github.com/locuslab/smoothing.

中毒攻击已成为对机器学习算法的重要安全威胁。已经证明对培训集进行小变化的对手，例如添加特制的数据点，可以损害输出模型的性能。一些更强大的中毒攻击需要全面了解培训数据。这种叶子打开了使用没有完全了解干净训练集的中毒攻击来实现相同的攻击结果的可能性。在这项工作中，我们启动了对上述问题的理论研究。具体而言，对于具有套索的特征选择的情况，我们表明全信息对手（基于培训数据的其余部分的工艺中毒示例）可从未获得培训集的最佳攻击者提供了更强的最佳攻击者数据分发。我们的分离结果表明，数据感知和数据疏忽的两个设置从根本上不同，我们不能希望在这些场景中始终达到相同的攻击或辩护。

It is widely believed that given the same labeling budget, active learning algorithms like uncertainty sampling achieve better predictive performance than passive learning (i.e. uniform sampling), albeit at a higher computational cost. Recent empirical evidence suggests that this added cost might be in vain, as uncertainty sampling can sometimes perform even worse than passive learning. While existing works offer different explanations in the low-dimensional regime, this paper shows that the underlying mechanism is entirely different in high dimensions: we prove for logistic regression that passive learning outperforms uncertainty sampling even for noiseless data and when using the uncertainty of the Bayes optimal classifier. Insights from our proof indicate that this high-dimensional phenomenon is exacerbated when the separation between the classes is small. We corroborate this intuition with experiments on 20 high-dimensional datasets spanning a diverse range of applications, from finance and histology to chemistry and computer vision.

尽管使用对抗性训练捍卫深度学习模型免受对抗性扰动的经验成功，但到目前为止，仍然不清楚对抗性扰动的存在背后的原则是什么，而对抗性培训对神经网络进行了什么来消除它们。在本文中，我们提出了一个称为特征纯化的原则，在其中，我们表明存在对抗性示例的原因之一是在神经网络的训练过程中，在隐藏的重量中积累了某些小型密集混合物；更重要的是，对抗训练的目标之一是去除此类混合物以净化隐藏的重量。我们介绍了CIFAR-10数据集上的两个实验，以说明这一原理，并且一个理论上的结果证明，对于某些自然分类任务，使用随机初始初始化的梯度下降训练具有RELU激活的两层神经网络确实满足了这一原理。从技术上讲，我们给出了我们最大程度的了解，第一个结果证明，以下两个可以同时保持使用RELU激活的神经网络。 （1）对原始数据的训练确实对某些半径的小对抗扰动确实不舒适。 （2）即使使用经验性扰动算法（例如FGM），实际上也可以证明对对抗相同半径的任何扰动也可以证明具有强大的良好性。最后，我们还证明了复杂性的下限，表明该网络的低复杂性模型，例如线性分类器，低度多项式或什至是神经切线核，无论使用哪种算法，都无法防御相同半径的扰动训练他们。

Classically, data interpolation with a parametrized model class is possible as long as the number of parameters is larger than the number of equations to be satisfied. A puzzling phenomenon in deep learning is that models are trained with many more parameters than what this classical theory would suggest. We propose a partial theoretical explanation for this phenomenon. We prove that for a broad class of data distributions and model classes, overparametrization is necessary if one wants to interpolate the data smoothly. Namely we show that smooth interpolation requires $d$ times more parameters than mere interpolation, where $d$ is the ambient data dimension. We prove this universal law of robustness for any smoothly parametrized function class with polynomial size weights, and any covariate distribution verifying isoperimetry. In the case of two-layers neural networks and Gaussian covariates, this law was conjectured in prior work by Bubeck, Li and Nagaraj. We also give an interpretation of our result as an improved generalization bound for model classes consisting of smooth functions.

Recently, Robey et al. propose a notion of probabilistic robustness, which, at a high-level, requires a classifier to be robust to most but not all perturbations. They show that for certain hypothesis classes where proper learning under worst-case robustness is \textit{not} possible, proper learning under probabilistic robustness \textit{is} possible with sample complexity exponentially smaller than in the worst-case robustness setting. This motivates the question of whether proper learning under probabilistic robustness is always possible. In this paper, we show that this is \textit{not} the case. We exhibit examples of hypothesis classes $\mathcal{H}$ with finite VC dimension that are \textit{not} probabilistically robustly PAC learnable with \textit{any} proper learning rule. However, if we compare the output of the learner to the best hypothesis for a slightly \textit{stronger} level of probabilistic robustness, we show that not only is proper learning \textit{always} possible, but it is possible via empirical risk minimization.

Neural networks with random weights appear in a variety of machine learning applications, most prominently as the initialization of many deep learning algorithms and as a computationally cheap alternative to fully learned neural networks. In the present article, we enhance the theoretical understanding of random neural networks by addressing the following data separation problem: under what conditions can a random neural network make two classes $\mathcal{X}^-, \mathcal{X}^+ \subset \mathbb{R}^d$ (with positive distance) linearly separable? We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. Crucially, the number of required neurons is explicitly linked to geometric properties of the underlying sets $\mathcal{X}^-, \mathcal{X}^+$ and their mutual arrangement. This instance-specific viewpoint allows us to overcome the usual curse of dimensionality (exponential width of the layers) in non-pathological situations where the data carries low-complexity structure. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity (based on a localized version of Gaussian mean width), which leads to sound and informative separation guarantees. We connect our result with related lines of work on approximation, memorization, and generalization.