A Unified Solution for Privacy and Communication Efficiency in Vertical Federated Learning
Authors: Ganyu Wang
Bin Gu
Qingsong Zhang
Xiang Li
Boyu Wang
Charles Ling
Venue: NeurIPS 2023 poster (2023)
Keywords: Vertical Federated Learning
Zeroth Order Optimization
Communication Efficiency
Privacy
TL;DR: Minimal application of ZOO in the most essential parts of VFL enjoys good convergence rate, communication efficiency, and an intrinsic differential privacy guarantee.

Abstract: Vertical Federated Learning (VFL) is a collaborative machine learning paradigm that enables multiple participants to jointly train a model on their private data without sharing it.
To make VFL practical, privacy security and communication efficiency should both be satisfied. Recent research has shown that Zero-Order Optimization (ZOO) in VFL can effectively conceal the internal information of the model without adding costly privacy protective add-ons, making it a promising approach for privacy and efficiency.
However, there are still two key problems that have yet to be resolved. First, the convergence rate of ZOO-based VFL is significantly slower compared to gradient-based VFL, resulting in low efficiency in model training and more communication round, which hinders its application on large neural networks. Second, although ZOO-based VFL has demonstrated resistance to state-of-the-art (SOTA) attacks, its privacy guarantee lacks a theoretical explanation.
To address these challenges, we propose a novel cascaded hybrid optimization approach that employs a zeroth-order (ZO) gradient on the most critical output layer of the clients, with other parts utilizing the first-order (FO) gradient. This approach preserves the privacy protection of ZOO while significantly enhancing convergence.
Moreover, we theoretically prove that applying ZOO to the VFL is equivalent to adding Gaussian Mechanism to the gradient information, which offers an implicit differential privacy guarantee. 
Experimental results demonstrate that our proposed framework achieves similar utility as the Gaussian mechanism under the same privacy budget, while also having significantly lower communication costs compared with SOTA communication-efficient VFL frameworks.

A Unified Solution for Privacy and Communication Efficiency in Vertical Federated Learning
Ganyu Wang
Bin Gu
Western University
Jilin University and MBZUAI
gwang3820uno.ca
j sgubinn@mail... com
Qingsong Zhang Xidian University
Xiang Li
Boyu Wang Western University bwang@osd. uwo. ca
Western University 1 Lixiang418126.. com
gszhang1995@gmail.comm com
Charles X. Ling Western University charles ling@uwo.ca
Abstract
Vertical Federated Learning (VFL) is collaborative machine learning paradigm that enables multiple participants to jointly train a model on their private data without sharing it. To make VFL practical, privacy security and communication efficiency should both be satisfied. Recent research has shown that Zero-Order Optimization (ZOO) in VFL can effectively conceal the internal information of the model without adding costly privacy protective add-ons, making it promising approach for privacy and efficiency. However, there still two key problems that have yet to be resolved. First, the convergence rate of ZOO-based VFL is signifi- cantly slower compared to gradient-based VFL, resulting low efficiency in model training and more communication round, which hinders its application on large neural networks. Second, although ZOO-based VFL has demonstrated resistance to state-of-the-an art (SOTA) attacks, its privacy guarantee lacks a theoretical explana- tion. To address these challenges, we propose novel cascaded hybrid optimization approach that employs zeroth-order (ZO) gradient on the most critical output layer of the clients, with other parts utilizing the first-order (FO) gradient. This approach preserves the privacy protection of ZOO while significantly enhancing convergence. Moreover, we theoretically prove that applying ZOO to the VFL equivalent to adding Gaussian Mechanism to the gradient information, which offers an implicit differential privacy guarantee. Experimental results demonstrate that our proposed framework achieves similar utility as the Gaussian mechanism under the same privacy budget, while also having significantly lower communication costs compared with SOTA communication-cffiicee VFL frameworks.
Introduction
is an emerging technique that has raised wide attention recently. It has become of the most important distributed learning frameworks for enabling multiple data holders to train a model collaboratiely without sharing their local privacy data explicitly.
Federated Learning 30 22
23
18
31
Co-corresponding authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Server
FD
120
1FO EFal
Embedding
Partal derivalive
Enbeddingg
20 info mation
Embedding
20 nformation
[ K200
:::
[-]
[::3] (,,)))
::: Aet
Piiayy
Piaay sRore
of lnaeoy
Citents
Faol
FO
(a) FOO-based VFL
(b) ZOO-based VFL
(e) VFL-GZOFO (Ours)
Figure I: Comparing the Asyn-VEL Frameworks
Our research focuses VFL., where each client possesses all the data points, but only a intersecting subset of the features (vertically distributed). In VFL, all participants collaborate train a single global model. The client trains feature extraction model that maps its local data sample to embeddings, and the server collects the embeddings from all clients to make
prediction 21 6
39 T6
efficiency is crucial for practical VFL implementations. One common approach achieve this is starting with basic VFL [5 6 28 and subsequently applying privacy protection techniques, such as Secure Multiparty Computation (SMC) g Differential Privacy (DP) 32 36 and Homomorphic Encryption (HE) [36 32 to
Ensuring both privacy and
protect privacy. However, the addition of these protection techniques often increases computation- communication costs. To avoid these costly protective add-ons, research attention has turned to Zero-Order Optimization (ZOO). Literature reports that ZOO-based VFL is able to conceal the internal information of the model (gradient/model parameter) making the SOTA privacy inference attack ineffective [4]. This finding highlights the potential of ZOO for efficient and secure VFL.
However, two critical problems remained. First, the convergence rate of ZOO based VFL is signifi- cantly slower [41] compared to VFL frameworks optimized with gradient, resulting in a high number of communication rounds and increased communication costs. Furthermore, the convergence rate is negatively correlated to the size of the parameters optimized using ZOO [4] 27 12], which hinders the application of ZOO-based VFL large neural networks. Second, although ZO-based VFL has demonstrated resistance to SOTA attacks, its privacy guarantee has not been theoretically explained.
To solve the first problem, we reevaluate the advantages and disadvantages of applying first-order (FO) or zero-order (ZO) gradient methods for each component of the VFL, and find an optimal balance between efficiency and privacy protection. This analysis leads to novel cascaded hybrid optimization framework that efficiently solves the convergence problems while fully preserving privacy protection. Specifically, our proposed framework (VFL-CZOFO) utilizes the ZO gradient for optimizing the most critical output layer of the clients, while other parts are optimized with the FO gradien To address the second problem, theoretically prove that applying ZOO VFL is equivalent to adding Gaussian Mechanism to the gradient information and can provide a corresponding intrinsic (c, 8D-DP guarantee.
For clear illustration, a schematic diagram of our proposed framework presented in Figure (c). The advantage of our framework is two-fold. First, it greatly alleviates the slow convergence problem of ZOO-based VFL (Figure b), where our framework's 's convergence is solely limited by the output size of the clients, rather than the parameter size of the entire model. Second, compared with the FoO-based VFL (Figure a),, the connection layer our framework used ZOO, allowing the backward messages be solely losses, thus inheriting the privacy protection of the ZOO-based VFL.
The primary innovations of our paper are as follows: Our framework employs a novel cascaded hybrid optimization method, in which different optimization methods are applied to different layers of the global model in each iteration, which significantly improves the convergence rate of ZOO-based VFL while preserving privacy. To the best of our knowledge, no prior research in VFL has proposed a similar method that cascaded a hybrid optimization and exploits its advantages. 2) We provide
Additionnlly, apply compression further reduce the communication of framework.

---

a theoretical explanation of the intrinsic privacy guarantee of ZOO, based on (c, 6)-DP, which is fundamentally different from the common DP mechanism, where noise is added items afterward.
In summary, the contributions of our paper are:
We propose the cascade hybrid optimization method in VFL, where ZOO is applied to the most essential part of the VFL, which provides intrinsic privacy protection and significantly improves the convergence rate compared with the ZOO-based VFL.
Theoretically analysis shows: the intrinsic (e, o)-differential privacy guarantee provided by ZOO within our framework, 2) the convergence of our framework and its superiority compared with the ZOO-based VFL, 3) the compatibility of communication compression for both forward and backward messages within our framework.
Extensive experiments show: 1) with the same (e, 8)differrenti privacy guarantee, method can achieve a similar utility as the Gaussian Mechanism, 2) Our method significantly reduces the communication cost compared with the SOTA communication-efficceee VFL.
2 A Detailed Comparison with SOTA VFL Frameworks
Table presents comparison of our VFL framework with other SOTA VFL frameworks, including "split- 34 "compressed- "FLL [5] "Syn-ZO0- VFL "VAFL" 6 "ZOO-VFL" [4]] In the table, Asyn/Syn are abbreviations for asynchronous and synchronous. The T is the iteration of the model. d and d, represent the size of the entire global model's parameter and the size of the client's output embeddings, respectively. The "communication size per iteration" column summarizes the number of elements in the original messages before any post-pni post-processing, such as compression. the batch size. is the sampling times for multiple point estimation of ZOO [27]
Compared to the FOO-based VFL framework leverages the intrinsic privacy protection of ZOO, which is a result of its stochastic characteristics and the concealment of internal information. Second, ZOO to reduce the communication cost from the server to the client where the backward message consists of merely q elements, which is typically significantly smaller than the FO-based VFL with d, B elements. The key difference between our framework and the FOO-based framework is that our approach reduces communication costs while simultaneously ensuring privacy protection. In contrast, FOO-based VFL typically shares internal information (parameters/gradient
6 our framework has distinct advantages. First, our
leverage the advantage of
6 5 and then applies
for extra privacy protection mechanism 36 32
Compared with the ZOO-based VFL [41) this framework and ours both leverage the privacy protec- tion of 7OO in VFL. However, Z0O-based VFL suffers from a slow convergence rate of Od/ /T) which constrained by the global model parameter size This hinders its effectiveness when dealing with "larger" networks containing millions of parameters, causing higher communication costs due increased communication rounds. To address this issue, we applied ZOO the crucial connection layer between the server and the client. By doing so, we maintained the privacy protection offered by ZOO while significantly mitigating the slow convergence problem, reducing the constraint from the entire global model size d to merely the output size of the clients d,.
Table 1: Compare with Different VFL. Algorithm
Comm, Size per Iter. (Forward Backward)
Framework
Privacy Asyn/Syn
Optimization
Convergence O(-)
Split learning
34 Compressed-VHH
Syn
FO
1/VT
d, d, B
Syn
FO
1/VT
dy B dy B
VAFL 6
X
Asyn
FO
1/VT
d, dg B
Syn-Z00-Vi VFI
Syn
Z0
d/VT
2d, +
Z00-VFL 41
Asyn
ZO
d/
2d, B +
VFL-CZOFO (Ours)
Asyn
ZO&FO
dn/VT
d, B +
This is the synchronous version Z00 VFL, the algorithm is in Appendix E.1

---

3 Method
Problem Definition In the framework,, there is server and M clientsf The server holds the label Yi for each sample i E [m]. (In _ (1,22..m)) n)), while each client holds a non-intersecting feature set for all the samples. Specifically, the features for sample on client m are denoted as Tmm.i- Client m's model, ht (Wm; Zm, is parameterized by tim and takes local feature Im,i as input, outputting the embedding. The server inputs the embeddings from all clients into its own model, which is parameterized by Wi,, and then calculates the losses for updating the parameters. The VFL framework can be viewed as solving a finite-sum problem in composite form:
f(Wo, w: xY 1
[(wo, hi. (. with hm, = hm (Wmi Fmaa) Vm E [M]
where w- [wi, war] denotes the parameter for all clients, X denotes the entire feature set across all clients, and y denotes the labels for all samples. For notation brevity, we define the outputs from all clients as Φb (w) = [/i (w1;
J.M (WM; (aM, = [M,,...... h..a]. Therefore, the loss for the i-th sample can be represented as fi T). L( ; is the loss function.
Cascaded and Minimal Application of ZOO on the Connection Layer Applying ZOO on VFL resolves the privacy leakage issue from the gradient [41] but simply applying ZOO to the entire VFL has a slow convergence problem, leading high number of communication rounds. Specifically, the major problem of ZOO is that with more dimensions on the gradient that need to be estimated, more variance will be introduced the estimation of the gradient (27 This is especially problematic for machine learning scenarios where even relatively small models may have millions of parameters. To address the slow convergence problem of ZOO-based VFL. we precisely apply ZOO to the client's output layer, while the rest of the model utilizes the FO gradient. This approach significantly improves the convergence of the ZOO-based VFL, since only small portion of the entire model uses ZOO.
ZOO [2] estimates the gradient of function by sampling a random perturbation within the function's 's domain of definition and evaluating its shift the value domain. To estimate the partial derivative with respect to the output layer of the client's 's model, we apply the average random gradient estimation Aavg-RanGrradEst) 27 25
which utilizes i.i.d. samples {
on the objective function: (m/
V Rem J's (Woy h1.s"" .MMa)
o(dRmn)
Eis(mmm Mm (nnd S' (hm, Mum
q
qpm
where Ji (hmus + (m,) is the abbreviation for fi (wo, hy.i. Bmm.i Jmn Mmnii I.M.;). drum is the size of the output layer of client m. ((dh... ) is dimension-dependenn factor (26) related the choice of the distribution p of the random vector u/m,5. If p is the multivariate uniform distribution ((, 1)) on unit sphere centered at with radius 1, then ((dn... ) = dr... If p the multivariate normal distribution N (00 I), then ((dh...) = 1. is the sampling times. The clients cannot calculate 5/ by themselves because the loss function f((-) is held by the server, therefore the server has to 7
send the &% back to the clients To implement multiple-poii estimation, the server must transmit multiple distinct values of & to the client, with the number of values sent equaling the number of sampling points used in the wgg-RandGradEst.
The theoretical difficulty in analyzing our framework is that different optimization methods are cascaded within single model. Unlike most VFL research [34] 5) 28 6 41 which updates the global model with a unified optimization method, e.g. fi (wm) (VAFL 6 or the V (Wm) (ZO0- VFL [41)), we apply a cascaded hybrid gradient via chain rule, i.e. Vin. fs (hm,s) V Ww hm,i where Wnn. fo (Nmm,)) the stochastic gradient estimator of the partial derivative w.r.t. the output layer of the client, and V w... hm (wm) is the local gradient of the client.
'Server and clients are the roles in the framework, in practice. one participant may take more than one role. Although sample was used throughout this paper, it is easy to generalize our approach to
B. 'The server and the client also need to share an identical random sequence umn.. but this can be achieved by sharing one random seed at the beginning of the training,
the sample ID as the random seed.

---

Compress the Communication Furthermore, we demonstrate that compression is compatible with our approach, and can be applied all communications in the framework, including the forward message [5] and the backward message R5 We define the compressor of the client as C. (-). and the compressor of the server as Co(.). each communication round, the client m sends compressed embeddings instead of the raw message to the server, and the server replies with the compressed messages. We apply the uniform scale compressor [2] in the experiment. However, other compression schemes such Top-K (24), sign-SGD 4 and lattice quantization [40] can also be applied to the different parts of our framework to further reduce the message size.
The theoretical challenge in proving the convergence with compression lies in that two errors (forward and backward) are introduced in the analysis. The first error affects the embeddings sent from the client to the server, where the error influences the server's 's model input, creating uncertainty in the loss value and gradients for updating the parameter. We bound this error by imposing assumptions on the curvature of the loss function, i.e. an upper bound for the norm of the Hessian matrix. The second error affects the message sent from the server to the clients, which then updates using the hybrid gradient with compression error. As result, there are three different sources of uncertainty in the clients' parameter update: the two mentioned above, as well as the error caused by ZOO.
Algorithm In this section, propose asynchronous VFI with ZOO on the connection layer and compression on the communication messages. Starting with the client, which randomly selects a sample and sends its local model output to the server. Receiving the forward message from the client m, the server calculates the _, with wagdddnGraddst (Eq. 2 and group on, with j 1,2,- :9
into vector Am, The server compresses Am, and sends it back the client. Then the server and client update their local model with the "gradient".
Algorithm VFL-CZOFO
Input:
Learning rate Tm, smoothing parameter Um. compressor C. for {0, 1, M.. Output: Parameter Wm for m E {0, ......
0: Initialize model parameter Wm.. for all participants (0, 1, ..
1: while not convergent do
2: when a client is activated, do:
3: Randomly select sample Tm.i
4: Compute and send (hm (m.))
server
5:
Receive Ca(Am.) from the server (in a listen manner)
6:
Compute Vnm.ii (wo, F2) via Avg- wyg-RandGradEss (Eq.
7:
Compute V wm him (Wmi Im,i) via backpropagation.
8:
Compute Um ft (wo, 42)) V Vmm hmmk
9:
Update Wm t- Wm - Tm
when server receives from client m, do: Compute 5',, and group into Am.s
11:
12:
Send Co (Am,)) to the client m
Compute up = V Wa (wo. 4)). (FOO)
14:
Update wo <- wo 7000
end while
Security Analysis
Threat Model We discuss privacy under two scenarios: "honest-but-curious" and "honest-bur colluded".. In both scenarios, all participants are assumed to follow the protocol and perform their assigned tasks. Under the "honest-but-curion but-curious" scenario, curious client attempts obtain private information from other participants using the information they have received. In the "honest- but- colluded" scenario, some participants collude obtain private information from other participants.
The attacker in this scenario can access all information and messages from the colluding participants. In the the "honest-but-curious scenario. This is because the attacker can acquire more information from other participants when colluding, therefore increasing their ability to infer sensitive data.
scenario, the attacker's 's capability is either equal to or stronger than in
A schematic graph and illustration of asynchronous VFL is in the Appendix section D.I
5

---

Theorem 4.1. Differential Privacy Guarantee of Sharing the ZO Gradient: Under the "honest- but-colluded" threat model where the attacker can access all information of all clients through the entire training process, including the client's 8 dataset, model, and the 70 gradient received from the server. Under algorithm [] with being sufficiently large, Ç being the maximum 22-norm of the partial gradient w.r.t. any client's s output through the entire training. If the following condition holds:
25 2
tr( m.
(3)
gdnT
N.
1=0
can derive that sharing the stochastic gradient estimation from the server ensures (2, 5)-P) for all e, 6, 8' O, where (n(18'()) + Tele" -1) 8 T6 + 8'.
Proof sketch: The proof can be found in Appendix T Firstly, we establish that each client's update can be modeled with ideal sequence, where the unbiased parameter is updated with the gradient of the smoothed loss function fu, (wa, $b,) = [f (wo. $(w)) ]) + jmm). Since
in Eq. i is an average of q independently and identically distributed samples from fi(-). applying the central limit theorem, the estimated gradient is normally distributed for sufficiently large We can
then apply the differential privacy guarantee for the Gaussian Mechanism the estimated gradient. Finally, the accumulated privacy guarantee is derived from the advanced composition theorem.
Remark 4.2. This theorem tells that under the worse case where a strong attacker has obtained all of the ZO information Am.; from all client m E [M]. of all sample E [N], during the entire training process E [T]. the attacker cannot differ a single data point in the dataset, with (2, 8)-DP guarantee. Remark 4.3. Since the 70 gradient is shared from the server to clients, this theorem mainly provides privacy guarantee for the label on the server
Remark 4.4. For weaker attacker, where the attacker can only access the information from fewer the privacy guarantee either
clients "hhonest-ut--oolludddd) or only one client remains the same or is strengthened.
we provided a detailed discussion of the privacy protection of our approach at the framework level. plus a discussion on the SOTA inference attacks under "honest-but- curious" [0 33 45
Additionally, in Appendix C.2
45
and
[0 45 29 38 threat model.
5 Convergence Analysis
Assumption 5.1. The formal definition and detailed discussion of the assumptions are in Appendix B
We assume that there is a feasible optimal solution for f(-). fi (-) is L-Lipschitz continuous, fi (-) has an unbiased gradient, bounded Hessian H,, and bounded block-coordinate gradient G The activation of the clients is independent, and the client has uniformly bounded delay to solve the problem with algorithm
Theorem 5.2. Under assumption 5.1 holds.
the following inequality
4p.E (1--S*)
E
V
(wg
w²
2mp. Lu (4d. G. + P. + 20
TT
1=0
p.pp. T G. (Ad. G? 1. + 2T2TT)
I. ,. G? + Ep, H (6 + 16G + 17Tp.G?
where L. max {L, Lo, Lmn. 710 tm 17, P-
1 minm Pms Pxx maxm {pm) d.
maxm {dh... J. G. = maxm {Go, Gm H. = maxm {Ho, Hm E and are the upper bound for the square of the norm of the forward and backward compression error respectively. T is the total number of iterations (communication rounds).
Design the compression make E O (0(#)
Remark 5.3. If we choose 1 V and μl VT
and r = 0 (+) we can derive:
H B | (w6. w =2)l1== (
dr

---

where dn max (dr... } is the maximum output layer size of the clients.
Remark 5.4. This theorem proves that we significantly relieve the slow convergence problem of Z0O-based VFL 41 from O
O
VT
6 Experiment
We conducted a systematic experiment on the SOTA and baseline VFL and our proposed framework. The primary objective of our study was empirically validate the security measures of our approach and demonstrate its capability in reducing communication overhead. Furthermore, we conducted an ablation study to quantify the contributions of each component toward improving communication efficiency. Due to space limitations, extra experiment details, the CIFAR-10 experiments, extra experiments on less common datasets, and extra experiments on other aspects of our framework have been placed in appendix [ The source code for this project is available at the following URL: https:///g thub. com/ /anyaaaang/VLLLLL..a /VFF-CZOFO
6.1 Experiment Setups
The datasets were vertically partitioned among all participants in our experiments. Each client held portion of the features of each sample, while the server held the corresponding labels. Both the server and the client kept the sample IDs during training. We utilized two datasets in our main experiments: MNIST (20) and CIFAR- 10 [19]. For both datasets, we employed two clients in our experiments, with each client being responsible for half of the image R the respective dataset. Therefore, we denoted these datasets as dist-MNIST and dist-CIFAR-ID 10.
Datasets
Models In our dist-MNIST experiment, we implemented a multilayer perception (MLP). Each client utilized a one-layer Fully Connected Layer (FCL), with an imput size equal to the flattened local data input size, and an output size of 64. The server employed two-layer FCL. The first layer concatenated all the outputs from all clients and produced embeddings with 128 neurons. The second layer outputs 10 neurons for prediction. ReLU [1] was used as the activation function for the server and clients. Practically, the server kept a table the outputs from all clients for all the samples,
ie. $ = [hi A- -i: ;I1)).)........................) W'r t-ThM was maintained by the server. The server updated the
corresponding value in the table when it received hm (wm ---mm Fmm.i from client m during each communication round. The clients' outputs from the table were then used for prediction. Regarding the Mist-CIFAR-II 10 dataset, each client padded its half-image to full size and trained a ResNet- 18 [15] The server then summed the outputs from all the clients.
Frameworks for Comparison We compare our framework with other SOTA VFL frameworks including "split-learning" [34]. "compressed-Ve VFL"" []] "Syn-VFL-ZO P "VAFL" 66. "Z00- VFL" " 41.. All frameworks utilized identical base models and training procedures. While some frameworks also introduced alternative VFL settings, e.g. server and clients both processing the labels, we only focus on the VFL setting where the server stores the labels and multiple clients possess non-intersecting features.
Training Procedures For the experiment applying the split MLP model on dist-MNIST, a batch size of 64 was utilized, and the model was trained for 100 epochs. For the experiment applying the ResNet-18 on dist-CIFAR-10 10, batch size of 128 was used, and the model was trained for 50 epochs. The learning rate 77 was chosen from 10.1, 0.01, 0.001...... and μ for ZOO was cho- sen from [1, 0.1, 0.001, 0.0001. ... We use a uniform scale compressor ( on the forward and backward messages with different compression bits [8, 4, 2, 1]. The number of sampling q used for Avg-RandGradEss in the dist-MNIST experiment was set [10, 100), while in the dist-CIFAR-ID 10 experiment, was set to either [100, 500, 1000). The sampling distribution is (S((0, 1)). We used vanilla SGD with fixed learning rate for all VFL frameworks to ensure a fair comparison. The reported test accuracy values in the tables have been obtained from five independent runs.
$ Details of the feature splitting can he found in Appendix E.1 9This is the synchronous version of ZOO- VFL, the algorithm is in Appendix E.1
7

---

Table 2: Sampling Times of Avg- RandGradEst and the Corresponding Differential Privacy Guarantee
4
x²
6
5
10
1.61
20.1
10
2.8 x 10
10
85.9
9.4 x 10
100
0.15
7.3
10
3.3 x 10-3
10-
93.6
9.4 x 10
6.2
Evaluation on the Privacy Protection
In this part, evaluate the privacy protection of our method and Gaussian Mechanism. The major difference between the ZOO and Gaussian Mechanism in DP is that the variance of the stochastic gradient estimation (2O0) is intrinsically controlled by the hyper- parameter of the ZOO and the characteristic of the objective function, while in the Gaussian Mechanism, the variance is parameter that directly controls the magnitude of the noise added.
0.6
0.4
Gutt $1.5
0.2
Gaussan 85.0
We obtain the DP guarantee w.r.t. the sampling times of ZOO in the dist-MNIST experiment and report the result in Table We estimate
10
25
30
Epoch
Figure 2: The Utility Compar- ing with the VAFL with Gaus- sian Mechanism
o² by freezing the model and repeatedly applying Eq 2 100 times, then calculating the variance of the estimated gradients. We obtain the maximum gradient norm Ç by recording the norm throughout the entire training process [T0 We set 8 10 and calculate based on the given sampling times q. The iteration 7' was set to the total iteration of 50 epochs, which is 93800.
In the second part, we compared the utility of our framework with the VAFL. ( using the Gaussian Mechanism and gradient clipping [ on the partial derivative w.r.. the client's 's output with the corresponding (c, DD.. We set the gradient norm clipping bound to 0.1 And plotted the training accuracy for each epoch Figure 2 As illustrated the figure, our scheme exhibits comparable utility to VAFL with the same privacy guarantee.
6.3 Evaluation of Training Efficiency and Communication Cost
this part, we compare our framework with SOTA VFL in the effectiveness of training and communication efficiency. We apply the best tuning for all other frameworks with respect to test accuracy and communication efficiency. (The experiment for dist-CIFAR-10 is in Appendix E.3
CATL Syn-ZOOV
Figure (a) demonstrates that our VFL-CZOFO frame- work has the fastest convergence rate comparable to VAFL, demonstrating the superiority of our cascade hybrid opti- mization method. It is worth noting that the pure-ZO0- based VFI. suffers from a slower convergence compared other frameworks, even with an MIP model. Figure 3 (b) plots the total communication cost against the training accuracy, where the crosses indicate the point where the curve reaches 95% training accuracy for MNIST. It shows that our VFL-CZOFO framework achieves the same level of convergence with much lower communication costs.
VML
Boo
MNIST by epochs
CUTL
Table report the important statistic about the training. As shown in the table, our framework significantly outper- forms other communication-effcee. frameworks in terms of communication cost.
Z00VT,
Donmentulbe
(b) MNIST by comm. cost
Figure 3: Compare with other VFL
Frameworks
Alternatively, one can also apply gradient clipping(i] to get better privacy guarantee by bounding C. however, want to focus the intrinsic privacy method, therefore only record the maximum norm.

---

Table 3: Evaluating the Test Accuracy and the Comm. Cost
Privacy
Test Accuracy
Cost(603))
Cost (80%)
Cost(90%%
Cost (95%)
Cost (total)
Split learning 14
X
98.03 + 0.07
175 MB
234 MB
937 MB
1758 MB
5859 MB
Compressed- VTL 5
98.17 1: 0.13
109 MB
330 MB
440 MB
1099 MB
3663 MB
VAFL 6
97.36 0.14
123 MB
184 MB
307 MB
1106 MB
6144 MB
VAFL D
95.81 + 0,20
123 MB
184 MB
799 MB
1413 MB
6144 MB
Syn-Z00-VFF
84.51 0.72
1406 MB
2520 MB
ZOO-VFI. 41
85.62 0.45
860
1300 MB
Ours
95.00 ::000::00 0.21
16 MB
24 MB
39 MB
205 MB
790 MB
6.4
Ablation Study
Minimal Zeroth-Order Optimization In this section, evaluate the impact of different ZOO parameters on convergence and communication costs, We did not apply compression in this section. We plot the training curve against epochs in Figure (a), and against the logarithm base 10 of the total backward message size in Figure (b). Table 4 reports the test accuracy and communication costs, (The experiment for Dist-CIFAR- 10 can be found in Appendix E.3.2 with a similar conclusion.)
Sigureeillustrattee how increasing the number of sampling q can enhance the convergence of our proposed method. When q is set 100, the training curve of our method closely matches that of the VAFL method. Notably, the use ZOO in VFI. results in a significant reduction in communication cost, reducing the backward cost by a factor of 40 compared to VAFL.
1.0
33
Table 4: Ablation Study on ZOO
66
70 Type
Test Accuracy
Backward Cost
FendSres-100
FO
97.36 = 0.14
3073 MB
0.2
Rendtana
AvgRand-100
95.30 = 0.25
75 MB
AvgRand-10
93,33 + 0.55
7.5
Epo07
of the lotal techner maxagg sies in
AvgRand-1
79.66 1 0.96
0.75 MB
(a) MNIST by epochs
(b) MNIST by comm. cost
Figure 4: Ablation Study on ZOO
Compression of the Communication In this section, we investigate the impact of compression on convergence and communication costs using Avg-RandGradFist with 100 samplings. We evaluate different compression schemes on either the forward (F) or backward (B) message. Figure presents the training curve plotted against the epoch and the log10 of the communication cost of the message with compression. Table 5 displays the test accuracy and the total cost at the end of the 100-epoch training period. (corresponding dist-CIFAR-I0 10 experiment can be found in Appendix E.3.2
The results show that increasing the compression rate reduces communication costs but leads to decline in test accuracy. Notably, even when compressing the gradient information to 2 bits, there is no significant decrease in test accuracy, and the message size is significantly reduced to 5.4 MB. Hence, a trade-off can be identified in practical application to achieve a balance point.
Table 5: Ablation Study on Compression
03
Compression Type
Test Accuracy
Mcssage Cost
No Compression
95.30 + 0.25
3073 MB
bi
F-8 bits
95.02 0.17
769
F-4 bits
93.35 0.23
386 MB
F-2 bits
79.10 0.41
194 MB
2:10
F-1 bit
30.20 0.45
96 MB
MNIST by forward cost (b) MNIST by backward
B-8 hits
94.58 0.21
19 MB
cost
B-4 bits
94.50 0.10
10 MB
B-2 hits
94.16 0.16
5.4 MB
Figure 5: Ablation Study on Compression
B-1 bit
90.67 0.22
3.1 MB

---

7 Limitation
While the utilization of improves communication efficiency and security, it comes at the expense of increased computational costs for the server. Specifically, the server needs to perform g extra forward propagations on its local model compared other FOO-based VFL methods. more comprehensive analysis and supplementary experiments can be found in Appendix/E.2 However, it important to note that the server typically has higher computational capabilities, which makes the associated costs manageable and acceptable.
8 Conclusion
We propose a solution in VFL that improves communication efficiency and privacy simultaneossly. Our method has been theoretically proven to outperform 400-based VFL in terms of convergence, while also providing proof of the intrinsic differential privacy guarantees. Through our experiments, demonstrate that method substantially reduces the communication cost of VFL in comparison to the state-of-the-ar communication-effiice utility VFL models that offer the same level of privacy guarantee.
VFL. Furthermore, our method achieves comparable
Acknowledgments and Disclosure of Funding
This work has been supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), Discovery Grants program. Bin Gu was partially supported by the National Natural Science Foundation of China under Grant 62076138.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Tlya Mironow, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] William Ralph Bennett. Spectra of quantized signals. The Bell System Technical Journal, 27(3):446 472, 1948.
Albert Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. thcoretical and empirical comparison of gradient approximations derivative-free optimization. Foundations of Computational Mathematics, 22(2):507-55) 560, 2022.
[4] Jeremy Bernstein, Yu- Xi-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560-569. PMLR, 2018.
[5] Timothy J Castiglia, Anirban Das, Shiqiang Wang, and Stacy Patterson. Compressed-vit vit: Communication- efficient lcarning with vertically partitioned data. In International Conference Machine Learning, pages 2738-2766. PMLR, 2022.
[6] Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. Vaft: method of vertical asynchronous federated lcarning. arXiv preprint (rXiv:2077.0608) 2020.
[7] Cynthia Dwork. Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trendse Theoretical Computer Science, 9(3 (13-4))211-2 4):211-407, 2014.
[8] Wenjing Fang, Derun Zhao, Jin Tan, Chaochao Chen, Chaofan Yu, Li Wang, Lei Wang, Jun Zhou, and Benyu Zhang. Large-scale secure xgb vertical federated learning. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 443 452, 2021.
[9] Matt Fredrikson. Somesh Jha. and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermcasures. Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1322-1333, 2015.
[10] Chong Fu, Xuhong Zhang, Shouling Ji, Jinyin Chen, Jingzheng Wu. Shanqing Guo, Jun Zhou, Alex X Liu, and Ting Wang. Label inference attacks against vertical federated learning. In 31st USENIX Security Symposium (USENIX Security 22), Boston, MA, 2022.
10

---

[11] Kunihiko Fukushima. Cognitron: A self-organizing multilayered neural network. Biological cybernetics. 20(3-4):111-136, 1975.
[12] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zedeth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[13] Bin Gu, Zhiyuan Dang, Xiang Li, and Heng Huang. Federated doubly stochastic kernel learning for vertically partitioned data. In Proceedings the 26th SIGKDD international conference knowledge discovery & data mining, pages 2483 2293,,2933222 2020.
[14] Bin Gu, An Xu, Zhouyuan Huo, Cheng Deng, and Heng Huang. Privacy-preserving asynchronous vertical federated learning algorithms for multiparty collaborative learning. IEÉE transactions on neural networks and learning systems, 2021.
[15] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[16] Yaochen Hu, Di Niu, Jianming Yang, and Shengping Zhou. Fdml: collaborative machine learning framework for distributed features. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2232-2240, 2019.
[17] Xiao Jin, Pin-Yu Chen, Chia-Yi Hsu, Chia-Mu Yu, and Tianyi Chen. Cafe: Catastrophic data leakage in vertical federated learning. Advances in Neural Information Processing Systems, 34:994-1006, 2021.
[18] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Schastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national Conference on Machine Learning, pages 5132-5143, PMLR, 2020.
[19] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[20] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available:
2. 2010.
[21] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 60, 2020.
[22] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith, Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020.
[23] Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. FedBN: Federated learning on non-lID features via local batch normalization. In International Conference on Learning Representations, 2021.
[24] Yujun Lin, Song Han, Huizi Mao, Yu Wang. and William Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.018 2017.
[25] Sijia Liu, Jie Chen, Pin-Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In International Conference on Artificial Intelligence and Statistics, pages 288-297. PMLR, 2018
[26] Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O Hero III, and Pramod K Varshney. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43-54, 2020.
[27] Sijia Liu, Bhavya Kailkhura, Pin-Yo Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018
[28] Yang Liu, Yan Kang, Liping Li. Xinwei Zhang, Yong Cheng, Tianjian Chen, Mingyi Hong, and Qiang Yang. communication efficient vertical federated learning framework. Scanning Electron Microse Meet at, 2019.
[29] Xinjian Luo. Yuncheng Wu, Xiaokui Xiao, and Beng Chin Ooi. Feature inference attack on model predictions in vertical federated learning. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 181-192. IEEE, 2021.
[30] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication-eflin learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273- 1282. PMLR, 2017.

---

[31] Konstantia Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead communication acceleration! finally! In International Conference on Machine Learning, pages 15750-13769. PMLR, 2022.
[32] Thilina Ranbaduge and Ming Ding. Differentially private vertical federated learning. arXiv preprint arXiv:2211.06782. 2022.
[33] Jiankai Sun, Xin Yang. Yuanshun Yao, and Chong Wang. Label leakage and protection from forward embedding vertical federated learning. arXiv preprint arXiv:2203.0144 2022.
[34] Praneeth Vepakomma, Otkrist Cupta, Tristan Swedish, and Ramesh Raskar. Split learning for health: Distributed deep learning without sharing raw patient data, arXiv preprint arXiv:1812.0056 2018.
[35] Yujia Wang, Lu Lin, and Jinghui Chen. Communication--fficieenn adaptive federated learning. arXiv preprint arXiv:2205.027 022119 2022.
[36] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard Н Yang, Farhad Farokhi, Shi Jin. Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-3469, 2020.
[37] Kang Wei, Jun Li, Chuan Ma. Ming Ding, Sha Wei, Fan Wu, Guihai Chen, and Thilina Ranbaduge. Vertical federated learning: Challenges, methodologies and experiments. arXiv preprint wxXiv2222.043300 2022.
[38] Haiqin Weng, Juntao Zhang, Feng Xue, Tao Wei, Shouling Ji, and Zhiyuan Zong. Privacy leakage of real-world vertical federated learning. arXiv preprint arXiv:201 2020.
[39] Kai Yang. Tao Fan, Tianjian Chen, Yuanming Shi, and Qiang Yang. A quasi-newton method based vertical federated learning framework for logistic regression. arXiv preprint 1r1.0v191..00011, 2019.
[40] Ram Zamir and Meir Feder. On lattice quantization noise. IEEE Transactions on Information Theory, 42(4): 152-1159, 1996.
[41] Qingsong Zhang, Bin Gu, Zhiyuan Dang, Cheng Deng. and Heng Huang. Desirable companion for vertical federated learning: New zeroth-order gradient based algorithm. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2598-26077 2021.
[42] Qingsong Zhang, Bin Gu, Cheng Deng, Songxiang Gu, Liefeng Bo, Jian Pei, and Heng Huang. AsySQN: Faster vertical federated learning algorithms with better computation resource utilization. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 3917-3927, 2021.
[43] Qingsong Zhang, Bin Gu, Cheng Deng, and Heng Huang. Secure bilevel asynchronous vertical federated learning with backward updating. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pages 10896-10904, 2021.
[44] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. idlg: Improved deep leakage from gradients. arXiv preprint arxivx2001.00000 026100, 2020.
[45] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019.
12


Reviews:
[{"review_id": "12cGkIww1O", "reviewer": "Reviewer_wequ", "summary": "The paper introduces a hybrid Federated Learning (FL) framework, named VFL-CZOFO, which aims to provide intrinsic privacy protection while also significantly improving the convergence rate when compared to existing ZOO-based frameworks.", "questions": "VFL-CZOFO is designed for better privacy protection while reducing communication costs. In the case where VFL-CZOFO guarantees a significantly smaller privacy budget than VAFL+Gaussian, what will the accuracy be?", "limitations": "The paper introduces a framework that provides intrinsic privacy protection while also improving communication costs. However, there are weaknesses and questions listed above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Faster Convergence: The paper demonstrates that VFL-CZOFO achieves faster convergence compared to other ZOO-based frameworks.\n\n2. Theoretical Solidity: The paper is theoretically sound, with a proof of convergence, and guarantees $(\\epsilon, \\delta)$-DP (differential privacy).", "weaknesses": "The major concern lies in the experimental performance of VFL-CZOFO. \n\n1. The experiments only involve 2 clients, which are considered too small for a conclusive evaluation. The proposed algorithm's performance in a large-scale federated learning system remains unclear. \n\n2. The usage of only 2 datasets and lack of clarity regarding heterogeneity raise concerns about the model's generalizability and applicability in diverse scenarios.\n\n3. The choice of epsilon (around 90) for privacy evaluation seems excessively high, raising doubts about the actual privacy protection offered. Additionally, the training doesn’t seem to converge well at epoch 50 in Fig. 2, potentially affecting the total privacy budget.\n\n4. Table 3 shows that the proposed method sacrifices accuracy compared to the FOO-based method while improving communication cost. This trade-off is questionable, as accuracy is generally more critical in most cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Weakness 1 (Experiment on more clients needed): \n\nWe conduct experiments with 4 and 8 clients to further assess the performance of our framework on a larger scale. The results are presented in Figure 1&2, Table 1&2 in the **attached PDF (in the topmost rebuttal box)**. It is essential to note that Vertical Federated Learning (VFL) typically involves a **small number of participants** (e.g. [5, 6, 10, 15, 27, 40] all used less than 5 clients). Unlike Horizontal Federated Learning (HFL), which involves millions of smartphones, tablets, and similar devices as clients, VFL primarily engages big companies and institutions. The added experiments will be included in the appendix of the manuscript.\n\n>Weakness 2 (The model’s generalizability in diverse scenarios): \n\nWe not only conducted the experiment on the mainstream CV dataset (MNIST and CIFAR10) but also on the **real-world dataset** for VFL. Specifically, the experiments conducted on GiveMeSomeCredit and Adult(a9a) datasets can be found in Appendix E.4 and E.5 of the manuscript. The results from these experiments demonstrate that we achieve comparable test accuracy to other baseline approaches, while significantly reducing communication costs.\n\nBesides, it is worth noting that there is no data distribution heterogeneity in VFL because, in VFL, each client shares different features of the **same sample**. Other types of heterogeneity in VFL such as system heterogeneity and feature unbalanced, is beyond the scope of our paper, including them will obscure the clarity of our theoretical and experimental result. \n\n\n>Weakness 3 (Privacy budget seems high. Deviation from convergence at epoch 50 in Figure 2.): \n\nThe $\\epsilon$ in that figure is the accumulated privacy budget for the entire training, demonstrating the guarantee in the **the worst case** in VFL. The worst case means that the attacker can acquire all the messages from the server by colluding all clients, during the entire training procedure of 50 epochs. Besides, the sampling time of 100 is very large in this experiment, whose margin gain for convergence is small. Therefore, the privacy budget demonstrated here is larger than practical. To acquire a smaller $\\epsilon$, we can use fewer iterations to reduce the accumulated information or use smaller sampling times to estimate the gradient less accurately. \n\nRegarding the “epoch 50 in Fig. 2”: the basic zeroth-order estimator (ZOE) in Eq.2 has a large forward bias. This is possibly the reason that causes an unstable convergence around epoch 50 in Figure 2. Applying a slightly “advanced” centralized version of ZOE, we can get a more stable convergence and higher test accuracy, with a trade-off of extra computational cost on the server. More specifically, we convert Eq.2 to its centralized version:\n$ \\frac{\\phi(d_{h_m}) }{2 q \\mu_m } \\sum_{j=1}^{q} [{f_i(h_{m, i} + \\mu_m u_{m, i}^j )  - f_i ({h_{m, i}}- \\mu_m u_{m, i}^j } )] u_{m, i}^j$\n\nWe add an experiment that combines the above techniques in **Figure 3 of the PDF attached**. Applying early stopping, smaller sampling times, and centralized ZOE, we demonstrate a smaller accumulated privacy budget of $\\epsilon=32$, without significantly influencing the convergence. The privacy budget can be further reduced with more techniques. However, it is worth noting that there is a privacy-utility trade-off in DP, a small privacy budget will cause low test accuracy [31, 35]. For example, in [35], when $\\epsilon = 100$, they achieve around 90% test accuracy, while $\\epsilon=50$, the accuracy drops to around 68%. \n\n\n>Weakness 4 (Sacrifice in test accuracy): \n\nOur framework also has the capability to achieve the same test accuracy as the corresponding VAFL baseline (not sacrificing the test accuracy), applying a corresponding privacy-utility trade-off. Note that the first three baselines sacrifice privacy and get higher test accuracy (“test-accuracy-focused trade-off”), while the last three baselines take a balance between privacy and utility (“balanced trade-off”). In Table 3, we only demonstrated the “balanced trade-off” for our method. However, our framework can also demonstrate the “test-accuracy-focused trade-off”, achieving the comparable test accuracy of the corresponding asynchronous VFL baseline (VAFL [6]). The cost is a larger privacy budget and increasing communication-computation costs. The experiment result is attached in **Table 3 of the PDF attached**.\n\nBesides, regarding the \"balanced trade-off\", the basic zeroth-order estimator (ZOE) we used has a large forward bias. To correct this, we apply a slightly “advanced” centralized version of ZOE so that we can reach higher test accuracy and better convergence. When we did the experiment in the manuscript, we only applied the basic ZOE because our prime goal was the communication cost, therefore we demonstrated a comparable test accuracy with the target baseline in Table 3. With this centralized ZOE, we can achieve a smoother convergence, a similar privacy budget ($\\epsilon=95$), and better test accuracy (96.32%) than the corresponding VAFL+DP of (95.94%). (Experiment result is shown in **Table 3 of PDF attached**.) \n\n>Question (What would be the accuracy if VFL-CZOFO has a smaller privacy budget than VAFL+DP):\n\nThe privacy-utility trade-off exists within all DP algorithms. If we achieve a smaller privacy budget than VAFL+Gaussian, it means that we apply a trade-off that places a greater emphasis on privacy, leading to lower utility and less test accuracy. However, the advantage of our framework is that we provide comparable protection as the DP mechanism while reducing the communication cost simultaneously.\n"}, {"review_id": "P40ZJLOHaV", "reviewer": "Reviewer_Mz1s", "summary": "This paper presents a pioneering Zero-Order Optimization (ZOO)-based VFL algorithm that effectively ensures privacy preservation while significantly enhancing communication efficiency. Regarding privacy, the paper demonstrates theoretically that ZOO can inherently offer $(\\epsilon,\\delta)$-differential privacy, providing a strong foundation for understanding the privacy preservation achieved by ZOO. Concerning communication efficiency, the method ingeniously combines first-order and zero-order gradient optimization, resulting in remarkable improvements in training and communication efficiency. Moreover, the paper rigorously proves the convergence of the proposed algorithm. Extensive experiments are conducted, further affirming the superiority of the method.", "questions": "1. Does the number of clients significantly affect the computational efficiency?\n2. In Appendix E.4 and E.5, Figure 5 and Figure 6 present VFL-ZOFO, which is different from VFL-CZOFO. Do they have any differences?\n", "limitations": "1. The computation cost of the server is extremely high.\n2. This method is not suitable for many client situations.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper presents a novel VFL method that applies different optimization methods to different layers of the global model in each iteration, significantly improving the convergence rate of ZOO-based VFL while preserving privacy.\n2. The theoretical proof that ZOO can inherently offer $(\\epsilon,\\delta)$-differential privacy provides a strong foundation for understanding the privacy preservation achieved by ZOO in VFL.\n3. This paper conducts extensive experiments, offering concrete evidence of its effectiveness.\n", "weaknesses": "1. The experiments are currently conducted with only two clients, but further experiments with varying numbers of clients are necessary. \n2. The article divides experiments on different datasets into multiple chapters for presentation, which hinders a comprehensive display of the model. \n3. The computation cost of the server is extremely high, and it escalates with an increase in the number of clients due to the average random gradient estimation for each client.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Weakness 1& Question 1& Limitation 2 (Experiment on more clients needed): \n\nWe conduct experiments with 4 and 8 clients to further assess the performance of our framework on a larger scale. The results are presented in the Figure 1&2, Table 1&2 in the **attached PDF (in the topmost rebuttal box)**. It is essential to note that Vertical Federated Learning (VFL) typically involves a **small number of participants** (e.g. [5, 6, 10, 15, 27, 40] all used less than 5 clients). Unlike Horizontal Federated Learning (HFL), which involves millions of smartphones, tablets, and similar devices as clients, VFL primarily engages big companies and institutions. The added experiments will be included in the appendix of the manuscript.\n\n>Weakness 2 (Presentation of the experiment): \n\nWe aimed to conduct a comprehensive evaluation of our algorithm, putting the experiment for all datasets together could be the optimal choice. However, because of space limitations, we had to put the experiment on other datasets in the appendix. We considered each dataset as a distinct scenario of applying VFL, therefore we separated them into different chapters for clarity.\n\n>Weakness 3 & Limitation 1 (Computational cost of the server): \n\nWe acknowledge this limitation, and we also include an experiment on the computational cost on the server with more clients in **Table 4 of the PDF attached** (the experiment setting is the same as Appendix E.2, but changing the number of clients). \n\nHowever, we have several justifications that this limitation is acceptable in practice. First, the number of clients involved in VFL is typically **quite small**, therefore the increase in the number of clients is controllable. Second, it is worth noting that **the bottleneck of VFL is communication cost** rather than computation cost [5, 27]. Local computations consume significantly less time compared to communication with other participants. Third, the server as the initiator and beneficiary **typically possesses more computational resources**, therefore using the higher computation cost of the server to trade off communication cost/privacy is favorable in the strategy of building VFL.\n\n\n>Q2 (Figure 5&6 in Appendix E): \n\nThat is a typo for Figures 5 and 6 in Appendix E, both should be “CZOFO”. Thank you very much for pointing that out!\n"}, {"review_id": "PJzdO3zSXx", "reviewer": "Reviewer_1JdL", "summary": "The paper is aiming at solving two critical problems of Vertical Federated Learning (VFL), the convergence rate of ZOO-based VFL and the privacy guarantee of ZOO-based VFL. This study provides a simple solution of using different optimizations i.e., the first-order optimization (FOO) and zeroth-order optimization method (ZOO) in the VFL framework, and theoretically explained the privacy guarantee with differential privacy. Experiments are conducted with regard to differential privacy, training efficiency, and communication cost which showed significant improvement in communication cost compared with SOTA and baselines.", "questions": "It is less clear to me whether the reduction of total communication cost is from “applying ZOO” or “applying compression”. The current ablation study did not tell the ratio of the reduction of the communication cost between “applying ZOO” and “applying compression”.\n\nHow your approach solves the problem if a certain privacy budget is required? Since the privacy budget of your framework is not directly controlled by the magnitude of the noise.", "limitations": "Yes, the limitation was discussed.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This study discusses the training efficiency and privacy in applying ZOO to VFL, which is a significant problem in this area. The idea of cascaded different optimization is novel and interesting. The motivation of balancing the advantages of FOO&ZOO sounds. I am appreciated that it proposes a simple solution that is easy to understand and will inspire more following studies in this area. The solution is validated from different dimensions and thus I think the effectiveness of the solution is reliable. \n\nThe paper is also theoretically contributed. Theorem 4.1 explains the privacy of ZOO. Theorem 5.2 guarantees training efficiency. The experiments are solid from my perspective, comprehensively covering the essential aspects of the algorithm, including the privacy budget of DP, the learning curve, and the communication cost at each stage. The method has high performance with a substantial improvement in communication efficiency, making this work great potential of being a new SOTA baseline.", "weaknesses": "According to Table 1, solely applying ZOO on the client layer only reduce the backward message size from $d_h B$ to $q$ compared with FOO-based VFL. However, the forward communication size was not improved. I agree with the improvement of your work in improving the convergence rate, however, a large reduction in the total communication cost could be due to the compression. Could you illustrate more on the contribution of compression and ZOO in reducing the total communication cost? \n\nAs you mention in #261-#263, the fundamental difference between ZOO and Gaussian Mechanism is that your privacy budgets ($\\epsilon, \\delta$) are implicitly controlled by the parameter of ZOO. Will this limit the application of your solution when a certain degree of privacy budget is required?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Weakness 1 & Question1 (The contribution of ZOO and compression in reducing communication cost): \n\nYes, both methods contribute to enhancing communication efficiency. However, typically ZOO makes a more significant contribution to reducing the communication cost. \n\nTake the experiment presented in Table 2 as an example, The application of the ZOO results in a reduction of backward message cost **from 3073MB to 75MB**, achieving a total reduction of **2998MB**.  Subsequently, by using compression, the forward message size diminishes from 3073MB to 769MB, and backward costs additionally reduce from 75MB to 19MB, leading to a total reduction of **2360MB**. For this experiment, the ratio of the absolution contribution between ZOO and compression is around **1.27: 1**. \n\n>Weakness 2 & Question 2 (How to achieve a certain privacy budget): \n\nYes, that is the fundamental difference between our method and Gaussian Mechanism. If a certain privacy budget ($\\epsilon, \\delta$) is required. We need to run the parameter tuning process for the ZOO to achieve that privacy budget. For example, if the privacy budget is too large, we need to reduce the sampling time $q$ to make the gradient estimation less accurate or reduce the number of iterations $T$ to make the attacker accumulate less information (early stopping). We acknowledge that this tuning process is less convenient than Gaussian Mechanism where the corresponding magnitude of the Gaussian noise can be directly calculated. However, with our scheme, we achieve DP-guarantee by reducing the communication amount, while Gaussian Mechanism achieves DP-guarantee by adding noisy information. \n\n>Other notes\n\nWe also included **additional experiments in the attached PDF** (located in the topmost rebuttal section), containing the experiment involving 4 and 8 clients. "}, {"review_id": "u9vBQwI80j", "reviewer": "Reviewer_WL8R", "summary": "The paper proposes a solution for privacy and communication efficient vertical FL training framework by utilizing zero-order-optimisation (ZOO). Since the convergence of ZOO-based VFL is significantly slower than standard gradient-based VFL, the paper proposes to only implement ZOO on the cut layer. ", "questions": "- Why choose the uniform scale compressor in particular for the experiment? Have you compared it with other compressors?\n\n- It mentions that the paper proposes an asynchronous VFL, but how does asynchronous work? To finish the forward prop, the model will need to have all the intermediate output from all clients. I'm surprised to see that the synchronous version (Syn-VFL-ZO) perform much worse than asynchronous version (the paper version). Is there any reason why? Also, the synchronous version doesn't seem to use the Avg-RandGradEst. \n\n", "limitations": "- Only 2 clients for experiments. Especially in this case, ZOO can potentially lower the performance when the number of clients increase. \n\n- Only work on the image datasets, which each client holds half of the image. This particular experimental setup is not realistic in the real-life scenarios. \n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a strong motivation and a realistic setup of VFL. It also provides a detailed comparison with the SOTA VFL framework in Section 2 with convergence rate. The method of apply different optimization for different layer is very interesting.\n\n", "weaknesses": "- The method proposes to use a compressor for communication since the ZOO will generate extra communication cost, but didn’t analyse which compressing method is the best for the method. \n\n- It seems from Fig 2 that the method give lower performance compared to Gaussian. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">W1&Q1 (The choice of compressor): \n\nYes, applying different compressors may lead to different communication costs. We will add an experiment on the Top-K compressor in the appendix to enrich the discussion. However, comparing the performance of different compressors is **not the focus** of our paper. The goal for this part is to show that compression, as a common practice in distributed learning, is compatible with our framework. Therefore, we theoretically proved the convergence of our method with **any compression method**, and only used a basic compressor for demonstration in the experiment. \n\n>W2 (Convergence of Figure 2): \n\nWhen we did the experiment, we only applied the basic zeroth-order estimator (ZOE) because our primary objective was to demonstrate comparable performance with VAFL+DP while significantly reducing the communication cost. The basic ZOE (Eq. 2) has a large forward bias because the perturbation is only on the function's forward side. Applying a slightly “advanced” centralized version of ZOE, we can reach higher test accuracy and better convergence. More specifically, we convert Eq.2 to its centralized version which reduces the bias by sampling from both sides of the function:\n$ \\frac{\\phi(d_{h_m}) }{2 q \\mu_m } \\sum_{j=1}^{q} [{f_i(h_{m, i} + \\mu_m u_{m, i}^j )  - f_i ({h_{m, i}}- \\mu_m u_{m, i}^j } )] u_{m, i}^j$\n\nWith this centralized ZOE, we achieve a smoother convergence, similar privacy budget ($\\epsilon=95$), and better test accuracy (96.32%) than the corresponding VAFL+DP of (95.94%). We attached the result in **Figure 4 in the attached PDF (in the topmost rebuttal box)**.\n\n>Q2 (How does asynchronous work? Why is Syn-VFL worse than Asyn-VFL in Figure 3? Why ZOO-VFL does not use Avg-RandGradEst?):\n\nRegarding “how does asynchronous work”: Yes, the server requires embeddings from all clients. Therefore, to support asynchronous updates, the server maintains a table of embeddings from all clients. During each round, only the embedding of the activated client undergoes an update. This specific detail has been explained in lines #238-#240 of the manuscript. Furthermore, a comprehensive explanation of Asynchronous VFL can be found in Appendix D.1 of the manuscript.\n\nRegarding “Syn worse than Asyn”: the primary reason is that the fundamental difference between Asyn-VFL and Syn-VFL causes some ambiguity in measuring the convergence. To address this ambiguity, we will add the definition of the x-axis in the manuscript. \n\nWe explain this ambiguity here:\n\nIn some other works, the \"communication round (**CR**)\" may be used to measure the convergence of Asyn-VFL and Syn-VFL (**Figure 5 in the PDF attached** shows the \"Syn outperforms Asyn\" with the x-axis changed to CR). In one CR, Asyn-VFL updates only **one client** and the server, while Syn-VFL updates **all clients** and the server. This difference in the definition of CR is the reason behind the observed superiority of \"Syn\" over \"Asyn\" in this particular case. It is worth noting that, in each communication round, the communication cost for Syn-VFL is greater than that of Asyn-VFL.\n\nIn our study, we extend the concept of **“epoch”** in Asyn-VFL, to advocate an intuitive understanding comparable to traditional ML. For Asyn-VFL the number of CR in one “epoch” precisely matches the number of CR required for all clients to traverse the dataset in an ideal no-delay case. As per this definition, the server in Asyn-VFL undergoes more updates on the server compared to its corresponding Syn-VFL within one \"epoch\". Therefore shows “Syn worse than Asyn”. Note that the communication cost for one “epoch” is the same for Asyn-VFL and the corresponding Syn-VFL, which brings some convenience in the discussion of communication cost. \n\nRegarding \"why ZOO-VFL does not use Avg-RandGradEst\": The reason is that applying Avg-RandGradEst in ZOO-VFL will **significantly increase its forward communication cost**. To implement Avg-RandGradEst, these frameworks would need to generate $q$ perturbations on its local model and send all of these embeddings to the server, i. e. forwarding $q$ different $h(x+\\mu u)$ with different $u$. And this large cost is inevitable. Besides, a more basic consideration is that the original work of ZOO-VFL [40] did not apply Avg-RandGradEst, and we followed the implementation of this baseline. \n\nOur method effectively circumvents the expense associated with multiple sampling because the perturbation is on the layer of clients’ output, i.e. $h(x)+\\mu u$, with $q$ different $u$. This random sequence of $u$ can be shared via sharing the random seed, and only need to be generated once. Therefore, in each iteration, our framework only needs to send $h(x)$ instead of $ h(x+\\mu u)$, thereby avoiding the communication cost incurred by multiple sampling of Avg-RandGradEst.\n\n>L1 (Experiment on more clients needed):\n\nWe conducted experiments with 4 and 8 clients to further assess the performance of our framework on a larger scale. The results are presented in the Figure 1&2, Table 1&2 in the **PDF**. It is essential to note that Vertical Federated Learning (VFL) typically involves a **small number of participants** (e.g. [5, 6, 10, 15, 27, 40] all used less than 5 clients). Unlike Horizontal Federated Learning (HFL), which involves millions of smartphones, tablets, and similar devices as clients, VFL primarily engages big companies and institutions. The added experiments will be included in the appendix of the manuscript.\n\n>L2 (Need experiment in real-life scenarios):  \n\nWe not only conducted experiments on the mainstream CV dataset (MNIST and CIFAR10) but also on the **real-world dataset** for VFL in the Appendix of the manuscript. Specifically, the experiments conducted on GiveMeSomeCredit and Adult(a9a) datasets can be found in Appendix E.4 and E.5. The results from these experiments demonstrate that we achieve comparable test accuracy to other baseline approaches, while significantly reducing communication costs. \n"}, {"review_id": "y5VhqDY5gS", "reviewer": "Reviewer_uLCn", "summary": "This research proposes a novel cascaded hybrid optimization approach named VFL-CFOZO for VFL that combines zeroth-order (ZO) gradient and first-order (FO) gradient optimization techniques. The critical output layer of the clients uses the ZO gradient, while other parts utilize the FO gradient. This approach enhances convergence while maintaining privacy protection. Experimental results demonstrate that VFL-CZOFO achieves similar utility as the Gaussian Mechanism in DP privacy preservation while significantly reducing communication costs compared to state-of-the-art communication-efficient VFL frameworks.", "questions": "1. Why not add VAFL+DP to Figure 3 in Section 6.3? This work also incorporates privacy and communication efficiency. Though the paper is compared for training accuracy in 6.2, it needs to be clarified and intuitive enough. \n\n2. Is there any basis or analysis of the application of the chain rule on a cascaded hybrid gradient? [40] indicates that the chain rule is inapplicable between two ZOE gradients due to extra variance. However, this research directly uses it between FO and ZO gradients.", "limitations": "As mentioned in Section 7, the extra computational costs for the server do limit the scalability and utility of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- A novel idea and good motivation. Based on existing research about FOO and ZOO frameworks in VFL, this research focuses on privacy in transmitted parameters and efficiency on other layers to load balance.\n\n- Complete analysis and proofs. Compared to the previous works in ZOO-VFL, such as [40], this research supplies clear proof of DP privacy. \n\n- Moreover, convergence proofs are also sufficient.", "weaknesses": "- Lack of scalability. In VFL, the dimension of the dataset often increases with the scale of clients, which means higher sample times should be applied to guarantee convergence. Thus, the current experiments with two clients are insufficient in this aspect. The evaluation of the correlations of client size and “enough” sample times should be added.\n\n- The potential risk of offline clients. The identical random sequence demands that the server and client maintain high synchronization. If a client drops for a while and reconnects with high delay, renegotiating the random seed may be better than using the original random ID because the completeness and timeliness of the information in an offline client are usually uncertain for the server.   \n\n- Some minor mistakes. In the explanation of Figure 4 in Section 6.4, the symbol q is miswritten as p. Inconsistent expression of the paper. ‘VAFL-ZOFO’ in Figure 5 of Appendix E.4 but ‘VAFL-CZOFO’ throughout the paper. Table 1 of Appendix A.2 shows that the output embeddings without delay formula should be Φ(w^t) instead of the w^t with the wide tide.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Weakness 1 (Experiment with more clients needed): \n\nWe conduct experiments with 4 and 8 clients to further assess the performance of our framework on a larger scale. The results are presented in the Figure 1&2, Table 1&2 in the **attached PDF (in the topmost rebuttal box)**. It is essential to note that Vertical Federated Learning (VFL) typically involves a **small number of participants** (e.g. [5, 6, 10, 15, 27, 40] all used less than 5 clients). Unlike Horizontal Federated Learning (HFL), which involves millions of smartphones, tablets, and similar devices as clients, VFL primarily engages big companies and institutions. The added experiments will be included in the appendix of the manuscript.\n\n>Weakness 2 (Synchronization of the random seed): \n\nThe synchronized random sequence does not need to be generated streamy (repeatedly) during the entire training process. Note that in Eq. 2, the random sequence $u_{m, i}^j $ **has no superscript for iteration time $T$**. Therefore, the participants only need to negotiate $u_{m, i}^j $ once, rather than repeatedly negotiate it during the entire training. Here we also provide one lazy method to generate the synchronized random sequence without communication, which is directly using the sample ID as the random seed to generate the random sequence. \n\nIn our work, we assume that generating the same random sequence with the same seed is feasible and not very expensive. However, further exploration of the engineering aspects related to generating random sequences is **beyond the scope** of this paper. \n\n>Weakness 3 (Minor issues): \n\nThank you very much for pointing them out! The typo $p$ in Section 6.4 has been corrected to $q$. Figures 5 and 6 in Appendix E are also typos, we corrected them to “CZOFO”. We corrected the symbol for the $\\Phi(w^t) $ in the notation table in Appendix A, along with some layout problems in that table. \n\n>Question 1 (Add VAFL+DP in Figure 3 of the manuscript): \n\nWe attached the figure where VAFL+DP is added in **Figure 6 of the PDF attached**. \n\nYes, our primary objective of section 6.2 is **comparing training efficiency and communication cost**, while carefully excluding the influence of other factors. Moreover, it is worth noting that VAFL has better convergence performance compared to \"VAFL+DP,\" as shown in the attached figure, where the latter incurs significantly higher communication costs. Therefore, we compared the VAFL baseline with the optimal convergence rate in that section.\n\nBesides, another fundamental concern is that the algorithm “VAFL[6]+DP[1]“ presented in our paper is **not a published baseline**; rather, it is a customized algorithm designed by us that offers equivalent protection to our proposed framework. Therefore, we did not treat it as a baseline for section 6.2 when we presented our work. \n\n>Question 2 (Basis of Chain ZOE. The discussion of the chain rule in [40]):\n\nTo the best of our knowledge, we are the first to propose the chain of different gradient estimators, explore its advantages in VFL, and provide a comprehensive convergence analysis. \n\nIn [40], the author means that the **multiplication of two ZOE** introduces extra variance. Specifically, separately estimating the two terms in $\\frac{\\partial f}{\\partial h} \\cdot \\frac{\\partial h}{\\partial w}$ with two ZOE will lead to extra variance. Therefore, they directly estimate $ \\frac{\\partial f}{\\partial w}$ with ZOE to avoid this extra variance. \n\nIn our framework, we also avoid the multiplication of two ZOE. We solely estimate $\\frac{\\partial f}{\\partial h} $ with ZOE and calculate $\\frac{\\partial h}{\\partial w}$ with FO gradient. As a result, no extra variance is introduced in our framework. \n\n>Limitation (Extra computational cost on the server):\n\nWe acknowledge this limitation. However, we have several justifications that this limitation is acceptable in practice. First, the number of clients involved in VFL is typically **quite small**, therefore the increase in the number of clients is controllable. Second, it is worth noting that **the bottleneck of VFL is communication cost** rather than computation cost [5, 27]. Local computations consume significantly less time compared to communication with other participants. Third, the server as the initiator and beneficiary **typically possesses more computational resources**, therefore using the higher computation cost of the server to trade off communication cost/privacy is favorable in the strategy of building VFL.\n"}]

Author rebuttal:
**We would like to thank the reviewers for dedicating their time and effort to assess the manuscript.**

**Attached is the PDF for the figures and tables.**

Meta-review: A vertical FL method is presented that combines zeroth-order (ZO) gradient (used by the output layer of the clients) and first-order (FO) gradient optimization techniques.  This approach enhances convergence while maintaining privacy protection. Experimental results show that this method is able to achieve similar privacy guarantee as the DP Gaussian mechanism while significantly reducing communication costs compared to other VFL frameworks.  There was a good amount of correspondence and discussion, resulting in all reviews on the positive side.
Decision: Accept (poster)