Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.18463 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912245800239104 |
|---|---|
| author | Leme, Renato Purita Paes Stein, Cliff Teng, Yifeng Worah, Pratik |
| author_facet | Leme, Renato Purita Paes Stein, Cliff Teng, Yifeng Worah, Pratik |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_18463 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Allocating Variance to Maximize Expectation Leme, Renato Purita Paes Stein, Cliff Teng, Yifeng Worah, Pratik Machine Learning 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. |
| title | Allocating Variance to Maximize Expectation |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.18463 |