Year: 2021

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( 1 √ 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.

text: 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.

heading: 1 INTRODUCTION
text: Federated Learning (McMahan et al., 2017) is a 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 et al., 2019; Rieke et al., 2020; Lim et al., 2020) in 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 be communication-efficient 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 on training performance.
Federated Learning methods often target the case where the data among parties is distributed horizontally: 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 a vertical manner: the parties store data on the same sample IDs but different feature spaces.
An example of a 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, financial transactions, and vehicle accident reports, respectively. These features must remain local to the institutions due to privacy concerns, rules and regulations (e.g., GDPR, HIPAA), and/or communication network limitations. In such a scenario, Vertical Federated Learning (VFL) methods must be employed. Although VFL is less well-studied than HFL, there has been a growing interest in VFL 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 pharmaceuticals (Kairouz et al., 2021).
Typically in VFL, each party trains a local embedding function that maps raw data features to a meaningful vector representation, or embedding, for prediction tasks. For example, a neural network can be an embedding function for mapping the text of an online article to a vector space for classification (Koehrsen, 2018). Referring to Figure 1a, suppose Party 1 is a hospital with medical data
features x1. The hospital computes its embedding h1(θ1;x1) for the features by feeding x1 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 encryption, secure multi-party computation, or secure aggregation). The embeddings are then combined in a server model θ0 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 et al., 2019; Nie et al., 2021; Han et al., 2021). Embeddings can be very large, in practice, sometimes requiring terabytes of communication over the course of training.
Motivated by this, we propose Compressed Vertical Federated Learning (C-VFL), a general framework for communication-efficient Federated Learning over vertically partitioned data. In our algorithm, parties communicate compressed embeddings periodically, and the parties and the server each run block-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 in 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 are parameters in the partial derivatives calculated at each party. The effect of compression error on the resulting partial derivatives may be complex; therefore, the analysis in previous work on 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( 1√
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 an arbitrary server model, allowing support for more complex prediction tasks than those supported by previous VFL algorithms.
We summarize our 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 a fixed point on non-convex objectives at a rate ofO( 1√ T ) for a 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 as well. Our work provides novel analysis for the effect of compressing embeddings on
convergence in a 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 CVFL. In particular, we examine scalar quantization (Bennett, 1948), lattice vector quantization (Zamir & Feder, 1996), and top-k sparsification (Lin et al., 2018).
4. We evaluate our algorithm by training LSTMs on the MIMIC-III dataset and CNNs on the ModelNet10 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. Richtárik & Takác (2016); Hardy et al. (2017) were the first works to propose Federated Learning algorithms for vertically partitioned data. Chen et 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 at 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 a common topic in HFL scenarios, where participants exchange gradients 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 sparsification (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 compression in VFL, as the effect of embedding compression error on each party’s partial derivatives may be complex. No prior work has analyzed the impact of compression on 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 experimental results are given in Section 5. Finally, we conclude in Section 6.

heading: 2 PROBLEM FORMULATION
text: We present our problem formulation and notation to be used in the rest of the paper. We let ‖a‖ be the 2-norm of a vector a, and let ‖A‖F be the Frobenius norm of a matrix A.
We consider a set of M parties {1, . . . ,M} and a server. The dataset X ∈ RN×D is vertically partitioned a priori across the M parties, where N is the number of data samples and D is the number of features. The i-th row of X corresponds to a data sample xi. For each sample xi, a party m holds a disjoint subset of the features, denoted xim, so that x i = [xi1, . . . , x i M ]. For each x
i, there is a corresponding label yi. Let y ∈ RN×1 be the vector of all sample labels. We let Xm ∈ RN×Dm be the local dataset of a party m, where the i-th row correspond to data features xim. 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 a 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 m holds a set of model parameters θm as well as a local embedding function hm(·). The server holds a set of parameters θ0 called the server model and a loss function l(·) that combines the embeddings hm(θm;xim) from all parties. Our objective is as follows:
minimize Θ
F (Θ; X; y) := 1
N N∑ i=1 l(θ0, h1(θ1;x i 1), . . . , hM (θM ;x i M ); y i) (1)
where Θ = [θT0 , . . . , θ T M ] T is the global model. An example of a global model Θ is in Figure 1a.
For simplicity, we let m = 0 refer to the server, and define h0(θ0;xi) := θ0 for all xi, where h0(·) is equivalent to the identity function. Let hm(θm;xim) ∈ RPm for m = 0, . . . ,M , where Pm is the size of the m-th embedding. Let ∇mF (Θ; X; y) := 1 N ∑N i=1∇θm l(θ0, h1(θ1;xi1), . . . , hM (θM ;xiM ); yi) be the partial derivatives for parameters θm.
Let XB and yB be the set of samples and labels corresponding to a randomly sampled mini-batch B of size B. We let the stochastic partial derivatives for parameters θm be ∇mFB(Θ; X; y) := 1 B ∑ xi,yi∈XB,yB ∇θm l(θ0, h1(θ1;xi1), . . . , hM (θM ;xiM ); y). We may drop X and y from F (·) and FB(·). With a minor abuse of notation, we let hm(θm; XBm) := {hm(θm;xB 1 m ), . . . , hm(θm;x BB m )} be the set of all party m embeddings associated with mini-batch B, where Bi is the i-th sample in the mini-batch B. We let ∇mFB(Θ) and ∇mFB(θ0, h1(θ1; XB1 ), . . . , hM (θM ; XBM )) be equivalent, and use them interchangeably.
Assumption 1. Smoothness: There exists positive constants L <∞ and Lm <∞, for m = 0, . . . ,M , such that for all Θ1, Θ2, the objective function satisfies ‖∇F (Θ1)−∇F (Θ2)‖ ≤ L ‖Θ1 −Θ2‖ and ‖∇mFB(Θ1)−∇mFB(Θ2)‖ ≤ Lm ‖Θ1 −Θ2‖. Assumption 2. Unbiased gradients: Form = 0, . . . ,M , for a randomly selected mini-batch B, the stochastic partial derivatives are unbiased, i.e., EB∇mFB(Θ) = ∇mF (Θ). Assumption 3. Bounded variance: For m = 0, . . . ,M , there exists constants σm <∞ such that the variance of the stochastic partial derivatives are bounded as: EB‖∇mF (Θ)−∇mFB(Θ)‖2 ≤ σ2m B for a randomly selected mini-batch B of size B.
Assumption 1 bounds how fast the gradient and stochastic partial derivatives can change. Assumptions 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 analysis 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. However, in VFL settings, all parties store identical sample IDs but different subsets of features. Hence, there is no equivalent notion of a non-IID distribution in VFL.
Assumption 4. Bounded Hessian: There exists positive constants Hm for m = 0, . . . ,M such that for all Θ, the second partial derivatives of FB with respect to hm(θm; XBm) satisfy: ‖∇2hm(θm;XBm)FB(Θ)‖F ≤ Hm for any mini-batch B.
Assumption 5. Bounded Embedding Gradients: There exists positive constants Gm for m = 0, . . . ,M such that for all θm, the stochastic embedding gradients are bounded by: ‖∇θmhm(θm; XBm)‖F ≤ Gm for any mini-batch B.
Since we are assuming a Lipschitz-continuous 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).

heading: 3 ALGORITHM
text: We now present C-VFL, a communication-efficient method for training a global model with vertically 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 θm forQ 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 embeddings 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: Cm(·) : RPm → RPm for m = 0, . . . ,M . To calculate the gradient for data sample xi, party m receives Cj(hj(θj ;xij)) from all parties j 6= m. With this information, a party m can compute ∇mFB and update its parameters θm for multiple local iterations. Note that each party uses a stale view of the global model to compute 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 use stale information. An example view a party has of the global model during training is in Figure 1b. Here, t is the current iteration and t0 is the start of the most recent global round, when embeddings were shared.
Algorithm 1 Compressed Vertical Federated Learning 1: Initialize: θ0m for all parties m and server model θ00 2: for t← 0, . . . , T − 1 do 3: if t mod Q = 0 then 4: Randomly sample Bt ∈ {X, y} 5: for m← 1, . . . ,M in parallel do 6: Send Cm(hm(θtm; XB t
m )) to server 7: end for 8: Server sends {C0(θ0), C1(h1(θt1; XB t 1 )), . . . , CM (hM (θtM ; X Bt M ))} to all parties
9: end if 10: for m← 0, . . . ,M in parallel do 11: Φ̂tm ← {C0(θ t0 0 ), C1(h1(θ t0 1 ; X Bt0 1 )), . . . , hm(θ t m; X Bt0 m ), . . . , CM (hM (θ t0 M ; X Bt0 M ))} 12: θt+1m ← θtm − ηt0∇mFB(Φ̂tm; yB t0
) 13: end for 14: end for
Algorithm 1 details the procedure of C-VFL. In each global round, when t mod Q = 0, a minibatch B is randomly sampled from X and the parties exchange the associated embeddings, compressed using Cm(·), via the server (lines 3-9). Each party m completes Q local iterations, using the compressed embeddings it received in iteration t0 and its own m-th uncompressed embedding set hm(θ t m,X Bt0 m ). We denote the set of embeddings that party m uses as:
Φ̂tm := {C0(θ t0 0 ), C1(h1(θ t0 1 ; X Bt0 1 )), . . . , hm(θ t m; X Bt0 m ), . . . , CM (hM (θ t0 M ; X Bt0 M ))}. (2)
For each local iteration, each party m updates θm by computing the stochastic partial derivatives ∇mFB(Φ̂tm; yB t0 ) and applying a gradient step with step size ηt0 (lines 13-16).
A key difference here from previous VFL algorithms is that C-VFL shares the server model with all parties in order to support multiple local gradient updates with a 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 ·Pm+ |θ0|)) for R global rounds. Our compression technique replaces Pm and |θ0| 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. In HFL settings, model update or gradient information is shared in messages. It has been shown that gradients can leak information about the raw data (Phong et al., 2018; Geiping et al., 2020). However in C-VFL, 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. Embeddings may be vulnerable to model inversion attacks (Mahendran & Vedaldi, 2015), which are methods by which an attacker can recover raw input to a model using the embedding output and black-box access to the model. One can protect against such an attack using homomorphic encryption (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 (FederatedAI, 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 to 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 4 would still hold in this case, and the additional communication is reduced by the use of message compression.

heading: 4 ANALYSIS
text: In this section, we discuss our analytical approach and present our theoretical results. We first define the compression error associated with Cm(·):
Definition 1. Compression Error: Let vectors x i
m for m = 0, . . . ,M , be the compression errors of Cm(·) on a data sample xi: x i
m := Cm(hm(θm;xi)) − hm(θm;xi). Let t0m be the Pm × B matrix with x i
m for all data samples x i in mini-batch Bt0 as the columns. We denote the expected squared
message compression error from party m at round t0 as Et0m := E ‖ t0m‖ 2 F .
Let Ĝ t = [(∇0FB(Φ̂t0; yB t0 ))T , . . . , (∇MFB(Φ̂tM ; yB t0 ))T ]T . The model Θ evolves as:
Θt+1 = Θt − ηt0Ĝ t . (3)
We note the reuse of the mini-batch of Bt0 for Q iterations in this recursion. This indicates that the stochastic gradients are not unbiased during local iterations t0 +1 ≤ t ≤ t0 +Q−1. However, using conditional expectation, we can apply Assumption 2 to the gradient calculated at iteration t0 when there is no compression error. We define Φtm to be the set of embeddings that would be received by party m if no compression error were applied:
Φtm = {θ t0 0 , h1(θ t0 1 ; X Bt0 1 ), . . . , hm(θ t m; X Bt0 m ), . . . , hM (θ t0 M ; X Bt0 M )}. (4)
Then, if we take expectation over Bt0 conditioned on previous global models Θt up to t0:
EBt0 [∇mFB(Φt0m) | {Θτ} t0 τ=0] = ∇mF (Φt0m). (5)
With the help of (5), we can prove convergence by bounding the difference between the gradient at the start of each global round and those calculated during local iterations (see the proof of Lemma 2 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 function value with compressed and uncompressed embeddings is bounded as:
E‖∇mFB(Φ̂tm)−∇mFB(Φtm)‖2 ≤ H2mG2m ∑M j=0,j 6=mE t0 j . (6)
The proof of Lemma 1 is given in the appendix. Using Lemma 1, we can bound the effect of compression error on convergence.
We present our main theoretical results. All proofs are provided in the appendix. Theorem 1. Convergence with fixed step size: Under Assumptions 1-5, if ηt0 = η for all iterations and satisfies ηt0 ≤ 116Qmax{L,maxm Lm} , then the average squared gradient over R global rounds of Algorithm 1 is bounded by:
1
R R−1∑ t0=0 E [∥∥∇F (Θt0)∥∥2] ≤ 2 [F (Θ0)− E [F (ΘT )]] ηT + 4ηQL M∑ m=0 σ2m B
+ 68Q2
R M∑ m=0 H2mG 2 m R−1∑ t0=0 M∑ j=0,j 6=m Et0j . (7)
The first term in (7) is based on 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 Lm’s. 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 Et0j = 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 second and third terms include a coefficient relating to local iterations. As the number of local 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 haveQ > 1 in 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 a small role in convergence error. We note that when M = 1 and Q = 1, Theorem 1 applies to Split Learning (Gupta & Raskar, 2018) when only uploads to the server are compressed.
Remark 1. Let E = 1R ∑R−1 t0=0 ∑M m=0 Et0m . If ηt0 = 1√ T for all global rounds t0, for Q and B
independent of T , then 1R ∑R−1 t0=0 E [ ‖∇F (Θt0)‖2 ] = O( 1√ T +E). This indicates that if E = O( 1√ T ) then we can achieve a convergence rate of O( 1√ T
). 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.
We consider a diminishing step size in the following theorem. Theorem 2. Convergence with diminishing step size: Under Assumptions 1-5, if 0 < ηt0 < 1 satisfies ηt0 ≤ 116Qmax{L,maxm Lm} , then the minimum squared gradient over R global rounds of Algorithm 1 is bounded by:
min t0=0,...,R−1
E [∥∥∇F (Θt0)∥∥2] = O( 1∑R−1
t0=0 ηt0
+
∑R−1 t0=0
(ηt0)2∑T−1 t=0 η t0 +
∑R−1 t0=0 ∑M m=0 η
t0Et0m∑R−1 t0=0 ηt0
) .
If ηt0 and Et0m satisfy ∑∞ t0=0 ηt0 = ∞, ∑∞ t0=0 (ηt0)2 < ∞, and ∑∞ t0=0 ∑M m=0 η
t0Et0m < ∞, then mint0=0,...,R−1 E [ ‖∇F (Θt0)‖2 ] → 0 as R→∞.
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( 1√
T ) in the context of Theorem 1, and guarantee convergence in
the context of Theorem 2. We analyze three common compressors: a uniform scalar quantizer (Bennett, 1948), a 2-dimensional hexagonal lattice quantizer (Zamir & Feder, 1996), and top-k sparsification (Lin et al., 2018). For uniform scalar quantizer, we let there be 2q 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. In Table 1, we present the choice of compressor parameters in order to achieve a convergence rate ofO( 1√
T ) in the context of Theorem 1.
We show how we 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 ηt0 = O( 1t0 ), where t0 is the current round. Then setting T = t0 in Table 1 provides a choice of compression parameters at each iteration to ensure the compression error diminishes at a rate ofO( 1√
t0 ), 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.

heading: 5 EXPERIMENTS
text: We present experiments to examine the performance of C-VFL in practice. The goal of our experiments is to examine the effects different compression techniques have on training, and investigate the accuracy/communication trade-off empirically.
Unless otherwise specified, our experimental setup consists of four parties and a server. Most realworld VFL settings include collaboration between a few institutions (Kairouz et al., 2021), so we
expect the number of parties to be small. We train our system with two datasets: the MIMICIII 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 are CAD photos of objects, 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 ModelNet10 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.
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 embedding values need to be bounded. In the case of MIMIC-III’s LSTM, the embedding values are the output of a tanh activation function and have a bounded range of [−1, 1]. For ModelNet10, the embeddings are the output of a ReLU activation function, and may be unbounded. We scale embedding values for ModelNet10 to the range [0, 1]. We apply subtractive dithering to both the scalar quantizer (Wannamaker, 1997) and vector quantizer (Shlezinger et al., 2021).
In our experiments, each embedding component is a 32-bit float. Let b be the bits per component we compress to. For the scalar quantizer, this means there are 2b quantization levels. For the 2-D vector quantizer, this means there are 22b 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 b32 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 a standard VFL algorithm without embedding compression, acting as a baseline for accuracy.
In Figure 2, we plot the test F1-Score and test accuracy for MIMIC-III and ModelNet10, respectively, when training with b = 2. We use F1-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 embeddings, 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, 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 a 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 b = 32. For the MIMIC-III dataset, we show the maximum test F1-score reached and the total communication cost of reaching an F1-Score of 0.4. The maximum F1-score 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 b = 2, we can achieve over 90% communication cost reduction over no compression to reach a target F1-score.
For the ModelNet10 dataset, Table 2 shows the maximum test accuracy reached and the total communication cost of reaching an accuracy of 75%. We can see similar results as for the MIMIC-III
(a) Parties M = 4 (b) Parties M = 12
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 to 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/computation tradeoff of local iterations. We show how the number of local iterations affects the time to reach a target F1-score in the MIMIC-III 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 a 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 is 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 is high, it may be beneficial to 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.
Finally, in Figure 3, we plot the test accuracy of ModelNet10 against the communication cost when using vector quantization with b = 2, 3, 4, and 32. We include plots for 4 and 12 parties. In the 12 party setup, each party stores one view for each CAD model. We note that changing the number of 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.

heading: 6 CONCLUSION
text: We proposed C-VFL, a distributed communication-efficient algorithm for training a model over vertically partitioned data. We proved convergence of the algorithm to a fixed point at a rate of O( 1√
T ), 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.

heading: A APPENDIX

heading: A.1 PROOFS OF THEOREMS 1 AND 2
text: In this section, we provide the proofs for Theorems 1 and 2.

heading: A.1.1 ADDITIONAL NOTATION
text: Before starting the proofs, we define some additional notation to be used throughout. At each iteration t, each party m trains with the embeddings Φ̂tm. This is equivalent to the party training directly with the models θtm and θ t0 j for all j 6= m, where t0 is the last communication iteration when party m received the embeddings. We define:
γtm,j =
{ θtj m = j
θt0j otherwise (A.1)
to represent party m’s view of party j’s model at iteration t. We define the column vector Γtm = [(γ t m,0) T ; . . . ; (γtm,M ) T ]T 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 F̂B(Γ t m) to be the stochastic loss with compression error for a randomly selected mini-batch B calculated by party m at iteration t:
F̂B(Γ t m) := FB ( θt00 + t0 0 , h1(θ t0 1 ; X Bt0 1 ) + t0 1 , . . . , hm(θ t m; X Bt0 m ), . . . , hM (θ t0 M ; X Bt0 M ) + t0 M ) .
(A.2)
Recall the recursion over the global model Θ:
Θt+1 = Θt − ηt0Ĝ t . (A.3)
We can equivalently define Ĝ t as follows:
Ĝ t = [ (∇0F̂B(Γt0))T , . . . , (∇M F̂B(ΓtM ))T ]T . (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∇mF̂B(Γtm). For our analysis, we redefine the set of embeddings for a mini-batch B of size B from party m as a matrix:
hm(θm; XBm) := [ hm(θm;x B1 m ), . . . , hm(θm;x BB m ) ] . (A.5)
hm(θm; XBm) is a matrix with dimensions Pm ×B where each column is the embedding from party m for a single sample in the mini-batch.
Let P = ∑M m=0 Pm be the sum of the sizes of all embeddings. We redefine the set of embeddings used by a party m to calculate its gradient without compression error as a matrix:
Φ̂tm = [ (θt00 ) T , (h1(θ t0 1 ; X Bt0 1 )) T , . . . , (hm(θ t m; X Bt0 m )) T , . . . , (hM (θ t0 M ; X Bt0 M )) T ]T . (A.6)
Φ̂tm is a matrix with dimensions P ×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 a mini-batch B of size B from party m is the matrix: t0m := [ B 1 m , . . . , BB m ] . (A.7)
t0m is a matrix of dimensions Pm × B where each column is the compression error from party m for a single sample in the mini-batch.
We define the compression error on each embedding used in party m’s gradient calculation at iteration t:
Et0m = [ ( t00 ) T , . . . , ( t0m−1) T , 0T , ( t0m−1) T , . . . , ( t0M ) T ]T . (A.8)
Et0m is a matrix with dimensions P × 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:
∇mFB(Φtm + Et0m) := ∇mF̂B(Γtm). (A.9)
Note that we can apply the chain rule to∇mF̂B(Γtm):
∇mF̂B(Γtm) = ∇θmhm(θtm)∇hm(θm)FB(Φ t m + E t0 m). (A.10)
With this expansion, we can now apply Taylor series expansion to ∇hm(θm)FB(Φtm + Et0m) around the point Φtm:
∇hm(θm)FB(Φ t m + E t0 m) = ∇hm(θm)FB(Φ t m) +∇2hm(θm)FB(Φ t m) tEt0m + . . . (A.11)
We let the infinite sum of all terms in this Taylor series from the second partial derivatives and up be denoted as Rm0 :
Rm0 (Φ t m + E t0 m) := ∇2hm(θm)FB(Φ t m) TEt0m + . . . (A.12)
Note that all compression error is in Rm0 (Φ t m + E t0 m). Presented in Section A.1.2, the proof of Lemma 1’ shows how we can bound Rm0 (Φ t m + E t0 m), bounding the compression error in ∇mF̂B(Γtm).
Let Et0 = EBt0 [ · | {Θτ}t0τ=0]. Note that by Assumption 2, Et0 [ Gt0 ]
= ∇F (Θt0) as when there is 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 t0. However, this is not true for iterations t0 + 1 ≤ t ≤ t0 +Q− 1, as we reuse the mini-batch Bt0 in these local iterations. We upper bound the error introduced by stochastic gradients calculated during local iterations in Lemma 2.

heading: A.1.2 SUPPORTING LEMMAS
text: Next, we provide supporting lemmas and their proofs.
We restate Lemma 1 here: Lemma 1. Under Assumptions 4-5, the norm of the difference between the objective function value with and without error is bounded by:
E ∥∥∥∇mFB(Φ̂tm)−∇mFB(Φtm)∥∥∥2 ≤ H2mG2m M∑
j=0,j 6=m
Et0j . (A.13)
To prove Lemma 1, we first prove the following lemma: Lemma 1’. Under Assumptions 4-5, the squared norm of the partial derivatives for party m’s embedding multiplied by the Taylor series terms Rm0 (Φ t m + E
t0 m) is bounded by:∥∥∇θmhm(θtm)Rm0 (Φtm + Et0m)∥∥2 ≤ H2mG2m ∥∥Et0m∥∥F . (A.14)
Proof. ∥∥∇θmhm(θtm)Rm0 (Φtm + Et0m)∥∥2 ≤ ∥∥∇θmhm(θtm)∥∥2F ∥∥Rm0 (Φtm + Et0m)∥∥2F (A.15) ≤ H2m
∥∥∇θmhm(θtm)∥∥2F ∥∥Et0m∥∥2F (A.16) where (A.16) follows from Assumption 4 and the following property of the Taylor series approximation error: ∥∥Rm0 (Φtm + Et0m)∥∥F ≤ Hm ∥∥Et0m∥∥F . (A.17)
Applying Assumption 5, we have:
∥∥∇θmhm(θtm)Rm0 (Φtm + Et0m)∥∥2 ≤ H2mG2m ∥∥Et0m∥∥2F . (A.18)
We now prove Lemma 1.
Proof. Recall that:
∇mF̂B(Γtm) = ∇mFB(Φtm + Et0m) (A.19) = ∇θmhm(θtm)∇hm(θm)FB(Φ t m + E t0 m). (A.20)
Next we apply Taylor series expansion as in (A.11):
∇mF̂B(Γtm) = ∇θmhm(θtm) ( ∇hm(θm)FB(Φ t m) +R m 0 (Φ t m + E t0 m) )
(A.21)
= ∇mFB(Γtm) +∇θmhm(θtm)Rm0 (Φtm + Et0m) (A.22)
Rearranging and applying expectation and the squared 2-norm, we can bound further:
E ∥∥∥∇mF̂B(Γtm)−∇mFB(Γtm)∥∥∥2 = E ∥∥∇θmhm(θtm)Rm0 (Φtm + Et0m)∥∥2 (A.23)
≤ H2mG2mE ∥∥Et0m∥∥2F (A.24)
= H2mG 2 m ∑ j 6=m E ∥∥ t0j ∥∥2F (A.25)
= H2mG 2 m ∑ j 6=m Et0j (A.26)
where (A.24) follows from Lemma 1’, (A.25) follows from the definition ofEt0m , and (A.26) follows from Definition 1.
Lemma 2. If ηt0 ≤ 14Qmaxm Lm , then under Assumptions 1-5 we can bound the conditional expected squared norm difference of gradients Gt0 and Ĝ t for iterations t0 to t0 +Q− 1 as follows:
t0+Q−1∑ t=t0 Et0 [∥∥∥Ĝt − Gt0∥∥∥2] ≤ 16Q3(ηt0)2 M∑ m=0 L2m ∥∥∇mF (Θt0)∥∥2
+ 16Q3(ηt0)2 M∑ m=0 L2m σ2m B
+ 64Q3 M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F . (A.27)

heading: Proof.
text: Et0 [∥∥∥Ĝt −Gt0∥∥∥2] = M∑
m=0
Et0 [∥∥∥∇mF̂B(Γtm)−∇mFB(Γt0m)∥∥∥2] (A.28)
= M∑ m=0 Et0 [∥∥∥∇mF̂B(Γtm)− F̂B(Γt−1m ) +∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2] (A.29)
≤ (1 + n) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γtm)−∇mF̂B(Γt−1m )∥∥∥2]
+ ( 1 + 1
n ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2] (A.30)
≤ 2 (1 + n) M∑ m=0 Et0 [∥∥∇mFB(Γtm)−∇mFB(Γt−1m )∥∥2]
+ 2 (1 + n) M∑ m=0 Et0 [∥∥∇θmhm(θtm)Rm0 (Φtm + Et0m)−∇θmhm(θt−1m )Rm0 (Φt−1m + Et−1m )∥∥2]
+ ( 1 + 1
n ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2] (A.31)
≤ 2 (1 + n) M∑ m=0 Et0 [∥∥∇mFB(Γtm)−∇mFB(Γt−1m )∥∥2]
+ 8 (1 + n) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2 + ( 1 + 1
n ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2] (A.32)
where (A.30) follows from the fact that (X + Y )2 ≤ (1 + n)X2 + (1 + 1n )Y 2 for some positive n and (A.32) follows from Lemma 1’.
Applying Assumption 1 to the first term in (A.30) we have:
Et0 [∥∥∥Ĝt −Gt0∥∥∥2] ≤ 2 (1 + n) M∑
m=0
L2mEt0 [∥∥Γtm − Γt−1m ∥∥2]
+ 2 ( 1 + 1
n ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 8 (1 + n) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2 (A.33) = 2(ηt0)2 (1 + n)
M∑ m=0 L2mEt0 [∥∥∥∇mF̂B(Γt−1m )∥∥∥2]
+ 2 ( 1 + 1
n ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 8 (1 + n) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2 (A.34) where (A.34) follows from the update rule Γtm = Γ t−1 m − ηt0∇mF̂B(Γt−1m ).
Bounding further:
Et0 [∥∥∥Ĝt −Gt0∥∥∥2] ≤ 2(ηt0)2 (1 + n)
M∑ m=0 L2mEt0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m) +∇mFB(Γt0m)∥∥∥2]
+ ( 1 + 1
n ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 8 (1 + n) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2 (A.35) ≤ 4(ηt0)2 (1 + n)
M∑ m=0 L2mEt0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 4(ηt0)2 (1 + n) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2]
+ ( 1 + 1
n ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 8 (1 + n) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2 (A.36) =
M∑ m=0 ( 4(ηt0)2 (1 + n)L2m + ( 1 + 1 n )) Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 4(ηt0)2 (1 + n) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2]
+ 8 (1 + n) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2 . (A.37)
Let n = Q. We simplify (A.37) further:
Et0 [∥∥∥Ĝt −Gt0∥∥∥2] ≤
M∑ m=0 ( 4(ηt0)2 (1 +Q)L2m + ( 1 + 1 Q )) Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 4(ηt0)2 (1 +Q) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2]
+ 8 (1 +Q) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F . (A.38)
Let ηt0 ≤ 14Qmaxm Lm . We bound (A.38) as follows:
Et0 [∥∥∥Ĝt −Gt0∥∥∥2] ≤ ( (1 +Q)
4Q2 +
( 1 + 1
Q )) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 4(ηt0)2 (1 +Q) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2]
+ 8(1 +Q) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.39) ≤ ( 1
2Q +
( 1 + 1
Q )) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 4(ηt0)2 (1 +Q) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2]
+ 8(1 +Q) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.40) ≤ ( 1 + 2
Q ) M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt−1m )−∇mFB(Γt0m)∥∥∥2]
+ 4(ηt0)2 (1 +Q) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2]
+ 8(1 +Q) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F . (A.41) We define the following notation for simplicity:
At := M∑ m=0 Et0 [∥∥∥∇mF̂B(Γtm)−∇mFB(Γt0m)∥∥∥2] (A.42)
B0 := 4(η t0)2 (1 +Q) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2] (A.43)
B1 := 8(1 +Q) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.44) C := ( 1 + 2
Q
) . (A.45)
Note that we have shown that At ≤ CAt−1 +B0 +B1. Therefore:
At0+1 ≤ CAt0 + (B0 +B1) (A.46) At0+2 ≤ C2At0 + C(B0 +B1) + (B0 +B1) (A.47) At0+3 ≤ C3At0 + C2(B0 +B1) + C(B0 +B1) + (B0 +B1) (A.48)
... (A.49)
At ≤ Ct−t0−1At0 + (B0 +B1) t−t0−2∑ k=0 Ck (A.50)
= Ct−t0−1At0 + (B0 +B1) Ct−t0−1 − 1
C − 1 . (A.51)
We bound the first term in (A.51) by applying Lemma 1:
At0 = M∑ m=0 Et0 [∥∥∥∇mF̂B(Γt0m)−∇mFB(Γt0m)∥∥∥2] (A.52)
≤ M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F . (A.53) Summing over the set of local iterations t0, . . . , t+0 , where t + 0 := t0 +Q− 1:
t+0∑ t=t0 Ct−t0−1At0 = At0 t+0∑ t=t0 Ct−t0−1 (A.54)
= At0 CQ − 1 C − 1
(A.55)
= At0
( 1 + 2Q )Q − 1(
1 + 2Q
) − 1
(A.56)
= QAt0
( 1 + 2Q )Q − 1
2 (A.57)
≤ QAt0 e 2 − 1
2 (A.58)
≤ 4QAt0 (A.59) ≤ 4Q M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F . (A.60) It is left to bound the second term in (A.51) over the set of local iterations t0, . . . , t0 +Q− 1.
t+0∑ t=t0 (B0 +B1) Ct−t0−1 − 1 C − 1 ≤ t+0∑ t=t0 (B0 +B1) Ct−t0−1 − 1 C − 1 (A.61)
= (B0 +B1)
C − 1  t+0∑ t=t0 Ct−t0−1 −Q  (A.62) = (B0 +B1)
C − 1 ( CQ − 1 C − 1 −Q )
(A.63)
= (B0 +B1)( 1 + 2Q ) − 1
 ( 1 + 2Q )Q − 1(
1 + 2Q
) − 1 −Q
 (A.64)
= Q(B0 +B1)
2
Q [( 1 + 2Q )Q − 1 ]
2 −Q
 (A.65)
= Q2(B0 +B1)
2
 ( 1 + 2Q )Q − 1
2 − 1  (A.66) ≤ Q 2(B0 +B1)
2
( e2 − 1 2 − 1 )
(A.67)
≤ 2Q2(B0 +B1) (A.68) (A.69)
Plugging the values for B0 and B1:
t+0∑ t=t0 (B0 +B1) Ct−t0−1 − 1 C − 1 ≤ 8Q2(ηt0)2 (1 +Q) M∑ m=0 L2mEt0 [∥∥∇mFB(Γt0m)∥∥2]
+ 16Q2(1 +Q) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.70)
Applying Assumption 3 and adding in the first term in (A.51):
t+0∑ t=t0 At ≤ 8Q2(ηt0)2 (1 +Q) M∑ m=0 L2m ∥∥∇mF (Θt0)∥∥2
+ 8Q2(ηt0)2 (1 +Q) M∑ m=0 L2m σ2m B
+ 4(4Q2(1 +Q) +Q) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.71) ≤ 16Q3(ηt0)2
M∑ m=0 L2m ∥∥∇mF (Θt0)∥∥2
+ 16Q3(ηt0)2 M∑ m=0 L2m σ2m B
+ 64Q3 M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F . (A.72)

