Converge Faster, Talk Less: Hessian-Informed Federated Zeroth-Order Optimization
Authors: Zhe Li
Bicheng Ying
Zidong Liu
Chaosheng Dong
Haibo Yang
Venue: ICLR 2026 Poster (2026)
Keywords: Zeroth-Order Optimization
Federated Learning
Hessian
LLM Fine-tuning
Communication Efficiency
Primary area: optimization

Abstract: Zeroth-order (ZO) optimization enables dimension-free communication in federated learning (FL), making it attractive for fine-tuning of large language models (LLMs) due to significant communication savings. However, existing ZO-FL methods largely overlook curvature information, despite its well-established benefits for convergence acceleration. To address this, we propose **HiSo**, a Hessian-informed ZO federated optimization method that accelerates convergence by leveraging global diagonal Hessian approximations, while strictly preserving scalar-only communication **without transmitting any second-order information**. Theoretically, for non-convex functions, we show that HiSo can achieve an accelerated convergence rate that is independent of the Lipschitz constant $L$ and model dimension $d$ under some Hessian approximation assumptions, offering a plausible explanation for the observed phenomenon of ZO convergence being much faster than its worst-case $O(d)$-bound. Empirically, across diverse LLM fine-tuning benchmarks, HiSo delivers a 1$\sim$5× speedup in communication rounds over existing state-of-the-art ZO-FL baselines. This superior convergence not only cuts communication costs but also provides strong empirical evidence that Hessian information acts as an effective accelerator in federated ZO optimization settings.

Published as a conference paper at ICLR 2026
CONVERGE FASTER, TALK LESS: HESSIAN-INFORMED FEDERATED ZEROTH-ORDER OPTIMIZATION
Zhe Li', Bicheng Ying", Zidong Liu", Chaosheng Dong', Haibo Yang' 1 Rochester Institute of Technology, Rochester, NY 14623, USA
2 Google, Los Angeles, CA 90034, USA
@ComboCurve Inc., Houston, TX 77005, USA
4 "Amazon.com com, Seattle, WA 98109, USA
edu, ybc&google com, z. 2.Liufcombeurree.cm chaosde amazon. com, hbyciserit.edu
ABSTRACT
Zeroth-order (ZO) optimization enables dimension-free communication in feder- ated learning (FL), making it attractive for fine-tuning of large language models (LLMs) due significant communication savings. However, existing ZO-FL meth- ods largely overlook curvature information, despite its well-established benefits for convergence acceleration. To address this, we propose HiSo.
-iffrmeed ZO federated optimization method that accelerates convergence by leveraging global diagonal Hessian approximations, while strictly preserving sealar-only com- munication without transmitting any second-order information. Theoretically, for non-convex functions, we show that HiSo can achieve an accelerated convergence rate that is independent of the Lipschitz constant L and model dimension d under some Hessian approximation assumptions, offering a plausible explanation for the observed phenomenon of ZO convergence being much faster than its worst-case (dd) ((dundd.... Empirically, across diverse LLM fine-tuning benchmarks, HiSo deliv- 1~55x speedup in communication rounds over existing sate-offtheearr ZO-FI baselines. This superior convergence not only cuts communication costs but also provides strong empirical evidence that Hessian information acts an effective accelerator in federated ZO optimization settings.
INTRODUCTION
The explosive development of large language models (LLMs)) has sparked strong interest in making their fine-tuning scalable across distributed and privacy-sensitive data sources (Naveed al. 2023
Zhao et al. 2023). As a promising and effective paradigm, federated fine-tuning has been successfully applied to enable collaborative model training while preserving data privacy in a large amount of
works (Kairouz et al.) 2021 Cho et al., 2024 Li et al. 2025a Zhang et al. 2025). Yet, modern LLMs massive parameter scale (e.g., several billions) introduces severe scalability barrier: due to communicating high-dimensional model updates, communication cost has become a primary bottleneck for federated LLM fine-tuning (Wu
2025 Jia et al., (2025). For instance, fine-tuning OPT-1.3B model by FedAvg (McMahan et al. [2017] usually requires about ~ TB communication cost for one client (Li et al. 2025b). To overcome this burden, recent work has proposed using zeroth- order (ZO) optimization (Nesterov & Spokoiny 2017) to enable dimension-fre free communication in FL. In particular. DeComFL (Li al. 2025b) encodes both uplink and downlink communication using shared random seeds and scalar-only updates, achieving communication cost independent of model dimension. Specifically, reduces the total communication cost from TB level to MB level. This dimension-fres communication framework is especially attractive for federated LLM fine-tuning, where communication is a dominant bottleneck.
However, the practical effectiveness of ZO-based FL is limited by its seriously slow convergence (Fang et al.) 2022 Li et al. 2025b). A key factor is that LLMs often exhibit heterogeneous and anisotropic curvature across their parameter space (Kingma & Ba 2015 Yao al., [02 Benzing 2022), making it difficult for vanilla ZO-SGD to adaptively scale updates. While prior work has shown that second-order information (e.g., Hessians their diagonal approximations) can significantly

---

Published as a conference paper at ICLR 2026
accelerate convergence (Kingma & Ba 2013; Ye et al. 2018 Jiang et al. 2024 Zhao al. 2025
estimating Hessian approximation and applying such and even more pronounced in dimension-fin -ree communication frameworks, where transmitting any Hessian-related information reintroduces expensive costs that scale with model size linearly or quadratically, directly contradicting the goal of scalar-only communication. This tension leads to our key research question:
techniques in FL are non trivial
Q: Can we accelerate federated zeroth-order fine-tuning while preserving dimension-free communication?
To answer this question, we first propose a generalized scalar-only communication FL framework that decouples scalar-only communication from its tight connection with vanilla ZO-SGD, enabling the integration of Hessian-informed optimizatior Within this framework, we are equipped to introduce HiSo, an efficient FL. algorithm via Hessian-informmn 7O optimization and Scalar-only communica- tion. Specifically. it captures curvature information through diagonal Hessian approximation without increasing Hessian-related communication cost. HiSo maintains the scalar-only communication and significantly improves convergence via Hessian-informeet preconditioning. Our theoretical and empirical results and contributions can primarily be summarized as follows:
We propose a flexible FL framework with scalar-only communication in both uplink and downlink, which supports broader class of optimization algorithms beyond vanilla ZO-SGD.
Under this framework, we propose HiSo, a fast federated ZO optimization method via Hessian- informed zeroth-order optimization and Scalar-only communication. It utilizes global Hessian information to speed up convergence while preserving scalar-only communication (without the need to communicate Hessian-related information).
Theoretically, we propose novel condition to get tight estimation of the variance of Hessian- informed ZO gradient under the low-effective rank and whitening assumptions. With this treatment, we prove that HiSo can achieve a convergence rate independent of model dimension and function smoothness in non-convex settings, marking the first such result for 7O methods in FL. In addition, our analysis generalizes the state-of-the-an DeComFL framework and, importantly, extends the theoretical guarantees multiple local updates key component of practical federated learning that DeComFL does not support in its convergence analysis.
Empirically, HiSo achieves up to 5x faster convergence than DeComFL, while delivering higher test accuracy than all ZO baselines across all tasks. Compared first-order baselines, up to 90 million times communication savings can be gained.
2 RELATED WORK
Adaptive Gradient Methods & Hessian-Informed Zeroth-Order (ZO) Optimization. To accel- erate first-order FL, adaptive FL algorithms (c.g., FedAdam, FedYogi, FedAdagrad (Reddi et al. 202T)) have been introduced to address the slow convergence in heterogeneous environments, By adaptively adjusting learning rates applying momentum techniques, these methods significantly outperform vanilla FedAvg in terms of convergence speed and final accuracy. Parallel this line, recent ZO advances have shown its effectiveness in gradient-free learning, especially when gradients are unavailable or expensive to compute. To further enhance convergence speed and stability, several studies Ye et al.) 2018 Zhang et al.) 2022 Chen et al. 2024 Zhao et al. 2025 Kim et al.) 2025) proposed Hessian- fressian-informed ZO methods that incorporate second second-order information, such as diagonal Hessian approximations, as preconditioning to improve the quality of gradient estimation and reduce variance, which shows the acceleration single-node settings.
Communication-En Efficient Federated Learning & Scalar-Only Communication. Communication efficiency is a critical challenge in FL primarily due to the frequent transmission of high-dimensional model updates between clients and the server (Kairouz et al. 2021 Jia al.) 2025). Numerous
methods have been proposed to reduce communication overhead in FL. including parameter-efficient
methods, such as Low-Rank Adaptation (LoRA) (Sun al. 2024 Guo et al. 2025) to transmit
'The term "Hessian-informed" does not imply that we calculate the full Hessian matrix; rather, the update approximates the Hessian preconditioning direction, as will explain detail later.
2

---

Published as a conference paper at ICLR 2026
only low-rank trainable matrix representing model updates, and compression techniques used to reduce the size transmitted data (Yng et al. 2021 Wang et al. 2022 Hönig et al. 2022 Su et al.)
2024 Li al. 2024 Zakerinia et al, (024). Moreover, Zo optimization has also been introduced to the FL. context (Fang et al. 2022] Qin et al. 2024 Liang et al. 2025). FedZO (Fang et al. 2022) integrates ZO-SGD into FI., but its communication heavily relies the model dimension. DeC DoComFL.
(Li et al.) 2025b) pioneeringly exploited the intrinsic properties of ZO gradients specifically, their decomposition into gradient scalars and perturbation vectors determined by random seeds to achieve dimension-fre free communication overhead in LLM fine-tuning. Yet, it suffers from slower convergence due to the nature of ZO-SGD.
A GENERALIZED SCALAR-ONLY COMMUNICATION IN FL FRAMEWORK
In this section, we will present generalized FL framework with scalar-only communication. Before that, we make brief review about the zeroth-order method and its application for the dimension-free communication in FL. which will be the key pillars for the following algorithm design.
3.1 HEROTH-ORDER SGD AND SCALAR REPRESENTATION
We focus on the randomized gradient estimator (RGE) for performing ZO gradient estimation in this paper. is also commonly referred to as Simultancous Perturbation Stochastic Approximation (SPSA) (Spall) 1992] Nesterov & Spokoiny 2017). Given scalar-valued loss function f(x) where x E R the forward-style RGE is
seed
9.1
{イ(=)= (f(x + (m)-f(())) u N(O, Ta),
(I)
where u represents a random direction vector sampled from standard Gaussian distribution and μ > 0 is small constant, Figure 1: An illustration of ZO update. commonly termed the smoothing parameter, controlling the perturbation step size.
An intriguing attribute of RGE is its efficient representation using only two scalars. First, we introduce a gradient scalar g = ( (x + pm) - f(x) IR, which serves as a scaling constant capturing the directional derivative. can also be explained as an approximate value for the directional gradient. Second, due to the deterministic nature of pseudo-randon number generators, the random direction vector Rd can be uniquely determined by random seed Hence, f can be efficiently expressed by two scalars. Crucially, this compact representation significantly enhances the efficiency of model updates in ZO frameworks. To illustrate, consider ZO-SGD update rule shown in Fig.
" (f(x + pun) ff f(xn) un En 1gnui P
Fo Σ Mr
FR+1 ER
This implies that, given the initial point zg. a few number of gradient scalars {gr and random seeds {s,} are sufficient reconstruct æR. irrespective of the dimensionality of z. This representation will play a crucial role in the dimension-free communication FI. algorithm that follows.
3.2 FEDERATED LEARNING WITH DIMENSION-FReD FFRE COMMUNICATION
We consider FL scenario with M clients, each owning local loss function ft. The goal is to collaboratively minimize the global loss function across all clients without sharing their private data:
min f( min #ER
Σ f((x), where fı(z) E [F: E.)
ZER" M
typical FL round consists two communications: 1) Downlink Communication: The server broadcasts the current aggregated global model to subset of clients; 2) Uplink Communication: The selected clients return their locally updated model to the server. Both can an expansive communication operation when the number of parameters d is large.
3

---

Published as a conference paper at ICLR 2026
The core idea of dimension-fiee communication in FL is leveraging the scalar representation of ZO-SGD to avoid transmitting the full models. To illustrate that, consider the following global model
(1) update rule with the notation that Ir,r denotes client i's model at the r-th round and 7-th local update step and 2y denotes the r-th global model:
Ir+1 Cr,
Σ -
Σ (,) CI C+ iEC.
ΣΣ
Fr.k uy
(4)
iEC.
iEC,
where C, is the set of sampled clients in the r-th round, Ur are generated by shared random seeds across all clients, ensuring that all clients move along consistent directions. enables that the global aggregation step in the server is simply computing average of the gradient scalars:
9r.k C, Eiec, Ir.h from the local gradient scalar gr,k: (f. + pul,,x) - f((()))))
Uplink Communication: From Eq. sampled clients only
Clann
transmit local gradient scalars Dy.k the server for global aggregation. Downlink Communication:: ZO scalar rep- resentation only captures relative updates, so crucial to ensure that the server and all clients start from the same starting point. To achieve this, a model-reset mechanism is introduced: after finishing their local updates in each round, each participants resets its local model to the initial model, which is the global server model by induction. With this reset mechanism, the downlink communication can be conceptual- ized similarly to Eq. (4) with the distinction that clients may be absent in multiple rounds.
Clann
Seed deaction
Seed direction
Seed directionn
Onc-round update with 2 clients and 3 local updates. They share the same direction for each local update with different lengths. Arrive 2++1 both clients requires steps: 3 local updates, reset and 3 updates with global values.
Figure 2:
Unlike the standard FL algorithm, reconstructing instead of pulling the model is used for catching the current server model through global gradient scalars and random seeds from preceding missed rounds. Consequently, the server is required to maintain auxiliary information: the client's last participation round, historical random seeds, and the global gradient scalars. This constitutes negligible extra memory requirement as these are merely a few scalar values. We demonstrate the process in Fig. 2
3.3 GENERALIZED SCALAR-ONIY COMMUNICATION IN FEDERATED LEARNING
In the work by Li et al. (2025b), the inherent dependency ZO-SGD limits its applicability and the full potential of its dimension- free communication framework. One of our key contributions is observing that the crucial element is not the specific choice of ZO-SGD, but the basic of scalar representations. Specifically, by maintaining records of their respective states with the update constructed by these scalar representations, the server and clients can effectively accommodate wider range of optimization algorithms within the dimension- free communication paradigm. Thus, in Algorithm [ we present a more generalized formulation that allows for the integration of various optimization techniques.
In Algorithm| communication is structured as follows: clients transmit (A for global aggregation, and the server distributes the aggregated update Ar, to clients for model reconstruction. The comeension-indppendeee and the server-side aggregated update Az, can be effectively represented by sealars. Note a persistent state may be required to reconstruct Ary with F: the last participated round.
(1) K
the server
property is preserved if both client-side updates Ar(1) r.
HESSIAN-INFORMED SCALAR-ONLY COMMUNICATION IN FL (HISO)
(i) 4.1 FIND A BETTER ASCENT AT. AZT DIRECTION
We use the proposed generalized framework to design a novel method superior to ZO-SGD-basee FL while retaining dimension-free communication. core challenge in the preceding framework is to
4

---

Published as a conference paper at ICLR 2026
( identify effective ascent direction Ary that is constructible solely from scalar values and current state information. While ZO-SGD meets these requirements, superior alternative can be found.
Recall that the ZO methods' slow convergence is due to its dependency on random search directions (Ma & Huang 2025). More specifically, recall the Eq. (1) with (O, I), which uniformly searches all directions the Rd space, is the update direction regardless of the scalar g. A natural extension is that can guide the search direction with an invertible matrix H,. Suppose H, is given, the Line 11 in Algo.
T can be formulated as the following sub-optimization problem
min fa
AZ
(Ascent Direction)
(5)
3ER
s.t. AzF
1/ ur dr ~ (O, E _
(Scalars Representation)
(6)
will be clear later why we use this strange H/2 notation instead of H, directly. Solving the above least-squares problem, have
g" = (uT,& ux " 1/2
Note (1" is a scalar that is independent of iterates x x Hence, we can absorb it into the learning rate. Next, note that uTt, H, f Hence, we obtain the following update rule
(f + HH, 1/2 (x,x)))) -((xx))))))))) O(s).
(Ja + 1H, 1/2 u,, [( H 1/11/urrkk
(8)
r.
Now should be clear why we use the notation H, 1/2 after we take the expectation of Az
EA (8) r.l R H,- uu,,,, H, H, 1/2 f.
V
When H, is a well-approximated Hessian matrix, the ex expectation of gradient descent follows the
Newton-style gradient descent (Boyd Vandenberghe 2004). The first-order counterpart An (i) is
called natural gradient since it can be viewed as pre-condationed gradient (Amari 1998). Recalling
the linear transformation property of Gaussian Distribution, the update Eq. 8 can be more concisely written the following form
Az (f( + (2r,x) - f.(2))))2n. 2r, ~ (0,,
(10)
This formulation also aligns with recent work by Ye et al. (2018) and Zhao et al. (025), which refers to this type of update as Infirmeed Hessian-Awen Zeroth Order Optimization.
4.2 LEARNING GLOBAL CURVATURE WITHOUT EXTRA COMMUNICATION COST
follow-up question for the above formulation is how to find this H, matrix. One plausible approach is, again, utilizing the zeroth-order gradient estimators approximate directional second derivatives
F(x + vu) + F(x pm) 2F(x) u ~ (a)
u T R3
(11)
2n²2
However, this approach has two limitations: 1) this requires an additional function evaluation per direction and extra communications: forming the full d x d Hessian is both costly and unnecessary. Instead, we only seek diagonal preconditioner, akin to Adam's 's per-coordinate scaling (Kingma & Ba 2015 Recall the global update term Az,, approximates the value of the gradient and can be constructed by scalars only discussed before. Further, notice this value is needed for the reconstruction step. Hence, we have a free variable to approximate the diagonal Hessian through following proposed rule. We only update the Hessian at the beginning of one communication round with 7-local update steps followed by the exponential moving averaging:
H = Hrr =(1 - H) +
Σ Dir +el) LES.
*More accurately, our method resembles RMSProp as it currently is without a momentum term. Momentum could be incorporated without additional communication costs using the same technique presented in this section. Given the existing length of this paper, we will not elaborate this momentum extension here.
5

---

Published as a conference paper at ICLR 2026
Algorithm I Generalized Scalar-only Communication in Federated Learning
1: Initialize: learning
local update steps communication rounds R.
Allocate: memory for recording the necessary historical states client's participation information.
3: for 0,..- R do
4: Server uniformly samples a client set C, and distributes the shared random seeds {8r).
5: for cach client E C, in parallel do
6: Receive the necessary scalar representations of (Arr') from server.
Reconstruct the (Arp) from the scalars and update state.
(. Zrg - E Azp
Equivalent pull model
9:
for k 0,-.. , 1 do
10:
Find Ar, that 1) is ascent direction; 2) can be represented by scalars state; F,,6+1 2 n end for
p Client local update
12:
13:
(6) J... = 7,,0 reset the model and other necessary states.
14:
Send the necessary scalar representations of (Am()) } to
Equivalent to push model
15:
end for
16:
Aggregate the scalar representations of (A into the ones for the global Az,
17: end for
1 Σ
H -11 + m EES
Diag((Az,,0l + cf),
(12)
where is a small number to make sure that Hr+1 is strictly positive definite.
This Adam-style method, similar to its first-order counterpart (Reddi et al.) [021]. has two advantages: 1) the diagonal matrix approximation avoids the d2 storage for the Hessian matrix, making the proposed method scalable with the large-scale model. 2) the vector A can be represented by scalars, so the server and clients can reconstruct this global Hessian without any extra communication.
4.3 PUTTING TOGETHER ESTABLISH THE DESIGN OF HISO
HiSo is established by substituting the previously determined ascent direction and the global Hessian learning method into the scalar-only communication framework. A illustration of HiSo is shown in To elucidate the basic HiSo with brevity, write out simplified update occurs per round (r 1). The following equation is for one round update of one client.
Fig. 3
where one local
for 1 = T1, T 1
Art = 9t H 1/2 ut, u = (seed:)
(Reconstruct States for the Missing Rounds)
(6) (1)
#11 J1 nAr
H4I = (1 b)H + DDiaa ((Ar]) +cl)
Aa (0) 1
[f(( + -HH, 1/2
fe(z) 1/1, -1H, (r)
F41 = 3 - AAr( (
(1)
CClient Local Update)
2 + Zr (reset)
(6)
Ax,
Σ
gr
H 1/2
GGooal Aggregation at Server)
C
C,
FEC.
where ri is the last participated round, (x(6) i-th client's model communication round and we omit the for local-update while is the global/server model. The same notation conventions apply gr. (f(() and Ar,,. Though mathematically equivalent, this representation is presented by disregarding implementation and communication intricacies to highlight the core mechanics better. Nevertheless, it is essential to highlight that only of Gr and random seeds required to be
for gr (4)

---

Published as a conference paper at ICLR 2026
communicated between clients and server as scalar-only framework proposes. For the detailed algorithm table with all features, we provide it in the Appendix D
Mistoriaal Seeds and Grad Scalans
8y,8
fr.k
ABR
(o.1)
Sryk=1
_r,2=1
reev
...
Servar
send
Ganssian
{+
Perturb
Z0O
{s}
Hessian Approv.
Update
Reset at the end
Reconstruct
Chiert
Figure Illustration of HiSo
PERFORMANCE ANALYSIS
HESSIAN, VARIANCE OF ZO GRADIENT, AND LOW EFFECTIVE RANK ASSUMPTION
To lay the foundation for analyzing HiSo, we first examine basic component of ZO: the estimation of the variance term. It provides essential insights into Hessian-informen ZO methods.
E | == E Eu, u ~ N(, Ia) E R
(13)
where E is some semi-positive Hessian matrice The standard L-smoothness assumption implies that || | < L. Consequently, the preceding quantity can be upper-bounded as:
[uul | ||/||2 < Ld,
(14)
Note that the upper bound derived above can be quite large if the dimension is large. This dependence on dimensionality is a well-known factor leading to typically slow convergence rate of ZO methods (Nesterov 2013). Fortunately, this bound only represents worst-case scenario. Motivated by empirical observations that the Hessian of trained large language models (LLMs) possesses relatively few eigenvalues significantly far from zero (Papyan [020 Yao et al. [020 Wu al. 2020). Malladi et al. (2023) proposed a low-effective rank assumption. This spectral property, concentrated near zero, is illustrated in Fig. 4 (left). To utilize this
where most cigenvalues assumption, we need to treat the variance more carefully:
E [|wl[ Tr(EE un ) = (T/EL))= := Lxs,
(15)
where ạ. = Tr(E/L) is called the effective rank of Hessian E. It computationally prohibitive to find the exact value of but several previous workers indicate к d (Li et al. [2025b] Malladi et al. 2023). Hence, we get a tighter variance estimation. Utilizing the Hessian approximate matrix, we can further improve this bound. Supposing we have a well approximation matrix H for the Hessian Σ, the weighted Gaussian vector 2 is sampled from the distribution A(0, H H-1). Then, we have
EE || E Tr(H
um )
11(22- -1/2)
(16)
where we call the quantity Ç as the low whitening rank of Hessian E.
H is the perfect approximation of Σ, then ( d. This case is neither possible in practice nor ideal in LLM cases. Recalling that only a few eigenvalues of E are non-zero, then H R Diag(E el) is a more effective inverse value, which is similar Wiener filtering in the denoising field (Sayed) 2003). Now we summarize the above discussion into the following definition.
Assumption
E E|
EE
[||2
L-smooth Low Effective Rank
Ld
2d
Lx
S
Table 1: The Upper-Bounde of 70 Gradient Variance
For a non-convex function, Hessian may contain some negative eigenvalues. One possible choice of Σ can he the absolute eigenvalues of the Hessian.
7

---

Published as a conference paper at ICLR 2026
150
Ld 120, 000
15
{ 100
Count
Lk 3, 400
100
10
50
5
0
200
400
600
0.5
1.0
Eigenvalue of
Eigenvalue of -H
Figure 4: An Illustration of the Eigenvalue Distribution.
Definition. We call a diagonal matrix as a well-approximate matrix of Hessian E if the whitening matrix =: -- satisfies the following condition:
Tr(=)) = TT = (2d (L-Smoothness)
(17)
is (Low Effective Rank)
where is a quantity independent of the dimension and the factor is just a safety factor to tolerate the imperfect inverse. The above assumptions and results are summarized in Table
To illustrate the effectiveness of this whitening process, we execute simple numerical experiment. To simulate the distribution of Hessian cigenvalues, we assume that there are 200 eigenvalues following the log-normal distribution, i.e., log(E)) . (V(0,37) (7). The simulation, depicted Fig. 4 shows that < La < Ld. This lays the theoretical foundation for the acceleration of our proposed HiSo.
5.2 CONVERGENCE RESULTS
We first present some standard assumptions that will be used to establish the convergence results. Assumption 1 (L-Lipschitz). Suppose the global loss function L-smooth, i.e. all z, Rd. we have |/ F(x) - VF(y)) S L||z yll-
Assumption (Unbiased Stochastic Gradients with Bounded Variance). The stochastic gra- dient computed by clients is unbiased with bounded variance: [. = fx(x) and [[; { f=()))] S o Va, where represents a data sample.
Assumption 3 (Bounded Heterogeneity). The cost function satisfies |/ fi(z) FF(z)] S ag, Va.
Assumption 4 (Bounded Learned Hessian). The learned Hessian has 0 < 3: S H S Bu, Vr.
The last assumption is common in Adam-style algorithms (Kingma & Ba, 2015 Reddi et 2021)) where the requirement of bounded gradient implies this assumption directly. It is worth noting that, unlike the assumption on Hessian, the parameters 3r and 3, can be easily controlled in the algorithm design by adding the clipping step
(Maritan et al. 2024 Zhao et al. 2025) or
(Liu et al. 2024). This assumption also implies 3-1 < 11 1 33
Theorem 1. Under Assumptions 1
2
3 and 4 in S min
1
M(d+2) and denote
mL Sp 4(7-1)
A1. = F(z,) - F*, the sequence of teerates generated by HiSo satisfies:
4A 32n(T L
16np
E [ P
(oé of) +
(oā + + + O(1)), Bem
R
Berm
k=0
extra client drift
(Tr(H, 1/2 ",, H, 1/2) + 2 H, 1/2 H,, 1/2 Er, is PSD matrix that upper-bounds Hessian at Tr,k and Φ = 1/2 E, (Tr(H, H1
where Er = 1
I p D
Roughly, p can be understood as the sum of whitening Hessian cigenvalues and as the sum of approximate Hessian eigenvalues. f consist of two parts: 1) Tr TT(H,1/223 H,, is the quantity discussed previously, 2) 1/2 "/,,, 1/21 typically, much smaller than the first term when the model dimension is large. The properties of the terms in & are similar to p.
Corollary 1 (Convergence Rate for HiSo). Suppose the learned global Hessian H, satisfies the well-approximated condition (17.. When and 7) /m3:/ pf, HiSo's convergence rate is
8

---

Published as a conference paper at ICLR 2026
d//d/RR). Further, if the Hessian exhibits the low-effective rank property, the rate can be further improved to O( ((C/mR) independent of the model dimension and the Lipschitz constant L. Corollary 2 (Convergence Rate for DeComFL.) Note that DeComFL. (Li et al., 2025b) can be regarded special case of HiSo with Ii, = I, Vr and 3r B. = 1. Therefore, we can immediately recover the convergence rate of DeComFL with assumptions Ol (KLLx/mlt with the extra low-effective rank phenomenon.
is Of Ld/mR) with standard
Corollary (Convergence Rate for > case). When the local update step T > the difference between HiSo and DeComFL becomes bigger. Under the -ell-approximate and low whitening rank scenario, the convergence rate of HiSo is O(VC/TmR) + O (( D(VTk//mR) still independent of the model dimension and Lipschitz condition Iı meanwhile, DeComFL. becomes dependent on again. This resolved the previous open question that DeComFL (Li ct al.) (025b) cannot provide the convergence rate with a low-effective rank assumption when т > See Appendix F.6.2 for details.
Remarks about vell-approximated condition. It is important to note that Theorem does not require the well-approximated condition. This condition is only necessary for the three preceding corollaries, which utilize it to establish clean convergence rates. Although it is hard to determine this approximation holds in the context of LLMs,, the assumption offers plausible explanation for the rapid convergence often observed in practice (where the required iterations are much smaller than d). If H, fails yield an effective Hessian approximation, the performance of HiSo, worst case, degenerates into DeComFL. We provide more discussion on this point in Appendix F.7.1
EXPERIMENTS
The Global Diagonal Hessian Approximation H. We begin by training simple CNN model on MNIST (LeCun et al. 1998) visualize the learned diagonal Hessian approximation H. We set up 64-client FL environment where data was partitioned non-Ill) using a Dirichlet distribution (a = Each communication round involved randomly sampling 8 clients for training. Evaluating the Hessian smoothing parameter // revealed negligible impact on convergence and final accuracy (Fig. [5] left), demonstrating the algorithm's 's robustness this hyperparameter, Furthermore, Fig. (right) plots each entry of the learned diagonal Hessian values at the end of training. While individual entries may appear stochastic, their overall distribution clearly exhibits long-tail phenomenon. This observation aligns with the low effective rank assumption discussed in Sec. 5.1 Although computing exact Hessian computationally prohibitive, the rapid convergence combined with this observed distribution suggests strategy effectively approximates relevant Hessian structure. We design more experiments and provide more direct evidences in Appendix F7..2
10
Test Accuracy
0.9
Valuo Loamedd H
v-
0.38
DeComFL
HISo v=0
0.7
HiSo
0.6
0
500
1000
1500
2000
2500
500c
10000
15000
20000
25000
5000
Communication Round
Count
Figure 5: Ablation study of smoothing parameter // and the distribution of the learned global Hessian H.
HiSo is Faster Than DeComFL in Small Model Training Tasks. Fig. 5] we evaluate HiSo against another dimension-free communication Fl. method DeComFI.. Crucially, the communication cost per round are the same for both to ensure fair comparison of al algorithmic efficiency. Fig. Fisoss that, under the same communication constraints, our HiSo achieves significantly faster convergence and reaches a superior final performance level compared to DeComFL. For this comparison, both tuned using their optimal learning rates. More comparison is provided in Appendix
LLM Fine-Tuning Task Setup: Our FL system consists of 6 clients in total, and 2 clients are uniformly sampled in each round. To comprehensively evaluate HiSo's performance, execute sentiment classification on SST-2 (Socher et al., (013). question matching on QQP, and question answering SQuAD (Rajpurkar al. 2016). We set P for all Z0 methods.

---

Published as a conference paper at ICLR 2026
HiSo Accelerates Training with Less Communication Cost in LLM Fine-Tuning, In Table 2 HiSo consistently reduces communication rounds required to reach DeComFL's best test accuracy, resulting in lower communication cost. Specifically, HiSo achieves 1.4-5.4x speedup with 29%-80% communication savings across all tasks. These results show that Hiso accelerates convergence and reduces communication cost, making it more practical for large-scale FL. scenarios involving LLMss.
Table 2: HiSo's Acceleration. For DeComFL, we report the total number of communication rounds required to fully converge. For HiSo, we report the number of rounds needed to match DeComFL's best test accuracy. along with the corresponding communication cost.
Model
Method
SST-2
QQP
SQuAD
Round
Speedup
Comm. Cost
Round
Speedup
Comm. Cost
Round
Speedup
Comm. Cost
OPT:350M
DcComFL
550
1x
21.56 KB 10.78 KB
775
1x
30.35 KB 16.64 KB
1350
1x
52.73 KB 9.77 KB
Hi5o
275
1.8x
5.4x
OPT-1.3B
DeComFL
1500
1x
58,59 KB
1125
1x
43.95 KB
350
1x
13.67 KB
Hiso
1075
14x
750
1.5x
2x
6.84
OPT-2.7B
DeComFF.
1250
1x
41.58 KB
1475
1x
48.75 Kn
450
1x
15.65 KB
Ni5o
775
1.6x
KB
1.5x
32.11
2.3x
6.94
Extensive Baseline Comparison on LLM Fine-Tuning Tasks. In Table 3 first-order methods
(e.g., FedAvg, FedAdam, Fed and FedAdagrad) consistently achieve high test accuracy, but at the cost of TB-level communication volumes, which is quite challenging for real-world federated fine-tuning. As for ZO baselines, FedZO's 's communication cost is also quite high due to transmitting d-dimensional update. Although DeComFL achieves several orders of magnitude communication reduction, its cost is still higher than HiSo it suffers from more rounds due to extremely slow convergence, Our proposed HiSo not only maintains the lowest communication cost in almost all tasks (only a little higher than DeComFL on OPT-L.3B+QQP) but also consistently outperforms ZO baselines in test accuracy.
Table 3: Performance for LLM Fine- TininTuning. 1) We report the total communication cost of the single client during the entire training process until convergence, test accuracy for SST-2 and QQP, Fl score for SQuAD.
Model
Method
SST-2
QQP
SQuAD
FedAvg
87.63% 0.16 (0.15 TB)
61.21% 0.37 (0.08 TB)
37.27 = 0.11 (0.05 TB)
FedAdam
88.29% 0.47 (0.30 TB)
63.18% 0.31 (0.06 TB)
37.98 + 0.20 (0.03 TB)
FodYogi
88.06%
0.33 (0.29 TB)
62.88% 0.21 (0.05 TB)
37.66 (0.04 TB)
OPT-125M
FedAdagrad
85.04% 1.551 (0.18 TB)
61.77% 1.2.2 (0.06 TB)
37.29 (0.04 TB)
FedZO
84.19% 0.22 (0.63 TB)
60.06% + (1.94 TR)
34.03 (0.14 TB)
DeComFL
85.21%
0.27 (22.92 KB)
0.11 KB)
0.21 (17.42 KB)
HiSo (Ours)
85.55% + 0.21 (14.69 KB)
60.72% 0.25 (21.23 KB)
0.14 KB)
FedAvg
89.79% + 0.05 (0.58 TB)
63.32% 0.13 (0.31 TB)
(0. TB)
FedAdam
89.92% 0.20 (0.21 TB)
63.28% 0.19 (0.28 TB)
45.92 (0.08 TB)
FedYogi
89.68% + 0.29 (0.25 TB)
63.21% 0.16 (0.28 TB)
45.01 0.25 (0.09 TB)
OPT-350M
FedAdagrad
87.42% 0.09 (0.23 TB)
62.55% 0.14 TB)
4.11 (0.09 TB)
Fed70
86.55% + 0.23 (0.68 TB)
61.22% + 0.30 (0.66 TB)
38.14 (0.38 TB)
DeComFL
86.72% = 0.28 (21.56 KB)
60.58 + 0.16 (30.35 KB)
38.20 0.15 (5.753 KB)
HiSo (Ours)
87.50% 1 0.22 (17.33 KB)
62.49% 1 0.17 (18.63 KB)
39.13 0.11 (20.51 KB)
FedAvg
90.48% + 0.35 (0.63 TB)
65.77% 0.20 (0.32 TB)
60.39 + 0.27 (0.41 (B)
FedAdam
92.86% + 0.43 (0.79 TB)
64.59% 0.53 (1.10 TB)
6.14 (0.4 TB)
FedYogi
92.39% 1 0.58 (0.83 TB)
64.44% 0.22 (1.12 TB)
61.44 0.19 (0:29 TB)
OPT-1.3B
FedAdagrad
90.92%
0.74 (0.88 TB)
64.05% 0.13 TB)
60.72 - 0.23 (0.33 TB)
FedZO
90.01%
0.29 (4.73 TB)
62.91% 03.4 TB)
57.26 0.17 (1.10
DeComFL
90.22%
0.10 (58.59 KB)
63.25% 0.11 (43.95 KB)
57.14 0.14 (13.67 KB)
HiSo (Ours)
90.34% 1 0.12 (49.18 KB)
64.20% 1 0.13 (96.67 KB)
$7.58 0.07 (7.81 KB)
In Appendix E we present additional experimental results, along with comparisons and analyses of memory cost, communication cost, computation time, and other FL+PEFT baselines.
ACKNOWLEDGMENT
This work is supported in part by RIT CHAI Faculty Seed Grant, NIH award R16GM159671 and NSF grant CNS-21 12471. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural Computation, 10(2)251-276.
1998.
Frederik Benzing. Gradient descent neurons and its link approximate second-order optimization. In International Conference on Machine Learning, pp. 18 1817-1853, PMLR, 2022.
Stephen P Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge university press, 2004.
Ran Chen, Yuzhe Li, and Tianyou Chai. Multi-objective derivative-free optimization based on hessian-aware gaussian smoothing method. In 2024 IEEE 18th International Conference Control Automaaion (ICCA), pp. 210-215. IEEE, 2024.
Yae Jee Cho, Luyang Liu, Zheng Xu, Aldi Fahrezi, and Gauri Joshi. Heterogeneous lora for federated fine-tuning of on-device foundation models. In Proceedings of the 2024 Conference on Empirical Methods Natural Language Processing, pp.
2024.
Wenzhi Fang, Ziyi Yu, Yuning Jiang, Yuanming Shi, Colin N Jones, and Yong Zhou. Communication- efficient stochastic zeroth-order optimization for federated learning. IEEE Transactions on Signal Processing, 70:5058-500 5573, 2022.
Haozhe Feng, Tianyu Pang, Chao Du, Wei Chen, Shuicheng Yan, and Min Lin. Baffle: baseline of backpropagation-free federated learning. In European Conference on Computer Vision, pp. 89-109. Springer, 2024.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):3341 1-2668, 2013.
Pengxin Guo, Shuang Zeng, Yanran Wang, Huijie Fan, Feifei Wang, and Liangqiong Qu Selec- tive aggregation for low-rank adaptation in federated learning. In The Thirteenth International Conference on Learning Representations, 2025.
Robert Hönig, Yiren Zhao, and Robert Mullins. Dadaquant: Doubly quantization for communication-efficcenn federated learning. In International Conference on Machine Learning, pp. 8852 8866. PMLR, 2022.
Edward Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Ninghui Jia, Zhihao Qu, Baoliu Ye, Yanyan Wang, Shihong Hu, and Song Guo. A comprehen- sive survey on communication-effiiee federated learning in mobile edge environments. IEEE Communications Surveys & Tutorials, 2025.
Ruichen Jiang, Ali Kavis, Qiujiang Jin, Sujay Sanghavi, and Aryan Mokhtari. Adaptive and optimal second-order optimistic methods for minimax optimization. Advances in Neural Information Processing Systems, 37:941 30-94162, 2024.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-210, 2021.
Bumsu Kim, Daniel McKenzie, Hanqin Cai, and Wotao Yin. Curvature-aware derivative-free optimization. Journal of Scientific Computing, 103(2):43, 2025.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFF, 86(1) (6(11):2278-3244 1998.
11

---

Published as a conference paper at ICLR 2026
Shiwei Li, Wenchao Xu, Haozhao Wang, Xing Tang, Yining Qi, Shijie Xu, weihongluo, Yuhua Li, xiuqiang He, and Ruixuan Li. FedBAT: Communication binarization. In Forty-first International Conference on Machine Learning, 2024.
federated learning via learnable
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Reprexentations, 2020.
Zhe Li, Seyedsina Nabavirazavi, Bicheng Ying, Sitharama Iyengar, and Haibo Yang. Fast: A lightweight mechanism unleashing arbitrary client participation in federated learning. In Proceed- ings of International Joint Conference on Artificial Intelligence, pp. 1144-5652, 2025a.
Zhe Li, Bicheng Ying, Zidong Liu, Chaosheng Dong, and Haibo Yang. Achieving dimension-fie free communication in federated learning via zeroth-order optimization. The Thirteenth International Conference Learning Representations, 2025b.
Dandan Liang, Jianing Zhang, Evan Chen, Zhe Li, Rui Li, and Haibo Yang. Towards straggler- resilient split federated learning: An unbalanced update approach. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
Hong Liu, Zhiyuan Li, David Leo Wright Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. In The Twelfth International Conference on Learning Representations, 2024.
Shaocong Ma and Heng Huang. Revisiting zeroth-order optimization: Minimum-variance two-point estimators and directionally aligned perturbations. In The Thirteenth International Conference Learning Representations, 2025.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038-53075, 2023.
Alessio Maritan, Subhrakanti Dey, and Luca Schenato. Fedzen: Quadratic convergence in zeroth- order federated learning via incremental hessian estimation. In 2024 European Control Conference (ECC), pp. 2320-2327. IEEE, 2024.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--fficeee learning of deep networks from decentralized data. Artificial Intelli- gence and Statistics, pp. 1273 1273-1282. PMLR, 2017.
Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saeed Anwar, Muhammad Usman, Naveed Akhtar, Nick Barnes, and Ajmal Mian. A comprehensive overview of large language models. arXiv preprint arXiv:2307.06433 2023.
Yurii Nesterov, Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566. 2017.
Vardan Papyan. Traces of class/cross-class structure pervade deep learning spectra. Journal of Machine Learning Research, 21(252):1-64, 2020.
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. In International Conference on Machine Learning, pp. 41473 41497. PMLR, 2024.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint /606.05600005520 2016.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2021.
Ali H. Sayed. Fundamentals of adaptive filtering. John Wiley & Sons, 2003.
12

---

Published as a conference paper at ICLR 2026
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference Empirical Methods in Natural Language Processing, pp- 1631-1642, 2013.
James C Spall. Multivariate stochastic approximation using simultaneous perturbation gradient approximation. JEEE Transactions on Automatic Control, 37(3):332-341, 1992.
Xiaoxin Su, Yipeng Zhou, Laizhong Cui, John CS Lui, and Jiangchuan Liu. Fed-evie: Compressing federated learning communications with variable-length codes. In IEEE INFOCOM 2024-IEEE Conference on Computer Communications, pp. 601-610. IEEE, 2024.
Youbang Sun, Zitao Li, Yaliang Li, and Bolin Ding, Improving loRA in privacy-preserving federated learning. The Twelfth International Conference on Learning Representations,
2024.. 2024.
Gemma Team. Gemma 3. 2025a. URL http:::/aaax....rrraa/////-0--1
Qwen Team. Qwen3 technical report, 2025b.
Yujia Wang, Lu Lin, and Jinghui Chen. Communication--eficicttt adaptive federated learning. In International Conference on Machine Learning, pp. 22802-22838. PMIR, 2022.
Yebo Wu, Chunlin Tian, Jingguang Li, He Sun, Kahou Tam, Li Li, and Chengzhong Xu. A survey on federated fine-tuning of large language models. arXiv preprint arXiv:2503. /2016, 2025.
Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, and Rong Ge. Dissecting hessian: Understanding common structure of hessian in neural networks. arXiv preprint arXiv:2010.04261, 2020.
Haibo Yang, Jia Liu, and Elizabeth S Bentley. Cfedavg: achieving efficient communication and fast convergence in non-iid federated learning. In 2021 19th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), pp. 1-8. IEEE, 2021.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE International Conference Big Data (Big data), pp. 581-590. IEFE, 2020.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney. Adahessian: An adaptive second order optimizer for machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10665-10673, 2021.
Haishan Ye, Zhichao Huang, Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian-aware zeroth- order optimization for black-box adversarial attack. arXiv preprint 1rXiv:1812.11377, 2018.
Bicheng Ying, Zhe Li, and Haibo Yang. Exact and linear convergence for federated learning under arbitrary client participation is attainable. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
Hossein Zakerinia, Shayan Talaei, Giorgi Nadiradze, and Dan Alistarh. Communication effficient federated learning with data and client heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 4448-3456. PMLR, 2024.
Bokang Zhang, Hong Guan, Hong kyu Lee, Ruixuan Liu, Jia Zou, and Li Xiong. Fedsgt: Exact federated unlearning via sequential group-based training, 2025. URL htttps://arxiv..r
abs/ 2bbs/551 251 1 23393
Hualin Zhang, Huan Xiong, and Bin Gu. Zeroth-order negative curvature finding: Escaping saddle points without gradients. Advances in Neural Information Processing Systems, 35:38332-38344, 2022.
Jiawei Zhao, Zhenyu Zhang. Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: Memory-efficiee Ilm training by gradient low-rank projection. In International Conference Machine Learning, pp. 61121-61143, PMLR, 2024.
13

---

Published as a conference paper at ICLR 2026
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. survey of large language models. arXiv preprint arXiv:2303./8223, 1(2), 2023.
Yanjun Zhao, Sizhe Dang, Haishan Ye, Guang Dai. Yi Qian, and Ivor Tsang. Second-order fine-tuning without pain for LLMs: A hessian informed zeroth-order optimizer. In The Thirteenth International Conference on Learning Representations, 2025.
14

---

Published as a conference paper at ICLR 2026
APPENDIX
A Statement of LLM Usage
16
B Conclusion and Limitations
16
Comparison of Related Works
16
Detailed HiSo Algorithm Table
16
Extra Analysis, Discussion, Experiment Detail and Results
18
Baseline Selection)
18
Memory Cost Results
19
Communication Cost and Training Acceleration Results
19
Time Cost Results
20
E.4.1
Computation Time Cost Results
20
E.4.2
Wall-Clock Time Cost
20
HiSo v.s. FL+PEFT Baselines
21
E,6
Training Loss Iterations/aall-Coog Time
21
Scenarios Suitable for HiSo
21
Main Proof
22
Notations
22
F2
Algorithm Reformulation and Main Recursion
23
Key Lemmas
24
E331
Lemmas about Gaussian Variables
................................
24
E33.2
Variance Lemma for Sampling Noise
25
4
Descent Lemma
26
F5
Consensus Lemma
28
F.6
Convergence Analysis Theorem
29
F66.1
Convergence Proof of Theorem
29
F66.2
Convergence Rate
30
F7
More Well-approximation of Hessian Matrix Analysis and Experiments
31
E7.1
Theoretical Analysis When Well-approximation Does not Hold
31
E72
Estimate the impact of meaningful Hessian Approximation
E7.3
Hessian Approximation Evaluation in Random Subspaces
31
G
Multi-Porturbation Version
32
Performance Analysis
33
G.2
Convergence Rate
34
15

---

Published as a conference paper at ICLR 2026
A STATEMENT OF LLM USAGE
LLM tools were used to help with language refinement and stylistic improvements. After each use of the tool, we carefully reviewed and validated the correctness and appropriateness of the generated text to ensure accuracy and alignment with the intended meaning.
B CONCLUSION AND LIMITATIONS
In conclusion, we first present generalized FL framework that supports scalar-only communication in both uplink and downlink, enabling the integration of a broader class of optimization algorithms be- yond vanilla ZO-SGD. Building this foundation, we propose HiSo, Hessian- -nffommed federated optimization algorithm that leverages diagonal Hessian approximations to accelerate convergence while preserving scalar-only communication efficiency without the demand to transmit any second- order information. From theoretical perspective, we introduce a novel variance characterization for Hessian-informed zeroth-order gradients under a low-effective-rank assumption. This allows us to establish a convergence rate that is independent of both model dimensionality and function smoothness in non-convex settings result not previously achieved by any ZO method in FL. Our analysis further generalizes the previous framework and extends its theoretical guarantees to support multiple local updates, critical component in practical FL deployments. The analysis offers plausible explanation for the observed phenomenon of 7O convergence being much faster than its worst case. Empirically, HiSo consistently outperforms existing baselines, delivering higher test accuracy, to about 5 faster convergence, and substantially lower communication overhead. These results demonstrate the practical viability and theoretical soundness of unifying curvature- -nnerreed optimization with scalar-only communication in federated fine-tuning.
The proposed method is currently limited by its treatment of the loss function fi as a generic one, without considering model-specific module structures. This is in contrast to modern parameter-efficient fine-tuning (PEFT) methods that often exploit properties like low-rank decomposition (e.g.. W AB where A E & and B E R and < k1, It is important to note that this explicit low-rank decomposition is distinct from the 'low effective rank' of the Hessian discussed in this paper. Consequently, there is potential to further refine approach by designing Hessian information specifically tailored for PEFT methods such as LoRA (Hu et al. 2022) GaLore (Zhao et al.) 2024).
Limitations:
C COMPARISON OF RELATED WORKS
observe that HiSo achieves the best convergence rate among all ZO-FL related works (e.g., FedZO, BAFFLE, DeComFL) and is the first work to provide the rigorous convergence proof under the low effective rank assumption and supporting the case at the same time. Compared with first-order related works, HiSo achieves significant communication improvement.
From Table 4
D DETAILED HISO ALGORITHM TABLE
Although the algorithm listed in the main context is quite complicated, it is simple if we ignore the dimension- free communication property. Mathematically, Hiso is equivalent to the following standard FedAvg style update
27.00 Fr
(6)
(Receive Model)
for 1: 0, 1, ..... ,,, -
1
(fi(x + +uHl, 1/2,11)
(1(
97.6 11
7, = Fr
-n H,, H.11/2
1/2
(Local Update)
3r+1 =
(9)
(Aggregate Model)
Cr
IEC,
H,4 =(1 H) #aih++DDiagllae DDiag((ar- xr| [x++1 x,] el)
With that reference, we present the full algorithm table for Hiso.
16

---

Published as a conference paper at ICLR 2026
Algorithm 2 Concrete Scalar Representations Communication with States for Federated Learning
1: Initialize: learning rate local update steps K, communication rounds R
2: Allocate: memory for recording the necessary historical states, including historical gradient scalars (g).
corresponding random seeds {s} clients' participation round {r'}. which are initialized as
3:
4: for 0, 1... R do
5: Server uniformly samples client set C, with cardinality m. Server randomly samples random seed set {Sr,k)k= and broadcasts sampled clients. each client E C. in parallel do
H{ Jk=0 (r-1))
Rebuild( (1 ( Fe (o (1
5,00 =2 - E 1
KD
10:
( = (ocalUpdatee (.,+)
11:
Send ig 1ro back to the server.
12:
end for
/T ccl
gr.k
Global gradient scalar aggregation
iEC,
14:
(Arr, 1==]
gri H. ur
Global A aggregation
15:
Store (grck I==0 and (Sr I== and update the client's 's last participation round r
Ir+1 = Jr A
(Optional) Global model update
17:
end for
Algorithm 2a Receiving Step for Hessian-Informed 70 Gradient for i-th Client at r-th Round
1: Function Rebuild( (tt | (1
is last participation round
do do 4: Utilize the random seed St, to produce ue,k N(O.I)
2: for t = -r,
3: for k= 0, ...
5:
Azy,k Hr u H₂+1 = (1 - H2 + Diag((AAs, +cl)
6:
7:
end for
8:
end for
9:
return ((ATY,k )
For model reconstruction
Algorithm 2b Sending Step for Inessien-Informed ZO Gradient for i-th Client at r-th Round
1: Function Local sy 1z=)):
2: for 1: = 0...................... .
do
3: Utilize the random seed 8,,8 produce ur ~ 10,
4:
0 = [1(= / + μH, 1/2 (r,k) (x(111))
Compute ZO gradient scalar
5:
Ax(1) -r. H,, 1/2 Wr.k
(6)
Can be replaced by other representation methods of Ar(()
Fr Ax (0)
(3)
6:
Fr.4+1
Update local model
7:
end for
8:
Reset the local model and update other necessary states
9: return (g
1-11
17

---

Published as a conference paper at ICLR 2026
Table 4: Comparison of Related Work. is the model dimension. m the number of sampled clients round. P is the number of perturbations. R is the number of rounds. is the low whitening rank of Hessian.
the low effective rank of the Hessian. "LER" means the low effective rank assumption. "DF" mean dimension-free. "Proof on > 1?" means whether the algorithm provides theoretical convergence proof under multiple local updates 7 1.
Methods
Convergence Rate
LER?
Uplink
Downlink
Proof on 7
FedAvg McMahan
2017
(v miter
XDF
X
FodAdam Reddi et al.
2021
x
X DF
DDF
/
mik
FedZ0 Fang al.
2022
Ld
X
Ld V
BAFFLE Feng al.
2024
mPRR
/ DF
DDF
/
DeComFL Li al.
2025b
o (v mPR
Le
/ DF
v DF
X
HiSo (This paper)
V mP Re
DF
DF
Client loss
possible gradient Expectation of 20 gradient
Directional Gradient Informed
Directional Gradient with Hessian Informed
Trajectory Hessian-informed
Trajectory without Hessian-Informed
Client 2 local loss
possible gradient Expectation of 20 gradient
Figure 6: An Illustration of Hessian-informed versus Regular ZO Gradient Direction under the FL Setting.
E EXTRA ANALYSIS, DISCUSSION, EXPERIMENT DETAIL AND RESULTS
E. BASELINE SELECTION
To comprehensively evaluate HiSo's performance, we select a broad range of classic or recent baselines covering both first-order and peroth-order FL methods. We explain the reason why we choose those baselines as follows:
First-Order FL Baselines:
FedAvg: the first and most classic first-order FL algorithm.
FedAdam, Yogi and FedAdagrad: adaptive gradient-based methods designed to accel- erate convergence in FL.
Zeroth-Order Baselines:
FedZO: the first FL method to incorporate ZO-SGD into client local updates.
DeComFL: the first method to achieve dimension-free communication in FL, which also uses 70-SGD to perform client local updates.
18

---

Published as a conference paper at ICLR 2026
E.2 MEMORY COST RESULTS
In HiSo, there are several places that require additional memory to store extra information. We test their real memory consumption in our FL system.
(a) Global Gradient Scalar and Seed {or 8,} Pairs: In each communication round, only one (gr, 5r) pair is stored at the server, regardless the number of clients. Specifically, storing two scalars per round over one million rounds would require only few megabytes that is well within the capacity of any modern server.
(b) Clients' Historical States (Last Participation Round): The server needs to store the last participation round (a scalar) for each client, which only consume a few megabytes for FL. system with even millions of clients. Specifically, storing million client states (i.e., 1 million scalars in int 32) only needs 3.8 MB. Moreover, this storage cost can be optimized. For example, the server can transmit the last participation round index to each client, and the client can store it locally as a scalar. When the client returns, it simply sends this scalar back to server. This design eliminates the need for server store all clients' states, so memory cost becomes negligible.
(c) Clients' Hessian H: We evaluate the peak memory usage single client across all baselines and our proposed HiSo. The results indicate that HiSo requires substantially less peak memory than all first-order baselines. Moreover, HiSo also outperforms FedZO in terms of memory efficiency, as in the original FedZO paper, it is not optimized for memory usage. Finally, when comparing HiSo with the memory-optimized DeComFL, we observe that HiSo still consumes less than twice the peak memory of DeComFL.
E.3 COMMUNICATION COST AND TRAINING ACCELERATION RESULTS
HiSo is Extremely Communication-EFFii Efficient. Fig. 7 shows the total communication cost of various FL methods across different model sizes (125M, 350M, and 1.3B), highlighting the dramatic efficiency of our HiSo. While traditional methods like FedAvg, FedZO, and FedAdam incur communication costs on the order of 10 10 HiSo reduces by over 40 million times for 125M and 350M models, and up 90 million times for the 1.3B model. Even compared to the strongest communication effficient baseline DeComFL, Hiso still achieves noticeably lower communication cost because accelerated convergence introduces less training rounds. This substantial reduction and particularly well-suited for large-scale FL
shows that Hiso is highly communication-effin with nigh-capacity models. More experiment details provided in Appendix
Reskpp
39000000X
43000000X
Communication cost.
Ra20
1D"
RedAdam
Rulfay
DeComFL
307
HiSD
30*
202
CPT-125M
OPT--500
OFT-3.30
Figure 7: Communication Overhead Comparison for LLM Fine- Tuning on SST-2 Dataset
In 5 show the additional experiment results about HiSo's acceleration including Qwen3-0.6B (Team, (0255) and Gemma-3-270M (Tea 2025a). For DeComFL, we report the number of rounds required to fully converge. For HiSo, we report the rounds required to match DeComFL's best accuracy, together with the corresponding communication cost. Across all settings, HiSo consistently requires far fewer communication rounds while maintaining the same accuracy target. For the Qwen3-0.6B model, HiSo reduces the communication rounds from 2500 to 950 on SST-2 (a 2.6x speedup), from 1050 to 650 on QQP (a 1.6x speedup), and from 375 to 225 on SQuAD (a 1.7x speedup). This round reduction directly translates into lower communication cost. The acceleration is equally pronounced on the lighter Gemma-3-270X model. HiSo achieves 2. 2.1% speedup on SST-2, 1.4x on QQP, and 2 on SQuAD, again halving the communication cost compared to DeComFL. Overall, these results demonstrate that HiSo substantially accelerates zeroth-order FL, achieving 1.4x-2.6x faster convergence while preserving the extremely low communication footprint. This validates the key insight of HiSo: leveraging Hossian-informed ZO updates dramatically improves convergence efficiency while maintaining scalar-only communication.
LLMs,
19

---

Published as a conference paper at ICLR 2026
Table 5: HiSo's Acceleration. For DeComFl., we report the total number of communication rounds required to fully converge. For HiSo. we report the number of rounds needed to match DeComFL's best test accuracy, along with the corresponding communication cost.
Model
Method
SST-2
QQP
SQUAD
Speedup
Speedup
Speedup
Qwen3-0.6B
DeComFI
2500
1x
83.16 KB
1050
1x
34,93 KB
375
1x
12:47 KB
HiSo
1000
2.5x
33.26 KB
650
1.6%
21.62 KB
225
1.7x
7.48 KH
Gemma-3 3-270M
DeComFI.
1x
1x
29.94
HiSo
1025
211x
34.05 KB
625
1.4%
20.79 KB
450
2X
14,97 KB
E,4
TIME COST RESULTS
E.4.1 COMPUTATION TIME COST RESULTS
We profiled the actual computation time per round for feessian-informet preconditioning (Tpre). along with the total computation time and estimated communication time on H100 GPUs. These results presented in the following Table Our profiling shows that the computation time for Hessian- informed preconditioning is negligible compared to both the overall computation and communication time. This confirms that HiSo remains scalable LLMs. This efficiency is expected, as the core operations involved in our preconditioning step consist of matrix squaring and matrix summation, both of which are computationally lightweight and do not scale prohibitively with model size.
In addition, the communication time heavily depends on the network condition and the number of transmitted scalars. To offer a comprehensive understanding, we provide an estimated communication time follows: considering two types of common bandwidth: 100 Mbps (e.g., wifi or 5G) and I Gbps (e.g., enterprise LAN / wired campus network). If we run HiSo with perturbations, it is reasonable to estimate that there are total 10 scalars to be transmitted in uplink and downlink per round. For transmitting 10 float32 scalars (approximately 1 KB including protocol overhead), the pure transmission time is about 0.08 ms under 100 Mbps, and 0.008 under Ghps bandwidth. Including typical round-trip network latency, the total communication time per round is approximately 20-30 ms in 100 Mbps environments and 1-2 ms in Gbps settings. This confirms that Hiso's per-round preconditioning time (<0.5 ms in our experiments) is negligible compared to communication time.
Table 6: Comparison of Computation Time for Informed Preconditioning with Different LLM Sizes (Using SST-2). Te the preconditioning time per round. Tostat the total time per round.
Test is the estimated communication time per round.
Model Size
T Tpre
Trotal
Tpre// Ttotat
T
OPT-125M
0.118 ms
88.4 ms
0.13%
I~330 ms
OPT-350M
0.137 ms
127.2 ms
0.11%
1~30 ms
OPT-1.3B
0.185 ms
329.3 ms
0.06%
1~33 ms
OPT-2.7B
0.259 ms
438.6 ms
0.06%
1~:30 ms
E.4.2 WALL-CLOCK TIME COST
In Table 7 we report the one-round computation time, one-round communication time and total wall-clock time until convergence of first-order baselines, ZO baseline and our HiSo. We observe that first-order FedAvg and FedAdam suffer from extremely high wall-clock time due to their high-dimensional communication overhead that each round requires 228.8 seconds, significantly dominating the overall runtime. Thus, despite their low per-round computation time, they require 68788 and 45858 total wall-clock time respectively.
In contrast, zeroth-order DeComFL. significantly reduce communication to only 2.24 x 10-6 seconds round, achieving 29x faster overall runtime than FedAdam. However, DeComFL. still requires many more communication rounds to reach the target accuracy, compared to other three methods. Further, our HiSo achieves the best overall efficiency. Although the per-round computation time is slightly higher due to DeComFL. Hence, HiSo achieves total wall-clock time of only 1064 seconds, representing a 43x speedup over FedAdam, 64x speedup over FedAvg, and a 2.2x improvement over DeComFL. This shows that HiSo not only preserves the ultra-low communication cost of scalar-only communication
updates, HiSo converges in far fewer rounds compared to
20

---

Published as a conference paper at ICLR 2026
but also substantially accelerates convergence (i.e., less training rounds) through its Hessian-informel optimization design.
Table 7:
Wall-Clock Time Cost Comparison (Qwen3-0.6B Model+SST-2 Dataset). We assume typical 5G network setting with 100 Mhps uplink and 500 Mhps downlink bandwidth without considering latency, protocol and so on. We tested this on HI00 GPUs.
Method
One-round Computation Time
Onc-round Communication Time
Total Wall-Clock Time
FedAvg
0.43 s
228.8
68788
FedAdam
0.49
228. 128.8%.
45858
DeComFL
0.94
2.24 x 10-6
2350
HiSo
1
2.24 X 10 6
1064 s
E,5
HrSo V.S. FL+PEFT BASELINES
Although this paper focuses on full-parameter FL, which differs in setup and assumptions from PEFT-based approaches, to provide comprehensive evaluation, we include additional comparisons with FL+PEFT baselines. As shown in T HiSo achieves up 10 communication overhead reduction while maintaining competitive test accuracy. Among ZO methods, HiSo consistently demonstrates lower communication overhead, higher test accuracy, and faster convergence.
Table 8: Comparison of HiSo and FL+PEFT Basclines. We report the communication cost of one client.
Model
Dataset
Methods
Test Acc.
Comm. Cost
FodAve+LoRA (r=8)
87.47%
0.34 GB
FedSA-LoRA Guo et al.
2025
(r=8)
87.53%
0.15 GB
FFA-LoRA (Sun et 2024
(r=8)
87.39%
0.16 GB
OPT-125M
SST-2
DeComFL+LORA (Li 2025b
(r=8)
85.23%
27.55 KB
Hiso+LoRA (Ours)
(F=8)
85.37%
22.26 KB
HiSo (Ours)
85.55%
14.69 KB
E.6 TRAINING LOss VS ITERATIONS/WALL-CCOOO TIME
Based on the convergence curves in Figure 8 HiSo consistently demonstrates substantially faster progress than DeComFL. in both iterations and wall-clock time. On SST-2 with Qwen-3-0.6B, DeComFL. requires roughly 2500 iterations to converge, while HiSo reaches the same accuracy within only about 1000 iterations, achieving 2.5x speedup in optimization rounds. This faster iteration- level convergence directly translates into end-to-end efficiency: when measuring real execution time, including communication and computation, HiSo is about 2.1x faster than DeComFL in reaching the same final accuracy. The accuracy-time time and loss-time curves further confirm that Hi maintains a steeper descent trajectory throughout training, reducing both the number of updates and the total runtime needed for convergence. Overall, these results show that HiSo accelerates federated fine-tuning in both algorithmic efficiency (iterations) and practical efficiency (wall-clock time), providing significantly faster convergence under the same hardware and network conditions.
F.7 SCENARIOS SUITABLE FOR HISO
HiSo is not designed as a drop-in solution for any FL scenario. Its core characteristics, Zero-Order (70) nature and extreme communication efficiency, make the best fit for these critical scenarios:
Gradient Inaccessibility. When true gradients are inaccessible or prohibitively expensive to compute, zeroth-order (ZO) optimization serves as a natural and effective alternative. In such black-box settings, where only function evaluations available, ZO methods enable optimization without explicit gradient information, thereby extending applicability to a broad range of tasks where gradient-based based approaches infeasible. As ZO-FL method, HiSo is particularly well-suited to this scenario.
Bandwidth- www.idddh-Costraineedd Networks. With a communication overhead limited to the kilo- byte (KB) range, HiSo is ideally suited for FL deployments in environments with limited bandwidth. This feature guarantees scalability and practicality even when fine- soeettunng massive models.
21

---

Published as a conference paper at ICLR 2026
Accur
Wallclock
4.40
872
0.20
Bartior
clrck (Cmsatted)
Secorn coneerarce
DiCzee' Jake
Latte
betre covaraans gar
ma007 36-
Starrey LAn
Wel. Eecrrett
Figure 8: Training Loss Iteration and Training Loss Wall-Clock Time. (Qwen3-0.6k + SST-2)
F
MAIN PROOF
F.1 NOTATIONS
The following proof utilizes matrix and vector notations. A bold symbol, such as æk, generally represents a vector encompassing multiple clients, whereas normal symbol, such as 2g the value for an individual client. To further lighten the notation for multiple clients and the local cost function, we adopt the following usage:
(6) denotes
C3 =
Fk
(1)
I
(2)
1x E
[Mn]
Rdxa
(18)
f(xx) = f1 (1
fe( (2) :
(2 E RIXM
(19)
Vf(xx) = ( cl))
(M (M), ( <(0) E Rx
(20)
where V (1 (())) represent the stochastic gradient evaluated local function the
point z Notice the function value fi the gradient V. applied on the different iterates xx above notations. Various vector and matrix norms are used the proof. For any semi-positive definite matrix Σ, we adopt the following convention in Table 9
(i)
Table 9: Norm Notations in This Paper
Notation
Definition
Comment
|
x Ex Tr(ATEA)
Mahalanobis (weighted) vector where R"
|
Mahalanobis (weighted) matrix A Idddd
| l2. |||]]
Fmax(A)
Spectrum norm, i.c., largest singular value of A
||
Tr(xTx)
Frobenius norm (note is matrix here)
Remark:
While the Frobenius norm be viewed as special case of the weighted matrix norm, confusion is unlikely in this paper as we only apply the Frobenius norm to the stacked vector æ. Other commonly used constants and symbols summarized in the following table.
22

---

To make a concise proof, we first re-write the algorithm into the vector-matrix form as introduced in the previous section. First, to make the convergence proof straightforward, we translate the two-level for-loop structure (outer round loop and inner local update loop) into single recursion structure. The k-th local update in r-th communication round equivalent the rt iterations. Then, inspired by the work (Li et al. 2020 Ying et al.) 2025), first we notice the Federated Learning algorithm is equivalent if we virtually send the server's s model to all clients but keep the aggregation step the same, equivalently reformulate the Published as a conference paper at ICLR 2026
Table 10: Notations in This Paper
Notation
Meaning
Index of clients
k
Index of iterations
Index of communication round and r [k/r]r
The number of local update steps
C
Indices set of clients sampled at r-th round Model parameter dimension
d
m, M
Number of sampled and total clients
J F
Local and global loss function A random vector drawing from the standard
2
and weighted Gaussian distributions
The all-one vector 1, 1 E Mx1 and the uniform vector I, = 1/M E Raxx are two common notations adopted in the rest of the proof. With these symbols, have the following identity
Vf(cl = VF(x) E 1dxx
(21)
F.2 ALGORITHM REFORMULATION AND MAIN RECURSION
ie.. only aggregate the clients' values in C,. Under this form, algorithm into this recursion
f(zz + HH 1/2 uu T) f(xx)
11 1/2 ug.
yk+1 =
(22)
P
1 YK++ WR.
(23)
where ws Yk E RddMM is the stacked vectors and Wi represents the communication matrix. Note the single subscript & is for the iteration, which is not the same in the double subscripts for local update step. The element W Ji represents the effective weight that client client at iteration If the iteration & * rT, Wt 1 local update step. If k rT, Wi becomes a column-stochastie matrix, each column
average matrix
representing the model average step. More concretely, having the same weights and the non-zero elements in each column the sampled clients in round For instance, suppose client {0, 1,3) sampled in the four clients case, the corresponding W₁ are
0
0
0
(24)
3
3 3
Back to the update rule 22
23 ,. the following proof for the general update rule of Hg- Hence,
just need focus on the property of H₃. instead of combining the update rule and revisit it later.
We further denote 24 H uk 2g ~ NO, H ') to simplify the update rule:
1/2
11
f(xx + 1== f(xx))
ykt1 =
(25)
Øk+1 W
(26)
23

---

Published as a conference paper at ICLR 2026
Because of the shared seeds and Hessians, 21 is variable that has no client index subscripts. Using directional gradient approximation
f(z + pz) = f() + pz Vf(2) + 2² 2 (L. V2 tz)dtt +
(27)
the update rule can be concisely written as
yk++ 2i 1 V f(x)) + Opm))
(28)
1 + WK.
(29)
To manage notational complexity and the handling of intricate coefficients, we adopt the O(un) notation. Since this paper concentrates on addressing client sampling and local updates in federated learning, the analysis of the zeroth-order approximation error intentionally simplified. This approach facilitates clearer understanding of the distinct error sources in the federated setting, without sacrificing proof rigor.
We define the (virtual) centralized iterates Iy := æz 1l and Un yı u.. The recursion of centralized iterates Σ == 2x 1l is
Ik+1 4k++1 1
(30)
22 1 wg O(um)
(31)
where we define we == Wa u- is straightforward to see that if * rT, wP = I, if rT, Wk is the random selection vector with each entry having m/M probability to be 1 /mm and 0 otherwise. Hence, we have the following two cases to handle with
k rt, Stk 11 (2)a)) O k= IT.
T 1 (ax) + (
Bk+1
(32)
where we denote
2y =x Wk:
(33)
M
(xx) -Vf((x)) =
fi(a E Rax
(34)
M
V (+x) V f
Σ (i(( R
(35)
ieC, Above two centralized recursions will be the main reference the following proof.
F.3
KEY LEMMAS
F LEMMAS ABOUT GAUSSIAN VARIABLES
The rest proof is built top of the following fundamental lemmas about the Gaussian distribution.
Lemma (Fourth-Order Moment of Gaussian Vector). Suppose that the random vector 2 ~ (o, A) where A is diagonal matrix. For any symmetric matrix W, have
Ezz W 2zzT = Tr(WA) A + 2AWA. If u I), i.e. drawing from standard Gaussian distribution, we have
(36)
Eun TeanT Tr(W) 2W..
(37)
Proof. Let the matrix V zz =2 T22T. For each element i j. We'. = 2B 2Bz 2/ w [i.j] = 2A,A, W(..),
V Vi = E 2,2,
(38)
where the second equality holds because the zero-mean property of z and 2 independent of each other. For the diagonal elements.
i
í
=E2?
Σ
2uz WF'
Σ E W/
K
24

---

Published as a conference paper at ICLR 2026
E W. BB
Σ Ag WWW 2W 2 [
(39)
where we utilize the fact that 20 3A Lastly, combining the above two results into a concise matrix notation, we establish
== Tr A + 2AWA
(40)
For the standard Gaussian distribution case, we just need to substitute A = 1 into equation 36
Lemma 2 (Gaussian Smoothed Function). We define smooth approximation of objective function as (*) that can be formulated as
f*(x)
f(x paye |wll dz = [Ef(( 14],
(41)
(2x)
where >> O is the smoothing parameter, and z is one n-dimensional standard Gaussian random vector. Then, we have
f(x + pm) - f(x) u
( -(=),= W (*),,, where ~ 1)
E
(42)
P Above equality implies the zo gradient is an unbiased estimate of the gradient of the smoothed function ft.
Proof. See the proof in (Ghadimi & Lan 2013 Nesterov & Spokoiny 2017
F.3.2 VARIANCE LEMMA FOR SAMPLING NOISE
Before we present the main proof, we first bound the variance of (**x)
Lemma 3. Suppose fo is L-smooth and the local cost functions satisfy the data heterogeneity assumption oz. For any semi-positive definite matrix E, the variance of the sampled gradient Vx(xx) satisfies:
EIVS (1) S211V 2 18 + +0?) +
2L2
|E
Ix I& 1
(43)
M
where is the number of sampled clients per round and M is the total number of clients.
Proof. For any semi-positive matrix E. we have
E { <2E VJ (Tx T) + 2E V - V (Tx 1)
(44)
where the inequality utilizes Jensen's 's inequality.
Next, noticing that the variance identity for any weighted distance || || satisfies
E E| 1
=E
| - E E= 2x) - E (E*])E& - ||E
|x 1 |R |3
(45)
Combining with the fact that E mm
v (Tx 11 = (F we establish
E ff
E EII -F(=)))F( IVF
(46)
The first term in the above equality can be further bounded through the data heterogeneity assumption that
E B
VF(
E
(V)((T))))- - VF(Tx) -FFG))))V((()) )
11
m
TEC. mM
1 (T
Σ [ + o
(47)
25

---

Published as a conference paper at ICLR 2026
where the second equality holds since the zero-mean property. Substituting the above results back to equation 44
we arrive
+ 2 1 + - + 2EE (fxx)) V
E V (2
2 v
|=)|( + - 2L |لح [ - و 1
(48)
where we applied the L Lipschitz condition and Jensen's inequality in the last step.
F.4 DESCENT LEMMA
Lemma 4. When yj S { Be } the virtual centralized iterales Ty of one round satisfy mL,: 5pk
(r+1)r
E (( SE F( ((
<EF(1
Σ
I + ((T
jmrT+1
4Tm2² (x+1)r
2L (++1)
+ 3.m
Σ
Pk(og + +,,+ +
Σ j=
1a,--2111
(49)
mM
j=r++1
where Tr(HH H, 1/2 + 2 2 E4 1/
Proof. Recall there are two random variables in the main recursion Eq. (32 one is the 70 random direction 2y and the other is the client sampling vector Wi.. First, taking the conditional expectation over Wg. we have
E Wy 1 = ã 1) 2/ Vf (xx) + (np))
(50)
for any iteration k. Then, taking conditional expectation over 2k. we have
E Eis+1 =ū, - T Vf + (npu
(51)
As a result of Assumption loss function satisfies
there is a semi-positive definite matrix Eyg I L. Ta such that the global
F(t) < Fly) + (VF())) v) + 10 y) TT 2).
(52)
Hence, we have
F(*x+1) S F(Tx) (V Tx+1 -mx) (Tx+1 II 3x)
(53)
Now, substituting Eq. 32 into the above expansion and taking the conditional expectation, we will establish the following two cases.
Local Update Iteration:
When the iteration & is not the communication iteration, i.c. k * rr. we have
((x+1)) <F(;)) - v/Vf((x VFF (V (n)2p)
+ "
2 Eu (fx)
(54)
First, we focus on the cross term
f((x)) H -VF(x))
= VF 1
[1) +
(V(())) -/ VF((2)
S (Tx((T))))))))))))))))))))) 2
| + IVF
1
Vf
2
2 IVF (|
|
VVF
(55)
Because of Assumption 4 we have 8,11 <
3, which implies
1 VF((x))
1
vf(x)))
- 23
[VF +((
2
M
Σ [f)(2z)) vf(aa(")11
<
23,N
26

---

Published as a conference paper at ICLR 2026
I,2
||0 - F2 12111
(56)
2
Substituting back, we have
11.22
(F(()))) SF(Ts)
| 17
1| "1- +
a - Fx 1
2
+ (f(
2
(++
(57)
Next, the key is this quadratic term. Leveraging Lemma 1 we establish
Q =E (ff())) TT( + 2Hz H vf
<(Tr(En + 2 / (z
(58)
where we utilize the following inequality in the last step
|e|| H H. = HH
1/2 2x
H 1/2 H 1/2 E3 H
1/2
H
1/2
H
1/2
||
For simplicity, introduce the matrix E H 1/2 noise variance result (48) we establish
11-1/22sh1 H
1/2 Plugging the previous sampling
(59) This Tr(Ex) + E || is the key quantity that we will encounter repeatedly. To further reduce the 2| E Combining all the above results, have
Q S (Tr(E,) + 2| E I2 (ZWW +
( + o
2
(o0
2L
xx 89 1H/
3.m
3.M
notation, denote PO: Tr(Ex)
E F( < (Tx))
"
2nj pt
[VF(
0(7
nL
2nj² Pk
2n Pk (o o.)) 3.m
| -
Fx 1
(60)
2,,
3.M
When S 1. the coefficients can be simplified into 4ps
EF(*++1) {F(Tx)
[[ H (17²21
!
nL2
ax - F4 T 11 + 2n pk
+
(oō + o²)
(61)
3.M
Bem
Communication Iteration:
When the iteration & is the communication iteration, i.e. k * rT, we have
E F(
<F())) 17 fx*))
VF-VV((a + =On2p)) p)
Σx a It MzZ (xxx) <FxT)) 1) v (Tx) H VV + (n)pp)
E (bx 3t .ル V
2E ( 3x) ΣΦ (i*
mx) 2n (xx))
[zx))] (62)
Next, we notice that
(áx xx) T Σg (.x x <L 1 12
x Fy 1 11
(63)
mM
Utilizing previously established result Eq. (60)
we have
E F( (F()
7 4n²
p
|[
H O(T2pp)
LL
2
4n Pk
+
+
Pk: | - FA1 1 +
(06 + +
(64)
23
3.M
Ben
When 7) S 1 the coefficients can be simplified into 8pc
EF(T++1) SF(Te)
IIF((E)) + 10(22))
L
?
41 Pk:
+
+
||
Ft 11
1
+
(06 + o.)
(65)
mM
B
p.m
27

---

Published as a conference paper at ICLR 2026
We further require the learning rate 77 mf establish
9.
E EF(#++1)
{*{) 1 |
2L
4n Pk
x
||
(oc o
(66)
mM
Brm
Combining Two into One Round:
Combining the above two results and iterating from = r (r+ 1)T, we establish
(r+1)r
E BF(2 SBF
7
Σ
|VF + 0(1²m)
4 j=
(r+1)r
ATnI pk
2L
(oc + 0 +
Σ
1 - o, 1|
(67)
Bpm
mM
j=rr+1
where absorb the coefficients the consensus term ||æ - F. 1 T1 into 2T/ mL/mM since above
we already require the learning rate 1j S mL. Also, we replace H₁ by H, since it is not updated within one communication round.
F.5 CONSENSUS LEMMA
Lemma 5. When 1j S 1[ V TTd+2 the sum of the consensus error of one round bounded by
the following term
1 (r+1)r
Σ
E E 2z I S (P(T-1)2MM33
| + 01722²)
(68)
where 4, +
Proof. The consensus residual is defined as
[b+11 x++1ll 1 1E
|| - 1 T 1724 2
+ (f(x)) - + (69)
If k all clients have the same value. Hence, expand the difference x4 -211" 1 up to
= rT and arrive at
| 14411111 1
- + +
j=r++1
<(r- Σ
(70)
j=r++1
where we utilize Jensen's inequality in the above step. Next, we focus on the term in the summation
|| Vz(z,) - 1. 1|
<4112y2, Vf - 2,3]Vf(2,1
2
<8|1= (f - - + + -
(71)
where we utilize the identity that V=(2,11)= = = +,,,,,,,,,, = +, H
" Recall that
(72)
where r is the corresponding round for the iteration j. Notice | < (d + 2) 3e, which is not tight bound though. Hence, taking the expectation with respect 2j, establish
E # Fetil 1
28

---

Published as a conference paper at ICLR 2026
&
<T - 1) Σ
[Vf(2;)
V
j=r++1
+ 22 - 1) Σ
H. 0
j=r++1
<81 11,,3,111111 1,
Σ
-
17- 11, (1)²²²)
j=7++
(73)
Lastly, we just need to take another summation over k from rT to (r + 1)7 - 2. Recall that
[pr+1 +r I| = 0. After rearranging and utilizing the fact that WkerT 2j Oj S
(++1)r Σ
(T 1) 1) (1+)) ag for any nonnegative value ag. we have
(r+1)r
10)333))
Σ
-
7 k=
(T
1 (1 + x1)²
(74)
After restricting to force 1 - 1
< 1/2, we establish this lemma.
O
special case local update step r = 1. In this case, we do not need any consensus error since the models are all synchronized. We can simply discard the term E || Fx 1 11? in the descent lemma.
F.6 CONVERGENCE ANALYSIS OF THEOREM
F.
CONVERGENCE PROOF OF THEOREM
Proof: We are now ready to present the convergence theorem, which simply combines the consensus lemma and the descent lemma above then taking the double exepection.
1r--)
E (f SE F[
1)1
7
Σ
E E|IVF(E,))l
((7pp) 0
4
J=P
(o' + o + 81 ( - 1)2L. (r+1)r-1
4Tm2 pk Bem
|0,11(00 + +z+)
(75)
jEPT
Expanding the summations and re-arranging terms, we obtain
4(F(E))- -F)
+ 16np (oā + oz) +
32n((T 1)
(0) + +
R
RT
Bem
3erm
+ O(p)),
(76)
where
K
1 K
1
Pk
(Tr(Ex) + 11)
(77)
K
k=
k=0
K
1
Σ
(Tr(H;
1/2 1/2 E/ H 1/2 + 2 H 1/2 1/25, H 1/21))
(78)
K
1
1 Σ R
(T(HH,
2
(79)
R
Combining all learning rate requirements, we have
31 1
B
1
min
(80)
mL' 8px
4(T
1) V L(d+2)
29

---

Published as a conference paper at ICLR 2026
Lastly, translating the above result back the two-level is and indexing, establish Theoreml
F.6.2 CONVERGENCE RATE
To establish the convergence rate, we distinguish two scenarios the local update and the local update
L. When I. the rate becomes much simpler
1
E (F 4(F(3))-F))
-F
16np Bem
(o) + o.) O(p)),
(81)
R
nR
When the communication round R sufficiently large and the 70 smoothing parameter ju is suffi- ciently small, choose the learning rate
V
mát all which leads the following rate:
R-
2
o
(82)
mR
Based on the Table we can establish the following four rates based on the conditions:
1. H, is well-approximated one with L-smoothness assumption, then the rate is O
V
mil
2. H, is well-approximated one with low effective rank, then the is O (Viss
mR
3. DeComFL Case: No Hessian information is learned, i.e., H& I, with L-smoothness
assumption, then the rate is
ml
4. DeComFL Case: No Hessian information is learned, i.e., H2 I, with low effective rank, then the rate is O (V
Lx mf
For the local update case, we choose the learning rate 17 min (V obtain the following rate
m&r Tplt
m3 Tell
Then
R-1
P
TO mR
BI H,
+
O
(83)
R
TIRR
k=
descentt residue
consensus residue
where the second extra term comes from the client model diverging in the local update steps.
Similarly, establish the four rates based the assumption. Here focus the low effective rank case since it reveals the difference between DeComFL. and HiSo.
When H, we have 5- + 2 and p S Ls.. Therefore, establish the following rate for DeComFL rate:
(V
Lx TmR
+
(84)
mR
Here we can see that even if can be tighter bounded by low-effective rank, the convergence rate still depends on d.
In contrast, if H, well-approximates the Hessian Σ with the low effective rank, we establish the convergence rate for HiSo is
(V
+ O
(V
Tk
(8:5)
TmR
mR
Now, if we compare Eq. (84) with Eq. 185 we can tell that HiSo is still capable of being independent of Lipschitz L and model dimension d; meanwhile, DeComFL cannot. This probably explains why the original paper (Li et al. 2025b) cannot provide the proof for the dimension-fir free rate with > 1. Of course, Eq. (84) is just an upper bound for the worst-case scenario. The practical performance may not be pessimistic as the bound indicates.
30

---

Published as a conference paper at ICLR 2026
F.7 MORE WELL-APPROXIMATTON OF HESSIAN MATRIX ANALYSIS AND EXPERIMENTS
F.7.1 THFORETICAL ANALYSIS WHEN APPLIAPPROXIAAAIOO DOES NOT HOLD
As mentioned in the main context, whether this approximation holds in the context of LLMs is difficult assess. To understand the impact of the approximation of the Hessian, we refer back the key quantity in Theorem 1.
P
TR ΣΣ (Tr(H, (Tr(H H, + 2| H,, 1/2
(86)
This is the dominant and distinguished term compared with other zeroth-order methods. Among these two terms in the double summation, Tr(H, 1/2 H, H, is usually much larger than | H, =,,,1 Hence, we can just focus on the former term only. Because both Σ,, and H, are positive semi-definite matrices, we know
d
Σ (xtErtt)AA((FF,, S
1/2) S
A j=1
(87)
where the notation )-(-) denotes the j-th eigenvalue of a matrix, ranked in descending order (from largest to smallest), and )-)()) represents the eigenvalues in ascending (reverse) order.
At the early stage H, R I, then Tr(H, 1/ Hr 1/) Tr(E,,)). equivalent to the no learning of Hessian. This can be thought as the baseline. Now, suppose we unfortunately learn a poor Hessian approximation that amplifies the largest eigenvalues of the Hessian while shrinking the smallest ones. this case, we will obtain larger Pr.k than Tr(Ei,,),, resulting in a worse outcome than the baseline that does not apply Hessian information. However, this case is unlikely to be stable, since H, will gradually improve its approximation of y,, to some degree. Most commonly, the value of Pr.k should lie between the bounds of equation 87 H, will not have the perfect same eigenspace as R. But as long as the largest few eigenvalues of Ex,k) are divided by correspondingly large values from H, the total sum should be smaller than Tr(E,,k)- This is highly probable due the long-tail distribution of the Hessian's 's eigenvalues.
Lastly, notice f has an O(1/R) decay rate, governing how quickly old values are forgotten. It is common for the estimation to be inaccurate at the beginning, but it eventually converges to a stable value. This O(1/R) rate matches the algorithm's 's convergence rate. Hence, as long as the Hessian approximation converges no slower than O R), any early, inaccurate estimates will not negatively impact the final rate.
F.7.2 ESTIMATE THE IMPACT OF MEANINGFUL HESSIAN APPROXIMATION
In Figure 5 we demonstrated that the final performance is relatively insensitive to the choice of provided that remains close to This is because high values of v ensure sufficient smoothing of the Hessian estimate. To further investigate the sensitivity, we conducted additional experiments using the same setup but with significantly smaller values of // (c.g., V < 0.5). In this regime, the estimator effectively utilizes only the most recent 1-2 rounds of zeroth-order information, resulting in a high-variance and uninformative Hessian approximation. The results, shown in Figure reveal that performance deteriorates as / decreases, confirming that a well-accumulated Hessian estimate is crucial for acceleration. Importantly, while poor Hessian approximation degrades performance, the algorithm still converges to reasonable solution. Since the preconditioner H remains a positive definite diagonal matrix, the "worst-case" scenario resembles poorly scaled first-order method rather than catastrophic failure. Conversely, these results validate that when the Hessian is well-learned (high v), it provides meaningful acceleration.
F.7.3 HESSIAN APPROXIMATION EVALUATION IN RANDOM SUBSPACES
While exact computation for the full model is prohibitive, we can rigorously analyze the exact Hessian within restricted subspaces. To do so, randomly sampled 1000 parameters to compute the exact 1000 1000 Hessian matrix E. We then projected the learned Hessian H from HiSo into this same subspace obtain HT
31

---

Published as a conference paper at ICLR 2026
Test Accuracy
0.95
HiSo 0=0.1
0.90
HiSo v=0.3
HiSo v=0.4
0.85
HiSo v=0.7
HiSo v E [0.9. 0.99]
0.80
500
1000
1500
2000
Communication Round
Figure 9: Impact of smoothing parameter v when is way smaller than 0.9. The gray area indicates the final performance HiSo when chosen in [0.9, 0.99] range. We can view the 0.1 case does not learn good Hessian approximate, hence the gap between the curves indicates improvement of good Hessian approximation.
104
Est. E|zls subspace
Lioschiz
30000
Whitia
25000
Sulepera D mension
Lowe Effective Rank
10a
15000
10000
102
Sub. Dim.
Lipschitz
Low Eff. Rank
Whittening
Random Sampled
Figure 10: Estimation of E| upper bounds restricted subspace. We randomly sampled 1,000 parameter indices from the final trained model in Figure extract the exact subspace Hessian and the corresponding learned diagonal Hessian H. The plotted quantities correspond to the four upper bounds listed in Table "Sub. Dim." (2d), "Lipschitz" (Ld, estimated via the largest eigenvalue of subspace Hessian), "Low Eff. Rank" (Lx), and "Whitening" (C). The left boxplot figure reports the values estimated across 10 independently sampled subspaces. The right figure illustrates how these quantities vary as the dimension the sampled subspace increases.
The eigenvalue correlation between Σ and is modest (7-20%, which we consider a reasonable value for diagonal approximations), But when we evaluate the quantity B||u||s discussed in Table we observe much better improvements. The whitened Hessian eigenvalues are significantly smaller than the dimension and lower than the low effective rank estimation that subspace. Specifically, we observe Č ~ 150, the estimated Ls ~ 250, and Ld ~ 5000. Compared to the ideal synthetic result in figure is reasonable to expect that the improvement is not significant. But this improvement is more or less consistent with our LLM experiment in Figure 7. We repeated this process across multiple sampled subspaces; the boxplot in the left one Figure T0 confirms the consistency of this observation.
Finally, we acknowledge that subspace Hessian eigenvalues are not unbiased estimators of the full Hessian. To mitigate this gap, we plotted the estimated quantities across varying subspace dimensions (the right one in Figure T0p. As expected, the worst-case Lipschitz estimation Ldd increases rapidly with dimension, whereas the whitening metric remains robust and insensitive to changes in dimension.
G MULT-PPETTURATION VERSION
Following our detailed examination of ZO- gradienn variance, it is evident that reducing this variance crucial for enhancing the performance of ZO-based methods. In this context, multi-perturbation sampling in ZO-SGD can be viewed as analogous to mini-batching in standard SGD, where multiple samples are used to improve the quality of the gradient estimate.
32

---

Published as a conference paper at ICLR 2026
In terms of HiSo, the multi-perturbation version is simply replacing the finding Au step by the following:
forp p 0, ,.1., 1
kp 1),
gr. [lici + .HH," 1/2 un,..)))))) (x///))
(0)
-
(88)
Au = H 1/2 1 Σ (1) Irkkp Dr.k..
Notice for the multi-perturbation version, we need to transmit P random seeds to generate p random (i)
vector Ur Moreover, P local gradient scalars fr,k.p required to be communicated well.
At the server side, the aggregation step now is required to average P values separately:
A
Σ IEC, K=0
( Fr
H1
1/2 My Krp
(89)
-|C,|
C
p=0
iECr
:00,kkpp
Notice we can switch the order of summation in above equations because ky common among all clients. This aggregated gradient scalar 9r.k stands for the r-th round, k-th local update, and p-th perturbation. P gradient scalars together with random seeds are sufficient to reconstruct the global Ary,k. For the reconstruction step, everything is the same.
G.1 PERFORMANCE ANALYSIS
Theorem 2 (Multi-Perturl Pantu-PPetttrbaiinn Version). Under Assumptions 7 and if S
min wT. SPE.P" 4(--1) M(d22]
Br
the sequence of iterates generated by HiSo with P pertur-
bations satisfies:
R-1r-1 TR
4(F(F)) -Ft)
32n(T - L5
16nĀp
E EI
(0g + o²)
(o + o
nTR
Brrm
B.m
O(nu),
extra client drift term
(90)
where
0p RR
1HT,,,1/E,, Tr(H, 1/2 11,,11111 + ( + ",,,,
(91)
op R Σ THH + C +1]|H,
(
(92)
and the rest of the quantities are the same as Theorem
Proof: In this case, the algorithm formulation can be written
Vk+1 27
=k.p V + O(wr),
(93)
Øk+1 -b++1
(94)
Notice there are three sources of the randomness - random direction gradient noise coming from ÉAm and the sampling randomness W₁. They are independent of each other, can treat them one by one separately. is straightforward to verify that the mean is unchanged
E P
T Zk. k
( Ex) = H (x(x)
(95)
p=1
33

---

Published as a conference paper at ICLR 2026
Next, noting { tp is independent and identically distributed, utilizing lemma we establish
2k.p2 2k
2h,0
p
p2
P
H
E H
E kn 2 Ea
p2
p2
P-1
H
Hy
H + (Tr(ExHE')) H
2H H
P
TCEA (
Ex
(96)
Recall that this quantity Pk of the single perturbation case
= HH 12 1/2) + 2 1/2 2 11 1/2
The multi-perturbationn version one will become
PR.P P Tr 1/2HH1133000 13) +
|111 1/2 2 1/2 1/2 20 P
Recall that the first term in Pk: is typically much bigger than the second one. Hence, Pk.P pk/ P as we expect that multi ceatiiperturbation will decrease the variance the random search direction.
Besides, it is similar case applied quantity:
1 P Tr(HE
(+ +1) H H
E 2k.p Fk.p' Ek.p'
(97)
p2 y'Eppl
So that the multi-perturbationn version of Φr,P will become
or, Ir(H,)) ( +1 |1
p 0r (6)).
Notice we just need to update the Eq. (58) with the result of Eq. simplification, we establish the result Theorem
After some calculations and
G.2 CONVERGENCE RATE
Notice the relationship Pk,P pk/ P, we can immediately establish that for 1 the convergence rate of Hiso is O mf
Further, under the well-approximated Hessian assumption, we can
establish the dimension-free free rate
R-1
(V
VF (o =0
S
(98)
mPR
When 7 > 1, we have O (V
TØ mR
Further, under the well-approximated Hessian
TmR
assumption, we can establish the dimension-free rate
(v
ΣΣ VF
S TmPR
+0
TK
(99)
7R
mPR
km
34


Reviews:
[{"review_id": "LDLsbmrAJr", "reviewer": "Reviewer_NVun", "summary": "The authors of this manuscript propose HiSo, a Hessian-informed federated zeroth-order (ZO) optimization method. It aims to accelerate the convergence of ZO-FL, which is attractive for LLM fine-tuning due to its scalar-only (dimension-free) communication, but typically suffers from slow convergence. The method computes a global diagonal Hessian approximation using an Adam-style update rule, which does not require transmitting any second-order information. The authors use this approximation to inform the ZO update direction. They provide a theoretical analysis showing convergence rates independent of model dimension and empirical results demonstrating a 1-5x speedup in communication rounds over the DeComFL baseline.", "questions": "1- How does the performance of HiSo change when applied to newer generations of models, such as the HuggingFace SmolLM or smaller variants of Qwen-2.5, LLaMA-3.2, and Gemma 3? Do the same convergence benefits hold?\n\n2- The authors call the method \"Hessian-informed.\" However, the update in Equation (12) is mathematically very similar to the variance/second-moment update in the Adam optimizer (a first-order method). Could the authors clarify why this should be considered a second-order method and not a first-order adaptive method? A direct comparison of the HiSo formulation with Adam would be insightful.\n\n3- The paper focuses on fine-tuning. Can the proposed ZO-FL framework be used for the pretraining of LLMs? What are the primary challenges in applying this method to the pretraining regime? I understand pretraining is expensive and do not expect experiments, but insight into the challenges would be helpful.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1- The improved convergence by HiSo is significant in comparison to other ZO-FL benchmarks, while keeping the communication costs significantly small. The 1-5x speedup over DeComFL is a practical and valuable improvement.\n\n2- The paper provides a theoretical analysis to support the method, proving a convergence rate independent of model dimension `d` for non-convex functions.\n\n3- The proposed method addresses a clear and important bottleneck in federated LLM fine-tuning, namely the high communication cost of traditional first-order methods and the slow convergence of previous ZO methods.", "weaknesses": "1- The experimental validation is limited to the OPT family of models (OPT-125M to OPT-2.7B). These models are somewhat dated and are known to be undertrained. The effectiveness of HiSo on newer, more capable models (e.g., smaller variants of LLaMA-3.2, Qwen-2.5, Gemma 3, or SmolLM) is not demonstrated. It is unclear if the same optimization behavior will hold on these new architectures.\n\n2- The claim that HiSo is a \"Hessian-informed\" or \"second-order\" method is potentially misleading. The proposed update for the diagonal Hessian approximation in Equation (12) is a recursive exponential moving average of the squared updates. This formulation is functionally identical to the variance/second-moment tracking in first-order adaptive optimizers like RMSProp or Adam. This makes the contribution appear more as an application of an adaptive preconditioner to the ZO setting, rather than a true second-order method.", "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": "46c9maUbgL", "reviewer": "Reviewer_HtDg", "summary": "This paper studies federated learning via zeroth-order optimization. By proposing a method that preserves scalar-only communication and avoids transmitting second-order information, it significantly reduces computational costs. Theoretically, they demonstrates an accelerated convergence rate under a suitable Hessian structure.", "questions": "See the weakness.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written, with a well-motivated research goal and a clear description of the  algorithm.", "weaknesses": "I have the following concerns regarding the paper:\n\nTheoretical Practicality and Depth: The theoretical analysis relies on a good approximation of the Hessian, yet the method employed in practice is only a diagonal approximation. This gap makes it difficult to appreciate the practical relevance of Theorem 1. Furthermore, a simple non-convex analysis seems insufficient, as it fails to capture the specific landscape properties of neural network loss functions.\n\nExperimental Comprehensiveness: The experimental validation appears somewhat limited. It would be strengthened by including plots of the training loss against both iterations and wall-clock time on more experiments. Additionally, experiments on more datasets and with larger models would better demonstrate the scalability and robustness of the proposed method.\n\nNovelty of Insight: The core idea seems limited. Since zeroth-order optimization inherently accesses only scalar information at each step, the advantage of communicating solely scalars appears straightforward. I did not find significant novel algorithmic insights in the current work.", "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": "BwvVFzkpvL", "reviewer": "Reviewer_FQxG", "summary": "In this paper, the authors propose HiSo, a Hessian informed, scalar only, federated zeroth order optimizer for large language model fine tuning.  The authors first generalize the scalar only paradigm into a reusable federated optimization framework, where the server and clients exchange only scalar update codes and can reconstruct each other's parameter trajectories without ever sending high dimensional tensors. Within that framework, they introduce HiSo, which maintains a global diagonal Hessian approximation on the server and uses it to precondition the zeroth order perturbation directions. Effectively, HiSo samples Hessian aware update directions, similar in spirit to natural gradient or approximate Newton steps, but still communicates only scalars.", "questions": "see weakness 1,2,3", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Theoretical contribution:  The paper proves non convex convergence bounds where the rate depends on a whitening rank related to the effective Hessian spectrum instead of the raw model dimension, and extends DeComFL style theory to multiple local steps per round.\n\n2. Strong and concrete motivation:  Existing scalar only ZO methods solve bandwidth but converge painfully slowly. HiSo squarely targets this convergence bottleneck without giving up the scalar only advantage.\n\n3. The paper repeatedly reports actual bandwidth numbers in KB and TB, and highlights 10^7 to 10^8 fold savings compared to FedAdam and FedAvg.", "weaknesses": "1. Benchmark scale and diversity：The main LLM experiments involve six clients with two sampled per round, and tasks are classification and extractive QA. Although these are standard NLP benchmarks and good stress tests for convergence and accuracy, they are still small compared to industrial federated networks across hospitals, phones, or enterprises. The paper would be stronger if it included either larger federations or at least a stress test with many more clients and skew patterns.\n\n\n2. Backbone model: The authors only conduct experiments on OPT series models, how about the Qwen series models? I am curious about the performance of proposed method on those models. \n\n3. Theory assumptions and coverage:\n   The convergence guarantee depends on a low effective rank Hessian spectrum and on the quality of the diagonal Hessian approximation. While the paper provides evidence that the estimated diagonal Hessian has a long tail and argues that large language models empirically satisfy this, it does not show failure cases or quantify how often the whitening rank assumption holds in domains beyond language. This makes it harder to judge how robust the dimension independent claim really is.", "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": "t9JC58MxVZ", "reviewer": "Reviewer_3tFi", "summary": "This paper proposes HiSo, a novel federated learning (FL) algorithm designed for communication-efficient fine-tuning of Large Language Models (LLMs). HiSo innovatively combines zeroth-order (ZO) optimization for dimension-free communication with Hessian-informed preconditioning to accelerate convergence. The core idea is to use a global, diagonal Hessian approximation to guide the random search directions in ZO optimization, effectively creating a \"natural gradient\" style update. Crucially, this Hessian information is learned and applied without transmitting any second-order matrices, preserving the scalar-only communication property that makes ZO methods attractive for high-dimensional problems. Theoretically, the authors provide a convergence analysis suggesting that under a \"low-effective-rank\" assumption for the Hessian, HiSo can achieve a rate independent of the model dimension d and Lipschitz constant L. Empirically, HiSo demonstrates significant speedups (1-5x in communication rounds) and up to 90 million times lower communication cost compared to first-order baselines like FedAvg on LLM fine-tuning tasks.", "questions": "1.  How does the total energy consumption (a function of both communication and computation) of HiSo compare to first-order methods and DeComFL, especially when considering the additional forward passes required for ZO estimation?\n2.  Could the HiSo framework be naturally extended to incorporate PEFT techniques (e.g., applying Hessian-informed updates only to low-rank LoRA parameters)? Do you see this as a promising future direction?\n3.  The theory suggests performance degrades to match DeComFL if the Hessian approximation is poor. Did you observe this in practice during the initial stages of training or on any specific tasks?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.  Novel and Well-Motivated Idea: The combination of Hessian-informed updates with scalar-only communication is highly innovative. It directly addresses the primary weakness of ZO methods (slow convergence) while preserving their key advantage (low communication cost). The motivation is clear and grounded in the practical challenge of federated LLM fine-tuning.\n2.  Strong Empirical Evaluation: The experiments are comprehensive, spanning from simple CNN/MNIST setups to LLM fine-tuning on standard NLP benchmarks (SST-2, QQP, SQuAD). The comparisons against a wide range of baselines (FedAvg, FedAdam, FedZO, DeComFL) are convincing and demonstrate clear improvements in convergence speed and final accuracy for ZO methods.\n3.  Significant Practical Impact: The reported communication savings (MBs vs TBs) are monumental. If applicable to even larger models, HiSo could have a substantial impact on the feasibility of federated fine-tuning in bandwidth-constrained environments.\n4.  Theoretical Depth: The paper goes beyond mere algorithm design by providing a non-trivial theoretical analysis. The introduction of the \"low whitening rank\"  to explain the accelerated convergence is a valuable conceptual contribution that helps reconcile the practical efficiency of ZO methods with their pessimistic worst-case theoretical bounds.", "weaknesses": "1.  Limited Discussion on Computation Overhead: While communication is the primary bottleneck, the computational cost of ZO methods is inherently higher than first-order methods due to the need for multiple forward passes. The paper briefly mentions the preconditioning time is negligible but does not provide a full comparison of the total wall-clock time (computation + communication) against first-order methods. This is crucial for assessing real-world utility, as increased computation time might offset communication savings.\n2.  Validation of Theoretical Assumptions: The core theoretical improvement hinges on the \"well-approximated Hessian\" condition (Eq. 17) and the low-effective-rank property. While the empirical results are strong evidence, the paper does not directly validate that the learned diagonal matrix H actually satisfies this condition for the LLMs used in the experiments. A more rigorous analysis or measurement of the whitening rank  during training would strengthen the theoretical claims.\n3.  Comparison with Parameter-Efficient Fine-Tuning (PEFT): The discussion of FL+PEFT baselines (like FedLoRA) is brief and relegated to the appendix. Given that PEFT is a dominant approach for efficient LLM fine-tuning, a more thorough comparison in the main text is warranted. HiSo's claim of \"full-parameter\" tuning is a different paradigm, but a direct comparison on metrics like final accuracy, communication cost, and memory usage would better situate HiSo within the existing landscape.\n4.  Hyperparameter Sensitivity: The ablation study on the Hessian smoothing parameter ν shows robustness, but the performance of adaptive methods like HiSo can be sensitive to other hyperparameters like the learning rate and the exponential moving average decay factor. A more detailed sensitivity analysis would be helpful for practitioners.", "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": "cHkvDxWs9Z", "reviewer": "Reviewer_7YFj", "summary": "This paper proposes HiSo, a novel Hessian-informed zeroth-order optimization method for federated learning that achieves dimension-free communication while accelerating convergence. The key innovation lies in leveraging global diagonal Hessian approximations as preconditioners without transmitting second-order information, thus preserving the scalar-only communication paradigm. Theoretically, the authors establish a convergence rate independent of model dimension and Lipschitz constant under certain Hessian approximation assumptions, providing the first such result for ZO methods in FL with multiple local updates. Empirically, HiSo demonstrates 1-5× speedup in communication rounds and up to 90 million times communication savings compared to first-order baselines across diverse LLM fine-tuning tasks.", "questions": "The theoretical advantages rely on the \"well-approximated Hessian\" condition. Do you have any empirical evidence (e.g., comparing with true Hessian on small models) suggesting your learning method effectively captures principal curvature directions?\n\nIn extreme FL scenarios with massive client populations (e.g., millions), could maintaining client participation history become a server-side memory bottleneck? How do you assess this scalability aspect?\n\nThe Hessian smoothing parameter ν appears to have minimal impact. Does this indicate HiSo is genuinely insensitive to this hyperparameter, or are there implicit guidelines for its selection?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The primary strength is the elegant resolution of a fundamental tension between leveraging second-order information for acceleration and maintaining extreme communication efficiency. HiSo represents a conceptually novel approach with non-trivial theoretical analysis and compelling empirical results. The scalar-only communication property holds significant practical value for bandwidth-constrained federated LLM fine-tuning.", "weaknesses": "The main weakness concerns the foundational assumptions underlying its theoretical advantages. The critical \"well-approximated Hessian\" condition is challenging to verify empirically, particularly during early training stages. While outperforming ZO baselines, the accuracy gap with first-order methods remains, highlighting inherent limitations of the ZO approach.", "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 (Poster)