betaFeedback

WorksMathematics

Continuized Quasar-Convex Acceleration via an Unbiased Finite-Mixing Network Oracle

Abstract

We study decentralized minimization of a smooth network average that is globally quasar-convex with respect to a fixed minimizer; the node functions may be nonconvex and need not share a minimizer. A unit-rate Poisson clock drives an exactly simulable continuized process: between events the state follows a closed-form accelerated flow, and each event uses one oracle vector. One master theorem covers oracles with a predictable bias and a state-dependent variance and keeps the inverse-quadratic term O(LR02/(γ2T2))\mathcal{O}(LR_0^2/(γ^2T^2)); one selected-row lemma supplies the oracle moments of three network implementations. CQA-Net keeps a common state, mixes local rows for finitely many rounds, and disseminates one uniformly selected row; its oracle is unbiased at every mixing depth, so incomplete averaging affects only the variance. A walking token removes dissemination, the shared clock, and the shared root, and an importance weight keeps it unbiased on fixed graphs. D-CQA keeps local states and mixes them; under bounded heterogeneity it needs O~(χLR0/(γθε))\widetilde{\mathcal{O}}(\sqrtχ\sqrt{L}R_0/(γθ\sqrt{\varepsilon})) communication rounds and no dissemination. Changing graphs enter through certified operator norms. Experiments on a certified nonconvex regression on static and changing graphs compare the three implementations.

Introduction

We consider a decentralized optimization problem over a possibly time-varying network:

min⁡x∈RdF(x):=1m∑i=1mfi(x),\min_{x\in\mathbb{R}^d} F(x) := \frac{1}{m}\sum_{i=1}^{m} f_i(x),

where node ii stores its own nonlinear-regression samples and the network objective is the average of the local ones. Such problems model learning from data that cannot be collected in one place and arise in federated learning, in sensor and multi-agent systems, and in large-scale training, where decentralized communication can be cheaper than routing everything through a central server [42, 38, 32].

Even for a realizable monotone-link model, this objective need not be convex: its Hessian can be indefinite. Nevertheless, if the link has slope at least α>0\alpha> 0 and is MM-Lipschitz, the objective satisfies the one-point inequality $\gamma\left[F(x)-F(x^\star)\right] \le ⟨∇F(x),x−x⋆⟩\langle\nabla F(x), x-x^\star\rangle with the globally valid parameter γ=min⁡{1,2α/M}\gamma=\min\{1,2\alpha/M\}; see Proposition 2.4. This quasar-convexity condition holds globally for generalized linear models with monotone links (§ 5) and for star-convex objectives, which are 1-quasar-convex ([19]). Weaker versions restricted to a domain of parameters arise elsewhere, for instance in learning linear dynamical systems ([16]); such cases need a projection or an invariance argument and are not covered by our global theorems. We ask whether the accelerated inverse-quadratic rate survives when the gradient is assembled by only finitely many peer-to-peer communication rounds.

Acceleration for convex decentralized problems is well studied ([17, 26, 27, 31] (Scaman et al. 2017; Xu et al. 2020)), but a convex decentralized proof cannot simply be copied. Quasar-convexity gives a lower model only for the pair (x,x⋆)(x,x^\star), not for two arbitrary query points, and it does not imply monotonicity of the gradient, so a consensus error cannot be inserted into the usual affine estimate-sequence inequalities.

Our approach separates the acceleration mechanism from the network. We first prove a continuized acceleration result for an abstract inexact oracle with a predictable bias and a state-dependent variance (Theorem 4.3): after TT events in expectation, the objective gap is O~(L∥x0−x⋆∥2/(γ2T2))\widetilde{O}(L\lVert x_0-x^\star\rVert^2/(\gamma^2T^2)) plus variance and bias terms. We then show that finitely many gossip rounds followed by the selection of one node’s mixed row implement such an oracle without bias, at every mixing depth: unfinished averaging enters only as variance, which the quasar-convex analysis can absorb. We call this method CQA-Net. It is synchronized, blocking, and common-state, and it relies on three global primitives: exact dissemination of the selected row, a shared event clock, and a shared uniform root. Dissemination is natural in federated learning, but in a peer-to-peer network, and especially on a changing graph, it is a strong requirement. We therefore give two further implementations. A walking token carries the common state along a random walk, so that the clock and the root travel with the token and nothing is disseminated. D-CQA keeps local states and mixes them; only a shared clock seed and synchronous rounds remain, and the dissemination depth disappears from the round count. Table 1 compares the three designs with related methods. We do not address physical asynchrony, fault recovery, partial participation, wall-clock time, or communication optimality.

