# Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2019.

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

- [Conditional Distributional Treatment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regression](https://mlsanity.com/paper/2102.08208/) (2021)
- [FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning](https://mlsanity.com/paper/2206.08829/) (2022)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021)
- [Sampling from Arbitrary Functions via PSD Models](https://mlsanity.com/paper/2110.10527/) (2021)
- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [Fast kernel methods for Data Quality Monitoring as a goodness-of-fit test](https://mlsanity.com/paper/2303.05413/) (2023)
- [Learning in RKHM: a C^*-Algebraic Twist for Kernel Machines](https://mlsanity.com/paper/2210.11855/) (2022)
- [Overcoming Saturation in Density Ratio Estimation by Iterated Regularization](https://mlsanity.com/paper/2402.13891/) (2024)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)
- [Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularization](https://mlsanity.com/paper/2106.08855/) (2021)
- [Online Estimation with Rolling Validation: Adaptive Nonparametric Estimation with Streaming Data](https://mlsanity.com/paper/2310.12140/) (2023)
- [Joker: Joint Optimization Framework for Lightweight Kernel Machines](https://mlsanity.com/paper/2505.17765/) (2025)
- [Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity](https://mlsanity.com/paper/2405.16126/) (2024)
- [BD-Net: Has Depth-Wise Convolution Ever Been Applied in Binary Neural Networks?](https://mlsanity.com/paper/2511.17633/) (2025)
- [How Much Rank Does LoRA Need? Rank-Error Bounds for Transformer Attention](https://mlsanity.com/paper/2608.26052/) (2026)

## Abstract (arXiv)

In this paper, we study large-scale convex optimization algorithms based on the Newton method applied to regularized generalized self-concordant losses, which include logistic regression and softmax regression. We first prove that our new simple scheme based on a sequence of problems with decreasing regularization parameters is provably globally convergent, that this convergence is linear with a constant factor which scales only logarithmically with the condition number. In the parametric setting, we obtain an algorithm with the same scaling than regular first-order methods but with an improved behavior, in particular in ill-conditioned problems. Second, in the non parametric machine learning setting, we provide an explicit algorithm combining the previous scheme with Nystr"om projection techniques, and prove that it achieves optimal generalization bounds with a time complexity of order O(ndf λ), a memory complexity of order O(df 2 λ) and no dependence on the condition number, generalizing the results known for least-squares regression. Here n is the number of observations and df λ is the associated degrees of freedom. In particular, this is the first large-scale algorithm to solve logistic and softmax regressions in the non-parametric setting with large condition numbers and theoretical guarantees.