NeFut Logo NeFut
EN 管理员登录

[算法理论] Pareto 秘书问题

发布于:2026-11-02 22:00 最后更新:2026-11-03 01:04
#algorithm #optimization #Math

Pareto 秘书问题研究在 i.i.d. 样本流中在线挑选一个 Pareto‑最大观测,即不存在其他观测在所有坐标上不劣且在至少一个坐标上更好。\ \ 对任意固定维度 $d\ge2$ 且各坐标独立连续分布,最优的失败概率量级为 $\frac{1}{(\log n)^{d-1}\log\log n}$,该结果在拥有完整观测信息和仅使用坐标秩两种情形下均成立。一个确定性的秩规则在所有边缘分布上实现该前导项。\ \ 若坐标服从任意正定高斯协方差,同样的失败量级保持不变,常数由相关矩阵决定;而基于秩的规则无需知道高斯参数即可达到最优前导失败概率。\ \ 在上述两种模型中,我们求得最优的固定截断点及其前导常数;其失败概率比无约束的最优多一个因子 $\Theta_d((\log\log n)^2)$。\ \ 在任意依赖结构下,若联合密度固定且边缘均匀分布,则全信息下的成功率可以趋近约 $0.58$。\ \ 证明核心利用支配概率极小的观测极其稀缺的事实,对任意停止规则给出上界。匹配规则在当前支配概率低于随时间递增的阈值时选取当前的极大点。通过初始样本得到的坐标秩能够提供足够精确的概率估计,从而保持最优的前导失败概率。\ \ 对已知相关性的奇异高斯分布,我们给出使用秩能够实现的最优失败渐近;奇异依赖可以使每个观测都可接受,或恢复选择唯一最佳点的难度。\ \ 点评

原文链接: https://arxiv.org/abs/2610.42101

[h] 返回首页