In this work, 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 $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 $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.

Summary and Contributions: This paper presents new second-order algorithms for the prototypical composite convex optimization problem. First, the paper introduces a new global second-order lower approximation. Based on this lower approximation model, the paper introduces a new second-order optimization algorithm. The proposed method successively minimizes the lower approximation model of the smooth term augmented by the nonsmooth term and constructs the solution to the original problem as a convex combination of the solutions to these subproblems. In this regard, it can be seen as a second-order modification of the Frank-Wolfe method, which considers a second-order lower model instead of the first-order.

In this work, 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 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 O(1/k) for this type of algorithms.