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 study the fundamental question of how to define and measure the distance from calibration for probabilistic predictors. While the notion of perfect calibration is well-understood, there is no consensus on how to quantify the distance from perfect calibration. Numerous calibration measures have been proposed in the literature, but it is unclear how they compare to each other, and many popular measures such as Expected Calibration Error (ECE) fail to satisfy basic properties like continuity. We present a rigorous framework for analyzing calibration measures, inspired by the literature on property testing. We propose a ground-truth notion of distance from calibration: the $\ell_1$ distance to the nearest perfectly calibrated predictor. We define a consistent calibration measure as one that is a polynomial factor approximation to the this distance. Applying our framework, we identify three calibration measures that are consistent and can be estimated efficiently: smooth calibration, interval calibration, and Laplace kernel calibration. The former two give quadratic approximations to the ground truth distance, which we show is information-theoretically optimal. Our work thus establishes fundamental lower and upper bounds on measuring distance to calibration, and also provides theoretical justification for preferring certain metrics (like Laplace kernel calibration) in practice.

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

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

我们在高斯分布下使用Massart噪声与Massart噪声进行PAC学习半个空间的问题。在Massart模型中，允许对手将每个点$ \ mathbf {x} $的标签与未知概率$ \ eta（\ mathbf {x}）\ leq \ eta $，用于某些参数$ \ eta \ [0,1 / 2] $。目标是找到一个假设$ \ mathrm {opt} + \ epsilon $的错误分类错误，其中$ \ mathrm {opt} $是目标半空间的错误。此前已经在两个假设下研究了这个问题：（i）目标半空间是同质的（即，分离超平面通过原点），并且（ii）参数$ \ eta $严格小于$ 1/2 $。在此工作之前，当除去这些假设中的任何一个时，不知道非增长的界限。我们研究了一般问题并建立以下内容：对于$ \ eta <1/2 $，我们为一般半个空间提供了一个学习算法，采用样本和计算复杂度$ d ^ {o_ {\ eta}（\ log（1 / \ gamma） ）））}} \ mathrm {poly}（1 / \ epsilon）$，其中$ \ gamma = \ max \ {\ epsilon，\ min \ {\ mathbf {pr} [f（\ mathbf {x}）= 1]， \ mathbf {pr} [f（\ mathbf {x}）= -1] \} \} $是目标半空间$ f $的偏差。现有的高效算法只能处理$ \ gamma = 1/2 $的特殊情况。有趣的是，我们建立了$ d ^ {\ oomega（\ log（\ log（\ log（\ log））}}的质量匹配的下限，而是任何统计查询（SQ）算法的复杂性。对于$ \ eta = 1/2 $，我们为一般半空间提供了一个学习算法，具有样本和计算复杂度$ o_ \ epsilon（1）d ^ {o（\ log（1 / epsilon））} $。即使对于均匀半空间的子类，这个结果也是新的;均匀Massart半个空间的现有算法为$ \ eta = 1/2 $提供可持续的保证。我们与D ^ {\ omega（\ log（\ log（\ log（\ log（\ epsilon））} $的近似匹配的sq下限补充了我们的上限，这甚至可以为同类半空间的特殊情况而保持。

我们正式化并研究通过嵌入设计凸替代损失函数的自然方法，例如分类，排名或结构化预测等问题。在这种方法中，一个人将每一个有限的预测（例如排名）嵌入$ r^d $中的一个点，将原始损失值分配给这些要点，并以某种方式“凸出”损失以获得替代物。我们在这种方法和多面体（分段线性凸）的替代损失之间建立了牢固的联系：每个离散损失都被一些多面体损失嵌入，并且每个多面体损失都嵌入了一些离散的损失。此外，嵌入会产生一致的链接功能以及线性替代遗憾界限。正如我们用几个示例所说明的那样，我们的结果具有建设性。特别是，我们的框架为文献中各种多面体替代物以及不一致的替代物提供了简洁的证据或不一致的证据，它进一步揭示了这些代理人一致的离散损失。我们继续展示嵌入的其他结构，例如嵌入和匹配贝叶斯风险的等效性以及各种非算术概念的等效性。使用这些结果，我们确定与多面体替代物一起工作时，间接启发是一致性的必要条件也足够了。

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类的弱假设可以学习哪些任务？可以学到“遥远”的复杂概念吗？为了回答第一个问题，我们{介绍组合几何参数，这些参数捕获增强的表现力。}作为推论，我们为认真的班级的第二个问题提供了肯定的答案，包括半空间和决策树桩。一路上，我们建立并利用差异理论的联系。

我们建立了量子算法设计与电路下限之间的第一一般连接。具体来说，让$ \ mathfrak {c} $是一类多项式大小概念，假设$ \ mathfrak {c} $可以在统一分布下的成员查询，错误$ 1/2 - \ gamma $通过时间$ t $量子算法。我们证明如果$ \ gamma ^ 2 \ cdot t \ ll 2 ^ n / n $，则$ \ mathsf {bqe} \ nsubseteq \ mathfrak {c} $，其中$ \ mathsf {bqe} = \ mathsf {bque} [2 ^ {o（n）}] $是$ \ mathsf {bqp} $的指数时间模拟。在$ \ gamma $和$ t $中，此结果是最佳的，因为它不难学习（经典）时间$ t = 2 ^ n $（没有错误） ，或在Quantum Time $ t = \ mathsf {poly}（n）$以傅立叶采样为单位为1/2美元（2 ^ { - n / 2}）$。换句话说，即使对这些通用学习算法的边际改善也会导致复杂性理论的主要后果。我们的证明在学习理论，伪随机性和计算复杂性的几个作品上构建，并且至关重要地，在非凡的经典学习算法与由Oliveira和Santhanam建立的电路下限之间的联系（CCC 2017）。扩展他们对量子学习算法的方法，结果产生了重大挑战。为此，我们展示了伪随机发电机如何以通用方式意味着学习到较低的连接，构建针对均匀量子计算的第一个条件伪随机发生器，并扩展了Impagliazzo，JaiSwal的本地列表解码算法。 ，Kabanets和Wigderson（Sicomp 2010）通过微妙的分析到量子电路。我们认为，这些贡献是独立的兴趣，可能会发现其他申请。

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.

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

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

我们正规化并研究通过嵌入式设计凸代理损失功能的自然方法，诸如分类，排名或结构化预测等问题。在这种方法中，一个将每个主要的预测（例如\排名）嵌入$ \ mathbb {r} ^ d $中的一个点，将原始损耗值分配给这些点，并以某种方式“凸出”损失获得代理人。我们在这种方法和多面体（分段 - 线性凸）代理损失之间建立了强大的联系。鉴于任何多面体损失$ L $，我们提供了一个联系功能的建设，其中$ l $是它嵌入的损失的一致代理人。相反，我们展示了如何为任何给定的离散损失构建一致的多面体代理。我们的框架在文献中产生了各种多面体代理人的一致性或不一致的简洁证明，并且对于不一致的代理人，它进一步揭示了这些替代品的离散损失是一致的。我们展示了一些额外的嵌入结构，例如嵌入和匹配贝叶斯风险的等价，以及各种概念的非赎罪概念的等价。使用这些结果，我们建立了间接诱导，在使用多面体替代品时也足够了。

预测器将人口中的单个实例映射到间隔$ [0,1] $。对于群体的集合$ \ Mathcal C $ \ Mathcal C $ \ Mathcal C $的预测器是多校准的，如果它在$ \ Mathcal C $的每个设置上同时校准它。我们启动了对脚手架套装的建设的研究，一个小型收藏品$ \ Mathcal S $与多校准相对于$ \ Mathcal S $的财产，确保正确性，而不仅仅是校准。我们的方法是由民间智慧的启发，即神经网络的中间层学习高度结构化和有用的数据表示。

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

我们研究了用于线性回归的主动采样算法，该算法仅旨在查询目标向量$ b \ in \ mathbb {r} ^ n $的少量条目，并将近最低限度输出到$ \ min_ {x \ In \ mathbb {r} ^ d} \ | ax-b \ | $，其中$ a \ in \ mathbb {r} ^ {n \ times d} $是一个设计矩阵和$ \ | \ cdot \ | $是一些损失函数。对于$ \ ell_p $ norm回归的任何$ 0 <p <\ idty $，我们提供了一种基于Lewis权重采样的算法，其使用只需$ \ tilde {o}输出$（1+ \ epsilon）$近似解决方案（d ^ {\ max（1，{p / 2}）} / \ mathrm {poly}（\ epsilon））$查询到$ b $。我们表明，这一依赖于$ D $是最佳的，直到对数因素。我们的结果解决了陈和Derezi的最近开放问题，陈和Derezi \'{n} Ski，他们为$ \ ell_1 $ norm提供了附近的最佳界限，以及$ p \中的$ \ ell_p $回归的次优界限（1,2） $。我们还提供了$ O的第一个总灵敏度上限（D ^ {\ max \ {1，p / 2 \} \ log ^ 2 n）$以满足最多的$ p $多项式增长。这改善了Tukan，Maalouf和Feldman的最新结果。通过将此与我们的技术组合起来的$ \ ell_p $回归结果，我们获得了一个使$ \ tilde o的活动回归算法（d ^ {1+ \ max \ {1，p / 2 \}} / \ mathrm {poly}。 （\ epsilon））$疑问，回答陈和德里兹的另一个打开问题{n}滑雪。对于Huber损失的重要特殊情况，我们进一步改善了我们对$ \ tilde o的主动样本复杂性的绑定（d ^ {（1+ \ sqrt2）/ 2} / \ epsilon ^ c）$和非活跃$ \ tilde o的样本复杂性（d ^ {4-2 \ sqrt 2} / \ epsilon ^ c）$，由于克拉克森和伍德拉夫而改善了Huber回归的以前的D ^ 4 $。我们的敏感性界限具有进一步的影响，使用灵敏度采样改善了各种先前的结果，包括orlicz规范子空间嵌入和鲁棒子空间近似。最后，我们的主动采样结果为每种$ \ ell_p $ norm提供的第一个Sublinear时间算法。

我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法，用于辅助性Subgaussian分布。在这项工作中，我们开发了第一个有效的算法，用于强大的稀疏平均值估计，而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布，带有“认证有限”的$ t $ tum-矩和足够轻的尾巴，我们的算法达到了$ o（\ epsilon^{1-1/t}）$带有样品复杂性$的错误（\ epsilon^{1-1/t}） m =（k \ log（d））^{o（t）}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况，我们的算法达到了$ \ tilde o（\ epsilon）$的接近最佳错误，带有样品复杂性$ m = o（k^4 \ mathrm {polylog}（d）（d））/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

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

A major problem in machine learning is that of inductive bias: how to choose a learner's hypothesis space so that it is large enough to contain a solution to the problem being learnt, yet small enough to ensure reliable generalization from reasonably-sized training sets. Typically such bias is supplied by hand through the skill and insights of experts. In this paper a model for automatically learning bias is investigated. The central assumption of the model is that the learner is embedded within an environment of related learning tasks. Within such an environment the learner can sample from multiple tasks, and hence it can search for a hypothesis space that contains good solutions to many of the problems in the environment. Under certain restrictions on the set of all hypothesis spaces available to the learner, we show that a hypothesis space that performs well on a sufficiently large number of training tasks will also perform well when learning novel tasks in the same environment. Explicit bounds are also derived demonstrating that learning multiple tasks within an environment of related tasks can potentially give much better generalization than learning a single task.

Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask: what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in contexts where aggregate information is released about a database containing sensitive information about individuals.Our goal is a broad understanding of the resources required for private learning in terms of samples, computation time, and interaction. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (non-private) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private PAC learner for the class of parity functions. This result dispels the similarity between learning with noise and private learning (both must be robust to small changes in inputs), since parity is thought to be very hard to learn given random classification noise.Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Therefore, for local private learning algorithms, the similarity to learning with noise is stronger: local learning is equivalent to SQ learning, and SQ algorithms include most known noise-tolerant learning algorithms. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms. Because of the equivalence to SQ learning, this result also separates adaptive and nonadaptive SQ learning.