Exploiting Negative Curvature in Deterministic and Stochastic Optimization
Frank E. Curtis (frank.e.curtisgmail.com)
Abstract: This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although some prior work has established convergence results for algorithms that integrate both descent and negative curvature directions, there has not yet been numerical evidence showing that such methods offer significant performance improvements. In this paper, we present new frameworks for combining descent and negative curvature directions: alternating two-step approaches and dynamic step approaches. A unique aspect of each of our frameworks is that fixed stepsizes can be used (rather than line searches or trust regions), which makes the methods viable for both deterministic and stochastic settings. For deterministic problems, we show that our dynamic framework yields significant gains in performance (in terms of lower objective function values in a fixed number of iterations) compared to a gradient descent method. We also show that while the gains offered in a stochastic setting might be more modest, they can be notable.
Keywords: stochastic optimization, unconstrained optimization, negative curvature, deep neural networks
Category 1: Stochastic Programming
Category 2: Nonlinear Optimization (Unconstrained Optimization )
Citation: F. E. Curtis and D. P. Robinson. Exploiting Negative Curvature in Deterministic and Stochastic Optimization. Mathematical Programming, Series B, 176(1):69–94, 2019.
Entry Submitted: 02/28/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|