A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints
share
Nonsmooth composite optimization with orthogonality constraints has a broad spectrum of applications in statistical learning and data science. However, this problem is generally challenging to solve due to its non-convex and non-smooth nature. Existing solutions are limited by one or more of the following restrictions: (i) they are full gradient methods that require high computational costs in each iteration; (ii) they are not capable of solving general nonsmooth composite problems; (iii) they are infeasible methods and can only achieve the feasibility of the solution at the limit point; (iv) they lack rigorous convergence guarantees; (v) they only obtain weak optimality of critical points. In this paper, we propose OBCD, a new Block Coordinate Descent method for solving general nonsmooth composite problems under Orthogonality constraints. OBCD is a feasible method with low computation complexity footprints. In each iteration, our algorithm updates k rows of the solution matrix (k≥2 is a parameter) to preserve the constraints. Then, it solves a small-sized nonsmooth composite optimization problem under orthogonality constraints either exactly or approximately. We demonstrate that any exact block-k stationary point is always an approximate block-k stationary point, which is equivalent to the critical stationary point. We are particularly interested in the case where k=2 as the resulting subproblem reduces to a one-dimensional nonconvex problem. We propose a breakpoint searching method and a fifth-order iterative method to solve this problem efficiently and effectively. We also propose two novel greedy strategies to find a good working set to further accelerate the convergence of OBCD. Finally, we have conducted extensive experiments on several tasks to demonstrate the superiority of our approach.
READ FULL TEXT