acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Federated Optimization Across Smooth and Nonsmooth Regimes

Abstract

AdaGrad-style methods can simultaneously adapt to both the order and constants of smoothness in centralized optimization. However, existing extensions to federated optimization with heterogeneous client objectives and multiple local steps require the smoothness order to be specified in advance. We address this limitation with AdaFed, a federated method that adapts across several regimes under a single choice of parameters. In the deterministic setting, AdaFed achieves an convergence rate for both smooth nonconvex and smooth convex objectives, and an rate for Lipschitz nonsmooth convex objectives. Under a light-tailed stochastic-gradient noise assumption, these guarantees extend to the stochastic setting with additional logarithmic factors and noise-dependent terms. Experiments across the three problem classes further support our theoretical findings.

Primary area:
optimization
Keywords:
Adaptive optimization, Federated Learning, AdaGrad

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_tt4qOpenReview ↗
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
  1. 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.
  2. 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
  1. The significance of local optimization relative to distributed minibatching remains unclear. The prescribed local-step scale decays as 1/((K−1)t)1/((K-1)t), 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.

  2. 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.

1 comment

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\sigma/\sqrt{mKT}, and with exact gradients the rates do not improve with KK.

Distributed minibatch AdaGrad evaluates the KK stochastic gradients of each client at xtx_t and applies the update in Eq. (Core-FP) with gˉtmb:=1mK∑i=1m∑k=0K−1gi(xt;ωi,kt).\bar g_t^{\mathrm{mb}}:=\frac1{mK}\sum_{i=1}^m\sum_{k=0}^{K-1}g_i(x_t;\omega_{i,k}^t). It uses the same number of oracle calls (mKmK per round) and communication rounds as AdaFed. It has no local drift (b^t=0\hat b_t=0), and its averaged noise satisfies the same bound σ2/(mK)\sigma^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+σ/mKT1/T^2+\sigma/\sqrt{mKT}, with mm and KK only in the noise term. The decaying schedule of τt\tau_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 x1x_1 (through the constants BB and B~\widetilde B in Line 841), and in the smooth convex case also at the minimizer x⋆x^\star (Eq. (50)). By the identity 1m∑i=1m∣∇Fi(u)∣2=∣∇F(u)∣2+1m∑i=1m∣∇Fi(u)−∇F(u)∣2,\frac1m\sum_{i=1}^m\\|\nabla F_i(u)\\|^2=\\|\nabla F(u)\\|^2+\frac1m\sum_{i=1}^m\\|\nabla F_i(u)-\nabla F(u)\\|^2, applied at u=x1u=x_1 and u=x⋆u=x^\star, these constants include the disagreement among the client gradients at x1x_1 and x⋆x^\star. 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∣\\|\nabla F_i(x_t)\\|\le\\|\nabla F_i(u)\\|+L\\|x_t-u\\|, with u=x1u=x_1 in Eq. (19) and u=x⋆u=x^\star in Eq. (50), which keeps the term L∣xt−u∣L\\|x_t-u\\| even for identical clients. With the split ∇Fi=∇F+(∇Fi−∇F)\nabla F_i=\nabla F+(\nabla F_i-\nabla F) instead, the global part can be absorbed into the descent argument. The deviation is at most its value at uu plus (sup⁡xmax⁡i∣∇2Fi(x)−∇2F(x)∣)∣xt−u∣(\sup_x\max_i\\|\nabla^2F_i(x)-\nabla^2F(x)\\|) \\|x_t-u\\|. Heterogeneity would then enter only through the gradient disagreement at uu 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.

Reviewer_fDKHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes AdaFed, an adaptive federated optimization algorithm that uses an aggregated server-level direction to update a shared scalar learning rate. A time-dependent local-step scaling factor is introduced to control client drift. The authors establish convergence guarantees for smooth nonconvex, smooth convex, and Lipschitz convex objectives within a unified framework, with extensions to partial participation and Hölder-smooth convex objectives under additional conditions. Experiments on synthetic logistic-regression problems and IJCNN1 compare AdaFed with several adaptive federated optimization baselines. The main contribution is theoretical; the extent of its advance over existing adaptive federated methods requires clearer demonstration.

Critical strengths
  1. The paper addresses a meaningful theoretical problem by establishing convergence guarantees for smooth nonconvex, smooth convex, and Lipschitz convex objectives within a unified adaptive federated optimization framework.

  2. The analysis addresses client drift caused by multiple local updates and delayed accumulation of aggregated server directions. The main results also avoid bounded-domain and bounded-iterate assumptions.

Critical weaknesses

The authors have addressed several of my previous mathematical concerns. In particular, the revised local-drift analysis is consistent, the stochastic noise terms are retained, and the correction to Eq. (56) is properly propagated through Eqs. (58)–(60) and the final CTC_T bound. My remaining concerns are as follows.

  1. Compared with Wang and Yurtsever (2026), the main technical contribution is extending centralized universal adaptive optimization to federated multi-step updates by controlling local gradient drift through server displacement and handling the delayed server accumulator. While this analysis is technically nontrivial, the resulting rates essentially match centralized AdaGrad up to logarithmic factors. Moreover, the benefit of increasing KK under stochastic gradients mainly comes from noise averaging, while no additional convergence improvement is obtained under exact gradients. The convergence constants also remain dependent on client gradient disagreement. Thus, the distinction from existing universal adaptive optimization and federated optimization results is still not sufficiently substantial.

  2. The revised manuscript claims to use balanced k-means partitioning and 20 random seeds, whereas the submitted code still uses margin-sorted round-robin partitioning, with only 10 seeds for the rate study and 3 for the benchmark. This discrepancy prevents independent reproduction of the revised experimental results.

