A globally convergent incremental Newton method

Abstract

Motivated by machine learning problems over large data sets and distributed optimization over networks, we develop and analyze a new method called incremental Newton method for minimizing the sum of a large number of strongly convex functions. We show that our method is globally convergent for a variable stepsize rule. We further show that under a gradient growth condition, convergence rate is linear for both variable and constant stepsize rules. By means of an example, we show that without the gradient growth condition, incremental Newton method cannot achieve linear convergence. Our analysis can be extended to study other incremental methods: in particular, we obtain a linear convergence rate result for the incremental Gauss-Newton algorithm under a variable stepsize rule.

References in corpus (2)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Cited by in corpus (13)

• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• Convergence Rate of Incremental Gradient and Newton Methods
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Variational Adaptive-Newton Method for Explorative Learning
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy
• HAMSI: A Parallel Incremental Optimization Algorithm Using Quadratic Approximations for Solving Partially Separable Problems
• Distributed Newton Optimization with Maximized Convergence Rate
• Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method