# The late-stage training dynamics of (stochastic) subgradient descent on homogeneous neural networks

Sholom Schechtman, Nicolas Schreuder

► To cite this version:

Sholom Schechtman, Nicolas Schreuder. The late-stage training dynamics of (stochastic) subgradient descent on homogeneous neural networks. The 38th Annual Conference on Learning Theory (COLT), Jun 2025, Lyon, France. pp.5143-5172. hal-05227831

HAL Id: hal-05227831

https://hal.science/hal-05227831v1

Submitted on 28 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The late-stage training dynamics of (stochastic) subgradient descent on homogeneous neural networks

Sholom Schechtman¹ and Nicolas Schreuder²

¹SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris

²CNRS, LIGM

August 28, 2025

## Abstract

We analyze the implicit bias of constant step stochastic subgradient descent (SGD). We consider the setting of binary classification with homogeneous neural networks – a large class of deep neural networks with ReLU-type activation functions such as MLPs and CNNs without biases. We interpret the dynamics of normalized SGD iterates as an Euler-like discretization of a conservative field flow that is naturally associated to the normalized classification margin. Owing to this interpretation, we show that normalized SGD iterates converge to the set of critical points of the normalized margin at late-stage training (i.e., assuming that the data is correctly classified with positive normalized margin). Up to our knowledge, this is the first extension of the analysis of the Lyu and Li (2020) on the discrete dynamics of gradient descent to the nonsmooth and stochastic setting. Our main result applies to binary classification with exponential or logistic losses. We additionally discuss extensions to more general settings.

## 1 Introduction

Modern deep learning architectures are typically *overparameterized* relative to the number of training samples, leading to infinitely many weight configurations that interpolate the training data. Traditional learning theory suggests such solutions should generalize poorly (Vapnik, 1998; Belkin et al., 2019). Yet, empirical evidence shows that interpolating solutions found through training often generalize well (Zhang et al., 2021). This observation has led to the *implicit bias* hypothesis, which posits that gradient-based optimization algorithms act as implicit regularizers, guiding models toward parameters that generalize well (Neyshabur et al., 2015; Gunasekar et al., 2018a). Understanding this bias is key to explaining the success of deep learning and remains an active research area.

While a general theoretical characterization for deep neural networks remains out of reach, progress has been made in simplified settings. One such setting is the class of positively homogeneous neural networks (NNs), where a network $\Phi(\cdot; w)$ satisfies $\Phi(x; \lambda w) = \lambda^L \Phi(x; w)$ for any $\lambda > 0$, weights $w$, and input features $x$. This class encompasses feedforward NNs of depth $L$ without biases and with piecewise linear activation functions, such as MLPs and CNNs.

In the spirit of early works by Lyu and Li (2020); Ji and Telgarsky (2020), this paper focuses on binary classification problem with such networks. Given a labeled dataset $((x_i, y_i))_{i \le n}$ in $\mathbb{R}^p \times \{-1, 1\}$ and a non-negative loss function $l$ strictly decreasing to zero (e.g., logistic or exponential loss), the objective is to minimize the empirical risk,

$$ \mathcal{L}(w) := \frac{1}{n} \sum_{i=1}^{N} l(y_i \Phi(x_i; w)). \qquad (1) $$

The quality of a prediction for a given weight vector $w$ is measured by the margin,

$$ m(w) := \min_{1 \le i \le n} y_i \Phi(x_i; w). \qquad (2) $$
Notably, the training set is correctly classified if $m(w)>0$. Two key observations follow. First, if some weights $w$ satisfy $m(w)>0$, then for any $\lambda>1$, $\mathcal{L}(\lambda w)<\mathcal{L}(w)$. Consequently, $\inf_w \mathcal{L}(w) = 0$, and reaching this infimum requires the norm of the weights to grow to infinity. Second, due to homogeneity, prediction quality depends only on the direction $\bar{w} := w/\|w\|$. This naturally raises the question of how $\bar{w}$ evolves during training and what properties characterize its limit points.

A step toward answering this question was taken by Lyu and Li (2020), who analyzed the dynamics of subgradient flow (GF) and, under additional smoothness assumptions, gradient descent (GD) on the empirical risk. Assuming that at some point during training $m(w) > 0$ (i.e., the training error is zero), they showed that the parameter norm grows to infinity and that the direction $\bar{w}$ converges to the set of KKT points of a constrained optimization problem related to margin maximization. Later, Ji and Telgarsky (2020) proved $\bar{w}$ actually converges to a unique KKT point considering the GF dynamics. These results highlights a clear implicit bias: even after achieving zero training error, the dynamics continue evolving until reaching a form of optimality in the normalized margin.

While the works of Lyu and Li (2020); Ji and Telgarsky (2020) provide key insights into the training dynamics of homogeneous networks, they leave open an important question: does the same implicit bias phenomenon extend to (stochastic) subgradient descent (SGD)? GF describes the limiting continuous-time dynamics of SGD, but the discrete-time analysis in Lyu and Li (2020) does not account for stochasticity or nonsmoothness. As a result, their framework does not extend to neural networks with ReLU or LeakyReLU activations, which are widely used in practice (Goodfellow, 2016; Fleuret, 2023).

**Main contributions** We address this open question by identifying a setting in which the limit points of the normalized directions $u_k := w_k/\|w_k\|$ can be characterized, where $(w_k)$ is generated by SGD with a constant step-size on the empirical risk (1) for L-homogeneous nonsmooth networks. Our analysis covers both the exponential and logistic losses. Since we are interested in the limit points of the normalized directions, we focus the late-stage training dynamics, i.e. after the training data is correctly classified. We define this stage as the regime in which the normalized margin remains positive, as formalized later by the event $\mathcal{E}$ in Equation (6) and discussed in Section 4. Our main contributions can be summarized as follows:

1. We show that the dynamics of $(u_k)$ can be interpreted as a Euler-like discretization (or stochastic approximation) of a gradient flow inclusion, $\dot{u}(t) \in \bar{D}_s(u(t))$, where $\bar{D}_s$ is a conservative set-valued field of the margin restricted to the unit sphere $m|_{\mathbb{S}^{d-1}}$. This gradient-like object, recently introduced by Bolte and Pauwels (2021), naturally appears in the analysis. In particular, we show in Proposition 4 that, approximately,

$$u_{k+1} \in u_k + \tilde{\gamma}_k \bar{D}_s(u_k) + \tilde{\gamma}_k e_k, \quad (3)$$

where $(e_k)$ is a sequence of (stochastic) perturbations, that diminishes as $k \to +\infty$.

2. As a consequence, leveraging recent results on stochastic approximations of differential inclusions (Benaïm (2006); Davis et al. (2020); Bolte and Pauwels (2021)), we establish in Theorem 5 that $(u_k)$ converges to the set of $\bar{D}_s$-critical points $\mathcal{Z}_s := \{u \in \mathbb{S}^{d-1} : \bar{D}_s(u) = 0\}$. In our setting, $\mathcal{Z}_s$ coincides exactly with the KKT points of Lyu and Li (2020).

From a mathematical perspective, our techniques differ from those of Lyu and Li (2020); Ji and Telgarsky (2020). Rather than constructing a smooth approximation of the margin, we directly consider the margin and interpret the dynamics of the normalized SGD iterates as a stochastic approximation. This, in contrast to these previous works, allows us to incorporate both stochasticity and nonsmoothness in our analysis. Finally, although we focus on exponential-type losses, we also present a more general setting in Appendix F where our proof techniques apply.

**Organization of the paper** We begin by reviewing related works in Section 2. Then, in Section 3, we introduce key technical concepts for nonsmooth analysis. Section 4 presents the main setting we consider. Our main result and its proof are detailed in Sections 5 and 6, respectively. Finally, additional proofs and supplementary materials are provided in the appendices.
## 2 Related works

We review related works on the implicit bias of neural networks trained with gradient-based algorithms and their connection to margin maximization. The discussion follows an increasing order of flexibility, starting with logistic regression–viewed as a one-layer network– then progressing to linear and homogeneous networks and finally addressing non-homogeneous architectures. For a comprehensive survey on the topic, we refer the reader to Vardi (2023).

**Logistic regression** Training a logistic regression model can be viewed as training a one-layer neural network or fine-tuning the final linear layer of a deep network, making it a natural starting point for studying the training dynamics of deep networks. Motivated by this perspective, a first line of research has explored the properties of (stochastic) gradient descent iterates for linear logistic regression. Soudry et al. (2018) showed that when learning parameters *w* using gradient descent on the logistic loss–or more generally, on exponentially-tailed losses–over separable data, the direction of *w* converges to the ℓ₂-max margin solution, while its norm grows to infinity. Nacson et al. (2019c) extended this result to stochastic gradient descent with a fixed learning rate, demonstrating similar behavior. Ji and Telgarsky (2018b) further considered non-linearly separable data, showing that the direction of *w* converges to the maximum margin predictor of the largest linearly separable subset.

**Linear networks** Linear networks, composed of stacked linear layers $W_D \times \cdots \times W_1$ without activation functions, represent linear functions, but their parameterization strongly influences learning dynamics and implicit bias. Gunasekar et al. (2018b) analyzed gradient descent on fully connected and convolutional linear networks, showing convergence in direction to the maximum-margin solution. Ji and Telgarsky (2018a) extended this result by proving predictor convergence under weaker assumptions and establishing asymptotic singular vector alignment. Nacson et al. (2019b) examined conditions on the loss function ensuring that gradient descent iterates converge to the ℓ₂-maximum margin solution. Yun et al. (2020) later developed a unified framework for gradient flow in linear tensor networks, covering fully connected, diagonal, and convolutional architectures.

**Homogeneous networks** Linear networks cannot model architectures with nonlinear activations, limiting their applicability. Homogeneous networks, including fully connected and convolutional architectures without bias terms and with ReLU activations, have been considered to address this limitation. In this setting, Du et al. (2018) proves that gradient flow enforces the differences between squared norms across different layers to remain invariant without any explicit regularization. Assuming training error converges to zero and parameters converge in direction, Nacson et al. (2019a) established that rescaled parameters reach a first-order KKT point of a maximum-margin problem. Lyu and Li (2020) showed that for networks trained with exponential or logistic loss, gradient flow converges to a KKT point of the maximum-margin problem in parameter space. Vardi et al. (2022) examined the (local) optimality of these KKT points, identifying conditions for local or global optimality. Chizat and Bach (2020) improve these results for infinitely wide two-layer neural networks with homogeneous activations, characterising the learnt classifier as the solution of a convex max-margin problem. Ji and Telgarsky (2020) proved that the direction of gradient flow converges to a unique point. Finally, Wang et al. (2021) analyzed margin maximization in homogeneous networks trained with adaptive methods such as Adam.

**Beyond homogeneous networks** Kunin et al. (2022); Le and Jegelka (2022) extend maximum-margin bias and alignment results from linear and homogeneous to quasi-homogeneous networks, allowing to consider networks with biases and residual connections. Cai et al. (2024) analyzes the dynamics of large-step-size gradient descent for training predictors that satisfy a near-homogeneity condition. They identify two distinct training phases: an initial phase in which the empirical risk oscillates, followed by a second phase where it decreases monotonically, and examines the role of the step size in driving the phase transition.
# 3 Preliminaries

Although feedforward and convolutional NNs with ReLU or LeakyReLU activations are inherently nonsmooth—making their analysis more challenging—they exhibit some form of regularity. In particular, they belong to the important class of semialgebraic functions, which we now introduce.

**Semialgebraic functions.** A set $A \subset \mathbb{R}^d$ is semialgebraic if it can be expressed as a finite union of intersections of sets of the form $\{Q(x) \le 0\}$, where $Q : \mathbb{R}^d \to \mathbb{R}$ is a polynomial. A (set-valued) function is semialgebraic if its graph is a semialgebraic set. Examples include piecewise polynomials, rational functions and functions such as $x \mapsto x^q$, where $q$ is any rational number.

Semialgebraic functions are closed under composition and remain stable under a finite number of operations, including $\{+, -, \times, \max, \min, \circ, \circ^{-1}\}$. From these properties it is clear that feedforward and convolutional NNs with piecewise linear activation functions such as ReLU are semialgebraic functions. Notably, the class of semialgebraic functions is a particular case of functions definable in an o-minimal structure. We discuss o-minimality in Appendix A and emphasize that every statement of the paper which involves semialgebraicity might be replaced by definability.

Although semialgebraic functions exhibit some regularity, they are not necessarily smooth. To analyze their behavior in optimization settings, we rely on a more general notion of differentiation—*conservative set-valued fields*, which we now define.

**Conservative set-valued fields.** Conservative set-valued fields were introduced in Bolte and Pauwels (2021) as an elegant framework for describing the output of automatic differentiation provided by numerical libraries such as TensorFlow and PyTorch (Abadi et al. (2015); Paszke et al. (2017)). They serve as a fundamental tool for analyzing first-order methods in non-smooth settings (see, e.g., Bolte et al. (2023)).

