The ubiquity of 2-homogeneity, how its implicit bias selects features, and other stories

We thank the reviewer for their time and comments. We address the reviewer’s comments below.

Can you compare your result on two-layer networks to Theorem 3.3 in Telgarsky 2022?

The primary difference is that theorem 3.3 in Telgarsky 2022 requires the inner layer to be frozen while our theorem 1.1 does not. In particular, it is not clear how to adapt the potential argument used in theorem 3.3 in Telgarsky 2022 to handle rotation.

We thank the reviewer for their time and comments. We address the reviewer’s comments below.

1. We first provide parameter choices for theorem 3.1 Without a distributional margin assumption like the one stated in section 4, $R \leq \ln (m)$. Therefore, setting $t = O {( \frac{ \ln (n) }{ \gamma} )}^4$ for the first margin result and $t = O( \exp ( m^{(4 n / \gamma)}))$ suffices. For theorem 4.1, thanks to the margin distribution assumption and sampling tools used in the proof of theorem 4.1, one can establish $R \leq O ( d \ln (1 / \gamma) )$. Hence, $t = ( {(\frac { d \ln (1 / \gamma )}{ \gamma} )}^4)$ suffices. It should be noted that all the assumptions for theorem 3.1 are satisfied for shallow ReLU networks provided the distributional margin assumption in section 4 holds. The distributional margin assumption is rather mild as it holds as long as there exists a perfect classifier.

2. As we will elaborate shortly, the proof technique of Theorem 3.6 is distinct from the prior work of Lyu&Li, which grants a more general theorem that applies to various classes of inhomogeneous functions such as ResNet and transformer models. In particular, Lyu&Li analyzes the logarithm of the smoothed margin by decomposing into its radial and tangential components. It is not clear how to use the radial and tangential decomposition argument when there exists inhomogeneous parameters. To avoid using this decomposition, we deal directly with the smoothed margin which allows us to establish a more general theorem. Furthermore, part 1 of Theorem 1.1 establishes that GF obtains a large margin while Lyu&Li assume one starts with a positive initial margin. We have revised the section following theorem 3.6 to include the discussion comparing theorem 3.6 and lemma 5.2 in Lyu&Li.

3. Thank you for raising this comment. Part 1 and part 2 both characterize the implicit bias of gradient descent; specifically, gradient flow implicitly maximizes the margin of the model with respect to the variational norm or, equivalently, optimizing over the $F_1$ space. Part 1 establishes that after some training, gradient flow obtains large $F_1$ margin. Part 2 ensures that the $F_1$ margin of the model does not degrade over time and hence gradient flow continues to implicitly maximize the $F_1$ margin.

Additionally, the combination of Telgarsky and Lyu&Li is not enough to establish theorem 1.1. In particular, when trying to establish part 1, while theorem 3.3 in Telgarsky does achieve the $F_1$ margin, the work freezes the inner layer which vastly simplifies the training dynamics. On the other hand, while theorem 2.2 in Telgarsky does not freeze the inner layer, it achieves the worse NTK margin. In particular, for the 2 parity problem, the $F_1$ margin is $O( \frac{ 1 }{ \sqrt{d }})$ which the NTK margin is $O(\frac 1 d)$ which is a significant difference; in the context of margin based generalization bounds, if a model only achieves the NTK margin, to get the same generalization error of a model that achieves the $F_1$ margin, the former model requires $O(d)$ more samples.

Also it is unclear from text why 2-homogeneity is unique - from my perspective $k$-homogeneity may also be provable using similar arguments for $k>1$.

The power of 2-homogeneity is best demonstrated by lemma 3.2. Given a more general $k$ homogeneous model of the form $h(x ; w = (a^1,\dots a^L ,V)) = \langle a^1 \odot \dots \odot a^L, F(x; V) \rangle$ and
defining the reparameterized weights as $u_j(t) := \prod_{\ell = 1}^k a^{\ell}_j(t)$, one can, by calculation, determine that the reparameterized mirror flow (eq 3) fails to hold for $k \neq 2$. As discussed in the section following lemma 3.2, the reparameterized mirror flow explicitly optimizes over the superior $F_1$ space as opposed to $F_2$ space. This is extremely important as $F_2$ margin can be significantly worse than the $F_1$ margin. In particular, as mentioned in example 4.1, for the k- parity problem $F_1$ margin is $\frac { 1 }{ k \sqrt{d }}$ while the $F_2$ is $\frac { 1 }{ d^{ k /2} }$; the significance of this difference becomes apparent again when looking at margin based generalization bounds as models that achieve $F_2$ margin will require exponentially more samples in $d$ to achieve the same generalization error as a model that achieves $F_1$ margin. To provide additional clarity, we have incorporated the preceding discussion in the section following lemma 3.2 in order to highlight the importance of 2-homogeneity.

Furthermore, the title of the paper should be changed in the pdf file.

Thank you for pointing this out. We have updated the title.

If the reviewer is not satisfied with this response, can they please clarify their further concerns?

We thank the reviewer for their time and comments. We address the reviewer’s question below.

We would like to emphasize part 2 of Theorem 1.1 (specifically the claim regarding nondecreasing smooth margins) hold for architectures beyond shallow normalized ReLU networks such as ResNet and transformer models. For ResNet, it is also true that the loss will converge to 0 and the norm of the homogeneous parameters, namely the final linear layer and the affine layer from the last Batch Norm layer, converge to infinity as the hidden output of ResNet right before the 2-homogeneous head is bounded thanks to Batch Norm.

Thank you for the valuable comments and insightful questions. We address your questions below.

1. Unfortunately, it does not seem possible for the reasons stated below. Firstly, it should be noted that both Gunasekar et al. and Lyu&Li are truly asymptotic results and it is not clear how to get finite time guarantees using a combination of Gunasekar et al. and Lyu&Li. In addition, both Gunasekar et al. and Lyu&Li operate in the late regime where perfect classification has been achieved and the model has small positive margin. In fact the first half of the proof of theorem 3.1 is dedicated to proving that one achieves a small positive margin. Furthermore, the convergence to the max margin predictor in Gunasekar et al. further assumes both the iterates produced by gradient descent and the loss gradients converge in direction, a fact that is highly non-trivial to prove.

2. Yes, that characterization is correct. However, we would like to emphasize that for shallow ReLU networks, we prove both the “slow-growing derivatives” property and the existence of “initial good features” under the distributional margin assumption in section 4.

3. While related, the strength of the assumptions are somewhat incomparable. Indeed, in the setting where perfect classification is impossible (e.g. data distributions where inputs have nonzero probability of being labeled both positive and negative), one can still have “high alignment” but the “initial good features” assumption is violated as the margin cannot be positive, hence not separable. However, on the flip side, the initial “good features” assumption can still hold but the “initial alignment” can be very small. This does not contradict the hardness results in Abbe et al. as getting a large margin (which is roughly equivalent to learning the target function) can take exponential time (in fact in the worst case it can be doubly exponential).

I found some of the initial discussion a little misleading in that e.g. the discussion around line 140 > made me think that the analysis would apply to arbitrary homogeneous subsets of parameters . While this is true for the margin definition given there, almost all of the paper applies only to the doubled-linear-layer structure of equation (2). This is fine

We apologize for the confusing discussion. The margin definition was described in full generality as the second part of theorem 1.1 handles arbitrary homogeneous subsets of parameters. We have revised the discussion following theorem 1.1, clarifying that part 1 of theorem 1.1 only applies to architectures with a double-linear-layer head.

I just found that bit of discussion confusing, particularly since taking e.g. only the last layer would also yield a 1-homogeneous structure, and I found myself wondering if it would really be true that it would increase the margin defined in terms of each possible homogeneous part of the network. (To be clear, I don't think any statements in the paper are wrong, I just found this brief discussion confusing.)

Surprisingly, the smoothed margin defined in terms of any homogeneous subset $\hat w$ is nondecreasing as asserted in theorem 3.6. In fact, this claim does not need any bounded assumptions of $h$ and its gradients with respect to the ignored parameters. This is crucial as any homogeneous parameters (of nonzero degree) in the ignored subset $w \ \hat{ w }$ violate the boundedness assumptions. However, as discussed in the section containing the margin definition, the notion of margin (and smoothed margin) only makes sense when the margin does not grow arbitrarily with the norm of the ignored parameters $w \ \hat w$.

If the reviewer is not satisfied with this response, can they please clarify their further concerns?