summaries: This paper compares 3 kinds of performance predictors, model based predictors, learning curve based predictor and zero nas predictors. They benchmark the performance of all 31 predictors against 5 benchmarks: NAS-Bench101, DARTS, NASBench201 and NLP.  In addition to this, they also incorporate SOTL-E and jacobian variance as addition features to NGBOOST and SemiNAS predictors and demonstrate that it improves the performance over all 3 of them.

summaries: Neural Architecture Search (NAS) aims to find the network architectures with the best accuracies -- or best size/accuracy tradeoffs -- from within a human-defined search space. The submission evaluates a number of different heuristics for ranking different candidate architectures in a search space. The submission claims to evaluate 31 different techniques which fall into several categories (e.g., early stopping, learning curve extrapolation, supervised learning, one-shot models, zero-shot metrics). The submission claims that different techniques work better for different compute budgets (e.g., low setup cost/low search cost vs. high setup cost/high search cost). It also claims that combining techniques from different families (e.g., supervised learning + zero-shot metrics) can lead to better results than using any one technique on its own. Experimental results are reported on NASBench-101, NASBench-201, the NASBench-301/DARTS search space, and NASBench-NLP.

summaries: The paper give a large-scale comparison of performance predictors in NAS. The results act as recommendations for the best predictors to use in different settings. The author also show that certain families of predictors can be combined to achieve even better predictive power.

summaries: The authors identify and benchmark a plethora of recently proposed techniques for predicting neural network architecture performance on a task without doing a full training run.   They begin by grouping each technique into categories: model-based, learning-curve-based, zero-cost, and weight-sharing. When viewed like this it becomes clear that there is a need for a common benchmark to distinguish the performance of the different approaches.   To compare under one framework, evaluation is done with respect to two variables: initialization time (time spent preparing the model) and query time (time spent retrieving predictions from the model).  The authors then present their own method, OMNI, which performs NAS using a blend of model-based, learning-curve-based, and zero-cost predictors.

abstractText: Early methods in the rapidly developing field of neural architecture search (NAS) required fully training thousands of neural networks. To reduce this extreme computational cost, dozens of techniques have since been proposed to predict the final performance of neural architectures. Despite the success of such performance prediction methods, it is not well-understood how different families of techniques compare to one another, due to the lack of an agreed-upon evaluation metric and optimization for different constraints on the initialization time and query time. In this work, we give the first large-scale study of performance predictors by analyzing 31 techniques ranging from learning curve extrapolation, to weight-sharing, to supervised learning, to zero-cost proxies. We test a number of correlationand rank-based performance measures in a variety of settings, as well as the ability of each technique to speed up predictor-based NAS frameworks. Our results act as recommendations for the best predictors to use in different settings, and we show that certain families of predictors can be combined to achieve even better predictive power, opening up promising research directions. Our code, featuring a library of 31 performance predictors, is available at https://github.com/automl/naslib.

authors:
Mohamed S Abdelfattah
Abhinav Mehrotra
Łukasz Dudziak
Nicholas Donald Lane

title: Zero-cost proxies for lightweight nas

venue: In Proceedings of the International Conference on Learning Representations (ICLR),

authors:
Bowen Baker
Otkrist Gupta
Ramesh Raskar
Nikhil Naik

title: Accelerating neural architecture search using performance prediction

venue: arXiv preprint arXiv:1705.10823,

authors:
Matthias Bauer
Mark van der Wilk
Carl Edward Rasmussen

title: Understanding probabilistic sparse gaussian process approximations

venue: arXiv preprint arXiv:1606.04820,

authors:
Gabriel Bender
Pieter-Jan Kindermans
Barret Zoph
Vijay Vasudevan
Quoc Le

title: Understanding and simplifying one-shot architecture search

venue: In Proceedings of the International Conference on Machine Learning (ICML),

authors:
Eli Bingham
Jonathan P Chen
Martin Jankowiak
Fritz Obermeyer
Neeraj Pradhan
Theofanis Karaletsos
Rohit Singh
Paul Szerlip
Paul Horsfall
Noah D Goodman

title: Pyro: Deep universal probabilistic programming

venue: The Journal of Machine Learning Research,

title: Pattern recognition and machine learning

venue: springer,

authors:
Han Cai
Ligeng Zhu
Song Han

title: Proxylessnas: Direct neural architecture search on target task and hardware

authors:
Akshay Chandrashekaran
Ian R Lane

title: Speeding up hyper-parameter optimization by extrapolation of learning curves using previous builds

venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
Tianqi Chen
Carlos Guestrin

title: Xgboost: A scalable tree boosting system

venue: In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining,

authors:
Patryk Chrabaszcz
Ilya Loshchilov
Frank Hutter

title: A downsampled variant of imagenet as an alternative to the CIFAR

venue: datasets. CoRR,

authors:
Tobias Domhan
Jost Tobias Springenberg
Frank Hutter

title: Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves

venue: In Twenty-Fourth International Joint Conference on Artificial Intelligence,

authors:
Xuanyi Dong
Yi Yang

title: Searching for a robust neural architecture in four gpu hours

venue: In Proceedings of the IEEE Conference on computer vision and pattern recognition,

title: Nas-bench-201: Extending the scope of reproducible neural architecture search

authors:
Tony Duan
Avati Anand
Daisy Yi Ding
Khanh K Thai
Sanjay Basu
Andrew Ng
Alejandro Schuler

title: Ngboost: Natural gradient boosting for probabilistic prediction

venue: In International Conference on Machine Learning,

authors:
Thomas Elsken
Jan Hendrik Metzen
Frank Hutter

title: Neural architecture search: A survey

venue: arXiv preprint arXiv:1808.05377,

authors:
Stefan Falkner
Aaron Klein
Frank Hutter

title: Bohb: Robust and efficient hyperparameter optimization at scale

authors:
Kirthevasan Kandasamy
Willie Neiswanger
Jeff Schneider
Barnabas Poczos
Eric P Xing

title: Neural architecture search with Bayesian optimisation and optimal transport

venue: In Advances in Neural Information Processing Systems,

authors:
Guolin Ke
Qi Meng
Thomas Finley
Taifeng Wang
Wei Chen
Weidong Ma
Qiwei Ye
Tie-Yan Liu

title: Lightgbm: A highly efficient gradient boosting decision tree

venue: Advances in neural information processing systems,

title: Designing neural networks using genetic algorithms with graph generation system

venue: Complex systems,

authors:
Aaron Klein
Stefan Falkner
Jost Tobias Springenberg
Frank Hutter

title: Learning curve prediction with Bayesian neural networks

authors:
Nikita Klyuchnikov
Ilya Trofimov
Ekaterina Artemova
Mikhail Salnikov
Maxim Fedorov
Evgeny Burnaev

title: Nas-bench-nlp: neural architecture search benchmark for natural language processing

venue: arXiv preprint arXiv:2006.07116,

title: Learning multiple layers of features from tiny images

venue: Technical report, University of Toronto,

authors:
Namhoon Lee
Thalaiyasingam Ajanthan
Philip Torr

title: SNIP: Single-shot network pruning based on connection sensitivity

authors:
Liam Li
Kevin Jamieson
Afshin Rostamizadeh
Ekaterina Gonina
Moritz Hardt
Benjamin Recht
Ameet Talwalkar

title: A system for massively parallel hyperparameter tuning

venue: In Proceedings of the Conference on Machine Learning Systems,

authors:
Liam Li
Mikhail Khodak
Maria-Florina Balcan
Ameet Talwalkar

title: Geometry-aware gradient algorithms for neural architecture search

authors:
Liam Li
Ameet Talwalkar

title: Random search and reproducibility for neural architecture search

venue: arXiv preprint arXiv:1902.07638,

authors:
Lisha Li
Kevin Jamieson
Giulia DeSalvo
Afshin Rostamizadeh
Ameet Talwalkar

title: Hyperband: A novel bandit-based approach to hyperparameter optimization

venue: arXiv preprint arXiv:1603.06560,

authors:
Hanwen Liang
Shifeng Zhang
Jiacheng Sun
Xingqiu He
Weiran Huang
Kechen Zhuang
Zhenguo Li

title: Darts+: Improved differentiable architecture search with early stopping

authors:
Andy Liaw
Matthew Wiener

title: Classification and regression by randomforest

venue: R news,

authors:
Marius Lindauer
Katharina Eggensperger
Matthias Feurer
Stefan Falkner
André Biedenkapp
Frank Hutter

title: Smac v3: Algorithm configuration in python

venue: URL https://github

authors:
Marius Lindauer
Frank Hutter

title: Best practices for scientific research on neural architecture search

venue: arXiv preprint arXiv:1909.02453,

authors:
Hanxiao Liu
Karen Simonyan
Yiming Yang

title: Darts: Differentiable architecture search

venue: arXiv preprint arXiv:1806.09055,

authors:
Renqian Luo
Xu Tan
Rui Wang
Tao Qin
Enhong Chen
Tie-Yan Liu

title: Neural architecture search with gbdt

venue: arXiv preprint arXiv:2007.04785,

title: Semi-supervised neural architecture search

venue: In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS),

authors:
Renqian Luo
Fei Tian
Tao Qin
Enhong Chen
Tie-Yan Liu

title: Neural architecture optimization

authors:
Lizheng Ma
Jiaxu Cui
Bo Yang

title: Deep neural architecture search with deep graph Bayesian optimization

venue: IEEE/WIC/ACM International Conference on Web Intelligence (WI),

authors:
Krzysztof Maziarz
Andrey Khorlin
Quentin de Laroussilhe
Andrea Gesmundo

title: Evolutionary-neural hybrid agents for architecture search

venue: arXiv preprint arXiv:1811.09828,

authors:
Joseph Mellor
Jack Turner
Amos Storkey
Elliot J Crowley

title: Neural architecture search without training

venue: arXiv preprint arXiv:2006.04647,

title: Snip: Single-shot network pruning based on connection sensitivity

venue: GitHub repository gahaalt/SNIP-pruning,

authors:
Tomáš Mikolov
Martin Karafiát
Lukáš Burget
Jan Černockỳ
Sanjeev Khudanpur

title: Recurrent neural network based language model

venue: In Annual conference of the international speech communication association,

authors:
Xuefei Ning
Wenshuo Li
Zixuan Zhou
Tianchen Zhao
Yin Zheng
Shuang Liang
Huazhong Yang
Yu Wang

title: A surgery of the neural architecture evaluators

authors:
Xuefei Ning
Yin Zheng
Tianchen Zhao
Yu Wang
Huazhong Yang

title: A generic graph-based neural architecture encoding scheme for predictor-based nas

venue: arXiv preprint arXiv:2004.01899,

authors:
David Patterson
Joseph Gonzalez
Quoc Le
Chen Liang
Lluis-Miquel Munguia
Daniel Rothchild
David So
Maud Texier
Jeff Dean

title: Carbon emissions and large neural network training

venue: arXiv preprint arXiv:2104.10350,

authors:
Fabian Pedregosa
Gaël Varoquaux
Alexandre Gramfort
Vincent Michel
Bertrand Thirion
Olivier Grisel
Mathieu Blondel
Peter Prettenhofer
Ron Weiss
Vincent Dubourg

title: Scikitlearn: Machine learning in python

venue: Journal of machine Learning research,

authors:
Hieu Pham
Melody Y Guan
Barret Zoph
Quoc V Le
Jeff Dean

title: Efficient neural architecture search via parameter sharing

venue: arXiv preprint arXiv:1802.03268,

authors:
Joaquin Quiñonero Candela
Carl Edward Rasmussen

title: A unifying view of sparse approximate gaussian process regression

venue: J. Mach. Learn. Res.,

title: Gaussian processes in machine learning

venue: In Summer School on Machine Learning,

title: Gaussian processes in machine learning

authors:
Esteban Real
Alok Aggarwal
Yanping Huang
Quoc V Le

title: Regularized evolution for image classifier architecture search

venue: In Proceedings of the aaai conference on artificial intelligence,

authors:
Binxin Ru
Clare Lyle
Lisa Schut
Mark van der Wilk
Yarin Gal

title: Revisiting the train loss: an efficient performance estimator for neural architecture

authors:
Binxin Ru
Xingchen Wan
Xiaowen Dong
Michael Osborne

title: Neural architecture search using Bayesian optimisation with weisfeiler-lehman kernel

venue: arXiv preprint arXiv:2006.07556,

authors:
Michael Ruchte
Arber Zela
Julien Siems
Josif Grabocka
Frank Hutter

title: Naslib: a modular and flexible neural architecture search library, 2020

authors:
Christian Sciuto
Kaicheng Yu
Martin Jaggi
Claudiu Musat
Mathieu Salzmann

title: Evaluating the search phase of neural architecture search

venue: arXiv preprint arXiv:1902.08142,

authors:
Han Shi
Renjie Pi
Hang Xu
Zhenguo Li
James Kwok
Tong Zhang

title: Bridging the gap between sample-based and one-shot neural architecture search with bonas

venue: Advances in Neural Information Processing Systems,

authors:
Julien Siems
Lucas Zimmer
Arber Zela
Jovita Lukasik
Margret Keuper
Frank Hutter

title: Nas-bench-301 and the case for surrogate benchmarks for neural architecture

authors:
Jasper Snoek
Oren Rippel
Kevin Swersky
Ryan Kiros
Nadathur Satish
Narayanan Sundaram
Mostofa Patwary
Mr Prabhat
Ryan Adams

title: Scalable Bayesian optimization using deep neural networks

venue: In International conference on machine learning,

authors:
Jost Tobias Springenberg
Aaron Klein
Stefan Falkner
Frank Hutter

title: Bayesian optimization with robust Bayesian neural networks

authors:
Kenneth O Stanley
Risto Miikkulainen

title: Evolving neural networks through augmenting topologies

venue: Evolutionary computation,

authors:
Yanan Sun
Xian Sun
Yuhan Fang
Gary Yen

title: A new training protocol for performance predictors of evolutionary neural architecture search algorithms

venue: arXiv preprint arXiv:2008.13187,

authors:
Kevin Swersky
David Duvenaud
Jasper Snoek
Frank Hutter
Michael Osborne

title: Raiders of the lost architecture: Kernels for Bayesian optimization in conditional parameter spaces

venue: In NIPS workshop on Bayesian Optimization in Theory and Practice,

authors:
Hidenori Tanaka
Daniel Kunin
Daniel LK Yamins
Surya Ganguli

title: Pruning neural networks without any data by iteratively conserving synaptic flow

venue: arXiv preprint arXiv:2006.05467,

authors:
Lucas Theis
Iryna Korshunova
Alykhan Tejani
Ferenc Huszár

title: Faster gaze prediction with dense networks and fisher pruning

venue: arXiv preprint arXiv:1801.05787,

title: Variational learning of inducing variables in sparse gaussian processes

venue: In Artificial Intelligence and Statistics,

authors:
Chaoqi Wang
Guodong Zhang
Roger Grosse

title: Picking winning tickets before training by preserving gradient flow

authors:
Linnan Wang
Yiyang Zhao
Yuu Jinnai
Rodrigo Fonseca

title: Alphax: exploring neural architectures with deep neural networks and monte carlo tree search

venue: arXiv preprint arXiv:1805.07440,

authors:
Chen Wei
Chuang Niu
Yiping Tang
Jimin Liang

title: Npenas: Neural predictor guided evolution for neural architecture search

venue: arXiv preprint arXiv:2003.12857,

authors:
Wei Wen
Hanxiao Liu
Hai Li
Yiran Chen
Gabriel Bender
Pieter-Jan Kindermans

title: Neural predictor for neural architecture search

authors:
Colin White
Willie Neiswanger
Sam Nolen
Yash Savani

title: A study on encodings for neural architecture search

authors:
Colin White
Willie Neiswanger
Yash Savani

title: Bananas: Bayesian optimization with neural architectures for neural architecture search

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Antoine Yang
Pedro M Esperança
Fabio M Carlucci

title: Nas evaluation is frustratingly hard

authors:
Chris Ying
Aaron Klein
Esteban Real
Eric Christiansen
Kevin Murphy
Frank Hutter

title: Nasbench-101: Towards reproducible neural architecture search

venue: arXiv preprint arXiv:1902.09635,

authors:
Kaicheng Yu
Rene Ranftl
Mathieu Salzmann

title: How to train your super-net: An analysis of training heuristics in weight-sharing nas

venue: arXiv preprint arXiv:2003.04276,

authors:
Arber Zela
Thomas Elsken
Tonmoy Saikia
Yassine Marrakchi
Thomas Brox
Frank Hutter

title: Understanding and robustifying differentiable architecture search

authors:
Arber Zela
Julien Siems
Frank Hutter

title: Nas-bench-1shot1: Benchmarking and dissecting one-shot neural architecture search

title: Neural predictor for neural architecture

venue: search. GitHub repository ultmaster/neuralpredictor.pytorch,

authors:
Yuge Zhang
Zejun Lin
Junyang Jiang
Quanlu Zhang
Yujing Wang
Hui Xue
Chen Zhang
Yaming Yang

title: Deeper insights into weight sharing in neural architecture

authors:
Dongzhan Zhou
Xinchi Zhou
Wenwei Zhang
Chen Change Loy
Shuai Yi
Xuesen Zhang
Wanli Ouyang

title: Econas: Finding proxies for economical neural architecture search

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Barret Zoph
Quoc V. Le

title: Neural architecture search with reinforcement learning

heading: 1 Introduction

text:
Neural architecture search (NAS) is a popular area of machine learning, which aims to automate the process of developing neural architectures for a given dataset. Since 2017, a wide variety of NAS techniques have been proposed [78, 45, 32, 49]. While the first NAS techniques trained thousands of architectures to completion and then evaluated the performance using the final validation accuracy [78], modern algorithms use more efficient strategies to estimate the performance of partially-trained or even untrained neural networks [11, 2, 54, 34, 38].
Recently, many performance prediction methods have been proposed based on training a model to predict the final validation accuracy of an architecture just from an encoding of the architecture. Popular choices for these models include Gaussian processes [60, 17, 51], neural networks [36, 54, 65, 69], tree-based methods [33, 55], and so on. However, these methods often require hundreds of fully-trained architectures to be used as training data, thus incurring high initialization time. In contrast, learning curve extrapolation methods [11, 2, 20] need little or no initialization time, but each individual prediction requires partially training the architecture, incurring high query time. Very recently, a few techniques have been introduced which are fast both in query time and initialization time [38, 1], computing predictions based on a single minibatch of data. Finally, using shared weights [45, 4, 32] is a popular paradigm for NAS [73, 25], although the effectiveness of these methods in ranking architectures is disputed [53, 74, 76].
Despite the widespread use of performance predictors, it is not known how methods from different families compare to one another. While there have been some analyses on the best predictors within
∗{colin, yang}@abacus.ai, {zelaa, fh}@cs.uni-freiburg.de, robin@robots.ox.ac.uk
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
each class [41, 72], for many predictors, the only evaluation is from the original work that proposed the method. Furthermore, no work has previously compared the predictors across different families of performance predictors. This leads to two natural questions: how do zero-cost methods, model-based methods, learning curve extrapolation methods, and weight sharing methods compare to one another across different constraints on initialization time and query time? Furthermore, can predictors from different families be combined to achieve even better performance?
In this work, we answer the above questions by giving the first large-scale study of performance predictors for NAS. We study 31 predictors across four popular search spaces and four datasets: NAS-Bench-201 [13] with CIFAR-10, CIFAR-100, and ImageNet16-120, NAS-Bench-101 [71] and DARTS [32] with CIFAR-10, and NAS-Bench-NLP [21] with Penn TreeBank. In order to give a fair comparison among different classes of predictors, we run a full portfolio of experiments, measuring the Pearson correlation and rank correlation metrics (Spearman, Kendall Tau, and sparse Kendall Tau), across a variety of initialization time and query time budgets. We run experiments using a training and test set of architectures generated both uniformly at random, as well as by mutating the highest-performing architectures (the latter potentially more closely resembling distributions encountered during an actual NAS run). Finally, we test the ability of each predictor to speed up NAS algorithms, namely Bayesian optimization [36, 54, 69, 51] and predictor-guided evolution [66, 59].
Since many predictors so far had only been evaluated on one search space, our work shows which predictors have consistent performance across search spaces. Furthermore, by conducting a study with three axes of comparison (see Figure 1), and by comparing various types of predictors, we see a more complete view of the state of performance predictor techniques that leads to interesting insights. Notably, we show that the performance of predictors from different families are complementary and can be combined to achieve significantly higher performance. The success of these experiments opens up promising avenues for future work.
Overall, our experiments bridge multiple areas of NAS research and act as recommendations for the best predictors to use under different runtime constraints. Our code, based on the NASLib library [52], can be used as a testing ground for future performance prediction techniques. In order to ensure reproducibility of the original results, we created a table to clarify which of the 31 predictors had previously published results on a NAS-Bench search space, and how these published results compared to our results (Table 7). We also adhere to the NeurIPS 2021 checklist along with the specialized NAS best practices checklist [31].
Our contributions. We summarize our main contributions below.
• We conduct the first large-scale study of performance predictors for neural architecture search by comparing model-based methods, learning curve extrapolation methods, zero-cost methods, and weight sharing methods across a variety of settings.
• We release a comprehensive library of 31 performance predictors on four different search spaces. • We show that different families of performance predictors can be combined to achieve substantially
better predictive power than any single predictor.

heading: 2 Related Work

text:
NAS has been studied since at least the 1990s [19, 58], and has been revitalized in the last few years [78]. While initial techniques focused on reinforcement learning [78, 45] and evolutionary search [37, 49], one-shot NAS algorithms [32, 12, 4] and predictor-based NAS algorithms [65, 54, 69] have recently become popular. We give a brief survey of performance prediction techniques in Section 3. For a survey on NAS, see [15]. The most widely used type of search space in prior work is the cell-based search space [79], where the architecture search is over a relatively small directed acyclic graph representing an architecture.
A few recent works have compared different performance predictors on popular cell-based search spaces for NAS. Siems et al. [55] studied graph neural networks and tree-based methods, and found that gradient-boosted trees and graph isomorphism networks performed the best. However, the comparison was only on a single search space and dataset, and the explicit goal was to achieve maximum performance given a training set of around 60 000 architectures. Another recent paper [41] studied various aspects of supernetwork training, and separately compared four model-based methods: random forest, MLP, LSTM, and GATES [42]. However, the comparisons were again on a single search space and dataset and did not compare between multiple families of performance predictors. Other papers have proposed new model-based predictors and compared the new predictors to other model-based baselines [34, 65, 54, 69]. Finally, a recent paper analyzed training heuristics to make weight-sharing more effective at ranking architectures [72]. To the best of our knowledge, no prior work has conducted comparisons across multiple families of performance predictors.

heading: 3 Performance Prediction Methods for NAS

