On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization

Abstract

Some recent works in machine learning and computer vision involve the solution of a bi-level optimization problem. Here the solution of a parameterized lower-level problem binds variables that appear in the objective of an upper-level problem. The lower-level problem typically appears as an argmin or argmax optimization problem. Many techniques have been proposed to solve bi-level optimization problems, including gradient descent, which is popular with current end-to-end learning approaches. In this technical report we collect some results on differentiating argmin and argmax optimization problems with and without constraints and provide some insightful motivating examples.

16 pages, 6 figures

References in corpus (1)

• Deep Learning in Neural Networks: An Overview

Cited by in corpus (53)

• OptNet: Differentiable Optimization as a Layer in Neural Networks
• Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities
• DeepEMD: Differentiable Earth Mover's Distance for Few-Shot Learning
• Efficient and Modular Implicit Differentiation
• Bilevel methods for image reconstruction
• Adaptively Sparse Transformers
• Video Representation Learning Using Discriminative Pooling
• Generalized Rank Pooling for Activity Recognition
• Truncated Back-propagation for Bilevel Optimization
• PINQI: An End-to-End Physics-Informed Approach to Learned Quantitative MRI Reconstruction
• Sinkformers: Transformers with Doubly Stochastic Attention
• Monotone operator equilibrium networks
• A Neural Network Architecture to Learn Explicit MPC Controllers from Data
• Action Recognition with Dynamic Image Networks
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• Hyperbolic Deep Neural Networks: A Survey
• Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
• Provably Faster Algorithms for Bilevel Optimization
• LP-SparseMAP: Differentiable Relaxed Optimization for Sparse Structured Prediction
• Backpropagation of Unrolled Solvers with Folded Optimization
• Solving Structured Hierarchical Games Using Differential Backward Induction
• Statistical Performance of Radio Interferometric Calibration
• Fast UAV Trajectory Optimization using Bilevel Optimization with Analytical Gradients
• The Differentiable Cross-Entropy Method
• Total Least Squares Phase Retrieval
• End-to-End Learnable Geometric Vision by Backpropagating PnP Optimization
• UFO-BLO: Unbiased First-Order Bilevel Optimization
• Implicitly Defined Layers in Neural Networks
• Using Affective Features from Media Content Metadata for Better Movie Recommendations
• Feature Attributions and Counterfactual Explanations Can Be Manipulated
• Sign-MAML: Efficient Model-Agnostic Meta-Learning by SignSGD
• Dense Non-Rigid Structure from Motion: A Manifold Viewpoint
• Counterfactual Explanations Can Be Manipulated
• NOVAS: Non-convex Optimization via Adaptive Stochastic Search for End-to-End Learning and Control
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Large Scale Learning of Agent Rationality in Two-Player Zero-Sum Games
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization
• Discriminatively Learned Hierarchical Rank Pooling Networks
• Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation
• Birds of a Feather Flock Together: A Close Look at Cooperation Emergence via Multi-Agent RL
• Differentiating through the Fréchet Mean
• Convergent Graph Solvers
• Neural Fixed-Point Acceleration for Convex Optimization
• Contrastive Video Representation Learning via Adversarial Perturbations
• Proximal Mapping for Deep Regularization
• Joint Unsupervised Learning of Optical Flow and Egomotion with Bi-Level Optimization
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems
• The Contextual Appointment Scheduling Problem
• Discriminative Video Representation Learning Using Support Vector Classifiers
• Joint Mapping and Calibration via Differentiable Sensor Fusion
• Debiasing a First-order Heuristic for Approximate Bi-level Optimization
• Fairness without Regret
• Generalized One-Class Learning Using Pairs of Complementary Classifiers