Can I read Allocating Variance to Maximize Expectation on EtoBox?

Allocating Variance to Maximize Expectation by Leme, Renato Purita Paes; Stein, Cliff; Teng, Yifeng; Worah, Pratik is a scholarly article available to read on EtoBox.

What is Allocating Variance to Maximize Expectation about?

We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let $\mathrm{OPT}:=\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 $|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.

Author

Leme, Renato Purita Paes; Stein, Cliff; Teng, Yifeng; Worah, Pratik

Published

2025

Language

EN