Improved Coresets for Vertical Federated Learning: Regularized Linear and Logistic Regressions
Authors: Supratim Shit
Gurmehak kaur chadha
Surendra kumar
Bapi Chatterjee
Venue: ICML 2025 poster (2025)
Keywords: Vertical Federated Learning
Coresets
Logistic Regression
Ridge Regression
Regularization
Regularized Sensitivity Score
Primary area: general_machine_learning->scalable_algorithms
TL;DR: Novel Coresets for Regularized Linear and Logistic Regressions in VFL.

Abstract: Coreset, as a summary of training data, offers an efficient approach for reducing data processing and storage complexity during training. In the emerging vertical federated learning (VFL) setting, where scattered clients store different data features, it directly reduces communication complexity. In this work, we introduce coresets construction for regularized logistic regression both in centralized and VFL settings. Additionally, we improve the coreset size for regularized linear regression in the VFL setting. We also eliminate the dependency of the coreset size on a property of the data due to the VFL setting. The improvement in the coreset sizes is due to our novel coreset construction algorithms that capture the reduced model complexity due to the added regularization and its subsequent analysis. In experiments, we provide extensive empirical evaluation that backs our theoretical claims. We also report the performance of our coresets by comparing the models trained on the complete data and on the coreset.

Improved Coresets for Vertical Federated Learning: Regularized Linear and Logistic Regressions
Supratim Shit
Gurmehak Kaur Chadha Surendra Kumar Bapi Chatterjee
Abstract
plexity and to avoid overfitting during training. If the model is regularized by user-defined parameter À E R then the loss function is also penalized by X and the model. Thus, it is defined as loss (Z, q. A) = Eigjni f(z, q) + g(), q). where g(-) adds a regularization penalty to the unregularized loss function. In this paper, we focus on regularized logistic regression and ridge regression problems. For the above defined dataset Z, regularization parameter À and set of models Q, the losses of regularized logistic regression and ridge regression for any model q Q are defined as,
Coreset, summary of training data, offers an efficient approach for reducing data processing and storage complexity during training. In the emerging vertical federated learning (VFL) set- ting, where scattered clients store different data features, directly reduces communication com- plexity. In this work, we introduce coresets con- struction for regularized logistic regression both in centralized and VFL settings. Additionally, improve the coreset size for regularized linear re- gression in the VFL setting. We also eliminate the dependency of the coreset size on a property of the data due to the VFL setting. The improvement in the coreset sizes is due to our novel coreset construction algorithms that capture the reduced model complexity due to the added regularization and its subsequent analysis. In experiments, we provide extensive empirical evaluation that backs our theoretical claims. We also report the perfor- mance of our corescts by comparing the models trained on the complete data and on the coreset.
ClassLoss(Z, q. =
In (1 + exp(-y:xx q))
+\||ql11
(1)
RegLoss q,
x y:)² \|ll| (2)
In the vertical federated learning (VFI.) setting, there multiple scattered clients, so no clients have access to the complete feature space. In the VFL setting, we study the setup where the feature space is partitioned between clients. Formally, let there are T scattered clients, we consider that dataset Z is partitioned among all the clients, each having (Z Z ,, Z }. such that no two clients share any features and their union Z. In this work, we present coreset construction algorithms for the following two crucial machine learning problems in the VFL model.
1. Introduction
Let Z be set of points and their corresponding la- bels/responses. Here, Z consists of X E Raad represents the n points in Id space and labels E IR". Let z; repre- sents the jth point (i.c., xx) and its corresponding label (i.c., y:) (see; Section 2 for notation). Let Q be the set of models on which machine learning algorithm optimizes its loss function. Let, the algorithm uses nonnegative function f: Z Q Rzo to compute the loss on the dataset for given model q E Q as, loss Z, q) = Eie(n] (z, q)-
Definition 1.1 (Vertical Regularized Logistic Regression (VRLog)). Given dataset Z consisting of X representing the points and y be their labels in the VFL model, regu- larization parameter À >> 0, the goal of the VRLog problem is to compute vector q E d the server that (approx- imately) minimizes ClassLoss (Z, A) while maintaining minimum total communication complexity.
Regularization is common technique to control model com-
'Department of Computer Science and Engineering, In- draprastha Institute of Information Technology Delhi, New Delhi, India. Correspondence to: Supratim Shit <supratim iiitdacc.in> Bapi Chatterjee <bapi iiitt.ac.in>..
Definition 1.2 (Vertical Ridge Linear Regression (VRLR)). Given dataset Z consisting of X represent- ing the points and y be their responses in the VFL model, regularization parameter À > 0, the goal of the VRLR problem is to compute a vector q E Rd on the server that (approximately) minimizes RegLoss q, A) while main- taining minimum total communication complexity.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Coreset for Regularized Linear and Logistic Regression in VFL
For training model in a VFL setting, the communication cost grows proportionately to the data size, thus entails finding approaches of reducing the training data without compromising the trained model quality. So, to address this issue, we take advantage of coresets. At a high level, a coreset is a small summary of the original dataset that ap- proximates the learning objective for every possible choice of learning parameters. For VRLog and VRLR, we give algorithms that return weighted subset ensuring the fol- lowing guarantees.
algorithm 3. Particularly, in the VFL setup, we show how to aggregate the locally computed scores that it is sufficient to ensure a global guarantee. One of the crucial contributions here is that for both cases, our algorithm effectively captures the reduction in the model complexity due to regularization. We analyze and show that for À > O, the algorithm returns a core- set, whose size decreases with an increasing À (See; Corollary 5.7).
For the VRLR problem, we propose the algorithm 2 to compute the local importance scores for every point at each client. We further show that when these scores are used as input for algorithm 3, the resulting coreset has a size that decreases as the regularization parameter increases (See Theorem 6.1).
Definition 1.3. Let Z be dataset as described in the Def- inition 1.1 in the VFL setting. Let E (0, 1), À >> 0. Let S. be a weighted set, comprising of a subset S C Z with an associated weight function w: S + [1, oc). We call S., an E-coreset for VRLog if with at least 0.99 probability, it guarantees that for every q E Rdd.
Intuitively, regularization reduces the model complex- ity. The model complexity decreases with an increas- ing regularization parameter, A. The size of the core- sets returned from algorithm 3 complements this phe- nomenon. This is due to the importance scores returned by both algorithms I and 2 for VRLog and VRLR, re- spectively. Both algorithm incorporates the regulariza- tion penalty to the original partitioned dataset each client. This dilutes each point's 's sensitivity (see Defi- nition 4.1), which in turn lowers its importance score. As the coreset size depends on the total sensitivity, we meticulously analyze this and show that it is equal to ε and lz statistical dimension (see Definition 5.4) of the data with respect to a regularization À for VRLog and VRLR respectively.
ClassLoss(S.... A) E =1 ClassLoss q. A)
where loss on S., is ClassLoss(SS.... q, A) defined as Eie|ss u(i)- In(1 1 exp(->ı x; 9)) + X||q|/2-
Definition 1.4. Let Z be dataset as described in the Def- inition 1.2 in the VFL setting. Let E E (0, 1). À > 0. Let Sw be a weighted set, comprising of a subset S S Z with an associated weight function w: S + [1, x.). We call S... an E-coreset for VRLog if with at least 0.99 probability, it guarantees that for every q E R.d.
RegLoss(S q. E (1 +) RegLoss( ZZ 9. A):
where RegLoss(S..: q, A) Eie[ss) w (() q- v1)² //
Finally, we performed an extensive empirical evalua- tion for both problems in the VFL setup. Our experi- ments not only support our theoretical guarantees but also show that our algorithm outperforms other coreset construction algorithms in the same setup. We compare the performance in multiple metrics on both training and test data. We also show that the model trained on our coresets is close to the model trained on the full training dataset.
It is important to note that even though we consider a VFL setup, where the features of the dataset have been parti- tioned among multiple clients, however the ensured coreset guarantees are on the loss functions defined on the loss func- tions defined on the complete features of the dataset. Thin inherently possesses some immediate challenges, which we discuss later.
A unified algorithm for constructing a coreset in was introduced in (Huang et al., 2022). For completeness, we restate as algorithm 3. It uses importance sampling for constructing a coreset by computing local importance scores each client for every point. In this paper, focus on constructing a coreset for VRLog and VRLR. Next, we discuss our main contributions in this paper.
2. Model and Preliminaries
Notations: A scalar is denoted by a lowercase letter, e.g., P while a vector is denoted by a boldface lowercase letter, e.g.. x. By default, all vectors are considered as column vectors unless specified otherwise. Matrices or sets are denoted by boldface uppercase letters, e.g., X. Specifically. X denotes an xd matrix where is the number of points (or rows) and the feature space is ıdd Normally, x and x, represents the th row and jth column respectively of the matrix X, unless stated otherwise. We consider the case where n > d. For any p E [1, 2] we denote lp norm for a vector x as ||x||p =
We propose novel algorithm for constructing core- sets for centralized regularized logistic regression (see Theorem 5.6). For the VRLog problem, we employ algorithm 1 to locally compute the importance scores for every point, at each client using l Lewis weights. The computed scores are then served as input to the
2

---

Coreset for Regularized Linear and Logistic Regression in VFL
(Exxf) 1/n The square of the Frobenius norm of a matrix is defined as |||| : Ei z.... For any p (0, oo), except when p- 2, the e, norm of a matrix is defined as |||| E.gel
sampling probability and the coreset size.
4. Coreset Guarantee: Compute the sum of the upper bounds and the VC dimension of the model. Based on these, sampling enough points ensures the desired coreset guarantee.
1/p
In this paper, by default, regularized linear regression would mean ridge regression. Let a and b be two scalars such that, (1 - =)a & b s (1+ z)a. We represent this relation by E (1 + E)a. In asymptotic terms, such as coreset size, we use O() hide logarithmic terms.
The main idea is to ensure that the returned weighted sub- sample is an unbiased estimator with a limited variance.
2.1. Coresets
2.2. Federated Learning
Coresets are weighted samples of datasets (Feldman & Lang- berg, 2011) with provable theoretical guarantees. In general, the size of the coreset depends the optimization function (i.e., its model complexity) and the size of the feature space. For given weighted dataset Z with an associated weight function Z + Rzo, the goal of a machine learning algorithm is to optimize a loss function that uses a function f: Z x Vx x Q- + R2o- Here Q is the set of feasible model parameters. Then for parameter E (0, and 8 (0, subset S C Z with a weight function w S - IR is called an (e, 80-coresttt if it satisfies the following with at least 1- - 5 probability for every q E Q.
Federated learning has become a go-to approach for train- ing machine learning models on a distributed system of clients where communicating data is precluded (Kairouz et al., 2021). Often, the distributed system includes desig- nated node, called server, that stores synchronized state of the model being trained over peer nodes or clients. The server orchestrates the client selection and synchronization methodology. Federated Learning comes in two flavours: (a) Horizontal Federated learning (HFL), where data with entire feature space is available on individual clients; data remains client local and can not be shared with either the server or peer client,
(b) Vertical Federated Learning (VFL), where data is distributed among clients in such a way that they contain a subset of feature space. More formally,
(1 (1-,) q) S f(. q) s (1+c) q).
(3)
For simplicity, we denote the weighted sets as Ze and S.. Our result holds for any arbitrary weight function v: Z R2 and d (0, 1). However, for simplicity in this paper, we assume Z + 1 and 6 = 0.01 for sim- plicity. Consequently, our coresets are e-coresets, which ensures the above guarantees with at least 0.99 probability.
1. HFL: Consider model q and set of clients T. A ba- sic federated learning procedure Federated Averaging (McMahan et al., 2017) is described as
(1) (1) = - 7/ quo 9
qosc cost (Z))
(4)
Vj E S, S [T] Ak E [K 11, Vr E [R]
For both problems, our coreset construction algorithm relies on an importance-based sampling method. Every point in the dataset gets a score that intuitively captures the impor- tance or relevance of the point during the training phase. Points are sampled based on these scores, i.e., point with a higher score will have higher chance of getting sampled. Next, every sampled point uses these scores to define its weight, eventually reflecting its significance during the train- ing. Finally, the set of weighted sampled points guarantees (3). We have used a standard coreset construction frame- work (Feldman & Langberg, 2011; Chhaya et al., 2020a) that comprises the following steps.
1
S K
9++1
J.
JES.
where at each synchronization round r E |R] S, S [T] clients participate in local training for K - 1 steps following (4). 1j > 0 is the learning rate, which we take as a constant for simplicity. They synchronize at the server by averaging the local models in (5). The clients j E [T] store local data Z() The server sends the synchronized state back to a new subset of clients at every synchronization round r E [R].
Horizontal federated learning suffers from heterogene- ity in data distribution and participation frequency across clients. To address the issues, several improve- ments have appeared in the literature: FedProx (Li al., 2020), SCAFFOLD (Karimireddy et al., 2020), Adaptive Federated Optimization (Reddi al., 2020) some of the well-known methods.
1. Importance Score:
For a given dataset and an opti- mization function, we define function (aka sensitivity function) that captures the importance of every point with respect to the complete dataset.
2. Distribution: Next, we derive a tight upper bound for these functions and define a distribution.
3. Weighted Sample:
Sample points based on the distri- bution and assign weights inversely proportional to the
2. VFL: Here over a set of clients T we consider the partition of feature space of data. We denote the dataset
3

---

Coreset for Regularized Linear and Logistic Regression in VFL
with subset of features partitioned over client set [7] as x such that Uj X() X. Thereby, basic
The closest to our work is (Huang et al., 2022). They pre- sented framework for coreset construction for regularized linear regression and k-means clustering in the VFL setting, As discussed, the complexity of VFL is directly related to the dataset, which has the same cardinality across clients. Clearly, constructing coresets directly reduces data process- ing and benefits the communication overhead. Compared to (Huang et al., 2022), our work improves by (1) giving a new coreset construction for regularized logistic regression, (2) ensuring the coreset size for ridge regression is optimum.
VFL scheme can be described in (6).
Client j E [T] computes V qun 9.)).
U V cost((X (0), )!
9,+1 = 9r - 17
jE(T]
Vr E [R]
Vj E [T).
(6)
In VFL setting the server orchestrates the accumulation of gradients computed at the clients before performing step of gradient descent. The cost of communica- tion is very high as the server has to wait for gradient accumulation and therein a perfect synchronization. Furthermore, each client has to participate in the pro- cess, and one step of the gradient update includes a full pass over each client. An early work on VFL appeared in (Hardy et al.. 2017). A recent survey on VFL can be found in (Liu et al., 2024).
4. Coreset Construction in VFL
We first state our VFL setup. Consider the dataset Z, con- sisting of X representing n points in IRd and y E IR" rep- resenting their labels. We have [I'] scattered clients such that every client has only limited access to the feature space, and no two clients share any features. A client j E [7] has access to all the points but only limited number of features, which is represented by z Now we describe the datasets for both problems in detail.
3. Related Work
VRLog: Z E IRa be the datset where, z; = -- X; E Rd for every E [m]] Hence, for every client j E [T]. ZO)
Coresets have been extensively studied for numerous ma- chine learning models, ranging from clustering (Feldman & Langberg, 2011; Cohen-Addad et al., 2021; 2022: Shit et al., 2022; Chhaya et al., 2022), regression (Avron al., 2017; Chhaya et al., 2020a), classification (Mai al., 2021; Tukan et al., 2022) to deep neural networks (Mirzasoleiman et al., 2020; Maalouf et al., 2022). The regularized machine learning models are common in practice, but to the best of our knowledge, the study of their coreset construction algorithms limited to a few models (Avron et al., 2017: Chhaya et al., 2020b; Ranjan& & Shit, 2024). In this work, we introduce coreset construction algorithm for regularized logistic regression in both centralized and VFL setups. We also improve the coreset size for regularized regression, but in a VFL setup. Lewis weights (Lewis, 1978) are used for coreset construction in a centralized setup where preserving lp subspace is important for real value of p (Cohen & Peng, 2015; Fazel al., 2022).
Ruxd; where 2, = -y; x for every i E [ri]. Here, Σ d = d. Let > 0 be the regularization parameter.
VRLR: Z E Raxd+1 be the dataset where z; = [x,, vil E Rd+1 for every i E [m]. Hence, for every client j E [7 - 1), Z E Raxd, where 2,") x!") for every
[m]. For
the client T, (T) E Raxdr where z; (T) = [x] (T) ..] for
every [m]. Here, Σ de = d + 1. Let À 0 be the
regularization parameter.
For both problems, we use the sensitivity framework for importance sampling, which relies on importance scores (sensitivity scores) of every point. Key challenges in this framework are obtaining a tight upper bound on the sensi- tivity scores and bounding the total sensitivity. Getting a tighter upper bound on sensitivity scores is often as expen- sive as solving the actual problem (Braverman et al., 2021), Here, we show how coresets can significantly reduce com- munication overhead while training a model in VFL. We accomplished this by addressing the following challenges.
Today, the literature on federated learning is sufficiently mature with ever-improving developments. A comprehen- sive report on the promises of this framework appeared in (Kairouz et al., 2021). Improving federated learning via coreset construction has attracted only limited attention from the research community. (Sivasubramanian et al., 2024) pre- sented a horizontal federated learning method where, at every synchronization round, the gradients are computed based on coreset of local data that uses submodular func- tions, which are not tractable. Given the limited size of data available on a large number of clients in the majority of horizontal federated learning applications. the impact of such a construction is potentially limited.
Pl:
Even in the VFL setup, our coreset guarantees hold for the global model, similar to centralized setting where standard sensitivity scores are well-defined. These bounds are typically derived by functions that have access to the complete feature space. However, in a VFL setup, where clients only possess partial feature sets, determining a tight upper bound on the sensitivity score is unknown.
P2: The model complexity of machine learning algorithm
4

