On the Implicit Bias of Linear Equivariant Steerable Networks
Authors: Ziyu Chen
Wei Zhu
Venue: NeurIPS 2023 poster (2023)
Keywords: implicit bias
equivariant steerable networks
data augmentation
margin
generalization bound
TL;DR: We analyze the implicit bias of gradient flow on linear equivariant steerable networks and demonstrate their implications in margin and generalization.

Abstract: We study the implicit bias of gradient flow on linear equivariant steerable networks in group-invariant binary classification. Our findings reveal that the parameterized predictor converges in direction to the unique group-invariant classifier with a maximum margin defined by the input group action. Under a unitary assumption on the input representation, we establish the equivalence between steerable networks and data augmentation. Furthermore, we demonstrate the improved margin and generalization bound of steerable networks over their non-invariant counterparts.

On the Implicit Bias of Linear Equivariant Steerable Networks
Ziyu Chen
Wei Zhu
Department of Mathematics and Statistics University of Massachusetts Amherst Amherst, MA 01003 z z'yuchen@umass.er
Department of Mathematics and Statistics University of Massachusetts Amherst Amherst, MA 01003 weizhudumass edu
Abstract
We study the implicit bias of gradient flow on linear equivariant steerable networks in group-invariant binary classification. Our findings reveal that the parameterized predictor converges in direction to the unique cooup-invariant classifier with maximum margin defined by the input group action. Under a unitary assumption on the imput representation,
establish the equivalence between steerable networks and data augmentation. Furthermore, we demonstrate the improved margin and generalization bound of steerable networks over their con-invariant counterparts.
Introduction
Despite recent theoretical breakthroughs in deep learning, it is still largely unknown why overparam eterized deep neural networks (DNNs) with infinitely many solutions achieving near-zero training enror can effectively generalize on new data. However, the consistently impressive results of DNNs trained with first-order optimization methods, e.g., gradient descent (GD), suggest that the training algorithm is implicitly guiding the model towards a solution with strong generalization performance.
Indeed, recent studies have shown that gradient-based training methods effectively regularize the solution by implicitly minimizing a certain complexity measure of the model [Vardi 2022). For example, Gunasekar et al. (018b) showed that in separable binary classification, the linear predictor parameterized by a linear fully- cullecco network trained under GD converges in the direction of max max-mn support vector machine (SVM), while linear convolutional networks are implicitly regularized by depth-related bridge penalty in the Fourier domain. Yunn et al. (2021) extended this
finding to linear tensor networks. Lyu and Li (2200) and and Telgarsky (2020) established the implicit max-margin regularization for (nonlinear) homogeneous DNNs in the parameter space.
On the other hand, another line of research aims explicitly regularize DNNs through architectural design to exploit the inherent structure of the learning problem. In recent years, there has been growing interest in leveraging group symmetry for this purpose, given its prevalence in both scientific and engineering domains. A significant body of literature has been devoted to designing group- houp-equuvariiat DNNs that ensure outputs transform covariantly to input symmetry transformations. Proup-equivariann steerable networks represent a general class of symmetry--reseervngg preserving models that achieve equivariance with respect any pair of input-output group actions [Cohen et al. 2019 |Willer and Cesal 2019 Cohen and Welling 2017]. Empirical evidence suggests that equivariant steerable networks yield substantial improvements generalization performance for learning tasks with group symmetry, especially when working with limited amounts of data.
There have been several recent attempts account for the empirical success of equivariant steerable networks through establishing a tighter upper bound on the test risk for these models. This is typically accomplished by evaluating the complexity measures of equivariant and non-equivariant models under the same norm constraint on the network parameters [Sokolic et al. 2017
Sannai
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

et al., 2021 Elesedy 2022]. Nevertheless, it remains unclear whether or why a GD-trained steerable network can achieve a minimizer with a parameter norm comparable that of its non-equivariant counterpart. Consequently, the effectiveness of such meallexitt--mmuuee-beee arguments to explain the generalization enhancement of steerable networks in group symmetric learning tasks may not be directly applicable.
In light of the above issues, in this work, we aim fully characterize the implicit bias of the training algorithm on linear equivariant steerable networks in group-invariant binary classification. Our result shows that when trained under gradient flow (GF), i.e., GD with an infinitesimal step size, the geerrbblenetworts net--ne-ttwaaaaaneeeee parameterized predictor converges in direction to the unique group- invariant classifier attaining a maximum margin with respect to norm defined by the input group representation. This result has three important implications: under a unitary input group action,
a linear steerable network trained on the original data set converge in the same direction as a linear fully-connected network trained on the group-augmented data set. This suggests the equivalence between training with linear steerable networks and data augmentation;
when trained on the same original data set, a linear steerable network always attains a wider margin on the group group-augmenedd data set compared fully-connected network:
when the underlying distribution is group-invariant, GF-trained linear steerable network achieves a tighter generalization bound compared to its non-equivariant counterpart. This improvement in generalization is not necessarily dependent on the group size, but rather it depends on the support of the invariant distribution.
Before we end this section, we note that a similar topic has recently been explored by Lawrence et al. (202T) in the context of linear Group Convolutional Neural Networks (G-CNNs), a special case of the equivariant steerable networks considered in this work. However, we point out that the models they studied were not truly group-invariant, and thus their implicit bias result does not explain the improved generalization of G-CNNs. We will further elaborate on the comparison between our work and [Lawrence al. 202T in Section
2
Related work
Implicit biases:
Recent studies have shown that for linear regression with the logistic or exponential loss on linearly separable data, the linear predictor under GD/SGD converges in direction to the
max-L22-marii SVM (Soudry et al., 2018 Nacson et al. 2019. Gunasekar et al. 2018a]. These results are extended linear fully-connected networks and linear Convolutional Neural Networks (CNNs) by Gunasekar et al. (2018b) under the assumption of directional convergence and alignment of the network parameters, which are later proved by Ji and Telgarsky [2019a b). Lyu and Li 20220). Ji and Telgarsky/ [2020]. The implicit regularization of gradient flow (GF) is further generalized to linear tensor networks by Yun et al. [2021). For overparameterized nonlinear networks in the infinite-width regime, rigorous analysis on the optimization of DNNs has also been studied from the neural tangent kernel [Jacot et al. 2018 Du et al., 2019 Allen-Zhu et al. 2019 and the mean-field perspectives [Mei et al. 2019 Chizat and Bach, 2018]. However, these models are not explicitly designed to be group-invanee wwap-paaaaaaa/euuvvvaaaaa
and the implicit bias of gradient- baseed methods might guide them to converge to sub-optimal solutions in learning tasks with intrinsic group symmetry.
Equivariant neural networks. Since their introduction by Cohen and Welling 2016), group equivariant network design has become burgeoning field with numerous applications from computer vision scientific computing. Unlike the implicit bias induced by training algorithms, equivariant networks explicitly incorporate symmetry priors into model design through either group convolutions [Cheng et al. 2019 Weiler et al. 2018 Sosnovik et al. 2020 Zhu et al. 2022 or, more generally, steerable convolutions Weiler and Cesa 2019][oher et al. 2019 Worrall et al. 2017). Despite their empirical success, remains largely unknown why and whether equivariant networks trained under gradient-based methods actually converge to solutions with smaller test risk in group-sye sroup-yymmetrie learning tasks (Sokolic et al., 2017 Sannai et al., 202T). a recent study, Elesedy and Zaidi 2021] demonstrated a provably strict generalisation benefit for equivariant networks in linear regression. However, the network studied therein is eeuiiaaiiin and only symmetrized after training; such test-time data augmentation is different from practical usage of equivariant networks.

---

Comparison to Lawrence et al. [2021]. A recent study by Lawrence et al. [2021] also analyzes the implicit bias of linear equivariant G-CNNs, which are special case of the steerable networks considered in this work. However, the networks studied therein are not truly equivariant/ivvarintt More specifically, the input space 2g they considered the set functions on the group G, i.e., X, { G JR and the input G-action is given by the regular representation
(po())f((o)) = f g') Vg E G.Vf E No.
(1)
In their case, due to the transitivity of the regular representation : No R are constrained to the (trivial) form:
T.. G-invariant linear functions
( = C..))
SEG
where C' is multiplicative constant. To avoid learning this trivial function, Lawrence et al. [2021] chose to parameterize & using a linear G-CNN, which the final layer is replaced by a fully- connected layer. While this folny-con layer provides the capability to learn more complex and nontrivial functions, it simultaneously undermines the property of group invariance. Therefore, their implicit bias result does not explain the improved generalization of G-CNNs. In contrast, assume Euclidean inputs with non-transitive group actions, allowing linear steerable networks to learn non-trivial group-invariant models.
3 Background and problem setup
We provide a brief background in group theory and croup-equivariant steerable networks. We also explain the setup of our learning problem for group-invariant binary classification.
3.1 Group and group equivariance
group is set G equipped with a binary operator, the group product, satisfying the axioms of associativity, identity, and invertibility. We always assume in this work that G is finite, ie., |G] < oc, where [ denotes its cardinality.
Given vector space X, let GL(X) the general linear group of consisting all invertible linear transformations on X. A map p G + GL(X) is called a group representation (or linear group action) of G on X if p is a group homomorphism from G to GL))), namely
plgh) = (h) E GL(X), Vg
(2)
When the representation p is clear from the context, we also abbreviate the group action p(g)x gx. Given a pair of vector spaces X, and their respective G-representations px and py, a linear map V : X + y is said to be G-equivariani if commutes with the G-representations and py, iee.
V o px( py(g) V Ag E G.
Linear equivariant maps also called intertwiners, and we denote by Home(px, Py) the space of all intertwiners satisfying (3). When Py = Id is the trivial representation, then V (px = [/x] for all x E X: namely, v becomes G-invariant linear map.
3.2 Equivariant steerable networks and G-CNNs
Let X, do be do-dimensional input Fuclidean space, equipped with the usual inner product.
Let Po : G + GL(X)) be a G-representation on Xo. Suppose we have an unknown target function
f Xn R + R that is G-invariant under Po. iee. fgxx) = (po(g)) = (x) for all g E G
and x Xg. The goal of equivariant steerable networks is to approximate f using an L-layer neural
network f = r. a W i.-1 o ... V that is guaranteed to be also G-invariant.
Since the composition of equivariant maps is also equivariant, it suffices to specify collection of G-representation spaces [(X,, ()) with (Xt,, Pt.) = (R, Id) being the trivial representation, such that each layer V (pmm((1-1.PL)) X-1 XG is G-equivariant. Equivalently, we want the
3

---

following diagram to be commutative,
22
Vs
Vn-1
Xo
X1
X2
Nt-1
po(9) (9)
pz(0)
PD-1(0)
pe(o)
Ag E G.
(4)
Xg X
W1
22
V2-3 Xt-1 Ve X1.
Equivariant steerable networks. Given the representations {(M,, pi) a (linear) steerable network is constructed as follows. For each I E [4] = (I,... ... [.), we choose a finite collection (pLm pt). Typically, {17 ( is basis of Homa(pt-1 Pt), but it is not necessary in our setting. The 1-th layer equivariant map Tatte 2 Xj of a steerable network is then parameterized by
of Ni (pre-computed) intertwiners (11))
V (x: wi)
Σ wf JE[N]]
Ex X-11
(5)
where the coefficients wi [NN))E(NN) TR-N are the trainable parameters of the 1-th layer. An L-layer linear steerable network fsteer (x; W) is then defined as the composition
Ssteer (x (x; W) Veterr (... Virieer ()<eer(;; w1); w2) :wr,,
(6)
where W [wi]f= = RM Wateer is the collection of all trainable parameters. The network
sstee x; W) defined in (6) is referred to as a steeruble network because it steers the layer-wise output to transform according to any specified representation.
G-CNNs. A special case of the steerable networks is the group convolutional neural network (G-CNN), wherein the hidden representation space (Xi, for each E [L- 1]
set
X = (R (xi G R"), ((())x((h) xi(9
Vg,
The representation E (L)()) in ( is known as the regular representation of G. Intuitively, X₁ Xg be viewed matrix of size di [G], and pr(g) is permutation of the columns of x1-
With this choice Pi)) the first-layer equivariant map of a G-CNN is defined as
G (x; (x: = wi. g x E Rd, Vx E R
(8)
where wi = (wI )3. E Rdaxd: are the trainable parameters of the first layer. Eq. (8) is called G-lifting map as it lifts a Euclidean signal x Rd to function GGGCNN (x; wi) on G. For the subsequent layers, equivariance is achieved through group convolutions, and the readers are referred to the appendix for detailed explanation.
Assumptions the representations. The input representation Po GL = Rd)) is assumed to be given, and PL = 1 e GL(Xg, = R) is set to the trivial representation for group- invariant outputs. In this work, we make the following special choices for the first-layer representation (p1, as well as the equivariant map Visteer w1) in a general steerable network.
Assumption 3.1. We adopt the regular representation for the first layer, and set the first-layer equivariant map Tpstee (x; w1) the G-lifting map (8)
Remark 3.2. The rationale of Assumption 3.1 is for the network to have enough capacity to parameterize any G-invariant linear classifier; this will be further explained in Proposition (3.6 We note that the representations Xi) and steerable maps Wasteer (x. wi) for all subsequent layers, I (2. L 1}, can be arbitrary.
Under Assumption 3.1 we can characterize the linear steerable networks ssteer:; (:; W) in the following proposition.
Proposition 3.3. Let (x;er(x; W) be the linear steerable network satisfying Assumption 3.1. where W wi)f E Water the collection of all model parameters. There exists lulti-linear map M (W2, ... WL) > M(W2, w..) E RRds such that for all x E RRdo and W E Water
face (x; W) faeer (x; W) 1X (W2. (WL)) wi
(9)
where x =
[C Eges gx is the average of all elements on the group orbit of x E TRd
1

---

Although straightforward proof of Proposition 3.3 can be readily derived using Schur's Lemma,
we have opted to include an elementary proof of Proposition 3.3 in the appendix for the sake of completeness. If we define
P steer (W) = W WW wr.,, Psteer Psteer(W= =
Σ 9
Pstcer( W);
(10)
G
9EG
where g² = po(g)) then
Ssteer (x; W) = (x, Psteer (W)) (x, P steer (W))
(11)
By the multi-linearity of (W2:-.., Wr.), one can verify that fateer (x; W), Pster (W), and P steer (W) all T-homogeneous in W; that is, for all O and W Wsteen
fseet (x:1 WW) = v² (x: W), Patee (vW) D steer (W), P Psteer (VW) W)
vLP steer (W). (12)
Remark 3.4. In comparison, an L-layer linear fully- network fte(x: W) is given by w.
Pic Pi((W) = W1 WL. where W iwilli E Wic = [I R R4 1xx)
fie(x: W) = wI WI .. =
(13)
x RR It is worth noting that when G fillayfully-ae fully-connected network frc W) is identical with a linear G-CNN, which is special case of linear steerable networks. See Remark A. 7 for details.
{e)
the trivial group, linear
3.3
Group-invariant binary classification
Consider a binary classification data {#1], Vi E [n). We assume that S are i..dd samples from a G-invariant distribution D defined below.
{xx, vi) i [n]]], where x, idd and yi
Definition 3.5. A distribution D over ıddo x { is said to be G-invariant with respect to representation po E GGL(Rd) if
(po(g) Id), D DDD, D, Vg GG
(14)
where (polg) & Id)(x, y) = (po(g)x.9) y). and (pu(g) @ Id), D = (po(g) @ Id) is the push- forward measure of D under po(g) & ld.
It is easy to verify that the Bayes optimal classifier / Ro {+1} (the one achieving the smallest population risk) for a G-invariant distribution D necessarily a G-invariant function, iee. ("(xx) f (x), Vg E G. Therefore, to learn f using (linear) neural networks, it is natural to approximate f" using an equivariant steerable network
(x) x sign (Jseer (x; W)) sign ((x, Pstcer W))).
(15)
After choosing the exponential loss lexp R (+1] R4, (e y) exp(-ůy) surrogate loss function, the empirical risk minimization over S for the steerable network S x; W) becomes
min WeW
S)
lexp((X,, Pater (W)) 91)
lexp ( P
ster (W)) v.). (16)
On the other hand, since Pateer (W) 3 E Rdd always corresponds to G-invariant linear predictor-
have slightly abused the notation by identifying 3 E Ro with the map - (x. 3) -3)-one can alternatively consider the empirical risk minimization directly over the invariant linear predictors 3:
min L(3:S) == Σ Loxp ()))))) BER
(17)
where 18:2 Ro is the subspace of all G-invariant linear predictors, which is characterized by the following proposition.
Proposition 3.6. Let R2d C do be the subspace of G-invariant linear predictors, i.e., Bdg {B do :3 xxx= BT gx, Vx E RRd,, Vg E G}. Then
5

---

(a) R& is characterized by
R
ker (I -g²)
Range
1
Σg
9
(18)
G
9EG
SEG
(b) Let A: Rd do be the group-averaging map.
A(B) = GG| Σ
9B.
(19)
BEG
Then its adjoint AT ++ 1
[ Egec 9 B is projection operator from IR B In
other words, Range(A)) R.O and A o A A
(c) G acts unitarily on Ng, i.e., pu(g = pu(g) then A = A is self-adjoins. This implies that A B + B is an orthogonal projection from TRd onto Re In particular, we have
==
B E R2. and || S |131, VB Ro
(20)
Proposition 3.6 combined with 10)) demonstrates that linear steerable network ssteer W) (, Patorr W)) realize any G-invariant linear predictor B Rd; that is, {Pstorr (W) W
Waser] Ry Therefore (T)) and (17) are equivalent optimization problems parameterized in
different ways. However, minimizing (16) using gradient-based methods may potentially lead to
different classifiers compared those obtained from optimizing (17) directly.
Gradient flow. Given an initialization (0)) E Waterr the gradient flow (W(t))20 for 16 the solution of the following ordinary differential equation (ODE),
dW dt V (W; S) - V
(oxp((Xi, P steer (W)), ,w:)
(21)
The purpose of this work is inspect the asymptotic behavior of the G-invariant linear predictors Bssser (t(()) parameterized by the linear stecrable network trained under gradient flow
(T.). In particular, we aim to analyze the directional limit of ( t >> co, i.e., lim4 [ (t]l
Sus (f)
Before ending this section, we make the following assumption on the gradient flow W(t) that also
appears in the prior works Ji and Telgarsky 2020 Lyu and Li [2020] Yun et al. [2021].
Assumption 3.7. The gradient flow W(t) satisfies Panm (W S) for some to > 0.
This assumption implies that the data set = {(x,, Mi) : E [n]} can be separated by a G-invariant linear predictor Pseee (t((t)) and our analysis is focused on the "late phase" of the gradient flow training as co.
Implicit bias of linear steerable networks
Our main result on the implicit bias of gradient flow on linear steerable networks in binary classifica- tion is summarized in the following theorem.
Theorem 4.1. Under Assumption 3.7 and Assumption 3.7 let Brtee (t) = Pswer (t)) be the time- evolution of the G-invariant linear predictors parameterized a linear steerable network trained with gradient flow on the data set S = {(x,, 3/ : [n]];; of. Eq. 21). Then
(a) The directional limit (a lim
(f)) exists and B 1 Eges 9 Y", where r is the max-T, T.?-margin SVM solution for the transformed data 5 |a| {xx, vi) : [m]]:
(t)((t)
7" arg min 7E340
||x|1
S.t. De (x,, 2 1, [n].
(22)
Furthermore, if G acts unitarily the input space Xo. i.e., g 1 T,, then 800 7

---

(b) Equivalently, S is proportional to the unique minimizer 3 of the problem
3 = arg min BERd
(1) s.t. S.t. E E Re and yi (x,, 93 2 1, [p],
(23)
where ProlRange(A) the projection from Rdo Range(A) Range over, if G acts unitarily on No. then
[
Egeas 9)
More-
Sriees x 3 arg min
|131 S.t. B EC and yi (x,, 2 1i [n].
(24)
BER
Namely, Breer achieves the maximum -a-man among all G-invariant linear predictors.
Theorem 4.1 suggests that gradient flow implicitly guides a linear steerable network toward the unique G-invariant classifier with maximum margin defined by the input representation po-
Remark 4.2. According Remark 3.4 when G {e} is trivial group, then linear G-CNN (which is a special case of linear steerable networks) reduces to a fully-connected network fic(x; W). Since the representation of trivial group is always unitary. have the following corollary which also appeared in Ji and Telgarsky (2020) and Yun et al. (2027).
Corollary 4.3, Let (t)) C Wie be the gradiens flow of the parameters when training a linear fully-connected network on the data set S {(x, y:), E [m]], i.e.,
dW dt
Cp. (W;S) = Vw
Σ
Leep Pic(W)) vi)
(25)
Then the classifier Bio(t) (t)( converges in a direction that aligns with the max-L -margin SVM solution " for the original data set = {(x,, y&) : [n]].
= arg min |h 7ER40
s.t. ya (x,, 7) 1.
(26)
Remark 4.4. While Theorem 4. provides complete characterization of the implicit bias exhibited by gradient flow in linear steerable networks, it is imperative to note that the convergence rate to the directional limit is, in fact, exponentially slow. This is consistent with the findings in, e.g., (Soudry et al. 2018 Yun et al.) 2027y. A comprehensive analysis of gradient flow behavior in a non-asymptotic regime falls outside the scope of this current study.
The equivalence between steerable networks and data augmentation
Compared hard-wiring symmetry priors into model architectures through equivariant steerable networks, an alternative approach to incorporate symmetry into the learning process is by training non-equivariant model with the aid of data augmentation. In this section, we demonstrate that these two approaches are equivalent for binary classification under unitary assumption for po-
Corollary 5.1. Let Baeer = lim [|Bres be the directional limit of the linear predictor (ssc(t)) = Passee(W (t)) parameterized by linear steerable network trained using gradient flow on the original data set S ( E in]]. Correspondingly, let 5% lim, (!]lI)))I
Bus=(t)
3t)
Bie(t) = Pto ((t)) 13), be that of a linear fully-connected network trained on the augmented data set S.ng (gxx, Uo). [n].g E G). If G acts unitarily on Xy, then
Bleer
B
(27)
In other words, the effect of using linear steerable network for is exactly the same as conducting data-augmentation for non-invarianl models.
binary elassification
Remark 5.2. The equivalence between data augmentation and training with linear steerable network valid only in an asymptotic sense, yet the underlying training dynamics differ substantially: Specifically, (lve(()) () is assured to maintain G-invariance throughout the training process, whereas (Ie(t) achieves G-invariance solely the limiting case as - oc. Moreover, the equivalence only holds for "full-batch" data cata-auumentttion over the entire group orbits.
7

---

Remark 5.3. For Corollary 5.1 to hold, it is crucial that E GL(()) is unitary, as otherwise the limit direction Pi of a linear calle-co network trained on the augmented data set generally not G-invariant (and hence cannot be equal to Patcer E &R&) ); see Example 5.4
Example 5.4. Let G = 2g {0, 1}. Consider inon-unitary) G-representation Po on X IR?,
1 0
1
1
0
[ 0
--
Po
No (1)
2
(28)
Let S = ((x, y)} = (((1,2)T +1)} be a training set with only one point. By Theorem 4.1 the limit linear predictor satisfies
direction Beter of memeaursterrable--tttorr--pppppe
-
B X
Σ9 gg BEG
0 > :
1
1 1
111
(29)
where Y = (0, T) is the max-margin SVM solution for the transformed data set S (x,,
{((0,3) 3) +1]]]. On the contrary, by Corollary 4.3 the limit direction 3 of a linear cunny-connected
network trained on the augmented data set Sang [((1,2) +1), ((-1, 4)T, +1)} aligns with the max-margin SVM solution Youg for Saug.
B X Yaug = arg min ||
s.t. y (x, 7) 2 1, V(x y) E Sang
(30)
7EX2
0.4) T * B
(31)
However, we demonstrate below that the equivalence between linear steerable networks and data augmentation can be re-established for non-unitary Pu by defining a new inner product on R
1/2
(v, w) =v
w, Vv,w X - RRo
(32)
G
gEG
When po is unitary, (v, w) = (v, w) is the normal Euclidean inner product. With this new inner product, we modify the linear fully-connected network and its empirical loss on the augmented data set Smgg {ggxx 3:) g E G,i E [n]]} as
f (x; W) = Pic)))
(33)
Pr. (W; Smgg)
Σ ΣΣ4
Lexp (J (gx;: W),
Lexp (loX., Pre(PP))) v.). (34)
gEG
gEG 1=1
The following corollary shows that, for non-unitary on Xo. the implicit bias of a linear steerable network is again the same that of a modified linear fully fully-connected network f (x: W) trained under data augmentation.
Corollary 5.5. Let Bree be the same as that in Corollary 5.1 Let B 300.00 = lim; [ (+)
be
the limit direction of 3 (t) = Ptc (t)()(t)) under the gradient flow of the modified empirical loss
Leo (W; Smgg) (34) for linear fully-connectedd network on the augmented data set Smug. Then
1/2
< (o(9)) po(s)
B50.00
(35)
G
9EG
Consequently, we have (x. ( x (x, 3 300000)
po for all x Rd
Improved margin and generalization
We demonstrate in this section the improved margin and generalization of linear steerable networks over their non-invariant counterparts. In what follows, we assume Po to be unitary.
The following theorem shows that the margin of a mhear-steerable-neee netwolk- parpoor-parrmmetrrizedd predictor 8 the augmented data set Saug is always larger than that of linear fully- connected network
a suggesting improved robbuustsssss of the harpolle-nettoo---aaaeteeeee classifier.

---

Theorem 6.1. Let Bxtee be the directional limit of a sterrbleeeook-ppreeeeeeee predictor trained on the original data set = {(x,, 3i), [n]]; let (i be that of a linear fully- culty-coneected network also trained on the same data set S. Let Mater and MR. respectively, be the (signed) margin of free and fig on the augmented data set Sung = [(gx; y6) E [m].g 9 E G), i.e,
Mateer
min Yi (Bsccc 9xi). Mie min ye (8% 9x.). TE(")
(36)
iE(n].9EG
Then always have Materr 2 Mic.
Finally, we aim to quantify the improved generalization of linear steerable networks compared to fully-connected networks in binary classification of linearly separable group-invariant distributions defined below.
Definition 6.2. A distribution D on RR x {+1} is called linearly separable if there exists B I.d such that
P (x.))= (V (x, 3) 2 1] =1
(37)
easy to verify (by Lemma F.1 that D is G-invariant and linearly separable, then can be separated by a G-invariant linear classifier. The following theorem establishes the generalization bound of linear steerable networks in separable group- group-invariant invariant binary classification.
{+1} that is linearly separable by an Theorem 6.3. Let D be G-invariant distribution over Rd
invariant classifier Bo E Wdo. Define
R= inf (r (2:0: O: | S r with probability 1}.
(38)
Let = ((x;, be i..dd samples from DD and let B be the limit direction of a steerable- network-paree paramet-pr linear predictor trained using gradient flow on S. Then, for any we have with probability at least 1 8 (over random samples S ~ D that
2R 1og(110)
P ((xy)> ly * sign ((x, 3Reen)
(39)
VT.
2n.
Remark 6.4. In comparison, let B% be the limit direction of a fully-comeeted-netwerrr parameterized linear predictor trained on S. Then with probability at least - ô, we have
2RI]Boll Vn.
(og(1/8)
P(x.))DD (y # sign ((x, BE S
+
(40)
2n.
where R inf fr > 0: |x r with probability 1}. This is the classical generalization result for max-margin SVM (see, e.g., a special case of Eq. (39), as a fully-connected network is G-CNN with G {e} 3 (ef. Remark 4.2) and therefore x = x and R=
and Ben- Ren-DDvidd) (2014).) Eq. (40) can also be viewed as
By Proposition 3.6 the map X is orthogonal projection, and thus we always have R S R. Therefore the generalization bound for steerable networks in 339 is always smaller than that of the fully-conmected network in (40).
Remark 6.5. A comparison between Eq. 39 and Eq. (40) reveals that the improved generalization of linear steerable network does not necessarily depend on the group size |G). Instead, depends on how far the distribution D's support is from the subspace Ted such that R could be much smaller than R. In fact, if the support D 'D is contained in Rdg then R = R, and the steerable network does not achieve any generalization gain. This is consistent with Theorem 4.1l in this case, the transformed data set S = {(x,, vi) [m]] is the same as the original data set S.
7 Conclusion and future work
In this work, we analyzed the implicit bias of gradient flow on general linear group-equivariant steerable networks in group-invariant binary classification. Our findings indicate that the parameter- ized predictor converges direction that aligns with the unique group-invariant classifier with maximum margin that is dependent the input representation. As corollary of our main result,

---

we established the equivalence between data augmentation and learning with steerable networks in our setting. Finally, we demonstrated that linear steerable networks outperform their non-invariant counterparts in terms of improved margin and generalization bound.
A limitation of our result is that the implicit bias of gradient flow studied herein holds in asymptotic sense, and the convergence rate to the directional limit might be extremely slow. This is consistent with the findings in, e.g. [Soudry al.) 2018 Yun al., 2021]. Understanding the behavior of gradient flow in a non-asymptotic regime is an important direction for future work. Furthermore, in our current framework, we assume that the first-layer equivariant map is represented by the G-lifting map. This assumption ensures that the linear steerable network possesses sufficient capacity to parameterize all G-invariant linear classifiers. Exploring the implicit bias of steerable networks without this assumption would be compelling next step. The removal of this constraint could facilitate the generalization of our findings from finite groups to compact groups.
Acknowledgements
The research was partially supported by NSF under DMS-2052525 DMS-2140982, and DMS- 2244976.
References
7. Allen-Zhu, Y. Li, and Song. convergence theory for deep learning via over-paramettriizaion.. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
X. Cheng, Q. Qiu, R. Calderbank, and G. Sapiro. RotDCF: Decomposition of convolutional filters for rotation-equivvariant deep networks. In International Conference on Learning Representations, 2019. URL httpst://///o
net//forumPPdd-H1l1EEjj00
L. Chizat and Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018.
T. Cohen and M. Welling. Group equivariant convolutional networks. In M. F. Balcan and K. Q. Wein- berger, editors, Proceedings The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 20-22 Jun 2016. PMLR. BRRLitttss:/pproceediiin .mr.r.sssm..................mr.. mlr http://wwoocciaaaaaaaeeeeeeeeeea www.ncce.cccc...ccm htmml
New York, New York, USA,
T. S. Cohen and M. Welling. Steerable CNNs. In International Conference on Learning Representa- tions, 2017. URL htttpp::/openreviex: wttp://ww...eeeooor/////dt//o
T. S. Cohen, M. Geiger, and M. Weiler. A general theory of equivariant CNNs homoge- neous spaces. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019, URL https://proceedinggs www.ineur.ic.ooo /ttpr/pps..c//pppe/////////
pdf
S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.
B. Elesedy. Group symmetry in pac learning. In ICLR 2022 Workshop Geometrical and Topological Representation Learning, 2022.
B. Elesedy and S. Zaidi. Provably strict generalisation benefit for equivariant models. In International Conference Machine Learning, pages 2959-2969 PMLR, 2021.
S. Gunasekar, Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR, 201 8a.
S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro. Implicit bias of gradient descent on linear convolutional networks, Advances in neural information processing systems, 31, 2018b.
A. Jacot, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. Advances in neural information processing systems, 31, 2018
10

---

Z. Ji and M. Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019a, JtLpptpse//pgarrei....etttttttmt HJf 1gf1g30
Z. Ji and M. Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pages 1772-1798. PMLR, 2019b.
Z. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 188:17766-1110 2020.
H. Lawrence, K. Georgiev, A. Dienes, and B. T. Kiani. Implicit bias of linear equivariant networks. 2021.
arXiv preprint arXiv:2110.0000:
K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020. URL https::/opperrerier net/
S. Mei, T. Misiakiewiez, and A. Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2464 PMLR, 2019.
M. Mohri and A. M. Medina. Learning theory and algorithms for revenue optimization in second price auctions with reserve. In International conference on machine learning, pages 262-270. PMLR, 2014.
M. S. Nacson, N. Srebro, and D. Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3051-3059. PMLR, 2019.
A. Sannai. M. Imaizumi, and M. Kawano. Improved generalization bounds of group invari- anteequivariant deep networks via quotient feature spaces. In Uncertainty in Artificial Intelligence, pages 771-780. PMLR, 2021.
S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
J. Sokolie, R. Giryes, G. Sapiro, and M. Rodrigues. Generalization error of invariant classifiers. In Artificial Intelligence and Statistics, pages 1094-1103. PMLR, 2017.
I. Sosnovik, M. Szmaja, and A. Smeulders. Scale-equivarian steerable networks. In International Conference on Learning Representations, 2020. URL SRLLhttts://operevviie wttpllwww.ee/ffooueeee net/forum?id HJgpugrKPS]
D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-2878. 2018.
G. Vardi. On the implicit bias in deep-learning algorithms. arXiv preprint arXiv: /2591, 2022.
M. Weiler and G. Cesa. General B(2)-equivariant steerable CNNs. In H. Wallach, Larochelle, A. Beygelzimer, F. d' d'Alché-Bue E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httphhttss//pppccdeiinggeeeee Paper. pdf
M. Weiler, F. A. Hamprecht, and M. Storath. Learning steerable filters for rotation equivariant cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 449-858,77 2018
D. E. Worrall, S. J. Garbin, D. Turmukhaabetov, and G. J. Brostow. Harmonic networks: Deep translation and rotation equivariance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5028-5037, 2017.
C. Yun, S. Krishnan, and H. Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2021. URL https:// openreview wwt.:eettourin ii ZsZM-41MQKR
W. Zhu, Q Qiu, R. Calderbank, G. Sapiro, and X. Cheng. bealingtraastaaion-equivvaaai networks with decomposed convolutional filters. Journal of machine learning research, 23(68): 2022.
11

---

A G-CNNS
special case of the steerable networks is the group convolational neural network (G-CNN), wherein equivariance is achieved through group convolutions. More specifically, for each E [L 11, the hidden representation space (Ri, pt) is
X ) {x1
R²),
( R E kg
(41)
The representation pt E (L( in [41 is known as the regular representation G. Intuitively, E Xg can be viewed as matrix of size di |G], and pr(g) is permutation of the columns of x;- With this choice {(2, pt) a (linear) G-CNN is built as follows.
First layer: the first-layer equivariant map V.CCNNN No X1 of G-CNN defined as
W (x: w (g) = w x E Rd, Vx E Rdo
(42)
where w1 (w J.k Rdoxd: are the trainable parameters of the first layer. Eq. (4) is called G-lifting map as it lifts Euclidean signal x E de to a function VC-CNN(x; (1; on G. Hidden layers: For l f2.
1}. define U.G.NNN X + X the group convolutions,
V.CCNN(N; (x; (x)))
Σ w/ ( g))(h) TR Vx E X-1, hEG
(43)
xi where wi(g) E R xdi Ag E G. Equivalently, w/ E Rdd-1xxxx can be viewed as 3D tensor.
XL-1 + X2 as the group-pooling followed by a fully-connected layer, Last layer: Define GGCCNN,
G-CNN (x: WL) = w |GI
Ex(9), Vx E XL-1,
(44)
|G|
9EG
where wt Rde-1 is the weight of the last layer. An L-layer linear G-CNN is then the composition
fx W) C.GCNN, (.... G--CNN (1GGNNN (x; w2):
W
[wi]en.
(45)
where W E Rdoxd x T x x Rdd-1 =: WG-CN are the trainable weights.
Remark A.1. As a special case of linear steerable networks, a linear G-CNN cGC W) can be written as
45
fG-CNN(x; W) = (x, (e..NN(W))) = (x, (W)c
(46)
where
L-1
|
PGCCN( = W1
II
Σ wi(g) gEG
WL, Po.cN(W)= =
1
Σ9 g
POCCN( (47)
G
gEG
B Proofs in Section
Proposition 3.3. Let Isteer W) be the linear steerable network satisfying Assumption 3.7 where Waser the collection of all model parameters. There exists multi-linear map
W wi wile
M (W2, ... wL) + M (WW, w..) E Idd such that for all E IRdo and W WWteen
(x W) = fssee W) (7, W (W2. "" (w)))"
(48)
where X = [ EgEa gx the average of all elements on the group orbit of x E IRdo
Proof. Since the linear steerable network faeer (x; W) is G-invariant, we have free (x; w) (gx; w) for all g E G. Therefore,
fatcer(x W)
G
Σ
fatcor (gx; W) fsteer
GG
1
Σ
gx:
fsscor W),
(49)
9EG
9EG
12

---

where the second equality is due to the linearity of fsteer (x; w) in x. We thus have
fstcer(x x W) = fstcer(5 [ W) = Vi (... 2 (1 (x; w1); W2) ... wL)
(50)
(Vi w), D (W2: WL))
(51)
where @(W2, ..... Wr.) 21 (Rdi) G is multi-linear with respect to (Wi,"., wr.) Under
Assumption 3.1. we have
fstcer( W)
[ ()) f ,WL((g)
(52)
gEG
( x. 1 W2, ((W2)--,,W)(())
(53)
SEG
Σ 9EG
(w, x, $(w,, ,"' (w,(())
(54)
Σ D(w2, ... w2X1o
X, W1
(55)
DEG
X W, W1MMM (W2, WL))
(56)
where M (w2, ......... WL) Egec (ww,. ... wr)(g) is also multi-linear in (W2, WL).
Proposition 3.6 Let Rd C Rdo be the subspace of G-invariant linear predictors, i.e., RG
[B Rd B =
3 gx, Vx E RRo Vg E G}. Then
(a) Re is characterized by
R n
ker(1 (I - g = -Range
Σ 9
(57)
9EG
BEG
(b) Let A:Rdo - dR be the group-averaging map,
A(B) = - G Σ 98.
(58)
9EG
Then its adjoint AT B + [ EgEG g TB is projection operator from TRd to Rdg. In other words, Bange(AA) TRdO and AT AT = AT.
1
(c) G acts unitarily on No, i.e,, p = po(g)T then A A self-adjoint. This implies that A: B + an orthogonal projection from dRdo onto R In particular, we have
B = + B E 12 and || < || VB e md.
(59)
Proof. To prove (a), for the first equality, vector B RR if and only if 0 TT g)x {(T T B,x), Vx E RRo, Vg G. This is equivalent f Ngec ker(T - g ) and therefore
IC = -gge ker ))
For the second equality, if B E Ngea ker(I [ T), then (I (I- T) 3
0. G. Hence
1
- T)3 3
Σ
g 3
(60)
G
G
gEG
gEG
B
Σ
g B Range
Σ TT
(61)
G
gEG
9EG
13

---

On the other hand, if 1 [c] Enech h y for some R then for all g E G,
(1- -1 -1-9)) )))
h h
h hTy y
Σ (hg)
(62)
G
G
BEG
REG
hEG
Thus B E NgEc ker(1 g)).
Point (b) can be easily derived from 57
and
60
To prove (c), notice that
1
AT
Σ 9
g=
(63)
G
gEG
gEG
gEG
Hence AA A is self-adjoint. This combined with point (b) implies that A = A 3+ 3 is an orthogonal projection from Rd onto R
C Proof of Theorem
Theorem 4.1,
Under Assumption 3.1 and Assumption 3.7 let (t) ( be the time-
(W)))
evolution of the G-invariant linear predictors parameterized by a linear steerable network trained with gradient flow on the duta set S = {(x;, V/) [m]];: cf. Eq. (1I) Then
(a) The directional limit B limm++0
[B]e exists and S [ Enec 9 Y, where
(t)
r is the max- L--margin SVM solution for the transformed data = {X,, W1) : [n]]]
arg min 7ER%
|r|1, S.L. Yi (X, 7) 2 1, [n].
(64)
Furthermore, if acts unitarily on the input space No. i.e., g = _, then B x y
(b) Equivalently, B is proportional the unique minimizer 3 of the problem
3 = aag min [ProjRanee ())3113 s.t. S.t. 3 E Reg and yi (x,. 2 1, [m], (65) BERdo
where ProjRamg(AA) is the projection from R: Range(A) Range [ Egeag) More-
over, if G acts unitarily on Xo. then
B x B arg min || S.t. B Ee and y (x,, B) 2 1, [n]] BER"O
(66)
Namely, Breer achieves the maximum I.2 .--margin among all G-invariant linear predictors.
we need the following lemma which holds for general L-homogeneous networks, of which linear stecrable networks are a special case. Note that in what follows, || always denotes the Euclidean norm of a tensor viewed as a one-dimensional vector.
Before proving Theorem 4.1
Lemma C.1 (paraphrased from Lyu and Li (2020) and Ji and Telgarsky [2020]. Under Assump-
tion 3.7 we have the following results of directional convergence and alignment.
(a) (W)); + 0, as + oc. Consequently, |[W(I) + oo and || (W + cc.
(b) The directional convergence and alignment of the parameters W(t and the gradients Ww (W())))((t)),
W(t) 8 = lim [(]]l
V Cyw (W ()):
lim
(67)
V CP StI:
for some W Water with | 1.
(c) The limit w is along the direction of first-order stationary point of the constrained
optimization problem
WlI. S.t. 34 (xi, Pateer Pstser(W) 2 1, Vi [n].
(68)
other words, there exists a scalingfactor T >> such that Wo0 satisfies the Karush- Carush-Kuhn-
Tucker (KKT) conditions of (68)
14

---

Proof of Theorem 4.7 The first part of the proof is inspired by Gunasekar et al. [0018b] To prove (a).
let 8 |w/ 111 lim
[ be the limit direction of W (t), and let W
(
7W > be the stationary point of problem (68) by Lemma C.1 The KKT condition for W
implies the existence of dual variables a; 2 0, i E [n]. such that
Pramst
V/ Psteer ( 2 1, Vi [m].
(69)
Stationarity:
Wa VW steer (Wo))
Σ 0ayiXii
(70)
Complementary slackness:
Yi Pstter (Wo),, xi) > ag 0.
(71)
We claim that > Pa steer (>>) is a stationary point of the following problem
min yERdo
s.t. y1 (x, 7) 2 1, vi E
(72)
That is, there exists à, 2 0, i E [n], such that the following conditions are satisfied.
framsiiea
Yi (Paeor (o)), xxx 2 Vi [m]
(73)
Stationarily:
P steer W 00)
ū,y;
(74)
Complementary slackness:
Mi P steer W > 1 + ā; =
(75)
Indeed, Eq. 73 holds due to Eq.
66 and (Psteer
Psteer
) ),x; = (P (Paeer Steer (wx) ) x;
Moreover, by
the definition of Psteer! () and P steer
(W) in 10 we have for any E Rdo
V Vw, P steer (W) 2 Z|M (22.
wr.)]
(76)
Vw, steer W) z
([M(22 ... WL.) ".
(77)
DEG
Therefore Eq. 770 implies
wi w1 P Stteer W20)
Σ asyix;
aayixi
[M
(78)
Hence
P steer W w M(w
w
Σ
|IM(WS.
(79)
15

---

0. where e MM ,.]l 2 0. From 73 we know that P Steer ( * 0 and hence >>
Let a; c0;; [n]. Then a; 2 O, and the stationarity (74)
satisfied due Eq. (79). and the complementary slackness also holds due to ã; being positive scaling of for all i E [n]-
Therefore 7-' Pawer ( stationary point of (72) Since problem 72) is strongly convex,
" = seer W is in fact the unique minimizer of Psteer (W(()) is
72 Hence the limit direction of the predictor
(iá Σ Egeco
P Patee (W(t))
Peter (()))
lim
lim
(80)
10000
P W())]
(1ā Egea 9") Psteer (W()))
Eger g
Patee
(WW(S)
C Egeag")
P
Psteer
W00
[
[W(OT]
lim
(81)
Egec 9¹)
P
steer
(W(() (W()l))
9")
Psteer steer
Wox)
9 r
(82)
gEG
where the third equality is due to Pster being I-hoomogeneous (12). and the fourth equality comes
from the continuity of P steer and that Pawer (Wo)= (iā) Eyec P
steer
W
*
(because
otherwise (69) can not hold.)
Finally, if G acts unitarily on No. then Eq. (74) combined with Proposition 3.6 implies that "
Potcor( (W E Rdg. Hence
B steer
α
GG|
E
G
Σ oy
=-'-"
(83)
9EG
gEG
where the last equality is again due to Proposition 3.6
This concludes the proof of (a).
To prove (b), first show that problem (65) has unique minimizer. To prove this, notice that ProjRange(A) R + Range(AA) is injective; indeed, for any Rd.
ProjRange( = 0 = B E Range(A)) ker(A")
(84)
Thus 0 = ATB B, where the second equality is due to A being projection onto Range(AA))
Rddo (Proposition 3.6) and B E IR Therefore the objective function in (65) strongly convex Redo and there exists a unique minimizer.
To show 2 B it suffices to verify that end, we notice that
G Egea
T 33 is the minimizer of 65 To this
1
AT - E Rd by Proposition 3.6
|G| for all e [n]
V/1
X1 |G|
9 x Ui (2,, 7)) 2 1.
(85)
gEG
Thus [ Egec 9 7" satisfies the constraints in (65)
Assume for the sake of contradiction that have
(a) Egec 9 x
T # Br, then by the uniqueness of the minimizer of 65
|R| = Proj Range (AA) (a) <
Proj Proj Range((( (A)
1
Σ9
TT
(86)
|G
DEG
where 7y (A) We make the following two claims to be proved shortly:
. Claim 1: y (7,x,) yi (B" xx) 1, Vi [n].
16

---

Claim 2: Proj (Ango [ Egec 9 X2= x==7" =
These two claims combined with (6) imply that 7 satisfies the constraint in (64) and has smaller norm compared to y", || < " This contradicts the fact that Y is the minimizer of problem (64). Therefore we have [G] Egea 9 3
If we assume in addition that po is unitary on Xn. then A = A :3 - B is an orthogonal projection from Rd onto & Range(AA). Therefore Projkane(AA) 3 B for B E IR and hence problems (65 and 666) are equivalent.
Finally, we prove the above two claims.
Proof of Claim 1: ys (7, x.) ys (181, x1) 2 1, Vi [m].
Since 7 = Proj Range (A) we have
- Br E RAage((A) = =kerAA)
(87)
Hence
A = A B == =
(88)
where the second equality is due to 3 E R = Range(AT] and A = =ATo o A is a projection;
cf. Proposition 3.6 Therefore, for all E [n].
31 (.. x,) y1 (A 7, x,) = 13"("" (8",,,) 2 1.
(89)
Proof of Claim 2: Proj A) A T7 y"
We first note that both Proj Range (4) A &T nrt and X* are in the affine space A 7² + ker(AT). Indeed,
ProjRange
(AT " ProjRange(A))- AT)")) 7²) Range(AA)+ = (AT(A)))
(90)
AT AT AT - A =0.
(91)
This also implies
A (ProjRango(A) A) (Tr²) =AT>"
(92)
Moreover, for any i [m].
y1 Proj (A) y", ) y (AT (Proj Rangee A A (xx) ,x
(93)
yi (A x,, = yı (r 21
(94)
Hence Proj Pranee A y also satisfies the constraint in (64 Since the orthogonal projection ProjRangs(A)) Y achieves the minimal norm among all vectors the affine space A 7 AT + -er(ATT)
which includes y", this can only happen when Proj Rango( A " Y is the unique minimizer of
64).
This concludes the proof of Theorem
D Proofs in Section 5
(us be the directional limit of the linear predictor Corollary 5.1 Let B = lim [B]l
(seer(t) = (st)((W(tt) parameterized by linear steerable network trained using gradient flow on the original data set S = {(x,, i E [n]]. Correspondingly, let B lim; (!]l
(t)
(L) (W()) 13 be that of a linear fully-connected network trained on the augmented data set S.ng ((gx), Ui) [n].g E G). IfG acts unitarily on Xn, then
B - 35c
(95)
other words, the effect of using a linear steerable network for group-invariant binary classification is exactly the same conducting data-auugmnntation for non-invariant models.
17

---

Proof. By Theorem 4.1 positive scaling y = B steer of B satisfies the KKT condition of (22
That is, there exists a, 0, [n], such that
Primal feasibility:
Ui (x) 21, Vi [n].
(96)
Stationarity:
?" = O
(97)
Complementary slackness:
y1 (Y x:) >
oj 0.
(98)
Using Corollary 4.3
we only need to show that y also the solution of
arg min ||>/ s.t. ys (gx;,)) 2 1, [m], e G. 7ER40
(99)
That is, there exists āigg 2 vi [n], Vgg E G, such that
Primal feasibility
Vi (1) EG Yi (Y .xx)) 21,
(100)
Stationarity:
(101)
i= gEG
Complementary slackness:
Yi (r" .gx.)
0igg 0.
(102)
Indeed, we set aig [ 04 0. Since 7" E Re if pu is unitary (this can also be observed from
Eq. 997) ). we have y/ ,y,,)) = y/ (r xx) Ag G, vi [m]. Hence we have primal feasibility
(100) from 96).
Vi (Y" .gx;) Vi y", |
Σ hgx;
Us (r xx) 21, W
(103)
hEG
Stationarity
[001] holds since
n Σ
n
Σ
Oclhgx; = Σ O = Y
(104)
G
1=1 9EG
1=1 +Ey BEG
where the last equality comes from
97 Finally, if Di (Y" .9x) > then T03 and (88 imply that
āi.g
0j 0.
(105)
This proves the condition for complementary slackness [022]
Corollary 5.5. Let B be the same as that in Corollary 5.1 Let 300.00
lim T (+)
3 (t)
be
the limit direction of 3 (1) Pie (L)) under the gradient flow the modified empirical loss C.P (W; Sagg) (34) for linear fully fully-connected network on the augmented data set Smn- Then
1/2
B x
Σ Po(g)) Po(g) BEG
3
(106)
|IG
Consequently, we have (x, Booar) oc (2,030000)
)
pa for all Rd
18

---

Proof. The proof is similar to that of Corollary 5.1 By Theorem 4.1 the limit direction 3 is proportional to
G Egec 9 y², where y satisfies the same KKT condition (166). (97 and (98) as in the proof of Corollary 5.1 On the other hand, note that the loss function
of problem
22
P (W; Smgg) equivalent to
34 for the modified fully-connected network on the augmented data set Sang is
Pi. (W; Saug)
Lexp (ix,,PPc( :B1)
(107)
gEG i=1
Lexp ((Agx,, Pte (W)) .9))
(108)
DEG
Lpc (W; Sa:)
(109)
where
1/2
( Σ po(g) po(s)
A
Swng
(Agxx, 9:) : i GJ.
(110)
9EG
Therefore, by Corollary 4.3 30a.00 is proportional to the solution Yaug of
Yuug arg min yER
171,,
s.t. yi (Agxi 2 Vi [n], Vg G.
(111)
We claim that Yog 1-1 [ E g JTrr). To see this, let ã. = 04, Vi [n]. where o, 2 0 is the dual variable for 7 problem (22). We verify below that the KKT conditions for problem |II are satisfied for the primal-duee pair A-1 (iā) Eyec g x-*) and (ār.g)i(()lo00-
Primal feasibility; for any i [m] and G,
V1
A
G
Σ g''r)
Ahix
G
Σ
9
lix:
(112)
gEG
9EG
>"
9
hx,
(113)
G
GEG
yi (7* x 2 1,
(114)
where the first equality is due A A being symmetric, and the last inequality due to
96
19

---

Stationarity:
A-1
G
Σ
9 8-
-1-1
[G]]
Σ 9
a,yiX;
(115)
BEG
DEG
A-1
Σ
9
Σ
Ogii Σ
li4
(116)
2
BEG
1=1
hEG
A A-
GG
atys
Σ
g
Txx:
(117)
BEG BEGGEG
AAAA A-
Σ
g g
Σ
hx:
(118)
G
i=1
gEG
hEG
U1
Ahx;
(119)
hEG
gig Agx
(120)
DEG
where the first equality is due to (97 and the last equality comes from the definition of the dual variable 0g = [ Ols; Vi E m. Vg
G.
Complementary slackness: y/ and g E G, then (14 and 98) imply that āigg = [ a; =0
C Egec! (oreggg())) Agx;)
for some [M]
Hence Yaug = A-1 (Tā) Σ Ege g x²)
is indeed the solution of 11I.. Therefore,
Bao
1
Σg EgT>"
A A.800000
(121)
GG
This completes the proof.
E Proofs of Theorem 6.1
Theorem 6.1
Let 3 be the directional limit of trained on the original data set 5 {(x1, y;), E [n]]; let B be that of a linear fully-connected network also trained on the same data set S. Let Maser and Mc respectively, be the (signed) margin of B and 3% on the augmented data set Saug = [gxx; yı) : E [n]. E G), iee.
predictor
Mateer = min Y/ (B gxi) Mc = min yi (8% ,9x)).
(122)
iE(").EEG
iE(r).eEG
Then we always have Msser 2 Mie-
Proof. By Corollary 4.3 and Corollary 5.I. we have
8
Ysieer arg min 7
||rl s.t. ye (r, (x, 2 1, Vg G, e [n].
(123)
8% Vie arg min 76
|| s.t. Di 9t 1, Vi [n].
(124)
Moreover, the margin Maser of the steerable network 2 on the augmented data set Saug Maser Consider the following three cases.
Case 1: min,elul.gEG Y4 (Tie. (x,))x..)))) 2 1. In this case, hi. also satisfies the more restrictive constraint in (123) Therefore Yie 7 which implies
320 and M Mcc
(125)
20

---

Case 2: mingg oe (Th- gx.) positive margin on D auy. Thus
S 0. This implies that Vie and hence B% has a non-
Mic I 0 Msteer.
(126)
Case 3: 0 (n) us (ree gx.)
In this case, define
The
(127)
min Yi (Yie, 9x.)
Then Nic satisfies the constraint in
123
and hence
(128)
Therefore
mingelai Di (
1
Mf. min yt ( EE [l
(129)
1i
1
M M
(130)
Ystoorl
This completes the proof.
F Proof of Theorem 6.3
To prove Theorem 6.3 we need first the following preliminaries.
Lemma F.1. D is G-invariant and linearly separable, then D can be linearly separated by G-imvariant classifier. That is, there exists B E RG such that
((x.a)=D ly (x, 1] 11
(131)
Proof. Since D is linearly separable, there exists Bg E RRdo such that P(x.)) (y Bo) 1] 1. Let B T Egea g G3 E RR and we aim to show that can also be linearly separated by 3. Indeed, for all (x, y) E Redo x {+1},
y (x
y x,
Σ 9 TTpo
Bo
<1
y
Σ DEG
gx, Bo
<1
(132)
G
9EG
3g E G, s.t. y (gx, Bo) < 1.
(133)
Let E [(x,))) : y (x, Bo) < 1] C do x {+)}, then
P P(x.g)< (x, 3) 1 < Σ
P (x <
(134)
DEG
Σ
D (xx, 9) (po(g) ld)(x; y) E E}
(135)
SEG
Σ (po(g) @ Id). (E) = Σ D
(136)
9EG
gEG
IP ((xa)~D [V (x, Ba) < = 0,
(137)
9EG
where the second equality in (136) is due to D being G-invariant, Therefore D can be separated by B Rdg.
Definition F22 (Empirical Rademacher complexity). Let F R be class of real-valued functions on 2, and let S (21, ... .7n) be a set of n. samples from 2. The (empirical) Rademacher complexity R., (F,S) of F over S is defined as
(R.F.)) = EEo((t))
sup Σ ozf(zz)) JEF
(138)
where o (a), σn) are the i...d. Rademacher variables satisfying IP(o; = 1] 1= =P(o; = -1] 1/2.
21

---

Lemma F.3 (Talagrand's Contraction Lemma, Lemma 8 in Mohri and Medina (014 ). Let Py: R R. E [n]. be L-Lipschitz functions, F C R be a function class, and (Zi....,Z,, Zn) E "
be a set of n samples from 2. Then
n a o s(zi)
(F,)) 2
sup |EF
(139)
n
Lemma F.4. Let H (x~>> (G, x) 3 E Redo || S B) be the function space of G-invariant
linear functions of bounded norm, and let Sx = {x1, .. xn} c IR be a set of n samples from Rddo Then
B maxie(m)
|
Ru (H,
(140)
n
Proof. By the definition of empirical Rademacher complexity
138
we have
n
RRR (H,, = FE
sup
Σ
as (3, x;)
(141)
EE
sup
0s x1)
(142)
BER .IABISBBBBBBBB i=1
EE,
sup
B,
oiXi
(143)
BER ||
i=1
= BE
O,Xi
(144)
Aml
2
1/2
S B
Eg
O,X;
(145)
where (42) is due to 3 E Rdg, Since a1, on are i.i.d., we have
EEg
Eg
Eo.o (X,,
(146)
X,, xz) E 0z0 + Σ |x,
|| 2 B
(147)
(
1=1
x 12 max max
|
|
(148)
[E(x]
Eq. 145 combined with (148) completes the proof.
We also need the following standard result on the generalization bound based on the Rademacher complexity Shalev-Shwande and Ben Devid 2014]. Lemma F.5. Let H. be a set of hypotheses, Z = RR x {+1} be the set of labeled samples, and
P: x Z + 10, (h. + e(h, z).
(149)
be loss function satisfying 0 < E(h,z) < for all Z and h H. Define the function class == E(H.)) .) = {z + E (h,z) z) h E H}. Then, for any 8 > 0 and any distribution D on Z, we have with probability at least 1 5 over i.i.d. samples (z)..... zn) D= that
log(1/5)
sup (h) - Cs(h) < 2R, + ov keh
(150)
2n
22

---

where Lp(h) = EE-pe(h,z z) and (s(h) = Ei= ((h,zi) are. respectively, the population and empirical loss of hypothesis h H. and (F) = (, the Rademacher complexity of F.
Finally, we can prove Theorem 6.3 restated below
Theorem 6.3 Let D be G-invariant distribution over RR x {+1} that is linearly separable by an
invariant classifier Bo E Re Define
R= inf (r > O: |ス S r with probability }}.
(151)
Let S - 9i) be i.i.d. samples from D, and let F be the limit direction of a steerable- network- paranntereed linear predictor trained using gradient flow on S. Then, for any >> 0, have with probability at least 8 (over random samples S D that
2R
log (1/5)
P ((xy)DD ly + sign ((x, Plsse))
(152)
vn
2n.
{ R || < |Bll]} and with slight abuse of notation we identify B with the invariant linear map x ト (x, 33). According to Theorem [4.1] let
Proof of Theorem 6.3 Let H
3 T ster 0, be the minimizer of (24). Since by assumption Bo also satisfies the constraint in
24 we have || - [| and hence f E H.
Consider the ramp loss l defined as
8 H x (R& {+1]) - [0, I], (8, (x, v)) + min(1, max 1 (x,
(153)
is easy to verify that l upper bounds the 0-1 loss: for all , E: H. and (x, v) 1d {+1).
EB3 (x, v)) 2 (xx))))(((xx8)))-
(154)
This implies that
P P(x,)) IV + sign ((x, S ((x.)) (V F sign ((x,3"))
(155)
E(x,)) ~D ( (x,3-)) )}}
(156)
S (x.,)) De (x, v)) (D(
(157)
Since Ls()t) always 0 by definition 24 and B E H. we have by Lemma F.5 that
P P(xy)~D (y # sign ((x, ( S LD(33) = (D( - (s(3)) S sup LD(B) - (.( (158)
BEH
22) + log(1/8)
(159)
2n
where F= ((H,-) = {(x y) + é (B, (x, v)) 3 E H.}. Therefore, to prove Theorem 6.3 it suffices
to show that (F) -
To this end, let S {(x,, y.) : i [m]} be a set of n labeled samples, and let Sx fx, i [m]} be the corresponding set of unlabeled inputs, then
R
/n
(F,
E sup " fEF i=1
Σ or oxf((x; Vi)
(160)
1 - F. sup BEH
orl (L, (x:: v:))
(161)
E sup
a min ma, - ys (x,,8))
(162)
n BEH
E sup
Σ of ((x,,
(163)
n
BEH
where の. : RR + R. min (1, max (0, yja) is 1-Lipschitz. Lemma F3 thus implies that
(F, < (H,,
(164)
23

---

Using Lemma F.4 and the fact that x I R with probability over (x,)) ~ D, we arrive at
R|lBoll
Rn ES (n SS) S R Sx, <
(165)
vn
This completes the proof of Theorem 6.3
24


Reviews:
[{"review_id": "tILYwCpoDZ", "reviewer": "Reviewer_WwNm", "summary": "This paper analyzes the implicit bias of gradient flow on linear group-equivariant steerable networks for group-invariant binary classification. It shows that the parameterized predictor converges in a direction that aligns with the unique group-invariant classifier with a maximum margin that is defined by the input representation. Under a unitary assumption, this paper also suggests the equivalence between data augmentation used in non-invariant models and learning with steerable networks. When the underlying distribution is group-invariant, linear steerable networks outperform their non-invariant counterparts in terms of improved margin and generalization bound.", "questions": "Are these findings limited to binary classification?", "limitations": "None", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is organized in a way easy to read and follow. The authors provide sufficient background knowledge for readers to understand Equivariant Steerable Networks. And all the assumptions are stated clearly in the problem setup section.\n2. The contributions of the paper have been listed in a rather detailed and clear way in the paper. The authors point out their main findings in theorems, followed by explanations in remarks and close each section with corollaries. \n3. The findings presented in this paper explain the success of equivariant steerable networks to a certain extent.", "weaknesses": "1. The authors claim to fully characterize the implicit bias of the training algorithm. However, there is no experiment on empirical dataset other than theoretical results throughout the paper. It would be more promising if the conclusion can be supported by empirical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment 1**: The authors claim to fully characterize the implicit bias of the training algorithm. However, there is no experiment on empirical dataset other than theoretical results throughout the paper. It would be more promising if the conclusion can be supported by empirical results.\n\n**Answer**: We totally agree with the reviewer that empirical verification of the theory established in this paper could  substantively enhance the impact of our theoretical findings. However, a notable limitation of our findings is that the implicit bias of gradient flow, as studied here, holds true only in an asymptotic sense. The convergence rate to the directional limit is, in fact, exponentially slow. This is consistent with the findings in Ref [1,2]. Specifically, Ref [2] shows that even if the loss function reaches an order of $10^{-5}$, the limit direction of the parameterized classifier (of a linear fully-connected network) is dependent on the initialization. This is because the networks are not trained all the way to zero loss. Understanding the behavior of gradient flow in a non-asymptotic regime is an important direction for future work.\n\nWe have mentioned this limitation in the conclusion of our paper, and we will emphasize this point further in the main text of our revised manuscript.\n\n[1] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822–2878, 2018.\n\n[2] C. Yun, S. Krishnan, and H. Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2021"}, {"review_id": "v3pWDBtbqQ", "reviewer": "Reviewer_vUEN", "summary": "The paper considers the implicit bias of gradient flow optimization for linear equivariant steerable networks. The paper consists of the following steps and contributions: \n* The equivariant network is assumed to have regular representation at the input (Assumption 3.1). The architecture is characterized in Proposition 3.2, and is based on an overparameterized linear function applied to group averaged input.\n* The space of G-invariant linear classifiers is characterized in Proposition 3.6, which can be seen as the range of the adjoint of group projection operator. (same as the group projection for unitary representations)\n* The analysis of gradient descent is done based on using gradient flow (eq 25). Assuming the existence of G-invariant separating function (Assumption 3.7), Theorem 4.1 shows that the gradient flow converges to a maximum margin G-invariant classifier.\n* A fully connected linear network with data augmentation converges to the solution \\textbf{direction} for linear steerable network for unitary input representation (Corollary 5.1), and with modified loss for non-unitary input representation (Corollary 5.4). \n* Despite sharing the direction, the margin is still larger for the steerable model (Theorem 6.1).\n* Finally, the generalization bound for steerable and non-steerable models are obtained using classical results for max-margin SVM from the book of S. Shalev-Shwartz and S. Ben-David. (Theorem 6.3)\n\nAs I mention below, the paper has a collection of interesting result in a previously unexplored topic. However, I have some technical concerns about the definition of the model, and would like to hear the authors’ answers.\n", "questions": "\n* Does not the choice of regular representation for the input impose that $d_0$ is a function of group size? The steerable network of Cohen and Welling 2017 is more general and includes translation operations and features fields. \n* How does the result generalize to compact but not finite groups? For example, the data augmentation for compact inifinite groups seems to be non-trivial. Some discussions on this point can be useful for the paper.\n* There are some follow-up works on the generalization bounds for equivariant networks with implicit and explicit bounds on the error. It is good to discuss the connection and compare the bound. It seems that all these works relate the generalization gain to the group size, which is different  from the current paper.\n   * Sicheng Zhu, Bang An, and Furong Huang. Understanding the Generalization Benefit of Model Invariance from a Data Perspective. In Advances in Neural Information Processing Systems, 2021\n  * 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\n  * Arash Behboodi, Gabriele Cesa, Taco Cohen, A PAC-Bayesian Generalization Bound for Equivariant Networks, In Advances in Neural Information Processing Systems, 2022\n\n\n", "limitations": "See above comments.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper considers the problem of implicit bias for equivariant networks using gradient flow analysis, which was not previously studied in the literature. Although the results seem to be mostly based on s. techniques of Lyu and Li [2020] and Ji and Telgarsky [2020], the conclusions are interesting, in particular, the equivalence of data augmentation and model equivariance in terms of converged direction.  ", "weaknesses": "\n* I have some concerns about the choice of linear model for equivariant networks. When considering linear group invariant classifiers, the steerable network, based on Schur’s lemma, utilizes only the trivial representation (See M. Weiler and G. Cesa 2019). The authors noticed a similar issue with Lawrence et al. 2021 paper, as they mentioned “In their case, the only group-invariant linear classifier is the group average of the input up to a scalar multiplication, due to the transitivity of the regular representation”. To summarize, a linear invariant network with equivariant kernels works only with trivial representations. In other words, only a single basis in equation (4), the one corresponding to the trivial irrep, matters for the optimization and the output. It seems to me that the current definition in (4) can be misleading in this sense. Note that Proposition 3.2 indicates as well that the network is only dependent on a group averaged version of $\\mathbf{x}$. \n* It seems that the equation (7) does not define an equivariant map. If we assume a regular representation,  then the map is equivariant only if $\\mathbf{w}_1$ has a group circulant structure. With this additional required structure, Lemma B.1 in the supplementary material cannot be directly applied, because of entry repetition in $\\mathbf{w}_1$. Note that according to assumption 3.1, the regular representation and $G$-lifting map is assumed for the first later.\n* The independence of the generalization error from group size in Remark 6.5 should be considered with care. Note that there is an experimental evidence, although light, for the impact of group size on the generalization (see Sokolic et al). On the other hand, the group size can shrink the size of the space $\\mathbb{R}^{d_0}_{G}$, and can potentially reduce $\\overline{R}$ proportional to the group size. I feel that Remark 6.5 should be a bit more nuanced. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment 1**: When considering linear group invariant classifiers, the steerable network, based on Schur’s lemma, uses only the trivial representation. I.e., only a single basis in equation (4) matters for optimization and the output. The definition in (4) is misleading in this sense. Proposition 3.2 indicates that the network is only dependent on a group averaged version of x.\n\n**Answer**: We thank the reviewer for the insightful comment. You are correct: based on Schur's lemma, the final linear predictor parameterized by a multi-layer linear steerable network uses only the trivial representation, due to the trivial representation on the output layer.\n\nHowever, we emphasize that although the parameterized linear predictor has simple form, the manner in which this predictor is parameterized has huge impact on the optimization, and consequently, the implicit bias. E.g., in Ref. [1]: even though linear CNNs and linear fully-connected nets equivalently parameterize all linear predictors, they have distinct inductive biases.\nWe also emphasize that although the output representation is the trivial representation, we do not limit the selection of representations for hidden layers. Hence multiple bases can coexist in equation (4).\n\n[1] C. Yun et al.. A unifying view on implicit bias in training linear neural networks. ICLR, 2021\n\n**Comment 2**: Equation (7) is not equivariant.\n\n**Answer**: We provide a simple proof: Eq.(7) reads\n$$\\Psi_1^{\\text{G-CNN}}(x, w_1)(g) = w_1^\\top g^{-1}x.$$\nWe need to check:\n$$ \\Psi_1^{\\text{G-CNN}}(hx, w_1) = \\rho_1(h) \\Psi_1^{\\text{G-CNN}}(x, w_1), \\forall h\\in G$$\nThe LHS when evaluated at $g$, is:\n$$ \\Psi_1^{\\text{G-CNN}}(hx, w_1)(g) = w_1^\\top g^{-1}hx.$$\nThe RHS is\n$$ \\Psi_1^{\\text{G-CNN}}(x, w_1)(h^{-1}g) = w_1^\\top (h^{-1}g)^{-1}x.$$\nHence it is equivariant.\n\n**Comment 3**: The independence of the generalization error from group size in should be considered with care. Experimental evidence exists for the impact of group size on generalization (Sokolic et al). The group size can shrink $\\mathbb{R}_G^{d_0}$, and can potentially reduce $\\bar{R}$.\n\n**Answer**: The reviewer is correct that the situation is more nuanced. In Theorem 6.3, we show that the improvement in generalization is **directly** tied to the reduction from $R$ to $\\bar{R}$, on which the group size may or may not have an impact. E.g., consider the input space $\\mathbb{R}^3$, on which $G=SO(2)$ acts by rotating around the z-axis. Regardless of the cyclic subgroup $C_n$ of $G$, as long as $n\\ge 2$, the averaged input $\\bar{x}$ is always the same for any $x$, i.e., $\\bar{x}$ is the projection of $x$ onto the z-axis. Hence $\\bar{R}$ is the same, no matter the group size $|C_n|=n$.  However, that there are certainly cases where the group size will (indirectly) affect generalization by reducing $\\bar{R}$.\n\nWe emphasize that this conclusion is reached **only** after considering the role of training in NNs. This understanding is largely absent in most existing research that attempts to quantify the generalization gain when learning under symmetry. Regarding the comparison with Sokolic et al., we will provide a detailed response to another question below.\n\n**Comment 4**: Does not the choice of regular representation for the input impose that $d_0$ is a function of group size?\n\n**Answer**: The regular representation is chosen only for the first hidden layer, while the input $G$-representation is not restricted.\n\n**Comment 5**: How does the result generalize to compact but not finite groups? For example, the data augmentation for compact inifinite groups seems to be non-trivial.\n\n**Answer**: Our current work contains a restriction that hinders us from directly extending the result to compact groups. This limitation is Assumption 3.1, which mandates that the first layer is a \n$G$-lifting map, with the first-layer features explicitly represented as matrices. Should this constraint be removed, we would be poised to expand our result to encompass compact groups.\n\n**Comment 6**: There are some follow-up works on the generalization bounds for equivariant networks. It is good to discuss the connection and compare the bound. It seems that all these works relate the generalization gain to the group size, which is different from the current paper.\n\n**Answer**: Many existing works that relate generalization gains for equivariant networks to group size are founded on this reasoning: the invariance of the target function suggests that learning operates on the quotient space of group orbits. This leads to a decrease in the covering number, and consequently, the Rademacher complexity. This reduction is connected to the group size. For instance, in Sokolic et al., the data distribution is assumed to be confined to $X = G\\times X_0$, so $G$-invariant models are essentially learning on $X_0$, resulting in a $|G|$-fold decrease in covering numbers.\n\nWhile these methods can establish a worst-case generalization upper bound that applies universally across distributions, they overlook a critical aspect, i.e., the training of neural networks. Notably, under specific distributions (those with $\\mathcal{D}\\subset \\mathbb{R}^{d_0}_G$ in our paper), learning with or without an equivariant constraint when trained under GF converges to the same solution. Consequently, imposing group symmetry does not yield any generalization gains.\n\nA related example involves training w/ and w/o data augmentation. If a data distribution is such that all samples remain unchanged after augmentation, then the use of data augmentation provides no advantage. Our generalization result, as articulated in Theorem 6.3, clarifies that it is not merely the group size but the distance between the distribution $\\mathcal{D}$ and the subspace $\\mathbb{R}^{d_0}_G$ hat influences the enhanced generalization of equivariant networks. This insight emerges when the training aspect is factored into the analysis."}, {"review_id": "SmAN7vlQEi", "reviewer": "Reviewer_UfQK", "summary": "This paper studies the implicit bias on the use gradient flow for the purpose of binary (group-invariant) classification while using linear equivariant steerable networks. There is now a fair amount of work on implicit bias in similar settings in the non-equivariant case. There is also some work for linear equivariant networks. However, as the authors note, it is unclear whether a steerable network, trained by gradient descent, can achieve a minimizer with some parameter norm which is comparable to non-equivariant cases. The main results essentially show that linear steerable networks trained on some data converge to the same direction as a fully connected NN trained on augmented data. Moreover, such a network trained on the original data always attains a wider margin than a fully connected network trained on augmented data. An additional result is shown that a linear steerable network trained using gradient flow has better generalization than its non-equivariant counterpart when the data has an group invariant distribution. Section 3 describes the background and results formalizing and proving some of the above points are shown in later sections. \n\nMinor comments:\n- On page 3, line 122: \"Equivalently, we want the following diagram to be commutative..\" --> reword this since that diagram is already commutative, but that you want your network to adhere to it. ", "questions": "- Please improve the discussion around the work of Lawrence (2021) at the end of page 2 and beginning of page 3. I am unable to parse the comments here. How are they \"not actually invariant or equivariant\" just because \"input is on a group\"? The inputs can be on a group in general in equivariant networks, or on spaces on which a group acts. I am also confused with the random claim that the paper works with Euclidean inputs with non-transitive actions. I don't think the formalism here is more general than operating on homogeneous spaces. Do the authors mean something else? I would appreciate a clarification. ", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The results, to the best of my knowledge, are solid and represent a good contribution complementing a host of body of work for non-equivariant models. \n- Generally speaking the paper is well written (although there is a flip side to this, which I will write in the weakness) and has a non-trivial contribution.", "weaknesses": "- One issue with the paper is its density. A lot of time is spent on background that doesn't need to be in the main paper. I understand the authors want to be thorough and that this is difficult. However, the essential idea and the proof techniques that the authors use, and the literature that it builds upon, are well-known, hence so much background is not necessary. I would suggest putting some of this material in the appendix and expanding on the results presented in the paper better and also comparing them to existing results. \n- Related to the above. I think the writing can be made more easy going (even if I had no problem in following it). I would understand for certain problems such heavy formalization is necessary. But I think this particular problem doesn't need it. It could be written simply. But in any case I would like to see more discussion about the actual results than the background. If the authors think so much of the background is necessary, I would be curious to hear their arguments. I think we can drop describing what a group or representation is, for example. It doesn't have to be done in every paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Minor Comment**: On page 3, line 122: \"Equivalently, we want the following diagram to be commutative..\" --> reword this since that diagram is already commutative, but that you want your network to adhere to it.\n\n**Answer**: We thank the reviewer for pointing this out. Yes, the diagram has indicated commutativity and we will reword it in the revised manuscript.\n\n**Comment 1 and 2**: One issue with the paper is its density. A lot of time is spent on background that doesn't need to be in the main paper.  I would suggest putting some of this material in the appendix and expanding on the results presented in the paper better and also comparing them to existing results.\n\n**Answer**: We thank the reviewer for the thoughtful suggestion. In line with this guidance, we will relocate some of the relevant but not strictly essential group-theoretical background information to the appendix. This will allow us to streamline the main text. In its place, we will improve the readability of the paper by including additional remarks and discussion, aimed at comparing our results with existing works in the field.\n\n**Comment 3**: Please improve the discussion around the work of Lawrence (2021) at the end of page 2 and beginning of page 3. I am unable to parse the comments here. How are they \"not actually invariant or equivariant\" just because \"input is on a group\"? The inputs can be on a group in general in equivariant networks, or on spaces on which a group acts. I am also confused with the random claim that the paper works with Euclidean inputs with non-transitive actions.\n\n**Answer**: In the work of Lawrence et al. (2021), the inputs to their networks are functions over a group $G$, and the input group action is characterized by the regular representation. Specifically, the input space is defined as $X_0 =$ {$f:G\\to\\mathbb{R}$}, with the input action given by\n$$(\\rho_0(g))f(g') = f(g^{-1}g'), \\forall g\\in G, \\forall f\\in X_0$$\nUpon inspection, one can prove that, under their setting, $G$-invariant linear functions  $\\Phi:X_0\\to\\mathbb{R}$ are constrained to the (trivial) form:\n\\begin{equation*}\n    \\Phi(f) = C \\sum_{g\\in G}f(g),\n\\end{equation*}\nwhere $C$ is a multiplicative constant.\n\nTo avoid learning this trivial function, Lawrence et al. (2021) chose to parameterize $\\Phi$ using a group-convolutional neural network, in which the final layer is replaced by a fully-connected (FC) layer. While this FC layer provides the capability to learn more complex and nontrivial functions, it simultaneously undermines the property of group invariance.\n\nOn the other hand, in our paper, the input space is the Euclidean space $X_0 = \\mathbb{R}^{d_0}$, and there exist non-trivial linear maps that are invariant to the input group action. We will include an explicit explanation in the revised version of our paper."}, {"review_id": "OdtKmQor4o", "reviewer": "Reviewer_3ceq", "summary": "The paper presents a collection of theoretical findings that highlight the equivalence between using a linear steerable network for group-invariant binary classification and employing data augmentation for non-invariant models within the specified context. Additionally, the paper demonstrates that linear steerable networks outperform their non-invariant counterparts in terms of generalization bounds.", "questions": "Please improve the presentation of implications of the research findings and future research directions.", "limitations": "The limitations of the theoretical study are adequately discussed.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "* The paper builds upon previous studies that have explored the implicit regularization properties of different network architectures. It references works that have examined the convergence of linear predictors trained under gradient descent (GD) towards max-margin support vector machines (SVMs) and the implicit regularization of linear convolutional and tensor networks.\n\n* The paper discusses the design of group-equivariant DNNs that preserve symmetry transformations in both input and output spaces. It highlights the empirical evidence suggesting that group-equivariant steerable networks improve generalization performance, especially in tasks with group symmetry and limited data.\n\n* The paper presents its key result, which demonstrates that linear equivariant steerable networks trained under gradient flow (GF) converge towards the unique group-invariant classifier that maximizes the margin with respect to a norm defined by the input group representation.", "weaknesses": "This paper is theoretical in nature. It does not present any new empirical results or experiments to validate its claims. Unfortunately, the reviewer has little knowledge of the topic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment 1:** This paper is theoretical in nature. It does not present any new empirical results or experiments to validate its claims. Unfortunately, the reviewer has little knowledge of the topic.\n\n**Answer:** We agree with the reviewer that empirical verification of the theory established in this paper could  substantively enhance the impact of our theoretical findings. However, a notable limitation of our findings is that the implicit bias of gradient flow, as studied here, holds true only in an asymptotic sense. The convergence rate to the directional limit is, in fact, exponentially slow. This is consistent with the findings in Ref [1,2]. Specifically, Ref [2] shows that even if the loss function reaches an order of $10^{-5}$, the limit direction of the parameterized classifier (of a linear fully-connected network) is dependent on the initialization. This is because the networks are not trained all the way to zero loss. Understanding the behavior of gradient flow in a non-asymptotic regime is an important direction for future work.\n\nWe have mentioned this limitation in the conclusion of our paper, and we will emphasize this point further in the main text of our revised manuscript.\n\n[1] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822–2878, 2018.\n\n[2] C. Yun, S. Krishnan, and H. Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2021"}, {"review_id": "NFW4CLusaP", "reviewer": "Reviewer_nbB9", "summary": "The paper present several results on linear equivariant steerable networks. 1) linear equivariant NN converge in the same direction as linear networks trained with data-augmentation, 2) equivariant networks always attain a larger margin then group-augmented fully connected networks, 3) also the generalization bounds are better for equivariant networks when the data distributions is group invariant.\n\n* score has been updated after the response to my assessment.", "questions": "1. Why is the emphasis on equivariant *steerable* networks? (instead of just equivariant networks) Steerability is I suppose a matter of definition, but classically the difference lies in whether you use the regular representation (G-convs) or irreducible representations (steerable G-convs) to generate the G-feature maps. Since the paper primarily focusses on the regular representation, I do not see why it is important to emphasize steerability. Moreover, line 79 says “more generally, steerable”, but I don’t think steerable G-CNNs are more general per se. That is, any linear layer is equivariant iff it is a group convolution [bekkers2018, thm1] regardless of the used feature type (one can always convert between regular representations and irreps via a generalized Fourier transform). See e.g. WeilerAndCesa 2019 or Brandstetter et al 2022 where this is recently discussed. \n\nBekkers, E. J. (2019, September). B-Spline CNNs on Lie groups. In International Conference on Learning Representations.\n\nWeiler, M., & Cesa, G. (2019). General e (2)-equivariant steerable cnns. Advances in neural information processing systems, 32.\n\nBrandstetter, J., Hesselink, R., van der Pol, E., Bekkers, E. J., & Welling, M. (2021, October). Geometric and Physical Quantities improve E (3) Equivariant Message Passing. In International Conference on Learning Representations.\n\n2. How does the following reference relate to the current work? It is also about generalization bounds of equivariant networks (through PAC learning) and thus seems related.\n\nElesedy, B. (2022, March). Group symmetry in PAC learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning.", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "* The paper presents a collection of statements about equivariant linear networks which could be useful as a general reference\n\n* Although the paper is extremely dense in information, it is readable and self-contained. The supplementary materials provide all the proofs.", "weaknesses": "1. The paper is essentially a mathematics paper and is the question to what extend it fits the scope of NeurIPS. As a non-mathematician, but someone interested in these topics, I did verify some of the proofs and the overall presentation is clear, however, I find it hard to assess the significance of the work.\n\n2. In particular, the limited scope on linear layers almost make the result seem trivial (though not from the mathematical perspective). To what extend do these results give insights on non-linear, multi-layer equivariant neural networks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment 1:** The paper is essentially a mathematics paper and is the question to what extend it fits the scope of NeurIPS. I find it hard to assess the significance of the work.\n\n**Answer:** Our research is indeed theoretical in nature, and we think it fits within the scope of NeurIPS, as reflected in similar works appearing in top ML conferences; see Ref. [1-4] for instance.\n\nOur work studies the training dynamics and inductive biases of NNs, a key aspect in explaining their generalization. Although there is a vast empirical body of work showcasing the improved generalization of equivariant NNs in group-invariant learning tasks, our paper is unique in rigorously showing that these networks indeed converge to a better solution when compared to their non-equivariant counterparts.\n\nMoreover, we have shown that in the framework we explore, data augmentation is equivalent to learning using equivariant nets. This has long been a postulated hypothesis but, to our knowledge, not rigorously proven until now.\n\nWe believe our findings contribute significantly to the field, providing new insights that have been suspected but not previously confirmed.\n\n**Comment 2:** The limited scope on linear layers make the result seem trivial. To what extend do these results give insights on non-linear, multi-layer equivariant NNs?\n\n**Answer:**  The study of implicit bias in linear nets often serves as an initial step towards unraveling the complexities of implicit bias in deep nonlinear nets. While there has been a surge of recent research aiming to explain the implicit bias in nonlinear nets, the field remains largely open. A particular insight gleaned from our paper's results is that equivariant nonlinear nets may achieve a larger margin in the **parameter space** compared to their non-equivariant counterparts, as alluded to in Theorem 6.1.\n\nWe respectfully disagree with the reviewer's assessment that the limited focus on linear layers renders our results trivial. On the contrary, as elaborated in response to the previous comment, our theoretical findings offer fresh perspectives on the generalization capabilities of equivariant networks, as well as their relationship to data augmentation. These insights provide tangible advances in understanding concepts that have been speculated upon but not definitively proven until now.\n\n**Comment 3:** Since the paper primarily focusses on the regular representation, I do not see why it is important to emphasize steerability. Moreover, I don’t think steerable G-CNNs are more general per se. Any linear layer is equivariant iff it is a group convolution [bekkers2018, thm1] regardless of the used feature type (one can always convert between regular representations and irreps via a generalized Fourier transform)\n\n**Answer:**  We appreciate the reviewer's perceptive comment. The concept of steerability, as utilized in our paper, is indeed a matter of definition. We employ this term to highlight our ability to select any representation within the hidden layers of the equivariant networks. Importantly, we are not confined to using regular representations beyond the initial hidden layer.\n\nThe reviewer's observation that \"converting between regular representations and irreps via a generalized Fourier transform\" is spot-on. Yet, it is crucial to recognize that the way these networks are parameterized (stemming from the different representations adopted in each layer)  have an impact on the model's implicit bias. For clarity, we refer to Ref. [1], where it's illustrated that even though linear CNNs and linear fully-connected nets can equivalently parameterize all linear predictors, training dynamics of these networks differ significantly, resulting in distinct inductive biases. We will elaborate on this point in the revision to ensure a clear understanding.\n\n\n**Comment 4:** How does the following reference relate to the current work? It is also about generalization bounds of equivariant networks (through PAC learning) and thus seems related. Elesedy, B. Group symmetry in PAC learning.\n\n**Answer:** We thank the reviewer for bringing this paper to our attention. Our understanding is that this work, like many other existing studies that quantify generalization gains for equivariant networks through PAC learning, fundamentally relies on the following reasoning: the invariance of both the target function and the neural networks means that learning is effectively conducted on the quotient space of group orbits. This results in a reduction of the covering number, and hence, the Rademacher complexity of the hypothesis space, which is used to derive the improved generalization bound.\n\nWhile these approaches can formulate a worst-case generalization upper bound that is universally applicable to all distributions, they may neglect a vital aspect of neural network, i.e., the training process. When this training aspect is taken into consideration, the enhanced upper bounds posited in these works may not necessarily be meaningful. For instance, in our paper, under certain distributions (denoted as $\\mathcal{D}\\subset \\mathbb{R}^{d_0}_G$), learning with or without the equivariant constraint converges to the exact same solution when models are trained using gradient flow. As a result, the imposition of group symmetry does not lead to any improvement in generalization, in contradiction to the findings of the existing works where the training aspect is not accounted for. We believe that our perspective offers a more nuanced understanding that aligns more closely with the behavior of models during the training process.\n\n[1] C. Yun et al. A unifying view on implicit bias in training linear neural networks. ICLR, 2021\n\n[2] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. ICLR, 2020\n\n[3] Z. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. NeurIPS ,2020.\n\n[4] H. Lawrence et al., Implicit Bias of Linear Equivariant Networks. ICML, 2022."}, {"review_id": "DFL7Of2Hx4", "reviewer": "Reviewer_H6K3", "summary": "This paper studies an implicit bias of gradient descent (GD) on linear equivariant neural networks. The authors show that the asymptotic GD solution of a linear steerable neural network, an instance of the equivariant nets, agrees with that of an FC net trained with data augmentation. They also show that the former achieves better margin and generalization bound than the latter. ", "questions": "1. The implications of Theorem 4.1 and Corollary 5.1 are interesting. Theorem 4.1 says that the GD solution of a steerable net converges to the max margin solution trained on the group-averaged data $\\bar{x}$. In contrast, Corollary 5.1 shows an FC net trained on the group-augmented data converges to the steerable net, which suggests that group averaging in the data space and data augmentation have roughly the same effect. This is not trivial because group averaging takes all possible augmentations for each data instance, but data augmentation puts a single transformation. In the sense of loss function, the former is written as $\\mathrm{loss}(E_{g}[gx])$ while the latter is $E_{g}[\\mathrm{loss}(gx)]$. Can you explain why these two are possibly equivalent?\n2. Related to the above question, I feel that group averaging is somehow similar to mixup, which augments data as $\\lambda x + (1-\\lambda) x'$ for $\\lambda \\in [0, 1]$. We may write group averaging as a special case of mixup, where we take an average in terms of groups instead of data instances. Do you have any insight in this direction?\n3. In line 186--187 $\\beta$ should be in $R^{d_0}_G$ instead of $R^{d_0}$\n4. Corollary 5.1: We may need some conditions for gs used in $S_aug$, such as g is drawn uniformly randomly from G.", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This study tackles a critical problem --- analysis of the solution of equivariant neural networks. \n2. The paper is well-written and easy to follow.\n3. The theory is presented cleanly and solidly. I found a few typos, but The mostly I could read the theory part without confusion. ", "weaknesses": "1. The paper does not contain empirical evaluations. The authors admit that the analysis relies on the asymptotic approximation, which might have a gap toward a real solution. I feel the experiments make the paper significantly more convincing. \n2. The paper limits the analysis to linear cases, but nonlinear networks are practically essential. Extending the theory toward nonlinearity might not be trivial, but at least we can evaluate them through experiments. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment 1:** The paper does not contain empirical evaluations. The authors admit that the analysis relies on the asymptotic approximation, which might have a gap toward a real solution. I feel the experiments make the paper significantly more convincing.\n\n**Answer:**  We agree with the reviewer that empirical verification of the theory established in this paper could  substantively enhance the impact of our theoretical findings. However, a notable limitation of our findings is that the implicit bias of gradient flow, as studied here, holds true only in an asymptotic sense. The convergence rate to the directional limit is, in fact, exponentially slow. This is consistent with the findings in, Ref [1,2]. Specifically, Ref [2] shows that even if the loss function reaches an order of $10^{-5}$, the limit direction of the parameterized classifier (of a linear fully-connected network) is dependent on the initialization. This is because the networks are not trained all the way to zero loss. Understanding the behavior of gradient flow in a non-asymptotic regime is an important direction for future work.\n\nWe have mentioned this limitation in the conclusion of our paper, and we will emphasize this point further in the main text of our revised manuscript.\n\n[1] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822–2878, 2018.\n\n[2] C. Yun, S. Krishnan, and H. Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2021\n\n**Comment 2:** The paper limits the analysis to linear cases, but nonlinear networks are practically essential. Extending the theory toward nonlinearity might not be trivial, but at least we can evaluate them through experiments.\n\n**Answer:**  The investigation of implicit bias in linear networks typically functions as a foundational step in exploring the more intricate nature of implicit bias in deep nonlinear networks. Despite a wave of recent research efforts to elucidate the implicit bias in nonlinear structures, the field still presents many unresolved questions.\n\nThe extension of our current theory to encompass nonlinearity is indeed a vital direction but goes beyond the scope of our present study. Nonetheless, an intriguing theoretical insight that our paper's findings may offer is the possibility that equivariant nonlinear networks could attain a larger margin in the **parameter space** relative to their non-equivariant counterparts. This notion is hinted at in Theorem 6.1 of our work. Future research may further explore this promising direction, building on the groundwork laid in our current analysis.\n\n**Comment 3:** The implications of Theorem 4.1 and Corollary 5.1 are interesting. Theorem 4.1 says that the GD solution of a steerable net converges to the max margin solution trained on the group-averaged data $\\bar{\\mathbf{x}}$. In contrast, Corollary 5.1 shows an FC net trained on the group-augmented data converges to the steerable net, which suggests that group averaging in the data space and data augmentation have roughly the same effect. This is not trivial because group averaging takes all possible augmentations for each data instance, but data augmentation puts a single transformation. In the sense of loss function, the former is written as $loss(E_g[gx])$ while the latter is $E_g[loss(gx)]$. Can you explain why these two are possibly equivalent?\n\n**Answer:**  We thank the reviewer for posing this insightful question. You are absolutely correct in identifying the two distinct objective functions that correspond to training with data augmentation and training with averaged inputs. While it is true that these two objective functions lead to different training dynamics, our study essentially demonstrates that the directional limits of the parameterized classifiers, when trained under gradient flow, are identical. We do note that this holds true because of our assumption that the networks only have linear layers, and the group actions are also linear.\n\nThis insight reveals an interesting connection between these seemingly disparate approaches, and we will make sure to include this observation in the revised version of our paper.\n\n**Comment 4:** Related to the above question, I feel that group averaging is somehow similar to mixup, which augments data as $\\lambda x + (1-\\lambda)x'$. We may write group averaging as a special case of mixup, where we take an average in terms of groups instead of data instances. Do you have any insight in this direction?\n\n**Answer:** This is an interesting question. After the ``mixup\" augmentation, we might have a much larger training set (including pairs of $x$ and $x'$, as well as randomly sampled $\\lambda$.) Unfortunately, at this stage, we do not possess direct insight into the ramifications of this augmentation technique. It presents an intriguing avenue for exploration, but elucidating its full impact would require further investigation.\n\n**Comment 5:** Typo.\n\n**Answer:** thank you for spotting that. This will be fixed in the revision.\n\n**Comment 6:** Corollary 5.1: We may need some conditions for $g$s, such as $g$ is drawn uniformly randomly from $G$.\n\n**Answer:** In our paper, we specifically consider the ``full\" data augmentation approach that enlarges the dataset by a factor equal to the size of the group $|G|$. In this context, the element $g$ is not randomly drawn, but rather systematically used to encompass the entire group structure. This ensures a comprehensive and deterministic treatment, rather than a stochastic one. We will clarify this aspect further in our revision."}]

Author rebuttal:

Meta-review: The authors are studying the implicit bias of gradient flow on linear group-equivariant steerable networks for group-invariant binary classification. The results regarding the equivalence with data augmentation have been well-received. All the reviewers have found the work to be relevant and interesting, with meaningful theoretical results. The reviewers have highlighted several aspects for improving the paper's presentation. We suggest that the authors incorporate these suggestions into the final camera-ready version.
In conclusion, I recommend accepting this paper.
Decision: Accept (poster)