Colloquium

Big data analytics is a current title given to the process of analyzing large amounts of recorded information, for the purpose of discovering valuable insights from the data. It is widely used in the business world as well as in scientific research. The methodologies used for analysis combine statistical models or non-probabilistic models with iterative learning algorithms. The output would typically be a predictive rule that is based on information from many features, and can help anticipating an outcome for newly coming observations.

It is no secret that online companies, hospitals, credit-card companies and governments hold massive datasets composed of our personal and private details. Information from such datasets is often released using some privacy preserving heuristics, which have been repeatedly shown to fail. In contrast, differentially private algorithms release information about a given dataset while satisfying a powerful and mathematical guarantee of privacy.

Data is now collected and processed on tremendous scale. Unfortunately, in several crucial applications it is not possible to leverage the full extent of collected information, e.g. when attempting to identify global properties across sensitive data sets held by agent(s) who are unable or unwilling to share the information.

A common approach to statistical learning on big data is to randomly split it among m machines and calculate the parameter of interest by averaging their m individual estimates.

Focusing on empirical risk minimization, or equivalently M-estimation, we study the statistical error incurred by this strategy. We consider two asymptotic settings: one where the number of samples per machine $n\rightarrow\infty$ but the number of parameters $p$ is fixed, and a second high-dimensional regime where both $p,n\rightarrow\infty$ with $p/n\rightarrow\kappa$.

Macromolecular assemblies, cellular machines comprised of many individual proteins, perform many essential tasks in the cell. To understand how these assemblies function and to develop strategies to modulate them for therapeutic purposes, we need to describe the structure, dynamics and interactions of the underlying proteins. These large assemblies, however, often elude structural characterization by the conventional techniques of X-ray crystallography or NMR spectroscopy.

Graph matching is one of the most well-studied problems in combinatorial optimization, with applications ranging from scheduling and object recognition to numerical analysis and computational chemistry. Nevertheless, until recently very little was unknown about this problem in real-life {dynamic networks}, which aim to model the constantly changing physical world. 

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. For a collection of simultaneously transmitting stations, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly.

In multi-agent interactions, each agent often faces uncertainty over the incentives and the behavior of the other agents. The traditional approach assumes that agents each maximize their expected utility w.r.t. some common prior distribution. However in most real-world scenarios agents have no way to accurately or even approximately know this distribution. Moreover, numerous psychological experiments have demonstrated that human decision makers fail even at fairly simple tasks involving probabilistic reasoning, and are prone to cognitive biases such as risk-aversion and loss-aversion.

I will describe an alternative, non-probabilistic, model for representing players' uncertainty in games, inspired by artificial intelligence and bounded rationality approaches.

While the model is quite general, I will demonstrate how it applies for preference aggregation mechanisms (voting), overcoming many shortcomings of previous theories. My main result is that the behavior of bounded-rational agents boils down to a simple and natural dynamics, which is guaranteed to converge to an equilibrium. Extensive simulations show that the resulting equilibria replicate known phenomena from real-world voting.

Finally, I will show how key components of this approach can be extracted and applied to very different settings, including online scheduling on Doodle and routing in networks with uncertain congestion.

The talk is based on published and unpublished work with Omer Lev, David Parkes, Jeffrey S. Rosenschein, and James Zou.

I will discuss two recent works:

1. Long running transfers in wide area networks are usually time critical, as delays might impact service quality, affect customer revenue, and increase costs incurred by waste of resources. Current traffic engineering systems fall short as they do not provide pre-facto guarantees on such long running transfers. I will present an online traffic engineering system that provides pre-facto guarantees while maximizing both fairness and network utility. The system is based on theoretical algorithmic techniques for solving packing and covering linear programs, and can quickly handle an evolving linear program containing up to millions of variables and constraints.
2. Combinatorial discrepancy is a basic problem in computer science and combinatorics, that has applications in diverse areas such as: computational geometry, complexity theory, Monte-Carlo simulation, number theory and more. Given a family of subsets $S_1,\ldots,S_n$ of a universe $N$ of size $n$, the goal is to color the elements of $N$ by one of two colors $\{-1,+1\}$ such that each set is colored as evenly as possible. Spencer's well known theorem asserts that this can be done while keeping the absolute value of the sum of the colors of every set to be $O(\sqrt{n})$. Known proofs, algorithmic and existential, recursively construct "partial colorings", which assign colors only to half the universe $N$. Unfortunately, this approach fails to provide tight guarantees to other important discrepancy problem, e.g., the Beck-Fiala and Koml\'os conjectures. Therefore, it has been an open question to find new techniques that avoid partial colorings. In this work I will present the first algorithm that directly computes a full coloring. The algorithm is based on a geometric perspective and in its core is the analysis of ellipsoids contained in polytopes.

Conversational interfaces and virtual assistants such as Apple's Siri, Google Now, and Facebook Graph Search, have led to a rising interest in systems that can translate natural language commands and questions to formal logical forms (like SQL queries) that can be executed against a knowledge base.  A major challenge has been to scale these systems, known as semantic parsers, to large knowledge bases. In this talk, I will describe novel algorithms for large scale semantic parsing.