# Allocating Variance to Maximize Expectation

arXiv: https://arxiv.org/abs/2502.18463 · HTML: https://mlsanity.com/paper/2502.18463/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 18 references that are in the map.
- First posted on arXiv 25 Feb 2025.

## Builds on (most cited first, 5 of 5)

- [Wide Neural Networks as Gaussian Processes: Lessons from Deep Equilibrium Models](https://mlsanity.com/paper/2310.10767/) (2023)
- [Deterministic Algorithms for Submodular Maximization Problems](https://mlsanity.com/paper/1508.02157/) (2015)
- [Best-Effort Adaptation](https://mlsanity.com/paper/2305.05816/) (2023)
- [Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint](https://mlsanity.com/paper/2408.03583/) (2024)
- [Calibrated Click-Through Auctions: An Information Design Approach](https://mlsanity.com/paper/2105.09375/) (2021)

## Abstract (arXiv)

We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let OPT:=maxσ1,cdots,σnmathbbEleft[sumj=1mmaxi∈ Sj Xiright], where Xi are Gaussian, Sjsubset[n] and sumiσi2=1, then our theoretical results include: - We characterize the optimal variance allocation -- it concentrates on a small subset of variables as |Sj| 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. Such expectation maximization problems occur in diverse applications, ranging from utility maximization in auctions markets to learning mixture models in quantitative genetics.