# Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance

arXiv: https://arxiv.org/abs/2210.11542 · HTML: https://mlsanity.com/paper/2210.11542/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2022.

## Built on by (most cited first, 22 of 22)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [Differentially Private Attention Computation](https://mlsanity.com/paper/2305.04701/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [The Expressibility of Polynomial based Attention Scheme](https://mlsanity.com/paper/2310.20051/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer](https://mlsanity.com/paper/2311.13624/) (2023)
- [Structured and Fast Optimization: The Kronecker SGD Algorithm](https://mlsanity.com/paper/2305.08001/) (2023)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)

## Abstract (arXiv)

Projection maintenance is one of the core data structure tasks. Efficient data structures for projection maintenance have led to recent breakthroughs in many convex programming algorithms. In this work, we further extend this framework to the Kronecker product structure. Given a constraint matrix sf A and a positive semi-definite matrix W∈ ℝn× n with a sparse eigenbasis, we consider the task of maintaining the projection in the form of sf B^top(sf Bsf B^top)-1sf B, where sf B=sf A(Wotimes I) or sf B=sf A(W1/2otimes W1/2). At each iteration, the weight matrix W receives a low rank change and we receive a new vector h. The goal is to maintain the projection matrix and answer the query sf B^top(sf Bsf B^top)-1sf Bh with good approximation guarantees. We design a fast dynamic data structure for this task and it is robust against an adaptive adversary. Following the beautiful and pioneering work of [Beimel, Kaplan, Mansour, Nissim, Saranurak and Stemmer, STOC'22], we use tools from differential privacy to reduce the randomness required by the data structure and further improve the running time.