# Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method

arXiv: https://arxiv.org/abs/2308.14742 · HTML: https://mlsanity.com/paper/2308.14742/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 28 Aug 2023.

## Builds on (most cited first, 15 of 15)

- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Gradient Regularization of Newton Method with Bregman Distances](https://mlsanity.com/paper/2112.02952/) (2021)
- [Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method](https://mlsanity.com/paper/1905.02671/) (2019)
- [Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods](https://mlsanity.com/paper/1704.02310/) (2017)
- [Local convergence of tensor methods](https://mlsanity.com/paper/1912.02516/) (2019)
- [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints](https://mlsanity.com/paper/1811.01220/) (2018)
- [Tensor Methods for Minimizing Convex Functions with H"older Continuous Higher-Order Derivatives](https://mlsanity.com/paper/1904.12559/) (2019)
- [Contracting Proximal Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1912.07972/) (2019)

## Built on by (most cited first, 7 of 7)

- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [DADA: Dual Averaging with Distance Adaptation](https://mlsanity.com/paper/2501.10258/) (2025)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Gradient Regularized Newton Boosting Trees with Global Convergence](https://mlsanity.com/paper/2605.00581/) (2026)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)
- [On Optimization Complexity of Second-Order Certified Unlearning](https://mlsanity.com/paper/2607.20192/) (2026)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)

## Abstract (arXiv)

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.