Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an empirical evaluation of differential privacy parameter epsilon in federated learning setting. It does so by inserting canaries and seeing if it can determine the presence of these canaries in the model after each round update. It then uses this to estimate per round epsilon.
strength_and_weaknesses: Strengths:
- it seems to be one of the first works to look into empirical epsilon estimate in FL
- the method is intuitive and based on examples that would cause worst case clipping

Weaknesses:
- DP guarantees are not explained well (i.e., is epsilon per user or overall epsilon, how doe shuffling come into play)
- it is not clear how the work is different from that of empirical estimation of epsilon in central setting (i.e., previous work in this space)
clarity,_quality,_novelty_and_reproducibility: The approach is presented well.
It would help to show more details on how real/theoretical epsilon is computed. The authors mention that they compute RDP over rounds but it requires more details to show how shuffling and sampling is accounted for compared to FedAvg with DP work.
It would be also good to explain why previous works that estimate epsilon empirically cannot be used in Federated setting. And similarly can the canary approach suggested here be used for centralised setting?
summary_of_the_review: The paper considers an important problem but it is unclear how it is different from previous work on estimating epsilon in centralised setting and where those methods would fail.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces CANIFE, a method for auditing the empirical privacy guarantees of federated learning algorithms. In short, CANIFE does the following: It considers a canary client with a single data point that contributes in k "frozen" rounds, and doesn't contribute in k other  "frozen" rounds (frozen means the global model update is computed but not applied). The data point is chosen to be as out-of-distribution as possible, using a small number of held out examples from the data distribution; in particular, the authors propose a loss function over the data domain whose optimizers should be data points whose gradient is orthogonal to the gradients of the held out examples, and as large in norm as possible. One can then compute an "attack score", equal to the dot product of the aggregated round update and the canary client's computed update. Comparing the attack scores for each set of k rounds, one can look at a hypothesis test for detecting the canary based on thresholding the attack score, and compute a per-round empirical (epsilon, delta)-DP for all delta using the false positive/negative rates of this test, which can be used to estimate the privacy guarantee of the whole algorithm. The authors argue this is an effective empirical auditing scheme since the adversary is much less power than an information theoretic one (e.g., no knowledge of the other data samples participating in a round, can only generate adversarial data points rather than adversarial model updates), but still has more power than an adversary in practice (e.g., has access to held out examples, gets to participate in multiple rounds).

The authors perform experiments auditing federated model training using CANIFE. The authors show that for a simple CIFAR10 training setup where every client has one example, the noise multiplier corresponding to the difference between the distributions of attack scores is a very good estimate of the actual noise multiplier used in training. For more realistic setups, the authors consider the CelebA, Sent140, and Shakespeare tasks and compute empirical epsilon values using CANIFE. The authors compute empirical epsilons varying from 4-7 for theoretical epsilons of 10, 30, 50.
strength_and_weaknesses: The main strength of the paper is the approach of designing the CANIFE algorithm. I felt the authors did a good job motivating the assumptions. The assumptions on the adversary do lie in a nice space where they are slightly more powerful than what is possible in practice, but still far-removed from an information theoretic adversary, and I haven't seen such a set of assumptions before. The assumption that one can only generate model updates from data points within the data domain rather than arbitrary model updates is especially a natural one. Furthermore, the method for designing canary data points rather than canary model updates is intuitive and elegant. Overall the method is lightweight and I think would be easy to apply in practice on a variety of federated model training algorithms. In addition, pending the caveats in the subsequent bullet points, I think the experiment results convey an interesting message, that a slightly powerful adversary still exhibits a reasonably large separation between its empirical privacy guarantees and the theoretical ones.

