In this paper we provide oracle complexity lower bounds for finding a point
in a given set using a memory-constrained algorithm that has access to a
separation oracle. We assume that the set is contained within the unit
$d$-dimensional ball and contains a ball of known radius $\epsilon>0$. This
setup is commonly referred to as the feasibility problem. We show that to solve
feasibility problems with accuracy $\epsilon \geq e^{-d^{o(1)}}$, any
deterministic algorithm either uses $d^{1+\delta}$ bits of memory or must make
at least $1/(d^{0.01\delta }\epsilon^{2\frac{1-\delta}{1+1.01 \delta}-o(1)})$
oracle queries, for any $\delta\in[0,1]$. Additionally, we show that randomized
algorithms either use $d^{1+\delta}$ memory or make at least $1/(d^{2\delta}
\epsilon^{2(1-4\delta)-o(1)})$ queries for any $\delta\in[0,\frac{1}{4}]$.
Because gradient descent only uses linear memory $\mathcal O(d\ln 1/\epsilon)$
but makes $\Omega(1/\epsilon^2)$ queries, our results imply that it is
Pareto-optimal in the oracle complexity/memory tradeoff. Further, our results
show that the oracle complexity for deterministic algorithms is always
polynomial in $1/\epsilon$ if the algorithm has less than quadratic memory in
$d$. This reveals a sharp phase transition since with quadratic $\mathcal O(d^2
\ln1/\epsilon)$ memory, cutting plane methods only require $\mathcal O(d\ln
1/\epsilon)$ queries.

在这篇文章中，我们使用具有访问分离预言机的内存受限算法提供了解决给定集合中的点的 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/ε)) 的查询次数。