组件是大量的神经元，其同步射击被假设代表记忆，概念，单词和其他认知类别。据信，组件可以在高级认知现象和低级神经活动之间提供桥梁。最近，已经显示出一种称为“大会微积分（AC）”的计算系统，其曲目在集会上具有生物学上合理的操作，能够模拟由任意空间的计算模拟，但也可以模拟复杂的认知现象，例如语言，推理和规划和计划。但是，尚不清楚组装可以调解学习的机制。在这里，我们提出了这样一种机制，并严格证明，对于标记组件的分布定义的简单分类问题，可以可靠地形成代表每个类别的新组装，以响应类中的一些刺激。因此，该组件是对同一类的新刺激的响应可靠地召回的。此外，只要相应的类是相似组件的簇时，这些类组件就可以区分。为了证明这些结果，我们利用具有动态边缘权重的随机图理论来估计激活顶点的序列，在过去五年中对该领域的先前计算和定理产生了强烈的概括。这些定理通过实验证明了组件的成功形成，这些定理代表了从此类分布中绘制的合成数据以及MNIST上的概念类别的形成，并在MNIST上，这可以通过每个数字的一​​个组装来分类。该机制被视为一种学习算法，完全是在线上，从很少的样本中概括，只需要轻度的监督 - 在大脑模型中学习的所有关键属性。

我们研究了小组测试问题，其目标是根据合并测试的结果，确定一组k感染的人，这些k含有稀有疾病，这些人在经过测试中至少有一个受感染的个体时返回阳性的结果。团体。我们考虑将个人分配给测试的两个不同的简单随机过程：恒定柱设计和伯努利设计。我们的第一组结果涉及基本统计限制。对于恒定柱设计，我们给出了一个新的信息理论下限，这意味着正确识别的感染者的比例在测试数量越过特定阈值时会经历急剧的“全或全或无所不包”的相变。对于Bernoulli设计，我们确定解决相关检测问题所需的确切测试数量（目的是区分小组测试实例和纯噪声），改善Truong，Aldridge和Scarlett的上限和下限（2020）。对于两个小组测试模型，我们还研究了计算有效（多项式时间）推理程序的能力。我们确定了解决检测问题的低度多项式算法所需的精确测试数量。这为在少量稀疏度的检测和恢复问题中都存在固有的计算统计差距提供了证据。值得注意的是，我们的证据与Iliopoulos和Zadik（2021）相反，后者预测了Bernoulli设计中没有计算统计差距。

我们研究了如何在大脑中占有结构的概念的问题。具体而言，我们介绍了分层结构化概念的模型，我们展示了一种生物合理的神经网络如何识别这些概念，以及如何首先学习它们。我们的主要目标是为这些任务介绍一般框架，并正式证明了如何实现（认可和学习）。我们表明，即使在存在噪音，也可以完成两个任务。为了学习，我们正式分析了OJA的规则，是一个众所周知的生物合理的规则，用于调整突触的重量。我们将学习结果与下限相关联，以便识别某个分层深度的概念，神经网络必须具有相应数量的层。

我们重新审视块世界中的规划问题，我们为此任务实施了一个已知的启发式。重要的是，我们的实施是生物学上可言论的，因此它仅通过神经元的尖峰进行。尽管在过去五十年中，在块世界中已经在块世界中完成了很多，但我们认为这是它的第一个算法。输入是编码初始块堆栈以及目标集合的符号序列，并且输出是一系列运动命令，例如“将顶部块放在桌子上的堆栈1中”。该程序是在组装微积分中写入的，最近提出的计算框架通过弥合神经活动与认知功能之间的差距来模拟大脑中的计算。其基本对象是神经元的组件（稳定的神经元组，其同时射击表示该主题正在考虑对象，概念，单词等），其命令包括项目和合并，其执行模型基于广泛接受的原则神经科学。该框架中的一个程序基本上建立了神经元的动态系统和最终具有高概率，实现任务的神经元和突触。这项工作的目的是凭经验建立了大会微积分中的合理大计划可以正确可靠地执行;这相当现实 - 如果理想化 - 更高的认知功能，例如在块世界中规划，可以通过这些程序成功实现。

训练神经网络的一种常见方法是将所有权重初始化为独立的高斯向量。我们观察到，通过将权重初始化为独立对，每对由两个相同的高斯向量组成，我们可以显着改善收敛分析。虽然已经研究了类似的技术来进行随机输入[Daniely，Neurips 2020]，但尚未使用任意输入进行分析。使用此技术，我们展示了如何显着减少两层relu网络所需的神经元数量，均在逻辑损失的参数化设置不足的情况下，大约$ \ gamma^{ - 8} $ [Ji and telgarsky，ICLR， 2020]至$ \ gamma^{ - 2} $，其中$ \ gamma $表示带有神经切线内核的分离边距，以及在与平方损失的过度参数化设置中，从大约$ n^4 $ [song [song]和Yang，2019年]至$ n^2 $，隐含地改善了[Brand，Peng，Song和Weinstein，ITCS 2021]的近期运行时间。对于参数不足的设置，我们还证明了在先前工作时改善的新下限，并且在某些假设下是最好的。

