Research map / Learning theory and algorithms / Sample complexity
Pairwise Maximum Likelihood For Multi-Class Logistic Regression Model With Multiple Rare Classes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes pairwise (PMLE) and subsample-based pairwise (SPMLE) maximum likelihood estimators for multi-class logistic regression with one major class and multiple rare classes, proving they are asymptotically as efficient as the global MLE.
Problem
Estimating multi-class logistic regression when one major class dominates and several rare classes exist, where the global MLE is computationally expensive in high dimension and with many classes.
Approach
Asymptotic theory shows the MLE covariance is block-diagonal across rare classes, so each rare class can be estimated separately against the major class (pairwise two-class logistic regressions, run in parallel), and the major class can be further downsampled without losing asymptotic efficiency.
Key results
- On the TTS dataset, GMLE, PMLE and SPMLE reach ACC 0.836, 0.835 and 0.824, outperforming focal loss (0.794), CBL (0.789), CSL (0.747) and RDS (0.763).
- PMLE matches GMLE RMSE in simulations while cutting CPU time; on TTS, CPU time is 145.85 s for GMLE vs 42.12 s for PMLE and 12.12 s for SPMLE.
- Theory: the MLE covariance is block-diagonal across rare classes, so pairwise estimators are asymptotically efficient, and SPMLE keeps this efficiency when pi_N/exp(alpha_N) diverges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace joint multi-class maximum likelihood with separate major–rare pairwise likelihood estimation | Multi-class logistic regression · TikTok Screenshots test | ACC: 0.836 -> 0.835 | No clear effect |
| Replace joint multi-class maximum likelihood with separate major–rare pairwise likelihood estimation | Multi-class logistic regression · TikTok Screenshots test | CPU time: 145.85 seconds -> 42.12 seconds | Helped |
| Downsample the major class during pairwise estimation (ablation) | SPMLE · TikTok Screenshots test | ACC: 0.835 -> 0.824 | Hurt |
| Downsample the major class during pairwise estimation (ablation) | SPMLE · TikTok Screenshots test | AUC: 0.999 -> 0.999 | No clear effect |
| Downsample the major class during pairwise estimation (ablation) | SPMLE · TikTok Screenshots test | CPU time: 42.12 seconds -> 12.12 seconds | Helped |
| Downsample the major class during pairwise estimation (ablation) | SPMLE · p = 50, K = 20 simulation | RMSE: 0.061 -> 0.062; 0.050 -> 0.050; 0.039 -> 0.039 | No clear effect |
| Downsample the major class during pairwise estimation (ablation) | SPMLE · p = 50, K = 20 simulation | CPU time: 0.875 -> 0.281; 1.698 -> 0.489; 3.959 -> 0.895 | Helped |
| Use PMLE instead of the competing methods | TikTok Screenshots classification · TikTok Screenshots test | ACC: 0.835 vs 0.794; 0.789; 0.747; 0.763 | Helped |
Surprising findings
- The convergence rate is governed by the rare-class sample size rather than the total sample size, so the major class can be heavily downsampled.
Limitations
- Theory assumes rare-class sizes are of the same order; unequal-order rare classes are unexplored.
- Only the logistic regression model is studied.
- Real-data comparison uses a single private dataset and a single train/test split.
Experimental setup
Datasets: TikTok Screenshots (TTS) dataset ImageNet (VGG16 pre-training)
Benchmarks: TikTok Screenshots (TTS)
Metrics: RMSE CPU time ACC AUC
Baselines: GMLE (Newton-Raphson) GMLE (gradient descent) focal loss class-balanced loss cost sensitive loss random downsampling
Builds on: Wang (2020) two-class rare-event logistic regression Newton-Raphson gradient descent
Closest papers by meaning
- Multinomial Logistic Regression: Asymptotic Normality on Null Covariates in High-Dimensions (NeurIPS 2023 · similarity 0.85)
- Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models (NeurIPS 2019 · similarity 0.84)
- Hypothesis Testing for Class-Conditional Noise Using Local Maximum Likelihood (AAAI 2024 · similarity 0.84)
- A Provably Accurate Randomized Sampling Algorithm for Logistic Regression (AAAI 2024 · similarity 0.83)
- SimPro: A Simple Probabilistic Framework Towards Realistic Long-Tailed Semi-Supervised Learning (ICML 2024 · similarity 0.82)
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.