# On Accelerated Perceptrons and Beyond††thanks: An earlier version of this
paper titled “Linear Separation via Optimism” is posted on:
https://arxiv.org/abs/2011.08797.

Guanghui Wang<EMAIL_ADDRESS>
College of Computing, Georgia Tech, Atlanta, GA, USA
Rafael Hanashiro<EMAIL_ADDRESS>
Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA,
USA
Etash Guha<EMAIL_ADDRESS>
College of Computing, Georgia Tech, Atlanta, GA, USA
Jacob Abernethy<EMAIL_ADDRESS>
College of Computing, Georgia Tech, Atlanta, GA, USA

###### 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 _optimistic_
online learning. We then show that the proposed framework also lead 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.

##  1 Introduction

In this paper, we revisit the problem of learning a linear classifier, which
is one of the most important and fundamental tasks of machine learning
(Bishop, 2007). In this problem, we are given a set $\mathcal{S}$ of $n$
training examples, and the goal is to find a linear classifier that correctly
separates $\mathcal{S}$ as fast as possible. The most well-known algorithm is
Perceptron (Rosenblatt, 1958), which can converge to a perfect (mistake-free)
classifier after $\Omega(1/\gamma^{2})$ number of iterations, provided the
data is linearly separable with some margin $\gamma>0$ (Novikoff, 1962). Over
subsequent decades, many variants of Perceptron have been developed (Aizerman,
1964; Littlestone, 1988; Wendemuth, 1995; Freund & Schapire, 1999; Cesa-
Bianchi et al., 2005, to name a few). However, somewhat surprisingly, there
has been little progress in substantially improving the fundamental Perceptron
iteration bound presented by Novikoff (1962). It is only recently that a
number of researchers have discovered _accelerated_ variants of the Perceptron
with a faster $\Omega({\sqrt{\log n}}/{\gamma})$ 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 established faster rates using
sophisticated optimization tools. Soheili & Pena (2012) put forward the smooth
Perceptron, framing the objective as a non-smooth strongly-concave
maximization and then applying Nestrov’s excessive gap technique (NEG,
Nesterov, 2005). Yu et al. (2014) proposed the accelerated Perceptron by
furnishing a convex-concave objective that can be solved via the mirror-prox
method (Nemirovski, 2004). Ji et al. (2021) put forward a third
interpretation, obtaining the accelerated rate by minimizing the empirical
risk under exponential loss with a momentum-based normalized gradient descent
algorithm.

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, we consider a general zero-sum
game that involves two players (Abernethy et al., 2018): a main player that
chooses the classifier, and an auxiliary player that picks a distribution over
data. The two players compete with each other by performing _no-regret online
learning_ algorithms (Hazan, 2016; Orabona, 2019), and the goal is to find the
equilibrium of some convex-concave function. We show that, under this dynamic,
all of the existing accelerated Perceptrons can find their equivalent forms.
In particular, these algorithms can be described as two players 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 & Sridharan, 2013; Daskalakis et al., 2018; Wang &
Abernethy, 2018; Daskalakis & Panageas, 2019). However, we emphasize that our
main novelty lies in showing that all of the existing accelerated Perceptrons,
developed with advanced algorithms from different areas, can be perfectly
described under this unified framework. It greatly simplifies the analysis of
accelerated Perceptrons, as their convergence rates can now be easily obtained
by plugging-in off-the-shelf regret bounds of optimistic online learning
algorithms. Moreover, the unified framework reveals a close connection between
the smooth Perceptron and the accelerated Perceptron of Ji et al. (2021):

######  Theorem 1 (informal).

Smooth Perceptron and the accelerated Perceptron of Ji et al. (2021) can be
described as a dynamic where the two players employ the optimistic-follow-the-
regularized-leader (OFTRL) algorithm to play. The main difference is that the
smooth Perceptron outputs the _weighted average_ of the main player’s
historical decisions, while the accelerated Perceptron of Ji et al. (2021)
outputs the _weighted sum_.

Beyond providing a deeper understanding of accelerated Perceptrons, our
framework also provides improved new results for several other important
areas:

  * •

_Implicit bias_ analysis. The seminal work of Soudry et al. (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 ($\ell_{2}$-)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 al. (2018)
show that GD can maximize the margin in an $O(1/\log t)$ rate, and this is
later improved to $O(1/\sqrt{t})$ (Nacson et al., 2019) and then $O(1/t)$ (Ji
& Telgarsky, 2021). The state-of-the-art algorithm is proposed by Ji et al.
(2021), who show that their proposed momentum-based GD has an $O(\log
t/t^{2})$ margin-maximization rate. In this paper, we make two contributions
toward this direction:

    1. 1.

We show that, under our analysis framework, we can easily improve the margin
maximization rate of the algorithm of Ji et al. (2021) from $O(\log t/t^{2})$
to $O(1/t^{2})$, which is an even faster convergence rate where the extra
$\log t$ factor disappears;

    2. 2.

Although previous work has analyzed the implicit bias of GD and momentum-based
GD, it is still unclear how the classical Nesterov’s accelerated gradient
descent (NAG, Nesterov, 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^{2})$ 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 $\ell_{2}$-ball. A more generalized setting is
considered in Gentile (2000), who assumes the feature vectors lie inside an
$\ell_{p}$-ball, with $p\in[2,\infty)$. Their proposed algorithm requires
$\Omega(p/\gamma^{2})$ number of iterations to find a zero-error classifier.
In this paper, we develop a new Perceptron algorithm for this problem under
our framework based on optimism strategies, showing that it enjoys an
accelerated $\Omega(\sqrt{p\log n}/\gamma)$ 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 Preliminaries (Section 3).

#### Accelerated Perceptrons and $p$-norm Perceptron

The study of Perceptron algorithms has an extensive history dating back to the
mid-twentieth century (Rosenblatt, 1958; Novikoff, 1962). However, it is only
recently that progress on improving the fundamental $\Omega(1/\gamma^{2})$
iteration bound of the vanilla Perceptron in the standard setting has been
made. Specifically, the smooth Perceptron proposed by Soheili & Pena (2012)
achieves an $\Omega(\sqrt{\log n}/\gamma)$ rate by maximizing an auxiliary
non-smooth strongly-concave function with NEG (Nesterov, 2005). The same
accelerated rate is later obtained by two other work (Yu et al., 2014; Ji et
al., 2021). The former considers a bi-linear saddle point problem and employs
the mirror-prox method (Nemirovski, 2004). The latter applies momentum-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 enjoy an $O(\operatorname*{poly}(n)\log(1/\gamma))$
convergence rate (Dunagan & Vempala, 2004; Peña & Soheili, 2016; Dadush et
al., 2020). These methods typically call (accelerated) Perceptrons as a
subroutine, and then apply the re-scaling technique to adjust the decision
periodically. Although the dependence on $\gamma$ becomes better, the
polynomial dependence on $n$ of these methods makes them computationally
inefficient for large-scale data sets. In this paper, we focus on accelerated
Perceptrons with $O(\sqrt{\log n}/\gamma)$ rate, and leave explaining the re-
scaling type algorithms as future work.

The $p$-norm Perceptron problem (Gentile & Littlestone, 1999) is a natural
extension of the classical Perceptron setting, which assumes the $p$-norm of
the feature vectors are bounded, where $2\leq p<\infty$. Gentile (2001) shows
that a mirror-descent-style update guarantees an $O(p/\gamma^{2})$ convergence
rate. By contrast, our proposed algorithm achieves a tighter $O(\sqrt{p\log
n}/\gamma)$ 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 al.,
2018). This is usually considered as the _implicit bias introduced by the
optimization methods_ (Soudry et al., 2018). Explaining this phenomenon is a
crucial step towards understanding the generalization ability of _commonly-
used_ optimization methods. For linear separable data, Soudry et al. (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 $\ell_{2}$-maximal margin
classifier. Later, Nacson et al. (2019) show that GD with a function-value-
dependant decreasing step-size enjoys an $O(1/\sqrt{t})$ margin-maximization
rate. Ji & Telgarsky (2021) improve this result to $O(1/t)$ by employing a
faster-decreasing step size. Ji et al. (2021) design a momentum-based GD that
maximizes the margin with an $O(\log t/t^{2})$ rate. However, it remained
unclear whether this rate could be further improved and how to analyze the
margin maximization ability of other classical optimization methods such as
NAG. In this paper, we provide positive answers to both questions.

#### 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
dynamics. The seminal work of Rakhlin & Sridharan (2013) recovers the
classical mirror-prox method (Nemirovski, 2004) with Optimistic online mirror
descent. Abernethy & Wang (2017) show that the well-known Frank-Wolfe
algorithm can be seen as applying (optimistic) online algorithms to compute
the equilibrium of a 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 al., 2018; Wang & Abernethy, 2018; Wang et al., 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 as NEG under the game framework. 3) Although both
Abernethy et al. (2018) and our work analyze NAG, the goals are significantly
different: Abernethy et al. (2018) focus on 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 Preliminaries

#### Notation.

We use lower case bold face letters $\mathbf{x},\mathbf{y}$ to denote vectors,
lower case letters $a,b$ to denote scalars, and upper case letters $A,B$ to
denote matrices. For a vector $\mathbf{x}\in\mathbb{R}^{d}$, we use $x_{i}$ to
denote the $i$-th component of $\mathbf{x}$. For a matrix
$A\in\mathbb{R}^{n\times d}$, let $A_{(i,:)}$ be its $i$-th row, $A_{(:,j)}$
the $j$-th column, and $A_{(i,j)}$ the $i$-th element of the $j$-th column. We
use $\|\cdot\|$ to denote a general norm, $\|\cdot\|_{*}$ its dual norm, and
$\|\cdot\|_{p}$ the $\ell_{p}$-norm. For a positive integer $n$, we denote the
set $\\{1,\dots,n\\}$ as $[n]$, and the $n$-dimensional simplex as
$\Delta^{n}$. Let $E:\Delta^{n}\mapsto\mathbb{R}$ be the negative entropy
function, defined as $E(\mathbf{p})=\sum_{i=1}^{n}p_{i}\log
p_{i},\forall\mathbf{p}\in\Delta^{n}$. For some strongly convex function
$R(\mathbf{w}):\mathcal{W}\mapsto\mathbb{R}$, define the Bregman divergence
between any two points $\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{W}$ as:

$D_{R}(\mathbf{w},\mathbf{w}^{\prime})=R(\mathbf{w})-R(\mathbf{w}^{\prime})-(\mathbf{w}-\mathbf{w}^{\prime})^{\top}\nabla
R(\mathbf{w}^{\prime}).$

#### Online convex optimization (OCO)

Here we review a general _weighted_ OCO framework, proposed by Abernethy et
al. (2018). In each round $t=1,\dots,T$ of this paradigm, a learner first
chooses a decision $\mathbf{z}_{t}$ from a convex set
$\mathcal{Z}\subseteq\mathbb{R}^{d}$, then observes a loss function
$f_{t}(\cdot):\mathcal{Z}\rightarrow\mathbb{R}$ as well as a weight
$\alpha_{t}>0$, and finally updates the decision. The performance of the
learner is measured by the _weighted_ regret, which is defined as
$R_{T}=\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z}_{t})-\min_{\mathbf{z}\in\mathcal{Z}}\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z}).$

Perhaps the most natural method for OCO is follow-the-leader (FTL), which
simply picks the empirically best decision at each round:
$\mathbf{z}_{t}=\operatorname*{argmin}_{\mathbf{z}\in\mathcal{Z}}\sum_{i=1}^{t-1}\alpha_{i}f_{i}(\mathbf{z}).$
However, FTL is unstable, and one can easily find counter-examples where FTL
suffers linear regret (Shalev-Shwartz, 2011). A classical way to address this
limitation is by adding a regularizer to the objective:
$\mathbf{z}_{t}=\operatorname*{argmin}_{\mathbf{z}\in\mathcal{Z}}\eta\sum_{i=1}^{t-1}\alpha_{i}f_{i}(\mathbf{z})+D_{R}(\mathbf{z},\mathbf{z}_{0}),$
where $\eta>0$ is the step size, and $\mathbf{z}_{0}$ is the initial decision.
This method is called follow-the-regularized-leader (Hazan, 2016), and it can
achieve a sub-linear regret bound with appropriately chosen $\eta$. 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 FTRL, Rakhlin & Sridharan, 2013; Orabona, 2019),
given by

$\text{OFTRL}[R,\mathbf{z}_{0},\psi_{t},\eta,\mathcal{Z}]:\mathbf{z}_{t}=\operatorname*{argmin}_{\mathbf{z}\in\mathcal{Z}}\eta\left[\sum_{i=1}^{t-1}\alpha_{i}f_{i}(\mathbf{z})+\alpha_{t}\psi_{t}(\mathbf{z})\right]+D_{R}(\mathbf{z},\mathbf{z}_{0}),$

where an additional function $\psi_{t}$ is added, which is an approximation of
the next loss $f_{t}$. A tighter regret bound can be achieved when $\psi_{t}$
is close enough to $f_{t}$. Next, we introduce two special cases of OFTRL:

$\begin{split}\textstyle\text{OFTL}[\psi_{t},\mathcal{Z}]:\mathbf{z}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{z}\in\mathcal{Z}}\sum_{j=1}^{t-1}\alpha_{j}f_{j}(\mathbf{z})+\alpha_{t}\psi_{t}(\mathbf{z})\\\
\textstyle\text{FTRL}^{+}[R,\mathbf{z}_{0},\eta,\mathcal{Z}]:\mathbf{z}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{z}\in\mathcal{Z}}\eta\cdot\sum_{j=1}^{t}\alpha_{j}f_{j}(\mathbf{z})+\mathcal{D}_{R}(\mathbf{z},\mathbf{z}_{0}).\end{split}$

The first one is Optimistic FTL, where the regularizer is set to be zero. The
second algorithm is FTRL+, which uses $f_{t}$ as the optimistic function
$\psi_{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). 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

Protocol 1 No-regret dynamics with weighted OCO

1: Input: $\\{\alpha_{t}\\}_{t=1}^{T},\mathbf{w}_{0},\mathbf{p}_{0}$.

2: Input: $\textsf{OL}^{\mathbf{w}}$, $\textsf{OL}^{\mathbf{p}}$. // The
online algorithms for choosing $\mathbf{w}$ and $\mathbf{p}$.

3: for $t=1,\dots,T$ do

4: $\mathbf{w}_{t}\leftarrow\textsf{OL}^{\mathbf{w}}$;

5: $\textsf{OL}^{\mathbf{p}}\leftarrow\alpha_{t},\ell_{t}(\cdot)$; // Define
$\ell_{t}(\cdot)=g(\mathbf{w}_{t},\cdot)$

6: $\mathbf{p}_{t}\leftarrow\textsf{OL}^{\mathbf{p}}$;

7: $\textsf{OL}^{\mathbf{w}}\leftarrow\alpha_{t},h_{t}(\cdot)$; // Define
$h_{t}(\cdot)=-g(\cdot,\mathbf{p}_{t})$

8: end for

9: Output:
$\overline{\mathbf{w}}_{T}=\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}\mathbf{w}_{t}.$

Finally, we introduce the framework for using no-regret online algorithms to
solve a zero-sum game. Consider the following general two-player game:

$\begin{split}\max\limits_{\mathbf{w}\in\mathcal{W}}\min\limits_{\mathbf{p}\in\mathcal{Q}}g(\mathbf{w},\mathbf{p}),\end{split}$
(1)

where $g(\mathbf{w},\mathbf{p})$ is a concave-convex function, and
$\mathcal{W}$ and $\mathcal{Q}$ are convex sets. The no-regret framework for
solving (1) is presented in Protocol 1. In each round $t$ of this procedure,
the $\mathbf{w}$-player first picks a decision $\mathbf{w}_{t}\in\mathcal{W}$.
Then, the $\mathbf{p}$-player observes its loss
$\ell_{t}(\cdot)=g(\mathbf{w}_{t},\cdot)$ as well as a weight $\alpha_{t}$.
After that, the $\mathbf{p}$-player picks the decision $\mathbf{p}_{t}$, and
passes it to the $\mathbf{w}$-player. As a consequence, the
$\mathbf{w}$-player observes its loss $h_{t}(\cdot)=-g(\cdot,\mathbf{p}_{t})$
and weight $\alpha_{t}$. Note that both $\ell_{t}$ and $h_{t}$ are convex.
Denote the weighted regret bounds of the two players as $R^{\mathbf{w}}$ and
$R^{\mathbf{p}}$, respectively. Then, we have the following classical
conclusion. The proof is shown in Appendix B.

######  Theorem 2.

Define
$m(\mathbf{w})=\min_{\mathbf{p}\in\mathcal{Q}}g(\mathbf{w},\mathbf{p}),$ and
$\overline{\mathbf{w}}$ the weighted average of
$\\{\mathbf{w}_{t}\\}_{t=1}^{T}$. Then we have that
$\forall\mathbf{w}\in\mathcal{W}$,
$m(\mathbf{w})-m(\overline{\mathbf{w}}_{T})\leq(\sum_{t=1}^{T}\alpha_{t})^{-1}\left({R}^{\mathbf{p}}+{R}^{\mathbf{w}}\right).$

##  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 1. For clarity, we use $\mathbf{v}_{t}$
to denote the classifier updates in the original algorithms, and
$\mathbf{w}_{t}$ the corresponding updates in the equivalent forms under
Protocol 1.

###  4.1 Binary Linear classification and Perceptron

We focus on the binary linear classification problem, which dates back to the
pioneering work of Rosenblatt (1958). Let
$\mathcal{S}=\\{\mathbf{x}^{(i)},y^{(i)}\\}_{i=1}^{n}$ be a linear-separable
set of $n$ training examples, where $\mathbf{x}^{(i)}\in\mathbb{R}^{d}$ is the
feature vector of the $i$-th example, and $y^{(i)}\in\\{-1,1\\}$ is the
corresponding label. The goal is to efficiently find a linear classifier
$\mathbf{w}\in\mathbb{R}^{d}$ that correctly separates all data points. More
formally, let
$A=[y^{(1)}\mathbf{x}^{(1)},\dots,y^{(n)}\mathbf{x}^{(n)}]^{\top}$ be the
matrix that contains all of the data. Then we would like to find a
$\mathbf{w}\in\mathbb{R}^{d}$ such that

$\min\limits_{i\in[n]}A_{(i,:)}\mathbf{w}>0.$ (2)

This goal can be reformulated as a min-max optimization problem:

$\max\limits_{\mathbf{w}\in\mathbb{R}^{d}}\min\limits_{i\in[n]}A_{(i,:)}\mathbf{w}=\max\limits_{\mathbf{w}\in\mathbb{R}^{d}}\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w},$
(3)

where, at the RHS of (3), $\min_{i\in[n]}A_{(i,:)}\mathbf{w}$ is rewritten as
$\min_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w}$. The two
expressions are equivalent since the optimal distribution
$\mathbf{p}\in\Delta^{n}$ will always put all weight on _one_ training example
(i.e., one row) in $A$. For any $\mathbf{w}\in\mathbb{R}^{d}$, let
$\gamma(\mathbf{w})=\min_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w}$
be the _margin_ of $\mathbf{w}$, and we introduce the following standard
assumption.

######  Assumption 1.

We assume that feature vectors are bounded, i.e.,
$\|\mathbf{x}^{(i)}\|_{2}\leq 1$ for all $i\in[n]$, and that there exists a
$\mathbf{w}^{*}\in\mathbb{R}^{d}$, such that $\|\mathbf{w}^{*}\|_{2}=1$ and
$\gamma(\mathbf{w}^{*})=\gamma>0$.

###  4.2 Smooth Perceptron

Algorithm 1 Smooth Perceptron (Soheili & Pena, 2012)

Initialization : $\theta_{0}=\frac{2}{3}$, $\mu_{0}=4$,
$\mathbf{v}_{0}=\frac{A^{\top}\mathbf{1}}{n}$

Initialization : $\mathbf{q}_{0}=\mathbf{q}_{\mu_{0}}(\mathbf{v}_{0}),$ where
$\mathbf{q}_{\mu}(\mathbf{v})=\operatorname*{argmin}_{\mathbf{q}\in\Delta^{n}}\mathbf{q}^{\top}A\mathbf{v}+\mu
D_{E}\left(\mathbf{q},\frac{\mathbf{1}}{n}\right)$.

for $t=1,\dots,T-1$ do

$\mathbf{v}_{t}=(1-\theta_{t-1})(\mathbf{v}_{t-1}+\theta_{t-1}A\mathbf{q}_{t-1})+\theta^{2}_{t-1}A\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})$

$\mu_{t}=(1-\theta_{t-1})\mu_{t-1}$

$\mathbf{q}_{t}=(1-\theta_{t-1})\mathbf{q}_{t-1}+\theta_{t-1}\mathbf{q}_{\mu_{t}}(\mathbf{v}_{t})$

$\theta_{t}=\frac{2}{t+3}$

end for

Output: $\mathbf{v}_{T-1}$

$\begin{split}\textsf{OL}^{\mathbf{w}}=\text{OFTL}\left[h_{t-1}(\cdot),\mathbb{R}^{d}\right]\Leftrightarrow{}&\mathbf{w}_{t}=\operatorname*{argmin}\limits_{\mathbf{w}\in\mathbb{R}^{d}}\sum_{j=1}^{t-1}\alpha_{j}h_{j}(\mathbf{w})+\alpha_{t}h_{t-1}(\mathbf{w})\\\
\textsf{OL}^{\mathbf{p}}=\text{FTRL}^{+}\left[{E}(\cdot),\frac{\textbf{1}}{n},\frac{1}{4},\Delta^{n}\right]\Leftrightarrow{}&\mathbf{p}_{t}=\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\frac{1}{4}\sum_{s=1}^{t}\alpha_{s}\ell_{s}(\mathbf{p})+\mathcal{D}_{E}\left(\mathbf{p},\frac{\textbf{1}}{n}\right)\end{split}$
Output: $\overline{\mathbf{w}}_{T}$

In order to solve (3), the vanilla Perceptron repeatedly moves the direction
of the classifier to 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 1. The key idea is to find a
classifier $\mathbf{v}\in\mathbb{R}^{d}$ that maximizes the following
$\ell_{2}$-regularized function:

$\psi(\mathbf{v})=-\frac{1}{2}\|\mathbf{v}\|_{2}^{2}+\min_{\mathbf{q}\in\Delta^{n}}\mathbf{q}^{\top}A\mathbf{v},$
(4)

which is _non-smooth strongly-concave_ with respect to $\mathbf{v}$. Under
Assumption 1, Soheili & Pena (2012) show that the maximum value of
$\psi(\mathbf{v})$ is
$\max_{\mathbf{v}\in\mathbb{R}^{d}}\psi(\mathbf{v})=\gamma^{2}/2$, and a
classifier $\mathbf{v}\in\mathbb{R}^{d}$ satisfies (2) when
$\psi(\mathbf{v})\geq 0$. In order to solve (4), Soheili & Pena (2012) apply
the classical Nesterov’s excessive gap technique (Nesterov, 2005) for strongly
concave functions. This algorithm introduces a smoothed approximation of (4),
which is parameterized by some constant $\mu>0$, and defined as

$\textstyle\psi_{\mu}(\mathbf{v})=-\frac{1}{2}\|\mathbf{v}\|_{2}^{2}+\min_{\mathbf{q}\in\Delta^{n}}\left[\mathbf{q}^{\top}A\mathbf{v}+\mu
D_{E}\left(\mathbf{q},\frac{\textbf{1}}{n}\right)\right],$ (5)

which bounds the function in (4) from below, i.e.,
$\forall\mathbf{v}\in\mathbb{R}^{d},\mu>0$,
$\psi_{\mu}(\mathbf{v})\leq\psi(\mathbf{v})+\mu\log n$. Then, the algorithm
performs a sophisticated update rule such that the excessive gap condition
holds $\forall t\geq 1$:
$\gamma^{2}/2\leq\|A\mathbf{v}_{t}\|^{2}/2\leq\psi_{\mu}(\mathbf{v}_{t})$. We
refer to Soheili & Pena (2012) for more details.

Soheili & Pena (2012) show that the smooth Perceptron can output a positive-
margin classifier after $\Omega(\sqrt{\log n}/\gamma)$ iterations. However,
the analysis is quite involved, which heavily relies on the complicated
relationship between $\psi(\mathbf{v}_{t})$, $\psi_{\mu}(\mathbf{v}_{t})$ and
$\|A\mathbf{v}_{t}||^{2}$. In the following, we provide a no-regret
explanation of this algorithm and then show that the convergence rate can be
easily obtained under our framework. Specifically, we define the objective
function in Protocol 1 as

$g(\mathbf{w},\mathbf{p})=\mathbf{p}^{\top}A\mathbf{w}-\frac{1}{2}\|\mathbf{w}\|_{2}^{2},$
(6)

and provide the equivalent expression in the second box of Algorithm 1. More
specifically, we have the following proposition. The proof is given in
Appendix C.1.

######  Proposition 1.

Let $\alpha_{t}=t$. Then the two interpretations of the smooth Perceptron in
Algorithm 1 are the same, in the sense that
$\mathbf{v}_{T-1}=\overline{\mathbf{w}}_{T}$, and
$\mathbf{q}_{T-1}=\frac{\sum_{t=1}^{T}\alpha_{t}\mathbf{p}_{t}}{\sum_{t=1}^{T}\alpha_{t}}.$

Proposition 1 shows that, under Protocol 1, the smooth Perceptron can be seen
as optimizing (6) by implementing two online learning algorithms: in each
round $t$, the $\mathbf{w}$-player applies OFTL with $\psi_{t}=h_{t-1}$, a
decision which the $\mathbf{p}$-player subsequently observes and responds with
FTRL+. Moreover, we obtain theoretical guarantees for the smooth Perceptron
based on Theorem 2, matching the convergence rate provided by Soheili & Pena
(2012).

######  Theorem 3.

Let $\alpha_{t}=t$. Under Protocol 1, the regret of the two players of
Algorithm 1 is bounded by ${R}^{\mathbf{w}}\leq
2\sum_{t=1}^{T}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2}$ and
${R}^{\mathbf{p}}\leq 4\log
n-2\sum_{t=1}^{T}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2}$. Moreover,
$\overline{\mathbf{w}}_{T}$ has non-negative margin when
$T=\Omega(\frac{\sqrt{\log n}}{\gamma})$.

###  4.3 Accelerated Perceptron via ERM

Algorithm 2 Accelerated Perceptron of Ji et al. (2021)

Input:
$\mathbf{q}_{0}=\frac{\textbf{1}}{n},\mathbf{v}_{0}=\mathbf{0},\mathbf{g}_{0}=\mathbf{0},\theta_{t-1}=\frac{t}{2(t+1)},\beta_{t}=\frac{t}{t+1}$.

for $t=1,\dots,T$ do

$\mathbf{v}_{t}=\mathbf{v}_{t-1}-\theta_{t-1}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})$

for $i=1,\dots,n$ do

$q_{t,i}=\frac{\exp(-y^{(i)}\mathbf{v}_{t}^{\top}\mathbf{x}^{(i)})}{\sum_{j=1}^{n}\exp(-y^{(j)}\mathbf{v}_{t}^{\top}\mathbf{x}^{(j)})}$

end for

$\mathbf{g}_{t}=\beta_{t}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t})$

end for

Output: $\mathbf{v}_{T}$

$\begin{split}\textsf{OL}^{\mathbf{w}}=\text{OFTL}\left[h_{t-1}(\cdot),\mathbb{R}^{d}\right]\Leftrightarrow{}&\mathbf{w}_{t}=\operatorname*{argmin}\limits_{\mathbf{w}\in\mathbb{R}^{d}}\sum_{j=1}^{t-1}\alpha_{j}h_{j}(\mathbf{w})+\alpha_{t}h_{t-1}(\mathbf{w})\\\
\textsf{OL}^{\mathbf{p}}=\text{FTRL}^{+}\left[{E}(\cdot),\frac{\textbf{1}}{n},\frac{1}{4},\Delta^{n}\right]\Leftrightarrow{}&\mathbf{p}_{t}=\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\frac{1}{4}\sum_{s=1}^{t}\alpha_{s}\ell_{s}(\mathbf{p})+\mathcal{D}_{E}\left(\mathbf{p},\frac{\textbf{1}}{n}\right)\end{split}$
Output: $\overline{\mathbf{w}}_{T}$

Since binary linear classification is a (and perhaps the most fundamental)
supervised machine learning problem, it can be naturally solved via empirical
risk minimization (ERM). This idea is adopted by Ji et al. (2021), who
consider the following ERM problem:

$\min\limits_{\mathbf{v}\in\mathbb{R}^{d}}R(\mathbf{v})=\frac{1}{n}\sum_{i=1}^{n}\ell(-y^{(i)}\mathbf{v}^{\top}\mathbf{x}^{(i)}),$
(7)

where $\ell(z)=\exp(z)$ is the exponential loss. To minimize (7), Ji et al.
(2021) propose the following normalized momentum-based gradient descent (NMGD)
algorithm

$\begin{cases}\mathbf{g}_{t}=\beta_{t}\left(\mathbf{g}_{t}-\frac{\nabla
R(\mathbf{v}_{t})}{R(\mathbf{v}_{t})}\right)\\\
\mathbf{v}_{t+1}=\mathbf{v}_{t}-\theta_{t}\left(\mathbf{g}_{t}+\frac{\nabla
R(\mathbf{v}_{t})}{R(\mathbf{v}_{t})}\right),\end{cases}$ (8)

where $\nabla R(\mathbf{v}_{t})/R(\mathbf{v}_{t})$ is the normalized gradient,
and $\mathbf{g}_{t}$ can be seen as momentum. Ji et al. (2021) show that NMGD
can converge to a classifier with a positive margin after $O(1/\gamma^{2})$
iterations. Based on the property of the normalized gradient $\nabla
R(\mathbf{v}_{t})/R(\mathbf{v}_{t})$, they also provide primal-dual form of
the algorithm (presented in the first-box of Algorithm 2), which can be
considered as applying Nesterov’s accelerated gradient descent in the _dual
space_ (Ji et al., 2021) .

For the accelerated Perceptron of Ji et al. (2021), we set
$g(\mathbf{w},\mathbf{p})=\mathbf{p}^{\top}A\mathbf{w}-\frac{1}{2}\|\mathbf{w}\|_{2}^{2}$
and provide its equivalent form at the second box in Algorithm 2.
Specifically, we have the following proposition.

######  Proposition 2.

Let $\alpha_{t}=t$. Then the two interpretations of the accelerated Perceptron
in Algorithm 2 are the same, in the sense that $\mathbf{q}_{T}=\mathbf{p}_{T}$
and
$\mathbf{v}_{T}=\frac{1}{4}\sum_{t=1}^{T}\alpha_{t}\mathbf{w}_{t}=\frac{1}{4}\left(\sum_{t=1}^{T}\alpha_{t}\right)\cdot\overline{\mathbf{w}}_{T}$.

#### Remark

Note that in Ji et al. (2021), the parameter $\theta_{t-1}$ is set to be 1. We
observe that this causes a mismatch between the weights and
$\mathbf{w}_{t}^{\prime}$s in the output (when $\theta_{t-1}=1$,
$\mathbf{v}_{T}$ will become $\sum_{t=1}^{T}\alpha_{t+1}\mathbf{w}_{t}$
instead of $\sum_{t=1}^{T}\alpha_{t}\mathbf{w}_{t}$). Our no-regret analysis
suggests that $\theta_{t-1}$ should be configured as $\frac{t}{2(t+1)}$, and
later we will show that this procedure helps eliminate the $\log t$ factor in
the convergence rate.

The proposition above reveals that the smooth Perceptron and the accelerated
Perceptron of Ji et al. (2021) are closely related. The main difference is
that the accelerated Perceptron of Ji et al. (2021) outputs the weighted sum
of all $\mathbf{w}_{t}$’s, instead of the weighted average. The rationale
behind this phenomenon is that, instead of the margin, Ji et al. (2021) use
the _normalized_ margin to measure the performance of the algorithm, defined
as

$\overline{\gamma}(\mathbf{v})=\frac{\min_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{v}}{\|\mathbf{v}\|_{2}}.$

They not only prove $\overline{\gamma}(\mathbf{v}_{T})>0$ (which directly
implies $\gamma(\mathbf{v}_{T})>0$), but also show
$\overline{\gamma}(\mathbf{v}_{T})=\Omega(\gamma-\frac{\log T}{\gamma
T^{2}})$. This guarantee is more powerful than the previous results, as it
implies that the _normalized margin can be maximized_ in an $O(\log t/t^{2})$
rate. When $t$ approaches $\infty$, the direction of $\mathbf{v}_{T}$ will
converge to that of the maximal margin classifier. We show that a better
margin-maximization rate can be directly obtained under our framework with the
parameter setting in Algorithm 2.

######  Theorem 4.

Let $\alpha_{t}=t$. Under Protocol 1, the regret of the two players of
Algorithm 2 is bounded by ${R}^{\mathbf{w}}\leq
2\sum_{t=1}^{T}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2}$ and
${R}^{\mathbf{p}}\leq 4\log
n-2\sum_{t=1}^{T}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2}$. Moreover,
$\overline{\mathbf{w}}_{T}$ has a non-negative margin when
$T=\Omega({\sqrt{\log n}}/{\gamma})$ and
$\overline{\gamma}(\mathbf{v}_{T})=\Omega(\gamma-\frac{8\log n}{\gamma
T(T+1)})$.

###  4.4 Accelerated Perceptron of Yu et al. (2014)

Finally, Yu et al. (2014) considers applying the mirror-prox algorithm to
solve the max-min optimization problem:

$\max\limits_{\|\mathbf{w}\|_{2}\leq
1}\min_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w},$ (9)

As discovered by Rakhlin & Sridharan (2013), 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 al. (2014) can be recovered as two-players applying OMD to
solve (9). The algorithmic details and their analysis are postponed to
Appendix C.5, which we summarize as follows (formalized in Theorems 8 and 9):

######  Theorem 5 (informal).

Let $g(\mathbf{w},\mathbf{p})=\mathbf{p}^{\top}A\mathbf{w}$. The Perceptron of
Yu et al. (2014) can be described under Protocol 1, where both players apply
OMD endowed with the appropriate parameters. Moreover, under Assumption 1,
$\overline{\mathbf{w}}_{T}$ has a non-negative margin when
$T=\Omega\left(\frac{\sqrt{\log n}}{\gamma}\right)$.

##  5 Beyond Perceptrons

In Section 4.3, we improved the convergence rate of the algorithm in Ji et al.
(2021) by an $O(\log t)$ factor. This section shows that our framework
benefits a wide range of other problems.

###  5.1 Margin Maximization by Nesterov’s Accelerated Gradient Descent

Algorithm 3 NAG

Input: $\mathbf{v}_{0}=\mathbf{0},\mathbf{s}_{0}=\mathbf{0}$.

for $t=1,\dots,T$ do

$\mathbf{u}_{t}=\mathbf{s}_{t-1}+\frac{1}{2(t-1)}\mathbf{v}_{t-1}$

$\mathbf{v}_{t}=\mathbf{v}_{t-1}-\eta_{t}\nabla R(\mathbf{u}_{t})$

$\mathbf{s}_{t}=\mathbf{s}_{t-1}+\frac{1}{2(t+1)}\mathbf{v}_{t}$

end for

Output: $\mathbf{s}_{T}$

$\begin{split}\textsf{OL}^{\mathbf{p}}=\text{OFTRL}\left[{E}(\cdot),\frac{\textbf{1}}{n},\frac{1}{4},\ell_{t-1}(\cdot),\Delta^{n}\right]\Leftrightarrow\mathbf{p}_{t}=\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}{}&\frac{1}{4}\left[\sum_{s=1}^{t-1}\alpha_{s}\ell_{s}(\mathbf{p})+\alpha_{t}\ell_{t-1}(\mathbf{p})\right]\\\
{}&+\mathcal{D}_{E}\left(\mathbf{p},\frac{\textbf{1}}{n}\right)\\\
\textsf{OL}^{\mathbf{w}}=\text{FTRL}^{+}[0,0,1,\mathbb{R}^{d}]\Leftrightarrow\mathbf{w}_{t}=\operatorname*{argmin}\limits_{\mathbf{w}\in\mathbb{R}^{d}}{}&\sum_{j=1}^{t}\alpha_{j}h_{j}(\mathbf{w})\end{split}$
Output:
$\widetilde{\mathbf{w}}_{T}=\frac{\sum_{t=1}^{T}\alpha_{t}}{4}\overline{\mathbf{w}}_{T}.$

One major task for the implicit bias study is to explain why _commonly-used_
first-order optimization methods generalize well. For linearly separable data,
previous work proves that GD and momentum-based GD prefers the
$\ell_{2}$-maximal margin classifier by showing that they can maximize the
margin. In this part, we show that the well-known Nesterov’s accelerated
gradient descent (NAG), with appropriately chosen parameters, can maximize the
margin in an $O(1/\gamma^{2})$ rate. Specifically, following previous work, we
consider the ERM problem in (7) and apply Nesterov’s accelerated gradient
descent (NAG) to minimize the objective function. The details of the algorithm
are summarized in the first box of Algorithm 3, and its equivalent form under
Protocol 1 is presented in the second box of Algorithm 3. For the NAG
algorithm, we set the objective function as
$g(\mathbf{w},\mathbf{p})=\mathbf{p}^{\top}A\mathbf{w}-\frac{1}{2}\|\mathbf{w}\|_{2}^{2}$,
and have the following conclusion.

######  Theorem 6.

Let $\eta_{t}=\frac{t}{R(\mathbf{u}_{t})}$ and $\alpha_{t}=t$. Then, the two
expressions in Algorithm 3 are equivalent, in the sense that
$\mathbf{s}_{T}=\widetilde{\mathbf{w}}_{T}$. Moreover,
$\frac{\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{s}_{T}}{\|\mathbf{s}_{T}\|_{2}}\geq\gamma-\frac{8\log
n+2}{T(T+1)\gamma}.$

#### Remark

Theorem 6 indicates that NAG can also maximize the margin in an $O(1/T^{2})$
rate. Note that, _in Algorithm 3, the $\mathbf{p}$-player plays first and the
$\mathbf{w}$-player second, while, in Algorithm 2, it is the other way
around_. This difference makes sense as Algorithm 3 can be considered as
applying Nesterov’s acceleration in the dual space (Ji et al., 2021), while
Algorithm 3 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
Gentile (2000). Compared 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, we assume: $\forall i\in[n]$,
$\|\mathbf{x}^{(i)}\|_{p}\leq 1$, where $p\in[2,\infty)$. Moreover, assume
there exists a $\mathbf{w}^{*}\in\mathbb{R}^{d}$, such that
$\|\mathbf{w}^{*}\|_{q}\leq 1$ and
$\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w}^{*}\geq\gamma$.
Here, $\|\cdot\|_{q}$ is the dual norm of $\|\cdot\|_{p}$; i.e.,
$\frac{1}{p}+\frac{1}{q}=1$ and $q\in(1,2]$.

Algorithm 4 Accelerated algorithm for the $p$-norm perceptron

$\begin{split}&\textsf{OL}^{\mathbf{w}}=\text{OFTRL}\left[\frac{1}{2(q-1)}\|\cdot\|_{q}^{2},\textbf{0},\eta^{\mathbf{w}},h_{t-1}(\cdot),\mathbb{R}^{d}\right]\Leftrightarrow\\\
&\hskip
56.9055pt\mathbf{w}_{t}=\operatorname*{argmin}\limits_{\mathbf{w}\in\mathbb{R}^{d}}\eta^{\mathbf{w}}\sum_{j=1}^{t-1}\alpha_{j}h_{j}(\mathbf{w})+\alpha_{t}h_{t-1}(\mathbf{w})+D_{\frac{1}{2(q-1)}\|\cdot\|_{q}^{2}}\left(\mathbf{w},\mathbf{0}\right)\\\
{}&\textsf{OL}^{\mathbf{p}}=\text{FTRL}^{+}[E,\frac{\mathbf{1}}{n},\eta^{p},\Delta^{n}]\Leftrightarrow\mathbf{p}_{t}=\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\eta^{\mathbf{p}}\sum_{s=1}^{t}\alpha_{s}\ell_{s}(\mathbf{p})+\mathcal{D}_{E}\left(\mathbf{p},\frac{\textbf{1}}{n}\right)\end{split}$

Output: $\overline{\mathbf{w}}_{T}=\frac{1}{T}\sum_{s=1}^{T}\mathbf{w}_{s}$.

Under Assumption 2, Gentile (2000) proposes a mirror-descent style algorithm
that achieves an $\Omega((1-p)/\gamma^{2})$ convergence rate. In the
following, we provide a new algorithm with a better rate. Specifically, under
Protocol 1, we define the objective function as
$g(\mathbf{w},\mathbf{p})=\mathbf{p}^{\top}A\mathbf{w},$ and introduce
Algorithm 4, wherein the $\mathbf{w}$-player uses OFTRL with regularizer
$\frac{1}{2(q-1)}\|\cdot\|_{q}^{2}$, which is $1$-strongly convex w.r.t. the
$q$-norm (Orabona, 2019). On the other hand, the $\mathbf{q}$-player employs
the FTRL+ algorithm. We have the following result.

######  Theorem 7.

Let $\alpha_{t}=1$, $\eta^{\mathbf{p}}=1/\eta^{\mathbf{w}}$, and
$\eta^{\mathbf{w}}=\sqrt{\frac{1}{2(q-1)\log n}}$. Then the output
$\overline{\mathbf{w}}_{T}$ of Algorithm 4 has a non-negative margin when
$T=\Omega\left({\sqrt{2(p-1)\log n}}/{\gamma}\right)$.

##  6 Conclusion

In this paper, we provide a unified analysis for the existing accelerated
Perceptrons, and obtain improved results for a series of problems. In the
future, we will explore how to extend our framework to other closely related
areas, such as semi-definite programming (Garber & Hazan, 2011) and
generalized margin maximization (Sun et al., 2022).

## References

  * Abernethy et al. (2018) Jacob Abernethy, Kevin A Lai, Kfir Y Levy, and Jun-Kun Wang.  Faster rates for convex-concave games.  In _Proceedings of the 31st Annual Conference on Learning Theory_ , pp. 1595–1625, 2018.
  * Abernethy & Wang (2017) Jacob D Abernethy and Jun-Kun Wang.  On frank-wolfe and equilibrium computation.  _Advances in Neural Information Processing Systems 30_ , 30, 2017\.
  * Aizerman (1964) Mark A Aizerman.  Theoretical foundations of the potential function method in pattern recognition learning.  _Automation and remote control_ , 25:821–837, 1964.
  * Bishop (2007) Christopher M. Bishop.  _Pattern Recognition and Machine Learning_.  Springer, 2007.
  * Cesa-Bianchi et al. (2005) Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile.  A second-order perceptron algorithm.  _SIAM Journal on Computing_ , 34(3):640–668, 2005\.
  * Dadush et al. (2020) Daniel Dadush, Laszlo A Vegh, and Giacomo Zambelli.  Rescaling algorithms for linear conic feasibility.  _Mathematics of Operations Research_ , 45(2):732–754, 2020.
  * Daskalakis & Panageas (2019) C Daskalakis and Ioannis Panageas.  Last-iterate convergence: Zero-sum games and constrained min-max optimization.  In _10th Innovations in Theoretical Computer Science conference_ , 2019.
  * Daskalakis et al. (2018) Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training gans with optimism.  In _International Conference on Learning Representations_ , 2018.
  * Dunagan & Vempala (2004) 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.
  * Freund & Schapire (1999) Yoav Freund and Robert E Schapire.  Large margin classification using the perceptron algorithm.  _Machine learning_ , 37(3):277–296, 1999.
  * Garber & Hazan (2011) Dan Garber and Elad Hazan.  Approximating semidefinite programs in sublinear time.  _Advances in Neural Information Processing Systems 24_ , 2011.
  * Gentile (2000) Claudio Gentile.  A new approximate maximal margin classification algorithm.  _Advances in Neural Information Processing Systems 13_ , 2000.
  * Gentile (2001) Claudio Gentile.  A new approximate maximal margin classification algorithm.  _Journal of Machine Learning Research_ , 2:213–242, 2001\.
  * Gentile & Littlestone (1999) 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.
  * Hazan (2016) Elad Hazan.  Introduction to online convex optimization.  _Foundations and Trends in Optimization_ , 2(3-4):157–325, 2016.
  * Ji & Telgarsky (2021) Ziwei Ji and Matus Telgarsky.  Characterizing the implicit bias via a primal-dual analysis.  In _Proceedings of the 32nd International Conference on Algorithmic Learning Theory_ , pp. 772–804, 2021.
  * Ji et al. (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.
  * Littlestone (1988) Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine learning_ , 2(4):285–318, 1988.
  * Nacson et al. (2019) Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry.  Convergence of gradient descent on separable data.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pp. 3420–3428, 2019.
  * Nemirovski (2004) 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–251, 2004.
  * Nesterov (2005) Yu Nesterov.  Excessive gap technique in nonsmooth convex minimization.  _SIAM Journal on Optimization_ , 16(1):235–249, 2005.
  * Nesterov (1988) Yurii Nesterov.  On an approach to the construction of optimal methods of minimization of smooth convex functions.  _Ekonomika i Mateaticheskie Metody_ , 24(3):509–517, 1988.
  * Novikoff (1962) 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.
  * Orabona (2019) Francesco Orabona.  A modern introduction to online learning.  _arXiv preprint arXiv:1912.13213_ , 2019.
  * Peña & Soheili (2016) Javier Peña and Negar Soheili.  A deterministic rescaled perceptron algorithm.  _Mathematical Programming_ , 155(1):497–510, 2016\.
  * Rakhlin & Sridharan (2013) Sasha Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  In _Advances in Neural Information Processing Systems 26_ , pp. 3066–3074, 2013.
  * Rosenblatt (1958) Frank Rosenblatt.  The perceptron: a probabilistic model for information storage and organization in the brain.  _Psychological review_ , 65(6):386, 1958.
  * Shalev-Shwartz (2011) Shai Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends in Machine Learning_ , 4(2):107–194, 2011.
  * Soheili & Pena (2012) Negar Soheili and Javier Pena.  A smooth perceptron algorithm.  _SIAM Journal on Optimization_ , 22(2):728–737, 2012.
  * Soudry et al. (2018) Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  _The Journal of Machine Learning Research_ , 19(1):2822–2878, 2018.
  * Sun et al. (2022) Haoyuan Sun, Kwangjun Ahn, Christos Thrampoulidis, and Navid Azizan.  Mirror descent maximizes generalized margin and can be implemented efficiently.  _arXiv preprint arXiv:2205.12808_ , 2022.
  * Wang & Abernethy (2018) 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.
  * Wang et al. (2021) Jun-Kun 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.11309_ , 2021.
  * Wendemuth (1995) A Wendemuth.  Learning the unlearnable.  _Journal of Physics A: Mathematical and General_ , 28(18):5423, 1995.
  * Yu et al. (2014) Adams Wei Yu, Fatma Kilinc-Karzan, and Jaime Carbonell.  Saddle points and accelerated perceptron algorithms.  In _International Conference on Machine Learning_ , pp. 1827–1835, 2014.

##  A Regret bounds on OCO algorithms

Protocol 2 A set of useful algorithms for the weighted OCO

for $t=1,\dots,T$ do

$\displaystyle\textstyle\text{OFTRL}[R,\mathbf{z}_{0},\eta,\psi_{t},\mathcal{Z}]:\mathbf{z}_{t}={}$
$\displaystyle\operatorname*{argmin}\limits_{\mathbf{z}\in\mathcal{Z}}\eta\left[\sum_{j=1}^{t-1}\alpha_{j}f_{j}(\mathbf{z})+\alpha_{t}\psi_{t}(\mathbf{z})\right]+D_{R}(\mathbf{z},\mathbf{z}_{0})$
$\displaystyle\text{OMD}[R,\widehat{\mathbf{z}}_{0},\eta,\psi_{t},\mathcal{Z}]:{\mathbf{z}}_{t}={}$
$\displaystyle\operatorname*{argmin}\limits_{\mathbf{z}\in\mathcal{Z}}\eta\left\langle\alpha_{t}\nabla\psi_{t}(\mathbf{z}_{t-1}),\mathbf{z}\right\rangle+\mathcal{D}_{R}(\mathbf{z},\widehat{\mathbf{z}}_{t-1})$
$\displaystyle{}{}{}{}\widehat{\mathbf{z}}_{t}={}$
$\displaystyle\operatorname*{argmin}\limits_{\mathbf{z}\in\mathcal{Z}}\eta\left\langle\alpha_{t}\nabla
f_{t}(\mathbf{z}_{t}),\mathbf{z}\right\rangle+\mathcal{D}_{R}(\mathbf{z},\widehat{\mathbf{z}}_{t-1})$
$\displaystyle\textstyle\text{OFTL}[\psi_{t},\mathcal{Z}]:\mathbf{z}_{t}={}$
$\displaystyle\operatorname*{argmin}\limits_{\mathbf{z}\in\mathcal{Z}}\sum_{j=1}^{t-1}\alpha_{j}f_{j}(\mathbf{z})+\alpha_{t}\psi_{t}(\mathbf{z})$
$\displaystyle\text{FTRL}^{+}[R,\mathbf{z}_{0},\eta,\mathcal{Z}]:\mathbf{z}_{t}={}$
$\displaystyle\operatorname*{argmin}\limits_{\mathbf{z}\in\mathcal{Z}}\eta\cdot\sum_{j=1}^{t}\alpha_{j}f_{j}(\mathbf{z})+\mathcal{D}_{R}(\mathbf{z},\mathbf{z}_{0})$

end for

######  Lemma 1 (Lemma 13 of Wang et al. (2021)).

Let
$\widetilde{\mathbf{z}}_{t}=\operatorname*{argmin}_{\mathbf{z}\in\mathcal{Z}}\sum_{s=1}^{t-1}\alpha_{s}f_{s}(\mathbf{z}_{s})$.
Assume $f_{t}$ and $\psi_{t}$ are $\lambda$-strongly convex w.r.t. some norm
$\|\cdot\|$. Then, for the OFTL$[\psi_{t},\mathcal{Z}]$ algorithm, the regret
is bounded by

$\begin{split}\forall\mathbf{z}\in\mathcal{Z},\ \
\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z}_{t})-\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z})\leq{}&\sum_{t=1}^{T}\alpha_{t}(f_{t}(\mathbf{z}_{t})-f_{t}(\widetilde{\mathbf{z}}_{t+1}))-\alpha_{t}(\psi_{t}(\mathbf{z}_{t})-\psi_{t}(\widetilde{\mathbf{z}}_{t+1}))\\\
{}&-\frac{1}{2}\sum_{t=1}^{T}\lambda\alpha_{t}\|\mathbf{z}_{t}-\widetilde{\mathbf{z}}_{t+1}\|^{2}.\end{split}$
(10)

######  Lemma 2 (Lemma 13 of Wang et al. (2021)).

For FTRL${}^{+}[R,\mathbf{z}_{0},\eta,\mathcal{Z}]$ algorithm, suppose $R$ is
$\beta$-strongly convex w.r.t some norm $\|\cdot\|$ and each $f_{t}(\cdot)$ is
$\lambda$-strongly convex w.r.t. the same norm, where $\lambda$ may be 0. Then

$\begin{split}\forall\mathbf{z}\in\mathcal{Z},\ \
\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z}_{t})-\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z})\leq{}&\frac{R(\mathbf{z})-R(\mathbf{z}_{0})}{\eta}-\sum_{t=1}^{T}\left(\frac{\lambda\sum_{s=1}^{t-1}\alpha_{s}}{2}+\frac{\beta}{2\eta}\right)\|\mathbf{z}_{t}-\mathbf{z}_{t-1}\|^{2}.\end{split}$
(11)

######  Lemma 3 (Theorem 7.35 of Orabona (2019)).

For the OFTRL$[R,\mathbf{z}_{0},\eta,\psi_{t},\mathcal{Z}]$ algorithm, assume
$R$ is 1-strongly convex w.r.t. some norm $\|\cdot\|$. Then the regret is
bounded by

$\begin{split}\forall\mathbf{z}\in\mathcal{Z},\ \
\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z}_{t})-\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z})\leq{}&\frac{R(\mathbf{z})-R(\mathbf{z}_{0})}{\eta}+\sum_{t=1}^{T}\left[\frac{\|\alpha_{t}\nabla
f_{t}(\mathbf{z}_{t})-\alpha_{t}\nabla\psi_{t}(\mathbf{z}_{t})\|_{*}^{2}}{2/\eta}.\right]\end{split}$
(12)

######  Lemma 4 (Lemma 1 of Rakhlin & Sridharan (2013)).

For the OMD$[R,\widehat{\mathbf{z}}_{0},\eta,\psi_{t},\mathcal{Z}]$ algorithm,
suppose $R$ is 1-strongly convex w.r.t. some norm $\|\cdot\|$. Then the regret
is bounded by

$\begin{split}\forall\mathbf{z}\in\mathcal{Z},\ \
\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z}_{t})-\sum_{t=1}^{T}\alpha_{t}f_{t}(\mathbf{z})\leq{}&\frac{\mathcal{D}_{R}(\mathbf{z},\widehat{\mathbf{z}}_{0})}{\eta}+\sum_{t=1}^{T}\|\alpha_{t}\nabla
f_{t}(\mathbf{z}_{t})-\alpha_{t}\nabla\psi_{t}(\hat{\mathbf{z}}_{t-1})\|_{*}\|\mathbf{z}_{t}-\widehat{\mathbf{z}}_{t}\|\\\
{}&-\frac{1}{2\eta}\sum_{t=1}^{T}\left(\|\mathbf{z}_{t}-\widehat{\mathbf{z}}_{t}\|^{2}+\|\mathbf{z}_{t}-\widehat{\mathbf{z}}_{t-1}\|^{2}\right).\end{split}$
(13)

##  B Proof of Theorem 2

The proof is motivated by Abernethy et al. (2018). Let
$\overline{R}^{\mathbf{w}}$ and $\overline{R}^{\mathbf{p}}$ denote the average
regret of the players. On one hand, we have

$\begin{split}\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}g(\mathbf{w}_{t},\mathbf{p}_{t})={}&\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}-\alpha_{t}h_{t}(\mathbf{w}_{t})\\\
={}&-\min\limits_{\mathbf{w}^{\prime}\in\mathcal{W}}\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{w}^{\prime})-\overline{R}^{\mathbf{w}}\\\
={}&\max\limits_{\mathbf{w}^{\prime}\in\mathcal{W}}\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}g(\mathbf{w}^{\prime},\mathbf{p}_{t})-\overline{R}^{\mathbf{w}}\\\
\geq{}&\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}g(\mathbf{w},\mathbf{p}_{t})-\overline{R}^{\mathbf{w}}\\\
\geq{}&g(\mathbf{w},\overline{\mathbf{p}}_{T})-\overline{R}^{\mathbf{w}}\\\
\geq{}&\min\limits_{\mathbf{p}\in\mathcal{Q}}g(\mathbf{w},\mathbf{p})-\overline{R}^{\mathbf{w}}.\end{split}$

where $\mathbf{w}\in\mathcal{W}$ is an arbitrary point. On the other hand, we
have

$\begin{split}\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}g(\mathbf{w}_{t},\mathbf{p}_{t})={}&\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}\ell_{t}(\mathbf{p}_{t})\\\
={}&\min\limits_{\mathbf{p}\in\mathcal{Q}}\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}\ell_{t}(\mathbf{p})+\overline{R}^{\mathbf{q}}\\\
={}&\min\limits_{\mathbf{p}\in\mathcal{Q}}\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}g(\mathbf{w}_{t},\mathbf{p})+\overline{R}^{\mathbf{p}}\\\
\leq{}&\min\limits_{\mathbf{p}\in\mathcal{Q}}g(\overline{\mathbf{w}}_{T},\mathbf{p})+\overline{R}^{\mathbf{p}}.\end{split}$

##  C Proof of Section 4

In this section, we provide the detailed proofs of Section 4.

###  C.1 Proof of Proposition 1

Recall the update rule of $\mathbf{w}$ and $\mathbf{p}$ in Algorithm 1:

$\begin{split}\mathbf{w}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{w}\in\mathbb{R}^{d}}\sum_{j=1}^{t-1}\alpha_{j}h_{j}(\mathbf{w})+\alpha_{t}h_{t-1}(\mathbf{w})\\\
={}&\operatorname*{argmin}\limits_{\mathbf{w}\in\mathbb{R}^{d}}\sum_{j=1}^{t-1}-\alpha_{j}\mathbf{p}^{\top}_{j}A\mathbf{w}-\alpha_{t}\mathbf{p}^{\top}_{t-1}A\mathbf{w}+\frac{\sum_{s=1}^{t}\alpha_{s}}{2}\|\mathbf{w}\|_{2}^{2}\\\
={}&\operatorname*{argmin}\limits_{\mathbf{w}\in\mathbb{R}^{d}}\sum_{j=1}^{t-1}-\alpha_{j}\mathbf{p}^{\top}_{j}A\mathbf{w}-\alpha_{t}\mathbf{p}^{\top}_{t-1}A\mathbf{w}+\frac{t(t+1)}{4}\|\mathbf{w}\|_{2}^{2},\end{split}$

and

$\mathbf{p}_{t}=\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\frac{1}{4}\sum_{s=1}^{t}\alpha_{s}\ell_{s}(\mathbf{p})+\mathcal{D}_{E}\left(\mathbf{p},\frac{\mathbf{1}}{n}\right)=\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\sum_{s=1}^{t}\alpha_{s}\mathbf{p}^{\top}A\mathbf{w}_{s}+4\mathcal{D}_{E}\left(\mathbf{p},\frac{\mathbf{1}}{n}\right),$
(14)

Note that here we drop the $\|\mathbf{w}_{s}\|^{2}/2$ of $\ell_{s}$ in (14),
as it is constant with respect to $\mathbf{p}$. We start from the
initialization: first, from the fact that
$\mathbf{p}_{0}=\frac{\textbf{1}}{n}$, we obtain

$\overline{\mathbf{w}}_{1}=\mathbf{w}_{1}=\operatorname*{argmin}_{\mathbf{w}\in\mathbb{R}^{d}}h_{0}(\mathbf{w})=\operatorname*{argmin}_{\mathbf{w}\in\mathbb{R}^{d}}-\mathbf{p}^{\top}_{0}A\mathbf{w}+\frac{1}{2}\|\mathbf{w}\|_{2}^{2}=\frac{A^{\top}\textbf{1}}{n}=\mathbf{v}_{0}.$

Additionally,

$\begin{split}\mathbf{p}_{1}={}&\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\ell_{1}(\mathbf{p})+4\mathcal{D}_{E}\left(\mathbf{p},\frac{\mathbf{1}}{n}\right)\\\
={}&\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w}_{1}+4\mathcal{D}_{E}\left(\mathbf{p},\frac{\mathbf{1}}{n}\right)\\\
={}&\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{v}_{0}+4\mathcal{D}_{E}\left(\mathbf{p},\frac{\mathbf{1}}{n}\right)=\mathbf{q}_{\mu_{0}}(\mathbf{v}_{0})=\mathbf{q}_{0}.\end{split}$

Next, we focus on $\mathbf{v}_{t}$ and its connection to
$\overline{\mathbf{w}}_{t}$. We have

$\begin{split}\mathbf{v}_{t}=&{}(1-\theta_{t-1})(\mathbf{v}_{t-1}+\theta_{t-1}A^{\top}\mathbf{q}_{t-1})+\theta_{t-1}^{2}A^{\top}\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})\\\
=&{}(1-\theta_{t-1})\mathbf{v}_{t-1}+\theta_{t-1}A^{\top}\left((1-\theta_{t-1})\mathbf{q}_{t-1}+\theta_{t-1}\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})\right).\end{split}$
(15)

Define $\mathbf{r}_{0}=\mathbf{v}_{0}$, and
$\mathbf{r}_{t}=(1-\theta_{t-1})A^{\top}\mathbf{q}_{t-1}+\theta_{t-1}A^{\top}\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})$
for $t\geq 1$. We will show that

$\mathbf{v}_{t}=\frac{\sum_{s=0}^{t}\alpha_{s+1}\mathbf{r}_{s}}{\sum_{s=0}^{t}\alpha_{s+1}}$

for all $t\geq 0$ by induction. First, by definition, we have
$\mathbf{v}_{0}=\mathbf{r}_{0}=\frac{\alpha_{1}\mathbf{r}_{0}}{\alpha_{1}}$.
Next, assume

$\mathbf{v}_{t-1}=\frac{\sum_{s=0}^{t-1}\alpha_{s+1}\mathbf{r}_{s}}{\sum_{s=0}^{t-1}\alpha_{s+1}}.$

Then

$\begin{split}\mathbf{v}_{t}={}&(1-\theta_{t-1})\mathbf{v}_{t-1}+\theta_{t-1}\mathbf{r}_{t}\\\
={}&\frac{t}{t+2}\mathbf{v}_{t-1}+\frac{2}{t+2}\mathbf{r}_{t}\\\
={}&\frac{t}{t+2}\frac{1}{\sum_{s=0}^{t-1}\alpha_{s+1}}\sum_{s=0}^{t-1}\alpha_{s+1}\mathbf{r}_{s}+\frac{2}{(t+2)(t+1)}(t+1)\mathbf{r}_{t}\\\
={}&\frac{t}{t+2}\frac{2}{(t+1)t}\sum_{s=0}^{t-1}\alpha_{s+1}\mathbf{r}_{s}+\frac{2}{(t+2)(t+1)}\alpha_{t+1}\mathbf{r}_{t}\\\
={}&\frac{2}{(t+1)(t+2)}\sum_{s=0}^{t}\alpha_{s+1}\mathbf{r}_{s}=\frac{\sum_{s=0}^{t}\alpha_{s+1}\mathbf{r}_{s}}{\sum_{s=0}^{t}\alpha_{s+1}}.\end{split}$
(16)

Following a similar procedure, we obtain

$\mathbf{q}_{t}=\frac{\sum_{s=0}^{t}\alpha_{s+1}\mathbf{q}_{\mu_{s}}(\mathbf{v}_{s})}{\sum_{s=0}^{t}\alpha_{s+1}}.$

Thus, for $t\geq 1$, we have

$\begin{split}\mathbf{r}_{t}={}&(1-\theta_{t-1})A^{\top}\mathbf{q}_{t-1}+\theta_{t-1}A^{\top}\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})\\\
={}&\frac{t}{t+2}\frac{2}{t(t+1)}A^{\top}\left(\sum_{s=0}^{t-1}\alpha_{s+1}\mathbf{q}_{\mu_{s}}(\mathbf{v}_{s})\right)+\frac{2}{(t+2)(t+1)}(t+1)A^{\top}\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})\\\
=&\frac{2}{(t+1)(t+2)}A^{\top}\left(\sum_{s=0}^{t-1}\alpha_{s+1}\mathbf{q}_{\mu_{s}}(\mathbf{v}_{s})+\alpha_{t+1}\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})\right)\\\
=&\operatorname*{argmin}_{\mathbf{r}\in\mathbb{R}^{d}}-\left(\sum_{s=0}^{t-1}\alpha_{s+1}\mathbf{q}_{\mu_{s}}(\mathbf{v}_{s})+\alpha_{t+1}\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})\right)^{\top}A\mathbf{r}+\frac{(t+1)(t+2)}{4}\|\mathbf{r}\|^{2}_{2}.\end{split}$
(17)

Finally, note that

