On Differential Privacy for Adaptively Solving Search Problems via Sketching

On Differential Privacy for Adaptively Solving Search Problems via Sketching

Speakers: Zhao Song, UC Berkeley; Shiyuan Feng, Peking University; Ying Feng, MIT; George Li, CMU; David Woodruff, CMU; Lichen Zhang, MIT

Conference: ICML 2025

YouTube: https://slideslive.com/39044045

Overview

This talk, presented by Zhao Song from UC Berkeley, introduces a novel framework for achieving differential privacy (DP) in the context of adaptively solving search problems through the strategic use of sketching. The research is a collaborative effort with Shiyuan Feng, Ying Feng, George Li, David Woodruff, and Lichen Zhang, with the core ideas largely attributed to Lichen Zhang. The talk addresses a fundamental challenge in privacy-preserving machine learning and data systems: how to maintain strong privacy guarantees when queries are not independent but rather adaptively chosen based on the results of previous queries. This scenario is common in real-world applications such as personalized recommendations, interactive data analysis, and adaptive learning algorithms, where the traditional approaches to differential privacy often lead to significant utility loss or require excessive computational resources.

The significance of this work lies in its ability to combine three critical areas—differential privacy, efficient search data structures, and dimensionality reduction via sketching—to provide theoretical guarantees for privacy-preserving adaptive computation. By demonstrating how to achieve sublinear improvements in resource requirements (specifically, a sqrt(T) factor for T adaptive queries) over naive baselines, the paper offers a more practical path towards deploying private systems that can handle complex, sequential interactions. This is particularly relevant as machine learning models become increasingly interactive and data-driven, necessitating robust privacy mechanisms that do not compromise the utility or efficiency of adaptive systems.

Background

▶ Watch: Introduction, talk outline, and speaker's channels (0:00)

The landscape of modern machine learning and data science is characterized by vast datasets and complex computational tasks. Ensuring the privacy of individual data points within these systems has become paramount, leading to the development and widespread adoption of differential privacy (DP). DP provides a rigorous mathematical guarantee that the presence or absence of any single individual's data in a dataset does not significantly alter the outcome of an analysis. The core idea is that if an algorithm's output changes only marginally when a single individual's data is added or removed, then an observer cannot infer much about that individual from the output, thereby protecting their privacy. As illustrated in the talk, if an AI system checking author profiles for a conference submission makes the same decision (desk accept/reject) whether one author's profile is complete or incomplete, it exhibits a form of differential privacy. This ensures that a single author's status doesn't drastically change the paper's fate in a way that reveals their private information.

Search data structures are fundamental building blocks in computer science, designed to preprocess a collection of data to enable rapid querying and retrieval. Imagine a supermarket where items are organized; a well-designed data structure allows for quick location of specific items. In machine learning, search problems are ubiquitous. For instance, nearest neighbor search (NNS) finds the data point closest to a given query point. This is crucial in applications like Reformer architectures for Transformers, which approximate attention computation by searching for relevant keys rather than computing all pairwise similarities, thereby reducing the quadratic complexity to something more manageable. Similarly, in regression and neural networks, identifying data points above or below certain thresholds, or finding hyperplanes, can be framed as search problems. Efficient search data structures often employ techniques like hashing to map data points to specific buckets, facilitating quick lookups.

A critical distinction in query types is between non-adaptive and adaptive queries. Non-adaptive queries are predetermined and independent of previous results. For example, simultaneously querying for a Spider-Man, a dinosaur, and a game character mask will yield three independent results. In contrast, adaptive queries are sequential, where each subsequent query can be formulated based on the output of preceding queries. The talk vividly illustrates this with an example of decoding a human's face: the first query reveals a Spider-Man mask, the second query is then modified based on this output to reveal a black mask, and the third query, further informed by previous results, finally decodes the human's face. This adaptive nature poses a significant challenge for differential privacy because the cumulative information leaked through a sequence of dependent queries can be much greater than the sum of information leaked by independent queries. Each query, by influencing the next, can amplify privacy vulnerabilities, making it difficult to maintain a strong privacy budget over time without severely degrading utility.

