LANS Informal Seminar: Raghu Pasupathy

Seminar Title: Adaptive Sampling Line Search for Simulation-based Optimization
Speaker: Raghu Pasupathy, Associate Professor, Department of Statistics, Purdue University

Date/Time: 2015-06-24 14:00
Location: Building 240, Room 4301

Description:
For roughly six decades since the seminal paper of Robbins and Monro (1951), Stochastic Approximation has dominated the landscape of algorithms for solving root finding and optimization problems with Monte Carlo observable functions. Recently, however, inspired by the rise in parallel computing and advances in nonlinear programming methods, there has been increasing interest in alternative sampling-based frameworks. Such frameworks are convenient in that they use an existing recursive method, e.g., quasi-Newton or trust-region recursion, with embedded Monte Carlo estimators of objects appearing within the recursion. In this talk, after reviewing some recent results on optimal sampling rates, we will present a line search method that relies on adaptive Monte Carlo sampling, with deep connections to proportional-width confidence intervals. The method is globally convergent. More importantly, we are able to prove that the algorithm exhibits convergence rates that are arbitrarily close to optimal. Such theoretical promise seems to be borne out by experiments; if time permits, we will show our numerical experience on solving a large-scale parameter estimation problem in the context of deciphering EEG data from the human brain. The adaptive sampling schemes we advertise were independently discovered by Nocedal et al. through heuristic (but sound) arguments and numerical experimentation. This is joint work with Fatemeh Hashemi (Virginia Tech), Soumyadip Ghosh (IBM Research), and Peter Glynn (Stanford University).