Rate of convergence for cyclic gradient descent

Question

I'm trying to solve the optimization problem

$\min_x \frac{1}{n} \sum_{i=1}^n f_i(x)$

where $f_i$ are (strongly) convex, smooth, lower semi-continuous, etc. However, I am not able to do conventional stochastic gradient descent (SGD), because the $f_i$ are distributed in multiple machines. I understand there are several ways to handle this situation, but suppose I do SGD in a deterministic cyclic way:

k = 1;

while 1

for i from 1 to n

     $x_{k+1} = x_k - \eta_k * \nabla f_i(x)$;

     k = k + 1;

end

end

Do whatever you like on the step size $\eta_k$.

Question: is there any rate of convergence in terms of $k$? A possible result could be like: for $x_k$ to be an $\epsilon$ accurate solution, $k$ needs to be at least $\frac{nC}{\epsilon^2}$, where the constant $C$ can be the strong convexity modulus of $f_i$, or Lipstchitz continuous constant of $f_i$ or its gradient, or norm of $\nabla f_i$, etc.

I am aware of results for cyclic coordinate descent: On the Finite Time Convergence of Cyclic Coordinate Descent Methods. Ankan Saha and Ambuj Tewari, Siam Journal of Optimization, 23(1):576-601, 2013.

Thanks in advance.

Answer 1

Methods of these type sometimes go under the name "Kaczmarz method". Kaczmarz method is a method for solving $Ax=b$ by iteratively (e.g. cyclic") projection onto the solutions of the equations given by the rows of the system. If the system is underdetermined and initialized at zero you'll end up minimizing $\|Ax-b\|_2^2$ and then you are precisely in the case of your question.

Although the method works pretty well in practice, at least for some problems (and for some it is even competitive to conjugate gradients for the normal equations), the convergence theory is not very nice. For example, the convergence rate depends on the order of the rows (or the $f_i$'s in your case). This seem most easily in two dimensions: If $A$ has two orthogonal rows, the methods finds the exact solution after projecting onto these two rows one successively. However, if there would be projections onto some other rows inbetween, you do not get convergence in finite time anymore. You get some convergence rate (in expectation) if you choose the rows not cyclically but randomly (see the Strohmer, Vershynin paper on the Wikipedia page).

The method is also related to the class of POCS-methods (projection onto convex sets). Perhaps even more closely related are incremental (sub)gradient methods (check "Incremental subgradient methods for nondifferentiable optimization" by Nedic and Bertsekas) and "stochastic gradient methods".