## Abstract

We study the problem of learning a mixture of two subspaces over F^{n}_{2} . The goal is to recover the individual subspaces A_{0}, A_{1}, given samples from a (weighted) mixture of samples drawn uniformly from the subspaces A_{0} and A_{1}. This problem is computationally challenging, as it captures the notorious problem of “learning parities with noise” in the degenerate setting when A_{1} ⊆ A_{0}. This is in contrast to the analogous problem over the reals that can be solved in polynomial time (Vidal’03). This leads to the following natural question: is Learning Parities with Noise the only computational barrier in obtaining efficient algorithms for learning mixtures of subspaces over F^{n}_{2}? The main result of this paper is an affirmative answer to the above question. Namely, we show the following results: 1. When the subspaces A_{0} and A_{1} are incomparable, i.e., A_{0} 6⊆ A_{1} and A_{1} 6⊆ A_{0}, then there is a polynomial time algorithm to recover the subspaces A_{0} and A_{1}. 2. In the case when A_{1} ⊆ A_{0} such that dim(A_{1}) ≤ α · dim(A_{0}) for α < 1, there is a n^{O}(1/^{(1-α))} time algorithm to recover the subspaces A_{0} and A_{1}. Thus, our algorithms imply computational tractability of the problem of learning mixtures of two subspaces, except in the degenerate setting captured by learning parities with noise.

Original language | English (US) |
---|---|

Pages (from-to) | 481-504 |

Number of pages | 24 |

Journal | Proceedings of Machine Learning Research |

Volume | 132 |

State | Published - 2021 |

Event | 32nd International Conference on Algorithmic Learning Theory, ALT 2021 - Virtual, Online Duration: Mar 16 2021 → Mar 19 2021 |

## Keywords

- learning parities with noise
- mixture models
- subspaces

## ASJC Scopus subject areas

- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability