Back to Search Start Over

Minibatch stochastic subgradient-based projection algorithms for feasibility problems with convex inequalities.

Authors :
Necoara, Ion
Nedić, Angelia
Source :
Computational Optimization & Applications; Sep2021, Vol. 80 Issue 1, p121-152, 32p
Publication Year :
2021

Abstract

In this paper we consider convex feasibility problems where the feasible set is given as the intersection of a collection of closed convex sets. We assume that each set is specified algebraically as a convex inequality, where the associated convex function is general (possibly non-differentiable). For finding a point satisfying all the convex inequalities we design and analyze random projection algorithms using special subgradient iterations and extrapolated stepsizes. Moreover, the iterate updates are performed based on parallel random observations of several constraint components. For these minibatch stochastic subgradient-based projection methods we prove sublinear convergence results and, under some linear regularity condition for the functional constraints, we prove linear convergence rates. We also derive sufficient conditions under which these rates depend explicitly on the minibatch size. To the best of our knowledge, this work is the first deriving conditions that show theoretically when minibatch stochastic subgradient-based projection updates have a better complexity than their single-sample variants when parallel computing is used to implement the minibatch. Numerical results also show a better performance of our minibatch scheme over its non-minibatch counterpart. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
09266003
Volume :
80
Issue :
1
Database :
Complementary Index
Journal :
Computational Optimization & Applications
Publication Type :
Academic Journal
Accession number :
151687251
Full Text :
https://doi.org/10.1007/s10589-021-00294-3