论文标题
有效的尺寸自适应草图方法，用于更快的正则最小二乘优化速度
Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
论文作者
论文摘要
我们提出了一种新的随机算法，用于基于草图解决L2规范化的最小二乘问题。我们考虑了两个最流行的随机嵌入，即高斯嵌入和亚采样随机hadamard变换（SRHT）。尽管最小二乘优化的当前随机求解器规定了至少大于数据维度的嵌入尺寸，但我们表明，嵌入尺寸可以缩小为优化问题的有效维度，并且仍然可以保留高概率的收敛保证。在这方面，我们在高斯和SRHT嵌入的椭圆形上得出了急剧的基质偏差不平等。具体而言，我们改善了经典高斯浓度结合的常数，而对于SRHT嵌入，我们的偏差不平等涉及一种新型的技术方法。利用这些界限，我们能够设计一种实用和自适应算法，该算法不需要事先知道有效的维度。我们的方法从等于1的初始嵌入尺寸开始，然后在迭代中，将嵌入尺寸提高到有效的尺寸。因此，我们的算法改善了解决正规化最小二乘问题的最新计算复杂性。此外，我们从数值上表明，在几个标准的机器学习数据集上，它的表现优于标准迭代求解器，例如共轭梯度方法及其预先调节版本。
We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT). While current randomized solvers for least-squares optimization prescribe an embedding dimension at least greater than the data dimension, we show that the embedding dimension can be reduced to the effective dimension of the optimization problem, and still preserve high-probability convergence guarantees. In this regard, we derive sharp matrix deviation inequalities over ellipsoids for both Gaussian and SRHT embeddings. Specifically, we improve on the constant of a classical Gaussian concentration bound whereas, for SRHT embeddings, our deviation inequality involves a novel technical approach. Leveraging these bounds, we are able to design a practical and adaptive algorithm which does not require to know the effective dimension beforehand. Our method starts with an initial embedding dimension equal to 1 and, over iterations, increases the embedding dimension up to the effective one at most. Hence, our algorithm improves the state-of-the-art computational complexity for solving regularized least-squares problems. Further, we show numerically that it outperforms standard iterative solvers such as the conjugate gradient method and its pre-conditioned version on several standard machine learning datasets.
