Given a metric space $(\mathcal{X},\rho)$ and $\mathcal{A}\subset\mathcal{X}$ totally bounded, i.e. A has a finite $\varepsilon$-covering for any $\varepsilon>0$. Consider $\operatorname{Lip}_{1}(\mathcal{A}, C)$ the space of $1$-Lipschitz functions $$(\mathcal{X},\rho)\to (\mathbb{R},\lvert\,\cdot\,\rvert)$$ that are uniformly bounded by $C>0$, that is $\lvert f(x)\rvert\leq C$ for all $x\in\mathcal{A}$. There are various variants to bound the covering number of the function space $\operatorname{Lip}_{1}(\mathcal{A}, C)$. For example, in "$\varepsilon$-Entropy and $\varepsilon$-Capacity", section §9, Kolmogorov and Tikhomirov show the following one:

Suppose the space $(\mathcal{X},\rho)$ is connected and centrable, i.e. for any $\mathcal{U}\subset\mathcal{X}$ with $\operatorname{diam}\mathcal{U}\leq d=2r$ there is a point $x\in\mathcal{X}$ (center) such that $\rho(x,u)\leq r$ for all $u\in\mathcal{U}$. Then

$$2^{M_{2\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/2}(\mathcal{A})},$$

where $M_{\nu}(\cdot)$ and $N_{\nu}(\cdot)$ denote the $\nu$-packing and $\nu$-covering number of a space, respectively. If $(\mathcal{X},\rho)$ is not necessarily connected and centrable, there are slightly weaker bounds:

$$2^{M_{4\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/4}(\mathcal{A})}.$$

Similarly, in "Efficient Regression in Metric Spaces via Approximate Lipschitz Extension", for the space $\mathcal{F}_1=\operatorname{Lip}_{1}((\mathcal{X},\rho),([0,1],\lvert\,\cdot\,\rvert))$ of $1$-Lipschitz functions $(\mathcal{X},\rho)\to ([0,1],\lvert\,\cdot\,\rvert)$, Gottlieb, Kontorovich and Krauthgamer show that

$$N_{\varepsilon}(\mathcal{F}_1,\lVert\,\cdot\,\rVert_{\infty}) \leq \left(\frac{8}{\varepsilon}\right)^{N_{\varepsilon/8}(\mathcal{X})}.$$

In both cases, the idea is to pick a $\nu$-covering $U_i$, $i\in N_{\nu}$ of the underlying space and where $\nu$ is for example $\varepsilon/8$ in the latter paper and pick some $x_i\in U_i$, in case of centrable space this can be taken to be centers. Then for any considered Lipschitz function $f$ define some discrete approximation $\hat{f}(x_i)$ at these points. In the latter paper for example, $\hat{f}(x_i)$ is defined to be a multiple of $\varepsilon/4$ and such that it differs from $f(x_i)$ by at most $\varepsilon/4$, e.g. $$\hat{f}(x_1)=\Big\lceil\frac{4f(x_1)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4}.$$ It is then claimed in the latter paper (and imho implicity in the Kolmogorov one) that $$\hat{f}:\{x_1,\ldots, x_{N}\}\to [0,1]$$ is $2$-Lipschitz continuous (and maybe even $1$-Lipschitz in the Kolmogorov paper). Thus, it can be extended to a $2$-Lipschitz continuous function on the whole space $\mathcal{X}$. However, it is not clear to me, how we can ensure that $\hat{f}$ is $2$-Lipschitz on the points $x_i$ in general. E.g. suppose that $$\hat{f}(x_i)=\Big\lceil\frac{4f(x_i)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4} =\Big(\frac{4f(x_i)}{\varepsilon}+r_i\Big)\frac{\varepsilon}{4}$$ with remainder $0\leq r_i < 1$. Then $$ \begin{split} \lvert \hat{f}(x_i) - \hat{f}(x_j)\rvert & \leq \lvert f(x_i) - f(x_j)\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \\ & \leq \lvert x_i-x_j\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \\ & \leq \lvert x_i-x_j\rvert + \frac{\varepsilon}{4}. \end{split} $$ If we could ensure that $\lvert x_i-x_j\rvert\geq \frac{\varepsilon}{4}$, we could now conclude the $2$-Lipschitzness . But it could be that the space is covered by for example by three $\varepsilon/8$-balls with centers $x_i$ that are arbitrary close to each other.

How can we remedy this? I.e. how can we in fact ensure that the constructed approximations are in fact $2$-Lipschitz continuous?

Given a metric space $(\mathcal{X},\rho)$ and $\mathcal{A}\subset\mathcal{X}$ totally bounded, i.e. $\mathcal{A}$ has a finite $\varepsilon$-covering for any $\varepsilon>0$. Consider $\operatorname{Lip}_{1}(\mathcal{A}, C)$ the space of $1$-Lipschitz functions $$(\mathcal{X},\rho)\to (\mathbb{R},\lvert\,\cdot\,\rvert)$$ that are uniformly bounded by $C>0$, that is $\lvert f(x)\rvert\leq C$ for all $x\in\mathcal{A}$. There are various variants to bound the covering number of the function space $\operatorname{Lip}_{1}(\mathcal{A}, C)$. For example, in "$\varepsilon$-Entropy and $\varepsilon$-Capacity", section §9, Kolmogorov and Tikhomirov show the following one:

Suppose the space $(\mathcal{X},\rho)$ is connected and centrable, i.e. for any $\mathcal{U}\subset\mathcal{X}$ with $\operatorname{diam}\mathcal{U}\leq d=2r$ there is a point $x\in\mathcal{X}$ (center) such that $\rho(x,u)\leq r$ for all $u\in\mathcal{U}$. Then

$$2^{M_{2\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/2}(\mathcal{A})},$$

where $M_{\nu}(\cdot)$ and $N_{\nu}(\cdot)$ denote the $\nu$-packing and $\nu$-covering number of a space, respectively. If $(\mathcal{X},\rho)$ is not necessarily connected and centrable, there are slightly weaker bounds:

$$2^{M_{4\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/4}(\mathcal{A})}.$$

Similarly, in "Efficient Regression in Metric Spaces via Approximate Lipschitz Extension", for the space $\mathcal{F}_1=\operatorname{Lip}_{1}((\mathcal{X},\rho),([0,1],\lvert\,\cdot\,\rvert))$ of $1$-Lipschitz functions $(\mathcal{X},\rho)\to ([0,1],\lvert\,\cdot\,\rvert)$, Gottlieb, Kontorovich and Krauthgamer show that

$$N_{\varepsilon}(\mathcal{F}_1,\lVert\,\cdot\,\rVert_{\infty}) \leq \left(\frac{8}{\varepsilon}\right)^{N_{\varepsilon/8}(\mathcal{X})}.$$

In both cases, the idea is to pick a $\nu$-covering $U_i$, $i\in N_{\nu}$ of the underlying space and where $\nu$ is for example $\varepsilon/8$ in the latter paper and pick some $x_i\in U_i$, in case of centrable space this can be taken to be centers. Then for any considered Lipschitz function $f$ define some discrete approximation $\hat{f}(x_i)$ at these points. In the latter paper for example, $\hat{f}(x_i)$ is defined to be a multiple of $\varepsilon/4$ and such that it differs from $f(x_i)$ by at most $\varepsilon/4$, e.g. $$\hat{f}(x_1)=\Big\lceil\frac{4f(x_1)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4}.$$ It is then claimed in the latter paper (and imho implicity in the Kolmogorov one) that $$\hat{f}:\{x_1,\ldots, x_{N}\}\to [0,1]$$ is $2$-Lipschitz continuous (and maybe even $1$-Lipschitz in the Kolmogorov paper). Thus, it can be extended to a $2$-Lipschitz continuous function on the whole space $\mathcal{X}$. However, it is not clear to me, how we can ensure that $\hat{f}$ is $2$-Lipschitz on the points $x_i$ in general. E.g. suppose that $$\hat{f}(x_i)=\Big\lceil\frac{4f(x_i)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4} =\Big(\frac{4f(x_i)}{\varepsilon}+r_i\Big)\frac{\varepsilon}{4}$$ with remainder $0\leq r_i < 1$. Then $$ \begin{split} \lvert \hat{f}(x_i) - \hat{f}(x_j)\rvert & \leq \lvert f(x_i) - f(x_j)\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \\ & \leq \lvert x_i-x_j\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \\ & \leq \lvert x_i-x_j\rvert + \frac{\varepsilon}{4}. \end{split} $$ If we could ensure that $\lvert x_i-x_j\rvert\geq \frac{\varepsilon}{4}$, we could now conclude the $2$-Lipschitzness . But it could be that the space is covered by for example by three $\varepsilon/8$-balls with centers $x_i$ that are arbitrary close to each other.

How can we remedy this? I.e. how can we in fact ensure that the constructed approximations are in fact $2$-Lipschitz continuous?

Given a metric space $(\mathcal{X},\rho)$ and $\mathcal{A}\subset\mathcal{X}$ totally bounded, i.e. A has a finite $\varepsilon$-covering for any $\varepsilon>0$. Consider $\operatorname{Lip}_{1}(\mathcal{A}, C)$ the space of $1$-Lipschitz functions $$(\mathcal{X},\rho)\to (\mathbb{R},\lvert\,\cdot\,\rvert)$$ that are uniformly bounded by $C>0$, that is $\lvert f(x)\rvert\leq C$ for all $x\in\mathcal{A}$. There are various variants to bound the covering number of the function space $\operatorname{Lip}_{1}(\mathcal{A}, C)$. For example, Kolmogorov and Tikhomirov show in "$\varepsilon$-Entropy and $\varepsilon$-Capacity" (https://doi.org/10.1007/978-94-017-2973-4_17) in Section §9:

Suppose the space $(\mathcal{X},\rho)$ is connected and centrable, i.e. for any $\mathcal{U}\subset\mathcal{X}$ with $\operatorname{diam}\mathcal{U}\leq d=2r$ there is a point $x\in\mathcal{X}$ (center) such that $\rho(x,u)\leq r$ for all $u\in\mathcal{U}$. Then

$$2^{M_{2\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/2}(\mathcal{A})},$$

where $M_{\nu}(\cdot)$ and $N_{\nu}(\cdot)$ denote the $\nu$-packing and $\nu$-covering number of a space, respectively. If $(\mathcal{X},\rho)$ is not necessarily connected and centrable, there are slightly weaker bounds:

$$2^{M_{4\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/4}(\mathcal{A})}.$$

Similarly, Gottlieb, Kontorovich and Krauthgamer show in "Efficient Regression in Metric Spaces via Approximate Lipschitz Extension" (https://doi.org/10.1007/978-3-642-39140-8_3) for the space $\mathcal{F}_1=\operatorname{Lip}_{1}((\mathcal{X},\rho),([0,1],\lvert\,\cdot\,\rvert))$ of $1$-Lipschitz functions $(\mathcal{X},\rho)\to ([0,1],\lvert\,\cdot\,\rvert)$ that

$$N_{\varepsilon}(\mathcal{F}_1,\lVert\,\cdot\,\rVert_{\infty}) \leq \left(\frac{8}{\varepsilon}\right)^{N_{\varepsilon/8}(\mathcal{X})}.$$

In both cases, the idea is to pick a $\nu$-covering $U_i$, $i\in N_{\nu}$ of the underlying space and where $\nu$ is for example $\varepsilon/8$ in the latter paper and pick some $x_i\in U_i$, in case of centrable space this can be taken to be centers. Then for any considered Lipschitz function $f$ define some discrete approximation $\hat{f}(x_i)$ at these points. In the latter paper for example, $\hat{f}(x_i)$ is defined to be a multiple of $\varepsilon/4$ and such that it differs from $f(x_i)$ by at most $\varepsilon/4$, e.g. $$\hat{f}(x_1)=\Big\lceil\frac{4f(x_1)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4}.$$ It is then claimed in the latter paper (and imho implicity in the Kolmogorov one) that $$\hat{f}:\{x_1,\ldots, x_{N}\}\to [0,1]$$ is $2$-Lipschitz continuous (and maybe even $1$-Lipschitz in the Kolmogorov paper). Thus, it can be extended to a $2$-Lipschitz continuous function on the whole space $\mathcal{X}$. However, it is not clear to me, how we can ensure that $\hat{f}$ is $2$-Lipschitz on the points $x_i$ in general. E.g. suppose that $$\hat{f}(x_i)=\Big\lceil\frac{4f(x_i)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4} =\Big(\frac{4f(x_i)}{\varepsilon}+r_i\Big)\frac{\varepsilon}{4}$$ with remainder $0\leq r_i < 1$. Then

$$\lvert \hat{f}(x_i) - \hat{f}(x_j)\rvert \leq \lvert f(x_i) - f(x_j)\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \leq \lvert x_i-x_j\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \leq \lvert x_i-x_j\rvert + \frac{\varepsilon}{4}.$$

If we could ensure that $\lvert x_i-x_j\rvert\geq \frac{\varepsilon}{4}$, we could now conclude the $2$-Lipschitzness . But it could be that the space is covered by for example by three $\varepsilon/8$-balls with centers $x_i$ that are arbitrary close to each other.

How can we remedy this? I.e. how can we in fact ensure that the constructed approximations are in fact $2$-Lipschitz continuous?

Given a metric space $(\mathcal{X},\rho)$ and $\mathcal{A}\subset\mathcal{X}$ totally bounded, i.e. A has a finite $\varepsilon$-covering for any $\varepsilon>0$. Consider $\operatorname{Lip}_{1}(\mathcal{A}, C)$ the space of $1$-Lipschitz functions $$(\mathcal{X},\rho)\to (\mathbb{R},\lvert\,\cdot\,\rvert)$$ that are uniformly bounded by $C>0$, that is $\lvert f(x)\rvert\leq C$ for all $x\in\mathcal{A}$. There are various variants to bound the covering number of the function space $\operatorname{Lip}_{1}(\mathcal{A}, C)$. For example, in "$\varepsilon$-Entropy and $\varepsilon$-Capacity", section §9, Kolmogorov and Tikhomirov show the following one:

Suppose the space $(\mathcal{X},\rho)$ is connected and centrable, i.e. for any $\mathcal{U}\subset\mathcal{X}$ with $\operatorname{diam}\mathcal{U}\leq d=2r$ there is a point $x\in\mathcal{X}$ (center) such that $\rho(x,u)\leq r$ for all $u\in\mathcal{U}$. Then

$$2^{M_{2\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/2}(\mathcal{A})},$$

where $M_{\nu}(\cdot)$ and $N_{\nu}(\cdot)$ denote the $\nu$-packing and $\nu$-covering number of a space, respectively. If $(\mathcal{X},\rho)$ is not necessarily connected and centrable, there are slightly weaker bounds:

$$2^{M_{4\varepsilon}(\mathcal{A})} \leq N_{\varepsilon}(\operatorname{Lip}_{1}(\mathcal{A}, C),\lVert\,\cdot\,\rVert_{\infty}) \leq \Big(\Big\lceil\frac{2C}{\varepsilon}\Big\rceil+1\Big)2^{N_{\varepsilon/4}(\mathcal{A})}.$$

Similarly, in "Efficient Regression in Metric Spaces via Approximate Lipschitz Extension", for the space $\mathcal{F}_1=\operatorname{Lip}_{1}((\mathcal{X},\rho),([0,1],\lvert\,\cdot\,\rvert))$ of $1$-Lipschitz functions $(\mathcal{X},\rho)\to ([0,1],\lvert\,\cdot\,\rvert)$, Gottlieb, Kontorovich and Krauthgamer show that

$$N_{\varepsilon}(\mathcal{F}_1,\lVert\,\cdot\,\rVert_{\infty}) \leq \left(\frac{8}{\varepsilon}\right)^{N_{\varepsilon/8}(\mathcal{X})}.$$

In both cases, the idea is to pick a $\nu$-covering $U_i$, $i\in N_{\nu}$ of the underlying space and where $\nu$ is for example $\varepsilon/8$ in the latter paper and pick some $x_i\in U_i$, in case of centrable space this can be taken to be centers. Then for any considered Lipschitz function $f$ define some discrete approximation $\hat{f}(x_i)$ at these points. In the latter paper for example, $\hat{f}(x_i)$ is defined to be a multiple of $\varepsilon/4$ and such that it differs from $f(x_i)$ by at most $\varepsilon/4$, e.g. $$\hat{f}(x_1)=\Big\lceil\frac{4f(x_1)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4}.$$ It is then claimed in the latter paper (and imho implicity in the Kolmogorov one) that $$\hat{f}:\{x_1,\ldots, x_{N}\}\to [0,1]$$ is $2$-Lipschitz continuous (and maybe even $1$-Lipschitz in the Kolmogorov paper). Thus, it can be extended to a $2$-Lipschitz continuous function on the whole space $\mathcal{X}$. However, it is not clear to me, how we can ensure that $\hat{f}$ is $2$-Lipschitz on the points $x_i$ in general. E.g. suppose that $$\hat{f}(x_i)=\Big\lceil\frac{4f(x_i)}{\varepsilon}\Big\rceil\frac{\varepsilon}{4} =\Big(\frac{4f(x_i)}{\varepsilon}+r_i\Big)\frac{\varepsilon}{4}$$ with remainder $0\leq r_i < 1$. Then $$ \begin{split} \lvert \hat{f}(x_i) - \hat{f}(x_j)\rvert & \leq \lvert f(x_i) - f(x_j)\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \\ & \leq \lvert x_i-x_j\rvert + \lvert r_i- r_j\rvert\frac{\varepsilon}{4} \\ & \leq \lvert x_i-x_j\rvert + \frac{\varepsilon}{4}. \end{split} $$ If we could ensure that $\lvert x_i-x_j\rvert\geq \frac{\varepsilon}{4}$, we could now conclude the $2$-Lipschitzness . But it could be that the space is covered by for example by three $\varepsilon/8$-balls with centers $x_i$ that are arbitrary close to each other.

How can we remedy this? I.e. how can we in fact ensure that the constructed approximations are in fact $2$-Lipschitz continuous?