技术摘要：从反例中进行排序

问题定义

本文研究了通过交互式查询过程学习 $n$ 个项目未知线性序（排名）$\pi^*$ 的问题。在每一轮中，学习者提出一个完整的线性序 $\pi$。预言机（Oracle）以两种方式之一做出响应：

1. 确认： 宣布 $\pi = \pi^*$，从而终止交互。
2. 反例： 返回一对项目 $\{i, j\}$，表明它们在 $\pi$ 中的相对顺序是错误的。

该问题的核心挑战在于存在不诚实的反例。返回的对 $\{i, j\}$ 被定义为诚实的，如果所提议的顺序 $\pi$ 与目标顺序 $\pi^*$ 在 $i$ 和 $j$ 的相对顺序上不一致。相反，如果 $\pi$ 与 $\pi^*$ 在 $i$ 和 $j$ 的相对顺序上实际上是一致的，则该反例是不诚实的。模型假设最多有 $k$ 个返回的反例是不诚实的（谎言），但学习者事先并不知道 $k$ 的值。目标是使用最少的查询次数（轮数）来识别目标排名 $\pi^*$。

该模型的一个关键约束是适当性（Properness）：学习者在每一轮中必须输出一个有效的线性序。这使该问题区别于标准的加权多数学习（Weighted-Majority Learning），在后者中，成对的预测可能会形成循环（孔多塞循环，Condorcet cycles）而无法扩展为单一的排名。

方法论

作者结合了排列的几何表示、凸几何以及组合下界构造。

1. 几何表示与 Grünbaum 定理（无限制排名）

对于目标可以是任意 $n!$ 个排名的通用情况，作者利用了一种几何表示，其中每个排名对应于超立方体 $[0, 1]^n$ 中的一个单元格。点 $x \in [0, 1]^n$ 通过其坐标的排序诱导出一个排名。

• 诚实情况： 当所有反例都是诚实时，一致的点集构成一个凸体。学习者查询由该凸体的**质心（Centroid）**诱导的排名。Grünbaum 定理保证了任何包含凸体质心的半空间都至少包含该凸体体积的 $1/e$ 部分。因此，一个错误的猜测会消除剩余体积的一个常数比例。这导致了 $O(n \log n)$ 的复杂度。
• 噪声情况： 为了处理不至于永久丢弃目标的非诚实反例，作者使用平滑加权更新取代了硬性消除。他们维护的是立方体上的一个对数凹密度（Log-concave density），而非离散权重。更新规则使用了一种旨在保持对数凹性的替代损失函数。这使得应用对数凹版本的 Grünbaum 定理成为可能。更新会对与反例不一致的排名进行惩罚，但确保靠近真实目标的权重下降缓慢（仅以与 $n$ 相关的因子下降），同时总质量在每一轮中下降一个常数因子。

2. 几何类别的强多数（Strong Majority）

对于具有低维几何结构的排名类别（其中项目为向量 $v_i \in \mathbb{R}^d$，排名由投影到方向 $w$ 诱导），作者改编了加权多数算法。

• 作者没有使用简单的成对多数（这可能会产生循环），而是定义了一个强多数关系：只有当当前权重支持该边的比例达到 $1 - O(1/d)$ 时，才存在边 $i \to j$。
• 利用 Carathéodory 定理，作者证明了在 $d$ 维几何类别中，这种强多数关系是无环的，并且可以扩展为一个有效的线性序。
• 这使得学习者可以查询一个有效的顺序，同时确保任何反例都能消除总权重的显著比例（$\Omega(1/d)$）。

3. 下界构造

下界由两种不同的对抗策略得出：

• 排序论证 ($\Omega(n \log n)$)： 改编自基于比较的排序（例如归并排序），对抗者迫使学习者遍历一个平衡比较树，即使在无噪声设置下也需要 $\Omega(n \log n)$ 次查询。
• 孔多塞循环 ($\Omega(nk)$)： 对抗者根据 $n$ 个项目的有向循环构造了一组候选排名。通过返回循环中的边作为反例，对抗者可以迫使学习者在 $n$ 个候选者之间进行区分，其中每个候选者直到其特定的“禁止”边被返回 $k+1$ 次后才会被排除。这产生了 $\Omega(nk)$ 的代价。
• 几何下界： 对于 $d$ 维类别，作者使用多项式排名（项目位于矩形曲线/moment curve 上）来表明识别转折点需要 $\Omega(d \log n)$ 次查询，并结合来自循环构造的 $\Omega(dk)$ 代价。

核心结果

1. 无限制排名

对于具有至多 $k$ 个不诚实反例的 $n$ 个项目的任意目标排名：

• 最优查询复杂度： $\Theta(n \log n + nk)$。
• 上界： 由一个不需要 $k$ 作为输入的确定性学习者实现。该算法使用对数凹密度更新并查询质心诱导的排名。
• 下界： 在常数因子范围内与上界匹配。$\Omega(n \log n)$ 项源于排序，$\Omega(nk)$ 项源于孔多塞循环构造。
• 含义： 虽然无噪声排序是 $O(n \log n)$，但每个不诚实的反例会产生额外的 $O(n)$ 代价，这与标准加权多数学习（其中谎言的代价为 $O(1)$）相比是一个显著的增加。

2. 几何排名类别

对于由 $\mathbb{R}^d$ 中的向量诱导的排名类别：

• 上界： $O(d^2 \log n + dk)$。
• 下界： $\Omega(d \log n + dk)$。
• 差距： 在无噪声项中存在一个 $d$ 倍的差距（$d^2 \log n$ 对比 $d \log n$）。上界是通过查询强多数图的线性扩张或通过中心点方法实现的。
• 适当性： 学习者可以被约束为输出本身也是几何可实现的（由 $\mathbb{R}^d$ 中的方向诱导）的排名。

意义与主张

本文声称提供了在有限噪声下从反例中学习排名的查询复杂度的紧确特征化，并强调了维持适当性（输出有效线性序）的特定成本。

• 适当性的代价： 作者强调，要求学习者输出线性序（而非任意成对预测）从根本上改变了存在噪声时的复杂度。在标准加权多数学习中，不诚实反馈的代价是 $O(1)$；而在这里，由于学习者必须解决潜在的循环（孔多塞现象）以生成有效顺序，其代价为 $O(n)$。
• 几何洞察： 该工作展示了如何利用凸几何（Grünbaum 定理）和对数凹测度来设计对噪声具有鲁棒性的适当学习算法，扩展了先前用于处理部分信息下排序的技术。
• 无参数学习： 提出的算法不需要知道谎言预算 $k$，这使得它们对变化的噪声水平具有鲁棒性。
• 开放问题： 作者指出，虽然对 $k$ 的依赖是紧确的，但 $d$ 在几何无噪声项中的依赖关系仍是一个开放问题（即 $O(d^2 \log n)$ 是否可以改进为 $O(d \log n)$）。他们也将开发高效的组合实现（避免通用采样）作为未来的研究方向。

论文总结道，即使在这样基础的受限不诚实反例设置下，线性序的结构性要求与噪声模型之间的相互作用也带来了非平凡的挑战，需要复杂的几何和组合工具来解决。