  Various types of parameter restart schemes have been proposed for accelerated
gradient algorithms to facilitate their practical convergence in convex
optimization. However, the convergence properties of accelerated gradient
algorithms under parameter restart remain obscure in nonconvex optimization. In
this paper, we propose a novel accelerated proximal gradient algorithm with
parameter restart (named APG-restart) for solving nonconvex and nonsmooth
problems. Our APG-restart is designed to 1) allow for adopting flexible
parameter restart schemes that cover many existing ones; 2) have a global
sub-linear convergence rate in nonconvex and nonsmooth optimization; and 3)
have guaranteed convergence to a critical point and have various types of
asymptotic convergence rates depending on the parameterization of local
geometry in nonconvex and nonsmooth optimization. Numerical experiments
demonstrate the effectiveness of our proposed algorithm.
