Implicit Bias of Linear Equivariant Networks
Authors: Hannah Lawrence
Kristian Georgiev
Andrew Dienes
Bobak Kiani
Venue: ICLR 2022 Submitted (2022)
Keywords: Implicit bias
equivariance
deep learning
linear networks
convolution
CNN

Abstract: Group equivariant convolutional neural networks (G-CNNs) are generalizations of convolutional neural networks (CNNs) which excel in a wide range of scientific and technical applications by explicitly encoding particular group symmetries, such as rotations and permutations, in their architectures. Although the success of G-CNNs is driven by the explicit symmetry bias of their convolutional architecture, a recent line of work has proposed that the implicit bias of training algorithms on a particular parameterization (or architecture) is key to understanding generalization for overparameterized neural nets. In this context, we show that $L$-layer full-width linear G-CNNs trained via gradient descent in a binary classification task converge to solutions with low-rank Fourier matrix coefficients, regularized by the $2/L$-Schatten matrix norm. Our work strictly generalizes previous analysis on the implicit bias of linear CNNs to linear G-CNNs over all finite groups, including the challenging setting of non-commutative symmetry groups (such as permutations). We validate our theorems via experiments on a variety of groups and empirically explore more realistic nonlinear networks, which locally capture similar regularization patterns. Finally, we provide intuitive interpretations of our Fourier-space implicit regularization results in real space via uncertainty principles.

Under review as a conference paper at ICLR 2022
IMPLICIT BIAS OF LINEAR EQUIVARIANT NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Group equivariant convolutional neural networks (G-CNNs) are generalizations of convolutional neural networks (CNNs) which excel in wide range of scientific and technical applications by explicitly encoding group symmetries, such as rota- tions and permutations, in their architectures. Although the success of G-CNNs is driven by the explicit symmetry bias of their convolutional architecture, recent line of work has proposed that the implicit bias of training algorithms on a partic- ular parameterization (or architecture) is key to understanding generalization for overparameterized neural nets. In this context, we show that L-layer full-width linear G- G-CNNs trained via gradient descent in binary classification task con- verge to solutions with low-rank Fourier matrix coefficients, regularized by the 2/L-cchateen matrix norm. Our work strictly generalizes previous analysis on the implicit bias of linear CNNs to linear G-CNNs over all finite groups, including the challenging setting of non-commutative symmetry groups (such as permutations), as well as hand-limited G-CNNs over infinite groups. We validate our theorems via experiments on a variety of groups and empirically explore more realistic non- linear networks, which locally capture similar regularization patterns. Finally, we provide intuitive interpretations of our Fourier space implicit regularization results in real space via uncertainty principles.
INTRODUCTION
Modern deep learning algorithms typically have many parameters than data points, and their ability to achieve good generalization in this overparameterized setting is largely unexplained by current theory. Classic generalization bounds, which bound generalization errors when models are not overly "complex," are vacuous for neural networks that can perfectly fit random training labels (Zhang et al., 2017). More recent work analyzes the complexity of deep learning algorithms by in- stead characterizing the properties of the functions they output. Notably, prior work has shown that training via gradient descent implicitly regularizes towards certain hypothesis classes with low complexity, which may generalize better as a result. For example, in underdetermined least squares regression, gradient descent converges to the f--n minimizer, while a ppintwise-squar reparametrization converges to the f--nrmm minimizer (Gunasekar et al., 2018at 8a). Such phenom- ena are consistent with certain linear neural networks, egg. Gunasekar et al. (2018b) showed that learned linear fully-connected and convolutional networks implicitly regularize the & norm and a depth-dependent norm in the Fourier space respectively.
From a more applicd perspective, large body of work imposes structured inductive biases on deep learning algorithms to exploit symmetry patterns (Kondor, 2007; Reisert, 2008; Cohen & Welling, 2016b). One prominent method parameterizes models over functions that equivariant with re- spect to a symmetry group (i.e., outputs transform predictably in response to input transformation). In fact, Kondor & Trivedi (2018) showed that any group equivariant network can be expressed as a series of group convolutional layers interwoven with pointwise nonlincarities, demonstrating that group convolutional neural networks (G-CNNs) are the most general family of equivariant networks.
The explicit inductive bias of G-CNNs is the main reason for their usage. Yet, to the best of our knowledge, the implicit bias imposed by equivariant architectures has not been explored. Here, we greatly generalize the results of Yun et al. (2020) and Gunasekar et al. (201 8b) to linear G-CNNs whose hidden layers perform group equivariant transformations.
Our Contributions:
show, sur- prisingly, that L-layer G-CNNs implicitly regularized by the 2/ L-L-chatt norm, which is the 2/ L norm of matrix's 's singular values, over the irreducible representations in the Fourier basis. As

---

Under review as a conference paper at ICLR 2022
8.0
173
CNN FC
15.0
12.
CNN
18
10.0
FC
5.0
6.0
epoch
spoch
Fourier space norm of network linearization 3
(b) Real space norm of network lincarization, B
Figure 1: Training via gradient descent of linear G-CNNs (with linearization (3) implicitly biases towards sparse singular values for Fourier matrix coefficients of 3 (see Theorem 1). Figure 1a traces the Dg Fourier space sparsity over the course of training three architectures in overparameterized classification task. The G-CNN converges to Fourier-sparse linearization in contrast with fully- connected and convolutional networks. Figure 1b illustrates the uncertainly principles discussed in Section 6 which show that sparseness (group) Fourier space necessitates being "dense" real space, and vice versa. See Appendix D for more visualizations of the implicit bias.
a result, convergence is biased towards sparse solutions the Fourier regime, as summarized below and illustrated in Figure la, well as further experiments in Section 6.
Theorem (main result; informal). Let NN2(-) denote an L layer linear group convolutional neural network, in which each hidden layer performs group cross-correlation over the group G with a full-width kernel and the final layer is fully connected layer. When learning linearly separable data {x,, Ys Jiiiz1 using the exponential loss function, the network converges in direction to a linear function N (z) x B x. where [3 given by the following minimization problem:
(8)
min
y
[n
B
2/L
where |
(8)
12 denotes the 2/ L-Schatte norm of the matrix Fourier transform of B (see Defini- tion 4) equivalent
de (1110) (8) 2/ L/2
3 2/4
dd Lee@
(2)
2/1
where G is a complete of unitary irreducible representations of G and dp is the dimension of irreducible representation p.
note that both sparsity (for vectors) and low-rankness (for matrices) are desirable properties for many applications, not least because such predictors efficient to store and manipulate, thus po- tentially expanding the scope of application of G-CNNs to arcas where sparsity and low-rankness explicitdesiderata.c Connecting our findings to rescarch uncertainty theorems (Wigderson & Wigderson, 2021) we also show that the implicit regularization towards sparseness (or low rank irre- ducible representations) in the Fourier regime necessarily implies that solutions in the real regime "dense," as illustrated in Figure lb. These results provide a more intuitive and practical perspective into the inductive bias of G-CNNs and the types of functions that they learn.
We proceed as follows. In Section 2, we discuss related works and their relation to our contribu- tions. In Scction 3, define notation. Scction 4 provides basic background in the group thcory and Fourier analysis necessary to understand our results. Our main results are stated in Section 5, with the main proof ideas for the abelian (or commutative) and non-abelian (or nom-commutative) cases given in Subsection 5.1 and Subsection 5.2, respectively (complete proofs can be found in Appendix A). Section validates our theoretical results with synthetic experiments on a variety of groups and exploratory experiments validating theory non-linear networks. Finally, discuss these results and future questions Section 7.

---

Under review as a conference paper at ICLR 2022
2
RELATED WORK
Enforcing equivariance and symmetries via parameter sharing schemes was introduced in the group theoretic setting in Cohen & Welling (2016a) and Gens & Domingos (2014). Despite considerable interest in equivariant learning, to the best of our knowledge, no works have explored the implicit regularization of gradient descent on equivariant convolutional neural networks. We show that the tensor formulation of neural networks in Yun et al. (2020) and the proofs in Gunasekar et al. (20188) encompass G-CNNs for which the underlying group is cyclic and naturally extend to G-CNNs over any commutative group (sec Subsection 5.1). However, these works do not cover the case of convo- lutions with respect to non-commutative groups, such as tions, which incidentally include some of the most compelling applications of group equivariance in practice (Zaheer et al., 2017; Anderson et al., 2019; Esteves et al., 2018). As such, articulating the implicit bias in the more general non-abelian case important for understanding many of the current group equivariant architectures (Zaheer et al., 2017; Kondor et al., 2018; Esteves et al., 2018; Weiler & Cesa, 2019). However, non-abelian convolutions require more structure theoretically analyze compared to abelian convolutions: the former are merely pointwise multiplications in Fourier space, whereas the latter requires matrix multiplication over irreducible representations which cannot be expressed in the tensor language of Yun et al. (2020). Instead, we use standard optimization tools and comparable convergence assumptions from the work of Gunasckar et al. (2018b) to explicilly characterize the stationary points of convergence for non-abelian G-CNNs.
rotations and permuta-
We also note that our results are consistent with the results of Razin & Cohen (2020) showing that implicit generalization is often captured by measures of complexity which quasi-norms such as tensor rank. Our results prove that linear G-CNNs are biased towards low rank solutions in the Fourier regime, via regularization of the L/L-Schatten norms over Fourier matrix coefficients (also a quasi-norm). Lastly, there is a line of work focusing on understanding the expressivity (Kon- dor& & Trivedi, 2018: Cohen et al., 2019; Yarolsky, 2021) and generalization (Sannai & Imaizumi, 2019; Lyle et al., 2020; Bulusu et al., 2021; Elesedy & Zaidi, 2021) of equivariant networks but not specifically the effects of implicit regularization.
To analyze bounded-width filters, which are more commonly used in practice, a recent work by Ja- gadeesan et (2021) shows that the implicit regularization for an arbitrary filter width K unlikely to admit dosed-form solution. Separate from calculating the exact form of implicit regularization, there is a rich line of work that details the trade-offs between restricting a function its real ver- sus Fourier regimes via uncertainty principles (Meshulam, 1992; Wigderson & Wigderson, 2021). While the connection between uncertainty thcorems and bounded-wil width convolutional neural net- works has not been thoroughly explored, Caro et al. (2021) and Nicola & Trapasso (2021) highlight the importance of uncertainty principles for understanding the behaviour of modern CNNs.
NOTATION
Throughout this text, we denote scalars in lowercase script (a), vectors bold lowercase script (a), matrices in either bold uppercase script (A) or lowercase script hat (@) when vectors are transformed into the Fourier regime (see Definition 4.1), and tensors bold non-italic uppercase script (A). For a function with range in C, we overload notation slightly and let f denote the function with an element-wise complex conjugate applied, i.e. f(x) = f(z). If f is defined on a group G, let (g) = -[q- -1). For a vector E C or a matrix A E Cmxn, we denote its conjugate transpose as a' and A respectively. We use ( to denote the standard vector inner product between two vectors and (., +)M to denote the inner product between matrices defined as (A, B)
tr)).. We use ||- |pp to denote the vector p-norm (p- = 2 when subscript is hidden) and ||- || to denote the p-Schatten norm' of a matrix (equivalent to the p-vector norm of the singular values of the matrix).
We denote groups by uppercase letters G. We denote an irreducible representation (irrep) of a group G by p or p; and a complete set of irreps as G. every unitary irrep p is equivalent (up isomorphism) exactly one element of G. The dimension of given irrep p is dp-
Despite our terminology, p-vector and p-Schatten norms are technically quasi-norms for < 1.

---

Under review as a conference paper at ICLR 2022
91
Blni
92
h
FM
hips
9.0 hyo
Figure 2: Cross-corcelation of two functions over a group is equivalent to matrix multiplication over
irreps (shown as blocks of a larger matrix here) Fourier space.
4 BACKGROUND IN GROUP THEORY AND GROUP-EQUIVARIAN CNNS
In this study, we analyze linear G-CNNs in a binary classification setting, where hidden layers perform equivariant operations over finite group G, and networks have no nonlinear activation function after their linear group operations. Inputs 2; are vectors of dimension |G] (i.e., vectorized group functions G IR,, and targets y; scalars taking the value of either +1 or 1. Hidden layers in our G-CNNs perform cross-correlation over group G, defined as
(g * h1) = ( Eg(ur)h(u
oEG
Note, that the above is equivariant to the left action of the group, i.e., if E and (u) g then (g', (u) = (g (wu). The final layer of our G-CNN is a fully connected layer mapping vectors of length |G] to scalars. We note that this final layer general will not construct functions that are symmetric to the group operations, strictly enforcing symmetries in this linear setting will result in trivial outputs (only scalings of the average value of the input). Nonetheless, this model still captures the composed convolutions of practical G-CNNs, and exhibits non-trivial implicit bias.
Analogous to the discrete Fourier transform, there exists a group Fourier transform mapping func- tion into the Fourier basis over the irreps of G.
Definition 4.1 (Group Fourier transform). Let : G Given a fixed ordering of G, ea be the standard basis vector R2G that functioon
the location of and elsewhere. Then,
Ener fuu)e is the vectorized function f. Given G Ga complete set of unitary irreps of G, let E G
be a given irrep of dimension dp. :: G -> GT. (dp. C). The group Fourier transform of f. f. G + C at representation p is defined as (Terras, 1999)
Flp) = I())p()).
(4)
wEG
By choosing a fixed ordering of G,, one can similarly construct of as block-diagonal matrix version of i (as in Figure 2). We define FM to be the matrix Fourier transform that takes f to f:
f = FM
+ f(p) E GLL ([G), C).
(5)
PE
I or F ff are shortened notation for the complete Fourier transform. Furthermore, by vectorizing the matrix f. there is unitary matrix F taking f f. analogous to the standard discrete Fourier matrix. We use the following explicit construction of F: denoting @pp.i,1l as the column-major vectorized basis for element Pıj in the group Fourier transform, then can form the matrix
dp
F-ΣΣ
Σ plu)seeppssee
(6)
VIGI
MEG PEG
Intuitively, for each group element the matrix F contains all the irrep images p(g) 'flattened' into single column. See Appendix B for further exposition.
Convolution and cross-correlation are equivalent, up to scaling, to matrix operations after Fourier
transformation. For example, in the case of cross-correlation (Equation 3), (g h)(p) (p))( This simple fact, illustrated in Figure 2, is the basis for the proofs of our implicit bias results.
NNote that for an abelian group, d, = Vp. For standard Fourier analysis over the cyclic group, each p is complex sinusoid at some frequency.

---

Under review as a conference paper at ICLR 2022
5
MAIN RESULTS
We consider linear group-convolutioall networks for classification analogous to those of Yun et al. (2020) and Gunasekar et al. (2018b). A linear G-CNN is composed of several group cross- correlation layers followed by a fully connected layer. The input is formalized the group (according to some pre-defined ordering of elements), a G - IR, and the output is a scalar. Explicitly, let G be finite group with wT, .... Wr real-valued functions from G to R. W 1: wz) - (æ, B3. Let W = [wi ... w.. be the concatenation of all network parameters, and ß = P(W) = ty L ..... i be the "end-to-endd" linear predictor consisting of composed cross-correlation operations. One can check (as we do in Lemma A.1) that 3 & FM WL.. wi. Networks are trained via gradient descent over the exponential loss function linearly separable data {x,, ) Iterates take the form
function on
The network output is NN(x)
(æz *
((+1) w( net V ((,,()((W))
where (((x,B),)) -xxp((t)) y) and 2(3) Σ E((x,; B), v1).
5.1 ABELIAN
Similar to ordinary (cyclic) convolution', the commutative property of abelian groups implies that convolutions in real space are equivalently pointwise multiplication of irres in Fourier space since all irreps are one-dimensional for commutative groups (d, = 1Vp). To start, recall the key definition of Yun et al. (2020), determining which network architectures fall within the purview of their results:
Proposition 5.1 (paraphrased from Yun et al. (2020)). Ler M(x) be a map from data C Rd to a data tensor M(x)) E R& xx2xx.-xx- .x.,, The input into an L-layer tensorized neural network can be written orthogonally decomposable data tensor if there exists full column rank matrix E I xd and semi-unitary matrices UI,..., UL E CRex where d S m S mine ke such that:
M (x)
Σ Sæl (UI) @ (12) 8 ... . &UL).)),
(8)
such that the network output the tensor multiplication between M(x) and each layer's parameters:
d
NN(x; θ) = M(x) (w1, WL)
M(z)e (wi).. (WL)a
Indeed, a linear G-CNN over an abelian group can be expressed in a way that satisfies Proposi- tion A.3 for an appropriate choice of S and UI,..., UL, as stated in the following proposition.
Proposition 5.2. Let M(x) be orthogonally decomposable data tensor with associated matrices S, S.U..... UL as in Proposition 5.1. Given a finite abelian group G, let d = m = b = |G] and F Cdxd be the group Fourier transform of G (see Definition 4.1). With S d F. unitary matrices U, = F Fi, and the data tensor M(x) defined correspondingly, the output of a G-CNN with real-valued filters Wi,..., WT, is tensor operation:
M(x)) (W), Wt. = (xc * * .... WT W1.)
The proof is deferred to Appendix A. Fundamentally. the result requires not only that F is unitary, which holds for all finite groups, but also that cross-correlation is pointwise multiplication (up conjugate transpose) in Fourier space, i.c. F(x w) (Fx) O (Fw)1. 1, This property only holds for commutative groups, as matrix multiplication pointwise multiplication only for matrices of dimension dp = 1. Given Proposition 5.2, we apply the implicit bias statement of Yun et al. (2020).
Theorem 5.3 (Implicit regularization of linear G-CNNs for G an abelian group). Suppose there exists À 0 such that the initial directions WI,..., Wt of the network parameters satisfy
'In fact, we include a canonical result in the appendix. Theorem A.4, demonstrating that all finite abelian groups are direct products of cyclic groups, ie. multidimensional translational symmetries.

---

Under review as a conference paper at ICLR 2022
Xfr [[ 2 all [L-1] and E [m], i.e. ife Fourier transform magnitudes of the initial directions look sufficiently different pointwise (which occurs with high probability for e.g. Gaussian random initialization). Then, (3 -P(W),.... wr]) converges direction that aligns with stationary point z of the following optimization program:
min =ECm
|F2lla/D s.t. y, z) 2 1, Vi e [n)
(9)
As noted in Theorem A.4 of the Appendix, all finite abelian groups can be expressed as a direct product of cyclic groups. In contrast, many groups (rotations, subgroups of permutations, etc.) with much richer structure are non-commutative, and we now turn our attention to the non-abelian case.
5.2 NON-ABELIAN
In Fourier space, non-abelian convolution consists of matrix multiplication over irreps, and do not fit the pointwise multiplication structure of Proposition 5.2. We instead build upon the results of Gunasekar al. (2018b), and directly analyze the stationary points of the proposed optimization program to prove the following:
Theorem 5.4 (Non-abelian; see also Theorem A.5). Consider a classification task with ground-truth linear predictor B3, trained via linear G-CNN architecture with L > 2 layers under the exponential loss. For almost all separable datasets {I.: ys 1.>r-- any bounded sequence of step sizes TJ, and almost all initializations: if the loss converges 0, the gradients converge in direction, and the iterates themselves all converge in direction to a classifier with positive margin, then the resultant predictor is a scaling of a first order stationary point of the optimization problem:
min B
1111622 (5)
S. Vnn Vn (D0 B3 2 1.
(10)
To prove the above statement, we show that linear G-CNNs converge stationary points of the KKT conditions above, which is also the high-level method of Gunasekar et al. (2018b). However, our proof differs in several key ways from that of Gunasekar al. (2018b). First, redefine operations of the G-CNN as a series of inner products and cross-correlations over the space of the matrix Fourier transform of Definition 4.1. Second, in this Fourier space, we analyze the subdifferential of the Schatten norms to ultimately show that the KKT conditions of Equation 10 are satisfied. In contrast, Gunasekar al. (2018b) analyze the subdifferential of different objective, the ordinary 2/L-vector norm. The fact that the irreps of a group are only unique up to isomorphism (e.g., conjugation by a unitary matrix) aids in identifying this Schatten norm as the correct regularizer, since Schatten norms are invariant to unitary matrix conjugation. These features are specific to the non-abelian case. More specifically, the proof of this result follows the outline below:
1. First, by applying general result of Gunasekar et al. (2018b), Theorem A.6, we char- acterize the implicit regularization in the full space of parameters, W (in contrast to the end-to-end linear predictor (3), as a (scaled) stationary point W of the following opti- mization problem in W:
| s.t. Un. P(W)) 21 WERP
min
(11)
2. Separately, we define distinct optimization problem, Equation 10, in B3 show that sta- tionary points of Equation 11 are subset of those of Equation 10, up to scaling.
3. The necessary KKT conditions for Equation 11 characterize its stationary points:
3ian on
0) an =0 if yn yn P(W
(12)
w V w. P(W
Σ anyhron
V un ((W
Σ CnnYn
From here, we show that the sufficient KKT conditions for Equation 10 are also satisfied by the corresponding end-to-end predictor. particular, we calculate the set of subgradients'
@ (8) for = 1 < 1, and then use Equation 12 to derive recurrences demonstrating
that positive scaling of Σn On Hn is a member of this set.
$00 is the local subgradient of Clarke (1975): 8 J [(3) = conv < vs(B + h.) h: 0+

---

Under review as a conference paper at ICLR 2022
Remark. For abelian groups where all irreps are one-dimensional, (3 in Theorem 5.4 is diagonal matrix. Thus, the p-Schatten norm coincides with the p-vector norm of the diagonal entries, recov- ering results in Subsection 5.2. However, Theorem 5.4 requires stronger convergence assumptions.
Infinite dimensional groups: Theorem 5.4 applies to all finite groups, but G-CNNs have extensive applications for infinite groups, where outputs of convolutions are infinitedimensionall Here, common to assume sparsity in the Fourier coefficients and "band-limit" filters over set of low- frequency irreps (under some natural group-specific ordering) that form finite dimensional linear subspace (we denote the representation of function in this band-limited Fourier space as Ti.) Here, G-CNNs with band-limiteh filters take precisely the form of the finite G-CNNs from Theorem 5.4. Thus, slightly modifications yield the following for infinite groups (see Appendix A.2.1 for details).
Corollary 5.5 madinite-dimensione groups with band-limited functions; see also Theorem A.11).
Let G be compact Lie group with irreps G, and let B C G with [B] < oa. Proceed fully in Fourier space, in the subspace corresponding to B: consider a linearly separable classification task with ground-tre
linear predictor 3 and inputs E, both real-valued and supported only on irreps in B, and proceed by gradient descent on the band-limited Fourier-space filters. Under near-identical conditions as Theorem 5.4, the resultant predictor is scaling of a first order stationary point of:
(S)
Vn, Vn ( (In. 3 1.
min 8
s.t.
(13)
2/L
6 EXPERIMENTS
Here, we first experimentally confirm our theory in a simple setting illustrating the effects of implicit regularization. Then, we relax the crucial assumption of linearity in our setup empirically show that our results may hold locally even in nonlinear settings. Note that the results for nonlinear networks in Subsection 6.2 are only empirical in nature, and Theorems 5.3 and A.5 do not necessarily hold in the more general nonlincar setting. For all binary classification tasks, we use three-layer networks with inputs and convolution weights in IR [ Since we are interested in the resulting implicit bias alone, we only analyze loss on data in the training set. A complete description of our experimental setup can be found in Appendix E.
Throughout this section, we plot norms in the Fourier and real regimes side-by-side to highlight un- avoidable trade-offs in implicit regularization between the two conjugate regimes. These trade- offs, which have a rich history of study physics and group theory, are commonly termed uncertainty principles (Wigderson & Wigderson, 2021). One especially relevant uncertainty theorem states that sparseness in the real or Fourier regime necessarily implies dense support the conjugate regime. Theorem 6.1 (Meshulam uncertainty theorem (Meshulam, 1992)). Given finite group G and f G --0 C, let & be the set of irreps of G and be the vectorized function (see Definition 4.1) Then
sfpp(f) rank(5 f)) = supp(f))
Σ d, rank (F(e) 2G
(14)
PEG
Other related uncertainty principles are detailed in Appendix C.
6.1 EMPIRICAL CONFIRMATION OF THEORY
Here, trace the regularization through (training) epochs via analysis over three groups which are all trained to classify data with #1 labels:
Dy (Figure 1): The dihedral group Dş is a simple non-abelian group that captures the geometry of a square". Inputs are vectors with clements drawn i.i.d. from (0, 1).
(Os x Ct) x Qs (Figure 3): A non-abelian group that has irreducible representations of up to dimension 8 displays implicit regularization over a more elaborate group structure. Inputs are vectors with elements drawn i.i.d. from the standard Normal distribution.
'For example, G = SO(3) and B indexes all Wigner d matrices with | S L (Kondor al., 2018).
"We use the convention that D., is the dihedral group of order n.

---

Under review as a conference paper at ICLR 2022
(C2a C28) Ds (Figure 4): A non-abelian group which acts images (the digits and 5) from the MNIST dataset.
In three settings above, we compare the behaviors of G-CNN, traditional CNN', and fully- connected (FC) network architectures with similar instantiations. We plot the the real space vector norm and Fourier space Schatten norm of the network linearization over training epochs. All mod- els perfectly fit the data in this overparameterized setting, and convergence solution corresponds to convergence in the loss to zero.
given regularized
Consistent with theory, G-CNN architectures shown in Figures 3, and 4 have the smallest Fourier space Schatten norms among the architectures. FC networks exhibit no group Fourier regime regu- larization while standard CNNs exhibit some regularization since they share some irreducible rep- resentations with the G-CNN. The differing behaviors of CNNs and FC networks show that implicit regularization is a consequence of the choice of architecture and not inherent the task itself.
200
1800
180
CNN
170
G-CNN
1000
CNV
160
FC
CNN
FC
150
140
0
spoch
spoch
Fourier space norm of network linearization 3
(b) Real space norm of network linearization B
Figure 3: Norms of the linearizations of three different linear architectures for the non-abelian group
G (Cs Cs) x Qs trained on binary classification task with 10 isotropic Gaussian data points.
3200
380000
360000
CNN
340000
G. CNN
CNN
C-ONN
4300
280000
4200
20
10
60
80
100
0
20
10
80
80
100
epoch
epoch
(a) Fourier space norm of network linearization 3
(b) Real space norm of network linearization 3
Figure 4: Norms of the linearizations of three different linear architectures for the non-abelian group
G (C2s C2s) x Dş trained using the digits 1 and 5 from the MNIST dataset.
6.2 ASSESSMENT THEORY NONLINEAR NETWORKS
Here introduce rectified linear unit (ReLU) nonlinearities between hidden layers to analyze im- plicit bias in the presence of nonlincarity. Our thcoretical results do not necessarily hold this casc,
exploring, rather than confirming, their validity for nonlincar networks. Accord- ingly, given a G-CNN with ReLU activations, we wish to calculate the Schatten norm the Fourier matrix coefficients of the network linearization B3. However, networks
longer be collapsed into linear functions due to the nonlincarities. Instead, we construct local linear approximations at each data point via a first-order Taylor expansion, calculate the norms of interest according to this lincarization, and average the results across the datasct to get a single aggregate value. We evaluate the implicit bias of an invariant ReLU G-CNN (with final pooling layer) with respect to translations,
We generically use "CNN" to refer to a G-CNN over the cyclic group of size equal to the size of the input.

---

Under review as a conference paper at ICLR 2022
rotations, and flips MNIST digits, and nonlinear G-CNN (with linear final layer) the dihe- dral group DEo with synthetic data. Note that we use linear approximations only to analyze implicit regularization, and not further interpret the outputs of the locally linear neural network, such analysis can give rise to misleading or fragile feature importance maps (Ghorbami et al., 2019).
Remarkably, as shown in Figures 5a and 5b, our results remain valid in this nonlinear setting. While this docs not guarantee that our implicit bias charactcrization will hold in more general scttings, it an encouraging sign that our theoretical results handle the violation of the lincarity assumption, least numerically. Additional figures detailing the real-space behaviour are provided in Appendix E.
G-CNN
325
1200
300
275
1100
1
200
1000
225
900
200
ReLU CNN
175
RuLU FC
20
100
opoch
spoch
(a) Fourier space norm for (C28 x C2s) x Ds
(b) Fourier space norm for D60
Figure 5: Group Fourier norms for nonlinear architcctures with ReLU activations show that non- linear G-CNNs seem to implicitly regularize locally. Both figures track the mean norm of the per- sample local linearizations of each network. The networks in Figure 5a use pooling layer after the convolutional layers to maintain invariance. Figure 5a evaluates binary classification task using MNIST digits 0 and 5. Figure 5b obtained on networks with a final linear layer, and evaluates binary classification task with 10 isotropic Gaussian data points.
DISCUSSION
In this work, we have shown that L-layer linear G-CNNs with full width kernels are biased towards sparse solutions in the Fourier regime regularized by the 2/ 2/L-cchatten norm over Fourier matrix coefficients. Our analysis applics to lincar G-CNNs, over finite groups (or infinite groups with band-limited inputs), trained in the task of binary classification. In advancing results implicit regularization, we highlight some limitations of our work and important future directions:
Nonlinearities: Adding nonlinearities to the G-CNNs studied here expands the space of functions which the G-CNNs can express, but implicit regularization this nonlinear set- ting may be challenging to characterize as G-CNNs are no longer linear predictors. Local analysis may be possible in special cases, e.g. in the infinite width limit (Lee al., 2017).
Bounded width kernels: Our results apply to full-width kernels with support on the whole space of group operations. Expanding results to bounded-wind kemnels, i.e., those with sparse support, is an obvious future direction, though prior work has indicated that closed form solutions may not exist for these more special cases (Jagadeesan et al., 2021).
Different loss function and learning settings: The loss function studied here is the ex- ponential loss function used binary classification tasks. Beyond binary classification, it is an open question how the implicit regularization changes for classification over more than two classes, not only for G-CNNs but for other re-parametrizations like CNNs and fully-connected networks as well (Gunasekar et al., 2018b).
Although concise implicit regularization measures are challenging to analyze for realistic, nonlinear architectures. linear networks provide an instructive case study with precise analytic results. In this work, by proving that linear group equivariant CNNs trained with gradient descent are regularized towards low-rank matrices in Fourier space, we hope to advance the broader agenda understanding generalization, and in particular how and why networks with diverse architectures particularly those with built-in symmetries - learn.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Brandon Anderson, Truong-Son Hy, and Risi Kondor. Cormorant: Covariant Molecular Neural Networks. Curran Associates Inc., Red Hook, NY, USA, 2019.
Srinath Bulusu, Mattco Favoni, Andreas Ipp, David Müller, and Daniel Schuh. Generalization ca- pabilities of translationally equivariant neural networks. arXiv preprint Stii::2003.166888 2021.
Josue Ortega Caro, Yilong Ju, Ryan Pyle, Sourav Dey, Wieland Brendel, Fabio Anselmi, and Ankit Patel. Local convolutions cause an implicit bias towards high frequency adversarial examples, 2021.
Frank H Clarke. Generalized gradients and applications. Transactions of the American Mathemati- cal Society, 205:247-26 1975.
Taco S. Cohen and Max Welling. Group equivariant convolutional networks. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML'16, 16, pp. 2990-2999. JMLR.org, 2016a.
Taco Cohen and Max Welling. Group Equivariant Convolutional Networks. arXiv, 2016b.
Taco S Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant cnns on ho- mogencous spaces. H. Wallach. H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 32. Curran As- neurips....... cct/papee/2019/E// pdf.
sociates, Inc., 2019. URL ht.ps:::pps..cm......m.. hRLtttss: h/ttctpp://proccedd.ng.... b9cfe8b6042cf 9
David L Donoho and Philip Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics, 4963)990-9931 1989.
David Steven Dummit and Richard M Foote. Abstract Algebra, volume 3. Wiley Hoboken, 2004.
Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models.
arXiv preprint arXiv:2102.1033: 2021.
Carlos Esteves, Christine Allen Allen-Blanchette, Ameesh Makadia, and Kostas Daniilidis. Learning so(3) equivariant representations with spherical cnns. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018.
Robert Gens and Pedro M Domingos. Deep symmetry networks. Advances in neural information processing systems, 27:2537-2545, 2014.
Amirata Ghorbani, Abubakar Abid, and James Zou. Interpretation of neural networks fragile. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 3681-3688, 2019.
Suriya Gunasckar, Jason Lec, Daniel Soudry, and Nathan Srebro. Charactcrizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1832-1841, PMLR, 10-15 Jul 2018a. URL http: httpp/pooceednsss////. mlr.press. / v80 gww.gekaaaaaaeeeemm 8a. html.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient de- scent on linear convolutional networks. In S. Bengio, H. Wallach, Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018b. URL http:: http://poceeeeenneeeeece neurips.co. paper/2018 file/ 9898ebb 4aff 2aaaaeaaaaac22222220444444222222
Paper.pdl
Meena Jagadeesan, Ilya P. Razenshteyn, and Suriya Gunasekar. Induetive bias of multi-channel linear convolutional networks with bounded weight norm. CoRR, abs/2102.122338 2021. URL
https: http//xxvvvv//. borg/al hlag//a//// 22002.22222..2 12238.
Risi Kondor. A novel set of rotationally and translationally invariant features for images based on the non-commutative bispectrum. arXiv preprins cs/0701 2007.
10

---

Under review as a conference paper at ICLR 2022
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups, 2018.
Risi Kondor,
Zhen Lin, and Shubhendu Trivedi. Clebsch-gordan nets; fully fourier space spherical convolutional neural network. Advances in Neural Information Processing Systems, 31:10117 10126, 2018.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstcin. Deep neural networks as gaussian processes. arXiv preprint arXiv: 17110006, 2017.
Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.00178. 2020.
Ewa Matusiak, Murad Özaydin, and Tomasz Przebinda. The donoho-stark uncertainty principle for finite abelian group. Acta Math. Univ. Comenianae, 73(2):155-16) 2004.
Roy Meshulam. An uncertainty inequality for groups of order pq. European journal of combina- forics, 13(5):401-400) 1992.
Fabio Nicola and S. Ivan Trapasso. On the stability of deep convolutional neural networks under irregular or random deformations, 2021.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. In Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 21174-21187. Curran As- sociates, Inc., 2020. URL https: httpttpdpp//proooeinggg... wwtpnnss.ccpppppeeee//e/.e.ee ffiee/ pdf.
f21e255f89ed F2 wcc.ceeeeeeeeeeeeeeeee
Marco Reisert. Group integration techniques in pattern analysis-a kernel view. 2008
Akiyoshi Sannai and Masaaki Imaizumi. Improved generalization bound of group invari- ant/equivariant deep networks via quotient feature space. arXiv preprint arXiv: 1910.0655, 2019.
Audrey Terras. Fourier analysis finite groups and applications. Number 43. Cambridge Univer- sity Press, 1999.
G Alistair Watson. Characterization the subdifferential of some matrix norms. Linear algebra and its applications, 170(0):33-45, 1992.
Maurice Weiler and Gabriele Cesa. General Equivaauia Steerable CNNs. In Conference on Neural Information Processing Systems (NeurIPS). 2019.
Avi Wigderson and Yuval Wigderson. The uncertainty principle: variations theme. Bulletin of the American Mathematical Society, 58(2):225-261,200 2021.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, pp. 1-68, 2021.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. unifying view on implicit bias training linear neural networks. CoRR, abs/2010.02501, 2020. URL htttts://aaxiii 2010. 02501.
abs/
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnaaa Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in Neural Information Processing Systems, 30, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking gencralization. 2017. URL 1611. 03530.
11


Reviews:
[{"review_id": "tsWTCG-eUEJ", "reviewer": "Reviewer_Mfmn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Strength: Focusing on the non-explicit bias of G-CNN, the results of the analysis are satisfactory.\n\nWeaknesses: I do not see anything special about it.\n\nQuestions:\nFrom a theoretical point of view, we would like this kind of result to include the case where the group does not do group convolution as a case where the group is trivial. What does Theorem 1 imply when the group is trivial?\\\n\nIt would be great if this kind of result could provide some insight in analyzing over parametrized FNN. When we regress the G-equivariant function on an over parametrized FNN, can your results give any insight?\\\n\nThis result was for finite groups, but there are also convolutions for geometric groups, such as Lie conv. Please tell us about the part of this result where the finite group assumption works and give us some insight into the generalization to Lie groups.\n\nAfter the revision, the paper was improved, for example by generalization to the Lie group, but in the main the assessment did not change significantly, resulting in the following scores\n\n", "summary_of_the_paper": "Because of the explicit inductive bias of G-CNN, other inductive biases have not been discussed much.\nIn this paper, the author focuses on and analyzes the non-explicit inductive bias of G-CNNs.\nTechnically, they present the non-explicit bias in terms of Fourier matrices by using a group Fourier transform, which depends on the group structure.\nThe results show that learning a linear G-CNN (with linearized β) by gradient descent implicitly biases the singular values of the Fourier matrix coefficients of β to be sparse.\nThis result has been experimentally confirmed in linear and some nonlinear situations.", "summary_of_the_review": "Basically, this paper is theoretically well done. The assumption of linearity is a strong one that is far from reality, but it is a reasonable assumption for the current theoretical analysis, and it is confirmed by experiments in the nonlinear case. Overall, I think this is a worthwhile paper.", "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": {}}, {"review_id": "etJIqhCK7Sw", "reviewer": "Reviewer_HWqt", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The authors show for the models under consideration an interesting and novel result: the models are implicitly biased not by the real space norm of the linear predictor, but by the Schatten norm of the Fourier transform of the predictor. For the Abelian case, this required an incremental generalization of prior work, but for the non-Abelian case required an interesting proof method. The paper is very clearly written and was a pleasure to read.\n\nMy main problem with this work is that it considers a model class that I’ve never seen used (besides the lack of non-linearities): it uses group equivariant CNNs and then takes an inner product with a G-feature weight, resulting in a non-equivariant linear predictor. If the authors used invariant outputs, the linear invariant predictors would just be averaging, and the analysis wouldn’t work. As G-CNNs are chosen for their symmetry properties, studying them in a non-equivariant context makes little sense to me. Whether the implicit bias found in this paper generalizes to equivariant non-linear G-CNN networks has not been convincingly shown.\n\nFor me to recommend acceptance of this paper, the authors should make a more convincing point why the results for this non-equivariant model class are applicable to equivariant G-CNN networks people actually use (besides the fact that the analysis applies to linear networks).\n\nOther weaknesses:\n* The non-Abelian case states two assumptions (gradients converge in direction, iterates converge in direction to a classifier with positive margin), but these are not clearly defined, nor is it stated when these are satisfied. The paper would be improved if there would be some discussion of these assumptions.\n* The key point of the paper seems to be that Fourier Schatten norm, not spatial norm is the implicit bias of the learned networks. The paper would be stronger if it would give some more intuition about this point. Perhaps visualize some of the learned weights in both Fourier and spatial domain?", "summary_of_the_paper": "Group Equivariant CNNs (G-CNNs) generalize CNNs from the translation group to arbitrary groups. It has been shown that overparameterized/undetermined linear transformations and linear CNNs learned by gradient descent are implicitly biased, in that they find zero train loss solutions that minimize some norm on the predictor. This paper generalizes these results from linear CNNs to linear G-CNNs. The linear G-CNNs are constructed into a non-equivariant linear transformation, by doing L G-CNN layers, followed by a non-equivariant inner product with a G-feature. The authors show that the implicit bias is to minimize the p-norm of the singular values (the Schatten norm) of the Fourier transform of the resulting linear transformation.\nIn the case where G is Abelian, by a tensor factorization of the linear G-CNN, the authors can straightforwardly apply a result from prior work on the implicit bias of such tensor factorizations to prove their result.\nIn the case where G is not Abelian, the authors prove their results in three steps. (1) They use prior work on gradient descent on linear predictors that are polynomials of the parameters, which their linear G-CNN falls under, to show that the stationary points minimize norm the joint norm on all weights. (2) They define a linear regression optimization that minimizes the Schatten norm of the linear predictor. (3) They show that all optima of the polynomial linear predictor are also optima of the Schatten-normed linear regression. To do so, they find the subdifferential of the p-Schatten norm and show that the polynomial optimum is in the subdifferential.\n\nThe authors confirm their theory in toy experiments in the linear case and show that in the non-linear case, where the Schatten norm is computed by local linearization, that similar results may hold in the non-linear case.", "summary_of_the_review": "While the authors use novel methods to derive an interesting implicit bias of the model class under consideration, this class, non-equivariant predictor based on equivariant neural network layers, is not what is generally used in practice. For the paper to be recommendable for acceptance, the authors should make a stronger argument why their results also apply to models actually used. If they do so convincingly, I'd increase my score.\n\n\n\nUpdated score to 6.", "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": {}}, {"review_id": "Xevn5xmUQ7f", "reviewer": "Reviewer_k7aV", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "From a technical perspective, the results for abelian groups (as the authors note) follow from appropriately applying the result of Yun et al. (2020). (This is because convolutions in Fourier space can be expressed as pointwise multiplication for abelian groups.) The more interesting technical contribution is for non-abelian groups. In this case, convolutions corresponds to matrix multiplications of matrices which need-not be diagonal, and thus do not correspond to point wise multiplication. For this case, the authors directly analyze the stationary points of the optimization problem. \n\nAn appealing aspect of the paper is to highlight that the norm that is implicitly controlled by gradient descent on group equivariant networks takes a simple form, even for general (finite) groups. This technical point is made clearly in the paper, and the paper is generally well-written.  \n\nOne weakness of the paper is that the it does not explicitly connect the theoretical results with practical settings. First, since group-equivariant convolutional neural networks are not a standard architecture, it could be helpful if the authors added a discussion of what group structures have been used / are meaningful in practice, and provided insight (e.g. in the empirical section) into the implicit regularization of gradient descent in these special cases. \n\nFurthermore, the empirical results are quite limited. Based on Appendix D, the networks appear to be run on very small synthetic datasets (with 6-10 datapoints). For this reason, it is difficult to determine if the takeaways hold for more realistic classification tasks. It would be helpful if the authors ran experiments on standard binary classification datasets (e.g. MNIST or CIFAR). \n\nLastly, another weakness of this paper is that the results are restricted to single-channel linear networks with full-dimensional kernels. In light of previous work (i.e. Yun et al. (2020, Gunasekar et al. (2018)), the results are somewhat incremental. The paper mainly demonstrates that the 2/L-norm in Gunasekar et al. (2018) for L-layer linear CNNs can be replaced by the (2/L)-Schatten norm. While this norm (especially for non-abelian groups) does give rise to different sparsity structures, the analysis and the conceptual takeaways are somewhat similar those in Gunasekar et al. (2018). \n", "summary_of_the_paper": "This paper studies the induced bias of gradient descent on L-layer linear group-equivariant convolutional neural networks. Their main result is: gradient descent implicitly controls the 2/L-Schatten norm of the Fourier transform of the (linear) predictor. More precisely, they show that gradient descent trained on a L-layer group-equivariant CNN with exponential loss on a linearly separable dataset converges in direction to a first-order stationary point of an optimization problem minimizing the 2/L Schatten norm of the Fourier transform of the linear predictor subject to the margin being at least 1. \n", "summary_of_the_review": "I recommend weak rejection due to the incremental nature of the technical results in light of previous work, as well as the limitations of the empirical section. \n\n---- \nUpdate after author response: I appreciate the additional experiments on the MNIST dataset, and believe that this improves the empirical analysis provided in this paper. However, given the results in previous work (e.g. Gunasekar et al. '18, etc) for the trivial group, I still think that the results in this work are fairly restrictive since they only hold for single-channel linear networks with full-dimensional filters. Although previous work has shown that simple closed-form solutions may not exist in general, it would still be useful to provide insight into how these important parameters affect the implicit bias of gradient descent. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "7gKDTygP2n-", "reviewer": "Reviewer_nEDA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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:\nAs far as I can assess, the paper is technically sound, novel and timely.\nThe paper is formal and precise.\nThe appendix is quite nice actually and is rather complete in mathematical background.\nThe paper is reproducible and has code provided.\n\nWeaknesses:\nMy main criticism is that the paper is very theoretical and feels a bit like a nice math exercise to prove something, however, without being clear why the problem is addressed in the first place (apart from the fact that no one did it yet). To me, as someone working with G-CNNs and having a good understanding of (irreducible) representation theory, but not in analysis, it is unclear what I should take home from the paper. \nI.e., why should we expect different results for non-Abelian compared to Abelian groups in the first place? \nHow should I interpret the bias towards dense solutions as a regularization effect? \nWhat are the implications?\n\nComments:\nIt would be helpful to have explicit statements about the main contributions/novelty of the paper.\n\nThe experiments in the figure make sense to me in the comparison G-CNN vs FC. Both map G-feature maps to scalars and the latter shows that the bias takes place due to architecture and not the data. However, I do not understand the comparison CNN to G-CNN. If the feature maps are functions on G, is a CNN not automatically a G-CNN? Then, what is the difference between the two? \n\nSome essential details are missing regarding the data. I cannot find it in the appendix either. The closest I get to a description is in caption of Figure 3: “trained … with six isotropic Gaussian data points”. What is an isotropic Gaussian data point? \n\nIn theorem 5.3 third line: is this a typo? (w.r.t. indexing to l should be l+1?, it says something like Fw_l-Fw_l \\geq \\lambda)\n", "summary_of_the_paper": "The paper describes a theoretical analysis of the implicit bias in G-CNNs. The results show that for linear G-CNNs trained on linearly separable data using GD converge to sparse solutions in the Fourier domain (equivalently dense solutions in the real domain). The theory is theoretically confirmed and shows that the implicit bias also occurs to some extend for non-linear G-CNNs.", "summary_of_the_review": "Although I am comfortable with group theory and basic harmonic analysis on groups through irreps, I find it hard to follow the derivations and make sense out of the statements. My impression is that the paper is too mathematical for ICLR audience, though I can really only speak for myself. The paper could improve a lot from more layman's explanations throughout the paper. For example, it already starts early in the paper with talk about Schatten norms, where to me it is not immediately obvious why these are considered.\n\nI understand that it is hard to please every reader, but I believe it is possible to convey the main messages better to a broader audience. Currently it seems overly tuned towards experts in analysis (of implicit biases).\n\nOverall, I do see value in publishing such work as the paper seems otherwise sound.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines the implicit bias of gradient descent of linear group equivalent convolutional neural networks with a single channel and full-dimensional kernel when trained on separable data with exponential loss. The main result is that the linear predictor converges in direction to the first order stationary point of the minimum 2/L Schatten matrix norm max-margin problem, under some assumptions. This generalizes previous results on linear convolutional neural networks.

I appreciated this paper states the theorems in terms of general group operations; if done correctly and written well, this can be a good reference for future papers. But I think this paper needs a little more work before getting there, as I explain below.

The reviewers were borderline (6,6,6,5) and did not have high confidence. Some stated clarity issues, other criticized the model being used: either that (1) only the case of single channel and full-dimensional kernel we examined, or that (2) the full model is not actually invariant. Given previous results (Jagadeesan et al.) I am OK with (1). I find (2) problematic, but not enough to be a reason to reject the paper. 

So I took a closer look.

First, I felt that indeed the paper writing could be improved. Specifically, the notation could be better explained (e.g., the h and g functions in eq. 3 are not defined: what are their range and domain?), and more discussions and examples can be added throughout the paper to clarify the significance of the results.

Second, the experimental results in the non-Abelian case (figure 4a) and non-linear case (figure 5) seemed somewhat weak (not so sparse) after I noticed the y-axis does not start from zero, as in Figure 3a.

Most importantly, looking at the proofs, I felt they were rather incremental, as I explain next. The authors claim their main result, Theorem 5.4, does not follow from Yun et al.'s paper. But Gunsekar et al. 2018b already had KKT condition results for max margin in parameter space, and even stronger results are in [1] (which the authors should cite and discuss clearly). These already give a stronger version of Theorem A.6. So the main extra contribution here is to extend it to a guarantee on function space (in the space of linear functions beta). 

But for L>2, I unless I am missing something, I feel this is straightforward, by using results like in [2], where they relate subdifferentials of unitarily invariant matrix functions to the corresponding vector subdifferentials on the singular values (and in the vector case, the subdifferential is trivial). 

The L=2 is not trivial as we need to show the condition in Assumption A.7, which is the most technical part of Gunsekar et al. / Yun et al. papers, and is often non-trivial. The authors in this paper, however, did not show this and rather leave to future work in the last paragraph of Appendix A.  I think that this is a concrete opportunity to make the paper better, perhaps following the same methodology in Gunsekar et al. / Yun et al. papers.

Minor comments: 
1) The informal Theorem 1 should state we converge to the f.s.p. of eq. 1, not a solution of eq. 1.  
2) The main paper is non-searchable, which makes it harder to read.
3) Many hype refs in the appendix do not work well (they get me to some random page).

[1] K. Lyu, and J. Li. "Gradient descent maximizes the margin of homogeneous neural networks." 2019.
[2] A. S. Lewis  The Convex Analysis of Unitarily Invariant Matrix Functions, 1995
Decision: Reject