Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
Author:
Preprint
Abstract
We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball-minimization oracle. In this paper, we show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the Dual Newton Method, and based on it, develop the corresponding Accelerated Newton Scheme for this problem class, which further improves the complexity factor of the basic method. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton Method applied to several practical problems, including Logistic Regression, Soft Maximum, and Matrix Scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Set-Limited Functions and Polynomial-Time Interior-Point MethodsJournal of Optimization Theory and Applications, 2023
- Minimizing Uniformly Convex Functions by Cubic Regularization of Newton MethodJournal of Optimization Theory and Applications, 2021
- Local convergence of tensor methodsMathematical Programming, 2021
- Sharp Worst-Case Evaluation Complexity Bounds for Arbitrary-Order Nonconvex Optimization with Inexpensive ConstraintsSIAM Journal on Optimization, 2020
- Oracle complexity of second-order methods for smooth convex optimizationMathematical Programming, 2018
- Generalized self-concordant functions: a recipe for Newton-type methodsMathematical Programming, 2018
- A regularized Newton method without line search for unconstrained optimizationComputational Optimization and Applications, 2014
- Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical resultsMathematical Programming, 2009
- Cubic regularization of Newton method and its global performanceMathematical Programming, 2006
- Interior-Point Polynomial Algorithms in Convex Programming1994