Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation

Amol Aggarwal, Josh Alman

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

For any real numbers B ≥ 1 and δ ∈ (0,1) and function f: [0,B] → ℝ, let d_{B; δ}(f) ∈ ℤ_{> 0} denote the minimum degree of a polynomial p(x) satisfying sup_{x ∈ [0,B]} |p(x) - f(x)| < δ. In this paper, we provide precise asymptotics for d_{B; δ}(e^{-x}) and d_{B; δ}(e^x) in terms of both B and δ, improving both the previously known upper bounds and lower bounds. In particular, we show d_{B; δ}(e^{-x}) = Θ(max{√{B log(δ^{-1})}, log(δ^{-1})/{log(B^{-1} log(δ^{-1}))}}), and d_{B; δ}(e^{x}) = Θ(max{B, log(δ^{-1})/{log(B^{-1} log(δ^{-1}))}}), and we explicitly determine the leading coefficients in most parameter regimes. Polynomial approximations for e^{-x} and e^x have applications to the design of algorithms for many problems, including in scientific computing, graph algorithms, machine learning, and statistics. 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 Θ(log n) dimensions with error δ = n^{-Θ(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 = Θ(log n) mirroring the corresponding transition in d_{B; δ}(e^{-x}): - When B = o(log n), we give the first algorithm running in time n^{1 + o(1)}. - When B = κ log n for a small constant κ > 0, we give an algorithm running in time n^{1 + O(log log κ^{-1} /log κ^{-1})}. The log log κ^{-1} /log κ^{-1} term in the exponent comes from analyzing the behavior of the leading constant in our computation of d_{B; δ}(e^{-x}). - When B = ω(log n), we show that time n^{2 - o(1)} is necessary assuming SETH.
BibTeX
@inproceedings{aggarwal2022optimal,
  author = {Amol Aggarwal and Josh Alman},
  title = {{Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation}},
  booktitle = {CCC},
  year = {2022},
  url = {https://openreview.net/forum?id=3OK6dnkIdA},
}

Loading related content...

Figure