Compressed-VFL: Communication-Efficient Learning with Vertically Partitioned Data
Authors: Timothy Castiglia
Anirban Das
Shiqiang Wang
Stacy Patterson
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Learning
Optimization
Split Learning
Cross-Silo Learning
Compression
Quantization
Sparsification

Abstract: We propose Compressed Vertical Federated Learning (C-VFL) for communication-efficient training on vertically partitioned data. In C-VFL, a server and multiple parties collaboratively train a model on their respective features utilizing several local iterations and sharing compressed intermediate results periodically. Our work provides the first theoretical analysis of the effect message compression has on distributed training over vertically partitioned data. We prove convergence of non-convex objectives to a fixed point at a rate of $O(\frac{1}{\sqrt{T}})$ when the compression error is bounded over the course of training. We provide specific requirements for convergence with common compression techniques, such as quantization and top-$k$ sparsification. Finally, we experimentally show compression can reduce communication by over $90\%$ without a significant decrease in accuracy over VFL without compression.

Under review as a conference paper at ICLR 2022
COMPRESSED-VFL, COMMUNICATION-EERRCENN LEARNING WITH VERTICALLY PARTITIONED DATA
Anonymous authors Paper under double-blind review
ABSTRACT
We propose Compressed Vertical Federated Learning (C-VFL) for communication-efficcen training on vertically partitioned data. In C-VFL. server and multiple parties collaboratively train model their respective features utilizing several local iterations and sharing compressed intermediate results periodically. Our work provides the first theoretical analysis of the effect message compression has on distributed training over vertically partitioned data. We prove convergence of non-convex objectíves to fixed point rate of O when the compression error is bounded over the course of training. We provide specific requirements for convergence with common compression tech- niques, such as quantization and top-k sparsification. Finally, we experimentally show compression can reduce communication by over 90% without significant decrease in accuracy over VFL without compression.
INTRODUCTION
Federated Learning (McMahan et al., 2017) is distributed machine learning approach that has become of much interest in both theory (Li et al., 2020; Wang et al., 2019; Liu et al., 2020) and practice (Bonawitz al., 2019; Rieke et al., 2020; Lim et al., 2020) recent years. Naive distributed learning algorithms may require frequent exchanges of large amounts of data, which can lead to slow training performance (Lin et al., 2020). Further, participants may be globally distributed, with high latency network connections. To mitigate these factors, Federated Learning algorithms aim to communictiion-effiiene by design. Methods such as local updates (Moritz et al., 2016; Liu et al, 2019), where parties train local parameters for multiple iterations without communication. and message compression (Stich et al., 2018; Wen et al., 2017; Karimireddy et al., 2019) reduce message frequency and size, respectively, with little impact training performance.
Federated Learning methods often target the case where the data among parties distributed hori- zontally: each party's data shares the same features but parties hold data corresponding to different sample IDs. This is known as Horizontal Federated Learning (HFL) (Yang et al., 2019). However, there are several application areas where data is partitioned in vertical manner: the parties store data on the same sample IDs but different feature spaces.
An example of vertically partitioned setting includes a hospital, bank, and insurance company seeking to train a model to predict something of mutual interest, such as customer credit score. Each of these institutions may have data on the same individuals but store medical history, finan- cial transactions, and vehicle accident reports. respectively. These features must remain local to the institutions due privacy concerns, rules and regulations (e.g.. GDPR, HIPAA), and/or communi- cation network limitations. In such a scenario, Vertical Federated Learning (VFL) methods must be employed. Although VFI. less well-studied than HFI,, there has been growing interest in VFI. algorithms recently (Hu et al., 2019; Gu et al., 2021; Cha et al., 2021), and VFL algorithms have important applications including risk prediction, smart manufacturing, and discovery of pharmaceu- ticals (Kairouz al., 2021).
Typically in VFL, each party trains a local embedding function that maps raw data features to a meaningful vector representation, embedding, for prediction tasks. For example, neural network can be an embedding function for mapping the text of an online article to a vector space for classi- fication (Koehrsen, 2018). Referring Figure Ia, suppose Party 1 is hospital with medical data

---

Under review as a conference paper at ICLR 2022
(rosphad)
Server
Compeesied Server Modol
(Bark)
By boy
C. (1
Compressd Embeddings
No (8,12u)
Cythatl 3
(a) Example a global model.
(b) Local view of a global model.
Figure I: Example global model with neural networks and its local view. a) To obtain ő prediction for data sample I, each party m feeds the local features of z, Im, into a neural network. The output of this neural network is the embedding hm (fm 3m). All embeddings are then fed into the server model neural network with parameters Og- b) When running C-VFL, Party 1 (in green) only has compressed snapshot of the other parties embeddings and the server model. To calculate ÿ. Party uses its own embedding calculated at iteration t, and the embeddings and server model calculated at time lg, the latest communication iteration, and compressed with C...
features 2T. The hospital computes its embedding hi (01; for the features by feeding xı through a neural network. The other parties (the bank and insurance company), compute embeddings for their features, then all parties share the embeddings in a private manner (e.g., homomorphic encryp- tion, secure multi-party computation, or secure aggregation). The embeddings are then combined in server model 6n to determine the final loss of the global model. A server model (or fusion network) captures the complicated interactions of embeddings and is often a complex, non-linear model (Gu al., 2019; Nie al., 2021; Han al., 2021). Embeddings can be very large, in practice, sometimes requiring terabytes of communication over the course of training.
Motivated by this, propose Compressed Vertical Federated Learning (C-VFL), a general frame- work for communication -efficiennn Federated Learning over vertically partitioned data. In our algo- rithm, parties communicate compressed embeddings periodically, and the parties and the server each run Mlock-coordinate descent for multiple local iterations, in parallel, using stochastic gradients to update their local parameters.
C-VFL is the first theoretically verified VFL algorithm that applies embedding compression. Unlike HFL algorithms, C-VFL compresses embeddings rather than gradients. Previous work has proven convergence for HFL algorithms with gradient compression (Stich et al., 2018: Wen et al., 2017; Karimireddy et al., 2019). However, no previous work analyzes the convergence requirements for VFL algorithms that use embedding compression. Embeddings parameters in the partial deriva- tives calculated at each party. The effect of compression eиrоr on the resulting partial derivatives may be complex; therefore, the analysis in previous work gradient compression in HFL does not apply to compression in VFL. In our work, we prove that, under a diminishing compression error, C-VFL converges at a rate of O (T)),, which is comparable to previous VFL algorithms that do not employ compression. We also analyze common compressors, such as quantization and sparsification, in C-VFL and provide bounds on their compression parameters to ensure convergence.
C-VFL also generalizes previous work by supporting an arbitrary server model. Previous work in VFL has either only analyzed an arbitrary server model without local updates (Chen et al., 2020), or analyzed local updates with a linear server model (Liu et al., 2019; Zhang et al., 2020; Das & Patterson, 2021). C-VFL is designed with arbitrary server model, allowing support for more complex prediction tasks than those supported by previous VFL algorithms.
We summarize main contributions in this work.
1. We introduce C-VFL with an arbitrary compression scheme. Our algorithm generalizes previous work in VFL by including both an arbitrary server model and multiple local iterations.
2. We prove convergence of C-VFL to fixed point on non-convex objectives at a rate of O V for fixed step size when the compression error is bounded over the course of training. We also prove that the algorithm convergence error goes to zero for a diminishing step size if the compression error diminishes well. Our work provides novel analysis for the effect of compressing embeddings on
2

---

