过度参数化模型即使与传统的减轻失衡技术结合使用，在存在数据失衡的情况下也无法很好地概括。本文着重于分类数据集，其中一小部分人口（少数​​）可能包含与类标签相关的功能。对于跨凝结损失修饰和代表性高斯混合模型的参数家族，我们在最严重的组误差上得出了非反应泛化的边界，该误差揭示了不同的超参数的作用。具体而言，我们证明，在适当调整后，最近提出的VS-Loss学会了一个模型，即使伪造的特征很强，也对少数群体也是公平的。另一方面，替代性启发式方法，例如加权CE和LA-loss，可能会急剧失败。与以前的作品相比，我们的界限适用于更多的通用模型，它们是非吸血管的，即使在极端不平衡的情况下，它们也适用。

标签 - 不平衡和组敏感分类中的目标是优化相关的指标，例如平衡错误和相同的机会。经典方法，例如加权交叉熵，在训练深网络到训练（TPT）的终端阶段时，这是超越零训练误差的训练。这种观察发生了最近在促进少数群体更大边值的直观机制之后开发启发式替代品的动力。与之前的启发式相比，我们遵循原则性分析，说明不同的损失调整如何影响边距。首先，我们证明，对于在TPT中训练的所有线性分类器，有必要引入乘法，而不是添加性的Logit调整，以便对杂项边缘进行适当的变化。为了表明这一点，我们发现将乘法CE修改的连接到成本敏感的支持向量机。也许是违反，我们还发现，在培训开始时，相同的乘法权重实际上可以损害少数群体。因此，虽然在TPT中，添加剂调整无效，但我们表明它们可以通过对乘法重量的初始负效应进行抗衡来加速会聚。通过这些发现的动机，我们制定了矢量缩放（VS）丢失，即捕获现有技术作为特殊情况。此外，我们引入了对群体敏感分类的VS损失的自然延伸，从而以统一的方式处理两种常见类型的不平衡（标签/组）。重要的是，我们对最先进的数据集的实验与我们的理论见解完全一致，并确认了我们算法的卓越性能。最后，对于不平衡的高斯 - 混合数据，我们执行泛化分析，揭示平衡/标准错误和相同机会之间的权衡。

重要性加权是一种处理分销班次的经典技术。然而，事先工作呈现出强大的实证和理论证据，证明重要性重量对过度分辨的神经网络没有影响。重要性加权与过度分辨率的神经网络的培训真正不相容吗？我们的论文在负面回答。我们表明重要的权重不是因为过度分辨率，而是因为使用像物流或交叉熵损失等指数尾损失。作为一种补救措施，我们表明多项式尾损失恢复了重要性重量在校正过度分配模型中的分布换档的影响。我们表征了梯度下降的行为，其具有过度分辨的线性模型的重要性加权多项式损耗，并且理论上证明了在标签换档设置中使用多环尾损失的优点。令人惊讶的是，我们的理论表明，使用通过以指数来引入经典无偏的重要性重量而获得的权重可以提高性能。最后，我们展示了我们对亚潜班班和标签移位数据集的神经网络实验的分析的实际价值。重新重复时，我们的损耗函数可以在测试精度的高达9％的跨熵优先于重复的交叉熵。我们的损耗功能还提供了与校正分配换档的最先进的方法可比或甚至超过的测试精度。

神经塌陷是指表征类嵌入和分类器重量的几何形状的显着结构特性，当经过零训练误差以外的训练时，深网被发现。但是，这种表征仅适用于平衡数据。因此，我们在这里询问是否可以使阶级失衡不变。为此，我们采用了不受限制的功能模型（UFM），这是一种用于研究神经塌陷的最新理论模型，并引入了单纯形编码标签的插值（SELI）作为神经崩溃现象的不变特征。具体而言，我们证明了UFM的跨凝结损失和消失的正则化，无论阶级失衡如何，嵌入和分类器总是插入单纯形编码的标签矩阵，并且其单个几何形状都由同一标签矩阵矩阵矩阵的SVD因子确定。然后，我们对合成和真实数据集进行了广泛的实验，这些实验确认了与SELI几何形状的收敛。但是，我们警告说，融合会随着不平衡的增加而恶化。从理论上讲，我们通过表明与平衡的情况不同，当存在少数民族时，山脊规范化在调整几何形状中起着至关重要的作用。这定义了新的问题，并激发了对阶级失衡对一阶方法融合其渐近优先解决方案的速率的影响的进一步研究。

