Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance-猫眼课题宝

DOI：

10.48550/arxiv.2210.11542

发表时间：

2022-10

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Zhao Song;Xin Yang;Yuanyuan Yang;Licheng Zhang

投影维护是数据结构的核心任务之一。用于投影维护的高效数据结构最近导致了许多凸规划算法的突破。在这项工作中，我们进一步将该框架扩展到Kronecker产品结构。给定一个约束矩阵和一个具有稀疏本征基的半正定矩阵$W，我们考虑了保持投影形式的任务：${SFB}^top({SFB}{SFB}^TOP)^-1}{\SFB}$，其中${\sf B}={\sf A}(W\otime i)$或${\sf B}={\sf A}(W^{1/2}\o次W^{1/2})$。在每一次迭代中，权重矩阵$W$都会有一个较低的排名变化，而我们会得到一个新的向量$h$。目标是维护投影矩阵并以良好的逼近保证回答查询${\SF B}^\top({\SF B}{\SF B}^\top)^{-1}{\SF B}h$。我们为该任务设计了一种快速的动态数据结构，它对自适应攻击具有很强的健壮性。在[Beimel，Kaplan，Mansour，Nissim，Saranurak和Stemmer，STEC‘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.

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

文献摘要

相似文献