Spherical Cap $L_2$ Discrepancy -- Blessing of Dimensionality and a Balanced Large-Cap Variant

1. Problem Statement

The paper investigates the information complexity of numerical integration on the $d$-dimensional unit sphere $S^d$. Specifically, it analyzes the spherical cap $L_2$ discrepancy, a metric quantifying how well a finite set of points $P_{N,d}$ approximates the uniform surface measure $\sigma_d$ when tested against indicator functions of spherical caps.

The central problem is to determine how the number of points $N$ required to achieve a target accuracy $\varepsilon$ (the inverse discrepancy, denoted $N^{\text{cap}}(\varepsilon, d)$) scales with the dimension $d$.

• The "Curse of Dimensionality": In many high-dimensional integration problems (e.g., on the unit cube), $N$ grows exponentially with $d$.
• The Phenomenon of Interest: The authors investigate whether the classical spherical cap discrepancy exhibits a "blessing of dimensionality" (where $N$ decreases as $d$ increases) or if this is an artifact of the specific definition used.

2. Methodology and Framework

A. Classical Setting

The authors define the classical spherical cap $L_2$ discrepancy for a set $P_{N,d}$ as:
$$L^{\text{cap}}_2(P_{N,d}) := \left( \int_{-1}^1 \int_{S^d} \left| \frac{1}{N}\sum_{n=1}^N \mathbf{1}_{C(x;t)}(x_n) - \sigma_d(C(x;t)) \right|^2 d\sigma_d(x) dt \right)^{1/2}$$
where $C(x;t)$ is a spherical cap centered at $x$ with height $t$.

They utilize Stolarsky's Invariance Principle, which connects the discrepancy to the worst-case integration error in a Reproducing Kernel Hilbert Space (RKHS) $H^{(d+1)/2}(S^d)$ with the kernel:
$$K_{1,d}(x, y) = 1 - C_d \|x - y\|$$
where $C_d \sim \frac{1}{\sqrt{2\pi d}}$ as $d \to \infty$.

B. The "Large-Cap" Variant

To address the potential triviality of the classical definition in high dimensions, the authors introduce a modified discrepancy that restricts the integration over cap heights to a scaled interval $[-\alpha_d, \alpha_d]$. This effectively ignores very small caps (which dominate the measure in high dimensions) and focuses on "large" caps close to hemispheres.
The modified kernel is defined as:
$$K_{\alpha_d, d}(x, y) = 1 - \frac{C_d}{\alpha_d} \|x - y\|$$
The parameter $\alpha_d \in [0, 1]$ controls the size of the caps considered.

C. Analytical Tools

• Asymptotic Analysis: Extensive use of Gamma function properties and asymptotic expansions to estimate constants $C_d$ and distance integrals $I_d$ as $d \to \infty$.
• Concentration of Measure: Leveraging the fact that for fixed $t \in (0,1)$, the measure of a spherical cap $\sigma_d(C(x;t))$ decays exponentially as $d$ increases, concentrating mass near the equator ($t=0$).
• Randomized Lower/Upper Bounds: Using probabilistic arguments (random i.i.d. points) to establish upper bounds on the inverse discrepancy and deterministic geometric arguments for lower bounds.

3. Key Contributions and Results

Contribution 1: The "Blessing of Dimensionality" in the Classical Case

The authors prove that for the classical spherical cap $L_2$ discrepancy ($\alpha_d = 1$), the information complexity decreases as the dimension $d$ increases.

• Result: $N^{\text{cap}}(\varepsilon, d) \leq \left\lceil \frac{1}{\varepsilon^2} \frac{C_d I_d}{1 - C_d I_d} \right\rceil$.
• Asymptotic Behavior: Since $C_d I_d \sim \frac{1}{\sqrt{\pi d}}$, the required number of points $N$ scales roughly as $O(1/\sqrt{d})$.
• Explanation: As $d \to \infty$, the kernel $K_{1,d}(x,y) \to 1$. The associated function space converges to the space of constant functions. Since constant functions can be integrated exactly with a single point, the problem becomes trivially easy in high dimensions. This is described as a "blessing of dimensionality," contrasting sharply with the curse of dimensionality seen in unit cube integration.

Contribution 2: A Balanced Variant with Stabilized Difficulty

The authors demonstrate that the "blessing" is not a fundamental property of spherical integration but an artifact of the classical discrepancy definition. By choosing a specific scaling for $\alpha_d$, they construct a variant where the problem difficulty does not decrease with dimension.

• Key Choice: Setting $\alpha_d = \sqrt{2} C_d$.
• Resulting Kernel:
  $$K_{\sqrt{2}C_d, d}(x, y) = 1 - \frac{1}{\sqrt{2}} \|x - y\|$$
  Crucially, the coefficient $1/\sqrt{2}$ is independent of dimension.
• Complexity: For this variant, the inverse discrepancy $N^{\text{cap}, \alpha_d}(\varepsilon, d)$ grows polynomially with $d$ (specifically, between $\sqrt{d}$ and $d$).
• Significance: This variant avoids the "blessing" and provides a polynomially tractable problem that remains challenging as dimensions increase, offering a more robust metric for high-dimensional point distributions.

Contribution 3: General Tractability Analysis

The paper establishes a general framework for the inverse discrepancy $N^{\text{cap}, \alpha_d}(\varepsilon, d)$ based on a function $g(d)$ related to the initial discrepancy.

• If $g(d) \to 1$: Blessing of dimensionality (Classical case).
• If $g(d) \to 0$ exponentially: Curse of dimensionality.
• If $g(d) \to 0$ polynomially: Polynomial tractability (the proposed "balanced" case).

Contribution 4: Hemisphere Discrepancy Limit

The paper briefly discusses the limit $\alpha_d \to 0$, which corresponds to the hemisphere discrepancy. In this case, the discrepancy is related to the geodesic distance. The authors show that for centrally symmetric point sets, the hemisphere discrepancy can be zero with just $N=2$ points, further illustrating how specific geometric constraints can trivialize the problem.

4. Significance and Implications

1. Re-evaluating High-Dimensional Metrics: The paper warns that the classical spherical cap $L_2$ discrepancy may provide overly optimistic (and misleading) predictions for sample complexity in high-dimensional applications (e.g., directional statistics, machine learning on spheres). The "blessing" arises because the metric effectively ignores the geometric structure of the sphere in high dimensions.
2. Robust Alternatives: The proposed "large-cap" variant with $\alpha_d = \sqrt{2}C_d$ offers a dimension-robust alternative. It maintains a connection to the Sobolev space $H^{(d+1)/2}(S^d)$ but ensures the integration problem does not become trivial as $d$ grows.
3. Theoretical Insight: The work clarifies the relationship between the geometry of spherical caps, the concentration of measure phenomenon, and the spectral properties of the associated reproducing kernels. It highlights that the "blessing of dimensionality" is a structural consequence of the specific kernel choice, not an inherent property of integration on spheres.

Conclusion

The paper successfully identifies a "blessing of dimensionality" in the classical spherical cap $L_2$ discrepancy, proving that the associated numerical integration problem becomes easier as dimensions increase. However, it argues this is a limitation of the metric's definition. By introducing a parameterized "large-cap" variant, the authors provide a modified discrepancy measure that exhibits polynomial tractability, ensuring that the difficulty of the integration problem remains stable and non-trivial in high dimensions. This provides a more reliable tool for assessing point distributions in high-dimensional spherical domains.