A Parallel Stochastic Approximation Method for Nonconvex Multi-Agent Optimization Problems

Abstract

Consider the problem of minimizing the expected value of a (possibly nonconvex) cost function parameterized by a random (vector) variable, when the expectation cannot be computed accurately (e.g., because the statistics of the random variables are unknown and/or the computational complexity is prohibitive). Classical sample stochastic gradient methods for solving this problem may empirically suffer from slow convergence. In this paper, we propose for the first time a stochastic parallel Successive Convex Approximation-based (best-response) algorithmic framework for general nonconvex stochastic sum-utility optimization problems, which arise naturally in the design of multi-agent systems. The proposed novel decomposition enables all users to update their optimization variables in parallel by solving a sequence of strongly convex subproblems, one for each user. Almost surely convergence to stationary points is proved. We then customize our algorithmic framework to solve the stochastic sum rate maximization problem over Single-Input-Single-Output (SISO) frequency-selective interference channels, multiple-input-multiple-output (MIMO) interference channels, and MIMO multiple-access channels. Numerical results show that our algorithms are much faster than state-of-the-art stochastic gradient schemes while achieving the same (or better) sum-rates.

Part of this work has been presented at IEEE SPAWC 2013

References in corpus (2)

• Parallel Selective Algorithms for Big Data Optimization
• Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization

Cited by in corpus (30)

• Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization
• Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems
• A Unified Successive Pseudo-Convex Approximation Framework
• Two-timescale Beamforming Optimization for Intelligent Reflecting Surface Aided Multiuser Communication with QoS Constraints
• Two-Timescale Hybrid Compression and Forward for Massive MIMO Aided C-RAN
• Large Intelligent Surface Aided Physical Layer Security Transmission
• Stochastic Successive Convex Optimization for Two-timescale Hybrid Precoding in Massive MIMO
• Parallelized Structures for MIMO FBMC under Strong Channel Frequency Selectivity
• Distributed Training of Graph Convolutional Networks
• Unraveling the Rank-One Solution Mystery of Robust MISO Downlink Transmit Optimization: A Verifiable Sufficient Condition via a New Duality Result
• Energy efficiency optimization in MIMO interference channels: A successive pseudoconvex approximation approach
• Successive Convex Approximation Based Off-Policy Optimization for Constrained Reinforcement Learning
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling
• An Online Parallel and Distributed Algorithm for Recursive Estimation of Sparse Signals
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
• Sample-based and Feature-based Federated Learning for Unconstrained and Constrained Nonconvex Optimization via Mini-batch SSCA
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning
• Spectrum Sharing Among Multiple-Seller and Multiple-Buyer Operators of A Mobile Network: A Stochastic Geometry Approach
• Model-Free Optimization for Reconfigurable Intelligent Surface with Statistical CSI
• Intelligent Reflecting Surfaces and Next Generation Wireless Systems
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
• Distributed Stochastic Nonconvex Optimization and Learning based on Successive Convex Approximation
• Content-Aware User Association and Multi-User MIMO Beamforming over Mobile Edge Caching
• Robust Federated Learning with Noisy Communication
• Sample-based Federated Learning via Mini-batch SSCA
• Stochastic Successive Convex Approximation for General Stochastic Optimization Problems
• Practical Precoding via Asynchronous Stochastic Successive Convex Approximation
• Low-complexity Robust Optimization for an IRS-assisted Multi-Cell Network
• Stochastic Transceiver Optimization in Multi-Tags Symbiotic Radio Systems
• Power Control for Massive MIMO Systems with Nonorthogonal Pilots