@inproceedings{8ae39f51a9d74dc8af3252b8cbe4cdd2,
title = "EG-VSSA: An extragradient variable sample-size stochastic approximation scheme: Error analysis and complexity trade-offs",
abstract = "Given a sampling budget M, stochastic approximation (SA) schemes for constrained stochastic convex programs generally utilize a single sample for each projection, requiring an effort ofM projection operations, each of possibly significant complexity. We present an extragradient-based variable sample-size SA scheme (eg-VSSA) that uses Nk samples at step k where ϵk Nk > M. We make the following contributions: (i) In strongly convex regimes, the expected error decays linearly in the number of projection steps; (ii) In convex settings, if the sample-size is increased at suitable rates and the steplength is optimally chosen, the error diminishes at δ(1=K-d1) and δ(1/ √M), requiring O(M1/(2-d2)) steps, where K denotes the number of steps and d1;d2 > 0 can be made arbitrarily small. Preliminary numerics reveal that increasing sample-size schemes provide solutions of similar accuracy to SA schemes but with effort reduced by factors as high as 20.",
author = "Afrooz Jalilzadeh and Shanbhag, {Uday V.}",
note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 Winter Simulation Conference, WSC 2016 ; Conference date: 11-12-2016 Through 14-12-2016",
year = "2016",
month = jul,
day = "2",
doi = "10.1109/WSC.2016.7822133",
language = "English (US)",
series = "Proceedings - Winter Simulation Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "690--701",
editor = "Roeder, {Theresa M.} and Frazier, {Peter I.} and Robert Szechtman and Enlu Zhou",
booktitle = "2016 Winter Simulation Conference",
}