\nTo me, the most interesting recent development in convex optimisation is the
\ndiscovery of a family of methods that exploit a finite-sum objective structure
\nto theoretically and practically converge faster than was previously thought possible.\n<\/p>\n
\nThe two early methods in this class were SAG<\/a> I spent time during my thesis working on these methods, \nI would like to compile here a list of other papers broadly in this area with some brief comments on each. If you feel I’ve left anything out or you have a correction of some kind, please leave a comment and I’ll see to it.\n<\/p>\n The SVRG method<\/a> really pushed \nThere has been quite a lot of interest in distributed versions. I still believe that variants of distributed gradient \nFor regular SGD, the two best approaches I’ve seen for distribution are Downpour<\/a> and soft penality methods like Elastic Averaging SGD<\/a>. The soft penality approach might work well with SAGA; It seems like a good topic for future work.<\/p>\n \nThe DSA<\/a> method take the approach of combining the EXTRA method (a ADMM variant) with \nA few papers cover distributed SDCA, like this one<\/a> \nThe distributed SVRG method<\/a> is a promising method I’ve seen. \nAnother NIPS 2015 paper<\/a> from some well respected Carnegie Mellon researchers \nThe paper A Universal Catalyst for First-Order Optimization<\/a> (NIPS) \nThe paper on accelerated SDCA<\/a> also takes the double loop approach. \nAnother double loop paper<\/a> \nIt’s not clear to me if a non-double loop approach is possible for a purely primal stochastic finte-sum methods. \nThere is one non-double loop accelerated approach I know of, in this draft technical report<\/a> The “Neighborhood Watch” method<\/a> (NIPS 2015), \nAgarwal and Bottou have an ICML 2015 paper<\/a> directly \nThey don’t really discuss the core question (at least in my mind): Does there \nOn a somewhat less related but interesting note, \nThe restricted class they consider is interesting and covers the core \nThe key idea of Arjevani et. al. is limiting the class of optimisation methods to steps that are a linear transformation \nIt’s quite obvious that the uniform sampling scheme used by the standard finite sum The paper<\/a> by Schmidt et. al. (AISTATS 2015) covers this problem \nFor SDCA, this<\/a> preprint covers the problem to some degree. In general, weighted sampling for coordinate descent is a well studied problem \nThere are two NIPS 2015 papers on the general topic, both with Tong Zhang as a co-author! Local Smoothness in Variance Reduced Optimization<\/a> by Vainsencher, Liu and Zhang and Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling<\/a> by Qu, Richtarik and Zhang. \nThe Local-smoothness paper discusses the particular problem of adapting the sampling scheme at run-time, so that the weighting doesn’t need to be specified up front. This is practically a necessity for good performance, and they do establish some theory covering it unlike previous work on adaptivity for SAG. \nThere is still lots of interesting avenues of research open for finite sum methods. Do practical accelerated variants of any of the methods exist? Ideally without lots of parameters that require tuning. Are other variance reduction approaches possible (like adding a second set of control variates, or by using multiplicative instead of additive control?).\n <\/p>\n \nI would like to see some solid c\/c++ implementations of the best methods so that they can be more widely used. There are some reasonable python implementations in the Lightning<\/a> package, but they need adaptive step sizes and importance sampling to really be production ready. Multithreading would also be great. It would also be nice to see SAGA implemented in TensorFlow, Vowpal Wabbit and LibLinear for example.<\/p>\n","protected":false},"excerpt":{"rendered":" To me, the most interesting recent development in convex optimisation is the discovery of a family of methods that exploit a finite-sum objective structure to theoretically and practically converge faster than was previously thought possible. The two early methods in this class were SAG and SDCA. I spent time during my thesis working on these … Continue reading Recent work on minimising finite sums<\/span>
\n and SDCA<\/a>.<\/p>\n
\nsee my publications on SAGA<\/a>
\n(an improved version of SAG)
\nand Finito<\/a>.\n<\/p>\nSVRG<\/h3>\n
\nthe class of finite sum methods forward. It uses a clunky double-loop construction, but the theoretical analysis
\nis really simple compared to SAG and SDCA, and it’s really the core building block of the SAGA method mentioned above.
\nIt can also be readily applied to non-convex problems unlike the other methods mentioned here. It makes an interesting
\ntrade-off: it avoids storing gradients for each term, with the downside of 2-3x more gradient calculations total.
\nThis trade-off is bad for logistic regression and most convex problems, but for neural networks it may help. I haven’t looked to see if its seen any use on neural networks
\nin practice, maybe a topic for a future post.<\/p>\n Distributed variants <\/h3>\n
\nLBFGS are still the fastest method for distributed convex optimisation at large scale.
\nThe way that SAG and related methods
\nexploit the objective structure is not clearly extendable to the distributed setting. In constrast,
\ndistributed gradient LBFGS is a embarrassingly-parallel algorithm. LBFGS doesn’t work well for non-convex problems though, and thats where most of the interest in distribution optimisation is at the moment.\n<\/p>\n
\nSAGA. It seems like a good idea to me in principle. From their paper, it sounds like it might be the fastest
\nmethod for some network topologies. They also try the obvious way of distributing SAG, which they include in their plots.
\nThe “obvious” way doesn’t actually work (in the sense it doen’t converge linearly, losing all advantages it has over regular SGD),
\nso comparing against it is kind of silly. In general I don’t find their results convincing, although I’m not expert
\n on distributed optimisation.\n <\/p>\n
\nby Tianbao Yang. It compares against ADMM, which is horribly slow compared to distributed gradient LBFGS, so I’m not really convinced
\nby their results either.\n<\/p>\n
\nThe SVRG method is inherently double-loop, with the inner loop looking like it could be potentially parallelised. I haven’t
\nlooked at the details in this paper, but it concerns me that compare against methods that I would not consider standard.
\nI would like to see comparisons against one of the many distributed SGD methods, or DG-LBFGS, or even just a wall-clock
\ncomparison against non-distributed SVRG or SAGA.\n<\/p>\n
\nalso addresses the asynchronous (i.e. multicore rather than distributed) SVRG\/SAGA problem. They cite my thesis,
\nwhich immediately gives them bonus points in my mind.
\nThey start with generalising SAGA\/SVRG into a meta algorithm which covers both cases. The construction is fairly obvious,
\nbut it’s nice to see it worked out with all the details. They then give an asynchronous SVRG method, which appears reasonable.
\nThe analysis uses techniques from the Hogwild! paper, which is one of the better asynchronous SGD methods.
\nThey talk about the applicability of their framework to both SVRG and SAGA, but they strangely don’t talk at all about
\nan asynchronous SAGA. I have a hunch the technique they use for asynchronous SVRG would not work well with SAGA,
\nbut I could be wrong. They have an excellent experiments section, with actually legible plots!! (I wish we lived in a world
\nwhere this didn’t deserve exclamation marks). In particular they show a solid speedup, with a mostly linear speedup with the
\nnumber of cores, although the slope is not the perfect 1:1 rate.
\nI have to point out that they actually compare against SGD based methods, which is great. Most finite-sum papers skip doing this
\nbecause it’s a pain to implement a fast SGD method. There are simply too many possible variants that reviewers will inevitably
\nsuggest you try.\n<\/p>\n Accelerated variants <\/h3>\n
\nby Lin, Mairal and Harchaoui is the clearest approach.
\nIn general, virtually any optimisation method can
\nbe accelerated by using it to solve the proximal operator within the
\naccelerated proximal-point algorithm framework (see Salzo and Villa
\n2012, based on the proximal point method from Rockafellar).
\nLin et. al. take this approach, giving a double loop method, where any of the finite-sum methods mentioned can be used in the
\ninner loop. I have suspected this kind of approach could be applied to SAGA for a while now,
\nso it’s nice to see this paper working out the details.\n<\/p>\n
\nBoth approaches have convergence rates with large hidden logarithmic factors, which
\nare clearly not artefacts of the proof, but rather inherent in the double loop approach.\n<\/p>\n
\ntakes a mirror descent style approach. I’m not sure if this is the same as the proximal point version, at
\nleast on the surface it appears to be a different method. I like the plots in this paper, they are too small and
\nnot well typeset, but they do show the differences between their method and SAGA\/SVRG fairly clearly.
\nIt seems the general trend is that the accelerated methods take 50-100 iterations before they overtake SAGA\/SVRG,
\nwhich matches my intuition. For most practical problems I would expect less than 100 iterations to be used; typically
\nthe test set error is completely minimised by then.\n<\/p>\n
\nThe obvious approaches don’t work, as the noise form the stochasticity is far too large compared to the amount of error that
\nvariants of Nesterov’s accelerated method can handle.\n<\/p>\n
\nfrom U. Florida. It takes a primal-dual approach. Guanghui Lan talked about this method in his OPT2015 workshop talk, and it sounds extremely promising. It’s still an early draft; It has no experiments section yet. I’ll be keeping an eye out for the published version in the future.\n<\/p>\n Online learning variants <\/h3>\n
\ntake a hybrid approach between SAGA and classical SGD. Essentially they consider storing fewer past gradients by using the gradient at neighbouring points as a surrogate.
\nAlthough the method they propose is not surprising, it’s not at all clear a priori that the technique they propose would work in practice, so it’s nice to see some experiments and theory verifying it. The paper is interesting from a theoretical point of view, as they use a different Lyapunov function from that used by SAGA. It seems simpler.<\/p>\nLower complexity bounds<\/h3>\n
\naddressing the class of finite sums. They recently updated their arXiv version to note that their
\nproof only covers deterministic methods, which is not ideal given all the known fast finite-sum methods are stochastic!
\nTheir difficulties are not surprising, the lower complexity analysis for finite sum methods is extremely complex; I was not able to make any
\nprogress on the problem after spending a few months on it during my PhD. Looking at the construction they use, I don’t see how
\nthey can handle the stochastic case without large changes.
\nEven with the cavet above, this paper is still interesting, particularly for the discussion in section 3.\n<\/p>\n
\nexist a deterministic finite-sum method with comparable
\nconvergence rates to SAG type methods?
\nI personally won’t be happy until we have lower and upper complexity bounds that give a tight answer
\nto this question. I would be really surprised if there existed a fast deterministic method.\n<\/p>\n
\nArjevani, Shalev-Shwartz & Ohad Shamir have put up on arXiv<\/a>
\na paper proving some new lower complexity bounds for general strongly convex optimisation.
\nIt’s a long paper with a large number of results, but the one I find interesting is their core result.
\nThe key result is a lower-complexity bound; that is they show that no optimisation method in the class they consider,
\nno matter how clever, can converge any faster than the bound they state.
\nLower complexity bounds can be hard to grasp if you are used to upper bounds, like those proving the worst-case convergence
\nof a optimisation method. The inequalities are in the opposite direction.\n<\/p>\n
\nmethods for strongly convex optimisation, namely gradient-descent and the simplest accelerated variant.
\nThey avoid the first\/second order oracle class used in the early lower-complexity bounds literature, which is why
\nthey are able to give an improved bound. The key result is the removal of dependence on problem dimension from the bound.
\nPrevious lower complexity bounds applied to any first-order method, with a proof relying on analysis of quadratic
\nproblems for tractability reasons. Since the well known conjugate gradient method
\ncan find an exact optimum of a quadratic problem in O(p) time, for a p-dimensional problem, this dimension constant
\np appears in the old lower bounds.\n<\/p>\n
\nof the last rho steps (x_k and x_{k-1}) for rho typically 2 or 3.
\nThe transformation its self can’t depend on the x values, so line searches are ruled
\nout. The conjugate gradients method effectively does such a line-search (although it uses a closed form solution for it),
\nso it doesn’t fall within their restricted class.\n<\/p>\nAlternative sampling schemes<\/h3>\n
\nmethods can be improved if we know (or can at least approximate) the imbalance between the terms in the sum.
\nBy imbalance, I’m referring to the difference in the Lipschitz constants between each term. Terms with large constants
\nwill generally have a disproportionate contribution to the full gradient.
\nIn general we want methods where the theoretical convergence rate depends on the
\naverage Lipschitz constant of the terms, rather than the max, which is the case for SAG and other primal methods.\n<\/p>\n
\nfor SAGA\/SAG style methods. I contributed a little to the theory for this paper. They show quite astounding practical results
\nfor conditional random field (CRF) problems, where weighted sampling seems crucial.<\/p>\n
\nI’ve only skimmed this paper. The practical results are not super-impressive. I believe this is because they
\nonly test on linear learners, which are too simple to really see the benefit.<\/p>\n
\nso applying those results to dual coordinate descent (i.e. SDCA) is a obvious research direction. I have a simple weighted sampling proof for a minor variant of SDCA in my thesis.\n<\/p>\n
\nQuartz is a variant of SDCA with a interpolation-with-previous-value update for the primal estimate of x instead of a direct update. They say this leads to a better theoretical convergence rate. The main novelty is a proof that works for sampling schemes like mini-batch, importance sampling and uniform sampling. The practical performance is not as good as SDCA except when they are able to exploit sparsity together with mini-batching, as the update is more conservative. I like that they didn’t introduce another acroynm. It’s becoming impossible to communicate finite sum methods to people outside the field due to all the method names sounding similar.\n<\/p>\n
\nI like their discussion of why it can be effective. They point out that for smoothed-hinge loss, data-points whose activation is in the linear parts of the hinge can almost be ignored by the sampler once we get close to the solution.\n<\/p>\n The future <\/h3>\n