Coresets for Vertical Federated Learning: Regularized Linear Regression and $K$-Means Clustering
Authors: Lingxiao Huang
Zhize Li
Jialin Sun
Haoyu Zhao
Venue: NeurIPS 2022 Accept (2022)
Keywords: vertical federated learning
coreset
linear regression
k-means clustering

Abstract: Vertical federated learning (VFL), where data features are stored in multiple parties distributively, is an important area in machine learning. However, the communication complexity for VFL is typically very high. In this paper, we propose a unified framework by constructing \emph{coresets} in a distributed fashion for communication-efficient VFL. We study two important learning tasks in the VFL setting: regularized linear regression and $k$-means clustering, and apply our coreset framework to both problems. We theoretically show that using coresets can drastically alleviate the communication complexity, while nearly maintain the solution quality. Numerical experiments are conducted to corroborate our theoretical findings.

Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering
Lingxiao Huang" Nanjing University
Zhize Li" Carnegie Mellon University zhizeli0cmu, edu
muangg|ingriao11990022..com
Jialin Sun" Fudan University 1208ff0un edu. cn
Haoyu Zhao
Princeton Univeristy haoyu@princetonn edu
Abstract
Vertical federated learning (VFL), where data features are stored in multiple parties distributively. is an important area in machine learning. However, the communica- tion complexity for VFL is typically very high. In this paper, we propose unified framework by constructing coresets in a distributed fashion for communication- efficient VFL. We study two important learning tasks in the VFL setting: regular- ized linear regression and k-means clustering, and apply our coreset framework to both problems. We theoretically show that using coresets can drastically alle- viate the communication complexity, while nearly maintain the solution quality. Numerical experiments are conducted to corroborate our theoretical findings.
Introduction
Federated learning (FL) 40
is a learning framework where multiple clients/parties collaboratively train machine learning model under the coordination of central server without exposing their raw data (i.e., each party's raw data is stored locally and not transferred). There are two large categories of FL, horizontal federated learning (HFL) and vertical federated learning (VFL), based on the distribution characteristics of the data. In HFL, different parties usually hold different datasets but all datasets share the same features; while in VFL, all parties use the same dataset but different parties hold different subsets of the features (see Figure lap.
36 68
communication: single party cannot observe the full features, it requires communication with other parties to compute the loss and the gradient of a single data. This will result in potential problems: it may require a huge amount of communication to jointly train the machine learning model when the dataset is large; and (ii) the procedure of VFL. transfers the information of local data and may cause privacy leakage. Most of the VFL literature focus on the privacy issue, and designing secure training procedure for different machine learning models in the VFL setting (28 74 72 10 However, the communication efficiency of the training procedure in VFL is somewhat underexplored. For unsupervised clustering problems, Ding et [99 propose constant approximation schemes for k-means clustering, and their communication complexity is linear in terms of the dataset size. For linear regression, although the communciaiton complexity can be improved sublinear via sampling, such as SGD-type uniform sampling for the dataset [50 74), the final performance is not comparable to that using the whole
Compared to HFL, VFL 74| 50 71 is generally harder and requires
"Alphbbetical order.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

dataset. Thus previous algorithms usually do not scale or perform well to the big data scenarios. This leads us to consider the following question:
How to train machine learning models using sublinear communication complexity in terms of the dataset size without sacrificing the performance in the vertical federated learning (VFI.) setfing?
In this paper, we try to answer this question, and our method is based on the notion of coreset [27] [22] 23]. Roughly speaking, coreset can be viewed as a small data summary of the original dataset, and the machine learning model trained on the coreset performs similarly to the model trained using the full
dataset. Therefore, as long as we can obtain a coreset the VFL setting in a communication-effiee way, we can then run existing algorithms on the coreset instead of the full dataset.
Our contribution We study the communication-efiie methods for vertical federated learning with an emphasis on scalability, and design a general paradigm through the lens of coreset. Concretely, we have the following key contributions:
1. We design a unified framework for coreset construction in the vertical federated learning setting (Section 3). which can help reduce the communication complexity (Theorem 2.5
2. We study the regularized linear regression (Definition 2.1 and k-means (Definition 2.2
problems in the VFL setting, and apply our unified coreset construction framework to them. get e-approximation for these two problems using only o(n2) sublinear
We show that communications under mild conditions, where n is the size of the dataset (Section and [5)
3. We conduct numerical experiments validate our theoretical results. Our numerical experi- ments corroborate our findings that using coresets can drastically reduce the communication complexity, while maintaining the quality of the solution (Section (). Moreover, compared to uniform sampling, applying our coresets can achieve a better solution with the same or smaller communication complexity.
1.1 More related works
Federated learning Federated learning was introduced by McMahan et al. (54, and received
increasing attention in recent years. There exist many works studied in the horizontal federated
learning (HFL) setting, such as algorithms with multiple local update steps [54, 17
39
25
56 77
There also many algorithms with communication compression [38 55 47
46
60
21
76
61 78
and algorithms with privacy preserving 770 30
Vertical federated learning Due the difficulties of VFI., people designed VFI. algorithms for
some particular machine learning models, including linear regression (50] 74), logistic regression [75
73
gradient boosting trees [63 10,, and k-means [19] For k-means, Ding al. [19
proposed an algorithm that computes the global centers based on the product of local centers, which
requires OnT'') communication complexity. For linear regression, Liu al. (50) and Yang al.
[74] used uniform sampling to get unbiased gradient estimation and improved the communication efficiency, but the performance may not be good compared to that without sampling. Yang et 773 also applied uniform sampling to quasi-Newton algorithm and improved communication complexity for logistic regression. People also studied other settings VFL, e.g., how to align the data among different parties 662), how to adopt asynchronous training 9 26), and how to defend against attacks this work, we aim to develop communication-effiiee algorithms to handle large-scale VFL. problems.
in VFL 49 53
Coreset Coresets have been applied to a large family of problems in machine learning and statistics,
including clustering 22 31
15 16), regression [20
43
6
13
34 [2], low rank approximation [14].
and mixture model [52 33 Specifically, Chhaya et 12 investigated coreset construction for reg-
ularized regression with different norms. Feldman and Langberg (22). Braverman et al. 77 proposed
an importance sampling framework for coreset construction for clustering (including k-means). The coreset size for k-means clustering has been improved by several following works [1 15] 16) to
Ökk=")) and Cohen-Addad et al. [6 proved lower bound of size {2(=-2k) Due to the mergable
In numerical experiments (Section
provide results justify this claim.

---

Central server
$ sto
Central server
xr()) (X y)
X((
x(2)
.t3
stey
507
data
m idxi
Party 1
Party 2
Party
Party 1
Party 2
Party
Communication model in VFL
(b) General coreset framework in VFL
Figure 1: Illustration of coreset construction in VFL
property of coresets, there have been studies on coreset construction in the distributed/horizontaal setting To our knowledge, we are the first to consider coreset construction in VFL.
2 Problem Formulation/Model
In this section, we formally define our problems: coresets for vertical regularized linear regression and coresets for vertical k-means clustering (Problem D.
Vertical federated learning model. We first introduce the model of vertical federated learning (VFL). Let IRd be dataset of size that is vertically separated stored I' data parties 2 2). Concretely, we represent each point æ; E X by 2; = (z)
where ((() E R (j E [T],
and each party j E [T] holds a local dataset X() =
iEjN Note that Σ dj
Additionally, if there is label Y/ E RR for each point E X, we assume the label vector E IR" stored Party T. The objective of vertical federated learning is to collaboratively solve certain training problems in the central server with total communication complexity as small as possible.
Similar to Ding et al. [9 Figure 1]. we only allow the communication between the central server and each of the I' parties, and require the central server to hold the final solution. Note that the central server can also be replaced with any party practice. For the communication complexity, we assume that transporting an integer/flaaing--on point costs 1 unit, and consequently, transporting d-dimensional vector costs d communication units. See Figure for an illustration.
Vertical regularized linear regression and vertical k-means clustering. the following two important machine learning problems the VFL model.
In this paper, we consider
Definition 2.1 (Vertical regularized linear regression (VRLR)). Given dataset X Rd together with labels E IR" in the VFL model, regularization function Rt Rd + R>o, the goal of the vertical regularized linear regression problem (VRLR) is to compute vector 0 E Rd in the server that (approximately) minimizes cost (X, 0) Eie(n) cost (X, 0) = - (ar y: R(0), and the total communication complexity is small as possible.
Definition 2.2 (Vertical k-means clustering (VKMC)). Given dataset X C Rd in the VFL model, an integer & 2 1, let C denote the collection of all k-center sets C E with |C| = and d(.,) :) denote the Fuclidean distance. The goal of the vertical k-means clustering prob- lem (VKMC) is to compute k-center set C. E C in the server that (approximately) minimizes cost (X, C)= == Eie(s) cost," (X, C)) Eigjn) d(x,, C)² Eie(n) minege d(æ;, e)², and the total communication complexity is as small possible.
Ding et al. 19 proposed a similar vertical k-means clustering problem and provided constant approximation schemes. They additionally compute an assignment from all points 3; to solution C, which requires communication complexity of at least Q(nT). Due to huge n, directly solving VRLR or VKMC non-trivial task and may need large communication complexity. To this end, introduce powerful data-reduction technique, called coresets 27 22 23

---

Coresets for VRLR and VKMC. Roughly speaking, a coreset is small summary of the original dataset, that approximates the learning objective for every possible choice learning parameters. We first define coresets for offline regularized linear regression and k-means clustering as follows. As mentioned in Section T.I both problems have been well studied in the literature 22 31 15] 16]
Definition 2.3 (Coresets for offline regularized linear regression). Given dataset X C R
together with labels y E IR" and & E (0, 1), subset 5 S [r] together with a weight function w : S + Rgo is called an e-coreset for offline regularized linear regression if for any 0 E Rd
cost (S, 0) = Σ w(i) (x. y:)² + R(O) (1 c) cost R (X.0).
IES
Definition 2.4 (Coresets for offline k-means clustering). Given a dataset X C IR an integer k 2 1 and (0, 1), subset S _ [n]] together with weight function w S RR R2 called an E-coreset for offline k- memns clustering for any k-center set C C Rdd,
cost (S, C) = Σ (i) d(z; C) (1 cost c (X, C). BES
Now we are ready to give the following main problem.
Problem (Coreset construction for VRLR and VKMC). Given dataset X C IRd (together with labels y R") in the VFL model and E (0, 1). our goal is to construct an E-coreset for regularized linear regression (or k-means clustering) in the server, with as small communication complexity as possible. See Figure Tb for illustration.
Note that our coreset is a subset of indices which is slightly different from that in previous work (2 22 23) whose coreset consists of weighted points. This is because we would like to reduce data transportation from parties to the server due to privacy considerations. Specifically, if the communication schemes for VRLR and VKMC do not need to make data transportation, then can avoid data transportation by first applying our coreset construction scheme and then doing the communication schemes based the coreset. Moreover, have the following theorem that shows how coresets reduce the communication complexity in the VFL models, and the proof is in Section C
Theorem 2.5 (Coresets reduce the communication complexity for VRLR and VKMC). Given
E (0. 1), suppose there exist
1. communication scheme A that given (weighted) dataset X C Rd together with labels y E Rnn in the VFL model, computes an a-approximate solution (a 2 1) VRLR (or VKMC) in the server with communication complexity Mn);
2. communication scheme A' that given a (weighted) dataset X C Bd together with labels y E Ra in the VFL model, constructs an E-coreset for VRLR (or VKMC respecitively) of size m the server with a communication complexity Ao-
Then there exists a communication scheme that given a (weighted) dataset X C. Rd together with labels y E RR the VFL model, computes an (1 (1+3e) 33))a-pproxximat solution (a 2 1) 1)for VRLR (or VKMC respectively) in the server with a communication complexity No + 2m. + M(m).
Usually, (m)) (2mTT) and Ag is small or comparable Tm (see Theorems and 5.2 for examples). Consequently, the total communication complexity by introducing coresets is dominated by A(m), which is much smaller compared to A(n). Hence, coreset can efficiently reduce the communication complexity with slight sacrifice the approximate ratio.
3 A Unified Scheme for VFL Coresets via Importance Sampling
In this section, we propose a unified communication scheme (Algorithm I that will be used as a
meta-algorithm for solving Problem We assume each party E [T] holds real number y > 0 for data 226' Algorithm that will be computed locally for both VRLR (Algorithm) 2 and VKMC (Algorithm B) There three communication rounds in Algorithm I In the first round (Lines 2-4), the server knows all "local total sensitivities" g(), takes samples of []] with probability proportional

---

to G(), and sends aj to each party j, where aj is the number of local samples of party j for the second round. In the second round (Lines 5-6), each party samples collection Sti) C [n]] of size a with probability proportional to g. ()) The server achieves the union S UJE(T SG), In the third round (Lines 7-8), the goal is to compute weights w(a) for all samples. In the end, we achieve a weighted subset (S, w). We propose the following theorem to analyze the performance Algorithm | and show that (S, w) is coreset when size m is large enough.
Theorem 3.1 (The performance of Algorithm I.
The communication complexity of Algorithm be an inleger. We have
Om Let e, ô E (0, 1/2) and
* LLt max sup iE[n] ec2d sou. (x. s d andm= 0 ( log((G) + log(1/8))). With
cont (()
max
probability at least 1 - 6, (S, w) is an e-coreset for offline regularized linear regression.
{ max max sup co o
zE|n] Cee an (x Seee//iseee Syc ahth and m (0= log((G) log(L/0)) With
probability at least 1 5, (S, w) is E-coreset for offline k-means clustering.
The proof can be found in Appendix D The main idea is to show that Algorithm I simulates well-known importance sampling framework for offline coreset construction by (22 The term
(X. supPErd (X,0) (or suec cost' (X.C) called the sensitivity of point æ; for VRLR (or VKMC) that represents the maximum contribution of æt over all possible parameters. Algorithm aimss to use
cost [x
9; to estimate the sensitivity of æ, and hence, Ç represents the maximum sensitivity gap over all points. The performance of Algorithm mainly depends on the quality of these estimations Ejerr 9, ( As both ( and the total sum g [ie(m))e((] o. become smaller, the required size m becomes smaller. Specifically, if both Ç and G only depends on parameters k. d, T, the coreset size m is independent of n as expected. Combining with Theorem 2.5 we can heavily reduce the Communicatll complexity for VRLR or VKMC.
Σ Ejerry
(5)
Algorithm A unified importance sampling for coresct construction in the VFL model
Input: Each party j E [7] holds data ae together with a real number g 2 0, an integer m 2 Output: weighted collection S C [m]] of size |S| S
1: procedure (IS {u!") : E j E [T]})
2: Each party j E [T]] sends gb) - Eie[n] 9/ to the server.
1st round begins 3: The server computes G -jeer g6) and samples multiset A S [T'] of m samples, where
each sample j E [7] is selected with probability 06//s_
4:
The server sends 0j +- #jj A to each party j [T].
> 1st round ends
5: Each party E [T] samples multiset 5(:) S [m] of size aj. where each sample i [n] is
selected with probability /gw)), and sends sti) to the server.
> 2nd round begins
6: The server broadcasts a multiset S + Useer S(3) to all parties.
> 2nd round ends
:i $} to the server. 7: Each party j E [T] sends GG) (i)
9 8: The server computes weights w(i) +- Ejery a for each i E S.
> 3rd round begins
3rd round ends
9: return (S, w)
end procedure
Privacy issue. We consider the privacy of the proposed scheme from two aspects: coreset construc- tion and model training. As for the coreset construction part (Algorithm 1), the privacy leakage comes
from the "sensitivity score" g,
(f) of the data points in different parties. To tackle this problem, we
can use secure aggregation [S] to transport the sum 9: Σイ= of²") to the server without revealing
the exact values of o (Line 7 of Algorithm 1 The server only knows (S, w) and go)s, For the model training part, we can apply the secure VFL algorithms if existed, e.g., using homomorphic encryption on SAGA for regression (it is an extension from SGD to SAGA (28).
5

---

Algorithm 2 Vertical federated coreset construction for Regularized Linear Regression (VRLR)
Input: Each party j E [T] holds the data x!! for all i E [ni], coreset size m.
1: for each party E [T] do
2: Compute orthornormal basis UG) = [u]] ..... un " of X()
3: 9j 1 11)
1|2 + n for all E [n]
4: end for
return (S, w) f (ms 3)
5:
Note that the VFL communication model in Section 2 is assumed be semi-honest. Suppose some party j is malicious, then it can report large enough go) (Line 2 of Algorithm 1 such that the server sets the number of samples aj R m in party j (Line 4 of Algorithm D Consequently, party can sample a large multi-set $() which heavily affects the resulting set S. For instance, by reporting st) of uniform samples, party j can make S close to uniform sampling and loss the theoretical guarantees in Theorem 3.1
4 Coreset Construction for VRLR
In this section, we discuss the coreset construction for VRLR. We first show that is generally hard construct a strong coreset for VRLR. Then, we show how to communicaiion--ffiieeeen coresets for VRLR under mild assumption. All missing proofs can be found in Section B
construct
With slightly abuse of notation, we denote X E Raxd X() E Baxdy to be the data matrix of whole data and the data matrix stored on party j respectively. Since there are labels y stored on party T, (T) has dimension n x (dr + 1).
Communication complexity lower bound for VRLR We first show that it is hard to compute the coreset for VRLR by proving an Qin)) deterministic communication complexity lower bound.
Theorem 4.1 (Communication complexity of coreset construction for VRLR). Let T 2 Given constant s E (0, 1), any deterministic communication scheme that constructs an E-coreset for VRLR requires a communication complexity M(n)).
The communication complexity lower bound for linear regression has also been considered in the HFL. setting 667. e.g., Vempala al. [67] also gets a deterministic communication complexity lower bound. Theorem 4.1 shows that linear regression in the VFL setting is "hard" and thus may need to add data assumptions to get theoretical guarantees for coresct construction.
Communication-efficiee coreset construction for VRLR Now we show that under mild condi- tion, we can construct a strong coreset for VRLR using o(n) number of communication. Specifically, we assume the data X satisfies the following assumption, which will be justified in the appendix.
Assumption 4.1. Let UG- E Raxdd denote the orthonormal basis of the column space of X stored on party j (U(T) denotes the orthonormal basis of X (TT))) v)), and then the matrix U (U(1), (2) (1)),.,,,(.))) UT] has smallest singular value o mmin (U) 2 7 0.
Intuitively, 7 E (0, 1] represents the degree of orthonormal among data in different parties. As the larger y is, the more orthonormal among the column spaces of xt), and thus more close the orthonormal basis computed on X directly. Now we introduce our coreset construction algorithm for VRLR (Algorithm P). At a very high level perspective, we let each party j to compute a coreset 8G) based on its own data X XG), and combine all the 8(3) together to obtain final coreset S. More specifically, for each party j. we let it to compute UG) = [u ..... un ())T based on the data X and set 9. ("' ||+
||2 + 1/ to be the weight of data i on party j. Then, we set gi = =Eje(r] 9. to be the final weight of data a; and want to sample samples using weight g,. To do this, we apply the DIS procedure (Algorithm I.
(5)
Theorem 4.2 (Coresets for VRLR). For a given dataset C RRd satisfying Assumption 4.1 number of parties T > 1 and constants 5 e (0, 1), with probability at least 1 8, Algorithu constructs

---

an E-coreset for VRLR of size m D log 2d log 1/8), and uses communication complexity O
and thus when combined with Theorem 2.5 using coresct construction can reduce the communication complexity for VRLR. When Assumption 4. iis not satisfied, Algorithm 4.2 is not guaranteed to return a strong coreset. However, as shown in the following remark, will return another kind of coreset called robust coreset 22 32 69], which allows small portion of data to be treated outliers and excluded both in S and X when evaluating the quality of S. The outliers represent a small percentage of data with unbounded sensitivity gap. More details can be found in the Theorem G.3
Note that the coreset size and the total communication are all independent
Remark 4.3 (Robust coreset for VRLR). Given dataset X C Re together with labels y E IR", E E (0, 1) and B E [0, 1), subset S S [n] together with a weight function w - R20 is called (3, 8) r-oobustt coreset for offline regularized linear regression for any IRd, there exists a subset Oo S [n] such that |Ool/n h S B, Ool/1S| S B and
cost R (S Oo, 0) E cost R3 (X (X, 0) 8 cost R (X,
If Assumption 4.1 is not satisfied, for ((E:(T))))()))))))) Algorithm wiill return a (B,bs-robust coreset for VRLR with communication complexity (mmT).
Coreset Construction for VKMC
In this section, we discuss the coreset construction for VKMC. Similar VRLR, we first show generally requires (2(n) communication complexity to construct a coreset for VKMC, and then we show that it is possible vastly reduce the communication complexity (Algorithm 3 under mild data assumption. All missing proofs can be found in Section! F
Communication complexity lower bound for VKMC. We first present an (2n)) communication complexity lower bound for constructing an e-coreset for VKMC in the following theorem.
Theorem 5.1 (Communication complexity of coreset construction for VKMC). Let d d222 T 2 2. Given a constant E (0, 1) and an integer k > 3. any randomized communication scheme that constructs an E-coreset for VKMC with probability 0.99 requires a communication complexity 12()).
Different from VRLR, we have a randomized communication complexity lower bound for VKMC. Similarly, we also need to introduce certain data assumptions to get theoretical guarantees for coreset construction due to this hardness result.
Communication-effcientt coreset construction for VKMC Now we show how to communication- efficiently construct coresets for VKMC under mild condition. Specifically, we assume that the data satisfies the following assumption, which will be justified in the appendix.
Assumption 5.1. There exists т 2 1 and some party 1 =x
[T] such that ||x, x3,1 S
1 for any i,j E [n].
This assumption says that, there is a party that is "important", and any two data points which be differentiated can also be differentiated that party to some extent. Specifically, as is more close to 1, Assumption 5.1 implies that there exists a party E [T'] whose local pairwise distances | _ IIIs ||s are close to the corresponding global pairwise distances ||.; - x3 |s. Then we introduce our coreset construction algorithm for VKMC (Algorithm 3 For the input, note that there exist several constant approximation algorithms for k-means 41
66 The widely used
k-means++ algorithm [66] provides an OIn k) apapproxinnttion and performs well in practice. Similar
to Algorithm 2 for VRLR, Algorithm also applies Algorithm after computing g
()) locally. The
key is to construct local sensitivities 9."" to upper bound both Ç and G in Theorem 3.1 The derivation
of the local sensitivities ()( defined in Line is partly inspired by (65) which upper bounds the total sensitivity of point set in clustering problems by projecting points onto an optimal solution. Intuitively, if some party / satisfies Assumption 5.T constant factor approximate solution computed locally in party can also induce global one. Then by projecting points onto this global constant
7

---

Algorithm 3 Vertical federated coreset construction for k-means Clustering (VKMC)
Input: Each party j E [T] holds the data ( for all i [n.], coreset size m, number of centers k, an a-approximation algorithm A (e.g. k-means++).
Output: a weighted collection S S [m] of size |S| S
1: for all party j E [T] do
2: CG) A(1x; he)m)) Note that ( {cl C2 ..... c 1 (
()
3: Initialize B
2 for / E [k].
4: for all i E [n] do
5: T(i) + arg mi d(x) ()) ,c))
>> a mapping to find the closest center locally.
6: Bú) + B =(()
Ui
((())
7:
end for
co f EiE(n) d(z) c
b d(z = d(x,") ()) .((())
8:
9:
for all i [n] do
o E Venn daa))) ,2
ad(a cf
10:
1 (i), 96 +
2a
cost
| (cos(5))
|
11: end for
end for
return (S,w)= + DIS(m, ()
13:
approximation, we can prove that (t) (scaled by some constant factor) is upper bound of the
global sensitivity of a for any E [n]. Though unaware which party satisfies Assumption [..
(i) suffices to sum up 9i over j E [T), only costing additional T in G. Finally, we can upper bound < by (T) and G by OKT) respectively. The main theorem as follows.
Theorem 5.2 (Coresets for VKMC). For a given dataset X C Rd satisfying Assumption 5.1 an a-approximatio algorithm for k-means with
O(1), integers k 1, > 1 and constants e, 8 E (0, 1), with probability at least - 6, Algorithm constructs an E-coreset for VKMC of size m 00--2arrkT arkkT dk log (orkT) log 1 1)5)), and uses communication complexity O(mT).
Again, note that both the coreset size and communication complexity are independent of n. Thus, using Algorithm 3 together with other baseline algorithms can drastically reduce the communication complexity. Similar to VRLR, we have the following remark when the data assumption (Assumption
5.T not satisfied. More details can be found in the Theorem G.4
Remark 5.3 (Robust coreset for VKMC). Given dataset X C Rd, an integer k > 1, (0, and
3 E [0, 1), a subset S S [n]] together with a weight function w : S + R220 is called a (B, errbbustt coreset for offline k-means clustering for any C Rd,, there exists a subset Oc C [n]] such that |0cl/n 8, S | 3 and
cost"((xC0 (X,C). cost C (SyOCSSOOO.. C) cost (X (x)0c, C) E cost
If Assumption 5.1 is not satisfied, for = -(( Algorithm 3 will return a (B, (8,e)-non -roouust coreset for VKMC with communication complexity OmmI).
Numerical Experiments
In this section, we present the numerical experiments, which corroborate theoretical results. We conduct experiments on a single system that simulates the distributed settings
dataset 4 for both VRLR Empirical setup. We conduct experiments on the YearPredictioonn dataset has 515345 data, and each data contains 90 features and
and VKMC. YearPredictionn corresponding label. We assume there are T 3 parties and each party stories 30 distinct features. For VRLR, we split the data into a training set with size 463715 and a testing set with size 51630. We consider ridge regression in VRLR by letting R())) = X 2 for À = 0.1n where is the dataset
Thhe codes available http://gg///tttttcooo////////a/a

---

115
115
C. Centrralizzd
Communication Complexity
U-Centralized
110
110
SAGA
U-SAGA
Testing Loss
-107
Testing Loss
105
105
100
10c
100
95
95
90
-10
90
Central C-CentralU- C-SAGA U-SAGA
1000
2000
3000
4000
5000
6000
(1000) (1200) (1000) (1000)
Different Methods
Sample Size
Figure 2: Left: Testing loss and communication complexity of VRLR for different methods. C and U means using coreset or uniform sampling. The number in the parentheses denotes the sample size. Right: Testing loss of VRLR for different methods under multiple sample sizes.
C-Kmeans++
Communication Complexity
82
82
U-Kmeans+++
10?
C-DistDim
80
80
U-DistDim
Kmeans++
DistDim
Cost
78
10a
Cost
78
76-
76
10a
74
74
72
72
10a
C-K
DD
C-DD U-DD
1000
2000
3000
4000
5000
6000
(1000)
(1200)
(1000) (2000)
Different Methods
Sample Size
Figure 3: Left: Cost and communication complexity of VKMC for different methods. C and U means using coreset sampling or uniform sampling. The number the parentheses denote the sample size. Right: Cost of VKMC for different methods under multiple sample sizes.
size. For VKMC, there only one training set with size 515345 and without labels. We choose A = 10 (10 centers) and we normalize each feature with mean 0 and standard deviation for VKMC.
For VRLR, we consider two baselines: 1) CENTRAL as the procedure that transfers all data to the central server and solves the problem using scikit-learn package [57]; 2) SAGA as using [18] algorithm to optimize in VFL fashion. For VKMC, also consider two basclines: 1) KMEANS+
as the procedure that transfers all data to the central server and clusters using KMEANS+ [66]; 2)
DISTDIM by [9]]
For each baseline, we compare our coreset algorithm with uniform sampling. We use C-X to denote coreset sampling followed by algorithm X and U-X for uniform sampling followed by algorithm X, e.g. C-DISTDIM means that we apply coreset construction and then use DISTDIM algorithm. We compare C-X and U-X with different sizes, and each experiment is repeated 20 times.
Empirical results. Figure shows results for VRLR and Figure 3 shows results for VKMC. Table I summarize the results. For VRLR, since it is supervised learning problem, we report the testing loss; for VKMC, it is unsupervised learning task and the cost refers to the training loss the full training data.
Coreset sampling performs close to the baseline with less communication. From the results, we find that using our coreset can achieve similar loss compared to the baseline, while the communica- tion complexity is reduced drastically. Specifically by Table our coreset algorithm C-CENTRA can

---

Table 1: Results of VRLR and VKMC on YearPrediction dataset. Left: results for VRLR. Right: results for VKMC. The average and std. are computed using the 20 repeated experiments. The
communication complexity denotes the average communication complexity, and the number in the parenthesis denotes the fraction of coreset construction (or uniform sampling respectively).
(6i2c)
Aig
segSaad
Cost
campl.
Com.
Alg
aeglaed
Cost
Com. compl.
(sizc)
Alg
avglad
Cost
congl
Com
Cost oeg/Std
compl.
Com.
CENTRAL
90.4540.00
4.2c7
KMLAANS*
11.650300
4.6o7
100.302211
9.9g41019)
108.79/2.79
9.3eM(0.03)
13.76-0.38
9.9:410.19
9.36::0.33)
2000
95.07
2.06500.09 (9)
996651.01
1.95((.03)
72.6840.35
2.0:5(000)
73.52/0:44
19:5/0003)
3000
91. 39.3900.3
3.0c5:0.00 09)
96 73
2.8.500.03)
5000
72:25A0:17
3.96500099
73.25/0.8 39
2.5550003)
4000
92. 02:73/0.41 41
4.0:54009)
05.3220.65
3.765:0.03)
4000
72. 1400 19
4.0:5/0:00)
72.740 59
3.7.5/0033)
5000
92.4220.33
5.0c510.99
94.08/0.48
4.7c5(0.03)
5000
719900.13
5.9c510.09
72.540037
4.7c5/0.03)
6000
91.5 .7.90...3
5.9:510.09)
03.54/0.44
5.665/0.03)
5000
71. 71.9200.00 09
5.9:500.09
72.57/0.44
566500.03)
NOA
N7A
74.3540:00
93/217
6.9671-00001
110.43/2.43
1.26%(<00.01)
77.75/1.76
1.34400700
78.81/144
7.0c310433
2000
00.550096
1.6c%(40.011
70.8320885
2.5:400.22
1./33/210 10
1.304/0.47)
3000
97.13/0.98
1.98(c20.01)
100.64:1.44
2/4c8c<0.011
3000
75. 03.5220..00 64
3.7e410 73)
77,85/2.23
1.94000.08
4000
95.90/1.0 .94
2.5e8(20.001
99. 10.0011.2 20
1.3e8(-0000)
4000
75 75-49/0.44 45
4.9e410.74) 74)
76 70/1 27
2.5e4/0.48)
3000
94.75/2.85
3.0e8(+0.00)
97.6400.59
3.9c8(<40.01)
5000
75.21/0.50
6.1e410.74)
76.38/1.17
3.1cf10.49)
6000
83,836
3.668(20.01)
96.88/1.12
4.6r81c00011
5000
75.32A0.35
7.5:4(0.74)
76.44/1.03
3.704(0.49)
use less than 0.4% of training data (2000/463715) and achieve a 95.01/99..4 x approoppo solution for VRLR compared to the baseline CENTRAL. Observe that a larger coreset size leads to a smaller cost and a larger communication complexity. From Figures 2 3 (left), using coresets can reduce 50-100x communication complexity compared with the original baselines.
Coreset performs better than uniform sampling under the same communication. From Fig- ures / and 3 (right), observe that our coresets always achieve better solution than uniform sampling under the same sample size. Table[aalso reflects this trend. Under the same sample size, the communication complexity by uniform sampling is slightly lower than that of coreset, since there is no need to transfer weights in uniform sampling. Thus, we also compare the performance of our coresets and uniform sampling under the same communication complexity. From Figures 2 and (left), we find that for different baselines, our coreset algorithms still achieve better testing loss/training cost while using fewer or the same communication, compared to uniform sampling.
Coreset and uniform sampling may also make the problem feasible. It is also interesting to observe that SAGA will not converge (or very slowly) on the original VRLR problem (Table [ possibly because of the large dataset and the ill-conditioned optimization problem. However, by applying the coreset/uniform sampling, SAGA works for VRLR. This also indicates the effectiveness of our framework and the importance reduce the dependency (the dataset size).
Conclusion and Future Directions
In this paper, we first consider coreset construction in the vertical federated learning setting. We propose a unified coreset framework for communication-efficie VFL, and apply the framework to two important learning tasks: regularized linear regression and k-means clustering. We verify the efficiency of our coreset algorithms both theoretically and empirically, which can drastically alleviate the communication complexity while still maintaining the solution quality.
Our work initializes the topic of introducing coresets to VFL, which leaves several future directions. Firstly, our VFL coreset size is still larger than that of offline coresets for both VRLR and VKMC, even under certain data assumptions. One direction is to further improve the coreset size. Another interesting direction is to extend coreset construction other learning tasks in the VFL setting, e.g., logistic regression or gradient boosting trees.
References
[1] O. Bachem, M. Lucic, and A. Krause. Scalable k-means clustering via lightweight coresets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1119-1127, 2018.
[2] M.-F. F. Balcan, S. Ehrlich, and Y. Liang. Distributed k-means and k-median clustering on general topologies. Advances in neural information processing systems, 26, 2013.
10

---

[3] Z. Bar- Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar. An information statistics approach data stream and communication complexity. Journal of Computer and System Sciences, 68 (4):702-732, 2004.
[4] Bertin-Mahieux, P. Ellis, B. Whitman, and Lamere. The million song dataset. 2011.
[5] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and Seth. Practical secure aggregation for privacy-preserviee machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1195-1191,220 2017.
[6] C. Boutsidis, P. Drineas, and M. Magdon-Ismail. Near-optimal coresets for least-squares regression. IEEE transactions on information theory, (9(10))6880--399))) 6892, 2013.
[7] V. Braverman, D. Feldman, and H. Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/16 0ts//612.00889 2016.
[8] P. Bürgisser and F. Cucker. Smoothed analysis of moore-penrooe inversion. SIAM Journal Matrix Analysis and Applicaations, 31 (1(5):2769-23) 2783, 2010.
[9] T. Chen, X. Jin, Y. Sun, and W. Yin. VAFL: method of vertical asynchronous federated learning. arXiv preprint arXiv:2007.06081, 2020.
[10] W. Chen, G. Ma, T. Fan, Y. Kang, Q. Xu, and Q. Yang. Secureboost4: A high performance gradient boosting tree framework for large scale vertical federated learning. arXiv preprint S..iv:211001092:. 2021.
[11] K. Cheng, T. Fan, Y. Jin, Y. Liu, T. Chen, D. Papadopoulos, and Q. Yang. Secureboost: A lossless federated learning framework. IEEE Intelligent Systems, 36(6):87 2021.
[12] R. Chhaya, A. Dasgupta, and S. Shit. On coresets for regularized regression. In International conference on machine learning, pages 1866-1876. PMLR, 2020.
[13] M. B. Cohen, T. Lee, C. Musco, C. Musco, R. Peng. and A. Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 181 180- ACM, 2015.
[14] M. B. Cohen, C. Musco, and C. Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms,, pages 7758-1777 SIAM, 2017.
[15] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. A new coreset framework for clustering. In S. Khuller and V. V. Williams, editors, STOC 221 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21 2021, pages 169-182. ACM, 2021.
[16] V. Cohen-Addad, K. G. Larsen, D. Saulpic, and C. Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Proceedings of the firty-fourth annual ACM symposium on Theory of computing, 2022.
[17] R. Das, A. Hashemi, S. Sanghavi, and I. S. Dhillon. Improved convergence rates for non-convex federated learning with compression. arXiv e-prints, pages arXiv-2012, 2020.
[18] A. Defazio, F. Bach, and S. Lacoste-Julien Saga: fast incremental gradient method with sup- port for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
[19] H. Ding, Y. Liu, L. Huang, and J. Li. K-means clustering with distributed dimensions. In International Conference on Machine Learning, 2016.
[20] P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Sampling algorithms for la regression and applications. In Proceedings of the seventeenth annual ACM-SIAM symposiun on Discrete algorithm, pages 1127-1136. Society for Industrial and Applied Mathematics, 2006.
11

---

[21] I. Fatkhullin, I. Sokolov, E. Gorbunov, Z. Li, and P. Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2100.03294. 2021.
[22] D. Feldman and M. Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569-578. ACM, 2011.
[23] D. Feldman, M. Schmidt, and C. Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pea and projective clustering. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1434-1453, SIAM, 2013.
[24] E. Gorbunov, K. P. Burlachenko, Z. Li, and P. Richtárik. MARINA: Faster non-convex dis- tributed learning with compression. In International Conference on Machine Learning, pages 3788 -398. PMLR, 2021.
[25] E. Gorbunov, F. Hanzely, and P. Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference Artificial Intelligence and Statistics, pages 3556-3564. PMLR, 2021.
[26] B. Gu, A. Xu, Z. Huo, C. Deng, and H. Huang. Privacy-preserving asynchronous feder- ated learning algorithms for multi-party vertically collaborative learning. arXiv preprint arXiv:2008.008 06233, 2020.
[27] S. Har-Peled and S. Mazumdar. On coresets for k-means and k-median clustering. In 36th Annual ACM Symposium on Theory of Computing. pages 291-300, 2004.
[28] Hardy, W. Henecka, H. Ivey-Law, R. Nock, G. Patrini, G. Smith, and B. Thorne Private fed- erated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint
2017.
[29] D. He, R. Du, S. Zhu, M. Zhang, K. Liang, and S. Chan. Secure logistic regression for vertical federated learning. IEEE Internet Computing, 2021.
[30] R. Hu, Y. Guo, H. Li, Q. Pei, and Y. Gong. Personalized federated learning with differential privacy. IEEE Internet of Things Journal, 7(10)9530-9539 2020.
[31] I.. Huang and N. K. Vishnoi. Coresets for clustering in euclidean spaces: Importance sampling nearly optimal. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1416-1429, 2020.
[32] L. Huang, S. H.-C. Jiang, J. Li, and X. Wu. Epsilon-coresetss for clustering (with outliers) in doubling metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 825. IEEE, 2018.
[33] L. Huang, K. Sudhir, and N. Vishnoi. Coresets for regressions with panel data, Advances in Neural Information Processing Systems, 33:325-337, 2020.
[34] I. Jubran, A. Maalouf, and D. Feldman. Fast and accurate least neattmmea--seee -qquarss solvers. In Advances Neural Information Processing Systems, pages 8305 8316, 2019.
[35] Kaggle. Ke house data.
[36] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
[37] B. Kalyanasundaram and G. Schintger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, 1992.
[38] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3.52-3261. PMLR, 2019.
12

