How to construct confidence intervals for sum of dependent random variables. Specifically, I want a high probability claim regarding the difference between the empirical mean and the true mean of the sum.

There are two general approaches to construction of CI I'm aware of:

  1. based on finite sample probability bounds for measure concentration, such as Chernoff and Hoeffding bounds.
  2. based on Central Limit Theorem arguments, in which case the problem translates to estimating/bounding the variance.

Yet, these hold for independent r.v. (I'm aware of concentration bounds that assume some type of dependency, like Azuma-Hoeffding, but I don't have this type of dependency).

How do I approach the problem for dependent r.v? A reference to a relevant book that discusses the subject would be great.

edit - My specific mean is the Leave-One-Out-CV loss (not the zero-one loss) of a binary classifier. So, there is a dependency between the losses, because of overlapping training sets. I know the variation of this loss around the true loss (i.e. generalization loss) is usually analyzed by stability of the learning alg. I wanted to check if I can bound this deviation without stability using CI.

  • 1
    $\begingroup$ There are central limit theorems for dependent random variables. If you can say something about the distribution you may be able to do other things. $\endgroup$ – Glen_b Jan 22 '15 at 8:02
  • $\begingroup$ H. White's book Asymptotic Theory for Econometricians in my opinion has a very nice list of CLT results for dependent variables. $\endgroup$ – mpiktas Jan 22 '15 at 8:17
  • $\begingroup$ What do you know about the form of the dependence? Without knowing/assuming somethingh here, it will be difficult. $\endgroup$ – kjetil b halvorsen Jan 22 '15 at 11:32
  • $\begingroup$ kjetil - since I'm looking at cross-validation loss I would expect the dependency to be positive. Namely, since the training sets overlap, if one test set has a low loss it implies the others also have a low loss. This intuition is more from k-fold cross validation rather than LOOCV. $\endgroup$ – M-H Jan 22 '15 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.