heading: A.1.3 PROOF OF THEOREMS 1 AND 2
text: Let t+0 := t0 +Q− 1. By Assumption 1:
F (Θt + 0 )− F (Θt0) ≤ 〈 ∇F (Θt0),Θt + 0 −Θt0 〉 + L
2 ∥∥∥Θt+0 −Θt0∥∥∥2 (A.73) = − 〈 ∇F (Θt0),
t+0∑ t=t0 ηt0Ĝ t
〉 + L
2 ∥∥∥∥∥∥ t+0∑ t=t0 ηt0Ĝ t ∥∥∥∥∥∥ 2
(A.74)
≤ − t+0∑ t=t0 ηt0 〈 ∇F (Θt0), Ĝ t 〉 + LQ 2 t+0∑ t=t0 (ηt0)2 ∥∥∥Ĝt∥∥∥2 (A.75)
where (A.75) follows from fact that ( ∑N n=1 xn) 2 ≤ N ∑N n=1 x 2 n.
We bound further:
F (Θt + 0 )− F (Θt0) ≤ − t+0∑ t=t0 ηt0 〈 ∇F (Θt0), Ĝ t −Gt0 〉 − t+0∑ t=t0 ηt0 〈 ∇F (Θt0),Gt0 〉
+ LQ
2 t+0∑ t=t0 (ηt0)2 ∥∥∥Ĝt −Gt0 + Gt0∥∥∥2 (A.76)
≤ − t+0∑ t=t0 ηt0 〈 ∇F (Θt0), Ĝ t −Gt0 〉 − t+0∑ t=t0 ηt0 〈 ∇F (Θt0),Gt0 〉
+ LQ t+0∑ t=t0 (ηt0)2 ∥∥∥Ĝt −Gt0∥∥∥2 + LQ t+0∑ t=t0 (ηt0)2 ∥∥Gt0∥∥2 (A.77)
= t+0∑ t=t0 ηt0 〈 −∇F (Θt0),Gt0 −Ĝ t 〉 − t+0∑ t=t0 ηt0 〈 ∇F (Θt0),Gt0 〉
+ LQ t+0∑ t=t0 (ηt0)2 ∥∥∥Ĝt −Gt0∥∥∥2 + LQ t+0∑ t=t0 (ηt0)2 ∥∥Gt0∥∥2 . (A.78)
≤ 1 2 t+0∑ t=t0 ηt0 ∥∥∇F (Θt0)∥∥2
+ 1
2 t+0∑ t=t0 ηt0 ∥∥∥Ĝt −Gt0∥∥∥2 − t+0∑ t=t0 ηt0 〈 ∇F (Θt0),Gt0 〉
+ LQ t+0∑ t=t0 (ηt0)2 ∥∥∥Ĝt −Gt0∥∥∥2 + LQ t+0∑ t=t0 (ηt0)2 ∥∥Gt0∥∥2 (A.79)
where (A.79) follows from the fact that A ·B = 12A 2 + 12B 2 − 12 (A−B) 2.
We apply the expectation Et0 to both sides of (A.79): Et0 [ F (Θt + 0 ) ] − F (Θt0) ≤ −1
2 t+0∑ t=t0 ηt0 ∥∥∇F (Θt0)∥∥2 + 1 2 t+0∑ t=t0 ηt0(1 + LQηt0)Et0 [∥∥∥Ĝt −Gt0∥∥∥2]
+ LQ t+0∑ t=t0 (ηt0)2Et0 [∥∥Gt0∥∥2] (A.80)
≤ −1 2 t+0∑ t=t0 ηt0(1− LQηt0) ∥∥∇F (Θt0)∥∥2
+ 1
2 t+0∑ t=t0 ηt0(1 + LQηt0)Et0 [∥∥∥Ĝt −Gt0∥∥∥2]+ LQ M∑ m=0 σ2m B t+0∑ t=t0 (ηt0)2
(A.81)
= −Q 2 ηt0(1− LQηt0) ∥∥∇F (Θt0)∥∥2 + 1
2 t+0∑ t=t0 ηt0(1 + LQηt0)Et0 [∥∥∥Ĝt −Gt0∥∥∥2]+ LQ2(ηt0)2 M∑ m=0 σ2m B
(A.82)
where (A.80) follows from applying Assumption 2 and noting that Et0 [ Gt0 ]
= ∇F (Θt0), and (A.82) follows from Assumption 3.
Applying Lemma 2 to (A.82):
Et0 [ F (Θt + 0 ) ] − F (Θt0) ≤ −Q
2 ηt0(1− LQηt0) ∥∥∇F (Θt0)∥∥2 + 8Q3(ηt0)3(1 + LQηt0)
M∑ m=0 L2m ∥∥∇mF (Θt0m)∥∥2
+ 8Q3(ηt0)3(1 + LQηt0) M∑ m=0 L2m σ2m B
+ 32Q3ηt0(1 + LQηt0) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F + LQ2(ηt0)2
M∑ m=0 σ2m B
(A.83)
≤ −Q 2 M∑ m=0 ηt0(1− LQηt0 − 16Q2L2m(ηt0)2 − 16Q3L2mL(ηt0)3)) ∥∥∇mF (Θt0)∥∥2
+ (LQ2(ηt0)2 + 8Q3L2m(η t0)3 + 8Q4LL2m(η t0)4) M∑ m=0 σ2m B
+ 32Q3ηt0(1 + LQηt0) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F . (A.84)
Let ηt0 ≤ 116Qmax{L,maxm Lm} . Then we bound (A.84) further:
Et0 [ F (Θt + 0 ) ] − F (Θt0) ≤ −Q
2 M∑ m=0 ηt0(1− 1 16 − 1 16 − 1 162 )) ∥∥∇mF (Θt0)∥∥2
+ (LQ2(ηt0)2 + 8Q3L2m(η t0)3 + 8Q4LL2m(η t0)4) M∑ m=0 σ2m B
+ 16Q3ηt0(1 + LQηt0) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.85) ≤ −Q
2 ηt0 ∥∥∇F (Θt0)∥∥2
+ (LQ2(ηt0)2 + 8Q3L2m(η t0)3 + 8Q4LL2m(η t0)4) M∑ m=0 σ2m B
+ 32Q3ηt0(1 + LQηt0) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.86)
After some rearranging of terms:
ηt0 ∥∥∇F (Θt0)∥∥2 ≤ 2
[ F (Θt0)− Et0 [ F (Θt + 0 ) ]]
Q
+ 2(LQ(ηt0)2 + 8Q2L2m(η t0)3 + 8Q3LL2m(η t0)4) M∑ m=0 σ2m B
+ 64Q2ηt0(1 + LQηt0) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.87) Summing over all communication rounds t0 = 0, . . . , R− 1 and taking total expectation:
R−1∑ t0=0 ηt0E [∥∥∇F (Θt0)∥∥2] ≤ 2 [F (Θ0)− E [F (ΘT )]] Q
+ 2 R−1∑ t0=0 (LQ(ηt0)2 + 8Q2L2m(η t0)3 + 8Q3LL2m(η t0)4) M∑ m=0 σ2m B
+ 64Q2ηt0(1 + LQηt0) M∑ m=0 H2mG 2 m ∥∥Et0m∥∥2F (A.88) ≤ 2 [ F (Θ0)− E [ F (ΘT ) ]] QR
+ 2 R−1∑ t0=0 (QL(ηt0)2 + 8Q2L2m(η t0)3 + 8Q3LL2m(η t0)4) M∑ m=0 σ2m B
+ 64Q2 R−1∑ t0=0 ηt0(1 + LQηt0) M∑ m=0 H2mG 2 mE [∥∥Et0m∥∥2F] . (A.89) Note that:
M∑ m=0 H2mG 2 mE [∥∥Et0m∥∥2F] = M∑ m=0 H2mG 2 m ∑ j 6=m E [∥∥ t0j ∥∥2F] (A.90)
= M∑ m=0 H2mG 2 m ∑ j 6=m Et0j (A.91)
where (A.91) follows from Definition 1.
Plugging this into (A.89)
R−1∑ t0=0 ηt0E [∥∥∇F (Θt0)∥∥2] ≤ 2 [F (Θ0)− E [F (ΘT )]] QR
+ 2 R−1∑ t0=0 (QL(ηt0)2 + 8Q2L2m(η t0)3 + 8Q3LL2m(η t0)4) M∑ m=0 σ2m B
+ 64Q2 R−1∑ t0=0 ηt0(1 + LQηt0) M∑ m=0 H2mG 2 m ∑ j 6=m Et0j . (A.92)
Suppose that ηt0 = η for all communication rounds t0. Then, averaging over R communication rounds, we have:
1
R R−1∑ t0=0 E [∥∥∇F (Θt0)∥∥2] ≤ 2 [F (Θ0)− E [F (ΘT )]] QRη + 2 M∑ m=0 (QLη + 8Q2L2mη 2 + 8Q3LL2mη 3) σ2m B
+ 64Q2
R R−1∑ t0=0 (1 + LQη) M∑ m=0 H2mG 2 m ∑ j 6=m Et0j . (A.93)
≤ 2 [ F (Θ0)− E [ F (ΘT ) ]] QRη + 4 M∑ m=0 QLη σ2m B
+ 68Q2
R R−1∑ t0=0 M∑ m=0 H2mG 2 m ∑ j 6=m Et0j . (A.94)
where (A.94) follows from our assumption that ηt0 ≤ 116Qmax{L,maxm Lm} . This completes the proof of Theorem 1.
We continue our analysis to prove Theorem 2. Starting from (A.92), we bound the left-hand side with the minimum over all iterations:
min t0=0,...,R−1
E [∥∥∇F (Θt0)∥∥2] ≤ 2 [F (Θ0)− Et0 [F (ΘT )]]
Q ∑R−1 t0=0 ηt0
+ 2 ( QL ∑R−1 t0=0
(ηt0)2∑R−1 t0=0 ηt0 + 8Q2L2m
∑R−1 t0=0
(ηt0)3∑R−1 t0=0 ηt0 + 8Q3LL2m
∑R−1 t0=0
(ηt0)4∑R−1 t0=0 ηt0 ) M∑ m=0 σ2m B
+ 64Q2 M∑ m=0 H2mG 2 m
∑R−1 t0=0 ηt0 ∑ j 6=m E
t0 j∑R−1
t0=0 ηt0
+ 64LQ3 M∑ m=0 H2mG 2 m
∑R−1 t0=0 (ηt0)2 ∑ j 6=m E
t0 j∑R−1
t0=0 ηt0
(A.95)
As R → ∞, if ∑R−1 t0=0 ηt0 = ∞, ∑R−1 t0=0 (ηt0)2 < ∞, and ∑R−1 t0=0 ηt0 ∑ j 6=m E t0 j < ∞, then
mint0=0,...,R−1 E [ ‖∇F (Θt0)‖2 ] → 0. This completes the proof of Theorem 2.

