Speaker: Yuejie Chi, Carnegie Mellon University
Title: Preconditioning Helps: Faster Convergence in Statistical and Reinforcement Learning 
Day: Monday, April 19, 2021
Time: 4:30 pm
Zoom Link: Please register using this link
Host: Yuxin Chen and Jason Lee 

Abstract:
While exciting progress has been made in understanding the global convergence of vanilla gradient methods for solving challenging nonconvex problems in statistical estimation and machine learning, their computational efficacy is still far from satisfactory for ill-posed or ill-conditioned problems. In this talk, we discuss how the trick of preconditioning further boosts the convergence speed with minimal computation overheads through two examples: low-rank matrix estimation in statistical learning and policy optimization in entropy-regularized reinforcement learning. For low-rank matrix estimation, we present a new algorithm, called scaled gradient descent, that achieves linear convergence at a rate independent of the condition number of the low-rank matrix at near-optimal sample complexities for a variety of tasks, even in the presence of adversarial outliers. For policy optimization, we develop the first fast non-asymptotic convergence guarantee for entropy-regularized natural policy gradient methods in the tabular setting for discounted Markov decision processes. By establishing its global linear convergence at a near dimension-free rate, we provide theoretical footings to the empirical success of entropy-regularized natural policy gradient methods.
 

Bio:
Dr. Yuejie Chi is an Associate Professor in the department of Electrical and Computer Engineering, and a faculty affiliate with the Machine Learning department and CyLab at Carnegie Mellon University, where she holds the Robert E. Doherty Early Career Development Professorship. She received her Ph.D. and M.A. from Princeton University, and B. Eng. (Hon.) from Tsinghua University, all in Electrical Engineering. Her research interests lie in the theoretical and algorithmic foundations of data science, signal processing, machine learning and inverse problems, with applications in sensing systems, broadly defined. Among others, Dr. Chi received the Presidential Early Career Award for Scientists and Engineers (PECASE), the inaugural IEEE Signal Processing Society Early Career Technical Achievement Award for contributions to high-dimensional structured signal processing, and was named a Goldsmith Lecturer by IEEE Information Theory Society.

This seminar is supported by CSML and EE Korhammer Lecture Series Funds