本文研究了带有噪声查询的聚类问题，提供了信息理论下限以及与之匹配的新算法，并介绍了在众包、社交网络和随机块模型中应用的情况。

Jun, 2017

我们研究了一个通用的聚类环境，其中我们有 $n$ 个要聚类的元素，并且我们的目标是尽量少地通过一个返回两个元素之间相似度的有噪声样本的预言进行查询。我们提出了在组合多臂赌博机的纯探索范式中根源于在线学习问题的两种新颖公式：固定置信度和固定预算设置。对于这两种设置，我们设计了将采样策略与经典的相关聚类近似算法相结合的算法，并研究了它们的理论保证。我们的结果是第一个针对 NP 困难的离线优化问题情况下 PE-CMAB 的多项式时间算法的示例。

Feb, 2024

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

Jun, 2023

本研究提出了基于同类簇查询与有噪音答案的方法，解决了离群点存在情况下的近似 K-means 聚类优化问题，证明了在一定条件下可以以大概率获得最优潜在解的 (1+ε）近似解，并且比目前已知的方法减少了同类簇查询数量。这种方法也推广到了控制噪音、离群点的场景中，同时在人造数据集和真实数据集上进行了测试。

Jun, 2018

我们重新审视了 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，它是首个在常数因子内接近最优的界限。

Nov, 2023

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

Jun, 2023

研究交互聚类的查询复杂度和相似度矩阵的信息理论下界及上界，证明相似度矩阵可以显著降低查询复杂度，在不知道 $k,f_+ 和 f_-$ 的前提下，算法高效且参数免费，并揭示其与常见社区检测模型的关联。

Jun, 2017

我们对改进的多臂赌博机问题给出了近似最优的上下界。我们证明了对于任何随机在线算法，存在一个实例使其相对于最优收益至少有一个 Ω(√k) 的近似因子。然后，我们提供了一个随机在线算法，在事先告知最优臂可达到的最大收益的情况下，保证了一个 O (√k) 的近似因子。我们接下来展示了如何消除这一假设，以增加 O (log k) 的近似因子，从而实现了相对于最优的 O (√k log k) 的整体近似。

Apr, 2024

本文提出了一种半监督主动聚类框架 (SSAC)，通过进行少量的相同聚类查询，可以在多项式时间内解决 K-means 聚类问题，而且算法不需要边界假设。

Apr, 2017

提出多臂老虎机算法中两个问题：如何识别平均值与最大平均值相差小于给定阈值的武器和如何识别平均值大于给定阈值的 k 支武器。在此基础上，给出了形式化的定义，匹配了样本复杂度的下界，并提供了几乎匹配上界的具体实用算法。

Jun, 2019