Stochastic mirror descent for convex optimization with consensus constraints
File(s)
Accepted version
Author(s)
Borovykh, Anastasia
Kantas, Nikolas
Parpas, Panayiotis
Pavliotis, Greg
Type
Journal Article
Abstract
The mirror descent algorithm is known to be effective in situations where it is beneficial to adapt
the mirror map to the underlying geometry of the optimization model. However, the effect of mirror
maps on the geometry of distributed optimization problems has not been previously addressed. In
this paper we study an exact distributed mirror descent algorithm in continuous-time under additive
noise. We establish a linear convergence rate of the proposed dynamics for the setting of convex
optimization. Our analysis draws motivation from the Augmented Lagrangian and its relation to
gradient tracking. To further explore the benefits of mirror maps in a distributed setting we present
a preconditioned variant of our algorithm with an additional mirror map over the Lagrangian dual
variables. This allows our method to adapt to both the geometry of the primal variables, as well
as to the geometry of the consensus constraint. We also propose a Gauss-Seidel type discretization
scheme for the proposed method and establish its linear convergence rate. For certain classes of
problems we identify mirror maps that mitigate the effect of the graph’s spectral properties on the
convergence rate of the algorithm. Using numerical experiments we demonstrate the efficiency of
the methodology on convex models, both with and without constraints. Our findings show that the
proposed method outperforms other methods, especially in scenarios where the model’s geometry is
not captured by the standard Euclidean norm.
the mirror map to the underlying geometry of the optimization model. However, the effect of mirror
maps on the geometry of distributed optimization problems has not been previously addressed. In
this paper we study an exact distributed mirror descent algorithm in continuous-time under additive
noise. We establish a linear convergence rate of the proposed dynamics for the setting of convex
optimization. Our analysis draws motivation from the Augmented Lagrangian and its relation to
gradient tracking. To further explore the benefits of mirror maps in a distributed setting we present
a preconditioned variant of our algorithm with an additional mirror map over the Lagrangian dual
variables. This allows our method to adapt to both the geometry of the primal variables, as well
as to the geometry of the consensus constraint. We also propose a Gauss-Seidel type discretization
scheme for the proposed method and establish its linear convergence rate. For certain classes of
problems we identify mirror maps that mitigate the effect of the graph’s spectral properties on the
convergence rate of the algorithm. Using numerical experiments we demonstrate the efficiency of
the methodology on convex models, both with and without constraints. Our findings show that the
proposed method outperforms other methods, especially in scenarios where the model’s geometry is
not captured by the standard Euclidean norm.
Date Issued
2024-09
Date Acceptance
2024-05-20
Citation
SIAM Journal on Applied Dynamical Systems, 2024, 23 (3), pp.2208-2241
ISSN
1536-0040
Publisher
Society for Industrial and Applied Mathematics
Start Page
2208
End Page
2241
Journal / Book Title
SIAM Journal on Applied Dynamical Systems
Volume
23
Issue
3
Copyright Statement
© 2024 Society for Industrial and Applied Mathematics.
This is the author’s accepted manuscript made available under a CC-BY licence in accordance with Imperial’s Research Publications Open Access policy (www.imperial.ac.uk/oa-policy)
This is the author’s accepted manuscript made available under a CC-BY licence in accordance with Imperial’s Research Publications Open Access policy (www.imperial.ac.uk/oa-policy)
License URL
Identifier
https://epubs.siam.org/doi/full/10.1137/22M1515197
Publication Status
Published
Date Publish Online
2024-08-05