Cubic regularization of Newton method and its global performance

By Yurii E. Nesterov, Boris Polyak. 2006

1,200 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

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

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

signSGD: compressed optimisation for non-convex problems (2018, background): “Theorists usually settle for measuring some restricted notion of success, such as rate of convergence to stationary points (Ghadimi & Lan, 2013; AllenZhu, 2017a) or local minima (Nesterov & Polyak, 2006).”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, methodology): “Algorithms that provably work in this setting include cubic regularization [36], trust region methods [16], approximate cubic regularization schemes [3], [12], [13], randomly initialized and perturbed (stochastic) gradients [17], [22], [22], [29], [30].”
Stochastic Variance Reduction for Nonconvex Optimization (2016, methodology): “We use Svrg (Johnson & Zhang, 2013), an algorithm recently shown to be very eﬀective for reducing variance in convex problems.”
Online Meta-Learning (2019, neutral): “As-sumption 1.3 is a statement about the higher order smoothness of functions which is common in non-convex analysis (Nesterov & Polyak, 2006; Jin et al., 2017).”
SOLA: Continual Learning with Second-Order Loss Approximation (2020, background): “ˆkw w0k 2, 8w;w 2W. We make the assumptions that the loss functions are smooth and Hessian Lipschitz. We note that the Hessian Lipschitz assumption is standard in analysis of non-convex optimization [31, 18]. Assumption 1. We assume that L k(w) is -smooth and ˆ-Hessian Lipschitz 8k2[K]. We also assu”
Generalizing to Unseen Domains via Adversarial Data Augmentation (2018, neutral): “Lemma 2 ([29, Lemma 1]) .”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “…all local minima are global, then perturbed (stochastic) gradient descent [Ge et al., 2015, Jin et al., 2017, Levy, 2016] or methods with second order information [Nesterov and Polyak, 2006, Curtis et al., 2014, Carmon et al., 2016, Allen-Zhu, 2017] can ﬁnd a global minimum in polynomial time.”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, methodology): “Assumption 4 A function F is said to be τ -gradient dominant if there exists a constant τ ∈ (0 , + ∞ ) such that where This assumption is well-known and widely used in the literature, see, e.g., (Karimi et al., 2016; Nesterov and Polyak, 2006; Polyak, 1964).”
Accelerated Methods for Non-Convex Optimization (2016, methodology): “Nesterov and Polyak [33] explore such possibilities with their work on the cubic-regularized Newton method, which they show computes an -stationary point in O(∆fL 0.5 2 −3/2) iterations (i.e. gradient and Hessian calculations).”
Second-order Conditional Gradients (2020, methodology): “Using a cubic regularized version of Newton’s method, the global convergence of the method can also be extended to a broader class of functions than that of self-concordant or strongly convex and smooth functions (Nesterov & Polyak, 2006).”
On the Oracle Complexity of First-Order and Derivative-Free Algorithms for Smooth Nonconvex Minimization (2012, methodology): “…here is the Adaptive Regularizations with Cubics (ARC) algorithm independently proposed by Griewank (1981), Weiser, Deuflhard and Erdmann (2007) and Nesterov and Polyak (2006), whose worstcase iteration complexity (1) was shown in the last of these references to be of O(ǫ −3/2 ), for finding an…”
WoodFisher: Efficient Second-Order Approximation for Neural Network Compression (2020, background): “In fact, IHVPs are a central ingredient in many parts of machine learning, most prominently for optimization [12–15], but also in other applications such as inﬂuence functions [16] or continual learning [17].”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “Other algorithms are developed for general non-convex optimization, and they can be classiﬁed into gradient-based [27, 44, 68, 4, 5, 33], Hessian-vector-product-based [12, 2, 56, 57], and Hessian-based [54, 19] methods.”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, background): “[36] Yurii Nesterov and Boris T Polyak.”
Efficient approaches for escaping higher order saddle points in non-convex optimization (2016, methodology): “For the “if” direction (necessary condition to third order local minimum), the main challenge is to balance the contribution we get from the positive part of the Hessian matrix and the third order derivatives.”
Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results (2011, methodology): “Despite the good convergence and complexity properties of the ARC algorithm, its practical efficiency ultimately relies on the ability to exactly or approximately minimize the cubic model mk. Though mk is non-convex, Theorem 3.1—first proved by different means in [19] and then, independently, in [ 2”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “This topic has been studied in [18][27][26][24][22].”