Unified view on accelerated randomized methods
Alexander Gasnikov, Moscow Institute of Physics and Technology
Abstract:
We start with the special version of fast gradient method (Yu. Nesterov). We show that from this method one can easily obtain:- accelereated coordinate descent method by changing gradient to the partial derivative (chooses at random),
- acelerated gradient-free method by changing gradient to kiefer-wolfowitz finite-difference .
The novelty is provided by unification of reasoning in the prove of the theorem about the rate of convegrence of these methods, and also by consideration of small noise (with unknown nature) in calculation of partial derivative for coordinate descent and in calculation of function's value for gradient-free method.