在许多应用程序的动机上，我们以错误的甲骨文研究聚类。在此问题中，有$ n $的项目属于$ k $未知群集，允许算法询问甲骨文是否属于同一群集。但是，Oracle的答案仅使用概率$ \ frac {1} {2}+\ frac {\ delta} {2} $正确。目的是恢复最少数量嘈杂的查询的隐藏群集。以前的作品表明，可以用$ o（\ frac {nk \ log n} {\ delta^2} + \ text {poly}（k，\ frac {1} {\ delta}，\ log n ）$ QUERIES，而$ \ Omega（\ frac {nk} {\ delta^2}）$ queries是必要的。因此，对于任何$ k $和$ \ \ delta $的值，上限和下限之间仍然存在非平凡的差距。在这项工作中，我们获得了广泛参数的第一个匹配上限和下限。特别是，具有$ o（\ frac {n（k + \ log n）} {\ delta^2} + \ text {poly}（k，\ frac {1} {\ delta}， n））提出了$查询。此外，我们证明了$ \ omega（\ frac {n \ log n} {\ delta^2}）$的新下限，它与现有$ \ omega（\ frac {nk} {\ delta^2结合在一起） }）$绑定，将我们的上限匹配到添加$ \ text {poly}（k，\ frac {1} {\ delta}，\ log n）$ term。为了获得新的结果，我们的主要成分是我们的问题与多臂强盗之间的有趣联系，这可能为其他类似问题提供有用的见解。

已经观察到图形神经网络（GNN）有时难以在跨节点上建模的长距离依赖性之间保持健康的平衡，同时避免了诸如过天平的节点表示的非线性后果。为了解决这个问题（以及其他事情），最近提出了两个单独的策略，即隐含和展开的GNN。前者将节点表示作为深度平衡模型的固定点，其可以有效地促进横跨图形的任意隐式传播，具有固定的存储器占用。相反，后者涉及将图形传播作为应用于某些图形正则化能功能的展开渐变迭代处理。在这种情况下激励，在本文中，我们仔细阐明了这些方法的相似性和差异，量化了他们所产生的解决方案的明确情况实际上是等同的，而行为发散的其他方法。这包括分析会聚，代表能力和解释性。我们还提供各种综合和公共现实世界基准的经验性头脑比较。

在本文中，我们研究了批次的嘴唇尖击匪徒问题，其中预期的奖励是Lipschitz，批量收集奖励观察。我们介绍了一种新颖的景观感知算法，称为批次的Lipschitz缩小（Blin），其自然适合批量反馈设置。特别是，我们表明，对于$ t $ -step问题，leipschitz奖励的zooming维度$ d_z $，我们的算法从理论上最佳的$ \ widetilde {\ mathcal {o}}}左右达到了left（t ^ {\ frac {d_z + 1} {d_z + 2}} \右）只使用$ \ mathcal {o} \ left（\ log \ log t \右）$批次。对于下限，我们展示在一个以$ B $ -batches的环境中，对于任何策略$ \ pi $，存在一个问题实例，使得预期的遗憾是由$ \ widetilde {\ omega} \ left的较低限制（ r_z（t）^ \ frac {1} {1- \左（\ frac {1} {d + 2}右）^ b} \右）$，其中$ r_z（t）$是遗憾的遗憾Vanilla Lipschitz匪徒取决于缩放维度$ d_z $，$ d $是ARM空间的尺寸。作为直接后果，需要$ B = OMEGA（\ log \ log t）$批次来实现遗憾下限，并且BLIN算法是最佳的。

作为推荐系统的主要协作过滤方法，一位矩阵完成需要用户收集的数据来提供个性化服务。由于阴险的攻击和意外推断，用户数据的发布通常会引起严重的隐私问题。为了解决此问题，差异隐私（DP）已在标准矩阵完成模型中广泛使用。但是，迄今为止，关于如何在一位矩阵完成中应用DP来实现隐私保护的知之甚少。在本文中，我们提出了一个统一的框架，以确保使用DP对单位矩阵完成的强大隐私保证。在我们的框架中，我们开发了与一位矩阵完成的不同阶段相对应的四种不同的私人扰动机制。对于每种机制，我们设计一个隐私性算法，并提供在适当条件下绑定的理论恢复误差。关于合成和现实世界数据集的数值实验证明了我们的建议的有效性。与没有隐私保护的一位矩阵完成相比，我们提出的机制可以维持高级隐私保护，而边际丧失完成精度。

许多代表性图形神经网络，例如GPR-GNN和CHEBNET，具有曲线图谱滤波器的图形卷曲。但是，现有的工作要么应用预定义的滤波器权重，或者没有必要的约束来学习它们，这可能导致过度简化或不良滤波器。为了克服这些问题，我们提出了一种具有理论支持的新型图形神经网络的Bernnet，提供了一种简单但有效的设计和学习任意曲线图谱滤波器的方案。特别是，对于在图形的标准化Laplacian谱上的任何过滤器上，我们的Bernnet通过命令估计它是一个订单 - $ k $伯尔尼斯坦多项式近似，并通过设置伯尔尼斯坦的系数来设计其光谱特性。此外，我们可以基于观察的图形及其相关信号学习系数（和相应的滤波器权重），从而实现专门用于数据的BERNNET。我们的实验表明，Bernnet可以学习任意光谱滤波器，包括复杂的带抑制和梳状滤波器，并且它在真实的图形建模任务中实现了卓越的性能。代码可在https://github.com/ivam-he/bernnet上获得。

