论文标题
基于全局二阶模型的凸优化
Convex optimization based on global lower second-order models
论文作者
论文摘要
在本文中，我们提出了用于复合凸优化的新二阶算法，称为合同域牛顿方法。这些算法是仿射不变的，并且基于目标平滑部分的全局二阶较低近似值。我们的方法将解释既是条件梯度方法的二阶概括，又是信任区域方案的变体。在假设问题域是有界的假设下，我们证明$ \ Mathcal {o}（1/k^{2}）$函数残差中的全局收敛速率，其中$ k $是迭代的次数计数器，最小化凸的凸面功能与lipschitz的连续hessian。这大大改善了此类算法的先前已知绑定的$ \ Mathcal {O}（1/K）$。此外，我们提出了我们方法的随机扩展，并提出了解决经验风险最小化问题的计算结果。
In this paper, we present new second-order algorithms for composite convex optimization, called Contracting-domain Newton methods. These algorithms are affine-invariant and based on global second-order lower approximation for the smooth component of the objective. Our approach has an interpretation both as a second-order generalization of the conditional gradient method, or as a variant of trust-region scheme. Under the assumption, that the problem domain is bounded, we prove $\mathcal{O}(1/k^{2})$ global rate of convergence in functional residual, where $k$ is the iteration counter, minimizing convex functions with Lipschitz continuous Hessian. This significantly improves the previously known bound $\mathcal{O}(1/k)$ for this type of algorithms. Additionally, we propose a stochastic extension of our method, and present computational results for solving empirical risk minimization problem.
