彩票假设引发了通过识别大型随机初始化神经网络的稀疏子网来实现结构学习的修剪算法的快速发展。这些“胜利门票”的存在理论上已被证明，但在次优稀疏水平。当代修剪算法还在努力确定复杂的学习任务的稀疏彩票票。这个次优稀疏仅仅是存在证明和算法的文物还是修剪方法的一般限制？并且，如果存在非常稀疏的罚单，则当前算法是能够找到它们的当前算法，或者是实现有效网络压缩所需的进一步改进吗？为了系统地回答这些问题，我们推导了一个框架来植物并隐藏大型随机初始化的神经网络中的目标架构。对于机器学习中的三个共同挑战，我们手工制作极其稀疏的网络拓扑，将它们植入大型神经网络，并评估最先进的彩票修剪方法。我们发现，修剪算法的当前局限性识别极其稀疏的票证是算法的，而不是基本的性质，并且预期我们的种植框架将促进有效修剪算法的未来发展，因为我们已经解决了所提出的领域缺失基线的问题Frankle等人。

强大的彩票票证假设有希望，即修剪随机初始化的深神经网络可以为具有随机梯度下降的深度学习提供计算有效的替代方案。但是，常见的参数初始化方案和存在证明集中在偏差为零的网络上，因此预言了修剪的潜在通用近似属性。为了填补这一空白，我们将多个初始化方案和存在证明扩展到非零偏差，包括Relu激活函数的显式“外观线性”方法。这些不仅可以实现真正的正交参数初始化，还可以减少潜在的修剪错误。在标准基准数据的实验中，我们进一步强调了非零偏置初始化方案的实际好处，并为最先进的强彩票修剪提供了理论上灵感的扩展。

彩票假设猜测稀疏子网的存在大型随机初始化的深神经网络，可以在隔离中成功培训。最近的工作已经通过实验观察到这些门票中的一些可以在各种任务中实际重复使用，以某种形式的普遍性暗示。我们正规化这一概念，理论上证明不仅存在此类环球票，而且还不需要进一步培训。我们的证据介绍了一些与强化强烈彩票票据相关的技术创新，包括延长子集合结果的扩展和利用更高量的深度的策略。我们的明确稀疏建设普遍函数家庭可能具有独立的兴趣，因为它们突出了单变量卷积架构引起的代表效益。

我们为神经网络提出了一种新颖，结构化修剪算法 - 迭代，稀疏结构修剪算法，称为I-Spasp。从稀疏信号恢复的思想启发，I-Spasp通过迭代地识别网络内的较大的重要参数组（例如，滤波器或神经元），这些参数组大多数对修剪和密集网络输出之间的残差贡献，然后基于这些组阈值以较小的预定定义修剪比率。对于具有Relu激活的双层和多层网络架构，我们展示了通过多项式修剪修剪诱导的错误，该衰减是基于密集网络隐藏表示的稀疏性任意大的。在我们的实验中，I-Spasp在各种数据集（即MNIST和ImageNet）和架构（即馈送前向网络，Resnet34和MobileNetv2）中进行评估，其中显示用于发现高性能的子网和改进经过几种数量级的可提供基线方法的修剪效率。简而言之，I-Spasp很容易通过自动分化实现，实现强大的经验结果，具有理论收敛保证，并且是高效的，因此将自己区分开作为少数几个计算有效，实用，实用，实用，实用，实用，实用，实用，实用和可提供的修剪算法之一。

我们在回归任务的背景下研究二元激活的神经网络，为这些特定网络的表现提供保证，并提出一种用于构建此类网络的贪婪算法。为了满足预测因素的资源需求较小，贪婪的方法无需提前修复网络的架构：一次构建一层，一次是一个神经元，导致预测因子并不必不是宽。深入执行给定的任务。与增强算法类似，我们的方法可以保证每次将神经元添加到一层时都会减少训练损失。这与大多数依赖于随机梯度下降的训练方案有很大的不同（避免了由替代物（如直通估计器或连续二进制化）等二进制激活功能的二进制激活功能的0个衍生衍生物问题）。我们表明，我们的方法提供了紧凑而稀疏的预测因子，同时获得了与训练二进制激活网络的最先进方法相似的性能。