heading: A.2 COMMON COMPRESSORS
text: In this section, we calculate the compression error and parameter bounds for uniform scalar quantization, lattice vector quantization and top-k sparsification, as well as discuss implementation details of these compressors in C-VFL.
We first consider a uniform scalar quantizer (Bennett, 1948) with a set of 2q quantization levels, where q 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 quantizer quantizes each individual component of embeddings. The error in each embedding of a batch B in scalar quantization is ≤ Pm∆ 2 12 = Pm (hmax−hmin)2 12 2 −2q where ∆ the size of a quantization bin, Pm is the size of the m-th embedding, hmax and hmin are respectively the maximum and minimum value hm(θtm;x i m) can be for all iterations t, parties m, and x i m. We note that if hmax or hmin are unbounded, then the error is unbounded as well. By Theorem 1, we know that 1 R ∑R−1 t0=0 ∑M m=0 Et0m = O( 1√ T ) to obtain a convergence rate of O( 1√ T
). If we use the same q for all parties and iterations, we can solve for q to find that the value q must be lower bounded by q = Ω(log2(Pm(hmax − hmin)2 √ T )) to reach a convergence rate of O( 1√
T ). For a diminishing
compression error, required by Theorem 2, we let T = t0 in this bound, indicating that q, the number of quantization bins, must increase as training continues.
A vector quantizer creates a set of d-dimensional vectors called a 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 Euclidean distance. A cell in vector quantization is
defined as all points in d-space that quantizes to a single codeword. The volume of these cells are determined 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 of size two, scaled to the unit square, then quantized to the nearest vector by Euclidean distance in the codebook. The error in this vector quantizer is ≤ V Pm24 where V is the volume of a 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 V based on Theorem 1: V = O( 1
Pm √ T ). If a diminishing compression error is required, we can set T = t0 in this bound, indicating that V must decrease at a rate of O( 1
Pm √ t0 ). As the number of iterations increases, the smaller V must be, and thus the more bits that must be communicated.
In top-k sparsification (Lin et al., 2018), when used in distributed SGD algorithms, the k largest magnitude components of the gradient are sent while the rest are set to zero. In the case of embeddings in C-VFL, a large element may be as important as an input to the server model as a small one. We can instead select the k embedding elements to send with the largest magnitude partial derivatives in ∇θmhm(θtm). Since a party m cannot calculate ∇θmhm(θtm) until all parties send their embeddings, party m can use the embedding gradient calculated in the previous iteration, ∇θmhm(θt−1m ). This is an intuitive method, as we assume our gradients are Lipschitz continuous, and thus do not change too rapidly. The error of sparsification is ≤ (1 − kPm )(‖h‖
2)max where (‖h‖2)max is the maximum value of ‖hm(θtm;xim)‖2 for all iterations t, parties m, and xim. Note that if (‖h‖2)max is unbounded, then the error is unbounded. We can calculate a lower bound on k: k = Ω(Pm − Pm(‖h‖2)max √ T
). Note that the larger (‖h‖2)max, the larger k must be. More components must be sent if embedding magnitude is large in order to achieve a convergence rate of O( 1√
T ). When considering a diminishing compression error, we set T = t0, showing that k must
increase over the course of training.

heading: A.3 EXPERIMENTAL DETAILS
text: For our experiments, we used an internal cluster of 40 compute nodes running CentOS 7 each with 2× 20-core 2.5 GHz Intel Xeon Gold 6248 CPUs, 8× NVIDIA Tesla V100 GPUs with 32 GB HBM, and 768 GB of RAM.

heading: A.3.1 MIMIC-III
text: The MIMIC-III dataset can be found at: mimic.physionet.org. The dataset consists of time-series data from ∼60,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 to 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: github.com/YerevaNN/mimic3benchmarks. 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. The new file of interest in our code base is “mimic3models/in hospital mortality/quant.py” which 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 experiments train models to predict for in-hospital mortality. For in-hospital mortality, there are 14,681 training samples, and 3,236 test samples. In our experiments, we use a step size of 0.01, as is standard for training an LSTM on the MIMIC-III dataset.

heading: A.3.2 MODELNET10
text: Details on the ModelNet10 dataset can be found at: modelnet.cs.princeton.edu/. The specific link we downloaded the dataset from is the following Google Drive link: https://drive.google.com/file/d/0B4v2jR3WsindMUE3N2xiLVpyLW8/view. The dataset consists of 3D CAD models of different common objects in the world. For each CAD model, there are 12 views
from different angles saved as PNG files. We only trained our models on the following 10 classes: bathtub, bed, chair, desk, dresser, monitor, night stand, sofa, table, toilet. We used a subset of the data with 1,008 training samples and 918 test samples. In our experiments, we use a step size of 0.001, as is standard for training a CNN on the ModelNet10 dataset.
Our code for learning on the ModelNet10 dataset is in the folder “MVCNN Pytorch” and is an extension of the MVCNN-PyTorch repo: github.com/RBirkeland/MVCNN-PyTorch. The file of interest in our code base is “quant.py” which runs C-VFL. Both our code base and the original are under the MIT License. Details on how to run our experiments can be found in the “README.md”. Each experiment took approximately six hours to run on a node in our cluster.

heading: A.4 ADDITIONAL EXPERIMENTS
text: 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 5, 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 a different quadrant of the image.
In Figure A.1, we plot the test accuracy for the ModelNet10 dataset. The test accuracy is 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.1a shows the test accuracy plotted by epochs. There is very little variation between compressors and no compression here. This leads to a very large benefit for compression when plotting by communication cost, seen in Figure A.1b. In Figure A.1c, we plot the test accuracy of C-VFL using vector quantization for different values of b, the number of bits to represent compressed values. Similar to previous results, lower b tends to improve test accuracy reached with the same amount of communication cost. We can also see that the total cost of communication has increased compared to the case of 4 and 12 parties in Figure 3. This is expected, as there are 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 a single fully-connected layer.
In Figure A.2, we plot the test accuracy for the CIFAR-10 dataset. The test accuracy is fairly low compared to typical baseline accuracies, which is expected, as learning object classification from only a quadrant of a 32 × 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 no 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 as well. In Figure A.2c, we plot the test accuracy of C-VFL using vector quantization for different values of b, the number of bits to represent compressed values. Similar to previous results, lower b tends to improve test accuracy reached with the same amount of communication cost.

heading: A.5 ADDITIONAL PLOTS
text: 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 are the average of five runs and the shaded regions represent the standard deviation.
Figures A.3 and A.4 plot the training loss and test F1-Score for training on the MIMIC-III dataset for different levels of compression. We can see that scalar and vector quantization perform similarly to 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.
Figures A.5 and A.6 plot the test F1-Score for training on the MIMIC-III dataset plotted against the communication cost. The plots in Figure A.5 include all compression techniques for a given level of
compression, while the plots in Figure A.6 include all levels of compression for a given compression technique. We can see that all compressors reach higher F1-scores with lower communication cost than no compression. It is interesting to note that increasing the number of bits per parameter reduces the variability in all compressors.
Figures A.7 and A.8 plot the training loss and test accuracy for training on 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 are available. We can see that scalar quantization has high variability on the ModelNet10 dataset.
Figures A.9 and A.10 plot the test accuracy for training on the ModelNet10 dataset against the communication cost. The plots in Figure A.9 include all compression techniques for a given level of compression, while the plots in Figure A.10 include all levels of compression for a given compression technique. We can see that all compressors reach higher accuracies with lower communication cost than no compression. Scalar quantization generally performs worse than the other compressors on the ModelNet10 dataset. From Figure A.10, we also see that when fewer bits are used in each compressor, higher test accuracies are reached at lower communication costs.

Review summaries:
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.

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. 	 

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.