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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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.

Improve this answer
$\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
    Commented 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$
    – Anton Petrunin
    Commented 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
    Commented May 17, 2013 at 18:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .