Nov, 2023

具有单调概率的尖锐嘈杂的二分搜索

PDF
TL;DR我们重新审视了 Karp 和 Kleinberg 的嘈杂二分搜索模型，其中我们有 n 个具有未知概率 pi 的硬币可进行翻转。硬币按递增的 pi 排序，我们希望找到概率以 ε 为间隔交叉目标值 τ 的位置。我们通过解决高概率行为和尖锐常数两个理论挑战，给出了一个成功率为 1-δ 的算法，其样本数量为 1/Cτ,ε * (lg n + O (log^(2/3) n * log^(1/3) * 1/δ + log * 1/δ))，其中 Cτ,ε 是可达到的最优常数。对于 δ > n^{-o (1)}，该算法接近最优，对于 δ<<1，它是首个在常数因子内接近最优的界限。
noisy binary search modelprobabilitiescoinsfixed-noise modelalgorithm
发现论文，激发创造
  • 图中的确定性和概率二分搜索

    本文研究在带权无向图中的二分查找问题，并给出了一个在查询顶点时几乎达到信息熵下界的算法，同时也探讨了该问题在不同情况下的复杂性。

    Mar, 2015

  • 通过多臂老虎机实现带噪声查询的最优聚类

    本文研究了带有错误预言机的聚类问题，利用多臂赌博机算法解决该问题的上下界。

    Jul, 2022

  • 关于含噪计算的最优界限

    本研究重新审视了来自 Feige 等人的 1994 年的噪声信息计算问题，改进其上下界以更好地描述查询复杂性，并考虑了自适应采样和非自适应采样这两种情况。

    Jun, 2023

  • 无需重新采样的嘈杂排序

    研究了反馈弧集问题的算法，使用 n 个元素上的顺序形成的锦标赛作为输入，并考虑到噪声干扰，以最大似然的方式找到排名。

    Jul, 2007

  • 充分利用样本

    研究在不知道估值分布的情况下为潜在买家设定价格的问题，并证明不同分布类型所需的样本数量及最优价格策略，为拍卖领域提供参考。

    Jul, 2014

  • 无限臂老虎机渐进最优纯探索

    本文研究了纯探索问题中具有无限多臂的赌博机问题，针对固定置信和固定预算两种情形，提出了两种算法，分别以最小的期望和固定样本复杂度为目标，最终准确选择一个高质量臂，使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$，并给出了理论证明。

    Jun, 2023

  • 稳定性和偏差优化风险界的收敛速度为 $O (1/n)$

    研究证明，通过满足所谓的 Bernstein 条件，可以避免高概率广义化界限中的采样误差项，从而实现高概率过量风险边界，我们进而讨论了一些强凸和 Lipschitz 损失的方法。我们展示了任何经验风险最小化方法的 $O (log n/n)$ 高概率过量风险边界，从而解决了 Shalev-Shwartz，Shamir，Srebro 和 Sridharan（2009）的问题。

    Mar, 2021

  • 嘈杂比较下的最大选择和排名

    在满足强随机可转性和随机三角不等式的概率模型中，本研究考虑了 $(\epsilon,\delta)$-PAC 最大选择和排名问题。提出了一种基于淘汰赛的选择算法和一般框架来改进排名算法，结合归并排序和二分查找，得到了一个优化性能的排名算法。

    May, 2017

  • 使用不均等大小的样本进行接近度测试

    考虑从一个未知分布 $p$ 取 $m_1$ 个样本，从另一个未知分布 $q$ 取 $m_2$ 个样本的情形，介绍了一种测试是否有 $p=q$ 的快速算法，并分析了测试的样本复杂度，同时提出了估计马尔科夫链混合时间的算法及其初始样本个数的选择方法。测试算法主要依靠一种表现较为优异的统计量。

    Apr, 2015

  • 计算 “或” 和 “最大值” 函数的噪声方法

    使用有噪声的查询计算具有错误概率的函数问题，给出了计算 OR 函数和 MAX 函数所需的期望查询次数，并在两个函数的上下界中对错误概率进行了更紧密的依赖。

    Sep, 2023