Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian

Jack Parker-Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair Letcher, Alexander Peysakhovich, Aldo Pacchiano, Jakob N. Foerster

TL;DR

Ridge Rider (RR) is a novel optimization framework that moves beyond the "greedy" nature of Stochastic Gradient Descent (SGD). Instead of following the gradient, RR follows the eigenvectors of the Hessian—referred to as "ridges"—to explore the loss landscape. By systematically branching along these ridges, RR discovers diverse, high-quality solutions that standard methods often miss, proving particularly effective for challenges like zero-shot coordination and out-of-distribution generalization.

The Problem with Greedy Optimization

In deep learning, Stochastic Gradient Descent (SGD) is the standard tool for minimizing loss functions. While SGD excels at finding a local minimum, it is inherently "greedy," following the path of steepest descent to the nearest basin. However, complex loss landscapes often contain multiple minima with similar loss values but vastly different properties.

For instance, in computer vision, one minimum might rely on "easy" texture features that generalize poorly, while another relies on "hard" shape features that generalize well. In multi-agent reinforcement learning, "self-play" often leads to idiosyncratic strategies, making it impossible for an agent to coordinate with a new partner. Standard optimization does not distinguish between these minima, but in many real-world scenarios, the type of solution matters immensely.

The Ridge Rider Approach

The authors propose Ridge Rider (RR), an algorithm that treats optimization as a search process through the curvature of the loss landscape.

  1. Following Ridges: Instead of following the gradient ($\nabla L$), RR follows the eigenvectors of the Hessian matrix ($H = \nabla^2 L$). These eigenvectors represent directions of principal curvature. Following directions of negative curvature leads to new minima.
  2. Branching: RR starts at a "Maximally Invariant Saddle" (often near zero initialization). From there, it branches by choosing different eigenvectors to follow.
  3. Iterative Exploration: The algorithm follows a chosen ridge until the loss stops decreasing or the curvature changes significantly, then it branches again. This creates a unique "fingerprint"—a sequence of ridge choices—that identifies a specific solution.
  4. Scaling to Deep Networks: Because computing the full Hessian is computationally prohibitive for large models, the authors developed an Approximate RR. This version uses efficient Hessian-vector products and the power method to find the most relevant eigenvectors without materializing the full matrix.
Comparison of Gradient Descent and Ridge Rider on a 2D loss surface. While GD gets trapped in the nearest basins, RR explores multiple paths along eigenvectors to find diverse minima.

Key Insights

  • Optimization as Search: RR converts continuous optimization into a discrete search over ridges. This allows it to bypass local minima that would trap a gradient-based optimizer.
  • Exploiting Symmetry: Many problems possess symmetries (e.g., permuting colors in a game) that lead to repeated eigenvalues in the Hessian. RR leverages this mathematical property to avoid redundant exploration and focus on qualitatively different solutions.
  • Sidestepping Goodhart’s Law: By finding a diverse set of solutions using only the training set and then selecting the best one via a validation set, RR avoids over-optimizing for generalization metrics that are often impossible to target directly.
  • Consistency for Coordination: Because the ordering of eigenvectors is consistent, two independently trained agents using RR are more likely to follow the same ridges and arrive at compatible strategies, enabling zero-shot coordination.

Experimental Results

The authors evaluated RR across several distinct domains, including a synthetic binary tree environment for reinforcement learning, a lever coordination game, and standard/Colored MNIST datasets.

  • Reinforcement Learning: In the binary tree task, RR found over 90% of the possible positive solutions, whereas standard Gradient Descent found fewer than 50% across various depths.
Ridge Rider significantly outperforms baselines in finding positive solutions across different depths in the tree environment.
  • Zero-Shot Coordination: In the lever game, RR successfully identified the ideal coordinated strategy that self-play SGD consistently missed.
  • Out-of-Distribution Generalization: On Colored MNIST, where color is a misleading spurious correlation, RR achieved 58.4% test accuracy. Standard Empirical Risk Minimization (ERM) collapsed to 17.8%, while specialized causal methods achieve roughly 66-70%. RR achieved this without being explicitly told which features were spurious.
  • Supervised Learning: RR reached ~98% accuracy on standard MNIST, demonstrating that following eigenvectors is a viable way to train neural networks.

Limitations and Future Work

While promising, RR faces several hurdles for widespread adoption. Even with Hessian-vector products, it is significantly more computationally expensive than SGD. Furthermore, the current method is sensitive to noise, making adaptation to mini-batch noise in large-scale settings a major open challenge. Finally, the branching logic and heuristics require careful hyperparameter tuning. Future work will explore better ways to sample eigenvectors and apply RR to more complex multi-agent environments.

Summary updated

Abstract

Over the last decade, a single algorithm has changed many facets of our lives - Stochastic Gradient Descent (SGD). In the era of ever decreasing loss functions, SGD and its various offspring have become the go-to optimization tool in machine learning and are a key component of the success of deep neural networks (DNNs). While SGD is guaranteed to converge to a local optimum (under loose assumptions), in some cases it may matter which local optimum is found, and this is often context-dependent. Examples frequently arise in machine learning, from shape-versus-texture-features to ensemble methods and zero-shot coordination. In these settings, there are desired solutions which SGD on <code>standard' loss functions will not find, since it instead converges to the</code>easy' solutions. In this paper, we present a different approach. Rather than following the gradient, which corresponds to a locally greedy direction, we instead follow the eigenvectors of the Hessian. By iteratively following and branching amongst the ridges, we effectively span the loss surface to find qualitatively different solutions. We show both theoretically and experimentally that our method, called Ridge Rider (RR), offers a promising direction for a variety of challenging problems.
BibTeX
@inproceedings{parkerholder2020ridge,
  author = {Jack Parker-Holder and Luke Metz and Cinjon Resnick and Hengyuan Hu and Adam Lerer and Alistair Letcher and Alexander Peysakhovich and Aldo Pacchiano and Jakob N. Foerster},
  title = {{Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=UETqbaxQgR},
}
Figure