Random minibatch projection algorithms for convex feasibility problems

摘要

This paper deals with the convex feasibility problem where the feasible set is given as the intersection of a (possibly infinite) number of closed convex sets. We assume that each set is specified algebraically as a convex inequality, where the associated convex function may be even non-differentiable. We present and analyze a random minibatch projection algorithm using special subgradient iterations for solving the convex feasibility problem described by the functional constraints. The updates are performed based on parallel random observations of several constraint components. For this minibatch method we derive asymptotic convergence results and, under some linear regularity condition for the functional constraints, we prove linear convergence rate. We also derive conditions under which the rate depends explicitly on the minibatch size. To the best of our knowledge, this work is the first proving that random minibatch subgradient based projection updates have a better complexity than their single-sample variants.