Exploiting negative curvature in deterministic and stochastic optimization
From MaRDI portal
Publication:2425164
machine learningmodified Newton methodsnegative curvaturenonconvex optimizationsecond-order methodsstochastic optimization
Numerical methods based on necessary conditions (49M05) Newton-type methods (49M15) Numerical methods based on nonlinear programming (49M37) Numerical mathematical programming methods (65K05) Stochastic programming (90C15) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Methods of quasi-Newton type (90C53)
Abstract: This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although prior work has established convergence results for algorithms that integrate both descent and negative curvature steps, there has not yet been extensive numerical evidence showing that such methods offer consistent performance improvements. In this paper, we present new frameworks for combining descent and negative curvature directions: alternating two-step approaches and dynamic step approaches. The aspect that distinguishes our approaches from ones previously proposed is that they make algorithmic decisions based on (estimated) upper-bounding models of the objective function. A consequence of this aspect is that our frameworks can, in theory, employ fixed stepsizes, which makes the methods readily translatable from deterministic to stochastic settings. For deterministic problems, we show that instances of our dynamic framework yield gains in performance compared to related methods that only follow descent steps. We also show that gains can be made in a stochastic setting in cases when a standard stochastic-gradient-type method might make slow progress.
Recommendations
- Using negative curvature in solving nonlinear programs
- scientific article; zbMATH DE number 4087442
- Exploiting negative curvature directions in linesearch methods for unconstrained optimization
- scientific article; zbMATH DE number 1694901
- Nonconvex optimization using negative curvature within a modified linesearch
Cites work
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis
- A solver for nonconvex bound-constrained quadratic optimization
- A stabilized SQP method: global convergence
- A stabilized SQP method: superlinear convergence
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Computing Modified Newton Directions Using a Partial Cholesky Factorization
- Curvilinear path steplength algorithms for minimization which use directions of negative curvature
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Exploiting negative curvature directions in linesearch methods for unconstrained optimization
- First-order methods almost always avoid strict saddle points
- scientific article; zbMATH DE number 1694901 (Why is no real title available?)
- scientific article; zbMATH DE number 3114657 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- On the use of directions of negative curvature in a modified newton method
- Optimization methods for large-scale machine learning
Cited in
(18)- The global optimization geometry of shallow linear neural networks
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Iterative grossone-based computation of negative curvature directions in large-scale optimization
- Polarity and conjugacy for quadratic hypersurfaces: a unified framework with recent advances
- Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization
- STOCHASTIC OPTIMIZATION OF MULTIPLICATIVE FUNCTIONS WITH NEGATIVE VALUE
- Sequential quadratic optimization for nonlinear equality constrained stochastic optimization
- A fully stochastic second-order trust region method
- A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer
- Open problem: Iterative schemes for stochastic optimization: convergence statements and limit theorems
- Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
- Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization
- Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems
- A deterministic gradient-based approach to avoid saddle points
- Yet another fast variant of Newton's method for nonconvex optimization
- Exploiting effective negative curvature directions via SYMMBK algorithm, in Newton-Krylov methods
- Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming
- Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm
This page was built for publication: Exploiting negative curvature in deterministic and stochastic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425164)
