#matrix-factorization

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Awnon Bhowmik, Mahmudul Hasan

本文研究纯ε差分隐私(DP)下连续计数问题中任意实数矩阵分解的成本。设T_n为下三角前缀和矩阵,Laplace矩阵机制的因子化成本c_frob和c_two分别控制每坐标平方误差的均值和最大值。作者证明了对于任意符号、稀疏性和平方性限制,以及任意有限内维,c_frob(T_n)和c_two(T_n)均为Θ((log(n+1))^{3/2})。由此得出,在纯ε-DP矩阵机制类中,优化的最大和均方误差均为Θ(ε^{-2} log^3(n+1))。此前Arkhipov和Kalinin仅对{0,1}项因子建立了匹配的低阶,并将任意因子扩展留作开放问题,本文填补了这一空白。下界证明采用p-核障碍技术:对前缀链建立聚合列宽估计D_k(T_n)≈n^{3/2} k^{-1/2}(1≤k≤n/16),结合Pietsch和Hinrichs–Pietsch的逼近空间转换,在临界指数p=2/3处发挥调和作用,再利用Hölder不等式将结果转移到两个因子成本。同一论证还确定了核范数nucpow_p(T_n)对0<p<1的精确阶:p<2/3时为n,p=2/3时为n log n,p>2/3时为n^{3p/2}。上界通过Fenwick区间分解构造得到匹配。结论仅限于纯ε-DP Laplace矩阵机制及两种平方误差准则,不适用于非矩阵连续机制、近似DP灵敏度或跨坐标期望最大值。该工作为差分隐私连续计数问题提供了严格的复杂度刻画,对设计最优隐私预算分配具有理论指导意义。

💡 推荐理由: 该成果精确刻画了纯DP连续计数中矩阵机制的误差下界,为数据发布和统计查询的隐私预算分配提供了理论基准,有助于安全工程师评估差分隐私系统在连续监测场景下的效用-隐私权衡。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)