23 citations · 28 across the 10 of their papers we have counts for
12 papers
Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
Gautam Kamath, Mahbod Majid, Ankur Moitra +2
We study learning a discrete distribution under person-level differential privacy in the batched setting. Given users, each contributing i.i.d. samples from an unknown dist…
Color Coding for the Sherrington-Kirkpatrick Model
Alina Harbuzova, Saba Lepsveridze, Mahbod Majid +1
We give a polynomial-time algorithm for approximating the partition function of mean-field mixed -spin models to arbitrarily high accuracy throughout the second-moment regime. T…
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Sergei Kudria, Jason Luo, Mahbod Majid
We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of…
Tight Lower Bounds for State Tomography with Limited Entanglement
Ufuk Keskin, Jason Luo, Mahbod Majid +1
We study state tomography when each measurement acts on at most fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound i…
Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing
Eric Shen, Tony Wu, Mahbod Majid +1
We study the task of learning the structure of a -sparse Gaussian graphical model on variables from a single trajectory of Glauber dynamics. Beyond algorithmic consideration…
Privately Estimating Monotone Statistics in Polynomial Time
Gavin Brown, Ephraim Linder, Mahbod Majid +1
We study efficient differentially private algorithms for estimating monotone statistics, i.e., statistics that are monotone under the addition of new observations. The starting poi…
Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
Sitan Chen, Jingqiu Ding, Mahbod Majid +1
Bayesian methods lie at the heart of modern data science and provide a powerful scaffolding for estimation in data-constrained settings and principled quantification and propagatio…
Sample-Optimal Private Regression in Polynomial Time
Prashanti Anderson, Ainesh Bakshi, Mahbod Majid +1
We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure).…
Sample-Efficient Private Learning of Mixtures of Gaussians
Hassan Ashtiani, Mahbod Majid, Shyam Narayanan
We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly samples suffice to learn a mix…
Private Mean Estimation with Person-Level Differential Privacy
Sushant Agarwal, Gautam Kamath, Mahbod Majid +3
We study person-level differentially private (DP) mean estimation in the case where each person holds multiple samples. DP here requires the usual notion of distributional stabilit…
Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid +1
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to…
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid
We give the first polynomial-time algorithm to estimate the mean of a -variate probability distribution with bounded covariance from independent samples subject t…