IMSE summer school on Multi-Agent Networked Systems

August 15-18, 2013

Organized by IMSE at the University of Illinois at Urbana-Champaign.

Interconnected networks, such as biological, communication, distribution, economic, financial, information, power, social, and transportation, have become the overarching paradigm of the modern society.more

Advances in technology have led to the ability to build large-scale connected networks with the capabilities by far greater than the mere union of their components.

The newly emerged network systems offer ways to dramatically improve our lives in various aspects. The existing, as well as the emerging networked systems concepts, pose challenging mathematical, engineering and computational problems whose resolution necessitates collaborations among mathematicians and engineers to cultivate a new discipline, which one may term the Science of Networks. The principal goal of this discipline is to gain a deep understanding of the networks intricacy through the development of fundamental mathematical theories and efficient computational methods for the resolution of various technical challenges of network issues.

As the Science of Networks is gaining an unprecedented interest in our research community, in order to initiate a successful development of this discipline it is critical to nourish and expand the existing collaboration of mathematicians and engineers, as well as to create new opportunities for their interactions.

Location:

Transportation Building 304

Program

The program will be comprised of four 2-hour tutorials, invited technical talks and a student talks session.
Sufficient break times will be included in each day.

Schedule

time Thursday, 8/15 Friday, 8/16 Saturday, 8/17 Sunday, 8/18
8:00 — 8:30 AM registration, light breakfast
8:30 — 8:45 opening
8:45 — 9:45 Angelia Nedich Stephen Morse Zhi-Quan (Tom) Luo Jeff Shamma
9:45 — 10:30 Lacra Pavel Lee DeVille Anna Scaglione Uday Shanbhag
10:30 — 11:00 coffee break coffee break coffee break coffee break
11:00 — 11:45 Kay Kirkpatrick Peter Marbach Choon Yik Tang Ali Belabbas
11:45 — 12:30 PM Sewoong Oh Michael Mahoney Shreyas Sundaram Ketan Savla
12:30 — 2:00 lunch lunch lunch lunch
2:00 — 3:00 Angelia Nedich Stephen Morse Zhi-Quan (Tom) Luo Jeff Shamma
3:00 — 3:45 Maxim Raginsky Alejandro Dominguez-Garcia Dan Work Negar Kiyavash
3:45 — 4:15 break break break break
4:15 — 5:00 Randy Berry Jared Bronski Mingyi Hong, Ashish Hota Domitilla Del Vecchio
5:00 — 5:45 Ali Jadbabaie Gesualdo Scutari Ali Khanafer, Farzad Yousefian Cedric Langbort
6:45 — 9:15 reception + dinner

Tutorials by

  • Zhi-Quan (Tom) Luo Optimal Resource Allocation in Heterogeneous Wireless Networks
    TBA
  • Angelia Nedich Distributed Optimization in Networked Systems
    Recent advances in wired and wireless technology necessitate the development of theory, models and tools to cope with new challenges posed by large-scale networks and various problems arising in current and anticipated applications over such networks. In this talk, optimization problems and algorithms for distributed multi-agent networked systems will be discussed. The distributed nature of the problem is reflected in agents having their own local (private) information while they have a common goal to optimize the sum of their objectives through some limited information exchange. The inherent lack of a central coordinator is compensated through the use of network to communicate certain estimates and the use of appropriate local-aggregation schemes. The overall approach allows agents to achieve the desired optimization goal without sharing the explicit form of their locally known objective functions. However, the agents are willing to cooperate with each other locally to solve the problem by exchanging some estimates of relevant information. Distributed algorithms will be discussed for synchronous and asynchronous implementations together with their basic convergence properties.The problem of interest is a convex constrained minimization problem of a networked system. The agents are connected by a physical communication network allowing them to share some information locally with their neighbors in the network. The algorithms for solving this system problem obey the network connectivity structure and the privacy of agent’s objective functions. Both directed and undirected time-varying connectivity networks will be considered.
  • Stephen Morse Introduction to Flocking
    Over the past decade there has been growing in interest in distributed control problems of all types. Among these consensus and flocking problems stand out as two of the most widely studied. The aim of these lectures is to explain what these problems are and to discuss their solutions. Related concepts from spectral graph theory, nonhomogeneous Markov chain theory, and linear system theory will be covered.
  • Jeff Shamma Learning in Games and Distributed Architecture Control
    Recent years have witnessed significant interest in the area of distributed architecture control systems, with applications ranging from autonomous vehicle teams to communication networks to smart grid energy systems. The setup is a collection of decision making components with local information and limited communication interacting to balance a collective objective with local incentives. While game theory
    is well known for its traditional role as a modeling framework in social sciences, it is seeing growing interest as a design approach for distributed architecture control. Of particular interest is game theoretic learning, in which the focus shifts away from equilibrium solution concepts and towards the dynamics of how decision makers reach equilibrium. This talk presents a tutorial overview of game theoretic learning, from its origins as a “descriptive” tool for social systems to its “prescriptive” role as an approach to design on linear learning algorithms for distributed architecture control. The talk presents a sampling of prior and recent results in these areas and provides examples from distributed coordination, self assembly, and network formation.

Talks by

  • M. Ali Belabbas Stability of Sparse Systems: Theory and Algorithms

    Abstract: Many problems of practical and theoretical nature in control,
    biology and communications are described by an underlying graph encoding
    which interactions within a system are allowed. It is thus of great
    interest to know whether this underlying graph is dense enough to allow
    for stable dynamics (we call such graphs stable), as many applications
    taking place over this graph, e.g. distributed optimization, metabolic
    regulation, formation flight, etc. cannot run successfully if the graph
    is not stable. In this lecture, we review known results that characterize
    stable graphs and present algorithms to create them in polynomial time.

  • Carolyn Beck Graph Aggregation and Dynamic Clustering

    Abstract: In this talk we present a framework for solving a
    large class of dynamic clustering and aggregation problems.
    This framework provides the ability to identify natural clusters
    in an underlying dynamic data set, aggregate graph and Markov
    Chain models according to a variety of performance metrics, and
    allows us to address inherent trade-offs such as those between
    cluster resolution and computational cost. More specifically,
    we define the problem of minimizing an instantaneous coverage
    metric as an optimization problem using a Maximum Entropy Principle
    formulation, constructed specifically for the dynamic setting
    and incorporating control theoretic solutions.

  • Randy Berry Bargaining in Networks with Middlemen

    Abstract: In this paper, we consider a dynamic and decentralized market modeled
    by a non-cooperative networked bargaining game. Our goal is to study how
    the network structure of the market and the role of middlemen influence
    the market’s efficiency and fairness. We introduce the concept of limit
    stationary equilibrium in a general trading network and use it to analyze
    how endogenous delay emerges in trade and how surplus is shared between sellers and buyers.

  • Jared Bronski Topology and the Eigenvalues of the Laplacian on a Network

    Abstract: The Laplacian on a graph or network arises in many appled problems
    including problems of synchronization and convergence to consensus. In the
    case where the edge weights are all positive the spectral theory of the
    Laplacian is well understood: the eigenvalues are all non-positive, with
    the number of zero eigenvalues equal to the number of components of the network.
    In many applications, however, the edge weights may be of either sign,
    and the spectral theory is much less well developed. In this talk we present
    a theory for such signed Laplacians which gives best possible information
    on the signs of e eigenvalues of the matrix in terms of the topology of
    the graph. We close with some applications to social networks with
    positive and negative edges (likes and dislikes).

  • Domitilla Del Vecchio A Control Theoretic Framework for the Analysis and Design of Biological Networks

    ABSTRACT: Control theory has been instrumental for the analysis and design of a number of
    engineering systems, including aerospace and transportation systems, robotics and
    intelligent machines, manufacturing chains, electrical, power, and information networks.
    In the past several years, the ability of de novo creating biomolecular systems and of measuring
    key physical quantities has come to a point in which quantitative analysis and design of biological
    networks is now possible. While a modular approach to analyze and design networked dynamical systems
    has proven critical in most control theory applications, it is still subject of intense debate
    whether a modular approach is viable in biomolecular networks. In fact, these networks display
    context-dependent behavior, that is, the input/output dynamical properties of a module change
    once interconnected with the surrounding modules. In this talk, we present techniques based
    on nonlinear control and dynamical systems theory to quantify the extent of modularity in
    biomolecular networks and to establish modular analysis and design techniques. Specifically,
    we address the fundamental question of modularity by demonstrating that impedance-like effects
    are found in biomolecular systems, just like in many engineering systems. These effects, which
    we call retroactivity, can be severe and alter the behavior of a module upon interconnection,
    undermining modular behavior. Leveraging nonlinear perturbation theory, we show how one
    can determine interconnection rules that account for retroactivity by calculating equivalent
    network descriptions, just like Thevenin’s theorem does for electrical circuits. By merging
    disturbance rejection and singular perturbation techniques, we further provide an approach
    that exploits the distinctive structure of biomolecular networks to design biomolecular
    insulating amplifiers. These devices buffer systems from retroactivity and restore modular
    behavior, allowing a bottom-up approach to creating synthetic biological circuits.
    We provide experimental demonstrations of our theory and illustrate concrete biological
    realizations of insulating amplifiers in living cells.

  • Lee DeVille Emergent Metastability for Dynamical Systems on Networks

    Abstract: We consider stochastic dynamical systems defined on networks that
    exhibit the phenomenon of collective metastability—by this we mean network
    dynamics where none of the individual nodes’ dynamics are metastable, but the
    configuration is metastable in its collective behavior. We will concentrate
    on the case of SDE with small white noise for concreteness. We also present
    some specific results relating to stochastic perturbations of the Kuramoto
    system of coupled nonlinear oscillators. Along the way, we show that there
    is a non-standard spectral problem that appears in all of these
    calculations, and that the important features of this spectral problem
    is related to a certain homology group.

  • Alejandro Dominiquez-Garcia Decentralized Approaches to Control and Coordination of Distributed Energy Resources

    Abstract: On the distribution side of a power system, there exist
    many distributed energy resources (DERs) that can be potentially
    used to provide ancillary services to the grid they are connected to.
    An example is the utilization of plug-in-hybrid vehicles (PHEV)
    for providing active power for up and down regulation. Proper coordination
    and control of DERs is key for enabling their utilization for providing
    these ancillary services. One solution to this coordination and
    control problem can be achieved through a centralized control strategy
    where each DER is commanded from a central decision maker.
    An alternative solution—and the one this talk will focus on—is
    to distribute the decision-making process among the DERs.
    In order to achieve so, the DERs need to exchange information
    with a number of other “close-by” DERs, and subsequently making
    a local decision based on this available information.

    In the first part of the talk, we discuss the problem of optimally
    dispatching a set of distributed energy resources (DERs) without
    relying on a centralized decision maker. We consider a scenario where
    each DER can provide a certain resource (e.g., active or reactive power)
    at some cost (namely, quadratic in the amount of resource), with
    the additional constraint that the amount of resource that each DER provides
    is upper and lower bounded by its capacity limits. We propose a low-complexity
    iterative algorithm for DER optimal dispatch that relies, at each iteration,
    on simple computations using local information acquired through exchange
    of information with neighboring DERs. We show convergence of the proposed
    algorithm to the (unique) optimal solution of the DER dispatch problem.

    In the second part of the talk, we introduce a strategic decision-making
    framework for decentralized DER control. In this framework, there is a
    set of agents referred to as aggregators who interact with the wholesale
    electricity market, and through some market-clearing mechanism they are
    incentivized to provide (or consume) certain amount of energy over
    some period of time, which they will be compensated for.
    The objective is for the aggregator to design a pricing strategy for
    incentivizing DERs to modify their active (or reactive) power
    consumptions (or productions) so that they collectively provide the amount
    that the aggregator has targeted for. In order to make a decision,
    each DER uses the pricing information provided by the aggregator and
    some estimate of the average energy that neighboring DERs can provide,
    computed through some exchange of information among them. The focus of this
    talk is on the DER strategic decision-making process, which we cast as a game.
    In this context, we provide sufficient conditions on the aggregator’s pricing
    strategy under which this game has a unique Nash equilibrium. Then, we discuss
    a distributed iterative algorithm for information exchange between DERs
    and allows for DERs to seek this Nash equilibrium.

  • Ali Jadbabaie Information Aggregation and observational social learning networks

    Abstract

    In this talk, I will present a dynamic model of opinion formation in
    social networks when the information required for learning a parameter may
    not be at the disposal of any single agent and where individuals engage in
    communication with their neighbors in order to learn from their experiences.
    I will first consider the case when the agents incorporate their neighbors’
    beliefs and their private signals in a Bayesian way and show conditions
    under which learning occurs.

    Motivated by the practical difficulties of Bayesian updating of beliefs in
    a network setting, I will present a simple update mechanism in which instead
    of incorporating the views of their neighbors in a fully Bayesian manner,
    agents use a simple updating rule which linearly combines their personal
    experience and the views of their neighbors. I will show that, as long as
    individuals take their personal signals into account in a Bayesian way,
    repeated interactions will lead them to successfully aggregate information
    and learn the true parameter. This result holds in spite of the apparent
    naïveté of agents’ updating rule, the agents’ need for information from
    sources the existence of which they may not be aware of, worst prior views,
    and the assumption that no agent can tell whether her own views or those of
    her neighbors are more accurate.

    In the second part of the talk, I will characterize upper and lower bounds
    on the rate by which agents performing such an update learn the realized
    state, and show that the bounds can be tight. Furthermore I will show that
    in some cases, information structures that enable fastest aggregation
    satisfy a positive assortative matching property between agents’ centrality
    the exact opposite is true: for fastest aggregation, the least informed
    agents need to be the most central and there needs to be negative
    assortative matching between centrality and information value .

  • Kay Kirkpatrick Statistical mechanics of magnetic spin models on networks.

    Abstract: We consider statistical mechanical models of magnetism on graphs
    or networks, where the particles sit at the nodes and have spins in the
    sphere (the classical Heisenberg model) or the circle (the XY model).
    Recent work with Elizabeth Meckes sheds light on the qualitative behavior
    of the Heisenberg model on complete graphs with the number of vertices
    going to infinity, including detailed descriptions of the total spin
    through a second-order phase transition. I will also discuss work
    in progress on metastability in the XY model with and without disorder
    in the interactions between spins.

  • Negar Kiyavash Learning Causal Interactions: Going Beyond Linear Models

    Abstract: In this talk, we consider the relationship between Directed Information
    Graphs (DIGs) and Linear Dynamical Graphs (LDGs), both of which are graphical models
    where nodes represent scalar random processes. DIGs were proposed in information-theoretic
    context and can be constructed using directed information and represent the causal
    dynamics between processes in a stochastic system. LDGs appear in system identification
    context in control theory and capture causal dynamics but only in linear systems and
    they are learnt using Wiener filtering. We show that DIGs are generalization of the LDGs
    in the sense that when underlying system is linear systems they recover the same causal
    graph as LDGs.

  • Cedric Langbort Of (community-based) apps and men

    Abstract: One of the current challenges in the design and operation of large-scale `smart’ infrastructures
    is the synergetic integration of cyber, human, and physical components, in other words the principled
    engineering of “cyber-socio-physical” systems. (Mobile device-based) apps are widely seen as possible
    enablers of such integration, due to their ability to crowdsource activities, provide users with
    up-to-date information about current infrastructure state, reward their ‘good’ behavior, or publish
    recommendations. However, a number of questions regarding the recommender/decision maker(s) interface
    must be answered before this vision can be truly brought to fruition. In this talk, we investigate
    two recommender/decision maker interactions scenarios from a theoretical viewpoint. The former scenario
    is based on a simple model of payoff-based learning in games and addresses the question as to how
    the recommender can efficiently influence the decision makers’ choices. The latter is inspired by
    strategic information transmission/cheap talk games, and concerned with the possibility of users
    mis-performing crowd-based tasks for their own interest.

    This work is partly joint with Dan Work, Robin Guers (UIUC) and Farhad Farokhi (KTH).

  • Peter Marbach Online Social Networks: Research Challenges and Results

    Abstract: Online social networks have revolutionized the way we
    interact and share information over the Internet. Popular social
    networking applications include YouTube, Flickr, MySpace, Facebook,
    and Twitter, which support millions of active users. While being
    enormously popular, these applications only scratch the surface
    of what is possible to do, and there are tremendous opportunities
    in developing new, more advanced online social networking applications.
    Creating such applications poses new and fascinating research problems.
    One of major research challenges in this domain is to develop a formal
    understanding of online social networks both in terms of how online
    social networks are formed, and how they can be used to efficiently
    share and distribute information. In the talk, we will discuss research
    aiming at creating a mathematical foundation of online social networks
    that provides a formal understanding and framework for the design
    and analysis of algorithms for online social networking applications.
    The first part of the talk will present a broader research agenda
    for online social network. The second part will focus on recent
    theoretical results on network formation, as well as search and
    trend adoption in social networks. An interesting aspect of the
    results that we obtain is that they provide insight into why
    real-life social networks are so efficient. This is joint work
    with Stratis Ioannidis, Felix Wong, and Lilin Zhang.

  • Michael W. Mahoney Tree-like Structure in Large Social and Information Networks

    Abstract: Although large informatics graphs such as social and information
    networks are often thought of as having hierarchical or tree-like
    structure, this assumption is rarely tested. We have performed a
    detailed empirical analysis of the tree-like properties of realistic
    informatics graphs using two very different notions of tree-like-ness:
    Gromov’s $\delta$-hyperbolicity, which is a notion from geometric
    group theory that measures how tree-like a graph is in terms of
    its distance structure; and tree decompositions,
    structural graph theory tools which measure how tree-like a graph
    is in terms of its cut structure. Although realistic
    informatics graphs often do not have meaningful tree-like structure
    when viewed with respect to the simplest and most popular metrics,
    \emph{e.g.}, the value of $\delta$ or the treewidth, we conclude that
    many such graphs do have meaningful tree-like
    structure when viewed with respect to more refined metrics,
    \emph{e.g.}, a size-resolved notion of $\delta$ or a closer analysis
    of the tree decomposition. We also show that, although these two
    rigorous notions of tree-like-ness capture very different tree-like
    structures in a worst-case sense, for most realistic informatics
    graphs, they empirically identify surprisingly similar structure. We
    interpret this in terms of the recently-characterized “nested
    core-periphery” property of large informatics graphs; and based on
    this we show that the fast and scalable $k$-core heuristic can be used
    to identify tree-like structure in realistic informatics graphs.

  • Sewoong Oh Near-optimal Message-Passing Algorithm for Crowdsourcing.

    Abstract: Crowdsourcing systems, like Amazon Mechanical Turk, provide
    platforms where large-scale projects are broken into small tasks that
    are electronically distributed to numerous on-demand contributors.
    Because these low-paid workers can be unreliable, we need to devise
    schemes to increase confidence in our answers, typically by assigning
    each task multiple times and combining the answers in some way.
    I will present a rigorous treatment of this problem, and provide
    both an optimal task assignment scheme (using a random graph) and an
    optimal inference algorithm (based on low-rank matrix approximation
    and belief propagation) for that task assignment.

    We represent crowdsourcing systems using graphical models and
    address the problem of inference in this graphical model. Standard
    techniques like belief propagation are difficult to implement in
    practice because they require knowledge of a priori distribution
    of the problem parameters. Instead, we propose a message-passing
    algorithm that does not require any knowledge of the a priori
    distributions. We show that this algorithm achieves performance
    close to a minimax lower bound. To analyze the performance of this
    message-passing algorithm, we borrow techniques from statistical physics
    and coding theory such as phase transition, correlation decay, and
    density evolution. Precisely, we show that above a phase transition,
    the graphical model exhibits correlation decay property. Then, an
    analysis technique known as density evolution gives a precise description
    of the density (or distribution) of the messages. Time permitting,
    I will discuss an interesting connection between this message-passing
    algorithm and the singular vectors of sparse random matrices.

  • Lacra Pavel Towards Decentralized Optimization of Dynamic Multi-Agent Networks

    Abstract: Engineered networked systems are ubiquitous: power grids, communication
    networks and transportation systems are all examples of large-scale networks
    comprising many sub-systems that often interact in dynamic ways. Such networks can be regarded
    as multi-agent networks, where the agents could be the network nodes, channels, or users
    in a network, each with individual goals and a capacity to act. The agents’ goals (and actions)
    interfere and this means that there is need for coordination. However, centralized coordination
    is often impractical, or consumes excessive bandwidth and energy. The aim is to design nearest-neighbor
    interaction rules that achieve a desirable collective configuration, rely on locally available information,
    minimize superfluous communication and processing overhead, and are provably convergent.

    In this talk we review results developed by our group towards the design of such rules, either in a
    game-theoretic or in a consensus-optimization framework. Game-theoretic based algorithms are
    inherently decentralized, however, coupling constraints among agents’ actions are challenging to enforce.
    In the setup of consensus-optimization, a set of dynamic agents cooperate in locating
    the optimum of the sum of their individual, privately known objective functions. The agents are to
    dynamically adjust their actions, in response to their individual cost and the analogous decisions
    made by neighboring agents. Our approach relies on system theoretic methods: we model and
    abstract the agents’ interconnections as coupled dynamic systems, develop methods to analyze
    their dynamic behaviour and stability, and use these to design provably convergent rules.
    As applications we present two case-studies: (1) game theory-based power control in optical
    networks, and (2) consensus-based optimization for energy-efficient content delivery in
    information centric networks (ICN).

  • Maxim Raginsky Online Discrete Optimization in Social Networks with Inertia

    Abstract: Recently, there has been a great deal of interest in
    modeling and analysis of collective information processing by
    networks of locally interacting entities with limited information.
    On the theoretical front, this circle of problems has deep
    connections to ideas from game theory, statistical physics,
    and discrete probability. For example, recent work by Gamarnik,
    Goldberg and Weber studies distributed combinatorial optimization
    of a random locally decomposable objective function and shows that,
    under a certain correlation decay condition similar to
    Dobrushin’s uniqueness condition from statistical physics,
    it is possible to construct polynomial-time approximation schemes
    relying only on local information.

    In this talk based on joint work with Angelia Nedich, I will
    describe a model of online (i.e., real-time) discrete optimization
    by a social network consisting of agents that must choose actions
    to balance immediate time-varying costs against a desire to act
    according to some default myopic strategy. The costs are generated
    by a dynamic environment, and the agents lack ability or incentive
    to construct an a priori model of the environment’s evolution.
    As in the work of Gamarnik et al., the global cost of the network
    decomposes into a sum of individual and pairwise interaction terms,
    and at each time step each agent is informed only about its own
    cost and the pairwise costs in its immediate neighborhood.
    The overall objective is to minimize the worst-case regret,
    i.e., the difference between the cumulative real-time performance
    of the network and the best performance that could have been achieved
    in hindsight with full centralized knowledge. I will discuss
    an explicit strategy for the network based on the Glauber dynamics
    and show that it achieves favorable scaling of the regret in terms
    of problem parameters under a Dobrushin-type mixing condition.
    The proof relies on ideas from statistical physics, as well as
    on recent developments in the theory of Markov chains in metric
    spaces, specifically Yann Olivier’s notion of positive Ricci curvature
    of a Markov operator.

  • Ketan Salva Distributed Routing for Dynamical Network Flows

    Abstract: Dynamical network flows provide a useful abstraction
    for infrastructure systems such as transportation. We present
    recent results on new frameworks and control for dynamical
    network flows. We consider a system of ordinary differential
    equations (ODEs), one for every link of the network. Every ODE
    is a mass balance equation, where the inflow and the outflow
    terms depend on distributed routing policies at the nodes. We
    propose a novel class of routing policies and analyze the
    resulting stability and resilience properties of the network.
    The margin of resilience is measured as the minimum sum of the
    link-wise capacity losses that make the outflow from the
    network to be less than its inflow. When the routing policies
    can only control the splitting of incoming flow at nodes among
    outgoing links, then the margin of resilience is equal to its
    minimum node residual capacity, which is provably maximal under
    this distributed control architecture. When the routing
    policies can also control the incoming flow at the nodes, then
    the network achieves its maximal throughput as well as margin
    of resilience under any control architecture. The proofs of
    these results rely on a novel contraction principle for
    monotone dynamical systems under conservation law. These
    results facilitate analysis of generalizations of existing
    dynamic transportation network models and also hint at stronger
    performance guarantees for well-known distributed routing
    policies in data networks.

  • Anna Scaglione Gossip-based Gauss Newton Algorithms with Application to Power Grid State Estimation from Hybrid Measurements

    Abstract: This talk provides a decentralized gossip based solution for
    solving non-linear least square problems that is robust to sensing
    errors and random failures and requires only local knowledge of the
    physical and cyber networks. The method and the analysis is particularly
    suitable to decentralized state estimation from hybrid measurements in the
    power grid, which is a notoriously difficult non-convex problem in general.
    To solve it we propose a gossip based Gauss-Newton algorithm (GGN) that
    emulates the performance of the most popular centralized counterparts and
    discuss how to provide convergence guarantees based on the algorithm initial
    condition. We show that with the appropriate deployment of Phasor Measurement
    Units, one can co-optimize the convergence and accuracy of the Gauss Newton
    algorithm and show that an appropriate initialization as well as the use of
    a second-order method significantly outperform other first order methods
    proposed for decentralized non linear least square problems.

  • Gesualdo Scutari Parallel Optimization of Large-Scale Multi-Agent Systems

    Abstract: In this talk we propose a novel decomposition framework for the distributed optimization
    of general (stochastic) nonconvex sum-utility functions, subject to private and/or shared constraints.
    This class of problems arise naturally in the system design of many wireless multi-user interfering systems,
    both deterministic and stochastic. Our main contributions are: i) the development of the first class of
    (inexact) Jacobi best-response algorithms with provable convergence, where all the users simultaneously and
    iteratively solve a suitably convexified version of the original sum-utility optimization problem;
    ii) the derivation of a general dynamic pricing mechanism that provides a unified view of existing
    pricing schemes that are based, instead, on heuristics; and iii) a framework that can be easily
    particularized to well-known applications, giving rise to very efficient practical distributed algorithms
    that outperform existing ad-hoc methods proposed for very specific problems. Interestingly, our framework
    contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many
    block-coordinate descent schemes for convex functions.

  • Uday Shanbhag On the Solution of Stochastic Variational Problems with Imperfect Information

    Abstract: Traditionally, computation of solutions to variational problems has been studied
    under the premise that the associated parameters are known a priori. We consider the
    solution of a stochastic variational problems denoted by VI (X, F(.;\theta^*)) where \theta^* is unavailable.
    Instead, \theta^* may be obtained by solving a suitably defined convex learning problem.
    We present a coupled stochastic approximation scheme for simultaneously computing x^* and learning \theta^*.
    The presented schemes are shown to be equipped with almost sure convergence properties in regimes where
    the function under suitable monotonicity requirements. Rate estimates are provided in strongly monotone
    regimes and the degradation associated with learning is quantified. The findings are supported by a
    brief set of numerical results.

  • Shreyas Sundaram Robustness of Complex Networks with Implications for Consensus and Contagion

    Abstract: We consider averaging dynamics on networks that contain stubborn or malicious nodes.
    In particular, we study a class of dynamics where each normal node removes extreme values
    from its neighborhood before averaging the remaining values. We show that traditional graph
    metrics such as connectivity are no longer sufficient to characterize the behavior of such dynamics;
    instead, we show that a property termed r-robustness is required. This property is much stronger
    than other graph properties such as connectivity and minimum degree, in that one can construct
    graphs with high connectivity and minimum degree but low robustness. We investigate the robustness
    of common random graph models for complex networks (Erdos-Renyi, geometric random, and preferential
    attachment graphs), and show that the notions of connectivity and robustness coincide on these graphs:
    the properties share the same threshold function in Erdos-Renyi graphs, cannot be very different in
    1-d geometric random graphs, and are equivalent in preferential attachment graphs. This indicates
    that a variety of purely local diffusion dynamics (such as resilient consensus and contagion)
    will be effective at spreading information in such networks.

  • Choon Yik Tang Distributed Convex Optimization and Saddle/Fixed Point Computation

    Abstract: In many applications of networked systems, it is
    desirable to have distributed algorithms that enable agents in
    a network to cooperatively compute a global quantity, or solve
    an optimization problem, with only local interactions and
    without any centralized coordination and topology information.
    In this talk, I will present two sets of such algorithms, one
    for solving convex optimization problems, and the other for
    computing saddle and fixed points of functions. More
    specifically, I will first show that a Lyapunov function
    candidate, defined by the Bregman divergence of the local
    Lagrangians, may be used to construct a family of distributed
    convex optimization algorithms that includes continuous-time,
    gossip, and local broadcast versions, as well as a version
    where the iterations are greedily controlled. I will then show
    that this family of algorithms: (a) yields nonlinear networked
    dynamical systems that evolve on an invariant,
    zero-gradient-sum manifold; (b) converges asymptotically and,
    in some cases, exponentially with quantifiable convergence
    rates; and (c) may be viewed as a natural generalization of
    several well-known algorithms and results for distributed
    consensus, to distributed convex optimization. Finally, I will
    show that a simple feedback connection of two second-order
    consensus algorithms with problem-dependent nonlinearities is a
    distributed algorithm for computing saddle points of
    convex-concave functions and fixed points of composite
    monotonic functions.

  • Daniel Work TrafficTurk: Monitoring traffic during extreme congestion events

    Abstract: While GPS data from smartphones has grown rapidly over the last few
    years, in many regions road traffic estimates are generated from sparse data
    collected over long time horizons. Data sparsity leads to poor estimates of
    traffic during extreme congestion events, such as sporting events or natural
    disasters. Moreover, during these events, customized traffic control is
    achieved through human traffic controllers to manage atypical travel demands.
    Combined, these factors pose significant challenges for accurately estimating traffic.

    This talk will describe a new approach to monitor traffic with cell phones,
    known as TrafficTurk. Inspired by Amazon’s Mechanical Turk for crowd–sourcing human
    intelligence tasks, TrafficTurk enables temporary large-scale traffic sensor deployments
    to improve data coverage during extreme congestion events. TrafficTurk emulates
    the simple but surprisingly effective manual counting devices traffic movement counters
    used by most municipalities to periodically measure traffic counts at intersections,
    but with streaming data capabilities and cheap deployment costs. In addition to improving
    data coverage, TrafficTurk also enables traffic control strategies to be recovered by
    solving an inverse optimal control problem on the observed data. Experimental deployments
    in New York following Hurricane Sandy and a 100–node test in Urbana will be discussed.

Student Talks by

  • Mingyi Hong Base Station Activation and Linear Transceiver Design for Heterogeneous Networks: An ADMM Approach

    Abstract: In a densely deployed Heterogeneous network (HetNet), the number of pico/micro base stations (BS)
    can be comparable with the number of the users. To reduce the operational overhead of the HetNet, proper
    identification of the set of serving BSs becomes an important design issue. In this work, we show that
    by jointly optimizing the transceivers and determining the active set of BSs, high system resource
    utilization can be achieved by using only a small number of BSs. We provide formulations and efficient
    algorithms for such joint optimization problem, under the design criteria of minimization of the
    total power consumption at the BSs. Nonsmooth regularizers are introduced to facilitate the activation
    of the most appropriate BSs. The regularized power minimization problem is solved by a novel
    application of the Alternating Direction Methods of Multipliers (ADMM). The efficiency and the
    efficacy of the developed algorithms are demonstrated via extensive numerical simulations.

  • Ashish Hota Resource Sharing Games with Failure and Heterogeneous Loss Averse Players

    Abstract: Resource sharing games are strategic games in which players compete
    for a set of common resources. Players choose to invest (wealth, traffic, etc.)
    in a set of resources, and receive utility from each resource as a function of their
    investment strategy and other players strategies. We study a class of these games
    where a resource might experience failure and fail to return any utility to the players
    investing in it. This results in uncertainty for the players. We analyze the setting
    where players have different loss aversion attitudes. We show the existence and
    uniqueness of the pure Nash equilibrium (PNE) of this game and characterize the
    properties of the PNE and the players’ strategies in relation to their degrees of
    loss aversion.

  • Ali Khanafer Virus Spread in Networks: Optimal Control and Stabilization

    Abstract: We study the problem of optimal control of virus spread over
    a network, where the designer is capable of modifying the curing rates of
    the nodes dynamically. We investigate the switching behavior of the
    optimal control, and propose an approximation method which yields a
    class of low complexity sub-optimal controllers. Further, we
    investigate the stabilization problem in the presence of control
    failure. We also propose a general dynamical model to capture the
    interaction of nodes in an infected network based on a network-wide
    noncooperative game. We show that our model subsumes the state-of-the
    art dynamical descriptions of network epidemics and enjoys simple
    convergence conditions.

  • Farzad Yousefian

    Abstract:

Registration is free but required - here.

 

Accommodation:

We have reserved a block of rooms at the Hampton Inn, just next to the conference site.

Additional rooms are expected to be available at the Illini Union located on the campus of the University.

Here are links to some further hotels in the area: Hawthorn Suites, Hilton Garden Inn.

IMSE is supported by the Vice Chancellor for Research, the College of Liberal Arts and Sciences, and the College of Engineering at the University of Illinois at Urbana-Champaign.