Optimal Observation-Intervention Trade-Off in Optimisation Problems with Causal Structure

• URL: http://arxiv.org/abs/2309.02287v1
• Date: Tue, 5 Sep 2023 14:46:06 GMT
• Title: Optimal Observation-Intervention Trade-Off in Optimisation Problems with Causal Structure
• Authors: Kim Hammar and Neil Dhir
• Abstract summary: We show that observation-intervention trade-off can be formulated as a non-myopic optimal stopping problem. We show that our formulation can enhance existing algorithms on real and synthetic benchmarks.
• Score: 1.724169474984623
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider the problem of optimising an expensive-to-evaluate grey-box objective function, within a finite budget, where known side-information exists in the form of the causal structure between the design variables. Standard black-box optimisation ignores the causal structure, often making it inefficient and expensive. The few existing methods that consider the causal structure are myopic and do not fully accommodate the observation-intervention trade-off that emerges when estimating causal effects. In this paper, we show that the observation-intervention trade-off can be formulated as a non-myopic optimal stopping problem which permits an efficient solution. We give theoretical results detailing the structure of the optimal stopping times and demonstrate the generality of our approach by showing that it can be integrated with existing causal Bayesian optimisation algorithms. Experimental results show that our formulation can enhance existing algorithms on real and synthetic benchmarks.

Related papers

• Graph Agnostic Causal Bayesian Optimisation [2.624902795082451]
  We study the problem of globally optimising a target variable of an unknown causal graph on which a sequence of soft or hard interventions can be performed. We propose Graph Agnostic Causal Bayesian optimisation (GACBO), an algorithm that actively discovers the causal structure that contributes to achieving optimal rewards. We show our proposed algorithm outperforms baselines in simulated experiments and real-world applications.
  arXiv  Detail & Related papers  (2024-11-05T11:49:33Z)
• Constrained Bayesian Optimization Under Partial Observations: Balanced Improvements and Provable Convergence [6.461785985849886]
  We endeavor to design an efficient and provable method for expensive POCOPs under the framework of constrained Bayesian optimization. We present an improved design of the acquisition functions that introduces balanced exploration during optimization. We propose a Gaussian process embedding different likelihoods as the surrogate model for a partially observable constraint.
  arXiv  Detail & Related papers  (2023-12-06T01:00:07Z)
• 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)
• Model-based Causal Bayesian Optimization [78.120734120667]
  We propose model-based causal Bayesian optimization (MCBO) MCBO learns a full system model instead of only modeling intervention-reward pairs. Unlike in standard Bayesian optimization, our acquisition function cannot be evaluated in closed form.
  arXiv  Detail & Related papers  (2022-11-18T14:28:21Z)
• Causal Entropy Optimization [12.708838587765307]
  We propose a framework that generalizes Causal Bayesian Optimization (CBO) to account for all sources of uncertainty. CEO incorporates the causal structure uncertainty both in the surrogate models for the causal effects and in the mechanism used to select interventions. CEO achieves faster convergence to the global optimum compared with CBO while also learning the graph.
  arXiv  Detail & Related papers  (2022-08-23T13:58:09Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• Quantum variational optimization: The role of entanglement and problem hardness [0.0]
  We study the role of entanglement, the structure of the variational quantum circuit, and the structure of the optimization problem. Our numerical results indicate an advantage in adapting the distribution of entangling gates to the problem's topology. We find evidence that applying conditional value at risk type cost functions improves the optimization, increasing the probability of overlap with the optimal solutions.
  arXiv  Detail & Related papers  (2021-03-26T14:06:54Z)
• Causal Bayesian Optimization [8.958125394444679]
  We study the problem of globally optimizing a variable of interest that is part of a causal model in which a sequence of interventions can be performed. Our approach combines ideas from causal inference, uncertainty quantification and sequential decision making. We show how knowing the causal graph significantly improves the ability to reason about optimal decision making strategies.
  arXiv  Detail & Related papers  (2020-05-24T13:20:50Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  We propose and analyze a novel theoretical and algorithmic framework for structured prediction. We study a large class of loss functions that implicitly defines a suitable geometry on the problem. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.
  arXiv  Detail & Related papers  (2020-02-13T10:30:04Z)

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.