Geometric median (GM) is a classical methodin statistics for achieving robust estimationof the uncorrupted data; under gross corruption,it achieves the optimal breakdownpoint of 1/2. However, its computationalcomplexity makes it infeasible for robustifyingstochastic gradient descent (SGD) inhigh-dimensional optimization problems. Inthis paper, we show that by applying GMto only a judiciously chosen block of coordinatesat a time and using a memory mechanism,one can retain the breakdown pointof 1/2 for smooth non-convex problems, withnon-asymptotic convergence rates comparableto the SGD with GM while resultingin significant speedup in training. We furthervalidate the run-time and robustness ofour approach empirically on several populardeep learning tasks. Code available at:https://github.com/anishacharya/BGMD