Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of
  Newton Method
Nikita Doikov
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.