Computer Sciences Colloquium - Overcoming Intractability in Learning

Abstract: 

Machine learning has recently been revolutionized by the introduction of Deep Neural Networks. However, from a theoretical viewpoint these methods are still poorly understood. Indeed the key challenge in Machine Learning today is to derive rigorous results for optimization and generalization in deep learning. In this talk I will present several tractable approaches to training neural networks. At the second part I will discuss a new sequential algorithm for decision making that can take into account metric structure in the action space and avoids erratic behavior which often makes MAB algorithm impractical.

I will present our work that provides some of the first positive results and yield new, provably efficient, and practical algorithms for training certain types of neural networks. In a second work I will present a new online algorithm that learns by sequentially sampling random networks and asymptotically converges, in performance, to the optimal network. Our approach improves on previous random features based learning in terms of sample/computational complexity, and expressiveness. In a more recent work we take a different perspective on this problem. I will provide sufficient conditions that guarantee tractable learning, using the notion of refutation complexity. I will then discuss how this new idea can lead to new interesting generalization bounds that can potentially explain generalization in settings that are not always captured by classical theory.

 In the setting of reinforcement learning I will present a recently developed new algorithm for decision making in a metrical action space. As an application, we consider a dynamic pricing problem in which a seller is faced with a stream of patient buyers. Existing MAB algorithms often ignore the structure in the action space, and they are led to an erratic behavior that leads to sub-optimal regret in face of a strategic environment. Our algorithm achieves an optimal regret, and improves on previously known regret bound.

Bio:

Roi Livni is a research instructor at the computer science department in Princeton University. He is a recipient of the Eric and Wendy Schmidt fellowship for strategic innovation, and a Yad Hanadiv fellow for postdoctoral position.

He completed his PhD at the Hebrew University, during which he was a recipient of a Google Europe fellowship in learning theory. He also served, during his graduate studies, as a long term intern at Microsoft Research. His graduate work won a Best paper award in ICML'13, and a best student paper award in COLT'13.