Implicit Regularization for Group Sparsity
Authors: Jiangyuan Li
Thanh V Nguyen
Chinmay Hegde
Raymond K. W. Wong
Venue: ICLR 2023 poster (2023)
Keywords: gradient descent
implicit regularization
structured/group sparsity
linear neural network

Abstract: We study the implicit regularization of gradient descent towards structured sparsity via a novel neural reparameterization, which we call a diagonally grouped linear neural network. We show the following intriguing property of our reparameterization: gradient descent over the squared regression loss, without any explicit regularization, biases towards solutions with a group sparsity structure. In contrast to many existing works in understanding implicit regularization, we prove that our training trajectory cannot be simulated by mirror descent. We analyze the gradient dynamics of the corresponding regression problem in the general noise setting and obtain minimax-optimal error rates. Compared to existing bounds for implicit sparse regularization using diagonal linear networks, our analysis with the new reparameterization shows improved sample complexity. In the degenerate case of size-one groups, our approach gives rise to a new algorithm for sparse linear regression. Finally, we demonstrate the efficacy of our approach with several numerical experiments.

Published as a conference paper at ICLR 2023
IMPLICIT REGULARIZATION FOR GROUP SPARSITY
Jiangyuan Li", Thanh V. Nguyen, Chinmay Hegde & Raymond K. W. Wong"
Texas A&M University
New York University
(jiangyunnli, raywong @tam.. edu;
t thanhng. cs& es@gmaill com; chinmay hênyu..cu.mm edu
ABSTRACT
We study the implicit regularization gradient descent towards structured sparsity via novel neural reparameterization, which we call "diagonally grouped linear neural network". We show the following intriguing property of our reparameter- ization: gradient descent over the squared regression loss, without any explicit regularization, biases towards solutions with a group sparsity structure. In contrast to many existing works understanding implicit regularization, we prove that our training trajectory cannot be simulated by mirror descent. We analyze the gradient dynamics of the corresponding regression problem the general noise setting and obtain minimax-optimmi eπror rates. Compared to existing bounds for implicit sparse regularization using diagonal linear networks, our analysis with the reparameterization shows improved sample complexity. In the degenerate case of size-one groups, our approach gives rise to a new algorithm for sparse linear regression. Finally, we demonstrate the efficacy of our approach with several numerical experiments"
INTRODUCTION
Motivation. salient feature of modern deep neural networks is that they are highly overparame- terized with many more parameters than available training examples. Surprisingly, however, deep neural networks trained with gradient descent can generalize quite well in practice, even without explicit regularization. One hypothesis is that the dynamics of gradient descent-based training itself induce some form of implicit regularization, biasing toward solutions with low-complexity (Hard) al., 2016; Neyshabur et al. 2017). Recent research in deep learning theory has validated the hypothesis of such implicit regularization effects. A large body of work, which we survey below, has considered certain (restricted) families of linear neural networks and established two types of implicit regularization standard sparse regularization and fg-norm regularization - depending on how gradient descent is initialized.
On the other hand, the role of network architecture, the way the model is parameterized in implicit regularization, less well-understood. Does there exist a parameterization that promotes implicit regularization of gradient descent towards richer structures beyond standard sparsity?
In this paper, we analyze a simple, prototypical hierarchical architecture for which gradient descent induces group sparse regularization. Our finding that finer, structured biases can be induced via gradient dynamics- - highlights the richness co-designing neural networks along with optimization methods for producing more sophisticated regularization effects.
Background. Many recent theoretical efforts have revisited traditional, well-understood problems such linear regression (Vaskevicius et al. 2019 Li et al.
2021 Zhao et al.) 2019), matrix factoriza- 2019) and tensor decomposition (Ge et al.) 2017: Wang al. 2020). from the perspective of neural network training. For nonlinear models with squared error loss, Williams et al. (2019) and Jin & Montúfar (2020) study the implicit bias of gradient descent in wide depth-2 ReLU networks with input dimension Other works (Gunasekar
tion (Gunasekar et al. 2018b Li et al. 2018 Arora et al.
et al. 2018c Soudry et al. 2018 Nacson et al. 2019) show that gradient descent biases the solution towards the max- max-ma (or minimum E norm) solutions over separable data.
Code available htttt:://gtthhiiee com/ jaagjyannggn1111. 1mpl iiiiitttee

---

Published as a conference paper at ICLR 2023
NNs
Noise
Implicit vs. Explicit
Regularization
Vaskevicius et al. (0119)
DLNN
V
Implicit (GD)
Sparsity
Dai et al. (2021)
LNN
X
Explicit (ly-penalty)
(Group) Quasi-norm
Jagadeesan al. (2021)
LCNN
X
Explicit (ez-penalty) Implicit Implicit (GD)
Norm induced by SDP f--norm Structured sparsity
Wu et al. (020))
DLNN
X
Thss paper
DGLNN
Table 1: Comparisons to related work on implicit and explicit regularization. Here, GD stands for gradient descent, (D)LNN/CNN for (diagonal) linear/convolutional neural network, and DGLNN for diagonally grouped linear neural network.
Outside of implicit regularization, several other works study the inductive bias network architectures under explicit f2 regularization model weights (Pilanci & Ergen 2020) Sahhner et al. 2020). For multichannel linear convolutional networks, Jagadecsan et al. (2021) show that norm minimization of weights leads to norm regularizer predictors, where the norm is given by semidefinite program (SDP). The representation cost in predictor space induced by explicit & regularization on (various different versions of) linear neural networks is studied in Dai et al. (202I), which demonstrates several interesting (induced) regularizers on the linear predictors such as &p quasi-norms and group quasi-norms. However, these results are silent on the behavior of gradient descent-based training without explicit regularization. In light of the above results, we ask the following question:
networks,,agaddcssan
Beyond fz-norm, sparsity and low-rankness, can gradient descent induce other forms of implicit regularization?
Our contributions. In this paper, rigorously show that a diagonally-rrouped linear neural network (see Figure [b) trained by gradient descent with (proper/partial) weight normalization induces group-sparse regularization: form of structured regularization that, the best of our knowledge, has not been provably established in previous work.
One major approach to understanding implicit regularization of gradient descent is based its equivalence to a mirror descent (on a different objective function) (e.g., Gunasekar et al. 20188a] Woodworth et al., (220). However, we show that, for the diagonally- grouped linear network architec- ture, the gradient dynamics is beyond mirror descent. We then analyze the convergence of gradient flow with early stopping under orthogonal design with possibly noisy observations, and show that the obtained solution exhibits an implicit regularization effect towards structured (specifically, group) sparsity. In addition, we show that weight normalization can deal with instability related to the choices of learning rates and initialization. With weight normalization, are able to obtain similar implicit regularization result but more general settings: orthogonal/non--oo hotp///oooooooooonnlllloooooo designs with possibly noisy observations. Also, the obtained solution achieve minimax opttimll error rates.
Overall, compared to existing analysis of diagonal linear networks, our model design - that induces structured sparsity exhibits provably improved sample complexity. In the degenerate case of size-one groups, our bounds coincide with previous results, and our approach can be interpreted as a new algorithm for sparse linear regression.
Our techniques. Our approach is built upon the power reparameterization trick, which has been shown to promote model sparsity (Schwarz et al., 2021). Raising the parameters of linear model element-wisely to the N-th power (N > 1) results in that parameters of smaller magnitude receive smaller gradient updates, while parameters of larger magnitude receive larger updates. In essence, this leads to "rich get richer" phenomenon in gradient-based training. In Gissin et al. (2019) and Berthier (2022). the authors analyze the gradient dynamics on a toy example, and call this "incremental learning". Concretely, for a linear predictor w E TRP, if we re-parameterize the model as w -o o (where N means the N-th clement-wise power of u), then gradient descent will bias the training towards sparse solutions. This reparameterization is equivalent to diagonal linear network, as shown in Figure Ia This is further studied in Woodworth et al. (2020) for interpolating predictors, where they show that small enough initialization induces ( fi-nrrm regularization. For noisy settings, /Vaskevicius et al. (2019) and Li et al. (202I) show that gradient descent converges to sparse models with early stopping. In the special case of sparse recovery from under-sampled
2

---

Published as a conference paper at ICLR 2023
(a) Diagonal linear NN (DLNN).
(b) Diagonally grouped linear NN (DGLNN).
Figure An illustration of the two architectures for standard and group sparse regularization.
observations (or compressive sensing), the optimal sample complexity can also be obtained via this reparameterization (Chou et al. (021).
Inspired by this approach, we study novel model reparameterization of the form where vz for each group E (1,..., I.). (One way to interpret this model is to think of as the "magnitude" and Vi as the "direction" of the subvector corresponding to each group; see Section for details.) This corresponds
[Wi..... wL).
special type of linear neural network architecture, shown in Figure lb related architecture has also been recently studied in Dai et al. (2021), but there the authors have focused the bias induced by explicit & regularization on the weights and have not investigated the effect of gradient dynamics.
The diagonally linear network parameterization of Woodworth et al. (2200) Li al. (2021 does not suffer from identifiability issues. In contrast to that, in our setup the "magnitude parameter wi of each group interacts with the norm of the "direction", Vvll2- causing fundamental problem of identifiability. By leveraging the layer balancing effect (Du et al., 2018) in DGLNN, we verify the group regularization effect implicit in gradient flow with early stopping. But gradient flow is idealized; for a more practical algorithm, we use a variant of gradient descent based on weight normalization, proposed in (Salimans Kingma| 2016), and studied in more detail in (Wu 2020). Weight normalization has been shown to be particularly helpful in stabilizing the effect of learning rates (Morwani & Ramaswamy 2022] Van Laarhoven, 2017). With weight normalization. the learning effect is separated into magnitudes and directions. We derive the gradient dynamics on both magnitudes and directions with perturbations. Directions guide magnitude to grow, and as the magnitude grows, the directions get more accurate. Thereby, are able to establish regularization effect implied by such gradient dynamics.
A remark on grouped architectures. Finally, we remark that grouping layers have been commonly used in grouped CNN and grouped attention mechanisms (Xie et al.) 2017 7] Wu et al. 2021 ), which leads to parameter efficiency and better accuracy. Group sparsity also useful for deep learning models in multi-omics data for survival prediction (Xie et al. 2019). We hope our analysis towards diagonally grouped linear NN could lead to more understanding of the inductive biases of grouping- style architectures.
2 SETUP
Notation. Denotes the set (1,2....,4 by [L], and the vector & norm by ||-|]- We use 1p and Op to denote p-dimensional vectors of all is and all Os correspondingly. Also, O represents the entry-wise multiplication whereas get denotes element-wise power N of a vector B. We use e, to denote the 7th canonical vector. We write inequalities up to multiplicative constants using the notation S. whereby the constants do not depend on any problem parameter.
Observation model. Suppose that the index set [p] = Uf is partitioned into L disjoint (i.e., non-overlapping) groups G1, G....,, GL where G, n. G, 0, vi j. The size of G1 is denoted by Pt = |Gr] for E []. Let w E RP be a p-dimensional vector where the entries of w are non-zero only subset of groups. We posit linear model of data where observations (x,, yi) E RP x R. i
3

---

Published as a conference paper at ICLR 2023
is noise vector. Note that we do not impose any special restriction between n (the number of observations) and p (the dimension). We write the linear model in the following matrix-vector form: y Xw* E, with the
[n] are given such that y (x,, w") + E, for = ....., and g= =
n x p design matrix X = 1 X2, X2,...,,A, where X, E Rexp! represents the features from the 7th
group G1, for 1 [7]. We make the following assumptions on X:
Assumption 1. The design matrix X satisfies
sup [8 |,,,,,,, | s1
(1
x X1 -1) B2) - x
S sins where B1,B3 E R
(1)
1 Xv
sup || ||8l
1
S Souts where 31 E CRR, E RR ,1,, (2)
Vn
Vn
for some constants din, Sout E (0.
The first part T is within-group eigenvalue condition while the second part 2 is a between group block coherence assumption. There are multiple ways to construct sensing matrix fulfill these two conditions (Eldar & Boleskei 2009 [Baraniuk et al. 2010). One of them is based on the fact that random Gaussian matrices satisty such conditions with high probability (Stojnic al. 2009).
Reparameterization. Our goal is to learn parameter w from the data [x,, }=) with coefficients which obey group structure. Instead of imposing an explicit group-sparsity constraint on w (e.g., via weight penalization by group), we show that gradient descent on the unconstrained regression loss can still learn w*, provided we design special reparameterizatio. Define mapping g(.) [p] + [L] from each index to its group g(i). Each parameter is rewritten as
wy =u 200 Us vi E [p]. The
parameterization G(.) R4 x R + Rp reads
[u us, .2,..., Up] + [u u U2,
mp]-
This corresponds to the 2-layer neural network architecture displayed in Figure 1b in which W (v..., and W₂ is "diagonally" tied within each group:
W2 = diag(u) (u........ U1,
ug).
Gradient dynamics. We learn and by minimizing the standard squared loss:
1 I|y L(u, v)
- (--I(Du) o v]l?
where
1p Op
Opt
0 pa
D =
p2
pa
E I
Opz.
pp
1pz/
By simple algebra, the gradients with respect and v read as follows:
V,L = 2D (v
x (Du) ov ow- E
о Du),
V.L= = X X((Du) Ov w*) X (Du)o2
Denote r(1) =y Et vl()))vv((t). For each group 1 [Z.]. the gradient flow reads
@v,(1) 1 dul (1) ( (1)
at (t)xx r(t).
Øt
Although we are not able to transform the gradient dynamics back onto w(t) due to the overparame- terization, the extra term un (t) on group magnitude leads "incremental learning" effect.
4

---

Published as a conference paper at ICLR 2023
3 ANALYSIS OF GRADIENT FLOW
3.1 FIRST ATTEMPT: MIRROR FLOW
Existing results about implicit bias in overparameterized models are mostly based on recasting the training process from the parameter space {u(t), v(f) to the predictor space {w()) (Woodworth et al. 2020; Gunasekar et al. 2018a). If properly performed, the (induced) dynamics in the predictor space now be analyzed by classical algorithm: mirror descent (or mirror flow). Implicit regularization demonstrated by showing that the limit point satisfies a KKT Kuhn-TTucke condition with respect to minimizing some regularizer R(-) among all possible solutions.
At first, predictor space), due to complicated interactions between u and V. This hints that the training trajectory induced by overparameterized DGLNN may be analyzed by mirror flow techniques. In fact, we prove a stronger negative result, and rigorously show that the corresponding dynamics cannot be recast as a mirror flow. Therefore, we conclude that our subsequent analysis techniques are necessary and do not follow as corollary from existing approaches.
unable express the gradient dynamics in Eq. in terms of w (t) (i.e., in the
We first list two definitions from differential topology below.
Definition 1. Let M be smooth submanifold of P. Given two C vector fields of X, Y M, define the Lie Bracket of X and Y as [X, (zz) = 0Y (x) (
Definition 2. Let M be a smooth submanifold RD A C2 parameterization G M - Rd is said be commuting iff for any i E [d], the Lie Bracket (V VG,[(x) = for all M.
The parameterization studied in most existing works on diagonal networks is separable, meaning that each parameter only affects one coordinate in the predictor space. In DGLNN, the parameterization is not separable, due to the shared parameter within each group. We formally show that it is indeed not commuting.
Lemma 1. G(-) is not a commuting parameterization.
Non-commutativity of the parameterization implies that moving along VG and then VVG is different with moving with VG, first and then G; This causes extra difficulty in analyzing the gradient dynamics. [i al. (202) study the equivalence between gradient flow on reparameterized models and mirror flow, and show that commuting parameterization is sufficient condition for when gradient flow with certain parameterization simulates a mirror flow. complementary necessary condition is also established on the Lie algebra generated by the gradients of coordinate functions of G with order higher than 2. We show that the parameterization G(-) violates this necessary condition.
Theorem 1. There exists an initialization [u mats Vinal IR4 x TRP and a dime-dependent loss Le such that gradient flow under L, @ G starting from (u Vinsel cannot be written as mirror flow with respect to any Legendre function R under the loss Ly.
The detailed proof deferred to the Appendix. Theorem shows that the gradient dynamics implied in DGLNN cannot be emulated by mirror descent. Therefore, a different technique is needed to analyze the gradient dynamics and any associated implicit regularization effect.
3.2 LAYER BALANCING AND GRADIENT FLOW
Let us first introduce relevant quantities. Following our reparameterization, we rewrite the true parameters for each group as
w = (uf)
||vī = vi E R.!
The support is defined on the group level, where S (1 [L] : uf > 0) and the support size is defined as s |.S. We denote ui max(uç] S), and wienn min uz 1 S).
The gradient dynamics in our reparameterization does not preserve (t)) = 1, which causes difficulty to identify the magnitude of each u, and [|v2())) Du et al. (001)) and Arora et al. (018))
5

---

Published as a conference paper at ICLR 2023
show that the gradient flow of multi-layer homogeneous functions effectively enforees the differences between squared norms across different layers to remain invariant. Following the same idea, we discover similar balancing effect in DGLNN between the parameter and
Lemma 2. For any I [L] we have
d 1
-
l/vll) O.
dt
The balancing result eliminates the identifiability issue on the magnitudes. As the coordinates within one group affect each other, the direction which controls the growth rate both u and need be determined as well.
Lemma 3. If the initialization vi(0) is proportional to a
1 x y, then
vi(O) [M) vi v1)21 21 -6pn + Ldout +
221-
- X /(1))))
Note that this initialization can be obtained by single step of gradient descent with O initialization.
Lemma 3 suggests the direction is close to the truth at the initialization. We can further normalize it to be (0)l 4u based on the balancing criterion. The magnitude equality, vv((1) = 1/ (1),
preserved by Lemma 2 However, ensuring the closeness of the direction throughout the gradient flow presents significant technical difficulties. That said, are able to present meaningful implicit regularization result the gradient flow under orthogonal (and noisy) settings.
Theorem 2.
> 0. Consider the case where 1 1
n X X2 O, + 1' the
initialization (0) 0 < [(mmagz and vi( n XT with (V)( 10P VI E [L]. there
exists lower bound and upper bound of the time Ti < Ty in the gradient flow in Eq. such that for any Ti < t < Tu we have
x E Ve, if 00/2
ifl $ S.
Theorem states the error bounds for the estimation of the true weights w*. For entries outside the (true) support, the error is controlled by 63/2, When 0 is small, the algorithm keeps all non-supported entries to be close to zero through iterations while maintaining the guarantee for supported entries. Theorem shows that under the assumption of orthogonal design, gradient flow with early stopping is able to obtain the solution with group sparsity.
4 GRADIENT DESCENT WITH WEIGHT NORMALIZATION
Algorithm Gradient descent with weight normalization
Initialize: u(0) a1, unit norm initialization vi(0) for each I [L]. 1/.. ( for t = to T
ztt 1) v(() M, V V.C((()), v())
(t + 1) = [2.++11 VI [4]
(t+++
u(t + 1) u(t) ( VuC(u(t), v(t 1))
the early stopping criterion is satisfied then stop
end
end for
We seek more practical algorithm with more general assumptions and requirements initialization. To speed up the presentation, we will directly discuss the corresponding variant of (the more practical) gradient descent instead of gradient flow. When standard gradient descent is

---

Published as a conference paper at ICLR 2023
applied DGLNN, initialization for directions is very crucial; The algorithm may fail even with very small initialization when the direction is not accurate, as shown in Appendix The balancing effect (Lemma 2 is sensitive to the step size, and errors may accumulate (Du et al. 2018).
Weight normalization as a commonly used training technique has been shown to be helpful in stabilizing the training process. The identifiability of the magnitude is naturally resolved by weight normalization on each Vt. Moreover, weight normalization allows for a larger step size on V. which makes the direction estimation at each step behave like that at the origin point. This removes the restrictive assumption of orthogonal design. With these intuitions in mind, we study the gradient descent algorithm with weight normalization on v summarized in Algorithm | One advantage of our algorithm is that it converges with any unit norm initialization (D). The step size on u(t) is chosen to be small enough in order to enable the incremental learning, whereas the step size on vt) is chosen as T wf(t) as prescribed by our theoretical investigation. For convenience, we
define Ç - 80 (I= x Elloo Vo), for precision parameter > 0. The convergence of Algorithm 1
formalized as follows:
Theorem 3. Fix e > 0. Consider Algorithm
7 with ca (Umaz) )8
CA1
E L' 80L (Umin)) )
1
(0 = <
A
VI E [L],
any unit-norm initialization Vi for each E [L] and y S 20
Suppose Assumption
satisfied with din S iterations
(Miman) 120
and 8ont S
I20s(Mmman) yr. There exist lower bound on the number of
(alnee)
log (
(uman)) )
5
To 2 2log(1 + (5 (umin)) ))))
logz
27((5 V (umnn)) )))
and an upper bound
Tub 2 167(5 V (u )2) log a4
such that Ti S Tub and any Ti St < Tub.
x El
Ve, if
[[)(()) - will S
a,
ifl il $
Similarly as Theorem Theorem 3 states the error bounds for the estimation of the true weights w'. When a is small, the algorithm keeps all non-supported entries to be close to zero through iterations while maintaining the guarantee for supported entries. Compared to the works on implicit (unstructured) sparse regularization (Vaskevicius et al. 2019 Chou et al. 2021). our assumption on the incoherence parameter dout scales with 1/s, where is the number of non-zero groups, instead of the total number of non-zero entries. Therefore, the relaxed bound on Sout implies an improved sample complexity, which is also observed experimentally in Figure We now state corollary in common setting with independent random noise, where (asymptotic) recovery of w* is possible.
Definition 3. A random variable Y is
if for all t RR there exists 0 such that Ee S e
Corollary 1. Suppose the noise vector & has independent --sub-Gausseee entries and 2 02 log(2p) Under the assumptions of Theorem Algorithm / produces w(t) = (Du(t)) о v(t) that satisfies [[((t) - 112 S (so" logp)/) /n with probability at least 1 - 1/(8p") for any t such that Tvs- S 5t Tub-
(o(t)-=1133
Note that the error bound we obtain is minimax-optimal. Despite these appealing properties of Algo- rithm [] our theoretical results require large step size on each vt),), which may cause instability at later stages of learning. We observe this instability numrerically (see Figure/6 Appendix E Although the estimation error of w' remains small (which aligns with our theoretical result), individual entries in v may fluctuate considerably. Indeed, the large step size is mainly introduced to maintain a strong directional information extracted from the gradient of v/(() the early iterations. Therefore, we also propose Algorithm] 2 a variant of Algorithm I where we decrease the step size after certain number of iterations.
to stabilize the updates of u(t) at
7

---

Published as a conference paper at ICLR 2023
Algorithm 2. Run Algorithml
7 with the same setup till each un(t), [L] gets roughty accurate, set Te = T/. Continue Algorithm until early stopping criterion satisfied.
Theorem 4. Under the assumptions of Theorem 3 with replacing the condition on 8's by din S (m
(iiii and dout S 120s(mmas) jar we apply Algorithm 2 with T1, wi())) at the beginning, and 12x
4 after vI (f 2 (uf)), then with the same Tas and Tab we have that
The = 1 9(umaox
for any Tib S Tub.
11 Ve, i. a
[1((())) - will 2
ifl $ S.
In Theorem 4 the criterion decrease the step size is: vf(() 2 (ut)), 2 [Z]. Once this criterion is satisfied, our proof indeed ensures that it would hold for at least up to the early stopping time Tub specified in the theorem. In practice, since ui's are unknown,
can switch more practical criterion: (t + 1) (1))///u((())))))))))))))))))(() +|} < for some pre-specified tolerance 7 > 0 and [E[4]
small value O as the criterion for changing the step size. The motivation of this criterion is further discussed in Appendix [ The error bound remains the same Theorem 3 The change in step size requires a new way to study the gradient dynamics directions with perturbations. With proof technique, Theorem 4 requires smaller bound on d's (see Lemma 16 versus Lemma in Appendix C for details). We believe is a proof artifact and leave the improvement for future work.
Connection to standard sparsity. Consider the degenerate case where each group size is 1. Our repa- rameterization, together with the normalization step, can roughly be interpreted as w. ss uf sgn (u.). which is different from the reraaterparaetteiiiattoonn w; u. un N 2 2 in Vaskevicius et al. (2019) and Li et al. (2021). This also shows why large step size v; is needed at the beginning. II the initialization on v is incorrect, the sign of o; may not move with a small step size.
5 SIMULATION STUDIES
We conduct various experiments on simulated data to support our theory. Following the model in Section sample the entries of X i..d using Rademacher random variables and the entries of the noise vector & i.i.d. under NO, o²). We set or = 0.5 throughout the experiments.
Recovery
Recovered group magnitudes
NM0) E maa w/())
[|w(0
1500
epochs
spachs
Figure Convergence of Algorithm
The entries on the support are all 10.
Thecurnd moiie
Secoeeed
[acowed
ku
475 7C
30
603
1342
130
300
Figure 3: Convergence of Algorithm
The entries the support from 5 to 13.
8

---

Published as a conference paper at ICLR 2023
The effectiveness of our algorithms. We start by demonstrating the convergence of the two proposed algorithms. In this experiment, we set n = 150 and = 300. The number of non-zero entries is 9, divided into 3 groups of size 3. We rum both Algorithms I and 2 with the same initialization = 10-6 The step size 7y on u and decreased step size 1/ on v are both 10-3. In Figure 2 we present the recovery error of w' the left, and recovered group magnitudes see, early stopping is crucial for reaching the structured sparse solution. In Figure 3 we present the recovered entries, recovered group magnitudes and recovered directions for each group from left to right. In addition to convergence, we also observe an incremental learning effect.
the right. As
Recovered entries using group sparsity
Recovered entries using sparsity
1.25
m.
1,00
0.75
0.75
0.50
0..0-
0.25
0.00
0.00
400
Figure 4: Comparison with reparameterization using standard sparsity. 100, 500.
Structured sparsity versus standard sparsity. From our theory, we see that the block incoherence parameter scales with the number of non-zero groups, as opposed the number of non-zero entries. As such, we can expect an improved sample complexity over the estimators based on unstructured sparse regularization. We choose a larger support size of 16. The entries on the support are all for simplicity. We apply our Algorithm with group size 4. The result is shown in Figure We compare with the method Vaskevicius et al. (2019) with parameterization w = v=2 designed for unstructured sparsity. We display the result in the right figure, where interestingly, that algorithm fails to converge because of an insufficient number of samples.
Recovered entries
Recovery error
1.0
0.5
0.0
muti).1 J
Jose l/w
-0.5
mage [un,(1)
200
400
610
500
1003
200
400
600
800
1000
epochs
Figure 5: Degenerate case when each group size is 1. The log e2-error plot is repeated 30 times, and the mean is depicted. The shaded area indicates the region between the 25th and 75th percentiles.
Degenerate case. In the degenerate case where each group is of size 1. reparameterization takes a simpler form wi s (V), i.c., due to weight normalization, our method normalizes v to or -1 after each step. We demonstrate the efficacy of algorithms n 80 and p= 200. The entries on the support are [1, 1,, 1, with both positive and negative entries. We present the coordinate plot and the recovery error in Figure
in the degenerate case. We set
DISCUSSION
In this paper, we show that implicit regularization for group-structured sparsity can be obtained by gradient descent (with weight normalization) for a certain, specially designed network architecture. Overall, hope that such analysis further enhances understanding of neural network training. Future work includes relaxing the assumptions on 8's in Theorem 2 and rigorous analysis modern grouping architectures well power parametrizations.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported in part by the National Science Foundation under grants CCF-1934904, CCF-1815101, and CCF-2005804.
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pp. 244-253. PMLR, 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv:1905. 2019.
Richard G Baraniuk, Volkan Cevher, Marco F Duarte, and Chinmay Hegde. Model-based compressive sensing. IEEE Transactions on information theory, 56(4): 2010.
Raphaël Berthier. Incremental learning in diagonal linear networks. arXiv preprinl arXiv:2208. 14673, 2022.
lain Carmichael, Thomas Keefe, Naomi Giertych, and Jonathan P Williams. yaglm: a python package for fitting and tuning generalized linear models that supports structured, adaptive and non-convex penalties. arXiv preprint arXiv:2110.05567, 2021.
Hung-Hsu Chou, Johannes Maly, and Holger Rauhut. More is less: Inducing sparsity via overparam- eterization. arXiv preprint arXiv:21 1027, 2021.
Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks: Analysis and design. Advances in Neural Information Processing Systems, 34, 2021.
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems, 31, 2018
Yonina C Eldar and Helmut Bolcskei. Block-sparsity: Coherence and efficient recovery. In 2009 IEEE International Conference Acoustics, Speech and Signal Processing, pp. 2885-2888. IEEE, 2009.
Rong Ge, Jason D Lee, and Tengyu Ma. Learning hiehiideen-layrr neural networks with landscape design. arXiv preprint arXiv:1711.00501, 2017.
Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. arXiv preprint 1rXiv:1909, 1205 2019.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832-1841. PMLR, 2018a.
Suriya Gunasekar, Jason Lee. Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. arXiv preprint httf::1806000666 2018b.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 31, 2018c.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234. PMLR, 2016.
Meena Jagadeesan, Ilya Razenshteyn, and Suriya Gunasekar. Inductive bias of multi-channel linear convolutional networks with bounded weight norm. arXiv preprint arXiv:2102. /2238, 2021.
Hui Jin and Guido Montúfar. Implicit bias of gradient descent for mean squared error regression with wide neural networks. arXiv preprint wrXiv:2006.07356 2020.
10

---

Published as a conference paper at ICLR 2023
Li Jing. Jure Zbontar, et al. Implicit rank minimizinn autoencoder. Advances in Neural Information Processing Systems, 15:14736-14745 2020.
Tae Kwan Lee, Wissam J Baddar, Seong Tae Kim, and Yong Man Ro. Convolution with logarithmic filter groups for efficient shallow cnn. In International Conference on Multimedia Modeling, pp- 117-129. Springer, 2018.
Jianguua Li, Thanh Nguyen, Chinmay Hegde, and Raymond K. W. Wong. Implicit sparse regu- larization: The impact of depth and early stopping. Advances in Neural Information Processing Systems, 34, 2021.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterize matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pp. 2-47. PMLR, 2018.
Zhiyuan Li, Tianhao Wang, JasonD Lee, and Sanjeev Arora. Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent. arXiv preprint arXiv:2207. 000000 2022.
Cesare Molinari, Mathurin Massias, Lorenzo Rosasco, and Silvia Villa. Iterative regularization for convex regularizers. In International conference artificial intelligence and statistics, pp-
1684-1692 PMLR, 2021.
Depen Morwani and Harish G Ramaswamy. Inductive bias of gradient descent for weight normalized smooth homogeneous neural nets. In International Conference on Algorithmic Learning Theory, pp. 827-880. PMLR, 2022.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1420-3428. PMLR, 2019.
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of optimization and implicit regularization in deep learning. arXiv preprint arXiv: 2017.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-tnn time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pp. 7695-7705. PMLR, 2020.
Arda Sahiner, Tolga Frgen, John Pauly, and Mert Pilanci. Vector-output relu neural network problems copositive programs: Convex analysis of two layer networks and polynomial-tine algorithms. arXiv preprint arXiv:2012.13322 2020.
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. Advances in neural information processing systems, 29, 2016.
Todd E Scheetz, Kwang- Youn A Kim, Ruth E Swiderski. Alisdair R Philp, Terry A Braun, Kevin L Knudtson, Anne M Dorrance, Gerald F DiBona, Jian Huang, Thomas L Casavant, al. Regulation of gene expression in the mammalian eye and its relevance to eye disease. Proceedings of the National Academy of Sciences, 103(39): (040))1142294333994 2006.
Jonathan Schwarz, Siddhant Jayakumar, Razvan Pascanu, Peter Latham, and Yee Teh. Powerpropaga- tion: A sparsity inducing weight reparameterisation. Advances in Neural Information Processing Systems, 34, 2021.
Daniel Soudry. Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018
Mihailo Stojnic, Farzad Parvaresh, and Babak Hassibi. On the reconstruction of block-sparse signals with an optimal number of measurements, IEEE Transactions on Signal Processing, 57() 3075-3085, 2009.
Twan Van Laarhoven. L2 regularization versus batch and weight normalization. arXiv preprint arXiv:100.0053 05350, 2017.
11

---

Published as a conference paper at ICLR 2023
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. In Advances in Neural Information Processing Systems, pp. 2972-2983, 2019.
Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond lazy training for over-paramettrriee tensor decomposition. Advances in Neural Information Processing Systems, 33:21934-21944, 2020.
Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. Advances neural information processing systems, 32, 2019.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference Learning Theory, pp. 3635-33377 PMLR, 2020.
Xiaoxia Wu, Edgar Dobriban, Tongzheng Ren, Shanshan Wu, Zhiyuan Li, Suriya Gunasekar, Rachel Ward, and Qiang Liu. Implicit regularization and convergence for weight normalization. Advances in Neural Information Processing Systems, 33:2835 2847, 2020.
Xuan Wu, Zhijie Zhang, Wanchang Zhang, Yaning Yi, Chuanrong Zhang, and Qiang Xu. convolutional neural network based on grouping structure for scene classification. Remote Sensing, 13(13):2457, 2021.
Gangcai Xie, Chengliang Dong, Yinfei Kong, Jiang F Zhong, Mingyao Li, and Kai Wang. Group lasso regularized deep learning for cancer prognosis from multi-omics and clinical features. Genes, 10(3):240, 2019.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492-1500, 2017.
Yi Yang and Hui Zou. A fast unified algorithm for solving group-lasse penalize learning problems. Statistics and Computing, 25:1 18::122911100 1141, 2015.
Peng Zhao, Yun Yang, and Qiao-Chu He. Implicit regularization via hadamard product over- parametrization in high-dimensional linear regression, arXiv preprint
2019.
12


Reviews:
[{"review_id": "klM1GDYkxNB", "reviewer": "Reviewer_4y3z", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies \"implicit regularization\", a phenomena in gradient-based optimization algorithms in which the local minima of unregularized cost functions contain properties that one would expect only by adding a regularization term, e.g., sparsity being the most popular one. More precisely, they proposed a reparametrization in which the solution shows \"group sparsity\" structure, which is often obtained by having a elastic net regularization.", "summary_of_the_review": "Well-organized paper with potentially impactful results.", "strength_and_weaknesses": "Strength\n======\n\n- Excellent contextualization of the problem being investigated.\n- Thorough analysis of the proposed reparametrization and the reasons behind its implicit regularization structure.\n- Great numerical analysis showcasing the theorectical development.\n- The analysis in Theorem 1 showing that the gradient dynamics in DGLNN cannot be emulated by mirror descent is interesting and appreciated.\n\nWeaknesses\n=========\n\n- No major weaknesses.\n\nMinor Comments\n=============\n\n- If I were the authors I would be more specific in the title of the paper.  Maybe find a way to introduce \"Neural Networks\" in the title as it is the model being studied here?", "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": "jt_5t3xiVJ", "reviewer": "Reviewer_aL9r", "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": "", "summary_of_the_paper": "The paper studies the implicit bias of gradient descent on diagonal linear networks.\nIt has been lately shown that parametrizing $x$ as $u \\odot v$ in $y \\approx A (u \\odot v)$ induces sparsity in the gradient flow iterates on the least squares loss.\nIn the paper a special architecture is proposed so that gradient descent imposes **group sparsity** on the weights x$.\nThe architecture is a so-called *diagonally-grouped linear neural network* (DGLNN)\nAn analysis is provided under the restrictive assumption of orthogonal design (Theorem 2).\nFor $L$ groups, the proposed parametrization uses two set of variables: scalar ones $u_l$ encoding the magnitude, and vector ones $v_l$ encoding the direction.\n\nGradient flow of the overparametrized objective (Eq 3) is analyzed.\nSection 4 is devoted to a practical version of the gradient flow, gradient descent with weight normalization.\nGuaranties similar to the sparse recovery literature are derived under subGaussianity of the noise (Corollary 1)", "summary_of_the_review": "Interesting idea and result, but valdiation fails to compare to the wealth of existing methods for sparse recovery, including implicit ones.", "strength_and_weaknesses": "Strengths:\n- this is a very active area of research, the contribution is relevant\n- even though the assumptions are strong, there are not so different from classical ones in sparse recovery literature and are a first step to a better understanding of the phenomenon at stake\n\nWeaknesses:\n- the assumption is very strong and unlikely to hold in practice. Testing the behavior of the proposed algorithm on real data to assess the sensitivity to this assumption would be of great interest.\n- comparison with explicit regularization methods is also expected. Implicit bias of mirror descent [2] for group elastic net could also be studied (if the elastic net regularization parameter is sufficiently low, the solution is the same as for group Lasso [2]), as well as iterative regularization methods based on primal dual procedures that can handle non strongly convex bias [4].", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EzDobuLV6-d", "reviewer": "Reviewer_oXvD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors study the theoretical properties of diagonally grouped linear neural networks, and they show that gradient descent over the squared regression loss, without any explicit regularization, biases towards solutions with a group sparsity structure. They conduct some experiments to verify their conclusion.  My main concern is the implications of these results on the modern neural networks are unclear. The reason is that the relationship between the diagonally grouped linear neural networks and the widely used deep neural networks in practice are unclear. Thus, the contribution of this paper is limited.", "summary_of_the_review": " My main concern is the implications of these results on the modern neural networks are unclear, which weakens the contributions of this paper. ", "strength_and_weaknesses": "Strength:\n\n1. This paper is well written and easy to read. \n\n2. Some theoretical results in this paper are interesting. \n\n\nWeaknesses:\n\n1. As we know deep learning theory studies aim at understanding the modern neural networks in practice. The authors need to discuss the relationship between their results, such as the group sparsity structure,  and the observations of deep neural networks in practice.\n\n2. In this paper, the authors focus on the diagonally grouped linear neural network, compared with the existing work, the authors need to explain more on the relationships between their structure and the ones in the modern neural networks. The grouped CNNs the authors mentioned are not the widely used neural network in practice. The authors are also recommended to specify the relationship between the structure of their model and grouped CNNs, such as where one can be reduced to another by using some specific settings.\nThe above limitation makes the contribution of this paper limited. \n\n3. Can the authors show some experimental results to demonstrate that their findings also exist in the neural networks in real applications.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster