Technical Summary: Sharper Bounds for Chebyshev Moment Matching, with Applications

Problem Statement

The paper addresses the fundamental problem of approximately recovering a probability distribution $p$ supported on $[-1, 1]$ given noisy measurements of its moments. While moment matching has been a central tool in statistics and numerical linear algebra for over a century, standard moment matching (using powers $x^i$) is notoriously ill-conditioned. Specifically, to achieve a Wasserstein-1 error of $O(1/k)$, standard moments must be estimated with exponentially small error $O(1/2^k)$, rendering the approach impractical in noisy settings.

Chebyshev moment matching, which utilizes moments of the form $\mathbb{E}[T_j(x)]$ where $T_j$ are Chebyshev polynomials, offers better conditioning. However, prior work established that to achieve $O(1/k)$ Wasserstein error, the first $k$ Chebyshev moments still required estimation errors of roughly $O(1/k)$ uniformly. The authors identify a gap between these theoretical bounds and the performance of alternative methods in specific applications (e.g., differentially private synthetic data), suggesting that the relationship between Chebyshev moment error and distribution recovery error could be significantly sharper.

Methodology

The core of the paper's methodology is a theoretical refinement of the error analysis linking Chebyshev moment discrepancies to Wasserstein distance. The proof relies on two primary components from approximation theory:

1. Constructive Jackson's Theorem: The authors utilize a "damped" truncated Chebyshev series to approximate any Lipschitz function $f$. Unlike standard truncation which incurs a $\log k$ factor in the error bound, the damped series (multiplying coefficients by factors $b_j \in [0, 1]$) achieves an approximation error of $O(1/k)$ without the logarithmic penalty.
2. Global Coefficient Decay Bound: The authors prove a novel, stronger bound on the decay of Chebyshev coefficients for Lipschitz functions. While it is well-known that the $j$-th coefficient $c_j$ of a Lipschitz function satisfies $|c_j| = O(1/j)$ (a "local" bound), the authors prove a "global" bound: $\sum_{j=1}^\infty j^2 c_j^2 = O(1)$. This implies that the coefficients cannot simultaneously saturate the local $O(1/j)$ bound; rather, they must decay faster on average in a weighted $\ell_2$ sense.

By combining these tools via the Kantorovich-Rubinstein duality (which characterizes Wasserstein-1 distance as the supremum of expectations over 1-Lipschitz functions), the authors derive a new bound on the Wasserstein distance between two distributions $p$ and $q$ based on the weighted $\ell_2$ norm of their Chebyshev moment differences.

Key Contributions and Results

1. Theoretical Main Result (Theorem 1)

The paper proves that if the first $k$ Chebyshev moments of distributions $p$ and $q$ satisfy a weighted error bound:
$$\sum_{j=1}^k \frac{1}{j^2} \left( \mathbb{E}_{x \sim p}[T_j(x)] - \mathbb{E}_{x \sim q}[T_j(x)] \right)^2 \le \Gamma^2$$
then the Wasserstein-1 distance is bounded by:
$$W_1(p, q) \le O\left(\frac{1}{k} + \Gamma\right)$$
This is a significant improvement over prior results (e.g., [BKM22]), which required the error for every moment $j \in \{1, \dots, k\}$ to be $O(1/k)$ to guarantee the same Wasserstein bound. The new result allows higher-order moments to have larger errors (scaling with $\sqrt{j}$) while maintaining the same overall recovery accuracy.

2. Application to Differentially Private Synthetic Data

The authors apply their bound to the problem of generating differentially private synthetic data.

• Result: They present an algorithm that, given a dataset of $n$ points, returns a distribution $q$ with expected Wasserstein-1 error $\tilde{O}(1/n)$.
• Significance: This matches the optimal rate (up to logarithmic factors) achieved by the complex "superregular random walk" method of Boedihardjo et al. [BSV24], but is achieved via a simpler "Select, Measure, Project" framework using standard Gaussian noise on moments. This improves upon the previous $\tilde{O}(1/n^{1/3})$ bound for Chebyshev moment matching methods.
• Empirical Validation: Experiments on real-world datasets (e.g., income, housing, health indicators) confirm that the Wasserstein error scales as predicted by the theory.

3. Application to Spectral Density Estimation (SDE)

The paper addresses estimating the spectral density of a symmetric $n \times n$ matrix $A$ using matrix-vector products.

• Result: An algorithm is provided that uses $\tilde{O}(1/\epsilon)$ matrix-vector products to output a distribution $q$ such that $W_1(p, q) \le \epsilon \|A\|_2$.
• Significance: Prior methods required a polynomial dependence on $1/\epsilon$ that was suboptimal for small $n$. The new bound removes this dependency, showing that $\tilde{O}(1/\epsilon)$ products suffice for any $n$. This essentially resolves the complexity of the SDE problem in the matrix-vector query model, matching known lower bounds up to logarithmic factors.

4. Application to Learning Populations of Parameters

The authors analyze the Maximum Likelihood Estimator (MLE) for the "Population of Parameters" problem (estimating a distribution of coin biases from noisy observations).

• Result: By applying their global coefficient decay bound directly to the Bernstein polynomial analysis used in prior work [VKVK19], they extend the "medium sample" regime where the MLE achieves $O(1/\sqrt{t} \log N)$ error. The range of samples $t$ is extended from $O(N^{2/9})$ to $O(N^{1/4})$.
• Significance: This tightens the theoretical understanding of the MLE's performance. The authors note that combining their improvement with a conjecture from [VKVK19] could potentially extend this to $O(N^{1-\epsilon})$, which would be essentially optimal.

5. Extension to Higher Dimensions

The paper extends the main theorem and the global decay bound to distributions in $d > 1$ dimensions.

• Result: They prove a multivariate version of the global Chebyshev coefficient decay bound and the corresponding Wasserstein error bound.
• Application: This yields an algorithm for differentially private synthetic data in $d$ dimensions with expected error $\tilde{O}((1/n)^{1/d})$, matching prior work up to logarithmic factors.

Significance and Claims

The paper claims that the primary contribution is a sharper theoretical bound on the accuracy required for Chebyshev moment matching. By leveraging a global decay property of Chebyshev coefficients for Lipschitz functions, the authors demonstrate that distribution recovery is more robust to noise in higher-order moments than previously understood.

The authors state that this theoretical improvement immediately translates to:

1. Simpler Algorithms: Achieving optimal rates for private synthetic data without complex random walk constructions.
2. Faster Linear Algebra: Accelerating spectral density estimation by reducing the number of required matrix-vector products.
3. Tighter Statistical Analysis: Refining the parameter regimes for optimal estimation in population learning problems.

The paper maintains a modest tone regarding the constants in the bounds, noting that while they prove a specific constant (e.g., 36), numerical evidence suggests these could be improved (e.g., to $2\pi$). Furthermore, the authors acknowledge that while their method improves the dependence on $n$ and $\epsilon$, the fundamental lower bounds for these problems (e.g., $\Omega(1/\epsilon)$ matrix-vector products) remain unchanged, and their results are optimal up to logarithmic factors.