Apple Machine Learning Research ·

函数的位置信息不变性属性与分布属性的比较：在测试中统一但在验证中分离

💡 原文英文，约600词，阅读约需2分钟。

📝

内容提要

本文探讨了函数的位置信息不变性属性与分布属性之间的关系，指出在验证过程中这种关系不再成立。研究提出了适用于多种位置信息不变性属性的双次亚线性交互证明（IPP）方法，并展示了验证者和诚实证明者的查询复杂度。与分布属性相比，后者没有双次高效的IPP。

🎯

函数的位置信息不变性属性是指可以通过每个值出现的频率来表征，而不考虑每个值出现的位置。
在验证过程中，位置信息不变性属性与分布属性之间的密切关系不再成立。
研究提出了适用于多种位置信息不变性属性的双次亚线性交互证明（IPP）方法。
对于每个值出现 m/n 次的函数集合，验证者的查询复杂度为 O(n^{0.5−α})，诚实证明者的查询复杂度为 e^{O(n^{0.5+α}/ε^2)}。
对于每个值出现 m/k 次或根本不出现的函数集合，验证者的查询复杂度为 poly(1/ε) · k^{(2/3)−2α}，而证明者的查询复杂度为 poly(1/ε) · e^{O(k^{(2/3)+α})}。
与之相比，分布属性没有双次高效的IPP，特别是均匀性属性在验证时需要的样本数无法低于 o(n^{1/2})。

🔎

位置信息不变性属性与分布属性在测试阶段表现出密切关系，但在验证过程中却分离。这意味着在实际应用中，验证这些属性时需要特别注意其复杂性差异，尤其是在处理大规模数据时。

研究提出的双次亚线性交互证明（IPP）方法在验证位置信息不变性属性时展现出较低的查询复杂度。这为需要高效验证的应用场景提供了新的思路，尤其是在数据量庞大的情况下，能够显著降低资源消耗。

与位置信息不变性属性相比，分布属性在验证时面临更高的复杂性，尤其是均匀性属性的验证需要较多样本。这提示研究者和实践者在选择验证方法时需谨慎，避免低效的验证策略。

❓

函数的位置信息不变性属性是指可以通过每个值出现的频率来表征，而不考虑每个值出现的位置。

在验证过程中，位置信息不变性属性与分布属性之间的密切关系不再成立。

双次亚线性交互证明（IPP）方法适用于多种位置信息不变性属性，且验证者和诚实证明者的查询复杂度均为亚线性。

对于每个值出现 m/n 次的函数集合，验证者的查询复杂度为 O(n^{0.5−α})。

分布属性在验证时，均匀性属性所需的样本数无法低于 o(n^{1/2})。

对于每个值出现 m/k 次或根本不出现的函数集合，验证者的查询复杂度为 poly(1/ε) · k^{(2/3)−2α}。

🏷️