Problem-Parameter Free Federated Learning
Adaptive federated learning;problem-parameter free;arbitrary data heterogeneity;adaptive stepsize
**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.**

**Reply to Weakness 1:**  Thank you for the comment. 1) The term "problem-parameter free" refers to algorithms that do not require problem-specific parameters for tuning. We adopt this terminology following established literature in the field. In our approach, the learning rates are explicitly determined by three system-defined constants: the number of participating clients $S$, local update iterations $K$, and communication rounds $T$, and is independent of problem-specific parameters. 

2) Our work relies on three assumptions, among which A1 and A2 involve the smoothness constant $L$. However, it is important to note that $L$ remains independent of both the local update iterations $K$ and communication rounds $T$. For reference, our Assumption 1 is cited below:

>**Assumption 1.** *Given any $\xi$, the sample-wise loss function $F(\boldsymbol\theta; \xi)$ is $L$-smooth, i.e., $||\nabla F(\boldsymbol\theta; \xi)-\nabla F(\boldsymbol\delta; \xi)|| \leq L||\boldsymbol\theta-\boldsymbol\delta||$ for all $\boldsymbol\theta,\boldsymbol\delta \in \mathbb{R}^{d}$.*

**Reply to Weakness 2:**  Thank you for the comment. Our algorithm incorporates hyperparameter adaptivity through gradient normalization, implemented in Step 8. This normalization mechanism ensures uniform update magnitudes across all clients, effectively preventing any single client from exerting disproportionate influence on the global model updates. Such design enhances the robustness and stability of the federated learning process. 

**Reply to Weakness 3:**  Thank you for the comment. For uplink communication of our algorithm, each client transmits two vectors per round: $\boldsymbol\theta_i^{t,K}$ and $\boldsymbol{c}_i^t$. The downlink broadcast, which originally consists of $\boldsymbol\theta^t$, $\boldsymbol{c}^t$, and $\boldsymbol{g}^t$, can be optimized by combining the latter two vectors into a single term $\beta\boldsymbol{c}^t + (1-\beta)\boldsymbol{g}^t$. After this revision, our algorithm achieves an equivalent communication overhead to SCAFFOLD.

**Reply to Weakness 4:**


**Reply to Question 1:**


**Reply to Question 2:** Thanks for the comment. We have added the comparion with only the momentum, named SCAFFOLD-M, in our comparisons. Based on the analysis for the centralized problem-parameter free algrorithm in [], only add normalization can lead to the algorithm diverse since after the expectaion, the normalized gradient direction is zero.
Point-to-Point Responses
Yes
N/A.
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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).
Yes
No ethics review needed.
**1.** Is there any intuition for why there is no requirement for any kind of heterogeneity bound for deriving the results of this paper?
**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.
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.
**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*.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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).
@inproceedings{
anonymous2024problemparameter,
title={Problem-Parameter Free Federated Learning},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=ZuazHmXTns},
note={under review}
}
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, making it, to our knowledge, the first FL algorithm to achieve such problem-parameter-agnostic adaptation; 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})$, 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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Adaptive federated learning problem-parameter free arbitrary data heterogeneity adaptive stepsize
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/c3f3f08a2ceef5a9cf6ef2d67ff75eda852ae2d6.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Problem-Parameter Free Federated Learning
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission