#  Select without Fear:
Almost All Mini-Batch Schedules Generalize Optimally

###### Abstract

We establish matching upper and lower generalization error bounds for mini-
batch Gradient Descent (GD) training with either deterministic or stochastic,
data-independent, but otherwise arbitrary batch selection rules. We consider
smooth Lipschitz-convex/nonconvex/strongly-convex loss functions, and show
that classical upper bounds for Stochastic GD (SGD) also hold verbatim for
such arbitrary nonadaptive batch schedules, including all deterministic ones.
Further, for convex and strongly-convex losses we prove matching lower bounds
directly on the generalization error uniform over the aforementioned class of
batch schedules, showing that all such batch schedules generalize optimally.
Lastly, for smooth (non-Lipschitz) nonconvex losses, we show that full-batch
(deterministic) GD is essentially optimal, among all possible batch schedules
within the considered class, including all stochastic ones.

Konstantinos E. Nikolakakis
---
<EMAIL_ADDRESS>
Amin Karbasi |
<EMAIL_ADDRESS>|  Dionysis Kalogerias
<EMAIL_ADDRESS>|

Keywords: Generalization Error, Minimax Bounds, Smooth Nonconvex/Convex
Optimization

##  1 Introduction

Stochastic gradient descent (SGD) constitutes one of the pillars of
optimization theory and practice, receiving widespread attention for more than
$60$ years. There is a long line of work focusing on optimization error and
convergence analysis of gradient-based algorithms. However, despite the
established success of GD and its variants in optimization, the generalization
abilities of gradient-based training schemes in the context of machine
learning are still not quite well-understood. The celebrated work of Hardt et
al. [20] on final iterate generalization bounds for standard SGD shed some
light on this issue by focusing on a canonical class of learning problems with
Lipschitz and smooth losses. Further, [20] also laid the foundation for
exploring generalization error guarantees for other variants of SGD including
SGD with early momentum [41], randomized coordinate descent [48], look-ahead
approaches [55], noise injection methods [50], and Stochastic Gradient with
Langevin Dynamics (SGLD) [40, 34, 29, 37, 10, 46, 47]. In parallel, a large
number of studies on algorithmic stability [14, 26, 21, 22, 24, 27, 56, 30,
28, 13, 32, 23, 11, 4, 25, 53, 38] emerged through the special connection
between uniform stability [12, 8] and generalization [7, 20].

In this work, we look at the generalization error of general mini-batch GD
training schemes (with no momentum and) with arbitrary data-independent batch
schedules (see Algorithm 1 and Definition 1 below for details). In a nutshell,
we extend classical upper bounds on the generalization error of SGD [20] to
all such general gradient based schemes, and derive matching, fully
parameterized lower bounds directly on the generalization error, showing
tightness of bounds and optimality of methods. A detailed statement of our
contributions, which are also summarized in Table 1, is as follows:

  * •

For smooth Lipschitz-convex/nonconvex/strongly-convex learning problems, we
establish sharp upper generalization error bounds for a large class of
gradient-based algorithms, namely those encompassing arbitrary stochastic or
deterministic, data-independent selection rules of any batch size (including
arbitrarily time varying batch schedules). In the case of Lipschitz (resp.
path-gradient-stable) and smooth (resp. strongly-)convex losses, our upper
bounds hold essentially verbatim to those in prior work [20], initially
developed for SGD with batch size $1$. Further, in constrast with [20], we
avoid a bounded loss assumption in the nonconvex case.

  * •

We establish minimax-optimal matching corresponding lower bounds that hold
uniformly over the whole class of algorithms under consideration (Definition
1) and depend explicitly on the parameters of the learning problem under
consideration (for instance Lipschitz and smoothness constants), the training
horizon and the step size. Our lower bounds confirm the sharpness of the
corresponding upper bounds, and characterize the optimal rate of algorithmic
generalization for each of the learning problem classes under study.

Generalization Rates for Gradient-Based Training — valid for all
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ —
---
Stepsize $\eta_{t}$ |  Upper Bound on |  |
$\stackrel{{\scriptstyle[}}{{(}}f,\mathcal{D})\in\mathcal{C}]{}{\sup}\\!|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|$ |  Lower Bound on |  |
$\stackrel{{\scriptstyle[}}{{(}}f,\mathcal{D})\in\mathcal{C}]{}{\sup}\\!|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|$ |  Problem Class $\mathcal{C}$ |  |
$\eta_{t}\leq 2/\beta$ |  $\displaystyle{\frac{2L^{2}}{n}\sum^{T}_{t=1}\eta_{t}}$ |  $\displaystyle{\frac{L^{2}}{2n}\sum^{T}_{t=1}\eta_{t}}$ |  Convex
$L$-Lipschitz |  |  |
$\beta$-Smooth |  |  |
$\eta_{t}\leq C/t$, $C<1/\beta$ |  $\dfrac{2C(1+\frac{1}{C\beta})e^{C\beta}L^{2}T^{C\beta}}{n}$ |  OPEN |  Nonconvex
$L$-Lipschitz |  |  |
$\beta$-Smooth |  |  |
$\eta_{t}\leq c/\beta t$, $c\leq 1$ |  $\mathcal{O}\left(\dfrac{T^{c}\sqrt{\log(T)}}{n}\right)$ ([39], GD) |  $\dfrac{(T+1)^{\log(1+c)}-1}{2n}$ |  Nonconvex
$\beta$-Smooth |  |  |
$\eta_{t}=\eta\in[\ell_{1},\ell_{2}]$ |  |  |
$\ell_{1}\triangleq 2/\gamma(T+1)$ |  |  |
$\ell_{2}\triangleq 1/(\beta+\gamma)$ |  $\dfrac{4{L}^{2}}{n\gamma}$ |  $\hskip 6.0pt\dfrac{L^{2}}{32\gamma n}$ |  $\gamma$-strongly-convex
$\beta$-Smooth |  |  |
$L$-path-Lipschitz |  |  |
Table 1: For certain stepsize choices, uniform over the algorithm class
$\mathcal{A}(\eta_{t},T)$ (see Definition 1) upper and lower bounds on the
worst-case generalization error
$\sup_{(f,\mathcal{D})\in\mathcal{C}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|$
appear in the second and third columns, respectively, where the class of
learning problems $\mathcal{C}$ under consideration appears in the last
column; here, $f$ and $\mathcal{D}$ denote the loss function and data
distribution, respectively, and $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$.
All colored boxes indicate our contributions, whereas the upper bound for GD
on nonconvex smooth losses is established in prior work [39]. Establishing a
lower bound for the class of Lisphitz and smooth nonconvex losses remains an
open problem left for future work.

  * •

For Lipschitz (resp. path-gradient-stable) and smooth (resp. strongly-)convex
losses, we show that all mini-batch GD methods with data-independent batch
schedules generalize optimally. This fact in particular rigorously implies no
competitive advantage of stochastic training over deterministic training, for
the aforementioned class of learning problems. In other words, deterministic
training provably performs as optimally as stochastic training in terms of
generalization performance.

  * •

In the same spirit, we show that full-batch (deterministic) GD is optimal
within the class of smooth (and possibly non-Lipschitz nonconvex) losses. In
fact, our lower bound essentially matches the upper bound from our prior work
in [39]. While optimality of full-batch GD training within the class of smooth
(possibly non-Lipschitz, nonconvex) losses is established in this work,
whether stochastic training is also optimal in the setting remains an open
problem.

###  1.1 Comparison with Prior Works

First, we explain how our analysis provides optimal generalization error rates
for general data-independent batch schedules, while standard techniques from
prior works fail in this respect, namely the main technical approach taken in
the seminal work of Hardt et al. in [20]. Then we compare results from prior
works with ours, also commenting on the now provable fact that stochastic
training has essentially no competitive advantage against deterministic
training, under very general assumptions. Finally, we provide a detailed
discussion regarding the lower bounds developed in this work, and how they are
positioned within the related literature.

####  1.1.1 Suboptimality of Uniform Stability

We begin by demonstrating that the uniform stability approach as well as the
core proof technique devised in [20] (as expected) result in vacuous bounds
for a non-negligible set of nontrivial training algorithms. At the same time,
the on-average stability approach advocated in this work produces optimal (and
thus correct) bounds, uniformly within the postulated class of algorithms.
Even though both uniform and on-average stability result in tight bounds for
vanilla SGD [27], uniform stability “throws away too much structure to start
with” and is thus inadequate for analyzing other common batch-schedules and
variants of (S)GD. To illustrate this further with a simple argument, we prove
here that the uniform stability approach of [20] indeed fails for the
deterministic incremental (round-robin) gradient method [42, Algorithm 3], [6,
5, 36, 17, 16], which among various other applications has been used to train
neural networks for more than $40$ years. Later, we demonstrate that the proof
technique utilized in [20] also gives vacuous generalization bounds for
general Lipschitz and smooth convex and strongly-convex losses (see Appendix
C).

Specifically, consider the loss $f(w,z)=\sum^{d}_{k=1}w^{k}z^{k}$, with
$w\in\mathbb{R}^{d}$ and ($d$ dimensional) examples
$z_{i}\triangleq(z^{1}_{i},z^{2}_{i},\ldots,z^{d}_{i})\in\\{-1,+1\\}^{d},i\in\\{1,\ldots,n\\}$.
Then, for the incremental gradient method (see, e.g., [42, Algorithm 3]),
denoted here as a map $A(\cdot)$ on example sequences, and for neighboring
example sequences $S,S^{\prime}$ [20], the uniform stability constant of [20,
Theorem 2.2] may be calculated explicitly (while assuming a decreasing step
size sequence which restarts after each epoch to the initial value $\eta_{1}$)
as

$\displaystyle\sup_{S,S^{\prime},z}\mathbb{E}_{A}[f(A(S);z)-f(A(S^{\prime});z)]$
$\displaystyle=\sup_{S,S^{\prime},z}[f(A(S);z)-f(A(S^{\prime});z)]$ (1)
$\displaystyle=\sup_{S,S^{\prime},z}\sum^{d}_{k=1}(A^{k}(S)-A^{k}(S^{\prime}))z^{k}$
$\displaystyle=\sup_{S,S^{\prime},z}\sum^{d}_{k=1}\left(w^{k}_{1}-\sum^{T}_{t=1}\eta_{t}\sum_{\mathcal{Z}\in
J_{t}}\mathcal{Z}^{k}-w^{k}_{1}+\sum^{T}_{t=1}\eta_{t}\sum_{\mathcal{Z}\in
J^{\prime}_{t}}\mathcal{Z}^{k}\right)z^{k}$ (2)
$\displaystyle=\sup_{S,S^{\prime},z}\sum^{d}_{k=1}\sum^{T}_{t=1}\eta_{t}\left((z_{t}^{\prime})^{k}-z^{k}_{t}\right)z^{k}$
(3)
$\displaystyle=K\times\sup_{S,S^{\prime},z}\sum^{d}_{k=1}\eta_{1}\left((z_{1}^{\prime})^{k}-z^{k}_{1}\right)z^{k}=2Kd\eta_{1},$
(4)

where $J_{t},J^{\prime}_{t}$ are the batches at time $t$ from the sequences
$S,S^{\prime}$ respectively. Equality (3) comes from the size of the batch
$|J_{t}|=|J^{\prime}_{t}|=1$. Lastly, equality (4) holds for any
$K\in\mathbb{N}$ number of epochs, and the supremum is achieved for the
sequences sequences $S,S^{\prime}$ that differ in the first entry because the
step-size sequence is assumed non-decreasing (at each epoch). Evidently,
because the uniform stability is a constant independent of the number of
samples $n$, this approach fails completely to provide a meaningful
generalization bound, even in this simple example. In fact, the optimal
generalization bound for the incremental gradient method in this case is
$\frac{2d}{n}\sum^{T}_{t=1}\eta_{t}$, for every choice of training horizon $T$
and stepsize (sequence) $\eta_{t}$. We refer the reader to Appendix C for a
more detailed and general comparison. It is also easy to see that the uniform
stability approach fails more generally within the general class of Lipschitz
and smooth losses by directly evaluating (1) (also see Appendix C).

Overall, it becomes plain that uniform stability constants in general cannot
be sufficient to characterize algorithmic generalization (except for certain
cases such as standard SGD studied in [20]). Rather than utilizing uniform
stability, in this work we show that the (or a) correct technical approach is
that of bounding the generalization error in terms of on-average algorithmic
stability, providing tight bounds which characterize algorithm generalization
in a minimax-optimal sense (see Section 1.5).

####  1.1.2 Stochastic Training is not Necessary

Many prior works consider stochastic batch scheduling and some even suggest
that stochasticity is necessary for good generalization [20, 9]. However more
recent experimental [15] and theoretical [39] works suggest that deterministic
training (e.g. full-batch GD) may be at least as good as stochastic training.
Our findings imply that, at least within the learning settings considered,
randomization in training provably offers no competitive advantage as compared
with deterministic training in terms of the achievable generalization error
(of course, the situation is different as far as the corresponding
optimization error is concerned [49]). An important implication of our results
is that different mini-batch schedules mainly affect the optimization error
(as appears in [49]) rather than the generalization error for the class of
Lipschitz and smooth losses. We also note that in the smooth (possibly non-
Lipschitz, nonconvex) case, the question of optimality of batch schedules
other than that of full-batch GD (which we prove to be optimal) remains open.

From a technical standpoint, our generalization error analysis in this paper
is developed in a fully unified manner relative to the choice of the
particular batch schedule. More specifically, we establish bounds which are
uniform over the class of mini-batch GD training schemes with either
deterministic or stochastic, data-independent, but otherwise arbitrary batch
schedules. This class of batch schedules includes both deterministic and
stochastic training as special cases. For instance, the set of algorithms
supported by our analysis includes but is not limited to classical SGD with
mini-batch of any size $m$, full-batch GD, round-robin deterministic batch
selection, SGD with random reshuffling [18], SGD with single shuffling, and
incremental gradient methods [42, 35, 49, 33, 16].

####  1.1.3 Lower Generalization Error Bounds (over Data-Independent Batch
Schedules)

To evaluate the performance of the algorithms under consideration, we are
interested in deriving minimax —over mini-batch GD algorithms ($\inf$) and
learning problem instances ($\sup$)— lower bounds directly on the
generalization error. Prior works have already developed lower bounds on
uniform stability constants (while taking a supremum over the data-set) for
non-smooth losses [4] and Lipschitz-smooth losses [54], for SGD and full-batch
GD. However, lower bounds on uniform stability do not imply a lower bound on
the generalization error; as also demonstrated above, uniform stability is
sufficient but not necessary for generalization. Further, recent work on the
class of smooth convex losses [52] considered the construction of specific
–and not fully parameterized– problem instances to derive lower bounds on the
corresponding excess risk (i.e., generalization $+$ optimization), and –in
this sense– showed tightness for the cases of SGD [27, 43] and full-batch GD
[39]. The construction of an elaborate example to lower bound the excess risk
of the (S)GD algorithm also appeared in [2, 1]. However, that construction
consists of a single instance of a Lipschitz non-smooth convex loss with
dimension $d\gtrsim 2^{n}$, where $n$ is the data-set size; this example is
not only restrictive but also not reasonable because the number of dimensions
is exponential in comparison with the size of data-set. On the other hand, for
Lipschitz possibly non-smooth generalized linear models, [3] recently shows
that GD is optimal.

In contrast with prior works, we develop lower bounds over classes of learning
problems parameterized by Lipschitzness and smoothness constants, as well as
data-set size, step-size and training horizon. Our lower bounds hold over
these parameterized classes of learning problems, uniformly over stochastic
and deterministic gradient-based algorithms. Our lower bounds essentially
match our upper bounds, as can be seen in the third column of Table 1, for
every choice of the set of related parameters (up to constants or
inconsequential factors, e.g., $\sqrt{\log}$). As an additional benefit of our
approach, while information theoretic generalization error bounds are
reportedly not tight for final-iterate algorithmic generalization [31, 19,
51], here we confirm that stability analysis [7, 20] is provably tight for
large classes of loss functions and gradient-based algorithms, very relevant
for practical use. At this point, it is worth mentioning that our results
(optimal upper and lower bounds) also hold for the popular (S)GLD (implemented
using any data-independent batch schedule), which has been widely studied in
the context of information theoretic algorithmic generalization.

Consequently, (on-average) stability seems most probably one right approach to
study algorithmic generalization. As also stated above, through our minimax
lower bounds we prove the simultaneous optimality (or equivalence) of all
mini-batch GD schemes with data-independent batch schedules for Lipschitz,
smooth and convex, and for smooth and strongly-convex losses. For learning
problems involving smooth and possibly nonconvex losses, we show that the
(deterministic) full-batch GD algorithm is essentially optimal, among all
possible gradient-based schemes considered (with possibly randomized batch
schedules).

###  1.2 Preliminaries

Let
$z_{1},z_{2},\ldots,z_{n},z^{\prime}_{1},z^{\prime}_{2},\ldots,z^{\prime}_{n}$
be i.i.d random variables, with respect to an unknown distribution
$\mathcal{D}$. For brevity, define the sets
$S\triangleq(z_{1},z_{2},\ldots,z_{n})$ and
$S^{(i)}\triangleq(z_{1},z_{2},\ldots,z^{\prime}_{i},\ldots,z_{n})$ that
differ at the $i^{\mathrm{th}}$ random element, and let us denote
$S^{\prime}\triangleq(z^{\prime}_{1},z^{\prime}_{2},\ldots,z^{\prime}_{n})$.
Let $f(w,z)$ be the loss at the point $w\in\mathbb{R}^{d}$ for some example
$z\in\mathcal{Z}$. Given a data-set $\\{z_{i}\\}^{n}_{i=1}$, our goal is to
find the parameters $w^{*}$ of a learning model such that
$w^{*}\in\arg\min_{w}R(w)$, where
$R(w)\triangleq\mathbb{E}_{Z\sim\mathcal{D}}[f(w,Z)]$ and $R^{*}\triangleq
R(w^{*})$. Since the distribution $\mathcal{D}$ is not known, we consider the
empirical risk

$\displaystyle R_{S}(w)\triangleq\frac{1}{n}\sum^{n}_{i=1}f(w;z_{i}).$ (5)