Questions for authors
  1. Theoretical novelty. The introduction states that AdaFed is, to the authors’ knowledge, the first federated-learning method to provide one convergence guarantee covering smooth nonconvex, smooth convex, and Lipschitz convex objectives without problem-dependent tuning. The related-work section includes comparisons with prior methods, but the precise distinction from Theorem 4.4 remains difficult to assess. What is the exact boundary of the novelty claim when objective classes, oracle assumptions, client participation, heterogeneity conditions, parameter knowledge, and convergence rates are considered?

  2. Role of the local-step scaling. Theorem 4.4 requires τt≤1(K−1)t\tau_t\leq\frac{1}{(K-1)t} for K≥2K\geq2, while the stated stochastic convergence bound contains a term proportional to σCTmKT\frac{\sigma C_T}{\sqrt{mKT}}. Algorithm 1 uses τt\tau_t to generate local client trajectories and normalizes the aggregated model displacement by KτtK\tau_t. How should the dependence on KK in the theorem be interpreted under this schedule? Which parts of the analysis capture sequential local optimization, and which reflect the stochastic-gradient contribution associated with mKmK?

  3. Client heterogeneity. Appendix G.1 constructs the synthetic and IJCNN1 client splits by sorting examples by margin and distributing them round-robin within blocks of 32 and 50 examples, respectively. The paper motivates AdaFed partly through its ability to accommodate heterogeneous client objectives, but the induced heterogeneity of these specific splits is not reported. What level of client heterogeneity do these partitions induce, and how does the evidence establish the relevance of the results to the heterogeneous-client setting emphasized in the paper?

  4. Scope of parameter-free adaptation. The introduction states that AdaFed operates without prior knowledge of the objective class or associated parameters. In the experiments, Appendix G.2 selects η\eta separately across dataset families, objective regimes, oracle types, and stochastic batch sizes, while Appendix G.6 also tunes η\eta and γ\gamma for individual settings. How should the parameter-free claim be interpreted in light of this protocol? Please distinguish the scope of the theoretical guarantee from the level of parameter reuse demonstrated empirically.

  5. Proof step in Appendix C. In Appendix C, Eq. (56), the authors derive E[DT2]≲1+E[RT2]\sqrt{\mathbb{E}[D_T^2]}\lesssim 1+\sqrt{\mathbb{E}[R_T^2]} and then conclude E[DT2]≲E[RT2]\sqrt{\mathbb{E}[D_T^2]}\lesssim\sqrt{\mathbb{E}[R_T^2]}. The latter implication requires additional justification, since no positive lower bound on E[RT2]\sqrt{\mathbb{E}[R_T^2]} is established under the stated assumptions. The same absorption of additive constants is used in Eqs. (58)–(59), which feed into the subsequent bound on RTR_T. Can the authors justify this transition or carry the additive constants through the subsequent argument and establish that the claimed bound still follows?

4 comments
AuthorsOpenReview ↗

Rebuttal part 1

Thank you for your review. We provide our responses to the weaknesses and questions below. Unless stated otherwise, line, equation, section, figure, 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/Q1.

We would like to clarify that universality and parameter-free are two different notions (see also footnote 1 in (Levy et al., 2018)). By universality, we mean that the same update rule, with the same parameters, attains the rate of each problem class without being told which class the problem belongs to (in the sense of (Nesterov, 2015)). This is different from proving separate guarantees for each class with class-specific step size strategies (e.g., constant steps ∝1/L\propto 1/L for smooth objectives and diminishing steps ∝1/t\propto 1/\sqrt{t} for nonsmooth ones), which requires knowing the class in advance. It is also different from being parameter-free. AdaGrad-type methods are in general not parameter-free. Their step-size parameter can be chosen arbitrarily, but it enters the constants of the bounds and affects practical performance. Yet they enjoy universal convergence guarantees in centralized optimization (Lines 121–125; e.g., Levy et al., 2018; Kavis et al., 2019; Ene et al., 2021). AdaFed is universal in the same sense, as the rates of Theorem 4.4 hold for every choice of η,γ>0\eta,\gamma>0, and these parameters affect only the constants in the bounds, not the rates. The paper does not claim to be parameter-free (see our response to Q4).

Thus, the novelty of our paper is universality in FL. We propose AdaFed, a single adaptive method that, without knowledge of the problem class or of problem parameters (LL, GG, σ\sigma, heterogeneity), attains the AdaGrad rates for smooth nonconvex, smooth convex, and Lipschitz convex objectives, under heterogeneous clients and multiple local steps (Lines 073–079, Table 1). Centralized AdaGrad-type methods are often universal (Lines 042–048), whereas no adaptive FL method had this property before (Lines 049–063, 135–140, Appendix H). Our paper specifically closes this gap (central question in Lines 061–063).

The boundary along the dimensions listed by the reviewer can be summarized as follows:

  • Objective classes. LL-smooth nonconvex, LL-smooth convex, and GG-Lipschitz convex client objectives, with the same update rule and the same schedule τt\tau_t (Theorem 4.4). For exact gradients and convex objectives, also Hölder smoothness of any order α∈[0,1]\alpha\in[0,1] (Appendix F).
  • Oracle. Exact or stochastic local gradients. The stochastic results assume light-tailed noise (Assumption 4.2). Proposition 4.3 shows that bounded variance alone is insufficient for AdaFed.
  • Participation. Full participation in Theorem 4.4. Independent, nonuniform partial participation is covered for exact local gradients (Appendix E).
  • Heterogeneity. No bounded-heterogeneity assumption in Theorem 4.4. Heterogeneity affects only the constants, through the client gradients at reference points (see our response to Reviewer tt4q, W2). The smooth partial-participation results additionally assume bounded heterogeneity (Appendix E).
  • Parameter knowledge. No knowledge of LL, GG, σ\sigma, or the heterogeneity level is required. The rates hold for every η,γ>0\eta,\gamma>0, and τt\tau_t depends only on KK and tt.
  • Rates. O~(1/T+σ/mKT)\widetilde O(1/T+\sigma/\sqrt{mKT}) for smooth nonconvex (on E∣∇F(xˉT)∣2\mathbb{E}\\|\nabla F(\bar x_T)\\|^2) and smooth convex objectives (on E[F(xˉT)−F⋆]\mathbb{E}[F(\bar x_T)-F^\star]), and O~(1/T+σ/mKT)\widetilde O(1/\sqrt{T}+\sigma/\sqrt{mKT}) for Lipschitz convex objectives (on E[F(xˉT)−F⋆]\mathbb{E}[F(\bar x_T)-F^\star]), matching centralized AdaGrad for each class up to logarithmic factors (Eq. (6)).

Comparison with the methods named by the reviewer (more details and other methods in Appendix H):

MethodObjective classesOracleMain assumptionsStep sizes
FedAdagrad (Reddi et al., 2021)smooth nonconvexstochasticbounded gradients, bounded variance, bounded heterogeneitydepend on LL and TT
FAFED (Wu et al., 2023)smooth nonconvexstochasticbounded gradients, bounded variance, bounded heterogeneitydepend on LL
FedAda² (Lee et al., 2025)smooth nonconvexexact onlybounded gradientsdepend on TT
AdaFedsmooth nonconvex, smooth convex, Lipschitz convexstochasticlight-tailed noisearbitrary η,γ>0\eta,\gamma>0

Two difficulties absent from centralized AdaGrad arise in our analysis. These are the local drift and a delayed accumulator (the server displacement of round tt is not available during round tt). We handle them by bounding the local drift by the server displacement, and by bounding the server displacement almost surely by the maximal noise, whose moments grow only logarithmically (Lines 099–106, Section 4.2).

AuthorsOpenReview ↗

Rebuttal part 2

W2/Q2.

Role of τt\tau_t and of the normalization. Since Δit=−(Kτt/qt)gˉt(i)\Delta_i^t=-(K\tau_t/q_t)\bar g_t^{(i)}, normalizing the aggregated displacement by KτtK\tau_t gives the server update xt+1=xt−gˉt/qtx_{t+1}=x_t-\bar g_t/q_t (Eq. (Core-FP), Lines 156–186). The server step size 1/qt1/q_t is set by the adaptive accumulator alone, and τt\tau_t does not scale it. The role of τt\tau_t is only to determine where along the local paths the mKmK gradients in gˉt\bar g_t are evaluated, i.e., how far the local iterates drift from xtx_t. The schedule depends only on KK and tt, not on problem parameters.

Sequential local updates. In the smooth nonconvex analysis (Section 4.2), they enter through the local drift b^t\hat b_t in the decomposition gˉt=∇F(xt)+b^t+ξˉt\bar g_t=\nabla F(x_t)+\hat b_t+\bar\xi_t (Lines 289–291), and b^t=0\hat b_t=0 when K=1K=1 (Line 309). The schedule τt≤1/((K−1)t)\tau_t\leq1/((K-1)t) keeps the local paths short enough that the accumulated drift is bounded by the server displacement, ∑tE∣b^t∣2≲1+RT\sum_t\mathbb{E}\\|\hat b_t\\|^2\lesssim1+\mathcal R_T (Eq. (8)), without any bounded-heterogeneity assumption. In the convex analyses, local updates also enter through the linearization error ϵt\epsilon_t (Eq. (48)), which vanishes when K=1K=1. In the Lipschitz convex case this is the only channel, and ∑tE[ϵt]≲(1+σ)log⁡(T+1)\sum_t\mathbb{E}[\epsilon_t]\lesssim(1+\sigma)\log(T+1) since ∑tτt≲log⁡(T+1)/(K−1)\sum_t\tau_t\lesssim\log(T+1)/(K-1) (Appendix D). In all three classes, the local drift affects only constants and logarithmic factors, not the rates.

Why τt\tau_t decays. With exact gradients in the smooth classes, qtq_t remains bounded, so the server step does not vanish. With a constant τt\tau_t, AdaFed would then behave like FedAvg with a fixed local step size, whose fixed points under heterogeneous objectives are in general not stationary points of FF (see, e.g., Pathak & Wainwright, 2020; Charles & Konečný, 2021). The decay of τt\tau_t removes this bias without control variates and without a bounded-heterogeneity assumption.

Stochastic contribution of mKmK. The noise term ξˉt\bar\xi_t averages mKmK independent oracle errors, so Et∣ξˉt∣2≤σ2/(mK)\mathbb{E}_t\\|\bar\xi_t\\|^2\leq\sigma^2/(mK) (Eq. (15), and the term 2σ2/(mK)2\sigma^2/(mK) in Eq. (7)), which produces the term σ/mKT\sigma/\sqrt{mKT}. In the smooth classes, for a fixed number of rounds TT, more local steps therefore mean more oracle calls per round and a smaller noise term. In the Lipschitz convex class, the factor VT\mathcal V_T in Eq. (4) contains σ2(1+log⁡(mKT))\sigma^2(1+\log(mKT)), so the leading term VT/T\mathcal V_T/\sqrt T is not reduced by mKmK; note that even for centralized subgradient methods, minibatching improves only the constant of the 1/T1/\sqrt T rate. With exact gradients (σ=0\sigma=0), the rates do not depend on KK in any class.

Interpretation. This is the expected behavior when heterogeneity is not bounded. In fact, Woodworth et al. (2020) show that under high heterogeneity, local SGD does not improve over minibatch SGD, whose rate has the same form 1/T+σ/mKT1/T+\sigma/\sqrt{mKT}. Figure 1 is consistent with this result (Lines 414–420): with exact gradients, the curves for K∈1,10,100K\in\\{1,10,100\\} nearly coincide; with stochastic gradients, a larger KK delays the transition to the noise-dominated regime in the smooth classes and improves the constant in the nonsmooth class.

AuthorsOpenReview ↗

Rebuttal part 3

Q3.

We agree that the margin-sorted round-robin partitions are not adequate. In the revision, we reran all experiments (including those in the appendix) on a new partition designed to induce strong heterogeneity. Specifically, we group examples whose loss gradients at the smooth convex minimizer are similar into the same client, using balanced kk-means (Section 5 and Appendix G.1 of the revision).

New partition strategy. We construct the partition once, based on the smooth convex problem, and use the same partition for all three problem classes. We measure heterogeneity by the gradient dissimilarity at the smooth convex minimizer x⋆x^\star: \zeta^2=\sum_{i=1}^m\frac{n_i}{n}\bigl\\|\nabla f_i(x^\star)-\nabla f(x^\star)\bigr\\|^2, where fif_i and ff are the client and global logistic losses (the regularizer is the same on all clients, so it does not contribute). This is the between-client part of the total spread of the per-example gradients, s2=1n∑j∣∇ℓj(x⋆)−∇f(x⋆)∣2s^2=\frac1n\sum_j\\|\nabla\ell_j(x^\star)-\nabla f(x^\star)\\|^2, so ζ2≤s2\zeta^2\leq s^2 for every partition of the same examples. We report the ratio ζ2/s2\zeta^2/s^2 below (also added to Appendix G.1 of the revision):

DataMargin-sorted round-robinBalanced kk-means
Synthetic, κ=1\kappa=11.5%16.0%
Synthetic, κ=10\kappa=101.6%21.1%
Synthetic, κ=100\kappa=1001.8%30.6%
IJCNN10.11%46.0%

The round-robin partitions are close to i.i.d. In contrast, the kk-means partitions are substantially more heterogeneous. For example, on IJCNN1, 23 of the 32 clients hold examples of a single class. With the new partitions, the conclusions of the experiments remain unchanged: the predicted rates for each problem class (1/T1/T for the two smooth classes and 1/T1/\sqrt{T} for the nonsmooth class), the benefit of more local steps under stochastic gradients, and the comparison with adaptive FL methods all remain. Theorem 4.4 does not assume bounded heterogeneity. Consistent with this, AdaFed follows the predicted rates on the strongly heterogeneous kk-means partitions, without any tuning to the heterogeneity level.


Q4.

As clarified in our response to Q1, the paper does not claim to be parameter-free. Our claim is universality: the rates of Theorem 4.4 hold for every η,γ>0\eta,\gamma>0, without knowledge of the problem class or of LL, GG, σ\sigma, or the heterogeneity level (Lines 073–079). As in centralized AdaGrad, η\eta and γ\gamma affect the constants, and hence the practical speed.

Why universality matters in practice. In general, step-size strategies designed for one problem regime may not be suitable for another. For example, constant step sizes motivated by smooth deterministic analyses (e.g.,, ∝1/L\propto1/L) may fail to converge to an exact solution on nonsmooth problems or in the presence of stochastic gradients. Conversely, diminishing step sizes motivated by nonsmooth or stochastic analyses (e.g., ∝1/t\propto1/\sqrt t) may lead to slow convergence on smooth deterministic problems, at a O(1/T)O(1/\sqrt{T}) rate instead of O(1/T)O(1/T). A universal method uses a single step-size strategy that adapts to these different regimes, recovering their standard convergence rates without prior knowledge of smoothness or noise levels. For instance, in our experiments in the nonsmooth convex regime in Figure 2, FedAdagrad, FedLADA, and FAFED saturate at an error floor, whereas AdaFed continues to decrease (Lines 429–431). Moreover, adaptive step-size strategies can potentially exploit favorable local problem structure that is not reflected in worst-case global assumptions, such as variations in smoothness or noise levels along the optimization trajectory, leading to better practical convergence.

The experiments are consistent with this scope:

  • Tuning (Appendix G.2). We fix γ=1\gamma=1, select η\eta from powers of ten at K=10K=10, and reuse it for all KK. We tuned per setting to avoid favoring any problem class, but the selected values show that a single choice works across classes. On IJCNN1, the selected value is η=10\eta=10 for all three problem classes and both oracles. On the synthetic data, it is 11 or 1010.
  • Sensitivity (Appendix G.4, Figures 5–8). For most of the tested values η∈0.1,…,1000\eta\in\\{0.1,\dots,1000\\} and γ∈0.01,…,100\gamma\in\\{0.01,\dots,100\\}, the metrics decrease over the horizon. A too large η\eta causes an initial overshoot, after which the accumulator grows and the iterates recover, whereas a too small η\eta slows progress.
  • Comparison (Appendix G.6). All methods, including AdaFed, are tuned per setting on short runs, for a fair comparison.
AuthorsOpenReview ↗

Rebuttal part 4

Q5.

We agree that the last steps of Eqs. (56) and (58)–(59), which absorb the additive constant, are not correct. However, these steps are not needed, and the claimed bounds follow with the constants carried through:

  • Eqs. (58)–(59) and the bound on RT\mathcal R_T. Eqs. (58)–(59) enter the rest of the proof only through Eq. (60), which keeps an additive constant (inherited from Eq. (57)). The subsequent self-bounding argument therefore starts from E[qT+1]≲1+E[RT2]+σT/(mK)\mathbb{E}[q_{T+1}]\lesssim1+\sqrt{\mathbb{E}[\mathcal R_T^2]}+\sigma\sqrt{T/(mK)}, as written in Eq. (60), and gives E[RT2]≲CT\sqrt{\mathbb{E}[\mathcal R_T^2]}\lesssim\mathcal C_T as stated.
  • Eq. (56) and Lemma C.2. The middle expression of Eq. (56) is sufficient: E[DT2]≲1+E[RT2]≲1+CT≲CT\sqrt{\mathbb{E}[D_T^2]}\lesssim1+\sqrt{\mathbb{E}[\mathcal R_T^2]}\lesssim1+\mathcal C_T\lesssim\mathcal C_T, since CT≥1\mathcal C_T\geq1 by definition (Eq. (3)).

We remove these steps in the revision. Lemma C.2 and Theorem C.3 are unchanged. The same point was raised by Reviewer LpTc (Q1).


References

Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs in federated learning and meta-learning. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021.

Reese Pathak and Martin J. Wainwright. FedSplit: An algorithmic framework for fast federated optimization. In Advances in Neural Information Processing Systems, 2020.

Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local SGD for heterogeneous distributed learning. In Advances in Neural Information Processing Systems, 2020.

Reviewer_LpTcOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes a new step-size scheduler for federated learning, targeting at the problem of smoothness conditions and the heterogeneous client learning. The method can converge unconditionally without the need of prior knwoledge of problem class and related parameters. Comprehensive theoretical investigations are provided with experiments on some simple tasks.

Critical strengths

The paper written is easy to follow. The problem settings are clear. The methodology is clearly stated and the background motivations are clearly discussed.

Critical weaknesses

1, The empirical experiment settings are on an old (2011) and easy (binary) task. We typically do not put federated learning under simple tasks as such tasks do not requires involving multiple clients.

2, The maths derivations have some very trivial mistakes. Seems like the authors lacks basic checks for AI generated proofs as claimed. I would post several questions in the "Questions for Authors" part.

Questions for authors

1, could you please explain more on eq (56) that E[DT2]≲\sqrt{E[D_T^2]} \lesssim 1+E[RT2]1+\sqrt{E[R_T^2]} ≲E[RT2]\lesssim \sqrt{E[R_T^2]}. First, neglecting the term 1 is problematic. Second, there is a trivial couterexample when the update on each step xt+1−xtx_{t+1}-x_t follows the same direction, as
DT=max⁡1≤t≤T+1∥xt−x⋆∥2D_T=\max_{1\le t\le T+1}\|x_t-x^\star\|^2 \qquad RT=∑t=1T∥xt+1−xt∥2.R_T=\sum_{t=1}^T\|x_{t+1}-x_t\|^2.

2, could you please identify that why the Θ≤1\Theta \leq 1 as in eq (13). As you cite �0��0�, but Θ=(1+Lτq1)K−1\Theta = \left(1+\frac{L\tau}{q_1}\right)^{K-1} cannot be guaranteed less than zero under existing assumptions.

3, why the noise σ\sigma term is dropped in some derivations such as term B~\tilde{B} ≲K−1\lesssim K-1 in eq (13). As noise terms in federated learning are essential and cannot be rudely dropped.

4 comments
AuthorsOpenReview ↗

Rebuttal part 1

Thank you for your review. We provide our responses to the weaknesses and questions 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.


W1.

The paper solves an open problem in the adaptive FL literature as we described in the Introduction. In centralized optimization, AdaGrad-type methods have universal convergence guarantees, meaning that a single update rule attains the rates of smooth and nonsmooth problems without knowing the problem class or its parameters (Lines 042–048). No counterpart exists in adaptive FL. Existing adaptive FL methods are analyzed for specific problem classes, and some require knowledge of smoothness parameters (Lines 049–060, 135–140). Our paper specifically closes this gap (central question in Lines 061–063). We made no claim of state-of-the-art empirical performance; the stated purpose of the experiments is to examine adaptation to the problem class, as predicted by the theory (Lines 361–364).

To this end, each test problem must provably belong to one of the three classes, and verifying the predicted rates (1/T1/T vs. 1/T1/\sqrt{T}) requires knowing F⋆F^\star to high accuracy. Regularized logistic regression meets both requirements. Deep networks are typically nonsmooth and nonconvex, a class for which neither our theory nor any adaptive FL method in our comparison (Appendix H) has guarantees.

Logistic regression is a standard test problem in the adaptive FL literature. It is used in FedOpt (Reddi et al., 2021), FedSPS (Mukherjee et al., 2023), and FedUR (Zhang et al., 2023), just to name a few. FedSPS also uses the same IJCNN1 dataset.


W2.

Thank you for pointing these out. None of them is foundational, and most of them were introduced while we were simplifying and condensing our original proofs for the submission.

The points raised in Q1-Q3 are

  • an additive constant absorbed without explicit justification in Eq. (56) (and likewise in Eqs. (58)–(59)),
  • a typo in the definition of the constant Θ\Theta (τ\tau instead of τ/(K−1)\tau/(K-1)) in Line 837,
  • and a σ\sigma-dependence suppressed in places such as B~\widetilde B in Eq. (13).

Each is corrected in the revision (marked in blue), with details in the responses below. We also rechecked all proofs and corrected further minor inaccuracies of similar kind. None of these corrections changes the algorithm, the assumptions, or the statements of the theorems.

AuthorsOpenReview ↗

Rebuttal part 2

Q1.

We agree that the last step in Eq. (56) and the last steps of Eqs. (58)–(59), 1+E[RT2]≲E[RT2]1+\sqrt{\mathbb{E}[\mathcal R_T^2]}\lesssim\sqrt{\mathbb{E}[\mathcal R_T^2]} are not correct. However, these steps are not used anywhere in the proof:

  • Eq. (60), which is what the rest of the proof uses, keeps an additive constant (inherited from Eq. (57)). So the subsequent bound E[RT2]≲CT\sqrt{\mathbb{E}[\mathcal R_T^2]}\lesssim\mathcal C_T is unaffected by the last steps of Eqs. (58)–(59).
  • Lemma C.2 follows from the middle expression of Eq. (56): E[DT2]≲1+E[RT2]≲1+CT≲CT\sqrt{\mathbb{E}[D_T^2]}\lesssim 1+\sqrt{\mathbb{E}[\mathcal R_T^2]}\lesssim 1+\mathcal C_T\lesssim\mathcal C_T, since CT≥1\mathcal C_T\geq1 by definition (Eq. (3)).

In the revision, we remove these steps. We also make explicit the σ\sigma-dependence hidden in the constant (cf. Q3): ∑tβt≲1+σ2\sum_t\beta_t\lesssim1+\sigma^2, so Eq. (56) reads E[DT2]≲1+σ2+E[RT2]\sqrt{\mathbb{E}[D_T^2]}\lesssim1+\sigma^2+\sqrt{\mathbb{E}[\mathcal R_T^2]}, and 1+σ21+\sigma^2 replaces 11 in Eqs. (58)–(60). The additional σ2\sigma^2 is absorbed since CT≥1+σ2\mathcal C_T\geq1+\sigma^2. Lemma C.2 and Theorem C.3 are unchanged.

The counterexample. Eq. (56) is derived for the iterates of AdaFed from the recursion in Eq. (53), which relies on convexity through Eq. (49). Your claimed counterexample is not valid since it contradicts these underlying assumptions. A sequence of identical nonzero steps violates Eq. (53) for large tt, and hence is not a valid AdaFed trajectory on a convex problem. Indeed, if rt=v≠0r_t=v\neq0 for all tt, then ζt=0\zeta_t=0 and dt=d1+(t−1)vd_t=d_1+(t-1)v, and since ∣dt+1∣2=∣dt∣2+2⟨v,dt⟩+∣v∣2\\|d_{t+1}\\|^2=\\|d_t\\|^2+2\langle v,d_t\rangle+\\|v\\|^2 and F(xt)≥F⋆F(x_t)\geq F^\star, Eq. (53) requires 2⟨v,dt⟩≤αt∣dt∣2+βt2\langle v,d_t\rangle\leq\alpha_t\\|d_t\\|^2+\beta_t. The left-hand side grows as 2t∣v∣22t\\|v\\|^2, whereas αt∝τt2\alpha_t\propto\tau_t^2 and βt∝τt2\beta_t\propto\tau_t^2 with τt≲t−p\tau_t\lesssim t^{-p}, p>1/2p>1/2, so the right-hand side grows at most as t2−2p=o(t)t^{2-2p}=o(t) (for K=1K=1, αt=βt=0\alpha_t=\beta_t=0).


Q2.

This is a typo in the definition of Θ\Theta: τ\tau should be τ/(K−1)\tau/(K-1). For K≥2K\geq2, the schedule in Eq. (12) gives τt≤τ/(K−1)\tau_t\leq\tau/(K-1), and the correct definition is Θ:=(1+Lτ(K−1)q1)K−1≤exp⁡(Lτq1)≲1,\Theta:=\left(1+\frac{L\tau}{(K-1)q_1}\right)^{K-1}\leq\exp\left(\frac{L\tau}{q_1}\right)\lesssim1, which is consistent with the justification after Eq. (13), (1+1/t)t≤e(1+1/t)^t\leq e.

Θ\Theta is used only to bound the factors (1+Lτt/qt)s(1+L\tau_t/q_t)^s, 0≤s≤K−10\leq s\leq K-1, that arise from unrolling the KK local steps. Accordingly, the bound τt≤τ\tau_t\leq\tau is replaced by τt≤τ/(K−1)\tau_t\leq\tau/(K-1) in Eqs. (18) and (33) and in the constants R0,R1R_0,R_1 of Lemma B.2. With this replacement, the factor 1+(K−1)LτΘ/(2q1)1+(K-1)L\tau\Theta/(2q_1) in Eq. (32) becomes 1+LτΘ/(2q1)1+L\tau\Theta/(2q_1), and R0R_0, R1R_1, and this factor are bounded independently of KK, as used in the proofs. No other step or result changes.


Q3.

No noise term is dropped from the convergence rates. The leading noise contribution 2σ2/(mK)2\sigma^2/(mK) in Eq. (16) is kept exactly through Eqs. (46)–(47), and it gives the term σCT/mKT\sigma\mathcal C_T/\sqrt{mKT} in Theorems B.4 and 4.4. The σ\sigma-dependence of the factors UT\mathcal U_T, CT\mathcal C_T, VT\mathcal V_T in Eqs. (3)–(4) is also explicit.

What was simplified is the constant B~\widetilde B in Eq. (13). From its definition, B~≲(K−1)(1+σ)\widetilde B\lesssim(K-1)(1+\sigma), and we now state this reasoning explicitly in the revision. B~\widetilde B enters the analysis only through B~2T~T≲1+σ2,B~T~T≲1+σ,\widetilde B^2\widetilde{\mathcal T}_T\lesssim1+\sigma^2,\qquad \widetilde B\sqrt{\widetilde{\mathcal T}_T}\lesssim1+\sigma, using T~T≲1/(K−1)2\widetilde{\mathcal T}_T\lesssim1/(K-1)^2 from Eq. (13). These appear only as additive terms in Lemma B.1, in Eqs. (31)–(32), and in the constant c1c_1 of Eq. (41). They are dominated by factors present in the bounds, since CT≥1+σ2\mathcal C_T\geq1+\sigma^2 and UT≥(1+σ2)/2\mathcal U_T\geq(1+\sigma^2)/2. (For the latter, let a:=σ2(1+log⁡(mKT))a:=\sigma^2(1+\log(mKT)); then alog⁡(1+a)≥a2/(1+a)≥a−1a\log(1+a)\geq a^2/(1+a)\geq a-1, so UT≥1+alog⁡(1+a)≥max⁡1,a≥(1+a)/2\mathcal U_T\geq1+a\log(1+a)\geq\max\\{1,a\\}\geq(1+a)/2.)

Hence Eq. (43), E[qT+1]≲UT\mathbb{E}[q_{T+1}]\lesssim\mathcal U_T, and the bounds E[GT]≲CT\mathbb{E}[\mathcal G_T]\lesssim\mathcal C_T, E[GT2]≲CT\sqrt{\mathbb{E}[\mathcal G_T^2]}\lesssim\mathcal C_T hold as stated, and Theorem B.4 is unchanged. The same applies to the constant ∑tβt\sum_t\beta_t in the smooth convex case (see our response to Q1).

Thank you for the detailed responses and the revised manuscript. I have checked the revised proofs against the points raised.

On Q1–Q3. I verified the corrections: with τt≤τ/(K−1)\tau_t\le\tau/(K-1), the constant Θ≤eLτ/q1\Theta\le e^{L\tau/q_1} is independent of KK, the additive 1+σ21+\sigma^2 is now kept in Eqs. (56)–(60); and the σ\sigma-dependence of B~\widetilde B and c1c_1 is dominated by CT≥1+σ2\mathcal C_T\ge 1+\sigma^2 and UT≥(1+σ2)/2\mathcal U_T\ge(1+\sigma^2)/2. I agree that the middle inequality of Eq. (56) follows from the recursion (53) and is not affected by my same-direction example.

However, I do not agree that Q2 is a typo: in the original version, Eqs. (18), (32), (33) and R0,R1R_0, R_1 were all derived with τt≤τ\tau_t\le\tau, consistently with the KK-dependent Θ\Theta, so the claimed KK-independence of the constants was unsupported.

Concern of revisions with other content Beyond Q1–Q3, the revision has many changes about 30 places, please provide a complete list of changes and dependencies for each whether it affects a lemma statement or an experimental setting. As for the time limit, AI tools is allowed (and encouraged as it is useful in such tedious checking work) as long as the dependencies are manually checked.

Remaining issues in the revised version.

I read more content in the proof and find at least three more problem (not limited to the three possible)

  1. Lemma E.3, Eq. (88): averaging the distance bound over kk only gives ∥gˉt(i)∥≤(1+(K−1)LΘτt/(2qt))∥∇Fi(xt)∥\|\bar g_t^{(i)}\|\le\big(1+(K-1)L\Theta\tau_t/(2q_t)\big)\|\nabla F_i(x_t)\|, which can exceed Θ\Theta (e.g., K=2K=2 and L/q1=2L/q_1=2 give 4>Θ=34>\Theta=3). The claim does hold via ∥∇Fi(xi,k+1t)∥≤(1+Lτt/qt)∥∇Fi(xi,kt)∥\|\nabla F_i(x_{i,k+1}^t)\|\le(1+L\tau_t/q_t)\|\nabla F_i(x_{i,k}^t)\|, but the stated argument does not establish it.
  2. Several self-bounding steps (Eqs. (42), (47), (56), (100), (104), (106) and Lemma D.3) rearrange E[qT+1]\mathbb E[q_{T+1}], E[qT+12]\mathbb E[q_{T+1}^2], E[DT2]\mathbb E[D_T^2] or E[(ZT∗)2]\mathbb E[(\mathcal Z_T^*)^2] without first showing that these quantities are finite.
  3. Assumption 4.2 says the noise variables are "conditionally independent" without specifying the conditioning. Within a client the noises are generally not independent.The proofs only use the martingale-difference property and conditional independence across clients given Ft\mathcal F_t (Eqs. (15) and (34)). Please state precisely what is assumed.

Thus I would remain my score as clear reject, as a formal published paper should not contains so many factual error in maths proofs, and it is irresponsible to let the reviewers help to check the errors in AI generated proof.

Thank you for checking the revised proofs and for confirming the corrections for Q1–Q3.

On Q2. This issue was introduced by a change of notation when we extended the analysis and then propagated a few steps. The earlier version of our analysis treated KK as a constant. To show that multiple local steps improve the noise term in the stochastic setting, we later made the dependence on KK explicit and rewrote the schedule as τt≤τ/((K−1)tp)\tau_t\leq\tau/((K-1)t^p) with a free constant τ\tau. However, we did not update Θ\Theta and the bounds that use τt≤τ\tau_t\leq\tau accordingly. This is why the same issue appears in Eqs. (18), (32), (33), R0R_0, and R1R_1, and why the justification after Eq. (13), (1+1/t)t≤e(1+1/t)^t\leq e, only works with τ/(K−1)\tau/(K-1). The justifications in the text reflect the definition we had in mind with τ/(K−1)\tau/(K-1), while the definition of Θ\Theta in the paper was not updated. Replacing τ\tau by τ/(K−1)\tau/(K-1) fixes all of them; the fix is local and requires no new argument. Only constants in auxiliary lemmas used in the analysis (e.g., R0R_0 and R1R_1 in Lemma B.2) change; none of the theorem statements changes, and hence neither do the claimed contributions. This is why we considered it a notational issue.

On the list of changes. All changes are marked in the revision. None of the main claims, theorem statements, or algorithmic definitions has changed. The experimental changes are limited to the following:

  • The margin-sorted round-robin partition is replaced by a strongly heterogeneous partition, to make the tests harder. The qualitaive conclusions of the experiments have not changed, but now they are tested in a more challenging setting.
  • The number of random seeds is increased from 10 (rate studies) and 3 (method comparisons) to 20. The number of seeds were small previously due to time constraints.
  • The method-comparison figures (e.g., Figure 2) now show error bands as well, which was not possible with 3 runs before. So previously we had them only for the rate study figures.

Algorithms, problems, metrics, and tuning protocols are unchanged; all experiments were rerun following the exact same protocol as in the original submission, with the three changes liseted above.

We added a discussion in the appendix quantifying the heterogeneity of the client partitions. This is just a further insight about the hardness of the problem setting, provided in the appendix. It has no affect on the experiment procedure.

On the three new points.

  1. Lemma E.3, Eq. (88). We agree that our one-line justification might be too brief. Applying smoothness step by step along the local path gives ∥∣∇Fi(xi,k+1t)∥∣≤(1+Lτt/qt)∥∣∇Fi(xi,kt)∥∣\||\nabla F_i(x_{i,k+1}^t)\||\leq(1+L\tau_t/q_t)\||\nabla F_i(x_{i,k}^t)\||, hence ∥∣∇Fi(xi,kt)∥∣≤Θ∥∣∇Fi(xt)∥∣\||\nabla F_i(x_{i,k}^t)\||\leq\Theta\||\nabla F_i(x_t)\|| for all k≤K−1k\leq K-1 and ∥∣gˉt(i)∥∣≤Θ∥∣∇Fi(xt)∥∣\||\bar g_t^{(i)}\||\leq\Theta\||\nabla F_i(x_t)\||. We now write this out; the lemma is unchanged. Thank you for the suggestion.
  2. Finiteness in the self-bounding steps. We agree. We will add these clarifications about the terms being finite, hence reordering works, in the camera-ready. We could not add them to the revision now due to time constraint. Thank you for the suggestions.
  3. Assumption 4.2. We agree that an explicit specification is important to avoid any misunderstanding, we have now updated it.

On the use of AI. We object to the repeated suggestion by the reviewer that the proofs are unchecked AI output. This is not the case. The theoretical framework, algortihm idea and derivation, the proof strategy, all the main proof steps, and the main claims of the paper were developed by the authors, and in fact arise from their prior work and experience on the subject. AI tools were used locally, to work out individual steps that adapt known arguments to our setting, to explore candidate counterexamples, and to simplify and condense the analysis, and the authors checked every such step. Our AI-use statement discloses this use as required by the ICLR policy. We are quite disturbed by the reviewer's repeated accusations suggesting as if the proofs were largely produced by AI, they are not. Most of the issues raised above by the reviewer are not related to the AI use, but arised during our manual writings and edits.

We thank the reviewer for their effort, but we respectfully disagree that any of the issues raised are critical or suggests a clear reject. All of them are easy to fix, none of them changes the main claims or the results of the paper. We respect the ICLR evaluation process and will accept the outcome. However, we strongly object to the unsupported accusations of irresponsible AI use. These allegations go beyond legitimate scientific criticism.

Respectfully,

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.