2
$\begingroup$

I am trying to read this paper 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 on math.SE a few days ago without getting any answers.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Yes, please fill in the details. It is not in general true that $\langle f_i'(x_t) e_i, x_t - x^* \rangle \geq 0$, is it? I think if that is true, its only true for the $i$ such that $|f_i'(x_t)|$ is largest. $\endgroup$
    – user21162
    May 16, 2013 at 20:30
  • $\begingroup$ Sorry, don't have time to type it in right now; please see (2.1.7 and 2.1.8) in the book Introductory lectures on convex optimization by Yu. Nesterov; you'll have to adapt those lemmas to the case of $f$ restricted to the $i$-th coordinate. From that the desired conclusion will follow. (Also, since $f$ is convex, $f'$ is monotone, so the inequality that you've mentioned in the comment also holds. The index being largest in magnitude was used for an earlier inequality in the cited paper. $\endgroup$
    – Suvrit
    May 17, 2013 at 5:45
  • $\begingroup$ Here is what seems to me to be a counterexample to the inequality in my comment which you say is true: Suppose $$f(x,y) = 10*(x-y-1)^2+(x+y+1)^2$$ Clearly $f$ is convex and moreover the minimum is $$(x,y)^{\rm min} = (0,-1)$$ Now computing the derivative: $$f_{x}(x,y) = 20*(x-y-1) + 2 (x+y+1)$$ $$f_x(0.5,0) = 20*(-.5) + 2(1.5)=-7$$ so that $$ \langle f_x(0.5,0) e_1, (0.5,0)-(0,-1) \rangle = -7*0.5 < 0$$ $\endgroup$
    – user21162
    May 17, 2013 at 6:28
  • $\begingroup$ Ok, I think I was too quick!! I'll check the details of the proof tmw and update my answer. $\endgroup$
    – Suvrit
    May 17, 2013 at 6:49
  • $\begingroup$ Thank you! Ok, I understand: so the answer to my question is that my claim ``the author appears to be using...'' is not right. $\endgroup$
    – user21162
    May 17, 2013 at 17:09
0
$\begingroup$

I guess $|f'(y)|$ stays for $|d_yf|$. If so, $$|f'(y)| \geq \frac{f(y) - f(x^{\rm min})}{|y - x^{\rm min}|}.$$ Since $|x(t)-x^{\rm min}|$ is decreasing, the statement follows.

$\endgroup$
3
  • $\begingroup$ I assume that by $|\cdot|$ you mean $||\cdot||_2$, since $x(t)$ and $x^{\rm min}$ are vectors. If so, why is $||x(t)-x^{\rm min}||_2$ decreasing? $\endgroup$
    – user21162
    May 16, 2013 at 19:01
  • $\begingroup$ @Robinson1. I would better leave it as an exercise :) BTW, if it would be wrong then so is the original statement. $\endgroup$ May 17, 2013 at 5:12
  • $\begingroup$ FYI, in comments to the other answer, it is claimed that numerical simulations show that the claim you leave as an exercise here is false. $\endgroup$
    – user21162
    May 17, 2013 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.