acceptodds
Under review as a conference paper at ICLR 2027

Robust Composite Recovery for Two-Component Mixed Linear Regression

Abstract

Mixed linear regression (MLR) models heterogeneous populations through multiple linear relationships with unobserved component memberships, with broad applications across market segmentation, trajectory clustering, and signal unmixing. A fundamental challenge in robust MLR is to reliably recover the underlying regression coefficients in the presence of both structured inlier noise and a small fraction of arbitrarily large response outliers, while providing rigorous finite-sample guarantees. We study the canonical two-component MLR setting with Gaussian covariates and component proportions bounded away from zero. We propose SARP-P (Segment-initialized Adaptive Robust Prox-linear estimation with Polishing), a complete estimator that unifies segment initialization, normalized composite iteration, and residual-calibrated response polishing in a single pipeline. With a sample size nearly linear in the covariate dimension, we establish a full finite-sample recovery guarantee: Provably correct initialization, a quadratic error recursion converging to an explicit noise floor, and valid recovery of the final polished estimate. Our bounds tolerate a bounded fraction of arbitrary response outliers independent of their amplitudes, and hold uniformly across all data-dependent adaptive weights and trimming steps. All stages of the estimator reuse the same observations, and all guarantees hold under a single high-probability event. A computable data-driven acceptance rule transfers recovery guarantees to the final polished estimate without requiring a known noise scale. Synthetic experiments demonstrate that response polishing improves estimation accuracy, with particularly strong gains under scale-mixture noise with response outliers.

Primary area:
learning theory
Keywords:
Mixed linear regression, composite optimization, robustness

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9EkUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies two-component mixed linear regression with Gaussian design where, on top of independent noise, a small fraction of responses can be replaced arbitrarily, and proposes a three-stage estimator, SARP-P. It initializes by locating the segment between the two coefficients (LAD, a spectral direction estimate, then a grid search for the endpoints). The core is a trimmed prox-linear iteration on the product-of-residuals loss with each term normalized by roughly the sum of its absolute residuals, because in MLR a corrupted response also enters the derivative and would otherwise dominate the local model. A calibrated Huber/Tukey IRLS step then polishes the estimate and is kept only if it passes a check on the composite objective. With n of order d up to logs, the analysis, built on a local growth bound that is uniform over the adaptive weights and trimming, gives correct initialization, quadratic convergence to an error floor set by a noise quantile, and a similar bound after polishing, all without sample splitting. Synthetic experiments show SARP-P is competitive with or better than existing robust methods, especially under scale-mixture noise.

Critical strengths

The core theory is correct and promising. All 360 primary trials are kept, the large failures are disclosed instead of filtered.

Critical weaknesses
  • The guarantee does not reach the algorithm that is evaluated, and gives no statistical rate. At p0=0.2,a=0.1p_0=0.2, a=0.1 the construction in (176)-(181) gives δg≤2.5×10−16\delta_{\mathrm{g}} \leq 2.5 \times 10^{-16} vs. 0.05 used; r/τ≈10−8r / \tau \approx 10^{-8} vs. 2 used; ϵ0≈5×10−51\epsilon_0 \approx 5 \times 10^{-51} vs. 5% contamination; s0≈10−48s_0 \approx 10^{-48} vs. s=0.01−0.1s=0.01-0.1. The point is not loose constants, i.e. rr is the ball the whole local argument lives on, and Table 5 shows the practical initializer at error ≈0.3\approx 0.3 (at Δ=1\Delta=1 ) being corrected by the composite stage to ≈0.004\approx 0.004 -0.016, whereas the theorem certifies an initializer already within ∼10−8τ\sim 10^{-8} \tau of the truth. These are different procedures. On top of that, the floor 12u/μ12 u / \mu in (26) uses a noise quantile; uG=u_{\mathrm{G}}= v2log⁡(4/ω)v \sqrt{2 \log (4 / \omega)} is constant in nn, and without spare budget uu grows like log⁡n\sqrt{\log n}. So even on the clean, well-separated Gaussian subclass, where Chen-Yi-Caramanis give vd/nv \sqrt{d / n}, nothing here shrinks with nn; "quadratic convergence" is an envelope et+1≤Aet2+be_{t+1} \leq A e_t^2+b, not convergence. The abstract's "complete estimator with full finite-sample guarantee" may oversell what is proved in this work.

  • Theorem 4.2 only preserves a bound for any proposal passing the guard, which tolerates F(z)≤F(c)+s^F(\boldsymbol{z}) \leq F(\boldsymbol{c})+\widehat{s}, it's a noise-scale increase; so it says nothing about E(z)≤E(c)\mathcal{E}(\boldsymbol{z}) \leq \mathcal{E}(\boldsymbol{c}). Appendix E analyzes known labels and true errors, not the fitted nearest-component residuals actually used; and the equal-prior Huber objective is not stationary at the truth under imbalance: in 1-D with a common shift tt, \begin{equation*} R^{\prime}(0)=-(2 p-1) A, ~~A>0, \end{equation*} so descent can be toward a biased point. Taken together, the theory is about the composite stage, the gains are from polishing, and neither supports the other.

Questions for authors
  • is there any certified regime that overlaps the experiments, or a computable diagnostic that verifies basin entry for a practical run? If not, should Theorems 4.1-4.2 be read as existence results for the method class rather than guarantees for SARP-P as run?

  • Can the technique give a shrinking stochastic term on any subclass (e.g. uncontaminated Gaussian noise, large Δ/v\Delta / v), or is there a structural obstruction in treating all errors as bounded deterministic perturbations?

  • Could authors report segment-init -> polishing (composite skipped) and Mix-IRLS -> polishing on the four primary settings. If either recovers most of the gain, the composite stage needs a different justification

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

The paper proposes SARP-P for two-component mixed linear regression with independent inlier noise and a bounded fraction of arbitrary response outliers. It combines segment-based initialization, a trimmed and derivative normalized prox-linear update, and data-calibrated response polishing. Its main theoretical contribution is a single high-probability, finite-sample guarantee covering initialization, a quadratic local error recursion down to a noise floor, and recovery of the guarded final output, despite reusing the same data for adaptive weights and trimming. Synthetic comparisons with four robust baselines show polishing gains.

Critical strengths

The analysis covers initialization, adaptive trimming, normalized updates, and the guarded output. Its bound holds even when the adversary replaces responses by arbitrary values. All stages reuse the same data. Controlling every fitted weight and retained subset on one event is a substantive result.

Critical weaknesses

The practical evidence is narrow relative to the cost. SARP-P takes 1.230 seconds per fit, versus 0.0137 for Mix-IRLS, this is about 90 times longer (Appendix Table 3). Mix-IRLS starts from a random pair, while several other baselines receive SARP-P's initializer. Tests across dimensions, sample sizes, mixture proportions, and outlier fractions would better establish the method's practical range. The methods should also be compared under a shared compute budget.

Questions for authors

How do coefficient error and initialization failures change with n/d, mixture proportion, and contamination? Please also compare methods under a shared runtime or restart budget. Giving Mix-IRLS the same segment initializer would help isolate the gains from the core update and polishing.

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

The paper studies two-component mixed linear regression with Gaussian covariates, inlier noise and adversarial response outliers. The proposed method, SARP-P, combines segment initialization, normalized composite iteration and Huber/Tukey polishing. Theorem 4.1 gives initialization and local convergence guarantees, while Theorem 4.2 bounds the final estimation error. Experiments compare the method with robust regression baselines under different noise distributions.

Critical strengths
  • The analysis covers initialization, refinement and the final output while reusing the same observations.
  • Table 1 also shows an appreciable improvement under scale-mixture noise.
Critical weaknesses
  • As per my understanding, the bounds in Theorems 4.1-4.2 are very conservative. For p0=0.2p_0=0.2, a=0.1a=0.1 reported in line 456, the sufficient contamination threshold in Eq.(180) is about 5×10−515\times10^{-51}, whereas the experiments use 5% contamination (line 448). The authors also mention in lines 458-459 that the practical grid and radius are not covered by Theorem 4.1. What do these guarantees tell us about the method in a practically relevant setting?

  • Can the authors compare their work to the following related works:

  1. Karmalkar S, Klivans A, Kothari P. List-decodable linear regression. Advances in neural information processing systems. 2019;32.
  2. Raghavendra P, Yau M. List decodable learning via sum of squares. SODA 2020
  3. Wang N, Zhang X, Mai Q. Statistical analysis for a penalized EM algorithm in high-dimensional mixture linear regression model. JMLR 2024
  • In lines 43-45, the authors motivate consistent recovery. Is the proposed estimator consistent? In line 391, the authors say "The resulting quantile-dependent floors do not establish a vanishing stochastic estimation rate."

  • The primary experiments use n=1000n=1000, d=20d=20 (line 444) and 5% contamination (line 448). I would also like to see how the estimation error changes with sample size, dimension and the actual outlier fraction.

Questions for authors
  • Can the sufficient constants be improved enough to cover the contamination level and practical parameters used in the experiments?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.