Implicit Bias of Mirror Flow on Separable Data

Authors: scott  pesme
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:15:42

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.

Main paper: 
 introduction: 
 Heavily over-parametrised yet barely regularised neural networks can easily perfectly fit a noisy training set while still performing very well on unseen data [Zhang et al., 2017] . This statistical phenomenon is surprising since it 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, it must be because the optimisation process has steered us towards a 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 of 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 ℓ 2 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 ℓ 2 -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 a range of non-linear parametrisations [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 to 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 a 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 et al., 2023] . Our paper bridges this gap by formally characterising the implicit bias of mirror descent for separable classification problems. M m Z 1 d Z n q F s O Q j v H h Q x K v f 4 8 2 / c Z L s Q R M L G o q q br q 7 g l g K g 6 7 7 7 e T W 1 j c 2 t / L b h Z 3 d v f 2 D 4 u F R 0 0 S J Z r z B I h n p d k A N l 0 L x B g q U v B 1 r T s N A 8 l Y w v p 3 5 r S e u j Y j U A 0 5 i 7 o d 0 q M R A M I p W a n n u Y 3 p R m f a K J b f s z k F W i Z e R E m S o 9 4 p f 3 X 7 E k p A r Z J I a 0 / H c G P 2 U a h R M 8 m m h m x g e U z a m Q 9 6 x V N G Q G z + d n z s l Z 1 b p k 0 G k b S k k c / X 3 R E p D Y y Z h Y D t D i i O z 7 M 3 E / 7 x O g o N r P x U q T p A r t l g 0 S C T B i M x + J 3 2 h O U M 5 s Y Q y L e y t h I 2 o p g x t Q g U b g r f 8 8 i p p V s p e t V y 9 v y z V b r I 4 8 n A C p 3 A O H l x B D e 6 g D g 1 g M I Z n e I U 3 J 3 Z e n H f n Y 9 G a c 7 K Z Y / g D 5 / M H Q I C O 4 Q = = < / l a t e x i t > 10 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " g f D D G 5 H d C 2 u j 5 9 m X U + 2 x x 3 l A B w E = " > A A A B 6 H i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K o l I 9 V j 0 4 r E F + w F t K J v t p F 2 7 2 Y T d j V B C f 4 E X D 4 p 4 9 S d 5 8 9 + 4 b X P Q 1 g c D j / d m m J k X J I J r 4 7 r f z t r 6 x u b W d m G n u L u 3 f 3 B Y O j p u 6 T h V D J s s F r H q B F S j 4 B K b h h u B n U Q h j Q K B 7 W B 8 N / P b T 6 g 0 j + W D m S T o R 3 Q o e c g Z N V Z q e P 1 S 2 a 2 4 c 5 B V 4 u W k D D n q / d J X b x C z N E J p m K B a d z 0 3 M X 5 G l e F M 4 L T Y S z U m l I 3 p E L u W S h q h 9 r P 5 o V N y b p U B C W N l S x o y V 3 9 P Z D T S e h I F t j O i Z q S X v Z n 4 n 9 d N T X j j Z 1 w m q U H J F o v C V B A T k 9 n X Z M A V M i M m l l C m u L 2 V s B F V l B m b T d G G 4 C 2 / v E p a l x W v W q k 2 r s q 1 2 z y O A p z C G V y A B 9 d Q g 3 u o Q x M Y I D z D K 7 w 5 j 8 6 L 8 + 5 8 L F r X n H z m B P 7 A + f w B f i + M w A = = < / l a t e x i t > 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " R I + 4 e g 4 8 b K n n h d / 1 9 8 r G N d U V O N c = " > A A A B 6 3 i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R b B U 9 k V W z 0 W v X i s Y D + g X U s 2 z b a h S X Z J s k J Z + h e 8 e F D E q 3 / I m / / G b L s H b X 0 w 8 H h v h p l 5 Q c y Z N q 7 7 7 R T W 1 j c 2 t 4 r b p Z 3 d v f 2 D 8 u F R W 0 e J I r R F I h 6 p b o A 1 5 U z S l m G G 0 2 6 s K B Y B p 5 1 g c p v 5 n S e q N I v k g 5 n G 1 B d 4 J F n I C D a Z 5 L m P t U G 5 4 l b d O d A q 8 X J S g R z N Q f m r P 4 x I I q g 0 h G O t e 5 4 b G z / F y j D C 6 a z U T z S N M Z n g E e 1 Z K r G g 2 k / n t 8 7 Q m V W G K I y U L W n Q X P 0 9 k W K h 9 V Q E t l N g M 9 b L X i b + 5 / U S E 1 7 7 K Z N x Y q g k i 0 V h w p G J U P Y 4 G j J F i e F T S z B R z N 6 K y B g r T I y N p 2 R D 8 J Z f X i X t i 6 p X r 9 b v L y u N m z y O I p z A K Z y D B 1 f Q g D t o Q g s I j O E Z X u H N E c 6 L 8 + 5 8 L F o L T j 5 z D H / g f P 4 A F d y N o Q = = < / l a t e x i t > 10 5 < l a t e x i t s h a 1 _ b a s e 6 4 = " 5 D E 3 + M a X n 9 W J V E J h n f s u h g k m w S Q = " > A A A B 7 X i c d V D L S g M x F M 3 U V 6 2 v q k s 3 w S I I w p A p t e 1 G K L p x W c E + o B 1 K J s 2 0 s Z l k S D L C U P o P b l w o 4 t b / c e f f m L Y j q O i B C 4 d z 7 u X e e 4 K Y M 2 0 Q + n B y K 6 t r 6 x v 5 z c L W 9 s 7 u X n H / o K 1 l o g h t E c m l 6 g Z Y U 8 4 E b R l m O O 3 G i u I o 4 L Q T T K 7 m f u e e K s 2 k u D V p T P 0 I j w Q L G c H G S u 0 U X s A z b 1 A s I f c c I a + C I H L R A p b U 6 j W E y t D L l B L I 0 B w U 3 / t D S Z K I C k M 4 1 r r n o d j 4 U 6 w M I 5 z O C v 1 E 0 x i T C R 7 R n q U C R 1 T 7 0 8 W 1 M 3 h i l S E M p b I l D F y o 3 y e m O N I 6 j Q L b G W E z 1 r + 9 u f i X 1 0 t M W P e n T M S J o Y I s F 4 U J h 0 b C + e t w y B Q l h q e W Y K K Y v R W S M V a Y G B t Q w Y b w 9 S n 8 n 7 T L r l d 1 q z e V U u M y i y M P j s A x O A U e q I E G u A Z N 0 A I E 3 I E H 8 A S e H e k 8 O i / O 6 7 I 1 5 2 Q z h + A H n L d P I c C O N Q = = < / l a t e x i t > y = +1 < l a t e x i t s h a 1 _ b a s e 6 4 = " t B I M Z 5 v q 7 h U D q n u P M I S z b 8 O n G 8 4 = " > A A A B 7 X i c d V D L S g M x F M 3 U V 6 2 v q k s 3 w S K 4 c c i U 2 n Y j F N 2 4 r G A f 0 A 4 l k 2 b a 2 E w y J B l h Train losses (Log log scale)K P 0 H N y 4 U c e v / u P N v T N s R V P T A h c M 5 9 3 L v P U H M m T Y I f T i 5 l d W 1 9 Y 3 8 Z m F r e 2 d 3 r 7 h / 0 N Y y U Y S 2 i O R S d Q O s K W e C t g w z n H Z j R X E U c N o J J l d z v 3 N P l W Z S 3 J o 0 p n 6 E R 4 K F j G B j p X Y K L + C Z N y i W k H u O k F d B E L l o A U t q 9 R p C Z e h l S g l k a A 6 K 7 / 2 h J E l E h S E c a 9 3 z U G z 8 K V a G E U 5 n h X 6 i a Y z J B I 9 o z 1 K B I 6 r 9 6 e L a G T y x y h C G U t k S B i 7 U 7 x N T H G m d R o H t j L A Z 6 9 / e X P z L 6 y U m r P t T J u L E U E G W i 8 K E Q y P h / H U 4 Z I o S w 1 N L M F H M 3 g r J G C t M j A 2 o Y E P 4 + h T + T 9 p l 1 6 u 6 1 Z t K q X G Z x Z E H R + A Y n A I P 1 E A D X I M m a A E C 7 s A D e A L P j n Q e n R f n d d m a c 7 K Z Q / A D z t s n J M q O N w = = < / l a t e x i t > y = 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 z h 0 d h K W 3 k t x e B 5 n 9 Q e + x t g h E k I = " > A A A C C X i c d V B N S 8 N A E N 3 U r 1 q / q h 6 9 L B b B U 0 n T 2 u p N V N B j B a t C E 8 t m u 9 G l m 0 3 Y n Q g h 5 O r F v + L F g y J e / Q f e / D d u t I K K P h h 4 v D f D z D w / F l y D b b 9 Z p Y n J q e m Z 8 m x l b n 5 h c a m 6 v H K q o 0 R R 1 q O R i N S 5 T z Q T X L I e c B D s P F a M h L 5 g Z / 5 o v / D P r p n S P J I n k M b M C 8 m l 5 A G n B I w 0 q G L X J y p z f Q Y k H 7 h c B p B e Z G 5 I 4 E q F 2 e F B n g + q N b u + s 9 1 2 t h x s 1 2 2 7 4 z T b B X E 6 L a e J G 0 Y p U E N j d A f V V 3 c Y 0 S R k E q g g W v c b d g x e R h R w K l h e c R P N Y k J H 5 J L 1 D Z U k Z N r L P j 7 J 8 Y Z R h j i I l C k J + E P 9 P p G R U O s 0 9 E 1 n c a P + 7 R X i X 1 4 / g W D b y 7 i M E 2 C S f i 4 K E o E h w k U s e M g V o y B S Q w h V 3 N y K 6 R V R h I I J r 2 J C + P o U / 0 9 O n X q j X W 8 f t 2 q 7 e + M 4 y m g N r a N N 1 E A d t I u O U B f 1 E E U 3 6 A 4 9 o E f r 1 r q 3 n q z n z 9 a S N Z 5 Z R T 9 g v b w D Q k 2 b X g = = < / l a t e x i t > ¯ GD 1 Limiting directions -max-margins < l a t e x i t s h a 1 _ b a s e 6 4 = " 3 3 N r M E n s / w + V U t B x t m K 3 5 F M l I G 0 = " > A A A B 8 n i c b V B N S 8 N A E N 3 U r 1 q / q h 6 9 L B b B U 0 l E q s e C B z 1 W s B + Q h L L Z b t q l m 9 2 w O x F C 6 M / w 4 k E R r / 4 a b / 4 b t 2 0 O W n 0 w 8 H h v h p l 5 U S q 4 A d f 9 c i p r 6 x u b W 9 X t 2 s 7 u 3 v 5 B / f C o Z 1 S m K e t S J Z Q e R M Q w w S X r A g f B B q l m J I k E 6 0 f T m 7 n f f 2 T a c C U f I E 9 Z m J C x 5 D G n B K z k B + m E D w M u Y 8 i H 9 Y b b d B f A f 4 l X k g Y q 0 R n W P 4 O R o l n C J F B B j P E 9 N 4 W w I B o 4 F W x W C z L D U k K n Z M x 8 S y V J m A m L x c k z f G a V E Y 6 V t i U B L 9 S f E w V J j M m T y H Y m B C Z m 1 Z u L / 3 l + B v F 1 W H C Z Z s A k X S 6 K M 4 F B 4 f n / e M Q 1 o y B y S w j V 3 N 6 K 6 Y R o Q s G m V L M h e K s v / y W 9 i 6 b X a r b u L x v t 2 z K O K j p B p + g c e e g K t d E d 6 q A u o k i h J / S C X h 1 w n p 0 3 5 3 3 Z W n H K m W P 0 C 8 7 H N 5 I J k X o = < / l a t e x i t > 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " F c x D 8 z C C v t C L P 0 p E T F 2 I W M 0 O U F w = " > A A A B 6 H i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K o l I 9 V j w o M c W 7 A e 0 o W y 2 m 3 b t Z h N 2 J 0 I J / Q V e P C j i 1 Z / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k E h h 0 H W / n b X 1 j c 2 t 7 c J O c X d v / + C w d H T c M n G q G W + y W M a 6 E 1 D D p V C 8 i Q I l 7 y S a 0 y i Q v B 2 M b 2 d + + 4 l r I 2 L 1 g J O E + x E d K h E K R t F K D e y X y m 7 F n Y O s E i 8 n Z c h R 7 5 e + e o O Y p R F X y C Q 1 p u u 5 C f o Z 1 S i Y 5 N N i L z U 8 o W x M h 7 x r q a I R N 3 4 2 P 3 R K z q 0 y I G G s b S k k c / X 3 R E Y j Y y Z R Y D s j i i O z 7 M 3 E / 7 x u i u G N n w m V p M g V W y w K U 0 k w J r O v y U B o z l B O L K F M C 3 s r Y S O q K U O b T d G G 4 C 2 / v E p a l x W v W q k 2 r s q 1 u z y O A p z C G V y A B 9 d Q g 3 u o Q x M Y c H i G V 3 h z H p 0 X 5 9 3 5 W L S u O f n M C f y B 8 / k D 5 T y N C A = = < / l a t e x i t > t < l a t e x i t s h a 1 _ b a s e 6 4 = " 5 l q c 1 e + b t r 2 Z w G J W q 8 M G Z c b K F N Q = " > A A A C H n i c d V B N a x s x F N Q 6 a Z u 6 T e u k x 1 5 E T a E n s 1 7 b a / d m k k J 6 T K D + A K + 7 a G W t L a K V h P S 2 Y B b / k l z y V 3 L p o S E E e m r / T b S 2 A 2 1 I B g T D z H v o z S R a c A u + / 9 e r 7 O w + e / 5 i 7 2 X 1 1 e v 9 N 2 9 r B 4 d D q 3 J D 2 Y A q o c w 4 I Z Y J L t k A O A g 2 1 o a R L B F s l J w f l / 7 o B z O W K / k N l p p N M z K X P O W U g J P i W i f S C x 5 H X K a w / F 5 E G Y G F y Y q T L 6 s V j r R R G h S O h s w A j u h M w Y b H Q V y r + 4 3 P v T D o B N h v + H 4 3 a I U l C b r t o I W b T i l R R 1 u c x r X f 0 U z R P G M S q C D W T p q + h m l B D H A q 2 K o a 5 Z Z p Q s / J n E 0 c l S R j d l q s 4 6 3 w R 6 f M c K q M e x L w W v 1 3 o y C Z t c s s c Z P l / f a h V 4 q P e Z M c 0 t 6 0 4 F L n w C T d f J T m A r v Q Z V d 4 x g 2 j I J a O E G q 4 u x X T B T G E g m u 0 6 k q 4 T 4 q f J s O g 0 Q w b 4 V m 7 3 j / a 1 r G H 3 q M P 6 B N q o i 7 q o 6 / o F A 0 Q R R f o C v 1 C 1 9 6 l 9 9 O 7 8 W 4 3 o x V v u / M O / Q f v z x 2 K s a N d < / l a t e x i t > GD 1 / k • k 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " W b U p o 2 / I y 5 a k X 4 f 4 5 J R E j P W Y h o w = " > A A A B 7 n i c d V D L S g N B E O y N r x h f U Y 9 e B o P g a Z k N M c k x 6 M V j B P O A Z F l m J 7 P J k N k H M 7 P i E v I R X j w o 4 t X v 8 e b f O E l W U N G C h q K q m + 4 u P x F c a Y w / r M L a + s b m V n G 7 t L O 7 t 3 9 Q P j z q q j i V l H V o L G L Z 9 4 l i g k e s o 7 k W r J 9 I R k J f s J 4 / v V r 4 v T s m F Y + j W 5 0 l z A 3 J O O I B p 0 Q b q Z d 5 H N 1 7 3 C t X s H 2 B s V P D C N t 4 C U M a z Q b G V e T k S g V y t L 3 y + 3 A U 0 z R k k a a C K D V w c K L d G Z G a U 8 H m p W G q W E L o l I z Z w N C I h E y 5 s + W 5 c 3 R m l B E K Y m k q 0 m i p f p + Y k V C p L P R N Z 0 j 0 R P 3 2 F u J f 3 i D V Q d O d 8 S h J N Y v o a l G Q C q R j t P g d j b h k V I v M E E I l N 7 c i O i G S U G 0 S K p k Q v j 5 F / 5 N u 1 X b q d v 2 m V m l d 5 n E U 4 Q R O 4 R w c a E A L r q E N H a A w h Q d 4 g m c r s R 6 t F + t 1 1 V q w 8 p l j + A H r 7 R N G j Y + O < / l a t e x i t > y i x i < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 l x 2 2 E b j G 4 j u K 2 x K p Y S M + m x J W r o = " > A A A B 7 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 s S Q i 1 W P R i 8 c K 9 g P a W D b b S b t 0 s w m 7 G 6 G E / g g v H h T x 6 u / x 5 r 9 x 2 + a g r Q 8 G H u / N M D M v S A T X x n W / n Z X V t f W N z c J W c X t n d 2 + / d H D Y 1 H G q G D Z Y L G L V D q h G w S U 2 D D c C 2 4 l C G g U C W 8 H o d u q 3 n l B p H s s H M 0 7 Q j + h A 8 p A z a q z U 8 t z H 7 L w 6 6 Z X K b s W d g S w T L y d l y F H v l b 6 6 / Z i l E U r D B N W 6 4 7 m J 8 T O q D G c C J 8 V u q j G h b E Q H 2 L F U 0 g i 1 n 8 3 O n Z B T q / R J G C t b 0 p C Z + n s i o 5 H W 4 y i w n R E 1 Q 7 3 o T c X / v E 5 q w m s / 4 z J J D U o 2 X x S m g p i Y T H 8 n f a 6 Q G T G 2 h D L F 7 a 2 E D a m i z N i E i j Y E b / H l Z d K 8 q H j V S vMirror descent with:< l a t e x i t s h a 1 _ b a s e 6 4 = " 5 g 1 w sU W N q q B M Z j p E g 2 K 8 z X T t p l M = " > A A A C J 3 i c d V D L S g M x F M 3 4 r P V V d e k m W I Q W p M w M U t u F U t S F G 6 G C f U C n D p k 0 b U O T m S H J C G W Y v 3 H j r 7 g R V E S X / o m Z t o K K H g g c z r m X m 3 O 8 k F G p T P P d m J t f W F x a z q x k V 9 f W N z Z z W 9 t N G U Q C k w Y O W C D a H p K E U Z 8 0 F F W M t E N B E P c Y a X m j s 9 R v 3 R I h a e B f q 3 F I u h w N f N q n G C k t u b k T J x z S m 9 j h S A 0 F j y / P E 9 d K C o 5 H F C r C Y + j I i L s x 1 S y 2 D u w k g Q 4 O 5 H D q u 7 Q I 3 V z e L J k a 5 T J M i V U x L U 2 q 1 Y p t V 6 E 1 s U w z D 2 a o u 7 k n p x f g i B N f Y Y a k 7 F h m q L o x E o p i R p K s E 0 k S I j x C A 9 L R 1 E e c y G 4 8 y Z n A f a 3 0 Y D 8 Q + v k K T t T v G z H i U o 6 5 p y f T P P K 3 l 4 p / e Z 1 I 9 S v d m P p h p I i P p 4 f 6 E Y M q g G l p s E c F w Y q N N U F Y U P 1 X i I d I I K x 0 t V l d w l d S + D 9 p 2 i W r X C p f H e Z r p 7 M 6 M m A X 7 I E C s M A R q I E L U A c N g M E d e A D P 4 M W 4 N x 6 N V + N t O j p n z H Z 2 w A 8 Y H 5 8 w M K T l < / l a t e x i t > MD1 ( ) = X i=1,2 cosh( i)< l a t e x i t s h a 1 _ b a s e 6 4 = " s q N F 4 wS k + W 1 J h D l J A D Y 6 + T L 8 k G 4 = " > A A A C G n i c d V D L S g M x F M 3 4 t r 6 q L t 0 E i 6 C b M j N q q w u h q K D L C r Y K n V o y 6 a 0 N Z h 4 k d 4 Q y 9 D v c + C t u X C j i T t z 4 N 2 b a C i p 6 I H B y z r 0 k 5 / i x F B p t + 8 M a G 5 + Y n J q e m c 3 N z S 8 s L u W X V + o 6 S h S H G o 9 k p C 5 9 p k G K E G o o U M J l r I A F v o Q L / + Y o 8 y 9 u Q W k R h e f Y i 6 E Z s O t Q d A R n a K R W 3 v H i r r h K v Y B h V w X p y X G / v + n 5 g G y L H l C v D g r p 4 D r k L f f K b e U L d n F / r + T u u t Q u 2 n b Z 3 S 5 l x C 3 v u N v U M U q G A h m h 2 s q / e e 2 I J w G E y C X T u u H Y M T Z T p l B w C f 2 c l 2 i I G b 9 h 1 9 A w N G Q B 6 G Y 6 i N a n G 0 Z p 0 0 6 k z A m R D t T v G y k L t O 4 F v p n M I u j f X i b + 5 T U S 7 O w 1 U x H G C U L I h w 9 1 E k k x o l l P t C 0 U c J Q 9 Q x h X w v y V 8 i 5 T j K N p M 2 d K + E p K / y d 1 t + i U i q W z n U L l c F T H D F k j 6 2 S T O K R M K u S U V E m N c H J H H s g T e b b u r U f r x X o d j o 5 Z o 5 1 V 8 g P W + y c y I 6 B Y < / l a t e x i t > GD ( ) = k k 2 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 y N g f S O 0 z 3 R g S 7 X U 6 0 / v V 5 c i p R c = " > A A A C U X i c d V F B a x N B F H 5 Z q 9 Z U b d S j l 0 e D 0 K K G 2 T R N 6 q F Q W g + 9 F C q Y t p B N l 9 n J p D t 0 Z n a d m R X C s n / R g 5 7 8 H 7 1 4 s D i b b k F F H w x 8f N / 7 e O 9 9 k + R S W E f I 9 1 Z w b + X + g 4 e r j 9 p r j 5 8 8 X e 8 8 e 3 5 q s 8 I w P m a Z z M x 5 Q i 2 X Q v O x E 0 7 y 8 9 x w q h L J z 5 K r w 1 o / + 8 y N F Z n + 6 B Y 5 n y p 6 q cV c M O o 8 F X f S K E / F R R k p 6 l K j y u P 3 V d y v N q O E O 7 q F 7 T 2 M b K H i U u A e l u G b f l X h U o o F 3 j m o Y V b o t P H E Y g v f e t M n 4 8 q G u O j j a w y r u N M l P b I z G o U E S W + w / W 5 7 d + g B I T u D E c H Q g 7 q 6 0 N R J 3 P k a z T J W K K 4 d k 9 T a S U h y N / X z n G C S V + 2 o s D y n 7 I p e 8 o m H m i p u p + U y k Q p f e W a G 8 8 z 4 p x 0 u 2 d 8 d J V X W L l T i O + s 7 7 N 9 a T f 5 L m x R u v j s t h c 4 L x z W 7 H T Q v J L o M 6 3 h x J g x n T i 4 8 o M w I v y u y l B r K n P + E t g / h 7 l L 8 P z j t 9 8 J h b / h h 0 N 0 / a O J Y h Z e w A Z s Q w g j 2 4 Q h O Y A w M v s A 1 / I S b 1 r f W j w C C 4 L Y 1 a D W e F / B H B W u / A K i p s p I = < / l a t e x i t > MD2 ( ) = X i=1,2 iarcsinh( i) q 2 i + 1< l a t e x i t s h a 1 _ b a s e 6 4 = " 2 A 7 h 5 l w s 9 k 2 b 0 W h i x 9 M w 3 v a 8 I 7 g= " > A A A C A X i c d V B N S 0 J B F J 1 n X 2 Z f V p u g z Z A E t p H n 0 9 R 2 U k E t W h h k C m o y b 5 y n g / M + m L k v k I d t + i t t W h T R t n / R r n / T P D W o q A M X D u f c y 7 3 3 2 I H g C k z z w 0 j M z S 8 s L i W X U y u r a + s b 6 c 2 t a + W H k r I 6 9 Y U v m z Z R T H C P 1 Y G D Y M 1 A M u L a g j X s 4 U n s N 2 6 Z V N z 3 r m A U s I 5 L + h 5 3 O C W g p W 5 6 5 y L b t h m Q L t x E b Z f A Q L r R 2 e l 4 f N B N Z 8 z c U a V k H V r Y z J l m 2 S q U Y m K V i 1 Y B 5 7 U S I 4 N m q H X T 7 + 2 e T 0 O X e U A F U a q V N w P o R E Q C p 4 K N U + 1 Q s Y D Q I e m z l q Y e c Z n q R J M P x n h f K z 3 s + F K X B 3 i i f p + I i K v U y L V 1 Z 3 y k + u 3 F 4 l 9 e K w S n 0 o m 4 F 4 T A P D p d 5 I Q C g 4 / j O H C P S 0 Z B j D Q h V H J 9 K 6 Y D I g k F H V p K h / D 1 K f 6 f X F u 5 f C l X u i x m q s e z O J J o F + 2 h L M q j M q q i c 1 R D d U T R H X p A T + j Z u D c e j R f j d d q a M G Y z 2 + g H j L d P p / q X E A = = < / l a t e x i t > L( GD t )< l a t e x i t s h a 1 _ b a s e 6 4 = " w 3 BV A Y K 2 / O s j f 9 x Y h U K 2 u 4 e E C 5 0 = " > A A A C A 3 i c d V D L S g N B E J z 1 G e M r 6 k 0 v g 0 G I l 7 A b J C a 3 o B 4 8 K E Q w D 8 j G Z X Y y S Y b M P p j p F c K y 4 M V f 8 e J B E a / + h D f / x t k k g o o W N B R V 3 X R 3 u a H g C k z z w 5 i b X 1 h c W s 6 s Z F f X 1 j c 2 c 1 v b T R V E k r I G D U Q g 2 y 5 R T H C f N Y C D Y O 1 Q M u K 5 gr X c 0 W n q t 2 6 Z V D z w r 2 E c s q 5 H B j 7 v c 0 p A S 0 5 u 9 6 J g u w y I A z e x 7 R E Y S i + + P E s c K z l 0 c n m z a G q U y z g l V s W 0 N K l W K 6 V S F V s T y z T z a I a 6 k 3 u 3 e w G N P O Y D F U S p j m W G 0 I 2 J B E 4 F S 7 J 2 p F h I 6 I g M W E d T n 3 h M d e P J D w k + 0 E o P 9 w O p y w c 8 U b 9 P x M R T a u y 5 u j M 9 U / 3 2 U v E v r x N B v 9 K N u R 9 G w H w 6 X d S P B I Y A p 4 H g H p e M g h h r Q q j k + l Z M h 0 Q S C j q 2 r A 7 h 6 1 P 8 P 2 m W i l a 5 W L 4 6 y t d O Z n F k 0 B 7 a R w V k o W N U Q + e o j h q I o j v 0 g J 7 Q s 3 F v P B o v x u u 0 d c 6 Y z e y g H z D e P g H c x J e z < / l a t e x i t > L( MD1 t )< l a t e x i t s h a 1 _ b a s e 6 4 = " 7 O S w 2 N 8 9 X o 6 P 5 Z D w P hV Z + 1 x Z q g k = " > A A A C A 3 i c d V D L S g N B E J z 1 G e M r 6 k 0 v g 0 H Q S 5 g 1 M d F b U A 8 e F C I Y D S R x m Z 3 M x i G z D 2 Z 6 h b A E v P g r X j w o 4 t W f 8 O b f O J t E U N G C h q K q m + 4 u N 5 J C A y E f 1 s T k 1 P T M b G Y u O 7 + w u L S c W 1 m 9 1 G G s G K + z U I a q 4 V L N p Q h 4 H Q R I 3 o g U p 7 4 r + Z X b O 0 r 9 q 1 u u t A i D C + h H v O 3 T b i A 8 w S g Y y c m t n 2 6 3 X A 7 U g e u k 5 V O 4 U X 5 y d j x w d g c 7 T i 5 P C m S v U r E J J o V S 8 a C 4 X z a E k L 1 S h W D b k B R 5 N E b N y b 2 3 O i G L f R 4 A k 1 T r p k 0 i a C d U g W C S D 7 K t W P O I s h 7 t 8 q a h A f W 5 b i f D H w Z 4 y y g d 7 I X K V A B 4 q H 6 f S K i v d d 9 3 T W d 6 p v 7 t p e J f X j M G b 7 + d i C C K g Q d s t M i L J Y Y Q p 4 H g j l C c g e w b Q p k S 5 l b M b q i i D E x s W R P C 1 6 f 4 f 3 K 5 W 7 D L h f J 5 K V 8 9 H M e R Q R t o E 2 0 j G 1 V Q F Z 2 g G q o jh u 7 Q A 3 p C z 9 a 9 9 W i 9 W K + j 1 g l r P L O G f s B 6 + w T q + J e 8 < / l a t e x i t >L( MD2 t ) < l a t e x i t s h a 1 _ b a s e 6 4 = " Q r s 5 K 0 C v B j C Q U Z R O P 4 M W X / n N w w g = " > A A A C C 3 i c d V B N S 8 N A E N 3 4 b f 2 q e v S y t A i e y r b W R m + i H r w I C l a F p o b N d q N L N 5 u w O x F K y N 2 L f 8 W L B 0 W 8 + g e 8 + W / c 2 A o q + m D g 8 d 4 M M / O C R A o D h L w 7 Y + M T k 1 P T M 7 O l u f m F x a X y 8 s q Z i V P N e J v F M t Y X A T V c C s X b I E D y i 0 R z G g W S n w f 9 / c I / v + H a i F i d w i D h 3 Y h e K R E K R s F K f r n i B V R n X s C B 5 r 4 n V A i D y 8 y L K F z r K D s 6 y P 1 G 7 p e r p E b c z c Y 2 w a S 2 6 T a 3 G j u W E L J D X B f X L S l Q R S M c + + U 3 r x e z N O I K m K T G d O o k g W 5 G N Q g m e V 7 y U s M T y v r 0 i n c s V T T i p p t 9 / p L j d a v 0 c B h r W w r w p / p 9 I q O R M Y M o s J 3 F l e a 3 V 4 h / e Z 0 U w u 1 u J l S S A l d s u C h M J Y Y Y F 8 H g n t C c g R x Y Q p k W 9 l b M r q m m D G x 8 J R v C 1 6 f 4 f 3 L W q N Vb t d Z J s 7 q 7 N 4 p j B q 2 h C t p A d e S i X X S I j l E b M X S L 7 t E j e n L u n A f n 2 X k Z t o 4 5 o 5 l V 9 A P O 6 w e S m p w O < / l a t e x i t > ¯ MD21 < l a t e x i t s h a 1 _ b a s e 6 4 = " W H Z u / r Q p 6 K 6 v n 8 / c I 6 7 j V q 5 n 1Z o = " > A A A C C 3 i c d V B N S 8 N A E N 3 4 b f 2 q e v S y W A R P J S l S 2 5 u o B y 9 C B a t C E 8 N m u 2 k X N 5 u w O x F C y N 2 L f 8 W L B 0 W 8 + g e 8 + W / c t B V U 9 M H A 4 7 0 Z Z u Y F i e A a b P v D m p q e m Z 2 b X 1 i s L C 2 v r K 5 V 1 z c u d J w q y r o 0 F r G 6 C o h m g k v W B Q 6 C X S W K k S g Q 7 D K 4 O S r 9 y 1 u m N I / l O W Q J 8 y I y k D z k l I C R / O q 2 G x C V u w E D U v g u l y F k 1 7 k b E R i q K D 8 9 L n y n 8 K s 1 u 2 4 b N J u 4 J E 7 L d g x p t 1 u N R h s 7 I 8 u 2 a 2 i C j l 9 9 d / s x T S M m g Q q i d c + x E / B y o o B T w Y q K m 2 q W E H p D B q x n q C Q R 0 1 4 + + q X A O 0 b p 4 z B W p i T g k f p 9 I i e R 1 l k U m M 7 y S v 3 b K 8 W / v F 4 K Y c v L u U x S Y J K O F 4 W p w B D j M h j c 5 4 p R E J k h h C p u b s V 0 S B S h Y O K r m B C + P s X / k 4 t G 3 W n W m 2 d 7 t Y P D S R w L a A t t o 1 3 k o H 1 0 g E 5 Q B 3 U R R X f o A T 2 h Z + v e e r R e r N d x 6 5 Q 1 m d l E P 2 C 9 f Q J + 7 5 w B < / l a t e x i t > ¯ MD1 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " C h s a T O b v Y / H t Z W V z q m n 2 x k m l + 7 s = " > A A A C I H i c d V D L T h s x F P X w K q Q 8 A i z Z W I 0 q d R V 5 w m P I L q I s 2 F Q C q Q l I m X T k c T z E w m N b 9 p 1 K 0 S i f w o Z f 6 a a L I k R 3 7 d f g I U E C B E e y d H T O v b o + J z V S O C D k X z A 3 v 7 C 4 9 G F 5 p f Z x d W 1 9 o 7 6 5 1 X O 6 s I x 3 m Z b a X q T U c S k U 7 4 I A y S + M 5 T R P J T 9 P r 7 5 W / v l P b p 3 Q 6 j u M D R / k 9 F K J T D A K X k r q U W x G I o m F y m D 8 o 4 x z C i O b l 9 + O J 0 l r g m N j t Q G N 4 x 6 3 g G M 2 1 D D l S Z j U G 6 R J o t 3 W I c G k u R v t 7 b f a n h D S J l G E Q 0 8 q N N A M p 0 n 9 b z z U r M i 5 A i a p c / 2 Q G B i U 1 I J g k k 9 q c e G 4 o e y K X v K + p 4 r m 3 A 3 K x 4 A T / N k r Q 5 x p 6 5 8 C / K g + 3 y h p 7 t w 4 T / 1 k l c C 9 9 i r x L a 9 f Q H Y 4 K I U y B X D F p o e y Q m I f u m o L D 4 X l D O T Y E 8 q s 8 H / F b E Q t Z e A 7 r f k S n p L i 9 0 m v 1 Q w P m g d n e 4 3 O 0 a y O Z b S D P q E v K E Q R 6 q A T d I q 6 i K F r 9 A v 9 Q b f B T f A 7 u A v u p 6 N z w W x n G 7 1 A 8 P 8 B 5 I q k D A = = < / l a t e x i t > MD2 1 / k • k 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " G E p T J h 5 k Y 6 m b u J i z V f 7 c P S w C 5 x k = " > A A A C J X i c d V B N a x s x F N Q 6 T e K 6 S b p N j 7 2 I m k J P Z t c E 1 4 Y c T N p D L 4 U E 4 g / w b h e t r L W F t Z K Q 3 h b M s n 8 m l / 6 V X n p o K I W e + l e q t R 1 I Q z o g G G b e 4 2 k m 1 Y J b C I L f X m P v y f 7 B Y f N p 6 9 n R 8 c l z / 8 X p 2 K r C U D a i S i g z T Y l l g k s 2 A g 6 C T b V h J E 8 F m 6 S r 9 7 U / + c K M 5 U p e w 1 q z O C c L y T N O C T g p 8 c 8 j v e R J x G U G 6 8 9 l l B N Y m r z 8 9 K F K w g p H 2 i g N C k d j Z g B H d K 5 g y 3 c L i d 8 O O o F D r 4 d r E v a D 0 J H B o N / t D n C 4 s Y K g j X a 4 T P z b a K 5 o k T M J V B B r Z 2 G g I S 6 J A U 4 F q 1 p R Y Z k m d E U W b O a o J D m z c b l J W e E 3 T p n j T B n 3 J O C N e n + j J L m 1 6 z x 1 k 3 U M + 9 C r x c e 8 W Q F Z P y 6 5 1 A U w S b e H s k J g l 7 y u D M + 5 Y R T E 2 h F C D X d / x X R J D K H g i m 2 5 E u 6 S 4 v + T c b c T 9 j q 9 q 7 P 2 8 G J X R x O 9 Q q / R W x S i d 2 i I P q J L N E I U 3 a B v 6 A e 6 9 b 5 6 3 7 2 f 3 q / t a M P b 7 b x E / 8 D 7 8 x e C p K a G < / l a t e x i t > MD1 1 / k • k 1 Figure 1:Mirror descent is performed using 3 different potentials on the same toy 2d dataset. Left: the losses converge to zero. Center: the iterates converge in direction towards 3 different vectors β∞ , the 3 lines passing through the origin correspond to the associated separating hyperplanes. Right: the limit directions are each proportional to arg min ϕ ∞ ( β) under the constraint min i y i ⟨x i , β⟩ ≥ 1 for their respective ϕ ∞ 's, as predicted by our theory (Theorem 1). The full trajectories are plotted Figure 4 and we refer to Section 5 for more details.For a separable dataset(x i , y i ) i∈[n] ,we study the mirror flow d∇ϕ(β t ) = -∇L(β t )dt with potential ϕ : R d → R and an exponential tailed classification loss L. We prove that β t converges in direction towards the solution of the ϕ ∞ -maximum margin solution where the (asymmetric) norm ϕ ∞ captures the shape of the potential ϕ 'at infinity' (see Figure 2 for an intuitive illustration).Theorem 1 (Main result, Informal). There exists a horizon function ϕ ∞ such that for any separable dataset, the normalised mirror flow iterates βt := β t /∥β t ∥ converge and satisfy:lim t→∞ βt is proportional to arg min mini yi⟨xi, β⟩≥1 ϕ ∞ ( β).Our result holds for a large class of potentials ϕ and recovers previous results obtained for ϕ = ∥ • ∥ p p [Sun et al., 2022] and for L-homogeneous potentials [Sun et 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 ϕ ∞ . 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 ϕ ∞ is then simply the asymmetric norm which has S ∞ as its unit ball (see Figure 3 for an illustration). In addition, when the function ϕ is 'separable' and can be written ϕ(β) = i φ(β i ) for a real valued function φ, then a very simple and explicit formula enables to calculate ϕ ∞ (Theorem 3).The paper is organised as follows. The classification setting as well as the assumptions on the loss and the potential are provided in Section 2. 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.We first outline the motivations for understanding the implicit regularization of mirror descent and discuss related works that contextualize our contribution within the machine learning context.Relevance of studying mirror descent in the context of machine learning. Though mirror descent is not per se an algorithm used by machine learning practitioners, it proves to be a very useful tool for theoreticians in the field. Indeed, when analysing gradient descent (and its stochastic and accelerated variants) on neural-network architectures, an underlying mirror-descent structure very recurrently emerges. Then, results for mirror descent enable to prove convergence as well as 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 et 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-saddle 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 ReLU networks [Chizat and Bach, 2020] . Building on these examples, Li et 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] .Gradient descent in classification. Numerous works have studied gradient descent in the classification setting. For linear parametrisations, separable data and exponentially tailed losses, Soudry et al. [2018] prove that GD converges in direction towards the ℓ 2 -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 ℓ 2 -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 ℓ 2 -max margin problem. A weaker version of this result was previously obtained by Nacson et al. [2019a] . Furthermore, convergence results for linear networks are 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.We provide here a few notations which will be useful throughout the paper. We let [n] be the integers from 1 to n. We denote by Z ∈ R n×d the feature matrix whose i th line corresponds to the vector y i x i . When not specified, ∥ • ∥ corresponds to any (definable) norm on R d . For a convex function h, ∂h(β) denotes its subdifferential at β: ∂h(β) = {g ∈ R d : h(β ′ ) ≥ h(β) + ⟨g, β ′ -β⟩, ∀β ′ ∈ R d }.For any scalar function f : R → R and vector u ∈ R p , the vector f (u) ∈ R p corresponds to the component-wise application of f over u. We denote by σ : R n → R n the softmax function equal toσ(z) = exp(z)/ n i=1 exp(z i ) ∈ ∆ n where ∆ n is the unit simplex. For a convex potential ϕ, we denote D ϕ (β, β 0 ) the Bregman divergence equal to ϕ(β) -(ϕ(β 0 ) + ⟨∇ϕ(β 0 ), β -β 0 ⟩) ≥ 0. 
problem set-up: 
 We consider a dataset (x i , y i ) 1≤i≤n with points x i ∈ R d and binary labels y i ∈ {-1, 1}. We choose a loss function ℓ : R → R and seek to minimise the empirical riskL(β) = n i=1 ℓ(y i ⟨x i , β⟩).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 a generalisation of gradient descent to non-Euclidean geometries induced by a given convex potential function ϕ : R d → R. The method generates a sequence ( βk ) k≥0 with β0 = β 0 ∈ R d and ∇ϕ( βk+1 ) = ∇ϕ( βk ) -γ∇L( βk ).When the step size γ goes to 0, the mirror descent iterates approach the solution (β t ) t≥0 to the following differential equation:d∇ϕ(β t ) = -∇L(β t )dt, (MF)initialised at β 0 . 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 ϕ.Assumption 1. The loss ℓ satisfies:1. ℓ is convex, twice continuously differentiable, decreasing and lim z→+∞ ℓ(z) = 0.2. ℓ has an exponential tail, in the sense that ℓ(z)∼ z→∞ -ℓ ′ (z) ∼ z→∞ exp(-z).The first part of the assumptions is very general and ensures that the empirical loss L can be minimised 'at infinity'. The exponential tail is crucial: it enables to identify a unique maximum margin solution towards which the iterates converge in direction, independently of the considered loss. Both the exponential ℓ(z) = exp(-z) and the logistic loss ℓ(z) = ln(1 + exp(-z)) 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 et al., 2018 , Nacson et al., 2019b , Ji et al., 2020 , Ji and Telgarsky, 2021 , Chizat and Bach, 2020] .Assumption 2. The potential ϕ : R d → R satisfies:1. ϕ is twice continuously differentiable, strictly convex and coercive.c ∈ R ≥0 and β 2 ∈ R d , the sub-level set {β 1 ∈ R d , D ϕ (β 2 , β 1 ) ≤ c} is bounded. 3. ∇ 2 ϕ(β) is positive-definite for all β ∈ R d .4. ∇ϕ diverges at infinity:lim ∥β∥→∞ ∥∇ϕ(β)∥ = +∞.The first two points of the assumption are commonly used to ensure well-posedness of mirror descent [Bauschke et al., 2017] . The third one is necessary in continuous time to ensure the existence and uniqueness over R ≥0 of a solution to the (MF) differential equation (in particular, we want to avoid the solution "blowing up in 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, we assume that the dataset is linearly separable.Assumption 3. There existsβ ⋆ ∈ R d such that y i ⟨β ⋆ , x i ⟩ > 0 for every i ∈ [n].Notice that such β ⋆ 's correspond to minimisation directions: L(λβ ⋆ ) λ→∞ -→ 0. Under the three previous assumptions, we can show that the mirror flow iterates (β t ) t≥0 minimise the loss while diverging to infinity.Proposition 1. Considering the mirror flow (β t ) t≥0 , the loss converges towards 0 and the iterates diverge:lim t→∞ L(β t ) = 0 and lim t→∞ ∥β t ∥ = +∞.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 to the main question addressed in this paper: Among all minimising directions β ⋆ , towards which does the mirror flow converge?We initially offer a heuristic and intuitive answer to this question, setting the stage for the formal construction of the implicit regularisation problem. 
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 ℓ(z) = exp(-z). The mirror flow then writesd dt ∇ϕ(β t ) = L(β t ) • Z T q(β t ),with q(β t ) = σ(-Zβ t ), where σ is the softmax function and Z the matrix with rows (y i x i ) i∈ [n] . Note that q(β t ) belongs to the unit simplex ∆ n .We simplify the differential equation by performing a time rescaling, which does not change the asymptotical behaviour. As θ : t → t 0 L(β s )ds is a bijection in R ≥0 (see Lemma 4), we can speed up time and consider the accelerated iterates βt = β θ -1 (t) . 1 By the chain rule, we haved dt ∇ϕ( βt ) = Z ⊤ q( βt ),and thereforeEQUATIONFrom now on, we drop the tilde notation and assume that a change of time scale has been done. We want to characterise the directional limit of the diverging iterates β t . To do so, we study their normalisation βt := βt ∥βt∥ . As they form a bounded sequence, and q(β t ) ∈ ∆ n is also bounded, we can extract a subsequence2 ( βts , q(β ts )) s∈N , with lim s→∞ t s = ∞ converging to some limit ( β∞ , q ∞ ). By the Césaro average property, 1 ts ts 0 q(β s )ds also converges towards q ∞ . Equation (1) then yieldsEQUATIONObserve that q(β t ) = σ(-Zβ t ) and the softmax function σ approaches the argmax operator at infinity. Hence, as β t diverges, we expect that q(β t ) k → 0 for coordinates k for which (-Zβ t ) k is not maximal, i.e. (Zβ t ) k not minimal. This observation is made formal in the following lemma. Its proof is straightforward and is given in Appendix A.Lemma 1. Assume that ( βts , q(β ts ))s→∞ -→ ( β∞ , q ∞ ). It holds that:(q ∞ ) k = 0 if y k ⟨x k , β∞ ⟩ > min 1≤i≤n y i ⟨x i , β∞ ⟩.In words, coordinates of q ∞ which do not correspond to support vectors of β∞ must be zero. Our goal is now to uniquely characterise β∞ as the solution of a maximum margin problem.As a warm-up, let us consider standard gradient flow, which corresponds to mirror flow with potential ϕ = ∥ • ∥ 2 2 /2. In this case, Equation (2) becomes β ts /t s → Z ⊤ q ∞ . Since the normalised iterates satisfy βts → β∞ , we getβ∞ = Z ⊤ q ∞ ∥Z ⊤ q ∞ ∥ 2 .Now notice that this equation along with the slackness conditions from Lemma 1 exactly correspond to the optimality conditions of the following convex minimisation problem:EQUATION< l a t e x i t s h a 1 _ b a s e 6 4 = " m c 2 5 p I q j X t M Z b W l 6 y 4 F t t C H z h Z o = " > A A A C A H i c d V C 7 S g N B F J 3 1 G e N r 1 c L C Z j A I S R N 2 g u Z R C E E b y w j m A d k 1 z E 5 m k y G z D 2 Z m h b B s 4 6 / Y W C h i 6 2 f Y + T d O k h V U 9 M C FV k Y 3 K h p R B 0 f j w L m M Y K V l g b m o R 2 N 2 W 1 S R K W 0 a L t U 4 R I 8 h 8 i y B m b B K l t z Q E 2 Q V T u r a N J o 1 F G j D l F m F U C G 1 s B 8 t 4 c h i X 0 a K M K x l H 1 k R c p J s F C M c J r m 7 V j S C J M J H t G + p g H 2 q X S S + Q M p P N H K E H q h 0 B U o O F e / T y T Y l 3 L q u 7 r T x 2 o s f 3 s z 8 S + v H y u v 7 i Q s i G J F A 7 J Y 5 M U c q h D O 0 o B D J i h R f K o J J o L p W y E Z Y 4 G J 0 p n l d Q h f n 8 L / S a d S R t V y 9 f q 0 0 L z I 4 s i B I 3 A M i g C B G m i C K 9 A C b U B A C h 7 A E 3 g 2 7 o 1 H 4 8 V 4 X b Q u G d n M A f g B 4 + 0 T 0 I e U o w = = < / l a t e x i t > (1) ( ) = < l a t e x i t s h a 1 _ b a s e 6 4 = " q I S b H S C u g K V L D Y t d i l 8 9 T s J u J E U = " > A A A B / 3 i c d V D L S s N A F J 3 U V 6 2 v q O D G z W A R 2 k 1 I 1 N Z m I R T d u K x g H 9 D E M p l O 2 q G T B z M T o c Q u / B U 3 L h R x 6 2 + 4 8 2 + c t h F U 9 M C F w z n 3 c u 8 9 X s y o k K b 5 o e U W F p e W V / K r h b X 1 j c 0 t f X u n J a K E Y 9 L E E Y t 4 x 0 O C M B q S p q S S k U 7 M C Q o 8 R t r e 6 G L q t 2 8 J F z Q K r + U 4 J m 6 A B i H 1 K U Z S S T 1 9 z 4 m H 9 C Y t W e V J y f G I R G V 4 B i 2 z p x d N w 6 5 V K s c m N A 1 z B k V s 2 7 a q F W h l S h F k a P T 0 d 6 c f 4 S Q g o c Q M C d G 1 z F i 6 K e K S Y k Y m B S c R J E Z 4 h A a k q 2 i I A i L c d H b / B B 4 q p Q / 9 i K s K J Z y p 3 y d S F A g x D j z V G S A 5 F L + 9 q f i X 1 0 2 k X 3 N T G s a J J C G e L / I T B m U E p 2 H A P u U E S z Z W B G F O 1 a 0 Q D x F H W K r I C i q E r 0 / h / 6 R 1 Z F h V o 3 p 1 U q y f Z 3 H k w T 4 4 A C V g g V N Q B 5 e g A Z o A g z v w A J 7 A s 3 a v P W o v 2 u u 8 N a d l M 7 v g B 7 S 3 T 2 v r l H M = < / l a t e x i t >(1) ( ) = < l a t e x i t s h a 1 _ b a s e 6 4 = " U A s + T o X t M w t Z P l s / 3 m G g k q 7 A 9W M = " > A A A B / 3 i c d V D L S s N A F J 3 4 r P U V F d y 4 G S x C u w l J t b V Z C E U 3 L i v Y B z S x T K a T d u j k w c x E K L E L f 8 W N C 0 X c + h v u / B u n b Q Q V P X D h c M 6 9 3 H u P F z M q p G l + a A u L S 8 s r q 7 m 1 / P r G 5 t a 2 v r P b E l H C M W n i i E W 8 4 y F B G A 1 J U 1 L J S C f m B A U e I 2 1 v d D H 1 2 7 e E C x q F 1 3 I c E z d A g 5 D 6 F C O p p J 6 + 7 8 R D e p M W y 6 V J 0 f G I R C V 4 B i 2 z p x d M w 6 5 V K s c m N A 1 z B k V s 2 7 a q F W h l S g F k a P T 0 d 6 c f 4 S Q g o c Q M C d G 1 z F i 6 K e K S Y k Y m e S c R J E Z 4 h A a k q 2 i I A i L c d H b / B B 4 p p Q / 9 i K s K J Z y p 3 y d S F A g x D j z V G S A 5 F L + 9 q f i X 1 0 2 k X 3 N T G s a J J C G e L / I T B m U E p 2 H A P u U E S z Z W B G F O 1 a 0 Q D x F H W K r I 8 i q E r 0 / h / 6 R V N q y q U b 0 6 K d T P s z h y 4 A A c g i K w w C m o g 0 v Q A E 2 A w R 1 4 A E / g W b v X H r U X 7 X X e u q B l M 3 v g B 7 S 3 T 2 1 9 l H Q = < / l a t e x i t >(2) ( ) = 10< l a t e x i t s h a 1 _ b a s e 6 4 = " Y C g 6 Z W q R e j / s U IY O n c r n X H S U u C E = " > A A A B / n i c d V D L S s N A F J 3 4 r P U V F V d u B o v Q b k I S a 9 u N U H T j s o J 9 Q B P L Z D p p h 0 4 e z E y E E g r + i h s X i r j 1 O 9 z 5 N 0 7 a C C p 6 4 M L h n H u 5 9 x 4 v Z l R I 0 / z Q l p Z X V t f W C x v F z a 3 t n V 1 9 b 7 8 j o o R j 0 s Y R i 3 j P Q 4 I w G p K 2 p J K R X s w J C j x G u t 7 k M v O 7 d 4 Q L G o U 3 c h o T N 0 C j k P o U I 6 m k g X 7 o x G N 6 m 5 a t y q z s e E S i C j y H 1 k A v m U a t a p / a Z 9 A 0 z D k y Y t m N e h 1 a u V I C O V o D / d 0 Z R j g J S C g x Q 0 L 0 L T O W b o q 4 p J i R W d F J B I k R n q A R 6 S s a o o A I N 5 2 f P 4 M n S h l C P + K q Q g n n 6 v e J F A V C T A N P d Q Z I j s V v L x P / 8 v q J 9 B t u S s M 4 k S T E i 0 V + w q C M Y J Y F H F J O s G R T R R D m V N 0 K 8 R h x h K V K r K h C + P o U / k 8 6 t m H V j N p 1 t d S 8 y O M o g C N w D M r A A n X Q B F e g B d o A g x Q 8 g C f wr N 1 r j 9 q L 9 r p o X d L y m Q P w A 9 r b J 9 e b l C M = < / l a t e x i t >(1) ( ) = 1< l a t e x i t s h a 1 _ b a s e 6 4 = " 4 3V o R G U c T t S 2 z 1 a f 1 1 s Y C N M R H n 0 = " > A A A B / n i c d V D L S s N A F J 3 4 r P U V F V d u B o v Q b k I S a 9 u N U H T j s o J 9 Q B P L Z D p p h 0 4 e z E y E E g r + i h s X i r j 1 O 9 z 5 N 0 7 a C C p 6 4 M L h n H u 5 9 x 4 v Z l R I 0 / z Q l p Z X V t f W C x v F z a 3 t n V 1 9 b 7 8 j o o R j 0 s Y R i 3 j P Q 4 I w G p K 2 p J K R X s w J C j x G u t 7 k M v O 7 d 4 Q L G o U 3 c h o T N 0 C j k P o U I 6 m k g X 7 o x G N 6 m 5 b t y q z s e E S i C j y H 1 k A v m U a t a p / a Z 9 A 0 z D k y Y t m N e h 1 a u V I C O V o D / d 0 Z R j g J S C g x Q 0 L 0 L T O W b o q 4 p J i R W d F J B I k R n q A R 6 S s a o o A I N 5 2 f P 4 M n S h l C P + K q Q g n n 6 v e J F A V C T A N P d Q Z I j s V v L x P / 8 v q J 9 B t u S s M 4 k S T E i 0 V + w q C M Y J Y F H F J O s G R T R R D m V N 0 K 8 R h x h K V K r K h C + P o U / k 8 6 t m H V j N p 1 t d S 8 y O M o g C N w D M r A A n X Q B F e g B d o A g x Q 8 g C f w r N 1 r j 9 q L 9 r p o X d L y m Q P w A 9 r b J 9 k s l C Q = < / l a t e x i t > (2) ( ) = 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " o c v h 9 K W 6 R C w 0 Q 4 H B Q I C Z 5 4 I / R 8 A = " > A A A C A H i c d V C 7 S g N B F J 3 1 G e N r 1 c L C Z j A I S R N m g + Z R C E E b y w j m A d k 1 z E 5 m k y G z D 2 Z m h b B s 4 6 / Y W C h i 6 2 f Y + T d O k h V U 9 M C F w z n 3 c u 8 9 b s S Z V A h 9 G E v L K 6 t r 6 7 m N / O b W 9 s 6 u u b f f k W E s C G 2 T k I e i 5 2 J J O Q t o W z H F a S 8 S F P s u p 1 1 3 c j n z u 3 d U S B Y G N 2 o a U c f H o 4 B 5 j G C l p Y F 5 a E d j d p s U K 6 W 0 a L t U 4 R I 8 h x Z C A 7 O A y m g O q I m F a m c V T R q N u t W o Q y u z C i B D a 2 C + 2 8 O Q x D 4 N F O F Y y r 6 F I u U k W C h G O E 3 z d i x p h M k E j 2 h f 0 w D 7 V D r J / I E U n m h l C L 1 Q 6 A o U n K v f J x L s S z n 1 X d 3 p Y z W W v 7 2 Z + J f X j 5 V X d x I W R L G i A V k s 8 m I O V Q h n a c A h E 5 Q o P t U E E 8 H 0 r Z C M s c B E 6 c z y O o S v T + H / p F M p W 9 V y 9 f q 0 0 L z I 4 s i B I 3 A M i s A C N d A E V 6 A F 2 o C A F D y A J / B s 3 B u P x o v x u m h d M r K Z A / A D x t s n 0 h q U p A = = < / l a t e x i t >(2) ( ) = 100< l a t e x i t s h a 1 _ b a s e 6 4 = " t A b 0 0 8 M q jEQUATION< l a t e x i t s h a 1 _ b a s e 6 4 = " Y 7 b 0 0 t j 2 Q 5 g P b G e p 8 e R Z W 7 I 4 j c w = " > AEQUATION< l a t e x i t s h a 1 _ b a s e 6 4 = " j Zf V O + l m x G J H D L Y H 9 c w r O F u m 2 0 o = " > A A A B + n i c b V B N S 8 N A E N 3 U r 1 q / U j 1 6 C R a h X k p S p H o s e v F Y w X 5 A G 8 N m u 2 m X b j Z h d 6 K E 2 J / i x Y M i X v 0 l 3 v w 3 b t s c t P X B w O O 9 G W b m + T F n C m z 7 2 y i s r W 9 s b h W 3 S z u 7 e / s H Z v m w o 6 J E E t o m E Y 9 k z 8 e K c i Z o G x h w 2 o s l x a H P a d e f X M / 8 7 g O V i k X i D t K Y u i E e C R Y w g k F L n l k e x G N 2 n 1 X r Z 1 N v w E Q A q W d W 7 J o 9 h 7 V K n J x U U I 6 W Z 3 4 N h h F J Q i q A c K x U 3 7 F j c D M s g R F O p 6 V B o m i M y Q S P a F 9 T g U O q 3 G x + + t Q 6 1 c r Q C i K p S 4 A 1 V 3 9 P Z D h U K g 1 9 3 R l i G K t l b y b + 5 / U T C C 7 d j I k 4 A S r I Y l G Q c A s i a 5 a D N W S S E u C p J p h I p m + 1 y B h L T E C n V d I h O M s v r 5 J O v e Y 0 a o 3 b 8 0 r z K o + j i I 7 R C a o i B 1 2 g J r p B L d R G B D 2 i Z / S K 3 o w n 4 8 V 4 N z 4 W r Q U j n z l C f 2 B 8 / g D O 7 Z O 7 < / l a t e x i t > (2) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 W R F C d c R 5 M 3 S x K d W o G w k k 0 L d E g c = " > A A A B + n i c b V B N S 8 N A E J 3 4 W e t X q k c v w S L U S 0 l E q s e i F 4 8 V 7 A c 0 M W y 2 m 3 b p Z h N 2 N 0 q I / S l e P C j i 1 V / i z X / j t s 1 B W x 8 M P N 6 b Y W Z e k D A q l W 1 / G y u r a + s b m 6 W t 8 v b O 7 t 6 + W T n o y D g V m L R x z G L R C 5 A k j H L S V l Q x 0 k s E Q V H A S D c Y X 0 / 9 7 g M R k s b 8 T m U J 8 S I 0 5 D S k G C k t + W b F T U b 0 P q 8 5 p x P f p T x U m W 9 W 7 b o 9 g 7 V M n I J U o U D L N 7 / c Q Y z T i H C F G Z K y 7 9 i J 8 n I k F M W M T M p u K k m C 8 B g N S V 9 T j i I i v X x 2 + s Q 6 0 c r A C m O h i y t r p v 6 e y F E k Z R Y F u j N C a i Q X v a n 4 n 9 d P V X j p 5 Z Q n q S I c z x e F K b N U b E 1 z s A Z U E K x Y p g n C g u p b L T x C A m G l 0 y r r E J z F l 5 d J 5 6 z u N O q N 2 / N q 8 6 q I o w R H c A w 1 c O A C m n A D L W g D h k d 4 h l d 4 M 5 6 M F + P d + J i 3 r h j F z C H 8 g f H 5 A 8 1 g k 7 o = < / l a t e x i t >(1) 1Figure 2 : Left two: Sketch of the level lines of two different potentials ϕ (1) , ϕ (2) : R 2 → R. Right two: Their corresponding horizon functions ϕ(1)EQUATION∞ as defined in Section 4.1.Furthermore, the ℓ 2 -unit ball being strictly convex, Problem (3) has a unique solution to which β∞ must therefore be equal. Importantly, notice that Problem (3) uniquely defines the limit of any extraction on the normalised iterates βt : the normalised iterates βt must therefore converge towards the ℓ 2 -maximum margin. We recover the implicit regularisation result from Soudry et al. [2018] :β∞ = arg min mini yi⟨xi, β⟩≥1∥ β∥ 2 .We now tackle general potentials ϕ. In the general case, the challenge of identifying the max-margin problem to which the iterates converge in direction stems from the fact that if the potential ϕ is not L-homogeneous , its geometry changes as the iterates diverge. More precisely, its sub-level sets S c := {β ∈ R d , ϕ(β) ≤ c} change of shape as c increase, as illustrated by Figure 2 (Left).However, we can hope that these sets have a limiting shape at infinity, meaning that the normalised sub-level sets Sc := S c /R c where R c := max β∈Sc ∥β∥ converge to some limiting convex set S ∞ as c → ∞. We can then construct an asymmetric norm4 ϕ ∞ which has S ∞ as its unit ball. In words, ϕ ∞ captures the shape of ϕ at infinity. This informal construction is made rigorous in Section 4.1.We state here the crucial consequence of this construction.Corollary 1. The horizon function ϕ ∞ is such that for any sequence β t diverging to infinity for which βt ∥βt∥ and ∇ϕ(βt) ∥∇ϕ(βt)∥ both converge, then:lim t→∞ ∇ϕ(β t ) ∥∇ϕ(β t )∥ ∈ λ • ∂ϕ ∞ ( β∞ ), where β∞ = lim t→∞ β t ∥β t ∥ ,for some strictly positive factor λ.Using this construction, we can derive the optimality conditions satisfied by β∞ . From the convergence in Equation ( 2) and that of βt → β∞ , applying Corollary 1, we obtain that:Z ⊤ q ∞ ∈ λ • ∂ϕ ∞ ( β∞ ).Up to a positive multiplicative factor (which is irrelevant due to the positive homogeneity of the quantities involved), this condition along with Lemma 1 are exactly the optimality conditions of the convex problemmin β∈R d ϕ ∞ ( β) under the constraint min i∈[n] y i ⟨x i , β⟩ ≥ 1.The limiting direction β∞ must therefore belong to the set of its solutions. Assuming that this set contains a single element of norm 1 (we refer to the next section for comments concerning the uniqueness), we deduce that the iterates βt must converge towards it:lim t→∞ β t ∥β t ∥ ∝ arg min mini yi⟨xi, β⟩≥1 ϕ ∞ ( β).Sub-level sets < l a t e x i t s h a 1 _ b a s e 6 4 = " J q e D L B G R P W K J h 3 S n 9 Y k 4 v A F 7 S v c = " > A A A B 7 n i c d V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i R V + 9 g V 3 b i s a B / Q h j C Z T t q h k 0 m Y m Q g l 9 C P c u F D E r d / j z r 9 x 2 k Z Q 0 Q M X D u f c y 7 3 3 + D F n S t v 2 h5 V b W V 1 b 3 8 h v F r a 2 d 3 b 3 i v s H H R U l k t A 2 i X g k e z 5 W l D N B 2 5 p p T n u x p D j 0 O e 3 6 k 6 u 5 3 7 2 n U r F I 3 O l p T N 0 Q j w Q L G M H a S N 1 b L y X e 2 c w r l u y y v Q A y x L F r F x V D G o 2 6 0 6 g j J 7 N K k K H l F d 8 H w 4 g k I R W a c K x U 3 7 F j 7 a Z Y a k Y 4 n R U G i a I x J h M 8 o n 1 D B Q 6 p c t P F u T N 0 Y p Q h C i J p S m i 0 U L 9 P p D h U a h r 6 p j P E e q x + e 3 P x L 6 + f 6 K D u p k z E i a a C L B c F C U c 6 Q v P f 0 Z B J S j S f G o K J Z O Z W R M Z Y Y q J N Q g U T w t e n 6 H / S q Z S d a r l 6 c 1 5 q X m Z x 5 O E I j u E U H K h B E 6 6 h B W 0 g M I E H e I J n K 7 Y e r R f r d d m a s 7 K Z Q / g B 6 + 0 T Z k q P p Q = = < / l a t e x i t > S c 3 < l a t e x i t s h a 1 _ b a s e 6 4 = "Z W L B n 7 n 8 f Z Y V F x h s 0 n k 3 m R + F 4 4 c = " > A A A B 7 n i c d V D L S s N A F L 2 p r 1 p f V Z d u B o v g K i T V 1 m Z X d O O y o n 1 A G 8 J k O m m H T h 7 M T I Q S + h F u X C j i 1 u 9 x 5 9 8 4 b S O o 6 I E L h 3 P u 5 d 5 7 / I Q z q S z r w y i s r K 6 t b x Q 3 S 1 v b O 7 t 7 5 f 2 D j o x T Q W i b x D w W P R 9 L y l l E 2 4 o p T n u J o D j 0 O e 3 6 k 6 u 5 3 7 2 n Q r I 4 u l P T h L o h H k U s Y A Q r L X V v v Y x 4 1 Z l X r l i m 0 6 j V z i x k m d Y C m j i O Y 9 d r y M 6 V C u R o e e X 3 w T A m a U g j R T i W s m 9 b i X I z L B Q j n M 5 K g 1 T S B J M J H t G + p h E O q X S z x b k z d K K V I Q p i o S t S a K F + n 8 h w K O U 0 9 H V n i N V Y / v b m 4 l 9 e P 1 V B w 8 1 Y l K S K R m S 5 K E g 5 U j G a / 4 6 G T F C i + F Q T T A T T t y I y x g I T p R M q 6 R C + P k X / k 0 7 V t O t m / e a 8 0 r z M 4 y j C E R z D K d h w A U 2 4 h h a 0 g c A E H u A J n o 3 E e DR e j N d l a 8 H I Z w 7 h B 4 y 3 T 3 S y j 6 4 = < / l a t e x i t > S c 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " w / P z XK I b V t T B E K m Y V I T k + o U s I F 4 = " > A A A B 7 n i c d V D L S s N A F L 3 x W e u r 6 t L N Y B F c h S T W t s u i G 5 c V 7 Q P a E C b T S T t 0 8 m B m I p T Q j 3 D j Q h G 3 f o 8 7 / 8 Z J G 0 F F D 1 w 4 n H M v 9 9 7 j J 5 x J Z V k f x s r q 2 v r G Z m m r v L 2 z u 7 d f O T j s y j g V h H Z I z G P R 9 7 G k n E W 0 o 5 j i t J 8 I i k O f 0 5 4 / v c r 9 3 j 0 V k s X R n Z o l 1 A 3 x O G I B I 1 h p q X f r Z c S z 5 1 6 l a p n 1 m n P u X C D L t B b I i e 0 0 G w 1 k F 0 o V C r S 9 y v t w F J M 0 p J E i H E s 5 s K 1 E u R k W i h F O 5 + V h K m m C y R S P 6 U D T C I d U u t n i 3 D k 6 1 c o I B b H Q F S m 0 U L 9 P Z D i U c h b 6 u j P E a i J / e 7 n 4 l z d I V d B 0 M x Y l q a I R W S 4 K U o 5 U j P L f 0 Y g J S h S f a Y K J Y P p W R C Z Y Y K J 0 Q m U d w t e n 6 H / S d U y 7 b t Z v a t X W Z R F H C Y 7 h B M 7 A h g a 0 4 B r a 0 A E C U 3 i A J 3 g 2 E u P R e D F e l 6 0 r R j F z B D 9 g v H 0 C U 0 O P l w = = < / l a t e x i t > S c 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " / c d h y u 6 s K m 0 6 q P O n Z l V G o w q J H X E = " > A A A B 9 H i c d V D L S s N A F J 3 U V 6 2 v q k s 3 g 0 V w F Z J q a 7 M r u n F Z 0 T 6 g D W E y n b R D J 5 M 4 M y m U k O 9 w 4 0 I R t 3 6 M O / / G a R t B R Q 9 c O J x z L / f e 4 8 e M S m V Z H 0 Z h Z X V t f a O 4 W d r a 3 t n d K + 8 f d G S U C E z a O G K R 6 P l I E k Y 5 a S u q G O n F g q D Q Z 6 T r T 6 7 m f n d K h K Q R v 1 O z m L g h G n E a U I y U l t y B j 0 R 6 m 3 k p 9 q q Z V 6 5 Y p t O o 1 c 4 s a J n W A p o 4 j m P X a 9 D O l Q r I 0 f L K 7 4 N h h J O Q c I U Z k r J v W 7 F y U y Q U x Y x k p U E i S Y z w B I 1 I X 1 O O Q i L d d H F 0 B k + 0 M o R B J H R x B R f q 9 4 k U h V L O Q l 9 3 h k i N 5 W 9 v L v 7 l 9 R M V N N y U 8 j h R h O P l o i B h U E V w n g A c U k G w Y j N N E B Z U 3 w r x G A m E l c 6 p p E P 4 + h T + T z p V 0 6 6 b 9 Z v z S v M y j 6 M I j s A x O A U 2 u A B N c A 1 a o A 0 w u A c P 4 A k 8 G 1 P j 0 X g x X p e t B S O f O Q Q / Y L x 9 A k H K k n M = < / l a t e x i t > Sc 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " z Y N 8 E J Q 0 m f y r K Y / W I Y c P W 0 P j H n E = " > A A A B 9 H i c d V D L S s N A F J 3 4 r P V V d e l m s A i u Q h J r 2 2 X R j c u K 9 g F t C J P p p B 0 6 m c S Z S a G E f I c b F 4 q 4 9 W P c + T d O 2 g g q e u D C 4 Z x 7 u f c e P 2 Z U K s v 6 M F Z W 1 9 Y 3 N k t b 5 e 2 d 3 b 3 9 y s F h V 0 a J w K S D I x a J v o 8 k Y Z S T j q K K k X 4 s C A p 9 R n r + 9 C r 3 e z M i J I 3 4 n Z r H x A 3 R m N O A Y q S 0 5 A 5 9 J N L b z E u x Z 2 d e p W q Z 9 Z p z 7 l x A y 7 Q W y I n t N B s N a B d K F R R o e 5 X 3 4 S j C S U i 4 w g x J O b C t W L k p E o p i R r L y M J E k R n i K x m S g K U c h k W 6 6 O D q D p 1 o Z w S A S u r i C C / X 7 R I p C K e e h r z t D p C b y t 5 e L f 3 m D R A V N N 6 U 8 T h T h e L k o S B h U E c w T g C M q C F Z s r g n C g u p b I Z 4 g g b D S O Z V 1 C F + f w v 9 J 1 z H t u l m / q V V b l 0 U c J X A M T s A Z s E E D t M A 1 a I M O w O A e P I A n 8 G z M j E f j x X h d t q 4 Y x c w R + A H j 7 R M g W 5 J c < / l a t e x i t > Sc 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 3 c F m z q + Y P + t B t z d q Y C S s k A A m K l c = " > A A A B 9 H i c d V D J S g N B E K 2 J W 4 x b 1 K O X x i B 4 C j N R s 9 y C X j x G N A s k w 9 D T 6 U m a 9 C x 2 9 w T C M N / h x Y M i X v 0 Y b / 6 N n W Q E F X 1 Q 8 H i v i q p 6 b s S Z V K b 5 Y e R W V t f W N / K b h a 3 t n d 2 9 4 v 5 B R 4 a x I L R N Q h 6 K n o s l 5 S y g b c U U p 7 1 I U O y 7 n H b d y d X c 7 0 6 p k C w M 7 t Q s o r a P R w H z G M F K S / b A x S K 5 T Z 2 E O G e p U y y Z Z X M B p I l l 1 i 4 q m j Q a d a t R R 1 Z m l S B D y y m + D 4 Y h i X 0 a K M K x l H 3 L j J S d Y K E Y 4 T Q t D G J J I 0 w m e E T 7 m g b Y p 9 J O F k e n 6 E Q r Q + S F Q l e g 0 E L 9 P p F g X 8 q Z 7 + p O H 6 u x / O 3 N x b + 8 f q y 8 u p 2 w I I o V D c h y k R d z p E I 0 T w A N m a B E 8 Z k m m A i m b 0 V k j A U m S u d U 0 C F 8 f Y r + J 5 1 K 2 a q W q z f n p e Z l F k c e j u A Y T s G C G j T h G l r Q B g L 3 8 A B P 8 G x M j U f j x X h d t u a M b O Y Q f s B 4 + w Q z Y p J q < / l a t e x i t > Sc 3 Normalised Sub-level sets < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 3 D c 1 w t Z G U O y f 8 b s i I R + l M 0 5 7 x o = " > A A A B 7 3 i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K o l I 9 V j 0 4 r G i / Y A 2 l M 1 2 0 y 7 d b O L u R C i h f 8 K L B 0 W 8 + n e 8 + W / c t j l o 6 4 O B x 3 s z z M w L E i k M u u 6 3 s 7 K 6 t r 6 x W d g q b u / s 7 u 2 X D g 6 b J k 4 1 4 w 0 W y 1 i 3 A 2 q 4 F I o 3 U K D k 7 U R z G g W S t 4 L R z d R v P X F t R K w e c J x w P 6 I D J U L B K F q p f d / r C h X i u F c q u x V 3 B r J M v J y U I U e 9 V / r q 9 m O W R l w h k 9 S Y j u c m 6 G d U o 2 C S T 4 r d 1 P C E s h E d 8 I 6 l i k b c + N n s 3 g k 5 t U q f h L G 2 p Z D M 1 N 8 T G Y 2 M G U e B 7 Y w o D s 2 i N x X / 8 z o p h l d + J l S S I l d s v i h M J c G Y T J 8 n f a E 5 Q z m 2 h D I t 7 K 2 E D a m m D G 1 E R R u C t / j y M m m e V 7 x q p X p 3 U a 5 d 5 3 E U 4 B h O 4 A w 8 u I Q a 3 E I d G s B A w j O 8 w p v z 6 L w 4 7 8 7 H v H X F y W e O 4 A + c z x 8 i B J A N < / l a t e x i t > S 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " M v w / x o W U v I v A f J y Q z b 6 K + 2 c k Q j M = " > A A A C E H i c b V D L S g M x F M 3 U V 6 2 v q k s 3 w S K 6 K j M i 1 W X R j c s K 9 g G d M m T S T B u a S U J y R y i l n + D G X 3 H j Q h G 3 L t 3 5 N 6 a P h b Y e C B z O u Z e b c 2 I t u A X f / / Z y K 6 t r 6 x v 5 z c L W 9 s 7 u X n H / o G F V Z i i r U y W U a c X E M s E l q w M H w V r a M J L G g j X j w c 3 E b z 4 w Y 7 m S 9 z D U r J O S n u Q J p w S c F B V P Q 9 3 n U c h l A k M c a q M 0 K B w 2 m A E c 0 q 6 C G Y + C q F j y y / 4 U e J k E c 1 J C c 9 S i 4 l f Y V T R L m Q Q q i L X t w N f Q G R E D n A o 2 L o S Z Z Z r Q A e m x t q O S p M x 2 R t N A Y 3 z i l C 5 O l H F P A p 6 q v z d G J L V 2 m M Z u M i X Q t 4 v e R P z P a 2 e Q X H V G X O o M m K S z Q 0 k m s A s 9 a Q d 3 u W E U x N A R Q g 1 3 f 8 W 0 T w y h 4 D o s u B K C x c j L p H F e D ir l y t 1 F q X o 9 r y O P j t A x O k M B u k R V d I t q q I 4 o e k T P 6 B W 9 e U / e i / f u f c x G c 9 5 8 5 x D 9 g f f 5 A 2 F 4 n M 4 = < / l a t e x i t > 1 / k • k 1 Figure 3 : Illustration of the construction of the horizon shape S ∞ . Left: the sub-level sets S c change of shape and are increasing. Middle: in order to avoid the shapes blowing up, we normalise them to keep them in the unit ball (here we choose the arbitrary constraining norm to be the ℓ 1 -norm). Right: the normalised sub-level sets Sc converge to a limiting set S ∞ for the Hausdorff distance.4 Main result: directional convergence towards the ϕ ∞ -max marginWe now state our formal results, starting with the precise construction of the horizon function ϕ ∞ , followed by the theorem showing convergence of the iterates towards the ϕ ∞ -max-margin.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: The main assumptions on the loss, potential and dataset are given at the beginning of the paper. If an additional assumption is required, it is clearly stated in the result. The proofs are all deferred to the appendix but we 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 crossreferenced. • 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 if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
construction of the horizon function ϕ ∞: 
 We first define the horizon shape of a potential ϕ, and provide sufficient conditions for its existence. Then, we use this shape to construct a horizon function ϕ ∞ , 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.o.g. that ϕ(0) = 0. For c ≥ 0, consider the sublevel set:S c (ϕ) = {β ∈ R d : ϕ(β)≤ c}, which is nonempty and compact by coercivity of ϕ. We can then define the normalised sublevel set:EQUATION)By construction, the set Sc belongs to the unit ball. We are interested in the limit of Sc as c → ∞. Definition 1. We say that ϕ admits a horizon shape if the family of normalized sublevel sets ( Sc ) c>0 defined in Equation (4) converges to some compact set S ∞ as c → ∞ for the Hausdorff distance. In addition, we say that this shape is non-degenerate if the origin belongs to the interior of S ∞ .The Hausdorff distance is a natural distance on compact sets [see Rockafellar and Wets, 1998, Section 4 .C., for a definition]. In Proposition 2, we prove the existence of the horizon shape for a large class of functions which contains all the potentials with domain R d encountered in practice. Although the horizon shape is guaranteed to exist for most functions, we cannot a priori prove that it is non-degenerate, as the normalized sub-levels Sc can become 'flat' as c → ∞. 5 Given the technical complexity associated with this case, we now focus exclusively on non-degenerate horizon shapes.Horizon function. If ϕ admits a non-degenerate horizon shape S ∞ , we define its horizon function as the Minkowski gauge [Rockafellar and Wets, 1998, Section 11 .E] of S ∞ :ϕ ∞ ( β) := inf {r > 0 : β r ∈ S ∞ } for β ∈ R d .By construction, the horizon function ϕ ∞ is an asymmetric norm and its sub-level sets correspond to scaled versions of S ∞ [see Rockafellar and Wets, 1998, Section 11 .C, for more properties]. For example, in the case of the horizon shape S ∞ illustrated in Figure 3 , the corresponding horizon function ϕ ∞ is proportional to the ℓ 1 -norm. Although the construction of ϕ ∞ presented here is rather abstract, we show in Theorem 3 that for separable potentials defined over R d , it can be 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 at the end of Section 4.3.We can now state our main result which fully characterises the directional convergence of mirror flow.Theorem 2. Assume that ϕ admits a non-degenerate horizon shape and let ϕ ∞ be its horizon function.Assuming that the following ϕ ∞ -max-margin problem has a unique minimiser, then the mirror flow normalised iterates βt = βt ∥βt∥ converge towards a vector β∞ and β∞ ∝ arg minβ∈R d ϕ ∞ ( β) under the constraint min i∈[n] y i ⟨x i , β⟩ ≥ 1,where the symbol ∝ denotes positive proportionality.Remark on the uniqueness of the margin problem. If the unit ball of ϕ ∞ is strictly convex, then the ϕ ∞ -max-margin problem has a 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 to guarantee uniqueness. For instance, if ϕ ∞ is proportional to the ℓ 1 -norm, a common assumption which ensures uniqueness is assuming that the data features are in general position [Dossal, 2012] .Our main result, presented in Theorem 2 relies on the existence of a horizon shape, S ∞ , as described in Definition 1. From this shape, the asymmetric norm ϕ ∞ is constructed.We show here that the existence of S ∞ is ensured for a 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 a typical assumption used for instance to prove the convergence of optimisation methods through the Kurdyka-Łojasiewicz property [Attouch et al., 2011] . Proposition 2. If any of the three following conditions hold: (i) ϕ is a finite composition of polynomials, exponentials and logarithms, (ii) ϕ is globally subanalytic, (iii) ϕ is definable in a o-minimal structure on R; then ϕ admits a horizon shape S ∞ .The proof is technical and we defer it to Appendix B. Although the previous proposition ensures the existence ϕ ∞ for a wide range of potentials, it does not offer a 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 ϕ ∞ . Assumption 4. The potential ϕ is separable, in the sense that there exists φ : R → R ≥0 such that ϕ(β) = d i=1 φ(β i ). We assume that φ satisfies Assumption 2, that it is definable in a o-minimal structure on R and that it is an even function. W.l.o.g. we assume that φ(0) = 0.We note that φ is a bijection over R ≥0 , and denote by φ -1 its inverse. We consider the function φ -1 • ϕ, which can be seen as a renormalisation of ϕ. It has the same level sets as ϕ and ensures that lim η→0 ηφ -1 (ϕ( β/η)) exists in R >0 for all β. These two observations lead to the following theorem. Theorem 3. Under Assumption 4, the potential ϕ admits a non-degenerate horizon shape and its horizon function is such that there exists λ > 0 such that for every β ∈ R d :ϕ ∞ ( β) = λ lim η→0 η • φ -1 ϕ β η .We use this simple formula when computing ϕ ∞ 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 ϕ ∞ ( β) = lim η→0 ηϕ( β/η) [Rockafellar and Wets, 1998, Laghdir and Volle, 1999] . In our context, this definition would yield a function which equals +∞ everywhere except at the origin. In contrast, our definition ensures that ϕ ∞ attains finite values over R d . The distinction stems from our way of normalising the level sets by R c in Section 4.1, or alternatively, from the composition by φ -1 in the separable case. The two constructions would coincide only if ϕ was Lipschitz continuous, which is at odds with Assumption 2.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of 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 in Section 5, we perform mirror descent over the dataset with the exponential loss. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [No] Justification: The code behind the experiments is straightforward and can easily be reproduced.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) 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 (e. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion and limitations: 
 In this paper, we offer a comprehensive characterisation of the implicit bias of 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 of R d (such as the log-barrier and the negative entropy), and with possibly non-coercive gradients. This class of potentials is of interest as it arises when investigating deep architectures, such as diagonal linear networks of depth D > 2. In this setting, it is known that gradient flow on the weights lead to a mirror flow on the predictors with a certain potential ϕ D [Woodworth et al., 2020] . Interestingly, the potentials ϕ D have non-coercive gradients and their horizon functions do not depend on the depth D as they are all proportional to the ℓ 1 -norm. The predictors are, however, known to converge in direction towards a KKT point of the non-convex ℓ 2/D -max-margin problem [Lyu and Li, 2020] which can be different from the ℓ 1 -max-margin problem [Moroshko et al., 2020] . This observation highlights that our coercive gradient assumption is necessary for our result to hold. However, extending our analysis beyond this assumption is a promising direction for understanding gradient dynamics in deep architectures.Organisation of the Appendix.1. In 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 2 and 3.where the inequality is by convexity of the loss. Integrating and due to the decrease of the loss, we get that:L(β t ) ≤ 1 t t 0 L(β s ) ds ≤ L(β) + D ϕ (β, β 0 ) -D ϕ (β, β t ) t ≤ L(β) + D ϕ (β, β 0 ) tSince this is true for all point β, we get thatL(β t ) ≤ inf β∈R d L(β) + D ϕ (β,β0) t. It remains to show that the right hand term goes to 0 as t goes to infinity. To show this, let ε > 0, by the separability assumption we get that there exists β ⋆ such that min y i ⟨x i , β ⋆ ⟩ > 0. Since L(λβ ⋆ ) -→ λ→∞ 0, we can choose λ big enough such that L(λβ ⋆ ) < ε and then t λ large enough such that 1 t λ D ϕ (λβ ⋆ , β 0 ) < ε. The loss therefore converges to 0.Divergence of the iterates.For all i ∈ [n], ℓ(y i ⟨x i , β t ⟩) ≤ L(β t ) -→ t→∞ 0.Due to the assumptions on the loss, this translates intoy i ⟨x i , β t ⟩ -→ t→∞ ∞, hence ∥β t ∥ -→ t→∞ +∞.Introducing a few notations. Before giving two important lemmas, we provide a few notations. Recall that Z is the data matrix of size n × d whose i th row is y i x i , we then have that ∇L(β) = Z ⊤ ℓ ′ (Zβ), where ℓ ′ is applied component wise. We now denote by q(β) the vector in R n equal to:q(β) = ℓ ′ (Zβ) ℓ ′ (ℓ -1 ( i ℓ(y i ⟨x i , β⟩)))Notice that due to ℓ > 0, ℓ ′ < 0, ℓ -1 is increasing and ℓ ′ is decreasing, we have that q(β) > 0 and that for all i 0 ∈ [n], q(β) i0 = ℓ ′ (y i0 ⟨x i0 , β⟩) ℓ ′ (ℓ -1 ( i ℓ(y i ⟨x i , β⟩))) ≤ ℓ ′ (y i0 ⟨x i0 , β⟩) ℓ ′ (ℓ -1 (ℓ(y i0 ⟨x i0 , β⟩)))≤ 1.Therefore q(β) ∈ (0, 1] n .We further denotea t := -ℓ ′ (ℓ -1 ( i ℓ(y i ⟨x i , β t ⟩))) > 0.This way we can simply write ∇L(β t ) = -a t Z ⊤ q t with q t := q(β t ).Integrating the flow (MF), we write:EQUATION)Two lemmas. In the following lemma we recall and prove that a coordinate q ∞ [k] must be equal to 0 if datapoint x k is not a support vector of β∞ .Lemma 3. For some function C t → ∞, if the iterates βt = βt Ct converge towards a vector which we denote β∞ and q t converges towards a vector q ∞ ∈ [0, 1] n . Then it holds that:q ∞ [k] = 0 if y k ⟨x k , β∞ ⟩ > min 1≤i≤n y i ⟨x i , β∞ ⟩.In words, q ∞ [k] = 0 if x k is not a support vector.Proof. Recall thatq(β t ) = ℓ ′ (Zβ t ) ℓ ′ (ℓ -1 ( i ℓ(y i ⟨x i , β t ⟩))).From Proposition 1, we have that min i∈[n] y i ⟨x i , β∞ ⟩ > 0 and we denote this margin as γ. Now consider k ∈ [n] which is not a support vector, i.e, y k ⟨x k , β∞ ⟩ > min i∈[n] y i ⟨x i , β∞ ⟩ and without loss of generality assume that y 1 ⟨x 1 , β∞ ⟩ = min 1≤i≤n y i ⟨x i , β∞ ⟩. We denote by δ = ⟨y k x ky 1 x 1 , β∞ ⟩ > 0 the gap. Thenq(β t ) k = ℓ ′ (C t ⟨x k , βt ⟩) ℓ ′ (ℓ -1 ( i ℓ(C t y i ⟨x i , βt ⟩))) ≤ ℓ ′ (C t y k ⟨x k , βt ⟩) ℓ ′ (C t y 1 ⟨x 1 , βt ⟩)We write βt = β∞ + r t where (r t ) t≥0 ∈ R d converges to 0. For t big enough, we have that y k ⟨x k , βt ⟩ ≥ y k ⟨x k , β∞ ⟩ -δ 4 and y 1 ⟨x 1 , βt ⟩ ≤ y 1 ⟨x 1 , β∞ ⟩ + δ 4 . Therefore for t large enough, since ℓ ′ is negative and increasing:q(β t )[k] ≤ ℓ ′ (C t (y k ⟨x k , β∞ ⟩ -δ/4)) ℓ ′ (C t (y 1 ⟨x 1 , β∞ ⟩ + δ/4)) ≤ ℓ ′ (C t (γ + δ/2 + δ/4)) ℓ ′ (C t (γ + δ/2)) -→ t→∞ 0,where the last term converge to 0 due to the exponential tail of -ℓ ′ and that C t → ∞.We here reformulate and prove Lemma 1. Lemma 4 (Reformulation of Lemma 1). Denoting a(β t ) := -ℓ ′ (ℓ -1 ( i ℓ(y i ⟨x i , β t ⟩))) > 0, we have that Proof. Recall that ∇ϕ(β t ) = ∇ϕ(β 0 ) + Z ⊤ t 0 a(β s )q(β s )ds, therefore∥∇ϕ(β t )∥ ≤ ∥∇ϕ(β 0 )∥ + n i=1 ∥x i ∥ t 0 a(β s )q(β s )[i]ds ≤ ∥∇ϕ(β 0 )∥ + n i=1 ∥x i ∥ t 0 a(β s )ds.Where the first inequality is due to the triangle inequality and the second to the fact q(β) ∈ (0, 1] n . Since the iterates diverge, we have from Assumption 2 that ∥∇ϕ(β t )∥ -→ t→∞ ∞ and therefore that t 0 a(β s )ds -→ t→∞ +∞.Consider now a sequence (β s ) s>0 satisfying the conditions described in (ii). Since it diverges to infinity and ϕ is coercive, we have ϕ(β s ) → ∞, and we may assume w.l.o.g that ϕ(β s ) > 0 for all s.We have by definition of sublevel sets that β s ∈ S ϕ(βs) , and therefore the gradient ∇ϕ(β s ) belongs to the normal cone of S ϕ(βs) at β s (indeed, the gradient is orthogonal to the level sets; see 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 haveEQUATIONConsider now the normalized levels sets as defined in (4). Denotingβs = β s R ϕ(βs),we have βs ∈ Sϕ(βs) and thus by simple rescaling (8) becomes ∇ϕ(β s ) ∈ ∂I Sϕ(βs) βs .Since ∂I Sc is a cone (the normal cone to Sc ), this also holds for any positive multiple of ∇ϕ(β s ). We deduce that for every s > 0 βs , ∇ϕ(β s ) ∥∇ϕ(β s )∥ ∈ G(∂η ϕ(βs) ).Note that since βs belongs to the normalized level sets, this sequence is bounded. We can extract a subsequence ( βs k , ∇ϕ(βs k )∥∇ϕ(βs k )∥ ) k≥0 which converges to a limit point ( β, ĝ). By the previous remark on graphical convergence of subdifferentials, we have ( β, ĝ) ∈ G(∂I S∞ ), i.e., ĝ ∈ ∂I S∞ ( β).(9)We need to prove that β is not 0. Since ϕ is strictly convex, the level set {ϕ(β) = c} is exactly the boundary of the sublevel set {ϕ(β) ≤ c}. Therefore, β s lies on the boundary of S ϕ(βs) , and hence so does βs lie on the boundary of Sϕ(βs) . Since 0 is in the interior of S ∞ , it also belongs to the interior of Sϕ(βs) for s larger than some s 0 . Then, there exists r 0 > 0 such that B(0, r 0 ) ⊂ Sϕ(βs) for s ≥ s 0 . By definition of boundary, we then have for s ≥ s 0 ∥ βs ∥ > r 0 , which leads to ∥ β∥ > 0.To achieve the desired result; we need to relate ( β, ĝ) to ( β, ḡ). First, notice that by construction we have necessarily ĝ = ḡ = lim s→∞ ∇ϕ(β s )/∥∇ϕ(β s )∥. Then, note thatβ = lim k→∞ β s k ∥β s k ∥ , β = lim k→∞ β s k R ϕ(βs k ).Taking the norm of the second limit, we have ∥ β∥ = lim k→∞ ∥βs k ∥ R ϕ(βs k ) . Injecting back in the first limit yieldsβ = lim k→∞ β s k R ϕ(βs k ) • R ϕ(βs k ) ∥β s k ∥ = β ∥ β∥ .Therefore, (9) becomes ḡ ∈ ∂I S∞ (∥ β∥ β).This means that ḡ belongs to the normal cone of S ∞ at ∥ β∥ β [Rockafellar, 1970, Sec. 23] . We note the level set {β : ϕ ∞ (β) ≤ ϕ ∞ ∥ β∥ β } is exactly τ S ∞ for some τ > 0. We use Corollary 23.7.1 from Rockafellar [1970] which states that if a vector is in the normal cone of the level set of ϕ ∞ , then it must be a positive multiple of a subgradient. This implies that that there exists λ ≥ 0 such that ḡ ∈ λ∂ϕ ∞ (∥ β∥ β).Finally, λ > 0 since ∥ḡ∥ = 1, and ∂ϕ ∞ (∥ β∥ β) = ∂ϕ ∞ ( β) by positive homogenity of ϕ ∞ .We can now prove our main result, which we restate here.Theorem 2. Assume that ϕ admits a non-degenerate horizon shape and let ϕ ∞ be its horizon function.Assuming that the following ϕ ∞ -max-margin problem has a unique minimiser, then the mirror flow normalised iterates βt = βt ∥βt∥ converge towards a vector β∞ and β∞ ∝ arg minβ∈R d ϕ ∞ ( β) under the constraint min i∈[n] y i ⟨x i , β⟩ ≥ 1,where the symbol ∝ denotes positive proportionality.The proof essentially follows exactly the same lines as in Section 3 but taking into account the fact that the loss is not exactly the exponential one.Proof. Recall the definitions of the quantities a t and q t given above Equation ( 7) which enable to write:∇ϕ(β t ) = ∇ϕ(β 0 ) + Z ⊤ t 0 a s q s ds.Similar to the time change we performed in Section 3, we consider θ(t) = t 0 a s ds. From Lemma 4, θ is a bijection over R ≥0 and perform the time change βt = β θ -1 (t) . Due to the chain rule, after the time change and dropping the tilde notation we obtain:∇ϕ(β t ) = ∇ϕ(β 0 ) + Z ⊤ t 0 q s ds.Dividing by t we get:EQUATIONwhere qt := 1 t t 0 q s ds corresponds to the average of (q s ) s≤t .Extracting a convergent subsequence: We now consider the normalised iterates βt = βt ∥βt∥ and up to an extraction we get that βt → β∞ . Since q t is a bounded function, up to a second extraction, we have that q t → q ∞ , and the same holds for its average: qt → q ∞ . Taking the limit in Equation ( 10) we immediately obtain that:lim t 1 t ∇ϕ(β t ) = Z ⊤ q ∞ , which also means that ∇ϕ(β t ) ∥∇ϕ(β t )∥ -→ t→∞ Z ⊤ q ∞ ∥Z ⊤ q∞ ∥We can now directly apply Corollary 2 and there exists λ > 0 such that:Z ⊤ q ∞ ∈ λ∂ϕ ∞ ( β∞ )The end of the proof is then as explained in Section 3.Finally we recall and prove Theorem 3 which provides a simple formula for the horizon function in the case of separable potentials.Theorem 3. Under Assumption 4, the potential ϕ admits a non-degenerate horizon shape and its horizon function is such that there exists λ > 0 such that for every β ∈ R d :ϕ ∞ ( β) = λ lim η→0 η • φ -1 ϕ β η .Proof. Lipschitzness, upper and lower boundedness. For η > 0, let us denote by hη : β → η • φ -1 (ϕ(β/η)) and notice that ∇h η (β) = ( φ ′ (β k /η) φ ′ (φ -1 ( i φ(βi/η))) ) k∈[d]≥ 0 Since φ ≥ 0 and that φ -1 and φ ′ are increasing we get that that ∇h η (β) ∈ [0, 1] d . Therefore (h η ) η>0 are uniformly Lipschitz-continuous. Consequently, for all β, h η (β) is upper-bounded independently of η. Lastly, since φ ≥ 0, notice that h η (β) ≥ min i |β i | > 0 for all β ̸ = 0.Point-wise and epi-convergence of h η . For all β, by composition, η → η • φ -1 (ϕ( β/η)) is a definable function, the monotonicity Lemma [Van den Dries and Miller, 1996] (Theorem 4.1) ensures that it has a unique limit in R which we denote h 0 (β). From the uniform Lipschitzness of h η , we get that (η, β) ∈ R ≥0 × R d → h η (β) is continuous. Hence for all sequence η k → 0, we get that h η k epi-converges to h 0 . Therefore (epi h η k ) k converges in the Painlevé-Kuratowski sense towards epi h η0 .Link between the level sets of h η and those of ϕ. To conclude the proof it remains to notice that for all c ≥ 0:{β ∈ R d , ϕ(β) ≤ c} = 1 η { β ∈ R d , h η ( β) ≤ ηφ -1 (c)}.Therefore letting η c = 1/φ -1 (c) we get thatη c • S c = { β ∈ R d , h ηc ( β) ≤ 1}.This simply means that η c is an appropriate normalising quantity, it replaces the normalisation by the radius ofS c . Since { β ∈ R d , h ηc ( β) ≤ 1} converges in the Painlevé-Kuratowski sense towards { β ∈ R d , h 0 ( β) ≤ 1}, we get that R c η c• Sc converges towards the same set. However, with our previous construction, we also have that Sc converges towards S∞ . The sets S∞ and { β ∈ R d , h 0 ( β) ≤ 1} are therefore proportional and h 0 ∝ ϕ ∞ which concludes the proof.• 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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, a 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 in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 a 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, or as supplemental material. 
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 not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: It is clear that our experiments can easily be reproduced by any computer.Guidelines:• The answer NA means that the paper does not include experiments.• 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 of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have checked the Code of Ethics and our work respects it.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 think are work leads to any direct positive nor negative societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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 (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]  
 
 Appendix: • The answer NA means that the paper does not include experiments.• 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 a 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 it 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. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.βt can also be seen as the mirror flow trajectory but on the log-sum-exp function instead of the sum-exp functionMore precisely, we let (tn) n∈N be any sequence with tn → ∞ as n → ∞ and then consider the discrete sequence ( βtn , q(βt n )) n∈N . We can then apply the Bolzano-Weierstrass theorem to extract a convergent subsequence. We will show that the limit ( β∞, q∞) is unique and does not depend on the sequence (tn), and therefore the continuous-time process ( βt, q(βt)) t∈R must converge towards it.A function is L-homogeneous if there exists L > 0 such that ϕ(cβ) = c L ϕ(β) for all β and c > 0An asymmetric norm p satisfies all the properties of a norm except the symmetry equality p(-β) = p(β)Consider for instance ϕ(x, y) = x 2 + y 4 on R 2 , for which the horizon shape is [-1, 1] × {0}. 


Decision: 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.

Reviews: review: paper_summary: paper_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$.
strength_weakness: strength_weakness: - The paper does not characterize $\phi_\infty$ in terms of the bregman potential $\phi$ (and other relevant entities). 
The main result expresses that there exists some function, that is minimized by $\bar \beta_\infty$, the direction of the classifier as $t\rightarrow \infty$. 
I 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.

- 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.
---
*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.*
questions: 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?

- Beyond gradient descent, is there any work that quantifies the rates of convergence to max-margin classifiers? Is this even possible?
limitations: limitations: The limitations are discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: NA
questions: 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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.
2. 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
2. 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.
3. 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.

[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.
questions: 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.
2. I guess there might be no minus in line 461 for the first equality.
3. 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.
4. 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) ?

[1] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.

[2] B.Wang, Q. Meng,W. Chen, and T.-Y. Liu. The implicit bias for adaptive optimization algorithms on homogeneous
neural networks. In International Conference on Machine Learning, pages 10849–10858. PMLR, 2021.
limitations: limitations: No limitations.

Comments: title: Reviewer Response
comment: I thank the authors for the response. My rating remains.
Thanks for the answers from the authors. I'm happy to maintain my score, voting for acceptance.
I thank the authors for the response. My rating remains.
Thank you for the answers.

Base on this, and reading other reviews, I have updated my review (the confidence score).
Dear Reviewers,

Now that the rebuttal period has ended, please take a moment to review the authors' responses to your initial reviews. Your engagement is crucial for:

    Ensuring a fair evaluation process
    Improving the quality of final reviews
    Fostering meaningful scientific discourse

If you have any questions or need clarification, please post follow-up comments.

Your continued dedication to this process is greatly appreciated.

Best regards,

AC