当前深度学习方法的许多应用程序的警告是需要大规模数据。Kolmogorov复杂性结果提出的一种改进是将最小描述长度原理与计算通用模型应用。我们研究了这种方法原则上可以带来的样品效率的潜在提高。我们使用多项式时间图灵机代表计算上的通用模型和布尔电路，以表示作用于有限精确数字的人工神经网络（ANN）。我们的分析解散了我们的问题与计算复杂性结果之间的直接联系。我们在使用图灵机而不是ANN应用的MDL之间的样品效率上提供了下限和上限。我们的界限取决于要学习的布尔函数的输入的位尺寸。此外，我们重点介绍了电路复杂性的经典开放问题与这些问题的紧密关系之间的密切关系。

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

我们证明，可以通过恒定的深度统一阈值电路模拟输入长度中具有对数精度的变压器神经网络（以及使用输入长度中的线性空间计算的FeedForward子网络）。因此，此类变压器仅在$ \ mathsf {tc}^0 $中识别形式语言，这是由常数深度，多大小阈值电路定义的语言类。这证明了NLP中的实际主张与计算复杂性理论中的理论猜想之间的联系：“注意就是您需要的一切”（Vaswani等，2017），即，只有在所有有效地计算的情况下，变形金刚都能够进行所有有效的计算可以使用日志空间来解决问题，即$ \ mathsf l = \ mathsf p $。我们还构建了一个可以在任何输入上评估任何恒定深度阈值电路的变压器，证明变形金刚可以遵循$ \ Mathsf {tc}^0 $中表示的说明。

本文研究了人工神经网络（NNS）与整流线性单元的表现力。为了将它们作为实际计算的模型，我们介绍了最大仿射算术计划的概念，并显示了它们与NNS之间的等效性有关自然复杂度措施。然后我们使用此结果表明，使用多项式NNS可以解决两个基本组合优化问题，这相当于非常特殊的强多项式时间算法。首先，我们显示，对于带有N $节点的任何无向图形，有一个NN大小$ \ Mathcal {O}（n ^ 3）$，它将边缘权重用为输入，计算最小生成树的值图表。其次，我们显示，对于任何带有$ N $节点和$ M $弧的任何定向图，都有一个尺寸$ \ mathcal {o}（m ^ 2n ^ 2）$，它将电弧容量作为输入和计算最大流量。这些结果尤其尤其暗示，相应的参数优化问题的解决方案可以在多项式空间中编码所有边缘权重或电弧容量的方法，并在多项式时间中进行评估，并且由NN提供这种编码。

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

我们连接学习算法和算法自动化证明搜索在命题证明系统中：每一种充分强大，表现良好的命题证明系统$ P $，我们证明以下陈述相当，1.可提供学习：$ P $证明p -size电路通过统一分布的子尺寸尺寸电路与成员资格查询进行了学习。 2.可提供自动性：$ P $证明$ P $可通过非均匀电路在表达P尺寸电路下限的命题公式上自动。在这里，如果I.-III，则$ P $足够强大和表现良好。持有：I. $ P $ P-SIMULATES JE \ v {R} \'ABEK的系统$ WF $（通过调节弱鸽子原则加强扩展弗雷格系统$ EF $）; II。 $ P $满足标准证明系统的一些基本属性，P-SIMUTED $ WF $; III。 $ P $可有效地证明一些布尔函数$ H $ H $ H $难以平均为子增长尺寸电路。例如，如果III。保持$ p = wf $，然后项目1和2等同于$ p = wf $。如果在Ne \ Cop Cone $的函数$ H \ IN，这是平均尺寸为2 ^ {n / 4} $的电路，对于每个足够大的$ n $，那么有一个明确的命题证明系统$ p $满意的属性I.-III。，即物品1和2的等价，以$ p $持有。

Characterizing the implicit structure of the computation within neural networks is a foundational problem in the area of deep learning interpretability. Can their inner decision process be captured symbolically in some familiar logic? We show that any transformer neural network can be translated into an equivalent fixed-size first-order logic formula which may also use majority quantifiers. The idea is to simulate transformers with highly uniform threshold circuits and leverage known theoretical connections between circuits and logic. Our findings also reveal the surprising fact that the entire transformer computation can be reduced merely to the division of two (large) integers. While our results are most pertinent for transformers, they apply equally to a broader class of neural network architectures, namely those with a fixed-depth uniform computation graph made up of standard neural net components, which includes feedforward and convolutional networks.

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the 'combine' function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. We present an improved simulation of the WL test on GNNs with \emph{exponentially} lower complexity. In particular, the neural network implementing the combine function in each node has only a polylogarithmic number of parameters in $n$, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.

我们研究神经网络表达能力的基本限制。给定两组$ f $，$ g $的实值函数，我们首先证明了$ f $中的功能的一般下限，可以在$ l^p（\ mu）$ norm中通过$ g中的功能近似$，对于任何$ p \ geq 1 $和任何概率度量$ \ mu $。下限取决于$ f $的包装数，$ f $的范围以及$ g $的脂肪震动尺寸。然后，我们实例化了$ g $对应于分段的馈电神经网络的情况，并详细描述了两组$ f $：h {\“ o} lder balls和多变量单调函数。除了匹配（已知或新的）上限与日志因素外，我们的下限还阐明了$ l^p $ Norm或SUP Norm中近似之间的相似性或差异，解决了Devore等人的开放问题（2021年））。我们的证明策略与SUP Norm案例不同，并使用了Mendelson（2002）的关键概率结果。

现代量子机学习（QML）方法涉及在训练数据集上进行各种优化参数化量子电路，并随后对测试数据集（即，泛化）进行预测。在这项工作中，我们在培训数量为N $培训数据点后，我们在QML中对QML的普遍表现进行了全面的研究。我们表明，Quantum机器学习模型的泛化误差与$ T $培训门的尺寸在$ \ sqrt {t / n} $上缩放。当只有$ k \ ll t $ gates在优化过程中经历了大量变化时，我们证明了泛化误差改善了$ \ sqrt {k / n} $。我们的结果意味着将Unitaries编制到通常使用指数训练数据的量子计算行业的多项式栅极数量，这是一项通常使用指数尺寸训练数据的大量应用程序。我们还表明，使用量子卷积神经网络的相位过渡的量子状态的分类只需要一个非常小的训练数据集。其他潜在应用包括学习量子误差校正代码或量子动态模拟。我们的工作将新的希望注入QML领域，因为较少的培训数据保证了良好的概括。

我们有助于更好地理解由具有Relu激活和给定架构的神经网络表示的功能。使用来自混合整数优化，多面体理论和热带几何的技术，我们为普遍近似定理提供了数学逆向，这表明单个隐藏层足以用于学习任务。特别是，我们调查完全可增值功能是否完全可以通过添加更多层（没有限制大小）来严格增加。由于它为神经假设类别代表的函数类提供给算法和统计方面，这个问题对算法和统计方面具有潜在的影响。然而，据我们所知，这个问题尚未在神经网络文学中调查。我们还在这些神经假设类别中代表功能所需的神经网络的大小上存在上限。

单调功能和数据集在各种应用中都会出现。我们研究单调数据集的插值问题：输入是带有$ n $点的单调数据集，目标是找到一个大小和深度有效的单调神经网络，具有非负参数和阈值单元，可以插入数据放。我们表明，单调数据集无法通过深度$ 2 $的单调网络插值。另一方面，我们证明，对于每个单调数据集，在$ \ mathbb {r}^d $中$ n $点，存在一个插值的单调网络，该网络的深度为$ 4 $ $ 4 $和size $ o（nd）$。我们的插值结果意味着，每个单调功能超过$ [0,1]^d $可以通过DEPTH-4单调网络任意地近似，从而改善了先前最著名的深度构建$ d+1 $。最后，基于布尔电路复杂性的结果，我们表明，当近似单调函数时，具有正参数的电感偏差会导致神经元数量的超顺式爆炸。

给定真实的假设类$ \ 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建立第一个非参数私人学习保证。我们的技术涉及一种新颖的过滤过程，以输出非参数函数类的稳定假设。

