The Experts below are selected from a list of 44901 Experts worldwide ranked by ideXlab platform
Usman A. Khan - One of the best experts on this subject based on the ideXlab platform.
-
linear convergence in optimization over Directed Graphs with row stochastic matrices
IEEE Transactions on Automatic Control, 2018Co-Authors: Van Sy Mai, Ran Xin, Eyad H Abed, Usman A. KhanAbstract:This paper considers a distributed optimization problem over a multiagent network, in which the objective function is a sum of individual cost functions at the agents. We focus on the case when communication between the agents is described by a Directed graph. Existing distributed optimization algorithms for Directed Graphs require at least the knowledge of the neighbors’ out-degree at each agent (due to the requirement of column-stochastic matrices). In contrast, our algorithm requires no such knowledge. Moreover, the proposed algorithm achieves the best known rate of convergence for this class of problems, $O(\mu ^k)$ for $0 , where $k$ is the number of iterations, given that the objective functions are strongly convex and have Lipschitz-continuous gradients. Numerical experiments are also provided to illustrate the theoretical findings.
-
A Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
IEEE Control Systems Letters, 2018Co-Authors: Ran Xin, Usman A. KhanAbstract:In this letter, we study distributed optimization, where a network of agents, abstracted as a Directed graph, collaborates to minimize the average of locally known convex functions. Most of the existing approaches over Directed Graphs are based on push-sum (type) techniques, which use an independent algorithm to asymptotically learn either the left or right eigenvector of the underlying weight matrices. This strategy causes additional computation, communication, and nonlinearity in the algorithm. In contrast, we propose a linear algorithm based on an inexact gradient method and a gradient estimation technique. Under the assumptions that each local function is strongly convex with Lipschitz-continuous gradients, we show that the proposed algorithm geometrically converges to the global minimizer with a sufficiently small step-size. We present simulations to illustrate the theoretical findings.
-
dextra a fast algorithm for optimization over Directed Graphs
IEEE Transactions on Automatic Control, 2017Co-Authors: Usman A. KhanAbstract:This paper develops a fast distributed algorithm, termed DEXTRA , to solve the optimization problem when $n$ agents reach agreement and collaboratively minimize the sum of their local objective functions over the network, where the communication between the agents is described by a Directed graph. Existing algorithms solve the problem restricted to Directed Graphs with convergence rates of $O(\ln k/\sqrt{k})$ for general convex objective functions and $O(\ln k/k)$ when the objective functions are strongly convex, where $k$ is the number of iterations. We show that, with the appropriate step-size, DEXTRA converges at a linear rate $O(\tau ^{k})$ for $0 , given that the objective functions are restricted strongly convex. The implementation of DEXTRA requires each agent to know its local out-degree. Simulation examples further illustrate our findings.
-
linear convergence in optimization over Directed Graphs with row stochastic matrices
arXiv: Optimization and Control, 2016Co-Authors: Van Sy Mai, Ran Xin, Eyad H Abed, Usman A. KhanAbstract:This paper considers a distributed optimization problem over a multi-agent network, in which the objective function is a sum of individual cost functions at the agents. We focus on the case when communication between the agents is described by a \emph{Directed} graph. Existing distributed optimization algorithms for Directed Graphs require at least the knowledge of the neighbors' out-degree at each agent (due to the requirement of column-stochastic matrices). In contrast, our algorithm requires no such knowledge. Moreover, the proposed algorithm achieves the best known rate of convergence for this class of problems, $O(\mu^k)$ for $0<\mu<1$, where $k$ is the number of iterations, given that the objective functions are strongly-convex and have Lipschitz-continuous gradients. Numerical experiments are also provided to illustrate the theoretical findings.
Alex Olshevsky - One of the best experts on this subject based on the ideXlab platform.
-
stochastic gradient push for strongly convex functions on time varying Directed Graphs
IEEE Transactions on Automatic Control, 2016Co-Authors: Angelia Nedic, Alex OlshevskyAbstract:We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying Directed Graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of $O((\ln t)/t)$ for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the $O((\ln t)/\sqrt{t})$ rate previously known for (general) convex functions.
-
nonasymptotic convergence rates for cooperative learning over time varying Directed Graphs
Advances in Computing and Communications, 2015Co-Authors: Angelia Nedic, Alex Olshevsky, Cesar A UribeAbstract:We study the problem of cooperative learning with a network of agents where some agents repeatedly access information about a random variable with unknown distribution. The group objective is to globally agree on a joint hypothesis (distribution) that best describes the observed data at all nodes. The agents interact with their neighbors in an unknown sequence of time-varying Directed Graphs. Following the pioneering work of Jadbabaie, Molavi, Sandroni, and Tahbaz-Salehi and others, we propose local learning dynamics which combine Bayesian updates at each node with a local aggregation rule of private agent signals. We show that these learning dynamics drive all agents to the set of hypotheses which best explain the data collected at all nodes as long as the sequence of interconnection Graphs is uniformly strongly connected. Our main result establishes a non-asymptotic, explicit, geometric convergence rate for the learning dynamic.
-
nonasymptotic convergence rates for cooperative learning over time varying Directed Graphs
arXiv: Optimization and Control, 2014Co-Authors: Angelia Nedic, Alex Olshevsky, Cesar A UribeAbstract:We study the problem of distributed hypothesis testing with a network of agents where some agents repeatedly gain access to information about the correct hypothesis. The group objective is to globally agree on a joint hypothesis that best describes the observed data at all the nodes. We assume that the agents can interact with their neighbors in an unknown sequence of time-varying Directed Graphs. Following the pioneering work of Jadbabaie, Molavi, Sandroni, and Tahbaz-Salehi, we propose local learning dynamics which combine Bayesian updates at each node with a local aggregation rule of private agent signals. We show that these learning dynamics drive all agents to the set of hypotheses which best explain the data collected at all nodes as long as the sequence of interconnection Graphs is uniformly strongly connected. Our main result establishes a non-asymptotic, explicit, geometric convergence rate for the learning dynamic.
-
stochastic gradient push for strongly convex functions on time varying Directed Graphs
arXiv: Optimization and Control, 2014Co-Authors: Angelia Nedic, Alex OlshevskyAbstract:We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying Directed Graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of $O \left((\ln t)/t \right)$ for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the $O \left((\ln t)/\sqrt{t} \right)$ rate previously known for (general) convex functions.
-
distributed optimization over time varying Directed Graphs
arXiv: Optimization and Control, 2013Co-Authors: Angelia Nedic, Alex OlshevskyAbstract:We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of Directed Graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of $O(\ln(t)/\sqrt{t})$, where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.
Angelia Nedic - One of the best experts on this subject based on the ideXlab platform.
-
stochastic gradient push for strongly convex functions on time varying Directed Graphs
IEEE Transactions on Automatic Control, 2016Co-Authors: Angelia Nedic, Alex OlshevskyAbstract:We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying Directed Graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of $O((\ln t)/t)$ for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the $O((\ln t)/\sqrt{t})$ rate previously known for (general) convex functions.
-
nonasymptotic convergence rates for cooperative learning over time varying Directed Graphs
Advances in Computing and Communications, 2015Co-Authors: Angelia Nedic, Alex Olshevsky, Cesar A UribeAbstract:We study the problem of cooperative learning with a network of agents where some agents repeatedly access information about a random variable with unknown distribution. The group objective is to globally agree on a joint hypothesis (distribution) that best describes the observed data at all nodes. The agents interact with their neighbors in an unknown sequence of time-varying Directed Graphs. Following the pioneering work of Jadbabaie, Molavi, Sandroni, and Tahbaz-Salehi and others, we propose local learning dynamics which combine Bayesian updates at each node with a local aggregation rule of private agent signals. We show that these learning dynamics drive all agents to the set of hypotheses which best explain the data collected at all nodes as long as the sequence of interconnection Graphs is uniformly strongly connected. Our main result establishes a non-asymptotic, explicit, geometric convergence rate for the learning dynamic.
-
nonasymptotic convergence rates for cooperative learning over time varying Directed Graphs
arXiv: Optimization and Control, 2014Co-Authors: Angelia Nedic, Alex Olshevsky, Cesar A UribeAbstract:We study the problem of distributed hypothesis testing with a network of agents where some agents repeatedly gain access to information about the correct hypothesis. The group objective is to globally agree on a joint hypothesis that best describes the observed data at all the nodes. We assume that the agents can interact with their neighbors in an unknown sequence of time-varying Directed Graphs. Following the pioneering work of Jadbabaie, Molavi, Sandroni, and Tahbaz-Salehi, we propose local learning dynamics which combine Bayesian updates at each node with a local aggregation rule of private agent signals. We show that these learning dynamics drive all agents to the set of hypotheses which best explain the data collected at all nodes as long as the sequence of interconnection Graphs is uniformly strongly connected. Our main result establishes a non-asymptotic, explicit, geometric convergence rate for the learning dynamic.
-
stochastic gradient push for strongly convex functions on time varying Directed Graphs
arXiv: Optimization and Control, 2014Co-Authors: Angelia Nedic, Alex OlshevskyAbstract:We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying Directed Graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of $O \left((\ln t)/t \right)$ for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the $O \left((\ln t)/\sqrt{t} \right)$ rate previously known for (general) convex functions.
-
distributed optimization over time varying Directed Graphs
arXiv: Optimization and Control, 2013Co-Authors: Angelia Nedic, Alex OlshevskyAbstract:We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of Directed Graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of $O(\ln(t)/\sqrt{t})$, where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.
Nikos Parotsidis - One of the best experts on this subject based on the ideXlab platform.
-
2 edge connectivity in Directed Graphs
ACM Transactions on Algorithms, 2016Co-Authors: Loukas Georgiadis, Giuseppe F Italiano, Luigi Laura, Nikos ParotsidisAbstract:Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of unDirected Graphs, surprisingly, not much has been investigated for Directed Graphs. In this article, we study 2-edge connectivity problems in Directed Graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2-edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v. This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the unDirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this article is an algorithm for computing the 2-edge-connected blocks of a Directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, when two query vertices v and w are not 2-edge-connected, we can produce in constant time a “witness” of this property by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v. We are also able to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-edge-connected blocks as the input graph, where n is the number of vertices.
-
2 edge connectivity in Directed Graphs
Symposium on Discrete Algorithms, 2015Co-Authors: Loukas Georgiadis, Giuseppe F Italiano, Luigi Laura, Nikos ParotsidisAbstract:Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of unDirected Graphs, surprisingly not much has been investigated for Directed Graphs. In this paper we study 2-edge connectivity problems in Directed Graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2-edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v. This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the unDirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this paper is an algorithm for computing the 2-edge-connected blocks of a Directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, we also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-edge-connected blocks as the input graph, where n is the number of vertices.
-
2 edge connectivity in Directed Graphs
arXiv: Data Structures and Algorithms, 2014Co-Authors: Loukas Georgiadis, Giuseppe F Italiano, Luigi Laura, Nikos ParotsidisAbstract:Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of unDirected Graphs, surprisingly not much has been investigated for Directed Graphs. In this paper we study $2$-edge connectivity problems in Directed Graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices $v$ and $w$ are $2$-edge-connected if there are two edge-disjoint paths from $v$ to $w$ and two edge-disjoint paths from $w$ to $v$. This relation partitions the vertices into blocks such that all vertices in the same block are $2$-edge-connected. Differently from the unDirected case, those blocks do not correspond to the $2$-edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are $2$-edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has $O(n)$ edges and maintains the same $2$-edge-connected blocks as the input graph.
Zhisheng Duan - One of the best experts on this subject based on the ideXlab platform.
-
Distributed adaptive consensus protocols for linear multi-agent systems over Directed Graphs with relative output information
IET Control Theory & Applications, 2018Co-Authors: Zhisheng DuanAbstract:This study is concerned with the fully distributed output feedback consensus protocol design problem for multi-agent systems with general linear dynamics over Directed Graphs. The authors propose new distributed observer-based adaptive consensus protocols to achieve consensus for strongly connected Directed Graphs or leader-follower Graphs. Different from the existing adaptive output feedback consensus protocols, which either depend on the absolute output information of each agent and its neighbours or are not fully distributed, the protocols designed in this study relying on only relative output information of neighbouring agents, can be implemented in a fully distributed way.
-
novel distributed robust adaptive consensus protocols for linear multi agent systems with Directed Graphs and external disturbances
International Journal of Control, 2017Co-Authors: Zhisheng Duan, Gang FengAbstract:ABSTRACTThis paper addresses the distributed consensus protocol design problem for linear multi-agent systems with Directed Graphs and external unmatched disturbances. Novel distributed adaptive consensus protocols are proposed to achieve leader–follower consensus for any Directed graph containing a Directed spanning tree with the leader as the root node and leaderless consensus for strongly connected Directed Graphs. It is pointed out that the adaptive protocols involve undesirable parameter drift phenomenon when bounded external disturbances exist. By using the σ modification technique, distributed robust adaptive consensus protocols are designed to guarantee the ultimate boundedness of both the consensus error and the adaptive coupling weights in the presence of external disturbances. All the adaptive protocols in this paper are fully distributed, relying on only the agent dynamics and the relative states of neighbouring agents.