Pith. sign in

REVIEW 2 major objections 4 minor 18 references

Safe-EF: Error Feedback for Nonsmooth Constrained Optimization

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper establishes that error feedback can work for nonsmooth convex constrained optimization: no zero-respecting first-order algorithm using contractive compressors can beat $\Omega(RM/\sqrt{\delta T})$ iterations, and the proposed…

desk verdict Solid upper-bound analysis and failure examples, but the lower-bound proof has a load-bearing flaw that leaves the claimed optimality unproven. read the letter →

arxiv 2505.06053 v1 pith:4YD74L2E submitted 2025-05-09 cs.LG math.OCstat.ML

Rustem Islamov , Yarden As , Ilyas Fatkhullin This is my paper · ORCID
classification cs.LGmath.OCstat.ML MSC 90C2590C3068W15
keywords errorfeedbacknonsmoothconvexoptimizationconstrainedcommunicationcompressioncontractivecompressorsminimaxlowerboundsfederatedlearningstochastic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that error feedback, the standard fix for communication-compressed training, can work in nonsmooth, constrained, distributed problems where it was previously known to fail. It proves that no zero-respecting first-order algorithm using contractive compressors can beat $\Omega(RM/\sqrt{\delta T})$ iterations or constraint-violation error, and it introduces Safe-EF, which matches that rate up to a constant. This matters because it gives the first principled guarantee that aggressive compression like Top-K can be used for problems with safety constraints, a regime central to federated reinforcement learning and other safety-critical deployments. The paper also extends the guarantee to stochastic subgradients and function evaluations, at the price of a large batch size for constraint estimation.

What carries the argument

The load-bearing mechanism is a switch between objective and constraint subgradients: at each round the workers evaluate the average constraint value $g(x_t)$ (one float of communication), and choose $h_t^i = f'_i(x_t)$ when $g(x_t) \leq c$ and $h_t^i = g'_i(x_t)$ otherwise, where $c$ is a carefully tuned threshold. These directions are transmitted with error feedback of the EF14 form, in which each worker accumulates the error between the true subgradient and the compressed message, and the server uses an EF21-P variant to compress its broadcast. The convergence proof runs on virtual iterates $\hat{x}_t = w_t - \gamma e_t$, whose update is an exact subgradient step without compression error, reducing the whole argument to bounding two compression-error terms by constants depending on $\delta$, $\delta_s$, and $M$. The lower bound rests on the zero-respecting property: in the worst-case construction each worker can discover at most one new nonzero coordinate per round, and Rand-K with shared randomness needs $1/\delta$ rounds to pass a coordinate from one worker to all others.

What would settle it

Run the explicit worst-case problem of Theorem 1 ($f_i(x)=C\cdot\max_{1\leq j\leq T}x_j + (\mu/2)\|x\|^2\cdot\max\{\|x\|^2, R^2\}$, $g_i = f_i - \min f_i$, $d=\lceil 5T\delta\rceil$, Top-K with $K=\lceil\delta d\rceil$ and shared randomness across workers) with Safe-EF's stated $\gamma$ and $c$: getting a rate better than $\Omega(RM/\sqrt{\delta T})$ would refute the lower bound, and divergence or violation of the $O(RM/\sqrt{\delta_s \delta T})$ bound would refute the upper bound.

Watch

Extended reading notes

Core claim

The central claim is a matching pair of bounds for nonsmooth convex constrained optimization with contractive compression. Theorem 1 states that for any zero-respecting first-order algorithm, there is a problem in the class with subgradients bounded by $M$, initial distance $R$, and compression level $\delta$ such that both the function suboptimality and constraint violation at the output are at least $\Omega(RM/\sqrt{\delta T})$ after $T$ rounds. Theorem 2 states that Safe-EF, a switching-subgradient error-feedback method with bidirectional compression, achieves $\mathbb{E}[f(x_T)-f(x^*)] \leq O(RM/\sqrt{\delta_s \delta T})$ and $\mathbb{E}[g(x_T)] \leq O(RM/\sqrt{\delta_s \delta T})$, matching the lower bound when the server compressor accuracy $\delta_s$ is a constant. Corollary 1 makes the choice explicit: stepsize $\gamma = R\sqrt{\delta_s \delta}/(M\sqrt{T})$ and switching threshold $c = 32RM/(\sqrt{\delta_s \delta T})$. In the stochastic setting, Theorem 3 gives high-probability bounds with the same rate up to logarithmic factors, requiring a batch size of order $\tilde{O}(\sigma_{fv}^2/(n\varepsilon^2))$ for $\varepsilon$-accuracy.

