TY - GEN
T1 - Block Alternating Optimization for Non-convex Min-max Problems
T2 - 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019
AU - Lu, Songtao
AU - Tsaknakis, Ioannis
AU - Hong, Mingyi
PY - 2019/5
Y1 - 2019/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85069543302&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069543302&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2019.8683795
DO - 10.1109/ICASSP.2019.8683795
M3 - Conference contribution
AN - SCOPUS:85069543302
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 4754
EP - 4758
BT - 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 12 May 2019 through 17 May 2019
ER -