Distributed conditional gradient online optimization with recursive variance reduction

This paper investigates the distributed online convex optimization problem in multi-agent networks with stochastic objective functions and a projection-expensive constraint set. In this setting, each agent makes its decision based only on its local stochastic gradients at the previous time while communicating with neighboring agents through the network. To address this problem, we propose a distributed projection-free online variance-reduced conditional gradient algorithm. The proposed algorithm employs recursive variance-reduced estimators for gradient updates to reduce noise in stochastic gradients. Different from existing projection-free algorithms, which either suffer from suboptimal regret bounds or incur high per-iteration computational costs, our proposed algorithm achieves near-optimal regret bounds while maintaining low per-iteration computational complexity. Moreover, leveraging martingale inequalities, we establish the regret bounds with high-probability guarantees, rather than in expectation. Finally, numerical simulations demonstrate the effectiveness and advantages of the proposed algorithm. © 2026 Elsevier Ltd.