acceptodds
Under review as a conference paper at ICLR 2027

Stronger Coreset Bounds for Kernel Density Estimators via Chaining

Abstract

Kernel density estimation is a fundamental nonparametric method for estimating probability densities, but its computational cost scales with the number of data points. Coresets provide a compact representation of the data while approximately preserving the resulting kernel density estimate. We give improved bounds on the coreset complexity of a broad class of kernels by combining a discrepancy-theoretic approach with a chaining argument. For uniformly bounded data, we give randomized polynomial-time algorithms that construct coresets of size for the Gaussian and Laplacian kernels, improving the best bounds obtainable using previous discrepancy-based techniques. For the Laplacian kernel in constant dimension, we additionally obtain coresets of size We further establish bounds of for the exponential, Hellinger, and Jensen-Shannon kernels, where denotes the kernel bandwidth. Our results show how chaining techniques can sharpen discrepancy-based guarantees for kernel methods and also offer data-aware bounds for coreset complexity.

Primary area:
learning theory
Keywords:
Kernel density estimation, coresets, discrepancy theory, chaining, kernel methods, computational learning theory

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_eCEUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper considers coresets for kernel density estimation. For different kernel functions, the question is how large a coreset is needed to approximate the kernel density estimate within ℓ∞\ell_\infty error ϵ\epsilon. The paper uses the known discrepancy approach, which constructs a coreset by repeatedly finding a low-discrepancy coloring and discarding half the points.For bounded data and fixed bandwidth, this yields Gaussian and Laplacian coresets of size O(dϵlog⁡log⁡(1/ϵ))O(\frac{\sqrt{d}}{\epsilon}\sqrt{\log\log(1/\epsilon)}), improving the previous log⁡(1/ϵ)\sqrt{\log(1/\epsilon)} factor. The paper also obtains bounds for unrestricted data in fixed dimension for other kernels.

Critical strengths

Kernel density estimation is an important problem both from a theoretical and practical perspective and several papers have considers coresets for the problem. It is nice that the paper improves the best known bounds for such coresets for several common kernels.

Critical weaknesses

It was very difficult for me to parse the paper. Theorems and definitions contain very complicated expressions that are explained in very little detail, e.g., I don't know how to think about the integrals of theorem 8 and 10. The core tools like Dudley's theorem and chaining which are highly technical concepts are defined but not explained. There is no technical overview, even though the proofs are highly technical, and many of the ideas needed in the proofs would need to be explained.

Unfortunately, I think that in the era of LLMs this kind of very technical theoretical paper is not of very high value, even though the theoretical results are interesting. If the authors for a different conference writes a paper which better explains what's going on, I would be more open to accepting the paper.

Also, the title of the paper in the pdf is currently "FORMATTING INSTRUCTIONS FOR ICLR 2027 CONFERENCE SUBMISSIONS". Not in itself a big issue, but it does give the idea that the manuscript might have been prepared very quickly perhaps with the help of some busy LLMs. Along the same note, the abstract uses concepts like chaining, which I don't think most readers would understand the meaning of here.

Finally, I believe that it is never introduced what the bandwidth parameter α\alpha is even though it is used several times.

Questions for authors

What is the bandwidth parameter?

What are the lower bounds for the different kernel functions and how close are your upper bounds to matching those lower bounds?

Reviewer_FTiMOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper combines discrepancy-based coloring using the Gram-Schmidt Walk with chaining in the kernel-induced metric to provide a coreset of size O(d log⁡log⁡(1/ε)/ε)O(\sqrt d\,\sqrt{\log\log(1/\varepsilon)}/\varepsilon) for bounded Gaussian and Laplacian data sets, Od(log⁡log⁡(1/ε)/ε)O_d(\sqrt{\log\log(1/\varepsilon)}/\varepsilon) for arbitrary Laplacian data sets in a fixed dimension, and O(dlog⁡(2max⁡{1,α})/ε)O(\sqrt{d\log(2\max\{1,\alpha\})}/\varepsilon) for exponential, Hellinger, and Jensen-Shannon kernels. The main contribution is to improve upon existing bounds in certain regimes.

Critical strengths
  1. The paper treats signed kernel sums as a sub-Gaussian process in the kernel-induced metric and applies multi-scale covering arguments to bound the supremum over queries. This addresses the logarithmic loss from a single fine discretization. The approach provides a reusable method for relating coreset complexity to kernel geometry and dataset structure.
Critical weaknesses
  1. The proof of Theorem 10 does not provide an explanation or justification for the concentration and aggregation parts. In addition, the entropy-integral part that is needed to prove Theorem 18 was left out of equation (8) on page 8. Lastly, the aggregation step at the end of the proof only states how many cells will have a larger contribution than O(1)O(1), but it does not state what the total contribution of all other cells would be. The global discrepancy guarantee has been unproven as stated. Since Corollary 23's fixed-dimensional Laplacian improvement relies on this theorem, this gap may affect one of the main contributions.

  2. The novelty of this work is limited. For example, Tai's previously published work provides a stronger bound for fixed dimensional Gaussian KDE than this paper[1]. Tai (2022) already gives Gaussian KDE coresets of size Od(1/ε)O_d(1/\varepsilon) in fixed dimension, removing the extra log⁡log⁡(1/ε)\sqrt{\log\log(1/\varepsilon)} factor present in this paper’s bound.

  3. This paper does not provide implementation, runtime benchmarks, or experiments. This limits the demonstrated practical impact and restricts the contribution to theoretical results.

For the format: The authors forgot to change the title from the ICLR template and have "FORMATTING..." as the paper title.

[1] Tai, Wai Ming. "Optimal coreset for Gaussian kernel density estimation." arXiv preprint arXiv:2007.08031 (2020).

Questions for authors

The author may explain the weaknesses.

Reviewer_A9RgOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies coreset complexity for kernel density estimation (KDE). It combines discrepancy-based techniques, the Gram–Schmidt walk, and a chaining argument to improve existing coreset size bounds. The authors derive general discrepancy bounds for positive-definite kernels and apply them to Gaussian, Laplacian, exponential, Hellinger, and Jensen–Shannon kernels. The main claimed improvement is the removal or reduction of logarithmic factors in previous bounds, leading to smaller theoretical coresets.

Critical strengths

The use of chaining to control discrepancy over a continuous query space is a meaningful departure from prior single-scale discretization approaches. The proposed framework directly targets the logarithmic factors in existing coreset bounds and addresses a relevant theoretical problem.

Critical weaknesses
  1. The proof of Theorem 10 contains several questionable steps, particularly the covering-number bound in Equation (6), the incorrect inequality direction in Equation (7), and the insufficiently justified treatment of nonadjacent cells. Furthermore, Corollaries 21 and 22 do not adequately justify eliminating the dependence on the bandwidth parameter. These issues directly undermine the main theoretical claims and raise significant concerns about the soundness of the results.
  2. The manuscript contains numerous typographical errors, inconsistent notation, and imprecise mathematical statements.
Questions for authors
  1. Please provide a rigorous justification for the covering-number bound in Equation (6), the inequality in Equation (7), and the treatment of nonadjacent cells in the proof of Theorem 10. These steps are essential to the claimed theoretical guarantees.
  2. How is the dependence on the bandwidth parameter eliminated in Corollaries 21 and 22? Please clarify the assumptions under which these bounds hold.
  3. The manuscript contains numerous typographical errors, inconsistent notation, and imprecise mathematical statements. The authors should carefully revise the presentation and ensure consistency in mathematical definitions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.