Allocating Variance to Maximize Expectation

We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let OPT:=maxσ1,cdots,σnmathbbEleft[sumj=1mmaxi∈ Sj Xiright], where Xi are Gaussian, Sjsubset[n] and sumiσi2=1, then our theoretical results include: - We characterize the optimal variance allocation -- it concentrates on a small subset of variables as |Sj| increases, - A polynomial time approximation scheme (PTAS) for computing OPT when m=1, and - An O(log n) approximation algorithm for computing OPT for general m>1. Such expectation maximization problems occur in diverse applications, ranging from utility maximization in auctions markets to learning mixture models in quantitative genetics.