- 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 is the strong-convexity parameter and 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 , independent of T, with . 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
- The paper addresses an important statistical question with an interpretable target rate.
The proposed bound distinguishes a shared estimation cost, , 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.
- 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
- The stochastic lower-bound proof does not consistently establish the claimed heterogeneity-dependent family.
Appendix C.1 samples group parameters 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 . 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.
- 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
- Stochastic minimax class: Is the stochastic minimax class defined by , 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.
- 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?
- Scope of parameter dependence: The stochastic construction sets and has sample smoothness . Can the authors establish the claimed dependence for independently specified admissible , while tracking the effect of rescaling on all parameters? This matters for assessing the claimed improvement in strong-convexity dependence.
5 comments
[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 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
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.
[Question 3] Can the authors establish the claimed dependence for independently specified admissible μ, β, σ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, where we sample x uniformly and independently from (d⋅e1,d⋅e2,…,d⋅ed). The strong onvexity parameter is μ. The smooth parameter is β=μd2. We can assign any admissible μ. We can also assign any admissible β by tuning d. Besides, the variance σ2 is also independent of μ and β, and can be any admissible value.
[Question 1.1] Is the stochastic minimax class defined by Δ<Δˉ, 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:
Δ=ω(μMTσ2) and Δ=O(μTσ2). The lower bound on minimax risk is Ω(Δ).
Δ≥0 and Δ=O(μMTσ2). The lower bound on minimax risk is Ω(σ2/(μMT)).
Δ=ω(μTσ2). The lower bound on minimax risk is Ω(σ2/(μ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 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 41δ2≤Δ≤δ2.
∀s=1,…,S,∀k∈Gs,δk,s=δ=32MTSdγ2.
It is enough to use the trivial upper bound on Δ Δ≤2μd⋅δ2=64μMTSσ2.
[Question 1.3] How the intermediate regime covers prime M.
[Answer] Our new proof does not require that M is divisible by S. We can divide the clients into S disjoint groups denoted by Gs,s=1,…,S, in which each group Gs⊆[M] contains as≥1 clients. All of the values of parameters and the analyses are independent of (as)s=1S.