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

## Abstract

Abstract We study the implicit bias of the general family of steepest descent algorithms , which includes gradient descent, sign descent and coordinate descent, in deep homogeneous neural networks. We prove that an algorithm-dependent geometric margin starts increasing once the networks reach perfect training accuracy and characterize the late-stage bias of the algorithms. In particular, we define a generalized notion of stationarity for optimization problems and show that the algorithms progressively reduce a (generalized) Bregman divergence, which quantifies proximity to such stationary points of a margin-maximization problem. We then experimentally zoom into the trajectories of neural networks optimized with various steepest descent algorithms, highlighting connections to the implicit bias of Adam .

## 1 Introduction

Overparameterized neural networks excel in many natural supervised learning applications. A theory that aims to explain their strong generalization performance places optimization at the forefront: in problems where many candidate models are available, the optimization algorithm implicitly selects well-generalizing ones (). The term “implicitly” indicates that neither the unregularized loss function nor the architecture explicitly favors simple, well-generalizing solutions, but this occurs due to the choice of the optimization algorithm. Most existing theoretical results on this so-called implicit bias of optimization demonstrate, to some extent, that gradient descent in overparameterized problems biases the solution to be the simplest, in terms of the lowest possible $\ell_{2}$ norm of the weights (Soudry et al.,, ; Ji and Telgarsky,, , ; Lyu and Li,, ; Nacson et al.,, ).

Simplicity, however, is a term that depends on the setting.
For instance, in logistic regression with many irrelevant features, an $\ell_{1}$-regularized solution is simpler than an $\ell_{2}$-regularized one (Ng,, ).
Moreover, in contemporary deep learning, Adam (Kingma and Ba,, ), AdamW (Loshchilov and Hutter,, ), and related optimization algorithms are preferred for language modeling (Zhang et al.,, ), and their implicit bias might be better suited for such applications than gradient descent.
It is therefore important to understand the types of solutions favored by optimization algorithms beyond (stochastic) gradient descent, in order to address the current (and future) applications of deep learning.

In this work, we contribute to this line of research by studying the large family of steepest descent algorithms (Equation [1](#S2.E1)) with respect to an arbitrary norm $\lVert\cdot\rVert$ in deep, non-linear, homogeneous neural networks. This class of methods generalizes gradient descent to optimization geometries other than the Euclidean, allowing the update rule to operate under a different norm. It includes coordinate descent (which has strong ties to boosting (Mason et al.,, )) and sign gradient descent (which is closely related to Adam (Kunstner et al.,, )) as special cases.

Our contributions. We provide a unifying, rigorous analysis of any steepest descent algorithm in classification settings with locally-Lipschitz, homogeneous neural networks trained using an exponentially-tailed loss. Specifically, we focus on the late stage of training (after the network has achieved perfect training accuracy) in the limit of an infinitesimal learning rate. Our first result characterizes the algorithm’s tendency to increase an algorithm-dependent margin (Theorem [3.1](#S3.Thmtheorem1)): similar to prior work on gradient descent (Lyu and Li,, ), we show that a soft version of the geometric margin starts increasing immediately after fitting the training data.

We then turn our attention to the asymptotic properties of the algorithm. In an attempt to find evidence of margin maximization, we define a notion of stationary points for optimization problems, which generalizes the usual Karush-Kuhn-Tucker one (Definition [3.4](#S3.Thmtheorem4)), along with approximate versions (Definition [A.9](#A1.Thmtheorem9)). As we show, during training, the algorithms make implicit progress towards such stationary points of a margin maximization problem in a specific, geometric sense: they progressively reduce a (generalized) Bregman divergence (Definition [3.6](#S3.Thmtheorem6)), which quantifies how well the stationarity condition is satisfied.
As this process concludes, the limit points of training are along the direction of a generalized KKT point of the algorithm-dependent geometric margin maximization problem (Theorem [3.8](#S3.Thmtheorem8)). For algorithms whose squared norm is a smooth function (for example, any $\ell_{p}$ norm for $p\geq 2$), Theorem [3.8](#S3.Thmtheorem8) further implies directional convergence to KKT points of the same margin maximization problem (Corollary [3.9](#S3.Thmtheorem9)).

In total, these results provide evidence for (geometric) margin-maximization in any steepest descent algorithm and significantly generalize prior results that concerned gradient descent only (Lyu and Li,, ; Nacson et al.,, ). Moreover, the generalized divergence can be interpreted as a measure of proximity to stationarity for optimization problems, similarly to what was proposed in prior definitions of approximate KKT points in the literature (Dutta et al.,, ), and could be of broader interest to the optimization community. We find it appealing and theoretically intriguing that, despite the non-convexity of the loss landscape of deep neural networks, such simple convex structures emerge once the data points separate.

Finally, in Section [4](#S4), we train neural networks with the three main steepest descent algorithms (gradient descent, sign gradient descent and coordinate descent). We perform experiments in: (a) teacher-student tasks, to elucidate the theoretical findings and assess the connection between implicit bias and generalization and (b) image classification tasks, to study the relationship between Adam and steepest descent algorithms.

### 1.1 Related Work

There have been numerous works studying the implicit bias of optimization in supervised learning and their relationship to geometric margin maximization - see (Vardi,, ) for a survey.

Steepest descent algorithms with respect to non-Euclidean geometries have been explored before, both in supervised (e.g. ; Large et al., ()) and non-supervised (e.g. Carlson et al., ()) machine learning problems.
The implicit bias of this family of optimization methods was first studied in generality in Gunasekar et al., () in the context of linear models for separable data, where margin maximization was established. Their proof is based on a result on Adaboost due to Telgarsky, (). Most related to our paper are the works of Nacson et al., (); Lyu and Li, () and Ji and Telgarsky, (). Nacson et al., () studied infinitesimal regularization and its connection to margin maximization in both homogeneous and non-homogeneous deep models, while also proving (directional) convergence of gradient descent to a first order point of an $\ell_{2}$-margin maximization problem for homogeneous models under strong technical assumptions. Lyu and Li, (); Ji and Telgarsky, (), whose theoretical setup we mainly follow, significantly weakened the assumptions, under which such a result holds, and Lyu and Li, () further demonstrated the experimental benefits of margin maximization in terms of robustness. Kunin et al., () generalized these results to a broader class of networks with varying degree of homogeneity, which includes networks with biases and skip connections. Vardi et al., () identified cases where the KKT points of the $\ell_{2}$ margin maximization problems are not (even locally) optimal.

The implicit bias of Adam (Kingma and Ba,, ) has been previously studied in Wang et al., (, ) for homogeneous networks, where it is proven that it shares the same asymptotic properties as gradient descent ($\ell_{2}$ margin maximization).
Recently, Zhang et al., () analyzed a version of the algorithm in linear models, without a numerical precision constant, which arguably better captures realistic training runs, and found bias towards $\ell_{1}$ margin maximization - the same bias as in the case of sign gradient descent. This makes us optimistic that insights from our analysis, which covers sign gradient descent (steepest descent with respect to the $\ell_{\infty}$ norm), can shed light on the poorly understood implicit bias of Adam in deep neural networks. See also Xie and Li, () for a recently established connection between AdamW (Loshchilov and Hutter,, ) and sign gradient descent. An additional motivation for studying steepest descent algorithms is in improving the robustness of deep neural networks: Tsilivis et al., (), recently, provided experimental evidence and theoretical arguments that deep networks adversarially trained with different steepest descent algorithms exhibit significant differences in their (robust) generalization error.

## 2 Background

#### Learning Setup

We consider binary classification problems with deep, homogeneous, neural networks. Formally, let $\mathcal{S}=\left\{\mathbf{x}_{i},y_{i}\right\}_{i=1}^{m}$ be a dataset of i.i.d. points sampled from an unknown distribution $\mathcal{D}$ with $\mathbf{x}_{i}\in\mathbb{R}^{d}$ and $y_{i}\in\{\pm 1\}$ for all $i\in[m]$, and let $f(\cdot;\bm{\theta}):\mathbb{R}^{d}\to\mathbb{R}$ denote a neural network parameterized by $\bm{\theta}\in\mathbb{R}^{p}$. The vector $\bm{\theta}$ contains all the parameters of the neural network, concatenated into a single vector. We study training under an exponential loss $\mathcal{L}(\bm{\theta})=\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}$. We focus on this setting for simplicity in the main text, but our results should readily generalize to more common losses, such as the logistic loss, as well as its multi-class generalization - the cross-entropy loss. See Section [A.3](#A1.SS3) for details and extensions of our main result.

#### Algorithms

The family of steepest descent algorithms generalizes gradient descent to different optimization geometries, allowing the update rule to operate under an arbitrary norm (instead of the usual Euclidean one) (Boyd and Vandenberghe,, ). Formally, the update rule for steepest descent with respect to a norm $\lVert\cdot\rVert$ is:

$$ $\begin{split}\bm{\theta}_{t+1}=\bm{\theta}_{t}+\eta_{t}\Delta\bm{\theta}_{t},\text{ where }\Delta\bm{\theta}_{t}\text{ satisfies }\\ \Delta\bm{\theta}_{t}=\operatorname*{\arg\!\min}_{\|\mathbf{u}\|\leq\|\nabla\mathcal{L}(\bm{\theta}_{t})\|_{\star}}\left\langle\mathbf{u},\nabla\mathcal{L}(\bm{\theta}_{t})\right\rangle,\end{split}$ (1) $$

where the dual norm $\lVert\cdot\rVert_{\star}$ of $\lVert\cdot\rVert$ is defined as $\|\mathbf{z}\|_{\star}=\max_{\mathbf{v}}\{\left|\left\langle\mathbf{z},\mathbf{v}\right\rangle\right|:\|\mathbf{v}\|=1\}$ for any $\mathbf{z}$, and $\eta_{t}$ is a learning rate. Gradient descent can be derived from Equation [1](#S2.E1) with $\lVert\cdot\rVert=\lVert\cdot\rVert_{2}$. See Appendix [C](#A3) for details on how steepest descent algorithms are closely related to popular adaptive methods, such as Adam (Kingma and Ba,, ) and Shampoo (Gupta et al.,, ).

#### Assumptions & Technical Points

In order to formally allow commonly used activation functions, such as the ReLU, we theoretically analyze loss landscapes that are not necessarily differentiable. That is, we consider Clarke’s subdifferentials (Clarke,, ) in our analysis:

$$ $\partial f:=\mathrm{conv}\left\{\lim_{k\to\infty}\nabla f(\mathbf{x}_{k}):\mathbf{x}_{k}\to\mathbf{x},f\text{ differentiable at }\mathbf{x}_{k}\right\},$ (2) $$

where $\mathrm{conv}(\cdot)$ stands for the convex hull of a set.
Furthermore, we analyze steepest descent in the limit of infinitesimal step size, i.e. steepest flow:

$$ $\frac{d\bm{\theta}}{dt}\in\left\{\operatorname*{\arg\!\min}_{\|\mathbf{u}\|\leq\|\mathbf{g}_{t}\|_{\star}}\left\langle\mathbf{u},\mathbf{g}_{t}\right\rangle:\mathbf{g}_{t}\in\partial\mathcal{L}(\bm{\theta}_{t})\right\}.$ (3) $$

This choice simplifies the analysis while still capturing the essence of the bias of the algorithms. Finally, we make the following assumptions:

- (A1)
Local Lipschitzness: For any $\mathbf{x}_{i}\in\mathbb{R}^{d}$, $f(\mathbf{x}_{i};\cdot):\mathbb{R}^{p}\to\mathbb{R}$ is locally Lipschitz (and admits a chain rule - see Theorem [A.2](#A1.Thmtheorem2)).
- (A2)
$L$-Homogeneity: We assume that $f$ is $L$-homogeneous in the parameters, i.e. $f(\cdot;c\bm{\theta})=c^{L}f(\cdot;\bm{\theta})$ for any $c>0$.
- (A3)
Realizability. There is a $t_{0}>0$, such that $\mathcal{L}(\bm{\theta}_{t_{0}})<1$.

Assumption ([A1](#S2.I1.i1)) is a minimal assumption on the regularity of the network, while assumption ([A2](#S2.I1.i2)) includes many commonly used architectures. For instance, ReLU networks with an arbitrary number of layers, but without bias terms, satisfy ([A1](#S2.I1.i1)),([A2](#S2.I1.i2)).
Assumption ([A3](#S2.I1.i3)) ensures that the algorithm will succeed in classifying the training points and allows us to focus on what happens beyond that point of separation. Indeed, we are particularly interested in understanding the geometric properties of the model $f(\cdot;\bm{\theta}_{t})$ as $t\to\infty$ (at convergence) – the so-called implicit biases of the learning algorithms.

## 3 Theory

We analyze the behavior of steepest descent algorithms in the late stage of training and study their geometric properties and how these relate to geometric, algorithm-specific, margins.

### 3.1 Algorithm-Dependent Margin Increases

In linear models, where $f(\mathbf{x};\bm{\theta})=\left\langle\bm{\theta},\mathbf{x}\right\rangle$, the concept of $\lVert\cdot\rVert_{\star}$-geometric margin
(^1^11In this paper, we diverge from the established terminology when it comes to naming margins, by calling it $\lVert\cdot\rVert_{\star}$-geometric margin (instead of $\lVert\cdot\rVert$-geometric margin) when it is defined with respect to the $\lVert\cdot\rVert$ norm of the parameters. We believe this is proper, since the $\lVert\cdot\rVert_{\star}$-geometric margin in linear models maximizes the metric induced by the $\lVert\cdot\rVert_{\star}$ norm (and not its dual, $\lVert\cdot\rVert$).)
, $\min_{i\in[m]}\frac{y_{i}\left\langle\bm{\theta},\mathbf{x}_{i}\right\rangle}{\|\bm{\theta}\|}$, plays a central and fundamental role in the analysis of the convergence of training (Novikoff,, ) as well as in the generalization of the final model (Vapnik,, ).
Ideally, we would like to track a similar quantity when training general, homogeneous, non-linear networks $f(\cdot;\bm{\theta})$ with steepest descent with respect to the $\lVert\cdot\rVert$ norm:

$$ $\gamma(\bm{\theta})=\frac{\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta})}{\|\bm{\theta}\|^{L}}=\min_{i\in[m]}y_{i}f\left(\mathbf{x}_{i};\frac{\bm{\theta}}{\|\bm{\theta}\|}\right),$ (4) $$

where recall that $L$ is the level of homogeneity of the model. As it turns out, it is easier to follow the evolution of the following, soft, geometric margin:

$$ $\tilde{\gamma}(\bm{\theta})=-\frac{\log\mathcal{L}(\bm{\theta})}{\|\bm{\theta}\|^{L}}.$ (5) $$

The characterisation of “soft” comes from the definition of “softmax” (a.k.a. log-sum-exp), which is often used in machine learning. The same idea is used here to approximate the numerator of Equation [4](#S3.E4). The soft margin $\tilde{\gamma}(\bm{\theta})$ is at most an additive $\log m$ away from $\gamma(\bm{\theta})$ - see Lemma [A.7](#A1.Thmtheorem7).

We show next that, given the algorithm has reached a small value in the loss, the soft margin is non-decreasing. This theorem is similar to part of Lemma 5.1 in (Lyu and Li,, ), which is the key lemma in their result. Ours is admittedly simpler, avoiding a beautiful polar decomposition which was crucial in their analysis, yet, unfortunately, pertinent to the $\ell_{2}$ case only.

###### Theorem 3.1 (Soft margin increases) .

For almost any $t>t_{0}$, it holds:

$$ $\frac{d\log\tilde{\gamma}}{dt}\geq L\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{1}{L\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}}-\frac{1}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\geq 0.$ $$

###### Proof of a simplified version.

We present a proof for a simplified version of this theorem here, covering differentiable networks $f$, while we defer the full proof to Appendix [A.2](#A1.SS2). For differentiable losses, steepest flow corresponds to:

$$ $\frac{d\bm{\theta}}{dt}\in\operatorname*{\arg\!\min}_{\|\mathbf{u}\|\leq\|\nabla\mathcal{L}(\bm{\theta}_{t})\|_{\star}}\left\langle\mathbf{u},\nabla\mathcal{L}(\bm{\theta}_{t})\right\rangle.$ (6) $$

By the definition of the dual norm and chain rule, we have for any $t>0$:

$$ $\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert=\|\nabla\mathcal{L}(\bm{\theta}_{t})\|_{\star}\;\;\;\mathrm{and}\;\;\;\frac{d\mathcal{L}(\bm{\theta}_{t})}{dt}=-\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}.$ (7) $$

Let $\mathbf{n}_{t}\in\partial\|\bm{\theta}_{t}\|$ (recall that a norm $\lVert\cdot\rVert$ might not be differentiable everywhere). For any $t>t_{0}$, we have:

$$ $\begin{split}\frac{d\log\tilde{\gamma}}{dt}&=\frac{d}{dt}\log\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}-L\frac{d}{dt}\log\|\bm{\theta}_{t}\|\\ &=\frac{d}{dt}\log\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}-L\left\langle\frac{\mathbf{n}_{t}}{\|\bm{\theta}_{t}\|},\frac{d\bm{\theta}}{dt}\right\rangle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\text{Chain rule})\\ &\geq\frac{d}{dt}\log\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}-L\frac{\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}\;\;\;\;\;(\text{def. of dual norm and $\|\mathbf{n}_{t}\|_{\star}\leq 1$, Lemma~{}\ref{lem:subgrad_norm}})\\ &=-\frac{d\mathcal{L}(\bm{\theta}_{t})}{dt}\frac{1}{\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}}-L\frac{\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\text{Chain rule})\\ &=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{1}{\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right).\;\;\;\;\;(\text{Equation~{}\ref{eq:norms_equal_loss_descent_main}})\end{split}$ (8) $$

The first term inside the parenthesis can be related to the second one via the following calculation:

$$ $\begin{split}\left\langle\bm{\theta}_{t},-\nabla\mathcal{L}(\bm{\theta}_{t})\right\rangle&=\left\langle\bm{\theta}_{t},\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}y_{i}\nabla f(\mathbf{x}_{i};\bm{\theta}_{t})\right\rangle\\ &=\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}y_{i}\left\langle\bm{\theta}_{t},\nabla f(\mathbf{x}_{i};\bm{\theta}_{t})\right\rangle\\ &=L\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}),\end{split}$ (9) $$

where the last equality follows from Euler’s theorem for homogeneous functions.
Now, observe that this last term can be lower bounded as:

$$ $\begin{split}\left\langle\bm{\theta}_{t},-\nabla\mathcal{L}(\bm{\theta}_{t})\right\rangle\geq L\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})\geq L\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})},\end{split}$ (10) $$

