- Faster Convergence of Robust Mean Estimation in One Dimension
- Project Year:
2018
- REU Student (s):
Ryan Rice | The University of Texas at Austin TX
- Student 1 Institution:
The University of Texas at Austin
- Project Mentor:
Pranjal Awasthi
- Project Mentor Area:
Computer Science
- Project Abstract:
The problem of learning the mean of a distribution from samples with
at most an ε-fraction of adversarial corruptions has been the
subject of much recent work. Several current breakthroughs are
polynomial time algorithms for high dimensional data in specific
classes of distributions. We consider the problem of robust mean
estimation for "resilient" distributions and show that with an
additional preprocessing step and different analysis, the current best
polynomial time algorithm will
only need O(log n) iterations of outlier removal in one dimension,
as opposed to O(n) in the worst case. This is significant due to the
costly outlier identification process involving principal component
analysis or semidefinite programming in these algorithms. Our work
could provide insight for future approaches on improving the
practicality of robust mean estimation for non-gaussian distributions.