The corresponding empirical risk minimization (ERM) problem is to find
$w^{*}_{S}\in\arg\min_{w}R_{S}(w)$ (assuming minimizers on data exist for
simplicity). For a (stochastic) algorithm $A$ with input $S$, and output
$A(S)$, the generalization error $\epsilon_{\mathrm{gen}}$ is defined as the
difference between the empirical and population loss

$\displaystyle\epsilon_{\mathrm{gen}}$
$\displaystyle\triangleq\mathbb{E}_{S,A}[R(A(S))-R_{S}(A(S))]=\mathbb{E}_{S,A,z^{\prime}_{i}}\Big{[}f(A(S);z^{\prime}_{i})-\frac{1}{n}\sum^{n}_{i=1}f(A(S);z_{i})\Big{]}.$
(6)

We continue by introducing the class of gradient-based algorithms that we
consider in this work.

1:data-set $S=(z_{1},z_{2},\ldots,z_{n})\in\mathcal{Z}^{n}$, horizon $T$,
batch-size $m$, stepsize $\\{\eta_{t}\\}^{T}_{t=1}$, loss function
$f:\mathbb{R}^{d}\times\mathcal{Z}\rightarrow\mathbb{R}^{+}$.

2:Choose initial point $w_{1}\in\mathbb{R}^{d}$, possibly random but
independent of $\cal D$.

3:for $t=1$ to $T$ do

4: Choose $m\leq n$ distinct indices
$\\{k^{t}_{1},k^{t}_{2},\ldots,k^{t}_{m}\\}\subseteq[n]$ according to a rule
$\mathcal{R}$ (at $t$), possibly randomized but independent of $\mathcal{D}$.

5: Set mini-batch
$J_{t}\leftarrow\\{z_{k^{t}_{1}},z_{k^{t}_{2}},\ldots,z_{k^{t}_{m}}\\}$.

6: $w_{t+1}=w_{t}-\frac{\eta_{t}}{m}\sum_{z\in J_{t}}\nabla f(w_{t},z)$.

7:return $W_{T+1}$

Algorithm 1 $A_{\mathcal{R}}$: Mini-batch (S)GD with Generic Batch Schedules

###  1.3 (Stochastic) Gradient Descent with Arbitrary Batch Schedules

We study a wide class of mini-batch GD training algorithms, for any mini-batch
selection rule (deterministic or stochastic) that is independent of the input
data-set. For instance, this class includes the classical SGD with mini-batch
of any size $m$, full-batch GD, deterministic approaches of sequential batch
selection rules as well as randomized selection rules with arbitrary
distribution for the batch choice (not necessarily identically distributed
choices with respect to each sample), round-robin with deterministic
selection, SGD with random reshuffling, SGD with single shuffling, or
incremental gradient methods [42]. In all cases, the mini-batch selection
policy at time $t$ is independent of input data-set. The size of the mini-
batch is $m$ and is considered to be fixed. Our analysis can be extended to
time dependent batch selection size $m_{t}$ without affecting the analysis or
the results, however, we consider it fixed for simplicity. A formal definition
of the class of algorithms considered is as follows (see also the Algorithm
1).

######  Definition 1 (Class of Algorithms)

Given the number of iterations $T$ and a step-step size sequence
$\\{\eta_{t}\\}^{T}_{t=1}$, we define the set of algorithms given by Algorithm
1 for all batch-selection rules $\mathcal{R}$ (independent of the input data-
set) as***We implicitly assume an underlying probability triplet on a sample
space $\Omega$.

$\displaystyle\mathcal{A}(\eta_{t},T)\triangleq\\{A_{\mathcal{R}}\textrm{ as
in Algorithm
\ref{alg:gen_SGD}}\,|\,\mathcal{R}:\Omega\rightarrow\\{1,2,\ldots,n\\}^{m\times
T},\,\mathbb{P}_{(\mathcal{R},S)}=\mathbb{P}_{\mathcal{R}}\mathbb{P}_{S}\\}.$
(7)

In other words, the class of algorithms $\mathcal{A}(\eta_{t},T)$ contains
stochastic and deterministic batch selection rules such that each example may
appear at most once in the batch $J_{t}$ with any probability (invariant of
the data-set). For the rest of the paper we write $A_{\mathcal{R}}$ to denote
an algorithm in the set $\mathcal{A}(\eta_{t},T)$.

###  1.4 On-Average Stability

A key part of our analysis is the derivation of upper bounds by considering
on-average algorithmic stability, namely
$\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|$.
Through on-average stability we show upper bounds for the generalization error
by using a unified analysis among all algorithms $A_{\mathcal{R}}$ within
$\mathcal{A}(\eta_{t},T)$. Specifically, we develop a uniform stability
analysis for all data-sets $S$ and selection rules $\mathcal{R}$. In contrast
to prior work [20] that considers only uniformity with respect to the data-
set, we extend the generalization error upper bounds for a general class of
gradient-based algorithms ($\mathcal{A}(\eta_{t},T)$).

In line with standard prior work, for convex and nonconvex losses we assume
that the loss is uniformly Lipschitz. For strongly-convex losses, the
Lipschitz assumption does not hold and we instead consider a relaxed path-
boundedness assumption on the loss gradients, introduced later to avoid
clutter (see Section 5).

######  Assumption 1 (Lipschitz Loss)

There exists a constant $L\geq 0$, such that for all $w,u\in\mathbb{R}^{d}$
and $z\in\mathcal{Z}$, $\|f(w,z)-f(u,z)\|_{2}\leq L\|w-u\|_{2}$.

Through Assumption 1, equation (6) gives an upper bound on the generalization
error as follows

$\displaystyle|\epsilon_{\mathrm{gen}}|$
$\displaystyle\triangleq\Big{|}\mathbb{E}_{S,z^{\prime}_{i},\mathcal{R}}[f(A_{\mathcal{R}}(S);z^{\prime}_{i})]-\mathbb{E}_{S,\mathcal{R}}\Big{[}\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);z_{i})\Big{]}\Big{|}$
$\displaystyle=\Big{|}\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S,z^{\prime}_{i},\mathcal{R}}[f(A_{\mathcal{R}}(S);z^{\prime}_{i})]-\mathbb{E}_{S,S^{\prime},\mathcal{R}}\Big{[}\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S^{(i)});z^{\prime}_{i})\Big{]}\Big{|}$
(8)
$\displaystyle=\Big{|}\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S,S^{\prime},\mathcal{R}}[f(A_{\mathcal{R}}(S);z^{\prime}_{i})]-\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[f(A_{\mathcal{R}}(S^{(i)});z^{\prime}_{i})\right]\Big{|}$
(9)
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[|f(A_{\mathcal{R}}(S);z^{\prime}_{i})-f(A_{\mathcal{R}}(S^{(i)});z^{\prime}_{i})|\right]$
(10) $\displaystyle\leq
L\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\right].$
(11)

While (9) and (11) have been considered in prior works [20, 27], we derive
uniform upper bounds on the average stability
$\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|$ for
any batch selection rule $\mathcal{R}$, thus extending generalization error
bounds for the SGD to the general class of algorithms
$\mathcal{A}(\eta_{t},T)$.

###  1.5 Minimax Lower Bounds on Algorithmic Generalization

Conversely, we establish minimax lower bounds within the class of algorithms
$\mathcal{A}(\eta_{t},T)$ for all cases of convex, nonconvex and strongly-
convex losses. In fact, we see the generalization error as a function of a
learning problem $(f,\mathcal{D})$ in a certain class $\mathcal{C}$ and an
algorithm $A_{\mathcal{R}}$ in the set $\mathcal{A}(\eta_{t},T)$, namely
$\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})$. Our purpose then is
to discover minimax bounds on the generalization error
$\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})$:

$\displaystyle\sup_{(f,\mathcal{D})\in\mathcal{C}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\geq\boxed{\boldsymbol{?}}\,,\,\,\,\forall
A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)\iff\inf_{A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)}\sup_{(f,\mathcal{D})\in\mathcal{C}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\geq\boxed{\boldsymbol{?}}\,,$

where the quantity $\boxed{\boldsymbol{?}}$ is independent of the choice of
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$. Provided matching upper bounds,
in this way we show tightness and of the generalization error within a large
class of learning problems and algorithms. Specifically, for Lipschitz smooth
convex losses we prove that any algorithm within the class
$\mathcal{A}(\eta_{t},T)$ is optimal and achieves rates identical to standard
rates for the SGD as appeared in prior work [20]. For Lipschitz and smooth
nonconvex losses we establish an upper bound which also matches [20] but holds
uniformly over all algorithms in $\mathcal{A}(\eta_{t},T)$, as well as a lower
bound for the more general class of smooth nonconvex losses. In the latter
case, our minimax lower bound almost matches upper bounds of full-batch GD
from prior work [39] showing that in fact full-batch GD is essentially optimal
within this class of learning problems and algorithms. Lastly, for strongly-
convex losses we prove that all algorithms in $\mathcal{A}(\eta_{t},T)$ are
optimal within the class of learning problems involving path-Lipschitz smooth
losses (see Section 5 for precise definitions).

##  2 Uniformity with Respect to the Selection Rule

We start by proving two key properties (Lemma 2 and Lemma 3) related to on-
average stability, which hold uniformly with respect to any randomized or
deterministic batch selection rule $\mathcal{R}$ (Definition 1). Let $J_{t}$
be the mini-batch at time $t$ from an input sequence
$S\triangleq(z_{1},z_{2},\ldots,z_{n})$ for some arbitrarily chosen sequence
of indices $\\{k^{t}_{1},k^{t}_{2},\ldots,k^{t}_{m}\\}\subseteq[n]$, and
$J^{(i)}_{t}$ be the mini-batch at time $t$ from an input sequence
$S^{(i)}\triangleq(z_{1},z_{2},\ldots,z^{\prime}_{i},\ldots,z_{n})$ for the
same arbitrarily chosen sequence of indices
$\\{k^{t}_{1},k^{t}_{2},\ldots,k^{t}_{m}\\}$. The first result is on counting
the number of different batches $J^{(i)}_{t}$ compared to $J_{t}$ for
$i\in\\{1,\ldots,n\\}$. The proof is based on the observation that for any
(randomized) data-independent selection rule of mini-batch with size $m$ and
each time $t\leq T$, at most $m$ out of $n$ batches $J^{(i)}_{t}$
($i\in\\{1,\ldots,n\\}$) differ with $J_{t}$ (at one example).

Specifically, for the rest of the paper we use the notation $\\{J_{t}\neq
J^{(i)}_{t}\\}$ to denote the event where the selection rule chooses the
$i^{\text{th}}$ entry of the respective data-set to be included in the mini-
batch (the mini-batches $J_{t}$ and $J^{(i)}_{t}$ contain the i.i.d. random
variables $z_{i}$ and $z^{\prime}_{i}$ at time $t$, respectively†††Although
the probability of the event $\\{z_{i}=z^{\prime}_{i}\\}$ is not zero in
general, we use the notation $\\{J_{t}\neq J^{\prime}_{t}\\}$ suggestively. We
handle the event $\\{z_{i}=z^{\prime}_{i}\\}$ in the analysis when necessary;
see also Lemma 3 and the proof of Lemma 3.), and $\\{J_{t}\equiv
J^{(i)}_{t}\\}$ to denote the complementary event, i.e., when the selection
rule does not choose the $i^{\text{ith}}$ entry at time $t$. The formal
statement of the first lemma follows.

###### Lemma 2

Let $\mathcal{R}$ be any (randomized) selection rule of a sequence of mini-
batches with size $m$, namely $\\{\mathcal{R}_{t}\\}^{T}_{t=1}$ (independent
of the input data-set). Let $J_{t}$ be the mini-batch at time $t$ from an
input sequence $S\triangleq(z_{1},z_{2},\ldots,z_{n})$ for some arbitrarily
chosen indices $\\{k^{t}_{1},k^{t}_{2},\ldots,k^{t}_{m}\\}\subseteq[n]$, and
$J^{(i)}_{t}$ be the mini-batch at time $t$ from an input sequence
$S^{(i)}\triangleq(z_{1},z_{2},\ldots,z^{\prime}_{i},\ldots,z_{n})$ for the
same indices with those of $J_{t}$ namely
$\\{k^{t}_{1},k^{t}_{2},\ldots,k^{t}_{m}\\}$. Then

$\displaystyle\sum^{n}_{i=1}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}=m,\quad\text{with probability }1.$ (12)

##### Proof of Lemma 2

The selection rule at time $t$ corresponds to some selection of $m$ distinct
indices from the set of integers $\\{1,2,\ldots,n\\}\triangleq[n]$. Let that
choice be $\\{k_{1},k_{2},\ldots,k_{m}\\}\triangleq[K]_{m}$, then notice that
$\mathds{1}_{J_{t}\neq J^{(i)}_{t}}=1$ if and only if $i\in[K]_{m}$, and
$\mathds{1}_{J_{t}\neq J^{(i)}_{t}}=0$ if and only if $i\notin[K]_{m}$. This
claim can be directly showed through Table 2, since $S$ and $S^{(i)}$ differ
in exactly one entry for all $i\in[n]$. Further the set $[K]_{m}$ contains
exactly $m$ distinct elements, thus we conclude that
$\sum^{n}_{i=1}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}=m$, which completes the
proof. $\Box$

We proceed by extending the growth recursion of the SGD with mini-batch size
$1$ [20, Lemma 2.4] to the generalized batch selection set of algorithms
$\mathcal{A}(\eta_{t},T)$ and for any mini-batch of size $m$.

$S$ | $z_{1}$ | $z_{2}$ | $z_{3}$ | $\cdots$ | $z_{i-1}$ | $z_{i}$ | $z_{i+1}$ | $\cdots$ | $z_{i-1}$ | $z_{n}$
---|---|---|---|---|---|---|---|---|---|---
$S^{(1)}$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{1}$ | $z_{2}$ | $z_{3}$ | $\cdots$ | $z_{i-1}$ | $z_{i}$ | $z_{i+1}$ | $\cdots$ | $z_{i-1}$ | $z_{n}$
$S^{(2)}$ | $z_{1}$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{2}$ | $z_{3}$ | $\cdots$ | $z_{i-1}$ | $z_{i}$ | $z_{i+1}$ | $\cdots$ | $z_{i-1}$ | $z_{n}$
$S^{(3)}$ | $z_{1}$ | $z_{2}$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{3}$ | $\cdots$ | $z_{i-1}$ | $z_{i}$ | $z_{i+1}$ | $\cdots$ | $z_{i-1}$ | $z_{n}$
$\vdots$ |  |  |  | $\ddots$ |  |  |  |  |  | $\vdots$
$S^{(i-1)}$ | $z_{1}$ | $z_{2}$ | $z_{3}$ | $\cdots$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{i-1}$ | $z_{i}$ | $z_{i+1}$ | $\cdots$ | $z_{i-1}$ | $z_{n}$
$S^{(i)}$ | $z_{1}$ | $z_{2}$ | $z_{3}$ | $\cdots$ | $z_{i-1}$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{i}$ | $z_{i+1}$ | $\cdots$ | $z_{i-1}$ | $z_{n}$
$S^{(i+1)}$ | $z_{1}$ | $z_{2}$ | $z_{3}$ | $\cdots$ | $z_{i-1}$ | $z_{i}$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{i+1}$ | $\cdots$ | $z_{i-1}$ | $z_{n}$
$\vdots$ |  |  |  |  |  |  |  | $\ddots$ |  | $\vdots$
$S^{(n-1)}$ | $z_{1}$ | $z_{2}$ | $z_{3}$ | $\cdots$ | $z_{i-1}$ | $z_{i}$ | $z_{i+1}$ | $\cdots$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{n-1}$ | $z_{n}$
$S^{(n)}$ | $z_{1}$ | $z_{2}$ | $z_{3}$ | $\cdots$ | $z_{i-1}$ | $z_{i}$ | $z_{i+1}$ | $\cdots$ | $z_{n-1}$ | $\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z^{\prime}_{n}$

Table 2: Graphical aid for the proof of Lemma 2. Observe that the data-set
instances $S$ and $S^{(i)}$ differ in exactly one (at most) entry for all
$i\in[n]$.

###  2.1 Growth Recursion for Generalized Batch Selection

Next, we show the growth recursion lemma similar to [20], which applies to any
algorithm in the set $\mathcal{A}(\eta_{t},T)$ (Definition 1) with mini-batch
size $m$. We consider a uniform smoothness assumption on the loss with respect
to the set of examples, identical to the settings of the prior work [20, 27,
28, 43, 44, 45].

######  Assumption 2 ($\beta$-Smooth Loss)

There exists a constant $\beta\geq 0$, such that for all
$w,u\in\mathbb{R}^{d}$ and $z\in\mathcal{Z}$,
$\|\nabla_{w}f(w,z)-\nabla_{u}f(u,z)\|_{2}\leq\beta\|w-u\|_{2}$.

We define the update map for any $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$
at time $t$ as $G_{J_{t}}(w)\triangleq w-\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\nabla f(w,z)$ (see Algorithm 1). Leveraging the Lipschitzness and
smoothness of the loss we may derive a growth recursion that holds universally
for all gradient-based algorithms in $\mathcal{A}(\eta_{t},T)$ with a mini-
batch of size $m$. For the case of (necessarily non-Lipschitz) strongly-convex
losses we establish the growth recursion seperately in Section 5, to avoid
clutter and keep the exposition concise.

######  Lemma 3 (Growth Recursion)

Choose an algorithm $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$, let
$w_{1}=w^{(i)}_{1}$ be any common starting point, and set
$w_{t+1}=G_{\\!J_{t}}(w_{t})$ and
$w^{(i)}_{t+1}=G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})$, $t\in\\{1,\ldots,T\\}$. Then
for any batch size $m\triangleq|J_{t}|=|J^{(i)}_{t}|$, any $t\geq 0$ and any
$i\in[n]$ the following recursions hold:

  * •

