Non-uniform packings

Lee-Ad Gottlieb, Aryeh Kontorovich

Abstract

Traditional packing numbers quantify the maximum number of non-overlapping balls of a fixed radius that can fit within a metric space. This paper generalizes this concept to non-uniform packings, where each ball may have a distinct radius. We demonstrate that the cardinality of such a set is upper-bounded by a formula dependent on the average radius of the balls, effectively extending classical results to heterogeneous contexts.

Introduction

In metric geometry and machine learning theory, packing and covering numbers are essential tools for characterizing the complexity of a space. A set is typically defined as $r$-separated if every pair of points is at least distance $r$ apart. The maximum size of such a set, the packing number, provides a discrete measure of the space's "volume" or capacity.

However, many real-world systems exhibit multi-scale characteristics where a single, uniform radius $r$ is insufficient. For instance, in a sensor network, different nodes may have varying ranges of exclusion or precision. This paper addresses the "non-uniform" packing problem by defining $R$-separation, where each point $a$ in a set $A$ has its own specific minimum distance $R(a)$ to its neighbors. The authors seek to determine if a general bound exists that accounts for these varying requirements without losing the elegance of classical theory.

Methodology

The authors employ two primary mathematical strategies to derive bounds for non-uniform packings, catering to different types of metric spaces.

Volumetric Analysis in Normed Spaces

In $d$-dimensional normed spaces, such as Euclidean space, the authors utilize Lebesgue measures. By treating each point $a \in A$ as the center of a ball with radius $R(a)/2$, they establish that these balls are necessarily disjoint. The total volume occupied by these balls cannot exceed the volume of the slightly expanded container set.

The transition from a sum of individual volumes (which depend on $R(a)^d$) to a bound based on the average radius $\bar{r}$ is achieved through Jensen’s Inequality. Because the function $f(x) = x^d$ is convex for $d \ge 1$, the average of the volumes is at least the volume of the average radius. This allows the authors to show that the non-uniform packing density is constrained by the average separation scale.

Minimum Spanning Trees in Doubling Spaces

For general metric spaces that lack a standard notion of volume, the authors turn to graph theory. They relate the sum of the separation radii to the total length of a Minimum Spanning Tree (MST) that connects all points in $A$.

This approach relies on the properties of "doubling spaces." A space is considered doubling if any ball of radius $r$ can be covered by a constant number of balls of radius $r/2$. The logarithm of this constant is the doubling dimension ($\text{ddim}$). By leveraging known bounds on MST lengths in such spaces, the authors derive a general bound that links the combinatorial structure of the set to its geometric separation.

Main Result: The Average Radius Bound

The primary contribution of this work is the formulation of a non-uniform packing bound. For a finite $R$-separated set $A$ in a doubling space $\Omega$, the size of the set $|A|$ is bounded by:

$$|A| \le \left( \frac{5 \cdot \text{diam}(A)}{\bar{r}} \right)^{\min\{\text{ddim}(A), \text{ddim}(\Omega)\}}$$

In this expression:

  • $\text{diam}(A)$ is the diameter of the set (the maximum distance between any two points).
  • $\bar{r}$ is the average separation radius, defined as $\frac{1}{|A|} \sum_{a \in A} R(a)$.
  • $\text{ddim}$ is the doubling dimension, representing the intrinsic dimensionality of the space.

This result is remarkably similar to the classical uniform bound, $|A| \le (2 \cdot \text{diam}/r)^{\text{ddim}}$. The transition from a fixed $r$ to an average $\bar{r}$ suggests that the total capacity of a space is surprisingly resilient to local variations in density, provided the average scale remains constant.

Discussion and Insights

The research highlights a deep connection between geometry and combinatorial optimization. The fact that the MST length—a global property—can be used to bound local packing constraints suggests that $R$-separation imposes a rigid structure on the set.

Furthermore, the reliance on the doubling dimension as the exponent confirms that the "tightest" or most complex part of the space dictates the overall packing limit. Whether considering the dimension of the set itself or the ambient space, the bound adapts to the most restrictive constraint.

Limitations and Future Work

While the theorem provides a robust upper bound, the constant factor of "5" is likely not optimal. In uniform cases, this constant is typically 2; the increase to 5 is a byproduct of the MST-based proof technique. Future research may focus on sharpening this constant to provide tighter estimates.

Additionally, the authors envision applications in machine learning, specifically in deriving generalization bounds for algorithms that process multi-scale data. By replacing uniform complexity measures with these non-uniform counterparts, it may be possible to achieve more precise theoretical guarantees for deep learning models and other high-dimensional estimators. Finally, extending these results to non-doubling spaces remains an open theoretical challenge.

Summary updated

Abstract

Highlights • Prove non-uniform packing numbers. • These hold in both normed and metric spaces. • The classical uniform packing bounds are recovered as special cases. Abstract We generalize the classical notion of packing a set by balls with identical radii to the case where the radii may be different. The largest number of such balls that fit inside the set without overlapping is called its non-uniform packing number. We show that the non-uniform packing number can be upper-bounded in terms of the average radius of the balls, resulting in bounds of the familiar classical form.
BibTeX
@article{gottlieb2022non,
  author = {Lee-Ad Gottlieb and Aryeh Kontorovich},
  title = {{Non-uniform packings}},
  journal = {Inf. Process. Lett.},
  year = {2022},
  doi = {10.1016/j.ipl.2021.106179},
}
Figure