A Statistical Perspective on Coreset Density Estimation

• URL: http://arxiv.org/abs/2011.04907v2
• Date: Tue, 8 Dec 2020 21:05:08 GMT
• Title: A Statistical Perspective on Coreset Density Estimation
• Authors: Paxton Turner, Jingbo Liu, Philippe Rigollet
• Abstract summary: Coresets have emerged as a powerful tool to summarize data by selecting a small subset of the original observations. We show that the practical coreset kernel density estimators are near-minimax optimal over a large class of H"older-smooth densities.
• Score: 26.023056426554415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Coresets have emerged as a powerful tool to summarize data by selecting a small subset of the original observations while retaining most of its information. This approach has led to significant computational speedups but the performance of statistical procedures run on coresets is largely unexplored. In this work, we develop a statistical framework to study coresets and focus on the canonical task of nonparameteric density estimation. Our contributions are twofold. First, we establish the minimax rate of estimation achievable by coreset-based estimators. Second, we show that the practical coreset kernel density estimators are near-minimax optimal over a large class of H\"{o}lder-smooth densities.

Related papers

• Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints [69.27190330994635]
  Coreset selection is powerful in reducing computational costs and accelerating data processing for deep learning algorithms. We propose an innovative method, which maintains optimization priority order over the model performance and coreset size. Empirically, extensive experiments confirm its superiority, often yielding better model performance with smaller coreset sizes.
  arXiv  Detail & Related papers  (2023-11-15T03:43:04Z)
• TAKDE: Temporal Adaptive Kernel Density Estimator for Real-Time Dynamic Density Estimation [16.45003200150227]
  We name the temporal adaptive kernel density estimator (TAKDE) TAKDE is theoretically optimal in terms of the worst-case AMISE. We provide numerical experiments using synthetic and real-world datasets, showing that TAKDE outperforms other state-of-the-art dynamic density estimators.
  arXiv  Detail & Related papers  (2022-03-15T23:38:32Z)
• Density Ratio Estimation via Infinitesimal Classification [85.08255198145304]
  We propose DRE-infty, a divide-and-conquer approach to reduce Density ratio estimation (DRE) to a series of easier subproblems. Inspired by Monte Carlo methods, we smoothly interpolate between the two distributions via an infinite continuum of intermediate bridge distributions. We show that our approach performs well on downstream tasks such as mutual information estimation and energy-based modeling on complex, high-dimensional datasets.
  arXiv  Detail & Related papers  (2021-11-22T06:26:29Z)
• Kernel Density Estimation by Stagewise Algorithm with a Simple Dictionary [0.0]
  This paper studies kernel density estimation by stagewise algorithm with a simple dictionary on U-divergence. We randomly split an i.i.d. sample into two disjoint sets, one for constructing the kernels in the dictionary and the other for evaluating the estimator.
  arXiv  Detail & Related papers  (2021-07-27T17:05:06Z)
• Featurized Density Ratio Estimation [82.40706152910292]
  In our work, we propose to leverage an invertible generative model to map the two distributions into a common feature space prior to estimation. This featurization brings the densities closer together in latent space, sidestepping pathological scenarios where the learned density ratios in input space can be arbitrarily inaccurate. At the same time, the invertibility of our feature map guarantees that the ratios computed in feature space are equivalent to those in input space.
  arXiv  Detail & Related papers  (2021-07-05T18:30:26Z)
• The Power of Log-Sum-Exp: Sequential Density Ratio Matrix Estimation for Speed-Accuracy Optimization [0.0]
  We propose a model for multiclass classification of time series to make a prediction as early and as accurate as possible. Our overall architecture for early classification, MSPRT-TANDEM, statistically significantly outperforms baseline models on four datasets.
  arXiv  Detail & Related papers  (2021-05-28T07:21:58Z)
• Nonparametric Density Estimation from Markov Chains [68.8204255655161]
  We introduce a new nonparametric density estimator inspired by Markov Chains, and generalizing the well-known Kernel Density Estor. Our estimator presents several benefits with respect to the usual ones and can be used straightforwardly as a foundation in all density-based algorithms.
  arXiv  Detail & Related papers  (2020-09-08T18:33:42Z)
• Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective [30.963638533636352]
  We propose and analyze a novel algorithm for coreset selection. We provide explicit convergence rate guarantees and present an empirical evaluation on a variety of benchmark datasets.
  arXiv  Detail & Related papers  (2020-07-01T19:34:59Z)
• Coresets via Bilevel Optimization for Continual Learning and Streaming [86.67190358712064]
  We propose a novel coreset construction via cardinality-constrained bilevel optimization. We show how our framework can efficiently generate coresets for deep neural networks, and demonstrate its empirical benefits in continual learning and in streaming settings.
  arXiv  Detail & Related papers  (2020-06-06T14:20:25Z)
• A Spatio-Temporal Kernel Density Estimation Framework for Predictive Crime Hotspot Mapping and Evaluation [1.0896567381206714]
  Existing methods such as the popular kernel density estimation (KDE) do not consider the temporal dimension of crime. A-temporal kernel density estimation (STKDE) method is applied to include the temporal component in predictive hotspot mapping. A new metric the predictive accuracy index (PAI) curve is proposed to evaluate predictive hotspots at multiple areal scales.
  arXiv  Detail & Related papers  (2020-05-30T13:51:05Z)
• On Coresets for Support Vector Machines [61.928187390362176]
  A coreset is a small, representative subset of the original data points. We show that our algorithm can be used to extend the applicability of any off-the-shelf SVM solver to streaming, distributed, and dynamic data settings.
  arXiv  Detail & Related papers  (2020-02-15T23:25:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.