ICML 2026poster0 citations
Allocating Variance to Maximize Expectation
Renato Leme, Clifford Stein, Yifeng Teng, Pratik Worah
Abstract
We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let $OPT:=\max_{\sigma_1,\cdots,\sigma_n}\mathbb{E}\sum_{j=1}^{m}\max_{i\in S_j} X_i$, 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 OPT when $m=1$, and - An $O(\log n)$ approximation algorithm for computing OPT for general $m>1$.
BibTeX
@inproceedings{
leme2026allocating,
title={Allocating Variance to Maximize Expectation},
author={Renato Paes Leme and Clifford Stein and Yifeng Teng and Pratik Worah},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=vqxprtjuKH}
}