我们展示了如何采用回归函数$ \ hat {f} $，该{f} $适当地``多校准''并有效地将其后处理成近似错误的分类器，使分类器满足各种公平限制。后处理不需要标记的数据，只有一定数量的未标记数据和计算。计算$ \ hat f $的计算和样本复杂性要求与解决单个公平学习任务的要求相媲美，但实际上可以用来有效地解决许多不同的下游公平约束的学习问题。我们的后处理方法可以轻松处理相交组，从而将先前的工作推广到后处理回归功能上，以满足仅应用于分离组的公平约束。我们的工作扩展了最近的工作，表明多校准的回归函数是``omnipredictors''（即可以在后处理以最佳解决无约束的ERM问题）以进行约束优化。

The most prevalent notions of fairness in machine learning are statistical definitions: they fix a small collection of high-level, pre-defined groups (such as race or gender), and then ask for approximate parity of some statistic of the classifier (like positive classification rate or false positive rate) across these groups. Constraints of this form are susceptible to (intentional or inadvertent) fairness gerrymandering, in which a classifier appears to be fair on each individual group, but badly violates the fairness constraint on one or more structured subgroups defined over the protected attributes (such as certain combinations of protected attribute values). We propose instead to demand statistical notions of fairness across exponentially (or infinitely) many subgroups, defined by a structured class of functions over the protected attributes. This interpolates between statistical definitions of fairness, and recently proposed individual notions of fairness, but it raises several computational challenges. It is no longer clear how to even check or audit a fixed classifier to see if it satisfies such a strong definition of fairness. We prove that the computational problem of auditing subgroup fairness for both equality of false positive rates and statistical parity is equivalent to the problem of weak agnostic learning -which means it is computationally hard in the worst case, even for simple structured subclasses. However, it also suggests that common heuristics for learning can be applied to successfully solve the auditing problem in practice.We then derive two algorithms that provably converge to the best fair distribution over classifiers in a given class, given access to oracles which can optimally solve the agnostic learning problem. The algorithms are based on a formulation of subgroup fairness as a two-player zero-sum game between a Learner (the primal player) and an Auditor (the dual player). Both algorithms compute an equilibrium of this game. We obtain our first algorithm by simulating play of the game by having Learner play an instance of the no-regret Follow the Perturbed Leader algorithm, and having Auditor play best response. This algorithm provably converges to an approximate Nash equilibrium (and thus to an approximately optimal subgroup-fair distribution over classifiers) in a polynomial number of steps. We obtain our second algorithm by simulating play of the game by having both players play Fictitious Play, which enjoys only provably asymptotic convergence, but has the merit of simplicity and faster per-step computation. We implement the Fictitious Play version using linear regression as a heuristic oracle, and show that we can effectively both audit and learn fair classifiers on real datasets.

Omnipredictors（Gopalan，Kalai，Reingold，Sharan和Wieder ITCS 2021）的概念提出了一种新的损失最小化范式。与损失损失$ c $相比，无需基于已知的损失功能学习预测指标，而是可以轻松地进行后处理以最大程度地减少任何丰富的损失功能家族。已经表明，这种杂手已经存在，并暗示（对于所有凸和Lipschitz损失函数），通过算法公平文献的多核概念的概念。然而，通常情况下，所选的动作必须遵守一些其他约束（例如能力或奇偶校验约束）。总体而言，全能器的原始概念并不适用于这种良好动机和大量研究的损失最小化的背景。在本文中，我们介绍了综合器，以进行约束优化并研究其复杂性和含义。我们介绍的概念使学习者不知道后来将分配的损失函数以及后来将施加的约束，只要已知用于定义这些约束的亚群的范围。该论文显示了如何依靠适当的多核变体获得限制优化问题的全能器。对于一些有趣的约束和一般损失函数以及一般约束和一些有趣的损失函数，我们显示了如何通过多核的变体隐含的，该变体的复杂性与标准的多核电相似。我们证明，在一般情况下，标准的数学启动不足，表明全能器是通过相对于包含$ c $中所有级别假设集的类的多核算来暗示的。我们还研究了约束是群体公平概念时的含义。

We present a systematic approach for achieving fairness in a binary classification setting. While we focus on two well-known quantitative definitions of fairness, our approach encompasses many other previously studied definitions as special cases. The key idea is to reduce fair classification to a sequence of cost-sensitive classification problems, whose solutions yield a randomized classifier with the lowest (empirical) error subject to the desired constraints. We introduce two reductions that work for any representation of the cost-sensitive classifier and compare favorably to prior baselines on a variety of data sets, while overcoming several of their disadvantages.

我们在禁用的对手存在下研究公平分类，允许获得$ \ eta $，选择培训样本的任意$ \ eta $ -flaction，并任意扰乱受保护的属性。由于战略误报，恶意演员或归责的错误，受保护属性可能不正确的设定。和现有的方法，使随机或独立假设对错误可能不满足其在这种对抗环境中的保证。我们的主要贡献是在这种对抗的环境中学习公平分类器的优化框架，这些普遍存在的准确性和公平性提供了可证明的保证。我们的框架适用于多个和非二进制保护属性，专为大类线性分数公平度量设计，并且还可以处理除了受保护的属性之外的扰动。我们证明了我们框架的近密性，对自然假设类别的保证：没有算法可以具有明显更好的准确性，并且任何具有更好公平性的算法必须具有较低的准确性。凭经验，我们评估了我们对统计率的统计税务统计税率为一个对手的统计税率产生的分类机。

在高赌注域中的机器学习工具的实际应用通常被调节为公平，因此预测目标应该满足相对于受保护属性的奇偶校验的一些定量概念。然而，公平性和准确性之间的确切权衡并不完全清楚，即使是对分类问题的基本范式也是如此。在本文中，我们通过在任何公平分类器的群体误差之和中提供较低的界限，在分类设置中表征统计奇偶校验和准确性之间的固有权衡。我们不可能的定理可以被解释为公平的某种不确定性原则：如果基本率不同，那么符合统计奇偶校验的任何公平分类器都必须在至少一个组中产生很大的错误。我们进一步扩展了这一结果，以便在学习公平陈述的角度下给出任何（大约）公平分类者的联合误差的下限。为了表明我们的下限是紧张的，假设Oracle访问贝叶斯（潜在不公平）分类器，我们还构造了一种返回一个随机分类器的算法，这是最佳和公平的。有趣的是，当受保护的属性可以采用超过两个值时，这个下限的扩展不承认分析解决方案。然而，在这种情况下，我们表明，通过解决线性程序，我们可以通过解决我们作为电视 - 重心问题的术语，电视距离的重心问题来有效地计算下限。在上面，我们证明，如果集团明智的贝叶斯最佳分类器是关闭的，那么学习公平的表示导致公平的替代概念，称为准确性奇偶校验，这使得错误率在组之间关闭。最后，我们还在现实世界数据集上进行实验，以确认我们的理论发现。

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.

尽管学习已成为现代信息处理的核心组成部分，但现在有足够的证据表明它可以导致偏见，不安全和有偏见的系统。因此，对学习要求施加要求至关重要，尤其是在达到社会，工业和医疗领域的关键应用程序时。但是，大多数现代统计问题的非跨性别性只有通过限制引入而加剧。尽管通常可以使用经验风险最小化来学习良好的无约束解决方案，即使获得满足统计约束的模型也可能具有挑战性。更重要的是，一个好。在本文中，我们通过在经验双重领域中学习来克服这个问题，在经验的双重领域中，统计学上的统计学习问题变得不受限制和确定性。我们通过界定经验二元性差距来分析这种方法的概括特性 - 即，我们的近似，可拖动解决方案与原始（非凸）统计问题的解决方案之间的差异 - 并提供实用的约束学习算法。这些结果建立了与经典学习理论的约束，从而可以明确地在学习中使用约束。我们说明了这种理论和算法受到速率受限的学习应用，这是在公平和对抗性鲁棒性中产生的。

We propose a criterion for discrimination against a specified sensitive attribute in supervised learning, where the goal is to predict some target based on available features. Assuming data about the predictor, target, and membership in the protected group are available, we show how to optimally adjust any learned predictor so as to remove discrimination according to our definition. Our framework also improves incentives by shifting the cost of poor classification from disadvantaged groups to the decision maker, who can respond by improving the classification accuracy.In line with other studies, our notion is oblivious: it depends only on the joint statistics of the predictor, the target and the protected attribute, but not on interpretation of individual features. We study the inherent limits of defining and identifying biases based on such oblivious measures, outlining what can and cannot be inferred from different oblivious tests.We illustrate our notion using a case study of FICO credit scores.

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.

该工作研究限制了随机函数是凸的，并表示为随机函数的组成。问题是在公平分类，公平回归和排队系统设计的背景下出现的。特别令人感兴趣的是甲骨文提供组成函数的随机梯度的大规模设置，目标是用最小对Oracle的调用来解决问题。由于组成形式，Oracle提供的随机梯度不会产生目标或约束梯度的无偏估计。取而代之的是，我们通过跟踪内部函数评估来构建近似梯度，从而导致准差鞍点算法。我们证明，所提出的算法几乎可以肯定地找到最佳和可行的解决方案。我们进一步确定所提出的算法需要$ \ MATHCAL {O}（1/\ EPSILON^4）$数据样本，以便获得$ \ epsilon $ -Approximate-approximate-apptroximate Pointal点，同时也确保零约束违反。该结果与无约束问题的随机成分梯度下降方法的样品复杂性相匹配，并改善了受约束设置的最著名样品复杂性结果。在公平分类和公平回归问题上测试了所提出的算法的功效。数值结果表明，根据收敛速率，所提出的算法优于最新算法。

公司跨行业对机器学习（ML）的快速传播采用了重大的监管挑战。一个这样的挑战就是可伸缩性：监管机构如何有效地审核这些ML模型，以确保它们是公平的？在本文中，我们启动基于查询的审计算法的研究，这些算法可以以查询有效的方式估算ML模型的人口统计学率。我们提出了一种最佳的确定性算法，以及具有可比保证的实用随机，甲骨文效率的算法。此外，我们进一步了解了随机活动公平估计算法的最佳查询复杂性。我们对主动公平估计的首次探索旨在将AI治理置于更坚定的理论基础上。

我们考虑为多类分类任务生产公平概率分类器的问题。我们以“投射”预先培训（且可能不公平的）分类器在满足目标群体对要求的一组模型上的“投影”来提出这个问题。新的投影模型是通过通过乘法因子后处理预训练的分类器的输出来给出的。我们提供了一种可行的迭代算法，用于计算投影分类器并得出样本复杂性和收敛保证。与最先进的基准测试的全面数值比较表明，我们的方法在准确性权衡曲线方面保持了竞争性能，同时在大型数据集中达到了有利的运行时。我们还在具有多个类别，多个相互保护组和超过1M样本的开放数据集上评估了我们的方法。

我们研究了一个受个人公平的限制的在线学习问题，这要求类似的个体相似地治疗。与事先对个人公平的工作不同，我们不认为个人之间的相似性措施是已知的，我们也不认为这种措施采用某种参数形式。相反，我们利用了审计师的存在，审计师在没有阐述定量措施的情况下检测公平违规行为。在每一轮中，审计员审查了学习者的决定，并试图识别学习者不公平对待的一对个人。我们提供了一般的框架，将我们的模型中的在线分类降低到标准的在线分类，这使我们能够利用现有的在线学习算法来实现子线性遗憾和公平违规的数量。令人惊讶的是，在独立于分布绘制数据的随机环境中，我们还能够建立PAC样式和准确性概括保障（YONA和Rothblum [2018]），尽管只有获得了一种非常受限制的公平形式回馈。我们的公平泛化界定定性匹配Yona和Rothblum的统一收敛[2018]，同时还提供了有意义的准确性概括担保。我们的结果通过Gillen等人解决了一个开放的问题。 [2018]通过表明在未知的单个公平性约束下的在线学习是可能的，即使在不假设基础相似度措施的强大参数形式的情况下也是可能的。

在联邦学习中，对受保护群体的公平预测是许多应用程序的重要限制。不幸的是，先前研究集团联邦学习的工作往往缺乏正式的融合或公平保证。在这项工作中，我们为可证明的公平联合学习提供了一个一般框架。特别是，我们探索并扩展了有限的群体损失的概念，作为理论上的群体公平方法。使用此设置，我们提出了一种可扩展的联合优化方法，该方法在许多群体公平限制下优化了经验风险。我们为该方法提供收敛保证，并为最终解决方案提供公平保证。从经验上讲，我们评估了公平ML和联合学习的共同基准的方法，表明它可以比基线方法提供更公平，更准确的预测。

个人概率是指仅实现一次的结果的概率：明天下雨的可能性，爱丽丝在未来12个月内死亡的可能性，鲍勃在未来18个月内因暴力犯罪而被捕的可能性等等。个人概率从根本上是不可知的。但是，我们表明，有两个在数据分发中的数据或如何从数据分发中进行采样的当事方不同意在如何建模个人概率上不同意。这是因为实质上不同意的任何两个模型的个人概率模型都可以用来凭经验伪造和改善两个模型之一。在“和解”过程中，这可以有效地迭代，该过程导致双方同意的模型优于他们开始的模型，并且（几乎）本身（几乎）都同意了各个概率（几乎）到处的预测。我们得出的结论是，尽管个人概率是不可知的，但它们是通过必须导致共识的计算和数据有效过程来竞争的。因此，我们无法发现自己​​有两个同样准确且不可解决的模型，这些模型在其预测中基本上不同意 - 为有时所谓的预测性或模型多样性问题提供答案。

最近的工作突出了因果关系在设计公平决策算法中的作用。但是，尚不清楚现有的公平因果概念如何相互关系，或者将这些定义作为设计原则的后果是什么。在这里，我们首先将算法公平性的流行因果定义组装成两个广泛的家庭：（1）那些限制决策对反事实差异的影响的家庭； （2）那些限制了法律保护特征（如种族和性别）对决策的影响。然后，我们在分析和经验上表明，两个定义的家庭\ emph {几乎总是总是} - 从一种理论意义上讲 - 导致帕累托占主导地位的决策政策，这意味着每个利益相关者都有一个偏爱的替代性，不受限制的政策从大型自然级别中绘制。例如，在大学录取决定的情况下，每位利益相关者都不支持任何对学术准备和多样性的中立或积极偏好的利益相关者，将不利于因果公平定义的政策。的确，在因果公平的明显定义下，我们证明了由此产生的政策要求承认所有具有相同概率的学生，无论学术资格或小组成员身份如何。我们的结果突出了正式的局限性和因果公平的常见数学观念的潜在不利后果。

这项工作提供了在人口统计学限制下的最佳分类函数的几种基本特征。在意识框架中，类似于经典的不受限制的分类案例，我们表明，在这种公平性约束下，最大化准确性等于解决相应的回归问题，然后在级别$ 1/2 $上进行阈值。我们将此结果扩展到线性分类分类度量（例如，$ {\ rm f} $ - 得分，AM度量，平衡准确性等），突出了回归问题在此框架中所起的基本作用。我们的结果利用了最近在人口统计学限制与多界限最佳运输公式之间建立了联系。从非正式的角度来看，我们的结果表明，通过解决公平回归问题的解决方案来代替标签的有条件期望，可以实现无约束的问题与公平问题之间的过渡。最后，利用我们的分析，我们证明了在两个敏感群体的情况下，意识和不认识的设置之间的等效性。

我们提出了一种可扩展的后处理算法，用于衰减培训的型号，包括深度神经网络（DNN），我们证明是通过限制其多余的贝叶斯风险而近乎最佳。我们在经典算法以及现代DNN架构上凭经验验证其对标准基准数据集的优势，并证明它在以前处理的同时表现出先前的后处理方法。此外，我们表明，该算法对于在刻度培训的模型是特别有效的，其中后处理是自然和实际的选择。

多集团不可知学习是一个正式的学习标准，涉及人口亚组内的预测因子的条件风险。标准解决了最近的实际问题，如亚组公平和隐藏分层。本文研究了对多组学习问题的解决方案的结构，为学习问题提供了简单和近最佳的算法。