Compression-aware Training of Neural Networks using Frank-Wolfe
Authors: Max Zimmer
Christoph Spiegel
Sebastian Pokutta
Venue: Submitted to ICLR 2023 (2023)
Keywords: compression aware
neural network
frank-wolfe
pruning

Abstract: Many existing Neural Network pruning approaches either rely on retraining to compensate for pruning-caused performance degradation or they induce strong biases to converge to a specific sparse solution throughout training. A third paradigm, ’compression-aware’ training, obtains state-of-the-art dense models which are robust to a wide range of compression ratios using a single dense training run while also avoiding retraining. In that vein, we propose a constrained optimization framework centered around a versatile family of norm constraints and the Stochastic Frank-Wolfe (SFW) algorithm which together encourage convergence to well-performing solutions while inducing robustness towards convolutional filter pruning and low-rank matrix decomposition. Comparing our novel approaches to compression methods in these domains on benchmark image-classification architectures and datasets, we find that our proposed scheme is able to yield competitive results, often outperforming existing compression-aware approaches. In the case of low-rank matrix decomposition, our approach can require much less computational resources than nuclear-norm regularization based approaches by requiring only a fraction of the singular values in each iteration. As a special case, our proposed constraints can be extended to include the unstructured sparsity-inducing constraint proposed constraint by Pokutta et al. (2020) and Miao et al. (2022), which we improve upon. Our findings also indicate that the robustness of SFW-trained models largely depends on the gradient rescaling of the learning rate and we establish a theoretical foundation for that practice.

Under review as a conference paper at ICLR 2023
COMPRESSION-AWARE TRAINING OF NEURAL NET- WORKS USING TRANK-WOLFE
Anonymous authors Paper under double-blind review
ABSTRACT
Many existing Neural Network pruning approaches either rely on retraining to com- pensate for pruning-caused performance degradation or they induce strong biases to converge specific sparse solution throughout training. A third paradigm, "compression-avee" awarre trraining, obtains state-of titie-of-th-art the art dense models which are robust to a wide range of compression ratios using single dense training run while also avoiding retraining. In that vein, we propose constrained optimization framework centered around a versatile family of norm constraints and the Stochastic Frank- Wolfe (SFW) algorithm which together encourage convergence to well werl-perf solutions while inducing robustness towards convolutional filter pruning and low- rank matrix decomposition. Comparing our novel approaches to compression methods in these domains on benchmark image-classificatte datasets, find that our proposed scheme is able to yield competitive results, often outperforming existing compression-awwnn approaches. In the case of low-rank matrix decomposition, our approach can require much less computational resources than nuclear-norg regularization based approaches by requiring only a fraction of the singular values in each iteration. As a special case, our proposed constraints can be extended to include the unstructured sparsity-inductoo Pokutta et al. (2020) and Miao et al. (2022), which we improve upon. Our findings also indicate that the robustness of SFW-trained models largely depends on the gradient rescaling of the learning rate and we establish a theoretical foundation for that practice.
architectures and
constraint proposed by
INTRODUCTION
The astonishing success of Deep Neural Networks relies heavily on over- parameterized architectures (Zhang al., 20) containing up to several billions of parameters. Consequently, modern networks require large amounts of storage and increasingly long, computationally intensive training and inference times, entailing tremendous financial and environmental costs (Strubell et al., 2019). To address this, large body of work focuses compressing networks, resulting in sparse models that require only a fraction of memory or floating pointt operations while being as performant as their dense counterparts. Recent techniques include the praming of individual parameters (LeCun et al., 1989; Hassibi & Stork, 1993; Han et al., 2015; Gale et al., 2019; Lin et al., 2020; Blalock al., 2020) or group entities such as convolutional filters and entire neurons (Li et al., 2016; Alvarez & Salzmann, 2016; Liu et al., 2018; Yuan et al., 2021), the utilization of low-bit representations of networks (quantization) (Wang et al., 2018; Kim et al., 2020) well as classical matrix- or densor-dccomposition. (Zhang et al., 2016b; Tai et al., 2015; Xu et al., 2020; Liebenwein et al., 2021) in order to reduce the number of parameters.
While there is evidence of pruning being beneficial for the ability of model to generalize (Blalock et al., 2020; Hoefler et al., 2021), a higher degree of sparsification will typically lead to a degradation in the predictive power of the network. To reduce this impact, two main paradigms have emerged. Pruning after training, most prominently exemplified by Iterative Magnitude Pruning (IMP) (Han et al., 2015), forms class of algorithms characterized by three-stage pipeline of regular (sparsity- agnostic) training followed by prune-retrain cycles that are either performed once (One-Shot) or iteratively. The need for retraining to recover pruning-induces inherent disadvantage and computationally impractical (Liu et al., 2020; Ding et al., 2019; Wortsman al., 2019; Lin al., 2020). In that vein, pruning during training or regularization approaches avoid
losses is often considered to be

---

Under review as a conference paper at ICLR 2023
retraining by inducing strong inductive biases to converge sparse model at the end of training (Zhu & Gupta, 2017: Perreira-Perpimnn & Idelbayev, 2018; Kusupati et al., 2020; Liu et al., 2020). The ultimate pruning then results in negligible performance degradation, rendering the retraining procedure superftuous. However, such procedures incorporate the goal sparsity into training, requiring to completely train a model per sparsity level, while IMP needs just one pretrained model to generate the entire
frontier, albeit at the price of retraining.
A third paradigm, which is the focus of this work, naturally emerges when no retraining is allowed, but training several times to generate the accuracy-Vs-sparsity tradeoff frontier is prohibitive. Ideally, the optimization procedure is "compression-ave aware"" " (Alvarez& & Salzmann, 2017; Peste et al., 2022) or "pruning-award -wware" (Miao et al., 2022), allowing to train once and then being able to compress One- Shot various degrees while keeping most of the performance without retraining (termed pruning stability). Compression-aware training procedures are expected to yield state-of-the-arr dense models which are robust to pruning without its (regularization) hyperparameters being selected for a particular level of compression. While many such methods employ (potentially modified) SGD-variants to discrimnate between seemingly 'important 'na 'unimportant" parameters, cf. GSM (Ding et al., 2019), LC CCarreiraPPerpinaa & Idelbayev, 2018), ABFP (Ding et al., 2018) Polarization (Zhuang et al., 2020), actively encouraging the former to grow and penalizing the latter, an interesting line of research considers the usage of specific optimizers other than SGD. An optimization approach that is particularly suited is the first-order and projection-free Stochastic Frank- Wolfe (SFW) algorithm (Frank et al., 1956; Berrada al., 2018; Pokutta al., 2020: Tsilikkaridis & Roberts, 2020; Miao et al., 2022). While being valued throughout various domains of Machine Learning for its highly structured, sparsity-enhaneing update directions (Lacoste-Julic et al., 2013; Zeng & Figueiredo, 2014; Carderera et al., 2021), 1), the algorithm has only recently been considered for promoting sparsity in Neural Network architectures.
Addressing the issue of compression-aweee aware training, we propose leveraging the SFW algorithm for a family of norm constraints actively encouraging robustness to convolutional filter pruning and low-rank matrix decomposition. Our approach, using the group-k-support norm and variants thereof (Argyriou et al., 2012; Rao et al., 2017; McDonald et al., 2016), is able to train state-of- tfate-oftthe-ar image classification architectures on large datasets to high accuracy, all the while biasing the network towards peappessioon-obusteess
Similarly motivated by the work of Pokutta et al. (2020) and, concurrent to our work, Miao et al. (2022) showed the effectivvness of k-sparse constraints, focusing solely on unstructured weight pruning. Our approach includes the unstructured pruning case as well, mitigating existing convergence and hyperparameter stability issues, while improving upon the previous approach. To the best of our knowledge, our work is the first to apply SFW for structured pruning tasks. In analyzing the techniques introduced by Pokutta et al. (2020). we find that the gradient rescaling of the learning rate is of utmost importance for obtaining high performing and pruning stable results. We lay the theoretical foundation for this practice by proving the convergence of SFW with gradient rescaling in the non-convex stochastic case, extending results of Reddi et al. (2016).
Contributions.
The major contributions of our work can be summarized as follows:
1. We propose a constrained optimization framework centered around a versatile family of norm constraints, which, together with the SFW algorithm, can result in well- perl-performing models that are robust towards convolutional filter pruning as well as low-rank matrix decomposition. We empirically show on benchmark inage-classffication architectures and datasets that the proposed method is able to perform on par to or better than existing approaches. Especially in the case of low-rank decomposition, our approach can require much less computational resources than nuclear-norm regularization based approaches.
2. As a special case, our derivation includes a setting suitable for unstructured pruning. We show that our approach enjoys favorale properties when compared to the existing k-sparse approach (Pokutta et al., 2020; Miao et al., 2022), which we improve upon.
3. We empirically show that the robustness of SFW can largely be attributed to the usage of the gradient rescaling of the learning rate, which increases the batch gradient norm and effective learning rate throughout training, even though the train loss constantly decreases. To justify the usage of gradient rescaling theoretically, we prove the convergence of SFW with batch gradient dependent step size in the non-convex setting.
2

---

