Statistical Preconditioning for Distributed Optimization | JRC Workshop 2021

Key Takeaways

hello everyone this is adrian hendricks and today i'll present you our work statistical preconditioning for distributed optimization this is joint work with ling chao and sebastian beck from microsoft research and francis back and lauren masuriere who are my phd advisors at inria paris so in this presentation we'll consider a distributed empirical risk minimization problem of the following form so the objective capital f can be written as an average of local objectives fg where fj is the local function of node j and you can think of it for instance as the loss function on the local data set of node g so this arrays is for instance when the data set is too big to be held on only one machine which happens a lot in online advertising or for image data sets which have just huge data sets and this is also the case when the data is inherently distributed and should not be for instance think of medical data held by hospitals or just because in general it's quite expensive to move or shuffle data so we adopt a centralized communication model um so in this model we have a server that has the parameter xk and then the server broadcast xk to all the workers the workers they locally compute their local gradients uh premium f5 of xk and then they send it back to the server the server aggregates all the local gradients uses them to compute the four gradients and then updates the parameter xk with this so this is a standard parallel grid in a sense and each iteration requires back and forth communication between the server and all workers so we'll take the following high level approach um our goal is to design a first order centralized algorithm with a low communication complexity so we want the we want it to be as few communication rounds as possible in order to achieve this i will assume that the server locally holds a function fn which approximates the global objective in some sense that we'll see later and the idea is to use this local function fn to change the iterations compared to grainy sense and thus reduce the iteration complexity and how we do this is using a mirror descent and appropriate pregnant life objects so our presentation will go as follows we first use the framework of red smoothness and strong convexity to formalize this notion of how well fn approximates f and show that this is captured by a new quantity the relative condition number kappa f of phi then we use concentration inequalities to give sharp bounds on kappa for the file depending on the size of the server's datasets and finally we'll briefly discuss an accelerated plane so the brain center iterations as you have seen um can be written in the following way so xt plus one is obtained uh by xt minus step size times improvement this can be written in an alternative form and so it's a minimization problem in which we wish to minimize as the dot product between our new parameters and the gradients under the condition that um the new parameter isn't too far from the current point x t so we penalize this problem uh by euclidean distance but actually we could use other uh kind of distances so not necessarily euclidean and if you plug in a bregman live vernon's term here then you obtain new dissents and the dragon divergence relative to f to phi between x and x t is given by the following equation and the important thing is for instance that's when phi is the squared norm then this reduces to greater sense because the gradient divergence reduces to the euclidean distance so what are the convergence properties of mirror distance well is if capital f is sigma f of 5 strongly convex and uh lfo5 smooth relatively to function 5 and so this relative regularity is just that uh the hessian of capital f is lower bounded by sigma times the fashion of phi and upper bounded by l times the hashing of uh so instead of having your hessian which is low down and up bounded just by the identity it's by another matrix and the hashem have another function and so in this case um the mirrored sign converges in kappa f over phi log 1 over epsilon iterations to minimize capital f at precision epsilon where kappa is this relative condition number so that smoothness divided by red strong complexity so compared to gradient sense uh what's interesting is that the kappa f in the bound is replaced by a kappa f alpha and this is interesting because kappa f of i can be much smaller so now the main question that we ask ourselves is uh what's the best phi for a distributed use case and what's the corresponding rate of condition number and the second question is how to accelerate this to obtain a square root kappa for five seconds while following the daily algorithm introduced by xiaomi retal we choose the function phi as fm so the local objective of the server plus a small quadratic term in the quadratic case we show that the relative condition number uh can actually be of order the usual condition number divided by n where n is the size of the server's datasets so this is huge because it means that even if you have a rather small local data set of the server then you can already achieve very good speed up and this just scales very well in the sample size at also in the case of generalized linear models such as logistic regression it's much harder because you don't concentrate matrices you need a concentration uniform concentration of hatchings yet you can still obtain that the relative condition number is of kappa f of square root n which is improvable to kappa f over and in some cases so in some cases you recover actually the convergence prices from your quadratic case what's important here is that our bounds improve the existing ones that are screwed and factor as in the cooler case and they hold outside of the pure product case and we show that the quadratic performance can actually be recorded in some but in quite large number of cases so now i'll just skip over the details of acceleration uh because i don't have time in this presentation and just present you quickly some experiments so this experiment these experiments were done the kdd2010 datasets which has 8 million samples in dimension 20 million we showed we chose the logistic regression objective with a very small organization parameter 13 minus seven and we compare three algorithms so uh day which is uh basically mirror descents uh with five chosen as i showed you a spag which is our accelerated version of thing and uh heavy bolding which is uh so spag is encashed lines and heavy bolding [Music] got dotted line which is another acceleration and uh so we benchmark this algorithm with three three different sizes for the local data sets in orange you have a thousand samples and login in the server in blue you have ten thousand samples and in red you have a hundred thousand samples so even though a hundred thousand samples looks big it's just one percent of the total injection so this really isn't much and in this case you see that um you can converge in a roughly 15 iteration to very very high precisions with accelerated their descent regardless of the method i mean we're slightly faster but it's not that fast but really uh the key thing is that when you have a huge local data set then you go fast and then even when the local data set isn't so big uh so for the blue curve you have only um you have a very small account date slope of 10 to the four so it's 1 000 times smaller than the big data sets and yet thanks to acceleration we achieve a very fast convergence uh to the optimum and in particular a much faster convergence than without the statistical condition and we see that uh when you have only 1000 samples then you still achieve good performances but of course the algorithm becomes kind of so so our contributions are the following and we presented the principal convergence theory based on mere descent we show improved balance on the relative condition number and we have a theory for a synthetic acceleration but we showed that it's actually quite effective in practice uh so there are some questions and one is the tightness of the concentration results and the other one is whether it's possible to prove non-asymptotic acceleration in some specific settings because it's actually impossible to prove it in general that's a negative result so i'm looking forward to hearing questions thank you for listening