Quantifying Classifier Utility under Local Differential Privacy

1. Problem Statement

The paper addresses a critical gap in the field of Local Differential Privacy (LDP): the lack of a general theoretical framework to quantify the utility of classifiers when inputs are perturbed by LDP mechanisms.

• Context: Users often need to submit sensitive data (e.g., medical records, financial data) to third-party classifiers. To protect privacy, they apply LDP mechanisms (adding noise) before sending data.
• The Challenge: While LDP provides rigorous privacy guarantees (controlled by parameter $\varepsilon$), it degrades data utility (classification accuracy).
  • Current Limitation: Existing methods rely on empirical evaluation (repeatedly sampling noise and testing the classifier). This is computationally expensive, specific to a single $\varepsilon$ value, and fails to provide analytical relationships between privacy and utility.
  • Analytical Difficulty: Deriving a closed-form utility expression is hard because LDP mechanisms introduce perturbations across the entire data domain, and classifiers (especially black-box ones like neural networks) have complex, non-linear decision boundaries.

2. Methodology

The authors propose a unified framework that connects LDP concentration properties with classifier robustness analysis. The core insight is reframing utility analysis as a robustness problem within a high-probability concentration region.

A. Core Framework

The framework establishes a probabilistic guarantee for classifier utility:
$$\text{Utility} \approx P(\text{LDP output} \in \text{Robust Region}) \times P(\text{Classifier is Robust})$$

1. Concentration Analysis of LDP Mechanisms:

   • The paper models LDP mechanisms as probability distributions. It analyzes the probability that the perturbed output $\tilde{x}$ falls within a specific neighborhood $B_\theta(x)$ of the original input $x$.
   • It covers continuous mechanisms (Noise-adding like Laplace/Gaussian; Piecewise-based like PM, SW) and discrete mechanisms (k-RR, Exponential).
   • It derives closed-form expressions for the concentration probability $p(\varepsilon, \theta)$ for various mechanisms.

2. Robustness Analysis of Classifiers:

   • Instead of assuming a specific classifier structure, the framework treats classifiers as black-box functions.
   • It defines Probabilistic Robustness: A classifier is robust at $x$ with radius $\theta$ if it maintains the correct label for inputs within $B_\theta(x)$ with high probability.
   • Method: Uses Hypothesis Testing and the Hoeffding Bound to estimate the robustness radius $\theta$ by sampling points around $x$ and querying the classifier. This works for both white-box and black-box classifiers.

3. Utility Quantification:

   • The final utility guarantee $\rho(\varepsilon, \theta)$ is the product of the concentration probability (from LDP) and the robustness probability (from the classifier).
   • This allows users to calculate the probability of correct classification for any $\varepsilon$ without re-sampling the LDP mechanism.

B. Refinement Techniques

To improve accuracy, especially for high-dimensional data, the authors introduce two refinements:

1. Robustness Hyperrectangle:

   • Standard robustness uses a uniform radius $\theta$ (an $\ell_\infty$-ball). The authors generalize this to a hyperrectangle where each dimension $i$ has its own robustness bound $[a_i, b_i]$.
   • This provides a tighter, less conservative estimate of the robust region, leading to higher utility guarantees.

2. PAC Privacy Relaxation:

   • Pure $\varepsilon$-LDP is restrictive. The authors adopt Probably Approximately Correct (PAC) LDP, which allows a small failure probability $\delta$.
   • Privacy Indicator: A technique to convert pure LDP mechanisms into PAC LDP mechanisms.
   • Extended Gaussian Mechanism: The standard Gaussian mechanism fails pure LDP for $\varepsilon > 1$. The authors prove an extended version that satisfies $(\varepsilon, \delta)$-PAC LDP for any $\varepsilon$, enabling the use of Gaussian noise in this framework.

3. Key Contributions

1. First Analytical Framework: The first framework to provide analytical (closed-form) utility quantification for classifiers under LDP-perturbed inputs, bridging concentration analysis and robustness.
2. Unified Robustness Method: A black-box approach to determine classifier robustness using hypothesis testing, applicable to any classifier type (linear, tree-based, neural networks).
3. Refinement Techniques:
   • Introduction of Robustness Hyperrectangles for dimension-specific robustness.
   • Adaptation of PAC Privacy to include an Extended Gaussian mechanism and a privacy indicator, expanding the range of usable mechanisms.
4. Mechanism Selection Guidelines: The framework enables systematic comparison of LDP mechanisms, revealing that Piecewise-based mechanisms (like PM) often outperform noise-adding mechanisms (like Laplace) in common scenarios.

4. Results and Case Studies

The authors validated the framework using three datasets and various classifiers (Logistic Regression, Random Forest, CNN):

• Stroke Prediction (Low-dim, Medical): Theoretical utility closely matched empirical observations. The Piecewise (PM) mechanism consistently provided the highest utility.
• Bank Customer Attrition (Low-dim, Financial): Similar results; the framework successfully guided the selection of $\varepsilon$ to meet specific utility thresholds.
• MNIST-7x7 (High-dim, Image):
  • Theoretical utility showed a larger gap with empirical results compared to low-dimensional cases due to complex decision boundaries and error accumulation in high dimensions.
  • However, the trend remained consistent: mechanisms with higher theoretical utility exhibited higher empirical utility.
  • The framework demonstrated that the PM mechanism generally outperforms others even in high-dimensional settings.

Efficiency: The theoretical approach is significantly faster than empirical methods. For example, computing theoretical utility took 0.94ms compared to 859ms for empirical estimation (2000 samples) for the Exponential mechanism.

5. Significance

• Systematic Design: Provides a mathematical tool for designers and users to select the optimal LDP mechanism and privacy parameter ($\varepsilon$) for a specific classifier and utility requirement, moving away from trial-and-error.
• Black-Box Applicability: Unlike previous works requiring knowledge of classifier internals, this framework works with black-box models, making it practical for real-world deployment.
• Privacy-Utility Trade-off: Offers a rigorous way to quantify the trade-off, allowing users to set a minimum utility threshold (e.g., "I need 90% accuracy") and derive the maximum allowable privacy budget ($\varepsilon$).
• Future Directions: The paper suggests extending this robustness-concentration connection to other domains like program verification and control systems, and exploring correlated LDP mechanisms.

In summary, this paper transforms the evaluation of LDP for classification from an empirical, case-by-case process into a rigorous, analytical science, enabling precise privacy-utility engineering.