Faster Margin Maximization Rates for Generic Optimization Methods
Authors: Guanghui Wang
Zihao Hu
Vidya Muthukumar
Jacob Abernethy
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Implicit bias
margin maximization
zero-sum game
online learning
TL;DR: We provide a series of state-of-the-art implicit bias rates for generic optimization algorithms.

Abstract: First-order optimization methods tend to inherently favor certain solutions over others when minimizing a given training objective with multiple local optima. This phenomenon, known as \emph{implicit bias}, plays a critical role in understanding the generalization capabilities of optimization algorithms. Recent research has revealed that gradient-descent-based methods exhibit an implicit bias for the $\ell_2$-maximal margin classifier in the context of separable binary classification. In contrast, generic optimization methods, such as mirror descent and steepest descent, have been shown to converge to maximal margin classifiers defined by alternative geometries. However, while gradient-descent-based algorithms demonstrate fast implicit bias rates, the implicit bias rates of generic optimization methods have been relatively slow. To address this limitation, in this paper, we present a series of state-of-the-art implicit bias rates for mirror descent and steepest descent algorithms. Our primary technique involves transforming a generic optimization algorithm into an online learning dynamic that solves a regularized bilinear game, providing a unified framework for analyzing the implicit bias of various optimization methods. The accelerated rates are derived leveraging the regret bounds of online learning algorithms within this game framework.

Faster Margin Maximization Rates for Generic Optimization Methods
Guanghui Wang', Zihao Hu', Vidya Muthukumar Jaccbb Abernethy
College of Computing, Georgia Institute of Technology
Sccooo of Electrical and Computer Engineering, Georgia Institute of Technology
SSchool of Industrial and Systems Engineering, Georgia Institute of Technology 'Google Research, Atalanta
{gwang369, zihaohu, vmuthukumarr@ @gatech. edu, abernethyj@google.co
Abstract
First-order optimization methods tend to inherently favor certain solutions over others when minimizing a given training objective with multiple local optima. This phenomenon, known as implicit bias, plays critical role in understanding the generalization capabilities of optimization algorithms. Recent research has revealed that gradient-descent-bee
methods exhibit an implicit bias for the mm-maximal margin classifier the context separable binary classification. generic optimization methods, such mirror descent and steepest descent, have been shown to converge to maximal margin classifiers defined by alternative geometries. However, while deddient-eescent-basedd al algorithms demonstrate fast implicit bias rates, the implicit bias rates generic optimization methods have been relatively slow. To address this limitation, in this paper, present series of state- of-the-ar art implicit bias rates for mirror descent and steepest descent algorithms. Our primary technique involves transforming generic optimization algorithm into an online learning dynamic that solves a regularized bilinear game, providing a unified framework for analyzing the implicit bias of various optimization methods.
contrast,
The accelerated rates are derived leveraging the regret bounds of online learning algorithms within this game framework.
Introduction
The training objective in the optimization of modern over-parametrized ML models typically presents various local optima with low training error. Despite this, empirical studies have demonstrated that first-order optimization methods generally converge to the solution with strong generalization, even without any explicit regularization (Neyshabur et al. 2014 Zhang et al. 2021). This observation has spurred interest the study of the implicil bias of the algorithm. In other words, among all potential parameter choices with low training error, which ones are inherently favored by optimization methods?
For the classical linear classification problem with separable data, the pioneering works (Soudry al. 2018 Ji Telgarsky 2018) reveal that minimizing the (unregularized) empirical risk with exponential loss by the classical gradient descent (GD) automatically maximizes the || 1l2-margin, meaning its margin converges to that of the best classifier within an fnrmorm ball (referred to as the
|. mmaxmmall margin classifier). This finding implies that GD exhibits implicit bias towards the mmaximaalll margin classifier, which helps account for its favorable generalization performance. loo T rate,
However, these works show that GD only maximizes the || lla-mn at a slow O loo where T is the time horizon, and is the cardinality of the data set. Since then, several faster margin
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

maximization rates have been reported. Nacson et al. 2019
revealed that for the exponential loss, log +
GD with an aggressive step size attains an O
||2 la-margin maximization rate. This
vT
result was later improved to O log by Ji & Telgarsky (021)) via an elegant primal-dual analysis.
Recent work (Ji et 2021 Wang al. 2022b) further proved that momentum- based GD and
Nesterov-accelerated GD can maximize the 1la-maggin at an O
log
rate.
As the implicit bias of seapiient-deeeet--baee methods becomes better understood, it is natural to explore similar characterizations for other optimization methods. Note that, since gradient-descent- based methods are biased towards the 1/2-maximal margin classifier, they might generalize poorly when the data does not adhere to the f2-geometry, as shown in /eetile (2000); Chen et al. (2001). This limitation suggests that essential to study the implicit bias alternative optimization methods that could potentially be biased in different directions. Two such methods include steepest descent with respect to different norms and mirror descent with different potentials. For instance, Gunasekar al. (2018a) demonstrate that for the exponential loss, the steepest descent algorithm with respect to a general norm -|| asymptotically converges to the corresponding || |l-maximal margin classifier. This result implies that the steepest descent algorithm
adapt to different data
geometries by changing the norm used in the algorithm. On the other hand, [Sun et al. (2022) show that the mirror descent algorithm with the potential . |11 for q >> 1 can maximize the g -arrgin at
a rate of O [log (Tog?)-r)
While the asymptotic directional convergence of these generic optimization methods is well- understood, natural question remains: can generic optimization methods (e.g., mirror descent and steepest descent) achieve faster margin maximization rates? Several papers have contributed partial answers this question. Li lieta
(021) show that mirror descent with an aggressive step size
rate. However, their analysis assumes the potential function is both mrongly-convvr and smooth with respect to some norm, and thus mainly limited to the l2 E2-geometry. For steepest descent with respect to general norm || || Nacson et al. (2019) prove that an O log ++ /T
maximizes the margin in an O
Ing.n T7/4
||. Mi-III-mm |l-margin maximization rate can be achieved with an appropriately chosen step size, but it is unclear whether can be further improved. In this paper, we provide the fastest known rates for margin maximization for generic optimization methods, through the following contributions:
First, we study weighted-average version of mirror descent with the squared ly norm blll 113 the potential for q (1, This potential function is strongly convex but not smooth. We show that, with an appropriately chosen step size, the algorithm achieves a faster
|| Il. margin maximization rate on the order of O
log log (q 1)f
We also further improve
the rate to O ((p)))
log T T
with more aggressive step size. When g = 2, the
algorithm reduces to average GD, and our rate (+
+ log n log
is a log n-factor tighter
72
than the O loga rate of the last-iterate GD Ji & Telgarsky 2.21).
Next, for the steepest descent algorithm with respect to the fy norm for q E (1, 2], we show the margin maximization rate can be improved from O loogn n +
to O
log n T(g-1)
vT
|| margin maximization rate can be achieved in two ways: a) mirror descent with Nesterov acceleration, or b) steepest descent with extra gradient and momentum.
Finally, we demonstrate that a even faster O log TT(q-13
The essential premise for our approach is that minimizing empirical risk (ERM) with generic optimiza- tion methods can be equivalently viewed as solving a regularized bilinear game with online learning dynamics. Within this framework, we design new pairs of online learning methods whose outputs (and, by extension, the outputs of the corresponding generic optimization methods) automatically maximize the margin. The convergence rates are determined by the time-averaged regret bounds of these online learning algorithms when played against each other, which turn out to be much faster than the worst-case O(L/VT) rate.

---

Wang et al. (2022b) were the first to draw parallels between Nesterov- GD for ERM and solving the bilinear game through an online dynamic. However, it was still open that whether this kind of analysis suits other GD-based methods. Moreover, the non-linearity of the mirror map in generic optimization methods makes analysis particularly challenging. In this paper, we reveal that the game framework can in fact encompass implicit bias analysis for range of generic optimization methods, and offer a more streamlined and unified analysis. Within this game framework, we derive several other results beyond those mentioned above:
By selecting suitable online learning algorithms, we obtain momentum- based data- VT
dependent MD algorithm with an ( + log logglog ) ||- llg ll--arggin maximization
7
rate, where Vr = Σi= llp. Pt- [] is the path-length of series of distributions on the training data pt. In the worst case, this reduces to the margin maximization rate of MD, but this can be much tighter if Vr is sublinear in T.
Apart from margin maximization rates, we also demonstrate the corresponding directional error, i.e., the bound on the fy-distance between the maximal margin classifier and the normalized output of the generic methods, which are also controlled by the regret bounds of two-players against each other. This kind of convergence rates are new for most of the generie methods. In general, we prove that the directional errors are typically a square-root factor worse than the margin maximization rates.
For our steepest descent, by setting the norm to the general norm || and the l2 fo-morm respectively,
can recover the algorithms and theoretical guarantees in Nacson et al. (2019); Ji & Telgarsky (202I) under the game framework. This implies that these algorithms can also be viewed as solving regularized bilinear game using online learning algorithms, offering a deeper understanding of the role of implicit bias in optimization methods.
Additional related work The strategy of solving zero-sum game using online learning algorithms playing against each other has been extensively studied, primarily through the lens of independent learning agents (e.g.. Rakhlin & Sridharan 2013 Daskalakis et al., 2018 Wang & Abernethy] 2018)
[ataageas[(019,99_.111 [2099] [ et al. 2022). contrast, our central motivation and challenge lies in identifying the exact equivalent forms of generic optimization algorithms under the regularized bilinear game dynamic. Our framework is also motivated by the line of research that employs the Fenchel-gand game to elucidate commonly used convex optimization methods (Abernethy et al. 2018 Wang & Abernethy| 2018; Wang et al., 2021b). However, our framework diverges significantly from these approaches. These works focus on the convergence of the optimization problem itself, while our framework emphasizes that the choice of optimization algorithm, which solely targets the minimization of empirical risk, has significant impact on maximizing the margin, which might view as an "algorithmic externality." Max-margin guarantees can not arise from convergence of the ERM objective alone, as there are typically multiple global minima in ERM minimization. Our analysis also considers an entirely different min-max problem than that of the Fenchel game (Wang) cet al., (2221b) Consequently, the correspondences we establish between optimization algorithms and online dynamics also differ. Finally, we note that previous work has also analyzed the implicit bias through direct primal optimization analysis (e.g.. Nacson et al. 2019 Sun al. 2022) or using dual perspective (e.g.. Ji & Telgarsky 2021 Ji et al. 2021). For the former analysis, it is unclear whether and how faster rates can be obtained. For the latter, it remains an open question how to extend the
Daskalakis & Panageas|
framework beyond l2- fa-geometry, which in some sense was the motivation for the present work. For more related work, we refer the reader to Appendix A
2 Preliminaries
In this section, we present our basic setting along with some standard assumptions and definitions.
Notation We use lower case bold face letters x. y denote vectors, lower case letters a, b to denote scalars, and upper case bold face letters A, B to denote matrices. For a vector x E IRd., we use d;; to denote the i-th component of x. For matrix A E Raxd, let (G.)) be its i-th row, (aa) the j-th column, and A(i.)) the i-th element of the j-th column. Vx Rd we use || || to denote a
general norm in Rd, |l ||. its dual norm, ||x||, the g-norm of x, defined as ||x||, (2 1i 119/9)
and q E (1, 2). We use || Ilp to denote the dual norm of n-nom,, where p E o0), + 1 1.
3

---

