Abstract
For any real numbers $B \ge 1$ and $\delta \in (0, 1)$ and function $f: [0, B] \rightarrow \mathbb{R}$, let $d_{B; \delta} (f) \in \mathbb{Z}_{> 0}$ denote the minimum degree of a polynomial $p(x)$ satisfying $\sup_{x \in [0, B]} \big| p(x) - f(x) \big| < \delta$. In this paper, we provide precise asymptotics for $d_{B; \delta} (e^{-x})$ and $d_{B; \delta} (e^{x})$ in terms of both $B$ and $\delta$, improving both the previously known upper bounds and lower bounds. In particular, we show
$$d_{B; \delta} (e^{-x}) = \Theta\left( \max \left\{ \sqrt{B \log(\delta^{-1})}, \frac{\log(\delta^{-1}) }{ \log(B^{-1} \log(\delta^{-1}))} \right\}\right), \text{ and}$$
$$d_{B; \delta} (e^{x}) = \Theta\left( \max \left\{ B, \frac{\log(\delta^{-1}) }{ \log(B^{-1} \log(\delta^{-1}))} \right\}\right).$$
Polynomial approximations for $e^{-x}$ and $e^x$ have applications to the design of algorithms for many problems, and our degree bounds show both the power and limitations of these algorithms. We focus in particular on the Batch Gaussian Kernel Density Estimation problem for $n$ sample points in $\Theta(\log n)$ dimensions with error $\delta = n^{-\Theta(1)}$. We show that the running time one can achieve depends on the square of the diameter of the point set, $B$, with a transition at $B = \Theta(\log n)$ mirroring the corresponding transition in $d_{B; \delta} (e^{-x})$. When $B=o(\log n)$, we give the first algorithm running in time $n^{1 + o(1)}$. When $B = \kappa \log n$ for a small constant $\kappa>0$, we give an algorithm running in time $n^{1 + O(\log \log \kappa^{-1} /\log \kappa^{-1})}$. When $B = \omega(\log n)$, we show that time $n^{2 - o(1)}$ is necessary assuming the Strong Exponential Time Hypothesis (SETH).
Introduction
Polynomial approximation is a cornerstone of numerical analysis and algorithm design. By replacing complex transcendental functions with simple polynomials, researchers can significantly accelerate computations across machine learning, physics simulations, and graph theory. A fundamental challenge in this field is determining the minimum degree ($d$) required to approximate a function like $e^{-x}$ or $e^x$ on an interval $[0, B]$ such that the maximum error is bounded by $\delta$.
While this problem is classic, modern applications—specifically Gaussian Kernel Density Estimation (KDE)—require understanding regimes where both the interval $B$ and the precision requirement $1/\delta$ grow as a function of the dataset size $n$. Previous bounds were often loose, missing critical logarithmic factors that determine whether an algorithm is practically viable. This paper provides the first tight mathematical bounds for these degrees and demonstrates their direct impact on algorithmic complexity.
Methodological Framework
To move beyond standard derivative-based lower bounds, which often fail to capture fine-grained behavior over large intervals, this work employs three primary mathematical strategies:
- Chebyshev Expansions: The authors represent exponential functions as series of Chebyshev polynomials. These are the "gold standard" for approximation because they distribute error optimally across an interval, preventing large deviations at the boundaries.
- Saddle Point Analysis: To determine the exact asymptotics of the required degree, the authors perform a sophisticated saddle point analysis on the coefficients of the Chebyshev series. This technique allows for the precise tracking of coefficient decay as the polynomial degree increases.
- Orthogonality for Lower Bounds: By leveraging the orthogonality properties of these polynomials, the authors prove that no polynomial of a lower degree can achieve the target error, establishing the "tightness" of the proposed bounds.
Key Insights: The Phase Transition
A central contribution of this research is the identification of a computational "phase transition" in Gaussian KDE. The complexity of the problem is intrinsically tied to the square of the diameter of the point set, denoted as $B$.
The required degree for approximation does not grow linearly; instead, it exhibits different behaviors depending on the relationship between $B$ and the error $\delta$. The authors identify a "critical regime" where $B \approx \log(1/\delta)$. At this threshold, the leading constant of the approximation degree is governed by a complex transcendental equation, $G(\nu) = 1 - r^{-1}$. This mathematical transition mirrors a shift in the algorithmic difficulty of KDE.
Algorithmic Results
The theoretical bounds on polynomial degrees translate directly into new performance guarantees for Batch Gaussian KDE:
- Near-Linear Time Regime: When the point set is relatively clustered ($B = o(\log n)$), the paper introduces the first deterministic algorithm that runs in $n^{1+o(1)}$ time. This is a significant improvement over previous methods for high-precision KDE.
- The Hardness Barrier: Using the Strong Exponential Time Hypothesis (SETH), the authors prove that when the point set is spread out ($B = \omega(\log n)$), no algorithm can run faster than $n^{2-o(1)}$. This establishes that the transition at $B = \Theta(\log n)$ is not a limitation of current algorithms, but a fundamental limit of computation.
- Bridging Theory and Practice: The "leading constants" derived in the mathematical proofs appear directly in the exponent of the running time for the KDE algorithms, showing that high-precision analysis is essential for understanding real-world algorithmic performance.
Conclusion and Future Work
This work provides a complete characterization of the polynomial degree required to approximate exponentials, resolving long-standing gaps in the literature. By applying these results to Gaussian KDE, the authors have mapped the boundary between problems that are computationally "easy" and those that are inherently "hard."
Future research may extend this high-precision saddle point analysis to other kernels used in machine learning, such as Matérn or rational quadratic kernels. Additionally, while the current work is theoretical, implementing these high-degree polynomials in a numerically stable manner remains an important challenge for practitioners.
Summary updated