LAPRAS : Learning-Augmented PRivate Answering for linear query Streams.

Modern database workloads are highly predictable: query streams are dominated by recurring jobs and templates, even when their arrival order is not known in advance. This motivates a learning-augmented view of online differentially private (DP) analytics: can algorithms utilize predictions about *which* queries will occur to improve utility under a single global privacy budget, while remaining robust when predictions are wrong? We study online DP query answering, where a curator must answer a stream $Q$ of $S$ linear queries arriving in uniformly random order under privacy budget $(\epsilon,\delta)$. We present *LAPRAS*, which assumes access to an oracle that outputs a prediction set of queries likely to appear in the stream and uses it to guide privacy spending. LAPRAS answers predicted queries using the offline-optimal Matrix Mechanism and answers the remaining queries online from a residual budget. To pace spending across an unknown number of unpredicted queries, we introduce *Smooth Allocation*, which forms an unbiased stopping-time estimate $\widehat{B}$ from the first $T=\Theta(\log^2 S)$ unpredicted queries and continuously recalibrates per-query expenditure. Empirically, over two real datasets, we validate the intended consistency--robustness trade-off: LAPRAS achieves near-offline utility under high overlap and degrades gracefully to baseline-level performance when overlap is low.

Organizations want live dashboards over sensitive data, but privacy-protecting systems must add random noise so that a single person’s data is not revealed. This is hard when questions arrive one at a time because the system does not know which future questions it should save its limited privacy allowance for. Our work observes that many database workloads are not fully surprising: the same kinds of questions often recur. We introduce LAPRAS, a method that uses predicted future questions to prepare accurate private answers in advance, then serves those answers when they arrive. For unexpected questions, LAPRAS estimates how many surprises remain and smoothly rations the remaining privacy allowance. This lets the system benefit when predictions are good, while still behaving like a standard private online method when predictions are poor. On two real datasets, LAPRAS greatly reduced error when predicted and actual questions overlapped, including reductions from 193.4 to 14.3 on Adult and 181.2 to 17.1 on Gowalla. When predictions were wrong, its error stayed comparable to a baseline that ignores predictions. This could make private analytics systems more useful by giving organizations more accurate aggregate results without weakening formal privacy protection.