Timeline for On a version of gradient descent
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 17, 2013 at 18:30 | vote | accept | user21162 | ||
| May 17, 2013 at 18:30 | comment | added | user21162 | Gotcha! I should learn to be more handy with code myself... | |
| May 17, 2013 at 17:38 | comment | added | Suvrit | I tested it on a simple numerical example; the sequence $r_t$ is not monotonic. Since you essentially brought up this point, I attributed it to you. | |
| May 17, 2013 at 17:11 | comment | added | user21162 | ...you say I observed that $r_t$ need not be monotonically decreasing, but I'm still uncertain about this: in my example above, $\langle f_i'(x_t) e_i, x_t - x^{\rm min} \rangle < 0$ only for the $i$ such that $|f_i'(x_t)|$ is not maximal.. | |
| May 17, 2013 at 17:09 | comment | added | user21162 | Thank you! Ok, I understand: so the answer to my question is that my claim ``the author appears to be using...'' is not right. | |
| May 17, 2013 at 16:43 | history | edited | Suvrit | CC BY-SA 3.0 |
fixed answer
|
| May 17, 2013 at 6:49 | comment | added | Suvrit | Ok, I think I was too quick!! I'll check the details of the proof tmw and update my answer. | |
| May 17, 2013 at 6:28 | comment | added | user21162 | 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$$ | |
| May 17, 2013 at 5:45 | comment | added | Suvrit | 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. | |
| May 16, 2013 at 20:30 | comment | added | user21162 | 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. | |
| May 16, 2013 at 19:20 | history | answered | Suvrit | CC BY-SA 3.0 |