# Adaptive Step-Size Methods for Compressed SGD

Adarsh M. Subramaniam, Akshayaa Magesh, Venugopal V. Veeravalli
Department of Electrical and Computer Engineering,
University of Illinois at Urbana-Champaign

###### Abstract

Compressed Stochastic Gradient Descent (SGD) algorithms have been recently
proposed to address the communication bottleneck in distributed and
decentralized optimization problems, such as those that arise in federated
machine learning. Existing compressed SGD algorithms assume the use of non-
adaptive step-sizes (constant or diminishing) to provide theoretical
convergence guarantees. Typically, the step-sizes are fine-tuned in practice
to the dataset and the learning algorithm to provide good empirical
performance. Such fine-tuning might be impractical in many learning scenarios,
and it is therefore of interest to study compressed SGD using adaptive step-
sizes. Motivated by prior work on adaptive step-size methods for SGD to train
neural networks efficiently in the uncompressed setting, we develop an
adaptive step-size method for compressed SGD. In particular, we introduce a
_scaling_ technique for the descent step in compressed SGD, which we use to
establish order-optimal convergence rates for convex-smooth and strong convex-
smooth objectives under an interpolation condition and for non-convex
objectives under a strong growth condition. We also show through simulation
examples that without this scaling, the algorithm can fail to converge. We
present experimental results on deep neural networks for real-world datasets,
and compare the performance of our proposed algorithm with previously proposed
compressed SGD methods in literature, and demonstrate improved performance on
ResNet-18, ResNet-34 and DenseNet architectures for CIFAR-100 and CIFAR-10
datasets at various levels of compression.

##  I Introduction

Consider the optimization problem of minimizing the sum of $n$ functions :

$\min_{x}f(x)=\min_{x}\frac{1}{n}\sum_{i=1}^{n}f_{i}(x).$ (1)

This formulation is widely used in machine learning, where $f_{i}$ is the loss
function corresponding to datapoint $i$, $n$ is the size of the training set,
and $x$ corresponds to the parameters of the learning model.

A practical approach to solving the optimization problem in (1) is stochastic
gradient descent (SGD) where one of the component functions $f_{i}$ is sampled
at random at a given iteration step, and the iterate $x$ is updated using the
gradient of $f_{i}$. The main problem of interest in this paper is one where
compressed versions of the gradients are used in the SGD iterations. The use
of compressed gradients allows for the alleviation of the communication
bottleneck in distributed and decentralized optimization settings such as
those that arise in federated learning [1].

There have been several recent papers on compressed SGD algorithms (see, e.g.,
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]). Compressed gradient transmission was
first explored in [2, 3], where only the top $k$ (e.g., $k=1\%$) values of the
components of the gradient (with feedback) are used in the iteration update.
The convergence properties of such compressed gradient methods with feedback
were studied in a number of subsequent papers (e.g., [5, 4]). Feedback has
also been shown to fix convergence issues in compression algorithms such as
Sign-SGD [13]. In the decentralized setting, the convergence of SGD with
compression and the use of gossip algorithms has been established in [14].

Existing works on compressed SGD algorithms assume the use of diminishing or
constant step-sizes based on system parameters to show convergence properties.
In applications to machine learning, the step-sizes are fine tuned to the
dataset and the machine learning model to provide good empirical performance.
However, such fine tuning can be impractical and can result in sub-optimal
rates of convergence. Hence it is of interest to study adaptive step-size
methods for compressed SGD.

Adaptive step-size techniques for (uncompressed) SGD have been studied in
several recent works (see, e.g., [15, 16, 17]). An efficient implementation of
the classical Armijo step-search method [18] to train neural networks has been
proposed in the work of [15]. Extensions to improve the performance of
adaptive gradient methods such as Adagrad [19] and AMSgrad [20] have been
proposed in [17]. Adaptive step-size methods for variance reduction algorithms
like SVRG have also been proposed in [16]. In order to establish convergence,
these works assume that the objective satisfies an interpolation condition.
The condition essentially implies that there exists a point $x^{*}$ which is a
minimum for all the functions $f_{i}$ in the optimization problem (1). Several
other recent works, [21, 22, 23] have used the interpolation condition to
establish convergence of non-compressed SGD in various settings. The use of
this condition has also been supported by theoretical works [24, 25], in the
context of modern neural networks, where the number of parameters is much
larger than the number of datapoints in the training dataset. The
interpolation condition is also satisfied by models such as non-parameteric
regression [26], boosting [27] and linear classification on separable data
[28].

Motivated by adaptive step-size techniques for uncompressed SGD, we develop an
adaptive step-size technique for compressed SGD that results in faster
convergence at the same compression level than existing non-adaptive step-size
compressed SGD algorithms. To this end, we develop a scaling technique, which
is crucial to the convergence of our adaptive step-size compressed SGD
algorithm. To the best of our knowledge, we are not aware of any adaptive
step-size SGD methods for compressed SGD with feedback that have theoretical
guarantees.

### Our Contributions

  1. 1.

We introduce the idea of scaling for the classical Armijo step-size search,
and demonstrate that it can accelerate convergence in certain asymmetric
optimization problems.

  2. 2.

Using a scaling technique, we prove that the Armijo step-size search [18] for
Gradient Descent (GD) converges at the rate of $O(\frac{1}{T})$ for convex and
smooth functions, where $T$ is the number of iterations, for all values of
$\sigma\in(0,1)$. Here $\sigma$ is a parameter of Armijo’s rule (see (2) for a
definition). To the best of our understanding, prior works have been able to
show $O(\frac{1}{T})$ convergence only for values of $\sigma\geq 0.5$ .

  3. 3.

We propose a computationally feasible and efficient adaptive step-size search
compressed SGD algorithm that uses the scaling technique and the biased
$top_{k}$ operator for compression. We prove under an interpolation condition
(see Definition 4), our proposed algorithm achieves a convergence rate of
$O(\frac{1}{T})$ when the objective function is convex and smooth, and
$O(\beta^{T})$ ($\beta<1$) when the objective function is strongly-convex and
smooth. We also show that under a strong growth condition (see Definition 5),
the algorithm achieves a convergence rate of $O(\frac{1}{T})$ in the non-
convex setting. The above results hold for all values of the parameter
$\sigma\in(0,1)$ of the step-search.

  4. 4.

We demonstrate through experiments that the scaling technique is not just a
proof technicality; without scaling, a direct implementation of Armijo step-
size search for compressed SGD can result in divergence of the algorithm from
the minimum.

  5. 5.

We demonstrate that our algorithm for compressed SGD outperforms existing non-
adaptive SGD methods on neural network training tasks at various levels of
compression.

##  II Preliminaries and Notation

In this section, we lay out the notation used in this paper, discuss the
classical Armijo step-size search, the compression operator $top_{k}$, and the
conditions under which we prove our convergence results.

###  II-A Notation

Let $x_{t}$ denote the iterate of the optimization algorithm at time $t$, and
$i_{t}$ denote the datapoint or batch of data chosen at time $t$. The loss
function of the batch $i_{t}$ chosen at time $t$ at an iterate $x_{t}$ is
denoted by $f_{i_{t}}(x_{t})$. The step-size used at time $t$ is denoted by
$\eta_{t}$.

###  II-B Armijo Step-Size Search in Gradient Descent

The algorithm proposed in this work makes use of a modified and efficient
implementation of the classical Armijo step-size search method [18]. For a
function $f$, the method at iteration $t$ searches for the step-size starting
at $\alpha_{\mathrm{max}}$, and decreases the step-size by a factor $\rho<1$
until the condition

$f(x_{t}-\alpha_{t}\nabla f(x_{t}))\leq f(x_{t})-\sigma\alpha_{t}||\nabla
f(x_{t})||^{2}$ (2)

is met, where $\sigma$ is a parameter of the algorithm. The step-size
$\alpha_{t}$ that satisfies (2) is substituted as the value of the step-size
in the iteration of the GD algorithm. The pseudocode for Armijo step-size
search is given in Algorithm 1.

Algorithm 1 Armijo Step-Size Search

1:procedure armijo step-size search($f,\alpha_{\mathrm{max}},x_{t},t$)

2: $\alpha_{t}=\alpha_{\mathrm{max}}$

3: repeat

4: $\alpha_{t}\leftarrow\alpha_{t}\rho$

5: $\tilde{x}_{t+1}\leftarrow x_{t}-\alpha_{t}\nabla f(x_{t})$

6: until $f(\tilde{x}_{t+1})\leq f(x_{t})-\sigma\alpha_{t}||\nabla
f(x_{t})||^{2}$

7: return $\alpha_{t}$

8:end procedure

###  II-C Topk Compression Operator

In our compressed SGD algorithm, the gradient in each iteration is compressed
using the $top_{k}$ compression operator (see, e.g., [4, 8]). Let
$x\in\mathbb{R}^{d}$. Let $\mathsf{T_{k}}$ be the set of indices of the $k$
elements of $x$ with maximum magnitude, and define
$\gamma\triangleq\frac{k}{d}$. The $top_{k}$ operator compresses a vector $x$
such that

$top_{k}(x)_{i}=\begin{cases}(x)_{i}&\text{If $i\in\ \mathsf{T_{k}}$}\\\
0&\text{otherwise}\\\ \end{cases}.$ (3)

###  II-D Definitions

To establish the convergence of our algorithm, we require the following
interpolation condition in the convex setting, and the strong growth condition
in the non-convex setting.

######  Definition 1 (Interpolation).

[29] A function $f(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$ satisfies the
interpolation condition if

$\exists\ x^{*}\;\;\;\text{s.t.}\;\;\;\nabla f_{i}(x^{*})=0,\forall
i\in\\{1,2,\cdots,n\\}.$ (4)

######  Definition 2 (Strong Growth Condition).

[15] A function $f=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$ satisfies the strong
growth condition with constant $\nu$ if

$\frac{1}{n}\sum_{i=1}^{n}||\nabla f_{i}(x)||^{2}\leq\nu||\nabla f(x)||^{2}$
(5)

##  III Compressed SGD with Adaptive Step-Size

Our proposed compressed SGD algorithm is motivated by the idea of scaling,
where the step-size returned by the Armijo rule is scaled by a factor $a$ in
the descent step. We now discuss the intuition for such scaling, and propose
an algorithm for compressed SGD with Armijo step-size search and scaling.

###  III-A Armijo Step-Size Search with Scaling

Optimization problems that arise in machine learning applications are usually
asymmetric, and have gradients that do not point in the direction of a
minimizer. For example, consider the function
$f(x)=\frac{x_{1}^{2}}{4}+\frac{x_{2}^{2}}{9}$. The negative gradient at a
point is orthogonal to the tangent and does not necessarily point towards the
minimizer $(0,0)$. Hence, GD with Armijo step-size search may suffer from
slower convergence if $\alpha_{\mathrm{max}}$ is large. In order to alleviate
this issue, we introduce the idea of scaling where the step-size $\alpha_{t}$
returned by Armijo’s rule (2) is scaled by a factor $a<2\sigma$, and
$\eta_{t}\triangleq a\alpha_{t}$ is used as the step-size in the descent step,
i.e.,

$x_{t+1}=x_{t}-\eta_{t}\nabla f(x_{t}).$

It is important to note that the stopping criterion for Armijo’s rule (2) uses
$\alpha_{t}$ (and not $\eta_{t}$) to scale the gradient. In the Appendix
(Figure 5), we plot the loss for GD with Armijo step-size search for the
asymmetric function $f(x)=\sum_{i=1}^{10}\frac{x_{i}^{2}}{2^{i}}$, and show
that the scaled GD algorithm outperforms the non-scaled one by several orders
of magnitude in terms of convergence time to the minimum.

Another aspect of GD algorithm with Armijo step-size search is that while the
algorithm converges for all values of $\sigma\in(0,1)$, a convergence rate of
$O(1/T)$ for convex objectives (where $T$ is the number of iterations of the
GD algorithm) has been proven only for values of $\sigma\geq 0.5$ [18]. On the
other hand, commonly used values of $\sigma$ in practice are in the range
$[10^{-5},\ 10^{-1}]$ [30]. With scaling added to Armijo step-size search, we
prove a convergence rate of $O(\frac{1}{T})$ for convex objectives for all
values of $\sigma\in(0,1)$. To the best of our knowledge, this is the first
such proof, and is presented in Section IX of the Appendix.

###  III-B Compressed SGD with Armijo Step-Size Search and Scaling (CSGD-ASSS)

Following [3], the method that we used for gradient compression is one that
utilizes memory feedback to compensate for the error due to compression. The
corresponding update rule for the iterate at time $t$ is given by:

$\displaystyle x_{t+1}=x_{t}-top_{k}(m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t}))$
(6)

where $\eta_{t}$ is the step-size, $i_{t}$ is the index of the function
sampled at time $t$, and $m_{t}$ is the error value due to compression that is
updated as in step 8 of Algorithm 2.

In the compressed SGD setting, even if the negative gradient $-\nabla
f_{i_{t}}(x_{t})$ points towards a minimizer of $f$, the descent direction
$-top_{k}(m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t}))$ may be skewed away from the
minimizer. Hence step-size search based on Armijo’s rule (without scaling)
used in [15] for uncompressed SGD may diverge (exponentially) for compressed
SGD, as we show in Section IV-C. Motivated by our results on scaling for GD
with Armijo step-size search, we propose scaling as a fix for compressed SGD
with Armijo step-size search as discussed below.

At iteration $t$, the CSGD-ASSS algorithm implements Armijo step-size search
(Algorithm 1) with the function $f_{i_{t}}$ and returns a value $\alpha_{t}$
that satisfies

$f_{i_{t}}(x_{t}-\alpha_{t}\nabla f_{i_{t}}(x_{t}))\leq
f_{i_{t}}(x_{t})-\sigma\alpha_{t}||f_{i_{t}}(x_{t})||^{2}.$ (7)

The step-size at iteration $t$ is subsequently chosen as
$\eta_{t}=a\alpha_{t}$, where $a$ is a scaling factor. The algorithm computes
the compressed gradient with feedback error $m_{t}$ and scaled step-size
$\eta_{t}$ as

$g_{t}=top_{k}(\eta_{t}\nabla f_{i_{t}}(x_{t})+m_{t}).$ (8)

The iterate and error for iteration $t+1$ are updated, respectively, as

$x_{t+1}=x_{t}-g_{t}$

and

$m_{t+1}=\eta_{t}\nabla f_{i_{t}}(x_{t})+m_{t}-top_{k}(\eta_{t}\nabla
f_{i_{t}}(x_{t})+m_{t}).$

Algorithm 2 Compressed SGD + Armijo Step-Size Search and Scaling (CSGD-ASSS)

1:for $t=1,\cdots,T$ do

2: Sample batch $i_{t}$ of data

3: $\alpha_{\mathrm{max}}=\omega\alpha_{t-1}$

4: $\alpha_{t}\leftarrow\text{Armijo Step-Size
Search}(f_{i_{t}},\alpha_{\mathrm{max}},x_{t},t)$

5: $\eta_{t}=a\alpha_{t}$

6: $g_{t}=top_{k}(m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t}))$

7: $x_{t+1}\leftarrow x_{t}-g_{t}$

8: $m_{t+1}=m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t})-top_{k}(m_{t}+\eta_{t}\nabla
f_{i_{t}}(x_{t}))$

9:end for

######  Remark 1.

The CSGD-ASSS algorithm in the distributed setting (presented in the Appendix)
adaptively tunes the step-size $\eta_{t}$ specifically to the data at each
node.

###  III-C Convergence Analysis

We now study the convergence of the CSGD-ASSS algorithm in the convex and
strong convex settings under the interpolation condition (4), and in the non-
convex setting under the strong growth condition (5). These rates achieved
under compression are the same as those in the uncompressed setting studied in
[15].

####  III-C1 Main Results

Consider the minimization of the objective
$f(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$ with CSGD-ASSS algorithm. For the
convex setting we prove the following convergence result under the
interpolation condition.

######  Theorem 1 (CSGD-ASSS convex).

Let $f_{i}(x)$ be convex and $L_{i}$ smooth for $i\in[n]$, and assume that the
interpolation condition (4) is satisfied. Then there exists $\hat{a}>0$ such
that for $0<a\leq\hat{a}$, the CSGD-ASSS algorithm with scaling $a$, parameter
$\sigma\in(0,1)$, and compression factor $\gamma=\frac{k}{d}$, satisfies

$E\left[f\left(\frac{1}{T}\sum_{t=0}^{T-1}x_{t}\right)\right]-E[f(x^{*})]\leq\frac{1}{\delta_{1}T}(E[||x_{0}-x^{*}||^{2}])$
(9)

where for any $0<\epsilon<\zeta$,
$\zeta\triangleq\frac{\sigma\gamma}{(2-\gamma)}$ and
$L_{\mathrm{max}}\triangleq\max_{i}L_{i}$,

$\displaystyle\delta_{1}\triangleq\rho\frac{2(1-\sigma)}{L_{\mathrm{max}}}\Big{(}2a-\frac{a^{2}}{\sigma}-\frac{a^{2}}{\sigma
p(\epsilon)}-(1-\gamma)\left(1+\frac{1}{r(\epsilon)}\right)\frac{a^{2}}{\sigma}\Big{)},$
(10) $\displaystyle\hat{a}=(\zeta-\epsilon).$

The values of $p(\epsilon),r(\epsilon)$ are obtained from the following convex
problem.

$\displaystyle\max_{p,r}\tilde{a}_{1}(p,r)=2\sigma/\Big{(}1+\frac{1}{p}+(1-\gamma)(1+\frac{1}{r})\Big{)}$
(11) $\displaystyle\mathrm{s.t.}(p+(1-\gamma)(1+r))\leq 1$ $\displaystyle
p\geq 0,r\geq 0$

Let the solution to the problem be $p_{\mathrm{max}},r_{\mathrm{max}}$. It is
shown in the Appendix that the maximum value
$\tilde{a}_{1}(p_{\mathrm{max}},r_{\mathrm{max}})$ is $\zeta$. Due to the
continuity of $\tilde{a}_{1}(p,r)$, the parameters $p(\epsilon),r(\epsilon)$
can be chosen to be any values that satisfy:

$\displaystyle(p(\epsilon)+(1-\gamma)(1+r(\epsilon)))<1$ (12)
$\displaystyle\tilde{a}_{1}(p(\epsilon),r(\epsilon))>\zeta-\epsilon.$

Consider the minimization of the function $f(x)$ in the convex setting, with
some $f_{i}(x)$ satisfying strong convexity with parameter $\mu_{i}>0$. Then
we can establish the following ‘linear’ convergence result.

######  Theorem 2 (CSGD-ASSS strong convex).

Let $f_{i}$ be convex and $L_{i}$ smooth for all $i\in[n]$, and $\mu_{i}$
strongly convex with $\mu_{i}>0$ for some $i\in[n]$. Assume that the
interpolation condition (4) is satisfied. Then there exists $\hat{a}>0$ such
that for $0<a\leq\hat{a}$, the CSGD-ASSS algorithm with scaling $a$ and
$\sigma\in(0,1)$ satisfies

$\displaystyle E[||x_{t}-x^{*}||^{2}]\leq
2(\hat{\beta})^{t}E[(||{x}_{0}-x^{*}||^{2})],$ (13)

for some $\hat{\beta}<1$, where for all $0<\epsilon<\zeta$

$\displaystyle\hat{\beta}=\max{\\{\beta_{1}(p{(\epsilon)},r{(\epsilon)}),(1-\frac{E_{i_{t}}[\mu_{i_{t}}]a(1-\sigma)}{L_{\mathrm{max}}})\\}},$
(14)
$\displaystyle\beta_{1}(p(\epsilon),r(\epsilon))=\Big{(}\mu_{\mathrm{max}}a\alpha_{\mathrm{max}}+p(\epsilon)+(1-\gamma)(1+r(\epsilon))\Big{)}$
$\displaystyle\hat{a}=\zeta-\epsilon$

The values $p(\epsilon),r(\epsilon)$ are as defined in (11) and (12), and
$\mu_{\mathrm{max}}$ is defined in the Appendix.

To show convergence guarantees in the non-convex case, we use the strong
growth condition (5).

######  Theorem 3 (CSGD-ASSS non-convex).

Let $f_{i}$ be convex, $L_{i}$ smooth and let $f_{i}$ $i\in[n]$ satisfy the
strong growth condition (5). Then, there exists $\hat{a},\hat{\alpha}$ such
that for $0<a\leq\hat{a}$ and $\alpha_{\mathrm{max}}\leq\hat{\alpha}$ ,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}E[\lVert\nabla
f(x_{t})\rVert^{2}]\leq\frac{(E[f({x}_{0})]-E[f(\hat{x}_{T})])}{\delta T}$
(15)

where $\hat{x}_{T}$ is a perturbed iterate [31] obtained from
$\\{x_{i}\\}_{i=1}^{T}$. A discussion on the choice of $\hat{a}$, and
$\hat{\alpha}$ is presented in the Appendix.

######  Remark 2.

Proofs for the uncompressed SGD setting [15] constrain the values of both
$\sigma$ and $\alpha_{\mathrm{max}}$ in the non-convex setting, and the bounds
are dependent on the function parameters $L_{i}$. Interestingly the scaling
technique allows us to eliminate the bound on $\sigma$.

##  IV Experimental Results

(a) ResNet34,CIFAR10,1.5%

(b) ResNet34,CIFAR100,1.5%

(c) ResNet18,CIFAR100,1.5%

(d) ResNet18,CIFAR10,1.5%

Figure 1: Training loss at $\approx\ 1\%$ compression

(a) DenseNet121,CIFAR100, 4% compression

(b) DenseNet121,CIFAR100, 10% compression

Figure 2: Training loss of DenseNet 121 on CIFAR100, at $4\%$, $10\%$
compression

(c) DenseNet121,CIFAR10, 4% compression

(d) DenseNet121,CIFAR10, 10% compression

Figure 3: Training loss of DenseNet 121 on CIFAR10, at $4\%$, $10\%$
compression

In this section, we describe our experimental setup, discuss the deep neural
network architectures we use and present simulation results to demonstrate the
performance of our proposed method. Our simulations have been performed on
NVIDIA GTX 1080 GPUs.

###  IV-A Experimental Setup

We test our CSGD-ASSS algorithm on neural network architectures ResNet 18,
ResNet 34 and DenseNet 121, on CIFAR 100 and CIFAR 10 datasets. Consistent
with compression schemes in previous works [8, 13], the compression is done at
each layer. As in [8], the layers with less than $1000$ parameters are not
compressed. We use a batch size of $64$ in our experiments and train for $90$
epochs. The training error is typically of the order of $10^{-2}$.

We set the initial value of $\alpha_{\mathrm{max}}=0.1$. In each subsequent
iteration, the value of $\alpha_{\mathrm{max}}$ is updated as
$\alpha_{\mathrm{max}}=\omega\alpha_{t-1}$, where $\alpha_{t-1}$ is the step-
size returned by the Armijo step-size search (Step 4) in CSGD-ASSS in the
previous iteration. In our simulations, $\omega=1.2$ and the step-size decay
factor used in the Armijo-step search, $\rho=0.8$. This renders the algorithm
computationally efficient for neural network training tasks, as discussed in
Section IV-B.

For the Armijo step-size search parameter $\sigma$, we use the value $0.1$ as
in non-compressed SGD with Armijo step-size search[15]. Motivated by the
analysis of scaled GD presented in Section IX in the Appendix, we set the
scaling factor $a$ to be a multiple of $\sigma$. In our simulations, we set
$a=3\sigma$ for all neural network training tasks.

In our experiments we choose arbitrary compression rates for the neural
networks. We train ResNet 34, ResNet 18 on CIFAR 100 and CIFAR 10 datasets at
compression ($\gamma$ values) $1.5\%$ and $10\%$, and DenseNet 121 on CIFAR
100 and CIFAR 10 at $4\%$ and $10\%$ compression. This means that, for
example, in ResNet 34, CSGD-ASSS uses only $1.5\%$ and $10\%$ of gradient
components in each layer. We compare our CSGD-ASSS algorithm with the non-
adaptive compressed SGD of [3] on typically used step-sizes $0.1,0.05,0.01$.
The reason for using the algorithm in [3] as a baseline for comparison is that
prevalent _non-adaptive_ compressed SGD algorithms build on the $top_{k}$
gradient compression operator with memory feedback introduced in [3].

###  IV-B Simulation Results

From Figures 1,3,3 , we observe that our proposed CSGD-ASSS algorithm (denoted
by $3\sigma$) outperforms fixed/non-adaptive step-size $top_{k}$ compressed
SGD with step-sizes $0.1,0.05,0.01$ (denoted by non-adap $0.1$, non-adap
$0.05$, non-adap $0.01$, respectively) on ResNet 34 and ResNet 18, on both the
CIFAR 100 and CIFAR 10 datasets in training at $1\%,$ compression. The CSGD-
ASSS algorithm also has the best performance on DenseNet 121 on the CIFAR
datasets at $4\%$ and $10\%$ compression. In the Appendix, we show in Figures
6,7 and Table I that the CSGD-ASSS algorithm outperforms non-adaptive
compressed SGD at $10\%$ compression on ResNet 18, ResNet 34 on CIFAR 100 and
CIFAR 10 datasets, and that the validation accuracy is also competitive.

Note on computational complexity: The Armijo step-size search of the CSGD-ASSS
algorithm with $\omega=1.2$ and $\rho=0.8$, on ResNets and DenseNets, on
average computes less than one additional forward pass compared to non-
adaptive compressed SGD. This means that each iteration of Step 4 of CSGD-ASSS
(Algorithm 2) involves the computation of the gradient once, and subsequently
multiplying the gradient with step-size $\alpha_{t}$ and evaluating the
stopping condition (Step 6) of the Armijo step-size search (Algorithm 1)
twice. Evaluating the gradient is computationally several orders more
expensive compared to a forward pass in the SGD algorithm; in the federated
learning [1] setup, the forward pass steps can be parallelized in the worker
nodes. With each gradient being several GigaBytes in size, and several hundred
worker nodes communicating with the master node, the communication time would
still remain the major bottleneck when implementing our proposed algorithm in
federated/distributed learning scenarios.

###  IV-C The Necessity of Scaling for Convergence of CSGD-ASSS

In this section, we illustrate through examples that scaling is necessary for
convergence of compressed SGD with Armijo step-size search. To this end, we
consider interpolated linear regression in the convex setting and neural-
networks in the non-convex setting as examples.

In interpolated linear regression, the loss function is

$\displaystyle f(x)=\frac{1}{n}\sum_{i=1}^{n}(\langle a_{i},x\rangle-
b_{i})^{2}.$ (16)

where $\exists\ x^{*}$ such that $\langle a_{i},x^{*}\rangle=b_{i}$, $\forall\
i\in[n]$. In our experiments, we choose $n=10000$,
$\\{a_{i},x\\}\in\mathbb{R}^{1024}$ and use $top_{k}$ compression with
compression ratio $\frac{k}{d}=1\%$. The elements of $x^{*}$ are generated
from $\mathcal{N}(0,1)$ and the elements of $a_{i}$ are distributed as
$\mathcal{N}(0,1)$ and $\mathcal{N}(0,10)$ in Figures 4(a) and 4(b),
respectively. The loss increases exponentially without scaling even in the
convex setting. This clearly demonstrates that for compressed SGD with Armijo
step-size search, scaling is a fundamental requirement and not just a proof
technicality. In Figure 4(c), the CSGD-ASSS algorithm is evaluated on
ResNet-34 and ResNet-18 on CIFAR-100 dataset with scaling $a=3\sigma$ and
$a=1$ (no scaling) at $\approx 1\%$ compression. The plot demonstrates that
the conclusions regarding the convergence of the CSGD-ASSS algorithm also hold
in (non-convex) neural network training tasks.

(a) Interpolated linear regression
vvvvvvv $a_{i}\in\mathcal{N}(0,1)$

(b) Interpolated linear regression
vvvvvvv $a_{i}\in\mathcal{N}(0,10)$

(c) ResNets,CIFAR100,1.5% comp- vvvvvvv-ression

Figure 4: Scaled vs non-scaled CSGD-ASSS at $\approx\ 1\%$ compression

##  V Conclusion

We have motivated and presented a scaling technique for Armijo step-size
search based adaptive gradient descent methods. We showed how the scaling
technique can be used in establishing convergence results, in convex, strongly
convex, and non-convex settings, when Armijo step-size search is applied in
the context of compressed SGD. In simulations, we have shown that our proposed
Compressed SGD with Armijo Step-Size Search and Scaling (CSGD-ASSS) algorithm
outperforms the corresponding non-adaptive compressed SGD algorithm on ResNet
18, ResNet 34 and DenseNet architectures trained on CIFAR 100 and CIFAR 10
datasets at various levels of compression. We have also demonstrated through
simulations the important role of scaling for convergence of compressed SGD
with Armijo step-size search. A distributed version of the CSGD-ASSS algorithm
is presented in the Appendix with convergence guarantees. For future work, one
could study the use of modifications such as local iterations, momentum, other
error-feedback operators, and adaptive gradient methods with the CSGD-ASSS
algorithm.

