acceptodds
Under review as a conference paper at ICLR 2027

A Sharp Phase Transition for MLE Existence in Multinomial Logistic Regression

Abstract

This paper studies when multinomial logistic regression admits a finite maximum-likelihood estimator. Under a Gaussian feature model with softmax class probabilities and a fixed number of classes, we establish a sharp phase transition for MLE existence. As the sample size and feature dimension grow proportionally, the probability that the MLE is finite converges to zero or one depending on whether the sample-to-dimension ratio lies below or above a critical threshold. We characterize this threshold through a matrix Gaussian-distance optimization whose dimension depends only on the number of classes, rather than on the feature dimension. The result allows for general feature covariance and signal strength, and applies to models fitted both with and without an intercept. Although fitting an intercept adds only finitely many parameters, it can strictly increase the asymptotic existence threshold, even when the true intercept is zero. Our characterization recovers the binary logistic threshold and yields explicit thresholds when labels are uniform and independent of the features. Simulations support the predicted thresholds across signal strengths and true intercepts, and show that estimating an intercept can lead to a higher threshold.

Primary area:
learning theory
Keywords:
Multinomial logistic regression, phase transition

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_xAPYOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper provides a mathematically rigorous characterization of the phase transition regarding the existence of a finite maximum likelihood estimator for multiclass classification using the softmax function. In softmax regression, if the number of data points falls below a certain critical threshold, the likelihood function can be maximized by driving the classification parameters to infinity; consequently, no finite maximum likelihood estimator exists. However, increasing the amount of data allows for a finite estimator to be obtained. This distinction manifests as a phase transition when the input vector dimension and the number of data points both tend to infinity in a linear relationship. Candès and Sur (2020) rigorously established the mathematical framework for this phenomenon in the context of binary classification. The contribution of the present paper is the generalization of these results to multiclass softmax regression. Compared to the binary case, the analysis for KK-class problems is significantly more complex because the relative distances between classes form a matrix comprising K(K−1)/2K(K-1)/2 parameters; nevertheless, this paper rigorously identifies the phase transition point based on this parameterization and verifies its validity through numerical experiments.

Critical strengths

It effectively handles the problem, which has become complex due to the expansion to multiple classes. It also quantitatively clarifies the impact of the "intercept". The numerical verification of the results is thorough in limited cases.

Critical weaknesses

The extension from binary to multinomial logistic regression is mathematically nontrivial, as the separation constraints involve coupled class comparisons and require a matrix-valued characterization. This constitutes a substantial theoretical contribution. However, beyond the specially constructed example demonstrating the effect of fitting an intercept, the paper provides relatively limited insight into how the matrix structure of class correlations determines the critical threshold. A more systematic investigation of genuinely multiclass phenomena would strengthen the significance of the results.

Questions for authors

The theoretical threshold is characterized by a generally nonconvex matrix optimization problem. How confident can we be that the numerical thresholds reported in Figures 1 and 2 correspond to the global optimum? Is there any independent way to bound the possible optimization error?

2 comments

Thank you for taking time to review our manuscript. We answer your question below.

Q1: The theoretical threshold is characterized by a generally nonconvex matrix optimization problem. How confident can we be that the numerical thresholds reported in Figures 1 and 2 correspond to the global optimum? Is there any independent way to bound the possible optimization error?

A1. The thresholds are stable across the tested starting matrices and integration settings. For two Figure 2 parameter settings, we also obtain rigorous error bounds relative to the global population threshold. The largest reported changes from integration refinement, seed comparisons at the finer integration level, and evaluation on fresh integration points were below 0.0030.003 in Figure 1 and 0.002180.00218 in Figure 2 (Appendices K.3–K.4). For Figure 2, different full-rank starting matrices gave thresholds agreeing within 3.74×10−63.74\times10^{-6}. We also searched over lower-rank matrices for better solutions on the boundary of the positive-semidefinite cone. Figures 1 and 2 compare the computed thresholds with MLE-existence frequencies determined by a separate linear-programming test.

To assess the total numerical error relative to the population threshold, we also obtained rigorous bounds on the global optimum for two settings in Figure 2, both with K=3K=3, γ=1\gamma=1, signal covariance S=(10.90.91)S=\begin{pmatrix}1 & 0.9 \\\\ 0.9 & 1\end{pmatrix} , and an intercept estimated during fitting. For b=0b=0 (zero true intercept), the numerical threshold is α^⋆=2.6272221691\widehat\alpha_\star=2.6272221691, and we proved that α⋆∈[2.62544091,2.62971945]\alpha_\star\in[2.62544091,2.62971945], giving an error below 0.0024980.002498. For b=1.5b=1.5 (true intercept (1.5,0)(1.5,0)), the numerical threshold is α^⋆=3.2128166086\widehat\alpha_\star=3.2128166086, and we obtained α⋆∈[3.20884070,3.21673716]\alpha_\star\in[3.20884070,3.21673716], giving an error below 0.0039760.003976. These verified primal and dual inequalities bound the global population threshold, even if the numerical optimizer converges to a local solution.

For b=0b=0, we bound the reciprocal threshold from both sides: one feasible construction supplies an upper bound, and an inequality satisfied by every feasible construction supplies a lower bound. Write t⋆=1/α⋆=inf⁡H⪰0,tr⁡(H)=1t(H)t_\star=1/\alpha_\star=\inf_{H\succeq0,\operatorname{tr}(H)=1}t(H) (equation (119)), where t(H)t(H) is defined by the score and second-moment constraints in equation (118), Appendix K.2. To obtain the upper bound, we construct feasible class scores at a fixed admissible matrix using piecewise multilinear interpolation. Rigorous bounds on the Gaussian integrals and tails give t⋆≤U=0.380888404t_\star\le U=0.380888404. For the lower bound, we choose a polar vector p∈CY∘p\in\mathcal C_Y^\circ so that the intercept and signal terms cancel: E[p]=0\mathbb E[p]=0 and E[pZ0⊤]=0\mathbb E[pZ_0^\top]=0. Define its second-moment matrix C=E[pp⊤]≻0C=\mathbb E[pp^\top]\succ0 and Gaussian cross-moment matrix P=E[pZ1⊤]P=\mathbb E[pZ_1^\top], where Z0,Z1Z_0,Z_1 are the Gaussian vectors in equation (118). Exact rational arithmetic verifies PP⊤⪰LCPP^\top\succeq LC with L=0.380268702L=0.380268702. This inequality, Gaussian rotational invariance, and matrix Cauchy–Schwarz imply t(H)≥Lt(H)\ge L for every admissible matrix HH, including singular matrices. Hence L≤t⋆≤UL\le t_\star\le U, which gives 1/U≤α⋆≤1/L1/U\le\alpha_\star\le1/L. These bounds account for integration error, Gaussian tails, arithmetic rounding, and the global matrix optimization. The verified intervals cover the two Figure 2 settings above. We will add the detailed proofs, certified intervals, and reproducible code for both settings to Appendix K of the revised manuscript.

Reviewer_xAPYOpenReview ↗

Thanks

Thank you for your reply. I keep my current score.

Reviewer_p2EvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the exact conditions under which the maximum likelihood estimator exists at finite parameter values for multinomial logistic regression in the proportional asymptotic regime, where the sample size and feature dimension grow proportionally while the number of classes remains fixed. Assuming Gaussian covariates and a softmax generative model with a well-defined limiting signal covariance, the authors establish a sharp zero-one phase transition governed by a critical sample-to-dimension ratio. This boundary is characterized as a matrix Gaussian-distance optimization whose dimension depends solely on the number of classes, reducing an asymptotic problem over high-dimensional parameters to a fixed-dimensional variational problem that captures the joint geometry of coupled decision cones. The analysis addresses both fitted and unconstrained intercept conventions, demonstrating the surprising result that estimating an intercept can strictly inflate the sample threshold required for existence even when the true data-generating intercept is zero. Synthetic Gaussian experiments closely mirror the theoretical boundaries across various signal strengths, true intercepts, and intercept configurations, providing a complete characterization of unrestricted finite maximum likelihood estimator existence that generalizes earlier binary results.

Critical strengths

Following are the strengths:

  • The paper establishes a sharp phase transition for unrestricted finite maximum likelihood estimator existence in multinomial logistic regression, closing an open high-dimensional problem by addressing mutually coupled decision boundaries rather than relying on bounded-norm constraints.
  • The finding that estimating an intercept can strictly inflate the existence threshold even when the true intercept is zero is theoretically surprising and rigorously justified through effective binary grouping dynamics, demonstrating that multiclass geometry alters asymptotic behavior beyond leading-order parameter counts.
  • The empirical validation goes beyond basic optimizer convergence by employing formal separation and polar certificates, paired sampling, and extensive reproducibility protocols to confirm the predicted critical boundaries.
Critical weaknesses

Following are the weaknesses:

  • The central guarantees rely heavily on Gaussian covariates, leaving open whether the sharp threshold exhibits universality under heavy-tailed, discrete, or dependent feature designs where rotational invariance and approximate message passing constructions fail.
  • While the threshold optimization is free of the ambient feature dimension, evaluating the objective requires solving a nonconvex matrix optimization with polyhedral distance integrals, which lacks global optimality certificates and becomes computationally demanding as the number of classes grows.
  • The theory addresses parameter finiteness without characterizing estimation error, leaving the statistical stability, coefficient divergence, and generalization performance of the estimator immediately above the critical threshold unquantified.
  • The strict inflation of the threshold from intercept estimation is proven only for a specialized, highly correlated three-class configuration, while the corresponding experiments evaluate a singular rank-one surrogate rather than the positive-definite perturbations covered by the proposition.
Questions for authors

Following are the questions:

  • Given the nonconvex nature of the outer matrix optimization and the need for numerical integration, how sensitive are the computed thresholds to initialization and solver tolerances, and can certified numerical bounds be established?
  • Does the sharp existence threshold depend exclusively on first and second covariate moments, or do higher-order moments fundamentally alter the transition point under non-Gaussian feature distributions?
  • Does the norm of the maximum likelihood estimator diverge as the sample-to-dimension ratio approaches the critical threshold from above, and can your framework quantify the divergence rate or its impact on out-of-sample prediction?
  • How do the matrix second-moment constraints and distance bounds scale if the number of classes grows jointly with the feature dimension, and does the underlying proof architecture remain viable in that regime?
3 comments

Thank you for taking time to review our manuscript. In the following, we address your questions one by one.

Q1: Given the nonconvex nature of the outer matrix optimization and the need for numerical integration, how sensitive are the computed thresholds to initialization and solver tolerances, and can certified numerical bounds be established?

A1. The computed thresholds show little sensitivity in the tested cases. Different full-rank initializations in Figure 2 agree within 3.74×10−63.74\times10^{-6} (Appendix K.4). With integration points and starting values fixed, tightening function and gradient stopping tolerances by factors of 1010 and 100100 changes α\alpha by at most 2.60×10−52.60\times10^{-5} in two fixed-HH problems and one outer restart. We also establish certified population error bounds for two Figure 2 settings. See our response to Q1 of reviewer xAPY for the intervals and their derivation, accounting for integration error and global optimization.

Q2: Does the sharp existence threshold depend exclusively on first and second covariate moments, or do higher-order moments fundamentally alter the transition point under non-Gaussian feature distributions?

A2. No. Matching the first two moments is insufficient. For K=2K=2, take uniform binary YY independent of X=BG/εX=BG/\sqrt{\varepsilon}, with independent B∼Bernoulli(ε)B\sim\mathrm{Bernoulli}(\varepsilon) and G∼N(0,Id)G\sim N(0,I_d), and fixed 0<ε<10<\varepsilon<1. Then XX is sub-Gaussian, E[X]=0\mathbb E[X]=0, and Cov⁡(X)=Id\operatorname{Cov}(X)=I_d. Without a fitted intercept, zero rows contribute constant loss. The NN nonzero rows are Gaussian with N/n→εN/n\to\varepsilon, so their threshold N/d=2N/d=2 becomes n/d=2/εn/d=2/\varepsilon, rather than 22 for Gaussian features with the same first two moments. With a fitted intercept, zero rows contain both labels with high probability, forcing any separating intercept direction to vanish; the threshold is again 2/ε2/\varepsilon.

Q3: Does the norm of the maximum likelihood estimator diverge as the sample-to-dimension ratio approaches the critical threshold from above, and can your framework quantify the divergence rate or its impact on out-of-sample prediction?

A3. Our existence theorem characterizes the critical threshold but does not establish whether the multinomial MLE norm diverges as α↓α⋆\alpha\downarrow\alpha_\star, nor does it quantify the divergence rate or its effect on out-of-sample prediction. In the binary setting, Sur, Chen and Candès (2019, Theorem 5 and Eqs. (25)–(26)) provide a characterization that implies divergence of the limiting MLE norm as n/d↓2n/d\downarrow2 for the null isotropic model without an intercept, where the high-dimensional limit is taken before approaching the threshold. Extending such results to multinomial logistic regression, including the divergence rate and implications for prediction risk, is an interesting direction for future research.

Q4: How do the matrix second-moment constraints and distance bounds scale if the number of classes grows jointly with the feature dimension, and does the underlying proof architecture remain viable in that regime?

A4. Our proof requires fixed KK. The bounds depend on the spectrum of HH and conditional class probabilities. For tr⁡(H)=1\operatorname{tr}(H)=1, the upper bound on the total second moment ranges from 1/[α(K−1)]1/[\alpha(K-1)] (equal eigenvalues) to 1/α1/\alpha (rank-one HH). The Euclidean distance lower-bound coefficient is 1/[K(K−1)]1/[K(K-1)] for uniform conditional class probabilities and can be smaller otherwise. These bounds alone do not determine the growing-KK threshold.

A growing-KK proof needs uniform bounds for the AMP approximation and the subsequent correction of separation inequalities. After TT AMP iterations, the discarded projections involve up to T(K−1)T(K-1) directions. Appendix H.1 shows that the normalized errors from discarding these projections vanish for fixed KK. It does not provide bounds that control these errors uniformly as KK grows. The correction step also uses conditioning constants that depend on KK.

For uniform labels independent of Gaussian features, α⋆,K∼K/(2log⁡K)\alpha_{\star,K}\sim K/(2\log K). Appendix I.4 gives α⋆,K=(K−1)/δ(DK)\alpha_{\star,K}=(K-1)/\delta(\mathcal D_K), where DK\mathcal D_K is the polar decision cone in regular-simplex coordinates and δ(DK)\delta(\mathcal D_K) is its statistical dimension (the expected squared norm of a standard Gaussian projected onto the cone). The scalar formula δ(DK)=Emin⁡a[(G0−a)2+∑j=1K−1(Gj−a)+2]\delta(\mathcal D_K)=\mathbb E\min_a[(G_0-a)^2+\sum_{j=1}^{K-1}(G_j-a)_+^2] uses independent standard Gaussians GjG_j. The minimizing level is asymptotic to 2log⁡K\sqrt{2\log K} in probability. Gaussian tail bounds give δ(DK)∼2log⁡K\delta(\mathcal D_K)\sim2\log K, yielding the threshold scaling. This result characterizes the population threshold in the uniform null model; a general theorem allowing KK to grow jointly with the feature dimension remains open.

Thank you for the explanation. The remaining concerns include limited theoretical generalizability beyond Gaussian covariates and fixed class counts, incomplete global optimality and scalability guarantees for numerical optimization, and insufficient characterization of MLE behavior near the threshold and the broader applicability of intercept-induced threshold inflation. Thus, I keep my score.

Thank you for reviewing our response and clarifying your remaining concerns. Our main contribution is a sharp phase transition for finite MLE existence in multinomial logistic regression with Gaussian covariates and any fixed number of classes, both with and without a fitted intercept. We establish the exact critical sample-to-dimension ratio separating asymptotic nonexistence and existence of the finite MLE.

Regarding theoretical generalizability, extensions to non-Gaussian covariates, growing number of classes, and MLE behavior near the threshold are important but distinct research questions. The binary literature developed these directions separately: Candès and Sur (2020) established the Gaussian existence threshold; Tang and Ye (2020) extended existence theory to elliptical covariates; and Sur, Chen, and Candès (2019, Theorem 5) studied the MLE norm in the binary null model. Our work establishes the corresponding sharp existence theory in the more complex multinomial setting, providing a foundation for further extensions.

Regarding numerical optimization, our main theorem provides an exact population optimization characterization of the threshold, independent of numerical optimization. Our primary contribution is to rigorously characterize the phase transition through this optimization problem, rather than to develop globally certified numerical solvers. Nevertheless, as detailed in our response to reviewer xAPY, we provide certified absolute error bounds of 0.002498 and 0.003976 for two Figure 2 settings, accounting for both numerical integration and global optimization errors.

Regarding intercept-induced threshold inflation, our result establishes that fitting an intercept can never decrease the threshold. More importantly, we prove that the increase is strict for a family of three-class models with positive-definite signal covariance and zero true intercept. This contrasts with binary Gaussian logistic regression, where the thresholds coincide when the true intercept is zero Candès and Sur (2020, Theorem 2). Thus, our result identifies a phenomenon specific to multinomial logistic regression, rather than merely extending a known binary result. Characterizing all settings in which the increase is strict is an interesting further question, but does not diminish the generality of the nondecreasing result or the significance of the strict-increase examples.

We agree that the suggested extensions are valuable. However, they concern important directions beyond the scope of our main results, rather than gaps in the established sharp phase transition theory. We hope the reviewer will assess our contribution in light of the exact phase transition theorem, its nontrivial extension from binary to multinomial logistic regression, and the new phenomenon of intercept-induced threshold inflation.

Reviewer_RR7jOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper theoretically provides phase transition of MLE existence for multinomial logistic regression in a scenario of Gaussian feature vectors. As is the case with binary logistic regression [Candes+20], a critical threshold for a sample-to-dimension ratio, n/dn/d, is proven to exist for sharply changing the phase. Besides, the proposed threshold is so general as to contain the other types of threshold formula in [Candes+20, Cover65] as special cases. Effectiveness of the proposed thresholds is validated through several simulation experiments.

Critical strengths
  • The phase transition threshold for sample complexity n/dn/d is proposed with sufficient theoretical foundation which seems solid to me, though I did not thoroughly check the detailed proof in a supplementary.
  • The threshold is also analyzed in terms of intercept in the linear regression model and its connections to the prior works [Candes+20, Cover65] are showcased for the cases of binary classification and null modeling. It enhances generality of the theoretical approach provided in this paper.
  • Numerical experimental results on synthetic data support the validity of the theoretical thresholds.
Critical weaknesses
  • There are some other works that focus on linear separability of multi-class classification, such as [Kini+21, Loureiro+21], as slightly mentioned in Sec.1. Theoretical connection to those prior works is less discussed in this paper. To well position this work in the literature, it is required to discuss such as limitations of the theoretical analysis in comparison to the related approaches.

  • While theoretical stuffs are well presented, the paper lacks reference to practical (real-world) data. For example, it is helpful to discuss the practical validity of Gaussian feature distribution and class distribution following the softmax law which are fundamental assumption in this work; it could be compared to the GMM assumptions in [Kini+21, Loureiro+21].

Questions for authors
  • Please provide comparison analyzes and/or discussions mentioned in Weakness section.
2 comments

Thank you for taking time to review our manuscript. We address both weaknesses below.

Weakness 1: There are some other works that focus on linear separability of multi-class classification, such as [Kini+21, Loureiro+21], as slightly mentioned in Sec.1. Theoretical connection to those prior works is less discussed in this paper. To well position this work in the literature, it is required to discuss such as limitations of the theoretical analysis in comparison to the related approaches.

Response. Thanks for pointing this out. We will add the following comparisons after line 85 in Section 1.

Loureiro et al. (2021) study multinomial logistic MLE-existence transitions under a Gaussian mixture model (GMM), X∣Y=j∼N(μj,Vj)X\mid Y=j\sim N(\mu_j,V_j). We assume X∼N(0,Σ)X\sim N(0,\Sigma) with softmax probabilities πj(x)=Pr⁡(Y=j∣X=x)\pi_j(x)=\Pr(Y=j\mid X=x) using affine class scores. Bayes' rule gives p(x∣Y=j)=ϕΣ(x)πj(x)/E[πj(X)]p(x\mid Y=j)=\phi_\Sigma(x)\pi_j(x)/\mathbb E[\pi_j(X)], where ϕΣ\phi_\Sigma is the Gaussian feature density; this conditional density is generally non-Gaussian. Conversely, a common-covariance GMM has affine softmax posteriors but a generally non-Gaussian marginal. Thus, neither joint model contains the other, and GMM thresholds do not directly supply ours. We establish a sharp finite-MLE threshold for the Gaussian–softmax model, allowing singular limiting signal covariance without an a priori MLE norm bound. We show that estimating an intercept can strictly increase the finite-MLE threshold, even when the true intercept is zero. Our results do not cover general losses, regularization, or prediction performance studied by [Loureiro+21].

Kini and Thrampoulidis (2021) study one-vs-one and one-vs-all separation under a GMM. If the design matrix of the fitted model has full column rank, finite-MLE nonexistence is equivalent to a nonzero common score direction fj(x)=bj⊤x+ajf_j(x)=b_j^\top x+a_j, with f0≡0f_0\equiv0, satisfying fYi(xi)≥fk(xi)f_{Y_i}(x_i)\ge f_k(x_i) for every ii and k≠Yik\ne Y_i (Proposition 2.2 and Corollary 2.4 of our paper). Equalities are allowed. Full column rank ensures at least one strict comparison. A strict one-vs-one separator gjk(x)=wjk⊤x+cjkg_{jk}(x)=w_{jk}^\top x+c_{jk} is positive on observed samples from class jj and negative on those from class kk. Writing gjk=fj−fkg_{jk}=f_j-f_k requires gjk(x)+gkℓ(x)=gjℓ(x)g_{jk}(x)+g_{k\ell}(x)=g_{j\ell}(x) for every xx and j<k<ℓj<k<\ell. One-vs-one separators need not satisfy these identities. Strict one-vs-all separation is sufficient but not necessary for MLE nonexistence. Its separators, used as common scores, rank the observed class strictly highest. Weak joint separation can hold when one-vs-all separation fails. The one-vs-one and one-vs-all separability thresholds do not directly give our MLE threshold.

Weakness 2: While theoretical stuffs are well presented, the paper lacks reference to practical (real-world) data. For example, it is helpful to discuss the practical validity of Gaussian feature distribution and class distribution following the softmax law which are fundamental assumption in this work; it could be compared to the GMM assumptions in [Kini+21, Loureiro+21].

Response. Thank you for this suggestion. We will add the following discussion of practical relevance at the end of Section 1, after line 85 and the expanded related-work comparison.

Gaussian features provide a tractable setting for characterizing the MLE-existence threshold. The softmax model has practical foundations: McFadden (1974) derived multinomial logit probabilities from affine utilities with independent Gumbel errors, with applications to real-world travel choices. Marginal Gaussian and class-conditional Gaussian assumptions are useful and complementary. Both are widely used in the high-dimensional logistic regression literature, with theoretical predictions also examined on real-world data. Zhao, Sur and Candès (2022) examine light-tailed non-Gaussian covariates and study MLE bias and variance inflation using wine-quality data. Tan and Bellec (2023) investigate multinomial inference using heart-disease data with an additional independent Gaussian null feature. Loureiro et al. (2021) compare theoretical predictions under GMM assumptions with regularized logistic regression learning curves on MNIST and Fashion-MNIST. These studies illustrate the practical relevance of Gaussian-based theoretical models. Moreover, the separation criterion for MLE existence applies to any full-column-rank design matrix, without requiring Gaussian features or softmax labels.

Thank you for the response. As my concerns are mostly alleviated, I keep my rating as weak accept.

Comments on the paper

1 comment

Dear Reviewers,

The rebuttal period ends in less than two days. If you have not already done so, I kindly ask you to acknowledge the authors’ responses, and indicate whether your main concerns have been adequately addressed or further clarification is needed.

Thank you.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.