Are Normalizing Flows the Key to Unlocking the Exponential Mechanism?

Overview

• The Exponential Mechanism (ExpM) is a technique for private optimization, but has historically been difficult to use on continuous sample spaces.
• This paper proposes a method called ExpM+NF that uses a Normalizing Flow (NF) to approximate sampling from the ExpM density, making it more practical for private machine learning (ML) tasks.
• The paper also proves a sensitivity bound for the L2 loss, enabling ExpM to be used with any sampling method.
• Experiments on MIMIC-III health data show that ExpM+NF can achieve accuracy close to non-private SGD, outperform Differentially Private SGD (DPSGD), and train faster.
• The paper also investigates the privacy properties of ExpM+NF empirically, finding it provides more privacy than non-private SGD, but less than DPSGD.

Plain English Explanation

The Exponential Mechanism (ExpM) is a technique used to keep data private when optimizing machine learning models. However, it has historically been tricky to use with continuous data, as it requires sampling from a complex probability distribution that is hard to work with.

This paper proposes a new approach called ExpM+NF that solves this problem. It uses a Normalizing Flow (NF), a type of deep neural network, to approximate the sampling process. This makes ExpM much more practical for private machine learning tasks.

The paper also proves a useful mathematical result, showing that the ExpM technique can be used with any sampling method as long as you can bound the sensitivity of the objective function (in this case, the L2 loss).

To test their approach, the researchers applied ExpM+NF to a healthcare dataset called MIMIC-III. They found that the method can achieve accuracy close to standard, non-private training, and outperform the popular Differentially Private SGD (DPSGD) approach, while also training faster.

The paper also looked at the privacy properties of ExpM+NF. They found it provides more privacy than non-private training, but not as much as DPSGD. However, many common privacy attacks were not effective against any of the models.

Overall, this work makes important progress in making the ExpM technique more usable for real-world private machine learning, with benefits in terms of accuracy, training speed, and privacy. It also provides some helpful theoretical results and empirical insights about the limitations of privacy evaluation.

Technical Explanation

The key technical contribution of this paper is the ExpM+NF method, which combines the Exponential Mechanism (ExpM) for private optimization with a Normalizing Flow (NF) to enable practical sampling from the ExpM density.

ExpM is a powerful private optimization technique, but has historically been challenging to use on continuous sample spaces, as it requires sampling from a generally intractable density. This paper proposes using an auxiliary NF model to approximately sample from the ExpM density, making it much more practical for private machine learning tasks.

The paper also proves a sensitivity bound for the L2 loss function, which enables ExpM to be used with any sampling method, not just the NF approximation.

To evaluate the approach, the authors conducted experiments on the MIMIC-III healthcare dataset. They compared the accuracy and training time of ExpM+NF to standard (non-private) SGD and the popular DPSGD method. They found that ExpM+NF achieved accuracy close to non-private SGD, outperformed DPSGD, and trained faster.

While the paper was unable to provide a formal privacy proof for the NF approximation, the authors conducted empirical privacy evaluations. They found that ExpM+NF provides more privacy protection than non-private SGD, but less than DPSGD. However, many state-of-the-art privacy attacks were ineffective against all the models.

Overall, this work makes important advances in making the ExpM technique more practical and useful for real-world private machine learning applications, with benefits in terms of accuracy, training efficiency, and empirical privacy guarantees.

Critical Analysis

The main limitation of this work is the lack of a formal privacy proof for the NF approximation used in ExpM+NF. While the empirical privacy evaluations are informative, a rigorous theoretical analysis would be ideal to fully understand the privacy properties of the method.

Additionally, the paper acknowledges that the NF model may not be able to perfectly approximate the ExpM density, which could introduce some error or suboptimal behavior. Further research is needed to characterize the impact of this approximation on the overall performance and privacy of the technique.

The paper also highlights the challenges of empirical privacy evaluation, noting that many state-of-the-art attacks were ineffective against all the models tested, including the non-private baseline. This raises questions about the reliability and comprehensiveness of such empirical approaches, and suggests the need for continued advancements in privacy auditing methodologies.

Despite these limitations, the work represents an important step forward in making the ExpM technique more practical and accessible for private machine learning. The theoretical results, empirical findings, and insights provided in the paper contribute valuable knowledge to the field and lay the groundwork for future research in this area.

Conclusion

This paper presents a novel method called ExpM+NF that combines the Exponential Mechanism (ExpM) for private optimization with a Normalizing Flow (NF) to enable practical sampling from the ExpM density. The authors prove a sensitivity bound for the L2 loss, allowing ExpM to be used with any sampling method, and demonstrate the effectiveness of ExpM+NF on the MIMIC-III healthcare dataset.

While the paper was unable to provide a formal privacy proof for the NF approximation, the empirical results suggest that ExpM+NF offers more privacy protection than non-private training, but less than the popular Differentially Private SGD (DPSGD) approach. The work also highlights the limitations of current empirical privacy evaluation methods.

Overall, this research represents an important advance in making the ExpM technique more accessible and useful for real-world private machine learning tasks, with benefits in terms of accuracy, training efficiency, and empirical privacy guarantees. The findings and insights provided in the paper will likely spur further developments in this active area of research.