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 $\mathrm{O}\mathrm{P}\mathrm{T}:={\max }_{{\sigma }_1,\cdots ,{\sigma }_n}\mathbb{E}\left[{\sum }_{j=1}^m{\max }_{i\in S_j}{X}_i\right]$, where $X_i$ are Gaussian, $S_j\subset [n]$ and ${\sum }_i{\sigma }_i^2=1$, then our theoretical results include: - We characterize the optimal variance allocation – it concentrates on a small subset of variables as $\mathrm{\mid }{S}_j\mathrm{\mid }$ increases, - A polynomial time approximation scheme (PTAS) for computing $\mathrm{O}\mathrm{P}\mathrm{T}$ when $m=1$, and - An $O(\log n)$ approximation algorithm for computing $\mathrm{O}\mathrm{P}\mathrm{T}$ 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.