了解深度神经网络成功背后的基本机制是现代机器学习文学中的关键挑战之一。尽管尝试了很多，但尚未开发扎实的理论分析。在本文中，我们开发了一种新颖的统一框架，以通过凸优化镜头揭示隐藏的正则化机制。首先表明，具有重量衰减正则化的多个三层relu子网的训练可以等同地作为较高尺寸空间中的凸优化问题来等效地投射，其中稀疏通过组$ \ ell_1 $ -norm正常化强制实施。因此，Relu网络可以被解释为高维特征选择方法。更重要的是，我们证明，当网络宽度固定时，可以通过标准凸优化求解器全局优化等同的凸起问题通过具有多项式复杂度的标准凸优化求解器。最后，我们通过涉及合成和真实数据集的实验来数值验证我们的理论结果。

我们描述了两层向量输出relu神经网络训练问题的凸半无限频体。该半无限的双重承认有限尺寸表示，但其支持在难以表征的凸起集中。特别是，我们证明非凸神经网络训练问题相当于有限维凸形成形程序。我们的工作是第一个确定全球神经网络的全球最佳与连阳性方案之间的强大联系。因此，我们展示了神经网络如何通过半非环境矩阵分解来隐化地揭示求解连接成型程序，并从该配方中汲取关键见解。我们描述了第一算法，用于可证明导航的全局最小值的导航神经网络训练问题，这些算法是固定数据等级的样本数量的多项式，但维度指数是指数。然而，在卷积架构的情况下，计算复杂性在所有其他参数中仅在滤波器大小和多项式中是指数的。我们描述了我们能够完全找到这种神经网络训练问题的全球最佳的环境，并提供了软阈值的SVD，并提供了一种成交量松弛，保证确切地用于某些问题，并与随机的解决方案相对应实践中的梯度下降。

人工神经网络（ANN）训练景观的非凸起带来了固有的优化困难。虽然传统的背传播随机梯度下降（SGD）算法及其变体在某些情况下是有效的，但它们可以陷入杂散的局部最小值，并且对初始化和普通公共表敏感。最近的工作表明，随着Relu激活的ANN的培训可以重新重整为凸面计划，使希望能够全局优化可解释的ANN。然而，天真地解决凸训练制剂具有指数复杂性，甚至近似启发式需要立方时间。在这项工作中，我们描述了这种近似的质量，并开发了两个有效的算法，这些算法通过全球收敛保证培训。第一算法基于乘法器（ADMM）的交替方向方法。它解决了精确的凸形配方和近似对应物。实现线性全局收敛，并且初始几次迭代通常会产生具有高预测精度的解决方案。求解近似配方时，每次迭代时间复杂度是二次的。基于“采样凸面”理论的第二种算法更简单地实现。它解决了不受约束的凸形制剂，并收敛到大约全球最佳的分类器。当考虑对抗性培训时，ANN训练景观的非凸起加剧了。我们将稳健的凸优化理论应用于凸训练，开发凸起的凸起制剂，培训Anns对抗对抗投入。我们的分析明确地关注一个隐藏层完全连接的ANN，但可以扩展到更复杂的体系结构。

训练深神网络是一个众所周知的高度非凸问题。在最近的作品中，显示出具有RELU激活的正则化两层神经网络没有二元性差距，这可以通过凸面程序进行全局优化。对于具有向量输出的多层线性网络，我们提出了凸双问题，并证明对偶性差距对于深度三和更深的网络而言并非零。但是，通过将深层网络修改为更强大的并行体系结构，我们表明二元性差距完全为零。因此，强大的凸面双重性具有，因此存在等效的凸面程序，使培训深层网络达到全球最优性。我们还证明，参数中的重量衰减正则化明确地通过封闭形式表达式鼓励低级溶液。对于三层非平行relu网络，我们表明对级别1数据矩阵的强双重性具有强度，但是，对白色数据矩阵的二元性差距不是零。同样，通过将神经网络体系结构转换为相应的并行版本，二元性差距消失了。

我们开发了快速算法和可靠软件，以凸出具有Relu激活功能的两层神经网络的凸优化。我们的工作利用了标准的重量罚款训练问题作为一组组-YELL_1 $调查的数据本地模型的凸重新印度，其中局部由多面体锥体约束强制执行。在零规范化的特殊情况下，我们表明此问题完全等同于凸“ Gated Relu”网络的不受约束的优化。对于非零正则化的问题，我们表明凸面式relu模型获得了RELU训练问题的数据依赖性近似范围。为了优化凸的重新制定，我们开发了一种加速的近端梯度方法和实用的增强拉格朗日求解器。我们表明，这些方法比针对非凸问题（例如SGD）和超越商业内部点求解器的标准训练启发式方法要快。在实验上，我们验证了我们的理论结果，探索组-ELL_1 $正则化路径，并对神经网络进行比例凸的优化，以在MNIST和CIFAR-10上进行图像分类。

