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

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.