揭示凸优化中内存与查询次数的极限权衡，首次证明内存不足时需更多查询。
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
- 建立随机与确定性算法的新型下界，揭示内存受限时优化效率瓶颈。
- 当内存约 $d^2$ 时，查询次数从多项式降至对数级，出现显著相变。
- 适用于关注内存-计算权衡的优化算法研究者，尤其适合低内存场景设计。
我们证明了在单位球上最小化 $d$ 维 $1$-Lipschitz 凸函数时，使用 $m$ 位内存的第一阶黑箱查询复杂度的两个下界。对于任意（可能随机）算法，必须进行 $ ildeΩ( rac{d^2}{ ext{√}m})$ 次查询；对于确定性算法，所需查询次数为 $ ildeΩ( ext{min}ig\igackslash{d^{1.6}, rac{d^{8/3}}{m^{2/3}}}igig\}$。这些结果在所有相关内存范围内均优于此前最佳下界。值得注意的是，结合现有上界，该确定性下界首次表明，在 $m \approx d^2$ 处存在尖锐的查询复杂度相变：内存微小变化即引发查询量 $ ext{poly}(d)$ 级别改变。此外，当精度要求为 $d$ 的多项式级别时，我们的随机算法下界首次表明，欲接近无内存约束下的最优查询复杂度，必须具备 $ ildeΩ(d^2)$ 内存。此前此类结论仅知于精度为 $d$ 的拟多项式级别的情形。
原文摘要 · Abstract (English)
We prove two lower bounds for the first order oracle complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory. We first show that any such (possibly randomized) algorithm must make $\tildeΩ(\frac{d^2}{\sqrt{m}})$ oracle queries. For deterministic optimization algorithms, we show that $\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})$ queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of $\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})$ and $\tildeΩ(\frac{d^{5/3}}{m^{1/3}})$ for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around $m\approx d^2$, where a polylogarithmic change in memory leads to a $\mathsf{poly}(d)$ change in the number of required oracle calls. Further, when the suboptimality is polynomially small in $d$, our lower bound randomized algorithms is the first to show that $\tildeΩ(d^2)$ memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in $d$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。