Private algorithms approximate matrices with private data.
problem Approximate matrices with same spectrum using private data.
method Differential privacy algorithms for unitary orbit optimization.
result Upper and lower bounds on approximation error.
New bounds for private matrix approximation using Gaussian noise and Dyson Brownian Motion.
problem Private approximation of symmetric matrices with Gaussian noise.
method Viewing Gaussian noise as Dyson Brownian Motion to track eigenvalue and eigenvector evolution.
result Improved bounds on Frobenius-distance utility for private matrix approximation.
Efficient private matrix analysis algorithms for recent variants.
problem Private analysis of recent matrix updates.
method Identifying sufficient conditions on positive semidefinite matrices.
result First efficient differentially private algorithms for various matrix analysis tasks.
PACE-GGM uses Gaussian mechanism for private covariance estimation.
problem Private estimation of covariance matrices in high dimensions.
method Data-adaptive selection of entries, Gaussian mechanism, maximum-entropy reconstruction.
result Consistent improvements in estimation error compared to Gaussian mechanism and baselines.
Private ALS method improves matrix completion with tighter rates and better privacy.
problem Differential privacy in matrix completion for user-level privacy.
method Joint differentially private ALS method with tighter sample complexity and privacy trade-offs.
result Achieves nearly optimal sample complexity and best privacy/utility trade-off.
In this paper, we study the problem of precision matrix estimation when the dataset contains sensitive information. In the differential privacy framework, we develop a differentially private ridge estimator by perturbing the sample covariance matrix. Then we develop a differentially private graphical lasso estimator by…
New method stabilizes private LASSO for high-dimensional data with diverse covariate scales.
problem Privacy constraints and heterogeneity in covariate scales degrade LASSO stability and accuracy.
method Gram-based anisotropic objective perturbation to counteract covariate structure.
result Significantly improves convergence and statistical efficiency of private LASSO estimators.
New algorithms for community detection in graphs with privacy constraints.
problem Community recovery in stochastic block models with node-wise privacy.
method Spectral clustering with privacy mechanisms, including privatized PCA, convex optimization, and matrix estimation.
result Developed algorithms that are computable in polynomial-time and achieve consistent community estimation under node differential privacy.
Efficiently estimates Gaussian distributions privately and robustly.
problem Private and robust estimation of Gaussian distributions.
method Efficient algorithms for pure and approximate differential privacy models.
result Optimal sample complexity in both pure and approximate differential privacy settings.
We improve private training accuracy with learning rate schedules and matrix factorizations.
problem Private training with learning rate schedules and correlated noise.
method General upper and lower bounds for learning rate schedules, memory-efficient constructions, and schedule-aware factorizations.
result Schedule-aware factorizations improve accuracy in private training.
Three new oracle-efficient algorithms for private synthetic data release.
problem Constructing private synthetic data that preserves statistical query answers.
method Oracle-efficient algorithms using optimization oracles for differential privacy.
result Better accuracy in large workload and high privacy regime compared to state-of-the-art.
In many signal processing and machine learning applications, datasets containing private information are held at different locations, requiring the development of distributed privacy-preserving algorithms. Tensor and matrix factorizations are key components of many processing pipelines. In the distributed setting, diff…
Efficiently private clustering algorithms with tight approximation ratios.
problem Differentially private clustering of various types.
method Efficient algorithms achieving tight approximation ratios for clustering problems.
result Achieves approximation ratios similar to non-private algorithms with small additive errors.
Novel privatization framework for high-dimensional variable selection with differential privacy.
problem High-dimensional controlled variable selection with rigorous FDR control under differential privacy constraints.
method Gaussian Johnson-Lindenstrauss Transformation for privatizing the knockoff matrix.
result The proposed private variable selection procedure maintains statistical power even under strict privacy budgets.
New method for private linear regression under privacy constraints, achieving optimal rates.
problem Statistical complexity of private linear regression under unknown, ill-conditioned covariates.
method Information-Weighted Regression method
result Optimal convergence rates for both central and local privacy models.
AdOBEst-LDP improves privacy-preserving frequency estimation for categorical data.
problem Estimating categorical distributions online while preserving privacy.
method AdOBEst-LDP uses adaptive randomized response mechanism to enhance future data utility.
result AdOBEst-LDP selects optimal subset for LDP mechanism with high probability.
Paper develops DP methods for low-rank matrix estimation with near-optimal performance.
problem Estimating a low-rank matrix under differential privacy constraints.
method Introduced computationally efficient DP-initialization and Riemannian optimization-based DP-RGrad algorithm.
result DP-RGrad achieves near-optimal convergence rate under weak differential privacy constraints.
Lower bounds on private estimation of Gaussian covariance matrices.
problem Private estimation of Gaussian covariance matrices under various parameter regimes.
method Stein-Haff identity and fingerprinting lemma extensions.
result Lower bounds match existing upper bounds in the widest known parameters.
JME continually estimates data moments privately and accurately.
problem Private and accurate continual estimation of data moments.
method Uses matrix mechanism and joint sensitivity analysis.
result Improves accuracy in estimating mean and covariance with reduced noise.
We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension~d requires Ω(log∗(d)) examples. As a corollary it follows that the class of thresholds over N can not be learned in a private manner; this resolves open qu…
Improves zeroth-order optimization for private machine learning with public data.
problem High computation and memory cost of first-order DP methods.
method PAZO (Public Data Assisted Zeroth-order Optimization) framework.
result Achieves superior privacy/utility tradeoffs across tasks.
We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization~[Blum et al. 2008] under pure ε-differential privacy [Dwork et al. TCC 2006] and approximate (ε,δ)-differential privacy [Dwork et al. Eurocrypt 2006]. We show that the sample complexity of these tasks under approxima…
Private sketches protect linear regression data privacy.
problem Protecting sensitive information in linear regression.
method Release private sketches of datasets, compute approximate solutions.
result Private sketches maintain good approximation guarantees to the original problem.
New algorithm estimates Gaussian means and covariances efficiently and privately.
problem Estimating Gaussian parameters privately and efficiently.
method Differentially private preconditioner to transform arbitrary Gaussian samples.
result First polynomial-time, sample-efficient estimator for arbitrary Gaussian distributions.
Privacy is a major issue in learning from distributed data. Recently the cryptographic literature has provided several tools for this task. However, these tools either reduce the quality/accuracy of the learning algorithm---e.g., by adding noise---or they incur a high performance penalty and/or involve trusting externa…
Efficiently estimates private least squares with linear error growth.
problem Private estimation of ordinary least squares with bounded residuals and leverage.
method Scaled noise added to a stable nonprivate estimator of the regression vector.
result Near-optimal accuracy guarantee with linear error growth in dimension.
Differential privacy is a cryptographically-motivated definition of privacy which has gained significant attention over the past few years. Differentially private solutions enforce privacy by adding random noise to a function computed over the data, and the challenge in designing such algorithms is to control the added…
We propose a new input perturbation mechanism for publishing a covariance matrix to achieve (ε,0)-differential privacy. Our mechanism uses a Wishart distribution to generate matrix noise. In particular, We apply this mechanism to principal component analysis. Our mechanism is able to keep the positive semi-definitene…
Study on InstaHide's security, linking to phase retrieval problem.
problem Security of InstaHide scheme for private dataset sharing.
method Design of a provable algorithm for private vector recovery.
result Private vectors can be recovered using synthetic vectors and public vectors.
Enhances DP linear regression using public data moments.
problem Limited utility of traditional DP methods in linear regression.
method Transform private data using public second-moment matrix for a better OLSE.
result Improved accuracy and robustness of OLSE in DP linear regression.
We present a private learner for halfspaces over an arbitrary finite domain X⊂Rd with sample complexity mathrmpoly(d,2log∗∣X∣). The building block for this learner is a differentially private algorithm for locating an approximate center point of m>poly(d,2log∗∣X∣) points -- a…
Paper optimizes private PCA for covariance estimation in statistics.
problem Private estimation of covariance matrices and principal components.
method Developed differentially private estimators for spiked covariance model.
result Established minimax rates of convergence for principal components and covariance matrix estimation.
New method for privacy amplification without sampling for matrix factorization.
problem Privacy amplification for differentially private model training with matrix factorization.
method Sampling-free bounds based on Rényi divergence and conditional composition.
result Stronger privacy guarantees for small ε, applicable to various matrices.
Simple DP algorithms find approximate solutions for nonconvex ERM.
problem Finding approximate solutions to nonconvex ERM problems with privacy.
method Differential privacy, descent directions, line search, mini-batching, two-phase strategy.
result Effective algorithms for nonconvex ERM with privacy guarantees.
DP-SEP privatizes EP by refining a single factor per data point.
problem Private inference of complex models with limited memory.
method Stochastic Expectation Propagation with differential privacy.
result DP-SEP provides better posterior estimates with guaranteed privacy.
We extend Kyle's model to include stochastic liquidity and multiple assets.
problem Modeling informed trading with stochastic liquidity and multiple assets.
method Developed a variational formulation and derived a matrix-valued martingale depth process.
result A linear-Gaussian equilibrium with stochastic matrix-valued price impact.
Paper proposes no-regret algorithms for private GP bandit optimization.
problem Private Gaussian process bandit optimization.
method Combines uniform kernel approximator with random perturbations for differentially private GP bandit algorithms.
result Provable no-regret algorithms for stationary kernel functions in two DP settings.
New lower bounds for private covariance estimation of Gaussian distributions are proven.
problem Proving tight lower bounds for private estimation tasks under differential privacy.
method Generalized fingerprinting method for exponential families and private Assouad method.
result Tight lower bounds for private covariance estimation in Frobenius and spectral norms.
Private classification and online prediction are shown to be equivalent.
problem Learning with differential privacy and online prediction equivalence.
method Introducing global stability and proving equivalence between online learnability and private PAC learnability.
result Every concept class with finite Littlestone dimension can be learned by a differentially-private algorithm.
A continuing challenge for machine learning is providing methods to perform computation on data while ensuring the data remains private. In this paper we build on the provable privacy guarantees of differential privacy which has been combined with Gaussian processes through the previously published \emph{cloaking metho…
Improved ADMM for convex distributed learning with differential privacy.
problem Privacy concerns in distributed learning with sensitive data.
method Approximate multi-step ADMM with calibrated noise.
result Higher utility and error bounds asymptotic to state-of-the-art.
We present a provably optimal differentially private algorithm for the stochastic multi-arm bandit problem, as opposed to the private analogue of the UCB-algorithm [Mishra and Thakurta, 2015; Tossou and Dimitrakakis, 2016] which doesn't meet the recently discovered lower-bound of Ω(εKlog(T)) [Shar…
Privacy concern has been increasingly important in many machine learning (ML) problems. We study empirical risk minimization (ERM) problems under secure multi-party computation (MPC) frameworks. Main technical tools for MPC have been developed based on cryptography. One of limitations in current cryptographically priva…
We propose a privacy-enhanced matrix factorization recommender that exploits the fact that users can often be grouped together by interest. This allows a form of "hiding in the crowd" privacy. We introduce a novel matrix factorization approach suited to making recommendations in a shared group (or nym) setting and the …
Optimizes private statistics with noisy methods.
problem Private inference in statistical models.
method Noisy optimization for M-estimators and confidence regions.
result Private estimators converge to non-private ones with high probability.
PMT uses public data moments to make DP feasible for unbounded data.
problem Applying differential privacy to unbounded data distributions.
method Public-moment-guided Truncation (PMT) using second-moments from public data.
result PMT improves the accuracy and stability of DP models.
A new scheme for private computation splits client data into shares for server operations.
problem Private computation between client and server without revealing data.
method Stochastic scheme splitting client data into privatized shares.
result Server performs operations on privatized shares without learning raw data.
Paper introduces data-dependent SSP for private linear and logistic regression.
problem Private linear and logistic regression with better performance.
method Data-dependent sufficient statistic perturbation (SSP) for linear and logistic regression.
result Data-dependent SSP outperforms state-of-the-art methods for linear and logistic regression.