← 研踪 PaperTrailarXiv:2605.02319 · v2
Optimal Privacy-Utility Trade-Offs in LDP: Functional and Geometric Perspectives
首次提交 2026-05-04 16:15
版本更新 2026-11-11 19:20
雷达观测 2026-11-13 14:16
摘要
Local differential privacy (LDP) has emerged as a gold-standard framework for privacy-preserving data analysis. However, characterizing the optimal privacy-utility trade-off (PUT) and the corresponding optimal LDP channels remains largely fragmented, relying on problem-specific, case-by-case analyses. In this work, we develop a unified theoretical framework that systematically characterizes the optimal PUT and optimal LDP channels for general privacy-preserving statistical decision-making problems. We first identify key functional properties of Bayesian and minimax risks as functions of the LDP channel, including the data processing inequality (DPI), direct-sum quasi-convexity (or additivity), concavity, and symmetry invariance. Leveraging these properties, we reduce the optimization domain required to compute the optimal PUT. To this end, we reinterpret the existing result implying the one-to-one correspondence between maximal LDP channels under the Blackwell order and a finite-dimensional polytope, through an alternative convex geometric derivation. This result renders the optimal PUT computationally tractable via vertex enumeration or linear programming. Furthermore, when the underlying problem exhibits symmetries characterized by a transitive group action, we show that the optimal PUT can be computed by comparing finitely many values, rather than optimizing over a high dimensional polytope. Our framework applies broadly beyond risk minimization, encompassing the maximization of information-theoretic measures. We demonstrate the efficacy of our theoretical framework by recovering or strengthening several known results, and deriving exact analytic expressions for the optimal PUTs in specific tasks that were previously unaddressed.
作者备注：20 pages, 2 figures. Compared to v1, relevant references have been newly added
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-11 19:20 · 最新观测版本
Optimal Privacy-Utility Trade-Offs in LDP: Functional and Geometric Perspectives
Local differential privacy (LDP) has emerged as a gold-standard framework for privacy-preserving data analysis. However, characterizing the optimal privacy-utility trade-off (PUT) and the corresponding optimal LDP channels remains largely fragmented, relying on problem-specific, case-by-case analyses. In this work, we develop a unified theoretical framework that systematically characterizes the optimal PUT and optimal LDP channels for general privacy-preserving statistical decision-making problems. We first identify key functional properties of Bayesian and minimax risks as functions of the LDP channel, including the data processing inequality (DPI), direct-sum quasi-convexity (or additivity), concavity, and symmetry invariance. Leveraging these properties, we reduce the optimization domain required to compute the optimal PUT. To this end, we reinterpret the existing result implying the one-to-one correspondence between maximal LDP channels under the Blackwell order and a finite-dimensional polytope, through an alternative convex geometric derivation. This result renders the optimal PUT computationally tractable via vertex enumeration or linear programming. Furthermore, when the underlying problem exhibits symmetries characterized by a transitive group action, we show that the optimal PUT can be computed by comparing finitely many values, rather than optimizing over a high dimensional polytope. Our framework applies broadly beyond risk minimization, encompassing the maximization of information-theoretic measures. We demonstrate the efficacy of our theoretical framework by recovering or strengthening several known results, and deriving exact analytic expressions for the optimal PUTs in specific tasks that were previously unaddressed.
查看此版本解读 →查看此版本原文 ↗