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:
- 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.
- 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