Stochastic Coordinate Minimization with Progressive Precision for
  Stochastic Convex Optimization
  A framework based on iterative coordinate minimization (CM) is developed for
stochastic convex optimization. Given that exact coordinate minimization is
impossible due to the unknown stochastic nature of the objective function, the
crux of the proposed optimization algorithm is an optimal control of the
minimization precision in each iteration. We establish the optimal precision
control and the resulting order-optimal regret performance for strongly convex
and separably nonsmooth functions. An interesting finding is that the optimal
progression of precision across iterations is independent of the
low-dimensional CM routine employed, suggesting a general framework for
extending low-dimensional optimization routines to high-dimensional problems.
The proposed algorithm is amenable to online implementation and inherits the
scalability and parallelizability properties of CM for large-scale
optimization. Requiring only a sublinear order of message exchanges, it also
lends itself well to distributed computing as compared with the alternative
approach of coordinate gradient descent.
