Exploiting negative curvature in deterministic and stochastic optimization
From MaRDI portal
Publication:2425164
machine learningnonconvex optimizationstochastic optimizationsecond-order methodsnegative curvaturemodified Newton methods
Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Stochastic programming (90C15) Methods of quasi-Newton type (90C53) Newton-type methods (49M15) Numerical methods based on necessary conditions (49M05)
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
- 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?)
- 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
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- 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
- Exploiting negative curvature directions in linesearch methods for unconstrained optimization
- First-order methods almost always avoid strict saddle points
- On the use of directions of negative curvature in a modified newton method
- Optimization methods for large-scale machine learning
Cited in
(14)- The global optimization geometry of shallow linear neural networks
- 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
- Open problem: Iterative schemes for stochastic optimization: convergence statements and limit theorems
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
- Iterative grossone-based computation of negative curvature directions in large-scale optimization
- Polarity and conjugacy for quadratic hypersurfaces: a unified framework with recent advances
- STOCHASTIC OPTIMIZATION OF MULTIPLICATIVE FUNCTIONS WITH NEGATIVE VALUE
- A deterministic gradient-based approach to avoid saddle points
- Sequential quadratic optimization for nonlinear equality constrained stochastic optimization
- Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization
- A fully stochastic second-order trust region method
- A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer
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)
