- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studied client sampling for federated learning. More specifically, this paper proposed an algorithm, called Intelligent Selection of Participants (ISP), to determine the number of clients to be sampled in each round. To do this, the paper formulates the optimization problem in Eq. 2 and argues that minimizing it yields the optimal number of clients to sample.
Critical strengths
- The formulation in Eq. 2 to determine the number of clients to be sampled looks novel.
- Eq. 2 can not be efficiently solved. Thus, this paper proposes an algorithm to approximately solve Eq. 2, which looks novel and interesting.
Critical weaknesses
- The problem formulation of Eq. 2 looks strange. Even in the non-distributed SGD, it is not guaranteed that . I understand that this paper considers the deterministic setting, while it would be a severe drawback when we apply the proposed method to neural network training.
- The convergence analysis seems insufficient. Specifically, there is no theorem that the proposed method converges to a stationary point. It is important to evaluate how many times we sample the clients in total until reaching the -accurate point. Otherwise, it is unclear if the proposed methods superior to the standard uniform sampling. Furthermore, the bounds in Theorems 4.4 and 4.5 depend on and $| \nabla f_i (x^\tau)| $, which makes them hard to interpret.
- Is the expression $f(x^\tau - \gamma g^\tau(C^n)) - f(x^\tau) $ in Line 8 of Algorithm 2 a typo? If not, computing appears to require communication with all clients in every round, which would significantly increase the communication cost and make the method highly communication-inefficient.
- Gradients are computed in line 4 of Algorithm 1 and again in line 5 of Algorithm 2. This seems inefficient from both communication and computational perspectives.
- The proposed methods only determine the number of clients to be sampled, but is it possible to determine which clients to be sampled as well?
Questions for authors
See the weakness section.
4 comments
Evaluation Overhead, Update Reuse, and Client Selection (Part 2/2)
We continue with the reviewer's third, fourth, and fifth concerns.
3. Objective evaluation and communication cost.
The expression in Algorithm 2 is not a typo: subtracting measures the loss change relative to the current model. The count is reconsidered only once every rounds (RQ2), and the baseline objective is evaluated once per adaptation and reused across candidate evaluations (Appendix A).
ISP targets the client-update communication bottleneck through the uplink cost in Definition C.1, following Konečný et al., Federated Learning: Strategies for Improving Communication Efficiency. Objective evaluation requires client-side inference and returns scalar losses, whose payload is negligible relative to a model update. As discussed in RQ3, when public data provide a server-side surrogate , as in the ECG experiment, candidate evaluation requires no client communication.
These evaluation steps are part of the overall procedure assessed in our experiments. The reported update counts include intermediate communications, with savings across client selectors (Table 2), compression strategies (Table 18), and aggregation methods (Table 10). Tables 2 and 10 also report reductions in overall training time, accounting for the computational cost of the procedure.
When is unavailable, we empirically evaluate the GP add-on to reduce client-side objective queries and their associated model downlinks (Definition C.2). Candidate evaluation need not involve all clients: the add-on uses a proxy-coverage evaluator cohort (Appendix C.6, “Proxy-coverage evaluator cohort”) to estimate the baseline and candidate losses. In the experiments in Table 13, these cohorts contain only 5–6 of the 100 clients (5–6%) and approximate the full-client loss response.
Finally, the “Transferred updates” paragraph in Appendix D.2 accounts for both uplink and downlink traffic, including candidate evaluation. The added total-transfer comparisons cover optimization methods, client selection, and domains (Table 15), as well as different fixed client counts (Figure 5), demonstrating communication savings with evaluation traffic included.
4. Repeated gradient computations in Algorithms 1 and 2.
Algorithm 2 collects intermediate updates only when ; at other rounds, it retains the count and the selected clients compute their updates once. At adaptation rounds, Algorithms 1–2 separate auxiliary estimation and training for the theoretical formulation, whereas the implementation reuses the updates from for the server update and retains the selected count for subsequent regular rounds. We have made this reuse explicit in Algorithm 3, Appendix A, with caching specified in Algorithm 4. Intermediate communications remain included in the reported totals: Table 8 separately reports their contribution to the overall communication cost.
5. Selecting client identities as well as their number.
Yes. ISP is designed to work jointly with methods that determine which clients participate. ISP provides the count , and the client sampling strategy selects the identities from pool (Definition 3.1; Algorithms 1–3 and Appendix A). Section 5.2 and Table 2 demonstrate this composition with Uniform, Power-of-Choice, FedCor, FedCBS, DELTA, and Oort, showing that ISP's adaptive participation counts work with these statistical and system-aware client-selection mechanisms while preserving their selection rules.
We thank the reviewer again for the questions, which helped us clarify the convergence result, strengthen the matched-accuracy comparison, and make update reuse explicit in the practical pseudocode.
Thank you for your rebuttal and additional analyses. However, I believe my main concerns remain unresolved and would like to maintain my original score. In particular, the upper bound on total client participation is essentially a trivial worst-case bound. It does not establish a non-trivial communication-complexity advantage over fixed-count uniform sampling. While the additional experiments are useful, they do not resolve this theoretical limitation.
Thank you for your follow-up and for acknowledging the additional experiments.
We agree that the worst-case upper bound on total client participation does not, by itself, establish a non-trivial communication-complexity advantage over fixed-count uniform sampling. Our theoretical results establish convergence and characterize the behavior of the adaptive count-selection mechanism under the stated assumptions, rather than guaranteeing superior communication complexity in general.
We address the communication-efficiency question empirically, through comparisons at matched accuracy across different fixed participation budgets (Appendix D.7, Table 22 and Figure 9). At the target accuracy of 0.836, ISP requires 14,343 client-update exchanges, compared with 16,147 for the most communication-efficient fixed-count Uniform baseline reaching this target, corresponding to an 11.2% reduction. Importantly, these counts include the additional auxiliary communication introduced by ISP.
The experiments across different client-selection strategies (Table 2) further support the practical benefits of adaptive participation.
We acknowledge that these empirical improvements do not constitute a general theoretical guarantee. Nevertheless, we believe that the combination of convergence analysis and experimentally demonstrated communication savings provides meaningful support for the proposed approach.
We thank the reviewer again for the constructive discussion.
Expected Progress, Convergence, and Communication Efficiency (Part 1/2)
We thank the reviewer for the careful evaluation and for recognizing the novelty of the client-count formulation and its approximation. We address the five concerns below, following their order in the review. References refer to the revised manuscript; additions are highlighted in blue.
1. Expected progress and neural-network training.
Equation (2) seeks a negative expected loss change over the sampled client cohort. It does not require every realized update to decrease the loss. Thus, the possibility that an SGD step increases the loss does not contradict the formulation. The strict feasible set can also be empty; Section 3.1 explicitly discusses this case, and Algorithm 2 provides a fallback. Theorem 4.4 quantifies the estimation error, and Theorem 4.5 controls expected progress while the count is reused.
The practical search implements (2) through an estimated response, so it does not enforce monotone loss reduction at every round. We have added the paragraph “Full-population response evaluation” in Appendix G to illustrate this distinction: the estimated full-population loss change in (2) is nonnegative at the accepted count in 8 of 63 states (12.7%).
Stochastic client gradients and finite local mini-batches are addressed in Proposition F.15 and Corollary F.16. Empirically, the method is evaluated with neural networks, including ResNet, Swin-T, and LSTM, across image, ECG, and text tasks.
2. Stationarity, total client participation, and interpretation of the bounds.
Stationarity. Theorem F.8 in Appendix F.3 establishes
\leq \frac{f(x^0)-f_{\inf}}{\gamma c_\Delta T}.$$ For an iterate $x^R$ selected uniformly from these $T$ iterates, this gives $\mathbb{E}\\|\nabla f(x^R)\\|^2\leq\varepsilon^2$ after $$T_\varepsilon=\left\lceil\frac{f(x^0)-f_{\inf}}{\gamma c_\Delta\varepsilon^2}\right\rceil$$ rounds, i.e., $O(\varepsilon^{-2})$ for the theorem's fixed constants. For clarity, we have added an explicit reference to Theorem F.8 in the main theoretical analysis (Section 4). **Total participation.** Equation (49) counts the client-update exchanges of the reference algorithm, including auxiliary updates: $$C_{\rm updates}(T)=\sum_{t<T}m_{t+1}+\sum_{s\in\mathcal{T}_\Delta}b_{s+1/2},$$ where $\mathcal{T}_\Delta$ contains the adaptation rounds. In particular, $C_{\rm updates}(T_\varepsilon)\leq M(T_\varepsilon+\lceil T_\varepsilon/\Delta\rceil)$. The actual cost is given by the selected counts in the preceding sum, including the amortized auxiliary cost. To compare communication at the same predictive accuracy, we have extended **Appendix D.7, Table 22 and Figure 9**. At reference accuracy **0.836**, ISP uses **14,343** communications, versus **17,940 / 16,147 / 26,275 / 39,600 / 62,250** for fixed Uniform counts $m=15/20/25/40/50$. ISP therefore uses **11.2% fewer** communications than the most efficient fixed count reaching this accuracy; $m=5,10$ do not reach it. Intermediate updates are included. This comparison retains Uniform client selection and isolates the benefit of adapting its count. ISP also composes with other selectors (Section 5.2, Table 2). **Gradient norms.** These terms quantify how uncertainty in a sampled update translates into uncertainty in its loss response. In Theorem 4.4, the global and local gradient norms determine the sensitivity of the loss to changes in the update, while differences between client gradients measure heterogeneity. Greater heterogeneity increases the response-error bound; a larger auxiliary pool or more Monte Carlo samples reduces the corresponding error term. In Theorem 4.5, the gradient-dependent drift term also accounts for the model's evolution while the count is reused. The theory thus explains how auxiliary participation, estimation depth, and adaptation frequency control the reliability of the progress-based decision that ISP makes from evaluated candidate responses. We ablate these parameters, together with count-search resolution, in Appendix E.