Block Alternating Optimization for Non-convex Min-max Problems: Algorithms and Applications in Signal Processing and Communications
Lists
Only you see this
Abstract
The min-max problem, also known as the saddle point problem, can be used to formulate a wide range of applications in signal processing and wireless communications. However, existing optimization theory and methods, which mostly deal with problems with certain convex-concave structure, are not applicable for the aforementioned applications, which oftentimes involve non-convexity. In this work, we consider a general block-wise one-sided non-convex min-max problem, in which the minimization problem consists of multiple blocks and is non-convex, while the maximization problem is (strongly) concave. We propose two simple algorithms, which alternatingly perform one gradient descent-type step for each minimization block and one gradient ascent-type step for the maximization problem. For the first time, we show that such simple alternating min-max algorithms converge to first-order stationary solutions. We conduct numerical tests on a robust learning problem, and a wireless communication problem in the presence of jammers, to validate the efficiency of the proposed algorithms.
BibTeX
@inproceedings{lu2019block,
author = {Songtao Lu and Ioannis C. Tsaknakis and Mingyi Hong},
title = {{Block Alternating Optimization for Non-convex Min-max Problems: Algorithms and Applications in Signal Processing and Communications}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2019},
url = {https://openreview.net/forum?id=O6dQi8ovWcLh},
}Loading related content...