Distributed stochastic optimization via matrix exponential learning

Abstract

In this paper, we investigate a distributed learning scheme for a broad class of stochastic optimization problems and games that arise in signal processing and wireless communications. The proposed algorithm relies on the method of matrix exponential learning (MXL) and only requires locally computable gradient observations that are possibly imperfect and/or obsolete. To analyze it, we introduce the notion of a stable Nash equilibrium and we show that the algorithm is globally convergent to such equilibria - or locally convergent when an equilibrium is only locally stable. We also derive an explicit linear bound for the algorithm's convergence speed, which remains valid under measurement errors and uncertainty of arbitrarily high variance. To validate our theoretical analysis, we test the algorithm in realistic multi-carrier/multiple-antenna wireless scenarios where several users seek to maximize their energy efficiency. Our results show that learning allows users to attain a net increase between 100% and 500% in energy efficiency, even under very high uncertainty.

arXiv comment31 pages, 3 figures

References in corpus (7)

• The Role of Relative Entropy in Quantum Information Theory
• A Survey on Metric Learning for Feature Vectors and Structured Data
• Energy-Efficient Power Control: A Look at 5G Wireless Technologies
• Regularization Techniques for Learning with Matrices
• No-regret Dynamics and Fictitious Play
• Parallelized Structures for MIMO FBMC under Strong Channel Frequency Selectivity
• Adaptive Power Allocation and Control in Time-Varying Multi-Carrier MIMO Networks

Cited by in corpus (12)

• Online convex optimization and no-regret learning: Algorithms, guarantees and applications
• Robust Distributed Optimization With Randomly Corrupted Gradients
• Matrix Exponential Learning Schemes with Low Informational Exchange
• Multi-agent online learning in time-varying games
• Hessian barrier algorithms for linearly constrained optimization problems
• Fast Optimization with Zeroth-Order Feedback in Distributed, Multi-User MIMO Systems
• Gradient-free Online Learning in Games with Delayed Rewards
• On the convergence of mirror descent beyond stochastic convex programming
• Randomized Gradient-Free Distributed Online Optimization via a Dynamic Regret Analysis
• Zeroth-order optimisation on subsets of symmetric matrices with application to MPC tuning
• First-order Methods with Convergence Rates for Multi-agent Systems on Semidefinite Matrix Spaces
• Distributed Stochastic Optimization in Networks with Low Informational Exchange