TY - JOUR

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

AU - Lu, Zhaosong

AU - Xiao, Lin

N1 - Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Block coordinate gradient method

KW - Nonconvex composite optimization

KW - Nonmonotone line search

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85039949923&partnerID=8YFLogxK

U2 - 10.1137/16M1110182

DO - 10.1137/16M1110182

M3 - Article

AN - SCOPUS:85039949923

SN - 0036-1429

VL - 55

SP - 2930

EP - 2955

JO - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

IS - 6

ER -