Furthermore, Lemma 1 in [1]} asserts that \(c(x,y)=\frac{1}{2}d(x,y)^2\)  is also \(|{\mathcal {M}}|\) -Lipschitz as a function of each of its variables. Therefore, using the \({\epsilon }\) -net, we get that for each \(x,y\in {\mathcal {M}}\)  there exists \(i\in [m]\)  so that
\(c(x,y)-\hat{\phi }^c(y) \ge c(x,y_i) - \hat{\phi }^c(y_i) - 2|{\mathcal {M}}|{\epsilon }\) 
