Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding

Abstract

In this paper, we study the problem of estimating latent variable models with arbitrarily corrupted samples in high dimensional space ({\em i.e.,} $d\gg n$) where the underlying parameter is assumed to be sparse. Specifically, we propose a method called Trimmed (Gradient) Expectation Maximization which adds a trimming gradients step and a hard thresholding step to the Expectation step (E-step) and the Maximization step (M-step), respectively. We show that under some mild assumptions and with an appropriate initialization, the algorithm is corruption-proofing and converges to the (near) optimal statistical rate geometrically when the fraction of the corrupted samples $\epsilon$ is bounded by $\tilde{O}(\frac{1}{\sqrt{n}})$. Moreover, we apply our general framework to three canonical models: mixture of Gaussians, mixture of regressions and linear regression with missing covariates. Our theory is supported by thorough numerical results.

arXiv commentAccepted at Machine Learning

References in corpus (11)

• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Byzantine Stochastic Gradient Descent
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• Robust Sparse Estimation Tasks in High Dimensions
• Computationally Efficient Robust Estimation of Sparse Functionals
• Robust descent using smoothed multiplicative noise
• The EM Algorithm in Genetics, Genomics and Public Health
• Restricted eigenvalue property for corrupted Gaussian designs