Size sensitive packing number for Hamming cube and its consequences

Kunal Dutta, Arijit GhosharXiv 2014 · OpenReview

TL;DR

This paper introduces a refined "size-sensitive" version of a fundamental packing lemma for set systems, improving upon existing bounds. This advancement leads to tighter discrepancy bounds for specific types of set systems, which in turn yields better approximations and sampling guarantees for machine learning and related fields.

What Problem Does This Paper Address?

The paper tackles a problem in combinatorial discrepancy theory, specifically concerning set systems with bounded "primal shatter dimension." This dimension is a measure of how complex a set system is, related to its VC dimension but often more applicable to geometric settings. Haussler's packing lemma provides an upper bound on the size of a "packing" (a set of subsets with a minimum separation) within such systems. However, this bound has limitations, particularly when considering the "size-sensitive" properties of the set system, a concept recently introduced by Ezra. Ezra's work showed that existing bounds were not optimal due to certain polylogarithmic factors. This paper aims to remove these factors and provide a more precise, size-sensitive packing bound, which then allows for improved discrepancy bounds and consequently, better approximation and sampling algorithms.

Methods

The core of the paper is a new "size-sensitive packing lemma" (Theorem 3). The authors build upon Haussler's original proof, which is described as a "magician's trick" and involves a probabilistic argument. They adapt this proof to incorporate the size-sensitive shattering constants introduced by Ezra. This involves a careful refinement of the decomposition and analysis of set systems.

Following this, the paper leverages this new packing lemma to derive improved "size-sensitive discrepancy bounds" (Theorem 6). This is achieved by combining the new packing lemma with Ezra's framework, which uses a chaining decomposition and the Lovett-Meka algorithm for partial coloring. The discrepancy of a set system measures how evenly elements can be colored such that no subset is too imbalanced.

Finally, these improved discrepancy bounds are used to obtain better bounds for "relative $(\varepsilon, \delta)$-approximations" and $(\nu, \alpha)$-samples (Theorem 7). This is done by employing a standard "halving technique" where the set system is repeatedly partitioned and colored.

Datasets

Not discussed in the paper. The paper deals with theoretical set systems and their properties, not empirical datasets.

Key Insights and Ideas

  • Removing Polylogarithmic Factors: The paper successfully removes "extra polylog factors" from previous size-sensitive discrepancy bounds, answering a specific question posed by Ezra. This suggests a more fundamental understanding of the underlying combinatorial structures.
  • Size-Sensitive Packing is Key: The core contribution is a size-sensitive packing lemma that is more precise than previous versions. This improved lemma is the foundation for all subsequent results.
  • Connecting Packing to Discrepancy: The paper demonstrates a strong connection between packing numbers and discrepancy bounds. By improving the packing bound, they directly improve the discrepancy bounds.
  • Implications for Approximation and Sampling: The improved discrepancy bounds have direct implications for the efficiency of algorithms that rely on these concepts, such as relative $(\varepsilon, \delta)$-approximations and $(\nu, \alpha)$-sampling, which are crucial in machine learning and computational geometry.
  • Generalization of Existing Results: The work extends and refines existing results by Matoušek and Ezra, providing tighter bounds for a broader class of set systems.

Key Results

  • Theorem 3 (Size-Sensitive Packing Lemma): Provides a new upper bound on the size of a $\delta$-separated set system with bounded primal shatter dimension and size-sensitive shattering constants $d_1$ and $d_2$. The bound is of the form $M \le c^* (\frac{n}{l})^{\frac{d_1}{d_2}} (\frac{1}{\delta})^{\frac{d_1}{d_2}}$, where $c^*$ is a constant independent of $n, l, \delta$. This bound is claimed to be optimal up to constants.
  • Theorem 6 (Improved Discrepancy Bound): Derives a new discrepancy bound for set systems with bounded primal shatter dimension and size-sensitive shattering constants $d_1, d_2$. The bound is significantly improved, removing polylogarithmic factors present in prior work. For $d_1 > 1$, it's $O(|S|^{d_2/(2d)} n^{(d_1-1)/(2d)} \sqrt{\log f})$, and for $d_1 = 1$, it's $O(|S|^{d_2/(2d)} \log n \sqrt{\log f})$, where $f$ depends on $|S|$ and $n$.
  • Theorem 7 (Improved Approximation/Sampling Bounds): Provides improved bounds for the size of relative $(\varepsilon, \delta)$-approximations and $(\nu, \alpha)$-samples. For $d_1 > 1$, the size is $O(\frac{\log \log n}{\nu^{\frac{d+1}{2d}} \alpha^{\frac{d+1}{2d}}})$. For $d_1 = 1$, it's $max \{O(\log n), O(\frac{\log n \log \log n}{\nu^{\frac{d+1}{2d}} \alpha^{\frac{d+1}{2d}}})\}$.

Limitations and Future Work

  • Constant Factors: While the paper aims to remove polylogarithmic factors and achieve optimal bounds "up to constants," the exact values of these constants are not explicitly determined and depend on various parameters.
  • Constructiveness: The paper mentions that some results are constructive (i.e., algorithms exist to find the coloring or sample), but the complexity of these algorithms is not always the primary focus.
  • Specific Geometric Settings: The paper notes that their bounds are slightly suboptimal for specific cases like points and halfspaces in the plane, suggesting that further specialization might yield even tighter results.
  • Future Work: The paper implicitly suggests future work in exploring the exact constants and potentially applying these improved bounds to other related problems in learning theory and computational geometry. The introduction of size-sensitive shattering constants and their impact on packing and discrepancy is a fertile ground for further research.

Summary updated

Abstract

We prove a size-sensitive version of Haussler's Packing lemma~\cite{Haussler92spherepacking} for set-systems with bounded primal shatter dimension, which have an additional {\em size-sensitive property}. This answers a question asked by Ezra~\cite{Ezra-sizesendisc-soda-14}. We also partially address another point raised by Ezra regarding overcounting of sets in her chaining procedure. As a consequence of these improvements, we get an improvement on the size-sensitive discrepancy bounds for set systems with the above property. Improved bounds on the discrepancy for these special set systems also imply an improvement in the sizes of {\em relative $(\varepsilon, \delta)$-approximations} and $(\nu, \alpha)$-samples.
BibTeX
@misc{dutta2014size,
  author = {Kunal Dutta and Arijit Ghosh},
  title = {{Size sensitive packing number for Hamming cube and its consequences}},
  year = {2014},
  eprint = {1412.3922},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.3922},
}
Figure