深度学习的成功以巨大的计算和能源成本，而训练大规模过度参数的神经网络的可伸缩性正成为AI进步的真正障碍。尽管传统反向传播通过梯度不错的传统反向传播的流行和低成本，但在理论和实践中，SGD在非凸面设置中具有高度的收敛速度。为了减轻这一成本，最近的工作提议采用替代性（牛顿型）培训方法，但收敛速度更快，尽管其每题成本更高。对于具有$ m = \ mathrm {poly}（n）$参数的典型神经网络，$ n $ datapoints in $ \ mathbb {r}^d $ of $ n $ datapoints的输入批次， Weinstein，ITCS'2021]需要$ \ sim mnd + n^3 $每次迭代。在本文中，我们提出了一种新颖的培训方法，它仅需要$ m^{1- \ alpha} n d + n^3 $摊销时间在同一过度叠加机制中，其中$ \ alpha \ in（0.01,1）$是某些固定常数。此方法依赖于神经网络的新替代视图，作为一组二进制搜索树，每个迭代都对应于修改树中节点的一小部分。我们认为，这种观点将在DNN的设计和分析中进一步应用。

我们考虑培训多层过参数化神经网络的问题，以最大限度地减少损失函数引起的经验风险。在过度参数化的典型设置中，网络宽度$ M $远大于数据维度$ D $和培训数量$ N $（$ m = \ mathrm {poly}（n，d）$），其中诱导禁止的大量矩阵$ w \ in \ mathbb {r} ^ {m \ times m} $每层。天真地，一个人必须支付$ O（m ^ 2）$时间读取权重矩阵并评估前向和后向计算中的神经网络功能。在这项工作中，我们展示了如何降低每个迭代的培训成本，具体而言，我们提出了一个仅在初始化阶段使用M ^ 2美元的框架，并且在$ M $的情况下实现了每次迭代的真正子种化成本。 ，$ m ^ {2- \ oomga（1）} $次迭代。为了获得此结果，我们利用各种技术，包括偏移的基于Relu的稀释器，懒惰的低级维护数据结构，快速矩阵矩阵乘法，张量的草图技术和预处理。

对抗训练是一种广泛使用的策略，可以使神经网络具有抵抗对抗性扰动的能力。对于宽度$ m $，$ n $输入培训数据的神经网络，在$ d $ dimension中，需要$ \ omega（MND）$每次培训迭代的时间费用来进行前进和向后计算。在本文中，我们分析了具有转移的Relu激活的两层神经网络上对抗训练程序的收敛保证，并表明每次迭代的每个输入数据都只能激活$ O（M）$神经元。此外，通过应用半空间报告数据结构，我们开发了一种用于对抗培训的算法，以$ O（m n d）$ $ O（m n d）$。

大规模监督学习中的共同挑战是如何利用新的增量数据到预先训练的模型，而无需从头开始重新培训模型。受到这个问题的激励，我们重新审视动态最小二乘回归（LSR）的规范问题，其中目标是通过增量训练数据学习线性模型。在此设置，数据和标签$（\ mathbf {a} ^ {（t）}，\ mathbf {b} ^ {（t）}）\ in \ mathbb {r} ^ {t \ times d} \ times \ MathBB {R} ^ T $以在线方式发展（$ t \ gg d $），目标是有效地将（近似）解决方案保持为$ \ min _ {\ mathbf {x} ^ {（t）}} \ | \ mathbf {a} ^ {（t）} \ mathbf {x} ^ {（t）} - \ mathbf {b} ^ {（t）} \ | \ | \ |在$中的所有$ t \。我们的主要结果是一种动态数据结构，它将任意小的恒定近似解，与摊销更新时间$ o（d ^ {1 + o（1）}）$，几乎匹配静态的运行时间（草图 - 基于）解决方案。相比之下，对于精确的（甚至$ 1 / \ mathrm {poly}（n）$ - 准确性）解决方案，我们在静态和动态设置之间显示了分离，即动态LSR需要$ \ω（d ^ {2- O（1）}）OMV猜想下的摊销更新时间（Henzinger等，STOC'15）。我们的数据结构在概念上简单，易于实施，并且在理论和实践中快速速度，通过对合成和现实世界数据集的实验进行了证实。

This work studies training one-hidden-layer overparameterized ReLU networks via gradient descent in the neural tangent kernel (NTK) regime, where, differently from the previous works, the networks' biases are trainable and are initialized to some constant rather than zero. The first set of results of this work characterize the convergence of the network's gradient descent dynamics. Surprisingly, it is shown that the network after sparsification can achieve as fast convergence as the original network. The contribution over previous work is that not only the bias is allowed to be updated by gradient descent under our setting but also a finer analysis is given such that the required width to ensure the network's closeness to its NTK is improved. Secondly, the networks' generalization bound after training is provided. A width-sparsity dependence is presented which yields sparsity-dependent localized Rademacher complexity and a generalization bound matching previous analysis (up to logarithmic factors). As a by-product, if the bias initialization is chosen to be zero, the width requirement improves the previous bound for the shallow networks' generalization. Lastly, since the generalization bound has dependence on the smallest eigenvalue of the limiting NTK and the bounds from previous works yield vacuous generalization, this work further studies the least eigenvalue of the limiting NTK. Surprisingly, while it is not shown that trainable biases are necessary, trainable bias helps to identify a nice data-dependent region where a much finer analysis of the NTK's smallest eigenvalue can be conducted, which leads to a much sharper lower bound than the previously known worst-case bound and, consequently, a non-vacuous generalization bound.

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.

我们提出了一种输入稀疏时间抽样算法，该算法可以近似于$ q $ - 折叠的列量张量产品$ q $矩阵的量子矩阵，使用几乎最佳的样品，从（q）$因素。此外，对于数据集的$ q $倍自量量的重要特殊情况，这是学位的功能矩阵-y $ q $ polyenmial kernel，我们方法运行时的领先术语与该方法的大小成正比输入数据集，并且不依赖$ Q $。以前的技术要么在其运行时产生Poly $（Q）$的放缓，要么以$ Q $的依赖性为代价，但要以次优目标维度为代价，并在其运行时四处依赖于数据点的数量。我们的抽样技术依赖于$ q $部分相关的随机预测的集合，这些预测可以同时应用于数据集$ x $的总时间，这仅取决于$ x $的大小，同时又有其$ q $ - fold kronecker产品在$ x^{\ otimes q} $的列跨度中的任何固定向量的近乎等值线。我们还表明，我们的采样方法概括为多项式以外的其他类别的内核，例如高斯和神经切线核。

训练神经网络的一种常见方法是将所有权重初始化为独立的高斯向量。我们观察到，通过将权重初始化为独立对，每对由两个相同的高斯向量组成，我们可以显着改善收敛分析。虽然已经研究了类似的技术来进行随机输入[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]的近期运行时间。对于参数不足的设置，我们还证明了在先前工作时改善的新下限，并且在某些假设下是最好的。

条件梯度方法（CGM）广泛用于现代机器学习。 CGM的整体运行时间通常由两部分组成：迭代次数和每次迭代的成本。大多数努力侧重于减少迭代的数量，作为减少整体运行时间的手段。在这项工作中，我们专注于改善CGM的迭代成本。大多数CGM中的瓶颈步骤是最大内部产品搜索（MAXIP），需要在参数上线性扫描。在实践中，发现近似的maxip数据结构是有用的启发式。然而，理论上，关于近似的MAIPIP数据结构和CGM的组合，没有任何内容。在这项工作中，我们通过提供一个正式的框架来肯定地回答这个问题，以将临时敏感散列类型近似maxip数据结构与CGM算法组合起来。结果，我们展示了第一算法，其中每个迭代的成本在参数的数量中，对于许多基本优化算法，例如Frank-Wolfe，emergorithm和政策梯度。

我们开发了第一个快速频谱算法，用于分解$ \ mathbb {r}^d $排名到$ o的随机三阶张量。我们的算法仅涉及简单的线性代数操作，并且可以在当前矩阵乘法时间下在时间$ o（d^{6.05}）$中恢复所有组件。在这项工作之前，只能通过方形的总和[MA，Shi，Steurer 2016]实现可比的保证。相反，快速算法[Hopkins，Schramm，Shi，Steurer 2016]只能分解排名最多的张量（D^{4/3}/\ text {polylog}（d））$。我们的算法结果取决于两种关键成分。将三阶张量的清洁提升到六阶张量，可以用张量网络的语言表示。将张量网络仔细分解为一系列矩形矩阵乘法，这使我们能够快速实现该算法。

我们研究了用于线性回归的主动采样算法，该算法仅旨在查询目标向量$ b \ in \ mathbb {r} ^ n $的少量条目，并将近最低限度输出到$ \ min_ {x \ In \ mathbb {r} ^ d} \ | ax-b \ | $，其中$ a \ in \ mathbb {r} ^ {n \ times d} $是一个设计矩阵和$ \ | \ cdot \ | $是一些损失函数。对于$ \ ell_p $ norm回归的任何$ 0 <p <\ idty $，我们提供了一种基于Lewis权重采样的算法，其使用只需$ \ tilde {o}输出$（1+ \ epsilon）$近似解决方案（d ^ {\ max（1，{p / 2}）} / \ mathrm {poly}（\ epsilon））$查询到$ b $。我们表明，这一依赖于$ D $是最佳的，直到对数因素。我们的结果解决了陈和Derezi的最近开放问题，陈和Derezi \'{n} Ski，他们为$ \ ell_1 $ norm提供了附近的最佳界限，以及$ p \中的$ \ ell_p $回归的次优界限（1,2） $。我们还提供了$ O的第一个总灵敏度上限（D ^ {\ max \ {1，p / 2 \} \ log ^ 2 n）$以满足最多的$ p $多项式增长。这改善了Tukan，Maalouf和Feldman的最新结果。通过将此与我们的技术组合起来的$ \ ell_p $回归结果，我们获得了一个使$ \ tilde o的活动回归算法（d ^ {1+ \ max \ {1，p / 2 \}} / \ mathrm {poly}。 （\ epsilon））$疑问，回答陈和德里兹的另一个打开问题{n}滑雪。对于Huber损失的重要特殊情况，我们进一步改善了我们对$ \ tilde o的主动样本复杂性的绑定（d ^ {（1+ \ sqrt2）/ 2} / \ epsilon ^ c）$和非活跃$ \ tilde o的样本复杂性（d ^ {4-2 \ sqrt 2} / \ epsilon ^ c）$，由于克拉克森和伍德拉夫而改善了Huber回归的以前的D ^ 4 $。我们的敏感性界限具有进一步的影响，使用灵敏度采样改善了各种先前的结果，包括orlicz规范子空间嵌入和鲁棒子空间近似。最后，我们的主动采样结果为每种$ \ ell_p $ norm提供的第一个Sublinear时间算法。

K-means++ is an important algorithm to choose initial cluster centers for the k-means clustering algorithm. In this work, we present a new algorithm that can solve the $k$-means++ problem with near optimal running time. Given $n$ data points in $\mathbb{R}^d$, the current state-of-the-art algorithm runs in $\widetilde{O}(k )$ iterations, and each iteration takes $\widetilde{O}(nd k)$ time. The overall running time is thus $\widetilde{O}(n d k^2)$. We propose a new algorithm \textsc{FastKmeans++} that only takes in $\widetilde{O}(nd + nk^2)$ time, in total.

内核密度估计（KDE）在机器学习中脱颖而出。问题是按以下方式定义的：给定的内核函数$ f（x，y）$和一组点$ \ {x_1，x_2，x_2，\ cdots，x_n \} \ subset \ subset \ mathbb {r}^d $，我们想计算$ \ frac {1} {n} \ sum_ {i = 1}^{n} f（x_i，y）$ for任何查询点$ y \ in \ mathbb {r}^d $。最近，将数据结构用于有效KDE的趋势越来越大。但是，提出的KDE数据结构集中在静态设置上。 KDE数据结构在动态变化的数据分布上的鲁棒性没有解决。在这项工作中，我们专注于具有对对抗性查询的KDE数据结构的动态维护。特别是，我们提供了KDE数据结构的理论框架。在我们的框架中，KDE数据结构仅需要次级空间。此外，我们的数据结构支持sublinear时间中数据集的动态更新。此外，我们可以在均匀时间内使用潜在的对手进行自适应查询。

