Looking Ahead: Machine Learning and Pseudorandomness

by Luca Trevisan

In the coming spring semester, the Simons Institute will host a program on the Foundations of Machine Learning, and a program on Pseudorandomness.

The recent success of machine learning techniques in a variety of application domains, from image recognition to natural language processing, has been outstanding, but a rigorous understanding of the algorithms and techniques involved in these breakthroughs remains to be fully articulated.

The program on Foundations of Machine Learning, organized by Sanjeev Arora, Nina Balcan, Peter Bartlett, Sanjoy Dasgupta, Sham Kakade and Santosh Vempala, will bring together theoreticians and practitioners with the goal of furthering our understanding of models and algorithms involved in machine learning.

One area of interest for the program, and the subject of the first workshop, is interactive learning, a machine learning paradigm in which the learner is not just given a set of labeled data to learn from, but instead, interacts with a domain expert. This modality of learning includes the well-studied model of active learning, in which the learning algorithm generates data and asks for labels, as well as emerging areas such as explanation-based learning and crowdsourcing.

Another area of interest is representation learning, in which one is interested in algorithms that discover salient features and structure in the data, and in good ways to encode such features and structure. Autoencoders based on deep networks, and representations of words as points in a high-dimensional space used in NLP, are two examples of empirically successful applications of representation learning for which we are lacking a rigorous explanation. The second workshop of the program will be devoted to representation learning.

A third challenge for the program is to bridge the gap between empirical results and rigorous analysis in the design of algorithms for machine learning applications. Optimization algorithms used to train machine-learning models, algorithms to reason statistically about data, as well as clustering algorithms often vastly outperform their worst-case analysis. Such algorithms are known to provably work well in certain restricted models, but those rigorous results do not explain the results seen in practice, because those restricted models often fail to model features of data sets on which algorithms empirically work well.

The theory of pseudorandomness is concerned with objects that have many of the interesting properties of random objects, even though they either have a deterministic description, or can be generated using much less randomness than would be required to generate truly random objects. The program on Pseudorandomness, organized by Jacob Fox, Ben Green, Russell Impagliazzo, David Zuckerman, Julia Wolf and me, is coming at a time of significant breakthroughs in the construction of pseudorandom objects, especially randomness extractors and expander graphs, and of developing connections between notions of pseudorandomness developed in analytic number theory and additive combinatorics, and notions of pseudorandomness developed in theoretical computer science.

In number theory, one is interested in properties that the set of prime numbers has in common with a randomly generated set of integers of the same density: probabilistic models of the primes have motivated and supported a number of conjectures about patterns in the primes, many of them still open, and have inspired proof techniques that rigorously capture the “random-like” properties of the primes, most recently by understanding the Gowers norms of functions related to the indicator function of the primes.

In combinatorics, one is interested in expander graphs, which are sparse graphs with several of the useful properties of random sparse graphs. In theoretical computer science and cryptography, there is interest in constructing randomness extractors, which are procedures that convert a sample from an unknown random source of unknown entropy into a stream of unbiased random bits; a few variants of randomness extractors are of interest, and, depending on their type, randomness extractors solve the privacy amplification problem in cryptography, and can be used to construct Ramsey graphs and graphs with very strong pseudorandomness properties.

Of common interest to combinatorics, number theory and theoretical computer science are results exploiting the structure-versus-randomness dichotomy, a phenomenon that can be rigorously quantified, according to which arbitrary objects can be approximated by a structured combination of pseudorandom components. The Green-Tao theorem that the primes contain arbitrarily long arithmetic progressions, Szemerédi’s regularity lemma and its applications to combinatorics, property testing, and graph limits, and properties of the notion of pseudoentropy, with applications to cryptography, are all part of this broad agenda.

Pseudorandom generators with rigorous guarantees are a fundamental tool both in cryptography and in complexity theory. In complexity theory, they are at the heart of the theory of derandomization, which is concerned with whether all randomized algorithms can be efficiently simulated deterministically.

The Pseudorandomness program will bring to the Simons Institute an unusual combination of pure mathematicians and theoretical computer scientists, and it will happen as the same time as a program on analytic number theory at neighboring MSRI, which will bring to Berkeley several other number theorists with related interests. The program will be an opportunity for the experts in residence to digest recent breakthroughs in the construction of randomness extractors and in existence proofs of expander graphs. The program will be an opportunity to push toward improved pseudorandom generators for space-bounded algorithms, a problem that has been open for more than 25 years and is a core open question in complexity theory. Finally, the program will be an opportunity for theoretical computer scientists and pure mathematicians to learn from each other about the latest development of randomness versus structure type of results in cryptography and additive combinatorics.

Related Articles

• Letter from the Director, Fall 2016
• “All sorts of surprising connections”: Conversations with Research Fellows Marco Molinaro, Joanna Ochremiak, Matt Weinberg and Christoph Berkholz
• Simons Institute Launches Journalist-in-Residence Program
• From the Inside: Logical Structures in Computation
• From the Inside: Algorithms and Uncertainty
• Research Vignette: Network Biology Meets Cancer Genomics
• Research Vignette: Phase Transitions in Random Constraint Satisfaction Problems