Colloquium

Projected gradient descent (PGD), and its close variants, are often considered the methods of choice for solving a large variety of machine learning optimization problems, including empirical risk minimization, statistical learning, and online convex optimization. This is not surprising, since PGD is often optimal in a very appealing information-theoretic sense. However, for many problems PGD is infeasible both in theory and practice since each step requires to compute an orthogonal projection onto the feasible set.

Algorithms and the Internet are revolutionizing how society allocates its resources. Examples range from wireless spectrum and electricity to online advertising and carpooling opportunities. A fundamental question is how to allocate such resources efficiently by designing robust computational markets.

The central result in game theory due to Nash ensures that every finite strategic game has an equilibrium. However, all the known proofs of the Nash theorem are non-constructive and, as of today, there is no polynomial time algorithm for finding a Nash equilibrium. Some recent works have tried to explain this status by showing lower bounds for finding Nash equilibria under strong cryptographic assumptions such as the notion of secure code obfuscation.

With the proliferation of multi-core processors, shared-memory concurrent programming has become increasingly important. Nevertheless, despite decades of research, there are still no adequate answers to the following fundamental questions:

Protein-RNA binding, mediated through both RNA sequence and structure, plays a vital role in many cell processes, including neurodegenerative-diseases. Modeling the sequence and structure binding preference of an RNA-binding protein is a key computational challenge. Accurate models will enable prediction of new interactions and better understanding of the binding mechanism. In addition, designing compact and efficient sequence libraries to experimentally measure these interactions is necessary to discover novel binding preferences.

Recommendation systems are ubiquitous in our day to day lives. This domain lies at the intersection of academic and industry interests, with examples of fruitful collaborations abounding. In this talk I will motivate the field of automated recommendation systems and give short introduction to common approaches including content-based and Matrix Factorization for collaborative filtering. I will also discuss evaluation methods for recommendation algorithm results.

In this talk I will demonstrate deep links between a core information-theoretic concept and features of genetic data. In essence, long stretches of genetic variants from a population may be captured as ‘typical sequences’ of a nonstationary source. I will introduce the concepts of typical genotypes, population entropy rate and mutual typicality, and their relation to the asymptotic equipartition property.

Individual genome sequences hold invaluable information about our evolutionary past, and recent advances in sequencing technology has made this type of data increasingly available. One of the greatest leaps made in the past ten years has been in our ability to sequence DNA from bones that are tens of thousands of years old. This ability has allowed researchers for the first time to directly study extinct human groups such as the mysterious Neanderthals.

We present a method for the approximation and learning of arbitrary continuous distance functions and semimetrics. Previous work have been limited to Euclidean metrics or other families of metrics (e.g., the Earth Mover's Distance). One usage of this method is to learn a function that given two objects returns whether they match (e.g., descriptor matching learning). Another usage is directly learning a distance function (e.g., perceptual color difference learning).