SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
This work addresses optimization challenges in machine learning for researchers and practitioners, offering a faster method for non-strongly convex problems, though it appears incremental as it builds on prior algorithms like SAG and SVRG.
The authors tackled the problem of optimizing composite objectives with non-strongly convex functions by introducing SAGA, an incremental gradient method that improves theoretical convergence rates over existing algorithms like SAG and SVRG, with experimental results demonstrating its effectiveness.
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.