Regularized Newton Method with Global O(1/k^2) Convergence
From MaRDI portal
Publication:6116237
Abstract: We present a Newton-type method that converges fast from any initialization and for arbitrary convex objectives with Lipschitz Hessians. We achieve this by merging the ideas of cubic regularization with a certain adaptive Levenberg--Marquardt penalty. In particular, we show that the iterates given by , where is a constant, converge globally with a rate. Our method is the first variant of Newton's method that has both cheap iterations and provably fast global convergence. Moreover, we prove that locally our method converges superlinearly when the objective is strongly convex. To boost the method's performance, we present a line search procedure that does not need prior knowledge of and is provably efficient.
Recommendations
- Accelerating the cubic regularization of Newton's method on convex problems
- Cubic regularization of Newton method and its global performance
- On the convergence of a modified regularized Newton method for convex optimization with singular solutions
- Regularized Newton methods for convex minimization problems with singular solutions
- A regularized Newton method without line search for unconstrained optimization
Cites work
- A continuous dynamical Newton-like approach to solving monotone inclusions
- A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity \(\mathcal{O}(1/n^2)\)
- A method for the solution of certain non-linear problems in least squares
- A Nonmonotone Line Search Technique for Newton’s Method
- A regularized Newton method without line search for unconstrained optimization
- Accelerating the cubic regularization of Newton's method on convex problems
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- An Algorithm for Least-Squares Estimation of Nonlinear Parameters
- Convergence and complexity analysis of a Levenberg-Marquardt algorithm for inverse problems
- Convergence Properties of the Inexact Levenberg-Marquardt Method under Local Error Bound Conditions
- Cubic regularization of Newton method and its global performance
- Curiosities and counterexamples in smooth convex optimization
- Gradient methods for minimizing composite functions
- Gradient methods of maximization
- Greedy quasi-Newton methods with explicit superlinear convergence
- High-order optimization methods for fully composite problems
- scientific article; zbMATH DE number 1694914 (Why is no real title available?)
- scientific article; zbMATH DE number 3579922 (Why is no real title available?)
- scientific article; zbMATH DE number 1306984 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- Implementable tensor methods in unconstrained convex optimization
- Inexact accelerated high-order proximal-point methods
- Introductory lectures on convex optimization. A basic course.
- Large-scale machine learning with stochastic gradient descent
- Lectures on convex optimization
- Levenberg-Marquardt method for solving systems of absolute value equations
- Majorization-minimization-based Levenberg-Marquardt method for constrained nonlinear least squares
- Minimization of functions having Lipschitz continuous first partial derivatives
- Modified Gauss–Newton scheme with worst case guarantees for global performance
- On the divergence of line search methods
- On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization
- On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption
- Optimization methods for large-scale machine learning
- Oracle complexity of second-order methods for smooth convex optimization
- Regularized Newton method for unconstrained convex optimization
- Regularized Newton methods for convex minimization problems with singular solutions
- Simple examples for the failure of Newton's method with line search for strictly convex minimization
- Superfast second-order methods for unconstrained convex optimization
- The use of quadratic regularization with a cubic descent condition for unconstrained optimization
- Trust Region Methods
- Universal Regularization Methods: Varying the Power, the Smoothness and the Accuracy
Cited in
(21)- On the convergence of a modified regularized Newton method for convex optimization with singular solutions
- Complexity of the regularized Newton's method
- Super-Universal Regularized Newton Method
- Gradient regularization of Newton method with Bregman distances
- Communication-efficient distributed cubic Newton with compressed lazy Hessian
- A hybrid inexact regularized Newton and negative curvature method
- On the linear convergence of additive Schwarz methods for the p-Laplacian
- Homogeneous second-order descent framework: a fast alternative to Newton-type methods
- Beyond nonconvexity: a universal trust-region method with new analyses
- Gradient norm regularization second-order algorithms for solving nonconvex-strongly concave minimax problems
- Yet another fast variant of Newton's method for nonconvex optimization
- Accelerated adaptive cubic regularized quasi-Newton methods
- Convergence analysis of a regularized Newton method with generalized regularization terms for unconstrained convex optimization problems
- Incremental Gauss-Newton methods with superlinear convergence rates
- A Hessian-free inexact regularized Newton method for composite convex optimization
- Randomized subspace correction methods for convex optimization
- Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization
- Improved global performance guarantees of second-order methods in convex minimization
- Minimizing quasi-self-concordant functions by gradient regularization of Newton method
- Escaping saddle points in distributed nonconvex optimization via cubic regularization
- Accelerating the cubic regularization of Newton's method on convex problems
This page was built for publication: Regularized Newton Method with Global \({\boldsymbol{\mathcal{O}(1/{k}^2)}}\) Convergence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116237)
