Private Quantiles Estimation in the Presence of Atoms

• URL: http://arxiv.org/abs/2202.08969v1
• Date: Tue, 15 Feb 2022 09:44:14 GMT
• Title: Private Quantiles Estimation in the Presence of Atoms
• Authors: Cl\'ement Lalanne (ENS Lyon), Cl\'ement Gastaud, Nicolas Grislain, Aur\'elien Garivier (CB), R\'emi Gribonval (CB)
• Abstract summary: We address the differentially private estimation of multiple quantiles of a dataset. Non-smoothed JointExp suffers from an important lack of performance in the case of peaked distributions. We propose a simple and numerically efficient method called Heuristically Smoothed JointExp.
• Score: 7.5072219939358105
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the differentially private estimation of multiple quantiles (MQ) of a dataset, a key building block in modern data analysis. We apply the recent non-smoothed Inverse Sensitivity (IS) mechanism to this specific problem and establish that the resulting method is closely related to the current state-of-the-art, the JointExp algorithm, sharing in particular the same computational complexity and a similar efficiency. However, we demonstrate both theoretically and empirically that (non-smoothed) JointExp suffers from an important lack of performance in the case of peaked distributions, with a potentially catastrophic impact in the presence of atoms. While its smoothed version would allow to leverage the performance guarantees of IS, it remains an open challenge to implement. As a proxy to fix the problem we propose a simple and numerically efficient method called Heuristically Smoothed JointExp (HSJointExp), which is endowed with performance guarantees for a broad class of distributions and achieves results that are orders of magnitude better on problematic datasets.

Related papers

• Equivariant Evidential Deep Learning for Interatomic Potentials [55.6997213490859]
  Uncertainty quantification is critical for assessing the reliability of machine learning interatomic potentials in molecular dynamics simulations.<n>Existing UQ approaches for MLIPs are often limited by high computational cost or suboptimal performance.<n>We propose textitEquivariant Evidential Deep Learning for Interatomic Potentials ($texte2$IP), a backbone-agnostic framework that models atomic forces and their uncertainty jointly.
  arXiv  Detail & Related papers  (2026-02-11T02:00:25Z)
• Data-Driven Information-Theoretic Causal Bounds under Unmeasured Confounding [10.590231532335691]
  We develop a data-driven information-theoretic framework for partial identification of conditional causal effects under unmeasured confounding.<n>Our key theoretical contribution shows that the f-divergence between the observational distribution P(Y | A = a, X = x) and the interventional distribution P(Y | do(A = a), X = x) is upper bounded by a function of the propensity score alone.<n>This result enables sharp partial identification of conditional causal effects directly from observational data, without requiring external sensitivity parameters, auxiliary variables, full structural specifications, or outcome boundedness assumptions.
  arXiv  Detail & Related papers  (2026-01-23T20:47:48Z)
• Efficient Ensemble Conditional Independence Test Framework for Causal Discovery [46.328102756312724]
  We introduce the Ensemble Conditional Independence Test (E-CIT), a general and plug-and-play framework.<n>E-CIT partitions the data into subsets, applies a given base CIT independently to each subset, and aggregates the resulting p-values.<n>Results demonstrate that E-CIT not only significantly reduces the computational burden of CITs and causal discovery but also achieves competitive performance.
  arXiv  Detail & Related papers  (2025-09-25T11:31:16Z)
• TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data [50.797729676285876]
  We propose TernaryVote, which combines a ternary compressor and the majority vote mechanism to realize differential privacy, gradient compression, and Byzantine resilience simultaneously. We theoretically quantify the privacy guarantee through the lens of the emerging f-differential privacy (DP) and the Byzantine resilience of the proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-16T16:41:14Z)
• Communication-Efficient Heterogeneous Federated Learning with Generalized Heavy-Ball Momentum [19.473386008007942]
  Federated Learning (FL) has emerged as the state-of-the-art approach for learning from decentralized data in privacy-constrained scenarios.<n>Despite significant research efforts, existing approaches often degrade severely due to the joint effect of heterogeneity and partial client participation.<n>In this work, we propose a novel Generalized Heavy-Ball Momentum (GHBM)<n>We show that GHBM substantially improves state-of-the-art performance under random uniform client sampling.
  arXiv  Detail & Related papers  (2023-11-30T14:17:57Z)
• Measurement Simplification in ρ-POMDP with Performance Guarantees [6.129902017281406]
  Decision making under uncertainty is at the heart of any autonomous system acting with imperfect information. This paper introduces a novel approach to efficient decision-making, by partitioning the high-dimensional observation space. We show that the bounds are adaptive, computationally efficient, and that they converge to the original solution.
  arXiv  Detail & Related papers  (2023-09-19T15:40:42Z)
• Exploiting Structure for Optimal Multi-Agent Bayesian Decentralized Estimation [4.320393382724066]
  Key challenge in Bayesian decentralized data fusion is the rumor propagation' or double counting' phenomenon. We show that by exploiting the probabilistic independence structure in multi-agent decentralized fusion problems a tighter bound can be found. We then test our new non-monolithic CI algorithm on a large-scale target tracking simulation and show that it achieves a tighter bound and a more accurate estimate.
  arXiv  Detail & Related papers  (2023-07-20T05:16:33Z)
• Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation [8.9598796481325]
  We investigate the consequences of this observation for both algorithms and computational complexity across different statistical problems. We establish an information-computation gap for private sparse mean estimation. We also give evidence for privacy-induced information-computation gaps for several other statistics and learning problems.
  arXiv  Detail & Related papers  (2022-11-01T20:03:41Z)
• Federated Expectation Maximization with heterogeneity mitigation and variance reduction [0.0]
  This paper introduces FedEM, which is the first extension of the Expectation Maximization (EM) algorithm for latent variable models. To alleviate complexity of communication, FedEM appropriately defined complete data sufficient statistics. Results presented support our theoretical findings as well as an application handles missing values imputation for biodiversity monitoring.
  arXiv  Detail & Related papers  (2021-11-03T09:14:34Z)
• Domain Generalization via Domain-based Covariance Minimization [4.414778226415752]
  We propose a novel variance measurement for multiple domains so as to minimize the difference between conditional distributions across domains. We show that for small-scale datasets, we are able to achieve better quantitative results indicating better generalization performance over unseen test datasets.
  arXiv  Detail & Related papers  (2021-10-12T19:30:15Z)
• Probabilistic Simplex Component Analysis [66.30587591100566]
  PRISM is a probabilistic simplex component analysis approach to identifying the vertices of a data-circumscribing simplex from data. The problem has a rich variety of applications, the most notable being hyperspectral unmixing in remote sensing and non-negative matrix factorization in machine learning.
  arXiv  Detail & Related papers  (2021-03-18T05:39:00Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• GenDICE: Generalized Offline Estimation of Stationary Values [108.17309783125398]
  We show that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions. The resulting algorithm, GenDICE, is straightforward and effective.
  arXiv  Detail & Related papers  (2020-02-21T00:27:52Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

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.