acceptodds
Under review as a conference paper at ICLR 2027

On the Minimax Excess Risk and -Communication Algorithm for Federated Learning under Statistical Heterogeneity

Abstract

We study the minimax excess risk in federated learning (FL) with strongly convex and smooth loss functions under statistical heterogeneity. Previous work established a minimax excess risk lower bound that depends on the degree of statistical heterogeneity, but leaves large gaps with existing upper bounds in terms of problem-dependent parameters. In this work, we establish sharper lower bounds, which improve previous lower bound by in the stochastic gradient regime where is strong convexity constant, is applicable to the exact gradient regime, and match existing upper bounds, resolving an open problem raised by Chen2023Minimax. We also design a two-stage FL algorithm that is nearly optimal and only requires a communication rounds where is the condition number and is the number of clients, while previous algorithms require a communication rounds where is the local sample size. The lower bound analysis requires a non-trivial extension of the local Fano's method proposed for the minimax risk analysis of centralized learning to deal with FL. The algorithmic novelties include a multistage stochastic gradient and a two-stage federated training strategy coupled with a model initialization scheme. Our results fully characterize the condition under which FL is better than non-cooperative learning, showing its advantages and limitations. Our algorithm provides a simple and communication-efficient FL framework that holds independent interest.

Primary area:
learning theory
Keywords:
excess risk, federated learning, stochastic optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_WkvbOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when collaboration improves statistical accuracy in federated learning with heterogeneous client distributions. It measures average excess risk relative to each client’s own optimal model.

For M clients with T samples each, the paper proposes the stochastic minimax lower bound \Omega\left( \frac{\sigma^2}{\mu MT}+\min\left{\Delta,\frac{\sigma^2}{\mu T}\right}\right), where μ\mu is the strong-convexity parameter and Δ\Delta measures heterogeneity. Intuitively, collaboration reduces sampling noise, but differences between clients limit its benefit.

The paper also introduces TWS-Fed, in which clients first train independently, then average their models, and then perform federated optimization. Its communication cost is O(κlog⁡M)O(\kappa\log M), independent of T, with κ=β/μ\kappa=\beta/\mu. The resulting upper bound approaches the proposed statistical lower bound up to logarithmic and optimization-rate gaps. A separate exact-gradient lower bound supports a claim that independent optimization is sufficient in that regime.

Validation is theoretical, through lower-bound constructions and convergence proofs.

Critical strengths
  1. The paper addresses an important statistical question with an interpretable target rate.

The proposed bound distinguishes a shared estimation cost, σ2/(μMT)\sigma^2/(\mu MT), from the cost associated with client differences. It gives a concrete way to reason about when collaboration can help and when independent training is competitive. Establishing this tradeoff sharply would be a useful contribution.

  1. The algorithm offers a concrete mechanism for reducing communication.

The paper connects the local-training stage directly to the initialization term in the subsequent convergence analysis. This explains how communication can remain independent of T. The analysis under a variance-at-the-local-optimum assumption is also valuable, since it avoids requiring uniformly bounded stochastic-gradient variance throughout the parameter space.

Critical weaknesses
  1. The stochastic lower-bound proof does not consistently establish the claimed heterogeneity-dependent family.

Appendix C.1 samples group parameters v1,…,vSv_1,\ldots,v_S independently from the same packing set. This independence is subsequently used in the information-theoretic argument: observations from other groups do not provide information about a particular group’s parameter.

Case 1 later requires these parameters to be distinct, however, and invokes Lemma 11 to establish δ2/4≤Δ≤δ2\delta^2/4 \leq \Delta \leq \delta^2. Independent sampling does not guarantee distinctness. If all sampled parameters coincide, the equal-amplitude construction has zero heterogeneity. Conditioning on distinctness, in turn, introduces dependencies, so the earlier information reduction cannot be reused without justification.

Independently drawing group parameters and forcing all group parameters to differ are different statistical experiments, and the proof uses properties of both.

There is also a coverage issue: the construction requires S to divide M, while the intermediate regime uses 1<S<M. The theorem permits odd prime values of M, for which no such partition exists.

These issues might be repairable, for instance by formulating the minimax class using an upper heterogeneity budget and modifying the grouping argument. The present proof does not supply those repairs. Because this lower bound supports the paper’s optimality claims, the gap matters.

  1. The exact-gradient lower bound assumes a narrower algorithm class than the theorem states.

In Appendix C.2, Equation (35) asserts that every first-order algorithm generates iterates within the affine span of previously observed gradients. The subsequent proof uses this restriction to show that only a limited number of coordinates can become nonzero.

This is an additional algorithmic restriction. Access to first-order information alone does not force an algorithm to choose queries or outputs within that span. The proof further allows the output to be a function of previous iterates, but an arbitrary function need not preserve their coordinate support.

The result therefore needs either an explicitly restricted algorithm class, including an output restriction, or an argument covering general adaptive first-order methods.

The budgets also differ: the main statistical formulation budgets T samples, while this proof budgets optimization iterations. Seeing T examples and being allowed T gradient queries are different constraints. Without a precise oracle model, the deterministic result does not justify the broad claim that federated learning is unnecessary whenever exact gradients are available. Even a valid worst-case lower bound would establish worst-case rate optimality of independent training, rather than exclude benefits on particular instances.

Questions for authors
  1. Stochastic minimax class: Is the stochastic minimax class defined by Δ≤Δˉ\Delta\leq\bar\Delta, by a fixed heterogeneity value, or by a range of values? Please reconcile independent sampling of group parameters with the distinctness assumption used later, and explain how the intermediate regime covers prime M.
  2. Exact-gradient algorithm class: What is the algorithm class in the exact-gradient result? Does it impose the linear-span restriction in Equation (35) on both queries and outputs? What does T count in this result, and how does that model relate to the dataset-based formulation?
  3. Scope of parameter dependence: The stochastic construction sets μ=2/d\mu=2/d and has sample smoothness β=2\beta=2. Can the authors establish the claimed dependence for independently specified admissible μ,β,σ2\mu,\beta,\sigma^2, while tracking the effect of rescaling on all parameters? This matters for assessing the claimed improvement in strong-convexity dependence.
5 comments

We sincerely appreciate the Reviewer for considerable time and effort in reviewing our paper, especially for providing valuable feedback on the lower bound analyses.

We agree with the reviewer’s comments on the proof of the lower bounds. We have updated the manuscript following the Reviewer’s feedback, with revisions marked in red. We summarize the revisions as follows.

  • In the case of stochastic gradient regime, we have given a new and simpler proof that does not depend on specific values of v1,v2,…,vS\mathbf{v}_1, \mathbf{v}_2,\ldots,\mathbf{v}_S (such as our new proof does not force all group parameters to differ), does not require SS to divide MM, and accommodates independently specified admissible values of μ\mu, β\beta and σ\sigma.
  • In the case of exact gradient regime, we have explicitly specified the algorithmic class and imposed a corresponding restriction on their outputs in Theorem 1. This class encompasses many adaptive first-order algorithms, such as gradient descent, Nesterov’s accelerated gradient descent, Adam, FedAvg, SCAFFOLD, FedChain, FedCLUP, FedAdam, etc.
  • In the case of exact gradient regime, we have clarified that TT denotes the number of exact gradient queries on each client, rather than the size of its local training set (refer to Remark 1 in the main text).

[Question 3] Can the authors establish the claimed dependence for independently specified admissible μ\mu, β\beta, σ2\sigma^2, while tracking the effect of rescaling on all parameters?

