TL;DR
This paper determines the exact asymptotic polynomial degree needed to approximate $e^{-x}$ and $e^x$ within error $\delta$ on the interval $[0, B]$ when both the range $B$ and precision $\delta^{-1}$ scale to infinity. Applying these optimal bounds to Batch Gaussian Kernel Density Estimation (KDE), the authors uncover a fine-grained computational phase transition: runtime transitions from near-linear time ($n^{1+o(1)}$) to quadratic hardness ($n^{2-o(1)}$ under SETH) depending on whether the squared diameter $B$ is sublinear, linear, or superlinear in $\log n$.
What Problem Does This Paper Address?
Polynomial approximations of exponential functions are widely used across computer science, including in the Lanczos method for matrix exponentials, spectral graph algorithms (like balanced separators), softmax estimation in machine learning, and kernel methods.
Prior work in classical approximation theory focused primarily on constant intervals ($B = O(1)$). However, modern algorithmic applications typically scale both the domain size $B$ and the target accuracy $\delta^{-1}$ with the input size $n$. Existing bounds on the required polynomial degree $d_{B;\delta}(e^{-x})$ either had sub-optimal logarithmic gaps or relied on derivative-degree inequalities (such as Markov Brothers' inequality) that fail to capture the true behavior when error tolerances $\delta$ become very small.
Methods
Instead of relying on Markov-type derivative bounds, the authors analyze the coefficients of the functions when rescaled to $[-1, 1]$ and expanded into the monic Chebyshev polynomial basis:
- Saddle Point Asymptotics: The expansion coefficients $A_{v, \lambda}$ and $B_{v, \lambda}$ (where $\lambda = B/2$) are expressed in terms of binomial sums and evaluated via saddle-point analysis as both the degree $v$ and scale $\lambda$ grow simultaneously.
- Chebyshev Orthogonality: Using the $L^2$-orthogonality of Chebyshev polynomials, the authors obtain lower bounds on the polynomial approximation error directly from the expansion coefficients, matching truncation upper bounds up to lower-order factors.
- Extremal Chebyshev Properties: For the very large domain regime ($B \ge \delta^{-\Omega(1)}$), where expansion coefficients become too small to yield tight lower bounds, the authors apply the extremal growth properties of Chebyshev polynomials outside the $[-1, 1]$ interval.
- Low-Rank Kernel Approximations: To solve Batch Gaussian KDE, the polynomial approximation of $e^{-z}$ transforms the $n \times n$ Gaussian kernel matrix into an explicit low-rank factorization whose rank is bounded by the number of monomials.
Datasets
Not discussed in the paper. (This is a purely theoretical paper containing mathematical proofs and algorithmic runtime analyses; no empirical datasets or benchmarks were used.)
Key Insights and Ideas
- Phase Transitions in Approximate Degree: The optimal degree exhibits sharp behavioral shifts:
- For $e^{-x}$, when $B = o(\log(\delta^{-1}))$, the degree is dominated by $\frac{\log(\delta^{-1})}{\log(B^{-1}\log(\delta^{-1}))}$ (nearly linear in $\log(\delta^{-1})$).
- When $B = \omega(\log(\delta^{-1}))$, the degree transitions to a square-root dependence: $(1+o(1))\sqrt{B \log(\delta^{-1})}$.
- In the "critical regime" where $B = 2r \log(\delta^{-1})$ for a constant $r > 0$, the degree is linear in $\log(\delta^{-1})$, with a leading constant determined by the unique positive solution to a transcendental equation $G(\nu) = 1 - r^{-1}$, where $G(x) = \sqrt{x^2+1} + x \log(\sqrt{x^2+1}-x)$.
- Direct Impact on Batch Gaussian KDE: In high dimensions ($m = \Theta(\log n)$) with polynomial error $\delta = n^{-\Theta(1)}$, the complexity of Batch Gaussian KDE directly mirrors the approximate degree phase transition:
- If $B = o(\log n)$, low-degree polynomial expansion enables deterministic $n^{1+o(1)}$ time.
- If $B = \omega(\log n)$, the authors show a matching conditional lower bound: running in faster than $n^{2-o(1)}$ time would violate the Strong Exponential Time Hypothesis (SETH).
Key Results
-
Tight Bounds for Exponentials: $$\begin{aligned} 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) \\ d_{B;\delta}(e^{x}) &= \Theta\left(\max\left\{B, \frac{\log(\delta^{-1})}{\log(B^{-1}\log(\delta^{-1}))}\right\}\right) \end{aligned}$$ Exact leading constants are established for almost all parameter regimes.
-
Batch Gaussian KDE Complexity:
- For $B = o(\log n)$ and $\delta = n^{-\Theta(1)}$: First deterministic algorithm running in $n^{1+o(1)}$ time.
- In the critical regime $B = \kappa \log n$ (for small constant $\kappa > 0$): Running time of $n^{1 + O(\log\log \kappa^{-1} / \log \kappa^{-1})}$.
- For $B = \omega(\log n)$: Requires $n^{2-o(1)}$ time assuming SETH.
Limitations and Future Work
- Missing Leading Constant in the Extreme Tail: When $B \ge \delta^{-\Omega(1)}$, the authors establish the tight $\Theta(\sqrt{B \log(\delta^{-1})})$ rate for $e^{-x}$, but only bound the leading constant between $1/2$ and $1$. Pinpointing the exact leading constant in this regime remains an open problem.
- Critical Regime Exponent Profile: When $B = \kappa \log n$, the algorithm achieves running time $n^{1+\varphi(\kappa)}$. While the paper shows $\varphi(\kappa) \to 0$ as $\kappa \to 0$, it remains open whether $\varphi(\kappa)$ transitions continuously from $0$ to $1$ as $\kappa$ increases or exhibits a sudden discontinuous jump.
Summary updated