Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints
Authors: Jose Gallego-Posada
Juan Ramirez
Akram Erraqabi
Yoshua Bengio
Simon Lacoste-Julien
Venue: NeurIPS 2022 Accept (2022)
Keywords: sparsity
constrained optimization
deep learning
l0 regularization

Abstract: The performance of trained neural networks is robust to harsh levels of pruning. Coupled with the ever-growing size of deep learning models, this observation has motivated extensive research on learning sparse models. In this work, we focus on the task of controlling the level of sparsity when performing sparse learning. Existing methods based on sparsity-inducing penalties involve expensive trial-and-error tuning of the penalty factor, thus lacking direct control of the resulting model sparsity. In response, we adopt a constrained formulation: using the gate mechanism proposed by Louizos et al. (2018), we formulate a constrained optimization problem where sparsification is guided by the training objective and the desired sparsity target in an end-to-end fashion. Experiments on CIFAR-{10, 100}, TinyImageNet, and ImageNet using WideResNet and ResNet{18, 50} models validate the effectiveness of our proposal and demonstrate that we can reliably achieve pre-determined sparsity targets without compromising on predictive performance.

Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints
Jose Gallego-Posade Juan Ramirez
Akram Erraqabi
Yoshua Bengio
Simon Lacoste-Julien
Mila and DIRO, Université de Montréal, Canada
$ Canada CIFAR Al Chair
Abstract
The performance of trained neural networks is robust to harsh levels of pruning. Coupled with the ever-growing size of deep learning models, this observation has motivated extensive research on learning sparse models. In this work, we focus on the task of controlling the level of sparsity when performing sparse learning. Existing methods based on sparsity-induchn error tuning of the penalty factor, thus lacking direct control of the resulting model sparsity. In response, we adopt a constrained formulation: using the gate mech- anism proposed by Louizos al. [31], we formulate constrained optimization problem where sparsification is guided by the training objective and the desired sparsity target in an end-to-end fashion. Experiments on CIFAR-(10, 100), Tiny- ImageNet, and ImageNet using WideResNet and ResNet( 18, 50) models validate the effectiveness of our proposal and demonstrate that we can reliably achieve pre-determined sparsity targets without compromising on predictive performance.
penalties involve expensive trial-and-
1 Introduction
Commonly used neural networks result in overparametrized models, whose performance is robust to harsh levels of parameter pruning [18, 42, 12, 14]. Thus, regularization techniques aimed at learning sparse models can drastically reduce the computational cost associated with the Icarnt model by removing unnecessary parameters, and retain good performance in the learning task. Given the recent research trends which explore the capabilities of ever more ambitious large-scale models [2], developing techniques which provide reliable training of sparsified models becomes crucial for deploying them in massively-used systems, or on resource-constrainee devices.
Pruning methods aim to reduce the storage and/or computational footprint of model by discarding individual parameters [18, 34] or groups thereof [29, 27, 27,37], while inducing minimal distortion the model's 's predictions. These methods can be further categorized based on whether the sparse model is obtained while or after training the model (also known as in in-training and post-training sparsification).
Traditional post-training methods rely on heuristic rankings of the weights or filters to be pruned, often based on parameter magnitudes [26, 18). Despite their simplicity. these methods usually require retraining the weights to maintain high accuracy after pruning, and thus incur in additional computational overhead. On the other hand, in- -n-training methods which learn a good sparsity pattern by augmenting the training loss with sparsity-inducing penalties [31, 27] do not perform fine-tuning, but face challenges regarding the tuning and interpretability the penalty hyperparameter.
In this work', we focus on the task of learning models with controlled levels of sparsity while performing in-training pruning. We tackle two central issues of the popular penalized method of Louizos et al. [3]]: J: ① tuning the Lo-penalty coefficient to achieve a desired sparsity level is non trivial and can involve computationally wasteful trial-and-error attempts; 2 in the worst case the penalized method can outright fail at producing any sparsity, as documented by Gale et al. [14].
Correspondencce to: {gallegoj, juan.ramires ramirez, akram erraqabi) quebec tOur code is available at: https: / httggggt...o/aaaallllgg
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

Lo-density
Parameters
MACs
1.0
10a
Layer- wise
Target Lo-density
0.8
Ponalty coef. Apen
48
48
10
0.6
Error (%)
46
10
Error
0.4
44
10
0.2
42
10"
0.0
0.0
0.2
0.4
0.6
0.8
1.0
25
50
75
100
0
25
50
75
100
Achioved Lo-density
Parameters (%)
MACs (%)
1.0
Model-wise
Tanget La-density
0.8
Ponalty coef. Apen
0.6
10
Error (%)
42.5
Error (%)
42.5
10
0.4
42.0
42.0
10
0.2
41.5
41.
10"
0.0
41.0
41.0
0.0 0.2 0.4 06
0.8 1.0
100
Achieved Lo-density
Purumeters (%)
MACs (%)
Figure 1: Training sparse ResNet18 models on Tinyema [28]. Density denotes the proportion of active gates in the model. The penalty-based method (red) shows a taaatinggtee--ovrhhoooin
behavior, making it difficult to tune. In contrast, our proposed constrained approach (blue) reliably achieves the desired target Lo-densities. The diagonal denotes the ideal case in which the achieved density exactly matches the target density used the constrained setting. Parameters and MACs are computed for the corresponding test-time purged networks following the procedure described in Appendix D; the Lo-density (see Eq. (3)) is computed for the train-time model.
To address these limitations, we propose a constrained optimization approach in which arbitrary sparsity targets are expressed constraints on the Lo-norm of the parameters. Formally, we consider constraints of the type ||0,llo < K, where 0, represents a group g of parameters of the network (e.g. individual layers, the whole model), and resort to well established gradient- based methods for optimizing the Lagrangian associated with the constrained optimization problem.
Adopting this constrained formulation provides several advantages:
Unlike the multiplicative factor À of a penalty term, the constraint level Eg has straight- forward and interpretable semantics associated with the density of block of parameters 0g, i.e. the percentage of active parameters.
Requiring different density levels for different parameter groups (e.g. lower density for network modules with a larger computational or memory footprint), simply amounts to specifying several constraints with levels matching these desired densities, thus avoiding the costly process of trial-and-error tuning" and re-balancing various penalty factors.
Much like the penalized approach in which additional regularizers can be "stacked" as other additive terms in the objective, new desired properties can be expressed in the constrained formulation in a modular and extensible fashion as additional constraints.
In non-convex problems, the constrained formulation can be strictly more powerful than the penalized approach: there may be constraint levels that cannot be achieved by any value of the penalty coefficient [1, $4.7.4).
The left column of Fig. illustrates the interpretability and controllability advantages of the con- strained approach when training a sparse ResNet18 8 model on TinylmageNet. We vary the constraint level (left axis) and the penalty coefficient (right axis) and compare the achieved parameter density at the end of training. Note how the penalized approach results in very dense model (> 80%) across several orders of magnitude of the penalty factor, and then suddenly drops to < 40% density. This behavior is in stark contrast with our proposed constrained approach, which consistently achieves the desired target density, across a wide range of values. See Section 5 for further discussion.
The purpose of our paper is to illustrate the feasibility and advantages of using constrained formula- tions in the study of sparse learning. We favor Lagrangian, gradient-basee methods for tackling the constrained optimization problem due to their ease of use and scalability in the context of machine learning models. Exploring alternative constrained optimization techniques an interesting direction for future studies, but lies beyond the scope of our work.
Appennix E. shows that the tuning challenges of penalized methods exist even for simple MI.P tasks.

