提出自适应加权平均法，高效选出最大值且不劣于随机选择。
Adaptive Weighted Averaging
- 基于每个值的单次无偏估计，设计自适应加权策略
- 在任何情况下都不劣于随机选，良性环境下显著更优
- 适用于在线转批量优化，无需妥协性能
我们研究从n个未知值x₁,…,xₙ中选出最大值的问题，仅能获得每个xᵢ的一个无偏估计yᵢ。设计出同时具有可接纳性（不被任何其他策略整体超越）和不低于基准策略（如均匀随机选择）性能的策略。该方法应用于随机优化，实现了在线到批量转换的边界，具备‘无妥协’特性：性能始终不低于标准随机迭代选择，而在有利条件下可显著更优。
原文摘要 · Abstract (English)
We study the problem of selecting the largest among $n$ unknown values $x_1,\dots,x_n$ given only a single unbiased estimate $y_i$ for each $x_i$. We design strategies that are simultaneously admissible (not uniformly dominated by any other strategy) and also never worse than a given baseline such as uniform random selection. We provide an application to stochastic optimization, where we obtain online-to-batch conversion bounds with a desirable "no-compromise" guarantee: they are never worse than standard random iterate selection, and yet can be significantly better in benign settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。