Learned classifiers should often possess certain invariance properties meant to encourage fairness, robustness, or out-of-distribution generalization. However, multiple recent works empirically demonstrate that common invariance-inducing regularizers are ineffective in the over-parameterized regime, in which classifiers perfectly fit (i.e. interpolate) the training data. This suggests that the phenomenon of ``benign overfitting," in which models generalize well despite interpolating, might not favorably extend to settings in which robustness or fairness are desirable. In this work we provide a theoretical justification for these observations. We prove that -- even in the simplest of settings -- any interpolating learning rule (with arbitrarily small margin) will not satisfy these invariance properties. We then propose and analyze an algorithm that -- in the same setting -- successfully learns a non-interpolating classifier that is provably invariant. We validate our theoretical observations on simulated data and the Waterbirds dataset.

过度分化的深网络的泛化神秘具有有动力的努力，了解梯度下降（GD）如何收敛到概括井的低损耗解决方案。现实生活中的神经网络从小随机值初始化，并以分类的“懒惰”或“懒惰”或“NTK”的训练训练，分析更成功，以及最近的结果序列（Lyu和Li ，2020年; Chizat和Bach，2020; Ji和Telgarsky，2020）提供了理论证据，即GD可以收敛到“Max-ramin”解决方案，其零损失可能呈现良好。但是，仅在某些环境中证明了余量的全球最优性，其中神经网络无限或呈指数级宽。目前的纸张能够为具有梯度流动训练的两层泄漏的Relu网，无论宽度如何，都能为具有梯度流动的双层泄漏的Relu网建立这种全局最优性。分析还为最近的经验研究结果（Kalimeris等，2019）给出了一些理论上的理由，就GD的所谓简单的偏见为线性或其他“简单”的解决方案，特别是在训练中。在悲观方面，该论文表明这种结果是脆弱的。简单的数据操作可以使梯度流量会聚到具有次优裕度的线性分类器。

良性过度拟合，即插值模型在存在嘈杂数据的情况下很好地推广的现象，首先是在接受梯度下降训练的神经网络模型中观察到的。为了更好地理解这一经验观察，我们考虑了通过梯度下降训练的两层神经网络的概括误差，后者是随机初始化后的逻辑损失。我们假设数据来自分离良好的集体条件对数符合分布，并允许训练标签的持续部分被对手损坏。我们表明，在这种情况下，神经网络表现出良性过度拟合：它们可以驱动到零训练错误，完美拟合所有嘈杂的训练标签，并同时达到最小值最佳测试错误。与以前需要线性或基于内核预测的良性过度拟合的工作相反，我们的分析在模型和学习动力学基本上是非线性的环境中。

尽管过度参数化的模型已经在许多机器学习任务上表现出成功，但与培训不同的测试分布的准确性可能会下降。这种准确性下降仍然限制了在野外应用机器学习的限制。同时，重要的加权是一种处理分配转移的传统技术，已被证明在经验和理论上对过度参数化模型的影响较小甚至没有影响。在本文中，我们提出了重要的回火来改善决策界限，并为过度参数化模型取得更好的结果。从理论上讲，我们证明在标签移位和虚假相关设置下，组温度的选择可能不同。同时，我们还证明正确选择的温度可以解脱出少数群体崩溃的分类不平衡。从经验上讲，我们使用重要性回火来实现最严重的小组分类任务的最新结果。

