Convex optimization based on global lower second-order models

Abstract

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.

References in corpus (7)

• Variance-Reduced and Projection-Free Stochastic Optimization
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Randomized Block Cubic Newton Method

Cited by in corpus (1)

• Optimization Methods for Fully Composite Problems