---

The main contributions of this work are:
Building on the work of Louizos al. [31], we propose a constrained approach for learning models with controllable levels of sparsity (Section 3).
We introduce a dual restart heuristic to avoid the excessive regularization caused by the accumulation of constraint violations in gradient-based Lagrangian optimization (Section 3). Previous studies [31. 14] have been unsuccessful at training sparse ResNets [45] based on Lo regularization without significantly damaging performance. We propose two simple adjustments to the implementation of Louizos et al. [31], allowing us to overcome these challenges (Appendix H).
We provide empirical evidence that we can reliably achieve controllable sparsity across many different architectures and datasets. Moreover, the controlability and interpretability benefits of the constrained approach do not come at the expense of achieving competitive predictive performance (Section 5).
2 Sparsity via Lo Penalties
Louizos et al. [31] propose a framework for learning sparse models using the Lo-"norm" of the model parameters an additive penalty to the usual training objective. The Lg-norm counts the number of non-zero entries in the parameter vector, and ignores the magnitude of said entries. Consider h(æ; 0) be predictor with parameters 0 and supervised learning problem defined by dataset of N i.i.d. pairs D = {(1i. y: W a loss function l and a regularization coefficient Xpen 2 0. Louizos et al. [31] formulate the To regullalrr empirical risk objective:
N Σ (b(z 0), yi) + Apen
R(O, Apen) CD + Xen 0
110, + 0}
(I)
The non-differentiability of the Lo-norm makes poorly suited for gradient- based optimization. The authors propose a reparamettization = C z, where θ are free (signed) parameter magnitudes, and are independent stochastic gates indicating whether a parameter is active The authors model the gates using modified version of the concrete distribution [32, 22], with parameters denoted by Φb
This reparametrization allows for gradient-basee optimization procedures, while retaining the possi- bility of achieving exact zeros in the parameters values. We provide a brief overview of the properties of the concrete distribution in Appendix A.
Moreover, this stochastic reparametrizzaion induces a distribution over the network parameters O. In consequence, the authors propose to re-define the training objective as the expectation (under the distribution of the gates) of the Lo-regularized empirical risk in Eq. (1):
R(,, Φ;, Apen) Ez
[ @ z, Apen)
Ez
[ z)} + Apen tb [||[||o]
(2)
Test-time model. Since the stochastic reparametrization induces a distribution over models, Louizos et al. [31] propose a protocol to choose a sparse network at test time. We employ a slightly modified version of their strategy, based on the medians of the gates (see Appendix A.
Parameter grouping. Rather than considering gate for each individual parameter (which would double the number of trainable parameters), several parameters may be gathered under shared gate. We match the setup Louizos et al. [31] who focus on neuron sparsity: using L one gate per input neuron for fully connected layers; and 2 one gate per outpul feature map for convolutional layers. This use of structured sparsity results in practical storage and computation improvements since entire parameter groups (e.g. slice of convolution kernels/activation) can be discarded.
Combining other norms. Louizos et al. [31] show that their reparametrization can used in con- junction with other commonly used norms for regularization, such as the L2-norm. One can express Ezi [10|3 = | P(z; A 0J 03, where 0 is gate-rescaled version of in order to "avoid extra shrinkage for the gates". Further discussion on the challenges of combining weight-decay and their proposed reparametrization can be found in Appendices and I.
'Ntte that Lo-norm of is determined by that z. This is because commonly used weight initialization and optimization schemes, θ o 0 almost surely.
3

---

Sparsity via Lo Constraints
We favor formulating regularization goals as constraints, rather than as additive penalties with fixed scaling factors. We refer to these two approaches as constrained and penalized, respectively. Although ubiquitous tool in machine learning, penalized formulations may come the cost of hpper-aarameter interpretability and are susceptible to intricate dynamics when incorporating multiple, potentially conflicting, sources of regularization.
3.1 Constrained Formulation
In contrast to the penalized objective of Louizos et al. [31] presented in Eq. (2), we propose to incorporate sparsity through constraints the Lo-norm. We formulate an optimization problem that aims to minimize the model's expected empirical risk, subject to constraints on the expected Lo-norm of pre-determined parameter groups:
La density
Ex, (h 1l
min (0, - Ezi (D( & z)) s.t. Oconst ( A 0.6
Sen for g E [1: G],
(3)
# #(0y)
where 9 denotes a subset of gates, (x) counts the total number of entries in x, and Xg denotes the entries of a vector associated with the group g. See Appendix for details parameter grouping.
Note how the # (fg) factor in the constraint levels allows us to interpret 'g as the maximum proportion of gates that are allowed to active within group g, in expectation. We refer to eg as the target density of group g. Lowering the target density demands a sparser model and thus (not necessarily strictly) more challenging optimization problem terms of the best feasible empirical risk. Moreover, for any choice of e, O, the feasible set in Eq. (3) is always non-empty; while values of Eg 2 result in vacuous constraints.
We highlight one important difference between the constrained and penalized formulations. The penalized approach is jointly optimizing the training loss fanj(0, Φ) and the expected Lo-norm ( due to their additive combination (mediated by Ape).. Meanwhile, the constrained method focuses obtaining the best possible model within prescribed density level given two feasible solutions, the constrained formulation Eq. (3) only discriminates based on the training loss. In other words, we aim to satisfy the constraints, not to optimize them.
3.2 Solving the Constrained Optimization Problem
We start by considering the (nonconvex concavve) Lagrangian associated with the constrained formu- lation in Eq. (3), along with the corresponding min-max game:
0" oh X
argmin argmax 2(0, Φb, Aco) faos (0, ②)) Ng (1)) -Eg)
(4)
0.6
A.
where A_o [X&]_ are the (non-negative) Lagrange multipliers associated with each constraint.
commonly used approach to optimize this Lagrangian is simultaneous gradient descent on (0, ())
and projected (to IR+)) gradient ascent on Aco [30]:
@ r0+1 0 0' Tprimal V و 2(0' (C.))
A4+1 Xo Mamml Vx, 2(0' Φ6 Noo) X + Mammll [Bcomac (+,)) - eg] g=1
g
(5)
X+ max (0.
The gradient update for Aco matches the value of the violation of each constraint. When a constraint is satisfied, the gradient for its corresponding Lagrange multiplier is non-positive. leading a reduction in the value the multiplier.
Negligible computational overhead. Just as the penalized formulation of Louizos et al. [31], the update for Ø and & requires the gradient of the training loss and that of the expected Lo-norm. Hence, the cost of executing this update scheme the same as the cost of gradient descent update on the penalized formulation in Eq. (1), up to the negligible cost of updating the multipliers.

---

Choice of optimizers. We present simple gradient descent- ascent (GDA) updates in Eq. (5). However, our proposed framework is compatible with different choices for the primal and dual optimizers. including stochastic methods. Throughout our experiments, we opt for primal (model) optimizers which match standard choices for the different architectures. A choice of gradient ascent for the dual optimizer provided consistently robust optimization dynamics across all tasks. Detailed experimental configurations are provided in Appendix J. The evaluation and design of other optimizers, especially those for updating the Lagrange multipliers, is an interesting direction for future research.
Oscillations. The non-convexity of the optimization problem in Eq. (4) implies that a saddle point (pure strategy Nash Equilibrium) might not exist. In general, this can lead to oscillations and unstable optimization dynamics. Appendix F provides pointers more sophisticated constrained optimization algorithms which achieve better convergence guarantees on nonconvex concavv problems than GDA. Fortunately, throughout our experiments we observed oscillatory behavior that quickly settled around feasible solutions. Empirical evidence of this claim is presented in Section 5.4.
Extensibility. Our proposed constrained formulation is "modular" in the sense that it is easy to induced other properties in the model's behavior beside sparsity (e.g. fairness [20, 5J) by prescribing them as additional constraints; much like extra additive terms in the penalized formulation. However, the improved interpretability and control afforded by the constrained approach removes the need to perform extensive tuning of the syper-parameters to balance these potentially competing demands.
3.3 Dual Restarts
drawback of gradient-basse updates for optimizing the Lagrangian in Eq. (4) that the constraint violations accumulate in the value of the Lagrange multipliers throughout the optimization, and continue to affect the optimization dynamics, even after a constraint has been satisfied. This results in an excessive regularization effect, which forces the primal parameters towards the interior of the feasible set. This behavior can be detrimental if we are concerned about minimizing the objective function and satisfying (but not minimizing!) the constraints.
To address this, we propose a dual restart scheme in which the Lagrange multiplier Ag associated with a constraint Beoma( (Øg) S Eg is set to O whenever the constraint is satisfied; rather than waiting for the "negative" gradient updates (geomsi( (8gy) Eg < O when feasible) to reduce its value. Formally, A max (o, (XColg + Tadual (Dconst ($1) en))
if
Gconst (0)) > Eg
11 (0, otherwise
(6)
Dual restarts remove the contribution of the expected Lo-norm to the Lagrangian for groups whose constraints are satisfied, so that the optimization may focus on improving the predictive performance of the model. In fact, this dual restart strategy can be theoretically characterized as a best response (in the game-theoretic sense) by the dual player. The effect of dual restarts in the optimization dynamics is illustrated in Section 5.3 and Appendix G.
4 Related Work
Min-max optimization. Commonly used methods for solving constrained convex optimization problems [1, 11, 21] make assumptions on the properties of the objective function, constraints or feasible set. In this work, we focus on applications involving neural networks, leading the violation of such assumptions. We rely on GDA-like updates for optimizing the associated Lagrangian. However, our proposed formulation can readily integrated with more soplisticated/theoretiia supported algorithms for constrained optimization of Non-convex-coneet objectives, such as the extragradient method [24]. Further discussion on guarantees and alternative algorithms for min-ma max optimization is provided in Appendix F.
Model sparsity. Learning sparse models is rich research area in machine learning. There exist many different approaches for obtaining sparse models. Magnitude-basee based methods [41, 18] perform one or more rounds of pruning, by removing the parameters with the lowest magnitudes. Popular non-magnitude based techniques include [26, 17, 34]. Structured pruning methods [6. 37, 31, 29], remove entire neurons/channels rather than individual parameters. More recently, the Lottery Ticket Hypothesis [12] has sparked interest in techniques that provide the storage and computation benefits of sparse models directly during training [35, 8). However, finding "good" sparse sub-networks at initialization remains central challenge for these techniques [13,33]. 33].
5

---

Controllable sparsity. Magnitude pruning [18, 29] can achieve arbitrary levels of sparsity "by design" since it removes exactly the proportion of parameters with lowest magnitudes in order to match the desired density. However, the magnitude pruning method experiences certain shortcomings: ! retaining performance usually involves several round of fine-tuning 2 relies on the assumption that magnitude (of filters or activations) is a reasonable surrogate for parameter importance; and @ it lacks the "extensibility" property of our constrained formulation: it is not immediately evident how to induce other desired properties in the model, besides sparsity.
Note that several extensions of the basic magnitude pruning method have been proposed. Zhu and Gupta [47] start from partially or fully pre- rre-traine model and consider sparsification scheme in which the network density gradually reduced, while fine-tuning the model to compensate for any potential loss in performance due to pruning. Wang et al. [44] start by identifying the parameters to be removed by applying magnitude pruning on pre-trained model. However, rather than pruning the model immediately, the authors propose to fine-tune the model with an adaptive T-2-penalty. The weight of this penalty is increased over time for the previously identified parameters, leading their magnitudes to decrease during the fine-tuning process.
Sparsity via constrained optimization. Previous works have cast the task of learning sparse models as the solution of a constrained optimization problem. Carreira-Perpinan and Idelbayev [3] consider a reformulation of the constrained optimization problem using "auxiliary variables", and assume that the constraints enjoy an efficient proximal operator. Their empirical evaluation is limited to low-scale models and datasets.
Zhou et al. [46] adopt a constrained formulation similar to ours, although based on a different reparametrization of the gates. The authors tackle the constrained problem via projected gradient descent by cleverly exploiting the existence of an efficient projection of the gate parameters onto their feasible set. However, the applicability of their method is limited to constraints with an efficientlycoompuabble projection operator.
Lemaire et al. [27] consider "budget-awer aware regularization" and tackle the constrained problem using a barrier method. Although originally inspired by a constrained approach. their resulting training objective corresponds to a penalized method with a penalty factor that requires tuning, in addition to the choice of barrier function.
Other constrained formulations in MI. Constrained formulations can be used to prescribe desired behaviors or properties in machine learning models. Nandwani et al. [36] study the problem of training deep models under constraints on the network's predicted labels, and approach the constrained problem in practice through a min-max Lagrangian formulation. Incorporating these constraints during training allows them to inject domain-specift knowledge into their models across several tasks in natural language processing.
Fioretto et al. [10] consider wide range of applications spanning from optimal power flow in energy grids, to the training of fair classification models. Their work demonstrates how Lagrangian- based methods can be complementary to deep learning by effectively enforcing complex physical and engineering constraints.
Cotter et al. [5] train models under constraints on the prediction rates of the model over different datasets. Note that the sparsity constraints we study in this paper depends only on properties of the parameters and not on the predictions of the model. We would like to highlight that the notion of proxy constraints introduced by Cotter al. [5] can enable training models based on constraints on their actual test time density, rather than the surrogate expected Lo- Lo-norm metric.
5 Experiments
The main goal of our work is to train models that attain good predictive performance, while having a fine-grained command on the sparsity of the resulting model. In this section we present comparison with the work of Louizos et al. [31]]; we explore the stability and controllability properties of our Lagrangian bbased constrained approach, along with the effect of our proposed dual restarts heuristic. Finally, we present empirical evidence which demonstrates that our method successfully retains its interpretability and controllability advantages when applied to large-scale models and datasets.
This re- traininnng overhead makes magnitude pruning less appealing compared with in-training alternatives. since magnitude pruning is typically performed given an already fully trained model.
'See comparison other sparsity methods therein, along with the survey of Gale et al. [14].

---

5.1 Experimental Setup
Experiment configuration and hyperparameters. Details implementation, hyperparameter choices and information on the network architectures can be found in Appendices A, B, C, D and J.
Model- and layer-wise settings. We present experiments using two kinds of constraints: one global constraint on the proportion of active gates throughout the entire model; or several local constraints prescribing maximum density at each layer. Note that for models such as ResNet50, the layer-wise setting involves handling 48 constraints. The experiments below demonstrate that our constrained approach can gracefully handle from single constraint up to dozens of constraints in a unified way and still achieve controllable sparsity for each of the layers/model. This level of control is an intractable goal for penalized methods: as demonstrated in Appendix E, even trying to tame one constraint via a penalty factor can be prohibitively expensive.
To In-regularization for residual models. ResNets have been a challenging setting for To--enalty based methods. Gale et al. [14] trained WideResNets [45] and ResNet50 [19] using the penalized lo-regularization framework of Louizos et al. [31], and reported being unable to produce sparse ResNets without significantly degrading performance.
We propose two simple adjustments that enable us to successfully train WRNs and ResNets with controllable sparsity, while retaining competitive performance: ! increasing the learning rate of the stochastic gates; and 2 removing the gradient contribution of the weight decay penalty towards the gates. Appendices H and I provide detailed analysis and empirical validation of these two modifications. We integrate these adjustments in all experiments involving residual models below.
Obtaining test-time models. Appendix D deseribes procedure to transform model with stochastic gates into a deterministic, test-time model. The measurements of retained parameters and MACs muulippy-accummulee operations) percentages reported in the tables and figures below, computed for the deterministic, purged, test-time models.
5.2 Proof of Concept Experiments on MNIST
We begin by comparing the behavior of our method with that of Louizos et al. [31] in the simple setting of training MLP and LeNet5 architectures on the MNIST dataset. The authors report the size of their pruned architectures found using the penalized formulation. In this section we aim to showcase the controllability advantages of our constrained approach. We manually computed the corresponding model-wise or layer-wise density levels achieved by the reported architectures of Louizos et al. [31] and used these values as the target density levels for our constrained formulation.
Table 1: Achieved density levels and performance for sparse MLP and LeNet5 models trained on MNIST for 200 epochs. Metrics aggregated over 5 runs. 'Results by Louizos et al. [31] with N representing the training set size (see Appendix C).
Pruned
Val. Error (%)
Architecture
Grouping
Method
Hyper-parametie
at 200 epochs (avg :: 95% CI)
architecture
best
Pen.
Apaan 0.1/N
219-214-100 100
1.4
Model
MLP 784-300-100
Const.
= 33%
198-233-100
1.36
1.77 +: 0.08
Pen.
Apmn 0.110.1,001111
266-88-33
1.8
Layer
Const.
(30%, 30%, 30%
243-89-29
1.58
2.19 = 0.12
Pen.
Apen = 0.1/N
20-25-45-462
0.9
Model
LeNet5
Const.
= 10%
20-21-34-407
0.56
1.01
0.05
20-50-800-85
Pen.
Apen [10, 0. O.1//N
9-18-65-25
1.0
Layer
Const. [50%, 30%, 70%, 10%]
10-14-224-29
0.7
0.91 + 0.05
Table 1 displays the results of our constrained method and the reported metrics for the penalized approach. Note that, as desired, the pruned models obtained using the constrained formulation resemble closely the "target architecture sizes" reported by Louizos et al. [31]. Moreover, our method does not cause any loss in performance with respect to the penalized approach. This final observation will be confirmed for larger-scale tasks in later sections.
Note that the goal of this section is to demonstrate that our constrained approach can achieve arbitrary sparsity targets "in one shot" (i.c. without rial-and-error tuning) and without inducing any
7

---

compromise in the predictive performance of the resulting models. Comprehensive experiments for MLP and LeNet5 models on MNIST across wide range of sparsity levels for model- and layer-wise constraints are presented in Appendix K.1.
5.3 Training Dynamics and Dual Restarts
We now discuss the effect of the dual restarts scheme introduced in Section 3.3 on the training dynamics of our constrained formulation. Fig. illustrates the training of convolutional network on MNIST under a 30% model-wise density constraint when using (blue) or not (orange) dual restarts.
Lo-densit
0.75
Multiplier Aco
Train loss
0.50
0.5
0.05
0.00
100
100
200
100 Epoch
200
Epoch
Epoch
Feasibility
Figure 2: Effect of dual restarts for training LeNet5 MNIST with model-wise target density 'g 30% (horizontal dashed line). The accumulation of the constraint violations in the Lagrange multiplier leads to excessive sparsification when the model satisfies the constraint. Restarting the Lagrange multiplier allows the model to concentrate on improving the training loss.
We initialize the Lagrange multipliers to zero. Therefore, at the beginning of optimization there is no contribution from the Lo-norm in the Lagrangian (see Eq. (4)), and the optimization focuses on improving the training loss. As the optimization progresses, the constraint violations are accumulated in the value of the Lagrange multiplier. When the Lagrange multiplier is sufficiently large, the impor- tance of satisfying the constraints outweighs that of optimizing the training loss." " In consequence, the model density decreases. As the model reaches the desired sparsity level, Aco stops increasing.
Up until the time at which the model is first feasible, the multiplier value accumulates the constraint violations (scaled by the dual learning rate). Once the model is feasible, the constraint violation (g)))( < < 0 becomes negative, leading to a decrease in the Lagrange multiplier. However, at this stage, the Lagrange multiplier is large due the accumulated constraint violations. This confers a higher relative importance to the gradient of the constraints over that of the training loss: the larger multiplier encourages reduce the constraints even they are already being satisfied.
Our proposed dual restart heuristic reduces the Lagrange multiplier to zero whenever the constrained is satisfied, allowing the training focus minimizing the training loss faster. Although this heuristic may lead to slightly unfeasible solutions, as demonstrated throughout our experiments, our models remain consistently below (or close to) the required Lo-density levels.
5.4 Stable Constraint Dynamics
Despite the theoretical risk of oscillatory dynamics commonly associated with iterative constrained optimization methods, we consistently observed quickly stabilizing behavior our experiments. Fig. 3 shows the density levels throughout training for layer of a WideResNet-288 10 trained on CIFAR-10 (right), and the model-wise density of a ResNet18 trained on TinyImageNet (left).
The desired density levels are successfully achieved over a wide range of targets, and the constraint dynamics stabilize quickly. These dynamics were consistent across all our architectures and datasets.
"Note that the Lagrange multiplier influences the update of the model parameters by dynamically adjusting the relative importance of the gradient of the training loss with respect to the gradient of the constraint. In the penalized method this relative importance fixed.

---

1.00
1.00
Lo-density
Lo-density
0.8
0.65
0.50
0.50
0.5
0.35
0.25
0.25
0.2
25
Epoch
Epoch
Figure 3: Density levels for a ResNetl 8 model (left; trained with model-wise constraint) and the last sparsifiable layer of WidcResNNet-28-10 model (right; trained with layer-wise constraints).
5.5 Large-scale Experiments
We now demonstrate the scalability of method to more challenging settings: consider Resde)ResNet models on the CIFAR- (10, 100), TinylmageNet [28] and ImageNet [7] datasets. Comprchensive experiment provided in Appendix K.
CIFAR-(10, 100) and TinyImageNet. Figures and 4 display the results for a ResNet18 model trained on Imagenet, and -edeRes 10 trained on CIFAR-10, respectively. The left column shows the alignment between the achieved and desired densities (as expected proportion of active gates in the model). Our method (in blue) provides robust control over the range of densities. In contrast, the penalized method (in red) exhibits an unreliable dependency between the penalty coefficient and the achieved density: when increasing the coefficient Apen. the achieved density seems to be insensitive to Apen for several orders of magnitude until starts considerably changing. This brittle sensitivity profile limits the potential of the penalized method for controlling sparsity.
Tg-denstty
Parameters
MACs
Target Lo-density
Penalty cuel. Apen
Apn
Layer-wise
10
4.4
Error (%))
4.4
0.6
10
Error
0.4
4.2
10
0.2
10"
0.0
0.2
0.4
088
1.0
50
75
100
25
75
100
Achioved Lo-density
Parameters (%)
MACs (%)
1.0
10a
Model-wise
Target Lg-density
Penally cuef. Apen
4.4
4.4
10a1
Error (%)
Error (%)
4.2
4.2
10
0.4
10
4.0
4.0
0.2
10
0.0
0.0
0.2
0.4
0.6
0.8 1.0
50
75
100
25
75
100
Achieved Lo-density
Parameters (%)
MACss (%)
Figure 4: Training sparse WideResNet-28-I models on CIFAR-IO.
Columns two and three display the number of parameters and MACs (multply-accumulatt operations) of the resulting purged models, proportion of those of the fully-dense baseline model. Note that, while retaining similar proportion of parameters, layer-wise constraints lead to a larger reduction in the number of MACs, compared the model-wise case. This because layer-wise constraints induce strict, homogeneous sparsification of all the modules of the network; while the model-wise setting can allow for more flexible allocation the parameter budget across different layers.
ImageNet. We conducted experiments on ImageNet [7] with ResNet50 architecture. We compare with layer-wise structured magnitude pruning [ The results presented in Table 2.
For each layer, remove the filters with the (1 c) lowest L1 norms achieved the desired density.

---

Note that experiments with layer-wise constraints correspond to optimization problems with 48 constraints (one for each sparsifiable layer). We highlight the number of constraints since tuning such large number of penalty coefficients is an intractable challenge when using the penalized method.
Table 2: ResNer50 models ImageNet with structured sparsity. "Fine-tuning" for zero epochs means no fine-tuning.
Best Val. Error (%)
Target Density
Lo Lensityy (%)
Params (%)
MACs (%)
Method
After line-tuning for # epochs
Pre-trained Baseline
100
[25.5M]
[4.12 10")
23.90
Const. Model-wise
90.36
88,06
91.62
24.68
90%
Const, Layer-wise
90.58
87.07
85.97
24.97
L1-MP Layer-wise
85.94
84.99
38.74
25.38
24.69
24.68
Const. Model-wise
70.78
64.41
76.50
25.53
c 70%
Const, Layer-wise
70.36
61.91
58.59
26.98
LI-MP Layer-wise
62.15
59.85
97.78
29.04
26.80
26.14
Const, Model-wise
50.18
42.47
58.00
27.51
50%
Const, Layer-wise
50.70
43.15
38.25
27.89
LI-MP Layer-wise
43.47
39.76
99.75
36.21
29.98
29.16
Const. Model-wise
30.31
31.81
42,05
29.65
30%
Const. Layer-wise
31.44
30.16
23.74
31.71
L1-MP Layer-wise
29.86
24.80
99.89
56.11
36.90
34.74
Just like the magnitude pruning method, our proposed approach successfully delivers the desired levels of sparsity in this challenging task. To the best of our knowledge, our work constitutes the first instance of successfully learning ResNet50 models using the Lo reparametrization of Louizos et al. [31] for structured sparsity while retaining high accuracy.
Our results clearly demonstrate that the constrained Lo formulations obtain large levels of structured parameter reduction while preserving performance. Table shows quick degradation in performance for the magnitude pruning method, and highlights the need for fine-tuning in heuristic- based pruning techniques.
5.6 Unstructured Sparsity
Appendix L contains experiments with unstructured sparsity (i.e. one gate per parameter, rather than per neuron/activation map) for the MNIST and TinyImageNce datasets. These experiments show that the controllability advantages of our constrained formulation apply in the unstructured regime. Recall that Gale et al. [14] report an apparent dichotomy between sparsity and performance when training (residual) models with unstructured sparsity using the Lo reparametrization of Louizos et al. [31]. Our experimental results demonstrate that it is in fact possible to achieve high levels of sparsity and predictive performance.
Conclusion
We resort to constrained optimization approach tool to overcome the controllability shortcom- ings faced by penalty-based sparsity methods. Along with a reliable control of the model density, this technique provides more interpretable hyper-parameter and removes the need for expensive iterative tuning. We adopt the Lo reparametrization framework Louizos et al. [31] and integrate simple adjustments to remedy their challenges training Resde) models. Our proposed method succeeds at achieving the desired sparsity with no compromise on the model's performance for broad range of architectures and datasets. These observations position the constrained approach solid, practical alternative to popular penalty- based methods in modern machine learning tasks.
Acknowledgments and Disclosure of Funding
This work was partially supported by the Canada CIFAR AI Chair Program and by IVADO PhD Excellence Scholarship. Simon Lacoste-Julien CIFAR Associate Fellow and Yoshua Bengio is Program Co-Director in the Learning in Machines & Brains program.
10

---

References
[1] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. (Cit. on 5)
[2] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language Models are Few-Shot Learners. In NeurlPS, 2020. (Cit. on p. 1)
[3] M. A. Carreira-Perpinen and Y. Idelbayev. Pruning. In CVPR, 2018. (Cit. on p. 6)
Algorithms for Neural Net
[4] G. H. Chen and R. T. Rockafellar. Convergence Rates in Forward- Splitting. SIAM Journal on Optimization, 7(2):421-444, 1997. (Cit. on p. 19)
[5] A. Cotter, H. Jiang. M. Gupta, S. Wang, T. Narayan, S. You, and K. Sridharan. Optimization with Non-Differentee Goals. In JMLR, 2019. (Cit. on p. 5, 19)
Constraints with Applications to Faimess, Recall, Churn, and Other
[6] B. Dai, C. Zhu, B. Guo, and D. Wipf. Compressing Neural Networks using the Variational Information Bottleneck. In ICML, 2018, (Cit. on p. 5)
[7] Deng, W. Dong, R. Socher, L.-J. Li, Kai Li, and Li Fei-Fei. ImageNet: A Large-Scale
Hierarchical Image Database. In CVPR, 2009. (Cit. p. 9, 26)
[8] U. Evci, T. Gale, J. Menick, P. S. Castro, and E. Elsenl. Rigging the Lottery: Making All Tickets Winners. ICML, 2020. (Cit. on p. 5)
[9] U. Evci, Y. Ioannou, C. Keskin, and Y. Dauphin. Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win. In AAAI, 2022. (Cit. on p. 37)
[10] F. Fioretto, P. Van Hentenryck, T. W. K. Mak, C. Tran, F. Baldo, and M. Lombardi. Lagrangian Duality for Constrained Deep Learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2020. (Cit. on p. 6)
[11] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2):95-100, 1956. (Cit. on p. 5)
[12] J. Frankle and M. Carbin. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In ICLR, 2019. (Cit. on p. 5)
[13] J. Frankle, G. K. Dziugaite, D. Roy, and M. Carbin, Linear Mode Connectivity and the Lottery Ticket Hypothesis. In ICML, 2020. (Cit. on 5)
[14] T. Gale, Elsen, and S. Hooker. The State of Sparsity in Deep Neural Networks. In NeurIPS- Workshop in ODML-CDNNR, 2019. (Cit. on p. 1, 3, 6, 7, 10, 21, 23, 36)
[15] J. Gallego-Posada and J. Ramirez. Cooper: a general-purpose, deep dearning-firss library for constrained optimization in Pytorch. https://gi thu.. www/ cooper- org/ cooperr 2022. (Cit. on p. 25)
[16] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A Variational Inequality Perspective on Generative Adversarial Networks. In ICLR, 2019. (Cit. on p. 19)
[17] Y. Guo, A. Yao, and Y. Chen. Dynamic Network Surgery for Efficient DNNs. In NeurlPS, 2016. (Cit. p. 5)
[18] S. Han, H. Mao, and W. J. Dally. Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. In ICLR, 2016. (Cit. on p. 1, 6)
[19] K. He, X. Zhang, S. Ren, and J. Sun. Deep Residual Learning for Image Recognition. 1rXiv:1512.088 1512.03385 2015. (Cit. on p. 7, 21)
[20] S. Hooker, A. Courville, G. Clark, Y. Dauphin, and A. Frome. What Do Compressed Deep Neural Networks Forget? arXiv:1911.0524 2019. (Cit. on 5.
11

---

[21] M. Jaggi. Revisiting Frank-Wolfe: Projection-Free Freeeiioo-FFeeeeee Sparse Convex Optimization. In ICML,
2013. (Cit. on p. 5)
[22] E. Jang, S. Gu, and B. Poole. Categorical Reparameterization with Gumbel-Softmax, In ICLR, 2017. (Cit. on 3)
[23] D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. In ICLR, 2015. (Cit. on
p. 25)
[24] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 1976. (Cit. p. 19)
[25] S. Kundu, M. Nazemi, M. Pedram, K. M. Chugg, and P. A. Beerel. Pre-defined Sparsity for Low-Complexity Convolutional Neural Networks. IEEE Transactions on Computers, 69(7): 1045-1058, 2020. (Cit. on 26)
[26] Y. LeCun, S. Denker, and S. A. Solla. Optimal Brain Damage. In NeurlPS, 1990. (Cit. on p. 5,
[27] C. Lemaire, A. Achkar, and P.-M. Jodoin. Structured Pruning of Neural Networks With Budget-Aware Regularization. In CVPR, 2019. (Cit. p. 1)
[28] F-F. Li, A. Karpathy, and J. Johnson. Tiny ImageNet. https://www. http:///wwwwkaggl...c com/c/ tiny- imagenet, 2017. (Cit. on 2, 26)
[29] H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf. Pruning Filters for Efficient ConvNets. In ICLR, 2017. (Cit. on p. 1, 5, 6, 9, 18, 27)
[30] Lin, C. Jin, and M. Jordan. On Gradient Descent Ascent for Nonconvex-Coneave Minimax Problems. In ICML, 2020. (Cit. on 4, 19)
[31] C. Louizos, M. Welling, and D. P. Kingma, Learning Sparse Neural Networks through Lo Regularization. ICLR, 2018. (Cit. on p. 1, 3, 6, 10, 16, 17, 21, 22, 25, 26, 27, 28, 30, 32, 36)
[32] C. J. Maddison, A. Mnih, and Y. W. Teh. The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. ICLR, 2017. (Cit. on 3)
[33] E. Malach, G. Yehudai, S. Shalev-Schwartz, and O. Shamir. Proving the Lottery Ticket Hypothesis: Pruning is All You Need. In ICML, 2020. (Cit. on 5)
[34] D. Molchanov, A. Ashukha, and D. Vetrov. Variational Dropout Sparsifies Deep Neural Networks. In ICML, 2017. (Cit. on p. 1,5)
[35] H. Mostafa and X. Wang. Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization. In ICMI., 2019. (Cit. on p. 5)
[36] Y. Nandwani, A. Pathak, Mausam, and P. Singla. A Primal Dual Formulation For Deep Learning With Constraints. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2019. (Cit. on p. 6)
[37] K. Neklyudov, D. Molchanov, A. Ashukha, and D. P. Vetrov. Structured Bayesian Pruning via Log-Normal Multiplicative Noise. In NeurlPS, 2017. (Cit. on p. 1,
[38] A. Nemirovski. Prox-Method with Rate of Convergence O(1/T) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Problems. SIAM Journal on Optimization, 15(1):229-22 251, 2004. (Cit. on p. 19)
Saddle Point
[39] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, Desmaison, Kopf, Yang, De Vetoo, M. Raison, Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An Imperative Style, High-Peeformance Deep Learning Library, 2019. (Cit. on p. 25, 35)
[40] Savarese, H. Silva, and M. Maire. Winning the Lottery with Continuous Sparsification. In NewrIPS, 2020. (Cit. p. 26)
12

---

[41] G. Thimm and E. Fiesler. Evaluating Pruning Methods. In ESANN, 1995. (Cit. on 5)
[42] K. Ullrich, E. Meeds, and M. Welling. Soft Weight-Sharing for Neural Network Compression. ICLR, 2017. (Cit. on p. 1)
[43] J. von Neumann. Zur Theorie der Gesellschaftsspicl.. Mathematische Annalen, (00(1)) 1928. (Cit. p. 19)
[44] H. Wang. C. Qin, Y. Zhang, and Y. Fu. Neural Pruning via Growing Regularization. In ICLR, 2021. (Cit. on p. 6)
[45] S. Zagoruyko and N. Komodakis. Wide Residual Networks. In BMVC, (Cit. on p. 7,
21, 25, 26)
[46] X. Zhou, W. Zhang, H. Xu, and T. Zhang. Effective Sparsification Neural Networks With Global Sparsity Constraint, In CVPR, 2021. (Cit. p. 6)
[47] M. Zhu and S. Gupta. To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression. 170.0017 2017. (Cit. on p. 6)
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Code provided in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix J.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendices J and K.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "r3AT6Rebti9", "reviewer": "Reviewer_TJdj", "summary": "The authors propose a new approach for enforcing sparsity with the L0-regularization technique proposed by Louizos et al. that allows for explicit specification of the target sparsity at the end of the optimization process. They demonstrate that their approach produces high quality sparse models on a range of applications and datasets.\n", "questions": "1. I wonder whether your fixes for the training instability reported by Gale et al. would generalize to unstructured sparsity as they explored. If you could comment on this or include results in the paper I think it would be useful to readers.\n2. In Table 2 it would be nice to include some higher sparsity levels. I recognize that you’re inducing structured sparsity and that expected compression levels will be lower than with unstructured but I think it would be useful to readers to see up to 50% compression.\n3. If you wanted to demonstrate another level of impact you could compare your improved L0-regularization technique to other state-of-the-art methods for neuron/channel pruning. I do not think this is necessary for this work to be published at NeurIPS, but it would be a way to increase the impact of the contributions further.\n", "limitations": "I am not aware of any limitations of the proposed approach that were not mentioned in the work. The authors did explicitly analyze potential issues - for example, the dynamics of their constraint during training.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper is very well written and easy to follow. The authors do a good job of highlighting the benefits of their technique, including the ability to target specific sparsity levels and the modularity and extensibility provided by this capability.\n2. I think the results of this work are impactful. L0-regularization was a very promising technique but prior work (Gale et al.) was unable to scale it to large models. The authors addressed its limitations both in the difficulty of tuning the loss coefficient to achieve a desired level of sparsity and the previously reported issues with training stability\n \nI did not identify any major weaknesses. In the next section I highlight a few things that could help to bring my score up further.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Td8p9PnKIKY", "reviewer": "Reviewer_syaD", "summary": "This paper mainly focuses on a previous work l0 regularization and demonstrate its feasibility  when solving it with constraints. The work considers the problem of L0 regularization thoroughly by 1) learning models with controllable levels of sparsity 2) dual restart heuristic to avoid the excessive regularization 3) fixing the performance dropping problem of L0 regularization.", "questions": "1. Can you present more comparisons with more sota methods and sparser region [2] ?\n\n2. Can this method be applied to sparse training and improve performance?\n\n[2] Winning the Lottery with Continuous Sparsification", "limitations": "I don't see any negative societal impact of this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This work presents valid improvements to previous L0 regularization, since I know L0 regularization cannot achieve stable results on ImageNet.\n\n2. This work gives a nice modification to the original test-time model selection criterion for its mediean property.\n\nWeaknesses: \n1. There is already work on dealing with the penality and unstable problem of L0 regularzation [1](Effective Sparsification of Neural Networks with Global Sparsity Constraint) and the final accuracy result is lower than [1] on ImageNet (73.44\\% with 12% params vs. 74.68% with 10% params). Please discuss the difference and connections with [1] and better make more empirical comparisons.\n\n2. The good property of test-time model selection should be further justified. Can you please give a table of statistics to demonstrate the changing dynamics of the test-time model selected during the training process? \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "D_VhLV07LIA", "reviewer": "Reviewer_oV8j", "summary": "The authors take the $L_0$ penalty method from Louizos et al. and present a constrained version of it, i.e., estimate the Lagrange multiplier to satisfy some desired level of parameter sparsity. They do this by specifying a desired parameter sparsity density, either for the entire model or per layer. The Lagrange factor appears to be estimated using (non-stochastic) gradient descent, with one additional trick: only apply the constraint when it isn’t satisfied. Experiments are performed using convolutional and fully-connected models on image datasets (CIFAR10, TinyImageNet, and ImageNet) in the supervised learning setting. They compare with the penalized version of the regularizer, as well as a pruning method based on weight magnitude.\n", "questions": "My main question is regarding the use of gradient descent for the Lagrange multiplier. Updating this factor once per epoch seems somewhat arbitrary, and I would guess that the issues with the slowly updating factor affecting training stem from this choice. Why not update the Lagrange multiplier online using stochastic gradients from each batch? Did you try this? The ‘dual restart heuristic’ may not be necessary in this case.", "limitations": "While the authors do not explicitly address the limitations of their work, they discuss the various tradeoffs of different sparsification algorithms to a reasonable extent.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n*Originality*:\nThe originality of the paper is somewhat unclear to me, as I am not especially familiar with the latest techniques for neural network compression. To the best of my knowledge, I am not aware of previous works that allow setting a desired number of used parameters (rather than setting a Lagrange hyperparameter). In this regard, the paper presents a somewhat original method.\n\nThe authors also present a number of additional aspects, which includes a ‘dual restart heuristic’ and techniques for applying regularization to residual networks. These are mildly original, but I do not see them as a core contribution to the paper’s novelty.\n\n*Quality*: \nThe paper is fairly high quality. The contributions of the paper are clearly defined. The diagrams clearly demonstrate the main benefit: being able to trace out the curve of parameters vs. performance in a more targeted manner. Experiments with multiple model architectures and datasets demonstrate the method, along with analysis plots in Figures 2 and 3.\n\n*Clarity*:\nThe paper is very clear in its presentation. The writing is clear, containing emphases on important words and ideas. Mathematical concepts are generally presented and explained clearly. Experiments clearly demonstrate the settings described in the paper. The figures are all well-presented, with clear legends and labels.\n\n*Significance*:\nAssuming that the paper is at least moderately original, then I see the results as being at least somewhat significant.\n\nIn particular, in Table 2, the authors demonstrate that their method is able to train models that contain similar numbers of parameters as magnitude pruning while obtaining significantly improved validation accuracy (in some cases as 70% difference). In fairness, it would be reasonable to also compare with smaller models trained without weight regularization, as well as models that are optimized post-training. Thus, the significance may be somewhat diminished after these additional comparisons.\n\nAgain, assuming the technique has not been introduced previously, the notion of being able to pre-specify the size of the model could be useful, e.g., to ensure that the final model fits within memory on a smaller device.\n\nThe authors also claim that their method, along with several additional techniques discussed in Section 5.1, is able to train $L_0$-regularized residual networks, whereas, supposedly, standard $L_0$-regularization struggles in these settings. I am not familiar with this literature, so it’s somewhat unclear to me, but I see this as a further significant contribution. Many large-scale vision models contain residual components, and this set of techniques opens up the applicability of $L_0$-regularization to these networks.\n\n**Weaknesses**\n\n*Originality*:\nThe main contribution of the paper is to replace the $L_0$-regularized training objective with a constrained objective, adjusting the Lagrange factor to satisfy this constraint. While I’m generally in support of simple methods, this method is so simple as to make me question whether something similar hasn’t already been tried before. Replacing regularized objectives with their constrained counterparts is a common, classic technique within the machine learning literature. Some examples with modern deep networks can be found in variational autoencoders ([Rezende & Viola, 2018](https://arxiv.org/abs/1810.00597)) and policy regularization in reinforcement learning ([Haarnoja et al., 2018](https://arxiv.org/abs/1812.05905)). Given that this method is seemingly *so* simple, in my view, it should provide highly significant or surprising results to warrant publication.\n\n*Quality*: \nThe quality of the paper is generally great, however, I have the following concerns:\n\nIt’s not clear whether post-training sparsification would obviate the issues with penalty-based regularization raised by the authors. That is, one could distill a larger, trained model into a smaller model of pre-specified size. In the introduction, the authors point to the additional computational overhead required by these methods, however, I do not find this to be the most compelling point. Additional discussion or empirical evaluation around this area would help to strengthen the authors’ claims.\n\nExperiments are performed entirely within the setting of supervised learning for image classification. While it’s understandable to demonstrate a method with practical applications in domains that are commonly used in-practice, I worry that this limits the scope of the paper. A more complete paper would demonstrate this method in a range of settings (e.g., within various networks for generative modeling or reinforcement learning). Given the seeming simplicity of the method, it’s unclear why the authors did not demonstrate this technique more broadly.\n\n*Clarity*:\nI do not see any major weaknesses in the clarity of the paper. The main ideas are presented well.\n\n*Significance*:\nThe significance of this paper may be somewhat limited.\n\nAs noted above, it may be the case that post-training sparsification methods would already provide a solution for obtaining a sparse network with a particular number of parameters. If this is the case, then the fact that this method is capable of doing so during training seems less consequential.\n\nAlso as mentioned above, the paper currently only contains empirical evaluations with supervised learning on image datasets. Expanding this to include other data modalities and tasks would expand the appeal of the paper.\n\nThe main selling-point of the paper is the ability to pre-specify the number of active parameters in the final, trained model. That is, one no longer has to manually adjust regularization penalty hyper-parameters during training. While I somewhat believe the appeal of this idea, in practice, I’m not sure whether this would actually save one from having to perform hyper-parameter tuning. The notion of having to pre-specify the density of active parameters (particularly per layer) is not so conceptually distinct from specifying the size (depth and width) of the network itself. Given that we generally sweep over these parameters, I do not see replacing a regularization penalty with a constraint to be a huge win here. Admittedly, this method allows one to set a global constraint, which is ideal compared with setting per-layer constraints / sizes.\n\nThe experiments in Table 2 (training ResNet50 on ImageNet) are fairly significant in terms of improvements in error. However, given the additional proposed techniques, I wonder whether a penalty-based regularization approach would perform similarly. If this is the case, then the only remaining benefit is the ease of tuning.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0szII-No7c2", "reviewer": "Reviewer_ep34", "summary": "This paper considers sparse neural network training with cardinality constraints instead of regularization. Based on the stochastic gates, they adopted a constrained formulation, which allows for simultaneously training and controlling exact sparsity in an end-to-end fashion. In terms of optimization algorithm, they considered the Lagrangian min-max problem and proposed gradient-descent-ascent algorithm with dual restarts. They conducted extensive and comprehensive numerical experiments on various network models, and demonstrated the effectiveness of their proposal.", "questions": "See \"Strengths And Weaknesses\"", "limitations": "See \"Strengths And Weaknesses\"", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proposes an end-to-end training framework for neural network training with exact sparsity constraint, which avoids tuning the sparsity-inducing regularization coefficients to satisfy the desired sparsity. They extended the previous work on stochastic gates (Louizos et al., 2018) to the constrained version, and solve it by gradient descent ascent on its Lagrangian. The paper is well written and comprehensive. Their extensive numerical experiments are sound and demonstrate their method consistently help achieve the sparsity targets for various models. In general, the paper is solid and good.\nHere are some comments/questions:\n\n1. Line 91-94: the introduction of $\\phi$ is a bit abrupt and may not be friendly to those who have not read the previous work Louizos et al. 2018. It is probably better to describe the idea of Louizos’ paper, and provide explicit expression of $\\lambda_{\\text{pen}}\\mathbb{E}_{\\bf{z}|\\phi}[\\|z\\|_0]$ wrt $\\phi$. \n2. The $L_0$-density throughout the paper (in experiment section, figures and tables): is it the “smoothed” version $g_{\\text{const}}(\\phi_g)$ (the LHS of the constraint) or the density based on test-time model? It is sort of confusing. At first, I thought it was the actual parameter density of the final purged model. So, it is probably better to clarify/define the term somewhere.\n\n3. Question related to test-time and purging: each $\\mathbb{E}_{\\bf{z}|\\phi}[1\\{z_i\\neq 0\\}]$ is a number between $[0,1]$. This means even $g (\\phi_g)\\leq \\epsilon_g$ holds, there are still chances that the $z$ in the test-time model has a larger density compared to $\\epsilon_g$. But why the Params(%) is in general smaller than $L_0$-density in Table 2?\n4. Question related to $L_0$-density: in the left panel of Figure 3, the curves of $L_0$-density do not meet the target sparsity level?  Any intuition why that happens?\n5. As a following work of Louizos et al. 2018, Yutaro et al. 2020 [1] mentioned the logistic-based hard-concrete distribution (also used in this paper) “yields high-variance gradient estimates”, and they proposed to use Gaussian distribution to replace the HC distribution for $z$. It would be interesting to check if Gaussian distribution works better in your case.\n\n[1] Yamada, Yutaro, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. \"Feature selection using stochastic gates.\" In International Conference on Machine Learning, pp. 10648-10659. PMLR, 2020.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept