Category Archives: Fall 2019

Alekh Agarwal; Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes

Alekh Agarwal, Microsoft Research AI
Tuesday Nov 12, 2019, CSE2 (Gates) G04, 4-5pm

Title: Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes

Abstract: Policy gradient methods are among the most effective methods in challenging reinforcement learning problems with large state and/or action spaces. However, little is known about even their most basic theoretical convergence properties, including: 1) if and how fast they converge to a globally optimal solution (say with a sufficiently rich policy class); 2) how they cope with approximation error due to using a restricted class of parametric policies; or 3) their finite sample behavior. In this talk, we will study all these issues, and provide a broad understanding of when first-order approaches to direct policy optimization in RL succeed. We will also identify the relevant notions of policy class expressivity underlying these guarantees in the approximate setting. Throughout, we will also highlight the interplay of exploration with policy optimization, both in our upper bounds and illustrative lower bounds. This talk is based on joint work with Sham Kakade, Jason Lee and Gaurav Mahajan. Please see https://arxiv.org/pdf/1908.00261 for details.

Bio: Alekh Agarwal is a Principal Research Manager at Microsoft Research where he has been since 2012. His research broadly focuses on designing theoretically sound and practically useful techniques for sequential decision making problems. Within this context, he has worked on areas such as bandits, active learning and most recently reinforcement learning. He has also worked on several other aspects of machine learning including convex optimization, high-dimensional statistics and large-scale machine learning in distributed settings.

Marco Cuturi; Computational Optimal Transport

Marco CuturiGoogle Brain, Paris
Tuesday Nov 19, 2019, CSE2 (Gates) G04, 4-5pm

Title: Computational Optimal Transport

Abstract: I will give in this talk a short introduction to optimal
transport theory, a fecund field at the intersection of analysis,
probability and PDEs crowned by two Field’s medals (Villani,’10 and
Figalli,’18) and which has now found applications in data-sciences,
notably biology, graphics, NLP and imaging. I will explain how these
intuitive tools require some adaptation before being used in
high-dimensional settings, and present computational strategies to
cope with the challenges of scale arising from the use of this theory
on real-life problems.

Cynthia Vinzant; Determinants, polynomials, and matroids

Cynthia VinzantDept. of Mathematics, North Carolina State University
Tuesday Oct 8, 2019, CSE2 (Gates) G04, 4-5pm

Title: Determinants, polynomials, and matroids

Abstract: The determinant of a symmetric matrix is a fundamental object in mathematics, whose discrete and functional properties have applications across the scientific disciplines. The determinant of a matrix is also a real polynomial in its entries.  Hyperbolic polynomials and, more generally, log-concave polynomials are real polynomials that share many useful functional properties of determinants. Like real-rooted univariate polynomials, they also have interesting combinatorial applications. I will discuss the beautiful real and combinatorial geometry underlying these polynomials and applications of this theory to counting and sampling problems involving combinatorial objects called matroids. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.