Algorithms for Solving Nonlinear Binary Optimization Problems in Robust
Causal Inference
- URL: http://arxiv.org/abs/2012.12130v1
- Date: Tue, 22 Dec 2020 16:12:11 GMT
- Title: Algorithms for Solving Nonlinear Binary Optimization Problems in Robust
Causal Inference
- Authors: Md Saiful Islam, Md Sarowar Morshed, and Md. Noor-E-Alam
- Abstract summary: We propose greedy algorithms to solve the robust causal inference test instances from observational data with continuous outcomes.
By leveraging the structure of the feasibility formulation, we develop greedy schemes that are efficient in solving robust test problems.
- Score: 2.169755083801688
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Identifying cause-effect relation among variables is a key step in the
decision-making process. While causal inference requires randomized
experiments, researchers and policymakers are increasingly using observational
studies to test causal hypotheses due to the wide availability of observational
data and the infeasibility of experiments. The matching method is the most used
technique to make causal inference from observational data. However, the pair
assignment process in one-to-one matching creates uncertainty in the inference
because of different choices made by the experimenter. Recently, discrete
optimization models are proposed to tackle such uncertainty. Although a robust
inference is possible with discrete optimization models, they produce nonlinear
problems and lack scalability. In this work, we propose greedy algorithms to
solve the robust causal inference test instances from observational data with
continuous outcomes. We propose a unique framework to reformulate the nonlinear
binary optimization problems as feasibility problems. By leveraging the
structure of the feasibility formulation, we develop greedy schemes that are
efficient in solving robust test problems. In many cases, the proposed
algorithms achieve global optimal solution. We perform experiments on three
real-world datasets to demonstrate the effectiveness of the proposed algorithms
and compare our result with the state-of-the-art solver. Our experiments show
that the proposed algorithms significantly outperform the exact method in terms
of computation time while achieving the same conclusion for causal tests. Both
numerical experiments and complexity analysis demonstrate that the proposed
algorithms ensure the scalability required for harnessing the power of big data
in the decision-making process.
Related papers
- Globally-Optimal Greedy Experiment Selection for Active Sequential
Estimation [1.1530723302736279]
We study the problem of active sequential estimation, which involves adaptively selecting experiments for sequentially collected data.
The goal is to design experiment selection rules for more accurate model estimation.
We propose a class of greedy experiment selection methods and provide statistical analysis for the maximum likelihood.
arXiv Detail & Related papers (2024-02-13T17:09:29Z) - Comparison of Single- and Multi- Objective Optimization Quality for
Evolutionary Equation Discovery [77.34726150561087]
Evolutionary differential equation discovery proved to be a tool to obtain equations with less a priori assumptions.
The proposed comparison approach is shown on classical model examples -- Burgers equation, wave equation, and Korteweg - de Vries equation.
arXiv Detail & Related papers (2023-06-29T15:37:19Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm.
The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources.
It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
arXiv Detail & Related papers (2022-12-06T12:42:11Z) - Efficient Learning of Decision-Making Models: A Penalty Block Coordinate
Descent Algorithm for Data-Driven Inverse Optimization [12.610576072466895]
We consider the inverse problem where we use prior decision data to uncover the underlying decision-making process.
This statistical learning problem is referred to as data-driven inverse optimization.
We propose an efficient block coordinate descent-based algorithm to solve large problem instances.
arXiv Detail & Related papers (2022-10-27T12:52:56Z) - The Statistical Complexity of Interactive Decision Making [126.04974881555094]
We provide a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning.
A unified algorithm design principle, Estimation-to-Decisions (E2D), transforms any algorithm for supervised estimation into an online algorithm for decision making.
arXiv Detail & Related papers (2021-12-27T02:53:44Z) - 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) - Sample Selection for Fair and Robust Training [28.94276265328868]
We propose a sample selection-based algorithm for fair and robust training.
We show that our algorithm obtains fairness and robustness better than or comparable to the state-of-the-art technique.
arXiv Detail & Related papers (2021-10-27T07:17:29Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together.
The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively.
Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
arXiv Detail & Related papers (2021-03-10T03:16:12Z) - Data-Driven Robust Optimization using Unsupervised Deep Learning [0.0]
We show that a trained neural network can be integrated into a robust optimization model by formulating the adversarial problem as a convex mixed-integer program.
We find that this approach outperforms a similar approach using kernel-based support vector sets.
arXiv Detail & Related papers (2020-11-19T11:06:54Z) - Learning while Respecting Privacy and Robustness to Distributional
Uncertainties and Adversarial Data [66.78671826743884]
The distributionally robust optimization framework is considered for training a parametric model.
The objective is to endow the trained model with robustness against adversarially manipulated input data.
Proposed algorithms offer robustness with little overhead.
arXiv Detail & Related papers (2020-07-07T18:25:25Z)
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.