Supplementary material

Note that, our original loss function is given by

(2)		$\displaystyle\mathcal{L}_{infoFiltra}=$	$\displaystyle\alpha(-I(\boldsymbol{h},\boldsymbol{x})+\beta I(\boldsymbol{h},r^{*})+\gamma I(\boldsymbol{h},s^{*})),$
	$\displaystyle\mathrm{s.t.}r^{*}=$	$\displaystyle argmax_{r,I(r,\boldsymbol{x})>0,I(r,y)=0}I(\boldsymbol{h},r),$
	$\displaystyle s^{*}=$	$\displaystyle argmax_{s,I(s,\boldsymbol{x})>0,I(s,y)=0}I(\boldsymbol{h},s).$

where $\alpha,\beta,\gamma\geq 0$. Since the Markov chain $(y,r,s)\rightarrow\boldsymbol{x}\rightarrow\boldsymbol{h}$, we have the following inequality

(3)

$$I(\boldsymbol{h},(y,r^{*},s^{*}))\leq I(\boldsymbol{h},\boldsymbol{x})$$

Given that

		$\displaystyle\quad I(\boldsymbol{h},(y,r^{*},s^{*}))$
		$\displaystyle=H(\boldsymbol{h})-H(\boldsymbol{h}|y,r^{*},s^{*})$
		$\displaystyle=H(\boldsymbol{h})-H(\boldsymbol{h}|r^{*})+H(\boldsymbol{h}|r^{*})-H(\boldsymbol{h}|y,r^{*},s^{*})$
(4)			$\displaystyle=I(\boldsymbol{h},r^{*})+I(\boldsymbol{h},(y,s^{*})|r^{*})$

Where $H(\cdot)$ represents information entropy and mutual information has the property that $I(a,b)=H(a)-H(a|b)$. Considering that $y,r^{*}$ and $s^{*}$ are independent of each other, and the property of mutual information where $I(a,b)=I(b,a)$, then

		$\displaystyle\quad I(\boldsymbol{h},(y,s^{*})|r^{*})$
		$\displaystyle=H((y,s^{*})|r^{*})-H((y,s^{*})|\boldsymbol{h},r^{*})$
		$\displaystyle\geq H(y,s^{*})-H(y,s^{*}|\boldsymbol{h})]$
		$\displaystyle=I((y,s^{*}),\boldsymbol{h})$
		$\displaystyle=H(\boldsymbol{h})-H(\boldsymbol{h}|y,s^{*})$
		$\displaystyle=H(\boldsymbol{h})-H(\boldsymbol{h}|s^{*})+H(\boldsymbol{h}|s^{*})-H(\boldsymbol{h}|y,s^{*})$
		$\displaystyle=I(\boldsymbol{h},s^{*})+I(\boldsymbol{h},y|s^{*})$
		$\displaystyle=I(\boldsymbol{h},s^{*})+H(y|s^{*})-H(y|\boldsymbol{h},s^{*})$
		$\displaystyle\geq I(\boldsymbol{h},s^{*})+H(y)-H(y|\boldsymbol{h})$
(5)			$\displaystyle=I(\boldsymbol{h},s^{*})+I(\boldsymbol{h},y)$

Combining the equation 1 and the inequality 3, 1, we can get the following inequality

(6)

$$I(\boldsymbol{h},s^{*})+I(\boldsymbol{h},r^{*})\leq I(\boldsymbol{h},\boldsymbol{x})-I(\boldsymbol{h},y)$$

So we can eliminate $I(\boldsymbol{h},r^{*})$ in the original loss function that are hard to calculate.

	$\displaystyle\quad\mathcal{L}_{infoFiltra}$
	$\displaystyle=\alpha(-I(\boldsymbol{h},\boldsymbol{x})+\beta(I(\boldsymbol{h},r^{*})+I(\boldsymbol{h},s^{*}))+p)$
(7)		$\displaystyle\leq\alpha(-I(\boldsymbol{h},\boldsymbol{x})+\beta(I(\boldsymbol{h},\boldsymbol{x})-I(\boldsymbol{h},y))+p)$

Where $p=(\gamma-\beta)I(\boldsymbol{h},s^{*})$. Then our target is to find the bound for $p$. We can deduce sensitive information from sensitive attributes. There is another Markov chain $z\rightarrow s$. Then $I(\boldsymbol{h},z)\leq I(\boldsymbol{h},s^{*})$. Combining the assumption $\beta\geq\gamma$, the upper bound of $p$ is $p\leq(\gamma-\beta)I(\boldsymbol{h},z)$. We have already discussed the necessity of $\beta\geq\gamma$ in the text. So we can prove that

	$\displaystyle\mathcal{L}_{infoFiltra}$	$\displaystyle\leq\alpha(-I(\boldsymbol{h},\boldsymbol{x})+\beta(I(\boldsymbol{h},\boldsymbol{x})-I(\boldsymbol{h},y))$
		$\displaystyle\quad+(\gamma-\beta)I(\boldsymbol{h},z))$
(8)			$\displaystyle=-\lambda_{1}I(\boldsymbol{h},\boldsymbol{x})-\lambda_{2}I(\boldsymbol{h},y)-\lambda_{3}I(\boldsymbol{h},z)$

where $\lambda_{1}=\alpha(1-\beta)$, $\lambda_{2}=\alpha\beta$, $\lambda_{3}=\alpha(\beta-\gamma)$. ∎

The gap $\epsilon$ is given by

(10)		$\displaystyle\epsilon$	$\displaystyle=$	$\displaystyle\alpha(\beta(\underbrace{I(\boldsymbol{h},\boldsymbol{x})-I(\boldsymbol{h},y)-I(\boldsymbol{h},r^{*})}_{Q_{1}})+$
				$\displaystyle\gamma(\underbrace{I(\boldsymbol{h},z)-I(\boldsymbol{h},s^{*})}_{Q_{2}})-\beta I(\boldsymbol{h},z))$

Suppose there is a function $f$ make that $\boldsymbol{x}=f(y,r,s)$. Let $\widetilde{r}$ and $\widetilde{s}$ be the random variable in the function $f$. We have

(11)		$\displaystyle I(\boldsymbol{h},\boldsymbol{x})$	$\displaystyle=$	$\displaystyle I(\boldsymbol{h},(y,\widetilde{r},\widetilde{s}))$
			$\displaystyle=$	$\displaystyle I(\boldsymbol{h},\widetilde{r})+I(\boldsymbol{h},(y,\widetilde{s})|\widetilde{r})$

Obviously, $I(\boldsymbol{h},\widetilde{r})\leq I(\boldsymbol{h},r^{*})$. We obtain

(12)		$\displaystyle Q_{1}$	$\displaystyle\leq$	$\displaystyle I(\boldsymbol{h},\boldsymbol{x})-I(\boldsymbol{h},y)-I(\boldsymbol{h},\widetilde{r})$
			$\displaystyle=$	$\displaystyle I(\boldsymbol{h},\widetilde{r})+I(\boldsymbol{h},(y,\widetilde{s})|\widetilde{r})-I(\boldsymbol{h},y)-I(\boldsymbol{h},\widetilde{r})$
			$\displaystyle=$	$\displaystyle I(\boldsymbol{h},(y,\widetilde{s})|\widetilde{r})-I(\boldsymbol{h},y)$
			$\displaystyle=$	$\displaystyle I(\boldsymbol{h},(y,\widetilde{s})|\widetilde{r})-I(\boldsymbol{x},y)+I(\boldsymbol{x},y)-I(\boldsymbol{h},y)$
			$\displaystyle=$	$\displaystyle H((y,\widetilde{s})|\widetilde{r})-H((y,\widetilde{s})|\boldsymbol{h},\widetilde{r})-H(y)+H(y|\boldsymbol{x})$
				$\displaystyle+I(\boldsymbol{x},y)-I(\boldsymbol{h},y)$

Given that $y,\widetilde{s}$ and $\widetilde{r}$ are independent of each other, we have $H((y,\widetilde{s})|\widetilde{r})=H(y,\widetilde{s})$, and $y$ can be derived from $x$ so that $H(y|\boldsymbol{x})=0$. We get

(13)

$$Q_{1}\leq I(\boldsymbol{x},y)-I(\boldsymbol{h},y)$$

Due to $Q_{2}\leq 0$, we can prove that

(14)

$$\epsilon\leq\alpha\beta(I(\boldsymbol{x},y)-I(\boldsymbol{h},y)-I(\boldsymbol{h},z))$$

∎