# Stability and Generalization for Randomized Coordinate Descent111To appear
in IJCAI 2021

Puyu Wang1 Liang Wu2&Yunwen Lei3 1School of Mathematics, Northwest University,
Xi’an 710127, China
2Center of Statistical Research, School of Statistics, Southwestern University
of Finance and Economics, Chengdu 611130, China
3School of Computer Science, University of Birmingham, Birmingham B15 2TT, UK
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Randomized coordinate descent (RCD) is a popular optimization algorithm with
wide applications in solving various machine learning problems, which
motivates a lot of theoretical analysis on its convergence behavior. As a
comparison, there is no work studying how the models trained by RCD would
generalize to test examples. In this paper, we initialize the generalization
analysis of RCD by leveraging the powerful tool of algorithmic stability. We
establish argument stability bounds of RCD for both convex and strongly convex
objectives, from which we develop optimal generalization bounds by showing how
to early-stop the algorithm to tradeoff the estimation and optimization. Our
analysis shows that RCD enjoys better stability as compared to stochastic
gradient descent.

##  1 Introduction

Randomized coordinate descent (RCD) is a popular method for solving large-
scale optimization problems which are ubiquitous in the big-data era
(Nesterov, 2012; Richtárik and Takáč, 2014, 2016). As an iterative algorithm,
it iteratively updates a single randomly chosen coordinate along the negative
direction of the derivative while keeping the other coordinates fixed. Due to
its ease of implementation and high efficiency, RCD has found wide
applications in various areas such as compressed sensing, network problems and
optimization (Richtárik and Takáč, 2014). In particular, the conceptual and
algorithmic simplicity makes it especially useful for large-scale problems for
which even the simplest full-dimensional vector operations are very expensive
(Nesterov, 2012).

The popularity of RCD motivates a lot of theoretical analysis to understand
its empirical behavior. Specifically, iteration complexities of RCD are well
studied in the literature under different settings (e.g., convex/strongly
convex (Nesterov, 2012), smooth/nonsmooth cases (Richtárik and Takáč, 2014,
2016; Lu and Xiao, 2015)) for different variants (e.g., distributed RCD
(Richtárik and Takáč, 2016), accelerated RCD (Nesterov, 2012; Ren and Zhu,
2017; Gu et al., 2018; Li and Lin, 2020; Chen and Gu, 2016), RCD for primal-
dual problems (Qu et al., 2016) and RCD for saddle problems (Zhu and Storkey,
2016)). These discussions concern how the empirical risks of the models
trained by RCD would decay along the optimization process. As a comparison,
there is little analysis on how these models would behave on testing examples,
which is what really matters in machine learning. Actually, if the models are
very complicated, it is very likely that the models would admit a small
empirical risk or even interpolate the training examples but meanwhile suffer
from a large test error. This discrepancy between training and testing, as
referred to as overfitting, is a fundamental problem in machine learning
(Bousquet and Elisseeff, 2002). The existing convergence rate analysis of RCD
is not enough to fully understand why the models trained by RCD have a good
prediction performance in real applications. In particular, it is not clear
how the optimization and statistical behavior of RCD would change along the
optimization process, which is useful for designing efficient models in
practice. For example, generalization analysis provides a principled guideline
on how to stop the algorithm appropriately for a best generalization.

In this paper, we aim to bridge the generalization and optimization of RCD by
leveraging the celebrated concept of algorithmic stability. We establish
stability bounds of RCD as measured by several concepts, including
$\ell_{1}$-argument stability, $\ell_{2}$-argument stability and uniform
stability. Under standard assumptions on smoothness, Lipschitz continuity and
convexity of objective functions, we show clearly how the stability and the
optimization error would behave along the learning process. This suggests a
principled way to early-stop the algorithm to get a best generalization
behavior. We consider convex, strongly convex and nonconvex objective
functions. In the convex and strongly convex cases, we develop minimax optimal
generalization bounds of the order $O(1/\sqrt{n})$ and $O(1/n)$ respectively,
where $n$ is the sample size. Our analysis not only suggests that RCD has a
better stability than stochastic gradient descent (SGD), but also is able to
exploit a low noise condition to get an optimistic bound $O(1/n)$ in the
convex case. Finally, we develop generalization bounds with high probability
which are useful to understand the robustness and variation of the training
algorithm (Feldman and Vondrak, 2019).

##  2 Related Work

###  2.1 Randomized Coordinate Descent

RCD was widely used to solve large-scale optimization problems in machine
learning, including linear SVMs (Chang et al., 2008), $\ell_{1}$-regularized
models for sparse learning (Shalev-Shwartz and Tewari, 2009) and low-rank
matrix learning (Hu and Kwok, 2019). The convergence rate of RCD and its
accelerated variant were studied in the seminal work (Nesterov, 2012), where
the advantage of RCD over deterministic algorithms is clearly illustrated.
These results were extended to structure optimization problems where the
objective function consists of a smooth data-fitting term and a nonsmooth
regularizer (Richtárik and Takáč, 2014; Lu and Xiao, 2015). RCD was also
adapted to distributed data analysis(Richtárik and Takáč, 2016; Sun et al.,
2017; Xiao et al., 2019), primal-dual optimization (Qu et al., 2016) and
privacy-preserving problems (Damaskinos et al., 2020). All these discussions
consider the convergence rate of optimization errors for RCD. As a comparison,
we are interested in the generalization behavior of models trained by RCD,
which is the ultimate goal in machine learning.

###  2.2 Stability and Generalization

We now review the related work on algorithmic stability and its application on
generalization analysis. The framework of algorithmic stability was
established in a seminal paper (Bousquet and Elisseeff, 2002), where the
important uniform stability was introduced. This algorithmic stability was
extended to study randomized algorithms in Elisseeff et al. (2005). Other than
uniform stability, several other stability measures including hypothesis
stability (Bousquet and Elisseeff, 2002), on-average stability (Shalev-Shwartz
et al., 2010) and argument stability (Liu et al., 2017) have been introduced
in statistical learning theory, whose connection to learnability has been
established (Mukherjee and Zhou, 2006; Shalev-Shwartz et al., 2010). The
uniform stability of stochastic gradient descent (SGD) was established for
learning with (strongly) convex, smooth and Lipschitz loss functions (Hardt et
al., 2016). This motivates the recent work of studying generalization of
stochastic optimization algorithms via several stability (Meng et al., 2017;
Charles and Papailiopoulos, 2018; Kuzborskij and Lampert, 2018; Yin et al.,
2018; Yuan et al., 2019; Lei and Ying, 2020; Bassily et al., 2020; Lei et al.,
2020; Lei and Ying, 2021; Wang et al., 2021; Yang et al., 2021). For example,
an on-average model stability (Lei and Ying, 2020) has been proposed to remove
the smoothness assumption or Lipschitz continuity assumption in Hardt et al.
(2016). Recently, elegant concentration inequalities have been developed to
get high-probability bounds via uniform stability (Feldman and Vondrak, 2019;
Bousquet et al., 2020). To our best knowledge, the algorithmic stability of
RCD has not been studied yet, which is the topic of this paper.

##  3 Problem Formulation

Let $\rho$ be a probability measure defined over a sample space
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$ is an input
space and $\mathcal{Y}\subset\mathbb{R}$ is an output space. We aim to build a
parametric model $h_{\mathbf{w}}:\mathcal{X}\mapsto\mathbb{R}$, where
$\mathbf{w}$ is the model parameter which belongs to the parameter space
$\mathcal{W}\subseteq\mathbb{R}^{d}$. The performance of the model
$h_{\mathbf{w}}$ on a single example $z$ can be measured by a nonnegative loss
function $f(\mathbf{w};z)$. The quality of a model can be quantified by a
population risk $F(\mathbf{w})=\mathbb{E}_{z}[f(\mathbf{w};z)]$, where
$\mathbb{E}_{z}$ denotes the expectation w.r.t. $z$. We wish to approximate
the best model
$\mathbf{w}^{*}\in\arg\min_{\mathbf{w}\in\mathcal{W}}F(\mathbf{w})$. However,
the probability measure is often unknown and we only have access to a training
sample $S=\\{z_{1},z_{2},\ldots,z_{n}\\}$ drawn independently from $\rho$. The
empirical behavior of $h_{\mathbf{w}}$ on $S$ can be measured by a empirical
risk $F_{S}(\mathbf{w})=\frac{1}{n}\sum_{i=1}^{n}f(\mathbf{w};z_{i})$.

Notations. For any $\mathbf{x}\in\mathbb{R}^{d}$, we denote the norm
$\|\mathbf{x}\|_{p}=\big{(}\sum_{i=1}^{d}|\mathbf{x}_{i}|^{p}\big{)}^{1/p}$
for $p\geq 1$. For any $m\in\mathbb{N}$, we use the notation
$[m]:=\\{1,\ldots,m\\}$. And we use the notation $B=O(\tilde{B})$ if there
exists a constant $c_{0}>0$ such that $B\leq c_{0}\tilde{B}$, and use
$B\asymp\widetilde{B}$ if there exist constants $c_{1},c_{2}>0$ such that
$c_{1}\widetilde{B}<B\leq c_{2}\widetilde{B}$. We say
$g:\mathcal{W}\mapsto\mathbb{R}$ is $L$-smooth if $\|\nabla
g(\mathbf{w})-\nabla g(\mathbf{w}^{\prime})\|_{2}\leq
L\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}$ for all
$\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{W}$.

We apply a randomized algorithm $A$ to the sample $S$ and get an output model
$A(S)\in\mathcal{W}$. We are interested in studying the excess generalization
error $F(A(S))-F(\mathbf{w}^{*})$. Since
$\mathbb{E}[F_{S}(\mathbf{w}^{*})]=F(\mathbf{w}^{*})$, we can decompose the
excess generalization error by

$\displaystyle\mathbb{E}_{S,A}\big{[}F(A(S))\\!-$
$\displaystyle\\!F(\mathbf{w}^{*})\big{]}\\!=\\!\mathbb{E}_{S,A}\big{[}F(A(S))\\!-\\!F_{S}(A(S))\big{]}$
$\displaystyle+\mathbb{E}_{S,A}\big{[}F_{S}(A(S))-F_{S}(\mathbf{w}^{*})\big{]}.$
(1)

We refer to the first term $\mathbb{E}_{S,A}\big{[}F(A(S))-F_{S}(A(S))\big{]}$
as the estimation error, and the second term
$\mathbb{E}_{S,A}\big{[}F_{S}(A(S))-F_{S}(\mathbf{w}^{*})\big{]}$ as the
optimization error. A standard approach to control estimation error is to
study the algorithmic stability of the algorithm $A$, i.e., how the model
would change if we change the training sample by a single example. There are
several variants of stability measures including the uniform stability,
hypothesis stability, on-average stability and argument stability (Bousquet
and Elisseeff, 2002; Hardt et al., 2016; Elisseeff et al., 2005), among which
the uniform stability is the most popular one.

######  Definition 1 (Uniform Stability).

A randomized algorithm $A$ is $\epsilon$-uniformly stable if for all training
datasets $S,\widetilde{S}\in\mathcal{Z}^{n}$ that differ by at most one
example, we have

$\sup_{z}\big{[}f(A(S);z)-f(A(\widetilde{S});z)\big{]}\leq\epsilon.$

In this paper we consider the on-average argument/model stability (Lei and
Ying, 2020), an advantage of which is that it can imply better generalization
bounds without a Lipschitz continuity assumption on loss functions.

######  Definition 2 (On-average Argument Stability).

Let $S=\\{z_{1},\ldots,z_{n}\\}$ and
$S^{\prime}=\\{z^{\prime}_{1},\ldots,z^{\prime}_{n}\\}$ be drawn independently
from $\rho$. For any $i=1,\ldots,n$, define
$S^{(i)}=\\{z_{1},\ldots,z_{i-1},z_{i}^{\prime},z_{i+1},\ldots,z_{n}\\}$ as
the set formed from $S$ by replacing $z_{i}$ with $z_{i}^{\prime}$. We say a
randomized algorithm $A$ is $\ell_{1}$ on-average argument $\epsilon$-stable
if
$\mathbb{E}_{S,S^{\prime},A}\big{[}\frac{1}{n}\sum_{i=1}^{n}\|A(S)-A(S^{(i)})\|_{2}\big{]}\leq\epsilon,$
and $\ell_{2}$ on-average argument $\epsilon$-stable if
$\mathbb{E}_{S,S^{\prime},A}\big{[}\frac{1}{n}\sum_{i=1}^{n}\|A(S)-A(S^{(i)})\|_{2}^{2}\big{]}\leq\epsilon^{2}.$

Lemma 1 (Lei and Ying, 2020) gives a connection between on-average argument
stability and estimation errors. Assumption 1 holds for popular loss functions
including logistic loss and Huber loss.

######  Assumption 1.

Let $G_{1},G_{2}>0$. Assume for all $\mathbf{w}\in\mathcal{W}$ and
$z\in\mathcal{Z}$, $\|\nabla f(\mathbf{w};z)\|_{1}\leq G_{1}$ and $\|\nabla
f(\mathbf{w};z)\|_{2}\leq G_{2}.$

######  Lemma 1 (Generalization via Argument Stability).

Let $S,S^{\prime}$ and $S^{(i)}$ be constructed as Definition 2.

  1. (a)

If Assumption 1 holds, then

$\big{|}\mathbb{E}_{S,A}\big{[}F_{S}(A(S))-F(A(S))\big{]}\big{|}\leq\\\
\frac{G_{2}}{n}\mathbb{E}_{S,S^{\prime},A}\Big{[}\sum_{i=1}^{n}\|A(S)-A(S^{(i)})\|_{2}\Big{]}.$

  2. (b)

If for any $z$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is
nonnegative and $L$-smooth, then for any $\gamma>0$ we have

$\mathbb{E}_{S,A}\big{[}F(A(S))-F_{S}(A(S))\big{]}\leq\frac{1}{\gamma}\mathbb{E}_{S,A}\big{[}F_{S}(A(S))\big{]}\\\
+\frac{L(1+\gamma)}{2n}\sum_{i=1}^{n}\mathbb{E}_{S,S^{\prime},A}\big{[}\|A(S^{(i)})-A(S)\|_{2}^{2}\big{]}.$

In this paper, we consider the specific RCD method widely used in large-scale
learning problems. Let $\mathbf{w}_{1}\in\mathcal{W}$ be the initial point. At
the $t$-th iteration it first randomly selects a single coordinate
$i_{t}\in[d]$, and then performs the update along the $i_{t}$-th coordinate as
(Nesterov, 2012)

$\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}},$
(2)

where $\nabla_{i}g$ denotes the derivative of $g$ w.r.t. the $i$-th coordinate
and $\mathbf{e}_{i}$ is a vector in $\mathbb{R}^{d}$ with the $i$-th
coordinate being $1$ and other coordinates being $0$. Here $\\{\eta_{t}\\}$ is
a nonnegative stepsize sequence. It is clear that RCD sequentially updates a
randomly selected coordinate while keeping others fixed. In this paper, we
consider the update of only a single coordinate per iteration. Our discussions
can be readily extended to randomized block coordinate descent where the
coordinates are partitioned into blocks, and each block of coordinates is
updated per iteration (Nesterov, 2012).

##  4 Stability of RCD

In this section, we present our stability bounds of RCD. To this aim, we first
introduce several standard assumptions (Nesterov, 2012). The first assumption
is the convexity of the empirical risk. Note we do not require the convexity
of each loss function, which is used in the stability analysis of SGD (Hardt
et al., 2016; Kuzborskij and Lampert, 2018).

######  Assumption 2.

For any training dataset set $S$, $F_{S}$ is convex.

Our second assumption is the coordinate-wise smoothness of the empirical risk.

######  Definition 3.

We say a differentiable function $g:\mathcal{W}\mapsto\mathbb{R}$ has
coordinate-wise Lipschitz continuous gradients with parameter
$\widetilde{L}>0$ if the following inequality holds for all
$\alpha\in\mathbb{R},\mathbf{w}\in\mathcal{W},i\in[d]$

$g(\mathbf{w}+\alpha\mathbf{e}_{i})\leq
g(\mathbf{w})+\alpha\nabla_{i}g(\mathbf{w})+\widetilde{L}\alpha^{2}/2.$

######  Assumption 3.

For any training dataset $S$, $F_{S}$ is $L$-smooth and has coordinate-wise
Lipschitz continuous gradients with parameter $\widetilde{L}>0$.

Convex case. Under these assumptions, we establish stability bounds of RCD.
Part (a) of Theorem 2 considers the $\ell_{1}$ on-average argument stability,
while Part (b) considers the $\ell_{2}$ on-average argument stability. The
proof is given in Section 7.

######  Theorem 2.

Let Assumptions 2, 3 hold. Let
$\\{\mathbf{w}_{t}\\},\\{\mathbf{w}_{t}^{(i)}\\}$ be given by (2) with
$\eta_{t}\leq 2/\widetilde{L}$ based on $S$ and $S^{(i)}$, respectively.

  1. (a)

If Assumption 1 holds, then

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S,S^{\prime},A}\Big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}\Big{]}\leq\frac{2G_{1}}{nd}\sum_{k=1}^{t}\eta_{k}.$
(3)

  2. (b)

For any $p>0$ the $\ell_{2}$ on-average argument stability can be bounded by

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}\big{]}\leq\frac{4L(1+1/p)}{n^{2}d}\times\\\
\sum_{j=1}^{t}\big{(}1+p\big{)}^{t-j}\eta_{j}^{2}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{j})+F_{S^{\prime}}(\mathbf{w}_{j})\big{]}.$
(4)

######  Remark 1.

We now compare the above results with the related work. Under Assumptions 1, 2
and 3, it was shown that SGD with $t$ iterations enjoys the $\ell_{1}$
argument stability bound $O(\frac{G_{2}}{n}\sum_{k=1}^{t}\eta_{k})$. Eq. (3)
shows that RCD admits a better stability since there is a $d$ in the
denominator. Note that in the worst case we can choose
$G_{1}\leq\sqrt{d}G_{2}$ for which our stability bounds of RCD are of the
order $O(\frac{G_{2}}{n\sqrt{d}}\sum_{k=1}^{t}\eta_{k})$. A notable property
of Part (b) is that the stability bound (4) does not require the Lipschitz
condition as $\|\nabla f(\mathbf{w};z)\|_{2}\leq G_{2}$, which is widely used
in the existing stability analysis (Hardt et al., 2016; Charles and
Papailiopoulos, 2018; Kuzborskij and Lampert, 2018). Indeed, a key point here
is that we replace the Lipschitz constant $G_{2}$ by empirical/population
risks $F$ and $F_{S}$. Since we are minimizing the empirical risk by RCD, it
is reasonable that $F$ and $F_{S}$ would be small and in this case the
algorithm would be more stable. This gives an intuitive connection between
stability and optimization: a small optimization error is also beneficial to
improve stability.

Strongly convex case. Theorem 2 shows the stability becomes worse as we run
more iterations. In the following theorem, we show the stability can be
further improved if we impose a strong convexity assumption.

######  Assumption 4.

Assume for all $S,i\in[d],\mathbf{w}\in\mathcal{W}$, the function $v\mapsto
F_{S}(\mathbf{w}+v\mathbf{e}_{i})$ is $\sigma$-strongly convex, i.e.,

$F_{S}(\mathbf{w}+v\mathbf{e}_{i})\geq
F_{S}(\mathbf{w}+v^{\prime}\mathbf{e}_{i})+(v-v^{\prime})\nabla_{i}F_{S}(\mathbf{w}+v^{\prime}\mathbf{e}_{i})\\\
+\sigma(v-v^{\prime})^{2}/2,\quad\forall v,v^{\prime}\in\mathbb{R}.$

######  Theorem 3.

Let Assumptions 1, 3, 4 hold. Let
$\\{\mathbf{w}_{t}\\},\\{\mathbf{w}_{t}^{(i)}\\}$ be produced by (2) with
$\eta_{t}\leq 1/\widetilde{L}$ based on $S$ and $S^{(i)}$, respectively. Then
we have

$\mathbb{E}_{A}[\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}]\leq\frac{4G_{1}}{n\sigma}.$
(5)

######  Remark 2.

Stability bounds of the order $O(1/(n\sigma))$ were established for SGD under
a strong convexity assumption (Hardt et al., 2016), which are extended to RCD
here. Another difference is that the stability bounds in Hardt et al. (2016)
are established for either the constant stepsize sequence $\eta_{t}\equiv\eta$
or the specific stepsize sequence $\eta_{t}=1/(t\sigma)$. As a comparison, our
results apply to general stepsizes.

Nonconvex case. We now present stability bounds for nonconvex problems, which
are ubiquitous in the modern machine learning. We denote
$\prod_{k=t+1}^{t}\big{(}1+\widetilde{L}\eta_{k}d^{-\frac{1}{2}}\big{)}=1$.

######  Theorem 4.

Let Assumptions 1 and 3 hold. Let
$\\{\mathbf{w}_{t}\\},\\{\mathbf{w}_{t}^{(i)}\\}$ be produced by (2) based on
$S$ and $S^{(i)}$, respectively. Then

$\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}\big{]}\leq\frac{2G_{1}}{nd}\sum_{j=1}^{t}\eta_{j}\prod_{k=j+1}^{t}\big{(}1+\widetilde{L}\eta_{k}d^{-\frac{1}{2}}\big{)}.$

Almost sure bounds. The above theorems consider stability bounds in
expectation. The following theorem gives almost sure stability bounds, which
is useful to develop high-probability generalization bounds. We need a
coordinate-wise Lipschitz continuity assumption.

######  Assumption 5.

For all $S$ and $[i]\in[d]$, assume
$|\nabla_{i}F_{S}(\mathbf{w})|\leq\widetilde{G}$ for all
$\mathbf{w}\in\mathcal{W}$.

######  Theorem 5.

Let Assumptions 1, 2, 3, 5 hold. Then RCD with $T$ iterations is
$\frac{2G_{2}\widetilde{G}}{n}\sum_{t=1}^{T}\eta_{t}$-uniformly stable.

##  5 Generalization of RCD

In this section, we use the stability bounds in the previous section to
develop generalization bounds for RCD. According to (1), we need to tackle the
optimization errors for a complete generalization analysis. The following
lemma is a slight variant of the optimization error bounds in Nesterov (2012).

######  Lemma 6 (Optimization Errors).

Let Assumptions 2, 3 hold. Let $\\{\mathbf{w}_{t}\\}$ be produced by (2) with
nonincreasing step sizes satisfying $\eta_{t}\leq 2/\widetilde{L}$. Then

$\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w})]\leq\frac{d}{2\sum_{j=1}^{t}\eta_{j}}\Big{(}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}+2\eta_{1}F_{S}(\mathbf{w}_{1})\Big{)}.$
(6)

If $F_{S}$ is $\sigma$-strongly convex, then
($\mathbf{w}_{S}=\arg\min_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w})$)

$\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{t+1})-F_{S}(\mathbf{w}_{S})\big{]}\\!\leq\\!\big{(}1\\!-\\!\eta_{t}\sigma/d\big{)}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}_{S})\big{]}.$
(7)

Convex Case. We first use the technique of $\ell_{1}$ on-average argument
stability to develop generalization bounds under a Lipschitz continuity
assumption, i.e., Assumption 1.

######  Theorem 7.

Let Assumptions 1, 2, 3 hold. Let $\\{\mathbf{w}_{t}\\}$ be produced by (2)
with $\eta_{t}\equiv\eta\leq 2/\widetilde{L}$. Then

$\mathbb{E}_{{S,A}}\big{[}F(\mathbf{w}_{T})-F(\mathbf{w}^{*})\big{]}\leq\frac{2G_{1}G_{2}T\eta}{nd}+\\\
\frac{d\|\mathbf{w}_{1}-\mathbf{w}^{*}\|_{2}^{2}}{2T\eta}+\frac{dF(\mathbf{w}_{1})}{T}.$
(8)

If we choose $T\asymp d\sqrt{n}$, then

$\mathbb{E}_{{S,A}}\big{[}F(\mathbf{w}_{T})-F(\mathbf{w}^{*})\big{]}=O(1/\sqrt{n}).$
(9)

The first term on the right-hand side of Eq. (8) is related to estimation
error, while the remaining two terms are related to optimization error.
According to (8), we know that the estimation error bounds increase as we run
more and more iterations, while the optimization errors would decrease. This
suggests that we should balance these two errors by stoping the algorithm at
an appropriate iteration to enjoy a favorable generalization, as shown in (9).

######  Remark 3.

Under the same condition, it was shown that SGD with $T\asymp n$ can achieve
the excess generalization bounds $O(1/\sqrt{n})$ (Hardt et al., 2016). Here we
show that the same generalization bounds can be achieved by RCD.

In Theorem 7, we require the boundedness assumption of stochastic gradients
(note the bounded gradient assumption does not hold for the least square
loss). We now show that this boundedness assumption can be removed by using
the $\ell_{2}$-on-average argument stability. A nice property is that it
incorporates the information of $F(\mathbf{w}^{*})$ in the generalization
bounds. This suggests that better generalization bounds can be achieved if
$F(\mathbf{w}^{*})$ is small, which are called optimistic bounds in the
literature (Srebro et al., 2010; Zhang and Zhou, 2019). Here we introduce a
parameter $\gamma$ to balance different components of the generalization
bounds.

######  Theorem 8.

Let Assumptions 2, 3 hold. Let $\\{\mathbf{w}_{t}\\}$ be produced by (2) with
nonincreasing $\eta_{t}\leq 2/\widetilde{L}$. For any $\gamma>0$ such that
$(1+T)(1+\gamma)L^{2}e\sum_{t=1}^{T}\eta_{t}^{2}\leq n^{2}d/4$, we have

$\mathbb{E}_{S,A}[F(\mathbf{w}_{T})-F_{S}(\mathbf{w}^{*})]=O\Big{(}\frac{1}{\gamma}+\frac{L^{2}(\gamma+\gamma^{-1})T}{n^{2}d}\sum_{t=1}^{T}\eta_{t}^{2}\Big{)}\\\
\times
F(\mathbf{w}^{*})+O\Big{(}\frac{d+d\gamma^{-1}}{\sum_{t=1}^{T}\eta_{t}}+\frac{L^{2}(\gamma+\gamma^{-1})T}{n^{2}}\Big{)}.$
(10)

The following corollary gives a quantitative suggestion on how to stop the
algorithm for a good generalization.

######  Corollary 9.

Let Assumptions 2, 3 hold and $d=O(n^{2})$. Let $\\{\mathbf{w}_{t}\\}$ be
produced by (2) with $\eta_{t}\equiv\eta\leq 2/\widetilde{L}$.

  1. (a)

If $(1+T)(L+n\sqrt{d}/T)LeT\eta^{2}\leq n^{2}d/4$, then we can choose
$T\asymp\sqrt{n}d^{\frac{3}{4}}$ to get

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

  2. (b)

If $F(\mathbf{w}^{*})=O(d^{\frac{1}{2}}Ln^{-1})$ and $(1+T)L^{2}eT\eta^{2}\leq
n^{2}d/8$, we can choose $T\asymp n\sqrt{d}$ and get

$\mathbb{E}_{S,A}[F(\mathbf{w}_{T})-F_{S}(\mathbf{w}^{*})]=O(d^{\frac{1}{2}}n^{-1}).$

######  Remark 4.

If $T\\!\asymp\\!\sqrt{n}d^{\frac{3}{4}}$, then
$(1\\!+\\!T)(L\\!+\\!n\sqrt{d}/T)LeT\eta^{2}\asymp
nd^{\frac{3}{2}}+n^{\frac{3}{2}}d^{\frac{5}{4}}$. Then the assumption in Part
(a) holds if $d\leq cn^{2}$ for some appropriate $c>0$. If $T\asymp
n\sqrt{d}$, then $(1+T)L^{2}eT\asymp n^{2}d$. In this case, the assumption
$(1+T)L^{2}eT\eta^{2}\leq n^{2}d/8$ in Part (b) is also easy to satisfy.

######  Remark 5.

As compared to Theorem 7, Part (a) admits a worse dependency on the
dimensionality, which is the cost we pay for removing the Lipschitz continuity
assumption. Furthermore, Part (b) shows that RCD is able to achieve a
generalization bound as fast as $O(\sqrt{d}/n)$ if the best model has a small
population risk, while Theorem 7 fails to exploit this low-noise assumption
and can only imply at most the generalization bound $O(1/\sqrt{n})$.

Strongly convex case. Now, we present generalization bounds for RCD for
strongly convex objective functions.

######  Theorem 10.

Let Assumptions 1, 2, 3, 4 hold. Let $\\{\mathbf{w}_{t}\\}$ be produced by (2)
with $\eta_{t}\equiv\eta\leq 1/\widetilde{L}$. Then

$\mathbb{E}_{S,A}\big{[}F(\mathbf{w}_{T+1})-F(\mathbf{w}^{*})\big{]}\leq\frac{4G_{1}G_{2}}{n\sigma}+\big{(}1-\eta\sigma/d\big{)}^{T}F(\mathbf{w}_{1}).$

In particular, we can set $T\asymp d\sigma^{-1}\log 1/(n\sigma)$ to get the
excess generalization bound

$\mathbb{E}_{S,A}\big{[}F(\mathbf{w}_{T+1})-F(\mathbf{w}^{*})\big{]}=O(1/(n\sigma)).$

######  Remark 6.

Stability bounds of the order $O(1/(n\sigma))$ were established for SGD under
a strongly convex setting (Hardt et al., 2016), which together with
optimization error bounds of the order $O(1/(T\sigma))$ (Rakhlin et al.,
2012), shows that SGD with $n$ iterations can achieve excess risk bounds
$O(1/(n\sigma))$. Here we show that this optimal generalization bound can also
be achieved for RCD with $d\sigma^{-1}\log 1/(n\sigma)$ iterations.

High probability generalization bounds. Finally, we present high-probability
bounds which are much more challenging than bounds in expectation and are
important to understand the variation of the algorithm in repeated runs.

######  Theorem 11.

Let Assumptions 1, 2, 3, 5 hold. Let $\\{\mathbf{w}_{t}\\}$ be produced by (2)
with $\eta_{t}\equiv\eta\leq 2/\widetilde{L}$ and $\delta\in(0,1)$. Assume
$\|\mathbf{w}_{t}\|_{\infty}\leq R$ and $|f(\mathbf{w}_{t};z)|\leq R$ for all
$t$. If we choose $T\asymp
n^{\frac{2}{3}}d^{\frac{1}{3}}\log^{-\frac{2}{3}}n\log^{-\frac{1}{3}}(1/\delta)$,
then with probability at least $1-\delta$ there holds

$F(\bar{\mathbf{w}}_{T})-F(\mathbf{w}^{*})=O\Big{(}\big{(}d/n\big{)}^{\frac{1}{3}}\log^{\frac{1}{3}}n\log^{\frac{2}{3}}(1/\delta)\Big{)},$

where $\bar{\mathbf{w}}_{T}=\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t}$ is an
average of iterates.

##  6 Experiments

(a) Ionosphere

(b) Svmguide3

(c) MNIST

Figure 1: Euclidean distance between two iterate sequences of RCD/SGD on
neighboring datasets.

In this section, we present some experimental results to illustrate our
stability bounds. We follow the set up in Hardt et al. (2016), i.e., we
consider two neighboring datasets and run RCD/SGD with $\eta_{t}\equiv 0.01$
on these neighboring datasets to produce two iterate sequences
$\\{\mathbf{w}_{t}\\},\\{\mathbf{w}_{t}^{\prime}\\}$. We then plot the
Euclidean distance between two iterate sequences as a function of the
iteration number. We consider the least square regression for two datasets
available at LIBSVM website (Chang and Lin, 2011): ionosphere, svmguide3 and
MNIST. We repeat the experiments $100$ times and report the average of
results. In Figure 1 we plot the Euclidean distance as a function of the
number of iterations. Experimental results show that the Euclidean distance
for RCD is much smaller than that with SGD, which is consistent with our
theoretical results that RCD is more stable than SGD.

##  7 Proof of Theorem 2

The basic idea to prove Theorem 2 is to show how
$\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}$ would change after a single
iteration.

###### Proof of Theorem 2.

We first prove Part (a). According to the update rule (2), we know

$\displaystyle\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}$
$\displaystyle=\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}$
$\displaystyle+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\eta_{t}\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\|_{2}$
$\displaystyle\leq\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}$
$\displaystyle+\eta_{t}\|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\|_{2}$
(11)
$\displaystyle\leq\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}+\eta_{t}\|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\|_{2},$
(12)

where we have used Lemma A.1 in the last step. Since $S$ and $S^{(i)}$ differ
by the $i$-th example, we know

$\displaystyle|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\\!-\\!\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|=\frac{1}{n}\big{|}\nabla_{i_{t}}f(\mathbf{w}_{t};z_{i})\\!-\\!\nabla_{i_{t}}f(\mathbf{w}_{t};z^{\prime}_{i})\big{|}$
$\displaystyle\leq\frac{1}{n}\Big{(}\big{|}\nabla_{i_{t}}f(\mathbf{w}_{t};z_{i})\big{|}+\big{|}\nabla_{i_{t}}f(\mathbf{w}_{t};z^{\prime}_{i})\big{|}\Big{)}.$
(13)

Note that $i_{t}$ is uniformly drawn from $[d]$, we further know

$\displaystyle\mathbb{E}_{i_{t}}\big{[}|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})-\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|\big{]}$
$\displaystyle\leq\frac{1}{nd}\sum_{j=1}^{d}\Big{(}\big{|}\nabla_{j}f(\mathbf{w}_{t};z_{i})\big{|}+\big{|}\nabla_{j}f(\mathbf{w}_{t};z^{\prime}_{i})\big{|}\Big{)}$
$\displaystyle=\frac{1}{nd}\big{(}\|\nabla
f(\mathbf{w}_{t};z_{i})\|_{1}+\|\nabla
f(\mathbf{w}_{t};z^{\prime}_{i})\|_{1}\big{)}\leq\frac{2G_{1}}{nd},$ (14)

where we have used Assumption 1 in the last step. Plugging the above
inequality back into (12), we get

$\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}\big{]}\leq\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}\big{]}+\frac{2G_{1}\eta_{t}}{nd}.$

Applying the above inequality recursively gives the stated inequality. This
completes the proof of Part (a).

We now prove Part (b). According to (2), we know

$\displaystyle\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}$
$\displaystyle=\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}^{2}$
$\displaystyle=\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}$
$\displaystyle+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\eta_{t}\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\|_{2}^{2}.$

By $(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$ we know

$\displaystyle\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}\leq$
$\displaystyle(1\\!+\\!p)\|\mathbf{w}_{t}\\!-\\!\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\\!-\\!\mathbf{w}_{t}^{(i)}\\!+\\!\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}^{2}$
$\displaystyle+(1+1/p)\eta_{t}^{2}\|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\|_{2}^{2}.$

It then follows from Lemma A.1 that

$\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}\leq(1+p)\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}^{2}\\\
+(1+1/p)\eta_{t}^{2}\|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\|_{2}^{2},$
(15)

Note that $S$ and $S^{(i)}$ differ by the $i$-th example, we can analyze
analogously to (13) and get

$|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})-\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|^{2}\\\
\leq\frac{2}{n^{2}}\Big{(}\big{|}\nabla_{i_{t}}f(\mathbf{w}_{t};z_{i})\big{|}^{2}+\big{|}\nabla_{i_{t}}f(\mathbf{w}_{t};z^{\prime}_{i})\big{|}^{2}\Big{)}.$

Since $i_{t}$ is uniformly drawn from $[d]$, we further know

$\displaystyle\mathbb{E}_{i_{t}}\big{[}|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})-\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|^{2}\big{]}$
$\displaystyle\leq\frac{2}{n^{2}d}\sum_{j=1}^{d}\Big{(}\big{|}\nabla_{j}f(\mathbf{w}_{t};z_{i})\big{|}^{2}+\big{|}\nabla_{j}f(\mathbf{w}_{t};z^{\prime}_{i})\big{|}^{2}\Big{)}$
$\displaystyle=\frac{2}{n^{2}d}\big{(}\|\nabla
f(\mathbf{w}_{t};z_{i})\|_{2}^{2}+\|\nabla
f(\mathbf{w}_{t};z^{\prime}_{i})\|_{2}^{2}\big{)}$
$\displaystyle\leq\frac{4L}{n^{2}d}\big{(}f(\mathbf{w}_{t};z_{i})+f(\mathbf{w}_{t};z^{\prime}_{i})\big{)},$

where we have used the self-bounding property according to the $L$-smoothness
of $f$ in the last step. Putting the above inequality back into (15) implies

$\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}\big{]}\leq(1+p)\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}^{2}\big{]}\\\
+\frac{4(1+1/p)L\eta_{t}^{2}}{n^{2}d}\mathbb{E}_{A}\big{[}f(\mathbf{w}_{t};z_{i})+f(\mathbf{w}_{t};z^{\prime}_{i})\big{]}.$
(16)

It then follows that

$\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}\big{]}\leq\\\
\frac{4L(1+1/p)}{n^{2}d}\sum_{j=1}^{t}\big{(}1+p\big{)}^{t-j}\eta_{j}^{2}\mathbb{E}_{A}\big{[}f(\mathbf{w}_{j};z_{i})+f(\mathbf{w}_{j};z^{\prime}_{i})\big{]}.$

Taking an average over $i$, we derive

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}\big{]}$
$\displaystyle\leq\frac{4L(1+1/p)}{n^{3}d}\sum_{i=1}^{n}\\!\sum_{j=1}^{t}\big{(}1\\!+\\!p\big{)}^{t-j}\eta_{j}^{2}\mathbb{E}_{A}\big{[}f(\mathbf{w}_{j};z_{i})\\!+\\!f(\mathbf{w}_{j};z^{\prime}_{i})\big{]}$
$\displaystyle=\frac{4L(1+1/p)}{n^{2}d}\sum_{j=1}^{t}\big{(}1+p\big{)}^{t-j}\eta_{j}^{2}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{j})+F_{S^{\prime}}(\mathbf{w}_{j})\big{]}.$

The proof is complete. ∎

##  8 Conclusions

In this paper, we initialize the generalization analysis of RCD based on the
algorithmic stability. We establish upper bounds of argument stability and
uniform stability for RCD, which further imply the optimal generalization
bounds of the order $O(1/\sqrt{n})$ and $O(1/n)$ in the convex and strongly
convex case, respectively. We also consider nonconvex case and develop high-
probability bounds. Remarkably, our analysis can leverage the low-noise
assumption to yield optimistic generalization bounds $O(1/n)$ in the convex
case without a bounded gradient assumption.

There are several interesting future directions. First, it would be
interesting to extend our analysis to other variants, such as distributed RCD
and RCD for structure optimization. Second, here we assume the objectives are
convex/strongly convex and each coordinate is sampled with the same
probability during RCD updates. It is interesting to extend our discussion to
nonconvex setting and importance sampling (Nesterov, 2012), which are popular
in modern machine learning.

## Acknowledgments

This work was supported in part by the National Natural Science Foundation of
China (Grant Nos. 61903309, 61806091, 11771012, U1811461) and the Fundamental
Research Funds for the Central Universities (JBK1806002).

## References

  * Bassily et al. [2020] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar.  Stability of stochastic gradient descent on nonsmooth convex losses.  NeurIPS, 33, 2020.
  * Bousquet and Elisseeff [2002] Olivier Bousquet and André Elisseeff.  Stability and generalization.  JMLR, 2(Mar):499–526, 2002.
  * Bousquet et al. [2020] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy.  Sharper bounds for uniformly stable algorithms.  In COLT, pages 610–626, 2020.
  * Chang and Lin [2011] Chih-Chung Chang and Chih-Jen Lin.  Libsvm: a library for support vector machines.  ACM Transactions on Intelligent Systems and Technology, 2(3):27, 2011.
  * Chang et al. [2008] Kai-Wei Chang, Cho-Jui Hsieh, and Chih-Jen Lin.  Coordinate descent method for large-scale l2-loss linear support vector machines.  JMLR, 9(Jul):1369–1398, 2008.
  * Charles and Papailiopoulos [2018] Zachary Charles and Dimitris Papailiopoulos.  Stability and generalization of learning algorithms that converge to global optima.  In ICML, pages 744–753, 2018.
  * Chen and Gu [2016] Jinghui Chen and Quanquan Gu.  Accelerated stochastic block coordinate gradient descent for sparsity constrained nonconvex optimization.  In UAI, 2016.
  * Damaskinos et al. [2020] Georgios Damaskinos, Celestine Mendler-Dünner, Rachid Guerraoui, Nikolaos Papandreou, and Thomas Parnell.  Differentially private stochastic coordinate descent.  arXiv preprint arXiv:2006.07272, 2020.
  * Elisseeff et al. [2005] Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil.  Stability of randomized learning algorithms.  JMLR, 6(Jan):55–79, 2005.
  * Feldman and Vondrak [2019] Vitaly Feldman and Jan Vondrak.  High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.  In COLT, pages 1270–1279, 2019.
  * Gu et al. [2018] Bin Gu, Yingying Shan, Xiang Geng, and Guansheng Zheng.  Accelerated asynchronous greedy coordinate descent algorithm for svms.  In IJCAI, pages 2170–2176, 2018.
  * Hardt et al. [2016] Moritz Hardt, Ben Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In ICML, pages 1225–1234, 2016.
  * Hu and Kwok [2019] En-Liang Hu and James T Kwok.  Low-rank matrix learning using biconvex surrogate minimization.  TNNLS, 30(11):3517–3527, 2019.
  * Kuzborskij and Lampert [2018] Ilja Kuzborskij and Christoph Lampert.  Data-dependent stability of stochastic gradient descent.  In ICML, pages 2820–2829, 2018.
  * Lei and Ying [2020] Yunwen Lei and Yiming Ying.  Fine-grained analysis of stability and generalization for stochastic gradient descent.  In ICML, pages 5809–5819, 2020.
  * Lei and Ying [2021] Yunwen Lei and Yiming Ying.  Sharper generalization bounds for learning with gradient-dominated objective functions.  In ICLR, 2021.
  * Lei et al. [2020] Yunwen Lei, Antoine Ledent, and Marius Kloft.  Sharper generalization bounds for pairwise learning.  In NeurIPS, volume 33, 2020.
  * Li and Lin [2020] Huan Li and Zhouchen Lin.  On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent.  JMLR, 21(33):1–45, 2020.
  * Liu et al. [2017] Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao.  Algorithmic stability and hypothesis complexity.  In ICML, pages 2159–2167, 2017.
  * Lu and Xiao [2015] Zhaosong Lu and Lin Xiao.  On the complexity analysis of randomized block-coordinate descent methods.  Mathematical Programming, 152(1-2):615–642, 2015.
  * Meng et al. [2017] Qi Meng, Yue Wang, Wei Chen, Taifeng Wang, Zhi-Ming Ma, and Tie-Yan Liu.  Generalization error bounds for optimization algorithms via stability.  In AAAI, volume 31, 2017.
  * Mukherjee and Zhou [2006] Sayan Mukherjee and Ding-Xuan Zhou.  Learning coordinate covariances via gradients.  JMLR, 7:519–549, 2006.
  * Nesterov [2012] Yu Nesterov.  Efficiency of coordinate descent methods on huge-scale optimization problems.  SIAM Journal on Optimization, 22(2):341–362, 2012.
  * Qu et al. [2016] Zheng Qu, Peter Richtárik, Martin Takác, and Olivier Fercoq.  Sdna: Stochastic dual newton ascent for empirical risk minimization.  In ICML, pages 1823–1832, 2016.
  * Rakhlin et al. [2012] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Making gradient descent optimal for strongly convex stochastic optimization.  In ICML, pages 449–456, 2012.
  * Ren and Zhu [2017] Yong Ren and Jun Zhu.  Distributed accelerated proximal coordinate gradient methods.  In IJCAI, pages 2655–2661, 2017.
  * Richtárik and Takáč [2014] Peter Richtárik and Martin Takáč.  Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.  Mathematical Programming, 144(1-2):1–38, 2014.
  * Richtárik and Takáč [2016] Peter Richtárik and Martin Takáč.  Distributed coordinate descent method for learning with big data.  JMLR, 17(1):2657–2681, 2016.
  * Shalev-Shwartz and Tewari [2009] Shai Shalev-Shwartz and Ambuj Tewari.  Stochastic methods for $\ell_{1}$ regularized loss minimization.  In ICML, pages 929–936, 2009.
  * Shalev-Shwartz et al. [2010] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Learnability, stability and uniform convergence.  JMLR, 11(Oct):2635–2670, 2010.
  * Srebro et al. [2010] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari.  Smoothness, low noise and fast rates.  In NeurIPS, pages 2199–2207, 2010.
  * Sun et al. [2017] Tao Sun, Robert Hannah, and Wotao Yin.  Asynchronous coordinate descent under more realistic assumptions.  In NeurIPS, pages 6182–6190, 2017.
  * Wang et al. [2021] Puyu Wang, Yunwen Lei, Yiming Ying, and Hai Zhang.  Differentially private SGD with non-smooth loss.  arXiv preprint arXiv:2101.08925, 2021.
  * Xiao et al. [2019] Lin Xiao, Adams Wei Yu, Qihang Lin, and Weizhu Chen.  Dscovr: Randomized primal-dual block coordinate algorithms for asynchronous distributed optimization.  JMLR, 20:43–1, 2019.
  * Yang et al. [2021] Zhenhuan Yang, Yunwen Lei, Siwei Lyu, and Yiming Ying.  Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss.  In AISTATS, pages 2026–2034. PMLR, 2021.
  * Yin et al. [2018] Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett.  Gradient diversity: a key ingredient for scalable distributed learning.  In AISTATS, pages 1998–2007. PMLR, 2018.
  * Yuan et al. [2019] Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang.  Stagewise training accelerates convergence of testing error over sgd.  In NeurIPS, pages 2604–2614, 2019.
  * Zhang and Zhou [2019] Lijun Zhang and Zhi-Hua Zhou.  Stochastic approximation of smooth and strongly convex functions: Beyond the O(1/t) convergence rate.  In COLT, pages 3160–3179, 2019.
  * Zhu and Storkey [2016] Zhanxing Zhu and Amos Storkey.  Stochastic parallel block coordinate descent for large-scale saddle point problems.  In AAAI, volume 30, 2016.

##  Appendix A Some Lemmas

We introduce some useful lemmas. The following lemma shows that the coordinate
descent operator
$\mathbf{w}\mapsto\mathbf{w}-\eta\nabla_{i}g(\mathbf{w})\mathbf{e}_{i}$ is
non-expansive.

######  Lemma A.1.

Let $g:\mathbb{R}^{d}\mapsto\mathbb{R}$ be convex and have coordinate-wise
Lipschitz continuous gradients with parameter $\widetilde{L}>0$. Then for any
$\eta\leq 2/\widetilde{L}$ and any $i\in[d]$ we have the following inequality
for any $\mathbf{w}$ and $\tilde{\mathbf{w}}$

$\|\mathbf{w}-\eta\nabla_{i}g(\mathbf{w})\mathbf{e}_{i}-\tilde{\mathbf{w}}+\eta\nabla_{i}g(\tilde{\mathbf{w}})\mathbf{e}_{i}\|_{2}\leq\|\mathbf{w}-\tilde{\mathbf{w}}\|_{2}.$
(A.1)

Furthermore, if $g$ is $\sigma$-coordinate-wise strongly convex and $\eta\leq
1/\widetilde{L}$, then

$\|\mathbf{w}-\eta\nabla_{i}g(\mathbf{w})\mathbf{e}_{i}-\tilde{\mathbf{w}}+\eta\nabla_{i}g(\tilde{\mathbf{w}})\mathbf{e}_{i}\|_{2}^{2}\\\
\leq\|\mathbf{w}-\tilde{\mathbf{w}}\|_{2}^{2}-\eta\sigma|w_{i}-\tilde{w}_{i}|^{2},$
(A.2)

where $w_{i}$ denotes the $i$-th coordinate of $\mathbf{w}\in\mathbb{R}^{d}$.

To prove Lemma A.1, we introduce the following lemma due to Hardt et al.
[2016].

######  Lemma A.2 (Hardt et al. 2016).

Assume the function $g:\mathbb{R}\mapsto\mathbb{R}$ is convex and $L$-smooth.
Then for all $w$, $w^{\prime}\in\mathbb{R}$ and $\eta\leq 2/L$ we know

$|w-\eta\nabla g(w)-w^{\prime}+\eta\nabla g(w^{\prime})|\leq|w-w^{\prime}|.$
(A.3)

Furthermore, if $g$ is $\sigma$-strongly convex and $\eta\leq 1/L$ there holds

$|w-\eta\nabla g(w)-w^{\prime}+\eta\nabla
g(w^{\prime})|^{2}\leq(1-\eta\sigma)|w-w^{\prime}|^{2}.$ (A.4)

###### Proof of Lemma A.1.

Recall that $w_{j}$ denotes the $j$-th coordinate of
$\mathbf{w}\in\mathbb{R}^{d}$. It is clear that

$\|\mathbf{w}-\eta\nabla_{i}g(\mathbf{w})\mathbf{e}_{i}-\tilde{\mathbf{w}}+\eta\nabla_{i}g(\tilde{\mathbf{w}})\mathbf{e}_{i}\|_{2}^{2}\\\
=\sum_{j\neq
i}|w_{j}-\tilde{w}_{j}|^{2}+|w_{i}-\eta\nabla_{i}g(\mathbf{w})-\tilde{w}_{i}+\eta\nabla_{i}g(\tilde{\mathbf{w}})|^{2}.$

We can fix $w_{j}$ for all $j\neq i$ and then $g$ can be considered as a
univariate function of $w_{i}$. Applying (A.3) in Lemma A.2 to this univariate
function, we have

$|w_{i}-\eta\nabla_{i}g(\mathbf{w})-\tilde{w}_{i}+\eta\nabla_{i}g(\tilde{\mathbf{w}})|\leq|w_{i}-\tilde{w}_{i}|.$

Combining the above two inequalities together, we derive the stated inequality
(A.1).

We now turn to (A.2) in a strongly convex setting. Similarly, (A.4) in Lemma
A.2 implies that

$\|\mathbf{w}-\eta\nabla_{i}g(\mathbf{w})\mathbf{e}_{i}-\tilde{\mathbf{w}}+\eta\nabla_{i}g(\tilde{\mathbf{w}})\mathbf{e}_{i}\|_{2}^{2}\leq\\\
\sum_{j\neq
i}|w_{j}-\tilde{w}_{j}|^{2}+(1-\eta\sigma)|w_{i}-\tilde{w}_{i}|^{2}.$

This completes the proof. ∎

Smooth functions enjoy the self-bounding property, which means that the
gradients can be bounded by the function values [Srebro et al., 2010].

######  Lemma A.3.

If $g:\mathcal{W}\mapsto\mathbb{R}_{+}$ is $L$-smooth, then for all
$\mathbf{w}\in\mathcal{W}$ there holds $\|\nabla g(\mathbf{w})\|_{2}^{2}\leq
2Lg(\mathbf{w}).$

##  Appendix B Proof of Theorem 3

###### Proof of Theorem 3.

By (A.2), we know ($w_{t,i_{t}}$ is the $i_{t}$-th component of
$\mathbf{w}_{t}$ and $w_{t,i_{t}}^{(i)}$ is the $i_{t}$-th component of
$\mathbf{w}_{t}^{(i)}$)

$\displaystyle\mathbb{E}_{i_{t}}\big{[}\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}^{2}\big{]}$
$\displaystyle\leq\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}^{2}-\eta_{t}\sigma\mathbb{E}_{i_{t}}[|w_{t,i_{t}}-{w}_{t,i_{t}}^{(i)}|^{2}]$
$\displaystyle=(1-\eta_{t}\sigma/d)\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}^{2}\leq(1\\!-\\!\eta_{t}\sigma/(2d))^{2}\|\mathbf{w}_{t}\\!-\\!\mathbf{w}_{t}^{(i)}\|_{2}^{2},$

where we have used

$\mathbb{E}_{i_{t}}[|w_{t,i_{t}}-w_{t,i_{t}}^{(i)}|^{2}]=\frac{1}{d}\sum_{k=1}^{d}[|w_{t}^{(k)}-w_{t,k}^{(i)}|^{2}]=\frac{1}{d}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}^{2}$

and $1-a\leq(1-a/2)^{2}$. It then follows that

$\mathbb{E}_{i_{t}}\big{[}\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}\big{]}\\\
\leq(1-\eta_{t}\sigma/(2d))\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}.$

Putting the above inequality into (11) and using (14), we get

$\mathbb{E}_{A}[\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}]\leq(1-\eta_{t}\sigma/(2d))\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}\big{]}+\frac{2G_{1}\eta_{t}}{nd}.$

Applying the above inequality recursively gives

$\mathbb{E}_{A}[\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}]\leq\frac{2G_{1}}{nd}\sum_{j=1}^{t}\eta_{j}\prod_{k=j+1}^{t}(1-\eta_{k}\sigma/(2d)).$

Note that

$\displaystyle\sum_{j=1}^{t}\eta_{j}\sigma/(2d)\prod_{k=j+1}^{t}(1-\eta_{k}\sigma/(2d))$
$\displaystyle=\sum_{j=1}^{t}\big{(}1-\big{(}1-\eta_{j}\sigma/(2d)\big{)}\big{)}\prod_{k=j+1}^{t}(1-\eta_{k}\sigma/(2d))$
$\displaystyle=\sum_{j=1}^{t}\prod_{k=j+1}^{t}(1-\eta_{k}\sigma/(2d))-\sum_{j=1}^{t}\prod_{k=j}^{t}(1-\eta_{k}\sigma/(2d))$
$\displaystyle=1-\prod_{k=1}^{t}(1-\eta_{k}\sigma/(2d))\leq 1.$

We can combine the above two inequalities together and get the stated bound.
The proof is complete. ∎

##  Appendix C Proofs of Generalization Bounds

In this section, we present the proofs of generalization bounds for RCD.

###  C.1 Convex Case

We first consider generalization bounds in the convex case.

###### Proof of Theorem 7.

Let $A(S)=\mathbf{w}_{T}$. It follows from Part (a) of Lemma 1 and Eq. (3)
that

$\mathbb{E}_{{S,A}}\big{[}F(\mathbf{w}_{T})-F_{S}(\mathbf{w}_{T})\big{]}\leq\frac{2G_{1}G_{2}}{nd}\sum_{t=1}^{T}\eta_{t}.$

This together with the optimization error bounds in (6) with
$\mathbf{w}=\mathbf{w}^{*}$ and the error decomposition (1) gives

$\mathbb{E}_{{S,A}}\big{[}F(\mathbf{w}_{T})-F(\mathbf{w}^{*})\big{]}\leq\frac{2G_{1}G_{2}}{nd}\sum_{t=1}^{T}\eta_{t}\\\
+\frac{d\big{(}\|\mathbf{w}_{1}-\mathbf{w}^{*}\|_{2}^{2}+2\eta_{1}\mathbb{E}[F_{S}(\mathbf{w}_{1})]\big{)}}{2\sum_{t=1}^{T}\eta_{t}}.$

Since $\eta_{t}\equiv\eta$ and
$\mathbb{E}_{{S,A}}[F_{S}(\mathbf{w}_{1})]=F(\mathbf{w}_{1})$, we further get
the stated bound (8). The second bound then follows from the choice of $T$.
The proof is complete. ∎

###### Proof of Theorem 8.

Taking expectation on both sides of (4) and noticing
$\mathbb{E}_{S^{\prime}}[F_{S^{\prime}}(\mathbf{w}_{j})]=F(\mathbf{w}_{j})$
since $\mathbf{w}_{j}$ is independent of $S^{\prime}$, we derive

$\mathbb{E}_{S,S^{\prime},A}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}^{2}\Big{]}\\\
\leq\frac{4L(1+1/p)}{n^{2}d}\sum_{j=1}^{t}\big{(}1+p\big{)}^{t-j}\eta_{j}^{2}\mathbb{E}_{S,A}\big{[}F_{S}(\mathbf{w}_{j})+F(\mathbf{w}_{j})\big{]}.$

We plug the above inequality into Part (b) of Lemma 1 with
$A(S)=\mathbf{w}_{t+1}$, and derive

$\mathbb{E}_{S,A}\big{[}F(\mathbf{w}_{t+1})-(1+\gamma^{-1})F_{S}(\mathbf{w}_{t+1})\big{]}\leq\\\
\frac{2(1+1/p)L^{2}(1+\gamma)}{n^{2}d}\sum_{j=1}^{t}\big{(}1+p\big{)}^{t-j}\eta_{j}^{2}\mathbb{E}_{S,A}\big{[}F(\mathbf{w}_{j})\\\
-(1+\gamma^{-1})F_{S}(\mathbf{w}_{j})+(2+\gamma^{-1})F_{S}(\mathbf{w}_{j})\big{]}.$

Let

$\delta_{j}=\max\big{\\{}\mathbb{E}_{S,A}[F(\mathbf{w}_{j})-(1+\gamma^{-1})F_{S}(\mathbf{w}_{j})],0\big{\\}},\quad\forall
j\in\mathbb{N}.$

Then, it follows that

$\displaystyle\delta_{t+1}-\frac{2(1+1/p)L^{2}(1+\gamma)(2+\gamma^{-1})(1+p)^{t-1}}{n^{2}d}\sum_{j=1}^{t}\eta_{j}^{2}$
$\displaystyle\times\mathbb{E}_{S,A}[F_{S}(\mathbf{w}_{j})]\leq\frac{2(1+1/p)L^{2}(1+\gamma)(1+p)^{t-1}}{n^{2}d}\sum_{j=1}^{t}\eta_{j}^{2}\delta_{j}$
$\displaystyle\leq\frac{2(1+1/p)L^{2}(1+\gamma)(1+p)^{t-1}}{n^{2}d}\sum_{j=1}^{t}\eta_{j}^{2}\max_{1\leq\tilde{j}\leq
t+1}\delta_{\tilde{j}}.$

Since the above inequality holds for all $t$ and the above upper bound of
$\\{\delta_{t}\\}$ is an increasing function of $t$, we can set $p=1/t$ and
derive

$\max_{1\leq\tilde{j}\leq
t+1}\delta_{\tilde{j}}\leq\frac{2(1+t)L^{2}(1+\gamma)e}{n^{2}d}\sum_{j=1}^{t}\eta_{j}^{2}\max_{1\leq\tilde{j}\leq
t+1}\delta_{\tilde{j}}\\\
+\frac{2(1+t)L^{2}(1+\gamma)(2+\gamma^{-1})e\sum_{j=1}^{t}\eta_{j}^{2}\mathbb{E}_{S,A}[F_{S}(\mathbf{w}_{j})]}{n^{2}d},$

where we have used $(1+1/t)^{t}\leq e$. According to the assumption
$(1+t)L^{2}(1+\gamma)e\sum_{j=1}^{t}\eta_{j}^{2}\leq n^{2}d/4$, we further get
the following inequality for all $t=1,\ldots,T$

$\max_{1\leq\tilde{j}\leq
t+1}\delta_{\tilde{j}}\leq\frac{1}{2}\max_{1\leq\tilde{j}\leq
t+1}\delta_{\tilde{j}}\\\
+\frac{2(1+t)L^{2}(1+\gamma)(2+\gamma^{-1})e\sum_{j=1}^{t}\eta_{j}^{2}\mathbb{E}_{S,A}[F_{S}(\mathbf{w}_{j})]}{n^{2}d},$

and therefore

$\mathbb{E}_{S,A}[F(\mathbf{w}_{t})-F_{S}(\mathbf{w}_{t})]\leq\\\
\gamma^{-1}\big{(}\mathbb{E}_{S,A}[F_{S}(\mathbf{w}_{t})]-\mathbb{E}_{S,A}[F_{S}(\mathbf{w})]+\mathbb{E}_{S,A}[F_{S}(\mathbf{w})]\big{)}+\\\
\frac{4(1+t)L^{2}(1+\gamma)(2+\gamma^{-1})e}{n^{2}d}\sum_{j=1}^{t}\eta_{j}^{2}\mathbb{E}_{S,A}[F_{S}(\mathbf{w}_{j})].$

Summing both sides by
${\mathbb{E}_{S,A}}[F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w})]$ and using the
decomposition
$F_{S}(\mathbf{w}_{j})=F_{S}(\mathbf{w}_{j})-F_{S}(\mathbf{w})+F_{S}(\mathbf{w})$,
it then follows from (6) and (E.5) that

$\mathbb{E}_{S,A}[F(\mathbf{w}_{t})-F_{S}(\mathbf{w})]\leq\gamma^{-1}\mathbb{E}_{S,A}[F_{S}(\mathbf{w})]\\\
+\frac{d(1+\gamma^{-1})}{2\sum_{j=1}^{t}\eta_{j}}\Big{(}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}+2\eta_{1}F(\mathbf{w}_{1})\Big{)}+\\\
\frac{2(1+t)L^{2}(1+\gamma)(2+\gamma^{-1})e}{n^{2}}\Big{(}\eta_{1}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}+2\eta_{1}^{2}F(\mathbf{w}_{1})\Big{)}\\\
+\frac{4(1+t)L^{2}(1+\gamma)(2+\gamma^{-1})e}{n^{2}d}\sum_{j=1}^{t}\eta_{j}^{2}\mathbb{E}_{S,A}[F_{S}(\mathbf{w})].$

We can set $\mathbf{w}=\mathbf{w}^{*}$ in the above inequality and get the
stated bound. The proof is complete.

∎

###### Proof of Corollary 9.

We first prove Part (a). For the constant step size $\eta_{t}\equiv\eta$, the
generalization bound in (10) becomes

$\mathbb{E}_{S,A}[F(\mathbf{w}_{T})-F_{S}(\mathbf{w}^{*})]=O\Big{(}\frac{1}{\gamma}+\frac{L^{2}(\gamma+\gamma^{-1})T^{2}}{n^{2}d}\Big{)}F(\mathbf{w}^{*})\\\
+O\Big{(}\frac{d+d\gamma^{-1}}{T}+\frac{L^{2}(\gamma+\gamma^{-1})T}{n^{2}}\Big{)}.$
(C.1)

We choose $\gamma=\frac{n\sqrt{d}}{TL}$. If

$(1+T)(L+n\sqrt{d}/T)LeT\eta^{2}\leq n^{2}d/4,$

then (C.1) holds and becomes

$\mathbb{E}_{S,A}[F(\mathbf{w}_{T})-F_{S}(\mathbf{w}^{*})]=O\Big{(}\frac{LT}{n\sqrt{d}}+{\big{(}\frac{LT}{n\sqrt{d}}\big{)}^{3}}+\frac{d}{T}+{\frac{L\sqrt{d}}{n}}\Big{)}.$

We can further choose $T\asymp\sqrt{n}d^{\frac{3}{4}}$ and use $d=O(n^{2})$ to
derive

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

We now turn to Part (b). If $F(\mathbf{w}^{*})=O(d^{\frac{1}{2}}Ln^{-1})$, we
choose $\gamma=1$. If $(1+T)L^{2}eT\eta^{2}\leq n^{2}d/8$, (C.1) holds and
becomes

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

We can further choose $T\asymp n\sqrt{d}/L$ and derive

$\mathbb{E}_{S,A}[F(\mathbf{w}_{T})-F_{S}(\mathbf{w}^{*})]=O(d^{\frac{1}{2}}Ln^{-1}).$

∎

###  C.2 Strongly Convex Case

We now consider the generalization bounds for strongly convex objective
functions.

###### Proof of Theorem 10.

Let $A(S)=\mathbf{w}_{T}$. It follows from Part (a) of Theorem 1 and Eq. (5)
that

$\mathbb{E}_{{S,A}}\big{[}F(\mathbf{w}_{T})-F_{S}(\mathbf{w}_{T})\big{]}\leq\frac{4G_{1}G_{2}}{n\sigma}.$

This together with the optimization error bounds in (7) and the error
decomposition (1) gives

$\mathbb{E}_{{S,A}}\big{[}F(\mathbf{w}_{T})-F(\mathbf{w}^{*})\big{]}\leq\frac{4G_{1}G_{2}}{n\sigma}\\\
+\big{(}1-\eta\sigma/d\big{)}^{T-1}\mathbb{E}\big{[}F_{S}(\mathbf{w}_{1})-F_{S}(\mathbf{w}_{S})\big{]}.$

To get the excess generalization bound $O(1/(n\sigma))$, it suffices that

$\displaystyle\big{(}1-\eta\sigma/d\big{)}^{T-1}F(\mathbf{w}_{1})$
$\displaystyle\leq\exp(-(T-1)\eta\sigma/d\big{)}F(\mathbf{w}_{1})$
$\displaystyle=O\big{(}1/(n\sigma)\big{)}.$

The stated requirement on $T$ follows directly. The proof is complete. ∎

##  Appendix D Proof of Theorem 4

In this section, we prove stability bounds of RCD in a nonconvex case.

###### Proof of Theorem 4.

Since $F_{S}$ has coordinate Lipschitz gradients, we know ($w_{t,i_{t}}$
denotes the $i_{t}$-th component of $\mathbf{w}_{t}$ and $w_{t,i_{t}}^{(i)}$
denotes the $i_{t}$-th component of $\mathbf{w}_{t}^{(i)}$)

$\big{|}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})-\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\big{|}\leq\widetilde{L}\big{|}w_{t,i_{t}}-w_{t,i_{t}}^{(i)}\big{|}$

and therefore

$\displaystyle\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}$
$\displaystyle\leq\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}+\eta_{t}\|\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}$
$\displaystyle\leq\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}+\widetilde{L}\eta_{t}\big{|}w_{t,i_{t}}-w_{t,i_{t}}^{(i)}\big{|}.$

It then follows the uniform distribution of $i_{t}$ that

$\displaystyle\mathbb{E}_{i_{t}}\big{[}\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}_{t}^{(i)}+\eta_{t}\nabla_{i_{t}}F_{S^{(i)}}(\mathbf{w}_{t}^{(i)})\mathbf{e}_{i_{t}}\|_{2}\big{]}$
$\displaystyle\leq\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}+\widetilde{L}\eta_{t}\mathbb{E}_{i_{t}}\big{[}\big{|}w_{t,i_{t}}-w_{t,i_{t}}^{(i)}\big{|}\big{]}$
$\displaystyle=\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}+\widetilde{L}\eta_{t}d^{-1}\sum_{j=1}^{d}\big{[}\big{|}w_{t,j}-w_{t,j}^{(i)}\big{|}\big{]}$
$\displaystyle=\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}+\widetilde{L}\eta_{t}d^{-1}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{1}$
$\displaystyle\leq\big{(}1+\widetilde{L}\eta_{t}d^{-\frac{1}{2}}\big{)}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2},$

where we have used $\|\cdot\|_{1}\leq\sqrt{d}\|\cdot\|_{2}$. We can plug the
above inequality and (14) into (11), and get

$\mathbb{E}_{{A}}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}\big{]}\leq\\\
\big{(}1+\widetilde{L}\eta_{t}d^{-\frac{1}{2}}\big{)}\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{(i)}\|_{2}\big{]}+\frac{2G_{1}\eta_{t}}{nd}.$

We can apply the above inequality recursively and get

$\mathbb{E}_{{A}}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}\big{]}\leq\frac{2G_{1}}{nd}\sum_{j=1}^{t}\eta_{j}\prod_{k=j+1}^{t}\big{(}1+\widetilde{L}\eta_{k}d^{-\frac{1}{2}}\big{)}.$

The proof is complete. ∎

##  Appendix E Proofs of Optimization Error Bounds

In this section, we prove optimization error bounds. The discussions follow
[Nesterov, 2012] and we give the proof here for completeness.

###### Proof of Lemma 6.

It follows from (2) that

$\displaystyle F_{S}(\mathbf{w}_{t+1})$
$\displaystyle=F_{S}(\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}})$
$\displaystyle\leq
F_{S}(\mathbf{w}_{t})-\eta_{t}|\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|^{2}+\frac{\widetilde{L}\eta_{t}^{2}}{2}|\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|^{2}$
$\displaystyle\leq
F_{S}(\mathbf{w}_{t})-\eta_{t}|\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|^{2}/2,$
(E.1)

where the first inequality holds since $F_{S}$ has coordinate-wise Lipschitz
continuous gradients [Nesterov, 2012] and in the last inequality we have used
$\eta_{t}\leq 1/\widetilde{L}$. Taking an expectation w.r.t. $i_{t}$, we
derive

$\displaystyle\mathbb{E}_{i_{t}}\big{[}F_{S}(\mathbf{w}_{t+1})\big{]}$
$\displaystyle\leq
F_{S}(\mathbf{w}_{t})-\eta_{t}\sum_{j=1}^{d}|\nabla_{j}F_{S}(\mathbf{w}_{t})|^{2}/(2d)$
$\displaystyle=F_{S}(\mathbf{w}_{t})-\eta_{t}\|\nabla
F_{S}(\mathbf{w}_{t})\|_{2}^{2}/(2d).$ (E.2)

According to the update (2) again, we know

$\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}=\|\mathbf{w}_{t}-\eta_{t}\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbf{w}\|_{2}^{2}\\\
=\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}+\eta_{t}^{2}|\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})|^{2}+\\\
2\eta_{t}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\rangle.$
(E.3)

Taking an expectation w.r.t. $i_{t}$, we derive

$\displaystyle\mathbb{E}_{i_{t}}[\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}]\leq\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}$
$\displaystyle+\frac{\eta_{t}^{2}}{d}\sum_{j=1}^{d}|\nabla_{j}F_{S}(\mathbf{w}_{t})|^{2}+\frac{2\eta_{t}}{d}\sum_{j=1}^{d}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{j}F_{S}(\mathbf{w}_{t})\mathbf{e}_{j}\rangle$
$\displaystyle=\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}+\frac{\eta_{t}^{2}}{d}\|\nabla
F_{S}(\mathbf{w}_{t})\|_{2}^{2}+\frac{2\eta_{t}}{d}\langle\mathbf{w}-\mathbf{w}_{t},\nabla
F_{S}(\mathbf{w}_{t})\rangle$
$\displaystyle\leq\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}+2\eta_{t}\mathbb{E}_{i_{t}}\big{[}F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}_{t+1})\big{]}$
$\displaystyle\qquad\qquad+\frac{2\eta_{t}}{d}\big{(}F_{S}(\mathbf{w})-F_{S}(\mathbf{w}_{t})\big{)},$

where in the last inequality we have used (E.2) and the convexity of $F_{S}$.
This together with the assumption $\eta_{t+1}\leq\eta_{t}$ gives

$\displaystyle
2\eta_{t}\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w})]$
$\displaystyle\leq
d\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}\big{]}-d\mathbb{E}_{A}[\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}]$
$\displaystyle+2\eta_{t}d\cdot\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t})]-2\eta_{t+1}d\cdot\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t+1})].$
(E.4)

Taking a summation of the above inequality gives

$2\sum_{j=1}^{t}\eta_{j}\mathbb{E}_{A}[F_{S}(\mathbf{w}_{j})-F_{S}(\mathbf{w})]\leq
d\cdot\mathbb{E}_{A}\big{[}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}\big{]}\\\
+2\eta_{1}d\cdot\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{1})\big{]}.$

This together with
$\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t+1})]\leq\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t})]$
due to (E.2) implies

$\displaystyle\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w})]$
$\displaystyle\leq\frac{1}{\sum_{j=1}^{t}\eta_{j}}\sum_{j=1}^{t}\eta_{j}\mathbb{E}_{A}[F_{S}(\mathbf{w}_{j})-F_{S}(\mathbf{w})]$
$\displaystyle\leq\frac{d}{2\sum_{j=1}^{t}\eta_{j}}\Big{(}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}+2\eta_{1}F_{S}(\mathbf{w}_{1})\Big{)}.$

This proves (6). Similarly, we can multiply both sides of (E) by $\eta_{t}$
and use the assumption $\eta_{t+1}\leq\eta_{t}$ to derive

$\displaystyle
2\eta_{t}^{2}\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w})]$
$\displaystyle\leq
d\eta_{t}\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}\big{]}-d\eta_{t+1}\mathbb{E}_{A}[\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}]$
$\displaystyle+2\eta_{t}^{2}d\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t})]-2\eta_{t+1}^{2}d\mathbb{E}_{A}[F_{S}(\mathbf{w}_{t+1})].$

Taking a summation of the above inequality gives

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

Now, we prove (7). By the $\sigma$-strong convexity we know [Nesterov, 2012]

$F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}_{S})\leq\frac{1}{2\sigma}\|\nabla
F_{S}(\mathbf{w}_{t})-\nabla F_{S}(\mathbf{w}_{S})\|_{2}^{2}.$

Plugging the above inequality back into (E.2) and using $\nabla
F_{S}(\mathbf{w}_{S})=0$, we get

$\mathbb{E}\big{[}F_{S}(\mathbf{w}_{t+1})\big{]}\leq\mathbb{E}[F_{S}(\mathbf{w}_{t})]-\frac{\eta_{t}\sigma}{d}\mathbb{E}\big{[}F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}_{S})\big{]}.$

Subtracting both sides by $F_{S}(\mathbf{w}_{S})$ gives the stated bound. The
proof is complete. ∎

##  Appendix F Proofs of Bounds with High Probability

We first prove Theorem 5 on the uniform stability of RCD.

###### Proof of Theorem 5.

Let $S$ and $S^{(i)}$ be defined in Definition 2. Let
$\\{\mathbf{w}_{t}\\},\\{\mathbf{w}_{t}^{(i)}\\}$ be produced by (2) with
$\eta_{t}\leq 2/\widetilde{L}$ based on $S$ and $S^{(i)}$, respectively.
According to (12), (13), we know

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

It then follows that

$\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{(i)}\|_{2}\leq\sum_{k=1}^{t}\frac{2\eta_{k}\widetilde{G}}{n}.$

According to Assumption 1, we further get

$f(\mathbf{w}_{t+1};z)-f(\mathbf{w}_{t+1}^{(i)};z)\leq\sum_{k=1}^{t}\frac{2G_{2}\eta_{k}\widetilde{G}}{n}.$

The proof is complete. ∎

The following lemma establishes high-probability generalization bounds for
uniformly stable algorithms [Bousquet et al., 2020].

######  Lemma F.1.

Assume $|f(A(S);z)|\leq R$ for some $R>0$ and $S,z\in\mathcal{Z}$. Let
$\delta\in(0,1)$. If $A$ is $\epsilon$-uniformly-stable almost surely, then
with probability at least $1-\delta$ there holds

$\big{|}F(A(S))-F_{S}(A(S))\big{|}=O\Big{(}\epsilon\log n\log(1/\delta)+\\\
Rn^{-\frac{1}{2}}\sqrt{\log(1/\delta)}\Big{)}.$

We now turn to optimization error bounds with high probability. To this aim,
we need to use concentration inequalities to control a martingale difference
sequence.

######  Lemma F.2.

Let $z_{1},\ldots,z_{n}$ be a sequence of random variables such that $z_{k}$
may depend on the previous random variables $z_{1},\ldots,z_{k-1}$ for all
$k=1,\ldots,n$. Consider a sequence of functionals
$\xi_{k}(z_{1},\ldots,z_{k}),k=1,\ldots,n$. Let

$\sigma_{n}^{2}=\sum_{k=1}^{n}\mathbb{E}_{z_{k}}\big{[}\big{(}\xi_{k}-\mathbb{E}_{z_{k}}[\xi_{k}]\big{)}^{2}\big{]}$

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

$\sum_{k=1}^{n}\xi_{k}-\sum_{k=1}^{n}\mathbb{E}_{z_{k}}[\xi_{k}]\leq\frac{\rho\sigma_{n}^{2}}{b}+\frac{b\log\frac{1}{\delta}}{\rho}.$
(F.1)

######  Lemma F.3.

Let Assumptions 1, 5 hold and $\|\mathbf{w}_{t}\|_{\infty}\leq R$. Introduce
the martingale difference sequence

$\xi_{t}=\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\rangle-\mathbb{E}_{i_{t}}\big{[}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\rangle\big{]}.$
(F.2)

For any $\delta\in(0,1)$, with probability at least $1-\delta$ there holds

$\sum_{t=1}^{T}\xi_{t}\leq
2(R+\|\mathbf{w}\|_{\infty})\Big{(}G_{2}\sqrt{d^{-1}T\log(1/\delta)}+\widetilde{G}\log(1/\delta)\Big{)}.$

###### Proof.

It is clear that $\mathbb{E}_{i_{t}}[\xi_{t}]=0$ and

$\big{|}\xi_{t}\big{|}\leq\|\mathbf{w}-\mathbf{w}_{t}\|_{\infty}\|\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}-\mathbb{E}_{i_{t}}[\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}]\|_{1}\\\
\leq 2(R+\|\mathbf{w}\|_{\infty})\widetilde{G}.$

Furthermore, there holds

$\displaystyle\mathbb{E}_{i_{t}}[\xi_{t}^{2}]$
$\displaystyle\leq\frac{1}{d}\sum_{i=1}^{d}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{i}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i}\rangle^{2}$
$\displaystyle\leq\|\mathbf{w}-\mathbf{w}_{t}\|_{\infty}^{2}\frac{1}{d}\sum_{i=1}^{d}\|\nabla_{i}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i}\|_{1}^{2}$
$\displaystyle\leq\frac{(R+\|\mathbf{w}\|_{\infty})^{2}\|\nabla
F_{S}(\mathbf{w}_{t})\|_{2}^{2}}{d}$
$\displaystyle\leq\frac{(R+\|\mathbf{w}\|_{\infty})^{2}G_{2}^{2}}{d}.$

We can apply Lemma F.2 to derive the following inequality with probability at
least $1-\delta$

$\sum_{t=1}^{T}\xi_{t}\leq\frac{\rho
T(R+\|\mathbf{w}\|_{\infty})G_{2}^{2}}{2\widetilde{G}d}+\frac{2(R+\|\mathbf{w}\|_{\infty})\widetilde{G}\log\frac{1}{\delta}}{\rho}.$

The stated inequality then follows with probability at least $1-\delta$ by
taking
$\rho=\min\big{\\{}\frac{2\widetilde{G}\sqrt{d\log(1/\delta)}}{\sqrt{T}G_{2}},1\big{\\}}$.
∎

######  Lemma F.4.

Let Assumptions 1, 2, 3, 5 hold. Let $\\{\mathbf{w}_{t}\\}$ be produced by (2)
with $\eta_{t}=\eta\leq 2/\widetilde{L}$ and $\delta\in(0,1)$. If
$\|\mathbf{w}_{t}\|_{2}\leq R$, then the following inequality holds with
probability at least $1-\delta$

$F_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w})\leq\frac{d}{T}\Big{(}F_{S}(\mathbf{w}_{1})+(2\eta)^{-1}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}\Big{)}\\\
+2(R+\|\mathbf{w}\|_{\infty})\Big{(}G_{2}\sqrt{dT^{-1}\log(1/\delta)}+\widetilde{G}dT^{-1}\log(1/\delta)\Big{)}.$

###### Proof of Lemma F.4.

As a combination of (E.1) and (E.3), we derive

$\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}\leq\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}+2\eta_{t}F_{S}(\mathbf{w}_{t})-2\eta_{t}F_{S}(\mathbf{w}_{t+1})\\\
+2\eta_{t}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\rangle$

Note

$\mathbb{E}_{i_{t}}\big{[}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{i_{t}}F_{S}(\mathbf{w}_{t})\mathbf{e}_{i_{t}}\rangle\big{]}=\\\
\frac{1}{d}\langle\mathbf{w}-\mathbf{w}_{t},\nabla
F_{S}(\mathbf{w}_{t})\rangle\leq\frac{F_{S}(\mathbf{w})-F_{S}(\mathbf{w}_{t})}{d}$

and $\eta=\eta_{t}$ for all $t$. Therefore, there holds

$\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}\leq\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}+2\eta
F_{S}(\mathbf{w}_{t})-2\eta F_{S}(\mathbf{w}_{t+1})\\\ +2\eta
d^{-1}(F_{S}(\mathbf{w})-F_{S}(\mathbf{w}_{t}))+2\eta\xi_{t},$

where we introduce $\\{\xi_{t}\\}$ in (F.2). Taking a summation of the above
inequality then gives

$\sum_{t=1}^{T}d^{-1}(F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}))\leq
F_{S}(\mathbf{w}_{1})\\\
+(2\eta)^{-1}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}+\sum_{t=1}^{T}\xi_{t}.$

It then follows from Lemma F.3 that the following inequality holds with
probability at least $1-\delta$

$\sum_{t=1}^{T}d^{-1}(F_{S}(\mathbf{w}_{t})-F_{S}(\mathbf{w}))\leq
F_{S}(\mathbf{w}_{1})+(2\eta)^{-1}\|\mathbf{w}_{1}-\mathbf{w}\|_{2}^{2}\\\
+2(R+\|\mathbf{w}\|_{\infty})\Big{(}G_{2}\sqrt{d^{-1}T\log(1/\delta)}+\widetilde{G}\log(1/\delta)\Big{)}.$

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

Putting the above optimization bounds and uniform stability bounds together,
we now present the proof of Theorem 11 on generalization bounds with high
probability.

###### Proof of Theorem 11.

Let $A(S)=\bar{\mathbf{w}}_{T}$. Then it follows from the convexity of norm
and Theorem 5 that $A$ is
$\frac{2G_{2}\widetilde{G}}{n}\sum_{t=1}^{T}\eta_{t}$-uniformly stable. This
together with Lemma F.1 gives the following inequality with probability at
least $1-\delta/3$

$\big{|}F(\bar{\mathbf{w}}_{T})-F_{S}(\bar{\mathbf{w}}_{T})\big{|}\\\
=O\Big{(}\frac{T\log
n\log(1/\delta)}{n}+Rn^{-\frac{1}{2}}\sqrt{\log(1/\delta)}\Big{)}.$

By Lemma F.4 the following inequality holds with probability at least
$1-\delta/3$

$F_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*})=O\Big{(}\frac{d\log(1/\delta)}{T}+\sqrt{\frac{d\log(1/\delta)}{T}}\Big{)}.$

Furthermore, the standard Hoeffding’s inequality implies the following
inequality with probability at least $1-\delta/3$

$\big{|}F(\mathbf{w}^{*})-F_{S}(\mathbf{w}^{*})\big{|}=O\big{(}\sqrt{n^{-1}\log(1/\delta)}\big{)}.$

We can combine the above three inequalities together and get

$F(\bar{\mathbf{w}}_{T})-F(\mathbf{w}^{*})=O\Big{(}\frac{T\log
n\log(1/\delta)}{n}\\\
+\sqrt{n^{-1}\log(1/\delta)}+\sqrt{\frac{d\log(1/\delta)}{T}}\Big{)}.$

We choose $T\asymp
n^{\frac{2}{3}}d^{\frac{1}{3}}\log^{-\frac{2}{3}}n\log^{-\frac{1}{3}}(1/\delta)$
to get the stated bound with probability at least $1-\delta$. The proof is
complete. ∎