论文标题
有效的凸优化需要超线性内存
Efficient Convex Optimization Requires Superlinear Memory
论文作者
论文摘要
我们表明，任何可将$ d $二维的一阶算法限制，$ 1 $ -Lipschitz凸出的单位球的功能至$ 1/\ mathrm {poly}（d poly}（d）$精确度，最多使用$ d^{1.25-δ} $ abion 3/d^$ $ d^$ $ \ tildexe（d^）一阶查询（对于[0，1/4] $中的任何常数$δ\）。因此，这种内存约束算法的性能是比最佳$ \ tilde {o}（d）$查询通过使用$ \ tilde {o}（o}（d^2）$内存获得的平面方法获得的此问题的多项式因素。这解决了Colt 2019 Woodworth和Srebro的开放问题。
We show that any memory-constrained, first-order algorithm which minimizes $d$-dimensional, $1$-Lipschitz convex functions over the unit ball to $1/\mathrm{poly}(d)$ accuracy using at most $d^{1.25 - δ}$ bits of memory must make at least $\tildeΩ(d^{1 + (4/3)δ})$ first-order queries (for any constant $δ\in [0, 1/4]$). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal $\tilde{O}(d)$ query bound for this problem obtained by cutting plane methods that use $\tilde{O}(d^2)$ memory. This resolves a COLT 2019 open problem of Woodworth and Srebro.
