# Compressed and distributed least-squares regression: convergence rates with
applications to Federated Learning

Constantin Philippenko
<EMAIL_ADDRESS>
École polytechnique, Institut Polytechnique de Paris, CMAP Aymeric Dieuleveut
<EMAIL_ADDRESS>
École polytechnique, Institut Polytechnique de Paris, CMAP

###### Abstract

In this paper, we investigate the impact of compression on stochastic gradient
algorithms for machine learning, a technique widely used in distributed and
federated learning. We underline differences in terms of convergence rates
between several unbiased compression operators, that all satisfy the same
condition on their variance, thus going beyond the classical worst-case
analysis. To do so, we focus on the case of least-squares regression (LSR) and
analyze a general stochastic approximation algorithm for minimizing quadratic
functions relying on a random field. We consider weak assumptions on the
random field, tailored to the analysis (specifically, expected Hölder
regularity), and on the noise covariance, enabling the analysis of various
randomizing mechanisms, including compression. We then extend our results to
the case of federated learning.

More formally, we highlight the impact on the convergence of the covariance
$\mathfrak{C}_{\mathrm{ania}}$ of the additive noise induced by the algorithm.
We demonstrate despite the non-regularity of the stochastic field, that the
limit variance term scales with
$\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)/K$ (where
$H_{F}$ is the Hessian of the optimization problem and $K$ the number of
iterations) generalizing the rate for the vanilla LSR case where it is
$\sigma^{2}\mathrm{Tr}\left(H_{F}H_{F}^{-1}\right)/K=\sigma^{2}d/K$ (Bach and
Moulines, 2013). Then, we analyze the dependency of
$\mathfrak{C}_{\mathrm{ania}}$ on the compression strategy and ultimately its
impact on convergence, first in the centralized case, then in two
heterogeneous FL frameworks.

##  1 Introduction

Large-scale optimization (Bottou and Bousquet, 2007) has become ubiquitous in
today’s learning problems due to the incredible growth of data collection. It
becomes computationally extremely hard to process a full dataset or even, to
store it on a single device (Abadi et al., 2016; Seide and Agarwal, 2016;
Caldas et al., 2019). This led practitioners to either process each
observation only once in a streaming fashion and to design distributed
algorithms. This paper is part of this line of work and considers in
particular stochastic federated algorithms (Konečný et al., 2016; McMahan et
al., 2017) that use a central server to orchestrate the training over a
network of $N$ in $\mathbb{N}^{*}$ clients.

A well-identified challenge in this framework is the communication cost of the
learning process (Seide et al., 2014; Chilimbi et al., 2014; Strom, 2015)
based on stochastic gradient algorithms. Indeed, iteratively exchanging
gradient or model information between the local workers and the central server
generates a huge computational and bandwidth bottleneck. To reduce this
communication cost, two strategies have been widely implemented and analyzed:
performing local updates (see e.g. McMahan et al., 2017; Karimireddy et al.,
2020), or reducing the size of the exchanged messages by passing them through
a compression operator, on the uplink channel (Seide et al., 2014; Alistarh et
al., 2017, 2018; Mishchenko et al., 2019; Karimireddy et al., 2019; Wu et al.,
2018; Horvath et al., 2022; Mishchenko et al., 2019; Li et al., 2020;
Richtarik et al., 2021), or on both uplink and downlink channels (Harrane et
al., 2018; Tang et al., 2019; Liu et al., 2020; Zheng et al., 2019;
Philippenko and Dieuleveut, 2020, 2021; Gorbunov et al., 2020b; Sattler et
al., 2019; Fatkhullin et al., 2021). These two strategies, although typically
analyzed independently, are often combined. We focus on compression; to reduce
the cost of exchanging a vector, three techniques are combined: (1) sending
the message to only a few clients, (2) sending only a fraction of the
coordinates, (3) sending low-precision updates.

Most analyses of the impact of compression schema rely on generic assumptions
on the compression operator $\mathcal{C}$, typically either contractive, i.e.
for any $z$ in $\mathbb{R}^{d}$, $\|\mathcal{C}(z)-z\|<(1-\delta)\|z\|$ with
$\delta\in]0;1[$ (almost surely or in expectation, see for instance Seide et
al., 2014; Stich et al., 2018; Karimireddy et al., 2019; Ivkin et al., 2019;
Koloskova et al., 2019; Gorbunov et al., 2020b; Beznosikov et al., 2020), or
unbiased with bounded variance increase, i.e., for any $z$ in
$\mathbb{R}^{d}$, $\mathbb{E}[\mathcal{C}(z)]=z$ and
$\mathbb{E}[\|\mathcal{C}(z)-z\|^{2}]\leq\omega\|z\|^{2}$ for a parameter
$\omega>1$ (see among others Alistarh et al., 2017; Wu et al., 2018;
Mishchenko et al., 2019; Chraibi et al., 2019; Gorbunov et al., 2020a;
Reisizadeh et al., 2020; Horvath et al., 2022; Kovalev et al., 2021;
Philippenko and Dieuleveut, 2020, 2021; Haddadpour et al., 2021; Li and
Richtárik, 2021; Khirirat et al., 2018). Unlike biased – and often
deterministic – operators, unbiased operators typically benefit from a
variance reduction proportional to the number of clients (e.g., Gorbunov et
al., 2020b vs Horváth et al., 2019).

In parallel, a line of work has thus focused on the design of compression
schemes satisfying one of these two assumptions (Bernstein et al., 2018; Dai
et al., 2019; Beznosikov et al., 2020; Horvath et al., 2022; Xu et al., 2020;
Leconte et al., 2021; Gandikota et al., 2021; Ramezani-Kebrya et al., 2021;
Horvath et al., 2022). Two fundamental strategies are typically combined: (1)
quantization (Rabbat and Nowak, 2005; Gersho and Gray, 2012; Alistarh et al.,
2018), and (2) random projection (Vempala, 2005; Rahimi and Recht, 2008;
Nesterov, 2012; Nutini et al., 2015). These methods are compared based on (1)
the number of bits required for storing or exchanging a $d$ dimensional vector
and (2) the resulting variance increase $\omega$ or contractiveness constant
$\delta$. Consequently, convergence results are worst-case results over the
class of compression operators: two compression operators satisfying the same
variance assumption are regarded as producing the same convergence rate.

The goal of this paper is to provide an in-depth analysis of compression
within a fundamental learning framework, namely least-squares regression (LSR,
Legendre, 1806), in order to highlight the differences in convergence between
several unbiased compression schemes having the same variance increase.

Especially, this analysis will highlight the impact of (1) the compression
scheme’s regularity (Lipschitz in squared expectation or not) and of (2) the
correlation between the compression of the different coordinates. We highlight
three examples of possible take-aways from our analysis, that will be detailed
in Section 3.

######  Take-away 1.

Quantization-based compression schemes do not have _Lipschitz in squared
expectation_ regularity but satisfy a Hölder condition. Because of that, their
convergence is degraded, yet they asymptotically achieve a rate comparable to
projection-based compressors, in which the limit covariance is similar.

######  Take-away 2.

Rand-$h$ and partial participation with probability $(h/d)$ satisfy the same
variance condition. Yet the convergence of compressed least mean squares
algorithms for partial participation is more robust to ill-conditioned
problems.

######  Take-away 3.

The asymptotic convergence rate is expected to be at least as good for
quantization than for sparsification or randomized coordinate selection, _if_
the features are standardized. On the contrary, if the features are
independent and the feature vector is normalized, then quantization is worse
than sparsification or randomized coordinate selection.

We consider a random-design LSR framework and make the following assumption on
the input-output pairs distribution

######  Model 1 (Federated case).

We consider $N$ clients. Each client $i$ in $[N]$ accesses $K$ in
$\mathbb{N}^{*}$ i.i.d. observations
$(x_{k}^{i},y_{k}^{i})_{k\in[K]}\sim\mathcal{D}_{i}^{\otimes K}$, such that
there exists a well-defined client-dependent model $w_{*}^{i}$:

$\displaystyle\forall k\in[K],\quad y_{k}^{i}=\left\langle
x_{k}^{i},w_{*}^{i}\right\rangle+\varepsilon_{k}^{i},\qquad\text{with}\leavevmode\nobreak\
\leavevmode\nobreak\
\varepsilon_{k}^{i}\sim\mathcal{N}(0,\sigma^{2})\leavevmode\nobreak\ \,,$ (1)

for an i.i.d. sequence $\left((\varepsilon_{k}^{i})_{k\in[K],i\in[N]}\right)$
independent from $\left((x_{k}^{i})_{k\in[K],i\in[N]}\right)$. We use the
generic notation $(x^{i},y^{i},\varepsilon^{i})$ for such an input-output-
noise triplet on client $i$. Moreover, we assume that the inputs’ second
moment111In the following, we may refer to this matrix $H$ as the covariance
(in the case of centered features, covariance is equal to the second moment)
is bounded to define $\mathbb{E}[x^{i}\otimes x^{i}]=H_{i}$ and
$\mathbb{E}[\|{x^{i}}\|^{2}]=R^{2}_{i}$; such that
$\mathbb{E}[\|{x^{i}}\|^{2}x^{i}\otimes x^{i}]\preccurlyeq R_{i}^{2}H_{i}$.
For any $i\in[N]$, we consider the expected squared loss on client $i$ of a
model $w$ as
$F_{i}(w):=\frac{1}{2}\mathbb{E}_{(x^{i},y^{i})\sim\mathcal{D}_{i}}[(\left\langle
x^{i},w\right\rangle-y^{i})^{2}]$.

######  Remark 1 (Almost surely bounded features).

In the case of linear compressors, we will also assume that for each client
$i$ in $[N]$, features are almost surely bounded by $R_{i}^{2}$.

This model is classical in the single worker case (e.g. Hsu et al., 2012; Bach
and Moulines, 2013):

######  Model 2 (Centralized case).

We consider Model 1 with $N=1$ client. For simplicity, we then omit the $i$
superscript.

We focus on the problem of minimizing the global expected risk
$F:\mathbb{R}^{d}\rightarrow\mathbb{R}$, thus finding the optimal model
$w_{*}$ in $\mathbb{R}^{d}$ such that:

$\displaystyle
w_{*}=\operatorname*{arg\,min}_{w\in\mathbb{R}^{d}}\left\\{F(w):=\frac{1}{N}\sum_{i=1}^{N}F_{i}(w)\right\\}\leavevmode\nobreak\
\leavevmode\nobreak\ $ (OPT)

Note that we assume that
$\mathrm{Span}\\{\mathrm{Supp}(x^{i}),i\in{[N]}\\}=\mathbb{R}^{d}$ to ensure
the existence and uniqueness of $w_{*}$.

The empirical version of the risk minimization admits an explicit formula, yet
is computationally too expensive to compute for large problems. This is why,
in practice, LSR is solved using iterative stochastic algorithms, for example
Stochastic Gradient Descent (SGD, see Robbins and Monro, 1951). SGD for LSR is
often referred to as the _Least Mean Squares_ (LMS) algorithm (Bershad, 1986;
Macchi, 1995). Analysis of LMS (Györfi and Walk, 1996; Bach and Moulines,
2013) and its variants received a lot of interest over the last decades.
Indeed despite its simplicity, LSR is a model of choice for practitioners
because of its efficiency to train good and interpretable models (see e.g.
Molnar, 2018, chapter 5.1). Moreover, its simplicity enables to isolate and
analyze challenges faced in specific configurations, for instance, non-strong
convexity (Bach and Moulines, 2013), interaction between acceleration and
stochasticity (Dieuleveut et al., 2017; Jain et al., 2018a; Varre and
Flammarion, 2022), non-uniform iterate averaging (Jain et al., 2018b; Neu and
Rosasco, 2018; Muecke et al., 2019), infinite-dimensional frameworks
(Dieuleveut and Bach, 2016), or over-parametrized regimes and double descent
phenomena (Belkin et al., 2019).

Our approach follows this line of work: our goal is to analyze the impact of
compression in FL algorithms, by providing a careful study of compressed LMS,
based on a fine-grained analysis of Stochastic Approximation (SA) under weak
assumptions on the random field. More precisely, we consider linear stochastic
approximation recursion, to find a zero of the linear mean-field $\nabla F$.

######  Definition 1 (Linear Stochastic Approximation, LSA).

Let $w_{0}\in\mathbb{R}^{d}$ be the initialization, the linear222While in LSA
literature, both the mean-field $\nabla F$ and the noise-field $(\xi_{k})$ are
linear, we do not here consider the noise fields to be linear.  stochastic
approximation recursion is defined as:

$w_{k}=w_{k-1}-\gamma\nabla F(w_{k-1})+\gamma\xi_{k}(w_{k-1}-w_{*}),\ \
k\in\mathbb{N},$ (LSA)

where $\gamma>0$ is the step-size and $(\xi_{k})_{k\in\mathbb{N}^{*}}$ is a
sequence of i.i.d. zero-centered random fields that characterizes the
stochastic oracle on $\nabla F(\cdot)$. For any $k\in\mathbb{N}^{*}$, we
denote $\mathcal{F}_{k}=\sigma\left(\xi_{1},\dots,\xi_{k}\right)$, such that
the filtration $(\mathcal{F}_{k})_{k\geq 0}$ is adapted to $(w_{k})_{k\geq
0}$.

We assume that $F$ is quadratic, we denote $H_{F}$ its Hessian,
$R_{F}^{2}:=\mathrm{Tr}\left(H_{F}\right)$ its trace and $\mu$ its smallest
eigenvalue. For any $k$ in $\mathbb{N}$, with $\eta_{k}=w_{k}-w_{*}$, we get
equivalently:

$\eta_{k}=(\mathrm{I}-\gamma H_{F})\eta_{k-1}+\gamma\xi_{k}(\eta_{k-1}),\ \
k\in\mathbb{N}.$

As underlined by Bach and Moulines (2013), (LSA) corresponds to a homogeneous
Markov chain. A study of stochastic approximation using results and techniques
from the Markov chain literature can be found for instance in Freidlin and
Wentzell (1998) or more recently in Dieuleveut et al. (2020).

(LSA) encompasses three examples of interest, the first one is the classical
LMS algorithm. Indeed, with the observations in Models 1 and 2, for any client
$i\in[N]$, any iteration $k$ in $[K]$, any model $w\in\mathbb{R}^{d}$,

$\textsl{g}_{k}^{i}(w):=(\left\langle x_{k}^{i},w\right\rangle-
y_{k}^{i})x_{k}^{i}$ (2)

is an unbiased oracle of $\nabla F_{i}(w)$. This can be used to define the
following three algorithms.

######  Algorithm 1 (LMS).

For LMS algorithm, with a single worker, we have for all $k\in\mathbb{N}$,
$w_{k}=w_{k-1}-\gamma\textsl{g}_{k}(w_{k-1})=w_{k-1}-\gamma(\left\langle
x_{k},w_{k-1}\right\rangle-y_{k})x_{k}$, thus equivalently
$\xi_{k}(\cdot)=(x_{k}x_{k}^{\top}-\mathbb{E}[x_{1}x_{1}^{\top}])(\cdot)+(\left\langle
w_{*},x_{k}\right\rangle-y_{k})x_{k}$.

Second, the case of a single client compressed LMS algorithm.

######  Algorithm 2 (Centralized compressed LMS).

A single client ($N=1$) observes at any step $k\in[K]$ an oracle
$\textsl{g}_{k}(\cdot)$ on the gradient of the objective function $F$, and
applies a random compression mechanism $\mathcal{C}_{k}(\cdot)$. Thus, for any
step-size $\gamma>0$ and any $k\in\mathbb{N}^{*}$, the resulting sequence of
iterates $(w_{k})_{k\in\mathbb{N}}$ satisfies:
$w_{k}=w_{k-1}-{\gamma}\mathcal{C}_{k}(\textsl{g}_{k}(w_{k-1}))\,.$

And finally, the extension to the distributed case.

######  Algorithm 3 (Distributed compressed LMS).

In our motivating example, each client $i\in[N]$ observes at any step
$k\in[K]$ an oracle $\textsl{g}_{k}^{i}(\cdot)$ on the gradient of the local
objective function $F_{i}$, and applies a random compression mechanism
$\mathcal{C}_{k}^{i}(\cdot)$. Thus, for any step-size $\gamma>0$ and any
$k\in\mathbb{N}^{*}$, the resulting sequence of iterates
$(w_{k})_{k\in\mathbb{N}}$ satisfies:
$w_{k}=w_{k-1}-\frac{\gamma}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w_{k-1}))\,$
(we consider the randomization made on clients
$(\mathcal{C}_{k}^{i}(\cdot))_{i\in\\{1\cdots,N\\}}$ to be independent)

######  Remark 2.

