arXiv:2004. 05813v3 Announce Type: replace-cross Abstract: Suppose that we are given independent, identically distributed random samples $x_1,\cdots,x_n$ from a mixture at most $k$ many $d$-dimensional spherical Gaussian distributions $\mu_1,\cdots,\mu_{k_0}$ of identical and known variance $\sigma^2$ in each coordinate, such that the minimum $\ell^2$ distance between two distinct centers $y_l$ and $y_j$ is greater than $2\Delta\sigma \min\{\sqrt{d},\sqrt k\}$, where $\Delta>C_0$, and $C_0$ is a sufficiently large universal constant.
By Somnath Chakraborty, Hariharan Narayanan
arXiv:2411. 12438v2 Announce Type: replace-cross Abstract: We develop a new approach for clustering non-spherical (i.
By Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
arXiv:2610. 12358v1 Announce Type: cross Abstract: We study Gaussian regression under squared population $L_2$ loss in a known $m$-dimensional subspace of degree-at-most-$k$ functions on the $d$-dimensional Boolean cube.
By Thomas Weinberger
In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions $P,Q$ on $[n]$ with $\mathrm{d_{TV}}(P,Q)\geq\varepsilon$, and from a third distribution $D\in\{P,Q\}$, the g...
arXiv:2610. 29798v1 Announce Type: new Abstract: In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions $P,Q$ on $[n]$ with $\mathrm{d_{TV}}(P,Q)\geq\varepsilon$, and from a third distribution $D\in\{P,Q\}$, the goal is to identify whether $D=P$ or $D=Q$.
By Gunjan Kumar, Yash Pote, Jonathan Scarlett
arXiv:2607. 14304v1 Announce Type: cross Abstract: We study sparse random geometric graphs generated by connecting pairs of high-dimensional vectors whose inner product exceeds a threshold.
By Manuel Fernandez V, Yizhe Zhu
arXiv:2401. 10927v3 Announce Type: replace-cross Abstract: In this paper, we consider the problem of partitioning a small data sample of size $n$ drawn from a mixture of $2$ sub-gaussian distributions in $\mathbb{R}^p$.
By Shuheng Zhou
arXiv:2610. 31612v1 Announce Type: new Abstract: We study learning a discrete distribution under person-level differential privacy in the batched setting.
By Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman
arXiv:2610. 01088v1 Announce Type: cross Abstract: The nonparametric maximum likelihood estimator (NPMLE) of a Gaussian location mixture maximizes the likelihood over the infinite-dimensional space of mixing distributions.
By Hansheng Jiang
We study learning a discrete distribution under person-level differential privacy in the batched setting. Given $n$ users, each contributing $m$ i.
arXiv:2604. 14614v2 Announce Type: replace-cross Abstract: We give an algorithm for PAC learning intersections of $k$ halfspaces with a $\rho$ margin to within error $\varepsilon$ that runs in time $\textsf{poly}(k, \varepsilon^{-1}, \rho^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/\rho) \log k})\right)$.
By Shyamal Patel, Santosh Vempala
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