# Simple Stochastic and Online Gradient Descent Algorithms for Pairwise
Learning

Zhenhuan Yang1∗ Yunwen Lei2∗ Puyu Wang3 Tianbao Yang4 Yiming Ying1
1University at Albany, SUNY, Albany, NY 2University of Birmingham, Birmingham
3City University of Hong Kong, Hong Kong 4University of Iowa City, IA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Pairwise learning refers to learning tasks where the loss function depends on
a pair of instances. It instantiates many important machine learning tasks
such as bipartite ranking and metric learning. A popular approach to handle
streaming data in pairwise learning is an online gradient descent (OGD)
algorithm, where one needs to pair the current instance with a buffering set
of previous instances with a sufficiently large size and therefore suffers
from a scalability issue. In this paper, we propose simple stochastic and
online gradient descent methods for pairwise learning. A notable difference
from the existing studies is that we only pair the current instance with the
previous one in building a gradient direction, which is efficient in both the
storage and computational complexity. We develop novel stability results,
optimization, and generalization error bounds for both convex and nonconvex as
well as both smooth and nonsmooth problems. We introduce novel techniques to
decouple the dependency of models and the previous instance in both the
optimization and generalization analysis. Our study resolves an open question
on developing meaningful generalization bounds for OGD using a buffering set
with a very small fixed size. We also extend our algorithms and stability
analysis to develop differentially private SGD algorithms for pairwise
learning which significantly improves the existing results. ††∗ Equal
contributions. The corresponding author is Yiming Ying.

##  1 Introduction

Many important learning tasks involve pairwise loss functions which are often
referred to as pairwise learning. Such notable learning tasks include AUC
maximization [15, 22, 28, 37, 46, 48], metric learning [4, 24, 39, 41, 44],
and a minimum error entropy principle [19]. For instance, AUC maximization
aims to rank positive instances above negative ones which involves a loss
$f(\mathbf{w};(x,y),(x^{\prime},y^{\prime}))=(1-\mathbf{w}^{\top}(x-x^{\prime}))_{+}\,\mathbb{I}_{[y=1\wedge
y^{\prime}=-1]}$ with $x,x^{\prime}\in\mathcal{X}\subseteq\mathbb{R}^{d}$ and
$y,y^{\prime}\in\mathcal{Y}=\\{\pm 1\\}.$ The aim of metric learning is to
learn a distance function
$h_{\mathbf{w}}(x,x^{\prime})=(x-x^{\prime})^{\top}\mathbf{w}(x-x^{\prime})$
where $\mathbf{w}$ is positive semi-definite matrix in $\mathbb{R}^{d\times
d}$. A typical pairwise loss can be
$f(\mathbf{w};(x,y),(x^{\prime},y^{\prime}))=(1+\tau(y,y^{\prime})h_{\mathbf{w}}(x,x^{\prime}))_{+}$
where $\tau(y,y^{\prime})=1$ if $y=y^{\prime}$ and $-1$ otherwise. Given a
training data
$S=\\{z_{i}=(x_{i},y_{i})\in\mathcal{X}\times\mathcal{Y}:i\in[n]\\}$ where
$[n]=\\{1,2,\ldots,n\\}$, the ERM formulation for pairwise learning is defined
as $\min_{\mathbf{w}\in\mathcal{W}}\frac{1}{n(n-1)}\sum_{i,j\in[n],i\neq
j}^{n}f(\mathbf{w};z_{i},z_{j})$ where $\mathcal{W}$ denotes the parameter
space. This scheme has been well studied theoretically using algorithmic
stability [1] and U-statistics tools [11]. At the same time, there are
considerable interests on developing and studying online gradient descent
(OGD) or stochastic gradient descent (SGD) algorithms for pairwise learning
due to their scalability in practice.

The critical issue for designing such stochastic algorithms is to construct
intersecting pairs of instances for updating the model parameter upon
receiving individual instances. For the offline (finite-sum) setting where the
prescribed training data $S=\\{z_{1},\ldots,z_{n}\\}$ is available, one
natural approach is to, at each time $t$, randomly select a pair of instances
$(z_{i_{t}},z_{j_{t}})$ from $n(n-1)/2$ pairs and update $\mathbf{w}$ based on
the gradient of the local error $f(\mathbf{w}_{t-1};z_{i_{t}},z_{j_{t}})$. The
excess generalization and stability was nicely established in [27]. One
popular approach [22, 38, 48, 45] is to consider the online setting where the
data is continuously arriving. This approach pairs the current datum
$z_{t}=(x_{t},y_{t})$, which is received at time $t$, with all previous
instances $S_{t-1}=\\{z_{1},\ldots,z_{t-1}\\}$ and then performs the update
based on the gradient of the local error
$f(\mathbf{w}_{t-1};S_{t-1})=\frac{1}{t-1}\sum_{z\in
S_{t-1}}f(\mathbf{w}_{t-1};z_{t},z)$. It requires a high gradient complexity
$\mathcal{O}(t)$ (i.e. the number of computing gradients) which is expensive
when $t$ becomes large. To mitigate this potential limitation, [22, 48, 37]
proposed to use a buffering set $B_{t-1}\subseteq S_{t-1}$ of size $s$ and the
local error $f(\mathbf{w}_{t-1};B_{t-1})=\frac{1}{s}\sum_{z\in
B_{t-1}}f(\mathbf{w}_{t-1};z_{t},z)$ which reduces the gradient complexity to
$\mathcal{O}(s)$. The excess generalization bound
$\mathcal{O}(\frac{1}{\sqrt{s}}+\frac{1}{\sqrt{n}})$ was established in [22]
using the online-to-batch conversion method [8] which is only meaningful for a
very large $s$. In particular, this bound tends to zero only when $s=s(n)$
tends to infinity as $n$ tends to infinity. It was mentioned in [22] (see the
discussion at the end of Section 7 there) as an open question on how to get a
meaningful bound for a fixed constant $s$.

In this paper, we show that optimal generalization bounds can be achieved for
simple SGD and OGD algorithms for pairwise learning where, at time $t$, the
current instance $z_{t}$ is only paired with the previous instance $z_{t-1}$.
This is equivalent to the First-In-First-Out (FIFO) buffering strategy [37,
22] while keeping the size $s$ of the buffering set $B_{t-1}$ to be $s=1$,
where, in this FIFO policy, the data $z_{t}$ arriving at time $t>1$ is
included into the buffer by removing $\\{z_{1},\ldots,z_{t-2}\\}$ from the
buffer. In particular, our main contributions are summarized as follows.

  * •

We propose simple SGD and OGD algorithms for pairwise learning where the
$t$-th update of the model parameter is based on the interacting of the
current instance and the previous one which has a constant gradient complexity
$\mathcal{O}(1)$.

  * •

We establish the stability results of the proposed SGD algorithms for pairwise
learning and apply them to derive optimal excess generalization bounds
$\mathcal{O}(1/{\sqrt{n}})$ for the proposed simple SGD algorithm for pairwise
learning with both convex and nonconvex as well as both smooth and nonsmooth
losses in the offline (finite-sum) setting where the training data of size $n$
is given. We introduce novel techniques to decouple the dependency of the
current SGD iterate with the previous instance in both the generalization and
optimization error analysis, which resolves the open question in [22] on how
to develop meaningful generalization bounds when the buffering set of FIFO has
a very small size.

  * •

We further develop a localization version of our SGD algorithms under
$(\epsilon,\delta)$-differential privacy (DP) constraints, and apply the
obtained stability results to derive an optimal utility (excess
generalization) bound
$\tilde{\mathcal{O}}\big{(}{1}/{\sqrt{n}}+{\sqrt{d}}/{n\epsilon}\big{)}$. In
contrast to the existing work [21] which requires the loss function to be
smooth and an at least quadratic gradient complexity, our proposed DP
algorithms only need a linear gradient complexity $\tilde{\mathcal{O}}(n)$ for
smooth convex losses to achieve the optimal utility bound and can also be
applied to non-smooth convex losses.

The paper is organized as follows. Section 2 reviews the related work and
Section 3 describes the proposed algorithms. In Section 4, we present excess
generalization bounds, stability results, and optimization errors of our
algorithms. Section 5 is devoted to the differentially private SGD for
pairwise learning and its utility bounds. Section 6 provides experimental
validation of theoretical findings. The paper is concluded in Section 7. All
the main proofs are postponed to the Appendix.

##  2 Motivating Examples and Related Work

In this section, we list examples of pairwise learning and discuss some
related work.

###  2.1 Motivating Examples

AUC maximization. Area under the ROC curve (AUC) of a prediction function
$h_{\mathbf{w}}$ is the probability that the function ranks a random positive
example higher than a random negative example. The empirical risk of AUC
maximization is given by
$F_{S}(\mathbf{w})=\frac{1}{n(n-1)}\sum_{i,j\in[n],i\neq
j}\ell(h_{\mathbf{w}}(\mathbf{x}_{i})-h_{\mathbf{w}}(\mathbf{x}_{j}))\mathbb{I}_{[y_{i}=1]}\mathbb{I}_{[y_{j}=-1]},$
where the loss $\ell(\cdot)$ can be the least square loss $\ell(t)=(1-t)^{2}$
or the hinge loss $\ell(t)=(1-t)_{+}.$

Minimum error entropy principle. Minimum error entropy (MEE) is a principle of
information theoretical learning [19, 20], which aims to find a predictor
$h:\mathcal{X}\mapsto\mathcal{Y}$ by minimizing the information entropy of the
variable $E=Y-h(X)$. The Rényi’s entropy of order $2$ for $E$ is defined as
$H(E)=-\log\int p_{E}^{2}(e)de$. Here $p_{E}$ is probability density function
and can be approximated by Parzen windowing
$\hat{p}_{E}(e)=\frac{1}{n\gamma}\sum_{i=1}^{n}G\big{(}\frac{(e-e_{i})^{2}}{2\gamma^{2}}\big{)}$,
where $e_{i}=y_{i}-h(x_{i})$, and $\gamma>0$ is an MEE scaling parameter and
$G:\mathbb{R}\mapsto\mathbb{R}^{+}$ is a windowing function. The approximation
of Rényi’s entropy is given by its empirical version
$\hat{H}=-\log\frac{1}{n^{2}\gamma}\sum_{i,j\in[n]}G\big{(}\frac{(e_{i}-e_{j})^{2}}{2\gamma^{2}}\big{)}.$
The maximization of $\hat{H}$ then leads to a pairwise learning problem since
each loss function involves a pair of training examples [19].

Metric learning. Metric learning aims to fine a distance metric
$h_{\mathbf{w}}:\mathcal{X}\times\mathcal{X}\mapsto\mathbb{R}_{+}$ consistent
with some supervised information, e.g., examples within the same class are
close while examples from different classes are apart from each other under
the learnt metric. If $\mathcal{Y}=\\{\pm 1\\}$, the performance of $h$ on an
example pair $z,z^{\prime}$ can be quantified by a loss function of the form
$f(\mathbf{w};z,z^{\prime})=\ell(yy^{\prime}(1-h_{\mathbf{w}};x,x^{\prime}))$,
where $\ell:\mathbb{R}\mapsto\mathbb{R}_{+}$ is a decreasing function for
which some typical choices include the hinge loss $\ell(t)=(1-t)_{+}$ and the
exponential function $\ell(t)=\log(1+\exp(-t))$. Then one can minimize the
training error $F_{S}(\mathbf{w})=\frac{1}{n(n-1)}\sum_{i,j\in[n]:i\neq
j}f(\mathbf{w};z_{i},z_{j})$ to learn a distance metric. Another closely
related learning task to metric learning is constrastive learning [35, 40, 30,
10] which has become very popular recently for learning visual representations
without supervision.

###  2.2 Related Work

The work [22, 37, 38, 48] assumed the online learning setting in which a
stream of i.i.d. data $\\{z_{1},z_{2},\ldots,z_{t},\ldots\\}$ is continuously
arriving. Upon receiving $z_{t}$ at time $t$, it is paired with all previous
instances and then the model parameter is updated based on the local error
$F_{t}(\mathbf{w}_{t-1})=\frac{1}{t-1}\sum_{j=1}^{t-1}f(\mathbf{w}_{t-1};\mathbf{z}_{t},\mathbf{z}_{j}).$
In particular, the work [37, 38] provided the first excess generalization
bound for online learning methods by obtaining online-to-batch conversion
bounds [8] using covering numbers of function classes. Kar et al. [22]
significantly improved the results using the so-called symmetrization of
expectations which reduce excess risk estimates to Rademacher complexities. To
further reduce the expensive gradient complexity $\mathcal{O}(t)$ at a large
time $t$, the work [22, 38, 48] proposed to use a buffering set $B_{t-1}$ with
size $s$ instead of all previous instances. It was shown that such OGD
algorithms have an excess generalization bound
$\mathcal{O}(\frac{1}{\sqrt{s}}+\frac{1}{\sqrt{n}})$ for convex and Lipschitz-
continuous losses. In the offline learning setting where the training data
$S=\\{z_{1},z_{2},\ldots,z_{n}\\}$ of size $n$ is fixed, the work [43]
considered the stochastic version of the algorithm in [37, 22] where, at time
$t$, a random instance $z_{i_{t}}$ with random index
$i_{t}\in\\{1,\ldots,n\\}$ is paired with all previous instances
$\\{z_{i_{1}},\ldots,z_{i_{t-1}}\\}.$ They derived stability and
generalization results of such algorithms in expectation.

Lei et al. [27] considered the offline learning setting and, at time $t$, the
algorithm there randomly picks a pair of instances
$(\mathbf{z}_{i_{t}},\mathbf{z}_{j_{t}})$ from all $\binom{n}{2}$ pairs of
instances. An excess risk bound
$\tilde{\mathcal{O}}\big{(}1/{\sqrt{n}}\big{)}$ with high probability was
derived for convex, Lipschitz and strongly smooth losses. Here the notation
$\tilde{\mathcal{O}}(\cdot)$ means $\mathcal{O}(\cdot)$ up to some logarithmic
terms. In the particular case of AUC maximization with the least square loss,
[46] considered the online learning setting and reformulated the problem as a
stochastic saddle point (min-max) problem which decouples the pairwise
structure. From this reformulation, efficient SGD-type algorithms [44, 29]
have been developed.

Recently, differentially private pairwise learning has been studied where the
construction of pairs of instances follows [22, 37, 48] or all pairs are used
at each iteration. In particular, Huai et al. [21] considered both online and
offline learning settings and the pairs of instances at time $t$ follow [22,
37, 48]. They provided a utility bound
$\widetilde{\mathcal{O}}(\sqrt{d}/(\sqrt{n}\epsilon))$ for convex and smooth
loss functions. The study [43] also paired the current instance with all
previous ones and showed that SGD with output perturbation for pairwise
learning has a utility bound
$\widetilde{\mathcal{O}}(\sqrt{d}/(\sqrt{n}\epsilon))$ for nonsmooth convex
losses. The work [42] showed that private gradient descent using all possible
pairs can achieve a utility bound
$\widetilde{\mathcal{O}}(1/\sqrt{n}+\sqrt{d}/(n\epsilon))$ for strongly smooth
and convex losses.

##  3 Proposed Algorithms for Pairwise Learning

In this section, we describe the proposed algorithms in two common learning
settings for pairwise learning: offline and online learning settings. Let
$\rho$ be a probability measure defined on
$\mathcal{Z}:=\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$ is an input
space and $\mathcal{Y}$ is an output space. In pairwise learning, the
performance of ${\mathbf{w}}$ is measured on a pair of instances
$(z,z^{\prime})$ by a nonnegative loss function $f(\mathbf{w};z,z^{\prime})$.
Denote by $[n]:=\\{1,2,\ldots,n\\}$ for any $n\in\mathbb{N}$.

1: Inputs: $S\\!=\\!\\{z_{i}\\!:i\in[n]\\}$ and step sizes $\\{\eta_{t}\\}$

2: Initialize: $\mathbf{w}_{0}\in\mathcal{W}$, let
$\mathbf{w}_{-1}=\mathbf{w}_{0}$ and randomly select $i_{0}\in[n]$

3: for $t=1,2,\ldots,T$ do

4:  Randomly select ${i_{t}}\in[n]$

5:
$\\!\mathbf{w}_{t}\\!=\\!{\Pi}_{\mathcal{W}}\bigl{(}\mathbf{w}_{t-1}\\!-\\!{\eta_{t}}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})\bigr{)}$

6: Outputs:
$\bar{\mathbf{w}}_{T}={\sum_{j=1}^{T}\eta_{j}\mathbf{w}_{j-2}}/\sum_{j=1}^{T}\eta_{j}$

Algorithm 1 SGD for Pairwise Learning

1: Inputs: learning rates $\\{\eta_{t}\\}$

2: Initialize: $\mathbf{w}_{0}\in\mathcal{W}$, let
$\mathbf{w}_{-1}=\mathbf{w}_{0}$ and receiving datum $z_{0}$.

3: for $t=1,2,\ldots,T$ do

4: Receive a data point $z_{t}$

5:
$\mathbf{w}_{t}={\Pi}_{\mathcal{W}}\bigl{(}\mathbf{w}_{t-1}-{\eta_{t}}\nabla
f(\mathbf{w}_{t-1};z_{t},z_{t-1})\bigr{)}$

6: Outputs:
$\widetilde{\mathbf{w}}_{T}={\sum_{j=1}^{T}\eta_{j}\mathbf{w}_{j-2}}/\sum_{j=1}^{T}\eta_{j}$

Algorithm 2 OGD for Pairwise Learning

Offline Learning (Finite-Sum) Setting. The first is the finite-sum setting
where the training data $S=\\{z_{i}=(x_{i},y_{i})\in\mathcal{Z}:i\in[n]\\}$
are drawn independently according to $\rho$. In this context, one aims to
solve the following empirical risk minimization (ERM):

$\mathbf{w}^{\ast}_{S}=\operatorname*{argmin}_{\mathbf{w}\in\mathcal{W}}\Big{[}F_{S}(\mathbf{w}):=\frac{1}{n(n-1)}\sum_{i,j\in[n],i\neq
j}f(\mathbf{w};z_{i},z_{j})\Big{]}.$ (1)

Our proposed algorithm to solve (1) is described in Algorithm 1. The notation
${\Pi}_{\mathcal{W}}(\cdot)$ there denotes the projection operator to
$\mathcal{W}.$ In particular, at iteration $t$, it randomly selects one
instance $z_{i_{t}}$ from the uniform distribution over $[n]$ and pairs it
only with the previous instance $z_{i_{t-1}}$, and then do the gradient
descent based on $\nabla f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}}).$ This is
in contrast to the classical SGD for pairwise learning in [37, 22, 48] where
the present instance $z_{i_{t}}$ is paired with all previous instances
$\\{z_{i_{1}},z_{i_{2}},\ldots,z_{i_{t-1}}\\}$. Note $\mathbf{w}_{t-1}$
depends on $z_{i_{t-1}}$ and then $\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})$ is not an unbiased estimate of
$\nabla F_{S}(\mathbf{w}_{t-1})$. Therefore, the standard analysis of SGD does
not apply. We introduce novel techniques to handle this dependency in our
analysis (see more details in Section 4).

Online Learning Setting. In the online learning setting where the data
$\\{z_{0},z_{1},z_{2},\ldots\\}$ is assumed i.i.d. from an unknown
distribution $\rho$ on $\mathcal{Z}$, the number of iterations of an online
algorithm is identical to the size of available data. In the same spirit to
Algorithm 1, the pseudo code is given in Algorithm 2. Specifically, upon
receiving a datum $z_{t}$ at the current time $t$, we pair it with $z_{t-1}$
which was revealed at the previous time $t-1$ and then perform gradient
descent based on the gradient $\nabla f(\mathbf{w}_{t-1};z_{t},z_{t-1}).$ It
aims to minimize the population risk which is defined as
$F(\mathbf{w})=\mathbb{E}_{Z,Z^{\prime}}[f(\mathbf{w};Z,Z^{\prime})].$ Here
$\mathbb{E}_{Z,Z^{\prime}}$ denotes the expectation with respect to (w.r.t.)
$Z,Z^{\prime}\sim\rho.$

It is worth pointing out that online learning [32, 18, 31] in general does not
require the i.i.d. assumption on the data and study the regret bounds. In this
paper, we mainly consider the statistical performance, measured by excess
generalization bounds, of the output $\widetilde{\mathbf{w}}_{T}$ of Algorithm
2 where the streaming data $\\{z_{0},z_{1},z_{2},\ldots\\}$ is i.i.d. from the
population distribution $\rho.$

######  Remark 1.

As discussed above, OGD for pairwise learning was proposed and studied in [37,
22] where the current instance $z_{t}$ is paired with a buffering set
$B_{t}\subseteq\\{z_{1},\ldots,z_{t-1}\\}.$ However, the resultant excess
generalization bound is in the form of
$\mathcal{O}(\frac{1}{\sqrt{s}}+\frac{1}{\sqrt{n}})$ which indicated that the
buffer size $s$ needs to be large enough in order to achieve good
generalization. Their analysis does not apply to our case since the buffering
set $B_{t}=\\{z_{t-1}\\}$ with size $s=1$ for Algorithm 2. As we show soon in
Section 4, we can prove that Algorithm 2, which pairs the current instance
$z_{t}$ with the previous instance $z_{t-1}$, still enjoys optimal statistical
performance $\mathcal{O}(1/{\sqrt{n}}).$

######  Remark 2.

The work [27] studied the stability and generalization of an SGD-type
algorithm for pairwise learning by randomly generating pairs of instances.
Specifically, at time $t$, randomly generating a pair $(z_{i_{t}},z_{j_{t}})$
from a given set of training data $S=\\{z_{i}:i\in[n]\\}$ and the subsequent
update is given by $\mathbf{w}_{t}=\mathbf{w}_{t-1}-\eta_{t}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{j_{t}}).$ In contrast, our algorithm, i.e.
Algorithm 1, updates the model parameter based on the pair of the current
random instance and the random one generated at the previous time $t-1$, i.e.
$(z_{i_{t}},z_{i_{t-1}}).$ Furthermore, our work here significantly differs
from [27] in the following aspects. Firstly, the algorithm there by randomly
selecting pairs of instances does not work in the online learning setting
while ours can seamlessly deal with the streaming data as stated in Algorithm
2. Secondly, regarding the technical analysis, our algorithms are more
challenging to analyze than the algorithm in [27]. Indeed, $\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{j_{t}})$ is not an unbiased estimate of
$\nabla F_{S}(\mathbf{w}_{t-1})$ due to the independency between
$\mathbf{w}_{t-1}$ and $(i_{t},j_{t})$. Therefore, the optimization error
analysis of the algorithm in [27] is the same as the SGD for pointwise
learning. As a comparison, $\nabla f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})$
is a biased estimate of $\nabla F_{S}(\mathbf{w}_{t-1})$ due to the coupling
between $\mathbf{w}_{t-1}$ and $i_{t-1}$. We introduce novel techniques to
handle this coupling for both the optimization and generalization analyses.
Thirdly, we will soon see below that we provide generalization results for
nonsmooth, nonconvex losses and also use Algorithm 1 to develop novel
differentially private pairwise learning algorithms while [27] focused on the
smooth convex losses in the non-private setting.

######  Remark 3.

If we let $\xi_{t}=(i_{t},i_{t-1})$ in Algorithm 1, then
$\\{\xi_{t}:t\in\mathbb{N}\\}$ forms a Markov Chain as $\xi_{t}$ only depends
on $\xi_{t-1}$ but not on $\\{\xi_{1},\ldots,\xi_{t-2}\\}.$ Hence, Algorithm 1
can be regarded as a Markov Chain SGD which was studied in [36]. Despite this
similarity, our results differ from [36] in two important aspects. Firstly, we
are mainly interested in stability and generalization of Algorithm 1 while
[36] focused on the convergence analysis of the Markov Chain SGD. One cannot
apply the results in [36] to obtain excess generalization bounds for Algorithm
1 in terms of the population risk as we will show soon in the next section.
Secondly, directly applying Theorem 1 in [36] only yields a convergence rate
of $\mathcal{O}(1/t^{1-q})$ with some $1/2<q<1$ in the convex setting. Our
proof for the convergence analysis of Algorithm 1 is much simpler and direct
which can yield a faster convergence rate $\mathcal{O}(1/\sqrt{t})$ as shown
in Section 4.3.

##  4 Generalization Analysis

The aim for the generalization analysis of Algorithm 1 and Algorithm 2 is the
same, i.e. to analyze the excess generalization error
$F(\mathbf{w})-F(\mathbf{w}^{*})$ of a model $\mathbf{w}$ measuring its
relative behavior w.r.t. the best model
$\mathbf{w}^{*}=\arg\min_{\mathbf{w}\in\mathcal{W}}F(\mathbf{w})$.

For Algorithm 1 where the training data $S$ with $n$ datum is given
beforehand, the excess generalization involves the generalization error and
optimization error. Specifically, one has the following error decomposition
for $\bar{\mathbf{w}}_{T}$

$\mathbb{E}\big{[}F(\bar{\mathbf{w}}_{T})\big{]}-F(\mathbf{w}^{*})=\mathbb{E}\big{[}F(\bar{\mathbf{w}}_{T})-F_{S}(\bar{\mathbf{w}}_{T})\big{]}+\mathbb{E}\big{[}F_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*})\big{]}.$
(2)

Here, the expectation is taken w.r.t. the randomness of Algorithm 1, i.e.,
$\\{i_{t}\\}$ and the randomness of data $S$ which is i.i.d. from $\rho$ on
$\mathcal{Z}.$ We refer to the first term
$\mathbb{E}\big{[}F(\bar{\mathbf{w}}_{T})-F_{S}(\bar{\mathbf{w}}_{T})\big{]}$
as the generalization error and
$\mathbb{E}\big{[}F_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*})\big{]}$ as
the optimization error. We will use algorithmic stability to handle its
generalization error in Subsection 4.2 for smooth and nonsmooth losses. The
estimation of the optimization error is given in Subsection 4.3 for both
convex and nonconvex losses. For Algorithm 2, there is no generalization error
as the data $\\{z_{1},z_{2},\ldots,z_{T}\\}$ is arriving in a sequential
manner with $T$ increasing all the time which does not involve the training
data. The randomness of Algorithm 2 is only from the i.i.d. data. Therefore,
the optimization error in this setting is exactly the excess generalization
error $F(\widetilde{\mathbf{w}}_{T})-F(\mathbf{w}^{*})$ which is estimated in
Subsection 4.3.

###  4.1 Excess Generalization Error

In this subsection, we present excess generalization error bounds of Algorithm
1 in terms of the sample size, iteration number and step size, which shows how
to tune these parameters to get a model with good generalization. Our analysis
requires the following assumptions.

######  Assumption.

Let $f:\mathcal{W}\times\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}^{+}$ and let
$\|\cdot\|_{2}$ denote the Euclidean norm.

  1. (A1)

Assume, for any $z,z^{\prime}$ and $\mathbf{w}\in\mathcal{W}$, that
$f(\cdot;z,z^{\prime})$ is $G$-Lipschitz continuous, i.e.
$|f(\mathbf{w};z,z^{\prime})-f(\mathbf{w}^{\prime};z,z^{\prime})|\leq
G\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}.$

  2. (A2)

Assume, for any $z,z^{\prime}\in\mathcal{Z}$, the map $\mathbf{w}\mapsto
f(\mathbf{w};z,z^{\prime})$ is $L$-strongly smooth, i.e.
$f(\mathbf{w};z,z^{\prime})-f(\mathbf{w}^{\prime};z,z^{\prime})-\langle\nabla
f(\mathbf{w}^{\prime};z,z^{\prime}),\mathbf{w}-\mathbf{w}^{\prime}\rangle\leq\frac{L}{2}\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}^{2}.$

  3. (A3)

Assume, for any $z,z^{\prime}\in\mathcal{Z}$, $f(\cdot;z,z^{\prime})$ is
$\alpha$-strongly convex, i.e.
$f(\mathbf{w};z,z^{\prime})-f(\mathbf{w}^{\prime};z,z^{\prime})-\langle\nabla
f(\mathbf{w}^{\prime};z,z^{\prime}),\mathbf{w}-\mathbf{w}^{\prime}\rangle\geq\frac{\alpha}{2}\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}^{2}.$
The case of $\alpha=0$ is identical to convexity.

  4. (A4)

Assume $F_{S}$ satisfies the Polyak-Łojasiewicz (PL) condition with parameter
$\mu\\!>\\!0$, i.e., for
$\mathbf{w}_{S}\\!\in\\!\arg\min_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w})$,
there holds
$2\mu\big{(}F_{S}(\mathbf{w})\\!-\\!F_{S}(\mathbf{w}_{S})\big{)}\\!\leq\\!\|\nabla
F_{S}(\mathbf{w})\|_{2}^{2}$ for all $\mathbf{w}\in\mathcal{W}$.

The PL condition (A4) means that the suboptimality in terms of function values
can be bounded by gradients [23]. Functions under the PL condition have found
various applications including neural networks, matrix factorization,
generalized linear models and robust regression (see, e.g., [23]). In
particular, AUC maximization problem with the classifier given by a one hidden
layer network satisfies the PL condition as shown in [29].

We first study smooth and non-smooth problems for the convex case, and derive
the excess generalization bounds of the order $\mathcal{O}(1/\sqrt{n})$ in
both cases. We use the notation $B\asymp\tilde{B}$ if there exist constants
$c_{1},c_{2}>0$ such that $c_{1}\tilde{B}\leq B\leq c_{2}\tilde{B}$. The
proofs are given in Section C.

######  Theorem 1 (Nonsmooth Problems).

Let $\mathbf{w}_{-1}=\mathbf{w}_{0}$ and $\\{\mathbf{w}_{t}:t\in[T]\\}$ be
produced by Algorithm 1 with $\eta_{t}=\eta>0$. Let
$\bar{\mathbf{w}}_{T}=\sum_{t=1}^{T}\eta_{t}\mathbf{w}_{t-2}/\sum_{t=1}^{T}\eta_{t}$.
Let (A1) and (A3) hold true with $\alpha=0$. Then, we have

$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})]-F(\mathbf{w}^{*})=\mathcal{O}\Big{(}\sqrt{T}\eta+\frac{T\eta}{n}+\frac{1+T\eta^{2}}{T\eta}\Big{)}.$
(3)

Furthermore, selecting $T\asymp n^{2}$ and $\eta\asymp T^{-\frac{3}{4}}$
yields that
$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})]-F(\mathbf{w}^{*})=\mathcal{O}(1/\sqrt{n})$.

######  Theorem 2 (Smooth Problems).

Let (A1), (A2) and (A3) hold true with $\alpha=0$. Let
$\mathbf{w}_{-1}=\mathbf{w}_{0}$ and $\\{\mathbf{w}_{t}:t\in[T]\\}$ be
produced by Algorithm 1 with $\eta_{t}=\eta\leq 2/L$. Let
$\bar{\mathbf{w}}_{T}=\sum_{t=1}^{T}\eta_{t}\mathbf{w}_{t-2}/\sum_{t=1}^{T}\eta_{t}$.
Then, there holds

$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})]-F(\mathbf{w}^{*})=\mathcal{O}\Big{(}\frac{T\eta}{n}+\frac{1+T\eta^{2}}{T\eta}\Big{)}.$
(4)

Furthermore, choosing $T\asymp n$ and $\eta\asymp T^{-\frac{1}{2}}$ implies
that
$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})]-F(\mathbf{w}^{*})=\mathcal{O}(1/\sqrt{n})$.

######  Remark 4.

Notice that the gradient complexity (i.e. the number of computing gradients)
of Algorithm 1 is identical to the number of iterations $T.$ The above results
show, to get excess generalization bounds $\mathcal{O}(1/\sqrt{n})$, that
Algorithm 1 requires a gradient complexity $\mathcal{O}(n^{2})$ for nonsmooth
problems, and $\mathcal{O}(n)$ for smooth problems. This matches the existing
generalization analysis for pointwise learning [25, 3, 17]. In Appendix E,
additional results are provided where we propose Algorithm 4 based on the
iterative localization technique [13] in order to reduce the gradient
complexity $\mathcal{O}(n^{2})$ required in Theorem 1 to $\mathcal{O}(n)$ for
nonsmooth problems.

######  Remark 5.

As stated in the introduction, Algorithm 1 can be considered as a specific
case of the classic pairwise learning algorithm [22] with a FIFO buffering set
$B_{t-1}$ of size $s=1$. A key difficulty in the generalization analysis is
that $\mathbf{w}_{t-1}$ depends on $B_{t-1}$, which renders the standard
martingale analysis not applicable. Kar et al. [22] proposed to remove this
coupling effect by considering
$\sup_{\mathbf{w}}\big{[}f(\mathbf{w};B_{t-1})-F_{S}(\mathbf{w})\big{]}$,
which is why they only derived the excess generalization error bound
$\mathcal{O}(1/\sqrt{s})$. We introduce novel techniques to handle the
coupling in both generalization analysis and optimization error analysis. For
the generalization analysis, our strategy is to write the stability as a
deterministic function of several indicator functions on whether we select the
different point in neighboring datasets, and then finally consider the
randomness of these indicator functions. This delay of considering expectation
successfully decouples the coupling between $\mathbf{w}_{t-1}$ and $B_{t-1}$.
For the optimization error analysis, our novelty is to observe that
$f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})=f(\mathbf{w}_{t-2};z_{i_{t}},z_{i_{t-1}})+\mathcal{O}(\eta_{t-1})$,
which removes the decoupling since $\mathbf{w}_{t-2}$ is now independent of
both $i_{t}$ and $i_{t-1}$. Since the additional term
$\mathcal{O}(\eta_{t-1})$ here is a term of smaller magnitude, the coupling
effect is removed without incurring any additional cost.

Finally, we study nonconvex pairwise learning under the PL condition. The
proof is in Section C.

######  Theorem 3.

Let (A1), (A2) and (A4) hold true. Let $\alpha_{0},B>0$. Let
$\mathbf{w}_{-1}\\!=\\!\mathbf{w}_{0}$ and
$\\{\mathbf{w}_{j}\\!:\\!j\in[t]\\}$ be produced by Algorithm 1 with
$\eta_{j}=2/(\mu(j+1))$. If $\mathbb{E}_{i_{j+1},i_{j+2}}\big{[}\|\nabla
f(\mathbf{w}_{j};z_{i_{j+1}},z_{i_{j+2}})\|_{2}^{2}\big{]}\leq\alpha_{0}^{2}$
and $\sup_{z,z^{\prime}}f(\mathbf{w}_{j};z,z^{\prime})\leq B$ for any $j$,
then

$\mathbb{E}\big{[}F(\mathbf{w}_{T})]-F(\mathbf{w}^{*})=\mathcal{O}\Big{(}\frac{T^{\frac{2L}{2L+\mu}}}{n}\Big{)}+\mathcal{O}\big{(}1/(T\mu^{2})\big{)}.$

Furthermore, choosing $T\asymp
n^{\frac{2L+\mu}{4L+\mu}}\mu^{-\frac{4L+2\mu}{4L+\mu}}$ yields that
$\mathbb{E}\big{[}F(\mathbf{w}_{T})]-F(\mathbf{w}^{*})=n^{-\frac{2L+\mu}{4L+\mu}}\mu^{-\frac{4L}{4L+\mu}}$.

######  Remark 6.

As pointed out before, there is no generalization error for the OGD algorithm,
i.e. Algorithm 2 as the i.i.d. data is given in a streaming manner and the
iteration number equals the number of the available data (i.e. $t=n$). In this
setting, the optimization error is identical to the excess generalization
error, which will be estimated in Subsection 4.3.

###  4.2 Stability and Generalization Errors

We study generalization errors by algorithmic stability, which measures the
sensitivity of the output of an algorithm w.r.t. the perturbation of the
dataset. Below we give the definition of uniform argument stability. We say
$S,S^{\prime}$ are neighboring datasets if they differ at most by a single
example.

######  Definition 1.

A (randomized) algorithm $\mathcal{A}$ for pairwise learning is called
$\varepsilon$-uniformly argument stable if for all neighboring datasets
$S,S^{\prime}\in\mathcal{Z}^{n}$ we have
$\mathbb{E}_{\mathcal{A}}[\|\mathcal{A}(S)-\mathcal{A}(S^{\prime})\|_{2}]\leq\varepsilon.$

It is clear $\varepsilon$-uniform argument stability implies
$G\varepsilon$-uniform stability i.e.,
$\sup_{\mathbf{z},\mathbf{z}^{\prime}}\mathbb{E}_{\mathcal{A}}[f(\mathcal{A}(S),\mathbf{z},\mathbf{z}^{\prime})\\!-\\!f(\mathcal{A}(S^{\prime}),\mathbf{z},\mathbf{z}^{\prime})]\leq
G\varepsilon$ for Lipschitz losses [7]. The connection between the uniform
stability for pairwise learning and its generalization has been established in
the literature [1, 34].

######  Lemma 1.

If an algorithm $\mathcal{A}$ for pairwise learning is $\varepsilon$-uniformly
stable for some $\varepsilon>0$, then we have
$|\mathbb{E}_{S,\mathcal{A}}[F_{S}(\mathcal{A}(S))-F(\mathcal{A}(S))]|\leq
2\varepsilon.$

We develop uniform argument stability bound of Algorithm 1 and apply it
together with Lemma 1 to establish the following generalization bounds.
Theorem 4 handles nonsmooth problems, while Theorem 5 handles smooth problems.
The detailed proofs for them can be found in Section A.

######  Theorem 4.

Let $\mathbf{w}_{-1}=\mathbf{w}_{0}$ and $\\{\mathbf{w}_{j}:j\in[t]\\}$ be
produced by Algorithm 1 with $\eta_{j}=\eta$. Let (A1) and (A3) hold with
$\alpha=0$. Then, Algorithm 1 is
$2\sqrt{e}G\eta\big{(}\sqrt{5t}+\frac{2t}{n}\big{)}$-uniformly argument stable
and

$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{t})-F_{S}(\bar{\mathbf{w}}_{t})]\leq
4\sqrt{e}G^{2}\eta\Big{(}\sqrt{5t}+\frac{2t}{n}\Big{)}.$

######  Theorem 5.

Let $\mathbf{w}_{-1}=\mathbf{w}_{0}$ and $\\{\mathbf{w}_{j}:j\in[t]\\}$ be
produced by Algorithm 1 with $\eta_{j}=\eta\leq 2/L$. Let (A1), (A2) and (A3)
hold true with $\alpha=0$. Then, Algorithm 1 is
$\frac{4G}{n}\sum_{j=1}^{t}\eta_{j}$-uniformly argument stable and the
generalization error satisfies
$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{t})-F_{S}(\bar{\mathbf{w}}_{t})]\leq\frac{8G^{2}}{n}\sum_{j=1}^{t}\eta_{j}.$

For Algorithm 2, there is no generalization error as the data
$\\{z_{1},z_{2},\ldots,z_{T}\\}$ is assumed to arrive in a sequential manner
with $T$ increasing all the time which does not involve the training data.

###  4.3 Optimization Error

In this subsection, we establish the convergence rate, i.e., optimization
error, of Algorithm 1 for convex, nonconvex and strongly convex problems. We
consider both bounds in expectation and with high probability. Our analysis is
based on the key observation
$f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})=f(\mathbf{w}_{t-2};z_{i_{t}},z_{i_{t-1}})+\mathcal{O}(\eta_{t-1})$.
The proofs of results in this subsection are given in Section B.

Below we only present optimization error bounds for Algorithm 1 here in the
offline (finite-sum) setting where the training data of size $n$, denoted by
$S=\\{z_{1},\ldots,z_{n}\\}$, is fixed, and the optimization error is measured
by
$F_{S}(\bar{\mathbf{w}}_{t})-\inf_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w}).$
We emphasize that all our optimization error bounds hold true for Algorithm 2
in the online learning setting with exactly the same analysis where the
streaming data $\\{z_{1},\ldots,z_{t},...\\}$ is assumed to be i.i.d according
to the population distribution $\rho$, and the bounds for the optimization
error in this case is given for the excess generalization error (excess
population risk), i.e.
$F(\widetilde{\mathbf{w}}_{t})-\inf_{\mathbf{w}\in\mathcal{W}}F(\mathbf{w}).$

######  Theorem 6.

Let $\mathbf{w}_{-1}=\mathbf{w}_{0}$ and $\\{\mathbf{w}_{j}:j\in[t]\\}$ be
produced by Algorithm 1. Let (A1) and (A3) hold true with $\alpha\geq 0$.
Then, for any $\mathbf{w}$ independent of $\mathcal{A}$ we have the following
convergence rates:

  1. (a)

Assume $f$ is convex, i.e. $\alpha=0.$ Then, we have

$\mathbb{E}_{\mathcal{A}}[F_{S}(\bar{\mathbf{w}}_{t})]-F_{S}(\mathbf{w})\leq\frac{\|\mathbf{w}_{0}-\mathbf{w}\|_{2}^{2}+G^{2}\sum_{j=1}^{t}(2\eta_{j}\eta_{j-1}+\eta_{j}^{2})}{2\sum_{j=1}^{t}\eta_{j}}.$
(5)

  2. (b)

Let $f$ be $\alpha$-strongly convex with $\alpha>0$ and
$\eta_{j}=\frac{2}{\alpha(j+1)}$. Then, there holds
$\mathbb{E}_{\mathcal{A}}[F_{S}(\bar{\mathbf{w}}_{t})]-F_{S}(\mathbf{w})=\mathcal{O}\bigl{(}{G^{2}/(\alpha
t)}\bigr{)}.$

######  Remark 7.

The above convergence rates match those in the pointwise learning [5].
Furthermore, if $\eta_{j}=\eta$, then Eq. (5) becomes
$\mathbb{E}_{\mathcal{A}}[F_{S}(\bar{\mathbf{w}}_{t})]-F_{S}(\mathbf{w})=\mathcal{O}(1/(t\eta)+\eta)$
and one can choose $\eta\asymp 1/\sqrt{t}$ to get
$\mathbb{E}_{\mathcal{A}}[F_{S}(\bar{\mathbf{w}}_{t})]-F_{S}(\mathbf{w})=\mathcal{O}(1/\sqrt{t})$.
We can extend our convergence analysis to a more general update as
$\mathbf{w}_{t}=\Pi_{\mathcal{W}}\big{(}\mathbf{w}_{t-1}-\frac{\eta_{t}}{s}\sum_{j=1}^{s}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-j}})\big{)}$ for $s\in\mathbb{N}$.
Indeed, one can use the observation
$f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-s}})=f(\mathbf{w}_{t-s-1};z_{i_{t}},z_{i_{t-s}})+\mathcal{O}\big{(}\sum_{j=1}^{s}\eta_{t-j}\big{)}$
to derive the convergence rate $\mathcal{O}(\sqrt{s}/\sqrt{t})$.

Below we present high-probability bounds to understand the variation of the
algorithm. We need to take conditional expectation of
$f(\mathbf{w}_{2j-2};z_{i_{2j}},z_{i_{2j-1}})$ w.r.t. $(i_{2j},i_{2j-1})$ to
get $F_{S}(\mathbf{w}_{2j-2})$. However, there is a coupling between
$(i_{2j},i_{2j-1})$ and $(i_{2j-1},i_{2j-2})$. Therefore, one can not directly
apply concentration inequalities for martingales to handle
$\sum_{j=1}^{t}\big{(}f(\mathbf{w}_{2j-2};z_{i_{2j}},z_{i_{2j-1}})-F_{S}(\mathbf{w}_{2j-2})\big{)}$.
We introduce a novel decoupling technique to handle this coupling. Note that
the high-probability bounds match the bounds in expectation up to a constant
factor.

######  Theorem 7.

Let $\mathbf{w}_{-1}=\mathbf{w}_{0}$ and $\\{\mathbf{w}_{j}:j\in[t]\\}$ be
produced by Algorithm 1. Let (A1) and (A3) hold true with $\alpha\geq 0$ and
$\sup_{\mathbf{w}}f(\mathbf{w};z,z^{\prime})\leq B$ for some $B>0$. Let
$\delta\in(0,1)$.

  1. (a)

Assume $f$ is convex, i.e. $\alpha=0$ and let
$\bar{\mathbf{w}}_{t}=\sum_{j=1}^{t}\eta_{j}\mathbf{w}_{j-2}/\sum_{j=1}^{t}\eta_{j}$.
Then, for any $\mathbf{w}\in\mathcal{W}$, with probability at least $1-\delta$
the following inequality holds

$\\!\\!\\!F_{S}(\bar{\mathbf{w}}_{t})-F_{S}(\mathbf{w})\\!\leq\\!\frac{1}{\sum_{j=1}^{t}\eta_{j}}\Big{(}\\!2B\Big{(}2\sum_{j=1}^{t}\eta_{j}^{2}\log(2/\delta)\Big{)}^{\frac{1}{2}}+\frac{1}{2}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}+G^{2}\sum_{j=1}^{t}\big{(}\eta_{j-1}\eta_{j}+\frac{\eta^{2}_{j}}{{2}}\big{)}\\!\Big{)}.$

  2. (b)

Assume $f$ is $\alpha$-strongly convex with $\alpha>0$ and
$\eta_{j}=\frac{2}{\alpha(j+1)}$. Let
$\bar{\mathbf{w}}_{t}=\sum_{j=1}^{t}j\mathbf{w}_{j-2}/\sum_{j=1}^{t}j$. Then,
with probability at least $1-\delta$, we have
$F_{S}(\bar{\mathbf{w}}_{t})-F_{S}(\mathbf{w})=\mathcal{O}\bigl{(}{G^{2}\log(1/\delta)/(\alpha
t)}\bigr{)}.$

Finally, we study the convergence of Algorithm 1 associated with nonconvex
functions. We first consider general smooth problems. Since we cannot find a
global minimum in this setting, we measure the convergence rate in terms of
gradient norms [16]. The following theorem establishes the convergence rate
$\mathcal{O}(1/\sqrt{t})$ for
$\min_{j=1,\ldots,t}\mathbb{E}_{\mathcal{A}}[\|\nabla
F_{S}(\mathbf{w}_{j})\|_{2}^{2}]$.

######  Theorem 8.

Let $\mathbf{w}_{-1}\\!=\\!\mathbf{w}_{0}$ and
$\\{\mathbf{w}_{j}\\!:\\!j\in[t]\\}$ be produced by Algorithm 1 with
$\eta_{j}\\!=\\!\eta\leq 1/(2\sqrt{L})$. Let (A2) hold true and
$\mathbb{E}_{i_{j+1},i_{j+2}}\big{[}\|\nabla
f(\mathbf{w}_{j};z_{i_{j+1}},z_{i_{j+2}})\|_{2}^{2}\big{]}\leq\alpha_{0}^{2}$
for some $\alpha_{0}$ and any $j$. Then,

$\frac{1}{t}\sum_{j=1}^{t}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})\big{\|}_{2}^{2}\big{]}\leq\frac{F_{S}(\mathbf{w}_{0})}{t\eta}+8L\eta\alpha_{0}^{2}.$

Furthermore, choosing $\eta\asymp 1/\sqrt{t}$ implies that
$\frac{1}{t}\sum_{j=1}^{t}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})\big{\|}_{2}^{2}\big{]}=\mathcal{O}(1/\sqrt{t})$.

We now turn to nonconvex problems under a PL condition. Theorem 9 gives
convergence rates of the order $\mathcal{O}(1/t)$, which match the existing
results for standard SGD in pointwise learning [23].

######  Theorem 9.

Assume (A2) and (A4) hold true and
$\mathbb{E}_{i_{j+1},i_{j+2}}\big{[}\|\nabla
f(\mathbf{w}_{j};z_{i_{j+1}},z_{i_{j+2}})\|_{2}^{2}\big{]}\leq\alpha_{0}^{2}$
for some $\alpha_{0}$ and any $j$. Let $\mathbf{w}_{-1}\\!=\\!\mathbf{w}_{0}$
and $\\{\mathbf{w}_{j}\\!:\\!j\in[t]\\}$ be produced by Algorithm 1 with
$\eta_{j}=2/(\mu(j+1))$. Then

$\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}_{S})]\leq\frac{32L\alpha_{0}^{2}}{\mu^{2}}\Big{(}\frac{1}{t+1}+\frac{\log(et)}{\mu
t(t+1)}\Big{)}.$

##  5 Application: Differentially Private SGD for Pairwise Learning

We now use Algorithm 1 and our stability analysis (i.e. Theorem 5) to develop
a differentially private algorithm for pairwise learning. Let us start with
the definition of differential privacy [12].

######  Definition 2.

A (randomized) algorithm $\mathcal{A}$ is called
$(\epsilon,\delta)$-differentially private (DP) if, for all neighboring
datasets $S,S^{\prime}$ and for all events $O$ in the output space of
$\mathcal{A}$, one has $\mathbb{P}[\mathcal{A}(S)\in O]\leq
e^{\epsilon}\mathbb{P}[\mathcal{A}(S^{\prime})\in O]+\delta.$

Algorithm 3 Differentially Private Localized SGD for Pairwise Learning

1: Inputs: Dataset $S=\\{\mathbf{z}_{i}:i\in[n]\\}$, parameters
$\epsilon,\delta>0$, and learning rate $\eta$, initial point $\mathbf{w}_{0}$

2: Set $K\\!=\\!\lceil\log_{2}n\rceil$ and divide $S$ into $K$ disjoint
subsets $\\{S_{1},\cdots,S_{K}\\}$ where $|S_{k}|\\!=\\!n_{k}\\!=\\!2^{-k}n$.

3: for $k=1$ to $K$ do

4: Set $\eta_{k}=4^{-k}\eta$

5: Compute $\bar{\mathbf{w}}_{k}$ by Algorithm 1 based on $S_{k}$ and
initiated at $\mathbf{w}_{k-1}$ for $\lceil n_{k}\log(4/\delta)\rceil$ steps.

6: Set $\mathbf{w}_{k}=\bar{\mathbf{w}}_{k}+\mathbf{u}_{k}$ where
$\mathbf{u}_{k}\sim\mathcal{N}(0,\sigma_{k}^{2}I_{d})$ with
$\sigma_{k}=12G\eta_{k}\log(4/\delta)\sqrt{2\log(2.5/\delta)}/\epsilon$.

7: Outputs: $\mathbf{w}_{K}$

Our proposed DP algorithm for pairwise learning is described in Algorithm 3
which is inspired by the iterative localization technique [13] for pointwise
learning. The privacy and utility guarantees are given by the following
theorem. Here $D$ denotes the diameter of $\mathcal{W}$.

######  Theorem 10.

Let (A1), (A2), and (A3) hold true with $\sigma=0$. Let
$\\{\mathbf{w}_{k}:k\in[K]\\}$ be produced by Algorithm 3 with
$\eta=\frac{D}{G}\min\\{\frac{\log(4/\delta)}{\sqrt{n}},\frac{\epsilon}{12\log(4/\delta)\sqrt{2d\log(2.5/\delta)}}\\}\leq\frac{2}{L}$.
Then, Algorithm 3 satisfies $(\epsilon,\delta)$-DP and, with gradient
complexity $\mathcal{O}(n\log(1/\delta)),$ we have the utility bound that

$\mathbb{E}[F(\mathbf{w}_{K})-F(\mathbf{w}^{*})]=\mathcal{O}\Big{(}GD\Big{(}\frac{1}{\sqrt{n}}+\frac{\sqrt{d}\log^{\frac{3}{2}}(1/\delta)}{\epsilon
n}\Big{)}\Big{)}.$

The main difference from the pointwise setting in [13] is that Algorithm 3
involves the coupling dependency between $\\{i_{t},i_{t-1}\\}$ at time $t$ in
Algorithm 1 and $\\{i_{t-1},i_{t-2}\\}$ at time $t-1$, which renders the
direct application of the standard concentration inequalities infeasible. We
propose a novel decomposition to circumvent this hurdle (see more detailed
proof for Theorem 10 in Appendix D).

######  Remark 8.

The above bound matches the lower bound given in [2] for
$(\epsilon,\delta)$-differentially private pointwise learning up to a
$\log(1/\delta)$ term. Our utility bound improves over the previous work [21]
which has the bound
$\mathcal{O}(\sqrt{d\log(1/\delta)}\log(n/\delta)/(\sqrt{n}\epsilon))$. During
the preparation of this work, we notice a very recent paper [42] also studied
the private version of pairwise algorithm by using the localization technique.
Their algorithm establishes the optimal rate
$\mathcal{O}\big{(}1/\sqrt{n}+\sqrt{d\log(1/\delta)}/(\epsilon n)\big{)}$
which, however, needs an expensive gradient complexity
$\mathcal{O}(n^{3}\log(1/\delta))$. As a comparison, we achieve nearly optimal
utility bound with linear gradient complexity $\mathcal{O}(n\log(1/\delta))$.

######  Remark 9.

In Appendix F, we further remove the smoothness assumption (A2) required in
Theorem 10 and propose a private algorithm (stated as Algorithm 5 there) that
achieves the optimal rate
$\mathcal{O}\big{(}\big{(}1/\sqrt{n}+\sqrt{d\log(1/\delta)}/(\epsilon
n)\big{)}\big{)}$ with gradient complexity $\mathcal{O}(n^{2}\log(1/\delta))$.
Such bound improves over the previous known results with nonsmooth losses [43]
where the utility bound was
$\mathcal{O}(\sqrt{d\log(1/\delta)}\log(n/\delta)/(\sqrt{n}\epsilon))$.

##  6 Experimental Validation

We now report some preliminary experiments222The source codes are available at
https://github.com/zhenhuan-yang/simple-pairwise. on AUC maximization with
$f(\mathbf{w};(\mathbf{x},y),(\mathbf{x}^{\prime},y^{\prime}))=\ell(\mathbf{w}^{\top}(\mathbf{x}-\mathbf{x}^{\prime}))\mathbb{I}_{[y=1\wedge
y^{\prime}=-1]}$ where $\ell$ is a surrogate loss function, e.g., the hinge
loss $\ell(t)=(1-t)_{+}.$

The purpose of our first experiment is to compare our algorithm, i.e.
Algorithm 1, against four existing algorithms for pairwise learning in terms
of generalization and CPU running time on several datasets available from the
LIBSVM website [9]. These algorithms are: 1) OLP [22] uses a buffer $B_{t}$
updated by a variant of Reservoir sampling with replacement where the buffer
size is chosen to be $200$ in order to guarantee the maximum AUC score as
indicated in [22]; 2) $\texttt{OAM}_{gra}$ [48] is tailored for AUC
maximization with the hinge loss which uses buffers by Reservoir sampling. The
buffer size is set to be $100$ for both positive and negative buffers as
suggested in that paper; 3) $\texttt{SGD}_{pair}$ [27] randomly pick a pair
from $\binom{n}{2}$ pairs by uniform distribution; 4) SPAUC [26], where AUC
maximization problem with the least square loss was reformulated as stochastic
saddle point (min-max) problem. Note that SPAUC and $\texttt{OAM}_{gra}$ can
only apply to AUC maximization problem with the least square loss and hinge
loss, respectively.

To validate the generalization ability, the surrogate loss for Algorithm 1,
$\texttt{SGD}_{pair}$ and OLP is chosen to be the hinge loss. Average AUC
scores of different algorithms are listed in Table 1 where we can see that our
algorithm yields competitive generalization performance with OAM and OLP using
a large buffering set. Detailed experimental setup, data statistics and more
results such as comparison with OLP and OAM with the size of the buffering set
$s=1$ are listed in Appendix G.

Table 1: Average AUC score $\pm$ standard deviation across multiple datasets. Our best results are highlighted in bold. Algorithm | diabetes | german | ijcnn1 | letter | mnist | usps
---|---|---|---|---|---|---
Ours | $.831\pm.030$ | $.793\pm.021$ | $.934\pm.002$ | $.810\pm.007$ | $.932\pm.001$ | $.926\pm.006$
$\texttt{SGD}_{pair}$ [27] | $.830\pm.028$ | $.794\pm.023$ | $.934\pm.003$ | $.811\pm.008$ | $.932\pm.001$ | $.925\pm.006$
OLP [22] | $.825\pm.028$ | $.787\pm.028$ | $.916\pm.003$ | $.808\pm.010$ | $.927\pm.003$ | $.917\pm.006$
$\texttt{OAM}_{gra}$ [48] | $.828\pm.026$ | $.785\pm.029$ | $.930\pm.003$ | $.806\pm.008$ | $.898\pm.002$ | $.916\pm.005$
SPAUC [26] | $.828\pm.031$ | $.799\pm.026$ | $.932\pm.002$ | $.809\pm.008$ | $.927\pm.002$ | $.923\pm.005$

Figure 1: CPU running time ($\log$ scale) versus the AUC score

To fairly compare the CPU running time, we apply the following uniform setting
across all algorithms: 1) $\mathcal{W}$ is an $\ell_{2}$ ball with the same
diameter; 2) the step sizes $\eta_{t}=\eta$ which is tuned by cross
validation. We report the results in Figure 1 for the hinge loss. We can see
that CPU running time for our algorithm and $\texttt{SGD}_{pair}$ are similar
while OLP and OAM needs more time to converge. The possible reason behind this
is that they have a high gradient complexity $\mathcal{O}(s)$ at each
iteration while ours is $\mathcal{O}(1).$ More results on comparison for the
least square loss and for differentially private algorithms are given in
Appendix G.

##  7 Conclusion

In this paper, we propose simple stochastic and online gradient descent
algorithms for pairwise learning. The key idea is to build a gradient
estimator by pairing the current instance with the previous instance, which
enjoys favorable computation and storage complexity. We leverage the lens of
algorithmic stability to study its generalization and apply tools in
optimization theory to study its convergence rates for various problems
including convex/nonconvex and smooth/nonsmooth settings. We also use our
algorithms and stability analysis to develop a new DP algorithm for pairwise
learning with differential privacy constraints which significantly improves
the existing results. The main difference from pointwise learning in the
analysis is the coupling between models and previous instances, which is
handled by introducing novel decoupling techniques.

For future work, it would be interesting to see whether the analysis and
results still hold true if the current example $\mathbf{z}_{i_{t}}$ in
Algorithm 1 is paired with one arbitrary previous example (e.g.,
$\mathbf{z}_{i_{1}}$ ). Other future work would be a systematic extension of
our algorithms using other acceleration schemes such as momentum and variance
reduction techniques.

## Acknowledgments

The authors are grateful to the anonymous reviewers for their constructive
comments and suggestions. Tianbao Yang is partially supported by NSF Career
Award #1844403 and NSF Award #2110545. Yiming Ying is supported by NSF under
grants DMS-2110836, IIS-1816227, IIS-2110546, and IIS-2103450.

## References

  * Agarwal and Niyogi [2009] S. Agarwal and P. Niyogi.  Generalization bounds for ranking algorithms via algorithmic stability.  _Journal of Machine Learning Research_ , 10(Feb):441–474, 2009.
  * Bassily et al. [2014] R. Bassily, A. Smith, and A. Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , pages 464–473. IEEE, 2014.
  * Bassily et al. [2020] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar.  Stability of stochastic gradient descent on nonsmooth convex losses.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Bellet et al. [2013] A. Bellet, A. Habrard, and M. Sebban.  A survey on metric learning for feature vectors and structured data.  _arXiv preprint arXiv:1306.6709_ , 2013.
  * Bottou et al. [2018] L. Bottou, F. E. Curtis, and J. Nocedal.  Optimization methods for large-scale machine learning.  _SIAM Review_ , 60(2):223–311, 2018.
  * Boucheron et al. [2013] S. Boucheron, G. Lugosi, and P. Massart.  _Concentration Inequalities: A Nonasymptotic Theory of Independence_.  Oxford university press, 2013.
  * Bousquet and Elisseeff [2002] O. Bousquet and A. Elisseeff.  Stability and generalization.  _Journal of machine learning research_ , 2(Mar):499–526, 2002.
  * Cesa-Bianchi et al. [2004] N. Cesa-Bianchi, A. Conconi, and C. Gentile.  On the generalization ability of on-line learning algorithms.  _IEEE Transactions on Information Theory_ , 50(9):2050–2057, 2004.
  * Chang and Lin [2011] C.-C. Chang and C.-J. Lin.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2:27:1–27:27, 2011.  Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  * Chen et al. [2020] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pages 1597–1607. PMLR, 2020.
  * Clémençon et al. [2008] S. Clémençon, G. Lugosi, and N. Vayatis.  Ranking and empirical minimization of U-statistics.  _The Annals of Statistics_ , pages 844–874, 2008.
  * Dwork et al. [2014] C. Dwork, A. Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Feldman et al. [2020] V. Feldman, T. Koren, and K. Talwar.  Private stochastic convex optimization: optimal rates in linear time.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 439–449, 2020.
  * Foster et al. [2018] D. J. Foster, A. Sekhari, and K. Sridharan.  Uniform convergence of gradients for non-convex learning and optimization.  In _Advances in Neural Information Processing Systems_ , pages 8759–8770, 2018.
  * Gao et al. [2013] W. Gao, R. Jin, S. Zhu, and Z.-H. Zhou.  One-pass auc optimization.  In _International Conference on Machine Learning_ , pages 906–914, 2013.
  * Ghadimi and Lan [2013] S. Ghadimi and G. Lan.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  _SIAM Journal on Optimization_ , 23(4):2341–2368, 2013.
  * Hardt et al. [2016] M. Hardt, B. Recht, and Y. Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 1225–1234, 2016.
  * Hazan [2016] E. Hazan.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Hu et al. [2013] T. Hu, J. Fan, Q. Wu, and D.-X. Zhou.  Learning theory approach to minimum error entropy criterion.  _Journal of Machine Learning Research_ , 14(2), 2013.
  * Hu et al. [2015] T. Hu, J. Fan, Q. Wu, and D.-X. Zhou.  Regularization schemes for minimum error entropy principle.  _Analysis and Applications_ , 13(04):437–455, 2015.
  * Huai et al. [2020] M. Huai, D. Wang, C. Miao, J. Xu, and A. Zhang.  Pairwise learning with differential privacy guarantees.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 694–701, 2020.
  * Kar et al. [2013] P. Kar, B. Sriperumbudur, P. Jain, and H. Karnick.  On the generalization ability of online learning algorithms for pairwise loss functions.  In _International Conference on Machine Learning_ , pages 441–449, 2013.
  * Karimi et al. [2016] H. Karimi, J. Nutini, and M. Schmidt.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In _European Conference on Machine Learning_ , pages 795–811, 2016\.
  * Kulis et al. [2013] B. Kulis et al.  Metric learning: A survey.  _Foundations and Trends® in Machine Learning_ , 5(4):287–364, 2013.
  * Lei and Ying [2020] Y. Lei and Y. Ying.  Fine-grained analysis of stability and generalization for stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 5809–5819, 2020.
  * Lei and Ying [2021] Y. Lei and Y. Ying.  Stochastic proximal auc maximization.  _Journal of Machine Learning Research_ , 22(61):1–45, 2021.
  * Lei et al. [2020] Y. Lei, A. Ledent, and M. Kloft.  Sharper generalization bounds for pairwise learning.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 21236–21246, 2020.
  * Liu et al. [2018] M. Liu, X. Zhang, Z. Chen, X. Wang, and T. Yang.  Fast stochastic auc maximization with o (1/n)-convergence rate.  In _International Conference on Machine Learning_ , pages 3195–3203, 2018.
  * Liu et al. [2020] M. Liu, Z. Yuan, Y. Ying, and T. Yang.  Stochastic auc maximization with deep neural networks.  In _International Conference on Learning Representations_ , 2020.
  * Oord et al. [2018] A. v. d. Oord, Y. Li, and O. Vinyals.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Orabona [2019] F. Orabona.  A modern introduction to online learning.  _arXiv preprint arXiv:1912.13213_ , 2019.
  * Shalev-Shwartz [2012] S. Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends® in Machine Learning_ , 4(2):107–194, 2012.
  * Shalev-Shwartz et al. [2009] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan.  Stochastic convex optimization.  In _COLT_ , 2009.
  * Shen et al. [2020] W. Shen, Z. Yang, Y. Ying, and X. Yuan.  Stability and optimization error of stochastic gradient descent for pairwise learning.  _Analysis and Applications_ , 18(05):887–927, 2020.
  * Sohn [2016] K. Sohn.  Improved deep metric learning with multi-class n-pair loss objective.  In _Advances in neural information processing systems_ , pages 1857–1865, 2016.
  * Sun et al. [2018] T. Sun, Y. Sun, and W. Yin.  On markov chain gradient descent.  _Advances in neural information processing systems_ , 2018.
  * Wang et al. [2012] Y. Wang, R. Khardon, D. Pechyony, and R. Jones.  Generalization bounds for online learning algorithms with pairwise loss functions.  In _Conference on Learning Theory_ , volume 23, pages 13–1, 2012\.
  * Wang et al. [2013] Y. Wang, R. Khardon, D. Pechyony, and R. Jones.  Online learning with pairwise loss functions.  _arXiv preprint arXiv:1301.5332_ , 2013.
  * Weinberger and Saul [2009] K. Q. Weinberger and L. K. Saul.  Distance metric learning for large margin nearest neighbor classification.  _Journal of Machine Learning Research_ , 10:207–244, 2009\.
  * Wu et al. [2018] Z. Wu, Y. Xiong, S. X. Yu, and D. Lin.  Unsupervised feature learning via non-parametric instance discrimination.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3733–3742, 2018.
  * Xing et al. [2003] E. P. Xing, M. I. Jordan, S. J. Russell, and A. Y. Ng.  Distance metric learning with application to clustering with side-information.  In _Advances in Neural Information Processing Systems_ , 2003.
  * Xue et al. [2021] Z. Xue, S. Yang, M. Huai, and D. Wang.  Differentially private pairwise learning revisited, 2021.  URL https://shao3wangdi.github.io/papers/IJCAI2021_pairwise.pdf.
  * Yang et al. [2021] Z. Yang, Y. Lei, S. Lyu, and Y. Ying.  Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2026–2034. PMLR, 2021.
  * Ying and Li [2012] Y. Ying and P. Li.  Distance metric learning with eigenvalue optimization.  _Journal of Machine Learning Research_ , 13:1–26, 2012\.
  * Ying and Zhou [2006] Y. Ying and D.-X. Zhou.  Online regularized classification algorithms.  _IEEE Transactions on Information Theory_ , 52(11):4775–4788, 2006.
  * Ying et al. [2016] Y. Ying, L. Wen, and S. Lyu.  Stochastic online AUC maximization.  In _Advances in Neural Information Processing Systems_ , pages 451–459, 2016.
  * Zhang [2005] T. Zhang.  Data dependent concentration bounds for sequential prediction algorithms.  In _Conference on Learning Theory_ , pages 173–187, 2005.
  * Zhao et al. [2011] P. Zhao, S. C. Hoi, R. Jin, and T. Yang.  Online AUC maximization.  In _International Conference on Machine Learning_ , pages 233–240, 2011.

##  Appendix A Proofs of Generalization Error (Theorems 4 and 5)

In this section, we present the stability and generalization error bounds for
SGD with convex loss functions. We first prove Theorem 4 on smooth problems
and then Theorem 5 on nonsmooth problems. Recall $\mathbb{E}_{\mathcal{A}}$
denotes the expectation w.r.t. the internal randomness of $\mathcal{A}$. For
SGD, this means the expectation w.r.t. $\\{i_{j}\\}_{j\in[t]}$.

###### Proof of Theorem 4.

We first investigate the uniform stability of Algorithm 1. Let
$S^{\prime}=\\{z_{1},\ldots,z_{n-1},z_{n}^{\prime}\\}$, where $z_{n}^{\prime}$
is independently drawn from $\rho$, and $\\{\mathbf{w}_{t}^{\prime}\\}$ be
produced by Algorithm 1 w.r.t. data $S^{\prime}$. We consider two cases: i.e.
the case of $\\{i_{t}\neq n\text{ and }i_{t-1}\neq n\\}$ and the case of
$\\{i_{t}=n\text{ or }i_{t-1}=n\\}.$

If $i_{t}\neq n$ and $i_{t-1}\neq n$, then

$\displaystyle\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}^{2}$
$\displaystyle\leq\big{\|}\mathbf{w}_{t-1}-\eta_{t}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\mathbf{w}^{\prime}_{t-1}+\eta_{t}\nabla
f(\mathbf{w}^{\prime}_{t-1};z^{\prime}_{i_{t}},z^{\prime}_{i_{t-1}})\big{\|}_{2}^{2}$
$\displaystyle=\big{\|}\mathbf{w}_{t-1}-\eta_{t}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\mathbf{w}^{\prime}_{t-1}+\eta_{t}\nabla
f(\mathbf{w}^{\prime}_{t-1};z_{i_{t}},z_{i_{t-1}})\big{\|}_{2}^{2}$
$\displaystyle=\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+\eta_{t}^{2}\big{\|}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\nabla
f(\mathbf{w}^{\prime}_{t-1};z_{i_{t}},z_{i_{t-1}})\big{\|}_{2}^{2}$
$\displaystyle-2\eta_{t}\langle\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime},\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\nabla
f(\mathbf{w}^{\prime}_{t-1};z_{i_{t}},z_{i_{t-1}})\rangle$
$\displaystyle\leq\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+\eta_{t}^{2}\big{\|}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\nabla
f(\mathbf{w}^{\prime}_{t-1};z_{i_{t}},z_{i_{t-1}})\big{\|}_{2}^{2}$
$\displaystyle\leq\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+4\eta_{t}^{2}G^{2},$

where the last second inequality follows from the inequality
$\langle\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime},\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\nabla
f(\mathbf{w}^{\prime}_{t-1};z_{i_{t}},z_{i_{t-1}})\rangle\geq 0$ due to the
convexity of $f$ and the last inequality follows from the Lipschitz continuity
of $f$. If $i_{t}=n$ or $i_{t-1}=n$, it follows from the elementary inequality
$(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$ and the Lipschitz condition that

$\displaystyle\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}^{2}$
$\displaystyle\leq(1+p)\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}$
$\displaystyle+(1+1/p)\eta_{t}^{2}\big{\|}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\nabla
f(\mathbf{w}^{\prime}_{t-1};z^{\prime}_{i_{t}},z^{\prime}_{i_{t-1}})\big{\|}_{2}^{2}$
$\displaystyle\leq(1+p)\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+4(1+1/p)\eta_{t}^{2}G^{2}.$

We can combine the above two cases together and derive

$\displaystyle\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}^{2}$
$\displaystyle\leq\big{(}\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+4\eta_{t}^{2}G^{2}\big{)}\mathbb{I}_{[i_{t}\neq
n\text{ and }i_{t-1}=n]}$
$\displaystyle+\big{(}(1+p)\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+4(1+1/p)\eta_{t}^{2}G^{2}\big{)}\mathbb{I}_{[i_{t}=n\text{
or }i_{t-1}=n]}$ $\displaystyle\leq\big{(}1+p\mathbb{I}_{[i_{t}=n\text{ or
}i_{t-1}=n]}\big{)}\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+4\eta_{t}^{2}G^{2}\big{(}1+\mathbb{I}_{[i_{t}=n\text{
or }i_{t-1}=n]}/p\big{)}$
$\displaystyle=\big{(}1+p\big{)}^{\mathbb{I}_{[i_{t}=n\text{ or
}i_{t-1}=n]}}\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}^{2}+4\eta_{t}^{2}G^{2}\big{(}1+\mathbb{I}_{[i_{t}=n\text{
or }i_{t-1}=n]}/p\big{)},$

where $\mathbb{I}_{[\cdot]}$ is the indicator function. We can apply the above
inequality recursively and get

$\displaystyle\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}^{2}$
$\displaystyle\leq
4G^{2}\sum_{k=1}^{t}\eta_{k}^{2}\big{(}1+\mathbb{I}_{[i_{k}=n\text{ or
}i_{k-1}=n]}/p\big{)}\prod_{j=k+1}^{t}\big{(}1+p\big{)}^{\mathbb{I}_{[i_{j}=n\text{
or }i_{j-1}=n]}}$ $\displaystyle\leq
4G^{2}\prod_{j=1}^{t}\big{(}1+p\big{)}^{\mathbb{I}_{[i_{j}=n\text{ or
}i_{j-1}=n]}}\sum_{k=1}^{t}\eta_{k}^{2}\big{(}1+\mathbb{I}_{[i_{k}=n\text{ or
}i_{k-1}=n]}/p\big{)}$
$\displaystyle=4G^{2}\eta^{2}\big{(}1+p\big{)}^{\sum_{j=1}^{t}\mathbb{I}_{[i_{j}=n\text{
or }i_{j-1}=n]}}\big{(}t+\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n\text{ or
}i_{k-1}=n]}/p\big{)},$

where the last inequality follows from $\eta_{j}=\eta$.

Now, we choose $p=1/\big{(}\sum_{j=1}^{t}\mathbb{I}_{[i_{j}=n\text{ or
}i_{j-1}=n]}\big{)}$ and use the inequality $(1+x)^{1/x}\leq e$ to derive the
following inequality

$\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}^{2}\leq
4eG^{2}\eta^{2}\Big{(}t+\big{(}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n\text{ or
}i_{k-1}=n]}\big{)}^{2}\Big{)}.$

By the inequality $\mathbb{I}_{[i_{k}=n\text{ or
}i_{k-1}=n]}\leq\mathbb{I}_{[i_{k}=n]}+\mathbb{I}_{[i_{k-1}=n]}$ and
$(a+b)^{2}\leq 2(a^{2}+b^{2})$ we know

$\displaystyle\mathbb{E}_{\mathcal{A}}\Big{[}\big{(}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n\text{
or }i_{k-1}=n]}\big{)}^{2}\Big{]}$ $\displaystyle\leq
2\mathbb{E}_{\mathcal{A}}\Big{[}\big{(}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n}\big{)}^{2}\Big{]}+2\mathbb{E}_{\mathcal{A}}\Big{[}\big{(}\sum_{k=1}^{t}\mathbb{I}_{[i_{k-1}=n}\big{)}^{2}\Big{]}$
$\displaystyle=4\mathbb{E}\Big{[}\big{(}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n]}\big{)}^{2}\Big{]}\leq
4t+4\sum_{j,k\in[t]:j\neq
k}\mathbb{E}\big{[}\mathbb{I}_{[i_{j}=n]}\mathbb{I}_{[i_{k}=n]}\big{]}$
$\displaystyle=4t+4\sum_{j,k\in[t]:j\neq k}\frac{1}{n^{2}}\leq
4t+4t^{2}/n^{2}.$

We can combine the above two inequalities together and derive

$\mathbb{E}_{\mathcal{A}}[\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}^{2}]\leq
4eG^{2}\eta^{2}\Big{(}5t+\frac{4t^{2}}{n^{2}}\Big{)}$

and by the convexity of $\|\cdot\|_{2}^{2}$ it follows

$\mathbb{E}_{\mathcal{A}}[\|\bar{\mathbf{w}}_{t}-\bar{\mathbf{w}}_{t}^{\prime}\|_{2}^{2}]\leq\frac{1}{t}\sum_{j=1}^{t}\mathbb{E}_{\mathcal{A}}[\|\mathbf{w}_{j}-\mathbf{w}_{j}^{\prime}\|_{2}^{2}]\leq
4eG^{2}\eta^{2}\Big{(}5t+\frac{4t^{2}}{n^{2}}\Big{)}.$

This establishes the uniform stability of Algorithm 1. Furthermore, for any
$\mathbf{z},\mathbf{z}^{\prime}$, we have

$\displaystyle\mathbb{E}_{\mathcal{A}}[f(\bar{\mathbf{w}}_{t},\mathbf{z},\mathbf{z}^{\prime})-f(\bar{\mathbf{w}}_{t}^{\prime},\mathbf{z},\mathbf{z}^{\prime})]\leq$
$\displaystyle
G\mathbb{E}_{\mathcal{A}}[\|\bar{\mathbf{w}}_{t}-\bar{\mathbf{w}}_{t}^{\prime}\|_{2}]=G\mathbb{E}_{\mathcal{A}}\Big{[}\sqrt{\|\bar{\mathbf{w}}_{t}-\bar{\mathbf{w}}_{t}^{\prime}\|_{2}^{2}}\Big{]}$
$\displaystyle\leq$ $\displaystyle
G\sqrt{\mathbb{E}_{\mathcal{A}}[\|\bar{\mathbf{w}}_{t}-\bar{\mathbf{w}}_{t}^{\prime}\|_{2}^{2}]}\leq
2\sqrt{e}G^{2}\eta\Big{(}\sqrt{5t}+\frac{2t}{n}\Big{)}$

where the first inequality we used the $G$-Lipschitz continuity of $f$ and the
second inequality we used the Jensen’s inequality. Therefore, Algorithm 1 is
$2\sqrt{e}G^{2}\eta\Big{(}\sqrt{5t}+\frac{2t}{n}\Big{)}$-uniformly stable. By
Lemma 1 it follows

$\mathbb{E}_{\mathcal{A}}[F(\bar{\mathbf{w}}_{t})-F_{S}(\bar{\mathbf{w}}_{t})]\leq
4\sqrt{e}G^{2}\eta\Big{(}\sqrt{5t}+\frac{2t}{n}\Big{)},$

which gives us the desired result. ∎

To prove Theorem 5 we require the following lemma on the nonexpansiveness of
gradient map $\mathbf{w}\mapsto\mathbf{w}-\eta\nabla
f(\mathbf{w};z,z^{\prime})$.

######  Lemma 2 (Hardt et al. 17).

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto
f(\mathbf{w};z,z^{\prime})$ is convex and $L$-smooth. Then for all $\eta\leq
2/L$ and $z,z^{\prime}\in\mathcal{Z}$ there holds

$\|\mathbf{w}-\eta\nabla
f(\mathbf{w};z,z^{\prime})-\mathbf{w}^{\prime}+\eta\nabla
f(\mathbf{w}^{\prime};z,z^{\prime})\|_{2}\leq\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}.$

###### Proof of Theorem 5.

Let $S^{\prime}=\\{z_{1},\ldots,z_{n-1},z_{n}^{\prime}\\}$, where
$z_{n}^{\prime}$ is independently drawn from $\rho$. Let
$\\{\mathbf{w}_{t}^{\prime}\\}$ be produced by Algorithm 1 w.r.t.
$S^{\prime}$. We consider two cases. If $i_{t}\neq n$ and $i_{t-1}\neq n$,
then it follows from Lemma 2 that

$\displaystyle\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\mathbf{w}_{t-1}-\eta_{t}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\mathbf{w}^{\prime}_{t-1}+\eta_{t}\nabla
f(\mathbf{w}^{\prime}_{t-1};z^{\prime}_{i_{t}},z^{\prime}_{i_{t-1}})\big{\|}_{2}$
$\displaystyle=\big{\|}\mathbf{w}_{t-1}-\eta_{t}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\mathbf{w}^{\prime}_{t-1}+\eta_{t}\nabla
f(\mathbf{w}^{\prime}_{t-1};z_{i_{t}},z_{i_{t-1}})\big{\|}_{2}$
$\displaystyle\leq\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}.$

Otherwise, we know

$\displaystyle\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}$
$\displaystyle\leq\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}+\eta_{t}\big{\|}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\nabla
f(\mathbf{w}^{\prime}_{t-1};z^{\prime}_{i_{t}},z^{\prime}_{i_{t-1}})\big{\|}_{2}$
$\displaystyle\leq\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}+2\eta_{t}G.$

We can combine the above two cases together and derive the following
inequality

$\displaystyle\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}$
$\displaystyle\leq\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}\mathbb{I}_{[i_{t}\neq
n\text{ and }i_{t-1}\neq
n]}+\big{(}\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}+2\eta_{t}G\big{)}\mathbb{I}_{[i_{t}=n\text{
or }i_{t-1}=n]}$
$\displaystyle=\|\mathbf{w}_{t-1}-\mathbf{w}^{\prime}_{t-1}\|_{2}+2\eta_{t}G\mathbb{I}_{[i_{t}=n\text{
or }i_{t-1}=n]}.$

We can apply the above inequality recursively and get

$\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}\leq
2G\sum_{j=1}^{t}\eta_{j}\mathbb{I}_{[i_{j}=n\text{ or }i_{j-1}=n]}\leq
2G\sum_{j=1}^{t}\eta_{j}\big{(}\mathbb{I}_{[i_{j}=n]}+\mathbb{I}_{[i_{j-1}=n]}).$

Taking expectations over both sides gives
$\mathbb{E}_{\mathcal{A}}\big{[}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}\big{]}\leq\frac{4G}{n}\sum_{j=1}^{t}\eta_{j}.$
It then follows from the convexity of $\|\cdot\|_{2}$ that

$\mathbb{E}_{\mathcal{A}}\big{[}\|\bar{\mathbf{w}}_{t}-\bar{\mathbf{w}}_{t}^{\prime}\big{\|}_{2}\big{]}\leq\frac{4G}{n}\sum_{j=1}^{t}\eta_{j}.$

This establishes the uniform argument stability of Algorithm 1. Furthermore,
it follows the Lipschitz condition that

$\sup_{z,z^{\prime}}\mathbb{E}_{\mathcal{A}}\big{[}f(\bar{\mathbf{w}}_{t};z,z^{\prime})-f(\bar{\mathbf{w}}_{t}^{\prime};z,z^{\prime})\big{]}\leq\frac{4G^{2}}{n}\sum_{j=1}^{t}\eta_{j}.$

The desired result then follows from Lemma 1. The proof for Theorem 5 is
completed. ∎

Finally, we consider the generalization analysis for nonconvex problems under
the PL condition. To prove Theorem 3, we first introduce a lemma motivated by
the arguments in [17].

######  Lemma 3.

Let $S=\\{z_{i}\\}_{i\in[n]}$ and $S^{\prime}=\\{z_{i}^{\prime}\\}_{i\in[n]}$
be neighboring datasets differing by a single example. Let
$\\{\mathbf{w}_{t}\\}_{t}$ and $\\{\mathbf{w}_{t}^{\prime}\\}_{t}$ be produced
by Algorithm 1 w.r.t. $S$ and $S^{\prime}$, respectively. Let Assumption (A1)
hold and $\sup_{z,z^{\prime}}f(\mathbf{w}_{i},z,z^{\prime})\leq B$. Let
$\triangle_{t}=\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}$. Then for every
$z,z^{\prime}\in\mathcal{Z}$ and every $t_{0}\in[n]$, there holds

$\mathbb{E}\big{[}|f(\mathbf{w}_{T};z,z^{\prime})-f(\mathbf{w}_{T}^{\prime};z,z^{\prime})|\big{]}\leq
G\mathbb{E}\big{[}\triangle_{T}|\triangle_{t_{0}}=0\big{]}+\frac{Bt_{0}}{n}.$

###### Proof.

Without loss of generality, we assume that $S$ and $S^{\prime}$ differ by the
last example. Let $\mathcal{E}$ denote the event $\triangle_{t_{0}}=0$. Then
we have

$\mathbb{E}\big{[}|f(\mathbf{w}_{T};z,z^{\prime})-f(\mathbf{w}_{T}^{\prime};z,z^{\prime})|\big{]}=\mathbb{E}\big{[}|f(\mathbf{w}_{T};z,z^{\prime})-f(\mathbf{w}_{T}^{\prime};z,z^{\prime})||\mathcal{E}\big{]}\mbox{Pr}\\{\mathcal{E}\\}\\\
+\mathbb{E}\big{[}|f(\mathbf{w}_{T};z,z^{\prime})-f(\mathbf{w}_{T}^{\prime};z,z^{\prime})||\mathcal{E}^{c}\big{]}\mbox{Pr}\\{\mathcal{E}^{c}\\},$

where $\mathcal{E}^{c}$ denotes the complement of $\mathcal{E}$. Furthermore,
we know

$\mbox{Pr}\\{\mathcal{E}^{c}\\}\leq\sum_{t=1}^{t_{0}}\mbox{Pr}\\{i_{t}=n\\}=\frac{t_{0}}{n}.$

We can combine the above two inequalities and the Lipschitz continuity of $f$
to derive the stated bound, which completes the proof. ∎

##  Appendix B Proofs of Optimization Error (Theorems 6-9)

In this section, we prove optimization error bounds for SGD. We first consider
convex cases, and prove convergence rates in expectation (Theorem 6) and with
high probability (Theorem 7). Then, we establish convergence rates for SGD
with nonconvex loss functions (Theorem 8 and Theorem 9).

###### Proof of Theorem 6.

Consider $j\geq 1$. Note that $f(\cdot;z,z^{\prime})$ is $\alpha$-strongly
convex and $G$-Lipschitz continuous, we have

$\displaystyle\|\mathbf{w}_{j}-\mathbf{w}\|_{2}^{2}\leq\|\mathbf{w}_{j-1}-\eta_{j}\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})-\mathbf{w}\|_{2}^{2}$
$\displaystyle=\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-2\eta_{j}\langle\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}}),\mathbf{w}_{j-1}-\mathbf{w}\rangle+\eta_{j}^{2}\|\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}$
$\displaystyle\leq(1-\eta_{j}\alpha)\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-2\eta_{j}[f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})]+G^{2}\eta_{j}^{2}$
$\displaystyle=(1-\eta_{j}\alpha)\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-2\eta_{j}[f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})]$
$\displaystyle+2\eta_{j}[f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})]+G^{2}\eta_{j}^{2}$
$\displaystyle\leq(1-\eta_{j}\alpha)\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-2\eta_{j}[f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})]$
$\displaystyle+2\eta_{j}G\|\mathbf{w}_{j-1}-\mathbf{w}_{j-2}\|_{2}+G^{2}\eta_{j}^{2}$
$\displaystyle\leq(1-\eta_{j}\alpha)\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-2\eta_{j}[f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})]$
$\displaystyle+2G^{2}\eta_{j}\eta_{j-1}+G^{2}\eta_{j}^{2},$ (B.1)

where the last inequality used the fact that
$\|\mathbf{w}_{j}-\mathbf{w}_{j-1}\|_{2}=\eta_{j}\|\nabla
f(\mathbf{w}_{j};z_{i_{j}},z_{i_{j-1}})\|_{2}\leq G\eta_{j}.$

For the convex case, i.e. $\alpha=0$, we know from (B.1) that

$\displaystyle\sum_{j=1}^{t}\eta_{j}[f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})]$
$\displaystyle\leq\frac{1}{2}\sum_{j=1}^{t}[\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-\|\mathbf{w}_{j}-\mathbf{w}\|_{2}^{2}]+\frac{G^{2}}{2}\sum_{j=1}^{t}(2\eta_{j-1}\eta_{j}+\eta^{2}_{j})$
$\displaystyle\leq\frac{1}{2}\|\mathbf{w}_{0}-\mathbf{w}\|_{2}^{2}+\frac{G^{2}}{2}\sum_{j=1}^{t}(2\eta_{j-1}\eta_{j}+\eta^{2}_{j}).$
(B.2)

Taking the expectation on both sides of the above inequality and observing
that $f(\cdot;z,z^{\prime})$ is convex, we get the desired estimation (5).

For the strongly-convex case, i.e. $\alpha>0$, we obtain from (B.1) that

$f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})\leq\frac{\eta_{j}^{-1}-\alpha}{2}\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-\frac{\eta_{j}^{-1}}{2}\|\mathbf{w}_{j}-\mathbf{w}\|_{2}^{2}+G^{2}\eta_{j-1}+\frac{G^{2}\eta_{j}}{2}.$

Now, we choose $\eta_{j}=\frac{2}{\alpha(j+1)}$ for any $j$, which implies
that

$\displaystyle
j[f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})]$
$\displaystyle\leq\frac{j(j-1)\alpha}{4}\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-\frac{j(j+1)\alpha}{4}\|\mathbf{w}_{j}-\mathbf{w}\|_{2}^{2}+\frac{2G^{2}}{\alpha}+\frac{G^{2}j}{\alpha(j+1)}$
$\displaystyle\leq\frac{\alpha}{4}[{j(j-1)}\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-{j(j+1)}\|\mathbf{w}_{j}-\mathbf{w}\|_{2}^{2}]+\frac{3G^{2}}{\alpha}.$

Taking the summation over $j$ implies that

$\displaystyle\sum_{j=1}^{t}j[f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})-f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})]$
$\displaystyle\leq\frac{3G^{2}t}{\alpha}+\frac{\alpha}{4}\sum_{j=1}^{t}[{j(j-1)}\|\mathbf{w}_{j-1}-\mathbf{w}\|_{2}^{2}-{j(j+1)}\|\mathbf{w}_{j}-\mathbf{w}\|_{2}^{2}]$
$\displaystyle\leq\frac{3G^{2}t}{\alpha}+\frac{\alpha}{4}[0-{t(t+1)}\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}]\leq\frac{3G^{2}t}{\alpha}.$
(B.3)

Dividing both sides of the above inequality by $\sum_{j=1}^{t}j$ yields the
desired estimation in part (b). ∎

To prove high-probability bounds, we require the following lemma on
concentration inequalities of martingales [6, 47].

######  Lemma 4.

Let $\tilde{z}_{1},\ldots,\tilde{z}_{n}$ be a sequence of random variables
such that $\tilde{z}_{k}$ may depend on the previous variables
$\tilde{z}_{1},\ldots,\tilde{z}_{k-1}$ for all $k=1,\ldots,n$. Consider a
sequence of functionals
$\xi_{k}(\tilde{z}_{1},\ldots,\tilde{z}_{k}),k=1,\ldots,n$. Let
$\alpha_{n}^{2}=\sum_{k=1}^{n}\mathbb{E}_{\tilde{z}_{k}}\big{[}\big{(}\xi_{k}-\mathbb{E}_{\tilde{z}_{k}}[\xi_{k}]\big{)}^{2}\big{]}$
be the conditional variance.

  1. (1)

Assume $|\xi_{k}-\mathbb{E}_{\tilde{z}_{k}}[\xi_{k}]|\leq b_{k}$ for each $k$.
Let $\delta\in(0,1)$. With probability at least $1-\delta$

$\sum_{k=1}^{n}\mathbb{E}_{\tilde{z}_{k}}[\xi_{k}]-\sum_{k=1}^{n}\xi_{k}\leq\Big{(}2\sum_{k=1}^{n}b_{k}^{2}\log\frac{1}{\delta}\Big{)}^{\frac{1}{2}}.$
(B.4)

  2. (2)

Assume that $\xi_{k}-\mathbb{E}_{\tilde{z}_{k}}[\xi_{k}]\leq b$ for each $k$.
Let $\rho\in(0,1]$ and $\delta\in(0,1)$. With probability at least $1-\delta$
we have

$\sum_{k=1}^{n}\mathbb{E}_{\tilde{z}_{k}}[\xi_{k}]-\sum_{k=1}^{n}\xi_{k}\leq\frac{\rho\alpha_{n}^{2}}{b}+\frac{b\log\frac{1}{\delta}}{\rho}.$
(B.5)

###### Proof of Theorem 7.

For simplicity, we assume $t$ is an even number. We first consider the convex
case. Let

$\xi_{j}=\eta_{2j}\big{(}f(\mathbf{w}_{2j-2};z_{i_{2j}},z_{i_{2j-1}})-f(\mathbf{w};z_{i_{2j}},z_{i_{2j-1}})\big{)},\quad
j\in[t/2].$

It is obvious that $|\xi_{j}-\mathbb{E}_{i_{2j},i_{2j-1}}[\xi_{j}]|\leq
2B\eta_{2j}$. Let $\tilde{z}_{j}=(i_{2j},i_{2j-1})$. It is clear that
$\tilde{z}_{j},j\in[t/2]$ are i.i.d. random variables. Therefore, one can
apply Part (a) of Lemma 4 to derive the following inequality with probability
at least $1-\delta/2$

$\sum_{j=1}^{t/2}\mathbb{E}_{\tilde{z}_{j}}[\xi_{j}]-\sum_{j=1}^{t/2}\xi_{j}\leq
2B\Big{(}2\sum_{j=1}^{t/2}\eta_{2j}^{2}\log(2/\delta)\Big{)}^{\frac{1}{2}}.$

It is clear that
$\mathbb{E}_{\tilde{z}_{j}}[\xi_{j}]=\eta_{2j}\big{(}F_{S}(\mathbf{w}_{2j-2})-{F_{S}(\mathbf{w})}\big{)}$.
Therefore, the following inequality holds with probability at least
$1-\delta/2$

$\sum_{j=1}^{t/2}\eta_{2j}\big{(}F_{S}(\mathbf{w}_{2j-2})-F_{S}(\mathbf{w})-f(\mathbf{w}_{2j-2};z_{i_{2j}},z_{i_{2j-1}})+f(\mathbf{w};z_{i_{2j}},z_{i_{2j-1}})\big{)}\leq
2B\Big{(}2\sum_{j=1}^{t/2}\eta_{2j}^{2}\log(2/\delta)\Big{)}^{\frac{1}{2}}.$

In a similar way, one can derive the following inequality with probability at
least $1-\delta/2$

$\sum_{j=1}^{t/2}\eta_{2j-1}\big{(}F_{S}(\mathbf{w}_{2j-3})-F_{S}(\mathbf{w})-f(\mathbf{w}_{2j-3};z_{i_{2j-1}},z_{i_{2j-2}})\\\
+f(\mathbf{w};z_{i_{2j-1}},z_{i_{2j-2}})\big{)}\leq
2B\Big{(}2\sum_{j=1}^{t/2}\eta_{2j-1}^{2}\log(2/\delta)\Big{)}^{\frac{1}{2}}.$

We can combine the above two inequalities together and derive the following
inequality with probability $1-\delta$

$\sum_{j=1}^{t}\eta_{j}\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w})-f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})+f(\mathbf{w};z_{i_{j}},z_{i_{j-1}})\big{)}\leq
2B\Big{(}2\sum_{j=1}^{t}\eta_{j}^{2}\log(2/\delta)\Big{)}^{\frac{1}{2}}.$

We can combine the above inequality and Eq. (B) to derive the following
inequality with probability at least $1-\delta$

$\sum_{j=1}^{t}\eta_{j}\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w})\big{)}\leq
2B\Big{(}2\sum_{j=1}^{t}\eta_{j}^{2}\log(2/\delta)\Big{)}^{\frac{1}{2}}+\frac{1}{2}\|\mathbf{w}_{{0}}-\mathbf{w}\|_{2}^{2}+G^{2}\sum_{j=1}^{t}\big{(}\eta_{j-1}\eta_{j}+\frac{\eta^{2}_{j}}{{2}}\big{)}.$

The stated bound then follows from the convexity of $F_{S}$.

We now turn to the strongly convex case. Let

$\xi_{j}=2j(f(\mathbf{w}_{2j-2};z_{i_{2j}},z_{i_{2j-1}})-f(\mathbf{w}_{S};z_{i_{2j}},z_{i_{2j-1}})),\quad
j\in[t/2].$

It is clear that $|\xi_{j}-\mathbb{E}_{i_{2j},i_{2j-1}}[\xi_{j}]|\leq 4jB\leq
2tB$ for $j\in[t/2]$. Furthermore, the conditional variance satisfies

$\displaystyle\mathbb{E}_{\tilde{z}_{j}}\big{[}\big{(}\xi_{j}-\mathbb{E}_{\tilde{z}_{j}}[\xi_{j}]\big{)}^{2}\big{]}$
$\displaystyle\leq\mathbb{E}_{\tilde{z}_{j}}[\xi_{j}^{2}]\leq
4j^{2}G^{2}\|\mathbf{w}_{2j-2}-\mathbf{w}_{S}\|_{2}^{2}$ $\displaystyle\leq
8\alpha^{-1}j^{2}G^{2}\big{(}F_{S}(\mathbf{w}_{2j-2})-F_{S}(\mathbf{w}_{S})\big{)},$

where the first inequality follows from $f$ is $G$-Lipschitz continuous, and
the second inequality used the fact $\nabla F_{S}(\mathbf{w}_{S})=0$ and $f$
is $\alpha$-strongly convex.

Note $\tilde{z}_{j}$ are independent random variables and

$\mathbb{E}_{\tilde{z}_{j}}[\xi_{j}]=2j\big{(}F_{S}(\mathbf{w}_{2j-2})-F_{S}(\mathbf{w}_{S})\big{)}.$

Therefore, we can apply Part (b) of Lemma 4 to derive the following inequality
with probability at least $1-\delta/2$

$2\sum_{j=1}^{t/2}j\Big{(}F_{S}(\mathbf{w}_{2j-2})-F_{S}(\mathbf{w}_{S})-f(\mathbf{w}_{2j-2};z_{i_{2j}},z_{i_{2j-1}})+f(\mathbf{w}_{S};z_{i_{2j}},z_{i_{2j-1}})\Big{)}\\\
\leq\frac{8G^{2}\rho\sum_{j=1}^{t/2}j^{2}\big{(}F_{S}(\mathbf{w}_{2j-2})-F_{S}(\mathbf{w}_{S})\big{)}}{2tB\alpha}+\frac{2tB\log(2/\delta)}{\rho}.$

In a similar way, one can derive the following inequality with probability at
least $1-\delta/2$

$\sum_{j=1}^{t/2}(2j-1)\Big{(}F_{S}(\mathbf{w}_{2j-3})-F_{S}(\mathbf{w}_{S})-f(\mathbf{w}_{2j-3};z_{i_{2j-1}},z_{i_{2j-2}})+f(\mathbf{w}_{S};z_{i_{2j-1}},z_{i_{2j-2}})\Big{)}\\\
\leq\frac{2G^{2}\rho\sum_{j=1}^{t/2}(2j-1)^{2}\big{(}F_{S}(\mathbf{w}_{2j-3})-F_{S}(\mathbf{w}_{S})\big{)}}{2tB\alpha}+\frac{2tB\log(2/\delta)}{\rho}.$

We can combine the above two inequalities together and derive the following
inequality with probability at least $1-\delta$

$\sum_{j=1}^{t}j\Big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w}_{S})-f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})+f(\mathbf{w}_{S};z_{i_{j}},z_{i_{j-1}})\Big{)}\\\
\leq\frac{2G^{2}\rho\sum_{j=1}^{t}j^{2}\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w}_{S})\big{)}}{2tB\alpha}+\frac{2tB\log(2/\delta)}{\rho}.$

We can combine the above inequality and Eq. (B.3) together and derive the
following inequality with probability $1-\delta$

$\sum_{j=1}^{t}j\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w}_{S})\big{)}\leq\frac{3G^{2}t}{\alpha}+\frac{G^{2}\rho\sum_{j=1}^{t}j\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w}_{S})\big{)}}{B\alpha}+\frac{2tB\log(2/\delta)}{\rho}.$

Now, we take $\rho=\min\big{\\{}1,B\alpha/(2G^{2})\big{\\}}$ and get the
following inequality with probability at least $1-\delta$

$\sum_{j=1}^{t}j\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w}_{S})\big{)}\leq\frac{3G^{2}t}{\alpha}+\frac{1}{2}\sum_{j=1}^{t}j\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w}_{S})\big{)}+2t\log(2/\delta)\max\big{\\{}B,2G^{2}/\alpha\big{\\}}$

and therefore

$\sum_{j=1}^{t}j\big{(}F_{S}(\mathbf{w}_{j-2})-F_{S}(\mathbf{w}_{S})\big{)}\leq\frac{14G^{2}t\log(2/\delta)}{\alpha}+4Bt\log(2/\delta).$

The stated bound then follows from the convexity of $F_{S}$. The proof is
completed. ∎

We now turn to nonconvex problems.

###### Proof of Theorem 8.

It is clear that $F_{S}$ is $L$-smooth and therefore

$\displaystyle F_{S}(\mathbf{w}_{j})$ $\displaystyle\leq
F_{S}(\mathbf{w}_{j-1})+\langle\mathbf{w}_{j}-\mathbf{w}_{j-1},\nabla
F_{S}(\mathbf{w}_{j-1})\rangle+\frac{L}{2}\|\mathbf{w}_{j}-\mathbf{w}_{j-1}\|_{2}^{2}$
$\displaystyle=F_{S}(\mathbf{w}_{j-1})-\eta_{j}\langle\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})\rangle+\frac{L\eta_{j}^{2}}{2}\|\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}$

Taking expectations over both sides gives

$\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})]\leq\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})]-\eta_{j}\mathbb{E}_{\mathcal{A}}\big{[}\langle\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})\rangle\big{]}+\\\
\frac{L\eta_{j}^{2}}{2}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}\big{]}.$ (B.6)

According to the elementary inequality $(a+b)^{2}\leq 2(a^{2}+b^{2})$ we know

$\displaystyle\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}\big{]}$ $\displaystyle\leq
2\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})-\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}\big{]}+2\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}\big{]}$ $\displaystyle\leq
2L\mathbb{E}_{\mathcal{A}}\big{[}\|\mathbf{w}_{j-1}-\mathbf{w}_{j-2}\|_{2}^{2}\big{]}+2\alpha_{0}^{2}=2L\eta_{j-1}^{2}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j-1}},z_{i_{j-2}})\|_{2}^{2}\big{]}+2\alpha_{0}^{2}$
$\displaystyle\leq\frac{1}{2}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j-1}},z_{i_{j-2}})\|_{2}^{2}\big{]}+2\alpha_{0}^{2},$

where we have used the $L$-smoothness, the assumption
$\mathbb{E}_{i_{j},i_{j-1}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}\big{]}\leq\alpha_{0}^{2}$
and $4L\eta_{j-1}^{2}\leq 1$. It is clear that
$\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{0};z_{i_{1}},z_{i_{0}})\|_{2}^{2}\big{]}\leq\alpha_{0}^{2}$. It
is easy to use an induction and the above inequality to show that

$\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}\big{]}\leq
4\alpha_{0}^{2},\quad\forall j.$ (B.7)

Furthermore, the smoothness assumption implies that

$\displaystyle\big{\langle}\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})\big{\rangle}$ $\displaystyle=\big{\langle}\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})\big{\rangle}+\big{\langle}\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})-\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})\big{\rangle}$ $\displaystyle=\big{\langle}\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-2})\big{\rangle}+\big{\langle}\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})-\nabla F_{S}(\mathbf{w}_{j-2})\big{\rangle}+$
$\displaystyle+\big{\langle}\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}})-\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})\big{\rangle}$ $\displaystyle\geq\big{\langle}\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-2})\big{\rangle}-L\|\mathbf{w}_{j-1}-\mathbf{w}_{j-2}\|_{2}\big{(}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})\|_{2}+\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}\big{)}.$

According to Schwartz inequality, the variance assumption and Eq. (B.7), we
know

$\displaystyle\mathbb{E}_{\mathcal{A}}\Big{[}\|\mathbf{w}_{j-1}-\mathbf{w}_{j-2}\|_{2}\big{(}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})\|_{2}+\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}\big{)}\Big{]}$
$\displaystyle\leq\frac{1}{2\eta_{j-1}}\mathbb{E}_{\mathcal{A}}\big{[}\|\mathbf{w}_{j-1}-\mathbf{w}_{j-2}\|_{2}^{2}\big{]}+\eta_{j-1}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}+\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}^{2}\big{]}$
$\displaystyle=\frac{\eta_{j-1}}{2}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j-1}},z_{i_{j-2}})\|_{2}^{2}\big{]}+\eta_{j-1}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}})\|_{2}^{2}+\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}^{2}\big{]}$ $\displaystyle\leq
2\alpha_{0}^{2}\eta_{j-1}+2\alpha_{0}^{2}\eta_{j-1}.$

We can combine the above two inequalities together and get

$\mathbb{E}_{\mathcal{A}}\big{[}\big{\langle}\nabla
f(\mathbf{w}_{j-1};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-1})\big{\rangle}\big{]}\geq\mathbb{E}_{\mathcal{A}}\big{[}\big{\langle}\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-2})\big{\rangle}\big{]}-4L\alpha_{0}^{2}\eta_{j-1}.$

We can combine (B.6), (B.7) and the above inequality, and get

$\displaystyle\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})]$
$\displaystyle\leq\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})]-\eta_{j}\mathbb{E}_{\mathcal{A}}\big{[}\big{\langle}\nabla
f(\mathbf{w}_{j-2};z_{i_{j}},z_{i_{j-1}}),\nabla
F_{S}(\mathbf{w}_{j-2})\big{\rangle}\big{]}+4L\alpha_{0}^{2}\eta_{j}\eta_{j-1}+2L\eta_{j}^{2}\alpha_{0}^{2}$
$\displaystyle\leq\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})]-\eta_{j}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})\|_{2}^{2}\big{]}+4L\alpha_{0}^{2}\big{(}\eta_{j}\eta_{j-1}+\eta_{j}^{2}\big{)},$

where the last inequality holds since $\mathbf{w}_{j-2}$ is independent of
$i_{j}$ and $i_{j-1}$. The above inequality can be reformulated as

$\eta_{j}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})\big{\|}_{2}^{2}\big{]}\leq\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})]-\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})]+4L\alpha_{0}^{2}\big{(}\eta_{j}\eta_{j-1}+\eta_{j}^{2}\big{)}.$
(B.8)

We can take a summation of the above inequality and get

$\sum_{j=1}^{t}\eta_{j}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})\|_{2}^{2}\big{]}\leq
F_{S}(\mathbf{w}_{0})+4L\alpha_{0}^{2}\sum_{j=1}^{t}\big{(}\eta_{j}\eta_{j-1}+\eta_{j}^{2}\big{)}.$

Since $\eta_{j}=\eta$, we further get

$\sum_{j=1}^{t}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})\|_{2}^{2}\big{]}\leq\eta^{-1}F_{S}(\mathbf{w}_{0})+8L\alpha_{0}^{2}t\eta.$

The proof is completed. ∎

###### Proof of Theorem 9.

According to the elementary inequality $\frac{1}{2}(a+b)^{2}\leq a^{2}+b^{2}$
we know

$\displaystyle\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})\big{\|}_{2}^{2}\big{]}$
$\displaystyle\geq-\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-2})-\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}^{2}\big{]}+2^{-1}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}^{2}\big{]}$
$\displaystyle\geq-L\mathbb{E}_{\mathcal{A}}\big{[}\|\mathbf{w}_{j-2}-\mathbf{w}_{j-1}\|_{2}^{2}\big{]}+2^{-1}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}^{2}\big{]}$
$\displaystyle=-L\eta_{j-1}^{2}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
f(\mathbf{w}_{j-2};z_{i_{j-1}},z_{i_{j-2}})\|_{2}^{2}\big{]}+2^{-1}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}^{2}\big{]}$
$\displaystyle\geq-4L\eta_{j-1}^{2}\alpha_{0}^{2}+2^{-1}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-1})\|_{2}^{2}\big{]},$

where we have used (B.7). This together with (B.8) gives

$2^{-1}\eta_{j}\mathbb{E}_{\mathcal{A}}\big{[}\|\nabla
F_{S}(\mathbf{w}_{j-1})\big{\|}_{2}^{2}\big{]}\leq
4L\eta_{j}\eta_{j-1}^{2}\alpha_{0}^{2}+\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})]-\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})]+4L\alpha_{0}^{2}\big{(}\eta_{j}\eta_{j-1}+\eta_{j}^{2}\big{)}.$

It then follows from the PL condition that

$\mu\eta_{j}\mathbb{E}_{\mathcal{A}}\big{[}F_{S}(\mathbf{w}_{j-1})-F_{S}(\mathbf{w}_{S})\big{]}\leq\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})]-\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})]+4L\alpha_{0}^{2}\big{(}\eta_{j}\eta_{j-1}+\eta_{j}^{2}+\eta_{j}\eta_{j-1}^{2}\big{)}.$

We can reformulate the above inequality as

$\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})-F_{S}(\mathbf{w}_{S})]\leq(1-\mu\eta_{j})\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})-F_{S}(\mathbf{w}_{S})]+4L\alpha_{0}^{2}\big{(}\eta_{j}\eta_{j-1}+\eta_{j}^{2}+\eta_{j}\eta_{j-1}^{2}\big{)}.$

Now, taking $\eta_{j}=2/(\mu(j+1))$, we get

$\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})-F_{S}(\mathbf{w}_{S})]\leq\frac{j-1}{j+1}\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})-F_{S}(\mathbf{w}_{S})]+\frac{4L\alpha_{0}^{2}}{\mu^{2}}\Big{(}\frac{8}{j(j+1)}+\frac{8}{j^{2}(j+1)\mu}\big{)}.$

We can multiple both sides by $j(j+1)$ and get

$j(j+1)\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j})-F_{S}(\mathbf{w}_{S})]\leq(j-1)j\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{j-1})-F_{S}(\mathbf{w}_{S})]+\frac{4L\alpha_{0}^{2}}{\mu^{2}}\big{(}8+8j^{-1}\mu^{-1}\big{)}.$

Taking a summation of the above inequality gives

$t(t+1)\mathbb{E}_{\mathcal{A}}[F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}_{S})]\leq\frac{32L\alpha_{0}^{2}}{\mu^{2}}\sum_{j=1}^{t}\big{(}1+j^{-1}\mu^{-1}\big{)}.$

The stated bound then follows. The proof is completed. ∎

##  Appendix C Proofs of Excess Generalization Error (Theorems 1-3)

In this section, we prove Theorem 1, Theorem 2 and Theorem 3 on excess
generalization error bounds.

###### Proof of Theorem 1.

According to Theorem 4, we know

$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})-F_{S}(\bar{\mathbf{w}}_{T})]=\mathcal{O}\Big{(}\sqrt{T}\eta+\frac{T\eta}{n}\Big{)}.$

Furthermore, according to Part (a) of Theorem 6 with
$\mathbf{w}=\mathbf{w}^{*}$, we know

$\mathbb{E}_{S,\mathcal{A}}[F_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*})]=\mathcal{O}\Big{(}\frac{1+T\eta^{2}}{T\eta}\Big{)}.$
(C.1)

We can plug the above generalization error bound and optimization error bound
back into the error decomposition (2), and get (3). Taking $T\asymp n^{2}$ and
$\eta\asymp T^{-\frac{3}{4}}$ in Eq. (3), we immediately get
$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})]-F(\mathbf{w}^{*})=\mathcal{O}(1/\sqrt{n})$.
The desired result is proved. ∎

###### Proof of Theorem 2.

According to Theorem 5, we know

$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})-F_{S}(\bar{\mathbf{w}}_{T})]=\mathcal{O}\Big{(}\frac{T\eta}{n}\Big{)}.$

We can plug the above generalization error bound and the optimization error
bound (C.1) back into the error decomposition (2), and get (4). Taking
$T\asymp n^{2}$ and $\eta\asymp T^{-\frac{3}{4}}$ in Eq. (4), we immediately
get
$\mathbb{E}_{S,\mathcal{A}}[F(\bar{\mathbf{w}}_{T})]-F(\mathbf{w}^{*})=\mathcal{O}(1/\sqrt{n})$.
The proof is completed. ∎

###### Proof of Theorem 3.

Let $S^{\prime}=\\{z_{1},\ldots,z_{n-1},z_{n}^{\prime}\\}$, where
$z_{n}^{\prime}$ is independently drawn from $\rho$. Let
$\\{\mathbf{w}_{t}^{\prime}\\}$ be produced by Algorithm 1 w.r.t.
$S^{\prime}$. If $i_{t}\neq n$ and $i_{t-1}\neq n$, then

$\displaystyle\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}$
$\displaystyle\leq\big{\|}\mathbf{w}_{t-1}-\eta_{t}\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\mathbf{w}_{t-1}^{\prime}-\eta_{t}\nabla
f(\mathbf{w}_{t-1}^{\prime};z_{i_{t}},z_{i_{t-1}})\big{\|}_{2}$
$\displaystyle\leq\|\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime}\|_{2}+\eta_{t}\|\nabla
f(\mathbf{w}_{t-1};z_{i_{t}},z_{i_{t-1}})-\nabla
f(\mathbf{w}_{t-1}^{\prime};z_{i_{t}},z_{i_{t-1}})\|_{2}$
$\displaystyle\leq(1+L\eta_{t})\|\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime}\|_{2},$

where in the last inequality we used the smoothness of $f$.

Otherwise, it follows from the Lipschitz condition that
$\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}\leq\|\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime}\|_{2}+2G\eta_{t}.$
Consequently, it follows that

$\displaystyle\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}$
$\displaystyle\leq(1+L\eta_{t})\|\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime}\|_{2}\mathbb{I}_{[i_{t}\neq
n\text{ and }i_{t-1}\neq n]}$
$\displaystyle+\big{(}\|\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime}\|_{2}+2G\eta_{t}\big{)}\mathbb{I}_{[i_{t}=n\text{
or }i_{t-1}=n]}$
$\displaystyle\leq(1+L\eta_{t})\|\mathbf{w}_{t-1}-\mathbf{w}_{t-1}^{\prime}\|_{2}+2G\eta_{t}\mathbb{I}_{[i_{t}=n\text{
or }i_{t-1}=n]}.$

We can apply the above inequality recursively and get

$\triangle_{t}\leq 2G\sum_{k=t_{0}+1}^{t}\eta_{k}\mathbb{I}_{[i_{k}=n\text{ or
}i_{k-1}=n]}\prod_{k^{\prime}=k+1}^{t}(1+L\eta_{k^{\prime}})+\triangle_{t_{0}}\prod_{k=t_{0}+1}^{t}(1+L\eta_{k}).$

Since $\triangle_{t_{0}}=0$ implies $i_{t_{0}}\neq n$, we have

$\displaystyle\mathbb{E}[\triangle_{t}|\triangle_{t_{0}}=0]$
$\displaystyle\leq
2G\sum_{k=t_{0}+1}^{t}\eta_{k}\mathbb{E}\big{[}\mathbb{I}_{[i_{k}=n\text{ or
}i_{k-1}=n]}|\triangle_{t_{0}}=0\big{]}\prod_{k^{\prime}=k+1}^{t}(1+L\eta_{k^{\prime}})$
$\displaystyle=2G\sum_{k=t_{0}+2}^{t}\eta_{k}\mathbb{E}\big{[}\mathbb{I}_{[i_{k}=n\text{
or
}i_{k-1}=n]}|\triangle_{t_{0}}=0\big{]}\prod_{k^{\prime}=k+1}^{t}(1+L\eta_{k^{\prime}})$
$\displaystyle=2G\sum_{k=t_{0}+2}^{t}\eta_{k}\mathbb{E}\big{[}\mathbb{I}_{[i_{k}=n\text{
or }i_{k-1}=n]}\big{]}\prod_{k^{\prime}=k+1}^{t}(1+L\eta_{k^{\prime}}),$

where we have used the independency between $\triangle_{t_{0}}$ and $i_{t}$
for $t>t_{0}$. It then follows that

$\displaystyle\mathbb{E}[\triangle_{t}|\triangle_{t_{0}}=0]$
$\displaystyle\leq
2G\sum_{k=t_{0}+2}^{t}\eta_{k}\mathbb{E}\big{[}\mathbb{I}_{[i_{k}=n]}+\mathbb{I}_{[i_{k-1}=n]}\big{]}\prod_{k^{\prime}=k+1}^{t}(1+L\eta_{k^{\prime}})$
$\displaystyle\leq\frac{4G}{n}\sum_{k=t_{0}+2}^{t}\eta_{k}\prod_{k^{\prime}=k+1}^{t}\exp(L\eta_{k^{\prime}})\leq\frac{8G}{\mu
n}\sum_{k=t_{0}+2}^{t}\frac{1}{k+1}\exp\Big{(}2L\mu^{-1}\sum_{k^{\prime}=k+1}^{t}\frac{1}{k^{\prime}+1}\Big{)}$
$\displaystyle\leq\frac{8G}{\mu
n}\sum_{k=t_{0}+2}^{t}\frac{1}{k+1}\exp\Big{(}2L\mu^{-1}\log(t/k)\Big{)}=\frac{8G}{\mu
n}\sum_{k=t_{0}+2}^{t}\frac{1}{k+1}\Big{(}\frac{t}{k}\Big{)}^{2L\mu^{-1}}$
$\displaystyle\leq\frac{8Gt^{2L\mu^{-1}}}{\mu
n}\sum_{k=t_{0}+2}^{t}k^{-1-2L\mu^{-1}}\leq\frac{8G}{\mu
n(2L\mu^{-1})}\Big{(}\frac{t}{t_{0}}\Big{)}^{2L\mu^{-1}}.$

Here we use $1+x\leq\exp(x)$ and $\eta_{j}=\frac{2}{\mu(j+1)}$. We can plug
the above inequality back into Lemma 3 and derive

$\mathbb{E}\big{[}|f(\mathbf{w}_{T};z,z^{\prime})-f(\mathbf{w}_{T}^{\prime};z,z^{\prime})|\big{]}\leq\frac{4G^{2}}{nL}\Big{(}\frac{T}{t_{0}}\Big{)}^{2L\mu^{-1}}+\frac{Bt_{0}}{n}.$

We can choose $t_{0}\asymp T^{\frac{2L}{2L+\mu}}$ and get the following
generalization error bounds

$\mathbb{E}\big{[}|f(\mathbf{w}_{T};z,z^{\prime})-f(\mathbf{w}_{T}^{\prime};z,z^{\prime})|\big{]}=\mathcal{O}\Big{(}\frac{T^{\frac{2L}{2L+\mu}}}{n}\Big{)}.$

Lemma 1 then implies
$\mathbb{E}\big{[}F(\mathbf{w}_{T})-F_{S}(\mathbf{w}_{T})\big{]}=\mathcal{O}\Big{(}\frac{T^{\frac{2L}{2L+\mu}}}{n}\Big{)}$.
Furthermore, according to Theorem 9 we have the following optimization error
bounds

$\mathbb{E}_{A}[F_{S}(\mathbf{w}_{T})]-\inf_{\mathbf{w}}[F_{S}(\mathbf{w})]=\mathcal{O}\big{(}1/(T\mu^{2})\big{)}.$

The desired result follows by combining the above two inequalities together
and using the fact
$\mathbb{E}[\inf_{\mathbf{w}}[F_{S}(\mathbf{w})]\leq\mathbb{E}[F_{S}(\mathbf{w}^{*})]=F(\mathbf{w}^{*})$.
∎

##  Appendix D Proof of Privacy and Utility Guarantees of Algorithm 3 (Theorem
10)

In this section, we present the proof of Theorem 10 on the privacy guarantee
and excess generalization bound of Algorithm 3.

To this end, we need the definition of $\ell_{2}$-sensitivity in terms of high
probability and some lemmas. The $\ell_{2}$-sensitivity definition given below
corresponds to the high probability version of uniform argument stability
stated in Definition 1.

######  Definition 3.

For any $\gamma\in(0,1)$, a (randomized) algorithm $\mathcal{A}$ has
$\ell_{2}$-sensitivity of $\Delta$ with probability at least $1-\gamma$ if for
any neighboring datasets $S,S^{\prime}\in\mathcal{Z}^{n}$, one has
$\|\mathcal{A}(S)-\mathcal{A}(S^{\prime})\|_{2}\leq\Delta$.

The next lemma demonstrates that Gaussian mechanism ensures the privacy of an
algorithm with high probability $\ell_{2}$-sensitivity.

######  Lemma 5.

Let $\mathcal{A}:\mathcal{Z}^{n}\rightarrow\mathbb{R}^{d}$ be a randomized
algorithm with $\ell_{2}$-sensitivity of $\Delta$ with probability at least
$1-\delta/2$. Then the Gaussian mechanism
$\mathcal{M}(S)=\mathcal{A}(S)+\mathbf{u}$ where
$\mathbf{u}\sim\mathcal{N}(0,(2\Delta^{2}\log(2.5/\delta)/\epsilon^{2})I_{d})$
satisfies $(\epsilon,\delta)$-DP.

###### Proof.

Let $S$ and $S^{\prime}$ be two neighboring datasets. Denote $E$ as the set
when $\mathcal{A}$ satisfies $\ell_{2}$-sensitivity of $\Delta$, i.e.
$E=\\{\|\mathcal{A}(S)-\mathcal{A}(S^{\prime})\|_{2}\leq\Delta\\}$. Then we
know $\mathbb{P}[E]\geq 1-\delta/2$. In favor of $E$, by classical results for
Gaussian mechanism, we know $\mathcal{M}$ satisfies $(\epsilon,\delta/2)$-DP
with $\sigma=\Delta\sqrt{2\log(2.5/\delta)}/\epsilon$. Therefore, for any
$\epsilon>0$ and any event $O$ in the output space of $\mathcal{M}$, we have

$\displaystyle\mathbb{P}[\mathcal{M}(S)\in O]=$
$\displaystyle\mathbb{P}[\mathcal{M}(S)\in
O|E]\mathbb{P}[E]+\mathbb{P}[\mathcal{M}(S)\in O|E^{c}]\mathbb{P}[E^{c}]$
$\displaystyle\leq$
$\displaystyle\Big{(}e^{\epsilon}\mathbb{P}[\mathcal{M}(S^{\prime})\in
O|E]+\frac{\delta}{2}\Big{)}\mathbb{P}[E]+\frac{\delta}{2}$
$\displaystyle\leq$ $\displaystyle
e^{\epsilon}\mathbb{P}[\mathcal{M}(S^{\prime})\in O\cap
E]+\frac{\delta}{2}+\frac{\delta}{2}$ $\displaystyle\leq$ $\displaystyle
e^{\epsilon}\mathbb{P}[\mathcal{M}(S^{\prime})\in O]+\delta$

where the first inequality is because $\mathcal{M}$ satisfies
$(\epsilon,\delta/2)$-DP when $E$ occurs and $\mathbb{P}[E^{c}]\leq\delta/2$,
the second and third inequalities are by basic properties of probability. The
proof is completed. ∎

We need the following Chernoff’s bound for a summation of independent
Bernoulli random variables [43].

######  Lemma 6 (Chernoff bound for Bernoulli vector).

Let $X_{1},\ldots,X_{t}$ be independent random variables taking values in
$\\{0,1\\}$. Let $X=\sum_{j=1}^{t}X_{j}$ and $\mu=\mathbb{E}[X]$. Then for any
$\tilde{\gamma}>0$, with probability at least
$1-\exp\big{(}-\mu\tilde{\gamma}^{2}/(2+\tilde{\gamma})\big{)}$ we have
$X\leq(1+\tilde{\gamma})\mu$.

In order to prove the privacy guarantee and excess generalization bound for
Algorithm 3, we also need the following high probability
$\ell_{2}$-sensitivity of the output of Algorithm 1.

######  Lemma 7.

Let $\\{\bar{\mathbf{w}}_{t}\\}$ and $\\{\bar{\mathbf{w}}^{\prime}_{t}\\}$ be
produced by Algorithm 1 based on the neighboring datasets $S$ and
$S^{\prime}$, respectively. If $f$ is convex and $L$-smooth and
$\eta_{t}=\eta\leq 2/L$, then with probability at least $1-\gamma$ we have

$\|\bar{\mathbf{w}}_{t}-\bar{\mathbf{w}}_{t}^{\prime}\big{\|}_{2}\leq
4G\eta\Big{(}\frac{t}{n}+\log(2/\gamma)+\sqrt{\frac{t\log(2/\gamma)}{n}}\Big{)}.$

###### Proof.

Without loss of generality, we assume the different example between $S$ and
$S^{\prime}$ is the $n$-th item. By the proof of Theorem 5, we know

$\big{\|}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\big{\|}_{2}\leq
2G\sum_{j=1}^{t}\eta_{j}\mathbb{I}_{[i_{j}=n\text{ or }i_{j-1}=n]}\leq
2G\sum_{j=1}^{t}\eta_{j}\big{(}\mathbb{I}_{[i_{j}=n]}+\mathbb{I}_{[i_{j-1}=n]}).$

Applying Lemma 6, with probability at least $1-\gamma$ there holds

$\sum_{j=1}^{t}(\mathbb{I}_{[i_{j}=n]}+\mathbb{I}_{[i_{j-1}=n]})\leq\frac{2t}{n}+2\log(2/\gamma)+2\sqrt{\frac{t\log(2/\gamma)}{n}}.$

It then follows from the convexity of $\|\cdot\|_{2}$ that

$\|\bar{\mathbf{w}}_{t}-\bar{\mathbf{w}}_{t}^{\prime}\big{\|}_{2}\leq
4G\eta\Big{(}\frac{t}{n}+\log(2/\gamma)+\sqrt{\frac{t\log(2/\gamma)}{n}}\Big{)},$

which implies the desired result. ∎

With the above preparations, we are now ready to prove Theorem 10.

###### Proof of Theorem 10.

We first consider the privacy guarantee of Algorithm 3. Since we run Algorithm
1 for $\lceil n_{k}\log(4/\delta)\rceil$ steps for each $k$, by Lemma 7, we
know with probability $1-\delta/2$

$\|\bar{\mathbf{w}}_{k}-\bar{\mathbf{w}}_{k}^{\prime}\big{\|}_{2}\leq
12G\eta_{k}\log(4/\delta).$

Therefore, by Lemma 5, each iteration $k$ of Algorithm 3 is
$(\epsilon,\delta)$-DP. Since the partition of the dataset $S$ is disjoint,
and each iteration $k$ of Algorithm 3 we only use one subset, thus the whole
process satisfies $(\epsilon,\delta)$-DP.

Next we investigate the utility bound of Algorithm 3. Let
$\bar{\mathbf{w}}_{0}=\mathbf{w}^{*}$ and
$\mathbf{u}_{0}=\mathbf{w}_{0}-\mathbf{w}^{*}$, then

$\displaystyle\mathbb{E}[F(\mathbf{w}_{K})-F(\mathbf{w}^{*})]=\sum_{k=1}^{K}\mathbb{E}[F(\bar{\mathbf{w}}_{k})-F(\bar{\mathbf{w}}_{k-1})]+\mathbb{E}[F(\mathbf{w}_{K})-F(\bar{\mathbf{w}}_{K})]$
(D.1)

Denote $F_{S_{k}}$ be the empirical objective based on sample $S_{k}$. For the
first term on the RHS of (D.1), we have

$\displaystyle\mathbb{E}[F(\bar{\mathbf{w}}_{k})-F(\bar{\mathbf{w}}_{k-1})]$
$\displaystyle=\mathbb{E}[F(\bar{\mathbf{w}}_{k})-F_{S_{k}}(\bar{\mathbf{w}}_{k})]+\mathbb{E}[F_{S_{k}}(\bar{\mathbf{w}}_{k})-F_{S_{k}}(\bar{\mathbf{w}}_{k-1})]+\mathbb{E}[F_{S_{k}}(\bar{\mathbf{w}}_{k-1})-F(\bar{\mathbf{w}}_{k-1})]$
$\displaystyle=\mathbb{E}[F(\bar{\mathbf{w}}_{k})-F_{S_{k}}(\bar{\mathbf{w}}_{k})]+\mathbb{E}[F_{S_{k}}(\bar{\mathbf{w}}_{k})-F_{S_{k}}(\bar{\mathbf{w}}_{k-1})]$
$\displaystyle\leq
8G^{2}\log(4/\delta)\eta_{k}+\Big{(}\frac{\mathbb{E}[\|\mathbf{u}_{k-1}\|_{2}^{2}]}{2\eta_{k}n_{k}}+\frac{3G^{2}\eta_{k}}{2}\Big{)}\leq\frac{\mathbb{E}[\|\mathbf{u}_{k-1}\|_{2}^{2}]}{2\eta_{k}n_{k}}+18\log(4/\delta)G^{2}\eta_{k},$

where the second identity is because $\bar{\mathbf{w}}_{k-1}$ is independent
of $S_{k}$ and the inequality follows from Theorem 6 Part (a) and Theorem 5.
Recall that by definition
$\eta\leq\frac{D\epsilon}{12G\log(4/\delta)\sqrt{2d\log(2.5/\delta)}}$, so
that for all $k\geq 0$,

$\mathbb{E}[\|\mathbf{u}_{k}\|_{2}^{2}]=d\sigma_{k}^{2}=d\Big{(}\frac{4^{-k}G\eta}{\epsilon}\Big{)}^{2}\leq
16^{-k}D^{2}.$

Plugging the above estimate into (D.1) it follows

$\displaystyle\mathbb{E}[F(\mathbf{w}_{K})-F(\mathbf{w}^{*})]\leq$
$\displaystyle\sum_{k=1}^{K}\frac{8\cdot 16^{-k}D^{2}}{4^{-k}2^{-k}\eta
n}+18\log(4/\delta)4^{-k}G^{2}\eta+4^{-K}GD$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}2^{-k}\Big{(}\frac{8D^{2}}{\eta
n}+18\log(4/\delta)G^{2}\eta\Big{)}+\frac{GD}{n^{2}}$ $\displaystyle=$
$\displaystyle\mathcal{O}\Big{(}GD\Big{(}\frac{1}{\sqrt{n}}+\frac{\sqrt{d}\log^{\frac{3}{2}}(1/\delta)}{\epsilon
n}\Big{)}\Big{)},$

where in the second inequality used $K=\lceil\log_{2}n\rceil$, and the last
inequality is due to
$\eta=\frac{D}{G}\min\\{\frac{\log(4/\delta)}{\sqrt{n}},\frac{\epsilon}{12\log(4/\delta)\sqrt{2d\log(2.5/\delta)}}\\}$.
The desired excess generalization error bound is proved.

Finally, we investigate the gradient complexity argument. Since we run
Algorithm 1 for $n_{k}$ at iteration $k$. Therefore, the total gradient
complexity is
$\mathcal{O}\Big{(}\sum_{k=1}^{K}n_{k}\Big{)}=\mathcal{O}(n\log(1/\delta)).$
The proof is completed. ∎

##  Appendix E Additional Results: Localization-Based Algorithm to Improve
Theorem 1

In this section, we provide additional results on how to reduce the gradient
complexity $\mathcal{O}(n^{2})$ required in Theorem 1 to $\mathcal{O}(n)$ for
nonsmooth problems. This improvement is attained by Algorithm 4 which is
motivated by the iterative localization technique [13].

Algorithm 4 Localized SGD for Pairwise Learning

1: Inputs: Dataset $S=\\{\mathbf{z}_{i}:i=1,\ldots,n\\}$, parameter $\zeta$,
initial point $\mathbf{w}_{0}$

2: Set $K=\lceil\log_{2}n\rceil$ and divide $S$ into $K$ disjoint subsets
$\\{S_{1},\cdots,S_{K}\\}$ such that $|S_{k}|=n_{k}=2^{-k}n$

3: for $k=1$ to $K$ do

4: Set $\zeta_{k}=2^{-k}\zeta$

5: Compute $\bar{\mathbf{w}}_{k}\in\mathcal{W}$ by Algorithm 1 with step sizes
$\eta_{j}=\frac{\zeta_{k}n_{k}}{j+1},j\in[T_{k}]$ and $T_{k}\asymp n_{k}$
iterations based on the objective $F_{k}$ where
$F_{k}(\mathbf{w};S_{k})=\frac{1}{n_{k}(n_{k}-1)}\sum_{z,z^{\prime}\in
S_{k}:z\neq
z^{\prime}}f(\mathbf{w};\mathbf{z},\mathbf{z}^{\prime})+\frac{1}{\zeta_{k}n_{k}}\|\mathbf{w}-\bar{\mathbf{w}}_{k-1}\|_{2}^{2}$

6: Outputs: $\bar{\mathbf{w}}_{K}$

The next theorem shows that the empirical risk minimization can imply models
with good excess generalization error by Algorithm 4.

######  Theorem E.1.

Let (A1) and (A3) hold true with $\alpha=0$ and let $D$ be the diameter of
$\mathcal{W}$. Let $\\{\bar{\mathbf{w}}_{k}:k\in[K]\\}$ be produced by
Algorithm 4 with $\zeta=\frac{D}{G\sqrt{n}}$. Then we have the following
excess generalization error bounds

$\mathbb{E}[F(\bar{\mathbf{w}}_{K})-F(\mathbf{w}^{*})]=\mathcal{O}\Big{(}\frac{GD}{\sqrt{n}}\Big{)}$

with gradient complexity $\mathcal{O}(n)$.

We provide two technical lemmas before we present the proof of Theorem E.1.

######  Lemma 8.

Let (A1) and (A3) hold true with $\alpha=0$ and let
$\hat{\mathbf{w}}_{k}=\arg\min_{\mathbf{w}}F_{k}(\mathbf{w};S_{k})$, then

$\mathbb{E}[\|\bar{\mathbf{w}}_{k}-\hat{\mathbf{w}}_{k}\|_{2}^{2}]=\mathcal{O}\big{(}G^{2}\zeta_{k}^{2}n_{k}\big{)}.$

###### Proof.

Note that $F_{k}$ is $\alpha_{k}=\frac{2}{\zeta_{k}n_{k}}$-strongly convex, by
the convergence of Algorithm 1 in Theorem 6 Part (b), we know that

$\frac{\alpha_{k}}{2}\mathbb{E}[\|\bar{\mathbf{w}}_{k}-\hat{\mathbf{w}}_{k}\|_{2}^{2}]\leq\mathbb{E}[F_{k}(\bar{\mathbf{w}}_{k};S_{k})-F_{k}(\hat{\mathbf{w}}_{k};S_{k})]=\mathcal{O}\Big{(}\frac{G^{2}}{\alpha_{k}n_{k}}\Big{)}$

which implies

$\mathbb{E}[\|\bar{\mathbf{w}}_{k}-\hat{\mathbf{w}}_{k}\|_{2}^{2}]=\mathcal{O}\big{(}G^{2}\zeta_{k}^{2}n_{k}\big{)}.$

The proof is completed. ∎

######  Lemma 9.

Let (A1) and (A3) hold true with $\alpha=0$. For any
$\mathbf{w}\in\mathcal{W}$, we know that

$\mathbb{E}[F(\hat{\mathbf{w}}_{k})-F(\mathbf{w})]\leq\frac{\mathbb{E}[\|\bar{\mathbf{w}}_{k-1}-\mathbf{w}\|_{2}^{2}]}{\zeta_{k}n_{k}}+2G^{2}\zeta_{k}.$

###### Proof.

Let
$r(\mathbf{w};\mathbf{z},\mathbf{z}^{\prime})=f(\mathbf{w},\mathbf{z},\mathbf{z}^{\prime})+\frac{1}{\zeta_{k}n_{k}}\|\mathbf{w}-\bar{\mathbf{w}}_{k-1}\|_{2}^{2},R(\mathbf{w})=\mathbb{E}_{\mathbf{z},\mathbf{z}^{\prime}}[r(\mathbf{w};\mathbf{z},\mathbf{z}^{\prime})]$
and $\mathbf{w}_{R}^{*}=\arg\min_{\mathbf{w}\in\mathcal{W}}R(\mathbf{w})$. By
the proof of Theorem 6 in Shalev-Shwartz et al. [33] , one has that

$\displaystyle\mathbb{E}[F(\hat{\mathbf{w}}_{k})+\frac{1}{\zeta_{k}n_{k}}\|\hat{\mathbf{w}}_{k}-\bar{\mathbf{w}}_{k-1}\|_{2}^{2}-F(\mathbf{w})-\frac{1}{\zeta_{k}n_{k}}\|\mathbf{w}-\bar{\mathbf{w}}_{k-1}\|_{2}^{2}]$
$\displaystyle=\mathbb{E}[R(\hat{\mathbf{w}}_{k})-R(\mathbf{w})]\leq\mathbb{E}[R(\hat{\mathbf{w}}_{k})-R(\mathbf{w}_{R}^{*})]\leq
2G^{2}\zeta_{k},$

which implies that

$\displaystyle\mathbb{E}[F(\hat{\mathbf{w}}_{k})-F(\mathbf{w})]\leq$
$\displaystyle
2G^{2}\zeta_{k}-\frac{1}{\zeta_{k}n_{k}}\mathbb{E}[\|\hat{\mathbf{w}}_{k}-\bar{\mathbf{w}}_{k-1}\|_{2}^{2}]+\frac{1}{\zeta_{k}n_{k}}\mathbb{E}[\|\mathbf{w}-\bar{\mathbf{w}}_{k-1}\|_{2}^{2}]$
$\displaystyle\leq$ $\displaystyle
2G^{2}\zeta_{k}+\frac{1}{\zeta_{k}n_{k}}\mathbb{E}[\|\mathbf{w}-\bar{\mathbf{w}}_{k-1}\|_{2}^{2}].$

The proof is completed. ∎

###### Proof of Theorem E.1.

Let $\hat{\mathbf{w}}_{0}=\mathbf{w}^{*}$, we have

$\displaystyle\mathbb{E}[F(\bar{\mathbf{w}}_{K})]-F(\mathbf{w}^{*})=\sum_{k=1}^{K}\mathbb{E}[F(\hat{\mathbf{w}}_{k})-F(\hat{\mathbf{w}}_{k-1})]+\mathbb{E}[F(\bar{\mathbf{w}}_{K})-F(\hat{\mathbf{w}}_{K})].$
(E.1)

For the first term we have

$\displaystyle\sum_{k=1}^{K}\mathbb{E}[F(\hat{\mathbf{w}}_{k})-F(\hat{\mathbf{w}}_{k-1})]\leq$
$\displaystyle\sum_{k=1}^{K}\Big{(}\frac{\mathbb{E}[\|\bar{\mathbf{w}}_{k-1}-\hat{\mathbf{w}}_{k-1}\|_{2}^{2}]}{\zeta_{k}n_{k}}+2G^{2}\zeta_{k}\Big{)}$
$\displaystyle=$ $\displaystyle\mathcal{O}\Big{(}\frac{D^{2}}{\zeta
n}+\sum_{k=2}^{K}G^{2}\zeta_{k}+\sum_{k=1}^{K}2^{-k}G^{2}\zeta\Big{)}$
$\displaystyle=$ $\displaystyle\mathcal{O}\Big{(}\frac{D^{2}}{\zeta
n}+G^{2}\zeta\Big{)}$ (E.2)

where the first inequality is by Lemma 9, the second inequality is by Lemma 8
and $\zeta=\frac{D}{G\sqrt{n}}$. For the second term we have

$\displaystyle\mathbb{E}[F(\bar{\mathbf{w}}_{K})-F(\hat{\mathbf{w}}_{K})]\leq$
$\displaystyle
G\mathbb{E}[\|\bar{\mathbf{w}}_{K}-\hat{\mathbf{w}}_{K}\|_{2}]\leq
G\sqrt{\mathbb{E}[\|\bar{\mathbf{w}}_{K}-\hat{\mathbf{w}}_{K}\|_{2}^{2}]}=\mathcal{O}\big{(}G^{2}\zeta_{K}\sqrt{n_{K}}\big{)}$
$\displaystyle=$
$\displaystyle\mathcal{O}\Big{(}2^{-2K}G^{2}\zeta\sqrt{n}\Big{)}=\mathcal{O}\Big{(}G^{2}\zeta\Big{)}$
(E.3)

where the first inequality is by $G$-Lipschitz continuity of $F$, the second
inequality is by Jensen’s inequality, the first identity is by Lemma 8 and the
second identity is by $n_{k}=2^{-k}n$.

Now putting (E) and (E) back to (E.1) and using $\zeta=\frac{D}{G\sqrt{n}}$,
we derive

$\mathbb{E}[F(\bar{\mathbf{w}}_{K})]-F(\mathbf{w}^{*})=\mathcal{O}\Big{(}\frac{GD}{\sqrt{n}}\Big{)}.$

Finally we investigate the gradient complexity. Since $F_{k}$ is
$\frac{2}{\zeta_{k}n_{k}}$-strongly convex, by Theorem 6 Part (b), we need to
choose $T_{k}\asymp n_{k}$ so that Lemma 8 holds. Therefore, in total, we
require $\mathcal{O}\Big{(}\sum_{k=1}^{K}n_{k}\Big{)}=\mathcal{O}(n)$ gradient
complexity, which yields the desired result. ∎

##  Appendix F Additional Results: Differentially Private SGD for Pairwise
Learning with Non-Smooth Losses

In this section, we propose a differentially private algorithm based on
iterative localization [13] for nonsmooth pairwise learning problems. The
algorithm is presented as follows.

Algorithm 5 Differentially Private Localized SGD for Pairwise Learning

1: Inputs: Dataset $S=\\{\mathbf{z}_{i}:i\in[n]\\}$, parameters
$\epsilon,\delta$, and $\zeta$, initial points $\mathbf{w}_{0}$

2: Set $K\\!=\\!\lceil\log_{2}n\rceil$ and divide $S$ into $K$ disjoint
subsets $\\{S_{1},\cdots,S_{K}\\}$ where $|S_{k}|\\!=\\!n_{k}\\!=\\!2^{-k}n$.

3: for $k=1$ to $K$ do

4: Set $\zeta_{k}=4^{-k}\zeta$

5: Compute $\bar{\mathbf{w}}_{k}\in\mathcal{W}$ by Algorithm 1 with step sizes
$\eta_{j}=\frac{\zeta_{k}n_{k}}{j+1}$ on objective $F_{k}$ such that with prob
$1-\delta$,
$F_{k}(\bar{\mathbf{w}}_{k};S_{k})-\min_{\mathbf{w}\in\mathcal{W}}F_{k}(\mathbf{w};S_{k})\leq
G^{2}\zeta_{k}/n_{k}$ where
$F_{k}(\mathbf{w};S_{k})=\frac{1}{n_{k}(n_{k}-1)}\sum_{z,z^{\prime}\in
S_{k}:z\neq
z^{\prime}}f(\mathbf{w};z,z^{\prime})+\frac{1}{\zeta_{k}n_{k}}\|\mathbf{w}-\mathbf{w}_{k-1}\|_{2}^{2}$

6: Set $\mathbf{w}_{k}=\bar{\mathbf{w}}_{k}+\mathbf{u}_{k}$ where
$\mathbf{u}_{k}\sim\mathcal{N}(0,\alpha_{k}^{2}I_{d})$ with
$\sigma_{k}=4G\zeta_{k}\sqrt{\log(2.5/\delta)}/\epsilon$.

7: Outputs: $\mathbf{w}_{K}$

We are now ready to present the privacy guarantee and utility bound of
Algorithm 5 in the following theorem. The proof differs from the iterative
localization algorithm in pointwise learning [13] since we employ our high
probability convergence results for non-smooth losses in pairwise learning.

######  Theorem F.1.

Let (A1) and (A3) hold true with $\alpha=0$ and let $D$ be the diameter of
$\mathcal{W}$. Let $\\{\mathbf{w}_{k}:k\in[K]\\}$ be produced by Algorithm 5
with
$\zeta=\frac{D}{G}\min\\{\frac{4}{\sqrt{n}},\frac{\epsilon}{4\sqrt{d\log(1/\delta)}}\\}$.
Then Algorithm 5 satisfies $(\epsilon,\delta)$-DP. Furthermore we have the
following excess generalization error bounds

$\mathbb{E}[F(\mathbf{w}_{K})-F(\mathbf{w}^{*})]=\mathcal{O}\Big{(}GD\Big{(}\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log(1/\delta)}}{\epsilon
n}\Big{)}\Big{)}$

with no more than $\mathcal{O}(n^{2}\log(1/\delta))$ stochastic gradient
computations.

###### Proof of Theorem F.1.

We first consider the privacy guarantee of Algorithm 5. For any neighboring
datasets $S=\\{S_{1},\ldots,S_{K}\\}$ and
$S^{\prime}=\\{S^{\prime}_{1},\ldots,S^{\prime}_{K}\\}$ differing by one
example, where $S^{\prime}$ follows the same partition as $S$, and $S_{i}\cap
S_{j}=\emptyset$ if $i\neq j$. Let
$\hat{\mathbf{w}}_{k}=\arg\min_{\mathbf{w}}F_{k}(\mathbf{w};S_{k})$ and
$\hat{\mathbf{w}}^{\prime}_{k}=\arg\min_{\mathbf{w}}F_{k}(\mathbf{w};S^{\prime}_{k})$.
We first investigate the $\ell_{2}$-sensitivity of $\hat{\mathbf{w}}_{k}$.
Since $F_{k}$ is $\alpha_{k}=\frac{2}{\zeta_{k}n_{k}}$-strongly convex, by
Theorem 6 in Shalev-Shwartz et al. [33] we have

$\|\hat{\mathbf{w}}_{k}-\hat{\mathbf{w}}^{\prime}_{k}\|_{2}\leq\frac{4G}{\alpha_{k}n_{k}}=2G\zeta_{k},$

where $\bar{\mathbf{w}}^{\prime}_{k}$ is the return from Line 5 in Algorithm 5
based on $F_{k}(\mathbf{w};S_{k}^{\prime})$. By the strong convexity of
$F_{k}$ again, we have with probability at least $1-\delta$

$\frac{\alpha_{k}}{2}\|\bar{\mathbf{w}}_{k}-\hat{\mathbf{w}}_{k}\|_{2}^{2}\leq
F_{k}(\bar{\mathbf{w}}_{k};S_{k})-F_{k}(\hat{\mathbf{w}}_{k};S_{k})\leq\frac{G^{2}\zeta_{k}}{n_{k}}$

which implies $\|\bar{\mathbf{w}}_{k}-\hat{\mathbf{w}}_{k}\|_{2}\leq
G\zeta_{k}$. This further implies $\bar{\mathbf{w}}_{k}$ has
$\ell_{2}$-sensitivity of $4G\zeta_{k}$ with probability $1-\delta$.
Therefore, by Lemma 5, each iteration $k$ of Algorithm 5 is
$(\epsilon,\delta)$-DP. Since the partition of the dataset $S$ is disjoint,
and each iteration $k$ of Algorithm 5 we only use one subset, thus the whole
process will still be $(\epsilon,\delta)$-DP.

Next we investigate the utility bound of Algorithm 5. Firstly, for any fixed
$\mathbf{w}$,

$\displaystyle\mathbb{E}[F(\bar{\mathbf{w}}_{k})-F(\mathbf{w})]=$
$\displaystyle\mathbb{E}[F(\hat{\mathbf{w}}_{k})-F(\mathbf{w})]+\mathbb{E}[F(\bar{\mathbf{w}}_{k})-F(\hat{\mathbf{w}}_{k})]$
$\displaystyle\leq$
$\displaystyle\frac{\mathbb{E}[\|\mathbf{w}_{k-1}-\mathbf{w}\|_{2}^{2}]}{\zeta_{k}n_{k}}+3G^{2}\zeta_{k}$

where we used Lemma 9 and
$\|\bar{\mathbf{w}}_{k}-\hat{\mathbf{w}}_{k}\|_{2}\leq G\zeta_{k}$. Denote
$\bar{\mathbf{w}}_{0}=\mathbf{w}^{*}$ and
$\mathbf{u}_{0}=\mathbf{w}_{0}-\mathbf{w}^{*}$, we have

$\displaystyle\mathbb{E}[F(\mathbf{w}_{K})-F(\mathbf{w}^{*})]=$
$\displaystyle\sum_{k=1}^{K}\mathbb{E}[F(\bar{\mathbf{w}}_{k})-F(\bar{\mathbf{w}}_{k-1})]+\mathbb{E}[F(\mathbf{w}_{K})-F(\bar{\mathbf{w}}_{K})]$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\Big{(}\frac{\mathbb{E}[\|\mathbf{u}_{k-1}\|_{2}^{2}]}{\zeta_{k}n_{k}}+3G^{2}\zeta_{k}\Big{)}+G\mathbb{E}[\|\mathbf{u}_{K}\|_{2}].$
(F.1)

Recall that by definition
$\zeta\leq\frac{D\epsilon}{4G\sqrt{d\log(2.5/\delta)}}$, so that for all
$k\geq 0$, there holds

$\mathbb{E}[\|\mathbf{u}_{k}\|_{2}^{2}]=d\sigma_{k}^{2}=d\Big{(}\frac{4^{-k}G\zeta}{\epsilon}\Big{)}^{2}\leq
16^{-k}D^{2}.$

Plugging the above estimate into (F) it follows

$\displaystyle\mathbb{E}[F(\mathbf{w}_{K})-F(\mathbf{w}^{*})]\leq$
$\displaystyle\sum_{k=1}^{K}2^{-k}\Big{(}\frac{8D^{2}}{\zeta
n}+3G^{2}\zeta\Big{)}+4^{-K}GD$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}2^{-k}GD\Big{(}\frac{8}{n}\max\Big{\\{}\sqrt{n},\frac{\sqrt{d\log(1/\delta)}}{\epsilon}\Big{\\}}+\frac{1}{2\sqrt{n}}\Big{)}+\frac{GD}{n^{2}}$
$\displaystyle\leq$ $\displaystyle
9GD\Big{(}\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log(1/\delta)}}{n\epsilon}\Big{)}+\frac{GD}{n^{2}}.$

This yields the desired utility bound.

Finally, we investigate the gradient complexity argument. Since $F_{k}$ is
$\frac{2}{\zeta_{k}n_{k}}$-strongly convex. We know from Theorem 7 Part (b),
after $T_{k}\asymp n_{k}^{2}\log(1/\delta)$ iterations, we have with
probability $1-\delta$

$F_{k}(\bar{\mathbf{w}}_{k};S_{k})-\min_{\mathbf{w}}F_{k}(\mathbf{w};S_{k})=\mathcal{O}\Big{(}\frac{G^{2}\zeta_{k}n_{k}\log(1/\delta)}{n_{k}^{2}\log(1/\delta)}\Big{)}=\mathcal{O}\Big{(}\frac{G^{2}\zeta_{k}}{n_{k}}\Big{)}$

which satisfies the requirement at Line 5 of Algorithm 5. Therefore, in total
the gradient complexity is of the form
$\mathcal{O}\Big{(}\sum_{k=1}^{K}n_{k}^{2}\log(1/\delta)\Big{)}=\mathcal{O}\big{(}n^{2}\log(1/\delta)\big{)}.$
The proof is completed. ∎

##  Appendix G Additional Experiments

In this section, we provide the experimental details and additional
experiments to support our theoretical findings. The datasets we used are from
LIBSVM website [9]. The statistics of the data is included in Table G.1. For
data with multiple classes, we convert the first half of class numbers to be
the positive class and the second half of class numbers to be the negative
class.

Table G.1: Data Statistics. $n$ is the number of samples and $d$ is the number of features. | diabtes | german | ijcnn1 | letter | mnist | usps
---|---|---|---|---|---|---
n | 768 | 1,000 | 49,990 | 15,000 | 60,000 | 7,291
d | 8 | 24 | 22 | 161 | 780 | 256
Table G.2: Average AUC score $\pm$ standard deviation across multiple datasets. Our best results are highlighted in bold. Algorithm | diabetes | german | ijcnn1 | letter | mnist | usps
---|---|---|---|---|---|---
Our | $.831\pm.030$ | $.793\pm.021$ | $.934\pm.002$ | $.810\pm.007$ | $.932\pm.001$ | $.926\pm.006$
$\texttt{SGD}_{pair}$ [27] | $.830\pm.028$ | $.794\pm.023$ | $.934\pm.003$ | $.811\pm.008$ | $.932\pm.001$ | $.925\pm.006$
OLP [22] | $.825\pm.028$ | $.787\pm.028$ | $.916\pm.003$ | $.808\pm.010$ | $.927\pm.003$ | $.917\pm.006$
$\texttt{OAM}_{gra}$ [48] | $.828\pm.026$ | $.785\pm.029$ | $.930\pm.003$ | $.806\pm.008$ | $.898\pm.002$ | $.916\pm.005$
OLP-RS1 | $.736\pm.074$ | $.630\pm.065$ | $.668\pm.026$ | $.683\pm.033$ | $.749\pm.045$ | $.737\pm.056$
OAM-RS1 | $.737\pm.069$ | $.640\pm.058$ | $.677\pm.014$ | $.675\pm.050$ | $.685\pm.042$ | $.691\pm.059$
SPAUC [26] | $.828\pm.031$ | $.799\pm.026$ | $.932\pm.002$ | $.809\pm.008$ | $.927\pm.002$ | $.923\pm.005$

For each dataset, we have used $80\%$ of the data for training and the
remaining $20\%$ for testing. The results are based on 25 runs of random
shuffling. The generalization performance is reported using the average AUC
score and standard deviation on the test data. To determine proper hyper
parameters, we conduct 5-fold cross validation on the training sets: 1) for
Algorithm 1 and $\texttt{SGD}_{pair}$, we select step sizes $\eta_{t}=\eta\in
10^{[-3:3]}$ and $\mathcal{W}$ diameter $D\in 10^{[-3:3]}$; 2) for OLP we
select step sizes $\eta_{t}=\eta/\sqrt{t}$ where $\eta\in 10^{[-3:3]}$ and
$\mathcal{W}$ diameter $D\in 10^{[-3:3]}$; 3) for $\texttt{OAM}_{gra}$ we
select learning rate parameter $C\in 10^{[-3:3]}$; 4) for SPAUC we select step
sizes $\eta_{t}=\eta/\sqrt{t}$ where $\eta\in 10^{[-3:3]}$.

Firstly, Table G.2 summarizes the generalization performance of different
algorithms which contains more comparison results than Table 1. In particular,
two additional results are added for comparison, i.e. OLP-RS1 and OAM-RS1
which denote the OLP [22] and $\texttt{OAM}_{gra}$ [48] with Reservoir
sampling and the buffering set size $s=1$, respectively. We can see that OLP-
RS1 and OAM-RS1 are inferior to other algorithms. This inferior performance
for OLP and OAM with a small buffering set was also observed in the
experiments of [22, 48].

Figure G.1: More CPU running time against AUC score for the hinge loss

Secondly, we also report more plots on CPU running time against the AUC score
on different datasets. Figure G.1 contains more convergence plots for the
hinge loss. For a fair comparison of Algorithm 1 with SPAUC, the loss function
is chosen as the least square loss for Algorithm 1, $\texttt{SGD}_{pair}$ and
OLP. The results are shown in Figure G.2. We can see there that SPAUC performs
very well among most of the datasets. However, this algorithm was designed
very specifically for the AUC maximization problem with the least square loss
while our algorithm can handle any loss functions and any pairwise learning
problems. We can also observe that our algorithm and $\texttt{SGD}_{pair}$
converge in a similar CPU running time. In fact, Algorithm 1 is slightly
faster than $\texttt{SGD}_{pair}$ when the number of samples gets larger. This
is partly due to different sampling schemes in Algorithm 1 and
$\texttt{SGD}_{pair}$. Indeed, at each iteration $\texttt{SGD}_{pair}$ picks a
random pair of examples from $\binom{n}{2}$ pairs, while Algorithm 1 only
needs to randomly pick one example from $n$ individual ones. Figure G.3
depicts the CPU times of these two sampling schemes versus the the number of
examples $n$. We can see that, when the sample size $n$ increases, the
sampling scheme used in $\texttt{SGD}_{pair}$ needs significantly more time
than our algorithm.

Figure G.2: AUC score against CPU running time for the square loss Figure G.3:
CPU running time of different sampling schemes against the sample size $n$

Figure G.4: Convergence of Algorithm 1 for the generalized linear model

Next, we investigate our Algorithm 1 in the non-convex setting. To this end,
we use the logistic link function $\text{logit}(t)=(1+\exp(-t))^{-1}$ and then
the square loss surrogate function $\ell(t)=(1-t)^{2}.$ That is, the loss
function for the problem of AUC maximization becomes
$f(\mathbf{w};(\mathbf{x},y),(\mathbf{x}^{\prime},y^{\prime}))=(1-\text{logit}(\mathbf{w}^{\top}(\mathbf{x}-\mathbf{x}^{\prime}))^{2}\mathbb{I}_{[y=1\wedge
y^{\prime}=-1]}$. Although $f$ is non-convex, it was shown that it satisfies
the PL condition [14]. The results are reported in Figure G.4 which shows that
Algorithm 1 also converges very quickly in this non-convex setting.

Finally, we compare our differentially private algorithm for AUC maximization
(i.e. Algorithm 3) with the logistic loss $\ell(t)=\log(1+\exp(-t))$ against
the state-of-art algorithm DPEGD [42]. DPEGD used gradient descent and the
localization technique to guarantee privacy. Algorithm 1 was used as non-
private baseline, i.e. $\epsilon=0$. Here, $\delta=\frac{1}{n}$ as suggested
in the previous work [42]. We consider the effect of different privacy budget
$\epsilon$’s against the generalization ability. The implementation across all
algorithms is based on fixed training size $256$. Average AUC scores over $25$
times repeated experiments are listed in Table G.3 and G.4 for the datasets of
diabetes and german, respectively. These results demonstrate Algorithm 3
achieves competitive performance with DPEGD using full gradient descent.

Table G.3: Average AUC $\pm$ standard deviation on diabetes. Non-Private result is $.813\pm.016$. Algorithm | $\epsilon=0.2$ | $\epsilon=0.5$ | $\epsilon=0.8$ | $\epsilon=1.0$ | $\epsilon=1.5$ | $\epsilon=2.0$
---|---|---|---|---|---|---
Our | $.690\pm.094$ | $.751\pm.028$ | $.771\pm.016$ | $.783\pm.024$ | $.784\pm.018$ | $.789\pm.018$
DPEGD [42] | $.624\pm.109$ | $.727\pm.055$ | $.768\pm.027$ | $.796\pm.011$ | $.797\pm.017$ | $.792\pm.016$
Table G.4: Average AUC $\pm$ standard deviation on german. Non-Private result is $.763\pm.016$. Algorithm | $\epsilon=0.2$ | $\epsilon=0.5$ | $\epsilon=0.8$ | $\epsilon=1.0$ | $\epsilon=1.5$ | $\epsilon=2.0$
---|---|---|---|---|---|---
Our | $.614\pm.035$ | $.672\pm.064$ | $.721\pm.024$ | $.725\pm.032$ | $.747\pm.019$ | $.749\pm.021$
DPEGD [42] | $.598\pm.018$ | $.703\pm.039$ | $.723\pm.029$ | $.742\pm.028$ | $.753\pm.017$ | $.757\pm.018$

We also report the CPU running times of Algorithm 3 and $\texttt{DPEGD}.$ In
this setting, we fix the privacy budget $\epsilon=1$ and vary the training
size $n$. The results are reported in Table G.5. These results shows that
Algorithm 3 can arrive competitive performance with DPEGD with less CPU
running time.

Table G.5: Average AUC score and average CPU running time $\pm$ standard deviation. Algorithm |  | diabetes | german
---|---|---|---
| $n=100$ | $n=200$ | $n=300$ | $n=100$ | $n=200$ | $n=300$
Our | AUC | $.709\pm.051$ | $.788\pm.019$ | $.790\pm.021$ | $.681\pm.029$ | $.692\pm.032$ | $.734\pm.022$
Time | $.046\pm.010$ | $.096\pm.019$ | $.135\pm.026$ | $.377\pm.097$ | $.637\pm.136$ | $.767\pm.151$
DPEGD [42] | AUC | $.705\pm.070$ | $.772\pm.017$ | $.777\pm.023$ | $.687\pm.033$ | $.700\pm.038$ | $.755\pm.019$
Time | $.421\pm.067$ | $.885\pm.158$ | $1.41\pm.248$ | $1.00\pm.185$ | $1.88\pm.273$ | $2.57\pm.421$