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,••• ,σn E m j=1 max i∈Sj X i , where X i are Gaussian, S j ⊂ [n] and i σ 2 i = 1, then our theoretical results include: • We characterize the optimal variance allocation -it concentrates on a small subset of variables as |S j | 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.