acceptodds
Under review as a conference paper at ICLR 2027

Sharp Limits and Efficient Recovery of Latent Memberships in Random-Design Regression

Abstract

Mixed regression models capture population heterogeneity through distinct regression relationships across latent groups. When group memberships are scientifically or practically meaningful, recovering them becomes a fundamental inferential problem. Yet the statistical limits of membership recovery remain much less understood than those of estimating the regression components. For the two-component Gaussian random-design model with , we show that the minimax mis-clustering risk is of order for noise-to-signal ratio , while exact recovery is possible if and only if . These limits arise from an intrinsic ambiguity induced by the random regression margin, whose mass near zero determines the mis-clustering scale, while the minimum realized margin across the sample governs exact recovery. We further develop an efficient procedure attaining both limits, in which a bounded-residual spectral direction is combined with the pooled residual to form an initial partition, followed by hard least-squares iterations that geometrically contract a margin-weighted Hamming loss.

Primary area:
learning theory
Keywords:
latent group recovery, mixed linear regression, exact recovery, minimax theory

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_hyUnOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies recovery of realized latent memberships in a two-component Gaussian random-design regression model with balanced, fixed but unknown labels and unknown regression coefficients, covariance, and noise level. It establishes a minimax Hamming-error scale of min⁡(1,r)\min(1,r), up to an exponentially small upper-bound remainder, and the exact-recovery criterion nr→0nr → 0 when pp is at most a sufficiently small multiple of nn. It also proposes bounded-residual spectral initialization followed by hard least-squares refinement. A uniform contraction analysis for margin-weighted Hamming loss establishes efficient attainment of the recovery scales. Simulations examine recovery, computation, initialization, and several departures from the main model.

Critical strengths
  1. The statistical question and resulting distinction are valuable. Recovering the realized labels is different from estimating shared regression components. The random margin explains why an order-r error remains even with known coefficients, and why exact recovery depends on the sample minimum rather than a fixed separation. The oracle formula q(r)=arctan⁡(2r)/πq(r)=\arctan(2r)/\pi makes this mechanism particularly transparent.
  2. The paper goes beyond an oracle calculation. The profile-RSS upper bound and balanced oracle subfamily connect the information-theoretic lower and upper bounds while accounting for label switching. The efficient procedure then addresses the computational limitation of exhaustive partition search.
  3. The local analysis is a substantive contribution. The use of margin-weighted loss, uniform control over local coefficient pairs, and the separate treatment of in-sample oracle errors address the lack of a uniform positive margin and the dependence created by reusing observations. This is more informative than assuming independently generated iterates or imposing a deterministic separation gap.
  4. The initialization and experiments support the theoretical story. Bounded residual weights preserve the population contrast direction and avoid the unfavorable concentration behavior of unbounded squared residuals. Appendix F includes the weighting ablation, unequal group sizes, intercepts, covariance and common-center changes, and non-Gaussian/dependent noise. The paper appropriately distinguishes the improvement in spectral direction from the smaller improvement after refinement in many settings.
Critical weaknesses
  1. The practical stopping rule is not fully connected to the stated efficient guarantee. Theorem 1.2 requires K≥⌈5log(1/r)⌉K \geq \lceil 5 log(1/r)\rceil even though rr depends on unknown quantities. Remark 3.1 suggests stopping when assignments stabilize, but the paper does not give a data-independent polynomial iteration cap with the same guarantees, or fully specify the stopping/capping rule used for the proposed method in the numerical study. Stabilization makes further exact iterations redundant; the remaining question is how long one must wait and how the implemented procedure is covered by the theorem. This appears addressable within the existing contraction argument.
  2. The scope of “sharp limits” should remain explicit. The results are for two components, Gaussian design and independent Gaussian noise, balanced groups, and p≤κnp \leq \kappa n for an unspecified sufficiently small κ. The Hamming upper bound contains an exponentially small remainder, so it is not a uniform constant-factor equivalence to r for arbitrarily tiny positive r; the exact-recovery result is an asymptotic criterion rather than a characterization of the full transition curve. The experiments outside the model are useful, but they do not extend the theorem. I view these as scope limitations, not flaws in the main statistical claim as precisely stated in Theorem 1.1.
  3. Some comparative empirical conclusions depend on adapted baseline choices. Appendix F fixes a search radius and angular grid for SVD-grid and sets the unspecified regularization multiplier of the convex initializer to one. Such choices are documented, but a limited sensitivity check would make the broad empirical superiority claim more convincing. Figure 7 already shows that the bounded and squared-residual initializers often perform similarly after refinement; the strongest algorithmic justification is therefore the sample-complexity analysis and the more difficult dimensional regimes, rather than a uniform empirical advantage from bounded weighting.
Questions for authors
  1. Can the contraction analysis yield an r-independent polynomial iteration cap attaining the stated risk bound, with early stopping on stable assignments? Please also state the exact stopping rule and cap used in the reported runtime and recovery results.
  2. How sensitive are the SVD-grid and convex-initializer comparisons to a small, prespecified range of grid resolutions/search radii and regularization multipliers? Existing simulation settings should suffice for this clarification.
  3. Could the introduction distinguish order-optimal Hamming risk with an exponential remainder, the exact-recovery criterion, and oracle transition curves more explicitly? Also, which part of the efficient-recovery proof is the main obstacle to extending beyond Gaussian design or two components?
3 comments
AuthorsOpenReview ↗

Response to Reviewer hyUn (Part 1/2)

We thank you for your careful reading and helpful comments. We are happy to engage in further discussion, and our point-by-point responses are detailed below.


W1 & Q1: Practical stopping rule and iteration cap

W1: The practical stopping rule is not fully connected to the stated efficient guarantee. Theorem 1.2 requires K≥⌈5log⁡(1/r)⌉K\ge\lceil5\log(1/r)\rceil even though rr depends on unknown quantities. [...] the remaining question is how long one must wait and how the implemented procedure is covered by the theorem.

Q1: Can the contraction analysis yield an rr-independent polynomial iteration cap attaining the stated risk bound, with early stopping on stable assignments? Please also state the exact stopping rule and cap used in the reported runtime and recovery results.

We agree. In the revised manuscript, we now require K≥min⁡(⌈5log⁡(1/r)⌉,n)K \ge \min(\lceil5\log(1/r)\rceil, n) in Theorem 1.2, so capping at K=nK=n iterations achieves the guarantees without knowing rr.

Moreover, Algorithm 3.1 is an alternating minimization procedure. Once assignments stabilize (z(k+1)=z(k)\mathbf{z}^{(k+1)}=\mathbf{z}^{(k)}), the updates reach a fixed point. All subsequent iterations stay the same. Stopping upon stabilization is therefore exact and covered by the theorem. We have clarified this explicitly in Remark 3.1.

For the experiments, the proposed method stops when the assignments stabilize or after 100 refinement iterations following the initial refit.

W2 & Q3: Scope and model extensions

W2: The scope of "sharp limits" should remain explicit. [...] The Hamming upper bound contains an exponentially small remainder, so it is not a uniform constant-factor equivalence to rr for arbitrarily tiny positive rr; the exact-recovery result is an asymptotic criterion rather than a characterization of the full transition curve. [...]

Q3: Could the introduction distinguish order-optimal Hamming risk with an exponential remainder, the exact-recovery criterion, and oracle transition curves more explicitly?

  • Hamming risk and exact recovery. In finite-sample analysis, the exponentially small term Ce−cnCe^{-cn} reflects the standard design-failure probability. When nr≳1nr\gtrsim 1, recovery is governed by the Hamming risk of order min⁡(1,r)\min(1,r) as the exponential term is negligible. When nr≪1nr\ll 1, the criterion shifts to exact recovery with non-asymptotic failure probability O(nr)+Ce−cnO(nr)+Ce^{-cn}, where the exponential remainder is likewise negligible for exact recovery and does not affect the nr→0nr\to0 threshold. We have made this distinction explicit in the introduction.

  • Oracle transition curve. In our paper, q(r)=arctan⁡(2r)/πq(r) = \arctan(2r)/\pi is the single-membership Bayes error curve for the symmetric oracle problem. The curve q(r)q(r) is plotted primarily as an intuitive visualization. Providing an exact characterization of the finite-sample transition curve is an interesting problem, and we leave it for future work.

Q3: Also, which part of the efficient-recovery proof is the main obstacle to extending beyond Gaussian design or two components?

Extensions beyond Gaussian designs.

Extending our results to general covariates involves two main issues.

  • Algorithmic guarantees. The main challenge is on the algorithmic side, which relies on two properties of Gaussian designs. The first is identifying the contrast direction through a Gaussian Stein-type identity, and the second is using rotational symmetry to control design covariances on wedge-shaped misclassification sets. For non-Gaussian designs, extending the initialization would require either suitable moment identities or another construction, such as truncation, to recover the contrast direction.

  • Statistical limits. The main statistical difficulty is controlling the covariate mass near the decision boundary, which determines how the recovery error depends on rr. For Gaussian covariates, the projected density near zero is bounded and positive, leading to the order-rr risk. Beyond the Gaussian case, heavier mass near zero makes the two components harder to separate even when the noise is small. A natural way to extend the minimax theory is to impose margin conditions on the projected covariates, which quantify the boundary separation and characterize the resulting decay rate in rr.

Extensions to multiple components.

For multiple components, the primary obstacle is initialization. In the two-component setting, a single contrast vector provides a sign rule that immediately yields an initial partition. With K0≥3K_0\ge3 components, the second-moment matrix only identifies the at most (K0−1)(K_0-1)-dimensional span of pairwise contrasts. Turning this subspace into an accurate initial partition requires jointly resolving the individual regression vectors and their memberships. Once a sufficiently good initial clustering is available, we believe the local contraction of hard least-squares refinement can achieve optimal mis-clustering rates.

AuthorsOpenReview ↗

Response to Reviewer hyUn (Part 2/2)

W3 & Q2: Sensitivity of baseline comparisons

W3: Some comparative empirical conclusions depend on adapted baseline choices. Appendix F fixes a search radius and angular grid for SVD-grid and sets the unspecified regularization multiplier of the convex initializer to one. [...] a limited sensitivity check would make the broad empirical superiority claim more convincing.

Q2: How sensitive are the SVD-grid and convex-initializer comparisons to a small, prespecified range of grid resolutions/search radii and regularization multipliers? Existing simulation settings should suffice for this clarification.

Thank you for the suggestion. We evaluated the sensitivity of both initializers to their tuning parameters across the designs of Figure 4, with each method followed by hard least-squares refinement.

To provide a concise summary, Tables 1 and 2 report the performance averaged across the tested range of each column parameter, based on 100 Monte Carlo replications. Columns rr, pp, and nn report the mean mis-clustering error (%), while column nrnr reports the mean exact-recovery probability (%).

Table 1. SVD-grid sensitivity to angular spacing Δθ\Delta\theta and radius multiplier aa, with default (0.3,1)(0.3,1) and search radius a(n−1∑iyi2)1/2a(n^{-1}\sum_i y_i^2)^{1/2}. Entries are percentages averaged across the tested values of each column parameter, reporting mis-clustering error for r,p,nr,p,n and exact-recovery probability for nrnr.

Initializationrrnrnrppnn
Proposed9.8452.8611.286.44
(0.15,0.5)(0.15,0.5)10.7252.5719.847.80
(0.15,1)(0.15,1)10.5752.2919.508.48
(0.15,2)(0.15,2)10.6952.5719.447.77
(0.3,0.5)(0.3,0.5)10.6952.2920.007.91
(0.3,1)(0.3,1)10.7952.0019.418.64
(0.3,2)(0.3,2)10.7152.2919.418.00
(0.6,0.5)(0.6,0.5)10.7752.7120.007.96
(0.6,1)(0.6,1)10.7652.0020.088.59
(0.6,2)(0.6,2)10.5952.2919.197.59

Table 2. Convex initializer sensitivity to the regularization multiplier cc, with default c=0.01c=0.01 and original value c=1c=1. Entries use the same averaging and percentage metrics as Table 1.

Initializationrrnrnrppnn
Proposed9.8452.8611.286.44
c=0c=09.8753.0023.486.41
c=0.01c=0.019.8753.0023.486.40
c=0.05c=0.059.8652.8623.486.40
c=0.1c=0.19.8852.8623.486.45
c=0.25c=0.259.9253.0023.486.66
c=0.5c=0.510.4952.5723.536.81
c=1c=111.7651.8623.607.07

SVD-grid.

Changing the angular spacing and search radius yields similar overall performance for SVD-grid. The proposed method achieves better average performance than all tested parameter choices across the four settings, with particularly clear gains at small nn and large pp.

Convex initializer.

For the convex initializer, we find that using a smaller regularization multiplier improves performance. When varying pp, however, its average mis-clustering error remains higher than that of the proposed method, especially at larger dimensions. The convex method is also more computationally demanding in the experiments.

We have updated all comparisons throughout the paper to adopt the optimized multiplier c=0.01c = 0.01 for the convex formulation initialization. For the sensitivity experiment, full details are included in Appendix G.11.


We once again thank you for your constructive review.

Reviewer_hyUnOpenReview ↗

I will maintain my current score

Thank you for the detailed responses and additional experiments. These largely address my main concerns, and I will maintain my current score.

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

The paper studies recovery of the observed samples' group labels in two-component Gaussian mixed linear regression. With $ r=\sigma ||\beta^\star_+ - \beta^\star_-||_{\Sigma}$ and p≤κnp\leq\kappa n for a sufficiently small constant κ\kappa, it gives minimax bounds of order min⁡(1,r)\min(1,r) and shows that exact recovery is possible if and only if nr→0nr\to0. The proposed method combines a bounded-residual spectral initializer with alternating groupwise least squares and label reassignment. The authors prove finite-sample recovery guarantees with unknown regression coefficients, covariance, and noise level. Simulations examine recovery, running time, and the effect of the initializer.

Critical strengths

A finite-sample guarantee for membership recovery. For the two-component Gaussian model, the paper gives a concrete procedure with expected misclassification error O(r)O(r) and probability of any label error O(nr)O(nr), up to exponentially small remainders, when p+log⁡(en)≤κnp+\log(en)\leq\kappa n. These bounds account for estimated coefficients and nuisance parameters and contain no additional logarithmic factor in the leading membership-error rates. They provide a precise guarantee for the proposed procedure.

Critical weaknesses
  1. The contribution beyond existing EM theory is unclear. EM already estimates memberships through its E-step, with hard labels obtained by assigning each observation to its most likely component. Substantial finite-sample theory already exists for EM in Gaussian mixed linear regression, and some are beyond the authors' citations: [Balakrishnan, Wainwright, and Yu (2017, Corollary 5)]; [Kwon and Caramanis (2020, Theorem 3.2)]; and [Kwon, Ho, and Caramanis (2021, Theorem 1)]. The submission’s initialization and contraction results require r≤r0r\leq r_0 for a sufficiently small constant, placing them in the high-SNR regime studied in this literature. For independent Gaussian observations, coefficient error of order σ\sigma already gives O(r)O(r) nearest-residual classification error for high SNR. The paper should identify what improves over existing guarantees. Without that comparison, it is difficult to judge whether the result resolves a substantial remaining problem or provides a limited refinement.

  2. The comparison with earlier explicit membership bounds is also incomplete. Liu, Liu, and Guo (2023, Theorem 4 and Example 2) already give an asymptotic Gaussian-design classification bound of O(r)O(r) as r→0r\to0. These results already show the order-rr recovery law was already present in earlier work. The paper should distinguish what was already understood about this scale from what its finite-sample analysis adds, and explain why the remaining improvement is substantial.

  3. The practical benefit of the algorithmic change is limited in the reported experiments. The refinement step is standard alternating least squares; the main change is the bounded-residual initializer. The bounded weights support the spectral guarantee when pp is proportional to nn. However, Figure 7(b)–(e) shows similar final recovery for bounded and squared-residual initialization except at the largest dimensions, as the authors acknowledge in Remark 5.2. The experiments also omit EM algorithm, a standard method for this problem. A comparison using the same initialization would help establish whether the hard refinement offers an advantage. The current evidence gives limited support for a practical improvement over existing methods.

Questions for authors
  1. In the shared high-SNR regime, what does Theorem 1.2 add to the membership guarantees obtainable from existing finite-sample EM results and existing membership results [Liu, Liu, and Guo (2023)] ?

  2. Do you have results comparing final membership recovery with EM using matched initialization and stopping rules? How do they compare with the initializer ablation in Figure 7?

4 comments
AuthorsOpenReview ↗

Response to Reviewer bX8x (Part 1/3)

We thank you for the helpful comments, especially for suggesting soft EM for membership recovery. While our hard least-squares refinement can be viewed as hard EM (with equal weights), your comment motivated us to analyze soft EM within our framework and establish the same minimax-optimal membership-recovery rates. Below, we address your comments and questions in detail, and we welcome any further discussion.


Contributions beyond existing finite-sample EM theory (Q1 and W1).

First, for our membership-recovery guarantees, the key distinction lies in the statistical target and problem setup. Indeed, existing EM literature including Balakrishnan et al. (2017), Kwon and Caramanis (2020), Kwon et al. (2021) has established important finite-sample guarantees for parameter estimation in mixed linear regression, typically under conditions such as isotropic designs, symmetric components, or sample splitting across iterations. However, parameter consistency, or even minimax-optimal parameter estimation, does not automatically imply the clustering error guarantees that we seek.

Specifically, we seek to establish in-sample membership recovery for the realized label vector z∗=(z1∗,…,zn∗)\mathbf z^*=(z_1^*,\dots,z_n^*) without sample splitting, where the data are reused for both parameter estimation and label assignment. This is the inferential target arising in subgroup analysis and individualized modeling (such as precision medicine and policy design), for which our minimax lower bound shows that high SNR is statistically necessary for nontrivial recovery, as we elaborate on below.

Regarding Q1, the intuition that an O(σ)O(\sigma) coefficient error directly gives O(r)O(r) classification error holds only for an independent, out-of-sample test point. However, such a parameter bound alone does not yield sharp finite-sample recovery guarantees across the sample due to the coupling between parameter refitting and label errors under in-sample data reuse.

Overcoming this in-sample coupling in the absence of a uniform margin gap is precisely our core technical contribution in Section 4, as also highlighted by the other reviewers. First, because random margins xi⊤θ\mathbf x_i^\top\boldsymbol\theta can fall arbitrarily close to zero, we track a margin-weighted Hamming loss that, as Reviewer 4ozs noted, "adaptively weights the difficult to classify memberships" according to their impact on subsequent refits. Second, as Reviewer hyUn emphasized, combining this margin-weighted contraction with "uniform control over local coefficient pairs, and the separate treatment of in-sample oracle errors addresses the lack of a uniform positive margin and the dependence created by reusing observations," rather than "assuming independently generated iterates or imposing a deterministic separation gap." By decoupling the in-sample oracle errors via a leave-one-out analysis, our proof ensures that estimating unknown parameters introduces no extra cost, yielding the sharp bounds "with no additional logarithmic factor" that you highlighted in the Critical strengths.

AuthorsOpenReview ↗

Response to Reviewer bX8x (Part 2/3)

Statistical motivation (W1).

More broadly, the goal of our paper goes beyond proposing a practical algorithm. We aim to characterize the fundamental limits of group recovery through minimax theory, clarifying when latent memberships can and cannot be reliably learned. In applications that go beyond point prediction, such as subgroup analysis and individualized modeling in precision medicine or policy design [1,2,3], researchers are interested in both the subgroup parameters and the latent label zi∗z_i^* of each observed individual, which indexes a structural regime governing marginal effects and responses to interventions (Ma et al., 2020; Dzemski & Okui, 2024; [4]).

Beyond specific applications, our study is motivated by revisiting a common theoretical premise in the subgroup analysis and individualized modeling literature (Ma & Huang, 2017; Ma et al., 2020; [2,5]). In many existing theoretical analyses, a standard approach is to show that under suitable separation, the oracle estimator (as if true memberships were known) is asymptotically a local minimizer of the objective function (e.g., Ma & Huang, 2017; Ma et al., 2020; [6,5,7,8], just to name a few). Subsequent statistical inference for subgroup parameters is then developed based on this oracle property. In other words, these inferential guarantees implicitly rely on the premise that exact group recovery can be achieved.

In this paper, our goal is precisely to examine the feasibility of this premise in a canonical regression setting. We rigorously demonstrate that under constant noise, exact recovery is intrinsically difficult (requiring nr→0nr\to0). Establishing this fundamental limitation is a primary motivation of our work, and we hope it encourages researchers to incorporate richer, more comprehensive information, such as repeated measurements and complementary data sources, to fundamentally alter these limits. Meanwhile, in the absence of such enriched data, subsequent parameter inference should account for membership mis-clustering.

We plan to incorporate these points in the final version to better communicate this core message.

Reference:

[1] Jared C. Foster, Jeremy M. G. Taylor, Stephen J. Ruberg. Subgroup identification from randomized clinical trial data. Statistics in Medicine, 2011. https://doi.org/10.1002/sim.4322

[2] Juan Shen, Xuming He. Inference for subgroup analysis with a structured logistic–normal mixture model. Journal of the American Statistical Association, 2015. https://doi.org/10.1080/01621459.2014.894763

[3] Susan Athey, Stefan Wager. Policy learning with observational data. Econometrica, 2021. https://doi.org/10.3982/ECTA15732

[4] Wuyi Wang, Peter C. B. Phillips, Liangjun Su. The heterogeneous effects of the minimum wage on employment across states. Economics Letters, 2019. https://doi.org/10.1016/j.econlet.2018.11.002

[5] Xiwei Tang, Fei Xue, Annie Qu. Individualized multidirectional variable selection. Journal of the American Statistical Association, 2021. https://doi.org/10.1080/01621459.2019.1705308

[6] Xiangbin Hu, Jian Huang, Li Liu, Defeng Sun, Xingqiu Zhao. Subgroup analysis in the heterogeneous Cox model. Statistics in Medicine, 2021. https://doi.org/10.1002/sim.8800

[7] Ye He, Ling Zhou, Yingcun Xia, Huazhen Lin. Center-augmented ℓ2\ell_2-type regularization for subgroup learning. Biometrics, 2023. https://doi.org/10.1111/biom.13725

[8] Lu Chen, Xuerong Chen, Xinzhou Guo, Yi Li. Subgroup identification and membership prediction. Biometrics, 2026. https://doi.org/10.1093/biomtc/ujag122

AuthorsOpenReview ↗

Response to Reviewer bX8x (Part 3/3)

Comparison with online classification bounds in Liu et al. [9] (Q1 and W2).

Thank you for pointing out this relevant paper. It is worth noting that Liu et al. [9, Theorem 4 and Example 2] essentially correspond to the oracle experiment in our work. Specifically, they study the asymptotic classification error of a newly arriving point in an online setting where the historical sample size grows to infinity, so that the coefficient parameters have already converged to the truth. In contrast, as discussed above, our goal is the finite-sample recovery of the entire realized membership vector, which involves the distinct technical challenges of in-sample dependence and simultaneous label recovery. Nonetheless, we agree that this is a related work, and we have cited and discussed it in the revised Introduction.

Clarification of Figure 7 and initialization (W3 and Q2).

First, we would like to clarify a misunderstanding regarding Figure 7 in the review. As stated in the paper, Figure 7 is an internal ablation study evaluating the bounded transformation within our proposed initializer, not a comparison against external baselines (which are evaluated across Figures 3 and 4 in Section 6, as well as Appendix G). The bounded transformation is theoretically motivated to ensure valid spectral concentration under p≲np\lesssim n, which explains why its empirical advantages are most visible at the largest dimensions.

More fundamentally, directly estimating the contrast direction via residual-based spectral statistics is a key advantage of our initializer. By yielding an initial partition without reconstructing coefficient components, it avoids several restrictive assumptions for existing initialization methods. For example, existing spectral initializers (e.g., Chaganty and Liang (2013); Yi et al. (2014)) require full-column-rank coefficients to identify regression components, while the convex formulation of Chen et al. (2014) requires the contrast to match the magnitude of the coefficients with near-equal group size. Here, our spectral initialization is invariant to arbitrary common regression components, and the proposed initialization demonstrates considerable improvements over existing baseline initializers.

Soft EM: theoretical extension and additional experiments (W3 and Q2).

We agree that investigating soft EM is an important direction. Motivated by your comment, we extended our theoretical framework to soft EM with posterior-assigned labels and established that it achieves the same local contraction guarantees, matching the minimax upper bounds in Theorem 1.2.

Specifically, Appendix F introduces the soft EM algorithm and establishes the result in Proposition F.1. Correspondingly, we have added a footnote to Algorithm 3.1 in the revised manuscript to reference the extension.

We have also added experiments across the simulation settings comparing soft EM combined with SVD-grid, multi-start random initialization, and our proposed initialization against hard least squares. The results highlight three main findings:

  1. First, under the proposed initialization, soft EM and hard least squares yield nearly indistinguishable performance across balanced settings (see Figures 3--4, 6, and Figure 12 in Appendix G.8), which is consistent with our theoretical guarantees.

  2. Second, across different initializers paired with soft EM, our proposed initializer performs at least as well as the baselines across the tested settings and gives smaller mis-clustering errors as the dimension increases (see Appendix G.8, Figure 12).

  3. Finally, in unbalanced settings (e.g., the 1:3 ratio in Figure 8), soft EM achieves lower mis-clustering error than hard least-squares refinement as its posterior assignments adaptively account for the unequal mixing proportions. By contrast, hard refinement retains slightly higher exact-recovery probability at small nrnr, since this adjustment in soft EM may shift a few observations near the boundary toward the larger group.

Reference:

[9] Yujing Liu, Zhixin Liu, Lei Guo. Global Convergence of Online Identification for Mixed Linear Regression. arXiv:2311.18506, 2023. https://arxiv.org/abs/2311.18506v1


We once again thank you for your constructive review.

Reviewer_bX8xOpenReview ↗

Response to the authors

Thank you for your careful response. Some of my concerns have been addressed; in particular, the distinction from Liu et al. is now clearer. As clarified, the submission strengthens an existing asymptotic O(r)O(r) classification guarantee to uniform finite-sample membership bounds and an exact-recovery characterization. This is a useful addition, particularly in regimes where the dimension grows and the noise level decreases with the sample size. However, the order-rr scaling is already known. I therefore view the main contribution as establishing efficient finite-sample attainment of these rates. While this clarification improves the paper's positioning, it does not alter my overall assessment of the contribution's significance so I would like to maintain the score.

Reviewer_4ozsOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the problem of estimating the latent class labels of a set of individuals under a two-class regression mixture model. They establish several interesting theoretical results. They characterise the minimax error behaviour of the problem, establish conditions for exact recovery, and provide a practical Algorithm that (up to constants) attains the minimax error rates. The Algorithm is shown to behave well under suitable initialisation, which they provide (the spectral procedure), and then demonstrate that the algorithm given such an initialisation will contract in a useful sense. Simulation results against a range of realistic (as far as I can tell) competitors show the Algorithm is fast and effective in practice.

Critical strengths
  • Language is nice, and presentation overall is quite good. Overall I enjoyed reading this paper, despite having to work at it (see negatives) more than I probably would have liked. I liked how the main results of the paper are presented up front. This gave me the big take-away from the paper immediately and set the scene for the rest of exposition nicely. The remarks accompanying the Propositions in Section 2 are excellent and help propel the narrative and keep the reader understanding the argument and flow. The algorithm is clearly presented. This should not be understated, as many papers make their key practical contribution (i.e., the algorithm) difficult to read or parse. I felt I could go away and easily implement Algorithm 3.1.

  • The logical structure of the results themselves is very nice. Theorem 4.1, and the use of the margin-weighted Hamming distance, to adaptively weight the difficult to classify memberships is clever. It is also interesting because it takes into account, in some sense, the impact of misclassifying those observations which are difficult to classify. They are difficult to classify precisely because their linear predictors are so similar, so misclassifying them has potentially less practical impact. Theorem 5.3 and especially Remark 5.4 are excellent. The authors demonstrate a deep understanding of their problem domain and the semantics of the problem itself.

Overall I found this paper to be refreshingly well constructed and coherent. It is clear that the authors put real, substantive time and effort into putting this together and I think that in the current era, this should be highlighted.

Critical weaknesses
  • Despite my previous praise on the overall paper presentation, my main criticism of the paper is how terse it can be in places. It is clear, and well structured, but in the effort to save a few words here and there it loses readability and makes a reader work to read it. A reviewer will make that effort; a general reader may not. So my suggestion would be spend a little time to help the reader keep engaged. Some examples.
  • In the intro, the authors note that exact recovery is possible only if n*r -> 0 (presumably as n -> infty) but the definition of r on the first page does not indicate a dependency on n. It would probably make it clearer to the reader if you explicitly state you study sequences of problems.
  • Theorem 1.2 references "K" but it does not appear in the bounds; in fact, it turns out to be the number of iterations Algorithm 3.1 needs to run. A pretty important "constant"! It would not hurt to flag this symbol as being the number of algorithm iterations in the Theorem for increased clarity.
  • After defining $\Theta_{c_0}$$ it would have been helpful to have a small bit of text interpreting what the object that just got defined actually represents.
  • In Theorem 1.2, a practically important condition is somewhat buried. p + log(en) <= kappa_2 * n, but I could not find any discussion about how big kappa_2 is, or how it depends on c_0. Knowing something about how big this is would give some confidence about the size of problems to which I could apply Algorithm 3.1 and attain the advertised risk bounds.
  • Before (1), the text "For the lower bound" is confusing and suggests you are referring to a previously established lower bound, not the upcoming bound you intend to show. Something like "We now turn to the minimax lower bounds. To establish these, consider the following oracle experiment..." would be easier to parse.

These are small things individually, and not exhaustive, but collectively they detract from an otherwise excellently presented paper, and make the paper much less accessible to those outside the (relatively) small group of specialists who work on this specific problem.

  • The second weakness is simply one of relevance. The results are clearly laid out and the paper does "what it says on the tin", but it is not completely clear to me how relevant the problem of hard-assignment of latent group labels in a two-class regression really is in practice. The authors give some presumably standard examples of this in action, but perhaps a little more motivation as to why hard-assignment is so crucial would be good. I could imagine that soft-assignment of memberships would work perfectly well for many downstream tasks, specifically as the authors point out that misclassification is most likely to occur in those cases where the linear predictors under the two classes are very similar, i.e., the two models make the same prediction about the individual. In this case, does it really matter, practically, if they are mis-classified? The paper itself establishes that exact recovery is not possible under the pretty realistic case of constant presence of noise, so the usefulessness of exact hard assignment is a little unclear.

Note that this does not detract from the aim of studying the conditions under which exact recovery is possible, as done in this paper, but is something the authors should think about.

Questions for authors
  1. A question of terminology, but if I understand correctly from Section 2, profile least-squares treats the regression coefficients as nuisance parameters and the memberships as the parameters of interest, and removes the regression coefficients by profiling them out (LS fits given memberships), then searches for the smallest profile RSS. The profiling here is the technique for removing the nuisance parameters. Is your algorithm also not a form of profiled least-squares as you also use profiling as your nuisance parameter removal technique -- its just an iterative approximate search for the membership vector rather than a brute force search?

  2. Invertibility is required, which I assume the above referenced condition helps guarantee, but a question to the authors would be: could the same algorithm be implemented using ridge-regression (or some penalized regression schema) in place of the least-squares estimates?

  3. A small question; Theorem 1 is labelled as an "information-theoretic limit" but I might suggest "minimax recovery limit" as a slightly more transparent name?

5 comments
AuthorsOpenReview ↗

Response to Reviewer 4ozs (Part 1/4)

We thank you for your thorough review and constructive comments. Your suggestions on improving the presentation, as well as your comments on hard assignments, have provided valuable perspectives for refining the paper. We are happy to engage in further discussion, and our point-by-point responses are detailed below.


W1: Terse exposition

[...] my main criticism of the paper is how terse it can be in places. [...] in the effort to save a few words here and there it loses readability and makes a reader work to read it. [...] So my suggestion would be spend a little time to help the reader keep engaged.

Thanks for pointing this out. Accordingly, we have made revisions to improve clarity below. Meanwhile, we have made initial edits across the manuscript to improve readability and plan to refine it further going forward.

In the intro, [...] the definition of rr on the first page does not indicate a dependency on nn. It would [...] make it clearer to the reader if you explicitly state you study sequences of problems.

We agree and have added a footnote right after defining θ\boldsymbol{\theta}, Λ\Lambda, and r=σ/Λr = \sigma/\Lambda in the intro.

Theorem 1.2 references KK but it does not appear in the bounds; [...] It would not hurt to flag this symbol as being the number of algorithm iterations in the Theorem for increased clarity.

Good point. We have flagged KK as the number of algorithm iterations in Theorem 1.2 and the corresponding corollary.

After defining Θc0\Theta_{c_0} it would have been helpful to have a small bit of text interpreting what the object that just got defined actually represents.

We have added an explanation right after the definition of Θc0\Theta_{c_0} to describe what this set represents.

In Theorem 1.2, [...] I could not find any discussion about how big κ2\kappa_2 is, or how it depends on c0c_0. Knowing something about how big this is would give some confidence about the size of problems to which I could apply Algorithm 3.1 and attain the advertised risk bounds.

This is an important point. In the original version, we treated c0c_0 as fixed without tracking its dependence. We revisited the proofs and found that κ2\kappa_2 can be chosen as c⋅c02c\cdot c_0^2 for an absolute constant cc. (We believe the quadratic dependence can be improved to linear by allowing a few transition steps instead of entering the contraction region in a single refit. We omit it to keep the paper focused.)

Specifically, conditioning the smaller group's Gram matrix requires p≲c0np \lesssim c_0 n. The quadratic dependence mainly arises from the spectral initialization and the initial refit that brings the estimates into the contraction region. The population eigengap is of order c0c_0, and tracking empirical spectral concentration together with the first-refit error leads to this dependence. Correspondingly, we have added a footnote to Theorem 1.2 to clarify the dependence and referenced the derivation in Appendix E.7, where we derive it via a few modifications.

At the same time, we acknowledge that obtaining a sharp constant for κ2\kappa_2 is technically hard with non-asymptotic bounds, and we do not intend to optimize the constant in the paper. In the in-sample analysis, controlling uniform empirical processes over data-dependent assignment regions relies on worst-case covering number and VC-type arguments, which introduce conservative constants. In practice, our experiments reveal reliable recovery for ratios up to p/(c0n)≈0.3p/(c_0 n) \approx 0.3, degrading as pp approaches the smaller group size c0nc_0 n.

Before (1), the text "For the lower bound" is confusing [...]. Something like "We now turn to the minimax lower bounds. To establish these, consider the following oracle experiment..." would be easier to parse.

Thank you for this suggestion. We have adopted your recommended wording.

AuthorsOpenReview ↗

Response to Reviewer 4ozs (Part 2/4)

W2: Motivation for hard assignment and exact recovery

[...] perhaps a little more motivation as to why hard-assignment is so crucial would be good. I could imagine that soft-assignment of memberships would work perfectly well for many downstream tasks [...]. In this case, does it really matter, practically, if they are mis-classified? The paper itself establishes that exact recovery is not possible under the pretty realistic case of constant presence of noise, so the usefulessness of exact hard assignment is a little unclear.

We appreciate your thoughtful comment, which gets to the core message of the paper. We address it from three complementary perspectives.

Why is hard membership assignment relevant in practice, even near the boundary?

Beyond predicting yiy_i at xi\mathbf{x}_i, zi∗z_i^* often corresponds to a structural regime that determines marginal effects and counterfactual responses to interventions (Ma et al., 2020; Dzemski & Okui, 2024; [1]). For an individual, even if xi⊤θ≈0\mathbf{x}_i^\top\boldsymbol{\theta} \approx 0 due to component cancellation, the change in response Δx⊤θ\Delta\mathbf{x}^\top\boldsymbol{\theta} can still be substantial under a covariate shift or intervention xi↦xi+Δx\mathbf{x}_i \mapsto \mathbf{x}_i + \Delta\mathbf{x}. In applications such as precision medicine or policy design [2,3,4], an explicit group assignment is often needed to select a discrete action, so mis-clustering can result in suboptimal or even negative decisions, especially under qualitative interactions where the preferred decision reverses across subgroups [5].

Does misclassifying boundary observations matter for prediction, and how should unavoidable boundary ambiguity under noise be treated?

At the same time, we completely agree with you that if the goal is prediction of yiy_i at xi\mathbf{x}_i, misclassifying observations with xi⊤(β+∗−β−∗)≈0\mathbf{x}_i^\top(\boldsymbol{\beta}_+^* - \boldsymbol{\beta}_-^*) \approx 0 barely changes the fitted value (which is why our local analysis uses the margin-weighted Hamming loss). Under the cross-sectional setting studied here, our goal is not to force correct hard recovery on these ambiguous boundary points. On the contrary, as emphasized in the discussion, when small-margin misclassifications are inevitable under noise, one should explicitly account for the uncertainty. This can be done, for instance, by constructing membership confidence sets (Dzemski & Okui, 2024).

Reference:

[1] Wuyi Wang, Peter C. B. Phillips, Liangjun Su. The heterogeneous effects of the minimum wage on employment across states. Economics Letters, 2019. https://doi.org/10.1016/j.econlet.2018.11.002

[2] Jared C. Foster, Jeremy M. G. Taylor, Stephen J. Ruberg. Subgroup identification from randomized clinical trial data. Statistics in Medicine, 2011. https://doi.org/10.1002/sim.4322

[3] Min Qian, Susan A. Murphy. Performance guarantees for individualized treatment rules. The Annals of Statistics, 2011. https://doi.org/10.1214/10-AOS864

[4] Susan Athey, Stefan Wager. Policy learning with observational data. Econometrica, 2021. https://doi.org/10.3982/ECTA15732

[5] M. Gail, R. Simon. Testing for qualitative interactions between treatment effects and patient subsets. Biometrics, 1985. https://doi.org/10.2307/2530862

AuthorsOpenReview ↗

Response to Reviewer 4ozs (Part 3/4)

Given that exact recovery is impossible under constant noise, why study the limits of hard assignment and exact recovery?

Beyond specific applications, the paper is motivated by revisiting a common theoretical premise in the subgroup analysis and individualized modeling (Ma & Huang, 2017; Ma et al., 2020; [6,7]). In many existing analyses, a standard way is to show that under suitable separation, the oracle estimator (computed with known true memberships) is asymptotically a local minimizer of the objective function (e.g., Ma & Huang, 2017; Ma et al., 2020; [8,7,9,10], just to name a few). Subsequent statistical inference for subgroup parameters is then established upon the oracle property. In other words, these results implicitly rely on the premise that exact group recovery can be achieved.

In this paper, our goal is to examine the feasibility of the premise in a canonical setting. We demonstrate that under constant noise, exact recovery is intrinsically difficult (requiring nr→0nr \to 0). Establishing this limitation is a primary motivation of our work. As we emphasize in the discussion, we hope it motivates researchers to incorporate richer, more comprehensive information, such as repeated measurements and complementary data sources, to fundamentally alter these limits. Meanwhile, in the absence of such enriched data, subsequent parameter inference should account for membership mis-clustering.

We plan to appropriately incorporate these points in the final version to better communicate the message.

Q1: Profile least-squares terminology

[...] The profiling here is the technique for removing the nuisance parameters. Is your algorithm also not a form of profiled least-squares as you also use profiling as your nuisance parameter removal technique -- its just an iterative approximate search for the membership vector rather than a brute force search?

Yes, your observation is completely correct. For the joint objective function

L(z,β+,β−)=∑b∈+,−∑i∈Ib(z)(yi−xi⊤βb)2,\mathcal{L}(\mathbf{z}, \boldsymbol{\beta}_+, \boldsymbol{\beta}_-) = \sum_{b \in \\{+,-\\}} \sum_{i \in I_b(\mathbf{z})} (y_i - \mathbf{x}_i^\top \boldsymbol{\beta}_b)^2,

minimizing over (β+,β−)(\boldsymbol{\beta}_+, \boldsymbol{\beta}_-) for a fixed z\mathbf{z} yields RSS(z)\mathrm{RSS}(\mathbf{z}). The estimator in Section 2 is the exact (combinatorial) profile least-squares estimator over the feasible set of assignments.

The hard least-squares refinement in Algorithm 3.1 implements alternating minimization on the objective function. Specifically, it alternates between updating the regression coefficients given the assignments and updating the assignments given the coefficients. It shares the same spirit as Lloyd's algorithm for kk-means clustering, and can be viewed as hard EM with equal mixing weights. At each step, the profile objective is non-increasing, satisfying

RSS(z(k+1))≤L(z(k+1),γ+(k),γ−(k))≤L(z(k),γ+(k),γ−(k))=RSS(z(k)).\mathrm{RSS}(\mathbf{z}^{(k+1)}) \le \mathcal{L}(\mathbf{z}^{(k+1)}, \boldsymbol{\gamma}_+^{(k)}, \boldsymbol{\gamma}_-^{(k)}) \le \mathcal{L}(\mathbf{z}^{(k)}, \boldsymbol{\gamma}_+^{(k)}, \boldsymbol{\gamma}_-^{(k)}) = \mathrm{RSS}(\mathbf{z}^{(k)}).

Reference:

[6] Juan Shen, Xuming He. Inference for subgroup analysis with a structured logistic–normal mixture model. Journal of the American Statistical Association, 2015. https://doi.org/10.1080/01621459.2014.894763

[7] Xiwei Tang, Fei Xue, Annie Qu. Individualized multidirectional variable selection. Journal of the American Statistical Association, 2021. https://doi.org/10.1080/01621459.2019.1705308

[8] Xiangbin Hu, Jian Huang, Li Liu, Defeng Sun, Xingqiu Zhao. Subgroup analysis in the heterogeneous Cox model. Statistics in Medicine, 2021. https://doi.org/10.1002/sim.8800

[9] Ye He, Ling Zhou, Yingcun Xia, Huazhen Lin. Center-augmented ℓ2\ell_2-type regularization for subgroup learning. Biometrics, 2023. https://doi.org/10.1111/biom.13725

[10] Lu Chen, Xuerong Chen, Xinzhou Guo, Yi Li. Subgroup identification and membership prediction. Biometrics, 2026. https://doi.org/10.1093/biomtc/ujag122

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.