23 citations · 149 across the 33 of their papers we have counts for
5 papers · 1 filter
Optimal Private Median Estimation under Minimal Distributional Assumptions
Christos Tzamos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Ilias Zadik
We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distr…
Group testing and local search: is there a computational-statistical gap?
Fotis Iliopoulos, Ilias Zadik
In this work we study the fundamental limits of approximate recovery in the context of group testing. One of the most well-known, theoretically optimal, and easy to implement testi…
The All-or-Nothing Phenomenon in Sparse Tensor PCA
Jonathan Niles-Weed, Ilias Zadik
We study the statistical problem of estimating a rank-one sparse tensor corrupted by additive Gaussian noise, a model also known as sparse tensor PCA. We show that for Bernoulli an…
Free Energy Wells and Overlap Gap Property in Sparse PCA
Gérard Ben Arous, Alexander S. Wein, Ilias Zadik
We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime, where the inference task is possible yet no polynomial-time algorithm is known to…
Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
Matt Emschwiller, David Gamarnik, Eren C. Kızıldağ +1
In the context of neural network models, overparametrization refers to the phenomena whereby these models appear to generalize well on the unseen data, even though the number of pa…