{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T15:53:02Z","timestamp":1791474782268,"version":"4.3.4"},"reference-count":66,"publisher":"Institute of Mathematical Statistics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Statist."],"published-print":{"date-parts":[[2021,1,1]]},"abstract":"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.\n Our basic result under minimal assumptions bounds the critical sample size by $O(d\\cdot d_{\\text{eff}})$, where $d$ the parameter dimension and $d_{\\text{eff}}$ 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 $\\theta _{*}$. Namely, we assume that the calibrated predictors, i.e., predictors scaled by the square root of the second derivative of the loss, is subgaussian at $\\theta _{*}$. Besides, for type-ii losses we require boundedness of certain measure of curvature of the population risk at $\\theta _{*}$.\n Our improved result bounds the critical sample size from above as \\begin{equation*}O(\\max \\{d_{\\text{eff}},d\\log d\\})\\end{equation*} under slightly stronger assumptions. Namely, the local assumptions must hold in the neighborhood of $\\theta _{*}$ 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 $\\ell _{1}$-penalized estimators in high dimensions.<\/jats:p>","DOI":"10.1214\/20-ejs1780","type":"journal-article","created":{"date-parts":[[2021,1,5]],"date-time":"2021-01-05T22:04:31Z","timestamp":1609884271000},"page":"326-391","source":"Crossref","is-referenced-by-count":18,"title":["Finite-sample analysis of $M$-estimators using self-concordance"],"prefix":"10.1214","volume":"15","author":[{"given":"Dmitrii M.","family":"Ostrovskii","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francis","family":"Bach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] Abramowitz, M. and Stegun, I. A. (1965)., Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables<\/i> 55<\/b>. Courier Corporation.","DOI":"10.1115\/1.3625776"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] Bach, F. (2010). Self-concordant analysis for logistic regression., Electronic Journal of Statistics<\/i> 4<\/b> 384\u2013414.","DOI":"10.1214\/09-EJS521"},{"key":"3","unstructured":"[3] Bach, F. (2014). Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression., The Journal of Machine Learning Research<\/i> 15<\/b> 595\u2013627."},{"key":"4","unstructured":"[4] Bach, F. and Moulines, E. (2013). Non-strongly-convex Smooth Stochastic Approximation with Convergence Rate $O(1\/n)$. In, Proceedings of the 26th International Conference on Neural Information Processing Systems<\/i> 1<\/b> 773\u2013781."},{"key":"5","unstructured":"[5] Barbier, J., Krzakala, F., Macris, N., Miolane, L. and Zdeborov\u00e1, L. (2018). Phase transitions, optimal errors and optimality of message-passing in generalized linear models. In, Proceedings of the 31st Conference On Learning Theory<\/i> 75<\/b> 728\u2013731."},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] Bartlett, M. S. (1953). Approximate confidence intervals. II. More than one unknown parameter., Biometrika<\/i> 40<\/b> 306\u2013317.","DOI":"10.1093\/biomet\/40.1-2.12"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] Bartlett, P. L., Jordan, M. I. and McAuliffe, J. D. (2006). Convexity, classification, and risk bounds., Journal of the American Statistical Association<\/i> 101<\/b> 138\u2013156.","DOI":"10.1198\/016214505000000907"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] Belloni, A., Chernozhukov, V. and Wang, L. (2011). Square-root lasso: pivotal recovery of sparse signals via conic programming., Biometrika<\/i> 98<\/b> 791\u2013806.","DOI":"10.1093\/biomet\/asr043"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] Bickel, P. J., Ritov, Y. and Tsybakov, A. B. (2009). Simultaneous analysis of Lasso and Dantzig selector., The Annals of Statistics<\/i> 37<\/b> 1705\u20131732.","DOI":"10.1214\/08-AOS620"},{"key":"11","unstructured":"[11] Bubeck, S. and Eldan, R. (2015). The entropic barrier: a simple and optimal universal self-concordant barrier. In, Proceedings of The 28th Conference on Learning Theory<\/i> 40<\/b> 279\u2013279."},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] Candes, E. and Tao, T. (2007). The Dantzig selector: statistical estimation when $p$ is much larger than $n$., The Annals of Statistics<\/i> 36<\/b> 2313\u20132351.","DOI":"10.1214\/009053606000001523"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] Caponnetto, A. and De Vito, E. (2007). Optimal rates for the regularized least-squares algorithm., Foundations of Computational Mathematics<\/i> 7<\/b> 331\u2013368.","DOI":"10.1007\/s10208-006-0196-8"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] Chernozhukov, V., Chetverikov, D. and Kato, K. (2017). Central limit theorems and bootstrap in high dimensions., The Annals of Probability<\/i> 45<\/b> 2309\u20132352.","DOI":"10.1214\/16-AOP1113"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] Donoho, D. and Montanari, A. (2016). High-dimensional robust $M$-estimation: Asymptotic variance via approximate message passing., Probability Theory and Related Fields<\/i> 166<\/b> 935\u2013969.","DOI":"10.1007\/s00440-015-0675-z"},{"key":"17","unstructured":"[17] Foster, D. J., Kale, S., Luo, H., Mohri, M. and Sridharan, K. (2018). Logistic regression: the importance of being improper. In, Proceedings of the 31st Conference On Learning Theory<\/i> 75<\/b> 167\u2013208."},{"key":"18","unstructured":"[18] Hazan, E., Koren, T. and Levy, K. Y. (2014). Logistic regression: tight bounds for stochastic and online optimization. In, Proceedings of The 27th Conference on Learning Theory<\/i> 35<\/b> 197\u2013209."},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] Hsu, D., Kakade, S. M. and Zhang, T. (2012). Random design analysis of ridge regression., The Journal of Machine Learning Research<\/i> 23<\/b> 1-24.","DOI":"10.1007\/s10208-014-9192-1"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] Hsu, D., Kakade, S. M. and Zhang, T. (2012). A tail inequality for quadratic forms of subgaussian random vectors., Electronic Communications in Probability<\/i> 17<\/b> 1\u20136.","DOI":"10.1214\/ECP.v17-2079"},{"key":"21","unstructured":"[21] Hsu, D. and Sabato, S. (2016). Loss minimization and parameter estimation with heavy tails., The Journal of Machine Learning Research<\/i> 17<\/b> 543\u2013582."},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] Huber, P. J. (1964). Robust Estimation of a Location Parameter., The Annals of Mathematical Statistics<\/i> 35<\/b> 73\u2013101.","DOI":"10.1214\/aoms\/1177703732"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] Juditsky, A. and Nemirovski, A. S. (2011). On verifiable sufficient conditions for sparse signal recovery via $\\ell _1$-minimization., Mathematical Programming<\/i> 127<\/b> 57\u201388.","DOI":"10.1007\/s10107-010-0417-z"},{"key":"27","doi-asserted-by":"publisher","unstructured":"[27] Koltchinskii, V. and Lounici, K. (2017). Concentration inequalities and moment bounds for sample covariance operators., Bernoulli<\/i> 23<\/b> 110\u2013133.","DOI":"10.3150\/15-BEJ730"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] Laurent, B. and Massart, P. (2000). Adaptive estimation of a quadratic functional by model selection., The Annals of Statistics<\/i> 28<\/b> 1302\u20131338.","DOI":"10.1214\/aos\/1015957395"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[29] Lee, J. D., Sun, Y. and Saunders, M. A. (2014). Proximal Newton-type methods for minimizing composite functions., SIAM Journal on Optimization<\/i> 24<\/b> 1420\u20131443.","DOI":"10.1137\/130921428"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[31] Loh, P.-L. (2017). Statistical consistency and asymptotic normality for high-dimensional robust $M$-estimators., The Annals of Statistics<\/i> 45<\/b> 866\u2013896.","DOI":"10.1214\/16-AOS1471"},{"key":"33","unstructured":"[33] Loh, P.-L. and Wainwright, M. J. (2015). Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima., The Journal of Machine Learning Research<\/i> 16<\/b> 559\u2013616."},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] Loh, P.-L. and Wainwright, M. J. (2017). Support recovery without incoherence: A case for nonconvex regularization., The Annals of Statistics<\/i> 45<\/b> 2455\u20132482.","DOI":"10.1214\/16-AOS1530"},{"key":"36","unstructured":"[36] Marteau-Ferey, U., Ostrovskii, D., Bach, F. and Rudi, A. (2019)., Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance<\/i> 99<\/b>. PMLR, Phoenix, USA."},{"key":"38","unstructured":"[38] Mehta, N. A. (2017). Fast rates with high probability in exp-concave statistical learning. In, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics<\/i> 54<\/b> 1085\u20131093."},{"key":"39","doi-asserted-by":"publisher","unstructured":"[39] Mei, S., Bai, Y. and Montanari, A. (2018). The landscape of empirical risk for nonconvex losses., The Annals of Statistics<\/i> 46<\/b> 2747\u20132774.","DOI":"10.1214\/17-AOS1637"},{"key":"41","doi-asserted-by":"publisher","unstructured":"[41] Negahban, S. N., Ravikumar, P., Wainwright, M. J. and Yu, B. (2012). A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers., Statistical Science<\/i> 27<\/b> 538\u2013557.","DOI":"10.1214\/12-STS400"},{"key":"45","unstructured":"[45] Ostrovskii, D. M. and Rudi, A. (2019). Affine Invariant Covariance Estimation for Heavy-Tailed Distributions. In, Proceedings of the Thirty-Second Conference on Learning Theory<\/i> 99<\/b> 2531\u20132550. PMLR, Phoenix, USA."},{"key":"49","doi-asserted-by":"publisher","unstructured":"[49] Spokoiny, V. (2012). Parametric estimation. Finite sample theory., The Annals of Statistics<\/i> 40<\/b> 2877\u20132909.","DOI":"10.1214\/12-AOS1054"},{"key":"50","doi-asserted-by":"publisher","unstructured":"[50] Sun, T. and Tran-Dinh, Q. (2018). Generalized self-concordant functions: a recipe for Newton-type methods., Mathematical Programming<\/i> 169<\/b> 1\u201369.","DOI":"10.1007\/s10107-018-1282-4"},{"key":"51","doi-asserted-by":"publisher","unstructured":"[51] Sur, P. and Cand\u00e8s, E. J. (2019). A modern maximum-likelihood theory for high-dimensional logistic regression., Proceedings of the National Academy of Sciences<\/i> 116<\/b> 14516\u201314525.","DOI":"10.1073\/pnas.1810420116"},{"key":"53","doi-asserted-by":"publisher","unstructured":"[53] Thrampoulidis, C., Abbasi, E. and Hassibi, B. (2018). Precise Error Analysis of Regularized $M$-Estimators in High Dimensions., IEEE Transactions on Information Theory<\/i> 64<\/b> 5592\u20135628.","DOI":"10.1109\/TIT.2018.2840720"},{"key":"54","doi-asserted-by":"publisher","unstructured":"[54] Tibshirani, R. (1996). Regression shrinkage and selection via the Lasso., Journal of the Royal Statistical Society, Series B (Methodological)<\/i> 58<\/b> 267\u2013288.","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"55","unstructured":"[55] Tran-Dinh, Q., Kyrillidis, A. and Cevher, V. (2015). Composite self-concordant minimization., The Journal of Machine Learning Research<\/i> 16<\/b> 371\u2013416."},{"key":"56","doi-asserted-by":"publisher","unstructured":"[56] van de Geer, S. A. and M\u00fcller, P. (2012). Quasi-likelihood and\/or robust estimation in high dimensions., Statistical Science<\/i> 27<\/b> 469\u2013480.","DOI":"10.1214\/12-STS397"},{"key":"58","doi-asserted-by":"publisher","unstructured":"[58] Vershynin, R. (2011). Approximating the moments of marginals of high-dimensional distributions., The Annals of Probability<\/i> 39<\/b> 1591\u20131606.","DOI":"10.1214\/10-AOP589"},{"key":"60","doi-asserted-by":"publisher","unstructured":"[60] Vovk, V. (1998). A game of prediction with expert advice., Journal of Computer and System Sciences<\/i> 56<\/b> 153\u2013173.","DOI":"10.1006\/jcss.1997.1556"},{"key":"62","doi-asserted-by":"publisher","unstructured":"[62] White, H. (1982). Maximum likelihood estimation of misspecified models., Econometrica: Journal of the Econometric Society<\/i> 50<\/b> 1\u201325.","DOI":"10.2307\/1912526"},{"key":"63","unstructured":"[63] Zhang, Y. and Lin, X. (2015). DiSCO: Distributed optimization for self-concordant empirical loss. In, Proceedings of the 32nd International Conference on Machine Learning<\/i> 37<\/b> 362\u2013370."},{"key":"64","doi-asserted-by":"publisher","unstructured":"[64] Zhang, Y., Wainwright, M. J. and Jordan, M. I. (2017). Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators., Electronic Journal of Statistics<\/i> 11<\/b> 752\u2013799.","DOI":"10.1214\/17-EJS1233"},{"key":"10","unstructured":"[10] Borovkov, A. A. (1998)., Mathematical Statistics<\/i>. Gordon and Breach Science Publishers."},{"key":"15","unstructured":"[15] Christensen, R. (2006)., Log-linear Models and Logistic Regression<\/i>. Springer Science & Business Media."},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] Huber, P. J. (2011). Robust statistics. In, International Encyclopedia of Statistical Science<\/i> 1248\u20131251. Springer.","DOI":"10.1007\/978-3-642-04898-2_594"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] Ibragimov, I. A. and Hasminskii, R. Z. (2013)., Statistical Estimation: Asymptotic Theory<\/i>. Springer Science & Business Media.","DOI":"10.1214\/aos\/1176347736"},{"key":"26","unstructured":"[26] Klenke, A. (2013)., Probability Theory: A Comprehensive Course<\/i>. Springer Science & Business Media."},{"key":"30","unstructured":"[30] Lehmann, E. L. and Casella, G. (2006)., Theory of Point Estimation<\/i>. Springer Science & Business Media."},{"key":"32","unstructured":"[32] Loh, P.-L. and Wainwright, M. J. (2011). High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. In, Advances in Neural Information Processing Systems<\/i> 2726\u20132734."},{"key":"35","unstructured":"[35] Marteau-Ferey, U., Bach, F. and Rudi, A. (2019). Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses., arXiv:1907.01771<\/i>."},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] McCullagh, P. and Nelder, J. A. (1989)., Generalized Linear Models, Second Edition<\/i>. Chapman & Hall.","DOI":"10.1007\/978-1-4899-3242-6"},{"key":"40","doi-asserted-by":"publisher","unstructured":"[40] Mendelson, S. and Zhivotovskiy, N. (2018). Robust covariance estimation under $L_4-L_2$ norm equivalence., arXiv:1809.10462<\/i>.","DOI":"10.1214\/19-AOS1862"},{"key":"42","unstructured":"[42] Nesterov, Y. (2013)., Introductory Lectures on Convex Optimization: a Basic Course<\/i>. Springer Science & Business Media."},{"key":"43","doi-asserted-by":"crossref","unstructured":"[43] Nesterov, Y. and Nemirovski, A. S. (1994)., Interior-point Polynomial Algorithms in Convex Programming<\/i>. Society of Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611970791"},{"key":"44","unstructured":"[44] Ostrovskii, D. M. and Bach, F. (2018). Finite-sample Analysis of M-estimators using Self-concordance., arXiv:1810.06838<\/i>."},{"key":"46","doi-asserted-by":"crossref","unstructured":"[46] Pollard, D. (1990)., Empirical Processes: Theory and Applications<\/i>. NSF-CBMS regional conference series in probability and statistics<\/i>. Institute of Mathematical Statistics and the American Statistical Association.","DOI":"10.1214\/cbms\/1462061091"},{"key":"47","doi-asserted-by":"crossref","unstructured":"[47] Rockafellar, R. T. (1970)., Convex analysis<\/i>. Princeton University Press.","DOI":"10.1515\/9781400873173"},{"key":"48","doi-asserted-by":"publisher","unstructured":"[48] Rush, C. and Venkataramanan, R. (2018). Finite sample analysis of approximate message passing algorithms., IEEE Transactions on Information Theory<\/i>.","DOI":"10.1109\/TIT.2018.2816681"},{"key":"52","unstructured":"[52] Talagrand, M. (2006)., The Generic Chaining: Upper and Lower Bounds of Stochastic Processes<\/i>. Springer Science & Business Media."},{"key":"57","unstructured":"[57] van der Vaart, A. W. (1998)., Asymptotic Statistics<\/i>. Cambridge Series in Statistical and Probabilistic Mathematics<\/i>. Cambridge University Press."},{"key":"59","doi-asserted-by":"crossref","unstructured":"[59] Vershynin, R. (2012). Introduction to the non-asymptotic analysis of random matrices. In, Compressed Sensing: Theory and Applications<\/i> 210\u2013268. Cambridge University Press.","DOI":"10.1017\/CBO9780511794308.006"},{"key":"61","unstructured":"[61] Wei, X. and Minsker, S. (2017). Estimation of the covariance structure of heavy-tailed distributions. In, Advances in Neural Information Processing Systems<\/i> 2859\u20132868."},{"key":"65","unstructured":"[65] Zhou, C., Gao, W. and Goldfarb, D. (2017). Stochastic Adaptive Quasi-Newton Methods for Minimizing Expected Values. In, Proceedings of the 34th International Conference on Machine Learning<\/i> 4150\u20134159."},{"key":"66","unstructured":"[66] Zhou, S. (2009). Restricted eigenvalue conditions on subgaussian random matrices., arXiv:0912.4045<\/i>."}],"container-title":["Electronic Journal of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.ejs\/1609902192","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T15:09:42Z","timestamp":1791472182000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/electronic-journal-of-statistics\/volume-15\/issue-1\/Finite-sample-analysis-of-M-estimators-using-self-concordance\/10.1214\/20-EJS1780.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":66,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1,1]]}},"URL":"https:\/\/doi.org\/10.1214\/20-ejs1780","relation":{},"ISSN":["1935-7524","1935-7524"],"issn-type":[{"value":"1935-7524","type":"print"},{"value":"1935-7524","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,1]]}}}