Under review as a conference paper at ICLR 2022
convergence in VFL algorithm. Our analysis also applies to Split Learning when uploads to the server are compressed.
3. We provide convergence bounds on parameters in common compressors that can be used in C- VFL. In particular, examine scalar quantization (Bennett, 1948). lattice vector quantization (Za- mir & Feder, 1996), and top-k sparsification (Linn et al., 2018).
4. We evaluate our algorithm by training LSTMs on the MIMIC-III dataset and CNNs on the Mod- elNet10 dataset. We empirically show how C-VFL can reduce the number of bits sent by over 90% compared to VFL with no compression without a significant loss in accuracy of the final model.
Related Work. Richtárik & Takác (2016); Hardy et al. (2017) were the first works to propose
Federated Learning algorithms for vertically partitioned data. Chen al. (2020); Romanini et al. (2021) propose the inclusion of an arbitrary server model in a VFL. algorithm. However, these works do not consider multiple local iterations, and thus communicate every iteration. Liu et al. (2019), Feng & Yu (2020), and Das & Patterson (2021) all propose different VFL algorithms with local iterations for vertically partitioned data but do not consider an arbitrary server model. In contrast to previous works, our work addresses a vertical scenario, an arbitrary server model, local iterations, and message compression.
Message compression is common topic in HFL scenarios, where participants exchange gradi- ents determined by their local datasets. Methods of gradient compression in HFL include scalar quantization (Bernstein et al., 2018), vector quantization (Shlezinger et al., 2021), and top-k spar- sification (Shi et al., 2019). In C-VFL, compressed embeddings are shared, rather than compressed gradients. Analysis in previous work on gradient compression in HFL does not apply to compres- sion in VFL, as the effect of embedding compression error on each party's 's partial derivatives may be complex. No prior work has analyzed the impact of compression convergence in VFL.
Outline. In Section 2, we provide the problem formulation and our assumptions. Section 3 presents the details of C-VFL. In Section 4, we present our main theoretical results. Our experi- mental results are given in Section 5. Finally, we conclude in Section 6.
PROBLEM FORMULATION
We present our problem formulation and notation be used in the rest of the paper. We let ||a|| be the 2-norm of a vector a, and let y be the Frobenius norm of matrix A.
We consider a set of M parties (I....,M M) and a server. The dataset X E NND is vertically partitioned priori across the M parties, where N is the number of data samples and is the number of features. The i-th row of X corresponds to a data sample x". For each sample x', party m holds disjoint subset of the features, denoted a so that x = [ai,.... wMM. For each x² there a corresponding label y¹. Let y E Nx be the vector of all sample labels. We let Xm NDD. be the local dataset of a party m. where the i-th row correspond to data features rim. We assume that the server and all parties have a copy of the labels y. For scenarios where the labels are private and only present at single party, the label holder can provide enough information for the parties to compute gradients for some classes of model architectures (Liu et al., 2019).
Each party holds set of model parameters O. as well as a local embedding function (.)..). The server holds set of parameters 0g called the server model and a loss function 1(-) that combines the embeddings hm (0mi xnr)) from all parties. Our objective is as follows:
minimize F(O;X;y) = 6
Σ 100, hn (f1; (0
where θ - 108 ... o I is the global model. An example of global model θ is in Figure la.
For simplicity, we let m = O refer to the server. and define ho ho x²)
= Op for
all x', where ho(-) equivalent to the identity function. Let hm (fm: am) E R Pm for
m = O...., M, where Pm is the size of the m-th embedding. Let Vn X:y: =
N Di Vo, 100, hy xf)= h (ex))...,,MM(AA. (Oms; )= be the partial derivatives for parameters 0...
3

---

Under review as a conference paper at ICLR 2022
Let X" and yB be the set of samples and labels corresponding randomly sampled mini-batch
of size B. We let the stochastic partial derivatives for parameters 8m be Vm (;; X:y) = (O ((0ss=''y))) =xy);; y). We may drop X and y from F(-) and Fb(.). With minor abuse of notation, we let (0m: X
................................ B La Vo.. 1(0,, i ()) ...
[Amm(0n)) =m "m").... )...., hm (0m: =B" }} be the set of all party embeddings associated with mini-batch B, where B is the i-th sample in the mini-batch B. We let v' and Vn Vm/'nOo. hi (01; ".,,..,,, XB M)) and use them interchangeably.
be equivalent,
Assumption 1. Smoothness: There exists positive constants L< 00 and Lm < cc, for m 0,- 0,.... M, such that for all O₁ O2 the objective function satisfies - L 1 - 02 and (v,FB(O1) V (mFF((2)) S Lm 1 O2l1-
Assumption 2. Unbiased gradients: For m O...., M. for randomll selected mini-batch B, the stochastic partial derivatives are unbiased, i.., Eg V F Fn()) = ((e).
Assumption 3. Bounded variance: For mn = O,...,,, there exists constants om < co such that the variance of the stochastic partial derivatives are bounded as: VgI[Vm F(O) - Vn FB (e)
o B for a randomly selected mini-batch B of size B.
Assumption bounds how fast the gradient and stochastic partial derivatives can change. Assump- tions 2 and 3 require that the stochastic partial derivatives are unbiased estimators of the true partial derivatives with bounded variance. Assumptions 1-3 are common assumptions in convergence anal- ysis of gradient- based algorithms (Tsitsiklis et al., 1986; Nguyen et al., 2018: Bottou et al., 2018). We note Assumptions 2-3 are similar to the IID assumptions in HFL convergence analysis. How- ever, in VFL settings, all parties store identical sample IDs but different subsets of features. Hence, there is no equivalent notion of a non-lID distribution in VFL.
Assumption 4. Bounded Hessian: There exists positive constants Hm for m O,..., M such that for all O the second partial derivatives of FB with respect to hm x satisfy: S Hm any mini-bateh B.
? Assumption 5. Bounded Embedding Gradients: There exists positive constants Gm for m O...., M such that for all 8m. the stochastic embedding gradients are bounded by: o hm (0m; X m) }>> S Gm for any mini-batch B.
F FF(())l> hm (m xe,
Since we are assuming Lipschitz-contimuous loss function (Assumption 1), we know the Hessian of F is bounded. Assumption 4 strengthens this assumption slightly to also bound the Hessian over any mini-batch. Assumption 5 bounds the magnitude of the partial derivatives with respect to embeddings. This embedding gradient bound is necessary to ensure convergence in the presence of embedding compression error (see appendix for details).
3 ALGORITHM
We now present C-VFL., a communication-effiienee method for training global model with verti- cally partitioned data. In each global round, a mini-batch B is chosen randomly from all samples and parties share necessary information for local training on this mini-batch. Each party, in parallel, runs block-coordinate stochastic gradient descent on its local model parameters On. for Q local iterations. C-VFL runs for a total of R global rounds, and thus runs for T RQ total local iterations.
For party m to compute the stochastic gradient with respect to its features, it must receive embed- dings from all parties. We reduce communication cost by only sharing embeddings every global round. Further, each party compresses their embeddings before sharing. We define a set of general compressors for compressing party embeddings and the server model: C.)(.) R. - PR for m = 0. M. To calculate the gradient for data sample x², party m receives C, (0;;; from all parties j of m. With this information, a party m can compute Vm and update its parameters Om for multiple local iterations. Note that each party uses a stale view of the global model to com- pute its gradient during these local iterations, as it is reusing the embeddings it receives at the start of the round. In Section 4, we show that C-VFL converges even though parties An example view party has of the global model during training is in Figure 1b. Here, is the current iteration and to is the start of the most recent global round, when embeddings were shared.
stale information.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Compressed Vertical Federated Learning
1: Initialize: 6% for all parties m and server model g
2: for I 1-4-0 0,..., T 1 do
3: if I mod Q = 0 then
4:
Randomly sample B' E (X.y)
5: for m t 1,... .M in parallel do
Send Cm (hm (Om X
6:
server
7:
end for
Server sends (Co( C1 (h1 (01; XT )), )),... Cas (hes (Ohri xX() to all parties
8:
9:
end if
for m f- .....,,M .M in parallel do
11: tb m f- (Co(00)), Ci (hi (0f:; x1 )).... .... hm i ) CaM
G f n7 V FB (5t mi y
12:
13: end for
14: end for
Algorithm details the procedure C-VFL. In each global round, when & mod Q = 0, a mini- batch B is randomly sampled from X and the parties exchange the associated embeddings, com- pressed using Cm(+). (-), via the server (lines 3-9). Each party m completes Q local iterations, using the compressed embeddings it received in iteration in and its own m-th uncompressed embedding 1m (0e, m: x ). We denote the set of embeddings that party yn uses as:
t = (Co(0)") C, Ch1 xX )).
h.m (6 ")...,, x= )..... Crr.,,,C(((ha (0 X ))}
For each local iteration, each party m updates Om by computing the stochastic partial derivatives Vn F'B ( ( BB")) and applying gradient step with step size ro (lines 13-16).
A key difference here from previous VFL algorithms is that C-VFL shares the server model with all parties in order support multiple local gradient updates with non-linear server model. Also note that the same mini-batch is used for all Q local iterations, thus communication is only required every Q iterations. Therefore, without any compression, the total communication cost is O(R M (B P.. + (6ol)) for R global rounds. Our compression technique replaces P., and |0o| with smaller values based on the compression factor. For cases where embeddings, the batch size, and the server model are large, this reduction can greatly decrease the communication cost.
Privacy. We now discuss privacy-preserving mechanisms for C-VFL. HFL settings, model up- date or gradient information is shared in messages. It has been shown that gradients can leak infor- mation about the raw data (Phong et al., 2018; Geiping et al., 2020). However in C- parties only share embeddings and can only calculate the partial derivatives associated with the server model and their local models. Commonly proposed HFL gradient attacks cannot be performed on C-VFL. Em- beddings may be vulnerable to model inversion attacks (Mahendran & Vedaldi, 2015), which methods by which an attacker can recover raw input to a model using the embedding output and black-box access the model. One can protect against such an attack using homomorphie encryp- tion (Cheng et al., 2019; Hardy et al., 2017) or secure multi-party computation (Gu et al., 2021). An efficient implementation of encryption for embeddings in VFL has been provided in the FATE open-source project (FederatedAA, 2021). Alternatively, if the input to the server model is the sum of party embeddings, then secure aggregation methods (Bonawitz et al., 2016) can be applied.
Note that C-VFL assumes all parties have access to the labels. For low-risk scenarios, such as predicting credit score, labels may not need be private among the parties. In cases where labels are private, one can augment C-VFL to apply the method in Liu et al. (2019) for gradient calculation without the need for sharing labels. Our analysis in Section would still hold in this case, and the additional communication is reduced by the use of message compression.
4 ANALYSIS
In this section, we discuss our analytical approach and present our theoretical results. We first define the compression error associated with (.):
5

---

Under review as a conference paper at ICLR 2022
Definition 1. Compression Error: Let vectors em for =0,.. ....., M, be the compression ervors of Cm (.) on a data sample x²: 2x = Cm (him (0::= x²)) Nm (fm;;")). Let co be the Pm B matrix with xi for all data samples x' mini-batch B as the columns. We denote the expected squared message compression error from party at round to as En = = 1e
Let G¹ ((Vo F y
FM Mi: ")?TT The model O evolves
- 7'"
(3)
We note the reuse of the mini-batch of B for Q iterations in this recursion. This indicates that the stochastic gradients are not unbiased during local iterations fo S S + Q-QQ-QQ1 However, using conditional expectation, we can apply Assumption
the gradient calculated iteration to when there is no compression error. We define & to be the set of embeddings that would be received by party m no compression error were applied:
Φ 100' hi (0f) X )).....
Am (0 m
B'o ",..., has (0 Mi
M5 }}.
(4)
Then, if we take expectation over B conditioned on previous global models Of up to lo:
B FB (n) {0r ) = V (())).
(5)
With the help of (5), prove convergence by bounding the difference between the gradient the start of each global round and those calculated during local iterations (see the proof of Lemma in the appendix for details).
To account for compression error, using the chain rule and Taylor series expansion, we obtain:
Lemma 1. Under Assumptions 4-5, the norm of the difference between the objective functiono value with compressed and uncompressed embeddings is bounded as:
V m ( V.. Fn( 11 H G f=0..
cta
The proof of Lemma is given in the appendix. Using Lemma we can bound the effect of compression error on convergence.
We present main thcoretical results. All proof's provided in the appendix.
Theorem 1. Convergence with fixed step size: Under Assumptions 1-5, if for all iterations and satisfies 17a S 16Q max ma, Lmn' then the average squared gradient over global rounds of Algorithm is bounded by:
1 R-1
2 F(O") E [[F(O")]
Σ
||VF(0"))
4
om
T/T
68Q²
M
Σ m==
Σ tn=0 j=0.jmm
Σ
(7)
R
The first term in (7) is based the difference between the initial model and final model of the algorithm. The second term is the error associated with the variance of the stochastic gradients and the Lipschitz constants L and L.. ss. The third term relates to the average compression error over all iterations. The larger the error introduced by a compressor, the larger the convergence error is. We note that setting 0 0 for all parties and iterations provides an error bound on VFL without compression and is an improvement over the bound in Liu et al. (2019) in terms of Q, M, and B. the number of local
The second and third terms include coefficient relating local iterations. iterations Q increases, the convergence error increases. However, increasing Q also has the effect of reducing the number of communication rounds. Thus, it may be beneficial to have Q > practice. We explore this more in experiments in Section 5. The second and third terms scale with M, the number of parties. However, VFL scenarios typically have a small number of parties (Kairouz et al., 2021), and thus M plays small role in convergence error. We note that when M and Q 1, Theorem I applies to Split Learning (Gupta & Raskar, 2018) when only uploads to the server are compressed.

---

Under review as a conference paper at ICLR 2022
Table 1: Choice of common compressor parameters achieve a convergence rate of O(1/VT). Pm is the size of the m-thh embedding. In scalar quantization, we let there be 29 quantization levels, and let hmax and Amin be respectively the maximum and minimum components in him (0, mm) for all iterations t. parties m, and rmm. We let V be the size of the lattice cell in vector quantization. We let be the number of parameters sent in an embedding after top-k sparsification, and (|]4]² max be the maximum value of [ (0th x 112 for all iterations t, parties and x
Uniform Sculur Quantizer
Luttice Quantization
Top-k Spursification
Parameter choice
Q Toga BPaaaaa Bratt
P. (VT)
V
A Q Pu Bi V
For
UPAVT
Compression error
2 $ BPp Omne - bomn 2 01
E
VBR 24
R(1
A X0AA June
Ol O13)))
12
m m If Iy = + for all global rounds to. for Q and B independent of T,, then + + [I = EE). This indicates that & 0 vT then we can achieve convergence rate of 0 ( Informally, this means that C-VFL can afford compression error and not worsen asymptotic convergence when this condition is satisfied. We discuss how this affects commonly used compressors in practice later in the section.
Remark 1. Let & = A 2 M
We consider diminishing step size in the following theorem.
Theorem 2. Convergence with diminishing step size: Under Assumptions 1-5, if 0 < 770 < satisfies 1750 S
I6Q max L.axx L.m. then the minimum squared gradient over R global rounds of Algorithm I is bounded by:
min
E
|VF
|1] -0
1
+
En
ER-I DM Im= 1
Eto
2 7/0
EtTo s/to
-1m0 1700
If 17'0 and tn sarisfy -===0 1/ 00, _7==00700)2
< oc, and Eio=0 Em= 1/ < oc, then
mink)=0.....
E
|VF(OM)) 0 as R 00.
According to Theorem 2, the product of the step size and the compression error must be summable over all iterations. In the next subsection, we discuss how to choose common compressor parameters to ensure this property is satisified. We also see in Section 5 that good results can be achieved empirically without diminishing the step size or compression error.
Common Compressors. In this section, we show how to choose common compressor parameters to achieve a convergence rate of O( (T) in the context of Theorem I, and guarantee convergence in the context of Theorem 2. We analyze three common compressors: uniform scalar quantizer (Ben- nett, 1948), a 2-dimensional hexagonal lattice quantizer (Zamir& & Feder, 1996), and top-k sparsifi- cation (Lin al., 2018). For uniform scalar quantizer, we let there be 29 quantization levels. For the lattice vector quantizer, we let V be the volume of each lattice cell. For top-k sparsification, we let k be the number of embedding components sent in a message. Table 1, we present the choice of compressor parameters in order to achieve convergence rate of O( /T) in the context of Theorem 1. We show how calculate these bounds in the appendix and provide some implementation details for their use. We can also use Table 1 to choose compressor parameters to ensure convergence in the context of Theorem 2. Let 17t O(2,), where to is the current round. Then setting 7 to in Table provides a choice of compression parameters each iteration to ensure the compression error diminishes at a rate of O ( ), guaranteeing convergence. Diminishing compression error can be achieved by increasing the number of quantization levels, decreasing the volume of each lattice cell, or increasing the number of components sent in messages.
EXPERIMENTS
We present experiments examine the performance of C-VFL in practice. The goal of our exper- iments is to examine the effects different compression techniques have on training, and investigate the accuracy/communictioo trade-off empirically.
Unless otherwise specified, our experimental setup consists of four parties and a server. Most real- world VFL settings include collaboration between few institutions (Kairouz al., 2021), so
7

---

Under review as a conference paper at ICLR 2022
0.5
0.5
0.4
0.3
Accune
Compressin Quantize
pressen Quantze
90
Comppresson Oueet
Compress
Qurnt ze
Qunmmiree
0.1
20
0.
Ryp-
Tip-
Epochs
Communication Cor
Epochs
Commun cation Cont (M4)
(a) MIMIC by epochs
(b) MIMIC by cost
(c) ModelNet by epochs
(d) ModelNet by cost
Figure 2:
C-VFL when compressing to 2 bits per component. We show test Fi Score on MIMIC-III
dataset and test accuracy on ModelNet10 dataset, plotted by epochs and communication cost (MB).
expect the number of parties to be small. We train our system with two datasets: the MIMIC- III dataset (Johnson et al., 2016) and the ModelNet10 dataset (Wu et al., 2015). MIMIC-III is an anonymized hospital patient time series dataset, while ModelNet10 each with 12 different views. For MIMIC-III, the task is binary classification to predict in-hospital mortality. Each party trains on 19 of the 76 features with an LSTM and the server model consists of two fully-connected layers. For ModelNet10, the task is classification of images into 10 object classes. Each party trains on three views with three convolutional layers and the server model consists of a fully-connected layer. We use a fixed step size of 0.01 for the MIMIC-III dataset and 0.001 for the ModelNet dataset. For MIMIC-III, we use a batch size of 1000, and for ModelNet10, we use a batch size of 16. We train on the MIMIC-III dataset for 1000 epochs and the ModelNet10 dataset for 50 epochs, where an epoch consists of all iterations to fully iterate over the dataset. More details on the datasets and training procedure can be found in the appendix.
CAD photos of objects,
We consider the three compressors discussed in Section 4: a uniform scalar quantizer, a 2- dimensional hexagonal lattice quantizer, and top-k sparsification. For both quantizers, the embed- ding values need to be bounded. In the case of MIMIC-III's LSTM, the embedding values are the output of tanh activation function and have bounded range of [-1, 1]. For ModelNet10, the embeddings are the output of a ReLU activation function, and may be unbounded. We scale em- bedding values for 1o the range [0, 1]. We apply subtractive dithering both the scalar quantizer ( (Wannamaker, 1997) and vector quantizer (Shlezinger et al., 2021).
In our experiments, each embedding component a 32-bit float, Let b be the bits per component we compress to. For the scalar quantizer. this means there are 2 quantization levels. For the 2-D vector quantizer, this means there are 2 vectors in the codebook. The volume V of the vector quantizer is a function of the number of codebook vectors. For top-k sparsification, k = Pm b 32 as we are using 32-bit components. We train using C-VFL and consider cases where b = 2, 3, and 4. We compare with a case where b- = 32. This corresponds to standard VFL algorithm without embedding compression, acting as a baseline for accuracy.
In Figure 2, we plot the test F1 -SoCe and test accuracy for MIMIC-III and ModelNet10, respec- tively, when training with b = 2. We use Fi-Score for MIMIC-III as the in-hospital mortality prediction task is highly skewed; most people in the dataset did not die in the hospital. The solid line in each plot represents the average loss over five runs, while the shaded regions represent the standard deviation. In Figures 2a and 2c, we plot by the number of training epochs. We can see in all cases, although convergence can be a bit slower, training with compressed embeddings still reaches similar accuracy to no compression. In Figures 2b and 2d, we plot by the communication cost in MB. The cost of communication includes both the upload of (compressed) embeddings to the server and download of embeddings and server model to all parties. We can see that by compressing em- beddings, we can reach higher accuracy with significantly less communication cost. In both datasets, the compressors reach similar accuracy to each other, though top-k sparsification performs slightly worse than the others on MIMIC-III III, while scalar quantization performs worse on ModelNet10.
In Table 2, we show the maximum test accuracy reached during training and the communication cost to reach target accuracy for both datasets. We show results for all three compressors with b = 2, 3, and 4 bits per component, as well as the baseline of = 32. For the MIMIC-III dataset, we show the maximum test Ficocere reached and the total communication cost of reaching an Fi-Score of 0.4. The maximum Fi Ficoe for each case is within a standard deviation of each other. However, the cost to reach target score is much smaller as the value of b decreases for all compressors. We can see that when = 2, we can achieve over 90% communication cost reduction over no compression to reach target F -score.
For the ModelNet10 dataset, Table 2 shows the maximum test accuracy reached and the total com- munication cost of reaching an accuracy of 75%. We can similar results as for the MIMIC-III
8

---

Under review as a conference paper at ICLR 2022
Table 2: Maximum F1-Score and test accuracy reached during training, and communication cost to reach a target accuracy. For MIMIC-III, the target test Fi-Score is 0.4, For ModelNet10, the target test accuracy is 75%. In these experiments, Q 10 and M
4.
Compressor
MIMIC-III dataset
ModelNet10 dataset
Max Fj Score Reached
Cost (MB)
Accuracy Reached
Cost (MB)
Tagget 0.4
Target 73%
Nome 32
0.448 0.010
3830.0
558.2
83.81% +: 0.54%
9715.9 1: 2819.3
Sealar 2
0.441 0.018
233.1
28.7
79.63% +: 1.74%
374.7 48.3
Vector 6 2
0,451
0.021
236.1
17.9 309.8
83.92% 1 0.66%
620.2 :: 194.2
Top-k 6
0.431 + 0.016
93.6
81.98% + 0.43%
594.3 +: 259.7
Scalar 3
0.446 1: 0.011
343.1
18.8
79.47% d: 1.58%
581.4 :: 106.1
Vector 3
0.455 0.020
330.5
10.6
83. 85% + 0.65%
930.2 + 264.3
Top-k b =
0.435 = 0.030
470.7 + 116.8
82.64% + 0.41%
833.3 = 355.2
Scalar 4
0.451 + 0.020
456.0
87.8
79.41% + 2.23%
749.4 + 96.7
Vector 1 0,446 0.017
446.5
21.3
83% + 0.62%
1240.3 352.4
Top-k b
0.453 + 0.014
519.1 + 150.4
17% + 0.74%
1137.0 + 450.5
Table 3: MIMIC-III time in seconds to reach a target F Score for different local iterations Q and communication latency te with vector quantization and = 3.
b-32
b-32
20
20
Time Reach Target -S-ocore
1003
2003
3002
10003
20320
Q =
Q 10
Q= 25
(a) Parties M
(b) Parties M -12
150.75
470.86 235.35
10
1262.78 + 274.10
512.82 +: 256.32
461.17
53.29
Figure 3: Communication cost of training on ModelNet10 with vector quantization.
50
3788.32
1 822.30
699.30
349.53
532.12
61.49
200
13259.14 2878.04
1398.60 699.08
798.19
dataset with the exception of scalar quantization. Scalar quantization achieves the target accuracy with much lower communication cost, but the maximum test accuracy is significantly lower than the other cases. This can be due to scalar quantization always quantizing embedding components the same values when nearing convergence. Vector quantization benefits from considering components jointly, and thus can have better reconstruction quality than scalar quantization (Woods, 2006).
In Table 3, we consider the communication/compaaaii the number of local iterations affects the time to reach a target Fi-score in the MIMIC-II dataset. We train C-VFL with vector quantization b = 3 and set the local iterations Q to 1, 10, and 25. We simulate a scenario where computation time for training a mini-batch of data at each party takes 10 ms, and communication of embeddings takes total of 1, 10, 50, and 200 ms roundtrip. These different communication latencies correspond to the distance between the parties and the server: within the same cluster, on the same local network, within the same region, and across the globe. According to Theorem 1, increasing the number of local iterations Q increases convergence error. However, the target test accuracy reached within less time when Q increases. The improvement over Q = 1 local iterations increases as the communication latency increases. In systems where communication latency high, it may be beneficial increase the number of local iterations. The choice of Q will depend on the accuracy requirements of the given prediction task and the time constraints on the prediction problem.
tradeoff of local iterations. We show how
Finally, in Figure 3, we plot the test accuracy of ModelNet against the communication cost when using vector quantization with = 2, 3, 4, and 32. We include plots for 4 and 12 parties. In the 12 party setup, each party stores parties changes the global model structure θ as well. We can see in both cases that smaller values of b reach higher test accuracies at lower communication cost. The total communication cost is larger with 12 parties, but the impact of increasing compression is similar for both M = 4 and M = 12.
view for each CAD model. We note that changing the number of
CONCLUSION
We proposed C-VFL, a distributed communication-effiiee. algorithm for training model over vertically partitioned data. We proved convergence of the algorithm to fixed point at a rate of O (())). and we showed experimentally that communication could be reduced by over 90% without a significant decrease in accuracy. For future work, we seek to relax our bounded gradient assumption and explore the effect of adaptive compressors.

---

Under review as a conference paper at ICLR 2022
REFERENCES
W. R. Bennett. Spectra of quantized signals. Bell System Technical Journal, 1948.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Arizzadenesheli, and Animashree Anandkumar. SIGNSGD: compressed optimisation for non-convex problems. In Proceedings of the 35th In- ternational Conference on Machine Learning, 2018.
Kallista A. Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for fed- erated learning on user-held data. arXiv, 2016.
Kallista A. Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzoechi, Brendan McMahan, Ti- Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In Proceedings of Machine Learning and Systems, 2019.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 2018.
Dongchul Cha, MinDong Sung, and Yu-Rang Park. Implementing vertical federated learning using autoencoders: Practical application, generalizability, and utility study. JMIR Medical Informatics, 2021.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. VAFL: method of vertical asynchronous federated learning, arXiv, 2020.
Kewei Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, and Qiang Yang. Secureboost: A lossless federated learning framework. arXiv, 2019.
Anirban Das and Stacy Patterson. Multi-tier federated learning for vertically partitioned data. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2021.
FederatedAI. Fate. https//giiiabbcmm///eeeetttt/ttt 2021.
Siwei Feng and Han Yu. Multi multi-pprticipant multi-class vertical federated learning. arXiv, 2020.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients how easy is it to break privacy in federated learning? In Advances in Neural Information Processing Systems, 2020.
Bin Gu, An Xu, Zhouyuan Huo, Cheng Deng, and Heng Huang. vertical federated learning algorithms for multiparty collaborative learning. IEEE Transactions on Neurul Networks and Learning Systems, 2021.
asynchronous
Yue Gu, Xinyu Lyu, Weijia Sun, Weitian Li, Shuhong Chen, Xinyu Li, and Ivan Marsic. Mutual correlation attentive factors in dyadic fusion networks for speech emotion recognition. In Pro- ceedings of the 27th ACM International Conference on Multimedia, 2019.
Otkrist Gupta and Ramesh Raskar, Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications, 2018.
Wei Han, Hui Chen, and Soujanya Poria. Improving multimodal fusion with hierarchical mutual in- formation maximization for multimodal sentiment analysis. Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing, 2021.
Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, Guillaume Smith, and Brian Thore. Private federated learning vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv, 2017.
Yaochen Hu, Di Niu, Jianming Yang, and Shengping Zhou. FDML: A collaborative machine learning framework for distributed features. In 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2019.
10

---

Under review as a conference paper at ICLR 2022
Alistair E.W. Johnson, Tom J. Pollard, Lu Shen, Li-wei H. Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G. Mark. Mimic-iii, freely accessible critical care database. Nature, 2016.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Gar- rett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgüir, Rasmus Pagh. Hang Qi. Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 2021.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning. 2019.
Will Koehrsen. Book recommendation system. http://siitbbbooo/llllllcceeeeet secrrccboonmaerrcccookkkoooooo
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proceedings of Machine Learning and Systems, 2020.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chame Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communication Surveys and Tutorials, 2020.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. In 8th International Conference Learning Representations, 2020.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reduc- ing the communication bandwidth for distributed training. In 6th International Conference Learning Representations, 2018
Lumin Liu, Jun Zhang, Shenghui Song, and Khaled B. Letaief. Client-edge-cloud hierarchical federated learning. In IEEE International Conference on Communications, 2020.
Yang Liu, Yan Kang, Xinwei Zhang, Liping Li, Yong Cheng, Tianjian Chen, Mingyi Hong, and Qiang Yang. communication efficient vertical federated learning framework. NeurlPS Work- shop on Federated Learning for Data Privacy and Confidentiality, 2019.
Aravindh Mahendran and Andrea Vedaldi. Understanding deep image representations by inverting them. In IEEE Conference on Computer Vision and Pattern Recognition, 2015.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agúera y Arcas. Communication-efficieee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence, 2017.
Philipp Moritz, Robert Nishihara, Ion Stoica, and Michael I. Jordan. Sparknet: Training deep net- works in spark. 2016.
Lam M. Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. SGD and hogwild! convergence without the bounded gradients assumption. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Weizhi Nie, Qi Liang, Yixin Wang, Xing Wei, and Yuting Su. MMFN: multimodal information
fusion networks for 3d model classification and retrieval. ACM Transactions on Multimedia Com- puting, Communications, and Applications, 2021.

---

Under review as a conference paper at ICLR 2022
Le Trieu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy- preserving deep learning via additively homomorphic encryption. IEEE Transactions on Infor- mation Forensics and Security, 2018.
Peter Richtárik and Martin Takáe. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 2016.
Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R. Roth, Shadi Albarqouni, Spyri- don Bakas, Mathieu N. Galtier, Bennett A. Landman, Klaus Maier-Hein, Sébastien Ourselin, Micah Sheller, Ronald M. Summers, Andrew Trask, Daguang Xu, Maximilian Baust, and M. Jorge Cardoso. Digital Medicine, 2020.
Daniele Romanini, Adam James Hall, Pavlos Papadopoulos, Tom Titcombe, Abbas Ismail, Tudor Cebere, Robert Sandmann, Robin Roehm, and Michael A. Hoeh. Pyvertical: A vertical feder- ated learning framework for multi-headed splitnn. ICLR Workshop on Distributed and Private Machine Learning, 2021.
Shaohuai Shi, Kaiyong Zhao, Qiang Wang, Zhenheng Tang, and Xiaowen Chu. A convergence analysis of distributed SGD with communication-efinnn efficiinf gradient sparsification. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019.
Nir Shlezinger, Mingzhe Chen, Yonina C. Eldar, Vincent Poor, and Shuguang Cui. Uveqfed: Universal vector quantization for federated learning. IEEE Transactions Signal Processing, 2021.
Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, 2018
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEFE transactions automatic control, 1986.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 2019.
Robert Alexander Wannamaker. The Theory of Dithered Quantization. PhD thesis, 1997.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, 2017.
John W Woods. Multidimenssonaa signal, image, and video processing and coding. Elsevier, 2006.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Conference on Computer Vision and Pattern Recognition, 2015.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology. 2019.
Ram Zamir and Meir Feder. On lattice quantization noise. IEEE Transactions on Information Theory, 1996.
Xinwei Zhang, Wotao Yin, Mingyi Hong, and Tianyi Chen. Hybrid federated learning: Algorithms and implementation. arXiv, 2020.
12

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
A. PROOFS OF THEOREMS AND
In this section, we provide the proofs for Theorems 1 and 2.
A.1.1 ADDITIONAL NOTATION
Before starting the proofs, we define some additional notation be used throughout. At each iteration t, each party trains with the embeddings & This is equivalent to the party training directly with the models tt and 0 for all * m, where to is the last communication iteration when party m received the embeddings. We define:
{
0
m m-j
mm.
(A.1)
otherwise
to represent party m's view party j's model at iteration t. We define the column vector r = o"" :.... (? to be party m's view of the global model at iteration t.
We introduce some notation to help with bounding the error introduced by compression. We define FT to be the stochastic loss with compression error for a randomly selected mini-batch calculated by party m iteration d:
XB ),...... h0 (T m)) = FB (06' + <i hy ) + .e.....,,,, Am (0
XBO
to
EM
(A.2)
Recall the recursion over the global model O:
0'
(A.3)
We can equivalently define G' as follows:
G² = (W,
(A.4)
Note that the compression error in F(.) is applied to the embeddings, and not the model parameters. Thus, F.)) and f()) are different functions. In several parts of the proof, we need to bound the compression error in V, FT.....
For our analysis, we redefine the set of embeddings for a mini-batee batch of size B from party m as matrix:
B hm (9m: XB is matrix with dimensions Pm x B where each column is the embedding from party m for a single sample in the mini-batch.
Nmm (fm: XB
Nin (fm jm .mm)) ).... hm (0m:
}]
(A.5)
Let P = Em Pm be the sum of the sizes of all embeddings. We redefine the set of embeddings used by a party m calculate its gradient without compression error matrix:
th m
[000) (hr (0 x)""))" ".. (l mi
BB m ))²
(har
B M )
(A.6)
di is matrix with dimensions P x B where each column is the concatenation of embeddings for all parties for a single sample in the mini-batch.
Recall the set of compression error vectors for mini-batch B of size B from party is the matrix:
to
B
B
(A.7)
<oo is a matrix of dimensions P., x B where each column the compression error from party m for single sample in the mini-batch.
13

---

Under review as a conference paper at ICLR 2022
We define the compression enror each embedding used in party m'ss gradient calculation itera- tion t:
E (c0
(=00)T ..... (ch-1) (cn-1)) ......
(A.8)
En is matrix with dimensions P x B where each column is the concatenation of compression error on embeddings for all parties for a single sample in the mini-batch.
With some abuse of notation, we define:
VmFi ( + Eth) V Vm-BilB (
(A.9)
Note that we can apply the chain rule V V FBFF(LT
mm BT
Ve.. hm (6%) Vm ( + Emi)
(A.10)
With this expansion, the point $
apply Taylor series expansion (0 FB( + E around
V (0.) ( m
E V (0mm FB( + V (o... (B.
m E +...
(A.11)
We let the infinite sum all terms this Taylor series from the second partial derivatives and up be denoted as R
E R ( + Emn)= = ( FB( EE +...
(A.12)
Note that all compression error is in R (T. + E22). Presented in Section A.1.2, the proof of Lemma 1' shows how we can bound Ro ( Ets), bounding the compression error in Vn FL
Let E = Egrl 10 Note that by Assumption 2, E G VF()") as when there no compression error in the gradients G, they are equal to the full-batch gradient in expectation when conditioned on the model parameters up to the iteration to. However, this not true for iterations to + 1 S S to + Q - 1, the error introduced by stochastic gradients calculated during local iterations in Lemma 2.
reuse the mini-batch B in these local iterations. We upper bound
A.1.2 SUPPORTING LEMMAS
Next, we provide supporting lemmas and their proofs.
We restate Lemma here:
Lemma 1. Under Assumptions 4-5, the norm of the difference between the objective function value with and without error is bounded by:
M
E
V n. Fn
Fm
V Fn( m
H
G2
Σ @=0,f$m
(A.13)
To prove Lemma we first prove the following lemma:
Lemma 1'. Under Assumptions 4-5, the squared norm of the partial derivatives for party m. embedding multiplied by the Taylor series terms R (Φ) + Fta)) is bounded by:
|| p.. Imm (0 RBg (Φ² + Fla) < H2 G2
Fto I|
(A.14)
Proof.
| Imm (0', R (1" + E1ai|| < Ve Am (0' (0m)) R (+ 11
(A.15)
H2 Ve.,, Iim (0 (0th)) ||? E
(A.16)
where (A.16) follows from Assumption 4 and the following property of the Taylor series approxi- mation error:
| (6' Ela
S H E
(A.17)
14

---

Under review as a conference paper at ICLR 2022
Applying Assumption 5, we have:
V nm (0 Ro + E/1)
H G
E 2
(A.18)
F
We now prove Lemma 1.
Proof. Recall that:
V m FB
V FB( Enn
(A.19)
Vnn hum (0 V hm (Pom (0 ; FB( +.
(A.20)
Next we apply Taylor series expansion as in (A.11):
V FT(T = Vo., Nm (8 (V (hom (f.) FB( + RØ ( + Et1)
(A.21)
In P m + V hm (0, 1R" (Ø) + E
(A.22)
Rearranging and applying expectation and the squared 2-norm, we can bound further:
E
V (T - V. (T m))
|| = E V om
(0
R5 (
+ E
(A.23)
H2 G2 m
to 2
(A.24)
m
11 G2 m
E 11
(A.25)
H2 G
(A.26)
1
where (A.24) follows from Lemma 1', (A.25) follows from the definition of E and (A.26) follows from Definition 1.
Lemma 2. If T7 < pected squared norm difference of gradients T and G for iterations to to to as follows:
4Q mama Tr... then under Assumptions 1-5 we can bound the conditional ex-
t
E ||o' -''00 0%01²
Σ L
V m
F(
M
L o
+ 11Q
B
m==
+ 64Q3 Σ
2 G2 E
(A.27)
15

---

Under review as a conference paper at ICLR 2022
Proof.
M
2 = Σ
( - Vn Fi
(A.28)
m=0
Σ m=0
E
V m
PB (L m) Fa( V ) V Fi
(A.29)
V (T)) -m |
(1 m)
E
M
1+
E V (T V (T
(A.30)
0
M
2 + +))
Σ
fo
V ( V ('a /
m=0
M
+ n)
V Nmm (0 (2) E V Am. hmm (0 22 (1 1-
E 10 1)
m=0
M
(1+ 1
Eaa
V m PB (Tmm)) V. (n(
(A.31)
n
M
2 + n)
Σ
Vm (T( |/ -Vm
m=0
M
+8(1+m)
Σ
G2 m
m=0
M
11+
Σ
E'
|
-0---,, Fm
(A.32)
M==
where (A.30) follows from the fact that (X + r)2 < (1 x + (1 + ))r² for some positive
and (A.32) follows from Lemma 1'.
Applying Assumption to the first term in (A.30) we have:
M
E ||o' - 6%0
<2 n)
2 1 mm
r2t m
m==
M
+
1
Elo
| (T
V. FB (T
m==
+8 n)
H2 G2
E
(A.33)
2( + n
Σ
I f m
M
+2
1
E
V
V.n Fis((tt) m
m==
+ (1 n))
H2 G2
E
(A.34)
m=0
where (A.34) follows from the update rule T r6-1 17a0 V m Fr (T
16

---

Under review as a conference paper at ICLR 2022
Bounding further:
G¹ G Giul1]
M $ 2(11/0022 (1 n) Σ
| \ FmF + Vn (T
L E
m=U
+1+ 1+
M
|| F - Fm
| [2]
E
m=0
+ 8 n)
Σ
H G
(A.35)
m==
S 4(17 (1 n2)
M
L Elo
|mfie(Tm
v FB FB 27
M
+ +4(7/003 (1 + n
L E2 Ebo
[|
m=0
+ +(+
M
F (T) 22
E
V n
m==
+8 + n)
H C F
(A.36)
===
4(1 4(170)2 (1+ n2) L + h1) 10 -
27
Σ
-
Fu
M
+ +4 (1 + n)
Σ m=0
L2 E2 t
M
+8 + n)
Σ
H2 G2 m
E
(A.37)
1==0
Let Q. We simplify (A.37) further:
G Go
27
M
L + (1+ E
27
<
4(1700) Q) 12
- Fr.Fo(1
m=
M
+ +2 Q) Σ Ed [
m==0
+8 Q) Σ
H 2
1
2
(A.38)
m==
17

---

Under review as a conference paper at ICLR 2022
Let 17/0 $ 4Q max L.
1
We bound (A.38) as follows:
B
c
(a+ 4Q2
+ (1+11) ())
Σ
M
E
|| m
(T
vn Fir (T m.
m=0 0
+ +4 (1 + Q) Σ
1 E
|
m=0
+8(1 Q) Σ
H G m
11
(A.39)
m2
+ (1+
M
< 2Q
E
V Pn(Tt) - v. (Ta
M
+ +4(7%0) (1 + Q) Σ
E 2
(T
m=0
+8(1 Q)
H G
|
(A.40)
(1+
M
Σ E
(T
FB
Vm
(T
m
M
+ +4(1/033 (1 + Q)
Σ
E 2
||vm/(((T<)))
m=0
+ 8(1 + Q) Σ
H E
(A.41)
===00
We define the following notation for simplicity:
M A' = t
V FB(T))) - V (T 27
(A.42)
m==
M
B. = 4(7 (1 + Q)
Σ
L B
(A.43)
m==
M Σ
B1 = 88 + Q)
H 2
E 2
(A.44)
m=U
C= C=(11 1+ 2
(A.45)
Note that we have shown that A' S CA'-1 + B, + B,. Therefore:
- < CAA' +
(A.46)
1 < A² +CB + B1) + (Bo + B1)
(A.47)
- < 3 + C B1) C(Bo + B1) (Bo + B1)
(A.48)
(A.49)
1-1--2
A S Ct A0 + +(B + B1)
Σ
(A.50)
k=
(1-
= - A0 + (Bo + Bi)
(A.51)
C-1
18

---

Under review as a conference paper at ICLR 2022
We bound the first term in (A.51) by applying Lemma 1:
M
4
V Fi(((t()))) - V Cm//B(1 (1
(A.52)
m==
H G Em
(A.53)
m==
Summing over the set of local iterations to to....,... 20
where to = + Q --1- 1:
#
C ca
A
C 10-to-1
(A.54)
t=
t=te
A 0
(A.55)
C-1
(1+ 2
9
④
-1
(A.56)
1+ Q
(1+ 2 Q
QA4
(A.57)
2
S SQ140 e2-1
(A.58)
4Q
(A.59)
M
S 4Q
Σ H G
E 12
(A.60)
It is left to bound the second term in (A.51) over the set of local iterations to....,, + Q - 1.
Ot-
Ot-
Bo + B₁)
S
Σ Bo + Bi)
(A.61)
C-1
C
(Bo + BB)
Σ
ch- 2)
(A.62)
C-1
1=
(Bo + BB)
0 -
C-1 Q
(A.63)
C-1
[ [+ 3 -1
(Bo + B1)
(A.64)
(1+ ()) -1
1+ 2
Q
2
Q(Bo + Bi)
Q
(A.65)
2
Q 1
(B + Bi)
1
+
3/
(A.66)
QB B1)
(62 (62-1 1 -11 11
<
(A.67)
< 2Q² + B1)
(A.68)
(A.69)
19

---

Under review as a conference paper at ICLR 2022
Plugging the values for Bo and B1:
0
M
(Bo + Bi)
(1 Q)
Σ 10
C -11
t=
m=0
+100
Σ
H1 G
|
(A.70)
Applying Assumption and adding in the first term in (A.51):
M
A (1
Σ
I
V
((
to
m=
+ +8Q
Σ
1 Fm
M
+1(4Q((1+ Q)
H G2 m2
(A.71)
m
M
(160 Σ Lm
V \m
m=0
+ +10 )
m B
M==
+ +64Q3 Σ
H G2
E 2
(A.72)
F
A.1.3 PROOF OF THEOREMS AND 2
Let to to + Q 1. By Assumption
- ((6%))-F(00)) < (VF(8)),, 0 0²)) -60) +
0 - 0
(A.73)
2
#
+
VF(O'))
Σ
1
+
L
n
to !
(A.74)
2
t=to
t
< - n
(VF(O%), )')))
LQ
(n
00 2
6''2²
(A.75)
2
t=to
t=
where (A.75) follows from fact that (IN xn, < N > 22
20

---

Under review as a conference paper at ICLR 2022
We bound further:
%
16
F(O%)) F(O s Σn 1/ (VF(O c' -Go)
Σn1 1//0 (VP(O Go))
t=to
LQ
(1//)2 G G + G
+
(A.76)
2
t=
S Σ 11 (VF(Ot)), G² -6%) Σ 1/0 (VP(O") G'o)
t=to
+ QQ Σ (17 (17003 G' Giull" + IQ Σ
(1/0)3 G
(A.77)
t=
t=
1
Σ 1
( G -G') Σ 1 10 (VF("'))
+ QQ
(17002 G' Glul?
+ IQ
Σ
(170) G |
(A.78)
1=10
1=
1 1d
Σ
10
2
5
G - G6// || - Σ n0 (VF(G*))
+
n
2 t=to
t=
LQ 1
+ LQ
>
G 2
G. ||
Σ (n)0) 1
(A.79)
where (A.79) follows from the fact that A B = A + 1 (AA-A(A))
- ()2
We apply the expectation E to both sides of (A.79):
#/²
taa [ - -(0%) < - Σ oo
|
Σ
(1 + 10
||'' G |
+ L4 Σ
n7 2 ||
(A.80)
Σ 10 /
M
+
n/ (1+ LQ
| G 2
+ LQ
o
(17
2 1=t
B
m=0
1=to
(A.81)
Q 2
o0 - ) |F
=
1
Σ
n (1 + LQn1")1B'
||0² - Go
- | ||
+ 17
Σ
om
2
B
1=
m=0
(A.82)
21

---

Under review as a conference paper at ICLR 2022
where (A.80) follows from applying Assumption 2 and noting that E [G'o] VF(O')), and (A.82) follows from Assumption 3. Applying Lemma 2 to (A.82):
E [[
=( --9 -1 - |F
M
+ +882(170)(11 + IQQ11)
Σ
T
V,, 2
m==
M
om B
+ +8Q'(110)00 + 1Q
L
m m00
M
+ +320%//00 (1 + LQn
Σ
H Gm
E 12
m=0
om
+ 0 2 Σ
(A.83)
B
m=0
Q M
Σ
--1/'//00000 - 3
16Q 1 [n (1n))))))))1)))))))))))) [1)
2 m==
M
-
+ +(10211/0)2 + -
Σ
B
m=0
M
+320" + LQn"
G 1 2
(A.84)
m=0
Let 17 < 16Q maxx),,axxx m.max L.
Then we bound (A.84) further:
EN [((tt)] - -(())) S - Σ (1
1622
1
V 2|
16
16
M
2
+ (LQ2(110)2 + 22 (n= + 8Q"
Σ
B
M Σ m=0
+ +16Q"n/00 + (1+
(A.85)
S -66 70 |F
2 Σ
M
+ +LL08(7/0) + SQ" (,
B
m=0
M Σ
+ 13203//0011 LQn"')
H 1
(A.86)
m=0
22

---

Under review as a conference paper at ICLR 2022
After some rearranging of terms:
2 (
- -Ea [(OOT)]
n/ |/F v
Q
M
+ +2((Q(170)) + 8Q" (m (7 + (7))))
Σ
om
B
m=0
M
+ +6103//001 + TQQ1"O)
Σ m=0
H² G
(A.87)
Summing over all communication rounds to 0, .,..... R and taking total expectation:
R-1
[F((0)) - [F
Σ E
||||
Q
R-1
M
+ 2
+ ( (1700)3 + 8Q (7))
Σ
B
m=U
M
+ 6440 + LQn ) Σ
G 1
(A.88)
m
m=0
2 [F((O") - E [F(O*)]]
QR
2 R-1
(1/1)3 (Q 8Q (8
(QL()"²)²
Σ
B
0
R-1
M
+ +4Q
Σ
1 (1 + LQn
Σ
H² G E m m
E
(A.89)
F
Ag 0
m=
Note that:
M Σ
M Σ
H E
H G2 Σ E ||:3 1|=]
(A.90)
m=0
m==0
J&
M
Σ
H 2
Σ Ehe
(A.91)
m
m=0
jFm
where (A.91) follows from Definition 1. Plugging this into (A.89)
R-1
2 [F((9)) - E [F(
Σ
E
[|
<
QR
4==
R-1
M
o²
+ 2
Σ
8QQ2L + 8Q" LL
Σ
B
10=0
m=0
R-1
M
+ +64Q2
1 (1 + LQ
Σ Σ cta
H2 G2
(A.92)
m
m
0==
m==
fmm
23

---

Under review as a conference paper at ICLR 2022
Suppose that 17/0 17 for all communication rounds to. rounds, we have:
Then, averaging over R communication
1
R-1
E
||
2 2 - -E [F(O(")]
+2
Σ
M
+
o B
R
Q
to
0
0
64Q²
R-1
M Σ
LQn)
H
G m
Σ 8
Ege.
(A.93)
R
m
10=0
m==
jtm
2 [F(09)
E [F(OT)]]
M Σ
0 QLn
QRn
m=U
68Q2
R-1 M
ΣΣ
H
H
Gm Σ
(A.94)
R
m==0==0
jp
where (A.94) follows from our assumption that 17"0 proof of Theorem 1.
I
This completes the 16Q max maxx Lm
We continue our analysis to prove Theorem 2. Starting from (A.92), we bound the left-hand hand side with the minimum over all iterations:
2 (F((0)) - Bdy [][OT]]]
JE [|V
min
fo 1o=
Q R-1 1/t0
R- (1)
2 Rt-1
210=0 (175033
200=0 (1)
R-
M
+ QL
-8Q2L2 L2
+ 8Q3 LL?
Σ
En=0 1pta
E 1/t0
m
Σ
-0o=0 1//0
B
m=0
M
260=0 1700
Σjsm
Ej
M
21o=0 10)
Σjjn Ej
+ 64Q²
Σ
H G
+ 64LQ*
Σ
H² G
10==0 1//0
Σ6=00 17'0
m=0
m=0
(A.95)
As R + 0o, if Σ 21==0 1/a0 = 0c. ( < oo, and Ei=bn Ejjm En <
co, then
= R-1 E
VF(( 0. This completes the proof of Theorem
A.2 COMMON COMPRESSORS
In this section, we calculate the compression error and parameter bounds for uniform scalar quanti- zation, lattice vector quantization and top-k sparsification, as well as discuss implementation details of these compressors in C-V
We first consider a uniform scalar quantizer (Bennett, 1948) with a set of 2 quantization levels, where is the number of bits to represent compressed values. We define the range of values that quantize to the same quantization level as the quantization bin. In C-VFL,, a scalar quan- tizer quantizes each individual component of embeddings. The error in each embedding of batch
in scalar quantization is < Pm A Pm,. [hmes [lhmes-husi'' 2 where A the size of a quantiza- 12 tion bin, Pm the size of the m-th embedding, hmaz and hmin are respectively the maximum and minimum value fmm ; can be for all iterations t, parties m, and x We note that if hmaz or hmin are unbounded, then the error is unbounded as well. By Theorem 1, we know that Rt Eb=0 Em=o Ehe = O ( to obtain a convergence rate of O ) If we use the same g for all parties and iterations, we can solve for q to find that the value q must be lower bounded by O(loog (Pm
12
1
2 VT)) to reach a convergence rate of O (())). For diminishing compression error, required by Theorem 2, we let T to in this bound, indicating that q, the number of quantization bins, must increase as training continues.
A vector quantizer creates set of d-dimensional vectors called codebook (Zamir & Feder, 1996). A vector is quantized by dividing the components into sub-vectors of size d, then quantizing each sub-vector to the nearest codebook vector in Fuclidean distance. A cell in vector quantization is
24

---

Under review as a conference paper at ICLR 2022
defined as all points in d-space that quantizes to single codeword. The volume of these cells are de- termined by how closely packed codewords are. We consider the commonly applied 2-dimensional hexagonal lattice quantizer (Shlezinger et al., 2021). In C-VFL, each embedding is divided into sub-vectors size two, scaled to the unit square, then quantized to the nearest vector by Euclidean V. where V is the volume of a distance in the codebook. The error in this vector quantizer I 24 lattice cell. The more bits available for quantization, the smaller the volume of the cells, the smaller the compression error. We can calculate an upper bound on based on Theorem 1: = O( P., /T If diminishing compression error is required, we can set T to in this bound, indicating that V must decrease at a rate of O ( vt. ). As the number of iterations increases, the smaller must be, and thus the more bits that must be communicated.
In top-k sparsification (Lin al., 2018), when used distributed SGD algorithms, the k largest magnitude components of the gradient are sent while the rest are set to zero. In the case of embed- dings in C-VFL, a large element may be as important as an input to the server model as small one. We can instead select the k embedding elements to send with the largest magnitude partial derivatives Ve.. hm (0"). Since a party m cannot calculate V hm (m, until all parties send their embeddings, party
use the embedding gradient calculated in the previous iteration, Ve.. (0. (O==,) This an intuitive method, as we assume our gradients are Lipschitz continuous, and thus do not change too rapidly. The error of sparsification is S (1 P.. ((1))) ) where ([1All2) (mar is the maximum value of Am (6 z )l( for all iterations t, parties m, and o Note that if [[lb]]])mar unbounded, then the error unbounded. We can calculate a lower bound on P'm ( vT). Note that the larger ([]AI|?)mar> the larger i must be. More com- ponents must be sent if embedding magnitude is large in order to achieve convergence rate of O ( When considering a diminishing compression error, we set T = to. showing that & must increase over the course of training.
k: h 12(m
A.3 EXPERIMENTAL DETAILS
For our experiments, we used an internal cluster of 40 compute nodes rumning CentOS 7 each with 2x 20-core 2.5 GHz Intel Xeon Gold 6248 CPUs, 8x NVIDIA Tesla V100 GPUs with 32 GB HBM, and 768 GB of RAM.
A.3.1 MIMIC-III
The MIMIC-III dataset can be found at: phmniccpyysionet.rrg The dataset consists of time-series data from ~00,000 intensive care unit admissions. The data includes many features about each patient, such as demographic, vital signs, medications, and more. All the data is anonymized. In order gain access to the dataset, one must take the short online course provided on their website.
Our code for training with the MIMIC-III dataset can be found in in the folder titled "mimic3". This is an extension of the MIMIC-III benchmarks repo found at: gathub.com/ Bettuu...oo//yceaaaWiiimmm YerevaN//mmmicc1) benchmarks The original code preprocesses the MIMIC-III dataset and provides starter code for training LSTMs using centralized SGD. Our code has updated their existing code to TensorFlow 2. which
The new file of interest in our code base is "mimic3modelsin.nne hoopitallmorttaliiyt. runs C-VFL. Both our code base and the original are under the MIT License. More details on installation, dependencies, and running our experiments can be found in "README.md". Each experiment took approximately six hours to run on a node in our cluster.
The benchmarking preprocessing code splits the data up into different prediction cases. Our exper- iments train models to predict for in-hospital mortality. For in-hospital mortality, there are 14,681 training samples, and 3,236 test samples. In experiments, we use step size of 0.01, as is standard for training an LSTT on the MIMIC-III dataset.
A.3.2 MODELNET10
Details on the ModelNet10 dataset can be found at: moodelnee.es.prmmetooocco specific link downloaded the dataset from is the following Google Drive link: https://drvv.ggo Wan.ll//////AAARRRaEEEEEEEEEEEE
The
The dataset consists of 3ID CAD models of different common objects in the world. For each CAD model, there 12 views
25

---

Under review as a conference paper at ICLR 2022
from different angles saved as PNG files. We only trained our models the following 10 classes: bathtub, bed, chair, desk, dresser, monitor, hight_stand, sofa, table, toilet. We used a subset of the data with 1,008 training samples and 918 test samples. In our experiments, use step size of 0.001, as is standard for training a CNN on the ModelNet10 dataset.
Our code for learning the ModelNet10 dataset is in the folder "MVCNN Pytorch" and is an extension of the MVCNN-PyTorch repo: interest in our code base is "quant.py" which runs C-VFL. Both our code base and the original under the MIT License. Details on how to run our experiments can be found in the "README.md". Each experiment took approximately six hours run on node in our cluster.
The file of
A.4 ADDITIONAL EXPERIMENTS
In this section we provide some additional experiments to test the scalability of C-VFL for a larger number of parties and larger datasets.
First, we run C-VFL using the same parameters as described in Section now with 48 parties and a server with the ModelNet10 dataset. Each 3D CAD model in the ModelNet10 dataset has 12 views, so we assign every four parties the same view, and have each store different quadrant of the image.
60-
60
Accuracy
Accuracy
Accuracy
40
20
Vector Quamroo
20
Quarttze
20
Top-c
600
Epochs
Communication Cost (GB)
Communication Cost (GB)
(a) Plotted by epochs
(b) Plotted by cost
(c) Vector quantization
Figure A.1: Test accuracy on ModelNet10 dataset with the number of parties M 48. In the first two plots, the compressors have b = 2, where b is the number of bits used to represent embedding components. In the third plot, 32 indicates there no compression. The results show little variation between compressors and compression, leading to large benefit in communication cost versus test accuracy.
In Figure A.I, we plot the test accuracy for the ModelNet10 dataset. The test accuracy overall lower than when running with 4 and 12 parties. This is expected, as each party has less information individually, making the prediction task more difficult. Figure A. la shows the test accuracy plotted by epochs. There is very little variation between compressors and no compression here. This leads very large benefit for compression when plotting by communication cost, seen in Figure A. In Figure Ac we plot the test accuracy of C-VFL using vector quantization for different values of the number of bits to represent compressed values. Similar to previous results, lower tends to improve test accuracy reached with the same amount of communication cost. We can also that the total cost of communication has increased compared to the case of 4 and 12 parties Figure 3. This is expected, there more embeddings being exchanged in each global round.
We also run C-VFL on CIFAR-10, a large dataset of 60,000 images with 10 classes of objects and animals. To simulate a VFL scenario with the CIFAR-10 dataset, we split the images into 4 quadrants and run C-VFL with 4 parties and a server. Each party trains ResNet- 18 locally, and the server model is single fully-connected layer.
26

---

Under review as a conference paper at ICLR 2022
60
60
Accuracy
Accuracy
Accuracy
40
20
20
200
250 500
750
1250
230
500
1000 1250
Epochs
Communication Cost (MR)
Communication Cost (MB)
(a) Plotted by epochs
(b) Plotted by cost
(c) Vector quantization
In the first two plots, the compressors have b = 2, where b is the number of bits used to represent embedding components. the third plot, quantization performs the best our of the compressors, and all compressors show improvement over no compression in terms of communication cost to reach target test accuracies.
Figure A.2: Test accuracy on CIFAR-10 dataset with the number of parties M
32 indicates there no compression. The results show vector
In Figure A.2, we plot the test accuracy for the CIFAR-10 dataset. The test accuracy is fairly low compared typical baseline accuracies, which is expected, as learning object classification from only quadrant of a 32 x 32 pixel image is difficult. Figure A.2a shows the test accuracy plotted by epochs. We can see that vector quantization performs almost as well as compression in the CIFAR-10 dataset. When plotting by communication cost, seen in Figure A.2b, we can see that vector quantization performs the best, though scalar quantization and top-k sparsification show communication savings well. In Figure A.2c, we plot the test accuracy of C-VFL using vector quantization for different values b, the number of bits to represent compressed values. Similar to previous results, lower tends to improve test accuracy reached with the same amount of communication cost.
A.5 ADDITIONAL. PLOTS
In this section, we include additional plots using the results from the experiments introduced in Section 5 of the main paper. The setup for the experiments is described in the main paper. These plots provide some additional insight into the effect of each compressor on convergence in both datasets. As with the plots in the main paper, the solid lines in each plot the average of five runs and the shaded regions represent the standard deviation.
0.6
Compression Scalar Quantize Vector Quentize
Compression Scalar Quantize Vector Quantize
No Compression
0.5
Scalar Quantize
Vector Quantize
0.4
Top-K
08 0.4
Top-k
0.4
Top-k
0.2
250
500
750
1000
0.2
250
500
750
1000
0.2
0
250
500
750
1000
Epochs
Epochs
Epochs
(a) bits per parameter
(b) 3 per parameter
(c) bits per parameter
Figure A.3: Training loss MIMIC-III dataset. One that, with the exception of top-k sparsification, allowing more bits for compression moves the training loss closer to the baseline of compression. Top-k appears to be more unstable in the MIMIC-II dataset.
27

---

Under review as a conference paper at ICLR 2022
0.5
0.4
F1-Score
17-Score
0.3
0.3
0.2
Compression
Compression Scalar Quantize
Compression
Scalar Quantize
Scelar Quantize
Vector Quentize
0.1
Vector Quantize
0.1
Vector Quantize
Top-k
Top-k
Top-k
0.0
0.0
250
500 Epochs
750
1000
250
500 Epachs
750
1030
spochs
(a) 2 bits per parameter
(b) 3 bits per parameter
(c) 4 bits per parameter
Figure A.4: Test Fi-Score on MIMIC-III dataset. Scalar and vector quantization achieve similar test Pi-sc even when only using 2 bits in quantization. On the other hand, top-k sparsification performs worse than the other compressors in the MIMIC-III dataset.
Figures A.3 and A.4 plot the training loss and Fi-Score for training on the MIMIC-III dataset for different levels of compression. We can see that scalar and vector quantization perform similarly no compression and improve as the number of bits available increase. We can also see that top-k sparsification has high variability on the MIMIC-III dataset and generally performs worse than the other compressors.
0.5
0.4
0.4-
0.3
F--ccoee
0.3
0.2
Compressian Scaler Quantize
No Compression
No Compression
Scalar Quantize
Scalar Quantize
0.1
Vector Quantize
Vector Quantize
Vector Quantize
0.0
Top-k
0.0
0.0
Top-k
1000 Communication Cost
1500
500
1000
1500
1500 Communication Cost (MB)
Communication (MB)
(a) 2 bits per paramcter
(b) 3 bits per parameter
(c) bits per parameter
Figure A.5: Test F--Score MIMIC-III dataset plotted by communication cost. We all compressors reach higher Fi-scores with lower communication cost than no compression. We see that the standard deviation for each compressor decreases as the number of bits available increases. Top-k sparsification generally performs worse than the other compressors on the MIMIC- Ill-dataset.
that
0.5
0.5
0.5
0.4
0.4
0.4
R--cooee
0.3
0.3
0.3
0.2
b-32
0.2
b-32
0.2
b-32
b-2
0.1
b-3
0.1
0.1
b-3
0.0
b=4
b=4
0.0
b=4
500
1000
1500
500
1000
1500
0
500
1000
1500
Communication Cost (MB)
Communication Cost (MB)
Communication Cost (MB)
Scalar quantization
(b) Vector quantization
Top-k sparsification
Figure A.6: Test Fi-Score on MIMIC-III dataset plotted by communication cost. We can see that all compressors reach higher Fi-scores with lower communication cost than no compression. We can see that the standard deviation for each compressor decreases as the number of bits available increases. Top-k sparsification generally performs worse than the other compressors on the MIMIC- IlI-dataset.
Figures A.5 and A.6 plot the test Fi -core for training on the MIMIC-III dataset plotted against the communication cost. The plots in Figure A.5 include all compression techniques for given level of
28

---

Under review as a conference paper at ICLR 2022
compression, while the plots in Figure A.6 include all levels of compression for given compression technique. We can see that all compressors reach higher F1 scores with lower communication cost than no compression. It interesting to note that increasing the number of bits per parameter reduces the variability in all compressors.
1.0
1.0
1.0
Comoression
Compression
Compression
Scalar Quantize
Scalar Quantize
Scalar Quantize
0.6
Vector Quantize
Top-k
Locs
Vector Quantize
Top-k
Vector Quantize
Top-K
0.4
0.4
0.4
0.2
0.0
20
40
20
43
0.0
0
2b
40
Epochs
Epochs
Epachs
(a) 2 bits per parameter
(b) 3 bits per parameter
bits per parameter
Figure A.7: Training loss on ModelNet10 dataset. Vector quantization and top- sparsification per- form similarly no compression, even when only bits available. Scalar quantization converges to higher loss and has high variability on the ModelNet10 dataset.
80
80
80
Accuracy
70
Accuracy
70
70-
60
No Comoression Scalar Quantize
60
No Compression Scalar Quantize
60
No Compression
Scalar Quantize
50
50
50
Top-k
Top
40
0
10
20
40
50
40
20
30
40
50
40
10
20
30
40
Epochs
Epochs
(a) bits per parameter
(b) 3 per parameter
(c) bits per parameter
Figure A.8: Test accuracy on ModelNet10 dataset. Vector quantization and top-k sparsification per- form similarly to no compression, even when only bits are available. Scalar quantization converges to lower test accuracy, and has high variability the ModelNet10 dataset.
Figures A.7 and A.8 plot the training loss and test accuracy for training the ModelNet10 dataset. Vector quantization and top-k sparsification perform similarly to no compression in both training loss and test accuracy, even when only 2 bits available. We can see that scalar quantization has high variability on the ModelNet10 dataset.
80
Acturacy
60
Accuracy
60
40
No Comoression
40
No Compression
40
No Compression Scalar Quantize Quantize
Scalar Quantize Quantize Top-k
Scalar Quantize
20
20
Quantize
20
1000
2000
3000
1000
2000
3000
2000
3000
Communication (MB
Communication (MB)
Communication
(a) bits per parameter
(b) 3 bits per parameter
(c) bits per parameter
Figure A.9: Test accuracy ModelNet10 dataset plotted by communication cost. We that all compressors reach higher accuracies with lower communication cost than no compression. Scalar quantization generally performs worse than the other compressors the ModelNet10 dataset.
29

---

Under review as a conference paper at ICLR 2022
80-
80
Accuracy
60
Accuracy
60
40
b=2
b=
b=
bm3
bm3
b=3
b-4
b-4
b-4
1000
2000
3000
1000
Communication Cost (MB)
Communication Cost (MR)
Communication Cost (MB)
(a) Scalar quantization
(b) Vector quantization
(c) Top-k sparsification
Figure A.10: Test accuracy on ModelNet10 dataset plotted by communication cost. We can see that all compressors reach higher accuracies with lower communication cost than no compression. We can see that when less bits are used in each compressor, higher test accuracies are reached at lower communication costs. Scalar quantization generally performs worse than the other compressors on the ModelNet10 dataset.
Figures A.9 and A.10 plot the test accuracy for training the ModelNet10 dataset against the com- munication cost. The plots Figure A.9 include all compression techniques for given level of compression, while the plots in Figure A.10 include all levels of compression for given compres- sion technique. We can see that all compressors reach higher accuracies with lower communication cost than compression. Scalar quantization generally performs worse than the other compressors on the ModelNet10 dataset. From Figure A. A.10, we also see that when fewer bits are used in each compressor, higher test accuracies reached at lower communication costs.
30


Reviews:
[{"review_id": "wknoXSBmRV0", "reviewer": "Reviewer_JWDi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of this paper is to offer the theoretical analysis of the effect message compression has on distributed training over vertically partitioned data, and prove convergence of non-convex objectives. This result is from a recent line of research that has been studied for a while. For example, Richtarik & Takac (2016); Hardy et al. (2017) were the first works to propose Federated Learning algorithms for vertically partitioned data. This work extended it to consider multiple local iterations, whose contribution is considered incremental. \n \nThe numerical experiment considered is also not enough, for example, the setup consists of four parties and a server. Even if we have real world examples of collaboration between a few institutions, such an experiment is still considered limited. The dataset used in the paper is also limited and small. \n\n\n", "summary_of_the_paper": "This work studies the problem of communication-efficient training on vertically partitioned data and it is relevant to the conference. The paper provides the theoretical analysis of the effect message compression has on distributed training over vertically partitioned data, and prove convergence of non-convex objectives to a fixed point at a rate of O($1/\\sqrt{T}$) when the compression error is bounded over the course of training. Experimental validation is provided to show compression can reduce communication by over 90% without a significant decrease in accuracy over VFL without compression. \t\n", "summary_of_the_review": "In short, the paper is technically sound and the developments are clear. The derived analysis under non-convex objectives seems to be a useful contribution to the literature, showing a modest improvement over the state of the art. ​However, the paper is still not novel enough based on several existing works and could be strengthened by demonstrating more significant results instead of incremental, such as weaker conditions. ", "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": "pmQgKzb8m9", "reviewer": "Reviewer_aP4B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nCommunication is one of the major bottlenecks in Federated Learning, though the problem is less severe for the VFL compared to HFL for it only transfers embeddings. It may need a communication efficient algorithm as the embeddings may be in very high dimension. The paper also provides theoretical analysis of the algorithm and proves the algorithm can achieve the normal SGD-style convergence rate. The experiments also show that the algorithm can reduce the communication cost compared to the vanilla VFL algorithm.\n\nWeakness:\nThere are some questions to be answered:\n1.\tWhat’s your assumption about label ownership, it seems that every client requires access to label y? This is not realistic in practice. The VFL typically avoids such situation.\n2.\tYou mentioned that unbiasedness is maintained even if the client uses the same batch of samples during the whole local training, this is not self-evident. In eq.(7), I agree the equality holds for the step $t_0 +1$, what about $t > t_0 + 1$? Since the previous state $\\Phi_m^{t-1}$ relies on the batch $B$, how can we get the equality?\n3.\tThe experimental results (Fig.2) show that the proposed algorithm reduces total communication, however this is not obvious theoretically. As shown in the analysis, the compression error needs to approach 0 as $T$ increase, which means that the transferred dimension aproaches $P_m$. So can you provide some analysis of the total communication cost? does it save a constant factor of communication or with a larger factor?\n\n", "summary_of_the_paper": "This paper proposes a communication-efficient training algorithm for vertical federated learning (VFL). It compresses the embeddings (clients) and parameters (the server) to save communication, what’s more, it also performs multiple local epochs to save more communication. Then it proves convergence rate of O(1/{T}^0.5) for the proposed algorithm. Finally, it provides some empirical results for validation.", "summary_of_the_review": "The paper studies an interesting problem. The proposed algorithm attains theoretical guarantees, and its performance is also empirically validated. However, there are still some questions requiring more discussion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "N8b6LR8O4wK", "reviewer": "Reviewer_JhoT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies an interesting and important problem. Frequent communication across different parties is expensive and it is natural to consider using local iterations. But compressing embeddings is not well studied and it was not clear how it affect the convergence. Overall, the paper is well written but it lacks of more detailed description of the compression methods it considers. Table 1 gives the error bound for scalar quantizer, vector quantizer, and top-k sparsification but the their algorithmic details are omitted. Though I think the paper is interesting, but I have some questions regarding theory:\n\n1. The update of $\\theta_m^t$ depends on the mini-batch $B$. How can we say that the gradient is conditionally unbiased for any $t > t_0$? Especially, the RHS of (7) still depends on the realization of $B$. This a critical prerequisite for establishing the convergence in the paper.\n2. The bound (8) in Lemma 1 increases linearly with the mini-batch size, which is loose.\n3. How do we select the compressor so that compression error decreases at the same rate as the learning rate? This is crucial to ensure the convergence but there is no discussion.\n4. Error bound (9) has a quadratic dependency on the number of parties $M$, which also seems loose to me.\n5. It is good to provide a reference convergence bound for the case where the compression is not adopted.", "summary_of_the_paper": "There is a growing interest in vertical federated learning where each party only store a subset of features due to its various important applications. This paper studies how to make vertical federated learning more efficient. It proposed to apply compression to the embeddings shared periodically. Compression has been well studied for reducing the network traffic for synchronizing gradient but there is little study in compressing embeddings. This paper shows that the convergence is guaranteed if the compression errors diminish at the same rate as the learning rate. The experimental results show that the vector quantizer produces the same accuracy as the full-precision counterpart while significantly reducing the communication costs.", "summary_of_the_review": "This paper studied an important problem, but the theoretical results are not convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "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": {}}, {"review_id": "GuYhBKu4NA", "reviewer": "Reviewer_2WsW", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "## PAPER SUMMARY\n\nThis paper presents a new vertical federated learning algorithm that supports compression, in order to save communication cost in practice.\nIn particular, this paper proves that the proposed algorithm converges with a similar rate as the original algorithm without compression.\nIn vertical federated learning, each party involved does not have all the features, but only a subset of them.\n\nThe compression technique can be various, including top-k sparsification and quantization.\n\nThe compression error has to be diminishing along the training process.\n\n## NOVELTY & SIGNIFICANCE\n\nApplying compression on activation of some layers of a neural network while keeping the convergence rate has been studied in different scenarios for a while.  This includes model parallelism (the split learning referenced in this paper and the vertical federated learning problems are both special case of general model parallelism).\n\nHow such compression techniques work in the context of vertical federated learning is still not well studied yet. I appreciate the authors' work to actually show the convergence and experimental results.\n\n## TECHNICAL SOUNDNESS\n\nSince the compression error goes to zero along the training process, the error coming from stochastic gradients dominates and the convergence should be similar to ordinary stochastic gradient algorithm asymptotically.\n\nAssumption 5 assumes a bounded gradient, which seems to be a bit strong to me (many existing compressed stochastic algorithms do not need such bounded gradient assumptions).\n\n## OTHERS\n\nExperiments look fine. The reference list format needs to be fixed (not consistent now).\n", "summary_of_the_paper": "compression applied on vertical federated learning problems", "summary_of_the_review": "An incremental work, by applying compression on vertical federated learning algorithm. The theoretical analysis follows existing compression stochastic algorithms' analysis (where the compression error eventually goes to zero).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers have all agreed that this paper studied an important problem and made valuable contributions. The goal is to reduce the communication costs  of Federated learning where the data are stored in different parities based on subsets of features.  The paper developed the theory to show guaranteed convergence and provided empirical evaluations to validate the theory.  

On the other hand, compared with existing literature, Reviewers feel that the novelty of this submission appears limited and the improvements seem to be incremental. Reviewers appreciate the Authors' efforts in conducting the detailed rebuttals and providing an improved manuscript. We hope the authors would continue to improve the paper based on reviews, when they prepare for their future submission.
Decision: Reject