# Bootstrap on a weighted subset

My group is developing an ML algorithm. We have a number of validation datasets we use to compare variants of the algorithm, but the validation is expensive in the sense that to test $m$ variants on a dataset of size $n$ we have to make $mn$ queries to a black box which evaluates the performance, and there is a hard limit on the number of queries we can make per day. We would like $n$ to be large, so the observed differences in performance are significant, but if we could decrease $n$ without losing significance, we could test more variants per day. Of course we should eventually be concerned about overfitting the validation set, but if possible let's ignore that for now.

Currently we run all the queries mentioned above to get scalars $x_{ij}$ indicating how well variant $i$ performed on example $j$. We then average over $j$ to get an estimate $\overline{x}_i$ of the quality of variant $i$. To see how significant variation in the $\overline{x}_i$ is, we use the bootstrap to construct a confidence interval $I_i$ for the true performance of variant $i$ on the whole population. We should be wary of comparing these independently-computed confidence intervals for lots of different variants, but unless it's absolutely essential let's ignore this for the sake of this question.

With the goal of decreasing $n$, I took a bunch of data of the type mentioned above and used Lasso to find a bias $b$ and sparse weights $w_j$ such that $\overline{x}_i \approx b + \sum_j w_j x_{ij}$. The intent is to use this estimator going forward to evaluate variants by only querying the black box on the $n_0 = \#\{j \mid w_j\neq 0\}$ examples with nonzero weights.

The question is: how can I form confidence intervals for the population mean for this method? To be clear, unlike other work I've found searching for "bootstrap lasso", I'm not looking at confidence intervals for some "true $w_j$". The fact that the $w_j$ are unequal means I can't just blindly apply the bootstrap to the subset of examples with nonzero $w_j$. I could require the $w_j$ to be nonnegative and then bootstrap samples from the empirical distribution weighted by the weights $\frac{w_j}{\sum_k w_k}$, but then it's not clear how many points to sample from this weighted distribution: $n$? $n_0$?

I can look at the statistics of the residuals from the Lasso on my cross-validation data to get an idea of how accurate and precise the estimator is, but I would like some measure that includes those effects and also attempts to capture variation from the population mean, like the bootstrap did in the initial setup with $n$ equally-weighted examples.

I am also open to alternative ways to approximate $\overline{x}_i$ using a subset of the $n$ examples besides the simple Lasso I did if they would make obtaining a confidence interval easier.