Finite-sample analysis of M-estimators using self-concordance

Dmitrii M. Ostrovskii, Francis BacharXiv 2018 · DOI · arXiv

Abstract

Classical asymptotic theory for parametric M-estimators guarantees that excess risk follows a chi-square type distribution in the limit of infinite samples. However, characterizing the behavior in finite-sample regimes, particularly under model misspecification, remains a challenge. This paper utilizes the property of self-concordance to determine the critical sample size required to enter the asymptotic regime. By imposing only local assumptions near the population risk minimizer, we derive bounds on the sample complexity that scale with the effective dimension. Our results cover both classical and pseudo self-concordant losses, such as logistic and pseudo-Huber losses, and extend to high-dimensional $\ell_1$-penalized estimators.

Introduction

M-estimation is a cornerstone of statistical inference, encompassing widely used methods like Maximum Likelihood Estimation (MLE) and Least Squares. While asymptotic theory provides a comforting "infinite data" guarantee—where the estimator's error behaves predictably according to a chi-square distribution—practical applications often operate with limited data. The fundamental question is: at what point does the "asymptotic" behavior actually begin?

Traditional finite-sample analyses often rely on global properties of the loss function, requiring it to be well-behaved across the entire parameter space. Such assumptions are frequently violated in practice. This work addresses this gap by leveraging self-concordance, a property that allows for a purely local analysis of the loss function's curvature, providing sharp bounds on the "critical sample size" needed for optimal convergence.

The Framework of Self-Concordance

The authors distinguish between two primary classes of loss functions:

  1. Canonical Self-Concordance: As defined by Nesterov and Nemirovski, where the third derivative of the loss is bounded by the $3/2$ power of the second derivative.
  2. Pseudo Self-Concordance: A variation introduced by Francis Bach, where the power is removed. This class is particularly relevant for generalized linear models (GLMs), including logistic regression.

The power of self-concordance lies in its affine invariance. Unlike Lipschitz-based methods, self-concordant analysis does not depend on the specific scaling or rotation of the coordinate system. This allows the authors to focus on the Dikin ellipsoid—a local neighborhood around the optimal parameter $\theta_*$ where the curvature of the population risk remains stable.

Local Assumptions and Effective Dimension

A key contribution of this research is the shift from global to local assumptions. The analysis primarily concerns the behavior of the "calibrated design"—the data features scaled by the square root of the loss function's Hessian—at the optimum $\theta_*$.

The paper introduces the effective dimension ($d_{\text{eff}}$), a metric that accounts for model misspecification. In a perfectly specified model, $d_{\text{eff}}$ aligns with the parameter dimension $d$. However, when the model is misspecified, $d_{\text{eff}}$ captures the additional complexity introduced by the mismatch between the model and the true data-generating process.

Main Results: Characterizing the Critical Sample Size

The authors establish two main bounds for the critical sample size $n$ required to achieve optimal error bounds:

  • Basic Bound: Under minimal local assumptions at $\theta_*$, the critical sample size scales as $O(d \cdot d_{\text{eff}})$.
  • Improved Bound: By extending the assumptions to the Dikin ellipsoid around $\theta_*$, the bound is sharpened to $O(\max\{d_{\text{eff}}, d \log d\})$.

These bounds represent the threshold at which the estimator transitions from a slow "pre-asymptotic" rate ($1/\sqrt{n}$) to the fast "asymptotic" rate ($1/n$). This transition is often referred to as the "elbow effect," which the authors validate through numerical experiments using Gaussian designs and logistic models. Interestingly, for logistic regression with Gaussian design, the subgaussian parameters and curvature measures remain near-constant over the Dikin ellipsoid, suggesting these conditions are naturally met in common scenarios.

High-Dimensional and Penalized Estimators

The analysis is further extended to high-dimensional settings where the number of parameters $d$ may exceed the sample size $n$, necessitating $\ell_1$-regularization (e.g., Lasso). The authors find that self-concordance still provides a path to understanding sample complexity, though the affine invariance is partially lost due to the $\ell_1$ norm. For these cases, the sample complexity scales with the sparsity $s$ of the model, specifically $n \gtrsim s^2 \log d$. While the $s^2$ term suggests a potential gap compared to the ideal $s$ scaling, it provides a rigorous foundation for M-estimation in sparse, high-dimensional regimes.

Conclusion

By bridging the gap between optimization theory and statistical inference, this work provides a robust framework for understanding the finite-sample behavior of M-estimators. The reliance on local self-concordance and the Dikin ellipsoid allows for more realistic assumptions than previous global theories, offering practitioners a clearer picture of when they can trust the asymptotic guarantees of their models. Future work may look to relax the subgaussian assumptions on data distributions to accommodate heavy-tailed data through techniques like median-of-means estimators.

Summary updated

Abstract

The classical asymptotic theory for parametric $M$-estimators guarantees\nthat, in the limit of infinite sample size, the excess risk has a chi-square\ntype distribution, even in the misspecified case. We demonstrate how\nself-concordance of the loss allows to characterize the critical sample size\nsufficient to guarantee a chi-square type in-probability bound for the excess\nrisk. Specifically, we consider two classes of losses: (i) self-concordant\nlosses in the classical sense of Nesterov and Nemirovski, i.e., whose third\nderivative is uniformly bounded with the $3/2$ power of the second derivative;\n(ii) pseudo self-concordant losses, for which the power is removed. These\nclasses contain losses corresponding to several generalized linear models,\nincluding the logistic loss and pseudo-Huber losses. Our basic result under\nminimal assumptions bounds the critical sample size by $O(d \\cdot\nd_{\\text{eff}}),$ where $d$ the parameter dimension and $d_{\\text{eff}}$ the\neffective dimension that accounts for model misspecification. In contrast to\nthe existing results, we only impose local assumptions that concern the\npopulation risk minimizer $\\theta_*$. Namely, we assume that the calibrated\ndesign, i.e., design scaled by the square root of the second derivative of the\nloss, is subgaussian at $\\theta_*$. Besides, for type-ii losses we require\nboundedness of a certain measure of curvature of the population risk at\n$\\theta_*$.Our improved result bounds the critical sample size from above as\n$O(\\max\\{d_{\\text{eff}}, d \\log d\\})$ under slightly stronger assumptions.\nNamely, the local assumptions must hold in the neighborhood of $\\theta_*$ given\nby the Dikin ellipsoid of the population risk. Interestingly, we find that, for\nlogistic regression with Gaussian design, there is no actual restriction of\nconditions: the subgaussian parameter and curvature measure remain\nnear-constant over the Dikin ellipsoid. Finally, we extend some of these\nresults to $\\ell_1$-penalized estimators in high dimensions.\n
BibTeX
@misc{ostrovskii2018finite,
  author = {Dmitrii M. Ostrovskii and Francis Bach},
  title = {{Finite-sample analysis of M-estimators using self-concordance}},
  year = {2018},
  eprint = {1810.06838},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.06838},
}
Figure