AI & ML
Online Allocation with Differential Privacy
arXiv cs.CR0 views
arXiv:2611.17554v1 Announce Type: new Abstract: We study private online allocation problems, where allocation decisions must satisfy differential privacy (DP) to protect sensitive user information while optimizing performance under limited resources. We first formalize differential privacy notions suited to different privacy requirements in online allocation and establish the fundamental performance limits of any algorithm under these definitions. Based on these insights, we propose PPOA, a privacy-preserving meta algorithm for online allocation, and establish sufficient conditions under which PPOA preserves Joint DP (JDP) or Local DP (LDP) while achieving asymptotically near-optimal performance. Building on these conditions, PPOA can be instantiated into a variety of concrete algorithms. In particular, we present the specific designs, which include PPOA-DMD that preserves JDP and LDP and PPOA-FTRL that preserves JDP. We analyze their performance under both adversarial and stochastic settings and characterize the fundamental trade-offs between DP and allocation performance. Finally, we demonstrate the superior performance of the proposed algorithms via numerical experiments on AI model routing in battery-powered edge systems.
Source:https://arxiv.org/abs/2611.17554PreviousI2C-GRPO: Insight Importance Checklist for Reinforcement Learning in a Multi-Agent DDoS Alert Triage WorkflowNextTractable Importance Sampling for Monte Carlo Privacy Accounting
Related posts
Cross-Benchmark Transfer from RL on Agentic Coding Tasks
0arXiv cs.SE
Programmable Distributions of Semantics-Preserving Variants for Evaluating Code Agents
0arXiv cs.SE
Kusner's conjecture on equilateral sets is false
0arXiv cs.NA
Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
0arXiv stat.ML
When Does On-Policy Interaction Help? Representational Tradeoffs in Value-Based Imitation Learning
0arXiv stat.ML
Disentangling Continuous-Time Latent Dynamics: Identifiability of Latent SDEs via Diffusion Shifts
0arXiv stat.ML