Many applications require sparse neural networks due to space or inference time restrictions. There is a large body of work on training dense networks to yield sparse networks for inference, but this limits the size of the largest trainable sparse model to that of the largest trainable dense model. In this paper we introduce a method to train sparse neural networks with a fixed parameter count and a fixed computational cost throughout training, without sacrificing accuracy relative to existing dense-tosparse training methods. Our method updates the topology of the sparse network during training by using parameter magnitudes and infrequent gradient calculations. We show that this approach requires fewer floating-point operations (FLOPs) to achieve a given level of accuracy compared to prior techniques. We demonstrate state-of-the-art sparse training results on a variety of networks and datasets, including ResNet-50, MobileNets on Imagenet-2012, and RNNs on WikiText-103. Finally, we provide some insights into why allowing the topology to change during the optimization can overcome local minima encountered when the topology remains static * .

模型压缩的目的是减小大型神经网络的大小，同时保持可比的性能。结果，通过减少冗余重量，神经元或层，可以大大降低资源有限应用中的计算和内存成本。提出了许多模型压缩算法，这些算法提供了令人印象深刻的经验成功。但是，对模型压缩的理论理解仍然受到限制。一个问题是了解网络是否比另一个相同结构更可压缩。另一个问题是量化有多少人可以通过理论上保证的准确性降解来修剪网络。在这项工作中，我们建议使用对稀疏敏感的$ \ ell_q $ -norm（$ 0 <q <1 $）来表征可压缩性，并提供网络中的软稀疏性与受控程度的压缩程度之间的关系准确性降解结合。我们还开发了自适应算法，用于修剪我们理论所告知的网络中的每个神经元。数值研究表明，与标准修剪算法相比，提出的方法的表现有希望。

神经网络修剪对于在预训练的密集网络架构中发现有效，高性能的子网有用。然而，更常见的是，它涉及三步过程 - 预先训练，修剪和重新训练 - 这是计算昂贵的，因为必须完全预先训练的密集模型。幸运的是，已经经过了多种作品，证明可以通过修剪发现高性能的子网，而无需完全预先训练密集网络。旨在理论上分析修剪网络表现良好的密集网络预培训量，我们发现在两层全连接网络上的SGD预训练迭代数量中发现了一个理论界限，超出了由此进行修剪贪婪的前瞻性选择产生了一个达到良好训练错误的子网。该阈值显示在对数上依赖于数据集的大小，这意味着具有较大数据集的实验需要更好地训练通过修剪以执行良好执行的子网。我们经验展示了我们在各种架构和数据集中的理论结果的有效性，包括在Mnist上培训的全连接网络以及在CIFAR10和ImageNet上培训的几个深度卷积神经网络（CNN）架构。

深度神经网络（DNN）的计算要求增加导致获得稀疏，且准确的DNN模型的兴趣。最近的工作已经调查了稀疏训练的更加困难的情况，其中DNN重量尽可能稀少，以减少训练期间的计算成本。现有的稀疏训练方法通常是经验的，并且可以具有相对于致密基线的准确性较低。在本文中，我们介绍了一种称为交替压缩/解压缩（AC / DC）训练DNN的一般方法，证明了算法变体的收敛，并表明AC / DC在类似的计算预算中准确地表现出现有的稀疏训练方法;在高稀疏水平下，AC / DC甚至优于现有的现有方法，依赖于准确的预训练密集模型。 AC / DC的一个重要属性是它允许联合培训密集和稀疏的型号，在训练过程结束时产生精确的稀疏密集模型对。这在实践中是有用的，其中压缩变体可能是为了在资源受限的设置中进行部署而不重新执行整个训练流，并且还为我们提供了深入和压缩模型之间的精度差距的见解。代码可在：https://github.com/ist-daslab/acdc。

Consider the multivariate nonparametric regression model. It is shown that estimators based on sparsely connected deep neural networks with ReLU activation function and properly chosen network architecture achieve the minimax rates of convergence (up to log nfactors) under a general composition assumption on the regression function. The framework includes many well-studied structural constraints such as (generalized) additive models. While there is a lot of flexibility in the network architecture, the tuning parameter is the sparsity of the network. Specifically, we consider large networks with number of potential network parameters exceeding the sample size. The analysis gives some insights into why multilayer feedforward neural networks perform well in practice. Interestingly, for ReLU activation function the depth (number of layers) of the neural network architectures plays an important role and our theory suggests that for nonparametric regression, scaling the network depth with the sample size is natural. It is also shown that under the composition assumption wavelet estimators can only achieve suboptimal rates.

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