The analysis naturally covers any randomized postprocessing
$\mathcal{C}_{k}^{i}(\cdot)$, beyond the compression case.

##### Challenges, contributions and structure of the paper.

Although there is abundant literature on the study of (LSA), the application
to Algorithms 2 and 3 poses novel challenges. Especially, most analyses of LSA
(Blum, 1954; Ljung, 1977; Ljung and Söderström, 1983) assume that the field
$\xi_{k}$ is linear (i.e. for any $z,z^{\prime}\in\mathbb{R}^{d},\
\xi_{k}(z)-\xi_{k}(z^{\prime})=\xi_{k}(z-z^{\prime})$, see Konda and
Tsitsiklis, 2003; Benveniste et al., 2012; Leluc and Portier, 2022). More
general non-asymptotic results on SA with a Lipschitz mean-field (i.e. SGD
with a smooth objective) also assume that the noise-field is Lipschitz-in-
squared-expectation i.e. for any
$z,z^{\prime}\in\mathbb{R}^{d},\mathbb{E}[\|\xi_{k}(z)-\xi_{k}(z^{\prime})\|^{2}]\leq
C\|z-z^{\prime}\|^{2}$ (Moulines and Bach, 2011; Bach, 2014; Dieuleveut et
al., 2020; Gadat and Panloup, 2023). One major specificity and bottleneck in
the case of compression is the fact that the resulting field does not satisfy
such an assumption. The rest of the paper is thus organized as follows:

  1. 1.

In Section 2, we provide a non-asymptotic analysis of (LSA) under weak
regularity assumptions of the noise field $(\xi_{k})_{k}$. We show that the
asymptotically dominant term depends on the covariance matrix
$\mathfrak{C}_{\mathrm{ania}}$ of the additive noise induced by the algorithm,
as expected from the classical asymptotic literature (Polyak and Juditsky,
1992). The backbone results of our paper are Theorems 1 and 2 which generalize
the results from Bach and Moulines (2013) for Algorithm 1. The limit
convergence rate term scales with
$\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)/K$, which
highlights the interaction between the Hessian of the optimization problem
$H_{F}$, and the additive noise’s covariance $\mathfrak{C}_{\mathrm{ania}}$.

  2. 2.

In Section 3, we prove that assumptions made in Section 2 are valid for
Algorithm 2 with classical compression schemes. Although this single-client
case is a simple configuration, it enables to describe the impact of the
compressor choice on the dependency between the features’ covariance $H$
(which is also the Hessian $H_{F}$ of the optimization problem) and the
additive noise’s covariance $\mathfrak{C}_{\mathrm{ania}}$. Contrary to
Algorithm 1, for which the noise is said to be structured, i.e. the additive
noise’s covariance is proportional to the Hessian $H_{F}$, applying a random
compression mechanism on the gradient breaks this structure. This phenomenon
is noteworthy: for an ill-conditioned $H_{F}$, it may lead to a drastic
increase in $\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)$
and thus, to a degradation in convergence. By calculating the additive noise’s
covariance for various compression mechanisms, we identify differences that
classical literature was unable to capture.

  3. 3.

In Section 4, we study the distributed Algorithm 3 with heterogeneous clients.
We examine two different sources of heterogeneity for which we show that
Theorems 1 and 2 remain valid. First, the case of heterogeneous features’
covariances $(H_{i})_{i=1}^{N}$ in Subsection 4.1; second, the case of
heterogeneous local optimal points $(w_{*}^{i})_{i=1}^{N}$ in Subsection 4.2.

These results are validated by numerical experiments which help to get an
intuition of the underlying mechanisms. The code is provided on our GitHub
repository. We summarize hereafter the structure of the paper in Figure 1.

Figure 1: Flow chart summarizing our results.

##### Notations.

We denote by $\preccurlyeq$ the order between self-adjoint operators, i.e.,
$A\preccurlyeq B$ if and only if $B-A$ is positive semi-definite (p.s.d.) and
$A\mathrel{\mathop{\preccurlyeq}\limits^{\vbox
to-0.90417pt{\kern-2.0pt\hbox{$\scriptstyle\sim$}\vss}}}B$ if $A\preccurlyeq
B$ and $A=B+O(\frac{1}{d})$. We denote by $A^{1/2}$ the p.s.d. square root of
any symmetric p.s.d. matrix $A$. For two vectors $x,y$ in $\mathbb{R}^{d}$,
the Kronecker product is defined as $x\otimes y:=xy^{\top}$, the element-wise
product is denoted as $x\odot y$, and the Euclidean norm is
$\|x\|^{2}:=\sum_{i=1}^{d}x_{i}^{2}$. For any rectangular matrix $A$ in
$\mathbb{R}^{n\times m}$ s.t. $AA^{\top}$ is inversible, we denote
$A^{\dagger}:=A^{\top}(AA^{\top})^{-1}$ the Moore–Penrose pseudo inverse. For
$x,y$ in $\mathbb{R}^{d}$, we use $x\wedge y$ for the minimum between two
values, and $x\mathrel{\mathop{\leq}\limits^{\vbox
to-0.60275pt{\kern-2.0pt\hbox{$\scriptstyle\sim$}\vss}}}y$ if $x\leq y$ and
$x=y+O(\frac{1}{d})$. For any sequence of vector
$(x_{k})_{k\in\\{0,\dots,K\\}}$ we denote
$\overline{x}_{K-1}=\sum_{k=0}^{K-1}x_{k}/K$. We use $e_{i}$ to denote the
vector in $\mathbb{R}^{d}$ with zero everywhere except at coordinate $i$, and
$\mathcal{O}_{d}(\mathbb{R})$ the group of orthogonal matrices. Finally, all
random variables are defined on a probability space
$(\Omega,\mathcal{A},\mathbb{P}),\mathbb{E}$ is the expectation associated
with the probability $\mathbb{P}$ and $\mathcal{A}$ is a $\sigma$-algebra. We
define the set of probability distribution function $\mathcal{P}_{M}$ whose
second moment is equal to $M$ in $\mathbb{R}^{d\times d}$:
$\mathcal{P}_{M}=\\{\text{probability distribution
}p_{M}\text{\leavevmode\nobreak\ over $\mathbb{R}^{d}$
s.t.},\mathbb{E}_{\varepsilon\sim p_{M}}[\varepsilon^{{\otimes 2}}]=M\\}\,.$
Any such distribution $p_{M}$ is indexed with its matrix of covariance.

##  2 Non asymptotic convergence result for (LSA)

###  2.1 Definition of the additive noise’s covariance and assumptions on the
random fields

For any $k$ in $\mathbb{N}^{*}$, we define the additive noise
$\xi_{k}^{\mathrm{add}}$ and the multiplicative noise
$\xi_{k}^{\mathrm{mult}}(\cdot)$.

######  Definition 2 (Additive and multiplicative noise).

Under the setting of Definition 1, for any $k$ in $\mathbb{N}^{*}$, we define:

$\xi_{k}^{\mathrm{add}}:=\xi_{k}(0)\qquad\text{and}\qquad\xi_{k}^{\mathrm{mult}}:z\in\mathbb{R}^{d}\mapsto\xi_{k}(z)-\xi_{k}^{\mathrm{add}}\,.$

######  Remark 3.

Observe that $(\xi_{k}^{\mathrm{add}})_{k\in\mathbb{N}^{*}}$ is an i.i.d.
sequence of random variables and
$(\xi_{k}^{\mathrm{mult}})_{k\in\mathbb{N}^{*}}$ is an i.i.d. sequence of
random field. The following assumptions, made for $k=1$, are thus equivalently
valid for any $k\geq 1$.

######  Assumption 1 (Second moment).

${\xi_{1}^{\mathrm{add}}}$ admits a second order moment. We note $\mathcal{A}$
in $\mathbb{R}^{d}$ s.t.
$\mathbb{E}[\|\xi_{1}^{\mathrm{add}}\|^{2}]\leq\mathcal{A}$.

Assumptions 1 and 3 enable us to define the covariance of the additive noise
induced by the algorithm.

######  Definition 3 (Additive noise’s induced by the algorithm’s
covariance.).

Under the setting of Definition 1, we define the _additive noise’s covariance_
as the covariance of the additive noise:
$\mathfrak{C}_{\mathrm{ania}}=\mathbb{E}[\xi_{1}^{\mathrm{add}}\otimes\xi_{1}^{\mathrm{add}}]\,.$

Secondly, we state our assumptions on the multiplicative part of the noise,
especially its regularity around 0 (note that $\xi_{1}^{\mathrm{mult}}(0)=0$).

######  Assumption 2 (Second moment of the multiplicative noise).

There exist two constants $\mathcal{M}_{1},\mathcal{M}_{2}>0$ such that, for
any $\eta$ in $\mathbb{R}^{d}$, the following hold:

  1. ALABEL:enumiasu:main:second_moment_noise.1:

$\mathbb{E}[\|{\xi_{1}^{\mathrm{mult}}(\eta)}\|^{2}]\leq
2\mathcal{M}_{2}\|{H_{F}^{1/2}\eta}\|^{2}+{4\mathcal{A}\,}.$

  2. ALABEL:enumiasu:main:second_moment_noise.2:

$\mathbb{E}[\|{\xi_{1}^{\mathrm{mult}}(\eta)}\|^{2}]\leq\mathcal{M}_{1}\|H_{F}^{1/2}\eta\|+3\mathcal{M}_{2}\|H_{F}^{1/2}\eta\|^{2}.$

The main originality of this section is the analysis under Item 2.2. This
Hölder-type condition will appear naturally for compression in Section 3. Up
to our knowledge, (LSA) has not been analyzed under this particular condition.

Under these assumptions, asymptotic results from Polyak and Juditsky (1992)
can be applied. Especially, we establish the asymptotic normality of
$(\sqrt{K}\overline{\eta}_{K-1})_{K>0}$, with an asymptotic variance equal to
$H_{F}^{-1}\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}$.

######  Proposition 1 (CLT for (LSA)).

Under Assumptions 1 and 2, consider a sequence $(w_{k})_{k\in\mathbb{N}^{*}}$
produced in the setting of Definition 1 for a step-size
$(\gamma_{k})_{k\in\mathbb{N}^{*}}$ s.t. $\gamma_{k}=k^{-\alpha}$,
$\alpha\in]0,1[$. Then $(\sqrt{K}\overline{\eta}_{K-1})_{K>0}$ is
asymptotically normal and converge in distribution to
$\mathcal{N}(0,H_{F}^{-1}\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1})$.

The proof of this result is almost straightforward and is recalled in
Subsection A.4. In the following, we establish non-asymptotic results in
Theorems 2 and 1, that highlight the impact of Item 2.2.

###  2.2 Convergence rates for (LSA), general case

In this section, we present non-asymptotic convergence rates for (LSA) under
the assumptions above. These results build upon the work of Bach and Moulines
(2013). Our first result is the main result, under the Hölder assumption on
the noise field, it is demonstrated in Appendix B.

######  Theorem 1 (Non-linear multiplicative noise).

Under Assumptions 2 and 1, consider a sequence $(w_{k})_{k\in\mathbb{N}^{*}}$
produced in the setting of Definition 1 for a constant step-size $\gamma$ such
that $\gamma(R_{F}^{2}+2\mathcal{M}_{2})\leq 1/2$. Then for any horizon $K$,
we have:

$\displaystyle\mathbb{E}[F(\overline{w}_{K-1})-F(w_{*})]$
$\displaystyle\leq\frac{1}{2K}\Bigg{(}\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|}{\displaystyle\gamma\sqrt{K}}\wedge\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+\left(10\mathcal{A}\gamma\right)^{1/4}\sqrt{\mathcal{M}_{1}\mu^{-1}}$
$\displaystyle\qquad\qquad+\left(30\mathcal{A}\gamma\right)^{1/2}\sqrt{\mathcal{M}_{2}\mu^{-1}}\Bigg{)}^{2}\,.$

The first two terms of the RHS correspond respectively to the impact of the
initial condition $\eta_{0}$ and the impact of the additive noise. The
dependency on these two terms is similar to the one established in Bach and
Moulines (2013) in the case of LMS. Note that following Defossez and Bach
(2015), we improve the dependency on the initial condition to
$\frac{\|\eta_{0}\|^{2}}{\gamma
K}\wedge\frac{\|H_{F}^{-1/2}\eta_{0}\|^{2}}{\gamma^{2}K^{2}}$. Regarding the
noise term, the dependency on
$\frac{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}{2K}$
corresponds to the classical asymptotic noise term in CLT for Stochastic
Approximation (e.g., Delyon, 1996; Duflo, 1997; Györfi and Walk, 1996). In
fact, for a sequence of step sizes $\gamma_{t}$ decreasing to zero, we recover
the variance from Proposition 1. Remark that in (Bach and Moulines, 2013) and
several follow up works, the algorithm under consideration is LMS (Algorithm
1, which enables to ensure that
$\mathfrak{C}_{\mathrm{ania}}\preccurlyeq\sigma^{2}H_{F}$: the variance term
thus scales as $\sigma^{2}d/K$. On the contrary, Algorithms 2 and 3 do not
always satisfy $\mathfrak{C}_{\mathrm{ania}}\preccurlyeq\sigma^{2}H_{F}$: in
such case, $\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)$
may scale as $1/\mu$.

The third and fourth term, that scale respectively as $\sqrt{\gamma}/K$ and
$\gamma/K$, are asymptotically negligible for $\gamma=o(1)$. Those term are
proportional to the Hölder-regularity constants
$\mathcal{M}_{1},\mathcal{M}_{2}$, and also increase with $\mu^{-1}$. The
dominant term is $\frac{\mathcal{M}_{1}\sqrt{10\mathcal{A}\gamma}}{\mu K}$.
Interestingly, when $\gamma$ is constant (not decreasing with $K$), then the
limit variance of the algorithm is affected. Moreover, contrary to (Bach and
Moulines, 2013), we do not recover a convergence rate independent of $\mu$.
This dependency is un-avoidable as the multiplicative noise is only controlled
around $w_{*}$: without strong-convexity, the iterates may not converge to
$w_{*}$. While these additional terms in the variance may be considered as a
drawback, it can be mitigated by taking a step-size $\gamma$ proportional to
$1/K^{\alpha}$ with $\alpha>0$ small ($\gamma$ is horizon dependent, but
constant).

######  Corollary 1.

Under the assumptions of Theorem 1, with $\gamma=1/K^{\alpha}$, and
$\alpha\in]0,1/2[$, we have:

$\displaystyle\mathbb{E}[F(\overline{w}_{K-1})-F(w_{*})]$ $\displaystyle\leq$
$\displaystyle\frac{60}{K}\Bigg{(}{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|^{2}}{\displaystyle
K^{(1-2\alpha)}}+\frac{{\mathcal{M}_{1}}\sqrt{\mathcal{A}}}{\mu
K^{\alpha/2}}+\frac{{\mathcal{M}_{2}}\mathcal{A}}{\mu K^{\alpha}}\Bigg{)}\,.$

The decrease of the second order terms is then optimized for $\alpha=2/5$. To
highlight the impact of the non-linearity in compression schemes, we provide
for comparison the result for a linear multiplicative noise.

###  2.3 Convergence rates for (LSA), linear case

Alternatively, to cover the particular case of a linear multiplicative noise
(e.g., to recover LMS or projection-based compressed LMS) we make the
following stronger hypothesis:

######  Assumption 3.

The multiplicative noise is linear i.e. there exists a random matrix $\Xi_{1}$
in $\mathbb{R}^{d\times d}$ s.t. for any $\eta$ in $\mathbb{R}^{d}$, we have
a.s. $\xi_{1}^{\mathrm{mult}}(\eta)=\Xi_{1}\eta$. Moreover
$\mathbb{E}[\|{\xi_{1}^{\mathrm{mult}}(\eta)}\|^{2}]\leq\mathcal{M}_{2}\|H_{F}^{1/2}\eta\|^{2}$.

######  Remark 4.

Note that $\Xi_{1}$ is not necessarily symmetric (in Algorithms 3 and 2, this
results from the compression).

In addition to Assumption 3, in the case of linear multiplicative noise, we
also consider the following assumption.

######  Assumption 4.

The following hold.

  1. ALABEL:enumiasu:main:baniac_lin.1:

There exists a constant333This letter $\Sha$ is the Russian upper letter
“sha”. $\Sha_{\mathrm{add}}>0$ s.t.
$\mathfrak{C}_{\mathrm{ania}}\preccurlyeq\Sha_{\mathrm{add}}H_{F}$.

  2. ALABEL:enumiasu:main:baniac_lin.2:

There exists a constant $\Sha_{\mathrm{mult}}>0$, such that
$\mathbb{E}\left[\Xi_{1}\Xi_{1}^{\top}\right]\preccurlyeq\Sha_{\mathrm{mult}}H_{F}$.

######  Remark 5 (Link between Assumptions 4, 2 and 1).

Assumption 1 (resp. Assumption 2) corresponds to an assumption on the second
order moment of the additive noise (resp. multiplicative), while Item 4.1
(resp. Item 4.2) is a (stronger) assumption on its covariance.

######  Theorem 2 (Linear multiplicative noise).

Under Assumptions 1, 3 and 4, i.e., with a linear multiplicative noise.
Consider a sequence $(w_{k})_{k\in\mathbb{N}^{*}}$ produced in the setting of
Definition 1, for a constant step-size $\gamma$ such that
$\gamma(R_{F}^{2}+\mathcal{M}_{2})\leq 1$ and $4\Sha_{\mathrm{mult}}\gamma\leq
1$. Then for any horizon $K$, we have

$\displaystyle\mathbb{E}[F(\overline{w}_{K-1})-F(w_{*})]\leq\frac{1}{2K}\left(\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+2\left(\gamma
d\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}\right)^{1/2}\right)^{2}\,.$

