Phase transitions for the existence of unregularized M-estimators in single index models
Authors: Takuya Koriyama
Pierre C Bellec
Venue: ICML 2025 poster (2025)
Keywords: proportional asymptotics
CGMT
conic geometry
convex analysis in Hilbert space
Primary area: theory->everything_else
TL;DR: This paper studies phase transitions for the existence of unregularized M-estimators in single-index models under proportional asymptotic regime.

Abstract: This paper studies phase transitions for the existence of unregularized M-estimators under proportional asymptotics where the sample size $n$ and feature dimension $p$ grow proportionally with $n/p \to \delta \in (1, \infty)$. We study the existence of M-estimators in single-index models where the response $y_i$ depends on covariates $x_i \sim N(0, I_p)$ through an unknown index ${w} \in \mathbb{R}^p$ and an unknown link function. An explicit expression is derived for the critical threshold $\delta_\infty$ that determines the phase transition for the existence of the M-estimator, generalizing the results of Candés & Sur (2020) for binary logistic regression to other single-index models.
Furthermore, we investigate the existence of a solution to the nonlinear system of equations governing the asymptotic behavior of the M-estimator when it exists. The existence of solution to this system for $\delta > \delta_\infty$ remains largely unproven outside the global null in binary logistic regression. We address this gap with a proof that the system admits a solution if and only if $\delta > \delta_\infty$, providing a comprehensive theoretical foundation for proportional asymptotic results that require as a prerequisite the existence of a solution to the system.

Phase transitions for the existence of unregularized M-estimators in single index models
Takuya Koriyama
Pierre C. Bellec
Abstract
where F x R + [0,1] is unknown deterministic
function and u E R is an unknown index with ||w||
This paper studies phase transitions for the exis- tence of unregularized M-estimators under pro- portional asymptoties where the sample size and feature dimension grow proportionally with n/p + 8 E (1, xc). We study the existence of M-estimators single-index models where the response yi depends on covariates E ~ (0, Ip) through an unknown index u E IPP and an un- known link function. An explicit expression derived for the critical threshold d that deter- mines the phase transition for the existence of the M-estimator, generalizing the results of Candès & Sur (2020) for binary logistic regression to other single-index models. Furthermore, we investigate the existence of a solution to the nonlinear system of equations governing the asymptotic behavior of the M-estimator when it exists. The existence of solution to this system for 8 > dec remains largely unproven outside the global null in binary logistic regression. We address this gap with a proof that the system admits a solution if and only if > 8, providing a comprehensive theoreti- cal foundation for proportional asymptotic results that require prerequisite the existence of solution to the system.
1. This includes generalized linear models, such as the Poisson model (in which y = {0, 2,2..
........) }) or Binary logistic model (in which y = {-1, 13 for instance).
An unregularized M-estimator fit observed data (ys, mi)se(s) by the minimization problem
inf BERP
lyp
(2.
(1)
where (-) is convex for every y E V. If the infimum is achieved, we say the M-estimator exists and denote it by i.e. b E argmin Σ
24 (x. b).
In this paper we focus on high dimensional regime where the sample size and feature gnow proportionally
n
+ + (1, t00)
Here the constant quantifies sample size per dimensions. In this proportional asymptotic regime, under logistic re- gression model with binary response y {-1, 1} and with (t) = log(1 + exp(-yt)) the logistic loss, the seminal work Candès & Sur (2020) establishes that the existence of the M-estimator undergoes sharp phase transition at critical threshold 8
1. Introduction
if 8 then the M-estimator exists with high- probability (i.e., the infimum in (1) is attained), while
Let (æ,, V: J:)se(n] be sample of i.i.d. observations where 2; E RR and follows the normal distribution ~ N (0, We consider responses E Y' where y C RR and assume a single-index model the form
if 5 < & then the M-estimator does not exist (i.e., the infimum is not attained) with high-probability.
If 8 > 8.c. the behavior of the unregularized M-estimator b. including the limit in probability of T w and the limit in probability of [4, ww >6112. is characterized (Sur & Candès, 2019) by the nonlinear system with three unknowns (1, ()) To x IR IR
Ply { x.) = F w)
Vt E R
University of Chicago, Booth School of Business 'Department of Statisties, Rutgers University. Correspondence to: Takuya Koriyama <tkoriyam @uchicago.edu>.
28 0² EfCy (pro + +
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
0 EEU' (prox//xxxx) oG))], (2)
a 1-1) EIG prox/>ev](aU +oG)),

---

Phase transitions for the existence of unregularized M- M-estimators in single index models
Biruary logiaai
Logalic with repeated moisureneents
Posson
y--1
20
15
y*3
yM
10
22
15
90
-100
-7.5
-60
62
7.5
10.0
-10.0
-7.
5.0
7.5
-3
(a) Logistic loss
(b) Binomial loss
(c) Poisson
Figure 1. Three examples of loss functions.
where G ~ N(0, 1) is independent of (U, Y), and (U,Y) has the same distribution as (a. w, Wt). In particular U ~ NO, 1). The phase transition result of Candès Sur (2020) for Gaussian design and binary logistic regression has been extended by Tang Ye (2020) to elliptic covariate distributions and general binary response models. Han & Ren (2022) extended the phase transition of the logistic gression model with Gaussian covariates to the constrained minimization setting where the infimum in (I) is restricted to a closed convex cone. More broadly, the phase transition phenomena studied our paper are connected to earlier works in statistical physics (CCover, 1965; Gardner Der- rida, 1988; Krauth & Mézard, 1989)). Especially, (Cover, 1965) analyzed the geometry of linear inequalities and de- rived 8 under the null, i.e., when is independent of y;- More recently, similar phase transition behavior has been investigated in (Mignacco et al., 2020) for Gaussian mixtures models and in (Gerace et al., 2020) for random feature models.
To prove that the system (2) admits a unique solution if and only if 6 >> 600-
2. Main Result
Let us introduce the three examples of interest that our assumptions will cover. Example 2.1 (Binary logistic regression). Here, labels in y [-1,1] and the loss function
(t) = log(1 + exp(-yt)).
Example 2.2 (Logistic regression with repeated measure- ments). Let 2. Here, y {0, 1......) q} and the loss function, corresponding to binomial regression model with throws and a sigmoid link function for the probability, is
(t log(1 + exp(t)) yt.
If = 1, this is equivalent to binary logistic regression by renaming {1, 0] to 11.
Results such as Sur & Candès (2019); Salehi al. (2019) studying the behavior of the M-estimator on the side of the phase transition where it exists with high-probability assume that the nonlinear system (2) admits a unique solu- tion. Under the global null in binary logistic regression, Sur et al. (2019) establishes that de = and that the system (2) admits unique solution if and only 8 > Beyond the global null, it was observed (Sur & Candès, 2019) that the system (2) can be solved numerically if 8 >> dxc (where 6. is characterized in Candès & Sur (2020)), and that if the solution exists, it is unique (see Remark 2 of the supplement of Sur & Candès (2019)). However to our knowledge there is no proof yet that the system admits a solution for 8 > & except under the global null (see discussion after eq. (16) of the supplement of Sur& & Candès (2019)).
Example 2.3 (Poisson regression). If the labels are in y = {0, 1,, = N, the non-negative likelihood of Poisson generalized linear model leads to the loss function
(t) = exp(t) yt.
The phenomenon of the phase transition for the existence of the M-estimator comes from the lack of coercivity of some of the loss functions Ey. appearing in the optimization problem (1). For instance,
In the binary logistic regression case (Example 2.1), the loss Ly, is not coercive for all yı: it is increasing for y - and decreasing for = 1.
The goal of the present paper is twofold:
For binomial logistic regression with 2 2 mea- surements, (Example 2.2), the loss Ey. is coercive y4 E {1..... - 1}, increasing for y, = 0 and decreas- ing for ys = q.
To characterize the critical threshold 8 for Gaussian covariates beyond binary response models, for instance the Poisson model.
2

---

Phase transitions for the existence of unregularized M-estimators in single index models
For Poisson regression, (Example 2.3), the loss by is coercive for yi 2 1 and increasing for yi O.
attained. Similarly, if the second line in Assumption 2.4 is zero, then + Σi= (aU;) is decreasing and the infimum is never attained.
The values of y; leading to a coercive, increasing or de- creasing loss by,() (-) and the distribution of (ax w, y/) will determine the critical threshold . In order to study 8ec. it will be thus useful to introduce the following notation: For random variable Y valued in V, we define the events Dy (Y), 22 (20) by
In conclusion, Assumption 2.4 merely assumes that for = 1, the infimum is achieved, i.e., the M-estimator ex- ists, with positive probability. If the M-estimator does not exist for p = then it will not exist for p > >1 either, so Assumption 2.4 is required to avoid this trivial case that the M-estimator does not exist for all p 1. The remaining of our working assumptions are given below.
Pv(Y) = (.) is coercive),
Assumption 2.5. The loss by satisfies the following:
0)(()= = [fy is strictly increasing),
(Y) = fly is strictly decreasing).
1. For all y E EY. R i C², strictly convex, and not constant.
These events can be made explicit for the three examples thanks to the discussion in the three bullet points above:
2. El inf (u)ll < +oo and Elléy < +o0 where G N(0, 1) independent Y.
In the binary logistic regression case (Example 2.1) we have )Y) = (Y- - and (Y) = {Y -1.
((( <.
4. There exists a positive constant and (Y)) meeasurbble positive random variable D(Y) satisfying [ED(Y)) < too and (X))() < too such that
In Example 2.2, (Y) = (Y = 0} as well as (x = (Y = q} and (Y) = {0 < < g)
For Poisson regression (Example 2.3) we have (Y) = (Y = 0} and (Y) = (Y 2 1}.
under ? >
V R, (y(u) D(Y) +
|ul under G2
We will assume that by is strictly convex in our working assumptions, so that if ly is not cocrcive it must be either strictly increasing or strictly decreasing. We first state an assumption that prevents the problem from being trivial.
under 2
Beyond Assumption 2.4, Assumption 2.5 requires differen- tiability of the loss (item 1), mild integrability conditions (item 2), that by, is not always coercive (item 3) and that in the directions where by diverges to + it does so at least as fast as an affine function with slope 1/b and squared integrable intercept D(Y) (item 4).
Assumption 2.4. The loss fy is strictly convex for every y E y, and the law of Y satisfies
E
U2 1=0,
01) > 0,
We define the critical threshold 8e E (0, +00| by
E
(T(() + 1 <0 + U 01) >
inf ((),
(4)
where we omit the argument Y in the three events Py ( and f2 (Y) for brevity.
8
EER
where cp R- Rxo is the convex function defined as
This prevents the problem from being trivial in the following sense. Consider 1, and write 2; = U; (which is now scalar valued). Assume that the first line in Assumption 2.4 is O. The minimization problem (5) becomes
ppt) = E E[(G++U) (G++U) 2 [[0.]]
+ + (G+ Ut) + 1(2
+B =B[(G+U1) 110.).
inf a
Cy (aU.).
Here, the positive part of any real is denoted a4 max(0, a) and the negative part a = max( 0) and the square is always taken after the positive/negative parts, i.e., d² = (a+)² and a² = (a_)². If inf (pt)= = 0 then 80o is interpreted as 6. = + Above, the infimum over E IR always admits a minimizer t, E R under Assump- tion 2.4 (see Lemma A.
Since 2(U > 0) by U ~ N(0. 1), this implies P(N (Y)) 0, so for each of the terms, the loss lg (.) is not coercive. In fact, each term is increasing in a, because U. > 0 = f2 (y:) and U. < L (v:) by the first line in Assumption 2.4, so in this case a + Σn= Cye (aU,) is increasing with probability one and the infimum is never
3

---

Phase transitions for the existence of unregularized M-estimators in single index models
If 830, the system (2) has unique solution.
Theory
0.81
M-estimator does not exists
To our knowledge, proof of this relationship between the critical threshold de and the existence of solution the system (2) is new, even in the case of binary logistic regres- sion. The global null case was handled in (Sur et al., 2019); however, outside the global null case, this phenomenon was observed numerically in (Sur & Candès, 2019) without proof see the discussion after eq. (16) of the supplement of (Sur & Candès, 2019).
0.82
dinersennisappe riz-sizze
0.80
Montanari et al. (2023) generalized the threshold 8 of Candès & Sur (2020) for linear separation in binary classi- fication (or equivalently for the existence of (12) with the logistic loss), allowing an arbitrary single-indes liggle-idex model for P(ys = 1 æt). Montanari et al. (2023) further established the existence of a unique solution to a system governing the behavior of max-margin classifiers for any < 8 that is, for any such that the data is linearly separable with bigh-probability. We emphasize that the system studied in Montanari et al. (2023) is different and complementary from the system (2) of interest in the present paper: The system of Montanari et al. (2023) governs the behavior of max- max-mat margin classifiers for 5 < & while the system (2) studied here governs the behavior of the M-estimator (1) for which Theorem 2.7 establishes existence of solutions if and only if 5 800.
0.74
M-estimator exists
0.0
0.5
1.0
1.5
2.0
2.5 3.0
signal strength
Figure Count instances where the minimizer (1) exists for varying p/n and signal strength. Simulation parameter: n. = 1500, 20 repetitions, fy (u) = =-- -yy is the Poisson loss, V/ æ; satisfics the Poisson model (8).
Our first result is that the threshold 8 characterizes the phase transition regarding whether the M-estimator exists or not with high-proban -oobabbbbbbllity under the proportional regime
n/p + 8.
Theorem 2.6. A,, + too with n/p + 8, we have
The tools we use to obtain Theorem 2.7 are based on the existence of solution to a convex minimization problem in an infiniteddimensional Hilbert space which is the focus of the next section.
The M- M-estimator exists, ie. the inf (1) is attained)
{
if 8 8oa,
if < 800.
Theorem 2.6 is numerically verified by Figure 2 for Pois- son regression (see Section 4 for details). The proof of Theorem 2.6 is based on a common argument based on conic geometry and the Gaussian kinematic formula given by Amelunxen al. (2014). This use of the kinematic for- mula of Amelunxen et al. (2014) is similar to the argument in Candès & Sur (2020) for the binary logistic regression model.
3. Infinite Dimensional Optimization Problem
In this section, define the mathematical objects at the heart of the proof of Theorem 2.7 and outline the proof strat- egy. The key is the analysis of an vex optimization problem that is in a dual relationship with the nonlinear system. The use of such optimization problems to prove the existence of solutions to nonlinear systems of equations was pioneered in Montanari et al. (2023) and later used in the context of boosting and LI interpolation (Liang & Sur, 2022), to analyse the Lasso (Ce- lentano et al., 2023), and for robust regularized regression (Bellec & Koriyama, 2023).
con-
more technical question, that requires an investigation be- yond the application of the kinematic formula of Amelunxen et al. (2014), whether the critical threshold also character- izes the phase transition regarding the existence of solution to the nonlinear system (4). A formal proof of existence of a unique solution to (4) is important, as it is required to leverage the Convex Gaussian Minmax Theorem (CGMT) of Thrampoulidis et al. (2018). For instance, the works Salehi et al. (2019); Loureiro et al. (2021) which apply the CGMT in generalized linear models to study b, assume in their theorems that the system (2) admits unique solution. Theorem 2.7.
The notation and setup of this infiniteddimensional convex optimization problem is heavily inspired by Bellec & Ko- riyama (2023), which studies the existence of solutions to systems of similar nature (2) in robust regression. In the robust regression setup of Bellec & Koriyama (2023) where coercive and Lipschitz loss functions ly. (-) are considered, the corresponding system has always a unique solution and the M-estimator always exists: there is no phase transition. A novelty of the present paper is to explain how these tools,
*188 s 8ec, the system (2) has no solution.
4

---

Phase transitions for the existence of unregularized M-estimators in single index models
in particular the infinite-dimensione optimization below, can be used predict the phase transition for the existence of minimizer in (I) and the phase transition for the exis-
that the KKT condition
-u.00(uv) a,,,,,,
v.), +
tence of solutions to the system (2).
Oa v) 30
(6)
M.g(v.) =
To begin with, let us consider the almost sure equivalent classes H. of squared integrable measurable functions of U,)
g(v.) < 0
is satisfied, where 0g and OL are the subdifferentials of the convex functions 9, C. Furthermore, we will argue that the Lagrange multiplier μ., is strictly positive. Combined with p.G(v.)
H. = fU:RA + R Elu < +oo}.
in the KKT condition (6), this means that g(v.) 0, i.e., the constraint G(v) 0 is binding. Following Bellec & Koriyama (2023), equipped with this positive Lagrange multiplier μ > 0 and the binding con- dition (v.) 0. we establish the following equivalence between the minimizer of the optimization problem (5) and the solution to the nonlinear system of equations (2).
where G 1). and independent of (U,Y). Here (U,Y) is equal in distribution to (y,, a w). Almost sure equivalence classes of H. form Hilbert space equipped with the usual inner product (u, v) = B[u(G. U, U,Y),(G, Y)) and corresponding Hilbert norm ||a|| = v (u, We will sometimes refer to H itself as the Hilbert space, in this case we implicitly identify random variables v(G U, Y) that are equal almost surely. For brevity, inside an expectation and probability signs with respect the probability measure of (G.U, S.U.Y., Y), we simply write denote the random variable v(G, U, Y). j. For instance, we write simply B[[G]] instead of U,GG,,,YYC
Theorem 3.1 (Equivalence).
Suppose (a..V.) E IR x H solves the constrained op- timization problem (5) with [|u.]| > 0. Let p. be the Lagrange multiplier satisfying the KKT condition. Let (7x, be the positive scalar defined by
Now we define two functions G and as follows:
a. 1l==lll/Vv---1 8-11 7- =lallo > 0.
g: H. + R, 4 Epcl-EE-G/VI-00
Then the pair O,, (., solves the nonlinear system of equation.
and
L:RX
H
R (-00),
If (ax, Ta, system, letting
Ta, O.) E RxX x R50 satisfies the nonlinear
Bll +i] if Ballr((UU + +)]l < too
(a,v) +00
otherwise
Ux = pr - + a.U
Here, a proper lower semicontinuous convex function, while is Lipschitz, finite valued, and convex function (See Lemma B.1 and Lemma B.2). With these functions (L, 9), we claim that the system of nonlinear equations (2) admits a unique solution if and only if the following infinite- dimensional convex optimization problem over R x H
(a,, v.) solves the optimization problem (5) with ||..|| = o. V-VI---1 > 0 and the KKT condition (6) satisfied for μax = o, a.vovo11000 8-1 //1
Theorem 3.1 implies that the nonlinear system of equations (2) admits unique solution (a., (a.,7s, 0., E R x R x R> if and only if the optimization problem ming(e)go C(a, v) admits unique solution (a., v.) IR x H with v, * 0 and a unique Lagrange multiplier p. > 0 satisfying the KKT condition (6). order to apply Theorem 3.1, we need to establish that the degenerate case v, cannot happen.
min C(a,t) v) subject to ((v) < 0 (a.))ERXH
(5)
admits a unique minimizer (ax, u.) E R x H. We will make this point more precise in the next paragraph.
Lemma 3.2. (Non-degeneracy) fa., v.) solves the opti- mization problem (5), then v, + O.
The key to such an equivalence between the nonlinear sys- optimization problem (5) is the existence of the Lagrange multiplier associated with the constraint (v) < 0. By Proposition 27.31 of Bauschke & Combettes (2017), an element (a,, v.) E R x H. solves the constrained optimization problem (w) C(v) and only if there exists a Lagrange multiplier μ4, 2 such
tem (2) and
In the proof of Lemma 3.2, the differentiability of the loss by is crucial in preventing the degenerate case c, = 0. When the loss is not differentiable, another different threshold, Sperteats emerges to determine whether vs = 0 or v, * occurs (Bellec Koriyama, 2023).
5

---

Phase transitions for the existence of unregularized M-estimators in single index models
Lemma 3.3. (Uniqueness) The minimizer of the optimiza- tion problem (5) is unique if it exists. Furthermore, the Lagrange multiplier satisfying the KKT condition (6) is also unique.
with G. so p" has better chance to satisfy the constraint ((p") S 0 than p. We show in Lemma A.I that
|p-1|| = v 0 llp1 =EGGp]
Combining Theorem 3.1, Lemma 3.2, and Lemma 3.3, we conclude that the system of nonlinear equations has a unique solution if and only if the anfnite-dimensione problem admits a minimizer. This equivalence is useful because studying the existence of solutions the system (2) directly is tenuous analysis problem that has been solved in only few cases: for the Lasso (Bayati & Montanari, 2011;
This immediately gives that if 0 I doc then p* satisfies the constraint G(p.) S 0 in (5) (this is serendipitous and "barely" works out, since for any 8 > doc the constraint would be violated). I & 80 we have exhibited a direction (a.: p.) such that [(sa., sp.) is decreasing in s > 0 and such that (sp.) sp S 0. Since we have found a direction along which the objective function decreasing and which satisfies the constraint, the minimization problem admits no minimizer. All these arguments are made precise and formally proved in the appendix.
optimization
Miolane & Montanari, 2021), 1), or for the global null case of logistic regression (Sur et al., 2019). Instead of studying the system (2) directly, this equivalence allows us to focus on the existence of minimizer for the
convex minimization problem (5). Even though the prob- lem is infinitediimensionall there is well-developed theory for convex minimization in Hilbert spaces (Bauschke & Combettes, 2017) which can be leveraged to study (5); in- cluding the KKT condition or the fact that a coercive convex objective function admits a minimizer.
For the other side of the phase transition, 5 > 620, the following idea used, which exhibits a similarly serendip- itous phenomenon. Here we must show that (5) admits a minimizer. This is typically obtained by showing that the objective function is coercive (i.e., has bounded level sets): that any v, satisfying the constraint such that L(a, v) S & for some & E R must satisfy la + ||w||| I C(E) for some constant C(E). We break the problem by breaking into two parts, v = ū + (v - ū) where
It remains establish that the existence of a minimizer for the optimization problem is governed by the threshold & (which is the same as in Theorem 2.6), thus completing the proof of Theorem 2.7.
(at + +o)- under f2 (2)
Theorem 3.4. Let de be the threshold defined in (4). Then we have the following:
0 == -a +
(aU + +0)+ under (Y)
under (Y)
8 S 80s, the problem (5) has no minimizer.
so that (a, E C for all (a, E H. Here, at + T is the additive part of aU + u that satisfies the constraints in the definition of C and carries risk of generating a ray along which the objective function is decreasing (as for p. in the previous paragraph). On the other hand, the other additive part ë can be bounded using the one-sided coercivity of Ły in Ω (Y) or (Y), and the two-sided coercivity under (Y) (this is made precise and formally proved in the appendix, see Lemma E.2). To bound ō (or directly v) after having controlled e ē, we establish using the properties of p. the inequality
If8 > 8,e, the problem (5) admits a minimizer.
Let us explain where this phase transition comes from, start- ing from the case 8 S 8 where we claim that (5) admits no minimizer. The first idea concerns C: natural avenue to show that there is minimizer is to try find direc- tion (a, v)) such that / + by (s(aU + v)) is decreasing in >> 0 for all realizations of (Y, U) (we are looking for such a direction because if a convex function admits ray along which it is decreasing, then it admits no minimizer). By considering the three events (Y), f2 (2), this motivates the definition of the cone C' IR x H defined as
|| - 8-1 -1l-ll) S Blu(G -p.)]
< 0 under 22 (Y)
< E - v)(p. G)],
(a.p) E C + aU +
0 under 2v
(7)
0 under (Y).
see (27) in the appendix. The factor (VI (VI-8-1 8- -1p--1 in the left-hand side is positive only on the side 8 > 800 of the phase transition, which serendipitously lets us prove that ||||| is in turn bounded, that the objective function is (5) is cocrcive, that (5) consequently admits minimizer, and by the equivalence in Theorem 3.1 that the system (5) admits a solution. This strategy is made precise and formally proved in Appendix E.
Next, the direction we are looking for should also satisfy the constraint G(v)= s 0. This motivates the consideration of
(a.,p.) E argmin((..))cc B|(G -
because among all (a.p) E C such that ||p|| = ||p" |]. the p" defined above necessarily has larger correlation E GGpp
6

---

Phase transitions for the existence of unregularized M-estimators in single index models
Q
1000
theory
1000
theory
1000
theory
800
M-estimator does exist
800
M-estimator does exist
800
M-estimator does exist
dimengion
600
600
600
400
400
400
200
200
200
0
M-ssstimator exists
0
M-estimator exists
0
M-estimator exists
2
e
10
2
8
10
0
2
10
Q
Q-16
theory
1000
theory
1.0
threshold: 1/6_
c=1
feature p
M-estimator does not exist
800
M-estimator does not exist
0.8
c
Q
1-16
0.6
0.4
0.2
M-estimator exists
M-estimator exists
2
signal strength
signal strength
signal strength
Figure 3. Count of instances where the minimizer in (1) exists for varying p/n and signal strength k. Simulation parameter: n = 1000, 20 repetitions, Vi xz satisfies the hinomial model Binomial(g, Pb) as in (9).
4. Numerical Simulation
where pj = =+oxp(-xe) m.) Here, 9 E f1, N is the number of measurement, a hyperparameter to be spec- ified. Given the data set (æ;, U:) we solve the opti- mization problem inf Σ (2. using the loss (1) = q log(1 + exp(l)) - yy; in other words, we compute the corresponding MLE. Similarly to Figure 2, Figure plots the count of instances where minimizer exists in (1) along with the theoretical threshold 1/6- for each hyper- parameter E {1, 2, 4, 8, 16). When g = 1, the simulation setting is reduced to the Binary logistic regression, thereby recovering the figure in (Candès & Sur, 2020). The result for q 2 is new, and we observe that the generalized threshold (4) predicts well the existence of the MLE.
We generate the covariates (w:))= lid N (Op, Ip) and re- sponses yi æ according to the Poisson model
A
Vk E N, P(u: k k
= exp(-Ar), R.!
(8)
where A; = cxp(- x;). Here, ej is the first canoni- cal basis vector, and x 2 0 is the signal strength. We fix 1000 and for varying values of (p/n, kt), we gener- ate 20 datasets of (æ,, y/) For each dataset (æi, == we solve the optimization problem infoes> Σ Ly (z, b) using the Poisson loss b. (1) exp(t)- - yet and record whether a minimizer exists using linear programming. In Figure 2, we normalize the count of instances where a min- imizer exists by dividing by 20, with the black points in- dicating higher rates of existence. Additionally, we plot the theoretical threshold 1e defined in (4) and compare it with the empirical result. The theoretical threshold ef- fectively separates the two regions, delineating where the M-estimator exists and where it does not.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Next, generate yile i according to the Binomial distribution
References
Amelunxen, D., Lotz, M., McCoy, M. B., and Tropp, J. A. Living on the edge: Phase transitions in convex programs
( ppd (1 - -p,)0-
Vk [g), P(y- k|zx))
7

---

Phase transitions for the existence of unregularized M-estimators in single index models
with random data. Information and Inference: A Journal of the IMA, 3(3):224-29)) 294, 2014.
generic features maps for realistic datasets with teacher- student model. Advances in Neural Information Process- ing Systems, 34:18137-18151, 2021.
Bauschke, H. H. and Combettes, P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2017.
Mignacco, F., Krzakala, F., Lu, Y., Urbani, P., and Zde- borova, L. The role of regularization in classification of high-dimensional noisy gaussian mixture. In Interna- tional conference machine learning, pp. 6874-6883 PMLR, 2020.
Bayati, M. and Montanari, A. The lasso risk for gaussian matrices. IEEE Transactions Information Theory, 58 (4):1997-2017, 20
Miolane, L. and Montanari, A. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. The Annals of Statistics, 49(4):23 (444):3313-23333 2021.
Bellec, P. C. and Koriyama, T. Existence of solutions to the nonlinear equations characterizing the precise enror of m-estimators. arXiv preprint arXiv:2312. 13254, 2023.
Montanari, A., Ruan, F., Sohn, Y., and Yan, J. The gen- eralization error of max-margin linear classifiers: High- dimensional asymptoties in the overparametrized regime, arXiv preprint arXiv: 1etXix::911.01555 2023.
Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
Candès, E. and Sur, P. The phase transition for the existence of the maximum likelihood estimate in high- dimensional logistic regression. The Annals of Statistics, 48(1):27-45) 2020.
Salehi, F., Abbasi, E., and Hassibi, B. The impact of regular- ization on nigh-dimensional logistic regression. Advances in Neural Information Processing Systems, 32, 2019.
Sur, P. and Candès, E. J. A modern maximun-likelihood the- ory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29):14516 14525, 2019.
Celentano, M., Montanari, A., and Wei, The lasso with general gaussian designs with applications hypothesis testing. The Annals of Statistics, (1(5):2114-222) 2023.
Cover, T. M. Geometrical and statistical properties of sys- tems of linear incqualities with applications in pattern recognition. IEEE Transactions on Electronic Computers, EC- BCC-143):26-3344, 1965.
Sur, P., Chen, Y., and Candès, J. The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi- uquare. Probability theory and related fields, 175:487-558. 2019.
Gardner, E. and Derrida, B. Optimal storage properties of neural network models. Journal of Physics A: Mathemat- ical and general, 21(1):271, 1988.
Tang, W. and Ye, Y. The existence of maximum likelihood estimate in high-dimensional binary response generalized linear models. Electronic Journal of Statistics, 2020.
Gerace, F., Loureiro, B., Krzakala, F. Mézard, M., and Zdeborová, L. Generalisation eиror in learning with ran- dom features and the hidden manifold model. In Interna- tional Conference on Machine Learning, pp. 3452-3462. PMLR, 2020.
Thrampoulidis, C., Abbasi, E., and Hassibi, B. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592- 5628, 2018
Han, Q. and Ren, H. Gaussian random projections of convex cones: approximate kinematic formulae and applications. arXiv preprint arXiv:2212.055453 2022.
Krauth, W. and Mézard, M. Storage capacity of memory networks with binary couplings. Journal de Physique, 50 (20):3057-3066, 1989.
Liang, and Sur, A precise high-dimensional asymptotic theory for boosting and minimum-E1-now interpolated classifiers. The Annals of Statistics, 50(3):1669-166) 2022.
Loureiro, B., Gerbelot, C., Cui, H., Goldt, S., Krzakala, F,, Mezard, M., and Zdeborová, L.. Learning curves of
8

---

Phase transitions for the existence of unregularized M-estimators in single index models
A. Derivation of threshold from convex geometry
Define 6 E (0, +oo] as
1/6x0 inf (t)) EER
where :p IR R is the convex function defined as
(t) +
+ (() =[[(G T0)))()))))
Here 2, are oYY) -measurabe events defined in (3). We denote by the Hilbert space which consists of measurable function of (G, U) with finite second moments. Let R x be the cone defined
S 0 under Ω (Y)
(t.p) + +p
=0 under 2
(10)
0 under Ω (Y)
Lemma A.1. The threshold 8ec be represented as
8
inf ptt)
inf B[(G p(t))
inf E[[G - B[(G-p) p) (t.p)EC
EER
tER
where (l)) for all E R and p(t) is given by
under (Y)
p(t) = tt +
(G UI)-
under 12 (Y)
(G Ut)+
under (Y).
Suppose that the law of (U, Y) satisfies
E
> >0
(1I)
7(x,))))))) (() [.)}] > >0
T
Then the map &p coercive, i.e. - (t) +o and inf (pt) admits minimizer t, R. Furthermore, the optimal p. p(t.) E satisfies
E = Ely.G), ||p_||
1 V1-
Proof. Fix /. E R. By the definition of the cone C and it easily follows that
inf PE
B[(G p) E[(G p( =
This proves the representation infLeR (t) inf (p))cc B[(G- p) infrer B[(G B[(G-p(t))}) Next, 1et us show that the map ip RR + R
(tt) EE (G + Ut) ((N + +B[ (CC000006DDD))HHC(CCCC333322,,,
is coercive. Since -tt is convex, it suffices to show the coercivity, i.e., lim st()) +00. For the first term, expanding the square of (G + U1)2, it immediately follows that
E[(G + (000://000.00000---0000000001110
For the second term B[ [[]++U))(((00)))
-1C0++-0001000000))---444---1110 G+Ut>> 0Hl
-1000)+0000))

---

Phase transitions for the existence of unregularized M-estimators in single index models
|1]
+00. By E|U = < +00, the dominated convergence theorem implies
E| Ut 0}] = =B00 0)]
+ + <H
[0,,)(0 +++0
(1), +
Thus,
(,) +
B(G++0))//(007)) + ( < 1
22
By the same argument, we have
(M) +00
12 BI B[C+U0)2/(000)11
(Y)) 14-00
Putting them together, we obtain
(t))
E
f "UU"H|00/""H+++00000000000000 < <0]] (10 > 0]]
+ -
Since the limit is strictly positive by the condition (11), the map ł + (tt) is coercive, and hence infrER st(t) is attained at some to E R.
Finally, we prove Elp = Elp.G G] and |p..1 = v1 1-65. The stationary condition of (t(..) = 0 gives
2E + UT, (U0
2E P_)
where
= (4
Here, [[G = since G and U are independent standard normal. Thus, the last equation gives E[p.U] 0. Then, we
have
Elyš] + + 21. Elp.U]
Elp.U] 00
- Ut.)
- + (V + (E +=[10,/)G++03]]]
Elp.G. G = El(p, +UI.)G
EUUG] = 0
By (G 1U0 (G (G+LU)= and the definition of p., get
Elp - Elp.G]
-12 + +E((U.UU+ [UK(U-44JJJ.40000000000004444400
=- + [1--0((((0H0h-110000000-------00
+, EUUL, +p))
by the definition of p.
- +0
EIU = 1, E[Up.] 0
= 0.
The equation ||p.|| /1 8-1 follows from ||p.1|2 Elp.G] and 5-1 EE(G p.))).
10

---

Phase transitions for the existence of unregularized M-estimators in single index models
A.1. Proof of Theorem 2.6
Lemma A.2. Suppose that ey, strictly convex, C² and inf ly (u) is finite. Then the M-estimator does exist if and only if
2 under S2-((1h)
A. RD \ (0) such that
Vi E [n],
mn b
under (2v(
(12)
50 under Ω x1s))
Proof. (12) holds = M-estimator does not exist:. Let L(b) = Ei=1 bn (a) b) be the objective function. Suppose there exists b, Rº \ { such that (12) is satisfied. Then, the map R20 3 t + L(tb,) is uniformly bounded by Σim ey (0).
For all Rº, let b, be the convex combination
b, = (1-1/ (1/v)(ub.), 1.
Note b, - b be as v + +o0. By the convexity of L(b) and uniform bound sup L(tb.) Eii=i (0). we have
I(bb)= 1 (1- +
& (1 1/2) + (1/v)
Σ cy. (0)
Taking p + +o0, the RHS converges to L(b.), while the LHS converges to L(b + b.) by the continuity of L(-) and by - + b., so we are left with
L(b+ S L(b), vb E ER.
Now we suppose that the M-estimator b E argmingeR= L(b) exists. Setting b = in the above display, since b. + Op, we know that b == b. + b is also minimizer with b & b. For all & (0, 1), by the convexity of L(-), we have
L(tb (1 11)8) s (b) + - ())(b)
Since and b minimize T., this holds in equality. With I(b) E, lu (a. and by the convexity of by,, the equality condition reads to
E ey (1x, b b+ +(1 - (1,0) b) ul,, (x. b) + (1 - l) (x.Tb)
must have x. b x; for all E [n]. i.., b- be Ker(X), However, since X E R2 has iid N(0, 1) entry, X is an n x matrix with rank = < This implies Ker(X) (X) {0,}} and b b Op, which is contradiction with b A b. Thus, if (12) holds then the M-estimator does not exist.
for all E (0, 1). By the strict convexity of by,
M-estimator does not exist = (12) holds: Suppose that the M-estimator does not exist. Then, there exists a sequence (b)))= such that as k + +00 we have L(bu) + infbERr L(b) and |bb||] + +oo. By the compactness of the unit sphere in RP, we can extract a subsequence (b())== of (bx) such that / / || - for unit sphere vector v E R.. Therefore,
we can assume without loss of generality that by/ ||b||| converges unit sphere vector es
We proceed by contradiction; suppose (12) is satisfied. Then we can find index i(v) E [m] associated with the unit sphere vector such that
< under (v:)
x; + under (px)
under Ω (w:)
If If (Bs), or Ω (y:),, then the derivative of + ly. (ta: v) is positive for all 2 1. S2y, it is not necessarily positive right away at 1, but eventually positive for large enough, say some l.: for any L., the derivative of L + (lax v) positive. Call this derivative tx, say A x._ vl (t,zz] v) and 0.
Let Uy = by/ by so that a. Uk + +x v. Since ly. is C²,, for l large enough we have that the derivative t + ly. (tx: vk)
i, is larger than 4/2. Call this derivative A = aς. vgl (I. 0R) so that A₁ > A/2 > 0.

---

Phase transitions for the existence of unregularized M-estimators in single index models
By the convexity of l + Ey (lar) 0x), have
tu (2. b&) = Lv. 2200 vx) 2 ly (1,20 ux) + (l|bll - 1.)Ax 2 by (t. Ux)) + (1|ball - 1.)
This gives
L(ba)=
Σ uy (a) bu) 2
Σ inf uy (u) + by (1.20) us) + (l|ball 1.)A,
where the RHS goes to oo since ||b&l| + to0 and A > 0. This is a contradiction with L(ba) - info L(b) < +00. Thus, if the M-estimator does not exist then (12) holds.
Proof of Theorem 2.6. By the rotational invariance of x; ~ (O 1p), we can assume without loss of generality that yi depend on 2; = (Ia, ...,...; Tip) E I" through its first coordinate T2,, ie.,
(yh, F. TL 1.222-1127)
(13)
By Lemma A.2 the M-estimator does not exist if and only if
Span (ee...... Xep) (c(Xe1, # +(0m),
where = 1,, ..,....,) are canonical basis vector in I² and C ((ex, v) is the cone in R" defined as follows:
0 under (B:)
yu P pEc(u,g) < 3t RR such that Vi [n], tu: + P:
under (1.)
under 22 (vs)
Here, Span Xe2,-.. .e...... Xey) is the linear space spanned by the (p- - 1) vectors (Xe:) which is rotationally invariant random subspace in R" with dimension p 1 since Xe; independent standard normal. Furthermore, (13) implics that Span .e.....,. Xep) is independent of the cone C(Xe,, y). Below, we write Xe, u for simplicity. Then, by Theorem I of Amelunxen et al. (2014) we have that for E (0, 1/2), conditionally on y.
1 + stat. (Cu, 3)) 2 n + 1/2+m P(M-estimator exists u, y) + 0,
(14)
1 + stat. dim(C(u, y)) < n 1/2- + P(M-estimator exists 3/)
almost everywhere. Here stat. dim(C(u, y)) is the statistical dimension of the cone given by
stat. dim(C((u, y))
(iiist(g,C(,,) y))² Xe1, y) with
NO,,, In),
where the expectation is taken with respect g. which independent of (u, y). Substituting this (14) with r set to 1/4.
get
1 2 E(dist(g C(u, ") u. yl + + 3/4 > PPMM-cstimator exists u. y) +
1 < E[dist(g. C(u, y) u. v] n2 3/4 IP MMcsttmmator exists u, y) +
With p/n + 8-1, if we prove the convergence
n Eldist(g, C(u, y))² y) - 6-1
then we complete the proof. Below we prove this. Recall Xe; so that (u, y) (u, vu ) Add (U,Y). By the explicit gradient identities (B.7) in (Amelunxen al., 2014), the Euclidean norm of the gradient of g ~ dist(g, C)² is bounded by ||/ Thus, conditionally y. the Gaussian Poincaré inequality (cf. Theorem 3.20(Boucheron et al., 2013)) yields
Eddist C(u, y)) |u, y) = dist C(u, "))² Or(Vn).
12

---

Phase transitions for the existence of unregularized M-estimators in single index models
Here dist C(u, y) inf (e)(u.)) l|g p|| is equal to the optimal value of
0 under f2 (36)
inf Exxp)
Σ lg. pi)2
subject to
Vi E [n], tu +
= 0 under O (1:)
1=1
S 0 under 2 (36)
For each f, we can solve the minimization with respect to p E R". The optimal p p(t) is given by
(gi + u,t)
under (1i,
pt(1) -2y +
under (1s)
(at + u,)) +1()
under f (Vi).
Therefore, 1t (g. C(u, y))² can be written as
1 di C(u, y()²
1 inf BER
Σ
(tu, + +0)2 + (tu; + (1)) + (tu, + x
1=1
inf 4p (t), ER
where
(t) Σ (tu + (50 + (tu,
+ (tu, (())
Notice that ipn (t)(() (t) is random and convex function, and by the law of large number,
(1) + (t)) = Bi + +G) B[(u
for each E R. By Lemma 1, we have
8-: inf (p(), EE
and (p() is coercive, i.e., lim + (p)) +oo. Then, infreR s=(( be reduced mink k se(() for compact K I. and if convex function converges point-wisely then it converges uniformly over any compact set. This provides infeR (t) +P infrER ptt) = 8 and completes the proof.
B. Set up for infinite-dimensional optimization problem
Lemma B.1. Suppose that ey > IR is proper lower semicontinuous convex function. Then the map
Ealr +v) if Elley(aU + + to0
C: H (+00}; (a,w)
+00
otherwise
again a proper lower semicontinuous convxtfuuntion Furthermore, for all (a, v) E dom L, the subderivative at (a, v) given by
0,C [B(U)] h (ay + +b)
0.C aly (aU + +)) n.
Proof. Proposition 16.63 in Bauschke Combettes (2017).
Lemma B.2 (Lemma A.1 of Bellec & Koriyama (2023)), Define G H. + R as
E|uG]
G: H R, u ||a||
VI
Then G is convex, Lipschitz, and finite valued. Furthermore, Fréchet differentiable at {0} in the sense that g(v h) ((v) + E[VG(t))) o(()b]]) for all ||a|| 0, where the gradient Vg(v) is given by
G
Vg(e)
|
8-1
13

---

Phase transitions for the existence of unregularized M-estimators in single index models
Lemma B.3 (Existence of Lagrange multiplier). Assume [[]]y(G)]] +00. Then (a,, v.) E dom L solves the constrained
optimization problem:
min L(a, v) subject to g(v) 5 (o.*)ERxH
if and only if there exists associated Lagrange multiplier nea O such that the KKT condition below is satisfied:
-v,0g(v.)) 0i, v.) + 0, 0 OaL(a., (l,((v)) 0, g 0.
(15)
Now we further assume that
BlJinf, (u)ll +00.
ly is strictly convex.
P(D P(Ω > O and (y()) is not constant with probability 1.
There exists positive constant and positive random variable D(Y) such that under Sly,
(y( 2 1-l Vu E
with E[D(())) < +00.
Then, the Lagrange multiplier is always strictly positive μs, and the constraint binding, i.e., g(v.) O.
Proof. First verify Slater's condition:
levgo 9 int dom g, dom 2 lev 9 + 0.
Since ((v) = E 8-1 is finite valued the first condition lev C int dom & immediately follows, As for and [C(a, 2)
the second condition, (a, v) (0, G) satisfies G(G) 1- 11-18-1)--12
[ S E[ley(G)ll
+00 by the assumption. Therefore, the objective function and the constraint (L, 9) satisfy Slater's condition. With Slater' condition, the "if and only if part follows from Proposition 27.21 of Bauschke & Combettes (2017).
Let us show naa > 0. Suppose μa. = 0. Then, (a., v.) solves min(a.)) Eley + u)]. Now, for any n E N, define un E H
as
Umin [fr (Umin) S n} under Ωry
Un
under 9 9
where umii E argmin wER (u(
under 22
Note that vn is in H since the coercivity assumption implies that under the event Ply,
Uminl [ (fy((uma)) S n) S b(n + ((Y)) S n3]
and the RHS has finite second moment under Shy by the moment assumption on D(Y). Evaluating the objective function (a, v) = (0, v,), by the optimality of (a., v.), we are left with
(a,r(a.U + +.)] S E[ly (0- U ++NN vn)] Elly (umin) (Umii) S [)
Efey (C > [((
+ (-n)
+ Elly
Note that each integrand on RHS is uniformly bounded by inf, (u)) + (6)())), where inff (v)) and [6)- have finite moments by the assumption and Lemma B.4. Thus, by the dominated convergence theorem, taking the limit n + +00, we obtain
(a, + +o.) < (y +0+ Blinf (v) Blinf by (1)
Elin Ey())
14

---

Phase transitions for the existence of unregularized M-estimators in single index models
and (a, v.) inf, by (u) < 0. Since the integrand ( v.) inf, (y(u) is non-negative, get by (a,U U + U.) inf (u
with probability Let us consider the event y. By the strict convexity of (y), under the event 9 y we have always (x) lim (y(-t) inf, yy (u) for all æ. This means that EY (a, U + v.) inf, (u) cannot occur under 92 n and hence r) 0. By the same argument, we get (())) 0. This is contradiction with P( >) P(O so must have μe, > 0.
Lemma B.4. Suppose (G)+ < +o0 and B[inf, [r(u)-] -00 where G ~ (0, 1) independent of Y. Then, [l] < +00.
Proof. Note
(0) < max(- (00) -inf (y
and the RHS has finite moment by the assumption and Jensen's 's inequality 400. Here we have used the fact that u + (u)) is convex and G N(, 1) is independent Y.
B[yy(G)+] <
C. Equivalence between nonlinear system and infinite-dimensional optimization problem: Theorem 3.1
Lemma C.1. Suppose Ellinf, (u)ll < too and (G) < +00. Then for any a, a,o,y E R R X Rz0. proxh]yy[{aU + oG) E H.
Proof. Denote prox(7ey](aU oG) by p.. Since p. minimizes u + (aU oG - u)² + (r(,), we have the upper estimate
1 (al + +oG - pp)² + (p.) - 2
1
(al + to)² + (O).
2
With (p) 2 inf, ey (u), this implies
(aU + LGG-p.y S (aU +
inf by (u)).
u
where the RHS has finite moment. This means aU + oG oG- p. E
e and p. E H.
Lemma C.2. Suppose (a.; v.) E H solves the optimization problem with ||v. > O. Let us take Lagrange multiplier
H4 > O satisfying the KKT condition (15). Define the positive scalar (,,,o.) R2 by
|0..1 V1 8-1'
3.V1-6 8-1
Hx
Then U. takes the form of
V. =
+ +o,G) - a.U
and (ar, ou, On, 7a) solves the nonlinear system of equations:
1 EElly (prox/rey(aaU +o))
(16)
0 ElU (paU) + (aU+
(17)
(11 8-1 E[G prox//ey](aU (aU+((((( +oG]
(18)
Proof. The map v - ((v) is Fréchet differentiable at u. + 0 with VG(v.) = 1 constraint is binding G(v+) (Lemma B.3). Thus, we have
G VI-5-7 (Lemma B.2), while the
-4e VG(v.= -
2x
G
E O,L((a, 0 E V,L(a, G(v.) = 0,
[T.
V1
15

---

Phase transitions for the existence of unregularized M-estimators in single index models
By the definition of (a+, 7x), the condition -ue (V,)) e.L((a,; yields
0,L((a,, 3 - -wv- G. G)//
This means that v. also minimizes the map
u ( = E (a. +2) -
(o.G
(o.G- u)2
H m セ ((v) +
27x
27x
U., minimizes the integrand and belongs to H by Lemma C.I, we have Since pro + t.
V prox[>>ey[aaLU +o.G) a.U E H.
With oG - U/ = ( + a, U), this also gives (v= + a,U) E H. This in particular means (a,t + +.,] E.R With v) = (ElUE' + w]]} n R, the condition 0 E (aL U.) provides
0 (E,Uyy(a + v.)l
With v, = (rox + o.G - a,U, we get (17). As for (16) and (18), rearranging o. = flvull/v/ liu.l//V----- and
g(v.) E/o,////
yields
lo. G 12 = 0 - -2. E(e.G] + ||0.12
= - -2 - 8-1) of 8-1)
6 - o
E[G(v, + a.U) = o. (1 8- +
Substituting prox/> to.G) a.,U to these two equations, obtain (16) and (18). This completes the proof.
Lemma C.3. Suppose (o,, E R x R solves the nonlinear system (16)-(18). Then, (a., v.) E R x H with
U, prox
a., H t.G)) a.U
solves the infinite dimensional optimization problem with ||u.|| =ov1---. > 0, and the KKT condition (15) is satisfied by the Lagrange multiplier μs, a.
Proof. We know from Lemma C.1 that U_ E 7l and oG - U. 7 + a.U) E H. In this case the subderivaitve of L at (ax, v.) is
OaL(a,, v.) (E, + +.)),,, OoL(an, u.) = {e (a. + v.)}
Noting BUUG] 0, the nonlinear system can be written as
8 02 E[(oG 3
(a. + v.)l
σ. (1 8 8-1) E(Gu.).
Here, the second equation gives
0 E Cla, U.).
Rearranging the first and the third equations, have
1| = (1 - 8-1)0 Elu.G] = o, 611
This implies ||v=||| and ((v.) O. Since ||u-|| > O, G is differentiable at The derivative formula gives
||o.1 (g(v.)
||0_1|
(
U.
G
G.G Ca + +o, Ü, w.)
V1 (
7+ ||
7/
74
Therefore, (a,, v.) satisfies the KKT condition (15) with the Lagrange multiplier μ4 ||v-] > 0. and (ax, v.) solves the constrained optimization problem.
16

---

Phase transitions for the existence of unregularized M-estimators in single index models
D. Non-degeneracy and uniqueness
D.I. Proof Lemma 3.2
The argument in this proof is inspired by the proof of Lemma 2.6] in (Bellec Koriyama, 2023). Suppose v, = 0. Let μs, > 0 be the associated Lagrange multiplier satisfying the KKT condition (15) so that e,, solves the unconstrained optimization problem mingen [(a., v) pv)((v) With (()) 0, this gives
(a, = Bléy (a,U + u) + nu, (I|=]] -
5-1)
for all v E H. Multiplying the both sides by X = v1 1 / pr > 0 and denoting f(-) A(by(a,U + ly(a,U)) we
have
0 S A(v) = - - -F[[o] for all E H.
(19)
We parametrize e E H as 0 = prox [ff]( E for all and show A(v)) < for sufficiently small <>> Note that (tG ve) E (0)) implies
- f(()) = f(0) - f(w) 2 - (tG - 20) - wx) = - Gu + 2
Substituting this to (19), noting that G| is cancelled out, we have
A(rr - B + ト + Elu v1 8-1 E|u,G| S - - - (llt (elt - /1 5-1).
(20)
Now we identify the limit of ||0/ /tl as t + 0+. The Moreau envelope constructed function + env, (tG, = 2: (tG v2)2 + f14) has the derivative
1 _ (IG - ux)² jolIG v.) = 2
Ut
21
which is increasing in / because the Moreau envelope env, Thrampoulidis et al. (2018)). This means that vî /t² is non-increasing in t and has non-negative limit as - 0+. By the monotone convergence theorem, we get
env f(x, y) is jointly convex in (I, y) E R (cf. Lemma D. of
lim |////||2 E lim (vr/t)²] [0, +oo] 1
(21)
2-00
Let us compute the limit e/t. First, claim vz 0. By the optimality of i prox(tf](IG)) with f()) Alr + (a.U))) we have
(IG)²
(IG - v2) + +(())) <
+ 5(0) LG2 + 0.
2t
2t
This gives
1
ビ (IG - uz) < G - f(x) = F2 (inn (r (r(a
Since (G,inf, (r) are all bounded in L,, they all finite with probability 1. This provides lim,-o0 82 0. Combined with G wt/t = (v,) (a.U + vt), since Ey (-) is C²,, we get v1/t G - Mly (a.U). Substituting this limit to (21), we obtain
||///t|12 + E[[G
Recall that (19) and (20) imply
0 < (1o))/15--1111 1 - -
V-1 40 0.
This excludes the case B[(G Mly (a) +oo otherwise the RHS converges to -00 as 0. Thus, we must have E[(G (a.U)) +o0 and by (a.U) H. Expanding the square, since G and (a.(a independent, we get
lim ||2//t|22 = = X² (a, 6+
Substituting this to the upper bound of A(wx)/t
lim - [|ax/t][[]ua/]]]] - v1 8-1)
(a. (a XE
-1110------68 5-1)
<- -1-511511 < 0,
which implies that there exists a sufficiently small such that A(vr) )/t < 0. This is a contradiction with A(vi)/t 2 0 for all 0. Therefore, we must have v, A
17

---

Phase transitions for the existence of unregularized M-estimators in single index models
D.2. Proof of Lemma 3.3
Suppose that there exists two minimizer (a, (d', E R H. Let (ae, 0z) ((a, v) + (1-1))))) ()( e') for all t E [0,1]. 1]. Then, by the convexity of objective function and constraint, (a,, Uz) solves the constrained optimization problem. This implies C(a,, v1) tC(a, v) + (1 t))( v') for all t [0, 1J. With C(a, v) Efly (aU + +)],, we must have
E (lrr(t(aU + + (1 t)(dU + +1)) (aU +0) - (1-t)yr(oo o') 0.
By the convexity of ey.
cy (t(aU + +u) + (1 - (a'U + d')) = (aU + u) + (a'U + +1))
for all & E [0, 1]. By the strict convexity of Ey, we must have aU + === a'U + + If a a' holds then we have v = 2/, completing the proof of uniqueness. We now show that a = a'. The condition al + a'U + + gives
o' + tU (a a'), 2t- to + t1- = ttu + Uaa d')} (1 - t)' =
so that G] = Elu'G G by independence of G and U. Meanwhile, since (a,, 0z) solves the constrained optimization
problem for all [0, 1], the constraint is satisfied in equality ||mz]| [E[u,G]/v 0-I 0 for all / E [0, (see Lemma B.3). Then, ||all| must be constant well. The polynomial ||0:|12 is given
+ + U(aa o 2 ||l + ta d2)l1 ||
t/o' a')]
(a-2
Since it is constant in t, the quadratic term must be O, hence (a - =
Finally, let us show the uniqueness of Lagrange multiplier. Suppose that there exists two distinet Lagrange multipliers μ.a * M.a. E 2 associated with the minimizer (a,, v.). Since the subderivative a (a,,, v.) the singleton {Ey(a.U (a.U v.)} the minimizer (a.: v.), the KKT conditions
- -, (G(.), VQ((v. E O.f(a.. v.)
lead to
14. Vg(c.) = pi.. vg(v.) =
+ v....
Combined with usa # Moa, this gives VG(r.) = 0 and Ey (a.U +v.) = O. Here 0 = VG(v.) = - implies u. [r.11 G. Letting a. |l..Il/ 8-T > 0, substituting this to Ey (a, + v.) = 0, we get
V1-8-1
Ey (a, +o.G) 0
Since ly is strictly convex, this means P(Iv)) = 1, which is contradiction with P(O.)) < 1. This completes the proof of uniqueness of Lagrange multiplier.
E. Proof of the phase transition: Theorem 3.4
Lemma F.1. If 800, the optimization problem (5) does not admit any minimizer.
Proof. Let us take (t..p.) E C IR x H as in Lemma A.1 so that
Ip. |l = / 8=d, =
Substituting this G(p-) ||p-1| || Ely. G// /11 1 8-1, using the condition 8 5 dra. we have
((..) = ||p-1 VI- 8
S O,
i.e. P. satisfies the constraint 9 < under the assumption 8 S 820
18

---

Phase transitions for the existence of unregularized M-estimators in single index models
Let us fix (a, v) E dom & n go combination with coefficients (1 1/2) and 1/v given by
so 9 so that B u)ll +o0 and G(v) S 0. For any 2 consider the convex
(ov. Uv) = (a, u) - 1/v) + (1/v)(ut,, vp.).
Note that (Oz, vv) - (a, u) + (t,.P.) almost surely as v + +oo. By the convexity of 9, the convex combination (av, Up) also satisfies the constraint ((v)) S O. On the other hand, the convexity of by implies
(a + vw) s (1 (1-11/)er(aU + +0
(1/v) (r(vl. vp.).
Here, by the definition of v..
(r(v(G+U()))) under Ω
Ey(vt,U+ + = (y(v(G+U())) under S under l2y
((((0)
and hence by Uvt,U + vl.) uniformly upper bounded by (0) for all v 2 We have (a + vw) s (1- (11)6 v) + (1/v)6r(0).
(22)
Taking expectation, we get
Clav, v (1 (1- (1-1/v)((a,) + (1/v) B[)
Now we consider the limit +oc. The RHS converges to L(a, v) as + to0 since we took (a, v) dom & and E[](y(0)]] < +o by Lemma B.4. As for the LHS L(a,, v.) Elyy (a (a. + v.)), from (22), the integrand uniformly
bounded as
la, +w²0l & inf by (w)l (ay + v) + [0)
where the RHS has finite expectation. Therefore, by the dominated convergence theorem, we get
lim C(ay, vn) lim (a u.)]
+00
v-++o
= E lim (y + v,))
E[ly((a (.)U + v p.)
by (av, v2) (a + bw, U and the continuity of (-(+)
L(a + u px).
We have proved that for any (a, u) dom L, the inequality L(a + tr, v + p.) s C(a, v) holds.
Now we suppose that minimizer (Amin, Vmin) exists. Then it must be unique by Lemma 3.3. Applying the inequality
C(a + L.,0 p.) ) S C(a, v) we have established with (a,v) = (aminy Umin), we must have l, = p. = 0. Substituting this the definition of p., we left with
(G) (G)+ (1)11)))))))+)00000000))))))1111 =0
Taking the expectation of this, since G and Y are independent and [[[ [[ 22/m O, we obtain (Y)) + P() 0, which contradicts the assumption I(())) P(2)(()) P()) 1. Therefore, the minimizer does not exist.
Lemma E.2. Assume that there exists positive constant b and positive random variable D(Y) with B(D(Y)) < +o0 such that
u under Ω under Ω
1
2u))--((Y) +
[u] under Z
Suppose 8 > 6xc- Then for any deterministic & O, if (a, u) satisfies gvv) S 0 and L(a, < &, then a + ||]|| S C(E) for some constant depending on &. Consequently, the objective function of the minimization problem is coercive and admits a minimizer (a., U.) by Proposition 11.15 in (Bauschke Combettes, 2017).
19

---

Phase transitions for the existence of unregularized M-estimators in single index models
Proof. By Lemma A.I, dee be represented d2 min((,))ee BB[G p) where C H. is the cone defined
< 0 under S2
(a, EC (u+ ali)
2 0 under 92>
under S2y
and the optimal p.) E argmin (G,)eC E[(G p) satisfies
|p..1| = V1 850
V1 - 8-1, ElP.] Elp.G)
(23)
where we have used 5 > 800 Now for all (). E R H. define ë E H as
(aU +2)- under Ω ,
= -U +
(at + +u+ under 2 under Qu
0
so that (a, 8) E C for all (a, E R x H. Furthermore,
(u + aU)+
under ? >
e w-
(v + at) under 22 and consequently
||u -0ll S ||ma| + |a|
1 + aU
under Pyy
By the condition L(a, v) = (e(rr (at + +)] S E and the using the variable D(Y) in Assumption 2.5, we know
ly ((v + at)+) ((v + al)))
under 22 under 52>,
1u 1- 81 D(Y) +
er (v + at)
under f2
Ey (0) (y + at)
if and at + v S 0
=
+0) +
(0) fy + al))
if and al + v 2 0
0
otherwise
< bey +0) + (0) inf (u))
so that
v i|] < bE + E(D(Y) + ME (0)l + En = (E)
By Assumption 2.4, we can take sufficiently small un such that
22 {IV no
n > u uf { -u) n = }u [10] >0 nSw
Ω {(U~ -oo Ju no) n u [[17] n
have positive probabilities. Let po min((((2))) > 0.
Suppose a > 0. Under {U > non 2 x, it holds that al + 5 (aU +v) + D(Y) and hence
auo S al < (aU + +) + D(Y) c.
Under IU < -uu} n S we have - -aU + v) < bey (aU + +) + D(Y and hence
auo S aa(U)) < bly (aU + v) + D(Y) +
Finally, under ([U) >> uo} O Lv, we have |aU + o| S byy (oU + v) + D(Y) + v so that
aup S a < |aU wl + |o| s (aU + v) + D(V) + |o].
20

---

Phase transitions for the existence of unregularized M-estimators in single index models
Combining them all together,
ang (((+) & (1T(4+)aun)
S bE(((y +0) +(+)+++++))))+))))) +00))))))))0)))) [++)
bEl(fr(aU + v) - inf (nf + inf (v(() + D(Y) + [2))
20
20 S bB(ly(aa + v) inf + (00 BDD E|wl
= bblly(aU + - - ++
- bg + Ell inf (u)]] + D()) + |2l12
By the same argument, if < 0, considering the event Ω2_, we have
(-o)uo P(L_) b9 | inf
+ 1ee12
Combined with min(PP(S, P(D_)) Po > 0, we have that
|a| < ( + E inf By (x))l + E[D] + [Tells) s Ci(E)(1 + [|0l12)
With ||u al| < |a|- + ||ll| we obtain
||U 1w-88 811 (E((+
(24)
Now we claim that the Pythagorean inequality
EI(G - pp)) El(p. - -) < B[(G - -
(25)
holds. A proof of (25) is as follows. Define for s E [0, 1] the convex combination vs =ppp - 8) + sē and consider the function
(s)) = =E((G - v,)31 - E - p.) - B[(v,- - p..)
By the definition of Ug. it follows that -0) = 0. Furthermore, (ps) is linear in s, as the quadratic term E[p3] cancels out. On the other hand, the optimality of (I,,P=) ) E argmin(e.))ec [ p) implies that B - p. )²] I E - v,
Combining this with the definition of (ps), we have sps) 2 - -[((r, - p.)² = - ->2E((p El(p. - e) Since (p(s) is linear in 8
and satisfies cp(s) 2 (s²2) as s - 0, the slope sp (0) must be non-negative. This implies 0 = (0) I (1). which is exactly inequality (25).
In both sides of (25), B[r²] cancel out, E[G*] and B[[(G - p.) 1- ||p=11 by (23), so that (25) can be rewritten as E p. i| S 2 R(GG),
i.e.,
-e)(p--G)] G 0.
(26)
From this, for all e satisfying the constraint G(v) = ||a|| - E[u 5-T S.
(V1-8-1 8-1 - -11p-ll -lpp-1) ||||||
< B[uG] - ||l
by ((v) ||a|| -
1 -
< E[u(G - p-)]
by the Cauchy-Schwarz inequality Klp.v]] s ||p-||||||| by E(e(p. G)] 2 0 in (26).
< (ū - cp - GG]
(27)
The parenthesis V1- 8-1 ||p_|| on the left is positive thanks to (23). On the right-hand side, considering the event be specified later, the Cauchy- inequality gives
[(p. - G| > C) for some constant
( - w)(p. - G)) < C Clll - w| + E[Tip.. G > CHp.- - Glj - =I]
< C BBll - w|] + v ELL G| C) p. GJ-] f||
21

---

Phase transitions for the existence of unregularized M-estimators in single index models
Since Pe G is bounded in L2, take sufficiently large (ea for all such that EE[[pp
G
(c) G ?] v e² Thus, have that for all
0,
(v1- -1p--1 ||||| S (c)( r +e|lo 2.
(28)
Recall the bound ||v - ill v (() + ||=|]) in (24), so if we take a sufficiently small e = 60 such that en (()))()
(vI - 1-----_-- - [pp11)//2 we obtain
[ -1-8--11lp-1)1-v & C(co) E ul + ca (5)
(29)
Since E
- v| S (E) was established at the beginning, this completes the proof.
22


Reviews:
[{"review_id": "kyiCwkdjuX", "reviewer": "Reviewer_LDvE", "summary": "This paper studies phase transitions for the existence of unregularized M-estimators in single-index models under proportional asymptotics, where the sample size n and feature dimension p grow proportionally with n/p → δ ∈ (1, ∞). The authors generalize results previously established for binary logistic regression by Candes & Sur (2020) to more general loss functions and single-index models. They derive an explicit critical threshold δ∞ governing the phase transition for the existence of the M-estimator and rigorously prove that the corresponding nonlinear system admits a solution if and only if δ > δ∞. The work relies on convex geometry, the Gaussian kinematic formula, and infinite-dimensional optimization techniques to establish these results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for highlighting the importance of earlier foundational work from the information theory and statistical physics communities. We agree that the phase transition phenomena studied in our paper are connected in spirit to classical results such as Cover (1965) on the geometry of linear inequalities, which leads to the threshold $\\delta_\\infty=2$ when the response $y_i$ follows the Bernoulli (1/2) and feature $x_i$ are independent from $y_i$. We also appreciate the pointer to earlier works in statistical physics: Gardner & Derrida (1988), Krauth & Mézard (1987).  We will revise the manuscript to include the historical overview, explicitly acknowledging these contributions. \n\nWe also thank the reviewer for drawing our attention to more recent developments, including Mignacco et al. (2020) and Gerace et al. (2020). While our focus is on the existence of unregularized M-estimators for single-index models with Gaussian design, these papers explore related questions and offer complementary perspectives.\n\nThe threshold in equation (27) Mignacco et al. (2020) is not directly recovered by our results, since we assume here $x_i\\sim N(0, I_p)$ which is not satisfied in the Gaussian mixture setting of Mignacco et al. (2020). However, the techniques presented in the submission can be used to prove that the system in Mignacco et al. (2020) has a solution, and we will add a remark to that effect in the camera-ready version.\n\nRegarding whether machine learning conferences such as ICML are suitable, we believe ICML and similar venues strive to present mathematical results with no gaps. The existence of solutions to the system of equations governing estimators in proportional asymptotics has been typically assumed in the theorems of the corresponding publications, for instance the CGMT paper (Thrampoulidis et al. 2015), Sur and Candes (2018) or Salehi et al. (2019), and several others assume in the theorems that the system of equations of interest admit a unique solution. Existence of solutions to the system can be easily deduced under a strong convexity assumption (e.g., with an additional L2 penalty $\\lambda\\|\\cdot\\|_2^2$), but taking the the limit $\\lambda\\to 0$ as in Appendix B.3 of https://arxiv.org/abs/2201.13383 to deduce results from the strongly convex case $(\\lambda>0)$ to the $\\lambda=0$ case by continuity requires that the low-dimensional system corresponding to $\\lambda=0$ has a unique solution. Thus our method to prove that the system has a unique solution complements these works, and in a sense fills the gap and completes the argument.\n\nThanks again for the careful reading and pointers to the missing references.", "claims_and_evidence": "These are theorems, with rigorous proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "These are theorems, with rigorous proofs. The mathematical derivations are elegant and rigorous. The results clarify and extend known phase transition phenomena in M-estimation.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper does a good job covering prior work in high-dimensional inference, particularly the literature stemming from Candes & Sur (2020) and related works in convex optimization.", "essential_references_not_discussed": "The author however seems to omit some of the early foundational studies in information theory and statistical physics, which introduced similar phase transitions long before the modern convex-geometry-based approaches. In particular, the classical results of Cover (1965) on the geometry of linear inequalities and Gardner & Derrida (1988) on the storage capacity of neural networks are directly related to the question of M-estimator feasibility in high dimensions. Moreover, Krauth & Mézard (1987) already presented a phase diagram remarkably similar to the one studied here, predating modern convex-analytic approaches by decades. It would be valuable for the authors to acknowledge these contributions and place their results within this broader historical context.\n\nIn more recent year, i can think of few generalization of Surr results, in e.g. \"Mignacco, F., Krzakala, F., Lu, Y., Urbani, P., & Zdeborova, L. (2020, November). The role of regularization in classification of high-dimensional noisy gaussian mixture. In International conference on machine learning (pp. 6874-6883). PMLR.\" which might be covered by the author theorem, or the random feature version of separbality in \nGerace, F., Loureiro, B., Krzakala, F., Mézard, M., & Zdeborová, L. (2020, November). Generalisation error in learning with random features and the hidden manifold model. In International Conference on Machine Learning (pp. 3452-3462). PMLR.", "other_strengths_and_weaknesses": "Overall, while the results are rigorous and mathematically insightful, their practical significance for ICML could be debated.After all the main contribution is a proof a known and accepted results. While this is a welcome addition, it is not clear that ICML is the best venue. I nevertheless support publication.", "other_comments_or_suggestions": "See above", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "cZPWEdQ1BQ", "reviewer": "Reviewer_kj91", "summary": "This paper investigates the existence of solutions to the nonlinear system of equations that characterize the asymptotic behavior of the M-estimator. Notably, the existence of a solution for $\\delta>\\delta_{\\infty}$ remains largely unproven when the assumption of independence between $x_i$ and $y_i$ is removed in binary logistic regression. The authors extend the existing theory in two key directions: (1) they generalize the results from binary logistic regression to a broader class of single-index models (strictly convex loss), and (2) they analyze the problem beyond the global null case, providing a necessary and sufficient condition that ensures the system admits a solution. This result effectively addresses a gap in the existing literature.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the careful reading of the paper and the kind words. We will be happy to provide clarifications if needed in later discussions.", "claims_and_evidence": "Claims are well supported.", "methods_and_evaluation_criteria": "As this paper generalizes the results of Candès & Sur (2020) from binary logistic regression to a broader class of single-index models, the authors provide numerical validation of their methods by generating data from a Binomial distribution, which can be easily transformed into binary logistic regression by setting $q=1$. Their method was verified and shown to be consistent with the results of Candès & Sur (2020).", "theoretical_claims": "The main proof strategy was presented in the main text. And I briefly read the proof in the supplementary. The theoretical claims look solid to me though I didn't verify every single piece of the details in the proof.", "experimental_designs_or_analyses": "The experiments are straightforward and effectively validate the soundness of the results.", "relation_to_broader_scientific_literature": "Candès and Sur (2020) primarily examine phase transitions in high-dimensional binary logistic regression models. A key contribution of this paper is its generalization of their results from binary logistic regression to a broader class of single-index models. Additionally, this work advances the theory beyond the global null, addressing a gap left by Sur and Candès (2019), which focused only on numerical solutions.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "I find this paper to be well-written and clearly articulated in its contributions. To the best of my knowledge, it is original in addressing a theoretical gap in the phase transition literature by extending the theory beyond the assumption of independence between $x_i$ and $y_i$,  particularly beyond the global null setting.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "n/a", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "n/a"}}, {"review_id": "OeEiwoVUAe", "reviewer": "Reviewer_om5X", "summary": "This paper studies the phase transitions for M-estimators in single index models. Prior work has demonstrated that there exist a threshold $\\delta_{\\infty}$, such that when $n/p \\to \\delta$, then the M-estimator exists with high-probability when $\\delta > \\delta_{\\infty}$ while\nthe M-estimator does not exist when $\\delta < \\delta_{\\infty}$. However the prior results only apply to binary logistic regression, while this work generalize this result to other single-index models. \nAnother contribution of this paper is that, there is a corresponding nonlinear system which governs the asymptotic behaviour of the M-estimator, but the existence of solution to this system for $\\delta > \\delta_{\\infty}$ is unproven. The authors address this gap by proving the existence of such solution when $\\delta > \\delta_{\\infty}$.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your suggestion regarding the introduction.\nThe single index model is a  flexible yet interpretable framework for modeling nonlinear relationships while avoiding the curse of dimensionality.\nSingle models are useful because it is a weak assumption regarding the modeling of $y_i\\mid x_i$. It only assumes the existence of a ground truth $\\beta^*\\in \\mathbb R^p$ (or $w$ in our paper), and that the response $y_i$ only depends on $x_i$ through the inner product with the ground truth $\\beta^*$. But makes no assumption on how $y_i$ depends on $x_i^T\\beta^*$, in particular any nonlinearity is allowed.\n\nFor machine learning in proportional asymptotics more specifically, single index models (or more generally multi-index models) allow to characterize the limiting behavior of estimators by a low-dimensional system of equations, for example equation (2) in the submission. Techniques in the submission push the understanding of these systems of equations (sometimes referred to as Gaussian Equivalent Model) that arise from CGMT (Thrampoulidis et al, 2015) or Approximate Message Passing analysis. Without the single-index (or multi-index) model assumption, for instance if $y_i$ depends on $x_i$ through a growing number of dimensions as $n,p\\to+\\infty$, we are not aware of an established Gaussian Equivalent Model.\n\n**Regading what happens if $p/n\\to\\delta$ for $\\delta=\\delta_\\infty$**: It is known that phase transitions arising from the convex geometry arguments of Amelunxen et al (2013) have a $1/sqrt n$ width of uncertainty. More concretely, the top of page 5 \nhttps://arxiv.org/abs/1804.09753 (Sur and Candes, 2018) explains this as follows: for any sequence $\\lambda_n\\to+\\infty$,\n\n- if $p/n > \\delta_\\infty^{-1} + \\lambda_n /\\sqrt n$ then $P(\\text{M-estimator exists})\\to 0$,\n- if $p/n < \\delta_\\infty^{-1} - \\lambda_n /\\sqrt n$ then $P(\\text{M-estimator exists})\\to 1$.\n\nSo it is possible to be more precise and study what happens near the threshold as long as $p/n$ stays a little more than $1/\\sqrt n$ away from the critical treshold. But this phenomenon was known since Amelunxen et al (2013) and  Sur and Candes (2018), so we did not emphasize that in the submission. We will add a remark explaining this, including the above pointers, in the camera-ready version.", "claims_and_evidence": "Yes, the two major claims are supported by clear and convincing evidence.\n1. the M-estimator exists with high-probability when $\\delta > \\delta_{\\infty}$ while\nthe M-estimator does not exist when $\\delta < \\delta_{\\infty}$ for general single index models. \nThe claim is justified by theorem 2.6.\n\n2. the existence of the solution to the critical linear system when $\\delta > \\delta_{\\infty}$.\nThe claim is justified by theorem 2.7.", "methods_and_evaluation_criteria": "This paper does not involve evaluation.", "theoretical_claims": "I have not check the correctness in detail. But the reasoning in the main text, where the authors relate the proof of Theorem 2.7 to infinite dimensional optimization problems seems to be reasonable.", "experimental_designs_or_analyses": "The experiments in section4 is sound and supports theorem 2.6. Theorem 2.7 is not supported by experiments.", "relation_to_broader_scientific_literature": "I am not an expert in this area, so I am not sure how the theory for single index model can affect the broader community.", "essential_references_not_discussed": "I do not find essential related works not discussed.", "other_strengths_and_weaknesses": "Strengths:\nThe authors generalize the theory of phase transition in single index models from binary logistic regression to general models,  which is of good significance. The theory for the existence of solution regarding the nonlinear systems is also of great importance. \n\nWeaknesses:\nno obvious weaknesses.", "other_comments_or_suggestions": "Is it possible that in the introduction, you briefly introduce how single index model is applied in machine learning? And why the phase transition is important.", "questions_for_authors": "What will happen when $\\delta = \\delta_{\\infty}$? Are there any more detailed characterization of the existence of the M-estimator under this border line scenario?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E0M3qfqdPl", "reviewer": "Reviewer_tCFd", "summary": "This work considers the problem of the existence of M-estimators in the proportional high-dimensional where the number of samples $n$ and covariate dimensions $p$ diverge at fixed rate $n/d\\to\\delta$. The main result is to establish a sharp frontier $\\delta_{\\infty}$ separating regimes where the probability of existence of a minimizer is asymptotically zero or one. This is achieved by exploiting a duality between the existence problem and an optimization problem in a Hilbert space, for which standard techniques apply.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the additional references. \nWe agree that the phase transition phenomena studied in our paper are connected to these earlier works in statistical physics. We addressed this point in our rebuttal to reviewer LDvE; in a way our results are complementary and fill a gap. We will add the references given in the review to the camera-ready version.\n\n**Regarding the assumption $\\delta>1$**\n\nThe assumptions $\\delta>1$ appears in several places. First, we used the assumption $\\delta>1$ for the infinite-dimensional optimization problem in equation (5) to be well-defined, where the constraint is given by $\\|v\\| - \\mathbb{E}[vG]/\\sqrt{1-\\delta^{-1}}\\le 0$. \n\nSecond, $\\delta=1$ allows for instance $p=n$ whence $X\\in R^{n\\times p}$ is almost surely invertible.\nIn this case, for a given $y_i$, one can always find a vector $b\\in R^p$ such that $x_i^Tb$ has a given sign for each $x_i$, so the problem is trivially separable.\n\nFinally, $\\delta\\le 1$ allows for instance $p\\ge n+1$, in which case the M-estimator (if it exists) is not unique (i.e., several solutions to the minimization problem in $R^p$ exists). Further structural assumptions are then needed to have a well-defined M-estimator, for instance by considering the solution with minimal L2 norm. \n\n**On question regarding the lower bound $\\delta_\\infty \\ge 1$**:\n\nIt is always true for any convex function and response structure of $(x_i, y_i)$ as long as assumption 2.4 is satisfied. This is because the threshold $\\delta_\\infty$ is defined as \n$$\n\\delta_\\infty = 1/ \\Bigl(\\inf_{t\\in \\mathbb{R}}\\varphi(t)\\Bigr) \\quad \\text{with} \\quad \\varphi(t) = \\mathbb{E}[(G+Ut)^2 I_{\\Omega_\\vee(Y)}]  + \\mathbb{E}[(G+tU)^2_+  I_{\\Omega_↗(Y)}]  + \\mathbb{E}[(G+tU)^2_-  I_{\\Omega_↘(Y)}].  \n$$\nHere, by $x_{-}^2 \\le x^2$ and $x_{+}^2\\le x^2$, $\\varphi(t)$ can be upper bounded as\n$$\n\\varphi(t) \\le \\mathbb{E}[(G+tU)^2] = 1 + t \\mathbb{E}[U^2], \\quad \\forall t\\in \\mathbb{R}, \n$$\nso taking $\\inf_{t\\in \\mathbb{R}}$ gives the upper estimate $\\inf_{t\\in \\mathbb{R}} \\varphi(t) \\le 1$. Combined with the definition of $\\delta_\\infty$, we get $\\delta_\\infty \\ge 1$.\n\nIn terms of statistical interpretation, the threshold $\\delta_\\infty$ decreases when the loss becomes coercive for more realizations of $Y$. This is because $(G + tU)^2$ dominates the other terms $(G + tU)^2_+$ and $(G + tU)^2_-$ pointwise, so $\\varphi(t)$ increases with $1_{\\Omega_\\vee(Y)}$ for each fixed $t$, thereby reducing $\\delta_\\infty = 1 / \\inf_t \\varphi(t)$.\n\nThis behavior is illustrated in Figure 3. For the Binomial loss with $q$ repeated measurements, $\\Omega_\\vee(Y)$ is equal to the event $\\{0 < Y < q\\}$. Consequently, $\\delta_\\infty$ decreases with larger $q$, as observed in the figure.\n\nWe will incorporate the above discussion into the camera-ready version.", "claims_and_evidence": "All the claims are followed by rigorous mathematical proofs. Numerical simulations are also provided as an illustration of the result in particular cases.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "I did not carefully check the proofs, but I did skim through them and did not find any red flag. The proof scheme builds on well-known previous work in the literature.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "Although there is not a classical \"Related Works\" section, the authors do a good job in situating their results within the literature. Their work is motivated by (Sur & Candès 2019; 2020), and build on previous contributions from (Montanari et al. 2023; Bellec & Koriyama 2023; Thrampoulidis et al. 2018), which are extensively acknowledged.", "essential_references_not_discussed": "The only missing works I would add are: [1] which was the first work to show that $n=2*d$ Gaussian points can be linearly separated at large $d$ and [2] who generalized this result to linear separators with a given fixed margin. They are not essential, but are foundational works concerning the question addressed here.\n\n- [1] Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with applica-\ntions in pattern recognition. IEEE transactions on electronic computers, (3):326–334, 19651964\n\n- [2]  E Gardner and B Derrida. Optimal storage properties of neural network models. 1988 J. Phys. A: Math. Gen. 21 271", "other_strengths_and_weaknesses": "Overall, I think this is a solid and well-written contribution. It clearly states the results, how it fits the literature and delivers what is promised, without overclaiming.\n\nOf course, this work has all sorts of the typical limitations related to exact asymptotic works (particular data distribution, convexity of the risk, etc.). But in my opinion these are all minor.", "other_comments_or_suggestions": "I would suggest the authors add a small discussion on the statistical implications of their findings. For instance, from the formula for $\\delta_{\\infty}$, can you say anything on the class of link functions which lead to higher or smaller threshold? What phenomenology can we draw out from the theoretical result?", "questions_for_authors": "Perhaps this is a naif question, but where does the limitation $\\delta\\in(1,\\infty)$ come from in the proof? Is it clear that $\\delta_{\\infty}>1$ for any convex loss function?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies phase transitions of existence of M-estimators in single index models in the proportional asymptotic regime. Authors assume isotropic Gaussian input and let the sample size n and feature dimension p to infinity while their ratio converges to a constant \delta. Authors generalize the results of Candes and Sur 2020 to other single index models and find a threshold for \delta that determines the existence of the M-estimator.


This paper was reviewed by four expert reviewers the following Scores: Accept, Accept, Accept, Weak Accept. I think the paper is studying an interesting topic and the results are relevant to ICML community. The following concerns were brought up by the reviewers:

- Some foundational references are missed. These should be cited and discussed in detail.


Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. Based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend including this paper to the ICML 2025 program.
Decision: Accept (poster)