# Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2019.

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

- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Error Scaling Laws for Kernel Classification under Source and Capacity Conditions](https://mlsanity.com/paper/2201.12655/) (2022)
- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent](https://mlsanity.com/paper/2205.07331/) (2022)
- [Efficient Methods for Online Multiclass Logistic Regression](https://mlsanity.com/paper/2110.03020/) (2021)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)
- [Fast kernel methods for Data Quality Monitoring as a goodness-of-fit test](https://mlsanity.com/paper/2303.05413/) (2023)
- [Adaptive learning of density ratios in RKHS](https://mlsanity.com/paper/2307.16164/) (2023)
- [Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits](https://mlsanity.com/paper/2410.01112/) (2024)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)
- [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)
- [Efficient and Robust Regularized Federated Recommendation](https://mlsanity.com/paper/2411.01540/) (2024)
- [Computational Efficiency under Covariate Shift in Kernel Ridge Regression](https://mlsanity.com/paper/2505.14083/) (2025)
- [SCORE: Approximating Curvature Information under Self-Concordant Regularization](https://mlsanity.com/paper/2112.07344/) (2021)
- [A Case of Exponential Convergence Rates for SVM](https://mlsanity.com/paper/2205.10055/) (2022)
- [Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps](https://mlsanity.com/paper/2105.13913/) (2021)
- [Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularization](https://mlsanity.com/paper/2106.08855/) (2021)
- [Confidence Sets under Generalized Self-Concordance](https://mlsanity.com/paper/2301.00260/) (2022)
- [An Online Multiple Kernel Parallelizable Learning Scheme](https://mlsanity.com/paper/2308.10101/) (2023)
- [Data Depth as a Risk](https://mlsanity.com/paper/2507.08518/) (2025)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Kernel-based estimation for partially functional linear model: Minimax rates and randomized sketches](https://mlsanity.com/paper/2110.09042/) (2021)
- [Dual Instrumental Method for Confounded Kernelized Bandits](https://mlsanity.com/paper/2209.03224/) (2022)
- [Doubly Stochastic Models: Learning with Unbiased Label Noises and Inference Stability](https://mlsanity.com/paper/2304.00320/) (2023)
- [Near-Optimal and Tractable Estimation under Shift-Invariance](https://mlsanity.com/paper/2411.03383/) (2024)
- [Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding](https://mlsanity.com/paper/2605.26067/) (2026)

## Abstract (arXiv)

We consider learning methods based on the regularization of a convex empirical risk by a squared Hilbertian norm, a setting that includes linear predictors and non-linear predictors through positive-definite kernels. In order to go beyond the generic analysis leading to convergence rates of the excess risk as O(1/√n) from n observations, we assume that the individual losses are self-concordant, that is, their third-order derivatives are bounded by their second-order derivatives. This setting includes least-squares, as well as all generalized linear models such as logistic and softmax regression. For this class of losses, we provide a bias-variance decomposition and show that the assumptions commonly made in least-squares regression, such as the source and capacity conditions, can be adapted to obtain fast non-asymptotic rates of convergence by improving the bias terms, the variance terms or both.