令$ \ mathscr {f} _ {n，d} $为所有函数的类$ f：\ { - { - 1,1 \}^n \ to [-1,1] $ to $ n $ dipermensional discement to [-1,1] $超级立方体最多$ d $。在本文的第一部分中，我们证明了学习$ \ mathscr {f} _ {n，d} $的任何（确定性或随机）算法带有$ l_2 $ -accuracy $ \ varepsilon $至少需要$ \ omega（ （1- \ sqrt {\ varepsilon}）2^d \ log n）$ queries for tomy $ n $，从而将锋利性确定为$ n \ to \ fty \ fty \ infty $ y iffty $，eSkenazis and Ivanisvili（2021）（2021） 。为此，我们表明$ l_2 $ - 包装数字$ \ Mathsf {m}（\ Mathscr {f} _ {n，d}，\ | \ cdot \ | _ {l_2}，\ varepsilon）$概念类$ \ mathscr {f} _ {n，d} $满足双面估计$$ c（1- \ varepsilon）2^d \ log n \ log n \ leq \ log \ log \ mathsf {m mathsf {m}（\ mathscr） } _ {n，d}，\ | \ cdot \ | _ {l_2}，\ varepsilon）\ leq \ frac {2^{cd} \ log n} {\ varepsilon^4} $ n $ ，其中$ c，c> 0 $是通用常数。在本文的第二部分中，我们提出了一个对数上限，以实现有界近似多项式类别的随机查询复杂性，其傅立叶光谱集中在很少的子集上。作为应用程序，我们证明了学习给定程度的近似作者所需的随机查询数量的新估计值，具有快速衰减的傅立叶尾巴和给定尺寸的恒定深度电路的功能。最后，我们获得了学习多项式类$ \ mathscr {f} _ {n，d} $所需的查询数量的界限，而在查询和随机示例模型中没有错误。

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.

图形神经网络（GNNS）是关于图形机器学习问题的深度学习架构。最近已经表明，GNN的富有效力可以精确地由组合Weisfeiler-Leman算法和有限可变计数逻辑来表征。该对应关系甚至导致了对应于更高维度的WL算法的新的高阶GNN。本文的目的是解释GNN的这些描述性特征。

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.

我们研究了图形表示学习的量子电路，并提出了等级的量子图电路（EQGCS），作为一类参数化量子电路，具有强大的关系感应偏压，用于学习图形结构数据。概念上，EQGCS作为量子图表表示学习的统一框架，允许我们定义几个有趣的子类，其中包含了现有的提案。就代表性权力而言，我们证明了感兴趣的子类是界限图域中的函数的普遍近似器，并提供实验证据。我们对量子图机学习方法的理论透视开启了许多方向以进行进一步的工作，可能导致具有超出古典方法的能力的模型。

我们研究了三个看似不同的组合结构之间的联系 - 在统计和概率理论中的“统一”括号，“在线和分布式学习理论”和“组合MacBeath地区”，或者在离散和计算几何中的MNET。我们表明这三个概念是单一组合物业的表现，可以在沿着VAPNIK-Chervonenkis型理论的统一框架中表达的统一收敛性。这些新连接有助于我们带来来自离散和计算几何的工具，以证明这些对象的改进界限。我们改进的界限有助于获得半个空间的分布式学习的最佳算法，一种改进的分布式凸起脱节问题，以及对大类半代数阈值函数的平滑对手的在线算法的改进的后悔界限。

本文识别数据分布的结构属性，使得深神经网络能够分层学习。我们定义了在布尔超立方体上的功能的“楼梯”属性，该功能在沿着增加链的低阶傅里叶系数可达高阶傅里叶系数。我们证明了满足该属性的功能可以在多项式时间中使用常规神经网络上的分层随机坐标血液中学到多项式时间 - 一类网络架构和具有同质性属性的初始化。我们的分析表明，对于这种阶梯功能和神经网络，基于梯度的算法通过贪婪地组合沿网络深度的较低级别特征来了解高级功能。我们进一步回复了我们的理论结果，实验显示楼梯功能也是由具有随机梯度下降的更多标准Reset架构进行学习的。理论和实验结果都支持阶梯属性在理解基于梯度的学习的能力的情况下，与可以模仿最近所示的任何SQ或PAC算法的一般多项式网络相反，阶梯属性在理解普通网络上的能力相反。