Recycling Model Updates in Federated Learning: Are Gradient Subspaces Low-Rank?
Authors: Sheikh Shams Azam
Seyyedali Hosseinalipour
Qiang Qiu
Christopher Brinton
Venue: ICLR 2022 Poster (2022)
Keywords: Distributed Machine Learning
Federated Learning
Gradient Subspace
SGD

Abstract: In this paper, we question the rationale behind propagating large numbers of parameters through a distributed system during federated learning. We start by examining the rank characteristics of the subspace spanned by gradients (i.e., the gradient-space) in centralized model training, and observe that the gradient-space often consists of a few leading principal components accounting for an overwhelming majority (95-99%) of the explained variance. Motivated by this, we propose the "Look-back Gradient Multiplier" (LBGM) algorithm, which utilizes this low-rank property of the gradient-space in federated learning. Operationally, LBGM recycles the gradients between model update rounds to significantly reduce the number of parameters to be propagated through the system. We analytically characterize the convergence behavior of LBGM, revealing the nature of the trade-off between communication savings and model performance. Our subsequent experimental results demonstrate the improvement LBGM obtains on communication overhead compared to federated learning baselines. Additionally, we show that LBGM is a general plug-and-play algorithm that can be used standalone or stacked on top of existing sparsification techniques for distributed model training.

Published as a conference paper at ICLR 2022
RECYCLING MODEL UPDATES IN FEDERATED LEARNING: ARE GRADIENT SUBSPACES LOW-RANK?
Sheikh Shams Azam, Seyyedali Hosseinalipour, Qiang Qiu, Christopher Brinton School ECE, Purdue University (a [azaml, hosseina, qqiu, cgb) @purdue. edu
ABSTRACT
In this paper, we question the rationale behind propagating large numbers of parameters through distributed system during federated learning. We start by examining the rank characteristics of the subspace spanned by gradients across epochs (i.e., the gradient-space) in centralized model training, and observe that this gradient-space often consists of few leading principal components accounting for an overwhelming majority (95 - 99%) of the explained variance. Motivated by this, we propose the "Look-bac" Gradient Multiplier" (LBGM) algorithm, which exploits this low-rank property to enable gradient recycling between model update rounds of federated learning, reducing transmissions of large parameters single scalars for aggregation. We analytically characterize the convergence behavior LBGM, revealing the nature of the trade-off between communication savings and model performance. Our subsequent experimental results demonstrate the improvement LBCM obtains communication overhead compared conventional federated learning on several datasets and deep learning models. Additionally, we show that LBCM a general plug-and-play algorithm that can be used standalone or stacked on top of existing sparsification techniques for distributed model training.
INTRODUCTION
Federated Learning (FL) (Konečný et al., 2016) has emerged as a popular distributed machine learning (ML) paradigm. By having each device conduct local model updates, FL substitutes raw data transmissions with model parameter transmissions, promoting data privacy (Shokri & Shmatikov, 2015; Azam al., 2021) and communication savings (Wang et al., 2020a). At the same time, overparameterized neural networks (NN) are becoming ubiquitous in the ML models trained by FL, e.g., computer vision (Liu et al., 2016; Huang et al., 2017) and natural language processing (Brown et al., 2020: Liu et al., 9a). While NNs can have parameters in the range of a few million (VGG (Simonyan Zisserman, 2014), ResNet (He et al., 2016)) to several billions (GPT-3 (Brown et al., 2020), Turing NI.G (tur, 2020)), prior works have demonstrated that majority of these parameters are often irrelevant (Frankle Carbin, 2019; Liu et al., 2019b; Han et al., 2015; Li et al., 2017) in optimization and inference. This presents opportunity to reduce communication overhead by transmitting lighter representations of the model, conventionally achieved through compression//parsifccttoo techniques (Wang et al., 2018; Alistarh et al., 2017; Vogels al., 2019).
In this work, we investigate the "overparamettrizzatoon of NN training, through the lens of rank characteristics of the subspace spanned by the gradients (i.e., the gradient-space) generated during stochastic gradient descent (SGD). We start with the fundamental question: can we observe the effect of overparameterization in NN optimization directly through the principal components analysis (PCA) of the gradients generated during SGD-based training? ? And if so: can this property be used reduce communication overhead in FL? Our main hypothesis is that
the subspaces spanned by gradients generated across SGD epochs are low-rank.
(H1) vector
This leads us to propose a technique that instead of propagating a wewtononiillionimmeee (i.c., gradient) over the system in each iteration of FL only requires propagating single scalar in the majority of the iterations. Our algorithm introduces a new class of techniques based on the concept of reusing/recyeling device gradients over time. Our main contributions
be summarized as follows:
We demonstrate the low-rank characteristics of the gradient-spase by directly studying its prin- cipal components for several NN models trained on various real-worf datasets. We show that

---

Published as a conference paper at ICLR 2022
CIFR-10 FCN
CIFA-10 CNN
CIFAR-10 Resfeel1
CIFAR-10
CelibA
ColeD4
CelekA
ColebA VGG19
VIS039
ResNec18
#corgurent
130
R05 PCR
N:0 PC
13
MO GA
3.40
822
150 140 cpoch
60 opech
25 opoch
50.ch
spach
opoch
opoch
opoch
Figure 1: PCA components progression. The top row shows the number of components that account for 99% (N99-PCA in blue) and 95% (N95-PCA in red) explained variance of all the gradients generated during gradient descent epochs. The bottom row shows the performance of the model on the test data. The results are presented for: (i) CIFAR-IC 10 classification (left 4 columns), and (ii) CelebA regression (right 4 columns).
principal gradient directions (i.e., directions of principal components of the gradient-space) can be approximated in terms of actual gradients generated during the model training process.
Our insights lead us to develop the "Look-back Gradient Multiplier" (LBGM) algorithm to sig- nificantly reduce the communication overhead in FL. LBGM recycles previously transmitted gradients at each device with single scalar. We
gradients to represent the further analytically investigate the convergence characteristics of this algorithm.
Our experiments show the communication savings obtained via LBGM in FL. both as a standalone solution and a plug-and-play method used with other gradient compression techniques, e.g., top-K. We further reveal that LBGM can be extended to distributed training, e.g., LBGM with SignSGD (Bernstein et al., 2018) substantially reduces communication overhead multi-GPU systems.
2 A GRADIENT-
ODYSSEY
We first start by directly studying the principal component analysis (PCA) of the gradient-space of overparameterized NNs. Given a centralized ML training task (e.g.. classification, regression, seg- mentation), we exploit principal component analysis (PCA) (Pearson, 1901) to answer the following: how many principal components explain the 99% and 95% variance (termed N99-PCA and P9A- respectively; together N-PCA) of all the gradients generated during model training?
We start with 4 different NN architectures: (i) fully-connected neural network (FCN), (ii) convo- lutional neural network (CNN), (iii) ResNer18 (He et al., 2016), and (iv) VGG19 (Simonyan & Zisserman, 2014); trained on 2 datasets: CIFAR-10 (Krizhevsky et al., 2009) and CelebA (Liu et al., 2015), with classification and regression tasks, respectively. We then compute the N-PCA for each epoch by applying PCA on the set of gradients accumulated until that epoch (pseudo-code in Algorithm 2 in Appendix D.1). The results depicted in Fig. 1 agree with our hypothesis (H1): both N99-PCA and N95-PCA are significantly lower than that the total number of gradients generated during model training, e.g., in Fig. I' the number of principal components (red and blue lines in top plots) are substantially lower (often as low as 10% of number of epochs, i.e., gradients generated) for both datasets. In Appendix E.1, we further find that (H1) holds in our experiments using several additional datasets: CIFAR-100 (Krizhevsky et al., 2009), MNIST (LeCun & Cortes, 2010), FMNIST (Xiao al., 2017), CelebA (I.iu al., 2015), PascalVOC (Everingham et al., 2010), COCO (Lin et al., 2014); models: U-Net (Ronneberger et al., 2015). SVM (Cortes & Vapnik, 1995); and tasks: segmen- tation and regression. Note that (especially on CIFAR-10) variations N-PCA across models are not necessarily related to the model performance (CNN performs almost as well as ResNet18 but has much lower N-PCA; Fig. 1 - columns 2 & 3) or complexity (CNN has more parameters than FCN but has lower N-PCA; Fig. 1 columns 1 & 2). The fact that rank deficiency of the gradient-span is not consequence of model complexity or performance suggests that the gradient-spare of state-of-thh--an large-scale ML models could be represented using few principal gradient directions (PGD).
N-PCA and FI.. In an "ideal" FL. framework, both the server and the workers/devices have the PGDs, then the newly generated gradients can be transmitted by sharing their projections on the PGDs, i.c., the PGD multipliers (PGM). PGMs and PGDs can together be used to reconstruct the device generated gradients at the server, dramatically reducing communication costs. However, this setting is impractical since: (i) it is infeasible to obtain the PGDs prior to the training, and (ii) PCA is computationally intensive. We thus look for an efficient online approximation of the PGDs.
"The addition of learning rate scheduler (e.g., cosine annealing scheduler (1 (Loshchilov & Hutter, 2016) has an effect the PCA of the gradient-space. Careful investigation of this phenomenon is left future work.
2

---

Published as a conference paper at ICLR 2022
CIFAR-LO L41
CIFAR-10, L#2
CIFAR-10, Les
CIFAR-1O, L,4
Calebé, La1
CalabA, Le2
CellA, Las
ColibA, 144
po prodencc
c4
Relem 075000
freemm 100
delem: 5000
delem: 10
#elem: 075030
Welem: 500
#etem: 5030
#elem: 10
Sr 08
spoch
130 35 09
spoch
103
28 150 200
epoch
to 03 8
epoch gradienis
Figure 2: Overlap of actual and principal gradients. The heatmap shows the pairwise cosine similarity between actual (epoch) gradients and principal gradient directions (PCA gradients). Epoch gradients have substantial overlap with one more PCA gradients and consecutive epoch gradients show a gradual variation. This suggest that there may exist high overlap between the gradients generated during the NN model training. The results are shown for a CNN classifier trained on CIFAR-I0 (left columns) and CelebA (right columns) datasets. Each subplot is marked with #L, the layer number of the CNN and #elem, the number of elements in each layer.
CIFAR 10, Le1
CIFAR-10. Laz #elem:
CIFAR 10, LF3 #elem:
CIFAR Le4
#elem:
CelebA, L.1
CelebA, Le2 #dlem:
CelebA, Le3
CelebA, Led
opoch gradlets
00001 gradienss
Relee:: 625000
L#6 #etem: 500
L+7 #elem: 5000
#elem: 10
Le0
spochh gradarnts
#eleem $25000
L#5
LB6 #elem: 500
L+7 #elem: 5000
Le8 #relem 10
170 10
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
upoch gradients
epoch gradients
epoch gradients
Figure 3: Similarity among consecutive gradients. The cosine similarity of consecutive gradients reveals
gradual change directions gradients over epnchs. Thus, the newly generated gradients he represented in terms of previously generated gradients with low approximation error. Reusing/recycling gradients can thus lead to significant communication savings during SGD-based federated optimization.
Overlap of Actual Gradients and N-PCA. To approximate PGDs, we exploit an observation made in Fig. (and further in Appendix E.1): N-PCA mostly remains constant over time, suggesting that the gradients change gradually across SGD epochs. To further investigate this, in Fig. (and further in Appendix E.2) we plot the cosine similarity between PGDs and actual gradients a heatmap." We observe that (i) the similarity of actual gradients to PGDs varies gradually over time, and (ii) actual gradients have high cosine similarity with one more PGDs. This leads to second hypothesis:
PGDs can be approximated using subset of gradients generated across SGD epochs. (H2)
Look-back Gradients. Our observations above suggest significant overlap among consecutive gradients generated during SGD epochs. This is further verified Fig. (and in Appendix E.3+),
where we plot the pairwise cosine similarity of consecutive gradients generated during SGD epochs. For example, consider the boxes marked B1, B2, and B3 in layer (L#11 in Fig. 3). Gradients each box can be used to approximate other gradients within the box. Also, interestingly, the number of such boxes that can be drawn is correlated with the corresponding number PGDs. Based on (H2), we next propose our Look-back Gradient Multiplier (LBGM) algorithm that utilizes subset of actual gradients, termed llok-back gradients", to reuse/recycle gradients transmitted in FL.
3 LOOK-BACK GRADIENT MULTIPLIER METHODOLOGGY
Federated Learning (FL) considers a system of K workers/devices indexed 1...., K, as shown in Fig. 4. Each worker l possesses local dataset Dj with n4 |D&l datapoints. The goal of the system is to minimize the global loss function F(.) expressed through the following problem:
min F(0) DERM
(x
'Refer to Algorithm in Appendix D.1 for the detailed pseudocode. #2 of 24 experiments (Fig. 52&53 in Appendix F.3) show inconsistent gradient overlaps. However, algorithm discussed in Sec. still performs well those datasets and models (see Fig. 60 in Appendix F.3).
3

---

Published as a conference paper at ICLR 2022
node k
PK
(0),
WK
(t)
vector LBGs
9 k
K
KK
O (
Pk
(f),E
Wk
wk Pk 1
g
k
SERVER
g
(t)
E
9k
= k 9k
92
Pi (1),
9
99 l
cos(
(ak (9-9)
scalar LBCs
Figure Look-buck gradient multiplier. (a) Look-back Coefficients (LBCs) are the projection of accumulated stochastic gradients at the workers on their Look-back Gradients (LBGs). (b) Scalar LBCs, i.c., the Pk (.,. are transmitted to the server. (c) LBG-bassed gradient approximations are reconstructed the server.
where M is the dimension of the model 0, Wk ng/N, N = E Tu. and (0)
EdeD. (0; d)/nk is the local loss at worker k, with do; denoting the loss function for data sample d given parameter vector 0. FL tackles (1) via engaging the workers in local SGD model training on their own datasets. The local models are periodically transferred to and aggregated the main server after local updates. forming global model that is used to synchronize the workers before starting the next round of local model training.
At the start of round I, each model parameter (1-0) is initialized with the global model (()) Thereafter, worker updates its parameters ((thb) as: 0 (f+b++1) < (((bb) n9, (e(t..)))) (((t.b))), where g (t. is the
stochastic gradient at local step b, and is the step size. During vanilla FL aggregation, the global
model parameters are updated ((++1) (()) 1) Ei= wxg
(1) where g Ei 9, (0!)))
is the accumulated stochastic gradient (ASG) at worker k. More generally, this aggregation may be conducted over subset of workers at time We define (0() ΣlE V (o(..)) and d = 9 /T as the corresponding accumulated true gradient and normalized ASG, respectively.
Indexing and Notations. In superscripts with parenthesis expressed as tuples, the first element denotes the global aggregation round while the second element denotes the local update round, e.g.. gk (t.b) is the gradient at worker ls global aggregation round at local update b. Superscripts without parenthesis denote the index for look-back gradients, e.g., l in Pk (t),e defined below.
LEGM Algorithm. LBGM (see Fig. 4) consists of three main steps: (i) workers initialize and propagate their look-back gradients (LBGs) to the server; (ii) workers estimate their look-back coefficients (LBCs), i.e., the scalar projection of subsequent ASGs on their LBGs, and the look-back phase (LBP),, i.e., the angle between the ASG and the LBG; and (iii) workers update their LBGs and propagate them to the server if the LBP passes threshold, otherwise they only transmit the scalar LBC. Thus, LBGM propagates only subset of actual gradients generated at the devices to the server. The intermediate global aggregation steps between two LBG propagation rounds only involve transfer of a single scalar, i.e., the LBC, from each worker, instead of the entire ASG vector.
In LBGM, the local model training is conducted in the same way as vanilla FL, while model aggrega-
tions at the server are conducted via the following rule:
((++1)
((t)
7
wk
where ((0) is the approximation of worker k's accumulated stochastic gradient, given by Definition 1.
Definition 1. (Gradient Approximation in LBGM) Given the ASG (t) and the LBG gfg the gradient
approximation Ø recovered by the server is given by:
((t) ( g for |
(0.e de = cas(a
gk Pk
(DI)
where LBC Pk (0,f denotes the angle between g and of (see Fig. 4(a)).
(f.e (t) .ggg/// |lgg 112 is the projection of the accumulated gradient g on the LBG
(g)
(1)
gf and LBP o'g
4

---

Published as a conference paper at ICLR 2022
Algorithm I LBGM: Look-back Gradient Multiplier
Notation:
0%; global model parameter at global aggregation round f.
0. (bb); model parameter at worker k, at global aggregation round t and local update
Ih accumulated gradient at worker & at global aggregation round f.
9h- last full gradient transmitted to server, termed look-back gradient (LBG).
og ( phase between the accumulated gradient 9 and LBG gig, termed look-back phase (LBP).
Training at worker k:
1: Update local parameters: ( t g(t), and initialize gradient accumulator: gk
O.
for
(r-1)
3: Sample minibatch of datapoints By from D;, and compute //1²)) LE Vfu(O((ab), :d)/BBx). :d)/1BB
4: Update local parameters: (1.b++1) &- (
(1.b) and accumulate gradient: gk t gk + g
(..
5: end for
6: Calculate the LBP error: sin sin' (a (1) ) ( / 0 lloE.l))
7: if sin"(a 0%
gthreshold then
checking the LBP error
8: Send scalar LBC to the server: 14
Pi
(
(g /1/
9: else
b updating the I.BG
10:
Send actual gradient the server: f4 9 (t)
Update worker-copy LBG: g < 9
(t)
12:
end if
Global update at the aggregation server:
13: Initialize global parameter ( and broadcast it across workers.
14: for to (T 1) do
15:
Receive updates from workers { Jk-1-
16:
Update global parameters: (1++1) - ((4)
E we 8K (1) gí + (1- 86) 11 11
1, if 1 is scalar
where Sy is an indicator function given by, 84
0, otherwise, i.e., if p a vector
17:
Update server-copy of LBGs: gf. (1 sx)u + (sx)ef Vk. end for
18:
LEGM initializes the LBGs of with the first actual gradients propagated by the devices at 1, For the subsequent aggregations, each worker k shares only its LBC Pk (0), with the server if the value of LBP error (a (1) is below a threshold, i..., (a (t.))) < 8threshold, where gthreshold E [0, 1] is &
tunable parameter; otherwise updates the LBG via transmitting the entire gradient the server.
The details of LBGM are given in Algorithm 1. We next conduct convergence analysis for LBGM.
Assumptions: It is presumed that the local loss functions bounded below: minøERM (x) - -c, Yk. Let || denote the 2-norm. Our analysis uses the following standard assumptions (Wang al., 2020a; Friedlander & Schmidt, 2012; Hosseinalipour et al., 2020; Li al.; Stich, 2019):
1. Smoothness of Local Loss Functions: Local loss function Fp R R, Ak, is 3-smooth:
(e..) V (0,))
||0
0yll
YO Oy R
(A1)
2. SGD Characteristics: Local gradients g& (0), Vk, estimated by SGD are unbiased estimators of the true gradients V (0), and have bounded variance σ² 2 O; mathematically:
E ( (0) = (0), and E [0) - (O) (F)
<
VO E RR
(A2)
3. Bounded Dissimilarity of Local Loss Functions: For any realization of weights (wx 2 0] where Σ km Wh = there exist non-negative constants r² > and 1 > such that
K
Wk V 12 <
2
Σ Wk (O) +12 VA E M
(A3)
5

---

Published as a conference paper at ICLR 2022
Theorem 1. (General Convergence Characteristic of LBGM) Assume A1, A2, A3, and that n/8 I
min (1/(27),1(T ) }. If the threshold value in step 7 of Algorithm I satisfies the condition 0% öthreshold < / / h 1?? Yk. where A 2 O is constant, then after T rounds of global aggregations, the performance of LBCM is characterized by the following upper bound:
() (0) P 16A² +8n30² +5nd o (
7
EE
1)+20n 8e
-1.. 1). (3)
T
Proof. The proof is provided in Appendix A.
The condition on & 5threshold and I.BP error sin? (ax (a) in the above theorem implies that have fixed
(0).) bound in (3), for a fixed A?, larger gradient norm "|d is associated with tighter condition on the LBP error sin 2 (a& (t),f) and 5threshold, This is intuitive because a larger gradient norm corresponds to larger estimation error when the gradient is recovered at the server for given LBP (see Fig. 4). 2 I|? does not grow to infinity during model training, the condition LBP error in Theorem 1, i..., san (a S < ( can always be satisfied for (t),4 O. Given the general any A 2 O, since transmitting actual gradients of worker A makes a&
In practice, since the gradient norm [|d%
convergence behavior in Theorem we next obtain specific choice of step size and an upper bound on A 2 for which LBGM approaches a stationary point of the global loss function (1).
Corollary 1. (Convergence of LBGM to Stationary Point) Assuming the conditions of Theorem I, if A? S n,, where n = I/VTT, then LBGM converges to stationary point of the global loss function. with the convergence bound characterized below: T-1 TE
l']
(o²(T (
11 + +0
o (r-1111
+0
(4)
rT
T
Proof. The proof is provided in Appendix B.
Considering the definition of A in Theorem 1 and the condition imposed on it in Corollary 1. the LBP error (i.e., sin (a(())))) should satisfy ||d 1 112 sin" sa (t)))) S 7 1/v7T for LBGM to reach stationary point of the global loss. Since 112 is bounded during the model training, this condition on the LBP error can always be satisfied by tuning the frequency of the full (actual) gradient transmission, i.e., updating the LBG as in lines 10&11 of Algorithm 1. Specifically, since the correlation across consecutive gradients high and drops as the gradients are sampled from distant epochs (see Fig. 3), low value of the LBP error can be obtained via more frequent LBG transmissions to the server.
Main Takeaways from Theorem Corollary 1, and Algorithm 1:
1. Recovering Vanilla-FL. Bound: In (3), if the LBGs are always propagated by all the devices, (t).z = 0, Vk, and thus 2 = 0 satisfies the condition on the LBP error. Then, (3) recovers the bound for vanilla FL. (Wang et al., 2020a; Stich, 2019; Wang & Joshi, 2018).
have a
2. Recovering Centralized SGD Bound: In (3), the LBGs are always propagated by all the devices,
i.e., A = 0, the local dataset sizes are equal, i.e., dy. 1/K, Vk, and 7 = 1, then (3) recovers the bound for centralized SGD, c.g., see Friedlander & Schmidt (2012).
3. Unifying Algorithm 1 and Theorem 1: The value of A 2 in (3) is determined by the value of the LBP error sin (t).F). which is also reflected in step of Algorithm This suggests that the performance improves when the allowable threshold on sin (a is decreased (i.e., smaller A"), which is the motivation behind introducing the tunable threshold 5threshold in our algorithm.
4. Effect of LPB Error on Convergence: As the value of sin (a (1) increases, the term in (3) containing 2 will start diverging (it can become the same order as the gradient (|a (12). The condition in Corollary 1 on A avoids this scenario, achieving convergence
stationary point.
5. Performance vs. Communication Overhead Trade-off: Considering step of Algorithm increasing the tolerable threshold on the LBP error increases the chance of transmitting scalar (i.e., LBC) instead of the entire gradient to the server from each worker, leading to communication savings. However, as seen in Theorem and the condition on A in Corollary 1, the threshold on the LBP error cannot increased arbitrarily since the LBGM may show diverging behavior.

---

Published as a conference paper at ICLR 2022
Vandle LBGM
Vanill FL Ae 0.0
& glwwtaa.
Mhi5T Non ID0
FHISST Non HD
CIFAB-1O Non ID
Calvbs Regression
MNIST KorelD
PHINIST NowiiD
CIFAR 15 Non-IID
Celebd
Regressior
1055 (NL0P)
2
3
25
125 24
30 20
220
304
21
230 25 360
220 12 a23
1.5
1022 1at2
235
8 2
losk
3.0g
parrams
aparams share3(x(10))
sparame
pprramss shares(x301t
aparams shered/x10f)
aparami
parrams sharee 304)
eparams shanddjx109 othreshold
shores(w10f)
1har
shared(K30*|
Figure 5: LBGM as a Standalone Algorithm. Irrespec- tive of the dataset/data configuration across workers, I LBGM consistently outperforms vanilla FL. in terms of the total parameters shared (middle row) while achiev- ing comparable accuracy (top row). The bottom row shows accuracy vs. # parameters shared.
Figure 6: Effect of 6threshold on LEGM As 0%
decrcases, the training may become unstable. For larger values of @threshold LBGM achieves communica- tion benefits (middle row) while maintaining a perfor- mance identical to vanilla FL (top row). The bottom row shows accuracy vs. # parameters shared.
4 EXPERIMENTS
Model Settings. We run experiments on several NN models and datasets. Specifically, consider: S1: CNN on FMNIST, MNIST, CelebA, and CIFAR- 10, S2: FCN on FMNIST and MNIST, and S3: R on FMNIST, MNIST, CelebA, CIFAR-I0 and CIFAR- for both independently and identically distributed (iid) and non-iid data distributions. We present results of S1 (on non-iid data) in this section and defer the rest (including S1 on iid data and U-Net on VOC) to Appendix F.
Properties Studied. We specifically focus on four properties of L.RG; Pl: the benefits of gradient recycling by LBGM as a standalone algorithm, P2: the effect of 8 gthreshold on LBGM from Theorem 1, P3: practical capabilities of LBGM as a general plug-and- and--pay algorithm that can be stacked on top of other gradient compression techniques in FL training, and finally P4: generalizability of LBGM to distributed learning frameworks, e.g., multi-processor multi-GPU ML systems.
Baselines. For P1 and P2, we compare LBGM with vanilla FL. For P3, we stack LBCM on top of top-K and ATOMO (Wang et al., 2018), two state-of-the-an art techniques for sparsification and low-rank approximation-basee gradient compression, respectively. For P4, we stack LBGM on top of SignSGD (Bernstein et al., 2018), state-of-the-art method in gradient compression for distributed learning.
Implementation Details. We consider an FL system consisting of 100 workers. We consider both the iid and non-iid data distributions among the workers. Under the iid setting, each worker has training data from all the labels, while under the non-iid setting each worker has training data only from a subset of all labels (e.g.. from 3 of 10 classes in MNIST/FMNIST), The workers train with batch sizes ranging from 128 to 512 based on the choice of dataset. We implement LBGM with uniform 8 5threshold across workers. We also use error feedback (Karimireddy et al., 2019) as standard only if top- K sparsification is used in the training. The FL system is simulated using Py PyTorch (Paszke et al., 2019) and PySyft (Ryffel et al., 2018) and trained on a 48GB Tesla-P100 GPU with 128GB RAM. All of our code and hyperparameters are available hpt : / //gi thub. com/ shams-aams- sam/ //F FedOpt.i. im. Appendix C.2 details the process of hyperparameter selection for the baselines.
Complexity. Compared to other gradient compression techniques, the processing overhead introduced by LBGM is negligible. Considering Algorithm 1, the calculation of LBCs and LBP errors involves inner products and division of scalars, while reconstruction of LBG-based gradient approximations at the server is no more expensive than the global aggregation step: since the global aggregation step requires averaging of local model parameters, it can be combined with gradient reconstruction. plug-and-play algorithm, as top-K and ATOMO (Wang et al., 2018)
This also holds for LBGM introduce considerable computation overhead. In particular, LBG has O(M) complexity, where M is the dimension of the NN parameter, which is inexpensive to plug on top of top-K (O(M log M)), ATOMO (Wang et al., 2018) (O(M?)) and SignSGD (Bernstein et al., 2018) (O(M) methods. The corresponding space complexity of LBGM for the server and devices is discussed in Appendix C.I.
LBGM as a Standalone Algorithm. We first evaluate the effect of gradient recycling by LBGM in FL. Fig. 5 depiets the accuracy/loss values (top row) and total floating point parameters transferred
7

---

Published as a conference paper at ICLR 2022
Wi LBGM
W/ LBGH
MNIST
FMNIST Non-lID/Top-
MMST Non-ID/ATOMM
FMNIST Non-IEDAATOME
Non-IlI2/Tee
Non-IlDD/ sp-K
Top-K
Non-IDDAATMO
ATOMO
1.4
(K300%
l003 (x10*)
7 2
3.59
46
C
E5C
C. E
322
2.5
625
c25
10
315
24
103
6
11
375
34
lovn (x107
035
075
logs (x10')
5 E
#params
#params shared(x10
04
05
shared(x109)
shared(x10*)
10)
x0
shared(x10
shared(x10*
sharedix10")
Figure LBGM as Plug-and-Plan Algorithm. LRGM obtains substantial communication benefits when
implemented on top of existing gradient compression techniques by exploiting the cankccaaacteristics of the gradient-space. Top-K and ATOMO are known to achieve state-of satte-of-thh-ar the-trteart performance of their respective domains of sparsification and low-rank approximation respectively.
over the system (middle row) across training epochs for gilreshold 0.2, Vk on diferent datasets. The parameters transferred indicates the communication overhead, leading to corresponding performance vs. efficiency tradeoff (bottom row). For each dataset, we observe that LBGM reduces communication overhead the order of 10? floating point parameters per worker. Similar results on other datasets and NN models are deferred to Appendix F.I. We also consider LBGM under device sampling (see Algorithm 3 in Appendix D.2) and present the results in Appendix F.5, which qualitatively similar.
Effect of f 5threshold on Accuracy vs. Communication Savings. In Fig. 5, the drops in accuracy for the corresponding communication savings are small except for on CIFAR- 10. The 14% reduction in accuracy here is a result of the hyperparameter setting & @ihneshoodd = 0.2. As noted in takeaway 3 in Sec. 3, a decrease in the allowable threshold on the LBP error improves the accuracy; the effect of threshold value is controlled by changing
& 5threshold values in Algorithm 1. Thus, we can improve the accuracy by lowering 5threshold; for & grhreshald = 0.05, the accuracy drops by 4% only while still retaining a communication saving of 55,, and for gthresholdd = 0.01, we get 22% communication saving for negligible drop in accuracy (by only 0.01%). In Fig. 6, we analyze LBGM under different 5threshiold values for different datasets. A drop in model performance can be observed as we increase % 5threshold, which is accompanied by an increase in communication savings. This is consistent with takeaway 5 from Sec. 3, i.e., while a higher threshold requires less frequent updates of the LBGs, reduces the convergence speed. Refer to Appendix F.2 for additional results.
Algorithm. For the plug-and-pla setup, LBGM follows the same steps as in Algorithm 1, with the slight modifica- tion that the output of gradient compression tech- niques, Kop-K and ATOMO, are used in place of accumulated gradients gk and LBGs gf. Vk.
LBGM as Plug-and-
NNIST Non IDD/SignSDD
RANIST Non IID/SignSED
CIFAR-10 Non IIDisinnse
Calebd S SirssD
secrrgy
Asc
035
(t)
esis Xx10
227
In Fig. 7, we see that LBGM adds on top of exist- ing communication benefits of both top-K and ATOMO, on the order of 10 and 10 floating point parameters shared per worker, respectively (30 - 70% savings across the datasets). The bot- tom row shows the accuracy/loss improvements that can be obtained for the same number of pa- rameters transferred. While top-K and ATOMO compress gradients through approximation, they do not alter the underlying low-rank characteris- ties of the gradient-space LBGM exploits this property to obtain substantial communication savings on top of these algorithms. Refer to Appendix F.3 for additional experiments.
339
24
635
34
025
250
25
ebits
#bit
shared(x10*)
sharedix10*
(x10
shared(x109)
Figure 8: Application of LBGM as a plug-and and -ad---nd--layy al-
gorithm on top of SignSGD in distributed training.
Generalizability of LBGM to Distributed Training. LBGM be applied to more general dis- tributed gradient computation settings, e.g., multi-core systems. While heterogeneous (non-iid) data distribution are not as much of consideration in these settings as they are in FL (since data can
8

---

Published as a conference paper at ICLR 2022
be transferred/allocateed across nodes), there is research interest in minimizing parameter exchange among nodes to reduce communication latency. SignSGD (Bernstein et al., 2018) is known to reduce the communication requirements by several order of magnitude by converting floating-poni parameters to sign bit communication. In Fig. 8, we apply LBGM as a plug-and-play addition on top of SignSGD and find that LBCM further reduces the overall bits transferred by SignSGD on the order of 10 bits (60 - 80% savings across the datasets). Refer to Appendix F,4 for additional experiments.
RELATED WORK
NN Overparameterization Analysis. Several prior works on NN overparameterization have focused on Hessian- based analysis. Sagun et al. (2016; 2017) divide the eigenspace of the Hessians into two parts: bulk and edges, and show that increasing network complexity only affects the bulk component. Ghorbani et al. (2019) argues that the existence of large isolated eigenvalues in the Hessian eigenspace is correlated with slow convergence. Gur-Ari et al. (2018) studies the overlap of gradients with Hessians and shows the Hessian edge space remains invariant during training, and thus that SGD occurs in low-rank subspaces. Gur-Ari et al. (2018) also suggest that the edge space cardinality is equal to the number of classification classes, which does not align with our observations in Sec. In contrast to these, our work explores the low-rank property by studying the PCA of the gradient-space directly. Li et al. (2021), a contemporary of ours, employs the spectral decomposition of the NN gradient space to improve centralized SGD training time. Our methodology based on Hypothesis (H2) is more suitable for FL since having the resource-constraine workers/devices execute spectral decomposition
component of the training process would add significant computational burden. The partitioning of the gradient subspace has also been observed in the domain of continual learn- ing (Chaudhry et al., 2020; Saha et al., 2020). However, the subspace addressed in continual learning is the one spanned by gradient with respect to data samples for the final model, which is different than the subspace we consider, i.e., the subspace of gradient updates generated during SGD epochs. Gradient Compression. Gradient compression techniques can be broadly categorized into (i) sparsification (Wangni et al., 2018; Sattler et al., 2019), (ii) quantization (Seide et al., 2014; Alistarh et al., 2017), and (iii) low-rank approximations (Wang et al., 2018; Vogels et al., 2019; Albasyoni et al., 2020; Haddadpour et al., 2021). Our work falls under the third category, where prior works have aimed to decompose large gradient matrices as an outer product of smaller matrices to reduce communication cost. This idea was also proposed in Konečný et al. (2016), one of the pioneering works in FL. While these prior works study the low-rank property in the context of gradient compression during a single gradient transfer step, our work explores the low rank property of the gradients generated across successive gradient epochs during FL. Existing techniques for gradient compression can also benefit from employing LBGM during FL. as we show in our experiments for top-K, ATOMO, and SignSGD.
Model Compression. Model compression techniques have also been proposed to reduce NN complexity, e.g., model distillation (Ba & Caruana, 2014; Hinton et al., 2015), model pruning (LeCun et al., 1990; Hinton et al., 2015), and parameter clustering (Son et al., 2018; Cho et al., 2021). (Li et al., 2020) extends the lottery ticket hypothesis to the FL setting. These methods have the potential to be employed in conjunction with LBGM to reduce the size of the LBGs stored at the server.
FL Communication Efficiency. Other techniques have focused on reducing the aggregation fre- quency in FL. Hosseinalipour et al. (2020); Lin et al. (2021) use peer-to-peer local network communi- cation, while SloMo (Wang et al., 2020b) uses momentum to delay the global aggregations.
6 DISCUSSION & CONCLUSIONS
In this paper, we explored the effect of overparameterizzatin in NN optimization through the PCA of the gradient-space, and employed this to optimize the accuracy vs. communication tradeoff in FL. We proposed the LBGM algorithm, which uses our hypothesis that PGDs can be approximated using a subset of gradients generated across SGD epochs, and recycles previously generated gradients at the devices to represent the newly generated gradients. LBGM reduces communication overhead in FL by several orders of magnitude by replacing the transmission of gradient parameter vectors with a single scalars from each device. We theoretically characterized the convergence behavior of LBGM algorithm and experimentally substantiated our claims several datasets and models. Furthermore, we showed that LBGM can be extended to further reduce latency of communication in large distributed training systems by plugging LBGM on top of other gradient compression techniques. More generally, our work gives a novel insight to designing a class of techniques based on "Look-back Gradients" that can be used in distributed machine learning systems to enhance communication savings.
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Turing-NLG: A parammete language model by Microsoft. https:/wwww.miicrostttcoomm/// 2020.
us/resencchhlleg/urinn--gge -aaaiiingng-------iiiii
Alyazeed Albasyoni. Mher Safaryan, Laurent Condat, and Peter Richtárik. Optimal Gradient Compression for Distributed and Federated Learning. arXiv preprint wwXiv:2010003244 2020.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication-EFinn Efficient SGD via Gradient Quantization and Encoding. In Neural Information Processing Systems (NeurlPS), 2017.
Sheikh Shams Azam, Taejin Kim, Seyyedali Hosseinalipour, Christopher Brinton, Carlee Joe- nee-Wong, and Saurabh Bagchi. Towards Generalized and Distributed preeecypr Representation Learning. arXiv preprint arXiv:2010.01792. 2021.
Lei Jimmy Ba and Rich Caruana. Do Deep Nets really need to be Deep? In Neural Information Processing Systems (NeurIPS), 2014.
Jeremy Bersstcin, Yu-Xian Yu-Xiang Wang, Kamyar Azizzadcnesheli, and Animashree Anandkumar, SignSGD: Com- pressed Optimisation for Non-convex Problems. In International Conference on Machine Learning (ICML), 2018.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subhiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Ncelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herhert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray. Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language Models are Few-Shot Learners. In Neural Information Processing Systems (NeurIPS), 2020.
Arslan Chaudhry, Nacemullah Khan, Puneet Dokania, and Philip Torr. Continual Learning in Low-rank Orthogonal Subspaces. In Neural Information Processing Systems (NeurlPS), 2020.
Minsik Cho, Keivan A Vahid, Saurabh Adya, and Mohammad Rastegari. DKM: Differentiable K-Meam Clustering Layer for Neural Network Compression. arXiv preprint arXiv:2 12659, 2021.
Corinna Cortes and Vladimir Vapnik. Support Networks. Machine Learning, 20(3):273-22) 297, 1995.
Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The Pascal Visual Object Classes (VOC) Challenge. International Journal of Computer Vision (IJCV), 88(2):303-333 2010.
Jonathan Frankle and Michael Carbin. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In International Conference on Learning Representations (ICLR), 2019.
Michael P Friedlander and Mark Schmidt. Hybrid Delerministic-stochastii Methods for Data Fitting. SIAM Journal on Scientific Computing, 34(3):A133)) 13300-A1055, 2012.
Behrooz Ghorbami, Shankar Krishnan, and Ying Xiao. Investigation into Neural Net Optimization via Hessian Eigenvalue Density. In International Conference on Machine Learning (ICML), 2019.
Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient Descent Happens in Tiny Subspace. arXiv preprint arXiv:1812.044 1812.0475, 2018
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated Learning with Compression: Unified Analysis and Sharp Guarantees. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both Weights and Connections for Efficient Neural Networks. In Neural Information Processing Systems (NewrIPS), 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge in a Neural Network. arXiv preprint arXiv:1503.022 00.533,,.23,,..... 2015.
Seyyedali Hosseinalipour, Sheikh Shams Azam, Christopher G Brinton, Nicolo Michelusi, Vaneet Aggarwal, David J Love, and Huaiyu Dai. Multi-stage Hybrid Federated Learning over Large-scale Wireless Fog Networks. arXiv preprint 17555 2020.
10

---

Published as a conference paper at ICLR 2022
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely Connected Convolutional Networks, In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4700-440 47004 2017.
Sai Praneeth Karimireddy, Quentin Rebjock, Sehastian Stich, and Martin Jaggi. Error Feedback fixes SignSGI and other Gradient Compression Schemes. In International Conference on Machine Learning (ICMI.), 2019.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated Learning: Strategies for Improving Communication Efficiency. In Neural Information Processing Systems (NeurIPS), 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features from Tiny Images. 2009.
Yann LeCun and Corinna Cortes. MNIST Handwritten Digit Database, 2010. URL httttt////yann lecun. com/
Yann LeCun, John S Denker, and Sara A Solla. Optimal Brain Damage. In Neural Information Processing Systems (NeurlPS), pp. 598-605 1990.
Ang Li, Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. LotteryFL: Personalized and Communication-effioee Federated Learning with Lottery Ticket Hypothesis on Non-iid Datasets, arXiv preprint arXiv:2008.00 03371, 2020.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, Hans Peter Graf. Pruning Filters for Efficient Convnets. In International Conference on Learning Representations (ICLR). (017.)
Tao Li, Lei Tan, Qinghua Tao, Yipeng Liu, and Xiaolin Huang. Low Dimensional Landscape Hypothesis True: DNNs can be Trained in Tiny Subspaces, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the Convergence of FedAvg on Non-IID Data. In International Conference on Learning Representations (ICLR).
Frank Po-Cher Chen Lin, Seyyedali Hosseinalipour, Sheikh Shams Azam, Christopher G Brinton, and Nicolo Michelusi. Two Timescale Hybrid Federated Learning with Cooperative D2D Local Model Aggregations. arXiv preprint arXiv:2103. 10481, 2021.
Tsung-Yi Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and Lawrence Zitnick. Microsoft COCO: Common Objects in Context. European Conference on Computer Vision (ECCV), pp. 740-755, 2014.
Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng- Fu, and Alexander C Berg. SSD: Single Shot Multibox Detector. In European Conference on Computer Vision (ECCV), pp. 21-37. Springer. 2016.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A Robustly Optimized BERT Pretraining Approach. arXiv preprint arXiv: 1692, 2019a.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang. and Trevor Darrell. Rethinking the Value of Network Pruning. In International Conference on Learning Representations (ICLR), 2019b.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep Learning Face Attributes in the Wild. In IEEE International Conference on Computer Vision (ICCV), December 2015.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. In International Conference on Learning Representations (ICLR), 2016.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Neural Information Processing Systems (NewrIPS). 2019.
Karl Pearson. LIII. On Lines and Planes of Closest Fit to Systems of Points in Space. The London, Edinburgh. and Dublin Philosophical Magazine and Journal of Science, 2(1 2(11):59-557 1901.
Olaf Renneberger, Philipp Fischer, and Thomas Brox, U-Net: Convolutional Networks for Biomedical Image Segmentation. In International Conference Medical Image Computing and Computer-assisted Intervention, pp. 234-241, 2015.
11

---

Published as a conference paper at ICLR 2022
Theo Ryffel, Andrew Trask. Morten Dahl. Bobby Wagner, Jason Mancuso, Daniel Rueckert, and Jonathan A Generic Framework for Privacy Preserving Deep Learning. arXiv preprint
arXiv: 181118401101 2018.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of Hessian Deep Learning Singularity and Beyond. arXiv preprint arXiv: 16/1:: 1.07476, 2016.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical Analysis of the Hessian of Over peer-parametrized Neural Networks. arXiv preprint 1706:0/00000444 2017.
Gobinda Saha, Isha Garg, and Kaushik Roy. Gradient Projection Memory for Continual Learning. Interna- tional Conference on Learning Representatiins (ICLR), 2020.
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and Communication- efficient Federated Learning from Non-iid Data. IEEE Transactions on Neural Networks and Learning Systems, (119))3400-41111 2019.
Frank Scide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit Stochastic Gradient Descent and its Data-paralle parallel Distributed Training of Speech DNNs. In Conference of the International Speech Communication Association (INTERSPEECH), 2014.
Application to Data
Reza Shokri and Vitaly Shmatikov. Privacy-preserving Deep Learning. In ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 1310-1321, 2015.
Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Seer Seage-Scaleaaee Image Recognition. arXiv preprint arXiv: (409. 1556, 2014.
Sanghyun Son, Scungjun Nah, and Kyoung Mu Lec. Clustering Convolutional Kernels to Compress Deep Neural Networks. In European Conference Computer Vision (ECCV), pp. 1122222,44222 2018
Sebastian U Stich. Local SGD Converges Fast and Communicates Little. In International Conference on Learning Representations (ICLR), 2019.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical Low-rank Gradient Compression for Distributed Optimization. In Neural Information Processing Systems (NewrIPS), 2019.
Hongyi Wang, Scott Sievert, Zachary Charles, Shengchao Liu. Stephen Wright, and Dimitris Papailiopoulos. ATOMO: Communication-elliceeet Learning via Atomic Sparsification. In Neural Information Processing Systems (NeurIPS), 2018.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A Unified Framework for the Design and Analysis of cattunniiiaaiiooffffiieeee SGD Algorithms. arXiv preprint arXiv:1808.00 070780 2018
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor.
Tackling the Objective Inconsistency Problem Heterogencous Federated Optimization. Neural Information Processing Systems (NeurIPS), 2020a.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving Communication- efficient Distributed SGD with Slow Momentum. In International Conference on Learning Representations (ICLR), 2020b.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient Sparsification for Communication-eefin Distributed Optimization. In Neural Information Processing Systems (NeurIPS), 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Machine Learning Algorithms, 2017.
a Novel Image Dataset for Benchmarking
12

---

Published as a conference paper at ICLR 2022
Appendix
Table of Contents
Proof of Theorem 1
14
A.I Condition Learning Rate
20
B Proof of Corollary 1
21
Additional Discussions
22
C.I LBGM Storage Considerations
22
C.2 Hyperparameter Tuning
22
Additional Pseudocodes
22
D.1 Pscudocode for Preliminary Experiments
22
D.2
Pseudocode for Device Sampling Experiments
24
Additional Preliminary Experiments
25
PCA Component Progression
25
E.2 Overlap of Actual and Principal Gradient
25
E.3
Similarity among Consccutive Generated Gradients
26
F
Additional LBGM Experiments
27
F.1
LEGM as a Standalone Algorithm.
27
F2
Effect of athreshold on LBGM.
27
F3 LBGM as a Sfug-and-Play Algorithm.
27
Generalizahility of LBBGM to Distrihuted Training.
27
LBCM under Client Sampling.
28
13

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM
We start by introducing a lemma, that used prominently throughout the analysis that follows.
Lemma 1. For a sequence of vectors {a, i=
such that EE' a a2-2:""1 01 = 0, Vi,
N
N
E
Σ
a
Σ
E
a
(L2)
1=1
Proof.
N N
E
Σ
a
Σ E a
Σ>>
M
E
[a
(5)
j=1
Using the law of total expectation, assuming < j. we get
E [ [a]
E
[a T [a a........................ [,]] = 0,
(6)
which completes the proof.
Next, we define few auxiliary variables that would be referenced in the proof later: as defined in the main text, 9 (t) Σi= Is. (o(t.)) is the accumulated stochastic gradient worker k, where
b ranging from 0 to T - 1 denotes the rounds of local updates. Using Assumption (A2), error in
stochastic gradient approximation 94 (o( can be defined C
(t,b) 9 (g((..)) VF, (F (((
Consequently, we can write the stochastic gradient as ()(((())) V (O (.b + E
(t.b)
where
FF, (O(( is the true gradient. From Assumption (A2) it follows that
(t.b) 0 and E
||
(c.b)
E
c
We also introduce the normalized stochastic gradient d given by
(o(
(F (1,)
(1,b)
(0) (0)
gh
Ek
hx
c/
(8)
6=0
6=0
b=
where we define
Cumulative Average of the true gradient: h2 (4)
F., (0) and
(0)
(t.b)
Cumulative Average of the SGD emror:
(10)
(
Next, we evaluate the first and second moment of normalized SGD error, c follows
k
(8)
E
(t,b) R
= 0,
(11)
6=0
b=0
[3]
(t,b)
||?
27
< o²
E
=
E
7
&
(12)
6=0
b=0
where (11) uses Assumption (A2) and (12) uses Lemma 1.
Now we can proceed to the proof of Theorem We start with the update rule of LBGM, where round of global update is given by
K Σ
K
g(++)) ((t)) 17
wh
(t)
g(
tn
Wk
w
(13)
14

---

Published as a conference paper at ICLR 2022
(t) where 9k is the approximate gradient shared by worker & with the server and dz is given by
(1)
d - ( g Pk (t). dx
(14)
where di - g is the normalized stochastic gradient w.r.t. the last LBG shared by worker k. Also, from the trigonometric relationship shown in Fig. 4, we have,
de
L cos(a 2
(15)
Similar to d from (8), di can be split into the cumulative average of true look-back gradient h and the corresponding cumulative average of SGD) error E given by
d = h + c..
(16)
From Assumption (A1), the global loss function is 3 smooth, which implies:
- -(((())) - (F ),(++)) (
11011-0000 - 6/ k E (1, 2, ... KK.b
3 2 |
p(0) 0000
(17)
Taking expectation over (1,b) F(o(++))) (()(
, E 10,1, - 1}.
I E VF((()).
Σ
K
Wk
dj
(11)
)
K
wk
du
(0)
27
(18)
2
We evaluate Z₁ follows
K
Z1 E
VF(O
Σ wx
=E E
VF(O
Σ
wk
d2
(t)
d
(1)
dx
E
VF(O"),
WR ci
VF(O
Wk
(
110)
dx
(19)
A=1
Zz.2
where Z1, is given by.
K
1|
(
K
Z1,1
( E
VF()
Σ
win
(0)
+
VF(B
Σ
wxE
(1)
K
K
1
E
wi
(0)
B
1
VF(O(())
(t) k
(20)
2
2
la b for any two real vectors and b. We next upper bound the term Z1 (although 1 has negative sign in (19), Z also appears with a negative sign in (18) which allows us to do the upper bound) as follows
where (i) follows from (16) and (ii) uses 2 (a, b)
|a||
|b|
K
(t) k
Z, =
Wk
(
1 (
K
$ 4
Wk
d
(21)
where (i) follows from (a, b) < [a/4)||||2 + |b6 (result of Schwartz and Young's inequalities). Substituting (20) and (21) back in (19), get
15

---

Published as a conference paper at ICLR 2022
K
K
-71 -
(
||
-
Σ
wk w (8)
+ t
1
VF(O
- w (o)
4
2
1=1
K
+
E
Σ
Wk
dheh
(22)
We next bound the term Zg in (18) as follows
K
27
K
Z- =
E
Wk
d
&
(1)
=
E
Wk
d
k
d
dx
(1)
R=1
(0)
$ 2
Σ
K
Wy x
+2E
Σ
K
Wk
dh
d2
(8)
(23)
Arm
Zz
where Z,, is given by,
K Σ
K
K
27
22 = E
w
(1)
wi
h
(1)
+ E
WKE
(1)
1=1
27
(8)
E
Σ Wk
h
(t)
(t)
2
E
Σ
wh
(t)
+
(24)
k=1
where (i) follows from (8), (ii) uses Jensen's 's inequality:
EK w S Exe
||a*|| 12 s.t.
Σ We = 1. and (iit) uses (12). Plugging (24) back into (23), we get
Z2 S 2E
Σ
K (A)
202 +
2E
K Σ
wi
d(tt)
-a(")
)("
(25)
T
Substituting (22) and (25) back (18), we get
E
[(B(L+t))] F(O(1))
THj
(F(
2
TM
E
K
Wk 1
4
2
k=1
K
K
+ T E
VF(O
Σ
w #
+ +mEE
Σ Wk
d
-(1)
2
K
+ 2 SE
Σ
wirh
(1)
+ TT)
30= 30"
+ 22 BE
Σ Wk
d
di
K
=- 77
=-4 4
VE(O(()) 1|²
2TTB)LE
Σ
wh (4)
T
VF(O(())
Σ wa (2)
17"
1)/11 + F
Σ Wk a
ah²
Tn² Bo²
(26)
16

---

Published as a conference paper at ICLR 2022
Choosing THi Σ 1/2, implies that - (1 2rmB) S 0 and 1 + 7n8 3/2 2, which results in simplification of (26) as:
F(((+t)))] F(O()))
_ VF
VF(O 1| +
1
VF(OR))
w (t) #
1/T
+ 2B
Σ Wk
K
dh
-dte)
7(10
+ n1802
(
(F()
||
+ 2 k=1
Σ
K
W
V (
4
(0)
+ 2
Σ
Wi E
d
dx
+n,3o²
(27)
Zi
where (i) follows from Jensen's 's inequality
k= a 1| S Σ
k== We
||aل||
s.t. Ex= wk =
1
and (()) ( vk due to local synchronization. Now Zg can be bounded as follows:
2
#
9k
96
Z3
E
d2
E
Pk
1
d
E
d
d
1
(124)
(1)
(1)
dp
E
(1) x
2
d
(0)
dk
k
(ie)
E
(1)
|| 2
cos2(ar (0).e
= R
| |a (1 cos? cos?(( (a.
2E
||a.5
2
sin 2
(a,
(0)
A
A
(28)
where (t) uses (14). (it) uses LBGM definition from (D1), (iii) uses the fact that d
gf (iv)
uses (a, b) = ||a|] [bb] cos(a), and (v) follows from the condition in the theorem. Substituting (28)
back in (27), get
E [(0(+))))] - F(((())
1 K
VF
||
+
Σ
wk
E
VF
(0())
1 (
+2A² +n302 (29)
2
k=1
Za
where Z4 is given by,
Z4 E (0 -
-
1
E
V Fa (1.0)
(O(
- (O(
-
72
-
o (c,0)
0 (tb)
E
<
E
(30)
6=0
17

---

Published as a conference paper at ICLR 2022
Also, using the local update rule (% +- 0 1) - gK (0f(..))) where og is the model
parameter obtained at the b-th local iteration the global round at device ki we get:
|10000
Zş E
k
Σ
&h
0
(.55)
20y
V
+ +
Σ 1=0
(5,s)
(10
2:)² 6
E
21)²
Σ
b-1
EE
c/
(t.s))
S 2b
E
(0
(1.))
+
22)2
(31)
where (z) uses Gauchy-Schwarlt inequality and (ii) uses Lemma 1 and inequality. Also note that
r-1 T(r 1))
Σ
(32)
Taking the cumulative sum of both hand sides of Zs from (31) over all batches, i.e., - Ei and using (32), we get:
o st |
-
1)
Σ
E
F
(L.b)
27
(33)
hm0 0
b=
Furthermore, term Ze can be bounded as follows:
Zo E 1O
0.0)
||]
(6)
2E
(Fi
| [|]
-
(o("0)
2E
|
(2)) S
|100000
[|]
2
2E
(34)
where (1) uses Cauchy-Schwartz inequality and (di) uses (A1). Replacing Ze in (33) using (34), get:
0 (1.0)
((.)))
E
0m
Zs
<
<1²0
27 1)
Σ
E
(t.b)
o
(1,0)
22n T 1)E
Zs
(35)
Note that Zs, which originally defined in (31), appears both in the left hand side (LHS) and right hand side (RHS) of the above expression. Rearranging the terms in the above inequality yields:
Σ
(.0)
|9] 5 1 2n (T
nT=2(T-
21 1)
|
+ 1 2n (T 1)
0=
(36)
18

---

Published as a conference paper at ICLR 2022
Defining H= 2n2 ((
1), the above inequality can be re-written to evaluate Za.
82 r-1 Z4
E①
b=
11² (2 -1
2n TT - 1) E
V F (0 [/]
<
1 211² (3 1) + 1 2 B2 - 1)
32 0²
H R [F |1(
(T - 1) +
(37)
1 H
1- H
Taking weighted sum from the both hand sides of the above inequality across all the workers and using (A3), we get:
K
VFA(O - n. 1/01pp]
W E
32 0² (T 1)
H
||]
Wk
wy
2(1 H)
2(1 H)
k=1
o2"300"(T 1)
H
K
+
Σ
F
E
2(1 H)
2(1 - H)
k=1
(1) 3023002(1 1)
H
|F(((())
19]
HT 2(1
E
(38)
2(1 H)
2(1 H)
H)
vk since computation occurs at the instance of global aggregation. Next, plugging (38) back in (29), we get:
where (i) follows from (A3) and ( = (())
E
F(O
V/T
K
$ 4
(F(
/|
2
Σ W |[F((O( - -ng [1
+ 2A - -n3o²
2 k=1
1
(F( )|
||2
+ 12 (T - 1)
HY²
VF(O |||
HT²
+
E
4
2(1 H)
2(1 - H)
2(1 - H)
+ 212 + 1130²
1 (1 2
I|
12 (T 1)
HT²
24 n1302
(39)
2(1 H)
2(1 H)
If H < T7 for some constant a 1, then it follows that - S 1 Choosing = 2 we can simplify the above expression follows:
2 and
2
< 1
1-
a
E F(0(++1))] - F()(
7/T
< (F)) )|² ||²
+212 + n,00 +123302 1)
(
1
+2 322 1)
(1+
1
8T2
4T²
(F( /|² +222 + n
5
28 8
32
(
+)+
5
2 -2 - 1).
(40)
2
19

---

Published as a conference paper at ICLR 2022
Rearranging the terms in the above inequality and taking the average across all aggregation rounds from the both hand sides, yields:
O0 |1]
E
V V
t=0
8
Σ 1=
E )( - )(
+ 164 + 8n332 5n 1) + 20m 1)
1TT
8 (() - -F(O(T)
16A + 8nB08 +
+ 201 g2T 1)
nTT
8 ()) F
16A + 8n50² + ( 1) + 321 1),
(41)
'T'
where used the fact that F is bounded below, since F&-s are presumed to be bounded below, and F & F(0), vo E RM, This completes the proof Theorem
A.1 CONDITION ON LEARNING RATE
From the two conditions on the learning rate used in the analysis above, we have
n13 < 2T
(42)
3² 1) - 1 + 422
(43)
We can further tighten the second constraint as,
1
2n1² 1) 2n
(44)
1 1 4
Combining the two we have,
n1 S min
(45)
2r T /2 4)
20

---

Published as a conference paper at ICLR 2022
B PROOF OF COROLLARY
Using (41) we have:
T-1
VF(O
E
1=
()) F
16 + 8n 32 1) 20m² 12 1).
(46)
N
Next, using the assumption in the corollary statement, we have A S 17. We then can upper bound the RHS of (46) to get:
||
E
1=0
8
F(O( F
+ 16n + 81130² + 32) 1) 20n2 - 1).
(47)
n
Choosing 1) V 7T we get,
VF(OL
E
8 ((00())-11
8,30
5 - 1) +
20
TT +
(48)
VTT
VT
7T
rT
We can write the above expression as,
||
(
(T--
+
+ +0
+0
(49)
VTT
rT
T
This completes the proof for Corollary I.
21

---

Published as a conference paper at ICLR 2022
C ADDITIONAL DISCUSSIONS
C.I LEGM STORAGE CONSIDERATIONS
As discussed in Section 3, LBGM requires both server and workers store the last copy of the workers' look-back gradient (LBG). While storing a single LBG (same size as the model) at each device might be trivial since the space complexity increases by constant factor (i.e., the space complexity increases from O (M) to O (2M) O (M) where M is the model size), storage of LBGs at the server might require more careful considerations since it scales linearly with the number of devices (i.e., space complexity increases from O (M) to O (K M) where M is the model size and K is the number of workers). Thus, the storage requirements can scale beyond memory capabilities of aggregation server for very large scale federated learning systems. We, therefore propose the following solutions for addressing the storage challenge:
Storage Offloading. In a large scale federated learning system, it is realistic assume network hierarchy Hosseinalipour et al. (2020), e.g., base stations, edge servers, cloud servers, etc. In such cases the storage burden can be offloaded and distributed across the network hierarchy where the LBGs of the devices are stored.
LBG Compression. If the LBGM is applied on top of existing compression techniques such as Top-K, ATOMO, etc., the size of LBGs to be stored at the server also gets compressed which reduces the storage burden. Alternatively, we could use parameter clustering techniques (Son al., 2018; Cho al., 2021) reduce LBG size the server.
LBG Clustering. In very large scale federated learning system, say with billion workers, it's unrealistic to assume that all the billion clients have very different LBGs given the low rank hypothesis (H1) and possible local data similarities across the workers. It should therefore be possible to cluster the LBGs at the server into a smaller number of centroids and only saving the centroids of the clusters instead of saving all the LBGs of the devices individually. The centroids can be broadcast across the devices to update the local version of the LBGs.
C.2 HYPERPARAMETER TUNING
Most of the compression/commuicattoo savings baselines operate on a tradeoff between communi- cation savings and accuracy. For hyperparameter selection, we first optimize the hyperparameters for the base algorithm such that we achieve the best possible communication saving subject to constraint that accuracy does not fall off much below the corresponding vanilla federated learning approach. For example, we optimize the value of K in top-K sparsification by changing K in orders of 10, i.e. K 10%, K = 1%. K 0.1%, etc. and choose the value that gives the best tradeoff between the final model accuracy and communication savings (this value is generally around K 10%). Similarly, for ATOMO we consider rank-1, rank-2, and rank-3 approximations. While rank-1 approximation gives better communication savings, the corresponding accuracy falls off sharply. Rank-3 approximation gives only a marginal accuracy benefit over rank-2 approximation but adds considerably more communication burden. Thus we use rank-2 approximations in ATOMO. In the plug-ant -naa evaluations, the LBGM algorithm is applied on top of the base algorithms once their hyperparameters are tuned as a final step to show the additional benefits we can attain by exploiting the low-rank characteristic of the gradient subspace. Our chosen hyperparameters can be found in our code repository: https: ///g///itttt github.. com/ shams- sam/ FedOpt ttptiimm i..
D ADDITIONAL PSEUDOCODES
D.I PSEUDOCODE FOR PRELIMINARY EXPERIMENTS
In this Appendix, we provide psuedocode for generating the preliminary experimental results in Sec. 2. The actual implementation of the following function calls used in the pseudocode can be found the listed files of our code repository: https: / /githtb. com/ shams - sam/ FedOpt im:
get num PCA_ components: implemented in function estimate, optimal ncomponents, file: src/ src/common/ nb .utils.py of the repository. In summary, we stack the accumulated gradients over the epochs perform singular value decomposition, after which we do the standard analysis
22

---

Published as a conference paper at ICLR 2022
for estimating the number of components explaining given amount of variance in the datasets. Specifically, we count the number of singular values that account for the 99% and 95% of the aggregated singular values.
Pett_PCA_comoneent implemented in function cra_transform, file: src/common/ /noomooon/nb/n/ ri_utils.py the repository. summary, we stack the accumulated gradients over the epochs an perform singular value decomposition, after which components explaining a given amount of variance the datasets. Specifically, we recover the left singular vectors corresponding the singular values that account for the 99% and 95% of the aggregated singular values.
do the standard analysis for recovering the principal
implemented using functions aeaaan.ppeprocesinngnoommaaaaaa and numpy.dot, such that cosine_ wim.ssiimiiiiiiiieeee. b) normalize( dd) do (oeor) where a and b are numpy.are array, where normaliza performs the vector normalization and dot is the standard vector dot product.
cosine_ cosine_similatte similaritty
plot_1, 1, plot_2po_222 2, and plot_3 3: implemented in files src/vizzppreim__1.py prc/viz/prelimm. 2.py, and
pypp respectively.
Algorithm 2 Pscudocode for Preliminary Experiments in Section 2
I: Initialize model parameter (())
2:
Initialize actual grads = ()
store gradients for PCA & store ficomponents accounting for 95% variance
3: Initialize pca95 store
4:
Initialize pcaa9_storee
D store #components accounting for 99% variance
5: for to T do
b training for epochs
6:
Initialize (*) 0.
initialize gradient accumulator
7: Set (t.0)) - g())
8:
for b to B 1
B minibatches per epoch
Sample minibatch of datapoints from dataset D. Compute ((())) = Edes V ((((())) d)/lB).
10:
11:
Update parameter: ((+,b+1) (+.b6) n. (tM)
12:
Accumulate gradient: gd < g (16)
13:
end for
14:
Set (((+1) (tt.B)
15:
append accumulated gradient to store
16:
pca95_s iorissstoreesee arreed. get _um__CA tot__commoenttsactteee grads, variance 0.95))
17:
pca99_store.app append(get, num BCC_aumm__ACCACCCCCC components sactual Bacuualggrdddsa grads, variance = 0.99))
18: end for
19: plot 1ppca95 store, pca99 store)
> plot of PCA component progression
20: principal grads get PCA componenta (actual grads, variance 0.99)
21: heatmap zeros (arrrooollaat ppnpiricalll
22: for = len len(actual_gradee
do
23:
for j to lenpprinciaallgrraae _grads)__dd_ (odds)- - do
24:
heatmap/i, = cosine similarity(actuun [ pradcii) [raccipppp_rrad(]] 25: end for
26:
end
27: plot_ (hot_2(heammp))
>> plot of overlap of actual and principal gradients
28: heatmap zeroa[[en(actuaa_grrdd gradsl._grdds..ooe lenfcuallld((
29: = to den(actual_grada - do
30: for j i to len grads) 1 do
31:
heatmap/i, j] = heatmap j. i] cosine similarity(actual grads actual grads(j))
32:
end for end for
33:
34: plot_3(heatmap)
> plot of similarity among actual gradients
23

---

Published as a conference paper at ICLR 2022
D.2 PSEUDOCODE FOR DEVICE SAMPLING EXPERIMENTS
The pseudocode for LBGM with device sampling is given below. The process is largely similar to Algorithm I, except modifications in the global aggregation strategy. During global aggregation the server samples subset K" of all the available clients and receives updates from only those clients for aggregation as shown in line 15-17 of the Algorithm 3.
In terms of the effect of sampling on the unsampled devices, as long as an unsampled device that joins at later step of the training have fairly good look-back gradient (i.e., its newly generated gradient are close to its look-back gradient (LBG)), there is no need for transmission of the entire parameter vector. This would often happen practice unless the device engages in model training after very long period of inactivity, in which case it would need to transmit its updated LBG before engaging in LBGM communication savings.
Algorithm 3 LBCM with Device Sampling
Notation:
g²) global model parameter at glohal aggregation round f.
e(th)); model parameter at worker ks at global aggregation round t and local update b.
9 accumulated gradient worker & at global aggregation round t.
9 last full gradient transmitted to server, termed look-back gradient (LBG).
ag ( phase between the accumulated gradient gr and LBG g termed look-back phase (LBP).
Training at worker k:
1: Update local parameters: ((t.0) g(t), and initialize gradient accumulator: gk O.
for = to (T-1)
Sample minibatch of datapoints B& from D; and compute g (t.b) EdEB, (f ;d)|BBB)
(8.b) 4: Update local parameters: ((t.b+1) +- 0(. 9k (t.b) and accumulate gradient: g g + 1.6
5: end for
6: Calculate the LBP error: sin? (a (t)) - _ / (1g Ila
sin" 8
gthreshold then
checking the LBP error
Send sealar LBC to the server: Mi
P
(g 1
9: else
D updating the LBG
10: Send actual gradient to the server: p4 + 9
(t)
11: Update worker-copy of LBG: g < 9
(t)
12: end if
Global update at the aggregation server:
13: Initialize glohal parameter ()) and broadcast it across workers.
for = 0 (T 1) do
15:
sample set of indices K', a random subset from the pool of devices (1,2, K....
16:
Receive updates from workers {14 (t) IEEK.
17:
Update global parameters: ((++1) ((0)
27 ΣLEK' We (sx u gl + (1 SE) 1a
1, if f/l is scalar
where #y is an indicator function given by, 8
0, otherwise, i.e., if 14 is a vector
18:
Update server-copy look-back gradients (LBGs): gf + sx)sx) + (su)gi Ak K'.
19:
end for
24

---

Published as a conference paper at ICLR 2022
E ADDITIONAL PRELIMINARY EXPERIMENTS
We next present the additional experiments performed to test hypotheses, (H1) & (H2). As mentioned in Section 2, we study the cankcharacterissicc of centralized training using SGD on multiple datasets: FMNIST, MNIST, CIFAR-10, 10, CelebA, COCO, and PascalVOC, and model architectures: CNN, FCN, Resnet18, VGG19, and U-Net. Section E.I presents experiments complementary the one presented in Fig. 1, while Section E.2 & E.3 present experiments complementary to those presented in Fig. 2, & 3, respectively. Please follow the hyperlinks for the ease of navigating through the figures.
E.1 PCA COMPONENT PROGRESSION
Together with Fig. Figs. 10-13 show that both N99-PCA and N95-PCA are significantly lower than that the total number of gradients calculated during model training irrespective of model/dataset/leam- ing task for multiple datasets and models which all agree with (H1). Specifically, the principal gradients (i.e., red and blue lines in the top row of the plots) are substantially lower (often as low as 10% of number of epochs, i.e., gradients generated) in these experiments. Refer below for the details of the figures.
1. Fig. 9 repeats the experiment conducted in Fig. I on CIFAR-100 using FCN, CNN, Resnet18, & VGGI9.
2. Fig. 10 repeats the experiment conducted Fig. on MNIST using FCN, CNN, Resnet18, VGG19.
3. Fig. 11 repeats the experiment conducted in Fig. on FMNIST using FCN, CNN, Resnet18, & VGG19.
4. Fig. 12 repeats the experiment conducted in Fig. 1 CIFAR-IO, FMNIST, and MNIST using SVM, suggesting that we can use LBGM for classic classifiers that are not necessary neural networks.
5. Fig. 13 repeats the experiment conducted in Fig. on COCO, and Pascal using U-Net.
E.2 OVERLAP ACTUAL AND PRINCIPAL GRADIENT
Next, we perform experiments summarized in Fig. 14-35 to further validate our observation in Fig. 2: (i) cosine similarity of actual gradients with principal gradients varies gradually over time, and (ii) actual gradients have a high cosine similarity with below for the details of the figures. Each subplot is marked with #L, the layer number of the neural network, and #elem, the number of elements in each layer.
more of the principal gradients. Refer
In the plots with dense heatmaps (a large number gradients in along and y axis) for larger models such Fig. 14, it is harder to observe the overlap among the actual gradient and the PCA gradients. However, we can still notice the number of prinicipal components (along axis) is substantially lower than the total number of epochs gradients (along y axis). A better picture of gradient overlap with other gradients can still be seen in corresponding inter-gradien overlap plot in Fig. 36, which consistent with the corresponding PCA progression shown Fig. Note that the lesser number of prinicipal gradient directions (e.g.. CNN in Fig. 1) implies higher overlap among the generated gradients (e.g., CNN in Fig. 3), while larger number of PGDs (e.g.. VGG19 Fig. 1) implies lower overlap among generated gradients (e.g., VGG19 in Fig. 40).
1. Fig. 14 repeats the experiment conducted in Fig. 2 on CelebA using VGG19.
2. Fig. 15 repeats the experiment conducted in Fig. 2 on CelebA using Resnet18.
3. Fig. 16 repeats the experiment conducted in Fig. 2 on CelebA using FCN.
4. Fig. 17 repeats the experiment conducted in Fig. 2 on CelebA using CNN.
5. Fig. 18 repeats the experiment conducted in Fig. 2 on CIFAR-10 using VGG19.
6. Fig. 19 repeats the experiment conducted in Fig. 2 on CIFAR-10 using Resnet18.
7. Fig. 20 repeats the experiment conducted in Fig. 2 on CIFAR-10 using FCN.
8. Fig. 21 repeats the experiment conducted in Fig. 2 on CIFAR-10 using CNN.
25

---

Published as a conference paper at ICLR 2022
9. Fig. 22 repeats the experiment conducted in Fig. 2 on CIFAR-100 using VGG19.
10. Fig. 23 repeats the experiment conducted in Fig. 2 on CIFAR-100 using Resnet18.
11. Fig. 24 repeats the experiment conducted in Fig. 2 on CIFAR-100 using FCN.
12. Fig. 25 repeats the experiment conducted in Fig. 2 on CIFAR-100 using CNN.
13. Fig. 26 repeats the experiment conducted in Fig. 2 on FMNIST using VGG19.
14. Fig. 27 repeats the experiment conducted in Fig. 2 on FMNIST using Resnet18.
15. Fig. 28 repeats the experiment conducted in Fig. 2 on FMNIST using FCN.
16. Fig. 29 repeats the experiment conducted in Fig. 2 on FMNIST using CNN.
17. Fig. 30 repeats the experiment conducted in Fig. 2 on MNIST using VGG19.
18. Fig. 31 repeats the experiment conducted in Fig. 2 on MNIST using Resnet 8.
19. Fig. 32 repeats the experiment conducted in Fig. 2 on MNIST using FCN.
20. Fig. 33 repeats the experiment conducted in Fig. 2 on MNIST using CNN.
21. Fig. 34 repeats the experiment conducted in Fig. 2 on PascalVOC using U-Net.
22. Fig. 35 repeats the experiment conducted in Fig. 2 on COCO using U-Net.
E.3 SIMILARITY AMONG CONSECUTIVE GENERATED GRADIENTS
Furthermore, we perform experiments summarized in Fig. 36-57. Together with Fig. 3, these experiments show that there a significant overlap of consecutive gradients generated during SGD iterations, which further substantiates (H2) and bolsters our main idea that "gradients transmitted in FL can be recycled/reused to represent the gradients generated the subsequent iterations" " Refer below for the details of the figures.
1. Fig. 36 repeats the experiment conducted in Fig. 3 on CelebA using VGG19.
2. Fig. repeats the experiment conducted in Fig. 3 on CelebA using Resnet18.
3. Fig. repeats the experiment conducted in Fig. 3 on CelebA using FCN.
4. Fig. repeats the experiment conducted in Fig. 3 on CelebA using CNN.
5. Fig. 40 repeats the experiment conducted in Fig. 3 on CIFAR-10 using VGG19.
6. Fig. 41 repeats the experiment conducted in Fig. 3 on CIFAR-10 using Resnet18.
7. Fig. 42 repeats the experiment conducted in Fig. 3 on CIFAR-10 using FCN.
8. Fig. 43 repeats the experiment conducted in Fig. 3 on CIFAR-10 using CNN.
9. Fig. 44 repeats the experiment conducted in Fig. 3 on CIFAR-100 using VGG19.
10. Fig. 45 repeats the experiment conducted in Fig. 3 on CIFAR-100 using Resnet18.
11. Fig. 46 repeats the experiment conducted in Fig. 3 on CIFAR-100 using FCN.
12. Fig. repeats the experiment conducted in Fig. 3 on CIFAR-100 using CNN.
13. Fig. 48 repeats the experiment conducted in Fig. FMNIST using VGG19.
14. Fig. 49 repeats the experiment conducted in Fig. 3 FMNIST using Resnet18.
15. Fig. 50 repeats the experiment conducted in Fig. FMNIST using FCN.
16. Fig. 51 repeats the experiment conducted in Fig. 3 FMNIST using CNN.
17. Fig. 52 repeats the experiment conducted in Fig. 3 MNIST using VGG19.
18. Fig. 53 repeats the experiment conducted in Fig. 3 MNIST using Resnet 8.
19. Fig. 54 repeats the experiment conducted in Fig. 3 MNIST using FCN.
20. Fig. 55 repeats the experiment conducted in Fig. 3 MNIST using CNN.
21. Fig. 56 repeats the experiment conducted in Fig. PascalVOC using U-Net.
22. Fig. 57 repeats the experiment conducted in Fig. 3 on COCO using U-Net.
26

---

Published as a conference paper at ICLR 2022
F ADDITIONAL LBGM EXPERIMENTS
In this section, we present complimentary experiments to the properties studies in Section 4 of the main text. In particular, show that our observations hold for datasets: CIFAR-1O, CIFAR- 100, CelebA, FMNIST, and MNIST. We also present results when using shallower models FCN or deeper models & different from CNNs. Section F.I gives further evidence of utility of LBGM as standalone solution. Section F.2 lists figures that summarize the effect of changing k hhhesshlld on model performance for mentioned datasets and models. In Section F.3 we list figures that summarize additional experiments to support the observations made in Fig. 7 and Section F.4 lists figures for additional experiments corresponding to the observations made in Fig. 8. Finally, Section F.5 presents results on LEGM algorithm corresponding to the case wherein 50% of clients are randomly sampled during global aggregation. Since the two layer FCN considered is a simple classifier; does not perform well complex datasets such as CIFAR-1O, CIFAR-100, and CelebA. Thus, the respective results are omitted for FCN on these complicated datasets and the performance of FCN is only studied for MNIST and FMNIST datasets. Similarly, the 4-layer CNN architecture does not perform well on CIFAR-100 datasel and hence the corresponding results are ommited. We also preseni results using U-Net architecture for semantic segmenlation PascalVOC dataset.
F. LBGM A STANDALONE ALGORITIM.
1. Fig. 58 shows the result of repeating the experiment conducted in Fig. 5 (CNNs on non-iid data distribution) on CNNs for iid data distribution for datasets CIFAR-10, FMNIST, and MNIST, and U-Net for segmentation for dataset PascalVOC.
2. Fig. 59 shows the result of repeating the experiment conducted in Fig. 5 (CNNs on non-iid data distribution) on FCNs for both non-iid and iid data distributions on datasets FMNIST and MNIST.
3. Fig. 60 shows the result of repeating the experiment conducted in Fig. 5 (CNNs non-iid data distribution) on Resnet18, 8s for non-iid data distribution on datasets CelebA, CIFAR-10, CIFAR-100, FMNIST, and MNIST using setup similar to that of Wang al. (2018).
F.2 EFFECT OF b
gthreshold LBGM.
1. Fig. 61 shows the result of repeating the experiment conducted in Fig. 6 (CNNs on non-iid data distribution) on CNNs for iid data distribution for datasets CIFAR-10, FMNIST, and MNIST, and U-Net for segmentation for dataset PaScalVOC.
2. Fig. 62 shows the result of repeating the experiment conducted in Fig. 6 (CNNs on non-iid data distribution) on FCNs for both non-iid and iid data distributions on datasets FMNIST and MNIST.
3. Fig. 63 shows the result of repeating the experiment conducted in Fig. 6 (CNNs non-iid data distribution) on Resnet 88 for non-iid data distribution on datasets CelebA, CIFAR-10 and CIFAR-100 using setup similar that of Wang et al. (2018).
F.3 LBGM A PLUG-AND-PLAY ALGORITHM.
1. Fig. 64 shows the result of repeating the experiment conducted in Fig. 7 (CNNs non-iid data distribution) on CNNs for iid data distribution for datasets CIFAR-10, FMNIST, and MNIST.
2. Fig. 65 shows the result of repeating the experiment conducted in Fig. 7 (CNNs non-iid data distribution) on FCNs for both non-iid and iid data distributions on datasets FMNIST and MNIST.
3. Fig. 66 shows the result of repeating the experiment conducted Fig. 7 (CNNs on non-iid data distribution) Resnet18, 18s for non-iid data distribution datasets CelebA, CIFAR-10 and CIFAR-100 using setup similar to that of Wang et al. (2018).
F.4 GENERALIZZBILLTT OF LBGM TO DISTRIBUTED TRAINING.
1. Fig. 67 shows the result of repeating the experiment conducted in Fig. 8 (CNNs on non-iid data distribution) on CNNs for iid data distribution for datasets CIFAR- 10, FMNIST, and MNIST.
2. Fig. 68 shows the result of repeating the experiment conducted in Fig. 8 (CNNs on non-iid data distribution) on FCNs for both non-iid and iid data distributions datasets FMNIST and MNIST.
27

---

Published as a conference paper at ICLR 2022
3. Fig. 69 shows the result of repeating the experiment conducted in Fig. 8 (CNNs non-iid data distribution) on Resnet18s for non-iid data distribution on datasets CelebA, CIFAR-10 and CIFAR-100 using setup similar that of Wang et al. (2018).
F,5 LEGM UNDER CLIENT SAMPLING.
We present results with LBGM under client sampling in this subsection. The results are qualitatively similar to those presented in Sec. 4 under "LBGM as Standalone Algorithm". For example, our results on the MNIST dataset for 50% client participation shows 35% and 55% improvement in communication efficiency for only 0.2% and 4% drop in accuracy for the corresponding i.i.d and non-i.i.d cases (see column 1 of Fig. 71&70 respectively).
1. Fig. 70 shows the result of repeating the experiment conducted in Fig. 5 (CNNs on non-iid data distribution) under 50% client sampling using CNNs for non-iid data distribution for datasets CIFAR-10, FMNIST, and MNIST, and regression for dataset CelebA.
2. Fig. 71 shows the result of repeating the experiment conducted Fig. 5 (CNNs on non-iid data distribution) under 50% client sampling using CNNs for iid data distribution for datasets CIFAR-I0, FMNIST, and MNIST.
CIFAR-100 FCN
CIFAR-100 CNN
CIFAR-100 ResNet18
CIFAR-100
VGG19
#components
200
N99-PCA
150
150
N95-PCA
50
50
100
150
200
0
50
100
150
200
0
50
100
150
200
50
100
150
200
0.6
0.6
0.6
0.6
0.2
0.2
0.2
0.2
0.0
50
0.0
200
0.0
100
epoch
epoch
epoch
epoch
Figure 9: PCA Components Progression. Repeat of Fig. on CIFAR-100 dataset.
MNIST FCN
MNIST CNN
MNIST ResNet18
MNIST VGG19
100
100
100
100
#components
N99-PCA
75
75
75
75
N95-PCA
50
50
50
50-
25
25
25
25
75
0
25
75
0
50
1.00
1.00
accuracy
0.75
0.75
0.75
0.00
50
75
100
0.00
25
50
75
100
1.00
25
50 epoch
75
100
0.00
25
50
75
100
epoch
epoch
epoch
Figure 10: PCA Components Progression. Repeat of Fig. I on MNIST dataset.
28

---

Published as a conference paper at ICLR 2022
FMNIST FCN
FMNIST CNN
FMNIST ResNet18
FMNIST VGG19
150
#components
N99-PCA
100
100
100
N95-PCA
50
50
50
75
150
225
300
75
150
225
300
0
75
150
225
300
75
150
225
300
1.00
1.00
1.00
1.00
accuracy
0.75
0.73
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
150 epoch
225
300
0.00
75
150 epoch
300
0.00
225
300
0.00
75
150
225
300
epoch
epoch
Figure 11: PCA Components Progression. Repeat Fig. on FMNIST dataset.
CIFAR SVM
FMNIST SVM
MNIST SVM
20
accuracy #components
15
10
10
12
50
200
25
50
50
75
1.00
1.00
1.00
0.75
0.75
0.75
0.50
0.50
0.50
0.25
0.25
0.25
0.00
50
100 epoch
150
200
0.00
25
50 epoch
75
100
0.00
25
50
75
100
epoch
Figure 12: PCA Components Progression, Repeat of Fig. I on CIFAR-10, F-MNIST, and MNIST datasets but using squared SVM classifier.
COCO Segmentation
PascalVOC Segmentation
CE Loss #components
20
20
0
0
25
75
100
75
150
225
300
1.00
0.75
0.25
0.00
25
75
100
0
150 epoch
225
300
epoch
Figure 13: PCA Components Progression. Repeat of Fig. on COCO, PascalVOC datasets using U-Net classifier.
29

---

Published as a conference paper at ICLR 2022
CelebA, L#1
CelebA, L#2 #elem: 64
CelebA, L#3 #elem:
CelebA, L#4
CelebA, L#5 #elem: 36864
CelebA, L#6 #elem: 64
CelebA, L#7 #elem: 64
pca gradlents pca gradients pea gradients pea gradlents pca gradlents pca gradlents pca gradlents pea gradlents pea gradients pca gradlents
#elem: 1728
#elem: 64
L#8
100
L#9
L#10
100
L#11
L#
15
100
L#13
L#14
#elem: 73728
#elem:
128
#elem:
147456
25
L##15"
15
100
25
L416"
15
100
25
L#17
75
100
23
L#11
100
25
L#19
75
100
25,
LL220*
100
25
L
75 100
#telem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 256
#elem: 589824
"L#22""
100
L#23"
L#24
100
L#25
L#26
L#27
L$
75
#elem: 256
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
LM29
75 100
25
LM300
L#31
100
23
L#
25
LM33
75
100
34
100
25
50
75
100
0.6
#elem: 589824
#elem: 256
#elem:
#elem: 256
# #elem: 1179648
#elem: 512
#elem: 512
25
L.436
15
100
25
L#37
100
25
10
75
100
25
20
100
25
50
75
100
25
100
25
50
75
100
#telem: 512
Welem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
Welem: 512
L#43"
L#44
L#45
100
L#46
L#47
L#48
L#49
0.4
#elem: 512
#elem: 512
# #elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
L#550
100
L#51
75
L#52
75
100
23
LL55
25
L#54
75
100
L55
100
25
L#56
75
#elem:
#elem: 512
#elem:
#elem: 2359296
#elem:
#elem: 512
#elem: 512
25
100
25
75
100
25
75
100
6
25
20
100
25,
LL#61
75
100
25
50
100
25
L
75
100
02
#elem: 2359296
Welem: 512
#elem: 512
#elem: 512
# #elem: 2359296
#elem: 512
Welem: 512
L#64
L#65
L#66 #elem:
epoch gradients
epoch gradients
epoch gradients
epoch gradients
#elem: 512
#elem: 5170
75 100
25
50
100
epoch gradients
epoch gradients
epoch gradients
gradienss
Figure 14: PCA Components Overlap with Gradient. Repeat of Fig. 2 on VGG19 trained
CelebA dataset.
30

---

Published as a conference paper at ICLR 2022
CelebA, L#1
CelebA, L#2 #elem: 64
CelebA, L#3 #elem:
CelebA, L#4 #elem: 36864
CelebA, L#5 #elem: 64
CelebA, L#6 #elem: 64
CelebA, L#7 #eler:: 36864
pca gradlents pca gradients pca gradlents pca gradients pca gradients pea gradlents pea gradlents pca gradients
#elem: 9408
L#8
75
100
10 15
100
L#10
100
23
L#11
15
100
25
12
75
100
#13
100
25
L#14
15
100
jhelem:
stelem: 64
#eleem: 36864
#elem:
#elem:
#elem: 36864
#elem: 64
L#115
100
25
L#16
50
25
26
Lø17
30
75
100
23
L#18
25
50
15
100
L#20*
100
25
L#21
50
75 100
#Felem: 64
#elem: 73728
#elem: 128
#elem: 128
# #elem: 147456
# #elem: 128
#elem: 128
LA#22"
L#23
24
L#25
L#26
L447
L#28
128
147456
147456
0.6
25
L#29
15
100
25
L430"
75
100
23
10
75
100
23
20
100
25
70
75
100
25
#34
100
25
10
75
100
#elem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
Pelem: 589824
#elem: 256
L#36
L#37
L#38
100
L#39
L#40
L#41
75 L#42
#elem: 256
# #elem: 32768
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
#elem: 256
L#43
15
100
25
4444
75
100
10
75
100
25
100
25
50
75
100
448
100
25
50
15
100
#elem: 589824
#elem: 256
#elem: 256
Relem: 1179648
#elem: 512
#elem: 512
#elem: 2359296
L#550"
100
L#51
LB32
100
L#53
L#54
100
LL#55
25
L#56
10
75
100
#elem: 512
#elem: 512
# #elem: 131072
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
LW55
L#58
L#59
100
L#60
L#61
L#62
epoch gradients
pca gradients
#elem:
#elem: 2359296
#elem:
512
25
50
75
100
25
50
75
100
25
30
75
160
0
25
50
100
25
50 75
100 100
25
50
75
epoch gradients
epach gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 15: PCA Components Overlap with Gradient. Repeat of Fig. 2 on ResNet18 trained on CelebA dataset.
31

---

Published as a conference paper at ICLR 2022
CelebA, L#1 #elem: 30720
CelebA, L#2 #elem: 10
1.0
pca gradients
0.8
0.6
0.4
0.2
2
0.0
25
50
100
25
50
75
100
epoch
gradients
epoch gradients
Figure 16: PCA Components Overlap with Gradient. Repeat of Fig. 2 on FCN trained on CelebA datasct.
CelebA, L#1
CelebA, L#2 #elem: 20
CelebA, L#3 #elem: 25000
CelebA, L#4
pca gradients
#elem: 1500
#elem: 50
1.0
0.8
75
100
100
0.6
L#5
L# 6
L#
L#8
#elem: 625000
#elem: 500
#elem: 5000
#elem: 10
pca gradients
0.4
0.2
0.0
75 100
25
50
100
75 100
25
50
100
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 17: PCA Components Overlap Gradient, Fig. on CNN trained on CelebA dataset.
32

---

Published as a conference paper at ICLR 2022
CIFAR-10,
CIFAR-10, 1.#7
CIFAR-10, # #elem:
CIFAR-10, 144
CIFAR-10, #5
CIFAR-10, 10, 1$6
CIFAR-10, 10, 1
pea gradients
thelem: 1728
#elem: 64
#elem: 64
ttelem: 36864
#elem:
#elem: 64
1312 9 3
200302 840
5o
100 150
200
50
L#9
150 200
150
200
50,
100
200
50
100 150 200
0
50
L#13
150
200
50,
L#114
200
pea grad letts pea gradients
#telem: 64
Welem: 73728
#elem: 128
#elem: 128
#elem: 128
#elem:
147456
#elem: 128
L##15
L#16
550
L#18
L#19
L#
L 150
#elem: 128
#elem: 128
*elem: 294912
#elem: 256
#elem: 256
#elem: 256
# #elem: 589824
50 100 150
50
L#23
130 200
L#24
200
50
L#25
150
LW
700
L#2 7
50
L#28
150
pca gradients
#elem: 256
#elem:
589824
#elem:
50 100 150 200
90
100
150 200
100 150 200
50
100
130 200
50
100
150
200
0
50
100
150
200
90
120
150
200
pea gradlents pca gradients
#eelem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 1179648
#elem:
512
#elem: 512
"L"33""
LW37
130
200
LW38
LW#39
L
150 200
LL441
100
50.
L$42
#eeee:: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
56 104
L#44
L#44
L#46
100
L#48
12 150
0.4
pca gradients pea gradients pca gradients
#telem: 512
#elem: 512
lelem: 2359296
Welem: 512
#elem:
#elem: 512
Melem: 2359296
5o 100 150
200
50
100
150 200
100
150 200
50
100
150
200
100
150 200
50
100
150 200
50
L#35
150
200
#teee: 512
#elem: 512
#elem:: 512
# #elem:: 2359296
#elem: 512
#elem: 512
#elem: 512
20002 0.0
50 100 150
LL#57
50
LW58
1.50
150 200
L#59
150
200
50
L#60
100
150
50
150 L#61
100
200
50
100
150 200
50 1.0 350 200
L#63
#éelem: 2359296
#elem: 512
#elem: 512
#clem: 512
#elem: 2359296
#clem: 512
#elem: 512
18022
LL#64
LW65
L# #elem:
epoch gradients
epoch gradients
epoch gradients
epoch gradients
pca gradients
##elem: 512
#elem: 5120
100
50 150 130 200
200
epoch gradients
epoch gradients
epoch gradients
Figure 18: PCA Components Overlap with Gradient. Repeat of Fig. 2 on VGG19 trained on CIFAR-10 dataset.
33

---

Published as a conference paper at ICLR 2022
CIFAR-10, L#1
CIFAR-10, L#2
CIFAR-10, L#3
CIFAR-10, L#4 #elem: 36864
CIFAR-10, L#5
CIFAR-10, L#6
CIFAR-10, L#7
pca gradients
#elem: 9408
#elee:: 64
#elem: 64
#eeeem: 64
#elem: 64
#elem: 36864
23185 0633
L#8
L#9
L#10
200
50
L#11
130
L#12
700
L#11
130
L#14
350
pca gradlents
#elem:
#elem: 64
#elem:
#elem:
50
100
150
200
50
100
150 200
100
150 200
50
100
150
200
50
100
150
200
50
105
150
200
50
100
250
200
0.8
pea gradients pea gradlents
#elem: 64
#elem: 73728
#elem: 128
#elem: 128
#elem: 147456
#elem: 128
# #elem: 128
5c 150
L#23
150
L#
450
150
L#255
L#26
L#
755
##elem: 8192
#elem: 128
#elem:: 128
#elem: 147456
#elem: 120
#elem: 128
#elem: 147456
50 100 150 200
50
LA330
150
200
50
L#331
150 200
50
LW332
150
200
50
L##33
150
200
50
100
150
200
50
130
200
pea gradlents
##elem: 128
#elem: 128
#elem: 294912
#elem:
256
#elem:
589824
256
50 100 150
200
50
100
200
L#38
100
150
200
50,
L#39
100
150
200
100
150
200
50
100
150
200
50
1,0 150 200 L#42
pca gradlents
#elem: 256
#elem: 32768
#elem: 256
#clem: 256
#elem: 589824
# #clem: 256
# #elem: 256
56 "L#43
150
L#44
L##45
100
L#46
LL#48
50 g
pca gradients
589824
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
#elem: 2359296
50 100 150
200
50
100
150
200
L
150 200
50
1.0
150
200
50
L##54
150
200
50
100
150
200
50
L49
150
200
02
gradients gradients
.telem: 512
#elem: 512
#elem: 131072
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
18-00 9:8
28.0022 840
50. 100
"L#57"
50
LW58
130
150
700
L#59
50
LM600
102
150
L#61
160
150
200
L##62
100
epoch gradients
50
150 150 700
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 5120
#elem: 10
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 19: PCA Components Overlap with Gradient. Repeat Fig. ResNet18 trained on CIFAR-10 dataset.
34

---

Published as a conference paper at ICLR 2022
CIFAR-10, L#1 #elem: 30720
CIFAR-10, L#2
#elem: 10
pca gradients
12
24
0.8
36
48
0.6
60
72
0.4
84
96
108
0.2
120
50
100
150
200
0
150 epoch gradients
50
100
200
epoch gradients
Figure 20: PCA Components Overlap with Gradient. Repeat of Fig. 2 on FCN trained on CIFAR-10 dataset.
CIFAR-10, L#1
CIFAR-10, L#2 #elem: 20
CIFAR-10, L#3 #elem: 25000
CIFAR-10, L#4
#elem: 1500
#elem: 50
pca gradients
1.0
0.8
50 100
150
200
50
100
150
200
50
100
150
200
50
100
150
200
0.6
5#5
L#6
L#7
L#8
pca gradients
#elem: 625000
#elem: 500
#elem: 5000
#elem: 10
0.4
7 0343210
0.2
0.0
50
150 200
100
200
150 epoch gradients
200 epoch gradients
50 100 150
epoch gradients
epoch gradients
Figure 21: PCA Components Overlap with Gradient. Fig. 2 on CNN trained CIEAR-10 dataset.
35

---

Published as a conference paper at ICLR 2022
CIFAR-100, 1
CIFAR-100, +2
11FAR-100,11 #3
CIFAR-100, 1#44
CIFAR-100, +55
CIFAR-100, 16
CIFAR-100, +77
pea gradients Shsssti
thelem: 1728
#elem: 64
#elem::
#telem: 64
#ellm: 36864
#elem:
#elem: 64
1,0
50 100 150
200
50
100
150
200
L
150 200
50
100
200
50
LL#12"
150 200
50
102
150
200
50
L#14
200
pca gradients pca gradients
#telem: 64
Belem:: 73728
#elem: 128
#elem: 128
#elem: 128
Pelem: 147456
# #elem: 128
50 5
L116 150
L#17 750
L#18
"L
L#
L#
#elem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 256
# #elem: 589824
30000
50 150
'##22
50
LW23
130 200
50
L#24
150 200
50
L#25
150
LW#26
150
200
50
L#227
150
50,
L#28
150
200
pea gradlents pca gradlents gradients
#elem:: 256
#elem: 256
#elle:: 589824
#elem:
#elem: 256
50 100 150 200
50
130 150 200
"L#31"
150 200
50
100
150
200
50
100
150
200
50
100
150
200
50
1:0
150 200
#telem: 589824
#elem: 256
#elem: 256
#elem: 256
Pelem: 1179648
#elem:
512
#elem: 512
LL#36"
50
L#37
150
L#38
LL439
L..200
200
L#41
100
50,
1/2
#telem: 512
Helem: 2359296
#elem: 512
#elem: 512
#eeem: 512
Welem: 2359296
#elem: 512
50
LL#43
150
L#44
#45
L#46
150
L#447"
100
L#49
pca gradients
#elem:
2359296
#elem:
2359296
50
100 15c
200
30
150
150 200
150 200
50
1.0
150
700
50
100
150 200
0
50
100
150
200
50
L
150 200
gradients
#elem: 512
#elem: 512
#elem: 512
# #elem: 2359296
#elem: 512
#elem: 512
#elem: 512
62
30 LB
150 200
Lg 200
150
200
50 110
200
LL#57
L#61
pca gradlents
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
Pelem: 2359296
#elem: 512
#elem: 512
100 150
L#65
1000 #elem: 100
epoch gradients
epoch gradients
epoch gradients
epoch gradients
gradients
512
51200
100
50
150 150 200
100 150 200 epoch gradients
epoch gradients
epach gradients
Figure 22: PCA Components Overlap with Gradient. Repeat of Fig. 2 on VGG19 trained on CIFAR-100 dataset.
36

---

Published as a conference paper at ICLR 2022
CIFAR-100, L#1
CIFAR-100, L#2
CIFAR-100, L#3
CIFAR-100, L#4 #elem: 2304
CIFAR-100, L#5
CIFAR-100, L#6
CIFAR-100, L#7
pca gradients Bstisioerss..
#elem: 432
#elem: 16
#elem: 16
#elem: 16
#elem: 16
#elem: 2304
121 6
170
LPB
LØ9
19 25
L#111
L#
150
L#113"
150
LL#14"
pea gradients
#eeee:: 16
#elem: 16
#tllem: 2304
#elem:
#elem: 16
#elem: 2304
#elem:
320 8 8.423
59
"L#15"
150
200
50
100
150
200
30
LL#17
150
200
"L#18"
150
200
L#19
150
200
50
"L#20"
150
L#21
150 200
pca gradients
#elem::
#ellem: 4608
#elem:
#elem:
#elem: 9216
#elem: 32
#elem:
20852 9610
18532 9630
50 L11222
150
200
50
L423
200
30
1:0
200
30
L
150
200
50
100
150
200
50,
L4427
200
50
100
200
L#
pca gradients
#telem: 9216
#eelem: 32
#eelm:: 32
#elem: 9216
#elem: 32
#elem: 32
#elee:: 18432
20R92 11822900 9618
L##29
L#30
1/9
150
L433
350
L#
10 150 200
pca gradients
(telem: 64
#elem:: 64
Welem: 36864
Welem:: 64
#elem: 64
Melem: 36864
#elem: 64
L#33
37
150
L#38
L#39
L#400"
150
L#41
L#42
150
pca gradients
#elem:
36864
#elem:
#elem: 7372B
128
100 150 200
50
100
150
200
30
160
150
200
1.0
150
200
0
50
100
150 200
50
100
150
200
50
10c 150 200
pca gradients
#Kelem: 147456
#elem:
128
#elem: 128
#elem: 147456
#elem: 128
#elem: 128
#ellem:
147456
LA80 350 200
50
150 150
150
150
200
1.0
150
200
50
100
150
200
50
100
150
100
150
203
LW51
L#53
pca gradients
#elem: 128
#elem: 128
#elem: 12800
#elem: 100
225 555000700
Figure 23: PCA Components Overlap with Gradient. Repeat Fig. on ResNet18 trained on CIFAR-100 dataset.
37

---

Published as a conference paper at ICLR 2022
CIFAR-100, L#1
CIFAR-100, L#2 #elem: 100
#elem: 307200
1.0
pca gradients
16
2
32
4
0.8
48
6
64
8
0.6
80
10
96
12
0.4
112
14
128
0.2
144
18
160
20
0.0
50
100
150
200
150 epoch gradients
50
100
200
epoch gradients
Figure 24: PCA Components Overlap with Gradient. Repeat of Fig. 2 on FCN trained on CIFAR-100 dataset.
CIFAR-100, L#1
CIFAR-100, L#2 #elem: 20
CIFAR-100, L#3 #elem: 25000
CIFAR-100, L#4
#elem: 1500
#elem: 50
pca gradients
1.0
32
48
80
0.8
96
10
112
12
14
100
200
100
200
100
200
16
100
200
0.6
L#5
L#6
L#7
L#8
pca gradients
#elem: 625000
#elem: 500
#elem: 50000
#elem: 100
0.4
14
56
70
0.2
98
150 200
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 25: PCA Components Overlap with Gradient. Fig. 2 on CNN trained CIFAR-100 dataset.
38

---

Published as a conference paper at ICLR 2022
FMNIST, 1#1
FMNIST, 1.#2 #telem: 64
FMNIST, #ellm::
FMNIST, 1-44
FMNISTT #5
FMNIST, #6 #eeem:
FMMNIST, 1#7
pca grad lents gradients pea gradients
#telem: 576
#eeem: 64
#telem: 36864
#elem: 64
G00 8 4.0
543213
25 L
100
25
LWg
75
100
L#100
100
25
56
75
100
25
20
75
100
25
L
100
25
L4114
75
150
#telem: 64
#elem: 73728
#elem: 128
#elem:: 128
#elem: 128
#elem:: 147456
Welem: 128
1220
22 L#115
L#16
L#18
L
100
L#20
L#21
#eleem: 128
#elem: 128
*elem: 294912
#elee:: 256
#elem: 256
#elem: 256
# #elem: 589824
22 L##22
25
L#23
15
100
L#24
23 L#25
2
LL#26
100
L#27
15
25
L#28
75
pca gradients
#elem: 256
#elem:
#elem:
589824
22
LA#29
75
100
25
50
75
100
30
100
25
50 75
100
25
50 75
100
29
50
100
25,
50
75
100
pca gradients pea gradlents pca gradients
#eeeem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
L.036""
LWW37
100
L#38
LW
4#
100
L#41
L#442
#eelem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
25 LL443
L444
L#44
25
L#446
L##47"
L#48
L#449
75
0.4
#telem: 512
Ielem: 512
Welem: 2359296
#elem: 512
#elem:
#elem: 512
#elem: 2359296
25 LL430"
100
25
50
15
100
L
100
25
L#53
100
L#54
75
100
25
50
100
25
L#56
75 100
pca gradients pea gradients
#telem: 512
#elem: 512
#elem:: 512
# #elem:: 2359296
#elem:
512
#elem:
512
#elem: 512
18552 9 6633
220
22
L.#57"
25
L#338
15
100
L
100
25
L#600
50
75
10c
25
L#61
50
75
100
25
L#62
50
100
25
L#63
50
100
#eele:: 2359296
#elem: 512
#elem: 512
#clem: 512
#elem: 2359296
#clem: 512
#elem: 512
Ro
"L#64
L#65
L@ #elem:
epoch gradients
epoch gradients
epoch gradients
epoch gradients
pca gradlents
#elcem: 512
#elem: 5120
50
100 75
100
epoch gradlents
epoch gradients
epoch gradients
Figure 26: PCA Components Overlap with Gradient, Repeat of Fig. 2 on VGG19 trained on EMNIST dataset.
39

---

Published as a conference paper at ICLR 2022
FMNIST, L#1
FMNIST, L#2
FMNIST, L#3
FMNIST, L#4 #elem: 36864
FMNIST, L#5
FMNIST, L#6
FMNIST, L#7 #elem:: 36864
pca gradlent letts
#elem: 3136
#elem:: 64
#telem: 64
#telem: 64
Welem: 64
20302 8.00
12
L#9
100
L#10
23 L#11
L#
100
L#13
L#14
pca gradlents
#elem: 64
#elem:
LL115"
100
25
LA116
75
100
L#17
75
100
25
LL418"
75
100
25,
L#11
75
100
25,
"L420*
100
25.
L
75
100
0.8
pca gradients pca gradients
#elem: 64
#elem: 73728
#elem: 128
#elem: 128
#elem: 147456
#elem: 128
#elem: 128
22 "L#22"
LA
L#
L#25
L#26
100
L#27
L#28
#elem:: 8192
#elem: 128
#elem: 128
#elem: 147456
#elem: 120
#elem: 128
#elem: 147456
21 LL#29
25
LA430"
75
100
25
L#31
100
25
L#32
75
100
L3
75
100
25
L#334
100
25.
L#35
75 100
pea gradients
##elem: 128
#elem: 128
#elem: 294912
#elem:
256
#elem:
#elem: 589824
#elem: 256
22 LL.36"
100
25
L.737
75
100
L
100
25
LL439"
75
100
25
L#400
75
100
25
90
100
25
L#42
50 75
100
pca gradients pca gradlents
#elee:: 256
#elem: 32768
#elem: 256
#clem: 256
#elem: 589824
# #clem: 256
#elem: 256
25,
L#449 75
LL443
L#44
L##4
L#46
47
LL#48
589824
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
#elem: 2359296
1508 Stte
23
LL#50"
100
25
50
75
100
L
100
25
45
75
100
L#54
75
100
25
L#35
100
25
L#456
75
100
02
pca gradlents gradients
.telem: 512
#elem: 512
#elem: 131072
#elem:
512
#elem: 512
#elem: 2359296
#elem: 512
2" 'L#57"
LWW5
75
100
L#59
100
75
6#
L#61
75
160
LW#62
100
epoch gradients
25
50
160
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 5120
#elem: 10
epoch gradients
epach gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 27: PCA Components Overlap with Gradient. Repeat Fig. on ResNet18 trained on FMNIST dataset.
40

---

Published as a conference paper at ICLR 2022
FMNIST-10, L#1 #elem: 7840
FMNIST-10, L#2 #elem: 10
1.0
pca gradients
0.8
0.6
0.4
0.2
0.0
25
50
100
25
50
75
100
epoch
gradients
epoch gradients
Figure 28: PCA Components Overlap with Gradient. Repeat of Fig. 2 on FCN trained on FMNIST dataset.
FMNIST-10, L#1
FMNIST-10, L#2 # #elem: 20
FMNIST-10, L#3 #elem: 25000
FMNIST-10, L#4
#elem: 500
#elem: 50
pca gradients
1.0
0.8
25
100
100
0.6
L#5
L# 6
L# #
L#8
pca gradients
#elem: 400000
#elem: 500
#elem: 5000
#elem: 10
0.4
87 066433210
0.2
0.0
75 100
25
50
100
75 100
25
50
100
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 29: PCA Components Overlap with Gradient. Fig. CNN trained on FMNIST dataset.
41

---

Published as a conference paper at ICLR 2022
MNIST, 1+1
MNIST, #2 itelem: 64
MNIST, #3 #elem:
MNIST, 1
MNIST, #5 #elem: 36864
MNIST, 1 #elem:
MNIST, #7
pca gradients pca gradlents pea gradlents pea gradients pca gradlents pea gradlents pea gradients pca gradients pea gradlents pea gradients
#teem: 576
#elem: 64
#elem: 64
1.0
L#8
100
25
25
L#100
100
L#112
15
100
L#11
100
25
20
75
100
#Felem: 64
# #elem: 73728
#elem: 128
Belem: 128
#elem: 128
#elem: 147456
#elem: 128
L#16
L#17
L#18
19
L#20
L#21
#tele:: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 256
#elem: 589824
25 "# 15 100
25 L#233 15 100
L#24
75
100
23
L$255
75
100
25
L#266
75
100
25,
L422
75 100
25
L#28
75 100
#telem: 256
#elem: 256
#eelm: 256
Welem: 589824
#eleem: 256
#elem:: 256
Welem: 256
L##29
100
25
L#30
15
25
L#311
75
100
23, 30
25
LW33 15 100
L#334
100
25 L#35
75 100
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
LW#36"
LW337"
LB
23 L#39
25 L#440"
L#441
L#42
#telm: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
25 LL#43"
15 100
25
L#44
75
100
L#45
75
100
25 20
100
25
50
75
100
25
L48
100
25 50 75 100
L#49
#telem: 512
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
25 50
100
25
L#511
50
15
25
L
75 100
23
L#53
25 50
L##54
75
100
LL#55
100
25 50 25
100
#eelem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
LL#57"
L455
L9
L#
25
L#61
75
L462
25,
LB63
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
L##64
75
100
25
50
15
100
L#06 #elem:
25
75
100
epoch gradients
50
100
epoch gradients
25
50
75
100
epoch gradients
100
epoch gradients
25 50
75 100
#elem: 512
#elem: 5120
0.0
100
25 epoch gradients
160
epoch gradients
epoch gradients
Figure 30: PCA Components Overlap with Gradient. Repeat of Fig. 2 on VGG19 trained MNIST dataset.
42

---

Published as a conference paper at ICLR 2022
MNIST, L#1 3136
MNIST, L#2
MNIST, L#3
MNIST, L#4 36864
MNIST. L#5
MNIST, L#6 #elem:
MNIST, L#7
#elem:
pca grad
1512 9 9630
1512 9322966 960
20062 01822844
21
10
75
100
75
10
75
100
25
LW110"
100
25
56
75
100
25
10
75
100
25
LW113
100
25
10 75
gradients
#eleem: 64
#elem: 64
#elem: 36864
#elem: 64
#elem:
#elem: 36864
#elem: 64
18852 9630
18852 9630
1210 8642002
2312
L#215
L6
100
L#117
LL#16
L'
100
"L.20
L#21
75
pca gradients gradients pca gradients
:telle:: 64
#elem: 73728
#eeemm 128
#elem: 128
#elem: 147456
#telem: 128
#elem: 128
280022 840
22 LL#22
25
LW#23
100
L##24
100
23
"L#26
100
L#27
25 L#28
8192
#elem:
#elem:
147456
#elem:
#elem: 128
#elem: 147456
18831 963
20892 9630
0.8
22 LL229
75
100
25
X0
100
L+
75
100
25
L432
75
100
25
L#333"
75
100
25,
L#334"
100
25,
10 75
100
#telem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 589824
# #elem: 256
120 930 26
1512 9
20032
LL#36
L#37
L#38
L#39
L#400
100
L#41
L#42
pca gradients
#ellem: 256
#elem: 32768
#Fele:: 256
#elem: 256
#elem: 589824
#elem: 256
#elem: 256
1857 9837
1852 018229633 9630
139 9 6.635
23 "L443"
25
L4
75
100
L
100
25
L#446
75
100
25
L#477
75
100
25
LL448
100
25,
L#449 75 100
pca gradients pca gradients gradients
#teem:: 589824
# #elem: 256
#elem:
#ellm:: 1179648
#elem:
#elem: 512
#elem: 2359296
3280
22 "L2300" 75
100
25
L1
75
100
$$$322
100
25
33
75
100
25
50
75
100
25 50
100
25 L9
75
100
##elem: 512
#elem: 512
#elem: 131072
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
LL#57
L#55
L#59
25 L#
L#61
L##2
epoch gradients
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 5120
#elem: 10
0.
0
50
100
25
50
75
100
100
0
25
50
75
10c
50 75
100
0
25
50 103
epoch gradients
epach gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 31: PCA Components Overlap with Gradient. Repeat of Fig. 2 on ResNet18 trained on MNIST dataset.
43

---

Published as a conference paper at ICLR 2022
MNIST, L#1 #elem: 7840
MNIST, L#2 2 #elem: 10
1.0
pca gradients
0.8
2
0.6
3
0.4
0.2
2
0.0
25
50
100
50
75
epoch
gradients
epoch gradients
Figure 32: PCA Components Overlap with Gradient. Repeat of Fig. 2 on FCN trained on MNIST dataset.
MNIST, L#1
MNIST, L#2
MNIST, L#3 #elem: 25000
MNIST, L#4
pca gradients
#elem: 500
#elem: 20
#elem: 50
0.8
4
50
100
75
25
75
100
100
0.6
L#
L#6
L#
L#8
pca gradients
#elem: 400000
#elem: 500
#elem: 5000
#elem: 10
0.4
0.2
0.0
50
100
75
100
25
75
100
100
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 33: PCA Components Overlap with Gradient. Fig. CNN trained on MNIST dataset.
44

---

Published as a conference paper at ICLR 2022
PascalVOC, #1
PascalVOC, #elem: 22
PascalVOC, 1
PascalVOC, #4
PascalVOC, 1#5
PascalVOC, 146
PascalVOC, 1
pca gradlents pca gradlents pea gradients
#elem:
#telem:
#elem: 32
itelem; 9216
#elem: 32
#elem: 32
2210 e 220
1.
100
25
50
15
L#100
100
LL#11
LL#12
15
100
LL113
L
100
#Felem: 32
#elem: 32
#elem: 32
#elem: 18432
#elem: 64
#elem: 36864
#elem: 64
30 6 4 20
1854321
NM0 3000
L#411
23 L#
"L #elem:
" L#18
LW
25 L#400
23
L#
##elem:
#elem: 64
#elem: 64
#elem: 73728
#elem: 128
#elem: 147456
120 9 86 0
25 LL#22
15
100
25 L4423"
100
L#24
75
100
23
L#25
100
25
00
75
100
25
L427
25
100
25:
L$28
75 100
pca gradients pca gradlents pea gradlents pea gradients pca gradients pea gradlents pea gradients
#telem: 128
#eeem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 294912
Welem: 256
L#29
100
25 50 15
25
L
75
100
23, 30
25
L#
50
15
100
L#344
100
25 50
100
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 131072
20
-30 86
5543210
8
90
L#36
25 LWW37" 15
1
23
L#39
L#400
L#41
L#42
#elem: 128
#elem: 32768
#elem: 128
#elem: 294912
#elem: 128
#elem: 147456
#elem: 128
25
L##43"
15 100
25
L444
75
100
10
75
100
25
L#46
100
25
50
75
100
25
448
100
25 50
75
100
#eeem:: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 32768
L##50
100
25 50 15
L#51
25
L#
75
100
23
L#53
25
L#54
50
15
100
L#55
100
25 50
75
100
##elem: 64
#elem: 8192
#elem: 64
#elem: 73728
#elem: 64
#elem: 36864
#elem: 64
25_ L4457"
25 43
25
25 30
25,
10 75
L#60
LL422
##eeem:
#elem: 64
#elem:
#elem: 64
#elem: 64
#elem:
#elem: 8192
L##64
75
100
25
50
100
L#06
75
100
25
L#67
100
25
50
79
100
50
100
spocil-arRtic #elem: 32
25
50 100
#Felem:
#elem: 2048
#elem:
#elem: 18432
#elem: 32
#elem: 9216
0.0
100
25 epoch gradients
160
25
50
100
25 50
100
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 34: PCA Components Overlap with Gradient. Repeat of Fig. U-Net trained PascalVOC datasct.
45

---

Published as a conference paper at ICLR 2022
COCO, 1
COCO, 1#2 #elem: 2
COCO, #3 #eeem:
COCO, 1 #elem: 32
COCO, 1 irelem 9216
COCO, 1#6 #elem: 32
COCO, #7
pca gradients pca gradlents pea gradlents pea gradients pca gradients pea gradlents pea gradients pca gradients pca gradlents pea gradlents
Welemm:
#elem: 32
1.
100
25
15
L#10
160
L#11
15 100
L#13
100
20
#Felem: 32
#elem: 32
#elem: 32
#elem: 18432
#elem: 64
#elem: 36864
#elem: 64
LL#15"
L#16
L#17
L#18
LM
L#20
L#21
##elem:
#elem: 64
#elem:
#elem: 64
#elem: 73728
#elem: 128
#elem: 147456
25
L##22 15 100
25 L#233
100
L#24
75
100
23
L#25
100
25
00
75
100
25
L427
75
100
25 50
75
100
#telem: 128
#eeem: 128
eleem: 128
#elem: 128
#elem: 128
#elem: 294912
Welem: 256
L##9
15 100
25 50 15
25
L#31
75
100
23
25
L#
50
15
100
L4334
100
25 50
100
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 131072
L#336"
3M
LA38
23
L#39
L#400
L841
L#42
#elem: 128
#elle:: 32768
#elem: 128
#elem: 294912
#elem: 128
#elem: 147456
#elem: 128
25
LL#43 15 100
25
L444
15
100
10
75
100
25
L#46
100
25
50
75
100
25
#48
100
25 50 75 100
#telem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 32768
L#550
100
25 50 15
L#51
25
L#52
75
100
23
L#53
25
L#54
50
75
100
L#55
50
100
25 L
75
100
##elem: 64
#elem: 8192
#elem: 64
#elem: 73728
#elem: 64
#elem: 36864
#elem: 64
25_
L#457"
25 L455
Lg
23
L#60
25 30
L462
25,
L#63
##elem:
#elem: 64
#elem:
#elem: 64
#elem: 64
#elem:
#elem: 8192
L##64
75
100
25
50
100
L#06
75
100
25
L#67
100
25
50
79
100
L#09
100
epocil Broiients #elem: 32
25 50
100
#Felem:
#elem: 2048
#elem:
#elem: 18432
#elem: 32
#elem: 9216
100
25 epoch gradients
160
50
15 100
25 epoch gradients
50
100
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 35: PCA Components Overlap with Grudient. Repeat Fig. on U-Net trained on COCO dataset.
46

---

Published as a conference paper at ICLR 2022
CelebA, 1 #telem: 1728
CelebA, 1+7 itelem: 64
CelebA, 1 #elem:
CelebA, #4 #elem: 64
CelebA, L #eeem: 36864
CelebA, #6 #elem:
CelebA, 1 #elem: 64
epoch grad letts
25
R
R
75
75
100
0
25
50
75
100
00
10
75
100
23
30
100
25
50
15
100
25
100
25
50
15
100
L#10
12
epoch gradlents
#kelem: 64
Al Welem: 73728
ellem: 128
Welle:: 128
Welem: 128
Velem: 147456
#lelem: 128
1p
10
X
4
50
15
100
25
50
15
100
80
25
10
75
100
23
50
100
20
25
50
75
100
100
80
25
50
75
100
L#15
L#16
L#17
L#118
L#
L#20
L#
epoch gradlents
#elem: 128
#elem: 128
#elem: 294912
#elem:: 256
#elem: 256
#elem: 256
#elem: 589824
8
8
8
R
16
190
80
8o
L#22
L#23
L# 24
L#25
L#26
L#2
L #28
epoch gradlents
#elem:
256
#elem:
#elem: 589824
#elem:
#elem:
#elem:
15
X0
10
R
50
R
3
75
75
100
25
75
100 20
25
50
100
25
50
75
100
100
25
10
75
100
L#29
L#30
L3
epoch gradlents
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
25
X
10
80
50
75
R
10
25
50
75
100
2
25
50
75
100
20
25
10
75
100
80
25
50
100
80
25
50
75
100
8
25
100
25
50
75
100
L#36
L#37
L 38
L#
L#40
L#41
L#42
epoch gradlents
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
35
X2
25
59
R
R
50
180
100
25
g0
100
g0
20
50
100
189
80
25
50
75
L#43
L444
L#45
L#46
L#47
L#48
L#49
epoch gradients
#tlem:
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
25
58
8
50
75
80
100
L#50
L#51
L#52
L#53
L#54
L#55
L#56
epoch gradlents
#elem:
#elem: 512
#eeem::
#elem: 2359296
#elem:
#elem: 512
#elem: 512
25
25
75
75
75
100
25
50
75
100
@0
10
75
100
Eo
23
30
100
25
50
75
100
100
25
50
75
100
L
L#61
epoch gradlents
#elem:: 2359296
Welem: 512
#eeem: 512
Welem: 512
#elem: 2359296
#elem: 512
Wlelem: 512
25
X
50
R
15
L#64
100
6#
So
L#66
100
So
epoch gradients
2o
epoch gradients
75
100
8
epoch gradlents
83
50 75 epoch gradients
25
100
epoch gradients
#elem: 512
#elem: $120
#elem:
50
5
0.0
20
go
50
epoch gradients
epoch gradients
epoch gradients
Figure 36: PCA Components Overlap with Gradient. Repeat of Fig. 3 on VGG19 trained on CelehA dataset.
47

---

Published as a conference paper at ICLR 2022
CelebA, L#1
CelebA, L@2 #elem: 64
CelebA, L#3 #elem:
CelebA, L#4 #elem: 36864
CelebA, Ld55 #elem:
CelebA, L#6 #elem:
CelebA, L#7 #elem: 36864
epoch gradlents
#elem: 9408
1.
25
R
2
75
75
75
100
25
50
15
100
00
30
100
23
30
75
100
25
50
75
100
25
100
25
50
15
100
12
#1
epoch gradients
#Felem: 64
#elem: 64
#elem: 36864
#elem: 64
#elem: 64
#elem: 36864
#el 64
25
10
14
50
8
R
75
R
75
100
25
So
100
Eo
50
75
100
100
85
50 75
L#15
L#16
L#17
L#18
L#
L#20
L#
epoch gradlents
#Feee::
#elem: 73728
#elem: 128
#elem: 128
#elem: 147456
#elem: 128
#elem: 128
59
8
R
R
15
180
8o
L#22
L#23
L#24
L#25
L#26
L#27
L#28
epoch gradlents
##elem: 8192
#elem: 128
#elem: 128
#elem: 147456
#ellm: 128
#elem: 128
#elem: 147456
25
75
25
50
15
100
00
25
30
75
100
00
10
75
100
25
30
100
25
90
75
100
25
75
100
25
50
75
100
L#29
L#
epoch gradlents
#elem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 589824
#Feem:: 256
25
X
X0
R
50
R
2
15
g
100
25
go
100 go
20
50
100
100
25
50
75
L#36
L#37
L838
L#
L#40
#41
L#42
epoch gradients
#elem: 256
#elem: 32768
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
#elem: 256
X
25
04
189 58
8
R
50
75
100
80
100 E0
100
75
L#43
L#44
L448
L#49
#eeem: 589824
#elem: 256
#elem: 256
#elem: 1179648
#elem:
#elem: 512
#elem: 2359296
epoch gradlents
25
10
R
X0
10
75
R
75
25
50
75
100
80
25
50
75
100
20
25
10
75
100
80
23
50
300
80
25
50
75
100
8:
25
100
S0
25
75 L#56
50
100
L#500
L#51
L052
L#553
L
L#555
epoch gradlents
#elem: 512
#elem: 512
#elem: 131072
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
2
25
50
R
R
50
75
75
180
100
0
25
80
100
go
30
100
3
25
75
L#57
L#58
L#59
L#60
L#61
L#62
gradients
epoch gradients
#eeeem:
#elem: 2359296
#elem:
512
#elem: 5120
2
%
56
8
R
epoch gradients
50
75
100
go
epoch gradlents
25
50
80
epoch gradients gradiens
30
75
100
epoch gradients
epoch gradients
25
50
100 75
100
Bb
epoch gradlents
Figure 37: PCA Components Overlap with Gradient. Repeat of Fig. 3 on ResNet18 trained on CelebA dataset.
48

---

Published as a conference paper at ICLR 2022
CelebA, L#1
CelebA, L#2 #elem: 10
#elem: 30720
1.0
epoch gradients
0.8
25
25
0.6
50
50
0.4
75
75
0.2
100
100
0.0
25
50
75
100
0
75 epoch gradients
25
50
100
epoch gradients
Figure 38: PCA Components Overlap with Gradient. Repeat of Fig.
FCN trained CelebA dataset.
CelebA, L#1 #elem: 1500
CelebA, L#2
CelebA, L#3 #elem: 25000
CelebA, L#4
#elem: 20
#elem: 50
epoch gradients
1.0
25
25
25
30
59
50
0.8
75
75
75
75
100
75
100
100
80
100
100
L#5
L#6
L#7
L#8
#elem: 625000
#elem: 500
#elem: 5000
#elem: 10
epoch gradients
0.4
25
25
8
50
50
50
0.2
75
75
75
75
100
25
50
75
100
190
25
50
100
100
25
50
75
100
100
25
50
75
100
0.0
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 39: PCA Components Overlap with Gradient, Fig, 3 on CNN trained on CelebA dataset.
49

---

Published as a conference paper at ICLR 2022
CIFAR-10, 1+1
CIFAR-10, +
CIFAR-10, 1
CIFAR-10,
CIFAR-10, 1#5 drelem: 36864
CIFAR-10, 10,
CIFAR-10, 1
epoch grad lents
330 100 55 0
dtelem: 1728
itelem: 64
#elem:
#elem: 64
#elem:
#elem: 64
55
3
50
30
100
100
100
350
330
350
300
50
100
150
200
50
1.0
150
200
56
100
350
200
80
50
100
150
200
300
30
100
150
200
200
50
100
150
200
200
96
100
350
200
L.12
L#13
epoch gradlents
Wielem: 64
4l eeelem: 73728
eelem: 128
Welem: 128
Welem: 128
Wele:: 147456
#lelem: 128
100 130 so
100 50
50
50
100
200 150 100
530
100
150
200
200
90
100
150
200
200
100
150
200
100
50
100
200
100
150
700
200
150
200
50
100 150 200
L#15
L#16
L#17
L##18
L#19
L#20
L#
epoch gradlents
#telem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 256
#elem: 589824
100
100
150 100
200 150
150
135
L#22
L#23
750
100
L#
L#225
380
L#26
150
L#2
200
L#28
150
epoch gradlents
0.
256
#elem:
#elem: 589824
#elem:
256
#elem: 256
130 100 So
50
50
50
100
500
100
150
150
150
200
1.0
150
200
50
1.00
150
200
20
100
150
200
50
100
200
100
150
200
100
150
200
200
50
100
150
200
epoch gradients
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
200 100 56
100 50
30
150 50
200 50
200
150
330
150
50 100 150
200
80
50
100
150
200
280
50
100
150
200
50
100
150
200
200
50
100
150
200
200
50
100
150
200
200
50
300
150 200
L#36
L#37
L
L#
LW40
L#41
L#42
epoch gradlents
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
200 130 100 50
150 100 50
13U 200 50
150 100
150
200
800
50
1,0
150
200
200
200
150
200
50
150
L#43
L#44
L#45
L#446
L#47
L#48
L#449
epoch gradlents
0.
#elem:
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
200 50
250 200 50
280 250 100
300
350
250
20
200
20
88
200
280
150
L#50
L#51
L#52
L#55
L#
L#55
L#56
epoch gradlents
0.
#elem:
#elem: 512
#elem:
#elem: 2359296
#elem:
#elem: 512
#tlemm: 512
150 100 58
100 59
100 50
50
100
150
150
150
50 100 150
200
80
50
100
150
200
50
150 L#
100
200
100
50
100
150
200
30
100
150
200
200
50
100
150
200
200
50
100
150 200
L#57
L#58
L#61
L#63
egoch gradients
W #elem: 2359296
#elem: 512
#lelem: 512
#eeem: 512
#elem: 2359296
#elem: 512
Jielem: 512
So
150 100 50
50
200 150 100 50
330 100
200 150
200
300
90
150
100
150
200
1g0
200
100 150 200
200
50 100 150
L#64
L#65
L#66
epoch gradients
epoch gradients
epoch gradlents
epoch gradients
epoch gradients
#elem: 512
#elem: $120
#elem:
206 150 100
100
150
0.0
3g6
88
epoch gradients
epoch gradients
epoch gradients
Figure 40: PCA Components Overlap with Gradient. Repeat Fig. on VGG19 trained on CIFAR-10 dataset.
50

---

Published as a conference paper at ICLR 2022
CIFAR-10, L#1 #elem: 9408
CIFAR-10, L#2
CIFAR-10, L#3 #elem:
CIFAR-10, L#4 #elem: 36864
CIFAR-10, L#5
CIFAR-10, L#6
CIFAR-10, L#7 #elem: 36864
epoch gradlents
#elem: 64
#elem: 64
#elem: 64
150 200 50
ISU AND 50
150 300 50
280 150 200
20
20
200
L#8
L#9
L#10
L#
L#13
# 14
epoch grad lents
150 100 so 0.
#telem:
#elem: 64
#elem: 36864
#elem:
#elem: 36864
#elem:
50
50
30
50
30
100
100
100
150
150
150
200
50
1#15
100
150
200
50
L#16
1.0
150
200
200
50
L#17
100
150
200
100
50
L#18
100
1.0
200
200
30
L#19
100
350
200
200
50
L#20
100
150
200
200
50
L#21
100
150
200
epoch gradients
#Felem: 64
#elem: 73728
#elem:: 128
#elem:: 128
#elem: 147456
# #elem: 128
#elem: 128
200 100 50
150 100 50
13U 100 30
100
150
200
300
50
1.00
250
150
200
200
200
100
150
200
50
100 150
L#22
L#23
L#24
L#$25
L#26
L#21
L#28
epech gradlents
#elem: 8192
#elem: 128
#elem:
#elem: 147456
#elem: 128
#elem: 128
#elem: 147456
200 250 100 So
100 50
250 s0p 50
100
0.6
350
250
200
280
200
100
800
200
200
150
L#29
L#30
L#
L#332
L#33
L#33
epoch gradlents
#elem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
200 130 100 so
50
50
100 50
100
100
150
130
150
50 100 150
200
80
50
100
150
200
80
50
100
150
200
0
50
100
150
200
30
100
150
200
50
100
150
200
400
50
300 150 200
L#36
L#37
L
L#
L#40
L#41
L#42
epoch gradlents
#elem: 256
#elem: 32768
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
#elem: 256
280 150 100 50
50
100
150 2000
100
150
250
200
800
200
150
150
180
150
L#43
L#44
L#455
L#446
L#47
L#48
L#49
epoch gradlents
#felem: 589624
#elem: 256
#elem:
felem: 1179648
#elem:
Welem: 512
2359296
280 130 100 So
50
50
100
100
150 100
150
130
200
100
150
200
150
200
100
080
150
200
200
200
200
50
100
150 200
L#52
epoch gradients
#elem: 512
#elem: 512
#elem: 131072
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
800 130 200 50
300 50
100 50
50
200 50
150
330
150
50 100 150
200
00
50
150
150
200
100
50
100
150
200
50
100
150
200
20
30
100
150
200
50
100
150
200
300
50
100 150 200
L#57
L#58
L#59
L##60
L#61
L#62
epoch gradients
epoch grad gradients ents
#telem: 512
Welem: 2359296
#eeem: 512
#elem: 512
#elem: 5120
#elem: 10
Los
100
150
I50
150
0.0
39
880
300
epoch gradients
epoch gradients
epoch gradients
epoch gradients
'eocch gradients
epoch gradients
Figure 41: PCA Components Overlap with Gradient. Repeat Fig. ResNet18 trained on CIFAR-10 dataset.
51

---

Published as a conference paper at ICLR 2022
CIFAR-10, L#1
CIFAR-10, L#2
#elem: 30720
#elem: 10
1.0
epoch gradients 200
0.8
50
50
0.6
100
100
0.4
150
150
0.2
0
50
100
150
200
200
150 epoch gradients
50
100
200
0.0
epoch gradients
Figure 42: PCA Compunents Overlap with Gradient. Repeat of Fig. 3 on FCN trained on CIFAR-10 dataset.
CIFAR-10, L#1
CIFAR-10, L#2
CIFAR-10, L#3 #elem: 25000
CIFAR-10, L#4
#elem: 1500
#elem: 20
#elem: 50
epoch gradients
1.0
50
50
50
50
100
100
100
100
0.8
150
150
150
150
200
150
200
100
200
200
100
200
50
100
150
200
L#5
L#6
L#7
L#8
#elem: 625000
#elem: 500
#elem: 5000
#elem: 10
epoch gradients
0.4
50
50
100
100
100
100
0.2
150
150
150
200
50
100
150
200
200
50
100
150
200
200
o
50
100 150
200
200
50
100
150 200
0.0
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 43: PCA Components Overlap with Gradient. Fig. 3 on CNN trained on CIEAR-10 dataset.
52

---

Published as a conference paper at ICLR 2022
CIFAR-100, 1#1
CIFAR-100, 142
CIFAR-100, ##3
CIFAR-100, 100, 1444
CIFAR-100, 1 Brelem: 36864
CIFAR-100, 1
CIFAR-100, 1
epoch grad gradlents lents
330 100 55 0
Jrelem: 1728
irelem: 64
#elem:
#elem: 64
#elem:
#elem: 64
52
55
50
100
100
350
250
150
20
50
100
150
200
80
50
1.0
150
200
100
56
L#10
100
150
200
R0
50
100
150
200
30
L#12
100
150
200
100
50
100
150
200
100
96
100
150 200
epoch gradients
0
elelem: 64
Al Welem: 73728
# eleem:
128
Welee::
128
#elem: 128
Wele:: 147456
elelem: 128
so
30
50
150 105
150 10)
100
100
130
150
200
50 100
150
200
200
90
150
150
200
50
100
150
200
50
100
150
200
200
100
150
700
200
150
200
200
90
100
150
200
L#15
L#16
L#17
L#118
L#19
L#20
L#
epoch gradients
#elem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 256
#elem: 589824
200 150 100
100
100
100
150
135
150
L#22
130
20
L#23
280
L
L#25
300
L#26
150
L#2)
200
L#28
150
epoch gradlents
50 8
#elem:
256
#elem:
589824
#elem:
#elem:
50
50
50
130 100
100
150 100
100
150
150
300
1.0
200
50
1.0
750
200
200
100
150
200
50
100
150
200
30
100
150
200
200
800
50
100
150
200
epoch gradlents
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
100 56
100 50
50
50
50
200
300
150
130
150
150
200
50 100 150
200
80
50
1.0
150
200
280
50
100
350
200
50
100
150
200
200
30
100
150
200
200
50
1000
150
200
200
50
300
150 200
L#36
L#37
L
L#
L#40
L#41
L#42
epoch gradlents
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
200 130 100 50
150 100 50
15U 2010 50
50
100
150
150
200
800
50
1,0
200
150
200
20
200
150
200
200
50
100 150
L#43
L#44
L#45
L#446
L#47
LW48
L#49
epoch gradients
0.
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
100 50
150 s0p s0
300
350
250
200
30
20
200
30
30
150
L#50
L#51
L#52
L#55
L#54
L#55
L#56
epoch gradlents
0.
#elem:
#elem: 512
#elem:
#elem: 2359296
#elem:
#elem: 512
#elem: 512
50
300 59
130 200 50
50
130 300
200
150
150
50
100 150
200
50
120
350
700
50
100
150
200
50
100
150
200
50
100
150
200
100
50
100
150
200
200
50
100
150 200
L#57
L#58
L#55
L#61
L#63
egoch gradients
#elem:: 2359296
#elem: 512
#eeem: 512
#elem: 512
#elem: 2359296
#eelmm 512
#ielem: 512
so
50
50
50
150 100
330 100
300 150 100
100 150
150
200
200
50
150
200
150
200
1g0
200
100 150 200
200
100 150 200
L#64
6#
L#66
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
#elem: 512
#elem: 51200
#elem: 100
100
200 150
150
0.
30
280
epoch gradients
epoch gradients
epoch gradients
Figure 44: PCA Components Overlap with Gradient. Repeat of Fig. 3 on VGG19 trained on CIFAR-100 dataset.
53

---

Published as a conference paper at ICLR 2022
CIFAR-10D, L#1
CIFAR-100, L#2
CIFAR-100, L#3
CIFAR-100. LiF4
CIFAR-100, L#5
CIFAR-100, L#6
CIFAR-100, L#7
epoch gradlents
#elem: 432
#elem: 16
#elem: 16
#elem: 2304
#elem: 16
#elem: 16
#elem: 2304
200 50
250 anp 50
100 50
200 200
150
150
800
20
150
200
150
L#8
L#9
L#10
L#11
L#12
#13
11
epoch gradlents
0.
#elem: 16
#elem: 2304
#elem: 16
#elem:
2304
So
50
150 s00 50
200 100
100
150 300
130
200
L#16
150
889
100
150
200
100
150
150
200
200
L#20
200
200
50
100
150 200
epoch gradlents
#Felem:
#elem: 4608
#elem: 32
#elem: 32
#elem: 9216
#elem:: 32
#elem: 32
280 130 100 so
100 10
20U 30
200 30
150
130
150
50 1.00 150
200
80
50
150
150
200
50
100
150
200
R
50
100
150
200
400
30
100
150
200
20
50
100
150
200
50
100 150 200
L#22
L#23
L#24
L#25
L#26
L#27
L#28
epoch gradlents
#ellem: 9216
#elem: 32
#elem: 32
#tlem: 9216
#elem: 32
#elem: 32
#tleem: 18432
100 50
200 150 100
100
100
150
350
150
200
280
200
200
L#29
L#30
L#31
L#32
L#33
L
444
L#35
epoch gradlents
0.
#Felem:
#elem:
#elem:
#elem:
#elem:
So
50
150 200 50
50
200 130 100
100
200
150
150
100
150
200
50
1.00
150
200
100
100
200
R0
50
100
200
38
30
100
150
200
200
150
200
50
100
150
200
epoch gradlents
0
#eeeem: 64
# #elem: 36864
#elem: 64
#elem: 64
#elem: 73728
#elem: 128
#elem: 128
280 100 56
50
200 50
50
300
200
350 100
150
100
150
200
80
50
1.0
150
100
-50
200
50
100
150
200
100
150
200
100
150
200
200
50
100
150 200
L#43
L#44
L#45
L#46
L#47
L#48
L#49
epoch gradlents
#telem:: 147456
#elem: 128
#elem: 128
#elem: 147456
#elem: 128
#elem: 128
#elem: 147456
100
200 150 100
150 100
200 150
15e
300
889
100
80
L#50
L#51
L#52
L#
epoch graclents
0.
#elem:
128
#elem:
#elem: 100
50
50
200 130 100
300
150
50
100
150
200
50
100
150
200
200
90
300
150
200
R0
50
100
150
200
0.0
Figure 45: PCA Components Overlap with Gradient. Repeat Fig. on ResNet18 trained on CIFAR-100 dataset.
54

---

Published as a conference paper at ICLR 2022
CIFAR-100, L#1
LIFAR-100, L#2
#elem: 307200
#elem: 100
1.0
epoch gradients 200
0.8
50
50
0.6
100
100
0.4
150
150
0.2
200
0.0
0
50
100
150
200
50
100
150
200
epoch
gradients
epoch gradients
Figure 46: PCA Components Overlap with Gradient. Repeat of Fig. 3 on FCN trained on CIFAR-100 dataset.
CIFAR-100, L#1
CIFAR-100, L#2
CIFAR-100, L#3
CIFAR-100, L#4
#elem: 1500
#elem: 20
#elem: 25000
#elem: 50
epoch gradients
1.0
50
50
50
50
100
100
100
100
0.8
150
150
150
200
150
200
100
200
200
200
100
L#5
L#6
L#7
L#8
#elem: 625000
#elem: 500
#elem: 50000
# #elem: 100
epoch gradients
0.4
50
100
100
100
150 100
0.2
150
150
200
50
100
150
200
200
50
100
150
200
200
50
100 150
200
200
200 epoch gradients
50
100
150
0.0
epoch gradients
epoch gradients
epoch gradients
Figure 47: PCA Components Overlap with Gradient. Fig. 3 on CNN trained on CIEAR-100 dataset.
55

---

Published as conference paper at ICLR 2022
FMNIST, 1
FMNIST, 1.22
FMNIST, #3 #elem:
FMNIST, #44 #elem: 64
FMMIIST #5
FMNIST, 166 #elem:
FMNIST, 1
epoch grad lntts
#elem: 576
itelem: 64
#elem: 36864
#elem: 64
25
R3
2
75
75
100
100
25
50
75
100
00
10
75
100
60
23
30
100
25
50
75
100
25
100
25
50
25
100
epoch gradlents
jlelem: 64
4 Welem: 73728
ellem: 128
Welem: 128
Welem: 128
Wele:: 147456
eeele:: 128
25
10
S0
X
75
4
75
52
100
100
25
50
75
100
80
25
10
75
100
8
23
20
25
50
75
100
100
-00
25
50
75
100
L#15
L#16
L#17
L#188
L#19
L#20
L#
epoch gradlents
#telem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 256
#elem: 589824
50
8
8
R
190
8o
80
8o
L#22
L#23
L# 24
L#25
L#
L#22
L #2
epoch gradlents
256
#elem:
#elem: 589824
#elem:
#elem: 256
25
10
R
50
R
3
75
75
100
25
75
1000
100 20
25
50
100
25
50
75
100
1000
25
10
75
100
L#29
L#30
#3
epoch gradlents
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem:: 512
25
X
10
50
75
R
10
25
52
75
100
80
25
50
75
100
20
25
10
75
100
8o
25
50
100
80
25
90
75
100
8
25
50
100
25
50
75
100
L#36
L#37
L
L##39
L#40
L#42
epoch gradlents
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
25
X2
25
50
R
R
50
50
75
75
100
100
25
g0
100 go
20
50
100
25
50
75
L#43
L444
L#45
L#46
L#44
444
L#44
epoch gradients
#elem::
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
10
25
58
8
R
50
75
80
100
L#50
L#51
L#52
L#53
L#55
L#56
epoch gradlents
0.
#elem:
#elem: 512
#elem:
#elem: 2359296
#elem:
#elem: 512
#teeem: 512
25
10
22
23
75
75
75
100
25
50
75
100
@0
10
75
100
Ed
23
30
100
25
50
75
100
100
400
25
50
75
100
L
L#61
epoch gradlents
# #elem: 2359296
Welem: 512
#ellm: 512
Welem: 512
#elem: 2359296
#elem: 512
Jielem: 512
25
X
X
50
8
R
15
R
L4
100
25
65
M
L#66
100
So
epoch gradients
2o
epoch gradients
75
100
8
epoch gradlents
8:
epoch gradients
25 50
100
epoch gradients
#elem: 512
#elem: $120
#elem:
50
5
15
0.0
26
go
80
epoch gradients
epoch gradients
eeoch gradients
Figure 48; PCA Components Overlap with Gradient. Repeat Fig. 3 on VGG19 trained on FMNIST dataset.
56

---

Published as a conference paper at ICLR 2022
FMNIST, L
FMNIST, L#2
FMNIST, L#3 #elem:
FMNIST, L#4 #elem: 36864
FMNIST, Le5 #elem: 64
FMNIST, L#6 #elem:
FMNIST, L#7
epoch gradlents
#elem:: 3136
#elem: 64
#elem: 36864
50
50
R
50
40
100
80
80
8
L#8
L#9
L#10
L#
L#12
11
+
14
epoch grad ents
25 0
#Felem:
# #elem: 64
#elem: 36864
#elem:
#elem: 36864
#elem: 64
R
23
75
R
75
25
75
100
80
25
30
75
100
S0
25
10
75
100
23
30
100
25
10
75
100
25
100
100
25
50
75
100
L#15
17
L#
L#20
L#21
epoch gradlents
#Felem: 64
#elem: 73728
#elem:: 128
#elem:: 128
#elem: 147456
# #elem: 128
#elem: 128
25
10
10
50
R
3
75
100
100
25
g0
100 Eo
20
50
75
100
100
25
50
75
L#22
L#23
L824
L#
L#26
L#27
28
epoch gradlents
#elem: 8192
#elem: 128
#elem: 128
#elem: 147456
#elem: 128
#elem: 128
#elem: 147456
12
25
56
50
50
75
0.6
100
100
100
80
100
L#29
L#30
L#31
L#32
L#33
L4
L#35
epoch gradlents
#elem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 589824
#Flem:: 256
25
10
X0
10
10
20
75
R
75
25
50
75
100
2
25
50
75
100
20
25
10
75
100
80
25
50
75
100
80
25
90
75
100
8
25
100
80
25
50
75
100
L#36
L#37
L#
L#339
L#40
L#41
L#42
epoch gradlents
#elem: 256
#elem: 32768
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
#elem: 256
25
2
50
58
R
R
50
75
75
188
100
g0
g0
00
L#43
L#44
L#45
L#46
L#47
L#48
L#49
epoch gradlents
#felem: 589824
#elem: 256
#elem:
#elem: 1179648
#elem:
Welem: 512
#elem: 2359296
2
10
10
50
R
R
88
100
100 8o
25
75
100
8
100
25
50
75
100
Le52
epoch gradlents
#elem: 512
#elem: 512
#elem: 131072
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
25
x0
25
50
15
R
75
180
25
52
75
100
80
25
50
75
100
g0
25
30
75
100
go
23
50
300
30
25
90
75
100
25
50
100
49
75 epoch gradients
25
50
100
L#57
L#58
L
L#600
L#61
L#62
#telem: 512
Welem: 2359296
#elem: 512
#elem: 512
#elem: 5120
#elem: 10
epoch grad
50
g
8
0.0
go epoch gradients
So
epoch gradients
epoch gradients
epoch gradients
eeocch gradients
epoch gradients
Figure 49: PCA Components Overlap with Gradient. Repeat Fig. on ResNet18 trained FMNIST
dataset.
57

---

Published as a conference paper at ICLR 2022
FMNIST, L#1
FMNIST, L#2
#elem: 7840
#elem: 10
1.0
epoch gradients
0.8
25
25
0.6
50
50
0.4
75
75
0.2
100
100
0.0
0
25
50
75
100
25
50
75
100
epoch gradients
epoch gradients
Figure 50: PCA Components Overlap with Gradient. Repeat of Fig.
FCN trained FMNIST dataset.
FMNIST, L#1 #elem: 500
FMNIST, L#2
FMNIST, L#3 #elem: 25000
FMNIST, L#4
#elem: 20
#elem: 50
epoch gradients
1.0
25
25
25
50
50
0.8
75
75
75
75
100
75
100
100
g0
100
100
L#5
L#6
L#7
L#8
#elem: 400000
#elem: 500
#elem: 5000
#elem: 10
epoch gradients
25
25
25
25
50
50
50
0.2
15
75
75
100
25
50
75
100
g0
25
50
100
100
25
50
75
100
100
25
50
75
100
0.0
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 51: PCA Components Overlap with Gradient. Fig. on CNN trained on FMNIST dataset.
58

---

Published as conference paper at ICLR 2022
MNIST, 1+1
MNIST, #2 itelem: 64
MNIST, # #eeem:
MNIST, 1 #elem: 64
MNIST, #5 #relem: 36864
MNIST, 1 #elem:
MNIST, #7
epoch grad lntss
#teem: 576
#elem: 64
25
R
R
2
23
75
75
190
56
75
100
8
25
50
75
100
10
75
100
60
23
30
100
25
50
75
100
25
100
25
30
25
100
epoch gradients
Wlelem: 64
Al Welem: 73728
eelem: 128
Welee:: 128
A Nelem: 128
Welem: 147456
eleem: 128
50 25
10
25
75
75
52
100
100
25
50
75
80
25
10
75
100
23
50
25
50
75
100
100
25
50
75
100
L#15
L#16
L#17
L#118
L#19
L#20
L#
epoch gradients
#telem: 128
#elem: 128
#elem: 294912
#elee: 256
#elem: 256
#elem: 256
#elem: 589824
50
8
3
R
:90
So
8o
80
L##2
L#23
L
L#25
L#26
L#2
L#
epoch gradients
256
#elem:
Pelem: 589824
#elem:
#elem:
25
10
12
50
R
3
40
75
L#29
75
100
-0
25
L#30
75
100 20
25
50
100
25
50
75
100
L#34
1000
25
10
75
100
epoch gradlents
#elem: 589824
#elem: 256
#elem: 256
# #elem: 256
#elem: 1179648
#elem: 512
#elem: 512
25
X0
10
10
50
75
R
R
100
25
5C
75
100
2
25
50
75
100
20
25
10 75
100
80
25
50
100
80
25
50
75
100
8
25
1000
80
25
50
75
100
L#36
L#37
L 38
L#
L#40
L#41
L#42
epoch gradlents
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
25
12
25
50
R
R
50
50
75
100
g0
100 go
20
100
25
50
75
L#43
4444
L#45
L#46
L#44
#47
L#48
L#49
epoch gradients
#tlem::
#elem: 512
#elem: 2359296
#elem: 512
#elem: 512
#elem: 512
#elem: 2359296
25
X
12
58
59
8
R
80
100
L#50
L#51
L#52
L#53
L#55
L#56
epoch gradients epoch gradlents
#elem:
#elem: 512
#telem:
#elem: 2359296
#elem:
#elem: 512
#elem: 512
25
10
22
75
75
100
00
25
50
75
100
20
10
75
100
Eo
25
50
75
100
25
50
75
100
1000
25
50
75
100
L
L#61
#elem: 2359296
Welem: 512
#ellm: 512
Welem: 512
#elem: 2359296
#elem: 512
#leeem: 512
25
R
X
50
8
R
15
R
L#64
50
100
25
65
L#66
100
80
epoch gradients
epoch gradients
50
75
100
8
epoch gradlents
85
epoch gradients
25 50
100
epoch gradients
#elem: 512
#elem: 5120
#elem:
58
5
0.0
200
20
80
epoch gradients
epoch gradients
epoch gradients
Figure 52: PCA Components Overlap with Gradient. Repeat of Fig. 3 on VGG19 trained MNIST dataset.
59

---

Published as a conference paper at ICLR 2022
MNIST, L#1 #elem: 3136
MNIST, L#2
MNIST, L #elem:
MNIST, L#4
MNIST, LM5 #elem:
MNIST, L#6 #elem:
MNIST, L#7 #elem: 36864
epoch gradlents
0
#elem: 64
#elem: 36864
1.
25
23
25
72
25
75
75
75
75
75
100
25
50
15
100
20
30
100
23
30
75
100
25
50
75
100
25
100
100
25
50
15
100
epoch gradients
#Feeem: 64
# #elem: 64
#eelm: 36864
#elem: 64
#elem: 64
#elem: 36864
#el em: 64
So 25
10
75
75
100
100
25
So
100 8o
20
50 75
100
100
50 75
100
L#15
L#16
L#17
L#188
L#
L#20
L#22
epoch gradlents
#Felem:
#elem: 73728
#elem: 128
#elem: 128
# #elem: 147456
#elem: 128
#elem: 128
25
50
R
R
50
190
So
So
80
L#22
L#23
L#24
L#25
L#26
L#27
L#28
epoch gradlents
#telem: 8192
#elem: 128
#telem: 128
#elle:: 147456
#elem: 128
#elem: 128
#elem:: 147456
25
13
10
10
75
25
L#29
15
100
25
10
75
100
20
25
10
75
100
go
23
30
100
25
L#33
90
75
100
25
1000
80
25
50
75
100
epoch gradlents
#elem: 128
#elem: 128
#elem: 294912
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
50 25
X0
R
2
8
15
100
80
25
go
100 8o
20
50
100
80
25
50
75
LW36
L#33
L#38
L#
L#40
#41
L#42
epoch gradients
#elem: 256
#elem: 32768
#elem: 256
#elem: 256
#elem: 589824
#elem: 256
#elem: 256
X
12
25.
04
399 58
8
R
59
75
100
100 E0
100
75
L#43
L#44
L#46
L48
L#49
#telem: 589824
#eeem: 256
#elem: 256
#elem: 1179648
#elem: 512
#elem: 512
#elem: 2359296
epoch gradlents
25
R
10
75
R
25
50
75
100
25
50
75
100
20
25
10
75
100
80
23
50
100
25
50
75
100
8:
25
100
25
50
75
100
L#550
L#51
L052
L#55
L4
L#55
L#56
epoch gradlents
#elem: 512
#elem: 512
#elem: 131072
#elem: 512
#elem: 512
#elem: 2359296
#elem: 512
25
50
R
50
15
75
100
0
g0
100
g0
30
3
50
L#57
L#58
L59
L#60
L#61
L#62
gradients
epoch gradients
#felem:
#elem: 2359296
#elem:
512
#elem: 5120
10
56
8
8
%0
100
g
50
30
75
100
80
23
25
50
75
100
100
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradlents
Figure 53: PCA Components Overlap with Grudient, Repeat of Fig. 3 on ResNet18 trained on MNIST dataset.
60

---

Published as a conference paper at ICLR 2022
MNIST, L#1
MNIST, L#2 #elem: 10
#elem: 7840
1.0
epoch gradients
0.8
25
25
0.6
50
50
0.4
75
75
0.2
100
0
25
50
75
100
100
25
50
75
100
0.0
epoch
gradients
epoch gradients
Figure 54: PCA Components Overlap with Gradient. Repeat of Fig.
FCN trained MNIST dataset.
MNIST, L#1
MNIST, L#2
MNIST, L#3 #elem: 25000
MNIST, L#4
#elem: 500
# #elem: 20
#elem: 50
epoch gradients
1.0
25
12
25
25
8
50
50
50
0.8
75
75
75
75
100
75
100
100
-00
100
100
L#5
L#
L#
L#8
#elem: 400000
#elem: 500
#elem: 5000
#elem: 10
epoch gradients
0.4
25
25
25
50
50
50
0.2
75
75
75
100
25
50
75
100
100
25
50
100
100
25
50
75
100
100
25
50
75
100
0.0
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 55: PCA Components Overlap with Gradient. Fig. on CNN trained on MNIST dataset.
61

---

Published as a conference paper at ICLR 2022
PascalVOC, 1#1
PascalVOC,
PascalVOC, #3 #relem:
PascalVOC, #4 #elem: 32
PascalVOC, 1 .telem; 9216
PascalVOC, 1
PascalVOC, 1
epoch grad letts
0
#elem: 704
#telem 22
#elem: 32
#elem: 32
25
R
%
22
75
75
75
100
80
25
50
15
100
60
10
75
100
80
23
30
73
100
25
50
75
100
25
100
100
25
50
25
100
L#11
epoch gradlents
jkelem: 32
elelem: 32
#elem: 32
A Welem: 18432
Kelem: 64
ellem: 36864
eell Welem: 64
10
10
50
8
75
4
75
L#15
52
100
100
25
L#16
50
25
100
80
25
L#17
75
100
23
L#18
50
100
25
L#19
50
75
100
L#20
50
100
25
L#21
50
75
100
epoch gradients
#kelem: 64
#elem: 64
#elem: 64
#elem: 64
#elem: 73728
#elem: 128
#elem: 147456
50
8
8
R
8
R
:90
So
8o
L#22
L#23
L
L#25
L#26
L#2
L #2
epoch gradlents
128
#elem:
#elem: 128
#elem:
#elem: 294912
#elem:
25
10
10
50
R
R
75
100
25
75
100 20
25
50
100
25
50
75
100
8
100
25
10
75
100
L#30
#3
epoch gradlents
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 131072
25
X
80
10
50
75
R
10
25
50
75
100
25
50
75
100
20
25
10
75
100
80
25
50 75
100
80
25
50
75
100
8
25
50
100
25
50
75
100
L#36
L#37
L
L#
L
L#41
L#42
epoch gradlents
#elem: 128
#elem: 32768
#elem: 128
#elem: 294912
#elem: 128
# #elem: 147456
#elem: 128
25
X
X
25
50
R
R
50
75
75
100
25
go
100 20
20
50
100
25
50
75
L#43
L444
L#45
L#46
L#44 4447
#48
L#449
epoch gradients
#elem:
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 32768
10
25
50
8
50
75
100 Eo
100
LL#50
L#51
L#52
L
L#54
L55
L#56
epoch gradlents
#telem:
#elem: 8192
#elem:
#elem: 73728
#telmm
#eeem:: 36864
#elem: 64
25
22
25
50
15
75
75
100
@0
25
50
75
100
@0
75
100
Ed
25
50
100
25
50
75
100
100
.00
25
50
75
100
L#57
L#58
L
epoch gradlents
jkelem: 64
#felem: 64
#elem: 64
#'elm: 64
#elem: 64
#elem: 64
#elem: 8192
25
X
50
8
R
15
e
75
100
25
75
100
g0
20
90
75
100
B
100
90 75 100 epoct
25
L#64
6#
L#66
L#67
L#68
L#
epoci-grrtilent giddilents
epoch gradients
##eee::
#elem: 2048
#elem:
#elem: 18432
#elem: 32
#elem: 9216
#elem: 32
50
5
3
R.
0.0
go
80
epoch gradients
epoch gradients
eepchh gradients
epoch gradients
epoch gradients
epoch gradients
epoch gradients
Figure 56; PCA Components Overlap with Gradient. Repeat of Fig. on U-Net trained PascalVOC dataset.
62

---

Published as a conference paper at ICLR 2022
COCO, 1#1
COCO, 1#2 #elem: 2
COCO, # #relem 864
COCO, 1 #elem: 32
COCO, 1 #telmm 9216
COCO, 1#6 #elem: 32
COCO, #7
epoch grad lents
Wrelem:
#elem: 32
25
%
50
75
75
75
100
25
50
15
100
10
75
100
23
30
100
25
50
15
100
25
100
25
50
15
100
L#11
epoch gradlents
Wlelem: 32
elelem: 32
#ellm: 32
@ elem: 18432
#elem: 64
eelem: 36864
Welem:: 64
10
10
X
75
4
L#15
50
15
100
25
L#16
50
75
100
25
L#17
10
75
100
Eo
23
L#188
50
100
20
25 50
L#19
75
100
L#20
50
100
25
L#21
50
75
100
epoch gradients
#eelem:
#elem: 64
#elem: 64
#elem: 64
#elem: 73728
#elem: 128
#elem: 147456
8
8
8
8
16
190
So
8o
L#22
L#23
L#
L#25
L#26
L#2
L#
epoch gradlents
#elem:
128
#elem:
#elem: 128
#elem:
#elem: 294912
#elem: 256
25
10
10
10
59
R
3
19
20
75
100
25
75
100 20
25
50
100
25
50
75
100
8
100
25
10
75
100
L#30
L3
epoch gradlents
#elem: 589824
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 256
#elem: 131072
25
X
80
10
80
50
15
R
10
25
50
75
100
25
50
75
100
20
25
10 75
100
80
25
50 75
100
80
25
50
75
100
8
25
50
100
80
25 50
75
100
L#36
L#37
L 38
L#
L#40
L#41
L#42
epoch gradlents
#elem: 128
#elem: 32768
#elem: 128
#elem: 294912
#elem: 128
# #elem: 147456
#elem: 128
35
X2
59
R
R
15
100
25
go
100 go
20
50
100
25
50
75
L#43
L444
L#45
L#46
L#44
444
L#44
epoch gradients
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 128
#elem: 32768
25
58
8
50
18
100 Eo
100
L#50
L#51
L#52
L#
L#54
L555
L#56
epoch gradlents
#eeeem
#elem: 8192
#elem:
#elem: 73728
#telmm:
#telem: 36864
#elem: 64
25
22
25
50
75
75
75
100
25
50
75
100
@o
10
75
100
Ed
25
50
100
25
50
75
100
100
.00
25
50
75
100
L#57
L#58
L
L#61
epoch gradients
jkelem: 64
#felem: 64
#elem: 64
#'elmm 64
#elem: 64
#eeem: 64
#elem: 8192
25
X
25
50
50
15
75
100
25
Sp
75
100
go
90
75
100
B
100
25 50 75 100 epoct spocl-grattleent giddleents
L#64
65
L#66
L#67
L#68
L#
epoch gradients
##eem:
#elem: 2048
#elem:
#elem: 18432
#elem: 32
#elem: 9216
#elem: 32
50
5.
3
R.
R.
0.0
So
So
epoch gradients
epoch gradients
'epcch gradients
epoch gradients
epochh gradients
epoch gradients
epoch gradients
Figure 57: PCA Components Overlap with Gradient, Repeat of Fig. 3 on U-Net trained on COCO dataset.
63

---

Published as a conference paper at ICLR 2022
Vanilla FL
LBGM
MNIST
FMNIST IID
CIFAR-10 IID
PascalVOC Segmentation
IID
1.00
accuracy
0.75
0.6
3
0.50
0.50
0.4
loss
0.25
0.25
0.00
100
75 100
125
250
375
500
75
150
225
300
shared (x106)
400
600
t
#params
40
40
300
400
20
20
200
200
0
25
50
75
100
25
50
75
100
125
250
375
500
75
150
225
300
accuracy
0.75
0.75
0.6
0.50
0.50
loss
0.25
0.00
0.00
0.0
200
400
200
400
# #params
# #params shared(x109)
#params
# #arrmmss
shared(x109)
Shared(x109)
shared(x100)
Figure 58: LBGM Standalone Algorithm. Experimental results in Fig. 5 repeated datasets: R-0. FMNIST, and MNIST (iid data distribution) using classifier: CNN, and dataset: PascalVOC using U-Net architecture.
Vanilla FL LBGM
MNIST
MNIST Non-lID
FMNIST IID
FMNIST
IID
Non-IID
1.00
1.00
accuracy
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
shared (x106)
1.00
1.00
1.00
1.00
# #params
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
1.00
1.00
accuracy
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
# params shared(x109)
# params shared(x109)
#params s
# #params shared(x109)
Figure 59: LBGG as Standalone Algorithm. Experimental results in Fig. 5 repeated for datasets: FMNIST and MNIST (both sid and non-iid data distribution) using classifier: FCN.
64

---

Published as a conference paper at ICLR 2022
Vanilla
LBGM
MNIST Non-IID
FMNIST Non-IID
CIFAR-10 Non-IID
CIFAR-100 Non-IID
CelebA Regression
loss (x104)
accuracy
0.75
0.75
0.6
0.4
0.50
0.59
0.4
0.00
25
50
100
0.00
25
50
75
100
0.0
50
100
150
200
0.0
125
250
375
500
0.0
25
100
shared (x10%)
#params
0.75
0.75
1.5
0.75
0.50
0.59
1.0
0.50
0.5
0.00
25
50
100
0.00
25
50
75
100
0.0g
30
100
150
200
125
250
375 500
0.00
25
100
loss (x114)
accuracy
0.75
0.75
0.6
0.4
1.5
0.50
0.50
0.4
3.00
0
0.5
1.0
0.00
0.0
0.5
0.0
0.0
8 6.00
1.0
#params
#params shared(x109)
# #params shared(x109)
# #params shared(x109)
#params
shared(x10F)
shared(x109)
Figure 60: LEGM Standalone Algorithm. Experimental results in Fig. 5 repeated for datasets: CIFAR-10. CIFAR-100, FMNIST, MNIST (non-iid data distribution), and CelebA (face landmark regression task) using classifier; Resnet18.
Vanilla FL 6threshold =0.9
6 holds = 0.8
@threshold_ 0.4 0
6threshold -n 0.6
6phreshoid_ 0.2 6
MNIST
FMNIST IID
CIFAR-10
PascalvOC
IID
IID
Segmentation
accuracy
0.75
7555
0,50
loss
0.28
00
shared (x10%)
#params
40
400
20
20
200
25
50
75
100
25
50
75
100
8
125
250
375
500
0
75
150
225
300
1.00
accuracy
0.75
0.6
0.30
0.4
loss
0.25
0.25
0.2
0.00
0.00
20
0.0
200
200
400
# #params shared(x10')
# params shared(x109)
#params
# #params shared(x10*)
shared(x109)
Figure 61: Effect of gthreshold LBGM. Experimental results in Fig. 6 repeated for datasets: C-FAR-10., FMNIST, and MNIST (iid data distribution) using classifier: CNN, and dataset: PascalVOC using U-Net architecture.
0%
65

---

Published as a conference paper at ICLR 2022
Vanilla FL
6
threshold - =0.8
6k
_ = 00.4
6% 6threshold =0,9
6
threeshold..o =0.6
6threshold =02
MNIST
MNIST Non-IID
FMNIST |ID
FMNIST
IID
Non-IID
1.00
1.00
accuracy
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
25
shared (x103)
t
t
10.0
10.0
10.0
10.0
#params
7.5
7.5
7.5
7.5
5.0
5.0
5.0
5.0
2.5
2,5
2.5
2.5
0.0
0.0
0.0
t
1.00
1.00
accuracy
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
#params
# ppaamss shared(x103)
# params shared(x10*)
#params shared(x10$)
shared(x109)
Figure 62: Effect of otheeshoid on LBGM. Experimental results in Fig. 6 repeated for datasets: FMNIST and MNIST (both iid and non-iid data distribution) using classifier: FCN.
Vanilla FL 6 @threshold_
5t threehhold =0.8
5 5t
threshold =0.4
=0.9
6threshold_0..3
6% threehoold=02.
CIFAR-10
CIFAR-100
CelebA
Non-IID
Non-IID
Regression
0.6
2.0
1x144
accuracy
0.6
1.5
0.2
los6
0.5
100
150 200
125
250
375 500
25
100
shared (x108)
#params
1.5
0.75
0.50
0.25
160
0
0.00
t
0.6
2.0
loss (x104)
accuracy
1.5
0.4
0.4
1.0
0.2
0.0
0.0
0.0
1.0
# params
# params
#params
shared(x109)
Figure 63: Effect of 8% gthreshold on LBGM, Experimental results Fig. 6 repeated datasets: CIFAR-10.
CLEAR-100 moo--id data distribution), and CelebA (face landmark regression task) using classifier: Resnet18.
66

---

Published as a conference paper at ICLR 2022
w/o LBGM
w/ LBGM
MNIST IID/Top-K
FMNIST IID/Top-K
CIFAR-10 IID/Top-K
MNIST IIDAATOMO
FMNIST IIDIATOMO
CIFAR-10 IID/ATOMO
1.00
accuracy
0.75
0.75
0.75
0.75
0.50
0.25
0.2
0.25
0.25
0.00
0.30
0.0
300
0.00
100
25
0.0
125
250
shares (x10%)
0.6
#params
0.2
25
50
75
100
25
50
75
100
125
250
375
500
0.0
25
50
75
180
3.0
25
50
75
100
0
125
250 t
375
520
accuracy
0.75
0.6
0.4
0.50
0.50
0.4
0.50
0.50
0.2
0.25
0.25
0.25
0.20
40
00
0.6
#params shared(x10*)
#params shared(x109)
#params shared(x10f)
params shared(x10*)
#params shared(x10*)
#params
shared(x109)
Figure 64: LEGK as Plug-and-Plcs Algorithm.. Experimental results in Fig. 7 repeated for dataset: CIFAR-10. FMNIST, and MNIST (iid data distribution) using classifier: CNN.
LBGM
LBGM
MNIST
MNIIST
FMNIST IID/Tap-K
FMNIST Nan-IID/Top- og-K
MNIST IIDATOMO
MNIST Non-ID/ATOMO
FMNIST IIDAATOMO
FMNIST
II/TTp-K
Non-lII3/op--K
Nen-IID/ATOMO
1.00
3,00
1.00
1.00
1.30
1.00
accuracy
3.78
0.2
0.75
850
0.50
shared [x] (109)
sporams
0.75
0.75
0.75
1.5
3.50
0.50
0.52
1.3
10
1.0
0.25
0.23
0.5
2.5
3.00
23
53
75
300
0.00
25
50
75
100
0.02
23
30
75
100
0.02
23
50
130
0.0
25
50
75
100
0.0
25
100
0.0
23
53
73
120
3.0
23
50
75
300
1.00
3.00
1.00
1.00
1.50
accuracy
0.75
0.75
0.75
0.75
0.75
0.55
0.75
0.75
8:0
0.52
222
022
0.25
0.0%
0.03
0.03
0.00
0.30
0.00
#params
#params shared(x10$)
#params shared(x10P)
#params chared(x109)
#params shared(x109)
#params shared(x10-)
#params shared(x10
shared(x10
shared(x10#)
Figure 65: LBGM as a Plug- and-Play Algorithm. Experimental results in Fig. 7 repeated for datasets: FMNIST and MNIST (both iid and non-iid data distribution) using classifier: FCN.
67

---

Published as a conference paper at ICLR 2022
w/o LBGM
w/ LBGM
CIFAR-10
CIFAR-100
CelieAA Top-K
CIFAR-10 Nan-IID/ATOMO
CIFAR-100 Non-IID/ATOMO
CelebA ATOMO
Non-IID/Top-K
Non DimpllI/TTp-** K
0.0
loss (x10*)
6 accuracy
0.5
0.2
50 100 150 230
0.0
125
250
375
520
0.0g
25
50
100
0.0
125
250
375
500
0.0
125
256
375
500
00
25
55
75 150
shared (x10%)
t
#params
5.0
2.5
2.5
0.5
30
100
130
250
520
30
100
0.0
125 250
375 300
125
375
000
75
loss (x10%)
loss (x109)
accuracy
0.4
0.4
84
1.0
0.4
16
22
0.2
0.5
0.2
02
G
0
10
1o
#params sxored(x10*)
#params shared(x10*)
#params shared(x10*)
#params shared(x10*)
#params
shared(x10*)
shared(X10*)
Figure 66: Effect of 6
5threshold 1.RGM. Experimental results in Fig. 7 repeated for datasets: CIFAR-10.
CIFAR-100 (non-iid data distrihution), and CelebA (face landmark regression task) using elassifier: Resnet18.
w/o LBGM
w/ LBGM
MNIST IIDSSigSSDD
FMNIST IIDSSigSSDD
CIFAR-10 IIDSSignSDD
1.00
accuracy
0.75
0.75
0.50
0.25
0.00
0.00
25
50
100
25
50
75
100
125
250
375
500
shared )
#bits
2
0.2
0.0
1.00
accuracy
0.75
0.6
0.75
0.50
0.50
0.4
0.25
0.2
0.00
0.00
0.0
# bits shared(x109)
# #bits
#bits
(x19))
shared (008))
Figure 67: Experimental results Fig. repeated for dataset: CIFAR-10, FMNIST, FMNIST (iid data distribution) using classifier: CNN.
68

---

Published as a conference paper at ICLR 2022
w/o LBGM
w/ LBGM
MNIST IIDSSignSGD
MNIST
FMNIST IIDSSignSGD
FMNIST
Non-lID/SignSGD
Non-IID/SignSGD
1.00
0.8
0.8
accuracy
0.75
0.6
0.6
0.50
0.4
0.50
0.4
0.25
0.2
0.2
0.00
0
0.0
0.00
0.0
accuracy shared (x10%)
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
#bits
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0
0.00
0
100
0.00
1.00
0.8
0.8
0.75
0.6
0.6
0.50
0.4
0.50
0.4
0.25
0.2
0.2
0.00
0.0
0.0
0.00
D.0
8.0
#bits
# bits
# bbits
#bits
(005)
(
sxared(x109)
(x
Figure 68: Experimental results in Fig. 8 repeated for dataset: FMNIST and MNIST (both iid and non-iid data distribution) using classifier: FCN.
w/o LBGM
w/ LBGM
CIFAR-10
CIFAR-100
CelebA SignSGD
Non-IID/SignSGD
Non-IID/SignSGD
0.8
0.6
lOSS (X104)
accuracy
0.6
1.5
0.4
0.2
0.2
0.5
0.0
0.0
0.0
150
200
125
250
200
shared (x106)
150
t
300
#bits
100
100
200
50
100
0
0
100
150
200
125
250
375
500
50
100
150
200
t
0.8
0.6
loss (x104)
2.0
accuracy
0.6
1.5
0.4
0.2
0.2
0.5
0.0
50
100
150
200 #bits
100
#bits
bitss
shared x (005))
shared( x 106)
chared(x106)
Figure 69: Effect of 5 gthreshold
LEGM. Experimental results in Fig. 8 repeated for datasets: CIFAR-10. C1EAR-100 (non-iid data distribution), and CelebA (face landmark regression task) using classifier: Resnet18.
69

---

Published as a conference paper at ICLR 2022
Vanilla FL LBGM
MNIST Non-IID
FMNIST Non-IID
CIFAR-10 Non-IID
CelebA Regression
1,00
0.6
2.0
accuracy
0.75
M
0.75
1.5
0.4
0.25
0.25
0.5
0.00
0.00
0.0
0.0
25
50
75
100
25
100
125
250
375
500
0
75
150
225
300
shared (x106)
t
40
#params
300
150
20
200
100
100
50
0
0
50
125
500
1.00
0.6
loss x100)
2.0
accuracy
0.75
0.75
1.5
0.50
0.50
1.0
0.25
0.25
0.2
0.5
20
40
200
400
100
200
#params
#params shared(x10*)
#params
#params
shared(x10t)
shared(x109)
shared(x109)
Figure 70: Experimental results Fig. repeated for dataset: CIFAR-10, FMNIST, FMNIST (non-iid data distribution) and CelebA (face landmark regression taks) using classifier: CNN under 50% client sampling for both Vanilla FL. and LBGM.
Vanilla FL
LBGM
MNIST IID
FMNIST IID
CIFAR-10 IID
1.00
accuracy
0.75
0.4
0.50
0.50
0.25
0.00
0.00
0.0
50
25
100
125
500
shared (x10%)
400
#params
300
20
20
200
0
50
100
25
50
100
0
125
250
500
1.00
0.6
accuracy
0.75
0.75
0.4
0.50
0.25
0.2
0.00
0.00
0.0
20
40
20
40
200
400
# #params
# #params
#params
shared(x109)
shared 1
Figure 71: Experimental results in Fig. 5 repeated for dataset: CIFAR-10, EMNIST. FMNIST (iid data distribution) using classifier: CNN under 50% client sampling for both Vanilla FL and LBGM.
70


Reviews:
[{"review_id": "zb4yHGWyNo5", "reviewer": "Reviewer_X6Uf", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "In general, I think the proposed algorithm is quite novel and interesting. It explores a new research direction to reduce the communication in FL. The theoretical analysis is also a nice addition to the paper. It provides many useful insights about the proposed algorithm.\n\nIn terms of weakness, I mainly have two concerns:\n1. In experiments, it seems that in most cases, using LBGM will degrade the performance a lot. For example, in figure 5, on CIFAR-10, the accuracy nearly drops 5-10%. Although the communication is significantly reduced, the performance degradation may prevent people using this algorithm.\n2. The algorithm is more suitable for classical distributed learning rather than federated learning. I encourage the authors to change the title and related parts in the paper. The reason is that in FL, at each round, only a few (maybe around 1-10%) clients will participate into training. That means, one client can be inactive for multiple rounds. As a result, the principle component on this client will likely be stale when it participate training again. So the client needs to transmit full gradient again. In this case, the benefits of using LGBM may diminish..  ", "summary_of_the_paper": "This paper proposed two hypothesis: (1) the space spanned by gradients generated during training is low-rank; and (2) the principle components can be approximated by the gradients generated during training. The authors first validated these two hypotheses on several datasets. Then, based on these, they proposed a new algorithm called LBGM to reduce the communication costs in federated learning. In the algorithm, the clients local gradients will be treated as the principle components (if there are K clients, then we have K principle components). Then, during training, each clients only needs send a scalar, which represents the coefficient of the corresponding components, to the server. Hence, the communication costs in FL can be significantly reduced.", "summary_of_the_review": "This paper proposed a novel idea to reduce communication in FL. However, it seems non-trivial to make this algorithm to work with partial client participation. Without this extension, I feel the current algorithm is more suitable for classical distributed training than FL.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "qvzW5A8R0Fl", "reviewer": "Reviewer_X8h7", "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": "**Novelty:** The idea of model updates in a low-rank subspace is not new. In fact, it has been mentioned in one of the pioneering papers on federated learning:\n- Konecny et al., Federated learning: Strategies for improving communication efficiency, 2016 (Section 2)\n\nThe core idea of low-rank updates in this paper is the same as the low-rank structured update in the above paper by Konecny et al. While the convergence analysis in this paper may be a new result, the proof technique is relatively standard and is similar to other works on delayed/compressed SGD. In general, it is not surprising to achieve a convergence result comparable to existing algorithms under the condition of $\\Delta^2 \\\\leq \\\\eta$ where $\\\\eta$ is inversely proportional to $1/\\\\sqrt{T}$ in Corollary 1. Furthermore, I feel that the current Algorithm 1 may be too specific in the sense that it only allows sending a scalar LBC that is related to the angular difference. The algorithm would be more flexible if an arbitrary (but given) number of scalars is allowed to be transmitted, where the number of scalars depends on the dimension of the constrained subspace of updates.\n\nIt is also worth mentioning that similar observations of low-rank gradient subspaces have been made and leveraged in continual learning literature:\n- Chaudhry et al., Continual Learning in Low-rank Orthogonal Subspaces, NeurIPS 2020.\n- Saha et al., Gradient Projection Memory for Continual Learning, ICLR 2021.\n\n**Practical feasibility:** It is difficult for the proposed algorithm to work in large-scale federated learning systems. The algorithm needs to store copies of look-back gradients (LBGs) for all the clients at the server, which would consume a huge amount of storage in realistic on-device federated learning systems with over millions of clients. Furthermore, in such large-scale systems, it is only feasible for only a small percentage of clients to participate in each federated learning round, i.e., random client sampling needs to be performed. This paper does not seem to consider client sampling/selection at all, not in the algorithm description, analysis, nor in the experiments.\n\n**Experiments:** It is not clear how the hyperparameters were found in the experiments, such as the threshold for LBGM and the value of K for top-K. This is important since the performance of each method could largely depend on the choice of these critical hyperparameters, so the hyperparameters should be found methodologically (e.g., using grid search) instead of chosen arbitrarily. The comparison is only fair if the hyperparameters for each method has been optimized for the method itself. In addition, it is a bit difficult to align the communication savings with the accuracy curves. It would help if figures showing accuracy vs. number of bytes transmitted could be added.\n\n**Minor:** \n- It seems that the spacing has been squeezed quite a lot to fit the paper into 9 pages. This should be avoided. For example, some detailed discussion on related work may be moved to the beginning of the appendix.\n- In the related work section, Gradient Compression paragraph, there is a sentence saying \"These works were originally proposed for inter-GPU communication speedups and not FL.\" This is incorrect. There has been many papers that discuss gradient compression in the context of federated learning. For example:\n  - Haddadpour et al., Federated Learning with Compression: Unified Analysis and Sharp Guarantees, AISTATS 2021.\n  - Albasyoni et al., Optimal Gradient Compression for Distributed and Federated Learning, 2020.\n", "summary_of_the_paper": "The paper presents an efficient federated learning method which leverages the empirical observation that the gradients used in model updates are usually in a low-rank subspace. Based on this observation, a \"look-back gradient multiplier\" (LBGM) method is proposed that only updates a scalar look-back coefficient (LBC) as long as the angular difference between the stored gradient and the latest gradient is within a given threshold. A theoretical analysis of this method is given in the paper and the performance is also verified in various experiments.", "summary_of_the_review": "While communication efficiency is an important aspect in federated learning, this paper appears to have limited novelty and also some issues regarding practical feasibility and experiments.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fG5vCDVXVif", "reviewer": "Reviewer_FQxe", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "From my perspective, the main novelty is two folds.\nOne is the investigation of the gradient subspace, while the other is the proposed method which reuses similar past gradients to save communication.\nThe proof technique for the theorem is standard. However, it seems to have some mistakes, which though can be fixed with additional efforts and some quantities redefined.\nThe paper provides abundant experiments which I appreciate a lot.\nExperiments illustrate communication efficiency and the plug-and-play property of their method.\nMost of the writing is clear but some parts are hard to understand.\n\nI have the following concerns:\n1. The readability for Figure 1-3 should be improved. Without the help of Algorithm 2, I can’t figure out the meaning of each coordinate axis. \n2. In the first paragraph of Section 3, it is better to add $\\theta^{(t, 0)}_k$ is initialized as $\\theta_k$ explicitly. \n3. The description of LBGM Algorithm is hard to understand at the first glance. Some undefined terms are used, like look-back coefficients. I have to look up their meanings and exact mathematical forms in Lemma 1 and Algorithm 1, which increases the reading burden. I suggest the author could give a specific definition of frequently used terminology at the beginning. Besides, to better deliver the main idea of Algorithm 1, certain properties could be provided. For example, each device uploads just one LBG to the server, and the server tracks and maintains all updated LBGs.\n4. Lemma 1 seems to have a mistake. Since both $\\rho_k^{(t), \\ell}$ and $\\cos(\\alpha_k^{(t), \\ell})$ are scalers, the equality (L1) implies that the vectors $g_k^{\\ell}$ and $g_k^{(t)}$ have the same direction (and thus are parallel), which is contradictory to (a) in Figure 4, where $g_k^{\\ell}$ and $g_k^{(t)}$ has an angle. \n5. The equality of the projections of a vector into two different vectors, though being wrong, is frequently used in the proof of Theorem 1. As a result, (14) and the first line of $Z_5$ are incorrect. However, these mistakes can be avoided. Letting $\\tilde{d}_k^{(t)} = d_k^{(t)} \\cos(\\alpha_k^{(t), \\ell})$ and abandon $\\tilde{d}_k^{(t)} =  \\rho_k^{(t), \\ell}d_k^{\\ell}$ solve the first problem. To bound $Z_5$, we can directly use the fact: $(1-\\cos \\theta)^2 \\le |\\sin \\theta|$ for all $- \\pi/2 \\le \\theta \\le \\pi/2$. In the way, though Theorem 1 can be rescued to be correct, the current proof is definitely not ready for publication.\n6. It is unclear the frequency of LBC being transmitted. Note that communication is only saved when we communicate LBC rather than the whole vector. In the paper, related results include Figure 5 and 6 which investigates the variation of the total number of parameters shared. Besides, to compute the LBPs, we should first compute $\\nabla F(\\theta_k^{(t)})$ which incurs additional communication. I don’t know whether Figure 5 and 6 have taken this factor into account or not.\n\nSome discussion:\n1. I think there are more choices to set LBGs. In the paper, the LBG are just one of the history gradient. Why not define LBG as a moving average? This means we update the new LBG as the average of all LBGs. When the algorithm starts to converges, the average could be more stable.\n2. The paper spends a lot of time studying the low-rank property of subsequent gradients. Why not let each device maintain more than one LBGs? In this way, each device has an LBG set, which is updated when the space it spans can’t explain the variance of the new coming LBG. Maybe we need PCA to determine whether the LBG set meets the requirement. With more LBGs, I guess the empirical performance would be improved further. After all, current experiments show with LBGM the test accuracy might slightly decay.", "summary_of_the_paper": "The paper studies the gradient subspace and finds it low-rank propery.\nThis observation motivates them to propose a new algorithm that reuses similar past gradients to save communication.\nThey provide a theoretical analysis (with some mistakes) and conduct experiments to validate their method.", "summary_of_the_review": "I appreciate the empirical investigation of low-rank gradient space and the idea behind the proposed method.\nHowever, the current version of this paper is not proper for publication due to the mentioned concerns.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Iuz3Xv8gjKU", "reviewer": "Reviewer_LE1r", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "## Important existing work\n\nI'd prelude everything by first mentioning **[this paper](https://arxiv.org/pdf/2103.11154.pdf)** from earlier this year, which is closely related to the paper but hasn't been cited. It approximates the subspace $S$ using only the (first-order) information from the optimization trajectory and then uses it to build a quasi-newton method. In light of this, it is not true that the paper is the first work that studies, \n>the effect of overparameterization on optimization of NN via the rank-characteristics of the first order optimization (gradient) landscape.\n \nFurthermore, an **[older paper](https://arxiv.org/pdf/1812.04754.pdf)** (which is cited) has already made the case that the stochastic gradients lie in a tiny sub-space, which is **(H1)** in this paper. I don't understand why this is underplayed while discussing this paper in the related works section, where this paper is clubbed with other papers that study the hessian?\n\nHaving said that, I am a bit apprehensive about both **(H1)** and **(H2)** (more below). But if we believe these hypotheses, it is indeed novel to use them in the context of federated learning. I'd encourage the authors to revise their writing and their discussion of novelty in the light of these papers. \n\n## Results on other data-sets\n\nIt is commendable that the authors do experiments with many different data sets and architectures and include them in the appendix. However, I am not convinced that the two hypotheses **(H1)** and **(H2)** are well corroborated in all the experiments. For instance, it is not clear if **(H1)** holds true in figures 11 and 13. Why were these experiments not run long enough to actually let the PCA components stabilize and the curve flatten out? Similarly in figures 18, 19, 23, 26, 27, 31, i.e., experiments with bigger models it is not clear if either hypothesis is true, and the figures look uninformative when compared to figure 2 which is presented in the main paper. Similarly, the consecutive gradient alignment curves in figures 52, 53 look uninformative. \n\nI am not saying that this phenomenon can be refuted entirely, but it seems that it is at least not robust to the choice of the model and dataset. And this has not been discussed sufficiently in the paper. \n\nFinally, why were figures 5-8 not presented for instance for U-Net for Pascal-VOC? Were the improvements worse? If they were it is important to include those for a fair presentation of the work. In fact, for this technique to be relevant to federated learning, it is important to know how it scales to bigger models and datasets. I am specifically mentioning this instance, based on the gradient alignment curves and model size.  \n\n### Learning rate scheduling\nWhat is happening at the 25th iteration in figure 3 for CelebA? Is there a learning rate decay there? These kinds of shifts in principal components happen throughout all the curves in the appendix as well. Looking at the provided code it is not clear what learning rate schedules were used for respective figures, and it would be good to highlight this in the paper. More importantly, does the schedule impact the principal components? It seems to be the case looking at the curves. It would be good to investigate that.\n\n## Convergence Rate\n\nI am mostly happy with the convergence analysis and the following discussion. The analysis is not particularly novel, but it is good to see how $\\Delta$ appears in the convergence guarantee.  \n\n***\n\n## Minor comments\n\n>Can we observe the effect of overparameterization in gradient descent-based optimization of NNs    \n\n1) This comes off as an ill-posed question, given the plethora of empirical and theoretical work that has come up in this area.\n    \n>We further reveal that LBGM can be extended to distributed training\n\n2) The distinction that the authors make between FL and distributed training is slightly confusing (even later in the paper). Latter subsumes the former, and it seems that the authors want to demarcate between homogeneous v/s heterogeneous data-distribution settings or cross-silo v/s cross-device FL. This is especially confusing when the authors choose to demarcate between the baselines for **P2** and **P3**. I think the point there is that just communicating gradient signs can be detrimental for the heterogeneous setting?\n  \n3) I don't like the term *principal gradients* for principal components of $S$, as they are not really *gradients*. Moreover, I couldn't find anywhere a mathematical description of how these components are calculated, perhaps using SVD of the concatenation of all the gradients? The pseudocode in the appendix just uses a black-box function. It would be useful to include this in the appendix and specify how different levels of variance are specified.  \n\n>SGD is resilient to noisy updates and often benefits from them in terms of generalization error\n\n4) This is a vague statement, first of all, what does it mean for an optimization algorithm to be resilient to noisy updates? Do you mean that the analysis of SGD can be done for any unbiased stochastic gradients, with bounded variance? That is true, but it is unclear (at least apriori) if the noise introduced by the LBGM procedure is like that. This is a slippery slope argument to make. Or do you mean that while training with SGD, additive noise doesn't hurt the performance? If you mean the latter, I am not convinced that there is conclusive evidence to show this, across a range of models, data sets, and noise levels. So this is an underqualified statement as well. Please re-write this sentence or avoid it. \n\n5) Lemma 1 seems trivial to me. You are basically re-deriving what it means to project onto a vector. Is it really worth putting this into a lemma and writing a proof? or am I missing something here? \n\n> S2: FCN on FMNIST and FMNIST\n\n6) Typo \n \n>The fact that rank deficiency of the gradient-space is not a consequence of model complexity or model performance suggests that the gradient-space of state-of-the-art large-scale ML models could be represented using a few principal gradient directions.\n\n7) I was hoping that the authors will further investigate what causes this rank deficiency. That would have been a significant contribution by itself. **[This paper](https://arxiv.org/pdf/2103.11154.pdf)** conjectured that it had something to do with the number of classes in the data-set. Could the authors corroborate or refute that claim?\n\n8) In many experiments (such as figure 2) the stochastic gradients were almost determined by a single PCA gradient. Did the authors investigate what caused this? How is the learning rate being decayed in these figures?\n\n9) Did the authors experiment with layer-wise PCA gradients? Perhaps even a proof of concept experiment could be done by using actual principal components of $S$?     ", "summary_of_the_paper": "This paper hypothesizes that,  \n**(H1)** the subspace $S$ spanned by the stochastic gradients while training through SGD is low rank, and  \n**(H2)** $S$ is well approximated by a subset of the actual stochastic gradients. \n\nIt provides empirical evidence to support these claims by calculating,   \n(i) the number of principal components that almost explain the entire variance of the stochastic gradients over time, and  \n(ii) the alignment between the principal components of $S$ and the stochastic gradients, as well as the consecutive stochastic gradients, across different models and data sets. \n\nWith these observations, the paper aims to reduce the complexity of the communicated bits between the devices in data-parallel distributed training. Specifically, it proceeds by first estimating the principal components of $S$ through consecutive stochastic gradients. These vectors are then stored at the server as well as each worker. At each communication round the device then only needs to share the projection coefficients for these principal vectors, until the set of the principal vectors needs to be updated and broadcasted to all the machines. \n\nThis technique is empirically shown to reduce the communicated bits while almost retaining the performance on certain data sets. A convergence rate is also provided for this algorithm under assumptions that highlight the trade-off between the frequency of updating the principal vectors and the convergence rate to a first-order stationary point.   ", "summary_of_the_review": "I think the claims of novelty in the first half of the paper are slightly inflated. The application to federated learning is definitely novel though and should become the focus of the paper. This can be done by improving the discussion of the related work, providing fair and well-rounded evidence for the low-rank hypotheses, and extending the experiments for federated learning to the biggest data-set and model possible. I am open to increasing my score if my concerns are addressed. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that most variance of gradients used in FL and distributed learning in general is in very low rank subspaces, an observation also made in Konecny et al 2016 and some other related works in deep learning, though sometimes for a different purpose.
The paper then proposes lightweight updates combining a fresh gradient with old updates. Experiments and a theoretical convergence guarantee complement the results, which are mostly convincing. 

The experiments compare against ATOMO but strangely not against the more common PowerSGD, which would also work with partial client participation.

Overall, reviewers all agreed that the paper is interesting, well-motivated and deserves acceptance.
We hope the authors will incorporate the open points as mentioned by the reviewers.
Decision: Accept (Poster)