Rétropropagation à travers les algorithmes combinatoires : l'identité avec projection fonctionne

Intégrer des solveurs discrets sous forme de couches différentiables a conféré aux architectures modernes d'apprentissage profond une expressivité combinatoire et des capacités de raisonnement discret. Toutefois, la dérivée de ces solveurs est nulle ou non définie, ce qui rend indispensable la mise en place d'une approximation significative pour permettre un apprentissage efficace basé sur les gradients. Les travaux antérieurs s'appuient sur des techniques telles que le lissage du solveur par perturbations d'entrée, la relaxation du problème vers un cadre continu, ou encore l'interpolation du paysage de perte par des méthodes qui nécessitent généralement des appels supplémentaires au solveur, introduisent des hyperparamètres supplémentaires ou compromettent les performances. Nous proposons une approche fondée sur la géométrie de l'espace des solutions discrètes, permettant de traiter le solveur comme une identité négative lors du passage arrière, tout en offrant une justification théorique rigoureuse. Nos expériences montrent que cette approche simple, dépourvue d'hyperparamètres, est en mesure de rivaliser avec des méthodes plus complexes sur de nombreux benchmarks, notamment le rétropropagation à travers des échantillonneurs discrets, le matching de graphes profonds et la récupération d'images. En outre, nous remplaçons la marge spécifique au problème et dépendante des étiquettes proposée précédemment par une procédure de régularisation générique, qui empêche le phénomène de « collapse du coût » et améliore la robustesse.