Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications

Abstract

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.

References in corpus (17)

• A Survey on Multi-Task Learning
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Parallel Selective Algorithms for Big Data Optimization
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Joint Downlink Base Station Association and Power Control for Max-Min Fairness: Computation and Complexity
• Proximity Without Consensus in Online Multi-Agent Optimization
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Multicell Coordinated Beamforming with Rate Outage Constraint--Part II: Efficient Approximation Algorithms
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Efficient Algorithms for Smooth Minimax Optimization
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• Multicell Coordinated Beamforming with Rate Outage Constraint--Part I: Complexity Analysis
• An Inexact Primal-Dual Smoothing Framework for Large-Scale Non-Bilinear Saddle Point Problems

Cited by in corpus (34)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Game-Theoretic Multiagent Reinforcement Learning
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
• A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems
• Near-Optimal Algorithms for Minimax Optimization
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Stochastic AUC Maximization with Deep Neural Networks
• On Lower Iteration Complexity Bounds for the Saddle Point Problems
• Efficient Algorithms for Smooth Minimax Optimization
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Improved Algorithms for Convex-Concave Minimax Optimization
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Low-rank Matrix Recovery With Unknown Correspondence
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• Minimax Optimization with Smooth Algorithmic Adversaries
• Randomized Stochastic Gradient Descent Ascent
• FedMM: Saddle Point Optimization for Federated Adversarial Domain Adaptation
• Adaptive Offline and Online Similarity-Based Caching