我们提供了通过线性激活的多渠道卷积神经网络中的$ \ ell_2 $标准来最大程度地减少$ \ ell_2 $标准而产生的功能空间表征，并经验测试了我们对使用梯度下降训练的Relu网络的假设。我们将功能空间中的诱导正规化程序定义为实现函数所需的网络权重规范的最小$ \ ell_2 $。对于具有$ C $输出频道和内核尺寸$ K $的两个层线性卷积网络，我们显示以下内容：（a）如果网络的输入是单个渠道，则任何$ k $的诱导正规器都与数字无关输出频道$ c $。此外，我们得出正常化程序是由半决赛程序（SDP）给出的规范。 （b）相比之下，对于多通道输入，仅实现所有矩阵值值线性函数而需要多个输出通道，因此归纳偏置确实取决于$ c $。但是，对于足够大的$ c $，诱导的正规化程序再次由独立于$ c $的SDP给出。特别是，$ k = 1 $和$ k = d $（输入维度）的诱导正规器以封闭形式作为核标准和$ \ ell_ {2,1} $ group-sparse Norm，线性预测指标的傅立叶系数。我们通过对MNIST和CIFAR-10数据集的实验来研究理论结果对从线性和RELU网络上梯度下降的隐式正则化的更广泛的适用性。

在本文中，我们研究了学习最适合培训数据集的浅层人工神经网络的问题。我们在过度参数化的制度中研究了这个问题，在该制度中，观测值的数量少于模型中的参数数量。我们表明，通过二次激活，训练的优化景观这种浅神经网络具有某些有利的特征，可以使用各种局部搜索启发式方法有效地找到全球最佳模型。该结果适用于输入/输出对的任意培训数据。对于可区分的激活函数，我们还表明，适当初始化的梯度下降以线性速率收敛到全球最佳模型。该结果着重于选择输入的可实现模型。根据高斯分布和标签是根据种植的重量系数生成的。

机器学习在解决无线干扰管理问题方面取得了成功。已经培训了不同种类的深神经网络（DNN），以完成功率控制，波束成形和准入控制等关键任务。基于DNNS的干扰管理模型有两个流行的培训范式：监督学习（即，由优化算法产生的拟合标签）和无监督的学习（即，直接优化一些系统性能测量）。虽然这两种范式都在实践中广泛应用，但由于对这些方法缺乏任何理论理解，但目前尚不清楚如何系统地理解和比较他们的性能。在这项工作中，我们开展理论研究，为这两个训练范例提供了一些深入的了解。首先，我们展示了一些令人惊讶的结果，即对于一些特殊的功率控制问题，无监督的学习可以表现比监督对手更糟糕，因为它更有可能陷入一些低质量的本地解决方案。然后，我们提供了一系列理论结果，以进一步了解两种方法的性质。一般来说，我们表明，当有高质量的标签可用时，监督学习不太可能陷入解决方案，而不是无监督的对应物。此外，我们开发了一种半监督的学习方法，可以妥善整合这两个训练范例，可以有效地利用有限数量的标签来找到高质量的解决方案。为了我们的知识，这些是第一种在基于学习的无线通信系统设计中了解不同培训方法的第一组理论结果。

We describe an algorithm that learns two-layer residual units using rectified linear unit (ReLU) activation: suppose the input $\mathbf{x}$ is from a distribution with support space $\mathbb{R}^d$ and the ground-truth generative model is a residual unit of this type, given by $\mathbf{y} = \boldsymbol{B}^\ast\left[\left(\boldsymbol{A}^\ast\mathbf{x}\right)^+ + \mathbf{x}\right]$, where ground-truth network parameters $\boldsymbol{A}^\ast \in \mathbb{R}^{d\times d}$ represent a full-rank matrix with nonnegative entries and $\boldsymbol{B}^\ast \in \mathbb{R}^{m\times d}$ is full-rank with $m \geq d$ and for $\boldsymbol{c} \in \mathbb{R}^d$, $[\boldsymbol{c}^{+}]_i = \max\{0, c_i\}$. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-truth network in terms of its parameters and nonlinearities. Following this objective landscape, learning residual units from finite samples can be formulated using convex optimization of a nonparametric function: for each layer, we first formulate the corresponding empirical risk minimization (ERM) as a positive semi-definite quadratic program (QP), then we show the solution space of the QP can be equivalently determined by a set of linear inequalities, which can then be efficiently solved by linear programming (LP). We further prove the strong statistical consistency of our algorithm, and demonstrate its robustness and sample efficiency through experimental results on synthetic data and a set of benchmark regression datasets.

神经塌陷是指表征类嵌入和分类器重量的几何形状的显着结构特性，当经过零训练误差以外的训练时，深网被发现。但是，这种表征仅适用于平衡数据。因此，我们在这里询问是否可以使阶级失衡不变。为此，我们采用了不受限制的功能模型（UFM），这是一种用于研究神经塌陷的最新理论模型，并引入了单纯形编码标签的插值（SELI）作为神经崩溃现象的不变特征。具体而言，我们证明了UFM的跨凝结损失和消失的正则化，无论阶级失衡如何，嵌入和分类器总是插入单纯形编码的标签矩阵，并且其单个几何形状都由同一标签矩阵矩阵矩阵的SVD因子确定。然后，我们对合成和真实数据集进行了广泛的实验，这些实验确认了与SELI几何形状的收敛。但是，我们警告说，融合会随着不平衡的增加而恶化。从理论上讲，我们通过表明与平衡的情况不同，当存在少数民族时，山脊规范化在调整几何形状中起着至关重要的作用。这定义了新的问题，并激发了对阶级失衡对一阶方法融合其渐近优先解决方案的速率的影响的进一步研究。

本文介绍了OptNet，该网络架构集成了优化问题（这里，专门以二次程序的形式），作为较大端到端可训练的深网络中的单个层。这些层在隐藏状态之间编码约束和复杂依赖性，传统的卷积和完全连接的层通常无法捕获。我们探索这种架构的基础：我们展示了如何使用敏感性分析，彼得优化和隐式差分的技术如何通过这些层和相对于层参数精确地区分;我们为这些层开发了一种高效的解算器，用于利用基于GPU的基于GPU的批处理在原始 - 双内部点法中解决，并且在求解的顶部几乎没有额外的成本提供了反向衰减梯度;我们突出了这些方法在几个问题中的应用。在一个值得注意的示例中，该方法学习仅在输入和输出游戏中播放Mini-sudoku（4x4），没有关于游戏规则的a-priori信息;这突出了OptNet比其他神经架构更好地学习硬限制的能力。

To rigorously certify the robustness of neural networks to adversarial perturbations, most state-of-the-art techniques rely on a triangle-shaped linear programming (LP) relaxation of the ReLU activation. While the LP relaxation is exact for a single neuron, recent results suggest that it faces an inherent "convex relaxation barrier" as additional activations are added, and as the attack budget is increased. In this paper, we propose a nonconvex relaxation for the ReLU relaxation, based on a low-rank restriction of a semidefinite programming (SDP) relaxation. We show that the nonconvex relaxation has a similar complexity to the LP relaxation, but enjoys improved tightness that is comparable to the much more expensive SDP relaxation. Despite nonconvexity, we prove that the verification problem satisfies constraint qualification, and therefore a Riemannian staircase approach is guaranteed to compute a near-globally optimal solution in polynomial time. Our experiments provide evidence that our nonconvex relaxation almost completely overcome the "convex relaxation barrier" faced by the LP relaxation.

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.

古典统计学习理论表示，拟合太多参数导致过度舒服和性能差。尽管大量参数矛盾，但是现代深度神经网络概括了这一发现，并构成了解释深度学习成功的主要未解决的问题。随机梯度下降（SGD）引起的隐式正规被认为是重要的，但其特定原则仍然是未知的。在这项工作中，我们研究了当地最小值周围的能量景观的局部几何学如何影响SGD的统计特性，具有高斯梯度噪声。我们争辩说，在合理的假设下，局部几何形状力强制SGD保持接近低维子空间，这会引起隐式正则化并导致深神经网络的泛化误差界定更严格的界限。为了获得神经网络的泛化误差界限，我们首先引入局部最小值周围的停滞迹象，并施加人口风险的局部基本凸性财产。在这些条件下，推导出SGD的下界，以保留在这些停滞套件中。如果发生停滞，我们会导出涉及权重矩阵的光谱规范的深神经网络的泛化误差的界限，但不是网络参数的数量。从技术上讲，我们的证据基于控制SGD中的参数值的变化以及基于局部最小值周围的合适邻域的熵迭代的参数值和局部均匀收敛。我们的工作试图通过统一收敛更好地连接非凸优化和泛化分析。

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激活的前馈神经网络的特定情况下存在两种替代配方，其具有recu激活：作为混合整数优化问题，作为具有互补限制的数学程序。对于后一种制剂，我们证明了在该问题的点处的有同性，对应于嵌入式制剂的实质性。这些配方中的每一个都可以用最先进的优化方法来解决，并且我们展示了如何为这些方法获得良好的初始可行解决方案。我们将三种实际应用的配方进行比较，在燃烧发动机的设计和控制中产生的三种实际应用，在对分类器网络的对抗攻击中产生的产生，以及在油井网中的最佳流动确定。

标签 - 不平衡和组敏感分类中的目标是优化相关的指标，例如平衡错误和相同的机会。经典方法，例如加权交叉熵，在训练深网络到训练（TPT）的终端阶段时，这是超越零训练误差的训练。这种观察发生了最近在促进少数群体更大边值的直观机制之后开发启发式替代品的动力。与之前的启发式相比，我们遵循原则性分析，说明不同的损失调整如何影响边距。首先，我们证明，对于在TPT中训练的所有线性分类器，有必要引入乘法，而不是添加性的Logit调整，以便对杂项边缘进行适当的变化。为了表明这一点，我们发现将乘法CE修改的连接到成本敏感的支持向量机。也许是违反，我们还发现，在培训开始时，相同的乘法权重实际上可以损害少数群体。因此，虽然在TPT中，添加剂调整无效，但我们表明它们可以通过对乘法重量的初始负效应进行抗衡来加速会聚。通过这些发现的动机，我们制定了矢量缩放（VS）丢失，即捕获现有技术作为特殊情况。此外，我们引入了对群体敏感分类的VS损失的自然延伸，从而以统一的方式处理两种常见类型的不平衡（标签/组）。重要的是，我们对最先进的数据集的实验与我们的理论见解完全一致，并确认了我们算法的卓越性能。最后，对于不平衡的高斯 - 混合数据，我们执行泛化分析，揭示平衡/标准错误和相同机会之间的权衡。

我们证明了由例如He等人提出的广泛使用的方法。（2015年）并使用梯度下降对最小二乘损失进行训练并不普遍。具体而言，我们描述了一大批一维数据生成分布，较高的概率下降只会发现优化景观的局部最小值不好，因为它无法将其偏离偏差远离其初始化，以零移动。。事实证明，在这些情况下，即使目标函数是非线性的，发现的网络也基本执行线性回归。我们进一步提供了数值证据，表明在实际情况下，对于某些多维分布而发生这种情况，并且随机梯度下降表现出相似的行为。我们还提供了有关初始化和优化器的选择如何影响这种行为的经验结果。

许多实际优化问题涉及不确定的参数，这些参数具有概率分布，可以使用上下文特征信息来估算。与首先估计不确定参数的分布然后基于估计优化目标的标准方法相反，我们提出了一个\ textIt {集成条件估计 - 优化}（ICEO）框架，该框架估计了随机参数的潜在条件分布同时考虑优化问题的结构。我们将随机参数的条件分布与上下文特征之间的关系直接建模，然后以与下游优化问题对齐的目标估算概率模型。我们表明，我们的ICEO方法在适度的规律性条件下渐近一致，并以概括范围的形式提供有限的性能保证。在计算上，使用ICEO方法执行估计是一种非凸面且通常是非差异的优化问题。我们提出了一种通用方法，用于近似从估计的条件分布到通过可区分函数的最佳决策的潜在非差异映射，这极大地改善了应用于非凸问题的基于梯度的算法的性能。我们还提供了半代理案例中的多项式优化解决方案方法。还进行了数值实验，以显示我们在不同情况下的方法的经验成功，包括数据样本和模型不匹配。

在本文中，我们研究了一类二聚体优化问题，也称为简单的双重优化，在其中，我们将光滑的目标函数最小化，而不是另一个凸的约束优化问题的最佳解决方案集。已经开发了几种解决此类问题的迭代方法。 las，它们的收敛保证并不令人满意，因为它们要么渐近，要么渐近，要么是收敛速度缓慢且最佳的。为了解决这个问题，在本文中，我们介绍了Frank-Wolfe（FW）方法的概括，以解决考虑的问题。我们方法的主要思想是通过切割平面在局部近似低级问题的解决方案集，然后运行FW型更新以减少上层目标。当上层目标是凸面时，我们表明我们的方法需要$ {\ mathcal {o}}（\ max \ {1/\ epsilon_f，1/\ epsilon_g \}）$迭代才能找到$ \ \ \ \ \ \ epsilon_f $ - 最佳目标目标和$ \ epsilon_g $ - 最佳目标目标。此外，当高级目标是非convex时，我们的方法需要$ {\ MATHCAL {o}}（\ max \ {1/\ epsilon_f^2,1/（\ epsilon_f \ epsilon_g}）查找$（\ epsilon_f，\ epsilon_g）$ - 最佳解决方案。我们进一步证明了在“较低级别问题的老年人错误约束假设”下的更强的融合保证。据我们所知，我们的方法实现了所考虑的二聚体问题的最著名的迭代复杂性。我们还向数值实验提出了数值实验。与最先进的方法相比，展示了我们方法的出色性能。