arXiv Machine Learning

On the SoS Certifiability of Log-Concave Distributions

arXiv:2609. 30105v1 Announce Type: new Abstract: For an arbitrary isotropic log-concave distribution $P$ on $\mathbb{R}^d$, we prove that the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares for every even $m\ge2$, where $C>0$ is a universal constant.

Hugging Face Trending Papers
Sep 24

On the SoS Certifiability of Log-Concave Distributions

For an arbitrary isotropic log-concave distribution $P$ on $\mathbb{R}^d$, we prove that the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares for every even $m\ge2$, where $C>0$ is a universal constant. This removes the dependence on the Poincaré constant in the theorem of Kothari and Steinhardt (arXiv:1711.

arXiv Machine Learning
Nov 2

Differentially Private Synthetic Data from Sliced Chebyshev Moments

The paper introduces SPLICE, a differentially private synthetic data algorithm that uses noisy sliced Chebyshev polynomial moments to fit a distribution. SPLICE achieves a Sliced Wasserstein-1 distance of ∼O(1/√n) from the target distribution, a bound that does not depend on the data dimension. The authors also prove a new moment‑matching result and provide a practical implementation that outperforms existing DP synthetic data methods on a large benchmark.

By Lucas Rosenblatt, R. Teal Witter, Christopher Musco
arXiv Machine Learning
Oct 12

Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions

The paper investigates how well two-stage structured Hadamard rotations approximate uniform random rotations in high-dimensional spaces. It establishes nonasymptotic upper bounds of order √{log d/d} for one-dimensional marginals, while showing a persistent Wasserstein-1 discrepancy for the full vector that does not vanish as dimension grows. These results highlight a separation between marginal and joint approximation quality, though they do not directly translate into algorithmic performance guarantees.

By Tomer Zilca, Gal Mendelson