Asymptotics of Large-Scale Interacting Networks (13w5136)

Arriving Sunday, February 24 and departing Friday March 1, 2013

Organizers

Bruce Hajek (University of Illinois at Urbana-Champaign)
Peter Marbach (University of Toronto)
Sujay Sanghavi (University of Texas at Austin - Electrical Engineering)

Objectives

The primary objectives of the workshop are to:


  1. Bring together experts on inference, optimization, and control in interacting networks to explore new research directions and approaches in the emerging research area of asymptotic analysis of interacting networks.

  2. Provide outstanding junior researchers an opportunity to learn about recent results and important open problems in this field, as well as to present their own research.

  3. Serve as a catalyst for new research directions and approaches in the emerging research area of asymptotic analysis of interacting networks -- particularly approaches spanning mathematics, applied probability, computer science, economics, and control and information theory.


Specific mathematical areas the workshop focuses on are:

  1. Exploration of the strengths and limitations of methods of statistical physics and interacting particle systems: A useful starting point for methods of statistical physics is mean field analysis, in which all agents mutually interact in a symmetry way, as in the theory of spin glasses. Mean field analysis has long been used within statistical physics, and in many scenarios it has sound mathematical justification, such as in the theory of propagation of chaos [Sznitman (1991)]. cite{Sznitman91}. Mean field analysis is seeing a renaissance of late, stimulated in part by its use in game theory [Lasry and Lions (2007)]. cite{lasry2007mfg}. Foundational questions within mean field game theory include existence, uniqueness, and limit questions, not only for statistical equilibria, but also for game-theoretic equilibria, in which individual agents attempt to maximize their own objective functions which include interactions with others. Statistical physics methods beyond mean field theory are relevant for incorporating the effect of local connectivity (i.e. graph topology) in the study of interactive networks. Recently work on the development of network coordination algorithms based on steering the equilibrium distribution of a network has shown promise (see [Jiang et al. (2011)]), cite{Jiangetal11}), but the difficulty of obtaining optimal coordination may increase dramatically with the range of statistical correlation (see [Gamarnik, Goldberg, and Weber (2009)]). cite{GamarnikGoldbergWeber09}). There is a folk theorem that it is intrinsically hard to learn the graph structure of Markov networks without fast correlation decay.

  2. Inverse problems in networks: Statistical inverse problems are those where a model or model instance has to be inferred from data. Network inverse problems are those where we need to infer structural or operational characteristics of the network from processes, such as data flow or user actions, executing within it. Such problems are of increasing importance because (a) the scale, and lack of centralized planning, of engineered networks like the Internet means that we need to infer its properties and structure, (e.g. inferring graph structure from delays [Anandkumer et al. (2011)]) cite{anahaskel11})

    and (b) network phenomena are increasingly the result of an interaction between human beings and engineered systems -- so that even if we had full knowledge of the latter, we would still need to draw inferences about the former [Shah and Zaman (2011)]. \cite{shazam11}.



    Network inverse problems involve a completely new interplay between combinatorics, statistics, game theory and engineering. For example, game theory models the actions of local agents, from which a graph with special properties (e.g. degree bounds, clustering coefficients etc.) needs to be inferred, typically from a limited number of samples. While techniques and ideas from these fields have been integrated before in ``forward" network problems (i.e. those where we want to make predictions about processes given a network model), inverse problems motivate completely new questions that have not been investigated in forward contexts.

  3. Markov random fields (MRF) and high-dimensional statistics: MRFs are graphical representations of statistical dependencies among variables: in the Markov graph of a probability distribution, every variable is a node, and the neighbors of a variable are the other variables that it directly depends on (i.e. conditioned on them, it is independent of the rest of the variables)

    [Lauritzen (1996)]. cite{lau_book}. MRFs naturally encode locality among random variables, and they provide a classical formalism that has proven useful in physics, statistics, and machine learning.

    The workshop will focus on several interesting recent developments that foretell an ever-widening intellectual exchange between the theory of MRFs (which is rooted in statistics), and large-scale complex networks. For example, MRFs have advanced the state of the art in network (a) decision making: Belief propagation, a classic MRF method, has been used to achieve distributed resource allocation in large-scale wireless networks [Bayati, Shah, and Sharma (2008)], cite{bayshasha08}, and (b) inference: methods to learn MRF structure from samples have now been used to infer the structure of the Internet from measurements.



    Equally crucial, network settings have shed fundamental new insights about classical methods in MRFs. For example, the application of belief propagation to weighted matching and independent set problems -- inspired by network applications -- led to the first formal proof of the connection between belief propagation and linear programming, for graphs with cycles. The workshop will also include speakers working on high-dimensional statistical problems in networks. This refers to settings where the number of variables to estimate exceeds the number of samples required to do the same.



