New nonasymptotic convergence rates of stochastic proximal
  pointalgorithm for convex optimization problems
  Large sectors of the recent optimization literature focused in the last
decade on the development of optimal stochastic first order schemes for
constrained convex models under progressively relaxed assumptions. Stochastic
proximal point is an iterative scheme born from the adaptation of proximal
point algorithm to noisy stochastic optimization, with a resulting iteration
related to stochastic alternating projections. Inspired by the scalability of
alternating projection methods, we start from the (linear) regularity
assumption, typically used in convex feasiblity problems to guarantee the
linear convergence of stochastic alternating projection methods, and analyze a
general weak linear regularity condition which facilitates convergence rate
boosts in stochastic proximal point schemes. Our applications include many
non-strongly convex functions classes often used in machine learning and
statistics. Moreover, under weak linear regularity assumption we guarantee
$\mathcal{O}\left(\frac{1}{k}\right)$ convergence rate for SPP, in terms of the
distance to the optimal set, using only projections onto a simple component
set. Linear convergence is obtained for interpolation setting, when the optimal
set of the expected cost is included into the optimal sets of each functional
component.
