With the rise of big data, and of the internet of things, distributed applications are becoming increasingly more popular. Distributed optimization focuses on finding the minimizer of a cost which is the sum of several functions. Each of these functions is stored within an agent that is physically separated from the others. Because no agent has full knowledge on the global cost, the minimizer cannot be found using traditional, centralized optimization algorithms.
In recent years, numerous distributed optimization algorithms have been proposed by the scientific community. Many of these algorithms come with strong theoretical guarantees, but they sometimes lack certain qualities of practical interest: Some methods have global hyper-parameters that need to be tuned beforehand, and which can significantly affect the method’s performance. Typically, tuning these parame- ters requires knowledge on the total cost, which goes against the distributed mindset that motivated these algorithms in the first place. Another common issue is that these algorithms require communications to be coordinated between all the agents simultaneously, which can be difficult to implement in practice.
In this thesis, we propose and study two distributed optimization methods that are application-friendly in the following sense: They have no global parameters to tune, and they work in asynchronous setups, meaning that only a subset of the agents is communicating at a time.
The first of these methods, the Stochastic alternate Linearization Method (StochaLM), can be interpreted as a distributed version of the dual block coordinate ascent method. The second method, called the Distributed Jacobi Asynchronous Method (DJAM), is based on the Jacobi and Gauss-Seidel methods.
For both methods, we prove theoretical convergence guarantees which are verified under mild assumptions. We also provide numerical results which evidence that our methods are competitive with state-of-the-art methods by other authors. Finally, we discuss several possible future research directions based on the present work.