On Accelerated Perceptrons and Beyond
Authors: Guanghui Wang
Rafael Hanashiro
Etash Kumar Guha
Jacob Abernethy
Venue: ICLR 2023 poster (2023)
Keywords: Perceptron
game
optimistic online learning
implicit bias
margin maximization

Abstract: The classical Perceptron algorithm of Rosenblatt can be used to find a linear threshold function to correctly classify $n$ linearly separable data points, assuming the classes are separated by some margin $\gamma > 0$. A foundational result is that Perceptron converges after  $\Omega(1/\gamma^{2})$ iterations. There have been several recent works that managed to improve this rate by a quadratic factor, to $\Omega(\sqrt{\log n}/\gamma)$, with more sophisticated algorithms. In this paper, we unify these existing results under one framework by showing that they can all be described through the lens of solving min-max problems using modern acceleration techniques, mainly through \emph{optimistic} online learning.  We then show that the proposed framework also leads to improved results for a series of problems beyond the standard Perceptron setting. Specifically, a) for the margin maximization problem, we improve the state-of-the-art result from $O(\log t/t^2)$ to $O(1/t^2)$, where $t$ is the number of iterations; b) we provide the first result on identifying the implicit bias property of the classical Nesterov's accelerated gradient descent (NAG) algorithm, and show NAG can maximize the margin with an $O(1/t^2)$ rate; c) for the classical $p$-norm Perceptron problem, we provide an algorithm with $\Omega(\sqrt{(p-1)\log n}/\gamma)$ convergence rate, while existing algorithms suffer the $\Omega({(p-1)}/\gamma^2)$ convergence rate.