Approximate Workshop Format: Developing a fundamental understanding of how information structure impacts networks, and its relation to efficient algorithms, requires a wide variety of technical tools that currently reside in several communities with limited overlap in terms of a joint venue to present mutually relevant results: probability, optimization, combinatorics, computer science, electrical engineering. Thus, we envisage a format where

  • The start of the workshop will feature longer-format tutorial style talks that crisply introduce the relevant ideas in each field. So, for example, there would be one talk covering convergence of Markov chains on graphs, another on mean field games, a third on high-dimensional statistics on Markov networks. The emphasis for these will be on accessible introduction of key ideas that have underpinned much recent work in their respective domains.

  • Dissemination of recent research via a series of half-hour talks. These will be able to build on the tutorials, and bring the entire audience up to speed with the latest frontier (whereas the tutorial would be more of a foundation).
  • All speakers will be asked to emphasize open problems related to their respective talks. For example, each half-hour talk should devote five minutes to an open problem/direction, and a discussion of what is the key challenge therein.
  • The workshop will encourage and provide time for participants to form study groups to have focused discussions on research problems and directions that arise during the workshop.





Workshop Participants: The workshop brings together researchers with diverse backgrounds, covering disciplines such such as mathematics, applied probability, computer science, economics, and control and information theory, with mathematical expertise including probability theory, graph theory, statistical physics, game theory, and control and information theory. We aim to include researchers from both universities and industrial research labs, as well as from different countries. Of the 42 slots for workshop participants, we propose to allocate six slots to outstanding researchers within two years (plus or minus) of their Ph. D., with selection based on evaluation of applications. The selection criteria will include accomplishments in related research.

Bibliography



  • Sznitman91 A.~S. Sznitman (1991) newblock Topics in propagation of chaos. newblock Springer.
  • lasry2007mfg J.M. Lasry and P.L. Lions (2007) newblock Mean field games. newblock Japanese Journal of Mathematics, 2(1):229--260.
  • Jiangetal11 L.~Jiang, M.~Leconte, R.~Srikant J.~Ni, and J.~Walrand (2011) newblock Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling. newblock To appear.
  • GamarnikGoldbergWeber09 D.~Gamarnik, D.~Goldberg, and T.~Weber (2009) newblock Correlation decay in random decision networks. newblock Available on arXiv:0912.0338v1.
  • anahaskel11 A. Anandkumar, A. Hassidim, and J. Kelner (2011) ``Topology Discovery of Sparse Random Graphs with Few Participants,” Proc. of ACM SIGMETRICS, (San Jose, USA)
  • shazam11 D. Shah and T. Zaman (2001) ``Rumors in a network: Who's the culprit?" IEEE Transactions on Information Theory, vol. 57, No. 8, pp. 5163-5181.
  • lau_book S.~Lauritzen, (1996) Graphical models. Oxford University Press.
  • bayshasha08 M.~Bayati, D.~Shah, and M.~Sharma (2008) ``Max-product for maximum weight matching: Convergence, correctness, and Lp duality,'' Information Theory, IEEE Transactions on, vol.~54, no.~3, pp. 1241--1251.