Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks

Thank you very much for the critical review of our work and your help in improving it!

First, before responding to your questions, please allow us to correct a small mistake in your evaluation of our work, in order to avoid confusions:

The limit points of the parameter directions are general KKT points of the margin maximization optimization problem under some assumption of the norm

Assumming that by "some assumption of the norm" you mean the algorithm norm squared being smooth, then: Theorem 3.8, which is the main result of this paper, asserts that steepest flow converges in direction to a generalized KKT point without any assumption on the algorithm norm. Corollary 3.8.1, on the other hand, strengthens this result in the case of a norm that satisfies the aforementioned property, stating that we get convergence to a (standard) KKT point, not a generalized one.

Can the authors extend the existing results on steepest flow to steepest descent? If not, it would be more accurate to clarify that the current theoretical results apply solely to steepest flow.

Indeed, our paper focuses on steepest descent with infinitesimal learning rate, i.e., steepest flow (Eq. 3). We specify this at the start of our introduction (line 051). We leave the generalization of our results to the case of steepest descent (with a non infinitesimal learning rate) as an open challenge. Notice that the possibility of a non-smooth norm substantially complicates a discrete time analysis - for instance, Theorem E.2 and Lemmata E.7, E.8, E.9 in [Lyu & Li, 2020] only hold in the case of an $\ell_2$ geometry. Furthermore, the proof will have to operate under more restrictive assumptions on the smoothness of the network, which, arguably, minimizes the practical relevance of such a result. We recognize this as a limitation of our analysis and added a short note on this in our conclusion (Section 5, line 478).

Is it feasible to demonstrate KKT point convergence for the general loss function?

We believe that this should be possible to prove for any exponentially-tailed loss. In particular, in Appendix A.3, we demonstrate how Theorem 3.1 generalizes to other loss functions, and we note that a more technical definition than Definition A.21 could allow the extension of our full proof to other loss functions, similar to the approach taken in [Lyu & Li, 2020]. As a matter of fact, in the Experiments section (Section 4), we consider training with both the exponential and logistic loss with various steepest descent algorithms, and the margin observations are consistent with our theory. Finally, let us remark that it is a common practice in the literature to focus solely on the exponential loss (see, for instance, [1, 2, 3]) as it is known to capture the essence of these results.

1. Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy. Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D. Lee, Nathan Srebro, Daniel Soudry.
2. Implicit Bias of Gradient Descent on Linear Convolutional Networks. Suriya Gunasekar, Jason Lee, Daniel Soudry, Nathan Srebro.
3. Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models. Mor Shpigel Nacson, Suriya Gunasekar, Jason D. Lee, Nathan Srebro, Daniel Soudry.

In Lyu & Li (2020), tight convergence rates for both the loss function and parameter norms were established. Are there any mathematical challenges in achieving similar results here?

No, we believe there are no mathemetical challenges in achieving similar complementary results. Essentially, Lemma A.6 in our paper characterizes the rate of convergence for the loss and the paramater norm (particularly for the relevant algorithm norm). We opted not to risk presenting such a complimentary result during the rebuttal period (after the first round of all the reviews), since it is not exactly straightforward, but we believe that an interested reader can deduce these rates using our Lemma A.6 and equations 30 and 31.

Additionally, they showed that the soft margin approximates the normalized margin. Could you provide a similar analysis in this context?

If we understand your question correctly, then, yes, this is (essentially) proved in Lemmata A.6 and A.7. We fixed a minor typo there (line 822) and added the conclusion as a corollary (Corollary A.7.1). Furthermore, we added a relevant pointer for this in the main text (lines 178-179). Thank you very much for the suggestion!

Thank you for reading our paper and helping us improve it!

We reply to your questions:

I do not understand Figure 1-right. What does it imply? How does this relate to the theory?

Thank you for the question! In Figure 1 (right), we compare 3 different steepest descent algorithms: gradient descent, sign gradient descent and coordinate descent. We measure the $\ell_\infty$ margin of the training dataset at the end of training (Eq. 14) and plot it against the test accuracy of the networks (each point -- circle, square, triangle -- corresponds to a different seed). The first observation, which connects to Theorem 3.1, is that coordinate descent has a larger $\ell_\infty$ margin than the rest of the algorithms -- see lines 409-412. This is expected since it is the only algorithm out of the 3 which is guaranteed to increase this margin during training. The second observation is about the connection between margin and generalization for this task and is less related to our theory. In short, we comment on the fact that these seems to be no strong, causal link between larger margin and generalization in this setting - see lines 412-425.

The theory only applies to the "exponential loss," which does not make much sense to me.

This is a valid concern, but our choice of this loss follows a long list of precedence and justification in the literature. Indeed, the reason why many papers are concerned with the exponential or exponentially-tailed losses is that: (a) they are close to the most common choice of the cross-entropy loss, or its binary version, the logistic loss, and (b) they allow for a clean relationship between the geometric margin and the loss via the softmax. Also, let us mention that this has been a standard practice in the literature, with numerous papers (e.g. [1, 2, 3]) that only study training under the exponential loss. In defense of the contributions of our paper, let us note that our work considers the generalization to other losses in Section A.3 (where Theorem 3.1 is generalized).

How close is the steepest descent to actual GD? Does the theory hold for GD?

A steepest descent algorithm is defined with respect to a norm. When this norm is the $\ell_2$, we obtain gradient descent. Otherwise, we obtain a different algorithm. The theory holds for gradient descent with infinitesimal learnging rate, but this is not the most interesting case since the result of [Lyu & Li, 2019] already covers this case.

We hope we were able to answer your questions convicingly. Please let us know if there are any other concerns or if you require further explanations.

In general, given your comment:

Lastly, I feel I should comment that I do not have the related background knowledge to assess the technical advancement made by this work

We would be happy to help you assess the technical advancements of this paper by explaining things further if you feel this is appropriate, in order to provide a basis that would allow you to raise your score and recommend acceptance. Thank you for your time and your help!

1. Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy. Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D. Lee, Nathan Srebro, Daniel Soudry.
2. Implicit Bias of Gradient Descent on Linear Convolutional Networks. Suriya Gunasekar, Jason Lee, Daniel Soudry, Nathan Srebro.
3. Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models. Mor Shpigel Nacson, Suriya Gunasekar, Jason D. Lee, Nathan Srebro, Daniel Soudry.

We appreciate the time you took to review our paper and are grateful you found our results novel! We reply to your only question regarding the technical contributions of the paper:

The set of results and proofs seem to be a straightforward generalization of [Lyu and Li, 2019]. The technical contribution is not strong.

While this is of course a relative matter, please let us elaborate on two technical points where our work departs significantly from [Lyu & Li, 2019]:

• Non-smoothness of the algorithm norm: the fact that the squared norm of the algorithm is not necessarily continuously differentiable (as it is in the case of gradient descent) complicates the analysis in many parts - see, for example, Proposition A.3 and the rest of the analysis where specific care must be taken to handle updates aligned with the least norm subgradient $\mathbf{g}_t^\star$.
• Quantifying proximity to stationarity: Gradient descent approaches the KKT points of the $\ell_2$ max margin problem by reducing a Euclidean distance measuring stationarity. Prior to our work, it was arguably unclear how a different steepest descent method might have progressed to approach stationarity of the corresponding implicit max margin problem. We introduced a novel measure of stationarity, based on an algorithm-specific (pseudo) Bregman divergence, and we show that this succeeds in quantifying the progress of the algorithms. This also naturally motivates a new progress measure for approximate stationarity (Section B), which could be of independent interest. Notice that here as well the non-smoothness of the norm causes technical challenges, and their handling required some fairly involved machinery from Convex Analysis (Proposition A.13 & Theorem 5.24 in [Beck, 2017]).

In general, the proof of [Lyu & Li, 2019] is heavily based on the $\ell_2$ geometry of gradient descent (naturally so!) and many parts have to be modified in order to obtain a clean result for any steepest flow. Testament to this are the many novel tools (generalized KKT points -- Definition 3.4, approximate generalized KKT points -- Definition A.9, generalized Bregman divergences -- Definition 3.6) and corresponding results (e.g. Proposition A.20) which we had to introduce in order to obtain our implicit bias characterization.

We would be happy if our explanations could make you reconsider the technical contribution of this work, and perhaps, make you raise your score. Please let us know if you have any specific questions. Thank you!

We are really grateful for your careful and critical review and we are encouraged you found our paper well-written, easy to follow, and its contributions "surprising". In particular, we are glad that your thorough reading recognized that the [Lyu & Li, 2019] proof relies heavily on the $\ell_2$ geometry (which, of course, is natural to some extent), and our analysis is not straightforward.

We respond to your questions:

Minor issue: there are large blanks on some pages in the appendix.

Thank you. This is fixed now.

This paper only proves the convergence to generalized KKT solutions for sign gradient flow, which is an important case of steepest descent. I wonder if the authors have any thoughts on whether failing to prove KKT in this case is an artifact due to the proof techniques or if some tricky hard cases actually exist.

We have indeed spent quite some time pondering this question. In short, it is unclear whether convergence to KKT points can be proven in general. We share some thoughts on this topic:

For sign gradient descent ($\|\cdot\| = \|\cdot\|_\infty$), the Bregman (pseudo) divergence is defined with respect to the $\ell_1$ norm squared. Since the $\ell_1$ norm squared is not strictly convex, the divergence between two vectors approaching 0 (as shown in Proposition A.15 and Theorem A.18), does not imply that the two vectors converge to the same point. A fairly standard technique in convex analysis might suggest to consider a different divergence: the Bregman divergence induced by the (normalized) negative entropy, which is strongly convex with respect to the $\ell_1$ norm. As a result, the obtained divergence, which is a normalized version of the KL divergence, becomes a proper divergence. Unfortunately, two issues arise with this approach: (a) the KL divergence requires non-negative values, which remains problematic even after employing the common trick of doubling the dimension, and (b) if we have a sequence of KL-approximate KKT points, it is not clear whether this implies convergence to a KKT point (that is, it is unclear whether Proposition A.20 holds for d=KL). Had this approach been successful, we could apply a dual rationale for coordinate descent, using the divergence induced by the log-sum-exp function.

One potential experimental approach to determine whether our result is an artifact of our proof technique or not would involve leveraging Corollary A.19.1 and, in particular, eq. 60. There, we show that the rate of convergence to stationarity (for smooth squared norms) depends on the smoothness parameter of the norm. Thus, an experiment could involve training a homogeneous neural network using various steepest descent algorithms (e.g., $\ell_p$ norms with $p = {2, 3, 4}$) and observing whether this theoretical lower bound manifests. Specifically, it would be interesting to see if, once the training data are fit, convergence to stationarity takes longer for algorithms with less smooth norms. However, this may be challenging since measuring some of these quantities in practice could be difficult due to subgradients.

In total, while we remain uncertain about the $\ell_1$ and $\ell_\infty$ cases, we believe that if convergence to a KKT point is true for any norm, a proof similar to ours would have been applicable. Although we do not currently have a definitive answer, we hope you find these insights interesting.

Finally, we would kindly suggest taking a look at our global response and the revised version of the paper. In particular, we think you might find Section C.2 interesting, where we added some discussion on the relevance of our results to a newly introduced adaptive method. Thank you once again!

The sentence before Theorem 3.1. The proof is quite similar to that in Lyu&Li. It seems to me that this paper used Cauchy-shwartz but Lyu&Li explicitly used the Pythagorean theorem (which only holds in inner prod space but not general normed space). If I am correct, then there is not much difference.

Yes, this is "conceptually" correct (Theorem 3.1 does not use the CS inequality, but rather the definition of the dual norm, while Lemma 5.1 in [Lyu & Li, 2019] does use a polar decomposition and the Pythagorean theorem). This is why we mentioned that Theorem 3.1 "is similar to part of Lemma 5.1 in [Lyu & Li, 2019]" in line 181.

I think it would be better to discuss briefly the relation between D-generalized KKT and ordinary KKT between Theorem 3.8 and Cor 3.8.1. and why not to prove something like Cor 3.8.1. directly.

Thank you for this suggestion! We added a short discussion in lines 315-317.

Please also consider taking a look at the general response to all reviewers. In particular, in addition to the improvements in presentation, the updated manuscript contains a small section on the connection between a newly introduced adaptive optimization algorithm (Shampoo) and our framework. We are grateful for your useful questions and suggestions, which helped us improve our paper. Please let us know if any of our answers is unclear or if you have further questions. If not, we kindly ask you to consider raising your score, which would help achieve a consensus among reviewers. Thank you!

Thank you very much for taking the time to review our paper and for helping us improve it! We reply to your comments:

Gunasckar et al. 18 already studied the implicit bias of several class of optimization algorithms. However, the citation here is very superficial and it is unclear to me how the results in this paper supercede (or compared with) their results.

Gunasekar et al. (2018) studied the implicit bias of all steepest descent algorithms in linear models under the exponential loss. Our paper, in contrast, analyzes steepest descent in homogeneous, potentially non-linear, neural networks. So, our setting is more general than Gunasekar's et al. (2018). The strongest results we obtain in this paper characterize the limiting points of the trajectory as KKT points of the margin maximization problem (in the case of a smooth squared norm), whereas Gunasekar et al. (2018) prove that in linear models, we obtain global maximizers of the equivalent margin maximization problem. The gap between the two results is, however, unavoidable, as it is known that even for gradient descent, homogeneous networks can converge to points which are KKT points, but not necessarily (even) locally optimal with respect to the margin [Vardi et al. (2022)]. We view our results as conceptually consistent with those of Gunasekar et al. (2018), and we have added one sentence elaborating on this in line 087.

It is also unclear to me how the results by Wang et al. on Adam is related to the results of this paper. If we simplify Adam to signGD, it seems that the results in Wang et al. is inconsistent with this paper?

Let us try clarify the confusion. Wang et al. (2021, 2022) analyzes the version of Adam where a precision paramater $\epsilon$ is added in the denominator to avoid numerical instability (see eq. 71 in our paper). In order to obtain signGD, we need to set $\epsilon$ to 0, so the results of Wang et al. (2021, 2022) do not apply. This issue was recently observed by Zhang et al. (2024), who analyze Adam without the precision parameter ($\epsilon=0$), but with momentum, specifically in linear models. As we mention in line 101, they "found bias towards l1 margin maximization - the same as in the case of sign gradient descent". Thus, our results are consistent with [Zhang et al. (2024)]. We elaborate on this topic further in Section 4.2, where we test these results empirically. As a reminder, in Section 4.2, we observe experimentally that models trained with Adam initially exhibit an $\ell_1$ bias, which later changes to an $\ell_2$ bias. We have updated the text in that section, corrected two minor typos that may have caused confusion, and revised Section C.1 in the Appendix, which discusses Adam in more detail.

The authors briefly discuss some prior work [...] I think more detailed discussion is necessary.

Thank you for the suggestion. We have included additional discussion and references in that section.

Moreover, the following papers also obtain implicit bias results towards L_p margin with p different from 2 (for special models). Is there any concrete relation between these results and the results in this paper. Kernel and Rich Regimes in Overparametrized Models (already cited but not discussed in details) Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy

Thank you for the question. These papers study gradient descent in a simple class of homogeneous networks (referred to as diagonal neural networks), defined as $f(\mathbf{x}; \mathbf{u})$= $\langle$ $\mathbf{u}$+^D - $\mathbf{u}$-^D,$\mathbf{x} \rangle$, $D > 0$. The constant $D$ represents the depth of the network. The focus of these papers is on how the initialization scale and depth $D$ affect the implicit bias of optimization, along with a precise characterization of the transition from the kernel to the rich regime during training. In their setting, it is known that gradient descent has a bias towards minimum $\ell_2$ norm of the parameters [Lyu & Li, 2019], but these papers explore how this bias translates into the predictor (i.e. function) space (see Section 2 of [Woodworth et al, 2020. Kernel and Rich Regimes in Overparametrized Models]). In this predictor space, they prove an implicit bias towards norm minimization for a norm different than the Euclidean one. In contrast, our results focus solely on the parameter space of homogeneous networks trained with steepest descent. We view these works as peripheral to ours, which is why we opted not to discuss them in detail (as doing so would require defining implicit bias in both parameter and predictor spaces, which, in our view, would detract from the focus of the paper).

Thanks for the response. The response and the revision have improved the quality of the paper slightly. I am leaning towards accepting the paper and my current rating is somewhere around 6.5. While I might consider rounding it up to a 7 if that were an option, it may not reach the caliber of an 8 in my opinion (compared to other ICLR rating-8 papers I’ve reviewed and read, in terms of conceptual and technical novelty). Therefore, I will maintain my current rating.