Apr, 2024
梯度下降在可行性问题的 Oracle 复杂度和内存权衡中是帕累托最优的
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory
Tradeoff for Feasibility Problems
TL;DR在这篇文章中，我们使用具有访问分离预言机的内存受限算法提供了解决给定集合中的点的Oracle复杂性下界，其中集合包含单位d维球体并且含有已知半径ε的球体。我们证明了对于准确度ε≥e^(-d^(o(1)))的可行性问题，任何确定性算法要么使用d^(1+δ) bits的内存，要么至少需要进行1/(d^(0.01δ)ε^(2((1-δ)/(1+1.01δ))-o(1)))次预言机查询，其中δ∈[0,1]。此外，我们还证明了对于随机算法，要么使用d^(1+δ)的内存，要么至少需要进行1/(d^(2δ)ε^(2(1-4δ)-o(1)))次查询，其中δ∈[0,1/4]。由于梯度下降算法仅使用线性的内存O(dln(1/ε))，但进行Ω(1/ε^2)次查询，我们的结果表明它在Oracle复杂性/内存权衡中是帕累托最优的。此外，我们的结果表明，如果算法在d维中具有小于二次的内存，则确定性算法的Oracle复杂性总是多项式级别的1/ε。这揭示了一个明显的相变，因为对于二次的O(d^2ln(1/ε))内存，割平面方法仅需要O(dln(1/ε))的查询次数。