High-Dimensional Optimization in Adaptive Random Subspaces
High-Dimensional Optimization in Adaptive Random Subspaces
复制标题
DOI：
--
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Jonathan Lacotte;Mert Pilanci;M. Pavone
中科院分区：
文献类型：
--
作者：
Jonathan Lacotte;Mert Pilanci;M. Pavone
我们提出了一种新的高维问题的随机化优化方法，它可以看作是坐标下降到随机子空间的推广。我们表明，随机子空间的自适应采样策略的性能显著优于最近文献中常见的不经意采样方法。自适应子空间可以由相关的随机矩阵集成有效地产生，该随机矩阵集成的统计模拟输入数据。我们证明了解的相对误差的改善可以紧密地用数据矩阵的谱来刻画，并给出了概率上界。然后，我们用不同谱衰减的数据矩阵来说明我们的理论的结果。大量实验结果表明，该方法在Logistic回归、具有随机卷积层的核分类和具有校正的线性单元的浅层神经网络等机器学习问题上具有显著的加速作用。我们的分析基于凸分析和芬切尔对偶，并建立了与草绘和随机矩阵分解的联系。
We propose a new randomized optimization method for high-dimensional problems which can be seen as a generalization of coordinate descent to random subspaces. We show that an adaptive sampling strategy for the random subspace significantly outperforms the oblivious sampling method, which is the common choice in the recent literature. The adaptive subspace can be efficiently generated by a correlated random matrix ensemble whose statistics mimic the input data. We prove that the improvement in the relative error of the solution can be tightly characterized in terms of the spectrum of the data matrix, and provide probabilistic upper-bounds. We then illustrate the consequences of our theory with data matrices of different spectral decay. Extensive experimental results show that the proposed approach offers significant speed ups in machine learning problems including logistic regression, kernel classification with random convolution layers and shallow neural networks with rectified linear units. Our analysis is based on convex analysis and Fenchel duality, and establishes connections to sketching and randomized matrix decomposition.