DynaNewton - Accelerating Newton's Method for Machine Learning

Understand

Newton's method is a fundamental technique in optimization with quadratic convergence within a neighborhood around the optimum.

• However reaching this neighborhood is often slow and dominates the computational costs.
• We exploit two properties specific to empirical risk minimization problems to accelerate Newton's method, namely, subsampling training data and increasing strong convexity through regularization.
• We propose a novel continuation method, where we define a family of objectives over increasing sample sizes and with decreasing regularization strength.