# Black-Box Generalization

Konstantinos E. Nikolakakis
<EMAIL_ADDRESS>Farzin Haddadpour
<EMAIL_ADDRESS>Dionysios S. Kalogerias
<EMAIL_ADDRESS>Amin Karbasi
<EMAIL_ADDRESS>
###### Abstract

We provide the first generalization error analysis for black-box learning
through derivative-free optimization. Under the assumption of a Lipschitz and
smooth unknown loss, we consider the Zeroth-order Stochastic Search (ZoSS)
algorithm, that updates a $d$-dimensional model by replacing stochastic
gradient directions with stochastic differences of $K+1$ perturbed loss
evaluations per dataset (example) query. For both unbounded and bounded
possibly nonconvex losses, we present the first generalization bounds for the
ZoSS algorithm. These bounds coincide with those for SGD, and rather
surprisingly are independent of $d$, $K$ and the batch size $m$, under
appropriate choices of a slightly decreased learning rate. For bounded
nonconvex losses and a batch size $m=1$, we additionally show that both
generalization error and learning rate are independent of $d$ and $K$, and
remain essentially the same as for the SGD, even for two function evaluations.
Our results extensively extend and consistently recover established results
for SGD in prior work, on both generalization bounds and corresponding
learning rates. If additionally $m=n$, where $n$ is the dataset size, we
derive generalization guarantees for full-batch GD as well.

Keywords: Generalization Error, Zeroth-Order Optimization, Black-Box Learning

##  1 Introduction

Learning methods often rely on empirical risk minimization objectives that
highly depend on a limited training data-set. Known gradient-based approaches
such as SGD train and generalize effectively in reasonable time [1]. In
contrast, emerging applications such as convex bandits [2, 3, 4], black-box
learning [5], federated learning [6], reinforcement learning [7, 8], learning
linear quadratic regulators [9, 10], and hyper-parameter tuning [11] stand in
need of gradient-free learning algorithms [11, 12, 13, 14] due to an unknown
loss/model or impossible gradient evaluation.

Given two or more function evaluations, zeroth-order algorithms (see, e.g.,
[14, 15]) aim to estimate the true gradient for evaluating and updating model
parameters (say, of dimension $d$). In particular, Zeroth-order Stochastic
Search (ZoSS) [13, Corollary 2], [16, Algorithm 1] uses $K+1$ function
evaluations ($K\geq 1$), while deterministic zeroth-order approaches [5,
Section 3.3] require at least $K\geq d+1$ queries. The optimization error of
the ZoSS algorithm is optimal as shown in prior work for convex problems [13],
and suffers at most a factor of $\sqrt{d/K}$ in the convergence rate as
compared with SGD. In addition to the optimization error, the importance of
generalization error raises the question of how well zeroth-order algorithms
generalize to unseen examples. In this paper, we show that the generalization
error of ZoSS essentially coincides with that of SGD, under the choice of a
slightly decreased learning rate. Assuming a Lipschitz and smooth loss
function, we establish generalization guarantees for ZoSS, by extending
stability-based analysis for SGD [1], to the gradient-free setting. In
particular, we rely on the celebrated result that uniform algorithmic
stability implies generalization [1, 17, 18].

Early works [17, 19, 20, 21, 22] first introduced the notion of stability, and
the connection between (uniform) stability and generalization. Recently,
alternative notions of stability and generalization gain attention such as
locally elastic stability [23], VC-dimension/flatness measures [24],
distributional stability [25, 26, 27], information theoretic bounds [16, 28,
29, 30, 31, 32, 33] mainly based on assuming a sub-Gaussian loss, as well as
connections between differential privacy and generalization [34, 35, 36, 37].

In close relation to our paper, Hardt et al. [1] first showed uniform
stability final-iterate bounds for vanilla SGD. More recent works develop
alternative generalization error bounds based on high-probability analysis
[38, 39, 40, 41] and data-dependent variants [42], or under different
assumptions than those of prior works such as as strongly quasi-convex [43],
non-smooth convex [44, 45, 46, 47], and pairwise losses [48, 49]. In the
nonconvex case, [50] provide bounds that involve on-average variance of the
stochastic gradients. Generalization performance of other algorithmic variants
lately gain further attention, including SGD with early momentum [51],
randomized coordinate descent [52], look-ahead approaches [53], noise
injection methods [54], and stochastic gradient Langevin dynamics [55, 56, 57,
58, 59, 60, 61, 62].

Recently, stability and generalization of full-bath GD has also been studied;
see, e.g., [63, 64, 65, 66, 67]. In particular, Charles and Papailiopoulos.
[64] showed instability of GD for nonconvex losses. Still, such instability
does not imply a lower bound on the generalization error of GD (in
expectation). In fact, Hoffer et al. [63] showed empirically that the
generalization of GD is not affected by the batch-size, and for large enough
number of iterations GD generalizes comparably to SGD. Our analysis agree with
the empirical results of Hoffer et al. [63], as we show that (for smooth
losses) the generalization of ZoSS (and thus of SGD) is independent of the
batch size.

#### Notation.

We denote the training data-set $S$ of size $n$ as $\\{z_{i}\\}^{n}_{i=1}$,
where $z_{i}$ are i.i.d. observations of a random variable $Z$ with unknown
distribution $\mathcal{D}$. The parameters of the model are vectors of
dimension $d$, denoted by $W\in\mathbb{R}^{d}$, and $W_{t}$ is the output at
time $t$ of a (randomized) algorithm $A_{S}$. The (combined) loss function
$f(\cdot,z):\mathbb{R}^{d}\rightarrow\mathbb{R}^{+}$ is uniformly Lipschitz
and smooth for all $z\in\mathcal{Z}$. We denote the Lipschitz constant as $L$
and the smoothness parameter by $\beta$. The number of function (i.e., loss)
evaluations (required at each iteration of the ZoSS algorithm) is represented
by $K+1\in\mathbb{N}$. We denote by $\Delta f$ the smoothed approximation of
the loss gradient, associated with parameter $\mu$. The parameter
$\Gamma^{d}_{K}\triangleq\sqrt{(3d-1)/K}+1$ prominently appears in our
results. We denote the gradient of the loss function with respect to model
parameters $W$, by $\nabla f(W,z)\equiv\nabla_{w}f(w,z)|_{w=W}$. We denote the
mini batch at $t$ by $J_{t}$, and $m\triangleq|J_{t}|$.

Generalization Error Bounds: ZoSS vs SGD
---
Algorithm |  Bound | NC | UB | MB
ZoSS (this work) |  |  |  |
$\alpha_{t}\leq C/(t\Gamma_{K}^{d})$ |  $\dfrac{1+(CB)^{-1}}{n}\big{(}(2+c)CL^{2}\big{)}^{\frac{1}{C\beta+1}}(eT)^{\frac{C\beta}{C\beta+1}}$ | ✓ | ✗ | ✗
SGD, $\alpha_{t}\leq C/t$ |  |  |  |
Hardt et al. [1] |  $\dfrac{1+(CB)^{-1}}{n}\big{(}2CL^{2}\big{)}^{\frac{1}{C\beta+1}}(eT)^{\frac{C\beta}{C\beta+1}}$ | ✓ | ✗ | ✗
ZoSS (this work) |  |  |  |
$\alpha_{t}\leq C/t$ |  $\dfrac{3e\big{(}1+(CB)^{-1}\big{)}^{2}}{2n}\big{(}1+(2+c)CL^{2}\big{)}T$ |  |  |
(independent of both $d$ and $K$) |  ✓ | ✗ | ✗ |
ZoSS (this work) $\alpha_{t}\leq\frac{\log\Big{(}1+\frac{C\beta}{\Gamma_{K}^{d}}\sqrt{\frac{3d-1}{K}}\Big{)}}{T\beta\sqrt{(3d-1)/K}}$ |  $\dfrac{(2+c)CL^{2}}{n}$ | ✗ | ✓ | ✓
SGD, $\alpha_{t}\leq C/T$ |  |  |  |
Hardt et al. [1] |  $\dfrac{2CL^{2}}{n}$ | ✗ | ✓ | ✓
ZoSS (this work) |  |  |  |
$\alpha_{t}\leq C/(T\Gamma_{K}^{d})$ |  $\dfrac{(2+c)L^{2}(e^{C\beta}-1)}{n\beta}$ | ✓ | ✓ | ✓
ZoSS (this work) |  |  |  |
$\alpha_{t}\leq\frac{\log(1+C\beta)}{T\beta\Gamma_{K}^{d}}$ |  $\dfrac{(2+c)CL^{2}}{n}$ |  |  |
(proper choice of $C$ in previous bound) |  ✓ | ✓ | ✓ |
ZoSS (this work) |  |  |  |
$\alpha_{t}\leq C/(t\Gamma_{K}^{d})$ |  $\dfrac{(2+c)L^{2}(eT)^{C\beta}}{n}\min\\{C+\beta^{-1},C\log(T)\\}$ | ✓ | ✓ | ✓
Table 1:  A list of the generalization error bounds developed herein for ZoSS
(Eq. 6) in comparison with SGD, with $\mu\leq
cL\Gamma^{d}_{K}/n\beta(3+d)^{3/2}$, for $c>0$. In the table, “NC” and “UB”
stand for “nonconvex” and “unbounded”, respectively. “MB”corresponds to the
mini-batch algorithm and for any batch size. Also, $\alpha_{t}$ denotes the
stepsize of ZoSS/SGD, and $T$ the total number of iterations.

###  1.1 Contributions

Under the assumption of Lipschitz and smooth loss functions, we provide
generalization guarantees for black-box learning, extending the analysis of
prior work by Hardt et al. [1] to the gradient free setting. In particular, we
establish uniform stability and generalization error bounds for the final
iterate of the ZoSS algorithm; see Table 1 for a summary of the results. In
more detail, the contributions of this work are as follows:

  * •

For unbounded and bounded losses, we show generalization error bounds
identical to SGD, with a slightly decreased learning rate. Specifically, the
generalization error bounds are independent of the dimension $d$, the number
of evaluations $K$ and the batch-size $m$. Further, a large enough number of
evaluations ($K$) provide fast generalization even in the high dimensional
regime.

  * •

For bounded nonconvex losses and single (example) query updates ($m=1$), we
show that both the ZoSS generalization error and learning rate are independent
of $d$ and $K$, similar to that of SGD [1, Theorem 3.8]. This property
guarantees efficient generalization even with two function evaluations.

  * •

In the full information regime (i.e., when the number of function evaluations
$K$ grow to $\infty$), the ZoSS generalization bounds also provide guarantees
for SGD by recovering the results in prior work [1]. Further, we derive novel
SGD bounds for unbounded nonconvex losses, as well as mini-batch SGD for any
batch size. Our results subsume generalization guarantees for full-batch ZoSS
and GD algorithms.

##  2 Problem Statement

Given a data $S\triangleq\\{z_{i}\\}^{n}_{i=1}$ of i.i.d samples $z_{i}$ from
an unknown distribution $\mathcal{D}$, 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)]$. 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}),$ (1)

and the corresponding empirical risk minimization (ERM) problem to find
$w^{*}_{s}\in\arg\min_{w}R_{S}(w)$. For a (randomized) algorithm $A_{S}$ with
input $S$ and output $W=A(S)$, the excess risk $\epsilon_{\text{excess}}$ is
bounded by the sum of the generalization error $\epsilon_{\mathrm{gen}}$ and
the optimization error $\epsilon_{\mathrm{opt}}$,

$\displaystyle\epsilon_{\mathrm{excess}}\triangleq\mathbb{E}_{S,A}[R(W)]-R(w^{*})=\underbrace{\mathbb{E}_{S,A}[R(W)-R_{S}(W)]}_{\epsilon_{\mathrm{gen}}}+(\underbrace{\mathbb{E}_{S,A}[R_{S}(W)]-R(w^{*})}_{\epsilon_{\mathrm{opt}}}).$
(2)

To analyze and control $\epsilon_{\mathrm{gen}}$, we prove uniform stability
bounds which imply generalization [1, Theorem 2.2]. Specifically, if for all
i.i.d. sequences $S,S^{\prime}\in\mathcal{Z}^{n}$ that differ in one entry, we
have
$\sup_{z}\mathbb{E}_{A}[f(A(S),z)-f(A(S^{\prime}),z)]\leq\epsilon_{\text{stab}}$,
for some $\epsilon_{\text{stab}}>0$, then
$\epsilon_{\mathrm{gen}}\leq\epsilon_{\text{stab}}$. Because the loss is
$L$-Lipschitz, $\epsilon_{\text{stab}}$ may then be chosen as
$L\sup_{S,S^{\prime}}\mathbb{E}_{A}\|A(S)-A(S^{\prime})\|$.

Our primary goal in this work is to develop uniform stability bounds for a
gradient-free algorithm $A_{S}$ of the form $w_{t+1}=w_{t}-\alpha_{t}\Delta
f_{w_{t},z}$, where $\Delta f_{w_{t},z}$ only depends on loss function
evaluations. To achieve this without introducing unnecessary assumptions, we
consider a novel algorithmic stability error decomposition approach. In fact,
the stability error introduced at time $t$ by $A_{S}$ breaks down into the
stability error of SGD and an approximation error due to missing gradient
information. Let $G_{t}(\cdot)$ and $G^{\prime}_{t}(\cdot)$ be the following
SGD update rules

$\displaystyle G_{t}(w)$ $\displaystyle\triangleq w-\alpha_{t}\nabla
f(w,z_{i_{t}}),\quad G^{\prime}_{t}(w)\triangleq w-\alpha_{t}\nabla
f(w,z^{\prime}_{i_{t}}),$ (3)

under inputs $S,S^{\prime}$ respectively, and let $i_{t}\in\\{1,2,\ldots,n\\}$
be a random index chosen uniformly and independently by the random selection
rule of the algorithm, for all $t\leq T$. Similarly we use the notation
$\tilde{G}(\cdot)$ and $\tilde{G}^{\prime}(\cdot)$ to denote the iteration
mappings of $A_{S}$, i.e.,

$\displaystyle\tilde{G}_{t}(w)$ $\displaystyle\triangleq w-\alpha_{t}{\Delta
f}_{w,z_{i_{t}}},\quad\tilde{G}^{\prime}_{t}(w)\triangleq w-\alpha_{t}{\Delta
f}_{w,z^{\prime}_{i_{t}}}.$ (4)

Then, as we also discuss later on (Lemma 2), the iterate stability error
$\tilde{G}_{t}(w)-\tilde{G}^{\prime}_{t}(w^{\prime})$ of $A_{S}$, for any
$w,w^{\prime}\in\mathbb{R}^{d}$ and for all at $t\leq T$, may be decomposed as

