@inproceedings{b9f150ccfc4e4a9d9b7ea8b74f015193,

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, {Vinayak V.}",

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",

address = "United States",

note = "2016 Winter Simulation Conference, WSC 2016 ; Conference date: 11-12-2016 Through 14-12-2016",

}