@article{22102,
  abstract     = {Differential privacy (DP) has established itself as one of the standards for ensuring privacy of individual data. However, reasoning about DP is a challenging and error-prone task, hence methods for formal verification and refutation of DP properties have received significant interest in recent years. In this work, we present a novel method for automated formal refutation of є-DP. Our method refutes є-DP by searching for a pair of inputs together with a non-negative function over outputs whose expected value on these two inputs differs by a significant amount. The two inputs and the non-negative function over outputs are computed simultaneously, by utilizing upper expectation supermartingales and lower expectation submartingales from probabilistic program analysis, which we leverage to introduce a sound and complete proof rule for є-DP refutation. To the best of our knowledge, our method is the first method for є-DP refutation to offer the following four desirable features: (1) it is fully automated, (2) it is applicable to stochastic mechanisms with sampling instructions from both discrete and continuous distributions, (3) it provides soundness guarantees, and (4) it provides semi-completeness guarantees. Our experiments show that our prototype tool SuperDP achieves superior performance compared to the state of the art and manages to refute є-DP for a number of challenging examples collected from the literature, including ones that were out of the reach of prior methods.},
  author       = {Chatterjee, Krishnendu and Kafshdar Goharshadi, Ehsan and Zikelic, Dorde},
  issn         = {2475-1421},
  journal      = {Proceedings of the ACM on Programming Languages},
  keywords     = {Static Program Analysis, Differential Privacy, Probabilistic Programming, Martingales},
  number       = {PLDI},
  publisher    = {Association for Computing Machinery},
  title        = {{SuperDP: Differential privacy refutation via supermartingales}},
  doi          = {10.1145/3808296},
  volume       = {10},
  year         = {2026},
}

@inproceedings{22146,
  abstract     = {We study differentially private model training with stochastic gradient descent under learning rate scheduling and correlated noise. Although correlated noise, in particular via matrix factorizations, has been shown to improve accuracy, prior theoretical work focused primarily on the prefix-sum workload. That workload assumes a constant learning rate, whereas in practice learning rate schedules are widely used to accelerate training and improve convergence. We close this gap by deriving general upper and lower bounds for a broad class of learning rate schedules in both single- and multi-epoch settings. Building on these results, we propose a learning-rate-aware factorization that achieves improvements over prefix-sum factorizations under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient constructions suitable for practical deployment, and experiments on CIFAR-10 and IMDB datasets confirm that schedule-aware factorizations improve accuracy in private training.},
  author       = {Kalinin, Nikita and Andersson, Joel D},
  booktitle    = {7th Symposium on Foundations of Responsible Computing},
  isbn         = {9783959774192},
  issn         = {1868-8969},
  keywords     = {differential privacy, machine learning, matrix factorization},
  location     = {Cambridge, MA; United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Learning rate scheduling with matrix factorization for private training}},
  doi          = {10.4230/LIPIcs.FORC.2026.2},
  volume       = {368},
  year         = {2026},
}

@article{22318,
  abstract     = {Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously
over a long period of time, making more statistical releases as either queries come in or the dataset is updated.
In this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that
support dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion
of neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition
theorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries
and dataset updates to the different composed mechanisms. Previous concurrent composition theorems for
differential privacy were only for the case when the dataset is static, with no adaptive updates. We also give
the first interactive and continual generalizations of the “parallel composition theorem” for noninteractive
differential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem
holds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure
differential privacy, but it fails to hold for composing approximately differentially private mechanisms with
dataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent
filter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We
extend these results to other measures of differential privacy, including Rényi DP and 𝑓 -DP.
We then formalize a set of general conditions on a continual mechanism M that runs multiple continual submechanisms such that the privacy guarantees of M follow directly using the above concurrent composition
theorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular
privacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the
case of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.
We also provide a framework that simplifies the analysis of local differential privacy when the protocol
includes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core
decomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5].},
  author       = {Henzinger, Monika H and Safavi Hemami, Roodabeh and Vadhan, Salil},
  issn         = {2836-6573},
  journal      = {Proceedings of the ACM on Management of Data},
  keywords     = {differential privacy, concurrent composition, continual release, continual observation, data streaming, continual mechanisms, concurrent parallel composition, concurrent filter composition},
  number       = {2},
  pages        = {1--26},
  publisher    = {Association for Computing Machinery},
  title        = {{Concurrent composition for differentially private continual mechanisms}},
  doi          = {10.1145/3801895},
  volume       = {4},
  year         = {2026},
}