在负面的感知问题中，我们给出了$ n $数据点$（{\ boldsymbol x} _i，y_i）$，其中$ {\ boldsymbol x} _i $是$ d $ -densional vector和$ y_i \ in \ { + 1，-1 \} $是二进制标签。数据不是线性可分离的，因此我们满足自己的内容，以找到最大的线性分类器，具有最大的\ emph {否定}余量。换句话说，我们想找到一个单位常规矢量$ {\ boldsymbol \ theta} $，最大化$ \ min_ {i \ le n} y_i \ langle {\ boldsymbol \ theta}，{\ boldsymbol x} _i \ rangle $ 。这是一个非凸优化问题（它相当于在Polytope中找到最大标准矢量），我们在两个随机模型下研究其典型属性。我们考虑比例渐近，其中$ n，d \ to \ idty $以$ n / d \ to \ delta $，并在最大边缘$ \ kappa _ {\ text {s}}（\ delta）上证明了上限和下限）$或 - 等效 - 在其逆函数$ \ delta _ {\ text {s}}（\ kappa）$。换句话说，$ \ delta _ {\ text {s}}（\ kappa）$是overparametization阈值：以$ n / d \ le \ delta _ {\ text {s}}（\ kappa） - \ varepsilon $一个分类器实现了消失的训练错误，具有高概率，而以$ n / d \ ge \ delta _ {\ text {s}}（\ kappa）+ \ varepsilon $。我们在$ \ delta _ {\ text {s}}（\ kappa）$匹配，以$ \ kappa \ to - \ idty $匹配。然后，我们分析了线性编程算法来查找解决方案，并表征相应的阈值$ \ delta _ {\ text {lin}}（\ kappa）$。我们观察插值阈值$ \ delta _ {\ text {s}}（\ kappa）$和线性编程阈值$ \ delta _ {\ text {lin {lin}}（\ kappa）$之间的差距，提出了行为的问题其他算法。

当数据自然分配到通过基础图的代理商之间，分散学习提供了隐私和沟通效率。通过过度参数化的学习设置，在该设置中，在该设置中训练了零训练损失，我们研究了分散学习的分散学习算法和概括性能，并在可分离的数据上下降。具体而言，对于分散的梯度下降（DGD）和各种损失函数，在无穷大（包括指数损失和逻辑损失）中渐近为零，我们得出了新的有限时间泛化界限。这补充了一长串最近的工作，该工作研究了概括性能和梯度下降的隐含偏见，而不是可分离的数据，但迄今为止，梯度下降的偏见仅限于集中学习方案。值得注意的是，我们的概括范围匹配其集中式同行。这背后的关键和独立感兴趣的是，在一类自我结合的损失方面建立了关于训练损失和DGD的传记率的新界限。最后，在算法方面，我们设计了改进的基于梯度的例程，可分离数据，并在经验上证明了训练和概括性能方面的加速命令。

现代神经网络通常具有很大的表现力，并且可以接受训练以使培训数据过高，同时仍能达到良好的测试性能。这种现象被称为“良性过度拟合”。最近，从理论角度出现了一系列研究“良性过度拟合”的作品。但是，它们仅限于线性模型或内核/随机特征模型，并且仍然缺乏关于何时以及如何在神经网络中发生过度拟合的理论理解。在本文中，我们研究了训练两层卷积神经网络（CNN）的良性过度拟合现象。我们表明，当信噪比满足一定条件时，通过梯度下降训练的两层CNN可以实现任意小的训练和测试损失。另一方面，当这种情况无法成立时，过度拟合就会有害，并且获得的CNN只能实现恒定的测试损失。这些共同证明了由信噪比驱动的良性过度拟合和有害过度拟合之间的急剧过渡。据我们所知，这是第一部精确地表征良性过度拟合在训练卷积神经网络中的条件的工作。

具有动量的随机梯度下降（SGD）被广泛用于训练现代深度学习体系结构。虽然可以很好地理解使用动量可以导致在各种环境中更快的收敛速率，但还观察到动量会产生更高的概括。先前的工作认为，动量在训练过程中稳定了SGD噪声，这会导致更高的概括。在本文中，我们采用了另一种观点，并首先在经验上表明，与梯度下降（GD）相比，具有动量（GD+M）的梯度下降在某些深度学习问题中显着改善了概括。从这个观察结果，我们正式研究了动量如何改善概括。我们设计了一个二进制分类设置，在该设置中，当两种算法都类似地初始化时，经过GD+M训练的单个隐藏层（过度参数化）卷积神经网络比使用GD训练的同一网络更好地概括了。我们分析中的关键见解是，动量在示例共享某些功能但边距不同的数据集中是有益的。与记住少量数据数据的GD相反，GD+M仍然通过其历史梯度来了解这些数据中的功能。最后，我们从经验上验证了我们的理论发现。

Popular iterative algorithms such as boosting methods and coordinate descent on linear models converge to the maximum $\ell_1$-margin classifier, a.k.a. sparse hard-margin SVM, in high dimensional regimes where the data is linearly separable. Previous works consistently show that many estimators relying on the $\ell_1$-norm achieve improved statistical rates for hard sparse ground truths. We show that surprisingly, this adaptivity does not apply to the maximum $\ell_1$-margin classifier for a standard discriminative setting. In particular, for the noiseless setting, we prove tight upper and lower bounds for the prediction error that match existing rates of order $\frac{\|\wgt\|_1^{2/3}}{n^{1/3}}$ for general ground truths. To complete the picture, we show that when interpolating noisy observations, the error vanishes at a rate of order $\frac{1}{\sqrt{\log(d/n)}}$. We are therefore first to show benign overfitting for the maximum $\ell_1$-margin classifier.

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.

最新工作的一条有影响力的线重点关注的是针对可分离的线性分类的非规范梯度学习程序的泛化特性，并具有指数级的损失函数。这种方法概括地概括的能力归因于它们对大幅度预测指标的隐含偏见，无论是渐近的还是有限的时间。我们为此概括提供了另一个统一的解释，并将其与优化目标的两个简单属性相关联，我们将其称为可实现性和自我限制性。我们介绍了通过这些特性的不受约束随机凸优化的一般设置，并通过算法稳定性镜头分析梯度方法的概括。在这种更广泛的环境中，我们获得了梯度下降和随机梯度下降的尖锐稳定性边界，这些梯度下降即使适用于大量梯度步骤，并使用它们来得出这些算法的通用泛化界限。最后，作为一般边界的直接应用，我们返回使用可分离数据的线性分类设置，并为梯度下降和随机梯度下降建立了几种新颖的测试损失和测试精度界限，用于各种尾巴衰减速率的多种损耗函数。在某些情况下，我们的界限显着改善了文献中现有的概括误差界限。

成功的深度学习模型往往涉及培训具有比训练样本数量更多的参数的神经网络架构。近年来已经广泛研究了这种超分子化的模型，并且通过双下降现象和通过优化景观的结构特性，从统计的角度和计算视角都建立了过分统计化的优点。尽管在过上分层的制度中深入学习架构的显着成功，但也众所周知，这些模型对其投入中的小对抗扰动感到高度脆弱。即使在普遍培训的情况下，它们在扰动输入（鲁棒泛化）上的性能也会比良性输入（标准概括）的最佳可达到的性能更糟糕。因此，必须了解如何从根本上影响稳健性的情况下如何影响鲁棒性。在本文中，我们将通过专注于随机特征回归模型（具有随机第一层权重的两层神经网络）来提供超分度化对鲁棒性的作用的精确表征。我们考虑一个制度，其中样本量，输入维度和参数的数量彼此成比例地生长，并且当模型发生前列地训练时，可以为鲁棒泛化误差导出渐近精确的公式。我们的发达理论揭示了过分统计化对鲁棒性的非竞争效果，表明对于普遍训练的随机特征模型，高度公正化可能会损害鲁棒泛化。

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

我们考虑估计与I.I.D的排名$ 1 $矩阵因素的问题。高斯，排名$ 1 $的测量值，这些测量值非线性转化和损坏。考虑到非线性的两种典型选择，我们研究了从随机初始化开始的此非convex优化问题的天然交流更新规则的收敛性能。我们通过得出确定性递归，即使在高维问题中也是准确的，我们显示出算法的样本分割版本的敏锐收敛保证。值得注意的是，虽然无限样本的种群更新是非信息性的，并提示单个步骤中的精确恢复，但算法 - 我们的确定性预测 - 从随机初始化中迅速地收敛。我们尖锐的非反应分析也暴露了此问题的其他几种细粒度，包括非线性和噪声水平如何影响收敛行为。从技术层面上讲，我们的结果可以通过证明我们的确定性递归可以通过我们的确定性顺序来预测我们的确定性序列，而当每次迭代都以$ n $观测来运行时，我们的确定性顺序可以通过$ n^{ - 1/2} $的波动。我们的技术利用了源自有关高维$ m $估计文献的遗留工具，并为通过随机数据的其他高维优化问题的随机初始化而彻底地分析了高阶迭代算法的途径。

Iterative regularization is a classic idea in regularization theory, that has recently become popular in machine learning. On the one hand, it allows to design efficient algorithms controlling at the same time numerical and statistical accuracy. On the other hand it allows to shed light on the learning curves observed while training neural networks. In this paper, we focus on iterative regularization in the context of classification. After contrasting this setting with that of regression and inverse problems, we develop an iterative regularization approach based on the use of the hinge loss function. More precisely we consider a diagonal approach for a family of algorithms for which we prove convergence as well as rates of convergence. Our approach compares favorably with other alternatives, as confirmed also in numerical simulations.

现代机器学习问题中的不平衡数据集是司空见惯的。具有敏感属性的代表性课程或群体的存在导致关于泛化和公平性的担忧。这种担忧进一步加剧了大容量深网络可以完全适合培训数据，似乎在训练期间达到完美的准确性和公平，但在测试期间表现不佳。为了解决这些挑战，我们提出了自动化，一个自动设计培训损失功能的双层优化框架，以优化准确性和寻求公平目标的混合。具体地，较低级别的问题列举了模型权重，并且上级问题通过监视和优化通过验证数据的期望目标来调谐损耗功能。我们的损耗设计通过采用参数跨熵损失和个性化数据增强方案，可以为类/组进行个性化处理。我们评估我们对不平衡和群体敏感分类的应用方案的方法的好处和性能。广泛的经验评估表明了自动矛盾最先进的方法的益处。我们的实验结果与损耗功能设计的理论见解和培训验证分裂的好处相辅相成。所有代码都是可用的开源。