Quantifying Classifier Utility under Local Differential Privacy DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Security and privacy Privacy-preserving protocols

Ye Zheng, Yidan Hu · 2025

Read Quantifying Classifier Utility under Local Differential Privacy DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Security and privacy Privacy-preserving protocols by Ye Zheng, Yidan Hu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-02727.txt.

Introduction

Ye Zheng and Yidan Hu build a general theory for predicting how much a classifier loses when its data is privacy-scrambled at the source, in a 2025 paper. Local differential privacy adds noise on the user's own device before data is shared, which protects people but blurs the patterns classifiers learn from. Designers had no unified way to forecast that cost, especially for black-box models.

The key insight is that the noise concentrates near the true data value with a known probability, So the privacy question becomes a robustness question. How well does the classifier hold up inside that small region? The framework then applies to any noise method and any classifier, and two refinements sharpen the estimates. Case studies match real measurements closely, and the theory can guide which privacy method and settings to pick. One piecewise method often wins on utility.

Catalog record

CREATORYe Zheng, Yidan Hu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-02727

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantifying Classifier Utility under Local Differential Privacy DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Security and privacy Privacy-preserving protocols Ye Zheng, Yidan Hu Abstract . Local differential privacy (LDP) provides a rigorous and quantifiable privacy guarantee for personal data by introducing perturbation at the data source. However, quantifying the impact of these perturbations on classifier utility remains a theoretical challenge, particularly for complex or black-box classifiers. This paper presents a framework for theoretically quantifying classifier utility under LDP mechanisms. The key insight is that LDP perturbation is concentrated around the original data with a specific probability, transforming utility analysis of the classifier into its robustness analysis in this concentrated region. Our framework connects the concentration analysis of LDP mechanisms with the robustness analysis of classifiers. It treats LDP mechanisms as general distributional functions and classifiers as black-box functions, thus applicable to any LDP mechanism and classifier. A direct application of our utility quantification is guiding the selection of LDP mechanisms and privacy parameters for a given classifier. Notably, our analysis shows that a piecewise-based mechanism leads to better utility compared to alternatives in common scenarios. Using this framework alongside two novel refinement techniques, we conduct case studies on utility quantification for typical mechanism-classifier combinations. The results demonstrate that our theoretical utility quantification aligns closely with empirical observations, particularly when classifiers operate in lower-dimensional input spaces. 1. Introduction Classifiers are functions that map input data to class labels, playing a fundamental role in industrial applications ranging from predictive modeling and data clustering to image recognition ( Lu and Weng 2007 ; Kowsari et al. 2019 ; Jain et al. 1999 ) . When deployed as services, classifiers require users to provide data inputs, which often contain sensitive information such as medical records or financial data, raising significant privacy concerns. While users wish to benefit from classification services, they may be reluctant to reveal their actual data. A common approach to address this concern is data perturbation, e.g. adding noise to numerical data or applying blur filters to images before sending them to the classifier. Data perturbation remains a lightweight and intuitive solution for privacy-preserving classification ( Zhang et al. 2005 ; Chen and Liu 2005 ; Zorarpaci and Özel 2021 ) . Local differential privacy (LDP) is a widely accepted mathematical framework for privacy protection through controlled data perturbation. It uses a parameter \varepsilon (the privacy parameter) to quantify the level of privacy protection. When data is processed through an LDP mechanism before being sent to a classifier, it receives provable privacy guarantees, meaning that any observer including the classifier cannot confidently infer the original sensitive data. Researchers have developed numerous LDP mechanisms for various data domains ( Dwork and Roth 2014 ; Kairouz et al. 2014 ; Wang et al. 2017 ; Wang et al. 2019 ; Li et al. 2020 ; Gu et al. 2020 ) , each offering different perturbation strategies while maintaining formal privacy guarantees. Figure 1 . From empirical data utility to theoretical data utility. This paper provides a theoretical quantification of classifier utility under LDP mechanisms by connecting the concentration analysis of LDP mechanisms with the robustness analysis of classifiers. Data utility is the most crucial metric when implementing LDP mechanisms. While privacy protection is controlled by the privacy parameter \varepsilon , data utility measures how well the perturbed data serves its intended application purpose. For simple applications like summation queries, utility can be directly quantified through the theoretical mean squared error (MSE) of LDP mechanisms ( Wang et al. 2017 ; Wang et al. 2019 ) . For classification tasks, utility corresponds to classification accuracy, which cannot be analytically expressed using MSE. A trivial approach to evaluate classifier utility under an LDP mechanism with a given privacy parameter \varepsilon is to perform multiple data perturbations, and measure the proportion of correctly classified instances, as illustrated in Figure 1 . While practical, this empirical method has significant limitations: it only applies to specific \varepsilon values and perturbed data instances; changing \varepsilon requires time-consuming re-evaluation, and different instances lead to different results. Moreover, it fails to establish relationships between utility and privacy parameters, making it inadequate for systematic comparison of LDP mechanisms. Unlike the MSE for summation queries, we currently lack an analytical utility quantification framework for classifiers. Quantifying the relationship between privacy and classifier utility presents significant analytical challenges. These challenges stem from two aspects: (i) LDP mechanisms inherently introduce perturbations across the entire data domain, potentially causing no utility for classifiers. (ii) classifiers are often complex or even black-box functions, making it difficult to analyze their behavior under perturbations. This paper develops a framework to theoretically quantify classifier utility under LDP mechanisms. Our approach addresses the aforementioned challenges through two key insights: (i) LDP mechanisms generate perturbed data that concentrates within a bounded region around the original data with a specific high probability, making extreme perturbations rare; (ii) within this concentration region, the utility analysis of a classifier can be reformulated as a robustness analysis problem. Robustness refers to how well a classifier maintains correct predictions when inputs are subjected to perturbations. We leverage established robustness analysis techniques to find the maximum permissible perturbation that preserves a classifier’s output, thereby maintaining utility. Combining the concentration analysis of LDP mechanisms with the robustness analysis of classifiers, we can establish theoretical data utility quantification in relation to the privacy parameter \varepsilon , expressed as: Given classifier h , LDP mechanism \mathcal{M}_{\varepsilon} , and raw data x : with probability at least p(\varepsilon,\theta) , h preserves its correct classification result under \mathcal{M}_{\varepsilon}(x) . This formulation provides a probabilistic guarantee for preserving the utility of classifier h when using mechanism \mathcal{M}_{\varepsilon} . The parameter \theta represents a concentration threshold that determines the probability guarantee p(\varepsilon,\theta) , which directly depends on the privacy parameter \varepsilon . Figure 1 illustrates this intuition. By determining the maximum allowable perturbation B_{\theta}(x) that a classifier h can tolerate, we can derive utility guarantees for h under \mathcal{M}_{\varepsilon} across different privacy levels without needing to repeatedly sample from the mechanism. Additionally, we introduce two refinement techniques to refine the utility quantification p(\varepsilon,\theta) for high-dimensional classifiers. First, we extend the widely used robustness notion of “robustness radius” to “robustness hyperrectangle,” enabling a more precise analysis of classifier robustness. Second, we adapt a relaxed privacy notion, Probably Approximately Correct (PAC) privacy ( Xiao and Devadas 2023 ) , as an alternative to (\varepsilon,\delta) -LDP. Under this notion, we propose a novel privacy indicator and an extended Gaussian mechanism applicable for any \varepsilon . The original Gaussian mechanism from Dwork ( Dwork and Roth 2014 ) is only valid for \varepsilon\in[0,1] . We improve the proof technique to extend it to \varepsilon\in[0,\infty) . These extensions allow the framework to provide more accurate utility quantification and incorporate more privacy-preserving mechanisms. Applications. The proposed utility quantification framework has direct applications in privacy-preserving classification systems: (i) It enables a comparative analysis of different LDP mechanisms for a given classifier by evaluating their probability guarantees p(\varepsilon,\theta) . An LDP mechanism that provides a higher p(\varepsilon,\theta) ensures better utility at the same privacy level. (ii)

Read the complete text