Sample Complexity of Learning Mixture of Sparse Linear Regressions.

Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata PalNeurIPS 2019 · OpenReview

Introduction

In standard linear regression, the goal is to find a single vector $\beta$ that maps inputs $x$ to outputs $y$. However, real-world data is often generated by a mixture of underlying relationships. Consider a medical study where patients belong to $L$ distinct sub-groups, each characterized by a unique genetic signature ($\beta^{(1)}, \dots, \beta^{(L)}$). When a measurement is taken, the sub-group identity is unknown, yielding a noisy observation $y = \langle x, \beta^{(\ell)} \rangle + \eta$.

This problem is significantly compounded when the underlying signals are sparse (most entries are zero), bridging the challenges of mixture models and compressed sensing. Historically, research in this domain has been constrained: algorithms either required restrictive "overlap" assumptions—dictating that signals could not share similar values at the same indices—or were strictly limited to mixtures of exactly two signals ($L=2$) in noisy environments.

This paper breaks through these barriers, introducing novel algorithms and theoretical bounds for learning multiple sparse signal vectors from a mixed stream of linear measurements. It achieves near-optimal sample complexity and provides the first robust reconstruction method for mixtures of more than two signals without relying on restrictive overlap assumptions.

Algorithmic Frameworks

The authors tackle the problem by dividing it into two distinct regimes: the noiseless case and the noisy case.

The Noiseless Case: Sparse Polynomials and Sorting

To recover $L$ signals without noise, the primary obstacle is "alignment"—determining which measurement corresponds to which signal across different queries. The authors leverage Vandermonde matrices (a class of Maximum Distance Separable matrices) to treat the inner product of a query and a signal as a polynomial.

The key insight here relies on the power of randomness in polynomials: the difference between two sparse signals is itself a sparse polynomial, which inherently has very few roots. The authors prove that by selecting a random evaluation point, the signals maintain a consistent sorted order. This allows the algorithm to effectively "unmix" the measurements simply by sorting them, acting as a reliable anchor across queries.

The Noisy Case: GMMs and Error Correction

When noise is introduced, simple sorting breaks down. To overcome this, the authors propose a robust three-step pipeline:

  1. Denoising via Gaussian Mixture Models (GMMs): By repeatedly querying the same vector, the authors transform the regression problem into a distribution learning problem. Multiple queries of the same vector are treated as a GMM. Using complex-analytic techniques, they can accurately estimate the underlying inner products.
  2. Alignment via Error-Correcting Codes: To link these inner products across different query vectors, the authors creatively apply algebraic coding theory. They perform redundant queries (e.g., querying $x_i$, $x_j$, and their sum $x_i + x_j$) to establish "parity checks." These checks reveal which values belong to the same underlying signal vector, bypassing the need for prior overlap assumptions.
  3. Recovery via Basis Pursuit: Once the measurements are successfully denoised and aligned, standard Basis Pursuit—a staple convex optimization tool from compressed sensing—is used to reconstruct the final sparse vectors.

Key Theoretical Results

As a purely theoretical work, the paper focuses on establishing rigorous sample complexity guarantees rather than empirical benchmarks.

  • Near-Optimal Noiseless Complexity: The authors demonstrate that $O(kL \log(kL))$ queries are sufficient to recover all $L$ signals of sparsity $k$. They also prove a lower bound of $\Omega(kL)$ queries, establishing that their noiseless algorithm is nearly optimal in terms of measurement efficiency. Crucially, this works for any set of sparse vectors.
  • Robust Noisy Complexity: For the noisy regime, the paper introduces the first robust algorithm for $L > 2$ signals. It requires $O(k \log^3 n \cdot \exp((\sigma/\epsilon)^{2/3}))$ queries. While the exponential dependence on the noise-to-error ratio appears steep, it represents a massive theoretical improvement over the $\exp(1/\epsilon)$ dependencies found in prior $L=2$ literature.

Limitations and Future Directions

While the proposed algorithms are highly sample-efficient, they come with practical trade-offs. The noisy reconstruction step relies on learning Gaussian mixtures, which can be computationally expensive to execute. Furthermore, the current noisy analysis assumes the number of signals $L$ is a constant; as $L$ scales, the complexity becomes significantly harder to manage.

Finally, the paper primarily investigates non-adaptive queries, where all input vectors $x$ are chosen upfront. The authors suggest that exploring adaptive queries—where the next $x$ is chosen based on previous $y$ observations—could further reduce the required number of measurements, presenting a promising avenue for future research.

Summary updated

Abstract

In the problem of learning mixtures of linear regressions, the goal is to learn a col-lection of signal vectors from a sequence of (possibly noisy) linear measurements,where each measurement is evaluated on an unknown signal drawn uniformly fromthis collection. This setting is quite expressive and has been studied both in termsof practical applications and for the sake of establishing theoretical guarantees. Inthis paper, we consider the case where the signal vectors aresparse; this generalizesthe popular compressed sensing paradigm. We improve upon the state-of-the-artresults as follows: In the noisy case, we resolve an open question of Yin et al. (IEEETransactions on Information Theory, 2019) by showing how to handle collectionsof more than two vectors and present the first robust reconstruction algorithm, i.e.,if the signals are not perfectly sparse, we still learn a good sparse approximationof the signals. In the noiseless case, as well as in the noisy case, we show how tocircumvent the need for a restrictive assumption required in the previous work. Ourtechniques are quite different from those in the previous work: for the noiselesscase, we rely on a property of sparse polynomials and for the noisy case, we providenew connections to learning Gaussian mixtures and use ideas from the theory of
BibTeX
@inproceedings{krishnamurthy2019sample,
  author = {Akshay Krishnamurthy and Arya Mazumdar and Andrew McGregor and Soumyabrata Pal},
  title = {{Sample Complexity of Learning Mixture of Sparse Linear Regressions.}},
  booktitle = {NeurIPS},
  year = {2019},
  url = {https://openreview.net/forum?id=JLSuPH8KCoux},
}
Figure