English
Learning with differentiable perturbed optimizers
Post-edited
Auteurs : Berthet, Quentin (Auteur de la conférence)
CIRM (Editeur )
62F99 - None of the above but in this section
68W20 - randomized algorithms
90C06 - Large-scale problems
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2133/Slides/perturbations_berthet.pdf
CIRM (Editeur )
Résumé :
Machine learning pipelines often rely on optimization procedures to make discrete decisions (e.g. sorting, picking closest neighbors, finding shortest paths or optimal matchings). Although these discrete decisions are easily computed in a forward manner, they cannot be used to modify model parameters using first-order optimization techniques because they break the back-propagation of computational graphs. In order to expand the scope of learning problems that can be solved in an end-to-end fashion, we propose a systematic method to transform a block that outputs an optimal discrete decision into a differentiable operation. Our approach relies on stochastic perturbations of these parameters, and can be used readily within existing solvers without the need for ad hoc regularization or smoothing. These perturbed optimizers yield solutions that are differentiable and never locally constant. The amount of smoothness can be tuned via the chosen noise amplitude, whose impact we analyze. The derivatives of these perturbed solvers can be evaluated eciently. We also show how this framework can be connected to a family of losses developed in structured prediction, and describe how these can be used in unsupervised and supervised learning, with theoretical guarantees.
We demonstrate the performance of our approach on several machine learning tasks in experiments on synthetic and real data.
Mots-Clés : perturbation methods; structured learning
Codes MSC : We demonstrate the performance of our approach on several machine learning tasks in experiments on synthetic and real data.
Mots-Clés : perturbation methods; structured learning
62F99 - None of the above but in this section
68W20 - randomized algorithms
90C06 - Large-scale problems
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2133/Slides/perturbations_berthet.pdf
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de Publication : 06/04/2020 Date de Captation : 09/03/2020 Sous Collection : Research talks Catégorie arXiv : Machine Learning ; Optimization and Control Domaine(s) : Informatique ; Théorie du Contrôle & Optimisation Format : MP4 (.mp4) - HD Durée : 00:50:11 Audience : Chercheurs Download : https://videos.cirm-math.fr/20120-03-09_Berthet.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : Optimization for Machine Learning / Optimisation pour l'apprentissage automatiqueOrganisateurs de la Rencontre : Boyer, Claire ; d'Aspremont, Alexandre ; Gramfort, Alexandre ; Salmon, Joseph ; Villar, Soledad Dates : 09/03/2020 - 13/03/2020 Année de la rencontre : 2020 URL de la Rencontre : https://conferences.cirm-math.fr/2133.html
Données de citation
DOI : 10.24350/CIRM.V.19622903Citer cette vidéo: Berthet, Quentin (2020). Learning with differentiable perturbed optimizers. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19622903 URI : http://dx.doi.org/10.24350/CIRM.V.19622903 |
Voir Aussi
- [Multi angle] Rank optimality for the Burer-Monteiro factorization / Auteur de la conférence Waldspurger, Irène.
- [Multi angle] What does back propagation compute? / Auteur de la conférence Pauwels, Edouard.
- [Multi angle] Bridging the gap between optimal transport and MMD Sinkhorn divergences / Auteur de la conférence Genevay, Aude.
- [Multi angle] Gradient descent for wide two-layer neural networks / Auteur de la conférence Bach, Francis.
Bibliographie
- PAPANDREOU, George et YUILLE, Alan L. Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models. In : 2011 International Conference on Computer Vision. IEEE, 2011. p. 193-200. - https://doi.org/10.1109/ICCV.2011.6126242
- KALAI, Adam et VEMPALA, Santosh. Efficient algorithms for online decision problems. In : Learning Theory and Kernel Machines. Springer, Berlin, Heidelberg, 2003. p. 26-40. - http://dx.doi.org/10.1007/978-3-540-45167-9_4
- BERTHET, Quentin, BLONDEL, Mathieu, TEBOUL, Olivier, et al. Learning with Differentiable Perturbed Optimizers. arXiv preprint arXiv:2002.08676, 2020. - https://arxiv.org/abs/2002.08676
