Importance sampling (IS) is a standard Monte Carlo (MC) tool to compute information about random variables such as moments or quantiles with unknown distributions.   IS is 
asymptotically consistent as the number of MC samples, and hence deltas (particles) that parameterize the density estimate, go to infinity. However, retaining infinitely many particles is intractable. We propose a scheme for only keeping a \emph{finite representative subset} of particles and their augmented importance weights that is \emph{nearly consistent}. To do so in {an online manner}, we approximate importance sampling in two ways.   First, we replace the deltas by kernels, yielding kernel density estimates (KDEs).   Second, we sequentially project KDEs onto nearby lower-dimensional subspaces. We characterize the asymptotic bias of this scheme as determined by a compression parameter and kernel bandwidth, which yields a tunable tradeoff between consistency and memory. In experiments,  we observe a favorable tradeoff between memory and accuracy, providing for the first time near-consistent compressions of arbitrary posterior distributions. Importance sampling is a MC method that addresses Bayesian inference in cases where the distribution that relates observations to the hidden state is time-invariant (Tokdar and Kass, 2010). More specifically, based upon independent samples from a proposal distribution, MC methods approximately compute expectations of arbitrary functions of the unknown parameter via weighted samples generated from the proposal. Recently, use of importance distributions to weight updates, e.g., coordinate descent (Allen-Zhu et al., 2016; Csiba et al., 2015) or stochastic gradient descent (Borsos et al., 2018) , have been developed. Doing so yields faster deep network training (Johnson and Guestrin, 2018; Katharopoulos and Fleuret, 2018) by weighting mini-batches (Hanzely and Richtárik, 2018) . Furthermore, in reinforcement learning (RL), an agent chooses actions according to a policy and then updates the policy via rewards observed (Watkins and Dayan, 1992) ; however, this theoretically requires an inordinate amount of random actions to be chosen before reasonable performance is learned (Tsitsiklis, 1994; , an issue known as the exploreexploit tradeoff. To lessen its deleterious effect, exploratory actions may be chosen via an importance distribution (Schaul et al., 2015) or policy updates may be chosen from previous experience known to be safe (Precup et al., 2000) . Contributions. We propose a compression scheme that operates within importance sampling, sequentially deciding which particles are statistically significant for the integral estimation. To do so, we draw connections between proximal methods in optimization (Rockafellar, 1976) and importance distribution updates: we view the empirical measure defined by importance sampling as carrying out a sequence of projections of un-normalized empirical distributions onto subspaces of growing dimension. Then, we augment the subspace selection by replacing it by one that is nearby (according to some metric) but with lower memory. These lower-memory subspaces are selected based on greedy compression with a fixed budget parameter via matching pursuit (Pati et al., 1993) . We combine this idea with kernel smoothing of the empirical measure in order to exploit the fact that compact spaces have finite covering numbers. Consequently, we have characterized the asymptotic bias of this method as a tunable constant depending on the kernel bandwidth parameter and a compression parameter. Experiments demonstrate that this approach yields an effective tradeoff of consistency and memory for MC methods.
We proposed a novel compressed kernelized importance sampling algorithm.