# Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation

arXiv: https://arxiv.org/abs/2206.01167 · HTML: https://mlsanity.com/paper/2206.01167/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 2 Jun 2022.

## Builds on (most cited first, 5 of 5)

- [Spectral Experts for Estimating Mixtures of Linear Regressions](https://mlsanity.com/paper/1306.3729/) (2013)
- [Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximization](https://mlsanity.com/paper/1704.08231/) (2017)
- [Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm](https://mlsanity.com/paper/1405.2936/) (2014)
- [Alternating Minimization Converges Super-Linearly for Mixed Linear Regression](https://mlsanity.com/paper/2004.10914/) (2020)
- [Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem](https://mlsanity.com/paper/2102.09704/) (2021)

## Built on by (most cited first, 4 of 4)

- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Outlier-robust Estimation of a Sparse Linear Model Using Invexity](https://mlsanity.com/paper/2306.12678/) (2023)
- [Invex Programs: First Order Algorithms and Their Convergence](https://mlsanity.com/paper/2307.04456/) (2023)

## Abstract (arXiv)

In this paper, we study the problem of sparse mixed linear regression on an unlabeled dataset that is generated from linear measurements from two different regression parameter vectors. Since the data is unlabeled, our task is not only to figure out a good approximation of the regression parameter vectors but also to label the dataset correctly. In its original form, this problem is NP-hard. The most popular algorithms to solve this problem (such as Expectation-Maximization) have a tendency to stuck at local minima. We provide a novel invex relaxation for this intractable problem which leads to a solution with provable theoretical guarantees. This relaxation enables exact recovery of data labels. Furthermore, we recover a close approximation of the regression parameter vectors which match the true parameter vectors in support and sign. Our formulation uses a carefully constructed primal dual witnesses framework for the invex problem. Furthermore, we show that the sample complexity of our method is only logarithmic in terms of the dimension of the regression parameter vectors.