Theorem 2 generalizes Theorem 1 from Bach and Moulines (2013). It also
highlights the impact of additive noise’s covariance, and the comparison
between Theorem 1 and Theorem 2 shows the advantage of linear compression
schemes. Indeed the variance scales as
$K^{-1}(\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)+4\gamma
d\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}})$. As before, the first term
$\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)$ corresponds
to the asymptotic variance given in Proposition 1, and the second term is
negligible: (i) for all $4\Sha_{\mathrm{mult}}\gamma\leq 1$ it can be upper
bounded by $d\Sha_{\mathrm{add}}$, and for LMS (see Bach and Moulines, 2013),
the variance term is
$\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)=d\sigma^{2}$,
which is thus at least as large, (ii) it scales with $\gamma$ thus is
asymptotically negligible as $\gamma$ tends to $0$. Overall, depending on
$\mathfrak{C}_{\mathrm{ania}}$, the algorithm may or may not suffer from the
lack of strong-convexity ($\mu$ tending to $0$). More precisely, in the case
of linear multiplicative noise, we can obtain a $O(K^{-1})$ rate independent
of $\mu$ if and only if $\mathfrak{C}_{\mathrm{ania}}\preccurlyeq aH_{F}$,
with $a$ in $\mathbb{R}$. The proof of Theorem 2 is given in Appendix C, and
follows the line of proof of Bach and Moulines (2013).

Conclusion: we established rates for (LSA) for both the Hölder-noise case and
the linear noise case. In the former, convergence requires strong convexity
while in the latter, we can achieve $O(K^{-1})$ for
$\mathfrak{C}_{\mathrm{ania}}\preccurlyeq aH_{F}$. In both cases, the dominant
term for an optimal choice of $\gamma$ scales as
$\frac{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}{K}$.

In the following section, we turn to the analysis of Algorithm 2: we show how
the choice of the compression impacts both the linearity of the noise and the
structure of $\mathfrak{C}_{\mathrm{ania}}$.

##  3 Application to Algorithm 2: compressed LSR on a single worker

In this section, we analyze Algorithm 2, i.e. compressed LSR. In Subsection
3.1, we introduce the compression operators of interest and verify in
Subsection 3.2 that Theorems 2 and 1 can be applied. Then, in Subsection 3.3,
we provide explicit formulas of
$\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H^{-1}\right)$ for various
compression schemes. Finally, in Subsection 3.4, we validate our findings with
numerical experiments.

###  3.1 Compression operators

Our analysis applies to most unbiased compression operators.

######  Definition 4 (Compression operators).

Let $z\in\mathbb{R}^{d}$.

  1. 1.

$1$-quantization is defined as
$\mathcal{C}_{\mathrm{q}}(z):=\|z\|\mathrm{sign}(z)\odot\chi\text{\leavevmode\nobreak\
with\leavevmode\nobreak\
}\chi\sim\otimes_{i=1}^{d}(\mathrm{Bern}(|z_{i}|/\|z\|_{2})).$

  2. 2.

Stabilized $1$-quantization is defined as
$\mathcal{C}_{\mathrm{sq}}(z):=U^{\top}\mathcal{C}_{q}(Uz)$, with
$U\in\mathrm{Unif}(\mathcal{O}_{d})$.

  3. 3.

Rand-$h$ is defined as $\mathcal{C}_{\mathrm{rd}h}(z):=\frac{d}{h}B(S)\odot z$
with $S\sim\mathrm{Unif}(\mathcal{P}_{h}([d]))$ and $B(S)_{i}=\mathbb{1}_{i\in
S}$.

  4. 4.

Sparsification is defined as $\mathcal{C}_{\mathrm{s}}(z):=\frac{1}{p}B\odot
z\in\mathbb{R}^{d}\text{\leavevmode\nobreak\ with\leavevmode\nobreak\
}B\sim\otimes_{i=1}^{d}\left(\mathrm{Bern}(p)\right)\,.$

  5. 5.

Partial participation is defined
$\mathcal{C}_{\mathrm{PP}}(z):=\frac{b_{0}}{p}z$ with
$b_{0}\sim\mathrm{Bern}(p)$.

  6. 6.

Random Projection, also referred to as _sketching_ , is defined as
$\mathcal{C}_{\Phi}(z):=\frac{1}{p}\Phi^{\dagger}\Phi z$, where $h\ll
d\in\mathbb{N}$, $p=h/d$ and $\Phi\in\mathbb{R}^{h\times d}$ is a random
projection matrix onto a lower-dimension space (Vempala, 2005; Li et al.,
2006). In the following, we consider Gaussian projection, where each element
$i,j\in\llbracket 1,h\rrbracket\times\llbracket 1,d\rrbracket$ follows an
independent zero-centered normal distribution.

We refer to the introduction for related work on compression. Operators
$\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}}$ are quantization-based
schemes while
$\mathcal{C}_{\mathrm{rd}1},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\Phi}$
are projection-based. Indeed sparsification can be seen as a random projection
(for $h\ll d$, $p=h/d$ and $h$ randomly sampled coordinates $\mathcal{I}$ from
$\llbracket 1,d\rrbracket$ such that for any $i\in\mathcal{I}$, the $i^{th}$
lines of $\Phi$ are equal to $e_{i}\in\mathbb{R}^{d}$, and equal to zero
otherwise). For $\mathcal{C}_{\mathrm{PP}}$, the motivation is distributed
settings, in which the intermittent availability of clients prevents them from
systematically participating in the training. This can be modeled through
partial participation: clients only participate in a fraction $p$ of the
training steps. In theoretical analyses, this can be handled as a compression
scheme $\mathcal{C}_{\mathrm{PP}}$, in which the compression of a vector $z$
is either $z/p$ or 0. Observe that in the centralized case, this is slightly
artificial as it actually means that no update is performed at most steps and
that the step-size is scaled at the other steps. Finally, we denote
$\mathcal{C}_{\mathrm{I}_{d}}:z\in\mathbb{R}^{d}\mapsto z$ the operator that
does not carry out any compression.

######  Remark 6.

The analysis of random projection is related to Random features (Rahimi and
Recht, 2008), usually used for Kernel learning in infinite dimensions. Nyström
method (introduced by Kumar et al., 2009) is another similar technique of
compression often used in this setting, it consists of removing a subset
$\mathcal{S}\subset\\{1,\cdots,d\\}$ of lines and columns in the kernel matrix
$K$. Both techniques have been extensively studied in the context of linear
and non-linear kernel learning (Rudi et al., 2015, 2017; Rudi and Rosasco,
2017; Lin and Rosasco, 2017). Recently, the combination of SGD and random
features has been analyzed by Carratino et al. (2018). However, their results
cannot be directly applied to our setting for two reasons. Firstly, their
analysis is for infinite dimensions, where they obtain a $O(1/\sqrt{K})$ rate
of convergence. Secondly, the compressions used in their approach are not
independent at each iteration.

######  Remark 7.

Diffusion LMS (i.e. distributed learning without a central server) has also
been studied from the perspective of low-cost training by Arablouei et al.
(2015); Harrane et al. (2018), but using only clients’ partial participation
or sparsification. Contrary to our work they use biased compression and an
adaptive correction step to compensate for the induced error. They provide
results guarantying asymptotic convergence (Harrane et al., 2018, see
Equations (28)-(37)).

###  3.2 Applicability of the results on (LSA) from Section 2

We first show that our results from Section 2 can be applied for Algorithm 2
with a random compression operator $\mathcal{C}$, in the case of Model 2.

######  Lemma 1.

For any compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$,
there exists constants $\omega,\Omega\in\mathbb{R}^{*}_{+}$, such that the
random operator $\mathcal{C}$ satisfies the following properties for all
$z,z^{\prime}\in\mathbb{R}^{d}$.

  1. L.1:

$\mathbb{E}[\mathcal{C}(z)]=z$ and
$\mathbb{E}[\|\mathcal{C}(z)-z\|^{2}]\leq\omega\|z\|^{2}$ (unbiasedness and
variance relatively bounded),

  2. L.2:

$\mathbb{E}[\|\mathcal{C}(z)-\mathcal{C}(z^{\prime})\|^{2}]\leq\Omega\min(\|z\|,\|z^{\prime}\|)\|z-z^{\prime}\|+3(\omega+1)\|z-z^{\prime}\|^{2}\text{(Hölder-
type bound),}$

with $\omega=\sqrt{d}$ and $\Omega=12\sqrt{d}$ (resp. $\omega=(1-p)/p$ and
$\Omega=0$) for $\mathcal{C}_{\mathrm{q}}$ and $\mathcal{C}_{\mathrm{sq}}$
(resp. $\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}}$,
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}$).

We note $\mathbb{C}$ the set of unbiased compressors verifying Lemma 1. Item
L.1 is frequently established in the literature and corresponds to the worst-
case assumption, see the introduction for references. On the other hand, Item
L.2 is the Hölder-type bound, which is not used in the literature up to our
knowledge. The expected squared distance between the compression of two nearby
points scales with the _non-squared_ norm of the distance. Moreover, the
distance is multiplied by an unavoidable coefficient scaling with
$z,z^{\prime}$. Remark that in Item L.2, we assume the compression randomness
to be the same for the compression of $z$ and $z^{\prime}$: formally, we
control $\mathcal{W}_{2}(\mathcal{C}(z),\mathcal{C}(z^{\prime}))^{2}$, with
$\mathcal{W}_{2}$ the Wassertein-$2$ distance. This lemma is demonstrated in
Subsection E.1.

######  Remark 8.

For a given $\omega$, note that the _communication cost_ $c$ for quantization-
based and projection-based compressors is not always equivalent. For
$1$-quantization we have $c\approx\frac{3}{2}\sqrt{d}\log_{2}{d}+32$ while for
projection-based we have $c\approx 32\sqrt{d}$, for $\sqrt{d}$-quantization we
have $c\approx 3d+32$ while for projection-based we have $c=16d$.

Lemma 1 enables to show that Theorems 2 and 1 Algorithm 2 are valid in the
context of Model 2.

######  Corollary 2.

Consider Algorithm 2 in the context of Model 2, with a compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},$
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$. With Lemma 1 above,
Assumptions 2 and 1 on the resulting random field
$(\xi_{k})_{k\in\mathbb{N}^{*}}$ are valid, with in particular $H_{F}=H$,
$R_{F}^{2}=R^{2}$, $\mathcal{A}=(\omega+1)R^{2}\sigma^{2}$,
$\mathcal{M}_{2}=(\omega+1)R^{2}$, $\mathcal{M}_{1}=\Omega R^{2}\sigma$.
Therefore, it follows that Theorem 1 holds.

Moreover for any linear compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},$
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$, under Remark 1, we also
have that Assumptions 3 and 4 are valid with
$\Sha_{\mathrm{add}}=\sigma^{2}\Sha_{H}$ and
$\Sha_{\mathrm{mult}}=R^{2}\Sha_{H}$, with $\Sha_{H}$ given below. Therefore,
it follows that Theorem 2 holds.

Compressor | $\mathcal{C}_{\mathrm{rd}h}$ | $\mathcal{C}_{\mathrm{s}}$ | $\mathcal{C}_{\mathrm{PP}}$ | $\mathcal{C}_{\Phi}$
---|---|---|---|---
$\Sha_{H}$ | $\frac{h-1}{p(d-1)}+(1-\frac{h-1}{d-1})\frac{\tau}{p}$ | $1+\frac{(1-p)\tau}{p}$ | $\frac{1}{p}$ | $\frac{\alpha-\beta}{p}+\frac{\beta\tau}{p}$
$\Sha_{H}$ (if $H$ diagonal) | $\frac{1}{p}$ | $\frac{1}{p}$ | $\frac{1}{p}$ | $\frac{\alpha-\beta}{p}+\frac{\beta\tau}{p}$

Where $p=h/d$, $\tau=\mathrm{Tr}\left(H\right)/\mu$, and for sketching
$\alpha=\frac{h+2}{d+2}$ and $\beta=\frac{d-h}{(d-1)(d+2)}$.

This corollary is proved in Appendix D. We observe that a first difference in
terms of convergence exists between quantization-based compression and
projection-based: for the former, only Theorem 1 can be applied and the lower-
order terms always have a poorer dependency on $\mu$ while for the latter,
Theorem 2 is applicable and lower-order terms do not necessarily depends on
$\mu$. Indeed, the constants $\Sha_{H}$ do not depend on $\mu$ for
$\mathcal{C}_{\mathrm{PP}}$, and for
$\mathcal{C}_{\mathrm{rd}1},\mathcal{C}_{\mathrm{s}}$, when the features’
covariance $H$ is diagonal. On the contrary, there is always a dependency on
$\mu$ for $\mathcal{C}_{\Phi}$, and for
$\mathcal{C}_{\mathrm{rd}1},\mathcal{C}_{\mathrm{s}}$ when $H$ is not
diagonal. In practice, this means that, among projection-based compressors,
regarding lower-order terms, the convergence is expected to be slower for
random Gaussian projection.

We now turn to the analysis of the impact of the choice of the compression on
the dominant asymptotic term
$\mathrm{Tr}\left(H_{F}^{-1}\mathfrak{C}_{\mathrm{ania}}\right)$.

###  3.3 Impact of the compression on the additive noise covariance

In this section, we illustrate how distinct compressors lead to different
covariances for the additive noise. This shows how
$\mathrm{Tr}\left(H_{F}^{-1}\mathfrak{C}_{\mathrm{ania}}\right)$ is impacted
by the choice of a compressor.

First recall that for Algorithm 2 in the context of Model 2, with any
compressor $\mathcal{C}$, the additive noise writes for any $k\in[K]$, as:

$\xi_{k}^{\mathrm{add}}\overset{\text{def.}\leavevmode\nobreak\
\ref{def:add_mult_noise}}{=}\xi_{k}(0)\overset{\text{algo}\leavevmode\nobreak\
\ref{ex:cent_comp_LMS}}{=}\nabla
F(w_{*})-\mathcal{C}_{k}(\textsl{g}_{k}(w_{*}))\overset{\text{eq.}\leavevmode\nobreak\
\ref{eq:def_oracle}}{=}-\mathcal{C}_{k}((\left\langle
x_{k},w_{*}\right\rangle-y_{k})x_{k})\overset{\text{model}\leavevmode\nobreak\
\ref{model:centralized}}{=}\mathcal{C}_{k}(\varepsilon_{k}x_{k})\,.$

Also recall that $\mathfrak{C}_{\mathrm{ania}}$ is defined as
$\mathfrak{C}_{\mathrm{ania}}:=\mathbb{E}[(\xi_{k}^{\mathrm{add}})^{\otimes
2}]=\mathbb{E}[\mathcal{C}(\varepsilon_{k}x_{k})^{\otimes 2}]$. Moreover, note
that
$\mathcal{C}(\varepsilon_{k}x_{k})\overset{\text{a.s.}}{=}\varepsilon_{k}\mathcal{C}(x_{k})$
for all operators under consideration (this is immediate for linear operators
and results from the scaling for quantization-based ones). Consequently

$\mathfrak{C}_{\mathrm{ania}}=\mathbb{E}[\varepsilon_{k}^{2}\mathcal{C}(x_{k})^{\otimes
2}]=\sigma^{2}\mathbb{E}[\mathcal{C}(x_{k})^{\otimes 2}],$ (3)

as $\mathbb{E}[\varepsilon_{k}^{2}|x_{k}]=\sigma^{2}$. Ultimately, we have to
study the covariance of $\mathcal{C}(x_{k})$, for $x_{k}$ a random variable
with second-moment $H$.

