Learning in Networks: Performance Limits and Algorithms (20w5212)


(University of Illinois)

Yihong Wu (Yale University)

Jiaming Xu (Duke University)


The Casa Matemática Oaxaca (CMO) will host the "Learning in Networks: Performance Limits and Algorithms" workshop in Oaxaca, from November 15 to November 20, 2020.

The focus of the workshop is on statistical learning, algorithms, information and computational limits, in large-scale networks. The overall objective of the workshop is to develop a better understanding of the information theoretic and computational barriers to making significant inferences from large-scale network data. The topics are organized into three interrelated areas, ranging from inference problems for single graphs, to inference involving two graphs, to classification of graphs from general families.

Inference problems to be addressed for single graphs include the detection of densely connected communities within dynamic graphs, and detection of other structures including Hamiltonian paths and bipartite matchings, with applications to seriation of DNA and particle tracking in physics experiments. A prototypical inference problem involving two graphs is the graph matching problem, in which two noisy versions of a parent graph are presented and the problem is to line up the vertices of the two graphs. The algorithms and analysis involve an interesting interplay of combinatorial algorithms and stochastic analysis. Another prototypical problem for graph classification to be addressed at the workshop is to estimate the density of network motifs or to estimate the number of connected components of a graph based on sampled neighborhoods.

Research on learning in networks: performance limits and algorithms combines techniques from probability theory, graph theory and combinatorics, statistical physics, optimization, and information theory. The researchers attending the workshop will span the disciplines of mathematics, applied probability, computer science, operation research, information theory, and statistics.

The workshop brings together the leading researchers in this area to discuss recent results and open problems, as well as to explore new mathematical techniques and models to study from network data. Besides tutorials and research presentations, the workshop will encourage and provide time for attendees to form study groups to have focused discussions on research problems and directions that arise during the workshop. We anticipate around ten of the participants will be graduate students and postdoctoral fellows interested in statistical learning in large scale networks.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).