论文标题
素描符合差异隐私：动态kronecker投影维护的快速算法
Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
论文作者
论文摘要
投影维护是核心数据结构任务之一。用于投影维护的有效数据结构已导致许多凸编程算法的突破。在这项工作中，我们将此框架进一步扩展到Kronecker产品结构。给定一个约束矩阵$ {\ sf a} $和一个阳性的半定位矩阵$ w \ in \ mathbb {r}^{n \ times n} $，并具有稀疏的eigenbasis，我们考虑以$ {\ sf b}^\ sf（\ sf）形式保持预测的任务b}^\ top）^{ - 1} {\ sf b} $，其中$ {\ sf b} = {\ sf a}（w \ otimes i）$或$ {\ sf b} = {\ sf b} = {\ sf a}在每次迭代中，重量矩阵$ w $都会获得低级变化，我们将获得新的矢量$ h $。目标是维护投影矩阵并回答查询$ {\ sf b}^\ top（{\ sf b} {\ sf b}^\ top）^{ - 1} { - 1} {\ sf b} h $，并提供良好的近似值保证。我们为此任务设计了快速的动态数据结构，并且对自适应对手具有鲁棒性。遵循[Beimel，Kaplan，Mansour，Nissim，Saranurak和Stemmer，Stoc'22]的精美而开创性的作品，我们使用差异隐私的工具来减少数据结构所需的随机性并进一步改善运行时间。
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\in \mathbb{R}^{n\times n}$ with a sparse eigenbasis, we consider the task of maintaining the projection in the form of ${\sf B}^\top({\sf B}{\sf B}^\top)^{-1}{\sf B}$, where ${\sf B}={\sf A}(W\otimes I)$ or ${\sf B}={\sf A}(W^{1/2}\otimes W^{1/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 B}{\sf B}^\top)^{-1}{\sf B}h$ 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.
