When Focus Enhances Utility: Target Range LDP Frequency Estimation and Unknown Item Discovery

When Focus Enhances Utility: Target Range LDP Frequency Estimation and Unknown Item Discovery

Speakers: Bo Jiang

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=A99LEANrl9o

Overview

Local differential privacy (LDP) is a cornerstone of privacy-preserving data collection, used by companies like Google and Apple to gather statistics without trusting any central server. However, the standard Count Mean Sketch (CMS) approach uses fixed, deterministic parameters that are not optimized for real-world use cases. This talk from TikTok researchers presents a generalized CMS approach that tunes perturbation parameters based on the target query frequency range, achieving lower variance for queries of interest while simultaneously reducing communication costs by at least 50%. The researchers also introduce an unknown item discovery protocol that uses a semi-honest auxiliary server to reduce the computational cost of discovering new, previously unseen items from cubic to linear time.

Background

▶ Watch: Background: central vs. local differential privacy models (0:00)

Differential privacy guarantees privacy for individuals while enabling data analysis. In the central model, a trusted server collects raw data and adds noise after aggregation. In the local differential privacy (LDP) model, since no server is trusted, clients add noise before sending their data. The server receives only noisy data, which it aggregates and analyzes.

The Count Mean Sketch (CMS) method, proposed by Apple, is a widely used LDP approach. On the client side, a hash function maps the private input into a vector, differential privacy noise is added by perturbing bits, and the noisy vector is sent to the server. The server aggregates responses from many clients and uses an unbiased estimator to recover frequency estimates. CMS supports arbitrary input domains (infinite domains are mapped to a fixed hash range) and provides unbiased estimation with closed-form variance expressions.

However, CMS has limitations: its perturbation parameters are deterministic and not optimized, and large hash ranges create high communication costs since the entire vector must be transmitted.

Key Findings

▶ Watch: Generalized CMS: tunable parameters for better utility (4:00)

Tunable Parameters Improve Both Utility and Efficiency: By making the hash range, number of hash functions, DP perturbation probability, and vector message size all tunable rather than fixed, the researchers demonstrated that both lower variance and lower communication cost can be achieved simultaneously.

Communication Reduction via Sparse Vector Compression: Before DP noise is applied, the CMS output vector has only one position set to "1" with all others empty -- an extremely sparse vector. Even after perturbation, the vector remains mostly zeros. By transmitting only the positions of "1" values and ignoring zeros, communication cost is reduced by at least half compared to classic CMS.

Target Frequency Optimization: The variance of the CMS estimator depends on both the tunable parameters and the true frequency of the target query. In real applications, analysts are typically interested in items within a specific frequency range (e.g., the most popular emojis, not all emojis). By plugging the target frequency into the variance equation, the optimization problem becomes a standard parameter tuning problem. The optimal perturbation probability P varies with the target frequency: items of higher interest (popular items) benefit from larger P values.

Unknown Item Discovery: Standard LDP only works when the server knows what to query. For discovering new, previously unseen items (e.g., a suddenly popular new emoji), the researchers introduce a protocol using a semi-honest auxiliary server that performs counting on cryptographic hashes. Items appearing more than a DP-determined threshold are released to the final server for decryption, achieving linear computational cost compared to the cubic cost of existing graph-based approaches from Apple and Google.

Technical Deep Dive

▶ Watch: Sparse vector compression cuts communication by 50%+ (6:00)

Generalized CMS Protocol: The client initializes an output vector (now with tunable length, potentially much smaller than the hash range), hashes the input with probability P (another tunable parameter), fills remaining positions with random elements, and transmits the compressed vector. The key insight is that the output vector length can be decoupled from the hash range, since the original sparse vector contains mostly empty positions.

Variance Optimization: The variance of the frequency estimator is expressed as a function of tunable parameters (p, q, m) and the true frequency FD. By fixing a target frequency range and minimizing variance over the parameter space, optimal parameter selections are derived. Visualization shows that the classic CMS parameter selection is demonstrably suboptimal -- for any given target frequency, a better P exists that reduces variance.

Unknown Item Discovery Protocol: Users encrypt their message with the final server's public key and separately hash it with a cryptographic hash function. The auxiliary server uses hash values for counting without seeing the actual data. When an item's count exceeds the DP threshold t, the auxiliary server releases the corresponding encrypted values to the final server for decryption. This transitions from pure LDP to a two-server model, trading the LDP guarantee for linear computational efficiency.

Demo / Proof of Concept

▶ Watch: Unknown item discovery with semi-honest auxiliary server (10:00)

The researchers presented experimental results on the ACI (Adult Census Income) dataset, showing:

• The optimized parameter selection achieves lower normalized variance than classic CMS across all epsilon values, with the improvement being most pronounced at small epsilon (strong privacy guarantees)
• Communication savings of at least 50% through sparse vector compression, with greater savings as hash ranges increase
• An interesting boundary effect: at very large epsilon values, the classic CMS approach can achieve marginally better variance, but such large epsilon values should not be used in practice for meaningful privacy guarantees

Defensive Implications

▶ Watch: Experiment results: variance reduction across epsilon values (12:00)

This research has direct implications for organizations deploying privacy-preserving data collection at scale:

Better Privacy-Utility Tradeoff: Organizations using LDP for telemetry, usage analytics, or A/B testing can achieve more accurate results at the same privacy level, or stronger privacy guarantees at the same accuracy, by adopting the optimized parameter selection.

Reduced Bandwidth Costs: The 50%+ communication reduction is significant for mobile deployments where bandwidth is constrained and costly. This makes LDP more practical for large-scale mobile data collection.

New Item Discovery: The unknown item discovery protocol enables organizations to detect emerging trends (new terms, new behaviors, new attack patterns) in their data without compromising user privacy, though it requires a semi-honest auxiliary server.

Privacy Budget Management: The target frequency optimization allows organizations to allocate their privacy budget more efficiently by focusing on the frequency ranges most relevant to their analysis goals.

Key Takeaways

• Classic Count Mean Sketch LDP parameters are suboptimal; tuning perturbation probability based on target frequency range yields measurably lower variance
• Sparse vector compression reduces LDP communication costs by at least 50% by decoupling message size from hash range
• The optimal perturbation probability P depends on the target frequency: higher-frequency items benefit from larger P values
• Unknown item discovery can be achieved with linear computational cost using a semi-honest auxiliary server and multiple encryption
• The approach works for arbitrary input domains and maintains unbiased estimation with closed-form variance expressions
• Trade-off: unknown item discovery protocol moves from pure LDP to a two-server model

About the Speaker(s)

Bo Jiang is represented by presenter Don Hanlu, a research scientist at TikTok. The research focuses on practical local differential privacy deployments at scale, addressing the real-world challenges of communication efficiency and parameter optimization that arise when deploying LDP across billions of users. The work reflects TikTok's operational experience with privacy-preserving data collection.