**Definition 1** (Bolte and Pauwels (2021)). A graph-closed, locally bounded set-valued map<fnref n="1" /> $D : \mathbb{R}^d \to \mathbb{R}^d$ with nonempty values is a conservative field for the potential $\mathcal{L} : \mathbb{R}^d \to \mathbb{R}$, if for any absolutely continuous curve $w : [0, 1] \to \mathbb{R}^d$, it holds for almost every $t \in [0, 1]$ that

$$ \frac{d}{dt} \mathcal{L}(w(t)) = \langle v, \dot{w}(t) \rangle \quad \text{for all } v \in D(w(t)). $$

Functions that are potentials of some conservative field are called path differentiable.

Given a continuously differentiable potential $\mathcal{L}$, the set-valued map $w \rightrightarrows \{\nabla \mathcal{L}(w)\}$ is an obvious example of a conservative field. For semialgebraic functions, two important examples of conservative set-valued fields are the Clarke subgradient and the output of backpropagation.

**Clarke subgradients.** Semialgebraic functions always admit a conservative field, the Clarke subgradient. This result, initially proven in Drusvyatskiy et al. (2015), builds on the work of Bolte et al. (2007).

**Definition 2** (Clarke subgradient Clarke et al. (1998)). Let $\mathcal{L}: \mathbb{R}^d \to \mathbb{R}$ be a locally Lipschitz function. The Clarke subgradient of $\mathcal{L}$ at $w \in \mathbb{R}^d$ is defined as

$$ \partial \mathcal{L}(w) := \operatorname{conv}\{v \in \mathbb{R}^d : \text{ there exist } w_k \to w, \text{ with } \mathcal{L} \text{ differentiable at } w_k \text{ and } \nabla \mathcal{L}(w_k) \to v\}, \quad (4) $$

where we denote by $\operatorname{conv}(A)$ the convex closure of a set $A$.

For semialgebraic function $\mathcal{L}$, $\partial \mathcal{L}$ is the minimal convex-valued semialgebraic conservative field (Drusvyatskiy et al. (2015); Bolte and Pauwels (2021)). That is, for any conservative set-valued field $D$ with semialgebraic potential $\mathcal{L}$, it holds for all $w$ that $\partial \mathcal{L}(w) \subset \operatorname{conv}(D(w))^2$.

<footnote n="1">¹A map $D: \mathbb{R}^d \to \mathbb{R}^d$ is set-valued if, for every $w \in \mathbb{R}^d$, $D(w)$ is a set in $\mathbb{R}^d$. See Appendix C for various definitions related to such maps.</footnote>

<footnote n="2">²Note that if $D$ is a conservative field, then the mapping $w \rightrightarrows \operatorname{conv}(D(w))$ is also conservative.</footnote>
**Backpropagation.** When applied to nonsmooth functions, the backpropagation algorithm formally applies the chain rule, replacing the derivative with an element of the Clarke subgradient when necessary. Although the Clarke subgradient of a composition $f \circ g$ is not necessarily equal to $\partial f \times \partial g$, the product of conservative mappings remains conservative (see Proposition 12 in Appendix B). As a result, (Bolte and Pauwels, 2021, Section 5) show that if a (possibly nonsmooth) semialgebraic function is defined through a computational graph (such as in a neural network), backpropagation produces an element of a conservative field. Consequently, the training a neural network via (S)GD is actually a (stochastic) conservative field descent.

# 4 Problem setting

We study (stochastic) gradient descent on the empirical risk

$$ \mathcal{L}(w) = \frac{1}{n} \sum_{i=1}^{n} l(p_i(w)), $$

where the loss function $l$ and the functions $(p_i)_{i=1}^n$ are specified in the following assumptions. Note that the empirical risk for binary classification from Equation (1) is a special case of the above objective.

**Assumption 1.**

i) The loss is either the exponential loss, $l(q) = e^{-q}$, or the logistic loss, $l(q) = \log(1+e^{-q})$.

ii) There exists an integer $L \in \mathbb{N}^*$ such that, for all $1 \le i \le n$, the function $p_i$ is positively L-homogeneous$^3$, locally Lipschitz continuous and semialgebraic.

If the $p_i$'s were differentiable with respect to $w$, the chain rule would guarantee that

$$ \nabla \mathcal{L}(w) = \frac{1}{n} \sum_{i=1}^{n} l'(p_i(w)) \nabla p_i(w) . $$

However, we only assume that the $p_i$'s are semialgebraic. While we could consider Clarke subgradients, the Clarke subgradient of operations on functions (e.g., addition, composition, and minimum) is only contained within the composition of the respective Clarke subgradients. This, as noted in Section 3, implies that the output of backpropagation is usually not an element of a Clarke subgradient but a selection of some conservative set-valued field. Consequently, for $1 \le i \le n$, we consider $D_i : \mathbb{R}^d \to \mathbb{R}^d$, a conservative set-valued field of $p_i$, and a function $a_i : \mathbb{R}^d \to \mathbb{R}^d$ such that for all $w \in \mathbb{R}^d$, $a_i(w) \in D_i(w)$. Given a step-size $\gamma > 0$, gradient descent (GD)$^4$ is then expressed as

$$ w_{k+1} = w_k - \frac{\gamma}{n} \sum_{i=1}^{n} l'(p_i(w_k)) a_i(w_k). \qquad (\text{GD}) $$

For its stochastic counterpart, stochastic gradient descent (SGD), we fix a batch-size $1 \le n_b \le n$. At each iteration $k \in \mathbb{N}$, we randomly and uniformly draw a batch $B_k \subset \{1, \dots, n\}$ of size $n_b$. The update rule is then given by

$$ w_{k+1} = w_k - \frac{\gamma}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) a_i(w_k). \qquad (\text{SGD}) $$

The considered conservative set-valued fields will satisfy an Euler lemma-type assumption.

**Assumption 2.** For every $i \le n$, $a_i$ is measurable and $D_i$ is semialgebraic. Moreover, for every $w \in \mathbb{R}^d$ and $\lambda \ge 0$, $a_i(w) \in D_i(w)$,

$$ D_i(\lambda w) = \lambda^{L-1} D_i(w), \quad \text{and} \quad L p_i(w) = \langle a_i(w), w \rangle. $$

<footnote>$^3$We recall that a mapping $f: \mathbb{R}^d \to \mathbb{R}$ is positively L-homogeneous if $f(\lambda w) = \lambda^L f(w)$ for all $w \in \mathbb{R}^d$ and $\lambda > 0$.</footnote>

<footnote>$^4$More precisely, this refers to conservative gradient descent. We use the term GD for simplicity, as conservative gradients behave similarly to standard gradients.</footnote>
Having in mind the binary classification setting, in which $p_i(w) = y_i\Phi(x_i, w)$, we define the margin

$$m : \mathbb{R}^d \to \mathbb{R}, \quad m(w) = \min_{1 \le i \le n} p_i(w). \qquad (5)$$

It quantifies the quality of a prediction rule $\Phi(\cdot, w)$. In particular, the training data is perfectly separated when $m(w) > 0$. A binary prediction for $x$ is given by the sign of $\Phi(x, w)$, and under the homogeneity assumption, it depends only on the normalized direction $w/\|w\|$. Consequently, we will focus on the sequence of directions $u_k := w_k/\|w_k\|$.

Finally, all of our results hold on the event

$$\mathcal{E} := [\liminf m(u_k) > 0], \qquad (6)$$

which ensures that the normalized directions $(u_k)$ have stabilized in a region where the training data is correctly classified. Before presenting our main result, we comment on our assumptions.

**On Assumption 1.** As discussed in the introduction, the primary example we consider is when $p_i(w) = y_i\Phi(x_i; w)$ is the signed prediction of a feedforward neural network without biases and with piecewise linear activation functions on a labeled dataset $((x_i, y_i))_{i \le n}$. In this case,

