Exploiting negative curvature in deterministic and stochastic optimization
Exploiting negative curvature in deterministic and stochastic optimization
复制标题
DOI：
10.1007/s10107-018-1335-8
复制
发表时间：
2019-07-01
影响因子：
2.7
通讯作者：
Robinson, Daniel P.
中科院分区：
文献类型：
--
作者：
Curtis, Frank E.;Robinson, Daniel P.
本文讨论的问题，它是否可以是有益的优化算法，以遵循负曲率的方向。虽然先前的工作已经建立了收敛结果的算法，集成下降和负曲率步骤，还没有广泛的数值证据表明，这种方法提供了一致的性能改善。在本文中，我们提出了新的框架相结合的下降和负曲率方向：交替两步方法和动态步骤的方法。我们的方法与以前提出的方法的区别在于，它们基于目标函数的（估计）上界模型做出算法决策。这方面的一个结果是，我们的框架可以，在理论上，采用固定的步长，这使得方法很容易从确定性转换到随机设置。对于确定性问题，我们表明，我们的动态框架的实例产生收益的性能相比，相关的方法，只遵循下降步骤。我们还表明，收益可以在一个随机设置的情况下，当一个标准的随机梯度型方法可能会取得缓慢的进展。
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.