- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes a new problem formulation (Equation 1) and a corresponding method (Algorithms 1 and 2), supported by substantial theoretical guarantees. The theoretical results appear sound, although I have not examined the proofs in the appendices.
Given its potentially novel perspective on federated learning and solid theoretical analysis, I lean toward acceptance if my concerns are adequately addressed. I would also consider the feedback from other reviewers.
Critical strengths
The paper introduces an interesting perspective on federated learning and proposes a corresponding algorithm with substantial theoretical guarantees. The theoretical analysis appears solid.
Critical weaknesses
-
Restrictive assumptions. The problem formulation and main theoretical results primarily focus on strongly convex objectives and linear tilts. The proposed estimation procedure also relies on independence and mean-zero assumptions. These restrictions may limit the applicability of the proposed framework.
-
Limited generalizability. My main concern is generalizability. Some possible directions to generalize it:
(i) General convex and nonconvex objectives: Can the problem be formulated for general convex or even nonconvex objectives? In particular, how should the learning objective be defined in the nonconvex setting, and how would the algorithm change? Such extensions could attract broader research interest.
(ii) Multiple local updates: The proposed algorithm is primarily based on minibatch SGD with a single update per round. Can it be extended to local SGD with multiple local updates?
If these extensions are currently difficult, I would appreciate a brief discussion of possible approaches and the associated technical challenges.
Questions for authors
- Novelty of the proposed perspective. The authors describe their formulation as a new "wisdom of crowds" perspective on federated learning. Could they clarify its novelty compared with existing formulations? At first glance, it introduces a client-specific perturbation into each local objective, which appears straightforward.
- Algorithm 1, Line 4. Since the update (x^k\gets\Pi_{\mathcal X}(\cdots)) is performed by the server, should it be placed under "Server: statistics from the same reports" rather than the client operations?
4 comments
Dear Reviewer G3cj,
Thank you again for the constructive suggestions. On generalizability, we added a non-convex extension (Proposition C.13) and experiments with several local steps under FedAvg and SCAFFOLD (Table 2).
We would appreciate your view on whether these additions answer your questions, and we remain available for any further discussion.
Best regards, The Authors
Thanks for the detailed responses.
- My weakness 1: I appreciate the clarification of the scope/assumptions for each result.
- My weakness 2: I appreciate the newly added content with respect to Polyak–Łojasiewicz inequality.
The authors explains why the extension can be difficult. However, the mentioned concerns of the extension for general convex/non-convex cases, and some restrictive assumptions still exist. These restrictions may limit the applicability. So I keep my original positive rating.
Thank you for reading our responses and for keeping your positive rating. We agree that these limitations remain, and we will state them explicitly in the final version, together with the possible approaches as directions for future work.
Thank you for the positive assessment and the concrete suggestions. We start with generalizability, which you name as your main concern, and then turn to the assumptions and your two questions.
Weakness #2(i) (non-convex objectives). Yes. The algorithm is unchanged, the target becomes a local minimiser x0⋆ of f0, and new Proposition C.13 (App. C.7) keeps the same bias term under a local Polyak–Łojasiewicz inequality. The other assumptions are those of Theorem 4.4, plus the condition that the iterates stay in the basin of x0⋆. Schematically, for every ϵ>0,
E[f0(x^)−f0⋆]≤2μ(1+ϵ)(1+κ)(Ψ^(bT)+2Δ)+O(T−1/2),
where the first term is the bias term of Theorem 4.4. The estimator does not involve f0, so only the optimisation term changes.
Weakness #2(ii) (multiple local updates). Yes, empirically: CROWD works with local steps, and best with a drift-corrected optimiser such as SCAFFOLD. New Table 2 (App. H) runs FedAvg with 1, 5 and 20 local steps and SCAFFOLD with 5 and 20 on both real-scan federations, with the SCAFFOLD control variate weighted by w. Excess risk relative to uniform weighting with the same optimiser, medians:
On the convention federation, client drift under FedAvg removes CROWD's gain at 20 steps, while SCAFFOLD keeps it. On the sensor federation CROWD stays close to inverse-noise weighting. Weights and drift correction address different errors, so they should be combined.
Two extensions remain directions for future research: general convex objectives without a growth condition, and a theory for several local steps. We find both settings interesting in their own right, because each changes what the crowd's disagreement can reveal. For general convex f0, a small gradient bias can move the minimiser far along flat directions, so the bias energy no longer controls the excess risk; a new link between bias and risk is needed, for example through a Hölderian error bound. For local steps, the reports are no longer gradients at one query point, and client drift adds a client-specific term to each report. The open step is to show that the residual statistics of Theorem 4.1 stay unbiased when computed from local updates; given that, a SCAFFOLD drift analysis could be combined with our bias bound. Neither is a routine extension of the present proofs: the first needs a new link between bias and risk, the second new estimation results, which is why we leave them for future work.
Weakness #1 (restrictive assumptions). The sharpest results do use linear tilts and a strongly convex truth, but several results do not, and each result now states its assumptions. Lemmas 4.2 and 4.3 hold for arbitrary tilts. Theorem C.7 covers curved crowds with client-specific curvature. Proposition 4.7 gives a guarantee without independence, centring or linearity. Independence and centring cannot be dropped entirely: correlation destroys identifiability (Prop. C.4), and centring cannot be tested (Prop. C.1). A new paragraph at the start of §4 lists the assumptions of each result.
Question #1 (novelty). The formulation is a simple step, but it leads to results that existing formulations do not give. The common objective cannot be identified from one federation (Prop. 3.1, Thm. 4.5). Yet the per-client bias energies can be estimated from the disagreement along the optimisation path (Thm. 4.1). The resulting excess risk matches a Bayesian minimax lower bound in the same constant (Cor. 4.6). And no check computed from the data can certify that a weighting beats uniform weighting (Prop. C.14), which is why the guarantee is stated under A1.
Question #2 (Algorithm 1). Corrected: the server update now sits in the server block of Algorithm 1.