If the loss is convex, then

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\|G_{\\!J_{t}}(w_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|\leq\begin{cases}\|w_{t}-w^{(i)}_{t}\|&\mathrm{under}\text{
}\\{J_{t}\equiv J^{(i)}_{t}\\}\\\
\|w_{t}-w^{(i)}_{t}\|+\frac{2L}{m}\eta_{t}&\mathrm{under}\text{ }\\{J_{t}\neq
J^{(i)}_{t}\\}\end{cases}.$ (13)

  * •

If the loss is nonconvex, then

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\|G_{\\!J_{t}}(w_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|\leq\begin{cases}(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|&\mathrm{under}\text{
}\\{J_{t}\equiv J^{(i)}_{t}\\}\\\
(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|+\frac{2L}{m}\eta_{t}&\mathrm{under}\text{
}\\{J_{t}\neq J^{(i)}_{t}\\}\end{cases}.$ (14)

We prove Lemma 3 in Appendix A.1. We consider slightly different notation in
the statement of the growth recursion compared to [20, Lemma 2.5] by
considering the events $\\{J_{t}\neq J^{(i)}_{t}\\}$ and
$\\{J_{t}=J^{(i)}_{t}\\}$ that are complement to each other. This later
simplifies the proof of the stability recursion for any
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$.

##  3 Convex Loss

In this section we derive matching upper and lower generalization error bounds
for the class of learning problems with Lipschitz and smooth convex losses,
and for all algorithms $A_{\mathcal{R}}$ in the class
$\mathcal{A}(\eta_{t},T)$. We start by defining the class of learning problems
under consideration.

######  Definition 4 (Lipschitz and Smooth Convex Class)

For fixed $L>0$ and $\beta>0$, the class $\mathcal{C}^{L}_{\beta}$ contains
all learning problems $(f,\mathcal{D})$ with $L$-Lipschitz, $\beta$-smooth,
convex losses $f(\cdot,Z)$, $Z\sim\mathcal{D}$.

We proceed by providing the on-average stability guarantees for the learning
problems class $\mathcal{C}^{L}_{\beta}$. Recall that our results hold
uniformly over the class of algorithms $\mathcal{A}(\eta_{t},T)$.

######  Theorem 5 (Generalization Error Upper Bound—Convex Loss)

Choose $L>0$ and $\beta>0$. For any learning problem
$(f,\mathcal{D})\in\mathcal{C}^{L}_{\beta}$, and for any algorithm
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ with step-size $\eta_{t}<2/\beta$
and number of iterations $T$, on-average algorithmic stability is bounded as

$\displaystyle\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\leq\frac{2L}{mn}\sum^{T}_{t=1}\eta_{t}\sum^{n}_{i=1}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}$ $\displaystyle=\frac{2L}{n}\sum^{T}_{t=1}\eta_{t}.$

Additionally, for any algorithm $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ it
is true that

$\displaystyle\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{C}^{L}_{\beta}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\leq\frac{2L^{2}}{n}\sum^{T}_{t=1}\eta_{t}.$
(15)

We proceed with the proof of the theorem.

##### Proof of Theorem 5

Lemma 3 gives

$\displaystyle\|w_{t+1}-w^{(i)}_{t+1}\|$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|\mathds{1}_{J_{t}=J^{(i)}_{t}}+\|w_{t}-w^{(i)}_{t}\|\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}+\frac{2}{m}L\eta_{t}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}$
$\displaystyle=\|w_{t}-w^{(i)}_{t}\|+\frac{2}{m}L\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}.$

By solving the recursion we find

$\displaystyle\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\equiv\|w_{T+1}-w^{(i)}_{T+1}\|$
$\displaystyle\leq\frac{2L}{m}\sum^{T}_{t=1}\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}\implies$
$\displaystyle\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|$
$\displaystyle\leq\frac{2L}{m}\sum^{T}_{t=1}\eta_{t}\left(\frac{1}{n}\sum^{n}_{i=1}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}\right).$ (16)

Inequality (16) and Lemma 2 give the on-average stability bound of the
statement. This and inequality (11) give the generalization error bound for
convex smooth and Lipschitz loss for the final iterate for any batch schedule
(see Algorithm 1), completing the proof. $\Box$

Note that Theorem 5 holds for any algorithm
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$, and extends established results
in prior works for the SGD with batch size $1$ [20]. Specifically, the
generalization error bound of Theorem 5 holds for general stochastic or
deterministic gradient schemes (Definition 1) and any batch size choice $m$.
Next, we present a matching lower bound on the generalization error for the
class of Lipschitz and smooth convex problems $\mathcal{C}^{L}_{\beta}$,
instance-wise relative to the parameters $L$ and $\beta$.

######  Theorem 6 (Generalization Error Lower Bound—Convex Loss)

Choose constants $L>0$, $\beta>0$, step size $\eta_{t}\leq 1/\beta$, number of
iterations $T$, data-set size $n$ and any initial point (independent of the
data-set). It is true that

$\displaystyle\inf_{A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)}\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{C}^{L}_{\beta}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\geq\frac{L^{2}}{2n}\sum^{T}_{t=1}\eta_{t}.$

To prove Theorem 6, we consider an $L$-Lipschitz, $\beta$-smooth convex loss
parameterized over $L,\beta>0$, and we find an explicit lower bound of the
generalization error for all the algorithmic instances
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ at the final iteration. We prove
Theorem 6 in Appendix A.2. As a consequence of the upper bound of the
generalization error in Theorem 5 and the minimax bound in Theorem 6 we
conclude that all algorithms in the set $\mathcal{A}(\eta_{t},T)$ are
simultaneously optimal with respect to the learning problem class
$\mathcal{C}^{L}_{\beta}$.

##  4 Nonconvex Loss

Herein, we show generalization error guarantees for learning problems with
general Lipschitz and/or smooth (possibly nonconvex) loss functions.
Specifically, we consider the class of Lipschitz and smooth losses for the
upper bounds of the generalization error. Then we provide minimax
generalization error bounds for smooth losses, and we show that in particular
full-batch GD is essentially optimal within this general class. The
definitions of the classes of learning problems considered here is as follows.

######  Definition 7 (Lipschitz and Smooth Class)

For fixed $L>0$ and $\beta>0$, the class $\mathcal{NC}^{L}_{\beta}$ contains
all learning problems $(f,\mathcal{D})$ with $L$-Lipschitz, $\beta$-smooth
non-convex losses $f(\cdot,Z)$, $Z\sim\mathcal{D}$.

Of course, for $L=\infty$ we obtain the class $\mathcal{NC}^{\infty}_{\beta}$
containing all $\beta$-smooth learning problems (with possibly nonconvex
loss). We proceed with the corresponding upper bound on the on-average
stability and generalization error within the class
$\mathcal{NC}^{L}_{\beta}$. Similarly to the convex case, the bounds apply
uniformly over the set of algorithms $\mathcal{A}(\eta_{t},T)$.

######  Theorem 8 (Generalization Error Upper Bound—Nonconvex Loss)

Choose $L>0$ and $\beta>0$. For any learning problem
$(f,\mathcal{D})\in\mathcal{NC}^{L}_{\beta}$ and for any algorithm
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ with step-size $\eta_{t}$ and
number of iterations $T$, it holds that

$\displaystyle\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\leq\frac{2L}{n}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1+\beta\eta_{j}).$

In particular, for any algorithm $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$
with a decreasing step-size $\eta_{t}\leq C/t$ where $C<1/\beta$, it is true
that

$\displaystyle\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{NC}^{L}_{\beta}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\leq\frac{2Ce^{C\beta}L^{2}T^{C\beta}}{n}\min\Big{\\{}1+\frac{1}{C\beta},\log(eT)\Big{\\}}.$
(17)

##### Proof of Theorem 8

Lemma 3 gives

$\displaystyle\|w_{t+1}-w^{(i)}_{t+1}\|$
$\displaystyle\leq(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|\mathds{1}_{J_{t}=J^{(i)}_{t}}+\left(1+\beta\eta_{t}\right)\|w_{t}-w^{(i)}_{t}\|\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}+\frac{2}{m}L\eta_{t}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}$
$\displaystyle\leq(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|+\frac{2}{m}L\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}.$

By solving the recursion we find

$\displaystyle\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\equiv\|w_{T+1}-w^{(i)}_{T+1}\|$
$\displaystyle\leq\frac{2L}{m}\sum^{T}_{t=1}\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}\prod^{T}_{j=t+1}(1+\beta\eta_{j})\implies$
$\displaystyle\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|$
$\displaystyle\leq\frac{2L}{m}\sum^{T}_{t=1}\eta_{t}\left(\frac{1}{n}\sum^{n}_{i=1}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}\right)\prod^{T}_{j=t+1}(1+\beta\eta_{j}).$ (18)

The inequality (11) together with (18) and Lemma 2 give the generalization
error bound for nonconvex smooth and Lipschitz loss for the final iterate of
any batch selection (Algorithm 1)

$\displaystyle|\epsilon_{\mathrm{gen}}|\leq\frac{2L^{2}}{n}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1+\beta\eta_{j}).$
(19)

Thus, for any learning problem $(f,\mathcal{D})\in\mathcal{NC}^{L}_{\beta}$
and for any algorithm $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ with a
decreasing step size $\eta_{t}\leq C/t$ (fixed $C<1/\beta$), it is true that
[39, Lemma 15]

$\displaystyle\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}\left(1+\beta\eta_{j}\right)\leq
Ce^{C\beta}T^{C\beta}\min\left\\{1+\frac{1}{C\beta},\log(eT)\right\\},$ (20)

and

$\displaystyle|\epsilon_{\mathrm{gen}}|\leq\frac{2Ce^{C\beta}L^{2}T^{C\beta}}{n}\min\left\\{1+\frac{1}{C\beta},\log(eT)\right\\}.$
(21)

Inequality (18) and Lemma 2 complete the proof. $\Box$

The next theorem provides a minimax lower bound on the generalization error
for learning problems $(f,\mathcal{D})$ within the class
$\mathcal{NC}^{\infty}_{\beta}$ (Definition 7) (smooth and possibly nonconvex
losses).

######  Theorem 9 (Generalization Error Lower Bound—Nonconvex Loss)

Choose $\beta>0$, step size $\eta_{t}=c/\beta t\leq 1/\beta$, number of
iterations $T$, data-set size $n$ and any initial point (independent of the
data-set). Then, it is true that

$\displaystyle\inf_{A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)}\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{C}^{\infty}_{\beta}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|$
$\displaystyle\geq\frac{1}{2n}\Big{(}(T+1)^{\log(1+c)}-1\Big{)}.$ (22)

We refer the reader to Appendix A.3 for the proof of Theorem 9. The class of
learning problems $\mathcal{NC}^{\infty}_{\beta}$ in Theorem 9 is larger than
the class $\mathcal{NC}^{L}_{\beta}$ of the upper bound in Theorem 8. We
proceed with a comparison between the lower bound of Theorem 9 and an upper
bound on the generalization error from prior work.

######  Remark 10 (Optimality of full-batch GD)

We may show that the full-batch GD is almost optimal (up to a $\sqrt{\log T}$
factor and slightly different order of the root) for general smooth losses
within the set of algorithms $\mathcal{A}(\eta_{t},T)$. To explain this
further, we compare upper bounds of the generalization error that appear in
prior work [39, Corollary 8], where it has been shown that the generalization
error of full-batch GD is

$\displaystyle\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{NC}^{\infty}_{\beta}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},\mathrm{FB\,\,GD})|=\mathcal{O}\left(\frac{T^{c}\sqrt{\log(T)}}{n}\right).$
(23)

By comparing the minimax bound in Theorem 9 with the upper bound in prior work
(inequality (23)) we observe the near-optimallity of full-batch GD within the
general class of learning problems $\mathcal{NC}^{\infty}_{\beta}$. The gap
between the roots of the upper and lower bound ($T^{c}$ and $T^{\log(1+c)}$
respectively) can be effectively closed for sufficiently small values of $c$,
since it is clear that $\log(1+c)\approx c$ near the origin (for instance, we
have the inequality $\log(1+c)\geq c/(c+1)$ is valid for all $c\in[0,1]$) or,
maybe more concretely, $\log(1+c)=c+o(c^{2})$, as $c\rightarrow 0$.
Regardless, our lower bound holds for any choice of $c\in(0,1]$ and provides a
generic representation for a wide set of step-size choices.

Lastly, we observe that the generalization error achieved by any algorithm in
$\mathcal{A}(\eta_{t},T)$ –such as (mini-batch) SGD– must necessarily be
arbitrarily close to that of full-batch GD (also in $\mathcal{A}(\eta_{t},T)$)
for all sufficiently small stepsizes (possibly up to inconsequential
$\sqrt{\log}$ factors). This once again rigorously shows that stochastic
(randomized) training may essentially be at most as optimal as nonstochastic
training, e.g. full-batch training.

##  5 Strongly-Convex Loss

For strongly-convex losses we relax the Lipschitz assumption on the loss,
since strong-convexity and Lipschitzness are in general incompatible. To do
this we consider the maximum norm of gradient loss along the optimization path
uniformly over the the data-set, and all algorithms in the given set
$\mathcal{A}(\eta_{t},T)$. Let $S$ be our data-set, and let $\tilde{S}$ be a
another data-set which differs from $S$ in exactly one entry; let that entry
of $\tilde{S}$ be $\tilde{z}$. For simplicity we denote the set of all such
data-set pairs as tuples $(S,\tilde{S})$. Consider the set of algorithms
$\mathcal{A}(\eta_{t},T)$, as specified in Definition 1. We now define the
constants

$\displaystyle\tilde{L}^{(1)}_{\eta_{t},T}(f)\triangleq$
$\displaystyle\sup_{\begin{subarray}{c}(S,\tilde{S}),\,\tilde{c}\in(0,1)\\\
A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)\end{subarray}}\|\nabla
f(\tilde{c}A_{\mathcal{R}}(S)+(1-\tilde{c})A_{\mathcal{R}}(\tilde{S}),\tilde{z})\|,$
$\displaystyle\tilde{L}^{(2)}_{\eta_{t},T}(f)\triangleq$
$\displaystyle\sup_{\begin{subarray}{c}t\leq T,\,(S,\tilde{S})\\\
A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)\end{subarray}}\|\nabla
f(w_{t},\tilde{z})\|,$ (24) $\displaystyle\tilde{L}_{\eta_{t},T}(f)\triangleq$
$\displaystyle\max\Big{\\{}\tilde{L}^{(1)}_{\eta_{t},T}(f),\tilde{L}^{(2)}_{\eta_{t},T}(f)\Big{\\}}.$

We note that the term $\tilde{L}_{\eta_{t},T}(f)$ essentially places an upper
bound on the norm of gradients along any path and any instance of the set of
algorithms $\mathcal{A}(\eta_{t},T)$. As a consequence,
$\tilde{L}_{\eta_{t},T}(f)$ is determined uniformly over the set
$\mathcal{A}(\eta_{t},T)$ and the domain $\mathcal{Z}^{n+1}$. In this way we
impose a Lipschitz-like assumption, while avoiding the incompatibility of
Lipschitz assumption for general strongly-convex losses. In what follows, we
consider the class of learning problems with strongly-convex and smooth
losses, such that the term $\tilde{L}_{\eta_{t},T}(f)$ is uniformly bounded by
some prescribed number. The formal definition follows.

######  Definition 11 (Smooth & Strongly-Convex Class)

Fix an iteration number $T$ and a stepsize sequence $\eta_{t}$. Choose
$\tilde{L}>0,\beta>\gamma>0$. The class
$\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}$ contains all learning problems
$(f,\mathcal{D})$ with $\beta$-smooth, $\gamma$-strongly-convex losses
$f(\cdot,Z),Z\sim\mathcal{D}$ such that
$\tilde{L}_{\eta_{t},T}(f)\leq\tilde{L}$ .

In words, the class $\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}$ contains all
($d$-dimensional) $\beta$-smooth, $\gamma$-strongly-convex problems which are
uniformly gradient-stable over the class of algorithms of interest
$\mathcal{A}(\eta_{t},T)$. We now derive an upper bound on the generalization
error by utilizing on-average stability. To begin with, note that for any pair
of points $A_{\mathcal{R}}(S),A_{\mathcal{R}}(S^{(i)})$, the mean-value
theorem implies the existence of some $\tilde{c}\in[0,1]$ such that

$\displaystyle|f(A_{\mathcal{R}}(S);z^{\prime}_{i})-f(A_{\mathcal{R}}(S^{(i)});z^{\prime}_{i})|$
$\displaystyle=|(A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)}))\cdot\nabla
f(\tilde{c}A_{\mathcal{R}}(S)+(1-\tilde{c})A_{\mathcal{R}}(S^{(i)}),z^{\prime}_{i})|$
$\displaystyle\leq\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\|\nabla
f(\tilde{c}A_{\mathcal{R}}(S)+(1-\tilde{c})A_{\mathcal{R}}(S^{(i)}),z^{\prime}_{i})\|$
$\displaystyle\leq\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\tilde{L}^{(1)}_{\eta_{t},T}(f)$
$\displaystyle\leq\tilde{L}_{\eta_{t},T}(f)\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|.$
(25)

Similarly to (10) we obtain the bound

$\displaystyle|\epsilon_{\mathrm{gen}}|$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[|f(A_{\mathcal{R}}(S);z^{\prime}_{i})-f(A_{\mathcal{R}}(S^{(i)});z^{\prime}_{i})|\right]$
$\displaystyle\leq\tilde{L}_{\eta_{t},T}(f)\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\right],$
(26)

where (25) gives inequality (26). Therefore, for any choice of
$(f,\mathcal{D})\in\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}$ (26) gives

$\displaystyle|\epsilon_{\mathrm{gen}}|$
$\displaystyle\leq\tilde{L}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\right].$
(27)

We use (27) as an alternative of (11) to derive bounds on the generalization
error in the strongly-convex case. To find upper bounds for the on-average
stability term
$\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|$ in
particular, we develop a growth-recursion for strongly-convex losses.

######  Lemma 12 (Growth Recursion—Strongly-Convex Loss)

Choose $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$, let $w_{1}=w^{(i)}_{1}$ be
the starting point, $w_{t+1}=G_{\\!J_{t}}(w_{t})$ and
$w^{(i)}_{t+1}=G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})$ for any
$t\in\\{1,\ldots,T\\}$. Then for any batch size
$m\triangleq|J_{t}|=|J^{(i)}_{t}|$, any $t\geq 0$ and any
$i\in\\{1,\ldots,n\\}$, it is true that

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\big{\|}G_{\\!J_{t}}(w_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\big{\|}\leq\begin{cases}(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|&\mathrm{under}\text{
}\\{J_{t}=J^{(i)}_{t}\\}\\\
(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{2\tilde{L}}{m}\eta_{t}&\mathrm{under}\text{
}\\{J_{t}\neq J^{(i)}_{t}\\}\end{cases}.$ (28)

We prove Lemma 12 in Appendix B.2. Through the growth recursion lemma, we
derive uniform upper bounds for the on-average stability and the
generalization error.

######  Theorem 13 (Generalization Error Upper Bound—Strongly-Convex Loss)

Choose $\beta>0,\gamma>0$ and $\tilde{L}>0$. For any learning problem
$(f,\mathcal{D})\in\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}$, and for any
algorithm $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ with step-size
$\eta_{t}\leq 2/(\beta+\gamma)$ and number of iterations $T$, it holds that

$\displaystyle\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\leq\frac{2\tilde{L}}{n}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}\bigg{(}1-\frac{\eta_{j}\gamma}{2}\bigg{)}.$

In particular, if $\eta_{t}=C\leq 1/(\beta+\gamma)$, then for any algorithm
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$

$\displaystyle\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\leq\frac{4\tilde{L}^{2}}{n\gamma}\left(1-\left(1-\frac{C\gamma}{2}\right)^{T}\right)\leq\frac{4\tilde{L}^{2}}{n\gamma}.$
(29)

##### Proof of Theorem 13

Lemma 12 gives

$\displaystyle\|w_{t+1}-w^{(i)}_{t+1}\|$
$\displaystyle\leq\bigg{(}1-\frac{\eta_{j}\gamma}{2}\bigg{)}\|w_{t}-w^{(i)}_{t}\|\mathds{1}_{J_{t}=J^{(i)}_{t}}+\bigg{(}1-\frac{\eta_{j}\gamma}{2}\bigg{)}\|w_{t}-w^{(i)}_{t}\|\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}+\frac{2}{m}\tilde{L}\eta_{t}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}$
$\displaystyle=\bigg{(}1-\frac{\eta_{j}\gamma}{2}\bigg{)}\|w_{t}-w^{(i)}_{t}\|+\frac{2}{m}\tilde{L}\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}.$

By solving the recursion we find

$\displaystyle\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|\equiv\|w_{T+1}-w^{(i)}_{T+1}\|$
$\displaystyle\leq\frac{2\tilde{L}}{m}\sum^{T}_{t=1}\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}\prod^{T}_{j=t+1}\bigg{(}1-\frac{\eta_{j}\gamma}{2}\bigg{)}\implies$
$\displaystyle\frac{1}{n}\sum^{n}_{i=1}\|A_{\mathcal{R}}(S)-A_{\mathcal{R}}(S^{(i)})\|$
$\displaystyle\leq\frac{2\tilde{L}}{m}\sum^{T}_{t=1}\eta_{t}\left(\frac{1}{n}\sum^{n}_{i=1}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}\right)\prod^{T}_{j=t+1}\bigg{(}1-\frac{\eta_{j}\gamma}{2}\bigg{)}.$
(30)

For a fixed step-size choice $\eta_{t}=C\leq 1/(\beta+\gamma)$, it is true
that [39, Lemma 15]

$\displaystyle\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}\left(1-\frac{\eta_{j}\gamma}{2}\right)=2\frac{1-\left(1-\frac{C\gamma}{2}\right)^{T}}{\gamma}.$
(31)

The inequalities (30), (31) and Lemma 2 complete the proof. $\Box$
Lastly, we establish a minimax bound over the set of learning problems of
strongly-convex problems in $\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}$. The
result follows.

######  Theorem 14 (Generalization Error Lower Bound—Strongly-Convex Loss)

Choose $\tilde{L}>0$, $\beta\geq\gamma>0$, dimension
$d\geq(\beta^{2}-\gamma^{2})/3\gamma^{2}$, number of iterations $T$, step-size
$\eta_{t}=\eta\in[2/\gamma(T+1),1/(\beta+\gamma)]$, input data-set size $n$
and initial point $w_{1}=0$. Then

$\displaystyle\inf_{A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)}\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\geq\frac{\tilde{L}^{2}}{32\gamma
n}.$ (32)

We compare the bounds of Theorems 13 and 14, and we conclude that all
algorithms within the set $\mathcal{A}(\eta_{t},T)$ are optimal for learning
problems in the class $\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}$. The proof of
Theorem 14 appears in Appendix B.3.

##  6 Conclusion

We developed upper and lower generalization error bounds for various classes
of learning problems, which hold uniformly over mini-batch gradient descent
algorithms with data independent batch schedules. In particular, we proved
that all gradient based algorithms in the set $\mathcal{A}(\eta_{t},T)$
described by Algorithm 1 (Definition 1) generalize optimally within the class
of Lipschitz smooth convex and strongly-convex losses. For non-convex losses,
we showed that full-batch GD is in fact optimal within the class of smooth
(possibly nonconvex) losses. Extension of the latter result to the class of
Lipschitz and smooth losses, or optimality of other mini-batch schemes, for
instance stochastic training schemes such as the SGD algorithm, for smooth
(non-Lipschitz) losses remain open problems for future work. An important
implication of our results is that different mini-batch schedules mainly
affect the optimization error of Lipschitz and smooth losses. Therefore,
optimization error guarantees suffice for optimal batch selection in this
class of loss functions.

##  7 Acknowledgement

We would like to thank Nathan Srebro for the helpful discussion and valuable
suggestions during the development of this work.