Solving the regularized bilinear game with online learning:
H1tt iitt p Aw ((w) WERK PEA"
Identify equivalent forms
Plug in regret bounds
Empirical risk minimization with generic optimization methods
Margin maximization rate: 7y 0 (CT) directional error: O (VCT)
Figure 1: Illustration of the game framework for implicit bias analysis. In Section 3 we show that solving regularized bilinear game with online learning algorithms (top box) can directly maximize the margin, and the convergence rate is on the same order of the averaged regret Or (right box); In Sections we prove that minimizing the empirical risk with a series of generie optimization methods (left box) is equívalent to using online learning algorithms to solve the regularized bilinear game. Thus, the implicit bias rates can be directly obtained by plugging in the regret bounds.
We denote B|l- the || ||-ball, defined as Bl--1 {x |||||||| S 1]. Vx, x'x'ss E Rd, define the Bregman divergence between and x' with respect strictly convex potential function Φ(x) as (x,xx') ) (xx x(x') v T (x -x)). For positive integer n, we denote {I...., n2 as [n]. and the (n 1) dimennsioa simplex as A". Let E' A + R be the negative entropy function, defined as E(p) E Pı log P;, Vpp A
Basic setting Consider set of data points S ((x(0) (x))), where x(() R is the feature vector for the i-th example, and yd E {-1, +1} the corresponding binary label. We are interested the optimization trajectory first-order methods for minimizing the following unbounded and unregularized empirical risk:
min L(W) W WERd
Σ r(w x0)
where Rd is linear classifier, r: R [+1] IR is the loss function. Following previous work, focus on the exponential loss, given by r(w x: exp(-yx w). We introduce the following standard assumption and definitions.
Definition (| (Il-Il-mrr)nn.. For linear classifier Rdd and norm ||- we define its |l-margin as
min y w (() (E(R)
min DTAN Aw
PEA"
(w)
[w]
||
where A = [ (1) ;..] Ruxd the matrix that contains all data.
Assumption 1. Assume S is linearly separable and bounded with respect some norm || - More specifically, assume Ewi.jl Bii-i s.t., w = argmax [w isi mingg]m) yf ( x w, whose margin 7( i-1) Y > We refer to wi-l as the || -IlImmaal margin classifier. Note that, for any E Rd, (w)) = and wiil are the same direction. Finally, also assume S is bounded wrt some dual norm || ||=, i.e., Vi E [m], ||x [|~ 1.
Definition 2 - |lMaargin maximization rate and || ||-directional error). Suppose Assumption is satisfied. We consider sequence of solutions Wi...., W.y..., and state that wt converges to will if either lim,-roc 7(w.) + 7/ or limy-roo ll w. || [[-1 - 0. We define the upper bound on l7 7(w:)) the ll-rgin maximization rate, and w.ll wi-pll ll the ||-directional error.
3 A Game Framework for Maximizing the Margin
In this section, we present a general game framework and demonstrate that solving this game with online learning algorithms can directly maximize the margin and minimize the directional emror

---

Protocol No-regret dynamics with weighted OCO for solving g(p, w)
1: Initialization: OL", OL". The online algorithms for choosing w and p.
2: for = 1..... T do
3: W; f OL"
4: OLP f- at (x()); Define (((-) g( (Wes))
5:
4- OLP:
6:
OL ott; (+):);: Define h+(+) = -9(:PP Pt)
7:
end for
8: Output: WT Σi= a.W.
Then, in Section we show that many generic optimization methods can be considered as solving this game with different online dynamics. As result, the margin maximization rate (and also the directional error) of these optimization methods are exactly characterized by the regret bounds of the corresponding online learning algorithms. We illustrate this procedure in Figure The game objective is defined as follows:
max min g(P, w) =p Aw ((w),
ERd A
where o (w) w| 2 is regularizer and ||-|| denotes some general norm in Rd. Following previous work (Wang et al. 2b 2022b), we apply weighted no-regret dynamic protocol (summarized in Protocol to solve the game. We first give brief introduction of Protocol [ and then present the theorem about the margin of its output.
Description of Protocol In Protocol the players of the zero-sum game try find the equilibrium by applying online learning algorithms. In each round t, the p-player first picks decision p.. and passes a weighted loss function to the w-player, defined
ael+(w) = (p, Aw +(w)) = (Pt w).
Then, the w-player observes the loss, picks decision Wx, and passes weighted loss function
(p) (p Aw, (ww))) a,g(p, w.).
to the p-player. Note that the order of the two players also be reversed. After T iterations, the algorithm outputs the weighted sum of the w-player's decisions: Wr ΣT a,W, Under this framework, we define the weighted regret upper bound of both players respectively as
Σ calo(p:) min
Σ anl((p) < Reg and Σ cale(ws) min Σ PEA t=1
cali(ww) S Regy.
wERd 2
Denote the upper bound on the average weighted regret by Cr = (Reg) + Reg
)/ /
1== dg. We
have the following conclusion on the margin and directional error of Wr. The proof of this theorem can be found in Appendix B
Theorem 1. Suppose Assumption 7 hoold with respect to some general norm || .
||. Consider solving the two-player zero-sum game defined in ( by applying Protocol Then Wr will have positive
margin on round T if Cr < 7- Moreover, as long as Cr S 4 we have
min AWT DEA"
4CT 72
27
(3)
WT
((w) is X-strongly convex with wrr ||. we have
8v2 CT.
WT
w
WT
Theorem shows that the output Protocol I denoted as Wr, achieves a positive margin when average regret Cr < z. In the following sections, demonstrate that with appropriately chosen
5

---

online learning algorithms Or always decreases with respect to T; in fact Cr + 0 as T + co. met for a particular value To, it will also be met for all T 2 Ty. Thereafter, Wr continues to increase the || |-margin and converges to the maximum |l -I-margin classifier, and the rate is directly characterized by Cr. Since Cr the average regret of the online learning algorithms, better bounds on Cr lead to a less stringent condition on large enough T. Finally, we note that the condition on sufficiently large
Therefore, once the condition C₁ I 1
also (explicitly or implicitly) required in all previous work on the non-asymptotic margin maximization rates of generic methods (Nacson
et al. 2019 Li et al. 2021 Sun et al. 2022). We refer to Appendix A for more details.
4 Implicit Bias of Generic Methods
In this section, we show that average mirror descent and steepest descent can find their equivalent online learning forms under Protocol | Thus, their margin maximization rates can be directly characterized by the corresponding average regret Cr. For clarity, we use V, to denote the classifier updates in the original methods, and w, the update under the game framework. Note that Theorem clearly implies that the convergence rate of the directional error is always a square-root worse than that of the margin maximization rate. Due to space limitations, we only present the margin maximization rates, while the corresponding rates on directional error are presented the appendix.
4.1 Mirror-Desccet-TTyee of Methods
First, we consider minimizing by applying the following mirror descent algorithm:
V: argmin n) (VL(v--1). v) + Dv vz-1),
VERd
where (v Vt-1) is the Bregman divergence between v and V:-1, and (vv) is strongly convex potential function that defines the mirror map. Note that since the feasible domain in is unbounded, we can rewrite the algorithm in the following form:
(V, = V+ " VL(ve-1).
In this paper, we consider weighted aveeagge mirror descent with the squared q-norm, i.e., ((w) [/l where g E (1, 2). and demonstrate that this optimization algorithm can enable faster margin maximization rates. The detailed update rule is summarized in the left box of Algorithm [
is worth noting that this type of regularizer is (q })-strongly convex with respect to -ll. and can be updated efficiently in closed form as below
for each coordinate i E [d], we have
Tt.i sign(u; b2 1 || 113 112-9 17. (I(v-)))):
(5)
2/,6 = sign(Or,)) 1o.,, 1- 1
We make few final observations about this algorithm: 1) Instead of using the weighted sum Vr, we v. could output the weighted average Ei without altering the margin or directional convergence
rate. This is attributed to the scale-invariance of the margin, i.e., Ve > O. w E Red, 7(w) (cw). The same argument applies to the directional error. 2) The use of the weighted average standard in the analysis of mirror descent (e.g., Section 4.2 Bubeck et al. (2015)) ). This paper shows that using non-uniform weights advantageous for achieving rapid margin maximization rates; 3) The per-round computational complexity of (5) is (dd, which is similar to that of p-mirror-descent of Sun et al.] (002)). However, we note that the p-MD algorithm of [un et al. (2022) does not need to compute the norm of the decision at each round, which could be more efficient in real-world applications where parallel or distributed computation is desired.
For Algorithm 1 we have the following theorem. We present its proof in Appendix C along with a more general theorem that allows a general configuration of the parameters T)t, 04 and 3r.
Theorem Suppose Assumption ] holds wrt || ||, norm for q E (1, For the left box of Algorithm i let nh Live-.y. For the right box, let or, = and 3 two boxes of Algorithm Maee identical, in the sense that VT Wr. Moreover, we have the average
B, - Then the methods in the
'This expression appears in (Section 6.7. Orabona 2019 and we reproduce it for completeness.

---

Algorithm I Mirror Descent [Recall (p)
(P, wx), and h4 (w) = -p(p,, w)l
1: for = 1,.... do
p-player: argmin a aul(-1(D) + DKL (p,
Vd(v;) ( -1--1))-VVVV VV(vv)
PEA"
w-player: W. argmin Σ/=1 ayky(()
3: end for
4:
Output: Vy = Eizitvi
Oulput: WT = Ei- O.W;
regret upper bound CT = 12gg) Therefore, the algorithm achieves a positive margin
T
4( +2 log n (log T+2) We have the convergence rate
when T is sufficiently large such that T
min P T AVT
+ 2logn)
(log T +
PEA
q-1
log log log T 1)22
27
= =
(6)
VT l1
72
and
g-1 + 2 logn) (log T 2)
VT
wii-k
8V2
=0
Vlog log T >2 1)v7
Vrlla
72 (a
T
9
The first part of Theorem 2 indicates that the mirror descent algorithm can be described as two players using certain cleverly designed online learning algorithms solve the regularized bilinear game in (2) More specifically, for the p-player, we propose a new and unusual online learning algorithm, which we call regularized greedy.
1 n
Pt argmin (xl-11()) BeD PEA"
P.
Essentially, in round f, the p-player minimizes the previous round's loss function, 4--1, plus regularizer round and the terms are balanced by the parameters or and Be. On the other hand, we select the follow-the-leader" algorithm for the w-player:
W; argmin
ayh,(w),
1=1
which returns the solution that minimize the cumulative loss so far. The + sign in the name is because the algorithm can pick the decision w, after seeing its loss function. This is an interesting and unusual design because the regularized greedy algorithm will clearly suffer worst-case linear regret for the p-player. Fortunately, for our specific case we are able to prove sharper data lata-dependent regret bound for the p-player as below:
T Σ 1=2
1)(g - 1) ||: - we-1ll, 11 log n log
Reg =0
2
Therefore, the dominating term (i.e., the first term above) of the p-player's regret bound can be canceled by the w-player's regret bound, given by:
Reg -0(-3 Σ l)(g
|w, w.-
Note that the w-player's regret bound is negative the corresponding algorithm used is clairvoyant, iee. can see the current loss l, before making a decision at round f. This ensures that sublinear (and more generally fast) rates are possible. Note that 3, and os will influence both the regret bound and the algorithm equivalence analysis, so finding the right parameter configuration that works for both non-trivial task. We make the choice 3r
which ensures both algorithmic equivalence
and sublinear regret bounds.

---

instead of Algorithm 2 Momentum-based MD [Recall (p) s(p, wx), and li (w) ((r, w)]
for 1,... .., do
w-player:
2: vQ(vi) (V)(v--)- VL(v--)
Wt argmin Eisl ashi(w) + aehe-1(w)
(MVVL((v-1) 17--1 V
p-player:
3: end for
Pi argmin acl((p) + (p,
4: Output: VT Σt 21=17 tv:
Oulpul: Wr E1 a:Wi
The second part of Theorem shows that the average regret Or of Algorithm I is on the order Therefore, by plugging in Theorem we observe that the margin shrinks on
of O log log (1-1);-T]
the order of y 0 log n log T 7- 1y7 and the implicit bias convergence rate is O log log T (9-11i Next,
we show improved rate with more aggressive step size the order of 0 T(vi)
[(ve) The proof of this result is given in Appendix
Theorem Suppose Assumption 7 holds wrr |I -lg- q E (1,2). For the left box of Algorithm
1 let 1)t JJ and let the final output be VT = Ei= F+I Vv. For the right box, let Os t, and
31 Se Then the two algorithms are identical, in the sense that VT = WT. Moreover,
A7, +1log log T +1+++1+2lgg
when T z
we have
min p T AVT PEA"
32
8(4 log log T 1 2 log
21
V l
TT - 1)
7212
and
VT
8/2 $ 22 T V (q- 1)T
8
log n log T + log n
Vrlly
wii-ls
7
Observe that the margin maximization rate in Theorem is O (リ-1) + O
log log
Com-
7272
pared (). it has better dependence on log and log
Finally, we focus on momentum-basee mirror descent algorithm, which is given in Algorithm 2 For this algorithm, we have the following guarantee.
Theorem 4. Suppose Assumption 7 holds wrt || lla-norm for q E (1,2). For the left box of Algorithm
2 let np 1[v;-1]' and îi 1(v.-1)- For the second box, let a4 tt and Bt ++1- Then the
methods in the two boxes of Algorithm are identical, the sense that VT = WT. Moreover, when
(8(1lgg n log T 20
we have
P
min p A
>T --
Dr
P:-1
|
32 log n log
27
(8)
[rrll
2- 1)72
272
and
VT V
8/2
ΣT |p:
P P |1
32 log n log
willl
72
2
- 1
7
The above theorem shows that, for sufficiently large T. the margin maximization rate can be data- dependent. Note that D |lp: PI- 27, so in the worst case, the bound reduces to the results in Theorem 3. but can become significantly better when Σ |p: P:-1 l small. We expect that when T' is very large, Pr will change very slowly we already know that the direction of Vir will converge however, turning this into a precise faster rate dependent on the original training data geometry, i.. A, is an intriguing open question.

---

Algorithm 3 Steepest Descent [Recall (p)) = g(p we). and h (w(w) = (Pr, w)l
for t 1,..., do
w-player: w, = argmin (61-104-1 Vhy-1 (W w)
2: 5:-1 = argmins (L(vi-1)
wERt
+D Dill-1p( W(-1)
||5|
Vi = Vi-1 + 11--18
p-player: Pt argmin Ei= agl((p) + DRL (p. PEA"
4: end for
5: Output: vr
Output: Wr - O.W,
4.2 Steepest Descent
Next, consider the steepest descent method under given general norm || For succinet description of this algorithm see (Boyd & Vandenberghe, [004]. For completeness, we have also described this algorithm in the left box of Algorithm 3 In each iteration t, the algorithm first identifies the steepest direction with respect to the norm || (Step 2). It then adjusts the decision towards this direction using specific step size vi (Step 3). After T iterations, the algorithm yields the final
iteration Vy. In the following, we show that an O [A+logn)
||||| marrinn maximization rate can be achieved when the squared-norm, i.e. bll 112 is X-strongly convex (e.g.. -ll - ll is (q I)-strongly convex wrt || (l,). The proof of this result provided in Appendix [ Morcover, recover the slower
O log n-tlog T of Nacson et al. 2019) rate a special case for norms that are not necessarily
strongly convex. Theorem 5. Suppose Assumption holds wrt general norm || and اlll 112 is X-strongly convex wrt I| Let n aul VLW.))l and d 01-1- Then the methods in the two boxes of Algorithm
I(w.)
à Then Cr 3 are are equivalent. in the sense that VT = WT. Moreover, let a: = 2-
3 +log
TA
Therefore, when T
A+4 log we have
An
min p AAT
P
+ 4 log
27
vrl
T2
and
VT
4v2
log
wii
S VXy²
|rl
TA
The first part of grrcoremmJlluiddaan the equivalent online dynamic of the steepest descent algorithm, which is also depicted in the right box of Algorithm 3 The w-player employs the standard online mirror descent (OMD) algorithm (Hazan 2016). while the p-player utilizes FTRL+ i.e., P, is selected by minimizing the cumulative loss observed so far, coupled with a regularization term. The crux of our algorithm equivalence analysis lies in evaluating the output of the w-player. For this, we initially prove that given d, = a. the OMD algorithm condenses to best-response (BR), that is, argmin ieth.i(ww.) We then prove that BR's output coincides with the steepest descent direction. The second part of Theorem shows that the average regret of this online learning dynamic
O A+log which leads the corresponding fast margin maximization/small direction error. We xT
note that the favorable average regret is made possible by allowing the two players to play against each other, rather than plugging in worst-case regret bounds.
4.3
Even Faster Rates with Accelerated Generic Methods
In the preceding subsections, we showed that, with suitable step sizes, steepest descent and average margin maximization rate. We now aim to derive even faster rates using two approaches, as illustrated in the top two boxes of Algorithm 4 The left box introduces a Vesterov-accelraation-be based mirror descent (Nesterov) 1988 Tseng 2008): In each iteration 1, the algorithm initially performs an extra update to yield (Step 2). then executes a mirror descent step with the gradient at v. (Step 3), and finally calculates moving average (Step 4). On the other hand, the right box depicts momentum camentum-bbsed steepest descent algorithm: In cach iteration,
nogg mirror descent can achieve an log n Iog

---

Algorithm 4 Accelerated Methods [Recall (xp) g(p, wt). and 1e (w() I(P:; w)]
for I...... T do Vi = +
for 1..... T do 2: = 8t,3g1 -1 - V
2:
3:
VQ(2i) = (7(()-1)- - Tp VL(v))
3: S = argmin s
4: V1 = B,,V, + 87,27
Vi Va-1 1/18t
5: end for
5: end for
6: Output: VT
6: Output: VT
p-player: P: = argmin PE A"
1= a;(((p) + axl(-1(()) + (p.(P.Po)
w-player: w. argmin
Ei=1 ashi(w)
Output: WT = Eiz a,W,
the method maintains a momentum term g: with an additional gradient (Step 2), then identifies the steepest direction with respect to g, (Step 3), and applies this direction to update the decision (Step 4). At first glance, these two algorithms appear markedly different. However, we show that with appropriately chosen parameters, they are actually equivalent, in the sense that they both correspond the online dynamic in the bottom box of Algorithm More specifically, we provide the following theoretical guarantee. The proof is given in Appendix
Theorem 6. Suppose Assumption holds wrt general norm || 11. and 111l 112 is X-strongly convex 2 wrt II- ||. For the left box, let Br,1 7,2 Bl,, 2(1-13 Br, 1, 31,2 TtI and L(ve)' For the right box, let 3r,3 1 Be, 3. 1/, Milss--ll. Bi.3 (4+1)
aV- -1 and
" = l|]g: ll.. For the bottom box, les e = E/. 0r L. Then all three methods in Algorithm are identical, the sense that VT VT WT. Moreover, when T 4v/2logn we have Vxy
minpea" P AWT [wrll
32 32log
-9- T2
and
VT |vlll
32 / x2
will
Remark Theorem 6 reveals that the two strategies implemented in Algorithm yield an optimal Ollogn// 2/()21²1) rate. It is worth noting that a similar online dynamic the one detailed in the bottom box of Algorithm was also considered by (Algorithm 5. Wang et al. 2022b). Nonetheless, there are some crucial distinctions: 1) Their work only demonstrated that this dynamic could achieve positive margin, leaving open questions regarding whether the margin can be maximized (i.e., converge to 7), and if so, what the margin maximization rate would be: 2) They only presented the online dynamic, without its equivalent optimization form. Finally, we note that, Theorem requires the norm to strongly convex, which is satisfied for, e.g. the n-norm when y E (1,
Conclusion and Future Work
This paper examines the implicit bias of generic optimization methods, delivering accelerated margin maximization and directional errors for average mirror descent and steepest descent. Our approach translates generic optimization methods for ERM into online learning dynamics for a regularized bilinear game, offering a simpler analysis and fresh perspective on implicit bias. Despite the effectiveness of the game framework in handling generic methods and accelerated techniques, presently holds some limitations: 1) the framework is currently operational only for exponential loss, making its extension to handle more general losses vital area for future research; 2) identifying algorithmic equivalence is nuanced and hon-trivial, and it is as yet unresolved whether this framework can elucidate other methods, such as the last-iterate of MD; 3) Finally, it remains to seen whether more advanced online learning algorithms are beneficial under our framework, such as parameter- free online learning (Orabona & Pái 2016 Cutkosky & Orabonal 2018) or adaptive online learning methods (van Erven & Koolen 2016 Wang et al. 2019 Zhang et al.) 2019 Wang et al. 202
10

---

Acknowledgments. GW was supported by ARC-ACO fellowship provided by Georgia Tech. VM was supported by the NSF (through CAREER award CCF-2239151 and award IIS-2212122. am Adobe Data Science Research Award, an Amazon Research Award and Google Research Colabs Award. JA was supported by the AI4OPT Institute, as part of NSF Award 2112533, and NSF through Award I11-1910077.
References
Abernethy, J., Lai, K. A., Levy, K. Y., and Wang. J.-K. Faster rates for convex-concave games. In Proceedings of the 31st Annual Conference Learning Theory, pp. 1595-1625, 2018.
Azizan, N. and Hassibi, B. Stochastic gradient/miirror descent: Minimax optimality and implicit regularization. In the 7th International Conference on Learning Representations, 2019.
Boyd, S. and Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004.
Bubeck. S. et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, (33-)):331-37,,000
Chen, S. S., Donoho, D. L., and Saunders, M. A. Atomic decomposition by basis pursuit. SIAM review, 43(1):129-159, 2001.
Cutkosky, A. and Orabona, Black-box reductions for parameter-free online learning in banach spaces. In Proceedings of the 31st Annual Conference Learning Theory, 2018.
Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In 10th Innovations in Theoretical Computer Science Conference, 2019.
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng. H. Training gans with optimism. In the 6th International Conference on Learning Representations, 2018.
Gentile, C. A new approximate maximal margin classification algorithm. Advances in Neural Information Processing Systems 13, 2000.
Gunasekar, S., Lee, J., Soudry, D., and Srebro, Characterizing implicit bias terms optimization geometry, In Proceedings of the 35th International Conference on Machine Learning, pp. 1832- 1841, 2018a.
Gunasekar, S., Lee, D., Soudry, D., and Srebro, N. Implicit bias of gradient descent on linear convolutional networks. Advances in neural information processing systems 31, 2018b.
Hazan, E. Introduction to online convex optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Ji, Z. and Telgarsky, M. Risk and parameter convergence of logistic regression. arXiv preprint 1803.00300 2018.
Ji, Z. and Telgarsky, M. Gradient descent aligns the layers of deep linear networks. In the 8th International Conference Learning Representations, 2020a.
Ji Z. and Telgarsky, M. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems 33, 2020b.
Ji, Z. and Telgarsky, M. Characterizing the implicit bias via a primal-dual analysis. Proceedings of the 32nd International Conference Algorithmic Learning Theory, pp. 772-804 2021.
Ji, Z., Dudik, M., Schapire, R. E., and Telgarsky, M. Gradient descent follows the regularization path for general losses. Proceedings of the 33rd Annual Conference on Learning Theory, pp. 2109-2136 PMLR, 2020.
Ji, Z., Srebro, N., and Telgarsky, M. Fast margin maximization via dual acceleration. In Proceedings of the 38th International Conference on Machine Learning, pp. 4860-4869, 2021.
Lai, K.-W and Muthukumar, General loss functions lead (approximate) interpolation high dimensions. arXiv preprint arXiv: 2003.0770 2023.

---

Li Y., Ju, C., Fang, E. X., and Zhao, T. Implicit regularization of bregman proximal point algorithm and mirror descent on separable data. arXiv preprint arXiv:2108. 068808,00..6688,, 2021.
Lyu, K. and Li, J. Gradient descent maximizes the margin homogeneous neural networks. In the 8th International Conference Learning Representations, 2020.
Nacson, M. S., Lee, J., Gunasekar, S., Savarese, H. P., Srebro, N., and Soudry, Convergence of gradient descent separable data. In Proceeding of the 22nd International Conference Artificial Intelligence and Statistics, pp. 3420-3428, 2019.
Nesterov, Y. On an approach to the construction of optimal methods of minimization of smooth convex functions. Ekonomika Mateaticheskie Metody, 24(3):509-517, 1988.
Neyshabur, B., Tomioka, R., and Srebro, N. In search the real inductive bias: On the role of implicit regularization in deep learning, arXiv preprint arXiv: 2014.
Orabona, F. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019.
Orabona, F. and Pál, D. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems 29, 2016.
Rakhlin, S. and Sridharan, K. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems 26, pp. 3066-3074, 2013.
Ramdas, A. and Pena, J. Towards a deeper geometric, analytic and algorithmic understanding of margins. Optimization Methods and Software, 31(2):377-391, 2016.
Soheili, N. and Pena, J. A smooth perceptron algorithm. SIAM Journal on Optimization, 22(2): 728 728-737,22 2012.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias gradient descent separable data. The Journal of Machine Learning Research, 19(1):2822-288 28788, 2018.
Sun, H., Ahn, K., Thrampoulidis, C., and Azizan, Mirror descent maximizes generalized margin and can be implemented efficiently. In Advances in Neural Information Processing Systems 35, 2022.
Telgarsky, M. Margins, shrinkage, and boosting. In International Conference on Machine Learning, pp. 307-315. PMLR, 2013.
Tseng, P. On accelerated proximal gradient methods convex-concave optimization. submitted to SIAM Journal on Optimization, 2(3), 2008
Erven, T. and Koolen, W. M. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29, pp. 3666-3674 2016.
Vardi, G. On the implicit bias in deep-learing algorithms. arXiv preprint arXiv: arXiv:2208.1259/ 2022. 2022.
Wang, B., Meng, Q. Zhang, H., Sun, R., Chen, W., Ma, Z.-.,, and Liu, T.-Y. Does momentum change the implicit regularization on separable data? Advances in Neural Information Processing Systems 35, 2022a.
Wang. G., Lu, S., and Zhang, L. Adaptivity and optimality: universal algorithm for online convex optimization. In Proceedings of the 35th Conference on Uncertainty Artificial Intelligence, 2019.
Wang, G., Wan, Y., Yang, T., and Zhang, L. Online convex optimization with continuous switching constraint. Advances Neural Information Processing Systems, 34:28636-288 28647, 2021a.
Wang, G., Hanashiro, R., Guha, E., and Abernethy, J. On accelerated perceptrons and beyond. arXiv preprint arXiv:2210.0937/ 2022b.
Wang, J.-K. and Abernethy, J. Acceleration through optimistic no-regret dynamics. In Advances in Neural Information Processing Systems 32, pp. 3824-3834, 2018.
12

---

Wang, J.-K., Abernethy, J., and Levy, K. Y. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization. arXiv preprint arXiv:2111.11309 2021b.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Zhang, L.,, Wang, G., Tu, W.-W., and Zhou, Z.-H. Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. ArXiv e-prints, arXiv:1906.1000 2019.
Zhang. M., Zhao, P., Luo, H., and Zhou, 7.-H. No-regret learning in time-varying zero-sum games.
In Proceedings of the 39th International Conference Machine Learning. 2022.
13

---

A Additional Related Work
As discussed in the introduction, the implicit bias of GD-based methods linear spreadable data with exponentially-taiee loss has been extensively studied (Soudry et al. 2018 Ji & Telgarsky
2018 Nacson al., 2019 Ji & Telgarsky 2021 Ji et al. 2021 Wang et al. 2022bj. For & nnormm
Telgarsky (2013) provides an O O /T/ margin maximization rate, and an ( convergence rate to a
sub-optumal margin. The idea of using the regularized game framework for analyzing the implicit bias of Desterov-accelerate
GD is firstly considered in Wang et al. (2022b). This idea is motivated by the smooth perceptron analysis of Soheili & Pena (2012), and the the Fenchel game framework by Wang et al. (021bb). The idea also inspired by the primal-dual analysis of & Telgarsky (0021) who discovered the relationship between the normalized gradient descent for the exponential loss and a smooth update of a distribution over data. Apart from the setting above, the implicit bias of GD-based optimization methods have also been studied in other cases, such as minimizing more general loss functions (Ji et al.) 2020 Ji & Telgarsky 2021; Lai & Muthukumar 2023), and deep
neural networks (Gunasekar 2018b Ji & Telgarsky| 22220 Lyu & Li 2020; Vardi 2022).
Compared with GD-based methods, the implicit bias of generic optimization methods for linear classification is less understood. Apart from the work summarized in the introduction (Gunasekar cet al. 2018a| Nacson et al. 2019 [i et al., 2021; Sun et al., (2022). the implicit bias of mirror descent also studied in regression problems (Gunasekar et al. 2018a| Azizan & Hassibi (019). We note that, as indicated in Gunasekar et al.] (2018a) and Sun et (2022), the analysis of implicit bias for
classification and regression are "fundamentally different". Apart from steepest and mirror descent, the implicit bias of other generic methods, such as Adagrad and Adam are also studied (Gunasekar
al. 2018a Wang et al. 2022a)
Discussion on large enough T Our Theorem Lindicates that ensure the margin be maximized, the number of iterations T has to be large enough such that CT < 2 We note that, similar conditions are also required (explicitly or implicitly) in other work for analyzing the margin maximization rates for generic optimization methods. For example, in the proof of Theorem 8 Nacson et al. (2019), in order to combine the upper bound in (53) and lower bound (54), one need to make sure the LHS of (53). i.c., the margin, is non non-negative, which essentially hinge on the condition that [og log'logg' similar to what is required in our Corollary In Sun et al. (0022), page 21, to 72
=
make sure the term
log be a constant, T has to be large enough such that m., the margin, goes mi
to co. In Li et al. (2021), the requirements for large enough T is stated in the main theorem (e.g.. Theorem 4.2).
Comparison with Wang et al. (2022h) As discussed in the introduction, our work motivated by Wang et al. (2022b). Compared with Wang et al. (2022b), we note that: Wang et al. (2022h) draws the connection between Nesterov-acceleruue through online dynamic. However, it was unclear whether this kind of analysis suits other gradient- descent-based methods, and generic optimization methods such as mirror descent/steepest descent was not addressed at all. We observe in this work that the non-linearity of the mirror map in generic optimization methods, such as mirror descent and steepest descent, makes the analysis particularly challenging. In this paper, reveal that the game framework can in fact encompass implicit bias analysis for a range of generic optimization methods, and offer a more streamlined and unified analysis. 2) Wang et al. (2022b) also proposed accelerated p-norm perceptron problem. However, they only demonstrated that the algorithm could achieve a non-negative margin, leaving open questions regarding whether the margin can be maximized, and if so, what the margin maximization rate would be; 2) They only presented the online dynamic, without its equivalent optimization form under ERM.
GD for ERM and solving the bilinear game
B Proof of Theorem 1
Define m(w) minped" ((p, w), Wr ΣT_ a following lemma, which shows that using online learning for solving the game defined in maximizes m(w).
Σt a.w, E a. Wr, and we introduce
14

---

Lemma 1 (Abernetty et al. (018)). Consider solving the game defined in with the online learning
dynamic defiend Protocol We have that Vw R
Reg + Regg
m(w)
(T)
Σ 01
Based on Lemma and the definition of m(-), we have
2
WT
W7
WT
m (WT) - m
Ei=1 at
=
min P PEA"
Li=1
T
at
Σi=1 at
WT
Reg.
Regr
7
11-11
E 04
(9)
1==
04
WT
WT
Reg + Regr
7
Σ1=1 a
-===1
1=1
which implies that
min P AwT PEa"
Reg + Reg
27
(10)
Wrl
Wr
The above proof follows the main idea Wang et al. (002bb.. Next, we turn to lower bound |Wr Il Note that since Wr (and also Wr) does not have simple explicit form, the the technique
for lower bounding the norm in (Wang et al. (002b) fails and we need to find a new approach. Let (x, y) {(x(9, ())) be data point. We have
Wr 2 ||]|||||| 2 yx WT 2 min p AWT: PEA
(11)
where the first inequality due to assumption that ||x|| S the second inequality is derived from the SScwcy-SShwarz inequality. To proceed, we need lower bound on the unormalized margin of WT. We have
Wr
WT
Wr
m
WT)
m
min PEA"
P
A
Σ aq
Σ aq
2
1==1
Reg + Reg
2 m (ywiHl)
Σ
(12)
Reg + Reg
min p Aw" |I z l PEA
Σ Qt
2
Reg + Reg
Σ 0z
where for the first inequality we apply Lemma last equality derived based on Assumption suggests that
and compare m(wr) with that of yw and the (the margin with is y, and [[w || = 1). 12)
Wr
72
T
72 T >
min p TAWr DEA"
2
+
Σ
(Reg + Reg
Σ
04
(Reg + Reg
2
ΣΣ
- Ot
2
==1
1=1
20
(13)
Note that, to plug in the lower bound of Wr, we need to ensure the RHS of (3) is positive. Notice that when 2² Et 04 2 (Regh + Reg
2 >
T
T
7
T
WT
ar - (Reg Reg
act
a: - (Regf + Reg")
a
2
4
1=1
[=1
15

---

Combining
100
and 13
we have
min AWT P
4 ( Regr)
4CT
(14)
Wrl
72 Ei=
72
Note that to apply
13 need
El= ar 2 (Reg) + Reg 2 0.
Finally, we focus on the distance between W and ii-ll for the case where O (w) ) is strongly convex wrt || Il. This part of the proof motivated by Theorem 4 of Ramdaa & Pena (0016), who show
[wr
that a variant of the perceptron algorithm can converge to the l2 "2-maximum margin classifier in an O(1/VB) convergence rate. We have
WT
W WT
Wrr
Wr
W
Wi-I
WT
WT
WT
7W 11-11 + 7w
|T |wii 7-1
[w]]
WT 7w
11-11
+ 17
|| |I|
(15)
[wrl
WT 7W 11-11 + I1l
WT
2 WT 7w |-
WT ||
where the first inequality based on the Minkowski inequality and the fact that [[ || Next. note that m (w) is A-strongly concave with respect to || |]. and yw i-1 maximize m((). This is because it is easy to see that the optimal solution of m ((w) always lies in the direction of wii and
we only need to decide the norm. Let c > be some constant, we have m [wwj] = cy 1 The function is maximized when % which implies that the optimal solution ?wiiii-- Combining these facts with Lemma D
we have
WT wwin m(rwij)) m(Wr) Reg + Reg
(16)
-== az
we have when 2 Σ T
Finally, combining the lower bound of WT proved in 2 (Regf + Regg) 0,
Oz.
T
22
WT
WT
00
Σ
4
4
1==1 at
1= az
1=1
so, combining the equation above with (15 and
16). we get
WT
8/ 2(Reg) Reg
|wrll
Mi-1
S
72 VAVV 04
(17)
C Omitted Proof in Section
Here, we present a more general algorithm framework (given in Algorithm 5) which allows different step sizes. In the following, we first state general theorem for this algorithm, and Theorems and 3 then given as Corollaries 2
In this section, we provide the omitted proof of Section 4.1
and 3
16

---

Algorithm 5 Mirror Descent (General Version)
1: for / , do
p-player: p: = argmin 04l1-1 + 3 DxL (p.
PEA"
2: v@(v.) = -
w-player: W: argmin 2j azh)(w) wER"
3: end for
4: Output: VT Et= Eist oz
Output: WT Ei= ayWi
Theorem 7. Suppose Assumption holds wrt || nla-morm. E (1,2). For the left box of Algorithm the 5 let Trt 1J For the right box, let 3e be E. for t L, $1 a1. Then the methods in
the two boxes of Algorithm 5 are identical, in the sense that Vr Wr, and Vs = We Σ. 2i=1 Moreover, the regret upper bound
a²
j=1 az(9 - 1)
Regf =2 22)
|| wi-1lly log
Be + 0n
ag(9 - 1)
2
1 as
Regy
||w, - we-1
2
1=2
Thus, VT achieves a positive margin (no smaller than 72 44 for sufficiently large T such that
4
Σ
T
04
t=
Eド 02(9
of
+ 2loog n
Σ
t=
T
1-1 1i=1
ar
0i
+a1(1+22 22g
(18)
After (18) is satisfied, the margin of VT is lower bounded by
4 (2>I
min p
AVT
+ log n2 21=2
+ a1 + 2 logn)
PEA
VTllg
22 -ラ=1
and the directional error is
WT
wii-
Wrllg
8
2
2
2
+ 2og Et=
+ +ai(1+ 2 log n)
2/
(q - 1) 1)
Next, show that different step sizes (decided by a:) lead to different implicit bias convergence rates. Firstly, we consider setting the step size т)- Vtlly, 15' which leads to a slow Ö (V bound.
Corollary 1. Let C4 =
1. Then the margin is lower bounded by
Vt
min p AAT P
((22) q-1
logn log T + 4log
q-1
(
1 22
27
[vrlly
11)
and
WT
wiil
8 72 /q
q-l
2 + logn
log T + 4 4og +
g-1 δ
4
1
Wrllg
VT
(q
2714
4((,2 Hlog Tog
when T sufficiently large such that VT
m-1
Ω
Next, we show that faster rate can be obtained with a constant ag, which implies Theorem
17

---

Corollary 2 (Theorem 2..
Let ar = 1. Then the margin is lower bounded by
min P AVT PEΛ"
9-1 + 2 n
(log T +
= -7
((g (011(11
1
27
VT lla
T2T
and
WT
8
9-1
+ +2log
(log T +
Wr
Wil
72 12
T
72 - (P(9-1)VV)
1( q- +2 2lggn)
when T is sufficiently large such that T 2
y²
Remark Note that, by setting a, according Theorem get 1/+ Liv. 1)> B1 and
3
T- which recovers the parameter configuration in Theorem
Corollary 2 shows that, with step size of order O
Algorithm 1 enjoys faster Ö (1-1)))7))
L(ve 1)
margin maximization rate when ?
log lognlogg log!
Next, we also considered using a even larger step
(g (g-1)>²
size. 17- I[ve-.) and recover Theorem
Corollary 3 (Theorem 3). Let a₁
Then VT
2 Vt. Σ
When 2
#1
+44 log log + 1+2 1o
we have we have
min AVT PEA
32
8(4 1og n log T 1 + 2 2logn) n)
27
(19)
| l1
72
1)
2222
and
VT Vr
8
8
log n log T + 2 log +
wi-lla
S /2
T
(q
1)T
7
7
Note that, when a2 t. we have ?e
1(v which recovers Theorem fixed and known before, we can set a₂ as T and get rid of the log term
Finally, we note that,
C.1 Proof of Theorem
We first focus on the algorithm equivalence, and start from the online learning framework. For w W-player, have
W. argmin wERE
aghy(w)
E aj
argmin wERl
a.pp Aw
|w/12
(20)
j=1
= |
Σ aaj A
AT. P.j
1 aj j=l
which implies that
v&(w:)
Σ a A A Pj Σ/=1 aj
1= v +
A P
Σj= 0j j=1
Σ/=1 aj
To proceed, note that
[ sign(w;; (w; 1 9-1
[w]] q-1
18

---

Thus, A4 > 0, cVD(w) = Vd(cw). Then, multiplying = Ej= aj on both sides, we get
1-1
V
W
jj
VΦ
W
Σ jml
aj
+ +aApp. P:.
On the other hand, for the p-player, we have
P
argmin a + BB, DKL p. m )
1
argmin
T P PEA" 3.
Aw, 1
Eps
Σ
Ps log
I
PEA"
Based on standard argument on the relationship between OMD with the negative entropy regularizer on the simplex (see, c.g., Section 6.6 of Orabona 2019). it is easy to verify that Vi E [n].t [T].
at exp(
2, x
W:-1)
Pt. -ー= exp( 11=yy00xx0 x
where Pt, is the i-th element of p.. Moreover, based on the definition of L(w), for any E Rd
VL(w) AT L(w)
exp( exp(-y(()x x1)) w) exp( -y x()) w)
which implies that
VL
Wi-1
A
P1
L
2i
W:-1
M
Combining the above equations and the definition of 8,
we get
2imt
[-1
1L
W Ei= 03)
V
W
aj
=
V
W
aj
f=1
f=1
L
W
ΣØ=1 |-1
aj
Substituting v. w. Σ}=1 aj. we get
VL(vi-1) L(v,-1)
V4(v)) v4(v.-1 0t
and WT = Et O.W; - 0. Vi. The proof is finished by replacing I(vi.))
with T)-
Σ
19

---

Next, we focus on bounding the regret of the two players. For the p-player, let p* min D aap' Aw, be the best decision in hindsight for the online leanring problem. We have PEA"
T aPP Aw,
T a.p " Aw,
Reg.
T
1 Pt: nt )
T
T - -w-1) SAT Aw, + Σ app. A(w. a.p,A(W.
Σ
a:p; Aw + BeDKL
Σ
app
T
1
B,DD
Pri
1=1
B.D (p 1)
atP arp"
T Aw
Σ
ap t TT Aw, E oap, A(w, -w--1)
Pr. -
B,D E
n
T
T
T
Σ
a&p' A 1(W-1-W/)
Σ
a.p. A(w; - -w--) + 2log n Σ
3c
1m1
IA
T
T
T
0 |////=11 - -w)lle +
we-1) + 22olog n
8
1=1
1=1
0r arl|A(wr---W)) wi)l + +2 n
3
1=1
T
2
0x argmax :E|u]
y (0xx()(((--)))) w.))
+ 2 2og
T
2
arl wellw:-1= weela + 2 2logn n
Σ
3z
t=1
t=l
2
arl arll [ell:;-1--a wello 2 2log n
B: + a1 w/l/
t=1
5
T
2a
ay - 1)
T
2 2
22
|| 10--ww,, w.-1ll 2 log n
3, + a will
2
aj14 1)
2.2
1=2
1=2
(=1
T
a?
T
jj=1
1-1
0g
(q
T Σ
2
+
- w log
B. + 01 l|
ag - 1)
2
1=
122
1=1
(21)
Here, inequality (a) is based on the optimality of Pt. inequality (b) is due to the fact that the negative
entropy regularizer upper bounded, inequality (c) because of the Hölder's inequality, inequality
(d) is derived from Pt, D A", inequality (e) is based on the Hölder's inequality and ||x I 1 for all i E [n]. and inequality (f) is based on Young's 's inequality:
20
1 ag - I| w 12
Σ Callwwi1-- wellg Σ
2 j=1 03
2.2
1=2
E alle-)) as the constant of Young's inequality. Finally, note that [VΦ] (A (1). so based on the property of p-norm, we have
where we pick
a1 willallo 111 ail [V4 (A p1)lla ail|A pıll> S a1.
20

---

For the w-player, note that (w) is (q 1) Itstrnngyy convex wrt the || llg-norm. Thus, based on
Lemma 3
we have
T
(9-1)
as 1|w, wor--w-112
Reg
(22)
2
C.2 Proof of Corollary 1
Note that Cr S _ is equivalent to 1 ΣT a4 2 (Regf + Regg). We have + 0g
z E t 2
T 22 VT, and
T
a
at
Reg + Regy
2
+ +22lg
+ +ar + +
1=
j=
05(1 1)
1 1=2
i=
04
1/t
1/v2
2
>
+ 2lg
+ 11+ 2
t= (9
1) E} 1/v5
(23)
2
( 1)tvt-1 logn n Vivt - + 2logn
2
<
(log T + 1) + logn(log T + 1) + 1 + 2 log
0
2
4
<
+ log n T + 4logn n +
q
9-1
9-1 1
Therefore, Cr $
2-
4 when
4 ((221 2 + log n log T + 4logn n +
1 9-1
72
and in this case
min p A
AVT
4 ((12) log n log T 4 log +
4
9-1
(24)
27
VTll,
T2VT
C.3 Proof of Corollary 2
We have I Et= 0+
TT and
a
Reg Reg
2 Σ
+ 2lg
+ + (1+ log
j=1 02 1)
1=2
-i=1
1
1
2
+ +2logn n
+ 1 2ogn
(t 1) 1)
(25)
T-1
1 + 2 log n +
+ +2 n
1-1
x ( 2
+ 22llgg m
(log + 2).
9-1
72 Therefore, Cr < 4 when
4
+ 2logg)
(log T 2)
9-1
T >
22
21

---

and in this case
min P T AVT DED
4 $
2 logn n)
(log T +
(26)
27
T2
and in this case
C.4 Proof of Corollary 3
We have 3 ΣE 04
x(1+))
22 T and 8
T
T
2
at
+ log
00
+ ta + 2 log n)
1=2
Σ j=1
a,l9 - 1)
1=2
ii=
ai
2
Σ
t(t 1)(9 -1 + 2 222og
21a
21.
1 + 2 2log
(27)
t(t
1)
1=
t=
8T
+ 4log log I' + 1 + nog
9
Therefore, Cr < 1 when
log n log + + 2 2log1
T2
72
and in this case
min pl T AVT PEA"
32
8(4 lo log T 1 2 loggn) n)
(28)
21
V l1p
72
722
C.5 Proof of Theorem
4
We first focus on the algorithm equivalence. We have
We = argmin wcRd
a.P. Aw - Aw
| + Σ ag
1=1
(29)
-[
Σ A=1
A;A pi a.A D 1
Ei=1 O3
So we have
1
VΦ((w)
A;A p. + A P:-1
Σ
0:
t-2
1
a3
Σ
A Pi + a PC-2) + a P + + ( - PI-2)
Σ
E11 a
1
P A - -Pi-2)
Oi
(b(w)-))+aaA
E
ag
(30)
Therefore, we have
1-1
V
W
=
VΦ
Wi-1
Σ
ai
+ a T Pt-1 a--1A (p--1 Pr-2).
(31)
1=1
i=1
22

---

On the other hand, for the p-player, we have
(D. p. n )
P argmin (1 DeL PEA"
Based on the relationship between OMD with the negative entropy regularizer on the simplex (Hazan 2016), it is easy to verify that vi E [n].t E [T']
exp(
x (1) we) 21 y x()) ww))
Pts
72 j=
exp(
which implies that
VI.
de We
A A
P:
21 De
Combining the equations above and replace Σ Wg with Ve, we get
VL(v(-1)
VL((v-1)
VL(ve-2) [(v(-1) T(ve-2)
Vo((v) vV(vv-1) 04 T(Vx-11 0t-1
The proof is finished by setting 04 = f. Next, we focus on the regret. For the w-player, Note that he(w) is (4 ))-strongly convex wrt the || no-mo.. Let W, argmin
E (w);(w). Then, based on Lemma have
WERd
T
Reg W
Σ ar (We(w:) - -We(We+)) - 1w + he-1 (We+())
tml
Σ 1= 0: -11) l| - w
t=1
r
Σ xi
azly - 1)
(p Pt-1) A(w, w.t1)
Σ
|| Wet1ll?
2
2 ailg 110--11 1) |w, - we+ill
Σ
Tall(P: - p:-1) Alpp//w.- wet1lla
(32)
T
af
Diml
a; 1)
A T (p: - 11
w. - w 112
Σ 1=
0:19 - 1)
2
{=1
T
E 1= a:(q - 1)
|w - w
1=1
T
n Σ
(pr, - Po-
2(g - 1) [=1
E O
i=1
Σ
| 1p:-pe P
2(q -
Ei=
where the first inequality is based on Hölder's inequality, the second inequality is based on Young's inequality, i.e.,
a4 aull(p: - -P--1) Alp h Worllly
(33)
a3
Eim ailq 1) l| we+1l13
2 _1 i= anl9 -1 1) |AA (p: -P--
2
1=1
23

---

For the p-player, we have
T Aw: min arp Aw,
a:Pi
T
Σ (a:P; Aw; + 3KL
Pt. =
min
a&p
Aw, - Σ
BrDE
Pri 1 pm!
(34)
n
pEd
t=1
1=1
T
T
< 2
Be log nt = Σ
a1
log n.
1=1
1=1
1=
O4
Finally, we focus on the margin and implicit bias. Since a; = t, for the w-player's regret, we have
T
Pr Pe-PP--lll PI-
Pt 11
2(g 1)
t=1
1=
a2
(9
1=1
and for the p-player, we have
Σ
Ott log S log 7 log n.
Ei
Following Theorem
we have the margin and implicit bounds when
T
T(T+1)
T
4
27
2
4 log n log T+
2
72
(q 1)
(35)
4
4log n log T
2
Pr P.-
(9 1)
since the RHS is exactly * (Reg? Rega))
D Omitted Proof in Section 4.2
In this section, we provide the proof related to the steepest descent algorithm. We first restate Algorithm 3 which is presented in Algorithm Here, provide two online dynamic under the game framework. They both are equivalent to the steepest descent algorithm in the left box, in the sense that Vy Wy- The left one is good for recovering the results in Nacson et al. 2201)) while the bottom one is more suitable for analysing our accelerated rates.
We first recover the results of Nacson al. 2019 in Theorem 8 and then proof our Theorem
Algorithm 6 Steepest Descent [Recall (p) g(p. we), and (w(w) = -g(Pi, w)]
1: for = I,..., T do
2: Sc-1 Argminnsssss VL(v;-1)
p-player: pt = argmin Σ (,bs (p. DEA"
3: V== ===w V+-1 = 16-18-1-11
w-player: W. argmin -argminwwse-ahhwww ashe(w)
4: end for
Output: WT -IT a.W:
5: Output: VT
w-player: w, argmin (5.- (5.-104-1 Vh,-1 (Wr-1), w) ) D D211112 (W,, w:-1)
WERd
p-player: P: argmin Ei= (pl(pp) + DKL. (p. 1)
A
Output: Wy Et= O.Wi
24

---

Theorem 8. Suppose Assumplion I holds wri general norm ||- Let or VL(W:-13] Then, the methods in the top two boxes of Algorithm 6 are equivalent, in the sense that VT WT. Moreover, let at J.. Then Cr log n+2 log Therefore, when T is sufficiently large such that
L(We-i)
VT
VT 20log++2 1+2)
we have
7²
min p AWT
PEa
4(2 + logn + 2 2lg T) -2VT
(36)
Wrl
The first part of Theorem 8 shows that the steepest descent algorithm can be seen as an online learning dynamic where the in each round p-player performs the standard algorithm (Hazan, 2016). while the w-player uses best-response" it picks the decision by directly minimizing the loss of the round. The second part of the theorem
(Wang et al., 2021b), meaning
shows that the margin convergence rate, which recovers the y - [oggntlog vT rate Nacson et al.
(2019), while the convergence in terms of distance is new. Note that the strongly convex condition is not required for the margin maximization analysis, but is needed for the distance convergence
analysis. Next, we restate Theorem where improved margin maximization rate when the strong convexity condition is met.
Theorem 9 (Restate of Theorem 5 Suppose Assumption 7 holds wrt a general norm ll 1l, and
I11 -12 is >-strongly convex wrt || Let 1tt au L(W,))l Then the methods in the first and third
L(we)
boxes of Algorithm 6 are are equivalent, in the sense that vT = WT. Moreover, let ai = 3/. Then n Therefore, when T>
CT = TA
A+4log
we have
Any
min AVT peA
A 4 4lgg and
8
+ 2 log n
Vrl
TT
v
i--1
I
Xy²
TA
D.1 Proof of Theorem 8
We first focus on the algorithm equivalence between the top two boxes. Based on the relationship between FTRL and EWA (Orabona 2019), one can verify that
exp( x0)) Ck=1 acww))
Pt.
2i=1 exp( ( x() (E 0g wx))
Combining with the definition of L and w., it implies that
V ((W A A Pt:
L (W::1)
That is, VI(W,-) - L(W:-1)A p.. Let 8; argmin s||s1
VL(We-1) L(w.-1)
Note that, on one
hand, we have
VL(Wi-1) argmins VL((w-1). L(W,-1)
argmins |
(37)
|+
where the second equality is because because the argmin does not change if we scale the objective functions. On the other hand, we have
VL(W(-1) argmaxss T VL(WE-1)
(-
argmins s |
L(W:-1) |
L(W
(38)
To proceed, we introduce the following lemma.
Lemma 2. Let ||
be any norm in Rd.. Let a Rd, and
s = argmaxs' 'Ta a.
(39)
|S
Then
1 -a x x
|a|| argmin xcRd
(40)
25

---

Proof. We first focus on (40). Note that the objective has two terms. For the first term, based on Hölder's inequality. have
|||| |x||-
Let | c, where 0 constant, then the equality is achieved (and thus the first term of the objective function is minimized) when
argmin a argmax 'T ||
(41)
||
In this case, for the objective function of (40), we have -a x + _ =| + _.2. It's easy -axx
to see that the objective function minimized when c = ||a||.. The proof finished by combining 339 and
This lemma shows that the best response direction (under our game) the steepest direction. Thus, we have
1 Pc Aw + 2
VL(W:-1)
I(We-1) + 1 /w/2
argmin
|w|2 argmin w
wERd
WERd
VL( (T(w--1)
argmin WERd
+ ||wl1
(42)
L ((W(-1)
VL(wi-1)
argmax w ||
L (WW 81-
L(W,-1)
where the first equality is based the updete rule of w, at the right box of Algorithm 6 the final inequality based on Lemma [ (38). Note that, for the first equality, we dropped a as it is scaling parameter and does not have influence argmin. Thus, combining with (37). have
V (L(W,-1)l4 1).
T((w-1) St (VL(W--IIl argmins LWW(W:
WF
(I((w-11)
||||S1
Finally, we have
[VL( argmins T VI((:-1). L(W:-1)
W. W o.W; = W. + ot
||
VV الll with ne, and noticing We can finish the first part of the proof by replacing w. with vs, ag L(W:-1) argmin/s/lss1 s VL(W.-1) is s;-1-
Next, we study the regret bound. Note that the p-player plays the FTRL algorithm on the simplex with 1-strongly convex regularizer DKL (p, 1)) (wrt -norm). Therefore, based on Lemma 5 the regret can be upper bounded by
T
T
Σ (pli(p:) Σ apl((p)) < log n +
Σ
a A T well
t=1
T
(mxx (0) wel
logn Σ
(OT (0T wil (TT)))))
max FEn
t=1
T
loog n +
//wrll
t=1
T
logn Σ
||A T
pell
log + log + 2,
(43)
where the equality is because
V (w) L(w,)
(L(we)
[wll
L(w.) = ||A prll..
On the other hand, the w- w-player uses the best response* algorithm, and one can easily observe that the regret is upper bounded by 0. Finally, we have ΣT
ΣT v 2 VT.
26

---

D.2 Proof of Theorem 9
We first focus on the bottom box. For the w-player, we show that, if we set 6,-1 0r-11
then this
OMD algorithm is equivalent to the best response algorithm.
Specifically, note that ((w) 2 w/ll 2 is now X-strongly convex. Thus the corresponding mirror map is well-defined and unique, and the function (-(() is invertible. Therefore, the solution for best response
W, argmin 14 argmin h4- (w) VΦ (A- Pt-1).
(44)
On the other hand, since the w-player uses OMD, and the decision set is unbounded, we have
(d((w:) = ( - 10-1 -he = ( A P:-1 vd(w:-1) = A P1-1-
(45)
Note that 6 1. Combining and (45) and BR (at round 1) here are the same. We use
draw the conclusion that w, and w.
identical, which shows OMD (with ó the BR form the algorithm equivalence analysis, and OMD form for the regret analysis.
Next, we prove the algorithm equivalence of the left and bottom boxes Algorithm 6 similar to that in Appendix [.I] The difference is that the order of the w-player and the p-player is switched. Firstly, For the p-player, based on the connection between FTRL and EWA, we have
The arguments
)) exp
(-g02(00
Σ a j=1
=exp(-y/0 (-y(0x(0T
Pt. OC exp
Combining with the definition of L, it implies that
VL(w::)
Pr
L(w:)
That is, VL(W,)= = -LW.. Pr. Let
V.(w.)
argmax
argmin V..(W.). ||a 121
(46)
L(w:)
|
Combining the first equality in 46) and Lemma
we have
[L(())l L(W()
VL( L(W:)
P. Aw + 1
St
argmin w weRd
//| argmin weRd
o |1ll/p
W1+1
Thus.
(VL(W.-))l argmins (L(W--1)) ||
W. L( (WW-1)
T VV((w-1).
Finally, we have
|VI(W:-)]ll argmins VL(W,-1). L(W,-1) ||
W. W a.w; W. +
|V( with 7h-1, and We can finish the first part of the proof by replacing w, with Va, ar L(W..1) argmin s (L(W..) with s..
Next, focus regret. For the w-player, it uses the OMD algorithm. and set the initial point
= 0. Note that we fixed for all f, and thus step size 8,-1 o.. X
4 is also fixed.
27

---

Therefore, Lemma 7 can be applied. Define
argmin
E 1t=1
(wh)(w), we have
WE3d
7
(w.) - min wER4 t=1
aph =
Σ
(w))(
Σ
t=1
t=1
{u
dag
The
6
X
T
a28
|| pr + Vo(w))l1
6
(u)
T Σ
af8
|| Pt + A 11 AT
8
t=1
(47)
= o7 ( + Σ
ag
A + A A p--
X
t=1
T
n
= ar0(u) +
Σ
at
Σ
(pr.i P1-1,))
A
1=1
i=1
S aa7 + Σ at
Σ Pt. - 1et-PP-11 Po-1,ol
T
at
S < +
|p:
1=1
where the second-to-last inequality is derived using triangle inequality and the assumption that ||x l]. is upper bounded by 1. Next, for u, note that
Σ at |w|
argmin weRd
awh+(w)= argmin wEBd
E
aP,, Aw
(48)
1 2 w/ atP; Aw +
argmin WERd
Et= Ot t=1
Based on Lemma
we have
T
u
AT
ΣJ at (=1
atpr
8,
where
argmaxs s |
T
A
Σ
o
/==1
t=l
Therefore,
T
(u) = 2 ||ll
A
o.P, 2'
Σ where the inequality is based the triangle-inequality and the assumption that the dual of data is upper bounded by 1. Finally, for the p-player, since it uses FTRL*, based on Lemma we have
2
t=1
T
T
1
Cadi(p)) - Σ lc(p') < logn
Pt 1
[=1
To summarize, and let a, = 2, we have
Reg + RegP
+ log
TX
1= 04
28

---

E Proof of Theorem 6
We first focus on the equivalence between the left and bottom boxes of Algorithm 4 similar to the proof of Theorem 7
For the w-player,
we have
Σj Oj
argmin WERd
[yyh(()==
argmin wERd
osP3 Aw +
|w|
(49)
[
1
Σ
ajJ Pj)
Σ Ej=1 a3
j=l
which implies that
1-1
vo((w)
j= aj
7 (w(1- +
at
A A Pt.
2j=10 aj
2j=1 aj
and thus
[-1
V
W
02
VΦ
W
Σ
a P +
j=1
j=1
On the other hand, for the p-player, since it performs Optimistic FTRL on a simplex with the negative entropy regularizer, we have
[-1
Pt, O exp
-C
Σ
a;W; + +a
x
(50)
(W a0 x)))(0)
exp
which implies that
VL(wi-11 -A ATp.
Pr.
Leww- co,,
Let 2, W. Ei ai then we have
VL(cW(-1 Σ.
cay 21 1)
VL(cW,-1
VΦ (Z,) V (zi-1)-a1 L(ow,-1 - ca.w1-1)
VΦ (ZI-1) a:
L(ewi-1 +
21 2(-1)
E. ai
Finally, notice that Wi = Wt-1 + a.W, = W.
Ei 21 The proof finished by replacing W.
with Ve, W, with
2. Σ1 CW:-1 + ca/ with v., configuring Br, = c= 3.- S/ = Σist a3
शリー 82 1, 822,1 a - 1/:
L
Next, we focus on the equivalence between the right and bottom boxes. Note that for the w-player, we also have
Ej=1 aj
W. argmin WERd
(y))(w)= argmin wERd
a,p, a,p,,A Aw
|
f=1
(51)
argmin wER
Σ asp, Aw
2 |w|l2
Σ/=1 aj 3=1
Let
Σ a Pj
S
argmaxs ||
Σ110 aj j=1
Based on Lemma 2 we have
A Pj
8t Wt
E/=1 0j
1=1
29

---

Next, let ------1 Ei-1 E/ a,A Pj.
Ppj. we know
g:
Σj
8: +
Σ 2j=1
at
A Dt)
For the p-player, it is clear that due to the optimistic term, we have
V car A.p. L(ew,-1 + ca,,
To summarize, and let 0₁ = 6, we can conclude the proof by the following algorithm:
2 VL(ew,-1 c(W,-1)
VL(cW,- + g (l,8;))))
g: + 81-1 + ++ L( + ctwc-1) ++ 18-11-1
Be-1 + t+1 L(ow,-1 + at gt-1 1[11)
= argmax -s argmin'' gr, |
||
W; W + +f|gelll.s)
and let 3r,3 [ Be, 3, 3/,1 Ar 11, 3i (++1)((A, -0-- +1,,0-11)) 1/1
-||g:ll..
Finally, we focus the regret bound. For the w-player, note that d(w) is X-strongly convex with respect to || Il. Thus, based on Lemma we have
A(t 1)
Σ a (w)) Σ achh(w)
Wi wo-1l13
(52)
[=1
On the other hand, note that c 2. so based on Lemma
8
we have
T
T
T
Σ (cl((p)) Σ aal((p) I
4log n
Aw.
- Aw.
8
4log n
+
X
T
max i6/n]
Iy (
(T) (w: - wo-lll
(53)
8
t=1
4log
X
w:
w
8
It is easy to verify that e ((t-1) 1) for 2 2. So to summarize we get
8 8log
Cr
X72
The proof can be finished by plugging in Theorem 1
F Regret Bounds for OCO Algorithms
In this section, we provide standard regret bounds for Follow-The--Leader (FTL++), Opti- mistic Follow-The-Leade (OptimisticFTL), hallow-The-Rggulaziiee-LLaa (FTRL), Follow-The- and Optimistic
(Optimistic FTRL).
Lemmas 3 5 and 0 are based on Lemma of 3 of Wang et al. (2021b), and Lemmas and comes
from Theorems 6.8 and 7.35 of Orabona (2019).
Lemma 3. Consider weighted online learning problem with series of X-strongly functions fi...., fr. and a series of corresponding parameters 01,..,,TT. The FTL algorithm, given by
24 argmin alf((z). ZERd
achieves the following regret bound:
T
T
A Ols
Vz Rd
alf(lz) S
[z, 2, 2.-1 11?.
1=1
30

---

Lemma 4. Consider weighted online learning problem with a series of X-strongly functions fi.....fr fr. and a series of corresponding parameters a QT. Let 2, argmingERs Ei=1 (z),(z). Then, the Optimistic FTL algorithm, given by
2, argmin Σ axfi(z) aasf--(())
xER
achieves the following regret vz Rd:
T
Σ arfi(zi) Σ a(f((z)
t=1
T
X
L i=
0i) Zt
at (fr(zz) f((2(41) - f(-1(2++1)
21+1
2
Lemma 5. Consider weighted online learning problem with a series of convex functions fi..... fr. and a series of corresponding parameters . OT. Let R(z)) be a 1-strongly convex regularizer wrl || The FTRL algorithm, given by
argmii + ZER 1=1
achieves the following regret bound:
T
Vz E Rdd. Σ Eosse(ze) - Σ (rse(()) S R(z) + 2 of (Z)
Lemma 6. Consider weighted online learning problem with a series of convex functions Ju...., Sr. and a series of corresponding parameters 01,.... QT. Let R(z) be a 1-strongly convex regularizer wrt 1|. The FTRL* algorithm, given by
2: = argmin
aaf((z) + R(z),
nERd
achieves the following regret bound:
T Yz E Z, Σ (afi(zz) Eaif(l)s
R(z)
T 1
- t=1
|zz 2, 2111
(54)
Lemma 7. Consider weighted online learning problem with a series of convex functions fi....,fe fr. and a series of corresponding parameters ai...., 0T. Let ((z) be 8-strongly convex regularizer wrt - Let Zo E Rdd be the initial point. The OMD algorithm, given by
{ (Z naa-1 fi
achieves the following regret bound:
T
- azf(()) (z;
1
T
Vz RRd.
nat V
3
t=1
t=1
Lemma Consider weighted online learning problem with a series of convex functions fi.... fr and a series of corresponding parameters o.,,..., Orr- Let R(z) be a 1-strongly convex regularizer wrt || and (z(z)) be the optimism term round t. The Optimistic FTRL algorithm, given by
1 aafi(z) arbi(z) + R(z)) 7)
argmin ZERd
achieves the following regret bound:
T
R(z)
T
|0 f(()) - as (1)))1
Vz E Z, Σ aif((z))
Σ azf((z)
(55)
n
2/n
t t=1
31


Reviews:
[{"review_id": "utz0igxZla", "reviewer": "Reviewer_bnuX", "summary": "This work introduces a novel method to derive margin maximization and directional error rates for generic optimization methods. The method consists in finding a reformulation of the regular optimization as a minmax bilinear game. Rates can then be derived using online learning techniques. The authors demonstrate (Thm. 1) how solving a min-max regularized bilinear objective using online learning is maximizing the margin. They also derive (Thm. 2,3,5) the minmax formulation of mirror descent and steepest descent. Using their method, several new margin-maximization and directional error rates for mirror descent (average iterate) and steepest descent are derived. Moreover, rates are also derived for accelerated methods (Thm. 4 and 6). ", "questions": "What would it take to remove the $\\log(T)$ term in the $\\mathcal{O}(\\frac{\\log n \\log T}{(q-1) T})$ for mirror descent? \nFor mirror descent, what is preventing the analysis to be extended to the last iterate? \n\nWhat would a comparison between your mirror descent rate and existing GD rates look like in the average iterate regime?\n\nDo you believe a similar approach could be used beyond the exponential loss? ", "limitations": "Limitations have been discussed in the conclusion. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality & Significance: While not being entirely familiar with all the prior works, I find the main idea presented in this paper novel. The proposed rates are improving upon prior works and the approach seems to be able encompass a wide range of optimization techniques, making it a significant contribution in my opinion. \n\nClarity: I found the paper easy to read despite its density. Some small typos: in Figure 1, this should be max min and not max max. ", "weaknesses": "The authors ask the question whether generic optimization methods can achieve faster rates than GD. It seems the proposed rate for steepest descent is matching the GD rate, but the question is still open for mirror-descent. It is unclear how to conclude for mirror descent as you are deriving an average iterate rate that is difficult to compare to existing last iterate rates. Usually average iterate rates are better than last iterate rates. \n\nIt is unclear how good those rates can become. Is there a lower-bound you could comment on? \n\nThis work provide a unifying method to obtain margin maximization rates for linear models with exponential loss. It is unclear how the approach could be extended to different losses. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are profoundly grateful for your positive evaluation of our work and your detailed, constructive feedback. We address some of your specific inquiries below:\n\n>What would be required to eliminate the term $O(\\log T)$ in the $O(\\frac{\\log n\\log T}{(q-1)T})$ for mirror descent?\n\nWe appreciate this insightful question. Following the proof structure of Corollary 3, if we fix the total number of iterations $T$ in advance, we can set $\\alpha_t$ to $T$, thereby eliminating the $\\log T$ term. However, as it does not make sense to fix $T$ in an optimization application of online learning, we set $\\alpha_t$ to either $1$ or $t$, both of which introduce a $\\sum_{t=1}^T \\frac{1}{t}$ term, resulting in the $\\log T$ factor. We will elaborate on this point in our revised version.\n\n>Regarding mirror descent, what hinders the analysis from being extended to the last iterate?\n\nThis is an excellent question. At present, the primary challenge lies in the non-linearity of the mirror map, namely $\\nabla \\Phi(\\sum_{t=1}^Tw_t)\\not=\\sum_{t=1}^T \\nabla\\Phi(w_t)$. While the equality holds for $q=2$, it does not when $q\\in(1,2)$, posing difficulties for various aspects of the proof such as obtaining a lower bound on the weighted sum of $w_t$ and proving algorithm equivalence. We discovered that by allowing the p-player to implement a specialized algorithm (namely, regularized greedy as defined at the bottom of page 6), we can derive a weighted average version of MD via algorithm equivalence analysis, and the issues mentioned earlier can also be addressed in a nuanced manner. We will provide a more thorough discussion on this issue.\n\n> How would a comparison between your mirror descent rate and the existing GD rates appear in the average iterate regime?\n\nThank you for the question. When $q=2$, our average MD corresponds to an average version of GD and exhibits an $O(1/T)$ rate, which is similar to the optimal rate of last-iterate GD. Conversely, when $q=2$, our last-iterate steepest descent algorithm also simplifies to last-iterate GD, thereby demonstrating that our framework is versatile and can be used to analyze last-iterate GD.\n\n> Do you believe a similar approach could be used beyond the exponential loss?\n\nThank you for raising this point. Please refer to the first question of the general response for our answer to this inquiry.\n"}, {"review_id": "xXwChUiaWn", "reviewer": "Reviewer_HfJS", "summary": "This paper studies the implicit bias of the generic optimization method such as mirror descent and steepest descent. By transforming the generic optimization algorithm into an online learning dynamic, this paper shows the accelerated rate and offers a new perspective.", "questions": "1. Can the author provide some simple experiments to verify the correctness of the theoretical results? For example, using the synthetic dataset with its max-margin solution known.\n2. For the P play, will solving the subproblem lead to a larger complexity?\n3. What is the meaning of $D_E$ in Algorithm 3?\n\n\nTypos:\nAlgorithm 4.3 should be Algorithm 4.", "limitations": "OK", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written.\n2. The theoretical analysis is solid and explicitly explained", "weaknesses": "The major weakness is that this paper only focuses on exponential loss.\nIn addition, choosing the hyperparameters is sometimes difficult.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and positive comments!\n \n> Can the author provide some simple experiments to verify the correctness of the theoretical results? For example, using the synthetic dataset with its max-margin solution known.\n\nThank you for the constructive suggestion; as we discuss in the second point of the general response, we will add numerical experiments in the revised version.\n \n \n> For the P play, will solving the subproblem lead to a larger complexity?\n\nThank you for the question. We note that the online/game framework is only introduced for theoretical analysis, and we do not need to actually run the corresponding online algorithms. Therefore, the p-player will not introduce extra computational complexity. We will make this clearer in the revised version. \n\n\n> What is the meaning of D_E in Algorithm 3?\n\nThank you for the question. D_E stands for the Bregman divergence with respect to the negative entropy regularizer. We will make it clear in the notation part.\n"}, {"review_id": "oMMRZpyhTh", "reviewer": "Reviewer_bPGG", "summary": "The paper studies the implicit bias of generic optimization methods, which plays a key role in understanding their generalization capabilities in settings with multiple solutions.\n\nThe authors propose a new game framework to derive margin and directional error rates, which consists of transforming the optimization method into an equivalent instance of a 2-player margin-maximization game. Afterwards, margin and directional error rates can be derived directly from the players’ average online regret.\n\nThey show equivalent transformations (under exp loss) from weighted MD with a squared p-norm potential and SD under a general norm to instances of the proposed 2-player game, yielding convergence rates from each transformation’s induced regret. More aggressive learning rates are also studied and shown to be able to improve convergence rates.\n\nThe paper shows, through their game framework, that even faster rates can be achieved with Nesterov MD and a form of momentum SD.", "questions": "Is the potential in the left box of Algorithm 4 the general norm squared? This seems to be the case but I think it is not specified in Section 4.3.", "limitations": "Limitations are properly acknowledged, e.g. applicability of the framework only to exp loss and showing method-game equivalence might take effort and be non-trivial.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is clear and well-written, adopting consistent, well-defined notation / objects and presenting assumptions, definitions, and results in a local and organized fashion.\n\nIts novelty and contribution seem significant:\n\nThe proposed game framework seems to be a novel approach to study implicit biases (margin / directional error rates). By reducing rate analyses to the task of finding equivalent transformations to the 2-player game, it might facilitate the study of new method’s implicit biases and hence prove useful for future research.\n\nIt provides a fresh perspective and, as shown in the paper, accommodates different forms of MD and SD, suggesting that it might be able to capture different first-order methods as well. The transformations, although technical and non-trivial, provide valuable insights on the behavior of MD and SD.\n\nThe use of clairvoyance for player w to show form equivalence is also interesting and might be useful for new proof techniques, but I cannot assess its novelty since I am not very familiar with the related work.\n\nThe improved margin rates and new accelerated methods given in Section 4.3 are also impactful and suggest that momentum might be crucial to speed up (general) margin maximization – from what I understand the community only had evidence of this for $p=2$ (Ji et al’21). \n\nFrom my understanding, the paper shows the first $1/T^2$ margin rate for $p \\in (1,2)$, which seems to be a significant contribution.\n", "weaknesses": "The last page or two seem to have been written a bit in a hurry, and little space has been allocated to Section 4.3 compared to its significance. However, since these can be easily fixed in a revision I will not account for that when rating the paper.\n\nAlthough I believe the paper has enough contributions, it would be interesting to have some small (even if synthetic) experiments with margin by time curves for different methods and learning rates regimes.\n\nMinor fixes:\n\nL51: log t -> log T?\n\nL{276, 285, L291, L293, L295}: Algorithm 4.3 -> Algorithm 4\n\nL516 proof -> prove\n\nShould state in Section 4.3 that proof of Theorem 6 is in Appendix E\n\nEq 6 and, Eq 7: period instead of comma after equation\n\nEq 8: missing period after equation\n\nEquation at end of page 6: colon instead of period before eq, period after eq.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your constructive review and supportive comments on our work! We will refine the presentation and rectify the typos in line with your suggestions. For clarity, we will specify in the revised version that the potential in the left box of Algorithm 4 refers to the general norm squared.\n"}, {"review_id": "BA4SmnUODJ", "reviewer": "Reviewer_VcXn", "summary": "This work gives a unified perspective on maximal margin problems realized by a wide range of optimization algorithms. It mainly covers three cases: (i) steepest descent under a general norm, (ii) mirror descent, and (iii) momentum-based acceleration. The authors collectively refer to them as generic optimization problems. The essential point of the theory is that they translate these generic optimization problems into a regularized bilinear game with online learning. This enables us to derive relatively tight margin maximization rates and to characterize the implicit bias of each algorithm. ", "questions": "**Difference from previous work**\n\nSince this work covers various topics of optimization problems, it seems hard for beginners in this research area to judge at what points it is significantly novel compared to the previous work. In particular, the difference from Wang et al 2022b seems to need more clarification. Did this previous work not address the max-margin rate of all of (i) steepest descent under a general norm, (ii) mirror descent, and (iii) momentum-based acceleration problems?  \n\n**Exetention to other generic loss functions**\n\nIt is quite curious whether the idea of using the bilinear game can be extended to other loss functions except for the exponential loss. Is there any work or evidence that the current proof approach could potentially be applied to other loss functions? Otherwise, is it quite specific to the exponential function? \n\n**Tightness compared to numerical experiments**\n\nAlthough I agree that the theoretical evaluation of the bounds itself contributes to enriching our understanding of the problems, it remains unclear how tight the obtained convergence rate is.  I mean, there would be the possibility that the obtained bounds could be much loose compared to the real optimization in experiments. The authors show no empirical confirmation and this makes a bit unclear the superiority of the fast convergence rates obtained in this work. It is not a major flaw, though.", "limitations": "As I mentioned in Questions, one limitation is that there is no comparison with numerical experiments and tightness (or \"true\" implicit bias) seems unclear. The other is the exponential loss as is mentioned in Section 5. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work is based on a concrete and rigorous theoretical analysis of a wide range of optimization problems. One interesting point is that all of them can be mapped in the regularized bilinear game formulation. It gives us a unified perspective of various optimization problems. In addition, this unified formulation enables us to obtain tight convergence rates compared to the previous work.", "weaknesses": "While this work covers various optimization problems and an interesting formulation with the bilinear game, it might be possible to view this as a collection of results that are not particularly novel. The convergence rates of the problems (for example, (i) steepest descent under a general norm, (ii) mirror descent, and (iii) momentum-based acceleration) have been studied although they seem looser than those obtained in the current work. The game formulation has been also provided by some previous work ([Wang et al 2021, 2022b]) in a limited situation. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Difference from Wang et al 2022b seems to need more clarification. Did this previous work not address the max-margin rate of all of (i) steepest descent under a general norm, (ii) mirror descent, and (iii) momentum-based acceleration problems?\n\nThank you for the constructive suggestion; we will add a more detailed discussion in the revised version. Compared with Wang et al (2022b), we note that:\n\n1)   Wang et al., (2022b) draws the connection between Nesterov-accelerated GD for ERM and solving the bilinear game through an online dynamic. However, it was unclear whether this kind of analysis suits other gradient-descent-based methods, and generic optimization methods such as mirror descent/steepest descent was not addressed at all. We observe in this work that the non-linearity of the mirror map in generic optimization methods, such as mirror descent and steepest descent, makes the analysis particularly challenging. In this paper, we reveal that the game framework can in fact encompass implicit bias analysis for a range of generic optimization methods, and offer a more streamlined and unified analysis. \n2)   Wang et al., (2022b) also proposed an accelerated p-norm perceptron problem. However, they only demonstrated that the algorithm could achieve a non-negative margin, leaving open questions regarding whether the margin can be maximized (i.e., converge to $\\gamma$), and if so, what the margin maximization rate would be; 2) They only presented the online dynamic, without its equivalent optimization form under ERM.  \n \n> It is quite curious whether the idea of using the bilinear game can be extended to other loss functions except for the exponential loss. Is there any work or evidence that the current proof approach could potentially be applied to other loss functions? Otherwise, is it quite specific to the exponential function?\n\nThank you for this intriguing question, and we will add a more detailed discussion in the revised version. please refer to the first question in the general response for our answer to this question.\n \n> Tightness compared to numerical experiments\n\nWe appreciate your valuable suggestions. While our paper's primary focus lies in the theoretical aspects of implicit bias analysis, we concur that supplementing these theories with numerical experiments would enhance our work. Accordingly, we will introduce experiments in the revised version to substantiate the efficacy of our proposed methods.\n"}, {"review_id": "vNhTZtGPSD", "reviewer": "Reviewer_Gj8T", "summary": "This paper studies efficient algorithms for margin maximization with respect to a general geometry. The problem of margin maximization is interesting because it has been shown that common optimization algorithm such as gradient descent prefers such solutions through a well-known phenomenon called \"implicit bias.\" This paper proposed a novel analytical framework by re-casting the problem as a bilinear game. The main results show that techniques from online learning can be applied to show fast convergence rates for various optimization algorithms such as mirror descent and steepest descent.", "questions": "I would like to see some proof sketch and strongly recommend the author to add it to the revision. In particular, for Section 4.1, I still don't understand where the $q \\in (1, 2]$ limitation comes into play. Does the same limitation apply to Section 4.3?", "limitations": "This is purely a theoretical paper, so I don't think this paper has any immediate negative societal impact. I find the proofs to be generally easy to follow, but I did not follow all of them line-by-line.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper brings an interesting angle of studying the properties of optimization algorithms through the lens of online learning and games. In particular, Theorem 1 cleanly encapsulates the reduction from optimization to online learning. I feel that this result has a lot of potential in quickly deriving new optimization guarantees by reusing tools from online learning.\n\nI also like the presentation of this paper that it clearly describes prior literature and makes conscious effort in recovering those results through the more general framework of this paper. This allows me to clearly understand the contribution of this paper and appreciate its versatility.", "weaknesses": "Notation is quite dense and can be difficult to parse. For example,\n1. In section 4.1, it is stated that the mirror descent potential is restricted to $q$-norm for $q \\in (1, 2]$. I think it would be better to bring this up sooner in the Preliminaries section.\n2. $D_E$ is not a standard notation, why not just call it the KL-divergence?\n3. I found that the terms $p$-norms and $q$-norms are used almost interchangeably, which might be confusing to readers.\n\nIn Section 4.3, does the mirror descent potential suffer the same limitation as the results in Section 4.1? I have a hard time figuring this out.\n\nThe theorem statements are very long and thus look unnecessarily intimidating. In particular, the notion of directional errors is almost entirely ignored in Section 4. I personally would love to see more discussion on the directional error.\n\nThe term \"rate\" is used imprecisely in the introduction. Some of the prior literature measure their rate in terms of margin maximization, while some others in directional error. The author should do more to clarify this.\n\nRegarding the remark on eq. (5)'s computational efficiency. While it is true that its total amount of computation compares similarly to algorithm such as GD, I don't think taking norm of the entire weight vector is practical in a lot of cases, especially for deep learning where parallel or distributed computation is desired.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your positive and constructive feedback. We will revise the notations and enhance the overall presentation as per your advice. Your specific questions and concerns are addressed below.\n\n>D_E is not a standard notation, why not just call it the KL-divergence?\n\nThank you for your recommendation. We agree that using standard notation can enhance the readability of our work. In the revised version, we will replace D_E with KL-divergence.\n\n> I would like to see some proof sketch and strongly recommend the author to add it to the revision. In particular, for Section 4.1, I still don't understand where the p∈(1,2] limitation comes into play.\n\nWe appreciate your interest in the derivation details, and we agree that a proof sketch would provide valuable insights. In the revised version, we will include a more comprehensive discussion in Section 4.1 to explain why the value of q must fall within the range (1,2]. The key to understanding this is that when q is in the range (1,2], it ensures the (q-1)-strong convexity of $\\ell_t(w)$, which in turn ensures a sufficiently small regret bound for the w-player. It's important to note that, as observed in Theorem 7 (Appendix C), the p-player has a significantly larger (potentially linear) regret bound. Therefore, it is crucial for the w-player's regret bound to be negative and small enough to offset terms in the final bound.\n\n>In Section 4.3, does the mirror descent potential suffer the same limitation as the results in Section 4.1?/ Does the same limitation apply to Section 4.3?\n\nIndeed, the same limitation applies to the results presented in Section 4.3. As outlined in Theorem 6 (Section 4.3), we assume the norm $||\\cdot||$ to be such that $||\\cdot||^2$ is strongly convex. Although this is slightly more general, it essentially confines us to cases where q falls within the range (1,2]. We will make sure to emphasize this point in the revised version for clarity.\n"}]

Author rebuttal:
We are deeply grateful to all reviewers for their positive feedback and valuable suggestions. We commit to implementing your advice to refine our paper, and some of the frequently asked questions are addressed below.
 
>Do you believe a similar approach could be used beyond the exponential loss?
 
We appreciate this insightful question and will include a more comprehensive discussion on this topic in our revised version. Our primary aim in this paper is to present a unified analysis framework for understanding the implicit bias phenomenon and to provide faster convergence rates for a variety of generic optimization methods. We posit that the analysis of exponential loss serves as a first step, and the application of the game/online learning framework bears the potential to be broadened to incorporate an analysis of a more diverse array of loss functions. The current choice of exponential loss is particularly apt for the game/online dynamic analysis as it relates closely to the classical Hedge algorithm in online learning, which also employs the exponential function to measure experts' losses. To broaden our scope to more general functions, we could contemplate replacing the exponential loss in the Hedge algorithm with other losses (e.g., using the “Polynomially Weighted Average Forecaster”, given in Corollary 2.1 of Cesa-Bianchi & Lugosi (2006)), and attempt to establish a link between this online dynamic and optimization methods for more general loss functions. Our preliminary investigations suggest that this avenue is promising but highly non-trivial, and warrants further exploration in future work.
 
> Tightness measured through numerical experiments in addition to theory.

We value your constructive suggestions. While our paper primarily focuses on the theoretical aspects of implicit bias analysis, we concur that complementing our theoretical findings with numerical experiments would provide a more robust validation of our work. Consequently, we intend to incorporate experiments in the revised version to demonstrate the effectiveness of the proposed methods.
 

Cesa-Bianchi, N., & Lugosi, G. Prediction, learning, and games. Cambridge university press 2006.


Meta-review: This very nice paper generalizes the (dual) momentum-based method for margin maximization of Ji-Srebro-Telgarsky, leading to an adjusted proof technique with new insights, and $1/T^2$ rates in broader settings, and in particular for other norms. The paper is dense with many results and the authors will have a tough time fitting it in a poster, let alone a spotlight! Nice work.

Minor comments:

- The camera ready gets an extra page; I urge the authors to use that space to import more insights from the appendix.
- As this work has some focus on margins wrt different norms, I recommend mentioning the 2013 work "margins, shrinkage, and boosting" by Telgarsky which not only gives a  $1/\sqrt{T}$ rate in  $\\|\cdot\\|_1$ (though it is presented there as a $1/T$ rate to a suboptimal margin, but moreover this work gave the ln-sum-exp proof idea as well as the large step size idea used in the later cited works by various authors (and is cited by them for this).
- Seems the *very* last period in the appendix should be outside the parens.
- The huge equation block in the appendix (currently marked line 482) is what causes whitespace issues elsewhere in the appendix; please break it up to aid other appendix readability/presentation.
Decision: Accept (spotlight)