Pith. sign in

REVIEW 2 major objections 5 minor 58 references

Decentralized Stochastic Nonconvex Optimization under the $(L_0,L_1)$-Smoothness

T0 review · 2 major / 5 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 Under relaxed smoothness, the decentralized algorithm DNSGD brings every agent to an $\epsilon$-stationary point, with per-agent sample cost spread as $1/m$ and communication cost set by the network spectral gap.

desk verdict Smart Lyapunov idea, but the proof of the load-bearing Lemma 3 contains an algebraic inequality that fails in the admissible parameter range, so the main theorem is not established as written. read the letter →

arxiv 2509.08726 v3 pith:L34YTFVH submitted 2025-09-10 math.OC cs.LG

Luo Luo , Xue Cui , Tingkai Jia , Cheng Chen This is my paper · ORCID
classification math.OCcs.LG MSC 90C2690C1568W15
keywords decentralizedoptimizationrelaxedsmoothness(L0L1)-smoothnessnormalizedstochasticgradientdescentnonconvexconsensuserrortrackingChebyshevacceleration
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

Relaxed smoothness, the condition that a gradient may change arbitrarily fast when the gradient itself is large, models neural-network training better than classical Lipschitz smoothness but has mostly been studied on a single machine. This paper claims the same guarantee is achievable in a decentralized network: a new algorithm, DNSGD, combines normalized stochastic gradients, gradient tracking, and Chebyshev-accelerated gossip, and proves each agent reaches an $\epsilon$-stationary point. The per-agent sample complexity is $O(m^{-1}(L_f\sigma^2\Delta_f\epsilon^{-4}+\sigma^2\epsilon^{-2}+L_f^{-2}L_1^3\sigma^2\Delta_f\epsilon^{-1}+L_f^{-2}L_1^2\sigma^2))$ with $L_f=L_0+L_1\zeta$, and the communication complexity is $\tilde{O}((L_f\epsilon^{-2}+L_1\epsilon^{-1})\gamma^{-1/2}\Delta_f)$. When $L_1=0$ these rates nearly match known lower bounds for standard-smooth decentralized nonconvex optimization; when $m=1$ they match the best-known complexity for exact-gradient relaxed-smooth problems.

What carries the argument

The load-bearing object is the Lyapunov function $\Phi_t=f(\bar{x}_t)+3\eta\sqrt{m}(M_0+M_1\|\nabla f(\bar{x}_t)\|)\|X_t-\mathbf{1}\bar{x}_t\|+2\eta\sqrt{m}\|V_t-\mathbf{1}\bar{v}_t\|$, where $X_t$ stacks the local iterates, $V_t$ stacks the local gradient estimators, and $\bar{x}_t,\bar{v}_t$ are their averages; $M_0=\sqrt{2(L_0^2+L_1^2\zeta^2)}$ and $M_1=\sqrt{2}L_1$. The product $(M_0+M_1\|\nabla f(\bar{x}_t)\|)\|X_t-\mathbf{1}\bar{x}_t\|$ mirrors the right-hand side of the relaxed-smoothness inequality, so the descent analysis can absorb consensus error even though $\nabla f$ has no Lipschitz bound. Around this Lyapunov function the algorithm uses normalized descent steps $v_t^i/\|v_t^i\|$, a gradient-tracking update $V_{t+1}=\mathrm{AccGossip}(V_t+G_{t+1}-G_t,K)$, and multi-consensus Chebyshev acceleration that contracts consensus error by a factor $\rho\le O(1/\sqrt{m})$ after $K=O(\gamma^{-1/2}\log m)$ rounds.

What would settle it

Run DNSGD in the centralized limit ($m=1$, exact gradients, $\zeta=0$), where it reduces to normalized gradient descent and the paper predicts iteration complexity $O(L_0\Delta_f\epsilon^{-2}+L_1\Delta_f\epsilon^{-1})$ for any nonconvex $(L_0,L_1)$-smooth function. Exhibiting one such function that needs more iterations to reach $\|\nabla f\|\le\epsilon$, or numerically detecting a violation of the Lyapunov descent inequality (5), would defeat the claimed rates.

Watch

Extended reading notes

Core claim

The central claim is that under the paper's formal assumptions, DNSGD computes, for every agent $i$, a point $\hat{x}_i$ sampled from that agent's local history with $\mathbb{E}[\|\nabla f(\hat{x}_i)\|]\le\epsilon$. The proof sets the step size to $\eta=\min\{\epsilon/(4L_f+1), 1/(2L_1)\}$, the mini-batch size to $b\ge\max\{256(4L_f+1)^2\sigma^2/(mL_f^2\epsilon^2), 1024L_1^2\sigma^2/(mL_f^2)\}$, the iteration count to $T\ge\max\{8(4L_f+1)\Delta_\Phi/\epsilon^2, 16L_1\Delta_\Phi/\epsilon\}$, and the number of Chebyshev communication rounds to $K=\tilde{O}(1/\sqrt{\gamma})$, so the consensus error is small enough that every local iterate, not only the hidden average, satisfies the stationarity guarantee. The analysis is driven by a Lyapunov function that couples function value, gradient norm, and consensus error, avoiding any need to bound the local gradients or assume they are Lipschitz continuous.

Load-bearing premise

The argument stands on the assumption that each local gradient stays within a fixed distance $\zeta$ of the global gradient everywhere; if this fails, the averaged objective can stop being relaxed smooth even when every local objective is, and the paper leaves decentralized convergence in that case open.

Editorial extensions

If this is right

  • Every agent can certify an $\epsilon$-stationary point from its own iterates, so the guarantee is fully decentralized and does not depend on a globally available mean.
  • The $1/m$ factor in the sample complexity means linear speedup: doubling the number of agents halves the per-agent sample requirement when heterogeneity and spectral gap are held fixed.
  • In the standard-smoothness limit $L_1=0$, the bounds reduce to $O(m^{-1}(L_0\sigma^2\Delta_f\epsilon^{-4}+\sigma^2\epsilon^{-2}))$ samples per agent and $\tilde{O}(L_0\Delta_f\gamma^{-1/2}\epsilon^{-2})$ communications, nearly matching the lower bounds.
  • In the single-agent limit, the method matches the best-known iteration complexity for exact-gradient relaxed-smooth nonconvex optimization and improves on the clipping-based stochastic bound in the regime where that bound dominates.

Reading between the lines

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

  • The Lyapunov product structure is likely reusable in other non-Lipschitz decentralized settings; pairing DNSGD with variance-reduced estimators could plausibly turn the $\epsilon^{-4}$ sample term into an $\epsilon^{-3}$ term, a route the paper itself identifies.
  • Without bounded gradient dissimilarity, a proof cannot rely on the averaged objective being relaxed smooth, since Proposition 3 shows the average of two relaxed-smooth exponentials leaves the class; a gradient-tracking analysis that uses only local relaxed smoothness would be the natural next step.
  • A direct stress test is to run DNSGD on mixtures of rapidly growing exponentials and increase the heterogeneity parameter $\zeta$; the theory predicts the difficulty should appear exactly where the averaged objective loses relaxed smoothness.
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 / 5 minor

Summary. The paper studies decentralized stochastic optimization of a finite average of local functions under (L0,L1)-relaxed smoothness and bounded gradient dissimilarity. It proposes DNSGD, which combines normalized stochastic gradients with gradient tracking and Chebyshev-accelerated gossip. The main theoretical result (Theorem 1 and Corollary 1) is an epsilon-stationarity guarantee for every local agent, with per-agent sample complexity O(m^{-1}(L_f sigma^2 Delta_f epsilon^{-4} + sigma^2 epsilon^{-2} + L_f^{-2} L_1^3 sigma^2 Delta_f epsilon^{-1} + L_f^{-2} L_1^2 sigma^2)) and communication complexity O~( (L_f epsilon^{-2} + L_1 epsilon^{-1}) Delta_f gamma^{-1/2} ). When L1=0, the sample complexity nearly matches known decentralized lower bounds. The analysis introduces a Lyapunov function that includes the product of the gradient norm and the consensus error. The paper also contains a counterexample (Proposition 3) showing that local relaxed smoothness alone does not imply global relaxed smoothness, and it explicitly leaves the decentralized setting without bounded gradient dissimilarity as an open problem.

Significance. The proposed Lyapunov framework is the main novelty: it avoids gradient clipping and handles non-Lipschitz, unbounded local gradients. If the proof gap described below is repaired, the paper would be a useful contribution to decentralized relaxed-smooth optimization. The special-case match to lower bounds in the L1=0 setting is a strong point, and the paper is transparent about the role of Assumption 3. The full proofs and numerical comparisons are also valuable. However, the central lemma used to control the gradient-tracking consensus error contains an invalid algebraic step, so the main theorem is not established as written. The revision should focus on repairing that step rather than on the algorithmic concept, which is sound in outline.

major comments (2)
  1. [Appendix E, Eq. (20)] The final inequality in (20) is false in the parameter regime of Theorem 1. Set L1=0, m=2, Lf=1, t=0, and X0=1bar{x}_0. Then A=m eta, G=||grad f(bar{x}_0)||, M2=1+rho, M3=0, and the claimed inequality becomes 3rho^2(2eta)^2 + 6eta^2 <= (1+rho)^2(2eta)^2, i.e. 12rho^2 + 6 <= 4(1+rho)^2, equivalently (2rho-1)^2 <= 0. This holds only at rho=1/2, whereas the conditions in Appendix F require rho <= O(1/sqrt(m)) and, for m=2, force rho to be considerably smaller than 1/2. Hence the displayed bound on ||grad f(X_{t+1}) - grad f(X_t)|| is not valid. Since Lemma 3 is used to derive the Lyapunov recursion (5) and then Theorem 1, the main convergence proof is incomplete as written. The lemma may be salvageable with a tighter triangle bound, but the current proof does not establish it.
  2. [Algorithm 2, line 6] The update U_t sets the i-th row to v_i^t / ||v_i^t||. This is undefined whenever ||v_i^t|| = 0. Such an event is not excluded by Assumptions 1-5; it can occur with positive probability for a mini-batch gradient estimate, or deterministically when an agent reaches a stationary point. The authors should specify a convention (for instance, define 0/0 = 0) and check that Lemmas 1-3 and Theorem 1 remain valid under that convention, or modify the algorithm with a small perturbation.
minor comments (5)
  1. [Title and abstract] The title and abstract claim decentralized optimization 'under the (L0,L1)-smoothness', while Theorem 1 requires the additional bounded-gradient-dissimilarity assumption (Assumption 3). This qualification should appear wherever the main claim is stated.
  2. [Appendix E, after Eq. (22)] The combining step in the proof of Lemma 3 writes 2rho sqrt(m) sigma / b, but Eq. (22) and the statement of the lemma require 2rho sqrt(m) sigma / sqrt(b). Please correct this typo.
  3. [Appendix A, Lemma 5 proof] The phrase 'vector AM-QM inequality' is not the correct name for the inequality used in the first bound of the proof of Lemma 5; the intended step is the triangle inequality. Please correct the terminology.
  4. [Section 6] The numerical comparison appears to be based on single runs and no error bars are reported. The claim that DNSGD outperforms all baselines would be more convincing with multiple seeds and standard deviations.
  5. [Abstract and notation] The abstract refers to a connected network of n agents while the rest of the paper uses m for the number of agents; please make the notation consistent.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the convergence bound is derived from Assumptions 1-5 via an analytic Lyapunov argument; self-citations are independent prior lemmas.

full rationale

The derivation chain is not circular. Theorem 1 is obtained by summing the one-step Lyapunov decrease shown in inequality (5), which is proved from Lemmas 1-3 and 8-9 using Assumptions 1-5; no quantity being bounded is used as an input. The Lyapunov coefficients M0, M1, M2, M3 and the parameter choices eta, b, T, K are fixed analytically from problem constants and the target accuracy epsilon, and the final sample and communication bounds are consequences of those choices rather than fitted values. The self-citations (Ye et al. [52, Proposition 1] for Chebyshev consensus contraction; Luo et al. [34, Lemma 2]; Zhang et al. [55, Lemma 7]; Li et al. [26, Lemma B.5]) are prior published technical lemmas with stated assumptions that do not include the target result; under the review rules, such citations count as independent support rather than circularity. The claimed match to lower bounds in the L1=0 and m=1 special cases is benchmarked against external results [33, 47, 55]. The paper explicitly flags that Assumption 3 is load-bearing and that removing it is open; that is assumption-dependence, not circularity. The reviewer concern about inequality (20) in Lemma 3 is a potential correctness defect in an algebraic step, not a reduction of the theorem to its inputs, so it does not change the circularity score.

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

No data-fitting parameters are present; the step size η, batch size b, and iteration counts T, K are set by the theorem in terms of problem constants. The proof relies on standard decentralized optimization assumptions, with the strongest being Assumption 3 on gradient dissimilarity.

assumptions (6)
  • domain assumption Assumption 1: the objective f is lower bounded by f* > -infinity.
    Standard for nonconvex optimization; ensures function value gaps are finite.
  • domain assumption Assumption 2: each local function f_i is (L0,L1)-smooth with ||∇f_i(x)-∇f_i(y)|| ≤ (L0 + L1||∇f_i(x)||)||x-y|| for ||x-y|| ≤ 1/L1.
    Central smoothness model for the paper; weaker than the original second-order definition, cited to Zhang et al. [55].
  • domain assumption Assumption 3: bounded gradient dissimilarity, ||∇f_i(x)-∇f(x)|| ≤ ζ for all i and x.
    Load-bearing for global relaxed smoothness and Lemma 9; the paper acknowledges that removing it is an open problem.
  • domain assumption Assumption 4: stochastic gradients are unbiased with bounded variance σ².
    Standard oracle model; enables the sample complexity analysis.
  • domain assumption Assumption 5: symmetric mixing matrix W with 0 ⪯ W ⪯ I, W1=1, and spectral gap γ > 0.
    Standard in decentralized optimization; supports the use of Chebyshev acceleration.
  • standard math Proposition 2 from Ye et al.: Chebyshev accelerated gossip contracts consensus error geometrically with rate 1 - c2√γ.
    Used to control consensus errors; quoted from a published source rather than proved in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Decentralized Stochastic Nonconvex Optimization under the $(L_0,L_1)$-Smoothness." pith.science (2026). https://pith.science/paper/L34YTFVH

@misc{pith2026250908726,
  author       = {Pith},
  title        = {Pith review of: Decentralized Stochastic Nonconvex Optimization under the $(L_0,L_1)$-Smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L34YTFVH}},
  note         = {Machine review of arXiv:2509.08726}
}
abstract

This paper focuses on the decentralized stochastic optimization problem $f(\mathbf{x})=\frac{1}{m}\sum_{i=1}^m f_i(\mathbf{x})$ over a connected network of $n$ agents, where each local function has the form of $f_i(\mathbf{x}) = {\mathbb E}\left[F(\mathbf{x};{\boldsymbol \xi}_i)\right]$ which satisfies the $(L_0,L_1)$-smooth condition but possibly nonconvex and each random variable ${\boldsymbol \xi}_i$ follows distribution ${\mathcal D}_i$. We propose a novel algorithm called decentralized normalized stochastic gradient descent (DNSGD), which can achieve an $\epsilon$-stationary point at each local agent. We present a new framework for analyzing decentralized first-order methods in the $(L_0,L_1)$-smooth setting, based on the Lyapunov function related to the product of the gradient norm and the consensus error. We show that the proposed algorithm attains the upper bounds on the sample complexity of ${\mathcal O}(m^{-1}(L_f\sigma^2\Delta_f\epsilon^{-4} + \sigma^2\epsilon^{-2} + L_f^{-2}L_1^3\sigma^2\Delta_f\epsilon^{-1} + L_f^{-2}L_1^2\sigma^2))$ per agent and the communication complexity of $\tilde{\mathcal O}((L_f\epsilon^{-2} + L_1\epsilon^{-1})\gamma^{-1/2}\Delta_f)$, where $L_f=L_0 +L_1\zeta$, $\sigma^2$ is the variance of the stochastic gradient, $\Delta_f$ is the initial optimal function value gap, $\gamma$ is the spectral gap of the network, and $\zeta$ is the degree of the gradient dissimilarity. In the special case of $L_1=0$, the above results (nearly) match the lower bounds of decentralized stochastic nonconvex optimization under the standard smoothness. We also conduct numerical experiments to show the empirical superiority of our method.

Figures

Figures reproduced from arXiv: 2509.08726 by the authors.

Figure 1
Figure 1. We present numerical results on the MNIST dataset over the Erd¨os-R´enyi network. The subfigures [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. We present numerical results on the Fashion-MNIST dataset over the Erd¨os-R´enyi network. The [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. We present numerical results on the MNIST dataset over the ring network. The subfigures (a) and [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: We present numerical results on the Fashion-MNIST dataset over the ring network. The subfigures [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 44 canonical work pages

  1. [1]

    Chebyshev acceleration of iterative refinement.Numerical Algorithms, 66(3):591–608, 2014

    Mario Arioli and Jennifer Scott. Chebyshev acceleration of iterative refinement.Numerical Algorithms, 66(3):591–608, 2014

    work page 2014

  2. [2]

    Stochastic gradient push for distributed deep learning

    Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. InInternational Conference on Machine Learning, pages 344–353, 2019

    work page 2019

  3. [3]

    On the complexity of finite-sum smooth optimization under the Polyak– Lojasiewicz condition

    Yunyan Bai, Yuxing Liu, and Luo Luo. On the complexity of finite-sum smooth optimization under the Polyak– Lojasiewicz condition. InInternational Conference on Machine Learning, pages 2392–2417, 2024

    work page 2024

  4. [4]

    Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization

    Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. InInternational Conference on Machine Learning, pages 5396–5427, 2023

    work page 2023

  5. [5]

    Convergence of clipped-SGD for convex ( L0,L 1)-smooth optimization with heavy-tailed noise.arXiv preprint arXiv:2505.20817, 2025

    Savelii Chezhegov, Aleksandr Beznosikov, Samuel Horv´ ath, and Eduard Gorbunov. Convergence of clipped-SGD for convex ( L0,L 1)-smooth optimization with heavy-tailed noise.arXiv preprint arXiv:2505.20817, 2025

    arXiv 2025

  6. [6]

    Y. Cooper. An empirical study of the (L 0,L 1)-smoothness condition. InWorkshop on Mathematics of Modern Machine Learning, 2022

    work page 2022

  7. [7]

    Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness

    Michael Crawshaw and Mingrui Liu. Complexity lower bounds of adaptive gradient algorithms for non-convex stochastic optimization under relaxed smoothness.arXiv preprint arXiv:2505.04599, 2025

    work page Pith review arXiv 2025

  8. [8]

    Robustness to unbounded smoothness of generalized SignSGD

    Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized SignSGD. InAdvances in Neural Information Processing Systems, pages 9955–9968, 2022

    work page 2022

Show all 58 references
  1. [9]

    Momentum improves normalized SGD

    Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. InInternational Conference on Machine Learning, pages 2260–2268, 2020

    2020

  2. [10]

    On random graphs I.Publicationes Mathematicae Debrecen, 6(290-297): 18, 1959

    Paul Erd˝ os and Alfr´ ed R´ enyi. On random graphs I.Publicationes Mathematicae Debrecen, 6(290-297): 18, 1959

    1959

  3. [11]

    SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator

    Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. InAdvances in Neural Information Processing Systems, pages 687–697, 2018

    2018

  4. [12]

    Convergence of clipped SGD on convex (L0,L 1)-smooth functions.arXiv preprint arXiv:2502.16492, 2025

    Ofir Gaash, Kfir Yehuda Levy, and Yair Carmon. Convergence of clipped SGD on convex (L0,L 1)-smooth functions.arXiv preprint arXiv:2502.16492, 2025

    2025 arXiv

  5. [13]

    Local SGD: Unified theory and new efficient methods

    Eduard Gorbunov, Filip Hanzely, and Peter Richt´ arik. Local SGD: Unified theory and new efficient methods. InInternational Conference on Artificial Intelligence and Statistics, pages 3556–3564, 2021

    2021

  6. [14]

    Methods for convex (L0,L 1)-smooth optimization: Clipping, acceleration, and adaptivity.arXiv preprint arXiv:2409.14989, 2024

    Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richt´ arik, Samuel Horv´ ath, and Martin Tak´ aˇ c. Methods for convex (L0,L 1)-smooth optimization: Clipping, acceleration, and adaptivity.arXiv preprint arXiv:2409.14989, 2024

    2024 arXiv

  7. [15]

    Beyond convexity: Stochastic quasi-convex optimization

    Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. InAdvances in Neural Information Processing Systems, pages 1594–1602, 2015

    2015

  8. [16]

    An optimal algorithm for decentralized finite-sum optimization.SIAM Journal on Optimization, 31(4):2753–2783, 2021

    Hadrien Hendrikx, Francis Bach, and Laurent Massoulie. An optimal algorithm for decentralized finite-sum optimization.SIAM Journal on Optimization, 31(4):2753–2783, 2021

    2021

  9. [17]

    Decentralized relaxed smooth optimization with gradient descent methods.arXiv preprint arXiv:2508.08413, 2025

    Zhanhong Jiang, Aditya Balu, and Soumik Sarkar. Decentralized relaxed smooth optimization with gradient descent methods.arXiv preprint arXiv:2508.08413, 2025

    2025 arXiv

  10. [18]

    Communication-efficient algorithms under generalized smoothness assumptions.OpenReview, 2024

    Sarit Khirirat, Abdurakhmon Sadiev, Artem Riabinin, Eduard Gorbunov, and Peter Richt´ arik. Communication-efficient algorithms under generalized smoothness assumptions.OpenReview, 2024. 10

    2024

  11. [19]

    Error feedback under (L0,L 1)-smoothness: Normalization and momentum.arXiv preprint arXiv:2410.16871, 2024

    Sarit Khirirat, Abdurakhmon Sadiev, Artem Riabinin, Eduard Gorbunov, and Peter Richt´ arik. Error feedback under (L0,L 1)-smoothness: Normalization and momentum.arXiv preprint arXiv:2410.16871, 2024

    2024 arXiv

  12. [20]

    Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U. Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. InInternational Conference on Machine Learning, pages 17343– 17363, 2023

    2023

  13. [21]

    Lower bounds and optimal algorithms for non-smooth convex decentralized optimization over time-varying networks

    Dmitry Kovalev, Ekaterina Borodich, Alexander Gasnikov, and Dmitrii Feoktistov. Lower bounds and optimal algorithms for non-smooth convex decentralized optimization over time-varying networks. In Advances in Neural Information Processing Systems, pages 96566–96606, 2024

    2024

  14. [22]

    Communication-efficient algorithms for decentralized and stochastic optimization.Mathematical Programming, 180(1):237–284, 2020

    Guanghui Lan, Soomin Lee, and Yi Zhou. Communication-efficient algorithms for decentralized and stochastic optimization.Mathematical Programming, 180(1):237–284, 2020

    2020

  15. [23]

    Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 2002

    Yann LeCun, L´ eon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 2002

    2002

  16. [24]

    Convergence of adam under relaxed assumptions

    Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, pages 52166–52196, 2023

    2023

  17. [25]

    Variance reduced EXTRA and DIGing and their optimal acceleration for strongly convex decentralized optimization.Journal of Machine Learning Research, 23 (222):1–41, 2022

    Huan Li, Zhouchen Lin, and Yongchun Fang. Variance reduced EXTRA and DIGing and their optimal acceleration for strongly convex decentralized optimization.Journal of Machine Learning Research, 23 (222):1–41, 2022

    2022

  18. [26]

    Problem-parameter-free decentralized nonconvex stochastic optimization.arXiv preprint arXiv:2402.08821, 2024

    Jiaxiang Li, Xuxing Chen, Shiqian Ma, and Mingyi Hong. Problem-parameter-free decentralized nonconvex stochastic optimization.arXiv preprint arXiv:2402.08821, 2024

    2024 arXiv

  19. [27]

    Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent

    Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. InAdvances in Neural Information Processing Systems, pages 5336–5346, 2017

    2017

  20. [28]

    Decentralized gradient-free methods for stochastic non-smooth non-convex optimization

    Zhenwei Lin, Jingfan Xia, Qi Deng, and Luo Luo. Decentralized gradient-free methods for stochastic non-smooth non-convex optimization. InAAAI Conference on Artificial Intelligence, pages 17477–17486, 2024

    2024

  21. [29]

    Stephen Morse

    Ji Liu and A. Stephen Morse. Accelerated linear iterations for distributed averaging.Annual Reviews in Control, 35(2):160–165, 2011

    2011

  22. [30]

    Decentralized convex finite-sum optimization with better dependence on condition numbers

    Yuxing Liu, Lesi Chen, and Luo Luo. Decentralized convex finite-sum optimization with better dependence on condition numbers. InInternational Conference on Machine Learning, pages 30807–30841, 2024

    2024

  23. [31]

    Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping.arXiv preprint arXiv:2412.19529, 2024

    Zijian Liu and Zhengyuan Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping.arXiv preprint arXiv:2412.19529, 2024

    2024 arXiv

  24. [32]

    Linear convergence rate in convex setup is possible! gradient descent method variants under ( L0,L 1)-smoothness.arXiv preprint arXiv:2412.17050, 2024

    Aleksandr Lobanov, Alexander Gasnikov, Eduard Gorbunov, and Martin Tak´ aˇ c. Linear convergence rate in convex setup is possible! gradient descent method variants under ( L0,L 1)-smoothness.arXiv preprint arXiv:2412.17050, 2024

    2024 arXiv

  25. [33]

    Optimal complexity in decentralized training

    Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. InInternational conference on machine learning, pages 7111–7123, 2021

    2021

  26. [34]

    On the complexity of decentralized finite-sum nonconvex optimization.arXiv preprint arXiv:2210.13931, 2022

    Luo Luo, Yunyan Bai, Lesi Chen, Yuxing Liu, and Haishan Ye. On the complexity of decentralized finite-sum nonconvex optimization.arXiv preprint arXiv:2210.13931, 2022

    2022 arXiv

  27. [35]

    Danilo P. Mandic. A generalized normalized gradient descent algorithm.IEEE Signal Processing Letters, 11(2):115–118, 2004

    2004

  28. [36]

    Decentralized finite-sum optimization over time-varying networks.arXiv preprint arXiv:2402.02490, 2024

    Dmitry Metelev, Savelii Chezhegov, Alexander Rogozin, Aleksandr Beznosikov, Alexander Sholokhov, Alexander Gasnikov, and Dmitry Kovalev. Decentralized finite-sum optimization over time-varying networks.arXiv preprint arXiv:2402.02490, 2024. 11

    2024 arXiv

  29. [37]

    Distributed subgradient methods for multi-agent optimization

    Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009

    2009

  30. [38]

    Achieving geometric convergence for distributed optimization over time-varying graphs.SIAM Journal on Optimization, 27(4):2597–2633, 2017

    Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs.SIAM Journal on Optimization, 27(4):2597–2633, 2017

    2017

  31. [39]

    Network topology and communication- computation tradeoffs in decentralized optimization.Proceedings of the IEEE, 106(5):953–976, 2018

    Angelia Nedi´ c, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization.Proceedings of the IEEE, 106(5):953–976, 2018

    2018

  32. [40]

    Harnessing smoothness to accelerate distributed optimization.IEEE Transactions on Control of Network Systems, 5(3):1245–1260, 2017

    Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization.IEEE Transactions on Control of Network Systems, 5(3):1245–1260, 2017

    2017

  33. [41]

    Variance-reduced clipping for non-convex optimization

    Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. InInternational Conference on Acoustics, Speech and Signal Processing, pages 1–5, 2025

    2025

  34. [42]

    An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization

    Emre Sahinoglu and Shahin Shahrampour. An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization. InInternational Conference on Machine Learning, pages 43043–43059, 2024

    2024

  35. [43]

    Optimal algorithms for smooth and strongly convex distributed optimization in networks

    Kevin Scaman, Francis Bach, S´ ebastien Bubeck, Yin Tat Lee, and Laurent Massouli´ e. Optimal algorithms for smooth and strongly convex distributed optimization in networks. InInternational Conference on Machine Learning, pages 3027–3036, 2017

    2017

  36. [44]

    Optimal gradient tracking for decentralized optimization

    Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan. Optimal gradient tracking for decentralized optimization. Mathematical Programming, 207(1):1–53, 2024

    2024

  37. [45]

    Revisiting stochastic proximal point methods: Generalized smoothness and similarity.arXiv preprint arXiv:2502.03401, 2025

    Zhirayr Tovmasyan, Grigory Malinovsky, Laurent Condat, and Peter Richt´ arik. Revisiting stochastic proximal point methods: Generalized smoothness and similarity.arXiv preprint arXiv:2502.03401, 2025

    2025

  38. [46]

    Toward a unified theory of gradient descent under generalized smoothness

    Alexander Tyurin. Toward a unified theory of gradient descent under generalized smoothness. In International Conference on Learning Representations, 2025

    2025

  39. [47]

    Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, and Sebastian U. Stich. Optimizing (L0,L 1)-smooth functions by gradient methods. InInternational Conference on Learning Representations, 2025

    2025

  40. [48]

    Woodworth, Kumar Kshitij Patel, and Nati Srebro

    Blake E. Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local SGD for heterogeneous distributed learning. InAdvances in Neural Information Processing Systems, pages 6281–6292, 2020

    2020

  41. [49]

    Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms.arXiv preprint arXiv:1708.07747, 2017

    Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms.arXiv preprint arXiv:1708.07747, 2017

    2017 arXiv

  42. [50]

    Trust region methods for nonconvex stochastic optimization beyond lipschitz smoothness

    Chenghan Xie, Chenxi Li, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. Trust region methods for nonconvex stochastic optimization beyond lipschitz smoothness. InAAAI Conference on Artificial Intelligence, pages 16049–16057, 2024

    2024

  43. [51]

    Ran Xin, Shi Pu, Angelia Nedi´ c, and Usman A. Khan. A general framework for decentralized optimization with first-order methods.Proceedings of the IEEE, 108(11):1869–1889, 2020

    2020

  44. [52]

    Multi-consensus decentralized accelerated gradient descent.Journal of Machine Learning Research, 24(306):1–50, 2023

    Haishan Ye, Luo Luo, Ziang Zhou, and Tong Zhang. Multi-consensus decentralized accelerated gradient descent.Journal of Machine Learning Research, 24(306):1–50, 2023

    2023

  45. [53]

    Mirror descent under generalized smoothness

    Dingzhi Yu, Wei Jiang, Yuanyu Wan, and Lijun Zhang. Mirror descent under generalized smoothness. arXiv preprint arXiv:2502.00753, 2025

    2025 arXiv

  46. [54]

    Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization

    Kun Yuan, Xinmeng Huang, Yiming Chen, Xiaohan Zhang, Yingya Zhang, and Pan Pan. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. InAdvances in Neural Information Processing Systems, pages 36382–36395, 2022. 12

    2022

  47. [55]

    Improved analysis of clipping algorithms for non-convex optimization

    Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. InAdvances in Neural Information Processing Systems, pages 15511–15521, 2020

    2020

  48. [56]

    1 T T−1X t=0 ∇f( ¯xt) # ≤E 8(Φ0−Φ T ) 5ηT + 6ηLf 5 ≤ 8∆Φ 5ηT + 6ηLf 5 , where the last step holds due to E[Φ0−Φ T ] =E

    Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. InInternational Conference on Learning Representations, 2020. A Some Technical Lemmas We first provide some technical lemmas for ...

    2020

  49. [57]

    In the case ofϵ/(4L f + 1)≤1/(2L 1), we follow the setting η= ϵ 4Lf + 1, b≥ & 256(4Lf + 1)2σ2 mL2 fϵ2 ’ ,andT≥ 8∆Φ ηϵ = 8(4Lf + 1)∆Φ ϵ2 (24) to obtain E " 1 T T−1X t=0 ∇f( ¯xt) # ≤ ϵ 5 + 3ϵ 10 = ϵ 2

  50. [58]

    1 T T−1X t=0 ∇f(x t i) # ≤E

    In the case of 1/(2L 1)≤ϵ/(4L f + 1), we follow the setting η= 1 2L1 , b≥ & 1024L2 1σ2 mL2 f ’ ,andT≥ 16L1∆Φ ϵ .(25) to obtain E " 1 T T−1X t=0 ∇f( ¯xt) # ≤ ϵ 5 + 3ϵ 10 = ϵ 2. Hence, we finish the proof. G The Proof of Corollary 1 Proof.We first provide the upper bound forE V0...

Pith tools

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