This paper addresses the question of whether it can be beneficial for anoptimization algorithm to follow directions of negative curvature. Althoughsome prior work has established convergence results for algorithms thatintegrate both descent and negative curvature steps, there has not yet beenextensive numerical evidence showing that such methods offer consistentperformance improvements. In this paper, we present new frameworks forcombining descent and negative curvature directions: alternating two-stepapproaches and dynamic step approaches. The aspect that distinguishes ourapproaches from ones previously proposed is that they make algorithmicdecisions based on (estimated) upper-bounding models of the objective function.A consequence of this aspect is that our frameworks can, in theory, employfixed stepsizes, which makes the methods readily translatable fromdeterministic to stochastic settings. For deterministic problems, we show thatinstances of our dynamic framework yield gains in performance compared torelated methods that only follow descent steps. We also show that gains can bemade in a stochastic setting in cases when a standard stochastic-gradient-typemethod might make slow progress.
展开▼