Private online allocation gets a meta-algorithm: PPOA adds noise to budgets and duals while keeping competitive ratios near the non-private ceiling
Synopsis
In online allocation, a shared budget turns one request's decision into a side channel on other users' contexts, while standard differential privacy barely lets an algorithm adapt actions to context. PPOA treats the remaining budget and the Lagrangian dual variable as the coordination quantities to privatize, and gives sufficient conditions for meeting budget constraints with asymptotically near-optimal performance under joint or local differential privacy. Of its two instantiations, PPOA-FTRL reaches a 0.834 competitive ratio when only joint privacy is required, and PPOA-DMD reaches 0.665 while satisfying both privacy notions.
Interpretation
A resource budget couples decisions across requests, so the allocation one user sees reveals earlier users' contexts; PPOA makes the coordination quantities in that coupling the object of privacy protection rather than treating the action output as the only thing to hide. Earlier jointly private resource-allocation work either handled offline convex objectives or gave an online algorithm under a random-arrival model, and neither covered worst-case competitive guarantees holding uniformly over all context sequences. On the RouterBench battery-powered edge AI model-routing task, PPOA-DMD, which satisfies both joint and local differential privacy, reaches a 0.665 competitive ratio and 0.801 average normalized reward, against 0.635 and 0.778 for NDMD under the same two privacy notions.
Each round, the algorithm pre-selects an action from the clean context, the privatized dual variable and the privatized remaining budget, then projects that action inside a conservative budget obtained by subtracting a reserved margin from the privatized budget, so it stays within budget with high probability despite the noise. Applying noisy dual mirror descent directly lets unbounded noise accumulate over time and breaks the worst-case guarantee; PPOA-DMD instead uses a projected dual mirror descent with a norm bound, and PPOA-FTRL releases cumulative budget consumption through a tree-aggregation mechanism. When only joint differential privacy is required, tree-aggregation-based PPOA-FTRL reaches a 0.834 competitive ratio and 0.879 average normalized reward on RouterBench, above NFTRL at 0.597 and 0.726 and above PPOA-DMD at 0.665 and 0.801.
Perspective
The scope is budget-constrained online allocation, with experiments on the RouterBench battery-powered edge AI model-routing task and the iPinYou online advertising bidding task, at default privacy parameters using a small relaxation and a privacy budget between 1 and 10. The guarantees are asymptotic: the competitive ratio holds in probability, and regret is sublinear under i.i.d. arrivals.
The authors note that the established bounds are not proved best in their scaling with privacy level, and that room remains to improve them toward almost-sure asymptotic or non-asymptotic forms. Under non-stationary contexts the asymptotic competitive ratio in probability still holds, but sublinear expected regret needs additional assumptions. Experiments also show that as the privacy budget tightens further, allocation performance becomes very weak for all methods.
