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

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

Introduction

Standard optimization algorithms like Stochastic Gradient Descent (SGD) are inherently "greedy." They follow the steepest path down a loss landscape, often converging to the most accessible local minima. While efficient, this approach frequently misses qualitatively different solutions that might offer better generalization or robustness. Ridge Rider (RR) is a novel framework designed to overcome this limitation by following the eigenvectors of the Hessian—the "ridges" of the loss landscape—to systematically explore diverse solutions that SGD typically overlooks.

The Challenge of Shortcut Solutions

In deep learning, minimizing a loss function is rarely the ultimate goal. We seek models that generalize to unseen data, remain robust to noise, and can coordinate effectively with other agents. However, non-convex loss landscapes are riddled with local minima. SGD tends to find "shortcut" solutions—for instance, a vision model might identify a "dog" based on background texture rather than shape because texture is easier to optimize. Once committed to such a path, SGD rarely deviates.

Directly optimizing for properties like generalization often triggers Goodhart’s Law: "When a measure becomes a target, it ceases to be a good measure." Instead of direct optimization, the authors propose discovering a diverse set of solutions and then selecting the most suitable one.

Methods: From Gradient to Curvature

The core innovation of Ridge Rider is the shift from gradient-following to curvature-following.

Visualization of Ridge Rider following eigenvectors (ridges) in a loss landscape compared to standard gradient descent.
  1. Maximally Invariant Saddle (MIS): RR begins at an MIS, typically near zero initialization, where the gradient is minimal and the model hasn't yet committed to a specific feature path.
  2. Following Ridges: From the MIS, the algorithm calculates the eigenvectors of the Hessian matrix. These eigenvectors represent directions of principal curvature. RR "branches" out by following these "ridges."
  3. Iterative Branching: As the algorithm traverses a ridge, the Hessian evolves. RR iteratively updates its direction to remain on the ridge. This process transforms a continuous optimization problem into a discrete search tree of potential solutions.
  4. Scalability: To handle large networks where computing a full Hessian is intractable, the authors developed Approximate RR. This version utilizes Hessian-vector products and power iteration to efficiently track the most significant ridges.

Experimental Evaluation

The authors evaluated Ridge Rider across several distinct domains:

  • Toy Binary Tree (RL): A synthetic environment requiring an agent to find multiple paths to positive rewards.
  • MNIST & Colored MNIST: Used to test if different ridges correspond to learning different digits and to evaluate Out-of-Distribution (OOD) generalization. In Colored MNIST, color is a spurious correlation, while digit shape is the causal feature.
  • Lever Coordination Game: A game theory benchmark where agents must choose the same lever as a stranger without communication, necessitating the discovery of a "uniquely identifiable" solution.

Key Insights

  • Optimization as Search: RR reframes deep learning as a search through a "fingerprint" of different ridges, each representing a distinct strategy.
  • Symmetry Breaking: The paper links problem symmetries to the Hessian. Symmetries result in repeated eigenvalues; by following distinct eigenvectors, RR systematically breaks these symmetries to find unique solutions.
  • Bypassing Shortcuts: In Colored MNIST, RR successfully ignored the "easy" color feature to find the "harder" digit-shape feature, suggesting causal features often lie along different ridges than the spurious ones.

Key Results

Ridge Rider demonstrated significant improvements over standard methods in exploration and generalization tasks.

Performance of Ridge Rider vs. baselines on the Toy Binary Tree task. RR consistently finds a higher percentage of solutions across various tree depths.
  • Exploration in RL: In the binary tree task, RR discovered over 90% of possible solutions, while Gradient Descent found at most 50%.
  • OOD Generalization: On Colored MNIST, standard Empirical Risk Minimization (ERM) achieved 87% training accuracy but only 17.8% on the test set due to color reliance. RR achieved 58.4% test accuracy, successfully identifying causal features.
  • Coordination: In the lever game, RR identified the "0.6 payoff" lever—the only uniquely identifiable option—enabling perfect zero-shot coordination where self-play methods failed.

Limitations and Future Work

Despite its success, Ridge Rider is computationally more intensive than SGD due to Hessian-vector product calculations. Scaling to massive architectures will require more efficient handling of Hessian estimation noise. Additionally, as the number of ridges grows, the search space expands significantly. Future research will focus on better "EndRide" heuristics and prioritized ridge exploration.

Summary updated

BibTeX
@inproceedings{parkerholder2020ridge,
  author = {Jack Parker-Holder and Luke Metz and Cinjon Resnick and Hengyuan Hu and Adam Lerer and Alistair Letcher and Alex 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