Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Because of the explicit inductive bias of G-CNN, other inductive biases have not been discussed much.
In this paper, the author focuses on and analyzes the non-explicit inductive bias of G-CNNs.
Technically, they present the non-explicit bias in terms of Fourier matrices by using a group Fourier transform, which depends on the group structure.
The results show that learning a linear G-CNN (with linearized β) by gradient descent implicitly biases the singular values of the Fourier matrix coefficients of β to be sparse.
This result has been experimentally confirmed in linear and some nonlinear situations.
main_review: Strength: Focusing on the non-explicit bias of G-CNN, the results of the analysis are satisfactory.

Weaknesses: I do not see anything special about it.

Questions:
From a theoretical point of view, we would like this kind of result to include the case where the group does not do group convolution as a case where the group is trivial. What does Theorem 1 imply when the group is trivial?\

It would be great if this kind of result could provide some insight in analyzing over parametrized FNN. When we regress the G-equivariant function on an over parametrized FNN, can your results give any insight?\

This result was for finite groups, but there are also convolutions for geometric groups, such as Lie conv. Please tell us about the part of this result where the finite group assumption works and give us some insight into the generalization to Lie groups.

After the revision, the paper was improved, for example by generalization to the Lie group, but in the main the assessment did not change significantly, resulting in the following scores


summary_of_the_review: Basically, this paper is theoretically well done. The assumption of linearity is a strong one that is far from reality, but it is a reasonable assumption for the current theoretical analysis, and it is confirmed by experiments in the nonlinear case. Overall, I think this is a worthwhile paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the induced bias of gradient descent on L-layer linear group-equivariant convolutional neural networks. Their main result is: gradient descent implicitly controls the 2/L-Schatten norm of the Fourier transform of the (linear) predictor. More precisely, they show that gradient descent trained on a L-layer group-equivariant CNN with exponential loss on a linearly separable dataset converges in direction to a first-order stationary point of an optimization problem minimizing the 2/L Schatten norm of the Fourier transform of the linear predictor subject to the margin being at least 1. 

main_review: From a technical perspective, the results for abelian groups (as the authors note) follow from appropriately applying the result of Yun et al. (2020). (This is because convolutions in Fourier space can be expressed as pointwise multiplication for abelian groups.) The more interesting technical contribution is for non-abelian groups. In this case, convolutions corresponds to matrix multiplications of matrices which need-not be diagonal, and thus do not correspond to point wise multiplication. For this case, the authors directly analyze the stationary points of the optimization problem. 

An appealing aspect of the paper is to highlight that the norm that is implicitly controlled by gradient descent on group equivariant networks takes a simple form, even for general (finite) groups. This technical point is made clearly in the paper, and the paper is generally well-written.  

One weakness of the paper is that the it does not explicitly connect the theoretical results with practical settings. First, since group-equivariant convolutional neural networks are not a standard architecture, it could be helpful if the authors added a discussion of what group structures have been used / are meaningful in practice, and provided insight (e.g. in the empirical section) into the implicit regularization of gradient descent in these special cases. 

Furthermore, the empirical results are quite limited. Based on Appendix D, the networks appear to be run on very small synthetic datasets (with 6-10 datapoints). For this reason, it is difficult to determine if the takeaways hold for more realistic classification tasks. It would be helpful if the authors ran experiments on standard binary classification datasets (e.g. MNIST or CIFAR). 

