Training Structured Neural Networks Through Manifold Identification and Variance Reduction
Authors: Zih-Syuan Huang
Ching-pei Lee
Venue: ICLR 2022 Poster (2022)
Keywords: Structured neural networks
variance reduction
manifold identification
proximal methods

Abstract: This paper proposes an algorithm, RMDA, for training neural networks (NNs) with a regularization term for promoting desired structures. RMDA does not incur computation additional to proximal SGD with momentum, and achieves variance reduction without requiring the objective function to be of the finite-sum form. Through the tool of manifold identification from nonlinear optimization, we prove that after a finite number of iterations, all iterates of RMDA possess a desired structure identical to that induced by the regularizer at the stationary point of asymptotic convergence, even in the presence of engineering tricks like data augmentation that complicate the training process. Experiments on training NNs with structured sparsity confirm that variance reduction is necessary for such an identification, and show that RMDA thus significantly outperforms existing methods for this task. For unstructured sparsity, RMDA also outperforms a state-of-the-art pruning method, validating the benefits of training structured NNs through regularization. 
Implementation of RMDA is available at https://www.github.com/zihsyuan1214/rmda.

TRAINING STRUCTURED NEURAL NETWORKS THROUGH MANIFOLD IDENTIFICATION AND VARI- ANCE REDUCTION
Zih-Syuan Huang
Ching-pei Lee Academia Sinica Leechinggei@@mail..com
Academia Sinica
zihsyuan@stat sini ca.nic..ee edu. tw
ABSTRACT
This paper proposes an algorithm, RMDA, for training neural networks (NNs) with a regularization term for promoting desired structures. RMDA does not incur computation additional to proximal SGD with momentum, and achieves variance reduction without requiring the objective function to be of the finite-sum form. Through the tool of manifold identification from nonlinear optimization, we prove that after a finite number of iter- ations, all iterates of RMDA possess a desired structure identical to that induced by the regularizer at the stationary point of asymptotic conver- gence, even in the presence of engineering tricks like data augmentation that complicate the training process. Experiments on training NNNs with structured sparsity confirm that variance reduction is necossary for such an identification, and show that RMDA thus significantly outperforms existing methods for this task. For unstructured sparsity, RMDA also outperforms a shate-offthe-art pruning method, validating the benefits of training struc tured NNs through regularization. Implementation of RMDA is available at https://wwit http://ww..tthhbbb.g com/ htm/zihsyuunn222 1214/rmda.
1 INTRODUCTION
Training neural networks (NNs) with regularization to obtain a certain desired structure such as structured sparsity or discrete-valued paramcters is problem of increasing interest. Existing approaches either use stochastic subgradients of the regularized objective (Wen (el. al. 2016 2018) or combine popular stochastic gradient. algorithms for NNs, like SGD with momentum (MSGD) or Adam (Kingina & Ba 2015), with the proximal operator associated with the regularizer to conduct proximal stochastic gradient updates to obtain a model with preferred structures (Bai et al. 2019 Yang et al. 2019 Yun et al. 2021 Deleu & Bengio 2021). Such methods come with proven convergence for cortain measures of first-order optimality and have shown some empirical success in applications. However, notice that an essential theoretical support lacking in existing methods is the guarantee for the output iterate to possess the same structure as that at the point of convergence. More specifically, often the imposed regularization is only known to induce a desired structure exactly optimal or stationary points of the underlying optimization problem (see for example, Zhhoo & Yu, 2006), but training algorithms are only able to generate iterates asymptotically converging
a stationary point. Without further theoretical guarantees, it is unknown whether the output iterate, which is just an approximation of the stationary point, still has the same structure. For example, let us assune that sparsity is desired, the point of convergence is x² = (1, 0),, and two algorithms respectively produce iterates and {a = (1+ 0))).. Clearly, both iterate sequences converge to
{y' = -1,t-1,t-)) x², but only of has the same desired structure as its limit point x", while y is not useful for sparsity despite that the point of convergence is. This work aims at filling this gap to propose algorithm for training structured NNs that can provably make all its iterates after

---

finite number of iterations possess the desired structure of the stationary point to which the iterates converge. We term the structure at a stationary point a stationary structure, and it should be understood that for multiple stationary points, each might correspond to a different stationary structure, and we aim at identifying the one at the limit point of the iterates of algorithm, instead of selecting the optimal one among all stationary structures. Although finding the structure at an inferior stationary point might seem not very meaningful, another reason for studying this identification property is that for the same point of convergence, the structure at the limit point is the most preferable onc. Consider the same example above, we note that for any sequence {x*} converging to x², z # for all L large enough, for otherwise x' does not converge to x². Therefore, x² cannol be sparser than x" if xt + x Identifying the structure of the point of convergence thus also amounts to finding the locally most ideal structure under the same convergence premise.
It is well-known in the literature of nonlinear optimization that generating iterates consis- tently possessing the structure at the stationary point of convergence is possible if all points with the same structure near the stationary point can be presented locally as a manifold along which the regularizer is smooth. This manifold is often termed as the active manifold (relative to the given stationary point), and the task of generating iterates staying in the active manifold iveative to the point of convergence after finite iterations is called manifold
identifical ion [Lwiis] 2002 Hare & Lewis 2004; Lewis & Zhang. 2013). To identify the ac- tive manifold of a stationary point, we need the regularizer to be partly smooth (Lewis) 2002 Hare & Lewis (004) at that point, roughly meaning that the regularizer is smooth along the active manifold around the point, while the change in its value is drastic along directions leaving the manifold. A more technical dcfinition will be given in /Section 3 Fortunately, most regularizers used in machine learning are partly smooth, so stationary structure iden-
lification is possible, and various deterministic algorit are known to achieve so (Hare
& Lewis 2007 Hare 2011 Wright. 2012 Liang el al., 2017a b Li et al. 2020
Lee 2020
Bareilles et al. 2020
On the other hand, for stochastic gradient-related methods to identify a stationary struc- ture, existing theory suggests that the variance of the gradient estimation needs to vanish as the iterates approach a stationary point (Poon et al. 2018), and indcod, it is observed empirically that proximal stochastic gradient descent (SGD) is incapable of manifold iden- tification due to the presence of the variance in the gradient estimation (Lee & Wright 2012 Sun el al., 2019) @ Poon al. (208)) showed that variance-reduction methods such as SVRG (Johnson & Zhang 2013 Xiao & Zhang 2014) and SAGA (Defazio el. al. 2014) that utilize the finite-sum structure of empirical risk minimization to drive the variance of their gradient estimators to zero are suitable for this task. Unfortunately, with the standard practice of data augmentation in deep learning, training of deep learning models with a reg- ularizer should be treated as the following stochastic optimization problem that minimizes the expected loss over a distribution, instead of the commonly seen finite-sum form:
min WEE
F F(W) = BE-D [5g (W)) + & (W),
(1)
where & is a Euclidean space with inner product (: and the associated norm I1-11, D is distribution over a space Ω, fe is differentiable almost everywhere for all & E S, and (W) is a regularizer that might be nondifferentiable. We will also use the notation f(W)= ==
[ewd[fe Without a finite-sum structure in Defazio & Bottou 2019 pointed out that classical reructio--oductioon methods are incftective for deep learning. and one major reason is the necessity of periodically evaluating V.((W) (or at least using a large batch from D to get a precise approximation of it) in veriatco-roducctoon methods is intractable, hence manifold identification and therefore finding the stationary structure becomes an extremely tough task for deep learning. Although recently there are efforts in developing variance-
reduction methods for (1) inspired by online problems (Wang et al.
2019 Nguyen et al. 2019), these methods
2021 Pham et al.) 2020 Cutkosky & Orabona 2019 Tran-Dinh et al.
all have multiple hyperparameters to tune and incur computational cost at least twice or
See a more detailed discussion in Appendix B.1
2 An exception is the interpolation case, in which the variance of plain SGD vanishes asymptot- ically. But data angmentation often fails this interpolation condition.
2

---

thrice to that of (proximal) SGD, As the training of deep learning models is time- and resource-consuminn, these drawbacks make such methods less ideal for deep learning.
To tackle these difficulties, extend the recently proposed modernized dual averaging framework (Jelassi Defazio 2020) to the regularized setting by incorporating proximal operations, and obtain new algorithm RMDA (Regularized Modernized Dual Averaging) for [1] The proposed algorithm provably achieves variance reduction beyond finitc-sum problems without any cost or hard-to-tune hyperparameters additional to those of proximal momentum SGD (proxMSGD), and we provide theoretical guarantees for its convergence and ability for manifold identification. The key difference between RMDA and the original regularized dual averaging (RDA) of [iio]] (2010) is that RMDA incorporates momentum and can achieve better performance for deep learning and the new algorithm requires nontrivial proofs for its guarantees. We further conduct experiments on training deep learning models with a regularizer for structurod-sparsity to demonstrate the ability of RMDA to identify the stationary structure without sacrificing the prediction accuracy.
terms of the generalization ability,
When the desired structure is (unstructured) spansity, popular approach is pruning that trims a given dense model to a specified level, and works like (Gale et al., 2019 Blalock et al., 2020 Evci et al. 2020: Verma & Pesquet 2021) have shown promising results. However,
wost-processing approach, pruning is essentially different from structured training considered in this work, because pruning is mainly used when model is available, while structured training combines training and structure inducing in one procedure to potentially reduce the computational cost and memory footprint when resources are scarce. We will also show in our experiment that RMDA can achieve better performance than a state-of-the-ar pruning method, suggesting that structured training indeed has its merits for obtaining sparse NNs..
The main contributions of this work are summarized as follows.
Principled analysis: We use the theory of manifold identification from nonlinear opti- mizalion to provide a unified way towards better underslanding of algorithus for training structured neural networks.
Variance reduction beyond finite-sum with low cost: RMDA achieves variance duction for problems that consist of an infinite-sum term plus a regularizer (see Lemma 2 while incorporating um to improve the generalization performance. Its spatial and computational cost is almost the same as proxMSGD, and there is no additional hyperparameters to tune, making RMDA suitable for large-scale deep learning.
Structure identification: With the help of variance reduction, theory shows that under suitable conditions, after a finite number of iterations, iterates of RMDA stay in the active manifold of its limit point.
Superior empirical performance: Experiments on neural networks with structured sparsity exemplify that RMDA can identify a stationary structure without reducing the validation accuracy, thus outperforming existing methods by achieving higher group spar- sity. Another experiment on unstructured sparsity also shows RMDA outperforms a state-of-the-art pruning method.
After this work is finished, we found a very recent paper Kungurtsev & Shikhman 2021 h that proposed the same algorithm (with slightly differences in the parameters setting in Line 5 of [Algorithm 1h and analyzed the expected convergence of (1) under a specific scheduling of ct = $14 1 when both terms are convex. In contrast, our work focuses on nonconvex deep learning problems, and especially the manifold identification aspect.
2 ALGORITHM
Details of the proposed RMDA are in Algorit At the (-th iteration with the iter- ate W we draw an independent sample & D to compute the stochastic gradient V fe, (W+-1), decide a learning rate Te, and update the weighted sum V₂ of previous stochas- lic gradients using Ve and the scaling factor Br := Vt:
Vo =0 0. V/= Σ'
B4 V (W+-1)- = Vi-1 + n.B. (WV
AE 0.
3

---

Algorithm 1: RMDA (W", T, n())
input Initial point W learning rate schedule r7(); momentum schedule c(-) number of epochs T
1 Vi 0. au tu-0 0
for 1 - l......, do
_ + vt, 9t t (t),, at t +
Sample & ~ D and compute V t + V W + arg ming (V', W) + & W - wol + (W) 2
5
// (2)
W (1 - c(()) + <())
output: The final model W
The tentative iterate T then obtained by the proximal operation associated with sh:
W = arox.,, to (Wo - -, at = Σ 3oTTe:
(2)
where for any function g, prox, (z) arg min, 1yy - x x/12/2 + glv) is its proximal operator. The iterate is then updated along the direction 777h W with a factor of a E [0,1]:
W = (1 c) W + + = w +
- -
When d = 0, RMDA reduces to the modernized dual averaging algorithm of Je assi &
Defazio (2020), in which case it has been shown that mixing W and W in 3 equals lo introducing momentum (Jelassi & Defazio 2020: Tao et al. 2018). We found that this introduction of momentum greatly improves the performance of RMDA and is therefore essential for applying it on deep learning problems.
3 ANALYSIS
We provide theoretical analysis of the proposed RMDA in this section. Our analysis shows variance reduction in RMDA and stationarity of the limit point of its iterates, but all of them revolves around our main purpose of identification of a stationary structure within finite number of iterations. The key tools for this end are partial smoothness and mani- fold identification (Hare & Lewis 2004 Lewis 2002). Our result is the currently missing cornerstone for those proximal algorithms applied to deep learning problems for identifying desired structures. In fact, it is actually well-known in convex optimization that those algo- rithms based on plain proximal stochastic gradient without variance reduction are unable to identify the active manifold, and the structure of the iterates oscillates due to the variance in the gradient estimation; see, for example, experiments and discussions in Lee & Wright (2012); Sun et. al. (2019). Our work therefore the first one to provide justification for solving the regularized optimization problem in deep learning to really identify desired structure induced by the regularizer. Throughout, V denotes the gradient of fe, Oe is the (regular) subdifferential of v, and velint(C)) means the relative interior of the set C.
We start from introducing the notion of partial smoothness.
Definition 1. A function to is partly smooth at point W relative to set Mw- W if and Mi C² 2. vb is regular (finâte with the Fréchet subdifferential coincides with the limiting Fréchet subdifferential) at all points W E Mw- around W with (e) + 0.
1. Around W*, Mw- is a C²
3. The offine spon of Ow((*) is translate of the normal space to Mw- at W*.
4. Ob is continuous at W* relative to Mw-
We often call Mw- the active manifold at W Another concept required for manifold identification is prox-regularity (Poliquin & Rockafellar 1996).
Definition 2. A function zb is prox-regular at W for V E "e(W")) if sb is finâte at W locally lower semi-continuous around W*, and there is p > 0 such that w(W,) 2 (WW)+ (V. W1- - -W2) - SIIW, - Wa whenever W,, W, are close to W with (W,) near (WW)) and V E (W2) near V to is pros-regular af W if it is so for all V E Owb(W))
4

---

To broaden the applicable range, function á prox-regular at some W is often also assumed to be subdifferentially continuous (Poliquin & Rockafellar 1996) there, meaning that W - W*, ((W*) + (WW) holds when there are V ( and sequence { {V* such that V E (W") and V - V* Notably, all convex and weakly-convex (Nurminskii 1973 functions are regular, prox-regular, and subdifferentially continuous in their domain.
3.1 THEORETICAL RESULTS
When the problem is convex, convergence guarantees for Algorithm 1 under two specific specific schemes are known. First, when G 1, RMDA reduces the classical RDA, and convergence to a global optimum (of W = W* in this case) on convex problems has been proven by Lee & Wright (2012): Duchi & Ruan (2021), with convergence rates of the expected objective or the regret given by Xiao (2010) Lee & Wrightt (2012). Second, when = 51+10 and (5,, a²) ) in Line of Algorithm are replaced by (5t+1. ar+1), convergence
recently analyzed by Kunguutsev & Shikhman (0221). In our analysis below, we do not assume convexity of either lerm.
We show that if {W:) converges to a point W* (which could be a non-stationary one), (W* also converges to W
Lemma 1. Consider Algorithm 1 with { satisfying Ea = oc. oc. If (W)) converges to a point W', {W*) also converges to W*
We then show that if {W²*} converges to a point, almost surely this point of convergence is stationary. This requires the following lemma for variance reduction of RMDA, meaning that the variance of using V, to estimate (W((t)1) reduces to zero, as a - VV, converges to ((((-1)) almost surely, and this result could be of its own interest. The first claim below uses a classical result in stochastic optimization that can be found at, for example, (Gupal knowledge, new.
1979 Theorem 4.1, Chapter 2.4), but the second one is, to hotpsstt-oootiiuuuuuyyyiiiieeeee
Lemma 2. Consider Algorithm I, Assume for any & ~ D, fe is L-Lipschittcconiinuuusly differentiable almost surely for some L, so f is also
and there is C 2 0 such that BE,ND VSe. (WI+))]l S for all t. If {m- salisfies
EBmar = 00, Σ (B <0, || - - (Benea a. 0. (4)
then of vv - (S(WC-1) with probability one. Moreover, if (W') lies in a bounded set, (W* + even if the second condition in (4) is replaced by a
we get E| E||a 'vt 'V-'''-V' Vf
weaker condition of Bono, 0
In general, the last condition in ( requires some regularity conditions in F to control the change speed of W One possibility is when v is the indicator function of a convex set, Sem x t" for t E (1/2, 1) will satisfy this condition. However, in other settings for T7, even when F and 1/ are both convex, existing analyses for the classical RDA such that = 1 in Allgriihhm still need an additional local error bound assumption to control the change of W - WT. Hence, to stay focused on our main message, we take this assumption for granted, and leave finding suitable sufficient conditions for it as future work.
With the help of Lemmas I and 2 we now show the stationarity result for the limit point of the iterates. The assumption of B,a;" approaching below classical in analyses of dual averaging in order to gradually remove the inftuence of the term ||W - -wol
Theorem 1. Consider Algorithm I with the conditions in Lemmas and 2 hold, and assume the of stationary points Z == [ 1 OF(W) is nonempty and B,a, + 0. For any given W consider the event that {W*) converges to point W (each event corresponds to a different W*), ), then if Or is outer semicontinuous at W*, and this event has a nonzero probobility, W Z, or equivalently, W is a stationory point, with probability one conditional on this event.
Finally, with Lemmas I and 2 and Theorem I we prove the main result that the active manifold of the limit point is identified in finite iterations of RMDA under nondegeneracy.
5

---

Theorem 2. Consider Algorithm 1 with the conditions in Theorem satisfied. Consider the event of [W"} converging to a certain point W as in Theorem if the probability of this event is nonzero; is proz-regular and subdifferentially continuous at W and partly smooth at W relative to the active C² manifold M; Oup is outer semicontinuous at W and the nondegeneracy condition
- -Vf(W*) E relint deb (W")
(5)
holds at W then condilional on this event, almost surely there To 2 0 such that
W E M,, Vt To-
(6)
In other words, the active manifold at W is identified by the iterates of Algorithm finite number of iterations almost surely.
after
As mentioned in Section 1 an important reason for studying manifold identification is to get the lowest- dimensional manifold representing the structure of the limit point, which often corresponds to preferred property for the application, like the highest sparsity, lowest rank, or lowest VC dimension locally. See an illustrated example Appendix B.1
APPLICATIONS IN DEEP LEARNING
We discuss two popular schemes of training structured deep learning models achieved through regularization to demonstrate the applications of RMDA. More technical details for applying our theory to the regularizers in these applications are in Appendix B
4.1 STRUCTURED SPARSITY
As modern deep NN models are often gigantic, it is sometimes desirable to trim the model to smaller when only limited resources are available. In this case, zeroing out redundant parameters during training at the group level is shown to be useful (Zhou et al. 2016), and one can utilize regularizers promoting structured sparsity for this purpose. The most famous regularizer of this kind is the group-LASSO norm (Yuan & Lin, 2006 Friedman ct al. 2010). Given 2 and a collection 9 of index sets {In} of the variable W, this convex regularizer is defined
(WW = Σ |91
g=1 W/ 1
with Wy > 0 being the pre-specified weight for Ig. For any W* let Gw- S be the index set such that WI, = 0 for all j E Gw-, the group-LASSO norm is partly smooth around W relative to the manifold Mw- == (W) Wz, 0, vi Gw-), J, our theory applies.
In order to promote structured sparsity, we need carefully design the grouping. For- tunately, in NNs, the parameters can be grouped naturally (Wen et al. 2016). For any fully-connected layer, let E goutxin be the matrix representation of the associated pa- rameters, where out is the number of output neurons and in is that of input neurons, can consider the column-wise groups, defined as W.j for all j. and the row-wise groups of the form W... For a convolutional layer with W E gehtnerx xheight being the tensor form of the corresponding parameters, kernel-wise groups, defined respectively as Wagass Wi,.. and Wis...-
consider channel filter-wise, and
4.2 BINARY/DISCRETH NEURAL NETWORKS
Making the parameters of NN binary integers is another way to obtain more compact model during training and deployment (Hubara et al. 2016), but discrete optimization is hard scale-up. Using a vector representation
m of the variables, Hou thus proposed to use the indicator function of {w wr, a; 0, E (#1]4 211 to
(017))
induce the entries of w to be binary without resorting to discrete optimization tools, where each I, cnumerates all parameters in the i-th layer. YYnng al. (2019) later proposed use
min.c E (as(w; 1)2 (1 as)(w: 1)2) the regularizer and to include

---

variable to train. At any a' with Io == fi af = 0} and 1 == [il = the objective is partly smooth relative to the manifold {(W,a) a مt = 0, = =}. Extension to discrete
NNs beyond the binary ones is possible, and Bai et al. (2019) have proposed regularizers with closed-form proximal operators for it.
EXPERIMENTS
We use the structured sparsity application in Section 4.1 to empirically exemplify the ability of RMDA to find desired structures in the trained NNs. RMDA and the following methods for structured sparsity in deep learning are compared using PyTorch (Paszke al.) 2019).
ProxSGD (Yang et al. 2019): A simple ProxMSGD algorithm. To obtain group sparsity, we skip the interpolating step in Yang et al. (2019)
ProxSSI (Deleu & Bengio, 2021] This is a special case of the adaplive proximal SGD algorithm to approximately solve the subproblem. We directly use the package released by the authors.
framework Yun et al. [201]] that uses the Newlon-Raphese
We exclude the algorithm Wen al. (0066) because their method is shown to be worse than ProxSSI by Deleu & Bengio (2021].
To compare these algorithms, we examine both the validation accuracy and the group spar- sity level of their trained models. We compute the group sparsity as the percentage of groups whose elements are all zero, so the reported group sparsity is zero when there is no group with a zero norm, and is one when the whole model is zero. For all methods above, we use ( with column-wise and channel-wise groupings in the regularization for training, but adopt the kernel-wise grouping in their group sparsity evaluation. Throughout the ex- periments, we always use multi-step learning rate schoduling that decays the learning rate by constant factor every time the epoch count reaches pre-specified threshold. For all methods, we conduct grid searches to find the best hyperparameters. All results shown in tables in [Sections 5.1 and 5.2 are the mean and standard deviation of three independent runs with the same arperparameters, while figures usee one representative run for better visualization.
In convex optimization, a popular way to improve the practical convergence behavior for momentum-based methods is restarting that periodically roset the momentum to zero O'doonoguue & Candes] 2015). Following this idea, we introduce a restart heuristic to RMDA. At each round, new input to the same algorithm, and continue using the scheduling v and e without reset- ting them. For so = 0, Jelassi & Defazio (2020) suggested increase et proportional decrease of until reaching C = 1. We adopt the same setting for and N and restart RMDA whenever 7) changes. As shown /Scction 3 that W finds the active manifold, increasing to 1 also accords with our interest in identifying the stationary structure.
the output of Algorithm I from the previous round as the
the
5.1
CORRECTNESS OF IDENTIFIED STRUCTURE USING SYNTHETIC DATA
Sparsity Corectress
100%
1.00%
Spersity Corectrest
1.00%
100%
Error
RMDA Isparsity correctness)
Prox5Si Isparsity correctress)
50%
50%
Prox5GD (sparsity correctress!
53%
50%
25%
25%
ProxSSi itraiiigg
RMDA (training error)
25%
25%
Prox5G3 (training emror)
200
400
300
200
Epochs
Epochs
(a) Logistic regression
(b) Legend
(c) Convolutional network
Figure 1: Group sparsity pattern correctness and training error rates on synthetic data.
Our first step is to numerically verify that RMDA can indeed identify the stationary structure desired. To exactly find a stationary point and its structure a priori, we consider syuthotic problems. We first decide ground truth model W that is structured sparse, generate random data points that can be well separated by W, and then decide their labels using W. The generated data then taken our training data. We consider linear logistic
7

---

regression model and small NN that has fully-connectedd layer and one convolutional layer. To ensure convergence to the ground truth, for logistic regression we generate more data points than the problem dimension to ensure the problem is strongly convex that there is only one stationary piationary/optiial /optimal point, and for the small NN, we initialize all algorithms close enough to the ground truth. We report in Fig. training for the proximity to the ground truth) and percentages of the optimal group sparsity pattern of the ground truth identified. Clearly, although all methods converge the ground truth, only RMDA identifies the correct structure of it, and other methods without guarantees for manifold identification fail.
rates (as an indicator
5.2 NEURAL NETWORKS WITH REAL DATA
Table 1: Group sparsity and validation accuracy of different methods. We report mean and standard deviation of three independent runs (except that for the linear convex model, only one is conducted with no sparsity-inducing regularizer.
guaranteed to find the global optima). MSGD is the baseline
Algorithm
Validation accuracy
Group sparsity
Validation accuracy
Group sparsity
Logist.cc regression /NIIST
Fully-connected NN M/ISS
ProxSGD
91.31 7
38. 78
88.72 0.05%
31.42
0.36%
ProxSSI
91.31
39.54
88.44 0.41%
35.25
1.56%
RMDA
91.34 %
56.51 %
88.09 - 0.04%
42.89 + 0.66%
LeNet5 (0fet5/MMISTT MNIST
LeNet5 LeNet5/Fashion MNIST
MSGD
99.36 + 0.06%
91.96 + 0.01%
ProxSGD
99.13 + 0.02%
76.57 + 2.33%
90.99 + 0.17%
50.50 + 2.66%
ProxSSI
99.07 + 0.03%
77.82 + 1.56%
90.93
0.02%
60.49 + 1.05%
RMDA
99.10 0.06%
79.81
1.56%
91.41 0.10%
66.15
1.68%
VGG19/CIFARR
VGG19/CIFAAR
MSGD
94.03 + 0.11%
74.62 0.22%
ProxSGD
92.38 - 0.31%
72.57
6.04%
71.91 0.08%
08.63
4.88%
ProxSSI
92.51 0.03%
$1.05
0.16%
66.20 0.38%
46.41
1.42%
RMDA
93.62 Σ 0.15%
86.37
0.25%
72.23 1 0.20%
58.86
0.41%
ResNet50
C.NeL50/CIFAR10
ResNet50/CIFAR1000
MSGD
95.65 0.03%
79.13 0.19%
ProxSGD
92.36 = 0.14%
76.82 + 4.09%
75.53 + 0.49%
51.83 + 0.34%
ProxSSI
94.09 = 0.08%
74.81 + 1.28%
74.52 + 0.29%
32.79 + 2.53% 57.67 + 3.76%
RMDA
94.25 = 0.02%
83.01 - 0.50%
76.12 0.46%
We turn to real-world data used in modern computer vision problems. We consider two rather simple models and six more complicated modern CNN cases. The two simpler models are linear logistic regression with the MNIST dataset (LeCun et al. 1998), and training small NN with seven fully-connected layers on the FashionMNIST dataset (iiao et al. 2017: The six
complicated cases 1. A version of LeNet5 with the MNIST dataset,
2. The same version of LcNet5 with the FashionMNIST datasot,
3. A modificd VGG19 (Simonyan & Zisserman 2015 with the CIFAR10 datasct
[Krizhevsky/ 2009
4. The samne modilied VGG19 with the CIFAR100 dataset Krizhevsky 2009
5. ResNet50 (He el al.) 2016 with the CIFARI0 datasel, and
6. ResNet50 with the CIFAR100 dataset.
For these six more complicated tasks, we include a dense baseline of MSGD with no sparsity- inducing regularizer in our comparison. For all training algorithms on VGG19 and ResNet50, we follow the standard practice in modern vision tasks to apply data augmentation through random cropping and horizontal flipping so that the training problem is no longer a finite- sum one. From Fig. 2. we see that similar to the previous experiment, the group sparsity level of RMDA is stable in the last epochs, while that of ProxGGD and ProxSSI oscillates below. This suggests that RMDA is the only method that, proven in Section identifies the structured sparsity at its limit point, and other methods with no variance reduction fail. Moreover, Table shows that manifold idlettiiiation of RMDA is achieved with
8

---

1.0
Logistic Regression MINIST
LeNett MINIST
VO01 CITAR10
0.85
RedMento CIPARTO
StnutLne Sparsky
Sparsdo
0.B.
RNCA
C.00
0.50
FAPEA
6.7
0.75
470
643
053
100
450
170
6.00
040
650
500
600
920
940
360
950
1000
0.70
100
1420
1400
1660
1400
1500
Epcctt
Spocta
Spechs
Spocto
Fullyecommetten
on Pas
VGGLS on CIFARLOO
Beshet50 CIFAR10O
Prudd
0.55
Pradd
800
1400
Eppctss
Epects
Sportts
Cpochic
Figure 2: Group Sparsity v.s epochs of different algorithms on NNs of single run.
sacrifice of the validation accuracy, so RMDA beats ProxSGD and ProxSSI in both criteria, and its accuracy is close to that of the dense bascline of MSGD. Morcover, for VGG19 and ResNet55, RMDA succeeds finding the optimal structured sparsity pattern despite the presence of data augmentation showing that RMDA can indeed overcome the difficulty from the infinite-sum setting of modern deep learning lasks.
We also report that in the ResNet50/ PrsNNe55/CIFAARO0 CIFAR100 task, our NVIDIA RIX 8000 GPU, MSGD, ProxSGD, and RMDA have similar per-epoch cost of 68, 77, and 91 seconds respec- tively, while ProxSSI needs 674 seconds per epoch. RMDA is thus also more suitable for largo-scale structured deep lcarning in terms of practical efficiency.
5.3 COMPARISON WITH PRUNING
We compare RMDA with state-of-the-art pruning method RigL EEvc et al. 2020 As pruning focuses on unstructured sparsity, we use RMDA with v(W) W|| to have a fair comparison, and tune À achieve pre-specified sparsity level. We run RigL with 1000 epochs, as its performance at the default 500 epochs was unstable, and let RMDA use the same number of epochs. Results of 98% sparsity in Table show that RMDA consistently outdoes RigL, indicating regularized training could be a promising alternative to pruning.
Table 2: Comparison between RMDA and RigL with 1000 epochs for unstructured sparsity in a single run.
5e with CIFAR10
50 with CIFAR100
Algorithm Dense bascline
Sparsity
Accuracy
Sparsity
Accuracy
94.81% %
74.61 %
RMDA RigL
98.36% 98.00%
93.78% 93.41%
98.32% 98.00%
74.32% %
70.88%
CONCLUSIONS
In this work, we proposed and analyzed a new algorithm, RMDA, for efficiently training structured neural networks with state-of-the-art performance. Even in the presence of data augmentation, RMDA can still achieve variance reduction and provably identify the desired structure stationary point using the tools of manifold identification. Experiments show that existing algorithms for the same purpose fail to find a stable stationary structure, while RMDA achieves with accuracy drop nor additional time cost..
9

---

ACKNOWLEDGEMENTS
This work was supported in part by MOST of R.O.C. grant 100-222---001--33-MM3,, and the AWS Cloud Credits for Research program of Amazon Inc.
REFERENCES
Yu Bai, Yu-Xiang Wang, and Edo Liberty. ProxQuant: Quantized neural networks via
proximal operators. In International Conference on Learning Representations, 2019.
Gilles Bareilles, Franck Tutzeler, and Jérôme Malick. Newton acceleration manifolds identified by proximal-gradient methods. Technical report, 2020. arXiv:2012.12936. 2
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state neural network pruning? Machine Learning and Systems, 2020.
Patrick Breheny and Jian Huang, Penalized methods for bi-level variable selection. Statistics and its interface, 2(3):369, 2009.
22
James V. Burke and Michael C. Ferris. Weak sharp minima in mathematical programming.
SIAM Journal on Coatrol and Optimization, 31(5):1340 1359, 1993. 19
Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction in non- convex SGD. In Advances in Neural Information Processing Systems, pp. 15236
2019. 2
Aaron Defazio and Leon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. In Aduances in Neural Information Processing Systems, pp. 1755- 2019. 2
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances neural information processing systems, pp. 1646-1654, 2014.
Tristan Deleu and Yoshua Bengio. Structured sparsity inducing adaptive optimizers for deep learning. Technical report, 2021. arXiv:2102.03869,
20 22
John C. Duchi and Feng Ruan. Asymptotic optimality in stochastic optimization. The Annals of Statistics, (9(1):21-48, 2021.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning,
pp. 2943-29010 24522 2020. 3
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. A note on the group lasso and a sparse group lasso, Technical report, 2010. 6
Trevor Gale, Erich Flsen, and Sara Hooker. The state of sparsity in deep neural net works. Technical report, 2019. arXiv:1902.0000
A.M. Gupal. Stochastic methods for solving nonsmooth extremal problems. Naukova Dumka, 1979. 5
14
Warren L. Hare. Identifying active manifolds in regularization problems. In Fized- Poinl Algorithms for Inverse Problems in Science and Engineering, pp. 261-271, Springer, 2011.
Warren I. Hare and Adrian S. Lewis. Identifying active constraints via partial smoothness and prox-regularity. Journal of Convez Analysis, 11(2):251 2266, 2004.
Warren L. Hare and Adrian S. Lewis. Identifying active manifolds. Algorithmic Operations
Research, 2(2):75 75, 2007. 2
10

---

Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE conference on computer vision and pottern recognition, pp. 770-778,
2016. 8 20
Lu Hou, Quanming Yao, and James T Kwok. Loss-aware binarization of deep networks. In International Conference on Learning Representations, 2017.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q- Weinberger. Denscly connected convolutional networks. In IEEE conference on computer vision and pattern
recognilion,, pp. 4700 4708, 2017. 20
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua. Bengio. Binarized neural networks. Advances in neural information processing systems, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp- 448-456, 2015.
20
Samy Jelassi and Aaron Defazio. Dual averaging is surprisingly effective for deep learning optimization. Technical report, 2020. arXiv:2010.10502
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, pp. 315 313-323, 2013. 2
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. D
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009. H
Vyachoslav Kungurtsev and Vladimir Shikhman. Regularized quasi-monotone method for stochastic optimization. Technical report, 2021. 1rXiv:2107.03779 3
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
Ching-pei Lee. Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification. Technical report, 2020. 2xXiv22012.02221
Sangkyun Lee and Stephen J. Wright. Manifold identification in dual averaging for regu- larized stochastic online learning. Journal of Machine Learning Research, 13:1705 1744,
2012. 2 5
Adrian S. Lewis. Active sets, nonsmoothness, and sensitivity. SIAM Journal on Optimiza- lion, 13(3):702-P7) 725, 2002.
4
Adrian S. Lewis and Shanshan Zhang. Partial smoothness, tilt stability, and gencralized hessians. 2344)974 2013. 2
Yu-Sheng Li, Wei-Lin Chiang, and Ching-per Lee. Manifold identification for ultimately communicttion-effiieee distributed optimization. In International Conference Ma- chine Learning, 2020. 2
Jingwei Liang, Jalal Fadili, and Gabriel Peyré. Activity identification and local linear con- vergence of forward backward-type methods. 27(1):408 437, 2017a. 2
Jingwei Liang, Jalal Fadili, and Gabriel Peyré. Local convergence properties of douglas- rachford and alternating direction method of multipliers. Journal of Optimization Theory and Applications, 177 913, 2017b.
Lam M. Nguyen, Katya Scheinberg, and Martin Takáč. Inexact SARAH algorithm for stochastic optimization. Oplimization Methods and Software, 36(1):237 -25,, 2021. 2
11

---

Evgeni Alekscevich Nurminskii. The quasigradient method for the solving of the nonlinear programming problems. Cybernetics, 0(1):145-150, 1973. 5
Brendan O'donoghue and Emmamuel Candes. Adaptive restart for accelerated gradient schemes. Foundations of compulational mathemalics, 15(3):715 732, 2015.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An im- perative style, high-performance deep learning library. Advances in neural information processing systems, pp. 8026-8037 2019. 7
Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, and Quoc Tran-Dinh. ProXSARAH: An efficient algorithunic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 21:1 48, 2020. 2
René Poliquin and R Rockafellar. Prox-regular functions in variational analysis. Transac-
tions of the American Mathematical Society, 348(5):1805-1888, 1996.
Clarice Poon, Jingwei Liang, and Carola- SAGA/proX-SVER -VRG and accelcration. In International Conference on Machine Learning, 2018. 2
Carola-Bibiane Bibianc Schönlicb. Local convergence properties of
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recoguition. 2015.
Yifan Sun, Halyun Jeong, Julie Nutini, and Mark Schmidt. Are there yet? manifold iden- tification of gradient-relatee proximal mothods. In International Conference on Artificial
Intelligence and Statistics, pp. 1110-1119, 2019.
2 4
Varun Sundar and Rajat Vadiraj Dwaraknath. [reproducibilityy report] rigging the lottery:
Making all tickets winners. In ML Reproducibility Challenge 2020, 2021. 20 26
Wei Tao, Zhisong Pan, Gaowei Wu, and Qing Tao. Primal averaging: A new gradient evalu- ation step to attain the optimal individual convergence. 1EEE transactions on cybernetics, 50(2):835-844 845, 2018.
Quoc Tran-Dinh, Nhan H. Pham, Dzung T. Phan, and Lam M. Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. Technical report, 2019.
Sagar Verma and -ean-Christophe Pesquet. Sparsifying networks via subdifferential inclu- sion. In International Conference on Machine Learning, pp. 10542 10552, 2021. 3
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momen- tum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems, pp. 2406-2416, 2019. 2
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, pp. 2074 2082, 2016. 6 7
Wei Wen, Yuxiong He, Samyam Rajbhandari, Minjia Zhang, Wenhan Wang, Fang Liu, Bin Hu, Yiran Chen, and Hai Li. Learning intrinsic sparse structures within long short-term memory. In International Conference on Learning Representations, 2018. D
Stephen J. Wright. Accelerated block-coordinate relaxation for regularized optimization.
SIAM Journal on Optimization, 22(11:159 186, 2012. 2
Han Xiao, Kashif Rasul, and Roland Vollgraf. Pashion-mnise benchmarking machine learning algorithms. Technical report, 2017. arXiv:1708.0774f
novel image dataset for
Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimiza-
tion. Journal of Machine Learning Research, 11 11(88)22543 2596, 2010. 3 5
12

---

Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):20572277) 2014.
Yang Yang, Yaxiong Yuan, Avraam Chatzimichailiddis, Ruud JG van Sloun, Lei Lei, and Symeon Chatzinotas. ProxSGD: Training structured neural networks under regularization and constraints. In International Conference on Learning Representations, 2019.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series (Statistical Methodology), 68(1):49-55 67,
2006. 6
Jihun Yun, Aurélie C Lozano, and Eunho Yang. Adaptive proximal gradient methods for structured neural networks. Advances in Neural Information Processing Systems, 2021.
Cun-Hui Zhang- Nearly unbiased variable selection under minimax concave penalty. The
Annols of statistics, 38(2):894 942, 2010. 21
Pong Zhao and Bin Yu. On model selection consistency of Lasso. The Journal of Machine Learning Research, 7:2541 2563, 2006. [
Hao Zhou, Jose M. Alvarez, and Fatih Porikli. Less is more: Towards compact CNNs. In Europeon Conference on Computer Vision, pp. 677. Springer, 2016.
Appendices
Table of Contents
Proofs
13
A.1 Proof of Lemma
13
A.2 Proof of Lemma
14
A.3 Proof of Theorem
16
4 Proof of heorem
Additional Discussions on Applications
18
B.1
Structured Sparsity
18
B.2 Binary Neural Networks
20
Experiment Setting Details
20
More Results from the Experiments
20
Other Regularizers for Possibly Better Group Sparsity and General-
ization
21
A PROOFS
A.1 PROOF OF LEMMA
3 the distance between We and W can be upper bounded through the triangle incquality:
Proof. Using
| w = (1- at) =[(1-a) w*) - ca (wr - w\)
A < + (1 cz) -
(8)
13

---

For any event such that W - W for any > 0, can find T. 2 0 such that
| - w S e, Vt W21. T.
Let 8, = I W ||, we see from the above inequality and
8 that
6, S (1 a) 6 cce, 2 Te.
By deducting c from both sides, we get that
(6, s) s (1 - at) Since Ea = 0o, we further deduce that
4A Te.
lim (6, - c) - II
(1 ai) (5T,-1-6
1000
t=
exp
(-c) (6T-11
t=T,
cxp
Ct
(81--1- -c)=
t=
where in the first inequality we used the fact that exp(x) 2 1 1+a x for all real number æ. The result above then implies that
lim 6, S. E. t1000
As c is arbitrary and 5, 2 0 from the definition, we conclude that lim 6g = 0, which is equivalent to that W W*
A.2 PROOF
LEMMA
Proof. We observe that
Vt
Σ
nkBk
fex (Wi--)
at
k=1 a₁
04-1
-1
//-1
+ 01 - -0--1 fe. (W--l)
a,-1
BeT
BiT vls. (W--l).
a, pl-1
at
at
From that f is J.Liischitt--coniinuussyy differentiable, we have that.
Eg EepLID Vi (W')) - -EE V.e. (W*-1)]]l |/ (W') - (
S - -
(9)
Therefore,
4 and
9
imply that
0 B D Se (W')]
EEND Vig (Wt-1)]l
W W
a.a. 0,
Bmaa
3im
which together with the sandwich lemma shows that
BeHII [V (W+)] EE [Vie, (W+-1)]]]
0.
(10)
3mmaa
Therefore, the first two conditions of together with (10) and the bounded variance
assumption satisfy the requirements of Gupal 1979 Chapter 2.4, Theorem 4.1), so the conclusion of almost sure convergence hold.
14

---

For the convergence in L2 part, we first define m² == ' and n. 3.aa for notational ease. Consider || VF(Wt)]? we have from the update rule in Algorithm 1 that
|m - VF(W"))1
= =|(11- ((1-T))m² + TO Vee+: - VF(W3)]
[[(1 - Tx) (m' VF(W")) T (Vie+ (W VF(W*))]
nt)² |1) - >F(W")| + 7, V (W') VF(W")|²
2T, (1 Te)(m' VF(W"), Vic.. (W9) VF(W"))
(1 7))² (m(m - VVF (W (VF (W -V (W²
(11)
+ + (W") VF(W")|| + 2n, - +mm - V F F(W"), V Sec. (W VF(W"))
Let {Fi denote the natural filtration of {(m', w Namely, Fr records the informa-
tion of W [-) {nz H=) and (ši)i=ı. By defining U, = Imm - VF(W(=1) and taking
expectation over (11) conditional on Fi, obtain from E Vf (W") Fi] vF(W")
that
E U
Fil = (1 - 7:) VE VF (W*-l)) + (VF (W"-)) -F--)--V(((P (W
+ E
fe. (WV) - )|( Fi
(12)
From the last condition in (4) and the Lipschitz continuity of VF, there are random variables
{e} and {u, such that M4 1, 6, 2 0, and VF(W* VF(W)) neEue for all t 0,
with e & 0 almost surely.
We thus obtain that
m VF(W(=1) + -
= m' VF(W(-I) + u
+ T2)2
T+ (m' VF (F((t-1))
Te 1+ T
$ (1+T)) 7
{_1 Un 1 1 Ti
Tee
(13)
1 Tτ.
where we used Jensen's inequality and the convexity of 11-11 in the last inequality. By substituting (13) back into (12) we obtain
E E(U+++|
$ (1 - ) (1 + T,) + (1 - T,) 71 + TT)TE 2 + T
VF(W*))
|
$ (1 - (U, + n.²2) + - V (W*) - VF(W 1|2 [r]
$ (1 U, + T. 2 + +
2 [F]]
(14)
For the last term in 14) we notice that
E [
VF
| Fi
2 E fe. [[ + [| [
< =2(C+|VF(w*>)3)
(15)
where the last incquality is from the bounded variance assumption. Since by assumption the {W") lies in a bounded set K, we have that for any point W E K, W W is upper bounded, and thus /V((Wt) V F[ is also bounded, implying that /V(W*)) C2
for some C2 2 O. Therefore,
15
further leads to
E V.e... - -VPW>)]
|J. < Co
(16)
15

---

for some C3 2 O.
Now we further take expectation on (14) and apply (16) to obtain
BUL+1 S1 Tr EU, ni C2 (1 ni EU; + To ( (+++CCs)
(17)
Note that the third implies e + 0, so this together with the second condition that 0 means of TT C3 3/4 0 as well, and thus for any > O, we can find Ta such that of +7, S
for all 1 Ts. Thus, (17) further leads to
BU,-1 - 8 (1 Tq EU, + 7j
(1 Te) (EU, 8) V1 2 Tg.
(18)
This implies that (EUG, 5) becomes a decreasing sequence starting from t 2 T', and since U, 2 O, this sequence is lower bounded by -Ō, and hence converges to certain value. By recursion of (18) we have that
EU, - 8 II (1 T() (EUTs 8),
1=
and from the well-known inequality (1 +1+x) exp" for all R, the above result leads to
EU 8 S exp
- (EUr; 6).
By letting approach infinity and noting that the first condition of indicates
Σ
for any l: 2 0, we see that
0 Σ i=
-8 S lim EU, 5 exp
Ti
(EUT, -8) 0. (19)
As d is arbitrary, by taking ( in 199 and noting the nonnegativity of U2, we conclude that lim BU, = 0, as desired. This proves the last result in Lemna 2
A.3 PROOF OF THEOREM
Proof. Using Lemma 2 we can view a,
as V((WWt plus some noise that asymptotically Vt -v-
decreases to zero with probability one:
V VV + ex. ||e|| a 0.
(20)
We use (0 to rewrite the optimality condition of (2) as (also see Line of Algorithm 1
-(V (W*) + e, + Baa," (.* w E aub (W*).
(21)
Now we consider OF(W²). Clearly from (21) we have that
Vs (W²) - v (W') 4 - B,o (w Wo) E AV (W') + t (W') = OF (W²).
(22)
Now we consider the said event that W + W for certain W and let us define this event as C Q. From Lemma 1 we know that W W as well under A. Let us define B C Ω as the event of & + O, then we know that since P(A) > 0 and P(B) = 1, where P is the probability function for events in Q P(AnB) = P(A). Therefore, conditional on the event of A, we have that e, a.8, still holds. Now we consider any realization of AnB. For the right-hand side of (22) as W convergent and 3,a," decreases to zero, by letting approach infinity, we have that
lim 6 + Sra;"' (W* W0) = 0 ( wo) 0. 1000
By the Lipschitz continuity of V,, we have from 3 and
4) that
< V (W') v (w*)l < Z. W W/
16

---

As {W*) and {W*} converge to the same point, see that || W/ - 0. Vf (W**)
f((W)) also approaches zero. Hence, the limit of the right-hand side of (22) is
lim V (W*) (VS (W") + BeoT (W* wº) 0.
(23)
On the other hand, for the left-hand side of (22) the outer semicontinuity of dip at W and the continuity of V show that.
lim Vf(W*) (w S 0V ((W"))+++))) & (W*) = OF(W").
(24)
Substituting
(33) and 24 back into (22) then proves that OF(W*) and thus W e
Z.
A.4 PROOF OF HEOREE 2
Proof. Our discussion in this proof are all under the event that W W From the argu-
ment in Appendix A.3 we can view vv as Vf(W") plus some noise that asymptotically
decreases to zero with probability one as shown (20) From Lemma we know that
W W" From (21) there is U E Öp (WY) such that
=-= 'v= + Be -
(W"-W9
(25)
Moreover, we define
7 W - W.
(26)
By combining 25
26
with (20)
obtain
min YEOF(WF)
|
| (W+) + U
Vf (Wr) - Vf (W") - 6 - a, 3e (W - W
f (WV) -V || + a a wo
<111 + ||a.|| a, & [[ 1-
(27)
where we used the Lipschitz continuity of V and the triangle inequality in the last inequal- ily.
We now separately bound the terms in 27 From that W - W and W - W it is straightforward that lh
The second term decreases zero almost surely according to (20) and the argument in Appendix A.3 For the last term, since a O, we know that
B, + 0, and
aj & - w'Il + 0, af B W' + 0.
Therefore, we conclude from the above argument and (27) that
min YEAF(W1)
| s.s. 0.
As f is smooth with probability one, we know that if & is partly smooth at W* relative to M, then so is f & with probability one. Moreover, hipschitz-continuuusyy differentiable functions are always prox-regular, and the sum of two prox-regular functions is still prox- regular, so is also prox-regular at W with probability one. Following the argument identical to that in Appendix A.3 we know that these probability one events still probability one conditional on the event of W > W* as this event has a nonzero probability. As W + W* and VS(W") + L n.s, 0 E OF(W*) (the inclusion is from the subdifferential continuity of vh and the smoothness of f that F(W")
(5) we have from
F(W*). Since
also have W + W* and minyeor(W")) ||Y|| an 0, clearly
W F (W*). min YEOF(W:)
a.s. WW",F(W").00 ||||]
(28)
Therefore, (28) and 5 together with the assumptions on ii at W imply that with proba- bility one, all conditions of Lemma 1 of Lee (2020) are satisfied, from it, (6) holds almost surely, conditional on the event of T W*
17

---

B ADDITIONAL DISCUSSIONS ON APPLICATIONS
We now discuss in more technical details the applications Section 4.1 especially regarding how the regularizers satisfy the properties required by our theory.
B.1 STRUCTURED SPARSITY
We start our discussion with the simple & norm as the warm-up for the group-LASSO norm. It is clear that [|W]|, is convex function that is finite everywhere, so it is prox-regular, subdifferentially continuous, and regular everywhere, hence we just need to discuss about the remaining parts in Definition I Consider problem with dimension n > 0. Note that
| = Σ Iaab
and the absolute value is smooth everywhere except the point of origin. Therefore, it is clear that ||=||] locally smooth if x4 + for all For any point x², when there is an index set I such that rf = 0 for all i I and x; & 0 for & I, we see that the part of the norm corresponds to l (the complement of T):
Σ a
locally smooth around x², Without loss of generality, we assume that I 2 (1.2....,A k} for some k 2 0, then the subdifferential of || at x² is the set
(sgn(x1)) x x... x {sgn(ax)) [-1,1]"--
(29)
and clearly we move from x" along any direction y == (y1...., yk. 0,. .,....0) 0) with a small step, the function value changes smoothly as it is a lincar function, satisfying the first condition of Definition I Along the same direction y with a small enough step, the set of subdifferential remains the same, so the continuity of subdifferential requirement holds. We can also observe from the above argument that the manifold should be MM = fr I, 0, vi E I}. and clearly it is subspace of R" with its normal space at x=' being N fy (x", y) = 0} - (y 91 = Vi E 19), which is clearly the affine span of (29) with the translation being (sgn(x1) x.... 0g ..,.)) 0). Moreover, indeed the manifolds are low dimensional ones, and for iterates approaching x", staying in this active manifold means that the (unstructured) sparsity of the iterates is the same the limit point x". We also provide a graphical illustration of ||>|| with n = 2 in Fig. 3 We can observe that for any with 21 A and 22 # 0, the function is smooth locally around any point, meaning that ||ق|| is partly smooth relative to the whole space at x (so actually smooth locally around r). For with Ii = 0, the function value corresponds to the sharp valley in the graph, and we can see that the function is smooth along the valley, and this valley corresponds to the one-dimensional manifold {u x1 = 0} for partial smoothness.
Next, we use the same graph to illustrate the importance of manifold identification. Consider that the red point x* = (0, 1.5) is the limit point of the iterates of a certain algorithm, and the yellow points and black points are two sequences that both converge to x=. If the iterates of the algorithm are the black points, then clearly except for the limit point itself, all iterates are nonsparse, and thus the final output of the algorithm is also nonsparse unless to exactly the limit point within finite iterations (which is usually impossible for iterative methods). On the other hand, if the iterates are the yellow points, this is the case that the manifold is identified, because all points sit in the valley and enjoy the same sparsity pattern as the limit point x² This is why we concern about manifold identification when we solve regularized optimization problems.
can get
From this example, we can also see an explanation for why our algorithm with the property of manifold identification performs better than other methods without such a property. Consider a Fuclidean space any point x² with an index set such that x = 0 and |7| > 0. This means that x² has at least one coordinate being zero, namely x² contains sparsity. Now let.
en = min
ee
18

---

1.5
1.5
-0.5
X
Figure 3: An illustration of partial smoothness of the l norm.
then from the definition of I, co > O. Fro any sequence (x²) converging s", for any é E (0,, we can find T, 2 0 such that
||= -=== - S. T.
Therefore, for any i & I, must have that x/ * for all t 2 T. Otherwise, || x" 20112 ED. but co > 6 2 ||," x= l1g. leading to a contradiction. On the other hand, for any E I, we can have x # 0 for all without violating the convergence. That being said, for any sequence converging to x², eventually the iterates cannot be sparser than x", so the sparsity level of xx, of its active manifold, the local upper bound for the sparsity level of points converging to x². Therefore, if iterates of two algorithms converge to the same limit point, the one with a proven manifold identification ability clearly will produce higher sparsity level.
Similar to our example here, applications other than sparsity, itcrates converging to limit point dwell on super-manifolds of the active manifold, and the active manifold is the minimum one that locally describes points with the same structure as the limit point, and thus identifying this manifold is equivalent to finding the locally most ideal structure of the application.
Now back to the sparsity case. One possible concern is the case that the limit point is (0. in the two-dimension example. In this case, the manifold is the O-dimensional subspace (0). If this is the case and manifold identification can be ensured, it means that limit point itself can be found within finite iterations. This case is known as the weak sharp minima (Burke & Ferris 1993) in nonlincar optimization, and its associated finite termination property is also stuuist
For this example, We also that ||<]] is partly smooth at any point x", but the manifold differs with x². This is a specific benign example, and in other cases, partial smoothness might happen only locally some points of interest instead of everywhere.
Next, we further extend our argument above to the case of (7) This can be viewed as the E norm for each group and we can easily obtain similar results. Again, since the group-LASSO norm is also convex and finite everywhere, prox-regularity, regularity, and subdifferential continuity are not issues all. For the other properties, we consider one group first, then the group-LASSO norm reduces to the l norm. Clearly, ||ж|| is smooth locally if æ * O, with the gradient. being æ/ </||>/]2 but is nonsmooth at the point x 0, where the subdifferential is the unit ball. This is very similar to the absolute value, whose subdifferential at is the interval [-1, Thus, we can directly apply similar arguments above, and conclude that for any W*. (7) is partly smooth at W with respect to the manifold Mw- = {W Wz, = 0,Vg W = 0), which is again a lower-dimensionall subspace. Therefore, the manifold of defining the partial smoothness for the group-LASSO norm exactly corresponds to its structured sparsity pattern.
19

---

B.2 BINARY NEURAL NETWORKS
We continue to consider the binary neural network problem. For casier description, for the Euclidean space & consider, will vectorized representation for W, E & such that the elements are enumerated as .,,..., W, and on....,, :0.. The corresponding optimization problem can therefore be written as
BEWD [se (W) Σ (ai(ws (wi + 1)² + (1 a:) (w; 1)² + 610.11 (as)).
min W,AEE
(30)
where given any set C, dc is the indicator function of C, defined as
6c(x) =ff {o else.
x E
We see that except for the indicator function part, the objective is smooth, the real partly smooth torm that we treat as the rogularizer is
n
((a) = Σ )j.))(a.).
We note that for O₁ E (0, 1), the value of (0.1)(a;)) remains a constant zero in a neighbor-
hood of a; and for a; & [0, 1], the indicator function is also constantly infinite within neighborhood. Thus, the point of nonsmoothness, happens only at a, {0. 1), and similar to our discussion in the previous subsection, & partly smooth along directions that we fix those og the boundary (namely, being either or 1) unchanged. The identified manifold therefore corresponds to the entries of as that are fixed at O or 1, and this can serve as the indicator for the desired binary pattern in this task.
C EXPERIMENT SETTING DETAILS
For the weights Wi of each group in for all experiments in Section 5) we follow Deleu & Bengio 2021] 1) to set W,, = IZyl- All ProxSSI parameter settings, excluding the regulariza- tion weight and the learning rate schedule, follow the default values in their package.
Tables to 13 provide detailed settings of [Section 5.2 For the modified VGG19 model, we follow Deleu & Bengio (202T) to eliminate all fully yclnnneeed layers except the output layer, and add one natch-norm layer (Lotfe & Szegedy 2015) after each convolutional layer to simulate modern CNNs like those proposed in He et al. (2016); Huang et al. (2017). For ResNet50 in the structured sparsity experiment. in [Section 5.2 version of ResNet50 is the one constructed by the publicly available script at htthhtps:// githhb........ com/weiaicunzal pytorch-cifari00
In the unstructured sparsily experiment presented in Section 5.3 for better comparison with existing works in the literature of pruning, we adopt the version of ResNet.50 used by Sundar & Dwaraknath (2021) Table 14 provides detailed settings Section 5.3, For RigL, we use the PyTorrh implementation Sundar & Dwaraknath (2021)
D MORE RESULTS FROM THE EXPERIMENTS
In this section, we provide more details of the results of the experiments we conducted in the main text. In particular, in Fig 4 we present the change of validation accuracies and group sparsity levels with epochs for the group sparsity tasks in Seccion 5.2) We then present in Fig. 5 validation accuracics and unstructured sparsity level versus epochs for the task in Section 5.3) We note that although it takes more epochs for RMDA to fully stabilize in terms of manifold identification, the sparsity level usually only changes in a very limited range once (sometines even before) the validation accuracy becomes steady, meaning that we do not need to run the algorithm for an unreasonably long time to obtain satisfactory results.
20

---

Table Details of the experimental settings of logistic regression on MNIST in Section 5.2
Parameter
Value
Data set
MNIST
Model
Logistic regression
Loss function
Cross entropy
Regularization function
Group LASSO 10-3
Regularization weight
Total epochs
500
ProxSGD
Learning rate schedule Momentum
(epocch) = 10-1-1111110 [ppoch/50]
10
ProxSSI
Learning rate schedule
n)ppoch) = 10
[0]
RMDA
Restart epochs Learning rate schedule
50, 100, 150, 200
nepocch) = max 10 - 10 10-
Momentum schedule
c(epoch) = min 10 10-20002+0000 [epuch/50]
Table 4: Details of the experimental settings of the multi-layer fully-connected NN on FashionMNIST in Section 5.2)
Parameter
Value
Data set
FashionMNIST
Model
Fully-connected NN Table 11 Cross entropy
Loss function
Regularization function
Group LASSO
Total epochs
500
ProxSGD
Regularization weight Learning rate schedule Momentum
10-4
1/peoch) 10-1-lepoch/50) 10
ProxSSI
Regularization weight Learning rate schedule
10 6
(eppoch) 10 3- (epocchh550)
RMDA
Regularization weight Restart epochs
x 10
50, 100, 150, 200
Learning rate schedule
1/(eoch) max 1000000:,0--- c(epoch) min 10-(1_h00-2
Momentum schedule
E OTHER REGULARIZERS FOR POSSIBLY BETTER GROUP SPARSITY AND GENERALIZATTION
downside of is that pushes groups toward zeros and thus introduces bias the final model. For its remedy, minimax concave penalty (MCP, Zhang 2010) is then proposed to penalize only the groups whose norm smaller than a user-specified threshold. More preciscly, given hyperparamcters À 2 0,w 2 1, the one-dimensional MCP is defined by
A/w| wx
iflw
wA
MCP(W:A,W)
iflwl
> wA.
One can then apply the above formulation to the norm a vector to achieve the effect of inducing group-sparsity. In case, given index set I, that represents group, the
21

---

Table Details of the experimental settings of LeNet5 on MNIST in Section 5.2
Parameter
Value
Data set
MNIST
Model
LcNet5 Table 12)
Loss function
Cross entropy
Regularization function
Group LASSO
Total epochs
500
ProxSGD
Regularization weight
1.2 10
Learning rate schedule
(epoch) 10-1-Lepoch/50)
Momentum
10
ProxSSI
Regularization weight
9 10
Learning rate schedule
(epochh) 10 (003-hpppch/501
RMDA
Regularization weight
10-1
Restart epochs
50, 100, 150, 200
Learning rate schedule
(epochh) max (10- 10 1e-1-00--pppp Lepoch/50]
Momentum schedule
e(epoch) min 10 2+ [opoch/50J)
Table 6: Details of the experimental settings of LeNet5 on FashionMNIST in Section 5.2
Parameter
Value
Data set
MNSST
Model
LeNet5 Table 12
Loss function
Cross entropy
Regularization function
Group LASSO
Total epochs
500
ProxSGD
Regularization weight
1.2 x 10
Learning rate schedule
(epochh) = 10 101ooccpoch/50) 10
Momentum
ProxSSI
Regularization weight
6 x 10-5
Learning rate schedule
n(poohh) = 10 10-3-100 10-3-10--00 (-pocchhh//50
RMDA
Regularization weight Restart epochs
10
50, 100, 150, 200
Learning rate schedule
(epoch)) = max 10 10 1 Lepoch/ /50)
Momentum schedule
c(epoch) min(1, 10 2+ lepoch/50]] /50]
MCP for this group is then computed as Breeeny & Huang
2009
Wx, ll.
W1, 2
if Wz,, || < wg
MCP (Wz,; wg) =
Ag
Wr, 2 wigAg-
2
We then consider
1
((W) Σ
MCP (Wz,: Ag
(31)
that group MCP regularization may simultancously provide higher group sparsity and better validation accuracy than the group LASSO norm in vision and language tasks. Another possibility to enhance sparsity is to add another 4-- norm entry-wise MCP regularization to the group-level regularizer. The major drawback
is shown in Deleu & Bengio 2021 1
22

---

Table 7: Details of the experimental settings of the modified VGG19 on CIFARIO in Sec-
tion 5.2
Parameter
Value
Data set
CIFARIO
Model
VGG19 Table 13
Loss function
Cross entropy
Regularization function
Group LASSO
Total epochs
1000
ProxSGD
Regularization weight Learning rate schedule
5 x 10
vepoohh) = 10 (0-1-lepoch/100) 10
Momentum
ProxSSI
Regularization weight Learning rate schedule
x 10-7
n(cpoch) 10 (eppoochpc//00
RMDA
Regularization weight Restart epochs
10
100, 200, 400, 500
Learning rate schedule
vepochh) = max [0 10 10-1--epuchh/unn
Momentum schedule
c(epoch) = min(1, 10 10-20-022200 2+
Table 8: Details of the experimental scttings of the modified VGG19 on CIFAR100 in
Section 5.2
Parameter
Value CIFART00
Data set
Model
VGG19 Table 13
Loss function
Cross entropy Group LASSO 1000
Regularization function
Total epochs
ProxSGD
Regularization weight Learning rate schedule Momentum
3 x 10
mepocch) 10 10-1- (epochh/110)) 10-1
ProxSSI
Regularization weight Learning rate schedule
10-7
nepochh) 10 3- Lepochh/100
RMDA
Regularization weight Restart epochs
10-4
100, 200, 300,400, 500
Learning rate schedule
πCppoch) maxx110= 6 1- 1spnchhpch/1100)
Momentum schedule
c(epoch) = min(1, 10 2+ 2 (epoch/100)
of these approaches the requirement of additional hyperparameters, and we prefer simpler approaches over those with more hyperparameters, as hyperparameter tuning in the latter can be troublesome for users with limited computational resources, and using a simpler sotting can also help us to focus on the comparison of the algorithms themselves. The experiment in this subsection is therefore only for illustrating that these more complicated regularizers can be combined with RMDA the user wishes, and such regularizers might lead to better results. Therefore, train version of LeNet5, which is slightly simpler than the one we used in previous experiments, on the MNIST dataset with such regularizers using RMDA and display the respective performance of various regularization schemes in Fig. For the weights W, of each group in (7) in this experiment we consider the following setting. Let. L be the collection of all index sets that belong to the i-th layer in the network,
23

---

Table 9: Details of the experimental settings of ResNet50 on CIFAR10 in Section 5.2
We use the ResNet50 model from the public script https: htt///gitttt com we wewawaaaaaaee ieeeiaccune cunzail/ pytorch-cifes -ifar1000
Parameter
Value
Data set
CIFARIO
Model
ResNet50
Loss function
Cross entropy
Regularization function
Group LASSO
Total epochs
1500
ProxSGD
Regularization weight Learning rate schedule Momentum
10-6
(eppoch) 10011-lpoch/hl0
10-1
ProxSST
Regularization weight Learning rate schedule
10-7
7/cpoch) 10-3-11111 L-Lppoch/// 150
RMDA
Regularization weight Restart epochs Learning rate schedule
10-5
150, 300, 450, 600 (eppoch) max [10 10 lepochhch/)
Momentum schedule
c(epoch) min (1, 10 2
Table 10: Details of the experimental settings of ResNet50 on CIFAR100 in Section 5.2 We use the ResNet50 model from the public script http:///gtthub..coo//eeaa.....at pytorch-cifar100
Parameter
Value
Data set.
CIFAR100
Model
ResNet50
Loss function
Cross entropy Group LASSO
Regularization function
Total epochs
1500
ProxSGD
Regularization weight Learning rate schedule Momentum
4 10-6
()peoch) = 10-1-10--ee lepoclpphh11100 10-1
1-
ProxSSI
Regularization weight Learning rate schedule
3 x 10-7
neepoch) = 10 3- (opoch/150)
RMDA
Regularization weight Restart epochs Learning rate schedule
1
150. 300, 450, 600
r/epoch) = max (10-4, lepocchh/150)
Momentum schedule
c(epoch) = min(1, (1, 10 10p2+tepoch/150))
and denote
Nr. Σz [Z IEEL:
the number of parameters this layer, for all i, we set wy /Nt, for all g such that Ig Lj. Given two constants À > 0 and 1, The values of Xg and Wy in (31) are then assigned as Ag = Awy and Wy WWy.-
In this figure, group LASSO is abbreviated GLASSO; 4-rorm plus group LASSO norm, LIGLASSO: group MCP, GMCP; clement-wiss MCP plus group MCP, L1GMCP. Our results exemplify that different regularization schemes might have different. benefits
24

---

Table 11:
Details of the multi-layer fully-connected NN.
/stee//essmmtttssdoe///sssss/s/s mlp https://github.com
2
Parameter
Value
Type of layers
fully-connected layer
Number of layers
7
Number of output neurons each layer: 2,5,,
512, 256, 128, 64, 32, 16, relu/softmax
Activation function for convolution/output layer
Table 12: Details of modified LeNet5 for experiments in Section 5.2 https: //github.
com
Sareett___rgeeeee large py:
Parameter
Value
Number layers
Number of convolutional layers
2
Number of fully-connected layers
2
Size of convolutional kernels
3
Number of output filters 1,2
20, 50
Number of output neurons 3,
500, 10
Kernel size, stride, padding of maxing pooling
2 x 2, none, invalid
Operations after convolutional layers
max pooling relu/softmaa
Activation function for convolution/oulpaee layer
one of the criteria with proper hyperparameter tuning. The detailed numbers are reported
in Table 15 and the experiment scttings can be found in Tables 16 and 17
Table 13: Details of the modified VGG19.
blob/masten
Parameter
Value
Number of layers
17
Number of convolutional layers
16
Number of fully-connected layers
1
Size of convolutional kernels
3 x 3
Number of output filters 1-2, 3-4, 5-8, 9-16 Kernel size, stride, padding of maxing pooling Operations after convolutional layers
64, 128, 256, 512 2 x 2, 2, invalid
max pooling, batchnorm relu/softmax
Activation function for convolution/outpee layer
25

---

Table 14: Details of experimental settings of ResNet50 on CIFARIO and CIFAR100 for
unstructured sparsity. In this experiment, adopt the version of ResNet50 in Sundar & Dwaraknath h021
Parameter
Value
Model
ResNet50
Loss function
Cross entropy
RMDA
Data
CIFAR1O
Total epochs
1000
L1 weight
10-5
Restart epochs
150, 450
Learning rate schedule
(/ppoch) max (10 10 1,0 1500)
Momentum schedule
c(epoch) = min 10 2 (epochhh111100
Data
CIFAR100
Total epochs
1000
L1 weight
3 x 10-5
Restart epochs
150,300 450
Learning rate schedule
(epochh) (10 10-lepoch/150) RigL
Momentum schedule
c(cpoch) min (1 (00-chhepcch///0 1100))
Data
CIFARI0
Total epochs
1000
Sparse initialization
erdos-renyi-kernel
Density
0.02
Prune rate
0.3
Decay schedule
cosine
Apply when
step end
Interval
100
End when
65918
Learning rate
0.1
Momentum
0.9
Weight decay
10
Label smoothing
0.1
Decay frequency
20000
Warmup steps
1760
Decay factor
0.2
Data
CIFAR100
Total epochs
1000
Sparse initialization
erdos-renyi-kernel
Density
0.02
Prune rate
0.3
Decay schedule
cosine
Apply when
step end
Interval
100
End when
65918
Learning rate
0.1
Momentum
0.9
Weight decay
10-4
Label smoothing
0.1
Decay frequency
20000
Warmup steps
1760
Decay factor
0.2
26

---

Stuctured Valcaaion Accurac)
Logistic Regression on MNIST
Sructured Spensky Validation Aviiationccuuree Accurecy
Fully-connected NN on FashionMNIST
Prox5GD
0.75
Frox5GD
0.910
Prov5Si
0.50
PrevSSi
0.905
HMDA
RMDA
100
200
300
400
500
0
100
200
300
400
500
Epochs
Epochs
0.50
0.4
0.00
0.0
100
200
300
400
500
100
200
300
400
500
Epochs
Epochs
(a) Logistic regression on MNIST
(b) Fully-connected NN on FashionMNIST
Validation Acouracy
LeNet5 on MNIST
Structured Sparsity Validetion Accumcy
LeNet5 FashionMNIST
MSCD
MSGD
0.90
Prox5GD
Prox33D
RMDA
RMDA
100
200
300
400
500
100
200
300
400
500
Epochs
Epochs
Sruchured
0.5-
0.0
0.0
100
200
300
500
1000
200
300
400
500
Epochs
Lpochs
(c) LeNet5 on MNIST
(d) LeNet5 on MashionMNNIST
Structured Sparity Validation Accurss
VGG19 CIFAR10
Strudured Speesit Validetoon Accumes accurncy
VGG19 CIFAR100
MSGD
ProXSGD
0.5
ProxSGD
ProvS5i
PronSSi
0.6
RMDA
RMDA
0.0
800
Epochs
Epochs
0.50
0.5-
200
400
600
800
1000
200
400
600
800
1000
Epochs
Epochs
(e) VGG19 on CIFARI0
(f) VGG19 on CIFAR100
Structured Valication Accuracy
ResNet50 CIFAR10
Structured Spersity Valdeaton Accuracy
ResNet50 CIFAR100
0.75
0.75
ProxGG
Prox3GD
Prex55i
ProxSSI
0.50
0.25
200
400
600
800 1pocts
1000
1200
1400
0.50
0.25
1400
Spochs
Fpochs
(g) ResNet50 CIFAR1O
(h) ResNet50 CIFAR100
Figure- 4: Group Sparsity and validation accuracy v.s epochs of different algorithms on various models with the group-LASSO regularization of single run.
27

---

1.0
1.0
Validation Sparsity
Sparsity
0.5
0.5
0.0
0.0
200
400
600
800
1000
Vall dation Accuracy
200
400
600
800
1000
0.90
0.7
0.85
0.6
RMDA
200
1000
600
800
1000
Epochs
Epochs
(a) Res.et50 on CIFAR10
(b) ResNet50 on CIFAR100
Figure 5: Unstructured Spansity and validation accuracy v.8 epochs of RMDA on ResNet50
of a single
1.00
Validation Accuracy
0.8
GLASSO
Group Sparsity
0.7
GMCP
0.99
0.6
GLASSO
0.5
0.98
L1GLASSO
GMCP
0.4
LIGMCP
0.97
0.3
0.200
50
100
150 Epochs
200
250
300
220
240
260
280
300
Epochs
Figure 6: Comparison between group LASSO, Li+u LASSO, Group MCP, L1+Group MCP
Table 15: Results of training LeNet5 on MNIST using RMDA with different regularizers. We report mean and standard deviation of three independent runs.
Regularizers Validation accuracy
Group sparsity
GLASSO
99.11 0.06%
45.33 0.99%
LIGLASSO
99.02 + 0.01%
58.92 = 1.30%
GMCP
99.25 + 0.08%
32.81 = 0.96%
LIGMCP
99.21 + 0.03%
32.91 + 0.35%
Table 16: Details of the modified simpler LeNet5 for the experiment in Appendix E
https:// http:://github.... http://wwwaa....//////aaa/t//tta small.pp
Parameter
Value
Number layers
5
Number of convolutional layers
3
Number of fully-comnected layers
2
Size of convolutional kernels
5
Number of output filters 1,2
6, 16
Number of output neurons 3, 4,
120, 84,
Kernel size, stride, padding of maxing pooling
2 x 2, none, invalid
Operations after convolutional layers
max pooling
Activation function for convolution coltuuttiooooouuuuu /output layer
relu/softmax
28

---

Table 17: Details of the experimental scttings for comparing different regularizers in Ap-
pendix E
Parameter
Value
Data set.
MNIST
Model
LeNet5 Table 16)
Loss function
Cross entropy
Algorithms
RMDA
Total epochs
300
Restart epochs
30, 60, 90, 120
Learning rate schedule
neppoch) max [0 1,10,,11000000
1,10:1000001--1-1111111111111111 1-110-11- Lepnch/330
Momentum schedule
c(epoch) = min [1 10 12 (epochhhphh/30)
GLASSO
Group LASSO weight
10-3
LIGLASSO
L1 weight
10
Group LASSO weight
10-5
GMCP
Group MCP weight
10-5
7
LIGMCP
L1 weight
10
Group MCP weight
10-5
7
64
29


Reviews:
[{"review_id": "sYY_QREJdX-", "reviewer": "Reviewer_KsXr", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "### Strengths\n\n1. The paper introduces an algorithm for training neural networks with a regularization term for promoting desired structures in the model. The new method does not incur computation additional to SGD with momentum and could be of practical use. The ideas of the paper are based on well-founded rationales.\n2. In general, the paper is quite well-written, with the main ideas outlined clearly. The approach is well-motivated and seems to be built upon established literature. The review of related works is informative.\n3. The main theoretical results of the paper (Theorem 1 and Theorem 2) are non-trivial and meaningful, and the proofs are rigorous.\n\n### Weakness\n\nI have a few concerns with the manuscript in its current state.\n\n1. In my opinion, the paper overstates the significance and implications of its results in its presentation. More precisely:\n    - In the abstract, introduction, and throughout the discussion, the paper claims that \"we rigorously prove that the proposed method can correctly identify within finite steps the underlying structure\".\n    - In the experiments, they conclude that \"RMDA is the only algorithm that steadily identifies the correct structured sparsity\".\n\n    I think those are not correct characterizations of the results obtained in this work:\n    - Roughly speaking, Theorem 2 for structured sparsity of neural networks just proves that:\n\n         *If the estimator converges to some stationary point W, then its sparsity converges to the sparsity of W within finite step*\n\n    - Similarly, the experiments just show that RMDA has a stable structured sparsity\n\n    While these results are non-trivial, they concern the **stability** of the algorithm, and have little to do with **correctness**: a bad algorithm that got stuck at a non-optimal stationary point also satisfies those properties. To obtain what the paper claims, some more work is needed. In the theory part, results that are equivalent to model-selection consistency for linear models are required. For the simulations part, some experiments with simulated data, when a measure of deviation from the \"ground truth\" or \"correct/optimal sparsity\" could be recognized, are necessary.\n2. While the results of Section 3 of the manuscript are rigorous, the applications to neural networks (Section 4) lack several important details. When moving from a general framework to a specific case (Section 4.1 and 4.2), two central concepts:\n    - the corresponding active manifold,\n    - the precise description of the limit point W^*\n\n    are not defined explicitly. This causes significant unnecessary confusion and makes it harder to judge the accuracy and the importance of the results. Specifically,\n    - In Definition 1: M is required to be a C^2 manifold, and in general, should be independent of the limit point W^*\n    - In Section 4.1 (Structured sparsity), the active manifold seems to be defined as a hyperplane around (and depends on) W^*. To make this fit into the framework, W^* needs to be unique for all random realizations (but this is unlikely). If this is not the case, then M is a union of several hyperplanes of different dimensions (correspond to different limit points for each realization) and is no longer a manifold.\n\n    I believe a clear description of the active manifolds for each case and some verification of their geometric properties would help improve the manuscript.\n3. My last concern about the theoretical analysis is its (somewhat hidden and informally defined) assumption that the tentative iterate {W ̃ t} converges almost surely to a certain point W∗. This statement can be interpreted in different ways and needs to be spelled out mathematically. My main question is: Is W* the same for all realizations of randomness? In principle, this is not true, but the analysis was written as if that was the case (see point (2) below).\n\n    The manuscript also stated that verifying this assumption is possible, but these are not the purpose of this work, so they avoid distracting the readers from such technical results. However, it is worth pointing out that W ̃ and W are intertwined in their constructions, and making the convergence of the W~ an assumption is a bit too strong. Even if rigorous results don't need to be provided, some examples and quick discussions about this should be included, perhaps in the appendix. This part will also help resolve the lack of understanding about the structure of W* described above.\n\n### Other comments and questions\n\n- Beginning of Section 3: \"In stark contrast to our results, it is actually well-known in convex optimization that those algorithms based on proximal stochastic gradient are *unable to identify the manifold within finite iterations*\".\n    —> This statement needs more references.", "summary_of_the_paper": "This paper proposes an algorithm for training neural networks with a regularization term for promoting desired structures in the model. The paper (claims to) prove that the proposed method can correctly identify within finite steps the underlying structure. The simulations then show that the method outperforms existing packages in identifying structured sparsity without compromising prediction accuracy.", "summary_of_the_review": "Overall, my vote for the paper is a (weak) reject. I think the paper has some strong points and the general results are meaningful. On the other hand, I think the technical writings of Section (Applications to deep learning) are less rigorous and lack important information. Finally, I feel the paper overstates the significance and implications of its results in its presentations.\n\nUpdate after author's responses and revision: Most of my concerns have been addressed in the revision, with (1) a more rigorous reframing if the significance and importance of the work, and (2) experiments to validate the efficiency of the approach. I think this is a good paper in its current state. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "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": "ZQRgQwVcJRG", "reviewer": "Reviewer_MELK", "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": "Positive aspects:\n\n1. The proposed algorithm is well motivated.\n2. The proposed algorithm is a unique and different take on structured learning.\n3. The proposed algorithm and the related math is well explained in the paper. \n\n\nNegative aspects:\n1. Experiments are limited. It is understandable that the main goal of the paper is to share a new proximal based method for structured learning but it will be good to have a few more experiments. \n2. It will also be good if comparisons with other structure learning-based methods are done. \n3. Related work is missing a recent work that leverages proximal operators to find a sparse network from a pretrained network which can also be applied during training for group sparsity. Verma, Sagar, and Pesquet, Jean-Christophe. \"Sparsifying Networks via Subdifferential Inclusion.\"  International Conference on Machine Learning. PMLR, 2021.", "summary_of_the_paper": "In this paper, the authors propose Regularized Modernized Dual Averaging (RDMA) algorithm to train structured neural networks. This is a proximal method that achieves variance reduction without any extra cost per iteration. The algorithm does not require any extra hyperparameters than what stochastic gradient descent requires. Authors theoretically prove that structure identification is guaranteed after a finite number of iterations.\n\nExperiments have been performed to obtain group sparse neural networks. Networks and datasets used in the experiments are simple logistic regression network on MNIST, 7-layer fully-connected network on FashionMNIST, LeNet5 on MNIST, and VGG16 on CIFAR10. The method has been compared with SGD, ProxSGD, and ProxSSI. ", "summary_of_the_review": "I am leaning towards acceptance given that authors address the problems listed out. Overall the idea is good and the paper is well written to be considered at par with ICLR.", "strength_and_weaknesses": "", "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": "0AimpG0XbHA", "reviewer": "Reviewer_mrfp", "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": "Using momentum and different regularizers to impose the desired structure during optimization and esp. NN training is common in machine learning. The proposed RMDA can be viewed as a non-trivial extension of the dial averaging algorithm to use momentum. \n\n1. I found the claims not 100% accurate, and sometimes misleading:\n - **Variance reduction beyond ...**: It was not clear how this achieved? can the authors explain what they meant by variance reduction and where in the paper they showed that? Also, despite claiming that RDMA's cost is the same as SGD, keeping track of momentum and dual averaging makes it slightly more complex than SGD (although still better than other variance reduction techniques)\n- **Guaranteed strucutre identification**: I find this slightly exaggeration of the results as there is no theoretical result on the convergence of the RDMA at all. Theorem 2 assumes that the algorithm converges, and under some assumptions, the converged parameter belongs to the active manifold.\n- **Superior empirical performance**: \"RDMA identifies the optimum structure\" is hard to prove, as there is no way to show that the structure found by any algorithm is the best and optimum, even though it is better than baseline.\n\n2. The theoretical analysis is not complete, and is based on the restrictive assumptions and expecting that with the given values of $\\\\beta_t$, $\\\\eta_t$ the algorithm converges. \n3. In theorem 2, does $T_0$ refer to the extra iterations of RDMA after having $\\\\tilde{W}^t$ converged? or it includes all iterations of RDMA, including the convergence of $\\\\tilde{W}^t$?\n4. Section 3, It is stated that in convex optimization, \"algorithms based on proximal stochastic gradient are unable to identify the manifold within finite iterations\". However, RMDA can identify the active manifold in finite iterations. What is the main reason to achieve this contradicting result? Is it because of the set of assumptions made in the analysis? or the way that momentum is incorporated in developing the algorithm?\n\nminor suggestions:\n- It would be much better to define all notations used in the paper, for example the notations for subdifferential, interior, relative-interior (although mostly standard).\n", "summary_of_the_paper": "Regularization is generally used to impose desired structure on NN during training. The authors developed RMDA (Regularized Modernized Dual Averaging) which uses the weighted average of the previous SG to compute the tentative update via proximal operation associated with the regularizer. Then the parameters of the model are updated in the direction of this tentative update with a pre-defined factor. The authors theoretically analyzed the performance of their algorithm and showed that under some assumptions, RMDA can identify the structure of model in finite iterations.\n", "summary_of_the_review": "By adding momentum and proximal operation associated with the regularization to the modernized dual averaging algorithm, the authors developed RDMA. Using tools from non-linear optimization and manifold identification, they theoretically showed that if RDMA converges, then it will find the active manifold after a finite number of iterations. Experimentally, they showed that RDMA outperforms proxSGD and ProxSSI in terms of both accuracy (sometimes) and group sparsity (always).", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper develops optimization algorithms for fitting structured neural networks. It focuses on the manifold identification property, which guarantees after finitely many iterations, all iterates have the same sparsity structure as at convergence. The proposed method extends dual averaging to include momentum. The paper’s analysis shows that if the proposed method converges, it converges to a stationary point, and identifies the sparsity pattern of the limit in finitely many iterations. Experiments show improvements in sparsification compared to existing two-step sparsifiers, without a degradation in accuracy. 

The initial review raised concerns about clarity, as well as some of the claimed significance of the results: the paper does not prove that an optimal, or even good sparsity structure is obtained — rather, it proves that the sparsity structure at convergence is obtained after finitely many iterations. The reviewers also raised a number of detailed concerns about the paper’s mathematical exposition. 

After considering the authors response, and a revision which significantly clarified both the paper’s notation and its main claims, the reviewers converged to a recommendation to accept. The paper provides a principled approach to sparsification, with supporting theory (albeit about finite identification, rather than optimality). The proposed algorithm appears quite practical and is supported by experiments demonstrating improvements over existing sparsification methods.
Decision: Accept (Poster)