## References

  * [1] Idan Amir, Yair Carmon, Tomer Koren, and Roi Livni.  Never go full batch (in stochastic convex optimization).  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 25033–25043. Curran Associates, Inc., 2021.  URL: https://proceedings.neurips.cc/paper/2021/file/d27b95cac4c27feb850aaa4070cc4675-Paper.pdf.
  * [2] Idan Amir, Tomer Koren, and Roi Livni.  SGD Generalizes Better Than GD (And Regularization Doesn’t Help).  arXiv preprint arXiv:2102.01117, 2021.  URL: https://arxiv.org/abs/2102.01117.
  * [3] Idan Amir, Roi Livni, and Nati Srebro.  Thinking outside the ball: Optimal learning with gradient descent for generalized linear stochastic convex optimization.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 23539–23550. Curran Associates, Inc., 2022.  URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/9521b6e7f33e039e7d92e23f5e37bbf4-Paper-Conference.pdf.
  * [4] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar.  Stability of stochastic gradient descent on nonsmooth convex losses.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4381–4391. Curran Associates, Inc., 2020.  URL: https://proceedings.neurips.cc/paper/2020/file/2e2c4bf7ceaa4712a72dd5ee136dc9a8-Paper.pdf.
  * [5] Dimitri Bertsekas.  Convex optimization algorithms.  Athena Scientific, 2015.
  * [6] Dimitri P Bertsekas, W Hager, and O Mangasarian.  Nonlinear programming. athena scientific belmont.  Massachusets, USA, 1999.
  * [7] Olivier Bousquet and André Elisseeff.  Stability and generalization.  The Journal of Machine Learning Research, 2:499–526, 2002.  URL: https://www.jmlr.org/papers/v2/bousquet02a.html.
  * [8] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy.  Sharper bounds for uniformly stable algorithms.  In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 610–626. PMLR, 09–12 Jul 2020.  URL: https://proceedings.mlr.press/v125/bousquet20b.html.
  * [9] Zachary Charles and Dimitris Papailiopoulos.  Stability and generalization of learning algorithms that converge to global optima.  In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 745–754. PMLR, 10–15 Jul 2018\.  URL: https://proceedings.mlr.press/v80/charles18a.html.
  * [10] Tyler Farghly and Patrick Rebeschini.  Time-independent generalization bounds for SGLD in non-convex settings.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 19836–19846. Curran Associates, Inc., 2021.  URL: https://proceedings.neurips.cc/paper/2021/file/a4ee59dd868ba016ed2de90d330acb6a-Paper.pdf.
  * [11] Vitaly Feldman.  Generalization of erm in stochastic convex optimization: The dimension strikes back.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.  URL: https://proceedings.neurips.cc/paper/2016/file/8c01a75941549a705cf7275e41b21f0d-Paper.pdf.
  * [12] Vitaly Feldman and Jan Vondrak.  Generalization bounds for uniformly stable algorithms.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.  URL: https://proceedings.neurips.cc/paper/2018/file/05a624166c8eb8273b8464e8d9cb5bd9-Paper.pdf.
  * [13] Vitaly Feldman and Jan Vondrak.  High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.  In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1270–1279. PMLR, 25–28 Jun 2019.  URL: https://proceedings.mlr.press/v99/feldman19a.html.
  * [14] Shi Fu, Yunwen Lei, Qiong Cao, Xinmei Tian, and Dacheng Tao.  Sharper bounds for uniformly stable algorithms with stationary mixing process.  In The Eleventh International Conference on Learning Representations, 2023.  URL: https://openreview.net/forum?id=8E5Yazboyh.
  * [15] Jonas Geiping, Micah Goldblum, Phillip E Pope, Michael Moeller, and Tom Goldstein.  Stochastic training is not necessary for generalization.  arXiv preprint arXiv:2109.14119, 2021.  URL: https://arxiv.org/abs/2109.14119.
  * [16] M. Gürbüzbalaban, A. Ozdaglar, and P. A. Parrilo.  On the convergence rate of incremental aggregated gradient algorithms.  SIAM Journal on Optimization, 27(2):1035–1048, 2017.  arXiv:https://doi.org/10.1137/15M1049695, doi:10.1137/15M1049695.
  * [17] M. Gürbüzbalaban, A. Ozdaglar, and P. A. Parrilo.  Convergence rate of incremental gradient and incremental Newton methods.  SIAM Journal on Optimization, 29(4):2542–2565, 2019.  arXiv:https://doi.org/10.1137/17M1147846, doi:10.1137/17M1147846.
  * [18] M. Gürbüzbalaban, A. Ozdaglar, and P. A. Parrilo.  Why random reshuffling beats stochastic gradient descent.  Mathematical Programming, 186(1):49–84, Mar 2021.  doi:10.1007/s10107-019-01440-w.
  * [19] Mahdi Haghifam, Borja Rodríguez-Gálvez, Ragnar Thobaben, Mikael Skoglund, Daniel M. Roy, and Gintare Karolina Dziugaite.  Limitations of information-theoretic generalization bounds for gradient descent methods in stochastic convex optimization.  In Shipra Agrawal and Francesco Orabona, editors, Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 663–706. PMLR, 20 Feb–23 Feb 2023.  URL: https://proceedings.mlr.press/v201/haghifam23a.html.
  * [20] Moritz Hardt, Ben Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1225–1234, New York, New York, USA, 20–22 Jun 2016. PMLR.  URL: https://proceedings.mlr.press/v48/hardt16.html.
  * [21] Zhanliang Huang, Yunwen Lei, and Ata Kaban.  Optimisation and learning with randomly compressed gradient updates.  Neural Computation, February 2023.
  * [22] Byol Kim and Rina Foygel Barber.  Black box tests for algorithmic stability.  arXiv preprint arXiv:2111.15546, 2021.  URL: https://arxiv.org/abs/2111.15546.
  * [23] Yegor Klochkov and Nikita Zhivotovskiy.  Stability and deviation optimal risk bounds with convergence rate $\mathcal{O}(1/n)$.  arXiv preprint arXiv:2103.12024, 2021.  URL: https://arxiv.org/abs/2103.12024.
  * [24] Ilja Kuzborskij and Christoph Lampert.  Data-dependent stability of stochastic gradient descent.  In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2815–2824. PMLR, 10–15 Jul 2018\.  URL: https://proceedings.mlr.press/v80/kuzborskij18a.html.
  * [25] Yunwen Lei, Ting Hu, and Ke Tang.  Generalization performance of multi-pass stochastic gradient descent with convex loss functions.  The Journal of Machine Learning Research, 22(25):1–41, 2021.  URL: http://jmlr.org/papers/v22/19-716.html.
  * [26] Yunwen Lei, Rong Jin, and Yiming Ying.  Stability and generalization analysis of gradient methods for shallow neural networks.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 38557–38570. Curran Associates, Inc., 2022.  URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/fb8fe6b79288f3d83696a5d276f4fc9d-Paper-Conference.pdf.
  * [27] Yunwen Lei and Yiming Ying.  Fine-grained analysis of stability and generalization for stochastic gradient descent.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5809–5819. PMLR, 13–18 Jul 2020\.  URL: https://proceedings.mlr.press/v119/lei20c.html.
  * [28] Yunwen Lei and Yiming Ying.  Sharper generalization bounds for learning with gradient-dominated objective functions.  In International Conference on Learning Representations, 2020.  URL: https://iclr.cc/virtual/2021/poster/3141.
  * [29] Jian Li, Xuanyuan Luo, and Mingda Qiao.  On generalization error bounds of noisy gradient methods for non-convex learning.  arXiv preprint arXiv:1902.00621, 2019.  URL: https://arxiv.org/abs/1902.00621.
  * [30] Jian Li, Xuanyuan Luo, and Mingda Qiao.  On generalization error bounds of noisy gradient methods for non-convex learning.  In International Conference on Learning Representations, 2020.  URL: https://openreview.net/forum?id=SkxxtgHKPS.
  * [31] Roi Livni.  Information theoretic lower bounds for information theoretic upper bounds.  arXiv preprint arXiv:2302.04925, 2023.  URL: https://arxiv.org/abs/2302.04925.
  * [32] Liam Madden, Emiliano Dall’Anese, and Stephen Becker.  High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent.  arXiv e-prints, pages arXiv–2006, 2020.  URL: https://arxiv.org/abs/2006.05610.
  * [33] Amirkeivan Mohtashami, Sebastian Stich, and Martin Jaggi.  Characterizing & finding good data orderings for fast convergence of sequential gradient methods.  arXiv preprint arXiv:2202.01838, 2022.  URL: https://arxiv.org/pdf/2202.01838.pdf.
  * [34] Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng.  Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints.  In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 605–638. PMLR, 06–09 Jul 2018.  URL: https://proceedings.mlr.press/v75/mou18a.html.
  * [35] Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry.  Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate.  In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3051–3059. PMLR, 16–18 Apr 2019.  URL: https://proceedings.mlr.press/v89/nacson19a.html.
  * [36] Angelia Nedić and Dimitri Bertsekas.  Convergence Rate of Incremental Subgradient Algorithms, pages 223–264.  Springer US, Boston, MA, 2001.  doi:10.1007/978-1-4757-6594-6_11.
  * [37] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy.  Information-theoretic generalization bounds for SGLD via data-dependent estimates.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.  URL: https://proceedings.neurips.cc/paper/2019/file/05ae14d7ae387b93370d142d82220f1b-Paper.pdf.
  * [38] Konstantinos Nikolakakis, Farzin Haddadpour, Dionysis Kalogerias, and Amin Karbasi.  Black-box generalization: Stability of zeroth-order learning.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 31525–31541. Curran Associates, Inc., 2022.  URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/cce0df2e85795d81e417fc74c9cc29ec-Paper-Conference.pdf.
  * [39] Konstantinos Nikolakakis, Farzin Haddadpour, Amin Karbasi, and Dionysios Kalogerias.  Beyond lipschitz: Sharp generalization and excess risk bounds for full-batch GD.  In The Eleventh International Conference on Learning Representations, 2023.  URL: https://openreview.net/forum?id=pOyi9KqE56b.
  * [40] Ankit Pensia, Varun Jog, and Po-Ling Loh.  Generalization error bounds for noisy, iterative algorithms.  In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546–550, 2018.  doi:10.1109/ISIT.2018.8437571.
  * [41] Ali Ramezani-Kebrya, Ashish Khisti, and Ben Liang.  On the generalization of stochastic gradient descent with momentum.  arXiv preprint arXiv:2102.13653, 2021.  URL: url={https://arxiv.org/abs/1809.04564}.
  * [42] Itay Safran and Ohad Shamir.  How good is SGD with random shuffling?  In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3250–3284. PMLR, 09–12 Jul 2020.  URL: https://proceedings.mlr.press/v125/safran20a.html.
  * [43] Matan Schliserman and Tomer Koren.  Stability vs implicit bias of gradient methods on separable data and beyond.  In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3380–3394. PMLR, 02–05 Jul 2022.  URL: https://proceedings.mlr.press/v178/schliserman22a.html.
  * [44] Hossein Taheri and Christos Thrampoulidis.  Generalization and stability of interpolating neural networks with minimal width.  arXiv preprint arXiv:2302.09235, 2023.  URL: https://arxiv.org/abs/2302.09235.
  * [45] Hossein Taheri and Christos Thrampoulidis.  On generalization of decentralized learning with separable data.  In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 4917–4945. PMLR, 25–27 Apr 2023.  URL: https://proceedings.mlr.press/v206/taheri23a.html.
  * [46] Bohan Wang, Huishuai Zhang, Jieyu Zhang, Qi Meng, Wei Chen, and Tie-Yan Liu.  Optimizing information-theoretical generalization bound via anisotropic noise of SGLD.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 26080–26090. Curran Associates, Inc., 2021.  URL: https://proceedings.neurips.cc/paper/2021/file/db2b4182156b2f1f817860ac9f409ad7-Paper.pdf.
  * [47] Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon.  Analyzing the generalization capability of SGLD using properties of gaussian channels.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 24222–24234. Curran Associates, Inc., 2021.  URL: https://proceedings.neurips.cc/paper/2021/file/cb77649f5d53798edfa0ff40dae46322-Paper.pdf.
  * [48] Puyu Wang, Liang Wu, and Yunwen Lei.  Stability and generalization for randomized coordinate descent.  arXiv preprint arXiv:2108.07414, 2021.  URL: https://arxiv.org/abs/2108.07414.
  * [49] Weiran Wang and Nathan Srebro.  Stochastic nonconvex optimization with large minibatches.  In Aurélien Garivier and Satyen Kale, editors, Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pages 857–882. PMLR, 22–24 Mar 2019.  URL: https://proceedings.mlr.press/v98/wang19a.html.
  * [50] Yue Xing, Qifan Song, and Guang Cheng.  On the algorithmic stability of adversarial training.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 26523–26535. Curran Associates, Inc., 2021.  URL: https://proceedings.neurips.cc/paper/2021/file/df1f1d20ee86704251795841e6a9405a-Paper.pdf.
  * [51] Aolin Xu and Maxim Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.  URL: https://proceedings.neurips.cc/paper/2017/file/ad71c82b22f4f65b9398f76d8be4c615-Paper.pdf.
  * [52] Peiyuan Zhang, Jiaye Teng, and Jingzhao Zhang.  Lower generalization bounds for GD and SGD in smooth stochastic convex optimization.  arXiv preprint arXiv:2303.10758, 2023.  URL: https://arxiv.org/abs/2303.10758.
  * [53] Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami.  Stability of SGD: Tightness Analysis and Improved Bounds.  arXiv preprint arXiv:2102.05274, 2021.  URL: https://arxiv.org/abs/2102.05274.
  * [54] Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pritham Pingali, Chao Chen, and Mayank Goswami.  Stability of SGD: Tightness analysis and improved bounds.  In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.  URL: https://openreview.net/forum?id=Sl-zmO8j5lq.
  * [55] Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan.  Towards understanding why lookahead generalizes better than SGD and beyond.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 27290–27304. Curran Associates, Inc., 2021.  URL: https://proceedings.neurips.cc/paper/2021/file/e53a0a2978c28872a4505bdb51db06dc-Paper.pdf.
  * [56] Yi Zhou, Yingbin Liang, and Huishuai Zhang.  Understanding generalization error of sgd in nonconvex optimization.  Machine Learning, 111(1):345–375, Jan 2022.  doi:10.1007/s10994-021-06056-w.

##  Appendix A Convex and Nonconvex Loss

Herein, we prove the growth recursion (Lemma 3), and minimax bounds for convex
and nonconvex losses as appear in Section 3 and Section 4.

###  A.1 Proof of Lemma 3 (Growth Recursion)

For two input sequences $S,S^{(i)}$ which differ in the $i^{\text{th}}$
element the update rules are

$\displaystyle G_{\\!J_{t}}(w)\triangleq w-\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\nabla f(w,z),\,\,\,G_{\\!J^{(i)}_{t}}(w)\triangleq
w-\frac{\eta_{t}}{m}\sum_{z\in J^{(i)}_{t}}\nabla f(w,z),$ (33)

for potentially different batches $J_{t}\triangleq J_{t}(S)$ and
$J^{(i)}_{t}\triangleq J^{(i)}_{t}(S^{(i)})$ (under the same selection rule),
respectively. For nonconvex losses, under the event $\\{J_{t}\equiv
J^{(i)}_{t}\\}$

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{(i)}_{t})\|$
$\displaystyle\leq\|w_{t}-\frac{\eta_{t}}{m}\sum_{z\in J_{t}}\nabla
f(w,z)|_{w=w_{t}}-w^{(i)}_{t}-\frac{\eta_{t}}{m}\sum_{z\in J^{(i)}_{t}}\nabla
f(w,z)|_{w=w^{(i)}_{t}}\|$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|+\frac{\eta_{t}}{m}\bigg{\|}\sum_{z\in
J_{t}}\nabla_{w}f(w,z)|_{w=w_{t}}-\sum_{z\in
J_{t}}\nabla_{w}f(w,z)|_{w=w^{(i)}_{t}}\bigg{\|}$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|+\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\bigg{\|}\nabla_{w}f(w,z)|_{w=w_{t}}-\nabla_{w}f(w,z)|_{w=w^{(i)}_{t}}\bigg{\|}$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|+\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\beta\|w_{t}-w^{(i)}_{t}\|$
$\displaystyle=(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|.$ (34)

Under the event $J_{t}\neq J^{(i)}_{t}$, define $J^{-i}_{t}\triangleq
J_{t}\setminus\\{z_{i}\\}$ and $J^{\prime-i}_{t}\triangleq
J^{(i)}_{t}\setminus\\{z^{\prime}_{i}\\}$, and notice that
$J^{-i}_{t}=J^{\prime-i}_{t}$ for any $t\leq T$ w.p. $1$. Thus we may
decompose the growth recursion as follows

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|$
$\displaystyle\leq\|w_{t}-\frac{\eta_{t}}{m}\sum_{z\in J_{t}}\nabla
f(w,z)|_{w=w_{t}}-w^{(i)}_{t}-\frac{\eta_{t}}{m}\sum_{z\in J^{(i)}_{t}}\nabla
f(w,z)|_{w=w^{(i)}_{t}}\|$
$\displaystyle=\bigg{\|}w_{t}-w^{(i)}_{t}-\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\nabla_{w}f(w,z)|_{w=w_{t}}+\frac{\eta_{t}}{m}\sum_{z^{\prime}\in
J^{(i)}_{t}}\nabla_{w}f(w,z^{\prime})|_{w=w^{(i)}_{t}}\bigg{\|}$
$\displaystyle=\bigg{\|}\frac{1}{m}\sum_{z\in
J^{-i}_{t}}\left(w_{t}-\eta_{t}\nabla_{w}f(w,z)|_{w=w_{t}}\right)-\frac{1}{m}\sum_{z^{\prime}\in
J^{\prime-i}_{t}}\left(w^{(i)}_{t}-\eta_{t}\nabla_{w}f(w,z^{\prime})|_{w=w^{(i)}_{t}}\right)$
$\displaystyle\quad+\frac{1}{m}\left(w_{t}-\eta_{t}\nabla_{w}f(w,z_{i})|_{w=w_{t}}\right)-\frac{1}{m}\left(w^{(i)}_{t}-\eta_{t}\nabla_{w}f(w,z^{\prime}_{i})|_{w=w^{(i)}_{t}}\right)\bigg{\|}$
$\displaystyle=\bigg{\|}\frac{1}{m}\sum_{z\in
J^{-i}_{t}}(\underbrace{w_{t}-\eta_{t}\nabla_{w}f(w,z)|_{w=w_{t}}}_{G(w_{t},z)})-\frac{1}{m}\sum_{z\in
J^{-i}_{t}}(\underbrace{w^{(i)}_{t}-\eta_{t}\nabla_{w}f(w,z)|_{w=w^{(i)}_{t}}}_{G(w^{(i)}_{t},z)})$
$\displaystyle\quad+\frac{1}{m}(\underbrace{w_{t}-\eta_{t}\nabla_{w}f(w,z_{i})|_{w=w_{t}}}_{G(w_{t},z_{i})})-\frac{1}{m}(\underbrace{w^{(i)}_{t}-\eta_{t}\nabla_{w}f(w,z^{\prime}_{i})|_{w=w^{(i)}_{t}}}_{G(w^{(i)}_{t},z^{\prime}_{i})})\bigg{\|}$
$\displaystyle=\frac{1}{m}\bigg{\|}\sum_{z\in
J^{-i}_{t}}\left(G(w_{t},z)-G(w^{(i)}_{t},z)\right)+G(w_{t},z_{i})-G(w^{(i)}_{t},z^{\prime}_{i})\bigg{\|}$
$\displaystyle\leq\frac{1}{m}\bigg{\|}\sum_{z\in
J^{-i}_{t}}\left(G(w_{t},z)-G(w^{(i)}_{t},z)\right)\bigg{\|}+\frac{1}{m}\|G(w_{t},z_{i})-G(w^{(i)}_{t},z^{\prime}_{i})\|$
$\displaystyle\leq\frac{1}{m}\sum_{z\in
J^{-i}_{t}}\|G(w_{t},z)-G(w^{(i)}_{t},z)\|+\frac{1}{m}\|G(w_{t},z_{i})-G(w^{(i)}_{t},z^{\prime}_{i})\|.$
(35)

for nonconvex loss (in a similar way as appears in [20, Lemma 2.4]) gives that
for a random variable $z$ it is true that

$\displaystyle\|G(w_{t},z)-G(w^{(i)}_{t},z)\|$
$\displaystyle\leq(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|$ (36)

additionally for two i.i.d. random variables $z_{i}$, $z^{\prime}_{i}$ (the
probability of $\\{z_{i}=z^{\prime}_{i}\\}$ is positive for discrete random
variables) and

$\displaystyle\|G(w_{t},z_{i})-G(w^{(i)}_{t},z^{\prime}_{i})\|$
$\displaystyle\leq\begin{cases}\|w_{t}-w^{(i)}_{t}\|+2L\eta_{t}&\quad\text{if
}z_{i}\neq z^{\prime}_{i},\\\
(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|&\quad\text{if
}z_{i}=z^{\prime}_{i}.\end{cases}$

Therefore, for both cases it is true that

$\displaystyle\|G(w_{t},z_{i})-G(w^{(i)}_{t},z^{\prime}_{i})\|$
$\displaystyle\leq(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|+2L\eta_{t}$ (37)

By combining the inequalities (36), (37) together with (35) we find

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|$
$\displaystyle\leq\frac{1}{m}\sum_{z\in
J^{-i}_{t}}(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|+\frac{1}{m}\left((1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|+2L\eta_{t}\right)$
$\displaystyle=\frac{m-1}{m}(1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|+\frac{1}{m}\left((1+\beta\eta_{t})\|w_{t}-w^{(i)}_{t}\|+2L\eta_{t}\right)$
$\displaystyle=\left(1+\beta\eta_{t}\right)\|w_{t}-w^{(i)}_{t}\|+\frac{2L}{m}\eta_{t}.$
(38)

The last display gives the second part of the recursion and completes the
proof for nonconvex losses. For convex loss [20, Lemma 2.4] gives

$\displaystyle\|G(w_{t},z)-G(w^{(i)}_{t},z)\|$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|,$ (39)
$\displaystyle\|G(w_{t},z_{i})-G(w^{(i)}_{t},z^{\prime}_{i})\|$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|+\eta_{t}\left(\|\nabla
f(w_{t},z_{i})\|+\|\nabla f(w^{(i)}_{t},z^{\prime}_{i})\|\right),$ (40)

and the inequality (40) holds under both events $\\{z_{i}=z^{\prime}_{i}\\}$
and $\\{z_{i}\neq z^{\prime}_{i}\\}$. By combining the last two together with
(35) we find

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|$
$\displaystyle\leq\frac{1}{m}\sum_{z\in
J^{-i}_{t}}\|w_{t}-w^{(i)}_{t}\|+\frac{1}{m}\left(\|w_{t}-w^{(i)}_{t}\|+2L\eta_{t}\right)$
$\displaystyle=\frac{m-1}{m}\|w_{t}-w^{(i)}_{t}\|+\frac{1}{m}\left(\|w_{t}-w^{(i)}_{t}\|+2L\eta_{t}\right)$
$\displaystyle=\|w_{t}-w^{(i)}_{t}\|+\frac{2L}{m}\eta_{t}.$ (41)

Finally, we find the non-expansive recursion for convex loss when $J_{t}\equiv
J^{(i)}_{t}$,

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{(i)}_{t})\|^{2}$
$\displaystyle=\|w_{t}-w^{(i)}_{t}\|^{2}-2\frac{\eta_{t}}{m}\langle\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z),w_{t}-w^{(i)}_{t}\rangle$
$\displaystyle\qquad+\eta^{2}_{t}\|\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla f(w^{(i)}_{t},z)\|^{2}$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|^{2}-2\frac{\eta_{t}}{\beta
m^{2}}\|\sum_{z\in J_{t}}\nabla f(w_{t},z)-\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z)\|^{2}$
$\displaystyle\qquad+\eta^{2}_{t}\|\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla f(w^{(i)}_{t},z)\|^{2}$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|^{2}-\frac{\eta_{t}}{m^{2}}(\frac{2}{\beta}-\eta_{t})\|\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\sum_{z\in J_{t}}\nabla f(w^{(i)}_{t},z)\|^{2}$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|^{2}.$ (42)

For the last chain of inequalities we used the co-coersivity of the function
$h(w)\triangleq\sum_{z\in J_{t}}\nabla f(w,z)$, for which is true that
$\langle h(w)-h(u),w-u\rangle\geq\frac{1}{\beta m}\|h(w)-h(u)\|^{2}$ and
$\eta_{t}<2/\beta$. Inequalities (41) and (42) gives the growth recursion for
convex losses and completes the proof. $\Box$

###  A.2 Proof Of Theorem 6 (Lower Bound—Convex Loss)

Let the initial point be any $w_{1}\in\mathbb{R^{d}}$ (independent of the
data-set) and consider the loss

$\displaystyle
f(w,\mathbf{z})=\sum^{d-1}_{k=1}w^{k}z^{k}+\frac{\beta}{2}(w^{d}-w^{d}_{1}-z^{d})^{2}\mathds{1}_{|w^{d}-w^{d}_{1}-z^{d}|\leq\tau}+\beta\tau(|w^{d}-w^{d}_{1}-z^{d}|-\frac{1}{2}\tau)\mathds{1}_{|w^{d}-w^{d}_{1}-z^{d}|>\tau},$

for some $\tau\leq L/\sqrt{d}\beta$,
$\mathbf{z}_{i}\triangleq(z^{1}_{i},z^{2}_{i},\ldots,z^{d}_{i})$, such that
$(z^{1}_{i},z^{2}_{i},\ldots,z^{d-1}_{i})\in\\{-L/\sqrt{d},+L/\sqrt{d}\\}^{d-1}$,
$z^{d}_{i}\in\\{-L/2\beta\sqrt{d},+L/2\beta\sqrt{d}\\}$
$i\in\\{1,2,\ldots,n\\}$, $\mathbb{P}(z_{i}^{j}=L/\sqrt{d})=1/2$ for
$j\in\\{1,\ldots,d-1\\}$, $\mathbb{P}(z_{i}^{d}=L/2\beta\sqrt{d})=1/2$ and
$z^{\ell}_{k}\perp z^{\ell^{\prime}}_{k^{\prime}}$ for all distinct pairs
$(\ell,k)$, $(\ell^{\prime},k^{\prime})$. Then $f(w,\mathbf{z})$ is $\beta$
smooth and $L$ Lipschitz, and continuously differentiable. For instance, we
have

$\displaystyle\|\nabla f(w,\mathbf{z})\|$
$\displaystyle=\sqrt{\sum^{d-1}_{k=1}(z^{k})^{2}+\beta^{2}(w^{d}-w^{d}_{1}-z^{d})^{2}\mathds{1}_{|w^{d}-w^{d}_{1}-z^{d}|\leq\tau}+\beta^{2}\tau^{2}\text{sign}^{2}(w^{d}-w^{d}_{1}-z^{d})\mathds{1}_{|w^{d}-w^{d}_{1}-z^{d}|>\tau}}$
$\displaystyle\leq\sqrt{\sum^{d-1}_{k=1}(z^{k})^{2}+\beta^{2}\tau^{2}}$ (43)
$\displaystyle\leq\sqrt{\frac{L^{2}(d-1)}{d}+\beta^{2}\frac{L^{2}}{d\beta^{2}}}\leq
L,$ (44)

and smoothness can be verified accordingly. Then the updates with step size
$\eta_{t}$ and $k\neq d$ are

$\displaystyle w^{k}_{t+1}$
$\displaystyle=w^{k}_{t}-\frac{\eta_{t}}{m}\sum_{z\in J_{t}}z^{k}\implies
w^{k}_{T}=w^{k}_{1}-\sum^{T-1}_{t=1}\frac{\eta_{t}}{m}\sum_{z\in J_{t}}z^{k},$
(45)

and for $k=d$ the update follows

$\displaystyle\\!\\!\\!w^{d}_{t+1}$
$\displaystyle=w^{d}_{t}-\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\left(\beta(w^{d}_{t}-w^{d}_{1}-z^{d})\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|\leq\tau}+\beta\tau\text{sign}(w^{d}_{t}-w^{d}_{1}-z^{d})\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|>\tau}\right).$
(46)

Hereafter, choose $\tau=L/(\sqrt{d}\beta)$. It is true that $\eta_{t}\leq
1/\beta$, and $|z^{d}|=\tau/2$. Starting from $w_{1}$, and

$\displaystyle w^{d}_{2}$
$\displaystyle=w^{d}_{1}-\frac{\eta_{t}}{m}\sum_{z\in J_{t}}\left(-\beta
z^{d}\mathds{1}_{|-z^{d}|\leq\tau}+\beta\tau\text{sign}(-z^{d})\mathds{1}_{|-z^{d}|>\tau}\right)$
(47) $\displaystyle=-\frac{\eta_{t}}{m}\sum_{z\in J_{t}}\left(-\beta
z^{d}\mathds{1}_{|-z^{d}|\leq\tau}\right)\implies$
$\displaystyle|w^{d}_{2}-w^{d}_{1}-z^{d}|$
$\displaystyle\leq|w^{d}_{2}-w^{d}_{1}|+|z^{d}|\leq\tau/2+\tau/2\leq\tau.$
(48)

Assuming that $|w^{d}_{t}-w^{d}_{1}|\leq\tau/2$, we can show that
$|w^{d}_{t+1}-w^{d}_{1}|\leq\tau/2$ and
$|w^{d}_{t+1}-w^{d}_{1}-z^{d}|\leq\tau$ because

$\displaystyle|w^{d}_{t+1}-w^{d}_{1}-z^{d}|$
$\displaystyle\leq|w^{d}_{t+1}-w^{d}_{1}|+|z^{d}|$
$\displaystyle\leq\bigg{|}w^{d}_{t}-w^{d}_{1}-\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\beta(w^{d}_{t}-w^{d}_{1}-z^{d})\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|\leq\tau}+\beta\tau\text{sign}(w^{d}_{t}-w^{d}_{1}-z^{d})\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|>\tau}\bigg{|}+\tau/2$
$\displaystyle=\bigg{|}(1-\beta\eta_{t})(w^{d}_{t}-w^{d}_{1})-\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\beta(-z^{d})\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|\leq\tau}+\beta\tau\text{sign}(w^{d}_{t}-w^{d}_{1}-z^{d})\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|>\tau}\bigg{|}+\tau/2$
$\displaystyle\leq|(1-\beta\eta_{t})(w^{d}_{t}-w^{d}_{1})|+\bigg{|}\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\beta
z^{d}\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|\leq\tau}+\beta\tau\text{sign}(w^{d}_{t}-w^{d}_{1}-z^{d})\mathds{1}_{|w^{d}_{t}-w^{d}_{1}-z^{d}|>\tau}\bigg{|}+\tau/2$
$\displaystyle=|(1-\beta\eta_{t})(w^{d}_{t}-w^{d}_{1})\Big{|}+\bigg{|}\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}\beta z^{d}\bigg{|}+\tau/2$ $\displaystyle\leq\tau/2+\tau/2=\tau.$

