#
A Stochastic Newton Algorithm for Distributed Convex Optimization

Brian Bullins Toyota Technological Institute at Chicago<EMAIL_ADDRESS>Kumar Kshitij Patel
Toyota Technological Institute at Chicago<EMAIL_ADDRESS>Ohad Shamir
Weizmann Institute of Science<EMAIL_ADDRESS>

Nathan Srebro Toyota Technological Institute at Chicago<EMAIL_ADDRESS>Blake
Woodworth
Toyota Technological Institute at Chicago<EMAIL_ADDRESS>
###### Abstract

We propose and analyze a stochastic Newton algorithm for homogeneous
distributed stochastic convex optimization, where each machine can calculate
stochastic gradients of the same population objective, as well as stochastic
Hessian-vector products (products of an independent unbiased estimator of the
Hessian of the population objective with arbitrary vectors), with many such
stochastic computations performed between rounds of communication. We show
that our method can reduce the number, and frequency, of required
communication rounds compared to existing methods without hurting performance,
by proving convergence guarantees for quasi-self-concordant objectives (e.g.,
logistic regression), alongside empirical evidence.

##  1 Introduction

Stochastic optimization methods that leverage parallelism have proven
immensely useful in modern optimization problems. Recent advances in machine
learning have highlighted their importance as these techniques now rely on
millions of parameters and increasingly large training sets.

While there are many possible ways of parallelizing optimization algorithms,
we consider the intermittent communication setting (Zinkevich et al., 2010;
Cotter et al., 2011; Dekel et al., 2012; Shamir et al., 2014; Woodworth et
al., 2018, 2021), where $M$ parallel machines work together to optimize an
objective during $R$ rounds of communication, and where during each round each
machine may perform some basic operation (e.g., access the objective by
invoking some oracle) $K$ times, and then communicate with all other machines.
An important example of this setting is when this basic operation gives
independent, unbiased stochastic estimates of the gradient, in which case this
setting includes algorithms like Local SGD (Zinkevich et al., 2010; Coppola,
2015; Zhou and Cong, 2018; Stich, 2019; Woodworth et al., 2020a), Minibatch
SGD (Dekel et al., 2012), Minibatch AC-SA (Ghadimi and Lan, 2012), and many
others.

We are motivated by the observation of Woodworth et al. (2020a) that for
_quadratic_ objectives, first-order methods such as one-shot averaging
(Zinkevich et al., 2010; Zhang et al., 2013)—a special case of Local SGD with
a single round of communication—can optimize the objective to a very high
degree of accuracy. This prompts trying to reduce the task of optimizing
general convex objectives to a short sequence of quadratic problems. Indeed,
this is precisely the idea behind many second-order algorithms including
Newton’s method (Nesterov and Nemirovskii, 1994), trust-region methods
(Nocedal and Wright, 2006), and cubic regularization (Nesterov and Polyak,
2006), as well as methods that go beyond second-order information (Nesterov,
2019; Bullins, 2020).

Computing each Newton step requires solving, for convex $F$, a linear system
of the form $\nabla^{2}F(x)\Delta x=-\nabla F(x)$. This can, of course, be
done directly using the full Hessian of the objective. However, this is
computationally prohibitive in high dimensions, particularly when compared to
cheap stochastic gradients. To avoid this issue, we reformulate the Newton
step as the solution to a convex quadratic problem, $\min_{\Delta
x}\frac{1}{2}\Delta x^{\top}\nabla^{2}F(x)\Delta x\ +~{}\nabla
F(x)^{\top}\Delta x$, which we then solve using one-shot averaging.
Conveniently, computing stochastic gradient estimates for this quadratic
objective does not require computing the full Hessian matrix, as it only
requires stochastic gradients and _stochastic Hessian-vector products_. This
is attractive computationally since, for many problems, the cost of computing
stochastic Hessian-vector products is similar to the cost of computing
stochastic gradients, and both involve similar operations (Pearlmutter, 1994).
Furthermore, highlighting the importance of these estimates, recent works have
relied on Hessian-vector products to attain faster rates for reaching
approximate stationary points in both deterministic (Agarwal et al., 2017;
Carmon et al., 2018) and stochastic (Allen-Zhu, 2018; Arjevani et al., 2020)
non-convex optimization.

Table 1: Convergence guarantees for different algorithms in the intermittent
communication setting. Notation is as follows: $H$: smoothness; $U$: third-
order-smoothness; $\sigma$: stochastic gradient variance; $\rho$: stochastic
Hessian-vector product variance; $g(x;z)$: stochastic gradient oracle;
$h(x,u;z^{\prime})$: stochastic Hessian-vector product oracle (see Section 2
for complete details). For the sake of clarity, we omit additional constants
and logarithmic factors.
Algorithm (Reference) | Convergence Rate |  Assumption, Oracle Access
---|---|---
Local SGD (Woodworth et al., 2020a) | $\frac{HB^{2}}{KR}+\frac{\sigma B}{\sqrt{MKR}}+\frac{H^{1/3}\sigma^{2/3}B^{4/3}}{K^{1/3}R^{2/3}}$ |  A1 $g(x;z)$
FedAc (Yuan and Ma, 2020) | $\frac{HB^{2}}{KR^{2}}+\frac{\sigma B}{\sqrt{MKR}}+\min\left\\{\frac{H^{1/3}\sigma^{2/3}B^{4/3}}{K^{1/3}R},\frac{H^{1/2}\sigma^{1/2}B^{3/2}}{K^{1/4}R}\right\\}$ |  A1 $g(x;z)$
Local SGD (Yuan and Ma, 2020) | $\frac{HB^{2}}{KR}+\frac{\sigma B}{\sqrt{MKR}}+\frac{U^{1/3}\sigma^{2/3}B^{5/3}}{K^{1/3}R^{2/3}}$ |  A3 ($3^{rd}$-order Smooth) $g(x;z)$
FedAc (Yuan and Ma, 2020) | $\frac{HB^{2}}{KR^{2}}+\frac{\sigma B}{\sqrt{MKR}}+\frac{H^{1/3}\sigma^{2/3}B^{4/3}}{M^{1/3}K^{1/3}R}+\frac{U^{1/3}\sigma^{2/3}B^{5/3}}{K^{1/3}R^{4/3}}$ |  A3 ($3^{rd}$-order Smooth) $g(x;z)$
FedSN (Theorem 1) | exp. decay + $\frac{HB^{2}}{KR}+\frac{\sigma B}{\sqrt{MK}}+\frac{\rho B^{2}}{\sqrt{K}R}$ |  A2 (QSC) $g(x;z)$, $h(x,u;z^{\prime})$

In the context of distributed optimization, second-order methods have shown
promise in the empirical risk minimization (ERM) setting, whereby estimates of
$F$ are constructed by distributing the component functions of the finite-sum
problem across machines. Such methods which leverage this structure have since
been shown to lead to improved communication efficiency (Shamir et al., 2014;
Zhang and Xiao, 2015; Reddi et al., 2016; Wang et al., 2018; Crane and Roosta,
2019; Islamov et al., 2021; Gupta et al., 2021). An important difference,
however, is that these methods work in a batch setting, meaning they allow for
repeated access to the same $K$ examples each round on each machine, giving a
total of $MK$ samples. In contrast, we work in the stochastic (one-pass,
streaming) setting, and so our model independently samples a fresh set of $MK$
examples per round, for a total of $MKR$ examples.

#### Our results

Our primary algorithmic contribution, which we sketch below and present in
full in Section 3, is the method Federated-Stochastic-Newton (FedSN), a
distributed approximate Newton method which leverages the benefits of one-shot
averaging for quadratic problems. We provide in Section 3, under the condition
of quasi-self-concordance (Bach, 2010), the main guarantees of our method
(Theorem 1). In Section 4 we show how, for some parameter regimes in terms of
$M$, $K$, and $R$, our method may improve upon the rates of previous first-
order methods, including Local SGD and FedAc (Yuan and Ma, 2020). In Section
5, we present a more practical version of our method, FedSN-Lite (Algorithm
5), alongside empirical results which show that we can significantly reduce
communication as compared to other first-order methods.

Algorithm (Sketch) Federated-Stochastic-Newton, a.k.a., FedSN$(x_{0})$

(Operating on objective $F(\cdot)$ with stochastic gradient $g(\cdot;\cdot)$
and Hessian-vector product $h(\cdot;\cdot,\cdot)$ oracles.)

$x_{0}\in\mathbb{R}^{d}$.

$T$: main iterations; $\bar{\xi}$: local stability parameter; and $N$: binary
search iterations (see Table 2).

Approximate solution to $\min_{x}F(x)$

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

$\Lambda=\left\\{\lambda_{1},\dots,\lambda_{N}\right\\}$ $\triangleright$ Set
of regularization parameters

while $\Lambda\neq\varnothing$ do

$\lambda=\textrm{Median}(\Lambda)$

Define:
$Q_{\lambda}(u)=\frac{1}{2}u^{\top}(\bar{\xi}\nabla^{2}F(x)+\lambda\mathbf{I})u+\nabla
F(x)^{\top}u$$\triangleright$ Regularized quadratic subproblem

Run SGD on $Q_{\lambda}(u)$ independently on each machine (starting with
$u_{0}=0$) for $K$ steps, then communicate the final iterate $u_{K}^{m}$ from
each machine $m$, and average them to obtain
$\tilde{u}=\frac{1}{M}\sum_{m=1}^{M}u_{K}^{m}$.

if Sufficiently good $\lambda$ is found then

$\Delta\tilde{x}_{t}=\tilde{u}$

break

else

Reduce the size of $\Lambda$ by half.

Update: $x_{t+1}=x_{t}+\Delta\tilde{x}_{t}$

Return: $x_{T}$

##  2 Preliminaries

We consider the following optimization problem:

$\min_{x\in\mathbb{R}^{d}}F(x),$ (1)

and throughout we use $F^{*}$ to denote the minimum of this problem. We
further use $\left\|\cdot\right\|$ to denote the standard $\ell_{2}$ norm, we
let $\left\|x\right\|_{\mathbf{A}}\coloneqq\sqrt{x^{\top}\mathbf{A}x}$ for a
positive semidefinite matrix $\mathbf{A}$, and we let $\mathbf{I}$ denote the
identity matrix of order $d$.

Next, we establish several sets of assumptions, beginning with those which are
standard for smooth, stochastic, distributed convex optimization. We would
note that we are working in the _homogeneous_ distributed setting (i.e., each
machine may access the same distribution), rather than the heterogeneous
setting (Khaled et al., 2019; Karimireddy et al., 2019; Koloskova et al.,
2020; Woodworth et al., 2020b; Khaled et al., 2020).

######  Assumption 1 (A1).

  1. (a)

$F$ is convex, differentiable, and $H$-smooth, i.e., for all
$x,y\in\mathbb{R}^{d}$,

$F(y)\leq F(x)+\nabla F(x)^{\top}(y-x)+\frac{H}{2}\|y-x\|^{2}.$

  2. (b)

There is a minimizer $x^{*}\in\operatorname*{arg\,min}_{x}F(x)$ such that
$\|x^{*}\|\leq B$.

  3. (c)

We are given access to a stochastic first-order oracle in the form of an
estimator $g:\mathbb{R}^{d}\times\mathcal{Z}\mapsto\mathbb{R}^{d}$, and a
distribution $\mathcal{D}$ on $\mathcal{Z}$ such that, for any
$x\in\mathbb{R}^{d}$ queried by the algorithm, the oracle draws
$z\sim\mathcal{D}$, and the algorithm observes an estimate $g(x;z)$ that
satisfies:

    1. (i)

$g(x;z)$ is an unbiased gradient estimate, i.e., $\mathbb{E}_{z}g(x;z)=\nabla
F(x)$.

    2. (ii)

$g(x;z)$ has bounded variance, i.e., $\mathbb{E}_{z}\|g(x;z)-\nabla
F(x)\|^{2}\leq\sigma^{2}.$

In order to provide guarantees for Newton-type methods, we will require
additional notions of smoothness. In particular, we consider $\alpha$-quasi-
self-concordance (QSC) (Bach, 2010), which for convex and three-times
differentiable $F$ is satisfied for $\alpha\geq 0$ when, for all
$x\in\textrm{dom}(F)$, $v,u\in\mathbb{R}^{d}$,

$\lvert\nabla^{3}F(x)[v,u,u]\rvert\leq\alpha\|v\|\left(\nabla^{2}F(x)[u,u]\right),$

where we define

$\nabla^{k}F(x)[u_{1},u_{2},\dots,u_{k}]\coloneqq\frac{\partial^{k}}{\partial
u_{1},\partial u_{2},\dots,\partial
u_{k}}\raisebox{-2.15277pt}{$\big{|}$}_{t_{1}=0,t_{2}=0,\dots,t_{k}=0}F(x+t_{1}u_{1}+t_{2}u_{2}+\dots+t_{k}u_{k}),$

for $k\geq 1$, i.e., the $k^{th}$ directional derivative of $F$ at $x$ along
the directions $u_{1},u_{2},\dots,u_{k}$. Related to this is the condition of
$\alpha$-self-concordance, which has proven useful for classic problems in
linear optimization (Nesterov and Nemirovskii, 1994), whereby for all
$x\in\textrm{dom}(F),u\in\mathbb{R}^{d}$,

$\lvert\nabla^{3}F(x)[u,u,u]\rvert\leq
2\alpha\left(\nabla^{2}F(x)[u,u]\right)^{3/2}.$

Though quasi-self-concordance is perhaps not as widely studied as self-
concordance, recent work has brought its usefulness to light in the context of
machine learning (Bach, 2010; Karimireddy et al., 2018; Carmon et al., 2020).
Notably, for logistic regression, i.e., problems of the form

$\min_{x}F(x)=\frac{1}{N}\sum\limits_{i=1}^{N}\log\left(1+e^{-b_{i}\left\langle
a_{i},\,x\right\rangle}\right),$ (2)

we observe that $\alpha$-quasi-self-concordance holds with
$\alpha\leq\max_{i}\left\\{\|b_{i}a_{i}\|\right\\}$. Interestingly, this
function is _not_ self-concordant, thus highlighting the importance of
introducing the notion of QSC for such problems, and indeed, neither of these
conditions implies the other in general.111For the other direction, note that
$F(x)=-\ln(x)$ is $1$-self-concordant but not quasi-self-concordant.

We now introduce further assumptions in terms of both additional oracle access
and other smoothness notions. The following outlines the requirements for the
stochastic Hessian-vector products, though we again stress that the practical
cost of such an oracle is often on the order of that for stochastic gradients
(Pearlmutter, 1994; Allen-Zhu, 2018).

######  Assumption 2 (A2).

In addition to Assumption 1, we have:

  1. (a)

$F$ is three-times differentiable and $\alpha$-quasi-self-concordant, i.e.,
for all $x,v,u\in\mathbb{R}^{d},$

$\left\lvert\nabla^{3}F(x)[v,u,u]\right\rvert\leq\alpha\|v\|\nabla^{2}F(x)[u,u].$

  2. (b)

We are given access to a stochastic Hessian-vector product oracle in the form
of an estimator
$h:\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathcal{Z}\mapsto\mathbb{R}^{d}$,
and a distribution $\mathcal{D}$ on $\mathcal{Z}$ such that, for any pair
$x,u\in\mathbb{R}^{d}$ queried by the algorithm, the oracle draws
$z^{\prime}\sim\mathcal{D}$, and the algorithm observes an estimate
$h(x,u;z^{\prime})$ that satisfies:

    1. (i)

$h(x,u;z^{\prime})$ is an unbiased Hessian-vector product estimate, i.e.,
$\mathbb{E}_{z^{\prime}}h(x,u;z^{\prime})=\nabla F^{2}(x)u$.

    2. (ii)

$h(x,u;z^{\prime})$ has bounded variance of the form
$\mathbb{E}_{z^{\prime}}\|h(x,u;z^{\prime})-\nabla^{2}F(x)u\|^{2}\leq\rho^{2}\|u\|^{2}.$

Meanwhile, other works (e.g., Yuan and Ma, 2020) require different control
over third-order smoothness and fourth central moment. We do not require this
assumption in our analysis, and include it here for comparison.

######  Assumption 3 (A3).

In addition to Assumption 1, we have:

  1. (a)

$F$ is twice-differentiable and $U$-third-order-smooth, i.e., for all
$x,y\in\mathbb{R}^{d}$,

$F(y)\leq F(x)+\nabla
F(x)^{\top}(y-x)+\frac{1}{2}\left\langle\nabla^{2}F(x)(y-x),\,y-x\right\rangle+\frac{U}{6}\|y-x\|^{3}.$

  2. (b)

$g(x;z)$ has bounded fourth central moment, i.e.,
$\mathbb{E}_{z}\|g(x;z)-\nabla F(x)\|^{4}\leq\sigma^{4}.$

##  3 Main results

We begin by describing our main algorithm, FedSN (Algorithm 1). Namely, our
aim is to solve convex minimization problems $\min_{x}F(x)$, subject to
Assumption 2.

Algorithm 1 Federated-Stochastic-Newton, a.k.a., FedSN$(x_{0})$

(Operating on objective $F(\cdot)$ with stochastic gradient $g(\cdot;\cdot)$
and Hessian-vector product $h(\cdot;\cdot,\cdot)$ oracles.)

$x_{0}\in\mathbb{R}^{d}$.

$T$: main iterations; and $\bar{\xi}$: local stability (see Table 2).

Approximate solution to $\min_{x}F(x)$ $\triangleright$ See Theorem 1

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

$\Delta\tilde{x}_{t}=\textrm{{Constrained-Quadratic-
Solver}{}}\left(x_{t}\right)$$\triangleright$ Approx.
$\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}\frac{\bar{\xi}}{2}u^{\top}\nabla^{2}F(x_{t})u+\nabla
F(x_{t})^{\top}u$

Update: $x_{t+1}=x_{t}+\Delta\tilde{x}_{t}$

Return: $x_{T}$

We will rely throughout the paper on several hyperparameter settings and
parameter functions, which we collect in Tables 2 and 3. Recall that $M$ is
the amount of parallel workers, $R$ is the number of rounds of communication,
$K$ is the number of basic operations performed between rounds of
communication, and $H$, $B$, $\sigma$, $\alpha$, and $\rho$ are as defined in
Assumptions 1 and 2.

Hyperparameter Setting | Description
---|---
$T\coloneqq\Bigg{\lfloor}\frac{R}{4\zeta}\log^{2}\left(\left(\frac{R}{\zeta}\right)\right)\Bigg{\rfloor}$ (for $\zeta=4096+4\left(80+32\log K+24\log(1+2\alpha B)\right)^{2}$) | Main iterations
$\beta:=0$ | Momentum
$\bar{r}\coloneqq\min\left\\{\frac{32B}{T}\log(TK),\,\frac{1}{5\alpha}\right\\}$ | Trust-region radius
$\bar{\xi}\coloneqq\exp(\alpha\bar{r})$ | Local stability
$\bar{\lambda}\coloneqq\max\left\\{\frac{2eH}{K-2},\,\frac{2\rho}{\sqrt{K}},\,\frac{32eH\log(51200)}{K},\,\frac{4\rho\sqrt{2\log(51200)}}{\sqrt{K}},\,\frac{320\sqrt{2}\rho}{\sqrt{MK}},\,\frac{320\sigma}{\bar{r}\sqrt{MK}},\,\frac{8eH}{K-16}\right\\}$ | Regularization bound
$N\coloneqq\left\lceil 1+\frac{5}{2}\log\frac{H(B+5T\bar{r})}{3\bar{\lambda}\bar{r}}\right\rceil$ | Binary search iterations
$C\coloneqq\left\lceil 8\log\left(\lceil\log_{2}N\rceil\left(4+\frac{eH}{\bar{\lambda}}+\frac{80H(B+5T\bar{r})}{\bar{\lambda}\bar{r}}\right)\right)\right\rceil$ | Reg. quadratic repetitions
Table 2: Hyperparameters $T$, $\beta$, $\bar{r}$, $\bar{\xi}$, $\bar{\lambda}$, $N$, and $C$, as used by FedSN and its subroutines. Parameter Function | Description
---|---
$\eta_{k}(\lambda):=\begin{cases}\eta_{\lambda}&K\leq\frac{2}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\textrm{ or }k<\frac{K}{2}\\\ \frac{4}{\lambda\left(\frac{8}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}+k-\frac{K}{2}\right)}&K>\frac{2}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\textrm{ and }k\geq\frac{K}{2}\end{cases}$ | Reg. quadratic stepsizes
$w_{k}(\lambda):=\begin{cases}(1-\lambda\eta_{\lambda}+\eta_{\lambda}^{2}\rho^{2})^{-k-1}&K\leq\frac{2}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\\\ 0&K>\frac{2}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\textrm{ and }k<\frac{K}{2}\\\ \frac{8}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\\\ \qquad+\ k-\frac{K}{2}-1&K>\frac{2}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\textrm{ and }k\geq\frac{K}{2}\end{cases}$ | Reg. quadratic weights
Table 3: Parameter functions $\eta_{k}(\lambda)$ and $w_{k}(\lambda)$, as used
by FedSN and its subroutines, where $\bar{\xi}$ is as defined in Table 2, and
where $\eta_{\lambda}$ denotes
$\eta(\lambda):=\frac{1}{2}\min\left\\{\frac{1}{\bar{\xi}H+\lambda},\
\frac{\lambda}{\rho^{2}}\right\\}$.

