Efficient Adaptive Federated Optimization
Authors: Su Hyeong Lee
Sidharth Sharma
Manzil Zaheer
Tian Li
Venue: NeurIPS 2025 poster ()
Keywords: federated optimization
communication- and memory-efficiency
adaptivity
Primary area: optimization

Abstract: Adaptive optimization is critical in federated learning, where enabling adaptivity on both the server and client sides has proven essential for achieving optimal performance. However, the scalability of such jointly adaptive systems is often hindered by resource limitations in communication and memory. In this paper, we introduce a class of efficient adaptive algorithms, named $FedAda^2$ and its enhanced version $FedAda^2$++, designed specifically for large-scale, cross-device federated environments. $FedAda^2$ optimizes communication efficiency by avoiding the transfer of preconditioners between the server and clients. Additionally, $FedAda^2$++ extends this approach by incorporating memory-efficient adaptive optimizers on the client side, further reducing on-device memory usage. Theoretically, we demonstrate that $FedAda^2$ and $FedAda^2$++ achieve the same convergence rates for general, non-convex objectives as its more resource-intensive counterparts that directly integrate joint adaptivity. Extensive empirical evaluations on image and text datasets demonstrate both the advantages of joint adaptivity and the effectiveness  and efficiency of $FedAda^2$/$FedAda^2$++.

Efficient Adaptive Federated Optimization
Su Hyeong Lee Department of Statistics University of Chicago
Sidharth Sharma
Manzil Zaheer" Google DeepMind
Department of Computer Science Columbia University
Tian Li
Department of Computer Science University of Chicago
Abstract
Adaptive optimization is critical in federated learning, where enabling adaptivity on both the server and client sides has proven essential for achieving optimal performance. However, the scalability of such jointly adaptive systems is often hindered by resource limitations in communication and memory, In this paper, we introduce class of efficient adaptive algorithms, named FedAda" and its enhanced version FedAda 2 designed specifically for large-scale, cross-device federated environments. FedAda² optimizes communication efficiency by avoiding the transfer of preconditioners between the server and clients. Additionally, FedAda extends this approach by incorporating memory-efficien adaptive optimizers the client side, further reducing on-device memory usage. Theoretically, we demonstrate that FedAda and FedAda achieve the same convergence rates for general, non-convex objectives as its more resource-intensive counterparts that directly integrate joint adaptivity. Extensive empirical evaluations on image and text datasets demonstrate both the advantages of joint adaptivity and the effectiveness and efficiency of
Introduction
Federated learning is distributed learning paradigm which aims to train statistical models across In vanilla federated learning, central server orchestrates the training process by distributing the global model subsample of thousands even millions of clients. These clients collaboratively perform local stochastic gradient descent while drawing from their private data streams. After several epochs have elapsed, each client communicates their aggregate updates to the server, which averages this information to make an informed adjustment to the global model. This algorithm, using non- non-adaptive weight updates, is called FedAvg (I]. A recent trend is to investigate utilizing adaptive optimizers to support federated learning 4 Adaptivity can be employed in either the server-side or the client-side, where joint adaptivity (consisting of global and local adaptive updates) has been shown to play a pivotal role in accelerating convergence and enhancing accuracy [5 6).
multiple clients while minimizing raw data exposure 1
2 3
Nevertheless, efficiency challenges remain for the successful deployment of jointly adaptive al- gorithms in practice, especially in cross-device federated settings 77. The server, which collects pseudogradients pushed by participating clients, consolidates global approximation of the precondi- tioners for adaptive model updates. Typically, the server sends the preconditioners back to the clients to precondition local adaptive updates. However, this can lead to significant communication overhead that detracts from the advantages offered by adaptivity [8] Furthermore, dynamically varying client
* Work done while Google DeepMind.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

resource limitations restrict the reliability of client-side adaptive optimizers in practice, especially when additional memory required for handling local preconditioners during each client model update.
In this work, we propose class of efficient jointly adaptive distributed training algorithms, called FedAda" and FedAda"++, to mitigate the aforementioned communication and memory restrictions while retaining the benefits of adaptivity, FedAda maintains an identical communication complexity as the vanilla FedAvg algorithm. Instead of transmitting global server-side preconditioners from the server to the selected clients, we propose the simple strategy of allowing each client to initialize local preconditioners from constants such as zero, without any extra communication of preconditioner"" FedAda ++ expands on this approach by adopting existing memory-efficiien optimizers that factorize gradient statistics to reduced dimensions in order to save on-device memory when synthesizing achieve
local updates. We prove that for the general, non-convex setting, FedAda² and FedAda aa "aaddda the same convergence rate as prior adaptive federated optimizers (e.g.. 4 Conclusively, we aim to demonstrate that jointly adaptive federated learning, as well as adaptive client-side optimiza- tion, are practicable in real-world settings while sidestepping localized memory restrictions and communication bottlenecks with minimal performance degradation.
Our contributions may be summarized as follows.
Motivated by the importance of joint server- and client-side adaptivity, we propose FedAda and FedAda ++ to avoid extra communication cost and reduce on-device memory while retaining the benefits of joint adaptive optimization (Section 3).
We provide convergence analyses for a class of FedAda'/FedAda"** algorithms instantiated with different server- and client-side adaptive methods and semorry-efficiee local optimizers (Section 4
Empirically, we show that FedAda (aliddaFFeddaa+*ee ++, without transmitting preconditioners and em- ploying on-device preconditioner compression, matches the performance of its more expensive counterparts, and outperforms baselines without joint adaptivity on both image and text datasets (Section 5)
2
Related Work
We now provide a brief overview of related work in adaptive federated learning and memory-efficien' preconditioning.
Adaptive Federated Optimization. Adaptive optimization preconditions the gradients to enhance optimization efficacy, dynamically adjusting the learning rate for each model parameter [c.g... 2 10
[1]. Recent developments in federated learning have leveraged adaptive methods for server and client model parameter updates. Frameworks such as FedAdam 4 and FederatedAGG 12 focus primarily on server-side adaptivity while using a constant learning rate for client updates. Additionally, FedCAMS []] delves into commumication-effiee -efficienn adaptive optimization by implementing error feedback compression to manage client updates while maintaining adaptivity solely on the server side. Conversely, methodologies such as FedDA [13, FedLALR [4), Local AdaAlter [15], and Local AMSGrad [16) have adopted client-side adaptivity exclusively and demonstrate benefits. These approaches involve transmitting both client preconditioners and model parameters for global aggregation in the server. Moreover, some frameworks have embraced joint adaptivity. Local Adaptive FedOPT [5] implements joint adaptivity while incorporating an additional client correction term. These terms, along with transmitted client pseudogradients, are aggregated on the server to construct a global preconditioner used to synthesize the subsequent model update, Alternatively, frameworks such MIME [17
18 transmit additional optimizer state information aggregated
"We note that this pragmatic strategy has briefly appeared in prior work 5 before, but lacked formal convergence guarantees and was not extensively studied via thorough empirical evaluations. We include
detailed discussion in Appendix BB
'There are various notions of Tefficiency' of adaptive methods in the context of the federated learning, two of them being communication efficiency and client memory efficiency. Our contribution specifically targets reducing communication and memory costs incurred by local preconditioners which is complementary with works that reduce communication by repeated local updates or model weighrisseuooraadent compression (e.g.. FedCAMS (8) and may, in theory, even be combined. We note that such methods tend to study compression of local models for server-only adaptive optimizers. whereas our contribution lies in minimizing communication of preconditioners in jointly adaptive settings.
2

---

in the server to mimic adaptive updates in centralized settings, while maintaining frozen-state optimizers on the client-side. In contrast with all these approaches, FedAda avoids the transmission of any local/global preconditioners and optimizer states entirely, maintaining precisely identical communication complexity as vanilla FedAvg despite leveraging joint adaptivity. We include further discussions in Appendix H.5
Memory-Efficient Adaptive Optimizers. The implementation of local adaptive methods sub- stantially increases client memory requirements, as it necessitates the maintenance of local precon- ditioners. For some models, it has been noted that the gradients combined with optimizer states consume significantly more memory than the actual model parameters themselves [19] Memory- efficient adaptive optimizers have been extensively studied in prior literature. Algorithms such as Adafactor (20] address memory reduction by tracking moving averages of the reduction sums of squared gradients along a singular tensor axis, attaining low-rank projection of the exponentially smoothed preconditioners. GaLore [21] targets the low-rank assumption of the gradient tensor, which reduces memory of both gradients and preconditioners. Shampoo [22] collapses gradient statistics into separate preconditioning matrices for each tensor dimension, which is extended via extreme tensoring [23. In this paper, we focus on SM3 [2 in our implementation and experiments due to its empirical performance; however, theoretical framework covers broad class of memory--ficcient optimizers applied on the client-side (Section and Appendix[E)
FedAda?: Efficient Joint Server- and Client-Side Adaptivity
In federated learning, typical server-side objective is formed by taking average of all client objectives Fz(z) for 2 E [N] and x E Rº:
f(z) N Σ F((z).
(1)
In the case of unbalanced client data sizes or sampling probabilities, the objective becomes Ein (z) on the right hand side where Pt is proportional to the local data size of client i, or the sampling probability. With slight abuse of notation, we denote Fi()) = E.-D, [Fe =)] where F2 2) the stochastically realized local objective and D; the data distribution of client i. The convergence analysis developed in Section holds when D; is taken to be the local population distribution, as well as when D, is the local empirical distribution.
A key characteristic of cross-device federated settings is that clients cannot store or maintain "states' across communication rounds (7. To facilitate joint adaptivity in stateless federated systems, natural baseline is to estimate pseudogradient statistics on the server (i.e., maintaining server-side or global preconditioners). which are then transmitted to all participating clients at each communication round. Selected clients then perform local adaptive updates using preconditioners initialized from the global values. While this allows clients leverage global preconditioner information for local model adjustments, transmitting global pseudogradient statistics, such as second moments, at every round substantially increases communication costs. On the other hand, warm-starting from previously stored preconditioners may not be beneficial, especially when the interval between consecutive rounds involving the same client is large so that the preconditioners can be very stale. Additionally, performing local adaptive updates induces client-side memory overhead. In the following, we discuss two key techniques for efficient federated adaptive optimization with convergence guarantees.
Zero Local Preconditioner Initialization. To enhance the fcasibility of jointly adaptive federated learning in cross-device settings, we first address extra major communication bottlenecks brought by transmitting global preconditioners from the server to subset of clients. We propose simple strategy of uniformly initializing local preconditioners to zero (or some constant vector) at the beginning of each training round, thus eliminating the need for preconditioner transmission.
To describe the process in more detail, assume Adagrad (with momentum) as the server-side op- timizer 4 for illustration purposes. We have the following server update rule (SU) for - the accumulated pseudogradient from client at step 1,
A |st Σies AS
m 1-m--1 (1 3))
0 ū + 42
34 I4-1 + Vo.tr
m.
(SU)
3

---

Here, 0n is the sum of squared server-side pseudogradient - As. and 31 is the momentum coefficient controlling the moving average m, of - The set S; C [M] gives the index of all participating clients at round I, and r is constant. An extension to the case when Adam is selected as the server optimizer is given Appendix D.2 After obtaining an updated global preconditioner it at each communication round, in FedAda", the server does not communicate i) to the participating clients. Instead, each client only receives 2, and initializes the local preconditioners from zero. Empirically, we demonstrate this simple strategy does not degrade the performance relative to the alternative of transmitting global preconditioners, while being significantly more communication efficient for adaptive methods beyond AdaGrad (Section 5.1 In addition to communication reduction, this approach enables the use of different optimizers on the server and clients, as the server and client can maintain independent gradient statistic estimates. We further discuss the theoretical guarantees as well as implications of this general framework in Section 4 and Appendix
Addressing Client-Side Resource Constraints. To accommodate local memory restrictions, we further employ existing memory- eefeor--fffcieet optimizers for all clients in FedAda Our framework allows any such optimizer be used, including a heterogeneous mixture within each communication round. We provide convergence guarantee for very broad class of optimizer strategies in Theo- rem 4.1 We note that order for convergence to be guaranteed, the memory-efficient optimizer must satisfy the conditions of Theorem E.1 which are non-restrictive' The FedAda framework summarized in Algorithm [ below, presented in a simplified form. Local statistics or global statistics refer to those used to construct preconditioners (e.g., first or second moment), and selecting a memory-efficient optimizer strategy gives FedAda?++.
Algorithm 1 FedAda?: Efficient Jointly Adaptive Optimization Framework (Simplified)
Require: Initial model zo. total number of clients N
1: for 1= 1,..,, T do
2: Sample client subset St C [N]
3: for each client E St (in parallel) do
4: <t,0 + -1-1
5:
local statistics + 0
6:
for k = 1,.... K do
7:
Draw gradient ki,kk ~ Diag k1)
8:
"i, + adtap_Ot.(="..e.. Lh pocal_statisticys (FedAda+++; memory-efficient Adap_Opt.)
9:
end for
11: A ===1,, Tt-1
12:
end for
x' Adap Sptp__Ott((L (f global_ statistics) (for example, Eq. (SU)
end for
During implementation, we have chosen to instantiate FedAda2++ with SM3 adaptations of Adam and Adagrad as the memory-efficient local optimizers (Appendix [c due to its strong empirical performance. Intuitively, SM3 exploits natural activation patterns observed in model gradients to efficiently synthesize low-rank approximation of the preconditioner. It maintains the statistics in the granularity of parameter groups instead of individual coordinates. Our analyses in Section 4 hold for class of memory-efficient local optimizers. Due to the highly technical nature of its implementation and the convergence analysis, specific algorithm design details and proofs have been relegated to Appendix D for interested readers only. Our convergence analysis further accounts for the of delayed preconditioner updates, where clients update their second-moment gradient statistics after every z minibatch backpropagations, introducing a z-step delay (see Algorithm 2 Appendix J.3
4 Convergence Analyses
One of the challenges in proving the convergence bound for jointly adaptive systems lies in handling client-side adaptivity with multiple local updates. The individual gradients may not be linearly sepa-
'It can easily be shown that Adam, AdaGrad. SGD, well as their memory efficient counterparts [24] for the first two, all satisfy the optimizer conditions for guaranteed convergence.

---

rable due to dependencies between historical client gradients in the local model updates. Furthermore, the combination of server- and client-side adaptivity complicates analysis relative to prior works focusing on only server-side only client-side adaptivity. To address these issues, we assume access to full batch client gradients, but allow for client partial participation.
Assumption (L-Smoothness)) The local objectives are L-smooth and satisty [[) (.(())) & L|| yll for all z; y E & and i [M].
Assumption (Bounded Gradients). The full gradient of the local objective is bounded: [VR(())) < G for j E [4], i E [M].
We note that although we assume a uniform upper bound on the full batch gradient (as opposed to stochastic gradients) for the convergence results to hold. These assumptions are standard within
the literature and have been used in previous works [5 25 26]. In particular, this delineates an L-Lipschitz family of objectives given that the arguments are ye5,-boundde away from each other,
[V V1J(I)I < D| - wll 2VdG
nes || yl
for j E [A] and || vl 2 C- Here, e, is an epsilon smoothing term that activates on the client side and ni is the local learning rate. This quantity used in a gradient clipping step in FedAda (full version Algorithm(5) where if the local gradient update is negligibly small in magnitude, then the gradient is autonomously clipped 0. vi > 0 is the local learning rate, and in particular, we note that T, @(n=') By taking es- -> 0, our algorithm recovers federated algorithms that do not utilize local gradient clipping. The definition the clipping threshold is purely for analytical purposes; in our experiments, we take E, to be a negligible value so that my is not set to O.
We now provide a convergence bound for the general, non-convex case under local gradient descent and partial client participation. The full theorem statement is provided in Appendix D as Theorem E. The SM3 instantiation of FedAda ++, as well as the generalization to the case where we use Adam as the server/client optimizers are provided in Appendices D.I and D.2, We note that the convergence bounds are derived for the deterministic setting. Extending the analysis to stochastic regimes and establishing analogous guarantees is a natural direction for future work.
Theorem 4.1 (Simplified). Under Assumptions I and 2 as well as some non-restrictive optimizer update conditions (Theorem E. for any choice of initialization Ho, Algorithm 7 satisfies
V1 + U2 + U + V, + Us
T
V/6
where asymptotically,
1 01=0(1), 122 = = Vs = I, Ws
mme log(l + +Tn?),
and
''ेTTT if O(m) - O())
(mET if O(T - 011)
15
TET if O(m) > 211) =-= = IIVTT if @(TT 2(1)
We defer the detailed proofs and complete statement of the bounds Appendix D and E A key theoretical insight in our work is that the benefits of joint adaptivity can be retained even without transmitting preconditioners. The condition O ((1) refers to learning rates that are asymptoti- cally constant or decaying with T, e.g., 1// = 1/T. etc. Our convergence allows for delayed preconditioner updates. In Lemma D.I in the appendix, we observe that a larger decay parameter can potentially slow down convergence. Empirically, the performance is robust to the choice of z (Appendix (.3). We make other assumptions on local or global learning rates (1) and 17) to extract the most general use of Theorem 4.1 We have the following two corollaries.
Corollary 4.2. Any of the following conditions are sufficient to ensure convergence of Algorithm 7
(A): He S (T- for 2(T < mh < 0(1)
(B): : Te = O 1 for 2(T < 7 < O)
Corollary 4.3. Algorithm converges at rate 11221
5

---

Discussions of Convergence Bound. There have been several recent works exploring adaptivity and communication efficiency in federated learning. The convergence rate in Corollary 4.3
matches
the state-of-the-art for federated non-convex optimization methods 44 8 12 14 15
16
However,
to the best of our knowledge, there are no known convergence results of jointly adaptive federated optimization that explicitly support several popular methods including Adam and AdaGrad.
Importance of Adaptivity Parameters. The e-smoothing term (i.e., adaptivity parameter) is crucial for maintaining stability and ensuring convergence in adaptive optimizers. For example, PyTorch's implementation of Adam adopts 10-* 8 as its default value. our convergence bounds (c.f., Theorem E.1 full version), the smoothing term explicitly appears in the denominator on the right-hand side of the convergence result via L and Setting 0 0 causes the right-hand side of the convergence bounds to diverge, thereby undermining convergence. To address this, we ensure e 0 in our algorithm and impose the smoothing condition my > 0 in Theorem D.6 (the full version of Theorem 4.I.
Extension of FedAda": Blended Optimization. The gradient descent setting used in the analysis of Theorem 4.1 is conceptually equivalent to accessing oracle client workers capable of drawing their entire localized empirical data stream, While this constraint is a limitation of our theory, it enables us to derive stronger results and induce additional adaptive frameworks for which our analysis generalizes. For instance, our bound deterministically guarantees asymptotic stabilization of the minimum gradient, regardless of initialization or client subsampling procedure. In Appendix [E] we extend the FedAda² framework to even more general framework of federated blended optimization.
Blended optimization distributes local optimizer strategies during the subsampling process, which are formalized as functions that take as input the availability of client resources and outputs hyperpa- rameters such as delay step size or choice of optimizer (Adam, AdaGrad, SGD, etc). These may be chosen to streamline model training based on variety of factors, such as straggler mitigation or low availability of local resources. In particular, this framework permits the deployment of different adaptive optimizers per device for each round, enhancing the utility of communication-efficcaa frameworks that do not retain preconditioners between clients or between the server and client. This flexibility is especially beneficial in scenarios where there is non-uniformity between server and client adaptive optimizer choices, or between client-side optimizers.
Empirical Evaluation
In this section, we empirically demonstrate the performance of FedAda'/FedAda"* compared with several baselines that are either non-adaptive or adaptive but inefficient. We first present our main results by comparing different instantiations of FedAda? with more expensive jointly adaptive baselines and non-jointly adaptive methods in Section [.1]] We then investigate the effects of hyperparameters in more detail in Section We repeat every run for 20 times under different random seeds for statistical significance, and report 95% confidence intervals as shaded error regions in all plots. Our experiments are designed to reflect memory- and communication-constaaiii scenarios, and we thoroughly demonstrate that our algorithms retain strong convergence behavior in such environments.
Evaluation Setup. We explore the impact of adaptivity on both text and image datasets, i.e.,
StackOverflow (27). CIFAR-100 (28). FEMNIST (29), and GLD-23K [30]. In StackOverflww each client single user posting on the StackOverflow website. For images, we explore vision transformer models (VTT-S (31) which are pretrained on ImageNet-21K (32) and finetune them the
Google Landmarks dataset 330. This represents a domain shift onto natural user-split pictorial data. We use the same model on the CIFAR-100 dataset (28), where we partition the data using LDA (33 with a = 0.001, a non-lII statistical topic modeling algorithm. To assess the performance of all algorithms in additional realistic heterogencous federated learning scenario, further utilize FEMNIST (29 where each client is an individual writer. This setup evaluates federated learning algorithms under non-IlI conditions, highlighting challenges such personalization and robustness to client heterogeneity. Details for federated dataset statistics, learning tasks, and hyperparameter tuning provided in Appendix[]
Description of Baselines. Throughout this section, we compare with the following baselines. FedAvg is the vanilla FL algorithm introduced in McMahan et al. [. without any additional

---

momentum for the server-side aggregation. FedAdaGrad or FedAdam are two examples of server- only adaptive federated optimization methods [4] where the server-side model updates are performed by an adaptive optimizer (e.g., AaGGrad/Admm) instead of vanilla averaging. 'Costly Joint Adaptivity' (named Costly Joint Adap. in the captions) indicates a jointly adaptive training regimen, where server-side preconditioners are transmitted to clients at every communication round. For instance, we may denote one such setup as MaaGrrad-AaGraad where server-side AdaGrad preconditioners are distributed to the client-side AdaGrad optimizers for local preconditioner initialization. Removing server-side preconditioner transmission and using zero initialization of client-side preconditioners naturally results in corresponding instantiation of FedAda", which is ceammmiiaatio-fffciine Further compressing the local preconditioners using SM3 [24] to account for client memory resource limitations gives FedAda ++ Therefore, the basclines and FedAda" //ee/daa ++ may be viewed as natural and well-motivated variations via the addition of jointly adaptive updates and memory-efficient optimizers.
5.1 Empirical Performance of FedAda and FedAda
CIFAR-100
GLD-23K
FEMNIST
Test Accuracy
Test Accuracy
Test Accuracy
Fublog
Pedios
646-
646-
044
Pedkda...
Packda'..
dn
Communication Rounds
Communication Rounds
Communication Rounds
CIFAR-101 100
GLD-233 23K
FEMNIST
Falfay
Fiiliag
Feiling
TaKLIGu
1:12
FalMdan
Feskdam
Feshhem
Test Loss
Datly Aon Ala
Test Loss
Coidy Join Adaa
Test Loss
Cardl Jel Adia
Tickge
2004
4.50
0.72
200
130
Communication Rounds
Communication Rounds
Communication Rounds
Figure 1: (Top) Test accuracies on CIFAR-100, GLD-23K, and FEMNIST datasets. If not otherwise specified, CIFAR-100 and GLD-23K use Adam for adaptivity. We see that jointly adaptive algorithms demonstrate improved performance over FedAvg and server-only adaptive systems. Furthermore, curtailing global preconditioner transmission in FedAda /FeAdda does not degrade performance, and preserves the benefits of joint adaptivity while maintaining efficiency. (Bottom) Corresponding test losses resultant from model training on the three datasets.
2 and FedAda for Training Transformers. We investigate the performance of finetuning vision transformer models (ViT-S (31]) on image data. For all runs on the CIFAR-100, FEMNIST, and GLD-23K datasets, we select Adam as the adaptive optimizer instantiation, except for the FedAdaGrad baseline. For CIFAR- 100 (Figure leftmost column), jointly adaptive and server-only adaptive methods (FedAdaGrad and FedAdam) converge faster and achieve higher accuracy than FedAvg. Methods utilizing joint adaptivity. including FedAda", show slightly faster convergence than FedAdam. While 'Costly Joint Adap.' attains similar performance to FedAda?++, the latter is much more memory and communication efficient. Similar trends are observed on GLD-23K (middle column). The superior performance of jointly adaptive methods are especially pronounced for FEMNIST (rightmost column), where significant gap can be observed between non-adaptive FedAvg, server-only adaptive FedAddam/FedAdaGraad, and the jointly adaptive FedAda2/FedAda respectively. Additionally, in Appendix C. incorporate the technique of delayed local precon- ditioner updates [22] to further mollify the computation burden on the clients, and verify that FedAAaa/FedAdaa2 are robust the said delayed updates (Appendix J.3
Effectiveness under Additional Adaptive Optimizers. Algorithm | provides general framework, and in Figure I we focus on symmetric server-client optimizer configurations (c.g., Adam-Adam
7

---

CIFAR- 100
GLD-23K
FEMNIST
Test Accuracy
Test Accuracy
Test Accuracy
12
Tuchaa FuckeeGrad
Fuckdar
Loar Ada
Costy Jant Adea
Gosty lice fole
181
220
Communication
Cost
Communication Cost
Communication Cost
Figure 2: Test accuracies against actual communication cost (total transmitted bits normalized to that of FedAvg) of all algorithms under the same settings as in Figure | When controlling for communication complexity, oodAda'/FedAda That is, the improvement is even more significant when measured in actual communication cost, where RedAda"/FedAcee joint adaptivity.
attain the fastest convergence over all baselines.
achieve faster convergence with fewer bits transmitted than even costly
AdaGrad-A AdaGrad-AdaGrad) Appendix contains ablations on the delay parameter including what happens when there a mismatch between the client and server adaptive optimizers (e.g., server-side Adam preconditioners communicated to client-side AdaGrad). That is, in Appendix [.2] Figure 10 we examine the performance of asymmetric server-client adaptivity setups under both jointly adaptive baselines and FedAda (Faaddaa//edaaa+= Surprisingly, our results show that in the Costly Joint Adap- tivity baseline, employing an unbalanced preconditioner (e.g., transmitting the server-side Adam preconditioner to client-side AdaGrad), does not significantly impact performance across a hyperpa- rameter sweep. Additionally, FedAda² as well as FedAdaa++ demonstrates robust training dynamics across various adaptivity instantiations with non-existent performance degradation, highlighting its effectiveness in enabling efficient jointly adaptive optimization.
Reduced Communication and Memory. As discussed in Section I while joint adaptivity has been shown to substantially improve performance, its scalability and practical deployment are sig- nificantly hindered by communication and memory complexity in real-world settings. To mitigate this bottleneck, FedAda forcibly matches the communication efficiency of FedAvg while retaining the advantages of joint adaptivity, while FedAda further compresses client memory with conver- gence guarantees (Theorem 4. I. In Figure when evaluating convergence in terms of the actual communicated bits (communication rounds times number of bits per round), FedAda"/FedAACa /Fedddda significantly outperforms costly joint adaptivity, saving significant communication bandwidth. For instance, in the case of ViT, when FedAda is instantiated via SM3, storing second-moment estimates for preconditioning requires only 0.48% additional memory. compared to an 1 x increase otherwise. This corresponds joint adaptivity, making it far more practical for aurge-scale applications. In Table []] we summarize the communication complexity and memory efficiency of FedAda /Fddddaaaa and baselines, compared to alternative adaptive frameworks such as MIME or MIMELite 17
99% reduction in the extra client memory required for deploying
34 Communication the two- way teeeeetto--lliett and client-to-server cost including both model parameters and preconditioners, and computation is the number of gradient calls per local iteration. Client-side memory cost includes the cost maintain both gradients and potentially gradient statistics.
Joint Adaptivity?
Communi- Computation Memory
DP StackOverflow
Method
cation
(fggrad. calls) (client)
FedAvg
N
2d
d
Test Accuracy
FedAdaGrud
N
2d
d
FedAdam
N
2d
d
MIME
N
5d
4d
Fallig
MIMELite
N
4d
3d
6.18
Costly Joint Adap.
Y
3d
2d
Eartl bust Adoo Falld??
FedAda
Y
2d
2d
0.01
Fattd?...
F
Y
2d
Communication Rounds
Table Comparison various algorithms (assuming AdaGrad as the adaptive optimizer). d denotes the model dimension.
Figure 3: Performance of training Stack- Overflow in the private setting.

---

Improvements in Private Settings. Another critical constraint for federated learning is user privacy, and federated learning itself may not offer formal privacy guarantees [35]. Hence, additional privacy mechanisms are critical to provably protect user information. We focus on the statistical framework
of differential privacy 36 where it guarantees that any third-party attacker cannot infer if any user
participates in training or not [37]. We apply the popular subsampled Gaussian mechanism [38] to privatize all the methods, using noise multiplier o = 1. which provides a privacy budget of (e = (13.1, 0.0025) with optimal Rényi-Differt Dinii-DDifferental Privacy (RDP) (39] order 2.0. On the
StackOverflow dataset with logistic regression model (Figure 3) we observe that FedAda and FedAda ++ again outperform other baselines by a large margin with privacy constraints.
5.2 Effects of Varying Configurations
GLD-23K
GLD-23K
GLD-23K
Test Accuracy
Test Accuracy
Test Accuracy
0.6
Fashag eg
Fudteg Fonden
Fackig Grad
FedkeaGrrd
Folkdom
Corty Mrpp
Cootl Adey
120
52
Communication Rounds
Communication Rounds
Communication Rounds
(a) Single Local Epoch
(b) 5 Local Epochs
(c) Local Epochs
Figure 4: Algorithm testing performance comparison under varying client resource limitations (i.e.. number of local epochs). When resources are constrained, FedAda 2+ converges the fastest, followed closely by FedAdam. Interestingly, the relative performance advantage of FedAda"++ ++ becomes less significant as the number of local epochs increases.
Dynamics of 2edAda under Varying Number of Local Epochs. In Figure 4 we study the transfer learning setting of a vision model under a highly constrained, moderate, and sufficient client computation budget, corresponding running 1, 5, and 20 local epochs on the clients. We see that when the number of epochs is low (Figure44 (a)). FedAda2++ achieves the best performance, closely followed by FedAdam. Interestingly, as the clients' computational budget increases, the relative performance advantage of FedAda diminishes. In such scenarios, jointly adaptive optimization outperforms FedAdam, although the margin is not substantial.
Sensitivity to Hyperparameters. In Figure 9 in the appendix, we plot test accuracies over the hyperparameter sweeps (all hyperparameters in Appendix (I) for all algorithms, on the verckOverflow dataset. Server-only adaptivity stabilizes the performance of FedAvg, and costly joint adaptivity further enhances the stabilized accuracies. However, eliminating server preconditioner transmission in FedAda² destabilizes the accuracy, resulting in significantly poorer performance for the worst losses while retaining the best performing losses. We see that there a wide range of hyperparameter under which FedAda" and FedAda have superior performance compared with the baselines. In particular, approximating the preconditioners in a memory-efficies manner using SM3 in ++dAda2++ is rather robust to hyperparameters, which we hypothesize is due to the denoising effect of projections during SM3 compression, previously unreported within the literature.
Summary. Across all datasets, we empirically demonstrate the benefits of joint server- and client- side adaptivity. However, vanilla implementation of joint adaptivity with transmitted global pre- conditioners can be expensive. We consistently find that initializing local preconditioners from zero (F (FedAda²) does not underperform (yet sometimes outperforms) costly joint adaptivity with full server-side preconditioner transmission, while being much more efficient (Table In general. we observe that FedAda" and FedAda2++ algorithms retain the competitive advantage of joint adap- tivity while being communication- and memory-efficient under variety of optimizers, datasets, and model architectures. Across our experiments, we consistently find that adaptive methods (e.g.. FedAdam, FedAdaGrad) outperform FedAvg, while jointly adaptive methods (FedAda Faladda?/FFFdee /Fee/daa consistently outperform server-only adaptive baselines.

---

Conclusion and Future Work
In this work, we introduce FedAda and FedAda2++, a class of jointly adaptive algorithms designed to enhance scalability and performance in large-scale, cross-device federated environments. By miti- gating the transfer of costly preconditioners in jointly adaptive methods, FedAda" algorithms significantly reduce the communication overhead and extra on-device memory cost without degrading model performance. Our theoretical convergence guarantees and empirical results demonstrate the practical benefits of FedAda" in real-world federated learning scenarios. In Appendix A further extend our work by providing a novel regret- based theoretical analysis of how leveraging client-side adaptivity improves distributed learning for interested readers. In particular, we study the heavy-tailed regime, which sheds light on how client-side adaptivity mitigates the propagation of noisy poddaes-pprticullan relevant in wransfommr-basee training. A promising future direction would be investigating how diverse client optimizer selections could combine their respective advantages in aggregate performance. Additionally, researchers could explore adapting various optimizer strategies across different timescales in blended optimization to better accommodate dynamically varying client resource constraints.
Acknowledgments
We thank the anonymous reviewers for their insightful feedback, which has helped to improve the quality of this paper. The authors declare no conflicts of interest.
References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. catpuuniiiiaioeffffiieeeeee learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, 2017.
[2] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):00-60, 2020.
[3] Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al- Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide federated optimization. arXiv preprint
2021.
[4] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. International Confer- ence on Learning Representations, 2021.
[5] Jianyu Wang, Zheng Xu, Zachary Garrett, Zachary Charles, Luyang Liu, and Gauri Joshi. Local adaptivity in federated learning: Convergence and consistency, arXiv preprint 10V:::066.02300 2021.
[6] Yan Sun, Li Shen, Hao Sun, Liang Ding, and Dacheng Tao. Efficient federated learning via local adaptive amended optimizer with linear speedup. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(12): 11:3::44431144440 2023.
[7] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji. Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings. et al. Advances and open problems in federated learning. Foundations and trends@) in machine learning. 14(1-2):1 1-210.. 2021.
[8] Yujia Wang, Lu Lin, and Jinghui Chen. Communication-effiienn adaptive federated learning. In International Conference Machine Learning, pages 28838.2888. PMLR, 2022.
[9] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-21551 2011.
[10] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference for Learning Representations, 2015.
10

---

[11] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. International Conference on Learning Representations, 2018.
[12] Qianqian Tong, Guannan Liang, and Jinbo Bi. Effective federated adaptive gradient methods with non-iid decentralized data, arXiv preprint arXiv:2009.06:3 066507 2020.
[13] Junyi Li, Feihu Huang, and Heng Huang. Fedda: Faster framework of local adaptive gradient methods via restarted dual averaging. ArXiv, 2023.
[14] Hao Sun, Li Shen, Shixiang Chen, Jingwei Sun, Jing Li, Guangzhong Sun, and Dacheng Tao. Fedlalr: Client-specific adaptive learning rates achieve linear speedup for non-iid data. arXiv preprint M.Xiv:2309.097199 2023.
[15] Cong Xie, Oluwasanmi Koyejo, Indranil Gupta, and Haibin Lin. Local adaalter: Communicationn-effice stochastic gradient descent with adaptive learning rates, arXiv preprint arXiv:19/1.00030) 2019.
[16] Xiangyi Chen, Xiaoyun Li, and Ping Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, pages 119-128, 2020.
[17] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebas- tian U. Stich, and Ananda Theertha Suresh. Breaking the centralized barrier for cross-device federated learning, Advances in Neural Information Processing Systems, 2021.
[18] Jiayin Jin, Jiaxiang Ren, Yang Zhou, Lingjuan Lyu, Liu, and Dejing Dou. Accelerated federated learning with decoupled adaptive optimization. International Conference on Machine Learning, 2022.
[19] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1-67, 2020.
[20] Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, pages 4596-4604. PMLR, 2018.
[21] Jiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: -effccette Ilm training by gradient low-rank projection. arXiv preprint arXiv:2403.03500 2024.
[22] Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. In International Conference on Machine Learning, pages 1842-1850. PMLR, 2018.
[23] Xinyi Chen, Naman Agarwal, Elad Hazan, Cyril Zhang, and Yi Zhang. Extreme tensoring for low-memory preconditioning. arXiv preprint arXiv: 990.0002220. 2019.
[24] Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. Memory efficient adaptive optimization. Advances in Neural Information Processing Systems, 32, 2019.
[25] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective inconsistency problem heterogeneous federated optimization. Advances in Neural Information Processing Systems, 2020.
[26] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang. and Zhihua Zhang. On the convergence of fedavg on non-iid data. International Conference on Learning Representations, 2020.
[27] Stack Exchange. Stack overflow dataset, 2021. URL hutpss//arrchve.orr//etaaa stackexchange
[28] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. URL https
//api www.nticschoollrrrr wtaeccholaarrr///ooouuuuo org/Corrps.D::eee 18268744

---

[29] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konecny, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. Arxiv, 2018.
[30] Tobias Weyand, André Araujo, Bingyi Cao, and Jack Sim. Google landmarks dataset v2 a large-scale benchmark for instance-level recognition and retrieval. In CVPR, 2020. URL https://arxivy http://wxxvvvor..r////// aa////bbs///0/// 01804
[31] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2021.
[32] Tal Ridnik, Emanuel Ben-Baruch, Asaf Noy, and Lihi Zelnik. Imagenet-21k pretraining for the masses. Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, 2021.
[33] David M Blei, Andrew Y Ng. and Michael I Jordan. Latent dirichlet allocation. Journal of Machine Learning Research, 3:993-1022, 2003.
[34] Jae Ro, Theresa Breiner, Lara MeConnaughey, Mingqing Chen, Ananda Suresh, Shankar Kumar, and Rajiv Mathews. Scaling language model size in cross-device federated learning. Proceedings of the First Workshop on Federated Learning for Natural Language Processing (FLANLP 2022), 2022.
[35] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances neural information processing systems, 32, 2019.
[36] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, 2006.
[37] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv: 1710006671.006 2017.
[38] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-3 018,118,771 2016.
[39] Ilya Mironov. Rényi differential privacy. 2017 IEEE 30th Computer Security Foundations Symposium, 2017.
[40] Jingzhao Zhang, Sai Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 2020.
[41] Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv, 2018.
[42] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Vore Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. Advances in Neural Information Processing Systems, 2020.
[43] Thanh Huy Nguyen, Umut Simsekli, Mert Gurbuzbalaban, and Gael Richard. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. Advances in Neural Information Processing Systems, 2019.
[44] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalahan. A tail-index analysis of stochastic gradient noise in deep neural networks. International Conference on Machine Learning, 2019.
12

---

[45] Umut Simsekli, Lingjiong Zhu, Yee Whye Teh, and Mert Gurbuzbalaban. Fractional under- damped langevin dynamics: Retargeting sgd with momentum under heavy-tailed gradient noise. International Conference on Machine Learning, 2020.
[46] Liuzhi Zhou, Yu He, Kun Zhai, Xiang Liu, Sen Liu, Xingjun Ma, Guangnan Ye, Yu-Gang Jiang, and Hongfeng Chai Fedcada: Adaptive client-side optimization for accelerated and stable federated learning, Arxiv, 2024.
[47] Sohom Mukherjee, Nicolas Loizou, and Sebastian U Stich. Locally adaptive federated learning. ArXiv, 2023.
[48] Tian Li, Manzil Zaheer, Ziyu Liu, Sashank Reddi, Brendan McMahan, and Virginia Smith. Dif- ferentially private adaptive optimization with delayed preconditioners. International Conference on Learning Representations, 2023.
[49] Junbo Li, Ang Li, Chong Tian, Qirong Ho, Eric P. Xing, and Hongyi Wang. Fednar: Feder- ated optimization with normalized annealing regularization. Advances in Neural Information Processing Systems, 2023.
[50] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applicd to document recognition. Proceedings of the IEEE, 86(11):2278-2333 1998.
[51] Arthur Douillard, Qixuan Feng, Andrei A. Rusu, Rachita Chhaparia, Yani Donchev, Adhiguna Kuncoro, Mare' Aurelio Ranzato, Arthur Szlam, and Jiajun Shen. Diloco: Distributed low- communication training of language models. ICML Workshop on Advancing Neural Network Training. 2024.
[52] Bo Liu, Rachita Chhaparia, Arthur Douillard, Satyen Kale, Andrei Rusu, Jiajun Shen, Arthur Szlam, and Mare' Aurelio Ranzato. Asynchronous local-sgd training for language modeling. ICMI. Workshop on Advancing Neural Network Training, 2024.
[53] Sami Jaghouar, Jack Min Ong, and Johannes Hagemann. Opendiloco: An open-source frame- work for globally distributed low.communication training. ArXiv, 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction give faithful summary of the results in Sec-
tions 3 5 and the Appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we give an overview of the main limitations of our theory in the third paragraph of Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: All results are followed by full proofs in the Appendix, and the assumptions are clearly stated in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide a very detailed explanation the setup in Appendix and and plan to release the code to reproduce experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide very detailed explanation of the setup in Appendix H Hnd and release the code to reproduce our experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc)
aublic//uidde//Cdeettttisss
www.sssinnooiiillooooooool for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtps/cccppplgguuuiieeeeee
Stteee///ooSSSeesssSioi.a www.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide a very detailed explanation of the setup Appendix Hand [ which includes hyperparameter settings and optimizer choices.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report confidence intervals as shaded regions in all relevant plots, averaged across 20 random seeds for high statistical significance and convergence.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide this information in Appendix
1.3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: ptattps://eeurtii wwwpeepp...ppuullceepeeeeeepeeee cc./pubbicc/thhiccciieeelllee
Answer: [Yes]
Justification:
The paper conforms to the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our contribution primarily address efficient distributed optimization. Therefore, we do not foresee any direct socictal consequences of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We provide extensive citations for all datasets and models in our evaluation.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We provide the code to reproduce the experiments, but do not release an API.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
20

---

Contents
Importance Client-Side Adaptivity
22
Additional Related Works
27
Detailed FedAda" Algorithm Description
28
D
Detailed Proofs
29
D.I Precompact Convergence Analysis
32
D.2 Extension to Adam
41
Federated Blended Optimization
Adam with Delayed Updates (ADMU)
46
AdaGrad with Delayed Updates (AGDU)
50
Datasets, Models, and Baselines
52
Hyperparameter Selection
55
Additional Experiments
57
J.1
Sensitivity to Hyperparameters
57
J.2
Dynamics of Heterogeneous Chinnt Server Adaptivity
57
J.3
Effect of Delayed Updates
58
21

---

A Importance of Client-Side Adaptivity
In this section, we motivate our work by providing a theoretical description of how leveraging client- side adaptivity improves distributed learning, which is validated in experiments (Section (5). Our analyses are motivated by prior works that uncover critical conditions under which centralized SGD can diverge, specifically in settings involving heavy-tailed gradient noise [40]. After analyzing the importance of client-side adaptivity, we propose efficient FL frameworks to mitigate the heightened
resources induced by adaptive local optimizers in Section 3 which is FedAda FedAda"/FedAda /FedAdaa++ We
begin by providing definition of heavy-tailed noise following previous literature.
Definition A.1. A random variable & ~ D follows heavy-tailed distribution if the a-moment infinite for a 2. In other words, we say that the stochastic gradient noise g(x) f(()) is heavy-tailed if E (z) V fxx)]]) is bounded for a E (0, 2) and unbounded for a 2 2, where g(x) is the stochastic gradient under some model parameter x, and fx)) the full gradient.
We may present the following proposition.
Proposition A.2. There exists federated learning problem with heavy-tailed client-side gradient noise such that the following arguments hold:
(i) For vanilla FedAvg, given any client sampling strategy. if the probability pt of client i with heavy- tailed grudient noise being sampled at communication round I is non-zero, then El| (x++1)]]2 oo for any nontrivial learning rate schedule vi. 0 and global parameter T++1-
(ii) Under an appropriate learning rate schedule, FedAvg with local adaptivity (i.e., via client-side AdaGrad) bounds the error in expectation as
2/3 1-8
lim Bl| - 2011 10000
for some é As O,
where x² is the global optimum.
detailed proof given by construction on quadratic objective in Appendix[A.] We show that even single client with heavy-tailed gradient noise is able to instantaneously propagate their volatility to the global model, which severely destabilizes distributed learning in expectation. Unfortunately, recent works have observed heavy-tailed gradient noise empirically, especially within model architectures utilizing attention mechanisms, including transformer-basee models (40
41l
42
31
43
44
45).
Proposition A.2 (ii) suggests that client-side adaptivity has the potential to stabilize local model updates pushed from diverse and large-scale distributed sources, communication bottlenecks and memory efficiency
be addressed.
The construction of the federated problem in Proposition A.2 draws gradient noise from the Student t- distribution which is heavy-tailed depending on the parameter regime, whose moments are relatively controlled nevertheless. We may exacerbate the severity of gradient stochasticity by inserting singular client with Cauchy-distribute noise, while enforcing all other clients to follow non-heavy- tailed Gaussian gradient noise. We further detail this setting Proposition A.3 Appendix A.
A.1 Constructions
Overview Student's I-distribution. For the convenience of the reader, we provide a brief summary of basic properties of the Student's i-distribution. Intuitively, the (-distribution can be understood as an approximation of the Gaussian with heavier tails. The density is given by
r p++
12
1v++1)/2
fo(t)
1
where y E Ry0 is the degree of freedom (or normality parameter), and is the gamma function. We recover the normalized Gaussian the degree of freedom tends to infinity. The first moment is 0 for v > 1, and the second moment satisfies v (v-2) 2) for v > 2 while being infinite for < v S 2, where the heavy-tails are most pronounced. Following the convention of [40), we refer to distribution as being heavy-tailed if the second moment is infinite.
The following proposition showcases the utility of local adaptivity in federated learning.
22

---

Proposition A.3. There exists federated optimization problem with heavy-tailed client noise which satisfies the following under FedAvg (where appropriate learning rate schedules are chosen for (īi-iv)):
(i) Given any client sampling strategy, the probability p of client i with heavy-tailed gradient noise being sampled at step t is non-zero, then V f (T do for any nontrivial learning rate schedule ni
(ii) Local adaptivity via client-side AdaGrad bounds the error in expectation as
2v3 1-
lim El - x* =x11| 10000
for some
é RJ O,
where is the global optimum.
(ii) Furthermore, local adaptivity implicitly constructs a critical Lyapunov stable region which stabilizes the gradient variance via the following inequality which holds once any learned weight enters the region:
min (E(I.....T)
V
E
S o -
(iv) The global gradient variance of the federated problem with heavy-tailed client noise is fully stabilized via
B ((<))) +2 (1,0 dr) for AE {I....,T). T)-
This proposition demonstrates that even single client with heavy-tailed gradient noise able to instantaneously propagate their volatility to the global model, which destabilizes federated training in expectation. However, recent work [40] has shown that heavy-tailed gradient distributions appear frequently in language model applications, and more generally within model architectures utilizing any kind of attention mechanism, including transformers. mode of distributed training resultant from the unbiased, yet heavy-tailed noise of singular client has not previously been reported within the literature.
our knowledge, this provable failure
Proof of (i). Let the local stochastic objectives be given by Ex( 22/2++ Ere where gradient noise follows t-distribution with + degrees of freedom. &, f.41 for Vi E (1...., N). This construction is chosen to materialize the setting in which only singular client suffers from heavy- tailed noise (i = 1). Minibatches are sampled with replacement, which ensures that gradient noise in each client epoch are independent amongst and in between any two (possibly identical) clients, and further identically distributed conditional on the client i. Clearly, the global objective is
N 2
(xx
Ee, (f((
E2e
N
For global step t, subsample clients St following any sampling strategy, where Ct is the collec- tion of all possible multisets S whose elements indicate (possibly repeated) client selection, with associated probabilities (r)(r) 0 of realization for E [[C']]. Assume that St. for some
Then, FedAvg updates may be written
1/8
Ft+1
Pil
|
iEst
1=1
23

---

which gives the squared length of the global gradient under expectation as
E, V = E,
F1
n
Vf(a) + (ie-1)
SM
iES!
ne
(= + -(/
2t
|8
iES t=1
c'1
Σ
(r((P((r)
Vf + El,e-1)
I1
S
iESt 1=1
2 (m)
Tle S
(2t,-1 + St,e-1
FES
where in the second equality we have conditioned on local gradient noise & and stochastic realizations up to timestep 4, using the law of iterated expectations. Recursively unravelling x in terms of sampled noise and æç,0- Iz gives
= = xiee-2 melie- 21,00
mee Σ Sip
1-2
= 24.00 - 116
Σ
( + tip
1-2
2 - 11
Σ
di. + Sip
p=0
Si.piip
where ae, op Qnd are polynomial functions of the learning rate with rational coefficients. Therefore, have for bi E Q(nel
t-2
(m))e
It
Te |St
Σ
Σ p=0
St.
iESt,
K
= =P
1
Stt
2t
MT St
Σ
af et + (
p
SESt
ē=1
FES!
{=1
p=0
r pP (ml S 1
K-2
= =p
Ot
Et
Egg
Σ
Σ
+ ki
St
BESt
iESL
p=
(m)
Si,K-
DO,
1St
where we have used that E/ ~ li+1 independently with mean 0, for all permissible e, and I.
Proof of (ii). We show that under client-side AdaGrad with normalized gradients, the expected iterate norm converges to a noise-dependent constant at rate (1/(), uniformly over client subsamples. The key idea is a decomposition of the update into contraction term and a noise-dependent residual, showing the decay of the contraction under suitable and learning rate schedules. We specialize to the setting with client-side AdaGrad with K 1. Assume that clients St have been selected to

---

participate in the round, which gives the update
K
gh.e
nhe
21+1 = Et
|
N +E
(2)
VES*
ff(afo)) + Si,1
ne
2t
|
Vf( + -1,1l +E
VE
m
1 1 + E:ll +
&
Zt
S
SS
+ &
+
iES
EES
where we have gradually simplified notation. Noting that
p(e)) de
2+ + Gill +e
6
setting n/ S gives
[V = | S |xxe||
Te St
Σ
+
H&N
(3)
24 + &ill +
S
+ Esll
+
iES!
jES!
Using E, denote expectation conditional over realizations up to step t, have
(1 (1-
S Te
1
))
Tle Sa
Ex
11 S ||<e|||
E,
E2
LiES' Ir.
& +e
|
&
+
iES!
To further bound the right hand side, consider the functional
T,(e) = /
| + Eill + E (5:1(()) de,,
where clearly
1or ot
Pi+1(-Ite) dx 00 |0||
((0)
Pit (E.) dé,
10t + Eill
and I,(1) < 1. By continuity and strict decay of [E),, there exists >> E > 0 and E; E (0, 1] such that for all i [N], we have 1 > [E))
E. for [Es, 1]. Taking e E [max]e[N] Et, 1] and
== maX &. we thus obtain
|k&ll
E. || S |[aell (1 - me(1 E))
+
Σ E2 iESt
S
|| + &ill
+
To bound the remaining term, it is easy to show that ||E: P (E,) is symmetric around the origin O and strictly increases from to (3/2 + 2/(i + 1)) while strictly decreasing afterwards. Defining the even extension of
(3/2-2((++1)--12 + supÇER (I)))p++1(() +e for 0 < &
hS4)(E))
||e:llpH+1(5 (E))
for &
to be (E:) for small >> c > O, we note that 1/([ + &ell + E) analogously is symmetric around E, -I, while decaying with respect the argument ||æ, E.ll- As h5+1(Et) is symmetric around O and decays moving to the left and right O, by matching monotonicity and maxima with 1/([|xr &:ll E), conclude that the left hand side of (5) is maximized for x; 0:
l&ll
1 (E:)
E2
de; = B,.
(5)
cr + S.ll +
Asymptotically 00, have
h (5)
|& + S PE))(E))
25

---

which gives that B; < co. Letting B ==
maXie[N] B; and scheduling the learning rate rf
1/((t + 1o)(1 - E)) where to is the smallest positive integer satisfying vá < e for all t, we thus conclude
1 + to
B
E B1411l
E|
t t to
(t + to) E)
+ to
2
2B
x
B1 ||
+ (1+ (o)(1 E)
1 1o
< ... S to
+ (t+ 1IB
1 to
- E)
1 I-
As this bound holds for any choice of client subsample S we are done. It is easy to show by straightforward integration that B < 2/3.
Proof of (iii). Our strategy is to locate 1-shot stabilization regime of the gradient norm that is formed via client adaptivity, which may viewed as a Lyapunov stable region of the optimum x².
From 3 and Jensen,
2
2
2n
II& aI + Eell
|r++|| $ 2|
1
+
Σ NiES
St
D2 + Eill
+E
|St12
+
E
ieSt
2
21
|KEl| Eill +
$ 2|12.
1
S
I + Eill +
|St
||
iESt
FES
We now impose ne S 22, while letting
< 5 for some ò E E>.. Taking expectations gives
2n
E, | 12 < 2|
+
Ey,
S*
|| + &
+
*ES!
and by similar arguments to the proof of (ii), the summands of the second term are bounded uniformly by B which yields
Bl|a++1ll < 25 + 2
Setting 8, n S O(I/VT) immediately gives the desired inequality.
Proof of (iv). An advantage of client-side adaptive optimization is the autonomous normalization
and clipping of the stochastic gradients. Let n/ == 1/1². Telescoping (2)
gives
n St
giee S ll
TT+1 30
iESt
which implies
g
| zool
St
9
+
iESt t=1
T
K
Dhe
|||er+1l|
11
11 ll +
1=1
iES!
1=1
K
gh.
| < ||
S
| |l
+
VES'
T
K
gi.e
E Frtill 2 s 2| + 2E
S
|9
+ +
S E=1
26

---

We Substituting the learning rate schedule r/ == 1/t² above gives
T
K
2
T
I E
KT
+
SES
1=1
1
R
K
dx
x2
Therefore, we conclude that for any t,
(
1 x
E c2 [ 2| 2K
da
A.2 Deep Remorse of FedAvg and SGD
So far, we have examined toy problems in which heavy-tailed gradient noise is guaranteed to destabilize distributed training in expectation. We now prove that this is an instantiation of a more general phenomenon in federated learning where family of online j-strongly convex global objectives collapses to the identical failure mode. To our knowledge, this provable limitation of distributed training resultant from the heavy-tailed noise of singular client has not previously been established within the literature. The proofs of all results are given in the appendix.
Definition A.4. A learning algorithm
deeply remorseful it incurs infinite or undefined regret in expectation. If A is guaranteed to instantly incur such regret due to sampling even a single client with heavy-tailed gradient noise distribution, then we say A resentful of heavy-tailed noise.
Theorem A.S. Let the global objectives fx(x) of distributed training problem satisfy p-strong convexity for = 11....T. Assume that the participation probability of a client with a heavy- tailed stochastic gradient noise distribution is non-zero. Then, FedAvg becomes deeply remorseful algorithm and is resentful of heavy-tailed noise. Furthermore, if the probability of the heavy-tailed client being sampled at step is nontrivial, then the variance of the global objective at + 1 satisfies (x oc.
I,..., (i.e., the objective functions are the same across all rounds). Proposition A.2 intuits that inserting local adaptivity successfully breaks the generality of remorse and heavy-tailed resent for FedAvg. A high-level overview is that client-side AdaGrad clips the local updates of each iteration, which mollifies the impact of stochasticity in perturbing the weight updates. This gives Proposition A.6 which is formulated loosely without utilizing any advantages provided by local adaptivity except for clipping. Given that adaptive methods inherently include an implicit soft clipping mechanism due to the effects of preconditioning, we consider them to be preferable to clipped SGD for large-scale applications as they also offer the benefits of adaptivity. This preference holds, provided that the memory and computational constraints of the clients can be adequately managed.
In federated learning, we typically have fe(x) f(x) for all =
Proposition A.6. Introducing client-side adaptivity via AdaGrad for the setting in Theorem A.5 produces a non-remorseful and a non-resenfuul algorithm.
The benefits of client-side adaptivity have also been shown in previous works (e.g.. [4 5 note that Proposition A.6 can be straightforwardly extended to jointly adaptive methods as well as for ft E C(Rd) not necessarily convex. An advantage of federated learning is that when done tactfully, the large supply of clients enable the trainer to draw from a virtually unlimited stream of computational power. The downside is that the global model may be strongly influenced by the various gradient distributions induced by the private client data shards. In this paper, we focus specifically on joint adaptive optimization as countermeasure to stabilize learning. For this reason, we propose PedAda2/FedAda /FedAda i
in Section 3 which utilizes joint adaptivity in an efficient and scalable manner for distributed or federated training.
B Additional Related Works
Due to space restrictions, we include a brief additional discussion of some recent related works here. Mukherjee [47] propose FedSPS, a locally adaptive method using stochastic Polyak step sizes to
27

---

dynamically scale updates client, achieving theoretical convergence under heterogeneous data. Li al. [T3] develop FedDA, a restarted dual averaging framework in which clients receive adaptive preconditioners and gradient estimates from the server and return dual states, enabling matching to standard non-adaptive gradient complexities for non-convex optimization. While these methods enhance local adaptivity, they often involve costly communication of dual states [13] or are not jointly adaptive [47]. By contrast, our approach maintains minimal communication and state, enabling efficient deployment while retaining joint adaptivity.
Comparing with Wang al. [5]. We note that Wang al. [ employs a similar strategy of initializing local preconditioners to zero. However, this work does not provide convergence guar- antees for this efficient algorithm with vanishing errors, and does not systematically evaluate empirically, Instead, it proposes another adaptive optimization framework with extra communication overheads. Although the theoretical results establish upper bounds, crucially, in their Theorem the terms involving h; cannot be computed in closed form for adaptive optimizers (only estimated numerically). limiting interpretability and practical applicability. To the best of our knowledge, our work is the first to provide rigorous convergence guarantees for FedAda" FedAda"/FedAda" /Fed/dda without leaving any residual terms that are not analytically characterized.
C Detailed FedAda? Algorithm Description
In the main text, we have opted to describe the intuitions behind SM3, due to its technical implemen- tation. In this appendix section, we give a more through walk-through of our algorithm details for any interested readers wishing reproduce our proof strategies implementations.
Algorithm 2 Adaptive server and client-side ADAGRAD with SM3 (FedAda
Require: A full cover ( S C P(dd) where U S. = {1, ........ d} Update delay step size E Z21, initializations To, 0o r2 and my t- 0
Local epsilon smoothing terms 6s, > O, global smoothing term > 0
Global decay parameter [1 E 1)
fort=1,.... T do
2: Sample subset St C [N] of clients using any sampling scheme
3:
for each client E S (in parallel) do
4: Initialize vn 2 0 (default value up- <- 0), 24.0 f It-1
5: for 1: = 1, .,..., do
6:
Draw stochastic gradient 9 ~ D, Dg.gad (=f with mean VF, Rd
7:
my g (b) + for Ab (1.....9}
8:
for j = 1,...,, do
9:
Approximate Preconditioner SM3 end for
10:
11:
0 < [|mm// + e)ll < E,, do my < 0
12:
ai1 + -=f,e-1 - me mi/ (V 1 + E)
13:
end for
14:
A = o 86-1
15:
end for
Server Update SU
17: end for
Addressing Client-Side Resource Constraints. In this paper, we specifically focus on SM3 24 adaptations of Adam and Adagrad. Intuitively, SM3 exploits natural activation patterns observed in model gradients to accumulate approximate parameter-wist statistics for preconditioning. More precisely, the gradient information in each coordinate element {1, [1....,d) dd} is blanketed by cover (S1....,S,, ..S) satisfying Ul_1. S. = (1.....d) d) for which auxiliary (b) is assigned for each E [g]. The (b) then act to form Uk as coordinate ascent upper bound to the squared gradient
sum (o,( as SM3 iterates over each j E [d].
As an optional add-on, utilizing the staleness of gradients to construct preconditioners has previously been suggested as strategy to accelerate adaptive optimization without hurting the performance [22
28

---

48 Therefore, we may optionally further mollify the burden of client-sid adaptive optimizers by enforcing delayed preconditioner updates (Appendix J.3). This is given by the following SM3 update rule (SM3) which incorporates delay step 2,
Un (j) + mina: Mh- (b) +
oh (i))
(i)
for Z
SM3 Update:
(b) - max (i), for vb Sb 3
(SM3)
vx(j) 1k-1(j)
otherwise
where & is the index of local iteration (starting from 1). These methodologies are consolidated into FedAda", Algorithm 2 For simplicity, we describe the variant in which both the client and server employ AdaGrad as the adaptive optimizers. However, we present other instantiations of FedAda" with different adaptive methods in Appendix and J.2
We now present description of SM3-I/II with delayed preconditioner updates as Algorithms and 4 SM3-II capitalizes on tighter approximation of the second moment, and empirically demonstrates better results. We have opted implement a smoothing term & instead of treating any zero denominator as zero as done in the original work. In this paper, we provide the analysis for SM3-II which generalizes the analysis for SM3-I.
Algorithm 3 Delayed preconditioner SM3-I
Require: Client learning rate Te. step delay 2 Z>1, and e-smoothing term Require: A full cover 1S,....,SA C P(dd) where U Se = {l.....d)
I: Initialize: æι and (o(r) 0 for Vr {I,....
2: for 1,..., K do
3: Jt Vf(x,)
4: if (t- - 1)/z E Z then
5:
for (r) + (r) + maxjes, 0i
I,..., do
6:
7:
end for end if
8:
9:
for j 1................ do
10:
( min..s. ej (r) (minimum taken over all r such that j E S,)
(J) + zx(1) m)
Vurl)++
12: end for
end for
D Detailed Proofs
To enhance clarity, we present several lemmas before giving the proof of Theorem D.6 Note that Lemma D.1 is written in broadcasting notation, where the scalars in the right hand side have 1 E R implicitly multiplied and the inequality holds coordinatewise. For notational convenience, we will view $K $ as vectors.
Lemma D.1. Under Algorithm
| is bounded by
A < " == 77
K
log 1
K
G2 E2
Te(K 1 z
Vup +
Proof. Forming bound for the pseudogradients is not trivial due to delayed preconditioner updates. We begin by noting that delayed gradient updates are initiated at local timesteps
no + 1 for E Zz.. We now split cases k/2 Z and k/2 E Z. In the first case, there exists n E Zzo such that
nL + 1 1 (n 1)2, and the latest preconditioner update by client step is given at timestep ([k/=] [1=/=]-1)=+1
[k/z|z 1. In the second case, if = ş 1, then step k is just one step shy of a preconditioner update. The latest update is therefore held step ([k/z] 1 1) + which is no longer identical to [//2]2 1.
29

---

Algorithm 4 Delayed preconditioner SM3-II
Require: Client learning rate step delay 2 E 221, and e-smoothing term >>
Require: A full cover (Si...... Sk} C P(dd) where U St (l....:d)
1: Initialize: 21 = and (6(r) = 0 for Vr E fI....,k}
2: for 1,..., K do
3: St 4- V((x.)
4: (((r)
0 for Vr [k]
5:
for j = 1....,, do
6:
if (t 1)/2
then
7:
vi(i) f- mi (1) for all r: r S, C do
8:
9:
set (r) c- max ( (((1)
end for
11:
else
12:
v1(() +- 14-1(1)
13:
end if
x++1(f) + x: 2r(s)) m(9(()
Vo(l)++
15:
end for
end for
With this observation, is easy show by induction that
(x) 2 vo(5) + Σ gh 1)=+1)))) for j E {l....,d} and e (L...., K}.
z/.0- By telescoping for local steps and the definition of gradient updates in AdaSquare SM3, obtain
Recall that A, = 1 A and A = x k
mp
A
NE
m2
Ep
+
+
r= (ot
(r-( +
For F= (0, I..., [K/2] - 1)2 + 1, we thus have that
A S m/
PEF Vuo + Σ1
-1==
12
(of,
(1- 1)+41
)2
+
19t.pt
+
PEIKT V + Σ1 (9) (0. (1),1-1))41122
To obtain deterministic bound, cannot ignore the worst-case stochastic realization that g. (r 1)2+1 for Vr E [[ E [ F. Therefore, we form the upper bound (where
Σ1 = 0 by definition)
l
A < mh Σ
Σ p
biipl
(6)
PEF V00 + lot,pl
(0 1)2+1 +e yo +E
Ti
5 m + Ne(K [ [K]]
Vuo +
30

---

As 0 is trivially bounded by any non-negative upper bound, we may without loss of generality assume that g (i-(r-1)2+) 1)=+1 # for at least one r [ We further bound I₁ as follows:
p
2 E2 + Σ EE Eiipl 19
Ti S Σ PEF
V 1ssppp
12 +
+
( 11, 12 +
DEF
$ VIAI
Σ PEf
Drejpjn 1st
K
19. 12
log²
1+
Note the use of Cauchy Schwartz in the third inequality. A detailed proof of the log inequality used the third line may be found as part of the proof of Theorem D.6, equation which uses similar techniques. By Assumption 2, we are done.
The server-side pseudogradient updates may also be bounded as follows. Lemma D.2. Under Algorithm 2 each server step size is bounded in absolute value by
+ min { TV (1 -1- T
Proof. Without loss of generality, we may let = when forming the first upper bound for expository purposes.
71 31) Σ 1-1 31 3--1A1 Ad
17k
1/2 + 5
V V
A + 72 +
711 Bi)
(bi. 87 A
221
S
V
E'en 33
E/=n 82
1TV
B1 V
BR
31 2
7y 31
Note that the final inequality is obtained using Cauchy-Schwartz, while the second bound in the lemma statement follows from the first inequality and Lemma D.I
Finally, we form loose upper bound for the gradient variance.
Lemma D.3. For k E {I,..., K}, }. the uncentered variance estimate Un as well as pe in Algorithm are bounded by
(B1): : 0 5 (b(b) < dkG² for and b (1,...,,).
(B2): : S vx(i) S dkG² for j E (l.
Proof. Non-negativity of the variance estimates is trivial and implies the non-negativity of pas thus we focus on the upper bound for which we use dual induction. The case k = 1 is satisfied by zero initialization. Assuming the inequality holds for k &- k - 1, we have for each j
vx(()
min /h-1 (bb) + (o)x S d(k 1)0² + G² < dkG². b:Ss3)
Now, μ4g is initialized to zero at the start of each step &s and its entries are increased while broadcasting over each coordinate j {l...., d) by
(b) max (x(i)} for vb:j E So.
31

---

For j = 1, it is clear that
(ba + un(s) - dkG for vb .l.....97. ot.
For j 2 2, inductively, we have
(b(() + max(ux(b). vx()) & dkG²
as both arguments of the maximum function are upper bounded by dkG?. This completes the proof.
D.1 Precompact Convergence Analysis
We aim to analyze the convergence of learning algorithms under the general, non-convex setting. However, extremely popular and well known adaptive optimizers such as Adam whose efficacy strongly supported by empirical evidence have been shown to fail converge even for convex settings [il]. Therefore, recent works have investigated the asymptotic stabilization of gradients, instead of requiring strict convergence to local or global optima of the objective
g 12 14 15 16
40). Such convergence bounds are of the form min; V (=+))l I O(T-"), and are interpreted via the following lemma:
Lemma D.4. For 24 the t-step parameters of any objective f(x) learned by an algorithm, let ming V (x+)] < O(T-a) for a > 0. Then, there exists a learning algorithm which outputs oc.
parameters (#i, ....... such that [V -
Proof. Assuming otherwise gives that (z+)] is e-bounded away from 0 for some 0, for any parameter realized by the algorithm. Clearly, minigigr ||V + as T - 0o gives contradiction. More constructively, note that Ve 0, T(s) E N such that T T(s) mini fxx))l < e. Letting ε = 1/n for n E NN and T, == T(//n), we have that there exists tn E [Tn]] such that [V, Ill < 1/n. Letting T. It, extracts the desired parameter sequence.
This notion of convergence can be formalized as precompact convergence which is consistent with sequence properties of precompact normed sets. In this paper, we explicitly formalize the conventions used in prior works, and take the term convergence mean precompact convergence unless stated otherwise.
Definition D.5 (Precompact convergence). A sequence {yn ) in a normed space y is said to converge precompactly y E y if there exists N -> N such that Up(n) y.
Our goal is to develop principled federated algorithms whose global gradients are guaranteed to converge precompactly to 0 regardless of parameter initialization, in the general, non-convex setting. Note that precompact convergence must allow for convergence to each element of the sequence. Now, we are ready present Theorem D.6.
We note that prior work, such as FedNAR 49 and FedOPT 44], primarily analyzes either server- side or client-side adaptivity in isolation. In contrast, algorithms incorporate joint adaptivity- combining client- and server-level adaptive updates-even without explicit preconditioner transmission, necessitating distinct convergence analysis. Intuitively, the proof relies on the L-smoothness property and a careful decomposition of the inner product between the gradient and the adaptive update. A key challenge is handling the time-varying preconditioner ( Or), which is addressed by splitting the analysis into a term capturing the change in the preconditioner and main descent term. The descent term is analyzed using auxiliary variables 7, a, and Young's inequality, which isolates the sufficient descent (negative definite term) from the client drift error (discrepancy between global and local gradients). After telescoping the inequalities over T iterations, the proof employs specialized techniques to bound the resulting summations. For instance, an inductive argument (Lemma D.8) yields a logarithmic bound for emoor related to preconditioner updates, while the accumulated client drift is rigorously controlled by demonstrating that the exponential decay of the momentum parameter dominates the polynomial growth of the drift (Lemma (.7). Rearranging these bounds provides the final convergence rate.
32

---

Theorem D.6. In Algorithm
2 we have that
11
+
12
33 +
4 + 4
min E((T]
| (1
V
where
V = f(z0) - f(x"),
LTd] /
2/2
T2
BT DTMe K
33
aIT(V TO + z)²
(1 B1)me K LT ((TT'((()))))) 11
V44
Tn + E)
0dll G - 31 + log 1 +
4.
72
3(1 - I
Mo
4 (VTI 122 8o
Here, the constant is defined with respect Br as
Vo(
1
c(B1)) =
Σ
zd for To(B.) inf(u E N: N: 3,00002
for for Ve u}
(o(B))
a=0
and the intermediary 7n on values are defined as
K
31 11 Voo + dKG
2 + dK G2 + 2e
Proof. To enhance readability, we use both coordinatewise and broadcasting notation, where a [- subscript is attached for the j-th coordinate. In particular, the arguments detailed mostly in the latter notation as it significantly clarifies the intuitions behind the proof. By L-smoothness, we have
f(x)) < f(x;-1) + (V - -I + || 11-111
2
= =((x)-1) +11 (V((E--)) 3im + (1 - 31) E1=1 T
+ 2
mg
(1-
B1)
Σ1 31
"
Vūr + T
2
+T
L
M + (1 - B1 ΣS
31
-(xx-1) + -1-
(1-Bi)n
To +
V0r +
where for r E [t].
To.r = (V(())))
A Ver +
and To,0 ([(()-)); Vie +
3 mg
Note that To,o can only decay exponentially training progresses, Vū, is monotonically increasing with respect to and (x is coordinatewise bounded by G. We decompose To,r further by
To,r = 31- Vf((r-))
ot-r
Vf(ar)))
0z
+T
V
+T
V
+
Ti.
Ta.r
33

---

A bound for Ti. can be obtained as:
A Ar - Vot)
Tı, = -
(I( (V + + 01-1 +
A
= -
Vf(x=-1),
8- T)( 01 V0r)
1
$ 1
(or + 01-1 +T)
$ 3 Σ
G
(ū2 + +2) 1 +T)
1=1
$
G
T
Lemma G.2 is used obtain the final inequality. For T2,r, we apply further decomposition for 7/ > allowed to be arbitrary within a compact interval enj- boundoddde away from 0,
vf(==-1)
(x(x+11)
T2. = 3/-r
Dr + 7o vf(())1)
-1,
Vū-1
V +T
22.
For expository purposes, we present the case in which local gradient clipping is not triggered. The analysis directly generalizes to the setting where clipping activates, where we assume that not all gradients are clipped to 0 for the algorithm to proceed. Unraveling the definition of A, gives
K
7 Sr
9
A,
11
YES"
p=1
which intuits the following value
K
n
7> ==
S
SEST
p=1
We have by Assumption and Lemma D.3 that
K
1
M K
Nr E
Fin
R2] ==
Uu + dKG
+e'
Vig +
p=1
34

---

Expanding T,2, for ar > 0 to be fixed,
(((==11)
31
Ar + (V(((-))))
V + 7
V ( ne (Vf(x(-1) Pip)
8
0-- +
Vpp +E
iEST
78.1 a
V (((=-1)
Σ
2/5"|
V +T
iEs"
(V((a 1) VB
ΣΣ 2/5r(a 0r
+
Vin-i (V
iES p=1
18 1 K
vf(a--1)
2
21 2|S T +E)
TjPP1
VF
VES"P=
where in the first inequality we drew the deterministic gradient instead of accessing the stochastic sample via full gradient descent. The first term is controlled by setting
011 02
2m K
2//00 + dKG + 2=' 2/7h +
We aim to bound the second term via majorization and telescoping arguments. We have by L- smoothness, Lemmas D.I D.2 and Assumption 2 that
Σ
FE[N]
Σ
N
FEIN
Σ (IVF
VPr
VV
VR -
KE[N]
2L
| - 11 27
|| 1 -
N
N
PE(N]
ME[N]
22 || - -リ-1 11 + 2% | -,,,ol"
1-1
2L - r) Σ
||,, - xo-1l1 11 1 |bp11
2L - 1 112
Note that the first inequality was obtained by Jensen, while the third inequality uses that the client weights rfo are synchronized to the global weights _r-1 for vi E [N] at the start of training. Now, we have
K
3 2|5r a, ( Ty + E)²
Σ
2L(t - 1 2|2 2I 1
"ES" p=1
ne KL(t 1 112
ne ブ 11
arT(Vro + =
a +)
35

---

Collecting terms gathered thus far gives
100 G -F
d
[
3/ -t-r
v vf(x(11)
(1 (1-B1) 11)n Torr S ((1-
Σ
1
1/
4
V
r=1
nest - KT
-
1..1--ī.K] || $
+(1 (1- - 31)n
+
a
a + E)²
Now, let us bound the final term in equation
mo + (1- - B1) Σ 3 A
8 mg
2
(1 31)
A 2
2
+2
Vt + T
V U/ +
U1
31 mo
(1 31) Σ L
31 max |
$ 2
+
-=
1 +
Vūg +
B mo
2
(1 31
2
5 2
+
||00 112
Vū +
Vox +
B mo
2
+ 2d
2/6 + T
72
Substituting into equation 7 gives that
8i
Ld| 1 12
K
|G3
f(x)) S (x) + 1/o.,0 + L
+ (1 (1-33 (1-3,)m
V +
72
T
KL(t - 2
ne.3 -
+ +1--31)
a, (vo6 + =)2
a, (voo 8)2
31 zt -r
vf(x(-1)
+ (1
B1)n
(9)
4
Note that the exponential decay caused by 31 in the third term will expectedly dominate the effect of first order moment initialization mo as training progresses, and summation over E [T] gives O(1). We initialize mo + 0 to further simplify the equations. We also further exacerbate the upper bound by substituting 71. 0g into Tr, respectively, which achieves independence from r. Telescoping equation ( then gives
2
3(1
T
(
ff(1)) - f(xx)) + (1- 3 )m) K ||G
T
d
AA?
4
V
+T
17
LT 12 (1 (1- K
ΣΣ
T
t
(13
1| 71 IPP)
(10)
a1T(Ven + 2)2
To complete the proof, we aim to ease logarithm out from the third term on the right hand side. For this purpose, we induce recursion with a log bound
A
1
Σ (1
B1
i
Σイ= -==
A
+
t=1=1
Ei=1
1=1
S 0T + CT log (1 + by)
(11)
Setting T -= 1 gives
A j A
(1 (1-
< a1 + c log(1 + +b1),
+ +
i.j
36

---

and setting ar = -1 33 satisfies this inequality (among other choices). Assuming formula (11 for T, let us explore the induction condition for T which
holds
T Σ (1- E=1
A
A ΣTT1
(1 31
g1+1)
S S0T+1 + CT+1 log (1 + bT+1).
A +
For simplicity, we impose that is a monotonically increasing non-negative sequence of l. We intend to contain the increase in the left hand side as T grows in the log argument only, in the right hand side. Therefore, we select aT+1 ar. For suitable choice of by+1 satisfying strong induction, it is enough to resolve
2
T+1.j
CT41 log
1 by (1+br=1)
by+1 by -C- 11+
log
T+1 D
A
+
1 bt
1 + bt
Here, we used monotonicity of Cz. Noting that log(1 + x) 2 2/((1 + x), it is again enough to resolve
T+i.j
c++11b++1 bT)
T+1 +
bT+1 +1
A T+J
A T
+ CT+ibr 1
CT-1
br+1-
+ jjj
Σ
2 + +
By positivity of be for / >>> 1, necessary condition is therefore that
A
CT+1 2
+
In order to enhance the tightness of our bound, we choose the minimal permissible value ca 1 uniformly, which attained as suprema. In this setting, we are left with recursion
A7
brt1 by
T+1
2,j +
bt +1
Lt=1
and collecting the terms in the form bT+1 = bT (A) + w2(A) would provide an optimal recursive bound given our simplifying assumptions, starting with 61 = 0. A less optimal but simpler bound can
be formed by selecting br+1 = by + A 17 T2 for bj = A /Tp Therefore, we arrive at
T
A
T
2
(1 -1- 31)
11 3 + +lg
1+
Σ
Ei
+ 7
1=1 r=1
t=1
T
112
< 1 - B + log
1
(12)
72
The remaining term to be bounded in equation
10
is given
(1 Br K KL ā1T( 0o =)²
T
ΣΣ (t)((t)))(10811
The trick to notice that the explosion of the series caused by double summation is culled selectively in reverse chronological order by the exponential, rendering the tail end asymptotically vacuous. Note that (1 B1) stabilizes the divergence as B1 1 in the limit. By change of variable = t r,
T
T-1
(1 - 31)
3 (1 - = -1 (1 -1-3)) 3h)
Σ
3y 2T - u).
w=
Defining
= N: :3p0 1
for Yu 2 u)
37

---

let
(31)
c(3i)
Σ
1 +
zd
mo(B))
==
Then, claim that
31)
We prove this by induction. The case T is trivial. Now, assume the desired inequality holds until T. For T + 1, we want to show
(1 B1)
( (1))))
- (1 )1) T-1
T
Σ ()) -1-1) 3,) Σ
Buu2 S (1- (1) +1)
==0
and thus by the inductive hypothesis it is enough to show
T
Σ 3r & c(3.).
However, this trivial by the definition of c(3r). Upon substitution into equation (10 and noting that
3(1 31 37
T
v (
3(1 3.
min
| (x
4
4 T 12 th +
simplify
3(1 - T
min
[ f(20) - -f(x))= +
4 / 112 8o +T)
1E|2
T2
(1 Bf mmme 1mmk TmKKTLLD0 112
(1 30mKKTL(6))00
(13)
(Vo + t)²
017(10 + E)2
nd || (1 31 + log (1+ T1 1 7²
T
Therefore, immediately conclude that
[[((==)))1 11 + 1/2
V/3 + V4 + V
min [E
V
where
V f(xO) f(x)),
1 LT $
T2
(1 B DmTe 1F
1/
aIT t0 + +)²
V. (1 3 K L.T [.T.(3:)((55))
āiT(VVo =)
/ |G (1 31 + log 1
T 12)
3(1 31 T
16
4 1(
( 1/2 No + 7
38

---

Here, the constant c is defined with respect to 31 as
c33 = Σ
u +
dx for ūn inf E N: 3
1
for Vu 2 u}
(o(
x²
62
a=0
and the intermediary 7,, ō1 values are defined as
K
n1 qe Voo + dKG
2//0 + dKG² + +
This concludes the proof.
Note that we have also shown the following two useful lemmas:
Lemma D.7. For B1 [0, 1) and T E Zzo let
To(31) = inf E N: Bi00 < = for Vu uu,
and
ig (31)
c =
1
2 +
(n(3,) x² dd. dz.
==
Then, we have that
T
(t
1=1
Lemma D.8. Let De, R. $1 E [0,1), 1), and T E Zzo. Then,
T
A Σ
1 TT
(1 B1
7 $ $1
+log
72
We present the following corollary.
Corollary D.9. Any of the following conditions sufficient to ensure convergence of Algorithm 2
(A) ne (TT21/2) for ((T < m < 0(1).
( me 9( 100) for 2(T < < <
Proof. The proof is formed by comparing orders of T. Recall that 71 O(ne) and === O(n '). As ΦK = =(ne) and o θ (min (n), m)))) we have for 7 O(TP)) and me O(Tv)).
1 = (())
1/2 = n'
4/3 T
'" if (()) 0(1)
4/4
NET i > 9(1)
4/5 me log(1 + Tn?))
mmeT
if OTT))) 0(1)
1/
IVT if (('())) 2(1)
39

---

If (TT)) & (1), then Onn) - (1) which implies
1/1
(mm(T) θ (I - (--(tttaa)))
166
4/2
me = (TRitR2)
1/3
m/ θ (T
24 1/21/ = θ
+2p)) (p2)
1/5
log(1 + TTī²)
= O(T
T
This implies that we must have that P2 v -1/2 and -1 -1 p1 + + < 0 for guaranteed convergence.
Thus, ny - O such that Q2T=1) < me < O(1 is sufficient condition. For instance, let
= O 1/2) and 1/3 < < /3)
Now, assume @ (1). If @m)) Q(1), / T// diverges. Therefore, let me S 0(1) We have
41
(TVT) O(T-P1-5 -1-b)
16
4/2
m2VT = @(Tm+tppptt
1/6
4/3
11
VT 2
166
4/4
VT = =m(T
m1e
1/
ds me log(1 Tm/))
<((
d/
/T
Therefore, it suffices to satisfy
1 < P2 -
< Pl,
P1 + 2p <
2p1 + 3p2 < -
2
2
2
An example satisfying these conditions are
O tb0)
2(T
<, <
Note that for all cases, Ny must decay to establish convergence. However, striking a balance between local and global learning rates provably allows for greater than 2(T1/33 divergence in the server learning rate without nullifying desirable convergence properties. This theoretically demonstrates the enhanced robustness properties of adaptive client-side federated learning algorithms to mitigate suboptimal choices of server learning rates.
Corollary D.10. Algorithm
2 converges at rate 112))
Proof. If (TT)) < O(), then we juxtapose // //e and 2/2/ 02///// is clear that the minimax value of the respective powers are attained at Pl + /22 = -1/2, realized by P2 = -1/2 and p1 = 0. In this case, clearly (vb:/vb)) < (T-1/22 for < S 5. If (T > 2((1), then our strategy should be to minimize P2 due to positive coefficients in the powers 1//066 Thus,
P2 11/2 + & for
>> 0. Then, the order of decay in 2/2 ths is - 1/22 2e, which is once again matched against
-Pi - 1/2, the power of /1/te ///e Taking the limit e + 0+, minimax - 11/2 1/2 - 1/2] for the
range - 1/2 < P1 is attained p1 O. This sets the maximal decay rate to (T221 for the second
case.
D
40

---

D.2 Extension to Adam
The extension to the case where Adam is selected as the optimizer for the server, for both the server and client is straightforward. We present the latter as it generalizes the former analysis. As in Lemma D.I we have the following bound for the compressed SM3 estimates of the second moment,
vx( 2 vo(s) + ()))))))+1))) for j E .......d and & (1....., K}:
which allows bounds be established for the local and global pseudogradients following analogous logic as Lemmas D.2 F2 As before, we arrive at equation ( where due to exponential moving averaging on the server side, we have
0 = 8200 + -2)) Σ
92 De.
Now, decompose Tor
A.
A.
A
Torr = 31-
-
Vol +
v 1
12 1
+
Ti.
To.
where Ti, may be bounded via
Tí, = 39-1 vf(aa-1). A.ly Sil/Bbn. 320,-1 - Vox)
(V () 82 +
-A,Aī(1 - -32)
81-1
V5(x)-))
(Vu, (V
1201-1 + r)( B2t + V0
| G 32)
d
Due to the exponential decay parameter in the first pseudogradient moment, we have
| G 32)
$ | G (3))
72
f=1
n| g GT 32)
An analogue of the arguments made in the proof of Theorem 4.1 with appropriate modifications, c.g..
(1 31) D1 gp-e
7t
ST
p=1
V 32) E 3
(e-1(11)))+1) +
gives the main change as the asymptotic behavior Vss which now satisfies
V (m
The convergence rate is still dominated by V, V as in Corollary D.10 which gives (12))
E Federated Blended Optimization
In federated blended optimization, we distribute local optimizer strategies during the subsampling process which may be formalized as functions that take input the availability of client resources,
41

---

Algorithm 5 Server-side ADAGRAD and client-side optimizer mixture (FedAda²)
Require: Local optimizer strategies O1, 0y....9 Oop (e.g. Adam, AdaGrad, SGD...) Require: Initializations 2o, 60 - and mo f- 0
Require: Global decay parameter 31 E (0,
1: for l,l,..., do
2: Sample participating client multiset S for each optimizer strategy / [Op]
3: for each sampled client collection I E [Op] (in parallel) do
4: for each client E St (in parallel) do
5:
100 f Øt-1
6:
2 (,)( t Optimizo(OI, i, 20 Clip = True)
f.
A/ w(11) (x.-1 (1 - 2t-1)
7:
8:
end for end for
9:
10:
S < Eielopl |
A. $ EiEjOnl Dies And
11:
M. Bim--1 11-1100 B1
13:
T = 8- + A
14:
-1-1 Vou+r
15: end for
and outputs the number of local epochs. K (OO),, as well as additional hyperparameters such as delay step size or preconditioner initialization. These may be chosen to streamline model training based on a variety of factors, such as straggler mitigation or dynamically restricted availability of local resources.
In the general formulation of FedAda?, blended optimization allows the trainer to utilize the unique strengths of each individual optimizer, balancing resource constraints and client noise. Each client has the option to run different optimizer strategies as the training rounds progress, depending on varying individual resource constraints or distribution shift in the local data stream. This faithfully corresponds to real-world settings where the availability local resources are actively dynamic. Future work will provide empirical results the performance of blended optimization, including identifying the settings in which mixing optimizer strategies are advantageous for distributed learning. The following theorem shows that under certain rontrestrie conditions, blended optimization still allows for convergence of the global gradient objective. We first present a paragraph on the key intuitions and insights behind the proof to improve accessibility.
The convergence guarantee for Federated Blended Optimization is obtained by treating each client's local optimizer (e.g., SGD, AdaGrad, Adam, SM3) as black-box whose per-step preconditioner and scaling factors uniformly bounded. First, one shows that single client update can blow up, i.e., its total local drift | is bounded by Φ and similarly the server- side useudo-gradient remains bounded by $ Smoothness of the global objective then lets us decompose the inner product between the true gradient and the aggregated update into two parts: small "denominator-drift" term that is absorbed into the variance, and main descent term that, after introducing an auxiliary pivot "rr and choosing appropriate weights ar, yields a guaranteed reduction in gradient norm. Telescoping the resulting inequality with geometric-serice weights recovers the same (1I/VT) nonconvex rate in SM3-FedAda ++. In this way, federating over multiple heterogeneous optimizers requires only uniform bounds on their preconditioners and step- sizes, and no change in the high-level convergence rate, provided each strategy respects these minimal stability conditions.
Intuitions.
Theorem E.1. Let Assumptions 1. 2 hold. Given client i [N], strategy E [Op], global timestep T, and local timestep p. assume that the optimizer strategies satisfy the parameter update rule
x
11
...
42

---

where
< my & ". .ith) - Mi and < at S o.d - A.
for all possible values of,, r. 1f1 K(O) S K and < = w(O)) Et, then Algorithm
admits identical convergence bound as Theorem D.6 with V V4 replaced by
3/3 = (1 31 mm CT 10
444 (1 11.1) -B))mCCTL(BBB)lle 1??
C (=+) [ + 1)(naxie(Op)) Af)
2ā17 min mi
The intermediary 71, ã1 values are defined as
E- mm 01 71 T) maxte(Op) Mi ã1 K(K + 1) maxte[Op) Mi
E mi oz
We have opted to provide looser bound for expository purposes, and the proof straightforwardly generalizes to finer bounds that depend on the individual characteristics of the optimizer strategy (c.g. m,, M, At, etc). The extension server-side Adam updates follows analogous steps to Section D.2
easy show that under the bounded gradient assumption (Assumption Adam, AdaGrad, and SGD (including under SM3 for the former two) all satisfy the optimizer condition depicted in Theorem
E. In Appendix and G we materialize two realizations of this framework as additional examples, using client-side Adam and AdaGrad with delayed preconditioner updates. Note that delayed updates require the debiasing term Adam to be adjusted accordingly. To prove Theorem E.I we begin with the following lemma.
Lemma E.2. Under Algorithm
A 1 is bounded by
の E K(K + maxie(Or) AG
2 min)et(n) my
and the server-side pseudogradient is bounded in absolute value by
T min min { 1 (1-
B:) B7t) T
Proof. Unraveling the definition of A. have
K(O)) Σ
rd
= -ee(())
Le .....
which immediately gives
K
A.G
K(K 1)A
A 1 S
E
= +
mi
2m
p=1
For the server bound, the proof is identical to Lemma D.2
We are now ready to prove Theorem
Proof. As the proof follows similar structure to Theorem 4.1 we provide only an outline for repetitive steps while focusing on differing aspects. As before, L- smoothness gives that
2
3 mo + (1 E4
f(x.) & f(z-11) 1/1o,0 +(1 --mm
Torr
Vū, +
(14)
43

---

where for r E [t].
Tor = B/- (V((oo)))))
Ar
3 m0
and To,0
v (f(=)-1);
V
+
V8r +
Decomposing Tor
A.
A,
Dr
To. = 3/-
(f(x)-1);
+
Vf(++11);
vo +
V +r
v 00-1+7
Ti.
P2.r
Ti, is bounded by
|
G
A?
Trr 1
Σ
T
11
For T2 we aim to apply further decomposition for > 0,
vf(x(-1)
vf(x-11)
T2r 31-
Ar 2
vf((c-1)
-7.11 3t-
Vūr-
1/-1 +T
21.
Unraveling the definition of A, gives
K(O))
w(Oi)a rd
A, 1
Σ
ΣAA
-TE
Σ
Σ
Eie(on) |ST
Eie(on)
|ST|
LE(Op) FEST
lE(Op) NEST p=1
which induces the following value
K(O)) P Σ
wOi)a r.
TJt
ΣΣ p=1
if
Σ N
ElEOopl |St
1E(Op) iESt
E=1
1E(Op)
For the purposes of the proof, we shall consider local device to have been dropped and unsampled if any runs less than 1 epoch. Then, we have
E min at
3 K(KK + 1) maxie(Op)
Ve
Fi, 7o)
Me
max M, .M6
2 minngeopn Mi
44

---

Expanding T22, for of > 0 to be fixed,
vf(x(-1)
8--"
Vū--1 Ar + 71 Vs(x+-1)
B9-
K(OS) p
(V gite)
Eie(on)
|ST
V
1.1
(E(On) iEST
p=1
vf(xz-1)
Σ lE(Op)
df Σ
((O)(((())) +1)
Ei |ST|
V +T
iESi
Me. 9r-
Σ+Σ
Σ
Σ
k(O))
w(O (V[(x,-1) - (F
+ 2 2 (c((Or) SS)
01 ....) V
iES
p=1
17P1
51
max
K( + +1)
V (Ir-1)
4
VV--i++ +T
K(O)) P
ne (
A3
Σ
Σ
Σ
-
2T
EiE(OM)
[ST
a.mi iEST
1E|Op]
p=l
We aim to control the first term by setting for all / E [Opl
7' TkK(K +1) [ā),āz]
E minee a
Et + 1) maxie ai
K(K + 1) maxie Op) Mi 2K(K + 1) minee(pp) Mi
Via gradient clipping as before, we have
| - V- ) S
- 22((t)))(100 12 10 11 1
Noting that
K(o))
1/ 31 (
A
1f VF-(0),
2r EiE(Opl [S)]
a
1E(Op)
YEST
p=1 t=1
< Th <2 + (max)c))pp) A?)
2ā1 minee(Op) mf
collecting terms into equation 14 gives that
31
LK 1|2
| |G0
f(x)) S (xx-1) + TTo, + I
+ (1- Σ
Viz +
72
T
2ic
KK(K + 1)maxxiejopl A7)
+(1 +11-3 (1-3))mm
(1
1
2 minie(or) mi
3 3
vi(xe1)
+(1 (1-3m)m
(15)
4
45

---

By initializing ma + 0 and enhancing the upper bound by substituting Y1 into Yr telescoping gives
2
3(1 B1 1
(
- {(00) - f(x") (1 31 3m G|G
A
VV
1² LTd 1
+1--Bammc
+
(16)
72
Again by noting that
2
3(1 3 mm
T
Vf(=111)
3(1 3, )nFT
min
4
VV-+i++ +T
( 112 8o +
TE
Lemmas
D.7 and
D.8 give that
3(1 31) T
min TE
[V((==-)|| S (z00) - -(xx)
4 [v 12 8o +
+ (1 3 DT. CTII 1 + (TL)),CTLL((())001
nd | (1 31 log
11 T K 11² ,²
This implies that
11 U2
U/ + 4/4 + Ms
min TE
V8
where
4 f(xo) f(x"),
122 LTd 2
72
1 = (1 mm M
V (1 L
7dllo ||G (1 - 31 log 1 1
T/
72
V3
3(1 3-:
V6
4 (VTI 122 Jo +7)
C (E+) 2 + 1)(max(e(0)) (Op) AP)
2 min mf
The intermediary 7, āi values are defined as
E min 4i
(in 0z
71 = (axte(Op) Mj
ō := K(K + 1) maXte(Op) Mi
F Adam with Delayed Updates (ADMU)
Considering client-side resource constraints in the federated setting, we propose an adapted version of Adam with delayed precondtioner updates aimed at relieving the cost moment estimate computation in Algorithm 6 which we call ADMU.
46

---

Algorithm 6 Adam with Delayed Moment Updates (ADMU)
Require: T/: Step size
Require: z Z21: Step delay for second moment estimate updates (where gives delay)
Require: 81. 52 E [0, 1): Exponential decay rates for the moment estimates
Require: f(x): Stochastic objective function with parameters
Require: zo: Initial parameter vector
Require: & 0: Smoothing term
1: Initialize me + O (1st moment vector)
2: Initialize Ug f 0 (2nd moment vector)
3: Initialize & -- 0 (Timestep)
4: while not converged do
5: I < 1 +1
6: 9t +- (=
7:
my $1 ----1 + (1- 91).90
8:
in + m (3)
9:
if - 1)/2 2 then
10:
Ut - 32 -0- + (1 (2) gt
0. 11/(1 B2 (11
11:
12:
else
13:
81 i2-1
14:
end if
15: Fit ft-1 me mu/ (V E)
16: end while
17:
return 24
we provide an intuitive justification for the initialization bias correction employed in ADMU. Recall that the motivation for adaptive step-size in ADAM is updating the parameters via empirical estimates of the pseudo-gradient B[g]/> V E[gHT. which allows for both momentum and autonomous annealing near steady states. The square root taken in the denominator to homogenize the degree of the gradient. Bias correction for ADMU adheres to the same principle, while requiring an additional assumption of gradient stabilization during the z-step preconditioner update delay. An equivalent formulation of the moment estimates in Algorithm for general t is given
Following 10
m = mp.3 + (1 B1)
Dr.
1 = 10 20 +
1=1 +1-111
+ +(1 (1-
(1) 322
32
11-1=---1 ① 0 :ecll=-st1x((=_eeee ((=)eegg))
r=1
11
= 3 2
1+1
11
+ (1 - 32)
3
9(r 1)++1 ① 00--))2++
(17)
We work with as the proof for is analogous with 1. Assume that the gradients gI.... ge drawn from latent gradient distribution 9: D(g:). We aim extract relation between the expected delayed exponential moving average of the second moment B[vy] and the true gradient expectation E.gg]. Taking expectation of both sides in equation (1).
Bie]] = vo.3
+ (1 - 32)
2
E
g
g 1)a+1
11
2 + (1 - -B2)B [
1=1
2 Elgz' 11 - 1= }
47

---

Here, we have used zero initialization for the first moment estimate, while accumulating any enror terms in Ç. Several assumptions can lead small Ç. As [TO], we assume that B1 chosen small enough that the exponential moving average decay undermines the influence of non-recent gradients 9e for i < < - 2 + 1. A second assumption is that the latent gradient distribution remains stable during the z-step delay as training progresses, allowing the approximation E[g.] 1 1
This leaves the residual scaling of the true gradient second moment of the form 1 - 3 which is caused by (zero) initialization as setting to = Elgn] eliminates 8r. Therefore, bias correction is enforced by scaling the empirical estimate by the inverse. We note that need not be initialized
to O, in which case we should additionally translate i2 by -0 = [+1 prior to the inverse scaling.
F11 Non-convex convergence analysis
Algorithm 7 Adaptive server-side ADAGRAD and client-side ADAM (FedAdaAdam)
Require: Update delay step size Σzι. initializations To, 0o 2 72 and mg
Require: Global and local decay parameters B1 32, 31, 32 E [0, 1)
Require: Pscudogradient weighting schedule = x... x = E RIS
x .... x R I for | S B
Require: Client epoch schedule K² x ... K² 2/81
x .... x Z 2SS"
for K 11 S K, VI E [T]
Require: Local epsilon smoothing term E, 0
for t 1,....,. do
2: Sample subset St C [N] of clients
3: for each client E S (in parallel) do
4: .r..0 <- I--1
5:
Initialize mo: up 2 with default values mo, no +-
6: for k = 1..... K2 do
7:
Draw stochastic gradient Dh,k ~ D() with mean (F E Rd
8:
my + 31 m + (1 - 31) gh 84)
9:
my m2/
10:
if (k: 1)/z E E then
Uk 32 uk + (1- (1- gi.n gh.k
û% u2/ (1 3/3 ( else
13:
Uk fk-1
15:
end if
16:
i < | (itg/(Virr Uh + e)ll < E. then
17:
m&
+ 0
18:
end
19:
L 21 -1,k-1 -
11 /i/e (V +
20:
end for
(1' i,k; =1-1)
21:
A -
22:
end for
23:
A [st Σ Eies: A
24:
M. B 1 + (1- (1-3:)A:
25:
& /- + A?
26:
_1-1 VittT
27:
end for
A description of FedAdaAdam is given Algorithm 7 A few remarks are in order. Firstly, to allow for straggler mitigation, we allow the number client i epochs K² at timestep to vary among the clients E S, Although Algorithm 7 sets a schedule for client epochs and pseudogradient weights for clarity of exposition, dynamic allocation still allows the convergence proof to go through, as long
as the schedule weights are bounded. By default, set K' K and E B 1 to avoid tuning
48

---

large number of hyperparameters or having to sample from a client epoch count distribution for the client subsampling case.
Secondly, for the purposes of the proof we shall consider a local device to have been dropped and unsampled if any runs less than epoch. We also enforce that pseudogradient weights bounded positively from below, i.c. = > Ew > O. We now provide a convergence bound for the general, non-convex case which holds for both full and partial client participation.
Corollary F.1. For Algorithm 7 we have an identical bound to Theorem 4.1 with V3, VA replaced by
V/- (1 BT ym
20
V (1 B1)mm((1111
11
2ā1
Here, the intermediary 7, ōn values are defined for == min;, K2 2 1 as
1- 3P
Ew (1 - -BP)
h1 7EW Σ
GV
32 +
GV 1 82 41 +5) (K + 1)2
The proof is subsumed by or analogous to Theorems and following lemma.
E.1 with changes summarized in the
Lemma F22 Under Algorithm 7
A
is bounded by
1-
Φ
E
ne
+ $ K
3
1
where
G1- BR.
$ K
Recall that A, = 1/1S" EiEs: A and A = E =f.0). By telescoping for K
Proof.
local steps and the definition of gradient updates in ADMU, we obtain
K
K
m + - (1-1:)) Dp 35 gh.r
mip
A
00p +E
ا (1 (2) Σ - 3
12 (111""0l, (0-,4111)241) e
0o
We assume Mo. + 0 for expository purposes, although to > 0 also suffices for the analysis (ending in a slightly different & K This gives that
(1 31)
8p- Dh.
A =
(11 - 32) Σ
(of (r- 1)2+1 )2
p=1
K
(1- 31) Σ 1
D (1
= p=1
(1 32) Σ 11 8
"(g" (0,(1- (r- 1)2+1 )2 22
K!
(1 B1) Σ ph 3
Li Xpp p-1 $2)
B2)
11
)2 +
49

---

To obtain a deterministic bound, we cannot ignore the worst-case stochastic realization that Ri,r--)== for Vr [[] Therefore, we form the intermediary upper bound
K
(1 (1- (1-
3 1
96.(r- 1)s+1
إ S E
(2)
-=1
(32
"ol (r 1))+1 )2 +
ne 11 31)
1ot xge 3-' p=1r=1
(18)
Note that the first term is 0 in the worst-case scenario above, which implies that any non-negative upper bound trivially satisfied. Therefore, we may assume without loss of generality that least one sampled gradient 9 (1,(r-1)s+1 is nontrivial and remove from the denominator to obtain an upper bound. By Cauchy- Schwartz, we have
E Σ
1&1 Σ
21
1 Σ 3
2
8
1r
-
which implies
21 -1-2 2r
K
+ Te E (1 (1- B1)
S
Σ
37 3p-T -1ghrl x9
B2
r=1
K
1
22 21 2r
K 1 - -B). (1 (1-
<
Σ
+
$2 -r
(1- 31)
2r
K G. - 3K
< K
E
$2
It can be shown that case of no update delay allows for h0 = 0, following a similar proof to
the given above. Note that क6 handles the superfluous gradient terms cemented by delaying preconditioner updates for the second moment, while moving averaging is performed for the first moment estimate. It also follows that A, is also upper bounded by the identical bound scaled by max, 1bo < B, as the average of the A.
G AdaGrad with Delayed Updates (AGDU)
We present AdaGrad with delayed preconditioner as Algorithm g for completeness.
Note that due to delayed updates, local gradient updates absolute value by Me- We may expand the delayed updates for 2/ as
necessarily elementwise bounded in
re1
Σ
t = vi +
gir- 1]s+1 3 9(r-1))++1
We have the following convergence bound.
Corollary G.I. Let K min;, / K > 1 and
K
1
3 = mw
ă1 ==
Do + 1K +E
2K
(V
10 +
K
G² +
2
Then Algorithm 2 has identical convergence bound to Theorem
4.1
50

---

Algorithm 8 AdaGrad with Delayed Updates (AGDU)
Require: Ne: Step size
Require: 2 E 2>1: Step delay for second moment estimate updates (where & gives no delay)
Require: [ax::: Stochastic objective function with parameters
Require: zo: Initial parameter vector
Require: e >> 0: Smoothing term
1: Initialize f 0 (2nd moment vector)
2: Initialize - 0 (Timestep)
3: while not converged do
4: & 1+1
5: + -=f((2:-1)
6: if (t 1)/2 then
7:
+ 11 + g
8:
else
9:
6- 1/-1
end if
11:
+s) 2t-1 mE (t/(/er +s)
12:
end while
13:
return Ztz
Algorithm 9 Adaptive server and client-side ADAGRAD (FedAdaAdagrad)
Require: Update delay step size E žΣ1, initializations To, 0o 2 72 and mo +
Require: Global decay parameter 31 E [0,
Require: Pseudogradient weighting schedule 3 x.. x E RRS .... x R S for E S B
Require: Client epoch schedule K²
K 2 x... x - for | 11 S K, vt [T]
Require: Local epsilon smoothing term e, O. global smoothing term
1: for = =, do
2: Sample subset St c [[V] of clients
3: for each client E St (in parallel) do
4: =t,0 < F4-1
5: Initialize vo 2 0 with default value < 0
6:
for 1 1.... K do Draw stochastic gradient Df,a ~ D(x(fa-)) with mean VF E Rd
7:
8:
my g4.e if (k: 1)/2 then
9:
10:
Uk + uh + gi,u ① 9
11:
else
12:
Uk Uk-1 end
13:
0
||m//( (mx//Vur Uu + E)ll E, then
15:
m, +- O end if
17:
zi - x ii,--
- T16 m [v
18:
end for
19:
A =
3
(a. i
x1-11)
20:
end for
21:
A:
Σ Dies: D;
m 8-m-11 + (1- 3.)A.
23:
T = 1- + A
24:
= 1 + o
25: end for
51

---

Similar to delayed Adam, the proof is analogous to Theorem following lemma.
with changes summarized in the
Lemma G.2.
Under Algorithm 9 | is bounded by
K K-1
KG
| S $
B
+1+
v +
Proof. Recall that A,
1/|8") Eies: 4 and A
3
(at
- x4,0)
By telescoping for K;
i.
local steps and the definition of gradient updates in FedAdaAdagrad, we obtain
K
K
Di.p
A
mp -
Up +e
p=1
+
Σ
(9) (r- 1)=+) )22 +
For F = {0, l...., (K 1)/2|}3 1, we thus have that
di.p
A - Σ
PEf
00 + Σ
15" -r=1
PiP
PE[K U0 E1E1 11
11
+2
To obtain a deterministic bound, we cannot ignore the worst-case stochastic realization that 0 for Vr [[[]]. Therefore, we form the upper bound
(1(r-1)2+11
A
M/
1
Σ
+ 10 + ΣE
(0 te
st.pl
(19)
UD + &
PE KI
K -
KKEK / +
Me
+1
where the last line uses that the local epoch schedules are upper bounded by K. Noting that |Eflle I B, we are done.
H
Datasets, Models, and Baselines
Below, we summarize the dataset statistics and provide more in-depth description.
Table 2: Summary of datasets and models.
Datasets
# Devices
Non-IID Partition
Model
Tasks
StackOverflow [27
400
Natural
Logistic Regression
500-Clas Tag Classification
CIFAR-100 28
1000
LDA
VIT-S
100-Class Image Classification
GLD-23K 30
233
Natural
ViT-S
203-Class Image Classification
PEMNIST
500
Natural
ViT-S
62-Class Image Classification
H.1 StackOverflow Dataset
The SverlOwe dataset [27 is a language dataset composed of questions and answers extracted from the StackOverflow online community. Each data entry includes associated metadata such as tags (e.g., "python"), the time the post was created, the title of the question, the score assigned the question, and the type of post (question answer). The dataset is partitioned by users, with each
52

---

client representing an individual user and their collection of posts. This dataset exhibits significant imbalance, with some users contributing only a few posts while others have a much larger number of entries. In this paper, we work with randomly selected 400-client subset of the full StackOverflow Dataset, with a client participation fraction of 0.1.
DP StackOverflow
DP StackOverflow
DP StackOverflow
DP StackOverflow
Feihig
Todleg
Foiling
Fecling
Test Accuracy
Train Accuracy
Text Loss
Train Loss
Toblar
Fublar
Facker
Communication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
Figure 5: Identical setting as Figure | except that 1 local epoch is taken instead of S. Additionally, the adaptive baseline algorithms employ the Adam optimizer instead of AdaGrad. We observe that jointly adaptive methods significantly outperform server-only adaptive methods, which in turn outperform non-adaptive FedAvg. The setting studies the noise multiplier a 1, with a privacy budget of (c, = (13.1, 0.0025) with optimal Rénfi-Differential Privacy (RDP) 39 order 2.0.
H.2 GLD-23K Dataset
The GLD-23K dataset is subset of the GLD-160k dataset introduced in 30 It contains 23,080 training images, 203 landmark labels, and 233 clients. Compared to CIFAR-I0/ 10/100, the landmarks dataset consists of images of far higher quality and resolution, and therefore represents a more challenging learning task. The client participation fraction for all GLD-23K experiments are set to 0.01.
GLD-23K
GLD-23K
Pseudo Gradient
Pseudo-Gradient
Fachag
Fabliy
Test Accuracy
Norr Mcan
Noorr SD
Test Loss
Fallatiees Coly Fabla?"
Communication Rounds
Communication Rounds
Communication Rounds
10
Communication Rounds
GLD-23K
GLD-23K
Gradient
Pseudo-Gran Gradient
Takles
Tackes
Test Accuracy
NoNorm Mcan
Text Loss
Ale.
Norm SD
Fachi
Communication Rounds
Communication Rounds
Communication Rounds
20
Communication Rounds
Figure 6: (Top) Additional results for the experiments in Figure 4 (b), where clients train over 5 epochs. (Bottom) Analogous experiments for full fine-tuning, where the entire net is unfrozen after replacing the classification layer. All adaptive optimizers are instantiated with Adam, with the exception of FedAdaGrad where the server-side adaptive optimizer is AdaGrad.
H.3 CIFAR-100 Dataset
The RIFAR-10/100 datasets 23 consist of 32 x 32 x images. In the smaller variant CIFAR- 10, there are 10 labels, with 50,000 training images and 10,000 test images. The 10 classes represent common objects: airplanes, automobiles, birds, cats, deer, dogs, frogs, horses, ships, and trucks. CIFAR-100 is meant to be an extension of CIFAR-10, consisting of 60,000 color images, but with 100 classes instead of 10. Each class CIFAR- 100 contains 600 images, and the dataset is similarly split into 50,000 training images and 10,000 test images. Unlike CIFAR-10. every class in CIFAR-100 subsumed by one of 20 superclasses, and each image is provided fine label and a coarse label that represents the former and latter )caas. In this paper, train and evaluate all algorithms
53

---

against the fine label. In Figure 7 we show the convergence of FedAda² as compared to all other adaptive or non-adaptive benchmarks using CIFAR-100.
CIFAR-100
CIFAR-100
CIFAR-100
CIFAR-100
Fullig
Faclon
Test Accuracy
Train Accuracy
Fachian hecler
Test Loss
Tublar
Train
Communication
Rounds
Communication Rounds
Communication Rounds
Communication Rounds
Training and testing accuracies of optimal hyperparameters for CIFAR-100. At each logging step, train/test accuracy and loss evaluation is done over all of training and testing data, disjointly, resulting in robust and similar-looking curves. Averaged over 20 random seeds for better convergence. Adaptive optimizer instantiation conventions are identical with Figure Though minimal, jointly adaptive baselines (Costly Joint Adaptivity, FedAda², FedAda outperform server-only adaptive baselines (FedAdam, FedAdaGrad) and non-adaptive FedAvg.
Figure 7:
H.4 FEMNIST Dataset
The FEMNIST dataset 29 extends the MNIST dataset [50] to include both digits and letters, comprising 62 unbalanced classes and total of 805,263 data points. It is specifically designed for federated learning research, featuring a natural, non-IID partitioning of data. Each user in the dataset corresponds to distinet writer who contributed to the original EMNIST dataset, capturing the individuality of handwriting styles. This user-level segmentation provides a realistic federated learning setting, simulating scenarios where data is distributed heterogeneously across clients. FEMNIST serves as a benchmark for evaluating the performance of federated learning algorithms under non-lID conditions, emphasizing challenges such as personalization and robustness client heterogeneity.
FEMNIST
FEMNIST
FEMNIST
FEMNIST
Acquracy
Train Accuracy
Test Loss
Tram Loss
Foblee
Pockey
Rockss
Communication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
FEMNIST
FEMNIST
FEMNIST
FEMNIST
Peeling
Test Accuracy
Train Accuracy
Test Loss
Trely
Train Lass
Fally Tacher.
Tabla'
Tokkifial Feckiss
Communication Rounds
1s
Communication Rounds
10
Communication Rounds
Communication Rounds
Figure 8: Training and testing accuracies of optimal hyperparameters for FEMNIST, with 0.5% participation (2 clients per round). Averaged over 20 random seeds for clearer convergence. Adaptive optimizer instantiation conventions are identical with Figure 6 where jointly adaptive optimizing paradigms use Adam due to better performance. We see that FedAvg is the least robust, both in terms of stability (i.e., confidence interval region) and final performance. By contrast, adding server-side adaptivity greatly strengthens the performance, and introducing client-side adaptive optimization further enhances the speed of convergence as well as test-time accuracy. We see that removing preconditioner transmission, and compressing client-side gradient statistics to save on-device memory as in 2 does not detract from the performance of joint adaptivity. The top row displays the results when each client takes 5 local epochs prior to server synchronization, where the gap between the jointly adaptive and non-adaptive baselines is more pronounced. The bottom row gives the results for 1 local epoch.
54

---

H.S Descriptions of Baselines
In the original FedAvg algorithm introduced by [ the server-side aggregation is performed without any additional momentum, relying solely on simple averaging. On the other hand, algorithms like FedAdaGrad and FedAdam represent examples of server-only adaptive approaches 44, where the server employs adaptive optimizers such as AdaGrad or Adam instead of vanilla averaging. We note that server-only adaptive frameworks such as FedAdam and FedAdaGrad are optimizer- instantiations of FedOpt [4) competitive framework that has been utilized in recent works to develop leading applications (e.g., by Google Deepmind to develop DiL.Co [1 52 ). The concept of
"Costly Joint Adaptivity' (Costly Joint Adap.) refers to a training paradigm where the server's adaptive preconditioners are shared with clients during each communication round. An example of this the AdaGrad- AdaGrad-AdaGrad AdaGrad setup used as differential privacy baseline in the StackOverflow task, where the server-side AdaGrad preconditioners are applied to client-side AdaGrad optimizers, guiding client model updates.
Alternatiell,, by eliminating the transmission of server-side preconditioners and initializing client- side preconditioners to zero, we derive the 'Joint Adaptivity without Preconditioner Communication (Joint Adap. w/o Precond. Commu.) baseline, which is more compressing local preconditioners align with client memory constraints leads to the development of FedAda Thus, FedAda2 and the various baselines can viewed as logically motivated extensions, incorporating adaptive updates and memory-effcient strategies. We provide comprehensive evalua- tions of all 15 algorithms (including 12 jointly adaptive methods tailored to each adaptive optimizer, 2 server-only adaptive methods, and non-adaptive method) in Section 5 and in the Appendix H
catpuuiiictiio-ffffcieeeeee Further,
For the VIT model for instance, we require just 0.48% memory store the second moment EMA compared to the full gradient statistic during preconditioning when using SM3.
I Hyperparameter Selection
L1 Hyperparameters for DP StackOverflow
We use subsampling rate of 0.1, for a total of 400 clients and 500 communication rounds. We investigate the setting of noise multiplier 1, which provides privacy budget of (c, ò) (13.1, 0.0025) with optimal Rényi-Differential Privacy (RDP) order 2.0. We sweep over the following hyperparameters:
e (0.1,
" E (0.001, 0.01, 0.5, 1),
f/ (0.001,,0011,01,0055, 0.5,
7 E $10 3)
Ta E {10-7,10 10
where e the gradient clip value. Here, m, 7/s indicates the client and server learning rates, while T, represents their respective adaptivity parameters. In the case of singular adaptivity, we ignore the irrelevant terms (i.e. client adaptivity parameter for FedAdaGrad). For FedAvg only, we select best hyperparameters using the expanded local learning rate grid
MJ (0.001, 0.01, 0.1, 0.5, 1,5,20, 40, 80, 160)
The optimal hyperparameters are summarized in Table which were chosen based on optimal test accuracy over running average of the last 10 logged datapoints. In Figure 4 (bottom), we see that adaptive optimization on either the client or server induces varying model training dynamics. Notably, we see in our experiments that for this privacy budget, removing preconditioners from jointly adaptive systems supercedes the performance of costly joint adaptivity. Compressing client adaptive preconditioning (FedAda²) reduces the performance slightly, but still performs the best among all other basclines.
55

---

Table 3: Best performing hyperparameters for DP StackOverflow with or
FedAvg
FedAdaGrad
Costly Joint Adap.
Joint Adap. w/o Precond. Commu.
FedAda
1.0
0.1
0.5
0.5
0.1
N/A
1.0
1.0
1.0
1.0
20.0
1.0
1.0
0.1
0.1
Ts
N/A
1e-3
1e-3
le-5
le-5
N/A
1c-3
lc-3
lc-3
1.2 Hyperparameters for Image Datasets
For all ViT experiments, images were resized to 224 224 pixels, and the client optimizer employed a linear learning rate warm-up, increasing from 0) to the final value over the first 10 local backpropaga- tion steps. The local batch size was consistently set to across all datasets used in this paper. Due to better empirical performance, Adam selected as the main optimizer strategy for VIT fine-tuning against the image datasets. We utilized prior work 4 as well as small-scale experiments regarding server-only adaptivity guide the selection of the momentum parameters 81 = 0.9, .2 0.999 for server Adam. The identical parameters were selected for client Adam, and better choices may exist for either the server client. In order to determine suitable learning rates and adaptivity parameters, we conduct extensive hyperparameter sweeps using a two-step procedure.
(Step 1)
The first step involved symmetric sweep over the values ! E {0.001, 0.01, 0.1, 1, 20}, V) 0.00,,, 1,5, Ti (10-3.10_7,1003100-3
T3 E {10-9. ,,000,,00,1100,,10000
Similar to the StackOverflow case, 7, indicates the client and server learning rates, while n; T, represents their respective adaptivity parameters. For FedAvg only, we probe over the expanded grid
m {0.001, 0.01, 0.1, 0.5, 1,5, 20, 40, 80, 160, 320).
(Step 2) Based on the sweep results over all 10 algorithm and dataset combinations, second asymmetric search was launched the most promising hyperparameter regions, which probed over the following:
M 3:0
10 N E : 11-
10 10
E 1000
To E
10 9.10 5]
Afterwards, the best performing hyperparameters were selected. For FedAvg only, the final grid increased additively 10-3 from 10 to 10-2 then by 10-2 onward until the largest value 10-1 That is, we sweep over the following:
T7| {0.001, 0.002, 0.003, .... 0.009, 0.01. 0.02. 0.099, 0.1).
For server-only adaptivity FedAvg, any irrelevant hyperparameters were ignored during the sweep. In Tables SablesJanii [] we summarize the best performing learning rates and adaptivity parameters. this subsection, any notion of adaptivity in jointly adaptive systems refers to the Adam optimizer, and local epochs were taken prior to server synchronization. Full fine-tuning indicates that the entire net was unfrozen after replacement of the linear classification layer. For FedAdaGrad, full fine-tuning, Step 2 utilized an expanded hyperparameter grid search due to poor performance.
Table 4: Server/Client Learning Rates n//m
FedAvg
FedAdaGrad
FedAdam
Costly Joint Adap.
Joint Adap. w/o Precond. Commu.
PočAda
3
1e471e3
le-/1e3
le33/le3
le-3/
1e-3/
CIFAR-100
NIA 1o-1
1e-2/1o5
1e-3/
1o-3/162
lo-3/ le-2
16:3 le-2
GLD-23K
/0.4
1e2//e62
le-3/
le33/
16-3
GLD-233 (Full)
NIA 0000
1e4/1e2
1e4/1e2
1e4/1e4
1e4/
le4/ 1e4
56

---

Table 5: Server/Client Adaptivity Parameters T./m1
FedAvg
FedAdaGrad
FedAdam
Costly Joint Adap.
Joint Adap. w/o Precond.
PedAda
FEMNIST
NIA NIA
1e-7 / N/A
1e-7/NIA
le-5/le-7
le-5/
1e-5 le-7
CIFAR-100
NI
le-10/N0
le:5/
1o-5/10
1c-5/10
1e:5/100
GLD-223K
NIA / NZA
le-5/NIA
1e-S/NIA
le:5/0.1
le-5/0.1
le-5/0.1
GLD-23K (Pall)
WAYNA
16-2/N/A
1e-5/N/A
le-5/1e-3
1e-5/1
1o-5 le-3
The setup was almost analogous to above, The only difference is that due to limited resources in (Steps 1-2), we swept over the grid
Hyperparameter Sweep for FEMNIST.
E 11005,10~$_100 ",00,00000
R 100
a 110-,,1033.10)) T, E (10-7,10 10-
For FedAvg only, we utilized the expanded learning rate grid
T {0.001, 0.002, 0.003.0......... ..., 0.009, 0,0,,000000000002..0,00000111111
Hyperparameters for varying client resources, GLDD-33. Analogous sweeps in (Step 1) above for the limited and sufficient client resource settings (locally training over 1, 20 local epochs prior server synchronization) were taken. For the constrained setting, there were no changes the (Step 2) grid. In the abundant setting, the modified final search space for adaptive methods was
T E { 10,,000,,100,01--1-- 10-3 10-2,10-14
E 1
10_ 16, 16.
10
Tg E (10-12,10-11111
10 10 90105]
and the optimal hyperparameters are summarized in T
Table 6: Hyperparameters for GLD-23K under restricted/sufffcient client resource settings
FedAvg
FedAdaGrad
FedAdam
Costly Joint Adup. Joint Adup. w/o Precond. Commu.
FedAda
14
NIA
le-2/ le-2
le-3/ le-3
le-3 le-3
le-3 / le-3
le:3/ee3
7e-27 le-2
le-2/ le-2
le-1 le-2
le-2/ le-3
le-2 le-3
/ee1/1e-
NIA NIA
1e-9/
le-5/le-
le-5/ le-7
le-7
le-5/le7
NIAN
NIA/NA
NIA/NIA
le-3/ Ie-1
le-3/ / le-1
/e-1/
1.3 Compute Resources
Experiments were performed on a computing cluster managed by Slurm, consisting of nodes with various configurations. The cluster includes nodes with multiple GPU types, including NVIDIA RTX 2080 Ti, A40, and H100 GPUs.
J Additional Experiments
J.1 Sensitivity to Hyperparameters
J.2 Dynamics of Heterogeneous Client-Server Adaptivity
In Figure 10 display the effects of heterogeneous client-server adaptivity in the setting of VIT fine-tuning over GLD-23K. All hyperparameter sweeps were done over the following grid:
m 110 10-11,00111
10 10-1)
7
(20)
a [10-7,10-5, 10-3 1 ,1]
T, 100-7,10 10-3 10
57

---

Aed
FedAdaGrad
Costly Joint Adap.
Test Accuracy
0.20
Test Accuracy
0.20
Test Accuracy
0.20
0.15
6.10
0.10
0.10
0.00
100
500
400
0.00
100
200
500
400
0.00
200
300
400
Communication Rounds
Communication Rounds
Communication Rounds
2edAda 2
F ++
Test Accuracy
0.20
Test Test Accuracy
0.20
0.15
0.15
0.30
0.05
0.05
Communication Rounds
Communication Rounds
Figure 9: We plot all test accuracies obtained during the hyperparameter sweeps detailed in Ap- pendix [.I] with fixed client subsampling random seed. The runs are ranked hierarchically from the lowest to the highest final test loss, with the colors transitioning from lighter to darker shades accordingly.
J.3 Effect of Delayed Updates
Similar to Figure 10, we demonstrate the effects of delayed updates in Figure [] Hyperparameter configuration for delayed updates is identical to Figure (b), except that client-side preconditioner updates are delayed. Hyperparameter sweeps were done over the following grid:
"h E 1002 10-1),
E
E (10-3,
(10-5,10-3 10-1)
We see that delaying the computation of the preconditioners does not significantly degrade the performance.
58

---

AdaGrad-AdaGrad
AdaGrad-Adam
Adam-AdaGrad
Adam-Adam
Test Test Accuracu
Test Accuracy
Test Accuracy
0.4
Test
Communication Rounds
110
Communication Rounds
101
Communication Rounds
20
Communication Rounds
124
353
AdaGrad-AdaGrad
AdaGrad-Adar
Adam-AdaGran
Adam-Adam
Test Accuracy
Test Accuracy
Test Accuracy
Test Accuracy
Communication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
AdaGrad-AdaGrad
AdaGrad-Adane
Adam-AdaGras
Adam-Adam
Test Accuracy
Test Accuracy
Test Accuracy
Test
2
Communication Rounds
52
Communication Rounds
Communication Rounds
20 Communication Rounds
Figure 10: Each test accuracy is color-coded and ranked based on the final test loss, and lighter colors indicate lower loss. Algorithm title colors are also consistent with labels; green for Costly Joint Adaptivity (top), magenta for Joint Adaptivity without Preconditioner Transmission (middle), and red for FedAda (bottom). Title ordering indicates server- and client-side optimizers, respectively: ie. AdaGrad-Adee uses server AdaGrad and client Adam. In the of Costly Joint Adaptivity with heterogeneous client-server optimizers, we transmit the mismatched server-side preconditioner to the client, which to our surprise demonstrates considerable performance. For FedAda", we add SM3 compression to the client-side optimizer after zero initialization the local preconditioner.
59

---

AdaGra
AdaGrad-Adam
Adam-AdaGrad
Adam-Adam
Test Test Accurac)
Test Accuracy
Test Accuracy
Test Accura
Communication Rounds
13
110
232
Communication Rounds
10
101
5.0
292
Communication Rounds
200
Communication Rounds
126
300
Epoch Delay
Epoch Delay
1 Epoch Delay
1 Epoch Delay
Test Accuracy
Test Accuracy
Test Accuracy
Test Accuracy
Communication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
Epoch Delay
Epoch Delay
3 Epoch Delay
3 Epoch Delay
Test Accurac)
Test Accuracy
Test Accuracy
Test Accuracy
Communication Rounds
Communication Rounds
Communication Rounds
20
2t Communication Rounds
Figure 11: After updating preconditioners per every local backpropagation step for the first client epoch, preconditioners are periodically frozen for the next (middle), (bottom) epochs, respectively, for each communication round. Algorithms are consistent across columns, and the top row is identical the FedAdaa results Figure 10 with hyperparameter sweep (20).
60


Reviews:
[{"review_id": "sUAbTPKXJz", "reviewer": "Reviewer_CoJv", "summary": "The paper introduces less resource-intensive adaptive algorithms, FedAda and FedAda++, for cross-device FL, and explores joint server and client-side adaptivity.  FedAda avoids the transfer of preconditioners between server and clients, and FedAda++ uses memory-efficient adaptive optimizers on clients. The authors establish similar convergence guarantees to those of the resource-intensive counterparts like FedAdam for general non-convex objectives with a coordinate-wise bounded gradient assumption.  \n\nPS: Not sure if you really need a superscript $.^2$ in the algorithm's name. What exactly will be difficulty if that is avoided?", "questions": "In addition to addressing the weaknesses mentioned above, see the following:\n\n1. Table 1 does not contain the statistics for FedAdam. Can the authors explain why? It would have been insightful to compare the efficiency and performance of FedAda algorithms against FedOpt algorithms in [2]. \n\n2. The authors state that they aim to increase communication efficiency by minimizing the transfer of local preconditioners, as opposed to other works that use model compression like FedCAMS, FedAMS [1], etc. Can the authors explain or compare the efficiency metrics \nbetween these two approaches? And which one to use in specific scenarios? \n\n[1] Yujia Wang, Lu Lin, and Jinghui Chen. Communication-efficient adaptive federated learning. In International Conference on Machine Learning, pages 22802–22838. PMLR, 2022. \n\n[2] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. International Conference on Learning Representations, 2021.", "limitations": "None.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n1. The FedAda framework permits the use of different optimizers at the client and server sides. \n\n**Weaknesses:**\n\n2. The proofs presented are difficult to follow through and seem to introduce a lot of abstractions without sufficient explanation. A clearer explanation of the steps involved in high-level ideas at some points may aid the reader's understanding of the proofs. Eg., proof (ii) of Proposition A.3. is quite dense and should be clearly explained for better understanding. \n\n3. Line 620 is unclear. It is challenging to assess the validity of the main theoretical results. \n\n4. The experiments are conducted on an array of datasets and demonstrate that FedAda and FedAda++ performs better than other existing popular adaptive federated learning algorithms and are at par with costly joint adaptivity. \n\n4. Overall, the readability of the paper can be substantially improved in the main body and proofs.", "was_revised": true, "final_justification": "I acknowledged the rebuttal of the co-authors. I believe a restructure of the theoretical discussion in the paper to improve its readability is required. Will keep my score unchanged.", "rebuttal": "We thank Reviewer CoJv for their thoughtful review. We appreciate the recognition of our proposed jointly adaptive framework—$FedAda^2$ and $FedAda^2$++—as being less resource-intensive while achieving strong empirical performance and convergence guarantees. Below, we incorporate the reviewer’s feedback.\n\n---\n\n**[Clarity and Proof Abstractions]**\n\nWe agree with the reviewer that some parts of the proofs, such as the second part of Proposition A.3, are dense and could benefit from higher-level explanation. In the revision, we will include more intuitive walkthroughs and clarify proof sketches in the appendix. Specifically, for Proposition A.3(ii), the result shows that under client-side AdaGrad with normalized gradients, the expected iterate norm converges to a noise-dependent constant at rate $\\mathcal{O}(1/t)$, uniformly over client subsamples. The key idea is a decomposition of the update into a contraction term and a noise-dependent residual, showing the decay of the contraction under suitable $\\varepsilon$ and learning rate schedules. \n\nRegarding Line 620, it refers back to the learning rate schedule defined in Line 618. We will make this reference clearer in the revised version. Generally, the abstractions introduced to generalize beyond FedAdam, or to apply a novel regret-based analysis in heavy-tailed settings as done in **Appendix A**, are non-trivial. Some of them were required to accommodate the jointly adaptive setting, where gradients are retained over time and related nonlinearly—preventing the use of standard linear expectation-based techniques. More broadly, we agree that some abstractions introduced in the proofs can be softened, and will include additional intuition and guiding commentary to make the results more accessible for dense derivations.\n\n---\n\n**[About the Algorithm Naming Convention ($FedAda^2$, $FedAda^2$++)]**\n\nWe use the superscript in $FedAda^2$ and $FedAda^2$++ to emphasize a core conceptual novelty: joint adaptivity on both the client and server sides. This setting substantially complicates the analysis—unlike server-only adaptive methods (e.g., FedAdam), the client adaptive updates retain gradient history locally and introduce nonlinear couplings across time, making standard FedOPT-style techniques inapplicable in the analysis. Our convergence proof thus departs from the FedAdam analysis and introduces new tools to handle these technical challenges. We appreciate the reviewer’s feedback on the proof complexity and will work to add clearer high-level overviews and intuitive scaffolding in the final version.\n\n---\n\n**[Table 1 and FedAdam Statistics]**\n\nThe reviewer asked about FedAdam in Table 1– its statistics are identical to those of FedAdaGrad on the client side, as both methods are server-only adaptive methods. For clarity, we will include a row explicitly labeled FedAdam in Table 1 of the revision. The updated table is:\n\n| Method              | Joint Adaptivity? | Communication | Computation (#grad. calls) | Memory (client) |\n|---------------------|-------------------|----------------|-----------------------------|------------------|\n| FedAvg              | N                 | 2d             | 1                           | d                |\n| FedAdaGrad          | N                 | 2d             | 1                           | d                |\n| FedAdam             | N                 | 2d             | 1                           | d                |\n| MIME                | N                 | 5d             | 3                           | 4d               |\n| MIMELite            | N                 | 4d             | 2                           | 3d               |\n| Costly Joint Adap.  | Y                 | 3d             | 1                           | 2d               |\n| $FedAda^2$          | Y                 | 2d             | 1                           | 2d               |\n| $FedAda^2$++        | Y                 | 2d             | 1                           | ~d               |\n\nWe note that $FedAda^2$++ achieves performance comparable to costly joint adaptivity while using *99% less* additional client memory needed to maintain client preconditioners (i.e., only 0.48% overhead when using SM3-AdaGrad with ViT, compared to a full 1× increase in second-moment memory for standard joint methods). This makes $FedAda^2$++ particularly appealing in memory-constrained or differentially private (DP) settings in FL.\n\n---\n\n**[Comparison with FedCAMS and FedAMS]**\n\nWe appreciate the reviewer’s question regarding comparisons with FedCAMS and FedAMS. These methods focus on *compression* of local models for server-only adaptive optimizers, whereas our contribution lies in minimizing *communication* of preconditioners in *jointly adaptive* settings. Crucially, our framework is complementary to these techniques and can flexibly incorporate their compression strategies. We emphasize this core flexibility in Section 2 (Lines 63–82), and we will strengthen this point further in the revision. \n\n---\n\n**[Performance Strength Clarification]**\n\nWe believe the reviewer’s fourth weakness—that $FedAda^2$/$FedAda^2$++ outperforms existing adaptive FL algorithms and matches costly joint adaptivity—was intended as a strength. For example, in Figure 2, when evaluating convergence by *actual communicated bits*, $FedAda^2$ and $FedAda^2$++ outperform costly joint adaptivity substantially. This demonstrates that our methods are not only communication-efficient in theory, but also in practice.\n\n---\n\n**[Final Remarks]**\n\nWe thank the reviewer again for their constructive suggestions. We are committed to improving the clarity and accessibility of the proofs, as well as refining the empirical narrative around joint adaptivity and communication efficiency. We hope this response has addressed the reviewer’s concerns, and if so, respectfully request reconsideration of the overall score.\n\nPlease let us know if any points remain unclear—we would be happy to elaborate further."}, {"review_id": "fYfcKbM8pG", "reviewer": "Reviewer_egAL", "summary": "This paper presents efficient adaptive federated optimization algorithms FedAda2 and FedAda2++. Specifically, these two algorithms avoid the transfer of preconditioners between the server and clients, and also incorporates memory-efficient adaptive optimizers on the client side. They shows the advantage both theoretically and empirically.", "questions": "1. What is the key new insight in the theoretical analysis, considering that the algorithm is fairly general? For instance, prior work such as [1] also provides theoretical guarantees for a general algorithmic framework. How does this work differ or advance the theory?\n\n\nRef:\n1. Fednar: Federated optimization with normalized annealing regularization", "limitations": "It's better to have experiments in larger scale.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The methods are theoretically well-founded. The paper first introduces a general algorithm, proves its convergence, and then develops a practical empirical version.\n2. The writing is clear and easy to follow.\n\nWeaknesses:\n1. The empirical results, as shown in Figure 1, do not demonstrate a clear improvement over the baselines.\n2. The scale of the experiments is limited. Given the current state of the field in 2025, more large-scale evaluations would be expected.\n3. It would be better to have more insight on the advantage of certain joint adaptivity.", "was_revised": true, "final_justification": "Overall, I think this work solid and above the average quality of academic research in FL.", "rebuttal": "We thank Reviewer egAL for their review and are glad that the reviewer found the theoretical foundations of $FedAda^2$ and $FedAda^2$++ to be rigorous, and the writing clear and easy to follow. Below, we incorporate the reviewer’s feedback regarding empirical results, experimental scale, and theoretical novelty.\n\n---\n\n\n**[Empirical Results and Effectiveness of Joint Adaptivity]**\n\nThe empirical results in Figure 1 do show clear improvements—that is, across all datasets, we observe consistent trends:\n\n- Adaptive methods (e.g., FedAdam, FedAdaGrad) outperform non-adaptive FedAvg.\n- Jointly adaptive methods (e.g., $FedAda^2$, $FedAda^2$++) converge faster and often achieve higher accuracy than server-only adaptive baselines.\n- While \"Costly Joint Adaptivity\" performs comparably to $FedAda^2$, our methods achieve this with drastically lower memory and communication costs.\n\nThis performance gap is especially notable on **FEMNIST**, where we see clear separation between non-adaptive, server-only adaptive, and jointly adaptive methods. These trends are present across all datasets, demonstrating that joint adaptivity consistently brings empirical benefit, even when communication of preconditioners is avoided.\n\nIn Figure 2, when convergence is measured by *actual communicated bits* (i.e., communication rounds × bits per round), $FedAda^2$ and $FedAda^2$++ significantly outperform costly joint adaptivity. For example, with ViT, when $FedAda^2$++ is instantiated via SM3-AdaGrad, client memory overhead for preconditioning drops from 100% to only **0.48%**—a **99% reduction**—making joint adaptivity far more practical for large-scale and resource-constrained deployments.\n\n---\n\n**[Scope and Scale of Experiments]**\n\nWe appreciate the suggestion to explore larger-scale experiments. Our goal in this paper is to target **cross-device** FL—settings such as mobile phones, wearables, or edge devices—where communication and memory constraints are significant.\n\nOur experiments are intentionally designed to reflect memory- and communication-constrained scenarios, and we demonstrate that our algorithms retain strong convergence behavior in such environments. While large-scale experiments (e.g., training LLaMA-like models) are a valuable future direction, they fall outside the scope of this work. Training those models on mobile phones is not the target use case of $FedAda^2$/$FedAda^2$++, and we will clarify this further in the revised manuscript.\n\n---\n\n**[Theoretical Contributions and Comparison to Prior Work]**\n\nWe thank the reviewer for prompting a deeper discussion of theoretical novelty. The key theoretical insight in our work is that **the benefits of joint adaptivity can be retained even without transmitting preconditioners**, as long as one controls $\\varepsilon$-smoothing and learning rate schedules. Our analysis identifies important terms (e.g., $\\varepsilon$) that ensure convergence under these constraints. This extends beyond prior work, such as FedNAR, which does not analyze joint adaptivity and focuses instead on regularization. Additionally, **Appendix A** provides theoretical insight into the *heavy-tailed gradient noise regime*, which is common in modern transformer training. We show that client-side adaptivity reduces regret propagation from heavy tails, which to our knowledge has not previously been reported in the FL literature. \n\n---\n\n**[Comparison with FedNAR]**\n\n\nFedNAR aims to improve convergence via annealing-based weight decay and is largely orthogonal to our contributions. It primarily introduces regularization in an FL setting. In contrast:\n\n\n- $FedAda^2$/$FedAda^2$++ focus on **communication and memory efficiency**, especially in avoiding the transmission of local preconditioners.\n- Our algorithms implement **joint adaptivity**, combining client- and server-side adaptive updates, which requires a distinct convergence analysis.\n- By contrast, in the theoretical convergence analysis, FedNAR is analyzed only as a client-only adaptive method, as opposed to $FedAda^2$/$FedAda^2$++, which is analyzed as a jointly adaptive method.\n\nThese frameworks are complementary, and FedNAR techniques can also be incorporated into our adaptive structure—e.g., $FedAda^2$++ with FedNAR-style decay.\n\n---\n\n**[Final Remarks]**\n\nWe thank the reviewer again for their feedback. In the revision, we will clarify the theoretical contributions, expand the discussion of empirical trends, and better motivate our focus on the cross-device federated learning setting. We would be happy to address any additional questions or suggestions."}, {"review_id": "ynsTHm9akc", "reviewer": "Reviewer_NuBp", "summary": "The authors propose an adaptive federated optimizer featuring local preconditioner re‑initialization, global preconditioner updates, and memory‑efficient client optimizers, matching prior convergence rates and validated on image/text benchmarks. They further demonstrate that this design balances adaptivity with communication and memory efficiency, yielding performance on par with baselines under resource constraints.", "questions": "./.", "limitations": "- The authors list some technical limitations. Broader societal impacts (e.g. misapplication in high‑stakes domains) are not well discussed, but risks appear negligible.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- Provides rigorous convergence proofs for non‑convex jointly adaptive federated training under minimal optimizer conditions.\n- Reduces communication overhead by initializing local preconditioners to zero without degrading performance.\n- Integrates memory‑efficient optimizers (e.g., SM3) to dramatically reduce client‑side memory.\n\nWeaknesses\n\n- Thm 4.1 is not introduced well, and is not very intuitive.\n- The zero‑cost re‑initialization trick is conceptually obvious once you view the server preconditioner as an aggregator.\n- Memory‑efficient optimizers (SM3) are basically plugged in.\n- The theoretical insights beyond standard bounds are limited; proofs largely follow existing templates.\n- Empirical gains are modest and confined to standard benchmarks, with no demonstration on truly large‑scale or heterogeneous deployments.\n- Convergence rates match prior Ada‑style FL methods.\n- Experiments lack ablation on key hyperparameters (e.g., smoothing ε, delay z) in main text.\n- Scalability evaluation omits wall‑clock time or system‑level benchmarks in true cross‑device settings.\n- Privacy study is limited to logistic regression on StackOverflow.\n- Dataset diversity is modest (only four benchmarks), with no evaluation on non‑vision/text tasks or personalization objectives.\n- Ablation of memory vs. accuracy trade‑offs for varying model sizes is not provided.\n- Experiments with heterogeneous client data distributions do not control the degree of heterogeneity.", "was_revised": true, "final_justification": "After carefully considering my initial assessment in the light of the rebuttal, I am willing to raise the score. \nThe rebuttal was effective and sufficiently convincing explanation of the non-trivial nature of their convergence proofs. \nWhile I believe that the contribution is correct, technically solid, and non-trivial, judging the magnitude of the contribution is not straightforward for me.\nIf one is willing to accept that the magnitude of this contribution is more than minor, I've to concur that the remaining points do not _clearly_ justify a rejection of this work. Therefore, the paper's strengths now outweigh its acknowledged weaknesses, making a score of borderline accept appropriate, while highlighting my uncertainty with lowering my weight.", "rebuttal": "We thank Reviewer NuBp for their review. We appreciate the recognition of our theoretical contributions and the practicality of our memory- and communication-efficient approach to joint adaptivity in federated learning. Below, we address each of the reviewer’s comments in turn.\n\n---\n\n**[Theorem 4.1 and Theoretical Contributions]**\n\nWe appreciate the reviewer’s comments on Theorem 4.1. The full version is given in **Appendix E**, and a key strength of this result is that it accommodates *different client-side optimizers*, enabled by the flexibility of $FedAda^2$/$FedAda^2$++.\n\n\nThe theorem establishes a general non-convex convergence guarantee for $FedAda^2$/$FedAda^2$++, bounding the minimum gradient norm across $T$ rounds. Specifically, $\\min_{t\\in[T]} \\|\\nabla f(x_{t-1})\\|^2$ is upper-bounded by $\\sum_{i=1}^5 \\Psi_i / \\Psi_6$, where:\n\n- The numerator aggregates smoothness-based descent, effects of exponential moving averaging in adaptive preconditioning, and learning-rate based decay, and\n- The denominator reflects effective learning rate scaled by the adaptive server-side preconditioner, and is stabilized by the smoothing terms on the client or server.\n\nThe proof requires non-trivial decompositions of momentum updates, exponential decay control using a new constant $c(\\widetilde{\\beta}_1)$, and log-sum bounds over adaptive gradients. Crucially, convergence is preserved even under fixed client step sizes, despite omitting preconditioner transmission.\n\nWhile the zero-cost reinitialization trick may appear conceptually simple once the server preconditioner is seen as an aggregator, proving convergence with reinitialization and joint adaptivity is non-trivial. Notably, the proof must incorporate $\\varepsilon$-smoothing dependencies and account for clients retaining historical gradients—a challenge absent in typical FedOPT-style analyses.\n\nWe also include a novel regret-based analysis in **Appendix A** for federated training in heavy-tailed regimes. To our knowledge, this is the first regret-based theoretical result showing that client-side adaptivity reduces gradient noise propagation in such settings—something not addressed by prior works.\n\n---\n\n**[On Use of Memory-Efficient Optimizers]**\n\nWe respectfully clarify that the statement “memory-efficient optimizers are basically plugged in” is incorrect for $FedAda^2$. Unlike $FedAda^2$++, $FedAda^2$ does not need to use memory-efficient optimizers by default, and its implementation and analysis do not rely on such plug-ins. \n\n---\n\n**[Empirical Results and Performance Gains]**\n\nWe respectfully disagree with the assessment that empirical gains are modest. Figure 1 shows consistent and meaningful improvements across all datasets:\n\n- Adaptive methods (e.g., FedAdam, FedAdaGrad) outperform FedAvg.\n- Jointly adaptive methods ($FedAda^2$, $FedAda^2$++) consistently outperform server-only adaptive baselines.\n- \"Costly Joint Adaptivity\" achieves similar accuracy to $FedAda^2$, but with **significantly** higher communication costs. Relaxing memory consumption by deploying $FedAda^2$++ does not meaningfully degrade performance, and in some cases, even enhances performance in noisy DP-settings (e.g., Appendix J, Figure 9).\n\nThe benefits are especially pronounced on **FEMNIST** or **StackOverflow**, where the stratified gap between FedAvg, server-only adaptivity, and joint adaptivity is clearly visible.\n\nIn **Figure 2**, when evaluating convergence in terms of *actual communicated bits*, $FedAda^2$ and $FedAda^2$++ significantly outperform costly joint adaptivity. Additionally, with ViT, $FedAda^2$++ instantiated via SM3-AdaGrad requires only **0.48%** additional memory to maintain client preconditioning, representing a **99% reduction** in extra client memory cost. This makes joint adaptivity significantly more practical for large-scale, resource-constrained deployments.\n\n---\n\n**[Convergence Rate Comparison]**\n\nWe agree that our convergence rate matches that of prior adaptive FL methods, as this is the best-known result for non-convex optimization: $\\mathcal{O}(1/\\sqrt{T})$. However, achieving this rate in the memory- and communication-efficient jointly adaptive setting is novel, especially when clients retain historical gradients and when no preconditioners are transferred.\n\nIn FedOPT-style proofs, linearity of expectation allows clean reductions to server-only adaptivity. In contrast, joint adaptivity complicates the analysis due to time-dependent preconditioners on both client and server sides. Our work is the first, to our knowledge, to rigorously establish this rate under such general and practical conditions.\n\n---\n\n**[Hyperparameter Ablations]**\n\nAs mentioned in the main text, we in fact do include very extensive hyperparameter ablations, though these are deferred to the appendix for space reasons. To summarize:\n\n- **Appendix I** contains detailed sweeps over learning rates and $\\varepsilon$.\n- **Appendix J** contains ablations on the delay parameter $z$, including what happens when there is a *mismatch* between the client and server adaptive optimizers (e.g., server-side Adam preconditioners communicated to client-side AdaGrad).\n\n---\n\n**[Benchmark Diversity and Modalities]**\n\nWe selected four well-established benchmarks across vision and text, representing the dominant modalities in FL research. These datasets and modalities are widely used in federated learning papers (e.g., FedOPT [1], FedNova [2], FedNAR [3]), and are considered standard baselines. \n\nOther modalities (e.g., audio) or personalization objectives are not the focus of our study, as our goal was to provide a general-purpose framework with convergence guarantees in the jointly adaptive case where preconditioners were not transmitted for memory and communication efficiency.\n\n---\n\n**[Ablation on Memory–Accuracy Tradeoffs & Heterogeneity Control]**\n\nOur goal is to demonstrate the feasibility of joint adaptivity with strong theoretical guarantees under practical constraints. While trade-off studies (e.g., model size vs. accuracy scaling laws) and controlled heterogeneity sweeps are interesting, they fall outside the scope of this work. That said, our convergence result does allow different optimizers per client, making such studies possible in future work. \n\n---\n\n**[Final Remarks]**\n\nWe thank the reviewer for their feedback. In the revision, we will clarify the theoretical contributions and expand the empirical discussions. We hope this response has addressed the reviewer’s concerns, and please let us know if there are any further questions.\n\n[1] Adaptive Federated Optimization. Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, H. Brendan McMahan. International Conference on Learning Representations, 2021. \n\n[2] Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization. Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, H. Vincent Poor. Neural Information Processing Systems, 2020. \n\n[3] FedNAR: Federated Optimization with Normalized Annealing Regularization. Junbo Li, Ang Li, Chong Tian, Qirong Ho, Eric P. Xing, Hongyi Wang. Neural Information Processing Systems, 2023."}, {"review_id": "cfEeHqhDF0", "reviewer": "Reviewer_T2Br", "summary": "This paper proposes FedAda 2 and FedAda 2++, two communication- and memory-efficient adaptive algorithms for federated learning that retain the benefits of joint adaptivity while achieving the same convergence rates as more resource-intensive methods, with strong empirical performance across image and text tasks.", "questions": "Since the proposed methods eliminate the need for communicating preconditioners, one would expect a significant reduction in communication cost, as reflected in Figure 2. However, this improvement is not clearly observed—could the authors clarify the reason for this discrepancy?", "limitations": "No significant limitation.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths:\nThe paper demonstrates that communicating preconditioners in adaptive optimization is unnecessary. This is an interesting finding, as it enables both memory and communication efficiency. Moreover, the approach does not compromise convergence performance, making it a promising direction for future research.\n\n\n### Weaknesses\n1. Without an aggregated or communicated preconditioner, the server must compute the preconditioner independently. This can introduce additional computational and memory overhead, especially since some prior work often assumes that the server performs only minimal computations.\n  \n2. Although the authors note that the bounded gradients assumption has been used in prior work, it remains a strong assumption given the potential variability of local objectives. It would be more exciting to explore results under weaker or more realistic assumptions.", "was_revised": true, "final_justification": "I justify the current score based on my review.", "rebuttal": "We thank Reviewer T2Br for their thoughtful review. We are pleased that the reviewer found our results on communication- and memory-efficient joint adaptivity promising, and appreciated our convergence guarantees and empirical performance.\n\n---\n\n**[On Communication Gains in Figure 2]**\n\nThank you for the question regarding Figure 2. The communication savings may look less visually pronounced in the plot due to y-axis scale, but the improvement is significant when measured in actual *communicated bits* (i.e., number of rounds × bits per round). Additionally, $FedAda^2$/$FedAda^2$++ attains more benefits in resource usage:\n\n\n- $FedAda^2$ and $FedAda^2$++ achieve faster convergence with fewer bits transmitted than costly joint adaptivity.\n- When $FedAda^2$++ is instantiated with **SM3-AdaGrad** on ViT, the client-side memory overhead for storing preconditioners drops from **100% to just 0.48%**.\n- This results in a **99% reduction** in memory overhead, while still achieving strong performance.\n\nWe will consider including a table or numerical summary in the revision to highlight these reductions more clearly alongside the visual plots.\n\n---\n\n**[On Server-Side Preconditioner Computation]**\n\nWe appreciate the reviewer’s observation regarding the server-side cost. While the server independently maintains a preconditioner, this cost is generally manageable, particularly when compared to the resource limitations on client devices. Prior work often assumes that the server is relatively powerful, and thus, in cross-device FL settings (e.g., mobile/IoT), it is often a favorable trade-off to reduce client memory and communication at the expense of modest server computation (e.g., [1-2]). \n\n---\n\n**[On the Bounded Gradient Assumption]**\n\nWe acknowledge that the coordinate-wise bounded gradient assumption is standard in prior analyses of adaptive FL (e.g., FedAdam, FedAdagrad, FedOPT). Our goal was to build upon and generalize this framework to jointly adaptive settings with memory-efficient client optimizers, which has not been done previously.\n\nThat said, we agree it would be exciting to explore convergence under weaker assumptions (e.g., sub-Gaussian or heavy-tailed gradients). In fact, **Appendix A** presents a novel regret-based analysis in heavy-tailed regimes, which sheds light on how client-side adaptivity mitigates the propagation of noisy updates—particularly relevant in transformer-based training. We thank the reviewer for highlighting this direction and will aim to emphasize it more clearly in the revision.\n\n---\n\n**[Final Remarks]**\n\nWe are grateful for the reviewer’s feedback and insightful suggestions. In the revision, we will enhance the clarity of communication efficiency results (Figure 2), clarify server-side trade-offs, and more clearly highlight the theoretical contribution on heavy-tailed settings in Appendix A. We thank the reviewer again for thoughtful comments.\n\n[1] FS-Real: Towards Real-World Cross-Device Federated Learning. Daoyuan Chen, Dawei Gao, Yuexiang Xie, Xuchen Pan, Zitao Li, Yaliang Li, Bolin Ding, Jingren Zhou. Arxiv, 2023.\n\n[2]  A survey on federated learning: challenges and applications. Jie Wen, Zhixia Zhang, Yang Lan, Zhihua Cui, Jianghui Cai & Wensheng Zhang. International Journal of Machine Learning and Cybernetics, 2023."}]

Author rebuttal:

Meta-review: **Summary.** This paper introduces a general framework for adaptive federated optimization, where clients may employ different adaptive optimization methods for local updates, and the server aggregates pseudogradients to perform a global adaptive step. Under assumptions of smoothness, bounded gradients, and mild restrictions on the form of the local optimizer - satisfied by standard methods such as SGD, AdaGrad, and Adam - the authors establish an $\mathcal{O}(1/\sqrt{T})$ convergence rate for the best squared norm of the gradient along the trajectory.

**Strengths and weaknesses.** The paper makes a meaningful contribution to the literature on adaptive federated optimization. Three reviewers (NuBp, T2Br, egAL) rated it positively (scores 4, 5, 5), while one reviewer (CoJv) leaned toward borderline rejection, primarily citing readability concerns. I agree that the readability needs improvement, but the rebuttal suggests the authors have adequately addressed this issue.

A notable weakness is the reliance on the bounded gradients assumption in addition to smoothness. While somewhat restrictive, this assumption is common in the analysis of Adam/AdaGrad-type methods and was also flagged by Reviewer T2Br. On balance, the mentioned strengths clearly outweigh the mentioned weaknesses.

**Requested clarifications.** One important point, overlooked by reviewers, is that Theorem 4.1 (Theorem E.1) analyzes a deterministic method: there are no assumptions on stochasticity, and the convergence guarantee holds with probability 1. It is crucial that the final version explicitly states that this convergence bound applies only in the deterministic setting. I also ask the authors to incorporate all promised changes from the rebuttal.

**Final recommendation.** I recommend acceptance of this paper, conditional on the authors making the requested clarifications and revisions.
Decision: Accept (poster)