[Answer] Yes, we can. Our new proof has changed the loss function to ∀w∈W,∀z=(x,y),f(w,z)=μ2(⟨w,x⟩−y)2,\forall \mathbf{w}\in\mathcal{W},\quad\forall \mathbf{z}=(\mathbf{x},y),\quad f(\mathbf{w},\mathbf{z})={\color{red}\frac{\mu}{2}} \left(\langle\mathbf{w},\mathbf{x}\rangle-y\right)^2, where we sample x\mathbf{x} uniformly and independently from (d⋅e1,d⋅e2,…,d⋅ed)(d\cdot\mathbf{e}_1,d\cdot\mathbf{e}_2,\ldots,d\cdot\mathbf{e}_d). The strong onvexity parameter is μ\mu. The smooth parameter is β=μd2\beta=\mu d^2. We can assign any admissible μ\mu. We can also assign any admissible β\beta by tuning dd. Besides, the variance σ2\sigma^2 is also independent of μ\mu and β\beta, and can be any admissible value.

[Question 1.1] Is the stochastic minimax class defined by Δ<Δˉ\Delta<\bar{\Delta}, by a fixed heterogeneity value, or by a range of values?

[Answer] The stochastic minimax class is defined by a range of values. Our results consists of three cases:

  • Δ=ω(σ2μMT)\Delta=\omega(\frac{\sigma^2}{\mu MT}) and Δ=O(σ2μT)\Delta=O(\frac{\sigma^2}{\mu T}). The lower bound on minimax risk is Ω(Δ)\Omega(\Delta).

  • Δ≥0\Delta\geq 0 and Δ=O(σ2μMT)\Delta=O(\frac{\sigma^2}{\mu MT}). The lower bound on minimax risk is Ω(σ2/(μMT))\Omega(\sigma^2/(\mu MT)).

  • Δ=ω(σ2μT)\Delta=\omega(\frac{\sigma^2}{\mu T}). The lower bound on minimax risk is Ω(σ2/(μT))\Omega(\sigma^2/(\mu T)).

[Question 1.2] Please reconcile independent sampling of group parameters with the distinctness assumption used later.

[Answer] Our new proof only requires that v1,v2,…,vS\mathbf{v}_1,\mathbf{v}_2, \ldots,\mathbf{v}_S are independently sampled from the same packing set, and does not require specific values of them. Our new proof also does not invoke Lemma 11 ( It has been removed in the new manuscript) to prove 14δ2≤Δ≤δ2\frac{1}{4}\delta^2\leq \Delta\leq \delta^2.

  • Case 1: for any independent v1,…,vS\mathbf{v}_1,\ldots,\mathbf{v}_S, we set

∀s=1,…,S,∀k∈Gs,δk,s=δ=Sdγ232MT.\forall s=1,\ldots,S,\quad \forall k\in G_s,\quad\delta_{k,s}=\delta=\sqrt{\frac{Sd\gamma^2}{32MT}}.

It is enough to use the trivial upper bound on Δ\Delta Δ≤μd2⋅δ2=Sσ264μMT.\Delta\leq\frac{\mu d}{2}\cdot\delta^2=\frac{S\sigma^2}{64\mu MT}.

  • Case 3: for any independent v1,…,vM\mathbf{v}_1,\ldots,\mathbf{v}_M, we set \begin{align*} \forall k=1,2,\ldots,\frac{M-1}{2},\quad\delta_k=\sqrt{\frac{d\gamma^2}{32T^{\nu}}},\quad \nu\in[0,1), \end{align*} and ∀k=M+12,…,M,δk=dγ232T.\forall k=\frac{M+1}{2},\ldots,M,\quad \delta_k=\sqrt{\frac{d\gamma^2}{32T}}. We can prove a lower bound on Δ\Delta without restrictions on the values of v1,…,vM\mathbf{v}_1,\ldots,\mathbf{v}_M, i.e., Δ=ω(σ2μT).\Delta=\omega(\frac{\sigma^2}{\mu T}).

[Question 1.3] How the intermediate regime covers prime MM.

[Answer] Our new proof does not require that MM is divisible by SS. We can divide the clients into SS disjoint groups denoted by Gs,s=1,…,SG_s, s=1,\ldots,S, in which each group Gs⊆[M]G_s\subseteq[M] contains as≥1a_s\geq 1 clients. All of the values of parameters and the analyses are independent of (as)s=1S(a_s)^S_{s=1}.