$\displaystyle\tilde{G}_{t}(w)-\tilde{G}^{\prime}_{t}(w)\propto\underbrace{G_{t}(w)-G^{\prime}_{t}(w^{\prime})}_{\epsilon_{\text{GBstab}}}+\underbrace{\big{[}\nabla
f(w,z_{i_{t}})-{\Delta f}_{w,z_{i_{t}}}\big{]}+\big{[}\nabla
f(w^{\prime},z^{\prime}_{i_{t}})-{\Delta
f}_{w^{\prime},z^{\prime}_{i_{t}}}\big{]}}_{\epsilon_{\text{est}}},$ (5)

where $\epsilon_{\text{GBstab}}$ denotes the gradient-based stability error
(associated with SGD), and $\epsilon_{\text{est}}$ denotes the gradient
approximation error. We now proceed by formally introducing ZoSS.

##  3 Zeroth-Order Stochastic Search (ZoSS)

As a gradient-free alternative of the classical SGD algorithm, we consider the
ZoSS scheme, with iterates generated according to the following (single-
example update) rule

$\displaystyle W_{t+1}$
$\displaystyle=W_{t}-\alpha_{t}\frac{1}{K}\sum^{K}_{k=1}\frac{f(W_{t}+\mu
U^{t}_{k},z_{i_{t}})-f(W_{t},z_{i_{t}})}{\mu}U^{t}_{k},\quad
U^{t}_{k}\sim\mathcal{N}(0,I_{d}),\quad\mu\in\mathbb{R}^{+},$ (6)

where $\alpha_{t}\geq 0$ is the corresponding learning rate (for the mini-
batch update rule we refer the reader to Section 5). At every iteration $t$,
ZoSS generates $K$ i.i.d. standard normal random vectors
$U^{t}_{k},k=1,\ldots,K$, and obtains $K+1$ loss evaluations on perturbed
model inputs. Then ZoSS evaluates a smoothed approximation of the gradient for
some $\mu>0$. In light of the discussion in Section 2, we define the ZoSS
smoothed gradient step at time $t$ as

$\displaystyle{\Delta f}^{K,\mu}_{w,z_{i_{t}}}\equiv{\Delta
f}^{K,\mu,\mathbf{U}^{t}}_{w,z_{i_{t}}}$
$\displaystyle\triangleq\frac{1}{K}\sum^{K}_{k=1}\frac{f(\omega+\mu
U^{t}_{k},z_{i_{t}})-f(\omega,z_{i_{t}})}{\mu}U^{t}_{k}.$ (7)

###  3.1 ZoSS Stability Error Decomposition

To show stability bounds for ZoSS, we decompose its error into two parts
through the stability error decomposition discussed in Section 2. Under the
ZoSS update rule, Eq. (5) holds by considering the directions ${\Delta
f}_{w,z_{i_{t}}}$ and ${\Delta f}_{w^{\prime},z^{\prime}_{i_{t}}}$ according
to ZoSS smoothed approximations (7). Then for any
$w,w^{\prime}\in\mathbb{R}^{d}$, the iterate stability error
$\tilde{G}_{t}(w)-\tilde{G}^{\prime}_{t}(w^{\prime})$ of ZoSS at $t$, breaks
down into the gradient based error $\epsilon_{\text{GBstab}}$ and
approximation error $\epsilon_{\text{est}}$.

The error term $\epsilon_{\text{GBstab}}$ expresses the stability error of the
gradient based mappings [1, Lemma 2.4] and inherits properties related to the
SGD update rule. The error $\epsilon_{\text{est}}$ captures the approximation
error of the ZoSS smoothed approximation and depends on $K$ and $\mu$. The
consistency of the smoothed approximation with respect to SGD follows from
$\lim_{K\uparrow\infty,\mu\downarrow 0}{\Delta f}^{K,\mu}_{w,z}=\nabla f(w,z)$
for all $w\in\mathbb{R}$ and $z\in\mathcal{Z}$. Further, the stability error
is also consistent since $\lim_{K\uparrow\infty,\mu\downarrow
0}|\epsilon_{\text{est}}|=0$. Later on, we use the ZoSS error decomposition in
Eq. (5) together with a variance reduction lemma (Lemma 1), to derive exact
expressions on the iterate stability error
$\tilde{G}_{t}(w)-\tilde{G}^{\prime}_{t}(w^{\prime})$ for fixed $K$ and
$\mu>0$ (see Lemma 2). Although in this paper we derive stability bounds and
bounds on the $\epsilon_{\mathrm{gen}}$, the excess risk
$\epsilon_{\text{excess}}$ depends on both errors $\epsilon_{\text{gen}}$ and
$\epsilon_{\text{opt}}$. In the following section, we briefly discuss known
results on the $\epsilon_{\text{opt}}$ of zeroth-order methods, including
convex and nonconvex losses.

###  3.2 Optimization Error in Zeroth-Order Stochastic Approximation

Convergence rates of the ZoSS optimization error and related zeroth-order
variants have been extensively studied in prior works; see e.g., [14, 15, 68].
For the convex loss setting, when $K+1$ function evaluations are available and
no other information regarding the loss is given, the ZoSS algorithm achieves
optimal rates with respect to the optimization error $\epsilon_{\text{opt}}$.
Specifically, under the assumption of a closed and convex loss, Duchi et al.
[13] provided a lower bound for the minimax convergence rate and showed that
$\epsilon_{\text{opt}}=\Omega(\sqrt{d/K})$, for any algorithm that
approximates the gradient given $K+1$ evaluations. In the nonconvex setting
Ghadimi et al. [69, 70] established sample complexity guarantees for the
zeroth-order approach to reach an approximate stationary point.

##  4 Main Results

For our analysis, we introduce the same assumptions on the loss function
(Lipschitz and smooth) as appears in prior work [1]. Additionally, we exploit
the $\eta$-expansive and $\sigma$-bounded properties of the SGD mappings
$G_{t}(\cdot)$ and $G^{\prime}_{t}(\cdot)$ in Eq. (3).111[1, Definition 2.3]:
An update rule $G(\cdot)$ is $\eta$-expansive if
$\|G(w)-G(w^{\prime})\|\leq\eta\|w-w^{\prime}\|$ for all
$w,w^{\prime}\in\mathbb{R}^{d}$. If $\|w-G(w)\|\leq\sigma$ then it is
$\sigma$-bounded. The mappings $G_{t}(\cdot)$ and $G^{\prime}_{t}(\cdot)$ are
introduced for analysis purposes due to the stability error decomposition
given in Eq. (5) and no further assumptions or properties are required for the
zeroth-order update rules $\tilde{G}_{t}(\cdot)$ and
$\tilde{G}^{\prime}_{t}(\cdot)$ given in Eq. (4). Recall that the
$\eta$-expansivity of $G_{t}(\cdot)$ holds for $\eta=1+\beta\alpha_{t}$ if the
loss is nonconvex, and $\eta=1$ if the loss is convex and $\alpha_{t}\leq
2/\beta$ [1, Lemma 3.6]. Note that $G_{t}(\cdot)$ is always $\sigma$-bounded
for $\sigma=L\alpha_{t}$ [1, Lemma 3.3.].

###  4.1 Stability Analysis

We start by providing a lemma that is useful in the proofs of our main
results.

###### Lemma 1

Let $\mathbf{U}_{k}\in\mathbb{R}^{d},k\in\\{1,2\ldots,K\\}$ be i.i.d standard
Gaussian.222Similar bounds (i.e., $\mathcal{O}(\sqrt{d/K})$) hold for other
distributions as well, e.g., when the $\mathbf{U}_{k}$’s are uniformly
distributed (and independent) in $[-1,+1]$. For every random vector
$\mathbf{V}\in\mathbb{R}^{d}$ independent of all
$\mathbf{U}_{k},k\in\\{1,2\ldots,K\\}$, it is true that

$\displaystyle\mathbb{E}\left[\Bigg{\|}\frac{1}{K}\sum^{K}_{k=1}\langle\mathbf{V},\mathbf{U}_{k}\rangle\mathbf{U}_{k}-\mathbf{V}\Bigg{\|}\Bigg{|}\mathbf{V}\right]\leq\sqrt{\frac{3d-1}{K}}\|\mathbf{V}\|.$
(8)

Different versions of Lemma 1 appear already in prior works (see, e.g., [13,
Proof of Corollary 2]. For completeness and clarity we provide a short proof
of Lemma 1 in the Appendix, Section A.1. Exploiting Lemma 1, we show a growth
recursion lemma for the iterates of the ZoSS.

######  Lemma 2 (ZoSS Growth Recursion)

Consider the sequences of updates $\\{\tilde{G}_{t}\\}^{T}_{t=1}$ and
$\\{\tilde{G}^{\prime}_{{}_{t}}\\}^{T}_{t=1}$. Let $w_{0}=w^{\prime}_{0}$ be
the starting point, $w_{t+1}=\tilde{G}_{t}(w_{t})$ and
$w^{\prime}_{t+1}=\tilde{G}^{\prime}_{t}(w^{\prime}_{t})$ for any
$t\in\\{1,\ldots,T\\}$. Then for any $w_{t},w^{\prime}_{t}\in\mathbb{R}^{d}$
and $t\geq 0$ the following recursion holds

$\displaystyle\mathbb{E}[\|\tilde{G}_{t}(w_{t})-\tilde{G}^{\prime}_{t}(w^{\prime}_{t})\|]\leq\begin{cases}\Big{(}\eta+\alpha_{t}\sqrt{\frac{3d-1}{K}}\beta\Big{)}\|w_{t}-w^{\prime}_{t}\|+\mu\beta\alpha_{t}(3+d)^{3/2},&\text{
if }\tilde{G}_{t}(\cdot)=\tilde{G}^{\prime}_{t}(\cdot),\\\
\|w_{t}-w^{\prime}_{t}\|+2\alpha_{t}L\Gamma^{d}_{K}+\mu\beta\alpha_{t}(3+d)^{3/2},&\text{
if }\tilde{G}_{t}(\cdot)\neq\tilde{G}^{\prime}_{t}(\cdot).\end{cases}$

The growth recursion of ZoSS characterizes the stability error that it is
introduced by the ZoSS update and according to the outcome of the randomized
selection rule at each iteration. Lemma 2 extends growth recursion results for
SGD in prior work [1, Lemma 2.5] to the setting of the ZoSS algorithm. If
$K\rightarrow\infty$ and $\mu\rightarrow 0$ (while the rest of the parameters
are fixed), then $\Gamma^{d}_{K}\rightarrow 1$, and the statement recovers
that of the SGD [1, Lemma 2.5].

#### Proof of Lemma 2.

Let $S$ and $S^{\prime}$ be two samples of size $n$ differing in only a single
example, and let $\tilde{G}_{t}(\cdot),\tilde{G}^{\prime}_{t}(\cdot)$ be the
update rules of the ZoSS for each of the sequences $S,S^{\prime}$
respectively. First under the event
$\mathcal{E}_{t}\triangleq\\{\tilde{G}_{t}(\cdot)\equiv\tilde{G}^{\prime}_{t}(\cdot)\\}$
(see Eq. (4)), by applying the Taylor expansion there exist vectors
$W^{*}_{k,t}$ and $W^{\dagger}_{k,t}$ with $j^{\text{th}}$ coordinates in the
intervals $\big{(}w^{(j)}_{t},w^{(j)}_{t}+\mu
U^{(j)}_{k,t}\big{)}\cup\big{(}w^{(j)}_{t}+\mu
U^{(j)}_{k,t},w^{(j)}_{t}\big{)}$ and
$\big{(}w^{\prime(j)}_{t},w^{\prime(j)}_{t}+\mu
U^{(j)}_{k,t}\big{)}\cup\big{(}w^{\prime(j)}_{t}+\mu
U^{(j)}_{k,t},w^{\prime(j)}_{t}\big{)}$, respectively, such that for any
$w_{t},w^{\prime}_{t}\in\mathbb{R}^{d}$ we have

$\displaystyle\\!\\!\\!\\!\tilde{G}_{t}(w_{t})-\tilde{G}^{\prime}_{t}(w^{\prime}_{t})=\tilde{G}_{t}(w_{t})-\tilde{G}_{t}(w^{\prime}_{t})$
$\displaystyle\\!\\!\\!\\!=w_{t}-w^{\prime}_{t}-\frac{\alpha_{t}}{K}\sum^{K}_{k=1}\langle\nabla
f(w_{t},z_{i_{t}})-\nabla f(w^{\prime}_{t},z_{i_{t}}),U^{t}_{k}\rangle
U^{t}_{k}$ (9)
$\displaystyle\\!\\!\\!\\!\quad-\frac{\alpha_{t}}{K}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{i_{t}})|_{w=W^{*}_{k,t}}U^{t}_{k}\right)U^{t}_{k}+\frac{\alpha_{t}}{K}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{i_{t}})|_{w=W^{\dagger}_{k,t}}U^{t}_{k}\right)U^{t}_{k}$
$\displaystyle\\!\\!\\!\\!=\underbrace{w_{t}-\alpha_{t}\nabla
f(w_{t},z_{i_{t}})}_{G(w_{t})}-\underbrace{\left(w^{\prime}_{t}-\alpha_{t}\nabla
f(w^{\prime}_{t},z_{i_{t}})\right)}_{G^{\prime}(w^{\prime}_{t})\equiv
G(w^{\prime}_{t})}$
$\displaystyle\\!\\!\\!\\!\quad-\frac{\alpha_{t}}{K}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{i_{t}})|_{w=W^{*}_{k,t}}U^{t}_{k}\right)U^{t}_{k}+\frac{\alpha_{t}}{K}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{i_{t}})|_{w=W^{\dagger}_{k,t}}U^{t}_{k}\right)U^{t}_{k}$
$\displaystyle\quad-\alpha_{t}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla
f(w_{t},z_{i_{t}})-\nabla f(w^{\prime}_{t},z_{i_{t}}),U^{t}_{k}\rangle
U^{t}_{k}-(\nabla f(w_{t},z_{i_{t}})-\nabla
f(w^{\prime}_{t},z_{i_{t}}))\bigg{)}.$ (10)

We find (10) by adding and subtracting $\alpha_{t}\nabla f(w_{t},z_{i_{t}})$
and $\alpha_{t}\nabla f(w^{\prime}_{t},z_{i_{t}})$ in Eq. (9). Recall that
$U^{t}_{k}$ are independent for all $k\leq K$, $t\leq T$ and that the mappings
$G(\cdot)$ and $G^{\prime}(\cdot)$ defined in Eq. (10), are $\eta$-expansive.
The last display and the triangle inequality give

$\displaystyle\\!\\!\\!\\!\mathbb{E}[\|\tilde{G}_{t}(w_{t})-\tilde{G}_{t}(w^{\prime}_{t})\|]$
$\displaystyle\\!\\!\\!\\!\\!\\!\leq\|G(w_{t})-G(w^{\prime}_{t})\|\\!+\\!\frac{2\alpha_{t}}{K}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}\left[\|U^{t}_{k}\|^{3}\right]\\!+\\!\alpha_{t}\sqrt{\frac{3d-1}{K}}\mathbb{E}[\|\nabla
f(w_{t},z_{i_{t}})-\nabla f(w^{\prime}_{t},z_{i_{t}})\|]$ (11)
$\displaystyle\\!\\!\\!\\!\\!\leq\eta\|w_{t}-w^{\prime}_{t}\|+\frac{2\alpha_{t}}{K}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}\left[\|U^{t}_{k}\|^{3}\right]+\alpha_{t}\sqrt{\frac{3d-1}{K}}\beta\|w_{t}-w^{\prime}_{t}\|$
(12)
$\displaystyle\\!\\!\\!\\!\\!\leq\left(\eta+\alpha_{t}\sqrt{\frac{3d-1}{K}}\beta\right)\|w_{t}-w^{\prime}_{t}\|+\mu\beta\alpha_{t}(3+d)^{3/2},$
(13)

where (11) follows from (10) and Lemma 1, and for (12) we applied the
$\eta$-expansive property of $G(\cdot)$ (see [1, Lemma 2.4 and Lemma 3.6]) and
the $\beta$-smoothness of the loss function.333For all $z\in\mathcal{Z}$ and
$W\in\mathbb{R}^{d}$ it is true that
$\|\nabla^{2}_{w}f(w,z)|_{w=W}\|\leq\beta$. Finally (13) holds since the
random vectors $U^{t}_{k}\sim\mathcal{N}(0,I_{d})$ are identically distributed
for all $k\in\\{1,2,\ldots,K\\}$ and
$\mathbb{E}\|U^{t}_{k}\|^{3}\leq(3+d)^{3/2}$. Eq. (13) gives the first part of
the recursion.

Similar to (10), under the event
$\mathcal{E}^{c}_{t}\triangleq\\{\tilde{G}_{t}(\cdot)\neq\tilde{G}^{\prime}_{t}(\cdot)\\}$,
we find

$\displaystyle\tilde{G}_{t}(w_{t})-\tilde{G}^{\prime}_{t}(w^{\prime}_{t})$
$\displaystyle=\underbrace{w_{t}-\alpha_{t}\nabla
f(w_{t},z_{i_{t}})}_{G(w_{t})}-\underbrace{\left(w^{\prime}_{t}-\alpha_{t}\nabla
f(w^{\prime}_{t},z^{\prime}_{i_{t}})\right)}_{G^{\prime}(w^{\prime}_{t})}$
$\displaystyle\quad-\frac{\alpha_{t}}{K}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{i_{t}})|_{w=\tilde{W}^{*}_{k,t}}U^{t}_{k}\right)U^{t}_{k}+\frac{\alpha_{t}}{K}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z^{\prime}_{i_{t}})|_{w=\tilde{W}^{\dagger}_{k,t}}U^{t}_{k}\right)U^{t}_{k}$
$\displaystyle\quad-\alpha_{t}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla
f(w_{t},z_{i_{t}})-\nabla
f(w^{\prime}_{t},z^{\prime}_{i_{t}}),U^{t}_{k}\rangle U^{t}_{k}-(\nabla
f(w_{t},z_{i_{t}})-\nabla f(w^{\prime}_{t},z^{\prime}_{i_{t}}))\bigg{)}.$ (14)

By using the last display, triangle inequality, Lemma 1 and
$\beta$-smoothness, we find

$\displaystyle\mathbb{E}[\|\tilde{G}_{t}(w_{t})-\tilde{G}_{t}(w^{\prime}_{t})\|]$
$\displaystyle\leq\|G(w_{t})-G^{\prime}(w^{\prime}_{t})\|+\frac{2\alpha_{t}}{K}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}[\|U^{t}_{k}\|^{3}]+\alpha_{t}\sqrt{\frac{3d-1}{K}}\mathbb{E}[\|\nabla
f(w_{t},z_{i_{t}})\\!-\\!\nabla f(w^{\prime}_{t},z^{\prime}_{i_{t}})\|]$
$\displaystyle\leq\min\\{\eta,1\\}\delta_{t}+2\sigma_{t}+\frac{2\alpha_{t}}{K}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}[\|U^{t}_{k}\|^{3}]+2L\alpha_{t}\sqrt{\frac{3d-1}{K}}$
(15)
$\displaystyle\leq\delta_{t}+2\alpha_{t}L\Gamma^{d}_{K}+\mu\beta\alpha_{t}(3+d)^{3/2},$
(16)

where (15) follows from the triangle inequality and $L-$Lipschitz condition,
while the upper bound on $\|G(w_{t})-G^{\prime}(w^{\prime}_{t})\|$ comes from
[1, Lemma 2.4]. Finally, (16) holds since $\eta\geq 1$ for both convex and
nonconvex losses, $\sigma_{t}=L\alpha_{t}$ and
$\mathbb{E}\|U^{t}_{k}\|^{3}\leq(3+d)^{3/2}$ for all $k\in\\{1,\ldots,K\\}$.
This shows the second part of recursion. $\Box$

###### Definition 3

Let $\mathcal{I}$ be an adapted stopping time that corresponds to the first
iteration index that the single distinct instance of the two data-sets
$S,S^{\prime}$ is sampled by ZoSS. For any $t_{0}\in\\{0,1,\ldots,n\\}$ we
define the event
$\mathcal{E}_{\delta_{t_{0}}}\triangleq\\{\mathcal{I}>t_{0}\\}\equiv\\{\delta_{t_{0}}=0\\}.$

Recall that $W_{T}$ and $W_{T^{\prime}}$ are the outputs of ZoSS (6) with
input data sequences $S$ and $S^{\prime}$, respectively. The next result
provides a stability bound on the expected value of the norm
$\|W_{T}-W^{\prime}_{T}\|$.

######  Lemma 4 (ZoSS Stability | Nonconvex Loss)

Assume that the loss function $f(\cdot,z)$ is $L$-Lipschitz and $\beta$-smooth
for all $z\in\mathcal{Z}$. Consider the ZoSS algorithm (6) with final-iterate
estimates $W_{T}$ and $W^{\prime}_{T}$, corresponding to the data-sets
$S,S^{\prime}$, respectively (that differ in exactly one entry). Then the
discrepancy $\delta_{T}\triangleq\|W_{T}-W^{\prime}_{T}\|$, under the event
$\mathcal{E}_{\delta_{t_{0}}}$, satisfies the inequality

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]\leq\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\beta\alpha_{j}\Gamma^{d}_{K}\left(1-\frac{1}{n}\right)\right).$
(17)

The corresponding bound of Lemma 4 for convex losses is slightly tighter than
the bound in (17). Since the two bounds differ only by a constant, the
consequent results of Lemma 4 are essentially identical for convex losses as
well. We provide the equivalent version of Lemma 4 for convex losses in
Appendix B.

#### Proof of Lemma 4.

Consider the events
$\mathcal{E}_{t}\triangleq\\{\tilde{G}_{t}(\cdot)\equiv\tilde{G}^{\prime}_{t}(\cdot)\\}$
and
$\mathcal{E}^{c}_{t}\triangleq\\{\tilde{G}_{t}(\cdot)\neq\tilde{G}^{\prime}_{t}(\cdot)\\}$
(see Eq. (4)). Recall that $\mathbb{P}(\mathcal{E}_{t})=1-1/n$ and
$\mathbb{P}(\mathcal{E}^{c}_{t})=1/n$ for all $t\leq T$. For any $t_{0}\geq
0$, a direct application of Lemma 2 gives

$\displaystyle\mathbb{E}[\delta_{t+1}|\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle=\mathbb{P}(\mathcal{E}_{t})\mathbb{E}[\delta_{t+1}|\mathcal{E}_{t},\mathcal{E}_{\delta_{t_{0}}}]+\mathbb{P}(\mathcal{E}^{c}_{t})\mathbb{E}[\delta_{t+1}|\mathcal{E}^{c}_{t},\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle=\left(1-\frac{1}{n}\right)\mathbb{E}[\delta_{t+1}|\mathcal{E}_{t},\mathcal{E}_{\delta_{t_{0}}}]+\frac{1}{n}\mathbb{E}[\delta_{t+1}|\mathcal{E}^{c}_{t},\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle\leq\left(\eta+\alpha_{t}\beta\sqrt{\frac{3d-1}{K}}+\frac{1}{n}\left(1-\eta-\alpha_{t}\beta\sqrt{\frac{3d-1}{K}}\right)\right)\mathbb{E}[\delta_{t}|\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle\quad+\frac{2\alpha_{t}L}{n}\Gamma^{d}_{K}+\mu\beta\alpha_{t}(3+d)^{3/2}.$
(18)

Define

$\displaystyle
R_{t}=R(\eta,\alpha_{t},\beta,n,d,K)\triangleq\left(\eta+\alpha_{t}\beta\sqrt{\frac{3d-1}{K}}+\frac{1}{n}\left(1-\eta-\alpha_{t}\beta\sqrt{\frac{3d-1}{K}}\right)\right),$
(19)

then by solving the recursion in (18) we find

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]\leq\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\alpha_{t}\prod^{T}_{j=t+1}R_{j}.$
(20)

We consider the last inequality for nonconvex loss functions with
$\eta=1+\beta\alpha_{t}$ and convex loss functions with $\eta=1$ to derive
Lemma 4 and Lemma 11 respectively (Appendix B). $\Box$

###  4.2 Generalization Error Bounds

For the first generalization error bound, we evaluate the right part of the
inequality (17) for decreasing step size and bounded nonconvex loss. Then the
Lipschitz condition provides a uniform stability condition for the loss and
yields the next theorem.

######  Theorem 5 (Nonconvex Bounded Loss | Decreasing Stepsize)

Assume that the loss $f(\cdot,z)\in[0,1]$ is $L$-Lipschitz and $\beta$-smooth
for all $z\in\mathcal{Z}$. Consider the ZoSS update rule (6) with $T$ the
total number of iterates, $\alpha_{t}\leq C/t\Gamma^{d}_{K}$ for some (fixed)
$C>0$ and for all $t\leq T$, and fixed $\mu\leq
cL\Gamma^{d}_{K}/n\beta(3+d)^{3/2}$ for some $c>0$. Then the generalization
error of ZoSS is bounded by

$\displaystyle\\!\\!\\!\epsilon_{\mathrm{gen}}$
$\displaystyle\leq\frac{\left((2+c)CL^{2}\right)^{\frac{1}{C\beta+1}}(eT)^{\frac{C\beta}{C\beta+1}}}{n}\max\\!\left\\{\\!1,1+(C\beta)^{-1}\\!-\\!\frac{e^{\beta
C}}{\beta
C^{{\frac{1}{C\beta+1}}}}\\!\left(\frac{(2+c)L^{2}}{eT}\right)^{\frac{C\beta}{C\beta+1}}\\!\right\\}$
(21)
$\displaystyle\leq\frac{\left(1+(C\beta)^{-1}\right)\left((2+c)CL^{2}\right)^{\frac{1}{C\beta+1}}}{n}(eT)^{\frac{C\beta}{C\beta+1}}.$
(22)

Inequality (21), as a tighter version of (22), provides a meaningful bound in
marginal cases, i.e.,

$\displaystyle\lim_{\beta\downarrow
0}\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]\leq\frac{(2+c)CL^{2}}{n}\max\left\\{\log\left(\frac{eT}{(2+c)CL^{2}}\right),1\right\\}.$
(23)

By neglecting the negative term in (21) we find (22), that is the ZoSS
equivalent of SGD [1, Theorem 3.8]. When $K\rightarrow\infty$ and
$c\rightarrow 0$, then $\Gamma^{d}_{K}\rightarrow 1$, and the inequalities
(21), (22) reduce to a generalization bound for SGD. Inequality (21) matches
that of [1, Theorem 3.8], and (21) provides a tighter generalization bound for
SGD as well.

Next, we provide a bound on the generalization error for nonconvex losses that
comes directly from Theorem 5. In contrast to Theorem 5, the next result
provides learning rate and a generalization error bounds, both of which are
independent of the dimension and the number of function evaluations.

###### Corollary 6

Assume that the loss function $f(\cdot,z)\in[0,1]$ is $L$-Lipschitz and
$\beta$-smooth for all $z\in\mathcal{Z}$. Consider the ZoSS update rule (6)
with $\mu\leq cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$, $T$ the total number of
iterates, and $\alpha_{t}\leq C/t$ for some (fixed) $C>0$ and for all $t\leq
T$. Then the generalization error of ZoSS is bounded by

$\displaystyle\epsilon_{\mathrm{gen}}\leq\left(1+(\beta
C)^{-1}\right)^{2}\left(1+(2+c)CL^{2}\right)\frac{3Te}{2n}.$ (24)

As a consequence, even in the high dimensional regime $d\rightarrow\infty$,
two function evaluations (i.e., $K=1$) are sufficient for the ZoSS to achieve
$\epsilon_{\mathrm{gen}}=\mathcal{O}(T/n)$, with the learning rate being no
smaller than that of SGD. We continue by providing the proof of Theorem 5. For
the proof of Corollary 6, see Appendix A.2.

#### Proof of Theorem 5.

We start by observing that $1-\eta-\alpha_{t}\beta\sqrt{\frac{3d-1}{K}}<0$
since $\eta\geq 1$. Eq. (19) and (20) give
$R(\eta,\alpha_{t},\beta,n,d,K)\leq(\eta+\alpha_{t}\beta\sqrt{(3d-1)/K})\triangleq\tilde{R}_{t}$,
and

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]\leq\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\alpha_{t}\prod^{T}_{j=t+1}\tilde{R}_{j}.$
(25)

Recall that $\eta=1+\beta\alpha_{t}$ for general (nonconvex) losses (see [1]).
Assuming that $\alpha_{t}\leq C/t\Gamma^{d}_{K}$ for all $t\leq T$, we have

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle\leq\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\alpha_{j}\beta\Gamma^{d}_{K}\right)$
$\displaystyle\leq\frac{C}{\Gamma^{d}_{K}}\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\frac{1}{t}\prod^{T}_{j=t+1}\left(1+\frac{C\beta}{j}\right)$
$\displaystyle\leq\frac{C}{\Gamma^{d}_{K}}\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\frac{1}{t}\prod^{T}_{j=t+1}\exp\left(\frac{C\beta}{j}\right)$
(26) $\displaystyle\leq\frac{C(eT)^{\beta
C}}{\Gamma^{d}_{K}}\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\frac{1}{t}\frac{1}{(t+1)^{\beta
C}}$ (27)
$\displaystyle\leq\underbrace{\beta^{-1}\left(\Gamma^{d}_{K}\right)^{-1}\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)}_{D}\\!\\!\left(\left(\frac{eT}{t_{0}}\right)^{\beta
C}\\!\\!\\!-e^{\beta C}\right).$ (28)

In the above, the inequality $1+x\leq e^{x}$ gives (26), inequality (27)
follows from the inequality $\sum^{T}_{j=t+1}1/j\leq\log T-\log(t+1)+1$, and
inequality (28) comes from the next inequality and integral evaluation
$\sum^{T}_{t=t_{0}+1}t^{-\beta C-1}\leq\int^{T}_{t=t_{0}}x^{-\beta
C-1}dx=(\beta C)^{-1}(t_{0}^{-\beta C}-T^{-\beta C})$. We define
$q\triangleq\beta C$ and find the value of $t_{0}$ that minimizes the right
part of [71, Lemma 3.11]444[71, Lemma 3.11] applies to the ZoSS update rule
(6) similar to SGD for nonnegative and $L$-Lipschitz losses. Note that
$\mathbb{P}(\mathcal{I}\leq t_{0})\leq t_{0}/n$, $t_{0}\in\\{0,\ldots,T\\}$,
and (29) comes from the Lipschitz assumption on the loss as
$\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]\leq\mathbb{P}(\mathcal{I}\leq
t_{0})\mathbb{E}\big{[}|f(W_{T},z)-f(W^{\prime}_{T},z)|\big{|}\mathcal{E}^{c}_{\delta_{t_{0}}}\big{]}+L\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]$.

$\displaystyle\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]\leq\frac{t_{0}}{n}\sup_{w,z}f(w,z)+L\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]\leq\frac{t_{0}}{n}+LD\left(\left(\frac{eT}{t_{0}}\right)^{q}\\!\\!\\!-e^{q}\right),$
(29)

which is $t^{*}_{0}=\min\\{\left(qnLD\right)^{1/(q+1)}(eT)^{q/(q+1)},T\\}$.
Then (29) gives

$\displaystyle\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]$
$\displaystyle\leq\max\left\\{\frac{\left(qnLD\right)^{\frac{1}{q+1}}(eT)^{\frac{q}{q+1}}}{n},\frac{1+1/q}{n}\left(qnLD\right)^{\frac{1}{q+1}}(eT)^{\frac{q}{q+1}}-LDe^{q}\right\\}.$
(30)

Choosing $\mu\leq cL\Gamma^{d}_{K}/n\beta(3+d)^{3/2}$ for some $c>0$ in (30)
proves our claim. $\Box$

In the unbounded loss case, we apply Lemma 4 by setting $t_{0}=0$ (recall that
$t_{0}$ is a free parameter, while the algorithm depends on the random
variable $\mathcal{I}$). The next result provides a generalization error bound
for the ZoSS algorithm with constant step size. In the first case of the
theorem, we also consider the convex loss as a representative result, as we
show the same bound holds for an appropriate choice of greater learning rate
than the learning rate of the nonconvex case. The convex case for the rest of
the results of this work can be similarly derived.

######  Theorem 7 (Unbounded Loss | Constant Step Size)

Assume that the loss $f(\cdot,z)$ is $L$-Lipschitz, $\beta$-smooth for all
$z\in\mathcal{Z}$. Consider the ZoSS update rule (6) with $\mu\leq
cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$ for some $c>0$. Let $T$ be the total
number of iterates and for any $t\leq T$,

  * •

if $f(\cdot,z)$ is convex for all $z\in\mathcal{Z}$ and
$\alpha_{t}\leq\min\\{\log\big{(}1+C\beta(1-1/\Gamma^{d}_{K})\big{)}/T\beta(\Gamma^{d}_{K}-1),2/\beta\\}$,
or if $f(\cdot,z)$ is nonconvex and
$\alpha_{t}\leq\log\big{(}1+C\beta\big{)}/T\beta\Gamma^{d}_{K}$, for some
$C>0$ then

$\displaystyle\epsilon_{\mathrm{gen}}\leq\dfrac{(2+c)CL^{2}}{n},$ (31)

  * •

if $f(\cdot,z)$ is nonconvex and $\alpha_{t}\leq C/T\Gamma^{d}_{K}$, for some
$C>0$ then

$\displaystyle\epsilon_{\mathrm{gen}}\leq\frac{L^{2}\left(2+c\right)(e^{C\beta}-1)}{n\beta}.$
(32)

For the proof of Theorem 7 see Appendix A.3. In the following, we present the
generalization error of ZoSS for an unbounded loss with a decreasing step
size. Recall that the results for unbounded nonconvex loss also hold for the
case of a convex loss with similar bounds on the generalization error and
learning rate (see the first case of Theorem 7).

######  Theorem 8 (Unbounded Loss | Decreasing Step Size)

Assume that the loss $f(\cdot,z)$ is $L$-Lipschitz, $\beta$-smooth for all
$z\in\mathcal{Z}$. Consider ZoSS with update rule (6), $T$ the total number of
iterates, $\alpha_{t}\leq C/t\Gamma^{d}_{K}$ for all $t\leq T$ and for some
$C>0$, and $\mu\leq cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$ for some $c>0$. Then
the generalization error of ZoSS is bounded by

$\displaystyle\\!\\!\\!\\!\epsilon_{\mathrm{gen}}\leq\frac{(2+c)L^{2}(eT)^{C\beta}}{n}\min\left\\{C+\beta^{-1},C\log(eT)\right\\}.$
(33)

For the proof of Theorem 8 see Appendix A.4. Note that the constant $C$ is
free and controls the learning rate. Furthermore, it quantifies the trade-off
between the speed of training and the generalization of the algorithm.

In the next section, we consider the ZoSS algorithm with a mini-batch of size
$m$ for which we provide generalization error bounds. These results hold under
the assumption of unbounded loss and for any batch size $m$ including the case
$m=1$.

##  5 Generalization of Mini-Batch ZoSS

For the mini-batch version of ZoSS, at each iteration $t$, the randomized
selection rule (uniformly) samples a batch $J_{t}$ of size $m$ and evaluates
the new direction of the update by averaging the smoothed approximation
${\Delta f}^{K,\mu}_{w,z}$ over the samples $z\in J_{t}$ as

$\displaystyle{\Delta f}^{K,\mu}_{w,J_{t}}$ $\displaystyle\equiv{\Delta
f}^{K,\mu,\mathbf{U}^{t}}_{w,J_{t}}\triangleq\frac{1}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{f(w+\mu
U^{t}_{k,i},z_{J_{t,i}})-f(w,z_{J_{t,i}})}{\mu}U^{t}_{k,i},$ (34)

where $U^{t}_{k,i}\sim\mathcal{N}(0,I_{d})$ are i.i.d. (standard normal), and
$\mu\in\mathbb{R}^{+}$. The update rule of the mini-batch ZoSS is
$W_{t+1}=W_{t}-\alpha_{t}{\Delta f}^{K,\mu}_{W_{T},J_{t}}$ for all $t\leq T$.
Due to space limitation, we refer the reader to Appendix C for the detailed
stability analysis of ZoSS with mini-batch. Specifically, we prove a growth
recursion lemma for the mini-batch ZoSS updates (Appendix C.1, Lemma 13).
Although the iterate stability error in the growth recursion depends on the
batch size $m$, the stability bound on the final iterates is independent of
$m$, and coincides with the single example updates ($m=1$, Lemma 4). Herein,
we provide an informal statement of the result.

######  Lemma 9 (Mini-Batch ZoSS Stability | Nonconvex Loss)

Consider the mini-batch ZoSS with any batch size $m\leq n$, and iterates
$W_{t+1}=W_{t}-\alpha_{t}{\Delta f}^{K,\mu}_{W_{T},J_{t}}$,
$W^{\prime}_{t+1}=W^{\prime}_{t}-\alpha_{t}{\Delta
f}^{K,\mu}_{W^{\prime}_{T},J^{\prime}_{t}}$, for all $t\leq T$, with respect
to the sequences $S,S^{\prime}$. Then the stability error $\delta_{T}$
satisfies the inequality of Lemma 4.

We refer the reader to Appendix Section C.1, Theorem 14 for the formal
statement of the result.555As in the single-query ($m=1$) ZoSS, under the
assumption of convex loss, the stability error of mini-batch ZoSS satisfies
the inequality (47), Appendix B, Lemma 11. Through the Lipschitz condition of
the loss and Lemma 9, we show that the mini-batch ZoSS enjoys the same
generalization error bounds as in the case of single-query ZoSS ($m=1$). As a
consequence, the batch size does not affect the generalization error.

######  Theorem 10 (Mini-batch ZoSS | Unbounded Loss)

Theorem 7 and Theorem 8 hold for the mini-batch ZoSS with iterate
$W_{t+1}=W_{t}-\alpha_{t}{\Delta f}^{K,\mu}_{W_{T},J_{t}}$, for all $t\leq T$
and any batch size $m\leq n$.

By letting $K\rightarrow\infty$ and $c\rightarrow 0$, the generalization error
bounds of mini-batch ZoSS reduce to those of mini-batch SGD, extending results
of the single-query ($m=1$) SGD that appeared in prior work [1]. Additionally,
once $K\rightarrow\infty$, $c\rightarrow 0$ and $m=n$ we obtain generalization
guarantees for full-batch GD. For the sake of clarity and completeness we
provide dedicated stability and generalization analysis of full-batch GD in
Appendix D, Corollary 15.

##  6 Conclusion

In this paper, we characterized the generalization ability of black-box
learning models. Specifically, we considered the Zeroth-order Stochastic
Search (ZoSS) algorithm, which evaluates smoothed approximations of the
unknown gradient of the loss by only relying on $K+1$ loss evaluations. Under
the assumptions of a Lipschitz and smooth (unknown) loss, we showed that the
ZoSS algorithm achieves the same generalization error bounds as that of SGD,
while the learning rate is slightly decreased compared to that of SGD. The
efficient generalization ability of ZoSS, together with strong optimality
results related to the optimization error by Duchi et al. [13], makes it a
robust and powerful algorithm for a variety of black-box learning applications
and problems.

## References

  * [1] 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.
  * [2] Alekh Agarwal, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin.  Stochastic convex optimization with bandit feedback.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.  URL: https://proceedings.neurips.cc/paper/2011/file/67e103b0761e60683e83c559be18d40c-Paper.pdf.
  * [3] Ohad Shamir.  An optimal algorithm for bandit and zero-order convex optimization with two-point feedback.  The Journal of Machine Learning Research, 18(1):1703–1713, 2017\.  URL: https://www.jmlr.org/papers/volume18/16-632/16-632.pdf.
  * [4] Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov.  Exploiting higher order smoothness in derivative-free optimization and continuous bandits.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9017–9027. Curran Associates, Inc., 2020.  URL: https://proceedings.neurips.cc/paper/2020/file/6646b06b90bd13dabc11ddba01270d23-Paper.pdf.
  * [5] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh.  Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models.  In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15–26, 2017.  URL: https://dl.acm.org/doi/10.1145/3128572.3140448.
  * [6] Zan Li and Li Chen.  Communication-efficient decentralized zeroth-order method on heterogeneous data.  In 2021 13th International Conference on Wireless Communications and Signal Processing (WCSP), pages 1–6, 2021.  doi:10.1109/WCSP52459.2021.9613620.
  * [7] Anirudh Vemula, Wen Sun, and J. Bagnell.  Contrasting exploration in parameter and action space: A zeroth-order optimization perspective.  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 2926–2935. PMLR, 16–18 Apr 2019.  URL: https://proceedings.mlr.press/v89/vemula19a.html.
  * [8] Harshat Kumar, Dionysios S. Kalogerias, George J. Pappas, and Alejandro Ribeiro.  Actor-only deterministic policy gradient via zeroth-order gradient oracles in action space.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1676–1681, 2021.  doi:10.1109/ISIT45174.2021.9518023.
  * [9] Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter Bartlett, and Martin Wainwright.  Derivative-free methods for policy optimization: Guarantees for linear quadratic systems.  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 2916–2925. PMLR, 16–18 Apr 2019.  URL: https://proceedings.mlr.press/v89/malik19a.html.
  * [10] Hesameddin Mohammadi, Mahdi Soltanolkotabi, and Mihailo R. Jovanović.  On the linear convergence of random search for discrete-time LQR.  IEEE Control Systems Letters, 5(3):989–994, 2021.  doi:10.1109/LCSYS.2020.3006256.
  * [11] Jeremy Rapin and Olivier Teytaud.  Nevergrad - A gradient-free optimization platform.  https://GitHub.com/FacebookResearch/Nevergrad, 2018.
  * [12] Luis Miguel Rios and Nikolaos V Sahinidis.  Derivative-free optimization: a review of algorithms and comparison of software implementations.  Journal of Global Optimization, 56(3):1247–1293, 2013.  URL: https://link.springer.com/article/10.1007/s10898-012-9951-y.
  * [13] John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono.  Optimal rates for zero-order convex optimization: The power of two function evaluations.  IEEE Transactions on Information Theory, 61(5):2788–2806, 2015\.  doi:10.1109/TIT.2015.2409256.
  * [14] Yurii Nesterov and Vladimir Spokoiny.  Random gradient-free minimization of convex functions.  Foundations of Computational Mathematics, 17(2):527–566, 2017.  URL: https://link.springer.com/article/10.1007/s10208-015-9296-2.
  * [15] Krishnakumar Balasubramanian and Saeed Ghadimi.  Zeroth-order nonconvex stochastic optimization: Handling constraints, high dimensionality, and saddle points.  Foundations of Computational Mathematics, pages 1–42, 2021.  URL: https://link.springer.com/article/10.1007/s10208-021-09499-8.
  * [16] Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Dan Roy.  Towards a unified information-theoretic framework for generalization.  Advances in Neural Information Processing Systems, 34, 2021.
  * [17] 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.
  * [18] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Learnability, stability and uniform convergence.  The Journal of Machine Learning Research, 11:2635–2670, 2010.  URL: https://www.jmlr.org/papers/volume11/shalev-shwartz10a/shalev-shwartz10a.pdf.
  * [19] Luc P. Devroye and et al.  Distribution-free performance bounds for potential function rules, 1979\.  URL: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.8772.
  * [20] Michael Kearns and Dana Ron.  Algorithmic stability and sanity-check bounds for leave-one-out cross-validation.  Neural Computation, 11(6):1427–1453, 1999.  doi:10.1162/089976699300016304.
  * [21] Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin.  Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization.  Advances in Computational Mathematics, 25(1):161–193, 2006.  URL: https://link.springer.com/article/10.1007/s10444-004-7634-z.
  * [22] Olivier Bousquet and André Elisseeff.  Algorithmic stability and generalization performance.  In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2001.  URL: https://proceedings.neurips.cc/paper/2000/file/49ad23d1ec9fa4bd8d77d02681df5cfa-Paper.pdf.
  * [23] Zhun Deng, Hangfeng He, and Weijie Su.  Toward better generalization bounds with locally elastic stability.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2590–2600. PMLR, 18–24 Jul 2021.  URL: https://proceedings.mlr.press/v139/deng21b.html.
  * [24] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio.  Fantastic generalization measures and where to find them.  arXiv preprint arXiv:1912.02178, 2019.  URL: https://arxiv.org/abs/1912.02178.
  * [25] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman.  Algorithmic stability for adaptive data analysis.  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 1046–1059, New York, NY, USA, 2016. Association for Computing Machinery.  doi:10.1145/2897518.2897566.
  * [26] Jonathan Ullman, Adam Smith, Kobbi Nissim, Uri Stemmer, and Thomas Steinke.  The limits of post-selection generalization.  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/77ee3bc58ce560b86c2b59363281e914-Paper.pdf.
  * [27] Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld.  A New Analysis of Differential Privacy’s Generalization Guarantees (Invited Paper), page 9.  Association for Computing Machinery, New York, NY, USA, 2021.  URL: https://doi.org/10.1145/3406325.3465358.
  * [28] Thomas Steinke and Lydia Zakynthinou.  Reasoning About Generalization via Conditional Mutual Information.  In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3437–3452. PMLR, 09–12 Jul 2020.  URL: https://proceedings.mlr.press/v125/steinke20a.html.
  * [29] Ibrahim Alabdulmohsin.  An Information-Theoretic Route from Generalization in Expectation to Generalization in Probability.  In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 92–100. PMLR, 20–22 Apr 2017.  URL: https://proceedings.mlr.press/v54/alabdulmohsin17a.html.
  * [30] 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.
  * [31] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli.  Tightening mutual information based bounds on generalization error.  In 2019 IEEE International Symposium on Information Theory (ISIT), pages 587–591, 2019.  doi:10.1109/ISIT.2019.8849590.
  * [32] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy.  Information-theoretic generalization bounds for stochastic gradient descent.  In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3526–3545. PMLR, 15–19 Aug 2021.  URL: https://proceedings.mlr.press/v134/neu21a.html.
  * [33] Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan.  Information-theoretic generalization bounds for black-box learning algorithms.  Advances in Neural Information Processing Systems, 34, 2021.
  * [34] Fengxiang He, Shaopeng Fu, Bohan Wang, and Dacheng Tao.  Robustness, privacy, and generalization of adversarial training.  arXiv preprint arXiv:2012.13573, 2020.  URL: https://arxiv.org/abs/2012.13573.
  * [35] Fengxiang He, Bohan Wang, and Dacheng Tao.  Tighter generalization bounds for iterative differentially private learning algorithms.  In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 802–812. PMLR, 27–30 Jul 2021.  URL: https://proceedings.mlr.press/v161/he21a.html.
  * [36] Zhenhuan Yang, Yunwen Lei, Siwei Lyu, and Yiming Ying.  Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss.  In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2026–2034. PMLR, 13–15 Apr 2021.  URL: https://proceedings.mlr.press/v130/yang21c.html.
  * [37] Puyu Wang, Zhenhuan Yang, Yunwen Lei, Yiming Ying, and Hai Zhang.  Differentially private empirical risk minimization for auc maximization.  Neurocomputing, 461:419–437, 2021.
  * [38] 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.
  * [39] 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.
  * [40] 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.
  * [41] 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.
  * [42] 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.
  * [43] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik.  SGD: General analysis and improved rates.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5200–5209. PMLR, 09–15 Jun 2019.  URL: https://proceedings.mlr.press/v97/qian19b.html.
  * [44] 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.
  * [45] 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.
  * [46] 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.
  * [47] 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.
  * [48] Yunwen Lei, Mingrui Liu, and Yiming Ying.  Generalization guarantee of SGD for pairwise learning.  Advances in Neural Information Processing Systems, 34, 2021.
  * [49] Yunwen Lei, Antoine Ledent, and Marius Kloft.  Sharper generalization bounds for pairwise learning.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21236–21246. Curran Associates, Inc., 2020.  URL: https://proceedings.neurips.cc/paper/2020/file/f3173935ed8ac4bf073c1bcd63171f8a-Paper.pdf.
  * [50] Yi Zhou, Yingbin Liang, and Huishuai Zhang.  Understanding generalization error of SGD in nonconvex optimization.  Machine Learning, pages 1–31, 2021.  URL: https://link.springer.com/article/10.1007/s10994-021-06056-w.
  * [51] Ali Ramezani-Kebrya, Ashish Khisti, and Ben Liang.  On the generalization of stochastic gradient descent with momentum.  arXiv preprint arXiv:2102.13653, 2021.
  * [52] 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.
  * [53] Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan.  Towards understanding why lookahead generalizes better than SGD and beyond.  Advances in Neural Information Processing Systems, 34, 2021.
  * [54] Yue Xing, Qifan Song, and Guang Cheng.  On the algorithmic stability of adversarial training.  Advances in Neural Information Processing Systems, 34, 2021.
  * [55] 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.
  * [56] 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.
  * [57] 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.
  * [58] 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.
  * [59] 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.
  * [60] Tyler Farghly and Patrick Rebeschini.  Time-independent generalization bounds for SGLD in non-convex settings.  Advances in Neural Information Processing Systems, 34, 2021.
  * [61] Bohan Wang, Huishuai Zhang, Jieyu Zhang, Qi Meng, Wei Chen, and Tie-Yan Liu.  Optimizing information-theoretical generalization bound via anisotropic noise of SGLD.  Advances in Neural Information Processing Systems, 34, 2021.
  * [62] Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon.  Analyzing the generalization capability of SGLD using properties of gaussian channels.  Advances in Neural Information Processing Systems, 34, 2021.
  * [63] Elad Hoffer, Itay Hubara, and Daniel Soudry.  Train longer, generalize better: closing the generalization gap in large batch training of neural networks.  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/a5e0ff62be0b08456fc7f1e88812af3d-Paper.pdf.
  * [64] 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.
  * [65] Idan Amir, Yair Carmon, Tomer Koren, and Roi Livni.  Never go full batch (in stochastic convex optimization).  Advances in Neural Information Processing Systems, 34, 2021.
  * [66] 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.
  * [67] Dominic Richards and Ilja Kuzborskij.  Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel.  Advances in Neural Information Processing Systems, 34, 2021.
  * [68] Yurii Nesterov.  Random gradient-free minimization of convex functions. core discussion papers 2011001, université catholique de louvain.  Center for Operations Research and Econometrics (CORE), 2011.  URL: https://econpapers.repec.org/paper/corlouvco/2011001.htm.
  * [69] Saeed Ghadimi and Guanghui Lan.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  SIAM Journal on Optimization, 23(4):2341–2368, 2013.  URL: https://doi.org/10.1137/120880811.
  * [70] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang.  Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization.  Mathematical Programming, 155(1-2):267–305, 2016.  URL: https://link.springer.com/content/pdf/10.1007/s10107-014-0846-1.pdf.
  * [71] Moritz Hardt, Benjamin Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  arXiv preprint arXiv:1509.01240, 2015.  URL: https://arxiv.org/abs/1509.01240.
  * [72] Robert M Corless, Gaston H Gonnet, David EG Hare, David J Jeffrey, and Donald E Knuth.  On the lambertw function.  Advances in Computational mathematics, 5(1):329–359, 1996.  URL: https://link.springer.com/content/pdf/10.1007/BF02124750.pdf.

##  Appendix A Proofs

###  A.1 Proof of Lemma 1

For fixed ${\bf V}\in\mathbb{R}^{d}$, we have due to independence

$\displaystyle\mathbb{E}\Bigg{[}\Bigg{\|}\dfrac{1}{K}\sum_{k=1}^{K}\langle{\bf
V},{\bf U}_{k}\rangle{\bf U}_{k}-{\bf V}\Bigg{\|}^{2}\Bigg{]}$
$\displaystyle=\dfrac{1}{K^{2}}\mathbb{E}\Bigg{[}\Bigg{\|}\sum_{k=1}^{K}\langle{\bf
V},{\bf U}_{k}\rangle{\bf U}_{k}-{\bf V}\Bigg{\|}^{2}\Bigg{]}$
$\displaystyle=\dfrac{1}{K^{2}}\sum_{k=1}^{K}\mathbb{E}\big{[}\|\langle{\bf
V},{\bf U}_{k}\rangle{\bf U}_{k}-{\bf V}\|^{2}\big{]}$
$\displaystyle=\dfrac{1}{K}\mathbb{E}\big{[}\|\langle{\bf V},{\bf
U}_{1}\rangle{\bf U}_{1}-{\bf V}\|^{2}\big{]}.$

Now, again due to independence

$\displaystyle\mathbb{E}\big{[}\|\langle{\bf V},{\bf U}_{1}\rangle{\bf
U}_{1}-{\bf V}\|^{2}\big{]}$ $\displaystyle=\mathbb{E}\big{[}\|\langle{\bf
V},{\bf U}_{1}\rangle{\bf U}_{1}\|^{2}-2\langle\langle{\bf V},{\bf
U}_{1}\rangle{\bf U}_{1},{\bf V}\rangle+\|{\bf V}\|^{2}\big{]}$
$\displaystyle=\mathbb{E}\big{[}\big{(}\langle{\bf V},{\bf
U}_{1}\rangle\big{)}^{2}\|{\bf
U}_{1}\|^{2}\big{]}-2\mathbb{E}\big{[}\langle{\bf V},{\bf
U}_{1}\rangle\langle{\bf U}_{1},{\bf V}\rangle\big{]}+\|{\bf V}\|^{2}$
$\displaystyle={\bf V}^{T}\mathbb{E}\big{[}{\bf U}_{1}{\bf U}_{1}^{T}\|{\bf
U}_{1}\|^{2}\big{]}{\bf V}-2{\bf V}^{T}\mathbb{E}\big{[}{\bf U}_{1}{\bf
U}_{1}^{T}\big{]}{\bf V}+\|{\bf V}\|^{2}$ $\displaystyle=\sum_{i=1}^{d}{\bf
V}^{T}\mathbb{E}\big{[}{\bf U}_{1}{\bf
U}_{1}^{T}\big{(}U_{1}^{(i)}\big{)}^{2}\big{]}{\bf V}-2\|{\bf V}\|^{2}+\|{\bf
V}\|^{2}$ $\displaystyle\leq\sum_{i=1}^{d}3{\bf V}^{T}{\bf V}-\|{\bf V}\|^{2}$
$\displaystyle=(3d-1)\|{\bf V}\|^{2}.$

Therefore,

$\mathbb{E}\bigg{[}\bigg{\|}\dfrac{1}{K}\sum_{k=1}^{K}\langle{\bf V},{\bf
U}_{k}\rangle{\bf U}_{k}-{\bf V}\bigg{\|}^{2}\bigg{]}\leq\dfrac{(3d-1)\|{\bf
V}\|^{2}}{K}.$

Thus, if ${\bf V}$ is random and independent of all ${\bf U}_{k}$’s, it
follows that

$\displaystyle\mathbb{E}\Bigg{[}\Bigg{\|}\dfrac{1}{K}\sum_{k=1}^{K}\langle{\bf
V},{\bf U}_{k}\rangle{\bf U}_{k}-{\bf V}\Bigg{\|}\Bigg{|}\mathbf{V}\Bigg{]}$
$\displaystyle\leq\sqrt{\mathbb{E}\Bigg{[}\Bigg{\|}\dfrac{1}{K}\sum_{k=1}^{K}\langle{\bf
V},{\bf U}_{k}\rangle{\bf U}_{k}-{\bf
V}\Bigg{\|}^{2}\Bigg{|}\mathbf{V}\Bigg{]}}$
$\displaystyle\leq\sqrt{\frac{3d-1}{K}\|\mathbf{V}\|^{2}}$
$\displaystyle=\sqrt{\frac{3d-1}{K}}\|\mathbf{V}\|,$

and our claim is proved. $\Box$

###  A.2 Proof of Corollary 6

Denote by $W_{0}(\cdot)$ the Lambert function [72]. Through Theorem 5 and by
replacing $C$ with $C\Gamma^{d}_{K}$ to recover the required learning rate,
the generalization error is bounded as

$\displaystyle\epsilon_{\mathrm{gen}}$ $\displaystyle\leq\frac{1+(\beta
C\Gamma^{d}_{K})^{-1}}{n}((2+c)CL^{2})^{\frac{1}{1+\beta
C\Gamma^{d}_{K}}}(\Gamma^{d}_{K})^{\frac{1}{1+\beta
C\Gamma^{d}_{K}}}(eT)^{\frac{\beta C\Gamma^{d}_{K}}{\beta C\Gamma^{d}_{K}+1}}$
$\displaystyle\leq\frac{1+(\beta
C\Gamma^{d}_{K})^{-1}}{n}((2+c)CL^{2})^{\frac{1}{1+\beta
C\Gamma^{d}_{K}}}\left(\frac{1}{\beta CW_{0}\left(\frac{1}{\beta
Ce}\right)}\right)^{\frac{1}{1+1/W_{0}\left(\frac{1}{\beta
Ce}\right)}}(eT)^{\frac{\beta C\Gamma^{d}_{K}}{\beta C\Gamma^{d}_{K}+1}}$ (35)
$\displaystyle\leq\frac{1+(\beta
C\Gamma^{d}_{K})^{-1}}{n}((2+c)CL^{2})^{\frac{1}{1+\beta
C\Gamma^{d}_{K}}}\left(\frac{1}{W_{0}\left(1/e\right)}\right)^{\frac{1}{1+1/W_{0}\left(\frac{1}{e}\right)}}\max\\{1,(\beta
C)^{-1}\\}(eT)^{\frac{\beta C\Gamma^{d}_{K}}{\beta C\Gamma^{d}_{K}+1}}$
$\displaystyle\leq\frac{3}{2}\frac{1+(\beta
C\Gamma^{d}_{K})^{-1}}{n}((2+c)CL^{2})^{\frac{1}{1+\beta
C\Gamma^{d}_{K}}}\max\\{1,(\beta C)^{-1}\\}(eT)^{\frac{\beta
C\Gamma^{d}_{K}}{\beta C\Gamma^{d}_{K}+1}}$ (36)
$\displaystyle\leq\frac{3}{2}\frac{1+(\beta
C)^{-1}}{n}((2+c)CL^{2})^{\frac{1}{1+\beta C\Gamma^{d}_{K}}}\max\\{1,(\beta
C)^{-1}\\}(eT)^{\frac{\beta C\Gamma^{d}_{K}}{\beta C\Gamma^{d}_{K}+1}}$ (37)
$\displaystyle\leq\frac{3}{2}\frac{1+(\beta
C)^{-1}}{n}\max\\{1,(2+c)CL^{2}\\}\max\\{1,(\beta C)^{-1}\\}(eT)^{\frac{\beta
C\Gamma^{d}_{K}}{\beta C\Gamma^{d}_{K}+1}}$ (38)
$\displaystyle\leq\frac{3}{2}\frac{\left(1+(\beta
C)^{-1}\right)^{2}}{n}\left(1+(2+c)CL^{2}\right)(eT)^{\frac{\beta
C\Gamma^{d}_{K}}{\beta C\Gamma^{d}_{K}+1}}$ $\displaystyle\leq\left(1+(\beta
C)^{-1}\right)^{2}\left(1+(2+c)CL^{2}\right)\frac{3Te}{2n},$ (39)