text:
In NAS, given a search space A, the goal is to find a∗ = argmina∈Af(a), where f denotes the validation error of architecture a after training on a fixed dataset for a fixed number of epochs E. Since evaluating f(a) typically takes hours (as it requires training a neural network from scratch), many NAS algorithms make use of performance predictors to speed up this process. A performance predictor f ′ is defined generally as any function which predicts the final accuracy or ranking of architectures, without fully training the architectures. That is, evaluating f ′ should take less time than evaluating f , and {f ′(a) | a ∈ A} should ideally have high correlation or rank correlation with {f(a) | a ∈ A}. Each performance predictor is defined by two main routines: an initialization routine which performs general pre-computation, and a query routine which performs the final architecture-specific computation: it takes as input an architecture specification, and outputs its predicted accuracy. For example, one of the simplest performance predictors is early stopping: for any query(a), train a for E/2 epochs instead of E [77]. In this case, there is no general pre-computation, so initialization time is zero. On the other hand, the query time for each input architecture is high because it involves training the architecture for E/2 epochs. In fact, the runtime of the initialization and query routines varies substantially based on the type of predictor. In the context of NAS algorithms, the initialization routine is typically performed once at the start of the algorithm, and the query routine is typically performed many times throughout the NAS algorithm. Some performance predictors also make use of an update routine, when part of the computation from initialization needs to be updated without running the full procedure again (for example, in a NAS algorithm, a model may be updated periodically based on newly trained architectures). Now we give an overview of the main families of predictors. See Figure 1 (left) for a taxonomy of performance predictors.
Model-based (trainable) methods. The most common type of predictor, the model-based predictor, is based on supervised learning. The initialization routine consists of fully training many architectures (i.e., evaluating f(a) for many architectures a ∈ A) to build a training set of datapoints {a, f(a)}. Then a model f ′ is trained to predict f(a) given a. While the initialization time for model-based predictors is very high, the query time typically takes less than a second, which allows thousands of predictions to be made throughout a NAS algorithm. The model is also updated regularly based on the new datapoints. These predictors are typically used within BO frameworks [36, 54], evolutionary frameworks [66], or by themselves [67], to perform NAS. Popular choices for the model include tree-based methods (where the features are the adjacency matrix representation of
the architectures) [33, 55], graph neural networks [36, 54], Gaussian processes [47, 51], and neural networks based on specialized encodings of the architecture [69, 42].
Learning curve-based methods. Another family predicts the final performance of architectures using only a partially trained network, by extrapolating the learning curve. This is accomplished by fitting the partial learning curve to an ensemble of parametric models [11], or by simply summing the training losses observed so far [50]. Early stopping as described earlier is also a learning curve-based method. Learning curve methods do not require any initialization time, yet the query time typically takes minutes or hours, which is orders of magnitude slower than the query time in model-based methods. Learning curve-based methods can be used in conjunction with multi-fidelty algorithms, such as Hyperband or BOHB [27, 16, 24].
Hybrid methods. Some predictors are hybrids between learning curve and model-based methods. These predictors train a model at initialization time to predict f(a) given both a and a partial learning curve of a as features. Models in prior work include an SVR [2], or a Bayesian neural network [20]. Although the query time and initialization time are both high, hybrid predictors tend to have strong performance.
Zero-cost methods. Another class of predictors have no initialization time and very short query times (so-called “zero-cost” methods). These predictors compute statistics from just a single forward/backward propagation pass for a single minibatch of data, by computing the correlation of activations within a network [38], or by adapting saliency metrics proposed in pruning-at-initialization literatures [23, 1]. Similar to learning curve-based methods, since the only computation is specific to each architecture, the initialization time is zero. Zero-cost methods have recently been used to warm start NAS algorithms [1].
Weight sharing methods. Weight sharing [45] is a popular approach to substantially speed up NAS, especially in conjunction with a one-shot algorithm [32, 12]. In this approach, all architectures in the search space are combined to form a single over-parameterized supernetwork. By training the weights of the supernetwork, all architectures in the search space can be evaluated quickly using this set of weights. To this end, the supernetwork can be used as a performance predictor. This results in NAS algorithms [32, 28] which are significantly faster than sequential NAS algorithms, such as evolution or Bayesian optimization. Recent work has shown that although the shared weights are sometimes not effective at ranking architectures [53, 74, 76], one-shot NAS techniques using shared weights still achieve strong performance [73, 25].
Tradeoff between intialization and query time. The main families mentioned above all have different initialization and query times. The tradeoffs between initialization time, query time, and performance depend on a few factors such as the type of NAS algorithm and its total runtime budget, and different settings are needed in different situations. For example, if there are many architectures whose performance we want to estimate, then we should have a low query time, and if we have a high total runtime budget, then we can afford a high initialization time. We may also change our runtime budget throughout the run of a single NAS algorithm. For example, at the start of a NAS algorithm, we may want to have coarse estimates of a large number of architectures (low initialization time, low query time such as zero-cost predictors). As the NAS algorithm progresses, it is more desirable to receive higher-fidelity predictions on a smaller set of architectures (model-based or hybrid predictors). The exact budgets depend on the type of NAS algorithm.
Choice of performance predictors. We analyze 31 performance predictors defined in prior work: BANANAS [69], Bayesian Linear Regression [6], BOHAMIANN [57], BONAS [54], DNGO [56], Early Stopping with Val. Acc. (e.g. [77, 27, 16, 79]) Early Stopping with Val. Loss. [50], Fisher [1], Gaussian Process (GP) [48], GCN [75], Grad Norm [1], Grasp [64], Jacobian Covariance [38], LCE [11], LCE-m [20], LcSVR [2], LGBoost/GBDT [33], MLP [69], NAO [35], NGBoost [55], OneShot [73], Random Forest (RF) [55], Random Search with Weight Sharing (RSWS) [26], SemiNAS [34], SNIP [23], SoTL [50], SoTL-E [50], Sparse GP [3], SynFlow [61], Variational Sparse GP [63], and XGBoost [55]. For any method that did not have an architecture encoding already defined (such as the tree-based methods, GP-based methods, and Bayesian Linear Regression), we use the standard adjacency matrix encoding, which consists of the adjacency matrix of the architecture along with a one-hot list of the operations [71, 68]. By open-sourcing our code, we encourage
104 105 106
Init. time (seconds)
101
102
103
Qu er
y tim
e (s
ec on
ds )
.93 .93 .93 .93 .93 .93 .93 .93 .93 .93 .93.93
.4
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57
.57 .6
.58
.62
.65
.6
.63
.66
.6
.64
.67
.7
.65
.67
.7
.69
.72
.74
.84
.73
.75
.77
.85
.63
.69
.74
.77
.8
.82
.83
.84
.84
.63
.69
.74
.77
.8
.82
.83
.84
.84
.63
.69
.74
.77
.8
.82
.83
.84
.84
.63
.69
.74
.77
.8
.82
.83
.84
.84
.63
.69
.74
.77
.8
.82
.83
.84
.84
.69
.74
.77
.8
.82
.83
.84
.84
.69
.74
.77
.8
.82
.83
.84
.84
.74
.77
.8
.82
.83
.84
.84
.74
.77
.8
.82
.83
.84
.84
.77
.8
.82
.83
.84
.8
.82
.83
.84
.63
.69
.74
.77
.8
.82
.83
.84
.84
.28 .42 .46 .5 .53 .57 .6
.6
.6
.6
.63
.63
.63
.63
.63
.68
.68
.68
.68
.68
.68
.73
.73
.73
.73
.73
.73
.73
Kendall Tau on NAS-Bench-201 CIFAR-10
105 106 107
Init. time (seconds)
102
103
104
Qu er
y tim
e (s
ec on
ds )
NAS-Bench-NLP
105 106 107
Init. time (seconds)
102
103
104
Qu er
y tim
e (s
ec on
ds )
NAS-Bench-201 ImageNet16-120
104 105 106
Init. time (seconds)
101
102
103
Qu er
y tim
e (s
ec on
ds )
NAS-Bench-101
104 105
Init. time (seconds)
101
102
103
Qu er
y tim
e (s
ec on
ds )
DARTS
5.00 5.25 5.50 5.75 6.00
5.0
5.2
5.4
5.6
5.8
6.0
BANANAS Bayes. Lin. Reg.
Early Stop (Acc.) GCN
Jacob. Cov. LGBoost
LcSVR NGBoost
SoTL-E SemiNAS
SynFlow XGBoost
Figure 2: The performance predictors with the highest Kendall Tau values for all initialization time and query time budgets on NAS-Bench-201, NAS-Bench-101, NAS-Bench-NLP and DARTS. For example, on NAS-Bench-201 CIFAR-10 (left) with an initialization time of 106 seconds and query time of 10 seconds, XGBoost achieves a Kendall Tau value of .73 which is the highest value out of the 31 predictors that we tested at that budget.
implementing more (existing and future) performance predictors which can then be compared to the 31 which we focus on in this work. In Section B.1, we give descriptions and detailed implementation details for each performance predictor. In Section D, we give a table that describes for which predictors we were able to reproduce published results, and for which predictors it is not possible (e.g., since some predictors were released before the creation of NAS benchmarks).

heading: 4 Experiments

text:
We now discuss our experimental setup and results. We discuss reproducibility in Sections A and D, and our code (based on the NASLib library [52]) is available at https://github.com/automl/ naslib. We split up our experiments into two categories: evaluating the performance of each predictor with respect to various correlation metrics (Section 4.1), and evaluating the ability of each predictor to speed up predictor-based NAS algorithms (Section 4.2). We start by describing the four NAS benchmarks used in our experiments.
NAS benchmark datasets. NAS-Bench-101 [71] consists of over 423 000 unique neural architectures with precomputed training, validation, and test accuracies after training for 4, 12, 36, and 108 epochs on CIFAR-10 [71]. The cell-based search space consists of five nodes which can take on any directed acyclic graph (DAG) structure, and each node can be one of three operations. Since learning curve information is only available at four epochs, it is not possible to run most learning curve extrapolation methods on NAS-Bench-101. NAS-Bench-201 [13] consists of 15 625 architectures (out of which 6 466 are unique after removing isomorphisms [13]). Each architecture has full learning curve information for training, validation, and test losses/accuracies for 200 epochs on CIFAR-10 [22], CIFAR-100, and ImageNet-16-120 [10]. The search space consists of a cell which is a complete DAG with 4 nodes. Each edge can take one of five different operations. The DARTS search space [32] is significantly larger with roughly 1018 architectures. The search space consists of two cells, each with seven nodes. The first two nodes are inputs from previous layers, and the intermediate four nodes can take on any DAG structure such that each node has two incident edges. The last node is the output node. Each edge can take one of eight operations. In our experiments, we make use of the training data from NAS-Bench-301 [55], which consists of 23 000 architectures drawn uniformly at random and trained on CIFAR-10 for 100 epochs. Finally, the NAS-Bench-NLP search space [21] is even
larger, at 1053 LSTM-like cells, each with at most 25 nodes in any DAG structure. Each cell can take one of seven operations. In our experiments, we use the NAS-Bench-NLP dataset, which consists of 14 000 architectures drawn uniformly at random and trained on Penn Tree Bank [40] for 50 epochs.
Hyperparameter tuning. Although we used the code directly from the original repositories (sometimes making changes when necessary to adapt to NAS-Bench search spaces), the predictors had significantly different levels of hyperparameter tuning. For example, some of the predictors had undergone heavy hyperparameter tuning on the DARTS search space (used in NAS-Bench-301), while other predictors (particularly those from 2017 or earlier) had never been run on cell-based search spaces. Furthermore, most predictor-based NAS algorithms can utilize cross-validation to tune the predictor periodically throughout the NAS algorithm. This is because the bottleneck for predictorbased NAS algorithms is typically the training of architectures, not fitting the predictor [56, 30, 16]. Therefore, it is fairer and also more informative to compare performance predictors which have had the same level of hyperparameter tuning through cross-validation. For each search space, we run random search on each performance predictor for 5000 iterations, with a maximum total runtime of 15 minutes. The final evaluation uses a separate test set. The hyperparameter value ranges for each predictor can be found in Section B.2.

heading: 4.1 Performance Predictor Evaluation

