UCLA

In this dissertation, we consider the problem of collaborating a network of nodes to accomplish an objective, which could be monitoring the state of a dynamical system or training a machine learning model, where each node only has access to partial data. Some nodes in the network are assumed to be attacked by an adversary. The attacked nodes may release incorrect information or, in the worst case, deviate from the prescribed rule and behave in an unexpected manner. This problem lies in the intersection of control theory, signal processing, machine learning, and network coding theory.

This problem is of great interest due to its wide applications in real life, such as monitoring the energy flow of a power grid, localizing a drone with multiple cameras, and machine learning in a decentralized network. Also, with the growing size of networked systems, it is getting harder and harder to physically shield network entities from adversarial attacks, which calls for a solution to the aforementioned problem even in the presence of adversaries.

In the first part of the dissertation, we study the problem of how to reconstruct the state of a linear system using partially corrupted state observations from heterogeneous sensors. In this part, we first discuss the computational complexity of this problem. We point out that although this problem is, in general, NP-hard, it allows a polynomial-time solution if certain conditions are met. We then extend our study on the same state-reconstruction problem, but in a decentralized network, where we focus on how the network topology and the dynamics of the linear systems affect the maximum number of correctable attacked nodes and attacked communication channels. In the end, we propose a novel approach, based on source coding and dynamic average consensus algorithms, that enables each node in the network to track the state of a linear system using minimal communications.

In the second part of the dissertation, we switch to the decentralized machine learning problem. We consider a collection of nodes connected through a network, each equipped with a local data set. The objective for all the nodes is to collectively train a machine learning model that minimizes the empirical loss, in a decentralized manner, i.e., each node can only use its local function and messages exchanged with nodes it is connected to. Moreover, each node is to agree on the said minimizer despite an adversary that can arbitrarily change the local functions of a fraction of the nodes. To solve this problem, we propose a novel decentralized learning algorithm that enables all nodes to reach consensus on the optimal model, by identifying attacked nodes and filtering out erroneous messages.