Through the induction above we showed that the updates $w^{d}_{t}$ remain in
the interval $|w^{d}_{t}-w^{d}_{1}-z^{d}|\leq\tau$ for any $t\leq T$, thus the
update in (46) gives

$\displaystyle\\!\\!\\!\\!w^{d}_{t+1}$
$\displaystyle=w^{d}_{t}-\frac{\beta\eta_{t}}{m}\sum_{z\in
J_{t}}(w^{d}_{t}-w^{d}_{1}-z^{d})=(1-\beta\eta_{t})w^{d}_{t}+\frac{\beta\eta_{t}}{m}\sum_{z\in
J_{t}}(z^{d}+w^{d}_{1})$ (49) $\displaystyle\implies
w^{d}_{T}=w^{d}_{1}\underbrace{\left(\prod^{T}_{t=1}(1-\beta\eta_{t})+\frac{\beta}{m}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1-\beta\eta_{j})\right)}_{\mathcal{H}}+\frac{\beta}{m}\sum^{T}_{t=1}\eta_{t}\sum_{z\in
J_{t}}z^{d}\prod^{T}_{j=t+1}(1-\beta\eta_{j}).$

Then the output of any algorithm in the set $\mathcal{A}(\eta_{t},T)$ for any
initial point (independent of the data-set) is

$\displaystyle A_{\mathcal{R}}^{k}(S)$
$\displaystyle=w^{k}_{1}-\sum^{T}_{t=1}\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}z^{k}.\quad k\in\\{1,2,\dots,d-1\\}$ (50) $\displaystyle
A_{\mathcal{R}}^{d}(S)$
$\displaystyle=w^{d}_{1}\mathcal{H}+\frac{\beta}{m}\sum^{T}_{t=1}\eta_{t}\sum_{z\in
J_{t}}z^{d}\prod^{T}_{j=t+1}(1-\beta\eta_{j})$ (51)

Additionally,

$\displaystyle\epsilon_{\mathrm{gen}}$
$\displaystyle=\mathbb{E}_{S,z,\mathcal{R}}[f(A_{\mathcal{R}}(S);\mathbf{z})-\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}_{i})]$
$\displaystyle=\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}^{\prime}_{i})]-\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}_{i})\right]$

We use (A.2) and the fact $|A^{d}_{\mathcal{R}}(S)-w^{d}_{1}-z^{d}|\leq\tau$,
then

$\displaystyle\epsilon_{\mathrm{gen}}$
$\displaystyle=\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\left(\frac{\beta}{2}(A^{d}_{\mathcal{R}}(S)-w^{d}_{1}-(z_{i}^{\prime})^{d})^{2}-\frac{\beta}{2}(A^{d}_{\mathcal{R}}(S)-w^{d}_{1}-z_{i}^{d})^{2}+\sum^{d-1}_{k=1}A^{k}_{\mathcal{R}}(S)((z_{i}^{\prime})^{k}-z_{i}^{k})\right)\right]$
$\displaystyle=\mathbb{E}_{S,S^{\prime},\mathcal{R}}\Bigg{[}\frac{1}{n}\sum^{n}_{i=1}\Bigg{(}\frac{\beta}{2}(-2A^{d}_{\mathcal{R}}(S)(z_{i}^{\prime})^{d}+2A^{d}_{\mathcal{R}}(S)z_{i}^{d}+((z_{i}^{\prime})^{d})^{2}-(z_{i}^{d})^{2})$
$\displaystyle\qquad\qquad\qquad+2w^{d}_{1}((z_{i}^{\prime})^{d})-z_{i}^{d}))+\sum^{d-1}_{k=1}A^{k}_{\mathcal{R}}(S)((z_{i}^{\prime})^{k}-z_{i}^{k})\Bigg{)}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S}\left[\frac{\beta}{2}(2A^{d}_{\mathcal{R}}(S)z_{i}^{d})+\sum^{d-1}_{k=1}A^{k}_{\mathcal{R}}(S)(-z_{i}^{k})\right]\right]$
$\displaystyle=\mathbb{E}_{\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S}\left[\beta(z_{i}^{d}\frac{\beta}{m}\sum^{T}_{t=1}\eta_{t}\sum_{z\in
J_{t}}z^{d}\prod^{T}_{j=t+1}(1-\beta\eta_{j}))+\sum^{d-1}_{k=1}z_{i}^{k}\sum^{T}_{t=1}\frac{\eta_{t}}{m}\sum_{z\in
J_{t}}z^{k}\right]\right],$

and for the last two equities we used the fact that the initial point $w_{1}$
is independent of data-set and that the random variables
$z_{i},z^{\prime}_{i}$ have zero mean for all $i\leq n$. If $\mathbf{z}_{i}\in
J_{t}$ then $\mathbb{E}_{S}[z^{d}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{d}]=L^{2}/\beta^{2}d$, otherwise
$\mathbb{E}_{S}[z^{d}_{i}\sum_{\mathbf{z}\in J_{t}}z^{k}]=0$, additionally for
$k\in\\{1,2,\ldots,d-1\\}$, if $\mathbf{z}_{i}\in J_{t}$ then
$\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in J_{t}}z^{k}]=L^{2}/d$, otherwise
$\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in J_{t}}z^{k}]=0$ thus
$\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{k}]=\mathds{1}_{\mathbf{z}_{i}\in J_{t}}L^{2}/d$ for any (randomized)
selection rule, further $\sum^{n}_{i=1}\mathds{1}_{\mathbf{z}_{i}\in J_{t}}=m$
for any $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ (Definition 1) with batch-
size $m\equiv|J_{t}|$ for all $t$, and the generalization error is

$\displaystyle|\epsilon_{\mathrm{gen}}|$
$\displaystyle=\left|\mathbb{E}_{\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\left(\frac{\beta^{2}}{m}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1-\beta\eta_{j})\mathbb{E}_{S}[z_{i}^{d}\sum_{z\in
J_{t}}z^{d}]+\sum^{d-1}_{k=1}\sum^{T}_{t=1}\frac{\eta_{t}}{m}\mathbb{E}_{S}[z_{i}^{k}\sum_{z\in
J_{t}}z^{k}]\right)\right]\right|$
$\displaystyle=\left|\mathbb{E}_{\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}\left(\frac{L^{2}}{dm}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1-\beta\eta_{j})\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}+\frac{L^{2}}{dm}\sum^{d-1}_{k=1}\sum^{T}_{t=1}\eta_{t}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}\right)\right]\right|$
$\displaystyle=\left|\mathbb{E}_{\mathcal{R}}\left[\frac{1}{n}\left(\frac{L^{2}}{dm}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1-\beta\eta_{j})\sum^{n}_{i=1}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}+\frac{L^{2}}{dm}\sum^{d-1}_{k=1}\sum^{T}_{t=1}\eta_{t}\sum^{n}_{i=1}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}\right)\right]\right|$
$\displaystyle=\left|\mathbb{E}_{\mathcal{R}}\left[\frac{1}{n}\left(\frac{L^{2}}{d}\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1-\beta\eta_{j})+\frac{L^{2}}{d}\sum^{d-1}_{k=1}\sum^{T}_{t=1}\eta_{t}\right)\right]\right|$
$\displaystyle=\frac{L^{2}}{dn}\left(\sum^{T}_{t=1}\eta_{t}\prod^{T}_{j=t+1}(1-\beta\eta_{j})+(d-1)\sum^{T}_{t=1}\eta_{t}\right)$
$\displaystyle\geq\frac{(d-1)L^{2}}{dn}\sum^{T}_{t=1}\eta_{t}$
$\displaystyle\geq\frac{L^{2}}{2n}\sum^{T}_{t=1}\eta_{t}.$ (52)

The inequality (52) holds for any algorithm in the set
$\mathcal{A}(\eta_{t},T)$, for any choice of step step size $\eta_{t}$, number
of iterations $T$, Lipschitz constant $L$ (due to (44)) and completes the
proof. $\Box$

###  A.3 Proof of Theorem 9 (Lower Bound—Nonconvex Loss)

Consider the loss
$f(w,\mathbf{z})=(w-\mathbf{z})^{\mathrm{T}}\Lambda(w-\mathbf{z})/2$,
$w\in\mathbb{R}^{d}$,
$\Lambda\triangleq\text{diag}(\lambda_{1},\ldots,\lambda_{d})$,
$\mathbf{z}_{i}=(z^{1}_{i},z^{2}_{i},\ldots,z^{d}_{i})\in\\{-1/\sqrt{\beta
d},+1/\sqrt{\beta d}\\}^{d}$, $i\in\\{1,2,\ldots,n\\}$,
$\mathbb{P}(z_{i}^{j}=1/\sqrt{\beta d})=1/2$ and $z^{\ell}_{k}\perp
z^{\ell^{\prime}}_{k^{\prime}}$ for all distinct pairs $(\ell,k)$,
$(\ell^{\prime},k^{\prime})$. Then the SGD updates with step size
$\eta_{t}=c/t\beta$ yield

$\displaystyle w_{t+1}$ $\displaystyle=w_{t}-\frac{c}{\beta
t}\Lambda\left(w_{t}-\frac{1}{m}\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}\right)=\left(1-\frac{c}{\beta
t}\Lambda\right)w_{t}+\frac{c}{m\beta t}\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}$ (53)

and for any arbitrary initial point $W_{1}$ (independent of the data-set)

$\displaystyle
A_{\mathcal{R}}(S)=w_{T+1}=\prod^{T}_{t=1}\left(1-\frac{c}{\beta
t}\Lambda\right)w_{1}+\frac{c}{m\beta}\sum^{T}_{t=1}\frac{1}{t}\prod^{T}_{j=t+1}\left(1-\frac{c}{\beta
j}\Lambda\right)\Lambda\sum_{\mathbf{z}\in J_{t}}\mathbf{z}.$ (54)

Additionally,

$\displaystyle\epsilon_{\mathrm{gen}}$
$\displaystyle=\mathbb{E}_{S,z,\mathcal{R}}[f(A_{\mathcal{R}}(S);\mathbf{z})-\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}_{i})]$
$\displaystyle=\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}^{\prime}_{i})]-\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}_{i})\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}(A_{\mathcal{R}}(S)-\mathbf{z}^{\prime}_{i})^{\mathrm{T}}\Lambda(A_{\mathcal{R}}(S)-\mathbf{z}^{\prime}_{i})-\frac{1}{n}\sum^{n}_{i=1}(A_{\mathcal{R}}(S)-\mathbf{z}_{i})^{\mathrm{T}}\Lambda(A_{\mathcal{R}}(S)-\mathbf{z}_{i})\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\Bigg{[}\frac{1}{n}\sum^{n}_{i=1}\big{(}A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda
A_{\mathcal{R}}(S)-2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}^{\prime}_{i}+(\mathbf{z}^{\prime}_{i})^{\mathrm{T}}\Lambda\mathbf{z}^{\prime}_{i}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad-A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda
A_{\mathcal{R}}(S)+2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}_{i}-(\mathbf{z}_{i})^{\mathrm{T}}\Lambda\mathbf{z}_{i}\big{)}\Bigg{]}$
$\displaystyle=\frac{1}{2n}\sum^{n}_{i=1}-2\mathbb{E}_{S,\mathcal{R}}[A^{\mathrm{T}}_{\mathcal{R}}(S)]\Lambda\underbrace{\mathbb{E}_{S^{\prime}}[\mathbf{z}^{\prime}_{i}]}_{=0}+\underbrace{\mathbb{E}_{S^{\prime}}[(\mathbf{z}^{\prime}_{i})^{\mathrm{T}}\Lambda\mathbf{z}^{\prime}_{i}]-\mathbb{E}_{S}[(\mathbf{z}_{i})^{\mathrm{T}}\Lambda\mathbf{z}_{i}]}_{=0}+\mathbb{E}_{S,\mathcal{R}}[2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}_{i}]$
$\displaystyle=\frac{1}{2n}\sum^{n}_{i=1}\mathbb{E}_{S,\mathcal{R}}[2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}_{i}]$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S}\Bigg{[}\mathbf{z}^{\mathrm{T}}_{i}\Lambda\frac{c}{m\beta}\sum^{T}_{t=1}\frac{1}{t}\prod^{T}_{j=t+1}\left(1-\frac{c}{\beta
j}\Lambda\right)\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}\Bigg{]}+\underbrace{\mathbb{E}_{S}[\mathbf{z}^{\mathrm{T}}_{i}]}_{0}\Lambda\prod^{T}_{t=1}\left(1-\frac{c}{\beta
t}\Lambda\right)\mathbb{E}[W_{1}]$
$\displaystyle=\frac{c}{m\beta}\sum^{T}_{t=1}\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}_{S,\mathcal{R}}\Bigg{[}\mathbf{z}^{\mathrm{T}}_{i}\Lambda\frac{1}{t}\prod^{T}_{j=t+1}\left(1-\frac{c}{\beta
j}\Lambda\right)\Lambda\sum_{\mathbf{z}\in J_{t}}\mathbf{z}\Bigg{]}.$ (55)

Define

$\displaystyle
M^{t}\triangleq\Lambda\frac{1}{t}\prod^{T}_{j=t+1}\left(1-\frac{c}{\beta
j}\Lambda\right)\Lambda.$ (56)

If $\mathbf{z}_{i}\in J_{t}$ then $\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{k}]=1/\beta d$, otherwise
$\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in J_{t}}z^{k}]=0$, thus
$\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{k}]=\mathds{1}_{\mathbf{z}_{i}\in J_{t}}1/\beta d$ for any
(randomized) selection rule, and $\sum^{n}_{i=1}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}=m$ for any $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ (Definition 1)
with batch-size $m\equiv|J_{t}|$ for all $t$, thus

$\displaystyle\frac{c}{\beta
nm}\mathbb{E}_{\mathcal{R}}\left[\sum^{n}_{i=1}\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\mathbb{E}_{S}\bigg{[}z^{k}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{k}\bigg{]}\right]$
$\displaystyle=\frac{c}{d\beta^{2}nm}\mathbb{E}_{\mathcal{R}}\left[\sum^{n}_{i=1}\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}\right]$
$\displaystyle=\frac{c}{d\beta^{2}nm}\mathbb{E}_{\mathcal{R}}\left[\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\sum^{n}_{i=1}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}\right]$
$\displaystyle=\frac{c}{d\beta^{2}n}\mathbb{E}_{\mathcal{R}}\left[\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\right]$
$\displaystyle=\frac{c}{d\beta^{2}n}\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}.$
(57)

Let $\lambda_{k}<0$ with $|\lambda_{k}|\leq\beta$, and choose $c\leq 1$. Then

$\displaystyle\sum^{T}_{t=1}M^{t}_{kk}$
$\displaystyle=\lambda^{2}_{k}\sum^{T}_{t=1}\frac{1}{t}\prod^{T}_{j=t+1}\left(1+\frac{c}{\beta
j}|\lambda_{k}|\right)$
$\displaystyle\geq\lambda^{2}_{k}\sum^{T}_{t=1}\frac{1}{t}\prod^{T}_{j=t+1}2^{\frac{c|\lambda_{k}|}{\beta
j}}$ (58)
$\displaystyle=\lambda^{2}_{k}\sum^{T}_{t=1}\frac{1}{t}2^{\sum^{T}_{j=t+1}\frac{c|\lambda_{k}|}{\beta
j}}$
$\displaystyle=\lambda^{2}_{k}\sum^{T}_{t=1}\frac{1}{t}2^{\sum^{T}_{j=1}\frac{c|\lambda_{k}|}{\beta
j}-\sum^{t}_{j=1}\frac{c|\lambda_{k}|}{\beta j}}$
$\displaystyle\geq\lambda^{2}_{k}\sum^{T}_{t=1}\frac{1}{t}2^{\frac{c|\lambda_{k}|}{\beta}\ln(T+1)-\frac{c|\lambda_{k}|}{\beta}\ln(t)-\frac{c|\lambda_{k}|}{\beta}}$
$\displaystyle=\lambda^{2}_{k}2^{\frac{-c|\lambda_{k}|}{\beta}}\sum^{T}_{t=1}\frac{1}{t}2^{\frac{c|\lambda_{k}|}{\beta}\ln(\frac{T+1}{t})}$
$\displaystyle=\lambda^{2}_{k}2^{\frac{-c|\lambda_{k}|}{\beta}}\sum^{T}_{t=1}\frac{1}{t}2^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}\log_{2}(\frac{T+1}{t})}$
$\displaystyle=\lambda^{2}_{k}2^{\frac{-c|\lambda_{k}|}{\beta}}(T+1)^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}\sum^{T}_{t=1}\frac{1}{t}\frac{1}{t^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}}$
$\displaystyle\geq\lambda^{2}_{k}2^{\frac{-c|\lambda_{k}|}{\beta}}(T+1)^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}\int^{T+1}_{1}\frac{1}{t}\frac{1}{t^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}}\mathrm{d}t$
$\displaystyle=\lambda^{2}_{k}2^{\frac{-c|\lambda_{k}|}{\beta}}(T+1)^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}\int^{T+1}_{1}\frac{1}{t^{1+\frac{c|\lambda_{k}|}{\beta\log_{2}e}}}\mathrm{d}t$
$\displaystyle=\lambda^{2}_{k}2^{\frac{-c|\lambda_{k}|}{\beta}}(T+1)^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}\frac{\beta\log_{2}e}{c|\lambda_{k}|}\left(1-(T+1)^{-\frac{\beta\log_{2}e}{c|\lambda_{k}|}}\right)$
$\displaystyle=\frac{|\lambda_{k}|\beta\log_{2}e}{c}2^{\frac{-c|\lambda_{k}|}{\beta}}\left((T+1)^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}-1\right),$
(59)

where (58) holds since $1+x\geq 2^{x}$ for all $x\in(0,1]$. Finally, equations
(55), (57) and (59) give

$\displaystyle|\epsilon_{\mathrm{gen}}|$
$\displaystyle\geq\frac{c}{d\beta^{2}n}\sum^{d}_{k=1}\frac{|\lambda_{k}|\beta\log_{2}e}{c}2^{\frac{-c|\lambda_{k}|}{\beta}}\left((T+1)^{\frac{c|\lambda_{k}|}{\beta\log_{2}e}}-1\right)$
$\displaystyle\geq\frac{\log_{2}e\min_{k}\\{|\lambda_{k}|\\}}{n\beta}2^{-c}\left((T+1)^{\frac{c\min_{k}\\{|\lambda_{k}|\\}}{\beta\log_{2}e}}-1\right).$

Similarly, for a smaller set of values for $c$, we may use the inequality
$1+x\geq\zeta^{x}$ for some $\zeta\in[2,e]$ instead of the inequality $1+x\geq
2^{x}$ in (58) and we identically find that for all $0\leq c\leq 1$ such that
$1+c\geq\zeta^{c}$,

$\displaystyle|\epsilon_{\mathrm{gen}}|$
$\displaystyle\geq\frac{\log_{\zeta}e\min_{k}\\{|\lambda_{k}|\\}}{n\beta}\zeta^{-c}\left((T+1)^{\frac{c\min_{k}\\{|\lambda_{k}|\\}}{\beta\log_{\zeta}e}}-1\right).$
(60)

For every choice of $c$, we may take the maximum allowable value of $\zeta$,
namely $\zeta=(1+c)^{1/c}$. Then, together with the choice
$\Lambda=-\beta\mathbf{I}$, we obtain

$\displaystyle|\epsilon_{\mathrm{gen}}|$
$\displaystyle\geq\frac{\log_{(1+c)^{1/c}}e}{(1+c)n}\left((T+1)^{\frac{c}{\log_{(1+c)^{1/c}}e}}-1\right)$
$\displaystyle=\frac{c}{(1+c)\log(1+c)n}\left((T+1)^{\log(c+1)}-1\right)$
$\displaystyle\geq\frac{1}{2\log(2)n}\left((T+1)^{\log(c+1)}-1\right)$
$\displaystyle\geq\frac{1}{2n}\left((T+1)^{\log(c+1)}-1\right).$ (61)

The proof is now complete. $\Box$

##  Appendix B Strongly-Convex Loss

Herein, we prove the generalization error bounds for strongly-convex losses.
We start by proving the upper bound and then we continue with the lower bound.

###  B.1 Strongly-Convex Loss Upper Bound

The next lemma gives the contraction property of the growth recursion for
strongly-convex losses.

###### Lemma 15

Let the loss function be $\gamma$-strongly-convex ($\gamma>0$) and
$\beta$-smooth for all $z\in\mathcal{Z}$. If the step size satisfies the
inequality $\eta_{t}\leq 2/(\beta+\gamma)$, then for any $t\leq T+1$ it is
true that

$\displaystyle\bigg{\|}w_{t}-w^{(i)}_{t}-\eta_{t}\bigg{(}\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z)\bigg{)}\bigg{\|}_{2}\leq\left(1-\frac{\eta_{t}\gamma}{2}\right)\|w_{t}-w^{(i)}_{t}\|_{2}.$

##### Proof.

The function $\frac{1}{m}\sum_{z\in J_{t}}f(\cdot,z)$ is also $\beta$-smooth
and $\gamma$ strongly-convex for all $z\in\mathcal{Z}$ (uniformly) and the
strong convexity gives

$\displaystyle\bigg{\langle}\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z),w_{t}-w^{(i)}_{t}\bigg{\rangle}$
$\displaystyle\geq\frac{\beta\gamma}{\beta+\gamma}\|w_{t}-w^{(i)}_{t}\|^{2}_{2}+\frac{1}{(\beta+\gamma)}\|\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z)\|^{2}_{2}.$ (62)

We expand the squared norm as follows

$\displaystyle\bigg{\|}w_{t}-w^{(i)}_{t}-\eta_{t}\bigg{(}\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z)\bigg{)}\bigg{\|}^{2}_{2}$
$\displaystyle=\|w_{t}-w^{(i)}_{t}\|^{2}_{2}-2\eta_{t}\langle\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z),w_{t}-w^{(i)}_{t}\rangle$
$\displaystyle\qquad+\eta^{2}_{t}\|\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla f(w^{(i)}_{t},z)\|^{2}_{2}$
$\displaystyle\leq\|w_{t}-w^{(i)}_{t}\|^{2}_{2}+\eta^{2}_{t}\|\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z)\|^{2}_{2}$
$\displaystyle\qquad-2\eta_{t}\bigg{(}\frac{\beta\gamma}{\beta+\gamma}\|w_{t}-w^{(i)}_{t}\|^{2}_{2}+\frac{1}{(\beta+\gamma)}\|\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z)\|^{2}_{2}\bigg{)}$ (63)
$\displaystyle=\left(1-2\eta_{t}\frac{\beta\gamma}{\beta+\gamma}\right)\|w_{t}-w^{(i)}_{t}\|^{2}_{2}$
$\displaystyle\qquad+\eta_{t}\left(\eta_{t}-\frac{2}{\beta+\gamma}\right)\|\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w_{t},z)-\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w^{(i)}_{t},z)\|^{2}_{2}$
$\displaystyle\leq\left(1-2\eta_{t}\frac{\beta\gamma}{\beta+\gamma}\right)\|w_{t}-w^{(i)}_{t}\|^{2}_{2}.$
(64)

We apply the inequality (62) to derive (63). The inequality (64) holds since
$\eta_{t}\leq 2/(\beta+\gamma)$ and $\beta\geq\gamma$. Also

$\displaystyle 2\eta_{t}\frac{\beta\gamma}{\beta+\gamma}$ $\displaystyle\geq
2\eta_{t}\frac{\beta\gamma}{2\beta}=\eta_{t}\gamma.$ (65)

We derive the bound of the lemma through (64), (65) and $\sqrt{1-x}\leq 1-x/2$
for $x\in[0,1]$. $\Box$

###  B.2 Proof of Lemma 12 (Growth Recursion—Strongly-Convex Loss)

$\displaystyle G_{\\!J_{t}}(w)\triangleq w-\eta_{t}\frac{1}{m}\sum_{z\in
J_{t}}\nabla f(w,z),\,\,\,G_{\\!J^{(i)}_{t}}(w)\triangleq
w-\eta_{t}\frac{1}{m}\sum_{z\in J^{(i)}_{t}}\nabla f(w,z)$ (66)

Under the same batch selection $J_{t}\equiv J^{(i)}_{t}$ we find the first
part of the statement as

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{(i)}_{t})\|$
$\displaystyle\leq\bigg{\|}w_{t}-\eta_{t}\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w,z)|_{w=w_{t}}-w^{(i)}_{t}+\eta_{t}\frac{1}{m}\sum_{z\in J_{t}}\nabla
f(w,z)|_{w=w^{(i)}_{t}}\bigg{\|}$
$\displaystyle\leq(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|,$ (67)

as Lemma 15 suggests. Similarly, we find the bound for the case $J_{t}\neq
J^{(i)}_{t}$ as

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|$
$\displaystyle=\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{(i)}_{t})+G_{\\!J_{t}}(w^{(i)}_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{(i)}_{t})\|+\|G_{\\!J_{t}}(w^{(i)}_{t})-G_{\\!J^{(i)}_{t}}(w^{(i)}_{t})\|$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{(i)}_{t})\|+\frac{\eta_{t}}{m}\left(\|\nabla
f(w^{(i)}_{t},z_{i})\|+\|\nabla f(w^{(i)}_{t},z^{\prime}_{i})\|\right)$
$\displaystyle\leq(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{\eta_{t}}{m}\left(\|\nabla
f(w^{(i)}_{t},z_{i})\|+\|\nabla f(w^{(i)}_{t},z^{\prime}_{i})\|\right).$

For both cases we have

$\displaystyle\|w_{t+1}-w^{(i)}_{t+1}\|$
$\displaystyle\leq(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{1}{m}\left(\|\nabla
f(w^{(i)}_{t},z_{i})\|+\|\nabla
f(w^{(i)}_{t},z^{\prime}_{i})\|\right)\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}$
$\displaystyle\leq(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{1}{m}\left(\sup_{t,S^{(i)},z_{i}}\|\nabla
f(w^{(i)}_{t},z_{i})\|+\sup_{t,S^{(i)}}\|\nabla
f(w^{(i)}_{t},z^{\prime}_{i})\|\right)\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}$
$\displaystyle\leq(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{2}{m}\left(\sup_{t,S^{(i)},z_{i}}\|\nabla
f(w^{(i)}_{t},z_{i})\|\right)\eta_{t}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}$
$\displaystyle=(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{2}{m}\left(\sup_{t,S^{(i)},z}\|\nabla
f(w^{(i)}_{t},z)\|\right)\eta_{t}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}$
$\displaystyle=(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{2}{m}\left(\sup_{t,S^{(1)},z}\|\nabla
f(w^{(1)}_{t},z)\|\right)\eta_{t}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}$
$\displaystyle=(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{2}{m}\left(\sup_{t,S,z^{\prime}}\|\nabla
f(w_{t},z^{\prime})\|\right)\eta_{t}\mathds{1}_{J_{t}\neq J^{(i)}_{t}}$
$\displaystyle\leq(1-\frac{\eta_{t}\gamma}{2})\|w_{t}-w^{(i)}_{t}\|+\frac{2\tilde{L}}{m}\eta_{t}\mathds{1}_{J_{t}\neq
J^{(i)}_{t}}.$ (68)

The last inequality completes the proof. $\Box$

###  B.3 Proof Of Theorem 14 (Lower Bound—Strongly-Convex Loss)

Set the initial point $w_{1}=0$ (independent of the data-set) and select the
loss function as
$f(w,\mathbf{z})=(w-\mathbf{z})^{\mathrm{T}}\Lambda(w-\mathbf{z})/2$,
$w\in\mathbb{R}^{d}$,
$\Lambda\triangleq\text{diag}(\beta,\gamma,\ldots,\gamma)$,
$\mathbf{z}_{i}=(z^{1}_{i},z^{2}_{i},\ldots,z^{d}_{i})\in\\{-L/\gamma\sqrt{d},+L/\gamma\sqrt{d}\\}^{d}$,
$i\in\\{1,2,\ldots,n\\}$, $\mathbb{P}(z_{i}^{j}=L/\gamma\sqrt{d})=1/2$ and
$z^{\ell}_{k}\perp z^{\ell^{\prime}}_{k^{\prime}}$ for all distinct pairs
$(\ell,k)$, $(\ell^{\prime},k^{\prime})$. Then the SGD updates with step size
$\eta_{t}=c/(\beta+\gamma)$ for $c\leq 1$ are

$\displaystyle w_{t+1}$
$\displaystyle=w_{t}-\eta_{t}\Lambda\left(w_{t}-\frac{1}{m}\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}\right)=\left(1-\frac{c}{\beta+\gamma}\Lambda\right)w_{t}+\frac{c\Lambda}{(\beta+\gamma)m}\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}.$ (69)

For any initial point (independent of the data-set), the output of the
algorithm is

$\displaystyle A_{\mathcal{R}}(S)$ $\displaystyle\equiv w_{T+1}$
$\displaystyle=\frac{c}{(\beta+\gamma)m}\sum^{T}_{t=1}\left(\prod^{T}_{j=t+1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)\right)\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}$
$\displaystyle=\frac{c}{(\beta+\gamma)m}\sum^{T}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{T-t}\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}.$ (70)

Then the norm of the gradient for any $\bar{t}\leq T$ is bounded as

$\displaystyle\|\nabla f(w_{\bar{t}+1},\mathbf{z})\|$
$\displaystyle=\bigg{\|}\frac{c\Lambda}{(\beta+\gamma)m}\sum^{\bar{t}}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{\bar{t}-t}\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}-\Lambda\mathbf{z}\bigg{\|}$
$\displaystyle\leq\bigg{\|}\frac{c\Lambda}{(\beta+\gamma)m}\sum^{\bar{t}}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{\bar{t}-t}\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}\bigg{\|}+\|\Lambda\mathbf{z}\|$
$\displaystyle\leq\frac{\sqrt{\sum^{d}_{k=1}\lambda^{2}_{k}\left(1-\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{\bar{t}}\right)^{2}}}{\gamma\sqrt{d}}L+\frac{\sqrt{\beta^{2}+(d-1)\gamma^{2}}}{\gamma\sqrt{d}}L$
$\displaystyle\leq\frac{\sqrt{\sum^{d}_{k=1}\lambda^{2}_{k}}}{\gamma\sqrt{d}}L+\frac{\sqrt{\beta^{2}+(d-1)\gamma^{2}}}{\gamma\sqrt{d}}L$
$\displaystyle=2\frac{\sqrt{\beta^{2}+(d-1)\gamma^{2}}}{\gamma\sqrt{d}}L$
$\displaystyle\leq 4L,$ (71)

for any $d$ such that

$\beta^{2}+(d-1)\gamma^{2}<4\gamma^{2}d\implies\beta^{2}-\gamma^{2}<3\gamma^{2}d\implies
d>\frac{\beta^{2}-\gamma^{2}}{3\gamma^{2}}.$

Similarly, for any $\tilde{c}\in(0,1)$

$\displaystyle\|\nabla
f(\tilde{c}A_{\mathcal{R}}(S)+(1-\tilde{c})A_{\mathcal{R}}(S^{(i)}),\mathbf{z})\|$
$\displaystyle=\bigg{\|}\frac{\tilde{c}c\Lambda}{(\beta+\gamma)m}\sum^{T}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{T-t}\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}+\frac{(1-\tilde{c})c\Lambda}{(\beta+\gamma)m}\sum^{T}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{T-t}\Lambda\sum_{\mathbf{z}\in
J^{(i)}_{t}}\mathbf{z}-\lambda\mathbf{z}\bigg{\|}$
$\displaystyle\leq\tilde{c}\bigg{\|}\frac{c\Lambda}{(\beta+\gamma)m}\sum^{T}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{T-t}\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}\bigg{\|}$
$\displaystyle\quad\quad\quad+(1-\tilde{c})\bigg{\|}\frac{c\Lambda}{(\beta+\gamma)m}\sum^{T}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{T-t}\Lambda\sum_{\mathbf{z}\in
J^{(i)}_{t}}\mathbf{z}\bigg{\|}+\|\Lambda\mathbf{z}\|$
$\displaystyle\leq\frac{\sqrt{\sum^{d}_{k=1}\lambda^{2}_{k}}}{\gamma\sqrt{d}}L+\frac{\sqrt{\beta^{2}+(d-1)\gamma^{2}}}{\gamma\sqrt{d}}L$
$\displaystyle=2\frac{\sqrt{\beta^{2}+(d-1)\gamma^{2}}}{\gamma\sqrt{d}}L$
$\displaystyle\leq 4L.$

Additionally,

$\displaystyle\epsilon_{\mathrm{gen}}$
$\displaystyle=\mathbb{E}_{S,z,\mathcal{R}}[f(A_{\mathcal{R}}(S);\mathbf{z})-\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}_{i})]$
$\displaystyle=\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}^{\prime}_{i})]-\frac{1}{n}\sum^{n}_{i=1}f(A_{\mathcal{R}}(S);\mathbf{z}_{i})\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\left[\frac{1}{n}\sum^{n}_{i=1}(A_{\mathcal{R}}(S)-\mathbf{z}^{\prime}_{i})^{\mathrm{T}}\Lambda(A_{\mathcal{R}}(S)-\mathbf{z}^{\prime}_{i})-\frac{1}{n}\sum^{n}_{i=1}(A_{\mathcal{R}}(S)-\mathbf{z}_{i})^{\mathrm{T}}\Lambda(A_{\mathcal{R}}(S)-\mathbf{z}_{i})\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}_{S,S^{\prime},\mathcal{R}}\Bigg{[}\frac{1}{n}\sum^{n}_{i=1}\big{(}A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda
A_{\mathcal{R}}(S)-2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}^{\prime}_{i}+(\mathbf{z}^{\prime}_{i})^{\mathrm{T}}\Lambda\mathbf{z}^{\prime}_{i}$
$\displaystyle\qquad\qquad\qquad\qquad-A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda
A_{\mathcal{R}}(S)+2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}_{i}-(\mathbf{z}_{i})^{\mathrm{T}}\Lambda\mathbf{z}_{i}\big{)}\Bigg{]}$
$\displaystyle=\frac{1}{2n}\sum^{n}_{i=1}\big{(}-2\mathbb{E}_{S,\mathcal{R}}[A^{\mathrm{T}}_{\mathcal{R}}(S)]\Lambda\underbrace{\mathbb{E}_{S^{\prime}}[\mathbf{z}^{\prime}_{i}]}_{=0}+\underbrace{\mathbb{E}_{S^{\prime}}[(\mathbf{z}^{\prime}_{i})^{\mathrm{T}}\Lambda\mathbf{z}^{\prime}_{i}]-\mathbb{E}_{S}[(\mathbf{z}_{i})^{\mathrm{T}}\Lambda\mathbf{z}_{i}]}_{=0}+\mathbb{E}_{S,\mathcal{R}}[2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}_{i}]\big{)}$
$\displaystyle=\frac{1}{2n}\sum^{n}_{i=1}\mathbb{E}_{S,\mathcal{R}}[2A^{\mathrm{T}}_{\mathcal{R}}(S)\Lambda\mathbf{z}_{i}]$
$\displaystyle=\frac{c}{(\beta+\gamma)nm}\sum^{n}_{i=1}\mathbb{E}_{S,\mathcal{R}}\Bigg{[}\mathbf{z}^{T}_{i}\Lambda\sum^{T}_{t=1}\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{T-t}\Lambda\sum_{\mathbf{z}\in
J_{t}}\mathbf{z}\Bigg{]}.$