MethodStateTimingGeometryMechanism and result
CQA-NetCommonBlocking event and broadcastGlobal quasar-convexityUnbiased finite mixing; O~(LR02/(γ2T2))\widetilde{O}(LR_0^2/(\gamma^2T^2)) plus a variance term
TokenOne mobile stateSequential walkGlobal quasar-convexityImportance-weighted walk endpoint; no global primitive
D-CQALocalSynchronous roundsGlobal quasar-convexity, bounded heterogeneityState mixing; O~(χLR0/(γθε))\widetilde{O}(\sqrt{\chi}\sqrt{LR_0}/(\gamma\theta\sqrt{\varepsilon})) rounds
Gradient tracking ([43, 31])LocalSynchronous roundsConvex or strongly convexPrimal and tracker consensus
DADAO ([41])LocalAsynchronous clocksStrongly convexIndependent Poisson communication and computation

Table 1. Comparison with nearby network-optimization models. “Common” means that all nodes hold identical optimization states after each event; “local” allows node disagreement.

§ 5 tests the methods on instances whose constants are certified in closed form: a nonconvex leaky-tanh regression on static and changing graphs, the individual variance mechanisms of CQA-Net, and a comparison of CQA-Net, the token, and D-CQA by communication rounds. It also quantifies how conservative the global certificates can be.

Main contributions.

  1. Theorem 4.3 gives one Lyapunov bound for oracles with a predictable bias and a state-dependent variance. It retains the variance integral and a gradient reserve that absorbs multiplicative noise, and it handles a mean-square bias by a square-root Gronwall argument, without projection or damping.

  1. Lemma 4.6 gives the conditional moments of any selected-row oracle: a mixed matrix of local rows, a root with an arbitrary law, and an optional importance weight. It yields unbiased finite mixing at every depth (Theorem 4.8, fixed and changing graphs) and the walking-token oracle (Corollaries 4.13 and 4.14).

  1. Theorem 4.19 analyzes the local-state variant D-CQA, and Corollary 4.20 bounds its communication by O~(χLR0/(γθε))\widetilde{O}(\sqrt{\chi}\sqrt{LR_0}/(\gamma\theta\sqrt{\varepsilon})) rounds, without a dissemination term.

  1. For shared-landscape finite sums, exact-snapshot restarts give a geometric rate with an accuracy-independent inner depth and batch size (Remark 4.10 and Appendix D).

Related work

Acceleration beyond convexity. Smooth convex acceleration originates with Nesterov [44] (1983). Accelerated methods for weakly quasi-convex and star-convex objectives use auxiliary one- or low-dimensional searches ([14, 29, 28, 19]), which are costly across a network because every trial point may need a global comparison. Continuized acceleration avoids this search: Even et al. [10] introduced exactly simulable Poisson-time acceleration, and Wang and Wibisono (2023) obtained the optimal deterministic dependence on the quasar parameter. Stochastic, robust, non-Euclidean, constrained, zeroth-order, proximal, and distributional developments appear in ([11, 18, 15, 30, 37, 12, 21, 8, 2, 9]); related one-point structures arise, on restricted domains, in learning linear dynamical systems ([16]). Nonconvex stochastic lower bounds (Saad et al., 2025) do not yield a matching lower bound for our model.

Acceleration in networks. Communication-optimal convex decentralized methods combine objective and spectral acceleration ([17, 26] (Scaman et al. 2017; Xu et al. 2020)), with sliding, similarity, and second-order variants ([27, 1, 7] (Takezawa et al. 2025; Tian et al. 2022)). Gradient tracking and primal-dual methods maintain local states ([43, 31, 20] (Qu and Li 2018)), DADAO uses asynchronous edge and gradient clocks ([41]), DCatalyst wraps a decentralized solver in an accelerated outer loop ([4]), and time-varying and finite-sum settings are treated in ([39, 40, 34, 33, 35] (Rogozin et al. 2020)). CQA-Net keeps one common state, so its round count contains the broadcast depth DD in addition to the Chebyshev depth; at γ=1\gamma= 1 it is a non-optimal common-state specialization. D-CQA removes DD and, under bounded heterogeneity, matches the convex local-state round scale up to a logarithm. Random-walk methods process one node per step along a walk ([22, 36]); our token uses this mechanism only to deliver the oracle, and push-sum-type protocols ([24]) are a natural route to message loss, which we do not treat.

Node sampling. At q=0q = 0 CQA-Net is uniform node sampling followed by dissemination, as in client sampling, Local SGD, and SCAFFOLD-type control variates ([23, 13, 25]) and randomized broadcast gossip ([3]). The uniform-row identity is elementary; we use it to supply the exact conditional moments that the quasar-specific Lyapunov theorem needs.

Organization. § 2 sets the geometry and the stochastic model, § 3 defines the algorithms, § 4 contains the analysis, and § 5 the numerical study. Technical proofs and reproducibility details are in the appendices.

Problem statement and notation

We separate the optimization state from the network data used to construct one oracle vector. The continuized dynamics live in Rd\mathbb{R}^{d} and are written with lowercase variables. A node index appears only on local rows and on the transient matrices used by the communication protocol. In CQA-Net every node stores the same optimization vectors at the end of each event; § 3.6 introduces a variant with local states.

The one-vector problem

Let F:Rd→RF:\mathbb{R}^{d} \to\mathbb{R} be differentiable and let x⋆x^{\star} be a fixed global minimizer. Continuous-time states and the oracle lie in Rd\mathbb{R}^{d} and are denoted xt,zt,gtx_t,z_t,g_t; all processes are right-continuous with left limits. For a jump index k≥1k \ge1,

x(k)=xτk,y(k)=xτk−,z(k)=zτk,g(k)=gτk,x^{(k)} = x_{\tau_k}, \qquad y^{(k)} = x_{\tau_k-}, \qquad z^{(k)} = z_{\tau_k}, \qquad g^{(k)} = g_{\tau_k},

so y(k)y^{(k)} is the pre-jump query and x(k)x^{(k)} the post-jump state, and Fτk−\mathcal{F}_{\tau_k-} collects everything revealed strictly before τk\tau_k. We set x(0)=x0x^{(0)} = x_0, z(0)=z0z^{(0)} = z_0, τ0=0\tau_0 = 0, Ek−1=τk−τk−1E_{k-1} = \tau_k - \tau_{k-1}, and R0:=∥x0−x⋆∥R_0 := \lVert x_0 - x^{\star}\rVert.

Definition 2.1 (Smoothness). The objective is LL-smooth if ∥∇F(x)−∇F(y)∥≤L∥x−y∥\lVert\nabla F(x) - \nabla F(y)\rVert\le L\lVert x-y\rVert for all x,y∈Rdx,y \in\mathbb{R}^{d}. Then the descent inequality

F(y)≤F(x)+⟨∇F(x),y−x⟩+L2∥y−x∥2.(1)F(y) \le F(x) + \langle\nabla F(x), y-x \rangle+ \frac{L}{2}\lVert y-x\rVert^{2}. \tag*{(1)}

holds for all x,y∈Rdx,y \in\mathbb{R}^{d}.

Definition 2.2 (Quasar-convexity / weak quasi-convexity). For γ∈(0,1]\gamma\in(0,1], the objective is γ\gamma-quasar-convex with respect to x⋆x^\star if

γ(F(x)−F(x⋆))≤⟨∇F(x),x−x⋆⟩for every x∈Rd.(2)\gamma\left(F(x)-F(x^\star)\right) \le\langle\nabla F(x),x-x^\star\rangle\qquad\text{for every } x \in\mathbb{R}^{d}. \tag*{(2)}

The number γ\gamma is any certified admissible value. Every statement remains valid after replacing it by a smaller positive value.

Definition 2.3 (Quadratic growth). The objective satisfies fixed-minimizer quadratic growth with constant μ>0\mu> 0 if

F(x)−F(x⋆)≥μ2∥x−x⋆∥2for every x∈Rd.(3)F(x)-F(x^\star) \ge\frac{\mu}{2}\lVert x-x^\star\rVert^{2} \qquad\text{for every } x \in\mathbb{R}^{d}. \tag*{(3)}

Condition (3) uses the same distinguished minimizer as quasar-convexity.

Convexity implies Definition 2.2 with γ=1\gamma=1, but the converse is false. The condition supplies a lower model only in the pair (x,x⋆)(x,x^\star): it gives neither an affine lower model at an arbitrary second point nor monotonicity of the gradient. It nevertheless implies that every stationary point is globally optimal. Quadratic growth is invoked only for the dissipative closure of Corollary 4.9(c).

Certified quasar-convex models

A concrete globally nonconvex class is realizable nonlinear regression with a strongly monotone link. Let φ:R→R\varphi:\mathbb{R}\to\mathbb{R} be a differentiable link function; quantitative assumptions on φ′\varphi' are stated in Proposition 2.4. Given features ar∈Rda_r \in\mathbb{R}^{d} and a target x⋆x^\star, the responses are realizable, yr=φ(arTx⋆)y_r=\varphi(a_r^{\mathsf T}x^\star), and the squared-loss objective is

F(x)=12N∑r=1N(φ(arTx)−yr)2.(4)F(x)=\frac{1}{2N}\sum_{r=1}^{N}\left(\varphi(a_r^{\mathsf T}x)-y_r\right)^2. \tag*{(4)}

Proposition 2.4 gives the constants used in the numerical section. Appendix E contains the proof.

Proposition 2.4 (Monotone-link and leaky-tanh certificates). Assume that φ\varphi is differentiable and 0<α≤φ′(u)≤M0<\alpha\le\varphi'(u)\le M for every uu. Then (4) is globally γ\gamma-quasar-convex with γ=min⁡{1,2α/M}\gamma=\min\{1,2\alpha/M\}. If Σ=N−1∑rararT≻0\Sigma=N^{-1}\sum_r a_ra_r^{\mathsf T}\succ0, it satisfies quadratic growth with μ=α2λmin⁡(Σ)\mu=\alpha^2\lambda_{\min}(\Sigma).

For α∈(0,1]\alpha\in(0,1] and φα(u)=αu+(1−α)tanh⁡u\varphi_\alpha(u)=\alpha u+(1-\alpha)\tanh u, let vr=arTx⋆v_r=a_r^{\mathsf T}x^\star and

Bα(v)=1+4α(1−α)e+4α(1−α)33∣v∣+8(1−α)233.B_\alpha(v)=1+\frac{4\alpha(1-\alpha)}{e}+\frac{4\alpha(1-\alpha)}{3\sqrt{3}}\lvert v\rvert+\frac{8(1-\alpha)^2}{3\sqrt{3}}.

Then ∇F\nabla F is globally Lipschitz with any L≥N−1∑rBα(vr)∥ar∥2L\ge N^{-1}\sum_r B_\alpha(v_r)\lVert a_r\rVert^2.

The quasar part sharpens Lemma 3 of Wang and Wibisono (2023), which gives the constant 2α2/M22\alpha^2/M^2 under the same assumptions, by the factor M/αM/\alpha; the quadratic-growth constant matches their quasar-growth bound. The certificate is global and permits negative curvature. In the scalar case N=d=1N=d=1, α=1/2\alpha=1/2, and x⋆=−2x^\star=-2, direct interval evaluation gives −0.253<F′′(1)<−0.250-0.253<F''(1)<-0.250. Realizability is essential: response noise creates a nonzero residual at x⋆x^\star and requires a separate one-point argument.

Certified examples used below. The smooth convex case has γ=1\gamma=1 and serves as a calibration and ridge benchmark. The realizable leaky-tanh regression instance is globally quasar-convex and satisfies quadratic growth despite being nonconvex; its rounded constants are γ=0.36\gamma=0.36, L=2.3631L=2.3631, and μ=1.457⋅10−3\mu=1.457\cdot10^{-3}. It is used for the static- and changing-network experiments. The aligned multiplicative quadratic has a convex network average with γ=μ=L=1\gamma=\mu=L=1 but nonconvex local terms and heterogeneity coefficient h1=1.28h_1=1.28. Full-precision constants are stored in the accompanying metadata.

Network average and local rows

References

  1. [1]Artem Agafonov, Pavel Dvurechensky, Gesualdo Scutari, Alexander Gasnikov, Dmitry Kamzolov, Aleksandr Lukashevich, and Amir Daneshmand. An accelerated second-order method for distributed stochastic optimization. arXiv preprint arXiv:2103.14392, 2021.arxiv.org/abs/2103.14392
  2. [2]Masoud Ahookhosh, José M. M. de Brito, Alireza Kabgani, Felipe Lara, and Jinyun Yuan. Quasar-convex optimization: Fundamental properties and high-order proximal-point methods. arXiv preprint arXiv:2604.26735, 2026.arxiv.org/abs/2604.26735
  3. [3]Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508–2530, 2006.DOI
  4. [4]Tianyu Cao, Xiaokai Chen, and Gesualdo Scutari. DCatalyst: A unified accelerated framework for decentralized optimization. Journal of Machine Learning Research, 27(47):1–57, 2026.arxiv.org/abs/2501.18114
  5. [5]Fang Chen, László Lovász, and Igor Pak. Lifting Markov chains to speed up mixing. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 275–281. ACM, 1999.DOI
  6. [6]Fan R. K. Chung. Diameters and eigenvalues. Journal of the American Mathematical Society, 2(2):187–196, 1989.
  7. [7]Amir Daneshmand, Gesualdo Scutari, Pavel Dvurechensky, and Alexander Gasnikov. Newton method over networks is fast up to the statistical precision. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2398–2409. PMLR, 2021.arxiv.org/abs/2102.06780
  8. [8]José de Brito, Felipe Lara, and Di Liu. Extending linear convergence of the proximal point algorithm: The quasi-convex case. arXiv preprint arXiv:2509.04375, 2025.arxiv.org/abs/2509.04375
  9. [9]Shihong Ding, Long Yang, Luo Luo, and Cong Fang. Optimizing over multiple distributions under generalized quasi-convexity condition. In Advances in Neural Information Processing Systems, volume 37, pages 4718–4764, 2024. doi: 10.52202/079017-0154.DOI
  10. [10]Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gaillard, Laurent Massoulié, and Adrien Taylor. Continued accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. In Advances in Neural Information Processing Systems, volume 34, pages 28054–28066, 2021.
  11. [11]Qiang Fu, Dongchun Xu, and Ashia Camage Wilson. Accelerated stochastic optimization methods under quasi-convexity. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 10431–10460. PMLR, 2023.
  12. [12]Eméric Gbaguidi and Julien Hermant. Accelerated stochastic zeroth-order quasi-convex optimization. arXiv preprint arXiv:2607.19965, 2026.arxiv.org/abs/2607.19965
  13. [13]Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3556–3564. PMLR, 2021.
  14. [14]Sergey Guminov, Alexander Gasnikov, and Ilya Kuruzov. Accelerated methods for weakly-quasi-convex optimization problems. Computational Management Science, 20(1):36, 2023. doi: 10.1007/s10287-023-00468-w. Earlier version: arXiv:1710.00797.DOI
  15. [15]Kanan Gupta, Jonathan W. Siegel, and Stephan Wojtowytsch. Nesterov acceleration despite very noisy gradients. In Advances in Neural Information Processing Systems, volume 37, pages 20694–20744, 2024. doi: 10.52202/079017-0653.DOI
  16. [16]Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19(29):1–44, 2018.
  17. [17]Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 897–906. PMLR, 2019.arxiv.org/abs/1810.02660
  18. [18]Julien Hermant, Jean-François Aujol, Charles Dossal, and Aude Rondopierre. Study of the behaviour of Nesterov accelerated gradient in a non-convex setting: the strongly quasi-convex case. arXiv preprint arXiv:2405.19809, 2024.arxiv.org/abs/2405.19809
  19. [19]Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Proceedings of the 33rd Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1894–1938. PMLR, 2020.arxiv.org/abs/1906.11985
  20. [20]Mingyi Hong, Davood Hajinezhad, and Ming-Min Zhao. Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1529–1538. PMLR, 2017.DOI
  21. [21]Jikai Jin. On the convergence of first order methods for quasi-convex optimization. arXiv preprint arXiv:2010.04937, 2020.arxiv.org/abs/2010.04937
  22. [22]Björn Johansson, Maben Rabi, and Mikael Johansson. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Optimization, 20(3):1157–1170, 2009.
  23. [23]Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Shankar J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5132–5143. PMLR, 2020.arxiv.org/abs/1910.06378
  24. [24]David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 482–491. IEEE, 2003.DOI
  25. [25]Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich. A unified theory of decentralized SGD with changing topology and local updates. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5381–5393. PMLR, 2020.arxiv.org/abs/2003.10422
  26. [26]Dmitry Kovalev, Egor Shulgin, Peter Richtárik, Alexander V. Rogozin, and Alexander Gasnikov. ADOM: Accelerated decentralized optimization method for time-varying networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5784–5793. PMLR, 2021.arxiv.org/abs/2102.09234
  27. [27]Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity. In Advances in Neural Information Processing Systems, volume 35, pages 33494–33507, 2022.
  28. [28]Ilya Kuruzov and Fedor Stonyakin. On some versions of subspace optimization methods with inexact gradient information. arXiv preprint arXiv:2407.01051, 2024.arxiv.org/abs/2407.01051
  29. [29]Ilya A. Kuruzov and Fedor S. Stonyakin. Sequential subspace optimization for quasi\-convex optimization problems with inexact gradient. In Advances in Optimization and Applications. OPTIMA 2021, volume 1514 of Communications in Computer and Information Science, pages 19–33. Springer, Cham, 2021. doi: 10.1007/978-3-030-92711-0_2. Earlier version: arXiv:2108.06297.DOI
  30. [30]Clement Lezane, Sophie Langer, and Wouter M. Koolen. Accelerated mirror descent for non-Euclidean star-convex functions. In Proceedings of the 37th International Conference on Algorithmic Learning Theory, volume 313 of Proceedings of Machine Learning Research, pages 1–41. PMLR, 2026.
  31. [31]Huan Li and Zhоuchen Lin. Accelerated gradient tracking over time-varying graphs for decentralized optimization. Journal of Machine Learning Research, 25(274):1–52, 2024.
  32. [32]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. In Advances in Neural Information Processing Systems 30 (NeurIPS), pages 5330–5340, 2017.
  33. [33]Yuxing Liu, Lesi Chen, and Luo Luo. Decentralized convex finite-sum optimization with better dependence on condition numbers. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 30807–30841. PMLR, 2024.
  34. [34]Aleksandr Lobanov, Andrew Veprikov, Georgiy Konin, Aleksandr Beznosikov, Alexander Gasnikov, and Dmitry Kovalev. Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs. Computational Management Science, 20(1):48, 2023. doi: 10.1007/s10287-023-00479-7.DOI
  35. [35]Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7111–7123. PMLR, 2021.arxiv.org/abs/2006.08085
  36. [36]Xianghui Mao, Kun Yuan, Yubin Hu, Yuანტao Gu, Ali H. Sayed, and Wotao Yin. Walkman: A communication-efficient random-walk algorithm for decentralized optimization. IEEE Transactions on Signal Processing, 68:2513–2528, 2020.arxiv.org/abs/1804.06568
  37. [37]David Martínez-Rubio. Smooth quasar-convex optimization with constraints. arXiv preprint arXiv:2510.01943, 2025. Revised July 2026.
  38. [38]Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1273–1282, 2017.arxiv.org/abs/1602.05629
  39. [39]Dmitry Metelev, Alexander Rogozin, Dmitry Kovalev, and Alexander Gasnikov. Is consensus acceleration possible in decentralized optimization over slowly time-varying networks? In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 24532–24554. PMLR, 2023.
  40. [40]Dmitry Metelev, Savелii 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.arxiv.org/abs/2402.02490
  41. [41]Adel Nabli and Edouard Oyallon. Decentralized asynchronous optimization with DADAO allows decoupling and acceleration. Journal of Machine Learning Research, 26(207):1–48, 2025.
  42. [42]Angelia Nedić and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009.DOI
  43. [43]Angelia Nedić, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597–2633, 2017. doi: 10.1137/16M1084316.DOI
  44. [44]Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Boston, 2004. doi: 10.1007/978-1-4419-8853-9.DOI

Paper details

vlnc:W_t7gtdqrj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents