在本文中，我们在具有线性阈值激活功能的神经网络上提出了新的结果。我们精确地表征了这种神经网络可表示的功能，并且显示2个隐藏层是必要的并且足以表示类中可表示的任何功能。鉴于使用其他流行的激活功能的神经网络的最近精确的可比性调查，这是一个令人惊讶的结果，这些功能使用其他流行的激活功能，如整流的线性单元（Relu）。我们还给出了代表类中任意函数所需的神经网络的大小的精确界限。最后，我们设计了一种算法来解决具有固定架构的这些神经网络的全球最优性的经验风险最小化（ERM）问题。如果输入维度和网络架构的大小被认为是固定常数，则算法的运行时间是数据样本大小的多项式。该算法的意义上是独一无二的，即它适用于任何数量的层数，而先前的多项式时间全局最佳算法仅适用于非常受限制的架构类。

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

我们研究神经网络表达能力的基本限制。给定两组$ 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）的关键概率结果。

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

了解训练具有整流线性单元（RELUS）的训练简单神经网络的计算复杂性最近是一项深入研究的主题。缩小差距和文献的补充结果，我们提供了有关训练两层relu网络的参数复杂性相对于各种损失函数的几个结果。经过对其他参数的简要讨论，我们着重分析培训数据对计算复杂性的尺寸$ d $的影响。我们根据w [1]的参数$ d $提供运行时间的下限，并证明已知的蛮力策略基本上是最佳的（假设指数时间假设）。与以前的工作相比，我们的结果适用于广泛（ER）范围的损失功能，包括[0，\ infty] $中的所有$ p \ for $ \ ell^p $ -loss。特别是，我们将已知的多项式时间算法扩展到常数$ d $，并将凸损失函数扩展到更一般的损耗函数，在这些情况下，我们的运行时间下限也匹配。

我们介绍了可以由具有Maxout单位的人造馈电神经网络表示的功能线性区域的数量。排名kaxout单元是一个函数，计算$ k $线性函数的最大值。对于具有单层Maxout单元的网络，线性区域对应于Minkowski多型的上顶点。我们根据热带超曲面的交点或部分Minkowski总和的上面数，以及任何输入维度的区域数，任何单位数量，任何等级，任何等级，任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，以及任何等级，在有和没有偏见的情况下。基于这些结果，我们还为具有多层的网络获得了渐近的上限。

We consider the algorithmic problem of finding the optimal weights and biases for a two-layer fully connected neural network to fit a given set of data points. This problem is known as empirical risk minimization in the machine learning community. We show that the problem is $\exists\mathbb{R}$-complete. This complexity class can be defined as the set of algorithmic problems that are polynomial-time equivalent to finding real roots of a polynomial with integer coefficients. Furthermore, we show that arbitrary algebraic numbers are required as weights to be able to train some instances to optimality, even if all data points are rational. Our results hold even if the following restrictions are all added simultaneously. $\bullet$ There are exactly two output neurons. $\bullet$ There are exactly two input neurons. $\bullet$ The data has only 13 different labels. $\bullet$ The number of hidden neurons is a constant fraction of the number of data points. $\bullet$ The target training error is zero. $\bullet$ The ReLU activation function is used. This shows that even very simple networks are difficult to train. The result explains why typical methods for $\mathsf{NP}$-complete problems, like mixed-integer programming or SAT-solving, cannot train neural networks to global optimality, unless $\mathsf{NP}=\exists\mathbb{R}$. We strengthen a recent result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021].

由于其在输入空间子集上的功能的知识，因此可以根据情况，诅咒或祝福来恢复神经网络的参数权重和偏差的可能性。一方面，恢复参数允许更好的对抗攻击，并且还可以从用于构造网络的数据集中披露敏感信息。另一方面，如果可以恢复网络的参数，它可以保证用户可以解释潜在空间中的特征。它还提供基础，以获得对网络性能的正式保障。因此，表征可以识别其参数的网络以及其参数不能的网络是很重要的。在本文中，我们在深度全连接的前馈recu网络上提供了一组条件，在该馈电中，网络的参数是唯一识别的模型置换和正重型 - 从其实现输入空间的子集。

使用神经网络学习依赖于可代表功能的复杂性，但更重要的是，典型参数的特定分配与不同复杂度的功能。将激活区域的数量作为复杂性度量，最近的作品表明，深度释放网络的实际复杂性往往远远远非理论最大值。在这项工作中，我们表明这种现象也发生在具有颤扬（多参数）激活功能的网络中，并且在考虑分类任务中的决策边界时。我们还表明参数空间具有多维全维区域，具有广泛不同的复杂性，并在预期的复杂性上获得非竞争下限。最后，我们调查了不同的参数初始化程序，并表明他们可以提高培训的收敛速度。