The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit when it is overparameterized?In this work, we prove that overparameterized neural networks can learn some notable concept classes, including two and three-layer networks with fewer parameters and smooth activations. Moreover, the learning can be simply done by SGD (stochastic gradient descent) or its variants in polynomial time using polynomially many samples. The sample complexity can also be almost independent of the number of parameters in the network.On the technique side, our analysis goes beyond the so-called NTK (neural tangent kernel) linearization of neural networks in prior works. We establish a new notion of quadratic approximation of the neural network (that can be viewed as a second-order variant of NTK), and connect it to the SGD theory of escaping saddle points.

我们对解决几个自然学习问题的一通流算法所需的记忆量给出了下限。在$ \ {0,1 \}^d $中的示例的环境中，可以使用$ \ kappa $ bits对最佳分类器进行编码，我们表明，使用近距离数量的示例学习的算法，$ \ tilde o（\ kappa）$，必须使用$ \ tilde \ omega（d \ kappa）$空间。我们的空间界限与问题自然参数化的环境空间的维度相匹配，即使在示例和最终分类器的大小上是二次的。例如，在$ d $ -sparse线性分类器的设置中，$ \ kappa = \ theta（d \ log d）$，我们的空间下限是$ \ tilde \ omega（d^^^ 2）$。我们的边界与流长$ n $优雅地降级，通常具有$ \ tilde \ omega \ left（d \ kappa \ cdot \ frac \ frac {\ kappa} {n} {n} \ right）$。 $ \ omega（d \ kappa）$的形式的界限以学习奇偶校验和有限字段定义的其他问题而闻名。在狭窄的样本量范围内适用的边界也以线性回归而闻名。对于最近学习应用程序中常见的类型的问题，我们的第一个范围是适用于各种输入尺寸的问题。

经典的算法adaboost允许转换一个弱学习者，这是一种算法，它产生的假设比机会略好，成为一个强大的学习者，在获得足够的培训数据时，任意高精度。我们提出了一种新的算法，该算法从弱学习者中构建了一个强大的学习者，但比Adaboost和所有其他弱者到强大的学习者使用训练数据少，以实现相同的概括界限。样本复杂性下限表明我们的新算法使用最小可能的训练数据，因此是最佳的。因此，这项工作解决了从弱学习者中构建强大学习者的经典问题的样本复杂性。

Graph-based learning is a rapidly growing sub-field of machine learning with applications in social networks, citation networks, and bioinformatics. One of the most popular models is graph attention networks. They were introduced to allow a node to aggregate information from features of neighbor nodes in a non-uniform way, in contrast to simple graph convolution which does not distinguish the neighbors of a node. In this paper, we study theoretically this expected behaviour of graph attention networks. We prove multiple results on the performance of graph attention mechanism for the problem of node classification for a contextual stochastic block model. Here the node features are obtained from a mixture of Gaussians and the edges from a stochastic block model. We show that in an "easy" regime, where the distance between the means of the Gaussians is large enough, graph attention is able to distinguish inter-class from intra-class edges, and thus it maintains the weights of important edges and significantly reduces the weights of unimportant edges. Consequently, we show that this implies perfect node classification. In the "hard" regime, we show that every attention mechanism fails to distinguish intra-class from inter-class edges. We evaluate our theoretical results on synthetic and real-world data.

Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high "standard" accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of "standard" learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

尽管使用对抗性训练捍卫深度学习模型免受对抗性扰动的经验成功，但到目前为止，仍然不清楚对抗性扰动的存在背后的原则是什么，而对抗性培训对神经网络进行了什么来消除它们。在本文中，我们提出了一个称为特征纯化的原则，在其中，我们表明存在对抗性示例的原因之一是在神经网络的训练过程中，在隐藏的重量中积累了某些小型密集混合物；更重要的是，对抗训练的目标之一是去除此类混合物以净化隐藏的重量。我们介绍了CIFAR-10数据集上的两个实验，以说明这一原理，并且一个理论上的结果证明，对于某些自然分类任务，使用随机初始初始化的梯度下降训练具有RELU激活的两层神经网络确实满足了这一原理。从技术上讲，我们给出了我们最大程度的了解，第一个结果证明，以下两个可以同时保持使用RELU激活的神经网络。 （1）对原始数据的训练确实对某些半径的小对抗扰动确实不舒适。 （2）即使使用经验性扰动算法（例如FGM），实际上也可以证明对对抗相同半径的任何扰动也可以证明具有强大的良好性。最后，我们还证明了复杂性的下限，表明该网络的低复杂性模型，例如线性分类器，低度多项式或什至是神经切线核，无论使用哪种算法，都无法防御相同半径的扰动训练他们。

在随机子集总和问题中，给定$ n $ i.i.d.随机变量$ x_1，...，x_n $，我们希望将[-1,1] $ in [-1,1] $的任何点$ z \作为合适子集的总和$ x_ {i_1（z）}，...，x_ {i_s（z）} $的$，最多$ \ varepsilon $。尽管有简单的陈述，但这个问题还是理论计算机科学和统计力学的基本兴趣。最近，它因其在人工神经网络理论中的影响而引起了人们的重新关注。该问题的一个明显的多维概括是考虑$ n $ i.i.d. \ $ d $ - 二维随机向量，目的是近似于[-1,1]^d $的每个点$ \ Mathbf {z} \。令人惊讶的是，在Lueker的1998年证明，在一维设置中，$ n = o（\ log \ frac 1 \ varepsilon）$ samples $ samples $ samples具有很高可能性的近似属性，在实现上述概括方面几乎没有进展。在这项工作中，我们证明，在$ d $ dimensions中，$ n = o（d^3 \ log \ frac 1 \ varepsilon \ cdot（\ log \ frac 1 \ frac 1 \ varepsilon + log d d））$ samples $ sample近似属性具有很高的概率。作为强调该结果潜在兴趣的应用程序，我们证明了最近提出的神经网络模型表现出\ emph {通用}：具有很高的概率，该模型可以在参数数量中近似多项式开销中的任何神经网络。

在本文中，我们研究了时间速度与非IID数据的协作学习模型中学习过程的交流次数之间的权衡，其中多个代理与可能不同的环境互动，他们希望学习一个目标。汇总环境。我们在匪徒理论中使用一个基本问题，称为多臂匪徒中最佳ARM识别作为传递以下概念信息的工具：对非IID数据的协作学习比在IID数据上更加困难。特别是，我们显示以下内容：a）非IID数据设置中的加速度可能小于$ 1 $（即放缓）。当回合$ r = o（1）$的数量时，我们将至少需要多项式数量的代理（就武器数量而言）来实现大于$ 1 $的加速。这与IID数据设置形成鲜明对比，在$ r \ ge 2 $中，无论代理数量如何，加速度总是至少$ 1 $。 b）学习过程中的适应性无济于事。这与IID数据设置形成鲜明对比，为了实现相同的速度，最佳的非自适应算法需要比最佳自适应算法要大得多。在技​​术空间中，我们进一步开发了Arxiv：1904.03293中引入的广义消除技术。我们表明，在使用复杂的硬输入分布并直接证明自适应算法的下限时，分配类别的隐式表示非常有用。

这项工作确立了梯度流量（GF）和随机梯度下降（SGD）的低测试误差（SGD）在具有标准初始化的两层relu网络上，在三个方案中，关键的重量集很少旋转（自然要么是由于GF和SGD，要么是由于GF和SGD，或达到人为的约束），并利用边缘作为核心分析技术。第一个制度几乎是初始化的，特别是直到权重以$ \ mathcal {o}（\ sqrt m）$移动为止，其中$ m $表示网络宽度，这与$ \ mathcal {o}（O}（O}（O}）形成鲜明对比） 1）神经切线内核（NTK）允许的重量运动；在这里显示，GF和SGD仅需要网络宽度和样本数量与NTK边缘成反比，此外，GF至少达到了NTK保证金本身，这足以建立避免距离范围目标的不良KKT点的逃脱，该点的距离逃脱了。而先前的工作只能确定不折扣但任意的边缘。第二个制度是神经塌陷（NC）设置，其中数据在于极度隔离的组中，样品复杂性尺度与组数。在这里，先前工作的贡献是对初始化的整个GF轨迹的分析。最后，如果内层的权重限制为仅在规范中变化并且无法旋转，则具有较大宽度的GF达到了全球最大边缘，并且其样品复杂度与它们的逆尺度相比；这与先前的工作相反，后者需要无限的宽度和一个棘手的双收敛假设。作为纯粹的技术贡献，这项工作开发了各种潜在功能和其他工具，希望有助于未来的工作。

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

预测性编码提供了对皮质功能的潜在统一说明 - 假设大脑的核心功能是最小化有关世界生成模型的预测错误。该理论与贝叶斯大脑框架密切相关，在过去的二十年中，在理论和认知神经科学领域都产生了重大影响。基于经验测试的预测编码的改进和扩展的理论和数学模型，以及评估其在大脑中实施的潜在生物学合理性以及该理论所做的具体神经生理学和心理学预测。尽管存在这种持久的知名度，但仍未对预测编码理论，尤其是该领域的最新发展进行全面回顾。在这里，我们提供了核心数学结构和预测编码的逻辑的全面综述，从而补充了文献中最新的教程。我们还回顾了该框架中的各种经典和最新工作，从可以实施预测性编码的神经生物学现实的微电路到预测性编码和广泛使用的错误算法的重新传播之间的紧密关系，以及对近距离的调查。预测性编码和现代机器学习技术之间的关系。

深度分离结果提出了对深度神经网络过较浅的架构的好处的理论解释，建立前者具有卓越的近似能力。然而，没有已知的结果，其中更深的架构利用这种优势成为可提供的优化保证。我们证明，当数据由具有满足某些温和假设的径向对称的分布产生的数据时，梯度下降可以使用具有两层S形激活的深度2神经网络有效地学习球指示器功能，并且隐藏层固定在一起训练。由于众所周知，当使用用单层非线性的深度2网络（Safran和Shamir，2017）使用深度2网络时，球指示器难以近似于一定的重型分配，这建立了我们最好的知识，基于第一优化的分离结果，其中近似架构的近似效益在实践中可怕的。我们的证明技术依赖于随机特征方法，该方法减少了用单个神经元学习的问题，其中新工具需要在数据分布重尾时显示梯度下降的收敛。

在线性回归中，我们希望根据少量样本估算超过$ d $维的输入点和实价响应的最佳最小二乘预测。根据标准随机设计分析，其中绘制样品i.i.d。从输入分布中，该样品的最小二乘解决方案可以看作是最佳的自然估计器。不幸的是，该估计器几乎总是产生来自输入点的随机性的不良偏置，这在模型平均中是一个重要的瓶颈。在本文中，我们表明可以绘制非i.i.d。输入点的样本，无论响应模型如何，最小二乘解决方案都是最佳的无偏估计器。此外，可以通过增强先前绘制的I.I.D。可以有效地生产该样本。带有额外的$ d $点的样品，根据点由点跨越的平方量重新缩放的输入分布构建的一定确定点过程，共同绘制。在此激励的基础上，我们开发了一个理论框架来研究体积响应的采样，并在此过程中证明了许多新的矩阵期望身份。我们使用它们来表明，对于任何输入分布和$ \ epsilon> 0 $，有一个随机设计由$ o（d \ log d+ d+ d+ d/\ epsilon）$点，从中可以从中构造出无偏见的估计器，其预期的是正方形损耗在整个发行版中，$ 1+\ epsilon $ times最佳损失。我们提供有效的算法来在许多实际设置中生成这种无偏估计量，并在实验中支持我们的主张。

我们提出了对学度校正随机块模型（DCSBM）的合适性测试。该测试基于调整后的卡方统计量，用于测量$ n $多项式分布的组之间的平等性，该分布具有$ d_1，\ dots，d_n $观测值。在网络模型的背景下，多项式的数量（$ n $）的数量比观测值数量（$ d_i $）快得多，与节点$ i $的度相对应，因此设置偏离了经典的渐近学。我们表明，只要$ \ {d_i \} $的谐波平均值生长到无穷大，就可以使统计量在NULL下分配。顺序应用时，该测试也可以用于确定社区数量。该测试在邻接矩阵的压缩版本上进行操作，因此在学位上有条件，因此对大型稀疏网络具有高度可扩展性。我们结合了一个新颖的想法，即在测试$ K $社区时根据$（k+1）$ - 社区分配来压缩行。这种方法在不牺牲计算效率的情况下增加了顺序应用中的力量，我们证明了它在恢复社区数量方面的一致性。由于测试统计量不依赖于特定的替代方案，因此其效用超出了顺序测试，可用于同时测试DCSBM家族以外的各种替代方案。特别是，我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。

我们研究了$ \ Mathcal {r} $的结构和统计属性 - 规范最小化由特定目标函数标记的数据集的内侧插值。$ \ MATHCAL {R} $ - 标准是两层神经网络的电感偏差的基础，最近引入了捕获网络权重大小的功能效果，与网络宽度无关。我们发现，即使有适合数据的脊函数，这些插值也是本质上的多元功能，而且$ \ Mathcal {r} $ - 规范归纳偏见不足以实现某些学习问题的统计上最佳概括。总的来说，这些结果为与实际神经网络训练有关的感应偏见提供了新的启示。