Implicit Bias of Mirror Flow on Separable Data
Authors: Scott Pesme
Radu-Alexandru Dragomir
Nicolas Flammarion
Venue: NeurIPS 2024 poster (2024)
Keywords: Implicit bias
Mirror descent
Classification
Primary area: optimization
TL;DR: We provide the implicit bias of mirror flow in the classification setting.

Abstract: We examine the continuous-time counterpart of mirror descent, namely mirror flow, on classification problems which are linearly separable. Such problems are minimised ‘at infinity’ and have many possible solutions; we study which solution is preferred by the algorithm depending on the mirror potential. For exponential tailed losses and under mild assumptions on the potential, we show that the iterates converge in direction towards a $\phi_\infty$-maximum margin classifier. The function $\phi_\infty$ is the horizon function of the mirror potential and characterises its shape ‘at infinity’. When the potential is separable, a simple formula allows to compute this function. We analyse several examples of potentials and provide numerical experiments highlighting our results.

Implicit Bias of Mirror Flow on Separable Data
Scott Pesme EPFL
Radu Aleuu-le Dragomir Télécom Paris
Nicolas Flammarion EPFL
Abstract
We examine the continuous-time counterpart of mirror descent, namely mirror flow, on classification problems which are linearly separable. Such problems are minimised 'at infinity' and have many possible solutions; study which solution is preferred by the algorithm depending on the mirror potential. For exponential tailed losses and under mild assumptions on the potential, we show that the iterates converge in direction towards a @x -mximumm margin classifier. The function do the horizon forizon,uncttion of the mirror potential and characterises its shape 'at infinity". When the potential is separable, simple formula allows to compute this function. We analyse several examples of potentials and provide numerical experiments highlighting our results.
Introduction
Heavily over- wer-parametrrsed yet barely regularised neural networks can easily perfectly noisy training set while still performing very well on unseen data [Zhang et al., 2017]. This statistical phenomenon surprising since is known that there exists interpolating solutions which have terrible generalisation performances [Liu et al., 2020]. To understand this benign overfitting, it is essential to take into account the training algorithm. If overfitting is indeed harmless, must be because optimisation process has steered towards solution with favorable generalisation properties.
From this simple observation, a major line of work studying the implicit regularisation of gradient methods has emerged. These results show that the recovered solution enjoys some type of low norm property in the infinite space zero-loss solutions. Gradient descent (and its variations) has therefore been analysed in various settings, the simplest and most emblematic being that of gradient descent for least-squares regression: it converges towards the solution which has the lowest &g distance from the initialisation [Lemaire, 1996]. In the classification setting with linearly separable data, iterates of gradient methods must diverge to infinity to minimise the loss. Therefore, the directional convergence of the iterates is considered and Soudry et al. [2018) show that gradient descent selects the Va-max-margin solution amongst all classifiers.
Going beyond linear settings, it has been observed that an underlying mirror-descent structure very recurrently emerges when analysing gradient descent in range of non-linear parametrisa- tions [Woodworth et al., 2020, Azulay et al., 2021]. Providing convergence and implicit regularisation results for mirror descent has therefore gained significant importance.
In this context, for linear regression, Gunasekar et al. [2018] show that the iterates converge to the solution that has minimal Bregman distance the initial point. Turning towards the classification setting, an apparent gap emerges as there is still no clear understanding of what happens: Can directional convergence be characterised in terms of max-margin problem? If so, what is the associated norm? Quite surprisingly. this question remains largely unanswered, as it is only understood for L-homogeneous potentials [Sun al., 2023]. Our paper bridges this gap by formally characterising the implicit bias of mirror descent for separable classification problems.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Mirror descent with:
Limiting directions
Px- max-margins
(P) =
(1P) 2 (W)))))
MDs x 11
lla
(arorin(()) -
MD,
x I|
10
Train losses (Tg log scale)
L(BED)
10
Iterations
[ I2 min (2,, 9)
Figure 1: Mirror descent performed using different potentials on the same toy 2d dataset. Left: the losses converge zero. Center: the iterates converge in direction towards 3 different vectors Boo. the 3 lines passing through the origin correspond to the associated separating hyperplanes. Right: the limit directions are each proportional arg min @ (3) under the constraint min; y (a B) 2 1 for their respective &i 's, as predicted by our theory (Theorem I). The full trajectories are plotted Figure and refer to Section for more details.
1.1 Informal statement of the main result
For a separable dataset (zi, M/ sejn) we study the mirror flow (V,) VL(B)dd )d with potential 6: IRd + R and an exponential tailed classification loss L. We prove that Br converges in direction towards the solution of the o. -maximum margin solution where the (asymmetric) norm 6x captures the shape of the potential Φ 'at infinity' (see Figure for an intuitive illustration).
Theorem 1 (Main result, Informal). There exists a horizon function @x such that for any separable dataset, the normalised mirror flow iterates 3t 3,/11B.]1 converge and satisfy:
lim Br is proportional min: da (111
arg min
soo (3).
Our result holds for large class of potentials & and recovers previous results obtained for á -|: [Sun al., 2022] and for L-homogeneous potentials [Sun al., 2023]. For general potentials, showing convergence towards a maximum margin classifier is much harder because, in stark contrast. with homogeneous potentials, ø's geometry changes as the iterates diverge. To capture the behaviour of á at infinity, we geometrically construct its horizon function &x.. By considering é's successive level sets (and re-normalising them to prevent blow up), we show that under mild assumptions, these sets asymptotically converge towards a limiting horizon set S The horizon function &x is then simply the asymmetric norm which has S%0 as its unit ball (see Figure 3 for an illustration). In addition, when the function ø is 'separable' and can be written c(B) Σ (p())) for real valued function io, then a very simple and explicit formula enables to calculate do (Theorem 3).
The paper is organised as follows. The classification setting well as the assumptions on the loss and the potential are provided in Section The proof sketch and an intuitive construction of the horizon function are given in Section 3. In Section 4, we state the formal definition and results. Simple examples of horizon potentials and numerical experiments supporting our claims are finally given in Section 5.
1.2 Relevance of mirror descent and related work
We first outline the motivations for understanding the implicit regularization of mirror descent and discuss related works that contextualize contribution within the machine learning context.
Relevance of studying mirror descent in the context of machine learning. Though mirror descent not per se an algorithm used by machine learning practitioners, proves to be a very useful tool for theoreticians in the field. Indeed, when analysing gradient descent (and its stochastic and accelerated

---

variants) on emerges. Then, results for mirror descent enable prove convergence as well characterise the implicit bias of gradient descent for these architectures. Diagonal linear networks, which are ideal proxy models for gaining insights on complex deep-learning phenomenons, is the most notable example of such an architecture. The hyperbolic entropy potential naturally appears and enables to prove countless results: implicit bias of gradient descent in regression [Woodworth et al., 2020, Vaskevicius al., 2019] and in classification [Moroshko et al., 2020], effect of stochasticity [Pesme et al., 2021] and momentum [Papazov et al., 2024], convergence of gradient descent and effect of the step-size [Even et al., 2023], saddle-to-see -aadle dynamics [Pesme and Flammarion, 2023]. Unveiling an underlying mirror-like structure goes beyond these simple networks as they also appear in: matrix factorisation with commuting observations [Gunasekar et al.. 2017, Wu and Rebeschini, 2021], fully connected linear networks [Azulay et al., 2021, Varre et al., 2023] and 2-layer ReI.U networks [Chizat and Bach, 2020]. Building on these examples, Li al. [2022] investigate the formal conditions that ensure the existence of a mirror flow reformulation for general parametrisations, extending previous results by Amid and Warmuth [2020a.b].
architectures, an underlying mirror-descent structure very recurrently
Gradient descent in classification. Numerous works have studied gradient descent in the classifi- cation setting. For linear parametrisations, separable data and exponentially tailed losses, Soudry et al. [2018) 8] prove that GD converges in direction towards the f2-maximum margin classifier and provides convergence rates. A very fine description of this divergence trajectory is conducted by Ji and Telgarsky [2018] and a different primal-dual analysis leading to tighter rates is given by Ji and Telgarsky [2021]. Similar results are proven for stochastic gradient descent by Nacson et al. [2019c]. In the case of general loss tails, Ji et al. [2020] prove that gradient descent asymptotically follows the l2-norm regularisation path. A whole 'astral theory' is developed by Dudík et al. [2022] who provide a framework which enables to handle 'minimisation at infinity'. Beyond the linear case, Lyu and Li [2020] proves for homogeneous neural networks that any directional limit point of gradient descent is along a KKT point of the f2-max margin problem. A weaker version of this result was previously obtained by Nacson al. [2019a]. Furthermore, convergence results for linear networks provided by Yun et al. [2021]. Finally, for 2-layer networks in the infinite width limit, assuming directional convergence, Chizat and Bach [2020] proves that the limit can be characterised as a max-margin classifier in a certain space of functions.
1.3 Notations
We provide here few notations which will be useful throughout the paper. We let [n] be the integers from to n. We denote by Z E =xd the feature matrix whose ith line corresponds to the vector y; When not specified, || corresponds to any (definable) norm on IRd, For a convex function ht (h(3) denotes its subdifferential B: ah(33 = fo E Rd h(5')= 2 h(B) + (g. 3). V E {. For any scalar function f IR - IR and vector E RP, the vector [') E R corresponds to the component-wii application of f over u. We denote by a IR" + R. the softmax function equal to a=)) = exp(2)/ -i= exp(=x) E An where A, is the unit simplex. For a convex potential Φ, we denote (3, 80) the Bregman divergence equal to x(3) - (x(5) + (Vo(Bo). 3 (b)) 2 0.
2 Problem set-up
We consider dataset (z,, siissinn with points x; E Idd and binary labels y E (-1,1). We choose a loss function é: IR- + R and seek to minimise the empirical risk
l(B)= = Σ
We propose to study the dynamics of mirror flow, which is the continuous-time limit of the mirror descent algorithm [Beck and Teboulle, 2003]. Mirror descent is generalisation of gradient descent to non-Euclidean geometries induced by given convex potential function & : Rd -> IR. The method generates a sequence (Bx)420 with B. = 20 E Bd and
vol3e+1) vo(3e) - LL
3

---

When the step size goes to O, the mirror descent iterates approach the solution (f:) to the following differential equation:
dV = - L(,,dd,
(MF)
initialised at So. Studying the mirror flow (MF) leads to simpler computations than its discrete counterpart, and still allows to obtain rich insights about the algorithm's behaviour.
We now state our standing assumptions on the loss function and potential Φb
Assumption 1. The loss & satisfies:
1. E is convex, twice continuously differentiable, decreasing and lim,--400 {(2) 0.
2. i has an exponential tail, in the sense that E(z) 20:00 - 2500 exp(-2).
The first part the assumptions is very general and ensures that the empirical loss be minimised "at infinity'. The exponential tail is crucial: it enables to identify unique maximum margin solution towards which the iterates converge in direction, independently of the considered loss. Both the exponential f(2) exp( 2) and the logistic loss E(z) = In(1 + exp(-2)) satisfy the conditions. On the other hand, losses with polynomial tails do not satisfy the second criterion. Similar assumptions on the tail appear when investigating the implicit bias of gradient descent for separable data [Soudry al., 2018, Nacson et al., 2019b, al., 2020, Ji and Telgarsky, 2021, Chizat and Bach, 2020J.
Assumption 2. The potential Rd R satisfies:
1. é is twice continuously differentiable, strictly convex and coercive.
2. for every e Rz0 and 32 IR,, the sub-level {Bi IR, (z(32, 31) S c} is bounded.
3. 42 (B) is positive-defintte for all 3 E Rd.
4. Ve diverges at infinity: liml [[)(3]] +00.
The first two points of the assumption are commonly used to ensure well-posedness of mirror descent [Bauschke et al., 2017]. The third one necessary in continuous time to ensure the existence and uniqueness over R2=0 of a solution to the (MF) differential equation (in particular, we want to avoid the solution "blowing up finite time "; see Lemma 2 in Appendix A). The coercive gradient assumption is crucial for our main result and we discuss it in more depth in Section 6.
Finally, assume that the dataset is linearly separable. Assumption 3. There exists 3 E Rd such that yı (8" > for every i E [r)].
Notice that such 3 correspond to minimisation directions: I(A3*) >=30 0. Under the three previous assumptions, we can show that the mirror flow iterates (3:)e20 minimise the loss while diverging to infinity.
Proposition 1. Considering the mirror flow (B))2o. the loss converges towards and the iterates diverge: lim L(3.) = 0 and lim ||
+00.
(+20
100
The proof relies on classical techniques used to analyse gradient methods in continuous time and we defer the proof to Appendix A. We now turn the main question addressed in this paper:
Among all minimising directions 3", towards which does the mirror flow converge?
We initially offer heuristic and intuitive answer to this question, setting the stage for the formal construction of the implicit regularisation problem.
3 Intuitive construction of the implicit regularisation problem
In this section, we give an informal presentation and proof sketch of our main result. A fully rigorous exposition is then provided in Section 4.

---

Preliminaries.
Assume here for simplicity that {(2) = exp(-2). The mirror flow then writes
d vo(3)) L(3)) ((t))
dt
with g(3x) - =--2,), where a is the softmax function and Z the matrix with rows (BIZ)))E())) Note that ((3x) belongs to the unit simplex A..
We simplify the differential equation by performing time rescaling, which does not change the asymptotical behaviour. As 0 1+ So L(B)dds is bijection in Rzo (see Lemma 4), we can speed up time and consider the accelerated iterates Be (0)- 1 By the chain rule, we have
d Vo(3,) = z TT (B.).
dt
and therefore
1 Vo(3)) + 2T ZT G. ((..)ds). t
V
From on, drop the tilde notation and assume that change of time scale has been done. We want to characterise the directional limit of the diverging iterates 3r. To do so, we study their normalisation Bg = 8, |ل:||| As they form a bounded sequence, and ((x) E A, is also bounded, we can extract subsequence* (Br, (),,,)) with lim t, oo converging to some limit (8xz ). By the Césaro average property, + : ((3,)ds also converges towards Joo. Equation (1) then yields
Vo(BI,) - ZT 9x0. 5-220
Observe that ( and the softmax function a approaches the argmax operator at infinity. Hence, as 3, diverges, we expect that g(3,)Lc - for coordinates for which (-Z3,); is not maximal, ie. (Z,z)) not minimal. This observation is made formal in the following lemma. Its proof is straightforward and is given in Appendix
Lemma 1. Assume that (Bi,, a(3,)))
=09 (Boo, 9oc). It holds that:
(gx)) k = O if yk (ak (Bo)) > min yi (T (00))
1545
In words, coordinates of 4ro which not correspond to support vectors of 3ox must zero. Our goal is now to uniquely characterise Boo as the solution of maximum margin problem.
3.1 Warm-up: gradient flow
As warm-up, up, let us consider standard gradient flow, which corresponds to mirror flow with potential = || 1|2/2. In this case, Equation (2) becomes Br,/t,, /t, + Z Td 9:0. Since the normalised iterates satisfy Br, + Boc, we get
Z g00
3:0
2
0 12
Now notice that this equation along with the slackness conditions from Lemma exactly correspond to the optimality conditions of the following convex minimisation problem:
min
B
under the constraint
min
ye (2, B) 2 1.
sE(n]
32 can also he seen as the mirror flow trajectory but on the log-sum-exp function instead of the sum-exp function
(ta)neN any sequence with t, + 00 as co then consider the discrete sequence (8t,, ((..)) )..N. We can then apply the Bolzano Weierstrass theorem to extract a convergent subsequence. We will show that the limit (Bx., qoo) is unique and does not depend on the sequence (t..), and therefore the continuous time process (Br, g(3))))) YEER must converge towards it.
'More precisely,
5

---

Figure 2: Left two: Sketch of the level lines of two different potentials (01) -R² - R. Right Iwo: Their corresponding horizon functions @x Pp as defined in Section 4.1.
(2)
Furthermore, the fz-unit ball being strictly convex, Problem (3) has unique solution to which 9xc must therefore be equal. Importantly, notice that Problem (3) uniquely defines the limit of any extraction on the normalised iterates 3y: the normalised iterates 3n must therefore converge towards the f2 maximum margin. We recover the implicit regularisation result from Soudry al. [2018]:
Boo
arg min
|| 11-2-
min, Be ())
3.2 General potential: introducing the horizon function 6000
We now tackle general potentials ø. In the general case, the challenge of identifying the max-margin problem which the iterates converge in direction stems from the fact that if the potential is L-homogeneous" its geometry changes as the iterates diverge. More precisely, its sub-level sets S. : (5 Rd, <(B) S c} change of shape as increase, illustrated by Figure (Left).
However, we can hope that these sets have limiting shape at infinity, meaning that the normalised sub-level sets S. = Se/ Rs where R. maxses, || converge some limiting convex set Soc as 0o. We can then construct asymmetric norm* dxo which has Soc its unit ball. In words, deo captures the shape of á at infinity. This informal construction is made rigorous Section 4.1. We state here the crucial consequence of this construction.
Corollary 1. The horizon function tho is such that for any sequence Be diverging to infinity for which
9. and Vo(8,) both converge, then: [[+[[]]]]
1311
Vo(3)) Vo(3))l
8x ||lell
lim
E 12.00 (Bxc) where 8.0 lim
for some strictly positive factor A.
Using this construction, we can derive the optimality conditions satisfied by 3oc. From the conver- gence in Equation (2) and that of 3, - Boc. applying Corollary 1, we obtain that:
zT goo (Boc).
Up positive multiplicative factor (which irrelevant due to the positive homogeneity of the quantities involved), this condition along with Lemma are exactly the optimality conditions of the convex problem
min BERd
(3) under the constraint
min iE(n]
y, 3) 1.
The limiting direction 3ox must therefore belong to the set of its solutions. Assuming that this set contains single element of norm (we refer the next section for comments concerning the uniqueness), we deduce that the iterates 3, must converge towards it:
Be
lim +-000
X arg min doe (33).
Be
min, M. (x1,
AA function T--homggeneous there exists I. such that 6(c3) = o² ((3) for all 8 and c 0 An asymmetric satisfies all the properties of a except the symmetry equality p(-3) p(3)

---

Sub-level sets
Sca
Normalised Sub-level sets
Sea
So0
Po0 x 1111
5ca
Ses
Sea
Figure 3: Illustration of the construction of the horizon shape S Left: the sub-level sets S. change of shape and increasing. Middle: in order avoid the shapes blowing up. normalise them to keep them in the unit ball (here we choose the arbitrary constraining norm to be the & normm)) Right: the normalised sub-level sets S. converge to limiting set S for the Hausdorff distance.
4 Main result: directional convergence towards the éx -max margin
We now state our formal results, starting with the precise construction of the horizon function &sc. followed by the theorem showing convergence of the iterates towards the 6 - ta-max-margin.
4.1 Construction of the horizon function 6xc
We first define the horizon shape of potential é, and provide sufficient conditions for its existence. Then, we use this shape to construct horizon function Φx.. which allows the interpretation of the directional limits of gradients of at infinity. The proofs require technical elements from variational analysis to ensure that the limits are well-defined; these are deferred to Appendix B.
Horizon shape.
Assume w.l.ogg. that ((0) O. For 2 0, consider the sublevel set:
Sc(o) {B E Ied 5(3) S c),
which is nonempty and compact by coercivity of Φb. We can then define the normalised sublevel set:
1 R. Se: =ax : 8 Sc}.
S.
(4)
By construction, the set S. belongs the unit ball. We are interested in the limit of S. as Definition 1. We say that e admits a horizon shape if the family of normalized sublevel sets (Se)ez0 defined in Equation (4) converges some compact set Soo addition, we say that this shape is non-degenerate if the origin belongs to the interior of Soc.
- oo for the Hausdorff distance. In
The Hausdorff distance is a natural distance on compact sets [see Rockafellar and Wets, 1998. Section 4.C., for definition]. In Proposition 2, prove the existence of the horizon shape for large class functions which contains all the potentials with domain Rd encountered practice. Although the horizon shape guaranteed exist for most functions, non-degenerate, as the normalized sub-levels S. can become 'flat' as c - oo. Given the technical complexity associated with this case, we now focus exclusively on non-degenerate horizon shapes.
cannot priori prove that it
Horizon function. If di admits non-degenerate horizon shape Soc, we define its horizon function as the Minkowski gauge [Rockafellar and Wets, 1998, Section 11.E] of Soc:
deo = inf (r
Soc) for Tdd.
By construction, the horizon function doo an asymmetric norm and its sub-level sets correspond to scaled versions of Sxc [see Rockafellar and Wets, 1998, Section 11.C, for more properties]. For example, the case of the horizon shape S.x illustrated in Figure 3, the corresponding horizon function di is proportional to the -noor. Although the construction of oix presented here is rather abstract, we show Theorem that separable potentials defined over Rd it can computed with an explicit formula. Though different, our definition of the horizon function shares many similarities with the classical concept of horizon function from convex analysis [Rockafellar and Wets, 1998]. We discuss the links between the two notions the end of Section 4.3.
Consider for instance ((x, y) x² +y on R for which the horizon shape is [-1, (0).

---

4.2 Main result: directional convergence of the iterates towards the 6x 225-max-margge
We can now state our main result which fully characterises the directional convergence of mirror flow.
Theorem 2. Assume that & admits non-degenerate horizon shape and let &x be its horizon function. Assuming that the following 6x mmx-maaaragin problem has a unique minimiser, then the mirror flow normalised iterates Be
T. converge towards a vector 8n0 and
3,
Bx x arg min 6o0 (B) under the constraint
min Yi (Zi, B) 2 1,
BER"
sE(m)
where the symbol x denotes positive proportionalily.
Remark on the uniqueness of the margin problem. If the unit ball of do is strictly convex, then the &x max-marga problem has unique solution. However, in the general case, there may exist an infinity of solutions and weak but ad hoc assumptions on the dataset are required guarantee uniqueness. For instance, if &o is proportional to the & f--nomm common assumption which ensures uniqueness assuming that the data features are in general position [Dossal, 2012].
4.3 Assumptions guaranteeing the existence of doc
Our main result, presented in Theorem 2 relies on the existence of a horizon shape, Sox, as described in Definition 1. From this shape, the asymmetric norm 6x is constructed.
We show here that the existence of S. is ensured for large class of 'nice' functions, specifically those definable in o-minimal structures [Dries, 1998]. For the reader unfamiliar with this notion, this class contains all 'reasonable' functions used in practice, such as polynomials, logarithms, exponentials, and 'reasonable' combinations of those. This is typical assumption used for instance to prove the convergence of optimisation methods through the 2011].
property [Attouch et al.,
Proposition 2. If any of the three following conditions hold: (i) 6 a finite composition of polynomi- als, exponentials and logarithms, (ii) o is globally subanalytie, (iii) 6 is definable in a o-minimal structure on IR; then & admits a horizon shape S.x.
The proof is technical and we defer it to Appendix B. Although the previous proposition ensures the existence &x for wide range of potentials, it does not offer direct method for computing it. In the following, we show that for potentials that are both separable and even, a simple formula exists, allowing for the direct calculation of &xc.
Assumption 4. The potential & is separable, in the sense that there exists yp : R + R:0 such that x(3) -i= ((B)). We assume that satisfies Assumption 2, that it is definable in o-minimal structure on TR. and that is an even function. W.L.o.g. we assume that (p
We note that to is a bijection over Rz0, and denote by y-1 its inverse. We consider the function oo o, which can be seen renormalisation of o. It has the same level sets as & and ensures that oo mip (o(3/n)) exists in Ey for all B. These two observations lead to the following theorem.
Theorem 3. Under Assumption the potential & admits a non-degenerate horizon shape and its horizon function is such that there exists X >> O such that for every Rd:
6 A lim 1 ---6111 n) n
We use this simple formula when computing dx for various potentials in the next section.
Remark on previous notions of horizon function. In the convex analysis literature, the horizon function is typically defined as dee (8) lim (B/B)) [Rockafellar and Wets, 1998, Laghdir and Volle, 1999]. In our context, this definition would yield a function which equals +oc everywhere except at the origin. In contrast, our definition ensures that 6x attains finite values over Rd. The distinction stems from our way of normalising the level sets by R, in Section 4, or alternatively, from the composition by - in the separable case. The two constructions would coincide only if Ø was Lipschitz continuous, which is at odds with Assumption 2.
8

---

Iterate trajectorics in the -ll-ne
Iterate trajectories the Rp- unit disk under the rescaling
(amous mark the progrussion iterates time, diverging outward)
x(3)
1+ ||
Socond conrdinare
BAD
MD
B
250
3
Rescaled trajectories visualisation purposes
a [
MD2
x(3
MD,
500
First coordinate
Figure 4: Mirror flow trajectories on a 2-dimensional dataset for three different potentials (exact same setting in Figure 1). Left: the iterates diverge to infinity and the directional convergence depends on the choice of potential. Right: the normalised iterates converge towards their respective -eo--mmxmmmmaaaaee predictors (illustrated by stars), predicted by Theorem 2.
Applications and experiments
In this section, we illustrate our main result using various potentials.
Homogeneous potentials. We first consider potentials & which are L-homogeneous, i.e., there exists L >> 0 such that for all > 0 and 3 E R2, 6(cB) ct (B). In this case, the sublevel sets S. are all equal. It follows that &oo 6-/4, An important example is the case of Φ | I1p where || llp corresponds to the -nomm with 1, for which get that do || llr and we recover the result from Sun al. [2022, 2023].
Hyperbolic-cosine entropy potential. Finally, we consider MD (3) = Σd (cosh(B.) 1). Applying Theorem 3, we get that Φxo & |l
Hyperbolic entropy potential. The hyperbolic entropy potential:
(
E (Barccinh v +I- 1) plays a central role in works considering diagonal linear networks [Woodworth al., 2020, Pesme and Flammarion, 2023]. Applying Theorem obtain that 6x x ||- | and we recover the result from Lyu and Li [2020] and Moroshko et al. [2020].
Experimental details concerning Figure 1. As shown Figure (Middle), generate 40 points with positive labels and 40 points with negative labels. Starting from 8o = O, we run mirror descent with the exponential loss {(z) exp(-2) and with the three following potentials:
GD -
(ii)
MD: cosh-entropy,
(iit) Φ MDz Hyperbolic entropy.
We first observe in Figure (Left) that the training loss converges to zero, as predicted by Proposition with convergence rate that varies across different potentials. Moreover, as illustrated in Figure (Middle and Right), the iterates converge in direction towards their respective unique d -max margin solutions associated with the following geometries:
GD
112,
(ii)
MD1
|| lbso,
(tax)
MD2
-1-112-
Therefore, by employing various potentials, we can induce diffeerent implicit biases, leading to distinct generalisation properties depending on the data distribution. The trajectories of the mirror descent iterates are shown and commented in Figure 4.

---

Conclusion and limitations
In this paper, we offer a comprehensive characterisation of the implicit bias mirror flow for separable classification problems. This characterisation is framed in terms of the horizon function associated with the mirror descent potential, leveraging the asymptotic geometry induced by the potential. Note that we did not cover the discrete mirror descent algorithm; we believe the analysis would extend without additional difficulties compared to the continuous counterpart.
Extensions and open problems. Our results being purely asymptotic, characterising the rate at which the normalised iterates converge towards the maximum-margin solution is an open direction for future research. Furthermore, we note that our analysis does not cover potentials that are defined only on a strict subset Rd (such as the log-barrier and the negative entropy), and with possibly non-coercive gradients. This class of potentials is of interest it arises when investigating deep architectures, such as diagonal linear networks of depth D 2. In this setting, that gradient flow the weights lead to mirror flow the predictors with certain potential ΦD [Woodworth et al., 2020]. Interestingly, the potentials oD have non-coercive gradients and their horizon functions do not depend on the depth D as they all proportional to the & norm. The predictors are, however, known to converge direction towards a KKT point of the non-convex 22/D-max-margin problem [Lyu and Li, 2020] which be different from the 4--max-mrgin problem [Moroshko et al., 2020]. This observation highlights that our coercive gradient assumption necessary for result to hold. However, extending our analysis beyond this assumption is promising direction for understanding gradient dynamics in deep architectures.
known
Acknowledgments and Disclosure of Funding
S.P. would like thank Loucas Pillaud- Pillaud-Vivien for the helpful discussions at the beginning of the project as well as Pierre Quinton for the careful proofreading of the paper. The authors also thank Jérôme Bolte and Edouard Pauwels for the precious help on the existence of the Hausdorff limit of definable families, as well as Nati Srebro and Lénaïc Chizat for the remarks on the limitations of our result for potentials with non-coercive gradients. This work was supported by the Swiss National Science Foundation (grant number 212111).
10

---

References
Charalambos Aliprantis and Kim Border. Infinite Dimensional Analysis. Springer Berlin, Heidelberg. 2006.
Ehsan Amid and Manfred K Warmuth. Winnowing with gradient descent. In Conference on Learning Theory, pages 163-182. PMLR, 2020a.
Ehsan Amid and Manfred KK Warmuth. Reparameterizing mirror descent gradient descent. Advances in Neural Information Processing Systems, 33:8430-8439, 2020b.
H. Attouch, X. Goudou, and P. Redont. The heavy ball with friction method, i. the continuous dynamical system: Global exploration of the local minima of real-valued function by asymptotic analysis of a dissipitive dynamical system. Communications in Contemporary Mathematics, 2(1): 1-34, 2000.
Hedy Attouch and Gerald Beer. On the convergence of subdifferentials of convex functions. Archiv der Mathematik, 1993.
Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi- algebraic and tame problems: proximal algorithmss, forward-backwand splitting, and regularized seuss- methods. Mathematical Programming, 2011.
Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In International Conference on Machine Learning, pages 468-477. PMLR, 2021.
Heinz H Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330-345 -48800-348,10 2017.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Jérôme Bolte, Aris Danilidis, and Adrian Lewis. Tame functions semismooth. Mathematical Programming, 2007.
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.
C. Combari and L. Thibault. On the graph convergence of subdifferentials of convex functions. Proceedings of the American Mathematical Society, 1998.
Richard Courant and Fritz John. Introduction to Calculus and Analysis. Springer New York, 1989.
Charles Dossal. A necessary and sufficient condition for exact sparse recovery by minimization. Comptes Rendus Mathematique, 350(1-2):117-11)) 2012.
L. van den Dries. Tame Topology and O-minimal Structures. Cambridge University Press, 1998.
Miroslav Dudik, Robert E Schapire, and Matus Telgarsky. Convex analysis at infinity: An introduction to astral space. arXiv preprint arXiv:2205.03220 2022.
Mathieu Even. Scott Pesme, Suriya Gunasekar, and Nicolas Flammarion. (s)gd over diagonal linear networks: Implicit bias, large stepsizes and edge of stability. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in neural information processing systems, 30, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841 PMLR. 2018
11

---

Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint (ttv:1803.73000 2018.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pages 772-804. PMLR, 2021.
Ziwei Ji, Miroslav Dudik, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. Conference on Learning Theory, pages 2109-2136.
PMLR. 2020.
Beata Kocel-Cynk, Wieslaw Pawlucki, and Anna Valette. short geometrie proof that hausdorff' limits are definable in any o-minimal structure. advg, 2014.
Mohammed Laghdir and Michel Volle. A general formula for the horizon function of convex composite function. Archiv der Mathematik, 1999.
B Lemaire. An asymptotical variational principle associated with the steepest descent method for convex function. Journal of Convex Analysis, 3:63-70, 1996.
Zhiyuan Li, Tianhao Wang, Jason D Lee, and Sanjeev Arora. Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent, Advances Neural Information Processing Systems, 35:34666-34640, 2022.
Shengchao Liu, Dimitris Papailiopoulos, and Dimitris Achlioptas. Bad global minima exist and sgd can reach them. Advances in Neural Information Processing Systems, 33.8543-8552, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogencous neural networks. In International Conference on Learning Representations, 2020.
Edward Moroshko, Blake E Woodworth, Suriya Gunasekar, Jason D Lee, Nati Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale training accuracy. Advances in neural information processing systems, 33:22182 221922219,3 2020.
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. The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-34288 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 Artificial Intelligence and Statistics, pages 3051-3059. PMLR, 2019c.
Hristo Papazov, Scott Pesme, and Nicolas Flammarion. Leveraging continuous time to understand momentum when training diagonal linear networks. In International Conference on Artificial Intelligence and Statistics, pages 3556-3564. PMLR, 2024.
Scott Pesme and Nicolas Flammarion. Saddle-to-saddle dynamics diagonal linear networks. Neurips, 2023.
Scott Pesme, Loucas Pillaud-Vivii and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34, 2021.
R. Tyrrell Rockafellar and Roger J. B. Wets. Variational Analysis. Springer Berlin Heidelberg, 1998.
Ralph Tyrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
Daniel Soudry, Flad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 2018.
12

---

Haoyuan Sun, Kwangjun Ahn, Christos Thrampoulidis, and Navid Azizan. Mirror descent maximizes generalized margin and can be implemented efficiently. Advances Neural Information Processing Systems, 35, 2022.
Haoyuan Sun, Khashayar Gatmiry, Kwangjun Ahn, and Navid Azizan. A unified approach to controlling implicit regularization via mirror descent. arXiv preprint arXiv:2306. 13853, 2023.
Lou Van den Dries and Chris Miller. Geometric categories and o-minimal structures. 1996.
Aditya Vardhan Varre, Maria-L Vladarean, Loucas Pillaud- Vivien, and Nicolas Flammarion. On the spectral bias of two-layer linear networks. Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32, 2019.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673. PMLR, 2020.
Fan Wu and Patrick Rebeschini. imglicitte in matrix sensing via mirror descent, Advances in Neural Information Processing Systems, 14:20558-20570. 2021.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICI.R, 2017.
13

---

Organisation of the Appendix.
Appendix A, we provide the proofs of the existence and uniqueness of (MF), of the convergence of the loss, the divergence of the iterates and the proof of Lemma 1.
2. In Appendix B, we provide all the proofs concerning the construction of the horizon shape and that of our main Theorems and 3.
14

---

A Proofs of properties of the mirror flow in the classification setting
We start by proving the existence and uniqueness of (MF) over Ikz-- The proof is standard and relies on ensuring that the iterates do not diverge in finite time.
Lemma 2. For any initialisation Bu E R., there exists a unique solution defined over Rzo which satisfies (MF) for all 2 0 and with initial condition 3t = -B-
Proof. From Assumption we have that is differentiable, strictly convex and its gradient is coercive. Consequently, Vø bijective over Rd (see Rockafellar [1970], Theorem 26.6). Furthermore, the Fenchel conjugate ø is differentiable over Rd and (VΦ) - VØ*.
To prove the existence and uniqueness of a global solution of (MF), we first consider the following differential equation:
du = (
(5)
with initial condition Uz=0 = VΦ (Bo).
Since I is C2, VL is Lipschitz on all compact sets. Furthermore, since & is p.s.d., VØ-= (V6)- C³ and therefore Lipschitz on all compact sets. Hence V o VΦ" is Lipschitz on compact sets and from the Picard-Lindelöf theorem, there exists a unique maximal (iee which cannot be extended) solution (ux) satisfying eq. (5) such that 4==0 = Vœ" (Bo). We denote [0, max) the intersection of this maximal interval of definition (which must be open) and Rzo. Our goal is now to prove that Tax = +o0. To do so, we assume that Tmax is finite and we will show that this leads to contradiction due to the fact that the iterates 3t cannot diverge in finite time. Let 3r == (w) and notice that 3g is therefore the unique solution satisfying (MF) over [0, Tmax) with Bi=0 = Su-
Bounding the trajectory of Be over [0, mmax). Pick any B E I2 and notice that by convexity of L:
d (3, - (VL B) S - (T.(B) T.(9)) T(B) Temin-
dt
Where Lmin is lower bound on the loss. Integrating from t t < T max get:
(a(3, B.) I (L(3) Limin) + (3 Bb)
I Tmax (L(3) - Lmin) + (3 30)
Therefore, due to Assumption 2, the iterates 3g are bounded over [0, Tmax). The proof from here is standard (see e.g. Attouch et al. [2000], Theorem 3.1): from eq. (5) we get that in is bounded over [0, mmax) and suPpe(0,TTma)) || =: C < +00 which means that ||u. we || S Clt - t'). Hence litt,-Tmax Ue Use must exist. Applying the Picard-Lindelöf again time T with initial condition uhe violates the initial maximal interval assumption. Therefore Tmax + which concludes the proof.
We now recall and prove classical results on the mirror flow in the classification setting. Proposition 1. Considering the mirror flow (8x)22,, the loss converges towards and the iterates diverge: lim I(3:) = 0 and lim ||3:]] = 400. 100
t0000
Proof. The loss decreasing, di L(a) (VL(3). B.) -VV26(8)) VL(B)) S where the inequality is due to the convexity of the potential á.
Convergence of the loss towards O. Now consider the Bregman divergence between an arbitrary point 3 and Br:
(8, - - Bb) 2
which is such that:
d
Do(3,B)) = < Vo(3)), B) di
=-VVL(B),.
- -(L(3) - I(())
(6)
15

---

where the inequality is by convexity of the loss. Integrating and due to the decrease of the loss, we get that:
L(B:) - ( ((3,) ds
$ ((()) + Do(3, Bo) (.)
S L(B) + Po(3,Bo)
Since this is true for all point B, we get that ((3,) I SER L(3) + Da(8,8)) remains to show that the right hand term goes assumption we get that there exists 3 such that min (F,, 3*) > Since ((AB.) - 0, we can
: >> 0. by the separability
goes to infinity. To show this, let
A-100
choose À big enough such that L(X8*) and then 2x large enough such that 12 DD8" Bo) The loss therefore converges to O.
Divergence of the iterates.
For all [n). ((na(ar (t)) s L(B() t-+00
0. Due to the assumptions on the loss, this translates into
Ye (a 86) - oc, hence || - 0. t000
10000
Introducing a few notations. Before giving two important lemmas, we provide a few notations.
Recall that Z is the data matrix of size d whose jth row is yız;, we then have that V V( Z ll (Z3), where is applied component wise. We now denote by ((3) the vector in R equal to:
(Z
((3) = peee-((E, (E, B))))
Notice that due 0, l' < 0, 8- is increasing and l' is decreasing, have that g(B) > 0 and that for all in E [n].
(yio (Fio B3)
('(y (Fi 3)) (((yn (F B)))) $ 1.
q(3)
e (V B)1))
Therefore ( E (0. 1|".
We further denote
0t := = - Σ
Ulys Bc)))) >
This way we can simply write VL(3) -a, with = g(B.). Integrating the flow (MF), write:
a
Vo(3,) Vo(36) - S'' VL(3.)ds
= Vo(3)) + zT/ S/" a.g.ds.
Two lemmas. the following lemma we recall and prove that coordinate [k] must be equal to 0 if datapoint zg is not a support vector of Boo.
Lemma 3. For some function C. cc, if the iterates 3, & converge towards vector which
denote Boo and qe converges towards a vector 9:0 E [0, 1) Then holds that:
qo0
[k]
if
yk ( Boo) min ye (2i, Boo)
ISi5n
In words, 9o0
[kolk] [k] = 0 if I is not support vector.
16

---

Proof. Recall that
(Zz3,)
((:)) ( B.))))
From Proposition 1, we have that min Ve Bao) 0 and we denote this margin Now consider E [n] which loss of generality assume that y1 (21, minigign yi (m Boo). We denote by (yk y1 ) > 0 the gap. Then
support vector, i.,, yk (ar, Boo) > min (o Boo) and without
(TK,
((3)) = "(e-1(E, ((C.yi(T (.))))
(C 91))
(CCy (21,
We write Be 3x0 + r2 where (r9)220 E B& converges to O. For big enough, have that yn (arks Br) 2 yı (Nt, (oo) - 2 and yn (211 Bc) S yn (21, Boo) + 4. Therefore for / large enough, since l' is negative and increasing:
(BAM) e(Ci(M Boo) - 6/4)) (CClln + 6/4))
+ 8/4))
0,
C(C,(r+ + 6/2))
t-:00
where the last term converge due the exponential tail of -l' and that C. - oC.
We here reformulate and prove Lemma 1. Lemma 4 (Reformulation of Lemma 1). Denoting = -E Elyilos (())) > we
have that Oo a(3,)ds +o0. For f(z) exp(-2), this translates So L(Ba)ds -
Proof. Recall that Vo(3,) = vo(30) + TT Jo aa(3.)((3.)d) therefore
V & (V + amall J a(B.)a(3.)(llds
$ |v + Σ |(all) [' a(B.)ds.
Where the first inequality due to the triangle inequality and the second to the fact g(3) E (0, 1)" Since the iterates diverge, have from Assumption 2 that [|Vo(8))] t
and therefore that
So a(3,)ds
400.
17

---

B Differed proofs on the construction of 6x
As mentioned in the main text, the following property highlights the fact that all 'reasonable' potentials have a horizon shape.
Proposition 2. If any of the three following conditions hold: (i) & is a finite composition of polynomi- als, exponentials and logarithms, (ii) @ is globally subanalytic, (iii) @ is definable in o-minimal structure on IR; then & admits a horizon shape S
Proof. Note that points (i) and (ii) are particular cases of (iii) [Dries, 1998, Bolte et al., 2007]. If h is definable in a o-minimal structure, then so is the sublevel set S. for > 0, and so is the normalization factor RG since be defined in first-order logic as
Re = fr R: 33* E Sc, || = and V3 Se, || rr).
Therefore, (Se)e5o if a definable family of definable and compact sets. Then so is the family (5(-1)re(o.1)) Since all the sets belong to the unit ball of Rdd, they lie in the sets of compact subsets of B 1). This set is compact for the Hausdorff metric [Aliprantis and Border, 2006, Thm 3.85]; therefore, there exists sequence (t&)xEN such that fx + 0 and (+ )KEN converges to some set S.
We can then apply Corollary 2 of Kocel-Cynk et al. [2014], which states that there exists a definable are y (0, 1] (0, 1] such that lim,-po 7(7) and 5 lim, ST()- This implies that the limit is uniquely defined and therefore that lim S S.
The next corollary is more general restatement of Corollary 1. It shows that the construction of &oc enables to take the limit lim, Vo(..)) (Bxo)
Corollary 2. Assume that & admits non-degenerate horizon shape S Then its horizon function doo satisfees the following properties.
1. deo convex and finite- valte- on Rdd.
2. Let (Bz)s20 be continous sequence such that when oc:
3
Vo(3.)
(a) || oc,
(b)
3 for some 3 RRR.
(c)
for some R
|B
VV(3.)]
Then g is proportional to subgradient of de 3::
g E x0 for some X > 0.
Proof. The sequence of sets (Sc) is contained in the compact ball B(0, 1); therefore, Hausdorff convergence is equivalent to Painlevé- Kuratowkk convergence [Rockafellar and Wets, 1998, Section 4.C]. Hence, as (S.) are convex, so their limit Sxx [Rockafellar and Wets, 1998, Prop 15]. follows that Φx is convex [Rockafellar and Wets, 1998, Ex 3.50].
Since S.x is non-degenerate, there exists radius ro such that (00, ro) Soo, which implies that 6oo (3) is finite-valued for every B.
To prove point (ii), consider the sequence of functions (ne)eso formed by the indicators of convex sets 5.:
0
i E Sc.
ne( (T. (3) +00
otherwise.
Note that the epigraph of n) is S_ R these sets also converge to Sx x R [Rockafellar and Wets, 1998, Ex 4.29], from which we conclude that function π)c converge epigraphically to the indicator function 7oc of Sox (1) Is_.). ). We can then apply Attouch's 's theorem [Attouch and Beer, 1993, Combari and Thibault, 1998] ensuring that the graph of the subdifferentials n)
g( ((8,g)
On.(3))
converge in Painlevé-Kurann Kuratowski sense to the graph (()))))) of subdifferential of 7/o- This means that if a sequence (Be, ge)coo such that (3e, ge) E ((m).) for every converges, then its limit belongs to G(0m.o).
18