Among our assumptions, we note in particular the condition of quasi-self-
concordance, under which several works have provided efficient optimization
methods. For example, Bach (2010) analyzes Newton’s method under QSC
conditions, in a manner analogous to that of standard self-concordance
analyses, to establish its behavior in the region of quadratic
$(\log\log(1/\epsilon))$ convergence. More recently, both Karimireddy et al.
(2018) and Carmon et al. (2020) have presented methods which rely instead on a
trust-region approach, whereby, for a given iterate $x_{t}$, each iteration
amounts to approximately solving a _constrained_ subproblem of the form

$\min_{\Delta x:\left\|\Delta x\right\|\leq c}\frac{\xi}{2}\Delta
x^{\top}\nabla^{2}F(x_{t})\Delta x+\nabla F(x_{t})^{\top}\Delta x,$

for some $\xi\geq 1$ and problem-dependent radius $c>0$. This stands in
constrast to the _unconstrained_ minimization problem $\min_{\Delta
x}\frac{\xi}{2}\Delta x^{\top}\nabla^{2}F(x)\Delta x+\nabla F(x)^{\top}\Delta
x$, which, as we may recall, forms the basis of the standard (damped) Newton
method. Carmon et al. (2020) further use their trust-region subroutine to
approximately implement a certain $\ell_{2}$-ball minimization oracle, which
they combine with an acceleration scheme (Monteiro and Svaiter, 2013).

These results show, at a high level, that as long as the radius of the
constrained quadratic (trust-region) subproblem is not too large, it is
possible to make sufficient progress on the _global_ problem by approximately
solving the quadratic subproblem. Our method proceeds in a similar fashion:
each iteration of Algorithm 1 provides an approximate solution to a
constrained quadratic problem. To begin, we follow Karimireddy et al. (2018)
in defining $\delta(r)$-local (Hessian) stability.

######  Definition 1.

Let $\delta:\mathbb{R}^{+}\mapsto\mathbb{R}^{+}$. We say that a twice-
differentiable and convex function $F$ is $\delta(r)$-locally stable if, for
any $r>0$ and any $x,y\in\mathbb{R}^{d}$ $(x\neq y)$ such that $\|x-y\|\leq r$
and $\|x-y\|_{\nabla^{2}F(x)}>0$,

$\|x-y\|_{\nabla^{2}F(y)}\leq\delta(r)\|x-y\|_{\nabla^{2}F(x)}.$

As the next lemma shows, quasi-self-concordance is sufficient to provide this
type of local stability.

######  Lemma 1 (Theorem I (Karimireddy et al., 2018)).

If $F$ is $\alpha$-quasi-self-concordant, then $F$ is $\delta(r)=\exp(\alpha
r)$-locally stable.

The advantage of local stability is that it ensures that approximate solutions
to locally-defined constrained quadratic problems can guarantee progress on
the global objective, and we state this more formally in the following lemma.
Note that this lemma is similar to (Theorem IV Karimireddy et al., 2018),
though we allow for an additive error in the subproblem solves in addition to
the multiplicative error, and its proof can be found in Appendix A.

######  Lemma 2.

Let $F$ satisfy Assumption 2 and be $\delta(r)$-locally stable for
$\delta:\mathbb{R}^{+}\mapsto\mathbb{R}^{+}$, let $x_{0}\in\mathbb{R}^{d}$ be
as input to FedSN (Algorithm 1), let $c>0$, let $\theta\in[0,1)$, and define

$Q_{t}(\Delta x)\coloneqq\frac{\delta\left(5c\right)}{2}\Delta
x^{\top}\nabla^{2}F(x_{t})\Delta x+\nabla F(x_{t})^{\top}\Delta x,$

where $x_{t}$ is the $t^{th}$ iterate of Algorithm 1. Furthermore, suppose we
are given that in each iteration of Algorithm 1, $\|\Delta\tilde{x}_{t}\|\leq
5c$ and

$\mathbb{E}Q_{t}(\Delta\tilde{x}_{t})-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}c}Q_{t}(\Delta x)\leq\theta\left(Q_{t}(0)-\min_{\Delta
x:\|\Delta x\|\leq\frac{1}{2}c}Q_{t}(\Delta x)\right)+\epsilon,$

for $\epsilon>0$. Then for each $T\geq 0$, Algorithm 1 guarantees

$\mathbb{E}F(x_{T})-F^{*}\leq\mathbb{E}\left[F(x_{0})-F^{*}\right]\exp\left(-\frac{Tc(1-\theta)}{2B\delta(\frac{1}{2}c)\delta\left(5c\right)}\right)+\frac{2B\delta(\frac{1}{2}c)d\left(5c\right)\epsilon}{c(1-\theta)}\
.$

We have now seen how to turn approximate solutions of constrained quadratic
problems into an approximate minimizer of the overall objective. We next need
to ensure that the output of our method Constrained-Quadratic-Solver
(Algorithm 2) meets the conditions of Lemma 2. As previously discussed,
Woodworth et al. (2020a) showed that first-order methods can very accurately
optimize _unconstrained_ quadratic objectives using a single round of
communication; however, here we need to optimize a quadratic problem subject
to a norm constraint. Our constrained quadratic solver is thus based on the
following idea: the minimizer of the _constrained_ problem $\min_{x:\|x\|\leq
c}Q(x)$ is the same as the minimizer of the _unconstrained_ problem
$\min_{x}Q(x)+\frac{\lambda^{*}}{2}\|x\|^{2}$ for some problem-dependent
regularization parameter $\lambda^{*}$. While the algorithm does not know what
$\lambda^{*}$ should be a priori, we show that it can be found with sufficient
confidence using binary search. Lemma 3, proven in Appendix B, provides the
relevant guarantees.

Algorithm 2 Constrained-Quadratic-Solver$(x)$

(Operating on objective $F(\cdot)$ with stochastic gradient $g(\cdot;\cdot)$
and Hessian-vector product $h(\cdot;\cdot,\cdot)$ oracles.)

$x\in\mathbb{R}^{d}$.

$\bar{r}$: trust-region radius; $\bar{\xi}$: local stability; $\bar{\lambda}$:
regularization bound; $N$: binary search iterations; and $C$: reg. quadratic
repetitions (see Table 2).

Approximate solution to
$\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}\frac{\bar{\xi}}{2}u^{\top}\nabla^{2}F(x)u+\nabla
F(x)^{\top}u$ $\triangleright$ See Lemma 3

$\Lambda_{1}=\left\\{\bar{\lambda}\left(\frac{3}{2}\right)^{n-1}\,:\,n=1,\dots,N\right\\}$

$i\leftarrow 1$

while $\Lambda_{i}\neq\varnothing$ do

$\lambda^{(i)}=\textrm{Median}(\Lambda_{i})$

for $c=1,\dots,C$ do

$\tilde{u}^{(i,c)}=\textrm{{Regularized-Quadratic-Solver}{}}(x,\lambda^{(i)})$

if
$\left\lvert\left\\{\tilde{u}^{(i,c)}:\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}\right\rvert>\frac{C}{2}$
then

$\tilde{u}=\textrm{{Regularized-Quadratic-Solver}{}}(x,\lambda^{(i)})$

