2025/02/25 by Renato Paes Leme, Leme, Renato Purita Paes, Clifford Stein +5
Decision Sciences · #Simulation Techniques and Applications
paper · pdf · doi:10.48550/arxiv.2502.18463
We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let OPT:=maxσ1,⋯,σn𝔼[∑j=1mmaxi∈ Sj Xi], where Xi are Gaussian, Sj⊂[n] and ∑iσ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.