## References

  * [1] P. Kairouz, H. B. McMahan, B. Avent, and et.al, “Advances and open problems in federated learning,” _CoRR_ , vol. abs/1912.04977, 2019. [Online]. Available: http://arxiv.org/abs/1912.04977
  * [2] N. Dryden, T. Moon, S. A. Jacobs, and B. Van Essen, “Communication quantization for data-parallel training of deep neural networks,” in _2016 2nd Workshop on Machine Learning in HPC Environments (MLHPC)_ , 2016, pp. 1–8.
  * [3] A. F. Aji and K. Heafield, “Sparse communication for distributed gradient descent,” _CoRR_ , vol. abs/1704.05021, 2017. [Online]. Available: http://arxiv.org/abs/1704.05021
  * [4] S. U. Stich, J. Cordonnier, and M. Jaggi, “Sparsified SGD with memory,” in _NeurIPS - Advances in Neural Information Processing Systems_ , 2018, pp. 4448–4459.
  * [5] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” in _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31. Curran Associates, Inc., 2018\. [Online]. Available: https://proceedings.neurips.cc/paper/2018/file/314450613369e0ee72d0da7f6fee773c-Paper.pdf
  * [6] H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu, “Communication compression for decentralized training,” in _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31. Curran Associates, Inc., 2018. [Online]. Available: https://proceedings.neurips.cc/paper/2018/file/44feb0096faa8326192570788b38c1d1-Paper.pdf
  * [7] J. Bernstein, Y. Wang, K. Azizzadenesheli, and A. Anandkumar, “Sign sgd: compressed optimisation for non-convex problems,” _CoRR_ , vol. abs/1802.04434, 2018. [Online]. Available: http://arxiv.org/abs/1802.04434
  * [8] D. Basu, D. Data, C. Karakus, and S. Diggavi, “Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations,” in _Advances in Neural Information Processing Systems_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, Eds., vol. 32. Curran Associates, Inc., 2019. [Online]. Available: https://proceedings.neurips.cc/paper/2019/file/d202ed5bcfa858c15a9f383c3e386ab2-Paper.pdf
  * [9] H. Shokri Ghadikolaei, S. Stich, and M. Jaggi, “Lena: Communication-efficient distributed learning with self-triggered gradient uploads,” in _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Banerjee and K. Fukumizu, Eds., vol. 130. PMLR, 13–15 Apr 2021, pp. 3943–3951. [Online]. Available: https://proceedings.mlr.press/v130/shokri-ghadikolaei21a.html
  * [10] V. Gandikota, D. Kane, R. Kumar Maity, and A. Mazumdar, “VQSGD: Vector quantized stochastic gradient descent,” in _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , A. Banerjee and K. Fukumizu, Eds., vol. 130. PMLR, 13–15 Apr 2021, pp. 2197–2205. [Online]. Available: https://proceedings.mlr.press/v130/gandikota21a.html
  * [11] D. Kovalev, A. Koloskova, M. Jaggi, P. Richtarik, and S. Stich, “A linearly convergent algorithm for decentralized optimization: Sending less bits for free!” in _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Banerjee and K. Fukumizu, Eds., vol. 130. PMLR, 13–15 Apr 2021, pp. 4087–4095. [Online]. Available: https://proceedings.mlr.press/v130/kovalev21a.html
  * [12] T. Lin, S. P. Karimireddy, S. Stich, and M. Jaggi, “Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data,” in _Proceedings of the 38th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, M. Meila and T. Zhang, Eds., vol. 139. PMLR, 18–24 Jul 2021, pp. 6654–6665. [Online]. Available: https://proceedings.mlr.press/v139/lin21c.html
  * [13] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi, “Error feedback fixes SignSGD and other gradient compression schemes,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, 09–15 Jun 2019, pp. 3252–3261. [Online]. Available: https://proceedings.mlr.press/v97/karimireddy19a.html
  * [14] A. Koloskova, S. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, 09–15 Jun 2019, pp. 3478–3487. [Online]. Available: https://proceedings.mlr.press/v97/koloskova19a.html
  * [15] S. Vaswani, A. Mishkin, I. H. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien, “Painless stochastic gradient: Interpolation, line-search, and convergence rates,” _CoRR_ , vol. abs/1905.09997, 2019. [Online]. Available: http://arxiv.org/abs/1905.09997
  * [16] B. Dubois-Taine, S. Vaswani, R. Babanezhad, M. Schmidt, and S. Lacoste-Julien, “SVRG meets adagrad: Painless variance reduction,” _CoRR_ , vol. abs/2102.09645, 2021. [Online]. Available: https://arxiv.org/abs/2102.09645
  * [17] S. Vaswani, F. Kunstner, I. H. Laradji, S. Y. Meng, M. Schmidt, and S. Lacoste-Julien, “Adaptive gradient methods converge faster with over-parameterization (and you can do a line-search),” _CoRR_ , vol. abs/2006.06835, 2020. [Online]. Available: https://arxiv.org/abs/2006.06835
  * [18] L. Armijo, “Minimization of functions having Lipschitz continuous first partial derivatives.” _Pacific Journal of Mathematics_ , vol. 16, no. 1, pp. 1 – 3, 1966. [Online]. Available: https://doi.org/
  * [19] J. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization,” _Journal of Machine Learning Research_ , vol. 12, pp. 2121–2159, 07 2011.
  * [20] S. J. Reddi, S. Kale, and S. Kumar, “On the convergence of adam and beyond,” _CoRR_ , vol. abs/1904.09237, 2019. [Online]. Available: http://arxiv.org/abs/1904.09237
  * [21] R. Bassily, M. Belkin, and S. Ma, “On exponential convergence of sgd in non-convex over-parametrized learning,” _arXiv preprint arXiv:1811.02564_ , 2018.
  * [22] C. Liu and M. Belkin, “Mass: an accelerated stochastic method for over-parametrized learning,” _CoRR_ , vol. abs/1810.13395, 2018. [Online]. Available: http://arxiv.org/abs/1810.13395
  * [23] S. Ma, R. Bassily, and M. Belkin, “The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning,” in _Proceedings of the 35th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, J. Dy and A. Krause, Eds., vol. 80. PMLR, 10–15 Jul 2018, pp. 3325–3334. [Online]. Available: https://proceedings.mlr.press/v80/ma18a.html
  * [24] S. Arora, S. Du, W. Hu, Z. Li, and R. Wang, “Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, 09–15 Jun 2019, pp. 322–332. [Online]. Available: https://proceedings.mlr.press/v97/arora19a.html
  * [25] A. Montanari and Y. Zhong, “The interpolation phase transition in neural networks: Memorization and generalization under lazy training,” _arXiv preprint arXiv:2007.12826_ , 2020.
  * [26] T. Liang and A. Rakhlin, “Just interpolate: Kernel “ridgeless” regression can generalize,” _The Annals of Statistics_ , vol. 48, no. 3, Jun 2020. [Online]. Available: http://dx.doi.org/10.1214/19-AOS1849
  * [27] P. Bartlett, Y. Freund, W. S. Lee, and R. E. Schapire, “Boosting the margin: a new explanation for the effectiveness of voting methods,” _The Annals of Statistics_ , vol. 26, no. 5, pp. 1651 – 1686, 1998. [Online]. Available: https://doi.org/10.1214/aos/1024691352
  * [28] S. Shalev-Shwartz and S. Ben-David, _Understanding Machine Learning: From Theory to Algorithms_. Cambridge University Press, 2014.
  * [29] C. Liu and M. Belkin, “Mass: an accelerated stochastic method for over-parametrized learning,” _CoRR_ , vol. abs/1810.13395, 2018. [Online]. Available: http://arxiv.org/abs/1810.13395
  * [30] D. Bertsekas, _Nonlinear Programming_. Athena Scientific, 1995.
  * [31] H. Mania, X. Pan, D. Papailiopoulos, B. Recht, K. Ramchandran, and M. I. Jordan, “Perturbed iterate analysis for asynchronous stochastic optimization,” _SIAM J. Optim._ , vol. 27, pp. 2202–2229, 2017.
  * [32] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” in _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31, 2018. [Online]. Available: https://proceedings.neurips.cc/paper/2018/file/314450613369e0ee72d0da7f6fee773c-Paper.pdf

Appendix

##  VI Mathematical Preliminaries

We begin by stating some useful results in Lemmas 4 and 5, whose proofs are
straightforward.

######  Lemma 4.

For vectors $v_{1},v_{2}\in\mathbb{R}^{n}$, and $p>0$,

$2\langle v_{1},v_{2}\rangle\leq p\lVert v_{1}\rVert^{2}+\frac{1}{p}\lVert
v_{2}\rVert^{2}$ (17)

######  Lemma 5.

For vectors $v_{1},v_{2}\in\mathbb{R}^{n}$, and $r>0$,

$\lVert v_{1}+v_{2}\rVert^{2}\leq(1+r)\lVert
v_{1}\rVert^{2}+(1+\frac{1}{r})\lVert v_{2}\rVert^{2}$ (18)

######  Lemma 6.

In CSGD-ASSS algorithm, $m_{t}=x_{t}-\hat{x}_{t}$

###### Proof.

See [4]. ∎

######  Lemma 7.

For $top_{k}$ compression operator with $\gamma=\frac{k}{d}$, and a vector
$v_{1}\in\mathbb{R}^{n}$,

$\lVert v_{1}-top_{k}(v_{1})\rVert^{2}\leq(1-\gamma)||v_{1}||^{2}$ (19)

###### Proof.

See [8]. ∎

######  Lemma 8.

The Armijo step-size search stopping condition for a data-point $i_{t}$
sampled at time $t$

$f_{i_{t}}(x_{t}-\alpha_{t}\nabla
f_{i_{t}}(x_{t}))-f_{i_{t}}(x_{t})\leq-\sigma\alpha_{t}||\nabla
f_{i_{t}}(x_{t})||^{2}$ (20)

is satisfied by all $\alpha_{t}\in[0,\frac{2(1-\sigma)}{L_{\mathrm{max}}}]$
where $L_{\mathrm{max}}=\max_{i\in[n]}{\\{L_{i}\\}}$

###### Proof.

See [18],[15]. ∎

######  Lemma 9.

The Armijo step-size search rule returns a step-size
$\alpha_{t}\in[\tilde{\alpha}_{\mathrm{min}}\rho,\alpha_{\mathrm{max}}]$ where
$\tilde{\alpha}_{\mathrm{min}}\triangleq\frac{2(1-\sigma)}{L_{\mathrm{max}}}$

###### Proof.

See [18] ∎

######  Remark 3.

In our proofs, for the Armijo step-size search
$\alpha_{\mathrm{min}}=\tilde{\alpha}_{\mathrm{min}}\rho$ and
$\alpha_{\mathrm{min}}\leq\alpha_{t}\leq\alpha_{\mathrm{max}}$. The step-size
$\eta_{t}$ for CSGD-ASSS is obtained by $\eta_{t}=a\alpha_{t}$ and hence
$\eta_{t}\in[\eta_{\mathrm{min}},\eta_{\mathrm{max}}]$, where
$\eta_{\mathrm{min}}=a\alpha_{\mathrm{min}}$ and
$\eta_{\mathrm{max}}=a\alpha_{\mathrm{max}}$.

##  VII Proofs for the CSGD-ASSS Algorithm

We first prove Theorem 2, since this proof is useful in the proofs of Theorems
1, 3.

###  VII-A Proof of Theorem 2

###### Proof.

From perturbed iterate analysis,
$\hat{x}_{t+1}\triangleq\hat{x}_{t}-\eta_{t}\nabla f_{i_{t}}(x_{t})$ where
$i_{t}$ is the data-point sampled at time $t$ and $\hat{x}_{0}=x_{0}$. Hence,

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}$
$\displaystyle=||\hat{x}_{t}-x^{*}-\eta_{t}\nabla f_{i_{t}}(x_{t})||^{2}$ (21)
$\displaystyle=||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\langle\hat{x}_{t}-x^{*},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle$
$\displaystyle=||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\langle\hat{x}_{t}-x_{t}+x_{t}-x^{*},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle$
$\displaystyle=||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\langle\hat{x}_{t}-x_{t},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle-2\langle x_{t}-x^{*},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle$
$\displaystyle=||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\langle\hat{x}_{t}-x_{t},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle+2\langle x^{*}-x_{t},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle.$

If $f_{i_{t}}$ is $\mu_{i_{t}}$-strongly convex,

$\langle x^{*}-x_{t},\nabla f_{i_{t}}(x_{t})\rangle\leq
f_{i_{t}}(x^{*})-f_{i_{t}}(x_{t})-\frac{\mu_{i_{t}}}{2}||x^{*}-x_{t}||^{2}.$
(22)

If $f_{i_{t}}$ is convex but not strongly convex, then $\mu_{i_{t}}=0$. In the
statement of the theorem, the only assumption is that $\exists\ i\in[n]$ such
that $\mu_{i}>0$.

From triangle inequality,

$-||x^{*}-x_{t}||^{2}\leq||x_{t}-\hat{x}_{t}||^{2}-\frac{1}{2}||\hat{x}_{t}-x^{*}||^{2}.$
(23)

Substituting (23) in (22) and $m_{t}=x_{t}-\hat{x}_{t}$ (by Lemma 6) and
defining $e_{t}\triangleq f_{i_{t}}(x_{t})-f_{i_{t}}(x^{*})$,

$\displaystyle 2\langle x^{*}-x_{t},\eta_{t}\nabla f_{i_{t}}(x_{t})\rangle$
$\displaystyle\leq
2\eta_{t}(f_{i_{t}}(x^{*})-f_{i_{t}}(x_{t}))+\mu_{i_{t}}\eta_{t}\left(||x_{t}-\hat{x}_{t}||^{2}-\frac{1}{2}||\hat{x}_{t}-x^{*}||^{2}\right)$
(24)
$\displaystyle=2\eta_{t}(-e_{t})+\mu_{i_{t}}\eta_{t}||m_{t}||^{2}-\frac{\mu_{i_{t}}}{2}\eta_{t}||\hat{x}_{t}-x^{*}||^{2}.$

Hence,

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}$
$\displaystyle\leq||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\langle\hat{x}_{t}-x_{t},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle-2\eta_{t}e_{t}+\mu_{i_{t}}\eta_{t}||m_{t}||^{2}$ (25)
$\displaystyle\hskip
20.00003pt-\frac{\mu_{i_{t}}\eta_{t}}{2}||\hat{x}_{t}-x^{*}||^{2}$
$\displaystyle=(1-\frac{\mu_{i_{t}}\eta_{t}}{2})||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\eta_{t}e_{t}+\mu_{i_{t}}\eta_{t}||m_{t}||^{2}$
$\displaystyle\hskip 20.00003pt+2\langle x_{t}-\hat{x}_{t},\eta_{t}\nabla
f_{i_{t}}(x_{t})\rangle.$

From Lemma 4,

$2\eta_{t}\langle x_{t}-\hat{x}_{t},\nabla f_{i_{t}}(x_{t})\rangle\leq
q_{t}\eta_{t}||x_{t}-\hat{x}_{t}||^{2}+\frac{\eta_{t}}{q_{t}}||\nabla
f_{i_{t}}(x_{t})||^{2},\;\;\forall q_{t}>0.$ (26)

Substituting in (25),

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}$
$\displaystyle\leq\left(1-\frac{\mu_{i_{t}}\eta_{t}}{2}\right)||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\eta_{t}e_{t}+\mu_{i_{t}}\eta_{t}||m_{t}||^{2}$ (27)
$\displaystyle\hskip
20.00003pt+q_{t}\eta_{t}||x_{t}-\hat{x}_{t}||^{2}+\frac{\eta_{t}}{q_{t}}||\nabla
f_{i_{t}}(x_{t})||^{2}.$

From the compression property in Lemma 7 and the memory update step
$m_{t+1}=(m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t}))-top_{k}(m_{t}+\eta_{t}\nabla
f_{i_{t}}(x_{t}))$ in the CSGD-ASSS algorithm,

$\displaystyle||m_{t+1}||^{2}$ $\displaystyle=\lVert(m_{t}+\eta_{t}\nabla
f_{i_{t}}(x_{t}))-top_{k}(m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t}))\rVert^{2}$
(28) $\displaystyle\leq(1-\gamma)||m_{t}+\eta_{t}\nabla
f_{i_{t}}(x_{t})||^{2}.$

From Lemma 5,

$\lVert m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t})\rVert^{2}\leq(1+r)\lVert
m_{t}\rVert^{2}+(1+\frac{1}{r})\eta_{t}^{2}\lVert\nabla
f_{i_{t}}(x_{t})\rVert^{2},\ \forall\ \ r>0.$ (29)

Substituting this in (28),

$\displaystyle||m_{t+1}||^{2}$
$\displaystyle\leq(1-\gamma)(1+r)||m_{t}||^{2}+(1-\gamma)(1+\frac{1}{r})\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}$ (30)

for some $r>0$. Adding (27) and (30), we obtain

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}$
$\displaystyle\leq(1-\frac{\mu_{i_{t}}\eta_{t}}{2})||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\eta_{t}e_{t}$ (31)
$\displaystyle+\mu_{i_{t}}\eta_{t}||m_{t}||^{2}+q_{t}\eta_{t}||x_{t}-\hat{x}_{t}||^{2}+\frac{1}{q_{t}}\eta_{t}||\nabla
f_{i_{t}}(x_{t})||^{2}$ $\displaystyle+(1-\gamma)(1+r)||m_{t}||^{2}$
$\displaystyle+(1-\gamma)(1+\frac{1}{r})\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}.$

Setting $p\triangleq q_{t}a\alpha_{t}$ where $p\in\mathbb{R}^{+}$ ($p$ can be
set independent of $t$ since $q_{t}$ is arbitrary),

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}$
$\displaystyle\leq(1-\frac{\mu_{i_{t}}\eta_{t}}{2})||\hat{x}_{t}-x^{*}||^{2}+\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}-2\eta_{t}e_{t}+\mu_{i_{t}}\eta_{t}||m_{t}||^{2}$ (32)
$\displaystyle+\frac{p}{a\alpha_{t}}\eta_{t}||x_{t}-\hat{x}_{t}||^{2}+\frac{a\alpha_{t}}{p}\eta_{t}||\nabla
f_{i_{t}}(x_{t})||^{2}$ $\displaystyle+(1-\gamma)(1+r)||m_{t}||^{2}$
$\displaystyle+(1-\gamma)(1+\frac{1}{r})\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}.$

Consider the Armijo step-size search stopping condition

$f_{i_{t}}(\tilde{x}_{t+1})-f_{i_{t}}(x_{t})\leq-\sigma\alpha_{t}||\nabla
f_{i_{t}}(x_{t})||^{2}.$ (33)

This implies,

$\displaystyle\eta_{t}^{2}||\nabla
f_{i_{t}}(x_{t})||^{2}\overset{(\mathbf{\phi})}{\leq}\frac{a^{2}\alpha_{t}}{\sigma}(f_{i_{t}}(x_{t})-f_{i_{t}}(x^{*})).$
(34)

Note that $(\phi)$ holds due to the interpolation condition. Substituting (34)
in (32),

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}$
$\displaystyle\leq(1-\frac{\mu_{i_{t}}\eta_{t}}{2})||\hat{x}_{t}-x^{*}||^{2}+\Big{(}\mu_{i_{t}}\eta_{t}+p+(1-\gamma)(1+r)\Big{)}||m_{t}||^{2}$
(35)
$\displaystyle-\alpha_{t}e_{t}\Big{(}2a-\frac{a^{2}}{\sigma}-\frac{a^{2}}{\sigma
p}-(1-\gamma)(1+\frac{1}{r})\frac{a^{2}}{\sigma}\Big{)}.$

Let $\mu_{\mathrm{max}}\triangleq\max_{i\in[n]}\mu_{i}$. Using
$\eta_{t}=a\alpha_{t}$ and $\alpha_{t}\leq\alpha_{\mathrm{max}}$, where
$\alpha_{\mathrm{max}}$ is the starting value of the Armijo step-size search
algorithm, we get

$\displaystyle\Big{(}\mu_{i_{t}}\eta_{t}+p+(1-\gamma)(1+r)\Big{)}\leq\Big{(}\mu_{\mathrm{max}}a\alpha_{\mathrm{max}}+p+(1-\gamma)(1+r)\Big{)}.$
(36)

Notice that in (35), $p,r$ can be chosen arbitrarily. Define
$\beta_{1}(p,r),\tilde{a}_{1}(p,r)$ and $\tilde{a}_{2}(p,r)$ as

$\displaystyle\beta_{1}(p,r)\triangleq\Big{(}\mu_{\mathrm{max}}a\alpha_{\mathrm{max}}+p+(1-\gamma)(1+r)\Big{)}$
(37) $\displaystyle\tilde{a}_{1}(p,r)\triangleq
2/\Big{(}\frac{1}{\sigma}+\frac{1}{\sigma
p}+\frac{(1-\gamma)(1+\frac{1}{r})}{\sigma}\Big{)}$
$\displaystyle\tilde{a}_{2}(p,r)\triangleq\Big{(}2a-\frac{a^{2}}{\sigma}-\frac{a^{2}}{\sigma
p}-(1-\gamma)(1+\frac{1}{r})\frac{a^{2}}{\sigma}\Big{)}$

If $a<\tilde{a}_{1}(p,r)$, then $\tilde{a}_{2}(p,r)>0$. If $p,r,a$ are chosen
such that $\beta_{1}(p,r)<1$ and $a<\tilde{a}_{1}(p,r)$, (35) simplifies to

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}$
$\displaystyle\leq(1-\frac{\mu_{i_{t}}a\alpha_{t}}{2})||\hat{x}_{t}-x^{*}||^{2}+\beta_{1}(p,r)||m_{t}||^{2}.$
(38)

The existence of such $p,r,a$ is proven in Lemma 12. The step-size in the
Armijo step-size search satisfies
$\tilde{\alpha}_{\mathrm{min}}\rho\leq\alpha_{t}$. Using this property and
taking expectation with respect to the data point $i_{t}$ conditioned on the
entire past therein,

$\displaystyle E_{i_{t}}[||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}]$
$\displaystyle\leq(1-\frac{E_{i_{t}}[\mu_{i_{t}}]a\alpha_{\mathrm{min}}\rho}{2})||\hat{x}_{t}-x^{*}||^{2}+\beta_{1}(p,r)||m_{t}||^{2}.$
(39)

By assumption, $\exists\ i\in[n]$ such that $\mu_{i}>0$. Hence,

$\bar{\mu}=E_{i_{t}}[\mu_{i}]=\frac{\sum_{i=1}^{n}\mu_{i}}{n}>0.$

This implies that

$0<(\bar{\mu}a\tilde{\alpha}_{\mathrm{min}}\rho)/2=\bar{\mu}a\frac{1}{L_{\mathrm{max}}}(1-\sigma)\rho<1,$

since $\bar{\mu}\leq L_{\mathrm{max}}$, the values $\sigma,\rho<1$ and $a<1$
by Lemma 12. Let

$\beta_{2}\triangleq(1-\frac{\bar{\mu}a\tilde{\alpha}_{\mathrm{min}}\rho}{2}).$

It follows that $0<\beta_{2}<1$. Let
$\hat{\beta}\triangleq\max\\{\beta_{1}(p,r),\beta_{2}\\}$. Since
$\beta_{1}(p,r)<1$, $\beta_{2}<1$, this implies $\hat{\beta}<1$. Using this in
(39),

$\displaystyle E_{i_{t}}[||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}]$
$\displaystyle\leq\hat{\beta}(||\hat{x}_{t}-x^{*}||^{2}+||m_{t}||^{2}).$ (40)

Taking expectation with respect to the entire process,

$\displaystyle E[||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}]$
$\displaystyle\leq\hat{\beta}E[(||\hat{x}_{t}-x^{*}||^{2}+||m_{t}||^{2})].$
(41)

Hence,

$\displaystyle E[||\hat{x}_{t}-x^{*}||^{2}+||m_{t}||^{2}]$
$\displaystyle\leq(\hat{\beta})^{t}E[(||\hat{x}_{0}-x^{*}||^{2}+||m_{0}||^{2})].$
(42)

Since $\|m_{t}\|=\|x_{t}-\hat{x}_{t}\|$,

$||x_{t}-x^{*}||^{2}\leq
2(||x_{t}-\hat{x}_{t}||^{2})+2(||\hat{x}_{t}-x^{*}||^{2})=2(||m_{t}||^{2}+||\hat{x}_{t}-x^{*}||^{2}).$
(43)

At $t=0$, $m_{0}=0$ and hence,

$\displaystyle E[||x_{t}-x^{*}||^{2}]$ $\displaystyle\leq
2(E[||\hat{x}_{t}-x^{*}||^{2}+||m_{t}||^{2}])$ (44) $\displaystyle\leq
2(\hat{\beta})^{t}E[(||\hat{x}_{0}-x^{*}||^{2})].$

In the perturbed iterate analysis, $\hat{x}_{0}=x_{0}$. Substituting this we
get,

$\displaystyle E[||x_{t}-x^{*}||^{2}]\leq
2(\hat{\beta})^{t}E[(||{x}_{0}-x^{*}||^{2})].$ (45)

Hence, we obtain the geometric convergence stated in the theorem. ∎

To show the existence of $p,r,a$ such that $\beta_{1}(p,r)<1$ and
$a<\tilde{a}_{1}(p,r)$ we prove Lemma 12, which is based on Lemmas 10 and 11
proved below.

######  Lemma 10.

Consider the convex optimization problem with variables
$s,z,\psi\in\mathbb{R}$ and $0<\psi<1$.

$\displaystyle\min_{s,z}$ $\displaystyle g(s,z)=\frac{1}{s}+\psi\frac{1}{z}$
(46) $\displaystyle\mathrm{s.t.}$ $\displaystyle(s+\psi(1+z))\leq 1$
$\displaystyle s\geq 0,z\geq 0$

The function $g(s,z)$ attains the minimum value
$\frac{(1+\psi)^{2}}{(1-\psi)}$ at
$(s^{*},z^{*})=(\frac{1-\psi}{1+\psi},\frac{1-\psi}{1+\psi})$.

###### Proof.

To solve the convex optimization problem, we consider the dual of the problem
and apply the approach of Proposition 3.3.1 in [30].

The constrains $s\geq 0$ and $z\geq 0$ are inactive since $s=0$ or $z=0$
implies the objective $g(s,z)=\infty$. Since only $(s+\psi(1+z))\leq 1$ can be
active, all local minimum are regular.

Consider the Lagrangian

$L(s,z,\lambda_{1},\lambda_{2},\lambda_{3})=g(s,z)+\lambda_{1}(s+\psi(1+z)-1)+\lambda_{2}(-s)+\lambda_{3}(-z)$
(47)

The values $s^{*},z^{*}$ are a local minimum of the convex problem (46) if
$\exists\lambda_{1}^{*},\lambda_{2}^{*},\lambda_{3}^{*}$ such that
$\lambda_{2}^{*}=0,\lambda_{3}^{*}=0$ and
$\nabla_{s,z}L(s^{*},z^{*},\lambda_{1}^{*},\lambda_{2}^{*},\lambda_{3}^{*})=0$.

Solving for $L(s^{*},z^{*},\lambda_{1}^{*},\lambda_{2}^{*},\lambda_{3}^{*})=0$
we get $s^{*}=z^{*}$ and $\lambda_{1}^{*}=\frac{1}{s^{*}}$ at any local
minimum. Hence $\lambda_{1}^{*}>0$ which implies that the constraint
$(s^{*}+\psi(1+z^{*}))\leq 1$ is active or tight.

Substituting $s^{*}=z^{*}$ in the active constraint,

$s^{*}+\psi(1+s^{*})=1.$ (48)

This implies

$s^{*}=z^{*}=\frac{1-\psi}{1+\psi}.$ (49)

Hence there is a unique local minimum. The minimum value of the objective
$g(s,z)$ subject to the constraints is

$\displaystyle g(s^{*},z^{*})$
$\displaystyle=\frac{1}{s^{*}}+\psi\frac{1}{z^{*}}$ (50)
$\displaystyle=\frac{1}{s^{*}}(1+\psi)$
$\displaystyle=\frac{(1+\psi)^{2}}{1-\psi}.$

∎

######  Lemma 11.

Let $f_{i}(x)$, $i\in[n]$ be a set of $\mu_{i}$ strong-convex functions s.t
$\mu_{i}>0$ for some $i>0$ and
$\mu_{\mathrm{max}}\triangleq\max_{i\in[n]}\mu_{i}$. Then
$\mu_{\mathrm{max}}\leq\xi$, $\forall\ \xi>0$ is justified.

###### Proof.

The case where $\xi\geq\mu_{\mathrm{max}}$ is trivial. Hence consider the case
where $\xi<\mu_{\mathrm{max}}$. Without loss of generality, let $\xi<\mu_{1}$
where $\mu_{1}$ is the strong convexity constant of $f_{1}$. This also implies
that

$\displaystyle\nabla^{2}f_{1}(x)\succeq\mu_{1}I.$ (51)

Since $\xi<\mu_{1}$, it also implies that

$\displaystyle\nabla^{2}f_{1}(x)\succeq\xi I.$ (52)

Hence $f_{1}$ is $\xi$ strongly convex. It is thus justified to assume
$\mu_{1}=\xi$ and set $\mu_{\mathrm{max}}\leq\xi$. ∎

We show the following lemma based on Lemmas 10 and 11.

######  Lemma 12.

Let $\zeta\triangleq\frac{\sigma\gamma}{(2-\gamma)}$. For all
$0<\epsilon<\zeta$ and $a\leq\zeta-\epsilon$, $\exists\
(p{(\epsilon)},r{(\epsilon)})$ such that
$\beta_{1}(p{(\epsilon)},r{(\epsilon)})<1$ and
$a<\tilde{a}_{1}(p{(\epsilon)},r{(\epsilon)})$, where
$p{(\epsilon)},r{(\epsilon)}$ are functions of $\epsilon$.

###### Proof.

The functions $\beta_{1}(p,r)$ and $\tilde{a}_{1}(p,r)$ have been defined as

$\displaystyle\beta_{1}(p,r)$
$\displaystyle=\Big{(}\mu_{\mathrm{max}}a\alpha_{\mathrm{max}}+p+(1-\gamma)(1+r)\Big{)}$
(53) $\displaystyle\tilde{a}_{1}(p,r)$
$\displaystyle=2/\Big{(}\frac{1}{\sigma}+\frac{1}{\sigma
p}+\frac{(1-\gamma)(1+\frac{1}{r})}{\sigma}\Big{)}.$

Consider the convex problem

$\displaystyle\sup_{p,r}\tilde{a}_{1}(p,r)=2\sigma/\Big{(}1+\frac{1}{p}+(1-\gamma)(1+\frac{1}{r})\Big{)}$
(54) $\displaystyle\mathrm{s.t.}\ (p+(1-\gamma)(1+r))<1$ $\displaystyle p\geq
0,r\geq 0$

Equivalently, the problem can be stated as

$\displaystyle\inf_{p,r}\Big{(}\frac{1}{p}+(1-\gamma)(1+\frac{1}{r})\Big{)}$
(55) $\displaystyle\mathrm{s.t.}\ (p+(1-\gamma)(1+r))<1$ $\displaystyle p\geq
0,r\geq 0$

Using Lemma 10 with $\psi=(1-\gamma)$, the infimum is
$\frac{(2-\gamma)^{2}}{\gamma}+(1-\gamma)$ and the infimum is attained at a
point $(p,r)$ such that $(p+(1-\gamma)(1+r))=1$. Hence, by substituting the
infimum of (55) in (54),

$\displaystyle\zeta\triangleq\sup_{p,r}\tilde{a}_{1}(p,r)=\frac{\sigma\gamma}{(2-\gamma)},$
(56)

subject to the constraints. By the continuity of the function
$2\sigma/\Big{(}1+\frac{1}{p}+(1-\gamma)(1+\frac{1}{r})\Big{)}$ at $p>0,r>0$
and since $(p+(1-\gamma)(1+r))<1,p\geq 0,r\geq 0$ is a region in the first
quadrant and $\zeta$ is attained at $(p^{*},r^{*})$ such that
$(p^{*}+(1-\gamma)(1+r^{*}))=1$, for all $\epsilon>0$,
$\exists~{}(p{(\epsilon)},r{(\epsilon)})$ and $0<\delta<1$ such that

$\displaystyle a_{1}(p{(\epsilon)},r{(\epsilon)})>\zeta-\epsilon$ (57)
$\displaystyle(p{(\epsilon)}+(1-\gamma)(1+r{(\epsilon)}))=1-\delta$

Let $\mu_{\mathrm{max}}\leq\frac{(\delta-\tau)}{\alpha_{\mathrm{max}}\zeta}$
for some $0<\tau<\delta$. This assumption is justified by Lemma 11. Hence,

$\displaystyle\beta_{1}(p{(\epsilon)},r{(\epsilon)})$
$\displaystyle\leq\Big{(}\mu_{\mathrm{max}}\zeta\alpha_{\mathrm{max}}+p{(\epsilon)}+(1-\gamma)(1+r{(\epsilon)})\Big{)}$
(58) $\displaystyle\leq(1-\tau)$ $\displaystyle<1.$

To conclude, we have shown that for any $a\leq\zeta-\epsilon$, $\exists\
(p(\epsilon),r(\epsilon))$ such that
$\tilde{a}_{1}(p(\epsilon),r(\epsilon))>\zeta-\epsilon$ and
$\beta_{1}(p(\epsilon),r(\epsilon))<1$. This implies that $\exists\
(p(\epsilon),r(\epsilon))$ s.t.

$\displaystyle a<\tilde{a}_{1}(p(\epsilon),r(\epsilon))$ (59)
$\displaystyle\beta_{1}(p(\epsilon),r(\epsilon))<1.$

∎

######  Remark 4.

In the proof of Theorem 2, for all $a<\zeta$, $\exists$ $p,r$ such that
$a<\tilde{a}_{1}(p,r)$ and $\beta_{1}(p,r)<1$ by Lemma 12 and hence (38) of
Theorem 2 holds.

###  VII-B Proof of Theorem 1

###### Proof.

For the convex case, (35) holds with $\mu_{i_{t}}=0$. Hence,

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}$
$\displaystyle\leq||\hat{x}_{t}-x^{*}||^{2}+\Big{(}p+(1-\gamma)(1+r)\Big{)}||m_{t}||^{2}$
(60)
$\displaystyle-\alpha_{t}e_{t}\Big{(}2a-\frac{a^{2}}{\sigma}-\frac{a^{2}}{\sigma
p}-(1-\gamma)(1+\frac{1}{r})\frac{a^{2}}{\sigma}\Big{)}.$

As in Theorem 2, we define

$\displaystyle\tilde{a}_{1}(p,r)=2/\Big{(}\frac{1}{\sigma}+\frac{1}{\sigma
p}+\frac{(1-\gamma)(1+\frac{1}{r})}{\sigma}\Big{)}$ (61)
$\displaystyle\tilde{a}_{2}(p,r)=\Big{(}2a-\frac{a^{2}}{\sigma}-\frac{a^{2}}{\sigma
p}-(1-\gamma)(1+\frac{1}{r})\frac{a^{2}}{\sigma}\Big{)}.$

If $a<\tilde{a}_{1}(p,r)$, then $\tilde{a}_{2}(p,r)>0$. Define
$\beta_{3}(p,r)$ as

$\displaystyle\beta_{3}(p,r)\triangleq(p+(1-\gamma)(1+r)).$ (62)

From Lemma 12, $\exists\ (p(\epsilon),r(\epsilon))$ such that

$\displaystyle\Big{(}p(\epsilon)+(1-\gamma)(1+r(\epsilon))\Big{)}$
$\displaystyle=1-\delta<1,$ (63)
$\displaystyle\tilde{a}_{1}(p(\epsilon),r(\epsilon))$
$\displaystyle>\zeta-\epsilon.$

Choosing $(p,r)=(p(\epsilon),r(\epsilon))$, (60) becomes

$\displaystyle||\hat{x}_{t+1}-x^{*}||^{2}+||m_{t+1}||^{2}$
$\displaystyle\leq||\hat{x}_{t}-x^{*}||^{2}+||m_{t}||^{2}$ (64)
$\displaystyle-\alpha_{t}e_{t}\tilde{a}_{2}(p(\epsilon),r(\epsilon)).$

Note that if $a\leq\zeta-\epsilon$, then
$a<\tilde{a}_{1}(p(\epsilon),r(\epsilon))$ and this implies
$\tilde{a}_{2}(p(\epsilon),r(\epsilon))>0$.

Bounding $\alpha_{t}$ by $\alpha_{\mathrm{min}}\rho\leq\alpha_{t}$,

$\displaystyle\alpha_{\mathrm{min}}\rho(f_{i_{t}}(x_{t})-f_{i_{t}}(x^{*}))\tilde{a}_{2}(p(\epsilon),r(\epsilon))$
$\displaystyle\leq||\hat{x}_{t}-x^{*}||^{2}-||\hat{x}_{t+1}-x^{*}||^{2}$ (65)
$\displaystyle+||m_{t}||^{2}-||m_{t+1}||^{2}.$

Taking expectation $E_{i_{t}}$ with respect to the data point $i_{t}$,
conditioned on the entire past therein,

$\displaystyle\alpha_{\mathrm{min}}\rho(f(x_{t})-f(x^{*}))\tilde{a}_{2}(p(\epsilon),r(\epsilon))$
$\displaystyle\leq||\hat{x}_{t}-x^{*}||^{2}-E_{i_{t}}[||\hat{x}_{t+1}-x^{*}||^{2}]$
(66) $\displaystyle+||m_{t}||^{2}-E_{i_{t}}[||m_{t+1}||^{2}].$

Taking expectation with respect to the entire process, and averaging over the
time horizon $T$,

$\displaystyle\alpha_{\mathrm{min}}\rho\frac{1}{{T}}\sum_{t=0}^{T-1}(E[f(x_{t})]-E[f(x^{*})])\tilde{a}_{2}(p(\epsilon),r(\epsilon))$
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}(E[||\hat{x}_{t}-x^{*}||^{2}]-E[||\hat{x}_{t+1}-x^{*}||^{2}])$
(67) $\displaystyle\hskip
20.00003pt+\frac{1}{T}\sum_{t=0}^{T-1}(E[||m_{t}||^{2}]-E[||m_{t+1}||^{2}])$
$\displaystyle\leq\frac{1}{T}(E[||\hat{x}_{0}-x^{*}||^{2}]-E[||\hat{x}_{T}-x^{*}||^{2}])$
$\displaystyle\hskip
20.00003pt+\frac{1}{T}(E[||m_{0}||^{2}]-E[||m_{T}||^{2}]).$

Since $f$ is convex, by Jensen’s inequality,

$E[f(\frac{1}{T}{\sum_{t=0}^{T-1}x_{t}})]\leq\frac{1}{T}\sum_{t=0}^{T-1}E[f(x_{t})].$

Thus,

$\displaystyle\alpha_{\mathrm{min}}\rho(E[f(\frac{1}{T}{\sum_{t=0}^{T-1}x_{t}})]-E[f(x^{*})])\tilde{a}_{2}(p(\epsilon),r(\epsilon))$
$\displaystyle\leq\frac{1}{T}(E[||\hat{x}_{0}-x^{*}||^{2}])$ (68)
$\displaystyle+\frac{1}{T}(E[||m_{0}||^{2}]).$

Since $\hat{x}_{0}=x_{0}$ and $m_{0}=0$, (68) simplifies to

$\displaystyle\alpha_{\mathrm{min}}\rho(E[f(\frac{1}{T}{\sum_{t=0}^{T-1}x_{t}})]-E[f(x^{*})])\tilde{a}_{2}(p(\epsilon),r(\epsilon))$
$\displaystyle\leq\frac{1}{T}(E[||{x}_{0}-x^{*}||^{2}]).$ (69)

Hence proved. ∎

###  VII-C Proof of Theorem 3

Let $f_{i}$ be $L_{i}$ smooth and let $f_{i}$ $i\in[n]$ satisfy the strong
growth condition (5). Then, there exists $\hat{a},\hat{\alpha}$ such that for
$0<a\leq\hat{a}$ and $\alpha_{\mathrm{max}}\leq\hat{\alpha}$ ,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}E[\lVert\nabla
f(x_{t})\rVert^{2}]\leq\frac{(E[f({x}_{0})]-E[f(\hat{x}_{T})])}{\delta T}$
(70)

where $\hat{x}_{T}$ is a perturbed iterate [31] obtained from
$\\{x_{i}\\}_{i=0}^{T-1}$ and

$\displaystyle\delta$
$\displaystyle=[(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p})-(\nu(\eta_{\mathrm{max}}-\eta_{\mathrm{min}})+\nu
L\eta_{\mathrm{max}}^{2}+(\nu\eta_{\mathrm{max}}^{2}\theta(1-\gamma)(1+\frac{1}{r})))]$
(71) $\displaystyle\hat{a}$
$\displaystyle=\min{\\{\frac{[(\frac{p}{p+1})+1]}{\tilde{\alpha}_{\mathrm{min}}v(L+\theta
G)},\frac{\theta\epsilon}{\beta
L^{2}+\tilde{\alpha}_{\mathrm{min}}pL^{2}}\\}}$ $\displaystyle\hat{\alpha}$
$\displaystyle=\frac{-(\nu-1)+\sqrt{(\nu-1)^{2}+\Big{(}4\nu(L+\theta
G)\hat{a}(\nu+\frac{p}{1+p})\tilde{\alpha}_{\mathrm{min}}\Big{)}}}{2\hat{a}(\nu
L+\nu\theta G)}$ $\displaystyle G$
$\displaystyle\triangleq\theta(1-\gamma)(1+\frac{1}{r})$ $\displaystyle L$
$\displaystyle=\frac{\sum_{i=1}^{n}L_{i}}{n}$

for any $p,r,\theta>0$,
$\tilde{\alpha}_{\mathrm{min}}=\frac{2(1-\sigma)}{L_{\mathrm{max}}}$,
$L_{\mathrm{max}}=\max_{i}{\\{L_{i}\\}}$, $\epsilon<\gamma$ and $\nu$ is the
strong growth constant.

###### Proof.

By the perturbed iterate analysis framework, let $\\{\hat{x}_{t}\\}_{t\geq 0}$
be the virtual sequence generated as

$\displaystyle\hat{x}_{t+1}=\hat{x}_{t}-\eta_{t}\nabla f_{i_{t}}(x_{t}).$ (72)

Since the gradient of $f$ is $L$-Lipschitz smooth,

$\displaystyle f(\hat{x}_{t+1})\leq f(\hat{x}_{t})+\langle\nabla
f(\hat{x}_{t}),\hat{x}_{t+1}-\hat{x}_{t}\rangle+\frac{L}{2}\lVert\hat{x}_{t+1}-\hat{x}_{t}\rVert^{2}.$
(73)

Substituting (72),

$\displaystyle f(\hat{x}_{t+1})\leq f(\hat{x}_{t})+\langle\nabla
f(\hat{x}_{t}),-\eta_{t}\nabla
f_{i_{t}}(x_{t}))\rangle+\frac{L}{2}\lVert\eta_{t}\nabla
f_{i_{t}}({x}_{t})\rVert^{2}.$ (74)

Using the identity $-2\langle a,b\rangle=\lVert a-b\rVert^{2}-\lVert
a\rVert^{2}-\lVert b\rVert^{2}$,

$\displaystyle 2(f(\hat{x}_{t+1})-f(\hat{x}_{t}))$
$\displaystyle\leq\eta_{t}(\lVert\nabla f(\hat{x}_{t})-\nabla
f_{i_{t}}(x_{t})\rVert^{2}-\lVert\nabla f(\hat{x}_{t})\rVert^{2}-\lVert\nabla
f_{i_{t}}(x_{t})\rVert^{2})$ (75) $\displaystyle+L\lVert\eta_{t}\nabla
f_{i_{t}}({x}_{t})\rVert^{2}.$

The step-size $\eta_{t}\in[\eta_{\mathrm{min}},\eta_{\mathrm{max}}]$. By
applying these bounds and taking expectation $E_{i_{t}}$ with respect to the
data point $i_{t}$ conditioned on $x_{t},i_{t-1}$ and the entire past therein,

$\displaystyle 2E_{i_{t}}[f(\hat{x}_{t+1})-f(\hat{x}_{t})]$
$\displaystyle\leq\eta_{\mathrm{max}}E_{i_{t}}[||\nabla f(\hat{x}_{t})-\nabla
f_{i_{t}}(x_{t})||^{2}]$ (76) $\displaystyle-\eta_{\mathrm{min}}||\nabla
f(\hat{x}_{t})||^{2}-\eta_{\mathrm{min}}E_{i_{t}}[||\nabla
f_{i_{t}}(x_{t})||^{2}]$
$\displaystyle+L\eta_{\mathrm{max}}^{2}E_{i_{t}}[||\nabla
f_{i_{t}}(x_{t})||^{2}].$

As $E_{i_{t}}[\nabla f_{i_{t}}(x)]=\nabla f(x)$,

$\displaystyle E_{i_{t}}[||\nabla f(\hat{x}_{t})-\nabla
f_{i_{t}}(x_{t})||^{2}]$ $\displaystyle=||\nabla
f(\hat{x}_{t})||^{2}+E_{i_{t}}[||\nabla f_{i_{t}}(x_{t})||^{2}]$ (77)
$\displaystyle-2\langle\nabla f(\hat{x}_{t}),\nabla f(x_{t})\rangle.$

Substituting (77) in 76,

$\displaystyle 2E_{i_{t}}[f(\hat{x}_{t+1})-f(\hat{x}_{t})]$
$\displaystyle\leq\eta_{\mathrm{max}}(||\nabla
f(\hat{x}_{t})||^{2}+E_{i_{t}}[||\nabla f_{i_{t}}(x_{t})||^{2}])$ (78)
$\displaystyle-\eta_{\mathrm{max}}2\langle\nabla f(\hat{x}_{t}),\nabla
f(x_{t})\rangle$ $\displaystyle-\eta_{\mathrm{min}}||\nabla
f(\hat{x}_{t})||^{2}-\eta_{\mathrm{min}}E_{i_{t}}[||\nabla
f_{i_{t}}(x_{t})||^{2}]$
$\displaystyle+L\eta_{\mathrm{max}}^{2}E_{i_{t}}[||\nabla
f_{i_{t}}({x}_{t})||^{2}].$

Since,

$\displaystyle-2\eta_{\mathrm{max}}\langle\nabla f(\hat{x}_{t}),\nabla
f(x_{t})\rangle=\eta_{\mathrm{max}}\lVert\nabla f(\hat{x}_{t})-\nabla
f(x_{t})\rVert^{2}-\eta_{\mathrm{max}}\lVert\nabla
f(\hat{x}_{t})\rVert^{2}-\eta_{\mathrm{max}}\lVert\nabla f(x_{t})\rVert^{2},$
(79)

$\displaystyle 2E_{i_{t}}[f(\hat{x}_{t+1})-f(\hat{x}_{t})]$
$\displaystyle\leq\eta_{\mathrm{max}}(||\nabla
f(\hat{x}_{t})||^{2}+E_{i_{t}}[||\nabla f_{i_{t}}(x_{t})||^{2}])$ (80)
$\displaystyle+\eta_{\mathrm{max}}\lVert\nabla f(\hat{x}_{t})-\nabla
f(x_{t})\rVert^{2}-\eta_{\mathrm{max}}\lVert\nabla f(\hat{x}_{t})\rVert^{2}$
$\displaystyle-\eta_{\mathrm{max}}\lVert\nabla
f(x_{t})\rVert^{2}-\eta_{\mathrm{min}}||\nabla f(\hat{x}_{t})||^{2}$
$\displaystyle-\eta_{\mathrm{min}}E_{i_{t}}[||\nabla
f_{i_{t}}(x_{t})||^{2}]+L\eta_{\mathrm{max}}^{2}E_{i_{t}}[||\nabla
f_{i_{t}}({x}_{t})||^{2}]$

From Lipschitz smoothness of $\nabla f(x)$,

$||\nabla f(\hat{x}_{t})-\nabla f(x_{t})||\leq L||\hat{x}_{t}-x_{t}||.$ (81)

Substituting the Lipschitz-smoothness property,

$\displaystyle 2E_{i_{t}}[f(\hat{x}_{t+1})-f(\hat{x}_{t})]$
$\displaystyle\leq(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})E_{i_{t}}[||\nabla
f_{i_{t}}(x_{t})||^{2}]+\eta_{\mathrm{max}}L^{2}[||\hat{x}_{t}-x_{t}||^{2}]$
(82) $\displaystyle\hskip 28.45274pt-\eta_{\mathrm{max}}||\nabla
f(x_{t})||^{2}-\eta_{\mathrm{min}}||\nabla f(\hat{x}_{t})||^{2}.$

For any $p>0$, from Lemma 4,

$\displaystyle\lVert a+b\rVert^{2}\leq(1+p)\lVert
a\rVert^{2}+(1+\frac{1}{p})\lVert b\rVert^{2}.$ (83)

Using this identity,

$\displaystyle\lVert\nabla f(x_{t})\rVert^{2}\leq(1+p)\lVert\nabla
f(x_{t})-\nabla f(\hat{x}_{t})\rVert^{2}+(1+\frac{1}{p})\lVert\nabla
f(\hat{x}_{t})\rVert^{2}.$ (84)

Since $f(x)$ has $L$-Lipschitz gradients,

$\displaystyle\lVert\nabla f(x_{t})\rVert^{2}\leq(1+p)L^{2}\lVert
x_{t}-\hat{x}_{t}\rVert^{2}+(1+\frac{1}{p})\lVert\nabla
f(\hat{x}_{t})\rVert^{2},$ (85)

$\displaystyle\frac{p}{1+p}\lVert\nabla
f(x_{t})\rVert^{2}-pL^{2}\lVert\hat{x}_{t}-x_{t}\rVert^{2}\leq\lVert\nabla
f(\hat{x}_{t})\rVert^{2}.$ (86)

Substituting (86) in (82),

$\displaystyle 2E_{i_{t}}[f(\hat{x}_{t+1})-f(\hat{x}_{t})]$
$\displaystyle\leq(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})E_{i_{t}}[||\nabla
f_{i_{t}}(x_{t})||^{2}]+\eta_{\mathrm{max}}L^{2}[||\hat{x}_{t}-x_{t}||^{2}]$
(87) $\displaystyle-\eta_{\mathrm{max}}||\nabla
f(x_{t})||^{2}-\eta_{\mathrm{min}}\big{(}\frac{p}{1+p}\lVert\nabla
f(x_{t})\rVert^{2}-pL^{2}\lVert\hat{x}_{t}-x_{t}\rVert^{2}\big{)},$

$\displaystyle 2E_{i_{t}}[f(\hat{x}_{t+1})-f(\hat{x}_{t})]$
$\displaystyle\leq(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})E_{i_{t}}[\lVert\nabla
f_{i_{t}}(x_{t})\rVert^{2}]$ (88)
$\displaystyle+(\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2})(\lVert\hat{x}_{t}-x_{t}\rVert^{2})$
$\displaystyle-(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p})(\lVert\nabla
f(x_{t})\rVert^{2}),$

$\displaystyle(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p})(\lVert\nabla
f(x_{t})\rVert^{2})$ $\displaystyle\leq
2E_{i_{t}}[f(\hat{x}_{t})-f(\hat{x}_{t+1})]$ (89)
$\displaystyle+(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})E_{i_{t}}[\lVert\nabla
f_{i_{t}}(x_{t})\rVert^{2}]$
$\displaystyle+(\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2})E_{i_{t}}[\lVert\hat{x}_{t}-x_{t}\rVert^{2}].$

By strong growth condition, $E_{i_{t}}[\lVert\nabla
f_{i_{t}}(x)\rVert^{2}]\leq\nu\lVert\nabla f(x)\rVert^{2}$ and thus,

$\displaystyle(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p})(\lVert\nabla
f(x_{t})\rVert^{2})$ $\displaystyle\leq
2E_{i_{t}}[f(\hat{x}_{t})-f(\hat{x}_{t+1})]$ (90)
$\displaystyle+(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})\nu\lVert\nabla
f(x_{t})\rVert^{2}+$
$\displaystyle+(\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2})(\lVert\hat{x}_{t}-x_{t}\rVert^{2}),$

$\displaystyle(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p}-(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})\nu)(\lVert\nabla
f(x_{t})\rVert^{2})$ $\displaystyle\leq
2E_{i_{t}}[f(\hat{x}_{t})-f(\hat{x}_{t+1})]$ (91)
$\displaystyle+(\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2})(\lVert\hat{x}_{t}-x_{t}\rVert^{2}).$

From Lemmas 6 and 7:

$\displaystyle\lVert x-top_{k}(x)\rVert^{2}\leq(1-\gamma)\lVert x\rVert^{2},$
(92)

$\displaystyle\lVert m_{t}\rVert=\lVert x_{t}-\hat{x}_{t}\rVert.$ (93)

The error update equation of the CSGD-ASSS algorithm is

$\displaystyle m_{t+1}=m_{t}+\eta_{t}\nabla
f_{i_{t}}(x_{t})-top_{k}(m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t})).$ (94)

Hence,

$\displaystyle\lVert m_{t+1}\rVert^{2}$ $\displaystyle=\lVert
m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t})-top_{k}(m_{t}+\eta_{t}\nabla
f_{i_{t}}(x_{t}))\rVert^{2}$ (95) $\displaystyle\leq(1-\gamma)\lVert
m_{t}+\eta_{t}\nabla f_{i_{t}}(x_{t})\rVert^{2}.$

From Lemma 4, for any $r>0$,

$\displaystyle\lVert m_{t+1}\rVert^{2}$
$\displaystyle\leq(1-\gamma)(1+r)\lVert
m_{t}\rVert^{2}+(1-\gamma)(1+\frac{1}{r})\eta_{t}^{2}\lVert\nabla
f_{i_{t}}(x_{t})\rVert^{2}$ (96) $\displaystyle\leq(1-\gamma)(1+r)\lVert
m_{t}\rVert^{2}+(1-\gamma)(1+\frac{1}{r})\eta_{\mathrm{max}}^{2}\lVert\nabla
f_{i_{t}}(x_{t})\rVert^{2}$

Taking expectation w.r.t data-point $i_{t}$ and mutiplying (96) by $\theta>0$
and adding to 91,

$\displaystyle(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p}-$
$\displaystyle(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})\nu)(\lVert\nabla
f(x_{t})\rVert^{2})+\theta E_{i_{t}}[\lVert m_{t+1}\rVert^{2}]$ (97)
$\displaystyle\leq 2E_{i_{t}}[f(\hat{x}_{t})-f(\hat{x}_{t+1})]$
$\displaystyle+(\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2})(\lVert\hat{x}_{t}-x_{t}\rVert^{2})$
$\displaystyle+\theta(1-\gamma)(1+r)\lVert
m_{t}\rVert^{2}+\theta(1-\gamma)(1+\frac{1}{r})\eta_{\mathrm{max}}^{2}(E_{i_{t}}[\lVert\nabla
f(x_{t})\rVert^{2}]).$

By strong growth condition,

$\displaystyle(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p}-$
$\displaystyle(\eta_{\mathrm{max}}-\eta_{\mathrm{min}}+L\eta_{\mathrm{max}}^{2})\nu)\lVert\nabla
f(x_{t})\rVert^{2}+\theta E_{i_{t}}[\lVert m_{t+1}\rVert^{2}]$ (98)
$\displaystyle\leq 2E_{i_{t}}[f(\hat{x}_{t})-f(\hat{x}_{t+1})]+$
$\displaystyle+(\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2})\lVert\hat{x}_{t}-x_{t}\rVert^{2}+$
$\displaystyle+\theta(1-\gamma)(1+r)\lVert
m_{t}\rVert^{2}+\theta(1-\gamma)(1+\frac{1}{r})\eta_{\mathrm{max}}^{2}\nu\lVert\nabla
f(x_{t})\rVert^{2}.$

Taking expectation w.r.t the entire process,

$\displaystyle[(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p})-(\nu(\eta_{\mathrm{max}}-\eta_{\mathrm{min}})+\nu
L\eta_{\mathrm{max}}^{2}$ (99)
$\displaystyle+(\nu\eta_{\mathrm{max}}^{2}\theta(1-\gamma)(1+\frac{1}{r})))]E[\lVert\nabla
f(x_{t})\rVert^{2}]$ $\displaystyle\hskip 50.00008pt\leq
2E[f(\hat{x}_{t})-f(\hat{x}_{t+1})]$ $\displaystyle\hskip
50.00008pt+\big{(}\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2}+\theta(1-\gamma)(1+r)\big{)}E[\lVert
m_{t}\rVert^{2}]-\theta E[\lVert m_{t+1}\rVert^{2}].$

Consider the term
$\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2}+\theta(1-\gamma)(1+r)$ and
an $\epsilon<\gamma$. Then,

$\displaystyle(1-\gamma)(1+r)\leq 1-\gamma+r\leq(1-\epsilon)$ (100)

iff $r\leq\gamma-\epsilon$. Set

$\displaystyle r\leq\gamma-\epsilon$ (101)
$\displaystyle\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2}\leq\theta\epsilon.$

The inequality
$\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2}\leq\theta\epsilon$ holds
iff

$\displaystyle
a\leq\frac{\theta\epsilon}{(\alpha_{\mathrm{max}}L^{2}+\alpha_{\mathrm{min}}pL^{2})}.$
(102)

Hence, setting $r=\gamma-\epsilon$ and $a$ satisfying 102, implies

$\displaystyle\big{(}\eta_{\mathrm{max}}L^{2}+\eta_{\mathrm{min}}pL^{2}+\theta(1-\gamma)(1+r)\big{)}\leq\theta.$
(103)

Let

$\displaystyle\delta\triangleq[(\eta_{\mathrm{max}}+\frac{\eta_{\mathrm{min}}p}{1+p})-(\nu(\eta_{\mathrm{max}}-\eta_{\mathrm{min}})+\nu
L\eta_{\mathrm{max}}^{2}+(\nu\eta_{\mathrm{max}}^{2}\theta(1-\gamma)(1+\frac{1}{r})))]$
(104)

and

$\displaystyle G\triangleq\theta(1-\gamma)(1+\frac{1}{r}).$ (105)

If $\delta>0$, and $a$ satisfies (102), (99) simplifies as

$\displaystyle\delta E[\lVert\nabla f(x_{t})\rVert^{2}]\leq
2E[f(\hat{x}_{t})-f(\hat{x}_{t+1})]+\theta(E[\lVert m_{t}\rVert^{2}]-E[\lVert
m_{t+1}\rVert^{2}]).$ (106)

Summing over the horizon $T$ and averaging,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}E[\lVert\nabla
f(x_{t})\rVert^{2}]\leq 2\frac{(E[f(\hat{x}_{0})]-E[f(\hat{x}_{T})])}{\delta
T}+\frac{\theta(E[\lVert m_{0}\rVert^{2}]-E[\lVert m_{T}\rVert^{2}])}{\delta
T}.$ (107)

Since $m_{0}=0$ and $\hat{x}_{0}=x_{0}$,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}E[\lVert\nabla
f(x_{t})\rVert^{2}]\leq 2\frac{(E[f(\hat{x}_{0})]-E[f(\hat{x}_{T})])}{\delta
T}.$ (108)

The conditions under which $\delta>0$, can be stated in 2 cases depending on
the value of $\alpha_{\mathrm{max}}$.

  1. 1.

Case 1: $\alpha_{\mathrm{max}}\leq\frac{2(1-\sigma)}{L_{\mathrm{max}}}$.

In this case $\alpha_{\mathrm{max}}=\alpha_{\mathrm{min}}$ by Lemma 8 and this
implies $\eta_{\mathrm{max}}=\eta_{\mathrm{min}}$. Hence $\delta>0$ iff

$\displaystyle
a\leq\frac{[(\frac{p}{p+1})+1]}{\tilde{\alpha}_{\mathrm{min}}v(L+\theta G)}$
(109)

  2. 2.

Case 2: $\alpha_{\mathrm{max}}>\frac{2(1-\sigma)}{L_{\mathrm{max}}}$. In this
case $\delta>0$ iff

$\displaystyle\alpha_{\mathrm{max}}\leq\frac{-(\nu-1)+\sqrt{(\nu-1)^{2}+\Big{(}4\nu(L+\theta
G)a(\nu+\frac{p}{1+p})\tilde{\alpha}_{\mathrm{min}}\rho\Big{)}}}{2a(\nu
L+\nu\theta G)}$ (110)

Let

$\displaystyle\mathrm{UB}(a)\triangleq\frac{-(\nu-1)+\sqrt{(\nu-1)^{2}+\Big{(}4\nu(L+\theta
G)a(\nu+\frac{p}{1+p})\tilde{\alpha}_{\mathrm{min}}\rho\Big{)}}}{2a(\nu
L+\nu\theta G)}$ (111)

An interval
$\alpha_{\mathrm{max}}\in(\frac{2(1-\sigma)}{L_{\mathrm{max}}},\mathrm{UB}(a)]$
exists if $\frac{2(1-\sigma)}{L_{\mathrm{max}}}\leq\mathrm{UB}(a)$. The bound
$\mathrm{UB}(a)$ is a monotonically decreasing function of $a$ and the
interval exists if

$\displaystyle
a\leq\frac{[(\frac{p}{p+1})+1]}{\tilde{\alpha}_{\mathrm{min}}v(L+\theta G)}.$
(112)

Combining the bounds on $a$ for $\delta>0$ and $\frac{1}{T}$ convergence from
(102),(112),

$\displaystyle
a\leq\min{\\{\frac{[(\frac{p}{p+1})+1]}{\tilde{\alpha}_{\mathrm{min}}v(L+\theta
G)},\frac{\theta\epsilon}{\beta
L^{2}+\tilde{\alpha}_{\mathrm{min}}pL^{2}}\\}}.$ (113)

Hence, in the statement of the theorem,

$\displaystyle\hat{a}$
$\displaystyle=\min{\\{\frac{[(\frac{p}{p+1})+1]}{\tilde{\alpha}_{\mathrm{min}}v(L+\theta
G)},\frac{\theta\epsilon}{\beta
L^{2}+\tilde{\alpha}_{\mathrm{min}}pL^{2}}\\}},$ (114)

and if $a=\hat{a}$, then

$\displaystyle\hat{\alpha}$ $\displaystyle=\mathrm{UB}(\hat{a}).$ (115)

Hence proved.

∎

##  VIII Distributed Compressed SGD with Armijo Step-Size Search (DCSGD-ASSS)

The CSGD-ASSS algorithm can be extended to the distributed setting with the
same convergence rates as the central/single worker node setting. In this
section, we present the algorithm and convergence results for DCSGD-ASSS.

###  VIII-A Notation

In the distributed setting, the superscript indicates the corresponding worker
node. For instance, $g_{t}^{(k)}$ is the compressed gradient of worker node
$k$ at time $t$. We assume for simplicity, the dataset is equally split among
the workers and $n=NM$, where $n$ is the total number of data points, $M$ is
the number of data points in each worker and $N$ is the number of worker
nodes. The $i$ th data point at worker $k$ is $f_{i}^{(k)}(x)$.

###  VIII-B Algorithm

Consider the distributed setting in which there is one central node and $N$
worker nodes. The function to be minimized is

$\displaystyle f(x)=\frac{1}{N}{\sum_{k=1}^{N}f^{(k)}(x)}$ (116)

where $f^{(k)}(x)=\frac{1}{M}{\sum_{i=1}^{M}f_{i}^{(k)}(x)}$. We consider a
distributed algorithm consistent with [3, 32]. Each worker node samples a data
point $f_{i_{t}}^{(k)}(x)$, searches for a step-size $\alpha_{t}^{(k)}$ with
the Armijo step-size search algorithm, computes
$a\alpha_{t}^{(k)}g_{t}^{(k)}$, and transmits it to the central node, where
$g_{t}^{(k)}$ is the compressed gradient. The central node averages the
compressed gradients and computes the descent step
$x_{t+1}=x_{t}-\big{(}\sum_{k=1}^{N}a\alpha_{t}^{(k)}g_{t}^{(k)}/N\big{)}$ and
transmits $x_{t+1}$ to the worker nodes.

Algorithm 3 Distributed Compressed SGD with Armijo Step-Size Search (DCSGD-
ASSS)

1:At worker node $(k),\ k\in[N]$ :

2:for $t=0,\cdots,T-1$ do

3: Sample data $i_{t}^{(k)}$

4: $\alpha_{t}^{(k)}\leftarrow\text{Armijo step-size
search}(f_{i_{t}}^{(k)},\alpha_{\mathrm{max}},x_{t})$

5: $g_{t}^{(k)}=top_{k}(m_{t}^{(k)}+a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t}))$

6: Transmit $g_{t}^{(k)}$ to central node

7: $m_{t+1}^{(k)}=m_{t}^{(k)}+a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})-g_{t}^{(k)}$

8:end for

9:At central node:

10:$x_{t+1}=x_{t}-\big{(}\sum_{k=1}^{N}g_{t}^{(k)}/N\big{)}$

11:Transmit $x_{t+1}$ to worker nodes

###  VIII-C Results

The convergence results for DCSGD-ASSS are proved using the perturbed iterate
analysis method. Let $\hat{x}_{0}=x_{0}$ and
$\hat{x}_{t+1}=\hat{x}_{t}-\frac{1}{N}\sum_{k=1}^{N}{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}$. The Lemma 13 is used in the proof of convergence.

######  Lemma 13.

For any time $t$,

$x_{t}-\hat{x}_{t}=\frac{1}{N}\sum_{k=1}^{N}m_{t}^{(k)}.$ (117)

###### Proof.

We prove this by induction. Note that $m_{0}^{(k)}=0$ for all $k$. For $t=1$,

$\displaystyle x_{1}$
$\displaystyle=x_{0}-\frac{1}{N}\sum_{k=1}^{N}{top_{k}(a\alpha_{0}^{(k)}\nabla
f_{i_{0}}^{(k)}(x_{0}))},$ (118) $\displaystyle\hat{x}_{1}$
$\displaystyle=\hat{x}_{0}-\frac{1}{N}\sum_{k=1}^{N}{a\alpha_{0}^{(k)}\nabla
f_{i_{0}}^{(k)}(x_{0})}.$ (119)

Then,

$x_{1}-\hat{x}_{1}=\frac{1}{N}\sum_{k=1}^{N}({a\alpha_{0}^{(k)}\nabla
f_{i_{0}}^{(k)}(x_{0})-top_{k}(a\alpha_{0}^{(k)}\nabla
f_{i_{0}}^{(k)}(x_{0}))})=\frac{1}{N}\sum_{k=1}^{N}{m_{1}^{(k)}}.$ (120)

Let $x_{t}-\hat{x}_{t}=\frac{1}{N}\sum_{k=1}^{N}m_{t}^{(k)}$. For $t+1$,

$\displaystyle x_{t+1}$
$\displaystyle=x_{t}-\frac{1}{N}\sum_{k=1}^{N}{top_{k}(m_{t}^{(k)}+a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t}))},$ (121) $\displaystyle\hat{x}_{t+1}$
$\displaystyle=\hat{x}_{t}-\frac{1}{N}\sum_{k=1}^{N}{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}.$ (122)

Thus,

$\displaystyle x_{t+1}-\hat{x}_{t+1}$
$\displaystyle=\frac{1}{N}\sum_{k=1}^{N}\big{(}{m_{t}^{(k)}+a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t}))-top_{k}(m_{t}^{(k)}+a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t}))}\big{)}$ (123)
$\displaystyle=\frac{1}{N}\sum_{k=1}^{N}{m_{t+1}^{(k)}}.$

∎

######  Theorem 14.

(Distributed-Convex) Let $f_{i}^{(k)}(x)$ be convex and $L_{i}^{(k)}$ smooth
for $i\in[M]$, $k\in[N]$, and $f_{i}^{(k)}$ satisfy the interpolation
condition. Then there exists $\hat{a}$ such that if $a<\hat{a}$, the
distributed compressed SGD with Armijo step-size search for $\sigma\in(0,1)$
and scale factor $a$ satisfies

$\displaystyle
E\left[f\left(\frac{1}{T}{\sum_{t=0}^{T-1}x_{t}}\right)\right]-E[f(x^{*})]$
(124) $\displaystyle\leq\frac{1}{\delta_{2}T}(E[||\hat{x}_{0}-x^{*}||^{2}])$

where for any $0<\epsilon<\zeta$,
$\zeta\triangleq\frac{\sigma\gamma}{(2-\gamma)}$ and
$L_{\mathrm{max}}\triangleq\max_{i,k}L_{i}^{(k)}$,

$\displaystyle\delta_{2}\triangleq\rho\frac{2(1-\sigma)}{L_{\mathrm{max}}}\Big{(}2a-\frac{a^{2}}{\sigma}-\frac{a^{2}}{\sigma
p(\epsilon)}-(1-\gamma)\left(1+\frac{1}{r(\epsilon)}\right)\frac{a^{2}}{\sigma}\Big{)},$
(125) $\displaystyle\hat{a}=(\zeta-\epsilon).$

The values $p(\epsilon),r(\epsilon)$ are as stated in Lemma 12.

###### Proof.

We have that

$\displaystyle\|\hat{x}_{t+1}-x^{*}\|^{2}$
$\displaystyle=\|\hat{x}_{t}-x^{*}-\frac{1}{N}\sum_{k=1}^{N}{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}\|^{2}$ (126)
$\displaystyle=\|\hat{x}_{t}-x^{*}\|^{2}+\frac{1}{N}\|\sum_{k=1}^{N}{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}\|^{2}-2\langle\hat{x}_{t}-x^{*},\frac{1}{N}\sum_{k=1}^{N}{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}\rangle$
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}+\frac{1}{N}\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}}-\frac{2}{N}\sum_{k=1}^{N}\langle\hat{x}_{t}-x^{*},{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}\rangle$
$\displaystyle=\|\hat{x}_{t}-x^{*}\|^{2}+\frac{1}{N}\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}}$ $\displaystyle+\frac{2}{N}\sum_{k=1}^{N}\langle
x_{t}-\hat{x}_{t},{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}\rangle+\frac{2}{N}\sum_{k=1}^{N}\langle
x^{*}-{x}_{t},{a\alpha_{t}^{(k)}\nabla f_{i_{t}}^{(k)}(x_{t})}\rangle,$

where the inequality arises from Jensen’s inequality.

Since each $f_{i_{t}}^{(k)}$ is convex,

$\langle x^{*}-x_{t},a\alpha_{t}^{(k)}\nabla f_{i_{t}}^{(k)}(x_{t})\rangle\leq
a\alpha_{t}^{(k)}(f_{i_{t}}^{(k)}(x^{*})-f_{i_{t}}^{(k)}(x_{t})).$ (127)

From Lemma 4, for any $p>0$,

$\langle x_{t}-\hat{x}_{t},\frac{2}{N}\sum_{k=1}^{N}{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}\rangle\leq
p\|x_{t}-\hat{x}_{t}\|^{2}+\frac{1}{p}\|\frac{1}{N}\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}\nabla
f_{i_{t}}^{(k)}(x_{t})}\|^{2}.$ (128)

From Jensen’s inequality,

$\langle x_{t}-\hat{x}_{t},\frac{2}{N}\sum_{k=1}^{N}{a\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t})}\rangle\leq
p\|x_{t}-\hat{x}_{t}\|^{2}+\frac{1}{pN}\sum_{k=1}^{N}a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}.$ (129)

Thus,

$\displaystyle\|\hat{x}_{t+1}-x^{*}\|^{2}$
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}+\frac{1}{N}\sum_{k=1}^{N}\big{(}{a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}}\big{)}+p\|x_{t}-\hat{x}_{t}\|^{2}$ (130)
$\displaystyle+\frac{1}{pN}\sum_{k=1}^{N}a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}+\frac{2}{N}\sum_{k=1}^{N}a\alpha_{t}^{(k)}(f_{i_{t}}^{(k)}(x^{*})-f_{i_{t}}^{(k)}(x_{t}))$
(131)
$\displaystyle=\|\hat{x}_{t}-x^{*}\|^{2}+p\|\frac{1}{N}\sum_{k=1}^{N}{m_{t}^{(k)}}\|^{2}+(1+\frac{1}{p})\frac{1}{N}\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}}$ (132) $\displaystyle\hskip
30.00005pt-\frac{2}{N}\sum_{k=1}^{N}a\alpha_{t}^{(k)}e_{t}^{(k)}$ (133)
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}+\frac{p}{N}\sum_{k=1}^{N}\|m_{t}^{(k)}\|^{2}+\frac{(1+\frac{1}{p})}{N}\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}}$ (134) $\displaystyle\hskip
30.00005pt-\frac{2}{N}\sum_{k=1}^{N}a\alpha_{t}^{(k)}e_{t}^{(k)},$ (135)

where $e_{t}^{(k)}\triangleq f_{i_{t}}^{(k)}(x_{t})-f_{i_{t}}^{(k)}(x^{*})$,
(133) is from Lemma 13 and (135) is from Jensen’s inequality.

We have from the compression property (Lemma 6) and Lemma 5 that for each $k$
and some $r>0$,

$\displaystyle||m_{t+1}^{(k)}||^{2}$
$\displaystyle\leq(1-\gamma)||m_{t}^{(k)}+a\alpha_{t}^{(k)}\nabla
f^{(k)}_{i_{t}}(x_{t})||^{2}$ (136)
$\displaystyle\leq(1-\gamma)\big{(}(1+r)||m_{t}^{(k)}||^{2}+(1+\frac{1}{r})a^{2}(\alpha_{t}^{(k)})^{2}||\nabla
f^{(k)}_{i_{t}}(x_{t})||^{2}\big{)}$
$\displaystyle\leq(1-\gamma)(1+r)||m^{(k)}_{t}||^{2}+(1-\gamma)(1+\frac{1}{r})a^{2}(\alpha_{t}^{(k)})^{2}||\nabla
f^{(k)}_{i_{t}}(x_{t})||^{2}.$

Averaging the above over all $k$ (the workers),

$\frac{1}{N}\sum_{k=1}^{N}||m_{t+1}^{(k)}||^{2}\leq\frac{(1-\gamma)(1+r)}{N}\sum_{k=1}^{N}{||m^{(k)}_{t}||^{2}}+\frac{(1-\gamma)(1+\frac{1}{r})}{N}\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}||\nabla
f^{(k)}_{i_{t}}(x_{t})||^{2}}.$ (137)

Adding (137) and (135), we get,

$\displaystyle\|\hat{x}_{t+1}-x^{*}\|^{2}+\frac{1}{N}\sum_{k=1}^{N}{||m_{t+1}^{(k)}||^{2}}$
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}+\frac{p}{N}\sum_{k=1}^{N}\|m_{t}^{(k)}\|^{2}$
(138)
$\displaystyle+(\frac{p+1}{pN})\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}}-\frac{2}{N}\sum_{k=1}^{N}a\alpha_{t}^{(k)}e_{t}^{(k)}$
$\displaystyle+\frac{(1-\gamma)(1+r)}{N}\sum_{k=1}^{N}{||m^{(k)}_{t}||^{2}}$
$\displaystyle+(1-\gamma)(1+\frac{1}{r})\frac{1}{N}\sum_{k=1}^{N}{a^{2}(\alpha_{t}^{(k)})^{2}||\nabla
f^{(k)}_{i_{t}}(x_{t})||^{2}}.$

For any worker $k$, from the Armijo step-size search stopping condition,

$\displaystyle\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}\leq\frac{1}{\sigma\alpha_{t}^{(k)}}(f_{i_{t}}^{(k)}(x_{t})-f_{i_{t}}^{(k)}(x_{t}-\alpha_{t}^{(k)}\nabla
f_{i_{t}}^{(k)}(x_{t}))).$ (139)

From the interpolation condition we have that
$f_{i_{t}}^{(k)}(x_{t}-\alpha_{t}^{(k)}\nabla f_{i_{t}}^{(k)}(x_{t}))\geq
f_{i_{t}}^{(k)}(x^{*})$. Thus,

$a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}\leq\frac{a^{2}\alpha_{t}^{(k)}}{\sigma}(f_{i_{t}}^{(k)}(x_{t})-f_{i_{t}}^{(k)}(x^{*})).$
(140)

Summing over all $k$ we get,

$\sum_{k=1}^{N}a^{2}(\alpha_{t}^{(k)})^{2}\|\nabla
f_{i_{t}}^{(k)}(x_{t})\|^{2}\leq\frac{1}{\sigma}\sum_{k=1}^{N}{a^{2}\alpha_{t}^{(k)}}e_{t}^{(k)}.$
(141)

Using the above in (138),

