Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning task) being distributed over n machines that can only communicate to their neighbors on a fixed communication graph. To reduce the communication bottleneck, the nodes compress (e.g. quantize or sparsify) their model updates. We cover both unbiased and biased compression operators with quality denoted by \omega 0. This is (up to our knowledge) the first gossip algorithm that supports arbitrary compressed messages for \omega > 0 and still exhibits linear convergence. We (iii) show in experiments that both of our algorithms do outperform the respective state-of-the-art baselines and CHOCO-SGD can reduce communication by at least two orders of magnitudes.

Stochastic distributed learning with gradient quantization and double-variance reduction

Konstantin Mishchenko, Sebastian Urban Stich

We consider distributed optimization over several devices, each sending incremental model updates to a central server. This setting is considered, for instance, in federated learning. Various schemes have been designed to compress the model updates in order to reduce the overall communication cost. However, existing methods suffer from a significant slowdown due to additional variance omega > 0 coming from the compression operator and as a result, only converge sublinearly. What is needed is a variance reduction technique for taming the variance introduced by compression. We propose the first methods that achieve linear convergence for arbitrary compression operators. For strongly convex functions with condition number kappa, distributed among n machines with a finite-sum structure, each worker having less than in components, we also (i) give analysis for the weakly convex and the non-convex cases and (ii) verify in experiments that our novel variance reduced schemes are more efficient than the baselines. Moreover, we show theoretically that as the number of devices increases, higher compression levels are possible without this affecting the overall number of communications in comparison with methods that do not perform any compression. This leads to a significant reduction in communication cost. Our general analysis allows to pick the most suitable compression for each problem, finding the rig ht balance between additional variance and communication savings. Finally, we also (iii) give analysis for arbitrary quantized updates.

TAYLOR & FRANCIS LTD2022

Optimization methods for collaborative learning

Sai Praneeth Reddy Karimireddy

A traditional machine learning pipeline involves collecting massive amounts of data centrally on a server and training models to fit the data. However, increasing concerns about the privacy and security of user's data, combined with the sheer growth in the data sizes has incentivized looking beyond such traditional centralized approaches. Collaborative learning (which encompasses distributed, federated, and decentralized learning) proposes instead for a network of data holders to collaborate together to train models without transmitting any data. This new paradigm minimizes data exposure, but inherently faces some fundamental challenges. In this thesis, we bring to bear the framework of stochastic optimization to formalize and develop new algorithms for these challenges. This serves not only to develop novel solutions, but also to test the utility of the optimization lens in modern deep learning.We study three fundamental problems. Firstly, collaborative training replaces a one-time transmission of raw data with repeated rounds of communicating partially trained models. However, this quickly runs against bandwidth constraints when dealing with large models. We propose to solve this bandwidth constraint using compressed communication. Next, collaborative training leverages the computation power of the data holders directly. However, this is not as reliable as using a data center with only a subset of them available at any given time. Thus, we require new algorithms which can efficiently utilize unreliable local computation of the data holders. Finally, collaborative training allows any data holder to participate in the training process, without being able to inspect their data or local computation. This may potentially open the system to malicious or faulty agents who seek to derail the training. We develop algorithms with Byzantine robustness which are guaranteed to be resilient to such attackers.

EPFL2021

Trust-region methods based on radial basis functions with application to biomedical imaging

Rodrigue Oeuvray

We have developed a new derivative-free algorithm based on Radial Basis Functions (RBFs). Derivative-free optimization is an active field of research and several algorithms have been proposed recently. Problems of this nature in the industrial setting are quite frequent. The reason is that in a number of applications the optimization process contains simulation packages which are treated as black boxes. The development of our own algorithm was originally motivated by an application in biomedical imaging: the medical image registration problem. The particular characteristics of this problem have incited us to develop a new optimization algorithm based on trust-region methods. However it has been designed to be generic and to be applied to a wide range of problems. The main originality of our approach is the use of RBFs to build the models. In particular we have adapted the existing theory based on quadratic models to our own models and developed new procedures especially designed for models based on RBFs. We have tested our algorithm called BOOSTERS against state-of-the-art methods (UOBYQA, NEWUOA, DFO). On the medical image registration problem, BOOSTERS appears to be the method of choice. The tests on problems from the CUTEr collection show that BOOSTERS is comparable to, but not better than other methods on small problems (size 2-20). It is performing very well for medium size problems (20-80). Moreover, it is able to solve problems of dimension 200, which is considered very large in derivative-free optimization. We have also developed a new class of algorithms combining the robustness of derivative-free algorithms with the faster rate of convergence characterizing Newtonlike-methods. In fact, they define a new class of algorithms lying between derivative-free optimization and quasi-Newton methods. These algorithms are built on the skeleton of our derivative-free algorithm but they can incorporate the gradient when it is available. They can be interpreted as a way of doping derivative-free algorithms with derivatives. If the derivatives are available at each iteration, then our method can be seen as an alternative to quasi-Newton methods. At the opposite, if the derivatives are never evaluated, then the algorithm is totally similar to BOOSTERS. It is a very interesting alternative to existing methods for problems whose objective function is expensive to evaluate and when the derivatives are not available. In this situation, the gradient can be approximated by finite differences and its costs corresponds to n additional function evaluations assuming that Rn is the domain of definition of the objective function. We have compared our method with CFSQP and BTRA, two gradient-based algorithms, and the results show that our doped method performs best. We have also a theoretical analysis of the medical image registration problem based on maximization of mutual information. Most of the current research in this field is concentrated on registration based on nonlinear image transformation. However, little attention has been paid to the theoretical properties of the optimization problem. In our analysis, we focus on the continuity and the differentiability of the objective function. We show in particular that performing a registration without extension of the reference image may lead to discontinuities in the objective function. But we demonstrate that, under some mild assumptions, the function is differentiable almost everywhere. Our analysis is important from an optimization point of view and conditions the choice of a solver. The usual practice is to use generic optimization packages without worrying about the differentiability of the objective function. But the use of gradient-based methods when the objective function is not differentiable may result in poor performance or even in absence of convergence. One of our objectives with this analysis is also that practitioners become aware of these problems and to propose them new algorithms having a potential interest for their applications.