Lastly, another weakness of this paper is that the results are restricted to single-channel linear networks with full-dimensional kernels. In light of previous work (i.e. Yun et al. (2020, Gunasekar et al. (2018)), the results are somewhat incremental. The paper mainly demonstrates that the 2/L-norm in Gunasekar et al. (2018) for L-layer linear CNNs can be replaced by the (2/L)-Schatten norm. While this norm (especially for non-abelian groups) does give rise to different sparsity structures, the analysis and the conceptual takeaways are somewhat similar those in Gunasekar et al. (2018). 

summary_of_the_review: I recommend weak rejection due to the incremental nature of the technical results in light of previous work, as well as the limitations of the empirical section. 

---- 
Update after author response: I appreciate the additional experiments on the MNIST dataset, and believe that this improves the empirical analysis provided in this paper. However, given the results in previous work (e.g. Gunasekar et al. '18, etc) for the trivial group, I still think that the results in this work are fairly restrictive since they only hold for single-channel linear networks with full-dimensional filters. Although previous work has shown that simple closed-form solutions may not exist in general, it would still be useful to provide insight into how these important parameters affect the implicit bias of gradient descent.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper describes a theoretical analysis of the implicit bias in G-CNNs. The results show that for linear G-CNNs trained on linearly separable data using GD converge to sparse solutions in the Fourier domain (equivalently dense solutions in the real domain). The theory is theoretically confirmed and shows that the implicit bias also occurs to some extend for non-linear G-CNNs.
main_review: Strengths:
As far as I can assess, the paper is technically sound, novel and timely.
The paper is formal and precise.
The appendix is quite nice actually and is rather complete in mathematical background.
The paper is reproducible and has code provided.

Weaknesses:
My main criticism is that the paper is very theoretical and feels a bit like a nice math exercise to prove something, however, without being clear why the problem is addressed in the first place (apart from the fact that no one did it yet). To me, as someone working with G-CNNs and having a good understanding of (irreducible) representation theory, but not in analysis, it is unclear what I should take home from the paper. 
I.e., why should we expect different results for non-Abelian compared to Abelian groups in the first place? 
How should I interpret the bias towards dense solutions as a regularization effect? 
What are the implications?

Comments:
It would be helpful to have explicit statements about the main contributions/novelty of the paper.

The experiments in the figure make sense to me in the comparison G-CNN vs FC. Both map G-feature maps to scalars and the latter shows that the bias takes place due to architecture and not the data. However, I do not understand the comparison CNN to G-CNN. If the feature maps are functions on G, is a CNN not automatically a G-CNN? Then, what is the difference between the two? 

Some essential details are missing regarding the data. I cannot find it in the appendix either. The closest I get to a description is in caption of Figure 3: “trained … with six isotropic Gaussian data points”. What is an isotropic Gaussian data point? 

In theorem 5.3 third line: is this a typo? (w.r.t. indexing to l should be l+1?, it says something like Fw_l-Fw_l \geq \lambda)

summary_of_the_review: Although I am comfortable with group theory and basic harmonic analysis on groups through irreps, I find it hard to follow the derivations and make sense out of the statements. My impression is that the paper is too mathematical for ICLR audience, though I can really only speak for myself. The paper could improve a lot from more layman's explanations throughout the paper. For example, it already starts early in the paper with talk about Schatten norms, where to me it is not immediately obvious why these are considered.

I understand that it is hard to please every reader, but I believe it is possible to convey the main messages better to a broader audience. Currently it seems overly tuned towards experts in analysis (of implicit biases).

Overall, I do see value in publishing such work as the paper seems otherwise sound.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Group Equivariant CNNs (G-CNNs) generalize CNNs from the translation group to arbitrary groups. It has been shown that overparameterized/undetermined linear transformations and linear CNNs learned by gradient descent are implicitly biased, in that they find zero train loss solutions that minimize some norm on the predictor. This paper generalizes these results from linear CNNs to linear G-CNNs. The linear G-CNNs are constructed into a non-equivariant linear transformation, by doing L G-CNN layers, followed by a non-equivariant inner product with a G-feature. The authors show that the implicit bias is to minimize the p-norm of the singular values (the Schatten norm) of the Fourier transform of the resulting linear transformation.
In the case where G is Abelian, by a tensor factorization of the linear G-CNN, the authors can straightforwardly apply a result from prior work on the implicit bias of such tensor factorizations to prove their result.
In the case where G is not Abelian, the authors prove their results in three steps. (1) They use prior work on gradient descent on linear predictors that are polynomials of the parameters, which their linear G-CNN falls under, to show that the stationary points minimize norm the joint norm on all weights. (2) They define a linear regression optimization that minimizes the Schatten norm of the linear predictor. (3) They show that all optima of the polynomial linear predictor are also optima of the Schatten-normed linear regression. To do so, they find the subdifferential of the p-Schatten norm and show that the polynomial optimum is in the subdifferential.

The authors confirm their theory in toy experiments in the linear case and show that in the non-linear case, where the Schatten norm is computed by local linearization, that similar results may hold in the non-linear case.
main_review: The authors show for the models under consideration an interesting and novel result: the models are implicitly biased not by the real space norm of the linear predictor, but by the Schatten norm of the Fourier transform of the predictor. For the Abelian case, this required an incremental generalization of prior work, but for the non-Abelian case required an interesting proof method. The paper is very clearly written and was a pleasure to read.

My main problem with this work is that it considers a model class that I’ve never seen used (besides the lack of non-linearities): it uses group equivariant CNNs and then takes an inner product with a G-feature weight, resulting in a non-equivariant linear predictor. If the authors used invariant outputs, the linear invariant predictors would just be averaging, and the analysis wouldn’t work. As G-CNNs are chosen for their symmetry properties, studying them in a non-equivariant context makes little sense to me. Whether the implicit bias found in this paper generalizes to equivariant non-linear G-CNN networks has not been convincingly shown.

For me to recommend acceptance of this paper, the authors should make a more convincing point why the results for this non-equivariant model class are applicable to equivariant G-CNN networks people actually use (besides the fact that the analysis applies to linear networks).

Other weaknesses:
* The non-Abelian case states two assumptions (gradients converge in direction, iterates converge in direction to a classifier with positive margin), but these are not clearly defined, nor is it stated when these are satisfied. The paper would be improved if there would be some discussion of these assumptions.
* The key point of the paper seems to be that Fourier Schatten norm, not spatial norm is the implicit bias of the learned networks. The paper would be stronger if it would give some more intuition about this point. Perhaps visualize some of the learned weights in both Fourier and spatial domain?
summary_of_the_review: While the authors use novel methods to derive an interesting implicit bias of the model class under consideration, this class, non-equivariant predictor based on equivariant neural network layers, is not what is generally used in practice. For the paper to be recommendable for acceptance, the authors should make a stronger argument why their results also apply to models actually used. If they do so convincingly, I'd increase my score.



Updated score to 6.
review_title: null

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

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

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

So I took a closer look.

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

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

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

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

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

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

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