Resilient Distributed Optimization

Distributed optimization has attracted considerable attention and achieved remarkable success in both theory and practice. The distributed convex optimization problem was first studied in [1] where a distributed subgradient algorithm was proposed. After this, various distributed optimization algorithms have been crafted and studied; see survey papers [2, 3, 4]. Distributed optimization techniques are also widely applied to decentralized deep learning [5].

Information exchange between neighboring agents is necessary for a multi-agent network for distributed optimization. However, agents’ states may be corrupted and they may not adhere to the designed algorithm due to faulty processes or external attacks. An agent is called Byzantine if it updates its state in an arbitrary, unknown manner, and can send conflicting values to different neighbors [6]. Such attacking agents can know global information of the network, play arbitrarily and strategically, and even be coordinated. Consider a network of agents in which Byzantine agents exist. An ideal resilient algorithm is the one which can lead non-Byzantine (or normal) agents to cooperatively solve the corresponding distributed optimization problem in the presence of Byzantine agents as if they do not exist. Such a resilient algorithm is highly desirable for the safety and security of multi-agent systems as faulty processes and external attacks are inevitable.

Resilient distributed optimization has recently received increasing attention, probably originating from the work of [7]. Almost all the existing works cannot guarantee full resilience; what they can guarantee is all normal agents’ states converge to a bounded neighborhood of the desired optimal point whose bound is not controllable [8, 9, 10, 11, 12], or an optimal point of an unspecified convex combination of all normal agents’ objective functions [7, 13, 14], or a convex combination of all normal agents’ local optimal points [15]. The only exceptions are [16, 17, 18] in which the underlying communication graph is assumed to be a complete graph, namely, each agent is allowed to communicate with all other agents. All [16, 17, 18] rely on the idea of “objective function redundancy”. The idea has also been applied to the federated setting and achieved full resilience [19, 20]. In the federated setting, a central coordinator agent is able to communicate with all worker agents, which is more or less equivalent to a complete graph in the distributed setting (or sometimes called decentralized setting). It is worth noting that [7, 13, 14, 15, 18] only consider special one-dimensional optimization.

Resilient distributed optimization is also related to resilient federated optimization/learning in the coordinator-workers setting (e.g., [20, 21, 22]), which has attracted increasing attention recently. The key problem is how the central coordinator aggregates the received information to eliminate or attenuate the effects of Byzantine worker agents. Various Byzantine-resilient information aggregation methods have been proposed for high-dimensional optimization/learning, focusing on stochastic gradient descent (SGD). Notable among them are [23, 24, 25, 26, 27], just to name a few; see an overview of recent developments in this area in [28]. It is doubtable that these methods can be applied to achieve full resilience in the distributed setting.

From the preceding discussion, and to the best of our knowledge, a fully resilient distributed optimization algorithm for general non-complete communication graphs does not exist, even for one-dimensional optimization problems. This gap is precisely what we study in this paper. We consider a distributed convex optimization problem in the presence of Byzantine agents and propose a fully resilient distributed subgradient algorithm based on the ideas of objective redundancy (cf. Definition 1) and graph redundancy (cf. Definition 2). The algorithm is shown to cause all non-Byzantine agents’ states to asymptotically converge to the same desired optimal point under appropriate assumptions. The proposed algorithm works theoretically for multi-dimensional optimization but practically not for high-dimensional optimization, as will be explained and discussed in the concluding remarks.

This work is motivated by two recent ideas. The first is the quantified notion of objective function redundancy proposed in [29] where a couple of different definitions of objective redundancy are studied, based on which fully resilient distributed optimization algorithms have been crafted either for a federated setting [29, 19, 20] or a distributed setting over complete graphs [16, 17, 18]; such redundancy has been shown necessary for achieving full resilience in multi-agent optimization [19]. We borrow one notation in [29] and further develop it. It is worth emphasizing that the results in [16, 17, 18] rely on objective redundancy among non-Byzantine agents, whereas ours depend on objective redundancy among all agents. This subtle difference is important for equipping a multi-agent network with a certain level of redundancy at a network design stage as which agents are non-Byzantine cannot be assumed a priori.

