Fetching the paper…
Reading the bibliography…
We give a new algorithm for learning mixtures of $k$ Gaussians (with identity covariance in $\mathbb{R}^n$) to TV error $\varepsilon$, with quasi-polynomial ($O(n^{\text{poly\,log}\left(\frac{n+k}{\varepsilon}\right)})$) time and sample complexity, under a minimum weight assumption.
Dynamical theories of Brownian motion
Nelson, E. (1967) · 1967
Earlier work this paper cites.
Approximation algorithms for combinatorial problems
Johnson, D. S. (1973) · 1973
Earlier work this paper cites.
Some inequalities for the distribution of sums of independent random variables
Nagaev, S. and Pinelis, I. (1978) · 1978
Earlier work this paper cites.
Reverse-time diffusion equation models
Anderson, B. D. (1982) · 1982
Earlier work this paper cites.
Statistical analysis of finite mixture distributions
Titterington, D. M., Smith, A. F., and Makov, U. E. (1985) · 1985
Earlier work this paper cites.
An empirical bayes approach to statistics
Robbins, H. E. (1992) · 1992
Earlier work this paper cites.
Noise sensitivity of boolean functions and applications to percolation
Benjamini, I., Kalai, G., and Schramm, O. (1999) · 1999
Earlier work this paper cites.
A two-round variant of em for gaussian mixtures
Dasgupta, S. and Schulman, L. J. (2000) · 2000
Earlier work this paper cites.
The best constant in the Rosenthal inequality for nonnegative random variables
Ibragimov, R. and Sharakhmetov, S. (2001) · 2001
Earlier work this paper cites.
Optimal estimation of high-dimensional location gaussian mixtures
Doss, N., Wu, Y., Yang, P., and Zhou, H. H. (2020) · 2002
Earlier work this paper cites.
Learning intersections and thresholds of halfspaces
Klivans, A. R., O’Donnell, R., and Servedio, R. A. (2004) · 2004
Earlier work this paper cites.
A spectral algorithm for learning mixture models
Vempala, S. and Wang, G. (2004) · 2004
Earlier work this paper cites.
Learning mixtures of separated nonspherical gaussians
Arora, S. and Kannan, R. (2005) · 2005
Earlier work this paper cites.
Agnostically learning halfspaces
Kalai, A. T., Klivans, A. R., Mansour, Y., and Servedio, R. A. (2008) · 2008
Earlier work this paper cites.
Learning geometric concepts via gaussian surface area
Klivans, A. R., O’Donnell, R., and Servedio, R. A. (2008) · 2008
Earlier work this paper cites.
Settling the polynomial learnability of mixtures of gaussians
Moitra, A. and Valiant, G. (2010) · 2010
Earlier work this paper cites.
Mean field models for spin glasses: Volume I: Basic examples
Talagrand, M. (2010) · 2010
Earlier work this paper cites.
A connection between score matching and denoising autoencoders
Vincent, P. (2011) · 2011
Earlier work this paper cites.
Thin shell implies spectral gap up to polylog via a stochastic localization scheme
Eldan, R. (2013) · 2013
Earlier work this paper cites.
Deep unsupervised learning using nonequilibrium thermodynamics
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. (2015) · 2015
Earlier work this paper cites.
Sample-optimal density estimation in nearly-linear time
Acharya, J., Diakonikolas, I., Li, J., and Schmidt, L. (2017) · 2017
Cited alongside, same era.
Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures
Diakonikolas, I., Kane, D. M., and Stewart, A. (2017) · 2017
Cited alongside, same era.
On learning mixtures of well-separated gaussians
Regev, O. and Vijayaraghavan, A. (2017) · 2017
Cited alongside, same era.
Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes
Ashtiani, H., Ben-David, S., Harvey, N., Liaw, C., Mehrabian, A., and Plan, Y. (2018) · 2018
Cited alongside, same era.
Mixture models, robustness, and sum of squares proofs
Hopkins, S. B. and Li, J. (2018) · 2018
Cited alongside, same era.
Robust moment estimation and improved clustering via sum of squares
Clustering mixtures with almost optimal separation in polynomial time
Liu, A. and Li, J. (2022) · 2022
Later among the works it cites.
Linear convergence bounds for diffusion models via stochastic localization
Benton, J., De Bortoli, V., Doucet, A., and Deligiannidis, G. (2023) · 2023
Later among the works it cites.
On learning gaussian multi-index models with gradient flow
Bietti, A., Bruna, J., and Pillaud-Vivien, L. (2023) · 2023
Later among the works it cites.
Generative diffusion in very large dimensions
Biroli, G. and Mézard, M. (2023) · 2023
Later among the works it cites.
Analysis of learning a flow-based generative model from limited sample complexity
Cui, H., Krzakala, F., Vanden-Eijnden, E., and Zdeborová, L. (2023) · 2023
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Kothari, P. K., Steinhardt, J., and Steurer, D. (2018) · 2018
Cited alongside, same era.
Generative modeling by estimating gradients of the data distribution
Song, Y. and Ermon, S. (2019) · 2019
Cited alongside, same era.
Small covers for near-zero sets of polynomials and learning latent variable models
Diakonikolas, I. and Kane, D. M. (2020) · 2020
Cited alongside, same era.
On the nonparametric maximum likelihood estimator for gaussian location mixture densities with application to gaussian denoising
Saha, S. and Guntuboyina, A. (2020) · 2020
Cited alongside, same era.
Score-based generative modeling through stochastic differential equations
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2020) · 2020
Cited alongside, same era.
High-dimensional probability
Vershynin, R. (2020) · 2020
Cited alongside, same era.
Settling the robust learnability of mixtures of gaussians
Liu, A. and Moitra, A. (2021) · 2021
Cited alongside, same era.
Convergence of score-based generative modeling for general data distributions
Lee, H., Lu, J., and Tan, Y. (2023) · 2023
Later among the works it cites.
Mei, S. and Wu, Y. (2023) · 2023
Later among the works it cites.
Sampling, diffusions, and stochastic localization
Montanari, A. (2023) · 2023
Later among the works it cites.
Diffusion models are minimax optimal distribution estimators
Oko, K., Akiyama, S., and Suzuki, T. (2023) · 2023
Later among the works it cites.
Fit like you sample: Sample-efficient generalized score matching from fast mixing markov chains
Qin, Y. and Risteski, A. (2023) · 2023
Later among the works it cites.
Deep learning in high dimension: Neural network expression rates for analytic functions in L 2 ( ℝ d , γ d ) {L}^{2}(\mathbb{R}^{d},\gamma_{d})
Schwab, C. and Zech, J. (2023) · 2023
Later among the works it cites.
Learning mixtures of gaussians using the ddpm objective
Shah, K., Chen, S., and Klivans, A. (2023) · 2023
Later among the works it cites.
Learning general gaussian mixtures with efficient score matching
Chen, S., Kontonis, V., and Shah, K. (2024) · 2024
Closest in time.
Cole, F. and Lu, Y. (2024) · 2024
Closest in time.
Critical windows: non-asymptotic theory for feature emergence in diffusion models
Li, M. and Chen, S. (2024) · 2024
Closest in time.
Provable benefits of score matching
Pabbaraju, C., Rohatgi, D., Sevekari, A. P., Lee, H., Moitra, A., and Risteski, A. (2024) · 2024
Closest in time.
Score-based diffusion models via stochastic differential equations–a technical tutorial
Tang, W. and Zhao, H. (2024) · 2024
Closest in time.
Optimal score estimation via empirical bayes smoothing
Wibisono, A., Wu, Y., and Yang, K. Y. (2024) · 2024
Closest in time.
Theoretical insights for diffusion guidance: A case study for gaussian mixture models
Wu, Y., Chen, M., Li, Z., Wang, M., and Wei, Y. (2024) · 2024
Closest in time.