where we used the fact $e^{-\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\leq\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}=\mathcal{L}(\bm{\theta}_{t})$. We have made the first term of Equation [8](#S3.E8) appear. By plugging Equation [10](#S3.E10) into Equation [8](#S3.E8), we get:

$$ $\begin{split}\frac{d\log\tilde{\gamma}}{dt}&\geq\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{L}{\left\langle\bm{\theta}_{t},-\nabla\mathcal{L}(\bm{\theta}_{t})\right\rangle}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\\ &\geq\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{L}{\|\bm{\theta}_{t}\|\|\nabla\mathcal{L}(\bm{\theta}_{t})\|_{\star}}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right).\;\;\;\;\;(\text{definition of dual norm})\end{split}$ (11) $$

Noticing that $\|\nabla\mathcal{L}(\bm{\theta}_{t})\|_{\star}=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert$ (from Equation [7](#S3.E7)) concludes the proof.
∎

###### Remark 3.2 .

Observe that it is the geometric margin induced by the dual norm of the algorithm that is non-decreasing, and not any geometric margin. The proof crucially relies on the fact that $\|\nabla\mathcal{L}(\bm{\theta}_{t})\|_{\star}=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert$.

###### Theorem 3.1 (Soft margin increases) .

###### Proof of a simplified version.

###### Remark 3.2 .

### 3.2 Convergence to Generalized Stationary Points of the Max-Margin Problem

The previous theorem provides evidence and is a first indication that steepest flow implicitly maximizes the $\lVert\cdot\rVert_{\star}$-geometric margin in deep neural networks.
However, the monotonicity of the (soft) margin alone does not imply anything about its final value and its optimality.
In this section, we provide a concrete characterization of the asymptotic behavior of steepest flow: we show that any limit point of the iterates produced by steepest flow is along the direction of a generalized KKT point of the following margin maximization (MM) optimization problem:

$$ $\displaystyle\begin{split}&\min_{\bm{\theta}\in\mathbb{R}^{p}}\frac{1}{2}\|\bm{\theta}\|^{2}\\ \text{s.t. }&y_{i}f(\mathbf{x}_{i};\bm{\theta})\geq 1,\;\forall i\in[m].\end{split}$ (MM) $$

Let us recall the definition of a Karush-Kuhn-Tucker point (Karush,, ; Kuhn, H. W. and Tucker, A. W.,, ).

###### Definition 3.3 (KKT point) .

A feasible point $\bm{\theta}\in\mathbb{R}^{p}$ of ([MM](#S3.Ex2)) is a Karush-Kuhn-Tucker (KKT) point, if there exist $\lambda_{1},\ldots,\lambda_{m}\geq 0$ such that:

- 1.
$\partial\frac{1}{2}\|\bm{\theta}\|^{2}+\sum_{i=1}^{m}\lambda_{i}\partial\left(1-y_{i}f(\mathbf{x}_{i};\bm{\theta})\right)\ni 0$.
- 2.
$\lambda_{i}(1-y_{i}f(\mathbf{x}_{i};\bm{\theta}))=0,\;\forall i\in[m]$.

Notice that the first so-called stationarity condition is defined using set addition, since we are dealing with non-differentiable functions. See (Dutta et al.,, ) for more details on optimization problems with non-smooth objectives/constraints. Under some regularity assumptions, the KKT conditions become necessary conditions for global optimality and for non-convex problems like ([MM](#S3.Ex2)) they might be the best characterization of optimality we can hope for. See Lemma [A.11](#A1.Thmtheorem11) for details.

In the following definition of generalized KKT points, we relax the stationarity condition and parameterize it by a non-negative function.

###### Definition 3.4 ( $d$ -generalized KKT point) .

Let $d:\mathbb{R}^{p}\times\mathbb{R}^{p}\to\mathbb{R}_{+}$. A feasible point $\bm{\theta}\in\mathbb{R}^{p}$ of ([MM](#S3.Ex2)) is called a $d$-generalized KKT point if there exist $\lambda_{1},\ldots,\lambda_{m}\geq 0$, $\mathbf{h}_{i}\in\partial f(\mathbf{x}_{i};\bm{\theta})$ and $\mathbf{k}\in\partial\frac{1}{2}\|\bm{\theta}\|^{2}$ such that:

- 1.
$d\left(\sum_{i=1}^{m}\lambda_{i}y_{i}\mathbf{h}_{i},\mathbf{k}\right)=0$.
- 2.
$\lambda_{i}(1-y_{i}f(\mathbf{x}_{i};\bm{\theta}))=0,\;\forall i\in[m]$.

###### Remark 3.5 .

When $d$ in the definition of a $d$-generalized KKT point is any metric, we readily recover the original definition of KKT point.

In Appendix [B](#A2), we demonstrate how to construct a progress measure for optimization problems leveraging the above notion of stationarity (as well as its approximate version - see Definition [A.9](#A1.Thmtheorem9)).

As we will show, the function $d$, which in our case measures proximity of steepest flow to stationarity, is a generalized Bregman divergence
induced by the dual norm of the algorithm (squared).

###### Definition 3.6 (Generalized Bregman divergence) .

Let $\psi:\mathbb{R}^{p}\to\mathbb{R}$ with $\psi(\bm{\theta})=\frac{1}{2}\|\bm{\theta}\|_{\star}^{2}$ for all $\bm{\theta}\in\mathbb{R}^{p}$. We define the (generalized) Bregman divergence $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\mathbf{m}}(\cdot,\cdot):\mathbb{R}^{p}\times\mathbb{R}^{p}\to\mathbb{R}$ induced by $\psi$ as follows:

$$ $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\mathbf{m}}(\mathbf{y},\mathbf{z})=\frac{1}{2}\left\lVert\mathbf{y}\right\rVert_{\star}^{2}-\frac{1}{2}\left\lVert\mathbf{z}\right\rVert_{\star}^{2}-\left\langle\mathbf{m},\mathbf{y}-\mathbf{z}\right\rangle,$ (12) $$

where $\mathbf{m}\in\partial\frac{1}{2}\left\lVert\mathbf{z}\right\rVert_{\star}^{2}$.

###### Remark 3.7 .

Notice that if the function $\psi(\bm{\theta})=\frac{1}{2}\|\bm{\theta}\|_{\star}^{2}$ is differentiable, then the subdifferental defined at any point collapses to a single element: the gradient of $\psi$. If, further, $\psi$ is strictly convex, then Equation [12](#S3.E12) coincides with the usual Bregman divergence induced by $\psi$, defined as $D_{\psi}(\mathbf{y},\mathbf{z})=\psi(\mathbf{y})-\psi(\mathbf{z})-\left\langle\nabla\psi(\mathbf{z}),\mathbf{y}-\mathbf{z}\right\rangle$. Bregman divergences (Bregman,, ) generalize the Euclidean squared distance in different geometries and have found numerous applications in machine learning (A. Nemirovskii and D. Yudin,, ; Banerjee et al.,, ).

We are now ready to state our main result.

###### Theorem 3.8 .

Under assumptions ([A1](#S2.I1.i1)), ([A2](#S2.I1.i2)), ([A3](#S2.I1.i3)), consider steepest flow with respect to a norm $\lVert\cdot\rVert$ (Equation [3](#S2.E3)) on the exponential loss $\mathcal{L}(\bm{\theta})=\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}$. Then, any limit point $\bar{\bm{\theta}}$ of $\left\{\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}\right\}_{t\geq 0}$ is along the direction of a $D_{\frac{1}{2}\lVert\cdot\rVert_{\star}^{2}}^{\tilde{\bm{\theta}}}$-generalized KKT point, of the following optimization problem:

$$ $\displaystyle\begin{split}&\min_{\bm{\theta}\in\mathbb{R}^{p}}\frac{1}{2}\|\bm{\theta}\|^{2}\\ \text{s.t. }&y_{i}f(\mathbf{x}_{i};\bm{\theta})\geq 1,\;\forall i\in[m],\end{split}$ (13) $$

where $D_{\frac{1}{2}\lVert\cdot\rVert_{\star}^{2}}^{\tilde{\bm{\theta}}}$ is a (generalized) Bregman divergence induced by $\frac{1}{2}\lVert\cdot\rVert_{\star}^{2}$ and $\tilde{\bm{\theta}}={\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bar{\bm{\theta}})\right)^{-\frac{1}{L}}}\bar{\bm{\theta}}$.

Theorem [3.8](#S3.Thmtheorem8) states that the iterates induced by steepest flow have very specific, geometric properties: not only do they asymptotically approach (in direction) a generalized KKT point of a margin maximization problem, but also, as the proof of this theorem and, in particular, Proposition [A.15](#A1.Thmtheorem15) tells us, they implicitly make progress towards stationarity by decreasing a Bregman divergence between the gradient of the objective function and the gradient of the constraints of ([MM](#S3.Ex2)). The full proof can be found in Appendix [A](#A1).

While the previous result is not strong enough to guarantee convergence to a KKT point for any instantiation of the algorithm norm $\lVert\cdot\rVert$, it immediately implies it in the case of a norm whose square is a smooth function. We can prove the following corollary for this special class of steepest flows.

###### Corollary 3.9 .

Under assumptions ([A1](#S2.I1.i1)), ([A2](#S2.I1.i2)), ([A3](#S2.I1.i3)),
any limit point $\bar{\bm{\theta}}$ of $\left\{\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}\right\}_{t\geq 0}$ produced by steepest flow (Equation [3](#S2.E3)) with respect to a norm $\lVert\cdot\rVert$, whose square is a smooth function, on the exponential loss, is along the direction
of a KKT point of the optimization problem ([MM](#S3.Ex2)).

The proof relies on a fundamental relationship between smoothness of a function and strong convexity of its convex conjugate (Proposition [A.19](#A1.Thmtheorem19)), and can be found in Appendix [A](#A1).
The main contribution of Lyu and Li, (), which characterizes the implicit bias of gradient flow in homogeneous deep networks, can be recovered by the above result when $\lVert\cdot\rVert=\lVert\cdot\rVert_{2}$. Additionally, Corollary [3.9](#S3.Thmtheorem9) generalizes this result in at least the following cases of algorithm norms:

- •
Any $\ell_{p}$ norm with $p\in[2,\infty)$ – see, for example, Lemma 17 in Shalev-Shwartz, () for a proof of its smoothness.
- •
Any norm induced by a positive definite symmetric matrix – i.e. $f(\mathbf{x})=\left\langle\mathbf{x},\mathbf{A}\mathbf{x}\right\rangle,\mathbf{x}\in\mathbb{R}^{d},\mathbf{A}\in\mathbb{R}^{d\times d}$.
- •
Any $(2,D)$-smooth norm (i.e. a norm such that $\frac{d^{2}}{dt^{2}}\|\mathbf{x}+t\mathbf{z}\|^{2}\leq 2D^{2}\|\mathbf{z}\|^{2}$ for all $\mathbf{x},\mathbf{z}$ and for a $D>0$) – see Kakade et al., () for details.

To the best of our knowledge, this is a first result about the implicit bias of an algorithm in the parameter space of deep homogeneous neural networks which is not about $\ell_{2}$-geometric margin maximization.

###### Definition 3.3 (KKT point) .

###### Definition 3.4 ( d 𝑑 d -generalized KKT point) .

###### Remark 3.5 .

###### Definition 3.6 (Generalized Bregman divergence) .

###### Remark 3.7 .

###### Theorem 3.8 .

###### Corollary 3.9 .

## 4 Experiments

In this section, we train neural networks with various steepest descent algorithms (gradient descent-GD, coordinate descent-CD, sign descent-SD) to confirm the validity and measure the robustness of the theoretical claims,
and to discuss the connection between Adam and steepest descent algorithms.
Amongst other quantities, we measure the three relevant geometric margins during training, which, in the context of one-hidden layer neural networks with homogeneous activations and without biases, become:

$$ $\gamma_{1}=\min_{i\in[m]}\frac{y_{i}f(\mathbf{x}_{i};\bm{\theta})}{\|\bm{\theta}\|_{\infty}^{2}},\;\;\;\gamma_{2}=\min_{i\in[m]}\frac{y_{i}f(\mathbf{x}_{i};\bm{\theta})}{\|\bm{\theta}\|_{2}^{2}},\;\;\;\gamma_{\infty}=\min_{i\in[m]}\frac{y_{i}f(\mathbf{x}_{i};\bm{\theta})}{\|\bm{\theta}\|_{1}^{2}}.$ (14) $$

### 4.1 Teacher – Student Experiments

We first perform experiments in a controlled environment, where the generative process consists of Gaussian data passed through a one-hidden layer (“teacher”) neural network, which is sparse. Specifically:

$$ $\mathbf{x}\sim\mathcal{N}(0,I_{d}),\;\;y=\mathrm{sgn}\left(f_{\mathrm{teacher}}(\mathbf{x};\bm{\theta}^{\star})\right)=\mathrm{sgn}\left(\sum_{j=1}^{k}u_{j}^{\star}\sigma\left(\left\langle\mathbf{w}_{j}^{\star},\mathbf{x}\right\rangle\right)\right),$ (15) $$

where $\sigma(u)=\max(u,0)$ is the ReLU activation, $\mathrm{sgn}(\cdot)$ returns the sign of a number, and
$\|\bm{\theta}^{\star}\|_{0}$ is assumed to be small. We train
(“student”) neural networks of the same architecture, but of larger width
and with randomly initialized weights: $f_{\mathrm{student}}(\mathbf{x};\bm{\theta})=\sum_{j=1}^{k^{\prime}}u_{j}\sigma\left(\left\langle\mathbf{w}_{j},\mathbf{x}\right\rangle\right),$
with width $k^{\prime}>k$ and $w_{jl}\sim\mathcal{U}\left[-\frac{\alpha}{d},\frac{\alpha}{d}\right],j\in[k^{\prime}],l\in[d],u_{j}\in\mathcal{U}\left[-\frac{\alpha}{k^{\prime}},\frac{\alpha}{k^{\prime}}\right]$ (for CD we use: $w_{jl}\sim\mathcal{U}\left[-\frac{\alpha}{k^{\prime}},\frac{\alpha}{k^{\prime}}\right],j\in[k^{\prime}],l\in[d]$ in order to keep all the individual parameters to the same scale at initialization). The magnitude of initialization $\alpha$ can control how fast the implicit bias of the algorithm kicks in, with smaller values entering this so-called “rich” regime faster (Woodworth et al.,, ). We compare the performance of (full batch) GD, CD and SD in minimizing the empirical exponential loss,
consisting of $m$ independent points sampled from the generative process of Equation [15](#S4.E15).
Section [D](#A4) contains full experimental details.

Figure: Figure 1: Evaluation of steepest descent algorithms in a teacher-student setup. Left: Geometric margins ($\gamma_{1},\gamma_{2},\gamma_{\infty}$ in Equation [14](#S4.E14)) over the course of training (average over 20 different seeds). Right: Final test accuracy vs final $\ell_{\infty}$ margin ($\gamma_{\infty}$). Each point in the 2d space corresponds to a different run (only showing runs that did not diverge). Larger points correspond to larger initialization scales $\alpha$. The star points are produced by switching from GD to CD (red) or SD (green), right after the point of perfect train accuracy.
Refer to caption: /html/2410.22069/assets/x1.png

According to Theorems [3.1](#S3.Thmtheorem1), [3.8](#S3.Thmtheorem8), we expect GD to favor solutions with small $\ell_{2}$ norm. This is equivalent to a small sum of the product of the magnitude of incoming and outcoming weights across all neurons (Theorem 1 in ()).
On the other hand, CD will seek to minimize the $\ell_{1}$ norm of the parameters, which translates to a narrow network with sparse 1st-layer weights. Finally, SD’s bias towards small $\|\bm{\theta}\|_{\infty}$ solutions does not appear to be useful for generalizing from few samples in this task. Therefore, we expect CD $>$ GD $>$ SD in terms of generalization.

Figure [1](#S4.F1) displays our main findings. We summarize our key findings below:

- (i)
Margins increase past $t_{0}$. As expected from Lemma [3.1](#S3.Thmtheorem1), we observe that, right after the point of separation, each algorithm implicitly increases its corresponding geometric margin (Figure [1](#S4.F1) left). Furthermore, we observe that the ordering of the algorithms is as expected for each margin (SD attains larger $\ell_{1}$ margin than GD and CD, etc.), despite the fact that Theorem [3.8](#S3.Thmtheorem8) only guarantees convergence to a KKT point (at best) of the margin maximization problem - note the log-log plot.
- (ii)
Smaller initialization produces larger geometric margin. A smaller magnitude of initialization $\alpha$ causes a larger eventual value of the geometric margin (see Figure [1](#S4.F1) right for CD and $\gamma_{\infty}$, where this effect is stronger, and Figure [4](#A4.F4) in Appendix [D](#A4) for $\gamma_{1},\gamma_{2}$).
- (iii)
Importance of early-stage dynamics for generalization.
Figure [1](#S4.F1), right, shows the final test accuracy of the networks (20 different runs) vs the value of their final $\ell_{\infty}$ margin ($\gamma_{\infty}$). We observe that, while there exist more CD runs with good generalization (red circles), these do not always coincide with larger $\gamma_{\infty}$. Furthermore, intervening in the algorithms to encourage or discourage $\gamma_{\infty}$-maximization does not result in significant generalization changes: after running GD until the point of perfect train accuracy, we switch to either SD (green stars) or CD (red stars) to directly control the late stage geometric properties of the model. Switching to CD seems to bear marginal benefits in terms of generalization, even though all the switched runs reach smaller values of $\ell_{\infty}$ margin compared to the full, no-switching, GD runs. These benefits, however, pale in comparison to the full CD runs. Switching to SD, on the other hand, results in smaller $\gamma_{\infty}$ and similar or marginally worse test accuracy. See also Figure [4](#A4.F4) in Appendix [D](#A4) for test accuracy vs the other two geometric margins. We conclude that it is unlikely that large generalization benefits can solely and causally be linked to larger geometric margins in this setup, and it appears that the early stage dynamics play an important role for generalization.

### 4.2 Connection between Adam and Sign-GD

Figure: Figure 2: Accuracy, and $\ell_{1},\ell_{2}$ margins during training for GD, SD and Adam on MNIST (3 random seeds). Adam is parameterized by a numerical precision constant $\epsilon$ and two momentum parameters $(\beta_{1},\beta_{2})$ (defaulting to $10^{-8}$ and $(0.9,0.99)$). We observe that Adam behaves similar to SD for the period right after the point of perfect train accuracy.
Refer to caption: /html/2410.22069/assets/x2.png

Adaptive optimization methods like Adam (Kingma and Ba,, ) have been popular in deep learning applications, yet theoretically their value has been questioned (Wilson et al.,, ) and their properties remain poorly understood. Wang et al., (, ) studied the implicit bias of Adam in homogeneous networks and concluded that Adam shares the same asymptotic properties as GD. More recently, this conclusion has been challenged, in the sense that this asymptotic property crucially depends on a precision parameter of the algorithm and does not capture realistic runs of the algorithm (see Section [C.1](#A3.SS1) for details). In particular, it was shown that in linear models, Adam, without this precision parameter, implicitly maximizes the $\ell_{1}$-geometric margin (Zhang et al.,, ), a property shared with SD and not GD. Indeed, it is easy to see that Adam without momentum, and ignoring the precision parameters, is equivalent to SD (see Section [C.1](#A3.SS1)).
Setting the precision parameter to 0, on the other hand, is not useful in applications, as small initial values of the gradient result in divergence of the loss. A question arises: what, then, are the relevant geometric properties of Adam in practice?

Figure [2](#S4.F2) provides some experimental answers to this question, in light of Theorems [3.1](#S3.Thmtheorem1), [3.8](#S3.Thmtheorem8). On a pair of digits extracted from MNIST we train two-layer neural networks with GD, SD and Adam, with small initialization. See Section [D](#A4) for experimental details. We observe that, as soon as the algorithms reach 100$\%$ train accuracy, the margins start to increase (as Theorem [3.1](#S3.Thmtheorem1) suggests); SD reaches a larger value of $\gamma_{1}$, while GD reaches a larger value of $\gamma_{2}$. Interestingly, Adam with the default hyperparameters (precision $\epsilon=10^{-8}$ and non-zero momentum), initially, behaves similar to SD, increasing $\gamma_{1}$, before it starts decreasing it, in order to slowly start increasing $\gamma_{2}$! Curiously, larger values of $\epsilon$ increase $\gamma_{1}$ even further and start the second phase slower, but more aggressively. Notice, however, that train and test accuracies have long converged, so it is unlikely that a typical run would have lasted long enough to see the second phase of $\ell_{2}$-margin maximization (in particular, the loss value needs to be smaller than $10^{-7}$ in order to observe such behavior). Similar observations hold for Adam without momentum (recall that without momentum and for $\epsilon\to 0$, we recover SD). Therefore, it appears that the $\ell_{1}$ bias of SD (Theorems [3.1](#S3.Thmtheorem1), [3.8](#S3.Thmtheorem8) for $\lVert\cdot\rVert=\lVert\cdot\rVert_{\infty}$) more faithfully describes a typical run of Adam in neural networks.

## 5 Conclusion

In our work, we considered the large family of steepest descent algorithms with respect to an arbitrary norm $\lVert\cdot\rVert$ and provided a unifying theoretical analysis of their late-stage implicit bias when training homogeneous neural networks. Furthermore, we introduced a notion of stationarity for optimization problems (defined with respect to a Bregman divergence induced by the algorithm norm), which, as we showed, captures the implicit progress of the algorithms and might be of independent interest.
Theorem [3.8](#S3.Thmtheorem8) does not preclude the possibility that any steepest descent algorithm will converge to a KKT point; and our positive result (Corollary [3.9](#S3.Thmtheorem9)) shows that this is the case for smooth squared algorithm norm. It would be interesting and theoretically challenging to generalize this result to any norm or show a counterexample.

Our results can reinforce several recent efforts that attempt to understand deep learning through the lens of implicit bias. In particular, questions about generalization, robustness, and privacy can now be asked more broadly: (a) is it possible to extract training samples from neural networks optimized with Adam, leveraging its connection to sign gradient descent, similarly to what has been shown to be possible for gradient descent (Haim et al.,, )? (b) can we leverage our implicit bias results to design more sample-efficient algorithms for robust training, as argued by Tsilivis et al., ()? (c) is benign overfitting a general property of first-order methods, or are current results (e.g. Frei et al., (); Shamir, ()) specifically tailored to gradient descent?

#### Acknowledgments.

NT and JK acknowledge support through the NSF under award 1922658. GV is supported by research grants from the Center for New Scientists at the Weizmann Institute of Science, and the Shimon and Golde Picker – Weizmann Annual Grant. We would like to thank Zhiyuan Li and Kaifeng Lyu for a useful discussion. Part of this work was done while NT was visiting the Toyota Technological Institute of Chicago (TTIC) during the winter of 2024, and NT would like to thank everyone at TTIC for their hospitality, which enabled this work. Part of this work was done while JK and NT were hosted by the Centre Sciences de Donnees at the
École Normale Supérieure (ENS) in 2023/24, whose hospitality we gratefully acknowledge. This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise.

## Appendix A Missing Proofs

In this section, we provide proofs for the results stated in the main text.

### A.1 Steepest Flow

We first present a series of technical results, which are about steepest flow in the case of non-differentiable loss functions.
In what follows, we will denote with $\mathbf{g}_{t}^{\star}$ any loss subderivative with minimum $\left\lVert\cdot\right\rVert_{\star}$ norm, i.e. $\mathbf{g}_{t}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t})}\|\mathbf{u}\|_{\star}$.
In the case of subdifferentials, chain rule holds as an inclusion:

###### Theorem A.1 (Theorem 2.3.9 and 2.3.10 in Clarke, ( 1990 ) ) .

Let $z_{1},\ldots,z_{n}:\mathbb{R}^{d}\to\mathbb{R}$, $f:\mathbb{R}^{n}\to\mathbb{R}$ be locally Lipschitz functions and define $\mathbf{z}=(z_{1},\ldots,z_{n})$. Let $(f\circ\mathbf{z})(\mathbf{x})=f(z_{1}(\mathbf{x}),\ldots,z_{n}(\mathbf{x}))$ be the composition of $\mathbf{z}$ with $f$. Then, it holds:

$$ $\partial(f\circ\mathbf{z})(\mathbf{x})\subseteq\mathrm{conv}\left\{\sum_{i=1}^{n}\alpha_{i}\mathbf{h}_{i}:\bm{\alpha}\in\partial f(z_{1}(\mathbf{x}),\ldots,z_{n}(\mathbf{x})),\mathbf{h}_{i}\in\partial z_{i}(\mathbf{x})\right\}.$ (16) $$

To further analyze steepest flows and to guarantee loss monotonicity, we need a stronger chain rule result.
This can be achieved for a large class of locally Lipschitz functions, as per the following theorem which is due to Davis et al., ().

###### Theorem A.2 .

(Theorem 5.8 in Davis et al., ())
If $F:\mathbb{R}^{k}\to\mathbb{R}$ is locally Lipschitz and Whitney $C^{1}$-stratifiable, then it admits a chain rule: for all arcs (functions which are absolutely continuous on every compact subinterval) $\mathbf{u}:[0,\infty)\to\mathbb{R}^{k}$, almost all $t\geq 0$, and all $\mathbf{g}\in\partial F(\mathbf{u}(t))$, it holds:

$$ $\frac{dF(\mathbf{u}(t))}{dt}=\left\langle\mathbf{g},\frac{d\mathbf{u}(t)}{dt}\right\rangle.$ (17) $$

Whitney $C^{1}$-stratifiability includes a large family of functions, including functions defined in an o-minimal structure which has been a standard assumption in the literature Ji and Telgarsky, (). It excludes some pathological functions - see, for instance, Appendix J in Lyu and Li, (). This version of chain rule allows us to derive the following central properties of steepest flows.

###### Proposition A.3 .

Let $\mathcal{L}:\mathbb{R}^{p}\to\mathbb{R}$ and assume that $\mathcal{L}$ admits a chain rule. Then, for the steepest flow iterates of Equation [1](#S2.E1), it holds for almost any $t\geq 0$:

$$ $\frac{d\mathcal{L}}{dt}=-\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\leq 0,$ (18) $$

and

$$ $\left\langle\frac{d\bm{\theta}}{dt},-\mathbf{g}_{t}^{\star}\right\rangle=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}=\|\mathbf{g}_{t}^{\star}\|_{\star}^{2},$ (19) $$

where $\mathbf{g}_{t}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t})}\|\mathbf{u}\|_{\star}$.

###### Proof.

From Theorem [A.2](#A1.Thmtheorem2), for almost any $t\geq 0$, it holds $\forall\;\mathbf{g}_{t}\in\partial\mathcal{L}(\bm{\theta}_{t})$:

$$ $\frac{d\mathcal{L}}{dt}=\left\langle\mathbf{g}_{t},\frac{d\bm{\theta}}{dt}\right\rangle.$ (20) $$

Applying this for the element of $\partial\mathcal{L}(\bm{\theta}_{t}),\mathbf{g}_{t}^{\prime}$, that corresponds to $\frac{d\bm{\theta}}{dt}$ from the definition of steepest flow Equation [3](#S2.E3), we get:

$$ $\frac{d\mathcal{L}}{dt}=\left\langle\mathbf{g}_{t}^{\prime},\frac{d\bm{\theta}}{dt}\right\rangle=-\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2},$ (21) $$

where the last equality follows from the definition of the dual norm. But, Equation [20](#A1.E20) for $\mathbf{g}_{t}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t})}\|\mathbf{u}\|_{\star}$, yields:

$$ $\left\lvert\frac{d\mathcal{L}}{dt}\right\rvert=\left\lvert\left\langle\mathbf{g}_{t}^{\star},\frac{d\bm{\theta}}{dt}\right\rangle\right\rvert\leq\|\mathbf{g}_{t}^{\star}\|_{\star}\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert.$ (22) $$

Thus, combining Equation [21](#A1.E21), Equation [22](#A1.E22), we obtain:

$$ $\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert\leq\|\mathbf{g}_{t}^{\star}\|_{\star},$ (23) $$

which implies that the update rule Equation [3](#S2.E3) is equivalent to:

$$ $\frac{d\bm{\theta}}{dt}\in\left\{\operatorname*{\arg\!\min}_{\|\mathbf{u}\|\leq\|\mathbf{g}_{t}^{\star}\|_{\star}}\left\langle\mathbf{u},\mathbf{g}_{t}^{\star}\right\rangle:\mathbf{g}_{t}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t})}\|\mathbf{u}\|_{\star}\right\}.$ (24) $$

Therefore, from the definition of the dual norm, we have:

$$ $\left\langle\frac{d\bm{\theta}}{dt},-\mathbf{g}_{t}^{\star}\right\rangle=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}=\|\mathbf{g}_{t}^{\star}\|_{\star}^{2}.$ (25) $$

∎

Hence, under the mild assumptions of Theorem [A.2](#A1.Thmtheorem2), the loss is non-increasing during training.

###### Theorem A.1 (Theorem 2.3.9 and 2.3.10 in Clarke, ( 1990 ) ) .

###### Theorem A.2 .

###### Proposition A.3 .

###### Proof.

### A.2 Late Phase Implicit Bias

A useful standard characterization of the subdifferential of a norm is the following:

###### Lemma A.4 .

$$ $\partial\|\mathbf{x}\|=\{\mathbf{v}:\left\langle\mathbf{v},\mathbf{x}\right\rangle=\|\mathbf{x}\|,\|\mathbf{v}\|_{\star}\leq 1\}$ $$

We present the proofs for our results about the late stage of training in steepest flow algorithms. The next lemma quantifies the behavior of the smooth margin past the point $t_{0}$ (where, recall, zero classification error is achieved).

###### Theorem A.5 (Soft margin increases - full version) .

For almost any $t>t_{0}$, it holds:

$$ $\frac{d\log\tilde{\gamma}}{dt}\geq L\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{1}{L\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}}-\frac{1}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\geq 0.$ $$

###### Proof.

Let $\mathbf{n}_{t}\in\partial\|\bm{\theta}_{t}\|$. We have:

$$ $\begin{split}\frac{d\log\tilde{\gamma}}{dt}&=\frac{d}{dt}\log\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}-L\frac{d}{dt}\log\|\bm{\theta}_{t}\|\\ &=\frac{d}{dt}\log\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}-L\left\langle\frac{\mathbf{n}_{t}}{\|\bm{\theta}_{t}\|},\frac{d\bm{\theta}}{dt}\right\rangle\;\;\;\;\;(\text{Chain rule})\\ &\geq\frac{d}{dt}\log\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}-L\frac{\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}\;\;\;\;\;(\text{definition of dual norm and $\|\mathbf{n}_{t}\|_{\star}\leq 1$})\\ &=-\frac{d\mathcal{L}(\bm{\theta}_{t})}{dt}\frac{1}{\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}}-L\frac{\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}\;\;\;\;\;(\text{Chain rule})\\ &=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{1}{\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\;\;\;\;\;(\text{Equation~{}\ref{eq:loss_descent}}).\end{split}$ (26) $$

But, the first term inside the parenthesis can be related to the second one via the following calculation. Recall that, by Theorem [A.2](#A1.Thmtheorem2), for any $\mathbf{g}_{t}\in\partial\mathcal{L}(\bm{\theta}_{t})$ there exist $\mathbf{h}_{1}\in\partial y_{1}f(\mathbf{x}_{1};\bm{\theta}_{t}),\ldots,\mathbf{h}_{m}\in\partial y_{m}f(\mathbf{x}_{m};\bm{\theta}_{t})$ such that $\mathbf{g}_{t}=\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\mathbf{h}_{i}$. Thus, for a minimum norm subderivative $\mathbf{g}_{t}^{\star}$, we have:

$$ $\begin{split}\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle&=\left\langle\bm{\theta}_{t},\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\mathbf{h}_{i}^{\star}\right\rangle\\ &=\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\left\langle\bm{\theta}_{t},\mathbf{h}_{i}^{\star}\right\rangle\\ &=L\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}),\end{split}$ (27) $$

where the last equality follows from Euler’s theorem for homogeneous functions (whose generalization for subderivatives can be found in Theorem B.2 in Lyu and Li, ()). Now, observe that this last term can be lower bounded as:

$$ $\begin{split}\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle\geq L\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})\geq L\mathcal{L}(\bm{\theta}_{t})\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})},\end{split}$ (28) $$

where we used the fact $e^{-\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\leq\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}$. We have made the first term of Equation [66](#A1.E66) appear. By plugging Equation [28](#A1.E28) into Equation [66](#A1.E66), we get:

$$ $\begin{split}\frac{d\log\tilde{\gamma}}{dt}&\geq\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{L}{\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\\ &\geq\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{L}{\|\bm{\theta}_{t}\|\|\mathbf{g}_{t}^{\star}\|_{\star}}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\;\;\;\;\;(\text{definition of dual norm}).\end{split}$ (29) $$

Noticing that $\|\mathbf{g}_{t}^{\star}\|_{\star}=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert$ (from Proposition [A.13](#A1.Thmtheorem13)) concludes the proof.
∎

By extending Lemma B.6 of Lyu and Li, (), we can further prove that the loss converges to 0 and, thus, the norm of the iterates diverges to infinity.

###### Lemma A.6 .

As $t\to\infty$, $\mathcal{L}(\bm{\theta}_{t})\to 0$ and $\|\bm{\theta}_{t}\|\to\infty$.

###### Proof.

We suppress the dependence of the loss and the iterates from time $t$, when it is obvious from the context.

From the definition of the steepest flow update and chain rule (eq. Equation [18](#A1.E18)), we have

$$ $-\frac{d\mathcal{L}}{dt}=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}=\|\mathbf{g}_{t}^{\star}\|_{\star}^{2}\geq\frac{1}{\|\bm{\theta}\|^{2}}\left\langle\bm{\theta},-\mathbf{g}_{t}^{\star}\right\rangle^{2},$ (30) $$

where we applied Equation [19](#A1.E19), Equation [18](#A1.E18) and the definition of the dual norm. But, as we showed in Equation [28](#A1.E28), the above inner product can be upper bounded by a function of the loss, so, by plugging in, we get:

$$ $-\frac{d\mathcal{L}}{dt}\geq\frac{L^{2}}{\|\bm{\theta}\|^{2}}\left(\mathcal{L}\log\frac{1}{\mathcal{L}}\right)^{2}=\frac{L^{2}}{\left(\log\frac{1}{\mathcal{L}}\right)^{2/L}}\tilde{\gamma}^{2/L}(t)\left(\mathcal{L}\log\frac{1}{\mathcal{L}}\right)^{2}\geq\frac{L^{2}}{\left(\log\frac{1}{\mathcal{L}}\right)^{2/L}}\tilde{\gamma}^{2/L}(t_{0})\left(\mathcal{L}\log\frac{1}{\mathcal{L}}\right)^{2},$ (31) $$

which follows from the definition of the margin (Equation [5](#S3.E5)) and its monotonicity (Lemma [A.5](#A1.Thmtheorem5)).
By rearranging:

$$ $-\frac{d\mathcal{L}}{dt}\frac{1}{\mathcal{L}^{2}}\left(\log\frac{1}{\mathcal{L}}\right)^{2/L-2}\geq L^{2}\tilde{\gamma}(t_{0})^{2/L},$ (32) $$

and integrating over time from $t_{0}$ to $t>t_{0}$, we further have:

$$ $\int_{t_{0}}^{t}\left(\log\frac{1}{\mathcal{L}}\right)^{2/L-2}\frac{d}{dt}\frac{1}{\mathcal{L}}dt\geq L^{2}\tilde{\gamma}(t_{0})^{2/L}(t-t_{0}),$ (33) $$

or, by a change of variables,

$$ $\int_{1/\mathcal{L}(t_{0})}^{1/\mathcal{L}({t})}\left(\log u\right)^{2/L-2}du\geq L^{2}\tilde{\gamma}(t_{0})^{2/L}(t-t_{0}).$ (34) $$

The RHS diverges to infinity as $t\to\infty$, hence so does the LHS, which can only happen if $\mathcal{L}\to 0$. In order for $\mathcal{L}(\bm{\theta}_{t})=\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}=\sum_{i=1}^{m}e^{-y_{i}\|\bm{\theta}_{t}\|^{L}f\left(\mathbf{x}_{i};\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}\right)}$ to go to zero, it must be $\|\bm{\theta}_{t}\|\to\infty$.
∎

The following Lemma quantifies the connection between soft and hard margin.

###### Lemma A.7 .

For any $\bm{\theta}$, it holds:

$$ $\frac{\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta})}{\|\bm{\theta}\|^{L}}-\log m\leq\tilde{\gamma}\leq\frac{\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta})}{\|\bm{\theta}\|^{L}}.$ (35) $$

###### Proof.

Follows from:

$$ $e^{-\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta})}\leq\mathcal{L}(\bm{\theta})\leq me^{-\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta})}.$ (36) $$

∎

The last part of the proof consists of characterizing the (directional) convergence of the iterates in relation to stationary points of the following optimization problem (re-introduced here for convenience):

$$ $\displaystyle\begin{split}&\min_{\bm{\theta}\in\mathbb{R}^{p}}\frac{1}{2}\|\bm{\theta}\|^{2}\\ \text{s.t. }&y_{i}f(\mathbf{x}_{i};\bm{\theta})\geq 1,\;\forall i\in[m].\end{split}$ (37) $$

Under some regularity assumptions, the KKT conditions (Definition [3.3](#S3.Thmtheorem3)) become necessary for global optimality (yet, not sufficient):

###### Definition A.8 .

We say that a feasible point of Equation [37](#A1.E37) satisfies the Mangasarian-Fromovitz Constraint Qualifications if there exists $\mathbf{v}\in\mathbb{R}^{p}$ such that for all $i\in[m]$ with $1-y_{i}f(\mathbf{x}_{i};\bm{\theta})=0$ and for all $\mathbf{h}\in\partial\left(1-y_{i}f(\mathbf{x}_{i};\bm{\theta})\right)$, it holds:

$$ $\left\langle\mathbf{v},\mathbf{h}\right\rangle>0.$ (38) $$

Our proof uses the following relaxed notion of stationarity.

###### Definition A.9 ( $(d,\epsilon,\delta)$ - approximate KKT point) .

Let $d:\mathbb{R}^{p}\times\mathbb{R}^{p}\to\mathbb{R}_{+}$. A feasible point $\bm{\theta}$ of ([37](#A1.E37)) is called an $(d,\epsilon,\delta)-$approximate KKT point if there exist $\lambda_{1},\ldots,\lambda_{m}\geq 0$, $\mathbf{h}_{i}\in\partial f(\mathbf{x}_{i};\bm{\theta})$ and $\mathbf{k}\in\partial\frac{1}{2}\|\bm{\theta}\|^{2}$ such that:

- 1.
$d\left(\sum_{i=1}^{m}\lambda_{i}y_{i}\mathbf{h}_{i},\mathbf{k}\right)\leq\epsilon$
- 2.
$\sum_{i=1}^{m}\lambda_{i}(y_{i}f(\mathbf{x}_{i};\bm{\theta})-1)\leq\delta$.

We first show that we can always construct a feasible point of Equation [37](#A1.E37) from a scaled version of $\bm{\theta}_{t}$.

###### Lemma A.10 .

For any $t>0$, $\tilde{\bm{\theta}}_{t}=\frac{\bm{\theta}_{t}}{\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})\right)^{\frac{1}{L}}}$ is a feasible point of Equation [37](#A1.E37).

###### Proof.

From the homogeneity of $f$, we have:

$$ $\begin{split}y_{i}f(\mathbf{x}_{i};\tilde{\bm{\theta}_{t}})&=y_{i}f\left(\mathbf{x}_{i};\frac{\bm{\theta}_{t}}{\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})\right)^{\frac{1}{L}}}\right)=\frac{y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}{\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})}\geq 1\end{split}$ (39) $$

for all $i\in[m]$. So $\tilde{\bm{\theta}}_{t}$ is a feasible point of Equation [37](#A1.E37).
∎

The next Lemma shows that Problem [37](#A1.E37) satisfies the Mangasarian-Fromovitz Constraint Qualifications:

###### Lemma A.11 .

Problem [37](#A1.E37) satisfies the Mangasarian-Fromovitz Constraint Qualifications at every feasible point $\bm{\theta}$.

###### Proof.

Let $\mathbf{h}_{i}\in\partial(1-y_{i}f(\mathbf{x}_{i};\bm{\theta}))$ and $\mathbf{v}=-\bm{\theta}$, then for all $i\in[m]$ satisfying $y_{i}f(\mathbf{x}_{i};\bm{\theta})=1$, we have from Euler’s theorem for homogeneous functions:

$$ $\left\langle\mathbf{v},\mathbf{h}_{i}\right\rangle=Ly_{i}f(\mathbf{x}_{i};\bm{\theta})=L>0.$ (40) $$

∎

Our proof uses core ideas from the theory of conjugate functions and Fenchel’s duality.

###### Definition A.12 (Convex conjugate) .

Let $\psi:\mathbb{R}^{p}\to\mathbb{R}$.
We denote by $\psi^{\star}(\cdot)$ the convex conjugate of $\psi(\cdot)$:

$$ $\psi^{\star}(\bm{\omega})=\sup_{\bm{\theta}\in\mathbb{R}^{p}}\{\left\langle\bm{\omega},\bm{\theta}\right\rangle-\psi(\bm{\theta})\}.$ (41) $$

We will make use of the following properties of conjugate functions.

###### Proposition A.13 .

(Conjugate subgradient theorem - Theorem 23.5 in Rockafellar, (), Theorem 4.20 in Beck, ())
Let $\psi:\mathbb{R}^{p}\to\mathbb{R}$ be convex and closed. For any $\bm{\theta}^{\star}\in\partial\psi^{\star}(\bm{\theta})$, it holds $\partial\psi\left(\bm{\theta}^{\star}\right)\ni\bm{\theta}$.

###### Lemma A.14 .

(Fenchel-Young inequality) (Fenchel,, )
For any $\psi:\mathbb{R}^{p}\to\mathbb{R}$ and $\bm{\omega},\bm{\theta}\in\mathbb{R}^{p}$, it holds:

$$ $\left\langle\bm{\theta},\bm{\omega}\right\rangle\leq\psi(\bm{\theta})+\psi^{\star}(\bm{\omega}).$ (42) $$

Next, we show that the scaled version of the iterates from Lemma [A.10](#A1.Thmtheorem10), $\tilde{\bm{\theta}_{t}}$, is an $\left(D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}_{t}},\epsilon(t),\delta(t)\right)$-approximate KKT point for $\epsilon(t)$ and $\delta(t)$ that vanish as $t$ increases.

###### Proposition A.15 .

For any $t>t_{0}$, $\tilde{\bm{\theta}}_{t}=\frac{\bm{\theta}_{t}}{\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})\right)^{\frac{1}{L}}}$ is an $\left(D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}_{t}},\epsilon(t),\delta(t)\right)$-approximate KKT point of Equation [37](#A1.E37), with:

$$ $\begin{split}\epsilon(t)&=\frac{1}{\tilde{\gamma}(t_{0})^{\frac{2}{L}}}\left(1-\left\langle\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|},\frac{-\mathbf{g}_{t}^{\star}}{\|\mathbf{g}_{t}^{\star}\|_{\star}}\right\rangle\right),\\ \delta(t)&=\frac{m}{eL\tilde{\gamma}(t_{0})^{\frac{2}{L}}\log\frac{1}{\mathcal{L}}},\end{split}$ (43) $$

with $\mathbf{g}_{t}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t})}\|\mathbf{u}\|_{\star}$.

###### Proof.

We suppress the dependence of the loss and the iterates from the time index $t$, when it is obvious from the context. From Lemma [A.10](#A1.Thmtheorem10), we know that $\tilde{\bm{\theta}}$ is a feasible point. To simplify the notation, let $q_{\text{min}}=\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta})$. We will denote by
$\tilde{\mathbf{k}}\in\partial\frac{1}{2}\|\tilde{\bm{\theta}}\|^{2}$ any subgradient of
$\frac{1}{2}\lVert\cdot\rVert^{2}$
at $\tilde{\bm{\theta}}$. Let, as previously stated, $\mathbf{g}_{t}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t})}\|\mathbf{u}\|_{\star}$ and $\mathbf{h}_{i}^{\star}\in\partial f(\mathbf{x}_{i};\bm{\theta}),i\in[m],$ such that $\mathbf{g}_{t}^{\star}=-\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}y_{i}\mathbf{h}_{i}^{\star}$ (whose existence is guaranteed from chain rule - Theorem [A.1](#A1.Thmtheorem1)). Finally, we define $\tilde{\mathbf{h}}_{i}^{\star}=q_{\text{min}}^{\frac{1}{L}-1}\mathbf{h}_{i}^{\star}$ for all $i\in[m]$, for which it holds: $\tilde{\mathbf{h}}_{i}^{\star}\in\partial f(\mathbf{x}_{i};\tilde{\bm{\theta}})$ from Theorem B.2(a) in Lyu and Li, ().

Given all these definitions, we set $\lambda_{i}=\frac{\|\bm{\theta}\|}{\|\mathbf{g}_{t}^{\star}\|_{\star}}q_{\text{min}}^{1-\frac{2}{L}}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}\geq 0$. The dual vector from the $(d,\epsilon,\delta)$-stationarity definition can be simplified to:

$$ $\begin{split}\sum_{i=1}^{m}\lambda_{i}y_{i}\tilde{\mathbf{h}}_{i}^{\star}&=\sum_{i=1}^{m}\lambda_{i}q_{\text{min}}^{\frac{1}{L}-1}y_{i}\mathbf{h}_{i}^{\star}\;\;\;\;\;(\text{Thm B.2(a) in \cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{LyLi20}{\@@citephrase{(}}{\@@citephrase{)}}}})\\ &=\frac{\|\bm{\theta}\|}{q_{\text{min}}^{\frac{1}{L}}\|\mathbf{g}_{t}^{\star}\|_{\star}}\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}y_{i}\mathbf{h}_{i}\\ &=-\frac{\|\bm{\theta}\|\mathbf{g}_{t}^{\star}}{q_{\text{min}}^{\frac{1}{L}}\|\mathbf{g}_{t}^{\star}\|_{\star}},\end{split}$ (44) $$

which is a scaled version of the (minimum norm) subderivative of the loss.

Let $\psi(\bm{\theta})=\frac{1}{2}\|\bm{\theta}\|_{\star}^{2}$ be the potential function that we shall use in order to define our divergence. For this specific $\psi$, it holds: $\psi^{\star}(\bm{\omega})=\frac{1}{2}\|\bm{\omega}\|^{2}$ (see for instance Example 3.27 in Boyd and Vandenberghe, () for a derivation).
Recall that in the definition of $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\mathbf{m}}$ (Equation [12](#S3.E12)) there is an extra choice that we have to make; the one of the subderivative $\mathbf{m}$.
In what follows, we will specifically measure “distance” between $\sum_{i=1}^{m}\lambda_{i}y_{i}\tilde{\mathbf{h}}_{i}$ and $\tilde{\mathbf{k}}$ using $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}}(\cdot,\cdot)$, i.e. by picking $\mathbf{m}=\tilde{\bm{\theta}}$. This is possible, since from Proposition [A.13](#A1.Thmtheorem13) it holds that $\tilde{\bm{\theta}}\in\partial\frac{1}{2}\|\tilde{\mathbf{k}}\|_{\star}^{2}$. Finally, let $\mathbf{r}\in\partial\|\tilde{\bm{\theta}}\|$ be the subgradient of $\lVert\cdot\rVert$ that stems from the chain rule of $\frac{1}{2}\lVert\cdot\rVert^{2}$ evaluated at $\tilde{\bm{\theta}}$.
We calculate the divergence between the two vectors:

$$ $\begin{split}D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}}&\left(\sum_{i=1}^{m}\lambda_{i}y_{i}\tilde{\mathbf{h}}_{i},\tilde{\mathbf{k}}\right)\\ &=\frac{1}{2}\left\lVert-\frac{\|\bm{\theta}\|\mathbf{g}_{t}^{\star}}{q_{\text{min}}^{\frac{1}{L}}\|\mathbf{g}_{t}^{\star}\|_{\star}}\right\rVert_{\star}^{2}-\frac{1}{2}\left\lVert\tilde{\mathbf{k}}\right\rVert_{\star}^{2}-\left\langle\frac{\bm{\theta}}{q_{\text{min}}^{\frac{1}{L}}},-\frac{\|\bm{\theta}\|\mathbf{g}_{t}^{\star}}{q_{\text{min}}^{\frac{1}{L}}\|\mathbf{g}_{t}^{\star}\|_{\star}}-\tilde{\mathbf{k}}\right\rangle\\ &=\frac{1}{2}\frac{\|\bm{\theta}\|^{2}}{q_{\text{min}}^{\frac{2}{L}}}-\frac{1}{2}\left\lVert\|\tilde{\bm{\theta}}\|\mathbf{r}\right\rVert_{\star}^{2}-\left\langle\frac{\bm{\theta}}{q_{\text{min}}^{\frac{1}{L}}},\frac{-\|\bm{\theta}\|\mathbf{g}_{t}^{\star}}{q_{\text{min}}^{\frac{1}{L}}\|\mathbf{g}_{t}^{\star}\|_{\star}}-\|\tilde{\bm{\theta}}\|\mathbf{r}\right\rangle\;\;\;\;\;(\text{Chain rule})\\ &=\frac{\|\bm{\theta}\|^{2}}{q_{\text{min}}^{\frac{2}{L}}}\left(\frac{1}{2}-\frac{1}{2}\left\lVert\mathbf{r}\right\rVert_{\star}^{2}-\left\langle\frac{\bm{\theta}}{\|\bm{\theta}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle+\left\langle\frac{\bm{\theta}}{\|\bm{\theta}\|},\mathbf{r}\right\rangle\right)\\ &\leq\frac{\|\bm{\theta}\|^{2}}{q_{\text{min}}^{\frac{2}{L}}}\left(\frac{1}{2}-\frac{1}{2}\left\lVert\mathbf{r}\right\rVert_{\star}^{2}-\left\langle\frac{\bm{\theta}}{\|\bm{\theta}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle+\frac{1}{2}\left\|\frac{\bm{\theta}}{\|\bm{\theta}\|}\right\rVert^{2}+\frac{1}{2}\left\lVert\mathbf{r}\right\rVert_{\star}^{2}\right)\;\;\;\;\;(\text{Equation~{}\ref{eq:fenchel_young}})\\ &=\frac{\|\bm{\theta}\|^{2}}{q_{\text{min}}^{\frac{2}{L}}}\left(1-\left\langle\frac{\bm{\theta}}{\|\bm{\theta}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle\right)\\ &\leq\frac{1}{\tilde{\gamma}^{\frac{2}{L}}}\left(1-\left\langle\frac{\bm{\theta}}{\|\bm{\theta}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle\right)\leq\frac{1}{\tilde{\gamma}(t_{0})^{\frac{2}{L}}}\left(1-\left\langle\frac{\bm{\theta}}{\|\bm{\theta}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle\right),\end{split}$ (45) $$

where the last 2 inequalities follow from the relation between smooth and hard margin (Lemma [A.7](#A1.Thmtheorem7)), and the monotonicity of the former.
For the second condition of an approximate KKT point, we have:

$$ $\begin{split}\sum_{i=1}^{m}\lambda_{i}\left(y_{i}f(\mathbf{x}_{i};\tilde{\bm{\theta})}-1\right)&=\frac{\|\bm{\theta}\|}{\|\mathbf{g}_{t}^{\star}\|_{\star}}\sum_{i=1}^{m}q_{\text{min}}^{1-\frac{2}{L}}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}\left(\frac{y_{i}f(\mathbf{x}_{i};\bm{\theta})}{q_{\text{min}}}-1\right)\\ &=\frac{\|\bm{\theta}\|}{q_{\text{min}}^{\frac{2}{L}}\|\mathbf{g}_{t}^{\star}\|_{\star}}\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}\left(y_{i}f(\mathbf{x}_{i};\bm{\theta})-q_{\text{min}}\right).\end{split}$ (46) $$

From eq. Equation [30](#A1.E30) and Equation [28](#A1.E28), we can lower bound the dual norm of the subderivate:

$$ $\|\mathbf{g}_{t}^{\star}\|_{\star}\geq\frac{L}{\|\bm{\theta}\|}\mathcal{L}\log\frac{1}{\mathcal{L}}\geq\frac{L}{\|\bm{\theta}\|}e^{-q_{\text{min}}}\log\frac{1}{\mathcal{L}}.$ (47) $$

By plugging in back to eq. Equation [46](#A1.E46), we obtain

$$ $\begin{split}\sum_{i=1}^{m}\lambda_{i}\left(y_{i}f(\mathbf{x}_{i};\tilde{\bm{\theta})}-1\right)&\leq\frac{\|\bm{\theta}\|^{2}}{q_{\text{min}}^{\frac{2}{L}}Le^{-q_{\text{min}}}\log\frac{1}{\mathcal{L}}}\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}\left(y_{i}f(\mathbf{x}_{i};\bm{\theta})-q_{\text{min}}\right)\\ &=\frac{\|\bm{\theta}\|^{2}}{q_{\text{min}}^{\frac{2}{L}}L\log\frac{1}{\mathcal{L}}}\sum_{i=1}^{m}e^{-\left(y_{i}f(\mathbf{x}_{i};\bm{\theta})-q_{\text{min}}\right)}\left(y_{i}f(\mathbf{x}_{i};\bm{\theta})-q_{\text{min}}\right)\\ &\leq\frac{1}{\tilde{\gamma}(t_{0})^{\frac{2}{L}}L\log\frac{1}{\mathcal{L}}}\sum_{i=1}^{m}e^{-\left(y_{i}f(\mathbf{x}_{i};\bm{\theta})-q_{\text{min}}\right)}\left(y_{i}f(\mathbf{x}_{i};\bm{\theta})-q_{\text{min}}\right)\;\;\;\;\;(\text{Lemmata \ref{lem:smooth_hard_margin}, \ref{thm:margin_monotonicity}})\\ &\leq\frac{m}{e\tilde{\gamma}(t_{0})^{\frac{2}{L}}L\log\frac{1}{\mathcal{L}}},\end{split}$ (48) $$

since the function $u\mapsto e^{-u}u,u>0$ has a maximum value of $e^{-1}$.
∎

Before we proceed with the main result, we state and prove two useful Lemmata. The first one lower bounds the alignment between normalized iterates and normalized loss gradients. This Lemma is key for showing that the alignment goes to 1 as $t\to\infty$.

###### Lemma A.16 .

For all $t_{2}>t_{1}\geq t_{0}$, there exists $t_{\star}\in(t_{1},t_{2})$ such that:

$$ $\left(\frac{1}{\left\langle\frac{\bm{\theta}_{t_{\star}}}{\|\bm{\theta}_{t_{\star}}\|},\frac{-\mathbf{g}_{t_{\star}}^{\star}}{\left\lVert\mathbf{g}_{t_{\star}}^{\star}\right\rVert_{\star}}\right\rangle}-1\right)\leq\frac{1}{L}\frac{\log\frac{\tilde{\gamma}(t_{2})}{\tilde{\gamma}(t_{1})}}{\displaystyle\int_{t_{1}}^{t_{2}}\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}dt},$ (49) $$

for all $\mathbf{g}_{t_{\star}}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t_{\star}})}\|\mathbf{u}\|_{\star}$

###### Proof.

From Lemma [A.5](#A1.Thmtheorem5), we have for all $\mathbf{g}_{t}^{\star}\in\operatorname*{\arg\!\min}_{\mathbf{u}\in\partial\mathcal{L}(\bm{\theta}_{t})}\|\mathbf{u}\|_{\star}$:

$$ $\begin{split}\frac{d\log\tilde{\gamma}}{dt}&\geq L\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert^{2}\left(\frac{1}{\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle}-\frac{1}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}\right)\\ &=L\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}\left(\frac{1}{\left\langle\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|},\frac{-\mathbf{g}_{t}^{\star}(\bm{\theta}_{t})}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle}-1\right).\end{split}$ (50) $$

We then integrate the two sides from $t_{1}$ to $t_{2}>t_{1}>t_{0}$:

$$ $\int_{t_{1}}^{t_{2}}\left(\frac{1}{\left\langle\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle}-1\right)\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}dt\leq\frac{1}{L}\log\frac{\tilde{\gamma}(t_{2})}{\tilde{\gamma}(t_{1})}.$ (51) $$

The desired existential statement follows from a proof by contradiction.
∎

Next, we bound the rate of change of the normalized iterates.

###### Lemma A.17 .

For any $t>0$, it holds:

$$ $\left\lVert\frac{d\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}}{dt}\right\rVert\leq 2\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}.$ (52) $$

###### Proof.

The rate of change of the normalized iterates can be written as follows:

$$ $\begin{split}\frac{d\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}}{dt}&=\frac{1}{\|\bm{\theta}_{t}\|}\frac{d\bm{\theta}_{t}}{dt}+\bm{\theta}_{t}\left(-\frac{1}{\|\bm{\theta}_{t}\|^{2}}\frac{d\|\bm{\theta}_{t}\|}{dt}\right)\\ &=\frac{1}{\|\bm{\theta}_{t}\|}\frac{d\bm{\theta}_{t}}{dt}+\bm{\theta}_{t}\left(-\frac{1}{\|\bm{\theta}_{t}\|^{2}}\left\langle\mathbf{n}_{t},\frac{d\bm{\theta}_{t}}{dt}\right\rangle\right),\;\;\;\;\;(\text{Chain rule})\end{split}$ (53) $$

where $\mathbf{n}_{t}\in\partial\|\bm{\theta}_{t}\|$. So, by the triangle inequality, its norm is bounded by:

$$ $\begin{split}\left\lVert\frac{d\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}}{dt}\right\rVert&\leq\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}+\frac{1}{\|\bm{\theta}_{t}\|}\left|\left\langle\mathbf{n}_{t},\frac{d\bm{\theta}_{t}}{dt}\right\rangle\right|\\ &\leq 2\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}.\;\;\;\;\;(\text{definition of dual norm and $\|\mathbf{n}_{t}\|_{\star}\leq 1$})\end{split}$ (54) $$

∎

We are, now, ready to state and prove our main result.

###### Theorem A.18 .

For steepest flow (eq. Equation [3](#S2.E3)) on the exponential loss, under assumptions [A1](#S2.I1.i1), [A2](#S2.I1.i2), [A3](#S2.I1.i3), any limit point $\bar{\bm{\theta}}$ of $\left\{\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}\right\}_{t\geq 0}$ is along the direction of a $D_{\frac{1}{2}\lVert\cdot\rVert_{\star}^{2}}^{\tilde{\bm{\theta}}}$-generalized KKT point, $\tilde{\bm{\theta}}:=\frac{\bar{\bm{\theta}}}{\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bar{\bm{\theta}})\right)^{\frac{1}{L}}}$, of the following optimization problem:

$$ $\displaystyle\begin{split}&\min_{\bm{\theta}\in\mathbb{R}^{p}}\frac{1}{2}\|\bm{\theta}\|^{2}\\ \text{s.t. }&y_{i}f(\mathbf{x}_{i};\bm{\theta})\geq 1,\;\forall i\in[m].\end{split}$ (55) $$

###### Proof.

Our strategy will be to consider any limit point $\bar{\bm{\theta}}$ and construct $\left(D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}_{t}},\epsilon(t),\delta(t)\right)$-approximate KKT points that converge to it, with vanishing $\epsilon(t),\delta(t)$.

Let $\epsilon_{m}=\frac{1}{m}$ for any $m>0$. We construct a sequence $\{t_{m}\}_{m\geq 0}$, by induction, in the following sense. Suppose $t_{1}<\ldots<t_{m-1}$ have been constructed already. Since $\bar{\bm{\theta}}$ is a limit point of the normalized iterates and $\log\tilde{\gamma}_{t}\to\log\tilde{\gamma}_{\infty}<\infty$ (as $\tilde{\gamma}_{t}$ is non-decreasing and bounded from above), there exists $s_{m}>t_{m-1}$ such that:

$$ $\left\lVert\frac{\bm{\theta}_{s_{m}}}{\|\bm{\theta}_{s_{m}}\|}-\bar{\bm{\theta}}\right\rVert\leq\epsilon_{m}=\frac{1}{m}\;\;\;\;\;\;\text{and}\;\;\;\;\;\;\frac{1}{L}\log\frac{\tilde{\gamma}_{\infty}}{\tilde{\gamma}_{s_{m}}}\leq\epsilon_{m}^{2}=\frac{1}{m^{2}}.$ (56) $$

Since $\frac{d\log\|\bm{\theta}_{t}\|}{dt}\leq\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}$, we have that $\lim_{t\to\infty}\displaystyle\int_{t_{A}}^{t}\frac{\left\lVert\frac{d\bm{\theta}_{t^{\prime}}}{d{t^{\prime}}}\right\rVert}{\|\bm{\theta}_{t^{\prime}}\|}dt^{\prime}=\infty$ for all $t_{A}>0$. Thus, there exists $s_{m}^{\prime}>s_{m}$ such that $\displaystyle\int_{s_{m}}^{s_{m}^{\prime}}\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}dt=\frac{1}{m}$.
Now, from Lemma [A.16](#A1.Thmtheorem16), we know there exists $t_{\star}\in(s_{m},s_{m}^{\prime})$ with:

$$ $\left(\frac{1}{\left\langle\frac{\bm{\theta}_{t_{\star}}}{\|\bm{\theta}_{t_{\star}}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle}-1\right)\leq\frac{1}{L}\frac{\log\frac{\tilde{\gamma}_{s_{m}^{\prime}}}{\tilde{\gamma}_{s_{m}}}}{\displaystyle\int_{s_{m}}^{s_{m}^{\prime}}\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}dt}\leq\frac{\frac{1}{m^{2}}}{\frac{1}{m}}=\frac{1}{m},$ (57) $$

which implies $\left\langle\frac{\bm{\theta}_{t_{\star}}}{\|\bm{\theta}_{t_{\star}}\|},\frac{-\mathbf{g}_{t}^{\star}}{\left\lVert\mathbf{g}_{t}^{\star}\right\rVert_{\star}}\right\rangle\geq\frac{1}{1+\frac{1}{m}}\to 1$ as $m\to\infty$.
On the other hand, for the normalized iterates we have:

$$ $\left\lVert\frac{\bm{\theta}_{t_{\star}}}{\|\bm{\theta}_{t_{\star}}\|}-\bar{\bm{\theta}}\right\rVert\leq\left\lVert\frac{\bm{\theta}_{t_{\star}}}{\|\bm{\theta}_{t_{\star}}\|}-\frac{\bm{\theta}_{s_{m}}}{\|\bm{\theta}_{s_{m}}\|}\right\rVert+\left\lVert\frac{\bm{\theta}_{s_{m}}}{\|\bm{\theta}_{s_{m}}\|}-\bar{\bm{\theta}}\right\rVert\stackrel{{\scriptstyle\text{eq.~{}Equation~{}\ref{eq:final_bounds}}}}{{\leq}}\left\lVert\frac{\bm{\theta}_{t_{\star}}}{\|\bm{\theta}_{t_{\star}}\|}-\frac{\bm{\theta}_{s_{m}}}{\|\bm{\theta}_{s_{m}}\|}\right\rVert+\frac{1}{m}.$ (58) $$

To deal with the first term, we can leverage Lemma [A.17](#A1.Thmtheorem17) which bounds the rate of change of the normalized iterates:

$$ $\left\lVert\frac{\bm{\theta}_{t_{\star}}}{\|\bm{\theta}_{t_{\star}}\|}-\bar{\bm{\theta}}\right\rVert\leq 2\displaystyle\int_{s_{m}}^{t_{\star}}\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}dt+\frac{1}{m}\leq 2\displaystyle\int_{s_{m}}^{s_{m}^{\prime}}\frac{\left\lVert\frac{d\bm{\theta}_{t}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}dt+\frac{1}{m}=\frac{3}{m}\to 0.$ (59) $$

Hence, by picking $t_{m}$ as $t_{\star}$, we constructed a time sequence such that, for any limit point $\bar{\bm{\theta}}$, $\frac{\bm{\theta}_{t_{m}}}{\|\bm{\theta}_{t_{m}}\|}\to\bar{\bm{\theta}}$ and also $\left\langle\frac{\bm{\theta}_{t_{m}}}{\|\bm{\theta}_{t_{m}}\|},\frac{-\mathbf{g}_{t}^{\star}(\bm{\theta}_{t_{m}})}{\left\lVert\mathbf{g}_{t}^{\star}(\bm{\theta}_{t_{m}})\right\rVert_{\star}}\right\rangle\to 1$.

Then, from Proposition [A.15](#A1.Thmtheorem15), we know that $\tilde{\bm{\theta}}_{t_{m}}=\frac{\bm{\theta}_{t_{m}}}{\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t_{m}})\right)^{\frac{1}{L}}}$ is an $\left(D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}_{t}},\epsilon(t_{m}),\delta(t_{m})\right)$-approximate KKT point of Equation [37](#A1.E37). But $\epsilon(t_{m})\to 0$ (since the alignment goes to 1) and $\delta(t_{m})\to 0$ as the loss goes to zero (Lemma [A.6](#A1.Thmtheorem6)), thus the sequence satisfies the conditions of Proposition [A.21](#A1.Thmtheorem21), which shows that the limit point of the sequence is a generalized KKT point. This concludes the proof of our claim.
∎

While the previous result is not strong enough to guarantee convergence to an approximate KKT point for a general algorithm norm $\lVert\cdot\rVert$, it immediately implies it in the case of a smooth norm. The proof relies on a fundamental relationship between smoothness of a function and strong convexity of its convex conjugate.

###### Proposition A.19 .

(Conjugate Correspondence Theorem - Thm. 5.26 in Beck, ())
Let $\sigma>0$. If $\psi$ is a $\frac{1}{\sigma}$-smooth convex function, then its conjugate $\psi^{\star}$ is $\sigma$-strongly convex.

We can prove the following corollary for a special class of steepest flows.

###### Corollary A.20 .

For steepest flow (eq. Equation [3](#S2.E3)) with respect to a norm $\lVert\cdot\rVert$, whose square is a smooth function, on the exponential loss, under assumptions [A1](#S2.I1.i1), [A2](#S2.I1.i2), [A3](#S2.I1.i3), any limit point $\bar{\bm{\theta}}$ of $\left\{\frac{\bm{\theta}_{t}}{\|\bm{\theta}_{t}\|}\right\}_{t\geq 0}$ is along the direction of a KKT point of optimization problem Equation [37](#A1.E37).

###### Proof.

From Proposition [A.19](#A1.Thmtheorem19), if $\frac{1}{2}\lVert\cdot\rVert^{2}$ is $\frac{1}{\sigma}$-smooth w.r.t. $\lVert\cdot\rVert$, then the function $\frac{1}{2}\lVert\cdot\rVert_{\star}^{2}$ is $\sigma$-strongly convex w.r.t. $\lVert\cdot\rVert_{\star}$. Thus, the function $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\bm{\theta}}$ is defined with respect to a strongly convex function and it becomes a proper Bregman divergence. Hence, from Theorem 5.24 in Beck, (), for $\tilde{\mathbf{h}}_{i}^{\star}=q_{\text{min}}^{\frac{1}{L}-1}\mathbf{h}_{i}^{\star}$, where $\tilde{\mathbf{h}}_{i}^{\star}\in\partial f(\mathbf{x}_{i};\tilde{\bm{\theta}}),i\in[m]$ such that $\mathbf{g}_{t}^{\star}=-\sum_{i=1}^{m}e^{-y_{i}f(\mathbf{x}_{i};\bm{\theta})}y_{i}\mathbf{h}_{i}^{\star}$ and $\tilde{\mathbf{k}}\in\partial\frac{1}{2}\|\tilde{\bm{\theta}}\|^{2}$, it holds:

$$ $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}}\left(\sum_{i=1}^{m}\lambda_{i}y_{i}\tilde{\mathbf{h}}_{i}^{\star},\tilde{\mathbf{k}}\right)\geq\sigma\left\lVert\sum_{i=1}^{m}\lambda_{i}y_{i}\tilde{\mathbf{h}}_{i}^{\star}-\tilde{\mathbf{k}}\right\rVert_{\star}.$ (60) $$

In other words, if $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\tilde{\bm{\theta}}}(\bm{\alpha},\bm{\beta})$ is 0, so is the difference $\bm{\alpha}-\bm{b}$ for any $\bm{\alpha},\bm{b}$.
As a result, and from the equivalence of the norms, the sequence $\tilde{\bm{\theta}}_{t_{m}}=\frac{\bm{\theta}_{t_{m}}}{\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t_{m}})\right)^{\frac{1}{L}}}$ from the proof of Theorem [A.18](#A1.Thmtheorem18), induces a sequence of $(\epsilon(t_{m}),\delta(t_{m}))$-approximate KKT points, which converges to a KKT point of Equation [37](#A1.E37). By Theorem C.4 in Lyu and Li, () (which is itself based on a result due to Dutta et al., ()), we get that $\frac{\bar{\bm{\theta}}}{\left(\min_{i\in[m]}y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})\right)^{\frac{1}{L}}}$ is a KKT point of Equation [37](#A1.E37).
∎

The following technical result was used in the proof of Theorem [A.18](#A1.Thmtheorem18).

###### Proposition A.21 .

Let (MM) be the following optimization problem:

$$ $\displaystyle\begin{split}&\min_{\bm{\theta}\in\mathbb{R}^{p}}\frac{1}{2}\|\bm{\theta}\|^{2}\\ \text{s.t. }&y_{i}f(\mathbf{x}_{i};\bm{\theta})\geq 1,\;\forall i\in[m].\end{split}$ (MM) $$

Let $\left\{\bm{\theta}_{t}\right\}_{t\geq 0}$ be a sequence of feasible, $(d,\epsilon_{t},\delta_{t})$-approximate KKT points, with $d:=D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\bm{\theta}_{t}}$ with $\epsilon_{t}\downarrow 0,\delta_{t}\downarrow 0$ and $\bm{\theta}_{t}\to\bar{\bm{\theta}}$. Assume that the Mangasarian-Fromovitz- Constraint Qualifications hold at $\bar{\bm{\theta}}$. Then, $\bar{\bm{\theta}}$ is a $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\bar{\bm{\theta}}}$-generalized KKT point of (MM).

###### Proof.

Our proof closely follows the proof of Theorem 3.6 in (Dutta et al.,, ), which is the direct analog for $(\epsilon,\delta)$-approximate KKT points.

By the definition of the $(d,\epsilon_{t},\delta_{t})$ stationarity, for each $t>0$, there exist $\mathbf{h}_{i}^{t}\in\partial f(\mathbf{x}_{i};\bm{\theta}_{t}),i\in[m],\mathbf{k}^{t}\in\partial\frac{1}{2}\|\bm{\theta}_{t}\|^{2}$ and $\lambda_{i}^{t}\geq 0,i\in[m]$ such that:

- (i)
$D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\bm{\theta}_{t}}\left(\sum_{i=1}^{m}\lambda_{i}^{t}y_{i}\mathbf{h}_{i}^{t},\mathbf{k}^{t}\right)\leq\epsilon_{t}$.
- (ii)
$\sum_{i=1}^{m}\lambda_{i}^{t}\left(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})-1\right)\leq\delta_{t}$.

We will show that the sequence $\{\bm{\lambda}^{t}\}_{t\geq 0}$ is bounded. Assume on the contrary that is not. Consider $\hat{\bm{\lambda}}=\frac{\bm{\lambda}^{t}}{\|\bm{\lambda}^{t}\|}$, which is bounded and wlog, it is: $\hat{\bm{\lambda}}\to\tilde{\bm{\lambda}}$ with $\|\hat{\bm{\lambda}}\|=1$. Note that the sequences $\{\mathbf{h}_{i}^{t}\},\{\mathbf{k}^{t}\}$ are bounded, as elements of a subdifferential, by the Lipschitz constant of the corresponding function. Hence, they also converge to, say, $\bar{\mathbf{h}}_{i}$ for all $i\in[m]$ and $\bar{\mathbf{k}}$, respectively.
From condition (i), we have:

