Search

Anantharam, Jog and Nair recently unified the Shannon-Stam inequality and the entropic form of the Brascamp-Lieb inequalities under a common inequality. They left open the problems of extremizability and characterization of extremizers. Both questions are resolved in the present paper., Comment: 21 pages. Comments welcome

We establish a general class of entropy inequalities that take the concise form of Gaussian comparisons. The main result unifies many classical and recent results, including the Shannon-Stam inequality, the Brunn-Minkowski inequality, the Zamir-Feder inequality, the Brascamp-Lieb and Barthe inequalities, the Anantharam-Jog-Nair inequality, and others., Comment: 23 pages. Comments welcome

We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = \langle X,w^* \rangle + \epsilon$ (with $X \in \mathbb{R}^d$ and $\epsilon$ independent), in which an $\eta$ fraction of the samples have been adversarially corrupted. We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $\mathbb{E} [XX^\top]$ has bounded condition number and $\epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $\epsilon$ is sub-Gaussian. In both settings, our estimators: (a) Achieve optimal sample complexities and recovery guarantees up to log factors and (b) Run in near linear time ($\tilde{O}(nd / \eta^6)$). Prior to our work, polynomial time algorithms achieving near optimal sample complexities were only known in the setting where $X$ is Gaussian with identity covariance and $\epsilon$ is Gaussian, and no linear time estimators were known for robust linear regression in any setting. Our estimators and their analysis leverage recent developments in the construction of faster algorithms for robust mean estimation to improve runtimes, and refined concentration of measure arguments alongside Gaussian rounding techniques to improve statistical sample complexities.

Under minimal regularity assumptions, we establish a family of information-theoretic Bayesian Cram\'er-Rao bounds, indexed by probability measures that satisfy a logarithmic Sobolev inequality. This family includes as a special case the known Bayesian Cram\'er-Rao bound (or van Trees inequality), and its less widely known entropic improvement due to Efroimovich. For the setting of a log-concave prior, we obtain a Bayesian Cram\'er-Rao bound which holds for any (possibly biased) estimator and, unlike the van Trees inequality, does not depend on the Fisher information of the prior., Comment: 15 pages, no figures. Comments welcome

Under minimal regularity assumptions, we establish a family of information-theoretic Bayesian Cram��r-Rao bounds, indexed by probability measures that satisfy a logarithmic Sobolev inequality. This family includes as a special case the known Bayesian Cram��r-Rao bound (or van Trees inequality), and its less widely known entropic improvement due to Efroimovich. For the setting of a log-concave prior, we obtain a Bayesian Cram��r-Rao bound which holds for any (possibly biased) estimator and, unlike the van Trees inequality, does not depend on the Fisher information of the prior., 15 pages, no figures. Comments welcome