大规模优化问题的近似牛顿方法：理论与实现

Many machine learning models are reformulated as optimization problems. Thus, it is important to solve a large-scale optimization problem in big data applications. Recently, subsampled Newton and sketch Newton methods have emerged to attract much attention for optimization due to their efficiency at each iteration, rectified a weakness in the ordinary Newton method of suffering a high cost at each iteration while commanding a high convergence rate. However, the convergence properties of these methods are still not well understood. There are several important gaps between current convergence theory and performance in real application. In this proposal, we aim to fill these gaps and propose a unifying algorithmic framework that called approximate Newton methods. Accordingly, we analyze local convergence properties of second order methods. Based on this framework, we would make our theoretical analysis match the performance in real application very well.

许多机器学习模型可以被定义为优化问题。因此，在大数据时代求解大规模优化问题是非常重要的。由于其计算有效性，子抽样和概略牛顿方法最近吸引了广泛关注。该类方法能客服传统牛顿方法高计算代价问题，但同时保持高收敛率。然而，这些方法的收敛性能还没有完全被理解，特别是，我们发现已有理论结果与实际使用之间存在一些缺口。比如，理论分析通常要求目标函数的Hessian满足Lipschitz连续性, 但是实际应用发现这个条件不是必要的; 已有理论分析需要假设抽样样本数依赖于问题的条件数等。该项目试图去弥补这些缺口。因此，我们提出一类近似牛顿方法的算法框架，由此，我们建立我们的理论结果，并给出一些新的有效非精确牛顿方法。

在大数据时代求解大规模优化问题是非常重要的课题。由于其计算有效性，子抽样和概略牛顿方法最近吸引了广泛关注。该类方法能客服传统牛顿方法高计算代价问题，但同时保持高收敛率。然而，这些方法的收敛性能还没有完全被理解，特别是，我们发现已有理论结果与实际使用之间存在一些缺口。比如，理论分析通常要求目标函数的Hessian满足Lipschitz连续性, 但是实际应用发现这个条件不是必要的; 已有理论分析需要假设抽样样本数依赖于问题的条件数等。该项目试图去弥补这些缺口。我们提出了一类近似牛顿方法的算法框架，由此，我们建立了我们的理论结果，并给出一些新的有效非精确牛顿方法。此外，我们引入了Nesterov加速技术来提高非精确二阶方法(近似牛顿)的收敛速度，并提出了加速的正则化子采样牛顿法。