Abstract: 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ö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.

Key words:  Nonconvex optimization, Nonsmooth optimization, H ? lder continuity, Prox-
imal quasi-Newton, Variance reduction