SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2205.15213 · ICLR · 2023

Backpropagation through Combinatorial Algorithms: Identity with Projection Works

Anselm Paulus, Vít Musil, Georg Martius, Volodymyr Kuleshov, Subham Sahoo, Marin Vlastelica

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

Embedding discrete solvers as differentiable layers has given modern deep learning architectures combinatorial expressivity and discrete reasoning capabilities. The derivative of these solvers is zero or undefined, therefore a meaningful replacement is crucial for effective gradient-based learning. Prior works rely on smoothing the solver with input perturbations, relaxing the solver to continuous problems, or interpolating the loss landscape with techniques that typically require additional solver calls, introduce extra hyper-parameters, or compromise performance. 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 and further provide a theoretical justification. Our experiments demonstrate that such a straightforward hyperparameter-free approach is able to compete with previous more complex methods on numerous experiments such as backpropagation through discrete samplers, deep graph matching, and image retrieval. Furthermore, we substitute the previously proposed problem-specific and label-dependent margin with a generic regularization procedure that prevents cost collapse and increases robustness. Code is available at github.com/martius-lab/solver-differentiation-identity.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2205.15213")
get_code_for_paper("2205.15213")
have("2205.15213")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2205.15213.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2205.15213.svg)](https://syntology.ai/paper/2205.15213)

Connect an agent — have() is free.