Return:
$\hat{u}=\min\left\\{1,\,\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\tilde{u}$

else if
$\left\lvert\left\\{\tilde{u}^{(i,c)}:\left\|\tilde{u}^{(i,c)}\right\|\leq\frac{5}{2}\bar{r}\right\\}\right\rvert>\frac{C}{2}$
then

$\Lambda_{i+1}=\left\\{\lambda^{\prime}\in\Lambda_{i}\,:\,\lambda^{\prime}<\lambda^{(i)}\right\\}$

else if
$\left\lvert\left\\{\tilde{u}^{(i,c)}:\left\|\tilde{u}^{(i,c)}\right\|>\frac{5}{2}\bar{r}\right\\}\right\rvert>\frac{C}{2}$
then

$\Lambda_{i+1}=\left\\{\lambda^{\prime}\in\Lambda_{i}\,:\,\lambda^{\prime}>\lambda^{(i)}\right\\}$

else

Return: $\hat{u}=0$

$i\leftarrow i+1$

$\tilde{u}=\textrm{{Regularized-Quadratic-Solver}{}}(x,\bar{\lambda})$

Return:
$\hat{u}=\min\left\\{1,\,\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\tilde{u}$

######  Lemma 3.

Let $F$ satisfy Assumption 2, let $x$ be as input to Constrained-Quadratic-
Solver (Algorithm 2), let $\bar{\xi}$ be as in Table 2, define

$Q(u)\coloneqq\frac{\bar{\xi}}{2}u^{\top}\nabla^{2}F(x)u+\nabla
F(x)^{\top}u,\qquad
Q_{\lambda}(u)\coloneqq\frac{1}{2}u^{\top}(\bar{\xi}\nabla^{2}F(x)+\lambda\mathbf{I})u+\nabla
F(x)^{\top}u,$ $u_{\lambda}^{*}\coloneqq\arg\min_{u}Q_{\lambda}(u),\qquad
r^{*}(\lambda)\coloneqq\|u_{\lambda}^{*}\|,$

and let $\lambda_{r}$ denote, for any $r>0$, the value such that
$r^{*}(\lambda_{r})=r$. Let $\hat{u}$ be the output of Algorithm 2 for
hyperparameters $\bar{r}$, $\bar{\xi}$, $\bar{\lambda}$, $N$ and $C$ as in
Table 2, and suppose the output $\tilde{u}_{\lambda}$ of Regularized-
Quadratic-Solver$(x,\lambda)$ satisfies for all $\lambda\geq\bar{\lambda}$
that

$\mathbb{E}Q_{\lambda}(\tilde{u}_{\lambda})-\min_{u}Q_{\lambda}(u)\leq\epsilon(\lambda)\coloneqq\frac{\lambda(r^{*}(\lambda)^{2}+\bar{r}^{2})}{800}\
.$

Then $\|\hat{u}\|\leq 5\bar{r}$ and

$\mathbb{E}Q(\hat{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\frac{3}{4}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda_{4\bar{r}})+\frac{\bar{\lambda}\bar{r}^{2}}{4}\
.$

We now show that using one-shot averaging (Zinkevich et al., 2010; Zhang et
al., 2012) with $M$ machines—i.e., averaging the results of $M$ independent
runs of SGD—suffices to solve each quadratic problem to the desired accuracy.
The following lemma, which we prove in Appendix C, establishes that
Regularized-Quadratic-Solver (Algorithm 3) supplies Algorithm 2 with an output
$\hat{u}$ that satisfies the conditions of Lemma 3.

######  Lemma 4.

Let $F$ satisfy Assumption 2, let $x\in\mathbb{R}^{d}$,
$\lambda\in\mathbb{R}^{+}$ be as input to Regularized-Quadratic-Solver
(Algorithm 3), let
$Q_{\lambda}(u)=\frac{1}{2}u^{\top}(\bar{\xi}\nabla^{2}F(x)+\lambda\mathbf{I})u+\nabla
F(x)^{\top}u$, let $Q_{\lambda}^{*}\coloneqq\min_{u}Q_{\lambda}(u)$, let
$u^{*}\coloneqq\operatorname*{arg\,min}_{u}Q_{\lambda}(u)$, and let stochastic
first-order and stochastic Hessian-vector product oracles for $F$, as defined
in Assumptions 1 and 2, respectively, be available for each call to
Regularized-Quadratic-Gradient-Access (Algorithm 4), for either Case 1 _(
Different-Samples)_ or Case 2 _( Same-Sample)_. Let $\hat{u}$, as output by
Algorithm 3, be a weighted average of the iterates of $M$ independent runs of
SGD with stepsizes $\eta_{0}(\lambda),\dots,\eta_{K-1}(\lambda)$, i.e.,

$\hat{u}=\frac{1}{M\sum_{k=0}^{K-1}w_{k}}\sum_{m=1}^{M}\sum_{k={}0}^{K-1}w_{k}u_{k}^{m}.$

Then, for both Cases 1 and 2,

$\mathbb{E}Q_{\lambda}(\hat{u})-Q_{\lambda}^{*}\leq\begin{cases}2\max\left\\{\bar{\xi}H+\lambda,\frac{\rho^{2}}{\lambda}\right\\}\left\|u^{*}\right\|^{2}\min\left\\{\frac{1}{K},\,\exp\left(-\frac{K+1}{4}\min\left\\{\frac{\lambda}{\bar{\xi}H+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)\right\\}+\frac{2(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda
MK}\\\\[5.0pt] \hfill\textrm{if
}K\leq\frac{2}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\\\
\\\
96\lambda\left\|u^{*}\right\|^{2}\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{\bar{\xi}H+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)+\frac{96(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda
MK}\hfill\textrm{ if
}K>\frac{2}{\lambda}\max\left\\{\bar{\xi}H+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}.\end{cases}$

Algorithm 3 Regularized-Quadratic-Solver$(x,\lambda)$

(Operating on objective $F(\cdot)$ with stochastic gradient $g(\cdot;\cdot)$
and Hessian-vector product $h(\cdot;\cdot,\cdot)$ oracles.)

$x\in\mathbb{R}^{d}$, $\lambda\in\mathbb{R}^{+}$.

$\beta$: momentum; $\bar{\xi}$: local stability; and parameter functions
$\eta_{k}(\lambda)$, $w_{k}(\lambda)$ (see Tables 2 and 3).

Approximate solution to
$\min_{u}Q_{\lambda}(u)=\frac{1}{2}u^{\top}(\bar{\xi}\nabla^{2}F(x)+\lambda\mathbf{I})u+\nabla
F(x)^{\top}u$$\triangleright$ See Lemma 4

Initialize: $u_{0}^{1},\dots,u_{0}^{M}=0$ $\triangleright$ Initial iterates on
each machine

for Each machine $m=1,\dots,M$ in parallel do

for $k=0,\dots,K-1$ do

$\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{{}^{\prime}m})=$ Regularized-Quadratic-
Gradient-Access$(x,u_{k}^{m},\lambda)$

$u_{k+1}^{m}=u_{k}^{m}-\eta_{k}(\lambda)\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{{}^{\prime}m})+\mathbbm{1}_{\\{k>0\\}}\beta(u_{k}^{m}-u_{k-1}^{m})$
222We add heavy-ball/Polyak momentum in this step with momentum parameter
$\beta$. Our theoretical results do not require any momentum, and thus FedSN
is analyzed for $\beta=0$. For our experiments we compare the algorithms both
with and without momentum, i.e., $\beta=0$ or optimally tuned
$\beta\in\\{0.1,0.3,0.5,0.7,0.9\\}$.

Return:
$\tilde{u}=\frac{1}{M\sum_{k=1}^{K}w_{k}(\lambda)}\sum_{m=1}^{M}\sum_{k=1}^{K}w_{k}(\lambda)u_{k}^{m}$

Algorithm 4 Regularized-Quadratic-Gradient-Access$(x,u,\lambda)$

(Operating on objective $F(\cdot)$ with stochastic gradient $g(\cdot;\cdot)$
and Hessian-vector product $h(\cdot;\cdot,\cdot)$ oracles.)

$x,u\in\mathbb{R}^{d}$, $\lambda\in\mathbb{R}^{+}$.

$\bar{\xi}$: local stability (see Table 2).

$\gamma(u;z,z^{\prime})$ s.t.
$\mathbb{E}_{z,z^{\prime}}[\gamma(u;z,z^{\prime})]=\nabla Q_{\lambda}(u)$ and
$\mathbb{E}_{z,z^{\prime}}\left\|\gamma(u;z,z^{\prime})-\nabla
Q_{\lambda}(u)\right\|^{2}\leq\sigma^{2}+\rho^{2}\left\|u\right\|^{2}$

Case 1: Different-Samples ($z,z^{\prime}$ drawn independently for each
stochastic oracle)

  * •

Query the stochastic first-order oracle at $x$ (as in Assumption 1(c)), so
that the oracle draws $z\sim\mathcal{D}$, and observe $g(x;z)$

  * •

Query the stochastic Hessian-vector product oracle at $x$ and $u$ (as in
Assumption 2(b)), so that the oracle draws $z^{\prime}\sim\mathcal{D}$, and
observe $h(x,u;z^{\prime})$

Case 2: Same-Sample (Same $z^{\prime}=z$ used for both stochastic oracles)

  * •

Query the stochastic first-order oracle at $x$ (as in Assumption 1(c)), so
that the oracle draws $z\sim\mathcal{D}$, and observe $g(x;z)$

  * •

Query the stochastic Hessian-vector product oracle at $x$ and $u$ (as in
Assumption 2(b)) for $z^{\prime}=z$, and observe $h(x,u;z^{\prime})$

$\gamma(u;z,z^{\prime})\coloneqq\bar{\xi}h(x,u;z^{\prime})+\lambda u+g(x;z)$

Return: $\gamma(u;z,z^{\prime})$

Our analysis for Algorithm 3 is based on ideas similar to those of Woodworth
et al. (2020a), whereby the algorithm may access the stochastic oracles via
Regularized-Quadratic-Gradient-Access (Algorithm 4). However, additional care
must be taken to account for the fact that Algorithm 4 supplies stochastic
gradient estimates of the _quadratic subproblems_ $Q_{\lambda}(u)$ as per the
oracles models described in Assumptions 1 and 2. Thus, the estimates—based in
part on stochastic Hessian-vector products—have variance that scales with the
norm of the respective iterates of Algorithm 3 (see Assumption 2(b.ii)).

We also note two possible cases for the oracle access: Case 1 (Different-
Samples) in Algorithm 4 requires both a call to a stochastic first-order
oracle (which draws $z\sim\mathcal{D}$) and a call to a stochastic Hessian-
vector product oracle (which draws a different $z^{\prime}\sim\mathcal{D}$);
while Case 2 (Same-Sample) allows both stochastic estimators to be observed
for the same random sample $z\sim\mathcal{D}$. These cases differ by only a
small constant factor in the final convergence rate, and we base our practical
method on this single sample model. We refer the reader to Section E.3 for
additional discussion of these alternative settings. Finally, having analyzed
Algorithms 1, 2, 3, and 4, we may put them all together to provide our main
theoretical result, whose proof can be found in Appendix D.

######  Theorem 1.

Let $F$ satisfy Assumption 2. Then, for $K\geq 175$ and
$R\geq\tilde{\Omega}(1)$, and for hyperparameters $T$, $\beta$, $\bar{r}$,
$\bar{\xi}$, $\bar{\lambda}$, $N$, $C$ and parameter functions
$\eta_{k}(\lambda)$, $w_{k}(\lambda)$ as in Tables 2 and 3, the output of
FedSN (Algorithm 1) with initial point $x_{0}\in\mathbb{R}^{d}$, using
Algorithms 2, 3, and 4 (for both Cases 1 and 2) satisfies

$\mathbb{E}[F(x_{T})]-F^{*}\leq
HB^{2}\left(\exp\left(-\frac{R}{\tilde{O}\left(\alpha
B\right)}\right)+\exp\left(-\frac{K}{O(1)}\right)\right)+\tilde{O}\left(\frac{\sigma
B}{\sqrt{MK}}+\frac{HB^{2}}{KR}+\frac{\rho B^{2}}{\sqrt{K}R}\right)\ ,$

where $\tilde{\Omega}$, $\tilde{O}$ hide terms logarithmic in $R$, $K$, and
$\alpha B$.

##  4 Comparison with related methods and lower bounds

In this section, we compare our algorithm’s guarantees with those of other,
previously proposed first-order methods. A difficulty in making this
comparison is determining the “typical” relative scale of the parameters $H$,
$\sigma$, $Q$, $\alpha$, and $\rho$. We therefore draw inspiration from
training generalized linear models in considering a natural scaling of the
parameters that arises when the objective has the form
$F(x)=\mathbb{E}_{z}\ell(\left\langle x,\,z\right\rangle)$, where
$\lvert\ell^{\prime}\rvert$, $\lvert\ell^{\prime\prime}\rvert$, and
$\lvert\ell^{\prime\prime\prime}\rvert$ are $O(1)$; this holds, e.g., for
logistic regression problems (see (2)). In this case, upper bounds on the
derivatives of $F$ will generally scale with the norm of the data, i.e.,
$\|z\|$. So if we assume that $\|z\|\leq D$ for some $D$, then the derivatives
of $F$ would generally scale as $\|\nabla F(x)\|\lesssim D$,
$\|\nabla^{2}F(x)\|_{\textrm{op}}\lesssim D^{2}$, and
$\|\nabla^{3}F(x)\|_{\textrm{op}}\lesssim D^{3}$, where
$\left\|\cdot\right\|_{\textrm{op}}$ denotes the operator norm. Thus, in the
rest of this section, we will take $H=D^{2}$, $\sigma=D$, $U=D^{3}$,
$\alpha=D$, and $\rho=D^{2}$. It is, of course, possible that these parameters
could have different relationships, but we focus on this regime for
simplicity.

In addition to working within this natural scaling, we consider the case where
we have access to a sufficient number of machines (i.e.,
$M\gtrsim\frac{KR^{3}}{D^{2}B^{2}}$) and where $K$ is sufficiently large. We
explore various regimes both w.r.t. the number of rounds of communication $R$
(though we restrict ourselves to $R\gtrsim DB\log(DBK)$ for technical
reasons), as well as w.r.t. $DB$, which roughly captures the “size” of the
problem. Thus, ignoring constants and terms logarithmic in $R$, $K$, and
$\alpha B$ for the sake of clarity, our upper bound from Theorem 1 reduces to

$\mathbb{E}F(\hat{x})-F^{*}\lesssim
D^{2}B^{2}\exp\left(-\frac{R}{DB}\right)+D^{2}B^{2}\exp\left(-K\right)+\frac{D^{2}B^{2}}{KR^{3/2}}+\frac{D^{2}B^{2}}{KR}+\frac{D^{2}B^{2}}{\sqrt{K}R}\approx\frac{D^{2}B^{2}}{\sqrt{K}R}\
.$ (3)

#### Comparison with Local SGD

Recall that, under third-order smoothness assumptions (Yuan and Ma, 2020),
Local SGD converges at a rate of

$\mathbb{E}F(\hat{x})-F^{*}\leq\tilde{O}\left(\frac{HB^{2}}{KR}+\frac{\sigma
B}{\sqrt{MKR}}+\frac{Q^{1/3}\sigma^{2/3}B^{5/3}}{K^{1/3}R^{2/3}}\right)\ .$

For the setting as outlined above, this bound reduces to

$\mathbb{E}F(\hat{x})-F^{*}\lesssim\frac{D^{2}B^{2}}{KR}+\frac{D^{2}B^{2}}{KR^{2}}+\frac{D^{5/3}B^{5/3}}{K^{1/3}R^{2/3}}\approx\frac{D^{2}B^{2}}{KR}+\frac{D^{5/3}B^{5/3}}{K^{1/3}R^{2/3}}\
.$

In the case where $DB$ is not too large ($DB\lesssim K^{2}R$), the dominant
term for Local SGD is $\frac{D^{5/3}B^{5/3}}{K^{1/3}R^{2/3}}$, and so we see
that our algorithm improves upon Local SGD as long as
$R\gtrsim\frac{D^{1/3}B^{1/3}}{K^{1/6}}$.

#### Comparison with FedAc

The previous best known first-order distributed method under third-order
smoothness assumptions is FedAc (Yuan and Ma, 2020), an accelerated variant of
the Local SGD method, which, as we recall, achieves a guarantee of

$\mathbb{E}F(\hat{x})-F^{*}\leq\tilde{O}\left(\frac{HB^{2}}{KR^{2}}+\frac{\sigma
B}{\sqrt{MKR}}+\frac{H^{1/3}\sigma^{2/3}B^{4/3}}{M^{1/3}K^{1/3}R}+\frac{Q^{1/3}\sigma^{2/3}B^{5/3}}{K^{1/3}R^{4/3}}\right)\
.$

For the setting as outlined above, this bound reduces to

$\mathbb{E}F(\hat{x})-F^{*}\lesssim\frac{D^{2}B^{2}}{KR^{2}}+\frac{D^{5/3}B^{5/3}}{K^{1/3}R^{4/3}}\
.$

In the case where $DB$ is not too large ($DB\lesssim K^{2}R^{2}$), the
dominant term for FedAc is $\frac{D^{5/3}B^{5/3}}{K^{1/3}R^{4/3}}$, and so we
see that our algorithm improves upon FedAc as long as
$R\lesssim\frac{\sqrt{K}}{DB}$, whereas for $R\gtrsim\frac{\sqrt{K}}{DB}$,
FedAc provides better guarantees than FedSN.

#### Comparison with min-max method under Assumption 1

Woodworth et al. (2021) identified the min-max optimal (up to logarithmic
factors) stochastic first-order method in the distributed setting we consider,
and under Assumption 1. Namely, a min-max optimal method can be obtained by
combining Minibatch-Accelerated-SGD (Cotter et al., 2011), which enjoys a
guarantee of

$\mathbb{E}F(\hat{x})-F^{*}\leq O\left(\frac{HB^{2}}{R^{2}}+\frac{\sigma
B}{\sqrt{MKR}}\right)\ ,$

with Single-Machine Accelerated SGD, which runs $KR$ steps of an accelerated
variant of SGD known as AC-SA (Lan, 2012), and enjoys a guarantee of

$\mathbb{E}F(\hat{x})-F^{*}\leq O\left(\frac{HB^{2}}{K^{2}R^{2}}+\frac{\sigma
B}{\sqrt{KR}}\right)\ .$

Therefore, an algorithm which returns the output of Minibatch Accelerated SGD
when $K\leq\frac{\sigma^{2}R^{3}}{H^{2}B^{2}}$, and otherwise returns the
output of Single-Machine Accelerated SGD, achieves a guarantee of

$\mathbb{E}F(\hat{x})-F^{*}\leq
O\left(\frac{H^{2}B^{2}}{K^{2}R^{2}}+\frac{\sigma
B}{\sqrt{MKR}}+\min\left\\{\frac{HB^{2}}{R^{2}},\frac{\sigma
B}{\sqrt{KR}}\right\\}\right)\ .$

As shown by Woodworth et al. (2021), this matches the lower bound for
stochastic distributed first-order optimization under Assumption 1, up to
$O(\log^{2}M)$ factors.

For the setting as outlined above, this bound reduces to

$\mathbb{E}F(\hat{x})-F^{*}\lesssim\frac{D^{2}B^{2}}{K^{2}R^{2}}+\frac{D^{2}B^{2}}{KR^{2}}+\min\left\\{\frac{D^{2}B^{2}}{R^{2}},\frac{DB}{\sqrt{KR}}\right\\}\approx\frac{D^{2}B^{2}}{K^{2}R^{2}}+\min\left\\{\frac{D^{2}B^{2}}{R^{2}},\frac{DB}{\sqrt{KR}}\right\\}\
.$

Thus, for $DB\lesssim\frac{R^{3/2}}{\sqrt{K}}$, the dominant term is
$\frac{D^{2}B^{2}}{R^{2}}$, in which case FedSN is better as long as
$R\lesssim\sqrt{K}$. Furthermore, for $\frac{R^{3/2}}{\sqrt{K}}\lesssim
DB\lesssim K^{3/2}R^{3/2}$, the dominant term is $\frac{DB}{\sqrt{KR}}$, in
which case FedSN is better as long as $R\gtrsim D^{2}B^{2}$. In these regimes,
we see that Assumption 2 allows FedSN to improve over the best possible when
relying only on Assumption 1. We also note that when $DB\gtrsim
K^{3/2}R^{3/2}$, the combined algorithm described above is better than the
guarantee we prove for FedSN—we do not know whether this is a weakness of our
analysis or represents a true deficiency of FedSN in this regime.

#### Comparison with first-order lower bounds

Woodworth et al. (2021) additionally provide lower bounds under other
smoothness conditions, including quasi-self-concordance, which are relevant to
the current work. Roughly speaking, they show that under Assumption 2(a), no
first-order intermittent communication algorithm can guarantee suboptimality
less than (ignoring constant and $\log M$ factors)

$\mathbb{E}F(\hat{x})-F^{*}\geq\frac{HB^{2}}{K^{2}R^{2}}+\frac{\sigma
B}{\sqrt{MKR}}+\min\left\\{\frac{HB^{2}}{R^{2}},\frac{\alpha\sigma
B^{2}}{\sqrt{K}R^{2}},\frac{\sigma B}{\sqrt{KR}}\right\\}\ .$

In the same parameter regime as above, the lower bound reduces to

$\mathbb{E}F(\hat{x})-F^{*}\gtrsim\frac{D^{2}B^{2}}{K^{2}R^{2}}+\min\left\\{\frac{D^{2}B^{2}}{\sqrt{K}R^{2}},\frac{DB}{\sqrt{KR}}\right\\}\
.$

Comparing this lower bound with our guarantee in Theorem 1, we see that, when
$DB=O(1)$ and the number of rounds of communication is small (e.g., $R=O(\log
K)$), our approximate Newton method can (ignoring $\log K$ factors) achieve an
upper bound of $\mathbb{E}F(\hat{x})-F^{*}\lesssim 1/\sqrt{K}$. Therefore, in
this important regime, FedSN matches the lower bound under Assumption 2(a),
albeit using a stronger oracle—the stochastic Hessian-vector product oracle
ensured by Assumption 2(b), rather than only a stochastic first-order oracle.
No prior work has been able to match this lower bound, and so we do not know
whether such an oracle (or perhaps allowing multiple accesses to each
component, which is an even stronger oracle) is necessary in order to achieve
it, or if perhaps the stronger oracle even allows for breaking it. Either way,
we improve over all prior stochastic methods we are aware of in this setting,
and at the very least match the best possible using any stochastic first-order
method.

##  5 Experiments

We begin by presenting a more practical variant of FedSN called FedSN-Lite in
Algorithm 5. It differs from FedSN in two major ways: first, it directly uses
Regularized-Quadratic-Solver (Algorithm 3) (with $\bar{\xi}=1$) as an
approximate quadratic solver without requiring a search over the
regularization parameter as in Algorithm 2; and in addition, it scales the
Newton update with a stochastic approximation of the Newton decrement (see
Nesterov (1998); Boyd and Vandenberghe (2004)) and a constant stepsize $\nu$
(we use $\nu=1.25$ in our experiments). Because of these changes, the Newton
update is fairly robust to the choice of $\nu$, so we then only need to tune
the learning rate of Regularized-Quadratic-Solver, making it as usable as any
other first-order method.

Algorithm 5 FedSN-Lite$(x_{0})$

(Operating on objective $F(\cdot)$ with stochastic gradient $g(\cdot;\cdot)$
and Hessian-vector product $h(\cdot;\cdot,\cdot)$ oracles.)

$x_{0}\in\mathbb{R}^{d}$.

$T$: main iterations; $\nu$: Newton stepsize scale; and $\beta$: momentum.

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

Regularized-Quadratic-Solver$(x_{t},0)$

$\nu_{t}:=\nu\left(1+(\Delta\tilde{x}_{t}^{\top}h(x_{t},\Delta\tilde{x}_{t};z))^{1/2}\right)^{-1}$
$\triangleright\ h(x_{t},\Delta\tilde{x}_{t};z)\ \text{is s.t.}\
\mathbb{E}_{z}[h(x_{t},\Delta\tilde{x}_{t};z)]=\nabla^{2}F(x_{t})\Delta\tilde{x}_{t}$
333We can calculate an approximation to the Newton decrement at
$\Delta\tilde{x}_{t}$, i.e.,
$(\Delta\tilde{x}_{t}^{\top}\nabla^{2}F(x_{t})\Delta\tilde{x}_{t})^{1/2}$,
using a call to the Hessian-vector product oracle (see Assumption 2(b)), along
with an additional dot product, namely
$\Delta\tilde{x}_{t}^{\top}h(x_{t},\Delta\tilde{x}_{t};z)$.

Update: $x_{t+1}=x_{t}+\nu_{t}\Delta\tilde{x}_{t}$

Return: $x_{T}$

Note that in each step of FedSN-Lite, the subroutine Regularized-Quadratic-
Solver approximately solves a quadratic subproblem using a variant of one-shot
averaging. Moreover, we implement FedSN-Lite such that each call to the
stochastic oracle from within Regularized-Quadratic-Solver uses only a single
sample (Case 2 in Algorithm 4), and so it is asymptotically as expensive as
the gradient oracle (i.e., $O(d)$, if $d$ is the dimension of the problem).
For a discussion of the computational cost of using a Hessian-vector product
oracle, see Section E.3.

Baselines. We compare FedSN-Lite against the two variants of FedAc (Algorithm
6, Yuan and Ma (2020)), Minibatch SGD (Algorithm 8, Dekel et al. (2012)), and
Local SGD (Algorithm 7, Zinkevich et al. (2010)). We also study the effect of
adding Polyak’s momentum, which we denote by $\beta$, to these algorithms (see
Section E.1). FedAc is mainly presented and analyzed for strongly convex
functions by Yuan and Ma (2020). In fact, they assume the knowledge of the
strong convexity constant to tune FedAc, which is typically hard to know
unless the function is explicitly regularized. To handle general convex
functions Yuan and Ma (2020) build some internal regularization into FedAc
(see Appendix E.2 in their paper). However, their hyperparameter
recommendations in this setting also depend on unknowns such as the smoothness
of the function and the variance of the stochastic gradients. This poses a
difficulty in comparing FedAc to the other algorithms, which do not require
the knowledge of these unknowns.

The main goal of our experiments is to be comprehensive and to fairly compare
with the baselines, giving especially FedAc the benefit of the doubt in light
of the above difficulty in comparing against it. With this in mind we conduct
the two experiments on the LIBSVM a9a (Chang and Lin, 2011; Dua and Graff,
2017) dataset for binary classification using the logistic regression model.

#### Experiment 1: Adding internal regularization to FedAc

(a) Each algorithm besides FedAc solves an unregularized ERM problem, and
reports the best relative sub-optimality w.r.t. the optimal minimizer. All
optimization runs were repeated $70$ times with the tuned hyperparameters.

(b) Each algorithm besides FedAc solves an unregularized ERM problem (with a
single pass on the training data), and reports the best validation loss on a
held-out dataset. We used $20{,}000$ samples for training, and validated on
the remaining dataset. All optimization runs were repeated $20$ times with the
tuned hyperparameters.

Figure 1: Empirical comparison of FedSN-Lite (Algorithm 5) to other methods
(see Section E.1 for complete details) on the LIBSVM a9a (Chang and Lin, 2011;
Dua and Graff, 2017) dataset for minimizing: (a) in-sample, and (b) out-of-
sample unregularized logistic regression loss using $M\in\\{100,200\\}$
machines. We vary the frequency of communication (horizontal axis of each
plot), while keeping the total number of steps on each machine (theoretical
parallel runtime) fixed at $KR=100$. For FedAc we tune the learning rate for
different levels of internal regularization in $\\{$1e-2, 1e-3, 1e-4, 1e-5,
1e-6$\\}$. For the other algorithms we tune the learning rate for either
$\beta=0$, i.e., without momentum, or for all
$\beta\in\\{0.1,0.3,0.5,0.7,0.9\\}$, to choose the optimal level of momentum.
We repeat this tuning procedure for each value of $M,R$, and thus each point
in the plot represents an optimal configuration of that algorithm for that
setting.

We take the more carefully optimized version of FedAc for strongly convex
functions and tune its internal regularization and learning rate: (a) for
minimizing the unregularized training loss (Figure 1(a)), and (b) for
minimizing the out-of-sample loss (Figure 1(b)). This emulates the setting
where the objective is assumed to be a general convex function, though FedAc
sees a strongly convex function instead. Specifically, we are concerned with
minimizing a convex function $F(x)$. In the first case (Figure 1(a)) we are
minimizing a finite sum, i.e., $F(x)=\sum_{i\in S}f_{i}(x)$ where $S$ is our
training dataset. In the second case (Figure 1(b))
$F(x)~{}=\mathbb{E}_{z\in\mathcal{D}}[f(x;z)]$, i.e., a stochastic
optimization problem where we access the distribution $\mathcal{D}$ through
our finite sample $S$. To estimate the true-error on $\mathcal{D}$, we split
$S$ into $S_{train}$ and $S_{val}$, then sample without replacement from
$S_{train}$ to train our models, and report the final performance on
$S_{val}$.

Figure 2: Empirical comparison of FedSN-Lite (Algorithm 5) to other methods
(see Section E.1 for complete details) on the LIBSVM a9a (Chang and Lin, 2011;
Dua and Graff, 2017) dataset for minimizing $\mu$-regularized logistic
regression loss using $M\in\\{100,200\\}$ machines and $\mu\in\\{$1e-4,
1e-6$\\}$ regularization strength. We vary the frequency of communication
(horizontal axis of each plot), while keeping the total number of steps on
each machine (theoretical parallel runtime) fixed at $KR=100$. Each algorithm
besides solves a regularized ERM problem, and reports the best relative sub-
optimality w.r.t. the optimal minimizer. For FedAc we use $\mu$ as the strong
convexity constant to tune its hyperparameters. For the other algorithms we
tune the learning rate for either $\beta=0$, i.e., without momentum, or for
all $\beta\in\\{0.1,0.3,0.5,0.7,0.9\\}$, to choose the optimum level of
momentum. We repeat this tuning procedure for each value of $\mu,M,R$, and
thus each point in the plot represents an optimal configuration of that
algorithm for that setting. All optimization runs were repeated $30$ times
with the tuned hyperparameters.

#### Experiment 2: Optimizing regularized objectives

We consider regularized empirical risk minimization (Figure 2), where we
provide FedAc the regularization strength $\mu$ which serves as its estimate
of the strong convexity for the objective. Unlike Experiment 1, here we report
regularized training loss, i.e., we train the models to optimize
$F(x)+r(x)=\sum_{i\in S}f_{i}(x)+\frac{\mu}{2}\|x\|_{2}^{2}$, for a finite
dataset $S$. We also vary the regularization strength $\mu$, to understand the
algorithms’ dependence on the problem’s conditioning. This was precisely the
experiment conducted by Yuan and Ma (2020) (c.f., Figures 3 and 5 in their
paper).

Implementation details. Both the experiments are performed over a wide range
of communication rounds and machines, to mimic different systems trade-offs.
We always search for the best learning rate $\eta\in\\{0.0001,0.0002,$
$0.0005,0.001,0.002,0.005,0.01,0.02,0.05,0.1,0.2,0.5,1,2,5,10,20\\}$ for every
configuration of each algorithm (where we then set the parameter functions as
$\eta(\lambda)=\eta$ and $w(\lambda)=\frac{1}{K}$). We verify that the optimal
learning rates always lie in this range. More details can be found in Section
E.2.

Observation. In all our experiments we notice that FedSN-Lite is either
competitive with or outperforms the other baselines. This is especially true
for the sparse communication settings, which are of most practical interest. A
more comprehensive set of experiments can be found in Section E.4.

##  6 Conclusion

In this work, we have shown how to more efficiently optimize convex quasi-
self-concordant objectives by leveraging parallel methods for quadratic
problems. Our method can, in some parameter regimes, improve upon existing
stochastic methods while maintaining a similar computational cost, and we have
further seen how our method may provide empirical improvements in the low
communication regime. In order to do so we rely on stochastic Hessian-vector
product access, instead of just stochastic gradient calculations. In many
situations stochastic Hessian-vector products can be calculated just as easily
as stochastic gradients. Furthermore, Hessian-vector products can be
calculated to arbitrary accuracy using two stochastic gradient accesses to the
same component (i.e., the same sample). It remains open whether the same
guarantees we achieve here can also be achieved using only independent
stochastic gradients (a single stochastic gradient on each sample), or whether
in the distributed stochastic setting access to Hessian-vector products is
strictly more powerful than access to only independent stochastic gradients.

##### Acknowledgements.

Research was partially supported by NSF-BSF award 1718970. BW is supported by
a Google Research PhD Fellowship.

## References

  * Agarwal et al. (2017) Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma.  Finding approximate local minima faster than gradient descent.  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1195–1199, 2017.
  * Allen-Zhu (2018) Zeyuan Allen-Zhu.  Natasha 2: faster non-convex optimization than sgd.  In _Advances in Neural Information Processing Systems_ , pages 2680–2691, 2018.
  * Arjevani et al. (2020) Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan.  Second-order information in non-convex stochastic optimization: Power and limitations.  In _Conference on Learning Theory_ , pages 242–299. PMLR, 2020.
  * Bach (2010) Francis Bach.  Self-concordant analysis for logistic regression.  _Electronic Journal of Statistics_ , 4:384–414, 2010.
  * Boyd and Vandenberghe (2004) Stephen Boyd and Lieven Vandenberghe.  _Convex Optimization_.  Cambridge University Press, 2004.
  * Bullins (2020) Brian Bullins.  Highly smooth minimization of non-smooth problems.  In _Conference on Learning Theory_ , pages 988–1030. PMLR, 2020.
  * Carmon et al. (2018) Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford.  Accelerated methods for nonconvex optimization.  _SIAM Journal on Optimization_ , 28(2):1751–1772, 2018.
  * Carmon et al. (2020) Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian.  Acceleration with a ball optimization oracle.  In _Advances in Neural Information Processing Systems_ , volume 33, 2020.
  * Chang and Lin (2011) Chih-Chung Chang and Chih-Jen Lin.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2:27:1–27:27, 2011.  Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  * Coppola (2015) Greg Coppola.  _Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing_.  PhD thesis, The University of Edinburgh, 2015.
  * Cotter et al. (2011) Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan.  Better mini-batch algorithms via accelerated gradient methods.  In _Advances in Neural Information Processing Systems_ , volume 24, pages 1647–1655, 2011.
  * Crane and Roosta (2019) Rixon Crane and Fred Roosta.  Dingo: Distributed Newton-type method for gradient-norm optimization.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Dekel et al. (2012) Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao.  Optimal distributed online prediction using mini-batches.  _Journal of Machine Learning Research_ , 13(Jan):165–202, 2012.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Ghadimi and Lan (2012) Saeed Ghadimi and Guanghui Lan.  Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework.  _SIAM Journal on Optimization_ , 22(4):1469–1492, 2012.
  * Gupta et al. (2021) Vipul Gupta, Avishek Ghosh, Michal Derezinski, Rajiv Khanna, Kannan Ramchandran, and Michael Mahoney.  LocalNewton: Reducing communication bottleneck for distributed learning.  _arXiv preprint arXiv:2105.07320_ , 2021.
  * Islamov et al. (2021) Rustem Islamov, Xun Qian, and Peter Richtárik.  Distributed second order methods with fast rates and compressed communication.  _arXiv preprint arXiv:2102.07158_ , 2021.
  * Karimireddy et al. (2018) Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi.  Global linear convergence of Newton’s method without strong-convexity or lipschitz gradients.  _arXiv preprint arXiv:1806.00413_ , 2018.
  * Karimireddy et al. (2019) Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh.  SCAFFOLD: Stochastic controlled averaging for on-device federated learning.  _arXiv preprint arXiv:1910.06378_ , 2019.
  * Khaled et al. (2019) Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.  First analysis of local gd on heterogeneous data.  _arXiv preprint arXiv:1909.04715_ , 2019.
  * Khaled et al. (2020) Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.  Tighter theory for local sgd on identical and heterogeneous data.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4519–4529. PMLR, 2020.
  * Koloskova et al. (2020) Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich.  A unified theory of decentralized sgd with changing topology and local updates.  In _International Conference on Machine Learning_ , pages 5381–5393. PMLR, 2020.
  * Lan (2012) Guanghui Lan.  An optimal method for stochastic composite optimization.  _Mathematical Programming_ , 133(1-2):365–397, 2012.
  * Monteiro and Svaiter (2013) Renato DC Monteiro and Benar Fux Svaiter.  An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.  _SIAM Journal on Optimization_ , 23(2):1092–1125, 2013.
  * Nesterov (1998) Yurii Nesterov.  Introductory lectures on convex programming volume i: Basic course.  _Lecture notes_ , 3(4):5, 1998.
  * Nesterov (2019) Yurii Nesterov.  Implementable tensor methods in unconstrained convex optimization.  _Mathematical Programming_ , pages 1–27, 2019.
  * Nesterov and Nemirovskii (1994) Yurii Nesterov and Arkadii Nemirovskii.  _Interior-point polynomial algorithms in convex programming_.  SIAM, 1994.
  * Nesterov and Polyak (2006) Yurii Nesterov and Boris T Polyak.  Cubic regularization of Newton method and its global performance.  _Mathematical Programming_ , 108(1):177–205, 2006\.
  * Nocedal and Wright (2006) Jorge Nocedal and Stephen Wright.  _Numerical optimization_.  Springer Science & Business Media, 2006.
  * Pearlmutter (1994) Barak A Pearlmutter.  Fast exact multiplication by the Hessian.  _Neural Computation_ , 6(1):147–160, 1994.
  * Reddi et al. (2016) Sashank J Reddi, Jakub Konečnỳ, Peter Richtárik, Barnabás Póczós, and Alex Smola.  Aide: Fast and communication efficient distributed optimization.  _arXiv preprint arXiv:1608.06879_ , 2016.
  * Shamir et al. (2014) Ohad Shamir, Nati Srebro, and Tong Zhang.  Communication-efficient distributed optimization using an approximate Newton-type method.  In _International Conference on Machine Learning_ , pages 1000–1008. PMLR, 2014.
  * Stich (2019) Sebastian U Stich.  Local sgd converges fast and communicates little.  In _International Conference on Learning Representations_ , 2019.
  * Wang et al. (2018) Shusen Wang, Fred Roosta, Peng Xu, and Michael W Mahoney.  Giant: Globally improved approximate Newton method for distributed optimization.  _Advances in Neural Information Processing Systems_ , 31:2332–2342, 2018.
  * Woodworth et al. (2020a) Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro.  Is local sgd better than minibatch sgd?  In _International Conference on Machine Learning_ , pages 10334–10343. PMLR, 2020a.
  * Woodworth et al. (2021) Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro.  The min-max complexity of distributed stochastic convex optimization with intermittent communication.  In _Conference on Learning Theory_. PMLR, 2021.
  * Woodworth et al. (2018) Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro.  Graph oracle models, lower bounds, and gaps for parallel stochastic optimization.  _Advances in Neural Information Processing Systems_ , 31:8496–8506, 2018.
  * Woodworth et al. (2020b) Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro.  Minibatch vs local sgd for heterogeneous distributed learning.  _Advances in Neural Information Processing Systems_ , 33:6281–6292, 2020b.
  * Yuan and Ma (2020) Honglin Yuan and Tengyu Ma.  Federated accelerated stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Zhang and Xiao (2015) Yuchen Zhang and Lin Xiao.  Disco: Distributed optimization for self-concordant empirical loss.  In _International Conference on Machine Learning_ , pages 362–370. PMLR, 2015.
  * Zhang et al. (2012) Yuchen Zhang, Martin J Wainwright, and John C Duchi.  Communication-efficient algorithms for statistical optimization.  In _Advances in Neural Information Processing Systems_ , pages 1502–1510, 2012.
  * Zhang et al. (2013) Yuchen Zhang, John C Duchi, and Martin J Wainwright.  Communication-efficient algorithms for statistical optimization.  _The Journal of Machine Learning Research_ , 14(1):3321–3363, 2013.
  * Zhou and Cong (2018) Fan Zhou and Guojing Cong.  On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization.  In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18_ , pages 3219–3227. International Joint Conferences on Artificial Intelligence Organization, 7 2018\.  doi: 10.24963/ijcai.2018/447.
  * Zinkevich et al. (2010) Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola.  Parallelized stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , pages 2595–2603, 2010.

##  Appendix A Analysis of Algorithm 1

We will use the following notation in our analysis:

$Q^{\sigma}_{t}(\Delta x)=\frac{\sigma}{2}\Delta
x^{\top}\nabla^{2}F(x_{t})\Delta x+\nabla F(x_{t})^{\top}\Delta x.$ (4)

######  Lemma 5 (Lemma 5 (Karimireddy et al., 2018)).

Let $F$ be $\delta(r)$-locally stable for a given
$\delta:\mathbb{R}^{+}\mapsto\mathbb{R}^{+}$, let $\|x^{*}\|\leq B$, let
$r>0$, let $\gamma=r/B$ and $x_{\gamma}^{*}=(1-\gamma)x_{t}+\gamma x^{*}$, and
let $x_{t+1}=x_{t}+\Delta\tilde{x}_{t}$ for $\|\Delta\tilde{x}_{t}\|\leq r$.
Then

$\displaystyle F(x_{t+1})-F(x_{t})$ $\displaystyle\leq
Q_{t}^{\delta(r)}(\Delta\tilde{x}_{t})$ $\displaystyle
F(x_{\gamma}^{*})-F(x_{t})$ $\displaystyle\geq
Q_{t}^{1/\delta(r)}(x_{\gamma}^{*}-x_{t}).$

######  Lemma 6 (Lemma 6 (Karimireddy et al., 2018)).

For any convex domain $\mathcal{Q}$ and constants $a\cdot b\geq 1$,

$\min_{\Delta x\in\mathcal{Q}}Q^{a}(\Delta x)\leq\frac{1}{ab}\min_{\Delta
x\in\mathcal{Q}}Q^{1/b}(\Delta x).$

We will now prove Lemma 2 from Section 3.

See 2

###### Proof.

To begin, we are given by the assumptions of the theorem statement that
Algorithm 1 chooses the update $\Delta\tilde{x}_{t}$ such that
$\|\Delta\tilde{x}_{t}\|\leq 5c$ and

$\mathbb{E}Q_{t}^{\delta(5c)}(\Delta\tilde{x}_{t})-\min_{\|\Delta
x\|\leq\frac{1}{2}c}Q_{t}^{\delta(5c)}(\Delta
x)\leq\epsilon+\theta\left(Q_{t}^{\delta(5c)}(0)-\min_{\|\Delta
x\|\leq\frac{1}{2}c}Q_{t}^{\delta(5c)}(\Delta x)\right).$ (5)

Therefore,

$\displaystyle\mathbb{E}\left[F(x_{t+1})-F(x_{t})\right]$
$\displaystyle\leq\mathbb{E}Q_{t}^{\delta(5c)}(\Delta\tilde{x}_{t})$ (6)
$\displaystyle\leq\epsilon+(1-\theta)\min_{\Delta x\,:\,\|\Delta
x\|\leq\frac{1}{2}c}Q_{t}^{\delta(5c)}(\Delta x)$ (7)
$\displaystyle\leq\epsilon+\frac{1-\theta}{\delta(5c)\delta(\frac{1}{2}c)}\min_{\Delta
x\,:\,\|\Delta x\|\leq\frac{1}{2}c}Q_{t}^{1/\delta(\frac{1}{2}c)}(\Delta x)$
(8)
$\displaystyle\leq\epsilon+\frac{1-\theta}{\delta(5c)\delta(\frac{1}{2}c)}Q_{t}^{1/\delta(\frac{1}{2}c)}\left(\left(1-\frac{c}{2B}\right)x_{t}+\frac{c}{2B}x^{*}-x_{t}\right)$
(9)
$\displaystyle\leq\epsilon+\frac{1-\theta}{\delta(5c)\delta(\frac{1}{2}c)}\left[F\left(\left(1-\frac{c}{2B}\right)x_{t}+\frac{c}{2B}x^{*}\right)-F(x_{t})\right]$
(10)
$\displaystyle\leq\epsilon+\frac{1-\theta}{\delta(5c)\delta(\frac{1}{2}c)}\left[\left(1-\frac{c}{2B}\right)F\left(x_{t}\right)+\frac{c}{2B}F^{*}-F(x_{t})\right]$
(11)
$\displaystyle=\epsilon-\frac{c(1-\theta)}{2B\delta(5c)\delta(\frac{1}{2}c)}\left[F(x_{t})-F^{*}\right].$
(12)

Here we used Lemma 5 for the first inequality, Lemma 6 for the third, Lemma 5
again for the fifth, and the convexity of $F$ for the sixth.

Rearranging, and unravelling the recursion, we conclude that

$\displaystyle\mathbb{E}\left[F(x_{T})-F^{*}\right]$
$\displaystyle\leq\left(1-\frac{c(1-\theta)}{2B\delta(5c)\delta(\frac{1}{2}c)}\right)^{T}\mathbb{E}\left[F(x_{0})-F^{*}\right]+\epsilon\sum_{t=0}^{T}\left(1-\frac{c(1-\theta)}{2B\delta(5c)\delta(\frac{1}{2}c)}\right)^{t}$
(13)
$\displaystyle\leq\mathbb{E}\left[F(x_{0})-F^{*}\right]\exp\left(-\frac{Tc(1-\theta)}{2B\delta(5c)\delta(\frac{1}{2}c)}\right)+\frac{2B\delta(5c)\delta(\frac{1}{2}c)\epsilon}{c(1-\theta)}\
.$ (14)

This completes the proof. ∎

##  Appendix B Proof of Lemma 3

Before we analyze Algorithm 2, we recall some key definitions. For a given
$x\in\mathbb{R}^{d}$, we let

$Q(u)=\frac{\bar{\xi}}{2}u^{\top}\nabla^{2}F(x)u+\nabla F(x)^{\top}u,$ (15)

and for a regularization penalty $\lambda$, we also define

$Q_{\lambda}(u)=\frac{1}{2}u^{\top}(\bar{\xi}\nabla^{2}F(x)+\lambda\mathbf{I})u+\nabla
F(x)^{\top}u.$ (16)

We use $u_{\lambda}^{*}$ to denote the (unique) minimizer of $Q_{\lambda}(u)$,
and we use $r^{*}(\lambda)=\|u_{\lambda}^{*}\|$ to denote the norm of the
minimizer. For $0\leq r\leq r^{*}(0)$, we also use $\lambda_{r}$ to denote the
value of $\lambda$ such that $r^{*}(\lambda_{r})=r$ (Lemma 7 below shows that
$\lambda_{r}$ is unique).

######  Lemma 7 (Lemmas 35 and 36 (Carmon et al., 2020)).

For any $r$, there exists a unique $\lambda_{r}\geq 0$ such that

$u^{*}_{r}=\operatorname*{arg\,min}_{u:\|u\|\leq
r}Q(u)=\operatorname*{arg\,min}_{u\in\mathbb{R}^{d}}Q_{\lambda_{r}}(u)=-(\nabla^{2}F(x)+\lambda_{r}\mathbf{I})^{-1}\nabla
F(x).$

Also, $\lambda_{r}$ is decreasing in $r$, and if $\lambda_{r}\neq 0$ then
$\|u^{*}_{r}\|=r$.

######  Lemma 8.

For $r\leq r^{*}(0)$, $\lambda_{r}\in\left[0,\frac{\|b\|}{r}\right]$.

###### Proof.

By Lemma 7, $\lambda\geq 0$. If $\lambda>0$, then since $\nabla^{2}F(x)\succeq
0$ ( by convexity of $F$), we have that

$r=\|u^{*}_{\lambda}\|=\|(\nabla^{2}F(x)+\lambda\mathbf{I})^{-1}\nabla
F(x)\|\leq\frac{\|\nabla F(x)\|}{\lambda}.$ (17)

Rearranging completes the proof. ∎

######  Lemma 9.

For any $r\geq 0$ let $\lambda\geq\gamma\geq 0$ such that $r^{*}(\lambda)=r$
and $r^{*}(\gamma)=2r$. Then

$\mathbb{E}\left[Q_{\gamma}(u)-Q_{\gamma}(u^{*}_{\gamma})\right]\leq\epsilon\implies\mathbb{E}\left[Q(u)-Q(u^{*}_{\lambda})\right]\leq\epsilon.$

Furthermore, for any $y$ and $\gamma$,

$\mathbb{E}\left[Q_{\gamma}(u)-Q_{\gamma}(u^{*}_{\gamma})\right]\leq\epsilon\implies\mathbb{E}\left[Q(u)-Q(y)\right]\leq\epsilon+\frac{\gamma\left\|y\right\|^{2}}{2}.$

###### Proof.

For any $u$,

$\displaystyle\mathbb{E}\left[Q_{\gamma}(u)-Q(u^{*}_{\lambda})\right]$
$\displaystyle=\mathbb{E}\left[Q_{\gamma}(u)-Q_{\gamma}(u^{*}_{\gamma})\right]+Q_{\gamma}(u^{*}_{\gamma})-Q_{\gamma}(u^{*}_{\lambda})+\frac{\gamma}{2}\left\|u^{*}_{\lambda}\right\|^{2}$
(18)
$\displaystyle\leq\epsilon+Q_{\gamma}(u^{*}_{\gamma})-Q_{\gamma}(u^{*}_{\lambda})+\frac{\gamma}{2}\left\|u^{*}_{\lambda}\right\|^{2}.$
(19)

By the $\gamma$-strong convexity of $Q_{\gamma}$, the fact that either
$\gamma=0$ or $\|u^{*}_{\lambda}\|=r$ and $\|u^{*}_{\gamma}\|=2r$, and the
reverse triangle inequality,

$Q_{\gamma}(u^{*}_{\gamma})-Q_{\gamma}(u^{*}_{\lambda})+\frac{\gamma}{2}\left\|u^{*}_{\lambda}\right\|^{2}\leq-\frac{\gamma}{2}\left\|u^{*}_{\gamma}-u^{*}_{\lambda}\right\|^{2}+\frac{\gamma
r^{2}}{2}\leq-\frac{\gamma(2r-r)^{2}}{2}+\frac{\gamma r^{2}}{2}=0.$ (20)

Combining (20) with (19) completes the first part of the proof. For the second
part, we observe that

$\mathbb{E}\left[Q(u)+\frac{\gamma}{2}\|u\|^{2}-Q(y)\right]=\mathbb{E}\left[Q_{\gamma}(u)-Q_{\gamma}(u^{*}_{\gamma})\right]+Q_{\gamma}(u^{*}_{\gamma})-Q_{\gamma}(y)+\frac{\gamma}{2}\|y\|^{2}\leq\epsilon+\frac{\gamma\|y\|^{2}}{2}.$
(21)

Above, we used that $Q_{\lambda}(u^{*}_{\lambda})=\min_{u}Q_{\lambda}(u)\leq
Q_{\lambda}(y)$. ∎

######  Lemma 10.

Let $\lambda\geq\gamma\geq 0$. Then ,

$\frac{\lambda}{\gamma}\geq\frac{\|u^{*}_{\gamma}\|}{\|u^{*}_{\lambda}\|}.$

###### Proof.

By the definition of
$u^{*}_{\gamma}=\operatorname*{arg\,min}_{u}Q_{\gamma}(u)$ and
$u^{*}_{\lambda}=\operatorname*{arg\,min}_{u}Q_{\lambda}(u)$ and the
$\gamma$\- and $\lambda$-strong convexity of $Q_{\gamma}$ and $Q_{\lambda}$,
respectively,

$\frac{\lambda-\gamma}{2}\left(\left\|u^{*}_{\gamma}\right\|^{2}-\left\|u^{*}_{\lambda}\right\|^{2}\right)=Q_{\gamma}(u^{*}_{\lambda})-Q_{\gamma}(u^{*}_{\gamma})+Q_{\lambda}(u^{*}_{\gamma})-Q_{\lambda}(u^{*}_{\lambda})\geq\frac{\lambda+\gamma}{2}\left\|u^{*}_{\lambda}-u^{*}_{\gamma}\right\|^{2}.$
(22)

Therefore, by rearranging and applying the reverse triangle inequality

$\frac{\lambda-\gamma}{\lambda+\gamma}\geq\frac{\left\|u^{*}_{\gamma}-u^{*}_{\lambda}\right\|^{2}}{\left\|u^{*}_{\gamma}\right\|^{2}-\left\|u^{*}_{\lambda}\right\|^{2}}\geq\frac{\left(\left\|u^{*}_{\gamma}\right\|-\left\|u^{*}_{\lambda}\right\|\right)^{2}}{\left\|u^{*}_{\gamma}\right\|^{2}-\left\|u^{*}_{\lambda}\right\|^{2}}\\\
=\frac{\left\|u^{*}_{\gamma}\right\|-\left\|u^{*}_{\lambda}\right\|}{\left\|u^{*}_{\gamma}\right\|+\left\|u^{*}_{\lambda}\right\|}\
.$ (23)

By Lemma 7, since $\lambda\geq\gamma$,
$\left\|u^{*}_{\gamma}\right\|\geq\left\|u^{*}_{\lambda}\right\|$. Therefore,
rearranging this inequality completes the proof. ∎

######  Lemma 11.

Let $X\sim\textrm{Binomial}(C,p)$ with $p\geq\frac{3}{4}$. Then,

$\mathbb{P}\left(X>\frac{C}{2}\right)\geq 1-\exp\left(-\frac{C}{8}\right)\ .$

###### Proof.

This is a simple application of Hoeffding’s inequality:

$\mathbb{P}\left(\frac{1}{C}X\leq\frac{1}{2}\leq
p-\frac{1}{4}\right)\leq\exp\left(-\frac{C}{8}\right)\ .$ (24)

∎

######  Lemma 12.

Let $x\in\mathbb{R}^{d}$ be as input to Algorithm 2, let
$Q_{\lambda^{(i)}}(u)=\frac{1}{2}u^{\top}\left(\delta(5\bar{r})\nabla^{2}F(x)+\lambda^{(i)}\right)u+\nabla
F(x)^{\top}u$, let
$Q_{\lambda^{(i)}}^{*}\coloneqq\min_{u}Q_{\lambda^{(i)}}(u)$, and for each
$i$, let $\tilde{u}^{(i,1)},\dots,\tilde{u}^{(i,C)}$ be computed as in
Algorithm 2 such that

$\mathbb{E}Q_{\lambda^{(i)}}(\tilde{u}^{(i,c)})-Q_{\lambda^{(i)}}^{*}\leq\epsilon(\lambda^{(i)})\leq\frac{\lambda^{(i)}\left(r^{*}(\lambda^{(i)})^{2}+\bar{r}^{2}\right)}{800}\
.$

Then,

$\displaystyle r^{*}(\lambda^{(i)})\in\left[2\bar{r},\,3\bar{r}\right]$
$\displaystyle\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}>\frac{C}{2}\right)\geq
1-\exp\left(-\frac{C}{8}\right)$ $\displaystyle
r^{*}(\lambda^{(i)})\not\in\left[\bar{r},\,4\bar{r}\right]$
$\displaystyle\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}\leq\frac{C}{2}\right)\leq\exp\left(-\frac{C}{8}\right)$
$\displaystyle r^{*}(\lambda^{(i)})<2\bar{r}$
$\displaystyle\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\leq\frac{5}{2}\bar{r}\right\\}>\frac{C}{2}\right)\geq
1-\exp\left(-\frac{C}{8}\right)$ $\displaystyle r^{*}(\lambda^{(i)})>3\bar{r}$
$\displaystyle\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|>\frac{5}{2}\bar{r}\right\\}>\frac{C}{2}\right)\geq
1-\exp\left(-\frac{C}{8}\right)\ .$

###### Proof.

By the $\lambda^{(i)}$-strong convexity of $Q_{\lambda^{(i)}}$, for each $c$,

$\mathbb{E}\left[\frac{\lambda^{(i)}}{2}\|\tilde{u}^{(i,c)}-u^{*}_{\lambda^{(i)}}\|^{2}\right]\leq\mathbb{E}Q_{\lambda^{(i)}}(\tilde{u}^{(i,c)})-Q_{\lambda^{(i)}}^{*}\leq\epsilon(\lambda^{(i)}).$
(25)

Therefore, by Markov’s inequality, for each $c$

$\mathbb{P}\left(\|\tilde{u}^{(i,c)}-u^{*}_{\lambda^{(i)}}\|^{2}\geq\frac{1}{100}r^{*}(\lambda^{(i)})^{2}+\frac{1}{100}\bar{r}^{2}\right)\leq\frac{200\epsilon(\lambda^{(i)})}{\lambda^{(i)}\left(r^{*}(\lambda^{(i)})^{2}+\bar{r}^{2}\right)}\leq\frac{1}{4}\
.$ (26)

Furthermore, by the reverse triangle inequality,

$\left\lvert\|\tilde{u}^{(i,c)}\|-r^{*}(\lambda^{(i)})\right\rvert\leq\|\tilde{u}^{(i,c)}-u^{*}_{\lambda^{(i)}}\|<\sqrt{\frac{1}{100}r^{*}(\lambda^{(i)})^{2}+\frac{1}{100}\bar{r}^{2}}\leq\frac{r^{*}(\lambda^{(i)})+\bar{r}}{10}\
.$ (27)

Therefore, for each $c$

$\mathbb{P}\left(\frac{9}{10}r^{*}(\lambda^{(i)})-\frac{1}{10}\bar{r}\leq\|\tilde{u}^{(i,c)}\|\leq\frac{11}{10}r^{*}(\lambda^{(i)})+\frac{1}{10}\bar{r}\right)\geq\frac{3}{4}\
.$ (28)

We now consider several cases:

If $r^{*}(\lambda^{(i)})\in\left[2\bar{r},\,3\bar{r}\right]$, then

$\displaystyle\mathbb{P}\left(\|\tilde{u}^{(i,c)}\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right)\geq\mathbb{P}\left(\frac{17}{10}\bar{r}\leq\frac{9}{10}r^{*}(\lambda^{(i)})-\frac{1}{10}\bar{r}\leq\|\tilde{u}^{(i,c)}\|\leq\frac{11}{10}r^{*}(\lambda^{(i)})+\frac{1}{10}\bar{r}\leq\frac{34}{10}\bar{r}\right)\geq\frac{3}{4}.$
(29)

Therefore, by Lemma 11

$r^{*}(\lambda^{(i)})\in\left[2\bar{r},\,3\bar{r}\right]\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}>\frac{C}{2}\right)\geq
1-\exp\left(-\frac{C}{8}\right)\ .$ (30)

If $r^{*}(\lambda^{(i)})>4\bar{r}$, then

$\mathbb{P}\left(\|\tilde{u}^{(i,c)}\|\not\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right)\geq\mathbb{P}\left(\frac{7}{2}\bar{r}\leq\frac{9}{10}r^{*}(\lambda^{(i)})-\frac{1}{10}\bar{r}\leq\|\tilde{u}^{(i,c)}\|\right)\geq\frac{3}{4}\
.$ (31)

Similarly, if $r^{*}(\lambda^{(i)})<\bar{r}$, then

$\mathbb{P}\left(\|\tilde{u}^{(i,c)}\|\not\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right)\geq\mathbb{P}\left(\|\tilde{u}^{(i,c)}\|\leq\frac{11}{10}r^{*}(\lambda^{(i)})+\frac{1}{10}\bar{r}\leq\frac{12}{10}\bar{r}\right)\geq\frac{3}{4}\
.$ (32)

Therefore, by Lemma 11,

$r^{*}(\lambda^{(i)})\not\in\left[\bar{r},\,4\bar{r}\right]\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}\leq\frac{C}{2}\right)\leq\exp\left(-\frac{C}{8}\right)\
.$ (33)

If $r^{*}(\lambda^{(i)})<2\bar{r}$, then

$\mathbb{P}\left(\|\tilde{u}^{(i,c)}\|\leq\frac{5}{2}\bar{r}\right)\geq\mathbb{P}\left(\|\tilde{u}^{(i,c)}\|\leq\frac{11}{10}r^{*}(\lambda^{(i)})+\frac{1}{10}\bar{r}\leq\frac{23}{10}\bar{r}\right)\geq\frac{3}{4}\
.$ (34)

Therefore, by Lemma 11

$r^{*}(\lambda^{(i)})<2\bar{r}\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\leq\frac{5}{2}\bar{r}\right\\}>\frac{C}{2}\right)\geq
1-\exp\left(-\frac{C}{8}\right)\ .$ (35)

Finally, if $r^{*}(\lambda^{(i)})>3\bar{r}$, then

$\mathbb{P}\left(\|\tilde{u}^{(i,c)}\|>\frac{5}{2}\bar{r}\right)\geq\mathbb{P}\left(\frac{26}{10}\bar{r}\leq\frac{9}{10}r^{*}(\lambda^{(i)})-\frac{1}{10}\bar{r}\leq\|\tilde{u}^{(i,c)}\|\right)\geq\frac{3}{4}\
.$ (36)

Therefore, by Lemma 11

$r^{*}(\lambda^{(i)})>3\bar{r}\implies\mathbb{P}\left(\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|>\frac{5}{2}\bar{r}\right\\}>\frac{C}{2}\right)\geq
1-\exp\left(-\frac{C}{8}\right)\ .$ (37)

This completes the proof. ∎

######  Lemma 13.

Let $N\geq 1+\frac{5}{2}\log\frac{\|\nabla F(x)\|}{3\bar{r}\bar{\lambda}}$.
Then, either $\bar{\lambda}\geq\lambda_{3\bar{r}}$ or
$\exists\lambda\in\Lambda_{1}$ with
$r^{*}(\lambda)\in\left[2\bar{r},3\bar{r}\right]$.

###### Proof.

In the case that $\bar{\lambda}\leq\lambda_{2\bar{r}}$, by Lemma 8, with
$N\geq 1+\frac{5}{2}\log\frac{\|\nabla F(x)\|}{3\bar{r}\bar{\lambda}}$,

$\bar{\lambda}\leq\lambda_{3\bar{r}}\leq\frac{\|\nabla
F(x)\|}{3\bar{r}}\leq\bar{\lambda}c^{N-1}.$ (38)

So, $\lambda_{3\bar{r}}$ is between the largest and smallest elements in
$\Lambda_{1}$. It follows that for some $1\leq n\leq N$,

$\bar{\lambda}c^{n-1}\leq\lambda_{3\bar{r}}\leq\bar{\lambda}c^{n}.$ (39)

Therefore, by Lemma 10,

$\frac{3}{2}=\frac{\bar{\lambda}\left(\frac{3}{2}\right)^{n}}{\bar{\lambda}\left(\frac{3}{2}\right)^{n-1}}\geq\frac{\bar{\lambda}\left(\frac{3}{2}\right)^{n}}{\lambda_{3\bar{r}}}\geq\frac{3\bar{r}}{r^{*}(\bar{\lambda}\left(\frac{3}{2}\right)^{n})}\implies
r^{*}(\bar{\lambda}\left(\frac{3}{2}\right)^{n})\geq 2\bar{r}$ (40)

Finally, by Lemma 7, $r^{*}(\bar{\lambda}\left(\frac{3}{2}\right)^{n})\leq
3\bar{r}$, so
$r^{*}(\bar{\lambda}\left(\frac{3}{2}\right)^{n})\in[2\bar{r},3\bar{r}]$ as
claimed. ∎

######  Lemma 14.

Let $\lambda$ satisfy $r^{*}(\lambda)\leq 4\bar{r}$ and let $\tilde{u}$ be
chosen so that

$\mathbb{E}Q_{\lambda}(\tilde{u})-Q_{\lambda}^{*}\leq\epsilon(\lambda)\coloneqq\frac{\lambda(r^{*}(\lambda)^{2}+\bar{r}^{2})}{800}\
.$

Then if $r^{*}(\lambda)\geq\bar{r}$,

$\mathbb{E}Q\left(\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\tilde{u}\right)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}\leq\frac{1}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda).$

Otherwise,

$\mathbb{E}Q\left(\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\tilde{u}\right)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}\leq\frac{1}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda)+\frac{\lambda\bar{r}^{2}}{8}\
.$

###### Proof.

First,

$\displaystyle\mathbb{E}$ $\displaystyle Q\left(\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\tilde{u}\right)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)$
$\displaystyle=\mathbb{E}Q\left(\left(1-\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\right)0+\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\tilde{u}\right)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)$
(41) $\displaystyle\leq\mathbb{E}\left[\left(1-\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\right)\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\left(Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)\right]$
(42)
$\displaystyle\leq\mathbb{E}\left[\frac{\|\tilde{u}\|}{\|\tilde{u}\|+5\bar{r}}\right]\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)$
(43)
$\displaystyle\leq\frac{\mathbb{E}\|\tilde{u}\|}{\mathbb{E}\|\tilde{u}\|+5\bar{r}}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u).$
(44)

For the first inequality we used the convexity of $Q$, and for the final
inequality we used Jensen’s inequality on the concave function
$x\mapsto\frac{x}{x+5\bar{r}}$. Next, we bound

$\displaystyle\mathbb{E}\|\tilde{u}\|$ $\displaystyle\leq
r^{*}(\lambda)+\mathbb{E}\|\tilde{u}-u^{*}_{\lambda}\|$ (45)
$\displaystyle\leq
4\bar{r}+\sqrt{\mathbb{E}\|\tilde{u}-u^{*}_{\lambda}\|^{2}}$ (46)
$\displaystyle\leq
4\bar{r}+\sqrt{\frac{2}{\lambda}\mathbb{E}Q_{\lambda}(\tilde{u})-Q_{\lambda}^{*}}$
(47) $\displaystyle\leq 4\bar{r}+\sqrt{\frac{2\epsilon(\lambda)}{\lambda}}$
(48) $\displaystyle\leq
4\bar{r}+\sqrt{\frac{r^{*}(\lambda)^{2}+\bar{r}^{2}}{400}}$ (49)
$\displaystyle\leq 4\bar{r}+\sqrt{\frac{17\bar{r}^{2}}{400}}$ (50)
$\displaystyle<5\bar{r}.$ (51)

Therefore,

$\mathbb{E}Q\left(\min\left\\{1,\
\frac{5\bar{r}}{\|\tilde{u}\|}\right\\}\tilde{u}\right)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\frac{1}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u).$
(52)

If $r^{*}(\lambda)\geq\bar{r}$, then by the first part of Lemma 9

$\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}r^{*}(\lambda)}Q(u)\leq\epsilon(\lambda).$
(53)

Otherwise, by the second part of Lemma 9

$\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)=\mathbb{E}Q(\tilde{u})-Q(u^{*}_{\lambda_{\frac{1}{2}\bar{r}}})\leq\epsilon(\lambda)+\frac{\lambda\|u^{*}_{\lambda_{\frac{1}{2}\bar{r}}}\|^{2}}{2}=\epsilon(\lambda)+\frac{\lambda\bar{r}^{2}}{8}\
.$ (54)

∎

We are now ready to prove Lemma 3. See 3

###### Proof.

First, we note that $\left\lvert\Lambda_{1}\right\rvert=N$, and in each
iteration either the algorithm terminates or $\Lambda_{i+1}$ is chosen such
that
$\left\lvert\Lambda_{i+1}\right\rvert\leq\frac{1}{2}\left\lvert\Lambda_{i}\right\rvert$.
Therefore, the algorithm terminates after at most $\lceil\log_{2}N\rceil$
iterations.

By Lemma 13, either $\bar{\lambda}\geq\lambda_{3\bar{r}}$ or there exists
$\lambda\in\Lambda_{1}$ for some $\lambda$ such that
$r^{*}(\lambda)\in\left[2\bar{r},3\bar{r}\right]$. If such a $\lambda$ exists,
we denote this (not necessarily unique) value $\lambda^{*}$.

By Lemma 12 and the union bound, the following holds for all iteration
$i=1,2,\dots$ with probability at least
$1-2\lceil\log_{2}N\rceil\exp\left(-\frac{C}{8}\right)$:

$\displaystyle r^{*}(\lambda^{(i)})\in\left[2\bar{r},\,3\bar{r}\right]$
$\displaystyle\implies\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}>\frac{C}{2}$
(55) $\displaystyle
r^{*}(\lambda^{(i)})\not\in\left[\bar{r},\,4\bar{r}\right]$
$\displaystyle\implies\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}\leq\frac{C}{2}$
(56) $\displaystyle r^{*}(\lambda^{(i)})<2\bar{r}$
$\displaystyle\implies\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\leq\frac{5}{2}\bar{r}\right\\}>\frac{C}{2}$
(57) $\displaystyle r^{*}(\lambda^{(i)})>3\bar{r}$
$\displaystyle\implies\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|>\frac{5}{2}\bar{r}\right\\}>\frac{C}{2}\
.$ (58)

For most of the rest of the proof, we condition on this event, which we denote
$E$.

Under $E$, if $\lambda^{(i)}=\lambda^{*}$, then the algorithm will terminate
on Line 10, and even if $\lambda^{(i)}\neq\lambda^{*}$, if the algorithm
terminates on Line 10, then $\lambda^{(i)}\in\left[\bar{r},4\bar{r}\right]$.
In either case, by the first part of Lemma 14

$\mathbb{E}Q(\hat{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\frac{1}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda^{(i)}).$
(59)

Finally, since $r^{*}(\lambda^{(i)})\leq 4\bar{r}$,
$\lambda^{(i)}\geq\lambda_{4\bar{r}}$.

If the algorithm instead updates

$\Lambda_{i+1}=\Lambda_{i}\setminus\left\\{\lambda\in\Lambda_{i}\,:\,\lambda\geq\lambda^{(i)}\right\\}$
(60)

as on Line 12, then conditioned on $E$,

$\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}\leq\frac{C}{2}<\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\leq\frac{5}{2}\bar{r}\right\\}$
(61)

implies $\lambda^{(i)}<2\bar{r}$. By Lemma 7, since $r^{*}(\lambda^{*})\geq
2\bar{r}>r^{*}(\lambda^{(i)})$, $\lambda^{*}<\lambda^{(i)}$ and therefore
$\lambda^{*}\in\Lambda_{i+1}$.

If the algorithm instead updates

$\Lambda_{i+1}=\Lambda_{i}\setminus\left\\{\lambda\in\Lambda_{i}\,:\,\lambda\leq\lambda^{(i)}\right\\}$
(62)

as on Line 14, then conditioned on $E$

$\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|\in\left[\frac{3}{2}\bar{r},\,\frac{7}{2}\bar{r}\right]\right\\}\leq\frac{C}{2}<\sum_{c=1}^{C}\mathbbm{1}\left\\{\left\|\tilde{u}^{(i,c)}\right\|>\frac{5}{2}\bar{r}\right\\}$
(63)

implies $\lambda^{(i)}>3\bar{r}$. By Lemma 7, since $r^{*}(\lambda^{*})\leq
3\bar{r}<r^{*}(\lambda^{(i)})$, we have $\lambda^{*}>\lambda^{(i)}$, and
therefore $\lambda^{*}\in\Lambda_{i+1}$.

Finally, $E$ implies that the algorithm will never reach Line 16.

Therefore, conditioned on $E$, if $\lambda^{*}\in\Lambda_{1}$, then the
algorithm will never remove $\lambda^{*}$ from the set of $\lambda$’s under
consideration, and it will eventually terminate on Line 10 by returning a
point such that

$\mathbb{E}Q(\hat{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\frac{1}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda^{(i)}).$
(64)

Otherwise, if such a $\lambda^{*}$ does not exist and the algorithm does not
terminate on Line 10, then it terminates on Line 19 using
$\bar{\lambda}\geq\lambda_{3\bar{r}}\geq\lambda_{4\bar{r}}$, which implies
$r^{*}(\bar{\lambda})\leq 4\bar{r}$. Therefore, by the second part of Lemma
14,

$\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\frac{1}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\bar{\lambda})+\frac{\bar{\lambda}\bar{r}^{2}}{8}\
.$ (65)

Therefore since $\epsilon(\lambda)$ is decreasing in $\lambda$, conditioned on
$E$ the algorithm’s output satisfies

$\mathbb{E}Q(\tilde{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\frac{1}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda_{4\bar{r}})+\frac{\bar{\lambda}\bar{r}^{2}}{8}\
.$ (66)

We now consider the case that $E$ does not hold. In this case, the algorithm’s
output is guaranteed to have norm at most $5\bar{r}$. Therefore,

$\displaystyle
Q(\hat{u})=\frac{\delta(5\bar{r})}{2}\hat{u}^{\top}\nabla^{2}F(x)\hat{u}+\nabla
F(x)^{\top}\hat{u}$
$\displaystyle\leq\frac{25\delta(5\bar{r})\|\nabla^{2}F(x)\|_{2}\bar{r}^{2}}{2}+5\bar{r}\|\nabla
F(x)\|$ (67)
$\displaystyle=Q(0)+\frac{25\delta(5\bar{r})\|\nabla^{2}F(x)\|_{2}\bar{r}^{2}}{2}+5\bar{r}\|\nabla
F(x)\|.$ (68)

Therefore, conditioned on $\lnot E$,

$Q(\hat{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq
Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)+\frac{25\delta(5\bar{r})\|\nabla^{2}F(x)\|_{2}\bar{r}^{2}}{2}+5\bar{r}\|\nabla
F(x)\|.$ (69)

We conclude by noting that

$\displaystyle\mathbb{E}Q(\hat{u})$
$\displaystyle-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)$
$\displaystyle=\mathbb{E}\left[Q(\hat{u})\,|\,E\right]\mathbb{P}(E)+\mathbb{E}\left[Q(\hat{u})\,|\,\lnot
E\right]\mathbb{P}(\lnot E)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)$ (70)
$\displaystyle\leq\frac{1+\mathbb{P}(\lnot
E)}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda_{4\bar{r}})+\frac{\bar{\lambda}\bar{r}^{2}}{8}$
(71)
$\displaystyle\qquad+\left(\frac{25\delta(5\bar{r})\|\nabla^{2}F(x)\|_{2}\bar{r}^{2}}{2}+5\bar{r}\|\nabla
F(x)\|\right)\mathbb{P}(\lnot E)$ (72)
$\displaystyle\leq\frac{1+2\lceil\log_{2}N\rceil\exp\left(-\frac{C}{8}\right)}{2}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda_{4\bar{r}})+\frac{\bar{\lambda}\bar{r}^{2}}{8}$
$\displaystyle\qquad+\left(\frac{25\delta(5\bar{r})\|\nabla^{2}F(x)\|_{2}\bar{r}^{2}}{2}+5\bar{r}\|\nabla
F(x)\|\right)\cdot 2\lceil\log_{2}N\rceil\exp\left(-\frac{C}{8}\right)$ (73)

Using the fact that

$C\geq
8\log\left(\lceil\log_{2}N\rceil\left(4+\frac{8\delta(5\bar{r})\|\nabla^{2}F(x)\|_{2}}{\bar{\lambda}}+\frac{80\|\nabla
F(x)\|}{\bar{\lambda}\bar{r}}\right)\right)$ (74)

we conclude

$\mathbb{E}Q(\hat{u})-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\leq\frac{3}{4}\left(Q(0)-\min_{u:\|u\|\leq\frac{1}{2}\bar{r}}Q(u)\right)+\epsilon(\lambda_{4\bar{r}})+\frac{\bar{\lambda}\bar{r}^{2}}{4}\
.$ (75)

This completes the proof. ∎

##  Appendix C Proof of Lemma 4

See 4

###### Proof.

We will use $\bar{u}_{k}=\frac{1}{M}\sum_{m=1}^{M}u_{k}^{m}$ to denote the
average of each independent run of SGD’s $k^{\textrm{th}}$ iterate. This
quantity is never explicitly computed until the end, but we can nevertheless
use it for our analysis. Likewise, we will use
$\bar{\gamma}_{k}=\frac{1}{M}\sum_{m=1}^{M}\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{{}^{\prime}m})$
to denote the average of the stochastic gradients of $Q_{\lambda}(u)$ computed
at time $k$, whereby we recall that
$\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{{}^{\prime}m})\coloneqq\bar{\xi}h(x,u_{k}^{m};z_{k}^{{}^{\prime}m})+\lambda
u_{k}^{m}+g(x;z_{k}^{m})$ as defined in Algorithm 3, along with the requisite
oracle access as described in Algorithm 4.

We also have that, by Assumptions 1(c) and 2(b), for Case 1:

$\mathbb{E}_{z_{k}^{m},z_{k}^{{}^{\prime}m}}[\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{{}^{\prime}m})]=\nabla
Q_{\lambda}(u)\ \textrm{and}\
\mathbb{E}_{z_{k}^{m},z_{k}^{{}^{\prime}m}}\left\|\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{{}^{\prime}m})-\nabla
Q_{\lambda}(u_{k}^{m})\right\|^{2}\leq\sigma^{2}+\rho^{2}\left\|u_{k}^{m}\right\|^{2},$

while for Case 2 we have:

$\mathbb{E}_{z_{k}^{m}}[\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{m})]=\nabla
Q_{\lambda}(u)\ \textrm{and}\
\mathbb{E}_{z_{k}^{m}}\left\|\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{m})-\nabla
Q_{\lambda}(u_{k}^{m})\right\|^{2}\leq
2\sigma^{2}+2\rho^{2}\left\|u_{k}^{m}\right\|^{2},$

where we used the fact that $\left\|a+b\right\|^{2}\leq
2\left\|a\right\|^{2}+2\left\|b\right\|^{2}$ for any $a,b\in\mathbb{R}^{d}$,
and so in either case the variance term is bounded by
$2\sigma^{2}+2\rho^{2}\left\|u_{k}^{m}\right\|^{2}$.

A key feature of these stochastic gradients of $Q_{\lambda}(u)$, which we will
use frequently, is that by the linearity of $\nabla
Q_{\lambda}(u)=(\bar{\xi}\nabla^{2}F(x)+\lambda\mathbf{I})u+\nabla F(x)$,

$\mathbb{E}\bar{\gamma}_{k}=\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}\gamma(u_{k}^{m};z_{k}^{m},z_{k}^{{}^{\prime}m})=\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}\nabla
Q_{\lambda}(u_{k}^{m})=\nabla Q_{\lambda}(\mathbb{E}\bar{u}_{k}).$ (76)

We begin by expanding,

$\displaystyle\mathbb{E}$
$\displaystyle\left\|\bar{u}_{k+1}-u^{*}\right\|^{2}$
$\displaystyle=\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}+\eta_{k}^{2}\mathbb{E}\left\|\bar{\gamma}_{k}\right\|^{2}-2\eta_{k}\mathbb{E}\left\langle\nabla
Q_{\lambda}(\bar{u}_{k}),\,\bar{u}_{k}-u^{*}\right\rangle$ (77)
$\displaystyle=\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}+\eta_{k}^{2}\mathbb{E}\left\|\nabla
Q_{\lambda}(\bar{u}_{k})\right\|^{2}-2\eta_{k}\left[Q_{\lambda}(\bar{u}_{k})-Q_{\lambda}^{*}+\frac{\lambda}{2}\left\|\bar{u}_{k}-u^{*}\right\|^{2}\right]+\eta_{k}^{2}\mathbb{E}\left\|\bar{\gamma}_{k}-\nabla
Q_{\lambda}(\bar{u}_{k})\right\|^{2}$ (78)
$\displaystyle\leq(1-\eta_{k}\lambda)\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}-2\eta_{k}(1-(\bar{\xi}H+\lambda)\eta_{k})\mathbb{E}\left[Q_{\lambda}(\bar{u}_{k})-Q_{\lambda}^{*}\right]+\eta_{k}^{2}\left(\frac{2\sigma^{2}}{M}+\frac{2\rho^{2}}{M^{2}}\sum_{m=1}^{M}\mathbb{E}\left\|u_{k}^{m}\right\|^{2}\right).$
(79)

Since $\eta_{k}\leq\frac{1}{2(\bar{\xi}H+\lambda)}$ for all $k$,
$(1-(\bar{\xi}H+\lambda)\eta_{k})\geq\frac{1}{2}$ so we can rearrange

$\displaystyle\mathbb{E}\left[Q_{\lambda}(\bar{u}_{k})-Q_{\lambda}^{*}\right]\leq\left(\frac{1}{\eta_{k}}-\lambda\right)\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}-\frac{1}{\eta_{k}}\mathbb{E}\left\|\bar{u}_{k+1}-u^{*}\right\|^{2}+\eta_{k}\left(\frac{2\sigma^{2}}{M}+\frac{2\rho^{2}}{M^{2}}\sum_{m=1}^{M}\mathbb{E}\left\|u_{k}^{m}\right\|^{2}\right).$
(80)

From here, we note that since $u_{k}^{1},\dots,u_{k}^{M}$ are i.i.d.,

$\displaystyle\frac{1}{M^{2}}\sum_{m=1}^{M}\mathbb{E}\left\|u_{k}^{m}\right\|^{2}$
$\displaystyle=\frac{1}{M^{2}}\sum_{m=1}^{M}\left[\mathbb{E}\left\|u_{k}^{m}-\mathbb{E}u_{k}^{m}\right\|^{2}+\left\|\mathbb{E}u_{k}^{m}\right\|^{2}\right]$
(81)
$\displaystyle=\mathbb{E}\left\|\bar{u}_{k}^{m}-\mathbb{E}\bar{u}_{k}^{m}\right\|^{2}+\frac{1}{M}\left\|\mathbb{E}\bar{u}_{k}\right\|^{2}$
(82)
$\displaystyle\leq\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}+\frac{1}{M}\left\|\mathbb{E}\bar{u}_{k}\right\|^{2}$
(83)
$\displaystyle\leq\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}+\frac{2}{M}\left\|\mathbb{E}\bar{u}_{k}-u^{*}\right\|^{2}+\frac{2}{M}\left\|u^{*}\right\|^{2}.$
(84)

Furthermore, for each $k$, since $\eta_{k-1}\leq\frac{1}{\bar{\xi}H+\lambda}$

$\displaystyle\left\|\mathbb{E}\bar{u}_{k}-u^{*}\right\|^{2}$
$\displaystyle\leq\left\|\mathbb{E}\bar{u}_{k-1}-u^{*}\right\|^{2}+\eta_{k-1}^{2}\left\|\nabla
Q_{\lambda}(\mathbb{E}\bar{u}_{k-1})\right\|^{2}-2\eta_{k-1}\left\langle\nabla
Q_{\lambda}(\mathbb{E}\bar{u}_{k-1}),\,\bar{u}_{k-1}-u^{*}\right\rangle$ (85)
$\displaystyle\leq\left\|\mathbb{E}\bar{u}_{k-1}-u^{*}\right\|^{2}+2(\bar{\xi}H+\lambda)\eta_{k-1}^{2}\left[Q_{\lambda}(\mathbb{E}\bar{u}_{k-1})-Q_{\lambda}^{*}\right]-2\eta_{k-1}\left[Q_{\lambda}(\mathbb{E}\bar{u}_{k-1})-Q_{\lambda}^{*}\right]$
(86)
$\displaystyle\leq\left\|\mathbb{E}\bar{u}_{k-1}-u^{*}\right\|^{2}\leq\left\|\mathbb{E}\bar{u}_{0}-u^{*}\right\|^{2}=\|u^{*}\|^{2}.$
(87)

Therefore, returning to (80),

$\displaystyle\mathbb{E}\left[Q_{\lambda}(\bar{u}_{k})-Q_{\lambda}^{*}\right]$
$\displaystyle\leq\left(\frac{1}{\eta_{k}}-\lambda\right)\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}-\frac{1}{\eta_{k}}\mathbb{E}\left\|\bar{u}_{k+1}-u^{*}\right\|^{2}+\frac{2\eta_{k}\sigma^{2}}{M}+2\eta_{k}\rho^{2}\left(\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}+\frac{4}{M}\left\|u^{*}\right\|^{2}\right)$
(88)
$\displaystyle=\left(\frac{1}{\eta_{k}}-\lambda+\eta_{k}\rho^{2}\right)\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}-\frac{1}{\eta_{k}}\mathbb{E}\left\|\bar{u}_{k+1}-u^{*}\right\|^{2}+\frac{2\eta_{k}\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}\
.$ (89)

We first consider the case
$K\leq\frac{2\max\left\\{\bar{\xi}H+\lambda,\frac{\rho^{2}}{\lambda}\right\\}}{\lambda}$,
so that

$\eta_{k}=\eta=\min\left\\{\frac{1}{2(\bar{\xi}H+\lambda)},\
\frac{\lambda}{2\rho^{2}}\right\\}\quad\textrm{ and }\quad
w_{k}=(1-\lambda\eta+\eta^{2}\rho^{2})^{-k-1}.$

Then,

$\displaystyle\mathbb{E}$ $\displaystyle
Q_{\lambda}\left(\frac{1}{\sum_{k=0}^{K}w_{k}}\sum_{k=0}^{K}w_{k}\bar{u}_{k}\right)-Q_{\lambda}^{*}$
$\displaystyle\leq\frac{1}{\eta\sum_{k=0}^{K}w_{k}}\sum_{k=0}^{K}\left[w_{k}\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}-w_{k}\mathbb{E}\left\|\bar{u}_{k+1}-u^{*}\right\|^{2}\right]+\frac{2\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}$
(90)
$\displaystyle=\frac{1}{\eta\sum_{k=0}^{K}w_{k}}\sum_{k=0}^{K}\left[\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{-k}\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}-\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{-(k+1)}\mathbb{E}\left\|\bar{u}_{k+1}-u^{*}\right\|^{2}\right]$
(91)
$\displaystyle\qquad+\frac{2\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}$
(92)
$\displaystyle\leq\frac{\mathbb{E}\left\|\bar{u}_{0}-u^{*}\right\|^{2}}{\eta\sum_{k=0}^{K}\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{-(k+1)}}+\frac{2\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}$
(93)
$\displaystyle\leq\frac{\left\|u^{*}\right\|^{2}}{\eta\max\left\\{K,\,\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{-(K+1)}\right\\}}+\frac{2\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}$
(94) $\displaystyle\leq
2\max\left\\{\bar{\xi}H+\lambda,\frac{\rho^{2}}{\lambda}\right\\}\left\|u^{*}\right\|^{2}\min\left\\{\frac{1}{K},\,\exp\left(-\frac{K+1}{4}\min\left\\{\frac{\lambda}{\bar{\xi}H+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)^{K+1}\right\\}$
$\displaystyle\qquad\qquad+\frac{2(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda
MK}\ .$ (95)

For the last line, we used that
$K\leq\frac{2\max\left\\{\bar{\xi}H+\lambda,\frac{\rho^{2}}{\lambda}\right\\}}{\lambda}=\frac{1}{\eta\lambda}$.

In the second case
$\left(K>\frac{2\max\left\\{\bar{\xi}H+\lambda,\frac{\rho^{2}}{\lambda}\right\\}}{\lambda}\right)$,
we consider the first $K/2$ iterations where

$\eta_{k}=\eta=\min\left\\{\frac{1}{2(\bar{\xi}H+\lambda)},\frac{\lambda}{2\rho^{2}}\right\\}:$
$\displaystyle\mathbb{E}Q_{\lambda}(\bar{u}_{K/2-1})-Q_{\lambda}^{*}$
$\displaystyle\leq\left(\frac{1}{\eta}-\lambda+\eta\rho^{2}\right)\mathbb{E}\left\|\bar{u}_{K/2-1}-u^{*}\right\|^{2}-\frac{1}{\eta}\mathbb{E}\left\|\bar{u}_{K/2}-u^{*}\right\|^{2}+\frac{2\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}$
(96) $\displaystyle\implies\mathbb{E}\left\|\bar{u}_{K/2}-u^{*}\right\|^{2}$
$\displaystyle\leq\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)\mathbb{E}\left\|\bar{u}_{K/2-1}-u^{*}\right\|^{2}+\frac{2\eta^{2}\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}$
(97)
$\displaystyle=\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{K/2}\mathbb{E}\left\|\bar{u}_{0}-u^{*}\right\|^{2}+\frac{2\eta^{2}\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}\sum_{k=0}^{K/2-1}\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{k}$
(98)
$\displaystyle=\left\|u^{*}\right\|^{2}\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{K/2}+\frac{2\eta^{2}\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}\frac{1-\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{K/2}}{\eta\lambda-\eta^{2}\rho^{2}}$
(99)
$\displaystyle\leq\left\|u^{*}\right\|^{2}\left(1-\eta\lambda+\eta^{2}\rho^{2}\right)^{K/2}+\frac{2\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M(\lambda-\eta\rho^{2})}$
(100)
$\displaystyle\leq\left\|u^{*}\right\|^{2}\left(1-\frac{1}{2}\eta\lambda\right)^{K/2}+\frac{4\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{\lambda
M}\ .$ (101)

This bounds the distance of the $(K/2)^{\textrm{th}}$ iterate to the optimum,
from which we can upper bound the suboptimality of the averaged iterate. Let
$W=\sum_{k=0}^{K}w_{k}=\sum_{k=K/2}^{K}w_{k}$. Then by the convexity of
$Q_{\lambda}(u)$,

$\displaystyle\mathbb{E}$ $\displaystyle
Q_{\lambda}\left(\frac{1}{W}\sum_{k=0}^{K}w_{k}\bar{u}_{k}\right)-Q_{\lambda}^{*}$
$\displaystyle\leq\frac{1}{W}\sum_{k=0}^{K}\left[w_{k}\left(\frac{1}{\eta_{k}}-\lambda+\eta_{k}\rho^{2}\right)\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}-\frac{w_{k}}{\eta_{k}}\mathbb{E}\left\|\bar{u}_{k+1}-u^{*}\right\|^{2}+\frac{2w_{k}\eta_{k}\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}\right]$
(102)
$\displaystyle\leq\frac{w_{K/2}\left(\frac{1}{\eta_{K/2}}-\lambda+\eta_{K/2}\rho^{2}\right)\mathbb{E}\left\|\bar{u}_{K/2}-u^{*}\right\|^{2}}{W}$
$\displaystyle\qquad\qquad+\frac{1}{W}\sum_{k=K/2+1}^{K}\left[\left(\frac{w_{k}}{\eta_{k}}-w_{k}\lambda+w_{k}\eta_{k}\rho^{2}-\frac{w_{k-1}}{\eta_{k-1}}\right)\mathbb{E}\left\|\bar{u}_{k}-u^{*}\right\|^{2}+\frac{2w_{k}\eta_{k}\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}\right]\
.$ (103)

With our setting of $w_{k}=(a+k-K/2-1)$ and
$\eta_{k}=\frac{4}{\lambda(a+k-K/2)}$ with
$a=\frac{8}{\lambda}\max\left\\{\frac{\rho^{2}}{\lambda},\
\bar{\xi}H+\lambda\right\\}$, we have for $k>K/2$,

$\displaystyle\frac{\eta_{k-1}}{\eta_{k}}-\eta_{k-1}\lambda+\eta_{k-1}\eta_{k}\rho^{2}$
$\displaystyle=\frac{a+k-K/2}{a+k-K/2-1}-\frac{4}{a+k-K/2-1}+\frac{16\rho^{2}}{\lambda^{2}(a+k-K/2)(a+k-K/2-1)}$
(104)
$\displaystyle=\frac{a+k-K/2}{a+k-K/2-1}+\frac{1}{a+k-K/2-1}\left(2-4+\frac{16\rho^{2}}{\lambda^{2}(a+k-K/2)}\right)$
(105)
$\displaystyle\leq\frac{w_{k-1}}{w_{k}}+\frac{1}{a+k-K/2-1}\left(-2+\frac{16\rho^{2}}{\lambda^{2}a}\right)$
(106) $\displaystyle\leq\frac{w_{k-1}}{w_{k}}\ .$ (107)

Therefore, we have

$\displaystyle\mathbb{E}Q_{\lambda}(\hat{x})$ $\displaystyle-Q_{\lambda}^{*}$
$\displaystyle\leq\frac{w_{K/2}\left(\frac{1}{\eta_{K/2}}-\lambda+\eta_{K/2}\rho^{2}\right)\mathbb{E}\left\|\bar{u}_{K/2}-u^{*}\right\|^{2}}{W}+\frac{2}{W}\sum_{k=K/2+1}^{K}\frac{w_{k}\eta_{k}\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{M}$
(108) $\displaystyle=\frac{(a-1)\left(\frac{\lambda
a}{4}-\lambda+\frac{4\rho^{2}}{\lambda
a}\right)\mathbb{E}\left\|\bar{u}_{K/2}-u^{*}\right\|^{2}}{W}+\frac{2(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{WM}\sum_{k=K/2+1}^{K}\frac{4(a+k-K/2-1)}{\lambda(a+k-K/2)}$
(109) $\displaystyle\leq\frac{\lambda
a^{2}\mathbb{E}\left\|\bar{u}_{K/2}-u^{*}\right\|^{2}}{4W}+\frac{8K(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda
WM}$ (110) $\displaystyle\leq\frac{\lambda
a^{2}}{4W}\left(\left\|u^{*}\right\|^{2}\left(1-\frac{1}{2}\eta\lambda\right)^{K/2}+\frac{4\eta\left(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2}\right)}{\lambda
M}\right)+\frac{8K(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda WM}$
(111) $\displaystyle=\frac{\lambda
a^{2}\left\|u^{*}\right\|^{2}}{4W}\left(1-\frac{1}{2}\eta\lambda\right)^{K/2}+\frac{(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda
WM}\left(8K+\eta\lambda a^{2}\right)$ (112) $\displaystyle=\frac{\lambda
a^{2}\left\|u^{*}\right\|^{2}}{4W}\left(1-\min\left\\{\frac{\lambda}{4(\bar{\xi}H+\lambda)},\
\frac{\lambda^{2}}{4\rho^{2}}\right\\}\right)^{K/2}+\frac{\left(8K+4a\right)(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda
WM}\ ,$ (113)

where, for the third-to-last line we used (101), and the last line we used
that $\eta=\min\left\\{\frac{1}{2(\bar{\xi}H+\lambda)},\
\frac{\lambda}{2\rho^{2}}\right\\}=\frac{4}{\lambda a}$. Finally, we lower
bound

$W=\sum_{k=K/2}^{K}(a+k-K/2)=\sum_{i=0}^{K/2}a+i\geq\frac{1}{2}aK+\frac{1}{8}K^{2}.$
(114)

Thus, since $K\geq\frac{2}{\lambda}\max\left\\{\frac{\rho^{2}}{\lambda},\
\bar{\xi}H+\lambda\right\\}=\frac{a}{4}$, we conclude

$\displaystyle\mathbb{E}Q_{\lambda}(\hat{x})-Q_{\lambda}^{*}$
$\displaystyle\leq
96\lambda\left\|u^{*}\right\|^{2}\left(1-\min\left\\{\frac{\lambda}{4(\bar{\xi}H+\lambda)},\
\frac{\lambda^{2}}{4\rho^{2}}\right\\}\right)^{K/2}+\frac{96(\sigma^{2}+\rho^{2}\left\|u^{*}\right\|^{2})}{\lambda
MK}\ .$ (115)

Combining this and (95) completes the proof. ∎

##  Appendix D Proof of Theorem 1

See 1

###### Proof.

We first recall the hyperparameters from Table 2, whose settings we will refer
to throughout the course of the proof:

Hyperparameter Setting | Description
---|---
$T\coloneqq\Bigg{\lfloor}\frac{R}{4\zeta}\log^{2}\left(\left(\frac{R}{\zeta}\right)\right)\Bigg{\rfloor}$ (for $\zeta=4096+4\left(80+32\log K+24\log(1+2\alpha B)\right)^{2}$) | Main iterations
$\beta:=0$ | Momentum
$\bar{r}\coloneqq\min\left\\{\frac{32B}{T}\log(TK),\,\frac{1}{5\alpha}\right\\}$ | Trust-region radius
$\bar{\xi}\coloneqq\exp(\alpha\bar{r})$ | Local stability
$\bar{\lambda}\coloneqq\max\left\\{\frac{2eH}{K-2},\,\frac{2\rho}{\sqrt{K}},\,\frac{32eH\log(51200)}{K},\,\frac{4\rho\sqrt{2\log(51200)}}{\sqrt{K}},\,\frac{320\sqrt{2}\rho}{\sqrt{MK}},\,\frac{320\sigma}{\bar{r}\sqrt{MK}},\,\frac{8eH}{K-16}\right\\}$ | Regularization bound
$N\coloneqq\left\lceil 1+\frac{5}{2}\log\frac{H(B+5T\bar{r})}{3\bar{\lambda}\bar{r}}\right\rceil$ | Binary search iterations
$C\coloneqq\left\lceil 8\log\left(\lceil\log_{2}N\rceil\left(4+\frac{eH}{\bar{\lambda}}+\frac{80H(B+5T\bar{r})}{\bar{\lambda}\bar{r}}\right)\right)\right\rceil$ | Reg. quadratic repetitions

We also note that since all of the updates $\Delta\tilde{x}_{t}$ have norm at
most $5\bar{r}$, $\|x_{t}-x^{*}\|\leq B+5T\bar{r}$ for all $t$, and therefore
by the $H$-smoothness of $F$, $\|\nabla F(x_{t})\|\leq H(B+5T\bar{r})$ for all
$t$. Furthermore, since $F$ is $H$-smooth and $\bar{r}\leq\frac{1}{5\alpha}$,
$\bar{\xi}\nabla^{2}F(x_{t})\preceq eH\mathbf{I}$ for all $t$. Therefore, our
settings of $N$ and $C$ satisfy the conditions of Lemma 3, and for each $t$,

$\mathbb{E}Q_{t}(\Delta\tilde{x}_{t})-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}\bar{r}}Q_{t}(\Delta
x)\leq\frac{3}{4}\left(Q_{t}(0)-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}\bar{r}}Q_{t}(\Delta
x)\right)+\epsilon(\lambda_{4\bar{r}})+\frac{\bar{\lambda}\bar{r}^{2}}{4}$
(116)

as long as the error guarantee of Algorithm 3 satisfies for all
$\lambda\geq\bar{\lambda}$

$\mathbb{E}Q_{\lambda}(\hat{u})-\min_{u}Q_{\lambda}(u)\leq\epsilon(\lambda)=\frac{\lambda(r^{*}(\lambda)^{2}+\bar{r}^{2})}{800}\
.$ (117)

By Lemma 4, since the objectives are such that
$\left\|\bar{\xi}\nabla^{2}F(x_{t})+\lambda\mathbf{I}\right\|_{2}\leq
eH+\lambda$ for all $t$ and $\lambda$, the output with optimally chosen
stepsizes have error at most

$\displaystyle\mathbb{E}Q_{\lambda}(\hat{u})-\min_{u}Q_{\lambda}(u)\leq\tilde{\epsilon}(\lambda)$
(118)
$\displaystyle\coloneqq\begin{cases}2\max\left\\{eH+\lambda,\frac{\rho^{2}}{\lambda}\right\\}r^{*}(\lambda)^{2}\exp\left(-\frac{K+1}{4}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)+\frac{2(\sigma^{2}+\rho^{2}r^{*}(\lambda)^{2})}{\lambda
MK}&K\leq\frac{2}{\lambda}\max\left\\{eH+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\\\
96\lambda
r^{*}(\lambda)^{2}\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)+\frac{96(\sigma^{2}+\rho^{2}r^{*}(\lambda)^{2})}{\lambda
MK}&K>\frac{2}{\lambda}\max\left\\{eH+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\
.\end{cases}$ (119)

With our choice of

$\bar{\lambda}=\max\left\\{\frac{2eH}{K-2},\,\frac{2\rho}{\sqrt{K}},\,\frac{32eH\log(51200)}{K},\,\frac{4\rho\sqrt{2\log(51200)}}{\sqrt{K}},\,\frac{320\sqrt{2}\rho}{\sqrt{MK}},\,\frac{320\sigma}{\bar{r}\sqrt{MK}},\,\frac{8eH}{K-16}\right\\}\
,$ (120)

we note that

$K\geq\frac{2}{\lambda}\max\left\\{eH+\lambda,\,\frac{\rho^{2}}{\lambda}\right\\}\
,$ (121)

so for $\lambda\geq\bar{\lambda}$

$\tilde{\epsilon}(\lambda)\leq 96\lambda
r^{*}(\lambda)^{2}\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)+\frac{96(\sigma^{2}+\rho^{2}r^{*}(\lambda)^{2})}{\lambda
MK}\ .$ (122)

Furthermore, $K\geq 175$ and
$\lambda\geq\bar{\lambda}\geq\max\left\\{\frac{32eH\log(51200)}{K},\,\frac{4\rho\sqrt{2\log(51200)}}{\sqrt{K}}\right\\}$
implies

$96\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)\leq\frac{1}{1600}\ .$ (123)

Likewise, $\lambda\geq\bar{\lambda}\geq\frac{320\sqrt{2}\rho}{\sqrt{MK}}$
implies

$\frac{96\rho^{2}}{\lambda^{2}MK}\leq\frac{1}{1600}\ .$ (124)

Finally, $\lambda\geq\bar{\lambda}\geq\frac{320\sigma}{\bar{r}\sqrt{MK}}$
implies

$\frac{96\sigma^{2}}{\lambda^{2}MK}\leq\frac{\bar{r}^{2}}{800}\ .$ (125)

Putting these together, we conclude that for $\lambda\geq\bar{\lambda}$

$\tilde{\epsilon}(\lambda)\leq\frac{\lambda(r^{*}(\lambda)^{2}+\bar{r}^{2})}{800}=\epsilon(\lambda).$
(126)

Combining this with (116), we conclude that the output of Algorithm 2
satisfies

$\displaystyle\mathbb{E}$ $\displaystyle
Q_{t}(\Delta\tilde{x}_{t})-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}\bar{r}}Q_{t}(\Delta x)$
$\displaystyle\leq\frac{3}{4}\left(Q_{t}(0)-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}\bar{r}}Q_{t}(\Delta x)\right)$
$\displaystyle\qquad+512\lambda\bar{r}^{2}\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)+\frac{96(\sigma^{2}+16\rho^{2}\bar{r}^{2})}{\lambda
MK}+\frac{\bar{\lambda}\bar{r}^{2}}{4}$ (127)
$\displaystyle\leq\frac{3}{4}\left(Q_{t}(0)-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}\bar{r}}Q_{t}(\Delta x)\right)$
$\displaystyle\qquad+512\lambda\bar{r}^{2}\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)+\frac{\sigma\bar{r}+16\rho\bar{r}^{2}}{2\sqrt{MK}}+\frac{\bar{\lambda}\bar{r}^{2}}{4}\
.$ (128)

Now, we upper bound
$\lambda\mapsto\lambda\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)$ for $\lambda\in\Lambda_{1}$.
First,

$\lambda\exp\left(-\frac{K}{8}\min\left\\{\frac{\lambda}{eH+\lambda},\
\frac{\lambda^{2}}{\rho^{2}}\right\\}\right)=\max\left\\{\lambda\exp\left(-\frac{\lambda
K}{8eH+8\lambda}\right),\,\lambda\exp\left(-\frac{\lambda^{2}K}{8\rho^{2}}\right)\right\\}\
.$ (129)

Considering each term separately,

$\frac{d}{d\lambda}\left[\lambda\exp\left(-\frac{\lambda
K}{8eH+8\lambda}\right)\right]=\exp\left(-\frac{\lambda
K}{8eH+8\lambda}\right)\left(1-\frac{eHK\lambda}{8(eH+\lambda)^{2}}\right)\ .$
(130)

This is less than zero if $8(eH+\lambda)^{2}\leq eHK\lambda$, i.e.,

$\frac{eH}{16}\left(K-16-\sqrt{(K-16)^{2}-16}\right)\leq\lambda\leq\frac{eH}{16}\left(K-16+\sqrt{(K-16)^{2}-16}\right).$
(131)

With our choice of $\bar{\lambda}\geq\frac{8eH}{K-16}$, for any
$\lambda\geq\bar{\lambda}$ and $K\geq 175$,

$\lambda\geq\frac{8eH}{K-16}\geq\frac{eH}{16}\left(K-16-\sqrt{(K-16)^{2}-16}\right),$
(132)

so the left side of this inequality is satisfied. Thus, for
$\lambda\in\Lambda_{1}$ such that
$\lambda\leq\frac{eH}{16}\left(K-16+\sqrt{(K-16)^{2}-16}\right)$,

$\lambda\exp\left(-\frac{\lambda
K}{8eH+8\lambda}\right)\leq\bar{\lambda}\exp\left(-\frac{\bar{\lambda}K}{8eH+8\bar{\lambda}}\right)\
.$ (133)

Also, if $\lambda>\frac{eH}{16}\left(K-16+\sqrt{(K-16)^{2}-16}\right)$, then
since $K\geq 175$

$\lambda\exp\left(-\frac{\lambda
K}{8eH+8\lambda}\right)\leq\lambda\exp\left(-\frac{\frac{eH(K-16)}{16}K}{8eH+\frac{eH(K-16)}{2}}\right)\leq\lambda\exp\left(-\frac{K}{10}\right)\
.$ (134)

Furthermore, for $\lambda\in\Lambda_{1}$,

$\lambda\leq\bar{\lambda}\left(\frac{3}{2}\right)^{N-1}\leq\frac{3\bar{\lambda}}{2}\frac{H(B+5T\bar{r})}{3\bar{\lambda}\bar{r}}=\frac{3H(B+5T\bar{r})}{6\bar{r}}\
.$ (135)

Therefore, for any $\lambda\in\Lambda_{1}$

$\lambda\exp\left(-\frac{\lambda
K}{8eH+8\lambda}\right)\leq\max\left\\{\bar{\lambda}\exp\left(-\frac{\bar{\lambda}K}{8eH+8\bar{\lambda}}\right),\,\frac{3H(B+5T\bar{r})}{6\bar{r}}\exp\left(-\frac{K}{10}\right)\right\\}\
.$ (136)

Similarly,

$\frac{d}{d\lambda}\left[\lambda\exp\left(-\frac{\lambda^{2}K}{8\rho^{2}}\right)\right]=\exp\left(-\frac{\lambda^{2}K}{8\rho^{2}}\right)\left(1-\frac{\lambda^{2}K}{4\rho^{2}}\right)\
.$ (137)

This is negative for all $\lambda\geq\bar{\lambda}\geq\frac{2\rho}{\sqrt{K}}$,
so

$\lambda\exp\left(-\frac{\lambda^{2}K}{8\rho^{2}}\right)\leq\bar{\lambda}\exp\left(-\frac{\bar{\lambda}^{2}K}{8\rho^{2}}\right)\
.$ (138)

We conclude that

$\displaystyle\mathbb{E}$ $\displaystyle
Q_{t}(\Delta\tilde{x}_{t})-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}\bar{r}}Q_{t}(\Delta x)$
$\displaystyle\leq\frac{3}{4}\left(Q_{t}(0)-\min_{\Delta x:\|\Delta
x\|\leq\frac{1}{2}\bar{r}}Q_{t}(\Delta
x)\right)+\frac{\sigma\bar{r}+16\rho\bar{r}^{2}}{2\sqrt{MK}}+\frac{\bar{\lambda}\bar{r}^{2}}{4}$
$\displaystyle\qquad+512\bar{r}^{2}\max\left\\{\bar{\lambda}\exp\left(-\frac{\bar{\lambda}K}{8eH+8\bar{\lambda}}\right),\,\frac{3H(B+5T\bar{r})}{6\bar{r}}\exp\left(-\frac{K}{10}\right),\,\bar{\lambda}\exp\left(-\frac{\bar{\lambda}^{2}K}{8\rho^{2}}\right)\right\\}\
.$ (139)

Now, because $F$ is $\alpha$-quasi-self-concordant, by Lemma 1, $F$ is
$\exp(\alpha r)$-locally stable, so with our choice of
$\bar{r}\leq\frac{1}{5\alpha}$, we have that
$\exp(\frac{1}{2}\bar{r})\exp(5\bar{r})\leq e^{1.1}\leq 4$. Thus, it follows
from Lemma 2, for $\theta=\frac{3}{4}$, combined with the guarantee on the
output of Algorithm 2 from Lemma 3, that

$\displaystyle\mathbb{E}F(x_{T})-F^{*}$
$\displaystyle\leq\mathbb{E}\left[F(x_{0})-F^{*}\right]\exp\left(-\frac{T\bar{r}}{32B}\right)+\frac{32B}{\bar{r}}\left(\frac{\sigma\bar{r}+16\rho\bar{r}^{2}}{2\sqrt{MK}}+\frac{\bar{\lambda}\bar{r}^{2}}{4}\right)$
$\displaystyle\qquad+\frac{32B}{\bar{r}}\cdot
512\bar{r}^{2}\max\left\\{\bar{\lambda}\exp\left(-\frac{\bar{\lambda}K}{8eH+8\bar{\lambda}}\right),\,\frac{3H(B+5T\bar{r})}{6\bar{r}}\exp\left(-\frac{K}{10}\right),\,\bar{\lambda}\exp\left(-\frac{\bar{\lambda}^{2}K}{8\rho^{2}}\right)\right\\}$
(140)
$\displaystyle\leq\mathbb{E}\left[F(x_{0})-F^{*}\right]\exp\left(-\frac{T\bar{r}}{32B}\right)+\frac{32\sigma
B+512\rho B\bar{r}}{2\sqrt{MK}}+8\bar{\lambda}B\bar{r}$
$\displaystyle\qquad+2^{14}\max\left\\{\bar{\lambda}B\bar{r}\exp\left(-\frac{\bar{\lambda}K}{8eH+8\bar{\lambda}}\right),\,\frac{3H(B^{2}+5TB\bar{r})}{6}\exp\left(-\frac{K}{10}\right),\,\bar{\lambda}B\bar{r}\exp\left(-\frac{\bar{\lambda}^{2}K}{8\rho^{2}}\right)\right\\}$
(141)
$\displaystyle\leq\mathbb{E}\left[F(x_{0})-F^{*}\right]\exp\left(-\frac{T\bar{r}}{32B}\right)+\frac{32\sigma
B+512\rho B\bar{r}}{2\sqrt{MK}}$
$\displaystyle\qquad+\bar{\lambda}B\bar{r}\left(8+2^{14}\max\left\\{\exp\left(-\frac{\bar{\lambda}K}{8eH+8\bar{\lambda}}\right),\,\frac{3H(B+5T\bar{r})}{6\bar{\lambda}\bar{r}}\exp\left(-\frac{K}{10}\right),\,\exp\left(-\frac{\bar{\lambda}^{2}K}{8\rho^{2}}\right)\right\\}\right)\
.$ (142)

We have, for a constant $c$,

$\displaystyle\bar{\lambda}$
$\displaystyle=\max\left\\{\frac{2eH}{K-2},\,\frac{2\rho}{\sqrt{K}},\,\frac{32eH\log(51200)}{K},\,\frac{4\rho\sqrt{2\log(51200)}}{\sqrt{K}},\,\frac{320\sqrt{2}\rho}{\sqrt{MK}},\,\frac{320\sigma}{\bar{r}\sqrt{MK}},\,\frac{8eH}{K-16}\right\\}$
(143)
$\displaystyle=\max\left\\{\frac{32eH\log(51200)}{K},\,\frac{4\rho\sqrt{2\log(51200)}}{\sqrt{K}},\,\frac{320\sqrt{2}\rho}{\sqrt{MK}},\,\frac{320\sigma}{\bar{r}\sqrt{MK}}\right\\}$
(144)
$\displaystyle=c\cdot\max\left\\{\frac{H}{K},\,\frac{\rho}{\sqrt{K}},\,\frac{\sigma}{\bar{r}\sqrt{MK}}\right\\}\
.$ (145)

So, for a constant $c^{\prime}$, and using
$\mathbb{E}F(x_{0})-F^{*}\leq\frac{HB^{2}}{2}$,