text:
We evaluate each predictor based on three axes of comparison: initialization time, query time, and performance. We measured performance with respect to several different metrics: Pearson correlation and three different rank correlation metrics (Spearman, Kendall Tau, and sparse Kendall Tau [72, 55]). The experimental setup is as follows: the predictors are tested with 11 different initialization time budgets and 14 different query time budgets, leading to a total of 154 settings. On NAS-Bench-201 CIFAR-10, the 11 initialization time budgets are spaced logarithmically from 1 second to 1.8× 107 seconds on a 1080 Ti GPU (which corresponds to training 1000 random architectures on average) which is consistent with experiments conducted in prior work [65, 69, 34]. For other search spaces, these times are adjusted based on the average time to train 1000 architectures. The 14 query time budgets are spaced logarithmically from 1 second to 1.8×104 seconds (which corresponds to training an architecture for 199 epochs). These times are adjusted for other search spaces based on the training time and different number of epochs. Once the predictor is initialized, we draw a test set of 200 architectures uniformly at random from the search space. For each architecture in the test set, the predictor uses the specified query time budget to make a prediction. We then evaluate the quality of the predictions using the metrics described above. We average the results over 100 trials for each (initialization time, query time) pair.
Results and discussion. Figure 1 shows a full three-dimensional plot for NAS-Bench-201 on CIFAR-10 over initialization time, query time, and Kendall Tau rank correlation. Of the 31 predictors we tested, we found that just seven of them are Pareto-optimal with respect to Kendall Tau, initialization time, and query time. That is, only seven algorithms have the highest Kendall Tau value for at least one of the 154 query time/initialization time budgets on NAS-Bench-201 CIFAR-10. This can be seen more clearly in Figure 2 (left), which is a view from above Figure 1: each lattice point displays the predictor with the highest Kendall Tau value for the corresponding budget. In Figure 2 (right), we plot the Pareto-optimal predictors for five different dataset/search space combinations. In Section B.3, we give the full 3D plots and report the variance across trials for each method. In Figure 4 (left), we also plot the Pearson and Spearman correlation coefficients for NAS-Bench-201 CIFAR-10. The trends between these measures are largely the same, although we see that SemiNAS performs better on the rank-based metrics. For the rest of this section, we focus on the popular Kendall Tau metric, giving the full results for the other metrics in Section B.3.
We see similar trends across DARTS and the two NAS-Bench-201 datasets. NAS-Bench-NLP also has fairly similar trends, although early stopping performs comparatively stronger. NAS-Bench-101 is different from the other search spaces both in terms of the topology and the benchmark itself, which we discuss later in this section.
In the low initialization time, low query time region, Jacobian covariance or SynFlow perform well across NAS-Bench-101 and NAS-Bench-201. However, none of the six zero-cost methods perform well on the larger DARTS search space. Weight sharing (which also has low initialization and low query time, as seen in Figure 1), did not yield high Kendall Tau values for these search spaces, either,

heading: 104 105 106

text:
which is consistent with recent work [53, 74, 76]. However, rank correlation is not as crucial to one-shot NAS algorithms as it is for black box predictor-based methods, as demonstrated by prior one-shot NAS methods that do perform well [25, 73, 32, 28, 12]. In the low initialization time, high query time region, sum of training losses (SoTL-E) consistently performed the best, outperforming other learning-curve based methods.
The high initialization time, low query time region (especially the bottom row of the plots, corresponding to a query time of 1 second) is by far the most competitive region in the recent NAS literature. Sixteen of the 31 predictors had query times under one second, because many NAS algorithms are designed to initialize (and continually update) performance predictors that are used to quickly query thousands of candidate architectures. GCN and SemiNAS, the specialized GCN/semi-supervised methods, perform especially well in the first half of this critical region, when the initialization time is relatively low. However, boosted tree methods actually performed best in the second half of the critical region where the initialization time is high, which is consistent with prior work [33, 55]. Recall that for model-based methods, the initialization time corresponds to training architectures to be used as training data for the performance predictor. Therefore, our results suggest that techniques which can extract better latent features of the architectures can make up for a small training dataset, but methods based purely on performance data work better when there is enough such data.
Perhaps the most interesting finding is that on NAS-Bench-101/201, SynFlow and Jacobian covariance, which take three seconds each to compute, both outperform all model-based methods even after 30 hours of initialization. Put another way, NAS algorithms that make use of model-based predictors may be able to see substantial improvements by using Jacobian covariance instead of a model-based predictor in the early iterations.
The Omnipotent Predictor. One conclusion from Figure 2 is that different types of predictors are specialized for specific initialization time and query time constraints. A natural follow-up question is whether different families are complementary and can be combined to achieve stronger performance. In this section, we run a proof-of-concept to answer this question. We combine the best-performing predictors from three different families in a simple way: the best learning curve method (SoTL-E), and the best zero-cost method (Jacobian covariance), are used as additional input features for a model-based predictor (we separately test SemiNAS and NGBoost). We call this method OMNI, the omnipotent predictor. We give results in Figure 3 and pseudo-code as well as additional experiments in Section B.4. In contrast to all other predictors, the performance of OMNI is strong across almost all budget constraints and search spaces. In some settings, OMNI achieves a Kendall Tau value 30% higher than the next-best predictors.
The success of OMNI verifies that the information learned by different families of predictors are complementary: the information learned by extrapolating a learning curve, by computing a zero-cost proxy, and by encoding the architecture, all improve performance. We further confirm this by running an ablation study for OMNI in Section B.4. We can hypothesize that each predictor type measures distinct quantities: SOTL-E measures the training speed, zero-cost predictors measure the covariance between activations on different datapoints, and model-based predictors simply learn patterns between the architecture encodings and the validation accuracies. Finally, while we showed a proof-of-concept, there are several promising areas for future work such as creating ensembles of the model-based approaches, combining zero-cost methods with model-based methods in more sophisticated ways, and giving a full quantification of the correlation among different families of predictors.
104 105 106 Init. time (seconds)
101
102
103
Qu er
y tim
e (s
ec on
ds )
Pearson correlation
Early Stop (Acc.) GCN Jacob. Cov. LcSVR SoTL-E SemiNAS XGBoost

heading: 104 105 106

text:
Init. time (seconds)
101
102
103
Qu er
y tim
e (s
ec on
ds )
Spearman rank correlation
Init time (seconds) 103 104
105
Que ry t
ime (se
con ds)
100
101
102
Ke nd
al l T
au
0.0
0.2
0.4
0.6
0.8
Kendall Tau on NAS-Bench-201 CIFAR-10
BANANAS BOHAMIANN BONAS Bayes. Lin. Reg. DNGO Early Stop (Acc.) Early Stop (Loss) GCN GP LCE LCNet LGBoost MLP NAO NGBoost RF SemiNAS SoTL SoTL-E Sparse GP Var. Sparse GP XGBoost Fisher Grad Norm Grasp Jacob. Cov. LcSVR SNIP SynFlow
Init time (seconds) 103 104
105
Que ry t
ime (se
con ds)
100
101
102
Ke nd
al l T
au
0.0
0.2
0.4
0.6
0.8
Kendall Tau on NAS-Bench-201 CIFAR-10
BANANAS BOHAMIANN BONAS Bayes. Lin. Reg.
DNGO Early Stop (Acc.) Early Stop (Loss) GCN
GP LCE LCE-m LGBoost
MLP NAO NGBoost RF
SemiNAS SoTL SoTL-E Sparse GP
Var. Sparse GP XGBoost Fisher
Grad Norm Grasp Jacob. Cov.
LcSVR SNIP SynFlow
Figure 4: The best predictors on NAS-Bench-201 CIFAR-10 with respect to Pearson (left) and Spearman (middle). Kendall Tau values from a mutation-based training and test set (right).
NAS-Bench-101: a more complex search space. In Figure 2, the plot for NAS-Bench-101 looks significantly different than the plots for the other search spaces, for two reasons. The first reason is a technical one: the NAS-Bench-101 API only gives the validation accuracy at four epochs, and does not give the training loss for any epochs. Therefore, we could not implement SoTL or any learning curve extrapolation method. However, all sixteen of the model-based predictors were implemented on NAS-Bench-101. In this case, BANANAS significantly outperformed the next-best predictors (GCN and SemiNAS) across every initialization time. One explanation is due to the complexity of the NAS-Bench-101 search space: while all NAS-Bench-201 architectures have the same graph topology and DARTS architectures’ nodes have exactly two incoming edges, the NAS-Bench-101 search space is much more diverse with architectures ranging from a single node and no edges, to five nodes with nine connecting edges. In fact, the architecture encoding used in BANANAS, the path encoding, was designed specifically to deal with the complexity of the NAS-Bench-101 search space (replacing the standard adjacency matrix encoding). To test this explanation, in Appendix B we run several of the simpler tree-based and GP-based predictors using the path encoding, and we see that these methods now surpass BANANAS in performance.
A mutation-based test set. The results from Figure 2 used a test set drawn uniformly at random from the search space (and the training set used by model-based predictors was also drawn uniformly at random). However, neighborhood-based NAS algorithms such as local search, regularized evolution, and some versions of Bayesian optimization consider architectures which are local perturbations of the architectures encountered so far. Therefore, the predictors used in these NAS algorithms must be able to distinguish architectures which are local mutations of a small set of seed architectures.
We run an experiment in which the test set is created by mutating architectures from an initial set of seed architectures. Specifically, we draw a set of 50 random architectures and choose the five with the highest validation accuracy as seed architectures. Then we create a set of 200 test architectures by randomly mutating up to three attributes of the seed architectures. Therefore, all architectures in the test set are at most an edit distance of three from a seed architecture, where two architectures are a single edit distance away if they differ by one operation or edge.
We create the training set by randomly choosing architectures from the test set and mutating one random attribute. As in all of our experiments, we ensure that the training set and test set are disjoint. In Figure 4 (right), we plot the correlation results for NAS-Bench-201 CIFAR-10. While the zero-cost and learning curve-based approaches have similar performance, the model-based approaches have significantly worse performance compared to the uniform random setting. This is because the average edit distance between architectures in the test set is low, making it significantly harder for model-based predictors to distinguish the performance of these architectures, even when using a training set that is based on mutations of the test set. In fact, interestingly, the performance of many model-based approaches starts to perform worse after 106 seconds. SemiNAS in particular performs much worse in this setting, and boosted trees have comparatively stronger performance in this setting.

heading: 4.2 Predictor-Based NAS Experiments

text:
Now we evaluate the ability of each model-based performance predictor to speed up NAS. We use two popular predictor-based NAS methods: the predictor-guided evolution framework [66, 59], and the Bayesian optimization + predictor framework [17, 36, 54]. The predictor-guided evolution framework is an iterative procedure in which the best architectures in the current population are mutated to create a set of candidate architectures. A predictor (trained on the entire population) chooses k architectures which are then evaluated. In our experiments, the candidate pool is created by mutating the top five architectures 40 times each, and we set k = 20. For each predictor, we run predictor-guided evolution for 25 iterations and average the results over 100 trials. The BO + predictor framework is similar to the evolution framework, but an ensemble of three performance predictors are used so that uncertainty estimates for each prediction can be computed. In each iteration, the candidate architectures whose predictions maximize an acquisition function are then evaluated. Similar to prior work, we use independent Thompson sampling [69], as the acquisition function, and an ensemble is created by using a different ordering of the training set and different random weight initializations (if applicable) of the same predictor. In each iteration, the top 20 architectures are chosen from a randomly sampled pool of 200 architectures.
In Figure 5, we present results for both NAS frameworks on NAS-Bench-201 CIFAR-10 and ImageNet16-120 for the 16 model-based predictors. We also test OMNI, using its lowest query time setting (consisting of NGBoost + Jacobian covariance), and another version of OMNI that replaces NGBoost with SemiNAS. Our results show that the model-based predictors with the top Kendall Tau rank correlations in the low query time region from Figure 2 also roughly achieve the best performance when applied for NAS: SemiNAS and NAO perform the best for shorter runtime, and boosted trees perform best for longer runtime. OMNI(NGBoost) consistently outperforms NGBoost, and OMNI(SemiNAS) often achieves top performance. This suggests that using zero-cost methods in conjunction with model-based methods is a promising direction for future study.

heading: 4.3 So, how powerful are performance predictors?

text:
Throughout Section 4, we tested performance predictors in a variety of settings, by varying the search spaces, datasets, runtime budgets, and training/test distributions. We saw largely the same trends among all of our experiments. Interesting findings included the success of zero-cost predictors even when compared to model-based predictors and learning curve extrapolation predictors with longer runtime budgets, and the fact that information from different families of predictors are complementary. When choosing a performance predictor for new applications, we recommend deciding on a target initialization time and query time budget, consulting Figures 2 and 6, and then combining the best
predictors from the desired runtime setting, similar to OMNI. For example, if a performance predictor with medium initialization time and low runtime is desired for a search space similar to NAS-Bench201 or DARTS, we recommend using NGBoost with Jacobian covariance and SynFlow as additional features.

heading: 5 Societal Impact

text: Our hope is that our work will have a positive impact on the AutoML community by making it quicker and easier to develop and fairly compare performance predictors. For example, AutoML practitioners can consult our experiments to more easily decide on the performance prediction methods best suited to their application, rather than conducting computationally intensive experiments of their own [43]. Furthermore, AutoML researchers can use our library to develop new performance prediction techniques and compare new methods to 31 other algorithms across four search spaces. Since the topic of this work is AutoML, it is a level of abstraction away from real applications. This work may be used to improve deep learning applications, both beneficial (e.g. reducing CO2 emissions), or harmful (e.g. creating language models with heavy bias) to society.

heading: 6 Conclusions and Limitations

text:
In this work, we gave the first large-scale study of performance predictors for neural architecture search. We compared 31 different performance predictors, including learning curve extrapolation methods, weight sharing methods, zero-cost methods, and model-based methods. We tested the performance of the predictors in a variety of settings and with respect to different metrics. Although we ran experiments on four different search spaces, it will be interesting to extend our experiments to even more machine learning tasks beyond image classification and language modeling.
Our new predictor, OMNI, is the first predictor to combine complementary information from three families of performance preditors, leading to substantially improved performance. While the simplicity of OMNI is appealing, it also opens up new directions for future work by combining different predictors in more sophisticated ways. To facilitate follow-up work, we release our code featuring a library of performance predictors. Our goal is for our repository to grow over time as it is used by the community, so that experiments in our library can be even more comprehensive.
Acknowledgments and Disclosure of Funding
This work was done while CW and YL were employed at Abacus.AI. AZ and FH acknowledge support by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme through grant no. 716721, and by BMBF grant DeToL. BR was supported by the Clarendon Fund of University of Oxford.

title: How Powerful are Performance Predictors in Neural Architecture Search?


summaries: The paper studies releasing a single sample from a Dirichlet posterior with several variants of differential privacy in the two specific tasks of Dirichlet sampling and private normalized histogram publishing. Both privacy and utility guarantees are analyzed by the authors. The authors compare the results with Gaussian mechanism theoretically and empirically using a simple simulation.

summaries: This paper proposes a method for releasing differentially private samples from Dirichlet posterior distribution. Authors present a privacy analysis for their proposed method and demonstrate that the method out performs Gaussian mechanism under certain conditions. Besides the empirical evaluation, authors also derive analytical utility guarantees for the method.

summaries: This paper provides a posterior sampling mechanism for the Dirichlet distribution achieving tCDP and approximate DP privacy, relying on modifying the alpha parameters. It includes an application on histogram release.  The response addressed my comments.

summaries: This paper studies the privacy of releasing a sample from the Dirichlet posterior. The paper shows for the Dirichlet posterior sampling with prior set to be $\mathrm{Dirichlet}(\alpha)$, that Dirichlet posterior sampling  satisfies a version of truncated concentrated Differential Privacy(tCDP). Now, using the relationship between tCDP and approximate DP established in Bun et al. (2018), the paper derives the approximate differential privacy of the Dirichlet Posterior sampling.   Given the result, the paper studies the utility of Dirichlet posterior sampling in 2 contexts: 1. One is interested in sampling for the posterior but changing the prior from $Dirichlet (\alpha)$ to $Dirichlet (\alpha’)$, such that $\alpha_i' > \alpha_i$ so as to increase the privacy preserving properties of the the posterior sampling. In this context, the paper derives sample complexity bounds such that $D_{KL}(\mathrm{Dirichlet}(\mathbf{x} + \alpha)|| \mathrm{Dirichlet}(\mathbf{x} + \alpha') )<\varepsilon$. 2. One is interested in releasing the normalized histogram $\mathbf{p} = \mathbf{x}/N$. One can privately release it by sampling from the Dirichlet posterior $Y \sim \mathrm{Dirichlet}(\mathbf{x}+ \alpha)$. The paper derives sample complexity bounds to incur small error $\ell_\infty$ norm. Authors also point out that one can get better sample complexity with Gaussian mechanism where Dirichlet posterior sampling outperforms Gaussian mechanism in small data regime.

abstractText: We study the inherent privacy of releasing a single sample from a Dirichlet posterior 1 distribution. As a complement to the previous study that provides general theories 2 on the differential privacy of posterior sampling from exponential families, this 3 study focuses specifically on the Dirichlet posterior sampling and its privacy 4 guarantees. With the notion of truncated concentrated differential privacy (tCDP), 5 we are able to derive a simple privacy guarantee of the Dirichlet posterior sampling, 6 which effectively allows us to analyze its utility in various settings. Specifically, 7 we provide accuracy guarantees of the Dirichlet posterior sampling in Multinomial8 Dirichlet sampling and private normalized histogram publishing. 9

text:
We study the inherent privacy of releasing a single sample from a Dirichlet posterior1 distribution. As a complement to the previous study that provides general theories2 on the differential privacy of posterior sampling from exponential families, this3 study focuses specifically on the Dirichlet posterior sampling and its privacy4 guarantees. With the notion of truncated concentrated differential privacy (tCDP),5 we are able to derive a simple privacy guarantee of the Dirichlet posterior sampling,6 which effectively allows us to analyze its utility in various settings. Specifically,7 we provide accuracy guarantees of the Dirichlet posterior sampling in Multinomial-8 Dirichlet sampling and private normalized histogram publishing.9
1 Introduction10
The Bayesian framework provides a way to perform statistical analysis by combining prior beliefs11 with real-life evidence. At a high level, the belief and the evidence are assumed to be described12 by probabilistic models. As we receive new data, our belief is updated accordingly via the Bayes’13 theorem, resulting in the so-called posterior belief. The posterior tells us how much we are uncertain14 about the model’s parameters.15
The Dirichlet distribution is usually chosen as the prior when performing Bayesian analysis on discrete16 variables, as it is a conjugate prior to the categorical and multinomial distributions. Specifically,17 Dirichlet distributions are often used in discrete mixture models, where a Dirichlet prior is put on18 the mixture weights [LW92; MMR05]. Such models have applications in NLP [PB98], biophysical19 systems [Hin15], accident analysis [de 06], and genetics [BHW00; PM01; CWS03]. In all of these20 studies, samplings from Dirichlet posteriors arise when performing Markov chain Monte Carlo21 methods for approximate Bayesian inference.22
Dirichlet posterior sampling also appears in other learning tasks. For example, in Bayesian active23 learning, it arises in Gibbs sampling, which is used to approximate the posterior of the classifier over24 the labeled sample [NLYCC13]. In Thompson sampling for multi-armed bandits, one repeatedly25 draws a sample from the Dirichlet posterior of each arm, and picks the arm whose sample maximizes26 the reward [ZHGSY20; AAFK20; NIK20]. And in Bayesian reinforcement learning, state-transition27 probabilities are sampled from the Dirichlet posterior over past observed states [Str00; ORR13].28
Dirichlet posterior sampling can also be used for data synthesis. Suppose that we have a histogram29 (x1, . . . , xd) of actual data. An approximate discrete distribution of this histogram can be obtained by30 drawing a sample Y from Dirichlet(x1 + α1, . . . , xd + αd), where α1, . . . , αd are prior parameters.31 Then synthetic data is produced by repeatedly drawing from Multinomial(Y). There are many32 studies on data synthesis that followed this approach [AV08; MKAGV08; RWZ14; PG14; SJGLY17].33
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
In the above examples, the data that we integrate into these tasks might contain sensitive information.34 Thus it is important to ask: how much of the information is protected from the Dirichlet samplings?35 The goal of this study is to find an answer to this question.36
The mathematical framework of differential privacy (DP) [DMNS06] allows us to quantify how much37 the privacy of the Dirichlet posterior sampling is affected by the prior parameters α1, . . . , αd. In the38 definition of DP, the privacy of a randomized algorithm is measured by how much its distribution39 changes upon perturbing a single data point of the input. Nonetheless, this notion might be too40 strict for the Dirichlet distribution, as a small perturbation of a near-zero parameter can cause a large41 distribution shift. Thus, it might be more appropriate to rely on one of several relaxed notions of42 DP, such as approximate differential privacy, Rényi differential privacy, or concentrated differential43 privacy. It is natural to wonder if the Dirichlet posterior sampling satisfies any of these definitions.44
1.1 Overview of Our results45
This study focuses on the privacy and utility of Dirichlet posterior sampling. In summary, we provide46 a closed-form privacy guarantee of the Dirichlet posterior sampling, which in turn allows us to47 effectively analyze its utility in various settings.48
§3 Privacy. We study the role of the prior parameters in the privacy of the Dirichlet posterior49 sampling. Theorem 1 is our main result, where we provide a guaranteed upper bound for truncated50 concentrated differential privacy (tCDP) of the Dirichlet posterior sampling. In addition, we convert51 the tCDP guarantee into an approximate differential privacy guarantee in Corollary 2.52 §4 Utility. Using the tCDP guarantee, we investigate the utility of Dirichlet posterior sampling53 applied in two specific applications:54
• In Section 4.1, we consider one-time sampling from a Multinomial-Dirichlet distribution.55 But instead of directly sampling from this distribution, we sample from another distribution56 with larger prior parameters. The accuracy is then measured by the KL-divergence between57 the original and the private distributions.58
• In Section 4.2, we use the Dirichlet posterior sampling for a private release of a normalized59 histogram. In this case, the accuracy is measured by the mean-squared error between the60 sample and the original normalized histogram.61
In both tasks, we compute the sample size that guarantees the desired level of accuracy. In the case62 of private histogram publishing, we also compare the Dirichlet posterior sampling to the Gaussian63 mechanism.64
1.2 Related work65
There are several studies on the differential privacy of posterior sampling. Wang, Fienberg, and66 Smola [WFS15] showed that any posterior sampling with the log-likelihood bounded by B is 4B-67 differentially private. However, the likelihoods that we study are not bounded away from zero; they68 have the form ∏ i p xi i which becomes small when one of the pi’s is close to zero. Dimitrakakis, Nelson,69 Zhang, Mitrokotsa, and Rubinstein [DNZMR17] showed that if the condition on the log-likelihood is70 relaxed to the Lipschitz continuity with high probability, then one can obtain the approximate DP.71 Nonetheless, with the Dirichlet density, it is difficult to compute the probability of events in which72 the Lipschitz condition is satisfied.73
In the case that the sufficient statistics x has finite `1-sensitivity, Foulds, Geumlek, Welling and74 Chaudhuri [FGWC16] suggested adding Laplace noises to x. Suppose that y is the output; they75 showed that sampling from p(θ|y) is differentially private and as asymptotically efficient as sampling76 from p(θ|x). However, for a small sample size, the posterior over the noisy statistics might be too77 far away from the actual posterior. Bernstein and Sheldon [BS18] thus proposed to approximate the78 joint distribution p(θ,x,y) using Gibbs sampling, which is then integrated over x to obtain a more79 accurate posterior over y.80
Geumlek, Song, and Chaudhuri [GSC17] were the first to study the posterior sampling with the81 RDP. Even though they provided a general framework to find (λ, )-RDP guarantees for exponential82 families, explicit forms of and the upper bound of λwere not given. In contrast, our tCDP guarantees83 of the Dirichlet posterior sampling imply an explicit expression for , and also an upper bound for λ.84
The privacy of data synthesis via sampling from Multinomial(Y), where Y is a discrete distri-85 bution drawn from the Dirichlet posterior, was first studied by Machanavajjhala, Kifer, Abowd,86 Gehrke, and Vilhuber [MKAGV08]. They showed that the data synthesis is (ε,δ)-probabilistic DP,87 which implies (ε,δ)-approximate DP. However, as their privacy analysis includes the sampling from88 Multinomial(Y), their privacy guarantee depends on the number of synthetic samples. In contrast,89 we show that the one-time sampling from the Dirichlet posterior is approximate DP, which by the90 post-processing property allows us to sample from Multinomial(Y) as many times as we want while91 retaining the same privacy guarantee.92
The Dirichlet mechanism was first introduced by Gohari, Wu, Hawkins, Hale, and Topcu [GWHHT21].93 Originally, the Dirichlet mechanism takes a discrete distribution p := (p1, . . . , pd) and draws one94 sample Y ∼ Dirichlet(rp1, . . . , rpd). Note the absence of the prior parameters, which makes Y an95 unbiased estimator of p. But this comes with a cost, as the worst case of privacy violation occurs96 when almost all of the parameters are close to zero. The authors avoided this issue by restricting97 the input space to a subset of the unit simplex, with some of the pi’s bounded below by a fixed98 positive constant. This results in complicated expressions for the privacy guarantees as they involve99 a minimization problem over the restricted domain. In this study, we take a different approach by100 adding prior parameters to the Dirichlet mechanism. As a result, we obtain a biased algorithm that101 requires no assumption on the input space and has simpler forms of privacy guarantees.102
1.3 Notations103
We let Rd≥0 be the set of d-tuples of non-negative real numbers and Rd>0 be the set of d-tuples of104 positive real numbers. We assume that all vectors are d-dimensional where d ≥ 2. The notations for105 all vectors are always in bold. Specifically, x := (x1, . . . , xd) ∈ Rd≥0 consists of sample statistics of106 the data and α := (α1, . . . , αd) ∈ Rd>0 consists of the prior parameters. The vector p := (p1, . . . , pd)107 always satisfies ∑ i pi = 1. The number of observations is always N . We also denote x0 := ∑ i xi108
and α0 := ∑ i αi. For any vectors x,x ′ and scalar r > 0, we write x+x′ := (x1 +x′1, . . . , xd +x ′ d)109 and rx := (rx1, . . . , rxd). For any positive reals x and x′, the notation x ∝ x′ means x = Cx′ for110 some constant C > 0, x ≈ x′ means cx′ ≤ x ≤ Cx′ for some c, C > 0, and x . x′ means x ≤ Cx′111 for some C > 0. Lastly, ‖x‖∞ := maxi|xi| is the `∞ norm of x.112
2 Background113
2.1 Privacy models114
Definition 2.1 (Pure and Approximate DP [DMNS06]). A randomized mechanism M : Xn → Y115 is (ε, δ)-differentially private ((ε, δ)-DP) if for any datasets x, x′ differing on a single entry, and all116 events E ⊂ Y ,117 P[M(x) ∈ E] ≤ eεP[M(x′) ∈ E] + δ. If M is (ε, 0)-DP, then we say that it is ε-differential privacy (ε-DP).118
The term pure differential privacy (pure DP) refers to -differential privacy, while approximate119 differential privacy (approximate DP) refers to (ε, δ)-DP when δ > 0.120
In contrast to pure and approximate DP, the next definitions of differential privacy are defined in121 terms of the Rényi divergence between M(x) and M(x′):122 Definition 2.2 (Rényi Divergence [Rén61]). Let P andQ be probability distributions. For λ ∈ (1,∞)123 the Rényi divergence of order λ between P and Q is defined as124
Dλ(P‖Q) := 1
λ− 1 log
∫ P (y)λQ(y)1−λ dy = 1
λ− 1 log ( E y∼P [ P (y)λ−1 Q(y)λ−1 ] . )
Definition 2.3 (tCDP and zCDP [BDRS18; BS16]). A randomized mechanism M : Xn → Y is125 ω-truncated ρ-concentrated differentially private ((ρ, ω)-tCDP) if for any datasets x, x′ differing on a126 single entry and for all λ ∈ (1, ω),127
Dλ(M(x)‖M(x′)) ≤ λρ. If M is (ρ,∞)-tCDP, then we say that it is ρ-zero-concentrated differential privacy (ρ-zCDP).128
Note that both tCDP and zCDP have the composition and post-processing properties. Intuitively, ρ con-129 trols the expectation and standard deviation of the privacy loss random variable: Z = log P [M(x)=Y ]P [M(x′)=Y ] ,130 where Y has density M(x), and ω controls the number of standard deviations for which Z concen-131 trates like a Gaussian. A smaller ρ and larger ω correspond to a stronger privacy guarantee. It turns132 out that tCDP implies approximate DP:133 Lemma 1 (From tCDP to Approximate DP [BDRS18]). Let δ > 0. IfM is a (ρ, ω)-tCDP mechanism,134 then it also satisfies (ε, δ)-DP with135
ε =
{ ρ+ 2 √ ρ log(1/δ) if log(1/δ) ≤ (ω − 1)2ρ
ρω + log(1/δ)ω−1 if log(1/δ) > (ω − 1) 2ρ .
2.2 Dirichlet distribution136
For α ∈ Rd>0, the Dirichlet distribution Dirichlet(α) is a continuous distribution of d-dimensional137 probability vectors i.e. vectors whose coordinate sum is equal to 1. The density function of Y ∼138 Dirichlet(α) is given by:139
p(y) = 1
B(α) d∏ i=1 yαi−1i ,
where B(α) is the beta function, which can be written in terms of the gamma function:140
B(α) =
∏ i Γ(αi)
Γ( ∑ i αi) . (1)
2.3 Dirichlet posterior sampling141
We consider the prior Dirichlet(α) and the likelihood of the form p(x|y) ∝ ∏d i=1 y xi i where142 x ∈ Rd≥0 consists of sample statistics of the dataset. The Dirichlet posterior sampling is a one-time143 sampling:144 Y ∼ Dirichlet(x + α). There is a modification of the sampling which introduces a concentration parameter r > 0, and145 instead we sample from Dirichlet(rx + α) [GSC17; GWHHT21]. Smaller values of r make the146 sampling more private, and larger values of r make Y a closer approximation of x. Even though the147 case r = 1 is the main focus of this study, our main privacy results can be easily extended to other148 values of r as we will see at the end of Section 3.1.149
Consider a special case where x = p is an empirical distribution derived from the dataset, and we150 want Y to be a private approximation of p; the sampling Y ∼ Dirichlet(rp + α) is called the151 Dirichlet mechanism [GWHHT21]. It is interesting to note that the Dirichlet mechanism is a form of152 the exponential mechanism [MT07]: let r > 0 be the privacy parameter, Dirichlet(α) be the prior,153 and the negative KL-divergence be the score function of the exponential mechanism. Then the output154 Y of this mechanism is distributed according to the following density function:155
exp(−rDKL(p,y)) ∏ i y αi−1 i∫
exp(−rDKL(p,y)) ∏ i y αi−1 i dy ∝ exp r ∑ i,pi 6=0 pi log(yi/pi) ∏ i yαi−1i
∝ ∏ i,pi 6=0 yrpii ∏ i yαi−1i = ∏ i yrpi+αi−1i ,
which is exactly the density function of Dirichlet(rp + α).156
2.4 Polygamma functions157
In most of this study, we take advantage of several nice properties of the log-gamma function and its158 derivatives. Specifically, ψ(x) := ddx log Γ(x) is concave and increasing, while its derivative ψ
′(x) is159 positive, convex, and decreasing. In addition, ψ′ can be approximated by the reciprocals:160
1 x + 1 2x2 < ψ′(x) < 1 x + 1 x2 ,
which implies that ψ′(x) ≈ 1x2 as x→ 0 and ψ ′(x) ≈ 1x as x→∞.161
3 Main privacy results162
3.1 Truncated concentrated differential privacy163
Theorem 1. Let α ∈ Rd>0 and αm := mini αi. Let γ ∈ (0, αm). Let ∆2,∆∞ > 0 be constants that164 satisfy ∑ i(xi − x′i)2 ≤ ∆22 and maxi |xi − x′i| ≤ ∆∞ whenever x,x′ ∈ R2≥0 are sample statistics165 of any two datasets differing on a single entry. The one-time sampling from Dirichlet(x + α) is166 (ρ, ω)-tCDP, where ω = γ∆∞ + 1 and167
ρ = 1
2 ∆22ψ ′(αm − γ). (2)
Note that (ρ,∞)-tCDP is not obtainable, as the ratio between two Dirichlet densities blows up as168 ω →∞. We present here a short proof that skips some calculations (see Appendix 1 for a full proof).169
proof. Consider any λ ∈ ( 1, γ∆∞ + 1 )
. Let u := x+α and u′ := x′ +α′. Let P (y) be the density170 of Dirichlet(u) and P ′(y) be the density of Dirichlet(u′). A quick calculation shows that:171
Ey∼P (y) [ P (y)λ−1
P ′(y)λ−1
] = B(u′)λ−1
B(u)λ−1 · B(u + (λ− 1)(u− u ′)) B(u) . (3)
We take the logarithm on both sides and apply the second-order Taylor expansion to the following172 G(ui, u ′ i) and H(ui, u ′ i) terms that appear on the right-hand side. As a result, there exist ξ between173 ui + (λ− 1)(ui − u′i) and ui, and ξ′ between ui and u′i such that174 G(ui, u ′ i) := (λ− 1)(log Γ(u′i)− log Γ(ui))
= −(λ− 1)(xi − x′i)ψ(ui) + 1
2 (λ− 1)(xi − x′i)2ψ′(ξ′) (4)
H(ui, u ′ i) := log Γ(ui + (λ− 1)(ui − u′i))− log Γ(ui)
= (λ− 1)(xi − x′i)ψ(ui) + 1
2 (λ− 1)2(xi − x′i)2ψ′(ξ), (5)
Note that ψ′ is increasing. If xi > x′i, then ξ and ξ ′ are bounded below by u′i ≥ αm. On the175 other hand, if xi ≤ x′i, then ξ and ξ′ are bounded below by ui − (λ − 1)|ui − u′i|. The condition176 λ < γ∆∞ + 1 guarantees that ui − (λ− 1)|ui − u ′ i| > αm − γ. All cases considered, we have177
G(ui, u ′ i) +H(ui, u ′ i) ≤
1
2
( (λ− 1) + (λ− 1)2 ) (xi − x′i)2ψ′(αm − γ)
= 1
2 λ(λ− 1)(xi − x′i)2ψ′(αm − γ). Denoting u0 := ∑ i ui and u ′ 0 := ∑ i u ′ i, the same argument shows that G(u0, u ′ 0) +H(u0, u ′ 0) > 0.178 Therefore,179
Dλ(P (y)‖P ′(y)) = 1
λ− 1 (∑ i (G(ui, u ′ i) +H(ui, u ′ i))−G(u0, u′0)−H(u0, u′0) )
< 1 λ− 1 ∑ i (G(ui, u ′ i) +H(ui, u ′ i))
≤ 1 2 λ ∑ i (xi − x′i)2ψ′(αm − γ) ≤ 1 2 λ∆22ψ ′(αm − γ).
The guaranteed upper bound (2) is independent of the sample statistics. As a result, the bound applies180 even in worst settings i.e., when xi = 0 and x′i = ∆∞, or vice versa, for some i. As we can see in181 Figure 1, the upper bound is a close approximation to the actual value of ρ when x6 = 0 and x′6 = 1.182 However, being a sample independent bound, the difference becomes substantial when all xi’s are183 large. There is one way to get around this issue: if there is no privacy violation in assuming that184 the sample statistics are always bounded below by some threshold τ , then we can incorporate the185 threshold into the prior (thus ψ′(αm − γ) in (2) is replaced by ψ′(αm + τ − γ)).186
The parameter γ allows us to adjust the moment bound ω as desired. Even though a higher ω usually187 leads to a better privacy guarantee, there are two downsides to picking γ close to αm in this case.188 First, note that ρ contains ψ′(αm− γ); as γ → αm, the value of ρ diverges to∞, leading to a weaker189 privacy guarantee instead. Second, as the Taylor approximation (5) is accurate when ui is close to190 ui + (λ− 1)(ui − u′i), having a large value of λ would push the guaranteed upper bound away from191 the actual privacy loss. Thus it is recommended to pick γ so that γ/∆∞ ≥ 1 and αm − γ 0.192 Alternatively, we can choose the value of γ that minimizes ε when converting from tCDP to (ε, δ)-DP193 using Lemma 1—this method will be explored in the next subsection.194
Theorem 1 can be easily applied to sampling from Dirichlet(rx+α). Replacing x with rx, we have195 ∆2 replaced by r∆2 and ∆∞ replaced by r∆∞. Consequently, the sampling is ( ρ, γr∆∞ + 1 ) -tCDP,196
where ρ = 12r 2∆22ψ ′(αm − γ). In Appendix 4, we analyze the scaling of r in conjunction with αm197 at a fixed privacy budget ρ.198
3.2 Approximate differential privacy199
We now convert the tCDP guarantee to an approximate DP guarantee. Let δ ∈ (0, 1). Using Lemma 1,200 the Dirichlet posterior sampling with Dirichlet(α) as the prior is (ε, δ)-DP with201
ε =
{ ρ(γ) + 2 √ ρ(γ) log(1/δ) if log(1/δ) ≤ γ2ρ(γ)/∆2∞
ρ(γ) (
γ ∆∞
+ 1 )
+ log(1/δ)∆∞γ if log(1/δ) > γ 2ρ(γ)/∆2∞
, (6)
where ρ(γ) = 12∆ 2 2ψ ′(αm − γ).202
We try to minimize by adjusting the value of γ. First, we consider the case log(1/δ) ≤ γ2ρ(γ)/∆2∞.203 Since ρ(γ) is a strictly increasing function of γ, both ρ(γ) + 2 √ ρ(γ) log(1/δ) and γ2ρ(γ)/∆2∞204 are both strictly increasing function of γ. Therefore, ε is minimized at the minimum possible205 value of γ in this case, that is, at the unique γM that satisfies log(1/δ) = γ2Mρ(γM )/∆ 2 ∞ =206
1 2γ 2 M∆ 2 2ψ ′(αm − γM )/∆2∞.207
Now we consider the second case, when γ < γM . As ρ(γ) is an increasing positive convex function208 of γ, the function209
f(γ) := 1
2 ∆22ψ
′(αm − γ) ( γ
∆∞ + 1
) +
log(1/δ)∆∞ γ ; γ ∈ (0, γM ], (7)
is also convex in γ, and thus has a unique minimizer γm ∈ (0, γM ]. Comparing to the first case, we210 have f(γm) ≤ f(γM ) = ρ(γM ) + 2 √ ρ(γM ) log(1/δ). We then conclude that ε = f(γm).211 Theorem 2. Let α ∈ R2>0 and denote αm = mini αi. Let ∆2,∆∞ > 0 be constants that satisfy212 ∑ i(xi − x′i)2 ≤ ∆22 and maxi |xi − x′i| ≤ ∆∞ whenever x,x′ ∈ Rd≥0 are sample statistics of any213 two datasets differing on a single entry. For any δ ∈ (0, 1), let γM be the solution to the equation214 log(1/δ) = 12γ 2∆22ψ ′(αm − γ)/∆2∞. The one-time sampling from Dirichlet(x + α) is (ε, δ)-DP,215 where216 ε = min
γ∈(0,γM ] f(γ). (8)
Figure 1 shows how δ decays as a function of ε at three different values of αm.217
4 Utility218
Using the results from the previous section, we analyze the Dirichlet posterior sampling’s utility in219 two specific tasks.220
4.1 Multinomial-Dirichlet sampling221
Suppose that we are observing N trials, each of which has d possible outcomes. For each i ∈222 {1, . . . , d}, let xi be the number of times the i-th outcome was observed. Then we have the223 multinomial likelihood p(x|y) ∝ ∏ i y xi i . From this, we sample from the Dirichlet posterior:224
Y ∼ Dirichlet(x + α). (9)
Suppose that we want to sample from a true distribution PX ∼ Dirichlet(x + α), but for privacy225 reasons, we instead sample from Qx ∼ Dirichlet(x + α′) where α′i > αi for all i. The utility of the226 privacy scheme is then measured by the KL-divergence between Px and Qx. Assuming that x is an227 observation of Multinomial(p), the following Theorem tells us that, on average, the KL-divergence228 is small when the sample size is large, and the pi’s are evenly distributed.229 Theorem 3. Let p := (p1, . . . , pd) where pi > 0 for all i and ∑ i pi = 1. Define a random230 variable X ∼ Multinomial(p). Let PX ∼ Dirichlet(X + α) and QX ∼ Dirichlet(X + α′) where231 α′i ≥ αi ≥ 1 for all i. The following estimate holds:232
EX[DKL(PX‖QX)] ≤ 1
N + 1 ∑ i (α′i − αi)2 · 1 pi . (10)
The proof is given in Appendix 2. Let us consider a simple privacy scheme where we fix s > 0 and233 let α′i = αi + s for all i. Thus (10) becomes:234
EX[DKL(PX‖QX)] ≤ G(p)s2
N + 1 , (11) where G(p) := ∑ i 1/pi. Now we take into account the privacy parameters. Let ρ = ∆ 2 2ψ ′(αm − γ)235
and ρ′ = ∆22ψ ′(α′m−γ), where αm = mini αi, α′m = mini α′i, and γ < αm. Here, we approximate236 the values of ψ′(αm − γ) and ψ′(α′m − γ) under two regimes:237
High-privacy regime: α′m − γ > 1. We have ψ′(α′m − γ) ≈ 1/(α′m − γ), which implies238 α′m−γ ≈ ∆22/ρ′. We also have αm−γ ≈ ∆22/ρ for αm−γ ≥ 1 and αm−γ > (αm−γ)2 ≈ ∆22/ρ239 for α− γ < 1. Thus we have the following bound for the right-hand side of (11):240
G(p)s2 N + 1 = G(p)(α′m − αm)2 N + 1 . ∆42G(p) N + 1
( 1
ρ′ − 1 ρ
)2 < ∆42G(p)
ρ′2(N + 1) . (12) Consequently, we have DKL(P‖Q) < for N = Ω ( ∆42G(p) ρ′2 ) .241
Low-privacy regime: 1 > α′m − γ > 0. This is similar as above, except we have α′m − γ ≈242 ∆2/ρ
′1/2 and αm − γ ≈ ∆2/ρ1/2. Similar computation as (12) shows that DKL(P‖Q) < when243 N = Ω ( ∆22G(p) ρ′ ) .244
We observe that, in both regimes, the sample size scales faster with respect to with a higher value of245 G(p), which is associated with a higher number of outcomes d, and more concentrated multinomial246 parameter p; this agrees with the result of our simulation in Appendix 3. Moreover, for small ρ′ the247 sample size scales as 1/ρ′2, while for large ρ′ the sample size scales as 1/ρ′.248
4.2 Private normalized histograms249
Let x = (x1, . . . , xd) be a histogram of N observations and p := x/N . We can privatize p by250 sampling a probability vector: Y ∼ Dirichlet(x + α). Note that Y is a biased estimator of p.251 Denoting α0 := ∑ i αi, the bias of each component of Y is given by E[Y]− pi. Hence,252
|Bias(Yi)| = ∣∣∣∣ xi + αiN + α0 − pi ∣∣∣∣ = |xiα0 −Nαi|N(N + α0) ≤ Nα0N(N + α0) = α0N + α0 . Since Yi ∼ Beta(xi + αi, N + α0 − xi − αi) is 14(N+α0+1) -sub-Gaussian [MA17], we have,253
P[|Yi − pi| > t+ |Bias(Yi)|] ≤ P[|Yi − E[Yi]|+ |Bias(Yi)| > t+ |Bias(Yi)|] = P[|Yi − E[Yi]| > t]
≤ 2e−2t 2(N+α0+1). With the union bound, we plug in t = √
log(2d/β) 2(N+α0+1) , for any β ∈ (0, 1), to obtain the following254 accuracy guarantee of the private normalized histogram:255 Theorem 4. Let Y ∼ Dirichlet(x + α), where x ∈ Rd≥0 and α ∈ Rd>0, and p := x/N . For any256 β ∈ (0, 1), with probability at least 1− β, the following inequality holds:257
‖Y − p‖∞ ≤
√ log(2d/β)
2(N + α0 + 1) + α0 N + α0 . (13)
Given > 0, we use (13) to find a lower bound for N that gives ‖Y − p‖∞ < w.p. 1− β when258 Y is sampled with ρ-tCDP. For simplicity, we consider a uniform prior: αi = α > 0 for all i.259 Thus, ρ = 12∆ 2 2ψ ′(α− γ), where γ might be chosen according to Corollary 2. We consider the two260 following regimes:261
High-privacy regime: α−γ > 1. In this case, ψ′(α−γ) ≈ 1/(α−γ). From ρ = 12∆ 2 2ψ ′(α−γ),262 we have α ≈ ∆22/2ρ+ γ. Replacing α0 by dα in (13) yields the sample size:263
N = Ω
( log(2d/β)
2 + d ( ∆22 2ρ + γ )) , (14)
for the desired accuracy.264
Low-privacy regime: α − γ < 1. This is the same as above, except now we have ψ′(α − γ) ≈265 1/(α − γ)2, which implies α ≈ ∆2/(2ρ)1/2 + γ. The sample size that guarantees the desired266 accuracy is:267
N = Ω
( log(2d/β)
2 + d ( ∆2√ 2ρ + γ )) . (15)
Let us compare this result to the Gaussian mechanism, which adds a noise Z ∼ N(0, σ2Id) to the268 normalized histogram p directly. Thus the `2-sensitivity in this case is ∆2/N . We have that the269 Gaussian mechanism is ρ-zCDP where ρ = ∆ 2
2N2σ2 [BS16]. Using the same argument as above, with270 probability at least 1− β, the following inequality holds for all i:271
‖Z‖∞ ≤
√ log(2d/β)∆22
N2ρ . (16)
Hence, the sample size of N = Ω
(√
log(2d/β)∆22/ρ 2
)
guarantees the desired accuracy. Compar-272 ing this to (14), if we assume < 1, the AM-GM inequality tells us that273
log(2d/β) 2 + d∆22 ρ > log(2d/β) 2 + ∆22 ρ ≥ 2
√ log(2d/β)∆22
ρ 2 . (17)
The inequality (17) implies that the Gaussian mechanism requires less sample than the Dirichlet274 mechanism in order to guarantee the same level of accuracy. The Gaussian mechanism is also better275 in the low-privacy regime as the ρ in (15) satisfies √ ρ < ρ and ∆2 ≈ ∆22, leading to the same276 inequality (17). Nonetheless, the decay in (16) is linear in d, while that in (13) has α0 = dα in277 the denominators. This observation suggests that, when x is a sparse histogram i.e. when N ≤ d,278 the `∞-accuracy of the Dirichlet mechanism is smaller than that of the Gaussian mechanism. This279 conclusion is supported by our simulation in Figure 2. We see that the `∞-accuracy of the Dirichlet280 mechanism is smaller than that of the Gaussian mechanism for small N when d = 1000. The code281 for all experiments in this study can be found in the supplemental material.282
Potential negative societal impacts283
It is important to note that, when ρ becomes unacceptably large (e.g., ρ = 104), the sampling is far284 away from being private. Thus any organization that deploys the posterior sampling on sensitive data285 must not vacuously refer to this study and claim that its algorithm is private. It is the organization’s286 responsibility to fully publish the prior parameters, and educate its users/customers on differential287 privacy and how the privacy guarantees are calculated.288
It is desirable that differentially private algorithms are accurate for the task at hand, especially when289 the data is used for important decision-making. Thus, one needs to make sure that there is enough290 sample to achieve the desired level of accuracy. For a large differentially private system, privacy291 budgets need to be allocated to the parts that require accurate outputs.292
Lastly, one must be careful with the choice of prior parameters; if a uniform prior is used, smaller293 groups will suffer a relatively larger statistical bias. As a result, private statistics of small populations294 (such as ethnic or racial minorities) will be relatively less accurate. One way to get around this issue295 is to (privately) impose larger prior parameters on larger populations.296
References297 [AAFK20] I. Aykin, B. Akgun, M. Feng, and M. Krunz. “MAMBA: A Multi-armed Bandit Framework for298 Beam Tracking in Millimeter-wave Systems”. In: 39th IEEE Conference on Computer Com-299 munications, INFOCOM 2020, Toronto, ON, Canada, July 6-9, 2020. IEEE, 2020, pp. 1469–300 1478.301
[AV08] J. M. Abowd and L. Vilhuber. “How Protective Are Synthetic Data?” In: Privacy in Statistical302 Databases, UNESCO Chair in Data Privacy International Conference, PSD 2008, Istan-303 bul, Turkey, September 24-26, 2008. Proceedings. Ed. by J. Domingo-Ferrer and Y. Saygin.304 Vol. 5262. Lecture Notes in Computer Science. Springer, 2008, pp. 239–246.305
[BDRS18] M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke. “Composable and versatile privacy via306 truncated CDP”. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of307 Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018. Ed. by I. Diakonikolas,308 D. Kempe, and M. Henzinger. ACM, 2018, pp. 74–86.309
[BHW00] R. J. Boys, D. A. Henderson, and D. J. Wilkinson. “Detecting Homogeneous Segments in DNA310 Sequences by Using Hidden Markov Models”. In: Journal of the Royal Statistical Society.311 Series C (Applied Statistics) 49.2 (2000), pp. 269–285. ISSN: 00359254, 14679876.312
[BS16] M. Bun and T. Steinke. “Concentrated Differential Privacy: Simplifications, Extensions, and313 Lower Bounds”. In: Theory of Cryptography. Ed. by M. Hirt and A. Smith. Berlin, Heidelberg:314 Springer Berlin Heidelberg, 2016, pp. 635–658.315
[BS18] G. Bernstein and D. R. Sheldon. “Differentially Private Bayesian Inference for Exponential316 Families”. In: Advances in Neural Information Processing Systems 31: Annual Conference on317 Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal,318 Canada. Ed. by S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and319 R. Garnett. 2018, pp. 2924–2934.320
[CWS03] J. Corander, P. Waldmann, and M. J. Sillanpää. “Bayesian Analysis of Genetic Differentiation321 Between Populations”. In: Genetics 163.1 (Jan. 2003), pp. 367–374. ISSN: 1943-2631.322
[de 06] M. de Lapparent. “Empirical Bayesian analysis of accident severity for motorcyclists in large323 French urban areas”. In: Accident Analysis & Prevention 38.2 (2006), pp. 260–268. ISSN:324 0001-4575.325
[DMNS06] C. Dwork, F. Mcsherry, K. Nissim, and A. Smith. “Calibrating noise to sensitivity in private326 data analysis”. In: TCC. 2006.327
[DNZMR17] C. Dimitrakakis, B. Nelson, Z. Zhang, A. Mitrokotsa, and B. I. P. Rubinstein. “Differential328 Privacy for Bayesian Inference through Posterior Sampling”. In: J. Mach. Learn. Res. 18329 (2017), 11:1–11:39.330
[FGWC16] J. R. Foulds, J. Geumlek, M. Welling, and K. Chaudhuri. “On the Theory and Practice of331 Privacy-Preserving Bayesian Data Analysis”. In: Proceedings of the Thirty-Second Conference332 on Uncertainty in Artificial Intelligence, UAI 2016, June 25-29, 2016, New York City, NY, USA.333 Ed. by A. T. Ihler and D. Janzing. AUAI Press, 2016.334
[GSC17] J. Geumlek, S. Song, and K. Chaudhuri. “Renyi Differential Privacy Mechanisms for Posterior335 Sampling”. In: Advances in Neural Information Processing Systems 30: Annual Conference336 on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA.337 Ed. by I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan,338 and R. Garnett. 2017, pp. 5289–5298.339
[GWHHT21] P. Gohari, B. Wu, C. Hawkins, M. T. Hale, and U. Topcu. “Differential Privacy on the Unit340 Simplex via the Dirichlet Mechanism”. In: IEEE Trans. Inf. Forensics Secur. 16 (2021),341 pp. 2326–2340.342
[Hin15] K. Hines. “A Primer on Bayesian Inference for Biophysical Systems”. In: Biophysical Journal343 108.9 (2015), pp. 2103–2113. ISSN: 0006-3495.344
[LW92] M. Lavine and M. West. “A Bayesian method for classification and discrimination”. In:345 Canadian Journal of Statistics 20.4 (1992), pp. 451–461.346
[MA17] O. Marchal and J. Arbel. “On the sub-Gaussianity of the Beta and Dirichlet distributions”. In:347 Electronic Communications in Probability 22.none (2017), pp. 1 –14.348
[MKAGV08] A. Machanavajjhala, D. Kifer, J. M. Abowd, J. Gehrke, and L. Vilhuber. “Privacy: Theory349 meets Practice on the Map”. In: Proceedings of the 24th International Conference on Data350 Engineering, ICDE 2008, April 7-12, 2008, Cancún, Mexico. Ed. by G. Alonso, J. A. Blakeley,351 and A. L. P. Chen. IEEE Computer Society, 2008, pp. 277–286.352
[MMR05] J.-M. Marin, K. Mengersen, and C. P. Robert. “Bayesian Modelling and Inference on Mixtures353 of Distributions”. In: Bayesian Thinking. Ed. by D. Dey and C. Rao. Vol. 25. Handbook of354 Statistics. Elsevier, 2005, pp. 459–507.355
[MT07] F. McSherry and K. Talwar. “Mechanism Design via Differential Privacy”. In: 48th Annual356 IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007,357 Providence, RI, USA, Proceedings. IEEE Computer Society, 2007, pp. 94–103.358
[NIK20] I. Nasim, A. S. Ibrahim, and S. Kim. “Learning-Based Beamforming for Multi-User Vehicular359 Communications: A Combinatorial Multi-Armed Bandit Approach”. In: IEEE Access 8 (2020),360 pp. 219891–219902.361
[NLYCC13] V. C. Nguyen, W. S. Lee, N. Ye, K. M. A. Chai, and H. L. Chieu. “Active Learning for362 Probabilistic Hypotheses Using the Maximum Gibbs Error Criterion”. In: Advances in Neural363 Information Processing Systems 26: 27th Annual Conference on Neural Information Processing364 Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada,365 United States. Ed. by C. J. C. Burges, L. Bottou, Z. Ghahramani, and K. Q. Weinberger. 2013,366 pp. 1457–1465.367
[ORR13] I. Osband, D. Russo, and B. V. Roy. “(More) Efficient Reinforcement Learning via Poste-368 rior Sampling”. In: Advances in Neural Information Processing Systems 26: 27th Annual369 Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held370 December 5-8, 2013, Lake Tahoe, Nevada, United States. Ed. by C. J. C. Burges, L. Bottou,371 Z. Ghahramani, and K. Q. Weinberger. 2013, pp. 3003–3011.372
[PB98] T. Pedersen and R. F. Bruce. “Knowledge Lean Word-Sense Disambiguation”. In: Proceedings373 of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Appli-374 cations of Artificial Intelligence Conference, AAAI 98, IAAI 98, July 26-30, 1998, Madison,375 Wisconsin, USA. Ed. by J. Mostow and C. Rich. AAAI Press / The MIT Press, 1998, pp. 800–376 805.377
[PG14] Y. Park and J. Ghosh. “PeGS: Perturbed Gibbs Samplers that Generate Privacy-Compliant378 Synthetic Data”. In: Trans. Data Priv. 7.3 (2014), pp. 253–282.379
[PM01] J. Pella and M. Masuda. “Bayesian methods for analysis of stock mixtures from genetic380 characters”. English. In: Fishery Bulletin 99 (Jan. 2001). 1, p. 151. ISSN: 00900656.381
[Rén61] A. Rényi. “On measures of entropy and information”. In: Proceedings of the Fourth Berkeley382 Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory383 of Statistics. The Regents of the University of California. 1961.384
[RWZ14] J. P. Reiter, Q. Wang, and B. Zhang. “Bayesian Estimation of Disclosure Risks for Multiply385 Imputed, Synthetic Data”. In: J. Priv. Confidentiality 6.1 (2014).386
[SJGLY17] M. J. Schneider, S. Jagpal, S. Gupta, S. Li, and Y. Yu. “Protecting customer privacy when387 marketing with second-party data”. In: International Journal of Research in Marketing 34.3388 (2017), pp. 593–603. ISSN: 0167-8116.389
[Str00] M. J. A. Strens. “A Bayesian Framework for Reinforcement Learning”. In: Proceedings of the390 Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University,391 Stanford, CA, USA, June 29 - July 2, 2000. Ed. by P. Langley. Morgan Kaufmann, 2000,392 pp. 943–950.393
[WFS15] Y. Wang, S. E. Fienberg, and A. J. Smola. “Privacy for Free: Posterior Sampling and Stochastic394 Gradient Monte Carlo”. In: Proceedings of the 32nd International Conference on Machine395 Learning, ICML 2015, Lille, France, 6-11 July 2015. Ed. by F. R. Bach and D. M. Blei. Vol. 37.396 JMLR Workshop and Conference Proceedings. JMLR.org, 2015, pp. 2493–2502.397
[ZHGSY20] J. Zhu, X. Huang, X. Gao, Z. Shao, and Y. Yang. “Multi-Interface Channel Allocation in Fog398 Computing Systems using Thompson Sampling”. In: 2020 IEEE International Conference on399 Communications, ICC 2020, Dublin, Ireland, June 7-11, 2020. IEEE, 2020, pp. 1–6.400
Checklist401
1. For all authors...402
(a) Do the main claims made in the abstract and introduction accurately reflect the paper’s403 contributions and scope? [Yes] We gave a simple guaranteed upper bound of tCDP (2)404 for the Dirichlet posterior sampling and illustrated how it can be used to derive accuracy405 guarantees in Section 4.406
(b) Did you describe the limitations of your work? [Yes] We discussed a limitation of407 the guaranteed upper bound of tCDP in the paragraph following Theorem 1. We also408 described a situation under which the Gaussian mechanism is preferable to the Dirichlet409 posterior sampling at the end of Section 4.2.410
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the411 section on potential negative societal impacts at the end of the paper.412
(d) Have you read the ethics review guidelines and ensured that your paper conforms to413 them? [Yes]414
2. If you are including theoretical results...415
(a) Did you state the full set of assumptions of all theoretical results? [Yes]416 (b) Did you include complete proofs of all theoretical results? [No] The proofs of all417 theorems are given in the main paper, except that of Theorem 3 which is given in418 Appendix 2.419
3. If you ran experiments...420
(a) Did you include the code, data, and instructions needed to reproduce the main experi-421 mental results (either in the supplemental material or as a URL)? [Yes] The code and422 the instructions for our simulations are included in the supplemental material.423
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they424 were chosen)? [Yes] We specified the details of our simulations in the figures’ captions.425
(c) Did you report error bars (e.g., with respect to the random seed after running experi-426 ments multiple times)? [Yes] We reported the error bars in Figure 2427
(d) Did you include the total amount of compute and the type of resources used (e.g.,428 type of GPUs, internal cluster, or cloud provider)? [N/A] Our experiments are not429 computationally intensive.430
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...431
(a) If your work uses existing assets, did you cite the creators? [N/A]432 (b) Did you mention the license of the assets? [N/A]433 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]434
435
(d) Did you discuss whether and how consent was obtained from people whose data you’re436 using/curating? [N/A]437
(e) Did you discuss whether the data you are using/curating contains personally identifiable438 information or offensive content? [N/A]439
5. If you used crowdsourcing or conducted research with human subjects...440
(a) Did you include the full text of instructions given to participants and screenshots, if441 applicable? [N/A]442
(b) Did you describe any potential participant risks, with links to Institutional Review443 Board (IRB) approvals, if applicable? [N/A]444
(c) Did you include the estimated hourly wage paid to participants and the total amount445 spent on participant compensation? [N/A]446

title: Differential Privacy of Dirichlet Posterior Sampling