Robust estimation algorithms don't need to know the corruption level
This addresses a pervasive limitation in robust estimation for real-world data analysis, offering a practical improvement for researchers and practitioners dealing with corrupt data.
The paper tackles the problem that robust estimation algorithms typically require a known upper bound on the corruption level to achieve optimal accuracy, which is often unavailable in practice, and presents a universal meta technique that converts such algorithms to achieve similar accuracy without needing this bound.
Real data are rarely pure. Hence the past half-century has seen great interest in robust estimation algorithms that perform well even when part of the data is corrupt. However, their vast majority approach optimal accuracy only when given a tight upper bound on the fraction of corrupt data. Such bounds are not available in practice, resulting in weak guarantees and often poor performance. This brief note abstracts the complex and pervasive robustness problem into a simple geometric puzzle. It then applies the puzzle's solution to derive a universal meta technique that converts any robust estimation algorithm requiring a tight corruption-level upper bound to achieve its optimal accuracy into one achieving essentially the same accuracy without using any upper bounds.