In this work we introduce a new optimisation method called SAGA in the spirit
of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient
algorithms with fast linear convergence rates. SAGA improves on the theory
behind SAG and SVRG, with better theoretical convergence rates, and has support
for composite objectives where a proximal operator is used on the regulariser.
Unlike SDCA, SAGA supports non-strongly convex problems directly, and is
adaptive to any inherent strong convexity of the problem. We give experimental
results showing the effectiveness of our method.

介绍了一种新的优化方法 ——SAGA，它是在最近提出的一组具有快速线性收敛率的增量梯度算法：SAG、SDCA、MISO 和 SVRG 的基础上提出的。SAGA 改进了 SAG 和 SVRG 的理论，具有更好的理论收敛率，并支持在规则化器上使用近端算子的复合目标。与 SDCA 不同，SAGA 直接支持非强凸问题，并且适应于问题的任何内在强凸性。 我们给出了实验结果，表明我们的方法的有效性。

SAGA: 具有非强凸复合目标支持的快速增量梯度方法

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly  Convex Composite Objectives

Many structured data-fitting applications require the solution of an
optimization problem involving a sum over a potentially large number of
measurements. Incremental gradient algorithms offer inexpensive iterations by
sampling a subset of the terms in the sum. These methods can make great
progress initially, but often slow as they approach a solution. In contrast,
full-gradient methods achieve steady convergence at the expense of evaluating
the full objective and gradient on each iteration. We explore hybrid methods
that exhibit the benefits of both approaches. Rate-of-convergence analysis
shows that by controlling the sample size in an incremental gradient algorithm,
it is possible to maintain the steady convergence rates of full-gradient
methods. We detail a practical quasi-Newton implementation based on this
approach. Numerical experiments illustrate its potential benefits.

本文介绍了一种结构化数据拟合应用的优化问题的混合方法，同时具有增量梯度算法的高效迭代和完全梯度算法的稳定收敛性，基于这种方法提出了一个实用的拟牛顿算法实现，并通过数值实验证明了其潜在优势。