Allocating Variance to Maximize Expectation

Abstract

We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let $\mathrm{OPT}:={\max }_{\ddot{I}{ƒ}_1,\cdots ,\ddot{I}{ƒ}_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\ddot{I}{ƒ}_i^2=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 $\mathrm{OPT}$ when $m=1$, and - An $O(\log n)$ approximation algorithm for computing $\mathrm{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.