We study the problem of minimizing the average of a very large number of smooth functions, which is of key importance in training supervised learning models. One of the most celebrated methods in this context is the SAGA algorithm. Despite years of research on the topic, a general-purpose version of SAGA---one that would include arbitrary importance sampling and minibatching schemes---does not exist. We remedy this situation and propose a general and flexible variant of SAGA following the {\em arbitrary sampling} paradigm. We perform an iteration complexity analysis of the method, largely possible due to the construction of new stochastic Lyapunov functions. We establish linear convergence rates in the smooth and strongly convex regime, and under a quadratic functional growth condition (i.e., in a regime not assuming strong convexity). Our rates match those of the primal-dual method Quartz for which an arbitrary sampling analysis is available, which makes a significant step towards closing the gap in our understanding of complexity of primal and dual methods for finite sum problems.

通过提出一种新的SAGA变体，并构建新的随机Lyapunov函数，我们展示了一种通用和灵活的方法，可用于训练监督学习模型中极大数量的平滑函数之和的平均值的最小化问题，这种方法可以包括任意的重要性抽样和小批量处理方法，并展示了该方法的迭代复杂度分析和平滑和强凸情形下的线性收敛率，从而在对于有限总和问题的原始/对偶方法的复杂性的理解上迈出了重要一步。

任意采样的SAGA