Mean estimation in the add-remove model of differential privacy

• URL: http://arxiv.org/abs/2312.06658v2
• Date: Mon, 19 Feb 2024 20:50:16 GMT
• Title: Mean estimation in the add-remove model of differential privacy
• Authors: Alex Kulesza and Ananda Theertha Suresh and Yuyan Wang
• Abstract summary: We study the problem of one-dimensional mean estimation under the add-remove model. We show that our proposed algorithm yields at least a factor of two improvement in mean squared error over algorithms frequently used in practice.
• Score: 20.78625240235862
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differential privacy is often studied under two different models of neighboring datasets: the add-remove model and the swap model. While the swap model is frequently used in the academic literature to simplify analysis, many practical applications rely on the more conservative add-remove model, where obtaining tight results can be difficult. Here, we study the problem of one-dimensional mean estimation under the add-remove model. We propose a new algorithm and show that it is min-max optimal, achieving the best possible constant in the leading term of the mean squared error for all $\epsilon$, and that this constant is the same as the optimal algorithm under the swap model. These results show that the add-remove and swap models give nearly identical errors for mean estimation, even though the add-remove model cannot treat the size of the dataset as public information. We also demonstrate empirically that our proposed algorithm yields at least a factor of two improvement in mean squared error over algorithms frequently used in practice. One of our main technical contributions is a new hour-glass mechanism, which might be of independent interest in other scenarios.

Related papers

• A Hitchhiker's Guide to Scaling Law Estimation [56.06982415792523]
  Scaling laws predict the loss of a target machine learning model by extrapolating from easier-to-train models with fewer parameters or smaller training sets. We estimate more than 1000 scaling laws, then derive a set of best practices for estimating scaling laws in new model families.
  arXiv  Detail & Related papers  (2024-10-15T17:59:10Z)
• Accelerating Ensemble Error Bar Prediction with Single Models Fits [0.5249805590164902]
  An ensemble of N models is approximately N times more computationally demanding compared to a single model when it is used for inference. In this work, we explore fitting a single model to predicted ensemble error bar data, which allows us to estimate uncertainties without the need for a full ensemble.
  arXiv  Detail & Related papers  (2024-04-15T16:10:27Z)
• Bayesian score calibration for approximate models [0.0]
  We propose a new method for adjusting approximate posterior samples to reduce bias and produce more accurate uncertainty quantification. Our approach requires only a (fixed) small number of complex model simulations and is numerically stable.
  arXiv  Detail & Related papers  (2022-11-10T06:00:58Z)
• Learning from aggregated data with a maximum entropy model [73.63512438583375]
  We show how a new model, similar to a logistic regression, may be learned from aggregated data only by approximating the unobserved feature distribution with a maximum entropy hypothesis. We present empirical evidence on several public datasets that the model learned this way can achieve performances comparable to those of a logistic model trained with the full unaggregated data.
  arXiv  Detail & Related papers  (2022-10-05T09:17:27Z)
• Diverse Counterfactual Explanations for Anomaly Detection in Time Series [26.88575131193757]
  We propose a model-agnostic algorithm that generates counterfactual ensemble explanations for time series anomaly detection models. Our method generates a set of diverse counterfactual examples, i.e., multiple versions of the original time series that are not considered anomalous by the detection model. Our algorithm is applicable to any differentiable anomaly detection model.
  arXiv  Detail & Related papers  (2022-03-21T16:30:34Z)
• X-model: Improving Data Efficiency in Deep Learning with A Minimax Model [78.55482897452417]
  We aim at improving data efficiency for both classification and regression setups in deep learning. To take the power of both worlds, we propose a novel X-model. X-model plays a minimax game between the feature extractor and task-specific heads.
  arXiv  Detail & Related papers  (2021-10-09T13:56:48Z)
• Distilling Interpretable Models into Human-Readable Code [71.11328360614479]
  Human-readability is an important and desirable standard for machine-learned model interpretability. We propose to train interpretable models using conventional methods, and then distill them into concise, human-readable code. We describe a piecewise-linear curve-fitting algorithm that produces high-quality results efficiently and reliably across a broad range of use cases.
  arXiv  Detail & Related papers  (2021-01-21T01:46:36Z)
• On Statistical Efficiency in Learning [37.08000833961712]
  We address the challenge of model selection to strike a balance between model fitting and model complexity. We propose an online algorithm that sequentially expands the model complexity to enhance selection stability and reduce cost. Experimental studies show that the proposed method has desirable predictive power and significantly less computational cost than some popular methods.
  arXiv  Detail & Related papers  (2020-12-24T16:08:29Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• When Ensembling Smaller Models is More Efficient than Single Large Models [52.38997176317532]
  We show that ensembles can outperform single models with both higher accuracy and requiring fewer total FLOPs to compute. This presents an interesting observation that output diversity in ensembling can often be more efficient than training larger models.
  arXiv  Detail & Related papers  (2020-05-01T18:56:18Z)
• Learning Interpretable Models Using Uncertainty Oracles [12.879371384378164]
  A desirable property of interpretable models is small size, so that they are easily understandable by humans. This leads to the following challenges: (a) small sizes imply diminished accuracy, and (b) bespoke levers provided by model families to restrict size might be insufficient to reach the desired size-accuracy trade-off.
  arXiv  Detail & Related papers  (2019-06-17T05:53:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.