BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory
BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Amirali Aghazadeh;Vipul Gupta;Alex DeWeese;O. O. Koyluoglu-O.;K. Ramchandran
中科院分区：
文献类型：
--
作者：
Amirali Aghazadeh;Vipul Gupta;Alex DeWeese;O. O. Koyluoglu-O.;K. Ramchandran
我们考虑在机器学习中的应用中的特征选择，其中数据的维度如此之大，以至于超过(本地)计算机器的工作内存。遗憾的是，当前的大规模草图绘制算法由于草图区域中随机梯度噪声的不可逆碰撞和累积而表现出较差的记忆精度折衷。在这里，我们开发了一种二阶超高维特征选择算法Bear，它通过将著名的Broyden-Fletcher-Goldfarb-Shannon(BFGS)算法中的二阶梯度存储在Count Sketch中来避免额外的碰撞，Count Sketch是一种来自流文献的次线性记忆数据结构。在真实数据集上的实验表明，与一阶草图算法相比，Bear算法需要的存储空间最多减少三个数量级，才能达到相同的分类精度。理论分析证明了该算法在t次迭代中收敛速度为O(1/t)。我们的算法揭示了二阶优化在超高维数据集上训练的模型的内存受限草图绘制方面的未知优势。
We consider feature selection for applications in machine learning where the dimensionality of the data is so large that it exceeds the working memory of the (local) computing machine. Unfortunately, current large-scale sketching algorithms show poor memory-accuracy trade-off due to the irreversible collision and accumulation of the stochastic gradient noise in the sketched domain. Here, we develop a second-order ultra-high dimensional feature selection algorithm, called BEAR, which avoids the extra collisions by storing the second-order gradients in the celebrated Broyden-Fletcher-Goldfarb-Shannon (BFGS) algorithm in Count Sketch, a sublinear memory data structure from the streaming literature. Experiments on real-world data sets demonstrate that BEAR requires up to three orders of magnitude less memory space to achieve the same classification accuracy compared to the first-order sketching algorithms. Theoretical analysis proves convergence of BEAR with rate O(1/t) in t iterations of the sketched algorithm. Our algorithm reveals an unexplored advantage of second-order optimization for memory-constrained sketching of models trained on ultra-high dimensional data sets.