The Implicit Bias of Gradient Descent on Separable Multiclass Data

Line 262: Why is $u_{\pm} = 0$, while in Def. 2.2, it can be anything?

We could have worded this better, thank you for the question! All the relative margins (which comprise $\mathbf{u}$, the vector argument to the template) go to infinity so that lets us pick any finite value for $u_{\pm}$. The value 0 in particular works for us because the 3 losses we analyze (cross-entropy, exponential loss, PairLogLoss) satisfy exponential tail with this parameter setting, as proven in Appendix C. We will re-word this in the paper to avoid any confusion in readers' minds.

Lines 609 to 611: I understand from the argument that...

Thank you for the careful reading! We note that one can easily verify this property for the 3 losses analyzed in our paper. Nevertheless, we are able to fill this gap for general losses using a new structural result on convex, symmetric, differentiable functions that we proved. The caveat is that now, our results require an additional assumption that the loss template be convex. It is easy to see that all 3 losses analyzed are convex by computing the second derivatives and verifying they are non-negative. We note that this condition is not required in the binary case in Soudry et al 2018. This is an interesting difference between the binary and multiclass case which we hope to address in future work. $\newcommand{\bbR}{\mathbb{R}}$ $\newcommand{\bfx}{\mathbf{x}}$ $\newcommand{\bfu}{\mathbf{u}}$ $\newcommand{\bfv}{\mathbf{v}}$

Our new structural result is stated below. First we need an additional piece of notation: Given a vector $\bfx \in \bbR^{n}$ and a real number $C \in \bbR$, define $\bfx \vee C \in \bbR^{n}$ to be the vector such that the $i$-th component of $\bfx \vee C$ is equal to $\max(x_{i}, C)$, for all $i \in [n]$.

Theorem. Suppose that $f : \bbR^{n} \to \bbR$ is a symmetric, convex, and differentiable function. Then for any real number $C \in \bbR$ and any $\bfx \in \bbR^{n}$, we have $\tfrac{\partial f}{\partial x_{i}} ( \bfx ) \le \tfrac{\partial f}{\partial x_{i}} (\bfx \vee C)$ for any $i \in \mathrm{argmin}(\bfx)$.

Using this theorem, we show that if not all components of $\bfu$ go to infinity, then we can derive a contradiction to $\nabla \psi(u) \rightarrow \mathbf{0}$, using the exponential tail property. We sketch the details of this.

1. Suppose that $\bfu^t$ is a sequence such that $\lim_t \nabla \psi(\bfu^t) \to 0$, but there exists a component $j$ such that $u^t_j$ does not go to infinity.
2. There must be a finite number $M$ such that $u^t_j \le M$ for infinitely many $t$. We pass to the subsequence so that $u^t_j \le M$ always.
3. Define $C := \max (\quad 2|u_{-}|, \quad M,\quad -\log (\tfrac{1}{2(K-1)}) \quad )$.
4. Define $\bfv^t := \bfu^t \vee C$. Then $\min(\bfv^t) \geq C$. Using the lower exponential tail bound combined with $C \geq -\log (\tfrac{1}{2(K-1)})$, this implies that $-\tfrac{\partial \psi(\bfv^t)}{\partial v_i} \geq \tfrac{1}{2}c\exp(-av_i)$.
5. Applying the theorem for all $i \in \mathrm{argmin}(\bfu^t)$, we get $\tfrac{\partial \psi(\bfu^t)}{\partial u_i} \leq \tfrac{\partial \psi(\bfv^t)}{\partial v_i} \leq -\tfrac{1}{2}c\exp(-av_i) < 0$. This contradicts what we proved on line 608, i.e. $\lim_t \nabla \psi(\bfu^t) \to 0$.

We are happy to follow up with more details of this sketch if you are interested.

Thank you for the careful reading and catching these typos! We will update our paper to reflect these changes. We also clarify line 116.

In page 3 line 85, the meaning of $[\mathbf{v}]\sigma(j)$ doesn't seem clear to me, is it $[\mathbf{v}]_{\sigma(j)}$?

Yes. This was a typo, we will remove $[\mathbf{v}]\sigma(j)$ from the paper.

Thank you for your review and catching the typo. We appreciate your time and the supportive feedback. We've added numerical simulations demonstration implicit regularization towards the hard margin SVM when using the PairLogLoss, in line with our theory's prediction. It is attached to the "global rebuttal" above.

$\newcommand{\bfx}{\mathbf{x}}$ $\newcommand{\bfW}{\mathbf{W}}$ $\newcommand{\bfw}{\mathbf{w}}$ $\newcommand{\bfD}{\mathbf{D}}$ $\newcommand{\mlc}{\boldsymbol{\Upsilon}}$ $\newcommand\pseudoindex[1]{[#1 ]}$

From a conceptual point of view, the results of the present paper do not provide additional insight into the implicit bias of multiclassification with respect to previous works limited to the cross-entropy loss.

Our novel insight is characterizing the conditions on a loss that suffice to endow it with the implicit bias towards the max-margin solution. This is significant because, while cross-entropy is the most popular loss used, there are many new losses being proposed that offer competitive performance (PairLogLoss being an example). Our work fills in a gap in the loss design literature regarding how to design losses that have the same implicit regularization property as the cross entropy. Also, our technique can be of wider interest due to the unified treatment of binary and multiclass classification, which your next feedback covers which we now address.

Also at the technical level, as the authors themselves state, using the PERM framework allows for a simple generalisation of the results of (Soudry et al., '18) to the multiclass case, to the point that a large fraction of the proof is identical or almost identical.

Our work offers a unified treatment of both binary and multiclass, and shows that the proof strategy from the binary case carries over. This is a strength of our analysis. Although some of our proofs simply mirrors the pre-established binary case, a large portion of our analysis is novel and nontrivial. For example, our new definition of exponential tail is itself a novel contribution. This definition captures the specific property that is needed for the implicit bias to hold for a broad class of losses beyond just cross-entropy. Additionally, verifying that existing multiclass losses satisfy our exponential tail definition (as well as the beta-smoothness condition) is nontrivial- the proofs are in Appendix C. Finally, we develop some novel tools and techniques to lay the groundwork for future binary-to-multiclass generalizations in the PERM framework. These techniques are captured in Lemmas 4.1 and 4.2, as well as Appendices B and D. This puts us at about 12 pages of novel analysis not present in (Soudry et al., '18).

Definition of $\tilde{\mathbf{x}}$ in Eq.~(9)?

$\tilde{\mathbf{x}}$ is defined on line 187.

The definition of coordinate projection after Eq. (19) in the proof of Lemma 4.5 is unclear;

This is an understandable confusion since we use a lot of different notation. Additionally, thank you for helping us notice a typo. On line 254, instead of "the $\tilde{\bfx}_{i,i}$ 0-entry is omitted",

it should say "the $\tilde{\bfx}_{i,y_i}$ 0-entry is omitted". This entry is 0 because looking at the definition on line 187, the $\mathbf{A}$ matrices will cancel out.

What we mean by our coordinate projection notation is essentially the following:

$\pseudoindex{\mlc_{y_{i}} \bfD \bfW^{\top} \bfx_{i}}_{k}$

is equal to

$\tilde{\bfx}_{i,k}^{\top} \bfw$

if $k < y_i$. else if $k \geq y_i$, we have

$\tilde{\bfx}_{i,k+1}^{\top} \bfw$

Please also see the beginning of Appendix D for an intuitive explanation. Finally, we have added a remark in the paper to clarify this.

The explanation preceding Eq. (20) in the same proof could mention that Eq. (11) is also used.

Thank you for your suggestion; we will make this fix.