  Metric learning is an important family of algorithms for classification and
similarity search, but the robustness of learned metrics against small
adversarial perturbations is less studied. In this paper, we show that existing
metric learning algorithms, which focus on boosting the clean accuracy, can
result in metrics that are less robust than the Euclidean distance. To overcome
this problem, we propose a novel metric learning algorithm to find a
Mahalanobis distance that is robust against adversarial perturbations, and the
robustness of the resulting model is certifiable. Experimental results show
that the proposed metric learning algorithm improves both certified robust
errors and empirical robust errors (errors under adversarial attacks).
Furthermore, unlike neural network defenses which usually encounter a trade-off
between clean and robust errors, our method does not sacrifice clean errors
compared with previous metric learning methods. Our code is available at
https://github.com/wangwllu/provably_robust_metric_learning.
