A random monotone operator framework for strongly convex stochastic optimization

摘要

Analysis of every algorithm for stochastic optimization seems to require a different convergence proof. It would be desirable to have a unified mathematical framework within which with minimal extra effort, proof of convergence and its rate could be obtained. We present a random monotone operator-based unified convergence analysis framework for iterative algorithms for strongly convex stochastic optimization. The framework offers both versatility and simplicity, and allows for clean and straightforward analysis of many algorithms for stochatic convex minimization, saddle-point problems and variational inequalities. We show convergence of the random operator to a probabilistic fixed point, and obtain non-asymptotic rates of convergence. The analysis technique relies on a novel stochastic dominance argument.