相似性函数衡量了元素的可比较对，并在各种应用程序中起关键作用，例如聚类问题和个人公平的考虑。但是，不应始终将获得准确的相似性函数访问。具体而言，当要比较的要素是由不同的分布产生的，换句话说属于不同的``人口统计学''群体时，对其真实相似性的了解可能很难获得。在这项工作中，我们提出了一个抽样框架，该框架仅使用有限的专家反馈来学习这些跨组相似性功能。我们以严格的界限显示了分析结果，并通过大量实验从经验上验证我们的算法。

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

本文展示了如何适应$ k $ -MEANS问题的几种简单和经典的基于采样的算法，以使用离群值设置。最近，Bhaskara等人。 （Neurips 2019）展示了如何将古典$ K $ -MEANS ++算法适应与异常值的设置。但是，他们的算法需要输出$ o（\ log（k）\ cdot z）$ outiers，其中$ z $是true Outliers的数量，以匹配$ o（\ log k）$ - 近似值的$ k的近似保证$ -Means ++。在本文中，我们以他们的想法为基础，并展示了如何适应几个顺序和分布式的$ k $ - 均值算法，但使用离群值来设置，但具有更强的理论保证：我们的算法输出$（1+ \ VAREPSILON）z $ OUTLIERS Z $ OUTLIERS在实现$ o（1 / \ varepsilon）$ - 近似目标函数的同时。在顺序世界中，我们通过改编Lattanzi和Sohler的最新算法来实现这一目标（ICML 2019）。在分布式设置中，我们适应了Guha等人的简单算法。 （IEEE Trans。知道和数据工程2003）以及Bahmani等人的流行$ K $ -Means $ \ | $。 （PVLDB 2012）。我们技术的理论应用是一种具有运行时间$ \ tilde {o}（nk^2/z）$的算法，假设$ k \ ll z \ ll n $。这与Omacle模型中此问题的$ \ Omega（NK^2/z）$的匹配下限相互补。

我们提出了改进的算法，并为身份测试$ n $维分布的问题提供了统计和计算下限。在身份测试问题中，我们将作为输入作为显式分发$ \ mu $，$ \ varepsilon> 0 $，并访问对隐藏分布$ \ pi $的采样甲骨文。目标是区分两个分布$ \ mu $和$ \ pi $是相同的还是至少$ \ varepsilon $ -far分开。当仅从隐藏分布$ \ pi $中访问完整样本时，众所周知，可能需要许多样本，因此以前的作品已经研究了身份测试，并额外访问了各种有条件采样牙齿。我们在这里考虑一个明显弱的条件采样甲骨文，称为坐标Oracle，并在此新模型中提供了身份测试问题的相当完整的计算和统计表征。我们证明，如果一个称为熵的分析属性为可见分布$ \ mu $保留，那么对于任何使用$ \ tilde {o}（n/\ tilde {o}），有一个有效的身份测试算法Varepsilon）$查询坐标Oracle。熵的近似张力是一种经典的工具，用于证明马尔可夫链的最佳混合时间边界用于高维分布，并且最近通过光谱独立性为许多分布族建立了最佳的混合时间。我们将算法结果与匹配的$ \ omega（n/\ varepsilon）$统计下键进行匹配的算法结果补充，以供坐标Oracle下的查询数量。我们还证明了一个计算相变：对于$ \ {+1，-1，-1 \}^n $以上的稀疏抗抗铁磁性模型，在熵失败的近似张力失败的状态下，除非RP = np，否则没有有效的身份测试算法。

模糊或柔软$ k $ -means目标是众所周知的$ k $ -means问题的流行泛化，将$ k $ -means扩展到不确定，模糊和否则难以群集的数据集的聚类能力。在本文中，我们提出了一个半监督的主动聚类框架，其中允许学习者与Oracle（域专家）进行交互，询问一组所选项目之间的相似性。我们研究了本框架中的聚类查询和计算复杂性。我们证明具有一些这样的相似性查询使得一个人能够将多项式时间近似算法获得到另外的辅助NP难题。特别是，我们提供了在此设置中的模糊聚类的算法，该算法询问$ O（\ mathsf {poly}（k）\ log n）$相似查询并使用多项式 - 时间复杂度运行，其中$ n $是项目的数量。模糊$ k $ -means目标是非渗透，$ k $ -means作为一个特殊情况，相当于一些其他通用非核解问题，如非负矩阵分解。普遍存在的LLOYD型算法（或交替的最小化算法）可以以局部最小粘在一起。我们的结果表明，通过制作一些相似性查询，问题变得更加易于解决。最后，我们通过现实世界数据集测试我们的算法，展示了其在现实世界应用中的有效性。

Arthur和Vassilvitskii的著名$ K $ -MEANS ++算法[SODA 2007]是解决实践中$ K $ - 英镑问题的最流行方式。该算法非常简单：它以随机的方式均匀地对第一个中心进行采样，然后始终将每个$ K-1 $中心的中心取样与迄今为止最接近最接近中心的平方距离成比例。之后，运行了劳埃德的迭代算法。已知$ k $ -Means ++算法可以返回预期的$ \ theta（\ log K）$近似解决方案。在他们的开创性工作中，Arthur和Vassilvitskii [Soda 2007]询问了其以下\ emph {greedy}的保证：在每一步中，我们采样了$ \ ell $候选中心，而不是一个，然后选择最小化新的中心成本。这也是$ k $ -Means ++在例如中实现的方式。流行的Scikit-Learn库[Pedregosa等人； JMLR 2011]。我们为贪婪的$ k $ -Means ++提供几乎匹配的下限和上限：我们证明它是$ o（\ ell^3 \ log^3 k）$ - 近似算法。另一方面，我们证明了$ \ omega的下限（\ ell^3 \ log^3 k / \ log^2（\ ell \ log k））$。以前，只有$ \ omega（\ ell \ log k）$下限是已知的[bhattacharya，eube，r \“ ogllin，schmidt; esa 2020），并且没有已知的上限。

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.

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

Consider the following abstract coin tossing problem: Given a set of $n$ coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point -- any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only $O(\log{n})$ coins and then iteratively refine it further and further, leading to algorithms with $O(\log\log{(n)})$ memory, $O(\log^*{(n)})$ memory, and finally a one that only stores a single extra coin in memory -- the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the $k$ most biased coins as well as other exploration problems such as finding top-$k$ elements using noisy comparisons or finding an $\epsilon$-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.

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

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

我们建立了量子算法设计与电路下限之间的第一一般连接。具体来说，让$ \ 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）通过微妙的分析到量子电路。我们认为，这些贡献是独立的兴趣，可能会发现其他申请。

机器学习中的歧视通常沿多个维度（又称保护属性）出现；因此，希望确保\ emph {交叉公平} - 即，没有任何子组受到歧视。众所周知，确保\ emph {边际公平}对于每个维度而言，独立不够。但是，由于亚组的指数数量，直接测量数据交叉公平性是不可能的。在本文中，我们的主要目标是通过统计分析详细了解边际和交叉公平之间的关系。我们首先确定一组足够的条件，在这些条件下可以获得确切的关系。然后，在一般情况下，我们证明了相交公平性的高概率的界限（通过边际公平和其他有意义的统计量很容易计算）。除了它们的描述价值之外，我们还可以利用这些理论界限来得出一种启发式，从而通过以相关的方式选择了我们描述相交子组的保护属性来改善交叉公平的近似和边界。最后，我们测试了实际和合成数据集的近似值和界限的性能。

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

众所周知，给定顺滑，界限 - 下面，并且可能的非透露函数，标准梯度的方法可以找到$ \ epsilon $ -stationary积分（渐变范围小于$ \ epsilon $）$ \ mathcal {O}（1 / \ epsilon ^ 2）$迭代。然而，许多重要的非渗透优化问题，例如与培训现代神经网络相关的问题，本质上是不平衡的，使这些结果不适用。在本文中，我们研究了来自Oracle复杂性视点的非透射性优化，其中假设算法仅向各个点处的函数提供访问。我们提供两个主要结果：首先，我们考虑越近$ \ epsilon $ -storationary积分的问题。这也许是找到$ \ epsilon $ -storationary积分的最自然的放松，这在非对象案例中是不可能的。我们证明，对于任何距离和epsilon $小于某些常数，无法有效地实现这种轻松的目标。我们的第二次结果涉及通过减少到平滑的优化来解决非光度非渗透优化的可能性：即，在光滑的近似值对目标函数的平滑近似下应用平滑的优化方法。对于这种方法，我们在温和的假设下证明了oracle复杂性和平滑度之间的固有权衡：一方面，可以非常有效地平滑非光滑非凸函数（例如，通过随机平滑），但具有尺寸依赖性因子在平滑度参数中，在插入标准平滑优化方法时，这会强烈影响迭代复杂性。另一方面，可以用合适的平滑方法消除这些尺寸因子，而是仅通过使平滑过程的Oracle复杂性呈指数大。

在使用提供明确定义的隐私保证的用户数据时，至关重要。在这项工作中，我们旨在与第三方私下操纵和分享整个稀疏数据集。实际上，差异隐私已成为隐私的黄金标准，但是，当涉及到稀疏数据集时，作为我们的主要结果之一，我们证明\ emph {any}与最初的私人机制有差异化的私人机制数据集注定要拥有非常薄弱的隐私保证。因此，我们需要选择其他隐私概念，例如$ k $ - 匿名性更好地在这种情况下保存实用程序。在这项工作中，我们介绍了$ k $ - 匿名的变体，我们称之为平滑$ k $ - 匿名和设计简单算法，可有效地提供平滑的$ k $ - 匿名性。我们进一步执行经验评估以支持我们的理论保证，并表明我们的算法改善了匿名数据下游机器学习任务的性能。

我们研究了在存在$ \ 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 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

在本文中，我们采用一种公理方法来定义满足一组一致性和公平公理的随机组排名。我们表明，这导致了通过合并来自不同敏感人群组的给定排名列表的排名，同时满足了最高等级中每个组的表示下限和上限，从而导致了唯一的分布$ \ MATHCAL {D} $。与确定性排名相比，随机或随机排名在最近的文献中引起了人们的关注。即使存在隐式偏见，不完整的相关信息，或者只有序数排名而不是相关性分数或实用程序值，我们的问题公式即使有效。我们提出了三种算法，以从上面提到的分布$ \ mathcal {d} $中采样一个随机的集体排名。我们的第一个算法样本排名从分配$ \ epsilon $ -close到$ \ nathcal {d} $的总变化距离，并且在所有输入参数中都在运行时间多项式，而$ 1/\ epsilon $，有足够的差距在所有组的上限和下限表示约束之间。我们的第二个算法示例从$ \ Mathcal {d} $恰好在组数量的时间指数中排名。我们的第三个算法从$ \ mathcal {d} $恰好从$ \ mathcal {d} $示例随机组公平排名，并且当每个组的上限和下限之间的差距很小时，比第一个算法更快。我们在实验中验证了上述算法的上述保证，该算法在最高排名中的群体公平性和现实世界数据集的每个等级中的代表性。

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

监督学习通常依赖于真实标签的手动注释。当有许多潜在的类别时，寻找最佳的班级对于人类注释者可能会过时。另一方面，比较两个候选标签通常要容易得多。我们专注于这种成对的监督，并询问如何有效地用于学习，尤其是在积极学习中。在这种情况下，我们获得了一些有见地的结果。原则上，可以使用$ K-1 $ Active查询来找到最好的$ K $标签。我们表明，有一种自然阶级，这种方法是最佳选择的，并且有更具比较的主动学习方案。我们分析中的一个关键要素是真实分布的“标签邻域图”，如果两个类共享决策边界，则在两个类之间具有优势。我们还表明，在PAC设置中，成对比较在最坏情况下不能提供改善的样品复杂性。我们通过实验补充了理论结果，清楚地证明了邻里图对样品复杂性的影响。