Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
This work provides a robust training method for high-dimensional machine learning problems under gross corruption, though it is incremental as it builds on existing geometric median techniques.
The paper tackles the problem of robust training in high-dimensional non-convex optimization by addressing the computational infeasibility of using the geometric median (Gm) with stochastic gradient descent (SGD). It proposes a block coordinate approach with a memory mechanism, achieving a breakdown point of 0.5 and non-asymptotic convergence rates comparable to SGD with Gm.
Geometric median (\textsc{Gm}) is a classical method in statistics for achieving a robust estimation of the uncorrupted data; under gross corruption, it achieves the optimal breakdown point of 0.5. However, its computational complexity makes it infeasible for robustifying stochastic gradient descent (SGD) for high-dimensional optimization problems. In this paper, we show that by applying \textsc{Gm} to only a judiciously chosen block of coordinates at a time and using a memory mechanism, one can retain the breakdown point of 0.5 for smooth non-convex problems, with non-asymptotic convergence rates comparable to the SGD with \textsc{Gm}.