Cette dissertation fait face au problème de la localisation de sources, un sujet qui a été largement étudié dans la littérature récente au vu de son grand nombre d'applications. En particulier, ce travail se concentre sur le pilotage de multiples capteurs, capables de prendre des mesures ponctuelles de la quantité émise, vers la source sans faire usage d'aucune information de position, qui se trouve être indisponible dans de nombreux cas pratiques (par exemple, sous l'eau ou dans l'exploration souterraine). En faisant quelques hypothèses sur le processus de diffusion, nous développons un modèle qui permet d'utiliser des outils mathématiques (l'intégrale de Poisson et ses dérivées) pour obtenir une simple approximation du gradient de la fonction décrivant le processus de diffusion, dont la source représente le maximum, ce qui permet d'utiliser l'algorithme du gradient et trouver l'emplacement de la source. Les contributions sont de trois ordres : d'abord, nous utilisons ces outils pour résoudre le problème de la recherche d'une source en deux dimensions à travers d'un contrôle centralisé, où un seul véhicule, équipé de multiples capteurs et sans information de position, se déplace dans un environnement planaire où se trouve une source. Ensuite, nous étendons cette recherche à un cadre en trois dimensions, en considérant un engin volant équipé de capteurs qui se déplace dans l'espace ; pour ce cas plus général, outre la validation par simulations, nous fournissons également une étude théorique des propriétes de convergence de la loi de commande proposée. Enfin, nous abordons le problème de la localisation de source de façon distribuée, compte tenu de plusieurs capteurs autonomes mobiles (en deux dimensions) ; outre le problème de mettre en oeuvre l'algorithme de localisation de source de manière distribuée, nous devons garantir un contrôle de la formation approprié pour assurer l'exactitude de l'estimation du gradient, et donc atteindre la source.} / The dissertation faces the problem of source localisation, a topic which has been extensively studied in recent literature due to its large number of applications. In particular, it focuses on steering multiple sensors, able to take point-wise measurements of the emitted quantity, towards the source without making use of any position information, which happens to be unavailable in many practical cases (for example, underwater or underground exploration). By making some assumptions on the diffusion process, we develop a model which allows us to use some mathematical tools (the Poisson integral and its derivatives) for a simple approximation of the gradient of the function describing the diffusion process, whose source represents its maximum, making it possible to perform a gradient ascent to find the source location. The contributions are threefold: first, we use such tools to solve a 2-dimensional centralised source-seeking problem, where a single vehicle, equipped with multiple sensors and without position information, is moving in a planar environment where a source is supposed to emit. Then, we extend it to a 3-dimensional framework, considering a flying vehicle equipped with sensors moving in the space; for this more general case, in addition to simulation validation, we provide a theoretical study of the convergence properties of the proposed control law. Finally, we tackle the distributed source-localisation problem, considering several autonomous moving sensors (in two dimensions); in addition to the problem of implementing the source-localisation algorithm in a distributed manner, in this latter case we have also to guarantee a suitable formation control, to ensure the correctness of the gradient estimation and hence reach the source.

A fundamental assumption behind most machine learning (ML) algorithms and analyses is the sequential execution. That is, any update to the ML model can be immediately applied and the new model is always available for the next algorithmic step. This basic assumption, however, can be costly to realize, when the computation is carried out across multiple machines, linked by commodity networks that are usually 104 times slower than the memory speed due to fundamental hardware limitations. As a result, concurrent ML computation in the distributed settings often needs to handle delayed updates and perform learning in the presence of staleness. This thesis characterizes learning with staleness from three directions: (1) We extend the theoretical analyses of a number of classical ML algorithms, including stochastic gradient descent, proximal gradient descent on non-convex problems, and Frank-Wolfe algorithms, to explicitly incorporate staleness into their convergence characterizations. (2)We conduct simulation and large-scale distributed experiments to study the empirical effects of staleness on ML algorithms under indeterministic executions. Our results reveal that staleness is a key parameter governing the convergence speed for all considered ML algorithms, with varied ramifications. (3) We design staleness-minimizing parameter server systems by optimizing synchronization methods to effectively reduce the runtime staleness. The proposed optimization of a bounded consistency model utilizes the additional network bandwidths to communicate updates eagerly, relieving users of the burden to tune the staleness level. By minimizing staleness at the framework level, our system stabilizes diverging optimization paths and substantially accelerates convergence across ML algorithms without any modification to the ML programs.

