Experimental Designs for Heteroskedastic Variance

Most linear experimental design problems assume homogeneous variance, even though heteroskedastic noise is present in many realistic settings. Let a learner have access to a finite set of measurement vectors that can be probed to receive linear responses with heteroskedastic noise. The heteroskedastic variances of these responses are functions of the measurement vectors and an unknown parameter. We propose, analyze and empirically evaluate a novel design for uniformly bounding estimation error of the variance parameters. We demonstrate the benefits of this method with two adaptive experimental design problems under heteroskedastic noise, fixed confidence transductive best-arm identification, and level-set identification; proving the first instance-dependent lower bounds in these settings. Lastly, we construct near-optimal algorithms and empirically demonstrate the large improvements in sample complexity gained from accounting for heteroskedastic variance in these designs.

In Advances in Neural Information Processing Systems, 36