隐私线性回归的复杂度由协方差矩阵的L1版本决定，非传统方法。
Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression
- 用L1型协方差替代传统协方差分析隐私下回归复杂度
- 提出信息加权回归法，达到最优收敛速率
- 适用于需高隐私保障的在线决策场景
我们研究了在未知且可能病态条件下的协变量分布下，隐私线性回归的统计复杂度。令人意外的是，在隐私约束下，内在复杂度并非由常规协方差矩阵刻画，而是由其L1类比形式决定。基于此洞见，我们建立了中心化与本地化隐私模型下的极小极大收敛率，并提出一种信息加权回归方法，实现了最优率。作为应用，在私有线性上下文老虎机中，我们设计了一种高效算法，分别在联合与本地α-隐私模型下实现了√T + 1/α 和 √T/α 的率最优后悔界。值得注意的是，我们的结果表明联合隐私几乎无额外代价，解决了Azize与Basu（2024）提出的开放问题。
原文摘要 · Abstract (English)
We study the statistical complexity of private linear regression under an unknown, potentially ill-conditioned covariate distribution. Somewhat surprisingly, under privacy constraints the intrinsic complexity is \emph{not} captured by the usual covariance matrix but rather its $L_1$ analogues. Building on this insight, we establish minimax convergence rates for both the central and local privacy models and introduce an Information-Weighted Regression method that attains the optimal rates. As application, in private linear contextual bandits, we propose an efficient algorithm that achieves rate-optimal regret bounds of order $\sqrt{T}+\frac{1}α$ and $\sqrt{T}/α$ under joint and local $α$-privacy models, respectively. Notably, our results demonstrate that joint privacy comes at almost no additional cost, addressing the open problems posed by Azize and Basu (2024).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。