Exploring Federated Optimization by Reducing Variance of Adaptive Unbiased Client Sampling

Thanks for the detailed comments and notification provided by the reviewer. We would like to respond to the weaknesses and questions to support our paper.

Weaknesses:

• "While there is nothing wrong with taking this approach, I wouldn't consider this a significant theoretical contribution and, therefore, I'd expect a thorough empirical evaluation." The main contribution of this paper stands that "we are the first work that extends the independent sampling procedure on adaptive client sampling in federated optimization." The previous theory of regret bounds and independent sampling are studied on the non-convex stochastic optimization for data sampling. Differently, we are exploring adaptive unbiased client sampling in federated learning, which is a very different manner. We provide concrete theory and experiments to support our points in the paper. Can we have further suggestions from the reviewer about "thorough empirical evaluation"? We sincerely appreciate detailed comments that improve our work.
• "The authors assume that all gradient norms are bounded. " In the federated optimization literature (most of the federated optimization papers we have cited), plenty of works follow the bounded gradient assumption, while maintaining its powerful performance in applications. Using this assumption is not supposed to be the weakness of our work. Besides, we involved the data heterogeneity in our analysis with the Assumption (11). Additionally, this paper mainly contributes an efficient and practical federated client sampler and proves its efficacy from theory and empirical study, instead of pursuing the state-of-art analysis in optimization.
• The experiments are very limited. Our experiment setting follows previous works on federated optimization and client sampling studies. We believe the main points of the paper are fully covered by experiments. It will be appreciated if the reviewer provides direct requirements of the further experiment study. We are also willing to conduct further experiments if suggested.
• Typos and issues. Thanks very much for your careful notification. We have modified all the minor issues and checked our paper carefully.

Questions:

• "In the proof of Theorem 8, why does the FTRL bound from Theorem 23 apply?" Please note that the term (B) in (41) has a similar form of FTRL objective in (34). Differently, we replace the true full feedback information with additional estimates according to sampled clients $S^t$ from $\tilde{p}^t$. As the additional estimates are unbiased as we discussed in Section 3.2, we can conduct the exact same analysis with Theorem 23 to prove the results by only replacing the $\ell_t(p)$ to $\tilde{\ell}_t(p)$. In conclusion, we can apply the FTRL bound from Theorem 23 in an expectation form.
• "In equation (41), the authors use unbiasedness of $\tilde{\ell}_t(p)$". We are analyzing an expected regret bound with partial feedback constraints. Therefore, it is applicable.
• "Objective (8) has unbounded gradients, why can we apply the FTRL theory?" Please note that objective (8) has a closed-form solution, which is analogous to Lemma 3 and the proof is detailed in Lemma 18. Therefore, we don't compute the gradients of objective (8). As we stated on page 6, the regularizer $\gamma$ of FTRL ensures that the distribution does not change too much and prevents assigning a vanishing probability to any clients.
• "Why the probabilities given in equation (9) add up to 1?" Please note that we restricted that "To be consistent, the sampling probability $p$ always satisfies the constraint $p_i^t > 0, \sum_{i=1}^N p_i^t = K, \forall t\in[T]$ in this paper" in Definition 1. Therefore, we always have that $\sum_{i=1}^N \tilde{p}_i^t=(1-\theta) \sum_{i=1}^N p_i^t+\theta \frac{K}{N} \cdot N = K$, which consistent with our definition.

In summary, we hope our response could better clarify our work. We are expecting the feedback from reviewers. Please feel free to comment us if further clarifications are required.

Thanks very much for your detailed comments! The following are our responses to the comments accordingly:

Weakneass in contributions:

• Clarify theoretical contribution. First of all, we would like to state that the main contribution of this paper stands that "we are the first work that extends the independent sampling procedure on adaptive client sampling in federated optimization." We mainly rely on the theoretical works of VRB and independent sampling proposed by Samuel Horváth and Peter Richtárik are studied on the non-convex stochastic optimization for data sampling. Differently, we are exploring adaptive unbiased client sampling in federated learning, which is a very different manner. In this paper, we first extend their theoretical results in federated optimization and present a new unbiased client sampling technique in federated learning.
• Comparison with other random sampling techniques. Theoretically, the benefits of independent sampling have been given in Lemma 2, where we conclude that independent sampling could minimize the variance better than random sampling. Besides, we prove the convergence benefits of the K-Vib sampler (using independent sampling) are better than other adaptive samplers MABS, Vrb, and Avare (using random sampling) in Theorem 13 and remark paragraph. Empirically, we conduct experiments in 4 settings to demonstrate the performance of the K-Vib sampler. It would be appreciated if the reviewer pointed out other similar papers with random sampling that we may missed.
• Benefits of independent sampling. The experiments show the superior performance of K-Vib over baselines. Besides, the K-Vib sampler partially inherits the theoretical design of Vrb, while innovatively replacing the sampling procedure with independent sampling. We believe the comparison between K-Vib and Vrb in Figure 4,5 could also indicate the conclusion in Lemma 2.

For a brief summary, our work contributes greatly to the understanding of adaptive unbiased client sampling topics in the federated learning community. It supports the design of an efficient client sampler.

• The convergence analysis is flawed. We humbly disagree with a few points in the comments. We have double-checked our analysis and are sure that the analysis has been fixed accurately. We split our response by points below:

  1. " In equation (43), the expectation is taken conditioning on the sigma algebra until x^t". "There should be only one expectation in the third term of the last line in page 25." In the last line of Equation (43), page 25, two expectation means different in $\mathbb{E}\left[\| \nabla f(x^t) - \mathbb{E}\left[d^t\right] \|^2\right]$. The first expectation is taking over time $t$ (condition on $x^t$. The second expectation is taken over sampling $S^t$, which reminds readers that the global estimates are built on an unbiased client sampling procedure. In Equation (44), we have removed all randomness.

  2. "In equation (52), the expectation is also conditional on x^t, so it is ridiculous to see, in equation (52), the expectation disappears." We humbly highlight that the expectation has not disappeared, but is absorbed by sampling quality function $Q(S^t)$ as we defined in Equation (45) or (11). To reach that, we put a lot of effort into our analysis to remove randomness from Equation (44) to (49) and Equation (51) with mild assumptions. In this way, we gather all randomness in the sampling quality function $Q(S^t)$ in order to theoretically compare with other adaptive baselines in Theorem 13.

  3. "The right step here is to take full expectation on both sides of (53) first, which removes all randomness, and then take summation over T. Only in this way, can you sum up equations for different T! " In the light of our response above, the Equation (53) can be summarised over time $T$. We also note that we missed an expectation symbol on LHS of (12) or (53), which has been corrected.

  4. "showing the minimum of the norm of the gradient lies a neighborhood around zero is a too weak result." The theoretical results stick to the standard analysis of non-convex optimization. Our goal is to provide a convergence comparison between FedAvg with unbiased adaptive samplers as we stated in the remark of Theorem 13, instead of pursuing the state-of-art rate in federated optimization. Besides, the theoretical results also match the rate of $\mathcal{O}(1/\sqrt{T})$ in previous non-convex federated optimization as we described in Theorem 13.

Given our response to the expectation problems, we are looking forward to your further comments on our theoretical analysis. We appreciate your comments helping us improve our work.

Thanks for your reply. Here is my further explanation.

First of all, $S^t$ is generated after obtaining $x^t$ means that we have $\mathbb{E}\left[d^t\right] = \sum_{i=1}^N \lambda_i g_i^t$ about sampling $p^t$ probability for the first equation of (44). To my opinion, the term $\mathbb{E}_{t} \left[\left\| \nabla f(x^t) - \mathbb{E} \left[d^t\right] \right\|^2\right] = \mathbb{E}_t \left[\left\| \nabla f(x^t) - d^t\right\|^2\right]$ can means the same. According to the comments, we have modified the term to the last one to be rigorous.

From (52) to (53), we should take full expectation on both (52) or (53) before summation as suggested. We have fixed the point in the new version.

For a brief summary, we are very thankful to the reviewer for pointing out the flaw in the analysis, which we have fixed accordingly. Most importantly, the main conclusion in Theorem 13 is not broken. Therefore, the main contribution of this paper still holds.

Given that, we sincerely request the reviewer reassess our paper according to our contribution. And, we would like to know if there are any other improvements that we can make to reach the top conference paper.

We really appreciate the supportive and construction comments! We would like to address the concerns and weaknesses of our paper with the following points.

Abstract:

• A line of 'free' adaptive client sampling: We define a federated client sampling technique as free if it is orthogonal to conventional federated learning protocol (e.g., fedavg) and doesn't require additional local computation and communication.
• Promising sampling probability: The "promising" means that the sampling probability utilized by the server could enhance federated optimization.
• Modification: "solves an online convex optimization (problem) respecting client sampling in federated optimization" -> "which solves an online convex optimization problem respecting federated client samplings".

We have modified our abstract with more precise expressions accordingly.

Introduction:

• Literature review: we have referred to the suggested works.
• Comparision with work: We refer to the contribution claim from the paper[Grudzień, M., Malinovsky, G., & Richtárik, P. (2023)] "We finally present a complete method for Federated Learning that incorporates all necessary ingredients: Local Training, Compression, and Partial Participation." to clarify our differences. The benefits of the paper are obtained from the novel incorporation of different techniques. In contrast, we assume the clients have no additional computation for other techniques and we focus on the sampling techniques and global estimates for model updating while maintaining the largest compatibility to secure aggregation and re-weighting algorithms. Additionally, our sampling technique could also work with communication compression algorithms, such as quantization and sparsification.
• Pseudocode: we have modified the pseudocode accordingly.

Prelinimaries:

• Local drift: we have modified the term for clarity.
• Lipschitz gradient: this is a writing fault. We mixed up the Assumptions 4 and 9 in our draft. We have modified assumption 4 to "bounded gradients".
• Local convergence: this assumption supports us in the analysis of our sampling method in a successful optimization procedure. It indicates that our samplers work in a converging federated learning procedure that with proper hyper-parameters of learning rates, batch size, and local steps settled. Therefore, we assume the norm of local updates decays over communication rounds in federated learning.
• Bounded gradient: in practical cases, companies deploying federated learning algorithms will incorporate the optimization algorithm with privacy-preserving techniques (we refer to the URL below). As a result, gradient clipping is an optional trick for our method in both practice and theory. URL: https://machinelearning.apple.com/research/differential-secrecy. Besides, since the bounded gradient is widely used in the cited federated optimization literature, we hope our bounded gradient be accepted. We are not contributing a new optimization analysis but an efficient client sampler in this paper.
• Smoothness and global variance: we will modify our analysis to a more general version with suggested assumptions. Besides, we want to clarify that our assumption partially inherits from widely accepted work in federated optimization[1], and our analysis is to prove the present sampler is effecant in federated learning.

[1]Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecný, Sanjiv Kumar, Hugh Brendan McMahan: Adaptive Federated Optimization. ICLR 2021.

Experiements:

• Figures: Thanks very much for the notification. We will revise the marker of our figures to make it clear.

Questions:

• Convex analysis: it is applicable to obtain the convergence guarantees for both strongly convex and general convex cases. We can replace Equation (43) with corresponding assumptions and extend the proof. We would like to note that our experiments on Synthetic datasets cover convex cases from a practical perspective.

In summary, we greatly appreciate the constructive comments to improve our work. We have modified some of the weak points and updated the PDF. For the overall analysis with different assumptions, we will work on and update it in the next version. Finally, please let us know if we addressed your concerns about our work. We are looking forward to your feedback and are delighted to answer any questions that may come up.