On the Convergence of SARAH and Beyond

  • 2020-01-16 17:54:07
  • Bingcong Li, Meng Ma, Georgios B. Giannakis
  • 0

Abstract

The main theme of this work is a unifying algorithm,\textbf{L}oop\textbf{L}ess \textbf{S}ARAH (L2S) for problems formulated assummation of $n$ individual loss functions. L2S broadens a recently developedvariance reduction method known as SARAH. To find an $\epsilon$-accuratesolution, L2S enjoys a complexity of ${\cal O}\big( (n+\kappa) \ln(1/\epsilon)\big)$ for strongly convex problems. For convex problems, whenadopting an $n$-dependent step size, the complexity of L2S is ${\cal O}(n+\sqrt{n}/\epsilon)$; while for more frequently adopted $n$-independent stepsize, the complexity is ${\cal O}(n+ n/\epsilon)$. Distinct from SARAH, ourtheoretical findings support an $n$-independent step size in convex problemswithout extra assumptions. For nonconvex problems, the complexity of L2S is${\cal O}(n+ \sqrt{n}/\epsilon)$. Our numerical tests on neural networkssuggest that L2S can have better generalization properties than SARAH. Alongwith L2S, our side results include the linear convergence of the last iterationfor SARAH in strongly convex problems.

 

Quick Read (beta)

loading the full paper ...