Automatically Learning Compact Quality-aware Surrogates for Optimization Problems

• URL: http://arxiv.org/abs/2006.10815v2
• Date: Thu, 22 Oct 2020 05:05:21 GMT
• Title: Automatically Learning Compact Quality-aware Surrogates for Optimization Problems
• Authors: Kai Wang, Bryan Wilder, Andrew Perrault, Milind Tambe
• Abstract summary: Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
• Score: 55.94450542785096
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving optimization problems with unknown parameters often requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in the model training pipeline results in predictions of the unobserved parameters that lead to higher decision quality. Unfortunately, this process comes at a large computational cost because the optimization problem must be solved and differentiated through in each training iteration; furthermore, it may also sometimes fail to improve solution quality due to non-smoothness issues that arise when training through a complex optimization layer. To address these shortcomings, we learn a low-dimensional surrogate model of a large optimization problem by representing the feasible space in terms of meta-variables, each of which is a linear combination of the original variables. By training a low-dimensional surrogate model end-to-end, and jointly with the predictive model, we achieve: i) a large reduction in training and inference time; and ii) improved performance by focusing attention on the more important variables in the optimization and learning in a smoother space. Empirically, we demonstrate these improvements on a non-convex adversary modeling task, a submodular recommendation task and a convex portfolio optimization task.

Related papers

• On characterizing optimal learning trajectories in a class of learning problems [0.0]
  This paper exploits the relationship between the maximum principle and dynamic programming for characterizing optimal learning trajectories in a class of learning problem. We provide an algorithmic recipe how to construct the corresponding optimal learning trajectories leading to the optimal estimated model parameters for such a class of learning problem.
  arXiv  Detail & Related papers  (2025-01-27T21:43:35Z)
• On improving generalization in a class of learning problems with the method of small parameters for weakly-controlled optimal gradient systems [0.0]
  We consider a variational problem for a weakly-controlled gradient system, whose control input enters into the system dynamics as a coefficient to a nonlinear term. Using the perturbation theory, we provide results that will allow us to solve a sequence of optimization problems. We also provide an estimate for the rate of convergence for such approximate optimal solutions.
  arXiv  Detail & Related papers  (2024-12-11T20:50:29Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and Optimization [59.386153202037086]
  Predict-Then- framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This approach can be inefficient and requires handcrafted, problem-specific rules for backpropagation through the optimization step. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by predictive models.
  arXiv  Detail & Related papers  (2023-11-22T01:32:06Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Careful! Training Relevance is Real [0.7742297876120561]
  We propose constraints designed to enforce training relevance. We show through a collection of experimental results that adding the suggested constraints significantly improves the quality of solutions.
  arXiv  Detail & Related papers  (2022-01-12T11:54:31Z)
• Bilevel Optimization for Differentially Private Optimization in Energy Systems [53.806512366696275]
  This paper studies how to apply differential privacy to constrained optimization problems whose inputs are sensitive. The paper shows that, under a natural assumption, a bilevel model can be solved efficiently for large-scale nonlinear optimization problems.
  arXiv  Detail & Related papers  (2020-01-26T20:15:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.