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 𝒪(LR02/(γ2T2)); 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 𝒪̃(√χ√LR0/(γθ√ε)) 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.
Related
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Weakly Quasar-Convex Optimization
- Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization
- The exact worst-case asymptotic rate of Nesterov acceleration for strongly convex optimization
- Unbiased Treatment Effect Estimation under Network Interference via Neighborhood-Excluded Cross-Fitting
BibTeX
@misc{kuruzov2026continuized,
title = {{Continuized Quasar-Convex Acceleration via an Unbiased Finite-Mixing Network Oracle}},
author = {Ilya Kuruzov and Artem Agafonov and Vadim Abronin and Darina Dvinskikh and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04597},
eprint = {2611.04597},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04597},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Continuized Quasar-Convex Acceleration via an Unbiased Finite-Mixing Network Oracle
AU - Ilya Kuruzov
AU - Artem Agafonov
AU - Vadim Abronin
AU - Darina Dvinskikh
AU - Alexander Gasnikov
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04597
UR - https://arxiv.org/abs/2611.04597
AB - 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 𝒪(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 𝒪̃(√χ√LR_0/(γθ√ε)) 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.
ER -