Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Overview: Privacy filters are probabilistic objects which allow one to study the composition of differentially private algorithms in a setting where the privacy parameters can be chosen adaptively. While filters have been constructed for the case of pure and approximate differential privacy, they have not been studied in the context of Renyi privacy. Moreover, there hasn’t been any study of individual privacy filters, objects which selectively drop elements out of the dataset when their privacy loss exceeds a certain preselected threshold.

This paper introduces Renyi privacy filters, objects providing theoretical guarantees for the composition of Renyi DP algorithms where the privacy rates can be chosen adaptively. In addition, the authors extend these filters to the individual level, allowing for selective removal of datapoints from the dataset in order to continue computation without exceeded a predetermined level of privacy. The authors provide a comparison of their privacy filters to others, showing significant closed-form improvement in several cases. Likewise, they provide experiments showing the application of individual privacy filters to private gradient descent.

main_review: Originality: While privacy filters are not original to this, the extension of the concept to Renyi DP is useful as many of the tightest analyses of common mechanisms rely on this form of privacy. The mathematical analysis does not leverage any new techniques, but it does provide a clean solution to the problem. Individual privacy accounting is novel and seems like an invaluable way of extending the number of computations which can be done on a dataset.

Quality: The paper is mathematically sound. Concepts are well motivated and rigorously presented. Some more investigation could have been done into using RDP filters to construct filters for approximate differential privacy, as this seems like one of the most promising applications of the results of the paper.

Clarity: The writing is mostly, and the paper flows well. Some sections (such as the experiments or applications to approximate DP) could have been further touched upon, as these really show the value of the theoretical contributions. Privacy loss is key to the paper, so perhaps it should be discussed more in the main body of the paper as opposed to the appendix.

Significance: The paper is the first to discuss Renyi filters, and leverages them to improve upon the original privacy filters found in [29]. 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

High-level Positives:
-	Constructing privacy filters for Renyi DP is very useful, as Renyi DP is used in many privacy accountants like those found in Tensorflow and PyTorch.
-	Likewise, the improvement over the original privacy filters in special cases (e.g. pure differential privacy) is impressive, especially given that the obtained bounds are (a) more readable, and (b) more closely match advanced composition.
-	The proofs are all clean and easy to follow, which helps make the presentation of Renyi Filters very clear.


High-level Negatives:
-	The proofs are mostly straightforward and do not introduce novel analysis techniques. The main mathematical arguments just apply standard results from martingale theory or standard conversion results between forms of privacy.
-	The use of Renyi Filters as approximate DP filters is very interesting. More comparisons would be valuable- even numerical ones if getting a closed form expression isn’t possible.

Additional Comments:

Section 1:
-	The problem is very well motivated, and the notions of filters, both at the individual and overall level are clear. Moreover, the relation to existing work is clear as well.


Section 3:
-	It might be useful to formally define the privacy loss in the body of the paper, as it is the key theoretical object used to prove results. Moreover, it is ultimately the object the filters are trying to control.
-	In the statement of Theorem 1, you state that the sequence of algorithms is of finite length, consisting of k algorithms. I think you can have it be of infinite length and still be able to apply the optional stopping Theorem in the proof.

Section 4:
-	You handle the case of pure differential privacy, but only provide an explicit bound for the case where all privacy parameters, e_t, are chosen to be the same in each round. I think it would be very informative to show more general cases to demonstrate superiority over the bounds found in Rogers et. al.
-	Pure privacy filters don’t immediately yield approximate privacy filters. There is a conversion cost necessary that can be quite large depending on the choice of privacy level epsilon. This wasn’t in the original version of [29], but more recent version have addressed this gap as an error was pointed out (such as the newest version on Arxiv I believe).

Section 5:
-	The experiments are interesting. Due to the fact the privacy filters allow you to change privacy levels based on previous algorithm outputs, it would be interesting to see if varying the privacy level as one goes would affect the convergence rate of gradient descent.

limitations_and_societal_impact: The authors do adequately address limitations. For instance, in the experimental section, they discuss that they often times only see limited empirical improvement using individual privacy accounting. Otherwise, the theoretical contributions generally improve on pre-existing results.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper carries out the “take suprema later” idea in DP. In particular, by moving the supremum over previous algorithm outputs and neighboring datasets outside of the expectation, they design a new filter for RDP that can potentially achieve savings in the DP parameters. As concrete evidences, they provide a theoretical result where a significant saving can be exploited from the sparsity, and a more practical one using MNIST showing that the saving is significant for suboptimal hyperparameters.
main_review: This paper carries out the “take suprema later” idea clealy. Their results are stronger and clearer than those in Rogers et al. I have many compliments regarding this in a previous review, so I will not repeat.

Compared to the previous version, the formal statement about sparsity is satisfying. This resolves one of the issues I posed. However, I am not fully convinced about the following issue.

The current presentation of Algorithm 3 doesn't reveal its computational cost. In particular, an expensive loop is presented using universal quantifier and summation. Although the authors remarks that SGD and minibatch does not save time with filtering, it would be easier for readers to see if it is revealed in the algorithm.

On the same issue, I still don't see the running time even in the appendix. If the experiment is run on very expensive machines that only big companies can afford and it takes significantly longer time than SGD, then the authors argument about "suboptimal hyperparameters are more common" is less convincing --- the computational resources can be spent two ways

