Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper investigates characterizations of solutions for the problem of training neural networks with exponential loss or logistic loss. The main contribution of the paper is to extend the previous work of  Lyu & Li (2019) for various types of networks. 
main_review: There are some concerns about the technical contributions of the paper. First, the implications of the technical result are not clear, in particular for generalization ability. In other words, how the characterization affect the generalization performance of the network? 

The second concern is that it is not clear how significant the generalization/improvement of the results is, compared to the result of Lyu & Li (2019) .  So far, it looks to me that the results are not as significant as the previous work. 
summary_of_the_review: The technical results seems non-trivial but the implications are not clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies implicit bias of linear and Relu networks (fully connected, diagonal, convolutional etc). Specifically, it investigates deeper a result by Lyu & Li (2019) who showed that gradient flow of such homogeneous next converges to a KKT point of the max margin problem in the parameter space. Owing to its non-convex nature, KKT conditions of this max margin problem do not guarantee local/global optimality. The paper answers whether these KKT conditions are (or not) local/global optima for a variety of linear and homogeneous Relu networks. 

The results are perhaps "negative" in the sense that Global optimality is found to be true only for Fully connected Linear (deep) nets, unless additional assumptions are made (Thm 3.1). An interesting positive result is that for linear deep nets not necessarily fully connected (e.g. diagonal/convolutional) the converging point of GF is a global optimum of a program that maximizes the margin of each layer independently. 
main_review: Strengths:
- Findings are interesting and concern an important topic
- Paper is generally well-written and rather easy to follow
- main findings are conveniently summarized on a Table

Weaknesses:
- The paper is missing a sound conclusion/discussion on the implications of their findings.

Given the interesting negative findings of the paper, I feel it is missing a punchline: what is the implication of these findings about existing works on implicit bias? What is the step ahead from the authors' viewpoint? Suppose that global optimality was true more generally, what are the implications of this? How could this be useful for further theoretical analysis? And in cases where is not true, what does this imply about works investigating implicit bias?

Related to above: in view of your Thm. 5.2, do you believe that is possible more generally to characterize the converging point as global optimum of some other problem with KKT conditions a superset of the KKT conditions of the max margin Problem 1? 

- In the abstract it is stated that: "On the flip side, we identify multiple setting where a local/global optimum can be guaranteed". This reads very promising compared to the sole positive results of Thm 3.1 and Thm 5.2 (Thm 4.2a requires rather stringent non-zero weight conditions)

Questions to the authors:
- The paper discusses binary classification. Have the authors considered what can be said about multiclass classification?
- Is program (3) equivalent to min_\theta \max_\ell ||u^{\ell}||_2  s.t. y_i\Phi(\theta;x_i)\geq 1 ? That is, does this imply that GF converges to the program that maximizes the worst margin among all layers?
- In Remark 4.1: (2) is a convex program, so every local optimum is a global optimum. "linear predictor \tilde\beta is not a local optimum of the following program" might be confusing
- Finally, can the authors comment explicitly on the role of bias?
summary_of_the_review: The paper has interesting findings on implicit bias theory. While the findings themselves are presented in a rather clear manner, the paper is lacking a sound conclusion especially so since it is "challenging" existing beliefs. I would encourage the authors to attempt clarifying their view on how these results are expected to affect further research on implicit bias.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the implicit bias of gradient flow in the lens of margin maximization. A previous work by Lyu & Li (2020) shows that gradient flow directionally converges to a KKT point of the margin maximization problem. The authors then focus on understanding what kind of local/global optimality of margin can be guaranteed by applying the KKT convergence result. The authors consider various settings on 2-layer/deep linear/ReLU neural nets, and for each setting they prove either local/global optimality of margin or an impossibility result.

As the positive results could be more preferable by the ML community, I summarize the positive results below:

* Global optimality for (deep) fully-connected linear nets;
* Global optimality for general two-layer linear nets with no weight sharing, assuming all the weights are non-zero;
* Local optimality for general two-layer ReLU nets with no weight sharing, assuming all neurons have non-zero inputs;
* Per-layer global optimality for general (deep) linear nets (i.e., every layer weights achieve the global max margin if all other layers are fixed.)
* Per-layer local optimality for general (deep) ReLU nets (i.e., every layer weights achieve a local max margin if all other layers are fixed.), assuming all neurons have non-zero inputs.

Here "general" nets can have arbitrary connections between neurons in adjacent layers.
main_review: #### Strengths

1. This paper presents lots of positive and negative results on the implicit bias of gradient flow, which certainly increases our knowledge of when gradient flow can or cannot converge to a local/global max-margin solution.
2. Among the positive results, the most interesting one is the per-layer local optimality for deep ReLU nets. Given the negative results in this paper, the per-layer local optimality seems to be the last hope for providing theoretical guarantees for margin in deep learning. Also this per-layer local optimality could have potential consequences besides margin.
3. The counterexamples for margin maximization are simple and intuitive.

#### Weaknesses

1. Although the authors made a lot of efforts analyzing the margin maximization across various different settings, this paper lacks a key result to highlight, and thus it may not be clear to readers what the main message is. Also this paper does not contain a conclusion section. The results for the linear nets reconstruct previous results with slight improvement, and the results for the ReLU nets are mostly negative. In my point of view, the result that interests me most is the per-layer local optimality for deep ReLU nets, and the main message could also be "proving the global optimality of margin is hopeless".
2. Although I like the simplicity of the counterexamples, I could not get a high-level insight and do not understand when the counterexamples may conceptually hold. Most of the counterexamples look like corner cases that could be excluded easily:
   * Theorem 3.2 considers a 2-neuron net. If the width is slightly wider, say 10, then we may get the max margin since there are more weight vectors with $\langle w, x_i \rangle > 0$.
   * Theorem 4.1, 4.4, 5.1 use symmetry: some parameters are initially the same and there is no symmetry breaking during training. So random initialization may mitigate this issue.
