Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization

By Bryan Wilder, Bistra N. Dilkina, Milind Tambe. AAAI Conference on Artificial Intelligence, 2018

390 citations recorded by the source corpus.

Creating impact in real-world settings requires artificial intelligence techniques to span the full pipeline from data, to predictive models, to decisions. These components are typically approached separately: a machine learning model is first trained via a measure of predictive accuracy, and then its predictions are used as input into an optimization algorithm which produces a decision. However, the loss function used to train the model may easily be misaligned with the end goal, which is to make the best decisions possible. Hand-tuning the loss function to align with optimization is a difficult and error-prone process (which is often skipped entirely).We focus on combinatorial optimization problems and introduce a general framework for decision-focused learning, where the machine learning model is directly trained in conjunction with the optimization algorithm to produce highquality decisions. Technically, our contribution is a means of integrating common classes of discrete optimization problems into deep learning or other predictive models, which are typically trained via gradient descent. The main idea is to use a continuous relaxation of the discrete problem to propagate gradients through the optimization procedure. We instantiate this framework for two broad classes of combinatorial problems: linear programs and submodular maximization. Experimental results across a variety of domains show that decisionfocused learning often leads to improved optimization performance compared to traditional methods. We find that standard measures of accuracy are not a reliable proxy for a predictive model’s utility in optimization, and our method’s ability to specify the true goal as the model’s training objective yields substantial dividends across a range of decision problems.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/015a9bec58a53f64c19a59fedea51c68d6a741f1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Lagrangian Duality for Constrained Deep Learning (2020, background): “Another line of work leverages explicit optimization algorithms as a differentiable layer into neural networks [4,13,34].”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, positive): “Wilder et al. (2019a) also note the nondifferentiability of SPO loss and modify the objective function of the nominal optimization problem to derive a differentiable, surrogate loss function.”
POPCORN: Partially Observed Prediction COnstrained ReiNforcement Learning (2020, methodology): “, 2011) to submodular optimization (Wilder et al., 2019).”
Differentiable Convex Optimization Layers (2019, background): “These layers have found several applications [40, 6, 35, 27, 5, 53, 75, 52, 12, 11], but many applications remain relatively unexplored (see, e.g. , [4, §8]).”
SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver (2019, background): “…previous work has introduced differentiable modules for quadratic programs (Amos & Kolter, 2017; Donti et al., 2017), submodular optimization problems (Djolonga & Krause, 2017; Tschiatschek et al., 2018; Wilder et al., 2018), and equilibrium computation in zero-sum games (Ling et al., 2018).”
Tackling Climate Change with Machine Learning (2019, background): “[60] Bryan Wilder, Bistra Dilkina, and Milind Tambe.”