$$ $\begin{split}\frac{1}{\|\bm{\lambda}^{t}\|^{2}}D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\bm{\theta}_{t}}\left(\sum_{i=1}^{m}\lambda_{i}^{t}y_{i}\mathbf{h}_{i}^{t},\mathbf{k}^{t}\right)\leq\frac{\epsilon_{t}}{\|\bm{\lambda}_{t}\|^{2}},\end{split}$ (61) $$

or

$$ $\frac{1}{2}\left\lVert\sum_{i=1}^{m}\frac{\lambda_{i}^{t}}{\|\bm{\lambda}^{t}\|}y_{i}\mathbf{h}_{i}^{t}\right\rVert^{2}_{\star}-\frac{1}{2}\left\lVert\frac{\mathbf{k}^{t}}{\|\bm{\lambda}^{t}\|}\right\rVert^{2}_{\star}-\left\langle\frac{\bm{\theta}_{t}}{\|\bm{\lambda}^{t}\|},\sum_{i=1}^{m}\frac{\lambda_{i}^{t}}{\|\bm{\lambda}\|}y_{i}\mathbf{h}_{i}^{t}-\frac{\mathbf{k}^{t}}{\|\bm{\lambda}\|}\right\rangle\leq\frac{\epsilon_{t}}{\|\bm{\lambda}_{t}\|^{2}},$ (62) $$

hence, by taking $t\to\infty$, we get:

$$ $\frac{1}{2}\left\lVert\sum_{i=1}^{m}\tilde{\lambda}_{i}y_{i}\bar{\mathbf{h}}_{i}\right\rVert_{\star}^{2}\leq 0,$ (63) $$

which implies that there exists $\tilde{\bm{\lambda}}\neq\bm{0}$ such that $\sum_{i=1}^{m}\tilde{\lambda}_{i}y_{i}\bar{\mathbf{h}}_{i}=\bm{0}$, where recall $\bar{\mathbf{h}}_{i}\in\partial f(\mathbf{x}_{i};\bar{\bm{\theta}})$. An existence of such a vector is prohibited by the Mangasarian-Fromovitz-Constraint Qualifications which hold at $\bar{\bm{\theta}}$. Thus, $\{\bm{\lambda}^{t}\}_{t\geq 0}$ is bounded and $\bm{\lambda}^{t}\to\bar{\bm{\lambda}}$ for some $\bar{\bm{\lambda}}\in\mathbb{R}^{m}$. Hence, by taking the limit $t\to\infty$, we have:

$$ $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\bar{\bm{\theta}}}\left(\sum_{i=1}^{m}\bar{\lambda}_{i}y_{i}\bar{\mathbf{h}}_{i},\bar{\mathbf{k}}\right)\leq 0,$ (64) $$

where $\bar{\mathbf{h}}_{i}\in\partial f(\mathbf{x}_{i};\bar{\bm{\theta}}),i\in[m]$ and $\bar{\mathbf{k}}\in\partial\frac{1}{2}\|\bar{\bm{\theta}}\|$.
From (ii), we obtain $\sum_{i=1}^{m}\bar{\lambda}_{i}\left(y_{i}f(\mathbf{x}_{i};\bar{\bm{\theta}})-1\right)\leq 0$. However, $y_{i}f(\mathbf{x}_{i};\bar{\bm{\theta}})-1\geq 0$ ($\bar{\bm{\theta}}$ is a feasible point of (P)) and $\bar{\lambda}_{i}\geq 0$ for all $i\in[m]$, thus it holds:

$$ $\sum_{i=1}^{m}\bar{\lambda}_{i}\left(y_{i}f(\mathbf{x}_{i};\bar{\bm{\theta}})-1\right)=0,$ (65) $$

which concludes the proof that $\bar{\bm{\theta}}$ is a $D_{\frac{1}{2}\|\cdot\|_{\star}^{2}}^{\bar{\bm{\theta}}}$-generalized KKT point.

∎

###### Lemma A.4 .

###### Theorem A.5 (Soft margin increases - full version) .

###### Proof.

###### Lemma A.6 .

###### Proof.

###### Lemma A.7 .

###### Proof.

###### Definition A.8 .

###### Definition A.9 ( ( d , ϵ , δ ) 𝑑 italic-ϵ 𝛿 (d,\epsilon,\delta) - approximate KKT point) .

###### Lemma A.10 .

###### Proof.

###### Lemma A.11 .

###### Proof.

###### Definition A.12 (Convex conjugate) .

###### Proposition A.13 .

###### Lemma A.14 .

###### Proposition A.15 .

###### Proof.

###### Lemma A.16 .

###### Proof.

###### Lemma A.17 .

###### Proof.

###### Theorem A.18 .

###### Proof.

###### Proposition A.19 .

###### Corollary A.20 .

###### Proof.

###### Proposition A.21 .

###### Proof.

### A.3 Generalization to other losses

The previous results can be generalized to any loss with exponential tails. In particular, let us proceed to the following definition:

###### Definition A.22 .

Let $\Phi:\mathbb{R}\to\mathbb{R}$. Assume that $\mathcal{L}(\bm{\theta})=\sum_{i=1}^{m}e^{-\Phi\left(y_{i}f(\mathbf{x}_{i};\bm{\theta})\right)},\bm{\theta}\in\mathbb{R}^{p}$, where $f:\mathbb{R}^{d}\to\mathbb{R},y_{i}\in\{\pm 1\}$. We call the function $l:\mathbb{R}\to\mathbb{R},l(u):=e^{-\Phi(u)}$, exponentially tailed, if the following conditions hold:

- (i)
$\Phi$ is continuously differentiable.
- (ii)
$\Phi^{\prime}(u)>0$ for all $u\in\mathbb{R}$.
- (iii)
The function $g(u)=\Phi^{\prime}(u)u$ is non-decreasing in $[0,\infty)$.

Notice that the definition above covers the exponential loss for $\Phi(u)=u$ and the logistic loss for $\Phi(u)=-\log\log(1+e^{-u})$.
To accommodate different loss functions, Assumption [A3](#S2.I1.i3) needs to be adjusted as follows:

- •
There is a $t_{0}>0$, such that $\mathcal{L}(\bm{\theta}_{t_{0}})<e^{-\Phi(0)}$.

See Section A in (Lyu and Li,, ) for a more general, albeit technical, definition that allows the extension of the full analysis to general exponentially-tailed losses.

Under these conditions, we can define the soft margin as follows:

$$ $\tilde{\gamma}=\frac{l^{-1}(\mathcal{L})}{\|\bm{\theta}\|^{L}}=\frac{\Phi^{-1}\left(\log\frac{1}{\mathcal{L}}\right)}{\|\bm{\theta}\|^{L}},$ $$

and prove a strict generalization of Theorem [3.1](#S3.Thmtheorem1).

###### Theorem A.23 (Soft margin increases - general loss function) .

For almost any $t>t_{0}$, it holds:

$$ $\frac{d\log\tilde{\gamma}}{dt}\geq L\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{\left(\Phi^{-1}\right)^{\prime}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}{L\mathcal{L}(\bm{\theta}_{t})\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}-\frac{1}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\geq 0.$ $$

###### Proof.

Let $\mathbf{n}_{t}\in\partial\|\bm{\theta}_{t}\|$. We have:

$$ $\begin{split}\frac{d\log\tilde{\gamma}}{dt}&=\frac{d}{dt}\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)-L\frac{d}{dt}\log\|\bm{\theta}_{t}\|\\ &=\frac{d}{dt}\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)-L\left\langle\frac{\mathbf{n}_{t}}{\|\bm{\theta}_{t}\|},\frac{d\bm{\theta}}{dt}\right\rangle\;\;\;\;\;(\text{Chain rule})\\ &\geq\frac{d}{dt}\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)-L\frac{\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}\;\;\;\;\;(\text{definition of dual norm and $\|\mathbf{n}_{t}\|_{\star}\leq 1$})\\ &=-\frac{d\mathcal{L}(\bm{\theta}_{t})}{dt}\frac{\left(\Phi^{-1}\right)^{\prime}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}{\mathcal{L}(\bm{\theta}_{t})\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}-L\frac{\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}{\|\bm{\theta}_{t}\|}\;\;\;\;\;(\text{Chain rule})\\ &=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{\left(\Phi^{-1}\right)^{\prime}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}{\mathcal{L}(\bm{\theta}_{t})\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\;\;\;\;\;(\text{Equation~{}\ref{eq:loss_descent}}).\end{split}$ (66) $$

But, the first term inside the parenthesis can be related to the second one via the following calculation. Recall that, by the chain rule for locally Lipschitz functions (Theorem [A.2](#A1.Thmtheorem2)), for any $\mathbf{g}_{t}\in\partial\mathcal{L}(\bm{\theta}_{t})$ there exist $\mathbf{h}_{1}\in\partial y_{1}f(\mathbf{x}_{1};\bm{\theta}_{t}),\ldots,\mathbf{h}_{m}\in\partial y_{m}f(\mathbf{x}_{m};\bm{\theta}_{t})$ such that $\mathbf{g}_{t}=\sum_{i=1}^{m}e^{-\Phi(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))}\Phi^{\prime}(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})))\mathbf{h}_{i}$. Thus, for a minimum norm subderivative $\mathbf{g}_{t}^{\star}$, we have:

$$ $\begin{split}\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle&=\left\langle\bm{\theta}_{t},\sum_{i=1}^{m}e^{-\Phi(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))}\Phi^{\prime}(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))\mathbf{h}_{i}^{\star}\right\rangle\\ &=\sum_{i=1}^{m}e^{-\Phi(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))}\Phi^{\prime}(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))\left\langle\bm{\theta}_{t},\mathbf{h}_{i}^{\star}\right\rangle\\ &=L\sum_{i=1}^{m}e^{-\Phi(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))}\Phi^{\prime}(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}),\end{split}$ (67) $$

where the last equality follows from Euler’s theorem for homogeneous functions (whose generalization for subderivatives can be found in Theorem B.2 in Lyu and Li, ()). But, now observe that as per assumption, $u\to\Phi^{\prime}(u)u$ is non-decreasing and this last term can be lower bounded as:

$$ $\begin{split}\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle\geq L\sum_{i=1}^{m}e^{-\Phi(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))}\Phi^{\prime}\left(\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)\right)\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right),\end{split}$ (68) $$

where we used the fact $y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t})\leq\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)$ for all $i\in[m]$ (by the monotonicity of $\Phi$ the definition of $\mathcal{L}$). Leveraging the fundamental property between the derivative of a function and its inverse’s, we further get:

$$ $\begin{split}\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle\geq L\sum_{i=1}^{m}e^{-\Phi(y_{i}f(\mathbf{x}_{i};\bm{\theta}_{t}))}\frac{\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}{\left(\Phi^{-1}\right)^{\prime}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t}}\right)}=L\mathcal{L}(\bm{\theta}_{t})\frac{\Phi^{-1}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t})}\right)}{\left(\Phi^{-1}\right)^{\prime}\left(\log\frac{1}{\mathcal{L}(\bm{\theta}_{t}}\right)}.\end{split}$ (69) $$

We have made the first term of Equation [66](#A1.E66) appear. By plugging Equation [69](#A1.E69) into Equation [66](#A1.E66), we get:

$$ $\begin{split}\frac{d\log\tilde{\gamma}}{dt}&\geq\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{L}{\left\langle\bm{\theta}_{t},-\mathbf{g}_{t}^{\star}\right\rangle}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\\ &\geq\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert^{2}\left(\frac{L}{\|\bm{\theta}_{t}\|\|\mathbf{g}_{t}^{\star}\|_{\star}}-\frac{L}{\|\bm{\theta}_{t}\|\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert}\right)\;\;\;\;\;(\text{definition of dual norm}).\end{split}$ (70) $$

Noticing that $\|\mathbf{g}_{t}^{\star}\|_{\star}=\left\lVert\frac{d\bm{\theta}}{dt}\right\rVert$ (from Proposition [A.13](#A1.Thmtheorem13)) concludes the proof.
∎

###### Definition A.22 .

###### Theorem A.23 (Soft margin increases - general loss function) .

###### Proof.

## Appendix B Bregman proximity measure

In the proof of our main result (Theorem [A.18](#A1.Thmtheorem18)), we constructed a sequence of approximate generalized KKT points
(Definition [A.9](#A1.Thmtheorem9)). However, in many cases, while solving (non-convex) optimization problems, we only have feasible points without any evidence of optimality or stationarity. In such cases, it is useful to come up with a progress measure of approximate stationarity that can also serve as a stopping criterion for the optimization algorithm.
Consider an optimization problem:

$$ $\displaystyle\begin{split}&\min_{\bm{\theta}\in\mathbb{R}^{p}}f(\bm{\theta})\\ \text{s.t. }&g_{i}(\bm{\theta})\leq 0\;\forall i\in[m],\end{split}$ (P) $$

where we assume that $f,\{g_{i}\}_{i=1}^{m}$ are differentiable for the sake of brevity.

Figure: Figure 3: An illustration of the reduction of the Bregman proximity measure. Once it separates the training points, steepest descent in homogeneous networks implicitly makes progress towards generalized stationary points $\bm{\theta}^{\star}$ of a margin maximization problem (Theorem [A.18](#A1.Thmtheorem18)).

For a feasible point $\bm{\theta}^{\prime}$ of ([P](#A2.Ex8)) and a non-negative function $d:\mathbb{R}^{p}\times\mathbb{R}^{p}\to\mathbb{R}_{+}$, we define the $d$-Bregman proximity measure as the solution of the following optimization problem:

$$ $\displaystyle\begin{split}&\min_{\epsilon,\lambda_{1},\ldots,\lambda_{m}}\epsilon\\ \text{s.t. }&d\left(-\sum_{i=1}^{m}\lambda_{i}\nabla g_{i}(\bm{\theta}^{\prime}),\nabla f(\bm{\theta}^{\prime})\right)\leq\epsilon,\\ &\sum_{i=1}^{m}\lambda_{i}g_{i}(\bm{\theta}^{\prime})\geq-\epsilon,\\ &\lambda_{i}\geq 0\;\forall i\in[m].\end{split}$ (71) $$

This definition mirrors and generalizes the definitions of (Dutta et al.,, ), which were inspired by approximate KKT points (whose proximity is measured using the Euclidean distance as $d$). However, as we saw in our analysis, there are many cases of problems where a proximity measure would be better defined using alternatives functions. Figure [3](#A2.F3) conceptually illustrates the reduction of the Bregman divergence in a possible converging path. The relaxation of the slackness constraints in the form of $\sum_{i=1}^{m}\lambda_{i}g_{i}(\bm{\theta}^{\prime})\geq-\epsilon$ is essential for ensuring that the proximity measure captures proximity to stationarity - see Section 3.2 in (Dutta et al.,, ) for a discussion.

## Appendix C Relationship to Adam and Shampoo

The family of steepest descent algorithms includes simplified versions (momentum turned-off) of two adaptive methods, Adam and Shampoo, which have been very popular for training deep neural networks.

### C.1 Adam

Adam (Kingma and Ba,, ) is a popular adaptive optimization method, which is frequently used in deep learning. Following our previous notation, the update rule of Adam amounts to:

$$ $\begin{split}\mathbf{m}_{t}&=\beta_{1}\mathbf{m}_{t-1}+(1-\beta_{1})\nabla\mathcal{L}(\bm{\theta}_{t-1})\\ \mathbf{v}_{t}&=\beta_{2}\mathbf{v}_{t-1}+(1-\beta_{2})\nabla\mathcal{L}(\bm{\theta}_{t-1})^{2}\\ \hat{\mathbf{m}}_{t}&=\frac{\mathbf{m}_{t}}{1-\beta_{1}^{t}};\hat{\mathbf{v}}_{t}=\frac{\mathbf{v}_{t}}{1-\beta_{2}^{t}}\\ \bm{\theta}_{t}&=\bm{\theta}_{t-1}-\eta_{t}\frac{\hat{\mathbf{m}}_{t}}{\sqrt{\hat{\mathbf{v}}_{t}}+\epsilon},\end{split}$ (72) $$

where the $\sqrt{},{}^{2},\div$ operations are overloaded to operate elementwise in vectors. Parameters $\beta_{1},\beta_{2}$ control the memory of the update rule, while $\epsilon$ is a numerical precision parameter. Notice that for $\beta_{1}=\beta_{2}=\epsilon=0$, we recover sign-gradient descent.

Wang et al., ()studied the implicit bias of ([72](#A3.E72)) for $\epsilon>0$ in linear networks establishing bias towards $\ell_{2}$ margin maximization, while Zhang et al., () analyzed the case of $\epsilon=0$ and generic $\beta_{1},\beta_{2}\in[0,1)$ also in linear networks and showed bias towards $\ell_{\infty}$ margin maximization.

### C.2 Shampoo

Shampoo (Gupta et al.,, ) is an adaptive optimization algorithm, which has recently gained popularity in deep learning applications. For each weight matrix $\mathbf{W}_{t}$ and its corresponding gradient matrix $\mathbf{G}_{t}$, the update rule of Shampoo without momentum amounts to (Bernstein and Newhouse,, ):

$$ $\begin{split}\mathbf{W}_{t+1}&=\mathbf{W}_{t}-\eta_{t}\mathbf{U}_{t}\mathbf{V}_{t}^{T},\end{split}$ (73) $$

where $\mathbf{U}_{t},\mathbf{V}_{t}$ contain the left and right singular vectors of $\mathbf{G}_{t}$, i.e., $\mathbf{G}_{t}=\mathbf{U}_{t}\mathbf{\Sigma}_{t}\mathbf{V}_{t}$. Bernstein and Newhouse, () recently noticed that this update corresponds to steepest descent (in matrix space) with respect to the spectral norm $\sigma_{\mathrm{max}}(\cdot)$. This is equivalent to an architecture-dependent norm in parameter space. For instance, if $\bm{\theta}=(\mathbf{W}_{1},\ldots,\mathbf{W}_{L})$, then Shampoo without momentum corresponds to steepest descent with respect to the norm $\|\bm{\theta}\|_{S}:=\max\left(\sigma_{\mathrm{max}}(\mathbf{W}_{1}),\ldots,\sigma_{\mathrm{max}}(\mathbf{W}_{L})\right)$.

## Appendix D Experimental Details

All experiments are implemented in PyTorch (Paszke et al.,, ).

#### Teacher-student experiments

We use the following hyperparameters: $d=2^{32},k=64,k^{\prime}=1024,m=250$, learning rate $\eta=6\times 10^{-3}$ and density $\frac{\|\bm{\theta}^{\star}\|_{0}}{k^{\prime}(d+1)}=0.0001$ (3 coordinates active per neuron). We vary the scale of initialization in $\{0.1,0.01,0.001\}$ and we train for $10^{5}$ epochs. Each random seed affects the draw of the datasets and the initialization of the parameters of the network. Test accuracy is estimated using 20,000 unseen data drawn from the same generative process.

Figure: Figure 4: Geometric margins vs test accuracy in a teacher-student setup. Left: $\ell_{1}$ margin. Right: $\ell_{2}$ margin. Each point corresponds to a different run (different random seed).
Refer to caption: /html/2410.22069/assets/x3.png

#### MNIST

We use a constant learning rate of $3\times 10^{-3}$ and 1-hidden layer neural networks of width $128$, optimizing the logistic loss. The digits that we extract are ’3’ and ’6’ (100 training points). Each random seed corresponds to a different draw of the training dataset and different initialization. Sign gradient descent runs were very effective in minimizing the training loss, and we stopped the training early after the loss reached value smaller than $10^{-7}$ in order to avoid numerical issues. We depict the final value, repeated for as many epochs as shown in the figures (as if the model has indeed converged).

Figure: Figure 5: Relationship between Adam and steepest descent algorithms. Digits ’2’ and ’7’.
Refer to caption: /html/2410.22069/assets/x5.png

Figure [5](#A4.F5) shows accuracy and margins for a different pair of digits ("2" vs "7").

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: minor comment: 
1. 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.

2. 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.
soundness: 4
strengths: **Strong Points:**

1. The paper provides rigorous theoretical analysis of the implicit bias of steepest descent algorithms. The results and proofs extend the l2 norm case (gradient descent) by Lyu&Li to general norms. The theoretical results are clean and some of the extension are nontrivial. 

2. The class of optimization algorithms studied in this paper is very general and include several important optimization algorithms as special cases.

3. The paper connects theoretical insights to practical optimization methods like Adam, which is widely used in the deep learning community. This connection may help to understand the benefit of Adam.
summary: The paper investigates the implicit bias of the family of steepest descent algorithms, including gradient descent, sign gradient descent, and coordinate descent, for deep homogeneous neural networks. The authors aim to understand how these optimization algorithms implicitly select solutions from the perspective of margin maximization. The main contributions of the paper are:

1. A rigorous analysis of the implicit bias of steepest descent algorithms in non-linear, homogeneous neural networks, showing that an algorithm-dependent geometric margin increases during training, under the same set of assumptions made in Lyu&Li.
2. The definition and characterization of a generalized notion of stationarity for optimization problems, demonstrating that these algorithms reduce a generalized Bregman divergence, which quantifies proximity to stationary points of a margin-maximization problem.
3. Experimental validation of the theoretical findings by training neural networks with various steepest descent algorithms, highlighting connections to the implicit bias of Adam.


I think the class of the optimization problems studied in this paper is general and the theoretical results of the paper are quite clean. Although the main proofs follow the framework developed by Lyu and Li, the proofs are nontrivial (I read most of the proofs in the main text and a few in the appendix). Overall, I am leaning towards accepting the paper. With additional clarifications of the relation with prior work, this paper would be a valuable addition to the literature on deep learning theory.
weaknesses: **Weak Points:**
The authors briefly discuss some prior work on implicit bias of optimization algorithms other than GD in the related work section. But I found the inclusion of related work and the discussion here is somewhat insufficient. For example, 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. 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? I think more detailed discussion is necessary.

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

---

confidence: 5
contribution: 3
initial_rating: 8
presentation: 4
questions: 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.
soundness: 4
strengths: 1. Understanding the implicit bias of optimization methods is an important problem in deep learning theory, and the paper takes a margin-based view of implicit bias and sheds light on how different methods may optimize different notions of margin for deep models.
2. It is a bit surprising that such an implicit bias of steepest descent can be rigorously proved in the general case. Previously, it is known that this can be proved for linear models, and for deep homogeneous networks, Lyu & Li (2020) generalized the result for GD. It is reasonable to imagine that one could somehow generalize Lyu & Li (2020)'s result to steepest gradient, but their proof apparently has a lot of dependence on the L2 geometry induced by GD. After having a careful read of the proof (though I skipped a few details), I believe the authors found the right way to do this generalization and worked out all the technical issues, including those related to non-smoothness.
3. The paper is well-written and easy to follow.
4. Experiments in simple settings validated the theoretical results.
summary: This paper studies the implicit bias of steepest descent methods with infinitesimal step size (i.e., steepest flow) and presents an interesting generalization of Lyu & Li (2020)'s result on gradient flow (steepest flow with L2 norm). Similar to gradient flow, it is shown that steepest flow has a bias towards KKT solutions to a margin maximization problem, but the margin being maximized here is normalized properly according to the norm used in steepest flow, which may not be the L2 norm in general.
weaknesses: 1. While I really appreciate that the authors worked out every technical detail to generalize the proof of Lyu & Li (2020), I also noted that the overall proof outline has not changed much from Lyu & Li (2020), which means this paper does not actually bring a brand new high-level proof idea. This is reasonable since any implicit bias analysis of steepest flow automatically implies an analysis of gradient flow, but the fact that the paper fails to prove the real KKT conditions and only manage to prove a weaker notion (generalized KKT) suggests that a perfect generalization from gradient flow to steepest flow may indeed need a completely new proof strategy.
2. Same as all previous works studying the max-margin bias, this paper only analyzes the late phase, where the training loss is already very small. While the asymptotic analysis of implicit bias is interesting, this also makes the phenomenon less relevant to the practice.

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

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See weakness
soundness: 3
strengths: 1. The convergence of the general steepest descent to the general maximum margin solution is novel. 
2. The connection between the implicit bias of Signed steepest descent with Adam is interesting.
summary: This paper studies the implicit bias of  steepest flow with general norm in homogeneous neural networks. It shows that the soft-margin is monotonically increasing after the loss is below a threshold. Furthermore, it shows that the steepest flow converges to the generalized KKT point. Finally, experiments demonstrate the similarity of Adam algorithm and Signed-steepest descent algorithm, in terms of implicit bias.
weaknesses: The set of results and proofs seem to be a straightforward generalization of [Lyu and Li, 2019]. The technical contribution is not strong.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: How close is the steepest descent to actual GD? Does the theory hold for GD?
soundness: 2
strengths: The problem of prediction margin is important and of fundamental importance
summary: This work studies how the prediction margin changes as the training proceeds in a homogeneous network
weaknesses: I am not sure if I understand the meaning of the result. Also, I find the setting of the theory too restrictive

1. I do not understand Figure 1-right. What does it imply? How does this relate to the theory?
2. The theory only applies to the "exponential loss," which does not make much sense to me.  

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

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: - 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.

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

- 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? Additionally, they showed that the soft margin approximates the normalized margin. Could you provide a similar analysis in this context?
soundness: 3
strengths: This paper extends the result in [Lyu & Li 2020] to steepest flow for general norms with the lightest extra assumption on the norm. While previous papers focused on gradient descent and other variants of gradient descent, this paper gives a general result for any steepest flow.
The claimed results seem sound and the paper is nicely written.
summary: This paper studies the implicit bias of the steepest flow with respect to a general norm in deep homogeneous neural networks. Theoretically, they present two major results. 1) The soft margin will increase 2) The limit points of the parameter directions are general KKT points of the margin maximization optimization problem under some assumption of the norm. They also show some experimental results concerning the trajectories of different steepest descent algorithms and the connection to the implicit bias of Adam.
weaknesses: The paper asserts that it presents results for the steepest descent; however, the theoretical results in Section 3 are limited to steepest flow. According to Lyu & Li (2020), additional work is required to extend the findings from flow to descent.

Regarding the general loss function, the paper demonstrates that the soft margin is monotonically increasing but fails to address the convergence of KKT points.

Moreover, the paper overlooks several relevant references, including:

1. Chatterji, N.S., Long, P.M., & Bartlett, P. (2021). "When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?"

2. Cai, Y., Wu, J., Mei, S., Lindsey, M., & Bartlett, P.L. (2024). "Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization."

3. Nacson, M.S., Srebro, N., & Soudry, D. (2019, April). "Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate."

4. Ji, Z., Srebro, N., & Telgarsky, M. (2021, July). "Fast margin maximization via dual acceleration."

Meta-review: This paper studies the implicit bias of steepest flow (continuous-time version of steepest descent) algorithm in training homogeneous neural networks. The paper extends an existing work Lyu & Li on gradient descent to a general class of algorithms, showing monotonic increase of the soft margin and convergence to the direction of generalized KKT points of the margin maximization problem.

All reviewers were positive about this submission. The paper presents an extension of a seminal result to a much more general class of algorithms, also drawing connections to practical algorithms such as Adam and Shampoo. Although the outline of proof seems to be the same as the existing paper, the extension from $\ell_2$ geometry to possibly nonsmooth cases looks nontrivial.

It is, though, unfortunate that the current proof technique cannot guarantee convergence to the usual KKT points (not the generalized KKT points introduced in the paper) in some important cases such as $\ell_1$ and $\ell_\infty$ norms.

Also, as Reviewer pCcn points out, the paper only characterizes the implicit bias in the continuous-time (flow) case and leaves the extension to the discrete-time (descent) case as future work. In fact, I see that there is no indicator of this fact in the title and abstract; I recommend revising at least the abstract to reflect this.

Overall, the paper offers solid contributions to the study of implicit bias of neural network training. I recommend acceptance.

Decision: Accept (Poster)