Timezone: »
Bilevel optimization problems involve two nested objectives, where an upper-level objective depends on a solution to a lower-level problem. When the latter is non-convex, multiple critical points may be present, leading to an ambiguous definition of the problem. In this paper, we introduce a key ingredient for resolving this ambiguity through the concept of a selection map which allows one to choose a particular solution to the lower-level problem. Using such maps, we define a class of hierarchical games between two agents that resolve the ambiguity in bilevel problems. This new class of games requires introducing new analytical tools in Morse theory to extend implicit differentiation, a technique used in bilevel optimization resulting from the implicit function theorem. In particular, we establish the validity of such a method even when the latter theorem is inapplicable due to degenerate critical points.Finally, we show that algorithms for solving bilevel problems based on unrolled optimization solve these games up to approximation errors due to finite computational power. A simple correction to these algorithms is then proposed for removing these errors.
Author Information
Michael Arbel (INRIA)
Julien Mairal (Inria)
More from the Same Authors
-
2021 Spotlight: Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization »
Gaspard Beugnot · Julien Mairal · Alessandro Rudi -
2022 : Fair Synthetic Data Does not Necessarily Lead to Fair Models »
Yam Eitan · Nathan Cavaglione · Michael Arbel · Samuel Cohen -
2021 Poster: KALE Flow: A Relaxed KL Gradient Flow for Probabilities with Disjoint Support »
Pierre Glaser · Michael Arbel · Arthur Gretton -
2021 Poster: Tactical Optimism and Pessimism for Deep Reinforcement Learning »
Ted Moskovitz · Jack Parker-Holder · Aldo Pacchiano · Michael Arbel · Michael Jordan -
2021 Poster: A Trainable Spectral-Spatial Sparse Coding Model for Hyperspectral Image Restoration »
Theo Bodrito · Alexandre Zouaoui · Jocelyn Chanussot · Julien Mairal -
2021 Poster: Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization »
Gaspard Beugnot · Julien Mairal · Alessandro Rudi -
2020 Poster: Unsupervised Learning of Visual Features by Contrasting Cluster Assignments »
Mathilde Caron · Ishan Misra · Julien Mairal · Priya Goyal · Piotr Bojanowski · Armand Joulin -
2020 Poster: A Non-Asymptotic Analysis for Stein Variational Gradient Descent »
Anna Korba · Adil Salim · Michael Arbel · Giulia Luise · Arthur Gretton -
2020 Poster: A Flexible Framework for Designing Trainable Priors with Adaptive Smoothing and Game Encoding »
Bruno Lecouat · Jean Ponce · Julien Mairal -
2020 : Discussion Panel: Hugo Larochelle, Finale Doshi-Velez, Devi Parikh, Marc Deisenroth, Julien Mairal, Katja Hofmann, Phillip Isola, and Michael Bowling »
Hugo Larochelle · Finale Doshi-Velez · Marc Deisenroth · Devi Parikh · Julien Mairal · Katja Hofmann · Phillip Isola · Michael Bowling -
2019 Poster: On the Inductive Bias of Neural Tangent Kernels »
Alberto Bietti · Julien Mairal -
2019 Poster: Recurrent Kernel Networks »
Dexiong Chen · Laurent Jacob · Julien Mairal -
2019 Poster: A Generic Acceleration Framework for Stochastic Composite Optimization »
Andrei Kulunchakov · Julien Mairal -
2019 Poster: Maximum Mean Discrepancy Gradient Flow »
Michael Arbel · Anna Korba · Adil Salim · Arthur Gretton -
2018 Poster: Unsupervised Learning of Artistic Styles with Archetypal Style Analysis »
Daan Wynen · Cordelia Schmid · Julien Mairal -
2018 Poster: On gradient regularizers for MMD GANs »
Michael Arbel · Danica J. Sutherland · Mikołaj Bińkowski · Arthur Gretton -
2017 Poster: Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure »
Alberto Bietti · Julien Mairal -
2017 Spotlight: Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure »
Alberto Bietti · Julien Mairal -
2017 Poster: Learning Neural Representations of Human Cognition across Many fMRI Studies »
Arthur Mensch · Julien Mairal · Danilo Bzdok · Bertrand Thirion · Gael Varoquaux -
2017 Poster: Invariance and Stability of Deep Convolutional Representations »
Alberto Bietti · Julien Mairal -
2016 Poster: End-to-End Kernel Learning with Supervised Convolutional Kernel Networks »
Julien Mairal -
2015 Poster: A Universal Catalyst for First-Order Optimization »
Hongzhou Lin · Julien Mairal · Zaid Harchaoui -
2014 Poster: Convolutional Kernel Networks »
Julien Mairal · Piotr Koniusz · Zaid Harchaoui · Cordelia Schmid -
2014 Spotlight: Convolutional Kernel Networks »
Julien Mairal · Piotr Koniusz · Zaid Harchaoui · Cordelia Schmid -
2013 Poster: Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization »
Julien Mairal -
2010 Poster: Network Flow Algorithms for Structured Sparsity »
Julien Mairal · Rodolphe Jenatton · Guillaume R Obozinski · Francis Bach -
2008 Poster: SDL: Supervised Dictionary Learning »
Julien Mairal · Francis Bach · Jean A Ponce · Guillermo Sapiro · Andrew Zisserman