Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization

本文研究了在高维空间$\mathbb R^d$中，具有近似$s$-稀疏梯度的函数的非凸零阶优化（ZOO）问题。为了减少查询复杂度对维度$d$的依赖性，高维ZOO方法试图利用梯度稀疏性设计梯度估计器。先前最好的方法需要$O\big(s\log\frac ds\big)$个查询才能实现$O\big(\frac1T\big)$的收敛速率，其中$T$是步数。本文提出了一种名为“梯度压缩感知”（GraCe）的查询高效和准确的稀疏梯度估计器，每步只需$O\big(s\log\log\frac ds\big)$个查询，仍然可以实现$O\big(\frac1T\big)$的收敛速率。据我们所知，我们是第一个在较弱的假设下实现了对$d$的查询复杂度的“双对数”依赖性的人。我们提出的GraCe将压缩感知中的Indyk-Price-Woodruff（IPW）算法从线性测量推广到非线性函数。此外，由于IPW算法的常数过大而纯理论性，我们通过我们的“依赖随机分区”技术以及相应的新颖分析改进了IPW算法，并成功将常数减小了近4300倍。我们的GraCe不仅在理论上查询高效，而且在实践中表现出色。我们在10000维函数上对比了12种现有的ZOO方法，并证明GraCe明显优于现有方法。

本论文旨在解决高维空间中具有近似s稀疏梯度的非凸零阶优化（ZOO）问题中查询复杂度依赖于维度d的问题，通过利用梯度稀疏性设计梯度估计器来降低查询复杂度。同时，还试图将压缩感知中的Indyk-Price-Woodruff（IPW）算法从线性测量推广到非线性函数。这是否是一个新问题？

本文提出了一种名为GraCe的梯度压缩感知算法，利用仅需要O(sloglog(d/s))的查询次数来实现O(1/T)的收敛速率，并且在较弱的假设下实现了对于维度d的双对数依赖查询复杂度。此外，通过依赖随机分区技术以及相应的新型分析，成功地将IPW算法的常数因子降低了近4300倍。

本文的亮点在于：提出了一种新的梯度压缩感知算法GraCe，实现了对于维度d的双对数依赖查询复杂度；通过依赖随机分区技术以及相应的新型分析，成功地将IPW算法的常数因子降低了近4300倍；实验结果表明GraCe在10000维函数上优于12种现有的ZOO方法。

最近的相关研究包括：基于梯度稀疏性的高维ZOO问题的研究，以及压缩感知中的IPW算法的研究。其中，IPW算法是在压缩感知中的一种理论算法，而本文则将其推广到了非线性函数中。