On getting stranded in local minima...
I was having my weekly "two retired guys chatting about stuff" lunch over Zoom with my friend Tom, and I was discussing my experience with polonius, my Monte Carlo Tree Search based checkers program that I had tinkered together with the aid of Claude Code. The project has largely stalled, having reached a good level of play, but is unable to proceed against very strong opponents. I was lamenting that it seemed to be orbiting some local minima, and I was wondering if we had to prod it in some way to avoid the minima and proceed to stronger play.
Tom suggested that might not be the case, citing "a paper" that showed that in low dimensional optimization landscapes, local minima can be problematic, but that the higher the dimension, the problem becomes less and less important. This morning I did a bit of research to track down the primary sources, and arrived these two:
- Choromanska, A., Henaff, M., Mathieu, M., Arous, G. B., & LeCun, Y. (2014). The Loss Surfaces of Multilayer Networks. arXiv.
- Dauphin, Y., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. arXiv.
The intuition of this is perhaps not as surprising as I originally imagined. To be considered a local minima, the gradient of the loss function must be zero (if it weren't zero, you'd step in the direction that reduces the loss function) and the second derivatives must be positive in every direction. The second bit is the thing that makes search spaces with high dimenionality unlikely, in fact, exponentially unlikely. It would be like flipping a coin thousands or millions of times, and getting heads every single time. If one fails, your optimizer will step in that direction and accelerate away from the critical point.
These two results are what make neural network training tractable. When trying to optimize a network via back propagation, you are going to find the global minima with high probability, because the dimensionality of the problem is so high.
I'm not certain that these results mean that I am not in a local minima with polonius. I can be reasonably certain that the networks are not being trained into a local minima, but I am uncertain that this applies uniformly to the entire system. It's not yet breakfast time, and I don't feel I've got the mental horsepower to define or absorb the remaining issues. Perhaps after some Trader Joes "Fruity Cuties" with milk, and the fog will part. But it does suggest to me a different way to think about/approach the problem with slightly more knowledge than I had before, which I think is necessary to break the impass that I had before.
Hope you all are having a good Friday.
Addendum:
Instead of waiting for the Fruity Cuties to kick in, I decided to ask Google Gemini to read my blog post and give me its critique, telling me where my conclusions have gone astray. It identified three different issues. I think that criticism 1 and 2 are pretty much just me being informal in my language: both point at subtle points which I perhaps glossed over in building my mental model of what was going on, but item 3 below probably is at the heart of why the results of these two papers don't give the magic path away from its current local minima.
Without further critique, here is Gemini's critique:
Gemini's critique:
Here is a critique of the technical claims and logic presented in the post:
1. Misinterpreting the core conclusion of the cited papers You claim that because of the high dimensionality of neural networks, "you are going to find the global minima with high probability." This is factually incorrect and misrepresents the Dauphin and Choromanska papers you linked. Those papers do not prove that SGD finds the global minimum. Instead, they demonstrate that in high-dimensional spaces, most local minima are functionally equivalent and have loss values very close to the global minimum. The primary obstacle identified by Dauphin et al. is that optimization gets drastically slowed down by saddle points—regions where the gradient is near zero but not all second derivatives are positive. You don't magically reach the global minimum; you just land in a local minimum that is "good enough," or you get bogged down in a saddle point.
2. The "Coin Flip" analogy for the Hessian is mathematically flawed You describe the probability of finding a local minimum (all positive second derivatives) as being like "flipping a coin thousands or millions of times, and getting heads every single time." This assumes the dimensions (eigenvalues of the Hessian matrix) are independent and randomly distributed like a uniform coin toss. They aren't. The parameter space of a neural network is highly correlated, and the Hessian spectrum is heavily skewed. Most eigenvalues in these models are concentrated at or extremely close to zero, meaning the landscape is dominated by flat valleys and ridges, not a perfectly symmetrical distribution of positive and negative curvatures.
3. Conflating supervised learning loss surfaces with Reinforcement Learning dynamics You are trying to apply supervised learning loss-surface theorems to an AlphaZero-style self-play system (MCTS + Neural Net). If your Checkers agent has plateaued, looking at the static loss surface of the network is looking in the wrong place. In self-play, the environment is non-stationary; the target is constantly moving as the agent updates. The agent isn't stuck in a geometric "local minimum" of a fixed loss function; it is likely stuck in a suboptimal Nash equilibrium or an RL policy trap. It has simply overfit to its own specific blind spots because it only plays against itself.
Rather than waiting for the "Fruity Cuties" to induce an epiphany about 2014 loss surface geometry, you should be looking at standard RL exploration fixes: increasing the Dirichlet noise at your MCTS root node, tweaking your exploration temperature, expanding network capacity, or maintaining a diverse pool of historical opponents to prevent catastrophic forgetting.