A Parallel Best-Response Algorithm with Exact Line Search for Nonconvex Sparsity-Regularized Rank Minimization
This addresses optimization challenges in machine learning for sparse and low-rank matrix problems, offering a more efficient and reliable method, though it appears incremental as it builds on existing best-response and line search techniques.
The paper tackles the nonconvex sparsity-regularized rank minimization problem by proposing a parallel best-response algorithm with exact line search, achieving faster convergence than subgradient and block coordinate descent methods while guaranteeing convergence to a stationary point, unlike ADMM which only works for convex problems.
In this paper, we propose a convergent parallel best-response algorithm with the exact line search for the nondifferentiable nonconvex sparsity-regularized rank minimization problem. On the one hand, it exhibits a faster convergence than subgradient algorithms and block coordinate descent algorithms. On the other hand, its convergence to a stationary point is guaranteed, while ADMM algorithms only converge for convex problems. Furthermore, the exact line search procedure in the proposed algorithm is performed efficiently in closed-form to avoid the meticulous choice of stepsizes, which is however a common bottleneck in subgradient algorithms and successive convex approximation algorithms. Finally, the proposed algorithm is numerically tested.