# Finite-sample analysis of M-estimators using self-concordance arXiv: https://arxiv.org/abs/1810.06838 · HTML: https://mlsanity.com/paper/1810.06838/ ## Key facts - Cited by 30 papers in the map (data through 14 Oct 2026). - First posted on arXiv 16 Oct 2018. ## Built on by (most cited first, 30 of 30) - [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023) - [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021) - [On the sample complexity of parameter estimation in logistic regression with normal design](https://mlsanity.com/paper/2307.04191/) (2023) - [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021) - [Learning to be Fair: A Consequentialist Approach to Equitable Decision-Making](https://mlsanity.com/paper/2109.08792/) (2021) - [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025) - [Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits](https://mlsanity.com/paper/2410.01112/) (2024) - [Non-Asymptotic Guarantees for Robust Statistical Learning under Infinite Variance Assumption](https://mlsanity.com/paper/2201.03182/) (2022) - [Overcoming Saturation in Density Ratio Estimation by Iterated Regularization](https://mlsanity.com/paper/2402.13891/) (2024) - [Multiply Robust Estimation for Local Distribution Shifts with Multiple Domains](https://mlsanity.com/paper/2402.14145/) (2024) - [SCORE: Approximating Curvature Information under Self-Concordant Regularization](https://mlsanity.com/paper/2112.07344/) (2021) - [A Differentially Private Weighted Empirical Risk Minimization Procedure and its Application to Outcome Weighted Learning](https://mlsanity.com/paper/2307.13127/) (2023) - [Sharper Generalization Bounds for Transformer](https://mlsanity.com/paper/2603.21541/) (2026) - [Orthogonal Statistical Learning with Self-Concordant Loss](https://mlsanity.com/paper/2205.00350/) (2022) - [A Conditional Randomization Test for Sparse Logistic Regression in High-Dimension](https://mlsanity.com/paper/2205.14613/) (2022) - [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023) - [A Geometric Analysis of PCA](https://mlsanity.com/paper/2510.20978/) (2025) - [Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis](https://mlsanity.com/paper/2512.24999/) (2025) - [Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps](https://mlsanity.com/paper/2105.13913/) (2021) - [Statistical and Computational Guarantees for Influence Diagnostics](https://mlsanity.com/paper/2212.04014/) (2022) - [Confidence Sets under Generalized Self-Concordance](https://mlsanity.com/paper/2301.00260/) (2022) - [Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization](https://mlsanity.com/paper/2309.01781/) (2023) - [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024) - [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026) - [Fast Rates for Inverse Reinforcement Learning](https://mlsanity.com/paper/2605.14599/) (2026) - [Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problem](https://mlsanity.com/paper/2111.06826/) (2021) - [FIRAL: An Active Learning Algorithm for Multinomial Logistic Regression](https://mlsanity.com/paper/2409.07379/) (2024) - [Near-Optimal and Tractable Estimation under Shift-Invariance](https://mlsanity.com/paper/2411.03383/) (2024) - [Generalized Linear Markov Decision Process](https://mlsanity.com/paper/2506.00818/) (2025) - [Minimax Optimal Estimator and Improved Error Rate for the MLE in Logistic Regression with Gaussian Design](https://mlsanity.com/paper/2608.17260/) (2026) ## Abstract (arXiv) The classical asymptotic theory for parametric M-estimators guarantees that, in the limit of infinite sample size, the excess risk has a chi-square type distribution, even in the misspecified case. We demonstrate how self-concordance of the loss allows to characterize the critical sample size sufficient to guarantee a chi-square type in-probability bound for the excess risk. Specifically, we consider two classes of losses: (i) self-concordant losses in the classical sense of Nesterov and Nemirovski, i.e., whose third derivative is uniformly bounded with the 3/2 power of the second derivative; (ii) pseudo self-concordant losses, for which the power is removed. These classes contain losses corresponding to several generalized linear models, including the logistic loss and pseudo-Huber losses. Our basic result under minimal assumptions bounds the critical sample size by O(d · deff), where d the parameter dimension and deff the effective dimension that accounts for model misspecification. In contrast to the existing results, we only impose local assumptions that concern the population risk minimizer θ_*. Namely, we assume that the calibrated design, i.e., design scaled by the square root of the second derivative of the loss, is subgaussian at θ_*. Besides, for type-ii losses we require boundedness of a certain measure of curvature of the population risk at θ_*.Our improved result bounds the critical sample size from above as O(maxdeff, d log d) under slightly stronger assumptions. Namely, the local assumptions must hold in the neighborhood of θ_* given by the Dikin ellipsoid of the population risk. Interestingly, we find that, for logistic regression with Gaussian design, there is no actual restriction of conditions: the subgaussian parameter and curvature measure remain near-constant over the Dikin ellipsoid. Finally, we extend some of these results to ℓ1-penalized estimators in high dimensions.