Finally, sketching is a powerful dimensionality reduction technique that transforms high-dimensional data into a much smaller representation (a "sketch") while preserving essential properties. Analogous to drawing a skeleton or boundary of an image, sketching captures the core features. Its applicability is particularly strong when data exhibits properties like sparsity (most entries are zero) or low-rank (the data can be well-approximated by a matrix of much lower rank). The talk provides examples: authors being away from keyboard for a deadline might lead to a sparse matrix of contributions, or authors writing multiple papers in the same topic could result in a low-rank matrix representing author-paper relationships. Sketching is vital for efficiency, as computations on smaller, sketched data are significantly faster. The core problem this research tackles is how to combine these three elements—differential privacy, search data structures, and sketching—to enable efficient and private adaptive search, overcoming the inherent challenges of privacy leakage in sequential, dependent query scenarios.

Key Findings

▶ Watch: Basic concept of data structures and organization (3:30)

The central contribution of this work is the development of a novel framework that successfully integrates differential privacy (DP) with search data structures and sketching to address the challenging problem of adaptively solving search problems. The research provides theoretical guarantees for achieving privacy in adaptive query settings, which are notoriously difficult due to the potential for cumulative privacy leakage.

The talk highlights two major specific results:

1. Nearest Neighbor Search (NNS) with Adaptive Queries:

• For T adaptive queries in a C-approximate nearest neighbor search setting (where C > 1 allows for some approximation loss for efficiency), the proposed algorithm achieves a significant improvement over naive approaches.
• A naive algorithm for T adaptive queries would typically require T independent copies of the data structure, each consuming a separate privacy budget. Another naive baseline, for low-dimensional data (dimension D), might require D copies to boost success probability.
• The key finding is that the new method requires only sqrt(T) copies of the data structure (assuming S is a small number related to problem parameters). This sqrt(T) factor improvement represents a substantial reduction in the computational and privacy budget overhead for handling a sequence of adaptive queries. It means that to answer T adaptive queries, the system effectively needs resources proportional to the square root of the number of queries, rather than linearly proportional.

1. Dynamic Programming (DPg) with Adaptive Updates:

• The framework extends to dynamic programming problems involving adaptive updates to matrices U and B.
• Under an assumption on kappa (the condition number of matrix U over time), a similar sqrt(T) improvement in efficiency is achieved. This indicates that the principles of privacy-preserving adaptive computation via sketching are broadly applicable beyond just nearest neighbor search.
• Furthermore, if the matrix U itself is not updated throughout the process, the dependence on the kappa assumption can be entirely removed, simplifying the conditions under which these efficiency gains are realized.

The core underlying technique enabling these improvements is the strategic application of sketching, which leverages sparsity or low-rank properties of the data. By reducing the effective dimensionality or complexity of the data, sketching allows for more efficient privacy mechanisms to be applied, especially in sequential, adaptive settings where each query's output could influence subsequent privacy budgets. The results are presented as mathematical theorems, emphasizing the theoretical robustness of the proposed methods. The speaker even jokingly suggests that follow-up work building on this "oral paper" has a "very very high chance to get a best paper or oral at least in next talk," underscoring the perceived significance and potential impact of these theoretical contributions.

Technical Deep Dive

▶ Watch: Illustrating search data structures with image queries (4:00)

The technical core of this research lies in its innovative fusion of differential privacy (DP), search data structures, and sketching to address the complexities of adaptive queries. Adaptive queries, where subsequent queries are formulated based on the outputs of previous ones, present a unique challenge for DP. In a non-adaptive setting, a fixed privacy budget can be allocated across all queries. However, with adaptivity, each query's output can reveal information that influences the next, potentially amplifying privacy leakage over time. Naively applying DP to each query in an adaptive sequence can quickly deplete the privacy budget or lead to severe utility loss due to excessive noise.

The paper's approach circumvents this by cleverly integrating sketching. Sketching techniques are employed when the underlying data or the query operations exhibit properties of sparsity or low-rank. For instance, if data can be represented by a sparse matrix (many zero entries) or a low-rank matrix (can be approximated by a product of two lower-dimension matrices), then a compact sketch can capture its essential information without incurring significant loss. This dimensionality reduction is crucial for efficiency. The talk provides examples like busy authors resulting in sparse contribution matrices or multiple papers by one author in a session leading to a low-rank author-paper matrix.

