Problem-Parameter-Free Federated Learning

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. To the best of our knowledge, our algorithm is the first to be truely problem-parameter-free in FL, regardless of whether diminishing or constant step sizes are employed. In our approach, the gradient normalization mechanism compensates for conservative step sizes, which provides two key benefits:

• It automatically adjusts the effective step size based on the local optimization landscape;
• It compensates for conservative nominal step sizes through adaptive scaling.

The effectiveness of this approach is validated by both our theoretical analysis and empirical results, where our parameter-free algorithm achieves competitive or superior performance compared to manually-tuned baselines. This demonstrates that careful algorithmic design can overcome the potential limitations of conservative step sizes.

Reply to Weakness 2: Thank you for the comment.

1. We will release our complete codebase upon acceptance via GitHub, including thorough documentation, running scripts, and configuration files.
2. All baselines are trained using the same model architecture as our algorithm: (1) a convolutional neural network (CNN) with three convolutional layers and two fully connected layers for image classification on the EMNIST dataset, and (2) a long short-term memory (LSTM) model for textual sentiment analysis on the IMDB dataset. The gradient search ranges from 1e-1 to 1e-5. Moreover, we have presented the performance of all baseline algorithms versus stepsize in Fig 2 for the image classification task, and the test accuracy in Fig 1 of all those baselines corresponds to the best stepsizes shown in Fig. 2.
3. We have also conducted additional experiments on the CIFAR-10 dataset using a ResNet-18 architecture, where similar results further corroborate our findings.

Reply to Question 1: Thank you for the insightful question regarding varying client participation. While our current theoretical analysis assumes a fixed number of participating clients $S$ per round for analytical tractability, our algorithm can be naturally adapted to accommodate variations in client participation. For scenarios with fluctuating client participation, we can define a variable $S_{min}$ to represent the minimum expected number of participants per round. The analysis remains valid by replacing $S$ with $S_{min}$.

Reply to Question 2: Thank you for this valuable suggestion. Test accuracy indeed serves as the primary measure of generalization performance, which is a core objective in machine learning applications. While optimization metrics (e.g., gradient norm) can indicate convergence during training, they do not necessarily reflect model performance on unseen data. Nonetheless, we agree that optimization metrics provide useful insights into algorithmic behavior. In the revised version, we have included gradient norm trajectories in Fig. 4 of the revised version.

Reply to Question 3: Thank you for the comment.

1. The gradient normalization in Line 8 enables adaptive step-sizes of our algorithm by automatically adjusting to the local optimization landscape. While the normalization only focus on the gradient direction, our algorithm maintains competitive convergence through two complementary mechanisms:

• The momentum term accumulates gradient information across iterations, helping to preserve magnitude-related information over time
• The control variates help reduce variance and maintain alignment with the global objective

2. It's important to note that our convergence analysis relies on the Lipschitz constant of the gradient (which is acutally the smoothness parameter $L$ in our paper). The gradient normalization, combined with our carefully designed control variates and momentum, ensures that we fully exploit the problem structure without requiring explicit knowledge of these constants. Our theoretical guarantees show that the design of our algorithm still maintains start-of-the-art convergence properties while achieving problem-parameter free operation.

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: We appreciate this thoughtful question about the "problem-parameter free" property. We would like to clarify the following two key points:

1. The term "problem-parameter free" refers to algorithms that do not require problem-specific parameters (such as smoothness constant $L$) for tuning in practice. In our algorithm, the learning rates are explicitly determined by only system-defined constants: the number of participating clients $S$, local update iterations $K$, and communication rounds $T$. These are configuration parameters that are known and set by the system administrator, rather than problem-specific parameters that would need to be estimated or tuned.

2. While our theoretical analysis includes assumptions involving the smoothness constant $L$ (e.g., Assumption 1), these assumptions are standard regularity conditions that establish the problem setting, rather than parameters needed for algorithm execution. Importantly, $L$ remains independent of both $K$ and $T$, and knowledge of $L$ is not required to run the algorithm. The practical implementation of PAdaMFed depends only on the system-defined constants ($S, K, T$), making it truly parameter-free from an operational perspective. Additionally, we would like to clarify that this paper only make three assumptions and Assumptions 1 and 2 are related to $L$-smoothness. But the smoothness condition on $L$ is independent of both the number of clients $K$ and the 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 achieves parameter-free operation through careful algorithmic design that incorporates automatic adaptivity. Specifically, the gradient normalization mechanism in Step 8 serves as the key adaptive component:

1. The normalization automatically adjusts step sizes based on the local optimization landscape, effectively providing adaptive learning rates without requiring manual tuning. This design ensures:

• Larger steps in regions with small gradients where more aggressive exploration is beneficial;
• Smaller steps in steep regions where careful progress is needed;
• Uniform update magnitudes across clients, preventing any single client from having disproportionate influence.

2. This adaptive mechanism, combined with momentum and control variates, creates a truly self-tuning system where:

• Update magnitudes are automatically calibrated based on local gradients;
• The effective step size becomes proportional to the ratio between learning rate and gradient norm;
• Client heterogeneity is naturally handled without requiring explicit bounds or parameters.

Our approach thus achieves parameter-free operation through algorithmic adaptivity rather than manual tuning, making it robust across diverse federated learning scenarios.

Reply to Weakness 3: We appreciate the concern about communication efficiency. We would like to clarify the actual communication overhead of our algorithm:

Uplink (client → server): Each client transmits two vectors per round: $\boldsymbol\theta_i^{t,K}$ and $\boldsymbol{c}_i^t$.

Downlink (server → clients): Originally appears to require three vectors: $\boldsymbol\theta^t$, $\boldsymbol{c}^t$, and $\boldsymbol{g}^t$. However, we can optimize this by combining $\boldsymbol{c}^t$ and $\boldsymbol{g}^t$ into a single term $\beta\boldsymbol{c}^t + (1-\beta)\boldsymbol{g}^t$. This optimization reduces downlink communication to two vectors.

With this implementation, our algorithm achieves the same communication overhead as SCAFFOLD, making it communication-efficient while maintaining its parameter-free advantages.

Reply to Weakness 4: We appreciate these thoughtful suggestions about the experimental evaluation. Our responses to each point of the comment is listed below:

1. Regarding FedAvg's performance on EMNIST: Our results are consistent with previous studies in the literature. For instance, references [1] and [2] reported similar convergence rates for FedAvg under comparable settings. In our simulation, the performance of all baseline algorithms were implemented under identical experimental conditions as our algorithms to ensure fair comparison.
2. We have enhanced our experimental results in the revised version (as provided in Appendix D.1) by:

• Including additional experiments on CIFAR-10 dataset;
• Conducting comprehensive ablation studies to analyze the individual contributions of adaptive stepsizes and momentum;
• Providing detailed analysis of how each component affects the overall performance.

3. To ensure reproducibility and facilitate further research, we will release our code on GitHub upon acceptance.

[1] J. Pei, W. Li and S. Mumtaz, "From Routine to Reflection: Pruning Neural Networks in Communication-efficient Federated Learning," in IEEE Transactions on Artificial Intelligence, 2024, doi: 10.1109/TAI.2024.3462300.

[2] V. S. Mai, R. J. La, T. Zhang, Y. Huang and A. Battou, "Federated Learning With Server Learning for Non-IID Data," 2023 57th Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA, 2023, pp. 1-6.

Reply to the following comment in the Weaknesses:

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

Reply: We sincerely appreciate the reviewer for recognizing our contributions. However, we would like to emphasize that our algorithm introduces significant innovations aimed at overcoming specific challenges of problem-specific parameter tuning in federated learning.

1. Our primary goal is to design a truly parameter-free federated learning algorithm that eliminates dependency on all problem-specific parameters while maintaining state-of-the-art convergence. This is achieved through the careful integration of three essential components:

• Local gradient normalization for adaptive step-sizes;
• Client-side momentum for heterogeneity bounding;
• Control variates for "client-drift" control.

2. The theoretical analysis of our algorithm follows a significantly different path from SCAFFOLD's proof technique. Our analysis requires novel theoretical tools to handle the interplay between gradient normalization, momentum, and control variates, while establishing convergence guarantees without requiring knowledge of problem parameters.
3. Our algorithms also eliminate the need for data heterogeneity bounds, which is an important advancement than the SCAFFOLD algorithm.
4. The variance reduced version PAdaMFed-VR is an extension of our original algorithm PAdaMFed to further accelerate its convergence. Even without variance reduction, PAdaMFed demonstrates state-of-the-art performance compared to existing non-variance-reduced algorithms.

