标题： 自适应迭代Hessian抽样通过A最优子抽样 显示英文标题

标题： Adaptive Iterative Hessian Sketch via A-Optimal Subsampling

摘要： 迭代Hessian草图（IHS）是一种用于建模大规模数据的有效草图方法。它最初由Pilanci和Wainwright（2016；JMLR）基于随机草图矩阵提出。然而，由于迭代草图过程，它计算量较大。在本文中，我们在无约束最小二乘问题设置下分析了IHS算法，然后通过A最优抽样提出了改进IHS的确定性方法。我们的贡献有三个方面：（1）建议了一个基于A最优设计的良好初始估计器；（2）为重复草图开发了一种新颖的正则化预条件器；（3）提出了一种精确线搜索方法以自适应地确定最优步长。大量的实验结果表明，我们提出的A最优IHS算法优于现有的加速IHS方法。 显示英文摘要

摘要： Iterative Hessian sketch (IHS) is an effective sketching method for modeling large-scale data. It was originally proposed by Pilanci and Wainwright (2016; JMLR) based on randomized sketching matrices. However, it is computationally intensive due to the iterative sketch process. In this paper, we analyze the IHS algorithm under the unconstrained least squares problem setting, then propose a deterministic approach for improving IHS via A-optimal subsampling. Our contributions are three-fold: (1) a good initial estimator based on the A-optimal design is suggested; (2) a novel ridged preconditioner is developed for repeated sketching; and (3) an exact line search method is proposed for determining the optimal step length adaptively. Extensive experimental results demonstrate that our proposed A-optimal IHS algorithm outperforms the existing accelerated IHS methods.