Let a set of $N$ pairs of matched measured points $p_i, c_i$ with some noise. Using an optimization method, we optimize a model $m$ that estimates $\hat{c_i}$ from $p_i$: $$\hat{c_i} = m(p_i)$$
Usually, the real-mean-square-error (rmse), is of an $O(n)$ computational complexity. However, due to the nature of my specific model, I am trying to assess the rmse of a specific parameter in the model $x_i$. For that, specific parameter, a correct estimation of the rmse would be of an $O(n^2)$ computational complexity. This is because I need to traverse all possible pairs of $((p_i,c_i),(p_j,c_j))$ for this specific parameter.
The purpose of estimating the rmse in my case, is to get a confidence measure for the current case. Is it possible to estimate such a confidence level in $O(n)$? Can I randomize sets of pairs and get a sense of the confidence without covering all the combinations of all the points? If so, what are the recommended methods to do so?