- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
They propose AdaFed, an federated adaptive optimization method that uses Adagrad-style local step size updates. What interesting theoretically is the control of client drift through aggressive local-step control instead of drift compensation or data heterogeneity bounds. Most importantly, the authors established convergence guarantees across smooth nonconvex, smooth convex, and nonsmooth convex objectives without prior knowledge of the problem class or smoothness parameters. Experiments on synthetic and logistic regression illustrate the predicted convergence behavior and compare AdaFed with existing adaptive FL methods.
Critical strengths
- The paper establishes convergence guarantees across smooth nonconvex, smooth convex, and nonsmooth convex objectives using a single adaptive rule without prior knowledge of the problem class or smoothness parameters.
- The analysis addresses local drift and delayed adaptive accumulation without requiring bounded iterates. Additionally, the experiments report objective gaps and gradient norms that directly correspond to the theoretical guarantees.
Critical weaknesses
-
The significance of local optimization relative to distributed minibatching remains unclear. The prescribed local-step scale decays as , increasingly restricting client movement. Additionally, the stated convergence rate reflect the benefit of additional local steps primarily through variance reduction. Thus a comparison with distributed minibatch AdaGrad under matched gradient-evaluation and communication budgets would help establish whether the method offers advantages beyond minibatching.
-
The convergence rate listed in the manuscript obscure dependence on client heterogeneity. In the smooth cases, proof constants depend on initial client-gradient magnitudes, which incorporate gradient disagreement. Making this dependence explicit would help readers distinguish avoiding a uniform bounded-heterogeneity assumption from obtaining heterogeneity-independent guarantees.
Questions for authors
Please address my two concerns above.
Rebuttal
Thank you for your review and the precise comments. Both points are accurate and addressing them has improved the paper. We respond to each below. Unless stated otherwise, line, equation, section, and appendix numbers refer to the submitted version. The works we cite are listed in the paper's references or, if not, at the end of this response.
W1.
We agree with the reviewer's reading. Theorem 4.4 benefits from additional local steps through the averaging of the oracle noise, via the term σ/mKT, and with exact gradients the rates do not improve with K.
Distributed minibatch AdaGrad evaluates the K stochastic gradients of each client at xt and applies the update in Eq. (Core-FP) with gˉtmb:=mK1∑i=1m∑k=0K−1gi(xt;ωi,kt). It uses the same number of oracle calls (mK per round) and communication rounds as AdaFed. It has no local drift (b^t=0), and its averaged noise satisfies the same bound σ2/(mK) (Eq. (15)). Hence, at matched budgets, similar rates can be derived for distributed minibatch AdaGrad.
In fact, without a bounded-heterogeneity assumption, local-update methods are not expected to improve over minibatching in the worst case. Woodworth et al. (2020) show that under high heterogeneity, local SGD does not improve over minibatch SGD, and that the optimal rate for smooth convex objectives is then of order 1/T2+σ/mKT, with m and K only in the noise term. The decaying schedule of τt in AdaFed controls the local drift without such an assumption (see also our response to Reviewer fDKH, Q2).
Since distributed minibatch AdaGrad is centralized AdaGrad with minibatches, its universality follows from centralized results. The open question we address is whether universality can be retained by a local-update method under heterogeneous clients. Existing adaptive FL methods with local updates do not have this property (Appendix H). Our results show that, with AdaFed, local updates retain universality. Showing that local steps provably help beyond minibatching would require additional structure, such as bounded heterogeneity or second-order similarity (see also our response to W2). We have stated this limitation explicitly in the revision after Eq. (6).
W2.
We agree. Theorem 4.4 does not assume bounded heterogeneity, but its guarantees are not independent of heterogeneity. In the smooth cases, the constants depend on the client gradients at the initial point x1 (through the constants B and B in Line 841), and in the smooth convex case also at the minimizer x⋆ (Eq. (50)). By the identity m1∑i=1m∣∇Fi(u)∣2=∣∇F(u)∣2+m1∑i=1m∣∇Fi(u)−∇F(u)∣2, applied at u=x1 and u=x⋆, these constants include the disagreement among the client gradients at x1 and x⋆. We now state this explicitly in Remark 4.5 of the revision.
The smooth-case constants can likely be sharpened further. The current proof bounds each client gradient as a whole by ∣∇Fi(xt)∣≤∣∇Fi(u)∣+L∣xt−u∣, with u=x1 in Eq. (19) and u=x⋆ in Eq. (50), which keeps the term L∣xt−u∣ even for identical clients. With the split ∇Fi=∇F+(∇Fi−∇F) instead, the global part can be absorbed into the descent argument. The deviation is at most its value at u plus (supxmaxi∣∇2Fi(x)−∇2F(x)∣)∣xt−u∣. Heterogeneity would then enter only through the gradient disagreement at u and the Hessian dissimilarity, both of which vanish for identical clients. This requires reworking the drift and displacement bounds in Appendices B and C, and we leave it for future work.
References
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local SGD for heterogeneous distributed learning. In Advances in Neural Information Processing Systems, 2020.