Inexact proximal stochastic second-order methods for nonconvex composite optimization

ABSTRACT

In this paper, we propose a framework of Inexact Proximal Stochastic Second-order (IPSS) method for solving nonconvex optimization problems, whose objective function consists of an average of finitely many, possibly weakly, smooth functions and a convex but possibly nonsmooth 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 analyse 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 propose 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

Mathematics Subject Classifications 2010:

• 49M37
• 65K05
• 90C30

Acknowledgments

We would like to thank two anonymous referees for their valuable comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 $f\in {\mathcal{C}}^1\left({\mathbb{R}}^d\right)$ means that $f:{\mathbb{R}}^d\to \mathbb{R}$ is continuously differentiable.

Additional information

Funding

This research was partially supported by the National Natural Science Foundation of China [grant numbers 11871453, 11731013], the 2018–2020 Young Elite Scientists Sponsorship Program by China Association for Science and Technology, the USA National Science Foundation [grant numbers 1522654, 1819161] and University Research Facility in Big Data Analytics of the Hong Kong Polytechnic University.

Notes on contributors

Xiao Wang

Xiao Wang is an associate professor at School of Mathematical Sciences at University of Chinese Academy of Sciences, China. Her research focuses on optimization theory, algorithms and applications. Her latest work is published in Optimization Methods and Software, Mathematics of Computation, and SIAM Journal on Optimization.

Hongchao Zhang

Hongchao Zhang is an Associate Professor at the Department of Mathematics at Louisiana State University, USA. His research focuses on nonlinear optimization theory and its applications. His latest work is published at Computational Optimization and Applications, Journal of Scientific Computing and SIAM Journal on Optimization.