Load-bearing premise

The proof requires that every subgradient of the objective and constraint functions has Euclidean norm at most a known bound $M$, because the stepsize and switching threshold are chosen from $M$ and every error estimate in the analysis uses this bound.

Editorial extensions

If this is right

  • With Top-K compression, Safe-EF's total communication for $\varepsilon$-accuracy is $O(dR^2M^2/\varepsilon^2)$ in the worst case, matching the uncompressed switching-subgradient method even when compression is very aggressive.
  • The lower bound implies that in the worst case, adding workers does not improve the convergence rate, so speedups in practice must come from problem structure rather than parallelism alone.
  • The stochastic guarantee shows the algorithm is robust to noisy gradient and constraint estimates with high probability, and the required batch size of $\tilde{O}(\sigma_{fv}^2/(n\varepsilon^2))$ grows only with the noise variance, not with the dimension.
  • The analysis covers any contractive compressor, such as sparsification, quantization, or low-rank approximation, as long as its accuracy parameter $\delta$ is known, which makes the method a drop-in replacement for earlier error-feedback schemes in federated systems.
  • Because the server-side compression only needs accuracy $\delta_s$, the bidirectional rate degrades by a factor $\sqrt{\delta_s}$, and the paper leaves open whether this dependence can be improved.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same switching mechanism may extend to nonconvex objectives: the paper's humanoid-experiment results show the algorithm enforcing constraints in a highly nonconvex policy-search problem, suggesting the convexity assumption is a proof artifact rather than an empirical requirement.
  • The factor $1/\sqrt{\delta_s \delta}$ in the bidirectional bound might be improvable to $1/(\sqrt{\delta}+\sqrt{\delta_s})$ by allowing multiple communication rounds per iteration, a route the paper explicitly mentions but does not take.
  • The large batch requirement for constraint estimation is likely the algorithm's main bottleneck; a primal-dual or level-set estimator with a smaller batch could make the stochastic method sample-optimal, but no such compressed method currently exists.
  • A testable extension: run Safe-EF with adaptive estimation of $M$ (e.g., gradient clipping) on the $\ell^1$-ball problem from Example 1; if it converges when $M$ is unknown, the bounded-subgradient assumption could be relaxed.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies distributed nonsmooth convex optimization with safety constraints and contractive communication compression. It first presents two failure examples showing that vanilla compressed gradient descent and the EF21 error-feedback method do not converge on a simple nonsmooth problem, and then proposes Safe-EF, an EF14-type switching-subgradient method with bidirectional compression. The main theoretical claims are a lower bound of order Ω(RM/√(δT)) for zero-respecting first-order compressed algorithms and a matching upper bound for Safe-EF, together with a high-probability stochastic extension and extensive experiments on synthetic problems and a distributed humanoid reinforcement learning task.

Significance. If the main claims held, this would be a significant contribution: it would provide the first optimal complexity rates for error feedback in nonsmooth constrained distributed optimization with practical contractive compressors such as Top-K, and the proposed algorithm is simple and well motivated. The failure examples for CGD and EF21 are explicit and correct, the upper-bound analysis in Appendix D is coherent, and the experimental study is thorough. However, the lower-bound proof contains a load-bearing internal inconsistency: the hard instance violates Assumption 2, so the advertised lower bound is not proved for the function class H_{R,M}. The matching lower bound is the paper's central optimality claim, so this gap prevents acceptance as written.

major comments (2)
  1. [Appendix E.2, Theorem 6] The hard instance h used in the lower-bound proof does not belong to the class F_{R,M} under Assumption 2. The proof sets C = M√T/(1+√δT) and, at x=0, the oracle returns h'(0)=C e_k, so ||h'(0)||=C. For the claimed parameter regime δ≤0.3 and T≥δ^{-2}, one has C>M; for example, R=M=1, δ=0.1, T=100 gives C≈2.40>1. Since Assumption 2 requires all subgradients of the objective and constraint functions to have norm at most M, the constructed h is not in F_{R,M}, and the lower bound in Theorem 1 is not established for the advertised class H_{R,M}. This is load-bearing because the paper's central claim that Safe-EF matches the lower bound depends on the same M in both bounds.
  2. [Appendix E.2, Step 5 of proof of Theorem 6] The proof assumes T≤d when defining h(x)=C·max_{1≤j≤T} x_j, but then chooses d=⌊5Tδ⌋. For δ<0.2 this choice gives d<T; for instance, δ=0.1 and T=100 give d=50. In that case the coordinate x_T used in the max is not defined, and Lemma 3's probability calculation over T coordinates is not meaningful. The proof should either choose d≥T and redo the probability estimate, or justify a different definition of the hard instance; as written, this is a second internal inconsistency in the lower-bound argument.
minor comments (4)
  1. [Theorems 2 and 3, Corollary 1] Several displayed rates appear to be missing division slashes: for example, O(RM√δsδT) should likely be O(RM/√(δsδT)), and similarly for the bounds in Corollary 1. Please correct these formulas so the claimed dependencies on δ, δ_s, and T are unambiguous and consistent with the proof.
  2. [Section 4.1] The sentence 'We do not require operators {C_i}^n_{i=1} to be neither distinct nor independent' should read 'We do not require operators ... to be distinct or independent.'
  3. [Table 1] The table appears to duplicate the row for s=1.0; the third data row should presumably be s=10.0, matching the experiments in Section 6.1.
  4. [Appendix I] The phrase 'We follow the standard follow the standard implementation provided in Brax' contains a duplicated phrase and should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound and Safe-EF upper bound are derived independently, with explicit constants and no fitted inputs.

full rationale

The paper's central claims are not circular. The lower bound (Theorem 1, proved as Theorem 6 in Appendix E) is built from an explicit Nesterov-type worst-case function with constants C = M√T/(1+√δT) and μ = 2M/(R(1+√δT)), combined with Rand-K compression, and is proved through a coordinate-progress argument and Lemma 3; none of these ingredients is fitted to Safe-EF's rate. The upper bound (Theorem 2, proved in Appendix D) uses the standard virtual-iterate identity (22), Lemmas 1-2, and Corollary 1, which give explicit choices γ = R√(δsδ)/(M√T) and c = 32RM/(√(δsδT)); the advertised rate is obtained by direct substitution, not by tuning to a target. The stochastic analysis in Appendix F similarly derives explicit high-probability bounds with stated batch-size requirements. The few self-citations (e.g., Fatkhullin et al. 2021, 2023b, 2024) are used for background, baseline comparison, or a proof technique in the auxiliary Appendix C, and are not load-bearing for the main matching lower/upper bound claim. The Limitations section openly identifies sample-inefficiency and open questions, which is evidence against circularity. A separate concern is that the hard instance in Theorem 6 may violate Assumption 2 (since at x=0 the oracle returns a vector of norm C > M for the stated parameter range) and sets d = ⌊5Tδ⌋ while the theorem assumes T ≤ d, but this is a correctness issue, not a self-referential or fitted-input circularity.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new postulates beyond standard convexity, bounded subgradients, and sub-Gaussian noise assumptions. The algorithm combines existing components (EF14, switching subgradient, bidirectional compression); no new forces, particles, or abstract entities are invented.

free parameters (3)
  • stepsize γ = R√(δsδ)/(M√T) in Corollary 1; tuned in experiments (e.g., 0.01, 0.0003)
    Theoretical choice depends on unknown R, M, δ; in practice tuned by grid search.
  • threshold c = 32RM/(√(δsδT))
    Controls switching between objective and constraint subgradients; depends on unknown constants.
  • batch size N_fv = 1024 (default in RL experiments); required ≥ ~O(σ²/(n c²))
    Large batch needed for sub-Gaussian function evaluation; small batches fail in experiments.
assumptions (6)
  • domain assumption Assumption 1: fi and gi are convex for all i.
    Used in Lemma 1 to apply convexity inequalities for f and g.
  • domain assumption Assumption 2: fi and gi have M-bounded subgradients.
    Used to bound ||h_t|| and error terms in Lemma 2; central to the rate.
  • domain assumption Definition 1: contractive compressors with parameter δ.
    Defines the compression model for Top-K and Rand-K.
  • domain assumption Definition 3: zero-respecting property for the algorithm class in the lower bound.
    Restricts the lower bound class; Safe-EF is zero-respecting.
  • domain assumption Assumption 3: stochastic subgradients bounded by M and constraint evaluations sub-Gaussian.
    Used in Theorem 3 for high-probability bounds.
  • domain assumption Assumption 4: stochastic functions convex.
    Used in Theorem 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Safe-EF: Error Feedback for Nonsmooth Constrained Optimization." pith.science (2026). https://pith.science/paper/4YD74L2E

@misc{pith2026250506053,
  author       = {Pith},
  title        = {Pith review of: Safe-EF: Error Feedback for Nonsmooth Constrained Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4YD74L2E}},
  note         = {Machine review of arXiv:2505.06053}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2505.06053 by the authors.

Figure 1
Figure 1. Non-convergence of CGD, divergence of EF21 and convergence of Safe-EF for the problem f(x) = ∥x∥1, i = 1, d = 2 used in the proofs of Examples 1 and 2 with Top-1 compressor. We run all algorithms for T = 103 iterations with x 0 = (γ/2, −1)⊤, γ = 1/ √ T, and v 0 = (1, 1)⊤ (for EF21). ⋆Safe-EF coincides with EF14 [Seide et al., 2014] in this example. Example 2. Consider the problem instance from Example 1. For this in… view at source ↗
Figure 2
Figure 2. Comparison of Safe-EF against CGD, EF21, EF21M, and EControl on synthetic non-smooth problem. ⋆Safe-EF coincides with EF14 [Seide et al., 2014] in this problem. We begin with a simple empirical setup designed to easily verify that all assumptions of Safe-EF are satisfied. Specifically, we consider the unconstrained problem of the form (1), where fi = ∥Aix− bi∥1. For this objective, the subgradient f ′ i (x) = A⊤ i s… view at source ↗
Figure 3
Figure 3. Gigabytes required to reach a fixed benchmark performance for dif￾ferent compression ratios. Top-K can achieve the same performance as CGD, but with approximately two orders of magnitude less gigabytes. 0.0 0.5 1.0 1.5 #Gigabytes / worker 0 2000 4000 6000 8000 10000 ˆJr 0.0 0.5 1.0 1.5 #Gigabytes / worker 0 Budget 200 300 400 500 ˆJc Safe-EF (Ours) Parallel-CRPO EF14 EF21 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (7 more)
Figure 5
Figure 5. Figure 5: Convergence plots for different num￾ber of workers. While increasing the number of workers helps reduce the communication cost, the effect becomes less significant as the num￾ber of workers continues to grow. 7000 7200 7400 7600 7800 8000 8200 Jˆr 0.2 0.3 0.4 0.5 0.6 0…
Figure 7
Figure 7. Figure 7: Objective and constraint values of Safe-EF compared to Primal-dual with different initial￾ization values of λ 0 . Each point represents a distinct experiment trial with a different random seed. Safe-EF ensures safety and achieves solid performance without requiring add…
Figure 8
Figure 8. Figure 8: Objective and constraint in the Cartpole environment. [PITH_FULL_IMAGE:figures/full_fig_p050_8.png]
Figure 9
Figure 9. Figure 9: Performance for different compression ratios. [PITH_FULL_IMAGE:figures/full_fig_p051_9.png]
Figure 10
Figure 10. Figure 10: Safe-EF performance is only slightly degraded compared to a non-distributed baseline in terms of sample efficiency. However, in the distributed setup, as we observed in [PITH_FULL_IMAGE:figures/full_fig_p051_10.png]
Figure 11
Figure 11. Figure 11: Objective and constraint learning curves for different compression ratio. [PITH_FULL_IMAGE:figures/full_fig_p051_11.png]
Figure 12
Figure 12. Figure 12: Objective and constraint for Neyman-Pearson classification. Compared to the [PITH_FULL_IMAGE:figures/full_fig_p052_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 11 canonical work pages

  1. [1]

    The compression is performed vector-wise

    If workeri queries atyt i and zt i with [yt i]k̸= 0, then one of the following must be true:    there exists some0≤s<t such that [xs i ]k̸= 0; there exists some1≤s<t such that [Ofi,i(ys i )]k̸= 0 or [Ogi,i(ys i )]k̸= 0; there exists some1≤s<t such that workeri has received somev∈V t s→w with [v]k̸= 0; there exists some1≤s<t such that workeri ...

    work page

  2. [2]

    γE [∑ t∈Bf(xt)−f(x∗) ] ≤ 0. Proof. Let us usex =x∗ in Lemma 1. Taking the expectation and using the fact that∥ht∥≤ M, we get E [ γ ∑ t∈B f(xt)−f(x∗) ] + E [ γ ∑ t∈N c−g(xt) ] ≤ 1 2R2 + 1 2M 2 T−1∑ t=0 γ2 +M T−1∑ t=0 γ2E [ ∥et∥ ] (26) + M T−1∑ t=0 γE [ ∥ˆet∥ ] . (27) Using the properties of the compressors{Ci}n i=1, we get by induction that (with the choic...

    work page

  3. [3]

    If workeri aims to send somev∈V t wi→s with [v]k̸= 0, then one of the following must be true:    there exists some0≤s<t such that [xs i ]k̸= 0; there exists some1≤s<t such that [Oi,fi(ys i )]k̸= 0 or [Oi,gi(ys i )]k̸= 0; there exists some1≤s<t such that workeri has received somev′∈V t s→w with [v′]k̸= 0; there exists some1≤s<t such that worke...

    work page

  4. [4]

    If the server aims to broadcast somev∈V t s→w with [v]k̸= 0, then one of the following must be true: { there exists some1≤s<t and 1≤i≤n such that the server has received somev′∈V s wi→s with [v′]k̸= 0; Safe-EF is zero-respecting. Fundamentally, the zero-respecting property ensures that any in- crease in the number of nonzero coordinates inxt i,yt i, or ot...

    work page 2022

  5. [5]

    (Cited on page 13) Guanghui Lan and Zhiqiang Zhou. Algorithms for stochastic optimization with function or expec- tation constraints.Computational Optimization and Applications, 76(2):461–498, 2020.(Cited on pages 4, 7, and 9) Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan. Faster algorithm and sharper analysis for const...

    arXiv 2020

  6. [6]

    Truly no-regret learning in constrained MDPs

    (Cited on page 4) Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly no-regret learning in constrained MDPs. InInternational Conference on Machine Learning, 2024. (Cited on page 3) Chetan Nadiger, Anil Kumar, and Sherine Abdelhak. Federated reinforcement learning for fast personalization. In 2019 IEEE Second International Co...

    arXiv 2024

  7. [8]

    virtual iterates

    improved the constant dependencies in the rate ofEF21. EF21 variant of EF has been analyzed in the context of(L0,L 1)-smooth optimization [Khirirat et al., 2024], which is different from our non-smoothness since(L0,L 1)-smoothness implies smooth- ness on any compact set and failure examples as in Example 2 cannot happen under such assump- tion. On the oth...

    work page 2024

  8. [10]

    Therefore,|B|≥ T 2, i.e

    Therefore, from (30) we derive T 2γc≤ E [∑ t∈N γc ] ≤ 1 2R2 + 1 2M 2γ2T +M 2γ2 2 √ 1−δ δ T +M 2γ2 4 √ 10(1−δs) δsδ T, which contradicts (24). Therefore,|B|≥ T 2, i.e. part 1. holds. Now we are ready to prove our main theorem. Theorem 5. Suppose thatγ and c are chosen such that(24) holds. Then we have E [ f(xT )−f(x∗) ] ≤ R2 γT +M 2γ + 4M 2γ √ 1−δ δ + 8M 2...

    work page

Show all 18 references
  1. [11]

    This implies that E [ f(xT )−f(x∗) ] ≤ 2 γT ( 1 2R2 + 1 2M 2γ2T +M 2γ2 2 √ 1−δ δ T +M 2γ2 4 √ 10(1−δs) δsδ T

    Since g(x∗)≤ 0, from (25) we obtain γE [∑ t∈B f(xt)−f(x∗) ] ≤ 1 2R2 + 1 2M 2γ2T +M 2γ2 2 √ 1−δ δ T +M 2γ2 4 √ 10(1−δs) δsδ T. This implies that E [ f(xT )−f(x∗) ] ≤ 2 γT ( 1 2R2 + 1 2M 2γ2T +M 2γ2 2 √ 1−δ δ T +M 2γ2 4 √ 10(1−δs) δsδ T. ) = R2 γT +M 2γ + 4M 2γ √ 1−δ δ + 8M 2γ √...

    2022

  2. [13]

    If the local modelxt i of workeri, aftert-th query, has [xt i]k̸= 0, then one of the following must be true:    there exists some0≤s<t such that [xs i ]k̸= 0; there exists some1≤s<t such that [Ofi,i(ys i )]k̸= 0 or [Ogi,i(ys i )]k̸= 0; there exists some1≤s<t such ...

  3. [16]

    γ∑ t∈Bf(xt)−f(x∗)≤ 0. Proof. Assume thatB =∅. Then from Corollary 2 we have that with probability at least1−β we have Tγc≤C1 log 1 β +∥x0−x∗∥2 +γ2M 2 ( 50 + 12 √ 1−δ δ ) T + 8σ2 fv C1nNfv Tγ 2, This contradicts the assumption of the lemma. Hence, we must haveB̸ =∅. Now assume ...

  4. [17]

    Hence, ifγ∑ t∈B(f(xt)−f(x∗))> 0, then|B|≥ T 2

    Therefore, we have T 2γc≤ ∑ t∈N γc≤C1 log 1 β +∥x0−x∗∥2 +γ2M 2 ( 50 + 12 √ 1−δ δ ) T + 8σ2 fv C1nNfv Tγ 2, which contradicts (52). Hence, ifγ∑ t∈B(f(xt)−f(x∗))> 0, then|B|≥ T 2. Now we are ready to establish our main convergence result in the stochastic setting. Theorem 8. Let...

  5. [18]

    46 Corollary 3

    Therefore, from (52) we obtain f(xT )−f(x∗)≤ 2 γT ( C1 log 1 β +∥x0−x∗∥2 +γ2M 2 ( 50 + 12 √ 1−δ δ ) + 8σ2 fv C1nNfv Tγ 2 ) = 2C1 log 1 β + 2∥x0−x∗∥2 γT + 2γM 2 ( 50 + 12 √ 1−δ δ ) T + 16σ2 fv C1nNfv γ. 46 Corollary 3. Let β∈ (0, 1/2) be the failure probability. Let R2≥∥x0−x∗∥2...

    2000

  6. [2019]

    Sparsified SGD with memory

    (Cited on pages 8 and 27) 19 Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. Advances in neural information processing systems, 31, 2018. (Cited on pages 2, 5, and 22) Richard S Sutton, David McAllester, Satinder Singh, and Yishay Man...

    2018

  7. [2020]

    High-probability convergence for com- posite and distributed stochastic minimization and variational inequalities with heavy-tailed noise

    (Cited on page 22) EduardGorbunov, AbdurakhmonSadiev, MarinaDanilova, SamuelHorváth, GauthierGidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability convergence for com- posite and distributed stochastic minimization and variational inequalities wi...

    2024 arXiv

  8. [2022]

    On biased compres- sion for distributed learning.Journal of Machine Learning Research, 24(276):1–50, 2023

    (Cited on page 22) Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compres- sion for distributed learning.Journal of Machine Learning Research, 24(276):1–50, 2023. (Cited on pages 2, 5, 8, and 23) Digvijay Boob and Mohammad Khalafi. Optimal ...

    2023 arXiv

  9. [2023]

    (Cited on page 22) Yankun Huang and Qihang Lin. 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 4) Florian Hü...

    2023 arXiv

  10. [2024]

    Stochastic first-order methods for convex and non- convex functional constrained optimization.Mathematical Programming, 197(1):215–279, 2023

    (Cited on page 4) Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and non- convex functional constrained optimization.Mathematical Programming, 197(1):215–279, 2023. (Cited on pages 4, 12, and 13) Digvijay Boob, Qi Deng, and Guanghui Lan. Le...

    2023 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.