BriefGPT - AI 论文速递
·
梯度下降在可行性问题的 Oracle 复杂度和内存权衡中是帕累托最优的
内容提要
本文介绍了一种使用具有访问分离预言机的内存受限算法来解决给定集合中的点的 Oracle 复杂性下界的方法。作者证明了对于准确度 ε≥e^(-d^(o (1))) 的可行性问题，确定性算法要么使用 d^(1+δ) bits 的内存，要么至少需要进行 1/(d^(0.01δ)ε^(2 ((1-δ)/(1+1.01δ))-o (1))) 次预言机查询，随机算法要么使用 d^(1+δ) 的内存，要么至少需要进行 1/(d^(2δ)ε^(2 (1-4δ)-o (1))) 次查询。结果表明梯度下降算法在 Oracle 复杂性 / 内存权衡中是帕累托最优的，并且如果算法在 d 维中具有小于二次的内存，则确定性算法的 Oracle 复杂性总是多项式级别的 1/ε。
关键要点
-
本文介绍了一种使用具有访问分离预言机的内存受限算法来解决给定集合中的点的 Oracle 复杂性下界。
-
集合包含单位 d 维球体和已知半径 ε 的球体。
-
对于准确度 ε≥e^(-d^(o (1))) 的可行性问题，确定性算法要么使用 d^(1+δ) bits 的内存，要么至少需要进行 1/(d^(0.01δ)ε^(2 ((1-δ)/(1+1.01δ))-o (1))) 次预言机查询。
-
随机算法要么使用 d^(1+δ) 的内存，要么至少需要进行 1/(d^(2δ)ε^(2 (1-4δ)-o (1))) 次查询。
-
梯度下降算法使用线性内存 O (dln (1/ε))，但进行 Ω(1/ε^2) 次查询，表明其在 Oracle 复杂性 / 内存权衡中是帕累托最优的。
-
如果算法在 d 维中具有小于二次的内存，则确定性算法的 Oracle 复杂性总是多项式级别的 1/ε。
-
对于二次的 O (d^2ln (1/ε)) 内存，割平面方法仅需要 O (dln (1/ε)) 的查询次数，揭示了一个明显的相变。
