Convergence Analysis of Inexact Randomized Iterative Methods
This work addresses the computational efficiency of iterative methods for optimization problems, but it is incremental as it extends existing methods by relaxing exactness requirements.
The paper analyzes the convergence rates of inexact variants of randomized iterative methods, such as stochastic gradient descent and randomized block coordinate descent, by allowing sub-problems to be solved inexactly, and provides iteration complexity results with numerical experiments showing benefits.
In this paper we present a convergence rate analysis of inexact variants of several randomized iterative methods. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic subspace ascent. A common feature of these methods is that in their update rule a certain sub-problem needs to be solved exactly. We relax this requirement by allowing for the sub-problem to be solved inexactly. In particular, we propose and analyze inexact randomized iterative methods for solving three closely related problems: a convex stochastic quadratic optimization problem, a best approximation problem and its dual, a concave quadratic maximization problem. We provide iteration complexity results under several assumptions on the inexactness error. Inexact variants of many popular and some more exotic methods, including randomized block Kaczmarz, randomized Gaussian Kaczmarz and randomized block coordinate descent, can be cast as special cases. Numerical experiments demonstrate the benefits of allowing inexactness.