众所周知，具有重新激活函数的完全连接的前馈神经网络可以表示的参数化函数家族恰好是一类有限的分段线性函数。鲜为人知的是，对于Relu神经网络的每个固定架构，参数空间都允许对称的正维空间，因此，在任何给定参数附近的局部功能维度都低于参数维度。在这项工作中，我们仔细地定义了功能维度的概念，表明它在Relu神经网络函数的参数空间中是不均匀的，并继续进行[14]和[5]中的调查 - 何时在功能维度实现其理论时最大。我们还研究了从参数空间到功能空间的实现图的商空间和纤维，提供了断开连接的纤维的示例，功能尺寸为非恒定剂的纤维以及对称组在其上进行非转换的纤维。

这项调查的目的是介绍对深神经网络的近似特性的解释性回顾。具体而言，我们旨在了解深神经网络如何以及为什么要优于其他经典线性和非线性近似方法。这项调查包括三章。在第1章中，我们回顾了深层网络及其组成非线性结构的关键思想和概念。我们通过在解决回归和分类问题时将其作为优化问题来形式化神经网络问题。我们简要讨论用于解决优化问题的随机梯度下降算法以及用于解决优化问题的后传播公式，并解决了与神经网络性能相关的一些问题，包括选择激活功能，成本功能，过度适应问题和正则化。在第2章中，我们将重点转移到神经网络的近似理论上。我们首先介绍多项式近似中的密度概念，尤其是研究实现连续函数的Stone-WeierStrass定理。然后，在线性近似的框架内，我们回顾了馈电网络的密度和收敛速率的一些经典结果，然后在近似Sobolev函数中进行有关深网络复杂性的最新发展。在第3章中，利用非线性近似理论，我们进一步详细介绍了深度和近似网络与其他经典非线性近似方法相比的近似优势。

We study the expressibility and learnability of convex optimization solution functions and their multi-layer architectural extension. The main results are: \emph{(1)} the class of solution functions of linear programming (LP) and quadratic programming (QP) is a universal approximant for the $C^k$ smooth model class or some restricted Sobolev space, and we characterize the rate-distortion, \emph{(2)} the approximation power is investigated through a viewpoint of regression error, where information about the target function is provided in terms of data observations, \emph{(3)} compositionality in the form of a deep architecture with optimization as a layer is shown to reconstruct some basic functions used in numerical analysis without error, which implies that \emph{(4)} a substantial reduction in rate-distortion can be achieved with a universal network architecture, and \emph{(5)} we discuss the statistical bounds of empirical covering numbers for LP/QP, as well as a generic optimization problem (possibly nonconvex) by exploiting tame geometry. Our results provide the \emph{first rigorous analysis of the approximation and learning-theoretic properties of solution functions} with implications for algorithmic design and performance guarantees.

众所周知，现代神经网络容易受到对抗例子的影响。为了减轻这个问题，已经提出了一系列强大的学习算法。但是，尽管通过某些方法可以通过某些方法接近稳定的训练误差，但所有现有的算法都会导致较高的鲁棒概括误差。在本文中，我们从深层神经网络的表达能力的角度提供了对这种令人困惑的现象的理论理解。具体而言，对于二进制分类数据，我们表明，对于Relu网络，虽然轻度的过度参数足以满足较高的鲁棒训练精度，但存在持续的稳健概括差距，除非神经网络的大小是指数的，却是指数的。数据维度$ d $。即使数据是线性可分离的，这意味着要实现低清洁概括错误很容易，我们仍然可以证明$ \ exp（{\ omega}（d））$下限可用于鲁棒概括。通常，只要它们的VC维度最多是参数数量，我们的指数下限也适用于各种神经网络家族和其他功能类别。此外，我们为网络大小建立了$ \ exp（{\ mathcal {o}}（k））$的改进的上限，当数据放在具有内在尺寸$ k $的歧管上时，以实现低鲁棒的概括错误（$） k \ ll d $）。尽管如此，我们也有一个下限，相对于$ k $成倍增长 - 维度的诅咒是不可避免的。通过证明网络大小之间的指数分离以实现较低的鲁棒训练和泛化错误，我们的结果表明，鲁棒概括的硬度可能源于实用模型的表现力。

让F：R ^ N - > R是前馈RELU神经网络。众所周知，对于任何选择参数，F是连续和分段（仿射）线性的。我们为有系统调查提供了一些基础，用于系统的架构如何影响其可能的决策区域的几何和拓扑以进行二进制分类任务。在差分拓扑中顺利函数的经典进展之后，我们首先定义通用，横向relu神经网络的概念，并显示几乎所有的Relu网络都是通用的和横向的。然后，我们在F的域中定义了一个部分取向的线性1-复合物，并识别该复合物的属性，从而产生妨碍决策区域的有界连接分量的障碍物。我们使用该阻塞来证明具有单个隐藏的尺寸层（N + 1）的通用横向Relu网络F：R ^ N - > R的决策区域可以不具有多于一个有界连接的组件。

本文开发了简单的前馈神经网络，实现了所有连续功能的通用近似性，具有固定的有限数量的神经元。这些神经网络很简单，因为它们的设计具有简单且可增加的连续激活功能$ \ Sigma $利用三角波函数和软片功能。我们证明了$ \ Sigma $ -Activated网络，宽度为36d $ 36d（2d + 1）$和11 $ 11 $可以在任意小错误中估计$ d $ -dimensioanl超级函数上的任何连续功能。因此，对于监督学习及其相关的回归问题，这些网络产生的假设空间，尺寸不小于36d（2d + 1）\ times 11 $的持续功能的空间。此外，由图像和信号分类引起的分类函数在$ \ sigma $ -activated网络生成的假设空间中，宽度为36d（2d + 1）$和12 $ 12 $，当存在$ \的成对不相交的界限子集时mathbb {r} ^ d $，使得同一类的样本位于同一子集中。

We study the complexity of functions computable by deep feedforward neural networks with piecewise linear activations in terms of the symmetries and the number of linear regions that they have. Deep networks are able to sequentially map portions of each layer's input-space to the same output. In this way, deep models compute functions that react equally to complicated patterns of different inputs. The compositional structure of these functions enables them to re-use pieces of computation exponentially often in terms of the network's depth. This paper investigates the complexity of such compositional maps and contributes new theoretical results regarding the advantage of depth for neural networks with piecewise linear activation functions. In particular, our analysis is not specific to a single family of models, and as an example, we employ it for rectifier and maxout networks. We improve complexity bounds from pre-existing work and investigate the behavior of units in higher layers.

样本是否足够丰富，至少在本地确定神经网络的参数？为了回答这个问题，我们通过固定其某些权重的值来介绍给定深层神经网络的新局部参数化。这使我们能够定义本地提升操作员，其倒置是高维空间的平滑歧管的图表。Deep Relu神经网络实现的函数由依赖样本的线性操作员组成局部提升。我们从这种方便的表示中得出了局部可识别性的几何必要条件。查看切线空间，几何条件提供了：1/可识别性的尖锐而可测试的必要条件以及2/可识别局部可识别性的尖锐且可测试的足够条件。可以使用反向传播和矩阵等级计算对条件的有效性进行数值测试。

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

我们研究了深层神经网络的表达能力，以在扩张的转移不变空间中近似功能，这些空间被广泛用于信号处理，图像处理，通信等。相对于神经网络的宽度和深度估算了近似误差界限。网络构建基于深神经网络的位提取和数据拟合能力。作为我们主要结果的应用，获得了经典函数空间（例如Sobolev空间和BESOV空间）的近似速率。我们还给出了$ l^p（1 \ le p \ le \ infty）$近似误差的下限，这表明我们的神经网络的构建是渐近的最佳选择，即最大程度地达到对数因素。

本文通过引入几何深度学习（GDL）框架来构建通用馈电型型模型与可区分的流形几何形状兼容的通用馈电型模型，从而解决了对非欧国人数据进行处理的需求。我们表明，我们的GDL模型可以在受控最大直径的紧凑型组上均匀地近似任何连续目标函数。我们在近似GDL模型的深度上获得了最大直径和上限的曲率依赖性下限。相反，我们发现任何两个非分类紧凑型歧管之间始终都有连续的函数，任何“局部定义”的GDL模型都不能均匀地近似。我们的最后一个主要结果确定了数据依赖性条件，确保实施我们近似的GDL模型破坏了“维度的诅咒”。我们发现，任何“现实世界”（即有限）数据集始终满足我们的状况，相反，如果目标函数平滑，则任何数据集都满足我们的要求。作为应用，我们确认了以下GDL模型的通用近似功能：Ganea等。 （2018）的双波利馈电网络，实施Krishnan等人的体系结构。 （2015年）的深卡尔曼 - 滤波器和深度玛克斯分类器。我们构建了：Meyer等人的SPD-Matrix回归剂的通用扩展/变体。 （2011）和Fletcher（2003）的Procrustean回归剂。在欧几里得的环境中，我们的结果暗示了Kidger和Lyons（2020）的近似定理和Yarotsky和Zhevnerchuk（2019）无估计近似率的数据依赖性版本的定量版本。