Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  user21162 May 16 '13 at 20:30
    
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. –  Suvrit May 17 '13 at 5:45
    
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$$ –  user21162 May 17 '13 at 6:28
    
Ok, I think I was too quick!! I'll check the details of the proof tmw and update my answer. –  Suvrit May 17 '13 at 6:49
    
Thank you! Ok, I understand: so the answer to my question is that my claim ``the author appears to be using...'' is not right. –  user21162 May 17 '13 at 17:09
show 3 more comments

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.

share|improve this answer
    
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? –  user21162 May 16 '13 at 19:01
    
@Robinson1. I would better leave it as an exercise :) BTW, if it would be wrong then so is the original statement. –  Anton Petrunin May 17 '13 at 5:12
    
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. –  user21162 May 17 '13 at 18:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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