Backpropagation through combinatorial algorithms: identity with
projection works

k 2023

Backpropagation through combinatorial algorithms: identity with projection works

SUBHAM SEKHAR, Sahoo; Anselm PAULUS; Marin VLASTELICA; Vít MUSIL; Volodymyr KULESHOV et. al.

Základní údaje

Originální název

Backpropagation through combinatorial algorithms: identity with projection works

Autoři

SUBHAM SEKHAR, Sahoo; Anselm PAULUS; Marin VLASTELICA; Vít MUSIL; Volodymyr KULESHOV a Georg MARTIUS

Vydání

11th International Conference on Learning Representations, ICLR 2023, 2023

Další údaje

Jazyk

angličtina

Typ výsledku

Prezentace na konferencích

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Poster, Openreview

Kód RIV

RIV/00216224:14330/23:00137556

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Machine learning; combinatorial optimization

Štítky

core_A, firank_1, Formela

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 7. 11. 2024 15:08, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

The result is a paper (27 pages) at the International Conference on Learning Representations. Although this is one of the very best conferences in CS, the proceedings do not have an ISBN or ISSN, so the result cannot be added to the RIV database as a type D result. The original abstract is as follows: 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 hyper-parameter-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.

Návaznosti

EF18_053/0016952, projekt VaV

Název: Postdoc2MUNI

GA23-06963S, projekt VaV

Název: VESCAA: Verifikovatelná a efektivní syntéza kontrolerů pro autonomní agenty

Investor: Grantová agentura ČR, VESCAA: Verifikovatelná a efektivní syntéza kontrolerů pro autonomní agenty

Citovat

SUBHAM SEKHAR, Sahoo; Anselm PAULUS; Marin VLASTELICA; Vít MUSIL; Volodymyr KULESHOV a Georg MARTIUS. Backpropagation through combinatorial algorithms: identity with projection works. In 11th International Conference on Learning Representations, ICLR 2023. 2023.

@proceedings{2449790,
   author = {Subham Sekhar, Sahoo and Paulus, Anselm and Vlastelica, Marin and Musil, Vít and Kuleshov, Volodymyr and Martius, Georg},
   booktitle = {11th International Conference on Learning Representations, ICLR 2023},
   keywords = {Machine learning; combinatorial optimization},
   language = {eng},
   title = {Backpropagation through combinatorial algorithms: identity with projection works},
   url = {https://openreview.net/forum?id=JZMR727O29},
   year = {2023}
}

TY  - CONF
ID  - 2449790
AU  - Subham Sekhar, Sahoo - Paulus, Anselm - Vlastelica, Marin - Musil, Vít - Kuleshov, Volodymyr - Martius, Georg
PY  - 2023
TI  - Backpropagation through combinatorial algorithms: identity with projection works
KW  - Machine learning
KW  - combinatorial optimization
UR  - https://openreview.net/forum?id=JZMR727O29
N2  - The result is a paper (27 pages) at the International Conference on Learning Representations. Although this is one of the very best conferences in CS, the proceedings do not have an ISBN or ISSN, so the result cannot be added to the RIV database as a type D result. The original abstract is as follows: 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 hyper-parameter-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.
ER  -

SUBHAM SEKHAR, Sahoo; Anselm PAULUS; Marin VLASTELICA; Vít MUSIL; Volodymyr KULESHOV a Georg MARTIUS. Backpropagation through combinatorial algorithms: identity with projection works. In \textit{11th International Conference on Learning Representations, ICLR 2023}. 2023.

Přehled o publikaci