We thus generically study the covariance of $\mathcal{C}(E)$, for $E$ a random
vector with distribution $p_{M}$ with second moment444Remark that we do not
assume $\mathbb{E}[E]=0$. Indeed, all computations only depend on the second-
order moment $M$ of $E$, not on its variance (and the convergence depends of
the second-order moment $H$ of $x$, not its variance). It is clear, that
$\mathbb{E}[\mathcal{C}(E)^{{\otimes 2}}]$ does not depend on the fact that
$E$ is centered: indeed, for $R$ a Rademacher $1/2$ independent of $E$, we
have $\mathbb{E}[\mathcal{C}(E)^{{\otimes
2}}]=\mathbb{E}[R^{2}]\mathbb{E}[\mathcal{C}(E)^{{\otimes
2}}]\overset{\perp}{=}\mathbb{E}[(R\mathcal{C}(E))^{{\otimes
2}}]=\mathbb{E}[\mathcal{C}(RE)^{{\otimes 2}}]$ and $RE$ is (1) centered (2)
has the same second-moment as $E$. Remark that centering the covariates before
learning does impact $H$: indeed $H=\mathbb{E}[(x)^{{\otimes
2}}]=\mathbb{E}[(x-\mathbb{E}[X])^{{\otimes 2}}]+(\mathbb{E}[X])^{\otimes
2}$). Centering subtracts $(\mathbb{E}[X])^{\otimes 2}$ to the second moment,
which is a rank-1 matrix, typically does not affect the smallest eigenvalue,
but it can affect the top-eigenvalue. $\mathbb{E}[E^{\otimes 2}]=M$.

######  Definition 5 (Compressor’ covariance on $p_{M}$).

We define the following operator $\mathfrak{C}$ which returns _the covariance
of a random mechanism $\mathcal{C}$_ acting on a distribution
$p_{M}\in\mathcal{P}_{M}$,

$\mathfrak{C}:\begin{array}[]{lcl}\mathbb{C}\times\mathcal{P}_{M}&\to&\mathbb{R}^{d\times
d}\\\ (\mathcal{C},\ \ p_{M})&\xmapsto{}&\mathbb{E}[\mathcal{C}(E)^{{\otimes
2}}]\,,\end{array}$

where $E\sim p_{M}$ and the expectation is over the joint randomness of
$\mathcal{C}$ and $E$, which are considered independent, that is
$\mathbb{E}[\mathcal{C}(E)^{{\otimes
2}}]=\int_{\mathbb{R}^{d}}\mathbb{E}[\mathcal{C}(e)^{{\otimes
2}}]\mathrm{d}p_{M}(e)$.

Figure 2: Illustration of Remark 9

Using a compressor $\mathcal{C}\in\mathbb{C}$, we therefore have by Equation
3:

$\mathfrak{C}_{\mathrm{ania}}=\sigma^{2}\mathfrak{C}(\mathcal{C},p_{H}),$ (4)

where $p_{H}$ is the marginal distribution of $x_{k}$ (for any $k$).

######  Remark 9 (Dependence on $p_{M}$, not only $M$).

Note that, for $\mathcal{C}=\mathcal{C}_{\mathrm{q}}$, there exist two
distributions $p_{M},p^{\prime}_{M}$ with the same covariance $M$, such that
$\mathfrak{C}(\mathcal{C},p_{M})\neq\mathfrak{C}(\mathcal{C},p^{\prime}_{M})$.
This is why we cannot simply denote $\mathfrak{C}(\mathcal{C},M)$.

Indeed, consider $d=2$ and (1) a normal distribution
${\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{1}}\sim\mathcal{N}(0,I_{2}/2)$,
vs (2) a _diamond_ distribution
${\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{2}}\sim\mathbb{P}_{\diamond}$,
such that
$\mathbb{P}_{\diamond}\\{(1,0)\\}=\mathbb{P}_{\diamond}\\{(-1,0)\\}=\mathbb{P}_{\diamond}\\{(0,1)\\}=\mathbb{P}_{\diamond}\\{(0,-1)\\}$
$=1/4\,,$ and thus
$\mathrm{Cov}\left[{\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{1}}\right]=\mathrm{Cov}\left[{\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{2}}\right]=I_{2}/2$.
Then
$\mathrm{Cov}\left[{\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{1}}\right]\prec\mathrm{Cov}\left[{\color[rgb]{1,0.49609375,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49609375,0.0546875}\mathcal{C}_{\mathrm{q}}(E_{1})}\right]$,
but
${\color[rgb]{1,0.49609375,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49609375,0.0546875}\mathcal{C}_{\mathrm{q}}(E_{2})}\overset{\mathrm{a.s.}}{=}{\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{2}}$
thus
$\mathrm{Cov}\left[{\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{2}}\right]=\mathrm{Cov}\left[{\color[rgb]{1,0.49609375,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49609375,0.0546875}\mathcal{C}_{\mathrm{q}}(E_{2})}\right]$.
We illustrate this on Figure 2: we represent
${\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}E_{i}}$
in blue and
${\color[rgb]{1,0.49609375,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49609375,0.0546875}\mathcal{C}_{\mathrm{q}}(E_{i})}$
in orange for $i=1$ (left) and $i=2$ (right). We also represent the covariance
matrices by plotting the ellipses
${\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}\mathcal{E}_{\mathrm{Cov}\left[E_{i}\right]}}$
and
${\color[rgb]{1,0.49609375,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49609375,0.0546875}\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}_{\mathrm{q}}(E_{i})\right]}}$,
where $\mathcal{E}_{M}=\\{x\in\mathbb{R}^{d},x^{\top}M^{-1}x=4\\}$ (see
Definition S1)555The constant 4 is chosen so that for Gaussian distributions,
the expected fraction of points within the ellipse is $86,4\%\simeq
1-F_{\chi^{2}(2)}(4)$ .

We now compute for the compression operators, the value or an upper bound on
$\mathfrak{C}(\mathcal{C},p_{{H}})$.

######  Proposition 2 (Compression and covariance).

The following formulas hold:

$\begin{array}[]{ll}\mathfrak{C}(\mathcal{C}_{\mathrm{I}_{d}},p_{{M}})&=M\\\
\mathfrak{C}(\mathcal{C}_{q},p_{{M}})&\preccurlyeq\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M):=M+\sqrt{\mathrm{Tr}\left(M\right)}\sqrt{\mathrm{Diag}\left(M\right)}-\mathrm{Diag}\left(M\right)\\\
&\text{(with equality if $\|E\|$ is a.s. constant under $p_{M}$)}\\\
\mathfrak{C}(\mathcal{C}_{s},p_{{M}})&=M+{(1-p)}{p^{-1}}\mathrm{Diag}\left(M\right)\\\
\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})&=p^{-1}\left((\frac{h+1}{d+2}+\delta_{hd})M+\left(1-\frac{h-1}{d-1}\right)\frac{\mathrm{Tr}\left(M\right)}{d+2}\mathrm{I}_{d}\right),\leavevmode\nobreak\
\text{with }\delta_{hd}=\frac{h-1}{(d-1)(d+2)}=O(\frac{1}{d})\\\
\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})&=p^{-1}\left(\frac{h-1}{d-1}M+\left(1-\frac{h-1}{d-1}\right)\mathrm{Diag}\left(M\right)\right)\\\
\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})&=p^{-1}M\,.\end{array}$

Conclusion and interpretation. Most compression operators induce both a
structured noise (Flammarion and Bach, 2015) which covariance scales with $H$
and an unstructured noise, which covariance scales with
$\mathrm{Diag}\left(H\right)$ or $\mathrm{I}_{d}$ – thus corresponding to an
isotropic noise.

From the convergence standpoint, the asymptotic convergence rate scales with
$\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H^{-1}\right)=\sigma^{2}\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C},p_{{H}})H^{-1}\right)$.
Therefore, the un-structured part in the noise is problematic as
$\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H^{-1})\right)$ will strongly
depends on the smallest eigenvalue $\mu$. This comes from the fact that the
compression induces a significant noise in directions in which the Hessian
curvature is very limited (thus directions onto which the contraction towards
the optimum in the algorithm is weak).

A particular case is when $H$ is diagonal (e.g. the features are centered and
independent), we get the following corollary.

######  Corollary 3 (Compression and covariance, diagonal case).

If $M$ is diagonal, then Proposition 2 is simplified to the following (with
the same $\delta_{hd}$):

$\begin{array}[]{llll}\mathfrak{C}(\mathcal{C}_{\mathrm{I}_{d}},p_{{M}})&=M&\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})&=p^{-1}\left((\frac{h+1}{d+2}+\delta_{hd})M+(1-\frac{h-1}{d-1})\frac{\mathrm{Tr}\left(M\right)}{d+2}\mathrm{I}_{d}\right)\\\
\mathfrak{C}(\mathcal{C}_{q},p_{{M}})&\preccurlyeq\sqrt{\mathrm{Tr}\left(M\right)}\sqrt{M}&\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{H}})&=p^{-1}M\\\
\mathfrak{C}(\mathcal{C}_{s},p_{{M}})&=p^{-1}M&\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})&=p^{-1}M.\\\
\end{array}$

######  Remark 10 (Composition of compressors).

For all compression schemes but $\mathcal{C}_{\mathrm{q}}$, we observe that
$\mathfrak{C}(\mathcal{C},p_{{M}})$ is a function of $M$, which complements
Remark 9. In that particular case, we can then denote $\mathfrak{C}(C,M)$.
This means that the lemma can be extended to any composition of compression
schemes, for example to compute $\mathfrak{C}({C_{1}\circ
C_{2},M})=\mathfrak{C}({C_{1},\mathfrak{C}(C_{2},M)}).$

From Proposition 2 and Corollary 3 we can deduce certain generic comparisons
between the asymptotic convergence rates, depending on the compression
operator (for compression operators having the same variance bound). They are
proven in Subsection E.3. In the following, for any $a,b\in\mathbb{R}$, we use
the notation $a\mathrel{\mathop{\leq}\limits^{\vbox
to-0.60275pt{\kern-2.0pt\hbox{$\scriptstyle\sim$}\vss}}}b$, to denote a
systematic inequality (i.e., $a\leq b$) with a negligible difference as
$d\to\infty$ (i.e., $a=b+O(1/d)$), and similarly for any two symmetric
matrices $A,B\in\mathcal{S}_{d}(\mathbb{R})$,
$A\mathrel{\mathop{\preccurlyeq}\limits^{\vbox
to-0.90417pt{\kern-2.0pt\hbox{$\scriptstyle\sim$}\vss}}}B$, for $A\preccurlyeq
B$ and $A=B+O(1/d)$ as $d\to\infty$.

######  Proposition 3 (Comparison between
${\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\Phi}}$,
$\omega=d/h-1$).

We consider
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{s}}$,
$\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\Phi}\\}$ with $p=h/d$, such that
$\mathcal{C}$ always satisfies Lemma 1 with $\omega=d/h-1$. For any matrix
$M\leavevmode\nobreak\ \in\leavevmode\nobreak\ \mathbb{R}^{d\times d}$:

  1. 1.

If $M$ is diagonal, then:

     * •

$\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})=\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})=\frac{d}{h}M$,

     * •

$\mathrm{Tr}\big{(}\mathfrak{C}(\mathcal{C}_{\mathrm{PP}/\mathrm{s}/\mathrm{rd}h},p_{{M}})M^{-1}\big{)}\leq\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})M^{-1}\right)$.

This means that the asymptotic convergence rate does not depend on the choice
of the compressor between
$\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\mathrm{rd}1}$
in the diagonal case.

  2. 2.

Moreover, for any matrix $M$ with a _constant diagonal_ (e.g., we
standardize666That means we center and rescale to get a variance of one for
each feature. the data in the pre-processing step, such that
$\mathrm{Diag}\left(M\right)=\mathrm{I}_{d}$), we have:

$\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1})\leq\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})M^{-1})\leq\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{s},p_{{M}})M^{-1})\leq\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})M^{-1})\,.$

With strict inequalities if $M$ is not proportional to $\mathrm{I}_{d}$. This
means that we expect the asymptotic convergence rate to be faster for PP than
Sparsification, Sketching, or Rand-$h$ (illustrated in experiments).

In the next proposition, we compare compressors
$\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\mathrm{PP}}$ to
$\mathcal{C}_{\mathrm{q}}$ for equal $\omega=\sqrt{d}$ (we exclude
$\mathcal{C}_{\mathrm{rd}h}$ and $\mathcal{C}_{\Phi}$ for which $h$ must be an
integer and that are shown to be worse than $\mathcal{C}_{\mathrm{s}}$ in
Proposition 3).

######  Proposition 4 (Comparison between
${\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{s}}}$,
$\omega=\sqrt{d}$ ).

We consider
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{s}}\\}$
with $p=(\sqrt{d}+1)^{-1}$, such that $\mathcal{C}$ always satisfies Lemma 1
with $\omega=\sqrt{d}$.

  1. 1.

For any symmetric matrix $M$ diagonal, we have:

$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)=\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{s},p_{{M}})M^{-1}\right)\overset{\text{possib.
}\ll}{\leq}\left(1+\frac{1}{\sqrt{d}}\right)\mathrm{Tr}\left(\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)M^{-1}\right)\,.$

  2. 2.

If $M$ is not necessarily diagonal but with a _constant diagonal_ (e.g., after
standardization), then

     * •

$\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)\preccurlyeq\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})$

     * •

$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)\leq\left(1+\frac{1}{\sqrt{d}}\right)\mathrm{Tr}\left(\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)M^{-1}\right)$

This means that sparsification is expected to always result in a poorer
asymptotic convergence rate than quantization. Moreover, the upper bound on
the covariance $\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)$ for
quantization itself leads to a worst bound than for PP.777Note that the
behavior for quantization, apart from the upper bound
$\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)$ is not quantified, it
is thus possible that quantization performs even better than PP.

We now propose a detailed illustration of the results of Proposition 2 and
Corollary 3, first in a low-dimensional setting ($d=2$) and then in higher
dimension on synthetic and real datasets.

####  3.3.1 Illustration of Proposition 2 and Corollary 3 in dimension 2.

In order to build intuition, we illustrate Proposition 2 and Corollary 3 in
Figures 3 and 4, showing how compression affects the additive noise
covariance, in a simple 2-dimensional case, for both a non-diagonal matrix $M$
(Figure 3) and a diagonal one (Figure 4).

Figure 3: $H$ not diagonal. Scatter plot of $(x_{k})_{i=1}^{K}$/
$(\mathcal{C}(x_{k}))_{i=1}^{K}$ with its ellipse
$\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}$/$\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}$.
Figure 4: $H$ diagonal. Scatter plot of
$(x_{k})_{i=1}^{K}$/$(\mathcal{C}(x_{k}))_{i=1}^{K}$ with its ellipse
$\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}$/$\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}$.

More specifically, we consider features $(x_{k})_{k\in[K]}$ sampled from
$\mathcal{N}(0,M)$ where $M=QDQ$, $D=\mathrm{Diag}\left(1,10\right)$ and $Q$
is rotation matrix with angle $\pi/8$ (resp. $0$) in Figure 3 (resp. 4). We
represent the values of $x_{k}$ and $\mathcal{C}(x_{k})$, unit-ellipses of the
corresponding covariance matrices
$\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}$ and
$\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}$ (see Definition S1
– recall that
${\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}}\subset{\color[rgb]{1,0.49609375,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49609375,0.0546875}\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}}\Leftrightarrow{\color[rgb]{0.12109375,0.46484375,0.70703125}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.46484375,0.70703125}{\mathrm{Cov}\left[x_{k}\right]}}\preccurlyeq{\color[rgb]{1,0.49609375,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49609375,0.0546875}{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}}$),
as well as their two eigenvectors; we take $p=(1+\sqrt{d})^{-1}=0.41$, hence
for
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\mathrm{PP}}\\}$
we have $\omega=1.41$ but for sketching and rand-$1$, we have $p=1/2$ and
$\omega=(1-p)/p=1$.

We make the following observations:

  * [Qtz]

For quantization and stabilized quantization, in the non-diagonal case, the
eigenvectors of $\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}$ and
$\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}$ are slightly888On
the figure, there are nearly aligned, but actually differ. different (as
$\sqrt{\mathrm{Diag}\left(M\right)}$ and $M$ are not jointly diagonalizable,
as well as if $\mathrm{Diag}\left(M\right)$ is constant, although this case is
not presented here, but in Figure S5 in Subsection E.3). They are equal for
the diagonal case (as $\sqrt{\mathrm{Diag}\left(M\right)}$ and $M$ are both
diagonal so the eigenvectors are aligned with the axis). In both cases, the
eigenvalue decay is reduced (from $\lambda_{2}/\lambda_{1}=1/10$ without
compression to $1/\sqrt{10}$ with compression, which visually corresponds to a
“wider” ellipse).

This slower eigenvalue decay results from the unstructured-noise, i.e., large
noise on the weak-curvature direction, which is particularly visible on Figure
4. This is critical as it results in a potentially much larger limit rate, as
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{q},p_{{M}})M^{-1}\right)\simeq\mathrm{Tr}\left(M^{-1/2}\right)$.

  * [Skt]

For sketching, the eigenvectors remain the same for
$\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}$ and
$\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}$ (as
$\mathrm{I}_{2}$ and $M$ are jointly diagonalizable, see Corollary 3), both in
the diagonal and non-diagonal case. However, the isotropic noise with
covariance $\mathrm{I}_{2}$ is visible (wide ellipse), also drastically
impacting
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)\varpropto\mathrm{Tr}\left(M^{-1}\right)$.

  * [Sp]

For $p$-sparsification, eigenvectors are not aligned with the ones of $M$ in
the non-diagonal case, but are in the diagonal case. In this latter case, the
covariance $\mathfrak{C}(\mathcal{C}_{s},p_{{M}})$ is proportional to $M$.

  * [Rd]

Same remarks hold for Rand-$1$ than for sparsification. We see that
$\mathfrak{C}(\mathcal{C}_{\mathrm{rd}1},p_{{M}})$ is diagonal, as expected.
Again, both operators induce an unstructured-noise in the non-diagonal case.

  * [PP]

For PP, the covariances are always proportional (with factor $p^{-1}$), i.e.,
the ellipses have the same axis and
$\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}$ is a scaled
version of $\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}$.

We highlight the following points regarding pairwise comparisons:

  * •

In the diagonal case, as stated by Item 1 in Proposition 3,
${\mathrm{Cov}\left[\mathcal{C}_{\mathrm{s}}(x_{k})\right]}$ and
${\mathrm{Cov}\left[\mathcal{C}_{\mathrm{PP}}(x_{k})\right]}$ are identical.
${\mathrm{Cov}\left[\mathcal{C}_{\mathrm{rd}1}(x_{k})\right]}$ would have been
identical too if $p=1/d$ (but here we observe
$\mathfrak{C}(\mathcal{C}_{\mathrm{rd}1},p_{{M}})\preccurlyeq\mathfrak{C}(\mathcal{C}_{s/\mathrm{PP}},p_{{M}})$
because the variance of rand-$1$ is smaller that for sparsification/PP).

  * •

In the non-diagonal case, from Item 2 in Proposition 3, we have
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)\leq\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{s},p_{{M}})M^{-1}\right)$,
however we do not have
$\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})\preccurlyeq\mathfrak{C}(\mathcal{C}_{s},p_{{M}})$,
hence we can not conclude anything on
${\mathrm{Cov}\left[\mathcal{C}_{\mathrm{PP}}(x_{k})\right]}$ and
${\mathrm{Cov}\left[\mathcal{C}_{\mathrm{s}}(x_{k})\right]}$.

  * •

In the non-diagonal scenario, we observe on Figure 3, that
$\mathfrak{C}(\mathcal{C}_{q},p_{{M}})\preccurlyeq\mathfrak{C}(\mathcal{C}_{s},p_{{M}})$
(as in Item 2 in Proposition 4).

####  3.3.2 Illustration of Proposition 2 and Corollary 3 in dimension $d>2$

(a) $M$ diagonal, $d=100$

(b) $M$ non-diagonal, $d=100$

(c) $\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}M^{-1}\right)$,
$d\in\llbracket 2,100\rrbracket$

Figure 5: Figures 5(a) & 5(b): Eigenvalues of
$\mathfrak{C}(\mathcal{C},p_{{M}})$. Figure 5(c):
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C},p_{{M}})M^{-1}\right)$.
$K\leavevmode\nobreak\ =\leavevmode\nobreak\ 10^{4},\omega=10$,
$M=Q\mathrm{Diag}\left((1/i^{4})_{i=1}^{d}\right)Q^{T}$ and $Q=\mathrm{I}_{d}$
(on 5(a) & 5(c)-l) or $Q\sim\mathrm{Unif}(\mathcal{O}_{d})$ (on 5(b) &
5(c)-r). Plain lines: empirical values; dashed lines: theoretical formula or
upper bound given by Proposition 2.

Another way of visualizing the structured and isotropic parts of the noise is
by plotting the eigenvalues of $\mathfrak{C}(\mathcal{C},p_{{M}})$ in
dimension $d=100$. This is done in Figure 5, in which we plot the eigenvalues
in decreasing order for both $M$ and $\mathfrak{C}(\mathcal{C},p_{{M}})$, with
Gaussian $p_{M}=\mathcal{N}(0,M)$ and
$\mathrm{Sp}(M)=\\{(1/i^{4})_{i=1}^{d}\\}$. We see that in the diagonal case,
in Figure 5(a), all operators but
$\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\Phi}$ have a covariance proportional
to $M$ (thus a slope $-4$ on a log/log scale), while
$\mathcal{C}_{\mathrm{q}}$ is proportional to $\sqrt{M}$ (thus a slope $-2$)
and $\mathcal{C}_{\Phi}$ has an isotropic component (thus eigenvalues not
decreasing to 0). In Figure 5(b) we see that only $\mathcal{C}_{\mathrm{PP}}$
has a covariance proportional to $M$ while all other ones have an isotropic
component (thus eigenvalues not decreasing to 0). We plot both empirical
values and the ones obtained in Proposition 2, which shows that the upper
bound on quantization is reasonable in practice and acts as a safety check for
other compression schemes.

We plot on Figure 5(c) the theoretical and empirical
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C},p_{{M}})M^{-1}\right)$ again in two
cases, diagonal and non-diagonal. In the diagonal case, PP, sparsification,
and rand-$h$ have the same behavior; their traces have the smallest value
among all compressors. However, in the general case of non-diagonal features’
covariance, all compression operators have similar slow performance except for
PP. For $d=100$, all the compressors _have $\omega=10$, but
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C},p_{{M}})M^{-1}\right)$ varies by
several orders depending on the compressor_, illustrating again that
compressors satisfying Lemma 1 with the same $\omega$ may have vastly
different behaviors.

(a) quantum (tabular dataset)

(b) cifar10 (images)

Figure 6: $\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C},p_{{M}})M^{-1}\right)$
w.r.t the level of $\omega$ for quantum and cifar10. X/Y-axis are in log
scale. Note that the plots may have different magnitudes.

Lastly, we perform the same experiments on
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C},p_{{M}})M^{-1}\right)$, but on non-
simulated datasets, namely quantum (Caruana et al., 2004) and cifar-10
(Krizhevsky et al., 2009): in Figure 6 we plot
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C},p_{{M}})M^{-1}\right)$ w.r.t. the
worst-case-variance-level $\omega$ of the compression in three scenarios:
(top-row) – with data standardization, thus $\mathrm{Diag}\left(M\right)$ is
constant equal to $1$; (middle-row) – with a PCA, thus with a diagonal
covariance $M$ (note that this is for illustration purpose: performing a PCA
would be more expensive computationally than running Algorithm 2); and
(bottom-row) – without any data transformation. As a pre-processing, we have
resized images of the cifar-10 dataset to a $16\times 16$ dimension. We adjust
the level $s\in\mathcal{C}_{\mathrm{q}}$,
$h\in\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\Phi}$, and
$p\in\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{s}}$ to make $\omega$
vary.

Interpretation. (Top-row): with standardization, the order predicted from
Proposition 3.2 (large $\omega$), and Proposition 4.2 (low $\omega$) is
obtained for both quantum and cifar-10:
$\mathcal{C}_{\mathrm{PP}}\leq\mathcal{C}_{\mathrm{q}}\leq\mathcal{C}_{\mathrm{s}}\simeq\mathcal{C}_{\mathrm{rd}h}\simeq\mathcal{C}_{\Phi}$.
For quantization, we observe two regimes: 1) when $\omega$ tends to zero,
quantization and PP outperform sketching, sparsification, and rand-$h$, that
are equivalent. 2) when $\omega$ increases, quantization changes from scaling
as PP to scaling as the second group. (Middle-row): in the diagonal regime,
comments made for Figure 5(c)-l are still valid. (Bottom-row): We observe that
for a generic matrix $M$ (obtained from raw-data) there is no systematic order
between compression schemes. This is un-avoidable as the order for a “$M$
diagonal” and “$M$ with constant-diagonal” is not the same. We observe that:

  * •

for quantum,
$\mathcal{C}_{\mathrm{PP}}\leq\mathcal{C}_{\mathrm{s}}\mathrel{\mathop{\leq}\limits^{\vbox
to-0.60275pt{\kern-2.0pt\hbox{$\scriptstyle\sim$}\vss}}}\mathcal{C}_{\mathrm{rd}h}\ll\mathcal{C}_{\mathrm{q}}\ll\mathcal{C}_{\Phi}$

  * •

for cifar-10,
$\mathcal{C}_{\mathrm{PP}}\ll\mathcal{C}_{\mathrm{q}}\ll\mathcal{C}_{\mathrm{s}}\simeq\mathcal{C}_{\mathrm{rd}h}\simeq\mathcal{C}_{\Phi}$.

We also observe that $\mathcal{C}_{\Phi}$, which is the only operator to
always induce an isotropic component, may be much worse than all other
compressors (e.g., on quantum). Ultimately, the order depends on the
covariance matrix $M$. Here we observe that the raw-data behavior is close for
cifar-10 to the standardized version, while for quantum the order between
compressors is the same for raw-data and diagonal (although the ratios are
different). In Subsection E.4 (Table S3), we provide an illustration of the
covariance matrices, that supports such interpretation.

###  3.4 Numerical experiments on Algorithm 2

In this section, we run Algorithm 2 on both synthetic and real datasets to
illustrate the combined theoretical results of Sections 2 and 3. In Figure 7,
we compare the compression operators to the baseline of no-compression. We
plot the excess loss of the Polyak-Ruppert iterate $F(\overline{w}_{k})-F(w)$,
versus the index in log/log scale. Each experiment is conducted 5 times, with
a new dataset generated from a new seed. The standard deviation of
$\log_{10}(F(\overline{w}_{k})-F(w))$ is indicated by the shadow-area.

Setting: (a) Synthetic dataset generation: The dataset is generated using
Model 2 with $K=10^{7}$, $\sigma^{2}=1$, an optimal point $w_{*}$ set as a
constant vector of ones and a geometric eigenvalues decay of
$D_{1}=\mathrm{Diag}\left((1/i^{4})_{i=1}^{d}\right)$ (resp.
$D_{2}=\mathrm{Diag}\left((1/i)_{i=1}^{d}\right)$). For $i\in\\{1,2\\}$, the
covariance matrix is $H_{\\{i\\}}=QD_{\\{i\\}}Q^{T}$, where $Q$ is either
orthogonal matrix, or $Q=\mathrm{I}_{d}$ in the case of a diagonal features’
matrix. (b) Real datasets processing: We resize images of the cifar-10 dataset
to a $16\times 16$ dimension, and then for both datasets, we apply
standardization. To compute the optimal point (and so to compute the excess
loss), we run SGD over $200$ passes on the whole dataset and consider the last
Polyak-Ruppert average as the optimal point $w_{*}$. (c) Algorithm 2: We take
a constant step-size $\gamma=1/(2(\omega+1)R^{2})$ with $R^{2}$ the trace of
the features’ covariance, and $w_{0}=0$ as initial point. We set the batch-
size $b=1$ (resp. $b=16)$ and the compressor variance $\omega=10$ (resp.
$\omega=1$, thus a factor 4 compression for quantum and factor 2 for cifar-10)
for synthetic datasets (resp. for real datasets). For cifar-10 and quantum, we
run Algorithm 2 for $5\times 10^{6}$ iterations (it corresponds to $100$
passes on the whole dataset). These settings are summarized in Tables S1 and
S2 in Subsection A.1. Additionally, to illustrate Corollary 1, we plot on
Figure 7(d) the final excess loss after running Algorithm 2 with an horizon-
dependent step-size $\gamma=K^{-2/5}$, computed for seven values of
$K\in\\{10^{i},i\in\llbracket 1,7\rrbracket\\}$.

Interpretation – $H$ diagonal (Figure 7(a)). For sparsification, rand-$h$, and
PP (linear compressors), the rate of convergence is given by Theorem 2. As
stated by Corollary 3, the covariance $\mathfrak{C}_{\mathrm{ania}}$ is
proportional to $H$ leading to a $O(1/K)$ rate. We indeed observe in Figure
7(a) that excess loss is linear in a log/log scale.

For non-linear compression operators, the rate is given by Theorem 1. On the
one hand, $1$-quantization results in a slower eigenvalues’ decay, leading to
a larger $\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H^{-1}\right)$, thus a
slower convergence than linear compressors. On the other hand, for sketching,
covariance has a purely isotropic part scaling with $\mathrm{I}_{d}$, which
causes $\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H^{-1}\right)$ to
strongly depend on the strong-convexity coefficient $\mu$ resulting in an
extremely large constant. Both behaviors are observed in Figure 7(a).

Interpretation – $H$ not diagonal (Figures 7(b) and 7(e)). In the case of the
high eigenvalues’ decay of $H_{1}$ ($\mu=10^{-8}$), the only compressor that
shows in Figure 7(b) a linear rate of convergence in the log/log scale is PP.
All others exhibit a saturation phenomenon after a certain number of
iterations. This is again due to the unstructured part of the noise for all
other compressors, as given by Proposition 2. Besides, we also note an
increase of the excess loss after some iterations that is likely caused by the
accumulation of noise on axis onto which the curvature of $H$ is weak (but the
isotropic noise is not). However, taking the optimal horizon-dependent step-
size given by Corollary 1, we recover on Figure 7(d) for all compressor
$\mathcal{C}$ the sub-linear convergence rate of PP shown at Figure 7(b),
reducing by a factor $100$ the excess loss w.r.t. to the scenario where
$\gamma=1/2(\omega+1)R^{2})$. While using a small step-size is slightly worse
for SGD, it reduces the second and third term of the variance in Theorem 1
that depends on $\mu$ for other compressors. And in the scenario of a slow
eigenvalues’ decay ($\mu=10^{-2}$), we observe on Figure 7(e) that all
compressors reach the sub-linear rate (same slope -1 on the log/log plot), but
with different constants. This illustrates Theorems 2 and 1 in the case of
moderate coefficient $\mu$ where we expect the second and third parts of the
variance term to be negligible.

Synthetic dataset | Real datasets
---|---
|  |
|  |

(a) $H_{1}$ diagonal.

(b) $H_{1}$ not diagonal.

(c) quantum

(d) $H_{1}$ not diagonal, $\gamma=K^{-2/5}$.

(e) $H_{2}$ not diagonal.

(f) cifar10

Figure 7: Logarithm excess loss of the Polyak-Ruppert iterate for a single
client ($N=1$).

Interpretation - real datasets (Figures 7(c) and 7(f)). We observe that
quantization performs competitively with PP and outperforms all other
compressors. The asymptotic behavior is consistent with Figure 6 (top-row) for
$\omega=1$, where the order
$\mathcal{C}_{\mathrm{PP}}\simeq\mathcal{C}_{\mathrm{q}}\ll\mathcal{C}_{\mathrm{s}}\simeq\mathcal{C}_{\mathrm{rd}h}\simeq\mathcal{C}_{\Phi}$
is observed. This experience is going beyond Proposition 2 which only applies
to $1$-quantization.

###  3.5 Conclusion

In this section, we investigated how the compression scheme choice impacts the
convergence rate, first by showing that quantization-based and projection-
based methods respectively satisfy Theorem 1 and Theorem 2, resulting in
different non-asymptotic behaviors. In the asymptotic regime, in both cases,
the averaged excess loss scales as
$\mathrm{Tr}\left(H^{-1}\mathfrak{C}_{\mathrm{ania}}\right)/K$. We then
analyzed the impact of the most-used schemes on this limit rate. Overall, it
appears that all compression schemes typically generate an unstructured-noise,
which covariance does not scale with $H$, contrarily to the classical un-
compressed Algorithm 1. The one exception is PP, which corresponds (on a
single worker) to performing fewer iterations. For other compression schemes,
we show the impact of the covariance $H$: depending on the correlation between
features ($H$ diagonal or not) and on the pre-processing (e.g.,
standardization for which $H$ has diagonal constant), the ordering between
compression scheme varies. In many cases, this highlights the need for an
additional regularisation when running Algorithm 2: all compression schemes
(but PP) result in a significant noise that accumulates along the low
curvature directions. Our results can be extended to the ridge (a.k.a.,
Tikhonov) regularized case (see Dieuleveut et al., 2017), which creates an
additional bias but changes the rate
$\mathrm{Tr}\left(H^{-1}\mathfrak{C}_{\mathrm{ania}}\right)/K$ into
$\mathrm{Tr}\left((H+\lambda\mathrm{I})^{-1}\mathfrak{C}_{\mathrm{ania}}\right)/K$.
The theoretical optimal choice for $\lambda$ depending on $H$ and the
compression scheme could be obtained from our analysis but is left as future
work.

