Nonparametric bootstrap: Circular reasoning behind colleague's comments?

Question

I have developed an iterative stochastic optimization search procedure that improves on a single initial guess until some desired threshold is reached, similar to how simulated annealing proceeds toward an optimal solution.

Briefly, my algorithm samples values randomly with replacement in the closed interval [1,..., $m$] according to some known probability distribution for $n$ subjects (individuals), where $m \leq n$. This sampling is repeated $p$ times (by default, 10000 times). The $np$ values are then placed on a grid, call it grid1, of size $p$ rows by $n$ columns. The $n$ individuals (columns) are then selected at random, one-by-one, without replacement and the cumulative mean number of unique values found for all $n$ individuals (columns) across all $p$ rows is calculated. The results are then placed into a new grid, grid 2, and fed into a custom function that computes a quality score (similar to how a fitness function calculates solution merit). This information is used to calculate an improved value of $n$, call it $n'$ If the mean for the last column in grid2 is not equal to $m$, then grid1 is expanded to contain $n'-n$ additional columns appended to the end. The process is then repeated anew until convergence is reached..

As a small example, the resulting grid1 along which means are computed might look like this (for $m$ = $n$ = $p$ = 4). Suppose further that the $m$ values are sampled uniformly (i.e., each $m_i$ has a $\frac{1}{m}=\frac{1}{4}$ chance of being selected):

1 3 4 2

2 2 4 1

3 1 4 2

4 2 3 3

The developed procedure is quite computationally-intensive for large $m$, $n$ and $p$ for single runs.

The Problem

When explaining to my colleagues (who are biologists) about how my algorithm works, I simply state that "it works like bootstrapping", leaving out the obvious subtleties. I use this analogy because the bootstrap is a statistical term that is (at least a bit) familiar to them.

A colleague unfamiliar with metaheuristics and optimization theory, stated to me: "We need to run your algorithm 10000 times to prove that the answer gets better with more trials." That is, the colleague was suggesting to let the already time-consuming algorithm converge once, and then follow this with 9999 more runs.

I replied that the suggested scheme was unnecessary, because with a larger value of $p$ (rows) in grid1, Monte Carlo error will decrease.

Clearly, the (Weak) Law of Large Numbers is at work here.

My Question: What is the best course of action here: run once with $p$ = 10000 rows, or run $p$ = 10000 times, each with $p$ = 10000 rows?

I realize variance reduction could be an option here, but to me it would seem challenging to implement in the given context.

Edit: @Ben - Reinstate Monica gave a nice general answer as to how best to proceed. This leads to a related question (though I don't think necessary of a new post, more to quell my sanity). My algorithm is essentially a resampling scheme, where each of the $p$ rows can be thought of as a "bootstrap sample". Why then isn't bootstrapping performed a large number of times, i.e., why isn't run the boot() R function once, followed by 9999 more times, each run generating 10000 bootstrap samples under the hood? Clearly, we don't do this in practice since sometimes the statistic being bootstrapped is complex or costly to evaluate. This is my logic in explaining to colleagues why I haven't run my algorithm 10000 times.

I realize there is the related concept of bootstrap iteration (iterative bootstrap) (Chernick, 2007, 2011), which is essentially a nested bootstrap (bootstrap within a bootstrap), which is also very computationally-demanding.

Answer 1

It sounds like your colleague wants you to demonstrate that your method works better as you take more iterations, which is a perfectly reasonable request. If you want to demonstrate this by simulation, this would entail generating a large number of "searches" that your algorithm generates for values $i=1,2,...,p$, and showing that the outcomes tend to be better as the iteration index $i$ gets larger. This could be done by simulation.

Your description of the problem you are trying to solve, and the algorithm itself, are both very poor, so I'm afraid I cannot make any sense of it. This really doesn't matter too much, because ultimately it is some algorithm that generates a "guess" of something using an iterative process. So what you need to do is to show that this "guess" tends to get better as you take more iterations. To do this, suppose you generate $S$ simulations of your search algorithm in some problem, each going up to $p$ iterations. (Make sure your algorithm is programmed so that it can retain every iteration for each simulation.) Let $x_{i,s}$ denote the $i$th iteration of the $s$th simulation. Then the vector of "guesses" $\mathbf{x}_{i} \equiv (x_{i,1},..., x_{i,S})$ are all the simulated guesses on the $i$th iteration. Generate some measure of aggregate "loss" for these guesses, and call this:

$$L_i = f(\mathbf{x}_{i}).$$

You now have loss values $L_1,...,L_p$ that measure the (aggregate) inaccuracy of your guesses at each iteration. If you compute this for a large number of simulations $S$ then this should give you a reasonable sense of how good the guesses are at each iteration. If you can show that the "loss" tends to decrease as $i=1,...,p$ increases, then than will confirm that the guesses tend to get better as you use more iterations.

In terms of computational complexity, this simulation method requires you to generate $S$ simulations of $p$ iterations. If your method is computationally intensive, you may need to think about an appropriate trade-off between the number of iterations and the number of simulations (or maybe just run the calculations over a long period of time). It seems unusual to me that an algorithm would take $p=10^4$ iterations to converge to a good output, so it might be worth thinking about whether such a large number of iterations is necessary.

Answer 2

I've done some digging on CV and my question posed in the Edit of my post essentially boils down to how many runs of a simulation need to be performed to assess "confidence" in outputted results.

I have found several answers in this regard, all pointing to the equivalence (via convergence in probability and in respect to the estimating the population mean) of

(1) running a single simulation with $mn$ replications, then reporting the estimated mean

(2) running $m$ simulations, each with $n$ replications and then averaging the results.

Advantage of multiple simulations in old-fashioned Monte Carlo?

averaging after n trials of monte carlo simulation or not? which is better statistically?

I also recall reading a comment by @whuber some time ago indicating that the bootstrap does not require simulation, but I can't seem to find the particular post where this comment is stated. Regardless, bootstrapping clearly falls into category (1) above. We do not run the boot() R function $n$ = 10000 times (say) where each run averages over $m$ = 10000 replications; instead, we draw simply draw $n$ 10000 bootstrap samples for a single simulation ($m$ = 1), find the sample mean, and then call it a day. However, there is no reason why we can't simply adopt option (2) for bootstrapping -- we just have to be very patient.

Option (1) can greatly save on CPU time and RAM, especially if simulations are computationally-intensive.

In the end, it seems that both my colleague and I are correct in our thinking, it's just a matter of how much time one has (and wishes) to devote.