The Limits and Possibilities of One Run Auditing

One-run auditing offers a practical alternative to classical multi-run auditing for differential privacy. Instead of repeating an experiment many times for a single user, it involves guessing the participation of many users (canaries) within a single run of the algorithm. This approach is crucial for complex mechanisms like training large neural networks, where repeated full training runs are infeasible.

Two years ago, Thomas and Nasa came up with one-run auditing, basically they say instead of repeating many many times the auditing process of guessing a single user, repeat once the process of guessing many users. So now the setting is that we have we can either think of it as many elements each one independently we choose if it will participate or not or we can think of it as many many pairs and from each pair we sample randomly which of the two will be used. Again for the purpose of this talk it won't matter.

One-run auditing, while valid, is not 'tight' in the same way classical auditing is. Its 'looseness' stems from three main issues: 1) non-uniform privacy loss among elements (e.g., 'name and shame' where only one element is revealed), 2) reliance on a typical scenario rather than worst-case (e.g., 'all or nothing' mechanisms that rarely reveal information), and 3) interference between elements (e.g., XOR parity where elements are interdependent). These factors mean the auditor has partial knowledge and averages over individuals and outcomes, leading to a weaker privacy bound than the true worst-case epsilon.

The answer is absolutely not. So I'll give three toy examples but these two examples are not here to convince you that this is not a good auditing method because all three of them are very unnatural by definition they are here mostly to explain what are the three and to the best of our knowledge the only three sources of looseness in this method. So first example is think about name and shame... Second option is a mechanism which sometimes is called all or nothing... And the third example that is a bit more interesting is the parity or exor function.

Despite its theoretical looseness, one-run auditing works in practice because many machine learning mechanisms are more 'local' than they initially appear. In high-dimensional models, individual data elements can be effectively placed in orthogonal 'coordinates' within the model's parameter space. This minimizes interference between elements, allowing the auditor to distinguish their presence with greater accuracy, effectively mimicking a series of independent local mechanisms.

And the short answer is basically because many more mechanisms are local than it might seem at first. So here's an example... if you have enough coordinates, you can place each element in its own coordinate, in which case you're summing. You're effectively running a local mechanism because each element lives in its own coordinate and everything that happens with the rest of the elements has no effect on it.

One-run auditing can be significantly improved by allowing the auditor to be 'adaptive'—meaning it can observe the outcome of previous guesses and decide whether to guess or abstain on subsequent elements. This strategy allows the auditor to focus on elements where it has higher certainty, leading to a better overall success rate and tighter privacy bounds, especially when dealing with mechanisms where privacy loss is not uniform.

Now if we go over the proof carefully, we know that it's okay if the guesser is told if their previous guess was correct. That we called it adaptive one on auditing and and basically it's a slightly stronger guesser because it can't know the future but it can remember the past.

For blackbox auditing, where only the model's output is accessible, using smarter score functions beyond simple loss can dramatically improve results. By accessing the full gradient of the model parameters with respect to an input, auditors can lift elements from a low-dimensional input space to the very high-dimensional model parameter space. This high-dimensional representation can create better orthogonality between elements, reducing interference and enabling more accurate membership inference attacks or privacy audits.

But when you are in the one run auditing and your biggest problem is that you need to create some kind of orthogonality in that setting it might be the case that these gradients are the key because they sort of lift the elements from living in the like one-dimensional space of loss or maybe lowdimensional space of of inputs to the very high dimensional space of the model parameters.