Stochastic Optimization Forests

• URL: http://arxiv.org/abs/2008.07473v6
• Date: Wed, 16 Mar 2022 06:26:45 GMT
• Title: Stochastic Optimization Forests
• Authors: Nathan Kallus and Xiaojie Mao
• Abstract summary: We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
• Score: 60.523606291705214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study contextual stochastic optimization problems, where we leverage rich auxiliary observations (e.g., product characteristics) to improve decision making with uncertain variables (e.g., demand). We show how to train forest decision policies for this problem by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We realize this seemingly computationally intractable problem by developing approximate splitting criteria that utilize optimization perturbation analysis to eschew burdensome re-optimization for every candidate split, so that our method scales to large-scale problems. We prove that our splitting criteria consistently approximate the true risk and that our method achieves asymptotic optimality. We extensively validate our method empirically, demonstrating the value of optimization-aware construction of forests and the success of our efficient approximations. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.

Related papers

• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  We use predictions to improve over approximation guarantees of classic algorithms. Our algorithms produce optimal solutions when provided with perfect predictions. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds.
  arXiv  Detail & Related papers  (2024-11-25T17:31:34Z)
• Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions [15.396561118589577]
  performative risk minimization is a formulation of optimization under decision-dependent distributions. Our algorithms significantly improve upon existing Lipschitz constant distribution parameter-based methods. We provide experimental results that demonstrate the numerical superiority of our algorithms over the existing method and other black-box optimistic optimization methods.
  arXiv  Detail & Related papers  (2024-02-23T08:36:28Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Robust Optimal Classification Trees Against Adversarial Examples [5.254093731341154]
  We propose a collection of methods to train decision trees that are optimally robust against user-specified attack models. We show that the min-max optimization problem that arises in adversarial learning can be solved using a single minimization formulation. We also present a method that determines the upper bound on adversarial accuracy for any model using bipartite matching.
  arXiv  Detail & Related papers  (2021-09-08T18:10:49Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling. We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  Batch policy optimization considers leveraging existing data for policy construction before interacting with an environment. We show that any confidence-adjusted index algorithm is minimax optimal, whether it be optimistic, pessimistic or neutral. We introduce a new weighted-minimax criterion that considers the inherent difficulty of optimal value prediction.
  arXiv  Detail & Related papers  (2021-04-06T05:23:20Z)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  We show that common optimization methods lead to poor variational approximations if the problem is moderately large. Motivated by these findings, we develop a more robust and accurate optimization framework by viewing the underlying algorithm as producing a Markov chain.
  arXiv  Detail & Related papers  (2020-09-01T19:12:11Z)
• Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees [28.46586066038317]
  We provide the first efficient implementation of general multi-stepahead look Bayesian optimization. Instead of solving these problems in a nested way, we equivalently optimize all decision variables in the full tree jointly. We demonstrate that multistep expected improvement is tractable and exhibits performance superior to existing methods on a wide range of benchmarks.
  arXiv  Detail & Related papers  (2020-06-29T02:17:18Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)

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.