Adaptive regularization with cubics on manifolds
Adaptive regularization with cubics on manifolds
复制标题
DOI：
10.1007/s10107-020-01505-1
复制
发表时间：
2018-05
影响因子：
2.7
通讯作者：
Naman Agarwal;Nicolas Boumal;Brian Bullins;C. Cartis
中科院分区：
文献类型：
--
作者：
Naman Agarwal;Nicolas Boumal;Brian Bullins;C. Cartis
自适应三次正则化（ARC）是一种无约束非凸优化算法。类似于信赖域方法，它的迭代可以被认为是近似的、安全的牛顿步骤。对于具有Lipschitz连续Hessian的代价函数，ARC具有最优迭代复杂度，在这个意义上，它产生的迭代的梯度小于迭代。对于相同的价格，它还可以保证最小特征值大于的Hessian。在本文中，我们研究了ARC的推广到黎曼流形上的优化。特别是，我们概括的迭代复杂性的结果，这个更丰富的框架。我们的核心贡献在于识别适当的流形特定的假设，使我们能够确保这些复杂性的保证时，使用指数映射和使用一般收缩。本文的一个重要部分是致力于研究这些相关的ARC以外，并为他们提供用户友好的充分条件。数值实验是令人鼓舞的。
Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the trust-region method, its iterations can be thought of as approximate, safe-guarded Newton steps. For cost functions with Lipschitz continuous Hessian, ARC has optimal iteration complexity, in the sense that it produces an iterate with gradient smaller thaniniterations. For the same price, it can also guarantee a Hessian with smallest eigenvalue larger than. In this paper, we study a generalization of ARC to optimization on Riemannian manifolds. In particular, we generalize the iteration complexity results to this richer framework. Our central contribution lies in the identification of appropriate manifold-specific assumptions that allow us to secure these complexity guarantees both when using the exponential map and when using a general retraction. A substantial part of the paper is devoted to studying these assumptions—relevant beyond ARC—and providing user-friendly sufficient conditions for them. Numerical experiments are encouraging.