[Question 2.1] What precisely is the algorithm class in the exact-gradient result? Does it impose the linear-span restriction in Equation (35) on both queries and outputs?

[Answer] The previous manuscript considers algorithm class that imposes the linear-span restriction in Equation (35) on queries. We have redefined the algorithm class where each algorithm generates a sequence of wτk,τ≥1\mathbf{w}^k_{\tau}, \tau\geq 1 such that

\mathrm{Supp}(\mathbf{w}^k_{\tau})\subseteq \bigcap^M_{i=1}\bigcap^{\tau-1}_{t=0}\mathrm{Supp}\left(\nabla F_i(\mathbf{w}^i_t)\right),$$ and outputs $\mathbf{w}^k,k=1,\ldots,M$ where \$\mathbf{w}^k\in \mathrm{span}(\mathbf{w}^k_1,\mathbf{w}^k_2,\ldots,\mathbf{w}^k_T)\$. The algorithm class follows distributed zero-respecting algorithm [1], which covers a broad range of (adaptive) first-order algorithms, such as gradient descent, Nesterov’s accelerated gradient descent, Adam, FedAvg, SCAFFOLD, FedChain, FedCLUP, FedAdam, etc. **[Question 2.2]** What does $T$ count in this result? **[Answer]** In the case of exact gradients, for both our lower bound and upper bounds, $T$ denotes the number of exact gradients queries on each client, rather than the size of its local training set. Our initial manuscript did not explain the distinctions between them. We acknowledge that using the same notation $T$ for these two different quantities may cause confusion. We have added a remark following Theorem 1 in the main text (refer to Remark 1). **[Question 2.3]** How does that model relate to the dataset-based formulation? **[Answer]** In the dataset-based formulation, we define $F_i(\cdot)$ as follows $$\forall i=1,\ldots,M,\quad F_i(\mathbf{w})=\mathbb{E}_{{\bf z}\sim D_i}[f(\mathbf{w},\mathbf{z})],$$ where $D_i$ is the data distribution on the $i$-th client. Then the exact gradient at $\mathbf{w}$ is $$\forall i=1,\ldots,M,\quad\nabla F_i(\mathbf{w})=\mathbb{E}_{{\bf z}\sim D_i}[\nabla f(\mathbf{w},\mathbf{z})].$$ Once we take the expectation with respect to the data, both the loss and its gradient only depend on the model parameter $\mathbf{w}$. We can use any admissible first-order algorithm for exact optimization to solve the dataset-based optimization problem $$\forall i=1,\ldots,M,\quad \min F_i(\mathbf{w}).$$ Thus the lower bound from Theorem 1 holds for the dataset-based formulation in the case of exact gradient regime. **Reference** [1] Blake E. Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs Local SGD for Heterogeneous Distributed Learning. Advances in Neural Information Processing Systems, 33:6281–6292, 2020. **We would be happy to discuss with the reviewer any further questions.**

Dear Reviewer Wkvb,

We sincerely thank you again for providing valuable feedback and for identifying several errors in the initial manuscript. We have revised the manuscript accordingly. As the author–reviewer discussion period is nearing its end, we would like to know if our responses have resolved your concerns.

We would welcome any further questions or feedback and would be happy to continue the discussion.

Best regards,

The Authors

Reviewer_pBTMOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper dedicates to resolve open problem proposed in (Chen et al., 2023). The target problem is to tighten the lower bounds for the minimax weighted excess risk of federated learning setting under statistical heterogeneity for smooth, strongly convex objectives. The authors extend local Fano constructions to both stochastic and exact-gradient regimes. They further propose TWS-Fed, a two-stage method that is claimed to attain these bounds using O(κlog⁡M)O(\kappa\log M) communication rounds, independently of the local sample size TT.

Critical strengths

The authors address the unresolved parameter gaps left by Chen et al. (2023), including the exact-gradient regime. They also separate multiple heterogeneity regimes and compare federated learning against personalized local and non-cooperative learning. Their communication bound is particularly appealing because it does not scale with TT, subject to the stated assumptions.

Critical weaknesses
  • I think the fully characterized weighted excess risk is a bit overstated.

    • The TWS-Fed upper bound differs from the lower bound by an O(log⁡M)O(\log M) factor in the variance term and an $ O(\sqrt{\kappa})$ gap in the exponential term.
    • Thus, isn't it providing a near-characterization in a restricted regime, rather than a full characterization of heterogeneous FL?
  • The manuscript presents an oracle decision as a learning strategy.

    • Its proposed dichotomous strategy chooses TWS-Fed or pure local training according to whether Δ≶σ2μT\Delta \lessgtr \frac{\sigma^2}{\mu T}.
    • That said, this does not explain how the server can estimate Δ,σ2\Delta, \sigma^2, or the relevant threshold without additional samples, private client information, or communication.
    • This also discusses the difficulty of adapting to unknown heterogeneity.
    • Or, at least, synthetic experiments should therefore have been presented given these factors controlled, so that one can confirm that the provided theoretical contributions are viable.
  • The "O(1)O(1)-communication" seems a bit aggressive.

    • The communication cost is provided as R=⌈24κlog⁡S⌉R=\left\lceil24\kappa\log S\right\rceil, and the dependence on the client population appears to use S=MS=M .Thus, it's independent of TT, but not of the condition number or number of clients.
    • Furthremore, it is required to satisfy T1≥38κT_1\ge38\kappa and R≤T2R\le T_2. It implies that the method may not even be runnable with few local samples, many clients, or ill-conditioned objectives.
    • Thus, I think it would be better to tone it down to “communication independent of TT”, rather than stating communication rounds alone.
  • While acknowledging the theoretical contributions, it does not align well with the practical constraints of FL.

    • First, it assumes equal local sample counts and client weights, i.i.d. sampling within each client, and access to all clients during the initialization stage, which are infeasible in modern FL (cf. Kairouz et al,. 2021; Advances and Open Problems in Federated Learning).
    • Second, it requires schedules tuned using unknown constants, such as μ\mu, β\beta, and variance-related quantities, which are rarely known in real deployments.
    • Third, a substantial local computation before federation is required, with enough samples to satisfy T≳κlog⁡MT\gtrsim\kappa\log M. I think this can exclude the data-scarce clients wehre FL is valuable in practice.
    • Fourth, though the second stage samples client subsets, the first-stage construction still depends on training and communicating models across the full client population. This weakens its suitability for practical FL with partial participation.
    • To sum up, it is still a useful theoretical FL algorithm, but not there exist gaps from practical constraints. Please consider narrowing down to claim to heterogeneous local SGD or heterogeneous distributed machine learning, instead of FL.
  • No empirical validation

    • I couldn't find any evidence about sensitivity to inaccurate μ\mu, β\beta, σ2\sigma^2, or Δ\Delta.
    • Even a syntehtic experiment for a comparison with FedAvg should have been conducted, to show the unresolved lower bound gap was significantly impactful in existing FL algorithms.
    • Again, I accept that a theory paper need not provide large scale benchmarks, but controlled simulations are necessary if TWS-Fed is presented as a communication-efficient framework.
Questions for authors
  • Please consider providing a neat notation table.
  • How can the server decide between TWS-Fed and local training without knowing Δ\Delta, σ2\sigma^2, and μ\mu?
  • How does its total communication in bits or transmitted model parameters compare with FedAvg, SCAFFOLD, and local training?
  • How does its first stage operate when only a small, changing fraction of clients is available in practice?
  • Can it support unequal TkT_k, unequal pkp_k, and partial client participation, which are necessary in typical FL setting? If not, please tone it down like heterogeneous local SGD, rather than FL.
  • Does the exact-gradient conclusion remain meaningful when the task requires one shared model or generalization to unseen clients?
4 comments

We sincerely appreciate the Reviewer for considerable time and effort in reviewing our paper, especially for providing valuable feedback.

We have updated the manuscript following the Reviewer’s feedback, with revisions marked in red.

We first clarify some weaknesses.

[Weakness 1] The fully characterized weighted excess risk is a bit overstated.

[Answer] We agree with the reviewer that our algorithm is not optimal. There are gaps between our upper bound and lower bounds. However, by comparison with the upper bounds achieved by existing algorithms, our lower bound is optimal, fully characterizing weighted excess risk.

  • In the variance term, our lower bound matches the upper bounds of existing algorithms, such as SCAFFOLD,characterizing the optimal variance term.
  • In the exponential term, the lower bound can be achieved by independently running the Nesterov’s accelerated gradient descent on each client (please refer to the discussions about Theorem 1).

[Weakness 3] The "O(1)O(1)-Communication" seems a bit aggressive.

[Answer] We thank the reviewer for the valuable suggestion that refines the statement O(1)O(1) by “the communication independent of TT”. We believe that both characterizations are valid.

In our initial manuscript, we have explained that O(1)O(1) means that the communication cost is independent of TT , but can depend on κ\kappa and MM (see the footnote in Page 3). In this work, both κ\kappa and MM are problem-dependent constants that are independent of TT. From the perspective of asymptotic complexity theory, using O(1)O(1) to characterize the communication round is valid.

[Question 1] Please consider providing a neat notation table.

[Answer] We thank the reviewer for this suggestion. We have added a notation tabel in Appendix B (Table 2), which summarizes the main notations used throughout the paper.

[Question 2] How can the server decide between TWS-Fed and local training without knowing Δ\Delta, σ2\sigma^2, and μ\mu?

[Answer] This is an important open problem and is left as an important future work. In principle, deciding between TWS-Fed and pure local training without prior knowledge of Δ\Delta, σ2\sigma^2, and μ\mu would require an adaptive strategy to estimate these parameters.

In this work, our goal is not to develop such an adaptive algorithm, but rather to characterize the conditions under which federated learning is better than non-cooperative learning, showing its advantages and limitations. Specifically, we establish the minimax excess risk under different levels of statistical heterogeneity and identify the regimes in which TWS-Fed or pure local training is preferable.

For certain regularized optimization problems, μ\mu can be readily determined from the regularization term. Besides, it would be easy to estimate σ2\sigma^2 by using an independent training set. Howerver, the main challenge lies in estimating Δ\Delta, which requires carefully designed algorithms.

[Question 3] How does its total communication in bits or transmitted model parameters compare with FedAvg, SCAFFOLD, and local training?

[Answer] In the case of M<S⋅TM< S\cdot T, the total communication in bits or transmitted model parameters of our algorithm is also smaller than FedAvg and SCAFFOLF. Local training requires no communication.

Let dd denote the dimension of parameter and RR denote the number of communication rounds. In the first stage, each of the MM clients independently runs M-SG and uploads its local model to the server, requiring MdMd transmitted scalar parameters. In the second stage, SS clients participate in each communication round. The server broadcasts one dd-dimensional model to each selected client, and each participating client uploads one dd-dimensional update.

Therefore, the total transmitted scalar parameters of TWS-Fed is Md+2SRd=Md+O(dSκln⁡M).Md+2SRd=Md+O(dS\kappa\ln M). where R=O(κln⁡M)R=O(\kappa\ln M).

Next we give the total transmitted scalar parameters of FedAvg, SCAFFOLF and local training.

  • The total transmitted scalar parameters of FedAvg is 2SRd=O(dST)2SRd = O(dS T).
  • SCAFFOLD must transmit control variables and gradients. Thus the total transmitted scalar parameters of SCAFFOLD is 4SRd=O(dST)4SRd = O(dS T).
  • local training: no communication.

If each scalar is represented using bb bits, we can compute the total communication cost in bits.

[Question 4] How does its first stage operate when only a small, changing fraction of clients is available in practice?

[Answer] In the first stage, our two-stage strategy is also applicable when only a small fraction of clients is available. We can randomly sample a subset of clients in the first stage. In the case, the minimax upper bound remain unchanged. To be specific, in the last page (marked in blue), we analyze how the initial model w1\mathbf{w}_1 influences the minimax excess risk. If we uniformly select a subset of clients with size S<MS<M, denoted by C\mathcal{C}, then the initial model returned from the first stage, denoted by w1′\mathbf{w}'_1, is defined by

w1′=1S∑i∈Cw^∗i.\mathbf{w}'_1=\frac{1}{S}\sum_{i\in \mathcal{C}}\hat{\mathbf{w}}^i_{\ast}.

w1\mathbf{w}_1 is the initial parameter obtained by selecting all of the clients in the first stage. It is easy to prove

E[w1′]=w1.\mathbb{E}[\mathbf{w}'_1]=\mathbf{w}_1. Following the proof in the last page (marked in blue), it is easy to prove the same minimax excess risk bound. Therefore, in expectation, the two strategies enjoy the same excess risk bound. Because only one round of communication is required during the first stage, we choose to include all clients.

[Question 5] Can it support unequal TkT_k, unequal pkp_k, and partial client participation?

[Answer] We thank the reviewer for raising this important question and agree that unequal TkT_k and pkp_k, and partial client participation are common in practical FL.

  • Our two-stage strategy and the current theoretial results are applicable for partial client participation (refer to Question 4).
  • Extending the algorithm and theoretical analysis to unequal TkT_k and pkp_k is non-trivial. Below, we outline a possible extension. Specifically, we retain the first stage of the algorithm and modify the second stage by allowing different numbers of local gradient descent steps across clients. However, establishing a rigorous weighted excess risk bound requires additional analysis. Extending the proposed two-stage strategy to unequal TkT_k and pkp_k is an important and interesting direction for future research.

We would be happy to discuss with the reviewer any further questions.

Thank you for your substantial efforts, and I apologize for the delayed response. While some of the designs and knobs are a bit off for a practical FL scenario, I would raise my score given the primary area assigned to this manuscript and its solid theoretical contribution.

Please promise to refine and polish the manuscript; it was difficult to parse at first glance because the text is tightly packed and dense overall. Note that authors can still use pages up to 10!

We sincerely thank the reviewer again for the constructive feedback, for recognizing the theoretical contributions of our work, and for raising the overall assessment.

We will take the reviewer’s suggestions into account and further polish the manuscript to improve its clarity.

Reviewer_xLefOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies the minimal excess risk in FL under heterogeneity. They show a sharper matching lower bound, attempting to resolve the open problem. Besides, they also design a two-stage FL that improves the communication complexity.

Critical strengths

The paper is well motivated and it aims to close the open gap. The proposed two stage algorithm looks simple yet interesting.

Critical weaknesses

There seem to be some gaps in the lower bound proof: Line 853:

We uniformly and independently sample v1,...,vS ∈V. However, in case 1 and case 3 it's required that each v_i is unique. So sampling without replacement should be used here?

Line 1140: For any first-order algorithm, it must be Eq (35). Why is this necessarily true?

There are no numerical experiments to demonstrate the advantages of the proposed two-stage algorithm.

Questions for authors

See questions above. In addition, can you elaborate on the improvement of the upper bound of the two-staged algorithm over other existing bounds? Also in 4.4.1 it's mentioned that M-SG improves its excess risk over SGD by (Stich 2019). However, the exponent decay is smaller.

2 comments

We sincerely appreciate the Reviewer for considerable time and effort in reviewing our paper, especially for providing valuable feedback.

We have updated the manuscript following the Reviewer’s feedback, with revisions marked in red.

[Question 1] We uniformly and independently sample v1,...,vS∈V\mathbf{v}_1,...,\mathbf{v}_S \in \mathcal{V}. However, in Case 1 and Case 3, it's required that each vi\mathbf{v}_i is unique. So sampling without replacement should be used here?

[Answer] We should not use sampling without replacement. We have given a new and simpler proof for the lower bound in the stochastic gradient regime. Our new proof only requires that v1,v2,…,vS\mathbf{v}_1,\mathbf{v}_2, \ldots,\mathbf{v}_S are independently sampled from V\mathcal{V}, and does not require specific values of them.

  • Case 1: We only require any independent v1,…,vS\mathbf{v}_1,\ldots,\mathbf{v}_S

  • Case 3: We only require any independent v1,…,vM\mathbf{v}_1,\ldots,\mathbf{v}_M.

[Question 2] Line 1140: For any first-order algorithm, it must be Eq (35). Why is this necessarily true?

[Answer] Our statement is not correct. First-order algorithm is a larger algorithm class than that defined by Eq(35).

  • We have corrected this statement, and also defined the algorithm class (rather than first-order algorithm) in Theorem 1.
  • We have redefined the algorithm class where each algorithm generates a sequence of wτk,τ≥1\mathbf{w}^k_{\tau}, \tau\geq 1 such that
\bigcap^M_{i=1}\bigcap^{\tau-1}_{t=0}\mathrm{Supp}\left(\nabla F_i(\mathbf{w}^i_t)\right),$$ and outputs $\mathbf{w}^k,k=1,\ldots,M$ where \$\mathbf{w}^k\in \mathrm{span}(\mathbf{w}^k_1,\mathbf{w}^k_2,\ldots,\mathbf{w}^k_T)\$. This algorithm class covers a broad range of (adaptive) first-order algorithms, such as gradient descent, Nesterov’s accelerated gradient descent, Adam, FedAvg, SCAFFOLD, FedChain, FedCLUP, FedAdam, etc. **[Question 3]** Can you elaborate on the improvement of the upper bound of the two-staged algorithm over other existing bounds? **[Answer]** As shown in Table 1, our algorithm achieves a slightly worse upper bound of order $O(\ln{M})$ compared with existing algorithms such as SCAFFOLD. However, it only requires $O(\kappa \ln{M})$ communication rounds, whereas existing algorithms require $O(T)$ rounds. **The key advantage of our two-stage algorithm is thus a substantial reduction in communication rounds, attained at the expense of a modest deterioration (i.e., $O(\ln{M})$) in the excess risk bound**. **[Question 4]** In 4.4.1 it's mentioned that M-SG improves its excess risk over SGD by (Stich 2019). However, the exponent decay is smaller. **[Answer]** We agree with the Reviewer that the excess risk achieved by (Stich 2019) enjoys a more favorable problem-independent constant in its exponential decay term, namely $-\frac{1}{4}$, compared with our constant of $-\frac{1}{16}$. **Nevertheless, our algorithm improves the problem-dependent constant within the exponential decay term from $O(\beta)$ to $O(\mu)$. Our focus lies primarily on this problem-dependent constant.** **[Question 5]** There are no numerical experiments to demonstrate the advantages of the proposed two-stage algorithm. **[Answer]** We thank the reviewer for this valuable suggestion. We agree that numerical experiments could provide additional empirical insights into the performance of the proposed two-stage algorithm. However, we would like to emphasize that the primary contributions of this work are theoretical. Our goal is to characterize the minimax excess risk of federated learning under statistical heterogeneity and the fundamental trade-off between excess risk and communication complexity. We believe that these theoretical results provide fundamental insights into the benefits and limitations of federated learning. We acknowledge that numerical experiments are valuable for our theoretical results and leave a comprehensive empirical evaluation for future work. **We would be happy to discuss with the reviewer any further questions.**

Dear Reviewer xLef,

We sincerely thank you again for providing valuable feedback. We have revised the manuscript accordingly. As the author–reviewer discussion period is nearing its end, we would like to know if our responses have resolved your concerns.

We would welcome any further questions or feedback and would be happy to continue the discussion.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.