the maximization of $x^{1/(1+x\beta C)}$ gives (35), we find (36) by
maximizing the term $\left(\beta C\right)^{-1/(1+1/W_{0}\left(1/xe\right))}$,
and $W_{0}\left(1/xe\right)^{-1/(1+1/W_{0}\left(1/xe\right))}$, and by
applying the inequality
$W_{0}\left(1/e\right)^{-1/(1+1/W_{0}\left(1/xe\right))}\leq 3/2$. Inequality
(37) holds since $\Gamma^{d}_{K}\geq 1$, we find (38) by maximizing the
function $((2+c)CL^{2})^{1/(1+\beta Cx)}$ for both cases $((2+c)CL^{2})<1$ and
$((2+c)CL^{2})\geq 1$. Finally, (39) holds for any value of $d\in\mathbb{N}$
and $K\in\mathbb{N}$ and gives the bound of the corollary. $\Box$

###  A.3 Proof of Theorem 7

We start by proving the first case of the Theorem for both convex and
nonconvex loss.

#### Proof of Theorem 7, First Case:

Let $\mathcal{C}$ denote the set of convex loss functions. Under the
assumption $\alpha_{t}\leq C^{\prime}/T$, and $\mu\leq
cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$ Lemma 4 (nonconvex loss) and Lemma 11
(convex loss) give

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]$
$\displaystyle\leq\frac{\left(2+c\right)L\Gamma^{d}_{K}}{n}\sum^{T}_{t=1}\frac{C^{\prime}}{T}\prod^{T}_{j=t+1}\left(1+\frac{\beta
C^{\prime}}{T}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)$
$\displaystyle=\frac{\left(2+c\right)LC^{\prime}\Gamma^{d}_{K}}{Tn}\sum^{T}_{t=1}\left(1+\frac{\beta
C^{\prime}}{T}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)^{T-t}$
$\displaystyle=\frac{\left(2+c\right)LC^{\prime}\Gamma^{d}_{K}}{Tn}\left(1+\frac{\beta
C^{\prime}}{T}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)^{T}\sum^{T}_{t=1}\left(1+\frac{\beta
C^{\prime}}{T}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)^{-t}$
$\displaystyle=\frac{\left(2+c\right)LC^{\prime}\Gamma^{d}_{K}}{Tn}\frac{\left(1+\frac{\beta
C^{\prime}}{T}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)^{T}-1}{\left(1+\beta\frac{C^{\prime}}{T}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)-1}$
$\displaystyle=\frac{\left(2+c\right)L\Gamma^{d}_{K}}{n}\frac{\left(1+\frac{\beta
C^{\prime}}{T}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)^{T}-1}{\beta\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)}$
$\displaystyle\leq\frac{\left(2+c\right)L\Gamma^{d}_{K}}{n}\frac{\exp\left(\beta
C^{\prime}\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)\right)-1}{\beta\left(\mathds{1}_{f(\cdot)\notin\mathcal{C}}+\sqrt{\frac{3d-1}{K}}\right)}.$

If the loss is convex ($f(\cdot)\in\mathcal{C}$) and $\alpha_{t}\leq
C^{\prime}/T\leq 2/\beta$, the last display under the choice

$\displaystyle
C^{\prime}=\frac{\log(1+C\beta\sqrt{\frac{3d-1}{K}}/\Gamma^{d}_{K})}{\beta\sqrt{\frac{3d-1}{K}}}$
(40)

gives

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]$
$\displaystyle\leq\frac{\left(2+c\right)L\Gamma^{d}_{K}}{n}\frac{\exp\left(\beta
C^{\prime}\sqrt{\frac{3d-1}{K}}\right)-1}{\beta\sqrt{\frac{3d-1}{K}}}\leq\frac{\left(2+c\right)CL}{n}.$
(41)

If the loss is nonconvex ($f(\cdot)\notin\mathcal{C}$) and $\alpha_{t}\leq
C^{\prime\prime}/T$, then by choosing

$\displaystyle C^{\prime\prime}=\frac{\log(1+C\beta)}{\beta\Gamma^{d}_{K}},$
(42)

we find

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]$
$\displaystyle\leq\frac{\left(2+c\right)L\Gamma^{d}_{K}}{n}\frac{\exp\left(\beta
C^{\prime\prime}\Gamma^{d}_{K}\right)-1}{\beta\Gamma^{d}_{K}}\leq\frac{\left(2+c\right)CL}{n}.$
(43)

The Lipschitz assumption
$\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]\leq
L\mathbb{E}[\delta_{T}]=L\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]]$ (as
a consequence of $\mathbb{P}(\mathcal{I}\leq 0)=\mathbb{P}(\delta_{0}>0)=0$)
completes the proof for the first case of the theorem.

#### Proof of Theorem 7, Second Case:

Lemma 4 (nonconvex loss) under the choice $t_{0}=0$ gives

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]\leq\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\beta\alpha_{j}\left(1+\sqrt{\frac{3d-1}{K}}\right)\right).$
(44)

Under the assumption $\alpha_{t}\leq C/(T\Gamma^{d}_{K})$, and $\mu\leq
cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$ we find

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]$
$\displaystyle\leq\left(2+c\right)L\frac{\Gamma^{d}_{K}}{n}\sum^{T}_{t=1}\frac{C}{T\Gamma^{d}_{K}}\prod^{T}_{j=t+1}\left(1+\frac{C\beta}{T}\right)$
$\displaystyle=\left(2+c\right)L\frac{\Gamma^{d}_{K}}{n}\frac{C}{T\Gamma^{d}_{K}}\sum^{T}_{t=1}\left(1+\frac{C\beta}{T}\right)^{T-t}$
$\displaystyle=\left(2+c\right)L\frac{\Gamma^{d}_{K}}{n}\frac{C\left(1+\frac{C\beta}{T}\right)^{T}}{T\Gamma^{d}_{K}}\sum^{T}_{t=1}\left(1+\frac{C\beta}{T}\right)^{-t}$
$\displaystyle=\frac{\left(2+c\right)L}{n}\frac{C}{T}\frac{\left(1+\frac{C\beta}{T}\right)^{T}-1}{\left(1+\frac{C\beta}{T}\right)-1}$
$\displaystyle=\frac{\left(2+c\right)L}{n}\frac{\left(1+\frac{C\beta}{T}\right)^{T}-1}{\beta}.$
(45)

The Lipschitz assumption
$\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]\leq
L\mathbb{E}[\delta_{T}]=L\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]]$ (as
a consequence of $\mathbb{P}(\mathcal{I}\leq 0)=\mathbb{P}(\delta_{0}>0)=0$)
completes the proof. $\Box$

###  A.4 Proof of Theorem 8

Under the assumptions $\mu\leq cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$ and
$\alpha_{t}\leq C/t\Gamma^{d}_{K}$, Lemma 4 gives

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]$
$\displaystyle\leq\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\beta\alpha_{j}\left(1+\sqrt{\frac{3d-1}{K}}\right)\right)$
$\displaystyle\leq\frac{\Gamma^{d}_{K}}{n}(2+c)L\sum^{T}_{t=1}\frac{C}{t\Gamma^{d}_{K}}\prod^{T}_{j=t+1}\left(1+\frac{C\beta}{j}\right)$
$\displaystyle\leq\frac{(2+c)L}{n}\sum^{T}_{t=1}\frac{C}{t}\exp\left(\sum^{T}_{j=t+1}\frac{C\beta}{j}\right)$
$\displaystyle\leq\frac{(2+c)L}{n}\sum^{T}_{t=1}\frac{C}{t}\exp\left(C\beta\log\left(\frac{eT}{t+1}\right)\right)$
$\displaystyle=\frac{C(2+c)L}{n}\sum^{T}_{t=1}\frac{1}{t}\left(\frac{eT}{t+1}\right)^{C\beta}$
$\displaystyle\leq\frac{C(eT)^{C\beta}(2+c)L}{n}\sum^{T}_{t=1}\frac{1}{t^{C\beta+1}}$
$\displaystyle\leq\frac{(eT)^{C\beta}(2+c)L}{n}\min\left\\{\frac{C\beta+1}{\beta},C\log(eT)\right\\}.$
(46)

The last inequality holds because of the inequalities
$\sum^{T}_{t=1}t^{-C\beta-1}\leq\sum^{\infty}_{t=1}t^{-C\beta-1}\leq(C\beta+1)/C\beta$
and $\sum^{T}_{t=1}t^{-C\beta-1}\leq\sum^{T}_{t=1}1/t\leq\log(eT)$. Then the
inequality $\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]\leq
L\mathbb{E}[\delta_{T}]=L\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]]$ (as
a consequence of $\mathbb{P}(\mathcal{I}\leq 0)=\mathbb{P}(\delta_{0}>0)=0$)
completes the proof. $\Box$

##  Appendix B Complementary Results

In this Section we provide complementary results and the corresponding proofs.
The next result provides the equivalent bound of Lemma 4 for convex losses.

######  Lemma 11 (ZoSS Stability Convex Loss)

Assume that the loss function $f(\cdot,z)$ is $L$-Lipschitz, convex and
$\beta$-smooth for all $z\in\mathcal{Z}$. Consider the ZO-SM algorithm (6)
with parameters estimates $W_{T}$ and $W^{\prime}_{T}$ for all the data-sets
$S,S^{\prime}$ respectively (that differ in exactly one entry). Then the
discrepancy $\delta_{T}\triangleq\|W_{T}-W^{\prime}_{T}\|$ under the event
$\mathcal{E}_{\delta_{t_{0}}}$ satisfies the following inequality,

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]\leq\left(\frac{2L}{n}\Gamma^{d}_{K}+\mu\beta(3+d)^{3/2}\right)\sum^{T}_{t=t_{0}+1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\beta\alpha_{j}\sqrt{\frac{3d-1}{K}}\right).$
(47)

We prove Lemma 11 in parallel with Lemma 4 in Section 4.1 of the main part of
the paper.

##  Appendix C ZoSS with Mini-Batch (Section 5)

For the stability analysis of mini-batch ZoSS, we similarly consider the
sequences $S,S^{\prime}$ that differ in one example. At each time $t$ we
sample a batch $J_{t}\subset S$ ($J^{\prime}_{t}\subset S^{\prime}$) (and
batch size $m\triangleq|J_{t}|=|J^{\prime}_{t}|$) with replacement, or by
considering random permutation of the samples and then sample the first $m$
examples. As a consequence in both cases $\mathbb{P}(J_{t}\neq
J^{\prime}_{t})=m/n$. Under the event $\\{J_{t}\neq J^{\prime}_{t}\\}$, the
sets $J_{t},J^{\prime}_{t}$ differ in one example $z_{i^{*}}\neq
z^{\prime}_{i^{*}}$ (for some $i^{*}$ without loss of generality), and
$z_{i}=z^{\prime}_{i}$ for any $z_{i}\in J_{t}$ and
$i\in\\{1,\ldots,m\\}\setminus\\{i^{*}\\}$. Let
$U^{t}_{k,i}\sim\mathcal{N}(0,I_{d})$ be independent for all
$k\in\\{1,2,\ldots,K\\}$, $i\in\\{1,2,\ldots,m\\}$ and $t\leq T$ and
$\mu\in\mathbb{R}^{+}$. Recall the definition of the smoothed approximation
and update rule mapping of mini-batch ZoSS,

$\displaystyle{\Delta f}^{K,\mu}_{w,J_{t}}$ $\displaystyle\equiv{\Delta
f}^{K,\mu,\mathbf{U}^{t}}_{w,J_{t}}\triangleq\frac{1}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{f(w+\mu
U^{t}_{k,i},z_{J_{t,i}})-f(w,z_{J_{t,i}})}{\mu}U^{t}_{k,i},$ (48)
$\displaystyle\tilde{G}_{\\!J_{t}}(w)$ $\displaystyle\triangleq
w-\alpha_{t}{\Delta
f}^{K,\mu}_{w,J_{t}},\quad\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(w)\triangleq
w-\alpha_{t}{\Delta f}^{K,\mu}_{w,J^{\prime}_{t}}.$ (49)

For the stability error decomposition, we define the gradient based mappings
$G_{\\!J_{t}}(\cdot)$ and $G^{\prime}_{\\!J^{\prime}_{t}}(\cdot)$ as

$\displaystyle G_{\\!J_{t}}(w)\triangleq w-\alpha_{t}\nabla
f_{w,J_{t}},\,\,\,G^{\prime}_{\\!J^{\prime}_{t}}(w)\triangleq
w-\alpha_{t}\nabla f_{w,J^{\prime}_{t}},\text{ and }\nabla
f_{w,J_{t}}\triangleq\frac{1}{m}\sum_{z\in J_{t}}\nabla f(w,z)$ (50)

the iterate stability error of the mini-batch ZoSS
$\tilde{G}_{\\!J_{t}}(w)-\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime})$
at time $t$ and similarly to (5), we show that

$\displaystyle\tilde{G}_{\\!J_{t}}(w)-\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime})\propto\underbrace{G_{\\!J_{t}}(w)-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime})}_{\epsilon^{m}_{\text{GBstab}}}+\underbrace{\big{[}\nabla
f_{w,J_{t}}-{\Delta f}^{K,\mu}_{w,J_{t}}\big{]}+\big{[}\nabla
f_{w^{\prime},J^{\prime}_{t}}-{\Delta
f}^{K,\mu}_{w^{\prime},J^{\prime}_{t}}\big{]}}_{\epsilon^{m}_{\text{est}}}.$
(51)

For the mini-batch case the derivation of the stability differs to that of (5)
($m=1$).To analyze the error term $\epsilon^{m}_{\text{GBstab}}$ in the mini
batch case, we derive (for the proof see Appendix, Section C.2) and apply the
Mini-Batch SGD Growth Recursion for the mappings
$G_{J_{t}}(\cdot),G^{\prime}_{J^{\prime}_{t}}(\cdot)$, that is an extension of
[1, Lemma 2.4] and describes the growth recursion property of the SGD
algorithm with mini batch.

######  Lemma 12 (Mini-Batch SGD Growth Recursion)

Fix arbitrary sequences of updates $\\{G_{\\!J_{t}}\\}^{T}_{t=1}$ and
$\\{G^{\prime}_{\\!J^{\prime}_{t}}\\}^{T}_{t=1}$. Let $w_{0}=w^{\prime}_{0}$
be the starting point, $w_{t+1}=G_{\\!J_{t}}(w_{t})$ and
$w^{\prime}_{t+1}=G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})$ for any
$t\in\\{1,\ldots,T\\}$. Then for any $t\geq 0$ the following recursion holds

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|\leq\begin{cases}(1+\beta\alpha_{t})\|w_{t}-w^{\prime}_{t}\|&\text{
if }G_{\\!J_{t}}(\cdot)=G^{\prime}_{\\!J^{\prime}_{t}}(\cdot)\\\
\left(1+\frac{m-1}{m}\beta\alpha_{t}\right)\|w_{t}-w^{\prime}_{t}\|+\frac{2}{m}L\alpha_{t}&\text{
if }G_{\\!J_{t}}(\cdot)\neq G^{\prime}_{\\!J^{\prime}_{t}}(\cdot).\end{cases}$
(52)

The error $\epsilon^{m}_{\text{GBstab}}$ depends on the batch size $m$ at the
event of different batch selection $\\{J_{t}\neq J^{\prime}_{t}\\}$ as appears
in Lemma 12. Additionally, the error $\epsilon^{m}_{\text{est}}$ breaks down
into the errors $\epsilon_{\mu},\epsilon^{m}_{d/K}$. Although $\epsilon_{\mu}$
is independent of $m$, $\epsilon_{\mu}\leq\mu\beta\mathbb{E}[\|U\|^{3}]$
($U\in\mathbb{R}^{d}$ is standard normal), $\epsilon^{m}_{\text{est}}$
dependents on the batch size $m$ similarly to gradient based stability error
$\epsilon^{m}_{\text{GBstab}}$. If the randomized algorithm (at time $t$)
selects $J_{t}\neq J^{\prime}_{t}$ then $\epsilon^{m}_{d/K}\leq
2\beta\alpha_{t}\sqrt{d/K}[(m-1)\|w-w^{\prime}\|+2L]/m$, else
$\epsilon^{m}_{d/K}\leq 4\beta\alpha_{t}\|w-w^{\prime}\|\sqrt{d/K}$. We
provide a unified representation of the stability error
$\tilde{G}_{\\!J_{t}}(w)-\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime})$
in the Section (Mini-Batch ZoSS Growth Recursion, Lemma 13).

###  C.1 Results for the ZoSS with Mini-Batch

We start by providing the growth recursion lemma for the ZoSS with mini batch.

######  Lemma 13 (Mini-Batch ZoSS Growth Recursion)

Consider the sequences of updates $\\{\tilde{G}_{\\!J_{t}}\\}^{T}_{t=1}$ and
$\\{\tilde{G}^{\prime}_{\\!J_{t}}\\}^{T}_{t=1}$ and $\mu\leq
cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$. Let $w_{0}=w^{\prime}_{0}$ be the
starting point, $w_{t+1}=\tilde{G}_{\\!J_{t}}(w_{t})$ and
$w^{\prime}_{t+1}=\tilde{G}^{\prime}_{\\!J_{t}}(w^{\prime}_{t})$ for any
$t\in\\{1,\ldots,T\\}$. Then for any $w_{t},w^{\prime}_{t}\in\mathbb{R}^{d}$
and $t\geq 0$ the following recursion holds

$\displaystyle\mathbb{E}[\|\tilde{G}_{\\!J_{t}}(w_{t})-\tilde{G}^{\prime}_{\\!J_{t}}(w^{\prime}_{t})\|]\leq\begin{cases}\left(1+\beta\alpha_{t}\Gamma^{d}_{K}\right)\delta_{t}+\frac{cL\alpha_{t}}{n}\Gamma^{d}_{K}&\text{
if }\tilde{G}_{\\!J_{t}}(\cdot)=\tilde{G}^{\prime}_{\\!J_{t}}(\cdot)\\\
\left(1+\frac{m-1}{m}\beta\alpha_{t}\Gamma^{d}_{K}\right)\delta_{t}+\frac{2L\alpha_{t}}{m}\Gamma^{d}_{K}+\frac{cL\alpha_{t}}{n}\Gamma^{d}_{K}&\text{
if
}\tilde{G}_{\\!J_{t}}(\cdot)\neq\tilde{G}^{\prime}_{\\!J_{t}}(\cdot).\end{cases}$

Our next result provides a stability guarantee on the difference of the mini-
batch ZoSS outputs $W_{T},W^{\prime}_{T}$, that holds for any batch size $m$.

######  Theorem 14 (Stability of ZoSS with Mini Batch | Nonconvex Loss)

Assume that the loss function $f(\cdot,z)$ is $L$-Lipschitz and $\beta$-smooth
for all $z\in\mathcal{Z}$. Consider the ZoSS with mini batch of size
$m\in\\{1,\ldots,n\\}$, initial state $W_{0}=W^{\prime}_{0}$, iterates
$W_{t}=\tilde{G}_{\\!J_{t}}(W_{t})$,
$W^{\prime}_{t}=\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(W^{\prime}_{t})$ for
$t>0$, and with final-iterate estimates $W_{T}$ and $W^{\prime}_{T}$
corresponding to the data-sets $S,S^{\prime}$, respectively (that differ in
exactly one entry). Then the discrepancy
$\delta_{T}\triangleq\|W_{T}-W^{\prime}_{T}\|$ under the event
$\mathcal{E}_{\delta_{t_{0}}}$ and the choice $\mu\leq
cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$ satisfies the inequality

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]\leq\frac{(2+c)L\Gamma^{d}_{K}}{n}\sum^{T}_{t=t_{0}+1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\beta\alpha_{j}\Gamma^{d}_{K}\left(1-\frac{1}{n}\right)\right).$
(53)

We prove Theorem 14 in Appendix, Section C.3. Note that666Under the random
selection rule $\mathbb{P}(\mathcal{I}\leq
t_{0})=1-\mathbb{P}(\cap^{t_{0}}_{i=1}\\{\mathcal{I}\neq
i\\})=1-\prod^{t_{0}}_{i=1}\mathbb{P}(\\{\mathcal{I}\neq i\\})$.
$\mathbb{P}(\mathcal{I}\leq t_{0})=1-(1-m/n)^{t_{0}}$. By setting the free
parameter $t_{0}=0$ and through the Lipschitz assumption we find the stability
bound of the loss as
$\mathbb{E}\left[|f(W_{T},z)-f(W^{\prime}_{T},z)|\right]\leq
L\mathbb{E}[\delta_{T}]=L\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{0}}]]$.
The last inequality and the solution of the recursion in (53) show that
Theorem 7 and Theorem 8 hold for the ZoSS algorithm with mini batch, and any
batch size $m\in\\{1,\ldots,n\\}$ as well.

###  C.2 Proof of Lemma 12

Under the assumption of nonconvex losses we find the first part of the
statement as

$\displaystyle\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{\prime}_{t})\|$
$\displaystyle\leq\|w_{t}-w^{\prime}_{t}\|+\frac{\alpha_{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^{\prime}_{t}}\bigg{\|}$
$\displaystyle\leq\|w_{t}-w^{\prime}_{t}\|+\frac{\alpha_{t}}{m}\sum_{z\in
J_{t}}\bigg{\|}\nabla_{w}f(w,z)|_{w=w_{t}}-\nabla_{w}f(w,z)|_{w=w^{\prime}_{t}}\bigg{\|}$
$\displaystyle\leq\|w_{t}-w^{\prime}_{t}\|+\frac{\alpha_{t}}{m}\sum_{z\in
J_{t}}\beta\|w_{t}-w^{\prime}_{t}\|$
$\displaystyle=(1+\beta\alpha_{t})\|w_{t}-w^{\prime}_{t}\|.$ (54)

Further define $J^{-i^{*}}_{t}\triangleq J_{t}\setminus\\{z_{J_{t,i^{*}}}\\}$
and $J^{\prime-i^{*}}_{t}\triangleq
J^{\prime}_{t}\setminus\\{z^{\prime}_{J^{\prime}_{t,i^{*}}}\\}$, and notice
that $J^{-i^{*}}_{t}=J^{\prime-i^{*}}_{t}$ for any $t\leq T$ w.p. $1$.

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

[1, Lemma 2.4] for nonconvex loss ($\eta=1+\beta\alpha_{t}$) gives

$\displaystyle\|G(w_{t},z)-G(w^{\prime}_{t},z)\|$
$\displaystyle\leq(1+\beta\alpha_{t})\delta_{t},$ (56)
$\displaystyle\|G(w_{t},z_{J_{t,i^{*}}})-G^{\prime}(w^{\prime}_{t},z_{J^{\prime}_{t,i^{*}}}\|$
$\displaystyle\leq\delta_{t}+2L\alpha_{t}.$ (57)

By combining the last two together with (55) we find

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

The last gives the second part of the recursion and completes the proof.
$\Box$

###  C.3 Proof of Lemma 13 and Theorem 14

First we provide the proof of Lemma 13, then we apply Lemma 13 to prove
Theorem 14.

#### Proof of Lemma 13

Consider the update rules under the event
$\tilde{\mathcal{E}}_{t}\triangleq\\{\tilde{G}_{\\!J_{t}}(\cdot)\equiv\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(\cdot)\\}$
that occurs with probability $\mathbb{P}(\tilde{\mathcal{E}}_{t})=1-m/n$ for
all $t\leq T$. Similarly to (10) we find

$\displaystyle\tilde{G}_{\\!J_{t}}(w_{t})-\tilde{G}_{\\!J_{t}}(w^{\prime}_{t})$
$\displaystyle=\underbrace{w_{t}-\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}}_{G_{\\!J_{t}}(w_{t})}-\Big{(}\underbrace{w^{\prime}_{t}-\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}}}_{G_{\\!J_{t}}^{\prime}(w^{\prime}_{t})\equiv
G_{\\!J_{t}}(w^{\prime}_{t})}\Big{)}$
$\displaystyle\quad-\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{*}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}$
$\displaystyle\quad+\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{\dagger}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}$
$\displaystyle\quad-\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}},U^{t}_{k,i}\rangle
U^{t}_{k,i}$
$\displaystyle\quad\quad\quad-(\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}})\bigg{)}.$
(59)

Denote by $\mathbb{E}_{\mathbf{U}^{\otimes K\times m}_{t}}$ the expectation
with respect to product measure of the random vectors
$U^{t}_{k,i}\sim\mathcal{N}(0,I_{d})$ for all $k\in\\{1,2,\ldots,K\\}$,
$i\in\\{1,2,\ldots,m\\}$ and fixed $t\leq T$. Recall that $U^{t}_{k,i}$ are
independent for all $k\in\\{1,2,\ldots,K\\}$, $i\in\\{1,2,\ldots,m\\}$ and
$t\leq T$. Inequality (59) and triangle inequality give

$\displaystyle\mathbb{E}[\|\tilde{G}_{\\!J_{t}}(w_{t})-\tilde{G}_{\\!J_{t}}(w^{\prime}_{t})\|]$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{\prime}_{t})\|$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{*}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{\dagger}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\Bigg{[}\Bigg{\|}\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}},U^{t}_{k,i}\rangle
U^{t}_{k,i}$
$\displaystyle\quad\quad\quad-(\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}})\bigg{)}\Bigg{\|}\Bigg{]}$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{\prime}_{t})\|$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{*}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{\dagger}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\mathbb{E}_{\mathbf{U}^{\otimes
K}_{t,i}}\Bigg{\|}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}},U^{t}_{k,i}\rangle
U^{t}_{k,i}$
$\displaystyle\quad\quad\quad-(\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}})\bigg{)}\Bigg{\|}$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{\prime}_{t})\|$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{*}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{\dagger}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\sqrt{\frac{3d-1}{K}}\|\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}}\|$
(60)
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}(w^{\prime}_{t})\|+\frac{2\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}_{\mathbf{U}_{t,i,k}}\left[\|U^{t}_{k,i}\|^{3}\right]$
$\displaystyle\quad+\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\sqrt{\frac{3d-1}{K}}\|\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}}\|$
(61)
$\displaystyle\leq(1+\beta\alpha_{t})\delta_{t}+\frac{2\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}_{\mathbf{U}_{t,i,k}}\left[\|U^{t}_{k,i}\|^{3}\right]+\alpha_{t}\sqrt{\frac{3d-1}{K}}\beta\delta_{t}$
(62)
$\displaystyle\leq\left(1+\beta\alpha_{t}\Gamma^{d}_{K}\right)\delta_{t}+\mu\beta\alpha_{t}(3+d)^{3/2},$
(63)

to find the inequality (60) we applied Lemma 1, inequality (61) comes from the
triangle inequality and $\beta$-smoothness, to derive the inequality (62) we
applied the $1+\beta\alpha_{t}$-expansive property for the
$G_{\\!J_{t}}(\cdot)$ mapping (Lemma 12) and the $\beta$-smoothness of the
loss function, finally the inequality (63) holds since the random vectors
$U^{t}_{k,i}\sim\mathcal{N}(0,I_{d})$ are i.i.d. and
$\mathbb{E}[\|U^{t}_{k,i}\|]\leq(3+d)^{3/2}$ for all $k\in\\{1,2,\ldots,K\\}$,
$i\in\\{1,2,\ldots,m\\}$ and $t\leq T$. Under the choice $\mu\leq
cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$, (63) gives the first part the
inequality in Lemma 13.

We continue by considering the event
$\tilde{\mathcal{E}}^{c}_{t}\triangleq\\{G_{\\!J_{t}}(\cdot)\neq
G^{\prime}_{\\!J^{\prime}_{t}}(\cdot)\\}$. Recall that
$\tilde{\mathcal{E}}_{t}^{c}$ occurs with probability
$\mathbb{P}(\tilde{\mathcal{E}}_{t})=m/n$ for all $t\leq T$. Under the event
$\tilde{\mathcal{E}}_{t}^{c}$ similarly to (14) we derive the difference

$\displaystyle\tilde{G}_{\\!J_{t}}(w_{t})-\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})$
$\displaystyle=\underbrace{w_{t}-\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}}_{G_{\\!J_{t}}(w_{t})}-\bigg{(}\underbrace{w^{\prime}_{t}-\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}}}_{G_{\\!J_{t}}^{\prime}(w^{\prime}_{t})}\bigg{)}$
$\displaystyle\quad-\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{*}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}$
$\displaystyle\quad+\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=W^{\dagger}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}$
$\displaystyle\quad-\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}},U^{t}_{k,i}\rangle
U^{t}_{k,i}$
$\displaystyle\quad\quad\quad-(\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}})\bigg{)}.$
(64)

By using the triangle inequality and Lemma 1 we get

$\displaystyle\mathbb{E}[\|\tilde{G}_{\\!J_{t}}(w_{t})-\tilde{G}^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|]$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z_{J_{t,i}})|_{w=W^{*}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\left[\left\|\frac{\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\left(\frac{\mu}{2}U^{\text{T}}_{k}\nabla^{2}_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=W^{\dagger}_{k,t,i}}U^{t}_{k,i}\right)U^{t}_{k,i}\right\|\right]$
$\displaystyle\quad+\mathbb{E}_{\mathbf{U}^{\otimes K\times
m}_{t}}\Bigg{[}\Bigg{\|}\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}},U^{t}_{k,i}\rangle
U^{t}_{k,i}$
$\displaystyle\quad\quad\quad-(\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}})\bigg{)}\Bigg{\|}\Bigg{]}$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|+\frac{2\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}_{\mathbf{U}_{t,i,k}}\left[\|U^{t}_{k,i}\|^{3}\right]$
$\displaystyle\quad+\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\mathbb{E}_{\mathbf{U}^{\otimes
K}_{t,i}}\Bigg{\|}\bigg{(}\frac{1}{K}\sum^{K}_{k=1}\langle\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}},U^{t}_{k,i}\rangle
U^{t}_{k,i}$
$\displaystyle\quad\quad\quad-(\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}})\bigg{)}\Bigg{\|}$
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|+\frac{2\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}_{\mathbf{U}_{t,i,k}}\left[\|U^{t}_{k,i}\|^{3}\right]$
$\displaystyle\quad+\frac{\alpha_{t}}{m}\sum^{m}_{i=1}\sqrt{\frac{3d-1}{K}}\|\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}}\|$
(65)
$\displaystyle=\|G_{\\!J_{t}}(w_{t})-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|+\frac{2\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}_{\mathbf{U}_{t,i,k}}\left[\|U^{t}_{k,i}\|^{3}\right]$
$\displaystyle\quad+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}\sum^{m}_{i=1,i\neq
i^{*}}\|\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i}})|_{w=w^{\prime}_{t}}\|$
$\displaystyle\quad+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}\|\nabla_{w}f(w,z_{J_{t,i^{*}}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i^{*}}})|_{w=w^{\prime}_{t}}\|$
$\displaystyle=\|G_{\\!J_{t}}(w_{t})-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|+\frac{2\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}_{\mathbf{U}_{t,i,k}}\left[\|U^{t}_{k,i}\|^{3}\right]$
$\displaystyle\quad+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}\sum^{m}_{i=1,i\neq
i^{*}}\|\nabla_{w}f(w,z_{J_{t,i}})|_{w=w_{t}}-\nabla_{w}f(w,z_{J_{t,i}})|_{w=w^{\prime}_{t}}\|$
$\displaystyle\quad+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}\|\nabla_{w}f(w,z_{J_{t,i^{*}}})|_{w=w_{t}}-\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i^{*}}})|_{w=w^{\prime}_{t}}\|$
(66)
$\displaystyle\leq\|G_{\\!J_{t}}(w_{t})-G^{\prime}_{\\!J^{\prime}_{t}}(w^{\prime}_{t})\|+\frac{2\alpha_{t}}{mK}\sum^{m}_{i=1}\sum^{K}_{k=1}\frac{\mu\beta}{2}\mathbb{E}_{\mathbf{U}_{t,i,k}}\left[\|U^{t}_{k,i}\|^{3}\right]$
$\displaystyle\quad+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}(m-1)\beta\delta_{t}+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}2L$
(67)
$\displaystyle\leq\left(1+\frac{m-1}{m}\beta\alpha_{t}\right)\delta_{t}+\frac{2}{m}L\alpha_{t}+\mu\beta\alpha_{t}(3+d)^{3/2}$
$\displaystyle\quad+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}(m-1)\beta\delta_{t}+\sqrt{\frac{3d-1}{K}}\frac{\alpha_{t}}{m}2L$
(68)
$\displaystyle=\left(1+\frac{m-1}{m}\beta\alpha_{t}\Gamma^{d}_{K}\right)\delta_{t}+\frac{2L\alpha_{t}}{m}\Gamma^{d}_{K}+\mu\beta\alpha_{t}(3+d)^{3/2},$
(69)

we find the inequality (65) by applying Lemma 1, the inequality (66) holds
since $z_{J_{t,i}}=z^{\prime}_{J^{\prime}_{t,i}}$ for any $i\neq i^{*}$, we
find (67) by using the triangle inequality and $\beta$-smoothness (for $i\neq
i^{*}$) and $L-$Lipschitz condition to bound the norm of the gradients
$\nabla_{w}f(w,z_{J_{t,i^{*}}})|_{w=w_{t}}$ and
$\nabla_{w}f(w,z^{\prime}_{J^{\prime}_{t,i^{*}}})|_{w=w^{\prime}_{t}}$. In
(68) we apply Lemma 12 to bound the quantity
$\|G_{\\!J_{t}}(w_{t})-G_{\\!J_{t}}^{\prime}(w^{\prime}_{t})\|$. Under the
selection of $\mu\leq cL\Gamma^{d}_{K}/(n\beta(3+d)^{3/2})$, Eq. (69) gives
the second part of the inequality in Lemma 13. $\Box$

#### Proof of Theorem 14

We apply Lemma 13 to get

$\displaystyle\mathbb{E}[\delta_{t+1}|\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle=\mathbb{P}(\mathcal{E}_{t})\mathbb{E}[\delta_{t+1}|\mathcal{E}_{t},\mathcal{E}_{\delta_{t_{0}}}]+\mathbb{P}(\mathcal{E}^{c}_{t})\mathbb{E}[\delta_{t+1}|\mathcal{E}^{c}_{t},\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle=\left(1-\frac{m}{n}\right)\mathbb{E}[\delta_{t+1}|\mathcal{E}_{t},\mathcal{E}_{\delta_{t_{0}}}]+\frac{m}{n}\mathbb{E}[\delta_{t+1}|\mathcal{E}^{c}_{t},\mathcal{E}_{\delta_{t_{0}}}]$
$\displaystyle=\left(1-\frac{m}{n}\right)\left(\left(1+\beta\alpha_{t}\Gamma^{d}_{K}\right)\mathbb{E}[\delta_{t}|\mathcal{E}_{\delta_{t_{0}}}]+\frac{cL\alpha_{t}}{n}\Gamma^{d}_{K}\right)$
$\displaystyle\quad+\frac{m}{n}\left(1+\frac{m-1}{m}\beta\alpha_{t}\Gamma^{d}_{K}\right)\mathbb{E}[\delta_{t}|\mathcal{E}_{\delta_{t_{0}}}]+\frac{m}{n}\frac{2L\alpha_{t}}{m}\Gamma^{d}_{K}+\frac{m}{n}\frac{cL\alpha_{t}}{n}\Gamma^{d}_{K}$
$\displaystyle=\left(1+\beta\alpha_{t}\Gamma^{d}_{K}\left(1-\frac{1}{n}\right)\right)\mathbb{E}[\delta_{t}|\mathcal{E}_{\delta_{t_{0}}}]+\frac{2L\alpha_{t}}{n}\Gamma^{d}_{K}+\frac{cL\alpha_{t}}{n}\Gamma^{d}_{K}.$
(70)

The last display characterizes the general case of nonconvex loss and
coincides with the inequality (18) (since $\eta=1+\beta\alpha_{t}$). As a
consequence the solution of the recursion (70) is

$\displaystyle\mathbb{E}[\delta_{T}|\mathcal{E}_{\delta_{t_{0}}}]\leq\frac{(2+c)L\Gamma^{d}_{K}}{n}\sum^{T}_{t=t_{0}+1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\beta\alpha_{j}\Gamma^{d}_{K}\left(1-\frac{1}{n}\right)\right).$
(71)

The last display completes the proof. $\Box$

##  Appendix D Full-Batch GD

As a byproduct of our analysis we derive generalization error bounds for the
full-batch gradient decent. Although our results reduce to the full-batch GD
by a direct calculation of the limits $c\rightarrow 0$, $K\rightarrow\infty$
and setting the batch size $m$ equal to $n$, we separately prove
generalization error bounds for the full-batch GD for clarity.

###### Corollary 15

[Stability and Generalization Error of Full-Batch GD | Nonconvex Loss] Assume that the loss function $f(\cdot,z)$ is $L$-Lipschitz and $\beta$-smooth for all $z\in\mathcal{Z}$. Consider the (deterministic) full-batch GD algorithm, initial state $W_{0}=W^{\prime}_{0}$, iterates $W_{t}=G_{\\!S}(W_{t})$, $W^{\prime}_{t}=G^{\prime}_{\\!S^{\prime}}(W^{\prime}_{t})$ for $t>0$, and with final-iterate estimates $W_{T}$ and $W^{\prime}_{T}$ corresponding to the data-sets $S,S^{\prime}$, respectively (that differ in exactly one entry). Then the discrepancy $\delta_{T}\triangleq\|W_{T}-W^{\prime}_{T}\|$ satisfies the inequality

$\displaystyle\\!\\!\delta_{T}\leq\frac{2L}{n}\sum^{T}_{t=1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\frac{n-1}{n}\alpha_{j}\beta\right).$
(72)

Further if $\alpha_{t}\leq C/t$ for any $t>0$ and some $C>0$ then

$\displaystyle\\!\\!\\!\\!|\epsilon_{\text{gen}}|=|\mathbb{E}_{S}[\mathbb{E}_{z}[f(W_{T},z)]-\frac{1}{n}\sum_{z\in
S}f(W_{T},z)]|\leq\frac{2L^{2}\left(eT\right)^{C\beta}}{n}\min\left\\{C+\beta^{-1},C\log(eT)\right\\}.$
(73)

The proof of Corollary 15 follows.

#### Proof of Corollary 15 (Full-Batch GD)

In the case of full-batch GD the algorithm is deterministic and we assume that
$z_{1},z_{2},\ldots,z_{i},\ldots,z_{n},z^{\prime}_{i}$ are i.i.d. and define
$S\triangleq(z_{1},z_{2},\ldots,z_{i},\ldots,z_{n})$ and
$S^{\prime}\triangleq(z_{1},z_{2},\ldots,z^{\prime}_{i},\ldots,z_{n})$,
$W_{0}=W^{\prime}_{0}$, the updates for any $t\geq 1$ are

$\displaystyle W_{t+1}$
$\displaystyle=W_{t}-\frac{\alpha_{t}}{n}\sum^{n}_{j=1}\nabla f(W_{t},z_{j}),$
(74) $\displaystyle W^{\prime}_{t+1}$
$\displaystyle=W^{\prime}_{t}-\frac{\alpha_{t}}{n}\sum^{n}_{j=1,j\neq i}\nabla
f(W^{\prime}_{t},z_{j})-\frac{\alpha_{t}}{n}\nabla
f(W^{\prime}_{t},z^{\prime}_{i}).$ (75)

Then for any $t\geq 1$

$\displaystyle\delta_{t+1}$
$\displaystyle\leq\delta_{t}+\frac{\alpha_{t}}{n}\bigg{\|}\sum^{n}_{j=1,j\neq
i}\nabla f(W_{t},z_{j})-\nabla
f(W^{\prime}_{t},z_{j})\bigg{\|}+\frac{\alpha_{t}}{n}\|\nabla
f(W_{t},z_{i})-\nabla f(W^{\prime}_{t},z^{\prime}_{i})\|$
$\displaystyle\leq\delta_{t}+\frac{\alpha_{t}(n-1)}{n}\beta\delta_{t}+\frac{2L\alpha_{t}}{n}$
$\displaystyle=\left(1+\frac{(n-1)}{n}\beta\alpha_{t}\right)\delta_{t}+\frac{2L\alpha_{t}}{n}.$

Then by solving the recursion we find

$\displaystyle\delta_{T}\leq\frac{2L}{n}\sum^{T}_{t=1}\alpha_{t}\prod^{T}_{j=t+1}\left(1+\frac{n-1}{n}\alpha_{j}\beta\right).$
(76)

Under the choice $\alpha_{t}\leq C/t$ the last display gives

$\displaystyle\delta_{T}$
$\displaystyle\leq\frac{2L}{n}\sum^{T}_{t=1}\frac{C}{t}\prod^{T}_{j=t+1}\left(1+\frac{n-1}{n}\frac{C}{j}\beta\right)$
$\displaystyle\leq\frac{2L}{n}\sum^{T}_{t=1}\frac{C}{t}\prod^{T}_{j=t+1}\left(1+\frac{C}{j}\beta\right)$
$\displaystyle\leq\frac{2L}{n}\sum^{T}_{t=1}\frac{C}{t}\prod^{T}_{j=t+1}\exp\left(\frac{C}{j}\beta\right)$
$\displaystyle=\frac{2L}{n}\sum^{T}_{t=1}\frac{C}{t}\exp\left(\sum^{T}_{j=t+1}\frac{C}{j}\beta\right)$
$\displaystyle\leq\frac{2L}{n}\sum^{T}_{t=1}\frac{C}{t}\exp\left(C\beta\left(1+\log\frac{T}{t+1}\right)\right)$
$\displaystyle=\frac{2L\left(eT\right)^{C\beta}}{n}\sum^{T}_{t=1}\frac{C}{t}\frac{1}{(t+1)^{C\beta}}$
$\displaystyle\leq\frac{2L\left(eT\right)^{C\beta}}{n}\sum^{T}_{t=1}\frac{C}{t^{C\beta+1}}$
$\displaystyle\leq\frac{2CL\left(eT\right)^{C\beta}}{n}\min\left\\{\frac{C\beta+1}{C\beta},\log(eT)\right\\}.$
(77)

Then

$\displaystyle|\mathbb{E}_{S}[R_{S}(A_{S})-R(A_{S})]|$
$\displaystyle=|\mathbb{E}_{S,z^{\prime}_{i}}[f(W_{T},z^{\prime}_{i})-f(W^{\prime}_{T},z^{\prime}_{i})]|$
(78)
$\displaystyle\leq\mathbb{E}_{S,z^{\prime}_{i}}[|f(W_{T},z^{\prime}_{i})-f(W^{\prime}_{T},z^{\prime}_{i})|]$
$\displaystyle\leq L\mathbb{E}_{S,z^{\prime}_{i}}\|W_{T}-W^{\prime}_{T}\|$
(79)
$\displaystyle\leq\frac{2L^{2}\left(eT\right)^{C\beta}}{n}\min\left\\{C+\beta^{-1},C\log(eT)\right\\}.$
(80)

In the above, Eq. (78) follows from [17, Lemma 7], the inequality (79) holds
under the Lipschitz property of the loss $f(\cdot,z)$ for any $z$. Finally, we
find the last inequality (80) by applying the bound in (77). $\hfill\Box$