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:
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.
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 NetworksTBA
- Angelia Nedich Distributed Optimization in Networked SystemsRecent 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 FlockingOver 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 ControlRecent 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
AbstractIn 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.