Published as a conference paper at ICLR 2023
ON ACCELERATED PERCEPTRONS AND BEYOND
Guanghui Wang', Rafael Hanashiro?, Etash Guha', Jacob Abernethy
"College of Computing, Georgia Tech, Atlanta, GA, USA
"Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA
'Google Research, Atlanta, GA 30309 (gwang369, etash) (eaahheggtech.. edu, edu, abernethyjggoogle.com
ABSTRACT
The classical Perceptron algorithm of Rosenblatt can be used to find linear threshold function to correctly classify linearly separable data points, assum- ing the classes are separated by some margin 7 > O. A foundational result is that Perceptron converges after O(1/7²) iterations. There have been several recent works that managed to improve this rate by a quadratic factor, to O( OVllog n/?), with more sophisticated algorithms. In this paper, unify these existing results under one framework by showing that they can all be described through the lens of solving min-max problems using modern acceleration techniques, mainly through optimistic online learning. We then show that the proposed framework also leads improved results for series of problems beyond the standard Perceptron set- ting. Specifically, a) for the margin maxinization problem, we improve the state- of-the-art result from (log (logt//t²) to O(1/t²), where t the number of iterations; b) we provide the first result on identifying the implicil bias property of the classi- cal Nesterov's accelerated gradient descent (NAG) algorithm, and show NAG can maximize the margin with an (1)((² rate; c) for the classical p-norm Perceptron problem, provide an algorithm with O O(V(p 1) log n/7) convergence rate, while existing algorithms suffer the O(pp 1)/??) convergence rate.
1 INTRODUCTION
In this paper, we revisit the problem of learning a linear classifier, which is one of the most im- portant and fundamental tasks of machine learning (Bishop. 2007). In this problem, we are given a set S of n training examples, and the goal is to find a linear classifier that correctly separates as fast as possible. The most well-known algorithm can converge to perfect (mistake-free) classifier after 2(1/>²) number of iterations, provided the data is linearly separable with some margin 7 > 0 (Novikofi) 1962). Over subsequent decades, many variants of Perceptron have been developed (Aizerman 1964: Littlestone. 1988: Wendemuth 1995: Freund & Schapird, 1999: Ceea-Bianchh et all 2005. to name a few). However, somewhat surprisingly, there has been little progress in substantially improving the fundamental Perceptron iteration bound presented by Novikoff (162).. It is only recently that a number of researchers have discovered accelerated variants of the Perceptron with faster (2(vlog n//7) iteration complexity, although with a slower per-iteration cost. These works model the problem in different ways, e.g.. as a non-smooth optimization problem or an empirical risk minimization task, and they have es- tablished faster rates using sophisticated optimization tools. Soheili & Pena (012) put forward the smooth Perceptron, framing the objective as non- mon-smooth crongly-concave maximization and then applying Nestrov's excessive gap technique (NEG, Nesterov. 2005). Yu all (014)) proposed the accelerated Perceptron by furnishing a convex-concane objective that can be solved via the mirror- prox method ( 2004). Ji all (2 put forward a third interpretation, obtaining the accelerated rate by minimizing the empirical risk under exponential loss with a momentum-ban normalized gradient descent algorithm.
Perceptron (Rosenblatl 1958), which
Following this line of research, in this paper, we present a unified analysis framework that reveals the exact relationship among these methods that share the same order of convergence rate. Moreover, we show that the proposed framework also leads to improved results for various problems beyond the standard Perceptron setting. Specifically, consider general zero-sum game that involves

---

Published as a conference paper at ICLR 2023
two players (Abernethy et 2018): main player that chooses the classifier, and auxiliary player that picks a distribution over data. The two players compete with each other by performing no-regret online learning algorithms (Hazan. 2016 Orabonal 2019), and the goal is to find the equi- librium of some convex-concave function. We show that, under this dynamic, all of the existing accelerated Perceptrons can find their equivalent forms. In partieular, these perceptrons can be de- scribed as a dynamic where two plavers solving the game via performing optimistic online learning strategies (Rakhlin & Sridharan 2013), which is one of the most important classes of algorithms in online learning. Note that implementing online learning algorithms (even optimistic strategies) to solve zero-sum games has already been extensively explored (e.g.. Rakhlin & Sridharanl 2013:
Daskalakis et all 2018: Wang & Abernethyl 2018: Daskalakis & Panageas. 2019). However, we emphasize that our main novelty lies in showing that all of the existing accelerated Perceptrons, de- veloped with advanced algorithms from different areas, can be perfectly described under this unified framework. It greatly simplifies the analysis of accelcrated Perceptrons, as their convergence rates can now be easily obtained by plugging-in off shellf regret bounds of optimistic online learn- ing algorithms. Moreover, the unified framework reveals a close connection between the smooth Perceptron and the accelerated Perceptron of et all (202)):
Theorem 1 (informal). Smooth Perceptron and the accelerated Perceptron of Ji al (2021) can be described as a dynamic where the two players employ the optimistic-follow-t seellow-the-regee regularized-leuae (OFTRL) algorithm to play. The main difference is that the smooth Perceptron outputs the weighted average of the main player's 's historical decisions, while the accelerated Perceptron of et al (202 outputs the weighted sum.
Beyond providing deeper understanding of accelerated Perceptrons, our framework also provides improved new results for several other important areas:
2018 shows that, for linearly separable data, minimizing the empirical risk with the vanilla gradient descent (GD) gives a classifier which not only has zero training error (thus can be used for linear separation), but also maximizes the margin. This phenomenon characterizes the implicit bias of GD, as it implicitly prefers the (l2-) maximal margin classifier among all classifiers with a positive margin, and analysing the implicit bias has become an important tool for understanding why classical optimization methods generalize well for supervised machine learning problems. Soudry et all (2018) show that GD can maximize the margin in O(1/ log t) rate, and this is later improved to O(L/Vt) Nacson et all 2019) and then (11/t) ( & Telgarskyl 202 The state-of of the- algorithm is proposed by Ui et all 202 who show that their proposed momentum- based GD has (logt//t²) margin-man maximization rate. In this paper, make two contributions toward this direction:
Implicit bias analysis. The seminal work of Soudry
1. We show that, under our analysis framework, we can easily improve the margin maxi- mization rate of the algorithm of of all 2021) from (logt//²) to O(1/t);;
Although previous work has analyzed the implicit bias of GD and momentum-based GD, it is still unclear how the classical Nesterov's 's accelerated gradient descent (NAG, Nesterox 1988) will affect the implicit bias. In this paper, through our framework, we show that NAG with appropriately chosen parameters also enjoys an O(1/t²) margin- maximization rate. To our knowledge, it is the first time the implicit bias property of NAG is proved.
p-norm Perceptron. Traditional work on Perceptrons typically assumes the feature vectors lie in an balb. A more generalized setting is considered in Gentile (000), who assumes the feature vectors lie inside an balbal,, with p [2, oo). Their proposed algorithm requires (p//²2) number of iterations to find zero-error classifier. In this paper, we develop a new Perceptron algorithm for this problem under our framework based on optimistic strategies, showing that it enjoys accelerated O(vp ni/7) rate.
2
RELATED WORK
This section briefly reviews the related work on Perceptron algorithms. implicit-bias analysis, and game theory. The background knowledge on (optimistic) online learning is presented in the Prelim- inaries (Section 3
2

---

Published as a conference paper at ICLR 2023
Accelerated Perceptrons and p-norm Perceptron The study of Perceptron algorithms has tensive history dating back to the mid-twentieth century dRosenblati 195& Novikofi. 1962). How- ever, it is only recently that progress improving the fundamental 2(1/12) iteration bound of the vanilla Perceptron in the standard setting has been made. Specifically, the smooth Perceptron proposed by (Soheili & Pena (012) achieves an (oy n/7) rate by maximizing an auxiliary non- smooth strongly-concave function with NEG (Nesteros. 2005). The same accelerated rate is later obtained by two other work (Yu et all 2014: Ji et al. 202 The former considers a bi-linear sad- dle point problem and employs the mirror- prooo method (Nemirovski. 2004). The latter applies momentum-bass based GD to minimize the empirical risk with exponential loss. In this paper, we show that these algorithms can be unitedly analysed under our framework.
Apart from the above accelerated Perceptrons, there exists another class of algorithms which en- joy an (n) (r)) convergence rate (Dunagan & Vempala, 2004, Peña & Soheili, 2016 Dadush et al. 2020). These methods typically call (accelerated) Perceptrons as subroutine, and then apply the re-scaling technique to adjust the decision periodically. Although the dependence on y becomes better, the polynomial dependence on n of these methods makes them computation- ally inefficient for large-scale data sets. In this paper, focus on accelerated Perceptrons with OVooog n/y) rate, and leave explaining the re-scaling type algorithms as future work.
The p-norm Perceptron problem (Gentile & Littlestond 1999) is natural extension of the classical Perceptron setting, which assumes the p-norm of the feature vectors are bounded, where 2 Σ p < co. Gentile (2001) shows that difror-descenn-stylle update guarantees an Opp/>²) convergence rate. By contrast, our proposed algorithm achieves a tighter O D(Vplogni// convergence rate.
Implicit-bias analysis In many real-world applications, directly minimizing the empirical risk (without any regularization) by first-order methods can provide a model which, not only enjoys low training error, but also generalizes well (Soudry et all 2018). This is usually considered as the implicit bias introduced by the optimization methods (Soudry et al. 2018). Explaining this phe- nomenon erucial step towards understanding the generalization ability of commonly-uses op- timization methods. For linear separable data, Soudry et all 2018) proves that, when minimizing the empirical risk with exponential loss, the vanilla GD can maximize the margin in an O(1/ log t) rate. This result implies the implicit bias of GD towards the ma-maxamal margin classifier. Later, Nacson et all (019) show that GD with a function-value-deeeenaaa decreasing step-size enjoys an O(1/Vl) margin-maximizan
rate. Ji & Telearsky (202)) improve this result to (11/t) by em- ploying fester-de step size. Ji all (2021) design a momentum-based GD that maximizes the margin with an (logt/t²) rate. However, it remained unclear whether this rate could be further improved and how to analyze the margin maximization ability of other classical optimization meth- ods such as NAG. In this paper, we provide positive answers to both questions. Fianlly, we note that (Ramdas & Penal 2016 prove varint of the Perceptron algorithm named normalized perceptron can also converge to maximum margin classifer in an O(1/ VF) convergence rate.
Games and no-regret dynamics Our framework is motivated by the line of research that links optimization methods for convex optimization to equilibrium computation with no-regret dynam- ics. The seminal work of Rakhlin & Sridharan (2013) recovers the classical mirror-prox method Tothhioiiiii
(Nemirovski. 2004)) with Optimistic online mirror descent. Abernethy & Wang (017) show that
the well-known Frank-Wolfe algorithm can be seen as applying (optimistic) online algorithms to compute the equilibrium of special zero-sum game called Fenchel game, which is constructed via the Fenchel duality of the objective function. Later, researchers demonstrate that other classical optimization methods for smooth optimization, such as Heavy-ball and NAG, can also be described similarly (Abernethy et all 2018 Wang & Abernethyl 2018 Wang et all 2021). We highlight the differences between this work and the previous ones: 1) Our analysis does not involve the Fenchel game or Fenchel duality; instead, we directly work on the (regularized) min-max game designed for linear classification. 2) Most of the previous work mainly focus on understanding optimization algorithms for smooth optimization, and it was unclear how to understand algorithm such NEG under the game framework. 3) Although both Abernethy et all (018)) and our work analyze NAG, the goals significantly different: Abernethy et all (2018) focus the optimization problem itself, while we consider how minimizing the empirical risk would affect the margin. 4) To our knowledge, the link between the implicit-bias problems and no-regret dynamics is also new
3

---

Published as a conference paper at ICLR 2023
3 PRELIMINARIES
Notation. We use lower case bold face letters x, to denote vectors, lower case letters a, b to denote scalars, and upper case letters A, B to denote matrices. For vector x E R we use x; to denote the i-th component of x. For a matrix E Rn let A(I.)) be its i-th row, A(..)) the j-th column, and ((t,)) the i-th element of the j-th column. We use || to denote general norm, || ll. its dual norm, and || ||p the l nn-norm. For positive integer n. we denote the set (l...., n) as [n]. and the n-dimensional simplex as A" Let E A + R be the negative entropy function, defined as (pp) Σi= Pi log Ps; Vp E A", For some strongly convex function R(w). W H R. define the Bregman divergence between any two points w, w' E W as:
DR(W, w') R(w) - R(w') (w w) VR((w).
Online convex optimization (OCO) Here we review a general weighted OCO framework, pro- posed by Abernethy at (018). In each round = ,. of this paradigm, learner first chooses a decision 2, from a convex set 2 _ R then observes a loss function ft(-) : 2 + R as well as weight a₂ > 0, and finally updates the decision. The performance of the learner is mea- sured by the weighted regret, which is defined as RT Σt= fefe(z)) minge 2 E fz()..
Perhaps the most natural method for OCO is follow-the-leader (FTL), which simply picks the em- pirically best decision at each round: z, = argmin 2 Σi= (z). However, FTL is unsta- ble, and one can easily find counter-examples where FTI. suffers linear regret (Shalev-Shwartz 2011). A classical way to address this limitation is by adding regularizer to the objective: Z: = argminge > (z) + DR(z, zo), where 1) O is the step size, and Zo is the ini- tial decision. This method is called follow-the-ree regularruuar sub-linear regret bound with appropriately chosen 17. Moreover, tighter bounds are also possible in favored cases with more advanced techniques. In this paper, we consider FTRL equipped with optimistic strategies (i.e., Optimistic FTRI., Rakhlin & Sridharan 2013 Orabona. 2019), given by
(Hazan 2016), and it can achieve
OFTRL|R, 2o. th,, 17, 2] 2t argmin 1 E a: fzfz(z) + anbh(z)) + DR(Z, 20),
where an additional function dh is added, which is an approximation of the next loss St- A tighter regret bound can be achieved when the is close enough ft. Next, we introduce two special cases of OFTRL:
OFTL| 2]:
argmin ZE2
agf{(z) arbi(z)
FTRL* Zo, 77, 2] 2, argmin nj
Σ (Z) + Dn(2, 20).
#E2
The first one is Optimistic FTL, where the regularizer is set to be zero. The second algorithm is FTRL* which uses ft as the optimistic function t/.. Finally, we note that, apart from FTL-type algorithms, there also exists optimistic methods that are developed based on mirror descent, such as optimistic online mirror decent (OMD, Rakhlin & Sridharan 2013). Due to page limitation, the details of OMD and the regret bounds of these OCO algorithms are postponed to the Appendix A
No-regret dynamics for zero-sum game online algorithms to solve zero-sum game. Consider the following general two-player game:
Finally, we introduce the framework for using no-regret
max min g(w, p), wEW PEQ
where g(w, p) is concave-convex function, and W and Q are convex sets. The no-regret frame- work for solving ① is presented in Protocol In each round f of this procedure, the w-player first picks a decision w, E W. Then, the p-player observes its loss (x(-)
g(we,-) as well as a weight a₁, After that, the p-player picks the decision Pt, and passes it to the w-player. As a consequence, the w-player observes its loss h+(+) = -g( Pt) and weight a, Note that both é, and ht are convex. Denote the weighted regret bounds of the two players as R and RP, respectively. Then, we have the following classical conclusion. The proof shown in Appendix
Theorem 2. Define m(w) = millpe g( ((,)), p), and w the weighted average of (wr) Then we have that Vw W, m(w) m(wr) & (Ei (4) (RP Rw).
4

---

Published as a conference paper at ICLR 2023
Protocol No-regret dynamics with weighted OCO
1: Input: {ar)1= Wo, Po-
12'
2: Input: OL OLP. The online algorithms for choosing w and p.
3: for = T......d. do
4:
W, OL";
5: OL Ct: fx(-); Define ((-)) g(w,,') :)
6:
Pr f- OL":
7:
OL w + a' (-); Define he(-) = -
8:
end for
9: Output: WT Eis Σt= O/WL
4 UNDERSTANDING EXISTING ACCELERATED PERCEPTRONS
In this section, we first introduce our main topic, i.e., the binary linear classification problem, and then present the three accelerated Perceptrons and their equivalent forms under Protocol D For clarity, we use to denote the classifier updates in the original algorithms, and w, the corresponding updates in the equivalent forms under Protocol
4.1 BINARY LINEAR CLASSIFICATION AND PERCEPTRON
We focus the binary linear classification problem, which dates back to the pioneering work of Rosenblat (958). Let S (x(+), ( be a linear-separable set of n training examples, where (f) E Rd is the feature vector of the i-th example, and y E {-1.1} } is the corresponding label. The goal efficiently find linear classifier w E Rd that correctly separates all data points. More be the matrix that contains all of the data. Then formally, let A (())) ..... (")...")).(()))) (")]
would like to find E IRd such that
min A(.: w > *E(n]
This goal can be reformulated as min-max optimization problem:
min A(..) max min p Aw, weRd sE(n)
(3)
weRd PEA"
where, at the RHS of B1, min in] A w is rewritten as m T Aw. The two expressions are A" will always put all weight on one training example
equivalent since the optimal distribution (i.e., one row) in A. For any w E Rdd, ((w) = milpee" p Aw be the margin of w, and we introduce the following standard assumption.
Assumption 1. We assume that feature vectors are bounded, i.e., ||x! S 1 for all i e [n]. and that there exists a w E IRd, such that ||w*||2 = 1 and 7(w") = > O.
4.2 SMOOTH PERCEPTRON
In order solve 33) the vanilla Perceptron repeatedly moves the direction of the classifier that of examples on which it performs badly. However, this greedy policy only yields a sub-optimal convergence rate. To address this problem. Soheili & Pena (2012) propose the Smooth Perceptron, and the pseudo-code is summarized in the first box in Algorithm[] The key idea is to find classifier d that maximizes the following lg reguauulr function:
(bv) - - || + mingee= q TAv,
which non-smooth strongly-concave with respect to v. Under Assumption |I Sohcili & Pena
(2012) show that the maximum value of vv(v) is max vv(v) ,,2 /2, and classifier
Rd satisfies when vv(v) > O. In order to solve 4.. [Soheili & Pena (012)) apply the classical
Nesterov's 's excessive gap technique (Nesterov, 2005) for strongly concave functions. This algorithm
introduces smoothed approximation of [4] which is parameterized by some constant μ >> 0, and defined as
(v) - minges" [q Av nDg (q. !
(5)

---

Published as a conference paper at ICLR 2023
Algorithm Smooth Perceptron (Soheili & Pena 2012)
Initialization 0n 2 Mo 4, Vn 1_1
Initialization [q quu (Vo). where (p(v) argmin a Av uDE (q. h).
for t 1.....T T- do
V; (1 8.-1((V,- + 1 Aq + Aq (Vı-1)
14 (1 0:- |/-11
q: (1 0, qu-1 + O2 19-
0. i-3
end for
Output: VT-1
OL" OLw = OFTL (v--(-),R*) + W. = argmin WERd
ayh,(w) + achh-1(w)
j=1
OL FTRL*
E(-), A
Pt argmin $ E acl((p) + +DE (p.
PE
Output: WT
which bounds the function in 4 from below, i.e., Vv E R 1 0, vv((v) S vvvv + y log Then, the algorithm performs sophisticated update rule such that the excessive gap condition holds Vi 1: /2 < || (v.). We refer to Soheili & Pena (012)) for more details.
Sohcili & Pena 2012) show that the smooth Perceptron can output a positive-margin classifier after ((Vlog n//y) iterations. However, the analysis is quite involved, which heavily relies the plicated relationship between vv(v)). y (v:) and || P. In the following, we provide a no-regret explanation of this algorithm and then show that the convergence rate be easily obtained under our framework. Specifically, we define the objective function in Protocol as
g(w: p) = p Aw w|
and provide the equivalent expression in the second box of Algorithm II More specifically, we have the following proposition. The proof given Appendix C.1
Proposition a4 Then the two interpretations of the smooth Perceptron Algorithm the same, in the sense that vT-1 Wr, and qr-1
-T. a.P
21-1
Proposition 1 shows that, under Protocol D the smooth Perceptron can be seen optimizing 1 by implementing two online learning algorithms: in each round the w-player applies OFTL with d/ f decision which the p-player subsequently observes and responds with FTRL More- over, we obtain thcoretical guarantees for the smooth Perceptron based on Theorem matching the convergence rate provided by Soheili & Pena 2012).
Theorem 3. Let a; = f. Under Protoco! / the regret of the two players of Algorithm 7 is bounded by R < 2 _ |p: PI-1 and RP < 4log Σ ||pr P Moreover, WT has
non-negative margin when = D2( Vlogn
4.3 ACCELERATED PERCEPTRON VIA ERM
Since binary linear classification is (and perhaps the most fundamental) supervised machine learn- ing problem, can be naturally solved via empirical risk minimization (ERM). This idea adopted by Ji et all (2021), who consider the following ERM problem:
min R(v) 1 Σ 10 x vER4
where E(z) = exp(2) is the exponential loss. To minimize
Ji et al 202 propose the a normal- ized momentum-based gradient descent (NMGD) algorithm, and show that NMGD converge

---

Moreover, Wi has Published as a conference paper at ICLR 2023
Algorithm 2 Accelerated Perceptron of et (2021)
Input: qu = Vo 0, = O. for f = I..... T do
Set 0--1 = 2[++1] Br = F+1
V: - Vt-1 - 0,- 18-1(8:11 (g--1
q q(-1)
for i = -I...., do
expl y x
qt Σ/=1 exp( ybyby, x(1)
end for
g: (e(g1-1 A 91)
end for Output: VT
OL w = OFTL (+), + w. = argmin weRd
(w]) + acche-l(w)
j=1
1
1
OL" FTRL
E(),, n2 A + Pe
argmin
Σ a
+Dg
P
PEA 4
Output: WT
a classifier with a positive margin after O(1/²²) iterations. Based on the property of the normalized gradient, they also provide primal-dual form of the algorithm (presented in the first-box of Algo- rithm 2b. which can be considered as applying Nesterov's ' accelerated gradient descent the dual space et 2021).
For the accelerated Perceptron of al 202 lb, we set g(w, p) = p AwAw w and provide its equivalent form at the second box in Algorithm ?
Specifically, have the following proposition.
Proposition 2. Let at Then the two interpretations of the accelerated Perceptron in Algorithm 2 are the same, in the sense that qr Pr and vT =E=ro o.W, = (E ot) WT.
Remark Note that in Ji al (202)), the parameter 0z-1 is set to be 1. We observe that this causes mismatch between the weights and w/s in the output (when 0--1 1, vr will become Σ at++ w. instead of Σ w.). Our no-regret analysis suggests that 0:-1 should con- figured as 20+IJ. and later we will show that this procedure helps eliminate the log factor in the convergence rate.
The proposition above reveals that the smooth Perceptron and the accelerated Perceptron of Ji et all (222h are closely related. The main difference is that the accelerated Perceptron Ji (021 outputs the weighted sum of all w, 's, instead of the weighted average. The rationale behind this phenomenon is that, instead of the margin, at (201)) use the normalized margin measure the performance of the algorithm, defined as 7(v) = minpe P Av/lvll They not only prove log 7ाт) This
7(VT) > 0 (which directly implies 7(vr) > 0), but also show 7(VT) = 2(7
guarantee is more powerful than the previous results, as it implies that the normalized margin can be maximized in an O(log t/t²) rate. When approaches oc, the direction of VT will converge to that of the maximal margin classifier. We show that better margin-maxe maximization rate be directly obtained under our framework with the parameter setting in Algorithm 2
Theorem 4. Let az = I. Under Protocol / the regret of the two players of Algorithm is bounded by R < 2 lp: P and RP < 4 4log - 2 2T |p: non-negative margin when T = 12VVlog n/Y) and ((vr) Q06 5T(T+1)
-P:111
8log
7

---

Published as a conference paper at ICLR 2023
Algorithm 3 NAG
Input: Vo = 0, S0 0.
for = ...... do
1 + 1[t-1] Vc-1
V: = Vt-1 7/ (VVR(()))
S; St-1 2(++))
end for Output: ST
OL" OFTRL [B(), 1, + Pt argmin PEΛ
agla(p) (pl
Dr (p,
OL FTRL 1T, 1,R, + W. = argmin
Σ ayh,(w)
wER
j=1
ΣT, WT.
Output: WT
4.4
ACCELERATED PERCEPTRON OF YU AL. (2014)
Finally, Yu all 2014) considers applying the mirror-prox algorithm to solve the max-min opti- mization problem:
min p AAw, S1 A
mirror-prox can be recovered by their optimistic online mirror descent (OMD) with an appropriately chosen optimistic term. Here, we show that, by simply manipulating the notation, the algorithm of Yu et all (2014) can be recovered as two-players applying OMD to solve Due to page limitation, the algorithmic details and their analysis are postponed to Appendix (5.5 which we summarize follows (formalized in Theorems R and 9
As discovered by Rakhlin & Sridharan 2013
Theorem 5 (informal). Let gew, = p Aw. The Perceptron of Yu et al 2014) can be described under Protocol where both players apply OMD endowed with the appropriate parameters. More-
over, under Assumption 7
WT has non-negative margin when T S2 Vlogn
5
BEYOND PERCEPTRONS
In This section, we show that our framework benefits wide range of other problems.
5.1 MARGIN MAXIMIZATION BY NESTEROV'S ACCELERATED GRADIENT DESCENT
One major task for the implicit bias study is to explain why commonly first-order optimization methods generalize well. For linearly separable data, previous work proves that GD and momentum- based GD prefers the maximlll margin classifier by showing that they can maximize the margin. In this part, show that the well-known Nesterov's accelerated gradient descent (NAG), with ap- propriately chosen parameters, can maximize the margin in an 011/~²) rate. Specifically, following previous work, we consider maximize the margin by solving the ERM problem in 7 and apply Nes- terov's accelerated gradient descent (NAG) to minimize the objective function. The details of the algorithm are summarized the first box of Algorithm R and its equivalent form under Protocol 11 is presented in the second box of Algorithm g For the NAG algorithm, we set the objective function
as g( w, p) -pp Aw
2 || Ig. and have the following conclusion.
Theorem 6. Let mr R(n.)
f and ag = t. Then, the two expressions in Algorithm are equivalent,
min p Ast DEA"
in the sense that sT
WT. Moreover;
8 1lognt2
B 1a
T(T+1)7
8

---

Published as a conference paper at ICLR 2023
Algorithm 4 Accelerated algorithm for the p-norm perceptron
OL OFTRL
11 17
"hnn",h-111 (h)1(().
2(q
[-1
Wr = argmin 17 wERd
Σ ==1
aayh(() + a + 219-1) 11.113 (w, 0)
1 Σ aglo(p) + +DE p.
OLP = FTRL
E. 1/ A
Pt argmin Ty
PEA
Output: WT + Σ W..
Remark Theorem 6 indicates that NAG also maximize the margin in an O(1/T²) rate. Note that, in Algorithm t the p-player plays first and the w-player second, while, in Algorithm 2 ir the other way around. This difference makes sense as Algorithm B can be considered as apply- ing Nesterov's acceleration in the dual space (Ji et 2021). while Algorithm R uses Nesterov's acceleration in the primal space.
5.2 ACCELERATED P-NORM PERCEPTRON
In this section, we focus on the p-norm Perceptron problem, introduced by Gentild 2000). Com- pared to the classical perceptron problem, p-norm Perceptron introduces the following assumption, which is more general than Assumption 1
Assumption 2. For the p-norm Perceptron problem, assume; Vi [m]]. ||x("Il I 1, where p E [2, oo). Moreover, assume there exists w E RRd, such thut ||w"lla S and min p Aw" 2 PEa
Here, || llg is the dual norm of || llpi i.e., = and (1,2).
Under Assumption Gentile 2000) proposes a mirror-descent style algorithm that achieves an algorithm with better rate. Specificallyy, under Protocol[ we define the objective function as g(w,p) p) = =p Aw, and introduce OFTRL with regularizer 2(7-1) l which is 1-strongly convex w.r.t. the g-norm Orabonal 2019). On the other hand, the q-player employs the FTRL+ algorithm. We have the following result.
2(11 - -p)/²²) convergence rate. In the following, we provide
Algorithm ! wherein the w-player
Theorem 7. Let a = 1, rp = 1/n"", and 17t V 2(g logn
Then the output WT of Algorithm
has nen-negative margin when T = St (V2(p- loglog/// logn/>).
CONCLUSION
In this paper, we provide unified analysis for the existing accelerated Perceptrons, and obtain im- proved results for a series of problems. In the future, will explore how extend our framework to other closely related areas, such as semi-definite programming (Garber & Hazan. 2011) and gener- alized margin maximization (Sun all 2022). Another interesting direction is to consider whether other more advanced online learning algorithms (Orabona & Pál. (20 Cutkosky & Orabona 2011
Jun et all, 20177 Zhane et all 2018 Wane et all. 2020: Zhao et al. 2020 useful for perceptron and
the implicit bias analysis based on our framework.
ACKNOWLEDGMENTS
We gratefully thank the AI4OPT Institute for funding, part of NSF Award 21 2112533. We also acknowledge the NSF for their support through Award 11-1190077, as well as an ARC-ACO fel- lowship provided by Georgia Tech.

---

Published as a conference paper at ICLR 2023
REFERENCES
Jacob Abernethy, Kevin A Lai, Kfir Y Levy, and Jun-Kun Wang. Faster rates for convex-concay. games. In Proceedings of the s1 Annual Conference on Learning Theory, pp. 1595-1622 2018.
Jacob D Abernethy and Jun-Kun Wang. On wolfe and equilibrium computation. Advances in Neural Information Processing Systems 30, 30, 2017.
Mark A Aizerman. Theoretical foundations of the potential function method in pattern recognition learning. Automation and remote control, 25:821 13:821-833 1-837, 1964.
Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2007.
Nicolo Cesa-Biancie Alex Conconi, and Claudio Gentile. second-order perceptron algorithm. SIAM Journal on Computing, 34(3):440-66,, 2005.
Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pp. 1493-1529, 2018.
Daniel Dadush, Laszlo A Vegh, and Giacomo Zambelli. Rescaling algorithms for linear conic feasibility. Mathematics of Operations Research, 45(2):732-754, 2020.
C Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In 10th Innovations in Theoretical Computer Science conference, 2019.
Constantinos Daskalakis, Andrew llyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations, 2018.
John Dunagan and Santosh Vempala. A polynomial-time rescaling algorithm for solving linear programs. In Proceedings of the 36th annual ACM symposium on Theory of computing, pp. 28, 2004.
Yoav Freund and Robert E. Schapire. Large margin classification using the perceptron algorithm. Machine learming, 37(3):277-296, 1999.
Dan Garber and Elad Hazan. Approximating semidefinite programs in sublinear time. Advances in Neural Information Processing Systems 24, 2011.
Claudio Gentile. A new approximate maximal margin classification algorithm. Advances in Neural Information Processing Systems 13, 2000.
Claudio Gentile. A new approximate maximal margin classification algorithm. Journal of Machine Learning Research, 2:213-242, 2001.
Claudio Gentile and Nick Littlestone. The robustness of the p-norm algorithms. In Proceedings of the 12th annual conference on Computational learning theory, pp. 1-11, 1999.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):1773325 2016.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via a primal-dual analysis. In Pro- ceedings of the 32nd International Conference on Algorithmic Learning Theory, pp. 772-804. 2021.
Ziwei Ji, Nathan Srebro, and Matus Telgarsky. Fast margin maximization via dual acceleration. In Proceedings of the 38th International Conference on Machine Learning, pp. 4860-4869, 2021.
Kwang- Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics, pp. 943-951, 2017.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new threastt algo- rithm. Machine learning, 2(4):285-318, 1988.
10

---

Published as a conference paper at ICLR 2023
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. The 22nd International Conference Artificial Intelligence and Statistics, pp. 3420-3422222 2019.
Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229- 2, 2004.
Yu Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Opti- mization, 16(1):235-26) 249, 2005.
Yurii Nesterov. On an approach to the construction of optimal methods of minimization of smooth convex functions. Ekonomika Mateaticheskie Metody, 24(3):509-517, 1988.
A.B.J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, volume 12, pp. 615-622, 1962.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv: 2019.
Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems 29, 2016.
Javier Peña and Negar Soheili. deterministic rescaled perceptron algorithm. Mathematical Pro- gramming, 155(1):997-510, 2016.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems 26, pp. 3066-3074, 2013.
Aaditya Ramdas and Javier Pena. Towards deeper geometric, analytic and algorithmic understand- ing of margins. Optimization Methods and Software, 31(2):377-391 2016.
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
Shai Shalev-Shward Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Negar Soheili and Javier Pena. A smooth perceptron algorithm. SIAM Journal Optimization, 22 (0):728733, 2012.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. The Journal of Machine Learning Research, 19 2878822-8878 2018.
Haoyuan Sun, Kwangjun Ahn, Christos Thrampoulidis, and Navid Azizan. Mirror descent maxi- mizes generalized margin and can be implemented efficiently. arXiv preprint 2205 2022.
Guanghui Wang, Shiyin Lu, Quan Cheng, Wei-wei Tu, and Lijun Zhang Sadam: A variant of adam for strongly convex functions. In International Conference on Learning Representations, 2020,
Jun-Kun Wang and Jacob D Abernethy. Acceleration through optimistic no-regret dynamics. In Advances in Neural Information Processing Systems 32, pp. 3824-3834 2018.
Jun Wang, Jacob Abernethy, and Kfir Y Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization. arXiv preprint arXiv:2111. 2021.
Wendemuth. Learning the unlearnable. Journal of Physics A: Mathematical and General, 28(18): 5423, 1995.
Adams Wei Yu, Fatma Kilinc-Karzan, and Jaime Carbonell. Saddle points and accelerated percep- tron algorithms. In International Conference Machine Learning, pp. 1827-1835, 2014.
11

---

Published as a conference paper at ICLR 2023
Lijun Zhang. Shiyin Lu, and Zhi-Hus Zhou. Adaptive online learning in dynamic environments, In Advances in Neural Information Processing Systems 31, pp. 5523-1333 2018.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions, Advances in Neural Information Processing Systems 33, pp. 12510-12520 2020.
12


Reviews:
[{"review_id": "o02DsFLSMP", "reviewer": "Reviewer_gCQu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a unified analysis for accelerated perceptrons via reduction to a certain minmax game. Improved rates are then achieved by designing the dynamics of the min and max player. The analysis is simple and easily captures several prior works as special cases, while also easily enabling the authors to develop new algorithms with improved rates.", "summary_of_the_review": "This is an excellent paper and I highly recommend its acceptance. ", "strength_and_weaknesses": "The paper is very strong overall. The writing is clear and the math is easy to follow (particularly for those already familiar with optimistic MD/FTRL). The analysis is elegant and leads to novel results while capturing existing works as special cases. \n\nMy only issue with the paper is that there are some connections to recent works on acceleration that I think would be worth discussing in the paper. In particular, Allen-Zhu (2016) and Joulani (2020) similarly view accelerated algorithms as decomposing into two online learning algorithms with interacting dynamics, with optimistic FTRL being the key component in Joulani 2020. I think these are both similar in spirit to what's happening here and would be worth discussing (or at least citing).\n\n- Joulani, P., Raj, A., Gyorgy, A., & Szepesvari, C. (2020). A simpler approach\n  to accelerated optimization: iterative averaging meets optimism. In H. D. III,\n  & A. Singh, Proceedings of the 37th International Conference on Machine\n  Learning (pp. 4984–4993). : PMLR.\n- Allen-Zhu, Z., & Orecchia, L. (2016). Linear coupling: an ultimate unification\n  of gradient and mirror descent.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LDBzN7dzEx", "reviewer": "Reviewer_nHQ8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Consider the problem of finding a linear classifier with positive margin for a given linearly separable dataset, which can be formulated as a bilinear minmax problem. This paper proposes a unified interpretation for two algorithms by Soheili & Pena (2012) and Ji et al. (2021) and a new algorithm based on Nesterov's accelerated gradient method. The key idea is to consider a slightly modified minmax problem---a game---and solve it via no-regret learning. The idea is reminiscent of the papers by Abernethy and Wang on interpreting convex optimization algorithms via no-regret learning in Fenchel games. ", "summary_of_the_review": "The paper considers a classic problem, is novel, and provides new insights for understanding existing algorithms. I don't see any significant weakness but only some minor flaws in the presentation. Therefore, I suggest acceptance of this paper. ", "strength_and_weaknesses": "***Strength***\nThe problem is classic. The results are new and interesting. The unified interpretation provides new insights. \n\n***Weaknesses***\nI don't see any significant weakness. Due to the *unreasonably tight review deadline*, I only checked the proof of Theorem 3. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3piTOF_N55f", "reviewer": "Reviewer_PKdM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper establishes minimax object function for perceptron algorithm, and treat it as a minimax optimization problem. For this problem, faster convergence rate (than perceptron) can be obtained. ", "summary_of_the_review": "I think the paper has potential, and tries to make interesting interpretation and connection to minimax optimization of a very specialized problem related to the perceptron algorithm. \n\nHowever, due to the content of the paper, it should be regarded as an optimization paper. For such a paper, the problem considered is quite narrow, so I'd expect more, including  what's special about this problem beyond standard minimax optimization, and what are the new optimization methods this paper actually develops in the broader context of minimax optimization. As it is currently written, I find it hard to interpret its significance.\n", "strength_and_weaknesses": "Strength. The minimax formulation is an interesting view of what perceptron tries to optimize, although it is fairly straight-forward.\n\nWeakness\nI am not sure what's the main message. Minimax problem is well-studied in optimization. This particular problem is a very specialized formulation of minimax problem. It will be nice to understand what makes it special and why it is not trivial to use some results for general minimax problems to derive convergence for this problem. Are there really new algorithms or merely reinterpretation of standard results for this specialized problem? If the latter, what's the benefit of the specialization?  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster