INEXACT NEWTON METHODS

By R. Dembo, S. Eisenstat, Trond Steihaug. 1982

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “For inexact Newton methods to obtain quadratic convergence, it has been shown that the error term needs to decrease as a quadratic function of the gradient (Dembo et al., 1982), which is not provided by SGC, and hence the need for additional techniques such as batch growing.”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “terative approach such as the conjugate gradient (CG) method [69]. By ensuring that the linear solves are accurate enough, such an inexact Newton-CG method can enjoy a superlinear rate of convergence [47]. In fact, the computational benets of inexact Newton-CG go beyond its ability to maintain class”
New Insights and Perspectives on the Natural Gradient Method (2014, methodology): “The exact minimizer 10 δ∗ = −G(θk)−1∇h(θk) is often too difficult to compute, and so practical methods will often only approximately minimize Mk(δ) (e.g Dembo et al., 1982; Steihaug, 1983; Dennis Jr and Schnabel, 1996; Martens, 2010; Vinyals and Povey, 2012).”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, methodology): “9 t3 = 128 189 (t2)3/2 ≤ 128 189 9 4 ω(t) 3/2 ≤ √ 6− 1 10 ω3/2(t). Applying this inequality to the right-hand side of (58) completes the proof. In classical analysis of inexact Newton methods [18, 16], asymptotic superlinear convergence occurs with ǫk ∼kf′(wk)k 3/2 2 (in fact with ǫ ∼kf′(wk)ks 2”
ON NEWTON-HSS METHODS FOR SYSTEMS OF NONLINEAR EQUATIONS WITH POSITIVE-DEFINITE JACOBIAN MATRICES (2010, background): “4) where r is a residual yielded by the inner iteration due to the inexact solving; see [10,11,21,23].”
Enabling New Flexibility in the SUNDIALS Suite of Nonlinear and Differential/Algebraic Equation Solvers (2020, methodology): “For the root-finding case, KINSOL provides inexact and modified Newton methods [25, 58] which may optionally utilize a line search strategy[27].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “For further deterministic inexact methods check [36] for Inexact Newton methods, [181, 171] for Inexact Proximal Point methods and [12] for Inexact Fixed point methods.”
Jacobian-free Newton-Krylov methods: a survey of approaches and applications (2004, background): “(2) does not require the exact solution of the linear system, the resulting algorithm is categorized as an ‘‘inexact’’ Newton s method [53].”
SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization (2002, methodology): “This “loose tolerance” strategy provides a dynamic balance between major and minor iterations in the manner of inexact Newton methods (Dembo, Eisenstat, and Steihaug [23]).”
Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2015, background): “While these strategies are popular, theoretical analysis of inexact Newton methods typically need strong assumptions on the eigenvalues of the Hessian [11].”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “For further deterministic inexact methods check [10] for Inexact Newton methods, [52, 47] for Inexact Proximal Point methods and [3] for Inexact Fixed point methods.”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, methodology): “[14] Ron S Dembo, Stanley C Eisenstat, and Trond Steihaug.”
Sub-sampled Newton Methods with Non-uniform Sampling (2016, background): “Such inexact updates used in many second-order optimization algorithms have been well studied in [4, 5].”