Backtracking New Q-Newton's method, Newton's flow, Voronoi's diagram and Stochastic root finding

• URL: http://arxiv.org/abs/2401.01393v2
• Date: Mon, 8 Jan 2024 08:15:41 GMT
• Title: Backtracking New Q-Newton's method, Newton's flow, Voronoi's diagram and Stochastic root finding
• Authors: John Erik Fornaess, Mi Hu, Tuyen Trung Truong, Takayuki Watanabe
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A new variant of Newton's method - named Backtracking New Q-Newton's method (BNQN) - which has strong theoretical guarantee, is easy to implement, and has good experimental performance, was recently introduced by the third author. Experiments performed previously showed some remarkable properties of the basins of attractions for finding roots of polynomials and meromorphic functions, with BNQN. In general, they look more smooth than that of Newton's method. In this paper, we continue to experimentally explore in depth this remarkable phenomenon, and connect BNQN to Newton's flow and Voronoi's diagram. This link poses a couple of challenging puzzles to be explained. Experiments also indicate that BNQN is more robust against random perturbations than Newton's method and Random Relaxed Newton's method.

Related papers

• Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation [0.0]
  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.
  arXiv  Detail & Related papers  (2022-05-23T04:34:10Z)
• Learning Neural Hamiltonian Dynamics: A Methodological Overview [109.40968389896639]
  Hamiltonian dynamics endows neural networks with accurate long-term prediction, interpretability, and data-efficient learning. We systematically survey recently proposed Hamiltonian neural network models, with a special emphasis on methodologies.
  arXiv  Detail & Related papers  (2022-02-28T22:54:39Z)
• 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)
• Free Probability, Newton lilypads and Jacobians of neural networks [0.0]
  We present a reliable and very fast method for computing the associated spectral densities. Our technique is based on an adaptative Newton-Raphson scheme, by finding and chaining basins of attraction.
  arXiv  Detail & Related papers  (2021-11-01T11:22:42Z)
• New Q-Newton's method meets Backtracking line search: good convergence guarantee, saddle points avoidance, quadratic rate of convergence, and easy implementation [0.0]
  modification of Newton's method, named New Q-Newton's method, which can avoid saddle points and has quadratic rate of convergence. Experiments on small scale show that the method works very competitively against other well known modifications of Newton's method.
  arXiv  Detail & Related papers  (2021-08-23T15:39:00Z)
• 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)
• Learning a Single Neuron with Bias Using Gradient Descent [53.15475693468925]
  We study the fundamental problem of learning a single neuron with a bias term. We show that this is a significantly different and more challenging problem than the bias-less case.
  arXiv  Detail & Related papers  (2021-06-02T12:09:55Z)
• Machine-Learning Non-Conservative Dynamics for New-Physics Detection [69.45430691069974]
  Given a trajectory governed by unknown forces, our Neural New-Physics Detector (NNPhD) aims to detect new physics. We demonstrate that NNPhD successfully discovers new physics by decomposing the force field into conservative and non-conservative components. We also show how NNPhD coupled with an integrator outperforms previous methods for predicting the future of a damped double pendulum.
  arXiv  Detail & Related papers  (2021-05-31T18:00:10Z)
• Learning Unknown Physics of non-Newtonian Fluids [56.9557910899739]
  We extend the physics-informed neural network (PINN) method to learn viscosity models of two non-Newtonian systems. The PINN-inferred viscosity models agree with the empirical models for shear rates with large absolute values but deviate for shear rates near zero. We use the PINN method to solve the momentum conservation equation for non-Newtonian fluid flow using only the boundary conditions.
  arXiv  Detail & Related papers  (2020-08-26T20:41:36Z)
• 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.