---

Consider now sequence (Be)s>0 satisfying the conditions described in (ii). Since it diverges to infinity and Φ coercive, have ((3,) + oc, and we may assume w.l.o.g that d(3,) for all s.
We have by definition of sublevel sets that 3. E Sasa.). and therefore the gradient (p. belongs to the normal cone of Sot,.) 8g (indeed, the gradient is orthogonal the level sets; e-g., [Courant and John, 1989, Chapter 1.5)). Since the normal cone of a convex set is the subdifferential of its indicator [Rockafellar, 1970, Section 23), we thus have
(d,).) E 0ls (3a);
(8)
Consider now the normalized levels sets as defined in (4). Denoting
Ba
R
we have 3, E Spco,) and thus by simple rescaling (8) becomes
Vo(3,) E dIsua. (Bs)
Since 0Ig, is a cone (the normal cone to S.), this also holds for any positive multiple of Vo(5.). We deduce that for every 8 > 0
3r [VV(())) )
Vo(3,)
G(ōmota.))
Note that since B, belongs to the normalized level sets, this sequence is bounded. We can extract subsequence (Bax: V I 120 which converges a limit point (3, 9). By the previous remark on graphical convergence subdifferentials, we have (3.g) E s.. i.e.
ve(s.g)
Ò E (B).
We need prove that 3 not Since & is strictly convex, the level set (o(B) = c} is exactly the boundary of the sublevel set {6(3) _ c). Therefore, B, lies on the boundary of Spce. and hence so does 3. lie on the boundary of S. Since 0 is in the interior of Soc, it also belongs to the interior of S (a,).) for s larger than some so. Then, there exists ro > 0 such that B(0, ro) C Sa(s.) for 2 so- By definition boundary, we then have for s 2 s0 ||3,1 To, which leads to || > 0.
To achieve the desired result; we need to relate (3, 9) to (B.g). First, notice that by construction we
have necessarily و g limg-+o0 Vo(3.)/11 (3.) ||. Then, note that
3sn
8 lim BSu
lim k=
||
Ro(sa)))
118 Taking the norm the second limit, we have || = lim Ro(Fo)) limit yields
Injecting back in the first
Ber
Ro(gnn
3
3 = lim
# 00c Ro(3..)
1B
||:1||
Therefore, (9) becomes
01s (11/1113).
This means that ğ belongs to the normal cone of S.0 at || [Rockafellar, 1970, Sec. 23). We note the level set {B dx (B) I do (11113) } is exactly 7Sx0 for some T > 0. We use Corollary 23.7.1 from Rockafellar [1970] which states that if vector is in the normal of the level set of disc then must be a positive multiple of a subgradient. This implies that that there exists 2 such that
g E X0 (113113).
Finally, À > 0 since || = 1, and 0e (131) = de (3) by positive homogenity &ze.
We now prove main result, which restate here.
19

---

Theorem 2. Assume that & admits non-degenerate horizon shape and let Oo be its horizon function. Assuming that the following ~ max-margin problem has a unique minimiser, then the mirror flow normalised iterates Be
converge towards vector Bo and ||
8,
Bo x arg min @ ( under the constraint
min Ve (2,, B) 2 1,
BERS
sein]
where the symbol & denotes positive proportionality.
The proof essentially follows exactly the same lines as in Section but taking into account the fact that the loss is not exactly the exponential one.
Proof. Recall the definitions of the quantities ae and qe given above Equation (7) which enable to write:
Vo(B.) = Vo(3)) + zT L agg,ds.
Similar to the time change we performed in Section 3, we consider 0(1) = f a,ds. From Lemma 4, 0 is bijection over R22 and perform the time change Br = BB-1(()- Due the chain rule, after the time change and dropping the tilde notation we obtain:
Vo(8)) = vo(3o) + - /// gods.
Dividing by we get:
Vo(8)= 1 Vo(33) + 2T t
(10)
where &. = t So g.ds corresponds to the average of (4e)sgi-
Extracting a convergent subsequence: We now consider the normalised iterates 3, = [[ and up extraction we get that B, 3ox Since a is bounded function, up second extraction, have that 4: + Toc. and the same holds for its average: Tr - 9oo. Taking the limit in Equation (10) we immediately obtain that:
6,
lim t vo(3i)) 7 4000
which also means that
Vo(3)
7 900
[b(3,)]
1+000 1 gool
We can now directly apply Corollary and there exists >> such that:
z Yco E X0 (Bo0)
The end of the proof is then explained in Section 3.
Finally recall and prove Theorem 3 which provides simple formula for the horizon function in the case of separable potentials.
Theorem 3. Under Assumption the potential & admits a non- den-eegeeeeate horizon shape and its horizon function such that there exists X > O such that for every TRd.
8
6oo (3) = A lim 17 --
-
20

---

Proof. Lipschitzness, upper and lower boundedness. For > O, let us denote by hy : B + n o (o(B/n)) and notice that (hn = (F o (B(B//))
(2. ((8,/1))) ketd 2 Since @ 2 0 and that
o and ş are increasing we get that that (h,
[o. 10. Therefore (hy) are uniformly
Lipschitz-continuuus. Consequently, for all B. hn (8) is upper-bounded independently of Lastly,
since y 2 O, notice that (3) 2 min; [3:] > for all / #0. 0.
Point-wise and epi-convergence of h.p For all B, by composition, H 17 47 (o(B/r) is definable function, the monotonicity Lemma [Van den Dries and Miller, 1996] (Theorem 4.1) ensures that it has unique limit in R which we denote ho (B). From the uniform Lipschitzness of hy get that (n, 3) E Rzo x Rd + (3) is continuous. Hence for all sequence T)s O, get that hng epi-converges to hg. Therefore (epi hy ) converges in the Shinevv-KKuatowe sense towards epi hmp
Link between the level sets of hi and those of Φb. To conclude the proof it remains notice that for all c 2 0:
{3 E R ((3) - cf = ( R hn(3) - mp (c)).
Therefore letting T) = 1/1--1006000 we get that
ne S. E h. (3) 1}.
This simply means that is an appropriate normalising quantity, it replaces the normalisation by the radius of Se. Since {3 E Rdd hy. (3) S 1) converges in the Ghinlevé-Kurtowwrr sense towards {3 Fd ho(B) S 13, we get that R. S. converges towards the same set. However, with our previous construction, we also have that S. converges towards Sx.. The sets Sxx and [B e RR, (3) S 1} are therefore proportional and hg x doc which concludes the proof.
21

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] " is generally preferable to "[No]" it is perfectly acceptable to answer " "[No] provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often
nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Theorems 2 and 3 give the results which are claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We included a "Limitations" paragraph at the end of the main paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
22

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- lant role in developing norms that preserve the integrity of the community, Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The main assumptions the loss, potential and dataset given at the beginning of the paper. If an additional assumption is required, clearly stated in the result. The proofs are all deferred the appendix but clearly state in the main text where they can be found.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide extremely toy examples which are very easy to reproduce. The dataset is shown in Figure 1 and, as stated Section 5, we perform mirror descent over the dataset with the exponential loss.
Guidelines:
The answer NA means that the paper does not include experiments.
23

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The code behind the experiments is straightforward and can casily be repro- duced.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wttpsscccppbppcc////cppppppppppp htwpubliiggggdes.../eee /CodeSubmisi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
24

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The considered potentials and loss are given. The value of the step-size is not given as it does not have any relevance.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
The use of error bars is not relevant in our work: there is no source of stochasticity.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification:
It is clear that our experiments easily be reproduced by any computer.
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //tn:///nsssseee http://arrrpp..pppppii////////// http///b..tttttttttttlleeeleeeee ines?
Answer:
[Yes]
Justification:
We have checked the Code of Ethics and our work respects
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Given the theoretical aspect of our work, we don't 't think are work leads to any direct positive negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
functioning correctly, harms that could arise when the
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
26

---

Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: There is no use of existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi whooodewthhheeee..o com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
27

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "5az731BP58", "reviewer": "Reviewer_DbGr", "summary": "This paper considers the asymptotic behaviour of the mirror descent (MD) algorithm for a linear classification task. It is shown that the classifier (hyperplane orthogonal to $\\beta$) will be a max-margin classifer, where the margin is determined by some unknown horizon function $\\phi_\\infty$. This works extend prior work which consider $\\ell_p$ and homogeneous potential functions for MD, and shows this result for very general $\\phi$.", "questions": "- Are there any classes of potential functions (other than the norms and $L$-homogeneous ones), for which $\\phi_\\infty$ may be calculated or approximated?\n\n- Beyond gradient descent, is there any work that quantifies the rates of convergence to max-margin classifiers? Is this even possible?", "limitations": "The limitations are discussed.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper makes an interesting statement about behaviour of mirror descent on classification tasks, will minimal assumptions. In doing so, it takes a big step and extends previous work to the cover general potential functions.\nThe paper is well written and the figures help with understanding the concepts of convergence.\n\n---\n*While I could understand the paper, this is not my area of research. I do not find myself fit to evaluate the paper on soundness, relevance to the sub-field and importance of contributions.*", "weaknesses": "- The paper does not characterize $\\phi_\\infty$ in terms of the bregman potential $\\phi$ (and other relevant entities). \nThe main result expresses that there exists some function, that is minimized by $\\bar \\beta_\\infty$, the direction of the classifier as $t\\rightarrow \\infty$. \nI think this limits the relevance and strength of the result. For instance, this does not help with interpretability compared to the case where we can prove the optimization algorithm converging to a max-margin classifier wrt the $\\ell_2$ norm.\n\n- I am not sure about relevance and use-cases of the mirror descent algorithm with very general potentials. As far as I know, typically, a small set of norm-based or entropic (neg-ent, tsallis, etc) are used within applications of ML. So while the theorem makes an interesting statement for an optimization standpoint, I'm not sure how relevant it is for the ML community. The theorem is also not entirely relevant to the pure optimization community since it's for the specific case of linear classification with finite data.\n---\n*While I could understand the paper, this is not my area of research. I do not find myself fit to evaluate the paper on soundness, relevance to the sub-field and importance of contributions.*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their report and relevant comments.\n\n**Q1:** In Theorem 3, we provide a formula for computing the horizon function when the potential $\\phi$ is **separable**. In that case, $\\phi_\\infty$ can be obtained by computing the limit at infinity of a simple one-dimensional function. We apply this to two examples of non-homogenous potentials in Section 5: the hyperbolic entropy and the cosine entropy. \n\nFor non-separable potentials, there is a priori no straightforward formula and one has to find the limiting shape $S_\\infty$ towards which the normalised sublevel sets $\\bar{S}_c$ converge to as $c \\to \\infty$. However, we emphasize that the separable case covers almost all known examples.\n\n**Q2:** By building on the arguments of Proposition 1 (line 467), we could show that $L(\\beta_t)$ decreases with rate $\\tilde{O}(1/t)$. However, this convergence rate does not inform us on the rate of convergence of the normalized iterates $\\bar \\beta_t$ to the limiting direction. This question is indeed a challenging open problem and is left for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3v3Hdqiyj9", "reviewer": "Reviewer_hMTV", "summary": "This manuscript examines the implicit bias of mirror descent on a classification problem when the dataset is linearly separable. Assuming a coercive gradient, it demonstrates that the implicit bias is characterized by the shape of the level set of the mirror potential near infinity. Their analysis successfully recovers existing results for p-norm potentials and identifies the implicit bias of the potentials emerging in the analysis of linear neural networks. Additionally, it leaves the characterization of the implicit bias when the gradient is not coercive as an interesting open problem.", "questions": "In line 123, the authors suggested that the logistic loss satisfies the conditions in Assumption 1. However, it is clear that the logistic loss does not have an exponential tail. Could they clarify whether this is a mistake or if there is an underlying argument supporting their claim?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I think the paper is very well-written and has a solid contribution.\n\nIt addresses an important problem, aiming to understand the implicit bias of neural networks. Prior work has shown that the dynamics of linear networks can be characterized by mirror descent, highlighting the relevance of this study.", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive report and relevant comments.\n\nIt can be verified that the logistic loss indeed satisfies the exponential-tail condition of Assumption 1, since $\\ln(1+\\exp(-z))$ is equivalent to $\\exp(-z)$ as $z \\rightarrow + \\infty$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "07N7ePCKz3", "reviewer": "Reviewer_j6HU", "summary": "This paper examines the implicit bias of mirror flow (the continuous-time counterpart of mirror descent) in the context of binary classification for linearly separable data. Given that the problem has infinitely many solutions, obtained at infinity, the authors aim to identify which solution is achieved through mirror flow. Assuming an exponential tail on the loss function, the authors demonstrate that mirror flow converges directionally to a maximum margin classifier, where the margin is characterized by a horizon function of the mirror potential. This result extends many existing works, and numerical experiments are provided to verify the findings.", "questions": "1. In the main result, Theorem 2, the conclusion that the normalized mirror flow converges to a vector \\(\\bar{\\beta}_{\\infty}\\) is drawn even when the \\(\\phi_{\\infty}\\)-max-margin problem does not necessarily have a unique solution. Can the authors provide more insight on this? If I understand correctly, in the motivating example, \\(\\bar{\\beta}_{\\infty}\\) is a subsequence limit. If the \\(\\phi_{\\infty}\\)-max-margin problem does not have a unique solution, this result cannot be extended to the whole limit, unlike in the gradient flow case with quadratic potential.\n2. More explanation could be provided for Figure 1. In particular, it would be interesting to see the trajectories of the mirror flows on the plane, rather than only showing the limit.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and well-organized. Despite the technical nature of the analysis and results, the paper is relatively easy to follow.\n2. The paper is also well-motivated. Although mirror descent is not commonly used as an algorithm for training neural networks, analyzing its convergence is valuable for understanding the implicit bias of gradient descent in various neural network architectures.\n3. I did not verify the details of the proof. However, the paper provides several motivating examples, including the quadratic potential corresponding to gradient flow, which makes the results quite convincing.\n4. The main results extend several prior works.", "weaknesses": "Although the authors have stated that the convergence rate is left for future study, it would be beneficial to provide at least empirical evidence of the convergence rate. The authors mentioned in line 294 that the convergence rate varies across different potentials.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their report and relevant comments.\n\n**Weaknesses**\n\nThe comment we make line 294 concerns the **training loss** convergence rate. We provide empirical evidence Figure 1 (left), we observe that the exact rate indeed depends on the potential. Also note that standard results from convex optimisation enables to show an $\\tilde{O}(1 / t)$ upperbound on the rate (see proof of Proposition 1).\n\nLines 303-304, we refer to the convergence rate of **the normalised iterates** towards the maximum margin solution, which we leave for future work. It would depend on the speed at which the normalised sublevel sets $\\bar{S}\\_c$ converge towards the limiting shape $S_\\infty$.\n\n**Questions**\n\n**Q1:** We indeed need to assume that the $\\phi_\\infty$-max-margin problem has a unique solution, otherwise there could exist multiple subsequential limits. This is stated in the assumptions of Theorem 2. We also discuss sufficient conditions for this assumption to hold on lines 239-243.\n\n**Q2:** We will add more details concerning Figure 1 in Section 5. We agree with the reviewer that plotting the full trajectory is interesting and we will add it in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mo0ZEMbJVn", "reviewer": "Reviewer_Jqcr", "summary": "In this paper, authors study the implicit bias of the mirror descent algorithm, from the perspective of the optimization trajectory of the continuous flow version. They propose the conceptions of horizon shape and horizon function $\\phi_\\infty$ to help characterize the properties of mirror flow at infinity. Since $\\phi_\\infty$ defines a norm, they prove that the mirror flow will eventually converge in direction to a max $\\phi_\\infty$-margin solution under the linear exponential-tail classification setting. Their findings contribute to a deeper understanding of the inherent characteristics of mirror descent across a wide range of potential functions.", "questions": "1. I'm really curious about whether this result could be extended to the q-homogenous neural networks like [1], cause it seems this result was also derived from the KKT condition of the lagrangian function.\n2. I guess there might be no minus in line 461 for the first equality.\n3. Could the author explain why they need to prove the uniqueness of the flow solution in Lemma 2, since this was not covered in the previous work, like [1][2]. Moreover, why do the authors need to prove that $\\int_0^t a(\\beta_s)ds \\to \\infty$ for Lemma 1.\n4. What is the definition of $h_\\infty$ in line 535 and $h(\\cdot)$? Moreover, could the author explain more about how to derive formula (8) ?\n\n[1] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.\n\n[2] B.Wang, Q. Meng,W. Chen, and T.-Y. Liu. The implicit bias for adaptive optimization algorithms on homogeneous\nneural networks. In International Conference on Machine Learning, pages 10849–10858. PMLR, 2021.", "limitations": "No limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The result of this work is solid, containing the general class of potential functions, and the authors derive a calculation rule of $\\phi_\\infty$ for a general class of potential functions.\n2. The paper is informative and well-structured, particularly in section 3. By using the example of gradient descent within the framework established by the preceding lemmas, which is a special case of mirror descent, the authors clearly outline the reasons why mirror flow will eventually converge in direction without complicated formulas.", "weaknesses": "1. Since mirror descent is not so popular in the practice of machine learning problems,  there could be more discussion about the implications of their results. For example, Figure 1 is really interesting as it reveals that the mirror descent shares the same structure of implicit bias with the steepest descent [1], what is the essence of such similarities?\n2. The setting of an infinitely small learning rate, i.e., optimization flow,  might be a little strong under a simple linear classification problem compared to the previous works. I suggest the authors state the technical challenges of the discrete optimization process of mirror descent.\n3. I might be wrong, but it seems not strict to apply the Bolzano–Weierstrass theorem to an uncountably infinite set at page 5, line 160 and 61.\n\n[1] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832–1841. PMLR, 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough report and relevant comments. We will take them into account and make the appropriate changes in the revised version. Please find below our response to the comments.\n\n**Weaknesses**\n\n**W1:** Indeed, our result has connections with Theorem 5 from Gunasekar et al. (2018). Note first that the updates of steepest descent and mirror descent are different and one cannot be seen as a special case of the other (unless the geometry is Euclidean). For a norm $\\Vert \\cdot \\Vert$, the steepest descent update is given by $w\\_{t+1} = \\text{arg min}\\_{w} \\ L(w\\_t) + \\langle \\nabla L(w\\_t), w - w_t \\rangle + \\Vert w -  w_t \\Vert^2$  whereas the mirror descent update is given by $w\\_{t+1} = \\text{arg min}\\_{w} \\  L(w\\_t) + \\langle \\nabla L(w\\_t), w - w_t \\rangle + D\\_\\phi(w, w_t)$  for a potential $\\phi$. \n\nWe can however observe the following connection: if the horizon function $\\phi_\\infty$ is a norm (this is the case when $\\phi$ is symmetric), then **the implicit bias induced by mirror descent is the same as that of steepest descent with norm $\\phi_\\infty$**. In other words, $\\phi$-mirror descent is asymptotically equivalent to $\\phi_\\infty$-steepest descent.\n\nRegarding the possible implications: our result could be used to study the mirror flow with new potentials that arise from gradient flow more complex neural network architectures, some of which are still under investigation (see answer to Q1 below).\n\n**W2:** The same results could be derived for mirror descent with finite step size, without major additional difficulties. We chose to study mirror flow as it simplifies the proofs and the presentation.\n\n**W3:** Indeed, we were (intentionally) a bit sloppy with the math, but the reasoning is correct. To make the derivation rigorous, one has to first consider any countable sequence $(t\\_n)\\_{n \\in \\mathbb{N}}$ with $t\\_n \\to \\infty$ as $n \\to \\infty$ and then consider the sequence $(\\bar{\\beta}\\_{t\\_n}, q(\\beta\\_{t_n}))\\_{n \\in \\mathbb{N}}$. We can then rightfully apply the Bolzano–Weierstrass theorem. Since the final limit $(\\bar{\\beta}\\_\\infty, q\\_\\infty)$ does not depend on the sequence $t_n,$ we can indeed conclude that $(\\bar{\\beta}\\_{t}, q(\\beta\\_{t}))_{t \\in \\mathbb{R}}$ must converge towards it. We will clarify this argument in the revised version.\n\n**Questions**\n\n**Q1:** The link between gradient flow on $q$-homogeneous networks (as in [1]) and mirror flow (as in our setting) is still opaque. As discussed in our conclusion section, gradient flow on a depth $q$ **diagonal** linear network can be seen through the lens of [1], as well as through the lens of mirror flow (as in our paper). However, whether a link exists in more general settings is still unclear and remains a very interesting question for future work.\n\n**Q2:** It is indeed a typo, thank you for pointing it out.\n\n**Q3:** The main purpose of Lemma 2 is to ensure that the mirror flow solution exists and that it is well-defined for all $t \\geq 0$. This fact is not trivial since, in a more general setting, the solution could \"blow up in finite time\". Previous work does not always prove global existence and implicitly assumes it to be true. Uniqueness is obtained as a by-product.\n\nRegarding the fact that $\\int_0^t a(\\beta_s)ds \\rightarrow \\infty$, it is an essential result for the main proof. We need it to apply the time change followed by the Cesaro argument (see lines 580 to 587 in the appendix).\n\n**Q4:** We made a notation error throughout the proof of Corollary 2: we used $h$ instead of $\\phi$. We will fix this.\n\nFormula (8) stems from the fact that the gradient of $\\phi$ is orthogonal to its level sets (we can invoke a result from multivariate calculus such as [1]). This means that $\\nabla \\phi(\\beta_s)$ belongs to the normal cone of $S_{\\phi(\\beta_s)}$ at $\\beta_s$. The subdifferential of the indicator of a convex set is given by its normal cone [2, Chap. 23], which allows to conclude. We will add these details to the revision.\n\n[1] Richard Courant; Fritz John (1999). Introduction to Calculus and Analysis Volume II/2. \n\n[2] R. Tyrell Rockafellar (1973). Convex Analysis.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper examines the implicit bias of mirror flow (continuous-time mirror descent) for linearly separable classification problems. The main result shows that, under mild assumptions, mirror flow converges in direction to a maximum margin classifier characterized by the horizon function of the mirror potential. This extends previous work to more general potential functions.

Strengths:
- Solid theoretical contribution extending prior results
- Well-written and structured paper 
- Relevant to understanding implicit biases in optimization

Weaknesses:
- Limited discussion of practical implications
- Some technical details need clarification

The reviewers were generally positive, with ratings ranging from 5 to 7. They found the paper to be technically sound with good to excellent contributions. However, several points require attention before publication:

1. Expand discussion on practical implications and connections to related work
2. Clarify some technical details in proofs and notations
3. Add more explanations for figures, especially trajectories in Figure 1
4. Fix minor typos and notation errors identified by reviewers

Overall, this paper makes a valuable contribution and is recommended for acceptance, contingent on thorough revisions addressing the above points. The authors should carefully consider all reviewer comments when preparing the final version.
Decision: Accept (poster)