Antonio Álvarez-López, Jingpu Cheng, Liyan Zhang, Qianxiao Li
Motivated by the expressive power of neural ordinary differential equations in flow-based generative modeling, we study the approximation of probability measures by pushforwards generated by parameterized families of Lipschitz vector fields. For Wasserstein distances, we establish a quantitative relationship between finite-sample point interpolation and distributional approximation, and derive universality criteria based on $L^p$-approximation of transport maps. In particular, affine-invariant families containing a non-affine vector field are universal from compactly supported absolutely continuous base measures. For total variation, we show that coordinate-wise dynamics are insufficient in dimensions $d\geq 2$ and establish sufficient conditions based on one-dimensional Sobolev approximation and shear-type mixing. We further examine the role of point interpolation, establishing when different regimes relate to one another and when approximate interpolation can be made exact.
Yan Zhang, Jiong Tuo, Meng Ding, Yuheng Ma, Di Wang
Sparse linear regression is a fundamental problem in high-dimensional statistics, and its private counterparts leave a large gap between the central and the local model of differential privacy. Shuffled differential privacy (SDP) sits between the two, offering accuracy closer to the central model without the trust requirement of a central curator. This paper studies sparse linear regression under both non-interactive and interactive SDP protocols. In the non-interactive setting, any non-interactive $(ε,δ)$-SDP protocol is shown to incur an $\ell_2$-norm estimation error of $Ω( \frac{\sqrt{dk}}{nε} )$ with dimension $d$, sparsity $k$, and $n$ users, revealing an inherent dimensionality barrier. In addition, a non-interactive algorithm is proposed that achieves an $\ell_2$-norm upper bound of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{n}} + \frac{d\sqrt{k}}{nε})$. To overcome this barrier, we turn to the interactive user-level setting, where each user holds $m$ samples. A two-round interactive algorithm is developed that first recovers the support through a heavy hitter step and then estimates the parameter, achieving an error of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{nm}} + \frac{k}{n\sqrt{m}ε} )$ with no polynomial dependence on $d$. Furthermore, by extending the score attack framework to user-level data, a new lower bound $Ω( \sqrt{\frac{k\log(d/k)}{nm}} + \frac{k\log(d/k)}{n\sqrt{m}ε} )$ is established for any user-level $(ε,δ)$-DP, showing that the proposed algorithm is near-optimal with only a gap of the factor $\log(d/k)$.