Why my gradient descent seems to diverge "pair-wise"?

Question

I've checked the algorithms and they work for golden section line search and "small step parameter".

However, when trying to get the algo to diverge, I notice that the results indicate that the divergence occurs "pair-wise". The components flip on every iteration (although they're not entirely the same, they show slow improvement).

Function is:

$$f(x,y)=x^2+y^2+x+2y$$

Does this have some symmetry that'd explain this?

Reproducing code:

https://pastebin.com/QM4twYLy

$f(x, y) = (x+\frac12)^2 + (y + 1)^2 + C$ for some constant $C$; that's nicely symmetric about the line $x = -\frac12$ and the line $y = -1$, which are pretty close to the axes when you're looking at a $200 \times 200$ rectangle. — John Hughes, Jan 22 '19 at 15:14
@JohnHughes Okay, but I don't see what causes flipping of the components or sign. — mavavilj, Jan 22 '19 at 15:18
You asked if there was some sort of symmetry, and I answered that. It's not clear from the question exactly what implementation you're using (nor even exactly what algorithm), so I can't tell you how (or whether) the symmetry causes sign-flipping. Presumably working through a few iteration by hand would lead to some insight. You might try the same thing with a starting point near, say, $(-\frac12, -1)$ and see whether you still get sign-flipping, or merely symmetry. The current scale is too large to tell the difference. — John Hughes, Jan 22 '19 at 15:48
Note that $-\nabla f$ always points towards $(-1/2,-1)$, so your iterates will always lie along the line joining that point to your initial guess. This property goes away if you change the coefficients of $x^2$ and $y^2$ to be different. — , Jan 22 '19 at 17:40
@JohnHughes There's no sign flip when the initial guess is near the optimal. Both will stay negative. However the components are still flipping, so it draws the same "pair-wise" pattern. — mavavilj, Jan 22 '19 at 19:36
Good enough -- so your initial claim that the sign flips was just a consequence of the center of symmetry being near the origin and the test-points being far away. As for the individual alternation...Rahul has a good point, and hand-simulation will probably tell you the whole story. — John Hughes, Jan 22 '19 at 19:45
@JohnHughes I noticed that the part computing (-df(an)) flips its sign every round. I removed that - and not it diverges like the others, no pair-wise phenomenon. However, in the formulation of gradient descent, it's supposed to have a minus. — mavavilj, Jan 22 '19 at 19:54
@JohnHughes I noticed though that I might be violating the monotonicity property: $F(x_0) \geq F(x_1) \geq F(x_2) \geq ...$ somehow. Since my $f(an)$ is growing from negative $-1.17$ up towards $0$. But $-1.17 < 0$. Or maybe this is because it diverges. — mavavilj, Jan 22 '19 at 19:57
@JohnHughes I think that this oscillation is just a feature of the algorithm diverging though: http://people.duke.edu/~ccc14/sta-663-2018/notebooks/S09G_Gradient_Descent_Optimization.html#Gradient-descent-with-large-step-size — mavavilj, Jan 22 '19 at 20:01
You seem to imagine that I know exactly what gradient descent algorithm you're using. I don't. Basically, nothing you're saying makes any sense to me because of that. I suggested, in my second remark, that you give more detail, but ... nothing. So...I'm quitting. — John Hughes, Jan 22 '19 at 20:01
"The code" is not an algorithm (nor does it seem to be an implementation of any reasonable gradient descent algorithm). But you can at least make it better by including it in your question rather than leaving a pointer. Far better would be to express it as an algorithm, independent of language/libraries. And you can -- if you're willing to do some work -- actually debug it via hand-simulation, or look at/print out values as it runs and determine what's happening. Once you try that, and include the results in your question, I might regain some interest. For now...it's up to you. — John Hughes, Jan 22 '19 at 21:16

Why my gradient descent seems to diverge "pair-wise"?

0 Answers0