Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation

• URL: http://arxiv.org/abs/2205.11033v1
• Date: Mon, 23 May 2022 04:34:10 GMT
• Title: Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation
• Authors: Md Sarowar Morshed
• Abstract summary: We propose two variants of Newton method for solving unconstrained problem. We generate novel variants of the Newton method namely the Penalty Newton method and the Augmented Newton method.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We propose two variants of Newton method for solving unconstrained minimization problem. Our method leverages optimization techniques such as penalty and augmented Lagrangian method to generate novel variants of the Newton method namely the Penalty Newton method and the Augmented Newton method. In doing so, we recover several well-known existing Newton method variants such as Damped Newton, Levenberg, and Levenberg-Marquardt methods as special cases. Moreover, the proposed Augmented Newton method can be interpreted as Newton method with adaptive heavy ball momentum. We provide global convergence results for the proposed methods under mild assumptions that hold for a wide variety of problems. The proposed methods can be sought as the penalty and augmented extensions of the results obtained by Karimireddy et. al [24].

Related papers

• Symplectic Stiefel manifold: tractable metrics, second-order geometry and Newton's methods [1.190653833745802]
  We develop explicit second-order geometry and Newton's methods on the symplectic Stiefel manifold. We then solve the resulting Newton equation, as the central step of Newton's methods. Various numerical experiments are presented to validate the proposed methods.
  arXiv  Detail & Related papers  (2024-06-20T13:26:06Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework.
  arXiv  Detail & Related papers  (2024-02-04T05:54:51Z)
• Backtracking New Q-Newton's method, Newton's flow, Voronoi's diagram and Stochastic root finding [0.0]
  A new variant of Newton's method - named Backtracking New Q-Newton's method (BNQN) - has strong theoretical guarantee, is easy to implement, and has good experimental performance.
  arXiv  Detail & Related papers  (2024-01-02T15:37:47Z)
• Newton-CG methods for nonconvex unconstrained optimization with H\"older continuous Hessian [5.161026048499362]
  We consider a nonconstrained unconstrained optimization problem minimizing a twice differentiable objective function with H"older Hessian. We develop a parameter-free NewtonCG method without requiring any prior knowledge of these parameters. We present preliminary numerical results to demonstrate the superior practical performance over a well-known regularized Newton method.
  arXiv  Detail & Related papers  (2023-11-22T01:50:43Z)
• FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning [75.46959684676371]
  We introduce a novel framework called FedNew in which there is no need to transmit Hessian information from clients to PS. FedNew hides the gradient information and results in a privacy-preserving approach compared to the existing state-of-the-art.
  arXiv  Detail & Related papers  (2022-06-17T15:21:39Z)
• Automated differential equation solver based on the parametric approximation optimization [77.34726150561087]
  The article presents a method that uses an optimization algorithm to obtain a solution using the parameterized approximation. It allows solving the wide class of equations in an automated manner without the algorithm's parameters change.
  arXiv  Detail & Related papers  (2022-05-11T10:06:47Z)
• Inertial Newton Algorithms Avoiding Strict Saddle Points [0.7614628596146602]
  We study the behavior of second-order algorithms mixing Newton's method and inertial gradient descent. We show that, Newtonian behavior of these methods, they almost always escape strict points.
  arXiv  Detail & Related papers  (2021-11-08T16:02:45Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
  We introduce variational which allow us to derive different methods for optimization. We derive two families of optimization methods in one-to-one correspondence. The preservation of symplecticity of autonomous systems occurs here solely on the fibers.
  arXiv  Detail & Related papers  (2021-06-04T20:21:53Z)
• Disentangling the Gauss-Newton Method and Approximate Inference for Neural Networks [96.87076679064499]
  We disentangle the generalized Gauss-Newton and approximate inference for Bayesian deep learning. We find that the Gauss-Newton method simplifies the underlying probabilistic model significantly. The connection to Gaussian processes enables new function-space inference algorithms.
  arXiv  Detail & Related papers  (2020-07-21T17:42:58Z)
• Information Newton's flow: second-order optimization method in probability space [10.340665633567083]
  We introduce a framework for Newton's flows in probability space with information metrics, named information Newton's flows. A known fact is that overdamped Langevin dynamics correspond to Wasserstein gradient flows of Kullback-Leibler divergence. We provide examples of Newton's Langevin dynamics in both one-dimensional space and Gaussian families.
  arXiv  Detail & Related papers  (2020-01-13T15:33:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.