A Framework for Private Matrix Analysis
A Framework for Private Matrix Analysis
复制标题
私有矩阵分析框架
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sarvagya Upadhyay
中科院分区：
文献类型：
--
作者：
Jalaj Upadhyay;Sarvagya Upadhyay
我们研究了滑动窗口模型中的私有矩阵分析，在该模型中，只有对矩阵的最后$W$更新被认为对分析有用。我们给出了谱逼近、主成分分析和线性回归的第一个有效的$o(W)$空间差分私有算法。对于主成分分析的两个重要变种：稀疏主成分分析和非负主成分分析，我们还提出并证明了有效的差分私有算法。在我们的工作之前，即使在静态数据设置下，稀疏和非负的差分私有主成分分析也没有这样的结果。这些算法是通过识别由流矩阵形成的半正定矩阵的充分条件而得到的。我们还给出了一个计算低阶近似所需空间的下界，即使算法给出了乘性逼近并产生了附加误差。这是通过降低到某个通信复杂性问题来实现的。
We study private matrix analysis in the sliding window model where only the last $W$ updates to matrices are considered useful for analysis. We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis: sparse principal component analysis and non-negative principal component analysis. Prior to our work, no such result was known for sparse and non-negative differentially private principal component analysis even in the static data setting. These algorithms are obtained by identifying sufficient conditions on positive semidefinite matrices formed from streamed matrices. We also show a lower bound on space required to compute low-rank approximation even if the algorithm gives multiplicative approximation and incurs additive error. This follows via reduction to a certain communication complexity problem.
滑动窗口模型下的次线性空间私有算法
DOI：
--
发表时间：
2019
期刊：
Proceedings of Machine Learning Research
影响因子：
--
作者：
Upadhyay, Jalaj
通讯作者：
Upadhyay, Jalaj