I am trying to read [this paper](http://www.optimization-online.org/DB_FILE/2010/01/2527.pdf) and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has Lipschitz constant $M$ and considers the scheme 
$$ x(t+1) = x(t) - \frac{1}{M} [f'(x(t)]\_k e\_k$$ where $[\cdot]\_i$ denotes the $i$'th entry of a vector and $k$ is the index which maximizes $|[f'(x(t)]\_k|$. In words, the update is to move in the opposite direction of the largest component of the gradient. 


The scheme is introduced on page 1 (see big box in middle of page) and just two lines later (in the sequence of inequalities after "Then,") the author appears to be using that 
$$||f'(x(t))||\_2^2 \geq \frac{\left( f(x(t) - f(x^{\rm min}) \right)^2}{||x(0) - x^{\rm min}||\_2^2}$$ where $x^{\rm min}$ is the global minimizer.


Anyway, I don't see why this statement is true. I do see how to prove it if $x(0)$ were replaced by $x(t)$ on the right-hand side, so if it could be shown that $||x(t)-x^{\rm min}||$ is nonincreasing, that would do it. But I don't see how to show that; it would seem to require showing that $[f'(x(t))]\_k$ has the same sign as $[x(t)-x^{\rm min}]\_k$, and I don't see how to argue that.


P.S. I [asked this](https://math.stackexchange.com/questions/389862/on-a-version-of-gradient-descent) on math.SE a few days ago without getting any answers. 



On a version of gradient descent
Here is a simple argument. First, define $r\_t = \|x\_t - x^\ast\|$, where $x^\ast$ denotes an optimal point.


Since $f$ is convex, we have


\begin{equation\*}
 f(x^\ast) \ge f(x\_t) + \langle f'(x\_t), x^\ast - x\_t \rangle.
\end{equation\*}
From this we conclude (where we use the fact that $f(x\_t) \ge f(x^\ast)$ and Cauchy-Schwarz) 


\begin{equation\*}
 (f(x\_t)-f(x^\ast)^2 \le \|f'(x\_t)\|^2 r\_t^2,
\end{equation\*}


**Edit** As noticed by the OP, the sequence $r\_t$ need not be monotonically decreasing, so we cannot simply write $r\_t \le r\_0$ and obtain the inequality in the paper. A reasonable choice here would be (a similar choice is made in the rest of the paper too, e.g., in Thm.1) is to use 


`\begin{equation*}
 R(x_0) := \max_{0 \le k \le t} \|x_k-x^*\|,
\end{equation*}`


where for simplicity I assumed $x^\*$ is unique.


