Efficient Heterogeneity-Aware Federated Active Data Selection
Authors: Ying-Peng Tang
Chao Ren
Xiaoli Tang
Sheng-Jun Huang
Lizhen Cui
Han Yu
Venue: ICML 2025 poster (2025)
Keywords: Federated learning
Active learning
Leverage score sampling
Primary area: general_machine_learning

Abstract: Federated Active Learning (FAL) aims to learn an effective global model, while minimizing label queries. Owing to privacy requirements, it is challenging to design effective active data selection schemes due to the lack of cross-client query information. In this paper, we bridge this important gap by proposing the \underline{F}ederated \underline{A}ctive data selection by \underline{LE}verage score sampling (FALE) method. It is designed for regression tasks in the presence of non-i.i.d. client data to enable the server to select data globally in a privacy-preserving manner. Based on FedSVD, FALE aims to estimate the utility of unlabeled data and perform data selection via leverage score sampling. Besides, a secure model learning framework is designed for federated regression tasks to exploit supervision. FALE can operate without requiring an initial labeled set and select the instances in a single pass, significantly reducing communication overhead. Theoretical analyze establishes the query complexity for FALE to achieve constant factor approximation and relative error approximation. Extensive experiments on 11 benchmark datasets demonstrate significant improvements of FALE over existing state-of-the-art methods.

Efficient Heterogeneity-Aware Federated Active Data Selection
Ying-Peng Tang'
Chao Ren
Xiaoli Tang'
Sheng-Jun Huang
Lizhen Cui
Han Yu
Abstract
2 global data selection
④
global model learning
Federated Active Learning (FAL) aims to learn effective global model, while minimizing label queries. Owing to privacy requirements, it is chal- lenging to design effective active data selection schemes due to the lack of cross-client query in- formation. this paper, we bridge this important gap by proposing the Federated Active data selec- tion by LEverage score sampling (FALE) method. It is designed for regression tasks in the presence of non-i.idd client data to enable the server to select data globally in privacy-preserving man- ner. Based on FedSVD, FALE aims to estimate the utility of unlabeled data and perform data se- lection via leverage score sampling. Besides, a secure model learning framework is designed for federated regression tasks exploit supervision. FALE can operate without requiring initial labeled set and select the instances in single pass, significantly reducing communication over- head. Theoretical analyze establishes the query complexity for FALE to achieve constant factor approximation and relative error approximation. Extensive experiments on 11 benchmark datasets demonstrate significant improvements of F FALE over existing ofte-off-theane art methods.
Server
gateragate data information
Client
Client 2
Client k
@ query & label
Oracle
Oracle
Oracle
Figure I. The overall framework the proposed method. First, the server aggregates data information from each client to facilitate data selection. Next, seleets the most informative data points and returns their corresponding indexes the respective clients. The clients then label the selected data locally. Finally. the global model is trained on the server using the masked features and labels of the queried data.
performance from an oracle for labeling, thereby reducing the labeling cost while maintaining high model performance. Traditional AL approaches usually focus the centralized learning setting, where all the data is readily accessible. However, in many real-world applications, data is stored in a distributed manner, raising the need to consider com- munication costs, or across multiple parties, in which the data cannot be directly accessed due to privacy concerns and data governance regulations (Regulation, 2016). In these challenging settings, existing methods often do not suffi- ciently address data privacy, computational constraints, and communication overhead. Consequently, their performance can be limited.
1. Introduction
Training effective machine learning models typically relies on large-scale labeled datasets, which are often expensive and consucons to obtain. Active Learning (AL) (Set- tles, 2009) addresses this issue by selectively querying the most usefuul unlabeled data points for improving the model
College of Computing and Data Seience, Nanyang Technolog- ical University, Singapore "School of Electrical Engineering and Computer Science, KTT Royal Institute of Technology. Sweden College of Computer Science and Technology. Nanjing Univer- sity of Aeronautics and Astronautics, Nanjing, China "School of Software, Shandong University, Jinan, China. Correspondence to: Han Yu thaanyuuue... ett...u.ss>....
Federated Learning (FL) (Yang et al., 2019; 2020) emerges as an effective learning paradigm to address these challenges by enabling collaborative model training across multiple decentralized devices or institutions. It tries to learn an accurate global model by aggregating local model updates from multiple clients, without sharing raw data. Due to the high demand for data privacy and security, each client usually needs to label their own data locally and only share the model updates during the learning process (Yang, 2021;
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Efficient HelerogeneityyAAwre Federated Active Data Selection
Ren et al., 2024; Weng et al., 2025). However, this yields high risk of knowledge overlapping among clients data, thus waste of labeling costs. This necessitates the research on Federated Active Learning (FAL) (Wu et al., 2022; Kim et al., 2023; Zhang et al., 2023a; Cao et al., 2023), to en- model learning
using Rgd d/e) queries with high probability in FAL setring, where d is the feature dimension, 6 is the error con- trol parameter. We demonstrate the effectiveness of our proposed FALE approach through extensive experiments on 11 benchmark datasets, showing significant improvements over existing methods.
able label-efficient and in decentralized environments.
In FAL, each client possesses its own dataset, which may contain limited or no initially labeled data, and the data distribution can vary significantly across clients. The objec- tive is to learn an effective global model while minimizing the number of data queries among clients, all under strict privacy constraints. The major challenges in FAL includes 1) designing a data selection algorithm that operates without direct access to the data and within limited communica- tion budget, and 2) establishing theoretical guarantees of the query complexity of the active selection algorithm in distributed and
2. Related Works
AL (Settles, 2009; Ren et al., 2021) focuses on selec- tive querying of high-potential unlabeled data. Numer- ous query strategies have been developed, generally falling into two categories: informativeness- based (Kirsch et al., 2019; Huang et al., 2024) and representativeness based (Sener & Savarese, 2018; Sinha et al., 2019) approaches. Informativenes--based methods measure the prediction un- certainties of data points, while representativeness based methods aim to capture the underlying data distribution by data selection. However, most existing AL algorithms assume centralized data storage, which restricts their appli- cability in decentralized settings.
learning scenario. Ex- isting FAL methods typically employ local data selection strategies to comply with the privacy regulation, where each client independently selects data samples for labeling based on local model (Wu et al., 2022), global model (Kim al., 2023) and data distributions (Zhang et al., 2023b). These approaches can unavoidably result in overlapping queries due to the limited coordination among clients and incom- plete knowledge of the global data landscape. Furthermore, the theoretical guarantees regarding the query complexity of active selection algorithms remain underexplored.
Leverage score sampling is an effective technique with provable guarantees for active fz-regression problems minş || - yxll (Woodruff et al., 2014; Mahoney. 201 I), where the feature matrix X E Raxd is known while the label vector y E R" needs to be queried with some costs. Theoretical analyses are widely conducted for ob- taining (1 ++ e)-aprroximate solutions, i.e., ||X - -lll S (1 + c)l Ull, where O' is the output of the algo- rithm and 0 is the true minimizer. For examples, Mahoney (2011) show that Od d suffices to solve. Chen & Price (2019) propose algorithm that achieves the optimal (d/e)) query complexity. Besides, the time complexities have also been analyzed (Woodruff et al., 2014). How- ever, existing methods are designed for centralized learning settings and its applicability to tributed learning scenarios is underexplored.
In this paper. we propose a novel FAL method, called FALE, for regression task on non-i.i.d. client data, shown in Fig. 1. Our proposed method designs a global selector that minimizes redundant information across clients, as well as a global model learning paradigm, supported by theo- retical guarantees on the query complexity. To achieve the effective data selection, our method leverages the lat- est FedSVD method (Chai et al.. 2022; 2024). which is a sewacc-preserving. method for Singular Value Decomposi- tion (SVD) in FL setting. FedSVD provides an efficient mechanism to gathering global information without expos- ing individual client data. Based on these results, we employ leverage score sampling (Mahoney, 2011; Woodruff et al., 2014) to identify and query the most informative data points. To fully exploit the queried supervision, we further pro- pose a model learning paradigm for federated regression. It securely trains a global model on the server by using masked feature matrices and label vectors of the queried data. Then, the learned model can be unmasked with a se- cret matrix on the client side. In this way, FALE can operate with no initial labeled set and select instances in a single pass, substantially reducing communication overhead. Fur- thermore, our theoretical analysis shows that our proposed FALE method achieves a constant factor approximation us- ing Ord d) queries, and relative error approximation
and dis-
FL (Liu et al., 2024; Ren et al., 2025; Fan et al., 2025) is decentralized approach to machine learning where multiple clients collaboratively train a model without sharing their raw data. Perhaps the most popular setting is the horizontal FL (Yang et al., 2019), where multiple clients have the same feature space but different data distributions. Furthermore, according to the data distributions among clients, it can be further categorized into i..d. (Yang, 2021) and non-i.i.d. (Lu et al., 2024) settings. Most of existing FAL methods focus on i.i.d. setting and apply off-the-shelf AL algorithms on each local node independently (Wu et al., 2022; Zhang et al., 2023b). The selections from different clients may contain repeated and redundant supervision, leading to suboptimal global model performance. There are some works studying the non-i.i.d. client data for federated active classification problem (Kim et al., 2023; Zhang et al., 2023a; Cao et al.,
2

---

Efficient Helerogeencty-AAwre Federated Active Data Selection
2023). They share similar idea that considers both informa- tiveness and representativeness in data selection. However, the querying is also conducted locally, which can be myopic and suboptimal. Besides, the theoretical guarantees of the query complexity has not been analyzed.
Leverage Score Sampling Leverage score sampling (Ma- honey, 2011; Woodruff et al., 2014) samples rows in a matrix with probability proportional to their leverage scores:
Definition 3.1 (Statistical Leverage Score), The leverage score r'( of the 7th row æ, of a matrix X E Rxxd is equal to: T' ((X) - 2 (x"x) Fi
3. Preliminaries
(1)
Moreover, when X is column full-rank, r'() - lle U... where the columns of U is an orthogonal basis of the column space of X.
U
Notations and Problem Settings Throughout the paper, we denote scalars by lowercase letters, vectors by bold lowercase letters, and matrices by bold uppercase letters. || denotes the norm of a vector. ej represents the j- th standard basis vector, where the j-th entry is equal to 1, and all other entries are O. This work focuses on the horizontal FL with non-i.i.d. data, where multiple clients have the same feature space but different data distribu- tions. Assuming that there are k clients, each client i has its own dataset D; = {ar )== which is assumed to be fully unlabeled. a. E IRd is the feature vector. We de- note X; = [x] ..... I as the feature matrix of data in client i, and y: = ly! .......... "."TT E R is the unknown label vector. n4 is the number of data points in client i, and n === E ny. Denote by X = = XT e Rnxd We assume that X is column full-rank and n >> d.
Importance Sampling Matrix Importance sampling ad- justs the weights of sampled data points to preserve the underlying distribution.
Definition 3.2 (Importance Sampling Matrix). Let
pa E (0, 1]"h be a given set of probabilities with P. = 1. A matrix S is an n, x n importance sampling matrix if each of its rows is chosen to equal ,., -e with probability proportional to pt. nt is the sampling size.
4. The Proposed FALE Method
4.1. Global Data Selection
Initially, each client has empty labeled dataset C; = 0 and unlabeled set U; = D, At each FAL iteration, each client i selects a subset of data Q; C U; for querying and update the sets L; = L; U 2. 24; = 24 \ 2, Then, a global model 09 is trained using the queried data by, e.g., FedAvg (McMahan et al., 2017). Existing FAL methods iteratively repeat this cycle until the querying budget ex- hausted or specific performance criteria are met. In contrast, the method proposed in this paper is one-pass querying approach, selecting all data points in a single iteration.
To perform global data selection in FL, we need to gathering necessary information of all clients' data, while preserving privacy. Fortunately, a recent technique called FedSVD (Chai et al., 2022) provides a secure and efficient way to achieve this goal. As introduced in Sec. 3, it calculates the SVD results for all clients' data, which provides abundant information for data selection. Therefore, our proposed FALE method first invokes VD as a subroutine. No- tably, the clients are only required to recover the left singular matrix to reduce the communication cost. After this process, each client will have U,. Next, each client calculates the leverage scores of their local data T; = [T......, 771), where .f |le] U= The clients then send the leverage scores to the FL server for aggregation.
FedSVD FedSVD (Chai et al., 2022) calculates the SVD of the entire dataset securely in FL setting. The main steps of the FedSVD is summarized as follows
On the server side, it concatenates the leverage scores to obtain t = [TI [T,...., ]. and calculates the sampling prob- ability p [pI..... P.).. where p; = - Given the query budget ny. the server performs i.i.d. sampling of in- tegers from the set [1...., n] with probability p. Note that duplicates may appear during sampling, they only affect the training weights and do not reduce the query budget. The server continues sampling until ng distinct data points have been selected, and we denote the total number of sam- ples drawn as ng. Denote by Q = (q1,..., In,) } the set of sampled integer indices. Construct an importance sampling matrix S E R",x", where each row i is equal to MaoPl, .eg with probability p;, for i = 1,... n,. After sampling, the server sends the selected indices to the respective clients, which label these data points locally.
(1) A trusted authority generates random orthogonal ma- trices P E R.xn and Q E RRdxd, where P can be sim- plified as diag(PI..... Px) for computational efficiency, P; E Rmexxs is a random orthogonal matrix. Q is sent to all clients and P. is sent to client i.
(2) All clients mask their local data by X P,X,Q and send X to the FL server.
(3) The FL server securely aggregates X' from all clients.
(4) The FL server performs SVD to obtain X' = U'EV' where U E Raxx Σ E Raxd, and V' E Rdxd (5) Users download the decomposed matrices and recover them using P; and Q. After recovering, each user will have the complete Σ and VT, but only part of U, denoted by U,, that corresponds to their local data.
3

---

Efficient HelerogennityyAAwre Federated Active Data Selection
4.2. Global Model Learning
Algorithm 1 The FALE Algorithm
Input: query budget ngy feature matrices X;, i 1,..., k.
One simple way to learn the global model is to perform global aggregation of the local models from all clients, e.g., using FedAvg (McMahan et al., 2017). However, this method can be suboptimal due to the non-i.idd data distri- bution among clients. Inspired by Chai et al. (2022), we propose to learn global model directly on the server using the masked feature matrix and label vector of the queried data points.
Output: prediction model 0
1: Initialization: ny + 0, [1. 2, 0, for
1. 1....,k. k.
Global Data Selection:
2: Perform FedSVD and each client obtains U, the left
singular matrix that corresponds to their local data
3: Each client calculates T. = |le] Ug|l² and sends to the server
Specifically, denote by Xf E gdl and of E _² as the feature matrix and label vector of the labeled data in client i, where n² the number of labeled data points. Clients mask their feature matrix by P,X.QQ and the label vector by Pay. where Q E Rdxd is the orthogonal matrix gen- erated in FedSVD, P. Raaxxl is an arbitrary random orthogonal matrix generated by client locally. The masked feature matrix and label vector are then sent to the server for aggregation. According to Chai et al. (2022), such a masking operation can preserve the privacy of individual data, as given a masked feature matrix X' = [PXQ], there are infinitely many possible X can be masked into X'.
Server aggregates the leverage scores T = [TI...., The and calculates sampling probabilities p. where Pj
T /||T|||
5: while Fewer than Ny distinct elements sampled do
6: + sample a number from (....,,,en((T)) with
replacement with probability p
n, f- n +
- append(L//Pd)
i q belongs to which client
10: append to Q
11: end while
12: 8; + 8/8/ 1,..,,
13: Server sends Q1..... Q2 to corresponding clients
The server performs secure aggregation, as Step 3 in FedSVD, to obtain the complete masked feature matrix [PX and the label vector Py where X&]
Global Model Learning:
14: Each client locally labels the selected data points in
Qi. (Note that repeated entries in Q, will not use extra querying budger)
x = [Xf, . and yf = "yf...., P = diag(P (P,,..., ,x). The importance sampling matrix S is then transformed to a reweighting matrix such that the non- zero element in each row is moved to the diagonal, denoted by S' IR xR, The server solves the following optimiza- tion problem to learn the global model:
15: Clients mask X. and yf by P.XfQ and P.yf and
send to the server
16: S' +- diag(s)
17: Server aggregates masked data and solves Ov arg minnl|PS'** PS' p
18: Server sends @ to clients
min I -
19: Clients recover the prediction model 0 = =QTA
20: Return: 09
or equivalently,
4.3. Analysis
min P|
4.3.1. PRIVACY ANALYSIS
The server cannot reveal the original matrix and predic- tion model: The privacy of the raw data is guaranteed by the FedSVD algorithm, as the masked feature matrix X can be mapped to infinitely many raw feature matrices X. In the selection phase, the server only has information of the lg norm of the left singular value matrix of local client data. After obtaining the selection probability, the server distributes the index of selected data to each client for la- beling, it cannot recover the raw data. The privacy of the prediction model is also guaranteed with a similar argument, as the global model learned on the server is encrypted by a secret random orthogonal matrix Q. According to the Theorem in (Zhang et al., 2019), the masked vector
Once the server computes a solution @ to the optimization problem (2), it sends 6 to all clients. Each client then recovers the prediction model by computing 0² = Q ga.
Our proposed global model learning method offers several benefits. First, it preserves the privacy of raw data and the prediction model, as the global model learned on the server needs to be recovered on the client side. Second, solving the optimization problem with masked data is equivalent to the original regression problem, thereby fully utilizing the available supervisory information.
Overall, our proposed FALE is summarized in Algorithm

---

Efficient Helerogeencty-AAware Federated Active Data Selection
computationally indistinguishable from a random vector.
Our proposed algorithm selects unlabeled data proportional their leverage scores and re-weights them in global training phase. Using the properties of leverage score sampling, this approach provides a subspace embedding (Woodruff et al., 2014) of X, which is a key component in proving our theorem. The detailed proof is provided in the appendix A.
Remark:
The users cannot know the data owned by the others: In our proposedF'AL2 AALE method, each client holds local data and U4. P. that correspond to their data. Although all clients share the same matrix Q, knowing Q, U2 P. is insufficient to reconstruct any other client's local data, as discussed in Chai et al. (2022). During the model learning phase, the global model trained on selected instances may reflect a coarse distribution of the global dataset, but it does not directly reveal the underlying data.
Our theoretical results establish that the query complexity of our method in the FAL setting matches with the leverage score sampling of the centralized setting (Mahoney, 201 I; Derezinski et al., 2018). .. By securely computing the lever- age scores across different clients in the FL framework, we establish that leverage score sampling can be effectively applied to a privacy-preserving decentralized learning envi- ronment without any degradation in performance.
4.3.2. COMMUNICATION COST ANALYSIS
The overall communication cost of FALE includes four main components: (1) performing FedSVD, (2) transmitting lever- age scores and the indices of selected data, (3) uploading masked feature matrices and label vectors, and (4) sharing the global model.
5. Experiments
5.1. Experimental Setup
FedSVD is highly efficient and scalable to billion-scale datasets. For detailed analysis of its communication over- head, we refer to the work (Chai et al., 2022). The trans- mission of leverage scores and selected data indices incurs relatively low costs, with complexities of (n) and On.,), respectively. Since the masked feature matrices retain the same dimensionality as the raw data, their transmission does not introduce significant additional overhead. Furthermore, the communication cost associated with global model trans- mission remains consistent with standard FL frameworks.
We employ 9 UCI (Dua & Graff, 2017) and OpenML (Bischl et al., 2021) regression benchmarks in our experiments. The information of is summarized Table 1. For each dataset, we uniformly sample 20% of the instances for testing, while the remaining instances are distributed across k 10 clients in non-i.i.d manner, with each client receiving a different number of instances. To simulate the non-i.i.d. setting in regression task, we perform binning on the regression target vector, with the number of bins equal to the number of clients. We then adopt the Dirichlet distribution strategy (Yurochkin et al., 2019) with Dirichlet alpha of 5 to assign instances clients using the bins class label. Note that some clients may not have instances from certain bins. We believe this is common scenario in real-world applications. Since most existing FAL methods require an initial labeled set, we randomly select 1% of the instances from each client to form the initial labeled set. FALE does not require any initial labeled data, although it can accommodate an initial labeled set if available. At each iteration, we allocate a query budget of instances per client, resulting in a total of 50 instances queried per round. Our method performs
A key advantage of FALE is its single-pas, selection ap- proach, where communication is performed only once. This makes it a caattuumiiaaiioffffciieeee solution.
4.3.3. THEORETICAL ANALYSIS
We analyze the query complexity of FALE as follows.
Theorem 4.1. Considering federated learning with non- i.i.d. data. Let k be the number of clients, c E (0, 1] be an error parameter, X; E Raaxd
xd be the corresponding data ma- trices and y: E Ri be the initially unknown target vector. Denote by X- [X] ,X,,,.,,]]] .J and y = [y] .......> y 0" arg ming |xe- - 2/2- Algorithm computes the global leverage scores for the data in each client. Moreover, if Algorithm I queries D(dlog d) data points and outputs the model 09, it holds with probubility at least 0.99 that
Table 1. The summary of datasets.
Dataset (Reference)
# Ins..
# Fea.
ct (Graf et al., 2011)
53500
379
kegg undir (Shannon et al., 2003)
64608
27
||X09 -ilă < aa|x0 -
(4)
online_video (Deneke et al., 2014)
68784
26
wec sydney (Neshat et al., 2018)
72000
48
sarcos ( (Vijayakumar & Schaal, 2000)
44484
21
with constant a. In addition, if queries Mdd d + d/e)
diamonds (OpenML ID: 42225)
53940
29
data points and outputs 89, it holds with probability at least 1 1/3 that
stock (OpenML ID: 1200)
59049
9
protein (OpenML ID: 42903)
45730
9
mir knn_rng (OpenML ID: 42454)
111753
132
|| | 2112 S (1 (1+ XX -
(5)
5

---

Efficient Heterogencity-Awan Federated Active Data Selection
FALE
1.1
FALE local
FALE
Mean Squared Error
0.35
FALE local
Mean Squared Error
Mean Squared Error
FALE-local
Randern
Random
Random
0.30
ACS-FWV
ACS FW
ACS FW
0.25
0.9
CoreSet BADGE
BADGE
BADGCE
0.20
LCMD LOGD
0.8
LCMD
L0G0
1.0
LOGO
LCKD
0.15
0.5
3000
6000
9000 12000 15000
3000
6000 9000 1200 15000
3000
6000
9000
12000 15D00
Number queries
Number of queries
Number of queries
(a) ct
(b) kegg_undir undir
(c) online.vidco vidco
1.0
Mean Squared Error
FALE--oc E-local
FALE
Mean Squared Error
F- F-lccal
Mean Squared Error
FAL E-local
Randorn
0.8-
Rabdomt:
Random
DAIT
BAIT
BAIT
ACS FW
ACS FW
ACS-FW
1.25
CoreSet
CoreSat
CaroSat
BADGE
BADGE
1.0
BADIGE
1.00
0.4
LCMD
0.75
LOGD
0.2
LOGO
0.5
LOGd
0.50
0.0
3000
6000
9000
12000
15000
3000
6000 9000
12000 15000
3000
6000
9000
12000 15000
Number queries
Number of queries
Number of queries
wec_sydney
(c) sarcos
(f) diamonds
Mean Squared Error
FALE-local
Mean Squared Error
1.1-
FALE-Hoc
FALE
Mean Squared Emro
0.8
FALE
FALE-local
Random
1.2
BAIT
1.0-
BAIT
RAIT
ACS-FW
1.0
CoreSet BADGE
CoreSet
CoreSet
BADGE
BADGE
0.8
LCMD
LCMD
0.6-
LCMD
1060
Loge
1060
0.6
0.8-
3000
6000 9000 12000
15000
3000
6000 9000 12000 15000
3000
6000
9000 12000 15600
Number of queries
Number of queries
Number of queries
(g) stock
(h) protein
(i) mlr knn_rng
Figure 2. The learning curves of the compared methods. The error bars represent the standard deviation of the performances over 10 runs.
global data selection within this same budget. The data splitting process is repeated 10 times, and the performance comparison results are averaged over these runs.
Random:
Uniformly select unlabeled data points for querying.
BAIT (Ash et al., 2021): Select informative data points by optimizing a bound on the maximum likelihood esti- mator error in terms of the Fisher information.
For comparison, we include the state-of-the-an FAL method LOGO (Kim et al., 2023) in our experiments. Although LOGO originally designed for classification tasks, Kim al. (2023) suggests that its uncertainty scoring function can be replaced with alternative informativeness scoring functions. Based on this, we extend LOGO to the regression setting by replacing its entropy-based selection mechanism with the pegresssion-spccffii uncertainty metric BAIT (Ash al., 2021). Other existing FAL. methods are primarily designed for classification tasks, and adapting them to re- gression problems remains non-trivial challenge. In addi- tion, compare our approach with state-of-the. active regression methods that operate locally within each client. Specifically, the following methods are included:
ACS-FW (Pinsler et al., 2019): Select a batch of repre- sentative data by optimizing a sparse subset approxima- tion the log posterior induced by the full dataset.
CoreSet (Sener & Savarese, 2018): Select batch of representative data points that minimizes the maximum distance to the remaining data.
LCMD (Holzmüller al., 2023) (Largest Cluster Max- imum Distance): Select batch of representative data points based on clustering.
BADGE (Ash et al., 2020): Select batch of informa- tive and diverse data points based on clustering and the gradient magnitude of the model parameters.
6

---

Efficient Helerogeenctyy-Aaree Federated Active Data Selection
Table Significance testing results (Win/Tie/Lan counts) based paired t-test with 0.05 significance level of PAIIS. R. (Algorithm 1, the upper table) and FALE-loca (Algorithm 2, the lower table) versus the rest methods. The comparison is conducted on the model performances when 10%, 20%, ..... 100% of the query budget are consumed over 10 runs of experiments.
FALE versus
Datasets
FALE-local
Random
BAIT
ACS-FW
CoreSet
BADGE
LCMD
LOGO
Total
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
80/0/0
diamonds
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
80/0/0
kegg undir.
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
80/0/0
mlr knn.
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
80/0/0
online video
2/8/0
10/0/0
10/0/0
10/0/0
2/8/0
2/8/0
2/8/0
10/0/0
48/32/0
protein
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
80/0/0
sarcos
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
80/0/0
stock
6/2/2
10/0/0
10/0/0
10/0/0
10/0/D
7/1/2
5/5/0
10/0/0
68/8/4
wecs
9/1/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
79/1/0
Total
77/11/2
90/0/0
90/0/0
90/0/0
82/8/0
79/9/2
77/13/0
90/0/0
675/41/4
FALE- FALE-local versus
Datasets
FALE
Random
BAIT
ACS-FW
CoreSet
BADGE
LCMD
LOGO
Total
0/0/10
10/0/0
10/0/0
10/0/0
10/0/0
0/10/0
1/9/0
10/0/0
51/19/10
diamonds
0/0/10
10/0/0
10/0/0
10/0/0
4/6/0
1/1/8
2/8/0
10/0/0
47/15/18
kegg-un -undi.
0/0/10
9/1/0
8/2/0
9/1/0
6/4/0
0/3/7
0/5/5
6/4/0
38/20/22
mir_knn.
0/0/10
10/0/0
10/0/0
10/0/0
7/3/0
6/3/1
5/4/1
10/0/0
58/10/12
online video
0/8/2
10/0/0
10/0/0
10/0/0
7/3/0
3/5/2
4/5/1
10/0/0
54/21/5
protein
0/0/10
10/0/0
10/0/0
10/0/0
10/0/0
9/1/0
10/0/0
10/0/0
69/1/10
sarcos
0/0/10
10/0/0
10/0/0
10/0/0
1/9/0
0/9/1
0/8/2
10/0/0
41/26/13
stock
2/2/6
10/0/0
10/0/0
10/0/0
10/0/0
2/8/0
1/9/0
10/0/0
55/19/6
wees
0/1/9
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
10/0/0
70/1/9
Total
2/11/77
89/1/0
88/2/0
89/1/0
65/25/0
31/40/19
33/48/9
86/4/0
483/132/105
LOGO (Kim et al., 2023): An FAL method that select informative and diverse data points locally.
5.2. Results
We plot the mean learning curves over 10 runs for the com- pared methods in Fig. 2. The mean and standard deviation of MSE the test set reported. Although we also include the learning curve of our proposed FALE method for comparison, it is important to note that FALE performs one-pass querying, meaning that each batch selection is independently determined and does not accumulate commu- nication overheads.
FALE: The method proposed in this paper, which per- forms global data selection and global model learning. FALE-local: A degenerated version of FALE that per- forms global data selection but trains the model locally. The algorithm is summarized in the appendix A.2.
Note that some of the active query strategies are originally designed for classification tasks. For these, we adopt the adaptation methods proposed by (Holzmüller et al., 2023) to extend them regression tasks. For all the other com- pared methods, the global model is trained using FedAvg (McMahan et al., 2017).
As shown in Fig. 2, FALE consistently outperforms bascline methods across all benchmarks, demonstrating the effec- tiveness of the proposed global data selection and global model training schemes in non-i.i.d. setting. FALE-local of- ten achieves the second-best performance or is comparable to the second-best method, demonstrating that our global selection strategy effectively identifies the most informative data points in each client. This allows the global model, even when aggregated using FedAvg, maintain strong performance. The learning curves of some baselines, such as LOGO and ACS-FW, exhibit an increase in test error as more data is queried on some datasets. This phenomenon aligns with our expectations. Because there are discrep- ancies between the data distribution of individual clients
We implement the regression model using PyTorch, consist- ing of a single layer to accommodate methods that require gradient information, as well the existing FL framework. The model is trained by optimizing the mean squared error (MSE) with the Adam optimizer, using a learning rate of 0.01 for 25 epochs. For local active regression methods, we utilize the implementation provided by Holzmüller et al. (2023). The implementation of LOGO (Kim et al., 2023) is sourced from the authors. The FL framework is built upon the FedLab (Dun Zeng & Xu, 2021) toolbox.

---

Efficient Helerogeneity--warr Federated Active Data Selection
Mean Squared Error
Mean Squared Error
Random
0.03
0.06
ACS FW
BAIT
CoreSet
0.02
0.04
BADGE
LCMD
LOGO
0.01
0.02
FALE
FALE-
3000
6000
9000
12000
15000
3000
6000
9000
12000
15000
Number of queries
Number of queries
(a) IMDB-WIKI
(b) CelebA
Figure The performance comparison results of the compared methods in the image regression datasets. The proposed methods conduct one-pass selection with query budget of 7500 and 15000.
and the latent distribution of the entire dataset. In such challenging setting, selecting data locally based repre- sentativeness may mislead global model learning. Among the baselines, LCMD and BADGE generally perform well, data selection is effective
images for training and 1 11K images for testing.
For each dataset, 5% of each client's data uniformly sam- pled form the initial labeled set. We employ pre-trained ResNet-50 to extract 2048-dimensions, feature vector for each image. All other empirical settings remain consistent with those described in the previous section.
indicating that clustering-basee in non-i.idd setting. This finding may serve as an inspira- tion for future research in this domain. The performance of Random and CoreSet varies across datasets, suggesting that there remains significant room for improvement through the development of more effective AL algorithms.
The comparison results are presented in Fig. 3. Notably, FALE and FALE-local perform one-pass querying, with query budgets of 7,500 and 15,000, respectively. The results indicate that FALE significantly outperforms iterative selec- tion methods, while FALE-local achieves performance com- parable to the second-best method. These findings demon- strate the effectiveness and cost-efficiency in terms of both label and communication the proposed FALE method in nigh-dimensional image data scenarios.
Table presents the significance testing results based on a paired (-test with a 0.05 significance level, conducted over 10 runs, comparing FALE and FALE-local with the other methods. The counts Win/Tie/Loss are calculated based on the model performances as the query budget is consumed in increments of 10%, 20%, ..., 100%, with 10 comparisons for each case.
The results show that FALE consistently outperforms the other baselines and rarely loses, demonstrating the effective- ness of the proposed framework. Additionally, FALE-local outperforms other local selection methods in most cases. No- tably, 77 out of the total 105 losses are attributed to FALE. These findings indicate that our global selection method can effectively identify the most informative unlabeled instances in non-i.i.d distributed data within the FL setting.
6. Conclusion
This paper presents a novel FAL method, FALE, which queries the most informative unlabeled data globally in a FL setting. FALE leverages FedSVD to extract cross-client query information, enabling global data selection and min- imizing redundant supervision across clients. Building on this, we employ leverage score sampling strategy for data selection and re-weighting. To fully exploit the queried data points, we further design model training scheme that securely learns the global regression model using the masked labeled data points on the server. Theoretical analy- sis demonstrates that FALE requires O(d log d) queries to achieve constant factor approximation and ( log d+d//e) queries to achieve relative error approximation with high probability. Extensive experiments on 11 regression bench- marks validate the effectiveness of the proposed method. The experimental results, compared with state-of-the-an FAL methods, show that F FALE significantly reduces the number queries to learn an effective global model on non-i.i.d. client data.
5.3. Study Image Regression Dataset
We further employ large scale image regression datasets to validate the effectiveness of the proposed method.
CelebA is a facial image dataset containing 162.7K training instances and 19.9K testing instances. Follow- ing Lyu et al. (2025), we use the abscissa of the right side of the mouth as the regression target.
WMDB-WIKI (Rothe et al., 2018) facial image dataset with age annotations. We adopt the dataset settings from Yang al. (2021), which include 191.5K
8

---

Efficient Helerogeencity-Aare Federated Active Data Selection
Impact Statement
of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 46-55, 2022.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chai, D., Zhang, J., Yang. L., Jin, Y., Wang. L., Chen, K., and Yang. Q. Efficient decentralized federated singular vector decomposition. In 2024 USENIX Annual Technical Conference, pp. 1029-1047, 2024.
Acknowledgment
Chen, X. and Price, E. Active regression via linear-sample sparsification. In Beygelzimer, A. and Hsu, D. (eds.), Proceedings of the 32nd Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 663-695, PMLR, 2019.
Chao Ren is supported, in part by Wallenberg-NTU Presi- dential Postdoctoral Fellowship, with Wallenberg AI, Au- tonomous Systems and Software Program (WASP); and the Swedish Research Council under contract 2024-06464. Sheng-Jun Huang is supported in part by the NSFC (U2441285, 62222605) and the Natural Science Founda- tion of Jiangsu Province of China (BK20222012). Lizhen Cui is supported in part by the NSFC No. 92367202. Han Yu is supported in part by the Ministry of Education, Singa- pore, under its Academic Research Fund Tier (RG101/24); the National Research Foundation, Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No. AISG2-RP-2020-019)
Cohen, M. B., Lee, Y. Musco, C., Musco, C., Peng, R., and Sidford, A. Uniform sampling for matrix approxi- mation. In Proceedings of the 2015 conference on Inno- vations in Theoretical Computer Science, pp. 181-190, 2015.
Deneke, T., Haile, H.,, Lafond, S., and Lilius, J. Vidco transcoding time prediction for proactive load balancing. In Proceedings of the 2014 IEEE International Confer- ence on Multimedia and Expo, pp. 1-6. IEEE, 2014.
References
Derezinski, M., Warmuth, M. K., and Hsu, J. Leveraged volume sampling for linear regression. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems, pp. 2510-2519, 2018.
Ash, J. T., Zhang, C., Krishnamurthy,, A., Langford, J., and Agarwal, A. Deep batch active learning by diverse, un- certain gradient lower bounds. In Proceedings of the 8th International Conference on Learning Representations. OpenReview.net, 2020.
Dua, D. and Graff, C. Uei machine learning repository, 2017. URL http: /ttp://arccceeeeeeee ics feriieddumm.
Dun Zeng, Siqi Liang, X. H. and Xu, Z. Fedlab: A flexible federated learning framework. arXiv preprint m:Xiv:2107.11221 2021.
Ash. J. T., Goel, S., Krishnamurthy, A., and Kakade, S. M. Gone fishing: Neural active learning with fisher embed- dings. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems, pp. 8927-8939, 2021.
Fan, T., Gu, H., et al. Ten challenging problems in federated foundation models. IEEE Transactions on Knowledge and Data Engineering, 2025.
Bischl, B., Casalicchio, G.. Feurer, M., Gijsbers, P., Hut- ter, F., Lang, M., Mantovani, R. G., van Rijn, J. N., and Vanschoren, J. Openml: A benchmarking layer on top of openml to quickly create, download, and share sys- tematic benchmarks. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021. URL https: //openreview wwt ? i di DCDDByKK.D........
Graf, F., Kriegel, H., Schubert, M., Pölsterl, S., and Caval- laro, A. 2d image registration in CT images using radial image descriptors. In Fichtinger, G., Martel, A. L., and Peters, T. M. (eds.), Proceedings of the Medical Image Computing and Computer- Intervention, volume 6892 of Lecture Notes in Computer Science, pp. 607-614. Springer, 2011.
Holzmüller, D.., Zaverkin, V., Kästnerr J., and Steinwart, framework and benchmark for deep batch active learning for regression. Journal of Machine Learning Research, 24(164):1-81, 2023.
Cao, Y., Shi. Y., Yu, B., Wang. J., and Tao, D. Knowledge- aware federated active learning with non-iid data. In Proceedings of the 2023 IEEE/CVF International Confer- ence on Computer Vision, pp. 22222-22232. IEEE, 2023. doi: 1LL11///CCC511000222000000
Huang, S., Li, Y., Sun, Y., and Tang, Y. One-shot ac- tive learning based on lewis weight sampling for mul- tiple deep models. In Proceedings of the 12th Interna- tional Conference on Learning Representations. OpenRe- view.net, 2024.
Chai, D., Wang, L., Zhang, J., Yang, L., Cai, S., Chen, K., and Yang, Q. Practical lossless federated singular vector decomposition over billion-scale data, In Proceedings

---

Efficient Heterogeenctyy-Awrr Federated Active Data Selection
Kim, S., Bae, S., Song, H., and Yun, S. Re-thinking fed- erated active learning based on inter-class diversity. In Proceedings of the 2023 IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 9944-3953. IEEE, 2023, doi: 10.1 10.11099CVR52229.220 2023335852229.22300884444
Ren, C., Dong, Z. Y., Yu, H., Xu, M., Xiong, Z., and Niyato, D. Esqft: Digital twin-driven explainable and secured quantum federated learning for voltage stability assess- ment in smart grids. IEEE Journal of Selected Topics in Signal Processing, 2024.
Kirsch, A.. van Amersfoort, J., and Gal, Y. Batchbald: Ef- ficient and diverse batch acquisition for deep bayesian active learning. In Proceedings of the 33rd Annual Con- ference on Neural Information Processing Systems, pp- 7026-7037, 2019.
Ren, C., Yu, H., et al. Advances and open challenges in federated foundation models. IEEE Communications Surveys and Tutorials, 2025.
Ren, P., Xiao, Y., Chang, X., Huang, P.-Y., Li, Z.., Gupta, B. B., Chen, X., and Wang, X. A survey of deep active learning, ACM computing surveys, 54(9);1-40, 2021.
Liu, F., Zheng, Z., Shi, Y., Tong, Y., and Zhang, Y. A survey on federated learning: a perspective from multi- party computation. Frontiers of Computer Science, 18(1): 181336, 2024.
Rothe, R., Timofte, R., and Gool, L. V. Deep expectation of real and apparent age from a single image without facial landmarks. International Journal of Computer Vision, 126(2-4): 157, 2018.
Lu, Z., Pan, H., Dai, Y., Si, X., and Zhang, Y. Federated learning with non-iid data: A survey. IEEE Internet of Things Journal, 2024.
Sarlós, T. Improved approximation algorithms for large ma- trices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 143-152. IEEE Computer Society, 2006.
Lyu, J., Zhang, Y., Lu, X., and Zhou, F. Task diversity in bayesian federated learning: Simultaneous processing of classification and regression. Proceedings of the 31 SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
Sener, O. and Savarese, Active learning for convolutional neural networks: core-set approach. In Proceedings of the 6th International Conference on Learning Represen- tations, 2018
Mahoney, M. W. Randomized algorithms for matrices and data. Foundations and Trends@ in Machine Learning. 3 (2):123-224, 2011. doi: 10. (0.156/22000000335.
Settles, B. Active learning literature survey. Technical report, University of Wisconsin- 2009.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and learning of deep networks from decentralized data. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics, pp. 1273-1282. PMLR, 2017.
y Arcas, B. A. Communication-effiae
Shannon, P., Markiel, A., Ozier, O., Baliga, N. S., Wang, J. T., Ramage, D., Amin, N., Schwikowski, B., and Ideker, T. Cytoscape: software environment for integrated models of biomolecular interaction networks. Genome Research, 13(11):2498-2500 2003.
Musco, C., Musco, C., Woodruff, D. P., and Yasuda, T. Active linear regression for lp norms and beyond. In Proceedings of the 63rd IEEE Annual Symposium Foundations of Computer Science, pp. 744-753. IEEE, 2022.
Sinha, S., Ebrahimi, S., and Darrell, T. Variational adversar- ial active learning. Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision, pp. 5972- 5981, 2019.
Neshat, M., Alexander, B., Wagner, M., and Xia, Y. A de- tailed comparison of meta-heuristic methods for optimis- ing wave energy converter placements. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1318-1325, 2018
Vijayakumar, S. and Schaal, S. Locally weighted projection regression: An o(n) algorithm for incremental real time learning in high dimensional space. In Proceedings of the I 7th International Conference on Machine Learning, volume 1, pp. 288-293, 2000.
Pinsler, R., Gordon, J., Nalisnick, E. T., and Hernández- Lobato, J. M. Bayesian batch active learning as sparse subset approximation. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, pp. 6356 006666367720 2019.
Weng. S., Ren, C., Xiao, M. and Skoglund, M. Heterogeneity aware client sampling: A unified solu- tion for consistent federated Icarning. arXiv preprint arXiv:2505. / 11304, 2025.
Regulation, P. Regulation (eu) 2016/679 of the european parliament and of the council. Regulation (EU), 679:
Woodruff, D. P. et al. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-157, 2014.
2016, 2016.
10

---

Efficient Heteragennitty-Awar Federated Active Data Selection
Wu, X., Pei, Chen, C., Zhu, Y., Wang. J., Qian, Q., Sun, Q., and Guo, Y. Federated active learning for multicenter collaborative disease diagnosis. IEEE Transactions Medical Imaging, 2022.
Yang, Q. Toward responsible ai: An overview of federated learning for user-centered privacy-preserviie computing. ACM Transactions on Interactive Intelligent Systems, 11 (3-4):1-22, 2021.
Yang, Q.. Liu, Y., Chen, T., and Tong. Y. Federated machine learning: Concept and applications. ACM Transactions Intelligent Systems and Technology. 10(2):1-9,, 2019.
Yang, Q. Fan, L.,, and Yu, H. Federated Learning: Privucy and Incentive. Springer, Cham, 2020.
Yang, Y., Zha, K., Chen, Y., Wang, H., and Katabi, D. Delv- ing into deep imbalanced regression. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 11842- 11851. PMLR, 2021.
Yurochkin, M., Agarwal, M., Ghosh, S., Greenewald, K., Hoang, N., and Khazaeni, Y. Bayesian nonparametric federated learning of neural networks. In Proceedings of the International Conference on Machine Learning, pp. 2252-7261. PMLR, 2019.
Zhang, Y., Xiao, X., Yang. L.-X., Xiang, Y., and Zhong, S. Secure and efficient outsourcing of pea-based face recognition. IEEE Transactions on Information Forensics and Security, 15:1683-1695 2019.
Zhang, Z., Qi, F., Li, S., and Xu, C. Affectfal: Federated active affective computing with non-iid data. In Pro- ceedings of the 31st ACM International Conference on Multimedia, pp. 871-882, ACM, 2023a. doi: 10.1 145/ $581783.3612444
Zhang, 7.,, Qi, F., Li, S., and Xu, C. Affectfal: Federated active affective computing with non-iid data. In Pro- ceedings of the 31st ACM International Conference Multimedia, pp. 87 1 8-82882, 2023b.

---

Efficient Heterogeenityy-Aare Federated Active Data Selection
A. Appendix
A.1. Proof of Theorem 4.1
We begin by introducing the definition of subspace embedding.
Definition A.1 (f2 Subspace Embedding). Let E (0, 1) be the distortion parameter. matrix S E IR.,, is said to be an l2 e-subspace--mbeeddii matrix for X Rxxd if holds simultaneously for all vectors 0 E E2 that (1 e) X -
||SX0|| (1 |X
Recall that Algorithm invokes FedSVD subroutine to securely calculate the left singular matrix of the data in each client. The clients then upload the lg norm of each row of the left singular matrix to the server. According to Definition 3.1, the server has the leverage scores T of the entire dataset X.
The server samples the data according to the leverage scores p = [11,.... "rt.....Prll ,nl.. where p. = = Then, it calculates a re- weighting matrix where each row is equal to ynsPa, Cz,, for 1,.... ng. Is easy to verify that S is an importance sampling matrix according to Definition 3.2.
Now we introduce the following lemma.
Lemma A.2 (Constant-factor Subspace Embedding, (Cohen et al., 2015, Theorem 7.1)). Given X E Raxd, Suppose that 2 S for all E [n]. where Zp log oh a sampling parameter. Let n, = = 4. I R= reweighted sampling matrix with sampling probability p, li for all then S is an &2 g-suspace-embeedding matrix for X with probability at least ò. 8.
nu
Since ||| < d, let n, lo d), by applying Lemma A.2, we have that S has constant- factor subspace embedding property of X with probability at least 1 - 5.
Nota that the output of Algorithm 09 is exactly 0 = arg ming |XX Syl12. To see this, note that 0s = Q Òs and an orthogonal matrix which does not change the problem, i.e.,
min PSXQQ PSylí = min SXXQ Syll min |SXX - Syl1a
(6)
Next, we show that 09 is a constant factor approximation to the minimizer of ming || y/12-
Lemma A.3 (Constant factor approximation, (Musco et al., 2022, Theorem 3.2)). For X E Rexd d y E R". For any 5 E (0, 1), i = arg ming |SX0 Syllž, such that
||xx - Sylla S (1 + min |XX Syy22.
where S E Rn is an &a } susuppuee-embbddding matrix of X. Then, with probability at leust 1 8,
X 2112 - 64(3 + 72/22/2 min X y112-
(8)
By letting 5 = 1/100 and 7 = then | yl12 S a min | yll for constant at
To achieve relative approximation, introduce the following lemma. Lemma A.4 (Relative error approximation, (Sarlós, 2006, Theorem 12 and Claim 13)). Given matrix X Bodd For all Ull where the columns in are orthonormal basis of the column space of X. Let S E R be row-sampling matrix such that Pr (So)
1 Isis n set
Ce for all 1 S S n.- For any 0 < S 1, if = St (d d + d/e).
n.P.
holds with probability at least 1/3 that
X
v
< (1 + cc] -113.
(9)
where arg ming | y11., and 0 arg ming ||Se
Sy 123
12

---

Efficient Helerogeencty--Aare Federated Active Data Selection
Let the sampling size n, be 52 log d d/e). By applying Lemma A.4, have
x 3 Σ (1 c)le y112.
(10)
holds with probability at least 1/3, which completes the proof.
A.2. Algorithm of FALE-local
We summarize the main steps of FALE-local method follow
Algorithm 2 FALE-local Algorithm
Input: query budget Ntg feature matrices X,, 1, 1....,k.
Output: prediction model
Initialization: Q t- for i=l,....k.
2: Perform FedSVD and each client obtains U, the left singular matrix that corresponds to their local data
3: Each client calculates T! [le]Ual Uzll and sends to the server
4: Server aggregates the leverage scores [T, .r..... Tk] and calculates sampling probabilities p, where pj = =
5: while Fewer than ny distinct elements sampled do
6: q sample number from , len(T)) with replacement with probability
7: i < q belongs to which client
8: append q to Q
9: end while
10: Server sends .,...., 2s to corresponding clients
Clients receive the queried indexes of data and label them locally
Clients train regression model locally based on their labeled data and upload the model parameters to the server 13: Server aggregates local models using FedAvg to obtain the global model 0
14: Return: 0
13


Reviews:
[{"review_id": "YizsjRjubz", "reviewer": "Reviewer_2DKU", "summary": "This paper investigates the data selection problem in Federated Active Learning (FAL) and introduces FALE, a score-based sampling method. FALE leverages FedSVD to extract cross-client query information, enabling a leverage score-based sampling strategy for data selection and re-weighting. Theoretical analysis shows that FALE requires O(d log d) queries for a constant-factor approximation and Ω(d log d + d/ε) queries for a relative error approximation with high probability. Experimental results on regression benchmarks validate the effectiveness of the proposed approach.", "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 greatly appreciate your constructive suggestions. Below, we address each of your comments in detail.\n\n> Q1- *Claims And Evidence*: Independent communication complexity and privacy analysis of FALE\n\nAs Reviewer 2DKU's suggestion, we have included a dedicated analysis of FALE's communication and storage complexity aspects. Specifically, in our proposed FALE method, each selected data instance is associated with two identifiers, i.e., the index of the data and client. Therefore, the communication complexity and storage overhead of transmitting leverage scores and selected data indexes are **$\\mathcal{O}(n)$ and $\\mathcal{O}(n_s)$**, respectively. Thus, the overhead in communication from maintaining and transmitting the metadata is **minimal and unlikely to be a practical bottleneck**, especially compared to transmission of the model gradient, which is usually much larger. Note that FALE conducts one-pass data selection, so the server **do not necessarily store the mappings** between sample indices and client identities.\n\nRegarding privacy, please refer to our detailed response to Reviewer JwJU in Q1.\n\n\n> Q2-*Claims And Evidence*: Explicit mechanism to address heterogeneity in FL settings\n\nWe wish to clarify that FALE inherently addresses data heterogeneity by leveraging FedSVD, which securely computes global singular vectors on distributed and non-i.i.d. client data. Consequently, **the obtained global leverage scores accurately reflect global data structures** rather than being biased towards any specific local data distribution. This global perspective naturally addresses the challenge of non-i.i.d. and heterogeneous client data distributions.\n\n> Q3-*Methods And Evaluation Criteria*: Lack of ablation studies and  analyses of selected instances\n\nWe wish to explain that the paper includes the **variant FALE-local, which can be regarded as one of the ablations to FALE**. Since it is a degenerated version of the proposed FALE method that only performs global data selection. To further enhance clarity, in the revision, we have explicitly added more detailed ablation studies and analyses exploring individual components. We have also included visual and statistical analyses of the selected data instances to better illustrate their global informativeness.\n\n> Q4-*Theoretical Claims*: Validity of Theorem 4.1 in the non-i.i.d. distributed setting\n\nWe wish to clarify that Theorem 4.1 remains valid under FL settings with non-i.i.d. data distributions. Theorem 4.1 only depends on the leverage score sampling derived from the globally computed singular vectors via FedSVD. Since FedSVD has been rigorously validated to accurately compute global singular vectors securely, the leverage scores obtained exactly match those in a centralized setting. We refer to our response to Q2 of reviewer JwJU for more details and an updated version of Theorem 4.1.\n\n> Q5-*Other Strengths And Weaknesses*: Contributions on specific challenges of FAL\n\nWe respectfully emphasize that, to best of our knowledge, FALE is the first FAL method to propose global data selection explicitly, departing from local query strategies common in prior works. Additionally, we provide a theoretical analysis of query complexity to provide formal guarantee, which is largely absent in existing literature of FAL. **These innovations address both heterogeneity and communication challenges** and have been highlighted in the revised manuscript.\n\n> Q6-*Questions For Authors*: Terminology clarification\n\nIn the revised manuscript, we have given the clear definitions.\n**One-pass** refers to conducting the active querying only once, without multiple iterative rounds.\n**Query budget** indicates the total number of allowed instances selected for labeling in active learning.\n**Query complexity** denotes theoretical analyses quantifying how many queried instances are necessary to achieve certain performance guarantees with high probability.\n\n> Q7-*Questions*: Experimental setup clarification and concern of distribution shift}\n\nWe clarify explicitly that there is a budget of labeling 50 data points (5 data querying for each client) per round for the methods that select data iteratively. FALE conducts one-pass selection in the server side. **Note that the server only handles the data selection part**, labeling always occurs locally on the client side. \n\nFor your 2nd concern, active selection naturally tends to focus on the most informative instances, potentially introducing bias. However, empirical studies indicate that such a bias does not necessarily degrade performance [1].\n\nRegarding scalability, computational and communication costs, please refer to our detailed responses to Reviewer nFHH in Q4 and Reviewer gkkn in Q4.\n\n\n### References\n\n[1] Lowell, D., Lipton, Z. C., and Wallace, B. C. (2019). ”Practical Obstacles to Deploying Active Learning.” EMNLP-IJCNLP.", "claims_and_evidence": "The main contribution of this paper is a privacy-preserving data selection algorithm for regression tasks with non-i.i.d. client data in federated learning. The authors claim that the proposed method operates without requiring an initial labeled set and can select instances in a single pass, thereby reducing communication costs. Additionally, they provide a theoretical analysis of the query complexity of their approach.\n\nA key strength of the proposed method is its inherent support for unsupervised learning, as it leverages FedSVD decomposition to extract cross-client query information. However, several concerns arise regarding the claims:\n\n1. Efficiency and Privacy: The paper mainly references analysis of FedSVD to support its efficiency and privacy claims but does not provide an independent communication complexity or privacy analysis for FALE itself. This omission is significant because FALE introduces additional challenges beyond standard SVD tasks. A key concern is metadata tracking, where the server must maintain mappings between sample indices and client identities to return selection results. This process may introduce extra communication and storage overhead, which is not explicitly analyzed. Additionally, it poses potential privacy risks, as it could expose certain distributional properties of local datasets, thereby compromising privacy.\n\n2. Handling of Heterogeneous Client Data: The paper claims to address federated learning with heterogeneous client data; however, its approach primarily relies on FedSVD, where masked client data is aggregated on the server into a matrix representation, effectively forming a pooled dataset. There is no explicit mechanism or dedicated analysis in the paper that directly addresses the challenges of heterogeneity in federated settings. Without specific design considerations and analysis for non-i.i.d. data, the claim that the proposed method effectively handles heterogeneous client distributions remains unsubstantiated.\n\nOverall, while the proposed method offers an interesting approach to privacy-preserving data selection, the lack of independent analyses on communication efficiency, privacy risks, and heterogeneous data handling weakens the validity of its claims. A more thorough evaluation of these aspects would strengthen the impact and reliability of the work.", "methods_and_evaluation_criteria": "The methods and evaluation criteria presented in the paper are partially reasonable but require further refinement and justification.\n\nFederated Active Learning and Data Heterogeneity Considerations: The approach of extracting cross-client information using FedSVD followed by leverage scoring is a reasonable choice. However, the paper does not sufficiently address the specific challenges of FAL and data heterogeneity (as discussed in the previous section). A more thorough analysis of how the method adapts to varying client distributions and the selection dynamics in an active learning scenario would strengthen its contributions.\n\nEmpirical Evaluation Scope: The experimental evaluation primarily focuses on regression performance using Mean Squared Error (MSE) as the evaluation metric. However, the paper lacks ablation studies to analyze the contribution of each algorithmic component and case studies to examine the characteristics of the selected data instances. Without these, it remains unclear whether each step of the proposed method is essential and effective, and what types of data are preferentially selected. A more comprehensive evaluation, including component-wise validation and qualitative insights, would improve the reliability and interpretability of the results.\n\nOverall, while the proposed methodology is reasonable, a deeper investigation into federated active learning constraints and a more comprehensive empirical analysis are necessary to substantiate its claims and enhance its applicability.", "theoretical_claims": "The proof for Theorem 4.1 leverages FedSVD to transform distributed client data into a pooled matrix representation, applying several lemmas originally proposed for centralized matrix approximation. However, it is unclear whether these results remain valid in the non-i.i.d. and distributed setting of FL. In FL, client data distributions are typically non-i.i.d., unbalanced, and locally biased, which may violate the assumptions underlying these lemmas, many of which rely on random or structured sampling.", "experimental_designs_or_analyses": "The experimental design is reasonable but lacks soundness in several key aspects:\n\n1. Scalability to Complex Models: All experiments are conducted on a single-layer model and mainly low-dimensional feature spaces. It remains unclear whether the proposed method can scale effectively to deeper architectures or more complex models in real-world applications. Testing on more diverse model architectures would provide stronger validation.\n\n2. Federated Scalability: The experiments are limited to only 10 clients with a query budget of 5 instances per client. This small-scale setting does not reflect realistic federated learning scenarios.\n\n3. Computational and Communication Costs: The paper claims reduced cost due to FedSVD-based selection, but there are no experiments analyzing server-side computational overhead (SVD computation) or communication cost (data collection and transmission).", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: Federated Active Learning (FAL) is a timely and practical research topic, addressing key challenges in federated learning by reducing labeling costs. The application of leverage score sampling on unlabeled data is promising, as it provides a principled way to select informative instances while preserving privacy.\n\nWeaknesses: The paper lacks originality, as its core methodology and claims, particularly regarding privacy and communication efficiency, heavily rely on FedSVD without substantial novel extensions. While leveraging FedSVD for data selection is reasonable, the work does not introduce significant new contributions to the specific challenges of FAL, such as adaptive query strategies, uncertainty estimation, or handling of heterogeneous client data.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Could you clarify key terminology such as \"one-pass\" (one communication between client and server?), \"query budget\"(numbers of instance queried?), and \"query complexity\" to ensure a precise understanding of their definitions and implications in the context of your method?\n\nBased on the experiments, the query budget is set to 5 per client with 10 query rounds. Does this mean that the server alone handles the selection process, selecting and labeling 50 instances per client before returning them for training? Additionally, for trials with 15,000 queries, does the sampling algorithm converge in a way that leads to repeated selection of the same instances, potentially collapsing diversity in the selected samples?", "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": "1nUrJ8kydl", "reviewer": "Reviewer_gkkn", "summary": "This paper presents FALE (Federated Active data selection by LEverage score sampling), a novel Federated Active Learning (FAL) method for regression tasks with non - i.i.d. client data. FALE leverages FedSVD to gather global data information without exposing individual client data. For global model learning, it trains a global model on the server using masked feature matrices and label vectors of the queried data, which are then unmasked on the client side. Theoretical results are provided to validate the superiority of FALE. Experiments on 9 benchmark datasets demonstrate that FALE significantly outperforms existing SOTA methods in terms of mean squared error, validating its effectiveness.", "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": "Thank you very much for your time in reviewing our paper. Below we respectfully address your concerns point-by-point.\n\n> Q1-*Theoretical Claims*: The relationship and effectiveness of Thrm. 4.1 for FALE\n\nWe have improved and rewritten Thrm 4.1 to explicitly clarify its direct connection and effectiveness to FALE algorithm. Specifically, Thrm 4.1 provides a formal guarantee that the output of Algorithm 1 achieves an approximation to the optimal solution within a constant factor or relative error. This can directly verify the effectiveness of FALE, as it quantifies how close the performance of FALE is compared to the best achievable performance. Also, please refer to our response to Reviewer JwJU in Q2 for details.\n\nRegarding why these results apply in the FL context, please refer to our detailed response to Reviewer 2DKU in Q4.\n\n> Q2-*Theoretical Claims*: Meaningfulness of Eq. (4)\n\nConstant-factor approximations are standard and meaningful theoretical results widely recognized in learning theory literature (see also [1-2]). **The key significance is that the factor $\\alpha$ is a fixed, bounded, and problem-independent constant rather than arbitrarily large.** This theoretical guarantee confirms that FALE’s selected samples provide sufficient global information. We have also explicitly highlighted and clarified this point in our revised manuscript. \n\n>Q3- *Other Strengths And Weaknesses*: Limited novelty\n\nWe wish to clarify our contributions explicitly. To the best of our knowledge, **our proposed FALE method is the first federated active learning approach with a global data selection strategy, substantially different from existing local-selection methods.** Moreover, our theoretical analysis on query complexity represents an important contribution to FAL, demonstrating the theoretical advantages of FALE. We sincerely appreciate your feedback; in the revision, we have explicitly emphasized these novel contributions.\n\n> Q4-*Other Strengths And Weaknesses*: Clarification on computational overhead\n\nWe have added the following detailed analysis in the revised paper: \" **The client-side masking computation scales quadratically with the labeled samples per client ($n^L_i$) and linearly with data dimension $d$, both of which are typically modest in size.** The server-side aggregation step involves solving a regression problem, which modern computing systems can handle efficiently. Therefore, the computational overhead introduced by masking and aggregation steps is not significant, making our method practical and scalable for realistic federated scenarios.\"\n\n> Q5-*Other Comments Or Suggestions*: Presentation and readability issues\n\nWe have carefully revised all figures and formulations (especially Fig. 1 and Fig. 2) in the paper. Specifically, text will be repositioned to avoid being cut by figure borders, repetitive labels will be simplified, and missing punctuation will be corrected. We appreciate your suggestions for improving clarity.\n\n>Q6-*Questions For Authors*: Influence of labeled set size on FALE performance\n\nWe have conducted a new experiment to explore the effect of the size of the labeled dataset to the performance of FALE. The results with different initial labeled data rates (0.01, 0.03, 0.05, 0.1) of the proposed methods, after querying 1000 data points, are shown as below.\n\n| Dataset | 0.01 FALE | 0.01 FALE-local | 0.03 FALE | 0.03 FALE-local | 0.05 FALE | 0.05 FALE-local | 0.1 FALE | 0.1 FALE-local |\n|-|-|-|-|-|-|-|-|-|\n| ct   | 0.15±0.00 | 0.18±0.02 | 0.15±0.00 | 0.25±0.09 | 0.15±0.00 | 0.21±0.06 | 0.14±0.00 | 0.20±0.05 |\n| diamonds | 0.11±0.01 | 0.55±0.06 | 0.15±0.01 | 0.55±0.04 | 0.15±0.01 | 0.48±0.03 | 0.13±0.00 | 0.42±0.03 |\n| kegg_undir_uci | 0.71±0.01 | 0.74±0.01 | 0.72±0.01 | 0.73±0.01 | 0.72±0.01 | 0.73±0.01 | 0.72±0.00 | 0.72±0.01 |\n| mlr_knn_rng  | 0.51±0.01 | 0.61±0.03 | 0.51±0.00 | 0.58±0.03 | 0.50±0.00 | 0.57±0.03 | 0.50±0.00 | 0.55±0.03 |\n| online_video | 0.49±0.03 | 0.48±0.01 | 0.48±0.01 | 0.48±0.00 | 0.48±0.02 | 0.48±0.00 | 0.48±0.02 | 0.48±0.00 |\n| protein | 0.76±0.00 | 0.85±0.01 | 0.77±0.01 | 0.84±0.01 | 0.77±0.01 | 0.83±0.01 |0.77±0.00 | 0.82±0.01 |\n| sarcos | 0.16±0.01 | 0.56±0.03 | 0.18±0.01 | 0.55±0.03 | 0.17±0.01 | 0.54±0.03 |0.17±0.01 | 0.51±0.03 |\n| stock | 0.57±0.00 | 0.59±0.02 | 0.56±0.00 | 0.59±0.02 | 0.56±0.00 | 0.57±0.01 |0.56±0.00 | 0.55±0.01 |\n| wecs| 0.58±0.01 | 0.66±0.05 | 0.57±0.01 | 0.66±0.03 | 0.58±0.01 | 0.65±0.03 |0.57±0.01 | 0.61±0.03 |\n\nAs shown, our proposed method is minimally affected by the size of the initially labeled dataset, demonstrating its robustness across a variety of applications.\n\n### References\n\n[1] Woodruff, David P. \"Sketching as a tool for numerical linear algebra.\" Found. and Trends in Theo. Comp. Sci. 10.1–2 (2014): 1-157.\n\n[2] Mahoney, Michael W. \"Randomized algorithms for matrices and data.\" Found. and Trends in ML 3.2 (2011): 123-224.", "claims_and_evidence": "The theoretical result is not convincing. Refer to **Theoretical Claims**.\nThe experiments are extensive.", "methods_and_evaluation_criteria": "Please refer to **Experimental Designs Or Analyses**.", "theoretical_claims": "* The authors provide theoretical guarantees, demonstrating both constant factor approximation and relative error approximation. However, Theorem 4.1 does not seem to have any relation with the proposed FALE. How can its result demonstrate the effectiveness of FALE?\n* Eq.4 seems to be meaningless. Eq.4 holds as long as $\\alpha$ is large enough.\n* The correctness of any proofs for theoretical claims is not checked.", "experimental_designs_or_analyses": "The authors include enough baseline methods and consider sufficient benchmark datasets in experiments. The proposed FALE method outperforms other baselines on benchmark datasets.", "relation_to_broader_scientific_literature": "The key contributions are not related to the broader scientific literature.", "essential_references_not_discussed": "There are no obvious essential references that were not discussed based on the information provided.", "other_strengths_and_weaknesses": "* The problem setting of federated active regression is under-explored and meaningful. Mitigating issues like client drift and imbalance that are common in federated scenarios.\n* The one-pass selection mechanism and privacy-preserving model training are highly relevant for real-world federated settings.\n* Limited Novelty. The proposed method is a simple application of FedSVD in the FAL field.\n* Additional clarification on the computational overhead of the masking and aggregation steps would further strengthen the practical insights.", "other_comments_or_suggestions": "*　Many text in Fig 1 are cut by frames, please fix them.\n*　Line 111, the formulation lacks an ending period.\n*　Fig 2, the same label repeats 9 times, please simplify it.", "questions_for_authors": "The authors claim that the proposed method does not require an initially labeled dataset. However, the experiments use a labeled dataset to initialize the model. What would happen if there is no available label? Also, how does the size of the labeled set influence the performance of the proposed method?", "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": "Hpa2JzDHXP", "reviewer": "Reviewer_nFHH", "summary": "This paper proposes FALE algorithm to select informative data points for non-i.i.d. federated regression task. The query strategy performs global data selection using leverage score sampling, where a FedSVD technique is employed to obtain the leverage scores of all data points in federated learning. Furthermore, a global model learning scheme is proposed to fully exploit the labeled data without privacy leakage. Both theoretical and empirical studies are conducted to validate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 5, "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": "Thank you very much for your thoughtful review of our paper. Below we respectfully address each of your comments point-by-point.\n\n> Q1-*Other Strengths And Weaknesses*: Concerns regarding potential data leakage and increased communication overhead\n\nRegarding data leakage concern, please see our response to reviewer JwJU for more details.\nRegarding communication overhead, we clarify that the method involves minimal overhead due to the one-pass querying strategy and efficient masking mechanisms. Specifically, the communication cost scales linearly with the number of clients and selected samples, and thus remains practical for large-scale federated scenarios.\n\n> Q2-*Other Strengths And Weaknesses*: Lack of thorough review of related homomorphic encryption works\n\nAs Reviewer nFHH's suggestion, we have explicitly included and reviewed related works employing homomorphic encryption in the revised manuscript. \n\n> Q3-*Other Comments Or Suggestions*: Some inconsistent symbols\n\nWe have carefully proofread the whole paper and eliminated all the grammatical, spelling, and punctuation errors. This revision enhances the readability and ensures the information is accessible without compromising the depth and accuracy of the content. \n\n> Q4-*Questions For Authors*: Clarification on how the communication overhead of FALE scales with increasing numbers of clients and larger datasets\n\nWe wish to clarify further and provide detailed insights regarding communication overhead scalability explicitly as follow:\nThe communication overhead of FALE involves three main components: FedSVD, data selection transmission, global model training.\n\n1. FedSVD has been rigorously validated as highly scalable to large datasets, incurring communication costs proportional to data dimensionality rather than the total data size. Thus, this overhead remains manageable even for extremely large-scale datasets.\n2. The cost of transmission the leverage scores and the indices of the selected data scales linearly with the total number of data instances. Each client transmits only a vector. Thus, even with an increasing number of clients or larger datasets, the incremental communication overhead remains relatively modest.\n3. The global model training phase has a similar communication complexity with FedSVD, which shares the same scalablity to large scale datasets.\n\nTherefore, explicitly considering these three components together, **FALE scales efficiently and practically with increasing numbers of clients and larger datasets**. In the revised manuscript, we have explicitly provided quantitative analyses illustrating communication overhead of in various scenarios, thus thoroughly demonstrating its scalability and practical applicability in realistic FL settings.", "claims_and_evidence": "The paper claims that FALE enables efficient and effective cross-client data selection in federated regression. This claim is well supported by detailed analyses and a range of experiments.", "methods_and_evaluation_criteria": "The authors evaluate the approach using 11 benchmark regression datasets. The empirical FL settings align well with existing practices in the literature. The evaluation criteria include the mean MSE loss among different random data split and the learning curve of AL approaches. They are correct and appropriate.", "theoretical_claims": "Yes, the proofs follow the techniques in leverage score sampling. They appear to be rigorous and correct.", "experimental_designs_or_analyses": "I have checked the details of experimental designs, the setup is both sound and appropriate.", "relation_to_broader_scientific_literature": "The contributions of this paper relate to the active regression problem with $\\ell_p$ loss functions.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Strengths:\n(1) The proposed method implements global active data selection, mitigating the issue of knowledge overlap among clients in federated learning. The data selection is conducted in a one-pass way, which is novel and well-motivated for FAL scenarios.\n(2) A global model learning paradigm is introduced and analyzed. It exploits the encrypted labeled data in the server and learns a model that is equivalent to the centralized setting, making it suitable for privacy-preserving learning settings.\n(3) The effectiveness of the proposed method is validated through comprehensive theoretical and empirical studies. The evaluation is robust. The experiments incorporate recent state-of-the-art methods and a diverse set of benchmark datasets, and the results are statistically significant.\n\nWeaknesses:\n(1) The method requires clients to encrypt and upload their local data, which might raise concerns regarding potential data leakage and increased communication overhead. \n(2) The paper employs an encryption technique related to homomorphic encryption; however, it would benefit from a more thorough review of related work in this area.\n(3) Experimental validation is limited to a federated learning scenario involving 10 clients. Further studies on a larger number of clients to better assess scalability.", "other_comments_or_suggestions": "There are some inconsistent symbols in the paper, e.g., in Algorithm 1. The authors should revise the paper again carefully.", "questions_for_authors": "How does the communication overhead of FALE scale with an increasing number of clients and larger datasets?", "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": "aa6IBp6q5q", "reviewer": "Reviewer_JwJU", "summary": "This paper considers active linear regression in the federated learning setting. It adapts the leverage score sampling to the federated learning setting for active learning. To make the method work in federated learning, it requires two components, data selection which estimates the leverage scores, and model learning which solves the linear regression problem once the data is selected and labels are obtained. For both of these two components, it applies the idea of FedSVD where it assumes that there is a trusted authority that generates random orthogonal matrices P and Q; each client to send their masked local data $PX_iQ$ to the server; the server does global computation, and send back the results to each clients. \n\nIt claims that the method is privacy preserving. It provides a theoretical analysis showing that the method achieves a similar label complexity as in the centralized learning setting. It also provides some empirical evaluation.", "questions": "", "limitations": "", "rating": 1, "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": "Thank you for your careful review of our manuscript. Below we respectfully and explicitly address your main concerns point-by-point.\n\n> Q1-*Claims And Evidence*: Concerns about privacy preservation and lack of a precise theoretical characterization of what kind of \"privacy\" is preserved\n\nThank you for raising this concern. We acknowledge that FALE utilizes masking techniques based on the FedSVD algorithm, which leads to partial leakage of structural information, such as the global distributional properties could be indirectly inferred from leverage scores, although direct identification of local client data remains infeasible. However, such limited structural leakage is often accepted in practical FL scenarios, please see [1-4]. Following the established FedSVD, **our method maintains the same level of data confidentiality against direct reconstruction**.\n\nTo clarify this issue further, we have explicitly stated these limitations and the level of privacy protection\nprovided in the revised manuscript. Specifically, **FALE adopts a one-pass querying mechanism and avoids persistent metadata tracking**. Once selected data indices are returned to clients, these mappings are discarded, reducing the risk of leakage. Furthermore, **FedSVD's privacy-preserving masking mechanism ensures that raw client data remains inaccessible**. Although the global distributional properties might be indirectly inferred from leverage scores, we wish to point that this certain degree of privacy risk is **generally acceptable** in the FL literature (see [1-4]). Hope for your understanding! We will folow and focus on more related privacy works in the future.\n\n> Q2-*Theoretical Claims*: Concerns regarding correctness and validity of Theorem 4.1, specifically the proof that locally computed leverage scores match the global leverage scores\n\nWe clarify that the validity of Theorem 4.1 relies fundamentally on the correctness of leverage scores computed via FedSVD. FedSVD has been rigorously proven to securely compute exact global singular vectors from distributed, non-i.i.d. data without exposing raw client data. **Since leverage scores are directly computed from these securely aggregated global singular vectors, leverage scores computed locally by each client indeed exactly match the global leverage scores computed centrally**. Consequently, Theorem 4.1 remains rigorously correct in our federated setting.\n\nIn the revised manuscript, we have rewritten Theorem 4.1 as follows.\n\n**Theorem 4.1**  *Consider FL with non-i.i.d. data. Let $k$ be the number of clients, $\\epsilon \\in (0, 1]$ be an error parameter, $X_i \\in \\mathbb{R}^{n_i \\times d}$ be the corresponding data matrices, and $\\mathbf{y}_i \\in \\mathbb{R}^{n_i}$ be the initially unknown target vector. Denote by $X = [X_1^\\top, \\ldots, X_k^\\top]^\\top$, $\\mathbf{y} = [\\mathbf{y}_1^\\top, \\dots, \\mathbf{y}_k^\\top]$, and $\\mathbf{\\theta}^\\ast = \\arg \\min _ {\\mathbf{\\theta}} \\| X \\mathbf{\\theta} - \\mathbf{y} \\|_2^2$.  **Algorithm 1 computes the global leverage scores for the data in each client**. Moreover, if Algorithm 1 queries $\\mathcal{O}(d \\log d)$ data points and outputs the model $\\mathbf{\\theta}^g$, then with probability at least 0.99 that:*\n\n\n$\\| X \\mathbf{\\theta}^g - \\mathbf{y} \\|_2^2 \\leq \\alpha \\| X \\mathbf{\\theta}^\\ast - \\mathbf{y} \\|_2^2,$\n\n\n*with some constant $\\alpha$. In addition, if it queries $\\Omega(d \\log d + d / \\epsilon)$ data points and outputs $\\mathbf{\\theta}^g$, then with probability at least $1/3$ that:*\n\n$\\| X \\mathbf{\\theta}^g - \\mathbf{y} \\|_2^2 \\leq (1 + \\epsilon) \\| X \\mathbf{\\theta}^\\ast - \\mathbf{y} \\|_2^2$.\n\n\n\nFinally, we would like to emphasize that FALE, to the best of our knowledge, introduces the first FAL approach with a global data selection strategy, **substantially different from existing local-selection methods and is more applicable to the practical heterogeneous FL settings**. Moreover, our theoretical analysis on query complexity represents an important and novel contribution in the FAL literature. \n\n### References\n\n[1] Rothchild, Daniel, et al. ”Fetchsgd: Communication-efficient federated learning with sketching.” International Conference on Machine Learning. PMLR, 2020. \n\n[2] Gu, Hang, et al. ”Fedaux: An efficient framework for hybrid federated learning.” ICC 2022-IEEE International Conference on Communications. IEEE, 2022. \n\n[3] Li, Chengxi, Gang Li, and Pramod K. Varshney. ”Decentralized federated learning via mutual knowledge transfer.” IEEE Internet of Things Journal 9.2 (2021): 1136-1147. \n\n[4] Chai, D., Wang, L., Zhang, J., Yang, L., Cai, S., Chen, K., and Yang, Q. Practical lossless federated singular vector decomposition over billion-scale data. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 46–55, 2022.", "claims_and_evidence": "One of my major concerns is that I'm not convinced that the proposed method is privacy preserving. The only support for it seems to be based on the idea that \"there are infinitely many possible $\\bar{X}$ can be masked into X' ($PX_iQ$)\" (line 182, left column), but this only guarantees that one cannot recover $X_i$ from $PX_iQ$, but recovering it up to some linear transformation is already leaking a significant amount of information in my opinion. A more precise theoretical characterization of what kind of \"privacy\" is preserved would be helpful.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I'm not very convinced that the main theoretical contribution, Theorem 4.1 is correct. It looks to me that in the proposed method, the leverage score $\\tau_i$ is computed locally. Can you provide a formal proof showing that the locally computed $\\tau_i$ is the same or close to the global leverage score defined as in equation (1)?", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": {}}]

Author rebuttal:

Meta-review: The overall quality of the paper is excellent. One major dispute is whether the proposed method can provide the desired level of privacy-preservation. In general, the federated learning framework can protect privacy in a trusted environment by embodying data locality mechanism. To provide privacy-preservaition guarantee in an untrusted envrionment, with privacy leakage and backdoor attack, a practical solution is to integrate a federated learning framework with a protection method from the cybersecurity domain.
Decision: Accept (poster)