$\mu_{t}=4\prod_{i=1}^{t}\frac{i}{i+2}=4\frac{1}{1+2}\cdot\dots\frac{t}{t+2}=4\frac{2}{(t+1)(t+2)}=\frac{4}{\sum_{s=0}^{t}\alpha_{s+1}},$

so

$\begin{split}\mathbf{q}_{\mu_{t}}(\mathbf{v}_{t})={}&\operatorname*{argmin}_{\mathbf{q}\in\Delta^{n}}\mathbf{q}^{\top}A\left(\frac{\sum_{s=0}^{t}\alpha_{s+1}\mathbf{r}_{s}}{\sum_{s=0}^{t}\alpha_{s+1}}\right)+\frac{4}{\sum_{s=0}^{t}\alpha_{s+1}}\mathcal{D}_{E}\left(\mathbf{q},\frac{\mathbf{1}}{n}\right)\\\
={}&\operatorname*{argmin}_{\mathbf{q}\in\Delta^{n}}\mathbf{q}^{\top}A\left(\sum_{s=0}^{t}\alpha_{s+1}\mathbf{r}_{s}\right)+4\mathcal{D}_{E}\left(\mathbf{q},\frac{\mathbf{1}}{n}\right).\end{split}$
(18)

To summarize, for $t=1$, we have
$\mathbf{r}_{0}=\mathbf{v}_{0}=\mathbf{w}_{1}$, and
$\mathbf{q}_{\mu_{0}}(\mathbf{v}_{0})=\mathbf{p}_{1}$. For $t\geq 2$, we know
that

$\begin{split}\mathbf{r}_{t-1}=\operatorname*{argmax}_{\mathbf{r}\in\mathbb{R}^{d}}-\left(\sum_{s=0}^{t-2}\alpha_{s+1}\mathbf{q}_{\mu_{s}}(\mathbf{v}_{s})+\alpha_{t}\mathbf{q}_{\mu_{t-2}}(\mathbf{v}_{t-2})\right)^{\top}A\mathbf{r}+\frac{t(t+1)}{4}\|\mathbf{r}\|^{2}_{2},\end{split}$
(19)

and

$\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})=\operatorname*{argmin}_{\mathbf{q}\in\Delta^{n}}\mathbf{q}^{\top}A\left(\sum_{s=0}^{t-1}\alpha_{s+1}\mathbf{r}_{s}\right)+4\mathcal{D}_{E}\left(\mathbf{q},\frac{\mathbf{1}}{n}\right).$

The proof is finished by replacing $\mathbf{q}_{\mu_{t-1}}(\mathbf{v}_{t-1})$
as $\mathbf{p}_{t}$, $\mathbf{r}_{t-1}$ as $\mathbf{w}_{t}$, and noticing that

$\mathbf{v}_{T-1}=\frac{1}{\sum_{s=0}^{T-1}\alpha_{s+1}}\sum_{s=0}^{T-1}\alpha_{s+1}\mathbf{r}_{s}=\frac{1}{\sum_{s=1}^{T}\alpha_{s}}\sum_{s=1}^{T}\alpha_{s}\mathbf{w}_{s}=\overline{\mathbf{w}}_{T}.$

and

$\mathbf{q}_{T-1}=\frac{1}{\sum_{s=0}^{T-1}\alpha_{s+1}}\sum_{s=0}^{T-1}\alpha_{s+1}\mathbf{q}_{\mu_{s}}(\mathbf{v}_{s})=\frac{1}{\sum_{s=1}^{T}\alpha_{s}}\sum_{s=1}^{T}\alpha_{s}\mathbf{p}_{s}$

###  C.2 Proof of Theorem 3

Let
$\widetilde{\mathbf{w}}_{t}=\operatorname*{argmin}_{\mathbf{w}\in\mathbb{R}^{d}}\sum_{s=1}^{t-1}\alpha_{s}h_{s}(\mathbf{w})$.
Note that $h_{t}(\cdot)$ is 1-strongly convex w.r.t $\|\cdot\|_{2}$. Thus, for
the $\mathbf{w}$-player, based on Lemma 1, we have

$\begin{split}\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{w}_{t})-\alpha_{t}h_{t}(\mathbf{w})\leq{}&\sum_{t=1}^{T}\alpha_{t}\left(h_{t}(\mathbf{w}_{t})-h_{t}(\widetilde{\mathbf{w}}_{t+1})\right)-\alpha_{t}\left(h_{t-1}(\mathbf{w}_{t})-h_{t-1}(\widetilde{\mathbf{w}}_{t+1})\right)\\\
={}&\sum_{t=1}^{T}\alpha_{t}\left(-\mathbf{p}_{t}^{\top}A\mathbf{w}_{t}+\frac{1}{2}\|\mathbf{w}_{t}\|_{2}^{2}+\mathbf{p}_{t}^{\top}A\widetilde{\mathbf{w}}_{t+1}-\frac{1}{2}\|\widetilde{\mathbf{w}}_{t+1}\|_{2}^{2}\right)\\\
{}&-\alpha_{t}\left(-\mathbf{p}_{t-1}^{\top}A\mathbf{w}_{t}+\frac{1}{2}\|\mathbf{w}_{t}\|_{2}^{2}+\mathbf{p}_{t-1}^{\top}A\widetilde{\mathbf{w}}_{t+1}-\frac{1}{2}\|\widetilde{\mathbf{w}}_{t+1}\|_{2}^{2}\right)\\\
={}&\sum_{t=1}^{T}\alpha_{t}\left(\mathbf{p}_{t}-\mathbf{p}_{t-1}\right)^{\top}A(\widetilde{\mathbf{w}}_{t+1}-\mathbf{w}_{t}).\\\
\end{split}$ (20)

Next, according to the definition of $\mathbf{w}_{t}$ and
$\widetilde{\mathbf{w}}_{t+1}$, we have

$\mathbf{w}_{t}=\frac{1}{\sum_{s=1}^{t}\alpha_{s}}A^{\top}\left(\sum_{s=1}^{t-1}\alpha_{s}\mathbf{p}_{s}+\alpha_{t}\mathbf{p}_{t-1}\right),$

and

$\widetilde{\mathbf{w}}_{t+1}=\frac{1}{\sum_{s=1}^{t}\alpha_{s}}A^{\top}\left(\sum_{s=1}^{t-1}\alpha_{s}\mathbf{p}_{s}+\alpha_{t}\mathbf{p}_{t}\right).$

Combining the two equations above with (20), we have that for any
$\mathbf{w}\in\mathbb{R}^{d}$,

$\begin{split}\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{w}_{t})-\alpha_{t}h_{t}(\mathbf{w})\leq{}&\sum_{t=1}^{T}\frac{\alpha_{t}^{2}}{\sum_{s=1}^{t}\alpha_{s}}\|A^{\top}(\mathbf{p}_{t}-\mathbf{p}_{t-1})\|_{2}^{2}\\\
={}&\sum_{t=1}^{T}\frac{\alpha_{t}^{2}}{\sum_{s=1}^{t}\alpha_{s}}\left\|\sum_{i=1}^{n}y^{(i)}[\mathbf{p}_{t}-\mathbf{p}_{t-1}]_{i}\mathbf{x}^{(i)}\right\|^{2}_{2}\\\
\stackrel{{\scriptstyle\rm(2)}}{{\leq}}{}&\sum_{t=1}^{T}\frac{\alpha_{t}^{2}}{\sum_{s=1}^{t}\alpha_{s}}\left(\sum_{i=1}^{n}|\mathbf{p}_{t}-\mathbf{p}_{t-1}|_{i}\|\mathbf{x}^{(i)}\|_{2}\right)^{2}\\\
\stackrel{{\scriptstyle\rm(3)}}{{\leq}}{}&\sum_{t=1}^{T}\frac{\alpha_{t}^{2}}{\sum_{s=1}^{t}\alpha_{s}}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|^{2}_{1}\\\
={}&\sum_{t=1}^{T}\frac{2t^{2}}{t(t+1)}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|^{2}_{1}\stackrel{{\scriptstyle\rm(4)}}{{\leq}}2\sum_{t=1}^{T}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2},\end{split}$
(21)

where inequality (2) is based on the triangle inequality, inequality (3) is
derived from Assumption 1, and inequality (4) is because $\frac{t}{t+1}\leq
1$.

On the other hand, for the $\mathbf{p}$-player, note that the the regularizer
is 1-strongly convex w.r.t. the $\|\cdot\|_{1}$. Thus, according to Lemma 2
(with $\lambda=0,\beta=1$), we have

$\begin{split}\sum_{t=1}^{T}\alpha_{t}\ell_{t}(\mathbf{p}_{t})-\sum_{t=1}^{T}\alpha_{t}\ell_{t}(\mathbf{p})\leq{}&4{\log
n}-2\sum_{t=1}^{T}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2}.\\\ \end{split}$
(22)

for any $\mathbf{p}\in\Delta^{n}$. Finally, we focus on the iteration
complexity. First, define $\widehat{\mathbf{w}}^{*}=\gamma\mathbf{w}^{*}$,
where $\mathbf{w}^{*}$ is the maximum margin classifier defined in Assumption
1. Then we have

$m(\widehat{\mathbf{w}}^{*})=\min_{\mathbf{p}\in\Delta^{n}}\\{\mathbf{p}^{\top}A\widehat{\mathbf{w}}^{*}\\}-\frac{1}{2}\|\widehat{\mathbf{w}}^{*}\|_{2}^{2}=\gamma^{2}-\frac{\gamma^{2}}{2}=\frac{\gamma^{2}}{2}.$

Thus, combining (21), (22), and Theorem 2, we have

$\begin{split}m(\widehat{\mathbf{w}}^{*})-m(\overline{\mathbf{w}}_{T})\leq\overline{R}^{\mathbf{p}}+\overline{R}^{\mathbf{w}}\leq\frac{8\log
n}{T(T+1)}\leq\frac{8\log n}{T^{2}},\end{split}$ (23)

and thus

$\begin{split}\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\overline{\mathbf{w}}_{T}\geq{}&m(\overline{\mathbf{w}}_{T})\\\
\geq{}&m(\widehat{\mathbf{w}}^{*})-\frac{8\log n}{T^{2}}\\\
={}&\frac{\gamma^{2}}{2}-\frac{8\log n}{T^{2}},\end{split}$ (24)

where the first inequality follows because
$-\frac{1}{2}\|\overline{\mathbf{w}}_{T}\|_{2}^{2}\leq 0$. Hence, it can be
seen that $\overline{\mathbf{w}}_{T}$ will have a non-negative margin when
$T\geq\frac{4\sqrt{\log n}}{\gamma}$.

###  C.3 Proof of Proposition 2

We start from the original expression in Ji et al. (2021). For
$\mathbf{g}_{t}$, we have

$\begin{split}\mathbf{g}_{t}={}&{\beta_{t}}\left((-A^{\top}\mathbf{q}_{t})+\mathbf{g}_{t-1}\right)\\\
={}&\frac{t}{t+1}\left((-A)^{\top}\mathbf{q}_{t}+\frac{t-1}{t}\mathbf{g}_{t-2}+\frac{t-1}{t}(-A)^{\top}\mathbf{q}_{t-1}\right)\\\
={}&\cdots\\\
={}&\frac{1}{t+1}(-A)^{\top}\left(\sum_{s=1}^{t}s\mathbf{q}_{s}\right).\end{split}$
(25)

Thus, we also have

$\mathbf{g}_{t-1}=\frac{1}{t}(-A)^{\top}\left(\sum_{s=1}^{t-1}s\mathbf{q}_{s}\right).$

Next, we focus on $\mathbf{v}_{t}$. Note that
$\mathbf{v}_{t}=\mathbf{v}_{t-1}-\theta_{t-1}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})$,
where

$\begin{split}-\left(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1}\right)=\frac{1}{t}A^{\top}\left(\sum_{s=1}^{t-1}s\mathbf{q}_{s}+t\mathbf{q}_{t-1}\right)={}&\frac{2(t+1)}{2t(t+1)}A^{\top}\left(\sum_{s=1}^{t-1}s\mathbf{q}_{s}+t\mathbf{q}_{t-1}\right)\\\
={}&\frac{t+1}{2}\mathbf{r}_{t},\end{split}$ (26)

where we define

$\begin{split}\mathbf{r}_{t}={}&\frac{2}{t(t+1)}A^{\top}\left(\sum_{s=1}^{t-1}s\mathbf{q}_{s}+t\mathbf{q}_{t-1}\right)=\frac{1}{\sum_{s=1}^{t}\alpha_{s}}A^{\top}\left(\sum_{s=1}^{t-1}s\mathbf{q}_{s}+t\mathbf{q}_{t-1}\right)\\\
={}&\operatorname*{argmin}\limits_{\mathbf{r}\in\mathbb{R}^{d}}-\left(\sum_{s=1}^{t-1}s\mathbf{q}_{s}+t\mathbf{q}_{t-1}\right)^{\top}A\mathbf{r}+\frac{\sum_{s=1}^{t}\alpha_{s}}{2}\|\mathbf{r}\|_{2}^{2}\\\
={}&\operatorname*{argmin}\limits_{\mathbf{r}\in\mathbb{R}^{d}}\sum_{s=1}^{t-1}\alpha_{s}\left(-\mathbf{q}_{s}^{\top}A\mathbf{r}+\frac{1}{2}\|\mathbf{r}\|_{2}^{2}\right)+\alpha_{t}\left(-\mathbf{q}_{t-1}^{\top}A\mathbf{r}+\frac{1}{2}\|\mathbf{r}\|_{2}^{2}\right)\end{split}$
(27)

As for the $\mathbf{q}_{t}$ variables, observe that

$\begin{split}q_{t,i}={}&\frac{\exp(-y^{(i)}\mathbf{v}_{t}^{\top}\mathbf{x}^{(i)})}{\sum_{j=1}^{n}\exp(-y^{(j)}\mathbf{v}_{t}^{\top}\mathbf{x}^{(j)})}\\\
={}&\frac{\exp(-y^{(i)}\mathbf{v}_{t-1}^{\top}\mathbf{x}^{(j)})\exp(\frac{t}{2(t+1)}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})^{\top}y^{(i)}\mathbf{x}^{(i)})}{\sum_{j=1}^{n}\exp(-y^{(j)}\mathbf{v}_{t-1}^{\top}\mathbf{x}^{(j)})\exp(\frac{t}{2(t+1)}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})^{\top}y^{(j)}\mathbf{x}^{(j)})}\\\
={}&\frac{\frac{\exp(-y^{(i)}\mathbf{v}_{t-1}^{\top}\mathbf{x}^{(j)})}{\sum_{k=1}^{n}\exp(-y^{(k)}\mathbf{v}_{t-1}^{\top}\mathbf{x}^{(k)})}\exp(\frac{t}{2(t+1)}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})^{\top}y^{(i)}\mathbf{x}^{(i)})}{\sum_{j=1}^{n}\frac{\exp(-y^{(j)}\mathbf{v}_{t-1}^{\top}\mathbf{x}^{(j)})}{{\sum_{k=1}^{n}\exp(-y^{(k)}\mathbf{v}_{t-1}^{\top}\mathbf{x}^{(k)})}}\exp(\frac{t}{2(t+1)}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})^{\top}y^{(j)}\mathbf{x}^{(j)})}\\\
={}&\frac{q_{t-1,i}\exp(\frac{t}{2(t+1)}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})^{\top}y^{(i)}\mathbf{x}^{(i)})}{\sum_{j=1}^{n}q_{t-1,j}\exp(\frac{t}{2(t+1)}(\mathbf{g}_{t-1}-A^{\top}\mathbf{q}_{t-1})^{\top}y^{(j)}\mathbf{x}^{(j)})}\\\
={}&\frac{q_{t-1,i}\exp(-\frac{\alpha_{t}}{4}\mathbf{r}_{t}^{\top}y^{(i)}\mathbf{x}^{(i)})}{\sum_{j=1}^{n}q_{t-1,j}\exp(-\frac{\alpha_{t}}{4}\mathbf{r}_{t}^{\top}y^{(j)}\mathbf{x}^{(j)})}=\frac{q_{0,i}\exp(-\sum_{s=1}^{t}\frac{\alpha_{s}}{4}\mathbf{r}_{s}^{\top}y^{(i)}\mathbf{x}^{(i)})}{\sum_{j=1}^{n}q_{0,j}\exp(-\sum_{s=1}^{t}\frac{\alpha_{s}}{4}\mathbf{r}_{s}^{\top}y^{(j)}\mathbf{x}^{(j)})}.\end{split}$
(28)

Based on the relationship between the multiplicative weights algorithm and
FTRL with the entropy regularizer, we have

$\begin{split}\mathbf{q}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{q}\in\Delta^{n}}\sum_{s=1}^{t}\frac{\alpha_{s}}{4}\mathbf{q}^{\top}A\mathbf{r}_{s}+\mathcal{D}_{E}(\mathbf{q},\mathbf{q}_{0}).\end{split}$
(29)

Next, note that
$\mathbf{r}_{1}=A^{\top}\mathbf{q}_{0}=\frac{A^{\top}\mathbf{1}}{n}=\mathbf{w}_{1}$,
from the proof of Proposition 1. Combining this with the fact that
$\mathbf{q}_{0}=\frac{\mathbf{1}}{n}=\mathbf{p}_{0}$, we can recursively
conclude that $\mathbf{r}_{t}=\mathbf{w}_{t}$ and
$\mathbf{q}_{t}=\mathbf{p}_{t}$. Finally, since $\mathbf{v}_{0}=\mathbf{0}$,
we have that

$\mathbf{v}_{T}=\mathbf{v}_{T-1}+\theta_{T-1}\frac{T+1}{2}\mathbf{r}_{T}=\mathbf{v}_{T-1}+\frac{T}{2(T+1)}\frac{T+1}{2}\mathbf{r}_{T}=\mathbf{v}_{T-1}+\frac{1}{4}\alpha_{T}\mathbf{r}_{T}=\frac{1}{4}\sum_{t=1}^{T}\alpha_{t}\mathbf{r}_{t}$

###  C.4 Proof of Theorem 4

For the first two parts of Theorem 4, note that the expressions in Algorithms
1 and and 2 are exactly the same. In the following, we focus on the normalized
margin analysis. First, recall that the normalized margin is defined as:

$\overline{\gamma}(\mathbf{w})=\frac{\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w}}{\|\mathbf{w}\|_{2}},$

and for the the maximal margin classifier $\mathbf{w}^{*}$ we have
$\overline{\gamma}(\mathbf{w}^{*})={\gamma}$. Next, we compute
$\overline{\gamma}(\mathbf{v}_{T})$ under our framework. Note that

$\overline{\mathbf{w}}_{T}=\frac{4\mathbf{v}_{T}}{\sum_{t=1}^{T}\alpha_{t}}=\frac{8\mathbf{v}_{T}}{T(T+1)}.$

Moreover, from the proof of Theorem 3, we know that
$m(\mathbf{w})-m(\overline{\mathbf{w}}_{T})\leq\frac{8\log n}{T(T+1)}$ for any
$\mathbf{w}\in\mathbb{R}^{d}$. Thus, we have

$\displaystyle\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\frac{8\mathbf{v}_{T}}{T(T+1)}-\frac{1}{2}\left\|\frac{8\mathbf{v}_{T}}{T(T+1)}\right\|_{2}^{2}$
$\displaystyle=\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\overline{\mathbf{w}}_{T}-\frac{1}{2}\|\overline{\mathbf{w}}_{T}\|_{2}^{2}$
$\displaystyle=m(\overline{\mathbf{w}}_{T})$ $\displaystyle\geq
m\left(\frac{8}{T(T+1)}\|\mathbf{v}_{T}\|_{2}\mathbf{w}^{*}\right)-\frac{8\log
n}{T(T+1)}$
$\displaystyle=\frac{8}{T(T+1)}\|\mathbf{v}_{T}\|_{2}\gamma-\frac{64}{2(T(T+1))^{2}}\|\mathbf{v}_{T}\|^{2}_{2}-\frac{8\log
n}{T(T+1)}$

Rearranging and multiplying both sides by
$\frac{T(T+1)}{8\|\mathbf{v}_{T}\|_{2}}$, we obtain

$\begin{split}{}&\frac{\min\limits_{\mathbf{p}}\mathbf{p}^{\top}A\mathbf{v}_{T}}{\|\mathbf{v}_{T}\|_{2}}\geq\gamma-\frac{\log
n}{\|\mathbf{v}_{T}\|_{2}}\end{split}$

The proof is finished by the following lower bound on
$\|\mathbf{v}_{T}\|_{2}$.

######  Lemma 5.

We have

$\|\mathbf{v}_{T}\|_{2}\geq\frac{T(T+1){\gamma}}{8}.$

###### Proof.

Note that $\|\mathbf{w}^{*}\|=1$, so
$\frac{\mathbf{v}_{T}^{\top}\mathbf{w}^{*}}{\|\mathbf{v}_{T}\|_{2}}\leq 1$.
Then, based on our derivation of $\mathbf{w}_{t}$ in the proof of Theorem 3,
we can conclude that

$\begin{split}\|\mathbf{v}_{T}\|_{2}\geq\mathbf{v}_{T}^{\top}\mathbf{w}^{*}={}&\frac{1}{4}\sum_{t=1}^{T}\alpha_{t}\mathbf{w}_{t}^{\top}\mathbf{w}^{*}\\\
={}&\frac{1}{4}\sum_{t=1}^{T}\alpha_{t}\left[\frac{1}{\sum_{s=1}^{t}\alpha_{s}}\left(\sum_{s=1}^{t-1}\alpha_{s}\mathbf{p}_{s}+\alpha_{t}\mathbf{p}_{t}\right)\right]^{\top}A\mathbf{w}^{*}\\\
\geq{}&\frac{1}{4}\sum_{t=1}^{T}\alpha_{t}\min_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w}^{*}\\\
={}&\frac{T(T+1){\gamma}}{8}.\end{split}$ (30)

∎

###  C.5 Details of Section 4.4

Algorithm 5 MPFP of Yu et al. (2014)

Input: $\\{\gamma_{t}\\}_{t=1}^{T},\mathbf{v}_{1}=\mathbf{r}^{*}$

for $t=1,\dots,T$ do

$\mathbf{u}_{t}=\text{Prox}_{\mathbf{v}_{t}}^{R}(\gamma_{t}F(\mathbf{v}_{t}))$

$\mathbf{v}_{t+1}=\text{Prox}_{\mathbf{v}_{t}}^{R}(\gamma_{t}F(\mathbf{u}_{t}))$

$\mathbf{z}_{t}=\frac{1}{\sum_{s=1}^{t}\gamma_{s}}\sum_{s=1}^{t}\gamma_{s}\mathbf{u}_{s}$

end for

Output: $\mathbf{z}_{T}$

$\begin{split}\textstyle\psi_{t}(\mathbf{w})={}&-\widehat{\mathbf{p}}_{t-1}^{\top}A\mathbf{w}\\\
\phi_{t}(\mathbf{p})={}&\mathbf{p}^{\top}A\widehat{\mathbf{w}}_{t-1}\\\
\textsf{OL}^{\mathbf{w}}=\text{OMD}\left[\frac{1}{2}\|\cdot\|_{2}^{2},\mathbf{0},\frac{1}{\sqrt{\log
n}},\psi_{t},\mathcal{B}_{d}\right]\Leftrightarrow{}{\mathbf{w}}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{w}\in\mathcal{B}_{d}}\frac{1}{\sqrt{\log
n}}\left\langle\nabla\psi_{t}(\mathbf{w}_{t-1}),\mathbf{w}\right\rangle\\\
&\hskip
71.13188pt+\mathcal{D}_{\frac{1}{2}\|\cdot\|_{2}^{2}}(\mathbf{w},\widehat{\mathbf{w}}_{t-1})\\\
{}{}{}{}\widehat{\mathbf{w}}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{w}\in\mathcal{B}_{d}}\frac{1}{\sqrt{\log
n}}\left\langle\nabla h_{t}(\mathbf{w}_{t}),\mathbf{w}\right\rangle\\\ &\hskip
71.13188pt+\mathcal{D}_{\frac{1}{2}\|\cdot\|_{2}^{2}}(\mathbf{w},\widehat{\mathbf{w}}_{t-1})\\\
\textsf{OL}^{\mathbf{p}}=\text{OMD}\left[E,\frac{\mathbf{1}}{n},\sqrt{\log
n},\phi_{t},\Delta^{n}\right]\Leftrightarrow{}{\mathbf{p}}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\sqrt{\log
n}\left\langle\nabla\phi_{t}(\mathbf{p}_{t-1}),\mathbf{p}\right\rangle\\\
&\hskip 85.35826pt+\mathcal{D}_{E}(\mathbf{p},\widehat{\mathbf{p}}_{t-1})\\\
{}{}{}{}\widehat{\mathbf{p}}_{t}={}&\operatorname*{argmin}\limits_{\mathbf{p}\in\Delta^{n}}\sqrt{\log
n}\left\langle\nabla\ell_{t}(\mathbf{p}_{t-1}),\mathbf{p}\right\rangle\\\
&\hskip 85.35826pt+\mathcal{D}_{E}(\mathbf{p},\widehat{\mathbf{p}}_{t-1})\\\
\end{split}$

The Perceptron proposed by Yu et al. (2014), named mirror-prox algorithm for
feasibility Problems (MPFP) procedure (Yu et al., 2014), is summarized in
Algorithm 5. Yu et al. (2014) consider a general objective
$g:\mathcal{W}\times\mathcal{P}\to\mathbb{R}$, for spaces
$\mathcal{P}\subset\mathbb{R}^{n}$ and $\mathcal{W}\subset\mathbb{R}^{d}$, and
defines
$F(\mathbf{w},\mathbf{p})=[-\nabla_{\mathbf{w}}g(\mathbf{w},\mathbf{p});\nabla_{\mathbf{p}}g(\mathbf{w},\mathbf{p})]\in\mathbb{R}^{d+n}$
where $[\mathbf{x};\mathbf{y}]$ denotes the concatenation of vectors
$\mathbf{x}$ and $\mathbf{y}$. Associated to $\mathcal{P}$ (and analogously
for $\mathcal{W}$), Yu et al. (2014) make use of the following quantities:

  * •

A constant $\alpha_{\mathbf{p}}>0$ and function
$R_{\mathbf{p}}:\mathcal{P}\to\mathbb{R}$ that is 1-strongly convex w.r.t.
some norm $\|\cdot\|_{\mathcal{P}}$ on $\mathcal{P}$;

  * •

Minimizer
$\mathbf{r}_{\mathbf{p}}^{*}=\operatorname*{argmin}_{\mathbf{p}\in\mathcal{P}}R_{\mathbf{p}}(\mathbf{p})$.

  * •

Bregman divergence
$D_{\mathbf{p}}(\mathbf{p},\mathbf{q})=D_{R_{\mathbf{p}}}(\mathbf{p},\mathbf{q})$;

  * •

Diameter
$\Omega_{\mathbf{p}}=\max_{\mathbf{p}\in\mathcal{P}}D_{\mathbf{p}}(\mathbf{p},\mathbf{r}_{\mathbf{p}}^{*})$.

From these, we can define the function $R:\mathbb{R}^{d+n}\mapsto\mathbb{R}$
and its minimizer

$\displaystyle
R(\mathbf{w},\mathbf{p})=\alpha_{\mathbf{w}}R_{\mathbf{w}}(\mathbf{w})+\alpha_{\mathbf{p}}R_{\mathbf{p}}(\mathbf{p})\quad\text{and}\quad\mathbf{r}^{*}=\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{d+n}}R(\mathbf{x})=[\mathbf{r}_{\mathbf{w}}^{*};\mathbf{r}_{\mathbf{p}}^{*}]$

Lastly, the algorithm relies on the following Prox map: for function
$f:\mathcal{Z}\to\mathbb{R}$ and point $\mathbf{v}\in\mathcal{Z}$ on a general
space $\mathcal{Z}\subset\mathbb{R}^{m}$, define the mapping
$\text{Prox}_{\mathbf{v}}^{f}:\mathcal{Z}\to\mathcal{Z}$ by

$\displaystyle\text{Prox}_{\mathbf{v}}^{f}(\mathbf{z})=\operatorname*{argmin}_{\mathbf{u}\in\mathcal{Z}}\left\\{\mathbf{u}^{\top}\mathbf{z}+D_{f}(\mathbf{u},\mathbf{v})\right\\}$

In this work, we consider MPFP under the bilinear objective
$g(\mathbf{w},\mathbf{p})=\mathbf{p}^{\top}A\mathbf{w}$, where the rows of $A$
are assumed to be normalized w.r.t. $\|\cdot\|_{2}$. We further give the
following specifications:

  * •

Spaces $\mathcal{P}=\Delta_{n}$ and
$\mathcal{W}=\mathcal{B}_{d}=\\{\mathbf{w}\in\mathbb{R}^{d}:\|\mathbf{w}\|_{2}\leq
1\\}$.

  * •

Norms $\|\cdot\|_{\mathcal{P}}=\|\cdot\|_{1}$ and
$\|\cdot\|_{\mathcal{W}}=\|\cdot\|_{2}$.

  * •

Regularizers $R_{\mathbf{p}}=E$, where $E$ denotes the entropy regularizer
(i.e., negative Shannon entropy), and
$R_{\mathbf{w}}=\frac{1}{2}\|\cdot\|_{2}^{2}$.

  * •

Contants
$\alpha_{\mathbf{p}}=\frac{1}{\sqrt{\Omega_{\mathbf{p}}}(\sqrt{\Omega_{\mathbf{p}}}+\sqrt{\Omega_{\mathbf{w}}})}$
and
$\alpha_{\mathbf{w}}=\frac{\sqrt{\Omega_{\mathbf{p}}}}{\sqrt{\Omega_{\mathbf{p}}}+\sqrt{\Omega_{\mathbf{w}}}}$.

  * •

Constant weights
$\gamma_{t}=\frac{1}{\sqrt{\Omega_{\mathbf{p}}}+\sqrt{\Omega_{\mathbf{w}}}}$
for each $t\in[T]$.

Endowed with these parameters, the procedure becomes the MPLFP algorithm of Yu
et al. (2014), and we can conclude the following connection.

######  Theorem 8.

Let $\alpha_{t}=1$. Then the MPLFP algorithm is equivalent to the game
dynamics given by Algorithm 5, in the sense that
$\mathbf{u}_{t}=[\mathbf{w}_{t};\mathbf{p}_{t}]$,
$\mathbf{v}_{t+1}=[\widehat{\mathbf{w}}_{t};\widehat{\mathbf{p}}_{t}]$, and
$\mathbf{z}_{t}=\left[\frac{1}{t}\sum_{s=1}^{t}\mathbf{w}_{s};\frac{1}{t}\sum_{s=1}^{t}\mathbf{p}_{s}\right]$.

###### Proof.

We begin by noting that

$\displaystyle\Omega_{\mathbf{w}}$
$\displaystyle=\max_{\mathbf{w}\in\mathcal{B}_{d}}D_{\mathbf{w}}(\mathbf{w},\mathbf{r}_{w}^{*})=\max_{\mathbf{w}\in\mathcal{B}_{d}}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}=\frac{1}{2}$
$\displaystyle\Omega\mathbf{p}$
$\displaystyle=\max_{\mathbf{p}\in\Delta^{n}}D_{\mathbf{p}}(\mathbf{p},\mathbf{r}_{p}^{*})=\max_{\mathbf{p}\in\Delta^{n}}\text{KL}\left(\mathbf{p}||\frac{\mathbf{1}}{n}\right)=\log
n$

where KL denotes the Kullback–Leibler divergence, so that we can derive
parameters

$\displaystyle\gamma_{t}=\frac{1}{\sqrt{\log
n}+\frac{1}{\sqrt{2}}}\quad\text{and}\quad\alpha_{\mathbf{p}}=\frac{1}{\sqrt{\log
n}\left(\sqrt{\log
n}+\frac{1}{\sqrt{2}}\right)}\quad\text{and}\quad\alpha_{\mathbf{w}}=\frac{\sqrt{\log
n}}{\sqrt{\log n}+\frac{1}{\sqrt{2}}}$

