"Variable Sample-size Stochastic Approximation (VSSA)"

ABSTRACT

Traditional stochastic approximation (SA) schemes employ a single gradient or a fixed batch of noisy gradients in computing a new iterate and requires a projection on a possibly complex convex set for every update. As a consequence, practical implementations may require the solution of a large number of projection problems, and may render this scheme impractical. We present a variable sample-size stochastic approximation (VSSA) scheme where the batch of noisy gradients may change in size across iterations and the scheme terminates when the budget is consumed. In this setting, we derive error bounds in strongly convex, convex differentiable, and convex nonsmooth regimes. In particular, we focus on quantifying the rate of convergence in terms of projection steps and in terms of simulation budget and comment on the optimality of the obtained rates. In addition, we present a (Nesterov-) accelerated VSSA scheme which displays the optimal accelerated rate of convergence in terms of projection steps if the sample size grows sufficiently fast. Preliminary numerics suggest that VSSA schemes outperform their traditional counterparts in terms of computational time while maintaining statistical accuracy.

VIDEO

BIO

Uday V. Shanbhag is currently the Gary and Sheila Bello Chaired Professor in the department of Industrial and Manufacturing Engineering (IME) at the Pennsylvania State University having been here since 2012. Prior to being at PSU, he was first an assistant professor, and subsequently a tenured associate professor (for approx. 10 days), in the department of Industrial and Enterprise Systems engineering (ISE) at the University of Illinois at Urbana-Champaign. His research honors include the triennial A.W. Tucker Prize by the mathematical programming society (MPS) in 2006, the NCSA Faculty Fellowship in 2006, the Computational Optimization and Applications (COAP) best paper award (with advisor Walter Murray) in 2007, and the best theoretical paper award in the Winter Simulation Conference (WSC) in 2013 (with Angelia Nedich and Farzad Yousefian). Additionally, he was awarded the NSF Early Career Development (CAREER) award in 2012 from the Operations Research program. He is currently an associate editor for IEEE Transactions on Automatic Control. He holds a  Ph.D. from Stanford University's department of Management Science and Engineering (2006), with a concentration in operations research. He also holds masters and undergraduate degrees from the Massachusetts Institute of Technology (MIT), Cambridge (in Operations Research) and the Indian Institute of Technology (IIT), Bombay, respectively. His interests lie in optimization, variational inequality problems, and noncooperative games complicated by nonsmoothness and uncertainty with application interests in statistical learning (more recently) and power systems and markets.