\section{Algorithm Development}

\section{Compressing the Importance Distribution}\label{sec:algorithm}
In this section, we detail our proposed sequential compression scheme for overcoming the curse of dimensionality in importance sampling. However, to develop such a compression scheme, we first rewrite importance sampling estimates in vector notation to illuminate the dependence on the number of past particles generated. Then, because directly defining projections over measure spaces is intractable, we incorporate a distributional approximation called a mean embedding \cite{sriperumbudur2010hilbert}, over which metrics can be easily evaluated. This permits us to develop our main projection operator.

 Begin by noting the curse of dimensionality in importance sampling can be succinctly encapsulated by rewriting the last step of Algorithm \ref{alg:importance_sampling} in vector notation. Specifically, define  ${\bbg}_n \in \reals^n$  ,
 $\overline{\bbw}_n \in \reals^n$ and $\bbX_n = [\bbx(1) ; \cdots \bbx(n)] \in \reals^{p \times n}$. Then, after each new sample $\bbx(n)$ is generated from the importance distribution, we incorporate it into the empirical measure \eqref{eq:importance_sampling_empirical_measure} through the parameter updates
\begin{align}\label{eq:importance_sampling_stack}
\bbg_{n} =& [\bbg_{n-1} ; g{(\bbx(n))} ] \;,\nonumber  \\
 \quad \overline{\bbw}_{n} =& z_n \bbg_{n} \;, \qquad \bbX_{n} = [\bbX_{n-1} ; \bbx(n) ],
\end{align}
 where we define $z_n:=1/(\mathbf{1}_n^T\bbg_{n})$ and  $\mathbf{1}_n$ is the all ones column vector  with dimension $n$.  The unnormalized posterior density estimate parameterized by $\bbg_n$ and \emph{dictionary} $\bbX_n$ is given by
\begin{align}\label{eq:posterior_distribution}
 \tilde{\mu}_n = \sum_{u=1}^n \bbg_n(u) \delta_{\bbx(u)},
\end{align}
where we define $\bbg_n(u) := g(\bbx(u))$ is the importance weight \eqref{eq:UIS_estimator} and $\delta_{\bbx(u)}$ is the Dirac delta function, both evaluated at sample $\bbx(u)$. Denote as $\Omega_{\bbX_n}$ the measure space ``spanned" by Dirac measures centered at the samples stored in dictionary $\bbX_n$. More specifically, given measurable space $(\Omega,\Sigma,\lambda)$, where $\Omega$ is a set of outcomes, $\Sigma$ is a $\sigma$-algebra whose elements are subsets, and $\lambda: \Sigma \rightarrow \reals$ denotes the Lebesgue measure, we define the restricted $\sigma$-algebra as $\Sigma_{\bbX_n}=\{F\cap\{\bbx(u)\}_{u\leq n} : F\in\Sigma\}$. The measure space associated with $\Sigma_{\bbX_n}$ and the Lebesgue measure $\lambda_{\bbX_n}$ over this restricted $\sigma$-algebra we denote in shorthand as $\Omega_{\bbX_n}$ (see \cite{wheeden1977measure} for more details).

We note that the unnormalized posterior density in \eqref{eq:posterior_distribution} is a linear combination of (nonnegative) Dirac measures with mass $\bbg_n(u)$ for each sample ${\bf x}(u)$.
 The question is how to select a subset of columns of $\bbX_n$ and {modify} the weights $\bbg_n$ such that with an infinite stream of $\bbx(n)$, we  ensures the number of columns of $\bbX_n$ is finite and the empirical integral estimate tends to its population counterpart, i.e., the integral estimation error becomes very small (or goes to zero) as $n$ tends to infinity \cite{ghosal2000convergence}. Henceforth, we refer to the number of columns in matrix  $\bbX_n$ which parameterizes \eqref{eq:posterior_distribution} as the \emph{model order} {denoted by $M_n$}.

\begin{figure}[t]
	\centering
	\includegraphics[scale=0.25]{diag.png}
	\caption{Approximating the distributions via kernel mean embedding.}
	\label{diag}\vspace{-6mm}
\end{figure}
\subsection{Kernel Mean Embedding}
In this subsection, we introduce kernel mean embedding which maps the measure estimate in the measure space $\Omega_{\bbX_n}$ to the corresponding reproducing kernel Hilbert space (RKHS) denoted by $\mathcal{H}_{{\bbX_n}}$ as shown in Fig. \ref{diag}. 	There is a kernel associated with with RKHS defined as $\kappa:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ and $\kappa(\bbx,\cdot)\in\mathcal{H}_{\bbX_n}$.  In order to appropriately select a subset of $\bbX_n$ which would define an approximator for $\tilde{\mu}_n$ in \eqref{eq:posterior_distribution},  we employ the notion of kernel mean embedding \cite{sriperumbudur2010hilbert} of Dirac measures, and then perform approximation in the corresponding RKHS $\mathcal{H}_{\bbX_n}$.
Doing so is motivated by the fact that operations involving distributions embedded in the RKHS may be evaluated in closed form, whereas in general measure spaces it is often intractable. The explicit value of the map for $ \tilde{\mu}_n$ to RKHS is given by
	%
	%
	 \begin{align}\label{eq:kernel_mean_emb}
		\beta_{n}=\sum_{u=1}^{n} \bbg_n(u) \kappa(\bbx(u),\cdot),
	\end{align}
	%
	 and $\beta_{n}\in\mathcal{H}_{\bbX_n}$. We remark here that the associated kernel $\kappa$ with RKHS is assumed to be a  characteristic kernel which ensure that the mapping $\tilde{\mu}_n\rightarrow\beta_{n}$ is injective \cite[Def. 3.2]{kernel_mean_embedding}. A characteristic  kernel is imperative to make sure that $\|\beta_{\mathbb{P}}-\beta_{\mathbb{Q}}\|_{\mathcal{H}}=0$ if and only if ${\mathbb{P}}={\mathbb{Q}}$ for measures ${\mathbb{P}}$ and ${\mathbb{Q}}$, i.e., that it satisfies the identity of indiscernibles. This makes sure that there is no information loss by introducing the mapping via kernel mean embedding.

For practical purpose, we are interested in obtaining the value of the underlying posterior density  associated with the mean embedding, which necessitates a way to invert the embedding. Doing so is achievable by computing the distributional pre-image \cite{honeine2011preimage}, which for a given $\beta_{n}\in\mathcal{H}_{{\bbX}_n}$ is given by
	%
	 \begin{align}\label{eq:proximal_hilbert_representer}
		\bbg^\star : =&\argmin_{\bbg \in \reals^{n}} \!
		\Big\| \beta_{{n}}
		\!\! -\! \!\sum_{u=1}^{n}{\bbg}(u)\kappa{(\bbx(u),\cdot)} \Big\|_\mathcal{H}^2,
		%
	\end{align}
where $\sum_{u=1}^{n}{\bbg}(u)\kappa{(\bbx(u),\cdot)} $ is the kernel mean embedding for the Dirac measure $\sum_{u=1}^{n}{\bbg}(u)\delta_{\bbd_{\bbx(u)}}$ and ${\bbg}=\bbg^\star$ is obtained as the solution of \eqref{eq:proximal_hilbert_representer}. Therefore, for a given  $\beta_{n}\in\mathcal{H}_{\bbX_n}$, we could recover the corresponding distribution in the measure space $\Omega_{\bbX_n}$  by solving \eqref{eq:proximal_hilbert_representer}. Note that \eqref{eq:proximal_hilbert_representer} exhibits a closed form solution with $\bbg^\star=\bbg_n$, as the distributional measures have a Dirac measure structure. This motivates us to perform the compression in the RKHS $\mathcal{H}_{\bbX_n}$ parameterized by $\bbX_n$.

	Specifically, given past particles collected in a dictionary $\bbX_n$, we seek to select the subset of columns of $\bbX_n$ to formulate its compressed variant $\bbD_n$. We propose to project the kernel mean embedding $\beta_{n}$ onto subspaces $\mathcal{H}_{\bbD_n}=\text{span}\{\kappa(\bbd_u,\cdot) \}_{u=1}^{M_n}$ that consist only of functions that can be represented using dictionary $\bbD_n = [\bbd_1,\ \ldots,\ \bbd_{M_n}] \in \reals^{p \times {M_n}}$.
		%
		More precisely, $\ccalH_{\bbD_n}$ is defined as a subspace in the RKHS $\mathcal{H}_{\bbX_n}$ that can be expressed as a linear combination of kernel evaluations at points $\{\bbd_u\}_{u=1}^{M_n}$.  We enforce efficiency by selecting dictionaries $\bbD_n$ such that $M_n \ll n$. The eventual goal is to achieve a finite memory $M_n=\mathcal{O}(1)$ as $n\rightarrow\infty$ or $\frac{M_n}{n}\rightarrow 0$ as $n\rightarrow\infty$, while ensuring the underlying integral estimate has minimal bias, i.e., that we can obtain nearly consistent finite particle estimates.

\begin{algorithm}[t]
\caption{Compressed Kernelized IS (CKIS)}
\begin{algorithmic}
\label{alg:compressed_online_kernel_importance_sampling}
\REQUIRE Unnormalized target distribution $\widetilde q({\bf x})$, importance distribution $\pi(\bbx)$
\FOR{$n=0,1,2,\ldots,N$}

	\STATE Simulate one sample from importance dist. $\bbx(n) \sim \pi(\bbx)$
	\STATE Compute the importance weight $g{(\bbx(n))}\equiv \frac{  \tilde q(\bbx(n)) }{\pi(\bbx(n))}$
	\STATE Normalize weights $w(n)$ by estimate for summand \eqref{eq:importance_sampling_denominator}: \vspace{-2mm}
\begin{equation*}
\overline w(j)\!:=\! \frac{{w}(j) }{z_n},  j=1,...,n. \; ,  z_n=\sum_{u=1}^n {w}(u)
\end{equation*}\vspace{-3mm}
	\STATE Update the mean embedding via last sample $\&$ weight [cf. \eqref{eq:kernel_mean_emb2}] \vspace{-2mm}
	$$	\tilde\beta_{n}=\beta_{{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot). $$

	\STATE Append dictionary $\tbD_{n} \!= \![\bbD_{n-1} ; \bbx(n)] $ and importance weights $\tilde \bbg_{n} \!= \! [\bbg_{n-1} ; g(\bbx(n)) ] $
	%
	\STATE Compress the mean embedding as (cf. Algorithm \ref{alg:komp}) \vspace{-2mm}
	$$(\beta_{n},\bbD_{n},\bbg_{n}) = \textbf{MMD-OMP}(\tilde\beta_{n},\tbD_{n},\tbg_{n},\epsilon_n)$$

  \STATE Evaluate the pre-image to calculate $\hat\mu_n$ using \eqref{eq:proximal_hilbert_representer}

\STATE  Estimate the expectation as \vspace{-0mm
$\hat{I}_n= \sum_{u=1}^{|\bbD_{n}|}\overline  w(u) \phi(\bbx(u))$
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Greedy Subspace Projections}
Next, we develop a way to only retain statistically significant particles by appealing to ideas from subspace based projections \cite{rockafellar1976monotone}, inspired by \cite{Koppel_POLK,koppelconsistent}.
 To do so, we begin by rewriting the evolution of the mean embedding in \eqref{eq:kernel_mean_emb} as
 	\begin{align}\label{eq:kernel_mean_emb2}
	\beta_{n}=\beta_{{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot).
\end{align}
 We note that the update in \eqref{eq:kernel_mean_emb2} can be written as
	\begin{align}\label{eq:proximal_hilbert_dictionary}
\beta_{n}=&
 \argmin_{f\in\mathcal{H}_{\bbX_n}} \ \|f-\big(\beta_{{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot)\big)\|^2_\mathcal{H} \; ,
\end{align}
where the  equality employs the fact that $\beta_{n}$ can be represented using only the elements in $\mathcal{H}_{\bbX_n}=\text{span}\{\kappa(\bbx(u),\cdot)\}_{u\leq n}$.
 %
 Observe that \eqref{eq:proximal_hilbert_dictionary} defines a projection of the update $\big(\beta_{\tilde{\mu}_{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot)\big)$ onto the subspace defined by $\mathcal{H}_{\bbX_n}$, which we propose to replace at each iteration by a projection onto a subspace defined by dictionary $\bbD_{n}$, which is extracted from the particles observed thus far. The process by which we select $\bbD_{n}$ will be discussed next. To be precise, we replace the update \eqref{eq:proximal_hilbert_dictionary} in which the number of particles grows at each step by the subspace projection onto $\mathcal{H}_{\bbD_{n}}$ as
	%
\begin{align}\label{eq:proximal_hilbert_dictionary2}
	%
	\beta_{n}=& \argmin_{f\in\mathcal{H}_{\bbD_n}}
	\ \|f-\big(\beta_{\tilde{\mu}_{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot)\big)\|^2_\mathcal{H} \nonumber
	\\
	:=& \mathcal{P}_{\mathcal{H}_{\bbD_n}}[\beta_{{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot)].
	%
	\end{align}

Let us define $\tilde\beta_{n}:=\beta_{{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot)$, which means that $\beta_{n}= \mathcal{P}_{\mathcal{H}_{\bbD_n}}[\tilde\beta_{n}]$.
	Let us denote the corresponding dictionary update as
	%
	\begin{align}\label{eq:importance_sampling_stack2}
		%
		\tbg_{n} =& [\bbg_{n-1} ; g{(\bbx(n))} ] \;, \qquad \tbD_{n} = [\bbD_{n-1} ; \bbx(n) ] \nonumber  \\
		\quad \overline{\bbw}_{n} =& z_n \bbg_{n} \;,
		%
	\end{align}
where $\bbD_{n-1}$ has $M_{n-1}$ number of elements and $\tbD_{n}$ has $\tilde M_n= M_{n-1}+1$. Using the expression for mean embedding in \eqref{eq:kernel_mean_emb}, we may write the projection in \eqref{eq:proximal_hilbert_dictionary2} as follows
	\begin{align}\label{eq:proximal_hilbert_representer22}
	\bbg_{n}:=&\argmin_{\bbg \in \reals^{{M}_{n}}}
	\Big\|\! \sum_{s=1}^{{M}_{n}} {\bbg}(s)\kappa{(\bbd_s,\cdot)}
	\! - \!\sum_{u=1}^{\tilde{M}_n}\tilde{\bbg}_n(u)\kappa{(\tbd_u,\cdot)} \Big\|^2_\mathcal{H}\\
	%
	%

	%
	&\hspace{-8mm}=\argmin_{\bbg \in \reals^{{M}_{n}}} \!
	\left( \!\bbg^T\bbK_{\bbD_{n},\bbD_{n}}\bbg
	\!-\! 2\bbg^T\!\bbK_{\bbD_{n},\tbD_{n}}\tbg_{n}
	\!+\! \tbg_{n}\bbK_{\tbD_{n},\tbD_{n}}\tbg_{n} \!\right) \!
	\!\nonumber \; ,
\end{align}
	where we expand the square and define the kernel covariance matrix $\bbK_{\bbD_{n},\tbD_{n}}$ whose $(s,u)^\text{th}$ entry is given by $\kappa{(\bbd_s,{\tbd_u})}$. The other matrices $\bbK_{\tbD_{n},\tbD_{n}}$ and $\bbK_{\bbD_{n},\bbD_{n}}$ are similarly defined. The problem in \eqref{eq:proximal_hilbert_representer22} may be solved explicitly by computing gradients and solving for $\bbg_{n}$ to obtain
\begin{equation} \label{eq:hatparam_update}
	\bbg_{n}=  \bbK_{\bbD_{n},\bbD_{n}}^{-1}\bbK_{\bbD_{n} \tbD_{n}} \tbg_{n}. \;
\end{equation}
Then, the projected estimate of the mean embedding $\tilde\beta_{n}$ is given by
 	%
 	\begin{align}
		\beta_{n}=& \mathcal{P}_{\mathcal{H}_{\bbD_n}}[\tilde\beta_{n}]
		=\sum_{s=1}^{{M}_{n}} {\bbg_n}(s)\kappa{(\bbd_s,\cdot)},
 	\end{align}
	%
	where $\bbg_n$ is obtained as a solution to \eqref{eq:hatparam_update}. Now, for a given dictionary $\bbD_n$, we know how to obtain the projected version of the mean embedding for each $n$. Next, we discuss the procedure to obtain $\bbD_n$ at each $n$.

\begin{algorithm}[t]
	\caption{MMD based Orthogonal Matching Pursuit (MMD-OMP) \hspace{-2mm}}
	\label{alg:komp}
	\begin{algorithmic}
		\REQUIRE  kernel mean embedding $\tilde\beta_{n}$ defined by dict. {$\tbD_n \in \reals^{p \times \tilde{M}_n}$}, coeffs. {$\tbg \in \reals^{\tilde{M}_n}$}, approx. budget  $\epsilon_n > 0$ \\
		\textbf{initialize} $\beta=\tilde\beta_{n}$, dictionary $\bbD = \tbD_n$ with indices $\ccalI$, model order $M=\tilde{M}_n$, coeffs.  $\bbg = \tbg_n$.
		\WHILE{candidate dictionary is non-empty $\ccalI \neq \emptyset$}
		\FOR {{$j=1,\dots,{M}$}}
			\STATE Find minimal approx. error with dictionary element $\bbd_j$ removed \vspace{-2mm}
			{			$$\gamma_j =  \text{MMD}\Big[\tilde\beta_{n}, \sum_{k \in \ccalI \setminus \{j\}} \bbg(k) {\kappa}(\bbd_k, \cdot)\Big] \; .$$ \vspace{-5mm}}
			%
			\ENDFOR
		\STATE Find dictionary index minimizing approximation error: $j^\star = \arg\min_{j \in \ccalI} \gamma_j$

		\INDSTATE{{\bf{if }}  minimal approx. error exceeds threshold $\!\gamma_{j^\star}\!\! > \! \epsilon_n$}
		\INDSTATED{\bf stop}
		\INDSTATE{\bf else}

		\INDSTATED Prune dictionary $\bbD\leftarrow\bbD_{\ccalI \setminus \{j^\star\}}$, {remove the columns associated with index $j^\star$}
		\INDSTATED Revise set $\ccalI \leftarrow \ccalI \setminus \{j^\star\}$ and {model order ${M} \leftarrow {M}-1$.}
		%
		\INDSTATED Update weights $\bbg$ defined by current dictionary $\bbD$

		\vspace{-2mm}{$$\bbg = {\argmin_{\bbw \in \reals^{{M}}}} \big\| \tilde\beta_{n} - \sum_{u=1}^{M} \bbw(u) {\kappa}(\bbd_u, \cdot) \big\|_{\ccalH}$$}\vspace{-3mm}
		%

		\INDSTATE {\bf end}
		\ENDWHILE

		%
		Assign $\bbg_n=\bbg$ and {Evaluate} the projected kernel mean embedding as

			$\beta_{n}=\sum_{u=1}^{{M}} {\bbg_n}(u)\kappa{(\bbd_u,\cdot)}$

		\RETURN $\beta_{n},\bbD_n,\bbg_n$ of complexity $\!M\!\! \leq  \!\tilde{M}$ s.t. $\text{MMD}[\tilde\beta_{n},\beta_{n}]\leq \!\eps_n$
	\end{algorithmic}
\end{algorithm}

\subsection{Dictionary Update}  The selection procedure for the dictionary $\bbD_{n}$ is based upon greedy sparse approximation, a topic studied in compressive sensing  \cite{needell2008greedy}.  The function $\tilde\beta_{n}:=\beta_{{n-1}} + \bbg_n(n) \kappa(\bbx(n),\cdot)$ is parameterized by dictionary $\tbD_{n}$, whose model order is $\tilde{M}_n={M}_{n-1} +1$. We form $\bbD_{n}$ by selecting a subset of $M_{n}$ columns from $\tbD_{n}$ that are best for approximating the kernel mean embedding $\tilde\beta_{_n}$ in terms of maximum mean discrepancy (MMD). As previously noted, numerous approaches are possible for sparse representation. We make use of destructive \emph{ orthogonal matching pursuit} (OMP) \cite{Vincent2002} with allowed error tolerance $\epsilon_n$ to find a dictionary matrix $\bbD_{n}$ based on the one that includes the latest sample point $\tbD_{n}$. With this choice, we can tune the stopping criterion to guarantee the per-step estimates of mean embedding are close to each other. We name the compression procedure {MMD-OMP} and it is summarized in Algorithm \ref{alg:komp}.
From the procedure in Algorithm \ref{alg:komp}, note that the projection operation in \eqref{eq:proximal_hilbert_dictionary2} is performed in a manner that ensures that   $\text{MMD}[\tilde\beta_{n},\beta_{n}]\leq \eps_n$ for all $n$, and we recall that $\beta_{n}$ is the compressed version of $\tilde\beta_{n}$.

\section*{Appendix}

\section{Proof of Consistency of Importance Sampling}\label{first_proof}
Here we state a result on the sample complexity and asymptotic consistency of IS estimators in terms of integral error. We increase the granularity of the proof found in the literature so that the modifications required for our results on compressed IS estimates are laid bare.

\begin{lemma}\label{first_theorem}
\cite{agapiou2017importance}[Theorem 2.1]  Suppose $\pi$, the proposal distribution is absolutely continuous w.r.t. $q$, the population posterior, and both are defined over $\ccalX$. Then define their Radon-Nikodyn derivative:
$
\frac{d q}{d \pi}(\bbx) := \frac{g(\bbx ) }{\int_{\ccalX} g(\bbx) \pi(d\bbx)} \; , \quad \rho := \frac{\pi(g^2)}{q(g^2)}
$
where $g$ is the unnormalized density of $q$ with respect to $\pi$. Moreover, $\rho$ is its second moment (``variance" of  unnormalized density).
Under Assumption \ref{as:first}\ref{as:testfunction1}, Alg. \ref{alg:importance_sampling} contracts to the true posterior as
\begin{align}\label{eq:posterior_contraction}
\sup_{|\phi| \leq 1}  | \mathbb{E}[I_N(\phi) - I(\phi) ] | \leq \frac{12}{N} \rho,\!\!\!
\; \   \mathbb{E}\left[ ( I_N(\phi) - I(\phi) )^2\right]  \leq \frac{4}{N} \rho \; ,
\end{align}
and hence approaches exact consistency as $N \rightarrow \infty$.

\end{lemma}
\begin{myproof}
This is a  more detailed proof than given in \cite{agapiou2017importance}[Theorem 2.1] develop for greater completeness and coherence. Let us denote the empirical random measure by $\pi_{}^N$ as
$\pi_{}^N:=\frac{1}{N}\sum\limits_{n=1}^{N}\delta_{\bbx{(n)}}$, and $\bbx{(n)}\sim \pi$,
where $\pi_{}^N$ is the occupancy measure, which when weighted, yields the importance sampling empirical measure \eqref{eq:importance_sampling_empirical_measure}. Note that the integral approximation at $N$ is denoted by ${I}_N(\phi)$. With the above notation is hand, it holds that
\begin{align}
\pi_{}^N(g)=\int\frac{1}{N}\sum\limits_{n=1}^{N}g(\bbx)\delta_{\bbx{(n)}}(\bbx
)dx=\frac{1}{N}\sum\limits_{n=1}^{N}g(\bbx{(n)}),
\end{align}
 and similarly
\begin{align}
\pi_{}^N(\phi g)=&\int\frac{1}{N}\sum\limits_{n=1}^{N}\delta_{\bbx{(n)}}(\bbx
)\phi(\bbx
)g(\bbx)dx\nonumber \\
=&\frac{1}{N}\sum\limits_{n=1}^{N}\phi(\bbx{(n)})g(\bbx{(n)}).
\end{align}
 From the above equalities, we can write the estimator bias as
\begin{align}
{I}_N(\phi)-I(\phi)=&\frac{\pi_{}^N(\phi g)}{\pi_{}^N(g)}-I(\phi)
\\
=&\frac{\pi_{}^N(\phi g)}{\pi_{}^N(g)}-\left(I(\phi)\frac{\pi_{}^N(g)}{\pi_{}^N(g)}\right)
\\
=&\frac{1}{\pi_{}^N(g)}\left[\pi_{}^N(\phi g)-I(\phi)\pi_{}^N(g)\right]
\\
=&\frac{1}{\pi_{}^N(g)}\pi_{}^N\left((\phi-I(\phi))g\right).
\end{align}
Let us define $\bar{\phi}:=\phi-I(\phi)$ and note that
\begin{align}\label{zero}
\pi(\bar{\phi}g)=0. \ \ \
\end{align}
Rewriting the bias, we get
\begin{align}\label{first}
{I}_N(\phi)-I(\phi)=&\frac{1}{\pi_{}^N(g)}\pi_{}^N\left(\bar{\phi}g\right)\nonumber
\\
=&\frac{1}{\pi_{}^N(g)}\left[\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right],
\end{align}
where the second equality holds from \eqref{zero}. The first term in the bracket is an unbiased estimator for the second one, so that
\begin{align}\label{unbiased}
\mathbb{E}\left[\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right]=0.
\end{align}
Taking the expectation on both sides  of \eqref{first}, we  get
\begin{align}\label{first1}
\mathbb{E}\left[{I}_N(\phi)-I(\phi)\right]=&\mathbb{E}\left[\frac{1}{\pi_{}^N(g)}
\left[\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right]\right].
\end{align}
Since it equals zero, we can add the  expression in \eqref{unbiased} to the right hand side of \eqref{first1} to obtain
\begin{align}\label{first2}
\mathbb{E}\left[{I}_N(\phi)-I(\phi)\right]=&\mathbb{E}\left[\frac{1}{\pi_{}^N(g)}\left[\pi_{}^N\left(\bar{\phi}g\right)
-\pi\left(\bar{\phi}g\right)\right]\right]\nonumber\\
&\quad+\mathbb{E}\left[\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right]
\\
&\hspace{-1cm}=\mathbb{E}\left[\frac{1}{\pi_{}^N(g)}\left[\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right]\right]
\nonumber\\
&\hspace{-1cm}\quad+\mathbb{E}\left[\frac{1}{\pi(g)}\left(\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right)\right].
\end{align}
Taking the expectation operator  outside, we get
\begin{align}
\mathbb{E}\left[{I}_N(\phi)\!-\!I(\phi)\right]=
&\mathbb{E}\!\left[\!\left(\!\frac{1}{\pi_{}^N(g)}\!-\!\frac{1}{\pi(g)}\!\right)\!\left(\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right)\right]\nonumber\\
&\hspace{-2.8cm}=\mathbb{E}\left[\frac{1}{\pi_{}^N(g)\pi(g)}\left(\pi(g)-\pi_{}^N(g)\right)\left(\pi_{}^N\left(\bar{\phi}g\right)-\pi\left(\bar{\phi}g\right)\right)\right].
\end{align}
Next, we split the set of integration to \(A=\{2\pi^N_{MC}(g)>\pi(g)\}\) and its compliment using the property
\[E[f(X)]=E[f(X)1_{A}(X)]+E[f(X)1_{A^c}(X)],\] where \(1_A\) the indicator function of the set \(A\) selecting $A=\{2\pi^N_{MC}(g)>\pi(g)\}$, which takes value 1 if \(x\in A\) and 0 if \(x\notin A\). We get
\begin{align}\label{intermediate}
|\mathbb{E}\left[{I}_N(\phi)-I(\phi)\right]|&\leq|\mathbb{E}\left[{I}_N(\phi)-I(\phi)\right]\boldsymbol{1}_{\{2\pi_{}^N(g)>\pi(g)\}}|  \nonumber\\
&\hspace{-1cm}+|\mathbb{E}\left[{I}_N(\phi)-I(\phi)\right]\boldsymbol{1}_{\{2\pi_{}^N(g)\leq\pi(g)\}}|.
\end{align}
Consider the second term of \eqref{intermediate}, and use the fact that $|\phi|\leq 1$, and so \(|\mu^N(\phi)|, |I(\phi)|\leq 1\) since they are mean values w.r.t. probability measures \(\mu^N,q\) respectively. Then we use \(E[1_A]=P(A)\) and obtain
\begin{align}
|\mathbb{E}\left[{I}_N(\phi)-I(\phi)\right]|\leq&|\mathbb{E}\left[{I}_N(\phi)
-I(\phi)\right]\boldsymbol{1}_{\{2\pi_{}^N(g)>\pi(g)\}}|\nonumber\\
&+2\mathbb{P}\left(2\pi_{}^N(g)\leq\pi(g)\right).\label{intermediate22}
\end{align}
The constant $2$ comes from the fact that $|{I}_N(\phi)-I(\phi)|\leq |{I}_N(\phi)|+|I(\phi)|\leq 2$.
For the first term on the right hand side of \eqref{intermediate22}, from the set condition (, it holds that
\begin{align}
\frac{1}{\pi^N_{MC}(g)\pi(g)}<\frac{2}{\pi^2(g)},
\end{align}
which implies that
\begin{align}
|\mathbb{E}\left[{I}_N(\phi)\!-\!I(\phi)\right]|\leq&\frac{2}{\pi(g)^2}\mathbb{E}\left[|\pi(g)\!-\!\pi_{}^N(g)||\pi_{}^N(\bar{\phi}g)
\!-\!\pi\!\left(\bar{\phi}g\right)\!|\right]\nonumber\\
&+2\mathbb{P}\left(2\pi_{}^N(g)\leq\pi(g)\right).\label{intermediate12}
\end{align}
Finally, to upper bound the first term on the right hand side of \eqref{intermediate12}, we first bound the expectation  using Cauchy-Schwartz
\begin{align}
E[|\pi(g)-&\pi_{}^N(g)||\pi^N(\bar{\phi}g)-\pi(\bar{\phi}g)|]
\nonumber\\
&\leq E[(\pi(g)-\pi_{}^N(g))^2]^{\frac12}E[(\pi^N(\bar{\phi}g)-\pi(g))^2]^\frac12\label{cauchy1}
\end{align}
The first expectation on the right hand side of \eqref{cauchy1} is bounded as follows:
by definition of \(\pi^N\) we have for \(x_n\sim \pi\) independent that
 \begin{align}
 E[(\pi(g)-\pi_{}^N(g))^2]=& E[(\pi(g)-\frac1N\sum_{n=1}^Ng(\bbx{(n)})^2)]\nonumber \\
 &\hspace{-1cm}=\frac1{N^2}E[(\sum_{n=1}^Ng(\bbx{(n)})-N\pi(g))^2],
 \end{align}
 %
 which since \(E[g(\bbx{(n)})]=\pi(g)\)
 %
 and by independence of the \(\bbx{(n)}\) is equal to \[=\frac1{N^2} Var(\sum_{n=1}^Ng(\bbx{(n)}))=\frac1{N^2} \sum_{n=1}^NVar(g(\bbx{(n)})),\] and since \(\bbx{(n)}\) is identically distributed, \(\bbx{(n)}\sim\pi\),
 %
 this is equal to \[\frac{N}{N^2}Var_{u\sim \pi}(g)=\frac1N(\pi(g^2)-\pi(g)^2)\leq \frac1N\pi(g^2).\]
The second expectation on the right hand side of \eqref{cauchy1} is bounded in a similar way along with the fact that \(|\phi|\leq 1\) so that \(|\bar{\phi}|\leq 2\). Then we utilize these upper bounds on the right hand side of \eqref{intermediate} to obtain
\begin{align}
|\mathbb{E}\left[{I}_N(\phi)\!-\!I(\phi)\right]|\leq&\frac{2}{\pi(g)^2}\mathbb{E}\left[|\pi(g)\!-\!\pi_{}^N(g)||\pi_{}^N(\bar{\phi}g)
\!-\!\pi\left(\!\bar{\phi}g\!\right)\!|\right]\nonumber\\
&+2\mathbb{P}\left(2\pi_{}^N(g)\leq\pi(g)\right)\label{intermediate1}\\
\leq&\frac{2}{\pi(g)^2}\frac{1}{\sqrt{N}}\pi(g^2)^{1/2}\frac{2}{\sqrt{N}\pi(g^2)^{1/2}}]\nonumber\\
&+2\mathbb{P}\left(2\pi_{}^N(g)\leq\pi(g)\right)\label{intermediate2}
\end{align}
where the inequalities follow from the fact that the test function is bounded $|\phi|$. Next, note that
\begin{align}\label{prob}
\mathbb{P}\left(2\pi_{}^N(g)\leq\pi(g)\right)=&\mathbb{P}\left(2\left(\pi_{}^N(g)-\pi(g)\right)\leq-\pi(g)\right)\nonumber\\
\leq
& \mathbb{P}\left(2|\pi_{}^N(g)-\pi(g)|\geq\pi(g)\right),
\end{align}
where the first equality  is obtained by subtracting $-2\pi(g)$ from both sides inside the bracket.
Next, we use the Markov inequality, given by
$\mathbb{P}\left(X\geq a\right)\leq \frac{\mathbb{E}(X)}{a}$.
Utilizing this, we can write
\begin{align*}
\mathbb{P}\left(2|\pi_{}^N(g)\!-\!\pi(g)|\geq\pi(g)\right)
\!\leq \frac{2\mathbb{E}\left[|\pi_{}^N(g)\!-\!\pi(g)|\right]}{\pi(g)}
\!\!\leq\!\! \frac{4}{N}\frac{\pi(g^2)}{\pi(g)^2}.
\end{align*}
This implies that
\begin{align}
\mathbb{P}\left(2\pi_{}^N(g)\leq\pi(g)\right)\leq \frac{4}{N}\frac{\pi(g^2)}{\pi(g)^2}.\label{inter2}
\end{align}
Finally, using  the upper bound in \eqref{inter2} in \eqref{intermediate2}, we obtain
\begin{align}
\sup_{|\phi|\leq 1}|\mathbb{E}\left[{I}_N(\phi)-I(\phi)\right]|\leq&\frac{12}{N}\frac{\pi(g^2)}{\pi(g)^2}
\end{align}
which proves the result
\end{myproof}

\section{Proof of Theorem \ref{thm:model_order}}\label{third_proof}
We begin by presenting a lemma which allows us to relate the stopping criterion of our sparsification procedure to a Hilbert subspace distance.

\begin{lemma}\label{lemma_subspace_dist}
Define the distance of an arbitrary feature vector $\bbx$ evaluated by the feature transformation $\psi(\bbx):=\kappa(\bbx,\cdot)$ to $\ccalH_{\bbD}=\text{span}\{\psi(\bbd_n) \}_{n=1}^M$, the subspace of the real space spanned by a dictionary $\bbD$ of size $M$,  as
\begin{align}\label{eq:hilbert_subspace_dist}
\text{dist}( \psi(\bbx) , \ccalH_{\bbD})
= \min_{y\in\ccalH_{\bbD}} | \psi(\bbx) - \bbv^T \bbphi_{\bbD} | \; .
\end{align}
This set distance simplifies to the following least-squares projection when $\bbD \in \reals^{p\times M}$ is fixed
\begin{align}\label{eq:hilbert_subspace_dist_ls}
\text{dist}( \psi(\bbx) , \ccalH_{\bbD})
=& \Big|  \psi(\bbx)
  - \psi(\bbx)\bbpsi_{\bbD}^T\bbK_{\bbD, \bbD}^{-1}
   \bbpsi_{\bbD} \Big|
   .
\end{align}
\end{lemma}

\begin{myproof}
The distance to the subspace $\ccalH_{\bbD}$ is defined as
\begin{align}\label{eq:subspace_dist}
\text{dist}( \psi(\bbx) , \ccalH_{\bbD_n})
=& \min_{y\in\ccalH_{\bbD}} | \psi(\bbx) - \bbv^T \bbpsi_{\bbD}|
\nonumber\\=& \min_{\bbv\in \reals^{M}} | \psi(\bbx) - \bbv^T \bbpsi_{\bbD} | \; ,
\end{align}
where the first equality comes from the fact that the dictionary $\bbD$ is fixed, so $\bbv\in \reals^M$ is the only free parameter. Now plug in the minimizing weight vector $\tbv^\star=\psi(\bbx_n)\bbK_{\bbD_n, \bbD_n}^{-1}\bbpsi_{\bbD_n}$ into \eqref{eq:subspace_dist} which is obtained in an analogous manner to the logic which yields \eqref{eq:proximal_hilbert_representer} - \eqref{eq:hatparam_update}. Doing so simplifies \eqref{eq:subspace_dist} to the following
\begin{align}\label{eq:subspace_dist2}
\text{dist}(\psi(\bbx_n) , \ccalH_{\bbD_n}) =&  \Big|  \psi(\bbx_n)
  - \psi(\bbx_n)[\bbK_{\bbD_n, \bbD_n}^{-1} \bbpsi_{\bbD_n}]^T
   \bbpsi_{\bbD_n} \Big|\nonumber \;\\
   &\hspace{-10mm}=  \Big|  \psi(\bbx_n)
     - \psi(\bbx_n)\bbpsi_{\bbD_n}^T\bbK_{\bbD_n, \bbD_n}^{-1}
      \bbpsi_{\bbD_n} \Big| .
\end{align}
\end{myproof}

Next, we establish that the model order is finite.

\begin{myproof}
Consider the model order of the kernel mean embedding $\beta_{n}$ and $\beta_{n-1}$ generated by Algorithm \ref{alg:compressed_online_kernel_importance_sampling} and denoted by $M_{n}$ and $M_{n-1}$, respectively, at two arbitrary subsequent instances $n$ and $n-1$.
Suppose the model order of the estimate $\beta_{n}$ is less than or equal to that of $\beta_{n-1}$, i.e. $M_{n} \leq M_{n-1}$. This relation holds when the stopping criterion of MMD-OMP ( defined in Algorithm \ref{alg:compressed_online_kernel_importance_sampling}), stated as $\min_{j=1,\dots,{M_{n-1} + 1}} \gamma_j > \eps$, \emph{is not} satisfied for the updated dictionary matrix with the newest sample point $\bbx{(n)}$ appended: $\tbD_{n} = [\bbD_{n-1} ; \bbx{(n)} ]$ [cf. \eqref{eq:importance_sampling_stack2}], which is of size $M_{n-1} + 1$.
Thus, the negation of the termination condition of MMD-OMP in Algorithm \ref{alg:compressed_online_kernel_importance_sampling} must hold for this case, stated as
\begin{align}\label{eq:komp_no_terminate}
\min_{j=1,\dots,{M_{n-1} + 1}} \gamma_j \leq \eps \; .
\end{align}
Observe that the left-hand side of \eqref{eq:komp_no_terminate} lower bounds the approximation error $\gamma_{M_{n-1} + 1}$ for removing the most recent sample $\bbx{(n)}$ due to the minimization over $j$, that is, $\min_{j=1,\dots,{M_{n-1} + 1}} \gamma_j \leq\gamma_{M_{n-1} + 1} $. Consequently, if $\gamma_{M_{n-1} + 1} \leq \eps$, then \eqref{eq:komp_no_terminate} holds and the model order does not grow. Thus it suffices to consider $\gamma_{M_{n-1} + 1}$.
The definition of $\gamma_{M_{n-1} + 1}$ with the substitution of $\beta_{n}$ in \eqref{eq:komp_no_terminate} allows us to write
\begin{align}\label{eq:min_gamma_expand}
\gamma_{M_{n-1}+1}
			&\!\!=\!\!\!\!\!\min_{\bbu\in\reals^{{M_{n-1}}}} \!\!\Big| {\beta_{n-1}} +  g(\bbx{(n)}) \kappa_{\bbx{(n)}}(\bbx)  -\hspace{-0.8cm}\sum_{k \in \ccalI \setminus \{M_{n-1} + 1\}} \hspace{-0.8cm}u_k \kappa_{\bbd_k}(\bbx) \Big| \nonumber\\
			%
			&=\min_{\bbu\in\reals^{{M_{n-1}}}} \Big|  \sum_{k \in \ccalI \setminus \{M_{n-1} + 1\}} \!\!\!  \!\!\!g(\bbx(k)) \kappa_{\bbd_{k}}(\bbx)\\
			&\qquad\qquad\quad\!\!+ g(\bbx{(n)}) \kappa_{\bbx{(n)}}({\bf x})   -\hspace{-0.8cm} \sum_{k \in \ccalI \setminus \{M_{n-1} + 1\}} \hspace{-0.8cm}u_k \kappa_{\bbd_{k}}(\bbx)\Big |\; \nonumber
			,
\end{align}
where we denote $\kappa_{\bbx{(n)}}(\bbx)=\kappa_{(\bbx{(n)},\cdot)}$ and the $k^\text{th}$ column of $\bbD_n$ as $\bbd_k$. The minimal error is achieved by considering the square of the expression inside the minimization and expanding terms to obtain
\begin{align}\label{eq:error_expansion}
\Big| &\!\!\! \!\!\!\sum_{k \in \ccalI \setminus \{M_{n-1} + 1\}} \!\!\!  \!\!\!g(\bbx(k)) \kappa_{\bbd_{k}}(\bbx)+  g(\bbx{(n)}) \kappa_{\bbx{(n)}}({\bf x})   - \hspace{-1cm} \sum_{k \in \ccalI \setminus \{M_{n-1} + 1\}} \hspace{-0.8cm}u_k \kappa_{\bbd_{k}}(\bbx)\Big|^2  \nonumber\\
&=\Big|  \bbg^T\bbkappa_{\bbD_n}(\bbx) + g(\bbx{(n)}) \kappa_{\bbx{(n)}}({\bf x})  -  \bbu^T \bbkappa_{\bbD_n}(\bbx) \Big|^2 \nonumber\\
&=  \bbg^T \bbK_{\bbD_n, \bbD_n} \bbg
+  g(\bbx{(n)})^2
+ \bbu^T \bbK_{\bbD_n, \bbD_n} \bbu  \nonumber \\
&\quad\!+\! 2 g(\bbx{(n)}) \bbw^T\! \bbkappa_{\bbD_n}(\bbx{(n)})\!
\!-\! 2  g(\bbx{(n)}) \bbu^T\!\bbkappa_{\bbD_n}(\bbx{(n)})\nonumber \\
&\qquad-2  \bbw^T\! \bbK_{\bbD_n, \bbD_n}\! \bbu  .
\end{align}
 To obtain the minimum, we compute the stationary solution of \eqref{eq:error_expansion} with respect to $\bbu \in \reals^{M_{n-1}}$ and solve for the minimizing $\tbu^\star$, which in a manner similar to the logic in \eqref{eq:proximal_hilbert_representer} - \eqref{eq:hatparam_update}, is given as
$ \tbu^\star =  {[ g(\bbx{(n)})\bbK_{\bbD_n, \bbD_n}^{-1}\bbkappa_{\bbD_n}(\bbx{(n)})
 +   \bbg ]} \; .$
Plug $\tbu^\star$ into the expression in \eqref{eq:min_gamma_expand} and,  using the short-hand notation $\sum_k u_k \kappa_{\bbd_{k}}(\bbx)= \bbu^T \bbkappa_{\bbD_n}(\bbx)$. Simplifies \eqref{eq:min_gamma_expand} to
\begin{align}\label{eq:min_gamma_optimal_weights}
&\Big| \bbg^T\bbkappa_{\bbD_n}(\bbx) + g(\bbx{(n)}) \kappa_{\bbx{(n)}}({\bf x})  -  \bbu^T \bbkappa_{\bbD_n}(\bbx) \Big| \nonumber\\
& =\! \Big| \bbg^T\bbkappa_{\bbD_n}(\bbx) + g(\bbx{(n)}) \kappa_{\bbx{(n)}}({\bf x}) \! \nonumber \\
& -  {[ g(\bbx{(n)})\bbK_{\bbD_n, \bbD_n}^{-1} \bbkappa_{\bbD_n}(\bbx{(n)})\! \!
 + \!\!  \bbg ]}^T
\!\!\bbkappa_{\bbD_n}(\bbx) \! \Big|  \nonumber\\
& =\! \Big| g(\bbx{(n)}) \kappa_{\bbx{(n)}}({\bf x})\! -\! {[ g(\bbx{(n)})  \bbK_{\bbD_n, \bbD_n}^{-1}\bbkappa_{\bbD_n}(\bbx{(n)})
 ]}^T \!\!
\bbkappa_{\bbD_n}(\bbx)\Big|  \nonumber\\
& =\! g(\bbx{(n)}) \Big| \kappa_{\bbx{(n)}}({\bf x})-  \bbkappa_{\bbD_n}(\bbx^n)^T\bbK_{\bbD_n, \bbD_n}^{-1} \bbkappa_{\bbD_n}(\bbx)\Big|
\end{align}
Notice that the right-hand side of \eqref{eq:min_gamma_optimal_weights} may be identified as the distance to the subspace $\ccalH_{\bbD_n}$ in \eqref{eq:subspace_dist2} defined in Lemma \ref{lemma_subspace_dist} scaled by a factor of {$g(\bbx{(n)})$}. We may upper-bound the right-hand side of \eqref{eq:min_gamma_optimal_weights} as
\begin{align}\label{eq:min_gamma_optimal_weights3}
   g(\bbx{(n)}) &\Big| \kappa_{\bbx{(n)}}({\bf x})-  \bbkappa_{\bbD_n}(\bbx{(n)})^T \bbK_{\bbD_n, \bbD_n}^{-1}\bbkappa_{\bbD_n}(\bbx)\Big| \nonumber\\
   &=   g(\bbx{(n)})\text{dist}(\kappa_{\bbx{(n)}}(\bbx) , \ccalH_{\bbD_n})
   %
\end{align}
where we have applied \eqref{eq:hilbert_subspace_dist_ls} regarding the definition of the subspace distance on the right-hand side of \eqref{eq:min_gamma_optimal_weights3} to replace the absolute value term. Now, when the {MMD-OMP} stopping criterion is violated, i.e., \eqref{eq:komp_no_terminate} holds, this implies $\gamma_{M_{n-1} + 1} \leq \eps$. Therefore, the right-hand side of \eqref{eq:min_gamma_optimal_weights3} is upper-bounded by $\epsilon$, and we can write
\begin{align}\label{eq:min_gamma_optimal_weights5}
 g(\bbx{(n)})\text{dist}(\kappa_{\bbx{(n)}}(\bbx) , \ccalH_{\bbD_n})\leq \epsilon.
   %
\end{align}
 After rearranging the terms in \eqref{eq:min_gamma_optimal_weights5}, we can write
\begin{align}\label{eq:min_gamma_optimal_weights4}
  \text{dist}(\kappa_{\bbx{(n)}}(\bbx),\ccalH_{\bbD_n}) \leq \frac{\epsilon}{ g(\bbx{(n)})} \;,
   %
\end{align}
where we have divided both sides by {$g(\bbx{(n)})$}.
Observe that if \eqref{eq:min_gamma_optimal_weights4} holds, then $\gamma_{M_{n}} \leq \eps$ holds, but since $\gamma_{M_{n}} \geq \min_{j} \gamma_j $, we may conclude that \eqref{eq:komp_no_terminate} is satisfied. Consequently the model order at the subsequent step does not grow which means that $M_{n} \leq M_{n-1}$ whenever \eqref{eq:min_gamma_optimal_weights4} is valid.

Now, let's take the contrapositive of the preceding expressions to observe that growth in the model order ($M_{n} = M_{n-1} + 1$) implies that the condition
\begin{align}
\label{eq:min_gamma2}
\text{dist}(\kappa_{\bbx{(n)}}(\bbx),\ccalH_{\bbD_n}) > \frac{\epsilon}{ g(\bbx{(n)})}
\end{align}
holds.  Therefore, each time a new point is added to the model, the corresponding map $\kappa_{{\bf x}}(\bbx{(n)})$ is guaranteed to be at least a distance of {$\frac{\epsilon}{g(\bbx{(n)})} $} from every other feature map in the current model.
In canonical works such as \cite{bengtsson2008curse,bickel2008sharp}, the largest self-normalized importance weight is shown to be bounded by a constant. Under the additional hypothesis that the \emph{un-normalized} importance weight is bounded by some constant $W$, then we have via \eqref{eq:min_gamma2}
$\text{dist}(\kappa_{\bbx{(n)}}(\bbx),\ccalH_{\bbD_n}) > \frac{\epsilon}{W} .$
 Therefore, For a fixed compression budget $\epsilon$, {the MMD-OMP} stopping criterion is violated for the newest point whenever distinct dictionary points $\bbd_k$ and $\bbd_j$  for $j,k\in\{1,\dots,M_{n-1}\}$, satisfy the condition $\text{dist}(\kappa_{{\bf x}}(\bbd_j),\kappa_{\bbd_{k}}(\bbx)) > \frac{\epsilon}{W}$. Next, we follow a similar argument as provided in the proof of Theorem 3.1 in \cite{1315946}.   Since $\ccalX$ is compact and $\kappa_{{\bf x}}$ is continuous, the range $\kappa_{{\bf x}}(\ccalX) $ of the feature space $\ccalX$ is compact.   Therefore, the minimum number of balls (covering number) of radius $\kappa$ (here, $\kappa = \frac{\epsilon}{W}$) needed to cover the set $\kappa_{{\bf x}}(\ccalX)$ is finite (see, e.g., \cite{anthony2009neural}) for a finite compression budget $\epsilon$. The finiteness of the covering number implies that the number of elements in the dictionary $M_N$ will be finite  and using \cite[Proposition 2.2]{1315946}, we can characterize the number of elements in the dictionary as
 %
$1 \leq M_{N}\leq C\left(\frac{W}{\eps}\right)^{2p}$,
 %
where $C$ is a constant depending upon the space $\mathcal{X}$.
\end{myproof}\vspace{-0mm}

\section{Application and Numerical tests}\label{sec:fields}
\subsection{Classification with Fairness Constraints}

With the increase in the process of automated decision making and the size of analyzed data becomes large there are growing concerns from government, civil organization and researchers \cite{sweeney2013discrimination} that automated decision can lead to loss of fairness, transparency and accountability. As algorithmic decision making process replaces human supervision and are becoming data driven, even in
the absence of intent, they can be unfair. To evaluate the fairness of a decision making process authors in \cite{zafar2015fairness} introduced the notion of disparate impact. A decision making process has disparate impact if it outcomes unfairly benefit (or hurt) particular groups of people with similar sensitive attributes such as race and sex. We will use $p$\% rule to quantify disparate impact as mentioned in \cite{zafar2015fairness}. Basically the $p$\%-rule states that the ratio
between the percentage of examples with a certain
sensitive attribute value classified as positive  in decision
outcome and the percentage of examples without
that value also classified as positive must not
be less than $p:100$.

In binary classification, the primary task is to learn a mapping function $f(\bbx)$ between feature vectors $\bbx \in \mathcal{R}^d$ and class labels $y \in \{-1,1\}$, using available training data set $[\bbx_i,y_i]^N_{i=1}$.  Typically the target is to obtain a decision boundary, characterized by a set of parameters $\bbtheta^*$, which gives the highest classification accuracy for the test data set, by minimizing a loss function $L(\bbtheta)$ over the training set. Let $r_{\bbtheta^*}(\bbx)$ be the distance between decision boundary and feature vector $\bbx$. For any new example $\bbx_i$ from test set, the classifier will predict $f_{\bbtheta}(\bbx_i)=1$ if  $r_{\bbtheta^*}(\bbx_i)\geq 0$ and $f_{\bbtheta}(\bbx_i)=-1$ for $r_{\bbtheta^*}(\bbx_i)< 0$. However, if class labels of training examples are correlated with sensitive attribute $\{\bbs_i\}_{i=1}^N$, then the classifier may suffer from disparate impact. That is the percentage of examples having a certain sensitive
attribute  with $r_{\bbtheta^*}(\bbx)\geq 0$ may differ dramatically
from the percentage of examples without this sensitive attribute having $r_{\bbtheta^*}(\bbx)\geq 0$\cite{zafar2015fairness}.

 We intend to design a classifier which
maximizes accuracy under the fairness constraints. In order to measure  the fairness/unfairness of decision boundary we define the covariance between the sensitive
attributes $\{\bbs_i\}_{i=1}^N$, and  the distance $\{r_{\bbtheta}(\bbx)\}_{i=1}^{N}$ between decision boundary and feature vector as:
\begin{align}
Cov(\bbs,r_{\bbtheta}(\bbx))&= \mbE[(\bbs-\bar{\bbs})r_{\bbtheta}(\bbx)]-\mbE[(\bbs-\bar{\bbs})]\bar{r}_{\bbtheta}(\bbx)\nonumber\\
&\approx \frac{1}{N} \sum_{i=1}^{N} (\bbs_i-\bar{\bbs})r_{\bbtheta}(\bbx_i).
\label{Cov_intro}
\end{align}

Now to incorporate the fairness constraint we can formulate the problem as follow:

 \begin{align}
&\bbtheta^*:=\argmin_{\bbtheta} L(\bbtheta)\nonumber\\
&\text{s.t.}\;\;\; \frac{1}{N}\sum_{i=1}^{N}(\bbs_i-\bar{\bbs})r_{\bbtheta}(\bbx_i)\leq \bbc\nonumber\\&\;\;\;\;\;\
\frac{1}{N}\sum_{i=1}^{N}(\bbs_i-\bar{\bbs})r_{\bbtheta}(\bbx_i)\geq -\bbc,
\label{app_prob_intro}
\end{align}
here $\bbc$ is the covariance threshold. Basically, $\bbc$ presents a
trade off between fairness and accuracy, such that decreasing $\bbc$  towards zero, results in classifier with a larger p\%-rule but with a larger loss in accuracy. In this work we will use logistic regression
classifier, whose mapping function is given by the following probability distribution:
\begin{align}
\label{logistic_distribution}
p(y_i=1|\bbx_i,\bbtheta)=\frac{1}{1+e^{-\theta^T\bbx_i}},
\end{align}
here, we obtain $\bbtheta$ by solving $\argmin_{\theta}-\sum_{i=1}^{N} \log(p_i|\bbx_i,\bbtheta)$ over the training set. Thus problem \eqref{app_prob_intro} becomes:

\begin{align}
&\min_{\bbtheta} \;\;\;\frac{-1}{N}\sum_{i=1}^{N}\log{p(y_i|\bbx_i,\bbtheta)}\nonumber\\
&\text{s.t.}\;\;\; \frac{1}{N}\sum_{i=1}^{N}(\bbs_i-\bar{\bbs})\bbtheta^T\bbx_i\leq \bbc\nonumber\\&\;\;\;\;\;\
\frac{1}{N}\sum_{i=1}^{N}(\bbs_i-\bar{\bbs})\bbtheta^T\bbx_i\geq -\bbc.
\label{app_prob_main}
\end{align}

Here, we have chosen the decision boundary simply the hyperplane defined by $\bbtheta^T\bbx+b=0$. Further, we appended 1 to all feature vectors reducing the decision boundary from $\bbtheta^T\bbx+b=0$ to $\bbtheta^T\bbx=0$. From \eqref{stochastic_lagrangian} and \eqref{app_prob_main} we can
define Lagrangian for $k^{th}$ realization of $y$ and $\bbx$ as:

\begin{align}
\hat{\mathcal{L}}_k(\bbtheta,\bblam)=&-\log p(y_k|\bbx_k,\bbtheta)+\lam_1\big((\bbs_k-\bar{\bbs})\bbtheta^T\bbx_k-\bbc\big)\nonumber\\&-\lam_2\big((\bbs_k-\bar{\bbs})\bbtheta^T\bbx_k+\bbc\big)-\frac{\delta}{2}\eps_k(\lam_1^2+\lam_2^2).
\label{app:lagrangian}
\end{align}

\begin{figure}[!tbp]
  \begin{subfigure}[b]{0.24\textwidth}
    \includegraphics[width=\textwidth]{Obj_syn}
    \caption{Objective}
    \label{obj_syn}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.24\textwidth}
    \includegraphics[width=\textwidth]{CV_syn}
    \caption{Constraint violation}
    \label{vio_syn}
  \end{subfigure}
  \caption{Convergence results on Synthetic Data set}
\end{figure}

\begin{figure}
	\centering
	\setcounter{subfigure}{0}
	\begin{subfigure}{0.7\columnwidth}		\includegraphics[width=\linewidth, height = 0.6\linewidth]{scatter_pi4}
		\caption{$\phi/4$}
		\label{scatter_pi4}
	\end{subfigure}\hspace{2.8cm}
	\begin{subfigure}{0.7\columnwidth}
		\includegraphics[width=\linewidth, height = 0.6\linewidth]{scatter_pi8}
		\caption{$\phi/8$}
		\label{scatter_pi8}
	\end{subfigure}
	\caption{Plots for synthetic data: For the scatter plot shown in (a) and (b), the solid light blue lines show the decision boundaries for unconstrained case. The dashed lines show the decision boundaries trained to maximize accuracy under fairness constraints.}
	\label{results_syn}
	\vspace{-0mm}
\end{figure}

\begin{figure*}
	\centering
	\setcounter{subfigure}{0}
	\begin{subfigure}{0.6\columnwidth}		\includegraphics[width=\linewidth, height = 0.6\linewidth]{p_vs_c_syn}
		\caption{p\%-rule vs. Cov.}
		\label{P_C_SYN}
	\end{subfigure}\hfill
	\begin{subfigure}{0.6\columnwidth}
		\includegraphics[width=\linewidth, height = 0.6\linewidth]{acc_vs_p_syn}
		\caption{Accuracy vs. p\%-rule}
		\label{A_P_SYN}
	\end{subfigure}\hfill
	\begin{subfigure}{0.6\columnwidth}
		\includegraphics[width=\linewidth, height = 0.6\linewidth]{z_vs_c_syn}
		\caption{\% in Positive class vs. Cov.}
		\label{Z_C_SYN}
	\end{subfigure}
	\caption{Panel (a) shows the correspondence between the
covariance and the p\%-rule for classifiers trained under fairness constraints. Panel (b) shows the accuracy
against p\%-rule value. Panel (c) shows the percentage of protected and non-protected examples in the
positive class against the covariance }
\label{SYN}
	\vspace{-0mm}
\end{figure*}

\begin{figure*}
	\centering
	\setcounter{subfigure}{0}
	\begin{subfigure}{0.6\columnwidth}		\includegraphics[width=\linewidth, height = 0.6\linewidth]{p_vs_c_adult_compare}
		\caption{p\%-rule vs. Cov.}
		\label{P_adult}
	\end{subfigure}\hfill
	\begin{subfigure}{0.6\columnwidth}
		\includegraphics[width=\linewidth, height = 0.6\linewidth]{acc_adult_compare}
		\caption{Accuracy vs. p\%rule}
		\label{acc_adult}
	\end{subfigure}\hfill
	\begin{subfigure}{0.6\columnwidth}
		\includegraphics[width=\linewidth, height = 0.6\linewidth]{time_compare_adult}
		\caption{Time variation with Sample size}
		\label{time}
	\end{subfigure}
	\caption{Results on Adult Dataset[]: Panel (a) shows variation of P\% with Covariance, (b) shows the accuracy
against p\%-rule, (c) shows the variation of time required by algorithm with increase in sample size of synthetic data.}
\label{compare}
	\vspace{-0mm}
\end{figure*}

For the simulation purposes we will use both the synthetic and real world data. We will show that the formulation in \eqref{app_prob_main} allows us to finely control the fairness, at a small loss in accuracy of the classifier.
\subsubsection{Synthetic data} We generate synthetic data the same way as mentioned in \cite{zafar2015fairness}. Total 4000 binary labels are generated uniformly at random. Two different Gaussian distributions are generated as: $p(x|y=1)=N([2;2],[5, 1;1, 5])$ and $p(x|y=-1)=N([-2;-2],[10, 1;1, 3])$. The feature vectors are assigned to labels by drawing samples from above two distributions.  For sensitive attribute $s$ we have used Bernoulli distribution: $p(s=1)=p(\hat{\bbx}|y=1)/p(\hat{\bbx}|y=1)+p(\hat{\bbx}|y=-1)$, here $\hat{\bbx}=[\cos(\phi), -\sin(\phi);\sin(\phi), \cos(\phi)]$. The correlation between sensitive attribute and class labels (i.e. disparate impact) depends on the parameter $\phi$. The smaller the $\phi$, the higher the correlation. In Fig. \ref{results_syn}- Fig. \ref{SYN}, we plot the results of this numerical experiment.

\begin{figure}[!tbp]
  \begin{subfigure}[b]{0.24\textwidth}
    \includegraphics[width=\textwidth]{Obj_adult}
    \caption{Objective }
    \label{obj_adult}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.24\textwidth}
    \includegraphics[width=\textwidth]{CV_adult}
    \caption{Constraint violation }
    \label{vio_adult}
  \end{subfigure}
  \caption{Convergence results on Adult Data set}
\end{figure}

Fig. \ref{obj_syn} shows the objective $(1/N)\sum_{i}\mbE_{\bbtheta_i}f(\bbx,\bbtheta_i) $
versus iteration k. In Fig. \ref{vio_syn}, we plot the constraint violation graph. The decision boundaries generated by the
classifiers for maximizing accuracy with fairness constraints is shown in Fig.\ref{scatter_pi4}-\ref{scatter_pi8}. The unconstrained
decision boundary is represented by a solid line while boundaries for different covariance thresholds, c is shown in dotted line. It can be observed that incorporating fairness constraint in data generation process, results into the rotation of the decision boundary (compared to unconstrained boundary). The rotation is more as the threshold value c is decreased. Fig.\ref{scatter_pi4} and Fig.\ref{scatter_pi8} also shows that increase in the correlation in the data i.e. chaining $\phi$ from $\pi/4$ to $\pi/8$ causes more rotation. Additionally, in Fig.\ref{SYN} we investigates the relation between p\% rule, accuracy and covariance. Fig.\ref{P_C_SYN} shows that higher the covariance, the lower the p\%-
rule the classifier satisfies. Moreover, Fig.\ref{A_P_SYN} shows the trade-off between p\% rule and accuracy: more p\% (i.e. smaller covariance or a larger rotation) leads to a more fair solution, but at the cost of reduced accuracy. In Fig.\ref{Z_C_SYN} we plotted  the percentage of protected and non-protected examples in the positive class against the covariance. It shows that to achieve more fairness (i.e. reduced cov or increased p\% rule) classifier moves more non-protected examples to negative class and protected examples to positive class. These results shows that the problem formulation of \eqref{app_prob_main} successfully incorporates fairness constraint by exploiting the covariance defined in \eqref{Cov_intro} and allows to control fairness constraint with small loss in accuracy.

\subsubsection{Real data}
We experiment with the Adult income dataset []. It has a total of
45222 examples, each with 14 features like education level, age, marriage status. The label (binary), denotes which subject has income  (positive class) or less (negative class) than 50K \$ . We have considered sex as a binary sensitive attribute. We refer females as protected group while
males as non-protected groups. In our experiments, we use 70\% of data for training while rest (30\%) are used for testing. We repeat our experiment 5 times and all the reported results are average of this.

The plot of objective and constraint violation versus iteration is shown in Fig.\ref{obj_adult} and Fig.\ref{vio_adult} respectively. We compare our approach to method presented in \cite{zafar2015fairness}. Fig.\ref{P_adult} shows variation of p\%-rule with covariance, as expected reducing covariance results in higher p\% value. Also it establishes that our proposed algorithm shows almost same p-\% value as that of \cite{zafar2015fairness} for different covariance values.  The accuracy (Fig.\ref{acc_adult}) of our algorithm although slighlty low, is comparable to  method presented in \cite{zafar2015fairness}. But the major advantage of proposed algorithm is in terms of time taken. As shown in Fig.\ref{time} our method clear has an advantage in terms of time as compared to method in \cite{zafar2015fairness}.

\section{Conclusions}

We focused on Bayesian inference where one streams simulated Monte Carlo samples to approximate an unknown posterior via importance sampling. Doing so may consistently approximate any function of the posterior at the cost of infinite memory. Thus, we proposed Algorithm \ref{alg:compressed_online_kernel_importance_sampling} (CKIS) to approximate the posterior by a kernel density estimate (KDE) projected onto a nearby lower-dimensional subspace, which allows online compression as particles arrive in perpetuity. We established that the bias of CKIS depends on kernel bandwidth and compression budget, providing a tradeoff between statistical accuracy and memory. Experiments demonstrated that we attain memory-reduction by orders of magnitude with very little estimation error. This motivates future application to memory-efficient versions of Monte Carlo approaches to nonlinear signal processing problems such as localization, which has been eschewed due to its computational burden.

\section{Balancing Consistency and Memory}\label{sec:convergence}

In this section, we characterize the convergence behavior of our posterior compression scheme. Specifically, we establish conditions under which the asymptotic bias is proportional to the kernel bandwidth and the compression parameter using posterior distributions given by Algorithm \ref{alg:compressed_online_kernel_importance_sampling}. To frame the discussion, we note that the pure SNIS estimator \eqref{eq:SNIS_estimator} $I_N(\phi)$, whose particle complexity goes to infinity, is asymptotically consistent \cite{mcbook}[Ch. 9, Theorem 9.2],
and that the empirical posterior $I_N(\phi)$ contracts to its population analogue at a $\ccalO(1/N)$ rate where $N$ is the number of particles. To establish consistency, we first detail the technical conditions required.
\subsection{Assumptions and Technicalities}\label{apx_technicalities}
\begin{assumption}\label{as:first}
Recall the definition of the target distribution $q$ from Sec. \ref{sec:prob} following \eqref{eq:posterior}. Denote the integral of test function $\phi:\ccalX \rightarrow \reals$ as $q(\phi)$.
\begin{enumerate}[label=(\roman*)]
\item Assume that $\phi$  is absolutely integrable, i.e., $q(|\phi|)<\infty$, and has absolute value at most unit $|\phi|\leq 1$. \label{as:testfunction1}
\item The test function has absolutely continuous second derivative, and $\int_{\bbx\in\ccalX} \phi''(\bbx) d\bbx < \infty$. \label{as:testfunction2}
\end{enumerate}
\end{assumption}
\begin{assumption}\label{as:2}
The kernel function associated with RKHS is such that  $\int_{\bbx \in \ccalX} \kappa_{\bbx^{(n)}}(\bbx) = 1$,  $\int_{\bbx \in \ccalX} \bbx \kappa_{\bbx^{(n)}} (\bbx) = 0$, and $\sigma_{\kappa}^2 = \int_{\bbx \in \ccalX} \bbx^2 \kappa_{\bbx^{(n)}}(\bbx) >0$.
\end{assumption}

\blue{\begin{assumption}\label{as:approximation}
Let $I_{1}(\phi)$ and $I_{2}(\phi)$ be two integral estimators for test function $\phi$, the we define the approximation error for $\phi\notin\mathcal{F}$ where  $\mathcal{F}:=\{f\in\mathcal{H}~|~ \|f\|_{\mathcal{H}}\leq 1\}$, as
 	 \begin{align}\label{approximation}
	I(\phi,f)= &\sup_{|\phi| \leq 1,f \in \mathcal{F}} \left(\mathbb{E}[I_1(\phi) \!-\! {I_2(\phi)}] \right)-\left(\mathbb{E}[ I_1(f) \!-\! {I_2(f)}] \right),
\end{align}
and we assume that $I(\phi,f)\leq \mathcal{Z}$, where $\mathcal{Z}$ is a finite constant.
\end{assumption}}
\red{skeptical about the above assumption}
Assumption \ref{as:first}\ref{as:testfunction1} is a textbook condition in the analysis of Monte Carlo methods, and appears in \cite{mcbook}. Assumption \ref{as:first}\ref{as:testfunction2} and \ref{as:2} are required conditions for establishing consistency of kernel density estimates and are standard -- see \cite{wasserman2006all}[Theorem 6.28].
 We begin by noting that under Assumption \ref{as:first}, we have classical statistical consistency of importance sampling as the number of particles becomes large as stated in Lemma \ref{first_theorem} in Appendix \ref{first_proof}.
This result permits characterizing the bias of Algorithm \ref{alg:compressed_online_kernel_importance_sampling} given next. \blue{The Assumption \ref{as:approximation} here non-standard which is used to bound the error due to operating in the RKHS. We note that if $\phi\in\mathcal{F}$ which is the case for most of the practical applications [\red{citations}], the value of $\mathcal{Z}$ would exactly be  $0$. }

\blue{\begin{lemma}\label{intermidiate_lemma}
Define the second moment of the true unnormalized density $\rho$ as in Lemma \ref{first_theorem}. Then, under Assumptions \ref{as:first}-\ref{as:approximation}, the estimator of Alg. \ref{alg:compressed_online_kernel_importance_sampling} satisfy
\begin{align}\label{lemma}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \sum_{n=1}^{N}\epsilon_n+\frac{24}{N} \rho +\mathcal{Z}.
	%
\end{align}
where $\epsilon_n$ is the compression budget for each $n$.
\end{lemma}}

\begin{myproof}
	\blue{Inspired by \cite{agapiou2017importance}, begin by denoting $\hat I_N(\phi)$ as the integral estimate given by Algorithm \ref{alg:compressed_online_kernel_importance_sampling}. Consider the bias of the integral estimate ${\hat I_N(\phi) - I(\phi)}$, and add and subtract $I_N(\phi)$, the uncompressed self-normalized importance estimator, the result of Algorithm \ref{alg:importance_sampling}, i..e., we get}
	%
	\begin{align}\label{new}
		\hat I_N(\phi) - I(\phi)=& \hat I_N(\phi) -I_N(\phi)+I_N(\phi) - I(\phi).
	\end{align}
	%

	%
	Take the expectation on both sides with respect to the population posterior \eqref{eq:posterior} to obtain
	%
	\blue{\begin{align}\label{new2}
			\mathbb{E}[\hat I_N(\phi) - I(\phi)]=& \mathbb{E}[\hat I_N(\phi) -  I_N(\phi)]+\mathbb{E}[I_N(\phi) - I(\phi)].
	\end{align}}
	%

	%
	Let's compute the $\sup$ of both sides of \eqref{new2} over range $|\phi | \leq 1$ followed by fact that a sup of a sum is upper-bounded by the sum of individual terms:
	%

	%
	\begin{align}\label{new3}
		%
		\sup_{|\phi | \leq 1} \left(\mathbb{E}[\hat I_N(\phi) - I(\phi)] \right)&\leq  \sup_{|\phi | \leq 1} \left(\mathbb{E}[\hat I_N(\phi) -  I_N(\phi)] \right)\nonumber
		\\

		&\quad+\! \sup_{|\phi| \leq 1}\!\!\left([\mathbb{E}[I_N(\phi) \!-\! I(\phi\!)] \right)\!.
		%
	\end{align}
	%
	Now, compute the absolute value of both sides of \eqref{new3}, and to the last two terms, pull the absolute value inside the supremum.
	%

	Then, \eqref{eq:posterior_contraction} (Lemma \ref{first_theorem}) applied to the last term yields:
	%
	\begin{align}\label{new4}
		%
		\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq & \left|\!\sup_{|\phi| \leq 1} \left(\mathbb{E}[\hat I_N(\phi) \!-\!  {I_N(\phi)}]\! \right)\!\right|\nonumber
		\\
		&+\frac{24}{N} \rho.
		%
	\end{align}
	%
	Thus, it remains to characterize the first term on the right-hand side of \eqref{new4},

	which is the integral approximation error associated using the compressed integral estimation via kernel mean embedding. \blue{

		To proceed with the analysis, let us add subtract the supremum over the space $\mathcal{F}:=\{f\in\mathcal{H}~|~ \|f\|_{\mathcal{H}}\leq 1\}$
		to the first term on the right hand side of \eqref{new4}, we get
		%
		\begin{align}\label{IPM0}
			\sup_{|\phi| \leq 1} \left(\mathbb{E}[\hat I_N(\phi) \!-\! {I_N(\phi)}] \right)
			=&\sup_{f \in \mathcal{F} }\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right)\nonumber
			\\
			&+I(\phi,f),
		\end{align}
		where $I(\phi,f)$ is defined in \eqref{approximation}.

		%

		Following Assumption \ref{as:approximation}, we could write \eqref{IPM0} as
		%
		\begin{align}\label{IPM00}
			\sup_{|\phi| \leq 1} \left(\mathbb{E}[\hat I_N(\phi) \!-\! {I_N(\phi)}] \right)
			=&\sup_{f \in \mathcal{F} }\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right)+\mathcal{Z}.
		\end{align}
		%

		Note that the first term on the right hand side of \eqref{IPM00} describes the instance of an integral probability metric (IPM) [Muller 1997] given by
		%
		\begin{align}\label{IPM1}
			\sup_{f \in \mathcal{F} } &\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right)\nonumber
			\\
			&=\sup_{f \in \mathcal{F} } \left(\int f(\bbx)d\hat \mu_N -\int f(\bbx)d\tilde\mu_N\right)
	\end{align} }
	%
	%
	\blue{where $\hat\mu_N$  is the pre-image unnormalized density estimate obtained by solving \eqref{eq:proximal_hilbert_representer}. The IPM in \eqref{IPM1} is exactly equal Maximum Mean Discrepancy (MMD)\cite{fortet1953convergence,muller1997integral}. Hence, we could write }
	%
	\blue{\begin{align}\label{eq:mmd}
			%
			\sup_{f \in \mathcal{F} } \left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right) =\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}.
			%
	\end{align}}
	%
	\blue{where $\gamma_{N}$ is the kernel mean embedding corresponding to the uncompressed measure estimate $ \tilde\mu_N$. Next, let us consider the term $\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}$ and add subtract the per step uncompressed estimate $\tilde\beta_{N}$ [cf. \eqref{eq:importance_sampling_stack2}] to obtain
	}
	%
	\blue{\begin{align}\label{triangle}
			\|\beta_{N}-\gamma_{N}\|_{\mathcal{H}} =& \|(\beta_{ N}-\tilde\beta_{ N})+(\tilde\beta_{ N}-\gamma_{N})\|_{\mathcal{H}}\nonumber
			\\
			\leq & \|\beta_{ N}-\tilde\beta_{N}\|_{\mathcal{H}}+\|\tilde\beta_{ N}-\gamma_{\nu_N}\|_{\mathcal{H}}\nonumber
			\\
			\leq &  \epsilon_N+\|\tilde\beta_{N}-\gamma_{N}\|_{\mathcal{H}}
	\end{align}}
	%
	\blue{where the last inequality holds from the fact that $\|\beta_{N}-\tilde\beta_{ N}\|_{\mathcal{H}}\leq \epsilon_N$ (cf. Algorithm \ref{alg:komp}). Now we substitute the values of $\tilde\beta_{N}$ and $\gamma_{N}$ using the update in \eqref{eq:kernel_mean_emb2}, we get }
	%
	\blue{\begin{align}\label{triangle2}
			\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}
			\leq &  \epsilon_N+\|\beta_{ {N-1}}-\gamma_{{N-1}}\|_{\mathcal{H}}.
	\end{align}}
	%
	Using the above recursion, we could obtain
	%
	\blue{\begin{align}\label{triangle3}
			\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}
			\leq &  \sum_{n=1}^{N}\epsilon_n.
		\end{align}
		as stated in Theorem \ref{thm:main_result}. Hence, using the upper bound of \eqref{triangle3} into \eqref{eq:mmd}, and then we an write the final upper bound in \eqref{new4} as
		%
		\begin{align}\label{new5}
			%
			\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \sum_{n=1}^{N}\epsilon_n+\frac{24}{N} \rho +\mathcal{Z}.
			%
		\end{align}}
\end{myproof}

\blue{Next, we present the main result of this paper. }

\blue{\begin{theorem}\label{thm:main_result}
Let $\rho$ as in Lemma \ref{lemma} under Assumptions \ref{as:first}-\ref{as:approximation}, then

1) for diminishing compression budget $\epsilon_n=\alpha^n$ with $\alpha=(0,1)$, the estimator of Alg. \ref{alg:compressed_online_kernel_importance_sampling} satisfy
\begin{align}\label{diminish}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \frac{\alpha}{1-\alpha}+\mathcal{O}\left(\frac{1}{N}\right) +\mathcal{Z}.
	%
\end{align}
To obtain $\delta$ accurate integral estimate, we need $N\geq\mathcal{O}\left(\frac{1}{\delta}\right)$ and $0<\alpha\leq 1/(1+(2/\delta))$.

2) for constant compression budget $\epsilon_n=\epsilon>0$ and memory $\mathcal{M}:=\mathcal{O}\left(\frac{1}{\epsilon^{1/(2p)}}\right)$
\begin{align}\label{final0}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq \mathcal{O}\left(\frac{N}{\mathcal{M}^{1/2p}}+\frac{1}{N}\right)
	%
\end{align}
and
\begin{align}
	\mathcal{O}\left(\frac{1}{\delta}\right)\leq N\leq \mathcal{O}\left(\delta {\mathcal{M}^{1/(2p)}}\right),
\end{align}
which implies that $\mathcal{M}\geq\mathcal{O}\left(\frac{1}{\delta^{4p}}\right)$.
\end{theorem}}
\begin{myproof}
Consider the statement of Lemma \ref{lemma} and to proceed next, we characterize the behavior of term $\sum_{n=1}^{N}\epsilon_n$ since it eventually determines the final bias in the integral estimation.

1) \blue{Diminishing compression budget: Let us consider $\epsilon_n=(\alpha)^n$ with $\alpha=(0,1)$, which implies that
\begin{align}\label{diminishing}
\sum_{n=1}^{N}\epsilon_n= \frac{\alpha(1-\alpha^N)}{1-\alpha}\leq \frac{\alpha}{1-\alpha}.
\end{align}
Substituting \eqref{diminishing} into the right hand side of \eqref{new5}, we get
\begin{align}\label{new6}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \frac{\alpha}{1-\alpha}+\frac{24}{N} \rho.
	%
\end{align}
To obtain $\delta$ accurate integral estimate, we need $N\geq\frac{48\rho}{\delta}$ and $0<\alpha\leq 1/(1+(2/\delta))$.}

2) \blue{Constant compression budget: Let us consider $\epsilon_n=\epsilon$, which implies that
	%
	\begin{align}\label{constant_epsilon}
		\sum_{n=1}^{N}\epsilon_n= N\epsilon.
	\end{align}
Using \eqref{constant_epsilon} into \eqref{new5}, we can write
\begin{align}\label{final}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  N\epsilon+\frac{24}{N} \rho.
	%
\end{align}
For a constant compression budget $\epsilon$, from Theorem \ref{thm:model_order}, we have
\blue{\begin{align}
		M_{\infty}\leq \mathcal{O}\left(\frac{1}{\eps^{2p}}\right):=\mathcal{M}.
\end{align}}
}
\blue{If we are given with a maximum memory requirement $\mathcal{M}$, then we could obtain the value of compression budget we need to choose $\epsilon$ as
\begin{align}
	\epsilon=\frac{G}{\mathcal{M}^{1/(2p)}}
\end{align}
where $G$ is the bound on the unnomalized weight $g(x(u))\leq G$ for all $u$. Using this lower bound value of $\epsilon$ into \eqref{final}, we get
\begin{align}\label{final1}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq \frac{NG}{\mathcal{M}^{1/2p}}+\frac{24}{N} \rho.
	%
\end{align}}
\blue{Note that the first term in the above expression increases with $N$ and the second term decreases with $N$, hence we obtain a tradeoff between memory and accuracy for the importance sampling based estimator. For a given memory $\mathcal{M}$ (number of elements we could store in the dictionary) and the required accuracy $\delta$, we obtain the following bound on the number of iterations $N$
\begin{align}
	\frac{48\rho}{\delta}\leq N\leq \frac{\delta {M^{1/(2p)}}}{2G},
\end{align}
which implies that for the increased accuracy we need to run for more iterations but we need more memory  and vice versa.    }
\end{myproof}

Theorem \ref{thm:main_result}  establishes that the compressed kernelized importance sampling scheme proposed in Section \ref{sec:algorithm} is \emph{nearly} asymptotically consistent, and can be made arbitrarily close to exact consistency by sending the compression budget $\epsilon_n$ to null. However, when these parameters are fixed positive constants, they provide a tunable tradeoff between bias and memory. That is, when the compression budget is a positive constant, then the memory of the posterior distribution representation is finite, as we formalize next.
\begin{theorem}\label{thm:model_order}
 Under Assumptions \ref{as:first}-\ref{as:2} (in Appendix \ref{apx_technicalities}), for compact feature space $\ccalX$ and bounded importance weights $g(\bbx^{(n)})$, the model order for Algorithm \ref{alg:compressed_online_kernel_importance_sampling}, $ M_n<\infty$ for all $n$ given by
\blue{\begin{align}
		M_{\infty}\leq \mathcal{O}\left(\frac{1}{\eps^{2p}}\right).
\end{align}}
\end{theorem}
Theorem \ref{thm:model_order} (proof in Appendix \ref{third_proof}) contrasts the classical bottleneck in the number of particles required to represent an arbitrary posterior, which grows unbounded \cite{agapiou2017importance}. While this is a pessimistic estimate, experimentally we observe orders of magnitude reduction in complexity compared to exact importance sampling, which is the focus of the subsequent section.

\section{Balancing Consistency and Memory}\label{sec:convergence}

In this section, we characterize the convergence behavior of our posterior compression scheme. Specifically, we establish conditions under which the asymptotic bias is proportional to the kernel bandwidth and the compression parameter using posterior distributions given by Algorithm \ref{alg:compressed_online_kernel_importance_sampling}. To frame the discussion, we note that the NIS estimator \eqref{eq:SNIS_estimator} $I_N(\phi)$, whose particle complexity goes to infinity, is asymptotically consistent \cite{mcbook}[Ch. 9, Theorem 9.2],
and that the empirical posterior $\mu_N(\cdot)$ contracts to its population analogue at a $\ccalO(1/N)$ rate where $N$ is the number of particles. To establish consistency, we first detail the technical conditions required.
\subsection{Assumptions and Technical Conditions}\label{apx_technicalities}
\begin{assumption}\label{as:first}
Recall the definition of the target distribution $q$ from Sec. \ref{sec:prob} (following \eqref{eq:posterior}). Denote the integral of test function $\phi:\ccalX \rightarrow \reals$ as $q(\phi)$.
\begin{enumerate}[label=(\roman*)]
\item Assume that $\phi$  is absolutely integrable, i.e., $q(|\phi|)<\infty$, and has absolute value at most unit $|\phi|\leq 1$. \label{as:testfunction1}
\item The test function has absolutely continuous second derivative, and $\int_{\bbx\in\ccalX} \phi''(\bbx) d\bbx < \infty$. \label{as:testfunction2}
\end{enumerate}
\end{assumption}
\begin{assumption}\label{as:2}
The kernel function associated with RKHS is such that  $\int_{\bbx \in \ccalX} \kappa_{\bbx^{(n)}}(\bbx) = 1$,  $\int_{\bbx \in \ccalX} \bbx \kappa_{\bbx^{(n)}} (\bbx) = 0$, and $\sigma_{\kappa}^2 = \int_{\bbx \in \ccalX} \bbx^2 \kappa_{\bbx^{(n)}}(\bbx) >0$.
\end{assumption}

\begin{assumption}\label{as:approximation}
Let $I_{N}(\phi)$ and $\hat I_{N}(\phi)$ be the integral estimators for test function $\phi$ associated with the uncompressed and compressed posterior densities. We define the approximation error for $\phi\notin\mathcal{F}$ where  $\mathcal{F}:=\{f\in\mathcal{H}~|~ \|f\|_{\mathcal{H}}\leq 1\}$, as
 	 \begin{align}\label{approximation}
\!	I(\phi,f\!)\!= \!\sup_{|\phi| \leq 1}\!\! \left(\mathbb{E}[\hat I_N(\phi) \!-\!  {I_N(\phi)}]\! \right)\!-\! \sup_{f \in \mathcal{F} }\!\!\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right),
\end{align}
We assume that $I(\phi,f)\leq G$, where $G$ is a finite constant.
\end{assumption}
Assumption \ref{as:first}\ref{as:testfunction1} is a textbook condition in the analysis of Monte Carlo methods, and appears in \cite{mcbook}. Assumptions \ref{as:first}\ref{as:testfunction2} and \ref{as:2} are required conditions for establishing consistency of kernel density estimates and are standard -- see \cite{wasserman2006all}[Theorem 6.28].
 We begin by noting that under Assumption \ref{as:first}, we have classical statistical consistency of importance sampling as the number of particles becomes large as stated in Lemma \ref{first_theorem} in Appendix \ref{first_proof}.
This result enables characterizing the bias of Algorithm \ref{alg:compressed_online_kernel_importance_sampling}, given next in Lemma \ref{intermidiate_lemma}. Assumption \ref{as:approximation} is non-standard and we use it to bound the error due to continuity conditions imposed by operating in the RKHS. We note that if $\phi\in\mathcal{F}$ which is the case for most practical applications, then $G=0$.

\begin{lemma}\label{intermidiate_lemma}
Define the second moment of the true unnormalized density $\rho$ as in Lemma \ref{first_theorem}. Then, under Assumptions \ref{as:first}-\ref{as:approximation}, the estimator of Alg. \ref{alg:compressed_online_kernel_importance_sampling} satisfies
\begin{align}\label{lemma}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \sum_{n=1}^{N}\epsilon_n+\frac{24}{N} \rho +G.
	%
\end{align}
where $\epsilon_n$ is the compression budget for each $n$.
\end{lemma}

\begin{myproof}
	Inspired by \cite{agapiou2017importance}, begin by denoting $\hat I_N(\phi)$ as the integral estimate given by Algorithm \ref{alg:compressed_online_kernel_importance_sampling}. Consider the bias of the integral estimate ${\hat I_N(\phi) - I(\phi)}$, and add and subtract $I_N(\phi)$, the uncompressed normalized importance estimator that is the result of Algorithm \ref{alg:importance_sampling}, to obtain
	%
	\begin{align}\label{new}
		\hat I_N(\phi) - I(\phi)=& \hat I_N(\phi) -I_N(\phi)+I_N(\phi) - I(\phi).
	\end{align}
	%

	%
	Take the expectation on both sides with respect to the population posterior \eqref{eq:posterior} to obtain
	%
	\begin{align}\label{new2}
			\mathbb{E}[\hat I_N(\phi) - I(\phi)]=& \mathbb{E}[\hat I_N(\phi) -  I_N(\phi)]+\mathbb{E}[I_N(\phi) - I(\phi)].
	\end{align}
	%

	%
	Let's compute the $\sup$ of both sides of \eqref{new2} over range $|\phi | \leq 1$ and use the fact that a sup of a sum is upper-bounded by the sum of individual terms:
	%

	%
	\begin{align}\label{new3}
		%
		\sup_{|\phi | \leq 1} \left(\mathbb{E}[\hat I_N(\phi) - I(\phi)] \right)&\leq  \sup_{|\phi | \leq 1} \left(\mathbb{E}[\hat I_N(\phi) -  I_N(\phi)] \right)\nonumber
		\\

		&\quad+\! \sup_{|\phi| \leq 1}\!\!\left([\mathbb{E}[I_N(\phi) \!-\! I(\phi\!)] \right)\!.
		%
	\end{align}
	%
Now add and subtract the supremum over the space $\mathcal{F}:=\{f\in\mathcal{H}~|~ \|f\|_{\mathcal{H}}\leq 1\}$
		to the first term on the right hand side of \eqref{new3} to write
		%
		\begin{align}\label{IPM0_0}
			&\sup_{|\phi| \leq 1} \Big(\mathbb{E}[\hat I_N(\phi) \!-\! {I(\phi)}] \Big) \\
		&	\leq \sup_{f \in \mathcal{F} }\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right)+ \sup_{|\phi| \leq 1}\!\!\left([\mathbb{E}[I_N(\phi) - I(\phi)] \right)\nonumber \\
		&+\underbrace{\sup_{|\phi| \leq 1} \left(\mathbb{E}[\hat I_N(\phi) \!-\!  {I_N(\phi)}]\! \right)- \sup_{f \in \mathcal{F} }\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right)}_{I(\phi,f)\leq G} \nonumber
			%
		\end{align}
Observe that the last line on the right-hand side of the preceding expression defines the integral function approximation error $I(\phi,f)$ defined in \eqref{approximation}, which is upper-bounded by constant $G$ (Assumption \ref{as:approximation}).
Now, compute the absolute value of both sides of \eqref{IPM0_0}, and to the second term on the first line, pull the absolute value inside the supremum.
	%

	Doing so allows us to apply \eqref{eq:posterior_contraction} (Lemma \ref{first_theorem}) to the second term on the first line, the result of which is:
	%
	\begin{align}\label{new4}
		%
		\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq & \sup_{f \in \mathcal{F} }\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right)\nonumber
		\\
		&+\frac{24}{N} \rho+G,
		%
	\end{align}
	where $G$ is defined in Assumption \ref{as:approximation} and note that $G=0$ if $\phi \in \mathcal{H}$.
	%

		It remains to address the first term on the right hand side of \eqref{new4}, which noticeably defines an instance of an integral probability metric (IPM) [Muller 1997], i.e.,
		%
		\begin{align}\label{IPM1}
			\sup_{f \in \mathcal{F} } &\left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right)\nonumber
			\\
			&=\sup_{f \in \mathcal{F} } \left(\int f(\bbx)d\hat \mu_N -\int f(\bbx)d\tilde\mu_N\right),
	\end{align}
	%
	%
	where $\hat\mu_N$  is the pre-image unnormalized density estimate obtained by solving \eqref{eq:proximal_hilbert_representer}. The IPM in \eqref{IPM1} is exactly equal to Maximum Mean Discrepancy (MMD)\cite{fortet1953convergence} for test functions  in the RKHS $f\in\mathcal{H}$. This observation allows us to write
	%
	\begin{align}\label{eq:mmd}
			%
			\sup_{f \in \mathcal{F} } \left(\mathbb{E}[\hat I_N(f) \!-\! {I_N(f)}] \right) =\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}.
			%
	\end{align}
	%
	{where $\gamma_{N}$ is the kernel mean embedding corresponding to the uncompressed measure estimate $ \tilde\mu_N$. Next, consider the term $\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}$ and add and subtract the per step uncompressed estimate $\tilde\beta_{N}$ [cf. \eqref{eq:importance_sampling_stack2}] to obtain
	}
	%
	\begin{align}\label{triangle}
			\|\beta_{N}-\gamma_{N}\|_{\mathcal{H}} =& \|(\beta_{ N}-\tilde\beta_{ N})+(\tilde\beta_{ N}-\gamma_{N})\|_{\mathcal{H}}\nonumber
			\\
			\leq & \|\beta_{ N}-\tilde\beta_{N}\|_{\mathcal{H}}+\|\tilde\beta_{ N}-\gamma_{\nu_N}\|_{\mathcal{H}}\nonumber
			\\
			\leq &  \epsilon_N+\|\tilde\beta_{N}-\gamma_{N}\|_{\mathcal{H}},
	\end{align}
	%
	where the last inequality holds from the fact that $\|\beta_{N}-\tilde\beta_{ N}\|_{\mathcal{H}}\leq \epsilon_N$ (cf. Algorithm \ref{alg:komp}). Now we substitute the values of $\tilde\beta_{N}$ and $\gamma_{N}$ using the update in \eqref{eq:kernel_mean_emb2}, and we get
	%
	\begin{align}\label{triangle2}
			\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}
			\leq &  \epsilon_N+\|\beta_{ {N-1}}-\gamma_{{N-1}}\|_{\mathcal{H}}.
	\end{align}
	%
	Using the above recursion, we easily obtain
	%
	{\begin{align}\label{triangle3}
			\|\beta_{ N}-\gamma_{N}\|_{\mathcal{H}}
			\leq &  \sum_{n=1}^{N}\epsilon_n.
		\end{align}
Hence, using the upper bound of \eqref{triangle3} in \eqref{eq:mmd}, and then substituting the result into \eqref{new4} yields
		%
		\begin{align}\label{new5}
			%
			\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \sum_{n=1}^{N}\epsilon_n+\frac{24}{N} \rho +G.
			%
		\end{align}}
		as stated in Lemma \ref{intermidiate_lemma}.
\end{myproof}

{With this technical lemma in place, we are ready to state the main result of this paper. }

\begin{theorem}\label{thm:main_result}
Define $\rho = \frac{\pi(g^2)}{q(g^2)}$ as the variance of the unnormalized importance density with respect to importance weights $g$ as  in Lemma \ref{first_theorem}. Then under Assumptions \ref{as:first}-\ref{as:approximation}, we have the following approximate consistency results:
\begin{enumerate}[label=(\roman*)]
\item \label{statement:diminish} for diminishing compression budget $\epsilon_n=\alpha^n$ with $\alpha\in(0,1)$, the estimator of Alg. \ref{alg:compressed_online_kernel_importance_sampling} satisfies
\begin{align}\label{thm:diminish}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \frac{\alpha}{1-\alpha}+\mathcal{O}\left(\frac{1}{N}\right) +G.
	%
\end{align}
To obtain a $\delta$ accurate integral estimate, we need at least $N\geq\mathcal{O}\left(\frac{1}{\delta}\right)$ particles and compression attenuation rate sufficiently large such that $0<\alpha\leq 1/(1+(2/\delta))$.
\item  \label{statement:constant} for constant compression budget $\epsilon_n=\epsilon>0$ and memory $\mathcal{M}:=\mathcal{O}\left(\frac{1}{\epsilon^{1/(2p)}}\right)$
\begin{align}\label{final0}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq \mathcal{O}\left(\frac{N}{\mathcal{M}^{1/2p}}+\frac{1}{N}\right)
	%
\end{align}
and
\begin{align}
	\mathcal{O}\left(\frac{1}{\delta}\right)\leq N\leq \mathcal{O}\left(\delta {\mathcal{M}^{1/(2p)}}\right),
\end{align}
which implies that $\mathcal{M}\geq\mathcal{O}\left(\frac{1}{\delta^{4p}}\right)$.
\end{enumerate}
\end{theorem}
\begin{myproof}
Consider the statement of Lemma \ref{lemma} and to proceed next, we characterize the behavior of the term $\sum_{n=1}^{N}\epsilon_n$ since it eventually determines the final bias in the integral estimation.

{\bf \noindent Theorem \ref{thm:main_result}\ref{statement:diminish}}: Diminishing compression budget: Let us consider $\epsilon_n=(\alpha)^n$ with $\alpha=(0,1)$, which implies that
\begin{align}\label{diminishing}
\sum_{n=1}^{N}\epsilon_n= \frac{\alpha(1-\alpha^N)}{1-\alpha}\leq \frac{\alpha}{1-\alpha}.
\end{align}
Substituting \eqref{diminishing} into the right hand side of \eqref{new5}, we get
\begin{align}\label{new6}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  \frac{\alpha}{1-\alpha}+\frac{24}{N} \rho.
	%
\end{align}
To obtain a $\delta$ accurate integral estimate, we need $N\geq\frac{48\rho}{\delta}$ and $0<\alpha\leq 1/(1+(2/\delta))$.

 \noindent{ \bf{Theorem \ref{thm:main_result}\ref{statement:constant}}}: Constant compression budget: Let us consider $\epsilon_n=\epsilon$, which implies that
	%
	\begin{align}\label{constant_epsilon}
		\sum_{n=1}^{N}\epsilon_n= N\epsilon.
	\end{align}
Using \eqref{constant_epsilon} in \eqref{new5}, we can write
\begin{align}\label{final}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq  N\epsilon+\frac{24}{N} \rho.
	%
\end{align}
For a constant compression budget $\epsilon$, from Theorem \ref{thm:model_order}, we have
\begin{align}
		M_{\infty}\leq \mathcal{O}\left(\frac{1}{\eps^{2p}}\right):=\mathcal{M}.
\end{align}
If we are given a maximum memory requirement $\mathcal{M}$, then we can choose $\epsilon$ as
\begin{align}
	\epsilon=\frac{G}{\mathcal{M}^{1/(2p)}},
\end{align}
where $G$ is a bound on the unnomalized weight $g(x(u))\leq G$ for all $u$. Using this lower bound value of $\epsilon$ in \eqref{final}, we get
\begin{align}\label{final1}
	%
	\big|\sup_{|\phi| \leq 1}  \big(\mathbb{E}[\hat I_N(\phi)- I(\phi)] \big) \big| \leq \frac{NG}{\mathcal{M}^{1/2p}}+\frac{24}{N} \rho.
	%
\end{align}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.15]{histogram.eps}
	\caption{Particle histogram for direct sampling experiment. }
	\label{hist}
	\vspace{-8mm}
\end{figure}

  \begin{figure*}[t]
	\centering
	\begin{subfigure}[b]{0.32\textwidth}
		\centering
		\includegraphics[width=\textwidth]{estimation_1.eps}
		\caption[\red{y label}]%
		{{\small Integral estimate. \vspace{-0mm}}}
		\label{fig:normalized}
	\end{subfigure}
	\begin{subfigure}[b]{0.32\textwidth}
		\centering
		\includegraphics[width=\textwidth]{approx_error_1.eps}
		\caption[]%
		{{\small Integral Error between Algs. \ref{alg:importance_sampling} - \ref{alg:compressed_online_kernel_importance_sampling}. }}
		\label{fig:error}
	\end{subfigure}
	\begin{subfigure}[b]{0.32\textwidth}
		\centering
		\includegraphics[width=\textwidth]{model_order_1.eps}
		\caption[]%
		{{\small Model Order. }}
		\label{fig:model_order}
	\end{subfigure}
	\caption[ The average and standard deviation of critical parameters ]
	{\small Simulation results for Alg. \ref{alg:compressed_online_kernel_importance_sampling} run with Gaussian kernel ($h=0.01$) and compression budget $\epsilon=3.5$ for the problem \eqref{eq:sample_problem2}. The memory-reduction scheme nearly preserves statistical consistency, while yielding reasonable complexity, whereas Alg. \ref{alg:importance_sampling} attains exact consistency as its memory grows unbounded with index $n$. {All the plots are averaged over $10$ iterations.}}
	\label{fig1}
	\vspace{-0mm}
\end{figure*}

Note that the first term in the above expression increases with $N$ and the second term decreases with $N$, hence we obtain a tradeoff between memory and accuracy for the importance sampling based estimator. For a given memory $\mathcal{M}$ (number of elements we could store in the dictionary) and the required accuracy $\delta$, we obtain the following bound on the number of iterations $N$
\begin{align}
	\frac{48\rho}{\delta}\leq N\leq \frac{\delta {M^{1/(2p)}}}{2G},
\end{align}
which implies that for increased accuracy we need to run for more iterations but need more memory,  and vice versa.
\end{myproof}

Theorem \ref{thm:main_result}  establishes that the compressed kernelized importance sampling scheme proposed in Section \ref{sec:algorithm} is \emph{nearly}
asymptotically consistent. Note that the right hand side in \eqref{thm:diminish} consists of three terms depending upon $\alpha$, $\frac{1}{N}$, and $G$. If we ignore $G$, which actually depends upon the approximation associated with function $\phi(\cdot)$, the other two terms can be made arbitrarily small by making $\alpha$ close to zero and a very high $N$. Hence, the integral estimation can be made arbitrarily close to exact integral. However, when these parameters are fixed positive constants, they provide a tunable tradeoff between bias and memory. That is, when the compression budget is a positive constant, then the memory of the posterior distribution representation is finite, as we formalize next.
\begin{theorem}\label{thm:model_order}
 Under Assumptions \ref{as:first}-\ref{as:2} (in Section \ref{apx_technicalities}), for compact feature space $\ccalX$ and bounded importance weights $g(\bbx^{(n)})$, the model order $M_n$ for Algorithm \ref{alg:compressed_online_kernel_importance_sampling}, for all $n$ is bounded by
\begin{align}
1\leq 	M_{n}\leq \mathcal{O}\left(\frac{1}{\eps^{2p}}\right).\end{align}
\end{theorem}
Theorem \ref{thm:model_order} (proof in Appendix \ref{third_proof}) contrasts with the classical bottleneck in the number of particles required to represent an arbitrary posterior, which grows unbounded \cite{agapiou2017importance}. While this is a pessimistic estimate, experimentally we observe orders of magnitude reduction in complexity compared to exact importance sampling, which is the focus of the subsequent section. Observe, however, that this memory-reduction does not come for free, as once the compression budget is fixed, the memory is fixed by the ratio $\frac{1}{\epsilon^{2p}}$ that eventually results in a lower bound on the accuracy of the integral estimate.

\section{Introduction}\label{sec:introduction}
Bayesian inference is devoted to estimating unknowns by considering as them random variables and constructing a posterior distribution. This posterior distribution incorporates the information of available observations (likelihood function) which is merged with prior knowledge about the  unknown (prior distribution) \cite{robert2013monte}.
Its application is widespread, spanning statistics \cite{robert2007bayesian}, signal processing \cite{candy2016bayesian}, machine learning \cite{murphy2012machine}, genetics \cite{beaumont2004bayesian}, communications \cite{7227082}, econometrics \cite{jangmin2004stock}, robotics \cite{wurm2010octomap}, among many other examples.
{Bayesian inference is only possible in a very small subset of problems (e.g., when the underlying model between observations and the hidden state is linear and corrupted by Gaussian noise  \cite{kalman}). In some cases, it is possible to linearize nonlinear models and still obtain closed-form (but approximate) solutions  \cite{hoshiya1984structural}. Beyond linearity, Bayesian inference may be tackled by Gaussian Processes when smoothness and unimodality are present \cite{rasmussen2004gaussian}.
However, in most models of interest, closeed-form expressions are not available, and the posterior distribution of the unknowns must be approximated.}

The standard approximation methodologies in Bayesian inference are either (a) Monte Carlo (MC) algorithms \cite{neal1993probabilistic}, which include Markov chain Monte Carlo (MCMC) methods \cite{martino2014metropolis}, importance sampling (IS) \cite{elvira2019generalized}, and particle filters (PFs) \cite{djuric2003particle}; or (b) variational algorithms \cite{blei2017variational}. The later approach approximates the posterior by using an optimization algorithm to select within a parametrized family (e.g., by minimizing the KL divergence). Variational algorithms can optimize the parameters sequentially via the solution of a stochastic optimization problem \cite{minka2013expectation}. In recent years, efforts to approximate the expectation by sampling have been investigated, e.g., see \cite{hoffman2013stochastic}.
Unfortunately, unless the prior belongs to a simple exponential family, the parametric update is defined by a non-convex objective, meaning that asymptotic unbiasedness is mostly beyond reach. Mixture models have been considered \cite{liu2016stein}, but their convergence is challenging to characterize and the subject of recent work on resampling  \cite{zhang2018stochastic}.

In contrast, MC is a general approach to Bayesian inference based upon sampling (i.e., the simulation of samples/particles), and is known to generate (weighted) samples that eventually converge to the true distribution/quantity of interest \cite{agapiou2017importance,second}. However, the scalability of Monte Carlo methods is still an ongoing challenge from several angles, in that to obtain consistency, the number of particles must go to infinity, and typically its scaling is exponential in the parameter dimension \cite{bengtsson2008curse}. These scalability problems are the focus of this work, which we specifically study in the context of importance sampling (IS), a very relevant family of MC methods.
We focus on IS, as compared with Markov chain Monte Carlo (MCMC), due to advantages such as, e.g., no burn-in period, simple parallelization \cite{robert2018accelerating}, built-in approximation of the normalizing constant that is  useful in many practical problems (e.g., model selection), and the ability to incorporate adaptive mechanisms without compromising its convergence \cite{bugallo2017adaptive}.  IS methods approximate expectations of arbitrary functions of the unknown parameter via weighted samples generated from one or several proposal densities \cite{first,elvira2019generalized}. Their convergence in terms of the integral approximation error, which vanishes  as the number of samples increases, has been a topic of interest recently \cite{first,agapiou2017importance}, and various statistics to quantify their performance have been proposed \cite{elvira2018rethinking}.

Our goal is to alleviate the dependence of the convergence rate on the representational complexity of the posterior estimate. To do so, we propose projecting the posterior density onto a finite statistically significant subset of particles {after every particle is generated.\footnote{Doing so may be generalized to scenarios where projection can be performed after generating a fixed number $T$ of particles, a form of mini-batching, but this is omitted for simplicity.}} However, doing so directly in a measure space is often intractable to evaluate. By embedding this density in a reproducing kernel Hilbert space (RKHS) via its kernel mean embedding  \cite{sriperumbudur2010hilbert}, we may  compute projections of distributions via parametric computations involving the RKHS. More specifically, kernel mean embeddings extend the idea of feature mapping to spaces of probability distributions, which, under some regularity conditions \cite[Sec. 3.8]{sriperumbudur2010hilbert}, admits a bijection between probability distributions and RKHS elements.

{\noindent \bf Contributions.} Based upon this insight, we propose a compression scheme that operates online within importance sampling, sequentially deciding which particles are statistically significant for the integral estimation. To do so, we invoke the idea of distribution embedding \cite{sriperumbudur2010hilbert} and map our unnormalized distributional estimates to RKHS, {in contrast to \cite{martino2021compressed,martino2021astronomy}}. We show that the empirical kernel mean embedding estimates in RKHS are parameterized by the importance weights and particles. Then, we propose to sequentially project embedding estimates onto subspaces of the dictionary of particles, where the dictionary is greedily selected to ensure compressed estimates are close to the uncompressed one (according to some metric). This greedy selection is achieved with a custom variant of matching pursuit \cite{Pati1993} based upon the Maximum Mean Discrepancy, which is an easily computable way to evaluate an integral probability metric by virtue of the RKHS mean embedding. The underpinning of this idea is similar to gradient projections in optimization, which has been exploited recently to surmount memory challenges in kernel and Gaussian process regression \cite{koppelconsistent,Koppel_POLK}.

We establish that the asymptotic bias of this method is a tunable constant depending on the compression parameter. These results yield an approach to importance reweighting that mitigates particle degeneracy, i.e., retaining a large number of particles with small weights \cite{li2014fight}, by directly compressing the embedding estimate of the posterior in the RKHS domain, rather than statistical tests that require sub-sampling in the distributional space \cite{bugallo2017adaptive,elvira2017improving}. The compression is performed \emph{online}, without waiting until the total number of samples $N$ are available, which is typically impractical.
Experiments demonstrate that this approach yields an effective tradeoff of consistency and memory, in contrast to the classical curse of dimensionality of MC methods.

{\noindent \bf Additional Context.} Dimensionality reduction of nonparametric estimators been studied in disparate contexts. A number of works fix the sparsity dimension and seek the best $N$-term approximation in terms of estimation error. When a likelihood model is available, one terms the resulting active set a Bayesian \emph{coresets} \cite{campbell2019automated}. Related approaches called ``herding"  assume a fixed number of particles and characterize the resulting error in a kernel-smoothed density approximation \cite{chen2010super,lacoste2015sequential,keriven2018sketching,futami2019bayesian}. In these works, little guidance is provided on how to determine the number of points to retain.

 In contrast, dynamic memory methods automatically tune the number of particles to ensure small model bias. For instance, in \cite{campbell2018bayesian}, a rule for retainment based on gradient projection error (assuming the likelihood is available) is proposed, similar to those arising in kernel regression \cite{Koppel_POLK}. Most similar to our work is the setting where a likelihood/loss is unavailable and one must resort to metrics on density estimates, i.e., statistical tests, for whether new particles are significant. Specifically, in particle filters, multinomial resampling schemes can be used with Chi-squared tests to determine whether the current number of particles should increase/decrease \cite{pmlr-v32-jun14,elvira2016adapting}. The performance of these approaches have only characterized when their budget parameter goes to null or sparsity dimension goes to infinity. In contrast, in this work, we are especially focused on finite-sample analysis when budget parameters are left fixed, in order to elucidate the tradeoffs between memory and consistency, both in theory and practice.

\section{Elements of Importance Sampling}\label{sec:prob}

In Bayesian inference \cite{sarkka2013bayesian}[Ch. 7], we are interested in computing expectations
\begin{align}\label{eq:template_problem}
I(\phi):=\mathbb{E}_{  \bbx}[{\phi}(\bbx)\given \bby_{1:K}  ] = \int_{\bbx\in\ccalX} \phi(\bbx)  p(\bbx|\bby_{1:K})  d\bbx
\end{align}
on the basis of a set of available observations  {$ \bby_{1:K}:=\{\bby_{1:K}\}_{k=1}^{K}$}, where $\phi : \ccalX\rightarrow \reals$ is an arbitrary function, $\bbx$ is a random variable taking values in $\ccalX\subset \reals^p$ which is typically interpreted as a hidden parameter, and $\bby$ is some observation process whose realizations $\bby_{1:K}$ are assumed to be informative about parameter $\bbx$. {For example, $\phi(\bbx) = \bbx$ yields the computation of the posterior mean, and $\phi(\bbx)=\bbx^p$ denotes the $p$-th moment.}
In particular, define the posterior density\footnote{Throughout, densities are with respect to the Lebesgue measure on $\reals^p$.}
\begin{align}\label{eq:posterior}
p\left(\bbx \given \bby_{1:K}\right)  = \frac{p\left(\bby_{1:K} \given  \bbx  \right) p\left(\bbx\right)}{p\left( \bby_{1:K}\right)}.
\end{align}
We seek to infer the posterior \eqref{eq:posterior} with $K$ data points $\bby_{1:K}$ available at the outset. Even for this setting, estimating \eqref{eq:posterior} has unbounded complexity \cite{li2005curse,tokdar2010importance} {when the form of the posterior is unknown}. Thus, we prioritize efficient estimates of \eqref{eq:posterior} from an online stream of samples from an \emph{importance density} to be subsequently defined.
Begin by defining posterior $q(\bbx) $ and un-normalized posterior $\widetilde q(\bbx)$ as
 %

 %
 \begin{align}
 	 \!\!\!\!q(\bbx) = {\widetilde q(\bbx) }/{Z} \; , \quad \!\widetilde q(\bbx){:=}\widetilde q(\bbx\given \bby_{1:K}){=}p\left(\bby_{1:K} \given  \bbx  \right) p\left(\bbx\right),
 \end{align}
where $\widetilde q(\bbx)$ integrates to normalizing constant $Z {:=} p\left( \bby_{1:K}\right)$\footnote{Note that $q(\bbx)$ and $\widetilde q(\bbx)$ depend on the data $\{\bby_{1:K}\}_{k \leq K}$, although we drop the dependence to ease notation.}.
In most applications, we only have access to a collection of observations $\bby_{1:K}$ drawn from a static conditional density $p( \bby_{1:K} \given \bbx )$ and a prior for $p(\bbx)$. Therefore, the integral \eqref{eq:template_problem} cannot be evaluated, and hence one must resort to numerical integration such as Monte Carlo methods.
In Monte Carlo, we approximate \eqref{eq:template_problem} by sampling. Hypothetically, we could draw $N$  samples $\bbx(n)\sim  q(\bbx)$ and estimate the expectation in \eqref{eq:template_problem} by the sample average
\begin{equation}\label{eq:template_sample_mean}
\mathbb{E}_{ q(\bbx)}[\phi(\bbx) ] \approx \frac{1}{N}\sum_{n=1}^N \phi(\bbx(n)),
\end{equation}
but typically it is difficult to obtain samples $\bbx(n)$ from posterior $ q(\bbx)$ of the {random variable}. To circumvent this issue, define the \emph{importance density}  $\pi(\bbx )$\footnote{In general, the importance density could be defined over any observation process  $\pi(\bbx \given \{\bby_{k}\} )$, not necessarily associated with time indices $k=1,\dots,K$. We define it this way for simplicity.} with the same (or larger) support as true density $q(\bbx)$, and multiply and divide by $\pi(\bbx )$ inside the integral \eqref{eq:template_problem}, yielding
\begin{equation}\label{eq:importance_distribution_factoring}
\int_{\bbx\in\ccalX} \phi(\bbx) q(\bbx) d\bbx = \int_{\bbx\in\ccalX}\frac{ \phi(\bbx)  q(\bbx)  } {\pi(\bbx)} \pi(\bbx )d\bbx,
\end{equation}
where the ratio ${{q}(\bbx)}/{\pi(\bbx)}$ is the Radon-Nikodym derivative, or unnormalized density, of the target ${q}$ with respect to the proposal $\pi$.  Then, rather than requiring samples from the true posterior, one may sample from the importance density $\bbx(n)\sim \pi(\bbx ),\;n=1,...,N$, and approximate \eqref{eq:template_problem} as
\begin{align}\label{eq:UIS_estimator}
  I_N(\phi) := & \frac{1}{N}\sum_{n=1}^N \frac{ q(\bbx(n)) } {\pi(\bbx(n) )}\phi(\bbx(n)) \nonumber \\
 %
 =&   \frac{1}{NZ}\sum_{n=1}^N g{(\bbx(n))}\phi(\bbx(n)),
\end{align}
where
\begin{align}\label{eq:posterior1}
	g{(\bbx(n))}\equiv \frac{  \widetilde{q}(\bbx(n)) }{\pi(\bbx(n))},
\end{align} are the importance weights.
Note that \eqref{eq:UIS_estimator} is unbiased, i.e., $\mathbb{E}_{\pi(\bbx)}[  I_N(\phi) ] = \mathbb{E}_{ q(\bbx)}[\phi(\bbx) ]$ {and consistent with $N$.} Moreover, its variance depends on the importance density $\pi(\bbx ) $ approximation of the posterior \cite{elvira2019generalized}.

Example priors and measurement models include Gaussian, Student's t, and uniform. Which choice is appropriate depends on the context \cite{sarkka2013bayesian}.
 The normalizing constant $Z$ can be also estimated with IS as
\begin{equation}\label{eq:importance_sampling_denominator}
\hat Z := \frac{1}{N}\sum_{n=1}^N  g{(\bbx(n))}.
\end{equation}
\begin{algorithm}[t]
\caption{ IS: Importance Sampling with streaming samples}
\begin{algorithmic}
\label{alg:importance_sampling}
\REQUIRE Observation model  $p(\bby \given \bbx )$  and prior $p(\bbx)$ or target density $q({\bf x})$ (if known), importance density $\pi(\bbx)$. Set of observations $\{\bby_{1:K}\}_{k=1}^K$
\FOR{$N=0,1,2,\ldots$}

	\STATE Simulate one sample from importance dist. $\bbx(n) \sim \pi(\bbx)$ \vspace{-0mm}
	\STATE Compute weight $g(\bbx(n))$ [cf. \eqref{eq:UIS_estimator}]

	\STATE Compute normalized weights $\overline{w}(n)$ by dividing by estimate for summand \eqref{eq:importance_sampling_denominator}: \vspace{-2mm}
\begin{equation*}
\overline{w}(n)= \frac{g{(\bbx(n))} }{\sum_{u=1}^N g{(\bbx(u))}}\ \ \ \ \ \text{for \ \ all}\ \ \ n.
\end{equation*}\vspace{-2mm}
	\STATE Estimate the expectation with the self-normalized IS as  \vspace{-2mm
	%
\begin{equation*}
I_N(\phi)= \sum_{n=1}^N \overline{w}(n) \phi(\bbx(n))
\end{equation*}\vspace{-2mm}
{	\STATE The posterior density estimate is given by\vspace{-2mm}
$$ {\mu}_N = \sum_{n=1}^N \overline{w}(n) \delta_{\bbx(n)}$$}\vspace{-2mm}
\ENDFOR
\end{algorithmic}
\end{algorithm}
Note that in Eq. \eqref{eq:UIS_estimator}, the unknown $Z$ can be replaced by $\hat Z$ in \ref{eq:importance_sampling_denominator}. Then, the new estimator is given by
\begin{align}\label{eq:SNIS_estimator}
 I_N(\phi) :=&  \frac{1}{N\hat Z}\sum_{n=1}^N g{(\bbx(n))}\phi(\bbx(n)) \\
 %
=&  \frac{1}{\sum_{j=1}^N g{(\bbx(j))}} \!\!\sum_{n=1}^N g{(\bbx(n))}\phi(\bbx(n))\nonumber
\\
=&\sum_{n=1}^N \overline w(n) \phi(\bbx(n)),\nonumber
\end{align}
where the { normalized }$\overline{w}(n)$ weights are defined
\begin{equation}\label{eq:normalized_importance_weight}
\overline{w}(n)\equiv\frac{g{(\bbx(n))} }{\sum_{u=1}^N g{(\bbx(u))}},
\end{equation}
for all $n$. The whole IS procedure is summarized in Algorithm \ref{alg:importance_sampling}. The function $I_N(\phi)$ is the normalized importance sampling (NIS) estimator. It is important to note that the estimator $I_N(\phi)$ can be viewed as integrating a function $\phi$ with respect to density $ {\mu}_N$ defined as
\begin{align}\label{eq:importance_sampling_empirical_measure}
 {\mu}_N({\bf x}):=\sum\limits_{n=1}^{N}\overline{w}(n)\delta_{\bbx(n)},
 %
\end{align}
which is called the particle approximation of $ {q}$.
Here $\delta_{\bbx(n)}$ denotes the Dirac delta measure evaluated at  $\bbx(n)$. This delta expansion is one reason importance sampling is also referred to as a histogram filter, as they quantify weighted counts of samples across the space. Subsequently, we leave the argument (an event, or measurable subset) of the delta $\delta_{\bbx(n)}$ as implicit.

As stated in \cite{first,second,agapiou2017importance}, for consistent estimates of \eqref{eq:template_problem}, we require that $N$, the number of samples $\bbx(n)$ generated from the importance density, and hence the parameterization of the importance density, to go to infinity $N\rightarrow \infty$. Therefore, when we generate an infinite stream of particles, the parameterization of the importance density grows unbounded as it accumulates every particle previously generated.  {We are interested in allowing $N$, the number of particles, to become large (possibly infinite), while the importance density's complexity is moderate, thus overcoming an instance of the curse of dimensionality in Monte Carlo methods.}
In the next section, we propose a method to do so.

\section{Experiments}\label{sec:experiments}

 \subsection{Direct Importance Sampling}\label{direct_IS}

In this section, we conduct a simple numerical experiment to demonstrate the efficacy of the proposed algorithm in terms of balancing model parsimony and statistical consistency. We consider the problem of estimating the expected value of function $\phi(\bbx)$
with the target $q({\bf x})$ and the proposal $\pi({\bf x})$ given by
\begin{align}\label{eq:sample_problem2}
\!\!\phi(x)=2\sin\!\left(\frac{\pi}{(1.5x)}\!\right)\; , \ q({\bf x})\!=\!\frac{1}{\sqrt{2\pi}}\exp\left(\!\!-\frac{(x-1)^2}{2}\right)\; , \ \nonumber\\
\pi({\bf x})\!=\!\frac{1}{\sqrt{4\pi}}\exp\left(\!\!-\frac{(x-1)^2}{4}\right),
\end{align}
to demonstrate that generic Monte Carlo integration allows one to track generic quantities of random variables that are difficult to compute under more typical probabilistic hypotheses. For \eqref{eq:sample_problem2}, since $q({\bf x})$ is known, this is referred to as ``direct importance sampling". We run Algorithm \ref{alg:importance_sampling}, i.e., classic importance sampling, and Algorithm \ref{alg:compressed_online_kernel_importance_sampling} for the aforementioned problem. For Algorithm \ref{alg:compressed_online_kernel_importance_sampling}, we select compression budget $\epsilon=3$, and used a Gaussian kernel with bandwidth $h=0.01$.  We track the normalized integral estimate  \eqref{eq:SNIS_estimator}, absolute integral approximation error, and the number of particles that parameterize the empirical measure (model order).

We first represent the histogram of the particles generated in Fig.~\ref{hist}.  In Fig. \ref{fig:normalized}, we plot the un-normalized integral approximation error for Algorithms \ref{alg:importance_sampling} - \ref{alg:compressed_online_kernel_importance_sampling}, which are close, and the magnitude of the difference depends on the choice of compression budget. Very little error is incurred by kernel mean embedding and memory-reduction. The magnitude of the error relative to the number of particles generated is displayed in Fig. \ref{fig:error}: observe that the error settles on the order of $10^{-3}$. In Fig. \ref{fig:model_order}, we display the number of particles retained by Algorithm \ref{alg:compressed_online_kernel_importance_sampling}, which stabilizes to around $56$, whereas the complexity of the empirical measure given by Algorithm \ref{alg:importance_sampling} grows linearly with sample index $n$, which noticeably grows \emph{unbounded}.

 \subsection{Indirect Importance Sampling}\label{indirect_IS}
 %
 As discussed in Sec. \ref{sec:prob}, in practice we do not know the target distribution $q({\bf x})$ and hence we use Bayes rule as described in \eqref{eq:posterior1} to calculate $q({\bf x}^{(n)})$ at each instant $t$. We consider the observation model $y_t=b+\text{sin}(2\pi x)+\eta_t$ where $\eta_t\sim\mathcal{N}(0,\sigma^2)$. From the equality in \eqref{eq:posterior1}, we need the likelihood and a prior distribution to calculate $q(x^{(n)})$ using Bayes Rule [cf. \eqref{eq:posterior}]. Here we fix the likelihood (measurement model) and prior as
 %

 $\mathbb{P}\left(\{y_k\}_{k\leq K} \given  x^{(n)}  \right)=\frac{1}{(2\pi\sigma_1^2)^{K/2}}\exp\left(-\frac{\|{\bf y}-x^{(n)}\|^2}{2\sigma_1^2}\right)$, $
  \mathbb{P}\left(x^{(n)}\right)=\frac{1}{(2\pi\sigma_2^2)}\exp\left(-\frac{(x^{(n)})^2}{2\sigma_2^2}\right). $

 We set $K=10$, $b=5$, $\sigma=0.1$, $\sigma_1=0.4$, $\sigma_2=1.6$, and compression budget $\epsilon=10^{-3}$. A uniform distribution $\mathcal{U}[3,7]$ is used as the importance distribution. The results are reported in Fig. \ref{fig2}.
 %
 We observe a comparable tradeoff to that which may be gleaned from Section \ref{sec:experiments}: in particular, we are able to obtain complexity reduction by orders of magnitude with extremely little integral estimation error. This suggests the empirical validity of our compression-rule based on un-normalized importance weights operating in tandem with kernel smoothing.
\begin{figure*}[ht!]
	\centering
	\begin{subfigure}[b]{0.32\textwidth}
		\centering
		\includegraphics[width=\textwidth]{first.eps}
		\caption{{\small Location estimate.}}
		\label{fig:one}
	\end{subfigure}
	%
	\begin{subfigure}[b]{0.32\textwidth}
		\centering
		\includegraphics[width=\textwidth]{second.pdf}
		\caption[]%
		{{\small Squared error estimate.}}
		\label{fig:two}
	\end{subfigure}
	%
	\begin{subfigure}[b]{0.32\textwidth}
		\centering
		\includegraphics[width=\textwidth]{third.pdf}
		\caption[]%
		{{\small Model Order. }}
		\label{fig:three}
	\end{subfigure}
	\caption[ The average and standard deviation of critical parameters ]
	{\small Simulation results for Alg. \ref{alg:compressed_online_kernel_importance_sampling} run with Gaussian kernel ($h=0.0001$) and compression budget $\epsilon=0.002$. Observe that the memory-reduction scheme (compressed) nearly preserves statistical consistency, while yielding a finite constant limiting model complexity, whereas the original uncompressed version (uncompressed) attains exact consistency but its memory grows linearly with particle index $t$. }
	\label{fig1}\vspace{-0mm}
\end{figure*}

\subsection{Source Localization}
In this section we present a sensor network localization experiment based on range measurements.The results illustrate the ability to succinctly  represent the unknown distribution of the source signal location, yielding a model that is both parsimonious and nearly consistent.
{Consider the problem of localizing a static target in two-dimensional space $\mathbb{R}^2$ with range measurements from the source collected in a wireless sensor network (WSN). Since the observation model is \emph{nonlinear}, the posterior distribution of the location of the target is intractable, and hence finding the least-squares estimator is not enough. This problem is well-studied in signal processing \cite{ali2009empirical} and robotics \cite{thrun2005probabilistic}.  Let ${\bf x}=[x,  y]^T$ denote the random unknown target location. We assume six sensors with locations $\{\bbh_i\}_{i=1}^6$ at locations $[1, -8]^T$, $[8, 10]^T$, $[-15, -17]^T$, $[-8, 1]^T$, $[10, 0]^T$, and $[0,10]^T$, respectively.  The true location of the target is at $[3.5, 3.5]^T$. The measurement at each sensor $i$ is related to the true target location ${\bf x}$ via the following nonlinear function of range
	%

	%
	$y_{i,j}=-20\log(\|{\bf x}-\bbh_i\|)+\eta_i$
	%

	%
	for $i=1$ to $6$ and $j=1$ to $N$, where $N_i$  is the number of measurements collected by sensor $i$. Here, $\eta_i\sim\mathcal{N}(0,1)$ models the range estimation error.   For the experiment, we consider a Gaussian prior on the target location $\bbx$ with mean $[3.5,  3.5]^T$ and identity covariance matrix. We use  the actual target location as the mean for the Gaussian prior because we are interested in demonstrating that the proposed technique successfully balances particle growth and model bias. In practice, for a general possibly misspecified prior, we can appeal to advanced adaptive algorithms -- for example see \cite{elvira2017improving,bugallo2017adaptive}.}

Fig. \ref{fig1} shows the performance of the proposed algorithm compared against classical (uncompressed) normalized importance sampling. Fig. \ref{fig:one} shows that the final estimated value of the target location for compressed and uncompressed versions of the algorithms are close. We plot the squared error in Fig. \ref{fig:two} and both algorithms converge with close limiting estimates. Further, in Fig. \ref{fig:three} we observe that the model order for the compressed distribution settles to $21$, whereas the classical algorithm requires its number of particles in its importance distribution to grow unbounded. The memory-reduction comes at the cost of very little estimation error (Fig. \ref{fig:one}).

\subsubsection{#1}\vspace{-3\baselineskip}\color{black}\medskip{\noindent \bf \thesubsubsection. #1.}}

\newcommand{\myparagraph}[1]{\needspace{1\baselineskip}\medskip\noindent {\it #1.}}

\newcommand{\myindentedparagraph}[1]{\needspace{1\baselineskip}\medskip \hangindent=11pt \hangafter=0 \noindent{\it #1.}}

\newcommand{\myparagraphtc}[1]{\needspace{1\baselineskip}\medskip\noindent {\it #1.}\addcontentsline{toc}{subsubsection}{\qquad\qquad\quad#1}}