First-order Methods with Convergence Rates for Multi-agent Systems on Semidefinite Matrix Spaces

Abstract

The goal in this paper is to develop first-order methods equipped with convergence rates for multi-agent optimization problems on semidefinite matrix spaces. These problems include cooperative optimization problems and non-cooperative Nash games. Accordingly, first we consider a multi-agent system where the agents cooperatively minimize the summation of their local convex objectives, and second, we consider Cartesian stochastic variational inequality (CSVI) problems with monotone mappings for addressing stochastic Nash games on semidefinite matrix spaces. Despite the recent advancements in first-order methods addressing problems over vector spaces, there seems to be a major gap in the theory of the first-order methods for optimization problems and equilibriums on semidefinite matrix spaces. In particular, to the best of our knowledge, there exists no method with provable convergence rate for solving the two classes of problems under mild assumptions. Most existing methods either rely on strong assumptions, or require a two-loop framework where at each iteration a semidefinite optimization problem needs to be solved. Motivated by this gap, in the first part of the paper, we develop a mirror descent incremental subgradient method for minimizing a finite-sum function. We show that the iterates generated by the algorithm converge asymptotically to an optimal solution and derive a non-asymptotic convergence rate. In the second part, we consider semidefinite CSVI problems. We develop a stochastic mirror descent method that only requires monotonicity of the mapping. We show that the iterates generated by the algorithm converge to a solution of the CSVI almost surely. Using a suitably defined gap function, we derive a convergence rate statement. This work appears to be the first that provides a convergence speed guarantee for monotone CSVIs on semidefinite matrix spaces.

arXiv commentarXiv admin note: text overlap with arXiv:1809.09155

References in corpus (8)

• The Role of Relative Entropy in Quantum Information Theory
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• The MIMO Iterative Waterfilling Algorithm
• Distributed stochastic optimization via matrix exponential learning
• Parallelized Structures for MIMO FBMC under Strong Channel Frequency Selectivity
• Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
• Distributed Learning for Cooperative Inference
• Distributed Mirror Descent over Directed Graphs