Optimal Privacy-Utility Trade-Offs in LDP: Functional and Geometric Perspectives

• URL: http://arxiv.org/abs/2605.02319v1
• Date: Mon, 04 May 2026 08:15:48 GMT
• Title: Optimal Privacy-Utility Trade-Offs in LDP: Functional and Geometric Perspectives
• Abstract summary: Local differential privacy (LDP) has emerged as a gold-standard framework for privacy-preserving data analysis.<n>However, characterizing the optimal privacy-utility trade-off (PUT) and the corresponding optimal LDP channels remains largely fragmented.
• Score: 16.365424373632568
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. Additionally, building on convex geometric insights, we establish a one-to-one correspondence between maximal LDP channels under the Blackwell order and a finite-dimensional polytope, yielding an exact geometric characterization. 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 derive an exact analytic expression for the optimal PUT, leading to closed-form solutions without numerical optimization. Our framework applies broadly beyond risk minimization, encompassing the maximization of information-theoretic measures such as mutual information, $f$-divergences, and Fisher information over LDP channels. 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.

Related papers

• Preference Data Selection for Mitigating the Alignment Tax in Large Language Models [52.18310687523229]
  BALIGN is a balanced data selection strategy that mitigates catastrophic forgetting while optimizing alignment efficacy.<n>By aggregating three key data-centric features into a unified composite risk score, BALIGN systematically filters out high-risk preference samples.<n>Experiments on standard human preference datasets demonstrate that BALIGN strongly preserves foundational capabilities without compromising alignment gains.
  arXiv  Detail & Related papers  (2026-08-25T07:58:42Z)
• p-PSO: A Penalized Particle Swarm Optimization Technique for Finding D-Optimal Designs with Mixed Factors in Generalized Linear Models [0.0]
  We introduce a new, general-purpose penalty formulation for constrained optimization, named $p$-PSO.<n>Results show that the method is highly efficient, with its primary contribution being a penalty formulation that enables the direct use of an off-the-shelf PSO algorithm.
  arXiv  Detail & Related papers  (2026-06-14T18:43:29Z)
• Sequential Bayesian Optimal Experimental Design in Infinite Dimensions via Policy Gradient Reinforcement Learning [3.2580743227673694]
  High-fidelity approaches require repeated forward and adjoint PDE solves inside nested Bayesian inversion and design loops.<n>We formulate SBOED as a finite-horizon Markov decision process and learn an amortized design policy via policy-gradient reinforcement learning.<n> Numerical experiments on sequential multi-sensor placement for contaminant source tracking demonstrate approximately $100times$ speedup over high-fidelity finite element methods.
  arXiv  Detail & Related papers  (2026-01-09T15:44:49Z)
• Non-Asymptotic Analysis of Online Local Private Learning with SGD [17.5801604365356]
  Differentially Private Gradient Descent (DP-SGD) has been widely used for solving optimization problems with privacy guarantees in machine learning and statistics.<n>Despite this, a systematic non-asymptotic convergence analysis for DP-SGD, particularly in the context of online problems and local differential privacy (LDP) models, remains largely elusive.<n>This work initiates the analysis to bridge this gap and opens the door to non-asymptotic convergence analysis of private optimization problems.
  arXiv  Detail & Related papers  (2025-07-09T17:06:01Z)
• StablePCA: Learning Shared Representations across Multiple Sources via Minimax Optimization [8.525738573467732]
  When multisource high-dimensional data, a key objective is to extract low-dimensional feature representations that effectively approximate the original features across different sources.<n>We propose the Mirror Stable Principal ComponentPCA, a novel method for group distribution of multi-dimensional representations.<n>We demonstrate high-dimensional accuracy and efficiency in extracting robust low-dimensional representations across various finite-sample scenarios.
  arXiv  Detail & Related papers  (2025-05-02T00:53:39Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
  We study offline reinforcement learning (RL) in partially observable Markov decision processes. We propose the underlineProxy variable underlinePessimistic underlinePolicy underlineOptimization (textttP3O) algorithm. textttP3O is the first provably efficient offline RL algorithm for POMDPs with a confounded dataset.
  arXiv  Detail & Related papers  (2022-05-26T19:13:55Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  We consider potentially non- optimized approximation problems. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
  arXiv  Detail & Related papers  (2022-04-11T09:37:04Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Is Pessimism Provably Efficient for Offline RL? [104.00628430454479]
  We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. We propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function.
  arXiv  Detail & Related papers  (2020-12-30T09:06:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.