Modern machine learning systems pose several new statistical, scalability, privacy and ethical challenges. With the advent of massive datasets and increasingly complex tasks, scalability has especially become a critical issue in these systems. In this thesis, we focus on fundamental challenges related to scalability, such as computational and communication efficiency, in modern machine learning applications. The underlying central message of this thesis is that classical statistical thinking leads to highly effective optimization methods for modern big data applications. The first part of the thesis investigates optimization methods for solving large-scale nonconvex Empirical Risk Minimization (ERM) problems. Such problems have surged into prominence, notably through deep learning, and have led to exciting progress. However, our understanding of optimization methods suitable for these problems is still very limited. We develop and analyze a new line of optimization methods for nonconvex ERM problems, based on the principle of variance reduction. We show that our methods exhibit fast convergence to stationary points and improve the state-of-the-art in several nonconvex ERM settings, including nonsmooth and constrained ERM. Using similar principles, we also develop novel optimization methods that provably converge to second-order stationary points. Finally, we show that the key principles behind our methods can be generalized to overcome challenges in other important problems such as Bayesian inference. The second part of the thesis studies two critical aspects of modern distributed machine learning systems — asynchronicity and communication efficiency of optimization methods. We study various asynchronous stochastic algorithms with fast convergence for convex ERM problems and show that these methods achieve near-linear speedups in sparse settings common to machine learning. Another key factor governing the overall performance of a distributed system is its communication efficiency. Traditional optimization algorithms used in machine learning are often ill-suited for distributed environments with high communication cost. To address this issue, we dis- cuss two different paradigms to achieve communication efficiency of algorithms in distributed environments and explore new algorithms with better communication complexity.

To integrate large volumes of renewables and use electricity more efficiently, many industrial trials are on-going around the world that aim to realize decentralized or hierarchical control of renewable and distributed energy resources, flexible loads and monitoring devices. As the cost and complexity involved in the centralized communications and control infrastructure may be prohibitive in controlling millions of these distributed energy resources and devices, distributed optimization methods are expected to become much more prevalent in the operation of future electric power systems, as they have the potential to address this challenge and can be applied to various applications such as optimal power ow, state estimation, voltage control, and many others. While many distributed optimization algorithms are developed mathematically, little effort has been reported so far on how these methods should actually be implemented in real-world large-scale systems. The challenges associated with this include identifying how to decompose the overall optimization problem, what communication infrastructures can support the information exchange among subproblems, and whether to coordinate the updates of the subproblems in a synchronous or asynchronous manner. This research is dedicated to developing mathematical tools to address these issues, particularly for solving the non-convex optimal power flow problem. As the first part of this thesis, we develop a partitioning method that defines the boundaries of regions when applying distributed algorithms to a power system. This partitioning method quantifies the computational couplings among the buses and groups the buses with large couplings into one region. Through numerical experiments, we show that the developed spectral partitioning approach is the key to achieving fast convergence of distributed optimization algorithms on large-scale systems. After the partitioning of the system is defined, one needs to determine whether the communications among neighboring regions are supported. Therefore, as the second part of this thesis, we propose models for centralized and distributed communications infrastructures and study the impact of communication delays on the efficiency of distributed optimization algorithms through network simulations. Our findings suggest that the centralized communications infrastructure can be prohibitive for distributed optimization and cost-effective migration paths to a more distributed communications infrastructure are necessary. As the sizes and complexities of subproblems and communication delays are generally heterogeneous, synchronous distributed algorithms can be inefficient as they require waiting for the slowest region in the system. Hence, as the third part of this thesis, we develop an asynchronous distributed optimization method and show its convergence for the considered optimal power flow problem. We further study the impact of parameter tuning, system partitioning and communication delays on the proposed asynchronous method and compare its practical performance with its synchronous counterpart. Simulation results indicate that the asynchronous approach can be more efficient with proper partitioning and parameter settings on large-scale systems. The outcome of this research provides important insights into how existing hardware and software solutions for Energy Management Systems in the power grid can be used or need to be extended for deploying distributed optimization methods, which establishes the interconnection between theoretical studies of distributed algorithms and their practical implementation. As the evolution towards a more distributed control architecture is already taking place in many utility networks, the approaches proposed in this thesis provide important tools and a methodology for adopting distributed optimization in power systems.

Decentralized multi-agent optimization has emerged as a powerful paradigm that finds broad applications in engineering design including federated machine learning and control of networked systems. In these setups, a group of agents are connected via a network with general topology. Under the communication constraint, they aim to solving a global optimization problem that is characterized collectively by their individual interests. Of particular importance are the computation and communication efficiency of decentralized optimization algorithms. Due to the heterogeneity of local objective functions, fostering cooperation across the agents over a possibly time-varying network is challenging yet necessary to achieve fast convergence to the global optimum. Furthermore, real-world communication networks are subject to congestion and bandwidth limit. To relieve the difficulty, it is highly desirable to design communication-efficient algorithms that proactively reduce the utilization of network resources. This dissertation tackles four concrete settings in decentralized optimization, and develops four provably efficient algorithms for solving them, respectively. Chapter 1 presents an overview of decentralized optimization, where some preliminaries, problem settings, and the state-of-the-art algorithms are introduced. Chapter 2 introduces the notation and reviews some key concepts that are useful throughout this dissertation. In Chapter 3, we investigate the non-smooth cost-coupled decentralized optimization and a special instance, that is, the dual form of constraint-coupled decentralized optimization. We develop a decentralized subgradient method with double averaging that guarantees the last iterate convergence, which is crucial to solving decentralized dual Lagrangian problems with convergence rate guarantee. Chapter 4 studies the composite cost-coupled decentralized optimization in stochastic networks, for which existing algorithms do not guarantee linear convergence. We propose a new decentralized dual averaging (DDA) algorithm to solve this problem. Under a rather mild condition on stochastic networks, we show that the proposed DDA attains an $\mathcal{O}(1/t)$ rate of convergence in the general case and a global linear rate of convergence if each local objective function is strongly convex. Chapter 5 tackles the smooth cost-coupled decentralized constrained optimization problem. We leverage the extrapolation technique and the average consensus protocol to develop an accelerated DDA algorithm. The rate of convergence is proved to be $\mathcal{O}\left( \frac{1}{t^2}+ \frac{1}{t(1-\beta)^2} \right)$, where $\beta$ denotes the second largest singular value of the mixing matrix. To proactively reduce the utilization of network resources, a communication-efficient decentralized primal-dual algorithm is developed based on the event-triggered broadcasting strategy in Chapter 6. In this algorithm, each agent locally determines whether to generate network transmissions by comparing a pre-defined threshold with the deviation between the iterates at present and lastly broadcast. Provided that the threshold sequence is summable over time, we prove an $\mathcal{O}(1/t)$ rate of convergence for convex composite objectives. For strongly convex and smooth problems, linear convergence is guaranteed if the threshold sequence is diminishing geometrically. Finally, Chapter 7 provides some concluding remarks and research directions for future study. / Graduate

<div>In the era of big data, the sheer volume and widespread spatial distribution of information has been promoting extensive research on distributed optimization over networks. Each computing unit has access only to a relatively small portion of the entire data and can only communicate with a relatively small number of neighbors. The goal of the system is to reach consensus on the optimal parametric model with respect to the entire data among all computing units. Existing work has provided various decentralized optimization algorithms for the purpose. However, some important questions remain unclear: (I) what is the intrinsic connection among different existing algorithms? (II) what is the min-max lower complexity bound for decentralized algorithms? Can one design an optimal decentralized algorithm in the sense that it achieves the lower complexity bound? and (III) in the presence of asynchrony and imperfect communications, can one design linearly convergent decentralized algorithms?</div><div><br></div><div> This thesis aims at addressing the above questions. (I) Abstracting from ad-hoc, specific solution methods, we propose a unified distributed algorithmic framework and analysis for a general class of optimization problems over networks. Our method encapsulates several existing first-order distributed algorithms. Distinguishing features of our scheme are: (a) When each of the agent’s functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents’ functions and network topology is decoupled; (b) When the objective function is convex, but not strongly convex, similar decoupling as in (a) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate; (c) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity; and (d) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms, yielding provably faster (worst-case) convergence rate for the class of problems under consideration. (II) Referring to lower complexity bounds, the proposed novel family of algorithms, when equipped with acceleration, are proved to be optimal, that is, they achieve convergence rate lower bounds. (III) Finally, to make the proposed algorithms practical, we break the synchronism in the agents’ updates: agents wake up and update without any coordination, using information only from immediate neighbors with unknown, arbitrary but bounded delays. Quite remarkably, even in the presence of asynchrony, the proposed algorithmic framework is proved to converge at a linear rate (resp. sublinear rate) when applied to strongly convex (resp. non strongly convex) optimization problems.</div>

Master‘s thesis deals with the theory of distributed optimization programs (next time just DOP), the suggestion and programme sample solver DOP and verification of the functionality of DOP ideas, principles and system architecture.

A cooperative multi-agent system is a collection of interacting agents deployed in a mission space where each agent is allowed to control its local state so that the fleet of agents collectively optimizes a common global objective. While optimization problems associated with multi-agent systems intend to determine the fixed set of globally optimal agent states, control problems aim to obtain the set of globally optimal agent controls. Associated non-convexities in these problems result in multiple local optima. This dissertation explores systematic techniques that can be deployed to either escape or avoid poor local optima while in search of provably better (still local) optima. First, for multi-agent optimization problems with iterative gradient-based solutions, a distributed approach to escape local optima is proposed based on the concept of boosting functions. These functions temporarily transform gradient components at a local optimum into a set of boosted non-zero gradient components in a systematic manner so that it is more effective compared to the methods where gradient components are randomly perturbed. A novel variable step size adjustment scheme is also proposed to establish the convergence of this distributed boosting process. Developed boosting concepts are successfully applied to the class of coverage problems. Second, as a means of avoiding convergence to poor local optima in multi-agent optimization, the use of greedy algorithms in generating effective initial conditions is explored. Such greedy methods are computationally cheap and can often exploit submodularity properties of the problem to provide performance bound guarantees to the obtained solutions. For the class of submodular maximization problems, two new performance bounds are proposed and their effectiveness is illustrated using the class of coverage problems. Third, a class of multi-agent control problems termed Persistent Monitoring on Networks (PMN) is considered where a team of agents is traversing a set of nodes (targets) interconnected according to a network topology aiming to minimize a measure of overall node state. For this class of problems, a gradient-based parametric control solution developed in a prior work relies heavily on the initial selection of its `parameters' which often leads to poor local optima. To overcome this initialization challenge, the PMN system's asymptotic behavior is analyzed, and an off-line greedy algorithm is proposed to systematically generate an effective set of initial parameters. Finally, for the same class of PMN problems, a computationally efficient distributed on-line Event-Driven Receding Horizon Control (RHC) solution is proposed as an alternative. This RHC solution is parameter-free as it automatically optimizes its planning horizon length and gradient-free as it uses explicitly derived solutions for each RHC problem invoked at each agent upon each event of interest. Hence, unlike the gradient-based parametric control solutions, the proposed RHC solution does not force the agents to converge to one particular behavior that is likely to be a poor local optimum. Instead, it keeps the agents actively searching for the optimum behavior. In each of these four parts of the thesis, an interactive simulation platform is developed (and made available online) to generate extensive numerical examples that highlight the respective contributions made compared to the state of the art.

Due to the increase in the advances in wireless communication, there has been an increase in the use of multi-agents systems to complete any given task. In various applications, multi-agent systems are required to solve an underlying optimization problem to obtain the best possible solution within a feasible region. Solving such multi-agent optimization problems in a distributed framework preferable over centralized frameworks as the former ensures scalability, robustness, and security. Further distributed optimization problem becomes challenging when the decision variables of the individual agents are coupled. In this thesis, a distributed optimization problem with coupled constraints is considered, where a network of agents aims to cooperatively minimize the sum of their local objective functions, subject to individual constraints. This problem setup is relevant to many practical applications like formation flying, sensor fusion, smart grids, etc. For practical scenarios, where agents can solve their local optimal solution efficiently and require fewer assumptions on objective functions, the Alternating Direction Method of Multipliers(ADMM)-based approaches are preferred over gradient-based approaches. For such a constraint coupled problem, several distributed ADMM algorithms are present that guarantee convergence to optimality but they do not discuss the complete analysis for the rate of convergence. Thus, the primary goal of this work is to improve upon the convergence rate of the existing state-of-the-art Tracking-ADMM (TADMM) algorithm to solve the above-distributed optimization problem. Moreover, the current analysis in literature does not discuss the convergence in the case of a time-varying communication network. The first part of the thesis focuses on improving the convergence rate of the Tracking-ADMM algorithm to solve the above-distributed optimization problem more efficiently. To this end, an upper bound on the convergence rate of the TADMM algorithm is derived in terms of the weight matrix of the network. To achieve faster convergence, the optimal weight matrix is computed using a semi-definite programming (SDP) formulation. The improved convergence rate of this Fast-TADMM (F-TADMM) is demonstrated with a simple yet illustrative, coupled constraint optimization problem. Then, the applicability of F-TADMM is demonstrated to the problem of distributed optimal control for trajectory generation of aircraft in formation flight. In the second part of the thesis, the convergence analysis for TADMM is extended while considering a time-varying communication network. The modified algorithm is named as Time-Varying Tracking (TV-TADMM). The formal guarantees on asymptotic convergence are provided with the help of control system analysis of a dynamical system that uses Lyapunov-like theory. The convergence of this TV-TADMM is demonstrated on a simple yet illustrative, coupled constraint optimization problem with switching topology and is compared with the fixed topology setting.

Cette thèse s’intéresse au problème d’estimation et d’optimisation distribuée dans les réseaux asynchrones, c’est à dire en n’utilisant que des communication locales et asynchrones. A partir de multiples applications allant de l’apprentissage automatique aux réseaux de capteurs sans-fils, nous concevons et analysons théoriquement de nouveaux algorithmes résolvant trois problèmes de nature très différentes : la propagation de la plus grande des valeurs initiales, l’estimation de leur moyenne et enfin l’optimisation distribuée. / This thesis addresses the distributed estimation and optimization of a global value of interest over a network using only local and asynchronous (sometimes wireless) communications. Motivated by many different applications ranging from cloud computing to wireless sensor networks via machine learning, we design new algorithms and theoretically study three problems of very different nature : the propagation of the maximal initial value, the estimation of their average and finally distributed optimization.