A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
A new method for private query release using Johnson-Lindenstrauss projection.
Study private query release with public data, reducing sample sizes.
Three new oracle-efficient algorithms for private synthetic data release.
We revisit the problem of differentially private release of classification queries. In this problem, the goal is to design an algorithm that can accurately answer a sequence of classification queries based on a private training set while ensuring differential privacy. We formally study this problem in the agnostic PAC …
We consider accurately answering smooth queries while preserving differential privacy. A query is said to be -smooth if it is specified by a function defined on whose partial derivatives up to order are all bounded. We develop an -differentially private mechanism for the class of -smooth queries…
Noisy Max and Sparse Vector are selection algorithms for differential privacy and serve as building blocks for more complex algorithms. In this paper we show that both algorithms can release additional information for free (i.e., at no additional privacy cost). Noisy Max is used to return the approximate maximizer amon…
A new mechanism for differentially private Fréchet mean on SPD matrices.
Paper introduces data-dependent SSP for private linear and logistic regression.
Differentially private data structures for estimating distances between strings.
New algorithm maintains privacy while improving model performance in selective release.
We derive concentration inequalities for differentially private median and mean estimators building on the "Propose, Test, Release" (PTR) mechanism introduced by Dwork and Lei (2009). We introduce a new general version of the PTR mechanism that allows us to derive high probability error bounds for differentially privat…
Framework purifies approximate differential privacy to pure differential privacy.
New algorithm corrects bias in LDP-released data for better analysis.
Lower bounds on query complexity for reconstructing private learner's training data.
Paper addresses private online convex optimization with optimal algorithms in various geometries and high-dimensional bandits.
New method generates private synthetic data with optimal utility for smooth queries.
DiPriMe forests use private medians to create balanced tree splits for privacy-protected data.
We study the sample complexity of private synthetic data generation over an unbounded sized class of statistical queries, and show that any class that is privately proper PAC learnable admits a private synthetic data generator (perhaps non-efficient). Previous work on synthetic data generators focused on the case that …
We study the query complexity of a learner-private sequential learning problem, motivated by the privacy and security concerns due to eavesdropping that arise in practical applications such as pricing and Federated Learning. A learner tries to estimate an unknown scalar value, by sequentially querying an external datab…
Differential privacy provides strong privacy guarantees simultaneously enabling useful insights from sensitive datasets. However, it provides the same level of protection for all elements (individuals and attributes) in the data. There are practical scenarios where some data attributes need more/less protection than ot…
Private sketches protect linear regression data privacy.
Improved algorithm for selecting a hypothesis locally privately with fewer queries.
We formulate a private learning model to study an intrinsic tradeoff between privacy and query complexity in sequential learning. Our model involves a learner who aims to determine a scalar value, , by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes…
New DP bootstrap method for statistical inference with improved privacy and accuracy.
New tool for parallel and private stochastic convex optimization reduces query complexity.
Privacy is enhanced by synthetic data release even with unlimited data.
Transform non-private e-values into differentially private ones.
We study the query complexity of Bayesian Private Learning: a learner wishes to locate a random target within an interval by submitting queries, in the presence of an adversary who observes all of her queries but not the responses. How many queries are necessary and sufficient in order for the learner to accurately est…
For a dataset of label-count pairs, an anonymized histogram is the multiset of counts. Anonymized histograms appear in various potentially sensitive contexts such as password-frequency lists, degree distribution in social networks, and estimation of symmetric properties of discrete distributions. Motivated by these app…
Many commonly used learning algorithms work by iteratively updating an intermediate solution using one or a few data points in each iteration. Analysis of differential privacy for such algorithms often involves ensuring privacy of each step and then reasoning about the cumulative privacy cost of the algorithm. This is …
This paper provides a method for noise-calibrated inference from DP synthetic data.
We introduce a general learning framework for private machine learning based on randomised response. Our assumption is that all actors are potentially adversarial and as such we trust only to release a single noisy version of an individual's datapoint. We discuss a general approach that forms a consistent way to estima…
Sensitive attributes such as race are rarely available to learners in real world settings as their collection is often restricted by laws and regulations. We give a scheme that allows individuals to release their sensitive information privately while still allowing any downstream entity to learn non-discriminatory pred…
We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of…
This work refines grid size selection for non-interactive private -means clustering.
Optimal locally private hypothesis selection with interactive rounds.
New algorithm for personalized healthcare with privacy guarantees.
Optimal private ERM and SCO with subquadratic gradient complexity.
We present differentially private algorithms for the stochastic Multi-Armed Bandit (MAB) problem. This is a problem for applications such as adaptive clinical trials, experiment design, and user-targeted advertising where private information is connected to individual rewards. Our major contribution is to show that the…
The paper analyzes and proposes methods for privately sharing individual privacy losses using per-instance differential privacy.
Study on generating and identifying languages privately, showing privacy imposes costs and creates barriers.
Popular approaches to differential privacy, such as the Laplace and exponential mechanisms, calibrate randomised smoothing through global sensitivity of the target non-private function. Bounding such sensitivity is often a prohibitively complex analytic calculation. As an alternative, we propose a straightforward sampl…
In adaptive data analysis, the user makes a sequence of queries on the data, where at each step the choice of query may depend on the results in previous steps. The releases are often randomized in order to reduce overfitting for such adaptively chosen queries. In this paper, we propose a minimax framework for adaptive…
Two private algorithms estimate Jaccard similarity efficiently.
Study differentially private methods for learning Hawkes processes.
We lay theoretical foundations for new database release mechanisms that allow third-parties to construct consistent estimators of population statistics, while ensuring that the privacy of each individual contributing to the database is protected. The proposed framework rests on two main ideas. First, releasing (an esti…
User releases data to service provider while balancing privacy and utility.
Improved DP KDE with better privacy and efficiency.