  We introduce two new stochastic conjugate frameworks for a class of nonconvex
and possibly also nonsmooth optimization problems. These frameworks are built
upon Stochastic Recursive Gradient Algorithm (SARAH) and we thus refer to them
as Acc-Prox-CG-SARAH and Acc-Prox-CG-SARAH-RS, respectively. They are
efficiently accelerated, easy to implement, tune free and can be smoothly
extended and modified. We devise a deterministic restart scheme for stochastic
optimization and apply it in our second stochastic conjugate framework, which
serves the key difference between the two approaches. In addition, we apply the
ProbAbilistic Gradient Estimator (PAGE) and further develop a practical
variant, denoted as Acc-Prox-CG-SARAH-ST, in order to reduce potential
computational overhead. We provide comprehensive and rigorous convergence
analysis for all three approaches and establish linear convergence rates for
unconstrained minimization problem with nonconvex and nonsmooth objective
functions. Experiments have demonstrated that Acc-Prox-CG-SARAH and
Acc-Prox-CG-SARAH-RS both outperform state-of-art methods consistently and
Acc-Prox-CG-SARAH-ST can as well achieve comparable convergence speed. In terms
of theory and experiments, we verify the strong computational efficiency of the
deterministic restart scheme in stochastic optimization methods.
