Problem-Parameter-Free Federated Learning

Authors: Wenjing Yan, Kai Zhang, Xiaolu Wang, Xuanyu Cao
Primary area: optimization
Keywords: adaptive federated learning, problem-parameter free, arbitrary data heterogeneity, adaptive stepsize

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.

Decision: accept (oral)
Reviewer scores: 8, 8, 8, 8, 6

Reviews and discussion:
<thread>
creation date:
1730168516115

thread_type:
official_review

<thread_object>
creator: reviewer_zrv1

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

strengths:
1. The parameter-free design in FL addresses a critical challenge, making this an interesting and important contribution.
2. 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\).
  
2. 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 .

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

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

Overall, 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).

questions:
1. I'd like to know the performance of these baselines, particularly FedAvg, which seems to underperform.
2. I suggest an ablation study to isolate the contributions of adaptive stepsizes and momentum in the PAdaMFed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730210634717

thread_type:
official_review

<thread_object>
creator: reviewer_pgaa

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

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. 

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

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

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?

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

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

Given 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? 

In Table 1, it would be good if you could also include the complexity bounds.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730440892571

thread_type:
official_review

<thread_object>
creator: reviewer_xnsx

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

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.

**2.** It is interesting that the results don't rely on any kind of heterogeneity bound. 

**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? 

**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$).

**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?

---

[1]: Ashok Cutkosky and Francesco Orabona. "Momentum-based variance reduction in non-convex SGD". *Advances in neural information processing systems, 32, 2019*.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730482055786

thread_type:
official_review

<thread_object>
creator: reviewer_xeqx

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

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.

2- There are not many works in the literature that study problem-independent parameters; this work is one of the first.

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

2- Empirical results are limited. Experiments for different architectures and datasets can help improve the paper and show its effectiveness.

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

Minor: 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.

[1] Li, Jiaxiang, et al. "Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization." arXiv preprint arXiv:2402.08821 (2024).

questions:
1- Can you recover the optimal bound with the extra assumption and different learning rates?

2- Can you design an experiment in which the gradient dissimilarity assumption does not hold and other methods fail to converge?

suggestion: 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731352029455

thread_type:
official_review

<thread_object>
creator: reviewer_a59w

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

strengths:
1. The proposed PAdaMFed is independent of the problem parameters such as gradient divergence. 

2. The author also designed PAdaMFed-VR to reduce the variance of the federated learning algorithm.

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

2. The challenge in the proof is unclear.

questions:
1. What are the challenges in the proof compare to the proof in the SCAFFOLD algorithm?

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

Karimireddy, 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732513846386

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Follow-Up: Request for ICLR Rebuttal Response

comment:
Dear Reviewers,

Thank you again for taking the time to review our paper and provide your valuable feedback. As the rebuttal period comes to a close, we wanted to kindly check if our clarifications in the rebuttal have satisfactorily addressed the concerns raised in your initial review. Your feedback is invaluable to us.

If so, we respectfully request you to consider updating your review score based on our responses. However, if you have any remaining questions or need further clarification from us, please do not hesitate to let us know.

Once again, we sincerely appreciate your time and consideration. Your prompt response would be greatly appreciated.

Sincerely,

Authors of the paper
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a novel federated learning algorithm, PAdaMFed, designed to be "problem-parameter-free". Specifically, as the authors clarify, the stepsize and momentum parameters required for the method depend only on system configurations, such as the total number of iterations and the number of clients, rather than on problem-specific parameters like smoothness.

The *parameter-free* property is achieved through normalized gradient updates performed locally, which ensure that the stepsize and momentum parameters do not depend on problem-specific parameters like smoothness. Additionally, the algorithm incorporates control variate-based drift correction (as in SCAFFOLD) and momentum-based variance reduction (similar to STORM), enhancing its robustness and efficiency in the federated learning setting. 

The authors provide a theoretical analysis, proving convergence to stationary points for smooth, potentially non-convex functions.

Overall, this paper addresses an important and timely problem in federated learning and substantially contributes to algorithm design. The proposed method is not only theoretically sound but also practically relevant, as it eliminates the need for problem-specific parameter tuning. This work will likely inspire further research on adaptive and robust algorithms for federated learning.

---
Comment:
I do not agree with the authors' response to reviewer XEQX (resp. their added footnote 1 on page 6). The provided inequality appears to go in the wrong direction. A transfer of the results might be possible when considering $\min_{t} ||\nabla f(\theta^t)||^2$, but the result does not necessarily hold for the average gradient norm squared.