Unlocking the Potential of Weighting Methods in Federated Learning Through Communication Compression
Authors: Valery Parfenov
Nail Bashirov
Daniil Medyakov
Dmitry Bylinkin
Aleksandr Beznosikov
Venue: ICLR 2026 Poster (2026)
Keywords: Convex optimization
Compression
Stochastic optimization
Primary area: optimization

Abstract: Modern machine learning problems are frequently formulated in federated learning domain and incorporate inherently heterogeneous data. Weighting methods operate efficiently in terms of iteration complexity and represent a common direction in this setting. At the same time, they do not address directly the main obstacle in federated and distributed learning -- communication bottleneck. We tackle this issue by incorporating compression into the weighting scheme. We establish the convergence under a convexity assumption, considering both exact and stochastic oracles. Finally, we evaluate the practical performance of the proposed method on real-world problems.

UNLOCKING THE POTENTIAL OF WEIGHTING METH- ODS IN FEDERATED LEARNING THROUGH COMMUNI- CATION COMPRESSION
Valery Parfenov1.23
Nail Bashirov Daniil Medyakoy
Dmitry Bylinkin 1.2.
Aleksandr Beznosikov!.2.4
Basic Research of Artificial Intelligence Laboratory (BRAIn Lab) Moscow Independent Research Institute of Artificial Intelligence HHS University "Federated Learning Problems Laboratory *Innopolis University
ABSTRACT
Modern machine learning problems frequently formulated in federated learning domain and incorporate inherently heterogeneous data. Weighting methods operate efficiently in terms of iteration complexity and represent common direction in this setting. At the same time, they do not address directly one of the main obstacle in federated and distributed learning communication bottleneck. We tackle this issue by incorporating compression into the weighting scheme. We establish the convergence considering both exact and stochastic oracles. Finally, we evaluate the practical performance of the proposed method on classification problems.
INTRODUCTION
Behind groundbreaking results achieved by new machine learning models lies carefully constructed optimization process. From the advent Stochastic Gradient Descent (SGD) (Robbins & Monro 1951) to adaptive methods like Adam (Kingma & Ba 2014) and beyond, new outputs of optimization theory not only accelerated convergence but have, at times, redefined what is possible in entire industries. Contemporary supervised machine learning approaches universally require large- scale training data to reach state-of-the-an results on established benchmarks (Alzubaidi et al. [021]] Hoffmann et al. 2022 Shoeybi et al. 2019). The primary way to process this volume of samples is usage multiple nodes for computations. This setting poses new challenges for the research community, highlighting once again that the future of the entire field hinges novel solutions.
To harness the full potential of such data, distributed learning [Verbraeken al. 2020 has become domain paradigm, enabling cutting-edge results in computer vision (CV) (Goyal et al. 2017), natural language processing (NLP) (Shoeybi et al. 2019). and recommendation systems (Covington et al.) 2016) by leveraging multiple machines working in parallel. Formally, this setting can be characterized by the following formulation of optimization problem:
min
f(0)
Σ f((0)
(1)
DER
where (0) represents the empirical risk (Shalev-Shwartz et al. 2010) for data at node bottleneck emerges in this distributed setting: communication. During the training process, local model states should be synchronized. This coordination steps can prohibitively time-expensive and completely offiset advantage gained from parallel processing.
Federated learning offers several major approaches to address this issue: local steps techniques (Stich) 2018, Gorbunov et al., (02Tb), partial participation concept (Li et al.) 2019b) Rizk al. 2021). diata-simiilaitty-bueee methods (Hendrikx et al. 2020 Kovalev al.) [0222] Lin et al.) (203)). Finally, in our work, we adopt compression. The first works in this field were dedicated to one-bit quantization (Seide al.] 2014 Bernstein al. 2018). Currently, the most widely used techniques include quantization (Alistarh et al. 2017) and sparsification (Alistarh et al. 2018 Beznosikov et al.
"Email: paafenov.vr@gmaai.ccm

---

methods such as RandK and TopK. A key consideration in this context is that increasing the number of nodes enhances the robustness of the training process to inaccuracies in aggregated local gradients. This gives rise to trade-off between transmission precision and communication cost, which can be exploited by compressing gradients during aggregation. Formally, compression can be described using unbiased and contractive compression operators. In work, utilize the former.
2023a
Definition 1.
We say that map Q Ia E' is an unbiased compression operator, simply unbiased compressor, if there exist a constant w such that holds:
[[(()] = E [I] [ S w||z|| for all x E R.
(2)
Contemporary problem formulations often additionally involve heterogeneity, which necessitates the development of federated learning techniques (Konečný et al., 2016, McMahan et al., 2017]
Smith et al., 2017 [i et al. 2020; Kairouz et al.] (021). The high cost of transmitting raw samples often makes homogeneous redistribution infeasible. Moreover, in particular settings, observation
redistribution is impractical or fundamentally disallowed (Nishio & Yonetani, 2019 Zhang et al.
2020
Diao et al. 2020 Mishchenko et al.) 2023 Khirirat et al. 2023 Islamov et al. 2025).
Standard formulation I of the objective function treats all devices equally. However, since the data
across nodes may inherently differ, the effectiveness of this formulation becomes questionable. To address this issue, various weighting strategies was proposed, alternating the optimization problem
into
M Σ fifi(0) }
min OER
where T. represent weights constrained to the simplex AM-1, provided by particular weighting method. The idea here is to assign big weights to clients with clean representative or even unique data, and small weights to ones with noisy inappropriate samples. If this is achieved by any means, performance of the model can be improved by effectively training it on higher-qualins observations.
Currently, a wide range weighting methods has been developed (McMahan et al. 2017 Nishio & Yonetani 2019:; Wang et al., 2020 Cao et al.) (020)). Each technique offers its own advantages, such as adaptivity or the absence of extra information communication. Agnostic reformulation of
optimization problem (Mohri et al. 2019 Namkoong & Duchi 2016 Shalev-Shwards & Ben- David 2014 Hashimoto et al.] (018)::
M Σ Em.1100)
min max BER REA
where A is a convex subset of M-1 combines both of these advantages. The weights are selected automatically during training, while the strategy only requires the server to have additional knowledge of the local losses. Communicating this information inexpensive and does not exacerbate the communication bottleneck. Intuitively, the method operates as follows: if certain nodes possess unique observations, a brief training phase can lead to a rapid loss reduction on the remaining users' samples. This, in turn, assigns higher weights to the devices holding the unique data, thereby mitigating the problem of data imbalance and reducing model bias. However, while mitigating the issues of data heterogeneity across nodes, weighting methods do not address another core challenge- - the communication bottleneck which makes them independently nonviable in real-worke applications. To address this fundamental problem and unlock the practical potential of weighting methods we aim to investigate the following question.
Is it possible effectively combine weighting-bet -aased approaches with communication compression techniques?
OUR CONTRIBUTION
We answer the posed question affirmatively by introducing ADI (Algorithm Tp. It incorpo- rates compression (I) into agnostic weighting scheme (4). Moreover, operating in the saddle point problem setting, the proposed method never requires the transmission of full gradients, which is further reinforce practical applicability.
2

---

We establish theoretical guarantees under general assumptions for the weighting setup. Our analysis additionally includes practically relevant settings of stochastic local oracles and partial participation.
We validate ADI performance the classification problems, including large scale real world task and an experimental study of the interplay hetween compression and weighting techniques.
3 RELATED WORKS
In this section, we intend to survey both classical results and recent developments the fields of weighting methods, compression, and saddle point problems, with particular focus on studies that integrate the latter two. These directions are most relevant to our work.
3.1 WEIGHTING METHODS
First approach in this field, FedAvg MMMMhan al. 2017), suggests assign weights to clients regarding the size of dataset my; n. ma, where m - my, This approach enables weight determination prior to training initiation, which precludes the need for additional inter-node commu- nication and mitigates associated bottleneck. However, it only addresses data imbalance in terms of quantity rather than quality. Subsequent approaches employ dynamic weight assignment. To estimate client importance, they leverage such information as cross-client weight distribution divergence (Wang et al.) (2020), local-global gradient discrepancy (Cao et al.) 2020 Nguyen al.) (2020), and local loss (Mohri et al. [2099] Cho et al., (2022). Alternative approaches leverage hardware-aware metrics, including node computation capacity and connection stability, to accelerate training. These methods minimize participation of edge devices with significantly slower compute or communication
capabilities (Nishio & Yonetani 2019 Li ct al. 2022; Ribero al. 2022).
Utilized in this paper technique 44 (Mohri et al. 1019,oamooong & Duchi 2016 Shalev-Shwarc &
Ben-David 2014 Hashimoto et al. 2018) offers the benefit of adaptivity while introducing minimal additional communication overhead, it only requires transmitting local loss values single scalar per device. The communication cost of aggregating this exact information is incomparably lower than even that of compressed gradients. This feature is particularly crucial as we aim to address the communication bottleneck. Finally, as can be observed, problem (4) is saddle point problem not classical minimization one. This introduces additional challenges algorithm design and theoretical analysis.
3.2 METHODS FOR SADDLE POINT PROBLEMS
The Bradient Descent method can be generalized to Descent -Ascenttt-scntt. algorithm (Loizou al. (02T) for saddle point problems (SPP). However, this straightforward generalization may fail to converge even for relatively simple objective functions (Beznosikov et al. (003b)) A more robust alternative, the Extraagra aadiradiee ent method, was introduced in 1976 by Korpelevich and has since become fundamental paradigm for solving saddle point problems. The original Ext rattrargrdee algorithm requires two gradient evaluations per iteration, but there are modifications that reduce this to single one, for instance, optimistic approach (Popov) 1980). It is worth noting that alternative techniques for solving SPP also exist (Tseng 2000 Nesterov 2007 Malitsky 2015). At the same time, the research community continues to actively adapt Ext r agr adiienni method to various settings [Nemirovski] 2004 Alacaoglu & Malitsky 2022), including distributed learning with communication compression Beznosikov al. 2022).
3.3 COMPRESSION METHODS
QSGD (Alistarh et al. 2017) was one of the initial steps toward understanding compression techniques applied to classical minimization problems. examined the incorporation quantized communica- tion into SGD (Robbins & Monro 1951). Authors used restrictive assumptions that all nodes have identical functions, and the stochastic gradients have bounded second moment. These assumptions were relaxed in subsequent studies (Khirirat et al.) 2018 Mishchenko et al./ (2024). Additionally, QSGD suffered from an irreducible term in the theoretical convergence bound, caused by the stochas- ticity of the compressor, even when full local gradients were computed. The next notable concept in
3

---

this field was the error feedback technique. Initially introduced as successful heuristic (Seide et al. 2014; Ström 2015). later it obtained theoretical support in (Stich et al. 2018; Karimireddy et al. 2019) and enabled the analysis of biased compression. Then, significant ad advancement followed with the idea of compressing the difference between successive local gradient estimators, instead of directly compressing the gradients. This concept first introduced in ANA (Mishchenko iet al. (024) and enabled vanishing irreducible compressor stochasticity term, improved theoretical guarantees and extension of the analysis to new settings. Later, in (Richtárik et al. 202T). was shown that local state difference compression can be interpreted as variant of the error feedback technique, which led to the development of the EF21 algorithm. Subsequently, in MARINA (Gor) bunov et al., (021a) the PAGE (Li et al. 2021) variance reduction technique was utilized. Using biased local gradient estimators MAR TNA reached state-of-the-art convergence rates. Finally, the authors of DASHA (Tyurin & Richtárik 2022) ultimately combined error feedback with the EF21 mechanism and achieved optimal oracle complexity while preserving the state-of-the-an communica- tion performance of MARINA. Moreover, they eliminated the need for periodic transmission of full gradients, which was required in MARINA.
Despite the fundamental importance of variational inequalities including saddle point problems, and their extensive study, methods for them which incorporate the compression remains largely unexplored. Only several algorithms operating in this setting was proposed. MASHA (Beznosikov) concept. An extension of MASHA (Beznosikov & Gasmikov (022), incorporates the optimistic principle and, through the use of permutation compressor, leverages data similarity strengthen theoretical guarantees. Finally, Three Pilla Fillars (Beznosikov et al. 2023c) combines compres- sion, data similarity, and local steps, unifying all three concepts within single framework and achieving optimal theoretical guarantees. However, despite these theoretical advantages, the practical applicability of Three Pillars remains limited. In particular, due to its strong reliance on data similarity across all devices. Moreover, key practical drawback of all three methods lies in the requirement for periodic transmission of full operator values.
al. 2022). , integrates operator compression with the Extragradiens
this approach, Optimist
4 SETUP
The analysis in this work is conducted relying on further assumptions. Assumption 1. For all i = 1,2,.... M, let Sa be Li-Lisschitz, i.e., (((0))))(00)) S 4. - 02ll holds for all 01, 0g E Rdd We denote L = max{Li};
..3...,,,...
Assumption 2. For all i 1,2,...,A M. let fo be Li-smooth, i.e., (l1) vf((1)) S T.i|00 02] holds for all 01, 02 Rdd We denote = max(
Assumption 3. For all i = 1, 2, M, let fi be corvex, iee, fi(0,) 2 f((02) (V..(0)), 01 - holds for all 01, 02 E Rdd
ALGORITHM AND THEORETICAL ANALYSIS
5.1 DESCRIPTION OF THE ALGORITHM
Now we are ready to present our Algorithm 1 ADII (Agnostic DIANA). In suggested approach each
iteration begins with the nodes computing weighted loss gradient ft. compressing the difference with their local memory state, and sending the result to the server - Linnss 55 and respectively. Additionally, Lines[3]add [ represents the modifications required in stochastic local oracle and partial participation settings. The nodes then update their local states in Line g
All remaining operations are carried out on the server side. Firstly, it aggregate compressed local differences and local losses - Line 1T] Then, gradients estimators g and p with respect to @ and are computed in Lines 12 and 14 After that, the update of 0 is performed using the optimistic version ğ of oracle g- - Lines 16 and 13 At the same time, the weights म. are constrained to remain within a subset A of the simplex. Hence, a Mirror Descent step in Line 17 is applied to update them. Where the - divergence is used as the Bregman divergence (Bregman (967). Additionally,
point out that due the maximization over πt in agnostic objective formulation 44. a negative sign precedes the inner product. Finally, server updates the local state h and communicates 0 and n, to each node.
4

---

Thus, Lines 16 and considering Lines
13 and 15 correspond to a step of Optimistt st ic
Extragradiers method (Yudin) 1983 Popov 1980). While Lines 7 8 12 18 reflect the idea
of difference compression introduced in D DIANA Mishchenko et al. 2024). This concept resembles the variance reduction technique (Johnson & Zhang 2013) and similarly enables the elimination of the irreducible term, caused by the stochasticity, in the convergence analysis. These methods are driven by an intuitive idea: near the optimum of a smooth function, the full gradient tends to zero, while local gradients may remain relatively large.
At the same time, according to Definition [ the distortion introduced by the compressor scales with the norm of its input. As re- sult, near the optima compression of local gradient introduce a significant noise and pre- vent the aggregated estimator from converg-
Algorithm ADI
I: Input: Starting points 0² E Rd TO E A, (1g) Mr No E IRd and ho 2i=1 h. num- ber of iterations K, number of nodes M, random variables 17," ~ Bern(p).
Σ
ing to zero. This leads to erratic oscillations near the solution 0 in practice and to an irre- ducible variance term in theoretical analysis.
2: Parameters: a. 3, T9, Ya > 0:p E (0, 1].
3: for k = 1,2,3....
K do
4:
for all nodes i = 1.2,..., M in parallel do
.22....., f ;; V fi ((tt) exact local gradient
In contrast, the difference between local gra- dients at nearby points is bounded due to the smoothness of each local objective. Hence, as the algorithm approaches the optimum and the update steps diminish, it becomes neces- sary to compress progressively finer differ- ences. Consequently, the local estimators h tend to the local gradients V (0*). It ensure that the aggregated estimator htt converges to zero. This property allows the method to converge to the optimum itself, rather than to a neighborhood of it.
5:
ftt = म, Vi.s. (0%) stochastic oracle
A = j.t -h
6:
A Q(A,)
7:
Â = ". Q(4() partial participation
8:
h ktt 11 + B
9:
send A (1hh) to server
10:
end for
11:
A Di=1 A
12:
g h + Å
Let us now justify the choice of D DIANA as the compression foundation in our method. To this end we consider alternative candidates.
13:
9 = (1 + a)g*
ag
D = (f)(0))) M
14:
i=1
15:
6e = (1 + tapp
ap*
Firstly, DASHA (Tyurin & Richtárik 2022). which demonstrates tfte-of-theearr results in the classical minimization setting, offers the- oretical guarantees under non-convex objec-
16:
g H 'a
17:
n arg min (-ra (1t x)
Dxz
TEA
18:
h++1 = / + A
tive functions. At the same time, the theoret-
19:
server send o. k+1 gh+1 to 7th node for all i
ical analysis of SPP in such setting remains largely underdeveloped. making the exten-
20:
end for
sion of DASHA's 's analysis to scenario intricated. MASHA (Beznosikov et al., 2022), the other hand, operates in the SPP setting and incorporates compression. However, it requires periodic com- munication of full gradients, which significantly limits its practical applicability. By establishing the analysis of D DIANA within the SPP setup, we avoid such constraints while leveraging its compression strategy.
Another detail we want highlight is simplex regularization. In various problem settings, it may be advantageous to impose additional constraints on the weights by restricting the feasible set to subset A of the simplex A M- (Mehta et al., 2024). Let us provide reasoning, helpful for understanding which regularization can be suitable in our case. Considering optimization problem with A = M- at optimum point the weights take the form of tio 1, 1, = 0 for all j # in. where io = f At the same time, some clients may possess noisy samples. The model
can not and should not - learn patterns from such data. Even single device with notable higher noise level can cause an obstacle to effective training. Partieularly, since its data is less representative, it experiences slower decrease in loss. As training progresses. this leads to the weight of that client growing close to one. Further training will only lead to overfitting the model to the noise present in the data of the given device. This potential issue can be mitigated by using A = A M-1 n Q.M where Q. = {x E RM (0 E x; S // } and a E [1, Mhe parameter a controls the trade-off between full flexibility in weight assignment and stronger averaging. Specifically, setting a = 1
5

---

recovers formulation I while M imposes additional constraints the weights. We employ regularization the specified form and additionally highlight its role in the theoretical sectrion.
Finally, us follow all communications the proposed algorithm. At each iteration, transmissions of (,())) from the nodes to the server and T.. 0 the opposite direction are required. As fe( and n. are scalar values, they do not pose major threat to communication efficiency. Then, both A and 6 have dimensionality The vector 8 is transmitted from the server to nodes, which poses fewer challenges (Kairouz et al. 2021). In contrast, aggregation of Å; on the server constitutes the main obstacle to communication efficiency. ADI address this issue since Á is compressed version of K which makes its transmission significantly cheaper than that of an general vector of dimension d. We now ready to proceed the theoretical analysis. In the following sections, provide guaranties for the cases of exact local gradients, stochastic local oracles and partial participation. For comparison of the ADI rates with those of prior compression methods, refer Appendix A
5.2 CONVERGENCE GUARANTIES EXACT LOCAL GRADIENT SETTING
We establish the convergence with respect to Gap function (Definition in Section F. It is standard for convex-concave SPP setup criteria. To initiate the analysis, we introduce the notation
(0, π)
and F(=*) = (g -p") Descent Lemma (Section F) imposes conditions on operator evaluation across iterations. Then Lemmas and 2 (Section Eb justify the transition to the Gap(z) function and
further analysis.
Finally, Theorem represents our main theoretical result. We remind that the constants T. and were introduced in Assumptions and respectively.
Theorem 1. Let Assumptions
hold and ar
1, B
To
7o =
min
A A AM-1 n Qa where Qa = tx
2L
360-+14M V AML 4676 12 12 2 2
RM 0 S x4 }.
Then, after K iterations of Algorithum
with unbiased compressor 2 and exact
local gradients solving problem (4) the following holds:
V
E [[Ga((Z>)] S
2
where
V
E max 4D 4D, +2100' 0|1
SED
M
+2> F(=))(()))))))))))))) - 211} ww
Σ k=
ft
nt|l
+ 7 ww
Σ pr -² 11 10
and 3K DR
This implies the following bounds the number of communication rounds and the amount of information transmitted from the clients to the server.
Corollary 1. In setting of Theorem 7 with 7 Yo. Algorithm 7 with exact local gradients needs
Ln + / + o 0-
(V aww
)))
+ w
M
iterations in order to reach e-accuracy with respect E [Gap Ex)) Additionally, it requires
O (
La + LM +
aw
M + +1))
bits communicated from nodes to the server.
The first term in both bounds in Corollary 1 originate from the recursion on || < IR. the weights are fixed, these terms vanish, and under condition < M, compression leads to at least no increase in communication complexity. Returning to the analysis of the full result, we must acknowledge that weighting algorithms typically suffer from weak theoretical guarantees. For instance, theoretically FedAvg enjoys only sublinear convergence rate in the strongly convex setting (Li et al. 2019b). In our setup, the rrighting-indducer terms deteriorate the theoretical guarantees

---

monotonically with increasing compression rate. Finally, discussing the role of simplex regularization the theoretical analysis, we note that enables an acceleration by a factor of a square-root M
terms.
5.2.1 EXTENSION TO THE NON-CONVEX SETUP
In this section, extend analysis by relaxing the convexity Assumption to Assumption 4 It is inspired by the minty assumption, traditionally associated with non-monotonicity (non-convexity) in the respective literature Dang Lan 2013): Mertikopoulos al. (2018): Kannan & Shanbhag (2019).
Assumption 4. Let there exists point 0" R such that:
M Σ T4((0) Σ m.)a for all E Bd N AMM--
TE TV(00000- 0r
For a more detailed discussion of the setting and the proof' for this section, we refer to Appendix G
Considered setting is special, since the objective function E i-=1 f(0) is linear in the weights by construction. This also reflected the criterion presented in (5) below. Convergence with respect to the weights involves the same term in the convex setting, whereas convergence with respect to the parameter is now expressed through the mean squared norm of the gradients.
M
M
W
E max T'EA
Σ
Mi00 (
m²) +
(. 0 0"
M
π k+1 - n 112 +
(0) K
K
K
32
Where T== Ex= 7 K 1
k+1 and क. VVf( ~ प. Vf. .....
The final result of this section, Corollary 2 provides convergence rates with respect to W under the relaxed assumptions. We remind that the constants L and L were introduced in Assumptions 2 and respectively.
Corollary 2. In setting of Theorem with y = 7/1 Algorithm with exact local gradients needs
of Lu + LM 1 + L
(V
aws
))
+
M
iterations in order to reach e e-accuracy with respect to W Additionally, it requires
(
Lo iM +
aw
M +1 +1)])
bits communicated from nodes to the server.
5.3 CONVERGENCE GUARANTIES IN STOCHASTIC LOCAL ORACLE SETTING
Despite introducing new challenges, federated learning is still subject to classical difficulties of gradient-based optimization. In practice, computing the full even local gradient may be prohibitively expensive, especially in the presence of devices with limited computational capabilities. This makes stochastic optimization (Robbins & Monro 195T Bottou et al. (2018) particularly relevant practical applications, including the context of federated learning. We extend analysis to cover this setting as well.
Guaranties in this case are provided under assumption that all nodes have access to an unbiased oracle (x*) with bounded variance, i.e., Assumption holds.
Assumption 5. Let all ls 1,2, K and = 1,,,,.... 1,2...., M V fi.g((")) satisfies
i) EV fa.s (@*) f((k))
i St. (0*) V/i(0+>)1 x
7

---

ADI structure imposes minor modification in this setting. Particularly, Line transforms into sample f = n. fi,. (0%). The theoretical analysis similarly remains largely unchanged. as stochasticity was already involved in the compression operator, and the oracle is assumed to be independent of it. Thus, we can reformulate Theorem for stochastic oracle setting as follows.
Theorem 2. Let in setting of Theorem additionally Assumption S hoodds Then, implies
V
64a
E [Gap(Zk))
+
o²
2
M
for iterations of Algorithm Choosing 7 min
7 with stochastic local oracles.
{
(70
V.M
obtain the further guarantees.
128a w
o
Corollary 3. In setting of Theorem with = min (70, local oracles needs
VM 1280" K
Algorithm with stochastic
o 0 o220022
(
aww Vawu M
)))
Lu 2/ + LM +
+
+
M
iterations in order to reach E-accuracy with respect to E [Gap(Ex)] Additionally, requires
[
[w + LM
(v aw
M + +1)]
M
bits communicated from nodes to the server.
In this case, guaranties Theorem 2 are affected by an additional irreducible term ? 61e2w² M o² induced
by the stochasticity of the local oracle. It is general term for analysis in stochastic oracle setup with Assumption 5 In its presence, optimal stepsize 7 transforms into min To-
VM 128a 12"K"="0"K
and
communication complexity bounds include additional term
5.4 CONVERGENCE GUARANTIES PARTIAL PARTICIPATION SETTING
Another classical direction in federated learning is partial participation (Li et al. 2019h Rizk et al., 202T). In its context only the subset of all nodes are involved in each computation and communication round. This modification addresses several challenges inherent to federated setting, primarily the periodic unavailability of some devices (Li et al. 2019b Yang et al. (021). We establish theoretical guarantees for this setup as well.
Corollary 4. In setting of Theorem 1 with 3 g. H1 32,
N
7 Tm 7
7p
min
2 AM1 (#) 22+ L 2T. 96(=)) +1*M(#))*
(0(=)*+
it implies
V
E Gap((Tk) 2
for iterations of Algorithm 7 with partial participation.
According Corollary 4 we bound number of communication rounds and volume data sent from the clients to the server.
Corollary 5. In setting of Corollary 4 with y = 7/p- Algorithm D with partial participation needs
(
i
3/2
LM
(v
a
+ P
p
My
iterations in order to reach e-accuracy with respect E [Gap (Ex)), Additionally, requires
o (T)))) (
1/2
(v Mp +1) +1))
+LM
bity communicated from nodes the server.
8

---

Analysis in this setting relies the observation that multiplying the compression operator by the p
2. with 17 ~ (p). yields another valid compression operator. It remains unbiased, while its
compression rate w is scaled by a factor of Finally we note that our analysis in stochastic local gradients and partial participation settings be straightforwardly merged.
6 EXPERIMENTS
To validate the performance of our algorithm ADI on practical tasks, we compare experiments against baseline methods that employ either weighting schemes or communication compression techniques. Specifically, AD I with no compression and EF21 (Richtárik et al.) (02T). DIANA (Mishchenko et al. 2024) serve representatives respectively, Although weighting- based approaches are specifically designed to improve performance heterogeneous settings, we assess the generality of ADI by conducting experiments under varying degrees of heterogeneity, including the homogeneous case. It is also important to note that classical approaches and weighting based methods formally solve different optimization problems ①1 and 3 Consequently, comparing them in terms of loss is not valid, and we instead rely on model quality metrics such as accuracy.
We conduct a comparative evalua- tion on image classification tasks ing CIFAR-10 10 (Krizhevsky et al. 2009) dataset and RESNET-18 (Meng) et al. 2019) neural network architec- ture, which is considered be stan- dard benchmark for optimizers perfor- mance. We set number of clients M equal to 10 and evaluate optimizers under major data distribution setups: i.i.d. distribution, where each client has the same number of data sam- ples, and class labels are uniformly distributed across clients; and non- i..d. distribution (namely Dirichlet one with the parameter a = 0.5) with different amount of data samples per client.
i...d.
non-L.id
Accomey
ADI [no comni
AD1 comp.t
ADI
DIANA
E722
4833
10900
communication runds
commun cation ounns
Rand50% compressor.
L.d.
non-L.id.
Acarray
Arrinry
ADI (ne compu
ADI (no comp.
ACI
AD1
DIANA
DIAMA
E722
2090
4893
19900
283
420
1990
communicatin rounds
cation ound:
The first set of experiments, presented in Figure [ compares ADI with compression- based methods under dif- ferent setups of data heterogeneity and parameter = 10%, 50% for RandK compressor. To ensure fair comparison, we run the experiments for 10k communica- tion rounds with stochastic oracle for each method and tune theirs hyperparameters.
Rand10% compressor.
Figure 1: Performance comparison for across different heterogeneity levels.
As illustrated in the plots presented in Figures ia Ib. the weighting mechanism plays cru- cial role in the convergence behavior of our method. By effectively mitigating the impact of data heterogeneity, ADI demonstrates supe- rior convergence properties compared base- line approaches. Furthermore, the accumulated weight adjustments significantly influence the later stages of training, contributing to enhanced model accuracy and overall performance. No- tably, comparing ADI and ADI (no comp.) we observe that incorporating compression only marginally slows down the convergence of the algorithm in terms of iterations, while yield- ing significant savings in communication bits.
90
80
Accuracy
50
40
ADI (no comp.)
30
ADI
DIANA (weighted)
EF21 (weighted)
2000
4000
6000
# communication rounds
Figure 2: Weighting approach comparison.

---

With the identity compressor, ADI reduces Optimistic Extragradi aditt (Popov 1980) method for problem effectively representing a standalone weighting- based optimization approach.
Ablation study. The second experiment (see Figure 2
compares the same compressed baselines, modification,
where additionally incorporate agnostic weighting via heuristic ceappeession-weighiiii design. We use
in order to isolate and assess the specific role of our joint RandK with K 10% and non-i.i.. data distribution. We observe consistent improvements in convergence across all methods demonstrating that while weighting itself enhances robustness in highly heterogeneous settings, our principled joint design yields the strongest gains over these naive integrations. We further analyze the evolution of client weights under Algorithm [ in heterogeneous setting, with full results shown in Figure 3 At initialization, all clients are assigned equal weights, reflecting no prior knowledge of their data quality or relevance. As training progresses, weights rapidly diverge, adapting to the statistical heterogeneity of local datasets. Over time, each client's s weight converges to distinct, stable plateau indicating that the system learns consistent, data-driven importance score for every participant.
This convergence behavior reveals two key phases of the optimization process:
0.25
Client No
Weight magnitude
0.20
(i) an early exploration phase, dur- ing which substantial weight adjust-
0.15
ments occur;
(ii) later stabilization phase, where weights remain nearly constant once the global model approaches an optimum.
0.10
Notably, significant reweighting ceases the optimizer enters neighborhood of (local or global) minimum, suggesting that the weight- ing mechanism primarily acts during transient. gighggradiett stages of training precisely when client contributions are most discriminative.
0.00
2000
4000
6000
8000
10000
# communication rounds
Figure 3: Weights magnitudes for Algorithm non-i.i.. data distribution setup.
Experimental setup details, additional experiments, including large scale problems, and more detailed weighting--ooprestti interaction experimental study be found in the Appendix B and
DISCUSSION
This study has introduced a method for federated learning, supported by comprehensive theoretical analysis and empirical validation. Theoretical guarantees scenarios, including setups with exact local gradients, stochastic local oracles, and partial client participation. Experimental results demonstrated that the superiority of the proposed method the baselines becomes more pronounced as the level of compression and data heterogeneity in- creases. This allows conclude that two of the most important problems in federated learning the communication bottleneck and data heterogencity can be addressed concurrently, offering new potential for specific federated learning formulations. Additionally, the developed approach maintains performance comparable to baseline algorithms in homogeneous data settings and never requires the transmission of full gradients, thus further supporting practical utility.
established for range of relevant
As natural direction for future research, saddle-point problems to our setting, as well as the extension of our analysis to the case of contractive compression operators (Beznosikov al. 2023a).
consider the adaptation of accelerated methods for
ACKNOWLEDGMENTS
The work was supported by the Ministry of Economic Development of the Russian Federation (agreement No. 139-15-2025-013, dated June 20, 2025, IGK 1000000113225P4BB00
10

---

REFERENCES
Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory, pp. 778-816. PMLR, 2022.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advunces in Neural Information Processing Systems, 31, 2018.
Laith Alzubaidi, Jinglan Zhang, Amjad Humaidi, Ayad Al-Dujaili, Ye Duan, Omran Al-Shamma, José Santamaría, Mohammed A Fadhel, Muthana Al-Amidie, and Laith Farhan. Review of deep learning: concepts, enn architectures, challenges, applications, future directions. Journal of big Data, 8:1-74, 2021.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
Daniel J Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Javier Fernandez-Maqque, Yan Gao, Lorenzo Sani, Kwing Hei Li, Titouan Parcollet, Pedro Porto Buarque De Gusmão, et al. Flower: A friendly federated learning research framework. arXiv preprint arXiv:2007. 14390, 2020.
Alcksandr Beznosikov and Alexander Gasnikov. Compression and data similarity: Combination of two techniques for communication International Conference on Optimization and Applications, pp. 151-162. Springer, 2022.
solving of distributed variational incqualities. In
Aleksandr Beznosikov, Peter Richtárik, Michael Diskin, Max Ryabinin, and Alexander Gasnikov. Distributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. Advances Neural Information Processing Systems, 35: 14113-1402,, 2022.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276):1-50, 2023a.
Aleksandr
Beznosikov, Boris Polyak, Eduard Gorbunov, Dmitry Kovalev, and Alexander Gasnikov. Smooth monotone stochastic variational inequalities and saddle point problems: A survey. Euro- pean Mathematical Society Magazine, (127):15-22) 2023b.
Aleksandr Beznosikov, Martin Takáč, and Alexander Gasnikov. Similarity, compression and local steps: three pillars of efficient communications for distributed variational inequalities. arXiv preprint arXiv:2302.07615, 2023c.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-33 311, 2018.
Lev M Bregman. The relaxation method of finding the common point of convex sets and its application the solution of problems convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217, 1967.
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine-robust federated learning via trust bootstrapping. arXiv preprint arXiv:2012.13995, 2020.
Chih-Chung Chang and Chih-Jen Lin. Diabetes dataset (scaled version). LIBSVM Data Repository, 2011. URL https::///// ///w:///wwwwwww www. csie. ntu edu. tw wtt.tt/www/nnliiitttttt wtt.://lnnnnliimmtooooooooo 1 hed/aaattett. Biiaayyddiabtea scale Original data from National Institute of Diabetes and Digestive and Kidney Diseases (NIDDK), 1999.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Towards understanding biased client selection in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 10351- 10375. PMLR, 2022.
11

---

Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM conference on recommender systems, pp. 191-198, 2016.
Cong D Dang and Guanghui Lan. On the convergence properties of non-euclidean extragradient meth- ods for variational inequalities with generalized monotone operators. Computational Optimization and applications, 60(2):277-310, 2015.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient
federated learning for heterogeneous clients. arXiv preprint arXiv:2010001264 2020.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. Marina: Faster non- convex distributed learning with compression. In International Conference on Machine Learning, pp. 3788-3798. PMLR, 2021a.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556-3564. PMLR, 2021b.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: 7rXxiv:700.02677,, 2017.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference Machine Learning. pp. 1929-1938. PMLR, 2018.
Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and Laurent Massoulie. Statisti- cally preconditioned accelerated gradient method for distributed optimization. In International conference on machine learning, pp. 4203-4227. PMLR, 2020.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203 15556,, 2022.
Samuel Horvoth, Chen- Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pp. 129-141. PMLR, 2022.
Rustem Islamov, Samuel Horvath, Aurelien Lucchi, Peter Richtarik, and Eduard Gorbunov. Double momentum and error feedback for clipping with fast rates and differential privacy. arXiv preprint 11X1::2502211662,, 2025.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
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 in federated learning. Foundations and trends@ in machine learning, 14(1-2):1-21) 2021.
Aswin Kannan and Uday V Shanbhag, Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):779-88) 0000002.20000000 2019.
Sai Praneeth Karimireddy, Quentin Rebjock, Sehastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International conference machine learning, pp. 3252-3261. PMLR, 2019.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed Icarning with compressed gradients. arXiv preprint arXiv:1806.066 06573, 2018
Sarit Khirirat, Eduard Gorbunov, Samuel Horváth, Rustem Islamov, Fakhri Karray, and Peter Richtárik. Clip21: Error feedback for gradient clipping. arXiv preprint arXiv:2305.18922 2023.
12

---

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:/610.05492 2016.
Brett Koonce. Resnet 34. In Convolutional neural networks with swift for tensorflow: image recognition and dataset categorization, pp. 51-61. Springer, 2021.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity, Advances in Neural Information Processing Systems, 0133494-33507, 2022.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Chenning Li. Xiao Zeng, Mi Zhang, and Zhichao Cao. Pyramidfl: A fine-grained client selection framework for efficient federated learning. In Proceedings of the 28th annual international conference on mobile computing and networking, pp. 158-171,22 2022.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprint arXiv: 2019a.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and futurre directions. IEEE signal processing magazine, 37(3):50-66) 60, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint arXiv: 1907.0299.. 2019b.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International conference machine learning, pp. 6286-6295. PMLR, 2021.
Dachao Lin, Yuze Han, Haishan Ye, and Zhihua Zhang. Stochastic distributed optimization under average second-order similarity: Algorithms and analysis. Advances in Neural Information Processing Systems, 36: 1849-1862, 2023.
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochas- tic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information Processing Systems, 34:19095- 19108, 2021.
Yu Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25(1):502-520, 2015.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--fficieen learning of deep networks from decentralized data. Artificial intelli- gence and statistics, pp. 1282. PMLR, 2017.
Ronak Mehta, Jelena Diakonikolas, and Zaid Harchaoui. Drago: Primal-dual coupled variance reduction for faster distributionally robust optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Debin Meng, Xiaojiang Peng, Kai Wang, and Yu Qiao. Frame attention networks for facial expression recognition in videos. In 2019 IEEE international conference on image processing (ICIP), pp- 3866-3870. IEEE, 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv: / 887.002699 2018.
13

---

Konstantin Mishchenko, Rustem Islamov, Eduard Gorbunov, and Samuel Horváth. Partially personal- ized federated learning: Breaking the curse of data heterogeneity. arXiv preprint arXiv:2305.18260 2023.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. Optimization Methods and Software, pp. 1-16, 2024.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- fional conference machine learning, pp. 4614 4625. PMLR, 2019.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in neural information processing systems, 29, 2016.
Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-coneave saddle point problems. SIAM Journal on Optimization, 15(1):229-25 251, 2004.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. 109(2):319-3))) 2007.
Hung T Nguyen, Vikash Sehwag, Seyyedali Hosseinalipour, Christopher G Brinton, Mung Chiang, and H Vincent Poor. Fast-convergent federated learning. IEEE Journal on Selected Areas in Communications, 39(1):201-215 2020.
Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In 2019-20019 IEEE international conference on communications (ICC), pp. 1-7, TEEE, 2019.
Leonid Denisovich Popov. A modification of the arrow-hurwitz method of search for saddle points. Mat. Zamerki, (8)5:77777784, 1980.
Mónica Ribero, Haris Vikalo, and Gustavo De Veciana. Federated learning under intermittent client availability and time-varying communication constraints. IEEE Journal of Selected Topics in Signal Processing, 17(1):98-111 202..
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34: 4396, 2021.
Elsa Rizk, Stefan Vlaski, and Ali H Sayed. Optimal importance sampling for federated learning. In ICASSP 202 / IEFE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3095-3099. IEEF, 2021.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to datalparallel distributed training of speech dnns. Interspeech, volume 2014, pp. 1058-1062. Singapore, 2014.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shai Shalev-Shward Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catan- zaro. Megatron- Training multi- billio- parameter language models using model parallelism. arXiv preprini arXiv: (tt::::9900000000 2019.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. Advances in neural information processing systems, 30, 2017.
Sebastian U Stich. Local sgd converges fast and communicates little, arXiv preprint arXiv:1805.0976) 2018.
14

---

Sebastian U Stich,, Jean-Baannnn Caan-Bpptsste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018.
Nikko Ström. Scalable distributed dnn training using commodity gpu cloud computing. 2015.
Paul Tseng. A modified forward bawkwrd splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, (6(2):4314445 2000.
Alexander Tyurin and Peter Richtárik. Dasha: Distributed nonconvex optimization with commu- nication compression, optimal oracle complexity, and no client synchronization, arXiv preprint arXiv:2202.01268, 2022.
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan Rellermeyer. A survey distributed machine learning. Acm computing surveys (csur), 53(2): 1-33, 2020.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. arXiv preprint arXiv:2002.06 04000, 2020.
Haibo Yang, Minghong Fang, and Jia Liu, Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11203, 2021.
David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983.
Michael Zhang. Karan Sapra, Sanja Fidler, Serena Yeung, and Jose M Alvarez. Personalized federated learning with first order model optimization. arXiv preprint arXiv:2012.0856: 2020.
15

---

A ADDITIONAL COMPARISON WITH PRIOR WORKS
In this section we provide complexity comparison of ADI against baselines.
Note that while previous compression algorithms address Problem (I), ADI operates with the objective function (4) The difference in objective functions makes a direct formal comparison of the rates less transparent. Additional difficulties in theoretically comparing ADT with classical compression methods arise from the distinct convergence criterion inherent to saddle-point problems, which should be taken into consideration we provide the comparative Table I beloo. Comparison is conducted for a smooth nonconvex setup, which in case of ADI I and MASHA, corresponds the minty assumption. For the sake of clarity, constants specific to the problem have been omitted from the estimates.
well. Nevertheless, for completeness of presentation,
Table I: Comparison of complexity across algorithms with compression.
Algorithm
Communication rounds
Bits of communication
ADI (this work)
1 a M 1
V-7/M
4/2 M vn/M
DIANA Horvóth et al.
2022
(1 + w) VujM
1/2 + 1 + w
VwM
DASHA Tyurin & Richtárik 2022
[1 + 4/V3T
[//2 + 1/vad
EF21
Richtárik al.
2021
1
1
Ea
MASHA [Beznosikov et al.
2022
[+*/ar+]]
|w/ar + +1]
Notation: accuracy of the solution, compression rate introduced in Definition]
1 M number of
nodes, parameter of contractive compressor.
Additionally, we note that EF21 was originally designed to be used with contractive compressor with constant a. Since this is a well-known and practically significant method, we include it in our experimental baselines and present its convergence rate for completeness.
B ADDITIONAL CLARIFICATION ON IMAGE CLASSIFICATION
Our experiments are conducted on the CIFAR-10 Krizhevsky al. 2009) dataset using a RESNET- 18 (Meng et al.) 2019) architecture, with M = 10 clients for federated training. We evaluate each sampling strategy under three representative data partitioning schemes: (homo) an i.i.d. homogeneous split, where each client receives statistically identical sample of the data; (hetero) heterogeneous configuration which clients are assigned disjoint class subsets, simulating non-i.i.d. label distribu- tions; and (pathological) strongly heterogeneous regime, reflecting real-world imbalances through uneven data quantities and skewed class distributions across clients. This controlled setup enables a rigorous comparison of Algorithm under increasingly realistic and challenging federated learning conditions. In all experiments we do not use simplex regularization, i.e. A = M1
B. HYPERPARAMETERS DETAILS
In our experiments, we employed the default partitioning utility provided by the Flower (flwr) framework (Beutel al. 2020 to generate non-i.i.d. (heterogeneous) data distribution across clients. To calibrate the hyperparameters of the ADI optimization method, we conducted systematic grid search over the following ranges:
Learning rate for model parameters (79)::
[1x10-1, 5x 10 - 10-0-3, 5x 10 1x 2 10-
Learning rate for client weights (Y=):
x1x10-3, 5x 10-3 10-22 10-
1x10-1)
16

---

Momentum decay coefficient for the model update (a:):
{0.70, 0.75, 0.80, 0.85, 0.90, 0.95]
Momentum decay coefficient for the weight adaptation (B): {0.05, 0.10, 0.15, 0.20}
The optimal configuration (selected based on validation performance (e.g., final accuracy and conver- gence stability)) was identified as:
% 0.01, Yn 0.01, 0.90, B 0.10.
Furthermore, across all compared methods, we employed staged learning rate decay schedule to promote convergence stability. Specifically, the initial learning rate was reduced by a factor of 5 after the 2000 communication rounds and subsequently by an additional factor of 10 (i.e., 50x relative to the initial value) after the 7500th communication round. Formally, for an initial learning rate yo, the schedule defined as:
70,
k 2000, 2000 & k < 7500,
(k)
70/5,
70/50,
2 7500,
where & denotes the round number.
C ADDITIONAL EXPERIMENTS
C.I LINEAR REGRESSION
To evaluate the performance of proposed method under tightly controlled conditions, we conduct additional experiments on the simplest task. We use the diabets scaled (Chang & Lin 2011 dataset for linear regression task consisting of 768 samples with 8 features and two classes As baselines, we select the communication compression algorithm DIANA (Mishchenko et al. 2024);
for uncompressed weighting method, we use ADI with identical compressor Opt i stic Extragradient (Popov) 1980) for formulation
44. Additionally, we compare ADI with MASHA (Beznosikov al. (022) for problem (4, which is an analogous method combining both weighting and compression. For all algorithms with compression we utilize Randk compressor.
To model different degrees of heterogeneity, we introduce parameter OA [0, 1]. While emulating training on M = 4 devices, we distribute data across clients as follows: the first node receives M + at M observations from the negative class and 1-as positive observations. The remaining M
M-1
data is distributed uniformly across the other MM 1 devices. Thus, 0% complete heterogeneity where the negative class appears only on one device while the other devices contain exclusively positive class observations. Accordingly, or = 0 corresponds to complete data homogeneity.
corresponds to
The first series experiments (Figure 4 compares ADI with the specified baselines under different levels of data heterogeneity (a,, equal to 0, 0.5, and 1). For all compression methods, use Randk with X = 1. MASHA additionally transmits full gradients every iterations. These experiments confirm the superiority of weighting methods: while showing comparable performance on homoge- neous data, ADI gains significant advantage over DIANA as heterogeneity increases. By comparing Optimistis Extragradi ent with other methods, demonstrate the effectiveness of com- pression, particularly in combination with weighting approaches across varying heterogeneity levels. Finally, we present the evolution of ADI algorithm's weights across iterations. We observe that their dynamics can be unpredictable, particularly in the homogeneous setup. Yet this does not lead to performance degradation.
Experiments in Figure 5 compares ADI and DIANA os 0.5 with different compressor constants K (8, 5, 2, 1). This comparison highlights that the advantage of weighting remains independent of the compression level even under aggressive compression as Randl.
Finally, in Figure 6 we verified that ADI weights ultimately stabilize in both complete homogeneity and heterogeneity cases. Notably, in the homogeneous scenario, their stabilizzatiio evolution does not affect performance.
17

---

0.3
04
6.5
comp.)
(no comp.
comp.)
0.4
ADI
ADI
ADI
DIANA
DIAMA
DIANA
MASHA
MASHA
180
200 253
53
268
150
260
250
300
200
400
254
200
transferred
(a) Convergence comparison.
O,1,
0r1y
0.45
8.40
6.7
Weeght mageituru
woott
32-
Node
Node
Node
Node
No00
Nodc
106
130
256
250
302
350
150
200
250
26
200
tranffrre
#bit transfarred
*biss transferred
(b) Weight magnitude ADI's nodes.
Figure 4: Performance comparison for ADI across different heterogeneity levels.
DUNNA 91
DIANA 1C
DUANA 2
43
20 Adta menstated
212
Figure 5: ADI and DIANA with RandK across different K with 09 = 0.5.
Homo (ct), 0)
Hetero (o,),
0.5
0.2
6.5
04
Weight
03
0.1
Node 2
ADI (Homm) ADI (Hetero)
Node 3
Node
Node-4
520 1566
19te
2000
201e
500o 300 000o
#blls transferred
ebits transfereed
#bis transferred
Figure 6: Weights stabilization in homogeneous and heterogeneous setups.
C.2 ADDITIONAL DATA PARTITIONING
For greater completeness of the experimental evaluation, we conducted an additional experiment using an alternative heterogeneity modeling setup. Specifically, we evaluate the same RESNET- 18 (Meng et al. 2019) backbone on the CIFAR-10 (Krizhevsky et al., 2009) dataset partitioned across 10 clients according to Dirichlet distribution with parameter degree of non-i.i.d. data heterogeneity. The corresponding results are presented in the Table 2 below. These results report the maximum accuracy (mean + standard deviation over three independent runs) achieved by the methods under the same number of communication rounds and an equal compression level.
0.3, introducing stronger
18

---

Table Comparison of ADI with baselines under Dirichlet 0.3) partition
Method
Rand 50% Acc.
Rand 10% Acc.
Rand 5% Acc.
ADI
82.6 = 0.24
81.9 = 0.24
82.4 + 0,28
DIANA
76.7 + 0.26
77.1 = 0.32
75.4 = 0,40
EF21
64.5 0.43
64.4 0.41
61.6 + 0.43
MASHAI
63.7 + 0.20
63.4 = 0.21
63.5 + 0.21
This experimental validation demonstrates that even under highly heterogeneous data distribution and a high power of compression (5%), our method achieves strong performance and delivers improved results compared the baselines.
C.3 WEIGHTS DISTRIBUTION ANALYSIS
To investigate the sensitivity of client-specific aggregation weights to the severity of model compres- sion, conduct ablation study RESNET- 18 (Meng et al., 2019) the backbone architecture and the CIFAR-10 (Krizhessky et al. 2009) dataset, partitioned across 10 clients using Dirichlet distribution with parameter 0.5 induce data heterogeneity.
Three compression levels Rand 50%, Rand 10%, and Rand 5% evaluated. For each setting, we report the learned client aggregation weights (mean + standard deviation over three independent runs) in Table below.
Table 3: Final client weights assigned by ADI under different compression levels
Client no.
Weight (Rand 50%)
Weight (Rand 10%)
Weight (Rand 5%)
1
0.019 + 0.005
0.019 + 0.006
0.014 + 0.005
2
0.026 = 0.007
0.025 0.007
0.027 = 0.009
3
0.141 + 0.007
0.139 + 0.008
0.139 + 0.007
4
0.248 +: 0.011
0.244 0.012
0.247 + 0.014
5
0.136 +: 0.007
0.137 + 0.007
0.134 + 0.007
6
0.054 = 0.008
0.055 + 0.007
0.057 + 0.011
7
0.145 # 0.011
0.143 0.016
0.144 0.013
8
0.047 + 0.008
0.062 0.013
0.056 + 0.014
9
0.043 + 0.009
0.052 0.008
0.048 + 0.011
10
0.147 + 0.010
0.124 + 0.013
0.134 0.011
Let us briefly describe and interpret obtained results.
(i) For the majority of clients (e.g., Clients 3, 4, 5, 7), the assigned aggregation weights remain remarkably stable across compression regimes, with variations typically within the margin of statistical uncertainty. This suggests convergence toward a data-informed equilibrium consistent with theoretical expectations that optimal client weights reflect local data representativeness and utility, rather than being artifacts of compression-induce noise.
(ii) Notably, Clients 8 9 exhibit non-monotonic weight adjustments under aggressive compression with Rand 5%, diverging from their trends at 50% and 10% compression. Post-hoc data inspection reveals that these clients possess highly skewed local distributions: each holds samples from only three classes, with two dominant classes constituting over 93% of their local datasets. Under severe sparsification, the reduced model capacity likely amplifies the impact of such distributional bias, leading the weight adaptation mechanism to dynamically re-calibrate contribution levels.
These findings underscore that while global aggregation weights are generally robust to moderate compression, extreme compression intensifies sensitivity to local data pathology, highlighting the interplay between model compression, client heterogeneity, and adaptive weighting strategies in federated optimization.
19

---

C.4 LARGE SCALE PROBLEM
To further validate the scalability and robustness of ADI, conduct experiments the CIFAR-100
(Krizhevsky et al. 2009) dataset, which presents a more challenging, large-scale classification task with 100 classes. We evaluate the RESNET-34 (Koonce) (2211) backbone across 10 clients, with data heterogeneity modeled using Dirichlet distribution with parameter a = 0.5, under three compression regimes: Rand 50,, Rand 10%, and Rand 5%.
In the table below, we report the final accuracy (mean + standard deviation over three independent runs with 10* communication rounds) for ADI and several prior approaches.
Table 4: Comparison of ADI with baselines on CIFAR- 100 under different compression levels
Method
Rand 50% Acc.
Rand 10% Acc.
Rand 5% Acc.
ADI
71.2 + 0.21
71.7 = 0.22
70.9 = 0.26
DIANA
69.8 + 0.19
70.1 = 0.22
71.1 = 0.27
EF21
62.2 + 0.41
62.3 + 0.38
59.2 + 0.43
MASHAI
61.7 + 0.22
63.2 + 0.17
62.5 + 0.21
These results demonstrate that ADI maintains stable and competitive performance even on a large- scale, highly heterogeneous dataset, consistently outperforming prior approaches. The findings underscore the effectiveness of ADI's adaptive weighting mechanism in challenging, real-world federated learning scenarios.
C.5 ADDITIONAL WEIGHTING BASELINES AND PARTIAL CLIENT PARTICIPATION
To assess the effectiveness of the selected compression strategy, we conduct additional experiments incorporating direct compression of transmitted gradients (Alistarh et al. 2017) naive baseline into AFL (Mohri et al.) 2019) and q-FFL (Li et al., 2019a) traditional weighting algorithms. To further investigate the effects associated with partial client participation, setup to the corresponding setting. Table 5 presents comparison results on CIFAR- 10 (Krizhevsky al. 2009) using the RESNET-1E (Meng et al. 2019) architecture, while Table on CIFAR-100 (Krizhevsky et al. 2009) with the RESNET-34 (Koonce 202T architecture across varying compression rates. Data heterogeneity is induced via a Dirichlet distribution with parameter = 0.5 across 10 clients, while client availability is sampled from Bernoulli distribution with parameters p = 0.5, 0.7, 1.0. For every setup runs was conducted with 10 communication rounds.
extended the experimental
6 reports results
Table 5: Comparison of methods on CIFAR-10 under partial client participation setting
Method (p)
Rand 50% Acc.
Rand 10% Acc.
Rand 5% Acc.
ADI (p 1.0)
85.2 0.21
85.7 0.22
84.9 + 0.26
AFL (p- 1.0)
67.2 0.37
52.3 = 0.38
47.2 +: 0.43
q-FFL (p (p= 1.0)
68.7
53.2 = 0.37
46.5 + 0.41
ADI (p =0.7)
82.2
81.6 = 0.22
81.9 0.22
AFL (p = 0.7)
6.37
49.9 = 0.35
4.42
q-FFL 0.7)
65.9
50.2 0.37
45.7
ADI (p 0.5)
99.2
78.9 = 0.21
79.3 00.+0.22 0.22
AFL (p 0.5)
64.5 + 0.31
48.1 0.39
48.2 + 0.41
q-FFL (p = 0.5)
65.7 + 0.29
49.2 = 0.34
45.5 + 0.41
The table reveals several clear patterns. ADI is almost insensitive the compression level, under extreme compression of 5%. However, a decrease in the client availability probability p leads slight deterioration in performance. The opposite trend is observed for the baselines: they relatively insensitive to partial client participation, but their performance drops substantially as the compression level increases.
Overall, the results demonstrate significant advantage of ADI the baselines: in the most extreme setup (p = 0.5, Rand 5%). the algorithm maintains a substantial performance lead over the baselines even under their most favorable conditions (p 1, Rand 50%). This highlights the
20

---

Table 6: Comparison of methods on CIFAR-100 under partial client participation setting
Method (p)
Rand 50% Acc.
Rand 10% Acc.
Rand 5% Acc.
ADI (p 1.0)
71.2 0.21
71.7 0.22
70.9 = 0,26
AFL (p 1.0)
58.2 0.32
46.3 = 0.31
41.2 + 0.33
q-FFL (p = 1.0)
59.7
46.2 = 0.30
41.3 = 0.31
ADI (p -0.7)
69.4
68.9 0.20
69.0
AFL (p = 0.7)
58.2
46.9 = 0.32
41.4 0.33
q-FFL (p = 0.7)
58.2
46.2 0.31
41.6
ADI (p =0.5)
+.20
66.9 = 0.20
66.2 0.21
AFL (p 0.5)
5.34
45.7 = 0.28
4
q-FFL (p = 0.5)
59.5 + 0.29
45.8 = 0.29
41.3 0.31
effectiveness the chosen compression strategy for achieving a strong performance in real-world applications.
D GENERAL INEQUALITIES AND NOTATION
Suppose v; y Rd,, mI, n2 E A and DRL. is Kullback-Leibe divergence. Then, following inequality holds:
8
(x, v) S ||=11² +
23 |lv11
(Fen)
2
| + v/1 < (1 + aa) ||=||| + (1 (1+a*) ||u1
(CS)
DKI(TI, T2) 2 マ || - -2ll 2 || T2 1
(Pi)
Definition 2. Let F IRd Rd and 'D be a compact subset RRd. Then, for any z E Rd we define Gap(z) max ( (FF(2),, z')}. Z'ED
Definition 3. Let || represents the amount of bits required to encode the vector E IRd, b denotes the number of bits per floating point value, and d is the dimensionality of the problem (i.e., bd = || Then for compression operator 2 we define the expected density of compressed vector
(()) bd
Pw
E AUXILIARY LEMMAS
Lemma reflects the general fact from the theory of saddle point problems.
Lemma 1. If a function f(x, y) : X' x y - R is convex w.r.f. x and concave w.r.t. y, then target operator F for the min-max problem min max (fx,))} of the form
(=)(z,) F(2) -V fx(
is monotone e.i.,
(F(#1) - F(z), 22) > for all 21, E Z =
Proof. We start from the definition of monotonicity, given in the statement, and utilize the convexity and concavity of
(F(z1) - F(22), 22) (Val(er,11) V f22,
x22)
- -(Vy[(2113)) - Vy/( 12), 1/2)
21 - x2) +
12)
(VV=((r2V2))222 (-V (2),,,))), 1/2 v1)
(
((n,,)) f(22,01) f(=1,12) f(
21

---

+f(22, (x1, + f(22, v1) - (22, (2) 0.
The following Lemma (L. (Lemma in (Alacaoglu & Malitsky, 2022)) justifies the interchange the maximum and the expectation operators, which is crucial for transitioning from the descent lemma to the actual convergence criterion the main theorem.
Lemma 2. Let F {Fk]kz be filtration and uk a stochastic process adopted to F with E [ux++ [FF]]
O. Then for any K E N, E Z and compact set D C. Z the following holds:
E
max ZDD
(uu+1:2) 2)
S
max ZED
2 - =1|2 +
Σ
B Blluu+1ll
(5)
Proof. Let
Zas Uk+1
Uk + u1+ 1. Since up -F Fa-measurable, Fi-mmasurable as well.
Then we write
1b6+1 =1|² = |11| - 211² + 2(ux+1, Uk - 2) + 1|2+1
Summing over k = 0, 0, .....,, - we get
K
K- 1
2(4 vk) S 11:00 - =112 + Σ
|
k=
k=0
Maximizing and taking expectation we obtain
K-1
K-1
K
E
max
( 2)
Σ
(u++1, vw)
- max
2
+
E
1
2 ZED
2
==
R=0
Finally, due to F-messurability of and by the tower property of conditional expectation, the second sum on the left-hand side vanishes. concludes the proof.
F MISSING PROOFS
Now we are ready to start the main analysis. We proceed with the descent Lemma
Lemma Let Ya 79 = Then, after K iterations of Algorithm ? solving problem the following holds:
27(F(z ) s (2DKI(T, 2D ( k2))
+ (110 0112 110 - 0113)
(27a(F(2t) F(s*-1), 2²
27(F(2 (1)) - F(=*), ) x -xtt2)
|1a
- =1122 11k 0
+2 111 + 2 2021 11-
8 π
gk
where z
and F(**)
-px))
Proof. We proceed with algorithm steps evaluation.
Mirror descent step provides:
0 (- Veb(m+t)) Vv((**), -
10t , x x1 + DKI(T, x²) ( D DxL (n a
Rearranging it we reach:
DKI DKI(T, DKI(T ,²t) -/00, nttl/
DKI(T,, DKI(akk m 7(1 + a) x
22

---

tyalp"-1 18 π xb11)
DKL(TT, x²) DKL (TT Th m²h) 7/0", "0"",. - x
-nulp" -p²-1, ,T π 1
DKI(TT, -Dxr (TT k-1 1
7/p" -p n8 x xh+11
-7(ptt1 , -ー- -=*+11 -a/pp"
p² 1 15 πT
rallp* ptp r - n bt1)
(6)
0 update rule implies:
110k-1 011
1 011
10 1- 2(0 0h, 0h -0:-0 0)
| 0112
10
1-122 2(0 0h gu+1 0)
I10| 0112
10++1
1-1 (g 0h+1)
110t 011
100+1
0 +2y(1 + ag gh+
(g A 0 0h 0h-1)
|10. 011
1 0²11² 27 0- -ktt
(2 g 0 - g
|10 - 011 | 1-112 (g -get1, , gh+l1
+2> 0 gk+l) 270/0"
g gh)
+2 gh- oh - gh+t)).
Summing 2 and 7 we get:
2 2D (T,, n &+1) + 110011 - 0|1
$ 2Dxx (T,, ) + 110h - 0112 2D k 1 k+1 x5
-110
0*1
27 k+1 x n x + 27 (g² g t+ ,0 gh+l)
27(p b+1 π - n k+1 + 27 k+1 gk+1)
2700(1 - pp k-1 , ) + 270 8 9 b-1
, gh)
-x0r(1) x- n π k + 27a - g 1=1 0h g2+t2).
0 T
gt
Now we rewrite last inequality using
and F( =
-pp))
2D (T, x k+1 + | 8|1
< 20 KL x²) + 110 - 0112 22 k hit xh) 110 0²1p2
+2r(F(22*) - F=(xt+)), 2- 2 - 27 (F *
+27a(F(2*) F(z (1=k-1),2 =/i 22a p111, n n xtt) + - 0r
-
gh+1).
Pinsker's inequality
and
with 8 2> provides
2D 2Dx (T, (+1) + | 1 - 011
< 2Dxl -²) + 1|0t - 012
n k+1 - n 2112 1|oh+1 - 00212
+ +2x(F(z*)) (1*++),, ), 2 - *k1) + 2 F 12 - 2111)
+ +2ya(F(z*)) F(a* k- ) - 2/
+2a721p"* -1= 1 n +t11
+2a7 219"
x 1|2 10 1.+1
Finally, rearranging brings us to
23

---

27(F(zht1), ) 2ktt1 - 2)
(2DKL(T, - 2D 2D (T,, n 1) + (110 - -112 01| 110h - -0113)
(270(T(22) [(==11 1)-)) ),, - 2 27 (F F(=*), =- =
(1 2) | **1 (1 (1- 2 1100t 1911
+ +200 - 11-1112 + 20 - gh 11-
F.1 ANALYSIS EXACT LOCAL GRADIENTSS SETTING
For the subsequent analysis, we need recursive relations for the oracle distortion terms. For notational convenience we introduce o² E f
1
. E
Lemma 4. Let Assumptions 7 and 2 hold. Then for iterations of Algorithm with unbiased
compressor 7 Q and exact local gradients holds:
w $ (1+
6
aa2²
Blbb
-1-111++22 +2
gh 11-111
1| x 11-
M
+(1 (1) + Fw
(8)
Proof. We begin by using the explicit update rule of clients' local state.
M
M
#
El
n111 = Σ BIJa
BBQ
-h n )1?
1=1
M
f f1-1) +
n - --008-11111-- -n
E
1=1
(1+02 1)
Σ
E | 8 11
+(1 + 02)
Σ
j
11
-20 -1
We estimate the first term:
Σ
E T
V
| (.'') 1[
i=1
M
+2
IE (
-. (
1=1
2
Σ
Em! Vf
i=1
M
+2 Σ
E π
o.. - (e |
M
M
2
Em
2.2 L ||@t
- gh ---211
+ 2E
π
k-
2 2
i
i=1
24

---

M
2
|| 0 - -8--11"
Σ
"
. L + 2
x 11-
1=1
M
21E 0
0 10
Σ 1=1
7
22
L3
+
2 1| -I
(10)
Where (i) holds due to Assumptions
and
We can bound Σ Bxt² L3 using condition π
A M-1 n Q&i where Qar
{x
E
R
0
v M } and E [1;
M
M
2
L
S
L2
T
S
L
max
||=||
ZE M- nQN
1=1
=
L
a 2 M
M
+
a
M
M
4 27
Q
2
M
+1
M
K L
Q
2
M
+
M
L
Q
2
3M
L
30
(LI)
M
M
Substitution of
11
into gives
10
M
M Σ
E
E a [V((t) -
aT?
EE 0h gh 01-11 +2i 1, -
1
(12)
M
Then we evaluate the second term of 9
RHS:
f fk-1 - BQ - ho 1 1| l|?
E
- | - n 2 + B 11 jk -1 - 18-1)
||
2E ( - BB2
7k-1 -1--h-11) n₂-1))
< p 1ーー - || + BBWB 574-1 1--1-hhh -/ k-1
23 7k-1 11
(1 + 32w - 2
h
(13)
Finally, combining
p with 12 and (13)
we obtain:
6 aT.2
* s (1+
E 1100
+ 0
+i.22 1| x 11
M
+(1
+ Bw - 2, Σ
8 - 1 |?
1=1
(1+ 6 6
aL?
M E El000 1
0r 00-1112 21--11+222 ++222B 1| -²" 11
+(1 (2++0)((1= + 32 23 k-1
We continue by examining the global oracle distortion evolution.
25

---

Lemma 5. Let Assumptions 7 and 2 hold. Then for iterations of Algorithm with unbiased
compressor 7 Q and exact local gradients holds:
rh - (1+
(2L'R 110 0h 10--11²- + 2M 2 | - π - 11:)
+ +11+ c1) (u+ 32 23) - 3² w -w-1)) 1))
(14)
Proof. We begin with the explicit global estimator update rule.
M
E ft
11
E
jr 1-1
2 j
11 11-11)
i=1
M
E
(i² - f +
pk-i1 -11 -
3
2 i 180-11111 11 1
1=1
(1+ ci 1) ) gk - - 111
M
+ +1+ pk-1 k=1 3
11-11)
(15)
Then we examine first term on the (15) RHS.
As all Jt are I-Lipschitz continuous (Assumption) 2) the weighted sum M Risi is I--Lipshitz continuous well. It justifies (i) in following inequality sequence.
E jk
jk-1
11?
E
fith -. v.
E
Σ
(V - v)i(0--1)) + ( m 1) ((k-12)) o
2E
T (V V.i(0n
M
+2E
Σ
(m क: 1 (SS(O--1)
i=1
2T.²
|00
0² 0k-111 + 2F
Σ
k-1
2T |
8² 1=-111 112
+ 2F
ب k-1
11
E g+
8h 11 112 + 2 E
xx
112
(16)
Now we concentrate on the second term on the 15 RHS:
E
jk
k-
Q
pk
h
k
2
E
jh-1
bb
+ B
Σ F7h 1b4-11
M
2/E
7t pt-1- b--1
O1F 2k-1 - n1-1)
26

---

fk - 8 || + B 3p( + -ww - 2,31R |a- 11-1
(1 + 3 23) + www
(17)
Plugging 17 and [6) into 15 yields:
(1 (1+ (21,'R) |10 -ph-111 + 2M 1| - -
+(++c) (u (1+ -2 25) B x
The last preparation before proceeding to the main theorem is evaluation of global state dynamics.
Lemma 6. For iterations of Algorithm [ with unbiased compressor [ 2, the following holds:
27 Bll" - و --1 11 = (w - 1) (w + (1 3)2=* + 4y (v + (1 3)2
(18)
Proof. Let us again begin with the explicit global estimator update rule.
Blg 9 1111 1|2
2 h + Å
h
Å
1112
M
M
M
= 2
Σ
(h+
1 + Σ
hh -nt) - Σ 2
1
76-1 - -17 115-1) 1)
1=1
1=1
M
M
M
2
27
Σ 1=1
2 (1, -
+
Σ o
( ( - -1t - Σ 0 (j+ ( 11/-1)
i=1
1=1
M
M
2T
Σ i=1
2 (1. - M1 - (1 - 3)
2 fk-1 - n
t=1
M
2 J
mt) -
- 4 -17(118)77
2
Σ o (i--1 n -/-1)
M
(19)
Terms differ only in their indices, which makes it convenient to analyze them separately. Here we utilize cross- cross-device compressor independence and unbiasedness once again:
M
E
Σ o f
M²)
Σ
E
ft
mt)
+
Σ
E
n²) -1)) (
1
WE
ng4
11
2
Σ
E
ft
nt) 2 (1) - -h²) htt)
1=1
itj
M
W
>
E
3
h
+
7tt
h -
1=1
M
+ jk 1 ||
(w
1)
Σ R
1=1
(w 1) k + k.
(20)
Substituting (00 into
19 we reach
"llg* 1 2 1) (w + (1 (1-1) 18 1) + 472 (ut (1- -
k
Finally, let us introduce the convergence criterion. In saddle point problems under the convex- concave setting convergence measures in term of the Gap function (Definition 2 Since ADT
27

---

incorporates possibly randomized compression operator Q. the convergence guaranties for it is based on [2)p This guaranties are provided by Theorem [
Theorem
1 Let Assumptions
7 hold and a - 3 - w H 32> w? N 7y2w.
= 70 7 S To = min 2L
A A AM n Qui
96
14
4M and L 12
where Qa for E RR S 23 S ). Then, after K iterations of Algorithm with unbiased
compressor 7 Q and exact local gradients solving problem (4) the following holds:
V
E [Gap(Zx)]
2
where
V
E max RED
4D
4DKL(T, + 2110' - 0112 + +> -F(="), ===))===))) 2113
112 1|] and 2x
H
+ N
j
K
k=
k=
k=1
Proof. We proceed with using the unbiasedness
of compressor Q:
E [F(( = EE
g
+ - E
[ ht
M
Q( h
2
det F(
where = convex with respect to 9 due convexity of all f.. At the same time. f is linear, and therefore Vof(O, concave with respect to all ग.. Then, noting that F(z) Vv we invoke Lemma | to establish its monotonicity.
M Ft
=i= TH ((O Considering f(0, π) = -E (() we note that it
Our objective to obtain convergence with respect to Gap(z) max (F(c)) - x)} Hence, the .ED
next step is conditioning the result of Lemma 3 on 2* ++1, using and summing over le 1 to K,
27
((2k+t), 2 2)
K
(2DKL(T,, ) 2D KL (TT, x xbt1) + (1le - ||ght1 - 0)12) -1|2-1188
+ (2T(F(2*)) - F(2h-1), - = - - 27 (F F(=*),
-2t11)
2 [lnttt - *²1 - [11h - -²
1
- -1 + 2>2 - -g* 1
(2DKL(T, - 2D kL (T,, n x(1)) + (1|01 0|12 1|0k+1 - 0113) + (2 - F(=9), 2t) 22 (7 (22K+1) F(z*), xk+11)
K
(=( - F(= ), 2 x
K
k++l x
2 -1oh+1 -0#
1
2
k=
22y
1112
2" g g111
Maximizing obtained inequality over compact set 2 E D and taking full expectation, we get
K
27 E
max RED
Σ
(F
201
2)}|
<
max (2DKL(T, - 2D (TT, π K K-1)) RED
28

---

+ +(10' 011 - | - -013)
+(27(F(2)) - F(="); =z²>
(F(( ((tx - F(x*), - 2 +)1
K-1
+ (y(F(22 (2 - F(2 1), 2 2 }
k=1
2 | - * - _110 0811
+2 llp 112 + 2 - s4-118] (21)
Several next steps evaluate different terms of 21 starting with the LHS. Due to monotonicity of F.
K
K
(F(*))
(f(:), -)) = K
F(:); K
k=1
k=
Maximizing over we get.
KGap (EK) S max
Σ
(F( 2t
(22)
sED
We apply Lemma 2 to bound the first sum on the RHS of (1
K
(F(c -F(ctt))(((ttt))) ((zttt)) 2 -- 2 }
2E max
ZED
1=
2E
max
(F( - (())t1))
- .2) }
FED
K
E (1 (F (z+1) - -((htt)) 1
K-1
}} - 0
= 2F
max
(7 (F( -
RED
k=1
K-
max
(11za- - 2113) + 7?
Σ
E F( - FF
(23)
ZED
We continue with evaluating of the last term applying properties
2 of unbiased compressor Q:
F(*) 1(
+
Σ i=1
= E
4z
M
h²:)) (ft -1t) ?
2
E
Σ
20F
M
Σ E
oou - nb>)|² +E
- fa - 124
=
M
E ( Q1Fat - ~Z
- -b+)
2
1=1
<
Σ
87t n111
E 1 1/ |
(24)
29

---

( π
Finally, using Pij.
the definition of =
and choosing za = z² 2, we estimate
max =ED
2D (2 (T) + 110 011²}
2
max || - T T||2 + -110 012)
= D
max || =1|2] =ED
(25)
Using notation 5² E 5 hb/l 1 = we derive:
2 B $ 11
and combining 23 24 with 25
K-1
(> (F(( F(z 2 - 2 ,tt1)} }
2 max FED
K
S max sED
2D KL 2Dxx (T, n + 110' - 0113 + 72
(wm ot))
(26)
k=
After that, we estimate
21 -p -p=-111 1|2 in 21 via Assumption
!
27² lp
p²
1 12 S 27 2 - -0t 112
(27)
Finally, we use
18 to evaluate the sum:
27 2
Bllg* 11
K
K
4
(w - -1) k + 2 (1 -1-10 -3) Σ
[(w - 1) 1)w + x-
k=
k=
K
K
4/²
Σ
[[w 1)w* + w/1 4 - -3)
[( - 1)w + +
k=1
k=
[
= 4 + (1 -9)2)
Σ (w 1)w* + w
k==
-4 -B)[(w - 1)w* + {
[w - 1)w" +
(28)
Substituting
(26 and 22 into
we get
2yKE [Gap(z [x])]
E
max xED
(ADKL(T,Tt) (+) 2D 20x( k(+1))
+ (2110t - 011 - -10041 - -0122)
+ (2>(F(=))) - F(="), =- - 2²)= 27 (F(( [(+)+)) - F(=*), ) =- -,=-=*+1 =k+1))
4-2 - -3][(w 1)w* + + - 1)w2 +
2 K
K
(ww* - v²t + 4 (1 + (1 B)²2) Σ
[(w - 1)wx* + #
k=
k=0
k+1
n x1
2? -2 M2) 110k+1 1
Using 24 ww x² 2 and 0 < 8 < 1, and introducing
EK
max (4DxL (T,, x 2D (I, x xk+1)
meb
+ (2100' -012 - |10*11 +1 - 0
+(27(F(2') F(2²), 2¹)
30

---

(F (2x - =F( - -= =x{11)}
-1 - B)[(W 1) K + +u - 4-2[(w - 1) + +00},
(29)
we can rewrite:
2 KE [Gap(Ex)]
S
E +
9w 2 + +
k=0
K
(1
1- 2-22 mi3) 110+ -291]] (30)
+
m
x x+1
* 1
2
Jom1
The next step is summing 33
kk=
K+1
H
88 N (14)
K+1
27 KE [Gap(Ek)]
Σ (Hw* No²)
k=
K
K
< E
K
+
1 u +
+ Σ
&w - 2
1=
[N + ai) (0+ 23) f
K
2NM | - 2H - (1+)))) |1 - 1
Σ
2
k=1
( 22 - (1 ((
Gat.
M - N aT 21. |10h - [d1p]]
By rearranging the terms, we obtain
K+1 (Hu + No*)
2₁KB (=p)(
2
E
E K
[772 N(1 +1)+ 32 rt
K
[9w? + H(1 +02) 23) + N(1 + +=),8((0 (w - -1)] w
k=0
K
1 22 (1 to7)) {
-| 1111
-
2
k=
2y Mī -
GaL2
N (1 a 21 11gh 0 {pP] (31)
M
Considering the respective coefficients of ||0b+1 gh || following restrictions:
* ll? w and b² we derive the
2 + GoL? M +N (1 (1+ ( 2L2,
21 -NM
(32)
H 2 2wy +[1+ N 1),
+(1
We now turn to selecting the free coefficients to satisfy conditions inequality on N. we set
32 Beginning with the last
7-2
C1 = 3, which yields N
(33)
B
is sufficient.
31

---

With this selection the third restriction in (32 transforms into
7y2
H (1+ o2) fw - 28))
9wn 2 + (1 3) (w 10 1).
The choice
3
32
02
3
guarantees sufficiency of H
(34)
Then, utilizing (4) and
33
we rewrite the second inequality in 32
1
3
+ - ML ML + )-
2
[1
2
8
This poses constrain on 7:
7 V 2 192w L + 28M
2L V 96w 14
(35)
Finally, we examine the first inequality in 32 Using
33 and
34 we derive:
32n²
GaL
7y2
N 2y ML2 +
(1 28 )
+
(1 8 2L
2
M
B
γ. s
2 24M + 576L2 3-3 M 2-
(36)
2 4M + 576 1.2 + 28
M
By choosing
7 = min
2L V 96w + 14M V 4. 576 ow L2 + 28 L2 M
(37)
and taking
35
36 into account, we satisfy
32
Consequently, with the definition EK
29
substitution,
31 transforms into
2- KE [Gap(Ek)] +HH + K+1)
E
max (4DKL(T, 2DxL(T, xe ( x(+1) RED
(2110) - 0112 110k+1= -013)
(2T(F((2)) F(2"), 2 2²) (x(F(z f(2x),, 1---2 x===x+1])) x
4/ B)[(w - L)w* + - [1r1-1 - 1)w0 + +00
K
w N v
Σ
27 2 1M. 0h11.
(38)
k=1
To proof the convergence we need eliminate the (F F(**), - =x+11 term
-
F(2 K-1) [[[F(2++1) - F( ((=KK) >12 + ||= - x
(1)
$ 2 F(2kt1) -F + 27 2 -F2
+10 11+1112 11222DKK(S a xx+1)
(0)
& ||0 gk+1112 + 2D2x (T,, न k+11) + 212 - 8K12
32

---

1 1) (w*+) (1 3) + 47² (o +11 (11 -)
+2y 2
(39)
Where (t) holds by (CS) and and (ti) follows from 24
and
18
Then, the choice of H and N 33 along with 39 provides
2y(F(( F(z*), ), 2
2
1 1
-(Hw + N+ - 2D (T, K+1) 1 0112 -
(40)
The substitution of 40 into 38
concludes the proof.
Theorem 1 yields further bounds on the number of communication rounds and the amount of information transmitted from the clients to the server.
Remark In our analysis we assume that compression does reduce the size of & below that of the scalar (ie., qu ). Hence, the cost of transmitting Si be upper bounded by that of Di. This allows us to ignore the communication of fo in the O notation.
Corollary 1 In setting of Theorem 7 Twith 7 Yo. Algorithm 7
with exact local gradients needs
of Luol + YM +
(V
aw
))
o
+ w
M
iterations in order to reach e-accuracy with respect to E [Gap(Er (xx)], Additionally, it requires
( Luvta + LM
aw + +11) )
bits communicated from nodes the server.
Proof. The result of Theorem [ directly provides the first bound.
Given Remark 1 to obtain the second estimate from the first, we consider transmitting Å from the nodes to the server for 1,2,.... M. This corresponds to sending M dbgg, bits every iteration. We omit constants M. d and 6 under the O notation. As for qus note that for practically relevant compressors (Beznosikov al. 2023a) it holds qu I It concludes the proof.
F.2 ANALYSIS STOCHASTIC LOCAL ORACLES SETTING
The convergence proof in the stochastic setting largely mirrors that of Theorem I Nevertheless, for the sake of completeness, we present it below.
To streamline the exposition, we slightly modify the notation: b E 1
w
EME h! Lemma 6 remains unchanged under the new notation. Lemma under- goes only minor modifications in the proof and takes the following form.
Lemma 7. Let Assumptions 7 2 and hold. Then for iterations Algorithm 7 with unbiased
S
compressor 7 Q and stochastic local grudients holds:
* < <1++55)
aL?
R. 1|0
0h 0h-1112 + 00-1112
|| Th x111
M
4a²
+(1 + c2) + F2 - -88)
0²
(41)
M
Proof. We begin by using the explicit update rule of clients' local state.
M
M Σ
k
Σ
i.c - 14/112
Jis. - h k-1
32( n
i=1
33

---

M
Σ
(fite - -Pite)) +
[k-1
32 - -n. 1) ||²
1=1
M
(1+ )
E fiie:
Jiki
jk-1
2
y=1
+(1 02)
B |hee
1 ph-1 -
h )|p
(42)
We now estimate the first term:
M
E
F.EL
pk-11
Σ B V[., -. -
Sog. (0 1|]
M
Σ
E
F..s (
- -x, - (V - ((()((()))
(((h-11))
(()(())1)) ||²
M
f... (0*) (()) (म - Viie - -, (F((((-11)) ||
Σ
E
M
-. (i !|2 f
+
E
(
(43)
The second sum of term of 4
43 was evaluated in and
We proceed with estimating the first
M
k Si.s (0t) - -( - (T.5-1 PAA--VJec V.i,e (iie -,,--11 (1:00 ||
M
T T Vi. N. -/ "
2
E
+2
Σ
k ---Viiie
(0 (Oh-1)
...
M
+ n (m
12
)0²
M 4a
0² 4a²
M 0².
(44)
M
i=1
Substitution of
(11 and (44) into 43
gives
Σ
M
R
<
aL2
E
|| - 8z 01-1 + +2i.3 - 1|
+
4a² M
0². (45)
M
Then we evaluate the second term of 2
RHS:
pk-1 - 11 11-11/1 2 i.6:
E
pk-1
11 - 3
E
ik-1
h/ ||
| + 3 @1
7k-1 1- h 1x-11
i,g.
2E
[ - h 1,300
pk-1 1-11 h: 11-11)
1.gi
j h 2 + & p -hŞ n..11 1|= 2,311
E
11-
34

---

(1 (1+BB 2
(46)
Finally, combining 42 with and (46) we obtain
6 aa²
w s (1+
E 1
01-1112 21. 1|
-
M
+1+ + B - + 4a
M 0².
Lemma 5 likewise undergoes a minor modifications.
Lemma
Let Assumptions ! and 2 hold. Then for iterations of Algorithm with unbiased
compressor 7 Q and stochastic local gradients holds:
u² (1+ (2T,7T 1|0E 11= + 2M 1| x== 11²) (1+
+ +1++a) R
32 (1+
23) BB
(47)
Proof. We begin with the explicit global estimator update rule.
E
jt
h"
E
ph h² k-1 3
2 pk-1 11 11-11)
i=1
E
(pz jk-1) )
jk-
k-
21 -
(1+ ') ) E gh - j4-1l
+ (1+c))B
pk-z h
8
2
2
h
For the first term the 48
RHS (6) remains unchanged and we concentrate the second term of
the 48
RHS:
E
pk
k
Σ
Q
sh-1
i.e,
E
gh-1
2 1(/-1) + BºE
M
25E
pk-1
b
(f 1 - n
7k- 1 k-1 2
32 (0 k-1 + (w - 11)= -2,1E g 1 6-1 1|2
(1 32 - 2,9) + 82 Pw (w - 1).
(48)
Plugging
and 66 into 48) yields
s (1+ (2L'E 0 - 04-1112 + 2M - x
+ + + (1) (0 11 + 23) - B2 ww
We are now ready to proceed to the proof of Theorem 2, which is the main result for the stochastic local oracles case. The structure of the reasoning remains the same in the proof of Theorem
35

---

Theorem 2 Let in setting of Theorem
7 additionally Assumption 5 holds. Then, it implies
V
64a2
E [[Gap(zk)]
+
o²
2
M
for iterations of Algorithm 7 with stochastic local oracles.
Proof.
For the sake of consistency with previous notation, we relabel the full weighted local gradient f (0*)) and its stochastic estimator fh& Ve.c (0*).
As in Theorem we proceed with using the unbiasedness
(2) of compressor Q:
E [F(=
E
= E
(
ht + 1i=1
+ Q h
def
F(=*),
p
where
E
= 7. f((K)) And Lemma
again justifies the monotonicity of F.
The next step conditioning the result of Lemma to K:
3 on 2 using 1 and summing over i = 1
27
F(= (( 2
(20xz 2D ( (n1) + (110 - 011 -110t+1 1 0113)
+ (2y(F(x*) - F(=* F(zk-1),< -2-1-------- ) 22 - - *)()) ),
2 |n *111 - _10At1 8²11
+2 - 112 + 24 2g g¹ g11
(2DKL x²) - 22
1 (TT, 1 x x+1)) + (110² - 0|1 - |10k+1 - -011) + (27(F(==*) F(="), 2 - 27 ([= - F(=*), )₂ 2k+1)) ), 2- -
2x (F( F(2ht1),
K
| 1 - 111 2 =1ght1 - 1/11
A=1
+2
11th
11 + 21 nd 11-1
Maximizing obtained inequality over compact set = E D and taking full expectation, we get
2 E
max RED
Σ (F(2*t1), 2+1
2, -2)
2)}|
< E
max
(T 2D K ( ( -11) LED
+ +(10' 0112 - 100+1 - 0013)
+ (22(((())) - F(=²), - =t)
(=t))) - F(=*), - -2k+1))
2 (F(222 (11)+) F(2a11), )),) 2- 2x x+1) }
K
| x * 1 11 - -8²112
2
1=1
+27
1|p*
p
k- 1112 + 2r - -9" [p]] (49)
Several next steps evaluate different terms of (49 Inequalities and 23 remain valid. We continue with evaluating of the last term applying properties
2 of unbiased compressor Q and its
36

---

independence from stochastic local oracles:
fk
+
1h
En= 2 h1t)
(( - F(
= E
pb
pb
R
21P - -,,) (5th -1²t)
Σ
L - -n²)|² B 1 x 11: 1
M
2
Σ
( (o(Jis. - -12),, - -1xt)
1=1
E
fr.s
12/ 12 -E 10 12th
(50)
0
Finally, using Pi
definition of 2
and choosing 2a = x1 gktl we estimate
max 2D 2Dx 7
110 0113}
2
max EDD
||
T 1|| + 110 013)
|| 21|² }
max ZED
(51)
Slightly changing old notation wk = jo
h* || w Eiz EF lis. n²ll and combining
50 with
5T we derive
(1 (F(#++1)- - F(2k+1)) - 2411) }
2E max RDD
K
$ max sED
2D KL ( x²) (++)+ + 110 - 0112] + 72
(wr* rt)).
(52)
k=
After that, we estimate
2*²
- 1 44 via Assumption
!
2y² 1p
111113
12 < 27 Mī - 1
(53)
Finally, we use 18 to evaluate the sum:
27²
Bllg* -
www + w + 21 -8)2
ww + x8
K
K
4-
www + r4 + -8 8)2
www + r
k=1
k=
4 (1 + (1 - -3)2)
Σ www wit
kk=0
21 3) ww + k
17 (ww 9 + I...
(54)
Substituting
54
53
52
and
22 into 49
2yKE [Ga[Gap( 2k)]
E max ZED
(4D n 2DxI(TT, *k+1)
37

---

+2110' 012 -110 - 8113)
(2y(F(=)) - F(="), 2²) 22 (F((F( - ),=
21 B//w K + + 4-² /// + r1]
K
Σ (wor (4) + 4 (1 + (1-3))
Two + vt]
k=
k=0
K
2 1|
k+1 π 11
1 2
- 27 27 Mi3
-091]]
Using
50 as www.
x 2 0 and 0 < 3 < 1, and recalling
Ek = max (ADKL(T, T²) 11DxL(mm x+1])
=ED
+ (2| 0|1 110 0/13)
+(27(F(2²) - (
x- - 2²))
(2x(F(x F(z*), =
- --7 - B) v + 1kk - -472 + +20,
(55)
we can rewrite:
K
2 KE [Gap(Zx)
S
E
E +
Ouo O u + +
k=0
+
K
a k+1
x* ||
(1
-222Mi²
liaht1 - 0212]] (56)
2
Am
The next step is summing 56
Σ
K+1 k=
H
+ N
47
K+1
2y [aap(Zk
+
Σ (H + Nv
2
k
K
< E
KK +
[9w>2 + 77 + Σ
[1(1+ + BRw -23)
k=0
k=1
[N (1 2,8 + BBw"))]
1 -
(1 -NNMi + t
|| x111
2
MT? - H(1 H(1+
GaL2
N (1 + - 21.2 (1+
110ht1
|10ht1 -1 08(22]
2
M
2K d².
M
The subsequent analysis unaffected by the additive term setting and fully mirrors the reasoning of Theorem | starting from Equation (11
Hk o² introduced in the stochastic At
Corollary provides bounds on number of communication rounds and transmitted from nodes to the server information in stochastic local oracles setup.
38

---

Corollary 3
In setting of Theorem
with y = min (70.
VM 1200"
Algorithm 1 with stochastic
local oracles needs
O 52
o2
a
+ Lu + LM
(v
aww M
+ w
)1)
M
iterations in order to reach e-accuracy with respect to E [Gap (xK)]. Additionally, it requires
o (
[
[iw\'= LM L
(v aw
M + +1)])
M
bits communicated from nodes to the server.
Proof. In stochastic local oracles case, guaranties in the Theorem are affected by addi- tional irreducible term ? 646?u² o². In its presence, optimal stepsize ? transforms into 7 64n"=" o² and makes further analysis similar This choice yields 2rK M
M
min 7o. 1288"="o"K to the proof of Corollary
V.M
F.3 ANALYSIS PARTIAL PARTICIPATION SETTING
We reduce this case to analysis in exact local oracles settings in Section F.1 by claiming that multiplying the compression operator by the 3, with ry Bern(p), yields another valid compression operator. It remains unbiased, while its compression rate is scaled by factor of p.
Corollary
In setting of Theorem
with B = E. = 32-²
7 T 70
=
7p = min
it implies
2L
96 +14M (7)
4ML +576 #1
Gaap(Ek) < 2
for iterations of Algorithm with partial participation.
Proof. We consider Q' Q and utilize independence of 17 and Q to write
E
((2)
E ||@(2)]1
! p B1[((2) E
0 1
(57)
p
Independence along with guaranties the unbiasedness of Q' as well:
E E Q
==" z. P'
(58)
The established properties implies that operator is unbiased compressor with compression rate w/ This enables the application of Theorem and finishing the proof.
Given Corollary in partial participation setting we establish the following bounds. Corollary In setting of Corollary 4 with 7 = Ypp Algorithm
with partial participation needs
(
i
8/2
L L
(v
(v
a
+
D)
Mp
p
iterations in order to reach e-accuracy with respect E [Gap (Ex)
Additionally, it requires
1/2 + +.M + L
+1))
o i
(V Mp
bits communicated from nodes to the server.
Proof. Proof in this setting completely coincide with the proof of Corollary
39

---

G ANALYSIS IN NON-CONVEX SETUP
In this section we conduct the convergence analysis under relaxed convexity Assumption Introduced further Assumption 4 is inspired by the minty assumption (i.e. existence of such =* E R that (F(z), - x²) 2 for all 2 E I)), traditionally associated with non-monotonicity in respective
literature Dang & Lan (2015): Mertikopoulos et al. (2018): Kannan & Shanbhag (019))
Assumption Let there exists a point 0" E R such that:
M
n. VV(0), 0r
Σ
Tif((0)
Σ T Tof((0"), for all E Rd, AM-1
We note that in our setting due to the linearity of objective Σe (() with respect to weights π transition the minty assumption is complicated. Instead of it we use Lemma g
Lemma 9. Let Assumption holds, then for operator F(z) = F(0,T) = (E V the following holds:
(F(2) =;="),=== =²1
"="),=="""" 2 O, for all e TRd and n, n' A-1
(59)
where 2 = ('), TT,
Proof. We explicitly expand the expression - ((=))
(F(z) - F(2 "=="");=-2"""" 2'²)
VV)(0) 0 0-) Σ (fi(0) fi(00) (FL -T/)
M
M
M
f((0)TT - Σ f(00)
Σ (f((0) f((0)) (Tr -
1=1
M
Σ (fi(0) f((00))
Lemma 9 allows to pass to the analysis with non-convex function f() and consequently a non- monotone operator F. Moreover, it enables to take into account naturally convex structure of the objective function Σ fi with respect to the weights which is also reflected in the convergence criterion presented in (5) and written below. In (5) we recognize the part of the Gap operator corresponding to while with respect to the parameter & the criterion involves averaged gradient norm.
M
W
E max
Σ
f((0))
7
+
Σ
V
-0- )
M
1
B n
k+1 n 11 +
E
(((A) K
K
K
32
Where 7k =K= E 1
k+
k+1 and n. vf((0)
~
[ VT.
K
Theorem provides convergence guaranties with respect to W under relaxed convexity Assumption
Theorem 3. Ler Assumptions
2
4 hold and a 1, B = w
70
$ m
1 -1
min i (48(17 2Mw2))
1/2
2448 aw 3 L2 + 26 + 16M
J.A-
A= AM
Q., where Q.M {x R 0 < v; 3) Then, after K iterations of Algorithm
1 with
40

---

unbiased compressor
Q and exact local gradients solving problem
4 the following holds:
1
W
E
max x'EA
(2DxL(T', + F( )( 2' =1)) + |10 112
2
K
Σ
3
11t 12 |
2w²
2 R 3
11 [1]
+
+
k=0
Proof. We begin with the result of Lemma 3
2y(F(2*t1)) 24+1 2)
(T x²) 2D (TT, xlt1))
+ (100 0|I 110ht1 - 0)12)
(2>(F(2*) - F(=*-1),= 2
27(F(2 x+1 - FF(=*),² 24t11)
2 | | - ~111 _ 110 00113
+2 11p - -p0--p---- 11- + 2g - 11-1112.
Proceeding with conditioning on 2++1
),(F(ttt),, ), 2)
$ (T, 2D (T,, n k)++ + (10+-011 - 0113)
KL L
(2x(F(=*)) - =(=*-1) x1=
1), 1--1,,
=²²) - (T F(=*). - = ,tt1)
Illntt1 - 12112 - 110b - 1²
2-pl - *
k1 1112 27 2221 g²*h 111.
(60)
We choose == Hzz in order to apply Lemma 9
(F( =) 2 (F(x'"), k+1 )²²)
(p", x k+1 n²)
n ( gh+1 gott1-00 - 0²),
(61)
Where p" (f:
M Then we substitute 61 into 600 and summing over k = 1 to K.
K
M
K (VV)((0).
2
pp
n
k+1 n²) ) + 27
Σ m
Σ
gb+l 0r
< (2DKL T²
- (T
2 xx+11) + (110' - 001 110 -8"112)
K
(2>(F((2)) F( ),2" -2 - 27 (x( - F(z*), 2' - =bt11)
/ |l - x² x²12 - - 110 - 1²2
1
+ 2 - 222 + 2 n² 11
(62)
At the next step we evaluate ||@++1_ 1²12 to extract the term for convergence criterion. We utilize CSS) inequality several times.
41

---

110h+1
IG
72
112
72 2
|1 - -11s* - -1a-111
72
[1
-
11
1 =11
g011 -119* gh
(63)
2
After that we splitting the 2110kt1 the one of them.
0 in
62
into 2 terms with factors & and substitute 63 into
K
M
K VV(()))
K
p
K
n
x+1
TT'
+
Σ
n
K
gb+l Hr
K
722
|| || k+1 x/113=
+
16
k=1
$ (2D (T',, T!)) 22 222x2 (á', x x)+1)) + (110 0-- -111-118++ -8112)
K
(2((F(=*)) F(2 n )1 2/ - 2² - 2y (((tttl) - F(z 2 21+11)
|1nkt1
x²12
110ut11 11
4
+ 22
8 115t g/112+ + 72
4 $19 - -1²-1112
+ 272112 1p 11 + 2 11
- -1
(64)
Then maximize
(64 over n' A and take full expectation. Additionally note, that
E
max F(² F(2x-1),,)0 - 2t E'EA
K
K
(g g¹ k-1 00 - -hh ) + max
pp pr k-1 7 x²)]
T'EA
1=1
E
E (g -9 80-180- - -8")1 + max
>
(p -p ,T' x²)]
n' E'
1==
K
E
5 h-1
0"
0h) + max
k-1 n }1}
T'EA
1=1
which enable us to recover the telescopic structure inner products sum.
K
M
1
1 g 0"
E max
K
p",
k+1
+
27/K
T
*'EA
K
K
k=
k=1
1
22
|
x x11
16
< EE
max K'EA
(2DRI(T',, n²) 2DKI ( k(t]) + (110) - 00112 -100 -0'13)
(27(F(=!) F(=0), x - -)2(F(=(++1)) F(= ) :/= - =k+1))
+ max T'AA
42

---

K
+
n k+1
x²12 1 =1 - 1F
4
k=1
9
+
2
+
l1g
g
11 2 + 27 21p 11
(65)
8
4
We proceed by summing 65
27
(8)
14
K+1 k=
H
40
k=
2=
M Σ
1
E max E'EA
p²,
K
π
k+1
nt
+ 2
m
V(((0)
K
gh+1 0"
K
2
K-1
K-1
+
π k+1
x x11
+
+ Σ Nottl+ +
Σ
Hw
16
A==1
k=1
k=1
< E
max E'EA
2D' ) )(="; - + 110 00
K
2H(1+ ( 1) 11 x
+
aL?
M +2 + - 110 00112
6H(1 + (
2
222
N(1 c1( 11 82 -2-3)) w 9(1 8- xx
8 +
4
9y2 (w 1) + N(1 + +11 1) H(1 + +2)(+ + +g - 23) w
+
972 + (w - 1)(1 (1(1-32))) -3 y
(66)
Considering the respective coefficients of ||0 @k11, || x² IR. w and v. we derive the following restrictions:
1 > 6H (1 + 4,2Mi2 1 2 21 2
H 9 (w 1) N(1 + (w 1) H(1 02) p2 23)
(67)
f (w 1 (w
-
N2 _ - + N(1 (1) (1+
82 2 + -0-
We now turn to selecting the free coefficients to satisfy conditions 67 inequality on N, we set
Beginning with the last
72 3
C1 = 3,8
(68)
Then the choice
1
34-2
3
guarantees sufficiency of H
(69)
2'
to satisfy third restriction in Finally, we evaluate the first two inequalities in 667 and obtaining
67
7 < ī-1 (48(17 - -2 -
(70)
and
96w 1.2 + 16Mi.) 4 S (2148 Mw 1,2 w
(71)
43

---

respectively.
By satisfying constraint (67
via choices 688)
we transform (66) into
))))
E max x E'EA
x
0h
K
K
K
K
+ K
E x+1
π
1 112+ +
7
Eli
32
K
km
Amm
2DxL(T', ; )) + (F(tt) - F(z*), - + 100 - -0112
211)
max F'EA
2
+
Σ k=0
30 + 85 2 &
It finishes the proof.
Proceeding similarly to Corollary 1 obtain the following bounds on the required number of iterations and the total amount of communicated information.
Corollary 2 setting of Theorem
with 7 = -1, Algorithm
with exact local gradients needs
(Vanr aws
))
o
La + LM + L E
VM
+w
iterations in order to reach e-accuracy with respect to W.K, Additionally, it requires
Lo + LM + L
(v
aw
M +1 +1)])
bits communicated from nodes to the server.
H LLM USAGE
Beyond aiding in the editing process, no large language models (LLMs) were employed in this work. The entire intellectual content - including all facts, claims, arguments, and proofs remained unaffected by LLM influence.
44


Reviews:
[{"review_id": "sJDM7qdjkg", "reviewer": "Reviewer_P4ke", "summary": "This paper introduces ADI (Agnostic DIANA), a novel federated learning algorithm that effectively integrates weighting methods, such as agnostic weighting for handling data heterogeneity, with communication compression techniques like DIANA-inspired gradient compression to address both statistical and system challenges in federated settings. The key contributions include a theoretically grounded framework with convergence guarantees under convex assumptions, empirical validation on benchmarks like CIFAR-10 showing improved robustness under non-IID data, and a practical approach that reduces communication overhead without compromising model performance. While the work is promising, it would benefit from broader experimental validation and extensions to non-convex scenarios.", "questions": "1. Regarding the practical utility and generalizability of the theoretical assumptions: The theoretical analysis in the paper is built on a strong convexity assumption. However, the primary application scenarios of federated learning (e.g., training neural networks) are inherently non-convex. Could the authors provide any evidence—such as experiments on standard non-convex benchmarks or a discussion on extending the theory to non-convex settings—that the convergence guarantees of the ADI algorithm still hold or remain informative in more practical non-convex environments? This is crucial for assessing the practical value of your theoretical contributions.\n\n2. On the universality and robustness of the experimental conclusions: The current experimental validation is mainly conducted on the CIFAR-10 dataset and under a specific non-i.i.d. setting. To demonstrate the broad applicability of the ADI method, could the authors present results in more challenging scenarios? For instance, does ADI consistently outperform baseline methods on larger-scale datasets or under different types of non-i.i.d. distributions—such as real-world federated benchmark datasets? This is essential for evaluating the significance of your approach.\n\n3. Toward a deeper analysis of the interaction between core components: The paper’s key innovation lies in combining weighting methods with compression techniques. However, the analysis of how compression specifically influences the dynamics of weight allocation (as illustrated in Figure 3) remains superficial. Under high compression rates, could the noise introduced by compression interfere with weight convergence or even bias the weight allocation? Could the authors provide a more in-depth analysis—such as visualizing weight trajectories under varying compression rates—to clarify this critical interaction mechanism? Clarifying this would significantly strengthen your methodological contribution.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The paper’s most striking strength lies in its high degree of originality. Rather than merely refining existing methods, it resolves a crucial yet under-explored problem through a creative synthesis. The authors perceptively recognize that, in federated learning, weighting schemes (which tackle data heterogeneity) and communication-compression techniques (which alleviate bandwidth bottlenecks) have long evolved as parallel, separate research strands. Deeply integrating the two represents a high-potential void. The proposed ADI algorithm successfully embeds an agnostic-weighting minimax formulation within a DIANA-style compressed-communication mechanism, delivering genuine interdisciplinary innovation and opening a fresh, important research avenue for the federated-learning community.\n\n- Methodologically, the work demonstrates solid quality. The algorithm is not a hasty patchwork; it is carefully engineered. It borrows mature tools from optimization theory—e.g., the optimistic extra-gradient method for saddle-point problems—and marries them with state-of-the-art variance-reduced compression, revealing a deep understanding and skillful command of relevant techniques. Moreover, the paper supplies a strict convergence analysis covering realistic scenarios such as exact gradients, stochastic oracles, and partial client participation, furnishing a firm mathematical foundation for the algorithm’s efficacy. This balanced emphasis on theory and algorithmic craft greatly enhances completeness and credibility.\n\n- The manuscript is exceptionally clear, enabling readers to grasp sophisticated ideas with ease. Starting from an articulate exposition of the twin challenges—data heterogeneity and communication bottlenecks—it gradually motivates their joint treatment, then elaborates method, theory, and experiments in a fluent, step-wise fashion. Key notions (unbiased compressors, agnostic objective) are rigorously defined; Algorithm 1 is accompanied by detailed pseudo-code and plain explanations, substantially improving reproducibility and allowing audiences to pinpoint the technical contribution accurately.\n\n- The results carry notable significance for propelling federated learning from theory to practice. By directly confronting the two toughest deployment constraints, the work is poised to yield practical algorithmic frameworks that simultaneously accommodate statistical heterogeneity and curtail communication costs. Systematic empirical comparisons robustly demonstrate the effectiveness of weighting approaches under compression, underscoring the study’s potential real-world influence.", "weaknesses": "- The theoretical convergence analysis of the paper is based on a key assumption: the local loss functions of the clients are convex. This assumption severely limits the practical value of the theoretical results because the primary application scenarios of federated learning (such as training deep neural networks) are inherently non-convex. This greatly diminishes the practical guidance provided by the theoretical guarantees. An actionable suggestion for improvement is that the authors should explicitly acknowledge this limitation in the discussion section and attempt to provide some heuristic convergence analysis or observations on standard non-convex models. For example, they could briefly discuss the possibility of extending the analysis to weaker non-convex assumptions, such as the Polyak-Łojasiewicz condition, which would significantly enhance the depth and relevance of the theoretical section.\n\n- The experimental section relies primarily on the CIFAR-10 dataset and a single non-IID partitioning method based on the Dirichlet distribution. This setup is too narrow to adequately demonstrate the generality and robustness of the proposed method. Specifically, validation is lacking for larger-scale or different modality datasets, as well as for more extreme or real-world heterogeneity scenarios. To address this weakness, the authors must conduct additional experiments. An actionable recommendation is to test the algorithm on more challenging benchmarks, such as CIFAR-100, a federated learning text dataset, or a real non-IID dataset from the LEAF benchmark. This would strongly demonstrate the method's scalability and universality, moving beyond a mere proof-of-concept that is effective only in a specific setting.\n\n- The paper's core innovation lies in the combination of weighting methods and compression techniques. However, there is a lack of in-depth analysis of how these two components interact. A key unanswered question is: does the noise introduced by compression interfere with or distort the dynamic process of weight assignment? For instance, under high compression rates, could weight updates become unstable or biased? The authors need to provide a more detailed analysis to clarify this mechanism. A specific method for improvement is to design a controlled experiment that systematically varies the compression rate and then observes and analyzes the trajectory, stability, and final distribution of client weights. Such an analysis would not only verify the robustness of the method but also profoundly reveal its internal working mechanism, thereby greatly strengthening the paper's contribution.", "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": "GMr1Kxvxdl", "reviewer": "Reviewer_KP2w", "summary": "The paper studies how to **combine adaptive weighting in federated learning (FL)** with **communication compression** by casting weighting as a **min–max (agnostic) formulation** and proposing an **extragradient-style** method, **ADI** (Alg. 1), that communicates only *compressed* model updates while exchanging one scalar (local loss) per client to update weights. The objective is written as\n$$\\min_{\\theta}\\max_{\\pi\\in\\Lambda}\\;\\sum_{i=1}^M \\pi_i f_i(\\theta),$$\nwhere $\\pi$ lies in a convex subset of the simplex (an agnostic-weighting set $\\Lambda$) so that weights are learned during training with negligible additional communication (one loss per client) compared to gradients. The paper proves **(i)** convergence in a deterministic convex setting, **(ii)** extensions to **stochastic local oracles**, and **(iii)** **partial participation** with sampling rate $p$ under **unbiased compressors** characterized by a variance parameter $\\omega$. Complexity bounds are provided in terms of the **gap function** and **bits-on-wire**. Experiments on classification (ResNet/CIFAR) qualitatively compare ADI to DIANA and show weight stabilization.", "questions": "1. **Comparative complexity**: For the main deterministic and stochastic results, can the authors **tabulate** iteration and bit complexity side-by-side against **DIANA**, **EF21**, and **MASHA**, fixing a common set of assumptions (convexity, unbiased compressors), to show **when ADI is strictly better** (or at least not worse) in the leading-order dependence on $M,\\omega,p$? \n2. **Non-convex case**: Can the analysis be **extended** to **non-convex** $f_i$, aligning with the deep-network experiments? If not, please clarify this limitation in the conclusions.\n3. **Weighting set $\\Lambda$ & prox**: What is $\\Lambda$ concretely in the experiments (simplex, KL-ball around uniform, box constraints)? The proofs rely on KL-based prox on $\\pi$; please **state $\\Lambda$** near the algorithm and connect it to the constants in the rates. \n4. **Partial participation**: The corollary yields an $\\omega/\\!p$ dependence in bits. Can you **empirically verify** this scaling by varying $p$ on a fixed task and compressor?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- **Clear motivation**: Formulating adaptive weighting as a saddle-point problem makes explicit how to **learn client weights** while preserving a communication-efficient pipeline; local losses are the only extra information needed at the server, which is indeed cheaper than transmitting even compressed gradients. \n- **Method design**: ADI integrates an **optimistic/extragradient**-style update for the $(\\theta,\\pi)$ saddle-point operator together with **compressed communications** and server-side memory terms, avoiding full-gradient transmission. \n- **Theoretical backbone**: The paper establishes monotonicity of the saddle-point operator and analyzes convergence under convexity and unbiased compression assumptions.  \n- **Stochastic & partial participation**: Beyond exact gradients, the analysis covers **stochastic oracles** and **partial participation** ($p<1$), with explicit dependence on $\\omega$ and $p$. \n- **Communication accounting**: The paper makes the **bits-on-wire** explicit through an expected density $q_\\omega$ and states iteration/bit complexities (including the $p$-scaling for partial participation). \n- **Connection to literature**: The related-work section situates the approach amid **agnostic FL** (AFL) and fairness-weighting methods as well as extragradient methods for saddle-point problems and compression.", "weaknesses": "- **Novelty positioning is underdeveloped**. The algorithmic ingredients—**agnostic weighting** (AFL), **extragradient/optimistic updates**, and **unbiased compression with memory**—are all known. The paper does not convincingly demonstrate **strict improvements** over prior **saddle-point + compression** methods such as **MASHA** or over **DIANA/EF21**-style approaches when combined with weighting, nor does it provide tight side-by-side **complexity comparisons** to prove advantages (e.g., in dependence on $\\omega, M, p$). \n\n[1] Mishchenko, Gorbunov, Takáč, Richtárik. “Distributed Learning with Compressed Gradient Differences.” _arXiv:1901.09269_, 2019. ([arXiv](https://arxiv.org/abs/1901.09269 \"[1901.09269] Distributed Learning with Compressed Gradient Differences\"))\n\n[2] Richtárik, Sokolov, Fatkhullin. “EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback.” _NeurIPS 2021_ (proceedings version).\n\n[3] Beznosikov, Richtárik, Diskin, Ryabinin, Gasnikov. “Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees.” _NeurIPS 2022_. ([NeurIPS Proceedings](https://proceedings.neurips.cc/paper_files/paper/2022/hash/5ac1428c23b5da5e66d029646ea3206d-Abstract-Conference.html \"Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees\"))\n\n\n- **Ambiguous constants and scalings**. The rates use $\\tilde L$, $L$, $M$, $\\omega$, and sometimes exhibit **non-intuitive mixes** (e.g., $\\tilde L \\sqrt{\\omega}$ and $L\\sqrt{\\omega^3/M}$ in bit complexity). The paper should (i) define $\\tilde L$ precisely near the main theorem; (ii) factor the bounds to highlight the **leading-order** dependence on $M,\\omega,p$; and (iii) provide **regimes** where ADI is provably preferable to DIANA/MASHA. \n- **Theory audit (tightness and steps)**. \n  - The **variance accounting** (e.g., the transition from (40)–(44) to the final bound) involves several compressions of sums across clients; a concise **lemma** summarizing how unbiased compression interacts with the server memory ($h^k$) would improve readability and verifiability. \n- **Empirical evaluation is limited**. \n  - The **baselines** are insufficient: no **AFL** (Mohri et al., 2019) or **q-FFL** variants (Li et al., 2020) are included, although these are central **weighting** competitors; likewise, **MASHA** (saddle-point with compression) is missing. \n\n[4] Mohri, M., Sivek, G., & Suresh, A. T. “Agnostic Federated Learning.” _ICML 2019 (PMLR v97)_, pp. 4615–4625.\n\n[5] Li, T., Sanjabi, M., Beirami, A., & Smith, V. “Fair Resource Allocation in Federated Learning.” _arXiv:1905.10497_ \n\n\n  - Plots are primarily **qualitative**; **error bars**, **multiple seeds**, **bytes-on-wire vs. accuracy** with equalized compute, **participation-rate sweeps** ($p$), and **compressor-strength sweeps** ($\\omega$) are needed. The paper does show weight stabilization, but does not quantify the impact on accuracy/fairness trade-offs. \n- **Reproducibility details**. Hyperparameters and training schedules are not reported with sufficient granularity (optimizers, LR decay, momentum/weight decay, batch sizes per client, number of local steps $K$ vs. rounds), nor is **code** provided; these are required for an ICLR-standard empirical section.", "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": "5GOfFk4hoC", "reviewer": "Reviewer_tXwb", "summary": "This paper introduces ADI, a unified federated learning algorithm designed to jointly tackle communication bottlenecks and data heterogeneity. By integrating a difference compression scheme within a min-max optimization framework, ADI dynamically learns to weight clients based on their data's informativeness.", "questions": "1.The paper's narrative suggests weights are assigned to clients with unique data. Could the authors elaborate on how the algorithm would behave in the following more nuanced scenarios, where the concepts of uniqueness and high loss might diverge?\n(a) A client with a unique data class that is very easy to learn. Would its weight initially spike and then fall once the model quickly masters its data, potentially ending up below average?\n(b) A client whose data classes are common across the network, but whose specific samples are particularly noisy or inherently difficult (i.e., 'hard examples'). Would this client receive a persistently high weight despite its data not being distributionally unique?\n\n2.Could the authors provide some intuition on why the dynamics of the agnostic weighting scheme, proven to be stable in the convex setting, appear to remain effective in the non-convex landscape of deep learning?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tThe work is highly relevant to the scope of ICLR, as it contributes a novel approach to a fundamental challenge in federated learning.\n-\tThe proposed ADI algorithm is novel in its effective integration of difference compression with an agnostic weighting scheme.\n-\tThe paper provides a comprehensive theoretical analysis that guarantees convergence in a convex setting.", "weaknesses": "-\tThe weight update rule in Algorithm 1 appears to contradict the paper's min-max objective, potentially invalidating the core weighting mechanism.\n-\tInsufficient explanation of hyperparameters.\n-\tThe interpretation of the weight dynamics in Figure 3 oversimplifies the mechanism, conflating high loss with data uniqueness without deeper analysis.\n-\tA significant gap exists between the paper's convex theoretical analysis and its non-convex deep learning experiments.\n-\tThe empirical validation is limited to a single dataset (CIFAR-10), which is insufficient to demonstrate the algorithm's generalizability.", "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)