String-averaging incremental stochastic subgradient algorithms. (4th May 2019)

• Record Type: Journal Article
• Authors: Oliveira, R. M.; Helou, E. S.; Costa, E. F.
• Is Part Of: Optimization methods and software. Volume 34:Number 3(2019)
• Page Start: 665
• Page End: 692
• Publication Date: 2019-05-04
• Subjects: Convex optimization -- stochastic optimization -- incremental algorithms -- stochastic subgradient methods -- approximate projection methods -- string-averaging algorithms; 65K05 -- 90C15 -- 90C25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1496432
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: We present a method to solve constrained convex stochastic optimization problems when the objective is a finite sum of convex functionsf i . Our method is based on Incremental Stochastic Subgradient Algorithms and String-Averaging techniques, with an assumption that the subgradient directions are affected by random errors in each iteration. Our analysis allows the method to perform approximate projections onto the feasible set in each iteration. We provide convergence results for the case where a diminishing step-size rule is used. We test our method in a large set of random instances of a stochastic convex programming problem and we compare its performance with the robust mirror descent stochastic approximation algorithm proposed in Nemirovski et al. (Robust stochastic approximation approach to stochastic programming, SIAM J Optim 19 (2009), pp. 15741609).