- 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 -class problems is significantly more complex because the relative distances between classes form a matrix comprising 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
Thanks
Thank you for your reply. I keep my current score.
Thank you for taking time to review our manuscript. We answer your question below.
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.003 in Figure 1 and 0.00218 in Figure 2 (Appendices K.3–K.4). For Figure 2, different full-rank starting matrices gave thresholds agreeing within 3.74×10−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=3, γ=1, signal covariance S=10.90.91 , and an intercept estimated during fitting. For b=0 (zero true intercept), the numerical threshold is α⋆=2.6272221691, and we proved that α⋆∈[2.62544091,2.62971945], giving an error below 0.002498. For b=1.5 (true intercept (1.5,0)), the numerical threshold is α⋆=3.2128166086, and we obtained α⋆∈[3.20884070,3.21673716], giving an error below 0.003976. These verified primal and dual inequalities bound the global population threshold, even if the numerical optimizer converges to a local solution.
For b=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/α⋆=infH⪰0,tr(H)=1t(H) (equation (119)), where 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.380888404. For the lower bound, we choose a polar vector p∈CY∘ so that the intercept and signal terms cancel: E[p]=0 and E[pZ0⊤]=0. Define its second-moment matrix C=E[pp⊤]≻0 and Gaussian cross-moment matrix P=E[pZ1⊤], where Z0,Z1 are the Gaussian vectors in equation (118). Exact rational arithmetic verifies PP⊤⪰LC with L=0.380268702. This inequality, Gaussian rotational invariance, and matrix Cauchy–Schwarz imply t(H)≥L for every admissible matrix H, including singular matrices. Hence L≤t⋆≤U, which gives 1/U≤α⋆≤1/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.