Gradient descent (Not ML) on arbitrary meshes
Maybe you can find a heuristic to detect when it gets stuck (e.g. gradient magnitude is too small, or it stays on the same triangle or returns to a recently visited triangle too many times in a row, or it hasn't moved at least X distance over the last N steps, etc) and just take a random step in some direction, e.g. to some randomly chosen neighboring triangle? That might help shake it out of the difficult region and get back to smooth descent.
For an even lower-tech solution, if you don't mind some randomness you could just inject occasional random moves all the time (without attempting to detect whether it's stuck). Kind of like stochastic gradient descent in ML.
If the gradient you're following is a geodesic distance, I think it can have saddle points, but not local minima (except for the global minimum), is that right? If that's a constraint you can rely on, you could try to use a second-order method, finding an estimate of the local Hessian and looking for eigenvectors with negative eigenvalues, which should be directions of principal curvature that will accelerate the gradient descent, and in particular, will pull you out of saddle points. I'm sure there must be a literature on such methods although I don't know much about it.