# Sharper Bounds for Chebyshev Moment Matching, with Applications

arXiv: https://arxiv.org/abs/2408.12385 · HTML: https://mlsanity.com/paper/2408.12385/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 104 references that are in the map.
- First posted on arXiv 22 Aug 2024.

## Builds on (most cited first, 30 of 38)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Traditional and Heavy-Tailed Self Regularization in Neural Network Models](https://mlsanity.com/paper/1901.08276/) (2019)
- [AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data](https://mlsanity.com/paper/2201.12677/) (2022)
- [The Emergence of Spectral Universality in Deep Networks](https://mlsanity.com/paper/1802.09979/) (2018)
- [Privacy in Deep Learning: A Survey](https://mlsanity.com/paper/2004.12254/) (2020)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [Differentially Private Synthetic Data: Applied Evaluations and Enhancements](https://mlsanity.com/paper/2011.05537/) (2020)
- [Private Synthetic Data for Multitask Learning and Marginal Queries](https://mlsanity.com/paper/2209.07400/) (2022)
- [The Limits of Differential Privacy (and its Misuse in Data Release and Machine Learning)](https://mlsanity.com/paper/2011.02352/) (2020)
- [Analysis of stochastic Lanczos quadrature for spectrum approximation](https://mlsanity.com/paper/2105.06595/) (2021)
- [Efficient Inverse Maintenance and Faster Algorithms for Linear Programming](https://mlsanity.com/paper/1503.01752/) (2015)
- [Network Density of States](https://mlsanity.com/paper/1905.09758/) (2019)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law](https://mlsanity.com/paper/1804.01221/) (2018)
- [Maximum Likelihood Estimation for Learning Populations of Parameters](https://mlsanity.com/paper/1902.04553/) (2019)
- [Optimal Sketching for Trace Estimation](https://mlsanity.com/paper/2111.00664/) (2021)
- [Algorithmically Effective Differentially Private Synthetic Data](https://mlsanity.com/paper/2302.05552/) (2023)
- [Spectrum Estimation from Samples](https://mlsanity.com/paper/1602.00061/) (2016)
- [The gradient complexity of linear regression](https://mlsanity.com/paper/1911.02212/) (2019)
- [Sublinear Time Spectral Density Estimation](https://mlsanity.com/paper/2104.03461/) (2021)
- [Optimal Eigenvalue Approximation via Sketching](https://mlsanity.com/paper/2304.09281/) (2023)
- [Instance-Optimal Private Density Estimation in the Wasserstein Distance](https://mlsanity.com/paper/2406.19566/) (2024)
- [Querying a Matrix through Matrix-Vector Products](https://mlsanity.com/paper/1906.05736/) (2019)

## Built on by (most cited first, 3 of 3)

- [Fast Spectrum Estimation of Some Kernel Matrices](https://mlsanity.com/paper/2411.00657/) (2024)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [Minimax optimal differentially private synthetic data for smooth queries](https://mlsanity.com/paper/2602.01607/) (2026)

## Abstract (arXiv)

We study the problem of approximately recovering a probability distribution given noisy measurements of its Chebyshev polynomial moments. This problem arises broadly across algorithms, statistics, and machine learning. By leveraging a global decay bound on the coefficients in the Chebyshev expansion of any Lipschitz function, we sharpen prior work, proving that accurate recovery in the Wasserstein distance is possible with more noise than previously known. Our result immediately yields a number of applications: 1) We give a simple "linear query" algorithm for constructing a differentially private synthetic data distribution with Wasserstein-1 error tildeO(1/n) based on a dataset of n points in [-1,1]. This bound is optimal up to log factors, and matches a recent result of Boedihardjo, Strohmer, and Vershynin [Probab. Theory. Rel., 2024], which uses a more complex "superregular random walk" method. 2) We give an tildeO(n2/ε) time algorithm for the linear algebraic problem of estimating the spectral density of an n× n symmetric matrix up to ε error in the Wasserstein distance. Our result accelerates prior methods from Chen et al. [ICML 2021] and Braverman et al. [STOC 2022]. 3) We tighten an analysis of Vinayak, Kong, Valiant, and Kakade [ICML 2019] on the maximum likelihood estimator for the statistical problem of "Learning Populations of Parameters'', extending the parameter regime in which sample optimal results can be obtained. Beyond these main results, we provide an extension of our bound to estimating distributions in d > 1 dimensions. We hope that these bounds will find applications more broadly to problems involving distribution recovery from noisy moment information.