1. Tune the hyperparameters really hard using SGD
2. Change SGD to the more expensive GD and put all the hope on the filter proposed in this paper

It requires further evidence that 1 is better than 2. In particular, I don't know why there are less experimental details in this version (appendix included) than the previous one.

Overall, I think it is a good paper. However, I'm very eager to hear the authors response. I'd love to change my score if I misunderstood.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 
      The paper proposes an individual privacy accounting via a Renyi filter. In their algorithm, each data point maintains a fixed privacy budget; The privacy filter will adaptively drop points once their personalized privacy loss exceeds the budget. The authors provide a tighter analysis of privacy loss composition by tracking the associated divergences at an individual level. 
 

main_review: Weak points and question:
I have a question about the experiments. When the epsilon increases, the gain of using the filter decreases. I am wondering if the benefits of the privacy filter will decrease in the low-privacy regime? 

Strengths:

1. Their Renyi DP-based individual privacy filter is of huge potential usefulness to the Federated learning community. For example, their private gradient descent example can be generalized to the federated setting where each client can maintain a privacy budget. 

2. They provide a new adaptive composition theorem for RDP, which allows a sequence of adaptively chosen privacy parameters during the training. 

3. The related work section is helpful. The authors thoroughly compared their work to other personalized DP/data-dependent DP.   
limitations_and_societal_impact: The authors have addressed the potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper present a fully adaptive composition theorem for the Renyi differential privacy that bounds the overall privacy loss by the personalized privacy losses of all data points. The proposed adaptive composition theorem generalizes the vanilla composition theorem for Renyi differential privacy. The individual privacy accounting is designed as a privacy filter, which monitors the individual privacy loss across all individuals and time to make sure that the data points are dropped when cumulative privacy loss is about to violate the privacy budgets. Besides the theoretical guarantees, the training procedure via DP-stochastic gradient descent is also discussed on how to incorporate individual privacy filtering. Empirical study on MNIST dataset also shows improvements on the proposed privacy filtering method.
main_review: 1. Vanilla accounting approaches are too conservative and those harm the accuracy (utility); therefore, the proposed individual accounting approach aims to improve this shortcoming. In Section 4.2, the authors provide a scenario on high-dimensional linear queries where individual accounting leads to better privacy-utility tradeoff. The key is to compare the privacy budget in the worst-case RDP and that in the individual accounting. In particular, when the max norm of $q_t$ is larger than $\sum_{j=1}^t\|q_j(X_i)\|_2^2$ (i.e., each user’s responses are sparse). In high-dimensional setting, it is possible. However, a query function is not usually high-dimensional and this scenario does not seem to be practical. Is there other more practical scenarios where the advantages of individual accounting can be theoretically proven? What are the general scenarios where the individual accounting will outperform vanilla accounting?

2. When the learning model is carefully tuned, the privacy budgets are all spent and therefore in the empirical study on MNIST in Section 5.1, the improvement with filtering is very marginal comparing to GD (tuned). In most machine learning settings, the neural networks are perfectly tuned. The empirical study did not show the cases when it is hard to perfectly tuned the network parameters, e.g., distributed learning, transfer learning. To me,  the experiments are not sufficient to support the claims made in the Introduction.

3. The paper uses a lot of space on Renyi-DP, but there is no empirical study on RDP in the experiments. How does different $\alpha$  in RDP affects the performance of the filtering?

4. The authors emphasize that GD is more computationally efficient comparing to private SGD and batch GD. A more thorough discussion is needed and run time reported. 

5. It will be great to show the decision made by the Renyi filter in the experiments, e.g., when to continue and when to halt. 

6. When the network weights are suboptimal, the Renyi filter improve the performance. Are the queries sparse in this case?
limitations_and_societal_impact: Personalized DP is a very important and practical topic in designing a DP mechanism, since the vanilla DP guarantee is often too pessimistic. There is not potential negative societal impact presented in this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes to track each individual's privacy loss when applying mechanisms to a database to preserve Renyi DP, instead of using the worst-case privacy budget as in the common composition.
More experiments and discussions are needed to support claims in the abstract.
main_review: Strengths:
- The idea of giving a tighter bound for privacy by considering each individual is appealing at the first glance
- The extension to the adaptive case is natural, and the algorithm proposed has a simple form in the linear response situation

Weakness:
- The work aims to allow more responses with the same privacy guarantee since the previous bound is conservative. However, the experiment results are not strongly supportive of its effectiveness. More experimental evidence is definitely needed.
- How to deal with the batch update? Is it worth exploiting the individual privacy loss?
- It would be interesting to compare it with the local differential privacy
- Minor problems with the notation and concepts, say, what's the point of Definition 2.5? Also, the Algo. 3 uses a different mechanism as before.
limitations_and_societal_impact: addressed
review_title: null

Meta-review: This paper provides new results for (differential) privacy filters that ensure that the individual privacy loss does not exceed certain thresholds. This is an important question in differentially private machine learning, and the paper gives non-trivial technical contributions. During the discussion, reviewers raised some questions regarding the experiments. The authors should provide further details about their experimental setup in the next revision.
Decision: Accept (Poster)