Optimization Online


Computation of exact bootstrap confidence intervals: complexity and deterministic algorithms

Dimitris Bertsimas(dbertsim***at***mit.edu)
Bradley Sturt(bsturt***at***mit.edu)

Abstract: The bootstrap is a nonparametric approach for calculating quantities, such as confidence intervals, directly from data. Since calculating exact bootstrap quantities is believed to be intractable, randomized resampling algorithms are traditionally used. Motivated by the fact that the variability from randomization can lead to inaccurate outputs, we propose a deterministic approach. First, we establish several computational complexity results for the exact bootstrap method, in the case of the sample mean. Second, we present the first efficient, deterministic approximation algorithm (FPTAS) for producing exact bootstrap confidence intervals which, unlike traditional methods, has guaranteed bounds on the approximation error. Third, we develop a simple exact algorithm for exact bootstrap confidence intervals based on polynomial multiplication. We provide empirical evidence involving several hundreds (and in some cases over one thousand) data points that the proposed deterministic algorithms can quickly produce confidence intervals that are substantially more accurate compared to those from randomized methods, and are thus practical alternatives in applications such as clinical trials.

Keywords: Bootstrap method, computational complexity, deterministic approximation algorithms, integral points in polyhedra, Monte Carlo simulation.

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 09/18/2017
Entry Accepted: 09/18/2017
Entry Last Modified: 09/18/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society