We study the problem of learning a metric space under discriminative constraints. Given a universe X and sets S, D of similar and dissimilar pairs in X, we seek to find a mapping f: X → Y, into some host metric space M = (Y, ρ), such that similar objects are mapped close together, and dissimilar objects are mapped to points that are far apart from each other. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified examples). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces, and for both linear and non-linear mappings. Our problem formulation leads to algorithms that are shown to be robust against poisoning attacks when learning Mahalanobis metric spaces. Finally, we also discuss the problem of learning Mahalanobis metric spaces using depth-2 neural networks. Based on joint works with Diego Ihara Centurion, Bohan Fan, Neshat Mohammadi and Francesco Sgherzi.