The second idea is so-called “Byzantine vector consensus” [30, 31] whose goal is, given a set of both Byzantine and non-Byzantine vectors, to pick a vector lying in the convex hull of the non-Byzantine vectors, based on Tverberg’s theorem [32, 33]. The idea has been very recently improved in [34] which can be used to achieve resilient multi-dimensional consensus exponentially fast. Exponential consensus is critical in the presence of diminishing disturbance [35]. We are prompted by this improved idea and make use of a resilient vector picking process, simplified from that of [34, Algorithm 1]. There are other recent approaches appealing to the idea of centerpoint [36, 37]. We expect that these approaches can also be applied to resilient optimization, provided that exponential consensus is guaranteed, e.g., in [37].

Consider a network consisting of $n$ agents, labeled $1$ through $n$ for the purpose of presentation. The agents are not aware of such global labeling, but can differentiate between their neighbors. The neighbor relations among the $n$ agents are characterized by a directed graph $\mathbb{G}=(\mathcal{V},\mathcal{E})$ whose vertices correspond to agents and whose directed edges (or arcs) depict neighbor relations, where $\mathcal{V}=\{1,\ldots,n\}$ is the vertex set and $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the directed edge set.¹¹1We use ${\cal A}\subset{\cal B}$ to denote that ${\cal A}$ is a subset of ${\cal B}$. Specifically, agent $j$ is a neighbor of agent $i$ if $(j,i)\in{\cal E}$. Each agent can receive information from its neighbors. Thus, the directions of edges represent the directions of information flow. We use $\mathcal{N}_{i}$ to denote the neighbor set of agent $i$, excluding $i$, i.e., $\mathcal{N}_{i}=\{j\in\mathcal{V}:(j,i)\in\mathcal{E}\}$.

Each agent $i\in{\cal V}$ has a “private” convex (not necessarily differentiable) objective function, $f_{i}:{\rm I\!R}^{d}\rightarrow{\rm I\!R}$, only known to agent $i$. There exist Byzantine agents in the network which are able to transmit arbitrary values to others and capable of sending conflicting values to different neighbors at any time. The set of Byzantine agents is denoted by ${\cal F}$ and the set of normal (non-Byzantine) agents is denoted by ${\cal H}$. Which agents are Byzantine is unknown to normal agents. It is assumed that each agent may have at most $\beta$ Byzantine neighbors.

The goal of the normal agents is to cooperatively minimize the objective functions

We will show that minimizing the above two objective functions can be achieved simultaneously with appropriate redundancy in objective functions (cf. Definition 1 and Corollary 1). It is assumed that the set of optimal solutions to $f$, denoted by ${\cal X}^{*}$, is nonempty and bounded.

Since each $f_{i}$ is not necessarily differentiable, the gradient descent method may not be applicable. Instead, the subgradient method [38] can be applied. For a convex function $h:{\rm I\!R}^{d}\rightarrow{\rm I\!R}$, a vector $g\in{\rm I\!R}^{d}$ is called a subgradient of $h$ at point $x$ if

Such a vector $g$ always exists and may not be unique. In the case when $h$ is differentiable at point $x$, the subgradient $g$ is unique and equals $\nabla h(x)$, the gradient of $h$ at $x$. Thus, the subgradient can be viewed as a generalization of the notion of the gradient. From (1) and the Cauchy-Schwarz inequality, $h(y)-h(x)\geq-G\|y-x\|$, where $G$ is an upper bound for the 2-norm of the subgradients of $h$ at both $x$ and $y$. We will use this fact without special mention in the sequel. Throughout this paper, we use $\|\cdot\|$ for the 2-norm.

The subgradient method was first proposed in [38] and the first distributed subgradient method was proposed in [1] for undirected graphs. Its extension to directed graphs has been studied in [39] and recently further analyzed in [40].

To describe our algorithm, we need the following notation.

Let ${\cal A}_{i}$ denote the collection of all those subsets of ${\cal N}_{i}$ whose cardinality is $(d+1)\beta+1$. It is obvious that the number of all such subsets is

and label them ${\cal A}_{i1},\ldots,{\cal A}_{ia_{i}}$. For each $j\in\{1,\ldots,a_{i}\}$, let ${\cal B}_{ij}$ denote the collection of all those subsets of ${\cal A}_{ij}$ whose cardinality is $d\beta+1$. For any subset of agents ${\cal S}\subset{\cal V}$, let ${\cal C}_{{\cal S}}(t)$ denote the convex hull of all $x_{i}(t)$, $i\in{\cal S}$.

Algorithm: At each discrete time $t\in\{0,1,2,\ldots\}$, each agent $i$ first picks an arbitrary point

for each $j\in\{1,\ldots,a_{i}\}$, and then updates its state by setting

where $\alpha(t)$ is the stepsize, and $g_{i}(\cdot)$ is a subgradient of $f_{i}(\cdot)$. $\Box$

In the special one-dimensional case with $d=1$, it is not hard to check that the steps (4) and (5) simplifies to the resilient scalar consensus algorithm in [41], which is essentially equivalent to the trimmed mean method and has been improved in [42].

The convergence and correctness of the proposed algorithm rely on the following assumptions.

It is easy to see that Assumption 1 implies that $f(x)$ is differentiable at any $x\in{\rm int}({\cal X}^{*})$, where ${\rm int}(\cdot)$ denotes the interior of a set. More can be said.

Proof of Lemma 3: Since ${\rm int}({\cal X}^{*})$ is nonempty, for any $x^{*}\in{\rm int}({\cal X}^{*})$, there exist a positive number $r$ and an open ball in ${\rm int}({\cal X}^{*})$ centered at $x^{*}$ with radius $r$, denoted as ${\cal B}(x^{*},r)\subset{\rm int}({\cal X}^{*})$. Let $h_{j}$ be a vector in ${\rm I\!R}^{d}$ whose $j$th entry is $\epsilon$ and the remaining entries all equal zero. Since $x^{*}+h_{j}\in{\cal B}(x_{0},r)\subset{\rm int}({\cal X}^{*})$ for sufficiently small $\epsilon$,

For each $i\in{\cal V}$, since $f_{i}(x)$ is convex, both $\lim_{\epsilon\rightarrow 0^{-}}\frac{f_{i}(x^{*}+h_{j})-f_{i}(x^{*})}{\epsilon}$ and $\lim_{\epsilon\rightarrow 0^{+}}\frac{f_{i}(x^{*}+h_{j})-f_{i}(x^{*})}{\epsilon}$ exist and $\lim_{\epsilon\rightarrow 0^{-}}\frac{f_{i}(x^{*}+h_{j})-f_{i}(x^{*})}{\epsilon}\leq\lim_{\epsilon\rightarrow 0^{+}}\frac{f_{i}(x^{*}+h_{j})-f_{i}(x^{*})}{\epsilon}$ for all $j\in\{1,\ldots,d\}$ [43, Theorem 24.1]. It follows that

Note that from (7),

Thus, $\lim_{\epsilon\rightarrow 0^{-}}\frac{f_{i}(x^{*}+h_{j})-f_{i}(x^{*})}{\epsilon}=\lim_{\epsilon\rightarrow 0^{+}}\frac{f_{i}(x^{*}+h_{j})-f_{i}(x^{*})}{\epsilon}$, i.e., $\partial f_{i}(x^{*})/\partial x_{j}$ exists for all $i\in{\cal V}$ and $j\in\{1,\ldots,d\}$.

To proceed, let $h_{i}(x)=\sum_{k\in{\cal V},\;k\neq i}f_{k}(x)$ for all $i\in{\cal V}$. From Corollary 1, $\operatorname*{arg\,min}_{x}h_{i}(x)={\cal X}^{*}$. Since $x^{*}\in{\rm int}({\cal X}^{*})$, both $f(x)$ and $h_{i}(x)$ are differentiable at $x^{*}$, implying that $\frac{\partial f}{\partial x_{j}}(x^{*})=\frac{\partial h_{i}}{\partial x_{j}}(x^{*})=0$ for all $i\in{\cal V}$ and $j\in\{1,\ldots,d\}$. Since $f_{i}(x)=f(x)-h_{i}(x)$, $\frac{\partial f_{i}}{\partial x_{j}}(x^{*})=0$ for all $i\in{\cal V}$ and $j\in\{1,\ldots,d\}$. Note that this holds for all $x^{*}\in{\rm int}({\cal X}^{*})$. From [44, Section 8.4.2], $f_{i}(x)$ is differentiable at $x^{*}$ with $\nabla f_{i}(x^{*})=0$ for all $i\in{\cal V}$.  

Lemma 3 has the following important implication.

Corollary 3 immediately implies that

Proof of Corollary 3: Suppose that, to the contrary, there exist $x^{*}\in{\cal X}^{*}$ and $i\in{\cal V}$ such that $x^{*}\notin\operatorname*{arg\,min}_{x}f_{i}(x)$. Pick a $z\in{\rm int}({\cal X}^{*})$. From Lemma 3, $z\in\operatorname*{arg\,min}_{x}f_{i}(x)$. It is then clear that $f_{i}(x^{*})>f_{i}(z)$. Let $h_{i}(x)=\sum_{k\in{\cal V},\;k\neq i}f_{k}(x)$. From Corollary 1, $\operatorname*{arg\,min}_{x}h_{i}(x)={\cal X}^{*}$, and thus $h_{i}(x^{*})=h_{i}(z)$. It follows that $f(x^{*})=f_{i}(x^{*})+h_{i}(x^{*})>f_{i}(z)+h_{i}(z)=f(z)$, which contradicts the fact that $x^{*}\in{\cal X}^{*}$.  

The above two assumptions are standard for subgradient methods.

To state our main results, we need the following concepts. For a directed graph $\mathbb{G}$, we use ${\cal R}_{r,s}(\mathbb{G})$ to denote the set of all $(r,s)$-reduced graphs of $\mathbb{G}$. For a rooted graph $\mathbb{G}$, we use $\kappa(\mathbb{G})$ to denote the size of the unique strongly connected component whose vertices are all roots of $\mathbb{G}$; in other words, $\kappa(\mathbb{G})$ equals the number of roots of $\mathbb{G}$. For any $(r,s)$-resilient graph $\mathbb{G}$, let

which is well-defined and denotes the smallest possible number of roots in any $(r,s)$-reduced graphs of $\mathbb{G}$.

The following example shows that $(n-\kappa_{\beta,d\beta}(\mathbb{G}))$-redundancy is necessary. For simplicity, set $d=1$. Consider a 4-agent network whose neighbor graph is the 4-vertex complete graph $\mathbb{C}$, which is $(1,1)$-resilient. Suppose that agent 4 is Byzantine and the other three are normal. It is possible that, with a carefully crafted attack strategy of the Byzantine agent, the three normal agents update their states mathematically equivalent to the case as if their neighbor graph is the 3-vertex $(1,1)$-reduced graph with the arc set $\{(1,2),(1,3),(2,3)\}$, which is rooted (cf. Lemma 6). In this case, since vertex 1 is the only root and agent 1 does not have any neighbor, it follows the single-agent subgradient algorithm, and thus its state will converge to a minimum point of $f_{1}(x)$, denoted $x^{*}$. Since all normal agents will eventually reach a consensus (cf. Lemma 9), both states of agents 2 and 3 will converge to $x^{*}$. To guarantee the resilient distributed optimization problem is solvable in this case, there must hold that $x^{*}\in\operatorname*{arg\,min}_{x}f_{i}(x)$, $i\in\{1,2,3\}$, which implies that the network needs to be 3-redundant. It is easy to see that $\kappa_{1,1}(\mathbb{C})=1$, and thus $n-\kappa_{1,1}(\mathbb{G})=3$.

Theorem 1 shows that the proposed algorithm achieves full resiliency. We next partially characterize the convergence rate of the algorithm.

The existing distributed optimization literature (without Byzantine agents) typically characterizes convergence rates by bounding the difference between $\sum_{i\in{\cal V}}f_{i}(\frac{1}{T}\sum_{t=0}^{T-1}x_{i}(t))$ and $\sum_{i\in{\cal V}}f_{i}(x^{*})$. The above theorem can be viewed as a “partial” convergence rate result in that it only reckons a subset ${\cal S}$ of normal agents and a subsequence ${\cal T}$ in a finite time horizon. Notwithstanding this, it is worth noting that $\min\sum_{i\in{\cal S}}f_{i}(x)$ is equivalent to $\min\sum_{i\in{\cal V}}f_{i}(x)$ in the setting here with Byzantine agents (cf. Corollary 1) and that $|{\cal T}|=O(T)$. Therefore, the theorem still to some extent evaluates the convergence rate of the resilient distributed subgradient algorithm under consideration. It is well known that the optimal convergence rate of subgradient methods for convex optimization is $O(1/\sqrt{t})$. Whether $f_{{\cal H}}(\cdot)=\sum_{i\in{\cal H}}f_{i}(\cdot)$ converges at this optimal rate or not, has so far eluded us.

Theorem 2 is an immediate consequence of the following proposition.

The proposition further quantifies a trade-off between the number of normal agents in ${\cal S}$ and the length of time subsequence ${\cal T}$. Roughly speaking, the fewer the normal agents involved in (8), the denser would the time subsequence be. In the special case when $b=\kappa_{\beta,d\beta}(\mathbb{G})$, the proposition simplifies to the following corollary.

This section provides the analysis of the algorithm and proofs of the main results.