For nearest neighbor search (NNS), the problem is defined as finding a C-approximate nearest neighbor for a query point, where C > 1 implies a relaxed search criterion. Traditional DP for NNS often involves adding noise to distances or to the retrieved neighbor itself. In an adaptive setting with T queries, a straightforward approach might involve creating T independent copies of a DP-enabled data structure. Each copy would be responsible for one query, effectively isolating the privacy budget for each step. Another naive baseline mentioned is using D copies if the query and update vectors are from a low-dimensional space D, to boost success probability through union bounds over a 2^D net of points. The proposed method, however, demonstrates that for T adaptive queries, only sqrt(T) copies of the data structure are needed, given that S (a parameter not explicitly defined in detail but implied to be small) is indeed small. This sqrt(T) factor improvement is a significant efficiency gain, implying that the privacy cost or computational resources scale sublinearly with the number of adaptive queries. This is likely achieved by a more sophisticated privacy accounting mechanism, perhaps using advanced composition theorems or by designing the sketching process itself to be differentially private in a way that minimizes cumulative noise. By sketching the data, the search space is reduced, allowing for less noise to be added to achieve the same privacy guarantee, or enabling more queries for the same privacy budget.

The framework also extends to dynamic programming (DPg) problems, which often involve iterative updates to matrices. Specifically, the talk mentions updates to matrices U and B. Here, the sqrt(T) improvement is also achieved for T adaptive updates, under the assumption of kappa being the condition number of U over time. The condition number kappa typically quantifies the sensitivity of the output of a function to changes in its input, and a large kappa indicates ill-conditioning. The fact that the improvement holds under this assumption suggests that the method can handle numerical stability challenges inherent in matrix operations. Furthermore, if the matrix U remains static and is not updated throughout the process, the dependence on kappa can be entirely removed, simplifying the conditions for achieving these privacy-preserving efficiency gains.

The running time complexities for these DPg problems are expressed using terms like omega (matrix multiplication time, typically 2.31 for state-of-the-art algorithms), alpha (approximation ratio between 0 and 1), and nnz(U) (number of non-zero entries in U). The inclusion of nnz(U) indicates that the algorithms leverage the sparsity of matrices for faster computation, a direct benefit of the sketching approach. The dimension D also plays a role. This implies that the solution for dynamic programming likely involves sparse matrix operations on sketched representations, with privacy noise carefully calibrated to maintain DP guarantees across adaptive updates. The sqrt(T) factor improvement across both NNS and DPg suggests a generalizable principle for privacy accounting in adaptive settings, potentially by bounding the "effective" number of times the privacy mechanism is queried or by using techniques that amortize privacy loss over the sequence of queries. The technical novelty likely lies in how the noise is added to the sketched representations and how the privacy budget is managed over adaptive queries without incurring a linear increase in noise or resource consumption.

Experimental Setup & Results

▶ Watch: Distinguishing non-adaptive from adaptive queries (6:20)

The talk primarily focuses on theoretical contributions, presenting mathematical theorems and complexity bounds rather than empirical results from specific experimental setups. Therefore, details regarding datasets, hardware, baselines, or specific performance metrics are not provided. The presented results are theoretical guarantees on efficiency improvements under differential privacy for adaptive search problems. The paper establishes a sqrt(T) factor improvement in resource requirements for T adaptive queries in both nearest neighbor search and dynamic programming contexts, compared to naive differentially private baselines. These improvements are quantified in terms of the number of data structure copies needed or the overall computational complexity, incorporating parameters like matrix multiplication time (omega), approximation ratio (alpha), and the number of non-zero entries (nnz) in matrices, under specified assumptions such as the smallness of S or the condition number kappa.

Practical Implications

▶ Watch: Detailed example of adaptive queries and responses (8:00)

This research has significant practical implications for the design and deployment of privacy-preserving machine learning systems, particularly those that involve interactive or sequential data processing.

For Practitioners and Model Builders: The ability to handle adaptive queries under differential privacy (DP) is crucial for a wide array of real-world applications. Consider personalized recommendation systems, where a user's next action (query) is often influenced by previous recommendations. Or adaptive learning platforms, where the curriculum adjusts based on a student's performance. In healthcare, diagnostic tools might ask follow-up questions based on initial test results. Historically, ensuring strong DP in such adaptive scenarios has been challenging, often leading to either excessive noise (making the system useless) or requiring unrealistic resource allocation. This work offers a theoretically sound path to building such systems, enabling model builders to design more sophisticated, interactive models without sacrificing user privacy. The sqrt(T) improvement means that systems can support a much larger number of adaptive interactions for a given privacy budget, making DP-enabled adaptive systems more feasible and practical.