3. The relationship between this paper and Chizat & Bach (2020), Ji & Telgarsky (2020) needs more explanations. Specifically, these two previous works analyzed the neural net with infinite or exponential width. Ji & Telgarsky (2020) actually showed that the global optimality of margin can be attained if a covering condition holds: the directions of weight vectors in the first layer forms an $\epsilon$-covers of the unit sphere. This means any counterexample should describe a training trajectory that violates the covering condition somehow. I would like to see if the authors can give high-level insights into why the covering conditions are violated.
4. The counterexample on the non-homogeneous neural net does not seem to be very interesting. Note that the normalized margin itself is not well-defined for non-homogeneous neural nets, because dividing by norms does not make perfect sense anymore. Although Lyu & Li (2020) noticed that the monotonicity of normalized margin (defined by dividing the product of weight norms) for VGG with bias, to actually analyze this a better definition for the normalization margin is still needed. Thus it would be more interesting to have positive results with a well-defined normalized margin, or negative results against a broad class of normalized margin definitions.

#### Minor Comments

* The footnote 3 could be misleading. A possible misinterpretation could be: Ji & Telgarsky (2020) only proved margin maximization in the predictor space, but the current paper proves that in the parameter space with brand new techniques. This is not true because the proof by Ji & Telgarsky (2020) almost implies margin maximization in the parameter space, and this paper indeed used Proposition 4.4 from Ji & Telgarsky (2020).
* Although the proofs for Theorem 5.2 and 5.4 are simple enough now, I am wondering whether it can be further simplified by applying Corollary 4.5 from Lyu & Li (2020). More specifically, for any homogeneous neural net, we can write $\Phi(\theta; x_i)$ as $\langle \theta, \nabla \Phi(\theta; x_i) \rangle$. Then we change the weight of the i-th layer (which corresponds to a part of $\theta$) while fixing the others. For deep linear nets, we can see from the formula that $\Phi(\theta; x_i)$ is linear with the i-th layer weight; for deep ReLU nets, $\Phi(\theta; x_i)$ is locally linear with the layer weight. Lyu & Li (2020) showed the KKT convergence result for the original net. Fixing the weights of other layers implies the per-layer global optimality for linear nets. Since the KKT conditions are local conditions, the KKT conditions still hold if a ReLU net is linear everywhere wrt the i-th layer, which implies the per-layer global optimality for linear nets (as what this paper and Lyu & Li (2020) did). I believe this proof also shows how to generalize Theorem 5.2 and 5.4 to homogeneous nets besides ReLU and linear nets.
* Section 2, Optimization problem and gradient flow (GF): it should be clarified that subgradient flow in the sense of Clarke is used for ReLU nets.
summary_of_the_review: This paper studies an interesting topic and presents a lot of positive and negative results, which could be potentially used by other theoretical works later. But this paper lucks a key result to highlight. I appreciate the authors' efforts in analyzing the various settings in the paper, but I have to vote for weak rejection because of the lack of a key result and all the other weaknesses I mentioned above.

-----------------

I was mainly concerned that this paper lacks a key result to highlight, but after reading the rebuttal, I am now satisfied with the authors' response to this major concern. While my other concerns remain (and the authors did not respond to most of them), I am happy to increase my score to 6, assuming that the authors will add the short conclusion section as promised. I look forward to the next revision of the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is inspired by recent results which have shown that homogeneous networks, when trained on losses with exponential decay converge in direction to KKT points, i.e. points which are first order stationary w.r.t. the opimization of the margin of classification. Since this margin maximization is non-convex, KKT points may not be global maximizers of the margin or not even local maximizers. The authors therefore study a wide range of architecture of linear and ReLU networks, some shallow, some deep, with or without sparse and shared weights, and study in which case all KKT points are global margin maximizers, local margin maximizers or neither (for negative results, counterexamples are given).

Finally they study what happens for non-homogeneous networks, in particular in the presence of skip connection. While for homogeneous networks the margin increases during training, they give an example of a simple network with skip connection where the margin is strictly decreasing.
main_review: The topic of this paper is interesting, I think that these margin maximization questions are very important. But it suffers from being a collection of a large amount of small results. The paper goes over a large quantity of different settings, and it can be a bit overwhelming and difficult to follow.

Nevertheless the paper is a good and quite thorough overview of what happens in all these settings (though I would have been interested to study what happens for multiple outputs as this could make things more interesting in the fully-connected case for example). The counterexample are well described and quite simple, giving an idea of what structure leads to KKT points begin non-optimal. The authors mention that some of their counter example are stable under perturbation while some aren't, but don't really go in the details. I think that this is an important question. To make an analogy, the loss surface of shallow linear network has multiple saddles but the probability to converge to them is 0 since they are all strict saddles. I think it is quite likely that a similar phenomenon could happen here where some of the counterexamples presented in this article only happen with probability zero or a very small probability.

I found the non-homogeneous example interesting, though it is very simple.
summary_of_the_review: The paper studies an important question and is quite thorough. However it suffers from being a collection of many rather small results.
review_title: null

Meta-review: This paper studies margin maximization in linear and ReLu networks. The reviewers appreciate the technical contributions of this paper, especially the simple counterexamples. However, reviewers also found the new results seem not to give enough conceptual insights or an important "main result". The meta reviewer agrees and thus decides to reject this paper.
Decision: Reject