## 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 [P. Richtarik and M. Takac, Math. Program., 144 (2014), pp. 1-38; A. Patrascu and I. Necoara, J. Global Optim., 61 (2015), pp. 19-46], our method has a nonmonotone avor 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 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 1-regularized least-squares problem, a dual support vector machine problem in machine learning, the 0-regularized least-squares problem, and a regularized matrix completion model. The computational results demonstrate that our method substantially outperforms the randomized block coordinate descent method with fixed or variable stepsizes.

Original language | English (US) |
---|---|

Pages (from-to) | 2930-2955 |

Number of pages | 26 |

Journal | SIAM Journal on Numerical Analysis |

Volume | 55 |

Issue number | 6 |

DOIs | |

State | Published - 2017 |

Externally published | Yes |

### Bibliographical note

Funding Information:∗Received by the editors January 3, 2017; accepted for publication April 28, 2017; published electronically November 28, 2017. http://www.siam.org/journals/sinum/55-6/M111018.html Funding: The work of the first author was supported in part by an NSERC Discovery Grant. †Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada (zhaosong@sfu.ca). ‡Machine Learning Groups, Microsoft Research, One Microsoft Way, Redmond, WA 98052 (lin.xiao@microsoft.com).

Publisher Copyright:

© 2017 Society for Industrial and Applied Mathematics.

## Keywords

- Block coordinate gradient method
- Nonconvex composite optimization
- Nonmonotone line search
- Randomized algorithms