A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming

Abstract

We propose a randomized nonmonotone block proximal gradient (RNBPG) method for minimizing the sum of a smooth (possibly nonconvex) function and a block-separable (possibly nonconvex nonsmooth) function. At each iteration, this method randomly picks a block according to any prescribed probability distribution and solves typically several associated proximal subproblems that usually have a closed-form solution, until a certain progress on objective value is achieved. In contrast to the usual randomized block coordinate descent method [23,20], our method has a nonmonotone flavor and uses variable stepsizes that can partially utilize the local curvature information of the smooth component of objective function. We show that any accumulation point of the solution sequence of the method is a stationary point of the problem {\it almost surely} and the method is capable of finding an approximate stationary point with high probability. We also establish a sublinear rate of convergence for the method in terms of the minimal expected squared norm of certain proximal gradients over the iterations. When the problem under consideration is convex, we show that the expected objective values generated by RNBPG converge to the optimal value of the problem. Under some assumptions, we further establish a sublinear and linear rate of convergence on the expected objective values generated by a monotone version of RNBPG. Finally, we conduct some preliminary experiments to test the performance of RNBPG on the ${\ell }_1$-regularized least-squares problem and a dual SVM problem in machine learning. The computational results demonstrate that our method substantially outperforms the randomized block coordinate {\it descent} method with fixed or variable stepsizes.

The previous title was "Randomized Block Coordinate Non-Monotone Gradient Method for a Class of Nonlinear Programming"

References in corpus (7)

• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Proximal Stochastic Dual Coordinate Ascent
• Iteration Complexity Analysis of Block Coordinate Descent Methods
• Inexact Coordinate Descent: Complexity and Preconditioning
• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (9)

• Parallel Selective Algorithms for Big Data Optimization
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• A globally convergent algorithm for nonconvex optimization based on block coordinate update
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• On Synchronous, Asynchronous, and Randomized Best-Response schemes for computing equilibria in Stochastic Nash games
• Block stochastic gradient iteration for convex and nonconvex optimization
• Separable Approximations and Decomposition Methods for the Augmented Lagrangian
• Randomized block proximal damped Newton method for composite self-concordant minimization
• A generic coordinate descent solver for nonsmooth convex optimization