I think a main weakness of the paper is that it seems to assume both in the algorithm's motivation, design, and in the experiments that the federated model update computed by a client with a single data point would be a rescaling of the gradient of the model sent to the client on that data point. However, this isn't necessarily true if e.g. clients do multiple epochs of training over their local data (and if the canary is acting honestly given the data, which seems to be an important assumption in the paper). The ability for clients to do multiple passes over their dataset is a key feature of federated learning (e.g. if one looks at McMahan et al. 2016, Figure 3, one sees that multiple passes actually can improve the training process if communication costs are the primary bottleneck). Since the loss CANIFE optimizes to choose its canary and the discussion in the paper (including e.g. the experiments) are based on this assumption, while CANIFE could still be applied to auditing central training methods or simple federated algorithms like FedSGD or FedAvg restricted to clients doing 1 epoch (for which this assumption does hold), it's unclear to me that CANIFE is an appropriate method for auditing even FedAvg in general. One thing that confuses this point for me is that in the experiments section, "epoch" seems to refer to a pass over the clients rather than a pass by the clients over their dataset. So it's unclear if clients are using one or multiple epochs in the experiment. One could perhaps show that the update generated by multiple client epochs has a large dot product with the initial gradient, in which case perhaps having the initial gradient be orthogonal is a good heuristic choice.

Also, it seems the RDP accountant was used for the theoretical epsilons, which as the authors mention is not tight if subsampling is used (which I believe is the case in the experiments), so the gap between the empirical and theoretical epsilons could be tightened by using a tighter accounting scheme to lower the theoretical epsilon (One might argue that clients in practice do not appear uniformly at random, but in that case one should prefer an algorithm like DP-FTRL anyway, I think). I think it is unlikely that e.g., entire gap would be closed, but I think part of the message of the paper (empirical epsilons are much smaller than theoretical epsilons, even for an adversary that is stronger than is practical) is weakened since this message is vacuously true if the theoretical epsilon is far from tight.
clarity,_quality,_novelty_and_reproducibility: As mentioned above, I have some questions about the quality of the algorithm proposed in the paper as it pertains to multi-client-epoch algorithms, as well as the experimental comparisons made.

I think the motivation of the paper is clearly explained and the algorithm is easy to understand, but as mentioned above, there are some seemingly implicit assumptions and parts of the experimental setup that I was unable to fully understand by reading the paper.

As mentioned above, the assumptions the authors place on the adversary in the auditing scheme, and in turn the auditing problem setting, are I believe novel.
summary_of_the_review: Overall, I lean towards rejecting the paper due to the aforementioned concerns. I think the paper carries a very nice message, that by using constrained adversaries we can get more reasonable practical epsilon estimates, and the problem of optimizing over data points in a canary is a very interesting one. But the fact that the paper seems tailored to single-client-epoch algorithms and uses a suboptimal accountant for its theoretical bounds makes it hard to discern if CANIFE is broadly applicable to a variety of federated learning algorithms, and how much of the gap in empirical and theoretical epsilons is due to a suboptimal accountant. So while I really like the ideas in the paper, it's hard to be confident in their level of impact. Furthermore, I think since the paper is breaching into a somewhat new space (so e.g., it is unclear if the problem setup will still be interesting in a few years, it's unclear how the empirical results would compare to other approaches), it needs to be held to a somewhat higher standard.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Motivated by the insight that DP budgets are conservative (i.e. a given budget overestimates the privacy/membership inference information that can be extracted realistically), this work designs a canary-based method to produce a more realistic estimate of the privacy budget in FL settings. The threat model is
- safe but cooperative server
- one rogue client
- access to public model weights once trained
- access to a public dataset ("design pool")
- access to public noisy model updates

The proposed method injects (or not) a canary data point in a given training round, computes scores using public noisy model updates, then aggregates per-round privacy estimates to global privacy estimates. The canary is obtained by a computationally cheap local SGD relying on the derivative of the loss wrt the canary value, holding model parameters fixed. 
strength_and_weaknesses: #Strengths

The privacy estimate provided by this method is practically useful as complement to a theoretical guarantee. The method is computationally accessible. The threat model is applicable in practice (though it looks to me as though client samples are wasted during training rounds ran for the purpose of the method). 

The paper is remarkably well written, well structured, self-contained but with useful extra detail in the appendices. Experimental details, including other software libraries, datasets, other methods are detailed. Plots are clear, legible, to the point. Notation, nomenclature, external references are all unambiguous and helpful. 

#Weaknesses

The proposed method seems to be limited intrinsically, probably like other methods with the same purpose: it requires a very specific protocol to be applied, and will return the specific privacy measurement corresponding to its threat model. However, complete practical privacy measurements presumably require multiple such methods, under varied threat models eg Nasr+ 2021, to form a complete picture as a counterpoint to the theoretical DP guarantee. 

