Allocating Variance to Maximize Expectation
This addresses expectation maximization problems in applications like auctions and genetics, but it is incremental as it builds on existing algorithmic frameworks.
The paper tackles the problem of maximizing the expectation of the supremum of Gaussian random variables by designing efficient approximation algorithms, achieving a PTAS for m=1 and an O(log n) approximation for general m>1.
We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let $\mathrm{OPT}:=\max_{σ_1,\cdots,σ_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σ_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.