Under review as a conference paper at ICLR 2023
Compression-aware training is promising research direction for training models to state-of of aeftthe-rt performance while encouraging stability to pruning. We believe that our work is an important building block in the design of structured training algorithms. One strength is the fact that the proposed methods cover a wide range of compression domains, i.e., structured pruning, matrix decomposition as well unstructured pruning. Our results show the suitability of the SFW algorithm and highlight the importance of the learning rate rescaling, which we justify theoretically in the hope of enabling further research.
Related Work. The Frank- Wolfe (FW) (Frank et al., 1956) or conditional gradient (Levitin & Polyak, 1966) algorithm has been studied extensively in the convex setting, enjoying popularity throughout various domains of Machine Learning for being able to efficiently deal with complex structural requirements (e.g. Lacoste-Julien et al., 2013; Zeng & Figueiredo, 2014; Frandi et al., 2015; Jaggi, 2013; Négiar et al., 2020). With convexity being relatively strong assumption, Lacoste-Julien (2016) extended the convergence theory of FW to the non-convex setting, while Hazan & Luo (2016) and Reddi et al. (2016) provide convergence rates for the stochastic variant of the algorithm (SFW). Several different accelerated variants have been proposed, including variance reduction methods (Hazan & Luo, 2016; Yurtsever et al., 2019; Shen et al., 2019), adaptive gradients (Combettes et al., 2020) and momentum (Mokhtari et al., 2018; Chen et al., 2018).
With the theoretical foundation for the non-convex stochastic setting being laid, SFW has received surge of interest the context training Neural Networks: Ravi et al. (2018) advocate the usage of parameter constraints in Deep Learning, Xie et al. (2019) train shallow networks using SFW, Berrada et al. (2018) design a variant specifically for Neural Networks, Tsiligkaridis & Roberts (2020) employ SFW for adversarial training and Pokutta et al. (2020) show that SFW can reach state-of-the-ard performance on benchmark image classification tasks. While there is a rich literature on classical FW being applied sparsity problems in Machine Learning, only few have considered exploiting the structure-enhancing properties of (stochastic) FW in the field of Deep Learning. Grigas al. (2019) remove neurons from three layer convolutional architectures. Pokutta al. (2020) propose to constrain the parameters to lie within a k-sparse polytope, resulting in a large fraction of the parameters having small magnitude. Miao et al. (2022) leverage this idea in the context of unstructured magnitude pruming with a focus on pruning-ave aware training, being compression setting of training 'once-for-all' sparsities (Cai et al., 2020). For a detailed account of different sparsification approaches we refer to the excellent survey of Hoefler et al. (2021).
Outline. We begin by introducing the problem setting and the SFW algorithm. Section 3 contains a precise description of the proposed approach and Section 4 is devoted to experimentally comparing it to existing approaches. Section 5 contains an analysis of the two learning rate rescaling mechanisms and the converge theorem for gradient rescaling. Finally, we conclude and discuss the findings of our work in Section
2 PRELIMINARIES
For I E R", we denote the i-th coordinate of a by [x]; The diagonal matrix with x on its diagonal is denoted by diag(1) E _ For p E [1, oo]. the Lall of radius is denoted by (T). ||allo denotes the number of non-zero components of
R". For any compact convex set C C R let us further denote the Li-diameter of C by D(C)= max ||x 2ll2- As usual, we denote the gradient of a function at 0 by (() and the batch gradient estimator by C())). For the sake of convenience, we abuse notation and apply univariate functions to vectors in elementwise fashion, e.g., |o|| denotes the vector |x| := ([æ1]..., (=a)). If not indicated otherwise, we treat a tensor x of a network as a vector E R
Constrained optimization using the Stochastic Frank- algorithm We aim at optimizing the parameters 0 of Neural Network while enforcing structure-inducing constraints by considering the constrained finite-sum optimization problem
min L(l) = min REC
(()),
(1)
BEC m 1=1
3

---

Under review as a conference paper at ICLR 2023
where the per-sample loss functions & are differentiable in & and C compact. convex set. When using SGD, imposing hard constraints requires a potentially costly projection back to to ensure feasiblity of the iterates. However, an alternative is the Stochastic Frank- Frank-Wolfe (SFW) algorithm (Frank et al., 1956; Berrada et al., 2018; Pokutta et al., 2020), being projection-free and perfectly suited for yielding solutions with structural properties. To ensure feasibility of the iterates, SFW does not use the (batch) gradient direction for its updates but rather chooses a boundary point or vertex of C that best aligned with the (negative) gradient. In each iteration t, SFW calls a linear minimization oracle (LMO) on the stochastic batch gradient V, = VL(()) to solve
1/- arg min(v, V.), vEC
which is then used as the direction to update the parameters using the convex combination
B.t1 f (1- 17:00; + Te,
where 7/ [0, 1] is a suitable learning rate. If the initial parameters dn are ensured to lie in the convex set C, then the convex update rule ensures feasibility of the parameters in each iteration. Solving Equation (2) is often much cheaper than performing a projection step (Jaggi, 2013; Combettes & Pokutta, 2021), in many cases even admitting closed-form solution. If C is given by the convex hull of (possibly infinitely many) vertices, so-called atomic domain, then the solution to Equation (2) is attained at one of these vertices (Jaggi, 2013).
Inducing structure through the feasible region Apart from constraining the parameters of network to satisfy a certain norm constraint, say to have bounded euclidean norm as is typically done with weight decay (being equivalent via the Lagrangian formulation), the unique update rule Equation (3) of the SFW algorithm can be used to induce structure through the feasible region. Not only can feasible region where the iy are highly structured be beneficial generalization (Ravi et al., 2018; Pokutta et al., 2020), but further induce desirable properties such as sparsity to the network itself.
A recent example is the k-sparse polytope introduced by Pokutta et al. (2020), being a generalization of the -bal B1. The k-sparse polytope = (s((T) is defined as the convex hull of all vectors E {0, - with at most k non-zero entries, which per design, form the solution set to Equation (2). For small k, v2 exhibits high degree of sparsity and by Equation (3) only & parameters are activated while all remaining parameters are discounted strongly, encouraging convergence towards sparse solutions (Pokutta et al., 2020; Miao al., 2022).
METHODOLOGY: COMPRESSION-AWANE TRAINING WITH SFW
In the following, we propose leveraging suitable family of norm constraints which arise naturally from Lz-regularizztion with sparsification requirements. In general. we require the constraints to result in sparse update directions when applying the update rule of Equation (3). In particular, want to discriminate between predefined groups of parameters, that is, we aim at decaying seemingly unimportant groups of parameters (e.g. filters or neurons) while allowing others grow. Similarly to the proposals by Pokutta et al. (2020) and Miao et al. (2022), we control the degree of sparsification with tunable hyperparameter such that the update vectors i2 are k-sparse, i.e., non-zero at at most k entries. However, the existing approach is limited to the sparsification of Neural Networks on an hetiiiuua-weigght basis (i.e. unstructured pruning) and may further lead to hyperparameter and convergence instability, which we discuss and improve upon with our proposal.
Distinguishing this work from previously proposed approaches, we aim at constructing constraints for the structured sparsification case, which elegantly include the unstructured case well. In addition, we ensure that (similar to classical SGD), the individual parameters receive updates corresponding to the magnitude of the gradient, enabling better convergence independent of the actual & chosen, will discuss further below.
3.1 INDUCING GROUP SPARSITY TO NEURAL NETWORKS
Given a disjoint partition of the network's 's parameters into groups G G, we define the group-k- support norm (Rao et al., 2017) ball of radius 7 as
Cº (T) conv(u (u ||elbb. & &k,llul12 S <T),
(4)
4

---

Under review as a conference paper at ICLR 2023
ResNet-18 CIFAR-10
Unstructured weight pruming
0.8
Relative distanze so prined model
tet uonareyy after grining
80.0%
0.6
60.0%
40.0%
0.2
20%
50%
20.05
k-support (ours)
30%
k 100%
kesparse (Polentta ot al., Miao et al)
0.0
90%
92%
94%
96%
99%
Epoch
fraction weightss praned
(a)
(b)
Figure 1: ResNet- 18 on CIFAR-I0: Relative distance to filter pruned model corresponding 70% sparsity when training with the proposed approach and varying & (left) and accuracy-vs-sparsity tradeoff curves for unstructured weight pruning comparing our approach to the existing k-sparse approach (right).
where ||vllo,s is the smallest number of groups that are needed to cover the support of v. In other words, the vertex set of C2 (T) is given by all (vectorized) parameters for which the euclidean norm is bounded by and where most k groups contain non-zero entries. Here, the definition of set of groups G is left abstract, as could be any disjoint partition of the parameters, that is each parameter must lie in exactly one group G E G. In the following however, let g be the set of all filters in a convolutional layer.
The norm originally proposed by Rao al. (2017) motivated by the group lasso (Yuan & Lin, 2006), which is common in the statistics and classical machine learning literature. Choosing 9 as a partition of the networks parameters, a group G E G let || be the L2-norm of x E RR when only considering elements of G. Given the batch gradient of the I-th convolutional layer V/ let GI,..., G3 be the k groups with the largest gradient Lormorm Villa, and let H U G.. The solution to Equation (2) is then given by
can now state the solution Equation (2) as follows. For
Vill//I if H, otherwise.
[ve]e
proof of this fact can be found in Rao et al. (2017). SFW applied (T) updates the l filters whose (stochastic) gradient entries correspond to those of fastest loss decrease while accounting for the distribution of magnitude among them instead of using the same magnitude for all parameters. Due to the convex update rule, the remaining filters are decayed, eventually resulting in few of them being close to zero and thus making the trained network robust towards filter pruning. Figure la shows how different values of k as fraction of the overall number of filters influence the relative distance to the pruned model, indicating that & allows controlling the degree of robustness towards sparsification.
Unstructured sparsity as special case Clearly, the proposed approach is easily extendable to the pruning of other groups, such as neurons. most obvious special case arises when each weight of the network has its own group, naturally extending the above rationale to the unstructured pruning case. In that case, one recovers the k-support norm as proposed by Argyriou al. (2012), which is suitable candidate for encouraging robustness towards unstructured weight pruning and to comparison to the existing k-sparse polytope approach leveraged by Miao et al. (2022).
The k-spars approach approach suffers from two drawbacks, which are mitigated by proposed method. First all, all activated parameters will receive an update of same magnitude, namely т. This hinders convergence, especially when & is larger. Consider for example the worst-case scenario in which & equals the number of parameters n, then every single parameter of the network will receive an update of magnitude 7, essentially losing the entire information of the gradient apart from the
5

---

Under review as a conference paper at ICLR 2023
entrywise sign. On the contrary, the k-support norm with k = n will lead optimization over the L2-ball, yielding the default and best converging case of Neural Network training. Figure 1b shows the facilitated convergence of our approach, which is nonetheless highly robust towards unstructured pruning. The k-sparse approach performs well in the medium to high sparsity regime, but quickly collapses for higher compression rates. A clear advantage of k-support norm ball constraints is that SFW is able to obtain this performance in the high compression regime while not suffering from underperformance before pruning. Secondly, Pokutta et al. (2020) and Miao al. (2022) specify the desired L2-diameter 'D of C = (T( to control the regularization strength and then in turn choose the radius T such that D(PP(T)) counter-ing intuttvei since it controls both the amount of activated parameters as per design of the LMO as well the magnitude of the parameter updates, resulting in unnecessarily coupled parameters. As opposed to the k-sparse polytope, the diameter of the k-support norm ball does not depend on & and hence decouples the parameters k and as desired. Figure 4 in the appendix shows the successful decoupling of the radius and k. The k-support norm ball is less sensitive to hyperparameter changes and obtains better results throughout wide range of hyperparameter configurations than its k-sparse counterpart.
'D. Defined this way, depends on k as D/ D/(2Vk) This is
3.2 A DIFFERENT NOTION OF SPARSITY: PRUNING SINGULAR VALUES
So far employed a very restricted notion of sparsity, namely that of the existence of zeros in a matrix or tensor. Instead of removing individual parameters or groups thereof, networks can also be compressed after training by decomposing parameter matrices into a product of smaller matrices, allowing one to replace a layer by two consecutive ones that require a drastically smaller amount of FLOPs at inference (Denton et al., 2014). The key ingredient is the truncated singular value decomposition (SVD). where setting the smallest singular values to zero leads to an optimal theorem. More precisely, given rank parameter matrix W E Ra.m with singular values a(W) = (oi(W..... or (WW) and SVD W = -E ", = UEVT, U [ui...., u.] E R" ل = diag(a E R V = [VI,... 2r] E Rm.r the k-SVD of W is given by W R Σ ". = V... where the magnitude of singular values quantifies the error in approximation. detailed account of this approach can be found in the appendix. A natural approach to ensure robustness matrix decomposition is hence based on penalizing the nuclear norm ||WI]_ = [[V()) (Tai et al., 2015; Alvarez & Salzmann, 2017), which requires the costly computation of the full SVD in each iteration.
low-rank approximation by virtue of the Eckart- Fckart-Young-
When constraining the parameters to have bounded nuclear norm instead of penalizing it, the LMO solution to Equation (2) utilized by SFW be computed efficiently by requiring only the first singular value-vector-pait (Jaggi, 2013). Extending this notion to consider the l largest singular pairs, we propose utilizing the spectral-k-ssuppon norm (McDonald et al., 2016), for which the ball of radius is defined as
(T) cW R=xm (aan s k. llo()) ST,
(5)
where (W))l2 is the 2-Schattennorm of the singular values o(W) (Jaggi, 2013). The following lemma allows us to efficiently compute the LMO solution.
Lemma 3.1. Given V E R= let W. = -T]|o[ U E (T)... where Ug VT is the truncated k-SVD of V, such that only the largest singular values kept. Then W. is solution to Equation (2).
proof can be found in the appendix. Note that similar to the sosupo--support norm ball taking the magnitude of k largest gradient groups into account, the sealing by Σg (Ex))) takes the magnitude of k largest singular values into account. In Section 4.2 we study the capabilities of norm of convolutional tensors, which account for the
SFW when constraining the Spectral-k-supper majority of FLOPs at inference (Han et al., 2015). While there exist higher-order generalizations of the SVD to decompose tensors directly (cf. Lebedev et al., 2014; Kim et al., 2015), we follow the approach of interpreting the tensor W E R xexdxx with e in-channels. n convolutional filters and spatial size as an (n x cd?) - (Alvarez & Salzmann, 2017; Idelbayev & carreira-Perpinte 2020).

---

Under review as a conference paper at ICLR 2023
3.3 EXPERIMENTAL SETUP: A FAIR COMPARISON BETWEEN METHODS
All experiments are conducted using the PyTorch framework (Paszke et al., 2019), where we relied on Weights Biases (Biewald, 2020) for the analysis of results. To enable reproducibility, our implementation will be available throughout the entire review process and publicly thereafter.
We train convolutional architectures such Residual Networks (He al., 2015) and Wide Residual Networks (Zagoruyko & Komodakis, 2016) on ImageNet- 1K (Russakovsky et al., 2015), Tinylma- geNer (Le & Yang. 2015), CIFAR- 100 and CIFAR-IO (Krizhevsky al., 2009). The exact training setups as well as grid searches used can be found in the appendix. As general remark, we follow the experimental guidelines of Blalock al. (2020) towards standardized comparisons between sparsification methods. All results are averaged over two seeds with min-max bands indicated for plots and standard deviation for tables. We use a validation set of 10% of the training data for hyperparameter selection.
In the compression-awee aware setting we are interested in finding single hyperparameter configurations that perform well under wide variety of compression rates, i.e. without tuning hyperparameters for each sparsity. When comparing the performance for multiple compression rates at once, we have to decide how to select the 'best' hyperparameter configuration. To that end, we select the configuration for each method that results the highest on-average validation accuracy among all sparsities at stake.
EXPERIMENTAL RESULTS
4.1 STRUCTURED FILTER PRUNING
For the pruning of convolutional filters, we follow the PFEC approach of Li et al. (2016): at the end of training we sort the filters each convolutional layer by their Lı-norm and remove the smallest ones until the desired level of compression is met. We enforce a uniform distribution of sparsity among layers, noting that there exist more sophisticated ways of determining the per-layer pruning ratios (Liebenwein et al., 2021).
Baselines We compare our approach (denoted as SparseFW) to several baselines. Every experiment includes the most natural baseline, which corresponds to regular training with momentum SGD and weight decay. Apart from that, we have implemented the following recent filter pruning approaches. SSL (Wen et al., 2016) leverages group penalty the filters. Similarly, GLT (Alvarez & Salzmann, 2016) employs group-lasso on the filters followed by a proximal gradient descent voot-thresholding) step. ABFP (Ding et al., 2018) follows an baloobalannee" approach which penalizes certain filters while actively encouraging others to grow. SFP (He et al., 2018) softly prunes after each epoch, allowing filters to recover throughout the epoch.
Results Figure 2 shows that SFW converges to solutions that are robust to a wide range of filter pruning ratios. Especially in the high sparsity regime SFW is able to keep most its performance, while other approaches collapse, with the exception of ABFP for TinylmageNe which can be even more robust for high sparsities. Apart from that, SFW reaches excellent results for a wide range of compression ratios. Full results can be found in the appendix.
4.2 LOW-RANK MATRIX DECOMPOSITION
We compare SparseFW with spectral-k-suppor norm constraints to other approaches aiming for robustness tensor decomposition. At the end of training, we set the smallest singular values of each convolutional matrix to zero and replace the layer by two consecutive layers as described in the appendix.
Baselines Apart from the regular training baseline using momentum SGD with weight decay, we implemented NUC (Denton et al., 2014) and SVDEnergy (Alvarez & Salzmann, 2017). The former employs nuclear norm regularization technique together with SGD, hence computing the subgradient nuclear norm regularization penalty term (Watson, 1992) and updating the weights accordingly. The latter similarly performs the usual SGD update the loss, followed by applying
7

---

Under review as a conference paper at ICLR 2023
Ro=Nrt-30 Image
0075
0105
Vot pootee dhd peudte
60%
Spansil't Baddzw SSE
6215
SpaneTi
Sporet
425
06%
50%
2.5
22%
ABET
4830
275
68%
701
375
135
2015
2012
35%
475
335
125
305
-27
2012
25%
455
Batho of shom prand.
Eradtio Shors perzed.
Eraction of Bhim pesnol
(a)
(b)
(c)
Figure 2: Accuracy-vs. securacy-vs--ppariiy -s..sssssssssty tradeoff curves for structured convolutional filter pruning on CIFAR- 10 (a), CIFAR- 100 (b) and ImageNet (c). The plots show the parameter configuration with highest test accuracy after pruning when averaging over all sparsities at stake.
Table I: WideResNet CIFAR-100 100: Comparison of approaches for encouraging low-rank matrices throughout training.
Sparsity
Method
30
40%
50%
60%
70%
80%
Baseline
75.57 #0.10
74.28 +2.59
73.52 +0.95
64.67 #11.12
56.04 +2.24
10.97 +8.29
SparseFW
75.53 10.18
75.69
20.04
75.75 20.08
75.37
#0.40
75.30 20.10
73.28 +2.02
NUC
75.96 #0.29
74.86 +1.53
72.35 +0.48
68.57 #4.95
55.97 +2.80
5.40 #2.12
SVDEnergy
75.69 20.95
75.14 20.18
74.11 #0.81
66.76 +4.41
55.40 +3.04
30.82 +26.87
the soft-thresholding operator over the singular values of the parameters, a strategy also known as singular value thresholding (Cai et al., 2010). Both approaches require the computation of the entire SVD, tradionally requiring O(nm min(n, m)) operations for an n x m matrix (Allen-Zhu & Li, 2016).
Results Table 1 compares the post-pruning test accuracy of the four approaches for range of sparsities between 30 and 80 percent. The proposed approach outperforms both the natural baseline of regular SGD training well as the nuclear norm regularization approaches, experiencing only minor accuracy decrease in the high sparsity regime and no performance degradation medium sparsity regime. The accuracies correspond to the on-average best hyperparameter configuration. A significant advantage of SFW in this regard is its efficiency, allowing a higher images-per per--seo----n throughput nuclear norm regularized based approaches (446 images per second compared to 191 images per second on CIFAR- 100), where we performed measurements on the same hardware, namely 24-core Xcon Gold with Nvidia Tesla V100 GPU. Since the LMO requires the computation of the & largest singular pairs, the efficiency of SFW is clearly dependent on k. The on-average best configuration of SFW in this setting given by i corresponding to ten percent of the singular values. We used a naive implementation of the k-SVD power method (Bentbib & Kanber, 2015), noting that there are more sophisticated and faster algorithms (Allen-Zhu Li, 2016).
5 THE DYNAMICS OF GRADIENT RESCALING
The learning rate E [0, determines the length of the parameter update relative to the size of the feasible region. This coupling between regularization strength and step size makes the tuning of the learning rate cumbersome. To decouple the tuning of the learning rate from the size of the feasible region, Pokutta et al. (2020) propose two different learning rate rescaling mechanisms: diameter rescaling and gradient rescaling, the latter being used throughout our experiments in the preceding section. While the former divides the learning rate by the Lz-diameter D(C) of C. gradient rescaling rescales the update direction length to that of the batch gradient, i.e., i ne V / [|v 0zl12-
is however largely unclear what effect these normalization schemes have on both the convergence for regular training well as the robustness pruning, noting that the learning rate of SFW explicitly
8

---

Under review as a conference paper at ICLR 2023
controls the decay on non-activated parameters. Figure shows the test accuracy vs. sparsity tradeoff curves directly before and after magnitude- trgminude-pruning of the parameters, comparing the two rescaling variants when training with k-support norm constraints. Gradient rescaling consistently outperforms its diameter-based counterpart w.r.t. both dense as well as pruned test accuracy.
We found the denominator of gradient rescaling not to be subject to much variation, whereas the batch gradient norm dynamically changes the learning rate over time. Figure 6 compares the evolution of |/V for two different radii of the k-support norm ball (with fixed k), where we compare
test pruniing amoount
95.00%
94.0%%
to usual SGD training with weight decay. For both SGD and SFW, V|Vell is subject to noise and increases until 75% of the training process, despite the continuous decrease of
sccumary
94.0%%
gradises vocading (prined)
the train loss. fact, the batch gradient norm is not signif-
gradiess resaling (diass))
icantly smaller than at the start of training even though the loss converges. This behaviour might best be explainable by the presence of terplay with weight decay has recently been analyzed by van Laarhoven (2017) and Hoffer et al. (2018): layers pre- ceding a Batch-Normalization are rescaling invariant, that their output remains unchanged when multiplying all parameters by a scalar, however rescaling them results in inverse rescaling of the gradient norm in subsequent layers and iterations. Weight decay continuously decreases the scale of the parameters and hence increases the scale of the batch gradient, where stronger decay of the former leads to stronger increase of the latter. Since in gradient rescaling the norm of the batch gradient also influences the strength of the decay of the parameters, this process has self-accelerating dynamic. This dynamic results in larger steps towards the (sparse) vertices of the s-support norm ball, leading to stronger decay on the previous parameter configuration, which in turn increases the robustness to pruning, making gradient rescaling the method of choice in that setting.
diometer rescoling (praned)
diamtter recaling (Akmse)
layers, whose in-
70%
75%
50%
80%
9095
95%
antomnt of woightt praned
Figure 3: ResNet-18 on CIFAR-IO: For each pruning amount, the best hyperpa- rameter configuration w.r.t. the accu- racy after pruning (pruned) is depicted. The corresponding value before pruning (dense) is depicted dashed line.
With the following theorem, we lay the theoretical foundation by showing that incorporating the batch gradient norm into the learning rate leads to convergence of SFW at the specified rate, that is, the expected product of exact gradient norm and the Frank- Wolfe Gap G(O.) decays at rate of (TT-1/2). The precise statement as well as proof can be found in Appendix A.5.
Theorem 5.1 (Convergence of gradient rescaling, informal). Assume that L is M-smooth and É is G- Lipschitz and let T7 = Vellnffor appropriately chosen 1j and all 0 S t < T. If is chosen uniformly at random from the SFW iterates (0: 0 < < T, then we have E [G(02) [[ = (T22) where E denotes the expectation w.E.t. all the randomness present.
6 DISCUSSION AND OUTLOOK
We proposed to utilize versatile family of norm constraints to, together with the SFW algorithm, train deep neural networks to state-of-the-art dense performance as well as robustness to compression for wide range of compression ratios. Our experimental results show that SFW can leverage highly structured feasible regions to avoid performance degradation when performing convolutional filter pruning or low-rank tensor decomposition. For the latter, SFW can result significant speedups compared to nuclear-norm regularization based approaches. As special case, our proposed approach includes the unstructured pruning case and we showed how utilizing the proposed norm can mitigate the bawwacks of and improve upon the results of Miao et al. (2022). We hope that our findings regarding the importance of the learning rate rescaling well as Theorem 5.1 stimulate further research in the direction of compression-aware training with SFW.
However, we emphasize that our results hold primarily in the setting that we described, namely that of compression-awart training, where the training is sparsity-agnosti and retraining is prohibitive. Our goal was to show the versatility of SFW, which provides a suitable algorithmic framework for enforcing structure throughout training. If the sparsity can be incorporated into training, significantly more complex approaches can be applied.

---

Under review as a conference paper at ICLR 2023
7 REPRODUCIBILITY
Reproducibility is a crucial aspect of any work based on experiments. Our code will be available to the reviewers throughout all stages of the submission and publicly thereafter. We also highlight some publicly available implementations we used. The R8 implementation is based on https://githhi com/ http://hhareeooiiyylaaaaaaaaaaaa PY, where for the com/mel me1 ketoy// ceetoy/wi deeddw/wwdeeeeeeeeeeeee resnet.
Setorch-resnet1l ciraarlor Par10/bloke wttp//////.//////attt/eeeeeeeeee WideResNet architecture we relied on /ttpl///mmatteee/mmeellss/////// pytorch. For the computation of the theoretical speedup, used the implementation of Blalock ct al. (2020) available at https: / /github. com/JJGO, http/////////i/eaeeeee shrinkbench. Regarding pruning methods that are not directly available through the Pytorch framework, we used the original imple- mentation whenever possible and indicate so directly in the code.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Lazysvd: Even faster svd decomposition yet without agonizing pain. Advances in neural information processing systems, 29, 2016.
Jose M. Alvarez and Mathieu Salzmann. Learning the number of neurons in deep networks. Advances in Neural Information Processing Systems, 29, 2016.
Jose M Alvarez and Mathieu Salzmann. Compression-aware training of deep networks. Advances in neural information processing systems, 30, 2017.
Andreas Argyriou, Rina Foygel, and Nathan Srebro. Sparse prediction with the k-support norm.
Advances in Neural Information Processing Systems, 25, 2012.
Brian Bartoldson, Ari Morcos, Adrian Barbu, and Gordon Eriebacher. The generalization-staailiy tradeoff in neural network pruning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 20864. Curran Associates, Inc., 2020. URL https:://prcceedngg www.iiinnss.uurppp...... nwurips. cc/ paper/20200 www.eeeeeiie...eee.eeeee.eeeeeee efeeleeeeeeeeeeeae ww555ee88bbboo wtw.d//eeeeeeeeeeeeaeeeaeaeaaa
AH Bentbib and Kanber. Block power method for svd decomposition. Analele Universitatii" Ovidius" Constanta-Sedd Matematica, 23(2):45-555 2015.
Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Deep frank-wolfe for neural network optimization. International Conference on Learning Representations 2019, November 2018.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL wwtptttt//// wandb. com/. Software available from wandb.com.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? In I. Dhillon, D. Papailiopoulos, and V. Sze (eds.), Proceedings of Machine Learning and Systems, volume pp. 129-146, 2020. URL https: /ttectt::/prooeee httpp/poooediieeeeeeooooooeo nggs mlsys. wwtg/apprr/ai httpp/ppppp//////pppp 2ttp:///2222//// http://eeeeeeeeeeeeeeeeeeeeeeeee Pappeeeeeeercc--ee..p... pdf.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. In International Conference on Learning
Representations, 2020. URL https: / /owpneevieeeeeeeeeooeeeeeee net/ wiwoorrumiiiiyyy. xF HKwS.
Jian-Feng Cai, Emmanuel J. Candès, and Zuowei Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 1064):195-1198,, 2010. doi: 10.1137/ 080738970.
Alejandro Carderera, Sebastian Pokutta, Christof Schütte, and Martin Weiser. Cindy: Conditional gradient-based identification of non-linear dynamics noise-robust recovery. January 2021.
Miguel A Carreira- Perpinán and Yerlan Idelbayev. pruning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018
algorithms for neural net
10

---

Under review as a conference paper at ICLR 2023
Lin Chen, Christopher Harshaw. Hamed Hassani, and Amin Karbasi. Projection-free online optimiza- tion with stochastic gradient: From convexity to submodularity. In International Conference on Machine Learning, pp. 814 814-823. PMLR, 2018.
Cyrille W. Combettes and Sebastian Pokutta. Complexity of linear minimization and projection on some sets. January 2021.
Cyrille W. Combettes, Christoph Spiegel, and Sebastian Pokutta. Projection-free adaptive gradients for large-scale optimization. September 2020.
Emily L Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. Advances in neural information processing systems, 27, 2014.
Xiaohan Ding, Guiguang Ding, Jungong Han, and Sheng Tang. Auto-balanced filter pruning for efficient convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Xiaohan Ding, Guiguang Ding, Xiangxin Zhou, Yuchen Guo, Jungong Han, and Ji Liu. Global sparse momentum sgd for pruning very deep neural networks. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Buc, Buch Fox, and Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: http///poeeeineeeeeeeeeeeeeeee/e neurips. cc/paper/2019 filee/ile//////eee E34 1111188444c55555 711.88881111111111 (el1d4f1113dd41e555 Paper.pol
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2952- PMLR, 13-18 Jul 2020. URL https: http:////ccceeedeeeeeooo mlr. gress/v119/evci200
Emanuele Frandi, Ricardo Nanculef, Stefano Lodi, Claudio Sartori, and Johan A. K. Suykens. Fast and scalable lasso via stochastic Frole-wolfe methods with convergence guarantee. October 2015.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110 110, 1956.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574, 2019.
Paul Grigas, Alfonso Lobos, and Nathan Vermeersch. Stochastic in-face frank-wolfe methods for non-convex optimization and sparse neural network training. June 2019.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 28, Curran Asso- ciates, Inc., 2015. URL https: http///oceeeednggg neurips. httppp.cccpeeeeee cttccc/pppaaa cccppappr/2015555 /f/ie/ .df..
aeCeb3eed3 9dwbce
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. In S. Hanson, Cowan, and C. Giles (eds.), Advances Neural Information Processing Systems, volume 5. Borgan-Kaufmamn 1993. URL htt.ttttps:://rrceeedinae nwurips.......... cc/ pdf.
file/ /ttp:////0.......a333e.eeee.ee0.
Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In
International Conference Machine Learning, pp. 1263-1271. PMLR, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), December 2015.
Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang. Soft filter pruning for accelerating deep convolutional neural networks. August 2018.

---

Under review as a conference paper at ICLR 2023
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruming and growth for efficient inference and training in neural networks. arXiv preprint arXiv:2102.00554, January 2021.
Elad Hoffer, Ron Banner, Itay Golan, and Daniel Soudry. Norm matters: Efficient and accurate normalization schemes in deep networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Besa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httpps::/prrcceeddiiii ings neuri porripp.. ps. cc/ paper/2014 http://///...////.0..00000000000 Paw.eee..aaaaarp.........
Yerlan Idelbayev and Miguel A Carveira-Perpinán Low-rank compression of neural nets: Learning the rank of each layer. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 8049-8059, 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis R. Bach and David M. Blei (eds.), Proceedings the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 448-456. JMLR.org, 2015. URL http: proceedingss .mlr. press v v37/ioffel5 html.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th international conference on machine learming, pp. 427-435, 2013.
Jangho Kim, Yoon Yoo, and Nojun Kwak. Position-based scaled gradient for model quantization and pruning. volume 33, pp. 20415-20426, 2020.
Bong-Deokkaa Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin. Compres- sion of deep convolutional neural networks for fast and low power mobile applications. November 2015.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi. Soft threshold weight reparameterization for learnable sparsity. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5544-5555. PMLR, 13-18 Jul 2020. URL https: /ttppppeeeinns...////////o//..sp mlr wwwpss///eeeeeee........eeeeetse httes/vlllle// http///11//kuuaaatt..... html.
Simon Lacoste-Julien. Convergence of frank-wolfe for non-convex objectives. July 2016.
Simon Julls,,-Jullin, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate frank- wolfe optimization for structural syms. In International Conference on Machine Learning, pp. 53-61. PMLR, 2013.
Duong Hoang Le and Binh-Son Hua. Network pruning that matters: A case study retraining variants. In International Conference on Learning Representations, 2021. URL https: openreview
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 23/N, 7(7):3, 2015.
Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oseledets, and Victor Lempitsky. Speeding- up convolutional neural networks using fine-tuned cp-decomposition. December 2014.
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In David S. Touretzky (ed.), Advances in Neural Information Processing Systems 2, (NIPS Conference, Denver, Colorado, USA. November 27-30, 1989], pp. 598-605. Morgan Kaufmann, 1989. URL http:://pppeeee n nips wwwppp/pp....eeeeeceeec.eeeeeeee 2000 opt ma brb a damage.
Jacho Lee, Sejun Park, Sangwoo Mo, Sungsoo Ahn, and Jinwoo Shin. Layer-adaptive sparsity for the magnitude- based pruning. In International Conference on Learning Representations, October 2020.
12

---

Under review as a conference paper at ICLR 2023
Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5):1-50, 1966.
Bailin Li, Bowen Wu, Jiang Su, Guangrun Wang. and Liang Lin. Eagleeye: Fast sub-net evaluation for efficient neural network pruning. July 2020a.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. August 2016.
Mengtian Li, Ersin Yumer, and Deva Ramanan. Budgeted training:
Rethinking deep neural network training under resource constraints. In International Conference on Learning Representations. 2020b. URL https: wwwp///ppneeeeeeeeeeeeeeeeee.eee hwt.:/net//ourrieee Eorum? Hd
Lucas Liebenwein, Alaa Maalouf, Oren Gal, Dan Feldman, and Daniela Rus. Compressing neural networks: Towards determining the optimal layer- wise decomposition. July 2021.
Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. In International Conference on Learning Representations, 2020.
Junjie Liu, Zhe Xu, Runbin Shi, Ray C. C. Cheung, and Hayden K.H. So. Dynamic sparse training: Find efficient sparse network from scratch with trainable masked layers. In International Confer- ence on Learning Representations, 2020. URL /ttp:::s//pprrevieww net fott/ffoummidd SJIbGJrtDB.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. October 2018.
Andrew McDonald, Massimiliano Pontil, and Dimitris Stamos. Fitting spectral decay with the k-support norm. In Artificial Intelligence and Statistiss, pp. 1061-1069. PMLR, 2016.
Lu Miao, Xiaolong Luo, Tianlong Chen, Wuyang Chen, Dong Liu, and Zhangyang Wang. Learning pruning-friendly networks via foank-wolfe: One-shot, any-sparsity, and no retraining. In Interna- tional Conference on Learning Representations, 2022. URL https: openreview. / Forum?id-01DEtIT:.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Conditional gradient method for stochastic submodular maximization: Closing the gap. In International Conference on Artificial Intelligence and Statistics, pp. 1886-1895. PMLR, 2018
Geoffrey Négiar, Gideon Dresdner, Alicia Tsai, Laurent El Ghaoui, Francesco Locatello, Robert Freund, and Fabian Pedregosa. Stochastic frank-wolfee for constrained finite-sum minimization. In International Conference on Machine Learning. pp. 7253 7262. PMLR, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran As- sociates, Inc., 2019, URL httptttt/tttcceeeeiiiieee// bdbca288 fee F2 F
neurips http/pppr/220/ /2019/ file/ .dd..
Alexandra Peste, Adrian Vladu, Dan Alistarh, and Christoph H. Lampert. Cram: A compression- aware minimizer. July 2022.
Sebastian Pokutta, Christoph Spiegel, and Max Zimmer. Deep neural network training with frank- wolfe. October 2020.
Nikhil Rao, Miroslav Dudík, and Zaid Harchaoui. The group k-support norm for learning with structured sparsity. In 2017 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 2402-2406, 2017. doi: 10.1 10.119//CASS9922077995553
Sathya N. Ravi, Tuan Dinh, Vishnu Lokhande, and Vikas Singh. Constrained deep learning using conditional gradient and applications in computer vision. March 2018.
13

---

Under review as a conference paper at ICLR 2023
Sashank Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic nonconvex optimization. In 2016 54th annual Allerton conference on communication, control, and computing (Allerton), pp. 1244-1252 IEEE, 2016.
methods for
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations, 2020.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 (3):211 13):211-252, 2015. doi: 10.1007/s1 1233-015-0816-
Zehang Shen, Cong Fang. Peilin Zhao, Junzhou Huang, and Hui Qian. Complexities in projection- free stochastic non-convex minimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2868-28766 PMLR, 2019.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in nlp. June 2019.
Cheng Tai, Tong Xiao, Yi Zhang, Xiaogang Wang, and Weinan E. Convolutional neural networks with low-rank regularization. November 2015.
Theodoros Tsiligkaridis and Jay Roberts. On frank-wolfe optimization for adversarial robustness and interpretability. December 2020.
Twan van Laarhoven. L2 regularization versus batch and weight normalization. June 2017.
Peisong Wang, Qinghao Hu, Yifan Zhang, Chunjie Zhang, Yang Liu, and Jian Cheng. Two-step quantization for low-bit neural networks. In Proceedings of the IEEE Conference computer vision and pattern recognition, pp. 4376-4384, 2018.
Alistair Watson. Characterization of the subdifferential some matrix norms. Linear algebra and its applications, 170(0):33-45 1992.
Wei Wen, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. August 2016.
Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. Discovering neural wirings. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-But E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran Asso- ciates, Inc., 2019. URL htttps://proceeeeee ngs. nwwrips.r..... httppps.ccpppppeeeep /20pper/20110 9/99////00 file// d01 03966a8aal fa 6edd
-dd..
Jiahao Xie, Zebang Shen, Chao Zhang, Boyu Wang, and Hui Qian. Efficient projection-free online methods with stochastic recursive gradient. October 2019.
Yuhui Xu, Yuxi Li, Shuai Zhang, Wei Wen, Botao Wang, Yingyong Qi, Yiran Chen, Weiyao Lin, and Hongkai Xiong. Trp: Trained rank pruning for efficient deep neural networks. April 2020.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68 (8(1):49-61 -67, 2006.
Xin Yuan, Pedro Henrique Pamplona Savarese, and Michael Maire. Growing efficient deep networks by structured continuous sparsification. In International Conference on Learning Representations, 2021. URL htt.h:t////// /ttp:///////eeeeeee//e//e net forum? wtw.:::wwwwwwwwbwbcommmm wttp:/oorrmmmmmmmaaaabboooooooo
Alp Yurtsever, Suvrit Sra, and Volkan Cevher. Conditional gradient methods via stochastic path- integrated differential estimator. In International Conference on Machine Learning, pp. 7282-7291. PMLR, 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 100500160 May 2016.
Xiangrong Zeng and Mário A. T. Figueiredo. The ordered weighted & norm: Atomic formulation, projections, and algorithms. September 2014.
14

---

Under review as a conference paper at ICLR 2023
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 November 2016a.
X. Zhang. J. Zou, K. He, and Sun. Accelerating very deep convolutional networks for classification and detection. volume 38, pp. 1943-1955, Los Alamitos, CA, USA, oct 2016b. IEEE Computer Society. doi: 1..100///AMM..21555522222.
Michael Zhu and Suyog Gupta. To prune, or not prune: Exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01878 October 2017.
Tao Zhuang, Zhixuan Zhang, Yuheng Huang, Xiaoyi Zeng, Kai Shuang, and Xiang Li. Neuron-level structured pruning using polarization regularizer. Advances in Neural Information Processing Systems, volume 33, pp. 9865-9877 2020.
Max Zimmer, Christoph Spiegel, and Sebastian Pokutta. How learned to stop worrying and love retraining, November 2021.
15

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 TECHNICAL DETAILS
Whenever using SFW, we employ a momentum variant (Pokutta et al., 2020) and enforce local constraints, i.e., we constrain the parameters of each layer in separate feasible region. As suggested by Pokutta al. (2020), we do not tune the radius т of the feasible region C(T) directly but rather specify scalar factor > 0 and set the Lz-diameter of the feasible region of each layer
D = (10
where the expected Lg-norm of the layer parameters are simply estimated by computing the mean among multiple default initializations. D is then in turn used to compute 7 such that D(C(T)) D. This allows us to control the Lg-regularization strength of each layer. We do not prune biases and batch-normalization parameters, they only account for a small fraction of the total number of parameters yet are crucial for obtaining well well-perfo models (Evci et al., 2020). Apart from the direct comparison between diameter and gradient rescaling, we use gradient rescaling throughout all experiments.
While there exist multiple successful strategies to retrain after pruning (Renda et al., 2020; Le & Hua, 2021: Zimmer et al., 2021), the compression-awe awware training setting requires the methods to be compared directly after pruning without retraining. However, similarly to Li et al. (2020a) and Peste et al. (2022) we notice that the validation accuracy after pruning can be significantly increased by recomputing the Batch Normalization (loffe Szegedy, 2015) statisties, which have to be recalibrated since the pre-activations of the hidden layers are distorted by pruning. To that end, we recompute the statistics on the train dataset after pruning and note that practice only fraction of the training data is necessary to recalibrate the Batch Normalization layers.
In the following, we state technical details of our approaches to structured and unstructured pruning. as well as low-rank matrix decomposition.
A.1.1 STRUCTURED FILTER AND UNSTRUCTURED PRUNING
As outlined in the main section, we follow the approach of Li et al. (2016) and remove the convo- lutional filters with smallest -orm.. Since each filter might correspond a different number of parameters, depending on the convolutional layer it is located in, the Li-norm of filters is incom- parable among different layers. We hence follow the local approach and prune the same amount in each convolutional layer until the desired sparsity is met. Since this will lead to the same theoretical speedup, independent of the algorithm at stake, we omit these values.
For unstructured pruning, we employ the usual magnitude pruning, that is, we remove the parameters with smallest absolute value until we meet the desired level of compression. As we found it to work best among all algorithms, we prune globally, i.e. we select the smallest weights among all network parameters eligible for pruning. We note however that there exists several different magnitude- selection approaches (cf. e.g. Han et al., 2015; Gale et al., 2019; Lee et al., 2020).
1.1.2 LOW-RANK MATRIX DECOMPOSITION
We describe the rationale behind the decomposition of matrices with (preferably) low rank. Low-Rank matrix decomposition is centered around the idea of truncating the singular value decomposition (SVD). Let 0 = UΣV" Ex= u, be the SVD of rank-r matrix 0 E Raxm, where u;, u; are the singular vectors to singular values 01 .... 2 or > 0. The goal is now to find the best low-rank approximation 8 E nx to 6, namely to solve
|00 0 (a)
min
6
By the Eckart-Young the smallest t - r singular values are truncated. If the singular values now decay rapidly, i.e., only the first singular values contain most of the energy of 6 then this approximation can be applied as a post- procesrrccssing step without much change in the output of linear layer (Denton et al., 2014). Consequently, natural approach to ensure stability w.r.t. matrix decomposition is based on
theorem, minimizer is given by U,E,V?'
: Ei ". where
16

---

Under review as a conference paper at ICLR 2023
Table 2: Exact training configurations used throughout the experiments. The dense test accuracy refers to the optimal accuracy we achieve using momentum SGD with weight decay.
Dataset
Network (number of weights)
Epochs
Batch size
Momentum
Learning rate (t iteration)
Dense test accuracy
CIFAR-I0
ResNet- 18 (11 Mio)
100
128
0.9
linear decay from 0.1
95.0%% #0.04%
CIFAR-100
WideResNet-28Bu (37 Mio)
100
128
0.9
linear decay from 0.1
76.7% 40.2%
Tiny Inngenete
ResNet- 50 (26 Mio)
100
128
0.9
linear decay from 0.1
64.9% #0.1%
ImageNet
ResNet-50 Mio)
90
1024
0.9
linear decay from 0.1
75.35% 10.1%
encouraging the parameter matrices to have low-rank throughout training, most prominently done by regularizing the nuclear norm of the weight matrix (Tai et al., 2015; Alvarez & Salzmann, 2017). If small, then the number of FLOPs can be drastically reduced by decomposing a layer into multiple layers. For linear layers this is straightforward: let (0, (3) be weights and biases of a linear layer with SVD of f as above. For input æ, the layer computes
Or + 3 = UVVT B U x)
being interpretable as the consecutive application of two linear layers: (E,V,". 0) followed by (Ut, (3), possibly reducing the number of parameters from nm to t(n + m). For four-dimensional convolutional tensor 0 E Raxexxxd, where is the number of in-channels, n the number of convolutional filters, and d is the spatial size, we cannot directly construct the SVD. However, we follow an approach similar to those of Alvarez & Salzmann (2017) and Idelbayev & Carreira-Peryee Perrinnn (2020), interpreting as a (n ed?) matrix, whose truncated SVD decomposition allows us replace the layer by two consecutive convolutional layers, the first one having filters, channels and spatial size d, followed by n filters, t channels and spatial size of one.
We describe NUC and SVDEnergy in more detail. Both approaches solve the problem
min L(0) + AI|01I..
where À >>00 0 is suitably chosen regularization parameter. NUC does so by computing the subgradient of A||@1I, (Watson, 1992) and performing an ordinary SGD update. On the other hand, SVDEnergy relies on the proximity operator of the nuclear norm, also known as singular value thresholding (Cai et al., 2010; Alvarez& & Salzmann, 2017). In each iteration this amount to first applying an SGD step to minimize L(O;) with learning rate obtaining Ö which is then followed by soft-thresholding the singular values of d to obtain 0,41,i.e. i.e.,
rank(6.+.1)
0++1= =
u, max(0, n.A)u,
where ui, are the singular vectors of 0e+i to singular values a,, In essence, singular values smaller than A are cut-off, potentially resulting in 0.41 having low rank.
A.2 EXPERIMENTAL SETUP AND EXTENDED RESULTS
Table 2 shows the exact training configurations we used throughout all experiments, where relied on a training timeframe of 100 epochs with a linearly decaying learning rate, as suggested by Li et al. (2020b). In the following, we state the hyperparameter grids used as well as full tables and missing plots.
A.2.1 STRUCTURED FILTER PRUNING
CIFAR-10 Hyperparameter grids If not specified otherwise, we use weight decay values of [Ie-4, 5c-4] for all algorithms except SparseFW.
SparseFW: We tune the fractional k E (0.1,0.2,0.3) and the multiplier w E {10,22) (10,20, 30) of the Tzgddiameter
SSL: We tune the the filter group penalty factor À E (1e-5, 5e-5, 1e44, 5e-4, 1e-3, 5e-3). GLT: We tune the the filter group penalty factor E {1e-5, 5c-5, Ic-4, 5c-4, 1c-3, 5c-3) and the lasso tradeoff between 0 and 0.5.
17

---

Under review as a conference paper at ICLR 2023
ABFP: We tune the fractional 0.2, 0.4) and the filter group penalty factor À E {le-5, 5e-5, le-4, 5e-4, 1e-3, 5e-3).
SFP: We tune fractional E {0.5, 0.6, 0.7, 0.8}. Further, we found beneficial to tune the epoch at which SFP starts the sparsification between (0, 10, 25), since to early starts might result model collapse.
CIFAR-100 Hyperparameter grids If not specified otherwise, weight decay values of le-4, J for all algorithms except SparseFW.
SparseFW: We tune the fractional E {0.15, 0.2,0,,. 0.33 and the multiplier w {20, 30, 40} of the Lz-diameter.
SSL: We tune the the filter group penalty factor À X (le-5, 5e-5, le4,, 5e-4, le-3, 5e-3}.
GLT: We tune the the filter group penalty factor E {1e-4, 5e-4, le-3, 5e-3, le-2, 5e-3)
and the lasso tradeoff between 0 and 0.5.
ABFP: We tune the fractional & E 0.2, and the filter group penalty factor À E
{ [e--5, 5e-5, le-4, 5e-4, 1e-3, 5e-3).
SFP: We tune the fractional it E {0.6, 0.7, 0.8, 0.9}. Further, we found beneficial to tune the epoch at which SFP starts the sparsification between {0, 10, 25), since to early starts might result model collapse.
TmnyIma Hyperparameter grids If not specified otherwise, we use weight decay values of [le-4, 5e-4) for all algorithms except SparseFW.
SparseFW: We tune the fractional & [0.115, 0.2, 0.3) and the multiplier w {20, 30, 403 of the L2-diameter.
SSL: We tune the the filter group penalty factor À E (1e-5, 5e-5, le-4, 5e-4, le-3, Se-3J.
GLT: We tune the the filter group penalty factor E {1e-4, 5e-4, 1e-3, 5e-3, le-2, 5e-3)
and the lasso tradeoff between 0 and 0.5.
ABFP: We tune the fractional & {0.1, 0.3) and the filter group penalty factor À E
{ [le-5, 5e-5, le-4, 5e-4, le-3, 5e-3).
SFP: We tune the fractional & E f0.6, 0.7, 0.75, 0.8, 0.85, 0.9). Further, we found benefi- cial to tune the epoch at which SFP starts the sparsification between {0, 20, 50}, since to early starts might result in model collapse.
Imagenet Hy Hyperparrmeter grids If not specified otherwise, use weight decay values of (le-4) for all algorithms except SparseFW.
SparseFW: We tune the fractional i E {20, 25, 30, 35} of the Ly-diameter.
0.3,) and the multiplier w
SSL: We tune the the filter group penalty factor À E (1e-5, 5e-5, le-4, 5e-4, le-3, Se-3J.
GLT: We tune the the filter group penalty factor E {le-4, 5e-4, 1e-3, 5e-3, le-2, 5c-3) and the lasso tradeoff between 0 and 0.5.
ABFP: We tune the fractional & 0.2, 0.3) and the filter group penalty factor À
{ [le-5, 5e-5, le-4, 5e-4, 1e-3, 5e-3).
SFP: We tune the fractional & E {0.6, 0.7, 0.75, 0.8, 0.85, 0.9). Further, we found benefi- cial to tune the epoch at which SFP starts the sparsification between (0, 20, 50}, since to early starts might result model collapse.
18

---

Under review as a conference paper at ICLR 2023
Table ResNet-18 on CIFAR-10: Comparison of Filter Pruning approaches. For each sparsity we indicate the achieved test accuracy after pruning averaged over all random seeds including standard deviation.
Sparsity
Method
60%
70%
80%
90%
Bascline
60.32 18
32.83 #0.52
14.49 +4.68
10.92 #0.20
SparseFW
90.21 #0. 14
89.78 #0.15
86.45 #0.91
37.01 #7.18
SSL
91.26 #0.
87.13 #1.72
63.66 #0.36
16.25 #1.24
GLT
68.54 +6.12
45,42 +6,99
21.03 +3.69
9.36 #0.22
ABFP
91.45 +0.49
91.43 +0.52
91.17 #0.42
28 28.91 #0.71
SFP
88.90 #3.78
67.66 #17.25
28.44
10.55 #1.33
Table 4: WideResNet on CIFAR-100: Comparison of Filter Pruning approaches. For each sparsity we indicate the achieved test accuracy after pruning averaged over all random seeds including standard deviation.
Sparsity
Method
10%
20%
30%
40%
Baseline
71.78 +2.29
65.30 +2.82
51.33 40.34
35.00 +2.59
SparseFW W
72.21 +0.30
72.24
+0.29
72.20
#0.23
71.23 #0.18
SSL
72.10 +1.20
67.51
+0.25
59.26
#0.77
42.18 +2.67
GLT
74.08 +0.87
69.37
+1.54
54.43
14.77
28.19 +6.30
ABFP
71.49 #0.12
71.50 #0.17
71.53
#0.11
71.51 #0.13
SFP
73.45 #0.35
73.47 +0.34
73.05
+0.04
63.82 +2.14
Table 5: ResNet-50 on Tinylmagenet: Comparison of Filter Pruning approaches. For each sparsity we indicate the achieved accuracy after pruning averaged over all random seeds including standard deviation.
Sparsity
Method
10%
20%
30%
40%
50%
60%
Baseline
62.20 20.26
57.44
49.69 20.47
39.63
26.75 11.32
13.04
SparseFW
60.37 20.32
60.37
60.25 +0.21
59.87
58.30
52.56
SST.
60.44 a0.37
58.86 +0.59
56.58 +1.46
53.06 +2.28
46.82 +2.69
36.79 +2.11
GLT
60.71 #0.46
57.47 +1.09
51.75 +0.52
42.96 +1.36
30.09 +1.17
14.86 +1.21
SFP
62.06 20.38
62.07 40.37
62.06 #0.37
62.06 #0.37
49.31
#1.33
26.76 #2.22
ARFP
60.28
60.28
60.20
$9.99
Table 6: ResNet-50 on Imagenet: Comparison of Filter Pruning approaches. For each sparsity we indicate the achieved test accuracy after pruning averaged over random seeds including standard deviation.
Sparsity
Method
10%
20%
30%
40%
Baseline
65.37 +0125
37.78 +1.46
7.33 40.48
0.65 +0.04
SparseFW
69.85 #01.1
68.44 +0.06
65.07
+0.07
57.26 +0.24
SSL
70.73 =0.08
60.05 #0.19
32.08
+0.35
9.58 +0.30
GLT
72.93 +0.20
63.39 +1.98
41.80 40.36
14.53 +1.4
SEP
70.69 #0.07
69.97 #0.38
69.28 +0.89
17.92 +7.73
ABEP
70.54 +0.23
69.33 40.33
66.29 +1.56
59.27 40.39
19

---

Under review as a conference paper at ICLR 2023
A.2.2 UNSTRUCTURED WEIGHT PRUNING
CIFAR-10 Hyperparameter grids For both the k-sparse polytope as well as k-support norm ball, tune the fractional & E {0.1, 0.3, 0.4, 0.5) and the multiplier w {10, 20, 30, 40, 50) of the I2-diameter.
Figure 4 compares the two feasible regions in correspond to the k-sparse polytope (above) and k-support norm ball (below), respectively. The left column shows heatmap of the test accuracy before pruning. While both approaches lead to well performing models for wide range of hyperparameter configurations (indicated as the radius multiplier on the r-axis and on the y-axis) the k-support norm ball reaches higher results and converges properly for all configurations at stake. The k-sparse polytope approach fails to yield adequately trained dense models when the radius relatively small but & becomes larger, which is counter-intuitivv since larger k allows larger fraction of the parameters to be activated. The right column shows the corresponding heatmap of the test accuracy right after pruning. Clearly, the proposed approach is robust to pruning for wider hyperparameter range.
larger hyperparameter search. The rows
dense test accuracy
pruned test aecuracy
1.0
96.00%
0.8
90.10%
Esppase pobttgee
0.6
84.21%
0.4
78.31%
0.2
72.41%
0.8
66.51%
Icomppar womm:
0.6
60.62%
0.4
54.72%
0.2
0.00%
20
40
60
80 100
20
40
60
80
100
radius
radius
Figure 4: ResNet-18 on CIFAR-10: 10: Contour plot when performing large hyperparameter search over the radius and i of the feasible regions, where the first row corresponds to the k-sparse polytope and the second before pruning, while the right column shows the test accuracy after pruning. The k-support norm approach leads better performing dense models given the hyperparameter search stake, which in turn are more stable to pruning.
corresponds to the k-support norm ball. The left column shows the test accuracy
Miao al. (2022) showed that SFW (with k-sparse polytope constraints) outperforms SGD with weight decay, which in turn clearly, and unsurprisingly, outperforms the SFW-based approach when is allowed to retrain. Our experiments indicate that while being less robust to pruning, SGD is able to reach on-par better results after retraining, same amount time. Leaving the domain of compression-awant training, this raises a more general question: in the case that retraining not prohibited, is it beneficial to aim for robustness pruning when trying to maximize the post-retraining accuracy?
when SFW is allowed to be retrained for the
Figure illustrates experiment where investigate this exact question by performing One-Shot IMP (Han et al., 2015) to a sparsity of 95% and retraining for 10 epochs using LLR (Zimmer et al., 2021). We uned both the weight decay for regular retraining well as the weight decay for the
20

---

Under review as a conference paper at ICLR 2023
retraining phase. Non suprrsingly, there is weight decay sweet spot when it comes to maximizing the pre-pruning accuracy (left). The middle plot shows that higher weight decay typically leads to more robustness to pruning, however too large weight decay hinders convergence of the dense model and might lower the performance after pruning. Surprisingly however, as depicted in the right plot showing the test accuracy after retraining, the optimal parameter configuration is the leads to the highest accuracy before pruning, which is also the least robust to pruning. This aligns with previous findings of Bartoldson et al. (2020), who question the strive for pruning stability when retraining is not prohibitive possible.
that
X310-1
dense
fioal
1.0
niriimn oengl
0.6
97.925
0.4
80.54%
70,83%
0.8
0.0
0.073
wesght docay
vesggt docap
sntglst decae
Figure 5: ResNet-18 CIFAR-10: Test accuracy heatmap before pruning (left), after pruning (middle) and after retraining (right) when training SGD and applying One-Shot pruning, tuning both the weight decay during training (æ-axis) well as during retraining (y-axis).
A.2.3 LOW-RANK MATRIX DECOMPOSITION
CIFAR-10 Hyperparameter grids If not specified otherwise, we use weight decay values of (le-4, 5e-4) for all algorithms except SparseFW.
SparseFW: We tune the fractional & E {20, 30, 50} of the L2-diameter.
0.3) and the multiplier w e
NUC: We tune the nuclear norm penalty [le-5, 5e-5, le-4, 5e-4, 1e-3, 8e-3, 5e-3, le-2, 5e-2).
factor
A
SVDEnergy: We tune the nuclear norm thresholding
{le-2, 5e-2, 1e-1, 5e-1, 7--1, 9c-1, le-0, 5c-0).
CIFAR-100 Hyperparameter grids If not specified otherwise, we use weight decay values of (le-4, 5e-4] for all algorithms except SparseFW.
SparseFW: We tune the fractional k E (0.1,0.15, 0.2, 0.25, 0.3) and the multiplier w {20, 30, 50} of the Læ-dimmeter.
NUC: We tune the nuclear norm penalty (1e-6, 5e-6, le-5, 5e-5, 1e4, 5e-4, le-3, 5e-3, le-2, 5e-2].
factor A
SVDEnergy: We tune the nuclear norm thresholding {le-2, 5e-2, 1e-1.3e11 Se-1, 7e-1, 9c-1, le-0, 5c-03 and varied the weight decay in { [le-4, 2c-4, 5c-4).
E
21

---

Under review as a conference paper at ICLR 2023
Table ResNet-18 on CIFAR-IO: Comparison of approaches for encouraging low-rank matrices
throughout training. For each method we indicate the images-per-second throughput during training.
Sparsity
Method
40%
50%
60%
70%
80%
90%
Baseline
93.19 +0.23
93.02 #0.13
91.66 #0.17
89.95 #0.14
82.07 #1.41
53.07 #1.98
SparseFW
92. 19 +0.11
92. 12 +0.21
92.14 #0.23
91.96 +0.22
90.72 #0.05
74.94 #2.40
NUC
92.56 #0.18
92.48 #0.27
92.59 #0.17
92.45
#0.33
89.82 #0.07
64.83 #1.16
SVDEnergy
92.75 20.81
92.62 20.64
92.48 #0.30
91.68 #0.42
87.99 +2.18
65.23 48,99
Table 8: WideResNet on CIFAR-100: Comparison of approaches for encouraging low-rank matrices throughout training. For each method we indicate the
throughput during training.
Sparsity
Method
30
40%
50%
60%
70%
80%
Baseline
75.57 #0.10
74.28 +2.59
73.52 +0.95
64.67 +11.22
56.04 +2.24
10.97 +8.29
SparseFW
75.53 #0.18
75.69
20.04
75.75 +0.08
75.37
+0.40
75.30 40.10
73.28 +2.02
NUC
75.96 #0.29
74.86 +1.53
72.35
#0.48
68.57 +4.95
55.97 +2.80
5.40 #2.12
SVDEnergy
75.69 #0.95
75.14 #0.18
74.11 #0.81
66.76 +4.41
55.40 #3.04
30.82 #26.87
A.3 THE DYNAMICS OF GRADIENT RESCALING
batch gradient norm
0.35
batch gradient n0rm
0.30
0.25
0.20
0.15
0.10
SGD (1e-4)
SPW (50)
0.05
(5e-4)
(100)
0.00
100
Epoch
Figure 6: ResNet-18 on CIFAR-10: 10: The evolution of the batch gradient norm || when training SFW for different values of l and SGD for weight decay strengths. The metric averaged with respect to two random seeds and over all iterations within one epoch.
A.4 PROOFS LMO CONSTRUCTIONS
In the following, we state the missing proof of the k-support norm LMO (being special case of the group-k-sun souup-t-uuppotte norm) and Lemma 3.1.
Lemma A.1. Given Vo, let vs E (T( = convee Iello < k ||u||2 S <T such that
- VV.k./l
ll2 if top (V.l), otherwise,
[ur]s
where Vi is the vector obtuined by setting to zero all - k entries [Vly of V, with g (oV.) Then Ut E arg min (v, V.) a solution to Equation (2).
Proof. By construction, all vertices v of (T) satisfy ||u||2 = т and are k-Sparse, i.c., ||oloo < Note that being k-Sparse includes cases where more than k entries are zero. The minimum of
22

---

Under review as a conference paper at ICLR 2023
Equation (2) is attained one such u. Further recall the following reformulation of the euclidean inner product:
V.) = || cos (v,, V.)) = = cos(L((v) V.)),
(10)
where L(u, Ve) denotes the angle between v and V. This term minimized as soon as the angle between v and V, is maximal. If v was not required to be k-Sparse, i.e., v would be allowed to lie anywhere on the border of (T),). the solution would clearly be given by - - However, since is k- k-Sparse, the vector maximizing the angle to V, is the one that is closest to i/Vll but is S-Spasse at the same time. This is exactly the one claimed.
Lemma A.2. Given V Ruxm let W3 CCG(T) such that
We [Ix UVIVV
where Ug V is the truncated SVD of V, such that only the largest singular values are kept. Then W, E arg min Vi) is solution to Equation (2).
Proof. Recall that
(T) conv
(W conv
R=
rrank(W) S k. (1V) S].
Let W be some minimizer. Note that rescaling matrix by scalar has no effect on its rank. Let us hence assume that [|a(W)]]2 = a for some a > and characterize W E arg min Vt). Again, we have
(W. W.) Ww, V axl V cos( ((W, V,)).
(11)
where for is there vectorized form of matrix æ. Since we can choose a S r, this term is minimal as soon the angle L(W, V.) is maximal, i.e. cos( ((W, v.) < 0 and = where we use the same euclidean-gent geommerri interpretation as in the proof for Lemma
above. To obtain a maximal angle, we hence minimize the Ly-distance between -W and V, in compliance with the rank constraint. Since again || W Vell2 = || W Vell the Eckart-Young- theorem yields the claim, where we rescale appropriately to meet the Schattennorm constraint.
A.5 CONVERGENCE OF SFW WITH GRADIENT RESCALING
Before priving the convergence of SFW with gradient rescaling as stated it informally in Theorem 5.1, we first recall some central definitions and assumptions.
A.5.1 SETTING
Let Z be the set of training datapoints from which we sample uniformly at random. In Equation (1) we defined unique loss function &, for each datapoint. In the following let L(A wi) (0) for w; E Ω. Similar to Reddi et al. (2016) and Pokutta et al. (2020), we define the SFW algorithm as follows, where the output is chosen uniformly random from all iterates Oo Or-
Algorithm Stochastic Frank- Wolfe (SFW)
Input:
Initial parameters &n E C, learning rate ?/ E [0. 1), batch size b, number of steps T. Output: Iterate 0, chosen uniformly at random from 0o.... Or
1: for t = 0 to T 1 do
2: sample i.i.d. w1 :....W,, ......,, EΩ
3: (.((,)) 1, Σge Ve(O,, (1)
4: Ut + arg min (VL())), v)
5: 0,+1 0, + 111 (v= 0.)
6: end for
Let us recall some definitions. We denote the globally optimal solution by 0* and the Frank- Wolfe Gap at as
((
max 0, L())).
(12)
VEC
23

---

Under review as a conference paper at ICLR 2023
We will use the same assumptions Reddi et al. (2016). First of all, let assume that L is M M-smooth, that is
[VT(()- vI(y)] s M| yll
(13)
for all y E C, which implies the well-known inequality
| v1?. I(x) S L(v) + (VI(y), - -y) + 2
(14)
Further, we assume the function É to be G-Lipschitz, that is for all æ E C and w E Ω we have
[[V[(z w)ll S G.
(15)
A direct consequence is that the norm of the gradient estimator can be bounded as |V((0))| S G.
A.5.2 CONVERGENCE PROOF
The following well-established Lemma quantifies how closely ( approximates VL(0). A proof can be found in Reddi et al. (2016).
Lemma A.3, Let wI,...,Wbp W/ be i.i.d. samples in Ω2 A E C and VL(O) = & ビ Ve(G,,w;) If is
G-Lipschitz, then
G
E
(16)
b1/2"
In the following, we denote the gradient estimator at iteration as V, = ((0,)) and the Li-dimmtter D(C) D. Let e R satisfy
2h(Ou)
B Σ MD
(17)
for some given initialization fu of the parameters, where h(Ho) L((e) L(0*) denotes the optimality gap of 0u-
Theorem A.4. For all 0 S t < T, let by = bb= T and n = V/ell where 17 = TM
M(R))
If
0g chosen uniformly at random from the SFW iterates {6, : 0 < i T}, then we have
D. (VMOOMMGP3 + G² + MGD
E (g II
S VT
2/2
where E denotes the expectation w.r.t all the randomness present.
Proof. First of all notice that 77, is well defined: Using as defined above we have
1/2
1
1
n 5
(18)
2TG2
G
2T
and consequently we obtain = |/ S of L we have
by using that || S G. By M-smoothness
V2T
M
L(0(41) S L(e)) + (Q:) 0.+1 - 0,) +
00:1 0.11
2
Using the fact that 0.+1 = 0z + nh (e 0.) and that ||u/ 0ell < D, it follows that
MD
L(0,+1) < (0,)) The (VL 02) +
(19)
2
Now let
6 = arg min (L(O),, ( =
arg max V ((,,), v)
(00)
aEC
vee
be the LMO solution if we knew the exact gradient at iterate 6., where t = O...., T 1. This minimizer not part of the algorithm but crucial in the subsequent analysis. Note that we have
((0.)
max(v 0,, L(..)) (6. O,, VL.
(21)
24

---

Under review as a conference paper at ICLR 2023
Continuing from Equation (19), we therefore have
I(00+1) T.(0.) + TIe (T.()),, 0.) + (VT.(.))) VI(00), v2 01) MD
s L(0.) + T/ (V. b - 0.) + - VI(00,, 12 - 0.)++ + MD
-0)) L(O.) + Th (VL(O)) 6 - 0,) + m (VL(0.) - LL)0)), 1/2 - -0x)
M D
2
L(O.) T/ G(O,) n (V LL())), 02 .2) MD
2
where the first inequality is just reformulation of Equation (19) and the second one is due to the minimality of vz. Applying Cauchy-Schwand and using the fact that the diameter is D, we therefore have
L(0++1) S L(O.) - 7t ((O.) + D(V 12(001 + MD
(22)
Now note that 1). = |/ & Gtj. yielding
L(0c+1) & (())) - Nie ((t)) + (GD - (L(01) G
(23)
2
Let fp: denote the sequence .o...., Oz. Taking expectations and applying Lemma A.3, we get
E0 L(0-1)) E L(O:) Es [n,((0)]+ DG MD
(24)
61/2
By rearranging and summing over t O..... - 1, we get the upper bound
T-1
TDG3n 61/2
TMD&G
Eso. [m)((0))] s L(6)) -Eo.T-((r)) L(Or)
2
S [((0)) I((0) + TDG n
TMD2G4
(25)
b1/2
Now fix and apply the law of total expectation to reformulate
E (m.)] Be...
0o.l] Ee,.. (9(0))) Ed Vell 0o.l].
(26)
where exploited that once lg:: is available, ((,) is not subject to randomness anymore. The expected norm of the gradient estimator given 0, depends only on the uniform selection of samples, allowing to exploit the unbiasedness of the estimator well as the convexity of the norm using Jensen's 's inequality as follows:
Ed Vell 0o.e| = B vell 0o:e]
(27)
2 | V 0o:11l
(28)
= 11 Σ Eu, (e(0,,);)))
(29)
1=1
(30)
Combining this with Equation (25), we obtain
TDG
T
Ba... (G().) [VVI( < h(0))
(31)
61/2
2
Using the definition of o,, being a uniformly at random chosen iterate from Go. oo...., 0r-1 we conclude the proof with the following inequality.
h(0))
DG2
MD&P2
E (O.)) [VVL(.))
+
(32)
Tn
61/2
2
D
Vh(00)MG2BB + G²
MGD
(33)
VT
2/2
25


Reviews:
[{"review_id": "mByKxvZi00", "reviewer": "Reviewer_RYk5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel framework for compression-aware training of neural networks. The proposed method uses norm constraints, for two types of pruning (1) convolutional filter pruning (2) low-rank matrix decomposition, expressed via updates of the Stochastic Frank-Wolfe (SFW) algorithm efficiently. ", "summary_of_the_review": "Overall, I think this is a good paper. The ideas presented are novel and are well-supported by ample experimental evidence and some theoretical results. The proposed method and discussions are relevant and useful to the community. ", "strength_and_weaknesses": "Pros: \n- The proposed framework is interesting and beneficial to the community. The authors provide sufficient intuition and motivation behind the use of the sparsity-inducing norm constraints and how they can be effectively realized via SFW. The presentation is clear and the math is easy to follow. \n- All the claims are supported well by empirical studies on benchmark datasets. The baselines seem sensible; although I must admit that I'm not too familiar with the related works in the compression-aware setting\n\nComments on the robustness study:\nOne of the interesting sections in the paper is the study on the robustness of the pruned model. The experimental study and the authors' discussion on the benefits of using the rescaled learning rate are insightful, especially at higher compression rates. With gradient scaling, the authors are able to show the 1/\\sqrt(T) convergence result (FW gap) for SFW. However, they still collectively don't provide enough convincing arguments for the robustness claims, in my opinion.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kkpY9s6ENoY", "reviewer": "Reviewer_gmRx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a constrained optimization framework based on a versatile family of norm constraints and the stochastic FrankWolfe (SFW) algorithm. The proposed method apply on benchmark image-classification architectures and datasets, and it yields competitive results, often outperforming existing compression-aware approaches. ", "summary_of_the_review": "The proposed method applied on benchmark image-classification architectures and\ndatasets outperform the existing compression-aware approaches.  In the case of low-rank\nmatrix decomposition, the proposed method can require much less computational resources\nthan nuclear-norm regularization based approaches by requiring only a fraction of\nthe singular values in each iteration. \n\nSome Questions:\n\n1. Why the proposed method can require much less computational resources\nthan nuclear-norm regularization based approaches by requiring only a fraction of\nthe singular values in each iteration ? It would be great if the authors would detail it.\n\n2. In the experimental results, we hope to see the efficiency of the proposed methods. \nPlease give the results on test accuracy vs time.\n\n3. There will be a strict upper limit of 9 pages for the main text of the submission, \nwith unlimited additional pages for citations (https://iclr.cc/Conferences/2023/CallForPapers). \nThis paper maybe not fit for this request.\n\n\n\n\n--------------------------------------------------------------------------------------------------------------------\n---------------------------------------------------------------------------------------------------------------------\nThe authors still did not solve my main concern- the limited novelty of this paper. \nSo I support to reject this paper.\n", "strength_and_weaknesses": "Strength:\n\nThe proposed method applied on benchmark image-classification architectures and\ndatasets outperform the existing compression-aware approaches.  In the case of low-rank\nmatrix decomposition, the proposed method can require much less computational resources\nthan nuclear-norm regularization based approaches by requiring only a fraction of\nthe singular values in each iteration.\n\nWeakness:\n\nThe novelty of this paper is very limited. This paper basically combines \nthe existing k-support norm regularztion (https://arxiv.org/pdf/1204.5043.pdf, \nhttps://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7952587) and the existing stochastic \nFrank-Wolfe methods (https://arxiv.org/pdf/1607.08254.pdf). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kJ178g9l2A", "reviewer": "Reviewer_XfiW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors adopt SWF (stochastic Frank-Wolfe) algorithm to perform compression-aware training. Prelimary experiments demonstrate the efficacy of the proposed approach. ", "summary_of_the_review": "See the comments above.", "strength_and_weaknesses": "The authors adopt a classic optimization algorithm (SFW) to perform structure compression-aware training. Before this work is accepted, several concerns should be addressed:\n(i)\tThe first concern is about the novelty. This work heavily depends on the unstructed compression-aware training by extending the unstructured pruning to structured pruning setting. The novelty is discounted. \n(ii)\tThe authors claims that the adopted SFW methods achieve significant speedup compated with nuclear-norm regularization based approach. In general, for nuclear norm regularized optimization, several SVD-free methods have been proposed [1]. We require the authors compare their proposed approach with more advanced optimization methods for solving nuclear norm regularized problem to show its effecgtiveness for a fair comparision. Furthermore, the real speedup ration should be reported to show the efficacy of the proposed algorithm. \n(iii)\tThe current experiments restrict to CIFAR-10, CIFAR-100, Tiny-ImageNet. In general, ImageNet-1K is a standard benchmark to verify the effiectiveness of the compression methods. We recommend the author provide more experents on ImageNet-1k. \n(iv)\tAbout Theorem 5.1. Why does the term E[g*||Grad{L}||] indicate the convergence of the proposed approach? THe authors should gives more discussions on this convergence criteria. \n\n\n[1] SVD-free Convex-Concave Approaches for Nuclear Norm Regularization, IJCAI, 2017.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0VyfhWKZab2", "reviewer": "Reviewer_v7Db", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes the SFW algorithm to solve a constrained optimization framework. The proposed method can result in well-performing models that are robust towards convolutional filter pruning as well as low-rank matrix decomposition. Experiment results also show that the proposed method has better “accuracy vs sparsity” performance than existing approaches. ", "summary_of_the_review": "The experiment result is convincing. I also like the idea of combing the SFW and the group-k-support norm constraint together, but I didn’t find much novelty in the theory and algorithm respects.", "strength_and_weaknesses": "Strength:\nOverall, the paper is well-organized and easy to follow. This paper studies two optimization problems: convolutional filter pruning and low-rank matrix decomposition. For the first problem, the author uses the group-k-support norm ball to constrain the optimization problem to compress the model instead of the existing k-sparse approach. To solve this problem, the author proposes to use the SFW algorithm. For the second problem, the spectral-k-support norm is used. Experiments results on those two problems show the advantage of the proposed method. Specifically, the accuracy of the proposed method is more robust than the existing methods when compressing the model.\n\nThis work also empirically shows that the robustness of SFW can largely be attributed to the usage of the gradient rescaling of the learning rate. To justify the usage of gradient rescaling theoretically, the convergence of SFW with batch gradient dependent step size in the non-convex setting is established.\n\nWeaknesses:\n1.  In the abstract, the author said that compression-aware training could obtain state-of-the-art dense models which are robust to a wide range of compression ratios using a single dense training run while also avoiding retraining. But I believe the proposed framework still needs to run several times independently to obtain models with different compression ratios. That is, to obtain a model with different compression ratios, you have to run SFW another time from the beginning. Therefore, I am not sure why this method can avoid retraining.\n  \n2. I notice that In Figure 2, the performance of ABFP is comparable to or even better than SFW. Could the author show the advantage of SFW compared to ABFP?\n\n3. Although Theorem 3.1 shows the convergence of SFW with batch gradient dependent step size in the non-convex setting.  However, the assumption of the objective function seems to be too strong (L-smooth and L-Lipschitz). I believe neither of the two studied problems would satisfy these assumptions. Please correct me if I am wrong.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject