Iterative Sketching and its Application to Federated Learning
Authors: Zhao Song
Zheng Yu
Lichen Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated learning
optimization
sketching
differential privacy

Abstract: Johnson-Lindenstrauss lemma is one of the most valuable tools in machine learning, since it enables the reduction to the dimension of various learning problems. In this paper, we exploit the power of Fast-JL transform or so-called sketching technique and apply it to federated learning settings. Federated learning is an emerging learning scheme which allows multiple clients to train models without data exchange. Though most federated learning frameworks only require clients and the server to send gradient information over the network, they still face the challenges of communication efficiency and data privacy. We show that by iteratively applying independent sketches combined with additive noises, one can achieve the above two goals simultaneously. In our designed framework, each client only passes a sketched gradient to the server, and de-sketches the average-gradient information received from the server to synchronize. Such framework enjoys several benefits: 1). Better privacy, since we only exchange randomly sketched gradients with low-dimensional noises, which is more robust against emerging gradient attacks; 2). Lower communication cost per round, since our framework only communicates low-dimensional sketched gradients, which is particularly valuable in a small-bandwidth channel; 3). No extra overall communication cost. We provably show that the introduced randomness does not increase the overall communication at all.


Under review as a conference paper at ICLR 2022
ITERATIVE SKETCHING AND ITS APPLICATION TO FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Johnson-LLindensrraus lemma is one of the most valuable tools in machine learn- ing, since it enables the reduction to the dimension of various learning problems. In this paper, exploit the power of Fast-JL transform so-called sketching technique and apply it to federated learning settings. Federated learning is an emerging learning scheme which allows multiple clients to train models without data exchange. Though most federated learning frameworks only require clients and the server to send gradient information over the network, they still face the challenges of communication efficiency and data privacy. We show that by it- eratively applying independent sketches combined with additive noises, one achieve the above two goals simultancously. In our designed framework, each client only passes sketched gradient to the server, and de-sketches the average- gradient information received from the server to synchronize. Such framework enjoys several benefits: 1). Better privacy, since we only exchange randomly sketched gradients with low-dimensional noises, which is more robust against emerging gradient attacks; 2). Lower communication cost per round, since our framework only communicates low-dimensional sketched gradients, which is par- ticularly valuable a hanul-bbndwidth channel; 3). No extra overall communica- tion cost. We provably show that the introduced randomness does not increase the overall communication at all.
INTRODUCTION
Federated learning enables multiple parties to collaboratively train a machine learning model with- out directly exchanging training data. This has become particularly important in areas of artificial intelligence where users care data privacy, security, and access rights, including healthcare (Li et al., 2020b; 2019), internet of things (Chen et al., 2020), and fraud detection (Zheng et al., 2020).
Given the importance and popularity of federated learning, it has become an important research topic for academia and industry, mostly focusing on two central themes. One is on data privacy. Federated learning seemingly protects clients' privacy, since it only communicates gradient infor- mation. Unfortunately, recent studies (Geiping et al., 2020; Zhu Han, 2020; Wang et al., 2019) have demonstrated that attackers can recover the input data from the shared gradients. The reason why the attacks work is the gradients carry important information about the training data (Ateniese al., 2015; Fredrikson al., 2015). The second one is on communication efficiency. Machine learning models are becoming increasingly larger but client devices that carry private data only have limited network bandwidth. The size of the gradient is the same as the size of the model, and the amount of data to communication between the clients and the servers thus is large. This becomes even more problematic when conducting federated learning on mobile and edge devices, where the bandwidth of the network is low. The communication cost is one of the most important the key per- formance bottlenecks in federated learning systems Goga & Teixeira (2012); Konečný et al. (2016). Many works try to address this challenge through local optimization method, such as local gradi- ent descent (GD), local stochastic gradient descent (SGD) and their variants (Konečný et al., 2016; McMahan et al., 2017; Stich, 2018).
Despite existing efforts, no work addresses both challenges simultancously as far as we concern. Therefore, ask the following question:
Is there FL frameworkk that protects the local privacy and tackles the communication challenge?

---

Under review as a conference paper at ICLR 2022
In this paper, achieve these goals by using old but powerful idea - the Johnson-Lindenstrauss transform and its fast variations (Fast-JL, see Ailon & Chazelle (2006)). we view the transform as sketch matrix, and its transpose de-sketch, then main idea is to iteratively apply the sketch and de-sketch matrices to gradients. Instead of running the vanilla gradient descent w(++1) w(t) - gl using true gradient g( E RR we apply sketch and de-sketch to the gradient: w (1+1) +- w
R R.R. R.
Here R E Rhbaaadd denotes a sketching matrix that sketches the true gradient to a lower dimension and R E Radxba denotes the de de-sketching process that maps the sketched gradient back to the true gradient dimension. The coordinate- wise embedding property (Song & Yu, 2021) ensures R Rg(0) being an unbiased estimator of g with bounded second moments, implying the new sketched gradient descent scheme preserving the original convergence properties. Hence, all clients will only communicate sketched gradients to the server, the server averages the sketched gradients and broacasts back all clients. Finally, each client de-sketches the received gradients and perform local updates. Since the sketching dimension is always small compared to original dimension, we save communication cost per iteration via Johnson-Lindeestrauss.
Though the communication problem has been addressed, such framework still faces privacy chal- lenge: applying Lindesn-Lindessttauuss "masks" the communicated gradients, but in order to give provable privacy guarantee on this framework, we introduce additive low-dimensional Gaussian noises to make sure that the communicated vectors themselves are differential private.
We summarize the contributions in this work follows:
Framework contribution: We propose a new federated learning framework that iteratively applics sketch and de-sketch matrices to gradients, which enjoys the following advantages:
Privacy: preserves the privacy via additive low-dimensional Gaussian noise.
Communication: it reduces communication per round, since at each synchronization step, only
sketched gradient of lower-dimensional is communicated.
Convergence: it preserves the convergence rate of vanilla local gradient descent method.
Technical contribution: Our analysis technique also of independent interest in the relating areas:
Unlike classical sketch-and-solve paradigm, iterative sketch and de-sketch method can be combined with gradient-bart based methods and extended to broader optimization problems.
We provide rigorous analysis on the impact of introducing sketching through coordinate-wise embedding, which can be generalized to other areas (Song & Yu, 2021).
As by-product, give a novel linear convergence result of local GD under the strongly-convex
and smooth scheme.
2 RELATED WORK
Federated Learning Federated learning (FL) is an emerging framework in distributed deep learn- ing. FL allows multiple parties clients collaboratively train model without data sharing. Fl let the local client perform most of the computation and a central sever update the model parame- ters through aggregation then transfers the parameters to local models (Dean al., 2012; Shokri & Shmatikov, 2015; McMahan et al., 2016; 2017). In this way, the details of the data are not disclosed in between each party.
Unlike the standard parallel setting, FL has three unique challenge (Li et al., 2020a), including communication cost, data heterogeneity and client robustness. In our work, we focus on the first two challenges. The training data are massively distributed over an incredibly large number of de- vices, and the connection between the central server and a device slow. direct consequence is the slow communication, which motivated communicatoon-efieientt FL. algorithm. Federated av- erage (FedAvg) (McMahan et al., 2017) firstly addressed the communication efficiency problem by introducing global model to aggregate local stochastic gradient descent updates. Later, dif- ferent variations and adaptations have arisen. This encompasses a myriad of possible approaches, including developing better optimization algorithms (Wang al., 2020a) and generalizing model to heterogeneous clients under special assumptions (Zhao et al., 2018; Kairouz et al., 2019; Li et al., 2021).
2

---

Under review as a conference paper at ICLR 2022
Local GD and Local SGD To seek the communication efficiency of Federated learning, local SGD has been proposed (Konečný et al., 2016; McMahan et al., 2017). where each client does a few SGD iterations locally before the server averages the local estimators. Different variants of local SGD algorithms has been explored, including with momentum (Yu et al., 2019b; Wang et al., 201 2018), with quantization (Basu al., 2019; Reisizadeh al., 2020), and with various variance-reduction methods (Liang et al., 2019; Karimireddy et al.. 2020). Convergence analysis for local SGD mainly focuses on two regimes: identical data regime (Stich, 2018; Basu et al., 2019; Stich & Karimireddy, 2019; Haddadpour & Mahdavi, 2019; Khaled et al., 2020) and heterogeneous data regime (Jiang & Agrawal, 2018; Yu al., 2019a; Basu et al., 2019; Haddadpour & Mahdavi, 2019; Khaled al., 2019; 2020). In this work, we propose our framework based upon vanilla local GD and our analysis focus on the heterogeneous data regime.
Sketching Sketching has many applications in numerical linear, such linear regression, low- rank approximation (Clarkson Woodruff, 2013; Nelson & Nguyên, 2013; Meng & Mahoney, 2013; Boutsidis & Woodruff, 2014; Song al., 2017; Andoni et al., 2018), distributed problems (Woodruff & Zhong, 2016; Boutsidis et al., 2016), reinforcement learning Wang et al. (2020b), tensor decomposition (Song et al., 2019), clustering (Esfandiari et al., 2021), cutting plane method (Jiang et al., 2020), generative adversarial networks (Xiao et al., 2018) and linear programming (Lee al., 2019; Jiang et al., 2021; Song & Yu, 2021).
We use E[-] to denote expectation (if it exists), and use Pr[-] to denote probability. For a vector z, we use || [E==1 x²) denote its lg norm. We denote (x=1) for / E to be the indicator function which equals to 1 if = I and 0 otherwise. Let f A - B and C + A be two functions, we use f o g to denote the composition of functions f and g, i.e., for any C. (f (fog)()) = f(g())) We
Notations For a positive integer we use [n]] to denote the set f1.2.....
denote La to be the identity mapping.
3 PROBLEM SETUP
Consider a federated learning scenario with N clients and corresponding local losses fo Rd + I. our goal is to find
N N
1
min f(x)
fa(x)
ZER
In this work, we consider the following classical convex and smooth setting for our objectives. Assumption 3.1. Assume that the set of minimizers of (1) is nonempty. Each fe is u-strongly comvex for μ 2 O and L-smooth. That is, for all x. y E IRd,
I - x112 < fc()) - fc(x) + (y x, Vf((z)) - 11
Note in the case μ 0, this assumption reduces buck to convexity and smoothness.
Apart from the above assumption, we allow local losses to have arbitrary heterogeneity. In other words, allow fe's to be arbitrary functions.
4 OUR ALGORITHM
In this section, propose federated learning framework that addresses the communication effi- ciency issue. When the learning gradients are of high dimension, classical federated learning frame- work which sends the exact gradient could incur heavy communication cost per round. Sketching technique, which emerges as an effective way to reduce the dimension of vector while preserving significant amount of information (Sarlós, 2006; Woodruff, 2014), is highly preferred in this setting. enables us to compress the gradient vector into a lower dimension while preserving convergence rates, and greatly saves the communication cost per round.
Motivated by above discussion, we propose the iterative sketching based federated learning algo- rithm, which builds upon vanilla local gradient descent: start with a predetermined sequence of
3

---

Under review as a conference paper at ICLR 2022
independent sketching matrices shared across all clients. In each round, local clients accumulate and sketch its change over K local steps, then transmit the low-dimensional sketch to the server. Server then averages the sketches and transmits them back to all clients. Upon receiving, each client de-sketches to update the local model.
Algorithm Iterative Sketching-based Federated Learning Algorithm with local steps
1: procedure |TERAATIESSKETCCNNGEL
2: Each client initializes w using the same set of random seed
3: for t = 1 + T do
>> '"' denotes the total number of global steps
4:
10 Client */
5:
parfor c c= 1 -
N do
N denotes the total number of clients
6:
if w t w
then
7:
P uu E R
8:
else
9:
20 w + desk, (Aw*11
desk;
Rh - IR de-sketch the change
10:
end if
11:
we u.
12:
for 1s = + do
u.u. + u k-k- Mocal V)((w))
end for
15:
Aw,(1) + w..k w'
Client e sends (t)( server
ske I2d Rhan sketch the change
17:
end parfor
1 Server #/
19: Aw <- 7gglobal Ee (Aw(()()))
! Awi E Rd
20:
Server sends A A to each client
21:
end for
22:
end procedure
We highlight several distinct features of our algorithm:
Communication: In each sync step, we only communicates low-dimensional sketched gradients, indicating a smaller communication cost per round. This property is particularly valuable in a small- bandwidth setting.
We emphasize that unlike the classical seetch-and-solve paradigm that decreases the problem dimension, algorithm applies sketching in each round, combined with de-sketching process which recovers back to the true gradient dimension.
De-sketch:':
Simple server task:: Server only needs to do simple averaging, indicating no need of trustworthy party as the server.
Decentralization: Our algorithm can be generalized decentralized learning settings, where local clients can only communicate with neighboring nodes. In this case, it requires ((diam) rounds to propagate the sketched local changes, where diam the diameter of the network graph.
4.1 sk/ /dek VIA COORDINATE WISE EMBEDDING
In this section, discuss the concrete realization of the /dekk, operators in Algorithm 1 through random sketching matrices. Note we should require any processed gradient desk; sky(g) to "be close" the true gradient g avoid breaking the convergence property of the algorithm. To achieve this, we first introduce the following property for broad family of sketching matrices, namely coordinate-wiz embedding (Jiang et al., 2021: Song Yu, 2021), that naturally connects with operators.
Definition 4.1 (a-coordinate-wise embedding). We say randomized matrix R E IR bame xd fying a-coordinate wise embedding if for any vector g, h E Rdd. we have ER-n(h R Rg]
satis-
and [h R R1 (h baketch |/ [
We elaborate the difference of our iterative sketch and de-sketch approach compared to classical sketch- and-solve approaches in Section 4.2.
4

---

Under review as a conference paper at ICLR 2022
In general, well-known sketching matrices have their coordinate-win embedding parameter being a small constant (See Section D). Note that if we choose h to be one-hot vector C₁. then the above conditions translate to Ex-n [R' Rg] and En-ul]B R Rg 2 I (1 11+
d d) 119112.
This implies that by choosing
sk: Rs E Ih Xd (sketching),
desk; Ry gax (de-sketching)
for any iteration 2 1, where R&'s independent random matrices with sketching dimension baetch. we obtain an unbiased skerching/de-skethhing scheme with bounded variance as state in the following Theorem 4.2.
Theorem 4.2. Let sky and desk, be defined by Eq. (2) using sequence of independent sketching matrices R. E R xd satisfying a-coordinate wise embedding property (Def. 4.1). Then the
following properties hold:
1. Independence: For different tterations, (ske, deske) 's are independent of each other.
2. Linearity: Both skę and desk; are linear operators.
3. Unbiased estimator: For any fixed vector h Rd, it holds (sk,
4. Bounded second moment: For any fixed vector E Rdd holds Fllldesk, (h))
(1 (1+0 a d/bstetc)) [12
We will use the above property to instantiate the convergent proof and communication complexity in section 5. We remark that unlike traditional sketching matrix R, one can intuitively think of matrix R as "de-sketch" matrix, it undoes sketching and recovers the sketched vector to original dimension.
4.2 SKETCH-AND-SOLLE VS SKEYCH--NN-DE--SEEEE
In this section, we provide brief discussion of the difference between classical sketch-and-son paradigm (Clarkson & Woodruff, 2013; Woodruff, 2014) and our sketch-and-de-sketee scheme. The general idea of sketch-and-solve is apply sketching matrix R to the entire problem, and certain black-box algorithm to solve the aketched-dowe low-dimensional version of the problem. Intuitively, sketching preserves the structure of the problem, therefore, the same algorithm can be exploited on smaller problem, and to achieve a 1 + guarantee. One downside of this method is the problem that is applicable needs to have certain structures. For example, is not clear that given non-convex objective, directly applying sketching will do any help.
In contrary, our seeech-and-de-sketdde scheme only applies sketching to certain key component of problem, for example, the gradient in a gradient descent method. Unlike sketch-and-solve, using sketch and de-sketch, we preserve the structure of the algorithm. This makes feasible wider range of applications, such as showing the progress of gradient descent non-convex objective, as we will show in appendix and G. One drawback of this scheme is gives a worse approximation guarantee (1 + O Maza )), but in gradient descent, this can be mitigated via choosing a smaller stepsize for compensation. In distributed setting, where privacy of communicated message and its size are main concerns, sketch-and-des ded--e- particularly valuable.
4.3 PRIVACY-PRESSERTIE SKETCHING VIA LOW-DIMENSIONAL NOISES
In this section, we discuss how to add low-dimensional Gaussian noise to make Algorithm differ- ential private. Consider gradient vector Ze generated via training of a client and another vector g/. that differs from ge by exactly one entry. Further, we assume this difference has a bounded magni- tude of y in terms of absolute value. The goal is to protect the sketched gradient, Rg.- Our strategy as follows: on line 16 of Algorithm 1, we add a random vector A, E h where each entry of Ag is drawn from (0, 2²) and with a 2 22 /d//////a///eeee//ee (logg1/)) (1/5),, then this modification on line 16 will produce (c, 8) differrenti private guarantee for the sketched gradient.
We remark this the most important step to preserve the privacy of the federated learning algorithm, since potential attackers might hack into single client and have access the sk, /dekk, operators for
5

---

Under review as a conference paper at ICLR 2022
each iteration. If they can further observe the communicated gradients from other clients, then the power of random masking with sketching is almost diminished, since they intuitively, they can de- sketch the sketched changes to obtain useful information. After adding low-dimensional Gaussian noises, attackers can no longer obtain useful information even they have the ske/desk, operators, which significantly improves the privacy of our system.
From an analytical perspective, adding this noise does not affect our analysis too much since it's sampled from a zero-mean Gaussian distribution, our estimator R_ (Rg + A.) is still unbiased estimator of vector g. it merely adds a variance term which can be factored into the variance of our un-modified estimator. Hence, in the analysis section, we present the theorems and proofs for the scenario where noises are not added. Similar analysis can be adapted to additive noise version.
CONVERGENCE THEORY AND COMMUNICATION COMPLEXITY
In this section, we analyze the convergence property of our proposed framework for smooth and convex objectives. Note the similarity shared by our framework and classical federated learning algorithms. We try to follow the existing analysis and focus on discussing the impact of the intro- duced randomness due to the sketching and de-sketching. We will show our approach enjoys benign convergence property and does not increase total communication at all.
5.1 SINGLE-STEP SCHEME
To start off, we consider simple scenario where the number of local steps K = 1. In this case, by the linearity of skę and desk, operators, the update rule can be written as
1+1 = w' - r)- (ske (V)("))
We remark that in the case of sk; and desk; being identity mappings, our framework is equivalent to distributed implementation of the vanilla gradient descent algorithm. Therefore, follow the classical analysis of gradient descent and have the following key lemma:
Lemma 5.1. If Assumption 3.1 holds and K = Denote == Mocal Mglobal- Then we have
El wl|lwt+ w" [la] S (1 np) Blllw' w0ll 2n n11 a) Elf(w') f(w }}
where w is minimizer of problem (1).
Proof. Note the update rule (3) implies
|| w² 112 = Il" w 1122 2n/(w² w", (sk + r/² l (V )))
Taking the conditional expectation over last synchronization, we have by Theorem 4.2,
(w w", (sk, [i] s (1 + a) [(())(
FF]] (w² w², Vf(
(sk
Combining with yı-strongly convexity and L-ssoothhess of f. we obtain
Ei]lw'+! 113 Fi] S ||wl - w01 2n(ww² - w", V + +1(++)))V
< (1 m//]l 2 w 11 27/(1 (1 + a)L) (s(w') f(w")).
Taking the expectation of both sides over F. we complete the proof.
Lemma 5.1 implies the introduced randomness from gradients only influence the second order term by a multiplicative factor 1 + a in expectation. Therefore, by scaling down the stepsize by a factor of ++a, we can obtain the exact same convergence guarantee as the vanilla gradient descent algorithm. For the strongly convex and smooth objective case, we obtain the following linear convergence.
1 Theorem 5.2. If Asssupption 3.1 holds with μ. > Let K and n == Mocal Oglohal S [[+a)L then have (w" -[(w")) < 1/2 [F[l w/ [12]] -
nuT where w" is minimizer of problem (1).

---

Under review as a conference paper at ICLR 2022
Proof. By the choice of stepsize and Lemma 5.1, obtain
Blllw" w' =12 S (1 T/16" BBIl - w "12]]--
Therefore, we have
B[f(w")- f(u')) Blllw" - w" - EB|| w0 w w0 l -uT
2
2
For the convex case, we consider the average of iterations and obtain the sublinear convergence. Theorem 5.3. If Asssuptiiin 3.1 holds with μt 0. Let K = and := Tlocal IIglobal S 2[1+a)L'
then we have f( f(ww)) S MI+IJ Blllw - w" [2]. where wt is a minimizer of problem (1) and wh 1 T+1 Et= w"
Proof. By the choice of stepsize and Lemma 5.1, we obtain r(s(w") - f(w") S 1B[1|wo w 12 R. B|]lw*t1 11]
Take the telescope summation over t 0, T. we have
T
E(f(w') - f(w")) f(w")
- 1 [B[ w" 11 B||lw++-- w0
(1211 - 17
1 E Billw w' ='
1=0
By the convexity of f we complete the proof.
We point out that in the case sk, and desk, being identity mappings, the parameter a reduces back 0 and Theorem 5.2 and 5.3 matches the convergence property of vanilla gradient descent exactly.
Further, above convergence results imply that comparing to vanilla gradient descent, our approach needs to shrink the stepsize by factor of O(a), thus enlarge the number of iterations by factor of O(a) to achieve desired accuracy. Therefore, using sketching matrices with dimension baketch- ours communicates O(bskechhdd /d-a) many bits in total compared to vanilla approaches. According to Theorem 4.2, we have a = (d/bbseuh)) for commonly used sketching matrices, implying our approach does not introduce extra communication cost at all.
5.2 MULTI-STEP SCHEME
Now we are ready to move on to general local step scheme. In this section, we assume Nglobal = 1. For notation simplicity, we denote ui:1 1 = ut - for t 2 2. We also introduce the following notations of the average iterates, iterates variance, local gradients and average gradients to help with the analysis.
N
N
N
1
Vik
Σ
t.k T
A.k == : Valluh
gth =
ge
N
c=l
Using the new set of notations, one key observation the average iterates satisfies
K-1
Mocal g L[k=o
Thoaal (4a desk, o sk,)
Σ g'-
v(t,)) (1,0)
We remark again if sk, and desk, being identity mappings, updates reduce back to the vanilla local gradient descent algorithm with K local steps.
By considering the distance to optimal solution ||æ** "" w1 have the following intermediate lemma parallel to Lemma 5.1. Due to the space limitation, we defer the proof to appendix, see Lemma F.6.
Lemma 5.4. If Assumption 3.1 holds and r7 == Mocal S 1
4F, then we have
B - - < (1 - (n)) - w w01 [E f(w")] 1.5mL B[
K-
1ul= aK
(AL > [B f(w") (ww)) 21 Σ B))
for any (1, (1,0), where w" is minimizer of problem (1).
7

---

Under review as a conference paper at ICLR 2022
Follow upon the above lemma, next step is to capture the quantity of the iterates variance Vi. observe that each round, we start off with yco = due to synchronization u u.. Then yr. can be viewed the accumulation of the variance of the next & local updates,
N Σ N
R-1
K-1
N
Σ
Mocal De - n 4. + Σ
Mocal g² nocal N
Σ
Σ
(g
De 1
Therefore, it naturally requires us to characterize V through certain measure of dissimilarity of local gradients. To achieve so, avoid the common Lipschitz assumption which only gives blur upper bound the difference of local gradients, but follow the approach Khaled al. (2019; 2020), which focus the quantity
def
Vfc(w")
that is always finite and naturally characterize the degree of heterogeneity of local objectives. And we have the following observation of the summation of iterates variance over a single round: Lemma 5.5. If Assumption 3.1 holds and Mocal
S 8LK- Then for any 2 0,
K-1
K-1
Σ vtk < 88horall LK2 K=
EfsTT* (f("))())) )) + Mhoca K2O
k=0
Combining Lemma 5.5 and Lemma 5.4, notice that by choosing appropriately small stepsize, the first term in upper-bounding Vt.k can be absorbed when we consider the average iterates over single round. Therefore, We can obtain the following convergence result for the strongly convex and smooth losses.
Theorem 5.6. If A'ssumpttion 3.1 holds with μ > 0. Mocal b(I+a)K
L E [ w/ "1]]2e "hhocaa + AvRicaal 1,2 03322
[[ [(w))
where w is minimizer of problem (1).
Proof. Telescoping sum up Lemma 5.4 k varies from to K and absorb the higher-order terms by the choice of the stepsize, we have for any 2 1,
K-1
Bl[[T w"
B w 11]
S
procal))
E Elil w" w01l2)
S LK3
Rearranging the terms, we obtain for any N 1,
w [|21 < (1 mMoocal Bl[l w1
[12] + +8 LK30?
implying
E|| F||l
Blllwo w" w01l2 112]e MMlloaa 81 L.3 0x/02/11 //..
We conclude by the L-smoothness of function f.
Corollary 5.7. Assumption 3.1 holds with μ puts an e-optimal solution w E Rd satisfying B[f(wT) =f(w") I by using O((LN/J) max(d, Vo²/(uc)) log(T. Elllw ((1l)())) bits of communication cost.
Then within Algorithm out-
We observe the same phenomenon as in the single-step scheme again, that compared to vanilla approaches, ours shrinks the stepsize by a factor of O(a), thus enlarge the number of rounds ap- proximately by factor of (ax). Since our approach only communicates Obskerch/ d) as many bits per round due to sketching, the total communication cost does not increase all for commonly used sketching matrices, according to Theorem 4.2.
We also point out that when x² (ud?), analysis implies a linear convergence rate of local GD under only dtrongly-covven and smooth assumptions, which new as far as we concern. We also have similar observation in the convex losses case, shown in the below theorem.
8

---

Under review as a conference paper at ICLR 2022
Theorem 5.8. If Assumption 3.1 holds with μr 0. Mocal 8(1+))KK
4 4B 4B[lw00 w"
Elf(w") )
321 LK20o?
Moca KT
where w² Algorithm
KT EE CK-1 wh is the average over parameters throughout the execution of
Proof. Telescoping sum up Lemma 5.4 as varies from to T and varies from to and absorb the higher-order terms by the choice of the stepsize,
B B w"
Blllw we
Mocal ΣΣ B[J(T'+h) [(w"]] + 81hocal To
Rearranging the above equation, we have
K-1
4 4E w w 12
ΣΣΣ
Elf - f(w")]
+ 323Mocal LK2
KT K=0
Mocal Mocal KT
By the convexity of we complete the proof.
Corollary 5.9. If Assumption 3. holds with μr = 0. Then Algorithm outputs an e-optimal solution का E I&& satisfying [[f f(w"((())))))))) S c by using [[E[[lw0 - w w0| N max (ax/ (aansLLocoo//eeee.. o,
bits of communication cost.
We compare communication cost with the work of Khaled et al. (2019), which analyzes the local gradient descent using the same assumption and framework. The result of Khaled et al. (2019) shows communication cost of O [BI]]
which is strictly no less than our results. This shows again our approach does not introduce extra overall communication cost.
w" w0 d L /
DISCUSSION
In this work, propose the iterative sketch-based federated learning framework, which only com- municates the sketched gradients with noises. Such framework enjoys the benefits of both better privacy and lower communication cost per round. We also rigorously prove that the randomness from sketching will not introduce extra overall communication cost.
Though our framework is built upon the local gradient descent algorithm and our theoretical discus- sion follows the analysis framework of Khaled et al. (2019; 2020), we emphasize that our approach and results be extended to other gradient- based optimization algorithms and analysis, including but not limited to gradient descent with momentum and local stochastic gradient descent. The key reason is due the sketched and de-sketched gradient R Rg is an unbiased estimator of the true gradient with second moments being a multiplier of || As the iterates approach the optimal solution, the second moments approaches correspondingly, resulting an exact match of the vanilla approach. Therefore, by scaling down the stepsize appropriately, we are able to recover the same convergence guarantee as the original gradient-based algorithms.
By simple modification to our algorithm with additive Gaussian noises on the sketched gradients, we can also prove the differential privacy of our learning system by "hiding" the most important component in the system for guarding the safety and privacy. This additive noise also does not affect the convergence behavior of our algorithm too much, since it does make the estimator biased, and the additive variance can be factored into original analysis.
Despite the benefits terms of privacy and communication cost, we point out our approach does have trade-off on computation complexity. Since we need to shrink stepsize and thus enlarge the number of iterations to achieve certain accuracy level, our approach requires (dd/baeeeh) as many computational cost compared to vanilla approaches. However, in aadaey-ann-commmmcatte focused distributed learning scenario, we hope this work provides a new solution and motivates future works.

---

Under review as a conference paper at ICLR 2022
Ethics Statement. This paper mainly focuses on the theoretical perspective of federated learning, and it proposes algorithm to improve the privacy of the learning system.
Reproducibility Statement. This paper contains several theoretical results, for discussions related to sketching, we refer readers to section D, for discussions related to the convergence analysis and communication costs of Algorithm I, we refer readers to section F and G. For discussions related to differential privacy, we refer readers to section H.
REFERENCES
Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson-lindensteeneee -indenstranusssss transform. In STOC, pp. 557-563, 2006.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments, Journal of Computer and system sciences, 58(1):137-147, 1999.
Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong. Subspace embedding and linear regression with orlicz norm. In International Conference Machine Learning (ICML), pp. 224-233. PMLR, 2018
Giuseppe Ateniese, Luigi Mancini, Angelo Spognardi, Antonio Villani, Domenico Vitali, and Giovanni Felici. Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers. International Journal of Security and Networks, 10(3):137- 150, 2015.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification, and local computations. arXiv preprint arXiv:1906. 1906.02367 2019.
Sergei Bernstein. On a modification of chebyshev's 's inequality and the error formula of laplace. Ann, Sci. Inst. Sav. Ukraine, Sect. Math, 144):38-49) 1924.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning, 2018
Christos Boutsidis and David Woodruff. Optimal cur matrix decompositions. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 353-362. ACM, https: //aaxiv..rg/ppf....... pttp:/pp////////// 1405. 7910, 2014.
Christos Boutsidis, David Woodruff, and Peilin Zhong. Optimal principal component analysis in distributed and streaming models. In Proceedings of the forty-e annual ACM symposium Theory of Computing (STOC). pp. 236-249, 2016.
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Mingzhe Chen, Zhaohui Yang, Walid Saad, Changchuan Yin, H Vincent Poor, and Shuguang Cui. A joint learning and communications framework for federated learning wireless networks. IEEE Transactions on Wireless Communications, 2020.
Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pp. 493-507, 1952.
Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pp. 81-90. https: / aariiiiii.. org/ pttp 6365, 2013.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aarreli Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. In Advances in neural information processing systems, pp. 1223-1231, 2012.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Anmual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006a.
10

---

Under review as a conference paper at ICLR 2022
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265 284. Springer, 2006b.
Hossein Esfandiari, Vahab Mirrokni, and Peilin Zhong. Almost linear time density level set estima- tion via dbscan. In AAAI, 2021.
Sergey Foss, Dmitry Korshunov, and Stan Zachary. An introduction to heavy-tailed and subexpo- nential distributions, volume 6. Springer, 2011.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Confer- ence on Computer and Communications Security, pp. 1322-1333, 2015.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients- how easy to break privacy in federated learning? arXiv preprint arXiv:2003. 14053, 2020.
Oana Goga and Renata Teixeira. Speed measurements of residential internet access. In Nina Taft and Fabio Ricciato (eds.), Passive and Active Measurement, pp. 168-178, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-225377-0
Uffe Haagerup. The best constants in the khintchine inequality. Studia Mathematica, 70(3):231- 283, 1981. URL http: http::/eedmmlllommm org doc / 2 8383.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in feder- ated learning. arXiv preprint arXiv: 1910. /4425, 2019.
David Lee Hanson and Farroll Tim Wright. A bound on tail probabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 4203):1079-1083, 1971.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-coneave games and its applications. In STOC, 2020.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 2530-2541, 2018.
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. Faster dynamic matrix inverse for faster Ips. In STOC. arXiv preprint arXiv:2004.07470, 2021.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977 2019.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5143. PMLR, 2020.
Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra. Privacy via the johnson--inddentrauss transform. Journal of Privacy and Confidentialityy 2013.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on hetero- geneous data. arXiv preprini urXiv:1909.04715. 2019,,
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4529. PMLR, 2020.
Alcksandr Khintchine. Über dyadische brüche. Mathematische Zeitschrift. 18(1):10-1116, 1923.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint /61iv:/610.05492 2016.
11

---

Under review as a conference paper at ICLR 2022
Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selec- tion. Annals of Statistics, pp. 1302-1338, 2000.
Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. COLT, 2019.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 60, 2020a.
Wenqi Li, Fausto Milletari, Daguang Xu, Nicola Rieke, Jonny Hancox, Wentao Zhu, Maximilian Baust, Yan Cheng, Sébastien Ourselin, M Jorge Cardoso, et al. Privacy-preserving federated brain tumour segmentation. In International Workshop on Machine Learning in Medical Imaging, pp- 133-141. Springer, 2019.
Xiaoxiao Li, Yufeng Gu, Nicha Dvorek, Lawrence Staib, Pamela Ventola, and James Dun- can. Multi-site fmri analysis using prrvacy--rreervingg federated learning and domain adaptation: Abide results. Medical Image Analysis, 2020b.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp. and Qi Dou. FedBN: Federated learn- ing on non-lID features via local batch normalization. International Conference on Learning Representations (ICLR), 2021. URL https: httpiaxxvvvvrr... abs 2202.00222. 120.20000 07.0076622 6763..
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint 1rXiv:1912.1280 2019.
Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar. Faster ridge regression via the sub- sampled randomized hadamard transform. In Advances in neural information processing systems, pp. 369-377, 2013.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficie learning of deep networks from decentralized data. In Artificial Intelli gence and Statistics, pp. 2273-1282. PMLR, 2017.
H. McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging. 02 2016.
Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing (STOC), pp. 91-100, 2013.
Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Sci- ence (FOCS), pp. 117-126. IEEE, https: //t./viviv//..///////.aa///aaavv wttpp//pppg/////////////eegeette 1002, 2013.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication--ffieee federated learning method with periodic averaging and quan- tization. In International Conference on Artificial Intelligence and Statistics, pp. 2021-2031.
PMLR, 2020.
Mark Rudelson and Roman Vershynin. Hanson-wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013.
Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of 47th Annual IEEE Symposium Foundations of Computer Science (FOCS), 2006.
Reza Shokri and Vitaly Shmatikov. ACM SIGSAC conference on computer and communications security, pp. 1310-1321. ACM, 2015.
deep learning. In Proceedings of the 22nd
Zhao Song and Zheng Yu. Oblivious sketching-baat based central path method for solving linear pro- gramming problems. In 38th International Conference Machine Learning (ICML), 2021.
12

---

Under review as a conference paper at ICLR 2022
Zhao Song, David P Woodruff, and Peilin Zhong. Low rank approximation with entrywise form error. In Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC), 2017.
Zhao Song, David P Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. In SODA, arXiv preprint 1rXiv:17044 1704.0826,, 2019.
Sebastian U Stich. Local sgd converges fast and communicates little.
arXiv preprint
arXiv:1805.09767, 2018.
Sebastian U Stich and Sai Pranceth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint 05350, 2019.
Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3(01n02):115-12,, 2011.
Hongyi Wang, Mikhail Yurochkin. Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni.
Federated learning with matched averaging. arXiv preprint arXiv:2002.0644 06440, 2020a.
Ruosong Wang, Peilin Zhong, Simon Du, Russ Salakhutdinov, and Lin F Yang. Planning with general objective functions: Going beyond total rewards. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2020b.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. When edge meets learning: Adaptive control for resource-constrained distributed machine learning. In JEEE INFOCOM 2018-IEEE Conference on Computer Communications, pp. 63 71. IEEE, 2018.
Zhibo Wang, Mengkai Song. Zhifei Zhang, Yang Song, Qian Wang, and Hairong Qi. Beyond inferring class representatives: User-level privacy leakage from federated learning. In IEEE IN- FOCOM 2019-IEEE Conference on Computer Communications, pp. 2512-2520. IEEE, 2019.
David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
David P Woodruff and Peilin Zhong. Distributed low rank approximation of implicit functions of matrix. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 847-858. IEEE, 2016.
Chang Xiao, Peilin Zhong, and Changxi Zheng. Bourgan: generative networks with metric embed- dings. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS), pp. 2275-2286, 2018
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient mo- mentum sgd for distributed non-convex optimization. In International Conference Machine Learning, pp. 7184-7193. PMLR, 2019a.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019b.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint IrXiv:I806.000 00582, 2018.
Wenbo Zheng, Lan Yan, Chao Gou, and Fei-Yue Wang. Federated meta-learning for fraudulent credit card detection. In Proceedings of the Twenty-Ninth International Joint Conference on Arti- ficial Intelligence (IJCAI), 2020.
Ligeng Zhu and Song Han. Deep leakage from gradients. In Federated Learning, pp. 17-31. Springer, 2020.
13

---

Under review as a conference paper at ICLR 2022
CONTENTS
Introduction
2 Related Work
3 Problem Setup
Our Algorithm
4.1
sk/desk via coordinate wise embedding
4.2
Sketch-and-Solve vs Sketch-and and-De-sketch
4.3
Privacy Privacy-preserved sketching via low-dimensional noises
5
Convergence Theory and Communication Complexity
5.1
Single-step scheme
5.2
Multi-step scheme..
6
Discussion
A Preliminary
16
Probability
16
Optimization Backgrounds
17
Sketching
18
D.1 Definition
18
D.2 Coordinate wise embedding
19
D.3 Expectation and variance
19
D.4 Bounding inner product
D.5 Infinite norm bound
25
E Analysis of convergence: Single-step scheme
28
E.1
Preliminary
28
E.2 Strongly-convex ff convergence analysis
29
E,3 Convex f convergence analysis
29
E,4
Non-convex f convergence analysis
30
k-step convex & strongly-convex fo analysis
31
F.1
Preliminary
31
F2 Unifying the update rule of Algorithm
32
F3 Upper bounding ||g..
32
F4 Lower bounding tk w0, ..
33
14

---

Under review as a conference paper at ICLR 2022
F.5
Upper bounding variance within K local steps Bounding the expected gap between T7' and w
34
F.6
35
F7 Main result: convex case
36
F88 Main result: strongly-convex case
38
G step non-convex f convergence analysis
39
H Differential Privacy
42
15

---

Under review as a conference paper at ICLR 2022
Roadmap. We organize the appendix as follows. In section A, introduce some notations and definitions that will be used across the appendix. In section B, we study several probability tools will be using in the proof of cretain properties of various sketching matrices. In section C, we lay out some key assumptions on local objective function fe and global objective function f. in order proceed our discussion of convergence theory. In section E, give complete proofs for single-step scheme. We dedicate sections F and G to illustrate formal analysis of the convergence results of Algorithm under local steps, given different assumptions of objective function f. In section H, we introduce additive noise to make our sketched gradients differential private and prove for specific AMS sketch matrix.
A PRELIMINARY
For positive integer we use [n]] to denote the set (1,2,...,,.. We use E|-] to denote expec- tation (if it exists), and use Pr[-] denote probability. For function we use Ö(f) denote If poly(log f). For a vector æ, For vector z, we use || == Σ, [a: to denote its & norm, we use || == (Ei= x2)2/²² to denote its &2 norm, we use ||~]| maxie[n]
[ to denote its foc.
norm. For a matrix A and vector z, we define ||^|| = Vx Ar. For a full rank square matrix A, A- to denote its true inverse. For matrix A, For matrix A, we use ||||| to denote its spectral norm. We use |||||r = (Ei,) A²2 to denote its Frobenius norm. We use AT to denote the transpose of A. We denote 1x=11 for E to be the indicator function which equals to I if x = I and O otherwise. Let ʃ A - and C A be two functions, we use f o to denote the composition of functions f and g. i.c., for any x E C, (f o (x) = f(((z)).
At denote its pseudo-inverse.
B PROBABILITY
Lemma B.1 (Chernoff bound Chernoff (1952)). Let X = X where X; = with probability
P: and X; = 0 with probability 1 - Pt. and all X; are independent. Let = E[X] = Σ Ps. Then
Pr[X 2 (1 + 5) S exp( 1/3),, Y6 > 0;
2. Pr X < (1 5) I exp(-6² 2/2), 40 <
Lemma B.2 (Hoeffding bound Hoeffding (1963)). Let X1, Xn, denote n independent bounded
variables in ba). Let X E X3, then have
2t
Pr[ E[X] 2 S 2exp
Db=1(b: - a.)2
Lemma B.3 (Bernstein inequality Bernstein (1924)). Let XI.... .n, be independent zero-mean random variables. Suppose that [X|] S M almost surely, for all Then, for all positive t,
t2/2
Pr Σ
x
S exp -
B[XJI + Mt/3
Lemma B.4 (Khintchine's inequality, Khintchine (1923); Haagerup (1981)). Let oe. on be i.i.d. sign random variables, and let 21, 2n be real numbers. Then there are constants C' > 0 so that for all t
Pr Σ z 2 111=1le] S exp(-CIP).
Lemma B.5 (Hisht-wright inequality Hanson & Wright (1971); Rudelson & Vershynin (2013)). Let x E 8n denote random vector with independent entries x, with E[r,] = and [xa] S K. Let A be an matrix. Then, for every 2 0.
Pr|p Ar -rEx TElxTAc Ax > t
exp(-cmin (f t/(3
Lemma B.6 (Lemma 1 page 1325 of Laurent and Massart Laurent & Massart (2000)). Let X ~ X2 be chi-squared distributed random variable with & degrees of freedom. Each one has zero mean and o² variance. Then
Pr(X -ko² (2Vkt +21000 exp(-t).
16

---

Under review as a conference paper at ICLR 2022
Pr[ko - X 2 exp(-t).
Lemma B.7 (Tail bound for sub-exponential distribution Foss et (2011)), We say E SE(o²,a) with parameters a > 0, a
if:
EleAX] S exp(A902/2), lKla < 1/a.
Let X E SE(o o)) and [[[] = then:
Pr[ n 2
min ,1/o))
Lemma B.8 (Matrix Chernoff bound Tropp (2011); Lu et al. (2013)). Let X be finite set of positive-semidefintte matrices with dimension d d, and suppose that
max
Amax (X) B. XEX
Sample (X1,-. Xn) uniformly random from X without replacement. We define pmin and pmax as follows:
Mmin = 72 Amin
E [X])
and Amax == 71 Amuax X~x
(X))
Xrex
Then
Pr Amin
X:) S (1 8)mmmin
S d. exp(p6d2 B) for E [0, 1),
i=1
Pr mmxx
X2) 2 (1 + M
S d. exep (-6² (Mmax/(4B)) for 2 0.
1=1
C
OPTIMIZATION BACKGROUNDS
Definition C.1. Let f Rdd + be a function, we say f is L-smooth for any x. y E Rd, we have
[Vʃ(x) ( S L|l - yl12
Equivalently, for any x, y E Rdd, have
f(v) S +()) (,,x,, + 2 ly x11
Definition C.2. Let f Rdd be a function, we say f is convex for any x, y E Rd, we have
f(x) f()) (a y, vf(y))
Definition C.3. Let f Rd + R be function, we say f is p-strongly-connex for any x, E Rdd we have
- -
Equivalently, for any E Rd,, we have
11y x11
f(0) 2 f(z) 2
Fact C.4. Let f: Rdd + IR an L-smooth and convex functtin, then for any x, y E Rd, we have
f(v) f(x)
x. V(()) + 2L -V(())
Fact C.5 (Inequality 4.12 in Bottou et al. (2018)). Let f .dd + R be a p-strongly convex function. Let x be the minimizer of f. Then for any x E Rdd, we have
1
f(x) f===((())==) < [Vf(2)]
24
17

---

Under review as a conference paper at ICLR 2022
D SKETCHING
In this section, we discuss the (a, B, 8), -coordinat wise embedding property we proposed in this work through several commonly used sketching matrices.
We consider several standard sketching matrices:
1. Random Gaussian matrices.
2. Subsampled randomized Hadamard/Fourier transform matrices Lu al. (2013).
3. AMS sketch matrices Alon et al. (1999), random {-1, per entry.
4. Count-Sketch matrices Charikar et al. (2002), each column only has one non-zero entry, and -1, +1 half probability each.
5. Sparse embedding matrices Nelson & Nguyên (2013), each column only has s non-zero entries, and each entry is V + vs
half probability each.
6. Uniform sampling matrices.
We list the definitions and results of above sketching matrices for coordinate-wist wise embedding in Table 1.
Table 1: Roadmap of the results for coordinate-wiee embedding
Sketching matrix
Definition
Expectation
Variance
Inner Product
Concentration
Random Gaussian
Definition D.2
Lemma D.11
Lemma D.I3
Lemma D.18
Lemma D.24
SRHT
Definition D3.3
Lemma D.11
Lemma D.12
Lemma 12.19
Lemma D.23
AMS
Definition D.4
Lemma D.11
Lemma D.12
Lemma D.20
Lemma D.23
Count-sketch
Definition D.5
Lemma D.11
Lemma D.14
Lemma D.21
Lemma D.25
Sparse emhedding
Definition 1.6,,).7
Lemma D.I1
Lemma D.I5
Lemma D3.22
Lemma D.28
Uniform sampling
Definition D.8
Lemma D.11
Lemma D.16
Lemma D.29
D.1 DEFINITION
Definition D.1 (k-wise independence). H {h [m] + [[]} is k-wise independent hash family if 4 is + ... is E [n]] and Vji, :3s [(].
1 [h(b)) i A ... Ah(ic) jul 1 NEW
Pr
Definition D.2 (Random Gaussian matrix). We say E puxn a random Gaussian matrix if all entries are sampled from (0, independently.
Definition D.3 (Subsampled randomized Hadamard/Fouriet transform matrix Lu et al. (2013)). We say R E TRbx bbxn is a subsampled randomized Hadamard transform matrix" if it is of the form Vn/bSHD, where E Rbxn random matrix whose rows are b uniform samples (without replacement) from the standard basis of R", H E pnxx is normalized Walsh- Haddm-d matrix, and D E B is diagonal matrix whose diagonal elements are i.i.d. Rademacher random variables.
Definition D.4 (AMS sketch matrix Alon et al. (1999)). Let has h2, ... ...,.,,,, .bo be randoom hash hashffucc tions picking from 4-wise independent hash family H {h [m]
1 {.). Then
R E Rbxn is AMS sketch matrix if set Rs,j hz(j).
Definition D.5 (Count-sketch matrix Charikar et al. (2002)). Let h [n] [6] be random 2-wise }1 be a random 4-wise independent hash function. Then R E bbxn is count-sketch matrix if we RR(g), = a(i) for all i [m) and other entries to zero.
independent hash function and a [n] > {-1, +1]
IIn this case, we require log he integer.
18

---

Under review as a conference paper at ICLR 2022
Definition D.6 (Sparse embedding matrix Nelson & Nguyên (2013)). We say R R is sparse embedding matrix with parameter s if each column has exactly 8 non-zero elements being =1//s uniformly random, whose locations picked uniformly random without replacement (and independent across columns) ii
Definition D.7 (Sparse embedding matrix II Nelson & Nguyên (2013)). Leth [n] x [b/s] be a a ramdom 2-wise independent hash function and a : [n] x [s] - + 1] be a 4-wise independent. Then R Rxxx is sparse embedding matrix II with parameter s if set R1j-1)//+h(--))
(i. j)/ for all (i. E [n] [s] and all other entries to zero."
Definition D.8 (Uniform sampling matrix). We say R. E Rbx" is uniform sampling matrix if it is of the form R - vn/bSD, where S E 5g is a random matrix whose rows are uniform samples (without replacement) from the standard basis of R", and D E BRxx is a diagonal matrix whose diagonal elements are i.i.d. Rademacher random variables.
D.2 COORDINATE WISE EMBEDDING
We define coordinate-wise embedding as follows
Definition D.9 ((a, 8, ccoordiine wise embedding). We say randomized matrix R R
satisfying (a, 3, 0) -coordinate wise embedding if
1. E
1g
R
Rh) =9" h,
2.
E
[[g
R
(
1191@211112
R~11
B
Pr R-11
9
R Rh - 9 Th 2 |191221111 S
Remark D.10. Given randomized matrix R E bg satisfying (a. 3, -coordinet wise embed- ding and any orthogonal projection R above definition implies
1. E IPR Rh] = Ph,
R~11
2. E
[PR [h)) < (Ph) + a:
b 11.1122
R~11
3. Pr R-TI
(PR Rh); (Ph)
vb llhll 8.
since Pl|| 1 implies PP.llll2 S 1 for all [n].
D.3 EXPECTATION AND VARIANCE
Lemma D.11. Let R E Rhx denote any of the random matrix in Desinition D.2, D.3, D.4, D.6. D.7, D.8. Then for any fixed vector Ro and any fixed vector g RR.", the following properties hold:
9 R
E R
Rh = g
Proof.
[g T RRR)] R-11
E
Rh)
E R
R Rhh Ih = -T.
Lemma D.12. Let R E 1abxn denote a subsampled randomized Hadamard transform or AMS sketch matrix as Definition D.3, D.4. Then for any fixed vector h R and any fixed vector g E IR,, the
following properties hold:
E l RR R-1I
TOTTRRAYS RA) h)² 119123 11112.
For our purposes the signs need only (log dl-w independent, and each column he specified hy a Olog d'j-wise independent permutation, and the seeds specifying the permutations in different columns need only be Oloog d) wise independent.
This definition has the same behavior as sparse embedding matrix for purpose.
19

---

Under review as a conference paper at ICLR 2022
Proof. If Ba[a] b, it is easy to see that
B b) = Ela²
2ab + = EBla² = b2)
We can rewrite as follows:
1 R Rhh2 - h1 R-ll
B
E R-1l
10 (R R -
It can be bounded as follows:
IE RM-l1
1(g (R R 1)6)?]
6 Σ
27
(Rg) (RKh) - gThz
=
R--l1
27
n
Rk
E
Ragh
R--I
jEIn/M()
n
E
RE
Right
Ri
Re Regg
R~ll
jE(NM{
M=1==1
d'E(niM(P)
E
Σ
R
Σ
R h
Σ
R g
Σ
Riggghh
1=1
k= i=1
b
91
+
gch
Σ
1=1
jE(m/M(
2
11
where the second step follows from R², = 1/b, 4k, E [b] x [n]. the forth step follows from
E Re. R 5 + 0 only if = Y, = k k' or = jj. = 8', h: = k, the fifth step follows from Rg and Rx, are independent if + and I2 12 = 1/b, and the last step follows from
Schwartz inequality.
Therefore,
2
R-1 1g R Rh)² (g hT])
E llg (RT R 1)h) 1111211112 R-n
Lemma D.13. Let R E Rbxn denote random Gaussian matrix as in Definition D.2. Then for any fixed vector h E Rn" and any fixed vector E IR.", the following properties hold:
(9 T R Rh) < (g T1)² + 3 11911 11
E R
Proof. Note
[g R Rh)3]
R-11"
E R-ll
Ru.gg
Right
k= Tml
j=l
b
b Σ
= E
Rk.gg
Σ
Rughy
R
Σ
Rw Joy
R-
A=1 1=1
1=1
M=1 1=
==1
20

---

Under review as a conference paper at ICLR 2022
" n
b n +
E
Σ
E ΣΣ IIIEE (M))
Red R selerrh
R
R-n
p=1
R2 R.
ΣΣ
jE
Σ
R R2 Ra
jE
hy
hhh
b
+ Σ = }E
Σ
L +
Σ
Σ PE|n|\
gehgghh by + b jE(N/Mb
Σ Σ
ghiggh
\) 1
where the third step follows from that for independent entries of random Gaussian matrix, E Ry RR * only 1. k * = j. j'. or k = K, =- or 3. k= K.i i i' === or k W. i= j + d'== j". or k, i= # j. the fourth step follows from B[R = 1/b and E [ = =3/b², and the last step follows from Cauchy-Sehward inequality.
Lemma D.14. Let R E bbx denote a count-sketch matrix as in Definition D.5. Then for any fixed vector h E IR" and any fixed vector R", the following properties hold:
3
10 R Rh) S (g h))² 111
R~n
Proof. Note
E R-ll
[gg
R R
27
n Σ
b
n
E R-1I
Rk Σ
Rk
1=1
n
E
Rk.i
Σ
Rkgghj
Σ
Σ
Rie gr
R~ll
1=1
J=1
k=IN==
5'=1
E R-1l
Σ
Σ
R R gethggie
+
Σ
1= k'E(b])(A) (k) 1=1 PelMMi
ΣΣ Σ
n² Ri
+
k=1 i=1 jE(r](()
A= i= rE(n]((
Σ
jE(N|((
he +
Σ g
PEjnjKi
Σ
Σ
Σ
Σ
h +
Σ
ghigghh
1=1 jE(n](()
1=1 rE(n]\()
JE
21

---

Under review as a conference paper at ICLR 2022
3 = + 7 1
where in the third step we are again considering what values of k,,',,,''' J. that makes E[Rg, R Ra v Rr & O. Since the hash function o(-) of the skench matrix is 4-wise independent, vk, k', when i i + + jr, or i = = $ j' (and the other symmetric cases), we have that RR,, RE. Re, Re = 0. Since the count-sketch matrix has only one non-zero entry in every column, when & * k', if = i' or = j' or j = i' or j = j'. we also have BRR,, Ry x Rx jr] 0. Thus = = = J'. 3. k K.i- i= i' f = -j' or 4. k = W. j * 1=
only need to consider the cases: 1. k + W. i = # i' j', jj. or 5.
or k W.
k == = i j + = j. And the fourth step follows from E(R 1/b and El R 1/b, and the last step follows from Cauchy- Schwartz inequality.
Lemma D.15. Let R E Rbx denote a sparse embedding matrix as in Definition D.6, D.7. Then for any fixed vector h E 18" and any fixed vector g E IR",, the following properties hold:
2 2. E [99 R. Rb) S (a 1)² + b 11111 1 R-ll
Proof. Note
E R-11
[(9 T R Rh)?]
27
b
E R-1l
Ra.
Ruillss
1m 1=1
j=1
b Σ
n2
11
b
n
11
E R-ll
Ri j=1
Russhs
Ry sry
A=1 1=1
k=1
E
R Re
Σ
gichi Σ
R Rh
R~ll
jE(m]((()
ΣΣ
Rh RS Riihige
Rr. +
ΣΣ
R2, Ra. f gihagghe
4 :f
WogfR Light"
Σ Σ KAK
R2 R2g o
Σ Rh + Σ
hy + 1
Σ Eithgg + Egps"
nh +
Σ
+
Σ Spp
gchaghho +
1 Σ ghh
b
b
$
< (9 h) 6 |
where the third step follows from the fact that the sparse embedding matrix has independent columns and 8 non-zero entry in every column, the fourth step follows from [[ = 1/b, [ = 1/(bs), and R inequality.
a(a-1) 6(-1)) 3. Vk # k and the last step follows from Cauchy-Schware
Lemma D.16. Let R E h denote a uniform sampling matrix as in Definition D.8. Then for any fixed vector h E I2" and any fixed vector g E RR" the following properties hold:
[9 R Rh 2 < (9 h)² + " 111
2. E R
Proof. Note
E R-1
[g R Rh)a
22

---

Under review as a conference paper at ICLR 2022
27
E R-II
R
Rk
j=1
E
BRi
Reiglej
Rie gi
Ri sihg
RM-ll
f=1
ΣΣ Rk of
ΣΣ
E R~ll
KOEN ip!
b 91 h
Σ
(b 1)m
Σ
(n 1)b
s (g h)² + 1191
where the third step follows from the fact that the random sampling matrix has one non-zero entry every row, the fourth step follows from E E[R Re = (/nnnnnnnnnn 1)6?) for k * W, * if and EIRg = n//b.
Remark D.17. Lemma D.16 indicates that uniform sampling fails bounding variance some sense, since the upper bound give here involves n..
D.4 BOUNDING INNER PRODUCT
Lemma D.18 (Gaussian). Let R E Rxx be a random Gaussian matrix (Definition D.2). Then we have:
olog(n/0) (())
Pr max (R Rx,)1 i#j
vb
Proof. Note for i + j. Rr Ri, No0, (b) are two independent Gaussian vectors. Let zμ
Rk, and 2 = (Rr,s, Rez). Then we have for any |>| < b/2.
E A
X2/22 I cxp(\2/b²),
where the first step follows from 2g 1 (R + R2.j)² + 1 (R Rk.j)² (Q1 Q2) where Q1 Q2 ~ x2. and B[eAQ] = VI-2x for any Q x²
This implies 24 SE(2/b2, 2/b) is sub-exponential random variable. Thus, have Σ 24 SE(2/b, 2/b), by sub-exponential concentration Lemma B.7 we have
Pr[[ s 2 exxp(_bt)
for 0 < Picking t Vlog(n2/6)) we have
Pr [[RL,, Raii1 > cVlog(n/0) vb
$ 8/n2.
Taking the union bound over all (i,j) E [n] [r]] and i + j. we complete the proof.
Lemma D.19 (SRHT). Let R E bbx= be subsample randomized Hadamard transform (Defini-
tion D.3). Then we huve:
Pr max (Rr,s, Regil Vlog(n/5)
S (
vb
17j
23

---

Under review as a conference paper at ICLR 2022
Proof. For fixed i # j. let X (Ru,,, Ra,gl | E Rbx2 Then X X Ek= Gk. where
RK.
Gx = [Rx.s Ray! [Bs,s Re.jl = RK.
Note the eigenvalues of G are 0 and and B[X" [X] b. [[G[]] 1a for all & [6]. Thus, applying matrix Chernoff bound B.8 X X have
Pr Amax (X XX) S {
S 2 eexp (-Pb/2) for l [0, 1), and
Pr Amax((X
Tx)= 2 + t
< 2 exp (-tb//8 for t t 0.
which implies the cigenvalues of X X are between [] 11-1,1+2 with probability - 4exp (-
So the eigenvalues of X X - Iz are between [-t, l] with probability 4 exp D Picking
c/log(n/0) have Jb
t
Pr | x - -221 eVlog(n/0)
8 n2
vb
Note
(Ra,s, Ra.j)
x X -12 = RR Reg))
whose spectral norm is KR,, i R. Thus, we have
Pr [ (R. oy c//lg(n/0) Vb
S 8/nn²
Taking union bound over all pairs (i,j) [m] x [n] and + j. complete the proof.
Lemma D.20 (AMS). Let R E RRxx be a random AMS matrix (Definition D.4). Let {or i [m]] be independent Rademacher random variables and R E hxx with RR,, = R,Rs,, Vi E [n]. Then
we have:
Vlog(n/0) vb
Pr max (Ro,is Rmji1 $$j
(())
Proof. Note for any fixed + J. R.,i and Rig are independent. By Hoeffding inequality
(Lemma B.2), we have
Pr
RR 21 s 2cxp (- E (
212
s 2c -P6/2
Choosing f = /2oog(2n2/08 /8)/ Vb, we have
Pr (R.t. Rl,,)1 2log(222 /5) vb <
5 n
Taking a union bound over all pairs (i, [m] x [n] and + j. we complete the proof.
Lemma D.21 (Count-Sketchh) Sketch), Let R Bixn be count-sketch matrix (Definition D.5). Let (ai, E [n]} be independent Rademacher random variables and R E Rbxx with Ro.5
R,Ra,,, Vi E [n). Then have:
max (R. R 1
Proof. Directly follow the definition of count-sketch matrices.
24

---

Under review as a conference paper at ICLR 2022
Lemma D.22 (Sparse embedding). Let R R be sparse embedding matrix with parameter 8 (Definition D.6 and D.7). Let (0s, E [n]} be independent Rademacher random variables and R E Rxxn with R = 3, E [n]. Then we have:
eVlog(n/0) S (
Pr
max 1f1
(R. R1
vs
Proof. Note for fixed + j. Ru,, and R., j are independent. Assume R.,; and Rr, has u non-zero elements at the same positions, where I u S s, then by Hoeffding inequality (Lemma B.2), we have
21
Pr,, Ro.s)) 2 S 2exp
S (2exp(-(2((au))
(4)
Σ ii G ---)))
Let v /2u/ (on))o/222//00 /n)² have
Pr [Ra.i, R.,i) 2s- log 1og((n2200))0 /0)
S Pr [(Ru, R.,)1 2us log((n)) (2n2/8)
S 88/n²
(5)
since u S s. By taking a union bound over all (i.j) E [n]] x [n] and i # j. we complete the proof.
D.5 INFINITE NORM BOUND
Lemma D.23 (SRHT and AMS). Let R E Rbxx denote subsample randomized Hadamard trans- form (Definition D.3) or AMS sketching matrix (Definition D.4). Then for any fixed vector h E IR" and any fixed vector g E R,, the following properties hold:
log 1.5
(n/8)
Pr. R-m
RR R Rh) (g (g)
|
< (0()-
vb
Proof. We can rewrite (g RT Rh) (g Tg h) follows:, RRT
(0 RR (g hh- =
ge (R,,i, ReS) + Σ geh R Re,111 -1)
1=
jE(m]i
Σ Σ
JE(NJV
where as's independent Rademacher random variables and Re,s o. Ro,is Vi [n], and the second step follows from |R,,, 112 = 1, Vi E [n].
We define matrix E Raxx and B E Raxx as follows:
A g.hy (Rr R.,),
Vi E [n]. [n] Vi E [m]. [m]
Bij gıhy max (Ra,y, R.g..). P$$
We define A E RR*x to be the matrix A Rex with removing diagonal entries, applying Hason- wright inequality (Lemma B.5), we have
Pr[lo T A 2 =
exp( exp(-cmin(62//44113. 7/|A4/
We can upper bound ||A and ||
|| < ||
< |A|[F
< |B|F
||
max (R.,i, Ra.i)l (#1
25

---

Under review as a conference paper at ICLR 2022
$ 119122 ||/||22 max (Rx, Rr,
where the forth step follows from B is rank-1.
For SRHT, note R has the same distribution R. By Lemma D.19 (for AMS, we use Lemma D.20) with probability at least - (6), we have
Vlo(n/0)
max (R, R,
ifj
vb
Conditioning on the above event holds.
Choosing = 1|ll2 ||ill2 log -og..((n///)) (n/6)/ /bb, we can show that
log 1.5 (n/d)
Pr (g R Rh) (g TT) 2 11gll2 |All2
S 000).
vb
Thus, complete the proof.
Lemma D.24 (Random Gaussian). Let R E bR denote a random Gaussian matrix (Defini- tion D.2). Then for any fixed vector R and any fixed vector g R". the following properties hold:
log (n/8)
Pr [g TOTHT R Rh) - (g h)1 (g)
119122 |
s 006).
Roil
Proof. We follow the same procedure proving Lemma D.23.
We can rewrite (R
R Rh) - (g) T h) as follows:,
TR - (g Σ
Σ
gely (Re,s, Ress) + Σ Cih -1)
1=1 jE(n|V
Σ
Σ
giligai NoiRo,s oj Res) + Σ gihh R2, 1).
(6)
:= jEIN
where or's are independent Rademacher random variables and R has the same distribution as R. To bound the first term En (o. R),, we define matrix A E R and
B E R as follows:
AI, gihy (Ri,i,
Vi E [n]. [m]
B1, = gihg max (Ru,s', , Re
E [n].] E [m]
743
We define A E RRax to be the matrix A E Ruxn with removing diagonal entries, applying Hason- wright inequality (Lemma B.5), we have
Pr[loT T A 2 7] < exp( exppt=cminn/3///4//1 T/
We upper bound || and ||
|| < |
< ||][
|||r
||g||2
||/l||2
max ifj
(Re, Rl,
<
|
||Al|2
max (Ra,i, Re,;)l
where the forth step follows from B is rank-1.
26

---

Under review as a conference paper at ICLR 2022
Using Lemma D.18 with probability at least 1 (()), have
v Vlog(n/o)
max (Ra
R.sil S
vb
Conditioning on the above event holds.
Choosing
||
[1lll2
log log..((n//))) (n/6)/ we can show that
log
1.5 (n/6)
Pr
Σ
Σ jEINJY
Johy (o,
2 l1lll2 ||A||2
S {
(7)
Vb
To bound the second term Ei (:h RR, 1), note that R,, Applying Lemma B.6, we have
x5 for every E [n]]
Ro.ill 1/2
cvlog(n/0)
Pr
S 5./n.
vb
which implies
Cv log(n/o)
Pr Σ gi
|R,,, - ||9|2/|/1122
S (
(8)
vb
Plugging the bounds Eq. (7) and (8) back to Eq. (6), we complete the proof.
Lemma D.25 (Count-sketch). Let R Bhxn denote a count-sketch matrix (Definition D.5). Then for any fixed vector h E I."" and any fixed vector IR"" the following properties hold:
Pr R-JIT
[ Rh)
TT)l 2 log 100(1//)lllllalbbll S ((6).
Proof. We follow the identical procedure as proving Lemma D.23 to apply Hason-wright inequality (Lemma B.5).
Then note Lemma D.21 shows
max 243
[R, R. $
Thus, choosing cl|g|12 |hill log(1/5), we can show that
Pr [I(a T RTT Rh) (g) h)] 2 clgl22 ||4]/2 (o)(1 s 6.
which completes the proof.
Lemma D.26 (Count-sketch 2). Let R E RRbxn denote a count-sketch matrix (Definition D.5). Then for any fixed vector h E Rh and any fixed vector R=, the following properties hold:
[ -000-9991 (g
1
191211bll2 < O
R~ll
Proof. is known that a count-sketod matrix with = 22 rows satisfies the (c, 5, 2)2 moment property (see e.g. Theorem of Woodruff (2014)). Using Markov's inequality, (e, 8, -JI moment property implies
[g Rd Rh) - To T)) 2 (199 < O R-ll
Pr
where
Vb5'
Remark D.27. In LP solver, we need = 1/ 1/poly(n), thus Lemma D.25 is stronger than Lemma 1)26
27

---

Under review as a conference paper at ICLR 2022
Lemma D.28 (Sparse embedding). Let R. R denote sparse-embeddine matrix (Defini- tion D.6 and D.7). Then for any fixed vector h E IR and any fixed vector g E R". the following properties hold:
log 1.5 (m/5)
3. Pr R
[0 R Rh) [n)
1 & ((6).
Proof. We follow the identical procedure proving Lemma D.23 to apply Hason-wrigh inequality (Lemma B.5).
Then note Lemma D.22 shows with probability least 1 we have
R R. R) cVlog(n/0)
max j
Vs
Conditioning on the above event holds, choosing cl11912- ||A||2
log. (L/6)),
we can show that
c' d'log (m/80)
Pr [g [gT R Rh) (g (g]1)]2
||A|2
S 0
Thus, we complete the proof.
Lemma D.29 (Uniform sampling). Let R E Rbx denote uniform sampling matrix (Defini-
tion D.8). Then for any fixed vector Rn and any fixed vector R", the following properties hold:
3. T R Rh) (9 (g S (1
n 71+ 1912211412
where I C [ni] be the subset of indexes chosen by the uniform sampling matrix.
Proof.
We can rewrite (g R. Rh) (g) h)) as follows:,
R Rh) (g h) Σ Σ
gohy (Re,,, Re,s) Σ
gehh((I RR,,,1
i=1 JE(n|is
1=1
n
gilu
Σ gihu.
where the second step follows from the uniform sampling matrix has only nonzero entry in each row.
Let I C [n] be the subset chosen by the uniform sampling matrix, then |R.,, n/b
for i for
I and
[R,, | = 0 for i E [m] I. So we have
[( R Rh)- - (g (g] Σ gehil n
-1)
Σ giht
iEl
xE(n]\
" < (1 11s1/2111112
E ANALYSIS OF CONVERGENCE: SINGLE-STEP SCHEME
E. PRELIMINARY
Throughout the proof of convergence, we will use F, to denote the sequence w,-1, Wc-2..... Wip- Also, we use y shorthand for //global Morll-
28

---

Under review as a conference paper at ICLR 2022
E.2 STRONGLY-CONVEX f CONVERGENCE ANALYSIS
Theorem E.1. Let f: R. + IK satisfying Assumption 3.1 with > 0. Let w" E IRd be the optimal
solution to I and assume sk/ sk/desk functions satisfying Theorem 4.2, Suppose 1l Aglobal Mocca has the property that (Ita]L' then
-1 f(w")((=))))))))){))) (1- (1-))) (f(w")- f(w"))
Proof. We shall first bound f(wtt)) - f(w():
+ L
f(w f(w²) S(w - w', vf(w"')
1w -
w0
2
= (desk, (Aw v vf (w²))
+
| (Ai"
2
1
(gglobal desk,
ske (Mocal VSc(wo Vf(w'))
N
N
|| desk,
ske (Nocat
Vff(("))))
Nglobal Mocal (deskr (V (V v
+ (Tglobal Mocai)3 ||desk, (sk; f ))
where the first step uses the L-smoothness condition of f. and the last step uses the linearity property of sk/desk functions.
Taking expectation over iteration & conditioning on F; and note that only #1+1 depends on random- ness at t, we get
[ (w s(wx') | [i]
Lad
S (sk ( (Vf(w)))) Fi), Vf(w")) +
(l]ldesk(ssc(V((()))) Fil
2
(VS(w'), Vf(w")) Lx2
(1 a) [VV[("
|V
2
un) (f(w") f(w"))
where the second step comes from the fact that desk, (s),(h)) is an unbiased estimator for any fixed
E IRd and the bound on its variance, the third step comes from rj S (1+a))+ and the last step comes from Fact C.5.
Upon rearranging and subtracting both sides by f(w"), ). we get E[f(w(-1)] fw=") Fi] < (1 un) (f(w") f(w")) Note that if we apply expectation over F, on both sides of Eq. (10) we can get
(10)
[[](w (ww) s (1 - -m7) (B[[(w))) - (ww")
(11)
Notice since 1 - um S this is contraction map. if we iterate this recurrence relation, will finally get
B[S(w s(w0((')))))))))))) s (1- -mm) (f(w)) (ww"))
(12)
E.3 CONVEX ʃ CONVERGENCE ANALYSIS
Assume f is a convex function, we obtain convergence bound terms of the average of all pa- rameters.
29

---

Under review as a conference paper at ICLR 2022
Theorem E.2. Let f : F > R satisfying Assumption 3.1 with 0. Suppose sk/dess //sesk functions satisfying Theorem 4.2. If 1 == Ngllball 'occal S 2(1+a)E then
E Blll w w
[lf(w") f(w")]
(T+1)
where w = T+1 El w' and w² E Rd is the optimal solution.
Proof. We shall first compute the gap between w and wt:
|| w" 12
= I/we desk, (A - w011
= W 77 desk, (ske [f - w"11
= 1| w n²² ||deskr (ski (V (V ())1)) - 21 (w' -u'-"",, dsk
(13)
By unbiasedness of desk, o skt, we have E[(w' - "", (deskr(ski (V](w") )) Fi] = E[[w" -w, VI(ww')) Fi]
(14)
Taking total expectation of Eq. (13) and plug Eq. (14), we get
B[]lw*+1 ++1
=" 1|
Fil
B[llw* w"ll 112
Fil + 11² BE[ldeskk (sk, (V ))) Fi] - 2n Bl w", VS(wo)) [F]
S B[]lw* 112
Fil + 17² (1 + a) B||| V (w) _/ Fi + 2n- Bi(w"= - w', vf(w()) Fi]
B[Ilw* w 112
Fi] +f (1+ a)) ( Fi. + 2n. (Ij(==[(- s(wo) Fi] (15)
where the second step follows from the variance of desk; o skę, and the last step follows from the convexity of Taking the expectation over F, and re-organizing the above equation, can get
2m Elf(w') f(w")) <
Billwo w" [[] w" "1 + rj² (1 +1+00 a) EII (l
Blllw' w 1| [[[l
w 11 + 1
a. 2L Bff(w')) f(w"))
where the second step follows from the convexity and L-smoothness of f. Rearrange the above inequality, we have
(2n r (1+a) 2L) [E[f(w") - f(w")] s 1Bll w01l - E[]l w013
Note 7) II+a]I have
17 n-E(f("") f(w") S Billw* w" w1 Elll w' 1011
Sum over all T iterations, arrive
T
Σ
Elf(w') - f(w)(( < w" B[]lwT+ w" 111 Blll w" [12)
(16)
1=0
Let = / It w² denote the average of parameters across iterations, then by convexity of f.
we conclude:
Blf(w>) f(w")] Billwo w'
(T 11)
E.4 NON-CONVEX / CONVERGENCE ANALYSIS
Next, prove version when is not convex function, due to loss of convexity, no longer bound the gap between [w") and f(w"), but we can instead bound the minimum (or average) expected gradient.
30

---

Under review as a conference paper at ICLR 2022
Theorem E.3. Let f : BR - IR be an L-smooth function (Def. C.I) and sk/ sk/desk functions satisfying
Theorem 4.2, let w E R. be the optimal solution to f. Suppose 1] : M/Lcall Ngglobal S (I+a)L' then
min EE[7]
11 v (T + (EIs(w")] - -f(w")
Proof. Note that the only place used strongly-conver assumption in the proof of Theorem E. is Eq. (9), so by the same analysis, we can get
Blf f(ww((()))))))))))) Fil - ? -IVVf("))
Rearranging and taking total expectation over Frr we get
E B ( - (f
Averaging over all T' iterations, get
T
2
E| B v
-BI
+ (T
1)
1=0
2
(B[f(w")] H[f(w")))
(T + 1)
2
nT (B[s(w") - f(w)))
This implies final result:
2
min eE(T]
V f( (
11 I n/T + 1)
[B[ f(w"))
Remark E.4. Notice due to the structure of sk/dksk functions, i.e, their variance is bounded in terms of true gradient, the convergence rate depends completely on the temm (1ta)E. If it's a con- stant, then we essentially recover convergence rate of gradient descent. On the other hand, if [I+o]T, S 1. then we get similar convergence rate as SGD, One clear advantage of our sk/ desk VT
functions is they don't i introduce extra noise term as in SGD, since we can choose appropriate step size to absorb the variance term.
F k-STEP CONVEX & STRONGLY-CONVEX fc ANALYSIS
F.1 PRELIMINARY
In this section, we assume each fa satisfies Assumption 3.1 and Niglobal = For notation simplicity, we also denote u. u 1ig-1,K-1 for 2 2. Definition F.1. Let (t, E {1, T T+
K 1}, define the following terms
for iteration kt:
i.k plit
Tl.k
w"
be the average of local parameters and distance to the optimal solution,
N
gih
(u
ge
be the local gradient and its average,
N
Vik
A.k
/ T
=
N
o=
31

---

Under review as a conference paper at ICLR 2022
be the variances of local updates.
1 N N
o²
to be a finite constant that characterize the heterogeneity of local objectives. We also define the following indicator function: let 1 E R, then we define {a=1} to be
[] if==l,
1 (x=1) = to otherwise.
F.2
UNIFYING THE UPDATE RULE OF ALGORITIM
Lemma F.2. We have the following facts for utt and it:h:
u0.0 T
ui. u 1
Mocal ge k-1-11 Vk 2
K-1
T = =Tth Jih-1 Mocal gik-1 + L[k=o) Mocal (La desk, o skz)
g
1-),),, v(t, k) * (1,0)
where Ia: R + Rd is the identity function.
Proof. First two equation directly follows from the update rule of Algorithm 1.
For 1,2, K - 1, taking the average of the second equation we obtain:
T
k-
Mocal
For = and 2 2, we have
K-1 desk, (ske(
0. w¹ 1-100
gi-litt)
Mocal
1=0
K-1
K-1 Σ
K-1
w²' 11.00
Mocal Σ
g 1-1 1,2 + Mocal
g 1,, Mocal
desk,
Σ g
(1)1,))
1=0
1=
K-1
1,K
Miccal
g 1,K
Mocal
(Ia - desk, o skr)
Σ (11
1=0
Combining above results together, we prove the third equation.
F.3
UPPER BOUNDING |igh*11
Lemma F3. Suppose for any E [N]. fe: Rd R is convex and L-smooth. Then
< vt2 + 4I( - f(w)))
Proof. By triangle inequality and
inequality, we have
l k
1 f ) V
< 2|| k -( +
where the first term be bounded
L.k
Vecluk Σ
N [VS((tt> fo fa(
32

---

Under review as a conference paper at ICLR 2022
N L
1 T/.111
N
and the second term can be bounded as follows:
IV 112 VV vf(("))1
S 22(((TT f(w"))
where the last step follows from that f is L-smooth and Fact C.4. Combining bounds on these two terms, we get
2L
l 11
Σ Muth x1 + 2 w"
S v + +I[(f(7(:k) - -(ww))
F.4 LOWER BOUNDING (u'-k w², ..
Lemma F.4. Suppose each Sa satisfies Assumption 3.1 with μ 2 then
(u w", 9²² 2 f((ltt) s(w") 2 2
ll
w
Proof. We will provide a lower bound on this inner product:
( w. gg...)
T w", vf((u()))
N
suffices to consider each term separately:
fc(((())) (T u th w³, v.((((()))
= (Tz u. Vfc(u + (w w", ((((
The first term can be lower bounded via T-ssoootness::
L ( woth V(((w(")) 2 fc( fc(ub())
| w
221
The second term can be lower bounded via convexity:
(u w", V(f(u="))) 2 fo(ut²) - fo(w") + 1/2 fllit* -w0 w0112
Combining these bounds and average them, we get a lower bound:
L w¹, gt.gghk>
Σ (fa(Th))) - -
I 11
L
1 1u
w= (
2
N
2 N
Σ (fc(Tt.k)) -f((w))) vii + 11
"l
w=
2
2
= f(('kk) f(ww)
1. Vink
11 |
w011
2
33

---

Under review as a conference paper at ICLR 2022
F.5
UPPER BOUNDING VARIANCE WITHIN K LOCAL STEPS
Lemma F.S. Suppose each fo is convex and L-smooth. Assume Thoral S 8LK
1
Then for any L 2 0,
K-1
K-1
v 88ucaal LK2
(
+ 4m R²0²
0=
k=0
Proof. By Lemma F.2, we know V 0 for any t 2 0. Consider .1, K 13, we have
N
Vik
1
T
N
1 nocal 1
11
noccl ge w.0 +
N
1=0
Noxal
ge
N
l1ght
N
1=0
nocas K
N
k-1
(17)
N
where the second step follows from Lemma F.2, the last step follows from g being the average of gh... By Cauchy- Sauchy-Schwartz inequality, we further have:
ligh 112 < 31 Vfa(a"')) + 3lIV//(("'")) V(a(w")] 3/ Sel 3 S 33 112 + 6L(ff(T()t - fc(w")++++) (w 0 vfc(w"))) +3]V)
where the last step follows from applying L-smoothness to the first and second term. Averaging with respect to
1 N
1 < 3T221. + - - [(ww)) + 30
Note that the inner product term vanishes since Plugging back to Eq. (17), we obtain
N E. Vi((w") = vs(w") = 0.
nioeat
K
Vik
1g
N
k-
Mocal
K
E(3 + ( + 30
Summing up above inequality as k varies from to K 1,
K-1k-1
vlk S Niocat Σ
K
(3L + +6L(((T") - f(w")) + +302)
K- --1
< viccal K
Σ
Σ
VL + +6L(S(T*)) [(w")) + +002)
K=
= 3
La 2
Via + Gr LK2
Σ
(f( - f(ww)) + 3o K30
1=0
==0
34

---

Under review as a conference paper at ICLR 2022
Rearranging terms we obtain:
K-1
K-1
(1-3mocal 3acca k2
Σ
vik I 67 LK² Σ
(f(a"tt) ffw")) )) + +3h K 002
-
k=
1=
Since Moccc
we have
3 L3 2 2.4 implying
SLK
K-1
Σ Vik S 8yhocal IK2
( f(w))) + 4mccall Ka0
F.6 BOUNDING THE EXPECTED GAP BETWEEN T. AND w
Lemma F.6. Suppose each So satisfies Assumption 3.1 with μ 2 If sk/desk satisfying Theo- rem 4.2 and Mocal I aL. then for any (t, k) # (1,0), we have
E El tk =11 $ (1 - pmmoccll El ih
w" 1|
Mocal L L Mocal E[f(z((k-1) - f(w")]
2
K-1
K-1
Ta 2T.
+ 4T,
E[ - -
1=0
==0
Proof. By Lemma F.2, we have for any (1, + (1,0),
K-1 )
u k n² 11- Mocal c + 1 [k=0)
Mocal (Ia desk, o ske
Σ 1=
g'-1,
Therefore, denoting h1' = (Ia - deske o ske) ( (2 9 g(-1.)). we have
|| w $12 = | w² Mocal gik-1 + ((k= Mocal 1/1l2
1 b-- w² + mocal |1g" 112 Mocal ( t k- w" g/ k
Mocaal 0k=0) (z/ w" h²) 2 (m=0) (gghh-1,1") hh)
+ nocal (x==0 |14'112
(18)
Note by Theorem 4.2, we have:
Eskesk h, E Bllkks (sk, (n)) S (1 + a) ||Al|2
hold for any vector h. Hence, by taking expectation over Eq. (18),
Blllu**
[3] [ w [[] + nicclll F 1. F.]
2Mocal [B( "" Iz 1> [F]] + 1 (k=0) Tocal 1[
Note that since E[h" Fe] = 0, so the two inner products involving ht vanishes.
Since
K
E 1[[141/1
B[I[(Ta desk, o sk,)
1. 11
K-1
< a B[]
Σ
1,4
1=0
K-1
< aK
Σ
1=0
Taking total expectation, we have
B w² [1]
35

---

Under review as a conference paper at ICLR 2022
I El| hh
w0 w01121 + Mocal
Bilg" -1ll""A-1113 1
Mocal B[ .. (..(h-1))
K-1
[w==) nocal ak Elllg- 1, 11
I E| k 1 w0 1112 + Mocal
+ 4L(f(( V
- f(ww)))
L prR-1 + 1 1 11
MMcaa El E[f(T( f(w0)
K-1
+ 0k=0) nocal ak
E(21,2t-12 1, 4I((f(u - f(w=)))
1=0
< (1 (moloos) ) B1ll=t w'
[2 + Mocal L (1 + M)cal -B(
Moeaa (1 2) [[
f(("")
K-1
K-1
+ [k=0) 'hocal
aK
(2r²²
E(V 1.0] 4L
Σ Bis(a' 1.1) - fwm)))
where the second step follows from Lemma E.3 and Lemma F.4. Since Mocal S 41, we have
3
E T
w= 1121 S (1 (molccl)
w" 111 Mocal L E[V L
nocal Elf(w' f(w"))
1-1
R-1
+ 1 (R 21,
Σ
El
1. + 4L
Σ
B[f(T' 1.1) - -(0)--(("))]
1=0
1=
F.7
MAIN RESULT: CONVEX CASE
Theorem F.7. Assume each fe convex and L-smooth. If Theorem 4.2 holds and Mocal
K[+o]LK
4E[ww w"
Bls(w²)) f(1o"() 1
32 LKK22
Mocal KT
where Wº Algorithm
EE EkEO wh is the average over parameters throughout the execution of KT
Proof. Summing up Lemma F.6 as t varies from to I and k varies from 0 to K 1,
E| u
T
+1,0
w"
1|
Elllw"
"1
T
K
T K
3
Mocal
L
B
- Mocal
- fww")]
2
1=1
k=
k=
10==0) nocall aK K 21.
B 4L
B[f(T"..) - fwo)))
K=0
3
T K
T K-1
2 Mocal
L
B - Mocal
E[f(T'->) f(w")]
1=1
k=0
T
K
T K-1
+
2
K
2T2
4L.
- (((''"))s(w'))))
t=1
i=0
1=0
K
3
Mocal L1
T Σ
K-1
Moocal (1 4mocal
Σ
Blf(w - f(w")
0=
36

---

Under review as a conference paper at ICLR 2022
T R-
T K-
Mocaa
E
nocal
B B[f(zt - [ww))]
2
t=1
k=0
t= k=0
1
< MMocal
Mmoraal LK²
B[f(T(".) - f(w")) + Amoen k3
nocal
Blf(T(
f[ww)]
t=1
t=1 k=
T
K
S /occcl
1
Σ
s( 8hhcall LK
where the fourth step follows from Mocal ranging the terms, we obtain
SaLK the last step follows from Mocal
SLK
Rear-
4 I [1 ==
Σ E
B
f("")
+ 32 LK20²
KT
MocaL
k=0
Finally, by the convexity of we complete the proof.
Now we are ready to answer the question: how much communication cost is sufficient to guarantee [[f(w") f(w")] S e? we have the following communication cost result:
Theorem F.8. Assume each fe is convex and L-smooth. If Theorem 4.2 holds. Ld Led : bits of communication cost, Algorithm I outputs optimal solution w" satisfying:
With
0 Billw w N max
ow/11)
- se
where Th
RT E EL Ek Ek-'TLiA
Proof. To calculate the communication complexity, we first note communication only happens in sync steps. Specifically, in each syne step, the algorithm requires ([N bits of communica- tion cost, where batetch denotes the sketching dimension. Therefore, the total cost of communication given by O D(NDsketch)) T). To obtain the optimal communication cost for cootimal solution, we choose T, K, Mocal and blcetch by solving the following optimization problem:
min T.K. Bekeeschh
Nbsketch T
s.t.
0 Mocal
8(1 (1+
E EEllw00
w0 113
Mincal KT
32 nocal T.K202
d 2 baketch -(-))
21
where d the parameter dimension and the last constraint due to Theorem 4.2. Above constraints imply:
8 SE[[|w 0 T
1
1
KToeaal min
nocal
8(1 + a)
80
Therefore, when e II+ the optimal solution is given by
Kiotcal 8(1 8)1+a)L' T 64E w wn [31(1 LLL
baketch = =0
and the corresponding optimal communication cost is O Blll" 11LLdd
37

---

Under review as a conference paper at ICLR 2022
when
o² (I+a)+E* the optimal solution is given by
c T 80 V L
64 G
w w
Daketch =0
K Moocal
3//2
and the corresponding optimal communication cost is O Blll BBOVINd
ac
Combining above two cases, the optimal a is given by O(d), and the corresponding optimal com- munication cost will be O[Elllw w" [| max{ Ld LvL
63/2 }).
F.8
MAIN RESULT: STRONGLY-CONVEE CASE
Theorem E99, Assume each Sa is p-strongly convex and L-smooth. If Theorem 4.2 holds and Mocal
B[+a)LK'
[[f(w f(w")] 2
Elll"
w= "11l Thooaal T
+ L 0²/PL /p.
L2K300
Proof. Summing up Lemma F.6 as k varies from 0 to K - 1, then we have for any 2 1,
K
K-1
E [
7 110
w
El
w= w²1l2)) (1 pmoocal
Biil t.
w (121)
k=0
3 Mocal
2
L
E[v
Mocal
Σ k[ - [[ww]]
K-1
K
K-1
+
1ęk=0 H
nocal
2L
E[ + 4L Σ -((()))))(ww")))
- f(w")])
k=0
i=0
K
K
3
2 Mocal
I
Mocal
[f - [ww)]
k=0
k=0
K-1
K-1
2 + Moral aK 222
Σ
E +
4L
Σ Elf(T'+) -f(w"))
K-1
K
= Mocal L(
2ocalaa
ElV4,
Mocal(1
4Mocala
Bif(T** - f(w")]
2
km0
kmm
K-1
K-1
< 2 L
B
2
Mocal
Elf(T - -[(w")]
k=0
k=0
K-1
K-1
< 2mocal L (8 LK2
E[f(T! - f(w")[ + ArRocal/3 kk
Σ
[[ f(w"))
Mocal
K-1
<
4 Mocall
Σ
El - f(w))] + Mmccal IK3d0
k=0
where the fourth step follows from Mocal ranging the terms, we obtain
SaLK the last step follows from Mocal S SLK Rear-
1
E +1.0 w0ll
< (MMoaa) Billu'' w² w01 + Smica 3K3 L
implying
B|]l - w01 Snio LK330 02/14 S (1 pMocal [E w0113 |1 Snioaa LK /²/H).
Therefore, we have
[ [[]l w/ w11
T.K30² T.K30² T. /11 < (1 mmocal )² (Blllw> w01 S.
38

---

Under review as a conference paper at ICLR 2022
Bl|lw w w=112e umocca -MMocca
Finally, by L-smoothness of function f. we obtain
B[s(w"+3) [(w"[[ v B s+1
Bll - w"1Bße pyoooall + +4hoocal L²² 2
Theorem F.10. Assume each So is pestrrongyy convex and L-smooth. If Theorem 4.2 holds. With log( - bits of communication cost, Algorithm outputs an e-
O LN max/d, v d2 # optimal solution w" satisfying:
pe
-((ww))-(wv) S..
Proof. To calculate the communication complexity, we first note communication only happens in syne steps. Specifically, in each syne step, the algorithm requires ((N bits of communica- tion cost, where baketch denotes the sketching dimension. Therefore, the total cost of communication given by O baketch, To obtain the optimal communication cost for e-optimal solution, we choose T, K, Mocal and Skktth by solving the following optimization problem:
min
baketch T
T. T.K. Miooro Sakntch,
1
s.t.
Mocal S
8(1 + L)
L E Blll
w" 122le" -mooal $
4m L LK 0² /
o
0
d d2 baketch
where d is the parameter dimension and the last constraint is due to Theorem 4.2. Above constraints imply:
log( L LE w0 -w" 11 Mocal I mind
1
T2
potolcal
8(1 + L) 2LK V
2K
Therefore, the optimal value is given when K = 1. When 2 given by
16lI+ay the optimal solution is
a²
8(1 + = 8(1 a
L TE [ w0
Mocal
log(
baketch = -
1
and the corresponding optimal communication cost is O LNd log( LEIl "11 )).
when
< 16(++a) the optimal solution is given by
1 μe
2Lo
2
L E
baketch 0 1 w
Mocal 2Lo
T
113/2
log
and the corresponding optimal communication cost is O
LLNd a/ Ve
log(
LE
E t w 21))
Combining above two cases, the optimal is given by (d), and the corresponding optimal com- munication cost will be O LN max
g2 pe
log( BB]l| -
G kTST NON-CONVEX f CONVERGENCE ANALYSIS
In this section, present convergence result for non-convex ʃ case in the k-llocal-step regime. In order for the proof to go through, we assume that for any c E [N] and any w E IRd, there exists universal constant G such that
[a)wll G.
39

---

Under review as a conference paper at ICLR 2022
Throughout the proof, we will use Fg to denote the sequence Wt-1, w4-2.... Wp. Also, as a shorthand for Ngglobll Mocal
Note that in k-local-step scheme, the average of local gradients is no longer the true gradient, there- fore, we can no longer bound everything using the true gradients. This means it's necessary to introduce the gradient norm upper bound assumption.
Lemma G.1. Let f I - R satisfying Assumption 3.1 and sk/ /eske functions satisfying Theo- rem 4.2. Further, assume Mocal S 2T.K Then
[VV + n- L.L.KK2 G² (Meaaa + 2. 2 a)
[[ s(w') Fi) < 'lglohal
Proof. We start by bounding f(w f(w²) without taking conditional expectation:
f(w(+1)- - f(w))
s (w w², v.(ww)) + L
| w0 112
L
(deski (Aw'), (
|lesk (Am')
L - A+ B
2
where
K-1
= (gglobal deski
ske
Mocal vf((u(())) vf(w"))
k=
N
K
B MMgiobal desk?
skr
Mocal
((((((())))
N
k=1
Bounding E[A Fi]
Using the fact that skt/ /desk, are linear functions and E[desk, (sk, h,
we get
N
K
1
E[A Fij =
(Tglobbll
Mocal
Vfclu( vf(w'))
N
c=1
k=0
Mocal Vic(u Va((w") + V(o(w')), V((w())
Nglobhal
N
N K-1
=
Tgllobal
[V + Tgllobll T/loccl
fc(( V.f(w'), vf(w))
km
suffices to bound the inner product, notice for k = O, the inner product is 0, so assume k 2 1:
(VSa(ul - V.a(w'), V[(w") < [VVSc V(((w"))l 1| [V
L. || - - w/1l2 | f((')))l
(19)
where the gap between uf and w can be further expanded:
| w' [|2 | *
Mocal
fe
k-
< Mocal
V fc (u 1
1=0
40

---

Under review as a conference paper at ICLR 2022
S Mocal k G
(20)
Plug in Eq. (20) to Eq. (19), we get
(V.clu(")) V.l(w") Vf(w"))
L Mocal k G²
Recall that 77 = Nglobal Nocal Put things together, we finally obtain a bound on E[A
Fi]:
K K-1 E
E
A
FiL Tglobal
V ( (1) + Moccl L
k). G2
R=0
< Iglobal
(w l2 Mocal L K2 G2
(21)
Bounding B[B Fil Using the fact that / linear functions, we get
B Igglbbll Moral
desk, (skr (ske(V (Vl(( ))
N2
k=0
N
K-1
S 2
Moocl
N2
K
||deskr (Sssss (VeC(u
km0
K
N
K-1
||desk (sk, (((()()))
N
k=0
Using variance bound of desk; (ske we get
N
K-1
B
S
[V
N
-
k=
K-1
K
< 1 N
(1+a).
Σ
Σ
G²
k=
2 K2 a)
(22)
Put things together Put the bound on B[A| Fi] and the bound on E[B Fil, we get
Fi
L 1. (1+a) G²
?global |Vvf(w))] + 1 Mocal L. L.K.GO
K2
K2 G² (Mocal 2 (1+a))
Nglobal
Theorem G.2. Let f RR. R be L-smooth. Let w² E Rdd be the optimal solution to I and assume sk/desk functions satisfying Theorem 4.2. Then
min KE(T]
1
(B[ + Mocal LK3G2 (Mocal + 2/ (1 + +a)
7
(T+ 1)/glbbll
Proof. By Lemma G.I, we know that
+1)( Fi] f(w*) S Nglobal
f +n. K2 G2, (Nocal + " -
Rearranging the inequality and taking total expectation, we get
E|| V |
[E[f(w*)] E[f(w(+1)) + Mocal LK [oocal + 17 -7. (1+ +a))
iglobal
Sum over all T iterations and averaging, we arrive at
41

---

Under review as a conference paper at ICLR 2022
(B[f(w")] [[[ + Mocal LK2 (Mocal + 2 (1 +aaa
Mylobal
(BIS(w")] - f(w)) + Mocal LK3 (Toocal + 2. -1+ +a)
+ Miliobll
2
H DIFFERENTIAL PRIVACY
We define (c, diffferentia privacy Dwork et al. (2006b;a) as
Definition H.1. Let é, be positive real number and A be a randomized algorithm that takes dataset as input (representing the actions of the trusted party holding the data). Let im) denote the image of A. The algorithm A said to provide e, o-differential privacy if. for all datasets D₁ and D2 that differ on single element (i..,, the data of one person), and all subsets S of im(
Pr(A(Di) E S) exp(c) Pr(A(D2) E 8
where the probability is taken over the randomness used by the algorithm.
We state a lemma from prior work Kenthapadi et al. (2013),
Lemma H.2 (Kenthapadi et al. (2013)). Let E (0, 1/41 and e > O. Let Y and Y' be points in Rd such that || 12 2 I w. Then for any D C Rd, and any Å drawn from (O, o where
Awe -1 Mog(118) the following inequality holds:
+ e A
Throughout this section, we assume that for any gradient Je and any one-entry perturbation g' of ge, the magnitude of the one-entry perturbation upper bounded by y.
Let R. E I. haaaa Xd denote our sketching matrix.
Let Y', Y',' E harsh, Let g, g' _d such that g and g' differ by exactly one entry and the magnitude of this difference is bounded by y. Let Y = Rg and Y' = Rg'.
We demonstrate how to pick the corresponding variance of noise for AMS sketch. We remark that for other sketching matrices where entries are bounded and hence its spectral norm is bounded, one can run similar argument obtain such results.
Fact H.3. If R an AMS sketching matrices, then
Va/b < |R]|| S vd/Vb.
Proof. Recall that each entry of an AMS sketching matrix is J hence its max or column L norm is d Recall that max row or column & norm is upper bound on the spectral norm, hence Vb we know that || [|||
On the other hand, we know its spectral norm is lower bounded by its max row or column & norm, hence,
< d
Vb"
| 2
| Vd/b.
Put things together, we have
Vdlb |R| S va/Vb.
Putting it all together, we have
Lemma H.4 Let A E Rhanh denote the noise vector that sampled from Gaussian distribution
(0, (b) with o 2 4 buins 1 then we have Rg + A is (e, (eiff--iffeeetttall private.
42

---

Under review as a conference paper at ICLR 2022
Proof. By Lemma H.2, it suffices to to bound | 122 Note that
|| Y' = |Rg Rg 1|
R||| l1g g 1l2
d l1g g 1l2
baketch
d bkktth
7.
This means if we pick a 2 Av bisa 76 -1 differential private.
Vlog(1/5)) then our sketched gradient with noise is (e, 8)-
43


Reviews:
[{"review_id": "soidK7Uos4Z", "reviewer": "Reviewer_YCQM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**A. Novelty in the update aggregation mechanism:**\n\nA1. The idea of using random matrices to reduce communication complexity in federated learning is not new at all. See, for instance, the following papers (which the authors seem to be oblivious to):\n\n   i) Suresh, A. T., Felix, X. Y., Kumar, S., & McMahan, H. B. (2017, July). Distributed mean estimation with limited communication. In International Conference on Machine Learning (pp. 3329-3337).\n\n   ii) Mayekar, P., & Tyagi, H. (2020, June). RATQ: A universal fixed-length quantizer for stochastic optimization. In International Conference on Artificial Intelligence and Statistics (pp. 1399-1409).\n\n   iii) Chen, W. N., Kairouz, P., & Özgür, A. (2020). Breaking the communication-privacy-accuracy trilemma. In advances in Neural Information Processing Systems (pp. 3312--3324).\n\n  iv) Agarwal, N., Suresh, A. T., Yu, F., Kumar, S., & Mcmahan, H. B. (2018). cpSGD: Communication-efficient and differentially-private distributed SGD. arXiv preprint arXiv:1805.10559.\n\nThe lack of comparison of the author's proposed scheme with any of these papers is astonishing and is definitely warranted for a fair understanding of the authors' contribution. \n\nA2. From my understanding of the papers mentioned above, there is nothing that the authors propose in their aggregating algorithm(Section 4) that wasn't already known. \n\n     a. For instance, both i, ii, highlight, and crucially use the fact that when the updates are processed using certain random matrices, the coordinates of the processed vector have small absolute values; a property amenable for efficient vector quantization. The authors of this paper, too, point out a similar property in Definition 4.1.\n\n      b. Similarly using $R^T$ to \"de-sketch\" the sketched update has also been highlighted in these papers.\n  \n\nA3.  I don't see the point behind definition 4.1, since the authors don't seem to exploit this property to build better communication protocols. In particular, since convergence guarantees seem to rely on only the second moment bound in T 4.2, something as unsophisticated as uniformly sampling $b_{sketch}$ coordinates would (and scaling appropriately and setting other coordinates to $0$) would give the same guarantees as sophisticated sketches (precisely the same as in T 4.2). What is the point of these sophisticated sketches then? This does not come out in the paper at all. \n\nAs I pointed out in A2., properties similar to Definition 4.1 have been highlighted by many papers since 2017. The rationale behind highlighting such properties in these papers was to further exploit such properties for efficient vector quantization.  It is pointless to use these sketches, without exploiting them to build efficient vector quantizers.\n\n\n **B. Presentation and clarity**\n\nB.1 The authors can significantly improve the presentation and the clarity of this paper. The paper has many ambiguities and typos in its current form, and, frankly, it is far from being ready for publication.\n\nB.2 In  a 43 page research paper whose main goal is to reduce the communication complexity of federated learning, it is astonishing that not a single line is used to describe the overall quantization procedure.\n\n Perhaps the author meant to use the default 32 bit (64 bit) precision to transmit each scalar. Even this is important to state explicitly. Of course, if this is indeed the case, then what is the point of using sophisticated sketches (See point A.3 for more details).\n\nB.3 The parameter $\\alpha$ is never defined. This parameter crucially shows up in convergence results. ( After going through the proofs, I could understand this was the variance blowup parameter. Nonetheless, it should have been highlighted in the first place.)\n\nB.4 It is only in the discussion section that the authors point out that their convergence results build upon the work of Khaled 19. In my opinion, this should be explicitly stated in Section 5 and highlighted, where the convergence results are presented. \n\nB.5 There are several inconsequential typos and grammatical mistakes throughout the paper. Thorough proofreading of the paper should be able to fix this.\n\nB.6 It is disappointing that there are no labels to identify the parts in the appendix as proofs of the results presented in the main paper. Given the lack of such labels, the appendix section is extremely difficult to navigate through.", "summary_of_the_paper": "The paper studies the application of linear sketching algorithms to reduce the communication complexity in federated Learning problems. In particular, the paper proposes that the clients send a low-dimensional linear sketch of their updates to the server. Convergence rate of local SGD when deployed with such a method for aggregating the updates are discussed for various function classes. Finally, the paper also discusses a method for integrating differentially privacy guarantees in their method.", "summary_of_the_review": "GIven the lack of novelty in the paper's main algorithm (A.2), the lack of comparison with other published works using similar approaches (A.1, B.4), the fact that authors themselves show a lack of understanding of the motivation behind using sketches (A.3), and multiple presentation issues (B.1 - B.6), I  recommend the paper be rejected.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "X_I4xuPUxw", "reviewer": "Reviewer_RjL4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Federated learning has recently become a popular framework for training machine learning models. Reducing the communication cost of federated learning is an important problem. However the contribution of this paper is incremental. First, combining sketching with federated learning has been studied by several existing papers (see comment 5). Also, the paper doesn't provide any empirical results and the theoretical part is also on the weak side. Here are the details:\n\n\n1. Some notations of different sections are inconsistent. For instance, the paper uses $a$ to denote the value of coordinate-wise embedding in section 4.1, but uses $\\alpha$ instead in section 5 and appendix. I suggest the authors check the notations in the paper to increase the readability of the paper.\n\n2. The theorems in section 5 only require Assumption 3.1 holds, but I think they also require theorem 4.2 holds since their proofs use the property of the sketching matrices. In addition, I'm confused with the proof of Lemma F.6. The inequality below Eq. (18) says $E[dest_t(sk_t(h))]\\leq (1+\\alpha)||h||^2$. However, Thm 4.2 only tells us $E[dest_t(sk_t(h))]\\leq (1+\\alpha d / b_{sketch})||h||^2$. The paper should provide some explanation on why it can remove the  $d / b_{sketch}$ term?\n\n3. I'm also confused with the proof of Corollary 5.7 and 5.9 (Thm F.8 and Thm F.10). In the last sentence of the proof of Thm F.8 says \"the optimal $\\alpha$ is given by O(d).\" Since $\\alpha$ is the value of the coordinate-wise embedding of the sketching matrix, how to let $\\alpha$ be O(d)? The proof of Thm F.10 faces the same problem.\n\n4. For Thm 5.6 and 5.8, $\\eta=1/(8(1+\\alpha)LK)$ is not enough to guarantee $w^T$ converge to the $w^*$ since the last term in the bounds won't decrease when the number of iteration increase. I think $\\eta$ should be related with $T$ or $\\epsilon$.\n\n5. It seems that the clients use different sketching matrices for different $t$. How to guarantee that all clients use the same sketching matrix in each round without communication?\n\n6. The following papers also adopt sketching to reduce the communication cost of federated learning. I suggest the author discuss the difference between those papers and this work.\n\n\"Communication-efficient Distributed SGD with Sketching\", NeurIPS 2019. \n\n\"FetchSGD: Communication-Efficient Federated Learning with Sketching\", ICML 2020.\n\n7. I also suggest the author perform some empirical evaluation to show the effectiveness of the proposed method.", "summary_of_the_paper": "This paper proposes a novel federated learning framework where the client only submits a sketched gradient to the server and de-sketches the average gradient received from the server. The proposed framework can preserve the privacy of the data as well as reduce the communication cost. The paper theoretically analyzes the convergence rate and shows that the proposed method requires less communication cost than existing methods.\n", "summary_of_the_review": "The paper lacks empirical results and the theoretical analysis is somewhat weak. Thus I recommend to reject the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "T4KO7mQP9x", "reviewer": "Reviewer_ujZn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n1) The paper considers an important problem of addressing both communication cost and privacy concerns in the federated learning setting.\n\n2) The paper makes several interesting technical contributions in the federated learning setting. In particular, the proposed sketching/de-sketching based learning algorithm is simple yet effective (as demonstrated by the analysis in the paper).\n\nWeaknesses:\n\n1) There is significant room for improvement in the presentation of the paper. The paper is filled with typos (see below) and many statements need to be paraphrased to effectively communicate the intended meaning. \n\n2) Even though the paper introduces privacy as one of the main focus points, it briefly discusses the privacy guarantee of the proposed method in Section 4.3. The authors should at least present a formal statement/results outlining the privacy guarantee. Moreover, the significance of considering two gradient vectors that differ in the single coordinate is not immediately clear. Shouldn't the authors focus on the two gradient vectors resulting from two local datasets that differ in a single data point? Please add a more detailed discussion around this.\n\n3) In Section 4.3, the authors justify presenting the convergence results for only a noiseless setting. However, it appears that variance of the noise added to the gradient with d. How does such a large noise affect the convergence results? It would be interesting to present the results that take the presence of added noise into account.\n\n4) The authors have provided a pretty extensive supplementary. It would be nice if the authors can connect the supplementary with the main text with more references to the supplementary. \n\n5) The authors discuss the issue of increased computation due to the increased number of iterations at the end of the paper. Please also consider discussing this issue earlier, e.g., in the introduction. \n\n6) There is scope for improving the discussion of related work. The statements like \"...no work addresses both challenges simultaneously as far as we [are] concern[ed]\" are not clear to the reviewer. For example, there is this prior work (https://arxiv.org/abs/1805.10559) that explores the issue of communication cost and privacy.\n\n7) Could the authors comment on their claim that they don't increase the communication cost. As far as I can see, the authors only show that the communication cost remains the same in *order-wise sense*. Please consider modifying the relevant statements accordingly. (Some empirical results that support the authors' claims will be valuable here.)\n\n8) The paper considers a gradient descent style algorithm where all clients participate in each round. Could the author comment on how their proposed solution should be modified for the setting where only a subset of clients participates in each round.\n\n9) Please define $\\Pi$ in Definition 4.1\n\n10) In Section 4.2, please elaborate on \"(1 \\pm \\epsilon) guarantee\". \n\n11) Please consider paraphrasing the discussion in the second paragraph of Section 4.3 more precisely.  \n\nSome examples of typos:\n\n1) page 1, '..the amount of data to communication between...' --> '..the amount of data to be communicated between...'\n2) page 1, '...is one of the most important the key...' --> please drop either 'the most important' or 'the key'\n3) page 2, 'Fl' --> 'FL'\n4) page 2, '...a central server update...' --> '...a central server updates...' \n5) page 2, '...three unique challenge...' -->  '...three unique challenges...'\n6) page 3, '....applications in numerical linear.' --> '....applications in numerical linear algebra.' ?\n7) page 4, '...we only communicates a low-dimensional sketched gradients.' --> '...we only communicate low-dimensional sketched gradients.''\n8) The authors use both 'Section' and 'section'. Please consistently use one of these. \n9) page 6, '...since they intuitively, they ...' --> '...since they...'\n\n[There are similar typos in other places. Please proofread to fix those.]\n", "summary_of_the_paper": "This paper proposes a sketching-based federated learning algorithm to address the communication and privacy concerns in the federated learning setting. In the proposed algorithm, each client projects its local update (gradient) to a lower dimension via a sketching matrix before communicating the update to the server. The server aggregates the sketched local updates from different clients and communicates the aggregated update to the clients. The clients then de-sketch the message received from the server to update their local model. \n\nThe paper shows that if the sketching matrix satisfies the \"coordinate-wise embedding\" property, then the proposed algorithm leads to provable convergence for smooth and convex objective functions. \n\nThe paper also discusses the issue of privacy and proposes to add Gaussian noise to the sketched gradients to claim differential privacy of the resulting learning algorithm.", "summary_of_the_review": "Overall, the paper explores an interesting and timely problem. The paper presents a simple and effective scheme that has provable performance guarantees. However, there is significant room for improvement to make the contributions of the paper clear. Especially, the discussion around privacy guarantees needs to be improved. The authors also need to discuss missing prior work on communication efficiency + privacy for federated learning.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-YTWjeYM1Q0", "reviewer": "Reviewer_NaBa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Let me first summarize the main idea of this paper. The idea is conceptually simple, it uses a JL sketch to reduce the dimension of gradient, and since this *projected* gradient has large correlations with the original gradient, one can prove the convergence. \n\n\nStrength. I found it interesting to combine sketching with federate learning. The idea is conceptually simple but no one explores it before.\n\n\nWeakness. There is no experiments, and the total communication cost does not decrease.", "summary_of_the_paper": "The paper proposes a sketching approach to reduce the communication cost of federate learning, and prove the convergence of their proposed method for convex function. By adding gaussian noise to the gradient, it can also guarantee different privacy.", "summary_of_the_review": "---------------------------------\nPost rebuttal:\n\nI have read author's response as well as other reviewer's suggestion. I still think the paper is of value at certain aspects. But as other reviewers pointed out, I suggest the authors include a more detailed discussion on related work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies federated learning with various sketching techniques used for communication. 

The main concerns from the reviewers are: 

1) the presentation can be improved; 

2) the novelty and related work section is not satisfactory since there have been papers on sketched federated learning; 

3) there is no numerical study to validate the efficacy of the method. 

I suggest the authors to take into consideration the feedback from the reviewers in the revision of the paper.
Decision: Reject