优化高斯变量期望上确界，找到最优方差分配策略
Allocating Variance to Maximize Expectation
- 通过集中方差到少数关键变量实现期望最大化
- 当m=1时可多项式时间求解，一般情况有log n近似算法
- 适用于拍卖机制设计和基因混合模型学习等场景
我们设计了高效近似算法，用于最大化高斯随机变量族上确界的期望。具体地，设 $ℭ\mathrm{OPT}:=\max_{σ_1,\cdots,σ_n}\mathbb{E}\left[\sum_{j=1}^{m}\max_{i\in S_j} X_i\right]$，其中 $X_i$ 为高斯变量，$S_j\subset[n]$ 且 $\sum_iσ_i^2=1$。理论结果包括：(1) 揭示最优方差分配——随着 $|S_j|$ 增大，方差集中在少数变量上；(2) 当 $m=1$ 时存在多项式时间近似方案（PTAS）；(3) 对任意 $m>1$ 可实现 $O(\log n)$ 近似。此类期望最大化问题广泛存在于拍卖市场效用优化、定量遗传学中的混合模型学习等领域。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。