现代神经网络通常具有很大的表现力，并且可以接受训练以使培训数据过高，同时仍能达到良好的测试性能。这种现象被称为“良性过度拟合”。最近，从理论角度出现了一系列研究“良性过度拟合”的作品。但是，它们仅限于线性模型或内核/随机特征模型，并且仍然缺乏关于何时以及如何在神经网络中发生过度拟合的理论理解。在本文中，我们研究了训练两层卷积神经网络（CNN）的良性过度拟合现象。我们表明，当信噪比满足一定条件时，通过梯度下降训练的两层CNN可以实现任意小的训练和测试损失。另一方面，当这种情况无法成立时，过度拟合就会有害，并且获得的CNN只能实现恒定的测试损失。这些共同证明了由信噪比驱动的良性过度拟合和有害过度拟合之间的急剧过渡。据我们所知，这是第一部精确地表征良性过度拟合在训练卷积神经网络中的条件的工作。

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

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

神经切线内核（NTK）已成为提供记忆，优化和泛化的强大工具，可保证深度神经网络。一项工作已经研究了NTK频谱的两层和深网，其中至少具有$ \ omega（n）$神经元的层，$ n $是培训样本的数量。此外，有越来越多的证据表明，只要参数数量超过样品数量，具有亚线性层宽度的深网是强大的记忆和优化器。因此，一个自然的开放问题是NTK是否在如此充满挑战的子线性设置中适应得很好。在本文中，我们以肯定的方式回答了这个问题。我们的主要技术贡献是对最小的深网的最小NTK特征值的下限，最小可能的过度参数化：参数的数量大约为$ \ omega（n）$，因此，神经元的数量仅为$ $ $ \ omega（\ sqrt {n}）$。为了展示我们的NTK界限的适用性，我们为梯度下降训练提供了两个有关记忆能力和优化保证的结果。

我们提供了新的基于梯度的方法，以便有效解决广泛的病态化优化问题。我们考虑最小化函数$ f：\ mathbb {r} ^ d \ lightarrow \ mathbb {r} $的问题，它是隐含的可分解的，作为$ m $未知的非交互方式的总和，强烈的凸起功能并提供方法这解决了这个问题，这些问题是缩放（最快的对数因子）作为组件的条件数量的平方根的乘积。这种复杂性绑定（我们证明几乎是最佳的）可以几乎指出的是加速梯度方法的几乎是指数的，这将作为$ F $的条件数量的平方根。此外，我们提供了求解该多尺度优化问题的随机异标变体的有效方法。而不是学习$ F $的分解（这将是过度昂贵的），而是我们的方法应用一个清洁递归“大步小步”交错标准方法。由此产生的算法使用$ \ tilde {\ mathcal {o}}（d m）$空间，在数字上稳定，并打开门以更细粒度的了解凸优化超出条件号的复杂性。

Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep overparameterized neural network with residual connections (ResNet). Our analysis relies on the particular structure of the Gram matrix induced by the neural network architecture. This structure allows us to show the Gram matrix is stable throughout the training process and this stability implies the global optimality of the gradient descent algorithm. We further extend our analysis to deep residual convolutional neural networks and obtain a similar convergence result.

主动回归考虑了一个线性回归问题，其中学习者会收到大量数据点，但只能观察到少数标签。由于在线算法可以处理增量培训数据并利用低计算成本，因此我们考虑了主动回归问题的在线扩展：学习者一一接收数据点，并立即决定是否应该收集相应的标签。目的是有效地维护收到的数据点的回归，并具有少量的标签查询回归。我们在$ \ ell_p $损失下为此问题提出了新算法，其中$ p \ in [1,2] $。要获得$（1+ \ epsilon）$ - 近似解决方案，我们提出的算法仅需要$ \ tilde {\ Mathcal {o}}（\ epsilon^{ - 2} d \ log（n \ kappa））$查询标签，其中$ n $是数据点的数量，而$ \ kappa $是数据点的数量，称为条件号。数值结果验证了我们的理论结果，并表明我们的方法与离线活性回归算法具有可比性的性能。