Optimization Online


Inexact proximal stochastic second-order methods for nonconvex composite optimization

Xiao Wang (wangxiao***at***ucas.ac.cn)
Hongchao Zhang (hozhang***at***math.lsu.edu)

Abstract: In this paper, we propose a framework of Inexact Proximal Stochastic Second-order (IPSS) methods for solving nonconvex optimization problems, whose objective function consists of an average of finitely many, possibly weakly, smooth functions and a convex but possibly nons- mooth function. At each iteration, IPSS inexactly solves a proximal subproblem constructed by using some positive definite matrix which could capture the second-order information of original problem. Proper tolerances are given for the subproblem solution in order to maintain global convergence and the desired overall complexity of the algorithm. Under mild conditions, we analyze the computational complexity related to the evaluations on the component gradient of the smooth function. We also investigate the number of evaluations of subgradient when using an iterative subgradient method to solve the subproblem. In addition, based on IPSS, we pro- pose a linearly convergent algorithm under the proximal Polyak-Łojasiewicz condition. Finally, we extend the analysis to problems with weakly smooth function and obtain the computational complexity accordingly.

Keywords: Stochastic gradient, second-order approximation, proximal Polyak-Łojasiewicz (PL) inequality, inexact subproblem solution, (weakly) smooth function, variance reduction, complexity, nonconvex

Category 1: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 10/10/2019
Entry Accepted: 10/11/2019
Entry Last Modified: 10/14/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society