Problem-Parameter-Free Federated Learning
Authors: Wenjing Yan
Kai Zhang
Xiaolu Wang
Xuanyu Cao
Venue: ICLR 2025 Oral (2025)
Keywords: Adaptive federated learning
problem-parameter free
arbitrary data heterogeneity
adaptive stepsize
Primary area: optimization

Abstract: Federated learning (FL) has garnered significant attention from academia and industry in recent years due to its advantages in data privacy, scalability, and communication efficiency. However, current FL algorithms face a critical limitation: their performance heavily depends on meticulously tuned hyperparameters, particularly the learning rate or stepsize. This manual tuning process is challenging in federated settings due to data heterogeneity and limited accessibility of local datasets. Consequently, the reliance on problem-specific parameters hinders the widespread adoption of FL and potentially compromises its performance in dynamic or diverse environments. To address this issue, we introduce PAdaMFed, a novel algorithm for nonconvex FL that carefully combines adaptive stepsize and momentum techniques. PAdaMFed offers two key advantages: 1) it operates autonomously without relying on problem-specific parameters; and 2) it manages data heterogeneity and partial participation without requiring heterogeneity bounds. Despite these benefits, PAdaMFed provides several strong theoretical guarantees: 1) It achieves state-of-the-art convergence rates with a sample complexity of $\mathcal{O}(\epsilon^{-4})$ and communication complexity of $\mathcal{O}(\epsilon^{-3})$ to obtain an accuracy of $||\nabla f\left(\boldsymbol{\theta}\right)|| \leq \epsilon$, even using constant learning rates; 2) these complexities can be improved to the best-known $\mathcal{O}(\epsilon^{-3})$ for sampling and $\mathcal{O}(\epsilon^{-2})$ for communication when incorporating variance reduction; 3) it exhibits linear speedup with respect to the number of local update steps and participating clients at each global round. These attributes make PAdaMFed highly scalable and adaptable for various real-world FL applications. Extensive empirical evidence on both image classification and sentiment analysis tasks validates the efficacy of our approaches.

Published as a conference paper at ICLR 2025
PROBLEM-PARAMETER-RR FEDERATED LEARNING
Wenjing Yan', Kai Zhang", Xiaolu Wang", Xuanyu Cao
'Te Chinese University Hong Kong "The Hong Kong University of Science and Technology
3 East China Normal University *Washington State University
(wiyan]@ie, cuhk. fedukeddu.. hk, [kzhangbn] connncct .ust.kk hk, [xiaoluwang] @sei ecnu. edu. cn, (xuanyu. cao jewsu.edu
ABSTRACT
Federated learning (FL) has garnered significant attention from academia and in- dustry in recent years due to its advantages in data privacy, scalability, and com- munication efficiency. However, current FL algorithms face a critical limitation: their performance heavily depends on meticulously tuned hyperparameters, par- ticularly the learning rates. This manual tuning process is challenging in feder- ated settings due to data heterogeneity and limited accessibility of local datasets. Consequently, the reliance on problem-specific parameters hinders the widespread adoption of FL and potentially compromises its performance in dynamic or diverse environments. To address this issue, we introduce PAdaMFed, novel algorithm for nonconvex FL that carefully combines adaptive stepsize and momentum tech- niques. PAdaMFee offers two key advantages: 1) it operates autonomously with- out relying on problem-specific parameters, and 2) it manages data heterogeneity and partial participation without requiring heterogencity bounds. Despite these benefits, PAdaMFed provides several strong theoretical guarantees: 1) it achieves state-of-the- convergence rates with sample complexity of O(e and com- munication complexity of Occ-3) to obtain an accuracy of [[)]l S 6, even using constant learning rates; 2) these complexities can be improved the best- known (E=))) for sampling and ((e-2) for communication when incorporating variance reduction; it exhibits linear speedup with respect the number of local update steps and participating clients at each global round. These attributes make PAdaMFed highly scalable and adaptable for various real-world FL applications. Extensive empirical evidence validates the efficacy of our approach.
INTRODUCTION
Federated learning (FL) has emerged as promising paradigm for machine learning, allowing mul- tiple clients to collaboratively train a model without sharing raw data. Since its introduction by McMahan et al. (017)), FL. has garnered substantial attention from both academia and industry. Ma- jor conferences such as NeurIPS, ICML,, and ICLR have witnessed proliferation of FL-rellaedd re- search, addressing critical challenges including communication efficiency (Chen et al., 2021 Sattler cct al. 2019). privacy preservation (Wei et al. 2020 Mothukuri et al. 2021), heterogeneity manage- ment Li al. 2020); Karimireddy al. (2020b); Wang al. (2000) and partial and asynchronous
participation [Wan et al. 2022 Xu et al. 2023).
Despite significant advancements, current FL algorithms face critical limitation: their performance heavily depends on meticulously tuned hyperparameters, particularly the learning rates. This tun- ing process typically requires extensive computational resources and problem-specific knowledge, such as smoothness parameters, heterogeneity bounds, stochastic gradient variances, and initial op- timality gaps. For instance, MIME (Karimireddy et al. (020aa) relies on smoothness constants and data heterogeneity bounds for stepsize determination, FedProx (Li et al. 2020) requires careful ad- justment of a proximal term based on data heterogeneity, and FedDyn (Acar al.) (021) demands tuning of regularization parameter contingent on problem characteristics. Furthermore, algorithms such as FedADT (aoo et al. 2023 and FedAMS (Chen et al. 2020) necessitate cubblem-specifer
"Corresponding Author.

---

Published as a conference paper at ICLR 2025
parameters to establish minimum communication rounds, which must exceed thresholds associated with smoothness constants and other problem characteristics.
This reliance problem-specifte parameters poses several critical challenges. First, it impedes the widespread adoption of FL by complicating deployment and requiring expertise for hyperparameter tuning (Mostafa 2019 Deng al. 2020). Second, it potentially compromises the performance of
FL in dynamic or diverse environments where data distributions may evolve (Reddi et al., [2020] Koloskova al. 2020). Last, accurately estimating these parameters is often infeasible due the distributed nature of data and the inherent privacy constraints of FL (Konečný et al. 2016).
Recent research has attempted to address this issue through adaptive stepsize methods. FedOpt (Reddi ct al. 2020) incorporates adaptive optimization techniques like AdaGrad, Adam, and Yogi into FL, demonstrating improved convergence compared to FedAvg (McMahan et al.) 2017). Fed- Nova Wang et al. 2020) introduces normalization technique that effectively mitigates objective inconsistency caused by partial client participation and data heterogeneity. FedBN (Li et al. 2021) employed local batch normalization to alleviate feature shift before averaging models, outperform- ing both classical FedAvg (McMahan et al., 2017) and FedProx (Li et al.) (2020) for non-IID data. While these approaches show promise, they still require careful tuning of global learning rates.
Momentum is a technique that mitigates data heterogeneity and accelerates gradient descent by maintaining velocity vector of gradient history. Recent studies have investigated the combination of adaptive methods with momentum to leverage both advantages. Hss et al. (2019) proposed Fe- dAvgM, which incorporates server-side momentum term into the FedAvg algorithm, demonstrating enhanced convergence rates and robustness against data heterogeneity. |Wang et al. (2019) developed SlowMo, momentum-basee -baed method that employs two nested loops facilitate faster convergence in distributed optimization. FedAMS (Chen et al. (020)) utilizes adaptive moment methods on both the server and client sides address data heterogeneity. MIME (Karimireddy et al. 2020a) com- bines client and server momentum to enhance convergence. [u et al. (2023) introduced FAFED, momentum-based variance reduction scheme integrated with an adaptive matrix, achieving the best-knon kntwn sample and communication complexity when utilizing diminishing stepsizes. Never- theless, these methods still necessitate fine-tuning multiple hyperparameters. limiting their practical applicability.
very recent contribution, FedSPS (Sohom Mukherjee 2024), claims to be the first fully locally adaptive method for FL with minimal hyperparameter tuning. While promising, this approach relies on stringent assumptions of bounded gradients and bounded data heterogeneity. Moreover, it fails to converge to optima with constant stepsizes and requires adjustment of maximum stepsize threshold based on the smoothness parameter, maintaining degree of hyperparameter dependence. Therefore, there is critical need for more robust and adaptive FL algorithms capable of operating effectively across diverse scenarios without relying on problem-speciff parameters.
1.1 MAIN CONTRIBUTIONS
This paper addresses these critical limitations of FL by proposing novel approach that eliminates the need for problem-specin hyperparameter tuming while effectively handling arbitrary heteroge- neous data. Our method based on careful combination of adaptive stepsize and momentum techniques. The adaptive stepsize mechanism dynamically adjusts local learning rates against client update heterogeneity, while the momentum component provides stability under partial participation and accelerates convergence in the nonconvex landscape. To the best of our knowledge, this is the first algorithm to achieve such parameter-agnostt adaptation in nonconvex FL with a state-of-the-art convergence guarantee. Our main contributions summarized as follows.
1) We introduce PAdaMFed, a problem-speciee Parameter Agnostic algorithm for nonconvex FL based on adaptive stepsizes and client-side Momentum. PAdaMFed offers several significant advantages:
Independent of problem-specific parameters: PAdaMFed operates autonomously without relying on any problem-specin parameters such as smoothness constants or stochastic gra- dient variance. All stepsizes in our approach are explicitly determined by system- defined constants, including the number of participating clients, local updates, and communication rounds.
2

---

Published as a conference paper at ICLR 2025
Robustness to arbitrary heterogeneous data: PAdaMFed inherently manages data hetero- geneity without requiring any heterogeneity bounds among clients while accommodating partial client participation. This feature enhances its scalability and adaptability in real- world scenarios where client data can be highly diverse and unpredictable, and full partici- pation may always be feasible due resource constraints device availability.
2) We provide rigorous theoretical analysis of PAdaMFed, demonstrating its state-of-the-ar per- formance:
PAdaMFed achieves sample complexity of O(e and communication complexity of (Ee-5) to obtain ||V]())]| < accuracy for nonconvex FL problems, even using constant learning rates.
The complexities are further improved to the best-known sample complexity of O(e and communication complexity of O(E-)) when incorporating variance reduction.
PAdaMFed exhibits linear speedup with respect to the numbers of local update steps and participating clients in each global round.
Notably, these theoretical results are obtained under minimal assumptions, requiring only L- smoothness of loss functions and unbiased stochastic gradients with bounded within-client vari- ance. This represents a significant advancement over existing FL, algorithms, which typically necessitate constraints such as data heterogeneity bounds (Li al., 2021]] Wu al. 2023)) di- minishing stepsizes (Wu et al. convergence rates (Liang et al. 2019 Alghunaim 2024).
2023
Sohom Mukherjee (2024), or fail to achieve the best-known
3) We conduct empirical evaluations to validate our theoretical findings and the efficacy of our algorithms. Our methods are compared against several established baselines, including FedAvg McMahan et al. 2017), SCAFFOLD (Karimireddy et al. (020b), and SCAFFOLD-M (Cheng et al. (2024) Extensive numerical evidence demonstrates the superiority of our approaches in not only runtime efficiency but also stepsize robustness.
2 PROBLEM SETUP
We consider an FL. system where N clients collaboratively train a common learning model Id under the coordination of parameter server. Let &, represent random sample of client i drawn from its local data distribution D.. The loss function associated with client i is given by (0( Eg [F (0: {,),, where (0: &:) the stochastic loss of client over sample & The objective of the FL system is to minimize the global loss function across all clients, defined as:
minger f(0) \ Σm (0) where f+) REE-DD [F (0: Ex)]
In federated setting, clients collaboratively train a global model, but the raw data of each client is never shared with the server and other clients.
Denote by 1-I the &a norm. We make the following standard assumptions.
Assumption (Sample-Wirs Wise Smoothness). Each sample-wise loss function F(O; Es) is L-smooth, ie., ||V (0: E - F (5: E.)ll S T.|l0 51) for all 0, 8 E TRd, i (1,...,,., and E, ~ Dr
The Sample- Wise Smoothness Assumption iimplies the following standard smoothness condition. Assumption (Standard Smoothness). There exists L O, such that each loss function fü is L- smooth, i.e., fı (0) V.J. (8)] < LII0 for all 0, Rd and i E {I....,N}
We emphasize that our original PAdaMFed algorithm is based on the Standard Smoothness As- sumption 2 The slightly more stringent Assumption required when using variance reduction to further accelerate convergence.
Assumption 3 (Stochastic Gradient). There exists a 2 O such that for any O E IRd and i E [1....,N), Eg, [VF (0; {:) v (0) and Ee, VI (0; Er) -V((0)) < o², where & ~ D;.
Assumption 3 ensures that the stochastic gradient V (0: {.) is unbiased and has bounded within- client variance, which standard stochastic optimization.
We consider nonconvex FL problems with data heterogeneity among clients, where the local data distributions D. * Dj for any * j. When addressing heterogencous data, most existing ap- proaches, such SCAFFOLD (Karimireddy al. 2020b), FedProx (Li al. 2020), FedAMS
3

---

Published as a conference paper at ICLR 2025
(Chen al. 2020), and MIME (Karimireddy et al. 2020a), require upper bound on gradient dissimilarity, L.c, there exist constants B, o. > 0 such that
N E IVA < B [(()) + for all 0 E IR4.
This assumption simplifies the mathematical analysis of those FL approaches and ensures their al- gorithmic performance. However, may hold in scenarios where data across clients exhibit significant and unpredictable variations, thus compromising the robustness of FL.
Additionally, existing algooriiss typically rely on problem-specific parameters to determine their stepsizes, including the smoothness constant T., gradient variance o², and heterogeneity bounds B and o². The smoothness constant, which characterizes the Lipschitz continuity of gradients, is generally global property requiring knowledge of the entire dataset. Similarly, quantifying data heterogeneity across clients necessitates a comprehensive understanding of the differences between local data distributions. However, in FL settings where raw data sharing is prohibited and only model updates are exchanged, obtaining precise measurements of these parameters is computation- ally prohibitive and may compromise FL's privacy guarantees.
In the subsequent section, we present an algorithm that is independent of problem-specific parame- ters and capable of handling arbitrarily heterogeneous data, thereby eliminating the requirement of the heterogeneity bound
3 ALGORITHM DEVELOPMENT
Algorithm PAdaMFed: Paallem-Prammeee-AAnntttti Algorithm for Nonconvex FL
1: Require: initial model 00, control variates c, * Ek= VF (0":E," for any i, c-
E momentum g c_l_ global learning rate y, local learning rate 77, and momentum parameter 3
2: for / 0,
do 3: Central Server: Uniformly sample clients S; S (1, NJ with [ = S
4: for each client i S, in parallel do
5: Initialize local model 00
0c
6: for l 0, ... K do
7:
Compute
8 VF 00h :68
ct
cl-l) + (1 -3)g
Update local model ,- 0l.k g. i
8:
9:
end for
Update control variate of Σ Σt=o
VF (oth:
( set oi -:-² "'ror St)
11: Upload 0..KK and ct to central server
end for Central server:
13:
Aggregate local updates g'
45K Eies, 00' (0'- 0%.0))
14:
Update global model 0++ 0¹ rg' Aggregate control variate c' c' + N Eies, (c: - c;-1)
15:
16:
Aggregate momentum g¹ B 1 Eies. - + cl-1) + (1 3)9
Download @++1, /e + (1 g) to all clients
18:
end for
In this section, we propose PAdaMFed, a problem-parameter aarameter-agnosti algorithm for nonconvex FL based adaptive stepsizes and client-side momentum. PAdaMFed is designed to operate indepen- dently any problem-specifie parameters, handle arbitrarily heterogeneous data, and accommodate partial client participation.

---

Published as a conference paper at ICLR 2025
3.1 ALGORITHM DEVELOPMENT OF PADAMFED
Our approach builds upon the well-established SCAFFOLD algorithm (Karimireddy et al. 2020b), which was designed to address "client drift" in FL. where local models significantly deviate from the global model due to partial participation and data heterogeneity. The core concept of SCAF- FOLD is the utilization of control variates to correct the drift between client updates and the global model. Specifically, the server maintains a global control variate, denoted c', to represent the av- erage model update direction, while each client maintains a local control variate, denoted by of for all i E ( N. to track individual update directions. Client updates are subsequently adjusted using the difference between local and global control variates. SCAFFOLD demonstrates faster and more stable convergence compared to the seminal FedAvg algorithm (McMahan et al. 2017).
In this paper, we extend the original SCAFFOLD framework by incorporating client-side momentum and local adaptive stepsizes, outlined in Algorithm [ Specifically, in Step 7 of Algorithm 1 the local descent direction of client at global round and local step Is is computed as:
g ks 3 (VF')
0 E.
- +'+ (1 3)g"'1
In this expression, the term V :g c. represents the stochastic gradient at the current local
model tedh with the sample c The term c' - c/- adjusts the difference between the global and local control variates, helping to mitigate client drift. The term g i-1 denotes the current global momentum, essential for stabilizing and accelerating the convergence across clients.
In Step 8 of Algorithm 1. the local model for each client i is updated by: 0 0
9 t.k
77
1
Here, an adaptive stepsize // f.k is utilized by normalizing the descent direction vector g, This normalization guarantees that the progresses from all clients have a uniform magnitude, preventing the disproportionate impact of any individual client on the global model update. It also provides us the convenience on quantifying the distance between consecutive models in our theoretical analysis,
0/-1|=- =1 9 /I9g/*11 1) for all i, k,t. maintaining that 0,.k+1 0%-h|
Additionally, since ct K -K-IN VF (ot* e for all i, the momentum update Step 16 of Algorithm can be expressed as:
g' 3 3 ( ( Ek- VF ( -c + od-1)
3)---1
(2)
This equation accumulates the descent directions across clients and iterations that we have g" Σ.,t a g.tht. With g', the optimization trajectories at each client are smoothed by the descent di- rections of other clients, enhancing the robustness of the optimization process against variability in local updates caused by data heterogeneity. Notably, our PAdaMFed algorithm maintains the communication workload of the SCAFFOLD for both uplink and downlink.
3.2 ACCELERATING PADAMFED WITH VARIANCE REDUCTION
Variance reduction is an effective technique to accelerate convergence and enhance the stability of FL., particularly when dealing with heterogeneous data and limited client participation. In this sub- section, we enhance PAdaMFed by integrating a variance reduction component into each client's de- scent direction, resulting in our PAdaMFed-V7 VR algorithm. The detailed procedures of PAdaMFed- VR are provided in Appendix B
PAdaMFed- VR differs from PAdaMFed primarily in its computation of the local gradient. Specifi- cally, Step of Algorithm is replaced with:
g VF ( E + -c' + 5) (g- (0)
VF (0-)):E!
where V (o'-1 c. represents the variance reduction component. Our variance reduction de- sign follows the principle of STORM (Cutkosky & Orabona 2019) to make more efficient sample utilization. For each local update, the sample c.th x used twice: 1) compute the gradient based on
5

---

Published as a conference paper at ICLR 2025
the current local model : and to evaluate the gradient the previous global model @- This dual usage of each sample mitigates the influence of within-client gradient noise, enabling more accurate estimation of gradient directions.
4
THEORETICAL RESULTS AND COMPARISONS WITH PRIOR WORK
4.1 THEORETICAL RESULTS
Theorem Suppose that Assumptions and 3 hold. the local and global learning rutes of respectively, the momentum parameter be 3 T
FAdaMFed be KVT and and (0t) 1:20 be the iterates generated by Algorithm | Then, it holds for all T
(SK) 1374
SK
1hhat
T-1
A L ++L+o+vie VLo VSKo + +L (A
T B
Σ
(SKT)*
VT
1=
where A == f (09) ming f0)- Theorem 2. Suppose that Assumptions
and 3
hold. Let the local and global learning rates of respectively, the momentum parameter be 3
SKYs T2rs
PAdaMFed-VE be 17 KT and 7 (SK) 14/3
and 100) J:20 be the iterates generated by Algorithm Then, it holds for all 2 1 that
T-1 [E(V)(0)
A ( (SKT)}
(L (L+ OSKK)
+
T
Remark 1. According to Theorem PAdaMFed converges to an e-stationary point in expectation within O s communication rounds. This convergence rate is improved to O Ske when corporating variance reduction, as shown in Theorem Furthermore, both algorithums demonstrate linear speedup with respect to the number of participating clients and local update steps K.
Remark 2. In PAdaMFed, setting SK -O(T) yields a sample complexity of O(E with communication complexity O(E-)). Similarly, by setting SK = O(VT), PAdaMFed-VE achieves the best-known sample complexity of ((E)) with communication complexity of o 9) to find an e-stationury point (Wu et al. 2023).
Remark 3. In traditional FL, selecting optimal stepsizes theoretically requires knowledge of problem-specific parameters, which are often unavailable. Consequently, in real-world FL sce- narios, stepsizes must be tuned empirically-44 process that is labor-intensive, time-consuming, and sometimes even impractical. our PAdaMFed and PAdaMFed- VR, the stepsizes are explic- itly determined by system-defined constants (the numbers of participating clients S, local update steps K, and communication rounds T), without requiring any problem-specific parameters. This pnperpprrmmeer-indepeeddde nature simplifies implementation, enhances robustness, and facilitates the deployment of our algorithm across diverse FL applications.
4.2 PROOF SKETCH
Our theoretical proof starts from the L-smoothness property of the loss function f(!), which yields the following incquality:
(0+ - (0") s 27 (Vf -00000')'-''---00 - ( sk Eies.A of g. +
-
'A point 0 is said be e-stationary if /| (0) Note that for any e-stationary point defined using V [0))l, one can derive the corresponding guarantee for [[][ based following relationship:
T-1 Σ BVIVS
T-1 T
T |I
/ VEV
where the first and second inequalities utilize Jensen's 's inequality as the square root function is concave. There- fore, we can align our results with the metrie of $ Eir (0'))))) 2 by taking square root on both sides their convergence bounds.
Total number of samples elients, local updates, and communication.

---

Published as a conference paper at ICLR 2025
To establish upper bound for 1 El E + E E IVS (0') - g'll and + Ei ER E Eies,
IV (0*)
||. must quantify two key terms:
The momentum g' is recursive variable that accumulates values from previous rounds. By plugging into the expression of g' (provided in ② into |V (0") g'll and introducing the auxiliary term / (0'-1), we can recursively express |[V (0') - g'lll by its predecessor (0-)) -g scaled by a contraction coefficient (1 - 8). This substitution also intro- duces additional terms associated with stochastic gradients and control variates. Through meticu- lous control of all intermediate terms, we prove that q. E E E (0*) g'll is upper bounded by ((SKK))=+ +) for PAdaMFed and by (((SKT)- - for PAdaMFed-VR.
g") represents gradient dissimilarity across clients. While the het- erogeneity bound (T) could readily control this term, our objective is to eliminate dependence on such bounds. Instead, we relax this term to E || fo (0' (0--)) ci- 1/ along with other con- trollable terms, by substituting the expressions for g and g'. Returning to our treatment of E B|[ (0*) g'll, we exploit the recursive property of the control variate c bound V (0- ". This, in turn, allows to establish a bound for E Eies, g." g"
The term EE [E | |1g
Combining the above processes leads to our analytical results. For comprehensive proofs, please refer to Appendix A for Theorem aan Appendix for Theorem
Intuition on the Algorithmic Features: The efficacy of PAdaMFed stems from the synergistic in- tegration of three indispensable components: local gradient normalization, client-side momentum, and control variates. 1) Gradient normalization serves an adaptive learning rate scheme, auto- matically adjusting stepsizes based on the local optimization landscape. This design automatically allows larger steps in regions with small gradients (where more aggressive exploration is beneficial) and smaller steps in steep regions (where careful progress is needed). 2) Client-side momentum helps accelerate convergence while maintaining stability. First, it helps overcome local irregularities in the loss landscape by accumulating gradients over clients and iterations. Second, accelerates progress in directions of consistent gradient agreement. 3) Furthermore, control variates align lo- cal updates with the global objective, reducing variance in gradient estimates and ensuring more consistent updates across heterogeneous client data. Collectively, these techniques ensure that the stepsizes are independent of problem-specife parameters such as smoothness constants and data heterogeneity bounds, simplifying the tuning process and enhancing robustness across diverse FL environments. Notably, our algorithms also eliminate the requirement of data heterogeneity bounds, further broadening their applicability.
4.3 COMPARISONS WITH PRIOR WORK
We compare PAdaMFed and PAdaMFed- VR with several representative algorithms for solving FL problems with heterogeneous data, as listed in Table 1.
Comparisons of PAdaMFed with Prior FL Algorithms: The SCAFFOLD (Karimireddy et al. 2020b) algorithm requires the smoothness parameter L for stepsize tuning. However, its communi- cation complexity, given by O
K
L.
is suboptimal. MIME (Karimireddy et al. 2020a) im-
5
Ket)
) by incorporating server-level momentum. Nevertheless, MIME requires large-batch local gradients per round, and its learning rates depend on multiple problem parameters, including initial optimality gap A and heterogeneity bound oz, which are challenging to estimate.
proves this complexity to O ( (ska))
FedSPS (Sohom Mukherjee, 2024 incorporates stochastic Polyak step-sizes into local client up- dates, achieving a communication complexity of O (vk=) in full participation scenarios. How- ever, its analysis relies on the assumption of bounded data heterogeneity. Moreover, its stepsize tuning requires knowledge of the lower bounds of all loss functions, i.e., e for all i, in addition to the smoothness parameter L, leading to significant moobemm-paammed dependence.
SCAFFOLD-M (Cheng et al. 2024) employs similar client-side momentum as PAdaMFed, remov- ing the need for bounded data heterogeneity. However, SCAFFOLD-M's stepsizes depend sev-
7

---

Published as a conference paper at ICLR 2025
Table 1: Comparisons of algorithms for solving FL problems with heterogeneous data.
(Shorthand notation: Add. Assump. Additional assumptions aside from Assumptions BDH Bounded data heterogeneity define in ( BG Bounded gradient that [[)]l G, vi,
BHD = Bounded hessian dissimilarity that V2 (i(0) v2 f S ő. 0)
Stepsize-Relatee
Communication
Algorithms
Add. Assump.
Stepsize Restrictions
Problem-Paramett
Complexity
SCAFFOLD
Y= vB.
Karimireddy ct. al.
2020b
24yR
Ke
Mime
BDH, BHD
1) =
AS LGTK2
G 0
L, A. o². of
1 3ke
Karimireddy al.
2020a
FedSPS
1.k 1/2
min
BDH
L.G.
Sohom Mukherjee 2024
1/b
min
8 = min
1, No
LASK
LAS GuN
SCAFFOLD M
22T
L. L. L. Go
Cheng 2024
7 L nKL X min
3Ke
v3' SK
PAdaMFed (This paper)
8K v
(SK)
( SKO
T
r
KVT
Variance Reduction
RAPED Wu et al. 2023
BDH, BG
Be x
N
8g x
oz
1 3kr3
Lt3
= min
N
KLA o
.5
SCAFBOLD M- Cheng 2024
7L min
{1, 1
L. L. o²
SvRe
r $ min
3
3R
PAdaMFed-VR (This paper)
(8K)
(SK)
(skrs)
T3
7
KT
4 < inf E.); for any i, and is constant balance adaptivity and accuracy. Go +/4 Σ [1])
eral problem-specifie parameters, including the smoothness parameter T., initial optimal gap A, and stochastic gradient variance o², resulting in laborious stepsize tuning. In contrast, PAdaMFed is completely independent of problem-specifie parameters while achieving start-of-the-art communi- cation complexity.
Comparisons of PAdaMFed-VR with Prior Vadicede-Reduced FL Algorithms: FAFED (wu ett al., (202)) employing momentum-bart based variance reduction with an adaptive matrix, achieving the best-known O( 3) sample complexity and O(e 2) communication complexity through the use of diminishing stepsizes. However, FAFED requires stringent assumptions of bounded gradients and bounded data heterogeneity. Moreover, its learning rates are subject to several complex constraints and rely pooollem-parmmttr-bbeeeee algorithm tuning. SCAFFOLD-M-VR (Cheng et al.) (024) variance-reduced SCAFFOLD-M algorithm and, similarly, requires careful step size tuning based multiple problem-dependee parameters. Nevertheless, it fails to achieve the best-known complexity established in the literature.
5 NUMERICAL EXPERIMENTS
In this section, we present experiments on two real-world datasets: EMNIST (Cohen et al., 2017)
and CIFAR-10 (Li al. 2017). We evaluate the proposed algorithms against several baselines,
8

---

Published as a conference paper at ICLR 2025
0.8
0.7
0.7
Accuraty
Acourcyy
0.6
0.6
0.5
0.5
FadAug
FadAug
SCAFFOLD
SCA/FOLD
0.4
SCAFFOLD
PAdaMiied
0.3-
PMdaMfee
SCAFFOLD
PAdaMiFed-VR
PRdeMrred
50
100
150
200
250
300
350
400
0
500
100
150
200
250
300
350
400
Communication Round
Communication Round
i.d
non-i.id
Figure 1: Test accuracy versus the number of communication rounds on the EMNIST dataset.
Tedfug
Teddin
SCAFFOLD
SCAFFOLD
SCAFFOL D-M
0.8
SCAFPOLDIN
0.8
PidsNFed
RASDMFFo
0.7
0.6
0.5
0.3
0.3
0.2
0.1
0.1
10
10
10"2
10
10a
10-4
10-3
10
10-
109
Leaming Rate
Learning
(a) i.i.d
(b) non-i.i.d
Figure 2: Test accuracy versus learning rate the EMNIST dataset.
including FedAvg McMahan et al. 2017), SCAFFOLD (Karimireddy et al. 2020b). SCAFFOLD
M (Cheng et al. 2024). Additionally, experiments are conducted under both i.i.d. and non-i.i.d. data distributions. Due to space limitations, the detailed experimental setup and additional simulation results are provided in Appendix
Figure D illustrates the test accuracy of various algorithms versus the number of communication rounds on the EMNIST dataset, with subfigure [afrepresenting i..d. data and subfigure (eaffguurebbddppiieee depiciin non-i.i.d. data. The stepsizes for algorithms, PAdaMFed and PAdaMFed- VRR are determined based on the theoretical guidance provided in Theorem and Theorem 2, respectively. For fair com- parisons, the hyperparameters other algorithms in Figure are optimized through grid search to achieve their best performance. The results demonstrate that our proposed methods significantly out- perform all baseline algorithms-FeedAvg. SCAFFOLD, and SCAFFOLD-M-1 both convergence speed and test accuracy. Notably. although SCAFFOLD employs similar momentum technique, converges more slowly than PAdaMFed and achieves lower accuracy, validating the efficacy of our adaptive stepsize design. Building upon these advantages, the incorporation of variance reduction further enhances our methods" superiority through more efficient sample utilization. Moreover, the results non-i.i.d. data in subfigure lb demonstrate even greater performance margins than the i..d. case, highlighting the advantages of our algorithms.
Figure 2 compares the test accuracy of various algorithms versus the learning rate on the EMNIST dataset. All algorithms were evaluated over 400 communication rounds to ensure a fair comparison. We observe that algorithm demonstrates superior robustness stepsize selection, maintaining stable performance across a significantly wider range of learning rates compared to baseline meth- ods. Specifically, it achieves test accuracy exceeding 0.8 across the stepsize range [3 10-3 10-1]

---

Published as a conference paper at ICLR 2025
for i..d. data distributions (subfigure 2a and above 0.7 for the same stepsize range under non-i..d. conditions (subfigure 2b). In contrast, baseline algorithms exhibit substantially narrower regions of stable performance, empirically validating our method's 's enhanced stepsize robustness.
CONCLUSIONS
This paper proposed a novel training approach, PAdaMFed, for nonconvex federated learning (FL) that eliminates dependency on problem-specific parameters and enables automatic generalization across diverse FL environments. PAdaMFed also removes the need for data heterogeneity bounds and accommodates partial client participation, further broadening its applicability. We provided rigorous theoretical analysis for PAdaMFed, demonstrating its state-of-the-art convergence under minimal assumptions, including the L-smoothness of loss functions and unbiased stochastic gradi- ents with bounded within-client variance. Furthermore, we enhanced this convergence rate by in- corporating variance reduction, achieving the best-known (c--3) sampling complexity and ((c-2) communication complexity. Extensive numerical experiments demonstrated that our algorithms out- perform existing representative FL approaches both runtime efficiency and stepsize robustness.
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. arXiv preprint arXiv:2/ / 1..02633, 2021.
Sulaiman A Alghunaim. Local exact-diffusion for decentralized optimization and learning. IEEE Transactions on Automatic Control, 2024.
Mingzhe Chen, Nir Shlezinger, H Vincent Poor, Yonina C Eldar, and Shuguang Cui. Communication-effiieeet federated learning. Proceedings of the National Academy of Sciences, 118(17))2024789115 2021.
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, pp. 119-128, 2020.
Ziheng Cheng, Xinmeng Huang, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. The Twelfth International Conference Learning Representations. 2024.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. 2017 international joint conference on neural networks (ICNN), pp. 2921-2924 IEEE, 2017.
Ashok Cutkosky and Francesco Orabona. Momentum- variance reduction in non-convex SGD. Advances in neural information processing systems, 32, 2019.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003. 13611, 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Huimin Gao, Qingtao Wu, Xuhui Zhao, Junlong Zhu, and Mingchuan Zhang. Fedadt: An adaptive method based on derivative term for federated learning. Sensors, 23(1))6003 2023.
Geoffrey Hinton.
Neural networks for machine learning, lecture 6a, 2012. URL http://
www. es htt.://c..cccccccoo.//////eaaee/ slides lec6. pdf Coursera.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint
2019.
10

---

Published as a conference paper at ICLR 2025
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebas- tian Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03606, 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference machine learning, pp. 5132-5143 PMLR, 2020b.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6968 2014.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreini, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5399 PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint urKiv:/610.05492 2016.
Hongmin Li, Hanchao Liu, Xiangyang Ji, Guoqi Li, and Luping Shi. Cifar10-dvs: an event-stream dataset for object classification. Frontiers in neuroscience, 11:309, 2017.
Jiaxiang Li, Xuxing Chen, Shiqian Ma, and Mingyi Hong. Problem-parameter-fiee decentralized nonconvex stochastic optimization. arXiv preprint arXiv:2-402.0881,, 2024.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and sys- fems, 2:429-450, 2020.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. Fedbn: Federated learning on non-iid features via local batch normalization. arXiv preprint arXiv:2/02.07623, 2021.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local SGD with lower communication complexity. arXiv preprint arXiv:1912. 12844, 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Commmicationn-fficieentt learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Hesham Mostafa. Robust federated learning through representation matching and adaptive hyper- parameters. arXiv preprint arXiv:
2019.
Viraaji Mothukuri, Reza M Parizi, Seyedamin Pouriych, Yan Huang, Ali Debghantanha, and Gautam Srivastava. A survey on security and privacy of federated learning. Future Generation Computer Systems, 115:619-644 2021.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295. 2020.
Felix Sautler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and communication--ffieee efficiient federated learning from non-iid data. IEEE transactions on neural net- works and learning systems, 3 31(9):3400-3413 2019.
Sebastian U. Stich Sohom Mukherjee, Nicolas Loizou. Locally adaptive federated learning. arXiv preprint arXiv:2307.06306 2024.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Im- proving communication-efficienn distributed SGD with slow momentum.
arXiv preprint
2019.
Jianyu Wang, Qinghua Liu, Hao Liang Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:761 1-76233, 2020.
11

---

Published as a conference paper at ICLR 2025
Xiaolu Wang, Yuchang Sun, Hoi-To Wai, and Jun Zhang. Dual-delayed asynchronous sgd for arbi- trarily heterogeneous data. arXiv preprint arXiv:240S.16966 2024.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security, 15:3454-3469, 2020.
Xidong Wu, Feihu Huang, Zhengmian Hu, and Heng Huang. Faster adaptive federated learning. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 10379-10387, 2023.
Chenhao Xu, Youyang Qu, Yong Xiang, and Longxiang Gao. Asynchronous federated learning heterogeneous devices: A survey. Computer Science Review, 50:100595, 2023.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum, arXiv preprint arXiv:2106.10874 2021.
12

---

Published as a conference paper at ICLR 2025
A RELATED WORKS
Adaptive stepsize methods have gained significant attention in opti- mization literature due to their ability to automatically adjust learning rates based on the geometry of the objective function. These methods, such as Adam (Kingma & Ba 2014), AdaGrad (Duchi) et al. 201T), and RMSProp Hinton (2012), have demonstrated remarkable success in various ma- chine learning tasks, particularly in handling sparse gradients and non-stationary objectives. In the context of FL, adaptive stepsizes offer several advantages. First, they eliminate the need for manual tuning of learning rates, which is especially beneficial in federated settings where global knowledge of the objective function's properties is limited. Second, adaptive methods can potentially mitigate the impact of data heterogeneity by allowing different update rates for different model parameters, effectively accounting for varying gradient statistics across clients.
Adaptive Stepsize Methods:
FedOpt (Reddi et al. 2020) introduced adaptive optimization techniques like AdaGrad, Adam, and Yogi into FL., demonstrating improved convergence properties compared to the traditional FedAvg algorithm. \aan et al. (2020) proposed FedNova, which normalizes and scales local updates to mit- igate objective inconsistency caused by partial client participation and data heterogeneity. FedBN (Li et al.) 2021) employed local batch normalization to alleviate feature shift before averaging mod- els, outperforming both classical FedAvg (McMahan et al., (017)) and FedProx (Li et al., (020) for non-III data. While these approaches demonstrated the advantages of adaptive methods for casing parameter tuning, none provides theoretical guarantees, and careful tuning of global learning rates remains essential.
Momentum, on the other hand, is a technique that accelerates gradient descent by accumulating velocity vector in directions of persistent reduction in the objective across iterations. In nonconvex optimization, momentum has been shown to help escape saddle points more effi ciently and potentially reach better local optima (Cutkosky & Orabona 2019). The incorporation of momentum in FL algorithms can provide several benefits. It can help smooth out the impact of het- erogeneous updates from different clients, potentially leading to more stable and faster convergence. Moreover, momentum can aid in overcoming the challenges posed by partial client participation by maintaining consistent optimization trajectory even when client participation varies across rounds.
Momentum:
Hsu et al. (0199) proposed FedAvgM, which adds server-side momentum term to the FedAvg algorithm, demonstrating improved convergence rates and robustness to data heterogeneity. [Wang et al. (2019) developed SlowMo, a momentum-based method using two nested loops to achieve faster convergence in distributed optimization. Both FedCM (Xu et al.] 202T] and [heng et al.) (2024) investigated the integration of client-side momentum in FedAvg to effectively tackle client heterogeneity and partial participation in FL.
Combination of Adaptive Stepsizes and Momentum: Recent works have explored combining adaptive methods and momentum in FL. FedAMS (Chen et al. 2020) implements a local AMS- Grad scheme for FL. demonstrating fast convergence with low communication cost. MIme (Karim- ireddy et al. 2020a) combines control variates with server-level momentum at every local update mimic centralized methods running on III data, outperforming centralized methods but requir- ing large-batch local gradient per round for each client. [w et al.] (2023) introduced FAFED, momentum-basee variance reduction scheme integrated with an adaptive matrix, attaining the best-known sample and communication complexity when using diminishing stepsizes. While these methods demonstrate improved performance, they still require careful tuning of global learning rates.
A recent contribution, FedSPS (Sohom Mukherjee| 2024). claims be the first fully locally adaptive method for FL with minimal hyperparameter tuning. While promising, this approach relies on stringent assumptions of bounded data heterogeneity and gradients. Moreover, it fails to converge to optima with constant stepsizes and requires adjustment of maximum stepsize threshold based on the smoothness parameter, thus retaining some hyperparameter dependence. The limitations of existing approaches underscore the critical need for more robust, adaptive FL algorithms capable of operating effectively across diverse scenarios without extensive parameter tuning.
This paper makes significant advancement by proposing novel algorithm, PAdaMFed, that com- pletely eliminates dependency on problem-spedee parameters. All stepsizes in our approach are ex- plicitly determined by the number of participating clients, local updates, and communication rounds.
13

---

Published as a conference paper at ICLR 2025
To the best of our knowledge, this is the first algorithm that achieves such problem-paraaee parameter inde- pendence in FL. Moreover, our algorithm inherently manages data heterogeneity and partial client participation without requiring any heterogeneity bound among clients, which is also nontrivial.
Data heterogeneity has been extensively studied in FL. However, existing algorithms either depend on bounded data heterogeneity (e.g.. FedAvg (McMahan et al. 2017), SCAFFOLD (Karimireddy eet al., 2020b), FedProx (Li et al. 2020). and Mime (Karimireddy et al. 2020a)) or fall short of achieving state-of-the-art convergence rates (e.g., VRL-SGD (Liang al. 2019) and LED (Alghu- naim 2024). Recently, [heng et al. (2024) demonstrated that momentum can eliminate the data heterogeneity constraint the FedAvg and SCAFFOLD algorithms while achieving state-of-the-ar convergence results. WWang et al. (2024) introduced DuDe-ASGD for asynchronous FL, which can effectively handle arbitrarily heterogeneous data by leveraging stale stochastic gradients. However, their algorithms require carefully designed stepsizes based on hyperparameters. In contrast, our al- gorithm accommodates arbitrary data heterogeneity while achieving complete parammtrr independence.
notable concurrent work by (Li et al., 2024) also explores the context of decentralized non-convex optimization. While both studies target problem-parane parameter- free optimization, our work addresses the unique challenges inherent to federated learning settings. The fundamental distinction lies in our treatment of client drift-a critical phenomenon arising from multiple local updates and data heterogeneity in federated environments. Our key technical contri- butions beyond (Li et al. 2024) are twofold: 1) The development of novel framework integrating control variates with momentum to mitigate client drift, requiring sophisticated theoretical analysis due their complex interactions; 2) The successful elimination of explicit heterogeneity bounds, which were previously considered essential in federated learning literature.
parameter-free algorithms in
A THEORETICAL ANALYSIS OF PADAMFED
Our analysis is based on the following useful lemmas. Lemma 1. For any we have
1
o 001
1 u and NK
0
001
2 nk.
NK
Proof. From the update rule of local model, for any i, k and t, we have
t
g k+1
0%
g
=n
n
g
t
Then,
k-1
10
0r
-500)
k
0
-0%:0| k
Summing the above inequality over and k yields
n K-1
1
001
Σ 122
(K 1)K(2 - 11) 3 2K?
S
NK
K k=0
6K
Similarly, we have
Σ o
0-1
Σ
(1107h 00l1²)
K-1
Σ 1 nn
NK
NK
K
k=O
These inequalities in Lemma are frequently used in our analysis.
14

---

Published as a conference paper at ICLR 2025
Lemma 2. Given vectors W1,... WN R and w N Ei= Wi if we sample S C {1,-.. ,N} uniformly randomly such that |S| = S. then it holds that
E
w.
| w|
5
SN
Proof. Letting 1 E calculation as follows:
S} be the indicator for the event i S, prove this lemma by direct
Σ IS
3.
=
E
w fi S}
(T, ]
E
| 2 1fi E S7+2 2
5
iej
S(S - 1)
Σ
|w!l1? +
Σ Kij
wi Wj
SN
8 N(N 1)
1 SN 1=1
S(S -1) 1)
Σ
|w:11 + 52 N(N -1
Σ wi
S(N 1) N Σ
N
| N(S - 1)
|0 1
5(N - 1)
N S
Wi
S(N - 1)
N
3
2 + 3
SN
1=1
where the last inequality uses the fact that
N < 1 for any nonempty set S.
From the L-smoothness of ((-) in Assumption 2 have
(0) f (0')
S Vf (0)) T (0'-1-0) (
+ 1
2
1
Σ
g, t,k
+
SK
t.k
2
9
9; 1
gi A.k
2L
>> (4) (0)) -.D-
Σ
79'
+
SK
iES.,k
g
SK
iESt,k
9
c,k
2
3  < (0)) l.6 (
9 t.
g'
22L
?
1|g*
+
SK
||gs] |
2
iES..k
9
"6 2 17/114
g"
72
(0) 1l.6 - / (0') + ||66||
SK
1.k
||g
2
9
2 (0) 11
- 1 (0)
Σ
1 k
g'll
+
2LL
(AI)
SK
2
k
15

---

Published as a conference paper at ICLR 2025
where (a) uses the inequality that |1o0+1 - 001l
2 SR
Cies,
S
7
(b)
is based on
9:
y [IVS - || S <>
v (0*)
gell and (c) is from the following relation:
lg'|l
1
Σ
9, c
g'
g'''l
Σ
gi
9
SK
k
9,
||g
SK
iEScck
9,"
9
gg'll
||g'l1
9
9,
SK
AES,,,
||g'|
9
| ||
||gsf|
9
SK
llg'll
||
iESt.k
1 SK
Σ
||g"||
9
tES,,k
t.k
g-
9i
SK
VESt,k
Taking expectation both sides of A1 obtain
E V
(0')
<
[ (0')
f
(0++))] + 2
Vs (0') 9'll
22L 2
+
7
E
Σ
9
+
SK
iES..k
Summing the above incquality over and dividing it by 7'', we have
2 T-1
T Σ
E
B
(0))
Ef
(00) - (0 )
Σ
E
V
(0")
gg'll
T E
sill
7l. 2
g,
+
(A2)
SKT
1=
SiES
We
have the following results
on
the terms
1 T
1Σ E (0') - gl'll
and
ET
E
E
g
-
g'
in
A2b.
SKT
Lemma 3. Under Assumptions and the disparity $ 2 E V (0t) - g" is upper bounded
by:
1 1 gg'll
30 VSK
L
10,3
303
B V (0')
BT E
1+
RKL + to.
S
SK
4N2
KVLL
+ 27
S
2
2V5
Lemma
4.
Under
Assumptions
and r²[] is upper bounded by:
the
gradient
dissimilarity
TT-1 Etes, 9
E
SKT
T
E
c.k gi .
9il
$2B ((+
2
o 2nKL + (1
(1+ 2N
S IL
SKT
VK
8N
120
25
+
3N KL
ST
VK
16

---

Published as a conference paper at ICLR 2025
The proof of Lemma is presented in subsection A.1 and the proof of Lemma 4 is presented in subsection A.2 Set 8
Be VT
7
and 1j
KVT From Lemma
we know that
T
f (0') g'll
T
1
BoT
30
Tol. BOT
10,3 L
30,30 SKVT
+
+
+
1+
+oV
BOVT
2T
VSK
SVT
VT
L0
Bu
4N2
Lo
1 +
T
S
8
2VSKT
30
7LL
L
30,80
Lo 2/SKT
17
VV
(A3)
BoVSKT
BOTT
VT
SKVT
Similarly, from Lemma
4
we know that
T-1
E
Σ
9
g'l
SKT
iES..k
200
((1
2L
2N
7oL
8N
28 L
1
+
1
VT
VK)
VT
5
T
ST
VK
3N VT
280g
4,00
(A4)
VT
VKT
Define the initial optimality gap A == f (00)
f-. Then, (89) -(()) S f f09)
fr =A.
Plugging (A3)
and
A4
into
A2 we have
T
1
60
20
2L
3033
+
+ 20
T
To
AVVSKT
VT
SK SKVT
E=
V2Lo
2500
4.00
70L
(SKT)
VT
VKT
2T
Let 70 = (SK)
and 9.- VSK. Then, we have
1
A A Vo
+ VSKo +L
E V (0') s
T
(SKT)
VT
By setting SK 0
(Tb)
we have
VSK VT
x 0 ((SKT)=++ and thus
|| 0 ( (A+L (A+L+otVIo VLo
B
E
00)
T t=0
(SKT)
A.1 PROOF OF LEMMA 3
The proof of Lemma 3 utilizes the following result.
Lemma 5. For any i, t, define of == E /||
f: (0')
- Under Assumptions
2 and 3 we have
$ 5 (222²² 220 2S
3 (1-
S
2t
+
N
22
o²
- Vi. K
3N
4N
Proof. Since for any I, the S elements in S, are uniformly sampled from (1,.... , N). we have
c
with probability 8
ct
Σ b
VF
slik)
with probability $
R
17

---

Published as a conference paper at ICLR 2025
Using Young's 's inequality repeatedly, we have
2
5
E
/ (0') - +
S
E
Σ
Vf. (0))
VF (0+ -:: 1)
N
N
K
k
5
E
V fo (
F VFi( - c--
+
5
20
+
21.
Σ
E
kk
84
N
N
K
K
k
S
S
1+ 2N
28
0²
E
& 11-1 +
7²1²2
K +
3
N
2N
N
S
2N
25 0²
1
2 +
2N
S
N
K
3""
S
8 +
2N
2 +
28
0²
3"
Σ
1-1
S
2N
5
N
K
2N
r=0
S
N2
a²
1
1
Φi + 4
82 1 2
2N
K
3
(09: LM). we have
Since ci
VF
R kk=
11
8 N
E
E S (09) -
+ N
E
VJi (09)
Σ
VF
(00M: 20.
K
1
S
0²
+
28
1,2E
000
0
||
2
+
0²
N
K
N
K
1+ S
0²
25
12
N)
K 3N
20
28
17 L2
K
3N
Then, we have
20
K
3N
25
1
2 k²1.2
(1-
2N
S
+4
N2
57
21, +
o²
K
+
3 {1P2313
1
20
28
K2L2)
(1-
S
21
+
N2
2
+ 0²
K )
K
3N
4N
52
where we use the relation
1
s 2N
S (1
Define g == f (8') -g' and u = ff (8')- - Vf 10) From the update rule of momentum g'. we have
3 (1= - -1- + Vi (0') -c--1- 1
Σ
VF
s..c) 0 +
c cl-1)
SK
iES,,
=(1 - -1)- + (1 - 8)u² + +B²²
=(1 - 81 Σ u (1 1)++1 + Σ 30 (1
-3)-
Based on the triangle inequality of la norm and the concavity of the square root (-)+, we have
EF Σ 30 (1 100-)))-- 00--1 (A5)
E 8|| <(1 |
Σ E u [1
-)++1+++ +
18

---

Published as a conference paper at ICLR 2025
Since c; = R Ek-1 VF (09:E:1))
()) for any i, c = = E, ci
c
and g =c we have
E B| = V (0))
Σ
VF
:0 LM) +
B
Σ (vr (0P VF (00 g..
NK
SK
i,k
iESo.k
E
B
VF
E, L
V. (0.) + Vi (0% AF (0. <0
VNK
SK
B0
3
(0%) (0)) fy (0R.M) ||
Ba VSK
E
Σ
VNK
VSK
SK
iESu.k
BL
E
00.
80||
+
30
NK
VSK
K
30
(A6)
2
VSK
where the last inequality uses the results in Lemma 1 Additionally, for any f, we have
gi t
Iu = V (0*+1) VV
V (0')l S L 11 - -0'1| S 7
1/h.
(A7)
SK
1 f
iES.
To proceed, we handle the last term in A5 First, we have
E
Σ B (1 - 8)--
8 1 11 ())
Σ
(1 (1- ()- (A8)
S
Let 5 + 0 and F.hk == a((0 (1 U F') and F++1 == a(u,Ft.K) for all t 2 0, where a indicates the o-algebra. Let [E||F" represent the expectation conditioned on the filtration J with respect to the random variables (c) ISisNoOscK in the 1-th iteration. Let Eg [+] represent
the expectation taking over the random sample tt Similarly, let Es, [-] represent the expectation taking over the uniformly sampled client set S,. The set S, independent across different t. Then, for any f, we have
E[u'|F"] E ((ete))
(e. M,, [00]
=Ee! 1vi.k
Vf (00) -
1
Σ i.k
VF 0 g
-c-
NK
(0')
1
Σ
Vff (0!.t)
NK
i.k
19

---

Published as a conference paper at ICLR 2025
where the last equality is based on Assumption 3 and the fact that 2/ E== ci = c' for any t. Then,
for any 0 I f
< tz
S T 1, we have
E (v" v22)
E ((00
E 1
2 |
Σ
V.f. - (0.21))
1
Σ
(V)) -V (09**)
E
SK
NN
i
( (D.:.h)
VF {
-. ))
Σ (V.. (0'z) v.c (0!a.t) ))
+E E
SK
NKK
i,k
+ E
E.S.
-
Σ
(. (0'x) - V. (0txit)
S
NNK
IES,
i,
I,2
E
1
gr. 11
1
Σ
E 0/
0' 2
L
Σ 1 0'2
2NK
2NK
VSK NK
i
i,k
1 1²
T
KLo
(A9)
3
2VS
Further, based on Lemma
2 we have
E |
<
V
(0))
Σ
F
0
NK
i.k
1
Σ E
1
Σ
VF
1
VF
-cc- - cl-1)
$ N
K
N
0/411²
a²
A
$2
II 0¹
+
+
NK)
5
2
202 + Ar
//
K2
NK
s
A 1
1
Σ E
-
N
K
1
Σ
E
1
V
F
F (0.t)
Vs: (0') F Ai: (0--1) - -c--1
N
K
40
AL2
Σ
E
0 0
0²1
+ 4LL' 0' 01 + 4 N Σ E V fi (0--) c 11-
K
NK
< K
402
3"
4
K22, + 1,,21² +
4
Σ $
N
where of 1-1
;= = E ||| V 10--1)- -c--1111
112
-From Lemma
5 we know that, for any i,
$ < 20"
+
25
" R2(2)
(1-
S
2(t-1)
+
N2
2 2 2 +
x²
+ 1 k3
K
3N
4N
52
K
2
4N2 2 TT?
+ 2ny
R2T
+
(A10)
K
g2
Plugging the upper bound of - into A, yields
280²
28
(1+ 4N2
A 5
2
K2 1.
+ 222
1+
K
S2
20

---

Published as a conference paper at ICLR 2025
Then, have
2
10
300²
4N2
E
+
of
x²
+
+
S (1
(A11)
3
S
SK
52
Plugging
A9
and
A1l
into
A8 gives
Σ Bo (1 3)-
S/B110 +E+4E4 o0
[ 5555)
2 10
5
Brj Brj K2²++
30023
437212
1+
4N2
SK
5
52
+ + KVLL
2/5
Since 8 < 1, taking square root on both sides of the above inequality yields
E
30 - (1-8)-m
103
308
4N2
Ko
+ KL + V.
S
SK
+ 27
5(+ 52
S
1+
2VS
(A12)
where we use the fact that va + & Va + vb, for any a, b 0.
Plugging (A6). A7 and A12 into A5
have
30
L
103
303
B|EE'| || 5(1 8)
M +
1+
nKL + 0
2
VSK
B
5
SK
8
4N2
TV WKL
+2/4//
1+
+
S
52
2VS
Summing the above inequality over t yields
B S
1 BT
(
n33KT.
30 VSK
L
+
103
KT
30
B
S
SK
3
3
4N2
VIVKLO
+ 2711
1+
8
52
2V5
A.2 PROOF OF LEMMA 4
Recall that G,a² = 3 VF s! - + cc-1) +(1 -1
g' SK Σ tk
iES..k
K
0² g( - d-11 + c
+ (1 -3gg--1
K
1ES,
21

---

Published as a conference paper at ICLR 2025
Then, we have
1
E
gi||
SK
K-1
BE
VF
cl.k)
- -c,-- - 1
Σ
Σ
VF
-
SK
5
K
SE A:
SES.
k=
2,3
@ gla - c
E
VF
NK
N,
23
Vsi (0.tt)
Vi (0)) + (0'((0'') cl-11|
E
F
NK
S 23
o +
Σ
10 - -0"|
+ 11' - 01-
+ 28 N
k VJ. [v. (0' (0- - c
NK
i,
1 a nn I. + 7/1)
23 N
Σ V Vo-
S 2B
+
From Lemma 5 we know that
2/
IN )
25
(1
(1-))
S
1-1
N
σ +
(21kk) Vi.
3N
+2
I +
K
4N
5
VK
Thus, we have
E
Σ
gi
$23 ((++
2
o +
2nKL+ +
[1 2N
5 74)
SK
vK)
220
25
(1-
5
S t-
+ 2/3
VK
+
3N
4N
Summing the above inequality over i yields
|
$2B (1 (1+
2
2N s 7T.
E
g. ckk
g6
a + 2nKT
(1+
SKT
vK)
8N3
12o
2S 3N
+
nKL
ST
VK
B THEORETICAL ANALYSIS OF PADAMFED WITH VARIANCE REDUCTION
The analysis of PAdaMFed-VR is similar to that of PAdaMFed. We first present the following two auxiliary Lemmas.
Lemma 6. Under Assumptions 1 and the disparity 7 IT ( - g") is upper bounded by:
1
30 VSK
+ GKL
2
22B
E
V (8') - -g'll s BT 2
7KL +
+ +
+ +oV
23
SK3
SK
33
4N2
63 S
7///
1 + g2
+ nKL
S
22

---

Published as a conference paper at ICLR 2025
Algorithm 2 PAdaMfied-RR: PAdaMIeed with Variance Reduction
1: Require: initial model 8 0-1 0 control variates c = k Σ K
VF
(00; & 1.k)
for -
any i, c-' = N E, ", momentum g = c_' global learning rate y, local learning rate f) and momentum parameter
2: for (- 0, ........... , do
3: Central Server: Uniformly sample clients S, (1, N} with |S = =
4: for each client i S in parallel do
5: Initialize local model 0: = 0c and control variate of = 0 (for i $ Sc, cj =c==c-1 1
6: for l: 0,... K do
7:
Compute gi
VF
0 :
+ B - c + (1
3) g VF ( (E(
Update local model 0. 0% 11 9:
8:
9:
Update control variate ct = ct + VF 0 g.
10:
end for
11:
Upload 0% and ot to central server
12:
end for
Central server:
Aggregate local updates g' 1
75K Eies, (8'-0,-0)
14:
Update global model 0++1 0¹ - -g Aggregate control variate c' c
15:
Eies, (c: - c
16:
Aggregate momentum g' = B ( Eies, (c: - 1 + c(111) + (1 - 3)g
17:
Download 0'+1, Bc + (1 - 8)g to all clients
end for
Lemma
7.
Under
Assumptions
and is upper bounded by:
3
the gradient
dissimilarity
SKT
Et
TT-1
E
Dies,
9
g6)
T
E
l.k g. .k
g"
28
(
(1+
2
σ + 2nKL+ + 1+ 2N
S 7L)
SKT
VK
t=1
8N3
V2o
2S
+
nKL
+ tKLL + L
ST
VK
3N
Set 8 =
80 T
and
- 17
1
From Lemma 6
we know that
KT.
Σ E
E (0')
g'll
L
30
L
Lo
2 SK Bb
228
BO
2T
VSK
2
T
T
SK
70 L
3,80
4N2
6,0
1
+
T
S
S
T
S
30
L
L
22,80
(A13)
BOSKTT
2
T
SK
30
T
SK
Similarly, from Lemma 7 we have
E
Σ
g
do
0²1
280
((++
2
o +
2L
1
2N
7o
SKT
T
VK
T
T
ieS..k
8N
V2o VK
2S L
L
L70
+ T
(A14)
ST
3N T
T
23

---

Published as a conference paper at ICLR 2025
Plugging A13 and (A14)
into A2
we have
A
60
L
2/27
20.
E |
To
T
BOVSKT'S
BOT
VSKBOTS
VSKT*
20
200L
+
T
T
Set 80 = (SK) and 7o0- = (SK)3, 3, we have
A
60
2/2
Σ E
V
2
7
BOVSKT
B
VSK3TT3
20 2
2800
2
VSKT
T3
T
A A+ 0
(L +
(SK))
3
0
(SKT)
T
By setting SK < O (VT). we have
(SK) T
X O ((SKT)+)) and thus
E
(O) 50
0
((3k7))
T
B.1 PROOF OF LEMMA 6
Since 8x == (0') g', we have
8 V'=VS(0) (0') 1 Σ VF
0
+ B
Σ
(c) 1-1 - 1
SK
S
K
iES,
(1 - B)
g F
VJ (0--1)
1
Σ VF (0- ((t))
SK
iES,,k
=(1 - -1-))---1--
VF
(0'
k - vF :
SK
k
+8 (0') cd-1_
1
Σ VF (o - ct 1
SK
iES,,k
==
+(1 - B)
Σ SK
VF (0c-) (5--)) VF (0': + V/ - v. (0-1)) -
iESe.k
t
1 Σ
=(1- + Σ
w (1- -1-
+ Σ u (1 - 1)
30 (1 - -)
r=1
r=1
r=1
Σ ã (1 (1-11)44-1 1)
E||81| <(1 3) || + Σ
E 2000 (1 (1-3)(-++ - E
11)
+
E
Σ
35 (1 8)¹ -76-
(A15)
24

---

Published as a conference paper at ICLR 2025
Since 0-1 0- c = L/ Ek' VF
(09:5:" (i) for any i, i. + E. s and g = c
have
E
10 =E Vf (09)
Σ
VF (0 1,k) 1.1
NK
1
Σ
(BV
00: lin)
+ (1 - 3/VF (0%:EEA) - VF (0% c 0,
SK
iESo.k
+
1
E
Σ
VSi (89) vi (OR*)) |
VNK
VSK
SK
VSK
kESu.k
L
001
30
E
+
NK
VSK
i
30
knnL
(A16)
VSK
Then, we have
|w0|
E
0 0¹1 s 2 5 L.
1
(A17)
SK
iES..k
Additionally, since [[ūi| [F]]
0, then, for any 0 t1 < t2 S 1, we have
E("", w'tt) = B (ut B/u ('ae) O.
From Lemma 2 for any 6, we have
0 (/+)) VF (0':E**)) + (0))
E
VF
NK
k
N
VF ( (0 VF (0': + +V (0*) - v.f v.
+
E
SN (=1
K
k
L2
1
1 0- 00-11
0- 01-
+
NK
SK
2,2
SK
Then, we have
1
2,221,
E
Σ ū (1 411-
Σ E E 1|2 - 3)+1- <
(A18)
SK3
Similarly, since E o
F+| = 0, for any 0 S t < t2
- -T- we have
E ( و()) = E ",th,B''' (ーوي 0.
From Lemma for any f, we have
E E| 1 < E
V (0')
ΣVF
VF
0²: k( (t))
1 Σ VF (l:
-c--1
NK
SN
K k
i
0²
N Σ
VF O0: E
FV. (0*) F Vʃ: 10- - -
+
NK
SN
K b
i=1
02
3a2
3 211 +
3
+
+ 5
$:-
NK
SK
SN
i=1
25

---

Published as a conference paper at ICLR 2025
By A10
G0² K
+ 2nn2 + 4N2 5 222.. Then, we have
22o²
37-1.²
4N2
6
E| 0 1
(1+ 52
SK
5
2
E Σ 36 (1 - 8)--
(1-
1 12
E 112(1 - B)(+-
1=1
22360 2
332
4N2 5
63 S
+
1+
+
5
(A19)
SK
5
Plugging (A16, A17). A18). and (A19)
into (A15)
yields
30
nKL
2
22B
BIE <(1 - 3)
28 + +77,
+ +oV
VSK
SKB
SK
33
4N2 S2
63
L v
1
+ K
V
S
S
Summing the above inequality over yields
T-1
(1 t=0 BT 2
30 VSK
+ nKL
2
22B
=
1 +
+ t
+ 0
28
SK3
SK
33
4N2
63 S
+ t74
1 $2
+ RKL
S
B.2 PROOF OF LEMMA 7
With variance reduction, we have g, ik VF (0.tt ck.
3 (ct--1c"" + (1
3) g - VF ( (,+)))+))) Since g"
1 SK
Eies, lik we have
E
1
91
1.k
oill
SK
V
2
E
V
F
0 s/
-1 - -cc--1-11-
NK
2
BE
VF
0 5/ cc--1 + (1 B)
VF @/ {/ ) VF (!+) |I)
NK
2/3
E
F
gt. :
ct.kk - -ct-1l
+ +22(1-1
Σ E EBloot 00
+ E
E100* 0 11
NK
NK
i.
i
2
E
V
5/ - c c/-11
+ +nKL 27L.
NK
From Section A.2
we know that
23
VF @. (g
- 523 ((+
2
o + +n2K +
1+
2N
NK
VK
S
V2o
25
(1
S t-1
23
VK
V
3N
KK
4N
26

---

Published as a conference paper at ICLR 2025
0.8
0.7
0.7
0.6
Acouracy
0.6
0.5
0.5
FedAng SCAFFOLD D
Fed/ug
SCAFFOLD
0.3
SCAFFOLD-M
0.3
SCAFFOLD-M
indeiteed
PAdaMiFed
20
40
60
80
100
120
140
160
0
20
40
60
80
100
120
140
160
Communication Round
Communication Round
(a) iid
non-i.id
Figure 3: Test accuracy versus the number of communication rounds on the CIFAR-10 dataset.
Then, have
E
Σ
9; 1.
g¹
< 23
((1+
2
+ 2nKL+ +
2NV (1+
7L)
SK
VK
S
kESt
V2o
28
(1-
S 1-1
23
+
n
+TKL 27L.
VK
3N
4N
Summing the above inequality over t, we have
T
2
2N 1+
E
g,
g"
23
1+
o + 2n +
S 7TL)
SKT
VK
JES ts
8N3
220
2S
+
3V (LL
+ +nkL+ + 27L.
ST
VK
3N
C ADDITIONAL NUMERICAL RESULTS
Experimental Settings: We employ a convolutional neural network (CNN) with three convolu- tional layers and two fully connected layers for the EMNIST dataset, and a ResNet- 18 architecture for 100 The experimental framework involves 100 distributed clients with 10 clients partici- pating randomly each training round. investigate both independent and identically distributed (i..d.) and non-i.idd data distributions. For i..d. scenarios, we implement uniform random data distribution across clients. To simulate realistic heterogeneity in non-i.i.d settings, we apply a Dirichlet distribution Dir(1) for EMNIST, Dir(0.5) for CIFAR-10. The hyperparameters of all base- lines, including learning rates, are optimized through comprehensive grid search.
C.I SIMULATIONS ON CIFAR-10 DATASET
Figure presents the comparative analysis of test accuracy across different algorithms on the CIFAR-TO dataset, with subfigures 3a and 3b illustrating the performance under i.i.d. and non- i...d. data distributions, respectively. The observed patterns align with those demonstrated in Figure 1. Our proposed algorithms demonstrate superior performance compared to existing methods, in- cluding FedAvg, SCAFFOLD, and SCAFFOLD-M, both in terms convergence rate and final test accuracy. Under non-i.i.d. conditions, while all algorithms exhibit increased performance volatility and reduced accuracy, the relative performance hierarchy remains consistent with the i.i.d. scenario, shown in subfigure 3b
Figure illlustrassss the evolution gradient norm [(') for various algorithms on the CIFAR- 10 dataset under both i.i.d. and non-i.i.d. data distributions. The results demonstrate that
27

---

Published as a conference paper at ICLR 2025
0.12
p
FedAwg SCAFFOLD-M
0.08
1210.1
0.06
RAdaMFied
0.06
0.04
FadAug
0.02
SCAFFOLD-M
RAdeMFeed
0.02
25
50
75
100
125
150
175
200
25
50
75
1.00
125
150
175
200
Communication Round
Communication Round
(a) i.d
non-i.id
Figure 4: Gradient norm versus the number of communication rounds on the CIFAR-10 dataset.
0.9
0.8
0.6
Iccurac)
0.5
0.3
0.2
Gradient normaliatiion Momentum
Gradient normalizaion Momentum
MidaMFee
PAdaMFed
25
50
100
125
150
200
75
100
150
175
200
Communication Round
Communication Rourd
(a) i.i.d
(b) non-i.i.d
Figure 5: Ablation study versus the number of communication rounds on the CIFAR-10 dataset.
momentum-enhannee methods, specifically proposed algorithm and SCAFFOLD-M, achieve more rapid gradient norm reduction compared to their non-momentum counterparts.
We further carry out the ablation study by isolating the effects of momentum and gradient normaliza- tion Figure [ The results demonstrate that incorporating SCAFFOLD with normalized gradient leads degraded performance due the loss of gradient magnitude information. Therefore, the momentum is essential in our algorithm design to maintain the descent direction by effectively ag- gregating gradients across clients and iterations.
28


Reviews:
[{"review_id": "rVDCjt7ITU", "reviewer": "Reviewer_A59W", "summary": "This paper proposed a new federated learning algorithm called PAdaMFed that is problem-parameter free. The main idea is to combine SCAFFLOD and momentum. The authors also designed a modified version of PAdaMFed to reduce the variance, called PAdaMFed-VR  The authors showed that PAdaMFed-VR can achieve state-of-the-art convergence performance. The performance of PAdaMFed and PAdaMFed-VR is also verified using experiments.", "questions": "1. What are the challenges in the proof compare to the proof in the SCAFFOLD algorithm?\n\n2. The assumptions used in this paper are similar to those used in proving the convergence rate of the SCAFFOLD algorithm, so the gain in terms of convergence analysis must coming from using momentum and variance reduction. Please provide a detailed explanation on the gain of the proposed algorithms. Please provide a detailed comparison in terms of the convergence rate/communication complexity between PAdaMFed, PAdaMFed-VR, the SCAFFOLD algorithm and related algorithms as the Table 2 in the SCAFFOLD paper.\n\nKarimireddy, Sai Praneeth, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. \"Scaffold: Stochastic controlled averaging for federated learning.\" In International conference on machine learning, pp. 5132-5143. PMLR, 2020.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed PAdaMFed is independent of the problem parameters such as gradient divergence. \n\n2. The author also designed PAdaMFed-VR to reduce the variance of the federated learning algorithm.\n\n3. The authors showed the convergence upper bound of PAdaMFed and PAdaMFed-VR analytically.", "weaknesses": "1. The idea of PAdaMFed is a direct extension of SCAFFOLD with momentum considered at each client. \n\n2. The challenge in the proof is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W60ktYWOip", "reviewer": "Reviewer_XEQX", "summary": "The paper introduces PAdaMFed, a federated learning algorithm that uses momentum and adaptive learning rates to address client heterogeneity, similar to SCAFFOLD-M. The method is problem-parameter-free and does not require parameter tuning. The paper provides a convergence bound, without the standard assumption about gradient dissimilarity.", "questions": "1- Can you recover the optimal bound with the extra assumption and different learning rates?\n\n2- Can you design an experiment in which the gradient dissimilarity assumption does not hold and other methods fail to converge?\n\nsuggestion: since $c^{t-1}$ and $g^{t-1}$ are used only as $\\beta c^{t-1} + (1- \\beta) g^{t-1}$ you can only send the weighted sum and not each one to the clients and have the same communication per round as SCAFFOLD.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1- The paper studies important problems. Both data heterogeneity and hyperparameter tuning are existing issues for FL systems. The method has problem-independent hyperparameters which makes it more useful in practice.\n\n2- There are not many works in the literature that study problem-independent parameters; this work is one of the first.\n\n3- The convergence bound and analysis is novel, and has minimal assumptions. The authors proved convergence without assumptions about gradient dissimilarity, a standard assumption that most of the literature's works require.", "weaknesses": "1- The convergence bound is not optimal compared to SCAFFOLD-M. Also, for the case when  $K$ (the number of local updates) is a function of $T$ (total rounds), a fair comparison would involve the equivalent formulation for SCAFFOLD-M under the same conditions.\n\n2- Empirical results are limited. Experiments for different architectures and datasets can help improve the paper and show its effectiveness.\n\n3- Missing related work: There are some similarities between your work and [1] which is not cited. Can you compare your method and results with this work. \n\nMinor: Most of related works uses $\\|\\nabla f(x)\\|^2 \\le \\epsilon$ and not  $\\|\\nabla f(x)\\| \\le \\epsilon$ for the definition of $\\epsilon$-stationary and this formulation makes the paper a bit confusing.\n\n[1] Li, Jiaxiang, et al. \"Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.\" arXiv preprint arXiv:2402.08821 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z8cASALJBX", "reviewer": "Reviewer_xnsX", "summary": "This paper proposes an algorithm called PAdaMFed, where the hyperparameters don't depend on the problem-specific parameters such as smoothness constant, stochastic gradient variance bound, etc. PAdaMFed applies a client-drift control mechanism similar to SCAFFOLD but also uses normalized updates at the client level. It also has a momentum-based update rule at the global level. A variance-reduced version of PAdaMFed, called PAdaMFed-VR is also proposed. PAdaMFed and PAdaMFed-VR have communication complexities of $\\mathcal{O}(\\epsilon^{-3})$ and $\\mathcal{O}(\\epsilon^{-2})$, respectively, for converging to an $\\epsilon$ stationary point. The convergence results don't rely on data heterogeneity bounds, which is also interesting. Empirical results on EMNIST and IMDB (in the appendix) show the efficacy of the proposed method.", "questions": "**1.** Is there any intuition for why there is no requirement for any kind of heterogeneity bound for deriving the results of this paper?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**1.** This paper seems to be the first one to provide an algorithm whose hyperparameters are fully independent of the problem-specific parameters such as smoothness constant, stochastic gradient variance bound, etc. However, I'm not up to speed on all the relevant literature.\n\n**2.** It is interesting that the results don't rely on any kind of heterogeneity bound. \n\n**3.** Empirical results show that the proposed method is better than SCAFFOLD.", "weaknesses": "**1.** It is not clear to me what exactly is enabling the algorithm to work with hyperparameters that don't depend on problem-specific parameters. This aspect should be explained better. For instance, does normalization in step 8 of Algorithm 1 enable the hyperparameters to be independent of the smoothness constant? \n\n**2.** How exactly the variation reduction step in PAdaMFed-VR leads to variance reduction should be explained more precisely. The current discussion in Section 3.2 is not very satisfactory. Is this step of PAdaMFed-VR inspired by the update rule of STORM [1]? Also since the relative weights of the gradients at $\\theta_i^{t,k}$ and $\\theta_i^{t-1}$ are different ($1$ and $1-\\beta$, respectively), it'd be helpful to have some discussion on how $\\beta$ should be chosen to reduce the variance and also retain a sufficient amount of client drift control (w/ weight $\\beta$).\n\n**3.** The empirical results show that PAdaMFed is better than SCAFFOLD even after the hyperparameters of SCAFFOLD are tuned. However, from what I understood, the derived convergence results don't indicate this. Can the authors please explain this?\n\n---\n\n[1]: Ashok Cutkosky and Francesco Orabona. \"Momentum-based variance reduction in non-convex SGD\". *Advances in neural information processing systems, 32, 2019*.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kOkKpLazeu", "reviewer": "Reviewer_pGAa", "summary": "The paper studies the convergence of federated averaging algorithms with momentum. Its main contribution is to establish the convergence and convergence rate of these algorithms when the step-sizes and momentum parameters in the local and aggregation algorithms are tuned independently of problem-specific parameters, such as the Lipschitz constant of the gradients. Instead, these parameters depend solely on the number of local and global iterations and the number of nodes sampled in each iteration.", "questions": "Since the number of sampled nodes is used in the parameter selection, what to do if the number of sampled nodes changes between iterations?\n\nIn the numerical results, why only considering accuracy? I get that accuracy, or some similar Machine Learning metrics are important to evaluation for Machine Learning applications. However, all the theory is related to optimization metrics, the size of the gradient norm. It would be good to also show how the numerical results align with the theoretical results in the paper.\n\nIn line 8 of Algorithm 1, why do you take scale the gradient direction with the gradient norm? This means that you don't use the magnitude of the gradient, only the direction of the gradient. This is probably why you don't need Lipschitz constant of the gradient, even in deterministic optimziation algorithms such algorithms converge without using Lipschitz constants, but if we don't use gradient magnitude then convergence rate will be worse worse and compatible to sub-gradient methods, since we are not exploiting the smoothness.\n\nGiven that for your algorithm you did not do any grid search to tune hyperparameters, while grid-search was used for the other algorithms, I am a bit surprised how much better results you get. In my experience, the hyperparameters obtain from the theory are usually not good in practice, usually one can find much better parameters from doing grid search. Would this be the case for your work? \n\nIn Table 1, it would be good if you could also include the complexity bounds.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The topic is important and well motivated. It is indeed a problem that for ensuring theoretical convergence one typically needs parameters like Lipschitz constant on the gradient, which are typically not known. \n\nThe paper is well written and the results look correct, at least the main steps in the proofs look correct.", "weaknesses": "I have some concerns with the setup. Many algorithms already permit diminishing step-sizes that do not require knowledge of the Lipschitz constant of the gradient, such as step-decay or similar approaches, which also come with theoretical guarantees. These methods have the added advantage that step-sizes can start relatively large and decrease over time, while in this approach, the step-size is inversely based on the total number of global and local iterations, which may be large. As a result, the step-sizes in this method are consistently small. There is no comparison to such methods here.\n\nThe experiments are not reproducible, the code is not provided and there is no information about hyper parameter tuning or other details for other algorithms, except that a grid search has been used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LXh3UgwuCD", "reviewer": "Reviewer_ZrV1", "summary": "This paper introduces PAdaMFed, a new federated learning (FL) algorithm that removes dependence on problem-specific parameters, a significant advancement for FL where hyperparameter tuning is often hindered by data heterogeneity and limited local dataset accessibility. By combining adaptive stepsizes and momentum, PAdaMFed aims to manage arbitrary data heterogeneity and partial client participation while achieving state-of-the-art convergence and communication complexities. Empirical results validate the theoretical benefits of PAdaMFed across multiple tasks, demonstrating robustness and scalability.", "questions": "1. I'd like to know the performance of these baselines, particularly FedAvg, which seems to underperform.\n2. I suggest an ablation study to isolate the contributions of adaptive stepsizes and momentum in the PAdaMFed.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The parameter-free design in FL addresses a critical challenge, making this an interesting and important contribution.\n2. Theoretical guarantees, including sample and communication complexities of \\(O(\\epsilon^{-4})\\) and \\(O(\\epsilon^{-3})\\) respectively for the standard version (with further improvements under variance reduction), are rigorously derived and well-supported.", "weaknesses": "1. The \"problem-parameter free\" claim is somewhat unclear. Although the authors suggest that PAdaMFed has no dependency on problem-specific parameters like the smoothness constant \\(L\\), it seems that implicit conditions on \\(L\\) might still affect the learning rate. For example, Assumptions A3 and A4 seem to require some condition on \\(L\\) related to \\(K\\) and \\(T\\), suggesting that the learning rate still indirectly depends on \\(L\\).\n  \n2. From my understanding, achieving a truly problem-parameter free algorithm would typically involve hyperparameter adaptivity based on problem characteristics. Simply incorporating variance reduction and momentum may not fully achieve this goal. In problem-parameter or hyper-parameter free algorithms in centralized learning, the key is to design the adaptivity of these hyper-parameters .\n\n3. The algorithm requires communication of three vectors per round, which is substantial. Since communication often constitutes a major bottleneck in FL, this increase is likely not marginal, especially given the lack of evidence provided to support this claim.\n\n4. I have concerns regarding the experiment results. The baselines, particularly FedAvg, appear to underperform, with an accuracy of only 0.8 on EMNIST IID data. The experimental section would be stronger if it included additional datasets and models, along with an ablation study to isolate the contributions of adaptive stepsizes and momentum, as proposed in the PAdaMFed, to the overall performance.\n\nOverall, this paper targets a meaningful problem and makes a substantial contribution to algorithm design in federated learning, supported by theoretical rigor and empirical evidence. However, its novelty may be limited by reliance on existing algorithmic techniques and proof strategies (e.g., variance reduction and SCAFFOLD).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)