Inexact Block Coordinate Descent Algorithms for Nonsmooth Nonconvex Optimization

Abstract

In this paper, we propose an inexact block coordinate descent algorithm for large-scale nonsmooth nonconvex optimization problems. At each iteration, a particular block variable is selected and updated by inexactly solving the original optimization problem with respect to that block variable. More precisely, a local approximation of the original optimization problem is solved. The proposed algorithm has several attractive features, namely, i) high flexibility, as the approximation function only needs to be strictly convex and it does not have to be a global upper bound of the original function; ii) fast convergence, as the approximation function can be designed to exploit the problem structure at hand and the stepsize is calculated by the line search; iii) low complexity, as the approximation subproblems are much easier to solve and the line search scheme is carried out over a properly constructed differentiable function; iv) guaranteed convergence of a subsequence to a stationary point, even when the objective function does not have a Lipschitz continuous gradient. Interestingly, when the approximation subproblem is solved by a descent algorithm, convergence of a subsequence to a stationary point is still guaranteed even if the approximation subproblem is solved inexactly by terminating the descent algorithm after a finite number of iterations. These features make the proposed algorithm suitable for large-scale problems where the dimension exceeds the memory and/or the processing capability of the existing hardware. These features are also illustrated by several applications in signal processing and machine learning, for instance, network anomaly detection and phase retrieval.

References in corpus (10)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
• Parallel Selective Algorithms for Big Data Optimization
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• A Unified Successive Pseudo-Convex Approximation Framework
• In-network Sparsity-regularized Rank Minimization: Algorithms and Applications
• Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
• Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
• Successive Convex Approximation Algorithms for Sparse Signal Estimation with Nonconvex Regularizations

Cited by in corpus (10)

• Outage and Finite-SNR DMT Analysis for IRS-aided MIMO Systems: How Large IRSs Need to Be?
• Efficient Learning of Decision-Making Models: A Penalty Block Coordinate Descent Algorithm for Data-Driven Inverse Optimization
• Extended Successive Convex Approximation for Phase Retrieval with Dictionary Learning
• A tensor model for the calibration of air-coupled ultrasonic sensor arrays in 3D imaging
• Alternating Minimization for Wideband Multiuser IRS-aided MIMO Systems under Imperfect CSI
• The Convergence Properties of Infeasible Inexact Proximal Alternating Linearized Minimization
• Adaptive Anomaly Detection in Network Flows with Low-Rank Tensor Decompositions and Deep Unrolling
• Data-Driven Logistic Regression Ensembles With Applications in Genomics
• Transforming physics-informed machine learning to convex optimization
• A Low-Complexity Algorithmic Framework for Large-Scale IRS-Assisted Wireless Systems