arXiv Machine Learning

Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation

arXiv:2609. 27860v1 Announce Type: new Abstract: A pointwise-unbiased one-bit compressor reconstructs every real input in expectation while transmitting one bit.

arXiv AI
Jun 2

Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation

arXiv:2606. 00703v1 Announce Type: cross Abstract: Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible.

By Munsik Kim
arXiv Machine Learning
Sep 25

An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension

arXiv:2609. 29696v1 Announce Type: new Abstract: We construct, for every function class $\mathcal{F}\subseteq[0,1]^{\mathcal{X}}$ and every accuracy $0<\alpha\le 1$, an agnostic sample compression scheme for the empirical squared loss: for every finite sample $S\in(\mathcal{X}\times[0,1])^m$ with arbitrary (noisy) labels, the scheme stores at most $O(\mathrm{fat}(\mathcal{F},c'\alpha)\cdot\log^3(2/\alpha))$ original labeled examples and auxiliary bits, independent of the sample size $m$, and reconstructs a function $\hat f$ with $L_2(\hat f,S)\le\inf_{f\in\mathcal{F}}L_2(f,S)+\alpha$.

By Guangjian Zhang
arXiv Machine Learning
Sep 25

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.

By Aleksandr Storozhenko
arXiv Machine Learning
Jul 14

Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization

arXiv:2607. 10618v1 Announce Type: cross Abstract: We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition: $y_i=g(\inner{\ba_i}{\bPhi\bw^\ast+\bPsi\bz^\ast})+e_i$, $i=1,\dots,m$, with $m\ll n$, incoherent orthonormal bases $\bPhi,\bPsi$, a scalar link $g$, and noise $e_i$ that may be heavy-tailed or contaminated.

By Raziyeh Takbiri
arXiv Machine Learning
Oct 22

Near Minimax Rate for Quantile Distributional Reinforcement Learning

The paper investigates quantile distributional policy evaluation by approximating the return distribution under a policy with a quantile Bellman fixed point. It constructs an estimator from an empirical Markov decision process and derives non‑asymptotic error bounds in Wasserstein distances, achieving root‑n rates that are independent of the quantile resolution for a wide range of Wasserstein orders. The authors also characterize the exact local asymptotic minimax risk and show that their estimator attains this optimal rate, while examining how the risk depends on resolution in simple state‑space examples.

By Zijie Cheng, Zhihua Zhang
arXiv AI
Jun 8

A Temporal Spatial Minimax Rate for Smoothly-Varying Distributions in Wasserstein Space

arXiv:2606. 07325v1 Announce Type: cross Abstract: We study the minimax rate of estimating a future value $\mu_{t_n+h}$ of a curve $t\mapsto\mu_t$ in the $2$-Wasserstein space $\mathcal{P}_2(\mathbb{R}^d)$ from finitely many noisy snapshots of its past, under an adiabatic bound $\|\nabla_t^k v\|\le\varepsilon$ on the $k$-th covariant derivative of the velocity field.

By Munsik Kim
arXiv Machine Learning
Oct 28

Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

The paper presents a Gaussian approximation for the privacy loss distribution in differentially private stochastic gradient descent (DP‑SGD) when subsampling is used. It shows that, after truncating rare large losses, the privacy loss behaves like a Gaussian with the same mean and variance, up to a small shift that grows only logarithmically with the error tolerance. This leads to tighter variance‑based bounds for subsampled mechanisms, improving upon previous Renyi‑divergence analyses and explaining the effectiveness of the connect‑the‑dots method for random allocation sampling.

By Vitaly Feldman, Moshe Shenfeld