Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Authors: Rustem Islamov
Yarden As
Ilyas Fatkhullin
Venue: ICML 2025 poster (2025)
Keywords: Optimization
Distributed Optimization
Compression
Safe Reinforcement Learning
Primary area: optimization->large_scale_parallel_and_distributed
TL;DR: We analyze a non-smooth distributed optimization problem with constraints and provide an algorithm to solve it which matches the lower bound.

Abstract: Federated learning faces severe communication bottlenecks due to the high dimensionality of model updates. Communication compression with contractive compressors (e.g., Top-$K$) is often preferable in practice but can degrade performance without proper handling. Error feedback (EF) mitigates such issues but has been largely restricted for smooth, unconstrained problems, limiting its real-world applicability where non-smooth objectives and safety constraints are critical. We advance our understanding of EF in the canonical non-smooth convex setting by establishing new lower complexity bounds for first-order algorithms with contractive compression. Next, we propose Safe-EF, a novel algorithm that matches our lower bound (up to a constant) while enforcing safety constraints essential for practical applications. Extending our approach to the stochastic setting, we bridge the gap between theory and practical implementation. Extensive experiments in a reinforcement learning setup, simulating distributed humanoid robot training, validate the effectiveness of Safe-EF in ensuring safety and reducing communication complexity.

Safe- Ef:e-EF: Error Feedback for Non-smooth Constrained Optimization
Rustem Islamov!
Yarden As
Ilyas Fatkhullin 23
Abstract
parameters to be optimized. The function ft: fi: local (possibly non-smooth) loss associated with data on worker i E [n]] = (1,...,n), and X' is subset of Rd.
IR is the
Federated learning faces severe communication bottlenecks due to the high dimensionality of model updates. Communication compression with contractive compressors (e.g., Top-K) is of- ten preferable in practice but can degrade perfor- mance without proper handling. Error feedback (EF) mitigates such issues but has been largely restricted for smooth, unconstrained problems, limiting its real-world applicability where non- smooth objectives and safety constraints are criti- cal. We advance our understanding of EF in the canonical non-smooth convex setting by estab- lishing new lower complexity bounds for first- order algorithms with contractive compression. Next, we propose Safe-EF, a novel algorithm that matches our lower bound (up to a constant) while enforcing safety constraints essential for practical applications. Extending our approach the stochastic setting, we bridge the gap between theory and practical implementation. Extensive experiments in reinforcement learning setup, simulating distributed humanoid robot training, validate the effectiveness of Safe-EF in ensuring safety and reducing communication complexity.
This paradigm is particularly valuable in privacy-sensitive and resource-conssrainee settings, where data remains de- centralized, and collaboration achieved without requiring direct data sharing. For instance, consider a fleet of robots that operate in homes (Kalashnikov et al., 2018; Brohan et al., 2022). In such settings, traditional centralized learn- ing approaches are impractical, as transmitting raw sensory data from each robot to a central server would pose severe privacy risks and require enormous bandwidth. Furthermore, these robots must adapt to diverse household environments, necessitating personalized learning while still benefiting from collective experience across the fleet. Despite its ad- vantages, distributed training faces significant communica- tion bottlenecks due to the high dimensionality of model updates. This challenge necessitates the development of communication--effiieen algorithms.
Communication compression with Top-K. One promi- nent strategy reduce communication costs is the com- munication compression technique, which applies possibly randomized compression to updates prior transmission. One of the most practical and versatile classes of compres- sion operators are those that satisfy the contractive property: for all x E Rd,
E [[][(() x < (1- 6)]==]/
1. Introduction
where 8 E (0, 1] represents the accuracy of the compression. Prominent examples are Top- sparsifier that preserves K largest components vector x in magnitude, and random sampling methods such as Rand-K that preserves a subset of K components of x chosen uniformly at random. Although both Top-K K and Rand-K K are contractive with 5 K/d, methods utilizing Top-K K operator are often empirically su- perior due to their greedy nature (You et al., 2016).
Federated learning is crucial framework for train- ing machine learning models across distributed environ- ments (Konečný al., 2016; Kairouz, 2019), where data is naturally stored in a distributed fashion. Formally, such problems can be expressed as
f() = 1 Σ f(()),
min f(x)(( zEX
(1)
Non-smooth challenges. The majority of works focusing on communication compression assume that the objective function is smooth, i.c., differentiable with Lipschitz contin- uous gradient, simplifying theoretical analysis (Stich et al., 2018; Richtárik et al., 2021). However, this assumption limits the applicability of developed methods to many real- world problems, where non-smooth functions frequently arise. For instance, consider problems involving ReLU ac- tivations (Glorot et al., 2011) or clipped objectives such
where represents the number of workers or machines participating in the training, and E Rd denotes the model
'University of Basel, Switzerland *ETH Zürich, Switzerland e "ETH AI Center, Switzerland. Correspondence to: Rustem Is- lamov crustem.isaamon @ unibas.ch>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Safc-EF; Error Feedback for Non-smooth Constrained Optimization
as those in proximal policy optimization (PPO, Schulman
*Safe-EF EF
et al., 2017). This motivates the first key question of our study:
EF21
CGD
What are the limits of compressed gradient methods in the non-smooth regime?
Question 1:
To illustrate the challenges of designing meaningful meth- ods with contractive compressors like Top-K, we present a non-convergence example for vanilla compressed gradient descent (CGD) the non-smooth setting. Consider
20
60
Iterations
Figure 1: Non-convergence of CGD, divergence of EF21
and convergence of Safe- for the problem f(x) | 1, == 1, d used in the proofs of Examples 1.1 and 1.2 with Top-1 compressor. We run all algorithms for T 10 iterations with x² (7/2, -))_,,)",, 7 = 1/VT, and en (1.1) (for EF21). *Safe-EF coincides with EF14 (Seide et al,, 2014) in this example.
++ x² 2 Σ CUI(')) n i=1
CGD
(2)
where f((x*) 0f((=') is subgradient of fi and y is stepsize.
Example 1.1. For any n 2 1, there exists a specific in- stance of problem (1) where X' = IR? and f(x)= = ||>||a is non-smooth, convex, and 1-Lipschitz continuous. For this instance, with some initial vector 20 R2, the iterates of CGD (2) applied with the Top-1 compressor and any stepsize 7 0, satisfy
Example 1.2. Consider the problem instance from Ex-
ample 1.1. For this instance, with some initial vectors x., eo, E IR2, the iterates of EF21 (3) applied with the Top-1
((x")-iin f(x) - 11 27 for any t tz O.
compressor and any stepsize 2 0 satisfy
f(x') min f(z) 1+ + +
for any t 2 0.
This example implies that running vanilla CGD with the Top-1 compressor even on a simple non-smooth problem may yield no improvement. It is remarkable that this failure occurs even in the identical data regime fi = f for all E [n], the setting where CGD known to converge in smooth case (Nesterov, 2012; Nutini et al., 2015; Beznosikov et al., 2023). The idea of the construction in Example 1.1 is that due to a rapid change of the gradients f' in consecutive iterations, CGD consistently ignores the direction of the second component of z², which results in a pathological cyclic behavior. See Figure for an illustration.
This example shows that EF21 does not converge for non- smooth problems despite achieving an excellent perfor- mance in smooth case, see Theorem C.I, and reaching the optimal iteration complexity in smooth non-convex opti- mization (Huang et al., 2022). Moreover, if we pick the classical stepsize 7 = 1/VT, EF21 diverges from the op- timum with a rate (tt/VT) = VT for t z T, which is even worse than CGD. We show the divergence in Fig- ure 1, where we also observe that another EF variant, EF14!, (Seide et al., 2014) converges without problems. We find such stark difference surprising in light of the equivalence of EF21 and EF14, established under additivity assumption of C (Richtárik et al., 2021). The catch is that Top-1 is not additive, and thus the equivalence does not hold here.
Error feedback can make things worse! A common rem- edy for coneeenveeee issues of compressed gradient methods is error feedback (EF), mechanism that has in- spired several variants (Seide et al., 2014; Richtárik et al., 2021; Fatkhullin et al., 2024; Gao et al., 2024). Among these, EF21 is a recent approach with state-of-the-an perfor- mance guarantees in smooth optimization due to Richtárik al. (2021):
Motivated by this fairly toy example, we find it important to understand EF in non-smooth setup, and aim to study EF14.
Safety considerations. In addition to these challenges, safety constraints play critical role in real-world appli- cations (Altman, 1999). Ensuring solutions satisfy feasi- bility requirements is essential, particularly in scenarios like federated reinforcement learning (FedRL) (Nadiger et al., 2019; Qi et al., 2021; Jin et al., 2022). Despite their importance, constrained optimization with commu- nication compression remains under-explored. Although some work develop methods assuming X is simple, i.e..
x -'-
EF21
at of ((f((x(t)) vf).
where f((+++) E (x- is subgradient of and of is a local gradient estimator at each worker. While Richtárik et al. (2021) only analyze this algorithm in the smooth non- convex case, we extend its analysis to smooth convex setup in Appendix C. However, we show that, surprisingly, EF21 fails to converge on the same problem as CGD.
'Our SFfe-EF method presented in Algorithm reduces EF14 unconstrained setting with Co = Id.
2

---

Safc-EF; Error Feedback for Non-smooth Constrained Optimization
using projection (Fatkhullin al., 2021) linear minimiza- tion (Nazykov al., 2024) oracles, they crucially rely
Next, we propose Safe-EF (Algorithm 1), an extension of EF14 (Seide et al., 2014) incorporating safety con- straints (4) via primal switching subgradient approach and bidirectional compression including the workers to server compressor Co. Safe-EF EF provably works in non- smooth distributed settings and efficiently minimizes the objective function, while controlling the constraint violation. We prove the convergence rate of Safe-EF matching the above-mentioned lower bound up to numerical constant under constant accuracy of the server compression Co. It seems our upper bound is new even when g(z) = 0 and Co Id.
smoothness. Moreover, the applications in Safe FedRL mo- tivate us to pay attention to problems with more complex constraints of the form
[(x)= + -E= (x) < 0}, where 9;: Rd + IR defines a constraint for worker i.
X { x E Rd
(4)
Question 2: Can we design a provably convergent compressed gradient method with Top- K com- pressor for non-smooth constrained problems?
We further study Safe-EF in practically relevant stochastic scenarios, where exact subgradients and function evaluations are unavailable and need to be estimated. We establish high probability bounds with a mild logarithmic dependence on failure probability, which is significant even without compression, since our bounds feature the distance to the optimum in- stead of the diameter of the set, which not bounded in our set-up.
Perhaps, the most common approach to solve (1) with (4) in non-distributed optimization (n = 1) is to reformulate it as saddle point problem, which is then solved by primal-dual methods (Nemirovski, 2004; Hamedani & Aybat, 2021).
This approach is popular in practice (Ding et al., 2020; Moskovitz et al., 2023; Ding et al., 2024; Müller et al., 2024) and has rich theory, e.g., (Boob et al., 2023; Boob & Khalafi, 2024; Zhang& & Lan, 2022). However, such methods have several limitations. First, they are known to be sensitive to the tuning of the initial dual variable (e.g., the experiments and discussion in Appendix G) and often require an estimate of the upper bound of the optimal dual variable. Second, their theoretical justification often requires projecting both primal and dual variables onto an unknown bounded set, which is not aligned with practical implementations. In the context of EF-type methods, this projection requirement im- plies several algorithmic and technical challenges because only certain smooth variants of EF seem be compatible with projection, e.g., (Fatkhullin al., 2021). An alter- native is to adopt a primal only approach, e.g., switching subgradient (Polyak, 1967; Lan & Zhou, 2020; Ma et al., 2020; Huang& & Lin, 2023; Jia & Grimmer, 2022), methods based on the velocity field (Yu et al., 2017; Muchlebach &
Finally, we conduct extensive experiments and abla- tion studies of Safe-EF, putting the method to the test on a challenging task of distributed humanoid robot training and providing important practical insights into the performance of non-smooth EF methods.
3. Assumptions and Communication Protocol
We consider distributed constrained optimization problem (1) with a constraint (4), and denote the optimal solution to this problem by x². Unless specified otherwise, we denote by II-II the Fuclidean norm in Rd
Assumption 3.1. We assume that fi and gi are convex for all E [m], namely, for all x, y E Rd we have (v() 2 f((x) + (f.. - x) e
Jordan, 2022: Schechtman et al., 2022; Kolev et al., 2024),
or level-set methods (Lin et al., 2018; Boob et al., 2024). Primal methods have also been used in (non-distributed) RL applications, e.g., (Xu et al., 2021; Chen et al., 2021; Jordan et al., 2024; Li et al., 2024). The key advantage of such primal schemes is their simplicity and convergence under mild assumptions without the need for the estimation of dual variables.
(5)
9:(y) 2 (x) + (o.. - x) Vol. E (g)
Each worker has access to the oracles Og,((z) and (z), which return the subgradients S E 0f((z), J. E dg.(z). and the function values fz(), (x(x) respec- tively for any x E Rd We assume bounded subgradient, which is a common assumption in non-smooth optimization (Nesterov al., 2018)
2. Contributions
Assumption 3.2. We assume that fa and 9s have M- bounded subgradients, i.e. for any x Rdd and i E [m]
convergence lower First, we establish Ω VST
bound for non-smooth convex distributed optimization with contractive compressors for function suboptimal- ity gap and a constraint violation. Here T' is the itera- tion count, R is the initial distance to the optimum, M bounds the norm of subgradients of f., and e (0, 1] is the compression accuracy.
we have
max (I) 110((=)113 S M.
(6)
We let the function classes FR,M and GRM denote the set of all functions satisfying Assumptions 3.1-3.2 for any un- derlying dimension and a given initialization d0 Rd
3

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
such that ||000 - x= ~=| R. We denote by HR.M the class of problems of form (1), (4), where functions {fi]== and {g.)== are taken from FR,M M and GR,M respectively.
4. Main Results
We start by presenting our first main contribution, which is the lower iteration/communcatioo complexity bound for a class of first-order compressed gradient methods.
Compression operators. We focus on the class of algo- rithms using contractive compressors.
4.1. Lower Bound
Given a problem h := subgradien//fucction value oracles { (O (0 g0 compressors {c.) C C((), and algorithm A represent
S HR.M
Definition 3.3. We say that a (possibly randomized) map- ping C: Rd + Rd is a contractive compression operator if for some constant 6 E (0, 1] it holds
[c,);_, let l == , the output of algorithm A after at most I oracle queries and communication rounds per worker. We define the minimax
E [[[[(x) - [ < (1 - ||]]]
(7)
Beyond Top-K K and Rand-K mentioned in Section 1, ex- amples satisfying (7) include sparsification (Alistarh et al., 2018; Stich et al., 2018; Islamov et al., 2021) and quantiza- tion (Wen et al., 2017: Bernstein al., 2018; Horváth al., 2022; Compagnoni et al., 2025) techniques, and low-rank approximations (Vogels et al., 2019; Qian et al., 2021a; Is- lamov et al., 2023). We refer to (Beznosikov et al., 2023; Safaryan et al., 2021) for further examples. We denote by (6) the set of all 6-contractive compressors.
convergence measure inf sup sup A (c.) AEHR.M ACHR,M
- ((x"))))(())))(((((
We do not require operators {C,}i=1 to be neither distinct nor independent, and parameter ō can be utilized by the algorithm A. Our first contribution is the lower bound for algorithms that support unidirectional compression.
Theorem 4.1. For any R. M > 0, 2 2
8 2 there exists a problem h C HR.M. oracles poaRR (0 Jn
Algorithm class. We follow Huang et al. (2022) to intro- duce the class of algorithms of interest. We consider centralized and synchronous algorithm A, where: i) work- ers are restricted to communicating directly with central server and cannot exchange information with one another directly; di) all iterations are synchronized, meaning all workers begin each iteration simultancously. In this setup, each worker maintains a local copy of the model, denoted as z/. iteration t. The output á of the algorithm after iterations be expressed as any linear combination of all previous local models, namely,
{O point x = 0 such that for any first-order algorithm A e
compressors {Co] S C(5), and the starting
A (c))= run for T S d iterations from x", satisfies
RM
((((Ar)-f(x")) -
and
V8T
(9)
RM
Elg(EAT)) 20 0
V8T
When 8 = and g 0, indicating no compression and no constraints, (9) recovers the classical lower bounds for non-smooth convex optimization (Nemirovskij & Yudin, 1983; Nemirovski, 1994; Nesterov, 2014; Braun et al., 2017; Scaman et al., 2018). However, when worker to server com- pression large, the convergence rate degrades by factor of 1/V8. Similar degradation appears in the constraint vi- olation. An interesting implication of Theorem 4.1 1. is that the convergence rate does not improve when increasing the number of workers n, which is different from prior work in smooth stochastic optimization (Huang et al., 2022; He et al., 2023). The key idea of the proof is to extend and modify the "worst-case" function from (Nesterov, 2014) and account for compression in the distributed setting, specifically, we use for all i [n]]
&' E span (f0ī:0 0 S st,,iii
(8)
We additionally require that the algorithm A satisfies the "zero-respecting" property (Carmon et al., 2020; Lu & De Sa, 2021). This ensures that the number of non-zero entries in a worker's local model can only increase through local subgradient queries, or synchronization with the central server. This property upheld by a broad range of exist- ing distributed optimization algorithms (Tang et al., 2019; Xie et al., 2020; Richtárik et al., 2021; Gao et al., 2024). In addition to these properties, the algorithm A must sup- port communication compression. To achieve this, each worker i E [r] is equipped with a compressor C, The for- mal definition of this algorithm class with worker to server compression is provided below, see Appendix E for details.
f((x) == C. mam I; + 4 1 max { ||a||12:
R 2
1S1S 2
Definition 3.4. Given compressors [C,,...,C,,) C.)). we de- note ( as the class of all centralized, synchronous, zero-respecting algorithms that support unidirectional com- pression, where compressor C,, i E [n], is applied to mes- sages from worker to the server.
(x(x)) = f((x) min fi(x))
=ERd
where C. > 0 are some constants depending on the bound of subgradients M and the compression level 6. We refer to Appendix E for the formal proof.

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Then there exist choice of stepsize 7 and threshold e such that the iterates of Sate-EF with bidirectional compression satisfy
Algorithm 1 Safe- EF with bidirectional compression
1: Input: w0 = z0. [C. 7, O, ep = 0
RM
2: for (- 0, O....,
do
E
5o
and
3: for I.... n in parallel do
VoLoT RM VoLöT
4: Send (x(")) to server
cheap one float comm.
(10)
[ [0(T")| s0
5: end for
6: Send g(x²) 1 E s=1 (z') ) to workers
where I² Eies''.
7: for = 1, ,..... n2 in parallel do
8: Compute hgg = (x() if g(x") S c clsse (x))
9: Send of = (el + ht) to server
The proof of the theorem is detailed in Appendix D, where also give explicit choice of 7 and Next, we discuss the obtained result in several special cases as well as the main difficulties in the convergence proof.
10:
Compute : = et + h of
11:
end for
12:
Compute of 1 ii of and w = w² - -pt
13: Compute x++1 = x² + Co(w - x²)
n
14:
Send Co (u(w+1 - x²) to workers
Single-node training with no compression. In the special
case where n = 1 and 6, = d = 1, corresponding to the non-distributed setting without compression, (10) recovers the rates in (Nesterov al., 2018; Lan & Zhou, 2020).
15:
end for
No constraints, i.e., 9 0, and Co = Id. In this case, our algorithm, Safe-EF. EFaa-EEF.. simplifies to the well-known EF14 method (Seide et al., 2014). EF14 was previously analyzed in the non-smooth setting for single-node training (n = 1) by Karimireddy et al. (2019). Theorem 4.2 extends the analysis to the distributed setup. Notably, the convergence rate is consistent with that presented in their work in this special case.
4.2. Safe-EF Method
In this section, we describe Safe-EF, our main algorithm de- tailed in Algorithm 1, which addresses two main challenges simultaneously: handles non-smoothness and constraints. The distinct feature of our method is a dynamical switch between the subgradients of the objective fi and those of the constraints 9: depending on if the constraint violation exceeds a predefined threshold c. To implement this, work- ers compute the constraint violations gi (xx") and commu- nicate them to the server. This process does not increase communication overhead, as it requires transmitting only a single float per iteration. Equipped with this switching rule, we use EF14 (Seide et al., 2014) type updates to limit the communication overhead of sub-gradients from workers to server. Furthermore, we additionally enhance Safe-EF with server to workers compression using "primal" EF21 variant, EF21-P, due to Gruntkowska et al. (2023), which compresses the difference between two estimates of the model parameters w/+1 and z²!
Unidirectional compression. Next, we consider the setting
with unidirectional compression, i.e., &g = 1 and Co = Id. We observe that both the functional suboptimality gap and constraint violation diminish at a rate of O1/V8T), consistent with the lower bound established in Theorem 4.1, thereby confirming the optimality of Safe-EF assuming 8, is numerical constant independent of d and K.
Bidirectional compression. Now we discuss the setting when the compression is applied in both directions. It is worth noting that most prior studics focus on a more re- stricted class of compressors, such as absolute compressors (Tang et al., 2019) or unbiased compressors (Philippenko Dieuleveut, 2021; Gruntkowska al., 2023; 2024; Tyurin & Richtarik, 2023), in the bidirectional setting. In contrast, our work does not impose any additional constraints on the compressors. Other related work considers only server to worker compression (Sokolov & Richtárik, 2024), while often compression both directions is important. The con- vergence rate in (10) highlights a slowdown by a factor of / Vōgō, which aligns with similar dependencies observed in prior works on smooth distributed optimization (Fatkhullin et al., 2021). It remains an open question whether the depen- dence on the compression levels 8 and å can be improved in the non-smooth setting. Perhaps, this dependency could potentially be reduced from vō.ō to v8 + Vog by incorpo- rating multiple communication rounds per iteration, similar
4.3. Convergence Upper Bound
In our next theorem, we provide the convergence guarantees for Safe-EF summarized in Algorithm 1. The set denotes all iteration counters when the constraint violation below the threshold c, i.e., B Ll [T - 1] ((x*)) S c).
Theorem 4.2. Assume Assumptions 3.1-3.2 hold, the server and workers use compressors Co E C(6)), (C.) C C(8).
II fact, it was noted by Gruntkowska et al. (2023) that pure EF21-P used at the server level can be reformulated as EF14 on the worker level. However, we only use EF21-P formulation for algorithmic presentation and design the convergence proof using EF14 formulation.
5

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
to the approach in (Huang al., 2022). However, this pro- cedure can be impractical since [K/ coordinates are communicated at every iteration as observed in (Fatkhullin et al., 2024), and we leave the study of this strategy for future work.
and
ge(x) Eswd, [a((x,))),
(13)
where Dj is a distribution of local environment (dataset)
at worker E [n]. We assume that the noise follows a
sub-Gaussian distribution.
Key theoretical challenges. We emphasize that controlling constraints significantly complicates the analysis compared to prior work (Karimireddy et al., 2019), which is limited to the unconstrained, unidirectional, non-distributed setting. A key novelty of our analysis lies in demonstrating that an appropriate choice of the stepsize y and threshold с ensures that the number of iteration counters in B with constraint violations below c is sufficiently large to guarantee progress in reducing functional suboptimality. In particular, is not empty and thus ह" is well-defined.
Assumption 5.1. Workers have access to M-bounded stochastic subgradients and of NNv-sub-Gaussia function evaluations of 9t. namely, for some M, M / > 0, any
R and any E [Tz] we have
(2. ("),,, (1o((1, E¹) S SM, (
(14)
E Eexp (x.(x, 9x()))
) S exp(1),
(15)
of./NNtv
where ç is a sample from the local dataset D. The latter assumption on sub-Gaussian function evaluation can be satisfied by implemented mini-batch estimation of the constraints with batch-size Niv. Moreover, we assume that the workers compute subgradients and function evaluations independently for any given x.
Communication complexity with Top-K. In unidirec- tional case with C; is Top-K and Co = Id, the total commu- nication complexity is"
R
KR 5
M2 62
K
(II)
8E2
Assumption 5.2. We assume that for all E [n]] and for all ç' Dj the functions (z) and (x {*) are convex, i... for all xr E IRd we have
Bouts per iteration
# iterations
where utilize the condition 8 3/4 for Top-K. This finding indicates that the communication complexity of Safe-EF aligns with that of parallel switching subgradi- ent method (Safe-EF without compression) in the worst- case scenario, However, an improvement is possible when 5 > 5. which occurs if the entries differ substantially in magnitude (Beznosikov et al., 2023).
ful, E*) 2 Mi(x, (²) + (f((x, vー x), (16) gilu. 2 9:(ar, (+) - (),(,,)),, x), (17) for all f((x, E*) E 0f, {²) and g((x, {*) E (t)
Remark 5.3. We highlight that the special (semi- stochastic) case when subgradient evaluations f( e*) g( are stochastic, but the constraint evaluation of gi is deterministic, the proof significantly simplifies, and conver- gence analysis can be repeated as in Appendix D. However, the stochastic estimation of constraint violation g(x) poses a significant challenge and we need to use advanced tech- niques to conduct high probability analysis.
Key Steps of the Proof. the "virtual iterates" construction of Stich & Karimireddy (2019) (see Equation (22)). In Lemma D.1, we then derive a unified bound controlling both the function sub-optimality and the constraint violation. Crucially, by enforcing appro- priate choices of the step size y and threshold e, we show that this bound can be made small enough. The same lemma also guarantees that after T iterations, either the number of approximately feasible points are at least | 2 _ the sub- optimality is already below the desired tolerance. Together with the preliminary lemma on the virtual iterates, this yields our full convergence theorem for Safe-EF. Finally, in Corol- lary D.4 we verify that the stipulated conditions on ? and are indeed feasible.
Our convergence proof builds
Theorem 5.4. Let ,3 E (0, 1/2) be a failure probability and R Z 1| - x= Assume workers use deterministic compressors {c.) S C()). Then there exists a choice of stepsize y, threshold c, and large enough batch-size Ni Z Ö dex ) such that the iterates of Sate-EF with unidirectional
compression satisfy with probability at least 1 - 2
(MR+ + NNew )(1 + log 11
f(3") - -(00))
V8T
(MR+
DIV VNN
[[ + log 4)
5. Extension to Stochastic Setting
g( S0
(18)
V8T
In this section, we consider a stochastic formulation of our the problem (1), (4), namely,
To achieve e-accuracy, i.e., f(xT) - Safe-EF requires batch-size of order ① (0((o) (dR/os²). The con- vergence rate matches the lower bound (9) up to numerical and logarithmic factors. The proof is deferred to Appendix F. One of the key technical challenges of the above result is that the analysis in the prior (oonddistributed) work (Lan &
S e,
f fx)) = EDWD, [f( {")]
(12)
'We omit the numerical constants and logarithmic factors in comparison.
6

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
Zhou, 2020) relies on bounded domain assumption, while the iterates of our algorithm can be potentially unbounded. To address this issue we use the ideas from (Liu et al., 2023) to establish strong high probability convergence.
initially faster; however, Safe-EF catches up with EControl by the end of the training.
6.2. Policy Gradients for Humanoid Robot Fleet
Remark 5.5. While the iteration (and communication) com- plexity of the method in the stochastic setting matches the lower bound up to numerical and logarithmic factors, its sample complexity is suboptimal. Taking into account the necessity of O(E)) batch-size, the sample complexity of the method becomes ((t)). Nevertheless, this complexity is no worse than the one given by non-distributed gradient switching method (Lan & Zhou, 2020). We use differ- ent technique to conduct high probability analysis than Lan & Zhou (2020) because their analysis crucially relies bounded diameter assumption, which we do not have in our formulation.
In this suite of experiments, we demonstrate an applica- tion of Safe-EF for reinforcement learnin. In this setup, each worker represents humanoid robot that collects noisy measurements of some utility and constraint functions, to solve a constrained Markov decision process (Altman, 1999, CMDP).
Constrained Markov decision processes. We define a CMDP the tuple (S, 7, 7, P),, where S describes state space (e.g. joint positions and velocities) and A describes a set of admissible actions (e.g. motor torques), The function r S x A + IR describes a reward func- tion that is ought to be maximized, while c S x A - R is a cost signal that must remain bounded. The system dynamics, p. describes a probability distribution over the next state, given a state s E S and action a E A. States are initially drawn from the distribution p. and 7 denotes discounting factor. In what follows, each robot-worker interacts with separate CMDP, such that CMDPs differ only in their dynamics, i.e., each robot collects trajectories from a slightly perturbed pt. relative to the nominal model p. Collecting trajectories entails carrying out actions de- termined by policy π (aa s), a stochastic mapping from states to actions. The objective and constraint for each CMDP are defined J'( = Ex.p, ('r(s, a.) and (x) = Ex.p. [Ei= 7'c(st, at)) where the expec- tations are w.r.t. pi, and Tz, policy parameterized by x E Rd.
Remark 5.6. We emphasize that the proof in the stochastic unidirectional setting can be advanced to the bidirectional setting following the derivations of Theorem 4.2 and The- orem 5.4. The convergence guarantees in the stochastic bidirectional setting matches that in the deterministic up to numerical and logarithmic factors.
6. Experiments
Now we test Safe-EF in practice. Below we provide ex- periments on a simple problem with synthetic data which satisfies all our assumptions, and later test our approach in more challenging task of training the Humanoid Robot. We include additional experiments on the classical Cartpole problem and Neyman Pearson classification in Appendix H.
6.1. Synthetic Data
Policy gradient. A common approach for policy search is via the class of policy gradient algorithms (Sutton et al., 1999; Schulman et al., 2017). In essence, policy gradient algorithms use Monte Carlo sampling to obtain stochastic gradient estimates of x w.r.t. the objective and constraints by "rolling out" the policy and measuring the returned rewards and costs along several trajectories. In our experiments, each worker collects data independently to obtain these estimates, which are then used to compute the PPO (Schulman et al., 2017) 7) loss
We begin with simple empirical setup designed to easily verify that all assumptions of Safe-EF are satisfied. Specif- ically, we consider the unconstrained problem of the form (I), where f. = ||A, - bill1- For this objective, the subgra- dient f((x)= = A, sign 66; (Beck, 2017). This choice ensures that all assumptions required for Safe-EF hold. The data (A,, by )=_ C Rdxd x Rd is synthetically generated, where the parameter controls the variability across local datasets: smaller values of s result in matrices A; that are more similar to each other. We set n = 10, d = 1000, and use the Top-K compressor with K- = 10 for all algorithms tested. Details the data generation process can be found in Appendix I. We compare the proposed Safe-EF with CGD, EF21, EF21M (Fatkhullin et al., 2024), and EControl (Gao et al., 2024). For each method, hyper-parameters are tuned (see Appendix I for details) based on function value after T = 1000 iterations, and performance with the optimal pa- rameters is shown in Figure 2. Our results indicate that for s E {0.1, 1.0). EF converges faster than all other algo- rithms. When heterogeneity is large, s = 10.0, EControl is
Ta (s) 7(a (8)
fi(x) = Es,ant
min
AT, (s,
T 8) 7(a
t (s. a1
clip
- 2, 2,1+2
8)
p.
where, A8, denotes the advantage (Schulman et al., 2015) in terms of cumulative rewards, for picking an action com- pared to expected action of Tg. म is the policy with which the trajectory data was drawn and غ is a hyperparameter. Similarly, a surrogate for the constraint (x( is given by replacing rewards with costs when computing the advantage.
7

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
"Safe-EF
CGD
EF21
EF21M
EControl
0.1
1.0
10.0
1.0
0.5
U.D
0.1
0.2
0.3
0.0
0.1
0.2
0.33
0.0
0.1
0.2
0.3
I/Gigabyles / worker
#Gigabytes/ / worker
#Gigabyles/ / worker
Figure 2: Comparison of Safe-EF against CGD, EF21, M, and EControl on synthetic non non-smooth problem. *Safe-EF coincides with EF14 (Seide et al., 2014) in this problem.
Crucially, both fi and gi are functioon due to clip(x,1,1) = max(l, min }.}.
compression. The results are presented in Figure 4, where Safe-EF satisfies the constraints with slight performance reduction, while EF14 violates the constraint. EF21 diverges, possibly due to non- non-smoothness of the objective and constraint. Next, given the same communication budget in gigabytes per worker, Parallel-CRPO fails to converge. This outcome highlights the non-trivial nature of the task, emphasizing that optimal policies in the unconstrained case are insufficient to meet the constraints.
Setup. Unless specified otherwise, in all our experiments, the default number of workers is n = 16, compression ratio is K/a- = 0.1 with Top-K K compression. We parameterize a neural network policy with 0.2M parameters and use a batch size Nt = 1024 to evaluate f; and gi- Moreover, we treat the NN parameters as a single "flat" vector when com- pressing, rather than performing layer-wise compression. We run all our experiments for 5 random seed initializa- tions and report the median and a 68% confidence interval when applicable. Empirical estimates of the objective and constraint are denoted as J and Je respectively. We use a batch of 128 trajectories to obtain these estimates. Further details, regarding the perturbations of models, the reward and cost functions and additional experiments are provided in Appendices H and I.
Number of workers. We analyze the performance of Safe-EF under varying number of available workers and present our findings in Figure 5. Our results reveal two key observations. First, the convergence rate decreases significantly when the number of workers very small. Second, beyond certain threshold, increasing the number of workers yields diminishing performance gains. The latter aligns with our theoretical lower bounds in Theorem E.2, which establish that no improvement in n. is possible in the worst case.
Experiment 3:
Experiment 1: Robust compression. We evaluate Safe-EF with Top-K and Rand-K K sparsifiers and compare with a constrained version of CGD with Top-K sparsifier. To adapt CGD to enforce the constraint, we follow the same approach as Safe-EF and use the switching subgradient method. Figure 3 shows the amount of communication (in gigabytes per worker) required to reach fixed perfor- mance of J, = 7500 as the compression ratio K/a increases. As illustrated, both Top-K and Rand-K significantly re- duce communication costs compared to CGD, with Top-K demonstrating the most robust performance across vary- ing compression rates with about x improvement in communication reduction!
Experiment 4: Effect of batch-size. Theorem 5,4 has certain requirement of sufficiently large batch-size Nty due to constraint estimation process. If this requirement is met, the convergence rate is improved when increas- ing Nr until it reaches the lower bound in Theorem 4.1. To study this effect in practice. we vary the batch size Nr E (256, 512, 1024, 2048, 40963. Our results in Fig- ure 6, indicate that by increasing the batch size from Nv 1024 to 2048, we can see the improvement how- ever, a further increase from Ni. 2048 to Nr 4096 does not yield more improvement. For smaller batch sizes Nr {256, 512]. Safe-EF did not converge, resulting in non-numeric values, and therefore are not presented in Figure 6. These findings are in line with our large-batch requirement in Thcorem 5.4 and highlight the need to design algorithms that are robust to smaller batch sizes suggesingg an important direction for future work.
Experiment 2: Safety. We study the performance of EF in terms of constraint satisfaction and compare it against the unsafe error feedback algorithms EF14 (Seide et al., 2014) and EF21 (Richtárik et al., 2021). Additionally, we compare Safe-EF against a parallel variant of CRPO (Xu al., 2021), CMDP solver that enforces constraints via the subgradient switching method. Our parallel variant of it, indicated as ParO, operates independently on each worker and transmits parameters x to the server without
8

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Top-K
Rand-K
CGD
Sale-EF (Ours)
Paralee-CRFO
EF14
EF21
800
#Gigabytes /worker
10a
10000
400
8000
10
8x
6000
300
9xx 1D
10-2
2000
Budget
1010
#Gigabytes/ worker
#Gigabhytes
worker
Figure Gigabytes required to reach fixed benchmark performance for different compres- sion ratios. Top-K achieve the same per- formance as CGD, but with approximately two orders of magnitude less gigabytes.
Figure Objective and constraint during learning. Budget denotes the level below which Je must remain to satisfy the constraint. EF14, safe baseline, fails to satisfy the constraint. EF21, another unsafe baseline designed for smooth problems, diverges. Parallel-CRPO, safe baseline without compression, suffers from communication overhead. In contrast, Safe-Er EF ensures constraint satisfaction with minimal performance loss.
## Workerss
Niy
16 Warkens
0.7
Niv 2048
8000
8 Workers
#Gigabbytes worker
Ns. = 1096
4 Workers
2 Workers
0.5
22.18 .18
4000
x2.00
x3.11
X2.50
0
0.0
0.2
0.4
0.6
0.8
7000
7200
7400
7600
7800
8000
8200
#GGigayytes worker
Jr
Figure 5: Convergence plots for different number of workers. While increasing the number of workers helps reduce the communication cost, the effect becomes less significant as the number of workers continues to grow.
Figure Communication required to reach a desired per- formance level for different batch samples N Beyond certain batch size, improvement diminishes.
7. Limitations and Future Work
and our experiments indicate it is likely an issue with the algorithm. Primal-dual approaches (Juditsky et al., 2011; Boob et al., 2023) can help mitigate this limitation.
While we make significant progress in understanding non- smooth EF, there are certain limitations in our work. First, assume all functions convex, while Safe-EF EF seems to excel even in challenging, highly non-convex RL tasks. Thus, it is crucial to understand non-convex problems: in a general setting (e.g. Boob et al., 2023; Jia & Grim- mer, 2022; Grimmer & Jia, 2025) as well as in structured RL problems (e.g. Agarwal et al., 2021; Xu et al., 2021; Lan, 2023; Fatkhullin al., 2023a; Barakat al., 2023: Islamov et al., 2024a). Second, our noise assumptions are relatively stringent, and be potentially relaxed using gradient clipping (Nazin et al., 2019; Gorbunov et al., 2024) or normalization (Hübler et al., 2024) techniques, although this is non-triven trivirriial due to constraint estimation. Finally, our algorithm requires large patch-sizes and not sample effi- cient in the stochastic setting due to constraint estimation,
Acknowledgements
Rustem Islamov acknowledges the financial support of the Swiss National Foundation, SNF grant No 207392. Yarden As is supported by the grant the Hasler foundation (grant no. 21039). Yarden As and Ilyas Fatkhullin are funded by ETH AI Center.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

---

Safe-EF; Error Feedback for Non-smooth Constrained Optimization
References
Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. On biased compression for distributed learning. Jour- nal of Machine Learning Research, 24(276):1-50, 2023. (Cited pages 2, 4, 6, and 17)
Adibi, A., Dal Fabbro, N., Schenato, L., Kulkarni, S., Poor, H. V., Pappas, G. J., Hassani, H., and Mitra, A. Stochastic approximation with delayed updates: Finite-time rates under markovian sampling. In International Conference on Artificial Intelligence and Statistics, pp. 2746-2754. PMLR. 2024. (Cited on page 16)
Boob, D. and Khalafi, M. Optimal primal-dual al- gorithm with last iterate convergence guarantees for stochastic convex optimization problems. arXiv preprint arXiv:2410. 18513, 2024. (Cited on page 3)
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine
Boob, D., Deng, Q., and Lan, G. Stochastic first-order meth- ods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(1):215- 279, 2023. (Cited pages and 9)
Learning Research, 22(98): 2021. (Cited on page 9)
Ajalloeian, A. and Stich, S. U. On the convergence of SGD with biased gradients. arXiv preprint arXiv:2008.0000 2020. (Cited on page 16)
Boob, D., Deng, Q., and Lan, G. Level constrained first or- der methods for function constrained optimization. Math- ematical Programming, pp. 1 1-61, 2024. (Cited on page
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: Communication--fficii
sgd via gradient quantization and encoding. Advances in neural informa- tion processing systems, 30, 2017. (Cited on page 16)
Braun, G., Guzmán, C., and Pokutta, S. Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Transactions on Informa- tion Theory, 63(7):4709 2017. (Cited page 4)
Alistarh, D., Hoefler, T., Johansson, M., Konstantinov, N., Khirirat, S., and Renggli, C. The convergence of sparsi- fied gradient methods. Advances in Neural Information Processing Systems, 31, 2018. (Cited on page 4)
Brohan, A., Brown, N., Carbajal, J., Chebotar, Y., Dabis, J.,
Finn, C., Gopalakrishnan, K., Hausman, K., Herzog, A., Hsu, J., et al. Rt-1: Roboties transformer for real-world control at scale. arXiv preprint arXiv:22/2.00881, 2022. (Cited page 1)
Altman, E. Constrained Markov Decision Processes, vol- ume 7. CRC Press, 1999, (Cited on pages and 7)
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points i. Mathematical Programming, (84(1):71-120, 2020. (Cited on page
Barakat, A., Fatkhullin, I., and He, N. Reinforcement learn- ing with general utilities: Simpler variance reduction and large state-action space. In International Conference on Machine Learning, pp. 1753-1800. PMLR, 2023. (Cited on page 9)
Chen, Y., Dong, J., and Wang, 7. A primal-dual approach to constrained markov decision processes. arXiv preprint arXiv:2101.10895, 2021. (Cited on page 3)
Beck, A. First-order methods in optimization. SIAM, 2017. (Cited on page 7)
Compagnoni, E. M., Islamov, R., Proske, F. N., and Lucchi, A. Unbiased and sign compression in distributed learn- ing: Comparing noise resilience via SDEs. In The 28th International Conference on Artificial Intelligence and Statistics, 2025. URL https: / openrevieww net/ forum? d-RRr (Cited on page 4)
Beikmohammadi, A., Khirirat, S., and Magnússon, S. Com- pressed federated reinforcement learning with genera- tive model. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 20-37. Springer, 2024. (Cited on page 16)
Demidovich, Y., Malinovsky, G., Sokolov, I., and Richtárik, P. A guide through the zoo of biased SGD. Advances in Neural Information Processing Systems, 36:23158- 23171, 2023. (Cited page 16)
Bernstein, J., Wang, Y.-X., Nrizzadenesheli, K., and Anand- kumar, A. SignSGD: Compressed optimisation for non- convex problems. In International Conference on Ma- chine Learning, pp. 560-569, PMLR, 2018. (Cited on page 4)
Ding, D... Zhang, K., Basar, T., and Jovanovic, M. Natu- ral policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Informa- tion Processing Systems, 33:8378-8390, 2020. (Cited on page
Beznosikov, A., Richtárik, P., Diskin, M., Ryabinin, M., and Gasnikov, A. Distributed methods with compressed communication for solving variational incqualities, with theoretical guarantees. Advances in Neural Information Processing Systems, 11144013-40299 2022. (Cited on page 16)
Ding, D.,, Wei, C.-Y., Zhang, K., and Ribeiro, A. Last- iterate convergent policy gradient primal-dual methods
10

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
for constrained mdps. Advances in Neural Information Processing Systems, 36, 2024. (Cited on page
Grimmer, B. and Jia, Z. Goldstein stationarity in lipschitz constrained optimization. Optimization Letters, 19(2): 425-435, 2025. (Cited on page 9)
Fatkhullin, I.. Sokolov, I., Gorbunov, E., Li, Z., and Richtárik, P. EF21 with bells & whistles: Practical al- gorithmic extensions of modern error feedback. arXiv preprint arXiv:21 2021. (Cited on pages 3, 5, and 18)
Gruntkowska, K., Tyurin, A., and Richtárik, P. EF21-P and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compres- sion. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 11111-11111100 PMLR, 23-29 Jul 2023. (Cited on page 5)
Fatkhullin, I., Barakat, A., Kireeva, A., and He, N. Stochas- tic policy gradient methods: Improved sample complexity for nedge--non- policies. In International Con- ference on Machine Learning, pp. 9827-9869. PMLR, 2023a. (Cited on page 9)
Gruntkowska, K. Tyurin, A., and Richtárik, P. Improving the worst-case bidirectional communication complexity for nonconvex distributed optimization under function similarity. arXiv preprint arXiv:2402.06412, 2024. (Cited on page 5)
Fatkhullin, I., He, N., and Hu, Y. Stochastic optimization der hidden convexity. arXiv preprint arXiv:2401.00108, 2023b. (Cited on page 18)
Hamedani, E. Y. and Aybat, N. S. A primal- algorithm with line search for general convex- coneex-concave saddle point problems. SIAM Journal on Optimization, 31(2): 1299- 1329, 2021. (Cited on page 3)
Fatkhullin, I., Tyurin, A., and Richtárik, P. Momentum provably improves error feedback! Advances in Neural Information Processing Systems, 36, 2024. (Cited on pages 2, 6, 16, 17, and 18)
He, Y., Huang, X., Chen, Y., Yin, W., and Yuan, K. Lower bounds and accelerated algorithms in distributed stochas- tic optimization with communication compression. arXiv preprint arXiv:2305.07612, 2023. (Cited page 4)
Freeman, C. D., Frey, E., Raichuk, A., Girgin, S., Mordatch, I. and Bachem, O. Brax- a differentiable physics engine for large scale rigid body simulation, 2021. URL http: // //github.... wtchhbccoooocc....ooooooo.oo.ooo wtt.c///o/o////oooco e/bbrax and 43)
(Cited on pages 40
He, Y., Hu, J., Huang, X., Lu, S., Wang, B., and Yuan, K. Distributed bilevel optimization with communication compression. arXiv preprint arXiv:2405. 2024. (Cited pages 16 and 41)
Gao, Y., Islamov, R., and Stich, S. U. EControl: Fast dis- tributed optimization with compression and error control. In International Conference on Learning Representations 2024. (Cited on pages 2, 4, 7, and 16)
Horváth, S., Ho, C.-Y., Horvath, L., Sahu, A. N., Canini, M., and Richtárik, P. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pp. 129-141. PMLR, 2022. (Cited on page 4)
Glorot, X., Bordes, A., and Bengio, Y. Deep sparse recti- fier neural networks. In Proceedings of the fourteenth international conference statistics, pp. 315-323. JMLR Workshop and Conference Proceedings, 2011. (Cited on page I)
artificial intelligence and
Huang, X., Chen, Y., Yin, W., and Yuan, K. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural In- formation Processing Systems, 15:18955-18965 2022. (Cited on pages 2, 4, 6, 25, and 26)
Gorbunov, E., Dvinskikh, D., and Gasnikov, A. Optimal decentralized distributed algorithms for stochastic convex optimization. arXiv preprint 1xXiv:191.007555 2019. (Cited on page 30)
Huang, X., Li, P., and Li, X. Stochastic controlled averaging for federated learning with communication compression. In International Conference on Learning Representations, 2023. (Cited on page 16)
Gorbunov, E., Kovalev, D., Makarenko, D., and Richtárik, P. Linearly converging error compensated SGD. Advances in Neural Information Processing Systems, 33:20889- 20900, 2020. (Cited on page 16)
Huang, Y. and Lin, Q. Oracle complexity of single-loop switching subgradient methods for non-smooth weakly convex functional constrained optimization. Advances in Neural Information Processing Systems, 36:61327- 61340, 2023. (Cited on page 3)
Gorbunov, E., Sadiev, A., Danilova, M., Horváth, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtárik, P. High-probabilityy convergence for composite and dis- tributed stochastic minimization and variational inequali- ties with heavy-tailed noise. In International Conference on Machine Learning, 2024. (Cited on page 9)
Hübler, F., Fatkhullin, I., and He, N. From gradient clipping to normalization for heavy tailed SGD, arXiv preprint arXiv:2410. 13849, 2024. (Cited on page 9)

---

Safe-EF; Error Feedback for Non-smooth Constrained Optimization
Islamov, R.,, Qian, X., and Richtárik, P. Distributed second order methods with fast rates and compressed communi- cation. In International conference machine learning, pp. 4617-4625 PMLR, 2021. (Cited on page 4)
for vision-based robotic manipulation. In Conference on robot learning, pp- 651-673. PMLR, 2018. (Cited on page
Karimireddy, S. P., Rebjock, Q. Stich, S., and Jaggi, M. Er- ror feedback fixes SignSGD and other gradient compres- sion schemes. In International Conference on Machine Learning, 2019. (Cited on pages 5, 6, and 17)
Islamov, R., Qian. X., Hanzely, S., Safaryan, M., and Richtárik, P. Distributed newton-type methods with communication compression and bernoulli aggregation. Transactions on Machine Learning Research, 2023. (Cited on pages 4 and 16)
Khirirat, S., Sadiev, A., Riabinin, A., Gorbunov, E., and Richtárik, P. Error feedback under (L0, smoothness: Normalization and momentum. arXiv preprint arXiv:2410. 2024. (Cited on page 16)
Islamov, R., Ajroldi, N., Orvieto, A., and Lucchi, A. Loss landscape characterization of neural networks without pver-parametrization. In Advances in Neural Information Processing Systems, volume 37, pp. 46680-46727, 2024a. (Cited on page?) 9)
Kingma, D. P. and Ba, Adam: A method for stochastic op- timization. arXiv preprint arXiv:1412.6980 2014. (Cited on page 44)
Islamov, R., Gao, Y., and Stich, S. U. Near optimal decen- tralized optimization with compression and momentum tracking. arXiv preprint arXiv:2405.201 14, 2024b. (Cited on page 16)
Kolev, P., Martius, G., and Muchlebach, M. Online learn- ing under adversarial nonlinear constraints. Advances in Neural Information Processing Systems, 36, 2024. (Cited page 3)
Islamov, R., Safaryan, M., and Alistarh, D. AsGrad: A sharp unified analysis of asynchronous-sgd algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 649-657. PMLR, 2024c. (Cited on page 21)
Koloskova, A., Lin, T., Stich, S. U., and Jaggi, M. De- centralized deep learning with arbitrary communication compression. In International Conference on Learning Represemtations, 2020. (Cited on page 16)
Islamov, R., Horvath, S., Lucchi, A., Richtarik, P., and Gorbunov, E. Double momentum and error feedback for clipping with fast rates and differential privacy. arXiv preprint arXiv:2502, 11682, 2025. (Cited on page 16)
Koloskova, A., McKenna, R., Charles, Z., Rush, J., and McMahan, H. B. Gradient descent with linearly cor- related noise: Theory and applications to differential privacy. Advances in Neural Information Processing
Systems, 36:35761-3577777 2023. (Cited on page 21)
Jaa, Z. and Grimmer, B. First-order methods for nonsmooth nonconvex functional constrained optimization with or without slater points. arXiv preprint arXiv:2212.009927, 2022. (Cited on pages 3 and 9)
Konečný, J., McMahan, H. B., Yu, F., Richtárik, P., Suresh, A. T., and Bacon, D. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016. (Cited on page 1)
Jn, H., Peng, Y., Yang, W., Wang, S., and Zhang, Z. Feder- ated reinforcement learning with environment heterogene- ity. In International Conference Artificial Intelligence and Statistics, pp. 18-37. PMLR, 2022. (Cited on page 2)
Lan, G. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and gen- eralized problem classes. Mathematical programming, 198(1):1059 1106, 2023. (Cited on page 9)
Jordan, P., Barakat, A., and He, N. Independent learning in constrained markov potential games. In International Conference Artificial Intelligence and Statistics, pp. 4024 4032. PMLR, 2024. (Cited on page 3)
Lan, G. and Zhou, Z. Algorithms for stochastic optimiza- tion with function or expectation constraints. Compu- tational Optimization and Applications, 76(2):461-498,
Juditsky, A., Nemirovski, A., and Tauvel, C. Solving varia- tional inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011. (Cited on page
2020. (Cited on pages 3. 5, 6, and 7)
Li, T., Guan, Z., Zou, S., Xu, T., Liang, Y., and Lan, G. Faster algorithm and sharper analysis for constrained markov decision process. Operations Research Letters, 54:107107, 2024. (Cited on page 3)
Kairouz, e. a. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977 2019. (Cited on page 1)
Lin, Q. Ma, R., and Yang, T. Level-set methods for finite- sum constrained convex optimization. In International conference on machine learning, pp. 2p.3112-3122 PMLR, 2018. (Cited on page 3)
Kalashnikov, D., Irpan, A., Pastor, P., Ibarz, J., Herzog, A., Jang, E., Quillen, D., Holly, E., Kalakrishnan, M., Van- houcke, V., al. Scalable deep reinforcement learning
12

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
Liu, Z.,, Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. High probability convergence of stochastic gradient methods. In International Conference on Machine Learn- ing. pp. 21884-281111 21914. PMLR, 2023. (Cited on pages 7, 30, 33, and 34)
Nazykov, R., Shestakov, A., Solodkin, V., Beznosikov, A., Gidel, G., and Gasnikov, A. Stochastic frank-wolfe: Uni- fied analysis and zoo of special cases. In International Conference on Artificial Intelligence and Statistics, pp. 4870-4878. PMLR, 2024. (Cited on page 3)
Lu, Y. and De Sa. C. Optimal complexity in decentralized training. In International conference on machine learning, pp. 7111-7123. PMLR, 2021. (Cited on page 4)
Nemirovski, A. Efficient methods in convex programming. Lecture notes, 1994. (Cited on page 4)
Nemirovski, A. Prox-method with rate of convergence o (I/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal Optimization, 15(1): 229 229-251, 2004. (Cited on page 3)
Ma, R., Lin, Q.. and Yang. I. Quadratically regularized subgradient methods for weakly convex optimization with weakly convex constraints. In International Confer- ence on Machine Learning, pp. 6564. PMLR, 2020. (Cited on page?) 3)
Nemirovskij, A. S. and Yudin, D. B. Problem complexity and method efficiency in optimization. 1983. (Cited on page 4)
Makarenko, M., Gasanov, E., Islamov, R., Sadiev, A., and Richtárik, P. Adaptive compression for communication-efieee distributed training. arXiv preprint arXiv:2211 1.00888, 2022. (Cited on page 16)
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012. (Cited on page
Mishchenko, K., Islamov, R., Gorbunov, E., and Horváth, S. Partially personalized federated learning: Break- ing the curse of data heterogeneity. arXiv preprint WrXiv:2305.18285 2023. (Cited on page 21)
Nesterov, Y. Introductory Lectures on Convex Optimization: A Basic Course. Springer Publishing Company, Incor- porated, edition, 2014. ISBN 1461346916. page 4)
(Cited on
Mitra, A., Pappas, G. J., and Hassani, H. Temporal difference learning with compressed updates: Error- feedback meets reinforcement learning. arXiv preprint arXiv:2301.00944, 2023. (Cited on page 16)
Nesterov, Y. et al. Lectures on convex optimization, volume 137. Springer, 2018. (Cited on pages and 5)
Nutini, J., Schmidt, M., Laradji, I., Friedlander, M., and Koepke, H. Coordinate descent converges faster with the gauss-southwell rule than random selection. In Interna- tional Conference on Machine Learning, pp. 1642-1641.
Moskovitz, T. O'Donoghue, B., Veeriah, V., Flennerhag, S., Singh, S., and Zahavy, T. Reload: Reinforcement learning with optimistic ascent-descent for last-iterate convergence in constrained mdps. In International Con- ference on Machine Learning, pp. 25303-25336. PMLR, 2023. (Cited page 3)
PMLR, 2015. (Cited on page 2)
Philippenko, C. and Dieuleveut, A. Preserved central model for faster bidirectional compression in distributed settings. Advances in Neural Information Processing Systems, 34: 2387-2399, 2021. (Cited on page 5)
Muehlebach, M. and Jordan, M. I. On constraints in first- order optimization: A view from non-smooth dynamical systems. Journal of Machine Learning Research, 23(56)): 1-47, 2022. (Cited on page 3)
Polyak, B. A General Method for Solving Extremum Prob- lems. Soviet Mathematics. Doklady, 8, 1967. (Cited on page 3)
Müller, A., Alatur, P., Cevher, V., Ramponi, G., and He, N. Truly no-regret learning in constrained MDPs. In International Conference on Machine Learning, 2024. (Cited on page 3)
Qi, J., Zhou, Q., Lei, L., and Zheng, K. Federated reinforce- ment learning: Techniques, applications, and open chal- lenges. arXiv preprint arXiv:2108. 1120008.11888/ 11887, 2021. (Cited on page 2)
Nadiger, C., Kumar, A., and Abdelhak, S. Federated re- inforcement learning for fast personalization. In 2019 IEEE Second International Conference on Artificial Intel- ligence and Knowledge Engineering (AIKE), pp. 123-127. IEEE, 2019, (Cited on page 2)
Qian, X., Islamov, R., Safaryan, M., and Richtárik, P. Basis matters: better communication-effiieenn second order methods for federated learning. arXiv preprint arXi::1111.01847, 2021a. (Cited page 4)
Nazin, A. V., Nemirovsky, A. S., Tsybakov, A. B., and Judit- sky, A. B. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 10:1607-1627, 2019. (Cited on page 9)
Qian, X., Richtárik, P., and Zhang, T. Error compensated distributed SGD can be accelerated. Advances in Neu- ral Information Processing Systems, 14:30401-30413 2021b. (Cited on page 16)
13

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
Richtárik, P., Sokolov, I., and Fatkhullin, I. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34:4384 2021. (Cited on pages 1, 2, 4,8, 16, 18, and 41)
Sokolov, I. and Richtárik, P. MARINA-P: Superior perfor-
mance in non-smooth federated optimization with adap- tive stepsizes. arXiv preprint arXiv:2412.17083 2024. (Cited page 5)
Stich, S. U. On communication compression for distributed optimization on heterogeneous data. arXiv preprint arXiv:2009.02388. 2020. (Cited on page 16)
Richtárik, P., Sokolov, L., Gasanov, E., Fatkhullin, I., Li, Z., and Gorbunov, E. 3PC: Three point compressors for communication-efiiiennn distributed training and a better theory for lazy aggregation. In International Conference on Machine Learning, pp. 18596-18648. PMLR, 2022. (Cited on page 16)
Stich, S. U. and Karimireddy, S. The error-feedback framework: Better rates for sgd with delayed gradi- ents and compressed communication. arXiv preprint arXiv: M0XX::99900053390 2019. (Cited on pages and 21)
Richtárik, P., Gasanov, E.,, and Burlachenko, K. Error feed- back reloaded: From quadratic to arithmetic mean of smoothness constants. arXiv preprint arXiv:2402.10774, 2024. (Cited on pages and 18)
Stich, S. U., Cordonnier, J.-B., and Jaggi, M. Sparsified SGD with memory. Advances neural information pro- cessing systems, 31, 2018. (Cited on pages 1, 4, and 16)
Safaryan, M., Islamov, R., Qian, X., and Richtárik, FedNL: Making newton-type methods applicable fed- erated learning, arXiv preprint wrxi:2200.02269, 2021. (Cited on page
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Informa- tion Processing Systems, 1999. (Cited on page 7)
Scaman, K., Bach, F., Bubeck, S., Massoulié, L., and Lee, Y. T. Optimal algorithms for non-smooth distributed opti- mization in networks. Advances in Neural Information Processing Systems, 31, 2018. (Cited on page
Tang, H., Yu, C., Lian, X., Zhang, T., and Liu, J. Dou- blesqueeze: Parallel stochastic gradient descent with double-pass sror-commensater compression. In Interna- tional Conference on Machine Learning, pp. 6155-6165. PMLR, 2019. (Cited on pages and 5)
Schechtman, S., Tiapkin, D., Moulines, E., Jordan, M. I., and Muehlebach, M. First-order constrained optimiza- tion: Non-smooth dynamical system viewpoint. IFAC- PapersOnLine, 55(1))2366441 2022. (Cited on page
Tyurin, A. and Richtarik, P. 2Direction: Theoretically faster distributed training with bidirectional communi- cation compression. Advances in Neural Information Processing Systems, 36:11737-11800 2023. (Cited on page 5)
Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. High-dimensional continuous control using generalized advantage estimation. arXiv preprint (tti::/300.22338 2015. (Cited page 7)
Vogels, T., Karimireddy, S. P., and Jaggi, M. PowerSGD: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019. (Cited on page 4)
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint 17Xiv:170..06347, 2017. (Cited on pages 2, 7, and 44)
Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. Terngrad: Ternary gradients to reduce com- munication in distributed deep learning. Advances in neural information processing systems, 30, 2017. (Cited on page 4)
Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. 1-bit stochas- tic gradient descent and its application to data-parallel distributed training of speech dnns. In Interspeech, vol- ume 2014, pp. 1058-1062. Singapore, 2014. (Cited on pages 2, 3, 8, and 40)
Shulgin, E., Khirirat, S., and Richtárik, P. Smoothed nor- malization for efficient distributed private optimization. arXiv preprint 15..:2502...3492 2025. (Cited on page 16)
Xie, C., Zheng, S., Koyejo, S., Gupta, I., Li, M., and Lin, H. Cser: Communication--fficee Advances in Neural Information Processing Systems, 33: 12593 12603, 2020. (Cited on page 4)
sgd with error reset.
Singh, N., Data, D., George, J., and Diggavi, S. SQuARM- SGD: Communication-ctticiinnn momentum sgd for decen- tralized optimization. JEEE Journal on Selected Areas in Information Theory, 2(3):954-966 2021. page 16)
Xu, T., Liang, Y., and Lan, G. Crpo: A new approach for safe reinforcement learning with convergence guarantee. International Conference on Machine Learning, pp. 11480-11491 PMLR, 2021. (Cited on pages 3, 8, and 9)
(Cited on
14

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
You, Y., Lian, X., Liu, J., Yu, H.-F. Dhillon, I. S., Demmel, J., and Hsieh, C.-J. Asynchronous parallel greedy coordi- nate descent. Advances in Neural Information Processing Systems, 29, 2016. (Cited on page 1)
Yu, H., Neely, M., and Wei, X. Online convex optimization with stochastic constraints. Advances in Neural Informa- tion Processing Systems, 30, 2017. (Cited on page
Zhang. Z. and Lan, G. Solving convex smooth function con- strained optimization is almost easy as unconstrained optimization. arXiv preprint arXiv:2210.05807, 2022. (Cited on page
Zhao, H., Li, B., Li, Z., Richtárik, P., and Chi, BEER: Fast (L//t) rate for decentralized nonconvex optimization with communication compression. Advances in Neural Information Processing Systems, 35:31653-31661 2022. (Cited on page 16)
15

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
A. Additional Related Work
The Error Feedback (EF) mechanism was initially studied in the single-node setting (n = 1) by Stich et al. (2018); Alistarh al. (2017). Subsequent research extended its analysis the smooth convex setting, incorporating additional unbiased compressors (Gorbunov et al., 2020; Stich, 2020; Qian et al., 2021b). The EF21 algorithm, introduced by Richtárik et al. (2021), was the first to establish provable convergence in the large-batch smooth regime without data heterogeneity bounds. Later, Fatkhullin et al. (2024) removed this large-batch requirement by integrating momentum mechanism into the EF21 framework, achieving an optimal asymptotic rate. An extension of EF14, called EControl, was proposed by Gao et al. (2024), demonstrating convergence in both smooth convex and non-convex settings while attaining optimal asymptotic complexity. Recent research has further advanced the analysis of EF, extending it to variational inequalities (Beznosikov et al., 2022),
decentralized communication graphs (Koloskova et al., 2020; Singh et al., 2021; Zhao et al., 2022; Islamov et al., 2024b),
local updates (Huang al., 2023), bilevel optimization (He et al., 2024), differentially private training (Shulgin et al., 2025; Islamov et al., 2025), and reinforcement learning (Mitra et al., 2023; Adibi et al., 2024; Beikmohammadi al., 2024). Additionally, Richtárik al. (2022); Makarenko et al. (2022); Islamov et al. (2023) expanded EF analysis to broader class of 3PC compression operators, encompassing contractive compressors mechanism as a special case of biased gradient descent in the single-node setting (Ajalloeian & Stich, 2020; Demidovich et al., 2023) while Richtárik et al. (2024) improved the constant dependencies the rate of EF21.
special case. Recent works analyzed the EF
EF21 variant of EF has been analyzed in the context of (Lo; -smoohh optimization (Khirirat al., 2024), which is different from our non-smoothness since (Lo, Li) ssmotthnsss implies smoothness any compact and failure examples as in Example 1.2 cannot happen under such assumption. On the other hand, if not limited compact set, the gradients under (Lo, ) smooohhess can grow when |
16

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
B. Failure of CGD and EF21 in Non-smooth Convex Setting
Proof of Example 1.1. Non-convergence of CGD.
Proof. Consider 2-dimensional problem f(()) = || = - f(()) with f(x.) 0. Set the initial vectors
x² (x/2, - and consider CGD (2) with Top-1 compressor.
The proof for the case when y = 0 is trivial. We consider the case when 7 > 0. In this case, the function is differentiable at every point of its trajectory, and for any & 2 0 holds that
(7(-1)
0f(x') {{
{{-)}
The base of induction (t 0) is trivial. For the induction step, make the calculation
(<<1))' (33 21 -TTop- (tI1)
7 -(-1))²
x1+1 x² >g
2
where the last step, Top-1 operator always selects the first coordinate since the entries are equal in absolute value. remains to compute the function value at these iterates f (x²) to conclude the proof.
We remark that divergence issues of gradient methods using biased compressors were previously raised in (Karimireddy et al., 2019). However, their examples only apply Sign operator, while are mainly interested in the behavior of Top-K compressor for distributed optimization. Thus, a different construction is required to capture the interplay of Top-K compressor with non-smoothness of f. Another divergence example using Top-K is shown by Beznosikov et al. (2023), however, their example is smooth, strongly convex and the key effect is different, since their divergence happens due to heterogeneity. Finally, Fatkhullin et al. (2024) show an example of divergence EF21 in the stochastic setting, which is also different since their function is smooth, strongly convex and the divergence occurs due to noise.
Proof of Example 1.2. Divergence of EF21.
Proof. Similarly to the proof of Example 1.1, we consider 2-dimensional problem f.(z) | = - f(()) with f(x.)= = 0. Set the initial vectors x² = (v/2, -1) of = (1, and consider EF21 (3) with Top-1 compressor.
The proof for the case when 7 = 0 is trivial. We consider the case when > 0. In this case the function is differentiable at every point of its trajectory and for any 2 0 it holds that
11111
((=))}
-/= (T-
1 11
x' 1-1tt
2
0f(('))
of
The base of induction (t 0) is trivial. For the induction step, we make the calculation
(-1-tr) -7 (T-1) (-1- (- (1))))
3(-1)*
(-
>(-2)(+1
x 1+1 = x² ---"
2
1+ = o/ ++ (11))) + Top-1
((--1-)-(--))) (1-1et)) (-1)442
(-
where in the last step, Top-1 operator selects the first coordinate since the entries are equal in absolute value. It remains to compute the function value these iterates f(x=') conclude the proof.
17

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
C. Convergence Upper Bound for EF21 in Smooth Convex Setting
In this section, we consider EF21 method with projection
1
- v²
Projected- EF221
71
(19)
++1 -0t + CCV - of).
where 1y is projection operator on a convex set X. This method was proposed and analyzed earlier in (Fatkhullin et al., 2021) for non-convex smooth problems. In Example 1 1.2, we showed that this algorithm is not suitable for non-smooth optimization because it diverges even in a simple convex example like ||>|| While this algorithm was extensively studied for smooth non-convex problems, we are not aware of any convergence results for this algorithm under convexity (with convergence in the function value). To close this gap and complement the failure example of this method in Example 1.2 in non-smooth convex case, we provide the convergence result for this method in smooth convex setting.
Theorem C.1. Let each f((-) be differentiable and L--smooth on X for all = -....,, n. i.e., for all z, y E X, and let f()) be convex over convex compact set X C Rd with diameter Rx- Then for any T 1 Projected-EF21 with stepsize S
Lill-~9l
6 satisfies
2061
R² 7T
(2AoT) 12
))
E[f(x² - f(xx)]]] -
+ log
where Ao= = ((x=))((x*))) +
1 VoL VoL (15 and I, = v Ei= T.3
Remark C.2. The current stepsize restriction is S 2V61 where L is the quadratic mcan of the smoothness constants L, This restriction be further improved by following the results in Richtárik et al. (2024), which requires weighting workers' contributions by non-uniform constants. This leads to the improved step-size (and eventually improved rate) of the form I O1/LL, where L = 1 Σ Li, since L S L always. However, setting the weights requires access to the smoothness constants {Li) which might be challenging in practice.
5
Before move to the proof of this result, few comments are in order. First, if we set y
5 this theorem
2V62
convergence rate for Projected-EFP5 where Ô hides numerical constants and a logarithmic term. This implies Ō L.R.3
convergence rate recovers (up to a logarithmic factor) the rate of subgradient descent when 5 1 (no compression), and is 1/8 times worse in the presence of compression. This is consistent with rates in non-convex and strongly convex settings (Richtárik et al., 2021; Fatkhullin al., 2021). We believe the logarithmic factor can be removed by a more careful choice of parameter À in the proof below. Second, the compactness of the set X' is critical in the analysis of the method, it would be interesting to explore if this requirement can be removed. Finally, the extension of this method to stochastic setting is possible by replacing V (z with a large mini-batch or momentum estimator, however, batch-free version of this method may not converge due to a counter-example in (Farkhullin et al., 2024).
Proof. Since each S; is Le-smooth, it follows that f(x) = ΣΣ fi(x) is L-smooth with L V Σn L,. Next, we follow the proof technique similar Theorem 8 in (Fatkhullin et al., 2023b). By smoothness of f. we have for any z E X'
L 11
(1tt1) s (x²) + (V/ (o').
lt1 x²)
1+1 - 0/1
2
= f fx²) + -00,20* (1 - -z²) ++}+
+
1
1 - x(112 + (Vi (x') - 0. x1 - x²)- -
(L)
L 1
||a - 2²112
27
2
27
(59) + 27 ||0 - ==1?2
1
121
- =1| + ( _= xt)
27
+ +VV (2' - - +1+1 x²) -
-4
L
1
|,0 x²1 2 =+(+,
2 27
18

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
where the last inequality follows by the update rule of the algorithm. Next, rearranging we get
(+) {x²² + 2" ||a² - =1²
27 ||at|1 - ==1² +
1
(Vf (x*) , 1- x²)
+ (VS (x') - -e²xx(t1 - -z)
(1=
-
-/2 1
1
||_0t1 - xz'1 x21
27/
$ fx²) + 27
|| - =|1²
|20t1- - =21?? + (Vf (x") ,2 - x²)
27
+ 2
1106 vV (x')
+ 2%
1
||2441 1-:41-211 =/1²
[/2
L 1
|| =z91
2 27y
fx²) + 1
||-² =1l - + (V/ (x²) 2 12-x") + ? 1|
(x')) - ( T. (
11 (2-22)
) - x'1??
2%
2
2x
where we used Young's inequality b) S ||a||2+ 2 ||b||3 for any a, E Rd. Using (lower curvature) smoothness of f. we derive
f (2(tt) S f(z)+ +
L
||- - =1|² + 2 Vf (+')) - (5
-
1 1|
+
2 2 )
27
[(=) + ? 1/- - =1|
1
7 2n
|10 - V (
27 2n) || - =21?? |102t1-0011
1
where the last inequality holds since 7 S 1/IL. Now we fix some À E [0. 1] and select = (1 - 2) xt + dr. E X, where
J. E X.. By convexity of f(-), we have
A(1 1 1)
[(=) (1-1)((a=²)) + \(
|V
- A)S(x*) ((a..)) (1
(s..))
2L
Moreover, 1|00 -21l = A || - xz1| S RRxx, where Rxx = max max || y/1. Thus, we get for any A E [0.1]
f(x - f(x.) S (1 - -)(((=)) - -f(x)) + x² + 2
Ve (1. 1
27 || - =²122
(00)
For a contractive compressor we have El(C(x) - x1125 (1 00|2=11 for some 8 E (0, 1]. Let Ve, == Ellot ((((t'))
V2 == 1
Ei= Vr, Then
n
V1+1,
Ellg ++1 ||| ElIC(V - g1) vf(
(1 --)) - ((( 112
8
Ellg: - Vf((2)) 12+ (1 2) 8)
S (1 (1-60 8)
1 1+ 2
- -
8)
3L3
1
Ve,1
+
Ellatt1 ++| - 221
2
8
By averaging for ===]] 1,.... we get
Ve+1 S
(1-5) 2
1
8)
V + 5
3L2
Elle - 111
(21)
Define A, A=:= ([(x())))))-- - f(xx)) )) then adding (20) + 3 times (21) and taking 7 S
8
we have
2V05."
27
A411 = Ar+1 +
Ve+1
8
< - -))A, + Vv +
2y
1
8
V +
X2
R2 -
L
1
+
3L2.27 27
FF Flla: - 202112
2
2
27
= - -(1-A)4 +
27
+
7
V1 +
X²
R²x
+
31.2 27
Ella. x012
8
2
22y
?
2
27
8
8
27
X2
S - A)A,- +
1
1/2
+
R²
8
X²
- <11A)) + 7
R²:
19

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
where in the last step we assume the choice À S 6/4. Finally, unroll the recursion for l 0.,,.... T
and setting
À min { 6. N log N
R }.
derive
RRR
AR
AT s 1)- +
Σ 1=0
A)
(1-1))
Ao
7
?
AR
?AAII
))
ARZ
exp(T log(1 A))Aa
S exp
(log
Ao
R³x
?
R2
R2
AAoT
log
7T
yT
R2
20

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
D. Convergence Upper Bound for Safe-EF with Bidirectional Compression
The analysis uses the "virtual iterates" framework, which is often used in the literature (Stich & Karimireddy, 2019; Koloskova al., 2023; Mishchenko et al., 2023; Islamov et al., 2024c). Define the virtual iterates f' == w² ye" with 4 z. Note that then we have gf+1 6 -h'. Indeed, assume that it is true at iteration t, then ++ = (w' yo") 7(6" + 11* - -²) = (w' - -e")- - --h² = 5 - --h"
g++1 = w - yettl
(22)
We additionally define et = w² ---t x², an error that appears due down-link (server worker) compression.
Lemma D.I. For any Rd, the following inequality holds
T-1
T-1 Σ t
Σ ((((') -f()) + Σ
7/c - g(x)] - 2
1100 2=12
Σ
11
>
2 1=
EE
EEN
Σ
||-1=11
1=
Proof. From the update rule (22), we have
| x=|3= || x012 - (1h","" x' =x) + +221119113
Rewriting the above, we get
2-(h', x' x) = 11 x 1-- 11: 2 x² - w²) + -0))
$1 x -1 || 0 2 | 11|2"11
Summing up both sides, we derive
T
T
T-1 2 11th"112+2 Σ 11''11-11"11++ Σ 7114"11-1e")
Σ 7hh x - x) S 11 -112-18T-
x
1
Dropping the non-negative term |: -z/12 and using 20
obtain
T-1
T-1
T-1
2 Σ rh x' - < 1x00 x112+ Σ
1311411 Σ
>/1 Σ
>llh 1-116"1|
1=
1=0
1=
Now we split the sum over A and B. Fort E B we have, h1 = f((a)),iee i.c ht- = (((),, and for t N hy = g((x'), i.c. ht= g' (x*). Therefore, armed with the convexity of and g we have
(f'(z)) - x) 2 f(x²) - f(x), Vk E B,
(o'( - x) 2 g(x') g(x) 2 c- g(x), VKE
Therefore, we have
[x(((=)) - f(z)) + Σ rlc - r(x)] s Σ (x') - x) + En ( x' x))
1EB
tEN
1E8
LEN
1 T-1
$ 1
1
x=12+
Σ
?11n 11
Σ ? 11
Σ -1
We now present the main convergence theorem, providing explicit bounds under appropriate conditions on y and To do so, we need to define x" as follows
Σ
ra'
(23)
E1Er
B
tE8
tEB
Lemma D.2. Suppose that the stepsize 7 and threshold e satisfy
T 1
R2 M2 2T + M
2 - 8
T
+ 22
222111 8z) T.
(24)
2
5,6
21

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Then we have
E I S(x")
+ylE
Σe- o(a"))
S
1 1 2 2
6 - 22 110(1 - 6,),
-
T. (25)
5.6
LIEN Moreover, suppose that (25) holds. Then B is non-empty, i.e. :" is well-defined, and one of the two following conditions holds
LEB
1. | 2: or
2. ,E [EiER (xx) - [(x)]] s O.
Proof. Let use x² in Lemma D.I. Taking the expectation and using the fact that | M, get
T-1
E
s(a')- f(x))
+
Σ c-
S
1
122
+
1
M²
72
+
M
Σ 2
[[e'']]
(26)
2
2
LEB
LEN
t=
M
Σ
>E
[|le
||]
(27)
Using the properties of the compressors
{C:]==>> get by induction" that (with the choice 17 8
1 n
E [1ee+I1p
S n
Ile 113
>
E [lle] + h C,(ct + +
n
1
EE [lle] + 1
i=1
S - 8) (1 +
E []]]]]]]] (1- [ (1 11 M²
Σ 1-
- (1-8)( + (1=-)))+ 61
1 6) + M (1-8)( + 1-
(1(111)))
M 2(1 5)
4(1 - 8)
M
M
8 77(1 - 6)
8
82
C
Similarly, we bound E [[]
E [|
[|a]
= E [|] |oo ++1 x + 113] = E [1 -x¹ C(w - =3)1
S (1 6.) [||u - [1]
= (1 iF [||w* -ro² - =d|1]]] (1 F [lle* -3001137
$ (1 51) i) [|]2 + (1 (1) + ザ ) 2 [110
(28)
Note that
2
E
Σ o 4
E [|EG||| +E [14681P]
71
2
4(1 - 6) M² + 1r2) = 2(124(1 (111-1+++6
(1-)) +82
10M2
<
82
82
82
i=1
*The base of induction abviously holds since || = 0.
22

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Therefore,
E
<
2 11
Σ
E |1oof
(ef + (c)+100))
2E
1
Σ
(ef kp)
- 2(1
6)
Σ
E ||ee + n3ll"]
2
Σ
E
e|et + nt'l"]
1=1
8
8 Σ E [|
[[]=
17
n2
1=1
40A2
82
Then we continue (28) as follows
[11 - (1) (1)))(11 - 22² 40M2
[[le++]]]
[1]]
<
+ n
82
1=0
(1 81)(1 + -- 40M²
(1 - (1)(1 + 1)
82
S 7 160(1 - 62)
6262
i.e. E [[le'|]] S C and EF [[(21]] S B. Therefore, we continue (26) follows
E
Σ
f(+)) - f(x")
+
7 Ee c c- E--g(z))
S R²
1
2 M222T + 2222
2v1 - 8 T
IEB
IEN
10(1 0z)
+ M22² 7
T.
(29)
5.6
Assume that B 0, then we have using the fact that g(x*) 50
1 R²
T
T-1
2/1 1+ 8 T + M2y² 4
10(1 5%)
Tye S 2
M2
Σ 72
+ M
T.
8,5
==:
t=0
This contradicts the assumption of the lemma (24). Therefore, we must have B * 0. If we have
rE
- ((x*)
00
LEB
then part 2. holds automatically. If we have the opposite, i.e.
EE
ES(rt) - s(x"))
[(x')
>0,
LIEB
then from (29) we have
< R² 22 M2²² 2
1
4
10(1
8g) T.
EE
Σ (c
9(x*))
T +
22
5.8
LIEN
Since g(x*) < 0, we have c e- g(x*) 2 c. Therefore, we have
1 R²
M27 MP ? 2012 T 22 4 10(1 0,) T.
1 2
E
70
(30)
5.6
Assume |B| 2, this means that W
T Therefore, from (30) derive
2
T
1
1 2 2 5
4
10(1 - 8,
ve
S E
Σ 7c
- R² +
8 T
2
T.
2
2
2
8.6
LEN
which contradicts (24). Therefore, |B]
T 2. i.e. part 1. holds.
23

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Now are ready to prove our main theorem.
Theorem D.3. Suppose that ? and e. are chosen such that (24) holds. Then we have
R²
vI 6
10(1 6z)
E [[f(T)) f(xx))
Tp +
M2y 4M3
8M²;
8
6g0
E [g( Sc
Proof. We start by using the results of Lemma D.1. Using convexity of f and Jensen inequality we get that if part of Lemma D.1 holds, we have
E [f((") f(x")] S O.
If part does hold, then we must have | T. Since g(x*) 0, from (25) we obtain
R² + y2y 2T + M²²² 2/1 1 T + 2 44 10(1 6z)
yE
Σ [(x')
-(x²)
1(x')
T.
2
8.6
LIEB
This implies that
(1 R2
2
4v 10(1 8%)
-((("))-(<7)) -
+ 2
M222T + 2
T + M
T.
7T
5.6
R²
5
SM2, V 10(1 8g)
+ 2 , 4M²
7T
8g6
Since g(x") S for t E B we get from convexity of and Jensen incquality that
E [g((T"] S
Corollary D.4. If Ry/8.8 MVT
and c
32RM V5,8T
then we have
32MR
E [f((x)) - f(x')
V8T
32MR
E [g(())]
V8T
Proof. Note that yc
RyJ.6 32RM
32R²
i.c.
2 yc 16R and
M T V8,0T
T
1
R
M2
2 +M22²
2 2222211
2
10(1 5.).
T
2
d.6
1 Rº + 2
R²80
2 I
8 R288
+ 2 4v 110(11 8%)
R2858
M
22
2
MºT
8 M
5.6
M
1
- + 7 R256, + 2R VI 56, +4 44/10(1 R2) - 16R?.
Therefore, (24) is satisfied. Hence, we have from Theorem D.3
H²
+ Rvo0
Rvo VI-6
Rvo.0
V10 82)
E [[((T")
+ 4M
+
8M2
RVS,5T MVT
MVT
MVT
8
MVT
856
MR
MRV8,5
4MR (1 - 8)8,
8MR 10(1 6.)
V
VT
V8T
V5.8
32MR
VoLōT
and
9(07) sc= 32MR
Vo.oT
24

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
E. Lower bound under Communication Compression for Non-smooth Convex Setting
In this section, we establish a lower bound in non-smooth convex setting, assuming workers can compute exact subgradients fa)x) e (z) or g' (x) E Ög(z), and the compression is the only source of stochasticity in the training. First, in the next subsection, we provide some preliminary background on the class of zero-respecting algorithms following the exposition in (Huang et al., 2022), and justify that our Gafe-EF method satisfies this general property. In the subsequent Appendices E.2 and E.3, we provide the proof of Theorem 4.1.
E.1. Zero-respecting algorithms
Let [ denote the j-th coordinate of a vector E Rdd for j [d], and define prog(2)) if = O;
prog(z) 0
maxig [m], # 0}, otherwise.
Similarly, for set of points X = (21, J. we define pxog(X) m prog(z). It holds that prog (X UY)- max (prog() X), pY))(Y)) for any X,y _ RR, and prog(X) (X) prog( X) for any X C C Rd.
We examine distributed learning framework incorporating communication compression. For each worker i and time step t 2 0, we denote by of and 2 the points at which worker i queries its subgradient (of f: and/or 9:) and function (of fi and/or gi) oracles, respectively'. In more detail, Oi, (Vi. 24) returns pair of the subgradient of (v()) and the function value fi(2{), namely,
(IG)). E Oo,, = (O s.y, (vl, 2f), Og, (vl. 2f)),
where M((t)) E Of(()() an arbitrary selection of subgradient element from subdifferential of fi at the point vf- We assume similarly the oracle for each constraint function gt. Oz,,. (wt, 24) which returns pair (gl gx())) where d(((() (g)(1(). Additionally, æf represents the local model updated by worker after the t-th query. is important to note that y and of are not necessarily equal to the previous local model 2;- instead, they may serve auxiliary vectors.
Between the (t- - 1) and t-th gradient queries, each worker is allowed to communicate with the server by transmitting (compressed) vectors. For worker i, we let -r denote the set of vectors that worker i aims to send to the server, i.e., the vectors before compression. Due to communication compression, the vectors received by the server from worker i, which we denote by Vr, - are the compressed version of V - = C2 (V:: with some underlying compressors C,. Note that VI - is set that may include multiple vectors, and its cardinality equals the rounds of communication. After receiving the compressed vectors from all workers, the server will broadcast some vectors back to all workers. We let V denote the set of vectors that the server aims to send to workers. Since consider the setting with unidirectional compression only, then V 5-
We now extend the zero-respecting property (Huang et al., 2022) to distributed learning with communication compression with functional constraints.
Definition E.I. We say a distributed algorithm A is zero-respecting if for any 2 0 and 1 s A S d, the following requirements are satisfied:
1. If worker queries at y and 2 with [y]] o O, then one of the following must be true:
there exists some 0 < s < such that [z]] # 0:
there exists some 1 < s < such that [O),,(vf]] & * 0 or (O ) + 0;
there exists some 1 < s < such that worker has received some v E Vi with [u]k + 0;
there exists some 1 < s < such that worker has compressed some Dt - with [o]a + 0:
'We consider deterministic oracles only. 'The compression is performed vector-wise.
Tf g. = Co(V
25

---

Safc-EF; Error Feedback for Non-smooth Constrained Optimization
2. If the local model of of worker after I-th query, has [<]]l + 0, then one of the following must be true:
there exists some 0 Σ s < such that [2]] * 0:
there exists some 1 S < such that [v + or (O (vx (uf)) + O;
there exists some 1 _ $ < such that worker has received some v E Vo- with [u]k 7 0;
there exists some 1 S 8 < such that worker has compressed some V -s with [v]x F 0:
3. If worker aims to send some v E V wi-+ with [e]a + 0, then one of the following must be true:
there exists some 0 S s < such that [>=]| * O;
there exists some 1 - s < t such that [Oi,,. (vf))a + 0 or (Oi.g (V])) * O:
there exists some 5 8 < such that worker has received some v' E Vo with [e']a + 0;
there exists some 5 8 < & such that worker i has compressed some v' V Vs with [v'] 0;
4. If the server aims to broadcast some v E V with [u]a * 0, then one of the following must be true:
there exists some S 8 < & and S S n such that the server has received some o' V with [e'] # 0;
Safe-EF is zero-respecting. Fundamentally, the zero-respecting property ensures that any increase in the number of nonzero coordinates in æt. v or other related vectors at worker stems from its past local gradient updates, local compression operations, synchronization with the server. Likewise, any expansion of nonzero coordinates in the server's 's vectors must result from receiving compressed messages from workers. Notably, this definition explicitly prohibits expanding the set of nonzero entries through fuucciin value queries of fi and/or gi. Therefore, our algorithm class excludes zero-order methods. Nevertheless, function values can be used to set a stepsize or coefficients in linear combination to compute local model xt. For instance, in Safe-EF function evaluation 9, are used to define an update direction:
h f (x (g(x²) S c) + s(xx") (g(x²) > c).
In this case, function values are only used to choose which of the directions, fz(²)) or g((x*), to follow, but they cannot be used compute the update direction itself.
E.2. Lower bound in unconstrained case
We first establish the lower bound in unconstrained setting when g(z) O, which is the most challenging part of the proof. Without loss of generality, we assume that z Given local loss functions ( S FR,MS, compressors denote the output of
(C.) C C()), and an algorithm A E A(cyr, to solve problem (1), we let & (A. algorithm A using no more than T' subgradient queries and rounds of communication by each worker node. Let us define the minimax measure in unconstrained case as
sup E E[S(EAAED) ACA He. CC(5) (A..,,
inf sup
(31)
In (31), we do require the compressors {C, to be distinct or independent. We allow the compression parameter to be accessible by algorithm A. Let [z], denote the j-th coordinate of vector Rd for j [d], and define prog(z) as
=
prog(x) = maxisjsai [zly + 00} otherwise.
In other words, prog(z) outputs the largest coordinate of input x that corresponds to non-zero entry. Importantly, prog(1) satisfies prog(A' X U U)) max(prog(X'), prog()'} for any X, Rd, and prog(X') S prog(X) for any X C X Rd (see, e.g., (Huang et al., 2022)). Now we ready to state and prove the lower bound stated in the unconstrained setting.
Theorem E.2 (Unconstrained setting). For any R, M O, 2 2, 8 S 0.3, T 2 8-2 there exist functions (fi) S FRRM compressors { S C(8), oracles 1O and the starting point z0 such that for any first-order algorithm A E N(c, run for T iterations from x., satisfies
MR VTT
E F(BARt)
min f(x) aERd
2
Proof. Step 1. Let us fix some and define = for E Rd || F).
Let h: Rd - RR be defined as
26

---

Safe-EF; Error Feedback for Non-smooth Constrained Optimization
max 24 + 2 15isT
if E S, max 2j + PR
Mxx)
C
|211
if $ S.
1S/ST
Here we assume that T S d. The constant C = MVT
1+ and μ= R(I+VOT)
2M
This implies that C = RpyT 2
Note that it is
never optimal to have [x*], * O for T < S d, and by symmetry, we know that
[a*]]
[x-]--
Ruy'T Thus, as long as C 1 2
the optimal solution x" and optimal value of the problem f== ming f(z) are given by
{ 0 for T' j S d,
Af for STST, and ʃ"
C
[x
2pT
One can show that the function h convex. Indeed, this is because taking max and/or a sum of convex functions preserves convexity. We consider the following subgradient oracle On
(((x) = 1oT + Ce 1R [R |
if E S, otherwise,
Cee
where k is the smallest index such that [z]} max Jm]y We set = with O, = On for all E [nt]. Note that the first 15/ST
x part of the subgradient (either jaz or juR |||=||| reach more non-zero coordinates due to the second part Cea only. However, it might increase prog prog(O,(z)) at most by one, namely.
is proportional to x. Therefore, the algorithms are hampered by oracle O₂ to
prog(O,(x)) S prog(x)
(32)
Step 2. Next, we assume that each worker i uses Rand-K K compressor with K = [dō Moreover, we assume that the randomness of the compressors shared among workers. Then this compressor belongs to C(6). This step ensures there no speedup of the final rate in the number of workers n1
We let vr be the vector that workers receive from the central server in the t-th communication (similar definition is used for -)) and let xf be the local model that worker i produces after the i-th communication round. Recall that algorithms satisfy the zero-respecting property. Therefore, we find that each worker can only achieve one more non-zero coordinate in the local model by local subgradient updates based on the received messages from the central server. Thus, we have that
Step 3.
prog(a)) S max (M +
(33)
15a5t
By further noting that vector wn sent by the central server can be traced back past vectors received from all workers, have
prog(vi_ow) & max max prog(u. -o))
(34)
Isestisisn
Combining (33) and (34), we reach
prog(z!) < max max prog(ve,-o) + Isettisisn
(35)
Step 4. Let
à E span (1=² StsT.
be the final algorithm output after T subgradient queries on each worker. By (35), we have prog(i)= S max max prog(vi..-aa)
1555 15i5n
By Lemma E.3, we have
P( max max prog(uy 2 T -T-1) 1) - exp (le 1)T(d6]/- 1). ETST iSiSo
Note that if prog($) < T then we have
{() - fr 2 -f- C2
2nT
Therefore, we have
E - (1 exp ((c - 1)T dō) //d 1)) O²
TT
27

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
we let d [578] and T to be less than fz. have
d = [T6] ž 5T8 1 2 4T8 + 82
-12
478
8 24
Then it is easy to verify
(e - 1)TTdd//d///- T 1)T(dō + +1)/d 1-T
(e 1)T8 + 1--If
+
S (e 1)T8 + (c 1) Tb
+1 T
4
(e 1) 5T8
+ +1-1
Note that since 8 < 0.3 and T 2 zz have
(e 1) 5 + 1 - +
(e 1)56
11_ -0- (ee-1)5-10 1
1
2 4 6.25
~ 3.95 > 2.
Since the last inequality holds, then we have
(e
- 1) 1)576 + 1 T < -1. Therefore, this leads to
C
M
1 R(1 + VOT) = ( MR
Elf(#)- - 1 2129 Ω
S
2nT
(1+ V8Ty2 2 2T
2M
V8T
VT
Lemma E.3 (Technical lemma). In example used in the proof of Theorem F.2, it holds that
P( max max prog(u", (...))) 2 T 1) S exp ((e - 1)T [d66 + 1).
181ST 1515n
Proof. Note that at the 1-th round of communication where t StSt T, the non-zero coordinates of (b,;)) the vector that to be transmitted by worker the server before compression, are achieved by utilizing previously received vectors (u(") I s S t 1} and local subgradient queries. Following the argument Step 3 Theorem E.2, we find that worker i can only achieve
non-zero coordinate in (t.+) by local subgradient updates based received vectors (u 1 < $ Σ - 1}. Therefore, it holds that
prog (1,)) < max prog(u! w +1 max max prog(ue,-.) + =: B(t-1), 15-S--11SSnn
(36)
15a5t-1
We additionally define (0)) 1. By the definition of B(O) and that prog(ut,,-s) prog("
(37)
it naturally holds that
B(t-1) < B(
max max prog(u ( + IssSnisisn
max
B B(t-1)
max prog(u (1 -s) + $1] Isisn
(37)
< max
((t-1)
max prog prog(u -25 + IsiSo
(36)
I max B(L B(t-1) + +1] < B(1 +1.
(38)
Therefore, one round of communication can increase B(9) at most by 1. Morcover, (38) implics that B(*) = B(t-1) + 1 only if max prog(va:))))
(t,x) max prog(ve.. Let k: max prog(vee) (t..) Recall that the compressors {C] share 15i5h
1Si5a
15v5
max prog (3,;;))))) k is equivalent to that the randomness, we therefore conclude that having max prog(vi, 1s#5 1
coordinate index is chosen to communicate in communication round f, which happens with probability -- Therefore, we
28

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
have
P(B()) = B(--1) + +1) 2 P( max prog(eu,-s) = max prog igi5n
(oog(u::+)) (f,4)
ggign
K d'
P the coordinate index max prog (2) is chosen at round t) ss
=
Let define the event E (the coordinate index max prog( (1.+) 1si5n
Do 44) is chosen at round (}. Since the compression
1EE) are i...d Be( ( random variables where 1()) is the indicator function. By the above argument, also have B0b) B(- I 1(E") for any 1 T. As result, reach by Markov's inequality
happens uniformly at random, we have 1(E()),....
P(B(T) 2 T)
P(e 2
1132 exp
exp B(T))
T
= -E-FF
B(O) + Σ (B())
-B(--1))
B((-11)
exp
S Se
B(0)
E Texp (1(E)))
[=1
(1 d'
K
1 + K
d ee)
(T-1)
K
(e 11)
d
S <e- 1T-1)
(e-1)///d
This concludes the proof the lemma.
E.3. Proof of Theorem 4.1 (constrained case)
Now we are ready to extend the proof of Theorem 4.1 1 to constrained setting based on the construction in Theorem E.2. Notice that the function classes FR,M and GR.M for objective and constraints have the same properties: convex with M -bounded subgradients. Moreover, the construction of Theorem E.2, all functions fi are identical and equal to f. Thus, we can set (z) fx) min fzy for all E [n.] Then such problem is in the class H.RMM by construction, and it has a unique feasible point, x=", which also coincides with the solution to unconstrained problem minzeR* f(x). Since
af((x) dg: (x:) for any E RR and all E [mi]. the trajectory of zero-respecting al algorithm on the unconstrained problem min fxx) and the constrained problem
min f(x)
s.t.
9(x)
zER
identical. Therefore, the statement of Theorem E.2 implies the lower bound Theorem 4.
29

---

Safc-EF; Error Feedback for Non-smooth Constrained Optimization
F. Convergence Upper Bound for Safe-EF in Stochastic Setting
We first recall a standard concentration inequality result for sub-Gaussian random vector.
Lemma F.1 (Lemma C.3 from Gorbunov et al. (2019)). Let {&x k=1 be the sequence of random vectors with values in R" such that
E [Ex Ek-11...., E1] = 0 a.s. V (KE...... N):
and set SN = Ek=1 Sk. Assume that the sequence is {Ex] are sub- sub-Gaussian, i.e.,
E [[exp(1ls<I)) 1//02, Ek-11...., E1 I exp(1) a.s. Vk N),
where ONN. are some positive numbers. Then all 2 0 we have
P |Ss12 (V2+ V26)
Σ c
<xx((-1/3).
We first establish several lemmas.
Lemma F.2. Assume that Assumption 5.1 holds. Assume that the compressors {c,) are deterministic (e.g.. Top-K),
Then for all t 2 0 and E [n]] we have I| 1(1-5) M
8a
Proof. Using the properties of the compressors {C,) i= we get by induction that (with the choice 1) 2(1-5)
5
1
++1
1|2= Σ
1
lee + h1 - -Ca(e) +bil?
71
lee + h1ll?
1=1
< (1--0) (1-08 () +1) 1 Σ
lej ++(1111110 - -8) (1 () M²
n
1=1
1
Σ [11 6)(1 + (1(+1)]*= 6)(1 1
1=0
(1 5) 11
M (1 (1- 0)(1 + 11
M = 2(1 - 2(1-))(1 + 1
4(1 - 6)
M <
M2
(1 - 8)
77(1 - 8)
8
82
which concludes the proof.
Theorem F.3. Let Assumptions 5.1 and 5.2 hold. Let B E (0,1) be the failure probability. Suppose 7² S 32M0
For
every 0 < t < T - 1 we have
T-1
80
T-1
[(exp(S()
Fil S exp 2
Σ
22
Σ Euf?²)
NN
where St is defined in (44).
Proof.
We use the same definition of J established in (22):
xt x¹ - 7e" where z0 = 20.
(39)
We start by extending the norm of || - ==
|
x: 2 || - x= 2 (h', 3² - xx)) 7 2 ||11 1|2
|| x=1 2-
27 (h' x² - x²) 27 ,z - x²) + + ?
Rearranging terms gives us
27 x¹ - x) = 1 2112 1 2 37 x² 12111112.
(40)
"The base of induction abviously holds since ||e||| - 0.
9hiis restriction is nerded to apply Lemma 2.2 from Liu et al. (2023).
30

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
Note that for / E W we have ht from (40)
1. n Ei= da(xa, ),), and for L E B we have ht = - ((xx,,))) Therefore, we get
27
(g (. x² - 1) E EN)+ + 27 n
Σ
Ei a') - -z)1(t B)
7
i=1
|
x|| | | x1 22"
2
|gg((" 10 E (N + -"
Eis( () (1(E B)
1=1
-|
12/l== -z))
27
+ 27
Σ
ll'((z') - - ((()t))))((()E))))))
i=1
27
n
2y²
+
E1(((E") B3 +
> [lf(((²)) - fi(o'. M(
(41)
n
Note that we have
Kh', 55 - S |1:1111711'11
SM 7 2/1
M = 2 -
8 7M²
8
Therefore, we continue from (41) as follows
27
24
-
(() - z) E B))
n
n i=1
4v
||
x
| -x
2
72 22 + + M²
8
272
n
lo.( (laaa.))l((tee..e N) + 272 n
> fx())) - (<<',=))11 (teet B).
+
n
n
We add and subtract full subgradients and derive
27
2
n
(1(xx)) x' E + Σ 2') B)
n
4vI-6 5
< || x12 1 - 2
22 + M2
6
27
(9(( - si(=', ( x' 2)1(t E NN + 27 (f((')))((a))
- f(lx' (0(''",)))''aa0a e B)
i=1
2,2
24² Σ
Σ Ilo(((a)) - Gio''
+
- - f((5",)0PP1( E B).
n
1=1
Now we use convexity of 9r and Si to derive
27
27 > - ((()))-(()))((e))))
(x)(x') - (()))
+
1=1
4v1 5
< 1| x1 111-11 2
72 222 M2
27
(x*) - g/0x' ()), x² 1) EN)+ + 24
Σ -(((( -2)/0=t e B)
n
2.2
2-2 > [f(((()) - e B).
(o)) - (11a',)))131(t E (N) +
31

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
We add and substract
1 E (x(,,, to obtain n
27
" 2y Σ(i(d) - ((()))) B))
(x', ; - ( +
n
1=1
|| x1 || x1|2+ 4
M² M2
8
27
(gn(a") - , ,t) - x1) (N) + 27 Σ (J((z') S((',, -x)1(1 e B)
27
+
Σ (gi(s),
- -
Ello'(2 - g( ())11((tt 27² n
n
Σ
((a)()))11 e B).
n
n
Now set x x² Since ni
EE= 4) 2 fort E and gnd") S get
27
4v 8
2/c1(t EN +
E(f((t)) - -(f((=)-((())))) f(())) - || x1| 2 + - -x11-
8 7 ?2 M²
27
(g((x²) - 27 n "(f((e)) - (((e.E)), -))((t)) E B)
<
17
n
27
+
(gi(x', (t)
2x
Σ (1o((x)) - -(((' (1 + 27 Σ ((),) B)-
+
n
i=1
Let us denote w/ = ((4)) - gi(x' and uf = f((x)) f) Then we have
+ 27
Σ (((0)~((xx)))) B) - || - x +|++1|+++++-11 x²1
4v1 1 ô
2 -2-2
n
yy
2 ((
x
- E B
n
n
2y
27² Σ [2tt 22² Σ
+
(1 - ((
I B).
We add and subtract Fz in some terms to obtain
2 ( M) E(f((t)) - f((x)) 111 x² x²1
2x
4v1 - 6
72 M² -2-2
8
27
n
(wf F² x EN) + 2y Σ
12
i=1
i=1
+
n
n
W/ - E B) +
27 n
Σ
(1/ -1'--F'1(( E B)
n
n
2y
2x²
2n²
+
-alla" N) +
Σ
11 B).
71
32

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Using (39) we derive
21
E
NN
2
Σ -(1("') - (M()))(() 13 x 1|++
x=1
4v 1V1+ 6
M2 -272M²
Y
x)
27 71
Σ (W(EEE)((EE)))
71
i=1
i=1
27
27"
EUSEE
+
11
+
27
n
-
272 n
+ 27² n |ut (
n Σ (1 E B).
n
n i=1
1=1
Since
||//11
||
2M get from Lemma F.2
2701 (t EN)+
27
[((())) fi(x")) B) | x" x²112+135++11
x
4V1 2 M² 22²
n
27
272
2
<
(W
x x (((E
2M
M1(tEN)
8
i=1
i=1
27
27
2V1
27 Σ
+
(W x1) +
2M
M1 E B) +
(g. - =((=)))((())))
n
5
27 1u
2-2 n
1//131(tE B).
n
n
Rearranging terms, we obtain
2ycl(tt E N) + 27
(fi(=)) - f((x*)) B) - -15 -111++113+11 x=1 12v1 8
72M2 22
27
n
(w) T
1(( E A²)
27
W/ )(( E B)
27
Σ
(a
- ( -
7
n
n
2n²
27²
|u +
Σ 1=1
11 B).
n1
1=1
Now we define
2
12 I
A = NN)+
Σ - B) -0'1-+1-- x
2 2M M2. (42)
n
8
i=1
In the case & E N, we have
A
27c
| xx
-111|++|
xx 2 12v1 - 8 222 -27222220 M²
n
27
27
n
2-²
<
Ww F x²)
+
(ot ( 9i(x')) +
|
n
n
n
1=1
In the case E B, we have
A,
2 n
Σ (1((2)) (
n
|| xx 13
x01 1|
12 1 6
2 M² 222
8
27
272
Σ
(t, - -x)) +
11112.
Following Liu et al. (2023) we define Z. as follows
Z, = wy, Ar ve v2117 - x=11?
(43)
33

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
where we and oy will be defined later. Next, we define
T-1
S =
Σ
Z,
(44)
1=t
Let us define the natural filtration F, == (Eo, ..... G--1). 1). We will show by induction that
[exp(S:) Fil I exp 48M
I-1
Σ
W
8o nN 1=t
Σ
T-1
wfn
1=t
The base of induction is trivial for / since ST Assume that the statement holds for E {o,...,, T 13. We have
E [()
FF] = E [exp(SI+1 + Ze) Fil
= E [L [exp(S++1 + 2e Fe+1l Fi].
We now analyze the inner expectation. Conditioned on Fe+1 we have Ze fixed. Using the inductive hypothesis, we derive
T-1
E eexp Zz + S(+1) Fe411 S exp(Zi) exp
48M 2
Σ
un?
lmt+1
Therefore,
T-1
E [exp(Ze + St+1) Fil S E [cxp(Z,)
[i] exp
48M
Σ
wun?
(45)
1=t+1
From (42), (43), and assuming that i E we have the following bound
2
12 - 72M
exp( = exp
10:
we || - -xx1= += - x011-- we
2
- -vel="'=x111
n
< exp
1
Σ (w - -2)) + 27pure >
|w0 2ywe
Σ (g;(z', - gi(x')) expl-22/1i5 x x²11²).
Next, use Lemma 2.2 from Liu et al. (2023) (with 2 (Ft x²) and b2 = 2y for the terms with wf, and with
a 2rws
1 for the terms with ge(x", , 9x(x²)) )) and independence of function and subgradient evaluations x²) 2
E
exp
2
(w Ft
| 2+
2ywe
Σ Coil ( - -((t))) I 1F
n
n
2 4M2 =12
272 n
2 ot 1)
< cxp
n
4M
+
n²
n²
Niv
(48-2 w?
oi
exp
2
x
21122+222 22
(46)
n
Niv
Therefore, from (45) we derive using the definition of 4872w? .22
uz
n
M² 2
8a T-1
E [exp(S.)) [F] S exp
11
18 x 11-1|++4,1 +22M
Σ
wn? 2
Σ uz72
nN
1=t
1=t
T-1
80 NN
T-1
exp
48M
2
Σ
fa
1=1
This concludes the transition step in the case & E ..
Now we move on to the case /. E B3 The derivations are similar, but we do not have function values. Therefore, instead of
18-22u
80 NNv
1 +
wi??
exp
in (46) get
2 M - =="]|=44
exp
n
Therefore, the transition step holds in both cases.
Corollary E4. Let B3 (0, 1) be a failure probability: Suppose the sequence {we) satisfy the restrictions of Theorem F.3
34

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
and W/ + wz M < 1/ Let the stepsize
Then with probability at least 1 B
12v1
Σ
+ Σ ((f(x)) - f(x')) - C₁ log
+ 1
x²
50 +
T
3
6
IEN
TEB
80
+
Ty
CinNE.
1872 M²
where C
11
T-1 w6?? + Proof. Let 48A12 E
s T-1 u??? + log 3.4 By Theorem F.3 and Markov's 's inequality, we have
aN:r
P(S. 2 T) I P(exp(So) 2 exp(T))
$ exp( -T)E (exp((o)) So)]
T-1 80 nNrr 1=0
< eex((-T) exp
exp 48M
Pwe
Σ
72 w/t
1=0
3. Note that since WA + 0 S w by the assumption of the lemma
So
7+
T-1
Σ
w. (2 E ((())))))((((teee))ee( B)) (v. + wr)l x= =1 11 xx"
2
12v1-6
?2M²
8
T-1
2yw: (cI(t N) + ((==)) B))
Σ
(w [ 2"112-wi| -
We 2+ 12v1-
72 ?2
T-1
2yw, (cI(( E N) + (f(x²) - -(xx)))((EEB)) - wollx x01/++uy 1157 - x=1
12vI-6
Σ Wt
2+ 8
T22²
2yw,, (cll(t E N) (f(x') - f(x*))[((e B)) wollz x 201 +ur 15 x=11
T-1
12 1 - 8
Σ Wi 2+
?²M²
35

---

Safc-EF; Error Feedback for Non-smooth Constrained Optimization
Therefore, with a probability of at least 1 33 we have
2ywcc+ + Σ
27 2)wr(f(a')) f(x"))
WT-111 =x²11
ANN
AEB
T-1
12v1- 8
I So + woll> - x +²1
Σ
Wi
2
M²2
8
1=U
S 1og
1 + wb 12 - x 221
+2 +
48MM
2M
12v1 8 M²
Σ
we +
80 I-1 n.v
Σ wî??
3
t=0
1=0
We need satisfy the following restrictions on Wp:
W/ S
32>² M
W/ + 4872
w 11-1-
n
Let
48 M
C
(47)
11
Then we set wT-1 + 4852362
Next, we set w such that the second inequality holds with equality, namely,
20T
2 w = we +
C1 w
W/- 1 Wy
n Indeed, the base induction holds by the choice of wT-1 Assume it holds
We can show by induction that w. S f, let us show that it holds at well:
C1 -
C1
Wt-1 wt +
T :
1
C
C1 + t
T(C + Cit)2
(G1 (C)++ (t-1)
C 1
(1-1))) G1)
(1+
+ G C+ G - (C1 + C 1))
+
G G (t (t-1) 1)
C 4
(t-
Now we show that the first condition is satisfied as well
wry wt 72
7
n
n
<
T GIT T
48
4 32M
n
Therefore, with a probability at least 1 - 8, we have
Σ
2ywic+ + Σ 2,00 f(x')) + WT WT--11T x11
EEN
EE
< log
1
+ Wol 1/0 - x x2122t²2 48M² + 2M 12 - M²
T-1
Σ
We +
80 T-1
Σ 2
(48)
3
N.
Since wr-1 20, and
S w4 5 J. have with probability least 1 - B
20
Σ
+ C tEB
Σ
(f(x') - f(x"))
C1
LEN
< log
1
+
1
11000 - x² +
(50M2+
12v1-8
M
T-1
807 T-1 NN
Σ
w 7
(49)
3
1=0
36

---

Safc-EF; Error Feedback for Non-smooth Constrained Optimization
We estimate the sums Er-1 w
S &
and E w 1. Therefore, derive
Σ
+
Σ
(f(x') -(xx))
1
Ci
IEN
IEB
1
+ -
- 
x² 1 (50+ 12v1 - 8
T
80 T nN tv
log
+
?
(50)
3
8
C1
Cf
Canceling O₁ in both sides, we finally obtain
Exe Σx(f(x") - f(x²))
1 s Ci log 3 + +1x² -x x= 12+2222 (50+
12v1
-
80 fv
T +
Ty
(51)
8
CnnNev
Lemma F.5. Let B E (0,1) be the failure probability and C₁ be defined as in(47). Suppose that the stepsize = VT and threshold satisfy
T 2 nc > C₁ log + ||00 221
12vI-
80
50+ 6
T+
TT?
(52)
3
CinNiv
Then we have with probability at least 1 9
7C+ ) -((x))
IEN
LEB
12 T 3 + 1| x² 12+
80
S log
50+
Ty2. CnNNN
(53)
8
Moreover, assume that (53) holds. Then non-empty, i.e. I = B conditions holds
Exeg x² is well-defined, and one of the following
1. |8|2 2: or
2. 7 EiER ((x²) - f(x)) S.
Proof. Assume that B 0. Then from Corollary F.4 we have that with probability at least 1 - B we have
1 + ||2.0 - +1 M22
50 + 12v1
80 Ty?
Tye S C1 log 3
T +
5
CInNev
This contradicts the assumption of the lemma. Hence, must have B * 0. Now assume that (53) holds. If have EIES f(x') - f(**) O, then the second condition holds. Assume that EIER f(=') - f(x*) > 0, then from (53) we obtain
Σ Ene S S log 3
1 + 1120 - 2=2
50 +
12
T +
Sa CinNe
Tz2
8
ENN
Assume that |B| T.
this means that |N12 T. Therefore, we have
T
1 + || x= 21 50
12
- 8 8
80
yc
Σ yc s log log 8
T +
Tn² CiNNN
TEN
which contradicts (52). Hence, if (ren(((at) f(x))) 0, then | 2
Now we are ready to establish our main convergence result in the stochastic setting.
Theorem F6. Let 8 E (0, 1) be the failure probability and C₁ be defined in (47). Suppose that the choice of y and e are chosen such that (52) holds. Then we have with probability of at least 1 - 3 that
2C1 log + 2| 112 +
12vI-
160
f( f(x))= <
22
50 +
+
CinNev 7
TT
8
37

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
Proof. We start by using the results Lemma F.5. Using the convexity of ʃ and Jensen's inequality we get that if part 2.
holds, then with probability of at least 1 B we have
f(x²) - f(x")= S O.
If part 2. does not hold, then | 2 h- Therefore, from (52) we obtain
-(
2 C2 log 1 + 1| x² x M
12v1-6 50+
80
T-?)
77
3
CinNer
201 log 1 + +21120 x²
12v1 -
160
+ 2yM2
50
T
CinNe 7
IT
Corollary E.7. Let B E (0, 1/2) be the failure probability. Let
R²2 2 11 - x x²1 ff/ NN
6M2
RV33 If v MVTi i.e,, 7=
R1/3 M
and 12 118 V/T
then we have with a probability of at least 2,3
MR
1 + 128
f(=²) - f(x*)= <
48 48log
V8T
3
g( 5 256RM (1 + log 1/3)
V8T
Proof. First, check that the stepsize y and threshold satisfy (52). We have with C₁ 18222
n
R 48
M
A12
log + ||00 - x11
R28
M
50
12
T
So
n
T
R266 8
M2T
8
N.
48
R
M M
M2T
RM2
/
log B
+ -1100 - =111 +1= + 12Rº +
n.M2
6M2
48
log
+ 11 - x x011=+62R2 + R
B
< 64R log
+ 64R2
At the same time, we have
T RVO (1 = = + log 1/3).
2 TC =
2 M.T
V8T
Therefore, with a probability of at least - 3 we have
-(3'))((+") 48 log 1 + 211x00 x= 1
MVT RVO
12
/o RVO
+2
M²
50
+
T
RV8
MVT
8
48 R'6
n MVT
M
1
MR
RM
RM
MRV5
(486log
+ 2)
100
24
+2
3
V8T
MVT
V8T
V8T
MR
48 log
+ 128
(54)
V8T
For the constraint violation we have that
9(
T
Σ
g(x0)
<
max g(x)) LEB
B
tEB
Moreover, from (15) and Lemma F.1 we have
n of
Σ (1(x)) (
(V2 221)
$ sexp(-69/3
Nwv
38

---

Safe-EF; Error Feedback for Non-smooth Constrained Optimization
This implies that Since for t have
IP
g(x')
1 Σ (x 52) - (V2+ v26)
JFr VnNr
<exp(-b²/3)
1=1
n Ei=1 gi + S c, then we get
P g(
cc (v2 + 26)
Jvv VnNiv
2 1 Texp(-67/s)
Choosing 12 = -3 log T 3 we obtain
P
g(x P
sct (v2 22b)
Ofv Vn.Vie
21-B. B.
Now we choose Niv 2 (v2+ + 226) nes we obtain
P (g(TT) ) < 2c) 2 1 8 3.
(55)
Thus with probability least 1 23 have both (54) and (55) hold. The batch-size Niv depends the problem constants as follows
Jf nc
ofv R
o nR²
Nv. 2 (V2 + 2b)
M
The number of iterations of Safe-EF EF to converge to e-accuracy is
R22 M
Ō=
Therefore, the batch-size required in the stochastic setting is of order
0% R8 M2 a5
2
Niv 2 2
fv
nR? M
This concludes the proof.
39

---

Safc-EF: Error Feedback for Non-smooth Constrained Optimization
G. Primal-dual Methods
short primer on primal-dual methods. In Section we briefly mentioned the primal-dus approach to solving the constrained problem (I). (4), here we elaborate more on this direction. Consider the Lagrangian with non-negative multiplier A:
- "
n
((x,A) f(x) + = Σ M(x))
g()))
Primal-dual schemes aim to find the saddle-point of this Lagrangian. If Slater's conditions hold, i.e., f(x) is convex and there exists strictly feasible solution g(x) < O, then the strong duality holds, that is
min max L(x, A) max min [(x, A),
A
A20
and general purpose methods for minimizing the primal-dur gap, Gap(æ', X² == maxx2o L(), min, L(,,, x). can
be used, The basic variant of such a scheme is Gradient Descent Ascent:
x x x (f'((') ) + )g'(z
Primal-dual
(56)
A II220X' + ne g(x
where {reh, {me} are primal and dual stepsizes respectively, and IΣ denotes the projection onto the non-negative ray. Similarly to the design of Safe-EF, we can write down an error feedback variant of this method for distributed optimization Algorithm 2. The intuitive justification Algorithm is similar to that of Safe-EF in Appendix D. However, a rigorous convergence analysis of Gap(æ', X²) for Algorithm 2 remains open since even the analysis (56) (special case of Algorithm in case of no compression) typically requires the projection step in x² variable. This problematic for EF analysis because the virtual iterates 3 defined in (22) do not have such simple form anymore.
Algorithm 2 Primal-dual Error Feedback for Constrained Optimization with Bidirectional Compression
1: Input: initial point n0,, Xo E stepsizes (1t), { compressors C and C, at the workers and the server
2: for = 0, ...,, T 1 do
3: for = 1 1,... n
4: Compute h (x ) (xgg(("))
5: Compute 2- C(c + ht) and send to server
6: Compute ++1 et + h of
7: end for
8: Compute v¹ 1 >1
11 v!!
9: Compute w +1 w² 7/06
Compute ++1 x² + Cs(w't1 x²) and send C.(w++1 x²) to workers
for
n do
Compute x² = x' Co(w++1 x²) Compute gi (z. (2) and send to server
13:
Cheap communication of one float
14:
end for
15:
Compute c+ " (i(xt+1)
Compute X+1 (x2 + m)
end for
Experiments. Although a rigorous convergence analysis for Primal-dual remains open, we investigate its practical performance through empirical evaluation. We follow the same experimental setup as before and compare Safe-EF with Algorithm 2, analyzing its sensitivity to different dual initializations 2º. We present our results Figure 7, where we compare the objective and constraint after 500M samples, the number of samples required for Safe-EF to converge. As shown, different values of X have significant impact the performance of Primal-dual. In contrast, Safe-EF that does require additional tuning of hyperparameters and only slightly underperforms Primal-dual when X -0=0 2.
H. Additional Experiments
Cartpole. We repeat our safety experiment using the Cartpole environment from Brax (Freeman et al., 2021), with the exception of using K/a- 0.01 instead of K/a- = 0.1. As before, we compare Safe-EF with EF14 (Seide et al., 2014),
40

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
Primal-dual,
Primal-dual,
Primal-dual, A 0.5
Primal-dual.
Safe- (Ours)
A
0.001
10000
8000
Unsafe
Safe and performant
4000
Low performance
2000
Budget
Je
Figure 7: Objective and constraint values of Safe-EF compared to Primal-dual with different initialization values of X Each point represents a distinct experiment trial with a different random seed. Safe-EF ensures safety and achieves solid performance without requiring additional hyperparameter tuning.
EF21 (Richtárik et al., 2021) and Parallel-CRPO. The results are presented in Figure 8. Similarly to the experiments with the Humanoid, Safe-EF rapidly satisfies the constraints with only a slight performance reduction in the objective. EF14 outperforms Safe-EF, however violates the constraints. Further, EF21 diverges during the last part of training. Finally, as ParO does not employ compression all, it requires significantly more gigabytes per worker converge.
1000
Safe-EF (Ours)
800
Parallel-CRPO
800
EF14
600
EF21
600
400
200
200
Budget
0.0
0.1
0.2
#Gigabytes worker
#Gigabytes/ / worker
Figure 8: Objective and constraint in the Cartpole environment. Safe-EF satisfies the constraints while maintaining competitive performance.
Price of compression. We follow the same evaluation protocol used Figure however now, instead of measuring how many gigabytes are required reach a certain benchmark performance, we use fixed sample "budget", and evaluate the performance achieved by each algorithm under this budget. Accordingly, we record J, after 100M and 500M samples, corresponding to 4883 and 24415 iterations respectively, for different values of K/a. We present the results in Figure 9. As shown, both Top-K and Rand-K K perform well under diminishing values of K/a after 500M samples. For training budget of 100M samples, Top-K significantly surpasses CGD and Rand-K.
Non-distributed baseline. We show that Safe-EF is able find non-trivial policy, by comparing it against Parallel-CRPO and its non-distributed variant, CRPO, where the latter is trained and evaluated only the nominal model We present our results in Figure 10.
Learning curves. In Figure 11 provide the full learning curves of the experiment trials used for Figures and 9.
Neyman-Pearson classification. We test Safe-EF on Neyman-Peaaaaee Pearson (NP) classification problem following the work of He et al. (2024). This statistical formulation aims to minimize type II error while enforcing an upper bound on type error,

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
100M Samples
@550M Samples
10000
Top-K
Rand-K
8000
CGD
6000
5
10
10-3
10 2
10
10
10-4
10
10
K/a
K/a
Figure 9: Performance for different compression ratios. Safe-EF with Top-K K and Rand-K K strategies outperform the CGD baseline. For training budget of 500M samples, Top-K reaches adequate performance, even under severe compression.
10000
Budget
8000
Sale EF (Ours)
80
Parallel-CRPO
6000
CRPO
60
40
2000
20
2
3
Samples
<100
Samples
Figure 10: Safe-EF performance only slightly degraded compared a non-distributed baseline terms of sample efficiency. However, in the distributed setup, we observed in Figure Safe-EF significantly outperforms Parallel-CRPO in communication efficiency.
Top-K
Rand-K
CGD
K/4 1 x 10-5
K/a 5x 10-5
K/a 1 x 10-4
K 5 x 10
Kfa 1 10-3
K/a 1x 10-2
K/4 1 10-1
10000
Rodget
#Gigabytes / worker
Figure 11: Objective and constraint learning curves for different compression ratio. Safe-EF with Top-K outperforms Rand-K and CGD, even under small compression values.
making particularly relevant for applications with asymmetric misclassification costs, such as medical diagnosis. The NP classification is
min f(x)
no Σ (h2 21,0); s.t. g(x)
1
ohh 2i,1) S
mi
where fz is a classifier parameterized by (3 layers MIP with 64 units in each layer and ReI.u activation); & is cross- entropy loss; {2,,0) and 1 are training samples from class 0 and class 1, respectively. The constraint ensures that the classification error for class does not exceed a predefined threshold c. Our results are presented in Figure 12.
This experiment further supports the argument that Safe-EF is useful for federated learning by showing its effectiveness in
42

---

Safe-EF; Error Feedback for Non-smooth Constrained Optimization
Safe-EF (Ours)
CGD
Parallel-CRPO
0.76
0.02
0.74
0.72
g(
-0.02
0.70
-0.04
00.6
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
#Gigabytes worker
#Gigabytes worker
Figure 12: Objective and constraint for Neyman Pearson classification. Compared to the CGD and Parallel-CRPO baselines,
Neyman-Pearson Safe-EF both satisfies the constraint and minimizes the loss while requiring significantly less communication overhead.
Table 1: The algorithms' hyperparameters used in the training from Section 6.1. Here denotes the stepsize for all algorithms, 3 is the momentum parameter for EF21M, and is the control stepsize for EControl.
Safe-EF
CGD
EF21
EF21M
EControl
0.1
0.01
7 0.01
7 0.003
0.01, 8 = 0.001
0.003,
0.01
1.0
?
0.01
Y 0.01
7 0.003
? 0.01, 8 0.001
7 == 0.003, 77 0.01
= 1.0
0.003
Y 0.01
7 = 0.001
? 0.001, 6 0.1
0.001, 17 = 0.1
Algorithm 3 Synthetic data generation mechanism
1: Parameters: number of nodes n, dimension d, noise scalers and
2: Generate A A( I) Rdxd and 2g ~ IO,, E Rd
Normalize A A/||
4: for i = 1, ...... do
5: Generate A; (0, I) E Rdxd
6: Normalize A, + A4/||All
7: Shift A; + A
8: Sample independently ~ (0,0 1) E Rd
9: Compute b; A,500 + CE
end for
11: Return (A,, b
well-established classification framework.
I. Additional Details on the Experimental Setup
Data generation. We generate matrices {A and shifts (b,) according to Algorithm 3. Here parameter controls how different the matrices A; from each other. In experiments, vary {0.1, 1.0, 10.0) and set 1
Hyper-parameter tuning for Section 6.1. For all algorithms mentioned in Section 6.1. we tune the step- size f0.01, 0.003, 0.001, 0.0003, 0.0001, 0.00003}. For EF21M we tune the momentum parameter B E (0.0001, 0.001, 0.01, 0,1, 0.5, 0.9). and for EControl, we tune " E 0,000, 0.01, 0.5, 0.9). The best hyper- parameters are reported in Table 1.
Humanoid. We use the Humanoid environment implementation from Brax (Freeman et al., 2021) and extend it with an indicator cost function for whenever any one of the joint angles goes outside of predefined limits. We perturb the dynamics
43

---

Safe-EF: Error Feedback for Non-smooth Constrained Optimization
P; of each worker by sampling the ground's friction coefficient and the gear parameter of the joints' motors. Sampling is done with uniform distribution, with symmetric interval centered around the nominal value given in Brax.
the environment implementation provided by Brax. The cost function is an indicator for whenever the 'cart' exceeds predefined distance from the center position. The dynamics are perturbed in the same fashion as the Humanoid, using a uniform distribution centered around nominal values. However in this experiment, we perturb the mass of the 'pole' and the gear parameter of the cart's motor.
Cartpole. As with the Humanoid,
Hyper-parameters tuning for Section 6.2. As mentioned before, our implementation Safe-EF builds on PPO (Schulman al., 2017). We follow the standard follow the standard implementation provided in Brax, including their default hyper- parameters used for the Humanoid environment. Notably, all of our experiments, we keep the default value ? = 0.0003, with Adam optimizer (Kingma Ba, 2014). In practice, we found the default set of parameters work well with Safe-EF. The only deviation from these parameters is the entropy regularization coefficient, which set to 0.01 from 0.001.
For more specific details, please use our open-source implementation https: /ittht...bb///ggg// com comm/yardenas/saff-eea
44


Reviews:
[{"review_id": "Wt0DgjjUUq", "reviewer": "Reviewer_K1fK", "summary": "The paper presents Safe-EF, an error feedback (EF) algorithm designed for non-smooth constrained optimization in distributed settings. It establishes lower complexity bounds for first-order algorithms with contractive compression and introduces Safe-EF, which matches these bounds while ensuring safety constraints. The algorithm uses bidirectional compression and a constraint-aware switching mechanism. The effectiveness of Safe-EF is demonstrated in a reinforcement learning (RL) setting, specifically in distributed humanoid robot training, where it reduces communication overhead while maintaining constraint satisfaction.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. We appreciate the reviewer's high evaluation of our theoretical guarantees and empirical results. For empirical evaluation, we (i) test our method on a well-controlled synthetic environment with different levels of heterogeneity and (ii) provide an extensive ablation study in more challenging continuous control environments (Cartpole and Humanoid). We believe the latter Federated Safe RL setting is one of the most relevant and challenging applications of our theory that tests the real potential of Safe-EF. Different transition dynamics $p_i$ of each worker make the loss $f_i$ different, resulting in a highly heterogeneous setting. We mentioned this aspect in Section 6.2 and Appendix I, but we will put more emphasis on the heterogeneity aspect in the revision. In our work, we focus on non-smoothness, safety constraints, biased and bidirectional compression. Decentralized aggregation is an important topic, and we leave it to future work. \n2. We test Safe-EF on Neyman-Pearson (NP) classification problem following the work (He et al., Federated Learning with Convex Global and Local Constraints, TMLR 2024). This statistical formulation aims to minimize type II error while enforcing an upper bound on type I error, making it particularly relevant for applications with asymmetric misclassification costs, such as medical diagnosis. The NP classification is $$\\min_xf(x)=\\frac{1}{n_0}\\sum_{i=1}^{n_0}\\phi(h_{x}, z_{i,0}),\\text{ s.t. }\\quad g(x)=\\frac{1}{n_1}\\sum_{i=1}^{n_1}\\phi(h_{x}, z_{i,1})\\le c,$$ where $f_x$ is a classifier parameterized by $x$ (3 layers MLP with 64 units in each layer and Relu activation); $\\phi$ is a CE loss; $\\\\{z_{i,0}\\\\}\\_{i=1}^{n_0}$ and $\\\\{z_{i,1}\\\\}_{i=1}^{n_1}$ are training samples from class 0 and class 1, respectively. The constraint ensures that the classification error for class 1 does not exceed a predefined threshold $c$. We include the results in https://ibb.co/SXYqWQtB. This benchmark further supports the argument that Safe-EF is useful for federated learning by showing its effectiveness in a well-established classification framework. We believe the Federated Safe RL remains the most relevant application naturally formulated as a stochastic optimization of the form (72), (73) in Appendix F (unlike the standard supervised learning task with finite dataset), but we welcome the reviewer for a discussion if this new set of experiments strengthens our argument that Safe-EF is useful for FL.  \n3. While we show our hard instance (functions, constraints, compressors) in the main paper, we will detail key steps of the proof in the revised version of the paper.\n4. The design of EF21 algorithm can be seen as a variance reduction (VR) technique. In a nonsmooth setting, gradients can change abruptly. Thus, VR mechanisms such as EF21 may fail. In contrast, EF14 algorithm's design is based on tracking the compression error, and the control of gradient change is not needed.\n5. We acknowledge reviewer's concern. From theory, in the choice $\\gamma=O(\\frac{R\\sqrt{\\delta\\delta_s }}{M\\sqrt{T}})$ and $c=O(\\frac{MR}{\\sqrt{\\delta\\delta_s T}})$ parameters $\\delta,\\delta_s,T$ are typically set by a user. Thus, there is no need to estimate them. We can estimate $M=\\max_i\\\\|f_i^\\prime(x^0)\\\\|$ and $R>\\\\|x^0\\\\|,$ if $x^*$ is close to zero. In general, we believe that choosing $\\gamma,c=O(1/\\sqrt{T})$ or $O(1/\\sqrt{t})$ can be a good starting point. In our experiments, $\\gamma=$1e-4 is chosen based on existing default value that is known to work well for PPO on standard RL benchmarks. The slackness parameter $c$ is set to 0, which is sufficient to get decent performance for both tasks. We did not try to further tune these parameters and agree that, in general, these parameters are problem-dependent.\n6. Thank you for pointing this out. Based on your suggestion, we will add additional details on our experimental setup to Appendix I. We kindly ask the reviewer to point out more specifically which parts in the exposition should be further clarified.\nAdditionally, we emphasize that the code for our experiments can be found in https://anonymous.4open.science/r/safe-ef-3ABC, as mentioned in Appendix I. We believe that this makes our experiments fairly easy to reproduce. \n8. We reference all relevant work within each subsection or paragraph of the introduction while discussing practical challenges and existing solutions. While we can divide the first section into an introduction and practical challenges, separating the related work into a standalone section would not be appropriate. Any additional related work that is not directly relevant to our main narrative is included in the appendix.\n9. Investigating convergence in the non-convex setting is indeed an interesting and important question motivated by real-world RL problems. We believe our analysis can be extended to weakly convex functions, i.e., $f(x)+r\\\\|x\\\\|^2$ and $g(x)+r\\\\|x\\\\|^2$ are convex following, e.g., (Jia and Grimmer, 2022); (Boob et al., 2023)", "claims_and_evidence": "The claims about Safe-EF’s theoretical guarantees (matching lower bounds) are well-supported with clear derivations. The empirical results effectively show that Safe-EF outperforms EF21 and CGD in terms of communication efficiency and constraint satisfaction. However, the claim that Safe-EF applies to federated learning (FL) is less substantiated, as the experiments do not fully capture the typical FL challenges (e.g., heterogeneous data, decentralized aggregation).", "methods_and_evaluation_criteria": "The problem setting and evaluation criteria are reasonable for distributed optimization. The experiments use a multi-agent RL setting, which is a valid but non-standard way to test federated learning algorithms. The humanoid training task is complex and relevant, but an additional FL benchmark would strengthen the argument that Safe-EF is useful for FL.", "theoretical_claims": "I reviewed the lower bound proof and the convergence analysis for Safe-EF. The derivations appear correct, and the methodology follows standard approaches in optimization theory. The results for error feedback in non-smooth settings are a useful contribution. However, the key proofs should be moved to the main text rather than being relegated to the appendix.", "experimental_designs_or_analyses": "The experiments convincingly show Safe-EF’s superiority over EF21 and CGD. However, some key experimental details are missing:\n\n-No clear explanation for why EF14 works while EF21 fails in non-smooth settings.\n\n-No guidance on practical choices for γ (step size) and c (constraint threshold), making Safe-EF harder to implement.\n\n-The humanoid RL task is well-chosen, but its setup is not clearly described, making reproducibility difficult.", "relation_to_broader_scientific_literature": "Safe-EF builds on prior error feedback methods (EF21, EF14, CGD) and contributes to communication-efficient distributed optimization. However, its positioning in federated learning needs stronger justification, as it lacks evaluation on heterogeneous FL datasets.", "essential_references_not_discussed": "The paper cites relevant work in error feedback, compressed optimization, and distributed learning. I do not see any critical omissions.", "other_strengths_and_weaknesses": "Strengths:\n\nNovel bidirectional compression approach.\n\nStrong theoretical guarantees.\n\nClear improvements over EF21 and CGD in non-smooth settings.\n\nWeaknesses:\n\nFederated learning framing is weak; an FL benchmark would make the claims stronger.\n\nThe introduction is too long and should be split into introduction, practical challenges, and related work.\n\nLack of practical guidance on hyperparameters γ and c.", "other_comments_or_suggestions": "Move key proofs to the main text instead of the appendix.", "questions_for_authors": "Why does EF14 work while EF21 fails? More insight into this difference would strengthen the theoretical claims.\n\nWhat values of γ and c should be used in practice? Can practical guidance be provided for choosing these parameters?\n\nCould Safe-EF be tested in a standard FL benchmark? This would help justify its relevance to federated learning.\n\nWould Safe-EF generalize to non-convex settings? Since many real-world RL problems are non-convex, would it still maintain convergence?", "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": "pZCJ3568Xj", "reviewer": "Reviewer_TUHp", "summary": "In this paper, the authors investigate a non-smooth optimization setting with bounded gradients in the context of Top-K compression. Communication compression using contractive compressors (e.g., Top-K) is commonly preferred in practice due to its efficiency; however, it can significantly degrade performance if not properly managed.\n\nThe authors demonstrate a scenario in which Error Feedback (EF) can lead to divergence but also propose a method to mitigate this issue. They contribute to the theoretical understanding of EF in the canonical non-smooth convex setting by establishing new lower complexity bounds for first-order algorithms under contractive compression.\n\nTo address the limitations of existing approaches, the authors introduce Safe-EF, a novel algorithm that achieves the established lower bound (up to a constant factor) while incorporating safety constraints crucial for practical applications. Furthermore, they extend their approach to the stochastic setting, enhancing its applicability.\n\nThe proposed method is thoroughly evaluated through extensive experiments in a reinforcement learning setup, specifically simulating distributed humanoid robot training. The results demonstrate that Safe-EF effectively maintains safety constraints while reducing communication complexity, highlighting its potential for real-world deployment in distributed optimization scenarios.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. We appreciate the reviewer’s comment and agree that further elaboration on the lack of prior work in this area would strengthen the manuscript. To the best of our knowledge, constrained optimization with communication compression remains largely unexplored. In fact, besides the two works we cited—(Fatkhullin et al, 2021), which considers projection-based methods, and (Nazykov et al, 2024), which employs linear minimization oracles—we are unaware of any other studies that explicitly address even simple constrained problems in the presence of contractive compression. In the more limited setting with Rand-$K$ operator (unbiased compressor), the recent work (Laurent Condat and Peter Richt{\\'a}rik. Randprox: Primal-dual optimization algorithms with randomized proximal updates, 2023) has established some results in the proximal setting. However, this is still limited to constraints/proximal functions with simple structure (e.g., Euclidean ball, simplex, affine constraints, etc). \n  \n    The situation becomes even more challenging when considering the general constraints of the form (4) in the manuscript, as no existing work tackles such cases. Fundamentally, addressing this problem requires overcoming new technical difficulties arising from the interaction between constrained optimization and communication compression. Specifically, in addition to the usual error accumulation from compression in unconstrained settings, constrained problems introduce further complexities: (i) compression errors affect the feasibility of iterates, making it harder to ensure constraint satisfaction, and (ii) primal-dual methods introduce an additional projection step, which requires the control of errors from projection, the objective and constraint updates simultaneously. These challenges necessitate novel algorithmic techniques, which we discuss in the subsequent paragraph of our introduction by distinguishing between primal-only and primal-dual approaches.\n\n    We will revise the manuscript to clarify these points and emphasize the fundamental difficulties that remain open in this research direction.\n2. We thank the reviewer for providing the references. We agree that these studies are relevant to our work, and we will incorporate them in the introduction. These papers examine a general case of SGD with biased stochastic gradients. The special case of their analyses is CGD, described in the introduction. However, their analysis does not fully align with our setting because they consider (i) a single-node training regime $n=1$, (ii) $L$-smooth functions while we focus on a non-smooth setting, and (iii) a plain SGD without a memory buffer to mitigate the bias (e.g., the compression error). Nonetheless, we agree that extending our results from unbiased gradients to biased ones is an interesting research direction for future work.\n3. Currently, a detailed description of the stochastic setting is provided in section F due to the page limit. We will try to reorganize the main body to fit the description in the main paper. We appreciate this suggestion. \n4. The logarithmic dependency on the failure probability $\\beta$ is a typical outcome of the high probability analysis that comes from the use of concentration inequalities [1,2]. To the best of our knowledge, the logarithmic dependency on the failure probability cannot be avoided as there exists a lower bound for a sample complexity of any learning algorithm Theorem 5.2 in [3]. We will add a note on this aspect in the revised version of the paper.\n\n    [1] Nemirovski et al., Robust stochastic approximation approach to stochastic programming, SIAM 2009\n\n    [2] Ghadimi \\& Lan, Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework, SIAM 2012\n\n    [3] Anthony \\& Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 2009", "claims_and_evidence": "Most of the claims in the paper are well-formulated and supported by either rigorous proofs or relevant references. The arguments are clearly articulated, contributing to the overall clarity and coherence of the work.  \n\nHowever, I identified one claim that might be considered questionable:  \n\n**Lines 102–104 (right side, page 2):**  \n*\"Despite their importance, constrained optimization with communication compression remains under-explored.\"*  \n\nWhile I believe this statement is accurate, it would benefit from further elaboration. Providing additional context, references, or a more detailed discussion would help clarify the extent to which this area has been explored and why it remains an open challenge. This would make the claim more accessible to a broader audience and strengthen its impact.", "methods_and_evaluation_criteria": "In this paper, the authors present theoretical convergence guarantees alongside experimental results for reinforcement learning tasks. These criteria are both relevant and well-justified, as they ensure that the proposed method is supported by rigorous mathematical analysis while also being validated through practical implementation. The combination of theoretical and empirical evaluation strengthens the credibility of the approach, demonstrating its effectiveness in real-world reinforcement learning scenarios. This dual perspective enhances the overall contribution of the paper by providing both fundamental insights and practical applicability.", "theoretical_claims": "In this paper, the authors establish tight convergence guarantees by providing both lower and upper bounds for the considered setting of non-smooth convex optimization with contractive compression operators.\n\nThe lower bounds presented in this work are particularly valuable, as deriving them is generally more challenging than establishing upper bounds. The proposed algorithm achieves a convergence rate that matches the lower bound (Equation 9), up to numerical and logarithmic factors.\n\nWhile the presence of additional logarithmic factors could be perceived as a drawback, this is a relatively minor issue compared to the overall theoretical contribution of the paper. The extension to the stochastic setting further enhances the significance of the work, broadening its applicability.\n\nI have briefly reviewed the analysis, and it appears to be correct. However, there is always a possibility that some errors may have been overlooked, so I recommend a thorough double-check for accuracy.", "experimental_designs_or_analyses": "In the experimental section, the authors conduct experiments on synthetic data to illustrate their theoretical findings.\n\nSubsequently, they explore the application of Safe-EF in reinforcement learning. In this setup, each worker represents a humanoid robot that collects noisy measurements of certain utility and constraint functions to solve a constrained Markov decision process (CMDP).\n\nThe experimental evaluation consists of several key components:\n\nComparison with CGD: The authors first evaluate Safe-EF using Top-K and Rand-K sparsifiers and compare its performance with a constrained version of CGD employing a Top-K sparsifier.\n\nConstraint Satisfaction Analysis: They then analyze Safe-EF’s ability to satisfy constraints, comparing it against unsafe error feedback algorithms (EF14 and EF21). Additionally, they benchmark Safe-EF against a parallel variant of CRPO, a CMDP solver that enforces constraints through the subgradient switching method.\n\nEffect of the Number of Workers: The authors examine how the performance of Safe-EF varies with the number of available workers, providing insights into its scalability.\n\nEffect of Batch Size: Finally, they study how different batch sizes impact the method’s performance.\n\nThe presented experiments are valuable and well-structured, providing strong empirical support for the proposed approach. However, exploring additional settings could further strengthen the study by demonstrating the robustness of Safe-EF across a broader range of scenarios.", "relation_to_broader_scientific_literature": "The key contributions of the paper are closely related to the broader scientific literature on optimization. In particular, the derivation of lower bounds is especially valuable, as such results are typically more challenging to establish and provide fundamental insights into the theoretical limits of the considered optimization setting.", "essential_references_not_discussed": "There are two papers that are discussing biased SGD and consider contractive compression in details, which is highly related to the current paper. \n\nAjalloeian, Ahmad, and Sebastian U. Stich. \"On the convergence of SGD with biased gradients.\" arXiv preprint arXiv:2008.00051 (2020).\n\nDemidovich, Yury, et al. \"A guide through the zoo of biased SGD.\" Advances in Neural Information Processing Systems 36 (2023): 23158-23171.", "other_strengths_and_weaknesses": "The paper is well-written and presents its ideas in a clear and structured manner. The theoretical contributions are strong and well-founded, making a significant impact on the understanding of the problem. Additionally, the figures and plots are carefully formatted, with appropriate use of grids and markers, which enhances readability and interpretability. The attention to detail in visualization and presentation reflects the authors’ commitment to clarity and precision.\n\nThe stochastic case extension section could be further expanded, as its current description lacks sufficient detail. Providing a more comprehensive discussion would enhance the clarity and depth of this section.", "other_comments_or_suggestions": "Please review the issues identified in the previous sections and ensure they are addressed appropriately.", "questions_for_authors": "Do you have any insights on how to eliminate the additional logarithmic factors in order to achieve the optimal rate?", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "0oOB0LsptE", "reviewer": "Reviewer_gSmf", "summary": "he paper establishes a convergence lower bound for the non-smooth convex distributed setting, where EF-21 and similar methods operate. Next, it proposes Safe-EF (Algorithm 1), an extension of EF14 (Seide et al., 2014) that incorporates safety constraints and bidirectional compression. Safe-EF is provably effective in non-smooth distributed settings and efficiently minimizes the objective function. The paper proves that the convergence rate of Safe-EF matches the aforementioned lower bound up to a numerical constant, assuming a constant accuracy of the server compression C₀.\n\nFurthermore, the paper studies Safe-EF in practically relevant stochastic scenarios, where exact subgradients and function evaluations are unavailable. It establishes high-probability bounds in these settings.\n\nExtensive experiments and ablation studies validate Safe-EF, demonstrating its effectiveness on the challenging task of distributed humanoid robot control.\n\nPaper contains source code for repoducability.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. We thank the reviewer for this valuable comment and pointing out this reference! Indeed, the workers cloning idea described in that paper can be extended to our result in convex (smooth) setting. We have revisited the convergence analysis of EF21 in our supplementary Theorem C.1. following the analysis from the proposed reference. The updated rate is $\\mathbb{E}[f(x^T) - f(x^*)] \\le \\frac{R_{\\mathcal{X}}^2}{\\gamma T}\\left(1+ \\log\\left(\\frac{\\gamma \\Lambda_0 T}{R_{\\mathcal{X}}^2}\\right)\\right),$\nwhere $$\\gamma \\le \\mathcal{O}\\left(\\frac{\\delta}{\\frac{1}{n}\\sum_{i=1}^nL_i}\\right).$$ The potential improvement compared to our Theorem C.1. is in the difference between the average $\\frac{1}{n}\\sum_{i=1}^nL_i$ and the quadratic mean $\\sqrt{\\frac{1}{n}\\sum_{i=1}^n L_i^2}$. This derivation follows directly from our analysis by replacing equation (15) in the proof of Theorem C.1. with more refined Lemma 7 in Appendix C.1. of the suggested paper. We will include the improved derivation in the next revision and cite the missing reference.\n2. We appreciate this useful suggestion. The hyperparameters used in Section 6.1 are provided in Appendix I. We perform a grid search over several choices of $\\gamma$ and select the one that gives the smallest train loss at the end of training. Table 1 in Appendix I gives concrete numbers for the selected step size for each heterogeneity level $s = 0.1, 1.0, 10.0$. In Safe RL experiment, we don’t tune the hyper-parameters and use the default step-size $\\gamma = 10^{-4}$ from the (non-distributed) PPO implementation that is known to work well on standard RL benchmarks. The slackness parameter $c$ is set to $0$, which is sufficient to get decent performance for both tasks. We did not try to further tune these parameters and agree that, in general, these parameters are problem-dependent. We will clarify these details in the revision, thank you for this advice!\n3. Thank you for bringing this to our attention. We highlight that we use $5$ seeds for all of our RL experiments, as also mentioned in the “Setup” paragraph of section 6.2.\n4. We emphasize that the choice of $c$ highly depends on the application. The choice of $c$ is dictated by the fact of how much constraint intolerance we can allow. From theory perspective, the choice of hyperparameters $\\gamma = \\mathcal{O}(\\frac{R\\sqrt{\\delta\\delta_s }}{M\\sqrt{T}})$ and $c=\\mathcal{O}(\\frac{MR}{\\sqrt{\\delta\\delta_s T}})$ depends on the compression levels $\\delta$ and $\\delta_{s}$, the gradient bound $M$, number of iterations $T,$ and the upper bound on the initial distance to the optimal set $R=\\\\|x^0-x^*\\\\|^2.$ The compression levels and the number of iterations are typically known beforehand as it is a user who sets them. Therefore, there is no need to estimate them. To set $\\gamma$ and $c$ we should provide an estimate on $M$ and $R.$  For example, we can estimate $M = \\max_i\\\\|f_i^\\prime(x^0)\\\\|$ and set $R \\geq \\\\|x^0\\\\|,$ if $x^*$ is close to zero. In general, we believe that choosing $\\gamma, c = \\mathcal{O}(1/\\sqrt{T})$ or diminishing $\\gamma, c = \\mathcal{O}(1/\\sqrt{t})$, $1 \\leq t \\leq T$, can be a good starting point.\n\nWe appreciate the reviewer for their thoughtful feedback! We believe we have addressed the main concerns (1–4) and would appreciate if you could confirm that everything is resolved and consider adjusting the score.", "claims_and_evidence": "No claims. The paper is strong and presents an interesting perspective for EF type methods in case of non-smooth convex distributed settings with constraints.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes. No issues.", "relation_to_broader_scientific_literature": "Error Feedback is a popular and immensely effective mechanism for fixing convergence issues that arise in distributed training. While EF was proposed almost a decade ago, and despite concentrated effort by the community to advance the theoretical understanding of this mechanism, there is still a lot to explore.", "essential_references_not_discussed": "No. All is fine. With one exception.\n\nThanks authors for \"B. Failure of CGD and EF21 in Non-smooth Convex Setting\".\n\nHowever, Convergence Upper Bound for EF21 in Smooth Convex Setting is not necessarily optimal selection of stepsize.\nThe work \"Error Feedback Reloaded: From Quadratic to Arithmetic Mean of Smoothness Constants\" https://openreview.net/pdf?id=Ch7WqGcGmb, https://arxiv.org/abs/2402.10774\nImproves quadratic mean to arithmetic mean.\n\nPlease, revisit Chapter C for Smooth Convex Setting under this consideration.", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "(1) Convergence Upper Bound for EF21 in Smooth Convex Setting should be revisited under a better setting of selecting meta-parameters \n\n(2) I have observed \\gamma = 1/\\sqrt{T} as step-size in Figure 1, but this information is missed in other experiments.\nPlease be specific about stepsize selection (theoretical, tuned for specific instance, estimated in another form) in experiments from Figures 2-11 in Experiment sections. Please elaborate about your selection.\n\n(3) Please provide information about the number of trials in experiments with error bars.\n\n(4) Theorem 4.2 contains a reference to Appendix D. This suggests select \\gamma and c as a function of T. Please elaborate more and provide implicit or explicit formulas in terms of the target discrepancy in function gap. Either provide the notion that T is the conceptual budget for iterations. But I strongly ask to elaborate on what constants should be estimated before Safe-EF can be launched.", "questions_for_authors": "Please address suggestions (1) - (4). Under this condition, I am glad to recommend the paper for acceptance.", "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": {"ethical_review_concerns": "No concerns."}}]

Author rebuttal:

Meta-review: This paper proposes Safe-EF algorithm for non-smooth constrained optimization in distributed environments under contractive communication compression. The main contributions include (i) tight lower complexity bounds for first-order methods under such compression and (ii) the Safe-EF algorithm, which matches these bounds (up to constants) while satisfying practical safety constraints through bidirectional compression. The theoretical contributions are strong and well-motivated. All reviewers agree that the lower-bound derivation is a valuable and nontrivial addition to the literature. The experimental evaluation focuses on a distributed reinforcement learning whose results are both compelling and challenging.
Decision: Accept (poster)