Sequential Decision Making: Nonconvexity and Nonstationarity

Presented by Abhishek Roy, University of California, Davis

Monday, January 10
4:00 p.m. ET
Online

Numerous statistical problems including dynamic matrix sensing and completion, and online reinforcement learning can be formulated as nonconvex optimization problem where the objective function changes over time. In this work, we propose and analyze stochastic zeroth-order optimization algorithms in online learning setting for nonconvex functions in a nonstationary environment. We propose nonstationary versions of regret measures based on first-order and second-order optimal solutions and establish sub-linear regret bounds on these proposed regret measures. The main takeaway from this work is that one can track statistically favorable solution, i.e., stationary point or local minima of the underlying nonconvex objective function of a statistical learning problem even in a nonstationary environment. For the case of first-order optimal solution-based regret measures, we provide regret bounds for stochastic gradient descent algorithm. For the case of second-order optimal solution-based regret, we analyze stochastic cubic-regularized Newton’s Method. We establish the regret bounds in the zeroth-order oracle setting where one has access to noisy evaluations of the objective function only. We illustrate our results through simulation as well as several learning problems.

Speaker Bio

Dr. Abhishek Roy is currently a postdoctoral researcher in the Department of Statistics at the University of California, Davis. He works primarily with Prof. Krishnakumar Balasubramanian. He finished his Ph.D. in Electrical and Computer Engineering from the University of California, Davis in June 2020, advised by Prof. Prasant Mohapatra. Prior to this, he received a Bachelor of Technology (Hons.) in Electronics and Electrical Communication Engineering in 2013 from the Indian Institute of Technology, Kharagpur. ​His research interests include non-convex optimization, uncertainty quantification, Markov Chain Monte Carlo (MCMC) sampling, generalization properties of deep networks and robust learning from dependent data.