Sketching, a dimensionality reduction technique, has received much attention
in the statistics community. In this paper, we study sketching in the context
of Newton's method for solving finite-sum optimization problems in which the
number of variables and data points are both large. We study two forms of
sketching that perform dimensionality reduction in data space: Hessian
subsampling and randomized Hadamard transformations. Each has its own
advantages, and their relative tradeoffs have not been investigated in the
optimization literature. Our study focuses on practical versions of the two
methods in which the resulting linear systems of equations are solved
approximately, at every iteration, using an iterative solver. The advantages of
using the conjugate gradient method vs. a stochastic gradient iteration are
revealed through a set of numerical experiments, and a complexity analysis of
the Hessian subsampling method is presented.

本文研究了在解决变量数量和数据点数量都很大的有限和最优化问题的 Newton 法的背景下，两种数据空间维数缩减方法：Hessian 子采样和随机 Hadamard 变换。通过一系列数字实验和 Hessian 子采样方法的复杂性分析，揭示了使用共轭梯度方法相对于随机梯度迭代方法的优势。