Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds
Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds
复制标题
DOI：
10.1109/tit.2022.3146206
复制
发表时间：
2020-12
影响因子：
2.5
通讯作者：
Jonathan Lacotte;Mert Pilanci
中科院分区：
文献类型：
--
作者：
Jonathan Lacotte;Mert Pilanci
基于变量对随机子空间的约束，提出了一种新的高维凸优化方法。我们考虑不经意和数据自适应子空间，并通过凸对偶和Fenchel共轭研究其逼近性质。一个合适的自适应子空间可以通过采样相关的随机矩阵，其二阶统计量反映输入数据来生成。我们说明，自适应策略可以显着优于标准的不经意采样方法，这是广泛使用的最近的文献。我们表明，随机近似的相对误差可以紧密地表征在最佳的数据矩阵和高斯宽度的对偶切锥的频谱。我们开发的下界优化和统计误差措施的基础上集中的措施和法诺不等式。然后，我们提出的后果，我们的理论与数据矩阵不同的光谱衰减曲线。实验结果表明，所提出的方法可以显着提高各种机器学习和优化问题的速度，包括逻辑回归，随机卷积层的核分类和具有整流线性单元的浅层神经网络。
We propose novel randomized optimization methods for high-dimensional convex problems based on restrictions of variables to random subspaces. We consider oblivious and data-adaptive subspaces and study their approximation properties via convex duality and Fenchel conjugates. A suitable adaptive subspace can be generated by sampling a correlated random matrix whose second order statistics mirror the input data. We illustrate that the adaptive strategy can significantly outperform the standard oblivious sampling method, which is widely used in the recent literature. We show that the relative error of the randomized approximations can be tightly characterized in terms of the spectrum of the data matrix and Gaussian width of the dual tangent cone at optimum. We develop lower bounds for both optimization and statistical error measures based on concentration of measure and Fano’s inequality. We then present the consequences of our theory with data matrices of varying spectral decay profiles. Experimental results show that the proposed approach enables significant speed ups in a wide variety of machine learning and optimization problems including logistic regression, kernel classification with random convolution layers and shallow neural networks with rectified linear units.