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

May, 2017

我们重新审视了 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

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

Jun, 2023

本研究旨在通过自适应挑选子集并收集偏好反馈，在 Plackett-Luce 模型下解决 PAC 排名问题，提出了新的 pivot trick 技巧，从而实现了在一定概率下识别 n 个项目的 ε- 最优排名，（m-1）/m 降低的样本复杂度和对称排名算法的阶无法提高的。

Oct, 2018

本文提出了 NeuralSort 算法，将排序操作的输出从置换矩阵松弛到单峰行随机矩阵的集合，使得任意计算图都可以进行端到端梯度优化；并且使用这种松弛方式，针对全排列空间提出了重参数化梯度估算器，展示了该框架在高维对象学习语义排序方面的实用性。

Mar, 2019

通过学习增强算法的角度探索排序问题，其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境：在第一种情境中，为每个项目提供了其在已排序列表中的位置预测；在第二种情境中，我们假设存在一种 “快速但不精确” 的方法来比较项目，除此之外还有慢而准确的比较。对于这两种情境，我们设计了新的简单算法，仅使用 O (Σi log ηi) 个精确比较，其中 ηi 是第 i 个元素的适当定义的预测误差。特别是，随着预测质量的下降，比较次数从 O (n) 平滑地降低到 O (nlogn)。我们证明在所考虑的误差度量方面，比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。

Nov, 2023

该论文研究了在不确定性条件下，利用学习增强算法处理排序和超图方向问题，并提出了针对准确和错误预测的性能保证算法，可以通过查询提高不确定性元素的精确度，从而最小化问题求解所需的查询数量。

May, 2023

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

Jul, 2022

本文研究了一个分类问题，其中样本标签被随机损坏。我们解决了如何在有标签噪声的情况下最好地利用传统分类问题的丰富代理损失函数，通过重要性重新加权来使用任何代理损失函数进行带有噪声标签的分类，以及如何获得噪声率的问题。

Nov, 2014

该论文考虑了具有洗牌标签的线性回归任务，提出了一种一步估计器来重构（Π，B），并给出了在不同情境下正确排列恢复的充分条件，最后通过数值实验验证了上述结论。

Oct, 2023