SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
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.
This important paper introduces an incremental gradient method called SAGA for minimizing f+h when f is an average of n functions f_i (like ERM) and h is a possibly non-smooth regularizer (for which we know a prox operator), that has provable linear convergence rates when f (or each f_i according to the case) is strongly convex and the same algorithm without a change has a 1/k rate when strong convexity is absent, hence allowing it to adapt to the level of strong convexity in the problem, automatically interpolating between the rates.One of the important contributions of the paper is to show the similarities between a vast array of existing algorithms for this problem like SAG (which did not provably handle prox operators and was non-adaptive to strong convexity), and SDCA (developed over the last few years), and more recent algorithms from the past year like MISO and SVRG. While the relationship to SAG is rather straightforward (as hinted by the name SAGA), it was very interesting to see the connections to MISO and SVRG and even more so SDCA. One of the most interesting features of the paper was its ability to verbally explain why this method works well and how it relates to other methods. I found it rather interesting that it uses a biased gradient unlike SAG which results in a reduced variance. It is also interesting how SVRG is very similar to SAGA but trades off computation for space by not storing and updating the \phi vectors frequently. The relation to MISO/Finito is also interesting and not direct. Lastly, viewing the SDCA algorithm in the primal might also be of independent interest and even then it is unclear that there is any relation between the algorithms, so writing it in the same form as MISO is very interesting.The main contribution of the paper is its simple and clear proofs of convergence (as compared to SAG!) for both the strongly convex and the non-strongly convex case in the appendix, which will be of use in understanding these algorithms as well as designing new ones. Since it is adaptive to the presence or absence of strong convexity, it seems practically extremely useful when it is not known what the strong convexity constant is.Because of the importance of these kinds of problems in ML (ERM with regularizers with or without strong convexity), and the comparison to existing methods, I think this is a very important paper to many people in the community (while optimization people might be interested in the proofs, it also seems very practically applicable for everyone else). Possible typos - It seems to me like the "s" in many places (description of MISO and in proof of Lemma 1) should actually be "mu". In the appendix "manor" should be "manner".