$$p_i(w) = y_i \Phi(w; x_i) = y_i V_L(W_L) \sigma(V_{L-1}(W_{L-1}) \sigma(V_{L-1}(W_{L-2}) \dots \sigma(V_1(W_1 x_i))), \quad (7)$$

where $w = [W_1, \dots, W_L]$, $W_i$ represents the weights of the $i$-th layer, $V_i$ is a linear function in the space of matrices (with $V_i$ being the identity for fully-connected layers) and $\sigma$ is a coordinate-wise activation function such as $z \mapsto \max(0, z)$ (ReLU), $z \mapsto \max(az, z)$ for a small parameter $a > 0$ (LeakyReLU) or $z \mapsto z$. Note that the mapping $w \mapsto p_i(w)$ is semialgebraic and $L$-homogeneous for any of these activation functions. Regarding the loss functions, the logistic and exponential losses are among the most commonly studied and widely used. In Appendix F, we extend our results to a broader class of losses, including $l(q) = e^{-q^a}$ and $l(q) = \ln(1 + e^{-q^a})$ for any $a \ge 1$.

**On Assumption 2.** Assumption 2 holds automatically if $D_i$ is the Clarke subgradient of $p_i$. Indeed, at any vector $w \in \mathbb{R}^d$, where $p_i$ is differentiable it holds that $p_i(\lambda w) = \lambda^L p_i(w)$. Differentiating with respect to $w$ and $\lambda$, respectively, and noting that $p_i$ remains differentiable at $\lambda w$ due to homogeneity, we obtain $\lambda \nabla p_i(\lambda w) = \lambda^L \nabla p_i(w)$ and $\langle \nabla p_i(\lambda w), w \rangle = L\lambda^{L-1}p_i(w)$. The second equality follows by taking $\lambda = 1$. The expression for any element of the Clarke subgradient then follows from (4).

However, for an arbitrary conservative set-valued field, Assumption 2 does not necessarily hold. For instance, $D(x) = 1(x \in \mathbb{N})$ is a conservative set-valued field for $p \equiv 0$, which does not satisfy Assumption 2. Nevertheless, in practice, conservative set-valued fields naturally arise from a formal application of the chain rule. For a non-smooth but homogeneous activation function $\sigma$, one selects an element $e \in \partial\sigma(0)$, and computes $a_i(w)$ via backpropagation. Whenever a gradient candidate of $\sigma$ at zero is required (i.e., in (7), for some $j$, $V_j(W_j)$ contains a zero entry), it is replaced by $e$. Since $V_j(W_j)$ and $V_j(\lambda W_j)$ have the same zero elements, it follows that for every such $w$, $a_i(\lambda w) = \lambda^L a_i(w)$. The conservative set-valued field $D_i$ is then obtained by associating to each $w$ the set of all possible outcomes of the chain rule, with $e$ ranging over all elements of $\partial\sigma(0)$. Thus, for such fields, Assumption 2 holds.

**On the event $\mathcal{E} = [\liminf m(u_k) > 0]$**. Training typically continues even after the training error reaches zero. The event $\mathcal{E}$ characterizes this late-training phase, where our result applies. As noted earlier, since $m$ is $L$-homogeneous, the classification rule is determined by the direction of the iterates $u_k = w_k/\|w_k\|$. The event $\mathcal{E}$ then captures the fact that, beyond some iteration, the normalized margin remains positive. Studying SGD on $\mathcal{E}$ is natural in the context of studying the implicit bias of SGD: we assume that we reached the phase in which the dataset is correctly classified and then characterize the limit points. A similar perspective was taken in Nacson et al. (2019a), where the implicit bias of GF was analyzed under the assumption that the sequence of directions and the loss converge. However, unlike their approach, ours does not require assuming such convergence a priori.
Earlier works such as Ji and Telgarsky (2020); Lyu and Li (2020), which analyze subgradient flow or smooth GD, establish convergence by assuming the existence of a single iterate $w_{k_0}$ satisfying $m(w_{k_0}) > \varepsilon$ and then proving that $\lim m(u_k) > 0$. Their approach relies on constructing a smooth approximation of the margin, which increases during training, ensuring that $m(u_k) > 0$ for all iterates with $k \ge k_0$. This is feasible in their setting, as they study either subgradient flow or GD with smooth $p_i$'s, allowing them to leverage the descent lemma.

In contrast, our analysis considers a nonsmooth and stochastic setting, in which, even if an iterate $w_{k_0}$ satisfying $m(w_{k_0}) > \varepsilon$ exists, there is no a priori assurance that subsequent iterates remain in the region where $m(u_k) > 0$. From this perspective, studying SGD on $\mathcal{E}$ can be viewed as a stability assumption, ensuring that iterates continue to classify the dataset correctly. Establishing stability for stochastic and nonsmooth algorithms is notoriously hard, and only partial results in restrictive settings exist Borkar and Meyn (2000); Ramaswamy and Bhatnagar (2017); Josz and Lai (2024).

# 5 Main result

As a first step toward our main result, we establish that the iterates norm ($\|w_k\|$) grows to infinity at a logarithmic rate. This is consistent with (Lyu and Li, 2020, Theorem 4.3).

**Proposition 3.** Under Assumptions 1–2, on the event $\mathcal{E}$, there exist $c_1, c_2, \varepsilon > 0$ and $k_0 \in \mathbb{N}$, such that for all $k \ge k_0$, $\|w_k\|$ increases and

$$c_1 \log(k) \le \|w_k\|^L \le c_2 \log(k) \quad \text{and} \quad 0 < \mathcal{L}(w_k) \le k^{-\varepsilon c_1}.$$

$$\text{In particular, } \|w_k\| \to +\infty \text{ and } \mathcal{L}(w_k) \to 0.$$

Sketch, full proof in Appendix E.. The proof follows from the next observations, which hold on the event $\mathcal{E}$, for $k$ large enough. (i) There is $\varepsilon > 0$, such that $m(u_k) \ge \varepsilon$. In particular, there are $M, C_1, C_2 > 0$, such that $C_2 e^{-M \|w_k\|^L} \le -l'(p_i(w_k)) \le C_1 e^{-\varepsilon \|w_k\|^L}$. (ii) As a result, there is $C_3 > 0$ such that

$$\|w_{k+1}\|^2 \ge \|w_k\|^2 (1 + C_3 \gamma e^{-M \|w_k\|^L} \|w_k\|^{L-2}), \quad (8)$$

which implies that $\|w_k\|$ is increasing to infinity and that there is $C_4 > 0$ such that

$$\|w_{k+1}\|^2 \le \|w_k\|^2 (1 + C_4 \gamma e^{-\varepsilon \|w_k\|^L} \|w_k\|^{L-2}). \quad (9)$$

(iii) Finally, using (8)–(9) and the Taylor’s expansion of $(1 + x)^{L/2}$ near zero, we obtain existence of constants $C_5, C_6, a > 0$, such that for $k$ large enough,

$$C_5 \gamma \le e^{a \|w_k\|^L} \left( \|w_{k+1}\|^L - \|w_k\|^L \right) \le C_6 \gamma.$$

Summing these inequalities from $k$ to $k + N$ and noticing that the expression in the middle is comparable to the integral of $e^{at}$ between $\|w_k\|^L$ and $\|w_{k+N}\|^L$, concludes the proof. $\square$

Define the set-valued map $\bar{D} : \mathbb{R}^d \to \mathbb{R}^d$ as

$$\bar{D}(w) = \text{conv}\{v : v \in D_i(w), \text{ with } i \in I(w)\}, \quad \text{where } I(w) = \{i : p_i(w) = m(w)\}. \quad (10)$$

As shown in Appendix B, it is a conservative set-valued field for the potential $m$. Note that, following Remark 14 in Appendix B, even if for all $i$, $D_i = \partial p_i$, $\bar{D}$ can be different from $\partial m$. Next, we define the set-valued field $\bar{D}_s : \mathbb{S}^{d-1} \to \mathbb{R}^d$ as

$$\bar{D}_s(u) := \{v - \langle v, u \rangle u : v \in \bar{D}(u)\}. \quad (11)$$

The associated set of critical points is then given by

$$\mathcal{Z}_s := \{u \in \mathbb{S}^{d-1} : 0 \in \bar{D}_s(u)\} \subset \mathbb{S}^{d-1}. \quad (12)$$
The field $\bar{D}_s$ and the critical points set $Z_s$ admit a straightforward interpretation. If $m$ is $C^1$ around some point $u \in \mathbb{S}^{d-1}$ and $\bar{D} = \{\nabla m\}$, then $\bar{D}_s(u)$ is the transverse component of $\nabla m(u)$, corresponding to its projection onto the tangent plane of $\mathbb{S}^{d-1}$ at $u$. From a Riemannian geometry perspective, this implies that $\bar{D}_s(u)$ is the Riemannian gradient<fnref n="5" /> of $m$ restricted to the sphere $\mathbb{S}^{d-1}$, $m|_{\mathbb{S}^{d-1}}$. Similarly, $Z_s$ corresponds to the set of critical points of $m|_{\mathbb{S}^{d-1}}$. More generally, since conservative fields are gradient-like objects (see Proposition 9 in Appendix A), we interpret $\bar{D}_s$ as the Riemannian conservative field of $m|_{\mathbb{S}^{d-1}}$, with $Z_s$ as its corresponding critical points<fnref n="6" />.

We will consider the differential inclusion (DI) associated to set-valued field $\bar{D}_s$,

$$ \dot{u}(t) \in \bar{D}_s(u(t)). \qquad (\text{DI}) $$

Under the aforementioned interpretation, this corresponds to the reversed gradient (or conservative field) flow of $m|_{\mathbb{S}^{d-1}}$.

We now show that the iterates' directions evolve according to a dynamic that approximates (DI) via an Euler-like discretization (or stochastic approximation). The proof is deferred to Section 6.

**Proposition 4.** Let Assumptions 1–2 hold. There exist three $\mathbb{R}^d$-valued sequences $(\bar{g}_k^s)$, $(r_k)$, $(\bar{\eta}_{k+1})$ and an $\mathbb{R}$-valued sequence $(\bar{\eta}_k)$ such that, for both (GD) and (SGD), the normalized direction iterates $u_k := w_k/\|w_k\|$ satisfy

$$ u_{k+1} = u_k + \bar{\eta}_k \bar{g}_k^s + \bar{\eta}_k \bar{\eta}_{k+1} + \bar{\eta}_k^2 r_k. \qquad (13) $$

Moreover, considering the filtration $(\mathcal{F}_k)_k$ where, for $k \in \mathbb{N}$, $\mathcal{F}_k$ the sigma-algebra generated by $\{w_0, \dots, w_k\}$, the following holds:

1. On the event $\mathcal{E}$, the sequence $(r_k)$ satisfies $\sup_k \|r_k\| < +\infty$.

2. The sequence $(\bar{\eta}_k)$ is positive and adapted to $(\mathcal{F}_k)$. Moreover, on the event $\mathcal{E}$, $\sum_k \bar{\eta}_k = +\infty$, and there is $c_3 > 0$ such that for sufficiently large $k$, $\bar{\eta}_k \le k^{-c_3}$.

3. For (GD), $\bar{\eta}_k = 0$. Otherwise, the sequence $(\bar{\eta}_k)$ is adapted to $(\mathcal{F}_k)$ and satisfies

$$ \mathbb{E}[\bar{\eta}_{k+1}|\mathcal{F}_k] = 0. $$

Additionally, there exists a deterministic constant $c_4 > 0$ such that $\sup_k \|\bar{\eta}_{k+1}\| < c_4$.

4. On the event $\mathcal{E}$, for any unbounded sequence $(k_j)_j$, such that $u_{k_j} \to u \in \mathbb{S}^{d-1}$, it holds that $\text{dist}(\bar{D}_s(u), \bar{g}_{k_j}^s) \to 0$.

Since Proposition 4 allows us to interpret $(u_k)$ as a discretization of (DI), it is natural to investigate the convergence properties of a solution of its continuous counterpart (DI). If $u$ is such solution, then for almost every $t \in \mathbb{R}$, there exists $v \in \bar{D}_s(u(t))$ such that $\dot{u}(t) = v - \langle v, u \rangle u$. Thus, by Definition 1, for almost every $t$, $\frac{d}{dt}m(u(t)) = \langle \dot{u}(t), v \rangle = \|\dot{u}(t)\|^2$. Therefore, for $T > 0$, we obtain

$$ m(u(T)) - m(u(0)) = \int_{0}^{T} \|\dot{u}(t)\|^2 dt. $$

This implies that $m(u(T)) \ge m(u(0))$, with strict inequality whenever $u(0) \notin Z_s$. In dynamical systems terminology, $-m$ is a Lyapunov function for (DI). In particular, it can be shown that any solution $u(t)$ to (DI) converges to $Z_s$.

Our main result, Theorem 5, establishes that the same holds true for the sequence of normalized directions: any limit point of $(u_k)$ is contained in $Z_s$. Since the sequence $(u_k)$ is bounded, it further implies that the entire sequence converges to the set of critical points $Z_s$. As discussed below, this result generalizes (Lyu and Li, 2020, Theorem 4.4) to stochastic gradient descent in the nonsmooth setting.

<footnote n="5">⁵Here, the Riemannian structure is implicitly induced from the ambient space.</footnote>

<footnote n="6">⁶As noted in (Bolte and Pauwels, 2021, Page 4, footnote), the concept of a conservative set-valued field extends naturally to functions defined on any complete Riemannian submanifold, including $\mathbb{S}^{d-1}$.</footnote>
**Theorem 5.** Under Assumptions 1–2, on the event $\mathcal{E}$, $m(u_k)$ converges to a positive limit and

$$ \mathrm{dist}(u_k, \mathcal{Z}_s) \xrightarrow{k \to +\infty} 0. \qquad (14) $$

*Proof.* The proof, which is given in Appendix D follows from Proposition 4 and some minor adaptations of recent results on stochastic approximation from Benaïm (2006); Davis et al. (2020). □

A natural question is the interpretation of membership in $\mathcal{Z}_s$. Given the Riemannian perspective on $\bar{D}_s$, it is unsurprising that belonging to $\mathcal{Z}_s$ is a necessary optimality condition for the max-margin problem. We formally prove this result in Appendix B.

**Lemma 6.** If $u^*$ is a local maximum of $m|_{\mathcal{S}^{d-1}}$, then $0 \in \bar{D}_s(u^*)$.

Thus, Theorem 5 establishes that $(u_k)$ converge to the set of $\bar{D}_s$-critical points, which is a necessary condition of optimality for $\arg\max_{u \in \mathcal{S}^{d-1}} m(u)$. Comparing our result with (Lyu and Li, 2020, Theorem 4.4), we note that, if each $D_i$ were equal to $\partial p_i$, then any limit point of $(u_k)$ would correspond exactly to a scaled KKT point from Lyu and Li (2020). In this work, the authors formulate an alternative optimization problem, namely

$$ \min\{\|w\|^2 : w \in \mathbb{R}^d, m(w) \ge 1\}. \qquad (P) $$

As discussed in Lyu and Li (2020), if there exists $w \in \mathbb{R}^d$ such that $m(w) > 0$, solving (P) is equivalent to maximizing the margin. Examining the KKT conditions (see Appendix F) of (P), we observe that for any $u \in \mathcal{Z}_s$ such that $m(u) > 0$, there exists $\lambda > 0$, such that $\lambda u$ is a KKT point. This implies that, within the setting of Theorem 5, the optimality characterization is identical to that in Lyu and Li (2020).

These observations also highlight that the appearance of a conservative field in our problem is unrelated to backpropagation. The set $\mathcal{Z}_s$ (thus, implicitly, $\bar{D}_s$) already arises in the analysis of continuous-time subgradient flow in Lyu and Li (2020). In fact, as previously noted, $\bar{D} \neq \partial m$, even if all $D_i = \partial p_i$ (see Remark 14).

However, we adopt a different perspective. Rather than linking $\mathcal{Z}_s$ directly to the KKT points of (P), we interpret it as the set of $\bar{D}_s$-critical points of the margin restricted to the sphere—where $m$ is naturally defined due to homogeneity. Moreover, our definitions of $\bar{D}_s$ and $\mathcal{Z}_s$ remain valid even when the $D_i$'s are arbitrary conservative set-valued fields, not just subgradients. In fact, our stochastic approximation interpretation allows us to consider a more general setting (see Appendix F), where in which the event $\mathcal{E}$ can be replaced by a larger event. In this broader framework, the limit points of $(u_k)$ still lie in $\mathcal{Z}_s$ without necessarily being rescaled versions of the KKT points of (P).

Finally, we note that as long as we are on “stability event” $\mathcal{E}$, our analysis allows the step-size $\gamma$ to be of arbitrary size. This may seem surprising, as (non-smooth) SGD typically requires vanishing step-sizes for convergence (Majewski et al. (2018); Davis et al. (2020); Bolte et al. (2023); Le (2024)). Mathematically, this follows from the fact that $\bar{\gamma}_k$, the effective step-size of the dynamics, is actually decreasing in our setting. A convergence analysis of constant-step SGD for smooth homogeneous linear classifiers was studied in Nacson et al. (2019c), but to the best of our knowledge, the more general non-smooth setting had not yet been addressed.

# 6 Proof of Proposition 4

In this proof, $C, C_1, C_2, \dots$ will denote some positive absolute constants that can change from equation to equation. We also note that for all $w, i, p_i(w) \le C \|w\|^L$ and, due to Assumption 2, for all $v \in D_i(w)$, $\|v\| \le C \|w\|^{L-1}$.

To obtain (13), we appropriately rescale the step-size and then write the Taylor’s expansion of $u \mapsto (u+h)/\|u+h\|$, for small $h$, using the fact that $\|w_k\| \to +\infty$.

Towards that goal, let us first introduce the (stochastic) sequence

$$ \eta_{k+1} := \frac{n_b - n}{n_b n} \sum_{i \in B_k} l'(p_i(w_k))a_i(w_k) + \frac{1}{n} \sum_{i \notin B_k} l'(p_i(w_k))a_i(w_k). \qquad (15) $$
Both (GD) and (SGD) (where for (GD), $η_k ≡ 0$) can be rewritten as

$$w_{k+1} = w_k - \frac{\gamma}{n} \sum_{i=1}^{n} l'(p_i(w_k))a_i(w_k) + \gamma \eta_{k+1}. \quad (16)$$

Now let us introduce the following notations

$$\tilde{\gamma}_k = -\gamma \|w_k\|^{L-1} \sum_{j=1}^{n} l'(p_j(w_k)), \quad \tilde{\eta}_k = \tilde{\gamma}_k \|w_k\|^{-1} \quad (17)$$

and

$$\lambda_{i,k} = \frac{l'(p_i(w_k))}{\sum_{j=1}^{n} l'(p_j(w_k))}, \quad \tilde{\eta}_{k+1} = \frac{-\eta_{k+1}}{\|w_k\|^{L-1} \sum_{j=1}^{n} l'(p_j(w_k))}. \quad (18)$$

Note that since $l'(q) < 0$, for all $k$, $\tilde{\gamma}_k$, $\bar{\gamma}_k$, $\lambda_{i,k} \ge 0$. Moreover, $\sum_{i=1}^n \lambda_{i,k} = 1$.

By Assumption 2 for each $i, k$, it holds that $v_{i,k} = \|w_k\|^{L-1} g_{i,k}$, where $g_{i,k} \in D_i(u_k)$. Thus, we can rewrite Equation (16) as:

$$w_{k+1} = w_k + \tilde{\gamma}_k \sum_{i=1}^{n} \lambda_{i,k} g_{i,k} + \tilde{\gamma}_k \tilde{\eta}_{k+1} := w_k + \tilde{\gamma}_k \bar{g}_k + \tilde{\gamma}_k \tilde{\eta}_{k+1}, \quad (19)$$

with $\bar{g}_k = \sum_{i=1}^n \lambda_{i,k} g_{i,k}$. Therefore, using the definition of $\tilde{\gamma}_k$ is (17),

$$u_{k+1} = \frac{w_k + \tilde{\gamma}_k \bar{g}_k + \tilde{\gamma}_k \tilde{\eta}_{k+1}}{\|w_k + \tilde{\gamma}_k \bar{g}_k + \tilde{\gamma}_k \tilde{\eta}_{k+1}\|} = \frac{u_k + \bar{\gamma}_k \bar{g}_k + \bar{\gamma}_k \tilde{\eta}_{k+1}}{\|u_k + \bar{\gamma}_k \bar{g}_k + \bar{\gamma}_k \tilde{\eta}_{k+1}\|}. \quad (20)$$

Using the Taylor's expansion $\|u+h\|^{-1} = 1 - \langle u, h \rangle + O(\|h\|^2)$, for $u \in \mathbb{S}^{d-1}$, we obtain

$$u_{k+1} = (u_k + \tilde{\gamma}_k \bar{g}_k + \tilde{\gamma}_k \tilde{\eta}_{k+1})(1 - \tilde{\gamma}_k \langle \bar{g}_k, u_k \rangle - \tilde{\gamma}_k \langle \tilde{\eta}_{k+1}, u_k \rangle + b_k) = u_k + \tilde{\gamma}_k \bar{g}_k^s + \tilde{\gamma}_k \tilde{\eta}_{k+1} + \tilde{\gamma}_k^2 r_k, \quad (21)$$

where $b_k$ is such that $|b_k| \le C \tilde{\gamma}_k^2 (\|\bar{g}_k\| + \|\tilde{\eta}_{k+1}\|)^2$, as soon as $\tilde{\gamma}_k \|\bar{g}_k + \tilde{\eta}_{k+1}\| \le 1/2$, and

$$\tilde{\eta}_{k+1} := \tilde{\eta}_{k+1} - \langle \tilde{\eta}_{k+1}, u_k \rangle u_k \quad \text{and} \quad \bar{g}_k^s := \bar{g}_k - \langle \bar{g}_k, u_k \rangle u_k, \quad (22)$$

and, finally,

$$\tilde{\gamma}_k^2 \|r_k\| \le |b_k| \|(u_k + \tilde{\gamma}_k \bar{g}_k + \tilde{\gamma}_k \tilde{\eta}_{k+1})\| + \tilde{\gamma}_k^2 \|(\bar{g}_k + \tilde{\eta}_{k+1})\langle \bar{g}_k + \tilde{\eta}_{k+1}, u_k \rangle\|. \quad (23)$$

Equation (21) correspond to (13). We now briefly prove the four points of the proposition.

Claim on $(\bar{\eta}_k)$. The fact that $\eta_k$ and thus $\bar{\eta}_k$ is $w_k$-measurable is immediate by its definition in (15). Additionally, $\mathbb{E}[\bar{\eta}_{k+1}^s | \mathcal{F}_k] = \mathbb{E}[\eta_{k+1} | \mathcal{F}_k] = 0$. Moreover, Assumption 2 and Equation (15) implies

$$\|\eta_{k+1}\| \le C_1 \left\| \sum_{i=1}^{n} l'(p_i(w_k))a_i(w_k) \right\| \le C_2 \|w_k\|^{L-1} \sum_{i=1}^{n} |l'(p_i(w_k))|,$$

with $C_2 > 0$ some deterministic constant independent on $k$. Therefore, by (18) and (22), $\|\bar{\eta}_{k+1}\| \le \|\tilde{\eta}_{k+1}\| \le C_2$.

Claim on $(\tilde{\gamma}_k)$. Almost surely on $\mathcal{E}$, there is $\varepsilon > 0$, such that for $k$ large enough, $m(u_k) \ge \varepsilon$. Thus, for every $i$, $l'(p_i(w_k)) \le e^{-\varepsilon \|w_k\|^L}$. By Assumption 2, $\|a_i(w_k)\| \le C \|w_k\|^{L-1}$, which implies for $k$ large enough,

$$\bar{\gamma}_k \le C_1 \|w_k\|^{L-2} e^{-\varepsilon \|w_k\|^L} \le \frac{C_1 c_2 \log(k)^{L-2}}{k^{\varepsilon c_1}} \le \frac{1}{\sqrt{k}^{\varepsilon c_1}}$$

where the penultimate inequality comes from Proposition 3. To show that $\sum_k \bar{\gamma}_k = +\infty$, note that using Equation (19), on the event $\mathcal{E}$, we have for $k$ large enough,

$$\begin{aligned} \|w_{k+1}\|^2 &\le \|w_k\|^2 + 2\tilde{\gamma}_k \|w_k\| \|\bar{g}_k + \tilde{\eta}_{k+1}\| + \tilde{\gamma}_k^2 \|\bar{g}_k + \tilde{\eta}_{k+1}\|^2 \\ &\le \|w_k\|^2 (1 + C\bar{\gamma}_k + C_1\bar{\gamma}_k^2) \le \|w_k\|^2 e^{C_2\bar{\gamma}_k} \le \|w_{k_0}\|^2 e^{C_2 \sum_{i=k_0}^k \bar{\gamma}_i} \end{aligned} \quad (24)$$
where $k_0$ is large enough, and where we have used the fact that $\sup_k (\|\bar{g}_k + \tilde{\eta}_{k+1}\|) < +\infty$ and that $\tilde{\gamma}_k \to 0$ on $\mathcal{E}$. Since the left-hand side of Equation (24) goes to infinity on $\mathcal{E}$ by Proposition 3, we obtain that the right-hand side diverge to infinity and therefore, on $\mathcal{E}$, $\sum_k \tilde{\gamma}_k = +\infty$.

*Claim on (r_k)*. Since on $\mathcal{E}$, $\tilde{\gamma}_k \to 0$, $\sup_k \|\tilde{\eta}_{k+1}\| \le C_1$ and $\sup_k \|\bar{g}_k\| < C_2$, there is $k_0$, such that for all $k \ge k_0$, $\tilde{\gamma}_k (\|\bar{g}_k\| + \|\tilde{\eta}_{k+1}\|) \le 1/2$. Therefore, for $k \ge k_0$, $|b_k| \le C \gamma_k^2 \|\bar{g}_k + \tilde{\eta}_{k+1}\|$ in (21), which by (23) implies that $\sup_{k \ge k_0} \|r_k\| \le C$.

*Claim on $\bar{D}$.* Consider a sequence $u_{k_j} \to u$ and $g$ any accumulation point $g_{k_j}$, we need to prove that $g - \langle g, u \rangle u \in \bar{D}_s(u)$, or, equivalently, that $g \in \bar{D}(u)$. Recall that $\bar{g}_k = \sum_{i=1}^k \lambda_{i,k} \bar{g}_{i,k}$, where $\lambda_{i,k} \ge 0$, $\sum_i \lambda_{i,k} = 1$ and $g_{i,k} \in D_i(u_k)$. Extracting a subsequence, we can assume that for each $i$, $\lambda_{i,k_j} \to \lambda_i$ and $g_{i,k_j} \to g_i \in D_i(u)$. We claim that $\lambda_i \ne 0 \implies p_i(u) = m(u)$. Indeed, without losing generality assume that $p_1(u_{k_j}) \to m(u)$. Then, if $\lim(p_i(u_k) - m(u)) > 0$, on $\mathcal{E}$ we obtain

$$ \lambda_{i,k_j} \le \frac{l'(\|w_{k,j}\|^L p_i(u_{k_j}))}{l'(\|w_{k_j}\|^L p_1(u_{k_j}))} \le Ce^{-\|w_k\|^L (p_i(u_k)-m(u))} \xrightarrow{j \to +\infty} 0. $$

Therefore, $g$ can be written as $\sum_{i=1}^n \lambda_i g_i$, where $g_i \in D_i(u)$ and $\lambda_i \ne 0 \implies p_i(u) = m(u)$. In other words, $g \in \bar{D}(u)$, concluding the proof. ■

## Acknowledgement

The authors thank Evgenii Chzhen for insightful discussions.

## References

Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https://www.tensorflow.org/. Software available from tensorflow.org.

Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. *Proceedings of the National Academy of Sciences*, 116 (32):15849–15854, 2019.

Michel Benaïm. Dynamics of stochastic approximation algorithms. In *Seminaire de probabilites XXXIII*, pages 1–68. Springer, 2006.

Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. *SIAM Journal on Control and Optimization*, 44(1):328–348, 2005.

Edward Bierstone and Pierre D Milman. Semianalytic and subanalytic sets. *Publications Mathématiques de l'IHÉS*, 67:5–42, 1988.

J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota. Clarke subgradients of stratifiable functions. *SIAM Journal on Optimization*, 18(2):556–572, 2007.

Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. *Mathematical Programming*, 188:19–51, 2021.

Jérôme Bolte, Tam Le, and Edouard Pauwels. Subgradient sampling for nonsmooth nonconvex minimization. *SIAM Journal on Optimization*, 33(4):2542–2569, 2023.
Vivek S Borkar. *Stochastic approximation: a dynamical systems viewpoint*, volume 9. Springer, 2008.

Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. *SIAM Journal on Control and Optimization*, 38(2):447–469, 2000.

Nicolas Boumal. *An introduction to optimization on smooth manifolds*. Cambridge University Press, 2023.
doi: 10.1017/9781009166164. URL https://www.nicolasboumal.net/book.

Yuhang Cai, Jingfeng Wu, Song Mei, Michael Lindsey, and Peter Bartlett. Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast optimization. *Advances in Neural Information Processing Systems*, 37:71306–71351, 2024.

Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In *Conference on learning theory*, pages 1305–1338. PMLR, 2020.

Francis H Clarke, Yuri S Ledyaev, Ronald J Stern, and Peter R Wolenski. *Nonsmooth analysis and control theory*, volume 178. Springer-Verlag, New York, 1998.

Michel Coste. *An introduction to o-minimal geometry*. Istituti editoriali e poligrafici internazionali Pisa, 2000.

Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. *Foundations of computational mathematics*, 20(1):119–154, 2020.

Dmitriy Drusvyatskiy, Alexander D Ioffe, and Adrian S Lewis. Curves of descent. *SIAM Journal on Control and Optimization*, 53(1):114–138, 2015.

Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. *Advances in neural information processing systems*, 31, 2018.

John C Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimization problems. *SIAM Journal on Optimization*, 28(4):3229–3259, 2018.

François Fleuret. The little book of deep learning. *A lovely concise introduction*, page 297, 2023.

Andrei Gabrielov. Complements of subanalytic sets and existential formulas for analytic functions. *Inventiones mathematicae*, 125(1):1–12, 1996.

Andrei M Gabrielov. Projections of semi-analytic sets. *Functional Analysis and its applications*, 2(4):282–291, 1968.

Ian Goodfellow. *Deep learning*, volume 196. MIT press, 2016.

Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer G. Dy and Andreas Krause, editors, *Proceedings of the 35th International Conference on Machine Learning*, ICML 2018, *Stockholmsmässan*, Stockholm, Sweden, July 10-15, 2018, volume 80 of *Proceedings of Machine Learning Research*, pages 1827–1836. PMLR, 2018a. URL http://proceedings.mlr.press/v80/gunasekar18a.html.

Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. *Advances in neural information processing systems*, 31, 2018b.

Alexander D Ioffe. An invitation to tame optimization. *SIAM Journal on Optimization*, 19(4):1894–1917, 2009.

Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. *arXiv preprint arXiv:1810.02032*, 2018a.

Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. *arXiv preprint arXiv:1803.07300*, 2018b.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. *Advances in Neural Information Processing Systems*, 33:17176–17186, 2020.

Cédric Josz and Lexiao Lai. Global stability of first-order methods for coercive tame functions. *Mathematical Programming*, 207(1):551–576, 2024.

Daniel Kunin, Atsushi Yamamura, Chao Ma, and Surya Ganguli. The asymmetric maximum margin bias of quasi-homogeneous neural networks. *arXiv preprint arXiv:2210.03820*, 2022.

Jacques Lafontaine. *An Introduction to Differential Manifolds*. Springer International Publishing, 2015. doi: 10.1007/978-3-319-20735-3. URL https://doi.org/10.1007/2F978-3-319-20735-3.

Tam Le. Nonsmooth nonconvex stochastic heavy ball. *Journal of Optimization Theory and Applications*, 201(2):699–719, 2024.

Thien Le and Stefanie Jegelka. Training invariances and the low-rank phenomenon: beyond linear networks. *arXiv preprint arXiv:2201.11968*, 2022.

Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In *8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020*. OpenReview.net, 2020. URL https://openreview.net/forum?id=SJeLIgBKPS.

Szymon Majewski, Błażej Miasojedow, and Eric Moulines. Analysis of nonsmooth stochastic approximation: the differential inclusion approach. *arXiv preprint arXiv:1805.01916*, 2018.

Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In *International Conference on Machine Learning*, pages 4683–4692. PMLR, 2019a.

Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In *The 22nd International Conference on Artificial Intelligence and Statistics*, pages 3420–3428. PMLR, 2019b.

Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In *The 22nd International Conference on Artificial Intelligence and Statistics*, pages 3051–3059. PMLR, 2019c.

Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In Yoshua Bengio and Yann LeCun, editors, *3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings*, 2015. URL http://arxiv.org/abs/1412.6614.

Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.

Arunselvan Ramaswamy and Shalabh Bhatnagar. A generalization of the borkar-meyn theorem for stochastic recursive inclusions. *Mathematics of Operations Research*, 42(3):648–661, 2017.

Arthur Sard. The measure of the critical values of differentiable maps. *Bull. Amer. Math. Soc.*, 48(12): 883–890, 1942. URL http://dml.mathdoc.fr/item/1183504867.

Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. *Journal of Machine Learning Research*, 19(70):1–57, 2018.

Alfred Tarski. A decision method for elementary algebra and geometry. In *Quantifier elimination and cylindrical algebraic decomposition*, pages 24–84. Springer, 1951.

Lou Van den Dries. *Tame topology and o-minimal structures*, volume 248. Cambridge university press, 1998.
Lou van den Dries and Chris Miller. Geometric categories and o-minimal structures. Duke Math. J., 85(1): 497-540, 1996.

Lou van den Dries, Angus Macintyre, and David Marker. The elementary theory of restricted analytic fields with exponentiation. Annals of Mathematics, 140(1):183–205, 1994.

Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003-4.

Gal Vardi. On the implicit bias in deep-learning algorithms. Communications of the ACM, 66(6):86–93, 2023.

Gal Vardi, Ohad Shamir, and Nati Srebro. On margin maximization in linear and relu networks. Advances in Neural Information Processing Systems, 35:37024–37036, 2022.

Bohan Wang, Qi Meng, Wei Chen, and Tie-Yan Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In International Conference on Machine Learning, pages 10849–10858. PMLR, 2021.

Alex Wilkie. Model completeness results for expansions of the ordered field of real numbers by restricted pfaffian functions and the exponential function. Journal of the American Mathematical Society, 9(4): 1051–1094, 1996.

Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. arXiv preprint arXiv:2010.02501, 2020.

Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107–115, 2021.
# A o-minimal structures

In every statement of this paper semialgebraic can be replaced by definable in a fixed o-minimal structure. We collect here some useful facts about definable sets and maps. In particular, Proposition 9, that provides a variational description of a definable conservative set-valued field of a definable potential, will be used in Appendix D to prove Theorem 5.

For more details on o-minimal structure we refer to the monographs Coste (2000); Van den Dries (1998); van den Dries and Miller (1996). A nice review of their importance in optimization is Ioffe (2009).

The definition of an o-minimal structure is inspired by properties that are satisfied by semialgebraic sets.

**Definition 7.** We say that $O := (O_n)$, where for each $n \in \mathbb{N}$, $O_n$ is a collection of sets in $\mathbb{R}^n$, is an o-minimal structure if the following holds.

i) If $Q : \mathbb{R}^n \to \mathbb{R}$ is a polynomial, then $\{x \in \mathbb{R}^n : Q(x) = 0\} \in O_n$.

ii) For each $n \in \mathbb{N}$, $O_n$ is a boolean algebra: if $A, B \in O_n$, then $A \cup B, A \cap B$ and $A^c$ are in $O_n$.

iii) If $A \in O_n$ and $B \in O_m$, then $A \times B \in O_{n+m}$.

iv) If $A \in O_{n+1}$, then the projection of $A$ onto its first $n$ coordinates is in $O_n$.

v) Every element of $O_1$ is exactly a finite union of intervals and points of $\mathbb{R}$.

Sets contained in $O$ are called definable. We call a map $f : \mathbb{R}^d \to \mathbb{R}^m$ definable if its graph is definable. Similarly, $D : \mathbb{R}^d \to \mathbb{R}^d$ is definable if $\text{Graph } D = \{(w, v) : v \in D(w)\}$ is definable. Definable sets and maps have remarkable stability properties. For instance, if $f$ and $A$ are definable, then $f(A)$ and $f^{-1}(A)$ are definable and definability is stable by most of the common operators such as $\{+, -, \times, \circ, \circ^{-1}\}$. Let us look at some examples of o-minimal structures.

**Semialgebraic.** Semialgebraic sets form an o-minimal structure. This follows from the celebrated result of Tarski Tarski (1951).

**Globally subanalytic.** There is an o-minimal structure that contains, for every $n \in \mathbb{N}$, sets of the form $\{(x, t) : t = f(x)\}$, where $f : [-1, 1]^n \to \mathbb{R}$ is an analytic function. This comes from the fact that subanalytic sets are stable by projection, which was established by Gabrielov Gabrielov (1968, 1996). The sets belonging to this structure are called globally subanalytic (see Bierstone and Milman (1988) for more details).

**Log-exp.** There is an o-minimal structure that contains, semialgebraic sets, globally sub-analytic sets as well as the graph of the exponential and the logarithm (see Wilkie (1996); van den Dries et al. (1994)).

With these examples in mind it is usually easy to verify that a function is definable. This will be the case as soon as the function is constructed by a finite number of definable operations on definable functions. From this, we see that most of neural networks architectures are definable in the structure Log-exp.

Let us record here a striking fact. The domain of a definable function can be always partitioned in manifolds such that $f$ is differentiable on each set of this partition. Before stating this result we briefly introduce to the reader some basics of differential geometry. We refer to the monographs Lafontaine (2015); Boumal (2023) for a more detailed introduction on these notions.

**Submanifolds, tangent spaces and Riemannian gradients.** A set $\mathcal{X} \subset \mathbb{R}^d$ is said to be a $k$-dimensional $C^p$-manifold if for every $x \in \mathcal{X}$, there is a neighborhood $\mathcal{U} \subset \mathbb{R}^d$ of $x$ and a $C^p$ function $g : \mathcal{U} \to \mathbb{R}^{d-k}$ such that the Jacobian of $g$ at every point of $\mathcal{U}$ is of full rank. The tangent space of $\mathcal{X}$ at $x$ is $\mathcal{T}_{\mathcal{X}}(x) = \ker Jac g(x)$. Equivalently, it is the set of vectors $v \in \mathbb{R}^d$ such that there is $\varepsilon > 0$ and a $C^1$ curve $u : (-\varepsilon, \varepsilon) \to \mathcal{X}$, such that $(u(0), \dot{u}(0)) = (x, v)$.

We say that a function $f : \mathcal{X} \to \mathbb{R}$ is $C^p$ if around every $x$ there is a neighborhood $\mathcal{U} \subset \mathbb{R}^d$ and a $C^p$ function $\tilde{f} : \mathcal{U} \to \mathbb{R}$ such that $\tilde{f}|_{\mathcal{U}} = f|_{\mathcal{U}}$. For such $f$ and $x \in \mathcal{X}$, the Riemannian gradient (here, we implicitly induce the Riemannian structure from the ambient space) of $f$ at $x$, is

$$ \nabla_{\mathcal{X}} f(x) := P_{\mathcal{T}_{\mathcal{X}}(x)} \nabla \tilde{f}(x), \qquad (25) $$
where $P_{\mathcal{T}_{\mathcal{X}}(x)}$ is the orthogonal projection onto $\mathcal{T}_{\mathcal{X}}(x)$. This definition is independent of the smooth representative $\tilde{f}$.

For the following two propositions we fix a definable structure $\mathcal{O}$ (e.g., semialgebraic sets) and definable will mean definable in $\mathcal{O}$.

**Proposition 8** (Van den Dries, 1998, 4.8)). Consider a definable $f: \mathbb{R}^d \to \mathbb{R}$. For every $p > 0$, there is $(\mathcal{X}_i)_{1 \le i \le l}$ a finite partition $^7$ of $\mathbb{R}^d$ into $\mathbb{C}^p$ submanifolds such that for every $i$, $f|_{\mathcal{X}_i}$ is $\mathbb{C}^p$, in the sense of differential geometry. Moreover, if $M \subset \mathbb{R}^d$ is definable, then this partition can be chosen such that there is $\mathcal{I} \subset \{1, \dots, l\}$ for which $M = \bigcup_{i \in \mathcal{I}} \mathcal{X}_i$.

Furthermore, the partition can be chosen in a way that along the tangent directions $D(w)$ is simply the Riemannian gradient of $f$. This will be useful in our proof of Theorem 5.

**Proposition 9** (Bolte and Pauwels, 2021, Theorem 4)). Consider a definable, locally Lipschitz continuous $f: \mathbb{R}^d \to \mathbb{R}$ a potential of a definable conservative set-valued field $D: \mathbb{R}^d \to \mathbb{R}^d$. For any $p > 0$, there is a partition $(\mathcal{X}_i)_{1 \le i \le l}$ such that the result of Proposition 8 holds and, moreover, for any $w \in \mathcal{X}_i$,

$$P_{\mathcal{T}_{\mathcal{X}_i}(w)} D(w) = \{\nabla_{\mathcal{X}_i} f(w)\}^8.$$

Moreover, if $M \subset \mathbb{R}^d$ is definable, then this partition can be chosen such that there is $\mathcal{I} \subset \{1, \dots, l\}$, for which $M = \bigcup_{i \in \mathcal{I}} \mathcal{X}_i$.

**Remark 10.** The last point of Proposition 9 is not formally stated in (Bolte and Pauwels, 2021, Theorem 4). Nevertheless, in its proof, the first stage of the construction of $(\mathcal{X}_i)$ is based on Proposition 8. Thus, at this stage we can use the last point of Proposition 8 (i.e. the one of (Van den Dries, 1998, 4.8)) and obtain the stated result.

# B Conservative mappings

The purpose of this section is to prove the fact that $i) \bar{D}$ from Equation (11) is a conservative set-valued field of $m$, ii) Lemma 6.

First, we introduce a generalization of conservative fields to vector-valued functions.

**Definition 11** (Bolte and Pauwels (2021)). For a locally Lipschitz function $f = (f_1, \dots, f_m): \mathbb{R}^d \to \mathbb{R}^m$, a set-valued map $J: \mathbb{R}^d \to \mathbb{R}^{m \times d}$ is said to be a conservative mapping for $f$ if for every $1 \le i \le m$ the $i$-th row of $J$ is a conservative field for $f_i$.

One of the issue of the Clarke subgradient is that it is not closed under composition. That is to say, if $f, g: \mathbb{R} \to \mathbb{R}$ are locally Lipschitz we do not necessarily have $\partial(f \circ g) = \partial f \times \partial g$. On the contrast, product of conservative mapping remains conservative. This is the main reason why the backpropagation algorithm outputs an element of a conservative set-valued field.

**Proposition 12** (Bolte and Pauwels, 2021, Lemma 5)). Consider $f: \mathbb{R}^d \to \mathbb{R}^m$, $g: \mathbb{R}^m \to \mathbb{R}^l$ two locally Lipschitz continuous functions with $D_f: \mathbb{R}^d \to \mathbb{R}^{m \times d}$, $D_g: \mathbb{R}^m \to \mathbb{R}^{l \times m}$ two corresponding conservative mappings. The set-valued map

$$D_{g \circ f}: w \mapsto \{J \in \mathbb{R}^{l \times m}: J = J_2 J_1, \text{ with } J_f \in D_f(w) \text{ and } J_g \in D_g(f(w))\}$$

is a conservative mapping of $g \circ f$.

In the context of the paper, $p_1, \dots, p_n: \mathbb{R}^d \to \mathbb{R}$ are semialgebraic potentials of semialgebraic conservative set-valued fields $D_1, \dots, D_n$. Recall that $m(w) = \min_i p_i(w)$ and the definition $\bar{D}$ in (10). We now have the tools to prove that $\bar{D}$ is a conservative set-valued field of $m$.

**Lemma 13.** The map $\bar{D}: \mathbb{R}^d \to \mathbb{R}^d$ is a semialgebraic conservative set-valued field for the potential $m$.

<footnote n="7">⁷This partition also satisfies some important properties and is usually called a stratification.</footnote>

<footnote n="8">⁸Note the similarity with (25).</footnote>
**Proof.** The fact that Graph $\bar{D}$ is semialgebraic comes from the fact that it is constructed from finite semi-algebraic operations involving only semialgebraic sets. To prove that $\bar{D}$ is a conservative set-valued field note that $m$ can be written as a composition of semialgebraic functions:

$$w \stackrel{\varphi_1}{\rightleftharpoons} (p_1(w), \dots, p_n(w)) \stackrel{\varphi_2}{\rightleftharpoons} \min(p_1(w), \dots, p_n(w))$$

Then, $D_p(w) = [D_1(w), \dots, D_n(w)]^\top$ is a conservative mapping of $\varphi_1$ and $(x_1, \dots, x_n) \Rightarrow \text{conv}\{e_i : x_i = \min(x_1, \dots, x_n)\}$, where $e_i \in \mathbb{R}^n$ is the $i$-the element of the canonical basis, is the Clarke subgradient (and thus a conservative gradient) of $\varphi_2$. The claim follows from Proposition 12 and the fact that conservativity is stable by convexity. $\square$

**Remark 14.** Even if $D_1, \dots, D_n$ are Clarke subgradients, $\bar{D}$ is not necessarily a Clarke subgradient. For instance, if $n = 2$, $p_1(w) = \min(0, w)$ and $p_2(w) = \min(0, -w)$, then $m(w) = 0$ and for any $w \neq 0$, $\bar{D}(w) = \{0\}$. Nevertheless, $\bar{D}(0) = [-1, 1]$. Thus, conservative set-valued fields appear naturally in the analysis of our problem, independently of the use of backpropagation.

We finish this section by a proof of Lemma 6. Note that $\mathbb{S}^{d-1} = \{u \in \mathbb{R}^d : \|u\| = 1\} = g^{-1}(0)$, with $g(w) = \|w\|^2$. Therefore, $\mathbb{S}^{d-1}$ is a $d-1$ dimensional $C^\infty$-manifold and for every $u \in \mathbb{S}^{d-1}$,

$$\mathcal{T}_{\mathbb{S}^{d-1}}(u) = \{v - \langle v, u \rangle : v \in \mathbb{R}^d\}. \qquad (26)$$

**Proof of Lemma 6.** Assume the contrary and consider $v_s \in \arg\min\{\|v'_s\| : v'_s \in \bar{D}_s(u^*)\}$. Since $v_s$ is in the tangent space of $\mathbb{S}^{d-1}$ at $u^*$, there is a $C^1$ curve $u : (-\varepsilon, \varepsilon) \to \mathbb{S}^{d-1}$ such that $u(0) = u^*$ and $\dot{u}(0) = v_s$. Moreover, since $\bar{D}_s(u^*)$ is convex and $v_s$ is its element of minimal norm, for any $v'_s \in D(u^*)$, $\langle v_s, v'_s \rangle \ge \|v_s\|^2 > 0$.

Since Graph $\bar{D}_s$ is closed, it also holds, for $t \ge 0$ small enough, that for any $v'_s \in \bar{D}_s(u(t))$, $2\langle v_s, v'_s \rangle \ge \|v_s\|^2$ and, thus, for $t$ small enough, $4\langle v'_s, \dot{u}(t) \rangle \ge \|v_s\|^2$.

In particular, for almost every $t \in [0, \delta]$, for $\delta$ small enough, and every $v \in \bar{D}(u(t))$,

$$\frac{d}{dt}m(u(t)) = \langle v, \dot{u}(t) \rangle = \langle v - \langle v, u(t) \rangle u(t), \dot{u}(t) \rangle \ge \frac{1}{4} \|v_s\|^2 > 0,$$

where we have used that $v - \langle v, u(t) \rangle u(t) \in \bar{D}_s(u(t))$ and that $\langle u(t), \dot{u}(t) \rangle = 0$. Therefore, $m$ strictly increase on $[0, \delta]$, which contradicts the fact that $u^*$ is a local maximum. $\square$

## C Discretization of differential inclusions

**Differential inclusions.** Consider $B \subset \mathbb{R}^d$. We say that $H$ is a set-valued map from $B$ to $\mathbb{R}^d$, denoted $H: B \rightleftharpoons \mathbb{R}^d$, if for every $w \in B$, $H(w)$ is a subset of $\mathbb{R}^d$. We say that $H$ is graph-closed if Graph $H := \{(w, v) : v \in H(w)\}$ is closed. It is said to have nonempty (respectively convex) values if for every $w \in B$, $H(w)$ is nonempty (respectively convex). It is said to be locally bounded, if every $w \in \mathbb{R}^d$ admits a neighborhood $U$ of $w$ and $M > 0$, such that for every $w' \in U$, and $v \in H(w')$, $\|v\| \le M$.

**Differential inclusions and Lyapunov functions.** To every such $H$ we can associate a differential inclusion (DI):

$$\dot{u}(t) \in H(u(t)). \qquad (27)$$

We say that $u : \mathbb{R}_+ \to B$ is a solution to (27), if Equation (27) is satisfied for almost every $t \ge 0$. A continuous function $\Lambda : B \to \mathbb{R}$ is said to be a Lyapunov function of (27) for a set $\mathcal{Z} \subset B$, if for every solution $u$ of (27),

$$\Lambda(u(t)) \le \Lambda(u(0)),$$

with strict inequality as soon as $u(0) \notin \mathcal{Z}$.

In the context of our paper, we are of course interested in the case where $B = \mathbb{S}^{d-1}$ and $H = \bar{D}_s$. In such case, as explained before the statement of Theorem 5, $-m$ is a Lyapunov function for the set $\mathcal{Z}_s$.
**Discretization of differential inclusions.** Consider a $\mathbb{R}^d$-valued sequence $(u_k)$, satisfying the following recursion:

$$u_{k+1} = u_k + \gamma_k v_k + \gamma_k e_k,$$

where $(\gamma_k)$ is a sequence of positive stepsizes, where $v_k, e_k \in \mathbb{R}^d$. In practice, $v_k$ will be chosen close to an element of $H(u_k)$, with $H$ some set-valued map (in our setting $H = \bar{D}_s$), and $(e_k)$ will represent some (stochastic) perturbations that will vanish when $k \to +\infty$. Hence, one can view this algorithm as an Euler-like discretization of the DI associated to $H$.

Under mild assumptions, under a presence of a Lyapunov function, we can characterize the accumulation points of $(u_k)$. The first such result was established in the seminal work of Benaïm et al. (2005). Similar statements were lately proved in Duchi and Ruan (2018); Borkar (2008); Davis et al. (2020). Here we use a version of the result proved in (Davis et al., 2020, Theorem 3.2).

To state the proposition, for every $T > 0$ and $k \in \mathbb{N}$, we define

$$n(k, T) = \sup \left\{ l \geq k : \sum_{i=k}^{l} \gamma_i \leq T \right\}.$$

**Proposition 15.** Let $B \subset \mathbb{R}^d$ be closed and let $H: B \to \mathbb{R}^d$ be a graph-closed set-valued map, with convex and nonempty values. Assume the following.

i) The sequences $(u_k), (v_k)$ are bounded and any accumulation point of $(u_k)$ lies in $B$.

ii) $(\gamma_k)$ is a sequence of positive numbers such that $\sum_k \gamma_k = +\infty$ and $\gamma_k \to 0$.

iii) For every $T > 0$,

$$\lim_{k \to +\infty} \sup \left\{ \left\| \sum_{i=k}^{l} \gamma_i e_i \right\| : k \le l \le n(k, T) \right\} = 0.$$

iv) There is $\Lambda: B \to \mathbb{R}$, a Lyapunov function associated with (27) and the set $\mathcal{Z} = \{u \in B: 0 \in H(u)\}$, such that $\Lambda(\mathcal{Z})$ is of empty interior.

v) For any unbounded sequence $(k_j)$, such that $(u_{k_j})$ converges to some $u \in B$, it holds that

$$\lim_{j \to +\infty} \mathrm{dist}(H(u), v_{k_j}) = 0 \qquad (28)$$

Then the limit points of $(u_k)$ are in $\mathcal{Z}$ and the sequence $\Lambda(u_k)$ converges.

The statement of (Davis et al., 2020, Theorem 3.2) have slightly different assumptions on $H$, $(e_k)$ and $(\gamma_k)$, and we devote the end of this section to describe how to adapt their proof to obtain our statement.

The only difference between Proposition 15 and (Davis et al., 2020, Theorem 3.2) are the following.

1. In (Davis et al., 2020, Theorem 3.2) there are no assumptions on $H$ and (28) is replaced by

$$\lim_{N \to +\infty} \mathrm{dist} \left( H(u), \frac{1}{N} \sum_{j=1}^{N} v_{k_j} \right) = 0.$$

2. In (Davis et al., 2020, Theorem 3.2) there is a requirement that $\sum_k \gamma_k^2 < +\infty$ and that $\sum_k \gamma_k e_k$ converges.

The only part in the proof of (Davis et al., 2020, Theorem 3.2) where these two points are needed are in their use of (Davis et al., 2020, Theorem 3.1) which corresponds to (Duchi and Ruan, 2018, Theorem 3.7). To state the result let us first define $\tau_k = \sum_{i=0}^{k} \gamma_i$ and the linearly interpolated processes $U$ as

$$U(t) = u_k + \frac{t - \tau_k}{\gamma_{k+1}} (u_{k+1} - u_k) \quad \text{if } t \in [\tau_k, \tau_{k+1}].$$
**Proposition 16** (Benaïm et al., 2005, Theorem 4.2)(Duchi and Ruan, 2018, Theorem 3.7)).

For any $T > 0$ and any sequence $t_k \to +\infty$, we can extract a subsequence $(k_j)$ such that there is a continuous $u : [0, T] \to \mathbb{R}^d$, for which,

$$ \lim_{j \to +\infty} \sup_{h \in [0, T]} \|U(t_{k_j} + h) - u(h)\| = 0, $$

and $u$ is a solution to (27).

This result holds under our assumptions. The idea of the proof is standard and goes back to (Benaïm et al., 2005, Proof of Theorem 4.2).

Indeed, define piecewise constant processes $V, E : \mathbb{R}_+ \to \mathbb{R}^d$ as

$$ \text{for } t \in [\tau_k, \tau_{k+1}), \quad V(t) = v_k, \quad E(t) = e_k. $$

Note that for any $t, h > 0$,

$$ U(t+h) = U(t) + \int_t^{t+h} (V(t') + E(t')) dt'. $$

Moreover, from our assumptions on $(\gamma_k), (e_k)$, it holds that

$$ \lim_{t \to +\infty} \left\| \sup_{h \in [0, T]} \int_t^{t+h} (E(t')) dt' \right\| = 0. $$

Therefore, fixing $t_k \to +\infty$, and proceeding as in (Benaïm et al., 2005, Proof of Theorem 4.2), there is $v, u : [0, T] \to +\infty$ and an extracted sequence $(k_j)$ such that

$$ \lim_{j \to +\infty} \sup_{h \in [0, T]} \|U(t_{k_j} + h) - u(h)\| = 0, $$

and for any $h \in [0, T]$,

$$ u(h) = u(0) + \int_0^h v(t') dt', $$

Moreover, for almost every $t' \in [0, T]$, there is a sequence $(\tilde{v}_{k_j})$ such that for each $j$, $\tilde{v}_{k_j}$ is a finite convex combination of elements in $\{V(t_{k_{j'}} + t') : j' \ge j\}$ and such that

$$ v(t') = \lim_{j \to +\infty} \tilde{v}_{k_j} \in H(u(t')), $$

where the last inclusion comes from (v) and the fact that $H$ is convex-valued. Consequently, we obtain for almost every $t' \in [0, T]$, $\dot{u}(t') = v(t') \in H(u(t'))$, which shows the statement of Proposition 16 and thus the one of Proposition 15.

# D Proof of Theorem 5

To obtain Theorem 5, we only need to check the assumptions of Proposition 15 on the event $\mathcal{E}$, with $H = \bar{D}_s, \Lambda = -m, v_k = \bar{g}_k^s$ and $e_k = \eta_{k+1} + \gamma_k r_k$.

**Boundedness of $(u_k)$ and $(\bar{g}_k^s)$**. For each $k$, $\|u_k\| = 1$. The fact that $(\bar{g}_k^s)$ is bounded comes from the fact that $\lim_k \text{dist}(\bar{D}_s(\mathbb{S}^{d-1}), g_k^s) = 0$ (or we could already see it from the way $\bar{g}_k^s$ is constructed in the proof of Proposition 4).

**Assumption on $(\bar{g}_k^s)$ and $(\bar{\gamma}_k)$**. Immediate by Proposition 4.
**Assumption on $\bar{D}_s$.** As established before Proposition 4, $-m$ is a Lyapunov function to the DI associated with $D_s$ and the set $Z_s$. We now prove that $m(Z_s)$ is of zero-measure. It is a Sard's type result and is a simple adaptation of (Bolte and Pauwels, 2021, Theorem 5.).

We first apply Proposition 9 to $m: \mathbb{R}^d \to \mathbb{R}$, $\bar{D}$ and $M = \mathbb{S}^{d-1}$, with $p \ge d$, obtaining $(\mathcal{X}_i)$ a partition of $\mathbb{R}^d$ into $C^p$ manifolds that is compatible with $\mathbb{S}^{d-1}$. Then, noting that for any $u \in \mathcal{X}_i \subset \mathbb{S}^{d-1}$, it holds that $\mathcal{T}_{\mathcal{X}_i}(u) \subset \mathcal{T}_{\mathbb{S}^{d-1}}(u) = \{v - \langle v, u \rangle : v \in \mathbb{R}^d\}$, we obtain

$$ \{\nabla_{\mathcal{X}_i} m(u)\} = P_{\mathcal{T}_{\mathcal{X}_i}(u)}(\bar{D}(u)) = P_{\mathcal{T}_{\mathcal{X}_i}(u)} \circ P_{\mathcal{T}_{\mathbb{S}^{d-1}}(u)}(\bar{D}(u)) = P_{\mathcal{T}_{\mathcal{X}_i}(u)}(\bar{D}_s(u)), $$

which implies

$$ Z_s \subset \bigcup_{i \in \mathcal{I}} \{u \in \mathcal{X}_i : \nabla_{\mathcal{X}_i} m(u) = 0\}. $$

Hence,

$$ m(Z_s) \subset \bigcup_{i \in \mathcal{I}} m_{|\mathcal{X}_i} (\{w \in \mathcal{X}_i : \nabla_{\mathcal{X}_i} m(w) = 0\}). $$

By Sard's theorem (Sard (1942)) every set in the union has zero-measure. Therefore, $m(Z_s)$ has zero-measure and the assumption on $\bar{D}_s$ holds.

**Assumption on $e_k = \eta_{k+1} + \gamma_k r_k$.** First, note that for any $k \le l \le n(k, T)$,

$$ \left\| \sum_{i=k}^{l} \bar{\gamma}_i^2 r_i \right\| \le \left( \sup_{k \le j \le l} \| \bar{\gamma}_j r_j \| \right) \sum_{i=k}^{l} \bar{\gamma}_i \le \left( \sup_{k \le j \le l} \| \bar{\gamma}_j r_j \| \right) \sum_{i=k}^{n(k, T)} \bar{\gamma}_i \le T \sup_{k \le j \le l} \| \bar{\gamma}_j r_j \|, $$

and the right-hand side goes to zero on $\mathcal{E}$, when $k \to +\infty$. Thus, we only need to prove that the following quantity goes to zero on $\mathcal{E}$

$$ C(k) := \sup \left\{ \left\| \sum_{i=k}^{l} \bar{\gamma}_i \bar{\eta}_{i+1} \right\| : k \le l \le n(k, T) \right\}. $$

To prove that $C(k)$ goes to zero we want to apply (Benaïm, 2006, Proposition 4.2, Remarks 4.3), which states that it is the case if there is a filtration $(\mathcal{F}_k)$ such that $i) (\bar{\gamma}_k)$ and $(\bar{\eta}_k)$ are adapted to $\mathcal{F}_k$, ii) there is $q \ge 2$ such that $\sup_k \mathbb{E}[\|\bar{\eta}_{k+1}\|^q] < +\infty$, iii) and $\sum_k \mathbb{E}[\bar{\gamma}_k^{1+q/2}] < +\infty$.

Note that the first two points hold by Proposition 4 (for any $q$) but for the last point, even though we have that, on $\mathcal{E}$, almost surely $\sum_k \bar{\gamma}_k^{1+2/c_3} \le \sum_k k^{-2} < +\infty$, such bound holds only on $\mathcal{E}$, and, furthermore, $c_3$ is a random variable, therefore we do not necessarily have such bound in expectation for a fixed $q$.

To address this issue, for every $b \in \mathbb{Q}$ define $\hat{\gamma}_k(b) = \min(\bar{\gamma}_k, k^{-b})$ and

$$ \tilde{C}(k, b) := \sup \left\{ \left\| \sum_{i=k}^{l} \hat{\gamma}_i(b) \eta_{i+1} \right\| : k \le l \le n(k, T) \right\}. $$

Next, for any $k_0 \in \mathbb{N}$, define $A_{k_0, b}$ as the following event

$$ A_{k_0, b} = [\forall k \ge k_0, \bar{\gamma}_k = \hat{\gamma}_k(b)]. $$

Note that by construction (since $b$ is fixed) assumptions of (Benaïm, 2006, Proposition 4.2, Remarks 4.3) are satisfied for $\bar{\eta}_{k+1}, \hat{\gamma}_k(b)$. Therefore, $\tilde{C}(k, b) \to 0$. Moreover, on $A_{k_0, b}$, for $k \ge k_0$, $\tilde{C}(k, b) = C(k)$. Therefore, on $A_{k_0, b}$, $C(k)$ converges to zero.

Finally, from the properties of $(\bar{\gamma}_k)$ on $\mathcal{E}$, $\mathcal{E} \subset \bigcup_{k_0, b \in \mathbb{N}} A_{k_0, b}$. Hence, $C(k, b)$ converges to zero on $\mathcal{E}$. This completes the proof of the assumption on $e_k = \eta_{k+1} + \gamma_k r_k$ and thus the proof of Theorem 5.
# E Proof of Proposition 3

Note that for the exponential loss $l(q) = e^{-q}$ and the logistic loss $l(q) = \log(1 + e^{-q})$, it holds

$$ \frac{e^{-q}}{2} \le -l'(q) \le e^{-q}, \quad \text{for all } q \ge 0. \qquad (29) $$

In the following proofs, we assume $k$ is sufficiently large so that $m(w_k) \ge \varepsilon \|w_k\|^L$, for some $\varepsilon > 0$. Taking for instance $\varepsilon = \liminf m(u_k)/2$, this is always possible by the fact that we are working on the event $\mathcal{E}$. We now establish that $(\|w_k\|)_k$ strictly increases to infinity.

**Lemma 17.** Under Assumptions 1–2, on the event $\mathcal{E}$, it holds that $(\|w_k\|)$ is a strictly increasing sequence that diverges to infinity.

*Proof.* Using the fact that $l'(q) < 0$, we obtain

$$ \begin{aligned} \|w_{k+1}\|^2 &= \|w_k\|^2 - \frac{2\gamma}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) \langle \mathbf{a}_i(w_k), w_k \rangle + \frac{\gamma^2}{n_b^2} \left\| \sum_{i \in B_k} l'(p_i(w_k)) \mathbf{a}_i(w_k) \right\|^2 \\ &\ge \|w_k\|^2 - L \frac{2\gamma}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) p_i(w_k) \\ &\ge \|w_k\|^2 - L \frac{2\gamma}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) m(w_k) \\ &\ge \|w_k\|^2 - \varepsilon L \frac{2\gamma}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) \|w_k\|^L, \end{aligned} $$

where for the second inequality we used Assumption 2 and for the last the homogeneity of the margin. As a result, $(\|w_k\|)_k$ is a strictly increasing sequence. Assume by contradiction that $\sup_{k \ge k_0} \|w_k\| \le M$. Then, there exists $\delta > 0$ such that $\inf_{k \ge k_0, i \le n} (-l'(p_i(w_k))) \ge \delta > 0$. In particular, it implies that for all $k \ge k_0$,

$$ \|w_{k+1}\|^2 \ge \|w_k\| + 2\varepsilon L \gamma \delta \|w_{k_0}\|^L, $$

which contradicts the fact that $\sup_{k \ge k_0} \|w_k\| \le M$. Therefore, $\|w_k\| \to +\infty$. $\square$

We now turn to the proof of the first part of Proposition 3.

**Proposition 18.** Let Assumptions 1–2 hold. Almost surely on the event $\mathcal{E}$, there exist constants $c_1, c_2 > 0$ and $k_2 \in \mathbb{N}$ such that for all $k \ge k_2$,

$$ c_1 \log(k) \le \|w_k\|^L \le c_2 \log(k). $$

In the following proof, $C, C', C_1, C_2, \dots$ denote positive constants that may vary from line to line. Additionally, we repeatedly use the following crude estimate, which follows from Taylor expansion: for $a > 0$ and sufficiently small $x \in \mathbb{R}$, there exist constants $C, C' > 0$ such that

$$ 1 + C'x \le (1 + x)^a \le 1 + Cx. $$

*Proof.* By Assumption 2, for every $k$, $\langle \mathbf{a}_i(w_k), w_k \rangle = L p_i(w_k) = L \|w_k\|^L p_i(u_k)$. Therefore,

$$ \begin{aligned} \|w_{k+1}\|^2 &= \|w_k\|^2 - 2 \frac{\gamma}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) \langle \mathbf{a}_i(w_k), w_k \rangle + \frac{\gamma^2}{n_b^2} \left\| \sum_{i \in B_k} l'(p_i(w_k)) \mathbf{a}_i(w_k) \right\|^2 \\ &= \|w_k\|^2 - 2L \|w_k\|^L \frac{\gamma}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) p_i(u_k) + \frac{\gamma^2}{n_b^2} \left\| \sum_{i \in B_k} l'(p_i(w_k)) \mathbf{a}_i(w_k) \right\|^2. \end{aligned} \qquad (30) $$
Since each $D_i$ is locally bounded, it is bounded on $\mathbb{R}^{d-1}$, which implies that there is a constant $C > 0$ such that for every $1 \le i \le n$, $u \in \mathbb{S}^{d-1}$ and $v \in D_i(u)$,

$$ \|v\| + |p_i(u)| \le C. $$

In particular, by Assumption 2, $a_i(w_k) \le C \|w_k\|^{L-1}$. Therefore, using Equation (29) and the fact that $p_i(u_k) \ge m(u_k) \ge \varepsilon$,

$$ \|w_{k+1}\|^2 \le \|w_k\|^2 + 2CL \|w_k\|^L \frac{\gamma}{n_b} \sum_{i \in B_k} e^{-\varepsilon \|w_k\|^L} p_i(u_k) + C'' \frac{\gamma^2 \|w_k\|^{2(L-1)}}{n_b^2} \sum_{i \in B_k} e^{-2\varepsilon \|w_k\|^L}. $$

Since $\|w_k\| \to +\infty$ and $p_i(u_k) \ge \varepsilon$, there exists a constant $C > 0$

$$ \|w_{k+1}\|^2 \le \|w_k\|^2 + C\gamma \|w_k\|^L e^{-\varepsilon \|w_k\|^L}. $$

Thus, using the Taylor's expansion of $(1+x)^{1/2}$ near zero, for $k$ large enough,

$$ \begin{aligned} \|w_{k+1}\|^L &\le \|w_k\|^L \left(1 + C \|w_k\|^{L-2} e^{-\varepsilon \|w_k\|^L}\right)^{1/2} \\ &\le \|w_k\|^L \left(1 + C' \|w_k\|^{L-2} e^{-\varepsilon \|w_k\|^L}\right) \\ &\le \|w_k\|^L + C'' e^{-\varepsilon \|w_k\|^L/2}. \end{aligned} $$

This implies

$$ e^{\frac{\varepsilon}{2} \|w_k\|^L} \left( \|w_{k+1}\|^L - \|w_k\|^L \right) \le C. $$

Denote $m_k := \|w_{k+1}\|^L$. Since $0 \le m_{k+1} - m_k \to 0$, $m_k \le t \le m_{k+1}$ implies $t \le 2m_k$ for $k$ large enough. Therefore,

$$ \int_{m_k}^{m_{k+1}} e^{\varepsilon t/4} \, dt \le e^{\varepsilon \|w_k\|^L/2} \left( \|w_{k+1}\|^L - \|w_k\|^L \right) \le C. $$

In particular, for any $k_0$, such that for all $k \ge k_0$, all the preceding equations hold, we obtain,

$$ \frac{4(e^{m_k} - e^{m_{k_0}})}{\varepsilon} = \int_{m_{k_0}}^{m_k} e^{\varepsilon t/4} \, dt \le C(k - k_0). $$

Therefore, for $k$ large enough,

$$ m_k \le C_1 + \log(C_2(k - k_0)) \le C_3 \log(k), $$

which proves the upper bound.

Establishing the lower bound is similar. First, using Equation (30), we obtain

$$ \begin{aligned} \|w_{k+1}\|^2 &\ge \|w_k\|^2 + \frac{L\varepsilon\gamma \|w_k\|^L}{n_b} \sum_{i \in B_k} e^{-\|w_k\|^L p_i(u_k)} \\ &\ge \|w_k\|^2 + L\varepsilon\gamma \|w_k\|^L e^{-C\|w_k\|^L}, \end{aligned} $$

where $C > 0$ is such that for every $i \le n$ and $u \in \mathbb{S}^{d-1}$, $|p_i(u)| \le C$.

Therefore, for $k$ large enough,

$$ \begin{aligned} \|w_{k+1}\|^L &\ge \|w_k\|^L (1 + C_1 \|w_k\|^{L-2} e^{-C\|w_k\|^L})^{1/2} \\ &\ge \|w_k\|^L (1 + C_2 \|w_k\|^{L-2} e^{-C\|w_k\|^L}) \\ &\ge \|w_k\|^L + C_3 e^{-C\|w_k\|^L}. \end{aligned} $$
Thus,

$$e^{C \|w_k\|^L} (\|w_{k+1}\|^L - \|w_k\|^L) \ge C_3.$$

Recalling that $m_k = \|w_k\|^L$, similarly to previous computations, for $m_k \le t \le m_{k+1}$, we obtain

$$\int_{m_k}^{m_{k+1}} e^{Ct} dt \ge C_3.$$

Therefore, for a fixed, large enough $k_0$ and $k \ge k_0$,

$$\frac{e^{Cm_k}}{C} \ge \int_{m_{k_0}}^{m_k} e^{Ct} dt \ge C_3(k - k_0),$$

which implies, for $C_2$ small enough and $k$ large enough,

$$m_k \ge \frac{\log(C_3 C(k - k_0))}{C} \ge C_2 \log(k).$$

□

To finish the proof of Proposition 3 it is enough to notice that on $\mathcal{E}$, for $k$ large enough,

$$\mathcal{L}(w_k) = \frac{1}{n} \sum_{i=1}^{n} e^{-\|w_k\|^L} p_i(u_k) \le e^{-m(u_k)\|w_k\|^L} \le e^{-\epsilon\|w_k\|^L} \le \frac{1}{k^{\epsilon c_1}}.$$

# F General convergence setting

The purpose of this section is to present a general convergence setting under which it is possible to apply the stochastic approximation ideas that were used in the proof of Proposition 4 and Theorem 5.

Mainly, our setting applies to more general losses than the exponential or logistic and allows to treat the case where we do not have an a priori control of the form $\liminf m(u_k) > 0$. Due to the generality of the approach, we do not aim to push its limits and believe that better guarantees (such as an equivalent version of Proposition 3) could be obtained on a case-by-case basis.

We still analyze (SGD) but now allow step-sizes to decrease to zero:

$$w_{k+1} = w_k - \frac{\gamma_k}{n_b} \sum_{i \in B_k} l'(p_i(w_k)) a_i(w_k). \quad (31)$$

Note that (31) encompasses the deterministic setting, in which $n_b = 0$, and note the presence of $(\gamma_k)$.

We first state our assumptions that are, mostly, only mild modifications of Assumptions 1–2.

## Assumption 3.

i) There exists a positive integer $L \in \mathbb{N}^*$, such that, for every $1 \le i \le n$, the function $p_i$ is $L$-homogeneous, locally Lipschitz continuous and semialgebraic.

ii) The loss function $l$ is $C^1$, with $l'(q) < 0$ on some interval $[q_0, +\infty)$ and is such that for any two sequences $a_k, b_k \to +\infty$,

$$\limsup \frac{b_k}{a_k} < 1 \implies \frac{l'(a_k)}{l'(b_k)} \to 0.$$

**Assumption 4.** For every $i \le n$, $a_i$ is measurable and $D_i$ is semialgebraic. Moreover, for every $w \in \mathbb{R}^d$ and $\lambda \ge 0$, $a_i(w) \in D_i(w)$ and

$$D_i(\lambda w) = \lambda^{L-1} D_i(w).$$

**Assumption 5 (Deterministic setting).** The batch-size $n_b = n$ and there is $\gamma > 0$ such that $\gamma_k \le \gamma$ and $\sum \gamma_k = +\infty$.
**Assumption 6 (Stochastic setting).** The sequence $(\gamma_k)$ is a sequence of strictly positive step-sizes such that $\sum_k \gamma_k = +\infty$ and there is $q \ge 2$ such that $\sum_k \gamma_k^{1+q/2} < +\infty$.

Finally, all of the results now hold on the, a priori, larger event

$$ \mathcal{E}' = [\|w_k\| \to +\infty] \cap [\|w_k\|^{L-2} \sum_{i=1}^{n} \ell'(p_i(w_k)) \to 0] \cap [\text{there is } k_0 \in \mathbb{N} \text{ such that } \inf_{k \ge k_0} m(w_k) \ge q_0], $$

where $q_0$ was defined in Assumption 3.

**Comments on Assumptions 3–4 and the event $\mathcal{E}'$.** These assumptions are similar to Assumptions 1–2. The main differences are the following.

* Assumption 3 allows us to consider more general losses such as $l(q) = e^{-q^a}$ or $l(q) = \log(1+e^{-q^a})$, for $a > 0$, already considered in Lyu and Li (2020).

* Differently to the main setting of the paper, to treat the stochastic case we require in Assumption 6 vanishing stepsizes. In fact it could be alleviated, if, similarly to Proposition 3 we have control on the growth of $\|w_k\|$. In the deterministic setting of Assumption 5 one could still choose a constant stepsize.

* In the definition of the event $\mathcal{E}'$, differently to the main setting of the paper, we assume $\|w_k\| \to +\infty$. Note that, similarly to Lemma 17, we could ensure this growth if we assumed $\liminf m(u_k) > q_0$. However, the event $\mathcal{E}'$ allows us to treat the case, where, a priori, we do not have such control on the growth of the normalized margin. For instance, if $l(q) = e^{-q}$, then the event $\mathcal{E}'$ requires that $\|w_k\|^{L-2} e^{-\|w_k\|^{L} m(u_k)} \to 0$. Thus, it would hold as soon as $m(u_k) \ge \|w_k\|^{-L} \log(\|w_k\|^{L-1})$ a much softer requirement than $\liminf m(u_k) > 0$.

Under these new assumptions we have a version of Proposition 4. Recall that $\mathcal{F}_k$ denotes the sigma algebra generated by $\{w_0, \dots, w_k\}$.

**Proposition 19.** Let either Assumptions 3–5 or Assumptions 3,4 and 6 hold. There are sequences $(\bar{g}_k)$, $(r_k)$, $(\bar{\gamma}_k)$, $(\bar{\eta}_{k+1})$ such that

$$ u_{k+1} = u_k + \bar{\gamma}_k(\bar{g}_k - \langle \bar{g}_k, u_k \rangle u_k) + \bar{\gamma}_k \bar{\eta}_{k+1} + \bar{\gamma}_k^2 r_k, \quad (32) $$

and the following holds.

1. On the event $\mathcal{E}'$, the sequence $(r_k)$ is such that almost surely $\sup_k \|r_k\| < +\infty$.

2. The sequence $(\bar{\gamma}_k)$ is adapted to $(\mathcal{F}_k)$ and almost surely on $\mathcal{E}'$, there is $k_0 \in \mathbb{N}$, such that for all $k \ge k_0$, $\bar{\gamma}_k > 0$. Moreover, on $\mathcal{E}'$, $\bar{\gamma}_k \to 0$ and $\sum_k \bar{\gamma}_k = +\infty$ and under Assumption 6, we additionally have that $\sup_k \bar{\gamma}_k/\gamma_k < +\infty$.

3. Under Assumption 5, $\bar{\eta}_k \equiv 0$. Otherwise, under Assumption 6, the sequence $(\bar{\eta}_k)$ is adapted to $(\mathcal{F}_k)$,

$$ \mathbb{E}[\bar{\eta}_{k+1} | \mathcal{F}_k] = 0, $$

and there is a deterministic constant $c_1 > 0$ such that $\sup_k \|\bar{\eta}_{k+1}\| < c_6$.

4. On $\mathcal{E}'$, for any unbounded sequence $(k_j)_{j \ge 0}$, such that $u_{k_j}$ converges to $u \in \mathbb{S}^{d-1}$, it holds that $\mathrm{dist}(\bar{D}(u), \bar{g}_{k_j}) \to 0$.

*Proof.* The proof goes as the one of Proposition 4 in Section 6 but with $\gamma$ replaced by $\gamma_k$. The claim on $(\bar{\gamma}_k)$ follows from the fact that

$$ \bar{\gamma}_k = -\gamma_k \|w_k\|^{L-2} \sum_{j=1}^{n} l'(p_j(w_k)). $$

Indeed, on $\mathcal{E}'$, for $k$ large enough, $p_j(w_k) \ge q_0$. Hence, $\bar{\gamma}_k > 0$ by Assumption 3-ii). Moreover, it goes to zero on $\mathcal{E}'$. From the same assumption and under Assumption 6 we indeed have $\limsup \bar{\gamma}_k/\gamma_k < +\infty$. The claim on $\bar{D}_s$ is obtained from Assumption 3-ii). The other claims are obtained exactly as in the proof of Proposition 4. $\square$
As a result, we have a version of Theorem 5.

**Theorem 20.** In the setting of Proposition 19, almost surely on $\mathcal{E}'$, $m(u_k)$ converges to a nonnegative limit and

$$ \mathrm{dist}(u_k, \mathcal{Z}_s) \xrightarrow[k \to +\infty]{} 0. \qquad (33) $$

*Proof.* The proof goes as the proof of Theorem 5, with Proposition 19 playing the role of Proposition 4. $\square$

Let us finish this section with a brief comment on KKT points of (P) considered in Lyu and Li (2020). A point $w \in \mathbb{R}^d$ is a KKT point of (P) if there is $\alpha_i, \dots, \alpha_n \ge 0$ and $v_1, \dots, v_n$, with $v_i \in \partial p_i(w)$ and

$$ w = \sum_{i=1}^{n} \alpha_i v_i \quad \text{and for all } i, \quad \lambda_i(p_i(w) - 1) = 0. $$

Denoting $\lambda_i = \alpha_i / \sum_{j=1}^n \alpha_j$ and $u = w / \|w\|$, we can successively observe that $i) \lambda_i \ne 0$ only if $p_i(u) = m(u)$ and $v_i = \|w\|^L g_i$, with $g_i \in \partial p_i(u)$, $ii) \sum_{i=1}^n \lambda_i g_i \in \bar{D}(u)$ $iii) \text{ therefore, } u = \sum_{i=1}^n \lambda_i g_i$ and finally $0 \in \bar{D}_s(u)$. Conversely, if $u \in \mathcal{Z}_s$ and if additionally $m(u) > 0$, then $w = u/m(u)^{1/L}$ is a KKT point of (P).

Nevertheless, due to the slow decrease rate required by the event $\mathcal{E}'$, we do not, a priori, have that $\lim m(u_k) > 0$. Therefore, in the setting of Theorem 20 there could be two scenarios. First, in which $\lim m(u_k) > 0$ and in that case the limit points of $(u_k)$ are *exactly* (scaled) KKT directions of (P). Second, in which $\lim m(u_k) = 0$, and we only have that any limit point of $(u_k)$ is in $\mathcal{Z}_s$.

Note however, that without any discussion on KKT points in all cases being in $\mathcal{Z}_s$ is a meaningful description of optimality of maximization of the margin, which, furthermore, naturally extends to settings, where $D_i$ are different of the Clarke subgradients of $p_i$.