Learning with Differentiable Perturbed Optimizers
arXiv:2002.08676
Abstract
Machine learning pipelines often rely on optimization procedures to make discrete decisions (e.g., sorting, picking closest neighbors, or shortest paths). Although these discrete decisions are easily computed, 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 optimizers into operations that are differentiable and never locally constant. Our approach relies on stochastically perturbed optimizers, and can be used readily together with existing solvers. Their derivatives can be evaluated efficiently, and smoothness tuned via the chosen noise amplitude. We also show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks. We demonstrate experimentally the performance of our approach on various tasks.
References in corpus (3)
Cited by in corpus (21)
- A Survey of Contextual Optimization Methods for Decision Making under Uncertainty
- Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities
- A mathematical model for automatic differentiation in machine learning
- Gradient Estimation with Stochastic Softmax Tricks
- Learning Linear Programs from Optimal Decisions
- Differentiable Rendering with Perturbed Optimizers
- Decision-Oriented Learning for Future Power System Decision-Making under Uncertainty
- Learning Randomly Perturbed Structured Predictors for Direct Loss Minimization
- Understanding Deep Architectures with Reasoning Layer
- Regularization of Persistent Homology Gradient Computation
- Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels
- Efficient Video Transformers with Spatial-Temporal Token Selection
- Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach
- A Surrogate Objective Framework for Prediction+Optimization with Soft Constraints
- Learning Representations for Axis-Aligned Decision Forests through Input Perturbation
- Sparse Communication via Mixed Distributions
- Strategic Classification Made Practical
- Differentiable Spline Approximations
- Reconciling the Discrete-Continuous Divide: Towards a Mathematical Theory of Sparse Communication
- Robust Losses for Decision-Focused Learning
- Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications