Memory-Query Tradeoffs for Randomized Convex Optimization
Memory-Query Tradeoffs for Randomized Convex Optimization
复制标题
DOI：
10.1109/focs57990.2023.00086
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
X. Chen;Binghui Peng
中科院分区：
文献类型：
--
作者：
X. Chen;Binghui Peng
我们证明了，任何随机一阶算法，最小化一个d维，1-Lipschitz凸函数的单位球必须使用$\Omega\left（d^{2-\delta}\right）$位的内存或$\Omega\left（d^{1+\delta / 6-o（1）}\right）$查询，对于任何常数$\delta \in（0，1）$和精度$\delta $是准多项式小的d。我们的结果表明，切割平面方法，使用$\tilde{O}\left（d^{2}\right）$位的内存和$\tilde{O}（d）$查询，是帕累托最优的随机一阶算法，和二次内存需要达到最佳的查询复杂度凸优化。
We show that any randomized first-order algorithm which minimizes a d-dimensional, 1-Lipschitz convex function over the unit ball must either use $\Omega\left(d^{2-\delta}\right)$ bits of memory or make $\Omega\left(d^{1+\delta / 6-o(1)}\right)$ queries, for any constant $\delta \in(0,1)$ and when the precision $\epsilon$ is quasipolynomially small in d. Our result implies that cutting plane methods, which use $\tilde{O}\left(d^{2}\right)$ bits of memory and $\tilde{O}(d)$ queries, are Pareto-optimal among randomized first-order algorithms, and quadratic memory is required to achieve optimal query complexity for convex optimization.