Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks

Thank you for your feedback. For the technical novelty, please refer to the section Technical novelty in our response to the reviewer R5kD. For insights of our results, please refer to the section Insights of our results in our response to the reviewer NQfK. Below, we address your other questions.

---

Q1. “One big issue, but I think it can be fixed easily: In the definition of (M,N)-nearly-homogeneous functions, M,N are assumed to be positive, but Example 4.1.C has M=0?”

A1. Thank you for pointing this out. This issue can be solved by relaxing our near-(M,N)-homogeneity definition to allow $M=0$. Specifically, we call a block s(θ; x) near-(0, N)-homogeneous, if it is independent of θ and near-N-homogeneous in $x$. We will clarify this in the revision.

---

Q2. “Some of the ‘theorems,’ such as 5.1, 5.2, and 5.3, should be downgraded to a lemma or proposition. … The definitions and assumptions are a bit scattered, so an index of notations/definitions would be a good addition to the appendix.”

A2. We will revise the paper according to your suggestions. Thank you.

---

Q3. “I would like to see M-nearly-homogeneous and (M, N)-nearly-homogeneous be unified into one definition.”

A3. While these two definitions can be unified, we prefer to keep them separate for the sake of clarity. Since our main results in Sections 3, 5, and 6 only make use of near-M-homogeneity, unifying these two definitions would make these results harder to unpack for the readers.

---

Q4. “I do not quite get how the discussion on o-minimal structure connects with the rest of the paper. The author should elaborate on this.”

A4. We will add a paragraph to clarify the role of o-minimal structures. Specifically, the o-minimal structure enables the chain rule of Clarke’s subdifferentials (see Lemma A.6), the existence of a desingularizing function (see Lemma C.14), and Kurdyka–Łojasiewicz inequalities (see Lemmas C.19 and C.20). These are crucial tools in our analysis.

---

Q5. “As I previously discussed, the technical work of this paper is very profound, but the high-level strategy is already present in the literature. So, I don't think this work offers new insights on the understanding of implicit bias.”

A5. We respectfully disagree with these comments. For the technical novelty, please refer to the section Technical novelty in our response to the reviewer R5kD. For insights of our results, please refer to the section Insights of our results in our response to the reviewer NQfK.

---

Q6. “I believe that author should also mention this work … ‘Gradient descent finds global minima of deep neural networks.’....”

A6. We will consider discussing this work in the revision. Based on our understanding, the paper you mentioned mainly uses neural tangent kernel (NTK) style techniques to study global convergence. This seems to be quite different from our focus: characterizing the asymptotic implicit bias of GD/GF in near-homogeneous models assuming a strong separability condition. We appreciate it if the reviewer could further elaborate on the connections between this work and ours.

---

Thank you for supporting our paper! We address your questions first and then discuss our technical novelty at the end of this response.

---

Q1. “...my question is whether the formulation of exponential loss is necessary. Can the results still be valid for multi-classification with cross-entropy loss?...”

A1. Our results can be extended to other loss functions with an exponential tail such as logistic loss. This is because our analysis focuses on the late training regime assuming that the predictor already classifies all data very well. In this regime, only the tail property of the loss function matters. Additionally, using arguments in [Lyu & Li 2020, Appendix G], there is no mathematical difficulty extending our results to multi-class settings using cross entropy loss. We will explain these in detail in the revision.

---

---

Technical novelty

We make significant technical innovations in our analysis. Below, we discuss them in our GF and GD analysis, respectively.

A. Technical novelty in GF analysis

In our gradient flow analysis, we make the following innovations rather than simply combining our near-homogeneity conditions and techniques from [Lyu and Li 2020, Ji and Telgarsky 2020]

1. Margin improvement. [Lyu and Li 2020] directly analyzed the smoothed margin (see their equation (3)). This does not work for non-homogenous predictors. Instead, we have to analyze a modified margin (see (6) in lines 213-215). Identifying the correct modification of the margin involves a sharp balance of many error terms. This is quite technical as we aim to cover as many non-homogeneous functions as possible; behind the scenes, we solve multiple ODEs to identify the right formula. Coming up with this modified margin is a significant technical contribution.

2.Directional convergence. The analysis in [Ji and Telgarsky 2020] heavily relies on a specific form of GF defined using the minimal norm subgradient; they then analyzed the corresponding spherical and radial components (see their Lemms C.2 and C.3)). This again fails to work for non-homogenous predictors. To address this issue, we have to consider a different form of GF defined with a special subgradient, which enables a special spherical and radial decomposition as shown in equations (21) and (22) and Lemma C.17. Moreover, we have to use an advanced property of the o-minimal structure to show that the choice of sub-gradient does not affect the global path property of GF (see Lemma A.6).

3.KKT convergence. Our KKT convergence proof for non-homogenous predictors is new. Although KKT conditions are well established for a homogeneous predictor that maximizes the margin, it is a priori unclear why an optimal non-homogenous predictor admits KKT conditions. To address this issue, we first need to prove the existence of a sufficiently good homogenization of a near-homogeneous predictor (see Theorem 5.1). Then we come up with a set of KKT conditions of a margin maximization program — however, this is not defined using the original predictor — this is defined using its homogenization. Because of this discrepancy, we have to design and analyze new dual variables that involve both the non-homogenous predictor and its homogenization (see equation (44)).

B. Technical novelty in GD analysis

We solve many additional technical challenges when extending our GF analysis to GD. Due to the space limit, we highlight two of them:

4.Stepsize condition. Although [Lyu and Li 2020] handled GD in the homogenous case, their stepsize assumption depends on a “constant” $C_{\eta}$ (see their Assumption (S5) in Appendix E.1), which turns out to be function of the initial margin (see their Page 32), preventing the stepsize to be large. In comparison, our assumptions on the stepsize are weak, determined by an explicit and interpretable separability condition (see Assumption 5). To achieve this, we have to conduct a technical, yet much tighter, analysis of the GD path (see our Theorem F.9 and Lemma F.10). This is beyond the techniques from [Lyu and Li 2020].

5.Directional convergence. Our directional convergence analysis for GD is new. Note that [Ji and Telgarsky 2020] only analyzed GF but not GD, where tools from differential equations are unavailable. To address this issue, we construct an arc by connecting all GD iterates using line segments. Even so, analyzing the directional limit of this arc is extremely technical, involving careful estimations of the spherical and the radial parts of this arc (see Lemmas F.16 and F.17, which are not needed for GF). These additional technical challenges do not exist in the GF analysis but must be addressed in the GD analysis. We will highlight these in the revision.

Thank you for your thoughtful comments and suggestions on the writing style. We will include more discussions on intuitions and technical innovations for our theorems in the revision. For the technical novelty, please refer to the section Technical novelty in our response to the reviewer R5kD. For insights of our results, please refer to the section Insights of our results in our response to the reviewer NQfK. Below, we address your other questions.

---

Q1. “I am wondering whether the upper bound on the degree of the polynomial in Definition 1 can be relaxed…why does the upper bound have to be $M$, and is there any intuition behind this choice?”

A1. In Definition 1, the upper bound of the degrees of the polynomials have to be $M$. We justify this from the following two aspects.

First, we discuss its importance. If we relax the degree upper bound from $M$ to $M+1$, then every sufficiently smooth function $f(\theta; x)$ that is uniformly bounded by $O(\\\| \\theta \\\|\_2\^M)$ for large $\\\| \\theta \\\|\_2$ satisfies Definition 1. This includes predictors that do not admit a homogenization (see Theorem 5.1). Note that homogenization plays a crucial role in our analysis. For instance, without homogenization, it seems impossible to even define a KKT problem, let alone prove the implicit bias of KKT directional convergence of GF/GD.

Second, we explain the intuition for choosing $M$ as the degree upper bound. In Definition 1, the polynomial $p’$ quantifies the deviation of $f$ from an $M$-homogeneous function (see $f_M$ in Theorem 5.1). Given that we require $f$ to be “near-homogeneous”, it is natural to assume that the discrepancy between $f$ and $f_M$ (quantified by $p’$) is of an order lower than $f_M$. The natural assumption, $\deg p \leq M$, suffices for this purpose.

We will clarify these in the revision.

---

Q2. “Why is it helpful to define the upper bound as a polynomial of the weight norm? Did you use any specific tools for handling polynomials? If not, why not simply set the upper bound as $O( \\| \\theta \\|_2^M)$ instead of introducing the polynomial concept $p' ( \\| \\theta \\|_2)$?”

A2. Good question. But before we address it, we would like to point out that the error upper bound is $p' ( \\| \\theta \\|\_2) = O(\\| \\theta \\|\_2^{M-1})$ in our Definition 1. So in your question, the error upper bound should be replaced by $o( \\| \\theta \\|_2^{M})$ instead of $O( \\| \\theta \\|_2^{M})$. We suspect this is a typo. But please let us know if we misunderstood your question.

We choose to define the upper bound as $p’$ in Definition 1, primarily for the simplicity of the exposition. This choice allows us to explicitly define the function $p_a$ (see Eq. (4)), which streamlines the theorem statements and their proof by making the inequalities more explicit and tractable.

Note that our results are not limited to this specific polynomial form. If the upper bound in Definition 1 is replaced by a function uniformly bounded by $O(\\\| \\theta \\\|\_2^{M-1})$ for large $\\\| \\theta \\\|\_2$, our analysis still goes through when Assumption 2 is adjusted accordingly. However, we do not feel this provides new information compared to our current version.

In general, if the error upper bound is only controlled by $o( \\\| θ \\\|\_2\^{M})$, we expect additional regularity conditions are needed to carry out the analysis. As our main focus is neural networks, we feel our current definition is both clean and sufficiently broad. We leave it as future work to further extend our results. We will include these discussions in the revision.

---

We thank the reviewer for their detailed comments and will fix all grammar issues and typos in the revision. For the technical novelty, please refer to the section Technical novelty in our response to the reviewer R5kD. For insights of our results, please refer to the end of this response. Below, we address your other questions.

---

Q1. "Is there an intuitive meaning to $p_a$? If so, it should be discussed briefly in the main paper."

A1. $p_a$ is used in our Assumption 2. This choice of $p_a$ guarantees that the class of near-homogeneous functions under Assumptions 1 and 2 all behave close enough to a homogeneous function along the GF path for $t\ge s$. Concretely, as shown in Lines 945-950, $p_a$ is chosen such that $g:= f - p_a$ satisfies a one-sided inequality of the homogeneous condition (see equation (3) in Line 152). This is a crucial design choice that enables our proof.

---

Q2. "Possible typo in line 136-l, line 885 and line 1043."

A2. Thanks for pointing these out. These are all typos. (i) The period in line 136-l should be a comma; (ii) $\log \phi$ in line 885 should be replaced by $\phi$; (iii) In line 1043, $G$ in the denominator should be $G_t$. We will make sure to correct them and other typos in the revision.

---

Q3. Starting from page 35, there seems to be a change in the naming of the assumptions, e.g. (A1)-(A3), (B1)-(B3), which does not match the main text and is not clearly addressed.

A3. We will fix this in the revision.

---

Q4. “Line 1212 — which proof does “We skip the proof here” refer to? Seems to be regarding Lemma C.14 which is proved later on, in page 27.”

A4. You are correct. The proof of Lemma C.14 is on page 27. We will polish this part (and all the appendix) carefully in the revision.

---

Q5. “Line 1624 — what does “for all $i \in [n]$” refer to? Is the supremum also being taken over $i$?”

A5. This is a typo. In this place, we define $B\coloneqq [ (\gamma^{GF}(\theta_s)]^{-1/M}$. Then we can verify that

$$\sup_{t \ge s, i \in [n]} \bar{f}_{M,i}^{-1/M} (\theta_t) \cdot \\|\theta_t\\|_2 \le B.$$

This suffices for the remaining proof. We will fix this in the revision.

---

Q6. "Proof of Lemma C.22 — there is a mismatch between the value of in line 1630, and the RHS in line 1681."

A6. This is a typo. The correct formula for $\delta$ is

$$\delta := n B^2 \frac{1+2 p_a(\rho_t)}{M \bar f_{M,\min }(\theta_t)}.$$

---

Q7. "In light of this, the contributions of the paper given previous results seem marginal, as, in addition, and as far as I noticed, there is no significant technical novelty beyond that of [1, 2]. "

A7. We respectfully disagree with your assertions that our contributions are marginal and our technical novelty is not significant. For the technical novelty, please refer to the section Technical novelty in our response to the reviewer R5kD. For insights of our results, please refer to the end of this response.

---

---

Insights of our results

We highlight insights from our results in the following three aspects.

1. A good definition = good insights. As a first step towards understanding implicit bias for non-homogeneous models, identifying the proper function classes for which meaningful theoretical insights can be extracted is already a challenging task. There are a few attempts in prior literature, but they seem to be far less fundamental than ours (see paragraph “Non-homogeneous Predictors” in Section 1.1). Our Definition 1 provides a natural quantification of the homogeneity error, covers a large class of networks, and has rich implications on the implicit bias. Such a powerful definition is rare, which already carries significant insights in our opinion.

2. Insights for understanding implicit bias. Our results suggest that a near-homogeneous predictor has the same implicit bias as its companion homogenization (see Theorem 3.4 and 5.1). This provides an important insight: understanding the implicit bias of a non-homogenous predictor can be reduced to understanding that of its homogenization. Compared to a generic non-homogenous model, its homogenization is much simpler to study (despite still being challenging).

3. Broader implications beyond DL theory. To the best of our knowledge, our near-homogeneity definition is novel and cannot be found even in pure math literature. As homogeneity is a fundamental math concept, widely used in many areas (such as PDE, harmonic analysis, and semi-algebraic geometry), our notion of near-homogeneity could motivate broader mathematical research beyond deep learning theory. In this regard, we believe technical tools established in our paper, integrating the near-homogeneity with o-minimal structures and non-smooth analysis (see also section Technical novelty in our response to reviewer R5kD), might be of broader interest. We will include these discussions in the revision.