We analyze a fast incremental aggregated gradient method for optimizing
nonconvex problems of the form $\min_x \sum_i f_i(x)$. Specifically, we analyze
the SAGA algorithm within an Incremental First-order Oracle framework, and show
that it converges to a stationary point provably faster than both gradient
descent and stochastic gradient descent. We also discuss a Polyak's special
class of nonconvex problems for which SAGA converges at a linear rate to the
global optimum. Finally, we analyze the practically valuable regularized and
minibatch variants of SAGA. To our knowledge, this paper presents the first
analysis of fast convergence for an incremental aggregated gradient method for
nonconvex problems.

本文分析了一种用于优化非凸问题的快速递增聚合梯度方法，在递增一阶预言框架中分析了 SAGA 算法，并表明它比梯度下降和随机梯度下降更快地收敛到稳定点。此外，我们还讨论了 Polyak 特殊类的问题，针对这类问题，SAGA 方法的收敛速度为线性收敛到全局最优解。最后，我们分析了实际有用的 SAGA 正则化和小批量变体。据我们所知，这篇论文提出了第一篇关于递增聚合梯度方法快速收敛的分析。