---

Coreset for Regularized Linear and Logistic Regression in VFL
reduces due an added regularization. As result, is natural expect smaller coreset size for this problem compared to unregularized version of the problem. However, designing an algorithm that captures the re- duced model complexity for a general problem through the sensitivity scores and then using them to quantify the size of the final coreset is unknown.
Next, for both problems, we define function for every point and every client such that the aggregation of the functions for every point from different clients ensures tight upper- bound on the sensitivity of the complete sigh-dimensional points. These are then further used to sample points and as- sign appropriate weights to them. We use the unified coreset construction algorithm from (Huang et al., 2022), which we state as algorithm 3 in the appendix for completeness. Here, we describe the overview of the algorithm.
We first introduce the sensitivity scores that capture the im- portance of point under the reduced model complexity in a centralized setting. In our definition, regularization inherently reduces the importance of each point, As the reg- ularization parameter increases, sensitivity scores decrease accordingly. This is intuitively correct as higher regulariza- tion leads to smaller model weights (or norm). The optimal model tends to a zero vector for a very large regularization parameter A. In such a case, the sensitivity scores would also be close 0 (i.e., negligible importance of every point). Definition 4.1 (Regularized Sensitivity). Let Z be dataset with points along with its labels. Let Q be the feasible model space and X Ry0 be a regularization pa- rameter. Let, loss(22 ZZ q, A) = Ei= fzz q) + 9(,, q) for every q E Q. Then for every point i E [n]] we define the regularized sensitivity score as,
A Algorithm Overview: The algorithm uses scores g'
[g] ........hh g..)g for every client j E [T]. Next, every j E [T] shares its local sum of scores, G with the server. Using these values, the server computes distribution over [T] and samples set of clients C C T. Here, clients with higher GD3 will have a greater likelihood of being selected by the server. Next, it asks every selected client to sample [m/t] points and send their indices to the server. This ensures that the union of the sampled indices forms a set S, with expected size of B[[S]]] = m. Finally, based on the received indices, the server determines the weight function w for all the sampled indices S and returns the weighted set Sw where S S Z and w: S 3 R>0-
Vertical Federated Optimization: At every round r E [A] the server makes a call of Algorithm to compute a coreset S.d of size m. It then informs Sw to the partic- ipating clients j E
fzz q) qe loss Z A)
8; == sup
[T] to compute the local gradients ( using S... Similar to the equation 6, the server then collects the gradients to update the model as 9r+1 qr 11--11 17 Ujtm Vata loss(S
V (os))
In the above definition, the importance of every point i E [n] is quantified by 8;, which is the supremum of the relative loss of the point to the complete regularized loss over all feasible models. Notice that the sensitivity scores can be any value between 0 and 1. Further, as À increases, the sensitiv- ity score decreases. Hence, compared with unregularized machine learning model for any À= > O, we get tighter sensitivity score. We exemplify this further. For simplicity, assume the number of clients to be 1, which can be easily extended to setup with multiple clients. Let X be a dataset with n points in Idd such that n/d- = c where is a positive integer. Again, for simplicity, the case of ridge regression, the response vector y is zero vector, and for regularized regression, it is all vector in n-dimensional space. Let X = [I. ....... I] E Rdxx where I is identity matrix. In (Huang et al.. 2022), the sensitivity score for every point in the ridge regression problem is at least 1/c. Hence, the total sensitivity for n points is ni/c = d, which directly affects the final coreset size. Notice that is irrespective of the fact whether X is or a positive scalar. So, in such a case, our sensitivity scores are 1/(c 2). Hence, the total sensitivity score is nt/ce + A) < n/cc = d. In fact, for higher values of X, the total sensitivity score could be significantly smaller. So, theoretically, the improvement in the coreset size is at least by a factor of c/(c + A). For our algorithm, obtaining a tighter upper bound on these functions is sufficient.
(1)) q .).
5. Coreset Construction for VRLog
Here, we present how to compute the scores g, for every client j E [T] and every point i E [m] for VRLog. For simplicity, we start with the case where T = 1 and bound the sensitivity scores. To get a practical bound, we use a data dependent property known as j-complexity of the dataset, as introduced by (Munteanu & Schwiegelshohn, 2018).
Definition 5.1 (μ- (u-Complexitt). For a given dataset Z e R and a vector q E RRd let (Zq)* and (Zq) - be vectors having only positive and negative entries respectively. Sim- ilarly (q)+ and (q) are defined. Then the p-complexity for the regularized logistic regression with a regularization parameter À is defined as,
(Zq) + 111 + Al| (9) 111
(Z, = sup
qERdN( ((0) [Zq) + X/| (9)-1)
Notice that due to sup, 0. we have , A) 2 1. I
implies م (ll - 11 + X1( Il) < [Z))+ +
(l[(q) +11 S a (I (l)) 1l1 + +A](()) l1.) For brevity, we refer to (Z, A) simply as μ in the future. W We consider
5

---

Coresct for Regularized Linear and Logistic Regression in VFL
an augmented matrix zT= = (Z' T, AT). In the following lemma, show that the lz norm of the orthonormal column basis of ZZ is the upper bound of the sensitivity scores.
looks like hinge, which is why the l Lewis weights used to preserve the sum of absolutes, i.e., the essential part of the hinge function. Since Z E Rnad considered to be full rank, so for p = 1, D-DD-// U/2U being orthonormal column basis of Z, it ensures that the sum of & Lewis weights is | := [D 1/2 U = d. This is due to the existence of the Lewis Basis (Musco et al., 2022). We give a simple proof in the appendix for completeness.
Lemma 5.2. Let Z E B be p-complex dataset. Let > O, and U be an orthonormal column basis of Z. Then the sensitivity scores for every i E [n].
fizi ①) ClassLoss(Z, 4.
S 20 + 1D) (Vuju++))
sup qead
Now, for the regularized logistic regression, focus the augmented matrix Z == AI
Z
To prove the above lemma, we analyze two possible cases 2, q 2 0.5 and 2 < 0.5 for every q E Rdd Detailed proof has been discussed in the appendix. The sensitivity scores remain tight as they effectively capture the impact of the regularization parameter.
which is (n + d) x d size
matrix. The algorithm computes the & Lewis weights for 2. Now, in our VRLog problem, we use the Lewis weights for computing the gi for every client j E [T] and every point E [ni]. score for every point e [n]]
Let, A E Rexd be matrix with singular values are {o,) Given a scalar À >> 0 the statistical dimension is defined as sd{ [ 2) = Σ
Algorithm 1 Weights for VRLog
Additionally, it is known that
Input: Each client j E [T] holds data (X(), y) and a real number À >>> 0
the VC dimension of logistic regression is d + 1. So, there a E-net of queries of size O (2)" (Matoušek, 1993).
Output: Scores g g()) E RR0 I: Compute Zú) R=xd, from (x6),
Using standard coreset construction framework, for E (0, 1). if the final coreset size is O V /...diZ.A.2))000((1
2: Compute 20) ZZ
ALd,
6²
3: return g ()) ;= LewisWeight(2 1)
then using Bernstein's 's inequality and taking union bound over the s-net, we get an e-coreset for regularized logistic regression with probability 0.99.
Algorithm Overview: augmented dataset Ž is feature-wise partitioned among scat- tered clients as governed by the original partition of Z, where 2 = - x for every i e [ni]. It then computes the & Lewis scores for all the n + d rows, locally at each client. However, the algorithm only returns the first scores, which are subsequently used by the algorithm 3 to define distribution and sample an appropriate number of points. The final coreset size depends on the p-complexity and the statistical dimension of Z with regularization À for l, The statistical dimension for ls has been defined in (Avron et al., 2017; Ranjan & Shit, 2024). For p = 1, we define the statistical dimension for E follows.
The algorithm 1 considers that the
Notice that the coreset size is still function of /n. We get rid of this dependence due to an improved analysis of our sensitivity-based coreset construction algorithm using Lewis weights.
Theorem 5.3. (Lewis, 1978) Let Z be d-dimensional col- umn space in Rn and a fixed 1 S p < co. Then, there exists basis matrix U that spans the column space of Z. The matrix U is called lp Lewis Basis of Z if DP/2-1U is orthonormal matrix, where D is diagonal matrix such that Da: = Vu, un for every E [n]].
As Lewis basis U is basis for the column space spanned by Z. hence due to row operation on U by a positive definite matrix D does not alter its column space. As result, the orthogonal matrix D spans the same column space of Z, making it orthonormal column basis of the matrix.
Definition 5.4. Given a matrix A E Rnxd and real posi- tive value X, let U be the E Lewis basis of A and for {o be the singular values of M where M U DD/221A A. Then the statistical dimension for & is sd(A,),1) = Σ
In (Mai et al.. 2021), it was shown that for models such as logistic regression and hinge loss, sampling points propor- tional to the & Lewis Weights ensures coreset guarantees. For every row E [n]] its lewis weight is ||u,|[ where u; the ith row vector of U. For a p-complex dataset Z the desired coreset size for unregularized logistic regression is d
The statistical dimension of matrix in lp is important parameter: One of the main results in the paper is Lemma 5.5, which is the foundation for bonding the coreset size for regularized logistic regression. We bound the total Lewis scores of the first n points of the matrix Z.
[Corollary 9 (Mai et al., 2021)]. The unregular- ized logistic regression implies that À = O. This is due to the fact that the logistic regression classification loss function
Lemma 5.5. In lemma 5.2, let U and Ü be the l Lewis basis of Z and Z respectively. Then the sum of & Lewis
6

---

Coresct for Regularized Linear and Logistic Regression in VFL
weights of first n points in U is sd(Z, X,1). Here M UP/22-1Z such that D is the diagonal matrix defined from U.
6. Coreset Construction for VRLR
In this section, we present an improved e-coreset for VRLR compared to (Huang et al., 2022). Recall the input dataset Z and its partition among clients for this problem. Our al- gorithm uses importance sampling and follows the unified framework. We propose new algorithm that computes a tighter bound of the novel sensitivity scores (see Definition 4.1). Through improved analysis, we not only reduce the coreset size but also eliminate the dependence on a dataset property that is influenced by the partitioning among the clients (Huang al., 2022). This parameter can grow as
We prove the above lemma in the appendix. Now, using the lemma 5.5 and Corollary 9 in (Mai et al., 2021), we have the following theorem, which is our main result for regularized logistic regression in the centralized setting.
Theorem 5.6. For a given Z, let À > 0 be a regularization parameter. Let Z be the augmented matrix. I Z be μl- complex dataset. Let algorithm I computes the scores g! for every j E (T) Then if then the size of the returned set from algorithm 3 is O (,)
large as Tmav (mmnn [Z) where max and min are the largest and the smallest singular values of the dataset Z. An adver- sary can generate dataset where this property is arbitrarily large. In contrast, our approach ensures that the coreset size is independent of this parameter, and instead it only depends on T (number of clients). Now, we present our algorithm for computing the g scores for every i [n]] at each client E [T] for the VRLR problem.
) then the set if an e-coreset VRLog with one client.
Lewis weights can be approximated by iterative algo- rithm (Cohen & Peng, 2015). We restate it as algorithm 4 for completeness. Notice that even though it is an iterative algorithm, the weights are always non-negative. Hence, we finally get a vector g representing the Lewis weights of all the rows of the input matrix.
Algorithm 2 Scores for VRLR
Input: Each client j E [T] holds data (x6), y] and a real number À >>> 0 Output: Scores g()) E ER
It is known from 5.2 or (Mai al., 2021) that the sensitivity scores for logistic regression are upper bound by a function that is proportional to the &2 norm of its corresponding in its orthonormal column basis. These are effectively the square root of the leverage scores, which is upper bounded by a function proportional to v (see Lemma 5.2). However, in the case when an orthonormal column basis is constructed from the Lewis basis, we get much tighter upper bounds.
1: j == then
X(T) ))
2: Compute 2(T) = (VAld 0)
3: else
X(1)
Compute 200 == VALe,
5: end if
6: return g(d) = LewisWeight
Now, consider the VFL setting with T clients, such that every j E [T] has access to ( E R and Ejerrj d, d. The sensitivity scores on the complete feature space can be upper bounded by the sum of local upper bounds and a factor that is proportional to T. We have discussed this in detail in the appendix.
Algorithm Overview: In algorithm 2, each client j con- siders a partition of 2 earlier. It computes tight upper bound of the sensitivity scores for their local data 26), It computes the local leverage scores (&2 Lewis weights) at each client j for every rows of 2ú) For a tall and thin matrix, these are the squares of the f2 norms of the rows of its orthonormal column basis. So, every client j E [T]. computes the orthonormal column UG) for 20) These computation happens in algorithm 4 where we set p = 2. Then for every E [m]] and every j E [T] the algorithm LewisWeightt)) computes a score g (3) = |lu 122 Finally it returns an n n-dimensional vector g for every client j E [T'
Notice that algorithm 4 gets p = 1. For every client j (T). the algorithm takes Ondz)) to return the Lewis weights g: (i) for every E [n]. The following corollary states our coreset guarantee for VRLog.
Corollary 5.7 (Coresets for VRLog). For a given dataset Z and a scalar X >> O, let Z be the augmented matrix such that it is partitioned among T clients. For every j E [T], as 200 E Rgndd, If Z be a μ-complex dataset then the algorithm 3 computes E-coreset (see; Definition 1.3) in ((dd) of size m = (TTET sd(z's) A.1) for some
These scores are finally used by the algorithm 3 to sample points. The points returned by the algorithm 3 ensure the following guarantees.
Theorem 6.1 (Coresets for VRLR). Let Z be the given dataset, partitioned between T 2 1 clients and E E (0. 1). The algorithm returns a e-coreset for VRLR (see; Def-
E E (0, 1) and the model can be trained with communication complexity Om.)).
7

---

Coresct for Regularized Linear and Logistic Regression in VFL
inition 1.4) of size mn = O T sd(z)),,,2) log(d)
T
Here, we use Matrix Bernstein's inequality (Tropp al., 2015; Chhaya et al., 2020a) prove the above lemma, which has been deferred to the appendix. The above lemma proves that difference between the covariances of the coreset and the full dataset along with the regularization parameter is PSD bounded, i.e, (1+ T Z + AD) - S + AI = 0 and STS... + AI - (1 - e) Z + AI) > 0. As, it ensures ridge lz subspace embedding, hence for every query vector q Rd we have, || || - (IZall + \l) Finally, it ensures the desired guar- antee in Theorem 6.1.
in
g²
imput sparsity time ((nzz(Z)) such that with probability at least 0.99. A model can be trained on this coreset with communication complexity (mmT).
We prove the above theorem using multiple lemmas. Our first lemma one of the important lemmas that gives a tight upper bound on the sensitivity scores in a VFL setup.
Lemma 6.2. For every point i E [m] and client j E [T]. the scores returned by the Algorithm 4 for VRLR, g! 11. Let U(), U U(T) be the orthonormal col- umn basis of ( _ point i E [r] the regularized sensitivity scores can be upper bonded as,
..... TT) respectively, then every
7. Experiments
We have conducted experiments for both regularized logis- tic and regularized linear regression 1. We have considered three datasets: (1) Credit Card for VRI.og problem, (2) Fi- nancial, and (3) Blog Feedback for VRLR. We have first partitioned each dataset into a training and a testing set (80:20). Further, for both problems, we have considered the number of clients to be 3, i.e., T == 3. We compare the performance of our coresets with various other sam- pling techniques. Once we have a sample from one of the sampling methods (including ours), we train an appropriate model (i.e., either regularized logistic or ridge regression). Next, we use this model to compute the training loss, test accuracy, model closeness, and training time for the VRLog experiment. For VRLR, we have reported test RMSE and model closeness. We have repeated each experiment 10 times for every sample size and reported their medians.
( q y1
sup
ST.
12
[qq y1 + 1
is important to note that the bound on the sensitivity scores of the points for ridge regression a function of T, i.e., the total number of clients and the aggregation of locally computed leverage scores. To compute these scores, the algorithm computes thin SVD of 20), This is the most computationally expensive operation, which takes ((ndf) time. However, this running time can be significantly im- proved using randomization techniques. Leverage scores can be approximately computed in input sparsity time, i.e.,
(mnz(Z()) (Woodruff et al., 2014).
Our next result gives tight bound on the total sensitivity scores. Like VRLog, the total sensitivity is a function of the regularization parameter \ and Z.
We have considered Credit Card data, which is binary class dataset, with imbalanced class sizes. Our algorithm is Auglewwis (Algorithm 1), and the rest of the sampling methods are- (1) Uniform: points sampled uni- formly at random. (2) HLSZ: Points are sampled based on the sampling method in (Huang et al., 2022). (3) SqLev: it is a heuristic sampling method, where the dataset is parti- tioned into two sets based on the labels. From both sets, we use the square root of leverage scores for sampling points (Munteanu et al., 2018). (4) Lewis: Uses &, Lewis weights of only dataset for sampling points.
VRLog:
Lemma 6.3. For the given regularization parameter X, the total sensitivity scores or the sum of the sensitivity scores in the VFL setup with [T] clients are upper bounded by O (T. Ej-ss(Z()) sd(Z()) )
For every j E [T] the sd( X, 2) is the la statistical dimension of Z with respect to A. As the A increases, the statistical dimension decreases, thereby decreasing the bound on the total sensitivity score. The proof is discussed in the appendix. Finally, with the following lemma, we prove that the approximation guarantee holds along every direction in the complete feature space.
In Figure 1, we have reported the training loss, balanced accuracy on test data, model closeness, and training time. Recall that in Corollary 5.7 our coreset ensures a E approx- imation guarantee on the training loss. The leftmost plot corroborates our theoretical guarantees.
Lemma 6.4. For a given Z E [=x(d+1) be the augmented matrix, let x >> O be a scalar and & E 10, The algorithu 3 samples a set S C Z with uppropriate weights w : S + E20- We represent the weighted set as S.. If the size S is T sd(z(5) .x,2) log(d)
We further observe that our coreset gives balanced accu- racy on par with the test dataset. Even though there are no known theoretical guarantees for models trained on coresets and models trained on the complete data, we observe that
at least O
then the set ensures the following guarantee with at least 0.99 probability.
Codes available Gel1-tiita/Coresttro
at https://github.e
(1 (Z (ZTZ+) Z AT) = ST + AI < (1 + (Z Z+ AI)
8

---

Coreset for Regularized Linear and Logistic Regression in VFL
Unifor SoLoy Lirats
Relativ Conffic Cre offorrencc
Uniform
H157
SqLev
Test Recurets
Uniform
Lewis
65
AugLewis
H152
AugLewis
Solev
04
07
Lawkis
120
LugLewis
100
SQLeY
Lewis
0.-
Auglews
300
1003
1565
2000
2000
300
U008
2200
2500
2200
1900
2000
3500
3000
10000
2000
2000
Sample
Sample 5:20
Sample Siz
Sample
Figure 1. vRLog Coreset Performance (Credit Card)
HE.2
Reastrre Coefiidnt Difforencc
HLS2
183
14.2
Rolutive Coefidiont Difforence
Lev
23
Lev
Tie XURET
"eet RARSE
0
E
23
Sample Size
Sample Size
Sample Size
Sample Size
Figure 2. VRLR Coreset Performance (Blog Feedback, Financial Dataset)
the model trained on our coresets is closer to the model trained on the complete data, compared to a model trained on the HLSZ sample, only SqLev outperforms. Overall, our coresets are either matching or outperforming in terms of balanced accuracy on the test dataset compared other coreset construction methods. The SqLev and Lewis al- gorithms are very close to the AugLewis. However, these algorithms have poorer theoretical guarantees, such as the sizes of the coreset are (V)n) and 0( respec- tively. In terms of training time, with our coresets training a model around 80x to 100x faster compared training model on the complete dataset.
in constructing coresets for VRLog problems.
For the VRLR problem, we used the Blog Feed- back dataset and financial data. We compare our sampling method (Algorithm 2) with a naive Uniform sampling and Leverage Score sampling (Huang et al., 2022). In Figure 2, reported the test RMSE and the model closeness between models trained on the coreset and model trained on the complete dataset. In both parameters, our algorithm (Lev) clearly outperforms the other sampling methods, which are uniform sampling and the sampling method from (Huang et al., 2018). It verifies our theoretical claim that using regu- larized sensitivity scores (see Definition 4. 4.1), our sampling method achieves smaller RMSE and parameter closeness compared to others. Hence, Lev is superior to its competi- tors for the VRLR problem.
VRLR:
Samples-
500
2500
Methods
Train
Test
Train
Test
Uniform
0.8192
0.8185
0.8723
0.8731
HLSZ
0.8704
0.8712
0.9071
0.9078
Conclusion
Lewis
0.9220
0.9230
0.9304
0.9315
AugLewis 0.9330
0.9343
0.9319
0.9331
In this paper, we highlight the advantages of using core- sets in Vertieal Federated Learning (VFL). We introduce smaller coresets for regularized logistic regression in both centralized and VFI. settings. Additionally, we demonstrate how a global guarantee on loss functions, utilizing the full feature space, can be achieved while maintaining data pri- vacy among clients. We further enhance the coreset size for regularized linear regression in VFL, making independent of data-dependent parameters. Notably, the regulariza- tion parameter À increases, model complexity decreases trend observed in both coresets. This relationship was em- pirically validated through our experiments.
Table I. scores on the Credit Card dataset.
We also compared the Fl scores between all the sampling methods on the Credit eard datasets. We observe table I that even though there are no known theoretical claims, from our any other coreset for logistic regression, our algorithm is always better than other sampling methods for various sample sizes.
Based on both empirical evidence and established theoreti- cal guarantees, our algorithm 1, which leverages regularized sensitivity scores, offers greater reliability and superiority
9

---

Coreset for Regularized Linear and Logistic Regression in VFL
Acknowledgment
Streaming coresets for symmetric tensor factorization. In International Conference on Machine Learning, pp. 1855-1865. PMLR, 2020a.
Supratim acknowledges the kind support from Data- Heroes Ltd and Anusandhan National Research Foundation (ECRG/2024/000959) The work was partly supported by their generous fund.
Chhaya, R., Dasgupta, A., and Shit, S. On coresets for regularized regression. In International conference on machine learning, pp. 1866-1876. PMIR, 2020b.
Bapi acknowledges support in part by the Indo-French Centre for the Promotion of Advanced Research (IFC- PAR/CEFIPRA) through the FedAAttoMoDL project and the Infosys Center for Artificial Intelligence (CAJ) at IIIT-Delhi through the Scalable Federated Learning project. He also acknowledges support by Anusandhan National Research Foundation under project SRG/2022/00229..
Chhaya, R., Dasgupta, A., Choudhari, J., and Shit, S. On coresets for fair regression and individually fair clustering. In AISTATS, pp. 9603-9625, 2022.
Cohen, M. B. and Peng, R.
L p row sampling by lewis weights. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 183-192. ACM, 2015.
Impact Statement
Cohen- Addan, V., Saulpic, D., and Schwiegelshohn. C. A new coreset framework for clustering. In Khuller, S. and Williams, V. V. (eds.), STOC '21: 53rd Anmual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pp. 169-182. ACM, 2021.
The paper presents an advancement in coreset construction algorithms problems vertical federated learning. There are no societal impacts that need any special mention, wiiliil
Acknowledgment
Cohen-Addad, V., Larsen, K. G., Saulpic, D., and Schwiegelshohn, C. Towards optimal lower bounds for k-median and k-means coresets. Proceedings of the firty-fourth annual ACM symposium on Theory of com- puting, 2022.
Supratim acknowledges the kind support from Data- Heroes Ltd and Anusandhan National Research Foundation (ECRG/2024/000955) The work was partly supported by their generous fund.
Fazel, M., Lee, Y. T., Padmanabhan, S., and Sidford, A. Computing lewis weights to high precision. In Proceed- ings of the 2022 Annual ACM-SIAM Symposium on Dis- crete Algorithms (SODA), pp. 2723-2742. STAM, 2022.
Bapi acknowledges support in part by the Indo-French Centre for the Promotion of Advanced Research (IFC- PAR/CEFIPRA) through the FedAutoMoDL project and the Infosys Center for Artificial Intelligence (CAl) at IIIT-Delli through the Scalable Federated I Learning project. He also acknowledges support by Anusandhan National Research Foundation under project SRG/2022/00229..
Feldman, D. and Langberg, M. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of comput- ing, pp. 569-578. ACM, 2011.
Impact Statement
Hardy, S., Henecka, W., Ivey-Law, H., Nock, R., Patrini, G., Smith, G., and Thorne, B. Private federated learn- ing on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint 1711 2017.
The paper presents an advancement in coreset construction algorithms problems vertical federated learning. There are no societal impacts that need any special mention.
References
Huang, L., Jiang, S. H.-C., Li, J., and Wu, X. Epsilon- coresets for clustering (with outliers) in doubling metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 814-825. IEEE, 2018.
Avron, H., Clarkson, K. L., and Woodruff, D. P. Sharper bounds for regularized data fitting. Approximation, Ran- domization, and Combinatorial Optimization. Algorithmss and Techniques, 2017.
Huang, L., Li, Z., Sun, J., and Zhao, H. Coresets for vertical federated learning: Regularized linear regression and k-means clustering. Advances in Neural Information Processing Systems, 35:29566-29581, 2022.
Braverman, V., Feldman, D., Lang, H., Statman, A., and Zhou, S. Efficient coreset constructions via sensitivity sampling. In Asian Conference Machine Learning, pp- 948-963. PMLR, 2021.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji. A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in
Chhaya, R., Choudhari, J., Dasgupta, A., and Shit, S.
10

---

Coreset for Regularized Linear and Logistic Regression in VFL
federated learning. Foundations and trends@ in machine learning, 14(1-2)11-210, 2021.
Ranjan, S. and Shit, S. Accurate coresets for latent vari- able models and regularized regression. arXiv preprint arXiv:2412.20118 2024.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averag- ing for federated learning. In International conference on machine learning. pp. 5132-5143, PMLR, 2020.
Reddi, S., Charles, Z.,, Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S., and McMahan, H. B. Adaptive federated optimization. arXiv preprint arXiv:2003.0029: 2020.
Lewis, D. Finite dimensional subspaces of lp. Studia Math, 63:2. 207-202, 1978.
Shit, S., Dasgupta, A., Chhaya, R., and Choudhari, J. Online coresets for parameterie and non-parametric bregman clustering. Transactions Muchine Learning Research, 2022.
Li, Sahu, A. K., Zaheer, M.. Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429-450, (1129945000000 2020.
Sivasubramanian, D., Nagalapatti, L.,, Iyer, R., and Ramakr- ishnan, G. Gradient coreset for federated learning. In Proceedings of the IEEE/CVF Winter Conference on Ap- plications of Computer Vision, pp. 2648-264355 2657,2022 2024.
Liu, Y., Kang. Y., Zou, T., Pu, Y., He, Y., Ye, X., Ouyang, Y., Zhang, Y.-Q., and Yang, Q. Vertical federated learning: Concepts, advances, and challenges. IEEE Transactions on Knowledge and Data Engineering, 2024.
Tropp. J. A. et al. An introduction to matrix concentra- tion inequalities. Foundations and Trends@ in Machine Learning, 8(1-2)11-230, 2015.
Maalouf, A., Eini, G., Mussay, B., Feldman, D., and Osad- chy, M. unified approach to coreset learning. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Tukan, M., Wu, X., Zhou, S., Braverman, V., and Feldman, D. New coresets for projective clustering and applications. In International Conference on Artificial Intelligence and Statistics, pp. 5391-5415. PMLR, 2022.
Mai, T., Musco, C., and Rao, A. Coresets for classification- simplified and strengthened. Advances in Neural Infor- mation Processing Systems, 34:1 1664-11654, 2021.
Woodruff, D. P. et al. Sketching as tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-155) 2014.
Matoušek, J. Epsilon-nets and computational geometry. In New Trends in Discrete and Computational Geometry, pp. 69-89. Springer, 1993.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effiiee. learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Mirzasoleiman, B., Cao, K., and Leskovec, J. Coresets for robust training of deep neural networks against noisy la- bels. Advances in Neural Information Processing Systems, 33:1 (414-11477,, 2020.
Munteanu, A. and Schwiegelshohn, C. meetosss and history: A theoreticians design pattern for approxima- tion and streaming algorithms. KI-Künsttliche Intelligenz, 32(1):37-533 53, 2018
Munteanu, A., Schwiegelshohn, C., Sohler, C., and Woodruff, D. On coresets for logistic regression. Ad- vances in Neural Information Processing Systems, 31, 2018.
Musco, C., Musco, C., Woodruff, D. P., and Yasuda, T. Active linear regression for Ip norms and beyond. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 744-753. IEEE, 2022.

---

Coreset for Regularized Linear and Logistic Regression in VFL
Appendix
Here we present all the missing (or known) algorithms for completeness and discuss all the proofs that are missing the main paper.
A. Missing Algorithms
Here we state the known algorithms used in our coreset construction for completeness.
A.1. Unified Framework
The unified framework from (Huang al., 2022) is as follows.
Algorithm 3 Unified Coreset for VFL
Input: Each client j E [T' has data Z vector g()) I", integer m 2 for coreset size.
Output: Weighted Set S..
1: Each client j (7) sends G(J) = Eie(ni Di
(i) to the server.
2: The server computes := ΣjE( G(i and samples a client subset C [T'] of size t, where each client j E [T] is
sampled with probability G G.
3: Each client j C, samples subset (t) C [n] of size [m/t], where each point i [n]] is sampled with probability
GGT and sends (O) to the server.
4: The server broadcasts S + Usetz 5t1) to all parties.
Each client j C sends { ( i E $s to the server.
6: For every point i S, server computes weights w(i) + 1s1-E,emn 9
7: return weighted set ...
A.2. Lewis Weights
The algorithm to compute Lewis Weights (Cohen & Peng, 2015) is as follows.
Algorithm 4 LewisWeight
Input: A matrix X, an integer p E (1,2)
Output: g R
1: n = #row(X)
2: W I,
3: for 1... 10 do
4: for 1...n do
5: Set Wi: + (x. (X W -1 -1x;)
6: end for
7: end for
8: return = diag(N W)
B. Proofs of VRLog
B.I. Proof of Lemma 5.2
Lemma B.1. Let Z Raad be p-complex dataset. Let A > O, and U be orthonormal column basis of Z. Then the sensitivity scores for every i E [n],
ClassLoss(Z, q. S 200(1 +1) (Vulu, ) m
f(z,, 9)
sup qERa
12

---

Coreset for Regularized Linear and Logistic Regression in VFL
Proof. Let [n] and q, E arg maxq Classoos
((),9)) We prove the theorem by considering two cases.
1. 2 q: 2 0.5
2. z/qq: 9: 0.5
Case 1: z qi 0.5
Proof. Consider QR decomposition 2 as Z UR. Here U is an orthonormal basis for the column space Z. When 0.5 < 2 q and monotonicity of that
f (z, q)
= f (z. q)
(q)
([
(8)
ff ([lu/ll/|URqq]
[|u:|l2||aal]
2/uu, lz Zqll2
WV IA
2/uu, 1z /alli
2/uu, (2(1 + (+) (2q) 112
W 14
2|uu, (2 + p))
Σ
f(z, 9) + >|a
jiz, 920
2|uu, (2(1 + (1) Classloss Z, A).
(7)
The inequality (i) is due to Cauchy Schwarz. Since an orthonormal matrix which is invariant towards Eg have the equality (it). For sufficiently large ja/. have |a| fa) I 2/a|; due to this, get the inequality (tit). The inequality from the y-complexity of Z. Finally we get the equation (7).
Case 1: z! q, 0.5
Note that f(-2) 1/100 and Proof. Let K- (j [n] 2. 22 and K+ (j E [n] 2 -2}.
f(2) q) & f(0.5) < 1. Also, n K + K- Thus if KK
2
n then
2
ClassLoss(Z. q.
Σ flz] q) + A|la/1
200
Iv
f(x] q).
(8)
200
We have the inequality (i) because z,J q > -2 and such cases f(-2) 2 1/ 1/100 further |K+1 n/2. Now, if [K
<
then K 2 n. Further, fzzJ q) S so we get the equation (8).
ClassLoss(Z,, Z. q.
IV IV8 IV
[Zq + \ll9 ( 11
(Zq) 111 + Alla (
n/(2p)
f(z] q).
(
24
13

---

Coreset for Regularized Linear and Logistic Regression in VFL
The inequality (i) is due the p-complexity property of Z, and the following inequality is due the reason from the previous analysis.
So, using the equations (7), (8) and (9) we have the following claim for every Idd
f(zi, q)
S $200(1 + (2) ( (vuTus u, 2
ClassLoss( q.
Lemma B.2. Given a Lewis busis U Z for some fixed p. we have [|Dp/2-1U||] |
Proof. We know Di = VU uu u, where D a diagonal matrix. So,
D diag (uTTu, u1, V un U2 u2..... V u un and subsequently have, D diag (u, un) 37
(u, un -
Now compute |D& U
D UI = Σ - Σ (u. u. p2:p (u. u.) = =<(n (u: uz)
|
B.2. Proof of Lemma 5.5
Lemma B.3. In lemma 5.2, let U and Ü be the & Lewis basis of Z and Ż respectively. Then the of &1 Lewis weights of first n points in Ü is sd(Z, X, 1). Here M U DPP2--12 such that D is the diagonal matrix defined from U.
Proof. Let Ü be the Lewis Basis of the matrix Ž and U is the Lewis Basis of Z. Let D and D be the diagonal matrices defined from U and U. From the above lemma B.2 we know that | |D-1/2
1/2 Ú 3 |U|| Hence, in the regularized logistic
regression, the total Lewis weights is Σi= ||ú:|1 Σ D3 0. ú.
Let M U 1/2Z a d full rank matrix, such that its decomposition M Ü.V Now, consider matrix not difficult to verify that N N I.- Now, recall that the
D 1/2U
-1/2
N
where Σ $ ALa) VAVY
column space of 2 is same as the column space of both Ú and D -1/2Ú. Further, N is column basis of Ž and N is an orthonormal matrix. Hence, N is an orthonormal column basis of 2. Since, N and 1 both are the orthonormal column basis of 2, so they are a rotation apart from each other. As Frobenius norm is invariant to rotations hence, we have E | = Em i ú. ú; = E n. n, where n. is the ith row of N. Now, we bound En n; n;
|D- 1D-1/"UETT
n n
(i1)
Here, (1) because both D 1 and Ü are the orthonormal column basis, to which the Frobenius norm is invariant. Since both E and E) are diagonal matrices, we get the final equality (ii).
14

---

Coreset for Regularized Linear and Logistic Regression in VFL
B.3. Proof of Corollary 5.7
Corollary B.4. For given dataset Z and scalar À O, let Z be the augmented matrix such that it is partitioned among T clients. For every j E [T], Z Baxd; If be ju-omplex dataset then the algorithm computes an E-coreset
n² Σ ad(z 2.1)
(see; Definition 1.3) in O of size m m with communication complexity O
for some E (0,1) and the model can be trained
Proof. For logistic regression from Lemma 5.2 we know that the sensitivity scores for every point E [r]] can be upper bounded by function that is proportional to the lg norm of the row of any orthonormal column basis of the matrix. Further, from (Mai et al., 2021) we know due to the existence of Lewis Basis, there is a tighter upper bound that is proportional to the square of the lg norm of a special orthonormal column basis of dataset that constructed from its Lewis Basis.
So. for matrix A _n the higher upper bound for any i E [nx] is mAX (aggg))
(a, Tg)² Now, in the case of VRLog, Aqll
we can upper bound these scores as, maXqeRd this bound by applying Cauchy Schwarz in the numerator and the in the denominator use lower bound. We use ||q 2 o] A Ac₃ 93 for every j E [d].
(a: Tq)
||
d
j=1
e A Aep.g
d'j=
of A Ae ) We get
Now, recall that due lemma B.2, the coreset size depends on the ||D U/2. For every point E [n]. its sensitivity score upper bounded by the lle, D-1/2 U12. Hence, the sum of the Lewis weights from different clients and factor of 7 upper bounds the actual Lewis weight of the point in higher dimensional space.
C. Proofs of VRLR
C.1. Proof of Lemma 6.2
Lemma C.1. For every point i E [n]] and client j E [T), the scores returned by the Algorithm for VRLR, 9. = =|(u,01 112 Let U(), U(2) ..... U(T) be the orthonormal column basis of (1) ( (T)) respectively, then every point i E [m] the regularized sensitivity scores can be upper bonded as,
(x] q y2
T ST.
sup
1
12
|X - yl +
Proof. For every point i, the regularized sensitivity function is defined as, supq [ y + For simplicity, assume
[x] q 9.)
that T = d and y O, such that every client j E [T], has access to Xj. which is the jth column of X. We consider Z = X
Z
and Ż
Now we analyze the sensitivity score for every q without the supremum as follows.
V
[x]] T q - y:)²
[x] q)²
Xxq y13 + A|111
Xqll 2 + A|ll||
(z. 2
[2qlي
(2/1 Qi + 2,2 92 + ... + 2id qa)
||qq
d ((zn 92) (E (2) + ... + (2id 9a)2)
|zqll
(1)
(211
)1
(z12 92)2
(2id - qu)2
d
e
Zer
e Z TTZe . 1/
e 2 Zea 23
(6z)
(zi)²²
(z²2)²
(zza)²
d
c
Ze1
e. 2 Ze2
C,2 2 Zed
15

---

Coreset for Regularized Linear and Logistic Regression in VFL
The inequality (i) is due Cauchy Schwarz in the numerator. In inequality (ii), the lower bound in the denominator, ie.. | /2qll 2 , 2 Ze, 03 for every [d]. Finally, we get (iit). Since independent of q, so it upper bounds the
above function even with a supremum over q. Here, every client j E [d] upper bounds their own function by oj Zey sensitivity scores entire point is upper bounded by aggregating these scores and scaling it with d.
($.,)* and
Notice that T = 1, then we do not need to apply Cauchy Schwarz in (i) since there is only one client, and has access to the complete data. So instead of (iri) we could upper bound the above function by z, (Z Z) z, This is also equal to the
square of the lg norm of the th row of the orthonormal column basis of Z. So, z; Z Z) z, ||u where u, is the 7t row of U which is the orthonormal column basis of Z.
In similar manner, when 1 < T < d every client [T] upper bounds its scores by o.¹ (z, ( ((20)
Here 9. are the values that were returned by LewisWeight. Finally, the sensitivity score of the entire point upper bound by aggregating these scores and scaling them with T.
So, for general T y we have,
x q y1)²
T 1
supp
ST.
12
X
y
1q
Here U is the orthonormal column basis of (05 for every j E [T].
C.2. Proof of Lemma 6.3
Lemma C.2. For the given regularization parameter X, the total sensitivity scores or the sum of the sensitivity scores in the sd sd(()) (x)))
yFL.setup with [T] clients are upper bounded by O (T -
Proof. This proof is similar to the proof of lemma B.3.
Consider singular value decomposition of 26,, i.e., 20) UEVT, where U e Raxd, representing the orthonormal
column basis of Z0) Es dj x dj diagonal matrix and V E Rdd xd, orthonomal row basis of 2(), Let = (E + >
UΣΣ VVAΣ
Let M
Notice, that M TM M Ld, and ()) MÉ 'V_ Hence, M the orthonormal column basis of
2 Although there infinitely many orthonormal column basis for any given matrix, each is rotation of another. Hence, the row norms each orthonormal column basis are the same. So, Σx= ||m,| = |UΣŠІ = ||Σس = d
()) Now, due to lemma C.1 the sum of upper bounds are Σx= Di = T sdd = T ΣØ 14
Hence,
G= E (Z)),, 2,
Now, we bound the sampling complexity by applying the following Matrix Bernstein's 's inequality.
Theorem C.3 (Matrix Bernstein (Tropp et al., 2015)). Let X1, X2...., Xn are independent x random matrices such
that Vi E [n]. |||x|||| ||| S and var(] S o² where X Er X,, then for some >
-212 11/2 +
Pr [||X|| X|| 2 2) S.d exp
C.3. Proof of Lemma 6.4
Lemma C.4. For a given Z E (d+1) be the augmented matrix, let be a scalar and e E (0, 1). The algorithm 3 samples set S C Z with appropriate weights w S - R2 We represent the weighted set as Sw. If the size S is least T ST sd(2 A.2) log(d)
O
then the set ensures the following guarantee with at least 0.99 probability.
- Z AT)
ST AI (1+ +
16

---

Coreset for Regularized Linear and Logistic Regression in VFL
Proof. Let R. be the random variable that holds the sampled points. So, have the random matrix R as,
R
2.
with probability pi, tth row of Z sampled
pim
Note that 1 R Z Z. So, the sum of the random matrices is unbiased and equal to the original data matrix Z. Here (R...... Bm) are the random variables that hold the sampled points from the algorithm. Now we bound |||||2
2,2
R
p,m
(14)
z;z,
G
12
(126)
(z,z,
'z,z Z 2G
(i0)
ž T 2G
m
In the above, the equality (i) and (di) are by definition. In the incquality (iit) we use the lower bound of g, = =x=>}f= ET=9! q)a for every q. the final inequality upper bound z.! (.])lzz Iz,z, Ld-
Now, we bound var 1 R3 (1))
using var [R,] S B.R... for every j E [T].
var Σ
R
S E
R
1=1
Z2 )
pim
(z.z,) T ) (2,2, )22T
ŻG
m²
(2 2
In the above analysis, the inequalities (i) and (ii) are same the previous analysis in |R]]
Therefore by applying Matrix Bernstein Theorem C.3 we get,
[=|| 2112)²
Pr
Σ R
2
2 2 211
I 2d . exp
=|1 2
12 |3
-
2d exp
3G/mi
Now to ensure that the event happens with probability at least 0.99 we need m 2 0
3G log(d)
As we know from the
lemma C.2 that G = (I Σn sd( X, 2. hence we have the claimed value of m.
D. More Empirical Evaluations
Here, we show more rigorous experiments over more real-world datasets. Building on the setup used the main paper, each dataset was partitioned into training and testing sets, with each experiment repeated up to 5 times, and then the median performance of these repetitions is reported.
17

---

Coreset for Regularized Linear and Logistic Regression in VFL
The Wave Energy Converters dataset consists of positions and absorbed power outputs of wave energy converters (WECs) in four real scenarios from the southern coast of Australia (Sydney, Adelaide, Perth, and Tasmania). We used the Sydney dataset that consisted of 71999 samples and 48 features after preprocessing. The dataset was split into training and testing subsets in ratio of 4:1.
The Year Prediction UCI ML dataset aims to predict the release year of a song based on audio features, specifically tim- bre attributes. It includes attributes-11 representing timbre averages and 78 representing timbre covariances across range songs from 1922 to 2011. The dataset was split into training (463,715 examples) and testing (51,630 exam- ples) subsets, ensuring artist appears in both sets.
The KDD Cup dataset is used for network intrusion detection. It contains 125,973 instances of network traffic data with 122 attributes. The dataset was split into 4:1 train-test sets for intrusion detection tasks, where the goal is to classify network traffic as either normal or intrusive.
The Credit Card Fraud Detection dataset contains 284,315 legitimate transactions and 492 fraudulent cases, resulting in highly imbalanced dataset. We address this imbalance using SMOTE sampling, which generates balanced dataset of 568,630 samples while maintaining the original split ratio. The task is to identify fraudulent transactions.
Gold Price Financial Markets dataset captures 50 market indicators over 3,904 trading days. The task is to predict the future movements of stock prices, making a time-series regression problem.
The Blog Feedback dataset consists of 56,239 samples and 280 features and is used predict the popularity of blog posts. The dataset contains mix of continuous and categorical features, making suitable for regression tasks.
The UlIndoorLoc UCI ML dataset is used for indoor positioning and consists of 21,048 samples with 527 WiFi signal attributes. The task is a multi-target regression problem, where the goal is to predict the latitude and longitude of mobile device based on its WiFi signal strengths.
D.1. vRLog Experiments
HLSZ
Relative Dowiltc sertt Diffierente
HLSZ
HLSZ
06-
SqLev
Sqley Levis
Training Time
Sqj.ev
Traning LOGK
Accursiy
0.0-
Augiewni
0-2
Uniform
02
05
AugLowis
200
1005
1000
2000
2200
300
1000
1200 Sample Size
2000
2000
1000
1200
Sample Size
Sample Size
Sample Size
Figure 3. VRLog Coreset Performance (KDD Cup)
Samples
50
2500
Methods
Train
Test
Train
Test
Uniform
0.3419
0.3412
0.9184
0.9155
HLSZ
0.4717
0.4702
0.9685
0.9659
Lewis
0.8715
0.8688
0.9712
0.9684
AugLewis 0.8801
0.8772
0.9713
0.9685
Table 2. Fl scores on the KDD Cup dataset.
Here, we have considered KDD dataset with similar setup as we had for the credit card dataset in the main section of the paper. In figure 3 we again observe that our sampling methods outperforms the other sampling methods in all aspects, but the difference between trained model on the subsample and full dataset. Even though SqLev performs better in terms of the model difference, however there are no known theoretical guarantees in this regard for Logistic regression from
18

---

Coreset for Regularized Linear and Logistic Regression in VFL
any sampling methods. Further, SqLev known have coresets whose size is proportional to vn, makes it less reliable in practice, where is the number of data points in the training set.
We again compared the Fl scores between all the sampling methods on the KDD datasets. Similar to the Credit Card dataset, we observe that our sampling method outperforms others in the table 2, even though there are no known theoretical claims.
Now, extending our experiments from section 7, on the Credit Card Fraud Detection dataset, this time, the coresets were partitioned into five clients, where each client consisted of around features. Here and we have considered various values. We compared our sampling method Augmented Coreset with Lewis with other sampling methods, which are (1) Uniform, (2)
Class-wist wass QR, and (3) Coreset With Lewis SqLev and Lewis from the section 7 respectively.
We observe in Figure 4, the plots are consistent, where our coreset outperforms all the other sampling methods (Uniform, QR. Lewis Weights) in both the training and testing phases. In the QR sampling, we partition the dataset based on the labels and then compute QR decomposition on each partition separately. Next, the row norms were used to define the distribution over the training dataset, and then was sampled. In the Lewis weights sampling, our sampling method here does not consider the regularization term the Lewis weight approximation.
Moan Train Arturary by (lamhda 001)
Mpan Anturacy Sizp (lambda=0. (01)
Fnmont
Clecvsise Qi
Asgineriedd Ccreeet Leses
Clasweise QR
Aiginnnten Coreaal of Lenb.
0.7
Meen Tein Acoraty
0.5
0.3
0.1
0.1
700
1000
5000
1200
2500
Mean Train Accuracy by Size (lambd==1)
Mean Test Accuracy by Size (lambda=1)
Unifom
Aagmeeted
Sugieened
Heen Train Recurecy
200
500
700
1000
1200
1500
2300
3000
200
500
700
1000
1200
1500
2500
3000
size
Size
Figure VRLog Coreset Performance (Credit Card)
19

---

Coreset for Regularized Linear and Logistic Regression in VFL
D.2. VRLR Experiments
Here, also increase the number of clients. We have considered the regularization parameter À to be 102 for the Wave dataset and 104 for the Year dataset. We have considered similar competitive sampling methods had in the section 7. Our coreset outperforms both in the training phase well the testing phase in both datasets.
In the top two images of Figure 5, we show our results in the Wave Energy Converters dataset. We partitioned the coreset into 3 and 10 clients for better analysis. We have considered various regularization parameter values A. These are captured by the parameter a, which defined as a = 1/x. Notice, our coreset (i.c., Ridge Leverage) performance significantly improves compared uniform and (Huang et al., 2022), which Leverage. Even with a coreset size as small as 0.5 percent of the full data, the performance of coreset is significant.
Next, we tried analysis the Year Prediction UCI ML dataset. Here, partitioned the coreset into 5 clients, each with around 18 features. The bottom two images in Figure 5 report the MSE of the Year dataset. While our coreset does not improve the results significantly compared to the other two sampling methods, it consistently outperforms them.
Training (elpha=100)
(lambda=100)
Uniiorm
Uniiorm
Leverage
Leverage
hidgo Leverage
Ridge Leverage
5000
5000
Neen TTaiiig MSE
3000
3000
2000
Size
Size
Mean Training MSE by Size
Mean Test MSE by Size
Uniterm
Unfomm
Levarage
Leverage Ridge Leverage
10
Ridge Leverage
20
Neen treining kSt
6-
500
1000
2000
4008
8030
500
1000
2000
4000
8000
Figure VRLR Coreset Performance (Wave Energy and Year Prediction)
20

---

Coreset for Regularized Linear and Logistic Regression in VFL
We extended our experiments additional datasets UJIIndoorLoe,, and Blog Feedback, which are presented in figure 6 and the Gold Price Finance dataset in figure for different values of X. To evaluate performance with all three sampling algorithms fürther, also reported relative training time and model closeness done in the section 7. The relative training time is defined as the ratio of the time taken to train model on the complete training dataset to the time taken to train model on the coreset. These are better when they are greater. The model closeness is the relative measure between the Euclidean distance between a trained model on the subsample and a trained model on the complete dataset, to the trained model from the complete dataset. These are better when smaller.
The training and the test RMSE very similar because both train and test well represent the distribution of the population. Here, also notice that our algorithm 2 clearly outperforms all the other coreset construction methods.
Uniform
Unform
Uniform
Uniform 11,52 02
Timee
Reattic Coemooen
200
400
E30
699
1006
1000
3900
1000
200
400
609
063
3000
1200
1990
1603
200
400
500
890
1005
1200
3000
3900
200
400
630
060
1000
1000
3400
1600
1.2
Darattee Cosfliicien Differettcc
31.0
RMACE
205
Lev
Selettve
Uniform
Uniform
MLSIZ
HLS5
26.0
1200 Semple Size
2000
2590
2000
2500
500
Semole Size
Sample Size
Sample
Figure 6. VRLR Coreset Performance (UJlIndoorLoc and Blog Feedback)
Based on this extensive empirical evidence and established thcoretical guarantees, again reiterate that algorithm 1 and algorithm 2, which leverages regularized sensitivity scores, offers greater reliability and superiority in constructing coresets for VRLog problems and VRLR problems, respectively.
21

---

Coreset for Regularized Linear and Logistic Regression in VFL
100
Uniform HLSZ
Uniform HLSZ
Coefficlent Offfrennce
Uniform HLSI
300
Lee
Yeat sOrGE
Relsove Traliing
HLSZ
8
300
Sample 5130
Sample
Sample
Sample
380
Uniform HLSZ
Uniferm HL52
Reterve Confricten Offfeennce
023
Teat RADGE
Unifam
8.00
Unifurm
Retoeve
30
380
25
100
125
150
175
25
100
125
150
200
100
150
175
200
50
100
130
175
200
120
Uniffrr
Reletve Coetrite Commernnce
Uniform
4.25
Toat RVeG
379
Retse
125
150
30
100
125
200
100
125
200
2.7
175
Sampie
Sample
Figure VRLR Coreset Performance (Financial)
22


Reviews:
[{"review_id": "A1kCFT8nAI", "reviewer": "Reviewer_Br26", "summary": "This paper studies regularized linear regression and regularized logistic regressions in the vertical federated learning (VFL) setting, where clients store different data features. The goal is to reduce communication complexity. The paper introduces coreset algorithms for these two problems and achieves improved coreset size.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer Br26 for the time taken to read our submission and the provided feedback. We address the concerns.\n\n> The introduction section introduces several dense math notations but does not provide the motivations for the problem.\n\nRegularized linear regression and regularized logistic regression are standard basic problems in the ML community. Federated learning is now well recognized for its ability to address data privacy, security, and scalability. We stated the motivation of the problem in lines 51-54 (right); we will highlight that in the final version where an additional page will be available.\n\n>The novelty of this paper compared to the literature has not been clearly illustrated. For instance, Algo 1 looks like Algo 1 in [Huang et al., 2022], while there is no discussion of the difference.\n\nIn [Huag et. al., 22] the coreset size for VRLR is a function of the rank of the input data. In comparison, our coreset size depends on the statistical dimension of the data, which is strictly smaller than the rank for any regularization parameter $\\lambda>0$. Algo 1 in the paper is only for completeness and has not been included in the contribution claims. The main novelties of the paper have been highlighted in the contribution claims. Algos 2 and 4 are our contributions, whereas algo 3 has been included for completeness and stated so. We discuss the improvement of coreset size in VRLR in rebuttal to reviewer YB3Z.\n\n>It is unclear why their coreset size is always smaller.\n\n> Can you provide a concrete dataset example and compare the explicit corset sizes between [Huang et al., 2022] and your result? What is the exact size improvement?\n \nThe coreset size depends on factors such as the total sensitivity, approximation error $\\epsilon$, failure probability and the pseudo dimension of the problem. The most standard experiment evaluations are that for a fixed coreset size, what is the $\\epsilon$ or loss or accuracy, and they tend to improve as we increase the coreset size. Comparing exact sizes between various sampling methods with a fixed one of the above parameters is impractical. Notice that in plot 2, for fixed coreset size, our algorithm has a smaller test and train RMSE and also smaller $\\epsilon$ compared to the sampling methods from Huang et. al. This clearly shows that with a fixed sample size, our coresets (LEV) are performing better than the existing methods. We have further conducted more experiments on other real datasets showing similar improvements included the appendix.\n\nThe exact difference between the coreset size can only be described theoretically. Let us exemplify this. For simplicity assume the number of clients to be 1, which can be easily extended to a setup with multiple clients. Let $A$ be a dataset with all $n$ points in $\\mathbb{R}^{d}$ such that $n/d = c$ where $c$ is a positive integer. Again, for simplicity, take its response vector $b$ to be the zero vector. Let $A = \\begin{bmatrix} I \\\\\\ \\vdots \\\\\\ I \\end{bmatrix}$ where $I$ is just identity matrix in $\\mathbb{R}^{d}$. In Huang et al., the sensitivity score for every point is $1/c$. Hence, the total sensitivity for $n$ points is $n/c = d$. Notice that it is irrespective of the fact if $\\lambda$ is 0 or a positive scalar. However, in section 4 [line 185 right] we have clearly motivated why a smaller coreset size is expected for the case when $\\lambda > 0$. So, in such a case, our sensitivity scores are $1/(c+\\lambda)$. Hence, the total sensitivity score is $n/(c+\\lambda) < n/c = d$. In fact, for higher values of $\\lambda$, the total sensitivity score could be significantly smaller. So, theoretically, the improvement in the coreset size is at least by a factor of $c/(c+\\lambda)$. We will further underscore this example in the final version.\n\n> It is strange to heavily strengthen that the bound for the total sensitivity is tight. If the coreset size is tight, it is interesting. For the sensitivity, a remark may be enough.\n\nThe coreset size is proportional to the total sensitivity (also mentioned above) which is the summation of individual sensitivity scores. Having a tighter sensitivity score gives a tighter total sensitivity, further resulting in a coreset with a tighter size. We will add a remark for this.\n\n> The paper heavily uses levis weights to compute the sensitivities, which have been studied extensively. However, they do not introduce or compare with the use of levis weights in the literature clearly. \n\nWhile there are various methods for computing Lewis weights, however, for our purpose, it suffices to compute the Lewis weight in any of the known methods. We have used the Lewis weights computation from Cohen Peng Lp Row Sampling by Lewis Weight 2015. We have presented this as algo 3 for completeness. We appreciate the suggestions, we will include the appropriate citations in the camera ready version.\n\nHope we have addressed your concerns and we will be happy to provide futher clarifications if needed.", "claims_and_evidence": "No\n\nFor example, this paper claims that their corset size improves upon that of [Huang et al., 2022] for ridge linear regression. However, they do not provide an explicit comparison between their coreset size provided in Theorem 6 and that of [Huang et al., 2022]. It is unclear why their coreset size is always smaller.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes.\n\nCheck the proof of Lemma 1, which is correct.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "Yes, it relates to the broader area of federated learning and data compression.", "essential_references_not_discussed": "Yes\n\nThe paper heavily uses levis weights to compute the sensitivities, which have been studied extensively. However, they do not introduce or compare with the use of levis weights in the literature clearly. I list some potential papers below:\n\n- William B. Johnson and Gideon Schechtman. Finite dimensional subspaces of $\\ell_p$. 2001.\n- Varadarajan, Kasturi R. and Xin Xiao. On the Sensitivity of Shape Fitting Problems. 2012.\n- Jambulapati, Arun, James R. Lee, Y. Liu and Aaron Sidford. Sparsifying Sums of Norms. 2023.", "other_strengths_and_weaknesses": "Weaknesses:\n\nThe writing is not well structured.  \n- The introduction section introduces several dense math notations but does not provide the motivations for the problem. \n- The novelty of this paper compared to the literature has not been clearly illustrated. For instance, Algorithm 1 looks like Algorithm 1 in [Huang et al., 2022], while there is no discussion of the difference.", "other_comments_or_suggestions": "- It is strange to heavily strengthen that the bound for the total sensitivity is tight. If the coreset size is tight, it is interesting. For the sensitivity, a remark may be enough.", "questions_for_authors": "- Can you provide a concrete dataset example and compare the explicit corset sizes between [Huang et al., 2022] and your result? What is the exact size improvement?", "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": "", "extra_scores": {"ethics_expertise_needed": ["Other expertise"]}}, {"review_id": "laPZZxi5E2", "reviewer": "Reviewer_VbiJ", "summary": "The paper introduces a coreset construction algorithms for Vertical Federated Learning (VFL), focusing on regularized logistic and linear regression (ridge regression). The authors present algorithms to efficiently construct coresets that significantly reduce communication complexity in VFL, essential due to clients possessing different subsets of the feature space. Their primary contributions include:\n1. A novel algorithm for regularized logistic regression coreset construction in centralized and VFL settings, employing ℓ₁ Lewis weights.\nImproved coreset construction for vertical regularized linear regression (ridge regression), reducing coreset sizes while eliminating dependency on a specific data-related property previously considered necessary. \n\n2. A detailed analysis demonstrating that increasing regularization parameters reduces model complexity and consequently reduces the required coreset size.\n\n3. Empirical validation that demonstrates superior performance of their coresets compared to existing methods, both in terms of accuracy and computational efficiency.\n\nThe experiments highlight significant speed-ups (up to 100x) and comparable accuracy to models trained on complete datasets, validating their theoretical claims.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful to the reviewer for taking the time to read our submission and providng a detailed review. \n\n> Limited experimental validation on diverse or large-scale real-world datasets.\n\nIn the literature, it is standard to perform experiments on publicly available datasets to support the theoretical claims of federated learning algorithms. Large-scale experiments are useful in their merit to validate the distributed (multi-node-multi-GPU) machine learning algorithms, where we need to capture system-related aspects. Moreover, for a **vertical** federated learning algorithm, an experimental validation over a dataset with 280 features (blog feedback) or, for that matter, one with 500,000 samples (year-prediction) is reasonably large enough to capture the core claims of the algorithm. \n\n> A potential computational bottleneck (e.g., calculation of Lewis weights) may restrict the practicality of the proposed algorithms in certain very large-scale federated learning scenarios.\n\nThis concern may not be completely well founded as a Lewis weight can be approximated using Online Row Sampling by Cohen Peng 2015 in $\\tilde{O}(nd^{2})$ where $n$ is the number of the points in $\\~R^{d}$. This is only larger by a $\\log (n)$ factor compared to the running time for VRLR. Due to this, in Corollary 1, we have the running time of our algorithm as $\\tilde{O}(nd^{2})$. We will add a remark after this corollary to clarify this. \n\n> In your experiments, how did you select the regularization parameters ($\\lambda$)? Did you use standard cross-validation or a more specialized method tailored to VFL settings?\n\nThough Cross-validation is used for selecting $\\lambda$ in centralized settings, it is not a standard approach for hyperparameter selection in federated learning, where it is unclear where -- on a client or the server -- to cross-validate. Please note that it is actually a critical decision problem for a client to even accept a federated model, which it would have contributed to the training of. We did a general grid search for $\\lambda$. See \"Federated hyperparameter tuning: Challenges, baselines, and connections to weight-sharing, Khodak et al. NeurIPS 2021\". We will specify this in the final version.\n\n> Why have you used accuracy instead of F1-Score?\n\nIn our experiments, we showcased losses (training/tests) because our theorem ensured theoretical guarantees on these parameters. Apart from these, we have compared the performance in terms of balanced accuracy, model parameters, and improvement in the training time. Following your suggestion, we did perform experiments to compare the performance on F1-Score. Even on that metric, the proposed algorithm outperforms the competitors. See the table below. We will include more extensive results in the supplementary material in the camera ready version of the paper. \n\n## 1. Credit Card Dataset\n\n### Sample Size: 500\n\n| Method   | Train F1 | Test F1 |\n| -------- | -------- | ------- |\n| Uniform  | 0.8192   | 0.8185  |\n| HLSZ     | 0.8704   | 0.8712  |\n| Lewis    | 0.9220   | 0.9230  |\n| AugLewis | **0.9330**   | **0.9343**  |\n\n### Sample Size: 2500\n\n| Method   | Train F1 | Test F1 |\n| -------- | -------- | ------- |\n| Uniform  | 0.8723   | 0.8731  |\n| HLSZ     | 0.9071   | 0.9078  |\n| Lewis    | 0.9304   | 0.9315  |\n| AugLewis | **0.9319**   | **0.9331**  |\n\n## 2. KDD CUP Dataset\n\n### Sample Size: 50\n\n| Method   | Train F1 | Test F1 |\n| -------- | -------- | ------- |\n| Uniform  | 0.3419   | 0.3412  |\n| HLSZ     | 0.4717   | 0.4702  |\n| Lewis    | 0.8715   | 0.8688  |\n| AugLewis | **0.8801**   | **0.8772**  |\n\n\n### Sample Size: 2500\n\n| Method   | Train F1 | Test F1 |\n| -------- | -------- | ------- |\n| Uniform  | 0.9184   | 0.9155  |\n| HLSZ     | 0.9685   | 0.9659  |\n| Lewis    | 0.9712   | 0.9684  |\n| AugLewis | **0.9713**   | **0.9685**  |\n\n\nWe thank you again for your time and we will be happy to provide further clarifications if any.", "claims_and_evidence": "The paper clearly demonstrates:\n1. The theoretical guarantees of coresets constructed with their proposed algorithms.\n2. Reduction in coreset size directly correlated with increasing regularization parameter λ.\n3. Empirical evidence across multiple datasets validates the theoretical results and effectiveness compared to competing methods.", "methods_and_evaluation_criteria": "The proposed methods (coreset construction algorithms using Lewis weights and sensitivity scores) are well-suited to the stated problems (regularized logistic and linear regression) within the VFL framework. The evaluation criteria, including comparison against multiple benchmarks (e.g., uniform sampling, leverage scores, previous state-of-the-art methods), are appropriate and standard for the problem domain.", "theoretical_claims": "The paper provides several theoretical results, including sensitivity score bounds (Lemma 1, Lemma 7), Lewis weights properties (Theorem 2, Lemma 3, Lemma 4), and coreset size bounds (Theorems 5 and 6). \n\nDid not thoroughly check the proofs.", "experimental_designs_or_analyses": "Authors validate their coresets across multiple datasets (Credit Card, Financial, Blog Feedback), comparing their performance on key metrics (training loss, test accuracy, RMSE, model closeness, training time) against other baseline methods.", "relation_to_broader_scientific_literature": "This paper establishes itself within the existing body of work on coresets and vertical federated learning. notably building upon prior literature such as Huang et al. (2022) and leveraging important foundational concepts from Lewis and sensitivity sampling.", "essential_references_not_discussed": "The paper has comprehensively cited the core relevant literature and key foundational works.", "other_strengths_and_weaknesses": "Strengths:\n------------\n1. Strong theoretical contributions and well-motivated problem.\n2. Relevant algorithmic contributions for the vertical federated learning setup.\n\nWeaknesses:\n----------------\n1. Limited experimental validation on diverse or large-scale real-world datasets.\n2. A potential computational bottleneck (e.g., calculation of Lewis weights) may restrict the practicality of the proposed algorithms in certain very large-scale federated learning scenarios.", "other_comments_or_suggestions": "Careful proofreading is suggested for typographical and minor grammatical mistakes in the introduction and methods sections.", "questions_for_authors": "1. In your experiments, how did you select the regularization parameters (λ)? Did you use standard cross-validation or a more specialized method tailored to VFL settings?\n\n2. Why have you used accuracy instead of F1-Score?", "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": "", "extra_scores": {}}, {"review_id": "U8Cx7WVfAH", "reviewer": "Reviewer_YB3Z", "summary": "Coresets serve as a compact summary of training data, offering an efficient method for reducing data processing and storage complexity during training. In the context of vertical federated learning (VFL), where different clients hold distinct data features, coresets help reduce communication complexity.\n\nThis work introduces a coreset construction method for regularized logistic regression in both centralized and VFL settings. Additionally, the authors improve coreset size efficiency for regularized linear regression in VFL, eliminating its dependence on certain data properties inherent to the VFL framework. These improvements stem from novel coreset construction algorithms that account for reduced model complexity due to regularization.\n\nExtensive empirical evaluations support the theoretical findings, demonstrating the effectiveness of the proposed coresets. The performance is further validated by comparing models trained on full datasets versus those trained on the coresets, showcasing their practical utility.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking time to read our submission and providing useful remarks. Below we address your concerns\n\n> However, certain statements, while technically correct, may lack sufficient clarity for a non-expert audience. For example, the statement: \"This is the most computationally expensive operation, which takes $(O(nd^2_j))$ time.\" (Lines 355–357, right side, Page 7). Although this statement provides the computational complexity, it does not explain why this operation is the most expensive or how the complexity arises from the underlying mathematical formulation. A brief explanation of the source of this complexity, its practical implications, and how it compares to other computational steps in the algorithm would enhance readability and understanding.\n\nThe paper mentions that, the running time of computing $g^{(j)}$ of line 6 in Algorithm 4 $O(nd_j^{2})$ for client $j \\in [T]$ having the dataset $Z^{(j)}$. This is because, for $p=2$, which is the case for VRLR, the matrix $W$ is always identity $I_{n}$ and hence $g^{(j)}$ can be computed using the orthonormal column basis of $\\hat{Z}^{(j)}$, since $g_i^{(j)} = (x_i^{(j)})^{T}((X^{(j)})^{T}X^{(j)}+\\lambda I_{d_j})^{-1}(x_i^{(j)})= (x_i^{(j)})^{T}((\\hat{Z}^{(j)})^{T}\\hat{Z}^{(j)})^{-1}(x_i^{(j)})= ||u_i^{(j)}||^2$, where $u_i^{(j)}$ is the $i^{th}$ row of the orthonormal column basis of $\\hat{Z}^{(j)}$. Recall, that in Huanf et. al., 22 the score for the same point is $(x_i^{(j)})^{T}((X^{(j)})^{T}X^{(j)})^{-1}(x_i^{(j)})$ which is greater than our scores because $((X^{(j)})^{T}X^{(j)}) \\prec ((X^{(j)})^{T}X^{(j)}+\\lambda I_{d_j})$. Hence the total sensivity is smaller and thereby our coreset size is smaller than Huang et. al. 2022 for the VRLR problem.\n\nOne can compute SVD of $\\hat{Z}^{(j)}$ to compute its orthonormal column basis. This can be computed in $nd_{j}^{2}$ time. Notice that these scores are part of the input to the coreset construction algorithm 1 which takes less time that $nd_{j}^{2}$. Once it has been computed, the rest of the algorithm takes fewer than $nd_{j}^{2}$ time. The first line takes  $O(n)$ to compute the sum of sensitivity scores. Next, line 2 takes $O(T)$ time at the server. In line 3 every client selects $\\lceil m/T\\rceil$ indices from $[n]$ based on the defined sampling probability. Next, these selected indices were shared with the server which defines global weight for the selected indices which again takes $O(n)$ time.  \n\n> While I appreciate the experimental results presented on these datasets, it would be beneficial to explore additional datasets to further strengthen the evaluation and generalizability of the proposed methods. A more diverse selection of datasets could provide deeper insights into the effectiveness and limitations of the approach across different data distributions and problem settings.\n\nThanks for your feedback. The guarantees that we provide here, as pointed out above, provably reduces the coreset size. The datasets considered are standard for this setting.\n     \n> However, extending the experiments to include deep learning tasks could offer additional practical insights. Given the increasing importance of deep learning in real-world applications, evaluating the proposed methods on more complex models could help assess their scalability, robustness, and applicability beyond the theoretical setting.\n\nSince our theoretical guarantees are only specific to regularized linear and logistic regression hence, the experimental evaluations were only conducted in that domain. We did not conduct any experiments on any deeper architecture as constructing the coresets for a regularized objective would require a potentially different approach. \n\n> The paper discusses federated learning methods designed to address client heterogeneity, such as SCAFFOLD. However, it would also be valuable to mention other relevant approaches, including ProxSkip, FedLin, and DANE, which have been proposed to mitigate ... A more comprehensive discussion of these methods could provide a broader perspective on existing solutions and how they relate to the proposed approach.\n\nIndeed the literature on federated learning is now mature with methods to mitigate heterogeneity in horizontal FL (the ones mentioned by you) to federated prototype learning (FedProto by Tan et al. AAAI 22), to federated continual learning (Wang et al. CVPR 2024) to so many other settings and problems. It is almost impractical to include them in the related work of any non-survey paper. We just touched upon the aspect of heterogeneity that lies at the core of Federated ML. We included the most relevant related works given our intent and purpose of reducing the communication complexity in Vertical FL via an improved coreset construction method. We will further include more references in the final version, where additional page space will be available.  \n\nWe thank you again for your time and we will be happy to provide further clarifications if any.", "claims_and_evidence": "Almost all claims in the paper are well-supported by **proofs or references**, ensuring a strong theoretical foundation.  \n\nHowever, certain statements, while **technically correct**, may lack sufficient clarity for a **non-expert audience**. For example, the statement:  \n*\"This is the most computationally expensive operation, which takes \\(O(nd^2_j)\\) time.\"* (Lines 355–357, right side, Page 7)  \n\nAlthough this statement provides the computational complexity, it does not explain **why** this operation is the most expensive or how the complexity arises from the underlying mathematical formulation. A brief explanation of the **source of this complexity**, its practical implications, and how it compares to other computational steps in the algorithm would enhance readability and understanding.  \n\nProviding additional context in such cases would make the paper more accessible to a broader audience, including those less familiar with the specific computational details.", "methods_and_evaluation_criteria": "In this paper, the authors provide theoretical guarantees alongside experimental results for regularized logistic and linear regression. This approach is well-justified, as it ensures alignment between theoretical insights and practical validation.", "theoretical_claims": "All theoretical claims are well-formulated, and the definitions, lemmas, and theorems are clearly stated. Additionally, the other theoretical derivations are presented in a clear manner. Unfortunately, as I am not an expert in this field, I cannot verify the proofs. However, at a high level, the statements appear to be sound and make sense.", "experimental_designs_or_analyses": "The authors conducted experiments on both regularized logistic regression (VRLog) and regularized linear regression (VRLR) using three datasets: Credit Card (classification), Financial (regression), and Blog Feedback (regression). Each dataset was partitioned into training and testing sets, with the training data further distributed among three clients.\n\nMaintaining the VFL sampling technique from Algorithm 1, the authors compared their sampling method with various other techniques. Once a sample was drawn using one of the sampling methods, they trained a model with a regularization parameter. For VRLog, they evaluated training loss, test accuracy, model closeness, and training time. For VRLR, they reported test RMSE and model closeness.\n\nFor each sampling method and sample size, the authors repeated the experiment 10 times and reported the median values of the results.\n\nWhile I appreciate the experimental results presented on these datasets, it would be beneficial to explore additional datasets to further strengthen the evaluation and generalizability of the proposed methods. A more diverse selection of datasets could provide deeper insights into the effectiveness and limitations of the approach across different data distributions and problem settings.\n\nThe inclusion of logistic regression and linear regression experiments is particularly valuable, as they align well with the theoretical framework and provide a solid foundation for validating the theoretical findings. However, extending the experiments to include deep learning tasks could offer additional practical insights. Given the increasing importance of deep learning in real-world applications, evaluating the proposed methods on more complex models could help assess their scalability, robustness, and applicability beyond the theoretical setting.", "relation_to_broader_scientific_literature": "This work is related to both vertical federated learning and the broader federated learning literature. However, as I am not an expert in this specific area, I am unable to provide a more detailed assessment of the underlying ideas.", "essential_references_not_discussed": "The paper discusses federated learning methods designed to address client heterogeneity, such as SCAFFOLD. However, it would also be valuable to mention other relevant approaches, including ProxSkip, FedLin, and DANE, which have been proposed to mitigate the effects of heterogeneity and improve convergence in federated learning settings. A more comprehensive discussion of these methods could provide a broader perspective on existing solutions and how they relate to the proposed approach.\n\nMishchenko, Konstantin, et al. \"Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!.\" International Conference on Machine Learning. PMLR, 2022.\n\nMitra, Aritra, et al. \"Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients.\" Advances in Neural Information Processing Systems 34 (2021): 14606-14619.\n\nJiang, Xiaowen, Anton Rodomanov, and Sebastian U. Stich. \"Federated Optimization with Doubly Regularized Drift Correction.\" International Conference on Machine Learning. PMLR, 2024.", "other_strengths_and_weaknesses": "The paper is generally well-written and easy to follow. However, for non-experts, the theoretical section may be challenging to comprehend, even at a high level. Providing additional explanations or intuitive insights could enhance accessibility for a broader audience.", "other_comments_or_suggestions": "Please review and address the issues raised in the previous sections.", "questions_for_authors": "Would it be possible to empirically evaluate the proposed methods on deep learning tasks to assess their practical effectiveness?", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: After the rebuttal, the reviewers remain concerned about the motivation, technical novelty, and comparisons with prior work. I have included some reviewer comments below:

``Introduction: What is the importance and application of vertical federated learning? Why should we consider VRlog and VRLR in vertical settings? What are their applications? What is a coreset? Why should we consider a coreset? Is coreset the only way to address the communication complexity issue? What are the prior studies/results about vertical coreset? Are there limitations in these results? Answering these questions in the introduction can make the motivation and studied problem clearer to readers who are not that familiar with vertical federated learning or coreset.

Technical novelty: Since not all algorithms are new, the contribution section should clearly mention this. Then, the technical novelty lies in adapting the prior Lewis weight to vertical coreset construction, e.g., what obstacles exist in this adaptation and how to overcome them. The current contribution section does not sufficiently distinguish the novelty of the paper and previous contributions.

Comparison with Huang et al. (2022): It is useful to provide examples to show the best theoretical improvement in corset size. The example in the author's response needs to be added properly.” 

Overall, I recommend a weak accept.
Decision: Accept (poster)