A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update

By Yangyang Xu, Wotao Yin. Journal of Scientific Computing, 2014

328 citations recorded by the source corpus.

Nonconvex optimization arises in many areas of computational science and engineering. However, most nonconvex optimization algorithms are only known to have local convergence or subsequence convergence properties. In this paper, we propose an algorithm for nonconvex optimization and establish its global convergence (of the whole sequence) to a critical point. In addition, we give its asymptotic convergence rate and numerically demonstrate its efficiency. In our algorithm, the variables of the underlying problem are either treated as one block or multiple disjoint blocks. It is assumed that each non-differentiable component of the objective function, or each constraint, applies only to one block of variables. The differentiable components of the objective function, however, can involve multiple blocks of variables together. Our algorithm updates one block of variables at a time by minimizing a certain prox-linear surrogate, along with an extrapolation to accelerate its convergence. The order of update can be either deterministically cyclic or randomly shuffled for each cycle. In fact, our convergence analysis only needs that each block be updated at least once in every fixed number of iterations. We show its global convergence (of the whole sequence) to a critical point under fairly loose conditions including, in particular, the Kurdyka–Łojasiewicz condition, which is satisfied by a broad class of nonconvex/nonsmooth applications. These results, of course, remain valid when the underlying problem is convex. We apply our convergence results to the coordinate descent iteration for non-convex regularized linear regression, as well as a modified rank-one residue iteration for nonnegative matrix factorization. We show that both applications have global convergence. Numerically, we tested our algorithm on nonnegative matrix and tensor factorization problems, where random shuffling clearly improves the chance to avoid low-quality local solutions.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/3acf43e2d9c284c2aa94506f00ec788b1f03c120

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates (2015, methodology): “Furthermore, in [54,55], the algorithms with random coordinate selection keep clear of low-quality local solutions in nonconvex optimization, which are difficult to avoid by fixed-order coordinate selection.”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “If f is differentiable, multi-convex or has separable non-smooth parts, then every limit point of the sequence generated by the proximal BCD is a critical point [21,59,69,70], but again, the nonsmooth terms cannot couple more than one block of variable.”
On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays (2016, background): “This modification can guarantee the whole sequence convergence of the coordinate descent method [36].”