Lyapunov Exponents for Diversity in Differentiable Games

• URL: http://arxiv.org/abs/2112.14570v1
• Date: Fri, 24 Dec 2021 22:48:14 GMT
• Title: Lyapunov Exponents for Diversity in Differentiable Games
• Authors: Jonathan Lorraine, Paul Vicol, Jack Parker-Holder, Tal Kachman, Luke Metz, Jakob Foerster
• Abstract summary: Ridge Rider (RR) is an algorithm for finding diverse solutions to optimization problems by following eigenvectors of the Hessian ("ridges" RR is designed for conservative gradient systems, where it branches at saddles - easy-to-find bifurcation points. We propose a method - denoted Generalized Ridge Rider (GRR) - for finding arbitrary bifurcation points.
• Score: 19.16909724435523
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ridge Rider (RR) is an algorithm for finding diverse solutions to optimization problems by following eigenvectors of the Hessian ("ridges"). RR is designed for conservative gradient systems (i.e., settings involving a single loss function), where it branches at saddles - easy-to-find bifurcation points. We generalize this idea to non-conservative, multi-agent gradient systems by proposing a method - denoted Generalized Ridge Rider (GRR) - for finding arbitrary bifurcation points. We give theoretical motivation for our method by leveraging machinery from the field of dynamical systems. We construct novel toy problems where we can visualize new phenomena while giving insight into high-dimensional problems of interest. Finally, we empirically evaluate our method by finding diverse solutions in the iterated prisoners' dilemma and relevant machine learning problems including generative adversarial networks.

Related papers

• ODE Discovery for Longitudinal Heterogeneous Treatment Effects Inference [69.24516189971929]
  In this paper, we introduce a new type of solution in the longitudinal setting: a closed-form ordinary differential equation (ODE) While we still rely on continuous optimization to learn an ODE, the resulting inference machine is no longer a neural network.
  arXiv  Detail & Related papers  (2024-03-16T02:07:45Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• Gradient Backpropagation Through Combinatorial Algorithms: Identity with Projection Works [20.324159725851235]
  A meaningful replacement for zero or undefined solvers is crucial for effective gradient-based learning. We propose a principled approach to exploit the geometry of the discrete solution space to treat the solver as a negative identity on the backward pass.
  arXiv  Detail & Related papers  (2022-05-30T16:17:09Z)
• A Variational Inference Approach to Inverse Problems with Gamma Hyperpriors [60.489902135153415]
  This paper introduces a variational iterative alternating scheme for hierarchical inverse problems with gamma hyperpriors. The proposed variational inference approach yields accurate reconstruction, provides meaningful uncertainty quantification, and is easy to implement.
  arXiv  Detail & Related papers  (2021-11-26T06:33:29Z)
• Multivariate Deep Evidential Regression [77.34726150561087]
  A new approach with uncertainty-aware neural networks shows promise over traditional deterministic methods. We discuss three issues with a proposed solution to extract aleatoric and epistemic uncertainties from regression-based neural networks.
  arXiv  Detail & Related papers  (2021-04-13T12:20:18Z)
• Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian [48.61341260604871]
  Gradient Descent (SGD) is a key component of the success of deep neural networks (DNNs) In this paper, we present a different approach by following the eigenvectors of the Hessian, which we call "ridges" We show both theoretically and experimentally that our method, called Ridge Rider (RR), offers a promising direction for a variety of challenging problems.
  arXiv  Detail & Related papers  (2020-11-12T17:15:09Z)
• Newton Optimization on Helmholtz Decomposition for Continuous Games [47.42898331586512]
  NOHD is a Newton-like algorithm for multi-agent learning problems based on the decomposition of the dynamics of the system. We show that NOHD is attracted to stable fixed points in general multi-agent systems and repelled by strict saddle ones.
  arXiv  Detail & Related papers  (2020-07-15T16:26:33Z)
• Stochastic gradient algorithms from ODE splitting perspective [0.0]
  We present a different view on optimization, which goes back to the splitting schemes for approximate solutions of ODE. In this work, we provide a connection between descent approach and gradient first-order splitting scheme for ODE. We consider the special case of splitting, which is inspired by machine learning applications and derive a new upper bound on the global splitting error for it.
  arXiv  Detail & Related papers  (2020-04-19T22:45:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.