$\displaystyle\|\hat{x}_{t+1}-x^{*}\|^{2}+\sum_{k=1}^{N}\frac{||m_{t+1}^{(k)}||^{2}}{N}$
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}+\frac{p+(1-\gamma)(1+r)}{N}\sum_{k=1}^{N}{||m^{(k)}_{t}||^{2}}$
(142)
$\displaystyle+\frac{\frac{a^{2}}{\sigma}(1+\frac{1}{p}+(1-\gamma)(1+\frac{1}{r}))-2a}{N}\sum_{k=1}^{N}{\alpha_{t}^{(k)}}e_{t}^{(k)}.$

From the definitions in Theorems 1,2,

$\displaystyle\beta_{3}(p,r)=\Big{(}p+(1-\gamma)(1+r)\Big{)}$ (143)
$\displaystyle\tilde{a}_{1}(p,r)=2/\Big{(}\frac{1}{\sigma}+\frac{1}{\sigma
p}+\frac{(1-\gamma)(1+\frac{1}{r})}{\sigma}\Big{)}$
$\displaystyle\tilde{a}_{2}(p,r)=\Big{(}2a-\frac{a^{2}}{\sigma}-\frac{a^{2}}{\sigma
p}-(1-\gamma)(1+\frac{1}{r})\frac{a^{2}}{\sigma}\Big{)}$

From Lemma 12, $\exists\ (p(\epsilon),r(\epsilon))$ such that

$\displaystyle\Big{(}p(\epsilon)+(1-\gamma)(1+r(\epsilon))\Big{)}=1-\delta<1$
(144) $\displaystyle\tilde{a}_{1}(p(\epsilon),r(\epsilon))>\zeta-\epsilon.$

Choosing $(p,r)=(p(\epsilon),r(\epsilon))$ in 143, if $a\leq\zeta-\epsilon$,
then $a\leq\tilde{a}_{1}(p(\epsilon),r(\epsilon))$.

It is shown in the proof of Theorem 2, that
$a\leq\tilde{a}_{1}(p(\epsilon),r(\epsilon))$ implies
$\tilde{a}_{2}(p(\epsilon),r(\epsilon))>0$. Also,
$\alpha_{t}\geq\tilde{\alpha}_{\mathrm{min}}\rho$ and
$e_{t}^{(k)}=f_{i_{t}}^{(k)}(x_{t})-f_{i_{t}}^{(k)}(x^{*})$. Substituting
these values in (142),

$\displaystyle\|\hat{x}_{t+1}-x^{*}\|^{2}+\sum_{k=1}^{N}\frac{1}{N}{||m_{t+1}^{(k)}||^{2}}$
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}+\frac{1}{N}\sum_{k=1}^{N}{||m^{(k)}_{t}||^{2}}$
(145)
$\displaystyle-\frac{\tilde{a}_{2}(p(\epsilon),r(\epsilon))}{N}\sum_{k=1}^{N}{\tilde{\alpha}_{\mathrm{min}}\rho}(f_{i_{t}}^{(k)}(x_{t})-f_{i_{t}}^{(k)}(x^{*})),$

$\displaystyle\frac{\alpha_{\mathrm{min}}\rho\big{(}\tilde{a}_{2}(p(\epsilon),r(\epsilon))\big{)}}{N}\sum_{k=1}^{N}(f_{i_{t}}^{(k)}(x_{t})-f_{i_{t}}^{(k)}(x^{*}))$
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}-\|\hat{x}_{t+1}-x^{*}\|^{2}$ (146)
$\displaystyle+\frac{1}{N}\sum_{k=1}^{N}(||m^{(k)}_{t}||^{2}-||m_{t+1}^{(k)}||^{2}).$

Taking expectation $E_{i_{t}}$ with respect to the sampled data points chosen
at all nodes $k=1,\ldots,N$ at time $t$ conditioned on the entire past,

$\displaystyle\alpha_{\mathrm{min}}\rho\big{(}\tilde{a}_{2}(p(\epsilon),r(\epsilon))\big{(}f(x_{t})-f(x^{*}))$
$\displaystyle\leq\|\hat{x}_{t}-x^{*}\|^{2}-E_{i_{t}}[\|\hat{x}_{t+1}-x^{*}\|^{2}]$
(147)
$\displaystyle+\frac{1}{N}\sum_{k=1}^{N}(||m^{(k)}_{t}||^{2}-E_{i_{t}}[||m_{t+1}^{(k)}||^{2}]).$

Taking expectation $E$ over the whole process and averaging over all $t$,

$\displaystyle\alpha_{\mathrm{min}}\rho\big{(}\tilde{a}_{2}(p(\epsilon),r(\epsilon))\big{)}$
$\displaystyle\frac{1}{T}{\sum_{t=0}^{T-1}(E[f(x_{t})]-E[f(x^{*})])}$ (148)
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}(E[\|\hat{x}_{t}-x^{*}\|^{2}]-E[\|\hat{x}_{t+1}-x^{*}\|^{2}])$
$\displaystyle+\frac{1}{NT}\sum_{k=1}^{N}\sum_{t=0}^{T-1}(E[||m^{(k)}_{t}||^{2}]-E[||m_{t+1}^{(k)}||^{2}])$
$\displaystyle\leq\frac{1}{T}(E[\|\hat{x}_{0}-x^{*}\|^{2}]-E[\|\hat{x}_{T}-x^{*}\|^{2}])$
$\displaystyle+\frac{1}{NT}\sum_{k=1}^{N}(E[||m^{(k)}_{0}||^{2}]-E[||m_{T}^{(k)}||^{2}]).$

Using Jensen’s inequality and $m_{0}^{(k)}=0$ for all $k$,

$\alpha_{\mathrm{min}}\rho\big{(}\tilde{a}_{2}(p(\epsilon),r(\epsilon))\big{)}\left(E[f(\frac{1}{T}{\sum_{t=0}^{T-1}x_{t}})]-E[f(x^{*})]\right)\leq\frac{1}{T}\left(E[\|{x}_{0}-x^{*}\|^{2}]\right).$
(149)

Hence proved. ∎

######  Remark 5.

Note that geometric convergence in the distributed setting for CSGD-ASSS can
be obtained similarly from the single node case under the assumption of
smoothness and that at least one function $f_{i}^{(k)}$ is strongly convex.

##  IX Proof of Scaled Armijo Step-Size Search GD

A proof for $O(\frac{1}{T})$ convergence of Armijo step-size search GD (CSGD-
ASSS without the stochasticity in $f_{i_{t}}$) with scaling for all
$\sigma\in(0,1)$ and convex function $f$ is presented in this section.

######  Theorem 15.

(Deterministic-Uncompressed-Convex) Let $f(x)$ be convex and $L$ smooth. The
Armijo step-size search gradient descent for $\sigma\in(0,1)$ and scale factor
$a<2\sigma$ satisfies

$\displaystyle
f(\bar{x}_{T})-f(x^{*})\leq\frac{||x_{0}-x^{*}||^{2}}{\tilde{\alpha}_{\mathrm{min}}\rho(2a-\frac{a^{2}}{\sigma})T}$
(150)

where $\bar{x}_{T}=\frac{1}{T}{\sum_{i=0}^{T-1}x_{i}}$.

###### Proof.

The descent step is $x_{t+1}=x_{t}-\alpha_{t}a\nabla f(x_{t})$ where $a$ is
the scaling factor and $x^{*}$ is the minimum.

$\displaystyle||x_{t+1}-x^{*}||^{2}$ $\displaystyle=||x_{t}-\alpha_{t}a\nabla
f(x_{t})-x^{*}||^{2}$ (151)
$\displaystyle=||x_{t}-x^{*}||^{2}+\alpha_{t}^{2}a^{2}||\nabla f(x_{t})||^{2}$
$\displaystyle\hskip 28.45274pt-2\alpha_{t}a\langle x_{t}-x^{*},\nabla
f(x_{t})\rangle$

From the convexity of $f$,

$\langle x^{*}-x_{t},\nabla f(x_{t})\rangle\leq f(x^{*})-f(x_{t}).$ (152)

This implies

$\displaystyle||x_{t+1}-x^{*}||^{2}$
$\displaystyle\leq||x_{t}-x^{*}||^{2}+\alpha_{t}^{2}a^{2}||\nabla
f(x_{t})||^{2}$ (153) $\displaystyle\hskip
28.45274pt+2\alpha_{t}a(f(x^{*})-f(x_{t})).$

The non-scaled iterate $\tilde{x}_{t}$ ($\tilde{x}_{t}=x_{t}-\alpha_{t}\nabla
f(x_{t})$) corresponding to the step-size $\alpha_{t}$ returned by the Armijo
step-size search satisfies

$\displaystyle f(\tilde{x}_{t+1})-f(x_{t})\leq-\alpha_{t}\sigma||\nabla
f(x_{t})||^{2}.$ (154)

This implies

$\displaystyle\alpha_{t}^{2}a^{2}||\nabla
f(x_{t})||^{2}\leq\frac{a^{2}\alpha_{t}}{\sigma}(f(x_{t})-f(\tilde{x}_{t+1})).$
(155)

Substituting (155) in (153),

$\displaystyle||x_{t+1}-x^{*}||^{2}$
$\displaystyle\leq||x_{t}-x^{*}||^{2}+\frac{a^{2}\alpha_{t}}{\sigma}(f(x_{t})-f(\tilde{x}_{t+1}))$
(156) $\displaystyle\hskip 28.45274pt+2\alpha_{t}a(f(x^{*})-f(x_{t})).$

Since $f(\tilde{x}_{t+1})\geq f(x^{*})$,

$\displaystyle||x_{t+1}-x^{*}||^{2}$
$\displaystyle\leq||x_{t}-x^{*}||^{2}+\frac{a^{2}\alpha_{t}}{\sigma}(f(x_{t})-f(x^{*}))$
(157) $\displaystyle\hskip 28.45274pt+2\alpha_{t}a(f(x^{*})-f(x_{t})),$

$\displaystyle\alpha_{t}(2a-\frac{a^{2}}{\sigma})(f(x_{t})-f(x^{*}))\leq||x_{t}-x^{*}||^{2}-||x_{t+1}-x^{*}||^{2}$
(158)

$(2a-\frac{a^{2}}{\sigma})>0\iff a<2\sigma$ . Without scaling the factor
$(2a-\frac{a^{2}}{\sigma})$ would be $(2-\frac{1}{\sigma})$, thus limiting
$\sigma\in[0.5,1)$ in [15].

For Armijo step-size search, $\alpha_{t}\geq\frac{2(1-\sigma)}{L}\rho$. Using
this lower bound, summing over the horizon $T$ and using Jensen’s inequality,

$\displaystyle
f(\frac{1}{T}{\sum_{t=1}^{T}x_{t}})-f(x^{*})\leq\frac{||x_{0}-x^{*}||^{2}}{\frac{2(1-\sigma)}{L}\rho(2a-\frac{a^{2}}{\sigma})T}.$
(159)

Hence proved.

∎

##  X Additional Simulation Results and Discussion

###  X-A Validation Accuracy Comparison between Adaptive and Non-Adaptive
Compressed SGD

A summary of validation accuracy of our experiments on ResNets and DenseNets
is presented in Table I, where NN, DS, CP, R34, R18, D121, C10, C100 refer to
Neural Network, Data Set, Compression Percentage, ResNet 34, ResNet 18,
DenseNet 121, CIFAR 10, and CIFAR 100 respectively. The columns
$0.1,0.05,0.01$ state validation accuracy of non-adaptive compressed SGD [3,
4] with step-sizes $0.1,0.05$ and $0.01$ respectively. The column $3\sigma$
corresponds to our proposed CSGD-ASSS algorithm with $a=3\sigma$. The
compression percentages we have used are not fine-tuned, and are arbitrary.
Since we do not compress layers with less than $1000$ parameters, consistent
with [8], the batch normalization layers of DenseNet 121 are not compressed.
Compressing the layers excluding the batch normalization layers at $1\%$
results in an average of $4\%$ per layer compression. From the table, we infer
that, the validation accuracy of CSGD-ASSS is competitive with tuned non-
adaptive compressed SGD.

NN | DS | CP | 0.1 | 0.05 | 0.01 | $\mathbf{3\sigma}$
---|---|---|---|---|---|---
R34 | C100 | 1.5 | 72.0 | 71.39 | 70.27 | 71.64
R18 | C100 | 1.5 | 71.55 | 71.74 | 69.85 | 72.82
R34 | C10 | 1.5 | 92.42 | 92.19 | 91.16 | 90.42
R18 | C10 | 1.5 | 92.34 | 92.23 | 91.28 | 91.1
R34 | C100 | 10 | 71.81 | 71.21 | 69.24 | 72.55
R18 | C100 | 10 | 71.64 | 71.79 | 70.04 | 72.46
R34 | C10 | 10 | 92.58 | 92.44 | 91.42 | 91.05
R18 | C10 | 10 | 92.28 | 92.1 | 91.11 | 91.46
D121 | C100 | 4 | 69.18 | 68.45 | 64.64 | 71.63
D121 | C100 | 10 | 68.65 | 67.91 | 63.26 | 70.82
D121 | C10 | 4 | 91.09 | 91.06 | 89.09 | 90.89
D121 | C10 | 10 | 91.39 | 90.8 | 89.42 | 91.25
TABLE I:  Validation accuracy of ResNets, DenseNet
NN- Neural Network, DS - Dataset, CP- Compression Percentage, R34 - ResNet 34,
R18 - ResNet18, D121- DenseNet 121, Non-adaptive step-sizes - 0.1,0.05,0.01,
CSGD-ASSS - 3$\sigma$

###  X-B Effect of Scaling on Armijo Step-Size Search

(a) GD on $\sum_{i=1}^{10}\frac{x_{i}^{2}}{2^{5}}$

(b) GD on $\sum_{i=1}^{10}\frac{x_{i}^{2}}{2^{i}}$

Figure 5: Scaled (S $\sigma=0.1$) vs non-scaled (NS $\sigma=0.1$) GD at
$\sigma=0.1$ and $a=1.5\sigma$

To demonstrate the effect of scaling on GD with Armijo step-size search, we
plot scaled and non-scaled Armijo step-size search on the symmetric curve
$\sum_{i=1}^{10}\frac{x_{i}^{2}}{2^{5}}$ and the asymmetric curve
$\sum_{i=1}^{10}\frac{x_{i}^{2}}{2^{i}}$ in Figures 5(a) and 5(b),
respectively. We set the parameters of the step-size search to be $\sigma=0.1$
and scale value $a=1.5\sigma$. On the symmetric curve, both the scaled and
non-scaled step-size search algorithms have comparable performance, however,
on the asymmetric curve, the scaled algorithm outperforms the non-scaled
algorithm by several orders of magnitude. Machine learning tasks can have loss
functions that are asymmetric, and hence scaling can prove to be a useful
technique for adaptive step-size methods.

(a) ResNet 34, CIFAR100, $\approx 10\%$

(b) ResNet 34, CIFAR10, $\approx 10\%$

Figure 6: Training loss of ResNet 34 on CIFAR100 and CIFAR10 at $\approx 10\%$
compression

(a) ResNet 18, CIFAR100, $\approx 10\%$

(b) ResNet 18, CIFAR10, $\approx 10\%$

Figure 7: Training loss of ResNet 18 on CIFAR100 and CIFAR10 at $\approx 10\%$
compression