Efficient Heterogeneity-Aware Federated Active Data Selection

Thank you for your careful review of our manuscript. Below we respectfully and explicitly address your main concerns point-by-point.

Q1-Claims And Evidence: Concerns about privacy preservation and lack of a precise theoretical characterization of what kind of "privacy" is preserved

Thank 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.

To clarify this issue further, we have explicitly stated these limitations and the level of privacy protection provided 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.

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

We 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.

In the revised manuscript, we have rewritten Theorem 4.1 as follows.

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:

$\| X \mathbf{\theta}^g - \mathbf{y} \|_2^2 \leq \alpha \| X \mathbf{\theta}^\ast - \mathbf{y} \|_2^2,$

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:

$\| X \mathbf{\theta}^g - \mathbf{y} \|_2^2 \leq (1 + \epsilon) \| X \mathbf{\theta}^\ast - \mathbf{y} \|_2^2$.

Finally, 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.

References

[1] Rothchild, Daniel, et al. ”Fetchsgd: Communication-efficient federated learning with sketching.” International Conference on Machine Learning. PMLR, 2020.

[2] Gu, Hang, et al. ”Fedaux: An efficient framework for hybrid federated learning.” ICC 2022-IEEE International Conference on Communications. IEEE, 2022.

[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.

[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.

Thank you very much for your thoughtful review of our paper. Below we respectfully address each of your comments point-by-point.

Q1-Other Strengths And Weaknesses: Concerns regarding potential data leakage and increased communication overhead

Regarding data leakage concern, please see our response to reviewer JwJU for more details. Regarding 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.

Q2-Other Strengths And Weaknesses: Lack of thorough review of related homomorphic encryption works

As Reviewer nFHH's suggestion, we have explicitly included and reviewed related works employing homomorphic encryption in the revised manuscript.

Q3-Other Comments Or Suggestions: Some inconsistent symbols

We 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.

Q4-Questions For Authors: Clarification on how the communication overhead of FALE scales with increasing numbers of clients and larger datasets

We wish to clarify further and provide detailed insights regarding communication overhead scalability explicitly as follow: The communication overhead of FALE involves three main components: FedSVD, data selection transmission, global model training.

1. 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.
2. 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.
3. The global model training phase has a similar communication complexity with FedSVD, which shares the same scalablity to large scale datasets.

Therefore, 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.

Thank you very much for your time in reviewing our paper. Below we respectfully address your concerns point-by-point.

Q1-Theoretical Claims: The relationship and effectiveness of Thrm. 4.1 for FALE

We 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.

Regarding why these results apply in the FL context, please refer to our detailed response to Reviewer 2DKU in Q4.

Q2-Theoretical Claims: Meaningfulness of Eq. (4)

Constant-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.

Q3- Other Strengths And Weaknesses: Limited novelty

We 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.

Q4-Other Strengths And Weaknesses: Clarification on computational overhead

We 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."

Q5-Other Comments Or Suggestions: Presentation and readability issues

We 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.

Q6-Questions For Authors: Influence of labeled set size on FALE performance

We 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.

As shown, our proposed method is minimally affected by the size of the initially labeled dataset, demonstrating its robustness across a variety of applications.

References

[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.

[2] Mahoney, Michael W. "Randomized algorithms for matrices and data." Found. and Trends in ML 3.2 (2011): 123-224.

We greatly appreciate your constructive suggestions. Below, we address each of your comments in detail.

Q1- Claims And Evidence: Independent communication complexity and privacy analysis of FALE

As 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.

Regarding privacy, please refer to our detailed response to Reviewer JwJU in Q1.

Q2-Claims And Evidence: Explicit mechanism to address heterogeneity in FL settings

We 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.

Q3-Methods And Evaluation Criteria: Lack of ablation studies and analyses of selected instances

We 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.

Q4-Theoretical Claims: Validity of Theorem 4.1 in the non-i.i.d. distributed setting

We 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.

Q5-Other Strengths And Weaknesses: Contributions on specific challenges of FAL

We 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.

Q6-Questions For Authors: Terminology clarification

In the revised manuscript, we have given the clear definitions. One-pass refers to conducting the active querying only once, without multiple iterative rounds. Query budget indicates the total number of allowed instances selected for labeling in active learning. Query complexity denotes theoretical analyses quantifying how many queried instances are necessary to achieve certain performance guarantees with high probability.

Q7-Questions: Experimental setup clarification and concern of distribution shift}

We 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.

For 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].

Regarding scalability, computational and communication costs, please refer to our detailed responses to Reviewer nFHH in Q4 and Reviewer gkkn in Q4.

References

[1] Lowell, D., Lipton, Z. C., and Wallace, B. C. (2019). ”Practical Obstacles to Deploying Active Learning.” EMNLP-IJCNLP.