Define

$\displaystyle
M^{t}\triangleq\Lambda\left(1-\frac{c}{\beta+\gamma}\Lambda\right)^{T-t}\Lambda.$
(72)

If $\mathbf{z}_{i}\in J_{t}$ then $\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{k}]=L^{2}/\gamma^{2}d$, otherwise
$\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in J_{t}}z^{k}]=0$, thus
$\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{k}]=\mathds{1}_{\mathbf{z}_{i}\in J_{t}}L^{2}/\gamma^{2}d$ for any
(randomized) selection rule, and $\sum^{n}_{i=1}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}=m$ for any $A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ (Definition 1)
with batch-size $m\equiv|J_{t}|$ for all $t$. Therefore, we obtain

$\displaystyle\frac{c}{(\beta+\gamma)nm}\mathbb{E}_{\mathcal{R}}\left[\sum^{n}_{i=1}\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\mathbb{E}_{S}[z^{k}_{i}\sum_{\mathbf{z}\in
J_{t}}z^{k}]]\right]$
$\displaystyle=\frac{c}{\gamma^{2}(\beta+\gamma)nm}\mathbb{E}_{\mathcal{R}}\left[\sum^{n}_{i=1}\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}L^{2}/d\right]$
$\displaystyle=\frac{cL^{2}}{\gamma^{2}d(\beta+\gamma)nm}\mathbb{E}_{\mathcal{R}}\left[\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\sum^{n}_{i=1}\mathds{1}_{\mathbf{z}_{i}\in
J_{t}}\right]$
$\displaystyle=\frac{cL^{2}}{\gamma^{2}d(\beta+\gamma)n}\mathbb{E}_{\mathcal{R}}\left[\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}\right]$
$\displaystyle=\frac{cL^{2}}{\gamma^{2}d(\beta+\gamma)n}\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}.$

Then we find $M_{kk}$ as

$\displaystyle\sum^{T}_{t=1}M^{t}_{kk}$
$\displaystyle=\lambda^{2}_{k}\sum^{T}_{t=1}\prod^{T}_{j=t+1}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{j}$
$\displaystyle=\lambda^{2}_{k}\sum^{T}_{t=1}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T-t}$
$\displaystyle=\lambda^{2}_{k}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}\sum^{T}_{t=1}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{-t}$
$\displaystyle=\lambda^{2}_{k}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}\frac{1-\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{-T}}{1-(1-\frac{c\lambda_{k}}{\beta+\gamma})^{-1}}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{-1}$
$\displaystyle=\lambda^{2}_{k}\frac{\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}-1}{1-\frac{c\lambda_{k}}{\beta+\gamma}-1}$
$\displaystyle=\frac{\lambda_{k}}{c}(\beta+\gamma)\left(1-\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}\right).$
(73)

Thus

$\displaystyle\epsilon_{\mathrm{gen}}$
$\displaystyle=\frac{L^{2}}{\gamma^{2}d(\beta+\gamma)n}\sum^{d}_{k=1}\sum^{T}_{t=1}M^{t}_{kk}$
$\displaystyle=\frac{cL^{2}}{\gamma^{2}d(\beta+\gamma)n}\sum^{d}_{k=1}\frac{\lambda_{k}}{c}(\beta+\gamma)\left(1-\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}\right)$
$\displaystyle=\frac{L^{2}}{\gamma^{2}dn}\sum^{d}_{k=1}\lambda_{k}\left(1-\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}\right)$
$\displaystyle=\frac{L^{2}}{\gamma^{2}dn}\sum^{d}_{k=1}\lambda_{k}-\frac{L^{2}}{\gamma^{2}dn}\sum^{d}_{k=1}\lambda_{k}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}$
$\displaystyle\geq\frac{L^{2}}{\gamma
n}-\frac{L^{2}}{\gamma^{2}dn}\sum^{d}_{k=1}\lambda_{k}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}$
$\displaystyle=\frac{L^{2}}{\gamma
n}-\frac{L^{2}(\beta+\gamma)}{c\gamma^{2}dn}\sum^{d}_{k=1}\frac{c\lambda_{k}}{\beta+\gamma}\left(1-\frac{c\lambda_{k}}{\beta+\gamma}\right)^{T}$
$\displaystyle\geq\frac{L^{2}}{\gamma
n}-\frac{L^{2}(\beta+\gamma)}{c\gamma^{2}n}\frac{1}{T+1}\left(1-\frac{1}{T+1}\right)^{T}$
$\displaystyle=\frac{L^{2}}{\gamma
n}-\frac{L^{2}(\beta+\gamma)}{c\gamma^{2}n}\frac{1}{T+1}\left(\frac{T}{T+1}\right)^{T}$
$\displaystyle\geq\frac{L^{2}}{\gamma
n}-\frac{L^{2}(\beta+\gamma)}{c\gamma^{2}n}\frac{1}{T+1}$
$\displaystyle=\frac{L^{2}}{\gamma
n}\left(1-\frac{(\beta+\gamma)}{c\gamma}\frac{1}{T+1}\right)$
$\displaystyle=\frac{L^{2}}{\gamma
n}\left(1-\frac{1}{\eta_{t}\gamma}\frac{1}{T+1}\right)$ (74)

Note that the last expression is non-trivial for all $\eta_{t}>1/\gamma(T+1)$.
For $2/\gamma(T+1)\leq\eta_{t}=c/(\beta+\gamma)$, let $\tilde{L}\equiv 4L$
($L$ is a free parameter in the example above) and it is true that
$\tilde{L}_{\eta_{t},T}(f)\leq\tilde{L}$ due to the inequalities (71) and
(B.3) (and $\tilde{L}_{\eta_{t},T}(f)$ is defined in (24)). Thus for
$d\geq(\beta^{2}-\gamma^{2})/3\gamma^{2}$ the inequality (74) holds for all
$A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)$ and the smallest value of
$\eta_{t}$ gives

$\displaystyle\inf_{A_{\mathcal{R}}\in\mathcal{A}(\eta_{t},T)}\sup_{\begin{subarray}{c}(f,\mathcal{D})\in\mathcal{SC}^{\tilde{L}}_{\beta,\gamma}\end{subarray}}|\epsilon_{\mathrm{gen}}(f,\mathcal{D},A_{\mathcal{R}})|\geq\frac{\tilde{L}^{2}}{32\gamma
n},$ (75)

as claimed. $\Box$

##  Appendix C Inherent Limitations of Uniform Stability

Herein, we demonstrate that the proof techniques in [20] produce vacuous
generalization bounds for incremental gradient methods [42, Algorithm 3], [6,
5, 36, 17], for general Lipschitz and smooth (strongly) convex losses.

###  C.1 Incremental Gradient Method: Convex Loss

Let the batch size be $m=1$ (since $m=1$ has been considered in [20]). Then
the update at time $t$ has the form

$w_{t+1}=w_{t}-\eta_{t}\nabla f(w_{t},z_{J_{t}}),$

and $J_{t}=(t-1)\mod n+1\in[1,T]$ ($T$ the total number of iterations) is the
sample that the algorithm selects at time. Consider the neighboring sequences
$S=(z_{1},z_{2},\ldots,z_{i^{*}},\ldots,z_{n})$ and $S^{\prime}\equiv
S^{(i^{*})}=(z_{1},z_{2},\ldots,z_{i^{*}}^{\prime},\ldots,z_{n})$ (where
$i^{*}$ is $1\leq i^{*}\leq n$). Define $z_{J_{t}}^{\prime}$ as any element in
$S^{\prime}$. Note that the mappings $G_{t}(\cdot)$ and
$G_{t}(\cdot)^{\prime}$ are

$G_{t}(w)=w-\eta_{t}\nabla f(w,z_{J_{t}}),\quad\text{for }z_{J_{t}}\in S$
$G_{t}^{\prime}(w)=w-\eta_{t}\nabla f(w,z_{J_{t}}^{\prime}),\quad\text{for
}z_{J_{t}}^{\prime}\in S^{\prime}.$

At this point we will consider cases for clarity.

##### Case 1.

$T<n$. Since the step-size sequence is a non-increasing the mappings have to
be different at time $t=1$, as we prove below. In fact, the method in [20] for
convex loss gives

$\displaystyle\sup_{S,S^{\prime},z}\|w_{T}-w_{T}^{\prime}\|$
$\displaystyle=\sup_{S,S^{(i^{*})},z}\|G_{T-1}(w_{T-1})-G_{T-1}^{\prime}(w_{T-1}^{\prime})\|$
$\displaystyle=\sup_{S,S^{(i^{*})},z}\|G_{T-1}(w_{T-1})-G_{T-1}^{\prime}(w_{T-1}^{\prime})\|$
$\displaystyle\leq\sup_{S,S^{(i^{*})},z}\|w_{T-1}-w_{T-1}^{\prime}\|$
$\displaystyle=\sup_{S,S^{(i^{*})},z}\|G_{T-2}(w_{T-2})-G_{T-2}^{\prime}(w_{T-2}^{\prime})\|$
$\displaystyle=\sup_{S,S^{(i^{*})},z}\|G_{T-2}(w_{T-2})-G_{T-2}(w_{T-2}^{\prime})\|$
$\displaystyle\leq\sup_{S,S^{(i^{*})},z}\|w_{n-2}-w_{n-2}^{\prime}\|$
$\displaystyle\quad\vdots$
$\displaystyle=\sup_{S,S^{(i^{*})},z}\|G_{1}(w_{1})-G_{1}^{\prime}(w_{1}^{\prime})\|\quad\text{
because of the }\sup\text{ we have here }G_{1}(\cdot)\neq
G_{1}^{\prime}(\cdot)$ $\displaystyle\leq\|w_{1}-w_{1}^{\prime}\|+2L\eta_{1}$
$\displaystyle\leq\|w_{0}-w_{0}^{\prime}\|+2L\eta_{1}$
$\displaystyle=2L\eta_{1}.$

Then the generalization error in [20] is bounded as

$\displaystyle\sup_{S,S^{\prime},z}\mathbb{E}_{A}[f(A(S),z)-f(A(S^{\prime}),z)]\leq
L\sup_{S,S^{\prime},z}\|w_{n}-w_{n}^{\prime}\|\leq 2L^{2}\eta_{1}.$ (76)

On the other hand we have established that (Theorem 5)

$|\epsilon_{\text{gen}}|\leq\frac{2L^{2}}{n}\sum^{T}_{t=1}\eta_{t},$

which is the optimal generalization bound for the incremental gradient
algorithm, while the technique in [20] gives an evidently vacuous result.

##### Case 2.

$T=K\times n$, where $K$ is the total number of epochs. Let the step-size be
$\eta_{t}$. Then similarly to the Case 1 above by induction we get

$\displaystyle\sup_{S,S^{\prime},z}\|w_{T}-w^{\prime}_{T}\|\leq
2L\sum^{K-1}_{k=0}\eta_{kn+1}.$ (77)

As a consequence the method in [20] gives

$\displaystyle\sup_{S,S^{\prime},z}\mathbb{E}_{A}[f(A(S),z)-f(A(S^{\prime}),z)]\leq
L\sup_{S,S^{\prime},z}\|w_{n}-w_{n}^{\prime}\|\leq
2L^{2}\sum^{K-1}_{k=0}\eta_{kn+1}.$ (78)

For instance, for a step-size choice $\eta_{t}=\beta^{-1}/((t-1)\mod n+1)$
(which we restart at the end of each epoch), the last expression gives

$\displaystyle\sup_{S,S^{\prime},z}\mathbb{E}_{A}[f(A(S),z)-f(A(S^{\prime}),z)]\leq
L\sup_{S,S^{\prime},z}\|w_{n}-w_{n}^{\prime}\|\leq 2L^{2}K\eta_{1}.$ (79)

This is of order $\mathcal{O}(1)$, because $K$ is an integer. On the other
hand we have established the optimal bound

$\displaystyle|\epsilon_{\text{gen}}|\leq\frac{2L^{2}}{n}\sum^{T}_{t=1}\eta_{t}=\frac{2L^{2}}{n}\sum^{Kn}_{t=1}\eta_{t}=\frac{2KL^{2}}{n}\sum^{n}_{t=1}\frac{1}{\beta
t}\leq\frac{2L^{2}K(\log(n)+1)}{\beta n},$ (80)

which is evidently of order $\mathcal{O}(\log(n)/n)$.

##### Case 3.

$T=K\times n$, where $K$ is the total number of epochs. Let the step-size be
fixed $\eta_{t}=\eta$.
Then our lower bound (Theorem 6) gives

$\displaystyle|\epsilon_{\text{gen}}|\geq\frac{L^{2}}{2n}\sum^{Kn}_{t=1}=K\frac{\eta
L^{2}}{2}=\Omega(1),$ (81)

and eventually the upper bounds in [20] and in our work are of order
$\mathcal{O}(1)$. The problem is hopeless with such a choice of the step-size
and for such a large number of iterations for all batch schedules. Note that
this impossibility result is new.

###  C.2 Incremental Gradient Method: $\gamma$-Strongly-Convex Loss

In the case of strongly-convex losss (the gradient mappings are now
$1-\eta\gamma$ expansive [20]), we choose a fixed step size $\eta_{t}=\eta$,
and $T=K\times n$ (for $K$ number of epochs). Then, for the method in [20], we
consider the following two cases.

##### Case 1.

One epoch, $T=n$. We can expand as

$\displaystyle\|w_{n}-w_{n}^{\prime}\|$
$\displaystyle=\|G_{n-1}(w_{n-1})-G_{n-1}^{\prime}(w_{n-1}^{\prime})\|$
$\displaystyle=\|G_{n-1}(w_{n-1})-G_{n-1}(w_{n-1}^{\prime})\|$
$\displaystyle\leq(1-\eta\gamma)\|w_{n-1}-w_{n-1}^{\prime}\|$
$\displaystyle=(1-\eta\gamma)\|G_{n-2}(w_{n-2})-G_{n-2}^{\prime}(w_{n-2}^{\prime})\|$
$\displaystyle=(1-\eta\gamma)\|G_{n-2}(w_{n-2})-G_{n-2}(w_{n-2}^{\prime})\|$
$\displaystyle\leq(1-\eta\gamma)^{2}\|w_{n-2}-w_{n-2}^{\prime}\|$
$\displaystyle\quad\vdots$
$\displaystyle\leq(1-\eta\gamma)^{n-i^{*}-2}\|G_{i^{*}+1}(w_{i^{*}+1})-G_{i^{*}+1}^{\prime}(w_{i^{*}+1}^{\prime})\|$
$\displaystyle=(1-\eta\gamma)^{n-i^{*}-2}\|G_{i^{*}+1}(w_{i^{*}+1})-G_{i^{*}+1}(w_{i^{*}+1}^{\prime})\|$
$\displaystyle\leq(1-\eta\gamma)^{n-i^{*}-1}\|w_{i^{*}+1}-w_{i^{*}+1}^{\prime}\|$
$\displaystyle=(1-\eta\gamma)^{n-i^{*}-1}\|G_{i^{*}}(w_{i^{*}})-G_{i^{*}}^{\prime}(w_{i^{*}}^{\prime})\|\quad\text{
here }G_{i^{*}}(\cdot)\neq G_{i^{*}}^{\prime}(\cdot)$
$\displaystyle\leq(1-\eta\gamma)^{n-i^{*}}\|w_{i^{*}}-w_{i^{*}}^{\prime}\|+2L\eta(1-\eta\gamma)^{n-i^{*}-1}$
$\displaystyle=(1-\eta\gamma)^{n-i^{*}}\|G_{i^{*}-1}(w_{i^{*}-1})-G_{i^{*}-1}^{\prime}(w_{i^{*}-1}^{\prime})\|+2L\eta(1-\eta\gamma)^{n-i^{*}-1}$
$\displaystyle=(1-\eta\gamma)^{n-i^{*}}\|G_{i^{*}-1}(w_{i^{*}-1})-G_{i^{*}-1}(w_{i^{*}-1}^{\prime})\|+2L\eta(1-\eta\gamma)^{n-i^{*}-1}$
$\displaystyle\leq(1-\eta\gamma)^{n-i^{*}+1}\|w_{i^{*}-1}-w^{\prime}_{i^{*}-1}\|+(1-\eta\gamma)^{i^{*}}2L\eta(1-\eta\gamma)^{n-i^{*}-1}$
$\displaystyle\quad\vdots$
$\displaystyle\leq(1-\eta\gamma)^{n}\|w\\_{0}-w\\_{0}^{\prime}\|+2L\eta(1-\eta\gamma)^{n-i^{*}-1}$
$\displaystyle=2L\eta(1-\eta\gamma)^{n-i^{*}-1}.$

Then the approach in [20] gives the following vacuous bound

$\displaystyle\sup_{S,S^{\prime},z}\mathbb{E}_{A}[f(A(S),z)-f(A(S^{\prime}),z)]\leq
L\sup_{S,S^{\prime},z}\|w_{n}-w_{n}^{\prime}\|\leq
2L^{2}\sup_{i^{*}}(1-\eta\gamma)^{n-i^{*}-1}=2L^{2}\eta(1-\eta\gamma)^{-1}.$

The above bound is of order $\mathcal{O}(1)$. In contrast, we prove the
optimal rate in Theorem 13.

##### Case 2.

Multiple epochs, $T=K\times n$. By induction on Case 1 and the approach in
[20], we obtain

$\displaystyle\sup_{S,S^{\prime},z}\mathbb{E}_{A}[f(A(S),z)-f(A(S^{\prime}),z)]\leq
L\sup_{S,S^{\prime},z}\|w_{n}-w_{n}^{\prime}\|\leq
2L^{2}\sup_{i^{*}}\sum^{K}_{k=1}(1-\eta\gamma)^{kn-i^{*}-1}=\mathcal{O}(1).$

In contrast, we prove the correct rate in Theorem 13. Our bounds are of the
order $\mathcal{O}(1/n)$ which is the optimal generalization rate in this
case.