&=  \hspace{-0.1cm}  \frac{{\rm d}}{ {\rm d} x} \hspace{-0.05cm}  \left(   f_{k-1}(x) \eu^{ \int_0^x \hspace{-0.1cm}  f_1(t) {\rm d} t}   \right) , \label{eq:DerivativeOfTheRecurance}
\end{align}

where the last expression is due to the product rule.  Now, let

\begin{equation}
h_k(x)=f_k(x) \eu^{ \int_0^x f_1(t) {\rm d} t}.
\end{equation}

Then, the  expression in (<ref>) implies that

\begin{equation}
h_k(x)=  \frac{{\rm d}}{ {\rm d} x}   h_{k-1}(x), \label{eq:DefinitionOfhk}
\end{equation}

which by using the recursion $k-1$ times implies that

\begin{equation}
h_k(x)=     \frac{{\rm d}^{k-1}}{ {\rm d} x^{k-1}} h_1(x)=   \frac{{\rm d}^{k-1}}{ {\rm d} x^{k-1}}   \left(  f_1(x) \eu^{ \int_0^x f_1(t) {\rm d} t } \right).  \label{eq:Definitionofhkfunction}
\end{equation}

Furthermore, by applying the chain rule in (<ref>), we arrive at

\begin{equation}
h_k(x)= \frac{{\rm d}^{k}}{ {\rm d} x^{k}}   \eu^{ \int_0^x f_1(t) {\rm d} t } .
\end{equation}

The proof of (<ref>) is concluded by using  the definition of  $h_k(x)$ in (<ref>).

To show the expression in (<ref>) recall the Faà di Bruno formula for the higher-order chain rule <cit.>: given two $k \in \mathbb{N}$ differentiable functions $g(t)$ and $\xi(t)$

\begin{equation}
\frac{{\rm d}^{k}  \xi(  g(t)  ) }{ {\rm d} t^{k}} = \sum_{m=1}^k  \xi^{(m)}( g(t))  \mathsf{B}_{k,m} \left(g^{(1)}(x), \ldots, g^{(k-m+1)}(x) \right). \label{eq: Fa\`a di Bruno formula}
\end{equation}

Next, by letting    $g(x) =\int_0^x f_1(t) {\rm d} t$, the expression in (<ref>) can be re-written as

\begin{align}
f_k(x)&=  \eu^{- g(x) }  \frac{  {\rm d}^k} { {\rm d} x^k } \eu^{ g(x)} \\
&=   \eu^{- g(x) } \sum_{m=1}^k  \eu^{g(x) } \mathsf{B}_{k,m} \left(g^{(1)}(x), \ldots, g^{(k-m+1)}(x) \right)  \label{eq:applying_Faa_di_Bruno_formula}\\
&=  \mathsf{B}_{k} \left (g^{(1)}(x), \ldots, g^{(k)}(x) \right) \label{eq:applying_complete_Ball_polynomial_def} \\
&= \mathsf{B}_{k} \left(f^{(0)}_1(x), \ldots, f^{(k-1)}_1(x) \right),  \label{eq:Applying derivative of g(t)}
\end{align}

where  (<ref>) follows by using the Faà di Bruno formula in (<ref>); (<ref>) follows from (<ref>); and  (<ref>) follows by noting that $g^{(m)}(x)=f^{(m-1)}(x), m\in \mathbb{N}$.

To show (<ref>), we use the inversion formula for the Bell polynomial <cit.> which asserts the following:  if

\begin{equation}
y_k=   \mathsf{B}_{k}(t_1,\ldots, t_k),
\end{equation}

\begin{equation}
t_k= \sum_{m=1}^k (-1)^{m-1}(m-1)!  \mathsf{B}_{k,m}(y_1,\ldots, y_{k-m+1}).
\end{equation}

Setting $y_k=f_k(x)$ and $t_k=f_1^{(k-1)}(x)$ leads to

\begin{align}
&=\sum_{m=1}^k (-1)^{m-1}(m-1)!  \mathsf{B}_{k,m}(f_1(x),\ldots, f_{k-m+1}(x)).
\end{align}

The proof is concluded by using a change of variable from $k-1$ to $k$.

§ PROOF OF PROPOSITION <REF>

First, observe that

\begin{align}
|\kappa_{X|Y=y}(k)| &\le k^k \E[ |X -\E[X|Y] |^k |Y =y] \label{eq:Bounds_on_cumulants}\\
& \le 2^{k-1} k^k  \E[ |X |^k |Y =y], \label{eq:Lp_esimates}
\end{align}

where in (<ref>) we have used the bound in <cit.>; and in (<ref>) we have used $| a+b|^k \le 2^{k-1} (| a|^k+|b|^k), k \ge 1$.

We now show a bound on $\E[ |X |^k |Y =y]$, which is a generalization of the bound shown in <cit.>. First,

\begin{align}
\E[|X|^k|Y=y]
& =\int_{  f_{Y|X}(y|x) \le f_Y(y) } |x|^k \frac{ f_{Y|X}(y|x)}{ f_Y(y) } {\rm d} P_X(x) + \int_{  f_{Y|X}(y|x) > f_Y(y) } |x|^k \frac{ f_{Y|X}(y|x)}{ f_Y(y) } {\rm d} P_X(x) \\
&\le \E[|X|^k]  + \int_{  f_{Y|X}(y|x) > f_Y(y) } |x|^k \frac{ f_{Y|X}(y|x)}{ f_Y(y) } {\rm d} P_X(x) . \label{eq:Prep_bound}
\end{align}

Next, we bounds the second term in (<ref>)

\begin{align}
&f_{Y|X}(y|x) > f_Y(y) \notag\\
&\Rightarrow  (y-x)^2 \le 2 \sigma^2 \log \left( \frac{1}{\sqrt{2 \pi \sigma^2} f_Y(y) }  \right) \notag\\
&\Rightarrow  |y-x|  \le \sqrt{ 2 \sigma^2 \log \left( \frac{1}{\sqrt{2 \pi \sigma^2} f_Y(y) }  \right)}  \notag\\
&\Rightarrow  |x|  \le |y|+ \sqrt{ 2 \sigma^2 \log \left( \frac{1}{\sqrt{2 \pi \sigma^2} f_Y(y) }  \right)}  \label{eq:applying_Triangle_Inequaltiy}\\
&\Rightarrow  |x|^k  \le 2^{k-1} \left( |y|^k+ \left( 2 \sigma^2 \log \left( \frac{1}{\sqrt{2 \pi \sigma^2} f_Y(y) }  \right) \right)^{ \frac{k}{2}}  \right)  \label{eq:Lp-type_Bounds}\\
&\Rightarrow  |x|^k  \le 2^{k-1} \left( |y|^k+ 2\left(  y^2 +\E[X^2] \right)^{ \frac{k}{2}}  \right) \label{eq:Applying_Jensen's_Inequality_to_cumulants}\\
&\Rightarrow  |x|^k  \le  2^{k-1}(2^{ \max (\frac{k}{2}-1,1)}+2) |y|^k + 2^{ \max (\frac{k}{2}-1,1)+k} \E^{ \frac{k}{2}}[X^2] ,   \label{eq:Lp_last_bound}
\end{align}

where (<ref>) follows from the reverse triangle inequality; (<ref>) follows by using the bound  $|a +b|^k \le2^{k-1} (|a|^k+|b|^k), k \ge 1$; (<ref>) follows by using Jensen's inequality to

\begin{align}
f_Y(y)&=\frac{1}{\sqrt{2\pi \sigma^2}} \E \left[ \eu^{-\frac{(y-X)^2}{2 \sigma^2}} \right]\\
&\ge \frac{1}{\sqrt{2\pi \sigma^2}} \eu^{-\frac{ \E \left[  (y-X)^2 \right]}{2 \sigma^2}} \\
&\ge \frac{1}{\sqrt{2\pi \sigma^2}} \eu^{-\frac{  y^2 +\E[X^2]}{\sigma^2}}; \text{ and}
\end{align}

(<ref>) follows form the bound  $|a +b|^k \le2^{ \max(k-1,1)} (|a|^k+|b|^k), k \ge 0$.

Combining (<ref>) and (<ref>) concludes the proof.

§ PROOF OF THE EXPRESSION IN (<REF>)

The first ingredient of the proof is the following derivative  expression:

\begin{equation}
\frac{{\rm d}}{{\rm d } t} \frac{I_\nu(t)}{I_{\nu-1}(t)}= 1-\frac{2\nu-1}{t}   \frac{I_\nu(t)}{I_{\nu-1}(t)} - \left( \frac{I_\nu(t)}{I_{\nu-1}(t)} \right)^2, \label{eq:Derivative_Ratio_Bessel_Functions}
\end{equation}

which follows form the identities $\frac{{\rm d}}{{\rm d } t} I_\nu(t)= \frac{\nu}{t} I_{\nu-1}(t) - \frac{\nu}{t}I_{\nu}(t)$
and $\frac{{\rm d}}{{\rm d } t} I_\nu(t)= \frac{\nu}{t} I_\nu(t)+  I_{\nu+1}(t)$  [50].

Next, consider the case of  $s_1 \neq s_2$. Then,

\begin{align}
\frac{\partial \E[ X_{s_2} |\Y={\bf y}]  }{ \partial y_{s_1}    }
& = R  y_{s_2} \frac{\partial  }{ \partial y_{s_1}    }   \frac{1 }{ \| {\bf y} \| }   \frac{I_{\frac{n}{2}}( R \| {\bf y}\|  ) }{ I_{\frac{n}{2}-1}(R \| {\bf y}\|) } \\
&=    \frac{ R  y_{s_2} y_{s_1} }{ \| {\bf y} \| }   \frac{I_{\frac{n}{2}}( R \| {\bf y}\|  ) }{ I_{\frac{n}{2}-1}(R \| {\bf y}\|) }  +    \frac{ R  y_{s_2}  }{ \| {\bf y} \| }  \frac{\partial  }{ \partial y_{s_1}    }    \frac{I_{\frac{n}{2}}( R \| {\bf y}\|  ) }{ I_{\frac{n}{2}-1}(R \| {\bf y}\|) } \\
&=    \frac{ R  y_{s_2} y_{s_1} }{ \| {\bf y} \| }   \frac{I_{\frac{n}{2}}( R \| {\bf y}\|  ) }{ I_{\frac{n}{2}-1}(R \| {\bf y}\|) }  +    \frac{ R^2  y_{s_2}  y_{s_1} }{ \| {\bf y} \| ^2}   \left(1 -\frac{n-1}{R \| {\bf y}\|}  \frac{I_{\frac{n}{2}}( R \| {\bf y}\|  ) }{ I_{\frac{n}{2}-1}(R \| {\bf y}\|) }  - \left( \frac{I_{\frac{n}{2}}( R \| {\bf y}\|  ) }{ I_{\frac{n}{2}-1}(R \| {\bf y}\|) }  \right)^2  \right),
\end{align}

where the last equality follows by using the derivative expression in (<ref>).

The proof for $s_1 = s_2$ follows along the similar lines.

§ COMPUTATION OF (<REF>) AND (<REF>)

If $X$ is standard normal, then

\begin{equation}
f_Y(y)=\frac{1}{\sqrt{ 2 \pi (1+\sigma^2)}} \eu^{-\frac{y^2}{ 2(1+\sigma^2)}}, \, y\in \mathbb{R}.
\end{equation}

Consequently, the information density is given by

\begin{align}
\iota_{P_{X Y}}(x;y)&=\log   \frac{f_{X|Y}(x|y)}{f_X(x)} \\
&= \log \frac{ f_{Y|X}(y|x)}{f_Y(y)} \\
&=  c-  \frac{ (y-x)^2}{2 \sigma^2} +  \frac{y^2}{2( 1+\sigma^2)},
\end{align}

where $c = \frac{1}{2}\log \frac{1+\sigma^2}{ \sigma^2}$. Hence,  the conditional variance is now given by

\begin{align}
\mathsf{Var}\left(    \iota_{P_{X Y}}(X; Y )  | X =x\right)
&= \mathsf{Var}\left(   - \frac{ (Y-X)^2}{2 \sigma^2} +  \frac{Y^2}{2( 1+\sigma^2)}  | X =x\right)\\
&=\mathsf{Var}\left(   - \frac{ N^2}{2 \sigma^2} +  \frac{(X+N)^2}{2( 1+\sigma^2)}  | X =x\right)\\
&=\mathsf{Var}\left(   - \frac{ N^2}{2 \sigma^2} +  \frac{ N^2 }{2( 1+\sigma^2)} + \frac{ N X  }{ 1+\sigma^2}  | X =x\right)\\
&=\mathsf{Var}\left(  - \frac{ 1}{2 \sigma^2( 1+\sigma^2)}    N^2+ \frac{ N X  }{ 1+\sigma^2}  | X =x\right)\\
&=  \frac{ \mathsf{Var}\left(N^2 \right)  }{4 \sigma^4( 1+\sigma^2)^2}    + \frac{ x^2 \mathsf{Var}( N )   }{( 1+\sigma^2)^2}  \label{eq:Covariance_N2_and_N}\\
&=  \frac{ 2 \sigma^4 }{4 \sigma^4( 1+\sigma^2)^2}    + \frac{ x^2  \sigma^2   }{( 1+\sigma^2)^2} , \label{eq:Variance_N2_and_N}
\end{align}

where in (<ref>) we have used that ${\rm Cov}( N^2, N)=0$; and (<ref>) follows by using that $\mathsf{Var}\left(N^2 \right)=2  \sigma^4 $ and $ \mathsf{Var}( N ) =\sigma^2$.
This concludes the proof.

§ PROOF OF THEOREM <REF>

It is sufficient to characterize only the second order partial derivatives $\frac{\partial }{ \partial y_j   \partial y_i} K_{\X}( {\bf t} |\Y={\bf y})$ and then apply a simple induction.

Let $U= \eu^{ {\bf t}^\mathsf{T} \X}$. Then, by using Theorem <ref>, we have that the gradient of the cumulant generating function can be expressed as

\begin{align}
\nabla_{{\bf y}}  K_{\X}( {\bf t} |\Y={\bf y})
&=\frac{ \nabla_{{\bf y}} \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ]   }{ \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] } \\
&=\frac{ \boldsymbol{\mathsf{K}}_{\N}^{-1}   \boldsymbol{\mathsf{Cov}} ( \X, U | \Y={\bf y}) }{ \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] } \\
&=\frac{ \boldsymbol{\mathsf{K}}_{\N}^{-1} \left(  \E[  \X \eu^{ {\bf t}^\mathsf{T} \X} | \Y={\bf y}  ]  -\E[ \X |\Y={\bf y}] \E[  \eu^{ {\bf t}^\mathsf{T} \X}  | \Y={\bf y}]  \right) }{ \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] }  \\
&= \boldsymbol{\mathsf{K}}_{\N}^{-1} \left( \nabla_{\bf t}   \log \left(  \E[  \eu^{ {\bf t}^\mathsf{T} \X}  | \Y={\bf y}] \right)   -\E[ \X |\Y={\bf y}]   \right) \label{eq:Gradeint_Log_Property} \\
&= \boldsymbol{\mathsf{K}}_{\N}^{-1}  \nabla_{\bf t} K_{\X}( {\bf t} |\Y={\bf y})   -  \boldsymbol{\mathsf{K}}_{\N}^{-1}  \E[ \X |\Y={\bf y}],
\end{align}

where in (<ref>) we have used that $\frac{\E[  \X \eu^{ {\bf t}^\mathsf{T} \X} | \Y={\bf y}  ]}{\E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ]} = \frac{ \nabla_{\bf t} \E[  \eu^{ {\bf t}^\mathsf{T} \X} | \Y={\bf y}  ]}{\E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ]}=\nabla_{\bf t}   \log \left(  \E[  \eu^{ {\bf t}^\mathsf{T} \X}  | \Y={\bf y}] \right)$.

Consequently, the partial derivative with respect to $i$ is given by

\begin{equation}
\frac{\partial }{ \partial y_i } K_{\X}( {\bf t} |\Y={\bf y})
%& = [ \boldsymbol{\mathsf{K}}_{\N}^{-1}   ]_i^T   \nabla_{\bf t} K_{\X}( {\bf t} |\Y={\bf y}) -  [ \boldsymbol{\mathsf{K}}_{\N}^{-1}   ]_i^T  \E[ \X |\Y={\bf y}] \\
= {\bf k}_i^\mathsf{T}  \nabla_{\bf t} K_{\X}( {\bf t} |\Y={\bf y}) -  {\bf k}_i^\mathsf{T}   \E[ \X |\Y={\bf y}],  \label{eq:PartialDerivative_of_cumulant_gen_fun}
\end{equation}

where we have used that  ${\bf k}_i^\mathsf{T} =\mathbf{e}_i^\mathsf{T} \boldsymbol{\mathsf{K}}_{\N}^{-1} $    (i.e., the $i$-th row of $\boldsymbol{\mathsf{K}}_{\N}^{-1}$).

Next, by differentiating with respect to $j$, we arrive at

\begin{align}
\frac{\partial^2 }{ \partial y_j   \partial y_i} K_{\X}( {\bf t} |\Y={\bf y})   &= \frac{\partial }{ \partial y_j   }  \left( {\bf k}_i^\mathsf{T}   \nabla_{\bf t} K_{\X}( {\bf t} |\Y={\bf y}) -  {\bf k}_i^\mathsf{T}      \E[ \X |\Y={\bf y}]  \right)\\
&=  {\bf k}_i^\mathsf{T}   \nabla_{\bf t}   {\bf k}_j^\mathsf{T}   \nabla_{\bf t} K_{\X}( {\bf t} |\Y={\bf y}) -  {\bf k}_i^\mathsf{T}   \frac{\partial }{ \partial y_j   }   \E[ \X |\Y={\bf y}]  ,\label{eq:using_partial_derivative_Expression}
\end{align}

where   (<ref>) comes from using the partial derivative formula in  (<ref>).

§ PROOF OF PROPOSITION <REF>

To see this note that $\frac{\partial^{j}  K_{\X}( {\bf t} |\Y={\bf y})  }{ \partial y_{s_1} \dots  \partial y_{s_{j}}   } |_{{\bf t}={\bf 0}} =0$ for every $j$

\begin{align}
\frac{\partial^{j}  K_{\X}( {\bf t} |\Y={\bf y})  }{ \partial y_{s_1} \dots  \partial y_{s_{j}}   } &=\frac{\partial^{j}  \log\left( \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] \right)  }{ \partial y_{s_1} \dots  \partial y_{s_{j}}   }\\
&=\frac{\partial^{j-1}   }{ \partial y_{s_1} \dots  \partial y_{s_{j-1}}}  \frac{\frac{\partial   }{ \partial y_{s_j}}    \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] }{ \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] }\\
&=  \frac{ g({\bf y})}{ ( \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] )^{ \max(1,2(j-1))}}. \label{eq:Gen_Quotion_Proof_Cumulant}
\end{align}

We do not attempt to find the exact expression for  $g({\bf y})$ and only observe that it contains terms of the form  $\frac{\partial^{k}   }{ \partial y_{s_1} \dots  \partial y_{s_{k}}}   \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] $ for some $k \ge 1$. We next show that $\frac{\partial^{k}   }{ \partial y_{s_1} \dots  \partial y_{s_{k}}}   \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] $ evaluated at ${\bf t}= {\bf 0}$ is equal to zero, which through  (<ref>) will lead to the desired conclusion.      To do this we use  the  Taylor expression for the multivariate moment generating function  given by <cit.>

\begin{align}
\E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] =1+  \sum_{j=1}^\infty \sum_{ {\bf s} \in S(j)} \frac{1}{j!} \mu({\bf y}; s_1,...,s_j) t_{s_1} \dots t_{s_j} ,
\end{align}

where  $\mu({\bf y}; s_1,...,s_j)=\E[ X_{s_1} \dots X_{s_j} | \Y={\bf y} ] $ and $S(j)=\{1,\ldots, n\}^j$ is set of all vectors of integers with $j$ components and all entries between $1$ and $n$.  Now we have that

\begin{align}
\frac{\partial^{k}   }{ \partial y_{s_1} \dots  \partial y_{s_{k}}}   \E[\eu^{ {\bf t}^\mathsf{T} \X}| \Y={\bf y} ] \Big |_{ {\bf t}={\bf 0} }
& =  \sum_{j=1}^\infty \sum_{ {\bf s} \in S(j)} \frac{1}{j!}  \frac{\partial^{k}   }{ \partial y_{s_1} \dots  \partial y_{s_{k}}}   \mu({\bf y}; s_1,...,s_j) t_{s_1} \dots t_{s_j}   \Big |_{ {\bf t}={\bf 0} } \\
\end{align}

This concludes the proof.

§ PROOF OF PROPOSITION <REF>

The proof of (<ref>) follows by applying  Hatsell and Nolte identity in (<ref>)  to the expressions in  Proposition <ref> together with the identity  $  \boldsymbol{\mathsf{D}}^2_\mathbf{x} f({\bf x})=   \boldsymbol{\mathsf{J}}_\mathbf{x}  \nabla_{\bf x} f(\mathbf{x}) $.

To show the general case observe that

\begin{align}
\boldsymbol{\mathsf{D}}^2_{\bf y}   \log \left(   \mathbb{P}[\X \in \mathcal{A} | \Y={\bf y}] \right)
&= \boldsymbol{\mathsf{J}}_\mathbf{y}  \nabla_{\bf y}    \log \left(   \mathbb{P}[\X \in \mathcal{A} | \Y={\bf y}] \right) \label{eq:Hessian_Jacobian_Gradient_idenity}\\
&= \boldsymbol{\mathsf{J}}_\mathbf{y}  \boldsymbol{\mathsf{K}}_{\N}^{-1}    (  \E[  \X  | \Y={\bf y}, \X \in \mathcal{A}] -  \E[  \X   | \Y={\bf y}]     ) \label{eq:Using_Gradient_Indeity_cond_dist} \\
&= \boldsymbol{\mathsf{J}}_\mathbf{y}     \left(  \frac{ \E[  \X \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y}]}{ \mathbb{P}[\X \in \mathcal{A}| \Y={\bf y}]} -  \E[  \X   | \Y={\bf y}]    \right )   \boldsymbol{\mathsf{K}}_{\N}^{- 1} \label{eq:Jacobian_of_linear_Transf}\\
%      &=  \Big(   \frac{  \boldsymbol{\mathsf{J}}_\mathbf{y}    \E[  \X \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y}]}{ \mathbb{P}[\X \in \mathcal{A}| \Y={\bf y}]}    \notag\\
%     &\quad -   \frac{\nabla \mathbb{P}[\X \in \mathcal{A}| \Y={\bf y}]  \E^\mathsf{T}[  \X \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y}] }{ \mathbb{P}^2[\X \in \mathcal{A}| \Y={\bf y}] }  \notag  \\
%     &\quad  -\boldsymbol{\mathsf{J}}_\mathbf{y}  \E[  \X   | \Y={\bf y}]   \Big)   \boldsymbol{\mathsf{K}}_{\N}^{- \mathsf{T} }\\
&=  \Big(   \frac{   \boldsymbol{\mathsf{K}}_{\N}^{-1}   \boldsymbol{\mathsf{Cov}} ( \X, \X \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y})  } { \mathbb{P}[\X \in \mathcal{A}| \Y={\bf y}]}     \notag\\
&\quad -   \frac{ \boldsymbol{\mathsf{K}}_{\N}^{-1}   \boldsymbol{\mathsf{Cov}} ( \X,  \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y})  \E^\mathsf{T}[  \X \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y}] }{ \mathbb{P}^2[\X \in \mathcal{A}| \Y={\bf y}] }  \notag  \\
&\quad  - \boldsymbol{\mathsf{K}}_{\N}^{-1}  \boldsymbol{\mathsf{Var}}(\X | \Y={\bf y})  \Big)   \boldsymbol{\mathsf{K}}_{\N}^{- 1 } \label{eq:Using_Main_Identity}\\
&=  \boldsymbol{\mathsf{K}}_{\N}^{-1} \Big(   \E[ \X \X^{\mathsf{T}} | \Y={\bf y}, \X \in \mathcal{A}]   \notag\\
&\quad -  \E[ \X   | \Y={\bf y}, \X \in \mathcal{A}]  \E[  \X^{\mathsf{T}} | \Y={\bf y}, \X \in \mathcal{A}] \notag\\
& \quad - \boldsymbol{\mathsf{K}}_{\N}^{-1}  \boldsymbol{\mathsf{Var}}(\X | \Y={\bf y})  \Big) \label{eq:Rewritting_ConditionalCovariances}  \\
&=  \boldsymbol{\mathsf{K}}_{\N}^{-1} \left( \boldsymbol{\mathsf{Var}}(\X | \Y={\bf y}, \X \in \mathcal{A}) - \boldsymbol{\mathsf{Var}}(\X | \Y={\bf y})     \right) \boldsymbol{\mathsf{K}}_{\N}^{- 1 }, \label{eq:Using_Definition_Conditiona_Variance}
\end{align}

where (<ref>) follows by using the identity  $  \boldsymbol{\mathsf{D}}^2_\mathbf{x} f({\bf x})=   \boldsymbol{\mathsf{J}}_\mathbf{x}  \nabla_{\bf x} f(\mathbf{x}) $; (<ref>) follows by using  (<ref>);  (<ref>) follows by using the property that $  \boldsymbol{\mathsf{J}}_{\bf x}   \boldsymbol{\mathsf{K}}_{\N}^{-1} f(\mathbf{x}) =  \boldsymbol{\mathsf{J}}_{\bf x}  f(\mathbf{x})   \boldsymbol{\mathsf{K}}_{\N}^{- \mathsf{T} } =\boldsymbol{\mathsf{J}}_{\bf x}  f(\mathbf{x})   \boldsymbol{\mathsf{K}}_{\N}^{- 1 } $; (<ref>) follows by using identity in (<ref>) with $\U= \X \mathsf{1}_{ \mathcal{A} }(\X)$ and the quotient rule for differentiation;
(<ref>) follows by   rewriting the first covariance term as

\begin{align}
\frac{     \boldsymbol{\mathsf{Cov}} ( \X, \X \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y})  } { \mathbb{P}[\X \in \mathcal{A}| \Y={\bf y}]}
% &=   \frac{     \E[ \X \X^{\mathsf{T}} \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y}] - \E[ \X   | \Y={\bf y}]  \E[  \X^{\mathsf{T}} \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y}]    } { \mathbb{P}[\X \in \mathcal{A}| \Y={\bf y}]} \\
= \E[ \X \X^{\mathsf{T}} | \Y={\bf y}, \X \in \mathcal{A}]   - \E[ \X   | \Y={\bf y}]  \E[  \X^{\mathsf{T}} | \Y={\bf y}, \X \in \mathcal{A}] ,
\end{align}

and the second covariance term as

\begin{align}
&\frac{   \boldsymbol{\mathsf{Cov}} ( \X,  \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y})  \E^\mathsf{T}[  \X \mathsf{1}_{ \mathcal{A} }(\X)  | \Y={\bf y}] }{ \mathbb{P}^2[\X \in \mathcal{A}| \Y={\bf y}] }\\
&\quad=  \E[ \X   | \Y={\bf y}, \X \in \mathcal{A}]  \E[  \X^{\mathsf{T}} | \Y={\bf y}, \X \in \mathcal{A}] -\E[ \X   | \Y={\bf y}]  \E[  \X^{\mathsf{T}} | \Y={\bf y}, \X \in \mathcal{A}];  \text{ and}
\end{align}

and (<ref>) follows from the definition of conditional variance.
This concludes the proof.

§ PROOF OF THEOREM <REF>

First, assume that

\begin{equation}
\sup_{|y| \le t_n} |  \widehat{f}_Y^{(m)}(y)-f^{(m)}_Y(y) | \le \epsilon_n,   m \in [0, \ldots, k] . \label{eq:EpsilonAssumption}
\end{equation}

Second, using the generalized TRE identity in  (<ref>)  and the expression for $\widehat{m}_k(y)$ in (<ref>), we have that

\begin{equation}
\frac{1}{\sigma^{2k} }\left|  \E[   X^k |Y=y ]    -\widehat{m}_k(y)  \right|
\le     \sum_{m=0}^k
\frac{  {{k} \choose {m}}  \left|  (-i)^m H_{e_m} \left( i \frac{y}{\sigma} \right) \right|}{\sigma^m}
\left|    \frac{  \widehat{f}_Y^{(k-m)}(y)   }{ \widehat{f}_Y(y)}  -  \frac{ f_Y^{(k-m)}(y)   }{f_Y(y)}    \right| , \label{eq:afterTriangleInequality}
\end{equation}

where the second absolute value term can be bounded as

\begin{align}
\left|    \frac{  \widehat{f}_Y^{(k-m)}(y)   }{ \widehat{f}_Y(y)}  -  \frac{ f_Y^{(k-m)}(y)   }{f_Y(y)}    \right|
&  =    \left|    \frac{  \widehat{f}_Y^{(k-m)}(y) f_Y(y)- f_Y^{(k-m)}(y)  \widehat{f}_Y(y) }{ \widehat{f}_Y(y) f_Y(y)}     \right| \\
% &  =    \left|    \frac{  \widehat{f}_Y^{(k-m)}(y) f_Y(y)-  f_Y^{(k-m)}(y)  f_Y(y)+f_Y^{(k-m)}(y)  f_Y(y)  - f_Y^{(k-m)}(y)  \widehat{f}_Y(y) }{ \widehat{f}_Y(y) f_Y(y)}     \right| \\
& \le  \left|    \frac{  \widehat{f}_Y^{(k-m)}(y) -  f_Y^{(k-m)}(y)  }{ \widehat{f}_Y(y) }     \right|  +   \left|    \frac{ (   f_Y(y)- \widehat{f}_Y(y) )  f_Y^{(k-m)}(y) }{ \widehat{f}_Y(y)  f_Y(y)}     \right| \\
& \le  \frac{\epsilon_n}{ \widehat{f}_Y(y) } +  \epsilon_n  \frac{  \left|    f_Y^{(k-m)}(y)  \right|  }{ \widehat{f}_Y(y)  f_Y(y)}    ,  \label{eq:BoundOnABSvalue}
\end{align}

where in the last step we have used the assumption in (<ref>).

The following lemma, whose proof can be found in Appendix <ref>, will be useful to further bound the terms in (<ref>).
Let $\E[X^2]<\infty$ and assume (<ref>) holds.  Let   $ \psi_\sigma(y)= \sqrt{2 \pi \sigma^2}  \eu^{\frac{ y^2 +\E[X^2]}{  \sigma^2}} $ and assume that

\begin{equation}
\epsilon_n   \psi_\sigma(t_n) \le 1.
\end{equation}

Then,   for $|y| \le t_n$

\begin{align}
\frac{1}{f_Y(y)} &\le \psi_\sigma(y),  \label{eq:B1}  \\
\frac{1}{ \widehat{f}_Y(y) } & \le  \frac{1}{1-\epsilon_n  \psi_\sigma(y) }   \psi_\sigma(y), \label{eq:B2}  \\
\left|    f_Y^{(k)}(y)  \right|  & \le    \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{\sqrt{k!}}{\sigma^k}  , \label{eq:B3} \\
\left|  H_{e_m} \left( i \frac{y}{\sigma} \right) \right| &\le  \sqrt{ m!} \eu^{ \frac{y^2}{4\sigma^2}} \le  \frac{\sqrt{ m!}}{\sqrt{ 2 \pi \sigma^2}}  \psi_\sigma(y) , \label{eq:B4} \\
\delta_{r,a}&=   \max_{t \in \mathbb{R}}\left| \mathbb{E}[ \widehat{f}_Y^{(r)}(t)]-f_Y^{(r)}(t) \right | \le   a   \sqrt{   \frac{ 4  (r+1)! }{ 3 \pi\sigma^{2(r+1)}}  },  \label{eq:B5}  \\
v_r&= \int  \left | k^{(r+1)}(x) \right|  {\rm d} x  \le  \sqrt{(r+1)!} \sqrt{ \frac{2}{3}} \label{eq:B6}  .
\end{align}

Combining (<ref>), (<ref>) and (<ref>)-(<ref>),  we arrive at

\begin{align}
\sup_{ |y| \le  t_n} \left|  \E[   X^k |Y=y ]    -\widehat{m}_k(y)  \right|
& \le  C_{1,\sigma, k}     \frac{\epsilon_n  \psi_\sigma^2(t_n)   }{1-\epsilon_n  \psi_\sigma(t_n) }  \left(1+ C_{2,\sigma, k}   \psi_\sigma(t_n)    \right) \\
&=\varepsilon_n,  \label{Eq:error_between_condtionals}
\end{align}

\begin{equation}
C_{1,\sigma, k} =   \sum_{m=0}^k
\frac{  {{k} \choose {m}}\sqrt{m!}}{\sigma^m}   ,  \,   C_{2,\sigma, k}=  \sqrt{\frac{2}{3}}  \max_{ m \in 0,\ldots, k}   \frac{ \sqrt{m!} }{\sigma^m}  .
\end{equation}

Now, choose $\epsilon_n >   \max_{m \in [0,\ldots, n]} \delta_{m,a} $ and observe that

\begin{align}
\mathbb{P} \left [  \sup_{ |y| \le  t_n}   \left|  \E[   X^k |Y=y ]    -\widehat{m}_k(y)  \right|   \ge \varepsilon_n   \right]
& \le  \sum_{m=0}^k  \mathbb{P} \left[   \sup_{ |y| \le  t_n}  |  \widehat{f}_Y^{(m)}(y)-f^{(m)}_Y(y) | >\epsilon_n  \right] \label{eq:Implication_for_error}\\
&  \le  \sum_{m=0}^k 2 \eu^{-2n \frac{a^{2m+2} (\epsilon_n - \delta_{m,a})^2}{ v_m^2} } ,\label{Eq:using_schuster_results}
\end{align}

where in (<ref>) we have used the fact that (<ref>) leads to (<ref>);  and in (<ref>) is due to the bound in  <cit.>.  Therefore, to complete the proof,  we need choose $\epsilon_n, a$ and $t_n$ such that

\begin{align}
&\lim_{n \to \infty} \epsilon_n  \psi_\sigma^3(t_n)=0,  \\
& \lim_{n \to \infty}  t_n \to \infty,\\
& \epsilon_n  >   \delta_{m,a}, \forall \, m \in [0,\ldots, n], \\
&  \lim_{n \to \infty} n a^{2m+2} (\epsilon_n - \delta_{m,a})^2= \infty  , \forall \,   m \in [0,\ldots, k],
\end{align}

The following choice satisfies the above equations:

\begin{align}
a&=  \frac{1}{n^u},  u \in \left(0, \frac{1}{2k +4}  \right), \\
\epsilon_n&= 2\delta_{m,a}=2  a  \max_{m \in [0,\ldots, k] }   \sqrt{   \frac{ 4  (k+1)! }{ 3 \pi\sigma^{2(k+1)}}  }, \\
t_n&= \frac{\sigma^2  \sqrt{ w  \log(n)} }{3} ,  w \in (0,u),
\end{align}

and, for large enough $n$, result in

\begin{equation}
\varepsilon_n \le  \frac{C_{k,\sigma} }{n^{u-w}},
\end{equation}

where the constant $C_{k,\sigma}$  is independent of $n$.

§ PROOF OF LEMMA <REF>

To show (<ref>), we use Jensen's inequality and the bound $(a+b)^2 \le 2 (a^2+b^2)$

\begin{align}
f_Y(y) &=  \E \left[  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \eu^{- \frac{(y-X)^2}{2 \sigma^2}} \right]\\
& \ge    \frac{1}{ \sqrt{2 \pi \sigma^2}}  \eu^{- \frac{  \E \left[(y-X)^2 \right]}{2 \sigma^2}}\\
& \ge    \frac{1}{ \sqrt{2 \pi \sigma^2}}  \eu^{- \frac{ y^2 +\E[X^2]}{  \sigma^2}} = \frac{1}{ \psi_\sigma(y) }.
\end{align}

To show (<ref>) we use the assumption in (<ref>) and the bound in  (<ref>)

\begin{align}
\frac{ 1 }{ \widehat{f}_Y(y)}& =   \frac{ 1 }{ \widehat{f}_Y(y)-  f_Y(y)  +   f_Y(y) }\\
& \le  \frac{ 1 }{    f_Y(y)  -\epsilon_n} \label{eq:TheUglyBound2}\\
& =   \frac{ 1 }{   1- \frac{\epsilon_n}{  f_Y(y) } } \frac{1}{  f_Y(y) }\\
&\le \frac{ 1 }{   1- \epsilon_n \psi(y) } \psi(y).
\end{align}

Next,  recall the following inequality <cit.>:

\begin{equation}
\left| H_{\eu_{r+1}}(x)   \right| \le  \sqrt{(r+1)!} \eu^{ \frac{x^2}{4} }. \label{eq:BoundOnHermitePolynomial}
\end{equation}

First, the  above  inequality  immediately leads to the proof of  (<ref>).   Second,  to show (<ref>),  observe the following sequence of steps:

\begin{align}
\left|  f_Y^{(k)}(t)  \right|&=  \left| \frac{ {\rm d}^{k}}{  {\rm d} t^{k}} \E \left[  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \eu^{- \frac{(t-X)^2}{2 \sigma^2}} \right]  \right| \\
&= \left| \E \left[  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{ {\rm d}^{k}}{  {\rm d} t^{k}}  \eu^{- \frac{(t-X)^2}{2 \sigma^2}} \right] \right| \\
&= \left|  \E \left[  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{(-1)^k}{\sigma^k} H_{e_k} \left( \frac{t-X}{ \sigma}  \right)  \eu^{- \frac{(t-X)^2}{2 \sigma^2}} \right] \right| \\
&\le  \E \left[  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{1}{\sigma^k} \left|  H_{e_k}  \left( \frac{t-X}{ \sigma}  \right) \right|   \eu^{- \frac{(t-X)^2}{2 \sigma^2}} \right] \\
& \le  \E \left[  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{1}{\sigma^k}  \sqrt{k!} \eu^{ \frac{(t-X)^2}{4 \sigma^2} } \eu^{- \frac{(t-X)^2}{2 \sigma^2}} \right]  \label{eq:UsingHermitePolynomial}\\
%& =  \E \left[  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{1}{\sigma^k}  \sqrt{k!} \eu^{-3 \frac{(t-X)^2}{4 \sigma^2}} \right] \\
& \le   \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{\sqrt{k!}}{\sigma^k}  ,  \label{eq:bound_exp(-x) <=1}
\end{align}

where the inequality in (<ref>) follows from the inequality in (<ref>); and the  inequality in (<ref>) follows by using $ \eu^{-3 \frac{(t-X)^2}{4 \sigma^2}} \le 1$.

To show (<ref>), first  note that

\begin{equation}
\mathbb{E}[\widehat{f}_Y^{(r)}(t)]=  \int  \frac{1}{a} \frac{ {\rm d}^r }{ {\rm d} t^r}  k \left( \frac{t-y}{a} \right)   f_Y(y) {\rm d} y  = \int  \frac{1}{a}   k \left( \frac{t-y}{a} \right)   f_Y^{(r)}(y) {\rm d} y  ,
\end{equation}

where we have used integration by parts. Then, the bias can be bounded as follows:

\begin{align}
\left| \mathbb{E}[\widehat{f}_Y^{(r)}(t)]-f_Y^{(r)}(t) \right |
&=  \left| \int  \frac{1}{a}   k \left( \frac{t-y}{a} \right)  \left(  f_Y^{(r)}(y) -f_Y^{(r)}(t) \right){\rm d} y  \right| \\
&=   \left| \int     k \left( y \right)  \left(  f_Y^{(r)}(t+a y) -f_Y^{(r)}(t) \right){\rm d} y   \right| \\
&\le  \sup_{t \in \mathbb{R}} \left| f_Y^{(r+1)}(t)  \right| \int     k \left( y \right)  a  |y|  {\rm d} y      \\
&= a \sqrt{ \frac{2}{\pi}}     \sup_{t \in \mathbb{R}} \left| f_Y^{(r+1)}(t)  \right| \\
& \le  \frac{1}{ \sqrt{2 \pi \sigma^2}}  \frac{\sqrt{k!}}{\sigma^k},
\label{eq:BoundOnDifferenceOfExpectedValue}
\end{align}

where the last bound is due to (<ref>).

Finally, to show (<ref>),  we use the inequality in (<ref>)

\begin{align}
v_r&= \int  \left | k^{(r+1)}(x) \right|  {\rm d} x \\
&=  \int         \left| H_{\eu_{r+1}}(x)  k(x)  \right| {\rm d} x \\
&\le   \int   \sqrt{(r+1)!} \eu^{ \frac{x^2}{4} } k(x) {\rm d} x \\
&=  \sqrt{(r+1)!} \sqrt{ \frac{2}{3}}.
\end{align}

This concludes the proof.

§ PROOF OF LEMMA <REF>

The proof largely follows the derivations in [14] and [15] and explicitly states the constants of the approximation.

To show (<ref>), we use  Taylor's remainder theorem

\begin{align}
f(x+ht)&= f(x)+ ht f'(x) + \ldots +  \frac{ (h t)^k}{k!} f^{(k)}(x)  + \frac{(h t)^{k+1}}{ (k+1)!} f^{(k+1)}(x) + \frac{(ht)^{k+2}}{ (k+2)!}  f^{(k+2)}(\tau),
\end{align}

for some $\tau$ between $x$ and $x+ht$, which leads to

\begin{align}
D_h^{(k)} f(x)&= \frac{c_k}{h^k }  \int_{-1}^1 f(x+h t)  P_k(t) {\rm d} t \\
&= f^{(k)}(x)   +   \frac{c_k h^2}{(k+2)! }  \int_{-1}^1 f^{(k+2)}(\tau)  t^{k+2} P_k(t) {\rm d} t,
\end{align}

where we have used the following properties of the Legendre polynomials <cit.>:

\begin{align}
\int_{-1}^1 t^m P_k(t) {\rm d} t&= 0, \,  m\in [0:k-1],\\
\int_{-1}^1 t^k P_k(t) {\rm d} t&= \frac{k!}{c_k} ,  \\
\int_{-1}^1 t^{k+1} P_k(t) {\rm d} t&= 0 .
\end{align}

\begin{align}
|D_h^{(k)} f(x)-  f^{(k)}(x) |
&\le   \frac{c_k h^2}{(k+2)! }  \int_{-1}^1 |  f^{(k+2)}(\tau)  t^{k+2} P_k(t) |  {\rm d} t\\
&\le   \frac{c_k h^2}{(k+2)! }  M_{k+2}  \int_{-1}^1 |   P_k(t) |  {\rm d} t \label{eq:Bound_f_tau}\\
&\le   \frac{c_k h^2}{(k+2)! }  M_{k+2}   \frac{2}{ \sqrt{  2k+1}}  \label{eq:Lagender_Polynomial_bound_jensen}\\
&= \alpha_k  M_{k+2} h^2 ,
\end{align}

where (<ref>) follows by using that   $\tau$  is between $x$ and $x+ht$ and hence $|f^{(k+2)}(\tau) | \le M_{k+2}$;  and (<ref>) follows by using Jensen's inequality and $\int_{-1}^1 |   P_k(t) |^2  {\rm d} t = \frac{2}{2k+1}$ to show that

\begin{equation}
\int_{-1}^1|P_k(t)| {\rm d} t   \le   2 \sqrt{ \int_{-1}^1|P_k(t)|^2  \frac{1}{2} {\rm d} t  } = \frac{2}{ \sqrt{  2k+1}}.  \label{eq:norm_Legender_polynomial}
\end{equation}

This completes the proof of the bound in (<ref>).

To show (<ref>) observe the following sequence of steps:

\begin{align}
| D_h^{(k)} g(x) -  f^{(k)}(x) |
& \le  | D_h^{(k)} f(x) -  f^{(k)}(x) | +  | D_h^{(k)} g(x) -  D_h^{(k)} f(x) | \label{eq:Apply_Triangular_Inequality_Lancos}\\
& =  \alpha_k  M_{k+2} h^2   +  \left|  \frac{c_k}{h^k }  \int_{-1}^1 \left( g(x+h t) - f(x+h t) \right) P_k(t) {\rm d} t      \right|\\
& \le  \alpha_k  M_{k+2} h^2   +   \frac{c_k}{h^k }  \epsilon  \int_{-1}^1|P_k(t)| {\rm d} t   \label{eq:bound_Lancos_derivative_error_applying}   \\
& \le \alpha_k  M_{k+2} h^2    +   \frac{c_k}{h^k }  \epsilon  \sqrt{ \frac{2}{2k+1}} \label{eq:Lagender_Polynomial_bound_jensen_v2}  \\
& = \alpha_k  M_{k+2} h^2    +    \frac{\beta_k   \epsilon}{ h^k}  ,
\end{align}

where (<ref>) follows by using the triangular inequality;  (<ref>) follows by using that $\sup_{x \in I_h} |f (x)-g(x)| \le \epsilon$; and (<ref>) follows by using the bound in (<ref>).
This completes the proof.

[1]
A. Dytso, H. V. Poor, and S. Shamai (Shitz), “A general derivative identity
for the conditional mean estimator in Gaussian noise and some
applications,” in Proc. IEEE Int. Symp. Inf. Theory.1em plus
0.5em minus 0.4emLos Angeles, CA, USA: IEEE, 2020, pp. 1183–1188.

[2]
——, “On the distribution of the conditional mean estimator in Gaussian
noise,” in Proc. IEEE Inf. Theory Workshop.1em plus 0.5em
minus 0.4emRiva del Garda, Italy: IEEE, 2021, to appear.

[3]
A. Banerjee, X. Guo, and H. Wang, “On the optimality of conditional
expectation as a Bregman predictor,” IEEE Trans. Inf. Theory,
vol. 51, no. 7, pp. 2664–2669, 2005.

[4]
D. Guo, S. Shamai, and S. Verdú, The Interplay Between Information
and Estimation Measures.1em plus 0.5em minus 0.4emnow
Publishers Incorporated, 2013.

[5]
D. P. Palomar and S. Verdú, “Gradient of mutual information in linear
vector Gaussian channels,” IEEE Trans. Inf. Theory, vol. 52, no. 1,
p. 141, 2006.

[6]
B. Efron, “Local false discovery rates,” 2005.

[7]
B. Efron and T. Hastie, Computer Age Statistical Inference.1em
plus 0.5em minus 0.4emCambridge University Press, 2016, vol. 5.

[8]
A. G. Jaffer and S. C. Gupta, “On relations between detection and estimation
of discrete time processes,” Inf. Control, vol. 20, no. 1, pp.
46–54, 1972.

[9]
H. Robbins, “An empirical Bayes approach to statistics,” in Proc.
Third Berkeley Symp. Math Statist. Probab.1em plus 0.5em minus
0.4emCiteseer, 1956.

[10]
R. Esposito, “On a relation between detection and estimation in decision
theory,” Inf. Control, vol. 12, no. 2, pp. 116–120, February 1968.

[11]
A. Dytso, M. Al, H. V. Poor, and S. Shamai (Shitz), “On the capacity of the
peak power constrained vector Gaussian channel: An estimation theoretic
perspective,” IEEE Trans. Inf. Theory, vol. 65, no. 6, pp.
3907–3921, 2019.

[12]
D. Guo, S. Shamai, and S. Verdú, “Mutual information and minimum
mean-square error in Gaussian channels,” IEEE Trans. Inf. Theory,
vol. 51, no. 4, pp. 1261–1282, 2005.

[13]
C. Lanczos, Applied Analysis.1em plus 0.5em minus 0.4emPrentice Hall, 1956.

[14]
C. Groetsch, “Lanczos' generalized derivative,” The American
Mathematical Monthly, vol. 105, no. 4, pp. 320–326, 1998.

[15]
S. Rangarajan and S. P. Purushothaman, “Lanczos' generalized derivative for
higher orders,” J. Comput Appl. Math, vol. 177, no. 2, pp. 461–465,

[16]
J. Shen, “On the generalized `lanczos' generalized derivative,” The
American Mathematical Monthly, vol. 106, no. 8, pp. 766–768, 1999.

[17]
C. Hatsell and L. Nolte, “Some geometric properties of the likelihood ratio
(corresp.),” IEEE Trans. Inf. Theory, vol. 17, no. 5, pp. 616–618,

[18]
Y. Wu and S. Verdú, “Functional properties of minimum mean-square error
and mutual information,” IEEE Trans. Inf. Theory, vol. 58, no. 3, pp.
1289–1301, 2012.

[19]
T. T. Cai and Y. Wu, “Optimal detection of sparse mixtures against a given
null distribution,” IEEE Trans. Inf. Theory, vol. 60, no. 4, pp.
2217–2232, 2014.

[20]
A. G. Jaffer, “A note on conditional moments of random signals in Gaussian
noise (corresp.),” IEEE Trans. Inf. Theory, vol. 18, no. 4, pp.
513–514, 1972.

[21]
J. A. Shohat and J. D. Tamarkin, The Problem of Moments.1em
plus 0.5em minus 0.4emAmerican Mathematical Soc., 1943, no. 1.

[22]
D. Guo, Y. Wu, S. Shamai, and S. Verdú, “Estimation in Gaussian noise:
Properties of the minimum mean-square error,” IEEE Trans. Inf.
Theory, vol. 57, no. 4, pp. 2371–2385, 2011.

[23]
A. Dytso and H. V. Poor, “Estimation in Poisson noise: Properties of the
conditional mean estimator,” IEEE Trans. Inf. Theory, vol. 66, no. 7,
pp. 4304–4323, 2020.

[24]
M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with
Formulas, Graphs, and Mathematical Table.1em plus 0.5em minus
0.4emNational Bureau of Standards Applied Mathematics series 55, 1965.

[25]
C. A. Charalambides, Enumerative Combinatorics.1em plus 0.5em
minus 0.4emCRC Press, 2018.

[26]
J. Arbel, O. Marchal, and H. D. Nguyen, “On strict sub-Gaussianity, optimal
proxy variance and symmetry for bounded random variables,” arXiv
preprint arXiv:1901.09188, 2019.

[27]
S. G. Krantz and H. R. Parks, A Primer of Real Analytic
Functions.1em plus 0.5em minus 0.4emSpringer Science &
Business Media, 2002.

[28]
J. E. Kolassa, Series Approximation Methods in Statistics.1em
plus 0.5em minus 0.4emSpringer Science & Business Media, 2006,
vol. 88.

[29]
J. C. Berry, “Minimax estimation of a bounded normal mean vector,” J.
Multivar Anal., vol. 35, no. 1, pp. 130–139, 1990.

[30]
N. L. Johnson, S. Kotz, and N. Balakrishnan, Continuous Univariate
Distributions.1em plus 0.5em minus 0.4emJohn Wiley & Sons,
Ltd, 1995.

[31]
A. Dytso, H. V. Poor, R. Bustin, and S. Shamai, “On the structure of the least
favorable prior distributions,” in Proc. IEEE Int. Symp. Inf.
Theory.1em plus 0.5em minus 0.4emVail, CO, USA: IEEE, 2018,
pp. 1081–1085.

[32]
M. Ledoux, “Concentration of measure and logarithmic Sobolev inequalities,”
in Seminaire de probabilites XXXIII.1em plus 0.5em minus
0.4emSpringer, 1999, pp. 120–216.

[33]
Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the
finite blocklength regime,” IEEE Trans. Inf. Theory, vol. 56, no. 5,
pp. 2307–2359, 2010.

[34]
J. Ziv and M. Zakai, “Some lower bounds on signal parameter estimation,”
IEEE Trans. Inf. Theory, vol. 15, no. 3, pp. 386–391, 1969.

[35]
E. Weinstein and A. J. Weiss, “A general class of lower bounds in parameter
estimation,” IEEE Trans. Inf. Theory, vol. 34, no. 2, pp. 338–342,

[36]
A. Dytso, M. Fauß, A. M. Zoubir, and H. V. Poor, “MMSE bounds for
additive noise channels under Kullback–Leibler divergence constraints on
the input distribution,” IEEE Trans. Signal Processing, vol. 67,
no. 24, pp. 6352–6367, 2019.

[37]
G. B. Folland, Real Analysis: Modern Techniques and Their
Applications.1em plus 0.5em minus 0.4emJohn Wiley & Sons,

[38]
W. Alghamdi and F. P. Calmon, “Polynomial approximations of conditional
expectations in scalar Gaussian channels,” arXiv preprint
arXiv:2102.05970, 2021.

[39]
T. Han, Information-Spectrum Methods in Information Theory.1em
plus 0.5em minus 0.4emSpringer Science & Business Media, 2013,
vol. 50.

[40]
S. Verdú, “Mismatched estimation and relative entropy,” IEEE Trans.
Inf. Theory, vol. 56, no. 8, pp. 3712–3720, 2010.

[41]
S. Chlaily, C. Ren, P.-O. Amblard, O. Michel, P. Comon, and C. Jutten,
“Information–estimation relationship in mismatched Gaussian channels,”
IEEE Signal Process. Lett., vol. 24, no. 5, pp. 688–692, 2017.

[42]
M. Chen and J. Lafferty, “Mismatched estimation and relative entropy in vector
Gaussian channels,” in Proc. IEEE Int. Symp. Inf. Theory.1em
plus 0.5em minus 0.4emIstanbul,Turkey: IEEE, 2013, pp. 2845–2849.

[43]
W. Huleihel and N. Merhav, “Analysis of mismatched estimation errors using
gradients of partition functions,” IEEE Trans. Inf. Theory, vol. 60,
no. 4, pp. 2190–2216, 2014.

[44]
P. Bhattacharya, “Estimation of a probability density function and its
derivatives,” Sankhyā: The Indian Journal of Statistics, Series
A, pp. 373–382, 1967.

[45]
Y. G. Dmitriev and F. Tarasenko, “On the estimation of functionals of the
probability density and its derivatives,” Theory of Probability & Its
Applications, vol. 18, no. 3, pp. 628–633, 1974.

[46]
W. Cao, A. Dytso, M. Faus, H. V. Poor, and G. Feng, “On
nonparametric estimation of the Fisher information,” in Proc. IEEE
Int. Symp. Inf. Theory, Los Angeles, CA, USA, 2020, pp. 2216–2221.

[47]
R. Bustin, M. Payaró, D. P. Palomar, and S. Shamai, “On MMSE crossing
properties and implications in parallel vector Gaussian channels,”
IEEE Trans. Inf. Theory, vol. 59, no. 2, pp. 818–844, 2013.

[48]
A. Dubkov and A. Malakhov, “Properties and interdependence of the cumulants of
a random variable,” Radiophysics and Quantum Electronics, vol. 19,
no. 8, pp. 833–839, 1976.

[49]
M. Fozunbal, “On regret of parametric mismatch in minimum mean square error
estimation,” in Proc. IEEE Int. Symp. Inf. Theory, Austin, TX, USA,
June 2010, pp. 1408–1412.

[50]
G. N. Watson, A Treatise on the Theory of Bessel Functions.1em
plus 0.5em minus 0.4emCambridge University Press, 1995.

[51]
E. F. Schuster, “Estimation of a probability density function and its
derivatives,” Ann. Appl. Stat., vol. 40, no. 4, pp. 1187–1195, 1969.


RESEARCH ARTICLE International Journal of Intelligent Systems
11affiliationtext: School of Information Science and Technology, University of
Science and Technology of China, Hefei, Anhui, 230022, China
22affiliationtext: School of Computing, National University of Singapore, Kent
Ridge, 119077, Singapore 33affiliationtext: College of Computer Science and
Technology, Zhejiang University, Hangzhou, Zhejiang, 310007, China Xiangnan
He, School of Information Science and Technology, University of Science and
Technology of China, Hefei, Anhui, 230022, China<EMAIL_ADDRESS>National Key
Research and Development Program of China, Grant/Award Number: 2020YFB1406703;
National Natural Science Foundation of China, Grant/Award Number: U19A2079,
61972372 and 62121002 The authors declared that they have no conflicts of
interest to this work. All persons who meet authorship criteria are listed as
authors, and all authors certify that they have participated sufficiently in
the work to take public responsibility for the content.

# Exploring Lottery Ticket Hypothesis in Media Recommender Systems

Yanfang Wang  Yongduo Sui  Xiang Wang  Zhenguang Liu  Xiangnan He

###### Abstract

Media recommender systems aim to capture users’ preferences and provide
precise personalized recommendation of media content. There are two critical
components in the common paradigm of modern recommender models: (1)
representation learning, which generates an embedding for each user and item;
and (2) interaction modeling, which fits user preferences towards items based
on their representations. In spite of great success, when a great amount of
users and items exist, it usually needs to create, store, and optimize a huge
embedding table, where the scale of model parameters easily reach millions or
even larger. Hence, it naturally raises questions about the heavy recommender
models: Do we really need such large-scale parameters? We get inspirations
from the recently proposed lottery ticket hypothesis (LTH), which argues that
the dense and over-parameterized model contains a much smaller and sparser
sub-model that can reach comparable performance to the full model. In this
paper, we extend LTH to media recommender systems, aiming to find the winning
tickets in deep recommender models. To the best of our knowledge, this is the
first work to study LTH in media recommender systems. With MF and LightGCN as
the backbone models, we found that there widely exist winning tickets in
recommender models. On three media convergence datasets — Yelp2018, TikTok and
Kwai, the winning tickets can achieve comparable recommendation performance
with only 29% ~48%, 7% ~10% and 3% ~17% of parameters, respectively.

###### keywords:

media recommender system, lottery ticket hypothesis, lightweight embedding,
model pruning, iterative magnitude-based pruning

##  1 Introduction

In the era of information explosion, media recommendation is becoming the core
of many online platforms, to accurately yield the information of interest that
meets user needs. Media recommender systems aim to provide precise
personalized recommendation for users to find their preferences from the
deluge of items. Towards better media recommendation, extensive deep
recommender models[1, 2, 3, 4] have been proposed to capture user preference
from behavioral data. In general, the common paradigm of these models can be
systematized as two critical components: (1) representation learning, which
creates a representation vector (i.e., embedding) for each single user and
item; and (2) interaction modeling, which fits the historical user-item
interactions and predicts the preference of a user to an item based on their
embeddings [5, 6]. Obviously, the capacity of recommender model depends
heavily on the representation ability of user and item embeddings, which are
influenced by the scale of parameters — an embedding with the larger size not
only delineates the characteristics of users and items better [7], but also
predicts the user-item interaction more precisely [8]. Although the large
embedding table brings obvious accuracy improvements, it suffers from two main
limitations:

(1) The massive parameters become the major obstacle for production deployment
and real-time prediction of deep recommender models. Specifically, in real-
world scenarios, the number of users and items is usually up to tens of
millions or even hundreds of millions. If each user (or item) is associated
with a certain dense embedding, it will bring extremely expensive costs of
memory and inference time to maintain the huge embedding table for all users
and items. A good case is the famous audio-visual media convergence
recommender system YouTube Recommendation [9], which projects a million videos
into a 256-dimensional vector space, producing an embedding table with 256
million model parameters.

(2) Interaction histories of different users usually contain varying item
numbers and sets, thus having different informativeness. Nevertheless, current
recommender models almost assign all users and items with the same embedding
size. Hence, unifying the embedding size might limit the representation
ability of user and item embeddings. Especially in a large-scale industrial
media recommendation scenario, it may cause serious over-parameterization and
over-fitting issues.

One prevalent solution is to adopt unstructured pruning (a.k.a. sparse
pruning) [10] on the user-item embedding table. As a branch of neural network
pruning technology, sparse pruning aims to refine sparse sub-networks with
similar performance but fewer parameters by removing redundant parameters of
dense networks. In traditional sparse pruning, a large over-parameterized
dense network is required to be trained first, followed by pruning and fine-
tuning. Obviously, training a large dense network is expensive. Therefore,
some researchers [11] suggested that, rather than training a large dense
network and then pruning it into a small sparse sub-network, it is better to
train a small sparse sub-network from the scratch. This view is normally
considered infeasible in previous studies, because large dense networks have
wide parameter search spaces to find optimum solution through independent
training, while small sparse networks merely have limited parameter search
spaces.

More recently, Frankle and Carbin [11] proposed Lottery Ticket Hypothesis
(LTH): a large and dense deep neural network contains a small sparse sub-
network, which can match the test accuracy of the original large network for
at most the same number of iterations when trained independently. This
trainable sparse sub-network is called a Winning Ticket. At present, LTH has
been verified in the fields of Computer Vision (CV) [11] and Natural Language
Processing (NLP) [12]. However, to the best of our knowledge, there is no
relevant research in the field of recommendation. If we can verify the
existence of winning tickets and find them in deep recommender models, then
the model parameters can be effectively reduced while preserving the test
performance. Benefiting from the technique of sparse matrix storage [13], we
can not only reduce the memory usage, but also speed up the inference.

In this work, we explore LTH in media recommender systems. Specifically, we
focus on the widely-used model parameters — the user-item embedding table.
Following the previous studies [11], we speculate that a large dense user-item
embedding table contains a smaller sparser sub-matrix, which can be
independently trained to achieve a similar performance as the full matrix.
Technically, we exploit the iterative magnitude-based pruning (IMP) [11, 14],
which gradually creates the embedding’s binary masks based on their weight
magnitudes and eventually reaches a powerful sub-matrix. The sub-matrix is
referred to as a winning ticket in the recommender model. We conduct the
extensive experiments on three benchmark datasets, where the empirical results
consistently show that: (1) winning tickets exist widely in deep recommender
models; (2) the IMP algorithm can stably find the winning tickets. Meanwhile,
the winning tickets we found significantly outperform the original large
matrix in terms of time consumption, memory usage and test performance.

Our main contributions are as follows:

  * •

We explore lottery ticket hypothesis in media recommender systems, aiming to
reduce the memory usage and speed up the inference while preserving the
recommendation accuracy. To the best of our knowledge, this is the first work
to study lottery ticket hypothesis in the field of recommendation.

  * •

With two deep recommender models Matrix Factorization (MF) [15] and Light
Graph Convolution Networks (LightGCN) [4] as the backbone models being pruned,
we conduct a lot of experiments on three real-world media convergence
recommendation datasets, demonstrating that winning tickets widely exist in
deep recommender models and the IMP algorithm we used can stably find the
winning tickets.

  * •

The experimental results show that the winning tickets are significantly
superior over the original large embedding table in terms of time consumption,
memory usage, and test performance. Specifically, on three datasets Yelp2018,
TikTok and Kwai, our found winning tickets achieve the same performance as the
complete models with only 29% ~48%, 7% ~10% and 3% ~17% of the parameters,
respectively.

##  2 Related work

###  2.1 Lightweight Embedding

As the most basic parameters in the deep recommender models, the huge user-
item embedding table dominates both the parameter scale and the inductive bias
of the model. In order to choose an appropriate embedding size and reduce the
parameter scale of the embedding table, there are two promising lightweight
techniques:

Auto Machine Learning (AutoML).[7] Joglekar et al. [16] designed two neural
search approaches: Single-Size embedding (NIS-SE) and Multi-Size embedding
(NIS-ME). They defined the embedding table search space by blocks and adjusted
the controller with the validation set, making the model automatically
determine the embedding size by maximizing the accuracy under the constraint
of the embedding table memory. On top of that, some other neural search
approaches such as Neural Architecture Search (NAS) [17], Efficient Neural
Architecture Search (ENAS) [18], and Differentiable Architecture Search (DAS)
[19] are also utilized to automatically determine the size of embeddings and
some of them have been deployed in the industry media recommender systems and
achieved certain benefits.

Model Compression. [20, 21] Common model compression technologies mainly
includes pruning [22], quantization [23] and distillation [24]. For example,
Liu et al. [10] compressed the embedding table by pruning the embedded vectors
of each feature domain of the data. Sun et al. [25] proposed a general
sequential model compression framework, which decomposes the embedding table
into multiple low-rank matrices. Wu et al. [26] clustered the features for
different domains of users and items by similarity calculation, effectively
reducing the total feature number. Zhang et al. [27] shared the parameters
among similar features so as to reduce the parameters of embedding tables.

###  2.2 Lottery Ticket Hypothesis

For preserving accuracy, conventional sparse pruning methods have to train a
large dense neural network first, and then prune it into a small sparse sub-
network. Obviously, this process is computationally expensive. To address this
problem, Frankle and Carbin [11] proposed lottery ticket hypothesis, which
states that there exist some small sparse sub-networks (winning tickets),
which can be directly trained from the scratch to achieve performance
comparable to the complete model with a similar or even faster training speed.
To find the winning tickets in deep neural networks, they further proposed the
IMP algorithm.

Recently, many efforts have been devoted to improving or extending lottery
ticket hypothesis. Brix et al. [28] applied LTH to Transformer models, by
rewinding the pruned sub-network weights to the values at iteration k instead
of 0. Renda et al. [29] compared three different retraining techniques: fine-
tuning, weight rewinding and learning rate rewinding. In their experiments,
the IMP approach with weight rewinding achieved the best performance in terms
of accuracy, compression ratio and search efficiency. You et al. [30] modified
the IMP algorithm to improve the search efficiency for winning tickets. Morcos
et al.[31] generalized LTH across different datasets and optimizers, while Yu
et al. [12] extended it to the field of NLP and reinforcement learning,
confirming the generality of winning tickets.

##  3 Methodology

This section begins with notations and definitions of the recommendation task
(3.1), followed by an introduction of the two widely-used deep recommender
models MF and LightGCN (3.2). Then we formally define LTH-MRS (3.3), and
detail our used method for searching winning tickets in recommender models
(3.4). Finally, we will provide some complexity analyses to show the
superiority of the winning ticket (3.5).

###  3.1 Notations and Definitions

For a media recommender system containing $M$ users and $N$ items, let
$\mathcal{U}=\\{u_{1},\cdots,u_{M}\\}$ denotes the user set and
$\mathcal{I}=\\{i_{1},\cdots,i_{N}\\}$ denotes the item set. Let the node set
$\mathcal{V}=\\{v_{1},\cdots,v_{|\mathcal{V}|}\\}$ denotes all the users and
items, where $\mathcal{V}=\mathcal{U}\cup\mathcal{I}$ and $|\mathcal{V}|=M+N$.
Let the edge set ${\cal E}{\rm{=}}\left\\{{\left({u,i}\right)|u\in{\cal
U},i\in{\cal I},{\mathop{\rm rec}\nolimits}(u,i)=1}\right\\}$ denotes the
interactions between users and items, where ${\mathop{\rm
rec}\nolimits}(u,i)=1$ if there exists an interaction between the user $u$ and
the item $i$, and $0$ otherwise. Then we can define the user-item interaction
records as a bipartite graph ${\cal G}=\left\\{{{\cal V},{\cal E}}\right\\}$.
Learning with ${\cal G}$, the purpose of deep recommender systems is to
predict the item preference ranking of each user.

For each node $v_{t}$ of ${\cal G}$, we represent it as an $F$-dimentional
vector ${\mathbf{x}_{t}}\in{\mathbb{R}^{F}}$. Then the node embedding table of
the whole graph ${\cal G}$ can be represented as follows:

${\mathbf{X}}{\text{ = \\{
}}\underbrace{{{\mathbf{x}}_{1}},{{\mathbf{x}}_{2}},\cdots,{{\mathbf{x}}_{M}}}_{{\text{users}}};{\text{
}}\underbrace{{{\mathbf{x}}_{M+1}},{{\mathbf{x}}_{M+2}},\cdots,{{\mathbf{x}}_{M+N}}}_{{\text{items}}}{\text{\\}
}}\in{\mathbb{R}^{\left|\mathcal{V}\right|\times F}}.$ (1)

We define the user-item interaction matrix as
$\mathbf{R}\in{\mathbb{R}^{M\times N}}$, where

$\mathbf{R}[i,j]=\begin{cases}1\quad\text{ if }(v_{i},v_{j})\in\mathcal{E},\\\
0\quad\text{otherwise}.\end{cases}$ (2)

Then, we can obtain the adjacency matrix of ${\cal G}$ as follows:

$\mathbf{A}={\text{ }}\left({\begin{array}[]{*{20}{c}}0&{\mathbf{R}}\\\
{{{\mathbf{R}}^{\mathrm{T}}}}&0\end{array}}\right)\in\mathbb{R}^{\left|\mathcal{V}\right|\times\left|\mathcal{V}\right|}.$
(3)

###  3.2 Backbone Model

Taking the classical MF [15] and the advanced LightGCN [4] as the backbone
models, we attempt to explore lottery ticket hypothesis in media recommender
systems.

####  3.2.1 MF

MF [15] is a classic recommender model, which aims to optimize the user-item
embedding table to fit the user-item interaction records. We define the
objective function of MF with bayesian personalized ranking (BPR) [15]. For a
pair of interacting user $u$ and item $i$, we can obtain an item $j$ not
interacting with $u$ by negative sampling. We define the score of the positive
instance $(u,i)$ as
$\tilde{y}_{ui}=\mathbf{x}_{u}^{\mathrm{T}}\mathbf{x}_{i}$, and the score of
the negative instance $(u,j)$ as
$\tilde{y}_{uj}=\mathbf{x}_{u}^{\mathrm{T}}\mathbf{x}_{j}$. Then the loss
function of MF is derived as follows:

$L(\mathbf{X})=-\sum\limits_{u=1}^{\left|M\right|}{\sum\limits_{i\in{\mathcal{N}_{u}}}{\sum\limits_{j\notin{\mathcal{N}_{u}}}{ln\sigma(\tilde{y}_{ui}-\tilde{y}_{uj}})+\lambda\left\|\mathbf{X}\right\|^{2}}}.$
(4)

where $\mathcal{N}_{u}$ is the set of all neighbors of the node $u$. With the
loss function in Eq. (4), MF tends to maximize the scores of positive
instances while minimize that of negative instances, so as to integrate the
historical interaction information into the user-item embedding table.

At the stage of inference, MF predicts the score of each pair of user and
item, and then generates an item preference ranking list for each user relying
on the scores.

####  3.2.2 LightGCN

LightGCN [4], which removes the unnecessary feature transformation and
nonlinear activation operations inherited from graph convolution networks,
achieves efficient and effective recommendation with its neighborhood
aggregation and layer combination.

At the $k$-th layer, LightGCN obtains node embeddings $\mathbf{X}^{(k)}$ by
neighborhood aggregation mechanism as follows:

$\mathbf{X}^{(k)}=\left(\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\right)\mathbf{X}^{(k-1)}.$
(5)

where $\mathbf{D}$ is a diagonal matrix of
$\left|\mathcal{V}\right|\times\left|\mathcal{V}\right|$, $\mathbf{D}_{ii}$
indicates the number of non-zero elements in $i$-th row of $\mathbf{A}$, and
$\mathbf{X}^{(0)}=\mathbf{X}$ is the user-item embedding table of the model.
Finally, the output vectors can be achieved by combining the node
representations of all layers as follows:

$\mathbf{O}=\alpha_{0}\mathbf{X}+\alpha_{1}\mathbf{X}^{(1)}+\alpha_{2}\mathbf{X}^{(2)}+\cdots+\alpha_{K}\mathbf{X}^{(K)}.$
(6)

where the coefficients $\alpha_{0}$, $\alpha_{1}$, $\cdots$, $\alpha_{K}$ are
conventionally $1$, and $K$ is the total layer number of LightGCN.

Following the previous studies [4], we use BPR loss function to optimize
LightGCN. Let
${\mathbf{O}}=\\{{{\mathbf{o}}_{1}},{{\mathbf{o}}_{2}},\ldots,{{\mathbf{o}}_{M+N}}\\}$
denotes the output node vectors, we define the score of the positive instance
$(u,i)$ as $\hat{y}_{ui}=\mathbf{o}_{u}^{\mathrm{T}}\mathbf{o}_{i}$, and the
score of the negative instance $(u,j)$ as
$\hat{y}_{uj}=\mathbf{o}_{u}^{\mathrm{T}}\mathbf{o}_{j}$. Then the loss
function of LightGCN is defined as follows:

$L(\mathbf{X},\mathbf{A})=-\sum\limits_{u=1}^{\left|M\right|}{\sum\limits_{i\in{\mathcal{N}_{u}}}{\sum\limits_{j\notin{\mathcal{N}_{u}}}{ln\sigma(\hat{y}_{ui}-\hat{y}_{uj}})+\lambda\left\|\mathbf{X}\right\|^{2}}}.$
(7)

###  3.3 Lottery Ticket Hypothesis in Media Recommender Systems

In order to extend lottery ticket hypothesis to the field of recommendation,
we explore lottery ticket hypothesis in media recommender systems (LTH-MRS) to
find winning tickets in the most basic parameter of recommender models—user-
item embedding tables. For a deep media recommender model, we assume its large
dense user-item embedding table contains a small sparse sub-matrix, and when
independently training the model with this sub-matrix, it can match or even
outperform that with the original large matrix. This sub-matrix is called a
winning ticket in media recommender systems.

Assume that a media recommender model $f(\mathcal{G};\mathbf{X})$ achieves the
best test result of $a$ after $j$ epochs of training. Let
$\mathbf{M}=\\{0,1\\}\in\mathbb{R}^{\|\mathbf{X}\|_{0}}$ denotes a binary
mask, then $\mathbf{M}\odot\mathbf{X}$ denotes a sparse sub-matrix of
$\mathbf{X}$. Assume that $f(\mathcal{G};\mathbf{M}\odot\mathbf{X})$ achieves
a test result of $a^{\prime}$ after $j^{\prime}$ epochs of training. Formally,
LTH-MRS can be formulated as: $\exists{\mathbf{M}}{\text{,
s}}{\text{.t}}{\text{. j'}}\leqslant{\text{j, a'}}\geqslant{\text{a and
}}{\left\|{\mathbf{M}}\right\|_{0}}\ll{\left\|{\mathbf{X}}\right\|_{0}}$. The
sub-matrix satisfying LTH-MRS is called a winning ticket in media recommender
systems.

Once LTH-MRS is verified and the winning tickets in media recommender systems
are found, the performance of a dense model can be achieved merely with far
fewer parameters. The costs of memory, training and inference can be reduced
effectively, providing more possibilities for the production deployment of
large scale of media recommender systems.

###  3.4 Identifying Winning Tickets in Media Recommender Systems

Figure 1: Overview of our used IMP algorithm to identify the winning tickets
in media recommender systems.

To verify LTH-MRS, we leverage the IMP algorithm to find the winning tickets
of user-item embedding tables for media recommender models. The IMP algorithm
process is shown in Figure 1. We use an untrainable matrix $\mathbf{M}$, where
each element is a binary flag indicating whether the corresponding parameter
has been pruned or not, to prevent the pruned parameters from participating in
computing. Let $\mathbf{X}^{0}$ denotes a randomly initialized dense user-item
embedding table, and $\mathbf{M}^{0}=1\in\mathbb{R}^{\|\mathbf{X}^{0}\|_{0}}$
denotes the initial mask which is an all-ones matrix. Then the original dense
model $f(\mathcal{G};\mathbf{X}^{0})$ is equivalent to
$f(\mathcal{G};\mathbf{M}^{0}\odot\mathbf{X}^{0})$. We perform magnitude-based
sparse pruning on the embedding table $\mathbf{M}^{0}\odot\mathbf{X}^{0}$ by
setting the values at the corresponding positions in $\mathbf{M}^{0}$ to $0$.
We define the percentage of parameters to be pruned at each iteration as the
iterative pruning rate $pr\%$, and the proportion of 0 in $\mathbf{M}^{i}$
(i.e. the mask after $i$ pruning iterations) as the sparsity
$\frac{\left\|{\mathbf{M}^{i}}\right\|_{0}}{\left\|{\mathbf{M}^{0}}\right\|_{0}}$.
Then, an embedding sub-matrix $\mathbf{M}^{I}\odot\mathbf{X}^{0}$ with the
sparsity of $1-(1-pr\%)^{I}$ can be achieved after $I$ pruning iterations.

To find the winning tickets, we run the following operations at $i$-th
iteration:

(1) Training: train the model
$f(\mathcal{G};\mathbf{M}^{i}\odot\mathbf{X}^{0})$ for $J$ epochs to achieve
$f(\mathcal{G};\mathbf{M}^{i}\odot\mathbf{X}^{J})$.

(2) Pruning: prune $pr\%$ of non-zero lowest magnitude values in
$f(\mathcal{G};\mathbf{M}^{i}\odot\mathbf{X}^{J})$ to generate a updated mask
$\mathbf{M}^{i+1}$.

(3) Rewinding: reset the updated dense matrix $\mathbf{X}^{J}$ to
$\mathbf{X}^{0}$, creating a new lottery ticket
$\mathbf{M}^{i+1}\odot\mathbf{X}^{0}$.

Note that the operation (3) is called rewinding mechanism, which is proposed
by Frankle and Carbin [11]. They believed that only when the small sparse sub-
networks obtained the same initialization of the original large dense
networks, can they be trained independently and efficiently.

Input: A user-item bipartite graph ${\cal G}$, a recommender model
$f(\mathcal{G};\mathbf{X}^{0})$, the iterative pruning rate $pr\%$, the total
pruning iteration $I$ and the training epoch $J$.

Output: The lottery ticket set $\mathcal{S}$.

1 Initialize a mask $\mathbf{M}^{0}\leftarrow
1\in\mathbb{R}^{\left\|{\mathbf{X}^{0}}\right\|_{0}}$.

2Initialize a lottery ticket set $\mathcal{S}\leftarrow\emptyset$.

3for  _$i\leftarrow 0$ to $I-1$_ do

4 Training: train $f(\mathcal{G};\mathbf{M}^{i}\odot\mathbf{X}^{0})$ with
${\cal G}$ for $J$ epochs to achieve
$f(\mathcal{G};\mathbf{M}^{i}\odot\mathbf{X}^{J})$.

5 Pruning: select $pr\%$ of non-zero lowest magnitude values in
$\mathbf{M}^{i}\odot\mathbf{X}^{J}$, and set the values at the corresponding
positions in $\mathbf{M}^{i}$ to $0$ to generate $\mathbf{M}^{i+1}$.

6 Rewinding: reset $\mathbf{X}^{J}$ to $\mathbf{X}^{0}$ to generate a new
lottery ticket $\mathbf{M}^{i+1}\odot\mathbf{X}^{0}$.

7
$\mathcal{S}\leftarrow\mathcal{S}\cup\left\\{\mathbf{M}^{i+1}\odot\mathbf{X}^{0}\right\\}$

8 end for

Algorithm 1 An IMP algorithm for the user-item embedding table.

The specifical process is detailed in Algorithm 1. When Algorithm 1 is
completed (i.e., after $I$ iterations of pruning), we can achieve a lottery
ticket set
$\mathcal{S}=\left\\{\mathbf{M}^{1}\odot\mathbf{X}^{0},\mathbf{M}^{2}\odot\mathbf{X}^{0},\cdots,\mathbf{M}^{I}\odot\mathbf{X}^{0}\right\\}$,
where each ticket is a sparse embedding sub-matrix with the sparsity of
$1-(1-pr\%),1-(1-pr\%)^{2},\cdots,1-(1-pr\%)^{I}$, respectively. Finally, we
independently train and test each lottery ticket in $\mathcal{S}$ to verify
the existence of winning tickets.

###  3.5 Complexity Analysis

Here, we provide the complexity analyses for MF and LightGCN to show the
superiority of the winning ticket.

MF. The inference time complexity of the original dense MF is
$\mathcal{O}\left(M\times N\times F\right)$ and the memory complexity is
$\mathcal{O}\left(M\times F+N\times F\right)$, where $M$ and $N$ are the
number of users and items in the recommender system, and $F$ is the size of
user-item embedding vector. For a winning ticket $\mathbf{M}\odot\mathbf{X}$
of MF, we denote $\mathbf{M}_{u}$ as the mask of the user $u\in\mathcal{U}$,
and $\mathbf{M}_{i}$ as the mask of the item $i\in\mathcal{I}$, where
$\mathcal{U}$ and $\mathcal{I}$ are the sets of user and item, respectively.
Then the inference time complexity of the winning ticket is
$\mathcal{O}\left(M\times
N\times\min\left({F_{u}^{*},F_{i}^{*}}\right)\right)$, and the memory
complexity is $\mathcal{O}\left(M\times F_{u}^{*}+N\times F_{i}^{*}\right)$,
where
$F_{u}^{*}=\max\limits_{u\in\mathcal{U}}\left\|\mathbf{M}_{u}\right\|_{0}$
indicates the maximum size of sparse user embeddings, and
$F_{i}^{*}=\max\limits_{i\in\mathcal{I}}\left\|\mathbf{M}_{i}\right\|_{0}$
indicates the maximum size of sparse item embeddings.

LightGCN. For a $K$-layer LightGCN, the time complexity of neighborhood
aggregation is $\mathcal{O}\left(K\times\|\mathbf{A}\|_{0}\times F\right)$,
where $\mathbf{A}$ is the adjacency matrix, the time complexity of layer
combination is $\mathcal{O}\left(M\times F+N\times F\right)$ and the time
complexity of similarity computation is $\mathcal{O}\left(M\times N\times
F\right)$. Considering $M+N\ll M\times N$, the inference time complexity of
the original dense LightGCN is
$\mathcal{O}\left(K\times\|\mathbf{A}\|_{0}\times F+M\times N\times F\right)$,
and the memory complexity is $\mathcal{O}\left(M\times F+N\times F\right)$.
For a winning ticket of LightGCN, the inference time complexity is
$\mathcal{O}\left(K\times\|\mathbf{A}\|_{0}\times\min\left({F_{u}^{*},F_{i}^{*}}\right)+M\times
N\times\min\left({F_{u}^{*},F_{i}^{*}}\right)\right)$, and the memory
complexity is $\mathcal{O}\left(M\times F_{u}^{*}+N\times F_{i}^{*}\right)$.

As compared with the large dense models, the winning tickets represent users
and items with much smaller sparse vectors (i.e., $F_{u}^{*},F_{i}^{*}\ll F$).
Therefore, the inference time complexity and the memory complexity of the
winning tickets are far lower than that of the original dense models.

##  4 Experiments

Beginning with an introduction of the experiment settings (4.1), this section
mainly attempts to explore the following questions through a series of
comparison experiments:

Q1: Does the winning ticket in media recommender systems exists? (4.2)

Q2: Does the IMP algorithm reliably find winning tickets? (4.3)

Q3: Does the found winning tickets outperform the other compression models?
(4.4)

To further explore the effects of different implementation details of IMP, we
conduct ablation studies (4.5). On top of that, we also compare the training
speed of the winning tickets and the original embedding table (4.6). Finally,
we visualize the winning tickets for interpretable analysis (4.7).

###  4.1 Experiment Settings

Here, we will detail our experiment settings, including the datasets, the
evaluation metrics, the backbone models and the hyperparameters settings.

Datasets. We conducted extensive experiments on three public benchmark
datasets:

  * •

Yelp2018 https://www.kaggle.com/yelp-dataset/yelp-dataset is a dataset for
recommending restaurants and bars, presented in the 2018 Yelp Dataset
Challenge.

  * •

TikTok https://www.biendata.xyz/competition/icmechallenge2019 is a dataset for
recommending the TikTok videos, presented in the 2019 ICME Challenge.

  * •

Kwai https://www.kuaishou.com/activity/uimc is a dataset for recommending the
Kwai videos, presented in the China MM 2018.

The TikTok and Kwai datasets are both the real-world user-video interaction
datasets under the media convergence environment. Following the previous works
[3, 32], we split the datasets into training set, validation set and test set
with a ratio of 7:1:2. Table 1 shows overall statistics for the three
datasets. Note that the original interaction data of TikTok is too huge, so we
merely use the videos within a period, and filter the data without complete
modalities.

Table 1: Statistics of the datasets. Datasets |  User Number |  Items Number |  Interaction Number |  Density
---|---|---|---|---
Yelp2018 | 31,668 | 38,048 | 1,561,406 | 0.00130
TikTok | 36,638 | 97,117 | 746,546 | 0.00021
Kwai | 7,010 | 80,631 | 292,042 | 0.00052

Evaluation Metrics. We adopt Recall and Normalized Discounted Cumulative Gain
(NDCG) as the main experimental evaluation metrics. For users in the test set,
we follow the all-ranking protocol to evaluate the top-$K$ recommendation
performance and report the average Recall@K and NDCG@K, where we set $K=20$.

Backbone Models. We adopt MF and LightGCN as our backbone models. MF and
LightGCN are representative because they are both merely user-item
interaction-based deep recommender models without any external information,
and the user-item embedding table is the only model parameter. (See 3.2 for
more details)

Hyper-parameters Settings. We apply the Adam [33] as the optimizer with the
learning rate of 0.001, the L2-regularization weight $\lambda$ of 0.0001 and
the batch size of 2048. In main experiments, the training epoch number $J$ is
1000, the iterative pruning rate $pr\%$ is 0.1 and the pruning iteration
number $I$ is 30.

Table 2: The Recall@20 and NDCG@20 of the sub-models with different sparsity
levels of MF and LightGCN on Yelp2018, TikTok and Kwai datasets. The bold
results indicate the performance of winning tickets, and the sparsity of 0
indicates the original dense model.

Evaluation Metrics | Recall@20 |  NDCG@20
---|---|---
Sparsity (%) | 0 | 27.1 | 65.13 | 95.29 | 0 | 27.1 | 65.13 | 95.29
Yelp2018 | MF | 0.0459 | 0.0487 | 0.0468 | 0.0395 | 0.0372 | 0.0396 | 0.0378 | 0.0320
LightGCN | 0.0600 | 0.0602 | 0.0584 | 0.0510 | 0.0488 | 0.0491 | 0.0476 | 0.0418
TikTok | MF | 0.0851 | 0.0955 | 0.0961 | 0.0638 | 0.0500 | 0.0552 | 0.0557 | 0.0354
LightGCN | 0.1423 | 0.1539 | 0.1577 | 0.1379 | 0.0828 | 0.0898 | 0.0918 | 0.0813
Kwai | MF | 0.0411 | 0.0464 | 0.0525 | 0.0529 | 0.0318 | 0.0353 | 0.0393 | 0.0431
LightGCN | 0.0779 | 0.0847 | 0.0857 | 0.0751 | 0.0638 | 0.0679 | 0.0689 | 0.0614

###  4.2 Existence of the Winning Ticket

We apply the IMP algorithm on Yelp2018, TikTok and Kwai datasets to obtain a
series of sparse sub-networks (a.k.a. lottery tickets) of MF and LightGCN.
Then each lottery ticket will be trained and tested independently to determine
whether it wins or not. We present the experimental results of the
32-dimensional original embedding size in Table 4.1. As shown in these
results, we have found a lot of winning tickets, which can achieve
significantly better performance with far fewer parameters than the original
models. Taking the results on Kwai dataset for example, as compared with the
original MF, the winning ticket improves Recall@20 and NDCG@20 by 28.7% and
35.5%, respectively, while reducing 95.29% parameters; as compared with the
original LightGCN, the winning ticket improves Recall@20 and NDCG@20 by 10.0%
and 7.99%, respectively, while reducing 65.13% parameters. The above
observations show that LTH-MRS is valid, and the winning tickets exist widely
in media recommender systems.

###  4.3 Effectiveness of the IMP Algorithm

Figure 2: The Recall@20 results of the lottery tickets with different sparsity
of MF and LightGCN obtained by IMP, RP and OMP approaches on Yelp2018, TikTok
and Kwai datasets. The positions of red stars
($\color[rgb]{0.75390625,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75390625,0,0}\star$)
indicate the highest sparsity that winning tickets can achieve while
preserving comparable performance.

To explore whether the IMP algorithm can find the winning tickets stably and
effectively, we select two representative pruning approaches[11] for
comparison: Random Pruning (RP) randomly removes elements from a trained
embedding table, and One-shot Magnitude-based Pruning (OMP) directly reduce a
trained embedding table to the target sparsity based on the element magnitude
without iterations. We compare the performance of the lottery tickets obtained
by IMP, RP and OMP, with the setting of 32-dimensional original embedding
size, to demonstrate the effectiveness of the IMP algorithm for finding
winning tickets. Notably, the Baselines with black dotted lines in Figure 2-5
indicate the corresponding large-dense recommender models.

From the results shown in Figure 2, we can observe that:

(1) RP can not stably find the winning tickets. In our experiments, RP merely
found winning tickets of LightGCN on TikTok dataset. Moreover, the winning
tickets found by RP achieved 40.7% and 27.3% declines in the highest sparsity,
and achieved 4.8% and 0.7% declines in highest Recall@20, compared with that
by IMP and OMP, respectively.

(2) IMP and OMP can both stably find the winning tickets, but the winning
tickets found by IMP significantly and consistently outperform that by OMP.
Specifically, on Yelp2018, TikTok and Kwai datasets, as compared with OMP, the
winning tickets of MF found by IMP achieve 30.8%, 25.2% and 2.5% improvements
in the highest sparsity, and achieve 18.8%, 8.8% and 1.1% improvements in the
highest Recall@20; the winning tickets of LightGCN found by IMP achieve 22.0%,
15.6% and 8.9% improvements in the highest sparsity, and achieve 6.6%, 4.0%
and 3.4% improvements in the highest Recall@20.

The above observations show that our used IMP algorithm can reliably find the
winning tickets, and the winning tickets found by IMP always outperform that
by the compared approaches.

###  4.4 Performance of the Winning Ticket

To further demonstrate the performance of the found winning tickets, we
compare against two competitive baselines: Linear Compression Model (LCM)
https://github.com/gusye1234/KD_on_Ranking, which compresses the large
embedding table into a small dense matrix with trainable feature
transformation; and Plug-in Embedding Pruning model (PEP) [10], which prunes
the embedding table into a small sparse matrix with a trainable dynamic
pruning threshold.

Table 3: The Recall@20 and NDCG@20 of the winning tickets, LCM and PEP with
different sparsity levels of LightGCN on Yelp2018, TikTok and Kwai datasets.

Evaluation Metrics | Recall@20 |  NDCG@20
---|---|---
Original Size | 64 | 128 | 64 | 128
Sparsity (%) | 50 | 75 | 50 | 75 | 50 | 75 | 50 | 75
Yelp2018 | LCM | 0.0558 | 0.0459 | 0.0610 | 0.0537 | 0.0460 | 0.0374 | 0.0493 | 0.0438
PEP | 0.0584 | 0.0570 | 0.0627 | 0.0601 | 0.0473 | 0.0459 | 0.0507 | 0.0483
Winning Ticket | 0.0635 | 0.0609 | 0.0666 | 0.0651 | 0.0525 | 0.0500 | 0.0545 | 0.0530
TikTok | LCM | 0.1508 | 0.1341 | 0.1594 | 0.1500 | 0.0895 | 0.0791 | 0.0941 | 0.0885
PEP | 0.1640 | 0.1567 | 0.1814 | 0.1801 | 0.0956 | 0.0901 | 0.1068 | 0.1047
Winning Ticket | 0.1851 | 0.1829 | 0.1911 | 0.1913 | 0.1085 | 0.1064 | 0.1128 | 0.1130
Kwai | LCM | 0.0690 | 0.0640 | 0.0742 | 0.0652 | 0.0585 | 0.0542 | 0.0544 | 0.0538
PEP | 0.0840 | 0.0836 | 0.0862 | 0.0860 | 0.0684 | 0.0673 | 0.0696 | 0.0695
Winning Ticket | 0.0867 | 0.0856 | 0.0888 | 0.0882 | 0.0696 | 0.0693 | 0.0706 | 0.0705

We present the comparison results of winning tickets, LCM and PEP for LightGCN
in Table 4.4, demonstrating that our found winning tickets remarkably
outperform LCM and PEP with equivalent quantities of parameters. Taking the
results on Yelp2018 dataset as examples, for a $128$-dimensional dense
embedding table, as compared with LCM, the winning tickets improve Recall@20
and NDCG@20 by 9.18% and 10.54% when the sparsity is 50%, and improves that by
21.23% and 21.00% when the sparsity is 25%.

As aforementioned, it is generally considered that dense models are easier to
train for better performance than sparse models. However, the experimental
results show that the sparse compressed models—winning tickets and PEP, can
consistently outperform the dense compressed model—LCM, which seems a little
counter-intuitive. The reason we believed is that, as a dense model, LCM
represents different users and items with a uniform size, neglecting the
diversity and the specificity among users and items. Hence, it may be hard for
LCM to handle the heterogeneity of users and items with different
popularities. By contrast, our used IMP algorithm automatically determines an
appropriate embedding size for each user or item by pruning unimportant
parameters during searching for winning tickets, and PEP also achieves this
property with its dynamic threshold mechanism. As compared with LCM, winning
tickets and PEP can express the heterogeneity of users and items better by
assigning different embedding sizes for them. The various sparsity of
embedding vectors describes the intrinsic diversity among different users and
items, and thus improves the performance of winning tickets.

Moreover, as shown in Table 3, although the dynamic threshold mechanism in PEP
remarkably speeds up the process of pruning, the performance of final sparse
models is worse than that of winning tickets. In addition, the performance of
PEP highly depends on hyperparameters for the trainable pruning threshold, so
it is required to consume expensive time for tuning those hyperparameters
carefully. In terms of performance, simplicity and stability, the winning
tickets has shown great superiority as compared with PEP.

Figure 3: The Recall@20 results of the lottery tickets of MF and LightGCN with
different original embedding sizes on Yelp2018, TikTok and Kwai datasets,
where the IMP-$i$d indicates the IMP with original embedding size of $i$.

Figure 4: The performance comparison of IMP algorithm with different iterative
pruning rates, where the IMP-$i$pr indicates the IMP with iterative pruning
rate of $i$.

###  4.5 Ablation Study

To further explore the effects and contributions of different implementation
details of IMP, including the original embedding size, the iterative pruning
rate $pr\%$ and the rewinding mechanism, we conduct a series of ablation
studies.

Effect of Original Embedding Size. We present the performance of winning
tickets with different original embedding sizes in Figure 3, from which it can
be observed that: (1) for the same deep recommender models with different
sizes, with the increase of sparsity, the performance trends of lottery
tickets are almost consistent; (2) for deep recommender models with different
original embedding sizes, the winning tickets widely exist and always can be
found by our used IMP algorithm.

Effect of Iterative Pruning Rate. We utilize IMP algorithm with different
$pr\%$ (5%, 10% and 20%) to find winning tickets of LightGCN on Yelp2018
dataset, and present the results in Figure 4, from which it can be observed
that: (1) the highest sparsity achieved with different $pr\%$ is almost the
same; (2) lower $pr\%$ achieves higher best Recall@20; (3) higher $pr\%$ takes
fewer steps to reach the sparsest winning ticket. These observations
demonstrate that a high iterative pruning rate can effectively improve the
search efficiency, while it may miss the optimal winning ticket. Therefore, to
trade off effectiveness and efficiency, it is necessary to set a reasonable
$pr\%$ when applying the IMP algorithm to find winning tickets.

Effect of Rewinding Mechanism. To explore the importance of rewinding
mechanism in our IMP algorithm, we conduct ablation studies for MF and
LightGCN on Yelp2018 dataset. It can be observed in Figure 5 that compared
with IMP w/o rewind, (1) the IMP with rewinding mechanism can find winning
tickets more stably and reliably; (2) the IMP with rewinding mechanism
improves the performance in Recall@20 and sparsity significantly and
consistently.

Overall, in IMP algorithm, the iterative pruning is a search technique for
winning tickets, while the rewinding mechanism ensures the stability of the
search and the effectiveness of the winning tickets.

Figure 5: The ablation study about rewinding mechanism, where the IMP w/o
rewind indicates the IMP algorithm without rewinding mechanism. Figure 6:
Relative training epochs of winning tickets and original embeddings.

###  4.6 Comparison of Training Speed

We compare the training speed of winning tickets and original embeddings to
show that during independently training, the winning tickets can achieve
comparable performance to the original dense embedding table with faster
learning speed. We take the consumed training epochs of winning tickets as one
unit, and then present the relative training epochs of original embeddings in
Figure 6, from which we can observe that the training speed of winning tickets
is far higher than that of original embeddings. For example, the winning
ticket of MF-32d reached comparable performance with a learning speed 8 times
the original embedding table. These experimental results demonstrate the huge
potential of the winning ticket for reducing expensive training cost of large-
scale media recommender systems.

###  4.7 Case Study

We visualize the original embedding table and the winning ticket on Yelp2018
dataset for case study. Due to the limited space, we merely show the first 10
users and items. As shown in Figure 7, the highly sparse winning ticket
achieved by IMP tends to preserve more critical features (of high magnitude)
for different users and items. During the iterations of identifying winning
tickets, the IMP algorithm can reduce the parameter scale of redundancy
features while preserving the significance of those meaningful features. By
denoising those unimportant features, we can obtain a sparse embedding table
(winning ticket) that can achieve comparable test performance of the full
embedding with much fewer parameters.

Figure 7: Visualization of winning ticket and original embedding.

##  5 Conclusion and Futute Work

To address the problem of parameter redundancy in media recommender systems,
we extended the lottery ticket hypothesis to the field of recommendation. We
studied lottery ticket hypothesis in media recommender systems, exploiting IMP
algorithm to find winning tickets of the user-item embedding table in two
representative deep recommender models — MF and LightGCN. Empirical results on
three real-world datasets showed the winning tickets can achieve better
performance with much fewer parameters and faster training speed than the full
user-item embeddings.

In the future, we plan to explore: (1) efficient schemes for identifying
winning tickets. The iterative identification of IMP requires a costly train-
prune-retrain process, which limits the practical benefits; (2) winning
tickets for implicit feedback interaction records. There exists a lot of noisy
data in the implicit feedback interaction records of recommender systems. For
example, a noisy interaction will be produced when a user accidentally clicks
on an uninterested item. Huge number of interaction records will lead to an
expensive training cost, while the serious noisy interactions will mislead the
learning of recommender models. (3)inductive mode for new-coming users and
items. The proposed method of this paper is limited to the transductive
setting. In each iteration, we performed pruning on the whole embedding
matrix, which allowed us to optimize the networks globally, but also limited
the generalization to new-coming users/items. In the future, we will consider
extending our method to the inductive setting.

## ACKNOWLEDGEMENTS

This work is supported by the National Natural Science Foundation of China
(U19A2079, 61972372, 62121002) and National Key Research and Development
Program of China (2020YFB1406703).

## References

  * [1] Y. Liu, A. Pei, F. Wang, Y. Yang, X. Zhang, H. Wang, H. Dai, L. Qi, R. Ma. An attention-based category-aware GRU model for the next POI recommendation. Int. J. Intell. Syst. 2021, 36 (7), 3174–3189.
  * [2] H. Chen, S. Wang, N. Jiang, Z. Li, N. Yan, L. Shi. Trust-aware generative adversarial network with recurrent neural network for recommender systems. Int. J. Intell. Syst. 2021, 36 (2), 778–795.
  * [3] X. Wang, X. He, M. Wang, F. Feng, T.-S. Chua. Neural graph collaborative filtering. Proceedings of the 42nd international ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 2019, 165–174.
  * [4] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, M. Wang. Lightgcn: simplifying and powering graph convolution network for recommendation. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 2020, 639–648.
  * [5] Z. Batmaz, A. Yurekli, A. Bilge, C. Kaleli. A review on deep learning for recommender systems: challenges and remedies. Artif. Intell. Rev. 2019, 52 (1), 1–37.
  * [6] S. Zhang, L. Yao, A. Sun, Y. Tay. Deep learning based recommender system: a survey and new perspectives. ACM Comput. Surv. 2019, 52 (1), 1–38.
  * [7] X. He, K. Zhao, X. Chu. AutoML: a survey of the state-of-the-art. Knowl-Based Syst. 2021, 212, 106622.
  * [8] U. Gupta, S. Hsia, V. Saraph, X. Wang, B. Reagen, G.-Y. Wei, H.-H. S. Lee, D. Brooks, C.-J. Wu. Deeprecsys: A system for optimizing end-to-end at-scale neural recommendation inference. 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). 2020, 982–995.
  * [9] P. Covington, J. Adams, E. Sargin. Deep neural networks for youtube recommendations. Proceedings of the 10th ACM Conference on Recommender Systems (RecSys). 2016, 191–198.
  * [10] S. Liu, C. Gao, Y. Chen, D. Jin, Y. Li. Learnable embedding sizes for recommender systems. International Conference on Learning Representations (ICLR). 2020.
  * [11] J. Frankle, M. Carbin. The lottery ticket hypothesis: finding sparse, trainable neural networks. International Conference on Learning Representations (ICLR). 2019.
  * [12] H. Yu, S. Edunov, Y. Tian, A. S. Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP. International Conference on Learning Representations (ICLR). 2019.
  * [13] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, et al.. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nat. Methods 2020, 17 (3), 261–272.
  * [14] T. Chen, Y. Sui, X. Chen, A. Zhang, Z. Wang. A unified lottery ticket hypothesis for graph neural networks. International Conference on Machine Learning (ICML). 2021, 1695–1706.
  * [15] S. Rendle, C. Freudenthaler, Z. Gantner, L. Schmidt-Thieme. BPR: bayesian personalized ranking from implicit feedback. Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI), Arlington, Virginia, USA 2009, 452–461.
  * [16] M. R. Joglekar, C. Li, M. Chen, T. Xu, X. Wang, J. K. Adams, P. Khaitan, J. Liu, Q. V. Le. Neural input search for large scale recommendation models. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (SIGKDD). 2020, 2387–2397.
  * [17] H. Liu, X. Zhao, C. Wang, X. Liu, J. Tang. Automated embedding size search in deep recommender systems. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 2020, 2307–2316.
  * [18] H. Pham, M. Guan, B. Zoph, Q. Le, J. Dean. Efficient neural architecture search via parameters sharing. International Conference on Machine Learning (ICML). 2018, 4095–4104.
  * [19] H. Liu, K. Simonyan, Y. Yang. DARTS: differentiable architecture search. International Conference on Learning Representations (ICLR). 2018.
  * [20] J. Lei, X. Gao, J. Song, X. Wang, M. Song. Survey of deep neural network model compression. J. Software 2018, 29 (2), 251–266.
  * [21] Y. Cheng, D. Wang, P. Zhou, T. Zhang. Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Proc. Mag. 2018, 35 (1), 126–136.
  * [22] Q. Xiang, X. Wang, Y. Song, L. Lei, R. Li, J. Lai. One-dimensional convolutional neural networks for high-resolution range profile recognition via adaptively feature recalibrating and automatically channel pruning. Int. J. Intell. Syst. 2021, 36 (1), 332–361.
  * [23] S. Gupta, A. Agrawal, K. Gopalakrishnan, P. Narayanan. Deep learning with limited numerical precision. International Conference on Machine Learning (ICML). 2015, 1737–1746.
  * [24] X. Jiao, Y. Yin, L. Shang, X. Jiang, X. Chen, L. Li, F. Wang, Q. Liu. TinyBERT: distilling BERT for natural language understanding. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings (EMNLP: Findings) 2020, 4163–4174.
  * [25] Y. Sun, F. Yuan, M. Yang, G. Wei, Z. Zhao, D. Liu. A generic network compression framework for sequential recommender systems. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 2020, 1299–1308.
  * [26] X. Wu, H. Xu, H. Zhang, H. Chen, J. Wang. Saec: similarity-aware embedding compression in recommendation systems. Proceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems (APSys) 2020, 82–89.
  * [27] C. Zhang, Y. Liu, Y. Xie, S. I. Ktena, A. Tejani, A. Gupta, P. K. Myana, D. Dilipkumar, S. Paul, I. Ihara, et al.. Model size reduction using frequency based double hashing for recommender systems. Proceedings of the 14th ACM Conference on Recommender Systems (RecSys). 2020, 521–526.
  * [28] C. Brix, P. Bahar, H. Ney. Successfully applying the stabilized lottery ticket hypothesis to the transformer architecture. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL). 2020, 3909–3915.
  * [29] A. Renda, J. Frankle, M. Carbin. Comparing rewinding and fine-tuning in neural network pruning. International Conference on Learning Representations (ICLR). 2020.
  * [30] H. You, C. Li, P. Xu, Y. Fu, Y. Wang, X. Chen, R. G. Baraniuk, Z. Wang, Y. Lin. Drawing early-bird tickets: toward more efficient training of deep networks. International Conference on Learning Representations (ICLR). 2020.
  * [31] A. S. Morcos, H. Yu, M. Paganini, Y. Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. Proceedings of the 33rd International Conference on Neural Information Processing Systems (NeurIPS). 2019, 4932–4942.
  * [32] X. He, L. Liao, H. Zhang, L. Nie, X. Hu, T.-S. Chua. Neural collaborative filtering. Proceedings of the 26th International Conference on World Wide Web (WWW). 2017, 173–182.
  * [33] D. P. Kingma, J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR). 2015.