FeedSign: Full-parameter Federated Fine-tuning of Large Models with Extremely Low Communication Overhead of One Bit

Authors: Zhijie Cai, Haolong Chen, Guangxu Zhu
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Large Model Fine-tuning, Federated Learning, Heterogeneity Resilience, Byzantine Resilience

Abstract:
Federated fine-tuning (FFT) aims to fine-tune a pre-trained model with private data from distributed clients by exchanging models rather than data under the orchestration of a parameter server (PS). However, as large models are acing in almost every machine learning task, the communication overhead and memory demand are surging accordingly, hindering the practical deployment on consumer devices. To overcome the bottleneck forged by the growing communication overhead of federated learning and lower the high memory demand of large model fine-tuning, we propose FeedSign, an FFT algorithm where a client uploads its update model and downloads the global model of any size using exactly $1$ bit per step, while the memory demand is squeezed to the amount needed for inference. This is realized by utilizing zeroth-order (ZO) optimizers on large models and shared pseudo-random number generators (PRNG) across devices to split the gradient estimate from the clients to 1) a direction corresponding to a designated random seed and 2) a binary vote from the client indicating whether the seed-corresponding direction grants a local loss descent, which is the only information the clients should convey to the PS. We conduct theoretical analysis on FeedSign and show that it converges at an exponential rate $\mathcal{O}(e^{-t})$, where $t$ is the number of elapsed steps, the same rate as in first-order (FO) methods can attain in big $\mathcal{O}$ notation. Moreover, it is also found that FeedSign enjoys good robustness against data heterogeneity and Byzantine attacks. We conduct extensive experiments on models across different structures and sizes (11M to 13B) and found that the proposed method performs better or closely, depending on scenarios, compared to its ZO and FO counterparts albeit an orders-of-magnitude lower communication overhead. We also discuss some interesting advantages as byproducts guaranteed by the minimalistic design of FeedSign.

Decision: reject
Reviewer scores: 5, 5, 5, 6

Reviews and discussion:
<thread>
creation date:
1730456391668

thread_type:
official_review

<thread_object>
creator: reviewer_rcz7

<content>
summary:
This paper presents FeedSign, a federated fine-tuning (FFT) method that significantly reduces communication overhead for large models, requiring just one bit per step. Unlike conventional FFT, which demands high memory and communication, FeedSign uses zeroth-order optimization and a shared random generator to let clients signal only a binary vote indicating local model improvement. This keeps memory demands low and is compatible with a range of device constraints. FeedSign converges at rates similar to first-order methods and is robust against data heterogeneity and Byzantine attacks, performing on par with or better than other FFT methods across model sizes up to 13 billion parameters.

strengths:
* Strong experimental results: the considered experimental setups are diverse and feature strong baselines, and the results of the proposed methods seem to be on par or better than the considered baselines. 
* The idea of communication one bit of information is quite simple and could be used in practice.

weaknesses:
* **Byzantine Resilience.** The paper could explore a broader range of Byzantine attacks and defenses, since “Byzantine resilience” refers to the ability of tolerating arbitrary corruptions. While robustness to basic Byzantine failures (Section 4.3) is a positive outcome, the method’s effectiveness against specific attacks (e.g., label flipping, gradient noise injection) is unclear. For instance, Allouah et al. (2023) explored representative defenses and attacks that might be relevant here, and integrating or testing such techniques could enhance FeedSign’s security profile.

* **Novelty Consideration.** Although FeedSign introduces an efficient mechanism for communication reduction, the reliance on sign-based updates and zeroth-order optimization is not entirely novel. Techniques like sign-SGD have been previously studied for Byzantine-resilient federated learning (Li et al. 2019), and zeroth-order methods are known in federated contexts. While FeedSign’s combination of these ideas is compelling, the novelty could be highlighted more by contrasting its specific contributions with these prior works in-depth.

* **Practical Relevance of Assumptions.** Assumption 2, in particular, appears to impose conditions that may not align with realistic settings. Further analysis or empirical evaluation showing how sensitive FeedSign’s performance is to deviations from this assumption would clarify the applicability of the theoretical results.

### References

Li et al. (AAAI 2019). RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets.

Allouah et al. (AISTATS 2023). Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity.

questions:
1. Could the authors clarify how FeedSign would handle more advanced Byzantine attack scenarios beyond "random" faults? Are there defenses that could be integrated into FeedSign to enhance robustness without substantially increasing communication costs?

2. The reliance on Assumption 2 for theoretical guarantees may limit FeedSign’s applicability in real-world data distributions. Could the authors provide empirical insights or adjustments to make this assumption more practical?

3. Since FeedSign’s communication relies on PRNG and zeroth-order methods, do these choices introduce any potential issues with reproducibility or variance in results across different clients, and if so, how might they be mitigated?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730512949181

thread_type:
official_review

<thread_object>
creator: reviewer_g6og

<content>
summary:
This paper introduces FeedSign, a federated fine-tuning framework that employs zeroth-order (ZO) optimizers and pseudo-random number generators, aiming to reduce communication overhead from 64 bits to 1 bit per communication round. While this technical innovation represents a noteworthy advancement in communication per round, the practical relevance of such a reduction remains debatable, particularly given the existing sufficiency of bandwidth for 64 bits. Furthermore, FeedSign does not demonstrate a clear performance advantage over existing frameworks such as FwdLLM and FedKSeed, which undermines its overall contribution.

strengths:
1 The motivation of this paper is well shown. 
2 Detailed proof is given.

weaknesses:
1 Lack of convergence speed analysis. The paper lacks a comprehensive analysis of the convergence speed, which is critical as it seems to be the tradeoff between FeedSign and conventional methods (like FedAvg). Adding a direct comparison can better validate the proposed method.

2 Performance Comparison Deficits: Despite its lower communication cost, FeedSign does not surpass ZO-FedSGD in several performance metrics across different experiments. The marginal reduction of 63 bits in communication cost per round is not adequately justified as a significant advantage over the existing methods, especially when FeedSign does not exhibit faster convergence. This could result in an increased number of communication rounds, negating its low bandwidth benefits. Figure 2 underscores this issue, showing that ZO-FedSGD can achieve faster convergence speed.

3 Vague Claims of Superiority: The paper claims that FeedSign offers “numerous surprising benefits” over its predecessors. However, these benefits are not well-defined or substantiated beyond the reduced communication requirement, making these claims appear overstated. The advantages over the frameworks in [1], [2], and [3] are ambiguously presented and lack clear support. The contribution should be strengthened.

4 Limited Client Participation: The experimental setup with only five participating clients raises questions about the scalability and generalizability of FeedSign. Testing with a larger client pool could provide more robust insights into the framework’s performance across diverse federated environments.

[1] Mengwei Xu, Dongqi Cai, Yaozong Wu, Xiang Li, and Shangguang Wang. {FwdLLM}: Efficient federated finetuning of large language models with perturbed inferences. In 2024 USENIX Annual Technical Conference (USENIX ATC 24), pp. 579–596, 2024
[2] Zhen Qin, Daoyuan Chen, Bingchen Qian, Bolin Ding, Yaliang Li, and Shuiguang Deng. Federated full-parameter tuning of billion-sized language models with communication cost under 18 kilobytes.
[3] Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes.

questions:
See Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730659943623

thread_type:
official_review

<thread_object>
creator: reviewer_wf4n

<content>
summary:
The paper proposes FeedSign and ZO-FedSGD as two methods to fine tune large models in an FL setting with communication efficiency. They utilize zeroth-order gradient estimation to also reduce the computational complexity in the edge devices. In the ZO-FedSGD method, each client samples a seed and computes the gradient estimator coefficient and shares the seed and the coefficient with the server (64 bits per round). In the FeedSign method, the seed is shared by the server to all clients, and clients compute their gradient estimator coefficient for that seed and send the sign of that estimator to the server (1 bit per round). In Theorem 1, they proved that the method converges with exponential rate O(e^{-t}). They evaluate the method's performance under different models and datasets for different tasks. Also the differential private version of FeedSign (DP-FeedSign) is proposed in theorem 2.

strengths:
The paper introduces a novel approach to minimizing communication overhead in fine-tuning large models by communicating only one bit per round, regardless of model size, structure, or task. This method combines communication efficiency with the computational efficiency of a zeroth-order gradient estimator in each client, which reduces memory requirements by estimating gradients through inference rather than backpropagation. The methods for both ZO-FedSGD and FeedSign are detailed in Algorithm 1. For the FeedSign method, which employs a voting mechanism, robustness against Byzantine attacks is achieved.
The exponential convergence rate O(e^{-t}) is proved in Theorem 1, and a comprehensive set of experiments is provided for various model architectures (ResNet, ViT, RoBERTa, OPT) and scales (ranging from 11M to 13B parameters).
The paper addresses the critical challenge of communication in federated learning by reducing communication overhead to one bit per round for FeedSign and 64 bits for ZO-FedSGD. It also tackles computational limitations in edge devices through the use of a zeroth-order gradient estimator. The method scales effectively to very large models (up to 13B parameters) and offers additional benefits, such as enhanced parameter security and privacy guarantees as byproducts.

weaknesses:
1- The ZO-FedSGD method is a distributed version of a zeroth-order algorithm, similar to MeZO, and is referenced in other forms in some citations within the paper. However, it does not appear to be the main contribution of the paper; instead, FeedSign is presented as the primary contribution, which is theoretically and practically distinct from previous work.

2- The assumption that FeedSign is unbiased is fundamentally inaccurate. In FeedSign, only the sign of $p$ is transmitted and aggregated, which would only yield unbiasedness if all $p$ values were uniformly $+1$ or $-1$. Since this is not the case, Lemma 1 holds only for ZO-FedSGD and does not apply to FeedSign. Consequently, it cannot be used in Theorem 1, and the proof of convergence for FeedSign in Theorem 1 should be revised.

3- In the experimental section, Table 1 shows instances where FeedSign or ZO-FedSGD achieve better accuracy than the centralized version, which seems improbable under the same scenario, as a decentralized version typically cannot surpass the accuracy of its centralized counterpart. If different scenarios were used for fine-tuning, this should be specified in the section, along with a rationale for selecting particular scenarios for the experiments.

questions:
1- Your method clearly introduces bias in gradient estimation by using only signs. Have you analyzed how this bias affects the convergence compared to unbiased ZO-FedSGD? Why does FeedSign still work well despite being biased?
2- Is there any theoretical bound on the bias of the method?
3- Is there any theoretical prove for the convergence of the FeedSign considering its a biased estimation of the gradient?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730719329216

thread_type:
official_review

<thread_object>
creator: reviewer_qg9z

<content>
summary:
This work studies Federated fine-tuning (FFT) realized by utilizing zeroth-order (ZO) optimizers. By using shared pseudo-random number generators (PRNG) across devices, the authors suggest to compress the transmitted gradients using 1-bit; which is in turn robust, as a result of the associated low-influence per-client. A convergence analysis is provided, demonstrating exponential rate similarly to the first-order (FO) methods. An experimental stay and a discussion are further presented, where the latter extends the proposed algorithm into a differentially private one.

strengths:
Quality & Clarity:
- The paper is well written and presented.
- The provided convergence analysis supports the validation of the presented algorithm. 
- The discussion section is comprehensive. 
- The reference to ZO-FedSGD is clear and easy- to-follow.

weaknesses:
Originality & Significance:
- Compressed FL has been extensively studied in literature. Specifically, the idea of clients voting via 1-bit compression and shared source-of-randomness; its differentially private version; and its implied associated robustness due to the implicit low-influence of its clients; have all already been presented in: 1) Lang, Natalie, et al. "CPA: Compressed private aggregation for scalable federated learning over massive networks." ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2023, and in 2) Lang, Natalie, et al. "Compressed private aggregation for scalable and robust federated learning over massive networks." arXiv preprint arXiv:2308.00540 (2023).‏
- The setting of both works 1) and 2) is the conventional FL with FO optimization, rather than the less adopted FFT and ZO, respectively.
- Moreover, as reflect from Algorithm 1 and lines 46-47; FFT does not change the implementation and associated challenges of regular FL, having the latter not-restricted to models of a certain size.

questions:
1. In lines 85-87: "However, we show that the per-step uplink and downlink communication overhead can be further reduced to 1 bit per step regardless of model size with little performance loss but numerous surprising benefits...". According to you Algorithm 1, only your uplink communication is being compressed. Additionally, in "numerous surprising benefits" the use of "numerous" may be too exaggerating. 
2. In lines 187-188: "However, to the best of our knowledge, efforts toward communication efficiency, data heterogeneity, and Byzantine resilience on FL are separated, motivating this work.". How does you method supports data heterogeneity?
3. In line 227: "...perturb its model in the same direction." What do you mean by that?
4. In line: "FeedSign left the sampling of random seeds to the PS...". Is this left of sampling is unique to FeedSign or can also be implemented in ZO-FedSGD?
5. What is 'D' in eq. (16)?
6. In lines 315-318: "...the only means of damaging convergence of FFT due to the binary voting scheme in FeedSign is to always send a reversed sign to PS." Does sending a constant sign (regardless of the true value) is also a possibility?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732590992844

thread_type:
official_comment

<thread_object>
creator: area_chair_b5dx

<content>
title:
Response

comment:
Dear Reviewers,

The authors have provided their rebuttal to your questions/comments. It will be very helpful if you can take a look at their responses and provide any further comments/updated review, if you have not already done so.

Thanks!
</content>
</thread_object>

</thread>
<thread>
creation date:
1733126852329

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Rebuttal Summary (part 1)

comment:
We would like to thank the AC and PCs for handling our paper and the reviewers for their expertise, effort, and time in reviewing our submission. They have helped us a lot in optimizing our work. Since the discussion phase is closing, we summarize our claimed contributions and the rebuttal as follows.

**Claimed contributions.**

- We proposed FeedSign, a federated finetuning framework. It features a zeroth-order optimizer, splits the gradient estimation into 1) direction, and 2) projection, and asks the client to communicate only the sign of the gradient projection. Since 1) can be easily reconstructed in a remote device with a shared PRNG, the sign can be regarded as a vague update that uses up only 1 bit per step per client, independent of model size. Meanwhile, the vague updates boost the system with
  
  - data heterogeneity resilience,
    
  - and Byzantine attack resilience.
    
  
  The convergence of the FL system with the sign-only transmission scheme is theoretically characterized and empirically verified. FeedSign shares low memory and computation requirements since employing ZO optimizers while the per-step communication load is further reduced. We also discussed some underexplored but valuable features that can be found in similar seed-projection designs.
  

**Acknowledged strengths.**

- **Strong experiment settings.** Strong baselines are considered, and the results cover a wide range of models and tasks. `rc27` `WF4n`
  
- **Convergence analysis.** This work features a theoretical analysis supported by comprehensive empirical results. `Qg9z` `G6oG`
  
- **Clean reference to pioneering works.** The references to prior works are easy to follow. `Qg9z`
  
- **Comprehensive discussion section.** `Qg9z`
  
- **Possible practical use.** `rcZ7`
</content>
</thread_object>

</thread>


Metareview:
metareview:
The authors propose a federated fine-tuning approach that just use 1-bit per client to update the model parameters each iteration. The 1-bit update is a carefully-chosen step-size towards a random direction. The size of the step is dependent on the gradient-to-that-random-direction (obtained via function evaluations). 

It is a good idea, since such 1-bit updates are pretty good estimators (as well-studied in sketching and 1 bit compressed sensing etc.).

However the novelty beyond this point seems limited as pointed out by all the reviewers. Note that, given signSGD and follow-up papers, robustness/byzantine resilience is not that surprising as the authors claim. In fact, the paper contained a wrong-claim about unbiasedness.

Based on the reviews and discussions, I recommend rejection at this stage.