A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming

Zhaosong Lu, Lin Xiao

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish
Pages (from-to)2930-2955
Number of pages26
JournalSIAM Journal on Numerical Analysis
Volume55
Issue number6
DOIs
StatePublished - 2017
Externally publishedYes

Keywords

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

Fingerprint

Dive into the research topics of 'A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming'. Together they form a unique fingerprint.

Cite this