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

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.

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

我们考虑在对抗环境中的强大学习模型。学习者获得未腐败的培训数据，并访问可能受到测试期间对手影响的可能腐败。学习者的目标是建立一个强大的分类器，该分类器将在未来的对抗示例中进行测试。每个输入的对手仅限于$ k $可能的损坏。我们将学习者 - 对手互动建模为零和游戏。该模型与Schmidt等人的对抗示例模型密切相关。 （2018）; Madry等。 （2017）。我们的主要结果包括对二进制和多类分类的概括界限，以及实现的情况（回归）。对于二元分类设置，我们都拧紧Feige等人的概括。 （2015年），也能够处理无限假设类别。样本复杂度从$ o（\ frac {1} {\ epsilon^4} \ log（\ frac {| h |} {\ delta}）$ to $ o \ big（\ frac {1} { epsilon^2}（kvc（h）\ log^{\ frac {3} {2}+\ alpha}（kvc（h））+\ log（\ frac {1} {\ delta} {\ delta}）\ big）\ big）\ big）$ for任何$ \ alpha> 0 $。此外，我们将算法和概括从二进制限制到多类和真实价值的案例。一路上，我们获得了脂肪震惊的尺寸和$ k $ fold的脂肪的尺寸和Rademacher复杂性的结果最大值的功能类别；这些可能具有独立的兴趣。对于二进制分类，Feige等人（2015年）使用遗憾的最小化算法和Erm Oracle作为黑匣子；我们适应了多类和回归设置。该算法为我们提供了给定培训样本中的球员的近乎最佳政策。

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

在这项工作中，我们调查了Steinke和Zakynthinou（2020）的“条件互信息”（CMI）框架的表现力，以及使用它来提供统一框架，用于在可实现的环境中证明泛化界限。我们首先证明可以使用该框架来表达任何用于从一类界限VC维度输出假设的任何学习算法的非琐碎（但是次优）界限。我们证明了CMI框架在用于学习半个空间的预期风险上产生最佳限制。该结果是我们的一般结果的应用，显示稳定的压缩方案Bousquet al。 （2020）尺寸$ k $有统一有限的命令$ o（k）$。我们进一步表明，适当学习VC类的固有限制与恒定的CMI存在适当的学习者的存在，并且它意味着对Steinke和Zakynthinou（2020）的开放问题的负面分辨率。我们进一步研究了价值最低限度（ERMS）的CMI的级别$ H $，并表明，如果才能使用有界CMI输出所有一致的分类器（版本空间），只有在$ H $具有有界的星号（Hanneke和杨（2015）））。此外，我们证明了一般性的减少，表明“休假”分析通过CMI框架表示。作为推论，我们研究了Haussler等人提出的一包图算法的CMI。 （1994）。更一般地说，我们表明CMI框架是通用的，因为对于每一项一致的算法和数据分布，当且仅当其评估的CMI具有样品的载位增长时，预期的风险就会消失。

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.

作为算法公平性的概念，多核算已被证明是一个强大而多才多艺的概念，其含义远远超出了其最初的意图。这个严格的概念 - 预测在丰富的相交子群中得到了很好的校准 - 以成本为代价提供了强大的保证：学习成型预测指标的计算和样本复杂性很高，并且随着类标签的数量而成倍增长。相比之下，可以更有效地实现多辅助性的放松概念，但是，仅假设单独使用多学历，就无法保证许多最可取的多核能概念。这种紧张局势提出了一个关键问题：我们能否以多核式式保证来学习预测因素，以与多审核级相称？在这项工作中，我们定义并启动了低度多核的研究。低度的多核净化定义了越来越强大的多组公平性概念的层次结构，这些概念跨越了多辅助性和极端的多核电的原始表述。我们的主要技术贡献表明，与公平性和准确性有关的多核算的关键特性实际上表现为低级性质。重要的是，我们表明，低度的数学振动可以比完整的多核电更有效。在多级设置中，实现低度多核的样品复杂性在完整的多核电上呈指数级（在类中）提高。我们的工作提供了令人信服的证据，表明低度多核能代表了一个最佳位置，将计算和样品效率配对，并提供了强大的公平性和准确性保证。

我们研究了非参数在线回归中的快速收敛速度，即遗憾的是关于具有有界复杂度的任意函数类来定义后悔。我们的贡献是两倍： - 在绝对损失中的非参数网上回归的可实现设置中，我们提出了一种随机适当的学习算法，该算法在假设类的顺序脂肪破碎尺寸方面获得了近乎最佳的错误。在与一类Littlestone维度$ D $的在线分类中，我们的绑定减少到$ d \ cdot {\ rm poly} \ log t $。这结果回答了一个问题，以及适当的学习者是否可以实现近乎最佳错误的界限;以前，即使在线分类，绑定的最知名错误也是$ \ tilde o（\ sqrt {dt}）$。此外，对于真实值（回归）设置，在这项工作之前，界定的最佳错误甚至没有以不正当的学习者所知。 - 使用上述结果，我们展示了Littlestone维度$ D $的一般总和二进制游戏的独立学习算法，每个玩家达到后悔$ \ tilde o（d ^ {3/4} \ cdot t ^ {1 / 4}）$。该结果概括了Syrgkanis等人的类似结果。 （2015）谁表明，在有限的游戏中，最佳遗憾可以从普通的o（\ sqrt {t}）$中的$ o（\ sqrt {t}）为游戏设置中的$ o（t ^ {1/4}）$。要建立上述结果，我们介绍了几种新技术，包括：分层聚合规则，以实现对实际类别的最佳错误，Hanneke等人的适当在线可实现学习者的多尺度扩展。 （2021），一种方法来表明这种非参数学习算法的输出是稳定的，并且证明Minimax定理在所有在线学习游戏中保持。

Boosting是一种著名的机器学习方法，它基于将弱和适度不准确假设与强烈而准确的假设相结合的想法。我们研究了弱假设属于界限能力类别的假设。这个假设的灵感来自共同的惯例，即虚弱的假设是“易于学习的类别”中的“人数规则”。 （Schapire和Freund〜 '12，Shalev-Shwartz和Ben-David '14。）正式，我们假设弱假设类别具有有界的VC维度。我们关注两个主要问题：（i）甲骨文的复杂性：产生准确的假设需要多少个弱假设？我们设计了一种新颖的增强算法，并证明它绕过了由Freund和Schapire（'95，'12）的经典下限。虽然下限显示$ \ omega（{1}/{\ gamma^2}）$弱假设有时是必要的，而有时则需要使用$ \ gamma $ -margin，但我们的新方法仅需要$ \ tilde {o}（{1}）（{1}） /{\ gamma}）$弱假设，前提是它们属于一类有界的VC维度。与以前的增强算法以多数票汇总了弱假设的算法不同，新的增强算法使用了更复杂（“更深”）的聚合规则。我们通过表明复杂的聚合规则实际上是规避上述下限是必要的，从而补充了这一结果。 （ii）表现力：通过提高有限的VC类的弱假设可以学习哪些任务？可以学到“遥远”的复杂概念吗？为了回答第一个问题，我们{介绍组合几何参数，这些参数捕获增强的表现力。}作为推论，我们为认真的班级的第二个问题提供了肯定的答案，包括半空间和决策树桩。一路上，我们建立并利用差异理论的联系。

A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work we consider list PAC learning where the goal is to output a list of $k$ predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to $k$-list learn a hypothesis class? We completely characterize $k$-list learnability in terms of a generalization of DS dimension that we call the $k$-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.

我们使用$ \ ell_p $损失和任意扰动集研究回归设置中测试时间对抗攻击的鲁棒性。我们解决了哪些功能类在此设置中可以学习的问题。我们表明，有限脂肪的脂肪尺寸是可以学习的。此外，对于凸功能类，它们甚至可以正确地学习。相比之下，一些非凸功能类别可证明需要不当学习算法。我们还讨论了不可知论学习的扩展。我们的主要技术是基于由脂肪崩溃尺寸确定的尺寸的对抗性稳健样品压缩方案的构造。

我们为在测试时间内对对抗性示例进行了学习预测的问题，为学习预测的问题提供了最小的最佳学习者。有趣的是，我们发现这需要新的算法思想和方法来实现对抗性的学习。特别是，我们从强烈的负面意义上表明，蒙塔瑟（Montasser），Hanneke和Srebro（2019）提出的强大学习者的次级临时性以及我们确定为本地学习者的更广泛的学习者。我们的结果是通过通过关键技术贡献采用全球视角来实现的：可能具有独立利益的全球单包含图，它概括了由于Haussler，Littlestone和Warminguth引起的经典单包含图（1994年）（1994年） ）。最后，作为副产品，我们确定了一个定性和定量表征哪些类别的预测因子$ \ mathcal {h} $的维度。由于Montasser等人，这解决了一个空旷的问题。 （2019年），并在固定稳健学习的样品复杂性上，在已建立的上限和下限之间结束了一个（潜在的）无限差距。

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

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

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.

收购数据是机器学习的许多应用中的一项艰巨任务，只有一个人希望并且预期人口风险在单调上汇率增加（更好的性能）。事实证明，甚至对于最小化经验风险的最大限度的算法，甚至不令人惊讶的情况。在训练中的风险和不稳定的非单调行为表现出并出现在双重血统描述中的流行深度学习范式中。这些问题突出了目前对学习算法和泛化的理解缺乏了解。因此，追求这种行为的表征是至关重要的，这是至关重要的。在本文中，我们在弱假设下获得了一致和风险的单调算法，从而解决了一个打开问题Viering等。 2019关于如何避免风险曲线的非单调行为。我们进一步表明，风险单调性不一定以更糟糕的风险率的价格出现。为实现这一目标，我们推出了持有某些非I.I.D的独立利益的新经验伯恩斯坦的浓度不等式。鞅差异序列等进程。

给定真实的假设类$ \ mathcal {h} $，我们在什么条件下调查有一个差异的私有算法，它从$ \ mathcal {h} $给出的最佳假设.I.i.d.数据。灵感来自最近的成果的二进制分类的相关环境（Alon等，2019; Bun等，2020），其中显示了二进制类的在线学习是必要的，并且足以追随其私人学习，Jung等人。 （2020）显示，在回归的设置中，$ \ mathcal {h} $的在线学习是私人可读性所必需的。这里的在线学习$ \ mathcal {h} $的特点是其$ \ eta $-sequentient胖胖子的优势，$ {\ rm sfat} _ \ eta（\ mathcal {h}）$，适用于所有$ \ eta> 0 $。就足够的私人学习条件而言，Jung等人。 （2020）显示$ \ mathcal {h} $私下学习，如果$ \ lim _ {\ eta \ downarrow 0} {\ rm sfat} _ \ eta（\ mathcal {h}）$是有限的，这是一个相当限制的健康）状况。我们展示了在轻松的条件下，\ LIM \ INF _ {\ eta \ downarrow 0} \ eta \ cdot {\ rm sfat} _ \ eta（\ mathcal {h}）= 0 $，$ \ mathcal {h} $私人学习，为\ \ rm sfat} _ \ eta（\ mathcal {h}）$ \ eta \ dockarrow 0 $ divering建立第一个非参数私人学习保证。我们的技术涉及一种新颖的过滤过程，以输出非参数函数类的稳定假设。

使用差异隐私（DP）学习的大多数工作都集中在每个用户具有单个样本的设置上。在这项工作中，我们考虑每个用户持有M $ Samples的设置，并且在每个用户数据的级别强制执行隐私保护。我们展示了，在这个设置中，我们可以学习少数用户。具体而言，我们表明，只要每个用户收到足够多的样本，我们就可以通过$（\ epsilon，\ delta）$ - dp算法使用$ o（\ log（1 / \ delta）来学习任何私人学习的课程/ \ epsilon）$用户。对于$ \ epsilon $ -dp算法，我们展示我们即使在本地模型中也可以使用$ o _ {\ epsilon}（d）$用户学习，其中$ d $是概率表示维度。在这两种情况下，我们在所需用户数量上显示了几乎匹配的下限。我们的结果的一个关键组成部分是全局稳定性的概括[Bun等，Focs 2020]允许使用公共随机性。在这种轻松的概念下，我们采用相关的采样策略来表明全局稳定性可以在样品数量的多项式牺牲中被提升以任意接近一个。

The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. Ideally, we would like the algorithm's performance to depend on the quality of the best predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is the best. We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.