The threat model might be demanding, especially the availability of public data (design pool) and cooperative clients and servers. 

Experiments are limited to classification tasks.

Looking hard for weaknesses, one could wish for the paper to be more overt about the method's shortcomings and limitations. 
clarity,_quality,_novelty_and_reproducibility: #Clarity and reproducibility

As mentioned under Strengths, the paper gives an excellent account of the method's motivation, implementation details and choices (paired with analytic experiments). Experiments are documented thoroughly. Standard software libraries and datasets are used to implement the experiments, which supports reproducibility. 

#Novelty

The approach is novel in that it brings in the idea of the canary, known from different settings, to carry out a task in the DP-FedAvg setting, empirical privacy determination. This task is usually achieved quite differently. 

#Quality

The work is of high quality. Many non-trivial technical steps had to be solved for the overall method to work. The experimental design is very complete and addresses all necessary aspects. The analysis is accurate, informed, state-of-the-art. 
summary_of_the_review: The paper is very good and has very few flaws, if any. It addresses a problem of practical importance, comes up with a relatively simple, general solution which solves the problem in many cases. Therefore its impact can be expected to be strong.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed CANIFE for measuring the empirical privacy loss under looser assumptions about the adversary’s capability compared to differential privacy (DP). CANIFE generates worst-case data samples in federated learning (FL) such that the gradients of such samples are orthogonal to most of the model updates from other participants, and from which the adversary can tell whether such outliers participated in training or not in each round. The authors evaluated the effectiveness of CANIFE on benchmark image and text datasets and showed that DP overestimated the privacy by 2 to 7 times. 

strength_and_weaknesses: Strength 

1. The paper is well-motivated as currently training large models with DP has non-negligible impact on utility and it is less understood whether such strong guarantees are necessary under more realistic settings. This paper could be useful for developing more practical private learning algorithms.
2. The paper is well-written and easy to follow, and the proposed algorithms are straightforward and simple to implement.
The evaluation is done on multiple image and text datasets demonstrating the effectiveness of the proposed approach. 

Weakness

1. Although the author mentioned a few existing empirical privacy loss estimation approaches, there is no empirical comparison between this work and prior works. For example, would any of the settings in Milad et al [1] be comparable with CANIFE, in terms of privacy loss estimation and attack efficiency? 
2. The main goal of the paper is to monitor empirical privacy during FL training while one limitation is that one has to have a good Design Pool (i.e. held-out data in the experiments) to simulate the other clients for a more accurate measurement. If the design pool is very different from the real distribution, then the measurement could be overly optimistic. However, in many real FL applications, there is no held-out data available since these are also sensitive data on device, and having an accurate design pool might be hard to achieve. The paper would be stronger if the authors also provided methods to generate a design pool when no held-out data are available yet the privacy measurement is tight. Relatedly, the distribution assumption about the design pool is also not rigorously defined.

References:

[1] Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papemoti, and Nicholas Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 866–882. IEEE, 2021.

clarity,_quality,_novelty_and_reproducibility: The clairity of this paper is good in terms of explaining the threat model and the algorithms, and the experiments are well-executed. The proposed CANIFE is original. Though there is no link to the code, the implementation should be straightforward from the pseudo code and all necessary hyperparameters are provided and I believe the results should be reproducible.

summary_of_the_review: Overall I think it is a good paper despite the weakness mentioned above.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper designs a relatively strong way to audit the privacy property of training a model via SGD in FL. It shows how an adversary can design an example that will lead to a model update with certain properties aimed at maximizing the probability of detecting the update in the final model. They demonstrate that this auditing leads to privacy levels several times stronger than those implied by theoretical DP guarantees.  One of the new and useful aspects of this work is that it creates actual inputs to the model and not just the gradient. 
This is useful progress in a line of work on auditing which aim to establish "empirical epsilon" (arguably, a rather misleading name). It's main weakness is that it is naturally geared toward a rather specific training scheme and specific distinguishing test. 
justification_for_why_not_higher_score: Well executed but not particularly novel ideas
justification_for_why_not_lower_score: Strong support from two reviewers one of whom works in this area.
Decision: Accept: poster