While machine learning is traditionally a resource intensive task, embedded systems, autonomous navigation, and the vision of the Internet of Things fuel the interest in resource-efficient approaches. These approaches aim for a carefully chosen trade-off between performance and resource consumption in terms of computation and energy. The development of such approaches is among the major challenges in current machine learning research and key to ensure a smooth transition of machine learning technology from a scientific environment with virtually unlimited computing resources into everyday's applications. In this article, we provide an overview of the current state of the art of machine learning techniques facilitating these real-world requirements. In particular, we focus on deep neural networks (DNNs), the predominant machine learning models of the past decade. We give a comprehensive overview of the vast literature that can be mainly split into three non-mutually exclusive categories: (i) quantized neural networks, (ii) network pruning, and (iii) structural efficiency. These techniques can be applied during training or as post-processing, and they are widely used to reduce the computational demands in terms of memory footprint, inference speed, and energy efficiency. We also briefly discuss different concepts of embedded hardware for DNNs and their compatibility with machine learning techniques as well as potential for energy and latency reduction. We substantiate our discussion with experiments on well-known benchmark datasets using compression techniques (quantization, pruning) for a set of resource-constrained embedded systems, such as CPUs, GPUs and FPGAs. The obtained results highlight the difficulty of finding good trade-offs between resource efficiency and predictive performance.

网络修剪是一种广泛使用的技术，用于有效地压缩深神经网络，几乎没有在推理期间在性能下降低。迭代幅度修剪（IMP）是由几种迭代训练和修剪步骤组成的网络修剪的最熟悉的方法之一，其中在修剪后丢失了大量网络的性能，然后在随后的再培训阶段中恢复。虽然常用为基准参考，但经常认为a）通过不将稀疏纳入训练阶段来达到次优状态，b）其全球选择标准未能正确地确定最佳层面修剪速率和c）其迭代性质使它变得缓慢和不竞争。根据最近提出的再培训技术，我们通过严格和一致的实验来调查这些索赔，我们将Impr到培训期间的训练算法进行比较，评估其选择标准的建议修改，并研究实际需要的迭代次数和总培训时间。我们发现IMP与SLR进行再培训，可以优于最先进的修剪期间，没有或仅具有很少的计算开销，即全局幅度选择标准在很大程度上具有更复杂的方法，并且只有几个刷新时期在实践中需要达到大部分稀疏性与IMP的诽谤 - 与性能权衡。我们的目标既可以证明基本的进攻已经可以提供最先进的修剪结果，甚至优于更加复杂或大量参数化方法，也可以为未来的研究建立更加现实但易于可实现的基线。

修剪是压缩深神经网络（DNNS）的主要方法之一。最近，将核（可证明的数据汇总）用于修剪DNN，并增加了理论保证在压缩率和近似误差之间的权衡方面的优势。但是，该域中的核心是数据依赖性的，要么是在模型的权重和输入的限制性假设下生成的。在实际情况下，这种假设很少得到满足，从而限制了核心的适用性。为此，我们建议一个新颖而健壮的框架，用于计算模型权重的轻度假设，而没有对训练数据的任何假设。这个想法是计算每个层中每个神经元相对于以下层的输出的重要性。这是通过l \“ {o} wner椭圆形和caratheodory定理的组合来实现的。我们的方法同时依赖数据独立，适用于各种网络和数据集（由于简化的假设），以及在理论上支持的。方法的表现优于基于核心的现有神经修剪方法在广泛的网络和数据集上。例如，我们的方法在Imagenet上获得了$ 62 \％$的压缩率，ImageNet上的RESNET50的准确性下降了$ 1.09 \％$。

修剪神经网络可降低推理时间和记忆成本。在标准硬件上，如果修剪诸如特征地图之类的粗粒结构（例如特征地图），这些好处将特别突出。我们为二阶结构修剪（SOSP）设计了两种新型的基于显着性的方法，其中包括所有结构和层之间的相关性。我们的主要方法SOSP-H采用了创新的二阶近似，可以通过快速的Hessian-vector产品进行显着评估。 SOSP-H因此，尽管考虑到了完整的Hessian，但仍像一阶方法一样缩放。我们通过将SOSP-H与使用公认的Hessian近似值以及许多最先进方法进行比较来验证SOSP-H。尽管SOSP-H在准确性方面的表现或更好，但在可伸缩性和效率方面具有明显的优势。这使我们能够将SOSP-H扩展到大规模视觉任务，即使它捕获了网络所有层的相关性。为了强调我们修剪方法的全球性质，我们不仅通过删除预验证网络的结构，而且还通过检测建筑瓶颈来评估它们的性能。我们表明，我们的算法允许系统地揭示建筑瓶颈，然后将其删除以进一步提高网络的准确性。

As the accuracy of machine learning models increases at a fast rate, so does their demand for energy and compute resources. On a low level, the major part of these resources is consumed by data movement between different memory units. Modern hardware architectures contain a form of fast memory (e.g., cache, registers), which is small, and a slow memory (e.g., DRAM), which is larger but expensive to access. We can only process data that is stored in fast memory, which incurs data movement (input/output-operations, or I/Os) between the two units. In this paper, we provide a rigorous theoretical analysis of the I/Os needed in sparse feedforward neural network (FFNN) inference. We establish bounds that determine the optimal number of I/Os up to a factor of 2 and present a method that uses a number of I/Os within that range. Much of the I/O-complexity is determined by a few high-level properties of the FFNN (number of inputs, outputs, neurons, and connections), but if we want to get closer to the exact lower bound, the instance-specific sparsity patterns need to be considered. Departing from the 2-optimal computation strategy, we show how to reduce the number of I/Os further with simulated annealing. Complementing this result, we provide an algorithm that constructively generates networks with maximum I/O-efficiency for inference. We test the algorithms and empirically verify our theoretical and algorithmic contributions. In our experiments on real hardware we observe speedups of up to 45$\times$ relative to the standard way of performing inference.

当我们扩大数据集，模型尺寸和培训时间时，深入学习方法的能力中存在越来越多的经验证据。尽管有一些关于这些资源如何调节统计能力的说法，但对它们对模型培训的计算问题的影响知之甚少。这项工作通过学习$ k $ -sparse $ n $ bits的镜头进行了探索，这是一个构成理论计算障碍的规范性问题。在这种情况下，我们发现神经网络在扩大数据集大小和运行时间时会表现出令人惊讶的相变。特别是，我们从经验上证明，通过标准培训，各种体系结构以$ n^{o（k）} $示例学习稀疏的平等，而损失（和错误）曲线在$ n^{o（k）}后突然下降。 $迭代。这些积极的结果几乎匹配已知的SQ下限，即使没有明确的稀疏性先验。我们通过理论分析阐明了这些现象的机制：我们发现性能的相变不到SGD“在黑暗中绊倒”，直到它找到了隐藏的特征集（自然算法也以$ n^中的方式运行{o（k）} $ time）;取而代之的是，我们表明SGD逐渐扩大了人口梯度的傅立叶差距。

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

We propose a simultaneous learning and pruning algorithm capable of identifying and eliminating irrelevant structures in a neural network during the early stages of training. Thus, the computational cost of subsequent training iterations, besides that of inference, is considerably reduced. Our method, based on variational inference principles using Gaussian scale mixture priors on neural network weights, learns the variational posterior distribution of Bernoulli random variables multiplying the units/filters similarly to adaptive dropout. Our algorithm, ensures that the Bernoulli parameters practically converge to either 0 or 1, establishing a deterministic final network. We analytically derive a novel hyper-prior distribution over the prior parameters that is crucial for their optimal selection and leads to consistent pruning levels and prediction accuracy regardless of weight initialization or the size of the starting network. We prove the convergence properties of our algorithm establishing theoretical and practical pruning conditions. We evaluate the proposed algorithm on the MNIST and CIFAR-10 data sets and the commonly used fully connected and convolutional LeNet and VGG16 architectures. The simulations show that our method achieves pruning levels on par with state-of the-art methods for structured pruning, while maintaining better test-accuracy and more importantly in a manner robust with respect to network initialization and initial size.

强有力的彩票假说（SLTH）规定了足够过度参数（密集的）神经网络中的子网的存在，当随机初始化并且没有任何培训时，可以实现受过全面训练的目标网络的准确性。 \ citet {da2022 -proving}的最新工作表明，SLTH也可以扩展到翻译模棱两可的网络（即CNNS），具有与密集网络中SLT相同的过多叠加级化。但是，现代神经网络能够不仅纳入翻译对称性，而且开发一般的模棱两可的体系结构（例如旋转和排列）一直是一个有力的设计原理。在本文中，我们将slth推广到保留$ g $（即$ g $ equivariant网络）的函数，并以很高的概率证明，可以修剪随机初始初始初始化的过度透明$ g $ - $ g $ - $ g $ equivariant子网网络近似于固定宽度和深度的另一个完全训练的$ g $ equivariant网络。我们进一步证明，我们规定的过透明方案也是误差耐受性的函数。我们为各个组开发了我们的理论，包括重要的理论，例如欧几里得组的子组$ \ text {e}（n）$和对称组的子群体$ g \ leq \ leq \ mathcal {s} _n _n $ - 允许我们找到用于MLP，CNN，$ \ text {e}（2）$的SLTS，并以$ \ text {e}（2）$ - 通知CNN和置换量表等度性网络作为我们统一框架的特定实例，该框架完全扩展了先前的工作。从经验上讲，我们通过修剪过度叠加的$ \ text {e}（2）$来验证我们的理论，并传达CNN和消息传递GNN，以匹配给定的错误耐受性内受过训练的目标网络的性能。