In this paper, we theoretically study the problem of binary classification in the presence of random classification noise -the learner, instead of seeing the true labels, sees labels that have independently been flipped with some small probability. Moreover, random label noise is class-conditional -the flip probability depends on the class. We provide two approaches to suitably modify any given surrogate loss function. First, we provide a simple unbiased estimator of any loss, and obtain performance bounds for empirical risk minimization in the presence of iid data with noisy labels. If the loss function satisfies a simple symmetry condition, we show that the method leads to an efficient algorithm for empirical minimization. Second, by leveraging a reduction of risk minimization under noisy labels to classification with weighted 0-1 loss, we suggest the use of a simple weighted surrogate loss, for which we are able to obtain strong empirical risk bounds. This approach has a very remarkable consequence -methods used in practice such as biased SVM and weighted logistic regression are provably noise-tolerant. On a synthetic non-separable dataset, our methods achieve over 88% accuracy even when 40% of the labels are corrupted, and are competitive with respect to recently proposed methods for dealing with label noise in several benchmark datasets.

In this paper, we study a classification problem in which sample labels are randomly corrupted. In this scenario, there is an unobservable sample with noise-free labels. However, before being observed, the true labels are independently flipped with a probability ρ ∈ [0, 0.5), and the random label noise can be class-conditional. Here, we address two fundamental problems raised by this scenario. The first is how to best use the abundant surrogate loss functions designed for the traditional classification problem when there is label noise. We prove that any surrogate loss function can be used for classification with noisy labels by using importance reweighting, with consistency assurance that the label noise does not ultimately hinder the search for the optimal classifier of the noise-free sample. The other is the open problem of how to obtain the noise rate ρ. We show that the rate is upper bounded by the conditional probability P ( Ŷ |X) of the noisy sample. Consequently, the rate can be estimated, because the upper bound can be easily reached in classification problems. Experimental results on synthetic and real datasets confirm the efficiency of our methods.

In many applications of classifier learning, training data suffers from label noise. Deep networks are learned using huge training data where the problem of noisy labels is particularly relevant. The current techniques proposed for learning deep networks under label noise focus on modifying the network architecture and on algorithms for estimating true labels from noisy labels. An alternate approach would be to look for loss functions that are inherently noise-tolerant. For binary classification there exist theoretical results on loss functions that are robust to label noise. In this paper, we provide some sufficient conditions on a loss function so that risk minimization under that loss function would be inherently tolerant to label noise for multiclass classification problems. These results generalize the existing results on noise-tolerant loss functions for binary classification. We study some of the widely used loss functions in deep networks and show that the loss function based on mean absolute value of error is inherently robust to label noise. Thus standard back propagation is enough to learn the true classifier even under label noise. Through experiments, we illustrate the robustness of risk minimization with such loss functions for learning neural networks.

通常，用于训练排名模型的数据受到标签噪声。例如，在Web搜索中，由于ClickStream数据创建的标签是嘈杂的，这是因为诸如SERP上的项目描述中的信息不足，用户查询重新进行的，以及不稳定的或意外的用户行为。在实践中，很难处理标签噪声而不对标签生成过程做出强烈的假设。结果，如果不考虑标签噪声，从业人员通常会直接在此嘈杂的数据上训练他们的学习到秩（LTR）模型。令人惊讶的是，我们经常看到以这种方式训练的LTR模型的出色表现。在这项工作中，我们描述了一类耐噪声的LTR损失，即使在类条件标签噪声的背景下，经验风险最小化也是一致的程序。我们还开发了常用损失函数的耐噪声类似物。实验结果进一步支持了我们理论发现的实际意义。

We introduce a tunable loss function called $\alpha$-loss, parameterized by $\alpha \in (0,\infty]$, which interpolates between the exponential loss ($\alpha = 1/2$), the log-loss ($\alpha = 1$), and the 0-1 loss ($\alpha = \infty$), for the machine learning setting of classification. Theoretically, we illustrate a fundamental connection between $\alpha$-loss and Arimoto conditional entropy, verify the classification-calibration of $\alpha$-loss in order to demonstrate asymptotic optimality via Rademacher complexity generalization techniques, and build-upon a notion called strictly local quasi-convexity in order to quantitatively characterize the optimization landscape of $\alpha$-loss. Practically, we perform class imbalance, robustness, and classification experiments on benchmark image datasets using convolutional-neural-networks. Our main practical conclusion is that certain tasks may benefit from tuning $\alpha$-loss away from log-loss ($\alpha = 1$), and to this end we provide simple heuristics for the practitioner. In particular, navigating the $\alpha$ hyperparameter can readily provide superior model robustness to label flips ($\alpha > 1$) and sensitivity to imbalanced classes ($\alpha < 1$).

Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the ǫ-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance.

We define notions of stability for learning algorithms and show how to use these notions to derive generalization error bounds based on the empirical error and the leave-one-out error. The methods we use can be applied in the regression framework as well as in the classification one when the classifier is obtained by thresholding a real-valued function. We study the stability properties of large classes of learning algorithms such as regularization based algorithms. In particular we focus on Hilbert space regularization and Kullback-Leibler regularization. We demonstrate how to apply the results to SVM for regression and classification.1. For a qualitative discussion about sensitivity analysis with links to other resources see e.g. http://sensitivity-analysis.jrc.cec.eu.int/

我们考虑训练在延迟反馈（\ emph {df Learning}）下培训二进制分类器。例如，在在线广告中的转换预测中，我们最初收到单击广告但没有购买商品的负样本；随后，其中一些样本购买了一个物品，然后更改为正面。在DF学习的环境中，我们会随着时间的推移观察样本，然后在某个时候学习分类器。我们最初收到负样本；随后，其中一些样本变为正变为正。在各种现实世界中，例如在线广告，在首次单击后很长时间进行用户操作，可以想象此问题。由于反馈的延迟，正对正和负样品的天真分类返回偏置分类器。一种解决方案是使用已正确标记这些样品的样品超过一定时间窗口的样品。但是，现有研究报告说，仅根据时间窗口假设使用所有样本的子集的性能不佳，并且使用所有样本以及时间窗口假设可以提高经验性能。我们扩展了这些现有研究，并提出了一种具有无偏见和凸经验风险的方法，该方法是根据时间窗口假设在所有样本中构建的。为了证明所提出的方法的合理性，我们为在线广告中的真实流量日志数据集提供了合成和开放数据集的实验结果。

数据标签噪声在监督学习应用中长期以来一直是一个重要的问题，因为它影响了许多广泛使用的分类方法的有效性。最近，重要的现实世界应用，如医学诊断和网络安全，已经产生了在Neyman-Pearson（NP）分类范式的重新兴趣，这在优选级别下限制了更严重的错误类型（例如，I错误）虽然最小化另一个（例如，II型错误）。但是，在标签噪声下对NP范例几乎没有研究。它有点令人惊讶的是，即使普通的NP分类器忽略训练阶段中的标签噪声，它们仍然能够控制I型错误，具有高概率。但是，他们支付的价格是I误差类型的过度保守性，因此电源的显着下降（即，1美元，II型错误）。假设领域专家在腐败严重程度上提供下限，我们提出了第一个理论支持算法，它适应NP范例下的训练标签噪声。由此产生的分类器不仅在所需水平下以高概率控制I误差，而且还提高功率。

最近已经建立了近似稳定的学习算法的指数概括范围。但是，统一稳定性的概念是严格的，因为它是数据生成分布不变的。在稳定性的较弱和分布依赖性的概念下，例如假设稳定性和$ L_2 $稳定性，文献表明，在一般情况下，只有多项式概括界限是可能的。本文解决了这两个结果方案之间的长期紧张关系，并在融合信心的经典框架内取得了进步。为此，我们首先建立了一个预测的第一刻，通用错误限制了具有$ l_2 $稳定性的潜在随机学习算法，然后我们证明了一个正确设计的subbagagging流程会导致几乎紧密的指数概括性限制在上面数据和算法的随机性。我们将这些通用结果进一步实质性地将随机梯度下降（SGD）实现，以提高凸或非凸优化的高概率概括性范围，而自然时间衰减的学习速率则可以通过现有的假设稳定性或均匀的假设稳定性来证明这一点。基于稳定的结果。

We study a natural extension of classical empirical risk minimization, where the hypothesis space is a random subspace of a given space. In particular, we consider possibly data dependent subspaces spanned by a random subset of the data, recovering as a special case Nystrom approaches for kernel methods. Considering random subspaces naturally leads to computational savings, but the question is whether the corresponding learning accuracy is degraded. These statistical-computational tradeoffs have been recently explored for the least squares loss and self-concordant loss functions, such as the logistic loss. Here, we work to extend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector machines. This unified analysis requires developing new proofs, that use different technical tools, such as sub-gaussian inputs, to achieve fast rates. Our main results show the existence of different settings, depending on how hard the learning problem is, for which computational efficiency can be improved with no loss in performance.

所有著名的机器学习算法构成了受监督和半监督的学习工作，只有在一个共同的假设下：培训和测试数据遵循相同的分布。当分布变化时，大多数统计模型必须从新收集的数据中重建，对于某些应用程序，这些数据可能是昂贵或无法获得的。因此，有必要开发方法，以减少在相关领域中可用的数据并在相似领域中进一步使用这些数据，从而减少需求和努力获得新的标签样品。这引起了一个新的机器学习框架，称为转移学习：一种受人类在跨任务中推断知识以更有效学习的知识能力的学习环境。尽管有大量不同的转移学习方案，但本调查的主要目的是在特定的，可以说是最受欢迎的转移学习中最受欢迎的次级领域，概述最先进的理论结果，称为域适应。在此子场中，假定数据分布在整个培训和测试数据中发生变化，而学习任务保持不变。我们提供了与域适应性问题有关的现有结果的首次最新描述，该结果涵盖了基于不同统计学习框架的学习界限。

部分标签学习是一种弱监督的学习，不精确的标签，在这里，每个训练示例，我们都有一组候选标签而不是一个真正的标签。最近，在候选标签集的不同一代模型下提出了部分标签学习的各种方法。然而，这些方法需要在生成模型上具有相对强烈的分布假设。当假设不保持时，理论上不保证该方法的性能。在本文中，我们提出了部分标签对适用权的概念。我们表明，这种适当的部分标签学习框架包括许多以前的部分标签学习设置作为特殊情况。然后，我们派生了统一的分类风险估计。我们证明我们的估算器是通过获取其估计误差绑定的风险态度。最后，我们通过实验验证了算法的有效性。

We present a new perspective on loss minimization and the recent notion of Omniprediction through the lens of Outcome Indistingusihability. For a collection of losses and hypothesis class, omniprediction requires that a predictor provide a loss-minimization guarantee simultaneously for every loss in the collection compared to the best (loss-specific) hypothesis in the class. We present a generic template to learn predictors satisfying a guarantee we call Loss Outcome Indistinguishability. For a set of statistical tests--based on a collection of losses and hypothesis class--a predictor is Loss OI if it is indistinguishable (according to the tests) from Nature's true probabilities over outcomes. By design, Loss OI implies omniprediction in a direct and intuitive manner. We simplify Loss OI further, decomposing it into a calibration condition plus multiaccuracy for a class of functions derived from the loss and hypothesis classes. By careful analysis of this class, we give efficient constructions of omnipredictors for interesting classes of loss functions, including non-convex losses. This decomposition highlights the utility of a new multi-group fairness notion that we call calibrated multiaccuracy, which lies in between multiaccuracy and multicalibration. We show that calibrated multiaccuracy implies Loss OI for the important set of convex losses arising from Generalized Linear Models, without requiring full multicalibration. For such losses, we show an equivalence between our computational notion of Loss OI and a geometric notion of indistinguishability, formulated as Pythagorean theorems in the associated Bregman divergence. We give an efficient algorithm for calibrated multiaccuracy with computational complexity comparable to that of multiaccuracy. In all, calibrated multiaccuracy offers an interesting tradeoff point between efficiency and generality in the omniprediction landscape.

通过使一组基本预测因素投票根据一些权重，即对某些概率分布来获得聚合预测器。根据一些规定的概率分布，通过在一组基本预测器中采样来获得随机预测器。因此，聚合和随机预测器的共同之处包括最小化问题，而是通过对预测器集的概率分布来定义。在统计学习理论中，有一套工具旨在了解此类程序的泛化能力：Pac-Bayesian或Pac-Bayes界。由于D. Mcallester的原始Pac-Bayes界，这些工具在许多方向上得到了大大改善（例如，我们将描述社区错过的O. Catoni的定位技术的简化版本，后来被重新发现“相互信息界“）。最近，Pac-Bayes的界限受到相当大的关注：例如，在2017年的Pac-Bayes上有研讨会，“（几乎）50种贝叶斯学习：Pac-Bayesian趋势和见解”，由B. Guedj，F组织。 。巴赫和P.Merain。这一最近成功的原因之一是通过G. Dziugaite和D. Roy成功地将这些限制应用于神经网络。对Pac-Bayes理论的初步介绍仍然缺失。这是一种尝试提供这样的介绍。

监督学习的关键假设是培训和测试数据遵循相同的概率分布。然而，这种基本假设在实践中并不总是满足，例如，由于不断变化的环境，样本选择偏差，隐私问题或高标签成本。转移学习（TL）放松这种假设，并允许我们在分销班次下学习。通常依赖于重要性加权的经典TL方法 - 基于根据重要性（即测试过度训练密度比率）的训练损失培训预测器。然而，由于现实世界机器学习任务变得越来越复杂，高维和动态，探讨了新的新方法，以应对这些挑战最近。在本文中，在介绍基于重要性加权的TL基础之后，我们根据关节和动态重要预测估计审查最近的进步。此外，我们介绍一种因果机制转移方法，该方法包含T1中的因果结构。最后，我们讨论了TL研究的未来观点。

我们从统计学习理论的角度调查分类生物神经网络的功能，以简化的设置为具有身份激活功能的连续时间随机经常性神经网络（RNN）。在纯粹的随机（鲁棒）制度中，我们提供了具有高概率的概括误差，从而表明经验风险最低限度是最典型的假设。我们表明RNNS保留了作为攻击培训和分类任务的唯一信息的路径的部分签名。我们认为这些RNNS很容易培训和强大，并在合成和实际数据的数值实验中培训和稳健。我们还在准确性和稳健性之间表现出权衡现象。

Virtually all machine learning tasks are characterized using some form of loss function, and "good performance" is typically stated in terms of a sufficiently small average loss, taken over the random draw of test data. While optimizing for performance on average is intuitive, convenient to analyze in theory, and easy to implement in practice, such a choice brings about trade-offs. In this work, we survey and introduce a wide variety of non-traditional criteria used to design and evaluate machine learning algorithms, place the classical paradigm within the proper historical context, and propose a view of learning problems which emphasizes the question of "what makes for a desirable loss distribution?" in place of tacit use of the expected loss.

标签排名（LR）对应于学习一个假设的问题，以通过有限一组标签将功能映射到排名。我们采用了对LR的非参数回归方法，并获得了这一基本实际问题的理论绩效保障。我们在无噪声和嘈杂的非参数回归设置中介绍了一个用于标签排名的生成模型，并为两种情况下提供学习算法的示例复杂性界限。在无噪声环境中，我们研究了全排序的LR问题，并在高维制度中使用决策树和随机林提供计算有效的算法。在嘈杂的环境中，我们考虑使用统计观点的不完整和部分排名的LR更通用的情况，并使用多种多组分类的一种方法获得样本复杂性范围。最后，我们与实验补充了我们的理论贡献，旨在了解输入回归噪声如何影响观察到的输出。

我们推出了可实现的机器学习模型的贝叶斯风险和泛化误差的信息 - 理论下限。特别地，我们采用了一个分析，其中模型参数的速率失真函数在训练样本和模型参数之间界定了所需的互信息，以便向贝叶斯风险约束学习模型。对于可实现的模型，我们表明，速率失真函数和相互信息承认的表达式，方便分析。对于在其参数中（大致）较低的LipsChitz的模型，我们将从下面的速率失真函数绑定，而对于VC类，相互信息以高于$ d_ \ mathrm {vc} \ log（n）$。当这些条件匹配时，贝叶斯相对于零一个损耗尺度的风险不足于$ \ oomega（d_ \ mathrm {vc} / n）$，它与已知的外界和最小界限匹配对数因子。我们还考虑标签噪声的影响，在训练和/或测试样本损坏时提供下限。