在[Mannor和Shamir，Neurips 2011]中提出的图表反馈的强盗问题由指向图$ G =（v，e）$，其中$ v $是强盗臂的集合，并且一旦触发臂一旦触发，所有入射武器都被观察到。基本问题是图形的结构如何影响Min-Max后悔。我们提出了分数分别捕捉上限和下限的美元弱统治号码$ \ delta ^ * $和$ k $ -packing独立号码的概念。我们表明，两种概念通过将它们与弱主导集合的线性程序和其双分数顶点包装组对齐，通过对齐它们通过对齐它们是固有的连接。基于这一联系，我们利用了强大的二元定理来证明一般遗憾的上限$ o \ left（\ left（\ delta ^ * \ log | v | \右）^ {\ frac {1} {3}} t ^ {\ frac {2} {3}} \右）$和一个下限$ \ oomega \ left（\ left（\ delta ^ * / \ alpha \ over）^ {\ frac {1} {3}} t ^ {\ frac {2} {3}}右）$ where $ \ alpha $是双线性程序的完整性差距。因此，我们的界限紧紧达到一个$ \左（\ log | v | \ over）^ {\ frac {1} {3}} $ thace，其中顶点包装问题包括树和图表有限度。此外，我们表明，对于几个特殊的图形，我们可以摆脱$ \左（\ log | v | \右）^ {\ frac {1} {3}} $ factor并建立最佳遗憾。

尽管近期图形神经网络（GNN）成功，但常见的架构通常表现出显着的限制，包括对过天飞机，远程依赖性和杂散边缘的敏感性，例如，由于图形异常或对抗性攻击。至少部分地解决了一个简单的透明框架内的这些问题，我们考虑了一个新的GNN层系列，旨在模仿和整合两个经典迭代算法的更新规则，即近端梯度下降和迭代重复最小二乘（IRLS）。前者定义了一个可扩展的基础GNN架构，其免受过性的，而仍然可以通过允许任意传播步骤捕获远程依赖性。相反，后者产生了一种新颖的注意机制，该注意机制被明确地锚定到底层端到端能量函数，以及相对于边缘不确定性的稳定性。当结合时，我们获得了一个非常简单而强大的模型，我们在包括标准化基准，与异常扰动的图形，具有异化的图形和涉及远程依赖性的图形的不同方案的极其简单而强大的模型。在此过程中，我们与已明确为各个任务设计的SOTA GNN方法进行比较，实现竞争或卓越的节点分类准确性。我们的代码可以在https://github.com/fftyyy/twirls获得。

Graph convolutional networks (GCNs) are a powerful deep learning approach for graph-structured data. Recently, GCNs and subsequent variants have shown superior performance in various application areas on real-world datasets. Despite their success, most of the current GCN models are shallow, due to the over-smoothing problem.In this paper, we study the problem of designing and analyzing deep graph convolutional networks. We propose the GCNII, an extension of the vanilla GCN model with two simple yet effective techniques: Initial residual and Identity mapping. We provide theoretical and empirical evidence that the two techniques effectively relieves the problem of over-smoothing. Our experiments show that the deep GCNII model outperforms the state-of-the-art methods on various semi-and fullsupervised tasks. Code is available at https: //github.com/chennnM/GCNII.

This paper focuses on designing efficient models with low parameters and FLOPs for dense predictions. Even though CNN-based lightweight methods have achieved stunning results after years of research, trading-off model accuracy and constrained resources still need further improvements. This work rethinks the essential unity of efficient Inverted Residual Block in MobileNetv2 and effective Transformer in ViT, inductively abstracting a general concept of Meta-Mobile Block, and we argue that the specific instantiation is very important to model performance though sharing the same framework. Motivated by this phenomenon, we deduce a simple yet efficient modern \textbf{I}nverted \textbf{R}esidual \textbf{M}obile \textbf{B}lock (iRMB) for mobile applications, which absorbs CNN-like efficiency to model short-distance dependency and Transformer-like dynamic modeling capability to learn long-distance interactions. Furthermore, we design a ResNet-like 4-phase \textbf{E}fficient \textbf{MO}del (EMO) based only on a series of iRMBs for dense applications. Massive experiments on ImageNet-1K, COCO2017, and ADE20K benchmarks demonstrate the superiority of our EMO over state-of-the-art methods, \eg, our EMO-1M/2M/5M achieve 71.5, 75.1, and 78.4 Top-1 that surpass \textbf{SoTA} CNN-/Transformer-based models, while trading-off the model accuracy and efficiency well.

Supervised Question Answering systems (QA systems) rely on domain-specific human-labeled data for training. Unsupervised QA systems generate their own question-answer training pairs, typically using secondary knowledge sources to achieve this outcome. Our approach (called PIE-QG) uses Open Information Extraction (OpenIE) to generate synthetic training questions from paraphrased passages and uses the question-answer pairs as training data for a language model for a state-of-the-art QA system based on BERT. Triples in the form of <subject, predicate, object> are extracted from each passage, and questions are formed with subjects (or objects) and predicates while objects (or subjects) are considered as answers. Experimenting on five extractive QA datasets demonstrates that our technique achieves on-par performance with existing state-of-the-art QA systems with the benefit of being trained on an order of magnitude fewer documents and without any recourse to external reference data sources.