Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
This work addresses a gap in algorithm design for non-convex min-max problems in signal processing and communication, offering a method for scenarios where existing convex-concave theories are insufficient, though it appears incremental as it builds on block successive approximation techniques.
The authors tackled the challenge of solving block-wise one-sided non-convex min-max problems, which are common in signal processing and communication but lack theoretical guidance due to non-convexity, by proposing the Hybrid Block Successive Approximation (HiBSA) algorithm that converges to first-order stationary solutions with quantifiable global rates, as validated through numerical tests on problems like robust learning and wireless jamming.
The min-max problem, also known as the saddle point problem, is a class of optimization problems which minimizes and maximizes two subsets of variables simultaneously. This class of problems can be used to formulate a wide range of signal processing and communication (SPCOM) problems. Despite its popularity, most existing theory for this class has been mainly developed for problems with certain special convex-concave structure. Therefore, it cannot be used to guide the algorithm design for many interesting problems in SPCOM, where various kinds of non-convexity arise. In this work, we consider a 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 a class of simple algorithms named Hybrid Block Successive Approximation (HiBSA), which alternatingly perform gradient descent-type steps for the minimization blocks and gradient ascent-type steps for the maximization problem. A key element in the proposed algorithm is the use of certain regularization and penalty sequences, which stabilize the algorithm and ensure convergence. We show that HiBSA converges to some properly defined first-order stationary solutions with quantifiable global rates. To validate the efficiency of the proposed algorithms, we conduct numerical tests on a number of problems, including the robust learning problem, the non-convex min-utility maximization problems, and certain wireless jamming problem arising in interfering channels.