Implicit Bias of Mirror Flow on Separable Data

We thank the reviewer for their thorough report and relevant comments. We will take them into account and make the appropriate changes in the revised version. Please find below our response to the comments.

Weaknesses

W1: Indeed, our result has connections with Theorem 5 from Gunasekar et al. (2018). Note first that the updates of steepest descent and mirror descent are different and one cannot be seen as a special case of the other (unless the geometry is Euclidean). For a norm $\Vert \cdot \Vert$, the steepest descent update is given by $w\_{t+1} = \text{arg min}\_{w} \ L(w\_t) + \langle \nabla L(w\_t), w - w_t \rangle + \Vert w - w_t \Vert^2$ whereas the mirror descent update is given by $w\_{t+1} = \text{arg min}\_{w} \ L(w\_t) + \langle \nabla L(w\_t), w - w_t \rangle + D\_\phi(w, w_t)$ for a potential $\phi$.

We can however observe the following connection: if the horizon function $\phi_\infty$ is a norm (this is the case when $\phi$ is symmetric), then the implicit bias induced by mirror descent is the same as that of steepest descent with norm $\phi_\infty$. In other words, $\phi$-mirror descent is asymptotically equivalent to $\phi_\infty$-steepest descent.

Regarding the possible implications: our result could be used to study the mirror flow with new potentials that arise from gradient flow more complex neural network architectures, some of which are still under investigation (see answer to Q1 below).

W2: The same results could be derived for mirror descent with finite step size, without major additional difficulties. We chose to study mirror flow as it simplifies the proofs and the presentation.

W3: Indeed, we were (intentionally) a bit sloppy with the math, but the reasoning is correct. To make the derivation rigorous, one has to first consider any countable sequence $(t\_n)\_{n \in \mathbb{N}}$ with $t\_n \to \infty$ as $n \to \infty$ and then consider the sequence $(\bar{\beta}\_{t\_n}, q(\beta\_{t_n}))\_{n \in \mathbb{N}}$. We can then rightfully apply the Bolzano–Weierstrass theorem. Since the final limit $(\bar{\beta}\_\infty, q\_\infty)$ does not depend on the sequence $t_n,$ we can indeed conclude that $(\bar{\beta}\_{t}, q(\beta\_{t}))_{t \in \mathbb{R}}$ must converge towards it. We will clarify this argument in the revised version.

Questions

Q1: The link between gradient flow on $q$-homogeneous networks (as in [1]) and mirror flow (as in our setting) is still opaque. As discussed in our conclusion section, gradient flow on a depth $q$ diagonal linear network can be seen through the lens of [1], as well as through the lens of mirror flow (as in our paper). However, whether a link exists in more general settings is still unclear and remains a very interesting question for future work.

Q2: It is indeed a typo, thank you for pointing it out.

Q3: The main purpose of Lemma 2 is to ensure that the mirror flow solution exists and that it is well-defined for all $t \geq 0$. This fact is not trivial since, in a more general setting, the solution could "blow up in finite time". Previous work does not always prove global existence and implicitly assumes it to be true. Uniqueness is obtained as a by-product.

Regarding the fact that $\int_0^t a(\beta_s)ds \rightarrow \infty$, it is an essential result for the main proof. We need it to apply the time change followed by the Cesaro argument (see lines 580 to 587 in the appendix).

Q4: We made a notation error throughout the proof of Corollary 2: we used $h$ instead of $\phi$. We will fix this.

Formula (8) stems from the fact that the gradient of $\phi$ is orthogonal to its level sets (we can invoke a result from multivariate calculus such as [1]). This means that $\nabla \phi(\beta_s)$ belongs to the normal cone of $S_{\phi(\beta_s)}$ at $\beta_s$. The subdifferential of the indicator of a convex set is given by its normal cone [2, Chap. 23], which allows to conclude. We will add these details to the revision.

[1] Richard Courant; Fritz John (1999). Introduction to Calculus and Analysis Volume II/2.

[2] R. Tyrell Rockafellar (1973). Convex Analysis.

We thank the reviewer for their report and relevant comments.

Weaknesses

The comment we make line 294 concerns the training loss convergence rate. We provide empirical evidence Figure 1 (left), we observe that the exact rate indeed depends on the potential. Also note that standard results from convex optimisation enables to show an $\tilde{O}(1 / t)$ upperbound on the rate (see proof of Proposition 1).

Lines 303-304, we refer to the convergence rate of the normalised iterates towards the maximum margin solution, which we leave for future work. It would depend on the speed at which the normalised sublevel sets $\bar{S}\_c$ converge towards the limiting shape $S_\infty$.

Questions

Q1: We indeed need to assume that the $\phi_\infty$-max-margin problem has a unique solution, otherwise there could exist multiple subsequential limits. This is stated in the assumptions of Theorem 2. We also discuss sufficient conditions for this assumption to hold on lines 239-243.

Q2: We will add more details concerning Figure 1 in Section 5. We agree with the reviewer that plotting the full trajectory is interesting and we will add it in the revised version.

We thank the reviewer for their positive report and relevant comments.

It can be verified that the logistic loss indeed satisfies the exponential-tail condition of Assumption 1, since $\ln(1+\exp(-z))$ is equivalent to $\exp(-z)$ as $z \rightarrow + \infty$.

We thank the reviewer for their report and relevant comments.

Q1: In Theorem 3, we provide a formula for computing the horizon function when the potential $\phi$ is separable. In that case, $\phi_\infty$ can be obtained by computing the limit at infinity of a simple one-dimensional function. We apply this to two examples of non-homogenous potentials in Section 5: the hyperbolic entropy and the cosine entropy.

For non-separable potentials, there is a priori no straightforward formula and one has to find the limiting shape $S_\infty$ towards which the normalised sublevel sets $\bar{S}_c$ converge to as $c \to \infty$. However, we emphasize that the separable case covers almost all known examples.

Q2: By building on the arguments of Proposition 1 (line 467), we could show that $L(\beta_t)$ decreases with rate $\tilde{O}(1/t)$. However, this convergence rate does not inform us on the rate of convergence of the normalized iterates $\bar \beta_t$ to the limiting direction. This question is indeed a challenging open problem and is left for future work.