Past Seminars

Abstract

Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science and statistical physics. While there has been success evidencing these gaps from the failure of restricted classes of algorithms, progress towards a more traditional reduction-based approach to computational complexity in statistical inference has been limited. Existing reductions have largely been confined to inference problems with similar structure -- primarily mapping among problems representable as a sparse submatrix signal plus a noise matrix, which are similar to the common starting point of planted clique.

In this talk I will describe how a slight generalization of the planted clique conjecture -- secret leakage planted clique -- enables the success of a variety of new average-case reduction techniques, yielding a web of reductions among problems with very different structures. Using variants of the planted clique conjecture for specific forms of secret leakage planted clique, we deduce tight statistical-computational tradeoffs for a diverse range of problems including robust sparse mean estimation, mixtures of sparse linear regressions, robust sparse linear regression, tensor PCA, variants of dense k-block stochastic block models, negatively correlated sparse PCA, semirandom planted dense subgraph, detection in hidden partition models and a universality principle for learning sparse mixtures. Joint work with Matthew Brennan.

Bio

Abstract

The Random Number Partitioning Problem (RNPP) is the problem of splitting a set of items with random i.i.d. weights into two groups so that to minimize the absolute difference of the sums of weights in each group. A randomized version of a classical NP-hard problem, it emerged recently in applications to randomized control studies, where the goal is to split the participants into the treated and controlled groups, so that the sums of attributes of the participants in two groups are as close to each other as possible. The problem exhibits a statistical vs computational gap, exhibited by many other optimization problems in random structures. In particular, while the optimal objective value for the case of standard normal weights is of the order 2^(-n), as shown by Karmarkar, Karp, Lueker and Odlyzko in 1986, the best value achievable by known polynomial time algorithms is only 2^(-\log^2 n), corresponding to the Largest Differences Algorithm (LDM), as shown by Yakir in 1996, and has not been improved ever since.

We study the origin of this gap from the solution space landscape point of view and establish that the model exhibits the Overlap Gap Property (OGP) for objective value up to 2^(-O(\sqrt(n \log n))). Loosely speaking the OGP says that pairs of near optimal solutions are either sufficiently close to each other or sufficiently far from each other. We establish that the OGP is an obstruction to any stable algorithm, namely algorithm which does not change its output significantly upon a small perturbation of the input. We verify the stability of the LDM algorithm by simulations, and conjecture that it does exhibit the stability. The proof of the OGP is obtained by the second moment method, and the proof of the algorithmic obstruction relies on the Ramsey theory from the extremal combinatorics, which is of independent interest.

Joint work with Eren Kizildag (MIT)

Bio

Abstract

Quantum information processing is at the cusp of having a significant impact on technology and society in the form of providing unbreakable security, ultra-high-precision distributed sensing with applications to metrology and science discovery (e.g., LIGO), and polynomial speeds up on search with implications to big data. Most of these applications are enabled by high-rate distributed shared entanglement between pairs and groups of users. A critical missing component that prevents crossing this threshold is a distributed infrastructure in the form of a world-wide “Quantum Internet” to enable this. This motivates our study of quantum networks, namely what is the right architecture and how should it be operated, i.e., route multiple quantum information flows, and dynamically allocate resources fairly.

In this talk we review a specific entanglement-based quantum network architecture and present opportunities and challenges related to resource sharing among multiple parties of users. In particular, we focus on issues related to resource allocation based on global/local state information and the benefits of path diversity. We also evaluate the performance of the simplest network, an entanglement-based quantum switch serving a population of users. We end the talk with a list of open problems.

Bio

Abstract

Consider a set of n agents, each of whom has a single message to convey to all other agents. The messages are all of the same length. Time is divided into rounds, and during each round, each agent may broadcast a single message. Agents are represented as nodes of a directed communication graph, and a broadcast is received error-free by all (out)-neighbours of the broadcasting node. The problem is to minimise the number of rounds until all agents have received all messages.

This is known as the broadcasting problem, and various versions of it have been studied. In our version, the communication graph is a dense directed Erdos-Renyi random graph G(n,p), and we seek simply decentralised gossip algorithms. We consider two algorithms, random relaying and random linear network coding. We consider a sequence of graphs with p fixed and n tending to infinity. Our main results are that random relaying requires Theta(log n) rounds, whereas random linear network coding requires only a constant number of rounds.

Bio

Abstract

As data collection becomes ubiquitous, understanding the potential benefits as well as the risks posed by the availability of such large amount of data becomes more pressing. Identifying how data from different sources relate to each other, could allow to merge and augment data. On the positive side, this could help for instance in deducting functionality of proteins by comparing protein interaction networks of different species. On the negative side, such alignment could cause unintended exposure of confidential information. A famous case of such breach occurred when customer data from the anonymous Netflix Prize database was revealed through alignment with public IMDB profiles.

In this talk we present information-theoretic results on database alignment, showing how the size of databases and the correlation between their elements determines the success of alignment. Database alignment is closely related to equally interesting problem of network alignment, a generalization of the graph isomorphism problem.

Bio

Abstract

We introduce threshold growth in the classical threshold contagion model, or equivalently a network of Cramer-Lundberg processes in which nodes have downward jumps when there is a failure of a neighboring node. Choosing the configuration model as underlying graph, we prove fluid limits for the baseline model, as well as extensions to the directed case, state-dependent inter-arrival times and the case of growth driven by upward jumps. We obtain explicit ruin probabilities for the nodes according to their characteristics: initial threshold and in- (and out-) degree.

We then allow nodes to choose their connectivity by trading off link benefits and contagion risk. We define a rational equilibrium concept in which nodes choose their connectivity according to an expected failure probability of any given link, and then impose the condition that the expected failure probability coincides with the actual failure probability under the optimal connectivity.

We show existence of an asymptotic equilibrium as well as convergence of the sequence of equilibria on the finite networks. In particular, our results show that systems with higher overall growth may have higher failure probability in equilibrium (talk based on work with Hamed Amini and Agnes Sulem).

Bio

Abstract

Much of social choice theory focuses on voting without taking into account the deliberation and negotiation that goes into making a group decision. We will describe several deliberation mechanisms where a group comes to a decision by a series of small-group deliberations among randomly chosen agents. We will show that upon convergence (to either a single point or a stationary distribution), this process results in provably good decisions on median spaces, which includes the cases where the decisions to be made can be represented on a line, a tree, or in any high-dimensional space equipped with the l1 norm. In addition to showing that this approach results in provably good decisions, we will also give bounds on the convergence time, as well as show that these deliberation mechanisms are strategy-proof.

We will conclude with a description of our participatory budgeting platform, and show that the above approach can lead to provable bounds for the participatory budgeting problem even in the presence of project interactions.

This represents old work with David Lee, Brandon Fain, Kamesh Munagala, and Sukolsak Sakshuwong as well as new results with Mohak Goyal, Sukolsak Sakshuwong, and Kamesh Munagala.

Bio

Abstract

Blockchains have become an important tool for maintaining distributed ledgers among mutually untrusting parties. As the systems that use these ledgers (e.g., cryptocurrencies) grow in popularity, it is becoming increasingly important to ensure their robustness along multiple axes, such as performance, security, privacy, and fairness. To date, most of the literature on these topics has tackled them at the application layer. In this talk, we will instead discuss the role that communication networks play in designing robust blockchain systems. We will illustrate this point through three case studies focusing on performance, privacy, and fairness. In each of these case studies, we show how careful modeling, analysis, and design of underlying communication networks can lead to improved robustness at other layers. These design and analysis challenges introduce new problem formulations combining elements of graph algorithms, random processes, and distributed systems.

Bio

Abstract

The future of machine learning lies in moving both data collection as well as model training to the edge. The emerging area of federated learning seeks to achieve this goal by orchestrating distributed model training using a large number of resource-constrained mobile devices that collect data from their environment. Due to limited communication capabilities as well as privacy concerns, the data collected by these devices cannot be sent to the cloud for centralized processing. Instead, the nodes perform local training updates and only send the resulting model to the cloud. A key aspect that sets federated learning apart from data-center-based distributed training is the inherent heterogeneity in data and local computation at the edge clients. In this talk, I will present our recent work on tackling computational heterogeneity in federated optimization, firstly in terms of heterogeneous local updates made by the edge clients, and secondly in terms of intermittent client availability.

Bio