学习提高AUC性能是机器学习中的重要主题。但是，AUC最大化算法可能会由于嘈杂数据而降低泛化性能。自定进度学习是处理嘈杂数据的有效方法。但是，现有的自定进度学习方法仅限于指尖学习，而AUC最大化是一个成对的学习问题。为了解决这个具有挑战性的问题，我们创新提出了一种平衡的自定进度的AUC最大化算法（BSPAUC）。具体而言，我们首先为自节奏的AUC提供了一个统计目标。基于此，我们提出了我们的自进度的AUC最大化公式，其中新型平衡的自定进定的正则化项被嵌入，以确保所选的阳性和负样品具有适当的比例。特别是，关于所有重量变量的子问题在我们的配方中可能是非凸，而通常在现有的自节奏问题中是凸出的。为了解决这个问题，我们提出了一种双环块坐标下降法。更重要的是，我们证明，相对于所有重量变量的子问题基于封闭形式的溶液会收敛到固定点，并且我们的BSPAUC在轻度假设下收敛到我们固定优化目标的固定点。考虑到基于深度学习和基于内核的实现，几个大规模数据集的实验结果表明，与现有的最新AUC最大化方法相比，我们的BSPAUC具有更好的概括性能。

Deep Metric Learning (DML) is a group of techniques that aim to measure the similarity between objects through the neural network. Although the number of DML methods has rapidly increased in recent years, most previous studies cannot effectively handle noisy data, which commonly exists in practical applications and often leads to serious performance deterioration. To overcome this limitation, in this paper, we build a connection between noisy samples and hard samples in the framework of self-paced learning, and propose a \underline{B}alanced \underline{S}elf-\underline{P}aced \underline{M}etric \underline{L}earning (BSPML) algorithm with a denoising multi-similarity formulation, where noisy samples are treated as extremely hard samples and adaptively excluded from the model training by sample weighting. Especially, due to the pairwise relationship and a new balance regularization term, the sub-problem \emph{w.r.t.} sample weights is a nonconvex quadratic function. To efficiently solve this nonconvex quadratic problem, we propose a doubly stochastic projection coordinate gradient algorithm. Importantly, we theoretically prove the convergence not only for the doubly stochastic projection coordinate gradient algorithm, but also for our BSPML algorithm. Experimental results on several standard data sets demonstrate that our BSPML algorithm has better generalization ability and robustness than the state-of-the-art robust DML approaches.

在本文中，我们提出了适用于深度学习的单向和双向部分AUC（PAUC）最大化的系统和高效的基于梯度的方法。我们通过使用分布强大的优化（DRO）来定义每个单独的积极数据的损失，提出了PAUC替代目标的新公式。我们考虑了两种DRO的配方，其中一种是基于条件 - 价值风险（CVAR），该风险（CVAR）得出了PAUC的非平滑但精确的估计器，而另一个基于KL差异正则DRO产生不确定的dro。但是PAUC的平滑（软）估计器。对于单向和双向PAUC最大化，我们提出了两种算法，并证明了它们分别优化其两种配方的收敛性。实验证明了所提出的算法对PAUC最大化的有效性，以对各种数据集进行深度学习。

ROC曲线下的区域（又称AUC）是评估分类器不平衡数据的性能的选择。 AUC最大化是指通过直接最大化其AUC分数来学习预测模型的学习范式。它已被研究了二十年来，其历史可以追溯到90年代后期，从那时起，大量工作就致力于最大化。最近，对大数据和深度学习的深度最大化的随机AUC最大化已受到越来越多的关注，并对解决现实世界中的问题产生了巨大的影响。但是，据我们所知，没有对AUC最大化的相关作品进行全面调查。本文旨在通过回顾过去二十年来审查文献来解决差距。我们不仅给出了文献的整体看法，而且还提供了从配方到算法和理论保证的不同论文的详细解释和比较。我们还确定并讨论了深度AUC最大化的剩余和新兴问题，并就未来工作的主题提供建议。

As machine learning being used increasingly in making high-stakes decisions, an arising challenge is to avoid unfair AI systems that lead to discriminatory decisions for protected population. A direct approach for obtaining a fair predictive model is to train the model through optimizing its prediction performance subject to fairness constraints, which achieves Pareto efficiency when trading off performance against fairness. Among various fairness metrics, the ones based on the area under the ROC curve (AUC) are emerging recently because they are threshold-agnostic and effective for unbalanced data. In this work, we formulate the training problem of a fairness-aware machine learning model as an AUC optimization problem subject to a class of AUC-based fairness constraints. This problem can be reformulated as a min-max optimization problem with min-max constraints, which we solve by stochastic first-order methods based on a new Bregman divergence designed for the special structure of the problem. We numerically demonstrate the effectiveness of our approach on real-world data under different fairness metrics.

本文重点介绍了解决光滑非凸强凹入最小问题的随机方法，这导致了由于其深度学习中的潜在应用而受到越来越长的关注（例如，深度AUC最大化，分布鲁棒优化）。然而，大多数现有算法在实践中都很慢，并且它们的分析围绕到几乎静止点的收敛。我们考虑利用Polyak-\ L Ojasiewicz（PL）条件来设计更快的随机算法，具有更强的收敛保证。尽管已经用于设计许多随机最小化算法的PL条件，但它们对非凸敏最大优化的应用仍然罕见。在本文中，我们提出并分析了基于近端的跨越时代的方法的通用框架，许多众所周知的随机更新嵌入。以{\ BF原始物镜差和二元间隙}的方式建立快速收敛。与现有研究相比，（i）我们的分析基于一个新的Lyapunov函数，包括原始物理差距和正则化功能的二元间隙，（ii）结果更加全面，提高了更好的依赖性的速率不同假设下的条件号。我们还开展深层和非深度学习实验，以验证我们的方法的有效性。

NDCG是标准化的折扣累积增益，是信息检索和机器学习中广泛使用的排名指标。但是，仍然缺乏最大化NDCG的有效且可证明的随机方法，尤其是对于深层模型。在本文中，我们提出了一种优化NDCG及其最高$ K $变体的原则方法。首先，我们制定了一个新颖的组成优化问题，以优化NDCG替代物，以及一个新型的双层构图优化问题，用于优化顶部$ K $ NDCG代理。然后，我们开发有效的随机算法，并为非凸目标提供可证明的收敛保证。与现有的NDCG优化方法不同，我们的算法量表的均量复杂性与迷你批量大小，而不是总项目的数量。为了提高深度学习的有效性，我们通过使用初始热身和停止梯度操作员进一步提出实用策略。多个数据集的实验结果表明，我们的方法在NDCG方面优于先前的排名方法。据我们所知，这是首次提出随机算法以优化具有可证明的收敛保证的NDCG。我们提出的方法在https://libauc.org/的libauc库中实现。

在本文中，我们研究了多块最小双重双层优化问题，其中上层是非凸线的最小值最小值目标，而下层级别是一个强烈的凸目标，并且有多个双重变量块和下层级别。问题。由于交织在一起的多块最小双重双重结构，每次迭代处的计算成本可能高高，尤其是在大量块中。为了应对这一挑战，我们提出了一种单循环随机随机算法，该算法需要在每次迭代时仅恒定数量的块进行更新。在对问题的一些温和假设下，我们建立了$ \ Mathcal {o}（1/\ Epsilon^4）$的样本复杂性，用于查找$ \ epsilon $ - 稳定点。这匹配了在一般无偏见的随机甲骨文模型下求解随机非convex优化的最佳复杂性。此外，我们在多任务深度AUC（ROC曲线下）最大化和多任务深度部分AUC最大化中提供了两种应用。实验结果验证了我们的理论，并证明了我们方法对数百个任务问题的有效性。

We describe an algorithm that learns two-layer residual units using rectified linear unit (ReLU) activation: suppose the input $\mathbf{x}$ is from a distribution with support space $\mathbb{R}^d$ and the ground-truth generative model is a residual unit of this type, given by $\mathbf{y} = \boldsymbol{B}^\ast\left[\left(\boldsymbol{A}^\ast\mathbf{x}\right)^+ + \mathbf{x}\right]$, where ground-truth network parameters $\boldsymbol{A}^\ast \in \mathbb{R}^{d\times d}$ represent a full-rank matrix with nonnegative entries and $\boldsymbol{B}^\ast \in \mathbb{R}^{m\times d}$ is full-rank with $m \geq d$ and for $\boldsymbol{c} \in \mathbb{R}^d$, $[\boldsymbol{c}^{+}]_i = \max\{0, c_i\}$. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-truth network in terms of its parameters and nonlinearities. Following this objective landscape, learning residual units from finite samples can be formulated using convex optimization of a nonparametric function: for each layer, we first formulate the corresponding empirical risk minimization (ERM) as a positive semi-definite quadratic program (QP), then we show the solution space of the QP can be equivalently determined by a set of linear inequalities, which can then be efficiently solved by linear programming (LP). We further prove the strong statistical consistency of our algorithm, and demonstrate its robustness and sample efficiency through experimental results on synthetic data and a set of benchmark regression datasets.

在结果决策中使用机器学习模型通常会加剧社会不平等，特别是对种族和性别定义的边缘化群体成员产生不同的影响。 ROC曲线（AUC）下的区域被广泛用于评估机器学习中评分功能的性能，但与其他性能指标相比，在算法公平性中进行了研究。由于AUC的成对性质，定义基于AUC的组公平度量是成对依赖性的，并且可能涉及\ emph {group}和\ emph {group} aucs。重要的是，仅考虑一种AUC类别不足以减轻AUC优化的不公平性。在本文中，我们提出了一个最小值学习和偏置缓解框架，该框架既包含组内和组间AUC，同时保持实用性。基于这个Rawlsian框架，我们设计了一种有效的随机优化算法，并证明了其收敛到最小组级AUC。我们对合成数据集和现实数据集进行了数值实验，以验证Minimax框架的有效性和所提出的优化算法。

成对学习是指损失函数取决于一对情况的学习任务。它实例化了许多重要的机器学习任务，如双级排名和度量学习。一种流行的方法来处理成对学习中的流数据是在线梯度下降（OGD）算法，其中需要将当前实例配对以前具有足够大的尺寸的先前实例的电流实例，因此遭受可扩展性问题。在本文中，我们提出了用于成对学习的简单随机和在线梯度下降方法。与现有研究的显着差异是，我们仅将当前实例与前一个构建梯度方向配对，这在存储和计算复杂性中是有效的。我们为凸和非凸起的展示结果，优化和泛化误差界以及平滑和非光滑问题都开发了新颖的稳定性结果，优化和泛化误差界限。我们引入了新颖的技术来解耦模型的依赖性和前一个例子在优化和泛化分析中。我们的研究解决了使用具有非常小的固定尺寸的缓冲集开发OGD的有意义的泛化范围的开放问题。我们还扩展了我们的算法和稳定性分析，以便为成对学习开发差异私有的SGD算法，这显着提高了现有结果。

本文研究了一系列组成函数的随机优化，其中每个汇总的内部函数与相应的求和指数耦合。我们将这个问题家族称为有限和耦合的组成优化（FCCO）。它在机器学习中具有广泛的应用，用于优化非凸或凸组成措施/目标，例如平均精度（AP），p-norm推动，列表排名损失，邻居组成分析（NCA），深度生存分析，深层可变模型等等，这应该得到更精细的分析。然而，现有的算法和分析在一个或其他方面受到限制。本文的贡献是为非凸和凸目标的简单随机算法提供全面的收敛分析。我们的关键结果是通过使用带有微型批次的基于移动平均的估计器，通过并行加速提高了Oracle的复杂性。我们的理论分析还展示了通过对外部和内部水平相等大小的批量来改善实际实现的新见解。关于AP最大化，NCA和P-norm推动的数值实验证实了该理论的某些方面。

基于梯度的高参数调整的优化方法可确保理论收敛到固定解决方案时，对于固定的上层变量值，双光线程序的下层级别强烈凸（LLSC）和平滑（LLS）。对于在许多机器学习算法中调整超参数引起的双重程序，不满足这种情况。在这项工作中，我们开发了一种基于不精确度（VF-IDCA）的基于依次收敛函数函数算法。我们表明，该算法从一系列的超级参数调整应用程序中实现了无LLSC和LLS假设的固定解决方案。我们的广泛实验证实了我们的理论发现，并表明，当应用于调子超参数时，提出的VF-IDCA会产生较高的性能。

许多实际优化问题涉及不确定的参数，这些参数具有概率分布，可以使用上下文特征信息来估算。与首先估计不确定参数的分布然后基于估计优化目标的标准方法相反，我们提出了一个\ textIt {集成条件估计 - 优化}（ICEO）框架，该框架估计了随机参数的潜在条件分布同时考虑优化问题的结构。我们将随机参数的条件分布与上下文特征之间的关系直接建模，然后以与下游优化问题对齐的目标估算概率模型。我们表明，我们的ICEO方法在适度的规律性条件下渐近一致，并以概括范围的形式提供有限的性能保证。在计算上，使用ICEO方法执行估计是一种非凸面且通常是非差异的优化问题。我们提出了一种通用方法，用于近似从估计的条件分布到通过可区分函数的最佳决策的潜在非差异映射，这极大地改善了应用于非凸问题的基于梯度的算法的性能。我们还提供了半代理案例中的多项式优化解决方案方法。还进行了数值实验，以显示我们在不同情况下的方法的经验成功，包括数据样本和模型不匹配。

We study distributionally robust optimization (DRO) with Sinkhorn distance -- a variant of Wasserstein distance based on entropic regularization. We provide convex programming dual reformulation for a general nominal distribution. Compared with Wasserstein DRO, it is computationally tractable for a larger class of loss functions, and its worst-case distribution is more reasonable. We propose an efficient first-order algorithm with bisection search to solve the dual reformulation. We demonstrate that our proposed algorithm finds $\delta$-optimal solution of the new DRO formulation with computation cost $\tilde{O}(\delta^{-3})$ and memory cost $\tilde{O}(\delta^{-2})$, and the computation cost further improves to $\tilde{O}(\delta^{-2})$ when the loss function is smooth. Finally, we provide various numerical examples using both synthetic and real data to demonstrate its competitive performance and light computational speed.

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

了解随机梯度下降（SGD）的隐式偏见是深度学习的关键挑战之一，尤其是对于过度透明的模型，损失功能的局部最小化$ l $可以形成多种多样的模型。从直觉上讲，SGD $ \ eta $的学习率很小，SGD跟踪梯度下降（GD），直到它接近这种歧管为止，梯度噪声阻止了进一步的收敛。在这样的政权中，Blanc等人。 （2020）证明，带有标签噪声的SGD局部降低了常规术语，损失的清晰度，$ \ mathrm {tr} [\ nabla^2 l] $。当前的论文通过调整Katzenberger（1991）的想法提供了一个总体框架。它原则上允许使用随机微分方程（SDE）描述参数的限制动力学的SGD围绕此歧管的正规化效应（即“隐式偏见”）的正则化效应，这是由损失共同确定的功能和噪声协方差。这产生了一些新的结果：（1）与Blanc等人的局部分析相比，对$ \ eta^{ - 2} $ steps有效的隐性偏差进行了全局分析。 （2020）仅适用于$ \ eta^{ - 1.6} $ steps和（2）允许任意噪声协方差。作为一个应用程序，我们以任意大的初始化显示，标签噪声SGD始终可以逃脱内核制度，并且仅需要$ o（\ kappa \ ln d）$样本用于学习$ \ kappa $ -sparse $ -sparse yroverparame parametrized linearized Linear Modal in $ \ Mathbb {r}^d $（Woodworth等，2020），而GD在内核制度中初始化的GD需要$ \ omega（d）$样本。该上限是最小值的最佳，并改善了先前的$ \ tilde {o}（\ kappa^2）$上限（Haochen等，2020）。

我们开发了快速算法和可靠软件，以凸出具有Relu激活功能的两层神经网络的凸优化。我们的工作利用了标准的重量罚款训练问题作为一组组-YELL_1 $调查的数据本地模型的凸重新印度，其中局部由多面体锥体约束强制执行。在零规范化的特殊情况下，我们表明此问题完全等同于凸“ Gated Relu”网络的不受约束的优化。对于非零正则化的问题，我们表明凸面式relu模型获得了RELU训练问题的数据依赖性近似范围。为了优化凸的重新制定，我们开发了一种加速的近端梯度方法和实用的增强拉格朗日求解器。我们表明，这些方法比针对非凸问题（例如SGD）和超越商业内部点求解器的标准训练启发式方法要快。在实验上，我们验证了我们的理论结果，探索组-ELL_1 $正则化路径，并对神经网络进行比例凸的优化，以在MNIST和CIFAR-10上进行图像分类。

在许多机器学习应用程序中出现了非convex-concave min-max问题，包括最大程度地减少一组非凸函数的最大程度，并对神经网络的强大对抗训练。解决此问题的一种流行方法是梯度下降（GDA）算法，不幸的是，在非凸性的情况下可以表现出振荡。在本文中，我们引入了一种“平滑”方案，该方案可以与GDA结合以稳定振荡并确保收敛到固定溶液。我们证明，稳定的GDA算法可以实现$ O（1/\ epsilon^2）$迭代复杂性，以最大程度地减少有限的非convex函数收集的最大值。此外，平滑的GDA算法达到了$ O（1/\ epsilon^4）$ toseration复杂性，用于一般的nonconvex-concave问题。提出了这种稳定的GDA算法的扩展到多块情况。据我们所知，这是第一个实现$ o（1/\ epsilon^2）$的算法，用于一类NonConvex-Concave问题。我们说明了稳定的GDA算法在健壮训练中的实际效率。

转移学习或域适应性与机器学习问题有关，在这些问题中，培训和测试数据可能来自可能不同的概率分布。在这项工作中，我们在Russo和Xu发起的一系列工作之后，就通用错误和转移学习算法的过量风险进行了信息理论分析。我们的结果也许表明，也许正如预期的那样，kullback-leibler（kl）Divergence $ d（\ mu || \ mu'）$在$ \ mu $和$ \ mu'$表示分布的特征中起着重要作用。培训数据和测试测试。具体而言，我们为经验风险最小化（ERM）算法提供了概括误差上限，其中两个分布的数据在训练阶段都可用。我们进一步将分析应用于近似的ERM方法，例如Gibbs算法和随机梯度下降方法。然后，我们概括了与$ \ phi $ -Divergence和Wasserstein距离绑定的共同信息。这些概括导致更紧密的范围，并且在$ \ mu $相对于$ \ mu' $的情况下，可以处理案例。此外，我们应用了一套新的技术来获得替代的上限，该界限为某些学习问题提供了快速（最佳）的学习率。最后，受到派生界限的启发，我们提出了Infoboost算法，其中根据信息测量方法对源和目标数据的重要性权重进行了调整。经验结果表明了所提出的算法的有效性。