Next, note that
$F(\mathbf{w},\mathbf{p})=\left[-\mathbf{p}^{\top}A;A\mathbf{w}\right]$. For
convenience, we will write the MPFP iterates as

$\displaystyle\mathbf{u}_{t}=[\mathbf{x}_{t};\mathbf{y}_{t}]\quad\text{and}\quad\mathbf{v}_{t+1}=[\widehat{\mathbf{x}}_{t};\widehat{\mathbf{y}}_{t}]$

Section 10 of Yu et al. (2014) shows that

$\displaystyle\text{Prox}_{[\widehat{\mathbf{x}};\widehat{\mathbf{y}}]}^{R}(\mathbf{x},\mathbf{y})=\left[\text{Prox}_{\widehat{\mathbf{x}}}^{R_{\mathbf{w}}}\left(\frac{\mathbf{x}}{\alpha_{\mathbf{w}}}\right);\text{Prox}_{\widehat{\mathbf{y}}}^{R_{\mathbf{p}}}\left(\frac{\mathbf{y}}{\alpha_{\mathbf{p}}}\right)\right]$

Using the iterate definitions, we can then obtain

$\displaystyle[\mathbf{x}_{t};\mathbf{y}_{t}]$ $\displaystyle=\mathbf{u}_{t}$
$\displaystyle=\text{Prox}_{\mathbf{v}_{t}}^{R}(\gamma_{t}F(\mathbf{v}_{t}))$
$\displaystyle=\text{Prox}_{[\widehat{\mathbf{x}}_{t-1};\widehat{\mathbf{y}}_{t-1}]}^{R}(-\gamma_{t}\widehat{\mathbf{y}}_{t-1}^{\top}A,\gamma_{t}A\widehat{\mathbf{x}}_{t-1})$
$\displaystyle=\left[\text{Prox}_{\widehat{\mathbf{x}}_{t-1}}^{R_{\mathbf{w}}}\left(\frac{-\gamma_{t}\widehat{\mathbf{y}}_{t-1}^{\top}A}{\alpha_{\mathbf{w}}}\right);\text{Prox}_{\widehat{\mathbf{y}}_{t-1}}^{R_{\mathbf{p}}}\left(\frac{\gamma_{t}A\widehat{\mathbf{x}}_{t-1}}{\alpha_{\mathbf{p}}}\right)\right]$
$\displaystyle=\left[\text{Prox}_{\widehat{\mathbf{x}}_{t-1}}^{R_{\mathbf{w}}}\left(-\frac{1}{\sqrt{\log
n}}\widehat{\mathbf{y}}_{t-1}^{\top}A\right);\text{Prox}_{\widehat{\mathbf{y}}_{t-1}}^{R_{\mathbf{p}}}\left(\sqrt{\log
n}A\widehat{\mathbf{x}}_{t-1}\right)\right]$

and

$\displaystyle[\widehat{\mathbf{x}}_{t};\widehat{\mathbf{y}}_{t}]$
$\displaystyle=\mathbf{v}_{t+1}$
$\displaystyle=\text{Prox}_{\mathbf{v}_{t}}^{R}(\gamma_{t}F(\mathbf{u}_{t}))$
$\displaystyle=\text{Prox}_{[\widehat{\mathbf{x}}_{t-1};\widehat{\mathbf{y}}_{t-1}]}^{R}(-\gamma_{t}\mathbf{y}_{t}^{\top}A,\gamma_{t}A\mathbf{x}_{t})$
$\displaystyle=\left[\text{Prox}_{\widehat{\mathbf{x}}_{t-1}}^{R_{\mathbf{w}}}\left(\frac{-\gamma_{t}\mathbf{y}_{t}^{\top}A}{\alpha_{\mathbf{w}}}\right);\text{Prox}_{\widehat{\mathbf{y}}_{t-1}}^{R_{\mathbf{p}}}\left(\frac{\gamma_{t}A\mathbf{x}_{t}}{\alpha_{\mathbf{p}}}\right)\right]$
$\displaystyle=\left[\text{Prox}_{\widehat{\mathbf{x}}_{t-1}}^{R_{\mathbf{w}}}\left(-\frac{1}{\sqrt{\log
n}}\mathbf{y}_{t}^{\top}A\right);\text{Prox}_{\widehat{\mathbf{y}}_{t-1}}^{R_{\mathbf{p}}}\left(\sqrt{\log
n}A\mathbf{x}_{t}\right)\right]$

Using the definition of the Prox function then yields

$\displaystyle\mathbf{x}_{t}$
$\displaystyle=\operatorname*{argmin}_{\mathbf{w}\in\mathcal{B}_{d}}\left\\{-\frac{1}{\sqrt{\log
n}}\widehat{\mathbf{y}}_{t-1}^{\top}A\mathbf{w}+D_{\mathbf{w}}(\mathbf{w},\widehat{\mathbf{x}}_{t-1})\right\\}$
$\displaystyle\widehat{\mathbf{x}}_{t}$
$\displaystyle=\operatorname*{argmin}_{\mathbf{w}\in\mathcal{B}_{d}}\left\\{-\frac{1}{\sqrt{\log
n}}\mathbf{y}_{t}^{\top}A\mathbf{w}+D_{\mathbf{w}}(\mathbf{w},\widehat{\mathbf{x}}_{t-1})\right\\}$
$\displaystyle\mathbf{y}_{t}$
$\displaystyle=\operatorname*{argmin}_{\mathbf{p}\in\Delta^{n}}\left\\{\sqrt{\log
n}\mathbf{p}^{\top}A\widehat{\mathbf{x}}_{t-1}+D_{\mathbf{p}}(\mathbf{p},\widehat{\mathbf{y}}_{t-1})\right\\}$
$\displaystyle\widehat{\mathbf{y}}_{t}$
$\displaystyle=\operatorname*{argmin}_{\mathbf{p}\in\Delta^{n}}\left\\{\sqrt{\log
n}\mathbf{p}^{\top}A\mathbf{x}_{t}+D_{\mathbf{p}}(\mathbf{p},\widehat{\mathbf{y}}_{t-1})\right\\}$

From the fact that

$\displaystyle[\widehat{\mathbf{x}}_{0};\widehat{\mathbf{y}}_{0}]=v_{1}=[\mathbf{r}_{\mathbf{w}}^{*};\mathbf{r}_{\mathbf{p}}^{*}]=\left[\mathbf{0};\frac{\mathbf{1}}{n}\right]=[\widehat{\mathbf{w}}_{0};\widehat{\mathbf{p}}_{0}]$

and plugging in the appropriate parameters into the OMD updates, we can
recursively conclude that
$[\widehat{\mathbf{w}}_{t};\widehat{\mathbf{p}}_{t}]=[\widehat{\mathbf{x}}_{t};\widehat{\mathbf{y}}_{t}]=\mathbf{v}_{t+1}$
and
$[\mathbf{w}_{t};\mathbf{p}_{t}]=[\mathbf{x}_{t};\mathbf{y}_{t}]=\mathbf{u}_{t}$
for each $t\in[T]$. As a result, we also have that

$\displaystyle\mathbf{z}_{t}$
$\displaystyle=\frac{1}{\sum_{s=1}^{t}\gamma_{s}}\sum_{s=1}^{t}\gamma_{s}\mathbf{u}_{s}$
$\displaystyle=\left[\frac{1}{\sum_{s=1}^{t}\gamma_{s}}\sum_{s=1}^{t}\gamma_{s}\mathbf{x}_{s};\frac{1}{\sum_{s=1}^{t}\gamma_{s}}\sum_{s=1}^{t}\gamma_{s}\mathbf{y}_{s}\right]$
$\displaystyle=\left[\frac{1}{t}\sum_{s=1}^{t}\mathbf{w}_{s};\frac{1}{t}\sum_{s=1}^{t}\mathbf{p}_{s}\right]$

∎

######  Proposition 3.

Let $\alpha_{t}=1$. Then the total regret of both players under the dynamics
of Algorithm 5 is bounded by

$\displaystyle R^{\mathbf{p}}+R^{\mathbf{w}}=O(\sqrt{\log n})$

Before we prove this result, we need to state a technical tool that we will
make use of.

######  Lemma 6.

For any $\mathbf{p}\in\mathbb{R}^{n}$ and $\mathbf{w}\in\mathbb{R}^{d}$, we
have that

$\displaystyle\|\mathbf{p}^{\top}A\|_{2}\leq\|\mathbf{p}\|_{1}\quad\text{and}\quad\|A\mathbf{w}\|_{\infty}\leq\|\mathbf{w}\|_{2}$

###### Proof.

For the first inequality, let
$\tilde{\mathbf{p}}=\frac{\mathbf{p}}{\|\mathbf{p}\|_{1}}$. Then,

$\displaystyle\|\mathbf{p}^{\top}A\|_{2}=\|\mathbf{p}\|_{1}\|\tilde{\mathbf{p}}^{\top}A\|_{2}=\|\mathbf{p}\|_{1}\left\|\sum_{i=1}^{n}\tilde{p}_{i}A_{(i,:)}\right\|_{2}\leq\|\mathbf{p}\|_{1}\sum_{i=1}^{n}|\tilde{p}_{i}|\|A_{(i,:)}\|_{2}=\|\mathbf{p}\|_{1}$

For the second inequality, we have that

$\displaystyle\|A\mathbf{w}\|_{\infty}=\max_{i\in[n]}\left|A_{(i,:)}^{\top}\mathbf{w}\right|\leq\|\mathbf{w}\|_{2}\max_{i\in[n]}\|A_{(i,:)}\|_{2}=\|\mathbf{w}\|_{2}$

∎

###### Proof of Proposition 3.

Let us first note that, from the proof of Theorem 8, we know that

$\displaystyle\Omega_{\mathbf{w}}=\max_{\mathbf{w}\in\mathcal{B}_{d}}D_{\mathbf{w}}(\mathbf{w},\widehat{\mathbf{w}}_{0})=\frac{1}{2}\quad\text{and}\quad\Omega_{\mathbf{p}}=\max_{\mathbf{p}\in\Delta^{n}}D_{\mathbf{p}}(\mathbf{p},\widehat{\mathbf{p}}_{0})=\log
n$

Then, using Lemmas 4 and 6, we can bound the regret of the $\mathbf{w}$-player
as follows:

$\displaystyle R^{\mathbf{w}}$ $\displaystyle\leq\frac{\sqrt{\log
n}}{2}+\sum_{t=1}^{T}\left[\|(\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t-1})^{\top}A\|_{2}\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t}\|_{2}-\frac{\sqrt{\log
n}}{2}\left(\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t}\|_{2}^{2}+\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t-1}\|_{2}^{2}\right)\right]$
$\displaystyle\leq\frac{\sqrt{\log
n}}{2}+\sum_{t=1}^{T}\left[\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t-1}\|_{1}\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t}\|_{2}-\frac{\sqrt{\log
n}}{2}\left(\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t}\|_{2}^{2}+\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t-1}\|_{2}^{2}\right)\right]$

Similarly, for the $\mathbf{p}$-player we obtain

$\displaystyle R^{\mathbf{p}}$ $\displaystyle\leq\sqrt{\log
n}+\sum_{t=1}^{T}\left[\|A(\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t-1})\|_{\infty}\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t}\|_{1}-\frac{1}{2\sqrt{\log
n}}\left(\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t}\|_{1}^{2}+\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t-1}\|_{1}^{2}\right)\right]$
$\displaystyle\leq\sqrt{\log
n}+\sum_{t=1}^{T}\left[\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t-1}\|_{2}\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t}\|_{1}-\frac{1}{2\sqrt{\log
n}}\left(\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t}\|_{1}^{2}+\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t-1}\|_{1}^{2}\right)\right]$

Adding both bounds then yields

$\displaystyle R^{\mathbf{w}}+R^{\mathbf{p}}$
$\displaystyle\leq\frac{\sqrt{\log n}}{2}+\sqrt{\log n}$ $\displaystyle\hskip
14.22636pt-\frac{1}{2}\sum_{t=1}^{T}\bigg{[}\frac{1}{\sqrt{\log
n}}\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t-1}\|_{1}^{2}+\sqrt{\log
n}\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t}\|_{2}^{2}-2\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t-1}\|_{1}\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t}\|_{2}$
$\displaystyle\hskip 42.67912pt+\sqrt{\log
n}\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t-1}\|_{2}^{2}+\frac{1}{\sqrt{\log
n}}\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t}\|_{1}^{2}-2\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t-1}\|_{2}\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t}\|_{1}\bigg{]}$
$\displaystyle=\frac{\sqrt{\log n}}{2}+\sqrt{\log n}$ $\displaystyle\hskip
14.22636pt-\frac{1}{2}\sum_{t=1}^{T}\bigg{[}\left((\log
n)^{-\frac{1}{4}}\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t-1}\|_{1}-(\log
n)^{\frac{1}{4}}\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t}\|_{2}\right)^{2}$
$\displaystyle\hskip 56.9055pt\left((\log
n)^{\frac{1}{4}}\|\mathbf{w}_{t}-\widehat{\mathbf{w}}_{t-1}\|_{2}-(\log
n)^{-\frac{1}{4}}\|\mathbf{p}_{t}-\widehat{\mathbf{p}}_{t}\|_{1}\right)^{2}\bigg{]}$
$\displaystyle\leq\frac{\sqrt{\log n}}{2}+\sqrt{\log n}$

∎

A nice property of the MPLFP algorithm is that it provides a linear separator
when the data is linearly separable and an approximate certificate of
infeasibility when it is not. Such a certificate is a vector
$\widehat{\mathbf{p}}\in\Delta^{n}$ satisfying
$\widehat{\mathbf{p}}^{\top}A=\mathbf{0}$; the duality of the two problems can
be observed via Gordan’s Theorem. We call $\widehat{\mathbf{p}}\in\Delta^{n}$
an $\epsilon$-certificate of infeasibility if
$\|\widehat{\mathbf{p}}A\|_{2}\leq\epsilon$. Next, we recover the convergence
analysis of MPLFP, from Yu et al. (2014), using the tools of no-regret
learning.

######  Theorem 9.

Let $\alpha_{t}=1$. Then under Assumption 1,
$\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t}$ has a non-negative margin when
$T=\Omega\left(\frac{\sqrt{\log n}}{\gamma}\right)$. On the other hand, if
$\max_{\mathbf{w}\in\mathcal{B}_{d}}\gamma(\mathbf{w})<0$, then
$\frac{1}{T}\sum_{t=1}^{T}\mathbf{p}_{t}$ is an $\epsilon$-certificate of
infeasibility when $T=\Omega\left(\frac{\sqrt{\log n}}{\epsilon}\right)$.

###### Proof.

Note that in this setting, we have that $m(\mathbf{w})=\gamma(\mathbf{w})$ for
each $\mathbf{w}\in\mathcal{B}_{d}$, and
$\frac{1}{T}\sum_{t=1}^{T}w_{t}\in\mathcal{B}_{d}$. Then, under Assumption 1,
we have that $\mathbf{w}^{*}\in\mathcal{B}_{d}$, so Theorem 2 and Proposition
3 yield

$\displaystyle\gamma\left(\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t}\right)=m\left(\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t}\right)\geq
m(\mathbf{w}^{*})-\frac{R^{\mathbf{w}}+R^{\mathbf{p}}}{T}=\gamma(\mathbf{w}^{*})-\frac{R^{\mathbf{w}}+R^{\mathbf{p}}}{T}\geq\gamma-\frac{3\sqrt{\log
n}}{2T}$

That is, the margin is non-negative provided that $T\geq\frac{3\sqrt{\log
n}}{2\gamma}$.

To show the second conclusion, let us begin by noting that with a slight
modification to the proof of Theorem 2, we can obtain

$\displaystyle\max_{\mathbf{w}\in\mathcal{B}_{d}}g\left(\mathbf{w},\frac{1}{T}\sum_{t=1}^{T}\mathbf{p}_{t}\right)\leq\min_{\mathbf{p}\in\Delta^{n}}g\left(\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t},\mathbf{p}\right)+\bar{R}^{\mathbf{w}}+\bar{R}^{\mathbf{p}}=m\left(\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t}\right)+\bar{R}^{\mathbf{w}}+\bar{R}^{\mathbf{p}}$

Our assumption now is that
$\max_{\mathbf{w}\in\mathcal{B}_{d}}m(\mathbf{w})=\max_{\mathbf{w}\in\mathcal{B}_{d}}\gamma(\mathbf{w})<0$,
so that

$\displaystyle\left\|\left(\frac{1}{T}\sum_{t=1}^{T}\mathbf{p}_{t}\right)^{\top}A\right\|_{2}$
$\displaystyle=\max_{\mathbf{w}\in\mathcal{B}_{d}}\left(\frac{1}{T}\sum_{t=1}^{T}\mathbf{p}_{t}\right)^{\top}A\mathbf{w}$
Cauchy-Schwarz
$\displaystyle=\max_{\mathbf{w}\in\mathcal{B}_{d}}g\left(\mathbf{w},\frac{1}{T}\sum_{t=1}^{T}\mathbf{p}_{t}\right)$
$\displaystyle<\bar{R}^{\mathbf{w}}+\bar{R}^{\mathbf{p}}$
$\displaystyle\leq\frac{3\sqrt{\log n}}{2T}$

Hence, $\frac{1}{T}\sum_{t=1}^{T}\mathbf{p}_{t}$ is an $\epsilon$-certificate
of infeasibility provided that $T\geq\frac{3\sqrt{\log n}}{2\epsilon}$. ∎

##  D Proof of Section 5

###  D.1 Proof of Theorem 6

First, based on the property of the objective function from Ji et al. (2021),
we have

$-A^{\top}\mathbf{q}_{t}=\frac{\nabla R(\mathbf{u}_{t})}{R(\mathbf{u}_{t})},$

where

$q_{t,i}=\frac{\exp\left(-y^{(i)}\mathbf{u}_{t}^{\top}\mathbf{x}^{(i)}\right)}{\sum_{j=1}^{n}\exp\left(-y^{(j)}\mathbf{u}_{t}^{\top}\mathbf{x}^{(j)}\right)}.$
(31)

Then, using the fact that $\mathbf{v}_{0}=\mathbf{0}$, we obtain

$\mathbf{v}_{t}=\mathbf{v}_{t-1}+tA^{\top}\mathbf{q}_{t}=\sum_{t=1}^{T}\alpha_{t}A^{\top}\mathbf{q}_{t}=\left(\sum_{i=1}^{t}\alpha_{i}\right)\cdot\mathbf{r}_{t},$

where we define $\mathbf{r}_{0}=0$ and
$\mathbf{r}_{t}=\frac{1}{\sum_{i=1}^{t}\alpha_{i}}\sum_{i=1}^{t}\alpha_{i}A^{\top}\mathbf{q}_{i}$
for $t\geq 1$. Then, we can rewrite

$\begin{split}\mathbf{s}_{t}=\mathbf{s}_{t-1}+\frac{1}{2(t+1)}\mathbf{v}_{t}=\sum_{i=1}^{t}\frac{1}{2(i+1)}\mathbf{v}_{i}=\sum_{i=1}^{t}\frac{1}{2i(i+1)}i\mathbf{v}_{i}={}&\frac{1}{4}\sum_{i=1}^{t}\frac{1}{\sum_{j=1}^{i}\alpha_{j}}i\mathbf{v}_{i}=\frac{1}{4}\sum_{i=1}^{t}\alpha_{i}\mathbf{r}_{i}.\end{split}$

where we used the initialization $\mathbf{s}_{0}=\mathbf{0}$. Moreover,

$\mathbf{u}_{t}=\mathbf{s}_{t-1}+\frac{1}{2(t-1)}\mathbf{v}_{t-1}=\frac{1}{4}\sum_{i=1}^{t-1}\alpha_{i}\mathbf{r}_{i}+\frac{1}{2(t-1)}\mathbf{v}_{t-1}=\frac{1}{4}\sum_{i=1}^{t-1}\alpha_{i}\mathbf{r}_{i}+\frac{1}{4}\alpha_{t}\mathbf{r}_{t-1}.$
(32)

Combining (31) and (32), we have

$\displaystyle\mathbf{q}_{t}$
$\displaystyle=\operatorname*{argmin}\limits_{\mathbf{q}\in\Delta^{n}}\mathbf{q}^{\top}A\mathbf{u}_{t}+D_{E}\left(\mathbf{q},\frac{\mathbf{1}}{n}\right)$
$\displaystyle=\operatorname*{argmin}\limits_{\mathbf{q}\in\Delta^{n}}\frac{1}{4}\left(\sum_{i=1}^{t-1}\alpha_{i}\mathbf{q}^{\top}A\mathbf{r}_{i}+\alpha_{t}\mathbf{q}^{\top}A\mathbf{r}_{t-1}\right)+D_{E}\left(\mathbf{q},\frac{\mathbf{1}}{n}\right).$

Additionally,

$\begin{split}\mathbf{r}_{t}=\frac{1}{\sum_{i=1}^{t}\alpha_{i}}\sum_{i=1}^{t}\alpha_{i}A^{\top}\mathbf{q}_{i}={}&\operatorname*{argmin}\limits_{\mathbf{r}\in\mathbb{R}^{d}}\sum_{i=1}^{t}\alpha_{i}\mathbf{q}_{i}^{\top}A\mathbf{r}+\frac{\sum_{i=1}^{t}\alpha_{i}}{2}\|\mathbf{r}\|_{2}^{2}\\\
={}&\operatorname*{argmin}\limits_{\mathbf{r}\in\mathbb{R}^{d}}\sum_{i=1}^{t}\alpha_{i}\left(\mathbf{q}_{i}^{\top}A\mathbf{r}+\frac{1}{2}\|\mathbf{r}\|_{2}^{2}\right).\end{split}$
(33)

Note that since $\mathbf{r}_{0}=\mathbf{w}_{0}$ and we can drop the
$\frac{1}{2}\|\cdot\|_{2}^{2}$ terms from the minimization in the
$\mathbf{p}$-player’s update (since it doesn’t depend on $\mathbf{p}$), we get
that $\mathbf{q}_{t}=\mathbf{p}_{t}$ and $\mathbf{r}_{t}=\mathbf{w}_{t}$.
Finally, we can conclude that

$\displaystyle\mathbf{s}_{T}=\frac{1}{4}\sum_{t=1}^{T}\alpha_{t}\mathbf{r}_{t}=\frac{\sum_{t=1}^{T}\alpha_{t}}{4}\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}\mathbf{w}_{t}=\frac{\sum_{t=1}^{T}\alpha_{t}}{4}\overline{\mathbf{w}}_{T}=\widetilde{\mathbf{w}}_{T}$

Next, we turn to the regret. For the $\mathbf{p}$-player, it uses OFTRL, so,
based on Lemma 3, we obtain

$\begin{split}{}&\sum_{t=1}^{T}\alpha_{t}\ell_{t}(\mathbf{p}_{t})-\sum_{t=1}^{T}\alpha_{t}\ell_{t}(\mathbf{p})\\\
\leq{}&{4\left(E(\mathbf{p})-E\left(\frac{\mathbf{1}}{n}\right)\right)}+\sum_{t=1}^{T}\frac{t^{2}\|A\mathbf{w}_{t}-A\mathbf{w}_{t-1}\|_{\infty}^{2}}{8}\\\
\leq{}&{4\log
n}+\sum_{t=1}^{T}\frac{t^{2}\left[\max_{i\in[n]}\left|y^{(i)}(\mathbf{w}_{t}-\mathbf{w}_{t-1})^{\top}\mathbf{x}^{(i)}\right|\right]\left[\max_{i\in[n]}\left|y^{(i)}(\mathbf{w}_{t}-\mathbf{w}_{t-1})^{\top}\mathbf{x}^{(i)}\right|\right]}{8}\\\
\leq{}&4{\log
n}+\sum_{t=1}^{T}\frac{t^{2}\|\mathbf{w}_{t}-\mathbf{w}_{t-1}\|_{2}^{2}}{8}.\end{split}$
(34)

On the other hand, the $\mathbf{w}$-player applies FTRL+, and note that
$h_{t}(\mathbf{w})$ is 1-strongly convex. Thus, the regret is bounded by

$\begin{split}\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{w}_{t})-\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{w})\leq{}&-\sum_{t=1}^{T}\frac{t(t-1)}{4}\|\mathbf{w}_{t}-\mathbf{w}_{t-1}\|_{2}^{2}.\end{split}$
(35)

Finally, we focus on the margin. Combining (LABEL:eqn:regret:nag:1), and (35),
we have

$\overline{R}^{\mathbf{w}}+\overline{R}^{\mathbf{p}}=\frac{2}{T(T+1)}\left(4\log
n+\sum_{t=1}^{T}\left(\frac{t^{2}}{8}-\frac{t(t-1)}{4}\right)\|\mathbf{w}_{t}-\mathbf{w}_{t-1}\|_{2}^{2}\right)\leq\frac{8\log
n+2}{T(T+1)},$

where we used the fact that
$\|\mathbf{w}_{1}\|_{2}^{2}=\|A^{\top}\mathbf{q}_{1}\|_{2}^{2}\leq 1$, and
$\frac{t^{2}}{8}\leq\frac{t(t-1)}{4}$ for $t\geq 2$. Based on Theorem 2, we
have

$\begin{split}\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\overline{\mathbf{w}}_{T}-\frac{1}{2}\|\overline{\mathbf{w}}_{T}\|_{2}^{2}=m(\overline{\mathbf{w}}_{T})\geq{}&-\frac{8\log
n+2}{T(T+1)}+\max_{\mathbf{w}\in\mathbb{R}^{d}}m(\mathbf{w}).\end{split}$ (36)

Next, note that
$\overline{\mathbf{w}}=\frac{8}{T(T+1)}\widetilde{\mathbf{w}}_{T}$. So

$\begin{split}{}&\frac{8}{T(T+1)}\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\widetilde{\mathbf{w}}_{T}-\frac{64}{2(T(T+1))^{2}}\|\widetilde{\mathbf{w}}_{T}\|_{2}^{2}\\\
\geq{}&-\frac{8\log
n+2}{T(T+1)}+\max_{\mathbf{w}\in\mathbb{R}^{d}}m(\mathbf{w})\\\
\geq{}&-\frac{8\log
n+2}{T(T+1)}+m\left(\frac{8\|\widetilde{\mathbf{w}}_{T}\|_{2}}{T(T+1)}\mathbf{w}^{*}\right)\\\
={}&-\frac{8\log
n+2}{T(T+1)}+\frac{8\|\widetilde{\mathbf{w}}_{T}\|_{2}}{T(T+1)}\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{w}^{*}-\frac{64\|\widetilde{\mathbf{w}}_{T}\|_{2}^{2}}{2(T(T+1))^{2}}\|\mathbf{w}^{*}\|_{2}^{2}\\\
={}&-\frac{8\log
n+2}{T(T+1)}+\frac{8\|\widetilde{\mathbf{w}}_{T}\|_{2}\gamma}{T(T+1)}-\frac{64\|\widetilde{\mathbf{w}}_{T}\|_{2}^{2}}{2(T(T+1))^{2}},\\\
\end{split}$ (37)

which implies that

$\begin{split}\frac{\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\widetilde{\mathbf{w}}_{T}}{\|\widetilde{\mathbf{w}}_{T}\|_{2}}\geq-\frac{8\log
n+2}{8\|\widetilde{\mathbf{w}}_{T}\|_{2}}+\gamma.\end{split}$ (38)

Finally, note that we always have
$\frac{\widetilde{\mathbf{w}}_{T}^{\top}\mathbf{w}^{*}}{\|\widetilde{\mathbf{w}}_{T}\|_{2}}\leq
1$, so

$\begin{split}\|\widetilde{\mathbf{w}}_{T}\|_{2}\geq{}&\frac{\sum_{t=1}^{T}\alpha_{t}}{4}\overline{\mathbf{w}}_{T}^{\top}\mathbf{w}^{*}\\\
={}&\frac{\sum_{t=1}^{T}\alpha_{t}}{4}\left(\frac{1}{\sum_{t=1}^{T}\alpha_{t}}\sum_{t=1}^{T}\alpha_{t}\mathbf{p}_{t}\right)^{\top}A\mathbf{w}^{*}\geq\frac{T(T+1)\gamma}{8}.\end{split}$
(39)

Thus, we have

$\frac{\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\mathbf{s}_{T}}{\|\mathbf{s}_{T}\|_{2}}=\frac{\min\limits_{\mathbf{p}\in\Delta^{n}}\mathbf{p}^{\top}A\widetilde{\mathbf{w}}_{T}}{\|\widetilde{\mathbf{w}}_{T}\|_{2}}\geq\gamma-\frac{8\log
n+2}{T(T+1)\gamma}.$

###  D.2 Proof of Theorem 7

Recall that $\alpha_{t}=1$, for all $t\in[T]$, and that the regularizer
$\frac{1}{2(q-1)}\|\cdot\|_{q}^{2}$ is 1-strongly convex w.r.t.
$\|\cdot\|_{q}$. Then, for the $\mathbf{w}$-player, based on Lemma 3, we have
$\forall\mathbf{w}\in\mathbb{R}^{d},\|\mathbf{w}\|_{q}\leq 1$,

$\begin{split}\sum_{t=1}^{T}h_{t}(\mathbf{w}_{t})-h_{t}(\mathbf{w})\leq{}&\frac{1}{2(q-1)\eta^{\mathbf{w}}}+\sum_{t=1}^{T}\frac{\|A^{\top}(\mathbf{p}_{t}-\mathbf{p}_{t-1})\|^{2}_{p}}{2/\eta^{\mathbf{w}}}\\\
={}&\frac{1}{2(q-1)\eta^{\mathbf{w}}}+\sum_{t=1}^{T}\frac{\|\sum_{i=1}^{n}y^{(i)}[\mathbf{p}_{t}-\mathbf{p}_{t-1}]_{i}\mathbf{x}^{(i)}\|^{2}_{p}}{2/\eta^{\mathbf{w}}}\\\
\leq{}&\frac{1}{2(q-1)\eta^{\mathbf{w}}}+\sum_{t=1}^{T}\frac{\left(\sum_{i=1}^{n}|\mathbf{p}_{t}-\mathbf{p}_{t-1}|_{i}\|\mathbf{x}^{(i)}\|_{p}\right)^{2}}{2/\eta^{\mathbf{w}}}\\\
\leq{}&\frac{1}{2(q-1)\eta^{\mathbf{w}}}+\sum_{t=1}^{T}\frac{\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2}}{2/\eta^{\mathbf{w}}}\end{split}$
(40)

On the other hand, for the $\mathbf{p}$-player, applying Lemma 2, we get

$\begin{split}\sum_{t=1}^{T}\ell_{t}(\mathbf{p}_{t})-\ell_{t}(\mathbf{p})\leq\frac{\log
n}{\eta^{\mathbf{p}}}-\sum_{t=1}^{T}\frac{1}{2\eta^{\mathbf{p}}}\|\mathbf{p}_{t}-\mathbf{p}_{t-1}\|_{1}^{2}.\end{split}$
(41)

Thus, with $\eta^{\mathbf{p}}=1/\eta^{\mathbf{w}}$,
$\eta^{\mathbf{w}}=\sqrt{\frac{1}{2(q-1)\log n}}$, we get

$m(\overline{\mathbf{w}}_{T})\geq\gamma-\frac{\sqrt{\frac{{2\log
n}}{(q-1)}}}{T}=\gamma-\frac{\sqrt{2(p-1)\log n}}{T},$ (42)

where the equality is based on the relationship between $p$ and $q$. Hence, we
obtain a positive margin when $T>\frac{\sqrt{2(p-1)\log n}}{\gamma}$. On the
other hand, let $\alpha\in(0,1)$, and if we would like to obtain

$\gamma-\frac{\sqrt{2(p-1)\log n}}{T}\geq(1-\alpha)\gamma,$

we have $T\geq\frac{\sqrt{2(p-1)\log n}}{\alpha\gamma}.$