This paper advance the field by providing a more robust and adaptable solution to federated learning challenges. We appreciate your recognition of the meaningful problem we address and the substantial contributions we make.

Reply to Question 1: Thank you for this question. Our answer can refer to the Reply to Weakness 4.

Reply to Question 2: We appreciate the suggestion to conduct an ablation study. By isolating the effects of adaptive step sizes and momentum, we can better understand their individual contributions to PAdaMFed's performance. Figure 5 of the revised manuscript presents our comprehensive ablation analysis examining test accuracy and step size robustness with respect to these two key components (momentum and gradient normalization). The results demonstrate that momentum enhances convergence speed by effectively aggregating descent directions across clients and iterations. Meanwhile, gradient normalization facilitates adaptive step size adjustment, enabling parameter-free tuning of our algorithm.

Thank you once again for your thoughtful review and constructive feedback.

Thank you for your follow-up comment and for pointing out your concerns. We would like to clarify the following points to address the issues raised:

1. Difference from Normalized Gradient Methods: The reference provided by the reviewer (https://parameterfree.com/2023/06/19/adapting-to-smoothness-with-normalized-gradients) focuses on the deterministic setting, where exact gradients are available at each step. In contrast, our work addresses the stochastic setting inherent to federated learning (FL), where only noisy, stochastic gradients are available at each update. This distinction is critical, as it has been formally shown (e.g., reference [1], Table 1) that normalized stochastic gradient descent cannot converge to the optimal solution even in the centralized case. Our contribution lies in overcoming this limitation by proposing a novel algorithm that achieves convergence in this more challenging stochastic environment.

[1] Yang, Junchi, et al. "Two sides of one coin: the limits of untuned SGD and the power of adaptive methods." Advances in Neural Information Processing Systems 36 (2024).

2. Challenges Unique to Federated Learning: Federated learning introduces distinct challenges that are fundamentally different from the centralized case considered in normalized SGD methods. The presence of multiple local updates in FL exacerbates issues like client drift, especially under data heterogeneity. These challenges cannot be addressed by a simple reduction to a one-step centralized case. To mitigate client drift, we introduce a novel integration of control variates with momentum. This contribution is not only algorithmically innovative but also requires non-trivial theoretical analysis to account for the interactions between control variates and momentum in a federated setting. Our algorithm also exhibits another important innovation in the elimination of explicit heterogeneity bounds, which have been a standard requirement in prior federated learning literature.
3. Definition of Problem-Parameter-Free: We use the term "problem-parameter-free" in the commonly accepted sense, where it describes an algorithm that avoids explicit dependence on problem-specific parameters such as the smoothness constant or Lipschitz constant. Our method adheres to this definition, as it does not require tuning or even knowledge of such parameters, which is a significant departure from traditional FL algorithms. While normalized gradient methods can adapt to smoothness in the deterministic setting, their limitations in stochastic and federated settings render them insufficient for addressing the challenges we solve.

In summary, while we appreciate the reviewer’s concerns and the reference provided, we believe our work makes significant contributions by addressing the unique challenges of the stochastic and federated setting. Our approach is fundamentally different from normalized gradient descent methods in deterministic optimization, as we overcome their known limitations in stochastic and federated scenarios. We would be happy to further clarify any remaining concerns and thank you again for your valuable feedback.

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 this valuable suggestion. We have added more explanations in Section 4.2 of our paper on how our algorithm achieves hyperparameter independence. The reviewer is right that the gradient normalization in Step 8 is indeed the key mechanism enabling our algorithm to operate without problem-specific parameters. This gradient normalization serves as an adaptive learning rate scheme, automatically adjusting step sizes based on the local optimization geometry — taking larger steps when gradients are small and smaller steps when gradients are large. It also provides us the convenience on quantifying the distance between consecutive models in our theoretical analysis, maintaining that $||\theta_i^{t, k+1}-\theta_i^{t,k}||= \eta$ for all $i, k, t$.

Momentum and control variables are also indispensable to achieve the satisfactory performance of our algorithm. 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, it accelerates progress in directions of consistent gradient agreement. Control variates align local 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-specific parameters such as smoothness parameters and heterogeneity bounds, simplifying the tuning process and enhancing robustness across diverse FL applications.

Reply to Weakness 2: Thank you for the comment. The variance reduction technique used by PAdaMFed-VR is derived from the update rule of STORM. Specifically, the term $g_i^{t,k}$ in PAdaMFed-VR can be expressed as: $g_i^{t,k} = \beta\left( \nabla F(\theta_i^{t,k};\xi_i^{t,k}) - \boldsymbol{c}_i^{t-1} + \boldsymbol{c}^{t-1} \right) + (1-\beta) \boldsymbol{g}^{t-1} + (1-\beta) \left( \nabla F(\theta_i^{t,k};\xi_i^{t,k}) - \nabla F(\theta^{t-1};\xi_i^{t,k})\right).$ The first two terms are utilized in the non-variance-reduced PAdaMFed, while the effect of variance reduction is due to the last difference term, similar to STORM. We thank the reviewer for pointing out this vagueness in our paper. We have added a clearer explanation in the revised version.

Reply to Weakness 3: Thank you for the comment. The strong performance of our algorithm can be attributed to two key design elements that provide inherent adaptivity:

1. Gradient normalization: Gradient normalization serves as an adaptive learning rate scheme, automatically adjusting step sizes 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). This per-step adaptivity can potentially achieve better performance than fixed learning rates, even when the latter are optimized through grid search.

2. Momentum: Our momentum-based update design helps accelerate convergence while maintaining stability. The momentum term provides two key benefits: it helps overcome local irregularities in the loss landscape by accumulating gradients over multiple iterations, and it accelerates progress in directions of consistent gradient agreement.

These adaptive mechanisms enable our algorithm to achieve strong performance without manual tuning, as they continuously optimize the learning dynamics throughout the training process.

Reply to Question 1: Thank you for the question. The use of momentum helps eliminate the requirement for data heterogeneity bounds. At each global round, the momentum is updated as follows: $g^{t} = \frac{\beta}{SK}\sum_{i\in S_t}(\sum_{k=1}^K\nabla F(\theta_i^{t,k};\xi_i^{t,k})-\mathbf{c}_i^{t-1})+\beta\mathbf{c}^{t-1}+(1-\beta)g^{t-1}$

$~~~=\frac{1}{SK}\sum_{i\in S_t}\sum_{k=1}^Kg_i^{t,k}.$ This accumulates the gradient directions across clients and iterations, providing an "anchoring" effect that effectively mitigates the “client-drift” phenomenon. In the extreme case where $\beta=0$, all clients remain synchronized in their local updates, eliminating the drift caused by data heterogeneity in the vanilla FEDAVG. By appropriately choosing the coefficient $\beta$, our algorithm achieves state-of-the-art convergence while removing the necessity for data heterogeneity assumptions.

Thank you once again for your thoughtful review and constructive feedback.

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: We sincerely appreciate the reviewer for pointing this out. SCAFFOLD-M achieves a convergence rate of $\frac{1}{T}\sum_{r=0}^{T-1}\mathbb{E}[||\nabla f(\theta^t)||^2] \leq \mathcal{O}\left(\sqrt{\frac{L\Delta\sigma^2}{SKT}} + \frac{L\Delta}{T}\left(1 + \frac{N^{2/3}}{S}\right)\right)$. While this bound is theoretically superior to our method by a factor of $\frac{N^{2/3}}{S}$ in the second term, the overall convergence behavior is primarily governed by the first term. Therefore, our comparative analysis focuses on the dominant first term, which represents the primary bottleneck in practical convergence.

In the revised version, we have explicitly incorporated this theoretical distinction to provide a more comprehensive comparison.

Reply to Weakness 2: We sincerely appreciate the reviewer for bringing [1] to our attention. We have added a comprehensive comparison of our work with [1] in the revised version. While both papers address problem-parameter free optimization, our work additionally need to handle the unique challenges inherent in federated learning. The key distinction lies in addressing client drift—a critical issue that emerges from multiple local updates and data heterogeneity in federated settings. Compared to [1], our main technical contributions are:

• The novel integration of control variates with momentum to mitigate client drift, which requires sophisticated theoretical analysis due to their non-trivial interactions.
• The elimination of explicit heterogeneity bounds that were previously required in federated learning literature.

Reply to the Minor Weakness: We sincerely appreciate the reviewer for pointing this out. We have clarified this choice throughout the manuscript. Our analysis uses $||\nabla f(\theta^t)||$ instead of $||\nabla f(\theta^t)||^2$ as this emerges naturally from our theoretical framework for establishing problem-parameter-free convergence. While conventional federated learning analyses typically employ the squared gradient norm, our novel proof technique specifically requires direct analysis of the gradient norm to achieve parameter-free convergence guarantees.

To facilitate comparison with existing literature, we have demonstrated how our results translate to the conventional $||\nabla f(\theta^t)||^2$ metric in the revised version through the following relationship: $\frac{1}{T} \sum_{t=1}^{T-1} \mathbb{E} \|\nabla f(\theta^t) \| = \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E} \sqrt{\|\nabla f(\theta^t) \|^2} \leq \frac{1}{T} \sum_{t=0}^{T-1} \sqrt{\mathbb{E} \|\nabla f(\theta^t)\|^2} \leq \sqrt{\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E} \|\nabla f(\theta^t)\|^2 }$ where the first and second inequalities utilizes Jensen’s inequality as the square root function is concave. Therefore, our results can be translated to the conventional $||\nabla f(\theta^t)||^2$ metric by squaring both sides of our convergence bounds.

Reply to Question 1: Thank you for your question. In our current analysis, we have achieved state-of-the-art convergence rates by relying on assumptions of smoothness (Assumptions 1 and 2) and stochastic gradient variance (Assumption 3). While these assumptions are sufficient for our theoretical guarantees, incorporating additional assumptions could potentially enhance the convergence bounds. If an extra assumption, such as strong convexity, were introduced, it's likely that we could derive tighter convergence bounds. These modifications might allow us to recover or even improve upon the optimal convergence rates observed in other algorithms. However, our focus has been on maintaining a robust and broadly applicable framework with minimal assumptions. We are open to exploring these possibilities in future work to further enhance the theoretical and practical performance of our algorithm.

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. While we appreciate the observation regarding SCAFFOLD, we respectfully disagree that PAdaMFed is merely a direct extension with momentum. Our work has a fundamentally different objective and makes distinct technical contributions:

1. Our primary goal is to design a truly parameter-free federated learning algorithm that eliminates dependency on all problem-specific parameters while maintaining state-of-the-art convergence. This is achieved through the careful integration of three essential components:

• Local gradient normalization for adaptive step-sizes;
• Client-side momentum for heterogeneity bounding;
• Control variates for "client-drift" control.

2. The theoretical analysis of our algorithm follows a significantly different path from SCAFFOLD's proof technique. Our analysis requires novel theoretical tools to handle the interplay between gradient normalization, momentum, and control variates, while establishing convergence guarantees without requiring knowledge of problem parameters.

While both algorithms use control variates, PAdaMFed's parameter-free nature and incorporation of adaptive mechanisms represent fundamental innovations rather than incremental extensions. Notably, our algorithms also eliminate the need for data heterogeneity bounds, which is an important advancement than the SCAFFOLD algorithm.

Reply to Weakness 2 and Question 1: Thank you for the comment. The proof of our algorithm presents several unique challenges compared to SCAFFOLD's analysis:

1. Handling normalized gradients: Our use of gradient normalization introduces new mathematical complexities. We need to carefully track how normalization affects the relationship between consecutive model updates. Special techniques are required to analyze the interaction between normalized gradients and momentum.
2. Momentum analysis: The introduction of momentum terms creates additional coupling between iterations. We need to bound the accumulated effects of momentum across multiple updates. The interaction between momentum and control variates requires novel analysis techniques.
3. Parameter-free guarantees: Proving convergence without relying on problem-specific parameters requires different analytical tools. We need to show that gradient normalization effectively compensates for the lack of parameter-dependent step sizes. The analysis must demonstrate that convergence holds across different problem settings without parameter tuning.

These challenges required developing new proof techniques that differ significantly from SCAFFOLD's analysis approach.

Reply to Question 2: Thank you for the comment.

1. We have enhanced our explanation on the gain of our proposed algorithms in the revised manuscript. Specifically, the gain of our PAdaMFed algorithm stems from the synergistic integration of three indispensable components:

• Gradient normalization serves as an adaptive learning rate scheme, automatically adjusting step sizes 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).
• 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, it accelerates progress in directions of consistent gradient agreement.
• Furthermore, control variates align local 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-specific parameters such as smoothness parameters and heterogeneity bounds, simplifying the tuning process and enhancing robustness across diverse FL applications.

2. We have provided 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.

Thank you once again for your thoughtful review and constructive feedback.