# Gradient descent in a distributed manner

Let $p(x_1,x_2,x_3)$ be a scalar function. The goal is to find $x_1,x_2,x_3$ to minimize $p(x_1,x_2,x_3)$. Now consider the gradient descent method: $$\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k+1} = \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k} - \alpha_k \left( \begin{array}{c} \frac{\partial p}{\partial x_1} \\ \frac{\partial p}{\partial x_2} \\ \frac{\partial p}{\partial x_3} \\ \end{array} \right)_{k}$$ where $\alpha_k$ is the step size.

My question is: can the above iterative process be conducted in a distributed manner? This might be motivated by some reasons such as distributed computational resources. The following is my opinion about this problem.

Rewrite the above equation to $$x_{1,k+1}=x_{1,k}-\alpha_{1,k} \frac{\partial p}{\partial x_1}$$ $$x_{2,k+1}=x_{2,k}-\alpha_{2,k} \frac{\partial p}{\partial x_2}$$ $$x_{3,k+1}=x_{3,k}-\alpha_{3,k} \frac{\partial p}{\partial x_3}$$ Then the three equations can be computed in three computers, respectively. Here I have a question, do the step size $\alpha_{1,k}, \alpha_{2,k}, \alpha_{3,k}$ matter? Should we keep $\alpha_{1,k}=\alpha_{2,k}=\alpha_{3,k}$?? In other words, is the following equation gradient descent? If $\alpha_{1,k}, \alpha_{2,k}, \alpha_{3,k}$ are different from each other, the global movement is no long along with $\nabla_\mathbf{x} p(\mathbf{x})$. $$\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k+1} = \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k} - \left( \begin{array}{ccc} \alpha_{1,k} & 0 & 0 \\ 0 & \alpha_{2,k} & 0 \\ 0& 0& \alpha_{3,k}\\ \end{array} \right) \left( \begin{array}{c} \frac{\partial p}{\partial x_1} \\ \frac{\partial p}{\partial x_2} \\ \frac{\partial p}{\partial x_3} \\ \end{array} \right)_{k}$$

-
Multiplying the gradient with a matrix is called preconditioning. It's used particularly with the conjugate gradient method. However, a fixed matrix is determined, based on information collected, and then a single step size is used to search along the gradient direction thus modified. If you use different step sizes in different directions, you're not using the gradient at all; you're just performing $n$ searches along the coordinate axes in parallel. –  joriki Aug 14 '11 at 12:22

Technically you are allowed to use different stepsizes for different variables so long as you can establish (mathematically) that the linesearch procedure that computes your $\alpha_{i,k}$ ensures that there exist constants $0 < l < u$ such that $$l \ \alpha_{i,k} \leq \alpha_{j,k} \leq u \ \alpha_{i,k} \quad \text{for all iterations } k \text{ and all } i, j = 1, \ldots, n.$$ This is used to prevent some steplengths from converging to zero or infinity while others remain finite.

In your second point, where the descent direction has the form $Ag$, you are using a quasi Newton method. If you were using Newton's method, your search direction would solve the linear system $$\nabla^2 f(x_k) d = - \nabla f(x_k).$$ (Note that I didn't say that the Hessian $\nabla^2 f(x_k)$ was invertible... it is what it is.) This search direction will be a descent direction if $d^T \nabla f(x_k) < 0$. It is the case when $\nabla^2 f(x_k)$ is positive definite, but it may happen in other situations. Now if second derivatives aren't available or are too costly to evaluate you can substitute your own matrix in the linear system above and require $d$ to solve $$B d = -\nabla f(x_k).$$ You'll get a descent direction provided $B$ is positive definite. The steepest descent method simply corresponds to $B = I$. There is a subtelty here. You'll likely use a different $B$ at each iteration so $B$ is really $B_k$. You can ensure convergence if you use one of the standard linesearch methods (Armijo, Wolfe, strong Wolfe, Goldstein, ...) and if you can ensure that $d$ never approaches orthogonality with $\nabla f(x_k)$ (it could happen in a sneaky manner in the limit). This amounts to proving that $d^T \nabla f(x_k) \leq -\theta < 0$ for some constant $\theta$ independent of $k$. In any optimization book, look for Zoutendijk's theorem.

Quasi-Newton methods are a form of preconditioning of the steepest descent method. In the early days, they were referred to as "variable metric" methods. Whether they can be computed in a distributed manner depends a great deal on the structure of the matrix $B$.

-

Now I figure it out.

The steepest gradient descent is $$x_{k+1}=x_k-\alpha_k g$$ where $g=\nabla p(x)$ is the gradient. When we want to use $$x_{k+1}=x_k-A g$$ with $A$ as a matrix instead, we need only to ensure $$g^T A g>0$$ such that $p(x)$ will keep decreasing. The geometric meaning of the above equation actually is: the evolving direction $-A g$ should make an angle strictly less than $\pi/2$ with $-g$. So as long as $A$ is positive definite, the evolving direction is always a descent direction (may not steepest).

-