一类非凸优化问题的邻近拟牛顿方法的复杂性

Complexity on Proximal Quasi-Newton Methods for a Class of Nonconvex Composite Optimization

This paper studies a class of nonconvex composite optimization, whose objective is a summation of an average of nonconvex(weakly) smooth functions and a convex nonsmooth function, where the gradient of the former function has the H o¨lder continuity. By exploring the structure of such kind of problems, we first propose a proximal(quasi-)Newton algorithm wPQN(Proximal quasi-Newton algorithm for weakly smooth optimization) and investigate its theoretical complexities to find an approximate solution. Then we propose a stochastic variant algorithm wPSQN(Proximal stochastic quasi-Newton algorithm for weakly smooth optimization), which allows a random subset of component functions to be used at each iteration. Moreover, motivated by recent success of variance reduction techniques, we propose two variance reduced algorithms,wPSQN-SVRG and wPSQN-SARAH, and investigate their computational complexity separately.