Two distributed online stochastic mirror descent algorithms achieve dynamic saddle point regret O(max{T^{θ1}, T^{θ2}(1+V_T)}) under Bregman divergence, generalizing earlier Euclidean results to stochastic, non-Euclidean settings.
Decentralized Distributed Optimization for Saddle Point Problems
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider distributed convex-concave saddle point problems over arbitrary connected undirected networks and propose a decentralized distributed algorithm for their solution. The local functions distributed across the nodes are assumed to have global and local groups of variables. For the proposed algorithm we prove non-asymptotic convergence rate estimates with explicit dependence on the network characteristics. To supplement the convergence rate analysis, we propose lower bounds for strongly-convex-strongly-concave and convex-concave saddle-point problems over arbitrary connected undirected networks. We illustrate the considered problem setting by a particular application to distributed calculation of non-regularized Wasserstein barycenters.
fields
math.OC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Distributed Online Stochastic Convex-Concave Optimization: Dynamic Regret Analyses under Single and Multiple Consensus Steps
Two distributed online stochastic mirror descent algorithms achieve dynamic saddle point regret O(max{T^{θ1}, T^{θ2}(1+V_T)}) under Bregman divergence, generalizing earlier Euclidean results to stochastic, non-Euclidean settings.