---

[39] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning. pages 5132-5143. PMLR, 2020.
[40] Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. 2016.
[41] A. Kumar, Y. Sabharwal, and S. Sen. A simple linear time (1+/spl -psioi-appooiiiatiion algorithm for k-means clustering in any dimensions. In 45th Annual IEEE Symposium Foundations of Computer Science, pages 454-662. IEFF, 2004.
[42] E. Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331-360. Elsevier, 1997.
[43] M. Li, G. L. Miller, and R. Peng. Iterative row sampling. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 127-136. IEEE, 2013.
[44] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 3703):00-60, 2020.
[45] Z. Li and P. Richtárik. A unified analysis stochastic gradient methods for nonconvex federated optimization. arXiv preprint wrXiv:2006.07013, 2020.
[46] Z. Li and P. Richtárík. CANITA: munication compression. In Advances in Neural Information Processing Systems, pages 13781, 2021.
Faster rates for distributed convex optimization with com-
[47] Z. Li, D. Kovalev, X. Qian, and P. Richtárik, Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, pages 5895-5904. PMLR, 2020.
[48] Z. Li, H. Zhao, B. Li, and Y. Chi. SoteriaFL: A unified framework for private federated learning with communication compression. arXiv preprint arXiv:2206. 09888, 2022.
[49] J. Liu, C. Xie, K. Kenthapadi, O. O. Koyejo, and B. Li. Rvfr: Robust vertical federated learning via feature subspace recovery. 1st NeurlPS Workshop on New Frontiers in Federated Learning (NFFL 2021), 2021.
[50] Y. Liu, Y. Kang, X. Zhang, Li, Y. Cheng, Chen, M. Hong, and Q Yang. A commu- nication efficient collaborative learning framework for distributed features. arXiv preprint 1912. 11 187, 2019.
[51] H. Lu, M. Li, T. He, S. Wang, V. Narayanan, and K. S. Chan. Robust coreset construction for distributed machine learning. IEEE J. Sel. Areas Commun., 38 (8(10))2400-244 2417, 2020.
[52] M. Lucic, M. Faulkner, A. Krause, and D. Feldman. Training Gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, 18(1):5885-5909 2017.
[53] X. Luo, Y. Wu, X. Xiao, and B. C. Ooi. Feature inference attack on model predictions in vertical federated learning. In 202/ IEEE 37th International Conference on Data Engineering (ICDE), pages 192- IEEE, 2021.
[54] B. McMahan, F. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication-effiiieen learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282, PMLR, 2017.
[55] K. Mishchenko, E. Gorbunov, M. Takáë, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1901.09269, 2019.
[56] A. Mitra, R. Jaafar, G. J. Pappas, and H. Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34: 14:11466--146 2021.
13

---

[57] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[58] J. M. Phillips. Coresets and sketches. CoRR, abs//600.0066 2016.
[59] A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-3900 1992.
[60] P. Richtárik, I. Sokolov, and I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34, 2021.
[61] P. Richtárik, I. Sokolov, E. Gasanov, I. Fatkhullin, Z. Li, and E. Gorbunov. 3PC: Three point compressors for communication-efficennn distributed training and a better theory for lazy aggregation. In International Conference on Machine Learning, pages 18596-18644 PMLR, 2022.
[62] J. Sun, X. Yang, Y. Yao, A. Zhang, W. Gao, J. Xie, and C. Wang. Vertical federated learning without revealing intersection membership. arXiv preprint arXiv2200600508, 2021.
[63] Z. Tian, R. Zhang, X. Hou, J. Liu, and K. Ren. Federboost: Private federated learning for gbdt. arXiv preprint 2rXi::2011.022766 2020.
[64] S. Truex, L. Liu, K.-H. Chow, M. E. Gursoy, and W. Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking, pages 61-66, 2020.
[65] K. Varadarajan and X. Xiao. On the sensitivity of shape fitting problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS fuer Informatik, 2012.
2012). Schloss Dagstuhi-Leiibniz-Zeen
[66] S. Vassilvitskii and D. Arthur. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027-1035, 2006.
[67] S. S. Vempala, R. Wang. and D. P. Woodruff. The communication complexity of optimization. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1732-1752. SIAM, 2020.
[68] J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, M. Al-Shedivat, G. Andrew, S. Aves- timehr, K. Daly, D. Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917, 2021.
[69] Z. Wang, Y. Guo, and H. Ding. Robust and fully-dynamic coreset for continuous-and-boundee learning (with outliers) problems. Advances in Neural Information Processing Systems, 34, 2021.
[70] K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. Quek, and H. V. Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-3400 2020.
[71] K. Wei, Li, C. Ma, M. Ding, S. Wei, F. Wu, G. Chen, and T. Ranbaduge. Vertical federated learning: Challenges, methodologies and experiments. arXiv preprint arXiv:2202. 04309, 2022.
[72] H. Weng, J. Zhang, F. Xue, T. Wei, S. Ji, and Z. Zong. Privacy leakage of real-world vertical federated learning. arXiv preprint arXiv:2011.00 .90.0,99,00.. 2020.
[73] K. Yang, T. Fan, T. Chen, Y. Shi, and Q. Yang. A quasi-newton method hased vertical federated learning framework for logistic regression. arXiv preprint arXiv: 19/20000 2019.
[74] Q. Yang, Y. Liu, T. Chen, and Tong. Federated machine learning: Concept and applications. ACM Transactions Intelligent Systems and Technology, 10(2):1-19, 2019.
14

---

[75] S. Yang, B. Ren, X. Zhou, and L. Liu. Parallel distributed logistic regression for vertical federated learning without third-party coordinator. arXiv preprint arXiv: 191.0999 2019.
[76] H. Zhao, K. Burlachenko, Z. Li, and P. Richtárik. Faster rates for compressed federated learning with client-variance reduction. arXiv preprini ar 13097, 2021.
[77] H. Zhao, Z. Li, and P. Richtárik. FedPAGE: A fast local stochastic gradient method for communication-effiien federated learning. arXiv preprint arX1v:2108.00755, 2021.
[78] H. Zhao, B. Li, 2. Li, P. Richtárik, and Y. Chi. BEER: Fast O(1/T) rate for decentralized
nonconvex optimization with communication compression. arXiv preprint urXiv:2201113320 2022.
[79] Y. Zhao. J. Zhao, M. Yang, T. Wang. N. Wang. L. Lyu, D. Niyato, and K.-Y. Lam. Local differential privacy-based federated learning for internet of things. IEEE Internet of Things Journal, 8(1 1):8836-8853 8853, 2020.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Assump- tion and Assumption 5.1 and we also provide justification of these data assumtions in Section
(b) Did you include complete proofs of all theoretical results? [Yes] All missing proofs can be found in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See section 6 footnote.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] All experiments are done using a single computer
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See the baseline
algorithms mentioned in Section 6
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] We provided the code for our experiments.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "vTRGBXodyS0", "reviewer": "Reviewer_Nzai", "summary": "This work considers how to subsample the datasets via coresets under the vertical federated learning (VFL) setting. By doing so, the communication cost of VFL algorithms can be sharply reduced. The authors first introduced a unified coreset construction algorithm in VFL, which requests an importance value for each sample, and then proposed how to estimate the importance values for regularized linear regression and k-means clustering, respectively. Experimental results show that the proposed algorithms can reduce the communication complexity without harming the model performance significantly. ", "questions": "## Definition\nHow is the cost evaluated in Section 6? In Definition 2.3 and Definition 2.4, the cost is evaluated on the coresets (i.e. $\\sum_{I \\in S}$). However, in my opinion, although the models are trained/computed on the coresets, the cost should be evaluated on the entire dataset (i.e., $\\sum_{I \\in \\[n\\]}$) when assessing the performance.\n\n## Privacy analysis\nI suggest the authors discuss the privacy of the proposed algorithms. To be specific, analyze what can be leaked from the messages transmitted in Algorithm 1. I also suggest the authors clarify the security assumption. It seems the server and clients are assumed to be semi-honest. But when they become malicious, is the proposed algorithm safe? \n\n## Experiments\nHow does the CENTRAL baseline solve the ridge regression problem? Does it solve by the closed-form solution (i.e., $(X^TX + \\lambda I)^{-1} X^T y$) or gradient descent? If by the closed-form solution, how does it solve the Lasso regression and elastic nets in Appendix A.2? \n\nIn Table 1, why the communication complexity of C-SAGA decreases w.r.t. the size of coresets? As indicated by Theorem 2.5, the communication complexity should be $\\Omega(mT)$ where $m$ is related to the size of coresets. \n\nMoreover, I suggest the authors report the communication of coreset construction and model training, respectively. It would help readers understand the overhead of your method. \n\n## Some other points\n- The caption of Figure 1 is missing.\n- The term “robust coreset” is not introduced. \n- In many previous VFL studies, there is no such a central server. However, it seems the central server can be substituted by Party T in Algorithm 1, so it looks good to me. \n", "limitations": "The authors have discussed future directions in Section 7.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nOverall, this is a solid work for me. The techniques are well introduced and the paper is easy to follow. Although the authors made two ideal assumptions when proposing algorithms for regularized linear regression and k-means clustering, they also provided the theoretical analysis when the assumptions are not satisfied. The experimental results are positive: the proposed algorithms work well when using less than 4% of the training data. \n## Weakness\nPrivacy is an important issue in VFL, but the authors did not analyze the privacy of the proposed algorithms. And the experimental results can be explained more in-depth. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "peLxfWfXQAi", "reviewer": "Reviewer_4KgV", "summary": "The paper gives a unified framework to construct coresets for the regularized regression and k-means clustering  in the vertical federated learning setting where the features of the data are distributed over multiple parties. The aim is to make the communication complexity sublinear in the no. of data points. The high level idea is to calculate local sensitivities for points at each party and then use them to sample points at each party. Finally take a union of these samples. The main contribution is to show that this intuitive technique gives a coreset with much lower communication complexity  under some assumptions on the data. When there are no assumptions, the authors also give some lower bounds. The authors also validate their theoretical claims with empirical results on real world dataset.", "questions": "Please clarify the following questions\n1) Will the results for regularized regression also extend to the setting when the data matrix is low rank? Is there any assumption here that data is full rank? Also the theoretical results hold for linear regression( no regularization) also? you have already shown some empirical results in appendix.\n2) Instead of giving the calculated values of communication complexity in the graphs, is it possible to compute time required for the communication in the experimental setup?\n", "limitations": "Please see the weaknesses/ questions section. Also please do a complete proof reading and try to make some sentence constructions better.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The use of coresets in the VFL setting to reduce communication complexity, to the best of my knowledge is novel. It is an important and interesting application.\n2) The idea is simple and intuitive\n3) The theory and the proofs appear sound and correct. I didnot go through the proofs in the appendix in details but had a quick look.\n4) Empirical evaluations validate theoretical claims in terms of the cost.\n\nWeaknesses:\n1)The writing is sloppy at a few places. Blelow are a few examples:\n        i)Line 22: \"Most of the VFL literature focus on the privacy issue, and design secure...\" should be and designing. \n        ii) Line 66 \"how to defend again\" should be against. \n        iii) Line 68 last sentence is not proper.\n        iv)Algorithm 1, line 3 summation should be over j.\n2) I could not find the details of the hardware system used for the implementation. Was it really a distributed set up or was the data just broken into parts and experiments were done on single system?\n3) Most of the proof techniques(other than lower bounds) and the coreset construction techniques  are very well known in literature and there is lack of novelty in that sense.\n4) The remarks regarding robust coresets are given without even the definiton of robust coreset in the main paper. I believe atleast the definition and some intuition/discussion as to why the robust coresets are possible without assumptions should be in main body otherwise the main paper becomes less readable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RjJkufbFxlR", "reviewer": "Reviewer_XK2T", "summary": "This paper forges a link between vertical federated learning where the attributes of the data are spread along multiple machines, to coresets - a data summarization that approximates the cost of every query on the data.\nSpecifically speaking, they focus on the problems of k-means and least mean squares regression.\n\nThe main idea is to reduce the communication complexity of an algorithm by computing a coreset for the distributed data - to do so, the authors extend the framework of importance (sensitivity) sampling to the vertical federated learning settings; see Algorithm 1 and Theorem 3.1.\n\nFocusing on Least squares regression the authors demonstrate that it is often challenging to build a \"strong\" (for every query) coreset for VRLR - the lower bound on the communication complexity is Ω(n).\nThen, they show how under a loose assumption, this can be done efficiently. According to this presumption, the subspace produced by data on any one party should not be entirely contained inside the subspace produced by other parties. Under such an assumption, one can get a coreset of size-independent from n, polynomial in the dimension d, and the appropriation error.\n\nThe same scenario hold for k-means - which requires a communication complexity Ω(n). However, assuming any two data points that may be differentiated can also be differed on a party that is \"important\" to some amount.\n\nFinally, experimental results show that coresets reduce the communication complexity and maintain a good quality solution.\n", "questions": "\n\nCan you please explain (intuitively) the relation between $\\gamma$ in Theorem 4.2 to the parameter which represents the maximum sensitivity gap overall points. Same for \\tau in Theorem 5.2.\n\n\nCan you give please more details about the parameter which represents the maximum sensitivity gap, how is it related to the data e.g., in linear regression?", "limitations": "The coreset requires a specific assumption on the data (that may not be satisfied in real-world).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the paper, mainly, the idea of using coreset in this new realm. The ideas are very interesting, and the findings are robust.\n\n\n\nSome comments and questions:\n1. Theorem 3.1 - S, W is not defined in the theorem.\n2. The empirical results are good but can be extended, e.g., 1. try on a larger number of parties, other datasets, and more.\n3. Please define (or at least explain) a robust coreset in the manuscript.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept