“Locality in Network Optimization”

Speaker: Sekhar Tatikonda
Associate Professor of Electrical Engineering
Yale University

Talk Summary: The complexity of network optimization depends on the network topology, the nature of the objective function, and what information (local or global) is available to the decision makers.   In this talk we introduce a notion of network locality and explore some of its properties.  (Joint work with Patrick Rebeschini.)

“Message Passing in Network Optimization”

Speaker: Patrick Rebeschini
Lecturer in the Computer Science Department at Yale University
 

Talk Summary: Message-passing algorithms are simple, iterative, distributed, general-purpose routines for a wide class of optimization and statistical problems that have a graph structure. In network optimization, message-passing is used to optimize objective functions that are sums of component functions supported on local parts of the network. For convex functions, message-passing has been shown to converge to the problem solution in any network topology under the assumption of scaled diagonal dominance. This condition is restrictive, and it does not apply to constrained problems. In our work we establish a general framework to analyze the convergence of message-passings in more general settings that include constraints. As an application, we analyze the behavior of message-passing to solve systems of linear equations in the Laplacian matrices of graphs, and to compute electric flows. These are two fundamental primitives that arise in several domains such as computer science, electrical engineering, operations research, and machine learning. (joint work with Sekhar Tatikonda)

.