p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets

Alexander Munteanu, Simon Omlor, Christian Peters

Binary classification is a cornerstone of statistical modeling, typically addressed through logistic or probit regression. However, these standard models rely on fixed link functions—the logistic and normal cumulative distribution functions (CDFs)—which assume specific tail behaviors. In real-world "Big Data" scenarios, these assumptions often fail: data may contain heavy-tailed outliers or be tightly bounded. Furthermore, the computational cost of Maximum Likelihood Estimation (MLE) scales linearly with the number of observations ($n$), creating a significant bottleneck for massive datasets.

In this paper, researchers from TU Dortmund University introduce $p$-generalized probit regression, a flexible extension that allows for tunable sensitivity to outliers. To address the computational challenge, they propose a scalable MLE framework using coresets—small, representative summaries of the data that provide high-accuracy approximations of the full dataset results.

The $p$-Generalized Probit Model

The core innovation lies in replacing the standard normal distribution used in probit regression with the $p$-generalized normal distribution. This family of distributions is parameterized by $p \in [1, \infty)$, allowing the model's link function to adapt to the data's specific characteristics:

  • $p=1$ (Laplace): Produces a robust model that is less sensitive to outliers.
  • $p=2$ (Gaussian): Recovers the standard probit regression model.
  • $p \to \infty$ (Uniform): Results in a model highly sensitive to extreme values.

By adjusting $p$, researchers can bridge the gap between robust and sensitive estimators. The authors demonstrate that the $p=1$ case often provides greater robustness than even standard logistic regression, particularly when dealing with distant outliers that might otherwise skew the decision boundary.

Scalable Estimation via Coresets

To make $p$-generalized probit regression viable for millions of observations, the authors employ a "sketch-and-solve" paradigm. The goal is to construct a coreset: a weighted subset of the original data that approximates the log-likelihood function of the full dataset within a factor of $(1 \pm \epsilon)$.

The construction involves several key steps:

  1. Sensitivity Sampling: Each data point is assigned a "sensitivity score" representing its influence on the model. Points with high sensitivity are more likely to be included in the coreset.
  2. Sketching for Efficiency: Calculating exact sensitivities is computationally expensive. The authors use sketching techniques (random projections) to approximate $\ell_p$ leverage scores. This allows the most influential points to be identified in just two passes over the data.
  3. Independence from $n$: Crucially, the size of the resulting coreset depends on the data's dimension ($d$) and the desired accuracy ($\epsilon$), but is independent of the total number of observations ($n$). This breaks the linear scaling bottleneck.

Empirical Results

The authors evaluated their approach on several large-scale benchmarks, including Webspam (350,000 observations), Covertype (581,012 observations), and Kddcup (494,021 observations).

The results highlight three main advantages:

  • Accuracy: The coreset-based MLE consistently achieved a median approximation ratio near 1.0, meaning the results derived from the tiny data summary were nearly identical to those from the full dataset.
  • Robustness: In synthetic 2D visualizations, the $p=1$ model successfully ignored outliers that pulled standard logit and $p=2$ models away from the primary data cluster.
  • Efficiency: The coreset construction proved significantly faster than other high-accuracy sampling methods (such as Lewis weights) and far more accurate than uniform sampling, which often fails as $p$ increases because it misses critical, high-influence points.

Theoretical Contributions and Limitations

Beyond the algorithmic framework, the paper provides refined bounds for the VC dimension of weighted loss functions in this context, improving upon existing results for logistic regression.

However, some limitations remain. The study is restricted to $p \ge 1$ to maintain the convexity of the optimization problem; while $p < 1$ could model even heavier tails, it introduces significant computational complexity. Additionally, the coreset size depends on a "complexity parameter" ($\mu$) related to how balanced the feature matrix is. Finally, the current model assumes a symmetric link function, leaving the exploration of skewed $p$-generalized distributions for future research.

Conclusion

The $p$-generalized probit regression model offers a powerful tool for practitioners needing to balance robustness and sensitivity in binary classification. By combining this statistical flexibility with efficient coreset construction, the authors provide a mathematically rigorous path toward analyzing massive datasets without sacrificing accuracy or computational feasibility.

Summary updated

Abstract

We study the $p$-generalized probit regression model, which is a generalized linear model for binary responses. It extends the standard probit model by replacing its link function, the standard normal cdf, by a $p$-generalized normal distribution for $p\in[1, \infty)$. The $p$-generalized normal distributions \citep{Sub23} are of special interest in statistical modeling because they fit much more flexibly to data. Their tail behavior can be controlled by choice of the parameter $p$, which influences the model's sensitivity to outliers. Special cases include the Laplace, the Gaussian, and the uniform distributions. We further show how the maximum likelihood estimator for $p$-generalized probit regression can be approximated efficiently up to a factor of $(1+\varepsilon)$ on large data by combining sketching techniques with importance subsampling to obtain a small data summary called coreset.
BibTeX
@inproceedings{munteanu2022p,
  author = {Alexander Munteanu and Simon Omlor and Christian Peters},
  title = {{p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=foWGWTWK7v7},
}
Figure