Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How does gradient descent work?

centralflows.github.io

Post reply on HN
Print view View original

11–20 of 25 posts

Re: How does gradient descent work?

#11

Post by programjames »

It's a little easier to see what's happening if you fully write out the central flow:

    -1/η * dw/dt = ∇L - ∇S * ⟨∇L, ∇S⟩/‖∇S‖²
We're projecting the loss gradient onto the sharpness gradient, and subtracting it off. If you didn't read the article, the sharpness S is the sum of the eigenvalues of the Hessian of the loss that are larger than 2/η, a measure of how unstable the learning dynamics are.

This is almost Sobolev preconditioning:

    -1/η * dw/dt = ∇L - ∇S = ∇(I - Δ)L
where this time S is the sum of all the eigenvalues (so, the Laplacian of L).

Re: How does gradient descent work?

#12

Post by lcnielsen »

programjames wrote: post #11

It's a little easier to see what's happening if you fully write out the central flow: -1/η * dw/dt = ∇L - ∇S * ⟨∇L, ∇S⟩/‖∇S‖² We're projecting the loss gradient onto the sharpness gradient, and subtracting it off. If you didn't read the article, the sharpness S is the sum of the eigenvalues of the Hessian of the loss that are larger than 2/η, a measure of how unstable the learning dynamics are. This is almost Sobolev…

Yeah, I did a lot of traditional optimization problems during my Ph. D., this type of expression pops up all the time with higher-order gradient-based methods. You rescale or otherwise adjust the gradient based on some system-characteristic eigenvalues to promote convergence without overshooting too much.

Re: How does gradient descent work?

#13

Post by imtringued »

I apparently didn't get the memo and used stochastic gradient descent with momentum outside of deep learning without running into any problems given a sufficiently low learning rate.

I'm not really convinced that their explanation truly captures why this success should be exclusive to deep learning.

Re: How does gradient descent work?

#14

Post by d3m0t3p »

lcnielsen wrote: post #12
programjames wrote: post #11

It's a little easier to see what's happening if you fully write out the central flow: -1/η * dw/dt = ∇L - ∇S * ⟨∇L, ∇S⟩/‖∇S‖² We're projecting the loss gradient onto the sharpness gradient, and subtracting it off. If you didn't read the article, the sharpness S is the sum of the eigenvalues of the Hessian of the loss that are larger than 2/η, a measure of how unstable the learning dynamics are. This is almost Sobolev…

Yeah, I did a lot of traditional optimization problems during my Ph. D., this type of expression pops up all the time with higher-order gradient-based methods. You rescale or otherwise adjust the gradient based on some system-characteristic eigenvalues to promote convergence without overshooting too much.

This sounds a lot like what the Muon / Shampoo optimizer do.

Re: How does gradient descent work?

#15

Post by danielmarkbruce »

untrimmed wrote: post #4

So all the classic optimization theory about staying in the stable region is basically what deep learning doesn't do. The model literally learns by becoming unstable, oscillating, and then using that energy to self-correct. The chaos is the point. What a crazy, beautiful mess.

I dont think it's a good way to think of it.

Researchers are constantly looking to train more expressive models more quickly. Any method which can converge + take large jumps will be chosen. You are sort of guaranteed to end up in a place where the sharpness is high but it somehow comes under control. If we weren't there.... we'd try a new architecture until we arrived there. So deep learning doesn't "do this", we do it using any method possible and it happened to be the various architectures that currently fit into "deep learning". Keep in mind many architectures which are deep do not converge - you see survivorship bias.

Re: How does gradient descent work?

#16

Post by d3m0t3p »

lcnielsen wrote: post #12
programjames wrote: post #11

It's a little easier to see what's happening if you fully write out the central flow: -1/η * dw/dt = ∇L - ∇S * ⟨∇L, ∇S⟩/‖∇S‖² We're projecting the loss gradient onto the sharpness gradient, and subtracting it off. If you didn't read the article, the sharpness S is the sum of the eigenvalues of the Hessian of the loss that are larger than 2/η, a measure of how unstable the learning dynamics are. This is almost Sobolev…

Yeah, I did a lot of traditional optimization problems during my Ph. D., this type of expression pops up all the time with higher-order gradient-based methods. You rescale or otherwise adjust the gradient based on some system-characteristic eigenvalues to promote convergence without overshooting too much.

Would you have some literature about that ?

Re: How does gradient descent work?

#17

Post by DoctorOetker »

markisus wrote: post #9
DoctorOetker wrote: post #5

Fascinating, do the gained insights allow to directly compute the central flow in order to speed up convergence? Or is this preliminary exploration to understand how it had been working? They explicitly ignore momentum and exponentially weighted moving average, but that should result in the time-averaged gradient descent (along the valley, not across it). But that requires multiple evaluations, do any of the expressi…

The authors somewhat address your questions in the accompanying paper https://arxiv.org/abs/2410.24206 > We emphasize that the central flow is a theoretical tool for understanding optimizer behavior, not a practical optimization method. In practice, maintaining an exponential moving average of the iterates (e.g., Morales-Brotons et al., 2024) is likely a computational feasible way to estimate the optimizer’s time-ave…

Yes, it certainly provides a lot more clarity than the handwaving.

While momentum seems to work, and the authors clearly state it is not intended as a practical optimization method, I can't exclude that we can improve convergence rates by building on this knowledge.

Is it guaranteed for the oscillating behavior to have a period of 2 steps? or is say 3 step period also possible (a vector in a plane could alternately point to 0 degrees, 120 degrees and 240 degrees).

The way I read this presentation the implication seems to be that its always a period of 2. Perhaps if the top-2 sharpnesses are degenerate (identical), a period of N distinct from 2 could be possible?

It makes you wonder what if instead of storing momentum with exponential moving average one were to use the average of the last 2 iterations, so there would be less lag.

It also makes me wonder if we should perform 2 iterative steps PER sequence so that the single-sample-sequence gives feedback along it's valley instead of across it. One would go through the corpus at half the speed, but convergence may be more accurate.

Re: How does gradient descent work?

#20

Post by kingstnap »

DoctorOetker wrote: post #17
markisus wrote: post #9

Earlier quoted context omitted.

The authors somewhat address your questions in the accompanying paper https://arxiv.org/abs/2410.24206 > We emphasize that the central flow is a theoretical tool for understanding optimizer behavior, not a practical optimization method. In practice, maintaining an exponential moving average of the iterates (e.g., Morales-Brotons et al., 2024) is likely a computational feasible way to estimate the optimizer’s time-ave…

Yes, it certainly provides a lot more clarity than the handwaving. While momentum seems to work, and the authors clearly state it is not intended as a practical optimization method, I can't exclude that we can improve convergence rates by building on this knowledge. Is it guaranteed for the oscillating behavior to have a period of 2 steps? or is say 3 step period also possible (a vector in a plane could alternately p…

I doubt it would ever be period 3.

Not a formal proof, but there is this fun theorem called period 3 implies chaos that my gut instinct says applies here.

Basically if you have a continuous mapping from [a,b] -> [a,b] and there exists a 3 cycle then that implies every other cycle length exists.

Which in this case would kinda say that if you are bouncing between three values on the y axis (and the bouncing is a continuous function which admittedly the gradient of a relu is not) you are probably in a chaotic system

Now that requires assuming that the behaviour of y is largely a function of just y. But their derivation seems to imply that it is the case.

Post reply on HN