For Infrastructure Teams and Deployers: The sqrt(T) factor improvement in resource allocation (e.g., needing sqrt(T) data structure copies instead of T) translates directly into tangible operational benefits. This means reduced computational overhead, lower memory footprint, and potentially faster query response times for DP-enabled adaptive search services. Infrastructure teams can deploy these systems more efficiently, optimizing resource utilization and potentially lowering operational costs. The reliance on sketching further aids this by leveraging data properties like sparsity and low-rank, which are common in many large-scale datasets. This allows for processing smaller data representations, further enhancing efficiency.

Tradeoffs and Limitations: While promising, the practical application of this framework comes with certain tradeoffs and considerations:

1. Approximation Ratio (alpha and C): The nearest neighbor search is C-approximate, and dynamic programming results involve an approximation ratio alpha. This means the system might not always return the exact nearest neighbor or the exact optimal solution. Practitioners must evaluate whether this controlled level of approximation is acceptable for their specific application, balancing privacy and efficiency against accuracy.
2. Assumptions on Data Properties: The efficiency gains are heavily reliant on the data exhibiting sparsity or low-rank properties, which enable effective sketching. While common in many domains (e.g., text data, graph data, user-item interactions), not all datasets will naturally possess these characteristics. Applications with dense, high-entropy data might not see the same level of benefits.
3. Problem-Specific Parameters (S, kappa): The sqrt(T) improvement in NNS depends on S being a "small number," and for dynamic programming, the kappa (condition number) assumption is sometimes needed. The practical implications of these parameters (e.g., how small S needs to be, or the typical range of kappa in real-world problems) need further investigation. High values of kappa might still pose challenges.
4. Theoretical vs. Empirical Performance: The current work presents theoretical guarantees. While strong, translating these into real-world performance gains often involves careful implementation, choice of sketching techniques, and calibration of privacy parameters. Empirical validation on diverse datasets and hardware stacks would be the next crucial step to understand practical bottlenecks and fine-tune implementations.
5. Future Directions: The speaker explicitly mentions future directions like "removing the assumption and dependence on S and kappa." This indicates that the current framework, while powerful, still has room for generalization and robustness improvements, which could further broaden its applicability.

In essence, this research provides a powerful theoretical foundation for building more efficient and privacy-preserving adaptive systems. It empowers practitioners to deploy interactive ML solutions in sensitive domains with stronger privacy guarantees, while infra teams can benefit from reduced resource consumption. However, careful consideration of the inherent approximations, data assumptions, and the need for empirical validation remains paramount for successful real-world deployment.

Key Takeaways

• Addressing Adaptive Query Privacy: The research tackles the challenging problem of maintaining differential privacy for adaptive queries, where sequential queries depend on previous outputs, which typically amplifies privacy leakage.
• Novel Framework: It proposes a novel framework combining differential privacy, search data structures, and sketching to achieve privacy-preserving adaptive computation.
• Efficiency Gains: The core contribution is a significant sqrt(T) factor improvement in resource efficiency (e.g., requiring sqrt(T) data structure copies instead of T) for T adaptive queries in both nearest neighbor search and dynamic programming problems.
• Leveraging Data Properties: The efficiency is largely enabled by sketching, which capitalizes on sparsity or low-rank properties of the data to reduce dimensionality and computational complexity.
• Broad Applicability: The results apply to fundamental ML tasks like C-approximate nearest neighbor search and dynamic programming with matrix updates, demonstrating the versatility of the approach.
• Theoretical Foundation for Practical Systems: This work provides strong theoretical guarantees, laying the groundwork for developing more practical and deployable privacy-preserving interactive machine learning and data analysis systems.

About the Speaker(s)

The talk was presented by Zhao Song from UC Berkeley. This research is a collaborative effort, with significant contributions from Shiyuan Feng (Peking University), Ying Feng (MIT), George Li (CMU), David Woodruff (CMU), and Lichen Zhang (MIT), with the major ideas for the paper attributed to Lichen Zhang. Zhao Song mentions maintaining a YouTube and Bilibili channel where he shares videos about real-time research with students, taking care to protect their privacy through visual anonymization. He also noted that this ICML 2025 talk was his first conference presentation in many years.