We now turn to the distributed/federated case, which motivates the study of
compression schemes for practical applications.

##  4 Application to Federated Learning

In this section, we consider Algorithm 3 under Model 1, which corresponds to
heterogeneous Federated Learning on a network composed of $N$ clients. We
hereafter consider two particular cases of Model 1. First, in Subsection 4.1,
the covariate-shift case, i.e., Model 1 with $w_{*}^{i}=w_{*}$ for all $i$
(thus the distribution of $y^{i}$ conditional to $x^{i}$ does not change
between workers), but on the other hand, the features’ marginal distributions
are different, in particular, $H_{i}\neq H_{j}$. Second, in Subsection 4.2,
the optimal-point-shift case, i.e., for each client $i,j\in[N]$, their optimal
points are different $w_{*}^{i}\neq w_{*}^{j}$, but $H_{i}=H_{j}$. In the rest
of the section, we denote $\overline{H}:=\frac{1}{N}\sum_{i=1}^{N}H_{i}$,
$\overline{R}^{2}:=\frac{1}{N}\sum_{i=1}^{N}R^{2}_{i}$, and we have
$F(w_{k})-F(w_{*})=\frac{1}{2}\left\langle\eta_{k-1},\overline{H}\eta_{k-1}\right\rangle$.

###  4.1 Heterogeneous covariance

In this section, we first show that Theorems 2 and 1 on (LSA) from Section 2
can be applied to the Federated Learning case within the scenario of
covariate-shift. Corollary 4 is proved in Subsection F.1.

######  Corollary 4 (Algorithm 3 with covariate-shift).

Consider Algorithm 3 under Model 1 with $w_{*}^{i}=w_{*}^{j}$ (and potentially
$H_{i}\neq H_{j}$).

  1. 1.

For a compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},$
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$, Theorem 1 holds, with
$H_{F}=\overline{H}$, $R_{F}^{2}=\overline{R}^{2}$,
$\mathcal{A}=(\omega+1)\overline{R}^{2}\sigma^{2}/N$,
$\mathcal{M}_{2}=(\omega+1)\max_{i\in[N]}(R_{i}^{2})/N$,
$\mathcal{M}_{1}=\Omega\sigma\max_{i\in[N]}(R_{i}^{2})/N$.

  2. 2.

Moreover for any linear compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},$
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$, Theorem 2 holds, with the
same constants and
$\Sha_{\mathrm{add}}=\sigma^{2}\max_{i\in[N]}(\Sha_{H_{i}})/N$ and
$\Sha_{\mathrm{mult}}=\max_{i\in[N]}(R_{i}^{2}\Sha_{H_{i}})/N$, with
$(\Sha_{H_{i}})_{i=1}^{N}$ given in Corollary 2.

The Hessian of the objective function is now $\overline{H}$, and Theorems 1
and 2 still hold. The proof consists in showing that with Lemma 1, Assumptions
2, 1, 3 and 4 on the resulting random field $(\xi_{k})_{k\in\mathbb{N}^{*}}$
are valid, with the constants given above.

In order to understand the impact of the compressor on the limit convergence
rate, we establish a formula for $\mathfrak{C}_{\mathrm{ania}}$ similar to
Equation 4. In the setting of covariate-shift, we have for any clients
$i,j\in[N]$, $w_{*}^{i}=w_{*}^{j}$, thus

$\displaystyle\xi_{k}^{\mathrm{add}}\overset{\text{def.}\leavevmode\nobreak\
\ref{def:add_mult_noise}}{=}\xi_{k}(0)$
$\displaystyle\overset{\text{algo}\leavevmode\nobreak\
\ref{ex:dist_comp_LMS}}{=}\nabla
F(w_{*})-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w_{*}))$
$\displaystyle\overset{\text{eq.}\leavevmode\nobreak\
\ref{eq:def_oracle}}{=}-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}((\left\langle
x_{k}^{i},w_{*}\right\rangle-
y_{k}^{i})x_{k}^{i})\overset{\text{model}\leavevmode\nobreak\
\ref{model:fed}}{\underset{\text{ with
}w_{*}^{i}=w_{*}^{j}}{=}}\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\varepsilon_{k}^{i}x_{k}^{i})\,.$

Next for all operators under consideration we have
$\mathcal{C}^{i}_{k}(\varepsilon_{k}^{i}x_{k}^{i})\overset{\text{a.s.}}{=}\varepsilon_{k}^{i}\mathcal{C}_{k}^{i}(x_{k}^{i})$,
thus, with $p_{H_{i}}$ denoting the distribution of $x_{k}^{i}$ with
covariance $H_{i}$, we have:

$\displaystyle\mathfrak{C}_{\mathrm{ania}}$
$\displaystyle=\mathbb{E}\left[(\xi_{k}^{\mathrm{add}})^{\otimes
2}\right]=\mathbb{E}\left[\left(\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\varepsilon_{k}^{i}x_{k}^{i})\right)^{{\otimes
2}}\right]\overset{\text{indep. of
}(\mathcal{C}_{k}^{i})_{i=1}^{d}}{=}\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}\left[\mathcal{C}_{k}^{i}(\varepsilon_{k}^{i}x_{k}^{i})^{{\otimes
2}}\right]$
$\displaystyle=\frac{\sigma^{2}}{N^{2}}\sum_{i=1}^{N}\mathbb{E}\left[\mathcal{C}_{k}^{i}(x_{k}^{i})^{{\otimes
2}}\right]\overset{\mathrm{Def.\leavevmode\nobreak\
\ref{def:cov_of_compression}}}{=}\frac{\sigma^{2}}{N^{2}}\sum_{i=1}^{N}\mathfrak{C}(\mathcal{C}_{k}^{i},p_{{H}_{i}})\overset{\text{notation}}{=:}\frac{\sigma^{2}}{N}\overline{\mathfrak{C}((\mathcal{C}^{i},p_{H_{i}})_{i=1}^{N})}\,.$
(5)

The operator $\overline{\mathfrak{C}((\mathcal{C}^{i},p_{H_{i}})_{i=1}^{N})}$
generalizes the notion of _compressor’s covariance_ (Definition 5) to the case
of multiple clients, and Equation 5 corresponds to Equation 4.

######  Remark 11 (All clients use the same linear compressor).

If for all $i\in[N]$, $\mathcal{C}^{i}\overset{(d)}{=}\mathcal{C}$ and
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\Phi}\\}$,
leveraging Remark 10, we have

$\overline{\mathfrak{C}((\mathcal{C}^{i},p_{H_{i}})_{i=1}^{N})}=\mathfrak{C}(\mathcal{C},{\overline{H}})\,.$

The analysis of (LSA) on a single worker made in Section 3 is still valid in
this setting with now the Hessian of the problem being equal to the average of
covariance $\overline{H}$. Corollary 4 and Equation 5 prove that the case of
covariate-shift is identical to the centralized setting with a variance
reduced by a factor $N$.

######  Remark 12 (Varying compressor, or compression level, or non-linear
compression).

In most other cases, the computation of
$\frac{\sigma^{2}}{N}\overline{\mathfrak{C}((\mathcal{C}^{i},p_{H_{i}})_{i=1}^{N})}=\frac{\sigma^{2}}{N^{2}}\sum_{i=1}^{N}\mathfrak{C}(\mathcal{C}_{i}^{i},p_{{H}_{i}})$
is possible using the results of Subsection 3.3

Overall, in the covariate-shift case, most insights from the centralized case
remain valid, especially, client sampling (i.e., PP) is the safest way to
limit the impact of compression. Moreover, the trade-offs and ordering between
compressors remain preserved, especially regimes in which quantization
outperforms other competitors.

###  4.2 Heterogeneous optimal point

Hereafter, we focus on the case of heterogeneous optimal points and consider
that all clients share the same covariance matrix, i.e. for any $i,j\in[N]$,
$H_{i}=H$, but potentially $w_{*}^{i}\neq w_{*}^{j}$. This can be seen as a
case of concept-shift (Kairouz et al., 2019), and we also refer to the
situation as optimal-point-shift. This setting could eventually be combined
with the covariate-shift case. Similarly, Theorems 2 and 1 on (LSA) from
Section 2 can be applied.

######  Corollary 5 (Algorithm 3 with concept-shift).

Consider Algorithm 3 under Model 1 with $H_{i}=H_{j}$ (and potentially
$w_{*}^{i}\neq w_{*}^{j}$).

  1. 1.

For a compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},$
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$, Theorem 1 holds, with
$H_{F}=H$, $R_{F}^{2}=R^{2}$,
$\mathcal{A}=\frac{R^{2}(\omega+1)}{N}(\kappa\mathrm{Tr}\left(H\mathrm{Cov}\left[W_{*}\right]\right)+\sigma^{2})$
with $W_{*}\sim\mathrm{Unif}(\\{w_{*}^{i},i\in[N]\\})$,
$\mathcal{M}_{2}=(\omega+1)^{2}/N$, and $\mathcal{M}_{1}=\Omega
R^{2}\sigma/N$.

  2. 2.

Moreover for any linear compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},$
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$, Theorem 2 holds, with the
same constants and $\Sha_{\mathrm{add}}=\sigma^{2}\Sha_{H}/N$ and
$\Sha_{\mathrm{mult}}=R^{2}\Sha_{H}/N$, with $\Sha_{H}$ given in Corollary 2.

Corollary 5 can be proved reusing computation made for Corollary 4 and using
below Proposition 5. We next aim at computing the additive noise covariance.
We note $g_{k,*}^{i}=\textsl{g}_{k}^{i}(w_{*})$ the local stochastic gradient
evaluated at optimal point $w_{*}$. We have, in Model 1, for any
$w\in\mathbb{R}^{d}$,
$F_{i}(w):=\mathbb{E}(\langle{x_{k}^{i}},{w-w_{*}^{i}}\rangle-
x_{k}^{i}\varepsilon_{k}^{i})^{2}$, thus $\nabla
F(w)=\frac{1}{N}\sum_{i=1}^{N}H(w-w_{*}^{i})$, and
$w_{*}=\sum_{i=1}^{N}w_{*}^{i}/N$. The setting of Definition 1 is verified
with $H_{F}=H$, and for any $w\in\mathbb{R}^{d}$, that the random field
$\xi_{k}$ can be computed as:

$\displaystyle\xi_{k}(w-w_{*})$ $\displaystyle\overset{\text{Def.
}\ref{def:class_of_algo}\&\mathrm{Alg.}\ref{ex:dist_comp_LMS}}{=}H_{F}(w-w_{*})-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}^{i}(\textsl{g}_{k}^{i}(w)),\text{
thus }\xi_{k}^{\mathrm{add}}\overset{\text{Def.
}\ref{def:add_mult_noise}}{=}-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}^{i}(g_{k,*}^{i}),$

with $g_{k,*}^{i}=(x_{k}^{i}\otimes
x_{k}^{i})(w_{*}-w_{*}^{i})+x_{k}^{i}\varepsilon_{k}^{i}$. We thus have, for
any $k\in\mathbb{N}$:

$\displaystyle\mathfrak{C}_{\mathrm{ania}}$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[(\xi_{k}^{\mathrm{add}})^{{\otimes
2}}\right]\overset{\nabla
F(w_{*})=0}{=}\mathbb{E}\left[\left(\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}^{i}(g_{k,*}^{i})-\nabla
F_{i}(w_{*})\right)^{{\otimes 2}}\right]$ $\displaystyle\overset{\forall i\neq
j,\leavevmode\nobreak\
\mathcal{C}_{k}^{i}\perp\mathcal{C}_{k}^{j}}{\underset{\mathbb{E}\mathcal{C}^{i}_{k}(g_{k,*}^{i})=\nabla
F_{i}(w_{*})}{=}}$
$\displaystyle\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}\left[\left(\mathcal{C}^{i}_{k}(g_{k,*}^{i})-\nabla
F_{i}(w_{*})\right)^{{\otimes 2}}\right]$ $\displaystyle=$
$\displaystyle\frac{1}{N^{2}}\sum_{i=1}^{N}\left(\mathbb{E}[\mathcal{C}^{i}_{k}(g_{k,*}^{i})^{{\otimes
2}}]-\nabla F_{i}(w_{*})^{{\otimes 2}}\right)\,$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{N^{2}}\sum_{i=1}^{N}\mathfrak{C}(\mathcal{C}^{i},p_{{\Theta}_{i}})-\frac{\displaystyle
1}{\displaystyle N^{2}}H\sum_{i=1}^{N}(w_{*}-w_{*}^{i})^{\otimes
2}H\preccurlyeq\frac{\sigma^{2}}{N}\overline{\mathfrak{C}((\mathcal{C}^{i},p_{\Theta_{i}})_{i=1}^{N})}\,,$

where $p_{\Theta_{i}}$ is the distribution of $g_{k,*}^{i}$ (for any $k$). In
the last inequality, we simply discarded the non-positive term
$-H\sum_{i=1}^{N}(w_{*}-w_{*}^{i})^{\otimes 2}H$. For linear compressors, by
Proposition 2, $\mathfrak{C}_{\mathrm{ania}}$ is a linear function of
$\frac{1}{N}\sum_{i=1}^{N}\Theta_{i}$ – the averaged second-order moment of
the local gradients $(g_{k,*}^{i})_{i=1}^{N}$. In order to bound this
quantity, following Dieuleveut et al. (2017), we make the following
assumption.

######  Assumption 5.

The kurtosis for the projection of the covariates $x^{i}_{1}$ (or equivalently
$x^{i}_{k}$ for any $k$) is bounded on any direction $z\in\mathbb{R}^{d}$,
i.e., there exists $\kappa>0$, such that:

$\forall i\in[N],\ \forall
z\in\mathbb{R}^{d},\quad\mathbb{E}\left[\left\langle
z,x^{i}_{1}\right\rangle^{4}\right]\leq\kappa\langle z,Hz\rangle^{2}$

For instance, it is verified for Gaussian vectors with $\kappa=3$. By Cauchy-
Schwarz inequality, it implies that $\mathbb{E}[\left\langle
z,x^{i}_{1}\right\rangle^{2}\ (x^{i}_{1})^{\otimes
2}]\preccurlyeq\kappa\langle z,Hz\rangle H$ for all $z\in\mathbb{R}^{d}$. We
obtain the following proposition.

######  Proposition 5 (Impact of client-heterogeneity.).

Let $W_{*}$ be a random variable uniformly distributed over
$\\{w_{*}^{i},i\in[N]\\}$, thus such that,
$\mathrm{Cov}\left[W_{*}\right]=\frac{1}{N}\sum_{i=1}^{N}(w_{*}-w_{*}^{i})^{\otimes
2}$, then:

$\frac{1}{N}\sum_{i=1}^{N}\Theta_{i}\preccurlyeq(\kappa\mathrm{Tr}\left(H\mathrm{Cov}\left[W_{*}\right]\right)+\sigma^{2})\
H\,.$

Proof  We have:

$\displaystyle\Theta_{i}$ $\displaystyle=\mathbb{E}[((x_{k}^{i}\otimes
x_{k}^{i})(w_{*}-w_{*}^{i})+x_{k}^{i}\varepsilon_{k}^{i})^{\otimes
2}]\overset{(\varepsilon_{k}^{i})\perp(x_{k}^{i})}{=}\mathbb{E}[(x_{k}^{i}\otimes
x_{k}^{i})(w_{*}-w_{*}^{i})^{\otimes 2}(x_{k}^{i}\otimes
x_{k}^{i})]+\sigma^{2}H$ $\displaystyle\overset{\text{Ass.
}\ref{ass:kurtosis}}{\preccurlyeq}\kappa\left\langle
w_{*}-w_{*}^{i},H(w_{*}-w_{*}^{i})\right\rangle
H+\sigma^{2}H=\kappa\mathrm{Tr}\left(H(w_{*}-w_{*}^{i})^{\otimes
2}\right)H+\sigma^{2}H\,.$

In words, we have the following two main observations.

######  Remark 13 (Structured noise before compression.).

Before compression is possibly applied, the noise remains structured, i.e.,
with covariance proportional to $H$, in the case of concept-shift. As a
consequence, the rate for un-compressed Equation LSA will remain independent
of the smallest eigenvalue of $H$. This remark extends to the case where
$\mathcal{C}_{\mathrm{PP}}$ is applied.

######  Remark 14 (Heterogeneous vs homogeneous case).

Compared to the homogeneous case, in which $\Theta_{i}=\sigma^{2}H_{i}$ and
$\mathfrak{C}_{\mathrm{ania}}=\frac{\sigma^{2}}{N}\overline{\mathfrak{C}((\mathcal{C}^{i},p_{H_{i}})_{i=1}^{N})}$,
the averaged second-order moment increases from $\sigma^{2}H$ to
$(\kappa\mathrm{Tr}\left(H\mathrm{Cov}\left[W_{*}\right]\right)+\sigma^{2})H$,
showing the impact of the dispersion of the optimal points
$(w_{*}^{i})_{i=1}^{N}$. This corresponds to the typical variance increase in
the compressed heterogeneous SGD case (Mishchenko et al., 2019; Philippenko
and Dieuleveut, 2020).

Concept-shift thus hinders the limit convergence rate. To limit this effect, a
solution is to introduce a control-variate term
$(h^{i}_{k})_{k\in\mathbb{N}^{*},i\in[N]}$, that is subtracted to the gradient
before compression and asymptotically approximate $\nabla F_{i}(w_{*})$ for
any $i\in[N]$ (see Mishchenko et al., 2019). We explore this direction in
Subsection F.2.

###  4.3 Numerical experiments

We support the theoretical results from Subsections 4.1 and 4.2 by performing
experiments in the FL framework that extend the ones from Section 3.

On figures Figure 8, we present the results of the excess loss of the Polyak-
Ruppert iterate $F(\overline{w}_{k})-F(w_{*})$ versus the number of iterations
in log/log scale. The experiments were run 5 times, each time with different
datasets (dispersion is shown by shaded area).

Settings. (a) Synthetic dataset generation: The dataset is generated using
Model 1 with $N=10$, $K=10^{6}$ on each client, $\sigma^{2}/{N}=1$. For any
clients $i$ in $[N]$, the covariance matrix is $H_{i}=Q_{i}D_{i}Q_{i}^{T}$,
where $Q_{i}$ is an orthogonal matrix. For heterogeneous clients, the dataset
generation is as follows. Covariate shift: The rotation matrix $Q_{i}$ is
sampled independently for each client and the diagonal matrix $D_{i}$ is
$\mathrm{Diag}\left((1/j^{\beta_{i}})_{j=1}^{d}\right)$ where
$\beta_{i}\sim\mathrm{Unif}(\\{3,4,5,6\\})$. Concept-shift: The optimal models
of the clients $i\in[N]$ were drawn from a zero-centered normal distribution
with a variance of $100\mathrm{I}_{d}$, that is,
$w_{*}^{i}\sim\mathcal{N}(0,100\mathrm{I}_{d})$. We also take for all client
$i$ in $[N]$, $H_{i}=QDQ^{T}$, with
$D=\mathrm{Diag}\left((1/j\right))_{j=1}^{d}$. (b) Real-dataset and covariate-
shift: To simulate non-i.i.d. clients, we split the dataset in heterogeneous
groups (with equal number of points) using a $K$-nearest neighbors clustering
on the TSNE representations (defined by Maaten and Hinton, 2008). Thus, the
marginal feature distribution significantly varies between clients, providing
a covariate-shift, while keeping the same distribution for the output
conditional to the features on all clients. (c) Algorithm 3: We take a
constant step-size $\gamma=1/(2(\omega+1)R^{2})$ with
$R^{2}=\mathrm{Tr}\left(H\right)$ and $w_{0}=0$ as initial point. We set the
batch-size $b=1$ for synthetic datasets and $b=16$ for real datasets, the
compressor variance is $\omega=10$. (d) Algorithm 3 vs Algorithm 4: We take a
bigger constant step-size $\gamma=(2R^{2})^{-1}$ in order to emphasize the
difference between the case w./w.o. control variate, we set $w_{0}=0$ as
initial point and the compressor variance is $\omega=10$. We set the batch-
size $b=32$ for Figure 8(c) and $b=K$ for Figure 8(f).

Covariate-shift | Concept-shift
---|---
Synthetic dataset | Real datasets | Synthetic dataset
|  |
|  |

(a) No shift: $\forall i\in[N],H_{i}=H$

(b) quantum

(c) Batch stochastic gradient

(d) $\forall i,j\in[N],H_{i}{\neq}H_{j}$

(e) cifar-10

(f) True gradient $\textsl{g}_{k}^{i}=\nabla F_{i}$

Figure 8: Logarithm excess loss of the Polyak-Ruppert iterate iterations for
$N=10$ clients.

Interpretation – homogeneous case and covariate-shift case (Figures 8(a),
8(d), 8(b) and 8(e)). These experiments extend those presented in Subsection
3.4 in the case of a single client. The observations made in the centralized
case (Figure 7), especially on the impact of the compressor choice on the
convergence and the ordering between limit convergence rates remain valid.
This illustrates Corollary 4 and Remark 11: Theorems 2 and 1 hold in the case
of homogeneous client or in the case of heterogeneous covariance and the only
compressor that ensures that the noise is structured is client sampling
(partial participation). On the real datasets, quantization is also
competitive.

Interpretation – concept-shift case (Figures 8(c) and 8(f)). These experiments
extend those presented on Figure 7(e) (slow eigenvalues’ decay with
$\mu=10^{-2}$) to the scenario of concept shift. First, we observe on Figure
8(c) that for all compressors the convergence rate remains in $O(1/K)$,
(though vanilla SGD converges faster during the first iterations). Second, we
observe that control-variates improve convergence for compressors inducing un-
structured noise ; this is predicted by theory, see Theorem S4. Third, on
Figure 8(f), at each iteration $k\in[K]$, we use deterministic gradients
$g_{k}^{i}=\nabla F_{i}$ which leads to having a.s.
$\xi_{k}^{\mathrm{add}}=0$, and in the absence of compression, we obtain a
$O(1/K^{2})$ convergence rate for $\overline{w}_{K}$ which corresponds in
Theorem 1 to the case where the dependency on the initial condition is
dominated by $\frac{\|H_{F}^{-1/2}\eta_{0}\|^{2}}{\gamma^{2}K^{2}}$. Overall,
these experiments illustrate and support our theoretical insights.

##  5 Conclusion and open directions

Conclusion. In short, we investigate the impact of the choice of compression
scheme on the convergence of the Polyak-Ruppert averaged iterate. By analysing
the case of compressed least-squares regression, we shed light on the
interplay between the Hessian of the optimization problem $H_{F}$, the
features’ distribution, the additive noise’s covariance
$\mathfrak{C}_{\mathrm{ania}}$, and the compression scheme. This shows
fundamental differences between compression that deemed equivalent under the
classical worst-case-variance assumption. We extend our analysis to the case
of heterogeneous federated learning, a setting in which compression is widely
used and its impact not fully understood.

More precisely, first, the analysis of the generic stochastic approximation
algorithm (LSA) provides (1) the fact that projection based compressions
achieve a faster convergence rate than quantization based, and that yet, their
asymptotic rate is similar; (2) the analysis of quantization-based compression
requires introducing a new Hölder-type regularity assumption for the analysis
of the stochastic approximation scheme, and showing that such an assumption is
satisfied for quantization.

Second, the computation of the additive noise’s covariance
$\mathfrak{C}_{\mathrm{ania}}$ reveals the impact of the compression scheme
and the data distribution on the asymptotically dominant term. We obtain that
(1) partial participation (i.e., client sampling in the federated case) is the
only method that systematically ensures a convergence without a dependency on
the strong-convexity constant; (2) other compressors may all induce an un-
structured noise, with covariance scaling with $\mathrm{I}$ or $\sqrt{H}$,
that strongly hinders convergence by accumulating noise on low curvature
directions; (3) the relative performance or various schemes changes depending
on the pre-processing applied to the data, making quantization the best method
(apart from PP) when standardization is applied, but one of the worst (with
random Gaussian projection) when the features are independent and the
eigenvalues of the covariance decay rapidly (4) in that particular last
setting, all projection based methods (but Gaussian projection) behave
similarly.

Third, we discuss how these results apply to the federated case, that
corresponds to the initial motivation. We show that we encompass two
particular heterogeneity situations and how our analysis applies. Overall,
these results are a step towards a better understanding of the impact of a
widely used tool.

Open directions. This analysis can be extended to include various aspects that
are beyond the scope of this work. First, one natural improvement for
application in FL would be to consider also the scenario where each client
runs several local iterations (McMahan et al., 2017; Karimireddy et al., 2020)
before sending their updates, reducing further the cost of communication.
Similar approach can be used, although the additive noise field would be more
complicated, which potentially implies a different additive noise’s
covariance. Second, as mentioned in Subsection 3.5, our analysis could also be
extended to the case of stochastic approximation with ridge regularization
(e.g., following Dieuleveut et al., 2017) which in practice is helpful to
mitigate the impact of the lack of strong convexity. Third, an obvious
direction is to extend beyond quadratic functions and considering other
objective functions, such as logistic regression or even shallow neural
networks. Several results in the literature can be leveraged to tackle non
quadratic but self-concordant losses Bach (2010); Gadat and Panloup (2023).
Fourth, our analysis still only relies on second moments (variance and
covariance) of the stochastic field. One major drawback of partial
participation is to induce a significant increase on higher order moments.
Incorporating higher order bounds may also bring novel insights to the use of
compression in FL. Finally, all our analysis is made in finite dimension and
our asymptotic focuses on $K\to\infty$: further works should analyze the case
of infinite dimension: within the reproducing kernel Hilbert space (Dieuleveut
and Bach, 2016) framework or within the overparametrized setting (Belkin et
al., 2019).

##  6 Acknowledgements

We would like to thank Richard Vidal, Laeticia Kameni from Accenture Labs
(Sophia Antipolis, France), and Eric Moulines from École Polytechnique for
insightful discussions. We also thank Baptiste Goujaud for his great help in
computing the covariance of sketching, and JM for her help on Figure 1. This
research was supported by the _SCAI: Statistics and Computation for AI_ ANR
Chair of research and teaching in artificial intelligence, by Hi!Paris, and by
_Accenture Labs_ (Sophia Antipolis, France).

Constantin Philippenko thanks his sister Ania, whose covariance has greatly
helped to write the theorems.

## Bibliography

  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: a system for large-scale machine learning.  In _Proceedings of the 12th USENIX conference on Operating Systems Design and Implementation_ , OSDI’16, pages 265–283, USA, November 2016. USENIX Association.  ISBN 978-1-931971-33-1.
  * Alistarh et al. (2017) Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic.  QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding.  _Advances in Neural Information Processing Systems_ , 30:1709–1720, 2017.
  * Alistarh et al. (2018) Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli.  The Convergence of Sparsified Gradient Methods.  _Advances in Neural Information Processing Systems_ , 31:5973–5983, 2018.
  * Arablouei et al. (2015) Reza Arablouei, Stefan Werner, Kutluyıl Doğançay, and Yih-Fang Huang.  Analysis of a reduced-communication diffusion lms algorithm.  _Signal Processing_ , 117:355–361, 2015.
  * Bach (2010) Francis Bach.  Self-concordant analysis for logistic regression.  _Electronic Journal of Statistics_ , 4(none):384–414, January 2010.  ISSN 1935-7524, 1935-7524.  doi: 10.1214/09-EJS521.  Publisher: Institute of Mathematical Statistics and Bernoulli Society.
  * Bach (2014) Francis Bach.  Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression.  _The Journal of Machine Learning Research_ , 15(1):595–627, 2014.
  * Bach (2022) Francis Bach.  Lecture notes on statistical machine learning and convex optimization, 2022.
  * Bach and Moulines (2013) Francis Bach and Eric Moulines.  Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n).  In _Neural Information Processing Systems (NIPS)_ , pages –, United States, December 2013.
  * Belkin et al. (2019) Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  _Proceedings of the National Academy of Sciences_ , 116(32):15849–15854, 2019.  Publisher: National Acad Sciences.
  * Benveniste et al. (2012) Albert Benveniste, Michel Métivier, and Pierre Priouret.  _Adaptive algorithms and stochastic approximations_ , volume 22.  Springer Science & Business Media, 2012.
  * Bernstein et al. (2018) Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar.  signsgd: Compressed optimisation for non-convex problems.  In _International Conference on Machine Learning_ , pages 560–569. PMLR, 2018.
  * Bershad (1986) Neil Bershad.  Analysis of the normalized lms algorithm with gaussian inputs.  _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , 34(4):793–806, 1986.
  * Beznosikov et al. (2020) Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan.  On Biased Compression for Distributed Learning.  _arXiv:2002.12410 [cs, math, stat]_ , February 2020.  arXiv: 2002.12410.
  * Blum (1954) Julius R Blum.  Multidimensional stochastic approximation methods.  _The Annals of Mathematical Statistics_ , pages 737–744, 1954.
  * Bottou and Bousquet (2007) Léon Bottou and Olivier Bousquet.  The Tradeoffs of Large Scale Learning.  _Advances in Neural Information Processing Systems_ , 20:161–168, 2007.
  * Caldas et al. (2019) Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar.  LEAF: A Benchmark for Federated Settings.  _arXiv:1812.01097 [cs, stat]_ , December 2019.  arXiv: 1812.01097.
  * Carratino et al. (2018) Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco.  Learning with SGD and Random Features.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Caruana et al. (2004) Rich Caruana, Thorsten Joachims, and Lars Backstrom.  KDD-Cup 2004: results and analysis.  _ACM SIGKDD Explorations Newsletter_ , 6(2):95–108, December 2004.  ISSN 1931-0145.  doi: 10.1145/1046456.1046470.
  * Chilimbi et al. (2014) Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman.  Project adam: Building an efficient and scalable deep learning training system.  In _11th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 14)_, pages 571–582, 2014.
  * Chraibi et al. (2019) Sélim Chraibi, Ahmed Khaled, Dmitry Kovalev, Peter Richtárik, Adil Salim, and Martin Takáč.  Distributed fixed point methods with compressed iterates.  _arXiv preprint arXiv:1912.09925_ , 2019.
  * Dai et al. (2019) Xinyan Dai, Xiao Yan, Kaiwen Zhou, Han Yang, Kelvin KW Ng, James Cheng, and Yu Fan.  Hyper-sphere quantization: Communication-efficient sgd for federated learning.  _arXiv preprint arXiv:1911.04655_ , 2019.
  * Defossez and Bach (2015) Alexandre Defossez and Francis Bach.  Averaged Least-Mean-Squares: Bias-Variance Trade-offs and Optimal Sampling Distributions.  In _Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics_ , pages 205–213. PMLR, February 2015.  ISSN: 1938-7228.
  * Delyon (1996) Bernard Delyon.  General results on the convergence of stochastic algorithms.  _IEEE Transactions on Automatic Control_ , 41(9):1245–1255, 1996.
  * Dieuleveut and Bach (2016) Aymeric Dieuleveut and Francis Bach.  Nonparametric stochastic approximation with large step-sizes.  _Ann. Statist._ , 44(4):1363–1399, 2016.  ISSN 0090-5364.  doi: 10.1214/15-AOS1391.
  * Dieuleveut et al. (2017) Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach.  Harder, better, faster, stronger convergence rates for least-squares regression.  _The Journal of Machine Learning Research_ , 18(1):3520–3570, 2017.  Publisher: JMLR. org.
  * Dieuleveut et al. (2020) Aymeric Dieuleveut, Alain Durmus, and Francis Bach.  Bridging the gap between constant step size stochastic gradient descent and markov chains.  _Ann. Statist._ , 48(3):1348–1382, 06 2020.  doi: 10.1214/19-AOS1850.  URL https://doi.org/10.1214/19-AOS1850.
  * Duflo (1997) Marie Duflo.  _Random iterative models_ , volume 34.  Springer Science & Business Media, 1997.
  * Fatkhullin et al. (2021) Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik.  EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback, October 2021.  arXiv:2110.03294 [cs, math].
  * Flammarion and Bach (2015) Nicolas Flammarion and Francis Bach.  From averaging to acceleration, there is only a step-size.  In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, _Proceedings of The 28th Conference on Learning Theory_ , volume 40 of _Proceedings of Machine Learning Research_ , pages 658–695, Paris, France, 03–06 Jul 2015. PMLR.  URL https://proceedings.mlr.press/v40/Flammarion15.html.
  * Freidlin and Wentzell (1998) Mark Iosifovich Freidlin and Alexander D Wentzell.  Random perturbations.  In _Random perturbations of dynamical systems_ , pages 15–43. Springer, 1998.
  * Gadat and Panloup (2023) Sébastien Gadat and Fabien Panloup.  Optimal non-asymptotic analysis of the Ruppert–Polyak averaging stochastic algorithm.  _Stochastic Processes and their Applications_ , 156:312–348, February 2023.  ISSN 0304-4149.  doi: 10.1016/j.spa.2022.11.012.
  * Gandikota et al. (2021) Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar.  vqsgd: Vector quantized stochastic gradient descent.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2197–2205. PMLR, 2021.
  * Gersho and Gray (2012) Allen Gersho and Robert M Gray.  _Vector quantization and signal compression_ , volume 159.  Springer Science & Business Media, 2012.
  * Gorbunov et al. (2020a) Eduard Gorbunov, Filip Hanzely, and Peter Richtárik.  A unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent.  In _International Conference on Artificial Intelligence and Statistics_ , pages 680–690. PMLR, 2020a.
  * Gorbunov et al. (2020b) Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtarik.  Linearly Converging Error Compensated SGD.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 20889–20900. Curran Associates, Inc., 2020b.
  * Györfi and Walk (1996) László Györfi and Harro Walk.  On the averaged stochastic approximation for linear regression.  _SIAM Journal on Control and Optimization_ , 34(1):31–61, 1996.
  * Haddadpour et al. (2021) Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi.  Federated learning with compression: Unified analysis and sharp guarantees.  In Arindam Banerjee and Kenji Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 2350–2358. PMLR, 13–15 Apr 2021.  URL https://proceedings.mlr.press/v130/haddadpour21a.html.
  * Harrane et al. (2018) Ibrahim El Khalil Harrane, Rémi Flamary, and Cédric Richard.  On reducing the communication cost of the diffusion lms algorithm.  _IEEE Transactions on Signal and Information Processing over Networks_ , 5(1):100–112, 2018.
  * Horvath et al. (2022) Samuel Horvath, Chen-Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik.  Natural compression for distributed deep learning.  In _Mathematical and Scientific Machine Learning_ , pages 129–141. PMLR, 2022.
  * Horváth et al. (2019) Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik.  Stochastic Distributed Learning with Gradient Quantization and Variance Reduction.  _arXiv:1904.05115 [math]_ , April 2019.  arXiv: 1904.05115.
  * Hsu et al. (2012) Daniel Hsu, Sham M. Kakade, and Tong Zhang.  Random Design Analysis of Ridge Regression.  In _Proceedings of the 25th Annual Conference on Learning Theory_ , pages 9.1–9.24. JMLR Workshop and Conference Proceedings, June 2012\.  ISSN: 1938-7228.
  * Ivkin et al. (2019) Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, and Raman Arora.  Communication-efficient Distributed SGD with Sketching.  _Advances in Neural Information Processing Systems_ , 32:13144–13154, 2019.
  * Jain et al. (2018a) Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford.  Accelerating Stochastic Gradient Descent for Least Squares Regression.  In _Proceedings of the 31st Conference On Learning Theory_ , pages 545–604. PMLR, July 2018a.  ISSN: 2640-3498.
  * Jain et al. (2018b) Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford.  Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification.  _Journal of Machine Learning Research_ , 18(223):1–42, 2018b.  ISSN 1533-7928.
  * Kairouz et al. (2019) Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D’Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao.  Advances and Open Problems in Federated Learning.  _arXiv:1912.04977 [cs, stat]_ , December 2019.  arXiv: 1912.04977.
  * Karimireddy et al. (2019) Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi.  Error Feedback Fixes SignSGD and other Gradient Compression Schemes.  In _International Conference on Machine Learning_ , pages 3252–3261. PMLR, May 2019.  ISSN: 2640-3498.
  * Karimireddy et al. (2020) Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.  Scaffold: Stochastic controlled averaging for federated learning.  In _International Conference on Machine Learning_ , pages 5132–5143. PMLR, 2020.
  * Khirirat et al. (2018) Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson.  Distributed learning with compressed gradients.  _arXiv preprint arXiv:1806.06573_ , 2018.
  * Koloskova et al. (2019) Anastasia Koloskova, Sebastian Stich, and Martin Jaggi.  Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication.  In _International Conference on Machine Learning_ , pages 3478–3487. PMLR, May 2019.  ISSN: 2640-3498.
  * Konda and Tsitsiklis (2003) Vijay R Konda and John N Tsitsiklis.  Linear stochastic approximation driven by slowly varying markov chains.  _Systems & control letters_, 50(2):95–102, 2003\.
  * Konečný et al. (2016) Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon.  Federated Learning: Strategies for Improving Communication Efficiency.  In _NIPS Workshop on Private Multi-Party Machine Learning_ , 2016.
  * Kovalev et al. (2021) Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtarik.  Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks.  _Advances in Neural Information Processing Systems_ , 34:22325–22335, 2021.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, and others.  Learning multiple layers of features from tiny images.  2009\.  Publisher: Citeseer.
  * Kumar et al. (2009) Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar.  Ensemble Nystrom Method.  In _Advances in Neural Information Processing Systems_ , volume 22. Curran Associates, Inc., 2009.
  * Kushner and Yin (2003) Harold J. Kushner and George Yin.  Stochastic approximation and recursive algorithms and applications.  2003\.
  * Leconte et al. (2021) Louis Leconte, Aymeric Dieuleveut, Edouard Oyallon, Eric Moulines, and Gilles Pages.  DoStoVoQ: Doubly Stochastic Voronoi Vector Quantization SGD for Federated Learning.  May 2021.
  * Legendre (1806) Adrien Marie Legendre.  _Nouvelles méthodes pour la détermination des orbites des comètes_.  Firmin Didot, Libraire pour les mathematiques, 1806.
  * Leluc and Portier (2022) Rémi Leluc and François Portier.  Sgd with coordinate sampling: Theory and practice.  _Journal of Machine Learning Research_ , 23(342):1–47, 2022.
  * Li et al. (2006) Ping Li, Trevor J Hastie, and Kenneth W Church.  Very sparse random projections.  In _Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 287–296, 2006.
  * Li (2010) Shengqiao Li.  Concise formulas for the area and volume of a hyperspherical cap.  _Asian Journal of Mathematics & Statistics_, 4(1):66–70, 2010.
  * Li and Richtárik (2021) Zhize Li and Peter Richtárik.  Canita: Faster rates for distributed convex optimization with communication compression.  _Advances in Neural Information Processing Systems_ , 34:13770–13781, 2021.
  * Li et al. (2020) Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik.  Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization.  In _International Conference on Machine Learning_ , pages 5895–5904. PMLR, November 2020.  ISSN: 2640-3498.
  * Lin and Rosasco (2017) Junhong Lin and Lorenzo Rosasco.  Optimal Rates for Learning with Nyström Stochastic Gradient Methods.  _arXiv preprint arXiv:1710.07797_ , 2017.
  * Liu et al. (2020) Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan.  A Double Residual Compression Algorithm for Efficient Distributed Learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 133–143, June 2020.  ISSN: 1938-7228 Section: Machine Learning.
  * Ljung (1977) Lennart Ljung.  Analysis of recursive stochastic algorithms.  _IEEE transactions on automatic control_ , 22(4):551–575, 1977.
  * Ljung and Söderström (1983) Lennart Ljung and Torsten Söderström.  _Theory and practice of recursive identification_.  MIT press, 1983.
  * Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton.  Visualizing Data using t-SNE.  _Journal of Machine Learning Research_ , 9(Nov):2579–2605, 2008.  ISSN ISSN 1533-7928.
  * Macchi (1995) Odile Macchi.  _Adaptative processing: the least mean squares approach with applications in transmission_ , volume 71.  New York: John Wiley & Sons, Ltd, 1995.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In _Artificial Intelligence and Statistics_ , pages 1273–1282. PMLR, April 2017.  ISSN: 2640-3498.
  * Mishchenko et al. (2019) Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik.  Distributed Learning with Compressed Gradient Differences.  _arXiv:1901.09269 [cs, math, stat]_ , June 2019.  arXiv: 1901.09269.
  * Molnar (2018) Christoph Molnar.  _Interpretable Machine Learning: A Guide for Making Black Box Models Explainable_.  2018\.
  * Moulines and Bach (2011) Eric Moulines and Francis Bach.  Non-asymptotic analysis of stochastic approximation algorithms for machine learning.  _Advances in neural information processing systems_ , 24, 2011.
  * Muecke et al. (2019) Nicole Muecke, Gergely Neu, and Lorenzo Rosasco.  Beating SGD Saturation with Tail-Averaging and Minibatching.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Nesterov (2012) Yu Nesterov.  Efficiency of coordinate descent methods on huge-scale optimization problems.  _SIAM Journal on Optimization_ , 22(2):341–362, 2012.
  * Neu and Rosasco (2018) Gergely Neu and Lorenzo Rosasco.  Iterate averaging as regularization for stochastic gradient descent.  In _Conference On Learning Theory_ , pages 3222–3242. PMLR, 2018\.
  * Nutini et al. (2015) Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke.  Coordinate descent converges faster with the gauss-southwell rule than random selection.  In _International Conference on Machine Learning_ , pages 1632–1641. PMLR, 2015.
  * Philippenko and Dieuleveut (2020) Constantin Philippenko and Aymeric Dieuleveut.  Artemis: tight convergence guarantees for bidirectional compression in Federated Learning.  _arXiv:2006.14591 [cs, stat]_ , November 2020.  arXiv: 2006.14591.
  * Philippenko and Dieuleveut (2021) Constantin Philippenko and Aymeric Dieuleveut.  Preserved central model for faster bidirectional compression in distributed settings.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Polyak and Juditsky (1992) Boris Polyak and Anatoli Juditsky.  Acceleration of Stochastic Approximation by Averaging.  _SIAM Journal on Control and Optimization_ , 30:838–855, July 1992.  doi: 10.1137/0330046.
  * Rabbat and Nowak (2005) Michael G Rabbat and Robert D Nowak.  Quantized incremental algorithms for distributed optimization.  _IEEE Journal on Selected Areas in Communications_ , 23(4):798–808, 2005.
  * Rahimi and Recht (2008) Ali Rahimi and Benjamin Recht.  Random Features for Large-Scale Kernel Machines.  In _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2008.
  * Ramezani-Kebrya et al. (2021) Ali Ramezani-Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M Roy.  Nuqsgd: Provably communication-efficient data-parallel sgd via nonuniform quantization.  _The Journal of Machine Learning Research_ , 22(1):5074–5116, 2021.
  * Reisizadeh et al. (2020) Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani.  FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2021–2031. PMLR, June 2020.  ISSN: 2640-3498.
  * Richtarik et al. (2021) Peter Richtarik, Igor Sokolov, and Ilyas Fatkhullin.  EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 4384–4396. Curran Associates, Inc., 2021.
  * Robbins and Monro (1951) Herbert Robbins and Sutton Monro.  A Stochastic Approximation Method.  _Annals of Mathematical Statistics_ , 22(3):400–407, September 1951.  ISSN 0003-4851, 2168-8990.  doi: 10.1214/aoms/1177729586.  Number: 3 Publisher: Institute of Mathematical Statistics.
  * Rudi and Rosasco (2017) Alessandro Rudi and Lorenzo Rosasco.  Generalization Properties of Learning with Random Features.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Rudi et al. (2015) Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco.  Less is More: Nyström Computational Regularization.  In _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.
  * Rudi et al. (2017) Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco.  FALKON: An Optimal Large Scale Kernel Method.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Sattler et al. (2019) Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek.  Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data.  _IEEE Transactions on Neural Networks and Learning Systems_ , pages 1–14, 2019.  ISSN 2162-2388.  doi: 10.1109/TNNLS.2019.2944481.  Conference Name: IEEE Transactions on Neural Networks and Learning Systems.
  * Seide and Agarwal (2016) Frank Seide and Amit Agarwal.  CNTK: Microsoft’s Open-Source Deep-Learning Toolkit.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, page 2135, New York, NY, USA, August 2016. Association for Computing Machinery.  ISBN 978-1-4503-4232-2.  doi: 10.1145/2939672.2945397.
  * Seide et al. (2014) Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns.  In _Fifteenth Annual Conference of the International Speech Communication Association_. Citeseer, 2014.
  * Sidiropoulos (2014) Panagiotis Sidiropoulos.  N-sphere chord length distribution.  _arXiv preprint arXiv:1411.5639_ , 2014.
  * Stich et al. (2018) Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi.  Sparsified SGD with Memory.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 4447–4458. Curran Associates, Inc., 2018.
  * Strom (2015) Nikko Strom.  Scalable distributed DNN training using commodity GPU cloud computing.  In _Sixteenth Annual Conference of the International Speech Communication Association_ , 2015.
  * Tang et al. (2019) Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu.  DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-pass Error-Compensated Compression.  In _International Conference on Machine Learning_ , pages 6155–6165. PMLR, May 2019.  ISSN: 2640-3498.
  * Varre and Flammarion (2022) Aditya Varre and Nicolas Flammarion.  Accelerated SGD for Non-Strongly-Convex Least Squares.  In _Proceedings of Thirty Fifth Conference on Learning Theory_ , pages 2062–2126. PMLR, June 2022.  ISSN: 2640-3498.
  * Vempala (2005) Santosh S Vempala.  _The random projection method_ , volume 65.  American Mathematical Soc., 2005.
  * Wu et al. (2018) Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang.  Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization.  In _International Conference on Machine Learning_ , pages 5325–5333. PMLR, July 2018.  ISSN: 2640-3498.
  * Xu et al. (2020) An Xu, Zhouyuan Huo, and Heng Huang.  Optimal gradient quantization condition for communication-efficient distributed training.  _arXiv preprint arXiv:2002.11082_ , 2020.
  * Zheng et al. (2019) Shuai Zheng, Ziyue Huang, and James Kwok.  Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.

Supplementary material

In this appendix, we provide additional information to supplement our work. In
Appendix A, we begin by detailing technical results, by introducing an
auxiliary lemma and by proving Proposition 1 which gives a CLT for (LSA).
Secondly, in respectively Appendix B and Appendix C, we give the proof of
Theorems 1 and 2. Thirdly, in Appendix D, we verify that the setting of
single-client compressed LSR fulfills the setting presented in Section 2. In
Appendix E we prove that Lemma 1 hold and compute the compressors’ covariance
to establish Propositions 2 and 3. Finally, in Appendix F, we provide
demonstrations for the federated learning case, including verifying
assumptions (covariate-shift scenario) on random fields in Subsection F.1, and
proving a Central Limit Theorem S4 in Subsection F.2 for the concept-shift
scenario.

##### Additional notations.

We use the Frobenius norm $\|A\|^{2}:=\mathrm{Tr}\left(A^{\top}A\right)$,
which is the same notation as the vector Euclidean norm (no ambiguity in
general), $J_{r}$ to denote the $d\times d$ diagonal matrix whose $r$ first
diagonal elements are equal to one and all the other matrix’s coefficients
equal to zero, $\mathcal{S}^{++}_{d}(\mathbb{R})$ the cone of positive
definite symmetric matrices, and
$\mathcal{L}^{p}(\Omega,\mathcal{A},\mathbb{P})$ the set of random vectors
defined on the probability space $(\Omega,\mathcal{A},\mathbb{P})$ such that
$\mathbb{E}[\|X\|^{p}]<\infty$. We define also the operator norm
${|\kern-1.07639pt|\kern-1.07639pt|A|\kern-1.07639pt|\kern-1.07639pt|}:=\sqrt{\max\mathrm{eig}(A^{\top}A)}$.

###### Contents

  1. 1 Introduction
  2. 2 Non asymptotic convergence result for (LSA)
  3. 3 Application to Algorithm 2: compressed LSR on a single worker
  4. 4 Application to Federated Learning
  5. 5 Conclusion and open directions
  6. 6 Acknowledgements
  7. A Technical results
  8. B Generalization of Bach and Moulines (2013).
  9. C Generalisation of Bach and Moulines (2013) for linear multiplicative noise.
  10. D Validity of the assumptions made on the random fields
  11. E Compression operators
  12. F Technical results on federated learning.

##  Appendix A Technical results

###  A.1 Settings of experiments

In Tables S1 and S2, we summarize the settings of experiments presented in
Subsection 3.4.

Table S1: Settings of experiments for a single client ($N=1$) on synthetic data (Figures 7(a) and 7(b)). Parameter | $K$ | $d$ | $\mathrm{eig}(H)_{i}$ | $w_{*}$ | $\sigma^{2}$ | $\omega$ | $\gamma^{-1}$ | $w_{0}$ | #runs
---|---|---|---|---|---|---|---|---|---
Values | $10^{7}$ | $100$ | $1/i^{4}$ | $(1)_{i=1}^{d}$ | $1$ | $10$ | $2(\omega+1)R^{2}$ | 0 | 5
Table S2: Settings of experiments for a single client ($N=1$) on real data (Figures 7(f) and 7(c)). Dataset | $d$ | standardization | $b$ | $\omega$ | $\gamma^{-1}$ | $w_{0}$ | #runs | reference
---|---|---|---|---|---|---|---|---
quantum | $65$ | ✓ | $16$ | $1$ | $2(\omega+1)R^{2}$ | 0 | 5 | (CTL04)
cifar-10 | $256$ | (Kri09)

###  A.2 Useful identities and inequalities

In this Subsection, we recall some classical inequalities and results.