$\displaystyle\mathbb{E}F(x_{T})-F^{*}$ $\displaystyle\leq
c^{\prime}\cdot\bigg{(}HB^{2}\exp\left(-\frac{T\bar{r}}{32B}\right)+\frac{\sigma
B+\rho B\bar{r}}{\sqrt{MK}}$
$\displaystyle\qquad+\bar{\lambda}B\bar{r}\left(1+\max\left\\{\exp\left(-\frac{\bar{\lambda}K}{H+\bar{\lambda}}\right),\,\frac{H(B+T\bar{r})}{\bar{\lambda}\bar{r}}\exp\left(-\frac{K}{10}\right),\,\exp\left(-\frac{\bar{\lambda}^{2}K}{\rho^{2}}\right)\right\\}\right)\bigg{)}$
(146) $\displaystyle\leq
c^{\prime}\cdot\left(HB^{2}\exp\left(-\frac{T\bar{r}}{32B}\right)+\frac{\sigma
B+\rho
B\bar{r}}{\sqrt{MK}}+\max\left\\{\bar{\lambda}B\bar{r},\,H(B^{2}+TB\bar{r})\exp\left(-\frac{K}{10}\right)\right\\}\right)$
(147)
$\displaystyle=c^{\prime}\cdot\bigg{(}HB^{2}\exp\left(-\frac{T\bar{r}}{32B}\right)+\frac{\sigma
B+\rho B\bar{r}}{\sqrt{MK}}$
$\displaystyle\qquad+\max\left\\{\frac{HB\bar{r}}{K},\,\frac{\rho
B\bar{r}}{\sqrt{K}},\,\frac{\sigma
B}{\sqrt{MK}},\,H(B^{2}+TB\bar{r})\exp\left(-\frac{K}{10}\right)\right\\}\bigg{)}$
(148)
$\displaystyle=c^{\prime}\cdot\left(HB^{2}\exp\left(-\frac{T\bar{r}}{32B}\right)+\frac{\sigma
B}{\sqrt{MK}}+\frac{HB\bar{r}}{K}+\frac{\rho
B\bar{r}}{\sqrt{K}}+H(B^{2}+TB\bar{r})\exp\left(-\frac{K}{10}\right)\right).$
(149)

So, since
$\bar{r}=\min\left\\{\frac{32B}{T}\log(TK),\,\frac{1}{5\alpha}\right\\}$, and
using the fact that, for $\zeta,a,b>0$,
$e^{-\zeta\min\left\\{a,b\right\\}}\leq e^{-\zeta a}+e^{-\zeta b}$, we have,
for a constant $c^{\prime\prime}$,

$\displaystyle\mathbb{E}F(x_{T})-F^{*}$ $\displaystyle\leq
c^{\prime\prime}\cdot\bigg{(}HB^{2}\exp\left(-\frac{T}{160\alpha
B}\right)+\frac{HB^{2}}{TK}+\frac{\sigma B}{\sqrt{MK}}+\frac{HB^{2}\log
TK}{TK}$ $\displaystyle\qquad\qquad+\frac{\rho B^{2}\log
TK}{T\sqrt{K}}+HB^{2}\log(TK)\exp\left(-\frac{K}{10}\right)\bigg{)}$ (150)
$\displaystyle\leq
c^{\prime\prime}\cdot\bigg{(}HB^{2}\exp\left(-\frac{T}{160\alpha
B}\right)+\frac{\sigma B}{\sqrt{MK}}+\frac{HB^{2}\log TK}{TK}$
$\displaystyle\qquad\qquad+\frac{\rho B^{2}\log
TK}{T\sqrt{K}}+HB^{2}\log(TK)\exp\left(-\frac{K}{10}\right)\bigg{)}\ ,$ (151)

where the last inequality follows from the fact $\log(TK)\geq 1$, since
$TK\geq 175$.

Finally, each call to Algorithm 2 requires at most $C\left\lceil\log
N\right\rceil$ rounds of communication (one for each call to Algorithm 3).
Therefore, we can implement up to $R/(C\left\lceil\log N\right\rceil)$
iterations of Algorithm 1 using our $R$ rounds of communication. We recall
that $N$ and $C$ are set as

$\displaystyle N$ $\displaystyle=\left\lceil
1+\frac{5}{2}\log\frac{H(B+5T\bar{r})}{3\bar{\lambda}\bar{r}}\right\rceil$
(152) $\displaystyle C$ $\displaystyle=\left\lceil
8\log\left(\lceil\log_{2}N\rceil\left(4+\frac{eH}{\bar{\lambda}}+\frac{80H(B+5T\bar{r})}{\bar{\lambda}\bar{r}}\right)\right)\right\rceil\
.$ (153)

Therefore, we need to choose $T$ such that $T\leq\frac{R}{C\left\lceil\log
N\right\rceil}$. To provide an explicit lower bound on how large $T$ can be,
we therefore lower bound the right hand side. First, we have

$\displaystyle N$ $\displaystyle=\left\lceil
1+\frac{5}{2}\log\frac{H(B+5T\bar{r})}{3\bar{\lambda}\bar{r}}\right\rceil$
(154) $\displaystyle\leq
2+\frac{5}{2}\log\frac{H\left(B+5T\frac{B}{T}\log(TK)\right)}{3\frac{2eH}{K-2}\min\left\\{\frac{32B}{T}\log(TK),\,\frac{1}{5\alpha}\right\\}}$
(155) $\displaystyle\leq
2+\frac{5}{2}\log\frac{BK\log(TK)}{e\min\left\\{\frac{32B}{T}\log(TK),\,\frac{1}{5\alpha}\right\\}}$
(156) $\displaystyle\leq
2+\frac{5}{2}\max\left\\{\log(TK\log(TK)),\,\log(2\alpha BK\log(TK))\right\\}$
(157) $\displaystyle\leq 2+5\log(1+2\alpha B)+5\log(TK).$ (158)

Similarly,

$\displaystyle C$ $\displaystyle=\left\lceil
8\log\left(\lceil\log_{2}N\rceil\left(4+\frac{eH}{\bar{\lambda}}+\frac{80H(B+5T\bar{r})}{\bar{\lambda}\bar{r}}\right)\right)\right\rceil$
(159) $\displaystyle\leq
1+8\log\left(\lceil\log_{2}N\rceil\left(4+\frac{eH}{\frac{2eH}{K-2}}+240\max\left\\{TK\log(TK),\,2\alpha
BK\log(TK)\right\\}\right)\right)$ (160) $\displaystyle\leq
1+8\log\left(\lceil\log_{2}N\rceil\left(4K+240\max\left\\{T^{2}K^{2},\,2\alpha
BTK^{2}\right\\}\right)\right)$ (161) $\displaystyle\leq
1+8\log\left(\left(1+\log N\right)\left(353T^{2}K^{2}+693\alpha
BTK^{2}\right)\right)$ (162) $\displaystyle\leq
1+8\log(693)+16\log(TK)+8\log(1+\alpha B)+8\log(1+\log(N))$ (163)
$\displaystyle\leq 54+16\log(TK)+8\log(1+\alpha B)+16\log\log N$ (164)
$\displaystyle\leq 80+32\log(TK)+24\log(1+2\alpha B).$ (165)

Therefore,

$\displaystyle\frac{R}{C\left\lceil\log N\right\rceil}$
$\displaystyle\geq\frac{R}{\left(80+32\log(TK)+24\log(1+2\alpha
B)\right)\left\lceil\log\left(2+5\log(1+2\alpha
B)+5\log(TK)\right)\right\rceil}$ (166)
$\displaystyle\geq\frac{R}{\left(80+32\log(TK)+24\log(1+2\alpha
B)\right)^{2}}$ (167) $\displaystyle\geq\frac{R}{2048+2\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\ .$ (168)

So, it suffices to choose $T$ such that

$T\log^{2}(T)\leq\frac{R}{2048+2\left(80+32\log K+24\log(1+2\alpha
B)\right)^{2}}\ .$ (169)

Note that equality holds for

$\displaystyle T$
$\displaystyle=\exp\left(2W\left(\left(\frac{R}{4096+4\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)^{1/2}\right)\right),$

where $W(\cdot)$ denotes the Lambert $W$ function. Thus, because
$W(x)\geq\log(x)-\log\log(x)$ for $x\geq e$, and since we assume

$R\geq\tilde{\Omega}(1)=e^{2}\left(4096+4\left(80+32\log K+24\log(1+2\alpha
B)\right)^{2}\right),$

we have that

$\displaystyle\exp\left(2W\left(\left(\frac{R}{4096+4\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)\right)^{1/2}\right)$
$\displaystyle\geq\exp\Bigg{(}2\left(\log\left(\frac{R}{4096+4\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)^{1/2}\right)$
$\displaystyle\qquad-\log\log\left(\frac{R}{4096+2\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)^{1/2}\Bigg{)}$
$\displaystyle=\frac{1}{4}\left(\frac{R}{4096+4\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)$
$\displaystyle\qquad\cdot\log^{2}\left(\left(\frac{R}{4096+4\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)\right).$

Thus, letting

$\displaystyle T$
$\displaystyle=\Bigg{\lfloor}\frac{1}{4}\left(\frac{R}{4096+4\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)$
$\displaystyle\qquad\cdot\log^{2}\left(\left(\frac{R}{4096+4\left(80+32\log
K+24\log(1+2\alpha B)\right)^{2}}\right)\right)\Bigg{\rfloor},$

and using $\tilde{O}$ notation to hide polylogarithmic factors in $R$, $K$,
and $\alpha B$, we have

$\displaystyle\mathbb{E}[F(x_{T})]-F^{*}\leq
HB^{2}\left(\exp\left(-\frac{R}{\tilde{O}\left(\alpha
B\right)}\right)+\exp\left(-\frac{K}{O(1)}\right)\right)+\tilde{O}\left(\frac{\sigma
B}{\sqrt{MK}}+\frac{HB^{2}}{KR}+\frac{\rho B^{2}}{\sqrt{K}R}\right)\ .$ (170)

This completes the proof. ∎

##  Appendix E Additional Information for Experiments

###  E.1 Baselines

We have compared FedSN-Lite against the two variants of FedAc (Yuan and Ma,
2020), Minibatch SGD (Dekel et al., 2012), and Local SGD (Zinkevich et al.,
2010). Two settings of hyperparameters are considered for FedAc in Yuan and Ma
(2020) for strongly convex functions:

  * •

FedAc-I: $\eta\in(0,1/H],\ \gamma=\max\left\\{\sqrt{\frac{\eta}{\lambda
K}},\eta\right\\},\ \alpha=\frac{1}{\gamma\lambda},\beta=\alpha+1$;

  * •

FedAc-II: $\eta\in(0,1/H],\ \gamma=\max\left\\{\sqrt{\frac{\eta}{\lambda
K}},\eta\right\\},\
\alpha=\frac{3}{2\gamma\lambda}-\frac{1}{2},\beta=\frac{2\alpha^{2}-1}{\alpha-1}$,

where $H$ is the smoothness constant as in Assumption 1, $\lambda$ is an
estimate of the strong convexity, and $\eta$ is the learning rate which has to
be tuned. Thus, a limitation of FedAc is that it requires either the knowledge
of $\lambda$ (say, through explicit $\lambda$-regularization), or that the
algorithm adds regularization to the objective itself (this is how Yuan and Ma
(2020) present FedAc for general convex functions). In our experiments we have
both of these settings, i.e., FedAc with internal regularization $\lambda$ or
explicitly $\lambda$-regularized objectives. For brevity, in Algorithm 6 we
present FedAc with five hyperparameters: $\alpha$, $\beta$, $\eta$, $\gamma$,
and $\lambda$. When the objective is regularized we use $\lambda=0$ (c.f.
Section 5, Experiment 2), whereas otherwise we tune $\lambda$ (c.f. Section 5,
Experiment 1), to ensure the best possible performance for FedAc.

Algorithm 6 FedAc$(x_{0},\alpha,\beta,\eta,\gamma,\lambda)$

(Operating on objective $F(\cdot)+\lambda/2\|.\|^{2}$ as opposed to $F(.)$
with stochastic gradient oracle $g_{\lambda}(\cdot;\cdot)$444Note that
$g_{\lambda}(x;z)=g(x;z)+\lambda x$, i.e., the stochastic oracle for the
regularized objective can always be obtained using the oracle for the
unregularized objective (see Assumption 1).).)

Intitialize: $x^{ag,m}_{0}=x^{m}_{0}=x_{0}$ for all $m\in[M]$

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

for every worker $m\in[M]$ in parallel do

$x^{md,m}_{t}\leftarrow\beta^{-1}x^{m}_{t}+(1-\beta^{-1})x^{ag,m}_{t}$

$g^{m}_{t}\leftarrow g_{\lambda}(x^{md,m}_{t},z^{m}_{t})$ $\triangleright$
Query the stochastic first-order oracle at $x^{md,m}_{t}$, for
$z^{m}_{t}\sim\mathcal{D}$

$v^{ag,m}_{t+1}\leftarrow x^{md,m}_{t}-\eta\cdot g^{m}_{t}$

$v^{m}_{t+1}\leftarrow(1-\alpha^{-1})x^{m}_{t}+\alpha^{-1}x^{md,m}_{t}-\gamma
g^{m}_{t}$

if $t$ mod $K=-1$ then

$x^{m}_{t+1}\leftarrow\frac{1}{M}\sum_{m^{\prime}=1}^{M}v^{m^{\prime}}_{t+1}$

$x^{ag,m}_{t+1}\leftarrow\frac{1}{M}\sum_{m^{\prime}=1}^{M}v^{ag,m^{\prime}}_{t+1}$

else

$x^{m}_{t+1}\leftarrow v^{m}_{t+1}$

$x^{ag,m}_{t+1}\leftarrow v^{ag,m}_{t+1}$

Return:
$\bar{x}^{ag}_{T}=\frac{1}{M}\sum_{m^{\prime}=1}^{M}x^{ag,m^{\prime}}_{T}$

In Algorithm 7 we describe Local SGD (a.k.a. FedAvg) (Zinkevich et al., 2010)
with learning rate $\eta$ and Polyak’s momentum (a.k.a. heavy ball method)
parameter $\beta$. Setting $\beta=0$ recovers the familiar algorithm as
analyzed in Woodworth et al. (2020a). Finally, in Algorithm 8 we describe
Minibatch SGD with fixed learning rate $\eta$ and momentum parameter $\beta$.
Note that in our experiments we compare the algorithms using the same number
of machines $M$, communication rounds $R$ and theoretical parallel runtime $T$
against each other, where $T=KR$. Also note that unlike Algorithm 6, there is
no internal regularization in Algorithms 7 and 8. While conducting Experiment
2 (c.f., section 5) we assume that $F(.)$ is regularized, so that Algorithms 7
and 8 instead minimize $F(.)+\frac{\lambda}{2}\|.\|^{2}$ and have access to
$g_{\lambda}(.;.)$. The reason why $\lambda$ is not presented as a
hyperparameter for any algorithms beside FedAc, is because the regularization
is a part of the algorithm FedAc itself which we tune besides its learning
rate (c.f., Section E in Yuan and Ma (2020)).

Algorithm 7 Local SGD$(x_{0},\beta,\eta)$

(Operating on objective $F(\cdot)$ with stochastic gradient oracle
$g(\cdot;\cdot)$.)

Intitialize: $x_{0,0}^{m}\leftarrow x_{0}$ for all $m\in[M]$

for $r=0,\dots,R-1$ do

for every worker $m\in[M]$ in parallel do

for $k=0,\dots,K-1$ do

$g^{m}_{r,k}\leftarrow g(x^{m}_{r,k};z_{r,k}^{m})$ $\triangleright$ Query the
stochastic first-order oracle at $x^{m}_{r,k}$ (for
$z^{m}_{r,k}\sim\mathcal{D}$ drawn by the oracle)

$x^{m}_{r,k+1}\leftarrow x^{m}_{r,k}-\eta
g_{r,k}^{m}+\mathbbold{1}_{k>0}\beta(x^{m}_{r,k}-x^{m}_{r,k-1})$

$x_{r+1}\leftarrow\frac{1}{M}\sum_{m^{\prime}=1}^{M}x_{r,K}^{m^{\prime}}$

Return: $x_{R}$

Algorithm 8 Minibatch SGD$(x_{0},\beta,\eta)$

(Operating on objective $F(\cdot)$ with stochastic gradient oracle
$g(\cdot;\cdot)$.)

Intitialize: $x^{m}_{0}=x_{0}$ for all $m\in[M]$

for $r=0,\dots,R-1$ do

for every worker $m\in[M]$ in parallel do

for $k=0,\dots,K-1$ do

$g^{m}_{r,k}\leftarrow g(x_{r};z_{r,k}^{m})$ $\triangleright$ Query the
stochastic first-order oracle at $x_{r}$ (for $z^{m}_{r,k}\sim\mathcal{D}$
drawn by the oracle)

$g_{r}\leftarrow\frac{1}{KM}\sum_{k^{\prime}=0}^{K-1}\sum_{m^{\prime}=1}^{M}g^{m^{\prime}}_{r,k^{\prime}}$

$x_{r+1}\leftarrow x_{r}-\eta g_{r}+\mathbbold{1}_{r>0}\beta(x_{r}-x_{r-1})$

Return: $x_{R}$

In addition, we may see that Regularized-Quadratic-Solver with
$\eta_{k}(\lambda)=\eta$ and $w_{k}(\lambda)=\frac{1}{K}$ (as in each
iteration of FedSN-Lite) is a special case of Local SGD (Algorithm 7) with
$R=1$. Thus to summarize, in our experiments, we have compared the following
algorithms:

  * •

FedSN-Lite (which uses Regularized-Quadratic-Solver) without momentum i.e.,
$\beta=0$ or with optimally tuned momentum
$\beta\in\\{0.1,0.3,0.5,0.7,0.9\\}$,

  * •

FedAc-1 and FedAC-2, with either no internal regularization i.e., $\lambda=0$
(in experiment 2 when the objective is explicitly regularized) or optimally
tuned internal regularization $\lambda\in\\{$1e- 2, 1e-3, 1e-4, 1e-5,
1e-6$\\}$ (in experiment 1),

  * •

Local SGD without momentum i.e., $\beta=0$ or with tuned momentum
$\beta\in\\{0.1,0.3,0.5,0.7,0.9\\}$,

  * •

Minibatch SGD without momentum i.e., $\beta=0$ or with tuned momentum
$\beta\in\\{0.1,0.3,0.5,0.7,0.9\\}$,

We search for the best learning rate $\eta\in\\{0.0001,0.0002,$
$0.0005,0.001,0.002,0.005,0.01,0.02,0.05,0.1,0.2,\\\ 0.5,1,2,5,10,20\\}$ for
every configuration of each algorithm. We verify (along with Yuan and Ma
(2020)) that the optimal learning rate always lies in this range.

###  E.2 More implementation details

Dataset. Following the setup in Yuan and Ma (2020), we use the full LIBSVM a9a
(Chang and Lin, 2011; Dua and Graff, 2017) dataset. It is a binary
classification dataset with $32{,}561$ points and $123$ features. For
generating fig. 1(a) and 2 we use the entire dataset as a training set. For
generating fig. 1(b) we split the dataset, using $20{,}000$ points as the
training set and the rest as the validation set.

Experiment 2. As described in the body of the paper, each sub-plot (in Figure
2) shows the performance of the different algorithms and their variants (as
discussed above) on $\mu$-regularized logistic regression. For the experiments
we vary the values of $\mu$, $M$, and $R$, for fixed theoretical parallel
runtime $KR$. Each of these is a different _setting_ , reflecting different
computation-communication-accuracy trade-offs. For each of these settings, we
run an algorithm configuration (with some $\beta$ and $\lambda=0$ for FedAc),
with different learning rates $\eta$, and record the best loss (which is the
Regularized ERM-loss on the entire dataset) obtained _at any point_ during
optimization. Based on this run we pick the optimal learning rate for each
setting for each algorithm.

Note that this means every point in a sub-plot is an individual experiment,
for which we have tuned. Since we are only concerned with optimization, we
tune and report the accuracy only on the training set (with $32{,}561$
points). Both the stochastic first-order oracle and the Hessian-vector product
oracle, used by the respective algorithms, do sampling with replacement.
Following Yuan and Ma (2020), we ensure that our learning rate tuning grid was
both wide and fine enough for the algorithms to achieve their optimal training
losses. Since we are using stochastic algorithms which sample with
replacement, without any definite order on the dataset (as opposed to making a
single pass), the best suboptimality is potentially different for each run of
the algorithm, even when choosing the same learning rate and initialization.
Thus, once we have the optimal parameters ($\eta,\beta,\lambda$), we rerun the
algorithm multiple times on the corresponding setting. The error bars
represent the standard deviation of the best suboptimality obtained when using
this optimal learning rate.

Note that changing the regularization strength changes the optimal error value
on the RERM task. Thus, to get the optimal loss value, we run exact Newton’s
method separately on each of these settings (for different values of $\mu$),
until the algorithm had converged up to $\approx 12$ decimal places. We also
ensure that our optimal loss values look similar to Yuan and Ma (2020). The