# Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 33 references that are in the map.
- First posted on arXiv 13 Nov 2023.

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

- [Learning Mixtures of Gaussians in High Dimensions](https://mlsanity.com/paper/1503.00424/) (2015)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid](https://mlsanity.com/paper/1811.01816/) (2018)
- [Learning sums of powers of low-degree polynomials in the non-degenerate case](https://mlsanity.com/paper/2004.06898/) (2020)
- [Polynomial-Time Power-Sum Decomposition of Polynomials](https://mlsanity.com/paper/2208.00122/) (2022)

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

- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)

## Abstract (arXiv)

We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal and Saha (FOCS 20), who designed such a framework for learning arithmetic circuits without any noise. A key ingredient of our meta algorithm is an efficient algorithm for a novel problem called Robust Vector Space Decomposition. We show that our meta algorithm works well when certain matrices have sufficiently large smallest non-zero singular values. We conjecture that this condition holds for smoothed instances of our problems, and thus our framework would yield efficient algorithms for these problems in the smoothed setting.