$\bigstar\bigstar$=middle, $\bigstar\bigstar\bigstar$=high

Performance Measure | Supervised Detectors | Unsupervised Detectors
---|---|---
|  KD+BU feinman2017detecting |  LID ma2018characterizing |  NSS kherchouche2020detection |  FS xu2017feature |  MagNet meng2017magnet |  DNR sotgiu2020deep |  SFAD aldahdooh2021selective |  NIC ma2019nic
OV |  $\bigstar$ |  $\bigstar$ |  $\bigstar$ |  $\bigstar$ |  $\bigstar\bigstar$ |  $\bigstar\bigstar\bigstar$ |  $\bigstar\bigstar\bigstar$ |  $\bigstar\bigstar\bigstar$
CM |  $\bigstar\bigstar\bigstar$ |  $\bigstar\bigstar\bigstar$ |  $\bigstar\bigstar$ |  $\bigstar$ |  $\bigstar\bigstar$ |  $\bigstar\bigstar\bigstar$ |  $\bigstar\bigstar$ |  $\bigstar\bigstar\bigstar$
INF |  $\bigstar$ |  $\bigstar$ |  $\bigstar$ |  $\bigstar\bigstar$ |  $\bigstar\bigstar$ |  $\bigstar$ |  $\bigstar$ |  $\bigstar\bigstar\bigstar$

###  6.9 Performance on high resolution dataset

In this subsection, the efforts for testing the detection methods on ImageNet
imagenet_cvpr09 , as a high resolution dataset, will be discussed. Table 3
shows that few detectors were tested using ImageNet. ImageNet is a dataset
that contains 14 million images annotated with 1000 classes. It is widely used
in computer vision research. When it is used for training the neural networks,
the images are downsampled to $224\times 224$, $299\times 299$, or $384\times
384$ to match the model’s and computational requirements.

LID ma2018characterizing : ImageNet was considered in the experiments of
ma2019nic . It was shown that it does not scale well on ImageNet white box and
black box attacks. It achieves the detection rate 82% on average. The main
reason behind this is that ImageNet’s images contain more noises, which makes
it more difficult for LID to identify the boundaries between clean images and
adversarial images. Moreover, LID has high FPR, around 14.5%.

NSS kherchouche2020detection : ImageNet was considered in the experiments of
kherchouche2020detection , and it showed a limited success for CW attacks. It
achieves a detection rate of 84% with 6.2% FPR.

FS xu2017feature : ImageNet was considered in the experiments of ma2019nic .
It was shown that FS has similar low performance for FGSM and BIM based
attacks. It achieves 43% 64% of detection rates for FGSM and BIM attacks,
respectively.

MagNet meng2017magnet : In liao2018defense , it was shown that MagNet doesn’t
scale well for high resolution images and has high FPR. Besides denoiser-based
detectors requiring large computation power to be trained on large datasets,
and denoiser-based detectors have also be shown to not perform well against
$L_{0}$-norm attack.

DNR sotgiu2020deep and SFAD aldahdooh2021selective : SFAD is expected to
perform well specially for black box attacks and for CW, DF, and $L_{0}$
attacks, as discussed in Section 6.7. The main drawback of these detectors is
to train more 4 classifiers for the detection process, which is time
consuming.

NIC ma2019nic : It was shown in ma2019nic that NIC performs well on ImageNet
dataset but it has a high FPR, 14.6% on ResNet50, and has a high runtime
overhead that reaches 28% on ResNet50.

###  6.10 Other performance evaluations

Performance measures related to complexity (CM), overhead (OV) and inference
time latency (INF) is very important, but it is application dependent. For
KD+BU feinman2017detecting and LID ma2018characterizing detectors, to train
them with known attacks is time consuming taking into consideration that LID
requires more time. Their overhead is very small, since we need to save only
the classifier parameters, while the inference time is very small. NSS
kherchouche2020detection has middle complexity since it is trained only with
PGD-based AEs, and have very small overhead due to saving SVM classifier
parameters, and have no latency in the inference time since feature extraction
process can be done in parallel with the prediction process of the baseline
classifier. For FS xu2017feature , the training complexity is very low and has
no overhead, while it has middle inference time due to generating squeezed
images. MagNet meng2017magnet has middle complexity and overhead due to
denoiser training and its parameters saving, while it has small latency due to
the detection process coming before the reformer and the baseline prediction
processes. DNR sotgiu2020deep and SFAD aldahdooh2021selective have high and
middle complexity, respectively. Both have high overhead due to classifiers
parameters saving, and both have no inference time latency. Finally, NIC
ma2019nic has high complexity, overhead and latency than other detectors due
to per-layer classifiers training and parameters saving. Table 20 shows the
estimate of 3-star rank for each performance measure per detector.

###  6.11 Supervised vs. Unsupervised Detection

In this subsection, we discuss the effectiveness of supervised and
unsupervised detection methods with respect to the performance criteria that
are discussed in Section 4.

  * •

Efficiency: If the number of adversarial attacks algorithms is limited, it
would be more efficient to build supervised detection models. Unfortunately,
this is not the case, hence, putting more efforts to build unsupervised
detection models is more effective since it has the power to model the normal
samples distributions and features space, as in LID and SFAD, and to detect
samples that lie out of this distribution and feature space. That will be more
effective in order to detect unknown attacks, especially the black box
attacks.

  * •

Overhead: The main price that the unsupervised detection models pay is the
overhead. Most of the unsupervised detection models learn extra models to help
the baseline model to detect the AEs. The extra models need an additional
storage space to be stored in which might not be applicable in some devices
and systems. LID, for instance, models the distribution of normal samples for
each layer. Moreover, DNR and SFAD model the features space of some layers,
which requires additional storage space.

  * •

Complexity: There is no preference with respect to the complexity issues. It
highly depends on the complexity of implemented algorithms. For instance, FS
doesn’t have any training and depends on the predicted scores of the
transformed samples. On the other hand, NSS, MagNet, and SFAD have modest
complexity if they are compared with NIC and LID. The source of complexity in
NIC came from the training models for each layer, while the complexity source
in LID came from the features extraction processes that are required for
training.

  * •

Inference time: Detection techniques have access to the baseline model outputs
at different layers, which facilitates working in parallel with the baseline
models. Supervised detection methods take advantage of such parallelism and
don’t compromise inference time constraints, while some unsupervised detection
methods, such as FS, MagNet, and NIC compromise the inference time
constraints. FS has first to apply many transformation methods before running
the detection. MagNet has first to apply the detection and then run the
baseline model for the prediction. NIC has to wait until all layers run the
corresponding detection model and then combine all model results to run the
final prediction. This extra latency is not suitable for real time
applications.

  * •

False positive rate: There is no preference for any category with respect to
false positive rate values. It highly depends on the implemented algorithm.
For instance LID, NSS, and SFAD have high FPR for Tiny-ImageNet dataset.

###  6.12 Content, CNN, and Detectors related discussion

In the adversarial detection systems, we have 4 main players, content of clean
images, content of attacked image, the baseline classifier and the detection
method in play. In this section, we provide our observations with respect to
each player. We follow our demonstration using visualisations that are
generated using gradient-weighted class activation mapping (Grad-CAM)
selvaraju2016grad and back-propagation based saliency springenberg2014striving
. Grad-CAM uses the gradients of any target class flowing into the final
convolutional layer to produce a coarse localization map highlighting the
important regions in the image for predicting the class. Back-propagation
based saliency is a variant of the deconvolution approach for visualizing
features learned by CNNs. Figures 5, 6, 7 and 8 show different visualization
methods for MNIST and CIFAR datasets. First column is the original/clean or
attacked image sample. MNIST images displayed with ‘viridis’ colormap. The
second column is the representative output of a specified layer of baseline
classifier. The third column is the heatmap generated with Grad-CAM technique.
Fourth column is a combination of the heatmap and the corresponding original
or attacked image. The fifth column is the saliency map generated with back-
propagation technique, while the last column is the combination of the
saliency and the Grad-CAM heatmap. Many observations can be concluded from
these figures:

  1. 1.

The saliency regions of MNIST dataset are morerestricted to the number regions
that cover the whole image, while the saliency regions of CIFAR dataset span
beyond the target object, i.e., the texture around the target object. Thus, 1)
this will maximize the probability of distracting the CNN model by giving
importance to non-relevant regions, and 2) any small perturbation added to
such images will highly affect its saliency and, as a consequence, the CNN
will target another prediction class.

  2. 2.

Looking at the Grad-CAM and guided Grad-CAM, we can notice that the CNN does
not necessarily use saliency regions of clean images in predicting the correct
class. This happens due to the use of complex/over-parametrized classifiers to
solve not complex tasks madry2017towards . Hence, CNNs are vulnerable to small
perturbation that will cause higher loss than of clean samples. This can be
confirmed as well by looking at the Grad-CAM and the guided Grad-CAM of the
AEs and notice that different small perturbations from different attacks yield
different Grad-CAM and guided Grad-CAM.

  3. 3.

Most of AEs detectors solutions rely on that the representative CNN layers
output of adversarial input is significantly different from clean input, which
is a true assumption. For MNIST, it was easy for most of the detectors to
detect the AEs, while for other datasets, detectors are not able to detect AEs
effectively? That might be due to 1) dataset has noisy samples, 2) CNNs either
very complex or very over-parametrized, 3) the behaviors of the CNN with
respect to the content itself of clean and adversarial inputs, for instance,
in the case where the guided Grad-CAM, i.e., important regions, of the AE is
slightly changed from the clean one, the detector work became much harder.

Figure 5: MNIST dataset original samples visualization. First column is the
original/clean image sample. The second column is the representative output of
the $10^{th}$ layer of baseline classifier. The third column is the heatmap
generated with Grad-CAM technique. Fourth column is a combination of the
heatmap and the corresponding original image. The fifth column is the Saliency
map generated with Back-propagation technique while the last column is the
combination of the saliency and the Grad-CAM heatmap. Figure 6: MNIST dataset
original and adversarial samples visualization. First column is the
original/clean or attacked image sample. The second column is the
representative output of the $10^{th}$ layer of baseline classifier. The third
column is the heatmap generated with Grad-CAM technique. Fourth column is a
combination of the heatmap and the corresponding original or attacked image.
The fifth column is the Saliency map generated with Back-propagation technique
while the last column is the combination of the saliency and the Grad-CAM
heatmap. Figure 7: CIFAR dataset original samples visualization. First column
is the original/clean image sample. The second column is the representative
output of the $27^{th}$ layer of baseline classifier. The third column is the
heatmap generated with Grad-CAM technique. Fourth column is a combination of
the heatmap and the corresponding original image. The fifth column is the
Saliency map generated with Back-propagation technique while the last column
is the combination of the saliency and the Grad-CAM heatmap. Figure 8: CIFAR
dataset original and adversarial samples visualization. First column is the
original/clean or attacked image sample. The second column is the
representative output of the $27^{th}$ layer of baseline classifier. The third
column is the heatmap generated with Grad-CAM technique. Fourth column is a
combination of the heatmap and the corresponding original or attacked image.
The fifth column is the Saliency map generated with Back-propagation technique
while the last column is the combination of the saliency and the Grad-CAM
heatmap.

##  7 Challenges, future perspectives, and conclusion

###  7.1 Challenges and future perspectives

The problem of adversarial examples is not yet solved. Figure 4 show that most
of the detectors are not robust against new/unknown attacks. Moreover,
findings from carlini2017adversarial ; athalye2018obfuscated show that the
defenses and the detectors are vulnerable to the carefully designed
adversarial perturbations. Hence, we can conclude that, to date, there are no
robust defenses and detectors and more investigations are required to identify
the features of the AEs. Such features will facilitate the design of robust
defense and detection techniques. Moreover, researchers are facing many
questions and challenges that are still open. Here we highlight them:

Supervised or Unsupervised detection? This is a confusing question. Supervised
detection methods have, in general, better performance evaluation due to the
detector capability to learn from labeled clean and AEs training data, but
this is much restricted to known attacks and cannot be generalized to all
kinds of attacks. Relatively, unsupervised detection method is much more
flexible since it relies only on the clean data. The main two challenges of
the unsupervised approach are 1) tuning its hyper-parameters is very
challenging since it cannot be generalized to all models and datasets. 2)
finding discriminating features for clean data that are not sensitive to noise
and data processing like compression, for instance. As a recommendation, we
need to focus on unsupervised detection methods. As discussed in Section 4,
each unsupervised method proposed a way to detect the AEs and here is another
confusing question, Which one to use? Denoiser based is much more effective if
the denoiser has a good estimation of the training data and it does not
require manual parameter tuning. Similar to denoiser based approaches, FS is
highly dependent on the squeezer quality. These two approaches are not
computationally expensive but have some inference test time latency. The
statistical methods are effective in estimating training data distribution but
it is not effective in large-scale applications with large amount of data and
classes. It is time consuming in the training phase and has no inference test
time latency. Most auxiliary models and NIC approaches depend on the
underlying techniques and they require a lot of hyper-parameters tuning to be
suitable for different DL based applications. Consequently, we leave the
choice of the model to the application requirement.

Generalization. The wide view of generalization is the capability of the
detector to detect white, black, gray (transferability) box attacks, and
counter-counter attacks. The reported performance in Section 5 shows that we
still need more research efforts to push detectors towards the generalization.

Lightweight detection. Lightweight detector is a detector that 1) has very
small overhead, 2) has no inference time latency and 3) is not time consuming
in training phase (some industries don’t care about that). According to the
reported results of the reviewed detector, one of these factors is
compromised. Thus, detectors that trade-off between these factors are highly
recommended.

Ensemble Detection. It is believed that ensemble techniques can boost one
detection technique. For instance,SFAD model used ensemble detection
methods,selective/uncertainty prediction, softmax based predictionand bi-match
prediction. These techniques are jointly integrated and give promised results
with a little price to FPR. Hence, ensemble detection is highly recommended
without compromising the FPR.

Meet the defense. As discussed in the Section 1, defense techniques,
especially robust classification techniques, try to correctly classify input
samples, whether attacked or not. Providing defense and detection jointly is
an added value to the deployed model since it makes the adversary work much
harder. In this approach, the adversary tries to generate AE with more
perturbation to fool the defense, but in this case, it will be easy for the
detector to detect it.

Training data Matters? Yes, the training data plays an important role.
Firstly, not noisy training data helps a lot in understanding and recognizing
AE features and properties in supervised and unsupervised detection methods.
Secondly, findings in schmidt2018adversarially show that adversarially robust
generalization requires more data. Hence, enough data helps in building CNN
and detectors that generalize well. Finally, the designed CNN should be
suitable and not complex with respect to the training data and the
classification task.

Consider high resolution data. As discussed in Section 6.9, detectors face a
huge challenge when they are tested on high resolution data such as ImageNet.
They might be not effective, have high FPR, have high overhead, or/and are
time consuming. Designing effective detectors for high resolution data is
highly required.

###  7.2 Conclusion

This paper reviewed the detection methods of evasion attacks for neural
networks classifiers of image classification task. We firstly categorized the
AE detection methods into supervised and unsupervised methods. Then, each
category is subdivided into statistical, auxiliary models, network invariant,
feature squeezing, denoiser-based and object-based methods. Secondly, we
demonstrated the performance evaluation of eight state-of-the-art algorithms
experimentally in terms of detection rates, false positive rates, complexity,
overhead and test time inference latency. We showed, as well, the impact of
the content and the CNN with respect to detection methods. Finally, we
highlighted the fact that the tested algorithms lack generalization and that
more research efforts should be made in this research direction.

## Acknowledgement

The project is funded by both Région Bretagne (Brittany region), France, and
direction générale de l’armement (DGA).

## References

  * [1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in neural information processing systems, pages 1097–1105, 2012.
  * [2] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [3] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [4] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431–3440, 2015.
  * [5] Luca Bertinetto, Jack Valmadre, Joao F Henriques, Andrea Vedaldi, and Philip HS Torr.  Fully-convolutional siamese networks for object tracking.  In European conference on computer vision, pages 850–865. Springer, 2016.
  * [6] Martin Danelljan, Goutam Bhat, Fahad Shahbaz Khan, and Michael Felsberg.  Eco: Efficient convolution operators for tracking.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6638–6646, 2017.
  * [7] Justin Ker, Lipo Wang, Jai Rao, and Tchoyoson Lim.  Deep learning applications in medical image analysis.  IEEE Access, 6:9375–9389, 2017.
  * [8] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [9] Awni Y. Hannun, Carl Case, Jared Casper, Bryan Catanzaro, Greg Diamos, Erich Elsen, Ryan Prenger, Sanjeev Satheesh, Shubho Sengupta, Adam Coates, and Andrew Y. Ng.  Deep speech: Scaling up end-to-end speech recognition.  CoRR, abs/1412.5567, 2014.
  * [10] Alexey Kurakin, Ian Goodfellow, and Samy Bengio.  Adversarial examples in the physical world.  ICLR Workshop, 2017.
  * [11] Ivan Evtimov, Kevin Eykholt, Earlence Fernandes, Tadayoshi Kohno, Bo Li, Atul Prakash, Amir Rahmati, and Dawn Song.  Robust physical-world attacks on machine learning models.  CoRR, abs/1707.08945, 2017.
  * [12] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  CoRR, abs/1708.06733, 2017.
  * [13] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami.  Practical black-box attacks against machine learning.  In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pages 506–519, 2017.
  * [14] Marco Melis, Ambra Demontis, Battista Biggio, Gavin Brown, Giorgio Fumera, and Fabio Roli.  Is deep learning safe for robot vision? adversarial examples against the icub humanoid.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 751–759, 2017.
  * [15] Keiron O’Shea and Ryan Nash.  An introduction to convolutional neural networks.  arXiv preprint arXiv:1511.08458, 2015.
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [17] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 2818–2826. IEEE Computer Society, 2016.
  * [18] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  CoRR, abs/1704.04861, 2017.
  * [19] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [20] A. Krizhevsky and G. Hinton.  Learning multiple layers of features from tiny images.  Master’s thesis, Department of Computer Science, University of Toronto, 2009.
  * [21] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng.  Reading digits in natural images with unsupervised feature learning.  In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, Granada, Spain, 2011.
  * [22] Leon Yao and John Miller.  Tiny imagenet classification with convolutional neural networks.  CS 231N, 2(5):8, 2015.
  * [23] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  ImageNet: A Large-Scale Hierarchical Image Database.  In CVPR09, 2009.
  * [24] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 580–587, 2014.
  * [25] Ross B. Girshick.  Fast R-CNN.  In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pages 1440–1448. IEEE Computer Society, 2015.
  * [26] Joseph Redmon, Santosh Kumar Divvala, Ross B. Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 779–788. IEEE Computer Society, 2016.
  * [27] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pages 4171–4186. Association for Computational Linguistics, 2019.
  * [28] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 5754–5764, 2019.
  * [29] Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut.  ALBERT: A lite BERT for self-supervised learning of language representations.  In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
  * [30] Nikolaos Pitropakis, Emmanouil Panaousis, Thanassis Giannetsos, Eleftherios Anastasiadis, and George Loukas.  A taxonomy and survey of attacks against machine learning.  Computer Science Review, 34:100199, 2019.
  * [31] Yiming Li, Baoyuan Wu, Yong Jiang, Zhifeng Li, and Shu-Tao Xia.  Backdoor learning: A survey.  arXiv preprint arXiv:2007.08745, 2020.
  * [32] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
  * [33] Nicholas Carlini and David Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3–14, 2017.
  * [34] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry.  Adversarial examples are not bugs, they are features.  In Advances in Neural Information Processing Systems, pages 125–136, 2019.
  * [35] Naveed Akhtar and Ajmal Mian.  Threat of adversarial attacks on deep learning in computer vision: A survey.  IEEE Access, 6:14410–14430, 2018.
  * [36] Han Xu Yao Ma Hao-Chen, Liu Debayan Deb, Hui Liu Ji-Liang Tang Anil, and K Jain.  Adversarial attacks and defenses in images, graphs and text: A review.  International Journal of Automation and Computing, 17(2):151–178, 2020.
  * [37] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [38] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard.  Deepfool: a simple and accurate method to fool deep neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2574–2582, 2016.
  * [39] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In 2017 ieee symposium on security and privacy (sp), pages 39–57. IEEE, 2017.
  * [40] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [41] Nicolas Papernot, Patrick D. McDaniel, and Ian J. Goodfellow.  Transferability in machine learning: from phenomena to black-box attacks using adversarial samples.  CoRR, abs/1605.07277, 2016.
  * [42] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh.  Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models.  In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15–26, 2017.
  * [43] Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry.  Exploring the landscape of spatial robustness.  In International Conference on Machine Learning, pages 1802–1811, 2019.
  * [44] Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai.  One pixel attack for fooling deep neural networks.  IEEE Transactions on Evolutionary Computation, 23(5):828–841, 2019\.
  * [45] Shashank Kotyan and Danilo Vasconcellos Vargas.  Adversarial robustness assessment: Why both $l_{0}$ and $l_{\infty}$ attacks are necessary.  arXiv e-prints, pages arXiv–1906, 2019.
  * [46] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan L. Yuille.  Adversarial examples for semantic segmentation and object detection.  In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 1378–1387. IEEE Computer Society, 2017.
  * [47] Jiajun Lu, Hussein Sibai, Evan Fabry, and David A. Forsyth.  NO need to worry about adversarial examples in object detection in autonomous vehicles.  CoRR, abs/1707.03501, 2017.
  * [48] Wei Emma Zhang, Quan Z Sheng, Ahoud Alhazmi, and Chenliang Li.  Adversarial attacks on deep-learning models in natural language processing: A survey.  ACM Transactions on Intelligent Systems and Technology (TIST), 11(3):1–41, 2020.
  * [49] Lichao Sun, Kazuma Hashimoto, Wenpeng Yin, Akari Asai, Jia Li, Philip S. Yu, and Caiming Xiong.  Adv-bert: BERT is not robust on misspellings! generating nature adversarial samples on BERT.  CoRR, abs/2003.04985, 2020.
  * [50] Di Li, Danilo Vasconcellos Vargas, and Kouichi Sakurai.  Universal rules for fooling deep neural networks based text classification.  In IEEE Congress on Evolutionary Computation, CEC 2019, Wellington, New Zealand, June 10-13, 2019, pages 2221–2228. IEEE, 2019.
  * [51] Donghua Wang, Rangding Wang, Li Dong, Diqun Yan, Xueyuan Zhang, and Yongkang Gong.  Adversarial examples attack and countermeasure for speech recognition system: A survey.  In International Conference on Security and Privacy in Digital Economy, pages 443–468. Springer, 2020.
  * [52] Huali Ren, Teng Huang, and Hongyang Yan.  Adversarial examples: attacks and defenses in the physical world.  International Journal of Machine Learning and Cybernetics, pages 1–12, 2021.
  * [53] Prithviraj Dasgupta and Joseph Collins.  A survey of game theoretic approaches for adversarial machine learning in cybersecurity tasks.  AI Magazine, 40(2):31–43, 2019.
  * [54] Samuel G. Finlayson, Isaac S. Kohane, and Andrew L. Beam.  Adversarial attacks against medical deep learning systems.  CoRR, abs/1804.05296, 2018.
  * [55] Cihang Xie, Mingxing Tan, Boqing Gong, Alan L. Yuille, and Quoc V. Le.  Smooth adversarial training.  CoRR, abs/2006.14536, 2020.
  * [56] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel.  Ensemble adversarial training: Attacks and defenses.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [57] Cihang Xie, Yuxin Wu, Laurens van der Maaten, Alan L Yuille, and Kaiming He.  Feature denoising for improving adversarial robustness.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 501–509, 2019.
  * [58] Tejas Borkar, Felix Heide, and Lina Karam.  Defending against universal attacks through selective feature regeneration.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 709–719, 2020.
  * [59] Fangzhou Liao, Ming Liang, Yinpeng Dong, Tianyu Pang, Xiaolin Hu, and Jun Zhu.  Defense against adversarial attacks using high-level representation guided denoiser.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1778–1787, 2018.
  * [60] Yassine Bakhti, Sid Ahmed Fezza, Wassim Hamidouche, and Olivier Déforges.  Ddsa: a defense against adversarial attacks using deep denoising sparse autoencoder.  IEEE Access, 7:160397–160407, 2019.
  * [61] Aamir Mustafa, Salman H Khan, Munawar Hayat, Jianbing Shen, and Ling Shao.  Image super-resolution as a defense against adversarial attacks.  IEEE Transactions on Image Processing, 29:1711–1724, 2019.
  * [62] Aaditya Prakash, Nick Moran, Solomon Garber, Antonella DiLillo, and James Storer.  Deflecting adversarial attacks with pixel deflection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8571–8580, 2018.
  * [63] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami.  Distillation as a defense to adversarial perturbations against deep neural networks.  In 2016 IEEE Symposium on Security and Privacy (SP), pages 582–597. IEEE, 2016.
  * [64] Shixiang Gu and Luca Rigazio.  Towards deep neural network architectures robust to adversarial examples.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015.
  * [65] Aran Nayebi and Surya Ganguli.  Biologically inspired protection of deep networks from adversarial attacks.  CoRR, abs/1703.09202, 2017.
  * [66] Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick D. McDaniel.  On the (statistical) detection of adversarial examples.  CoRR, abs/1702.06280, 2017.
  * [67] Dongyu Meng and Hao Chen.  Magnet: a two-pronged defense against adversarial examples.  In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pages 135–147, 2017.
  * [68] Weilin Xu, David Evans, and Yanjun Qi.  Feature squeezing: Detecting adversarial examples in deep neural networks.  In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018. The Internet Society, 2018.
  * [69] Kathrin Grosse, Nicolas Papernot, Praveen Manoharan, Michael Backes, and Patrick D. McDaniel.  Adversarial perturbations against deep neural networks for malware classification.  CoRR, abs/1606.04435, 2016.
  * [70] Shiqing Ma and Yingqi Liu.  Nic: Detecting adversarial samples with neural network invariant checking.  In Proceedings of the 26th Network and Distributed System Security Symposium (NDSS 2019), 2019.
  * [71] Guillermo Ortiz-Jiménez, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard.  Optimism in the face of adversity: Understanding and improving deep learning through adversarial robustness.  Proceedings of the IEEE, 109(5):635–659, 2021.
  * [72] Xiaoyong Yuan, Pan He, Qile Zhu, and Xiaolin Li.  Adversarial examples: Attacks and defenses for deep learning.  IEEE transactions on neural networks and learning systems, 30(9):2805–2824, 2019.
  * [73] Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopadhyay.  Adversarial attacks and defences: A survey.  CoRR, abs/1810.00069, 2018.
  * [74] Xianmin Wang, Jing Li, Xiaohui Kuang, Yu-an Tan, and Jin Li.  The security of machine learning in an adversarial setting: A survey.  Journal of Parallel and Distributed Computing, 130:12–23, 2019\.
  * [75] Gabriel Resende Machado, Eugênio Silva, and Ronaldo Ribeiro Goldschmidt.  Adversarial machine learning in image classification: A survey towards the defender’s perspective.  CoRR, abs/2009.03728, 2020.
  * [76] Saikiran Bulusu, Bhavya Kailkhura, Bo Li, Pramod K Varshney, and Dawn Song.  Anomalous example detection in deep learning: A survey.  IEEE Access, 8:132330–132347, 2020.
  * [77] David Miller, Yujia Wang, and George Kesidis.  When not to classify: Anomaly detection of attacks (ada) on dnn classifiers at test time.  Neural computation, 31(8):1624–1670, 2019.
  * [78] David J Miller, Zhen Xiang, and George Kesidis.  Adversarial learning targeting deep neural network classification: A comprehensive review of defenses against attacks.  Proceedings of the IEEE, 108(3):402–433, 2020.
  * [79] Alex Serban, Erik Poll, and Joost Visser.  Adversarial examples on object recognition: A comprehensive survey.  ACM Computing Surveys (CSUR), 53(3):1–38, 2020.
  * [80] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli.  Evasion attacks against machine learning at test time.  In Joint European conference on machine learning and knowledge discovery in databases, pages 387–402. Springer, 2013.
  * [81] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song.  Delving into transferable adversarial examples and black-box attacks.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [82] Battista Biggio, Giorgio Fumera, and Fabio Roli.  Pattern recognition systems under attack: Design issues and research challenges.  International Journal of Pattern Recognition and Artificial Intelligence, 28(07):1460002, 2014.
  * [83] Battista Biggio, Igino Corona, Blaine Nelson, Benjamin IP Rubinstein, Davide Maiorca, Giorgio Fumera, Giorgio Giacinto, and Fabio Roli.  Security evaluation of support vector machines in adversarial environments.  In Support Vector Machines Applications, pages 105–153. Springer, 2014.
  * [84] Battista Biggio and Fabio Roli.  Wild patterns: Ten years after the rise of adversarial machine learning.  Pattern Recognition, 84:317–331, 2018.
  * [85] Dong C Liu and Jorge Nocedal.  On the limited memory bfgs method for large scale optimization.  Mathematical programming, 45(1-3):503–528, 1989.
  * [86] Francesco Croce and Matthias Hein.  Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.  In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2206–2216. PMLR, 2020.
  * [87] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard.  Universal adversarial perturbations.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1765–1773, 2017.
  * [88] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami.  The limitations of deep learning in adversarial settings.  In 2016 IEEE European symposium on security and privacy (EuroS&P), pages 372–387. IEEE, 2016.
  * [89] Sara Sabour, Yanshuai Cao, Fartash Faghri, and David J. Fleet.  Adversarial manipulation of deep representations.  In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
  * [90] Shumeet Baluja and Ian Fischer.  Adversarial transformation networks: Learning to generate adversarial examples.  CoRR, abs/1703.09387, 2017.
  * [91] Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok.  Synthesizing robust adversarial examples.  In International conference on machine learning, pages 284–293. PMLR, 2018.
  * [92] Anish Athalye, Nicholas Carlini, and David A. Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 274–283. PMLR, 2018.
  * [93] Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein.  Square attack: A query-efficient black-box adversarial attack via random search.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIII, volume 12368 of Lecture Notes in Computer Science, pages 484–501. Springer, 2020.
  * [94] Wieland Brendel, Jonas Rauber, and Matthias Bethge.  Decision-based adversarial attacks: Reliable attacks against black-box machine learning models.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [95] Jianbo Chen, Michael I Jordan, and Martin J Wainwright.  Hopskipjumpattack: A query-efficient decision-based attack.  In 2020 ieee symposium on security and privacy (sp), pages 1277–1294. IEEE, 2020.
  * [96] Sayantan Sarkar, Ankan Bansal, Upal Mahbub, and Rama Chellappa.  UPSET and ANGRI : Breaking high performance image classifiers.  CoRR, abs/1707.01159, 2017.
  * [97] Anh Nguyen, Jason Yosinski, and Jeff Clune.  Deep neural networks are easily fooled: High confidence predictions for unrecognizable images.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 427–436, 2015.
  * [98] Nicholas Carlini and David A. Wagner.  Defensive distillation is not robust to adversarial examples.  CoRR, abs/1607.04311, 2016.
  * [99] Jiajun Lu, Theerasit Issaranon, and David Forsyth.  Safetynet: Detecting and rejecting adversarial examples robustly.  In Proceedings of the IEEE International Conference on Computer Vision, pages 446–454, 2017.
  * [100] Stefanos Pertigkiozoglou and Petros Maragos.  Detecting adversarial examples in convolutional neural networks.  CoRR, abs/1812.03303, 2018.
  * [101] Fabio Carrara, Rudy Becarelli, Roberto Caldelli, Fabrizio Falchi, and Giuseppe Amato.  Adversarial examples detection in features distance spaces.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 0–0, 2018.
  * [102] Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff.  On detecting adversarial perturbations.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [103] Hasan Ferit Eniser, Maria Christakis, and Valentin Wüstholz.  RAID: randomized adversarial-input detection for neural networks.  CoRR, abs/2002.02776, 2020.
  * [104] Reuben Feinman, Ryan R. Curtin, Saurabh Shintre, and Andrew B. Gardner.  Detecting adversarial samples from artifacts.  CoRR, abs/1703.00410, 2017.
  * [105] Lewis Smith and Yarin Gal.  Understanding measures of uncertainty for adversarial example detection.  In Amir Globerson and Ricardo Silva, editors, Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pages 560–569. AUAI Press, 2018.
  * [106] Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [107] Jonathan Aigrain and Marcin Detyniecki.  Detecting adversarial examples and other misclassifications in neural networks by introspection.  CoRR, abs/1905.09186, 2019.
  * [108] João Monteiro, Isabela Albuquerque, Zahid Akhtar, and Tiago H Falk.  Generalizable adversarial examples detection based on bi-model decision mismatch.  In 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC), pages 2839–2844. IEEE, 2019.
  * [109] Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku.  Adversarial and clean data are not twins.  CoRR, abs/1704.04960, 2017.
  * [110] Hossein Hosseini, Yize Chen, Sreeram Kannan, Baosen Zhang, and Radha Poovendran.  Blocking transferability of adversarial examples in black-box learning systems.  CoRR, abs/1703.04318, 2017.
  * [111] Julia Lust and Alexandru Paul Condurache.  Gran: An efficient gradient-norm based detector for adversarial and misclassified examples.  In 28th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN 2020, Bruges, Belgium, October 2-4, 2020, pages 7–12, 2020.
  * [112] Anouar Kherchouche, Sid Ahmed Fezza, Wassim Hamidouche, and Olivier Déforges.  Detection of adversarial examples in deep neural networks with natural scene statistics.  In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–7. IEEE, 2020.
  * [113] Fei Zuo and Qiang Zeng.  Exploiting the sensitivity of L2 adversarial examples to erase-and-restore.  In Jiannong Cao, Man Ho Au, Zhiqiang Lin, and Moti Yung, editors, ASIA CCS ’21: ACM Asia Conference on Computer and Communications Security, Virtual Event, Hong Kong, June 7-11, 2021, pages 40–51. ACM, 2021\.
  * [114] Xin Li and Fuxin Li.  Adversarial examples detection in deep networks with convolutional filter statistics.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5764–5772, 2017.
  * [115] Xingjun Ma, Bo Li, Yisen Wang, Sarah M. Erfani, Sudanthi N. R. Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E. Houle, and James Bailey.  Characterizing adversarial subspaces using local intrinsic dimensionality.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [116] Gilad Cohen, Guillermo Sapiro, and Raja Giryes.  Detecting adversarial samples using influence functions and nearest neighbors.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14453–14462, 2020.
  * [117] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin.  A simple unified framework for detecting out-of-distribution samples and adversarial attacks.  In Advances in Neural Information Processing Systems, pages 7167–7177, 2018.
  * [118] Scott Freitas, Shang-Tse Chen, Zijie J. Wang, and Duen Horng Chau.  Unmask: Adversarial detection and defense through robust feature alignment.  In IEEE International Conference on Big Data, Big Data 2020, Atlanta, GA, USA, December 10-13, 2020, pages 1081–1088. IEEE, 2020.
  * [119] Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman.  Pixeldefend: Leveraging generative models to understand and defend against adversarial examples.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [120] Dan Hendrycks and Kevin Gimpel.  Early methods for detecting adversarial images.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017.
  * [121] Zhihao Zheng and Pengyu Hong.  Robust detection of adversarial attacks by modeling the intrinsic properties of deep neural networks.  In Advances in Neural Information Processing Systems, pages 7913–7922, 2018.
  * [122] Bin Liang, Hongcheng Li, Miaoqiang Su, Xirong Li, Wenchang Shi, and Xiaofeng Wang.  Detecting adversarial image examples in deep neural networks with adaptive noise reduction.  IEEE Trans. Dependable Secur. Comput., 18(1):72–85, 2021.
  * [123] Fabio Carrara, Fabrizio Falchi, Roberto Caldelli, Giuseppe Amato, Roberta Fumarola, and Rudy Becarelli.  Detecting adversarial example attacks to deep neural networks.  In Proceedings of the 15th International Workshop on Content-Based Multimedia Indexing, pages 1–7, 2017.
  * [124] Tianyu Pang, Chao Du, Yinpeng Dong, and Jun Zhu.  Towards robust detection of adversarial examples.  In Advances in Neural Information Processing Systems, pages 4579–4589, 2018.
  * [125] Fatemeh Sheikholeslami, Swayambhoo Jain, and Georgios B. Giannakis.  Minimum uncertainty based detection of adversaries in deep neural networks.  In Information Theory and Applications Workshop, ITA 2020, San Diego, CA, USA, February 2-7, 2020, pages 1–16. IEEE, 2020.
  * [126] Angelo Sotgiu, Ambra Demontis, Marco Melis, Battista Biggio, Giorgio Fumera, Xiaoyi Feng, and Fabio Roli.  Deep neural rejection against adversarial examples.  EURASIP Journal on Information Security, 2020:1–10, 2020.
  * [127] Ahmed Aldahdooh, Wassim Hamidouche, and Olivier Déforges.  Revisiting model’s uncertainty and confidences for adversarial example detection.  arXiv preprint arXiv:2103.05354, 2021.
  * [128] Nicholas Carlini and David A. Wagner.  Magnet and ”efficient defenses against adversarial attacks” are not robust to adversarial examples.  CoRR, abs/1711.08478, 2017.
  * [129] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  The journal of machine learning research, 15(1):1929–1958, 2014\.
  * [130] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision. 2015.  arXiv preprint arXiv:1512.00567, 2015.
  * [131] Anish Mittal, Anush Krishna Moorthy, and Alan Conrad Bovik.  No-reference image quality assessment in the spatial domain.  IEEE Transactions on image processing, 21(12):4695–4708, 2012.
  * [132] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  The Journal of Machine Learning Research, 13(1):723–773, 2012.
  * [133] Xiaofeng Mao, Yuefeng Chen, Yuhong Li, Yuan He, and Hui Xue.  Learning to characterize adversarial subspaces.  In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2438–2442. IEEE, 2020.
  * [134] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998–6008, 2017.
  * [135] Yonatan Geifman and Ran El-Yaniv.  Selectivenet: A deep neural network with an integrated reject option.  CoRR, abs/1901.09192, 2019.
  * [136] Solomon Kullback and Richard A Leibler.  On information and sufficiency.  The annals of mathematical statistics, 22(1):79–86, 1951.
  * [137] Aaron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, et al.  Conditional image generation with pixelcnn decoders.  Advances in neural information processing systems, 29:4790–4798, 2016.
  * [138] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017.
  * [139] Maria-Irina Nicolae, Mathieu Sinn, Minh Ngoc Tran, Beat Buesser, Ambrish Rawat, Martin Wistuba, Valentina Zantedeschi, Nathalie Baracaldo, Bryant Chen, Heiko Ludwig, Ian M. Molloy, and Ben Edwards.  Adversarial robustness toolbox v1.0.0, 2019.
  * [140] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In European conference on computer vision, pages 630–645. Springer, 2016.
  * [141] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 618–626. IEEE Computer Society, 2017.
  * [142] Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin A. Riedmiller.  Striving for simplicity: The all convolutional net.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015.
  * [143] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry.  Adversarially robust generalization requires more data.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 5019–5031, 2018.

  *[AE]: adversarial example
  *[DL]: deep learning
  *[AI]: artificial intelligence
  *[ML]: machine learning
  *[NLP]: natural language processing
  *[AEs]: adversarial example
  *[AA]: adversarial attack
  *[AAs]: adversarial attack
  *[DNN]: deep neural network
  *[CNN]: convolutional neural network
  *[SGD]: stochastic gradient descent
  *[L-BFGS]: limited memory broyden-fletcher-goldfarb-shanno
  *[FGSM]: fast gradient sign method
  *[BIM]: basic iterative method
  *[PGD]: projected gradient descent
  *[CW]: carlini-wagner
  *[DF]: deepFool
  *[UAP]: universal adversarial perturbations
  *[JSMA]: jacobian saliency map attack
  *[FA]: feature adversary attack
  *[ATN]: adversarial transformation networks
  *[EOT]: expectation over transformation
  *[BPDA]: backward pass differentiable approximation
  *[HCA]: high confidence attack
  *[ZOO]: zeroth order optimization
  *[DE]: differential evolution
  *[EA]: evolutionary algorithm
  *[PA]: pixel attack
  *[TA]: threshold attack
  *[ST]: spatial transformation
  *[SA]: square attack
  *[BA]: boundary attack
  *[UPSET]: universal perturbations for steering to exact targets
  *[ANGRI]: antagonistic network for generating rogue images
  *[CPPN EA]: compositional pattern-producing network-encoded evolutionary algorithm
  *[NN]: neural network
  *[NSS]: natural scene statistics
  *[MMD]: maximum mean discrepancy
  *[PCA]: principal component analysis
  *[KD]: kernel density
  *[LID]: local intrinsic dimensionality
  *[$k$-NN]: k-nearest neighbor
  *[GMM]: Gaussian mixture model
  *[DNR]: deep neural rejection
  *[SFAD]: selective and feature based adversarial detection
  *[BU]: bayesian uncertainty
  *[RBF]: radial basis function
  *[SVM]: support vector machine
  *[MSCN]: mean subtracted contrast normalized
  *[GDA]: gaussian discriminant analysis
  *[NIC]: neural-network invariant checking
  *[FS]: feature squeezing
  *[FPR]: false positive rate
  *[Grad-CAM]: gradient-weighted class activation mapping
  *[CNNs]: convolutional neural network


}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(70.0,0.0){
\small Train/Validation split } \put(49.0,13.0){ \leavevmode\hbox
to11.98pt{\vbox to142.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{142.26378pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(49.5,27.0){\rotatebox{90.0}{ \small$\mathbb{E}\big{|}\hat{C}(X)\big{|}$}}
\par\par\put(6.0,47.5){ \leavevmode\hbox to85.96pt{\vbox
to9.14pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(30.0,47.5){
\leavevmode\hbox to85.96pt{\vbox to9.14pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(10.0,47.5){
\small$\mathbb{P}(Y\in\widehat{C}(X))$ } \put(31.0,47.5){
\small$\mathbb{P}(W\cap\widehat{C}(X)\neq\emptyset)$ } \par\put(5.0,50.0){ \bf
A} \put(52.0,50.0){ \bf B} \end{overpic} Figure 6: Results for the video
tracking matching dataset MOT2015 [29], over $N_{\text{trials}}=20$ trials. We
use one video sequence for training (ETH-B, ETH-P or ETH-S) and the two others
for calibration and testing. A: Strong (1) and weak (3) coverage. B: Average
confidence set size for fully supervised (FSC) and weakly supervised conformal
(WSC) methods.

We now apply our weakly supervised conformal methods to a bipartite matching
problem. A common objective in computer vision, relevant for instance for
self-driving cars, is to track people’s trajectory throughout different time
frames. Since we can leverage powerful algorithms [39] to individually detect
objects in every single frame, the problem that we study here is actually a
matching task where the goal is to match two sets of people appearing in two
separate frames: this is an instance of a maximal matching problem.

##### Weak supervision with partial matchings

In this context, we expect partial supervision to come under the form of a
partial matching: some people, e.g. people that are easier to track between
two consecutive frames because they are in the foreground, already have their
match in the second frame, when others, perhaps more difficult to track, are
still waiting for a potential match. Given these partially labeled instances,
the goal then becomes to return confidence sets of matchings that guarantee
$1-\alpha$ coverage: to provide valid weak coverage (3), we wish to include a
configuration that contains at least all the partial matches.

##### Predicting trajectories in the MOT2D15 data set [29]

We experiment using the MOT2D15 pedestrian video tracking dataset [29]. It is
a public benchmark data set that contains short street videos with
pedestrians, and for which the goal is to track each of them while they appear
in the frame. Specifically, each frame already has a set of bounding boxes
corresponding to each individual present in that frame, and we aim at matching
boxes representing the same person between two consecutive frames. Since an
individual can enter or exit the frame between two consecutive images, we need
to account for potentially unmatched boxes, which we do by including “virtual”
nodes in the bipartite graph, similarly to previous approaches [27, 16].

We use the same feature representation of Kim et al. [27] and Fathony et al.
[16]: given a pair $x\coloneqq(x_{1},x_{2})$ of two consecutive images, and
two bounding boxes $u\subset x_{1}$, $v\subset x_{2}$, we compute a $d=46$
dimensional vector $\phi(x_{1},x_{2},u,v)$ that summarizes key features (e.g.
position of the bounding box, color distribution) allowing to determine
whether $u$ and $v$ represent the same person. We then train our model using a
structured S-SVM approach [49], following the approach of Kim et al. [27].
Such model outputs a pairwise score function
$s^{\text{PW}}:(x,u,v)\mapsto\theta^{T}\phi(x_{1},x_{2},u,v)$ for some vector
$\theta\in\mathbb{R}^{d}$ where the feature vector
$x=(x_{1},x_{2})\in\mathcal{X}$ consists of two consecutive frames, and
$(u,v)$ are two potential bounding boxes (one in each image).

##### Experimental set-up and partial labels

We use the data set MOT2D15 as follows. For each of the ETH-Bahnhof, ETH-
Pedcross2 and ETH-Sunnyday video sequences, which contain respectively 1000,
837, and 354 consecutive images, we select one of them for training, one of
them for calibration and one of them for actual testing, using $\alpha=0.02$
for conformalization purposes. We further introduce weak supervision by
assuming that for each pair of images, we observe a partial matching,
precisely that among the $K_{i}$ paired individuals, a user provided us
feedback on $K_{i}^{\text{partial}}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}1+\text{Poi}(0.5)$ matches.

For both our FSC and WSC methods, we use a translated version of the score
$s^{\text{Matching}}$ (11) with pairwise functions $\\{s_{u,v}:x\mapsto
s^{\text{PW}}(x,u,v)\\}_{u,v}$: for each instance
$(x,y)\in\mathcal{X}\times\mathcal{Y}$, we use the score

$\displaystyle\tilde{s}^{\text{Matching}}(x,y)\coloneqq
s^{\text{Matching}}(x,y)-\min_{\tilde{y}\in\mathcal{Y}}s^{\text{Matching}}(x,\tilde{y})$

This operation simply ensures that
$\min_{y\in\mathcal{Y}}\tilde{s}^{\text{Matching}}(x,y)=0$ for every
$x\in\mathcal{X}$ and thus does not change the ordering of configurations, nor
the score difference between two configurations. We simply use it to make sure
to place all the instances $X_{i}$ on the same scale when applying Algorithm 1
in the sense that they all have the same best achievable score. In particular,
in the noiseless case where the true label $Y_{i}$ is always the minimizer of
$y\mapsto s^{\text{Matching}}(X_{i},y)$, it guarantees that $\widehat{C}(X)$
eventually contains a single configuration (as we should, since the score
function in this case outputs perfect predictions).

##### Experimental results

This specific problem is actually low-noise, as it is possible to achieve a
very high accuracy with the S-SVM approach, which is not so surprising as we
assume perfect detection of every person thanks the bounding boxes. As a
result, we can expect the FSC and WSC methods to output very similar
confidence sets, as the configuration minimizing the score is often the true
label itself. This is precisely what we observe in Figure 6, where both
methods are actually indistinguishable and where, even with a very high
confidence $1-\alpha.=0.98$, both the FSC and WSC methods are able to return
confidence sets with a single configuration in average. We only notice a
slight difference between both methods when training on the ETH-Sunnyday
sequence, which contains fewer images, and hence produces slightly worse score
functions.

###  5.4 Prediction intervals for weakly supervised regression

As we mentioned earlier, much of our development thus far goes beyond (finite)
spaces with combinatorial structure, as we saw in the last few examples.
Therefore, we finish with a regression problem. We consider predicting the
fraction of votes in each United States county for the Democratic Party
candidate in the 2016 United States presidential election, using demographic
(census) data as covariates and the results of past elections. It is common
during elections for forecasters to build predictive models from both census
and historical election data, as well as current polling data. We view the
historical data as strong supervision (it tells us exactly how many people
voted for each candidate), and the polling data as weak supervision (as polls
always come with a margin of error). Our goal here is to fit a regression
model to the strongly supervised past election data, and then form prediction
intervals for the fraction of people in each county who voted Democrat by
leveraging the weakly supervised polling data. We hope by combining both we
obtain valid intervals narrower than the polling margins of error.

Our data comes from the 2013–2017 American Community Survey 5-Year Estimates,
which is a longitudinal survey that records demographic information about each
of the 3220 United States counties. We use 34 of the available demographic
features. The response is simply the fraction of people in each county who
voted Democratic (and is publicly available). Thus our sample size is 3220,
and the number of dimensions is $d=34$.

We construct a stylized version of the above situation in the following way.
First, we split the data set into thirds: 33% of the counties (and their
associated fractions of Democratic voters) go into the training set, 33% go
into the calibration set, and the rest go into the test set; as our splits are
random, they are exchangeable. Then, we fit a Beta regression model to the
strongly supervised training data. To simulate the availability of weakly
supervised polling data, we replace each calibration set response
$Y_{i}\in[0,1]$ with a weak response $W_{i}\subset[0,1]$, $i=1,\ldots,n$, by
forming

$\displaystyle W_{i}=[Y_{i}-Z_{i},Y_{i}+Z_{i}],\quad
Z_{i}\sim\mathsf{N}(\mu,0.0001),\quad i=1,\ldots,n,$ (22)

for various values of $\mu\in\\{.01,.05,.1,.15,.2\\}$, so that $W_{i}$
captures fluctuations around $Y_{i}$ that are roughly $\pm\mu$. We
conformalize by running Alg. 1 with the absolute error scoring function,

$s(x,y)=|\hat{y}(x)-y|,$

where $\hat{y}(x)\in[0,1]$ denotes the Beta regression model’s prediction for
the point $x\in\mathbb{R}^{d}$. Here, conformalization boils down to solving a
simple linear program, i.e.,

$\displaystyle
s(X_{i},Y_{i})=\min_{\gamma\in\mathbb{R}}~{}\left\\{|\hat{y}(X_{i})-\gamma|~{}\mid~{}Y_{i}-Z_{i}\leq\gamma,~{}\gamma\leq
Y_{i}+Z_{i}\right\\},\quad i=1,\ldots,n.$

Finally, we evaluate both strong (1) and weak (3) coverage on the test set (we
apply the same transformation as in (22) to generate the weak labels for the
test set). We compute the two types of coverage, as well as the lengths of the
prediction intervals, by repeating this process 20 times. We set the
miscoverage level $\alpha=.05$.

Similar to our other experiments, we find that Alg. 1 achieves weak coverage
at the nominal level $.95$, for all values of $\mu$ (governing the amount of
weak supervision), shown in the middle panel of Figure 7. On the other hand,
we expect the strong coverage to be much lower. The left panel of Figure 7
shows the strong coverage for Alg. 1 in teal and standard conformal inference
in pink, and we can see that this is indeed the case. However, in return, we
expect the prediction intervals that Alg. 1 generates to be smaller than those
coming from standard conformal inference. The right panel of Figure 7 shows
that this is also the case: in particular, when $\mu\geq.1$, the average
length of Alg. 1’s intervals is at least three times smaller than standard
conformal’s, and half the length of the average weakly supervised interval
$W_{i}$ from (22) ($\approx.2$). We can also see from these figures, as in our
other experiments, that Alg. 1’s strong coverage degrades as $\mu$ grows,
whereas its weak coverage improves and the length of its prediction intervals
shrinks.

Figure 7: Results for the regression problem with the election data, over 20
trials. The left panel shows the strong coverage (1), and the middle panel
shows the weak coverage (3). The dashed red line indicates the nominal
coverage level, $1-\alpha=.95$. The right panel shows the prediction interval
lengths. In these plots, we show Alg. 1, denoted “WSC”, in teal. We show
standard conformal inference, denoted “FSC”, in pink.

We view these results from a slightly different perspective in Figures 8 and
9. In Figure 8, we show the true fraction of people in each county from the
test set that voted Democratic. In Figure 9, we show the lower and upper
endpoints of Alg. 1’s prediction intervals, for a randomly chosen repetition
with $\mu=.05$. In these two figures, we color the counties with strong
(predicted) Democratic majorities blue, and those with strong (predicted)
Republican majorities red. By comparing the colors, we can see that the
prediction intervals only sometimes contain the true response, which is
expected. Finally, we note that the colors of the lower and upper endpoints in
Figure 9 are similar, because the length of the prediction intervals is
usually small.

Figure 8: Map of United States counties. We color each county according to the
actual fraction votes for the Democratic candidate in the 2016 United States
presidential election. We color counties with strong Democratic majorities
blue, and those with strong Republican majorities red. We color the counties
from the training and calibration sets gray.

Figure 9: Map of United States counties. We color each county according to the
value of the upper (top panel) and lower (bottom panel) endpoints of the
confidence interval that Alg. 1 returns, when $\mu=.05$. We color counties
with values close to 1 blue, and those with values close to 0 red. We color
the counties from the training and calibration sets gray.

##  6 Discussion

The new measures of coverage we develop here—tailored to partially supervised
data that may be easier to collect in many engineering and measurement-centric
scientific scenarios—help to bridge a gap between typical conformal predictive
inference methods, which require expensive supervised data, and problems with
partial supervision, whose typical focus is on prediction but not uncertainty
quantification. Our hope is that this work opens several avenues for future
work. The new definition (3) a 0-1 loss-based approach, in the sense that the
confidence set $\widehat{C}_{n}$ either covers the weakly supervised set or
fails. A natural initial extension is thus similarly to what Bates et al. [4]
propose in the strongly supervised case, recognizing that many structured
prediction problems (e.g., segmentation tasks or multilabel problems) benefit
from more subtle and granular loss functions. In the same vein, we present a
few efficient choices of scoring mechanisms for structured prediction, which
highlight the practicality and potential application of our general
methodology; it seems quite plausible that more sophisticated scoring models
could yield substantial improvements.

In our view, one of the more exciting potential applications of this work
reposes on the (growing) centrality of partial and weakly labeled data in
statistical learning [38]. Whether this be from partial reporting in surveys,
or because collecting labeled data is quite expensive, a major challenge in
modern machine learning deployments and the release of statistical models is
monitoring their performance. The weaker notions of predictive inference and
coverage here, we might hope to build more effective and applicable guardrails
and uncertainty measures for modern statistical systems, even as they are
released to the world.

## References

  * Ailon et al. [2008] N. Ailon, M. Charikar, and A. Newman.  Aggregating inconsistent information: Ranking and clustering.  _Journal of the Association for Computing Machinery_ , 55(5), 2008.
  * Angelopoulos et al. [2020] A. Angelopoulos, S. Bates, J. Malik, and M. I. Jordan.  Uncertainty sets for image classifiers using conformal prediction.  _arXiv:2009.14193 [cs.CV]_ , 2020.
  * Barber et al. [2021] R. F. Barber, E. J. Candès, A. Ramdas, and R. J. Tibshirani.  The limits of distribution-free conditional predictive inference.  _Information and Inference_ , 10(2):455–482, 2021\.
  * Bates et al. [2021] S. Bates, A. Angelopoulos, L. Lei, J. Malik, and M. I. Jordan.  Distribution-free, risk-controlling prediction sets.  _Journal of the Association for Computing Machinery_ , 2021.
  * Boutell et al. [2004] M. R. Boutell, J. Luo, X. Shen, and C. M. Brown.  Learning multi-label scene classification.  _Pattern Recognition_ , 37(9):1757–1771, 2004\.
  * Cabannes et al. [2020] V. Cabannes, A. Rudi, and F. Bach.  Structured prediction with partial labelling through the infimum loss.  In _Proceedings of the 37th International Conference on Machine Learning_ , 2020.
  * Cao et al. [2007] Z. Cao, T. Qin, T.-Y. Liu, M.-F. Tsai, and H. Li.  Learning to rank: from pairwise approach to listwise approach.  In _Proceedings of the 24th International Conference on Machine Learning_ , pages 129–136, 2007.
  * Cauchois et al. [2021] M. Cauchois, S. Gupta, and J. Duchi.  Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction.  _Journal of Machine Learning Research_ , 22(81):1–42, 2021.
  * Chegireddy and Hamacher [1987] C. R. Chegireddy and H. W. Hamacher.  Algorithms for finding k-best perfect matchings.  _Discrete Applied Mathematics_ , 18(2):155–165, 1987.
  * Cid-Sueiro et al. [2014] J. Cid-Sueiro, D. García-García, and R. Santos-Rodríguez.  Consistency of losses for learning from weak labels.  In _Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 197–210, 2014.
  * Cour et al. [2011] T. Cour, B. Sapp, and B. Taskar.  Learning from partial labels.  _Journal of Machine Learning Research_ , 12:1501––1536, 2011.
  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L. Li, K. Li, and L. Fei-Fei.  ImageNet: a large-scale hierarchical image database.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 248–255, 2009.
  * Donoho [2017] D. L. Donoho.  50 years of data science.  _Journal of Computational and Graphical Statistics_ , 26(4):745–766, 2017.
  * Duchi et al. [2013] J. C. Duchi, L. Mackey, and M. I. Jordan.  The asymptotics of ranking algorithms.  _Annals of Statistics_ , 41(5):2292–2323, 2013\.
  * Elisseeff and Weston [2001] A. Elisseeff and J. Weston.  A kernel method for multi-labeled classification.  In _Advances in Neural Information Processing Systems 14_ , 2001.
  * Fathony et al. [2018] R. Fathony, S. Behpour, X. Zhang, and B. Ziebart.  Efficient and consistent adversarial bipartite matching.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80, pages 1457–1466, 2018.
  * Fernandes and Brefeld [2011] E. R. Fernandes and U. Brefeld.  Learning from partially annotated sequences.  In _Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 407–422, Berlin, Heidelberg, 2011\. Springer Berlin Heidelberg.
  * Fisch et al. [2021] A. Fisch, T. Schuster, T. Jaakkola, and R. Barzilay.  Efficient conformal prediction via cascaded inference with expanded admission.  In _Proceedings of the Ninth International Conference on Learning Representations_ , 2021.
  * Freund et al. [2003] Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer.  Efficient boosting algorithms for combining preferences.  _Journal of Machine Learning Research_ , 4:933–969, 2003\.
  * Golovin et al. [2014] D. Golovin, A. Krause, and M. Streeter.  Online submodular maximization under a matroid constraint with application to learning assignments.  _arXiv:1407.1082 [cs.LG]_ , 2014.
  * Gupta et al. [2019] C. Gupta, A. K. Kuchibhotla, and A. K. Ramdas.  Nested conformal prediction and quantile out-of-bag ensemble methods.  _arXiv:1910.10562 [stat.ME]_ , 2019.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 770–778, 2016.
  * Hechtlinger et al. [2019] Y. Hechtlinger, B. Póczos, and L. Wasserman.  Cautious deep learning.  _arXiv:1805.09460 [stat.ML]_ , 2019.
  * Hüllermeier et al. [2008] E. Hüllermeier, J. Fürnkranz, W. Cheng, and K. Brinker.  Label ranking by learning pairwise preferences.  _Artificial Intelligence_ , 172(16–-17):1897––1916, Nov. 2008.
  * Kemeny [1959] J. G. Kemeny.  Mathematics without numbers.  _Daedalus_ , 88(4):577–591, 1959.
  * Kendall [1938] M. G. Kendall.  A new measure of rank correlation.  _Biometrika_ , 30(1/2):81–93, 1938.
  * Kim et al. [2013] S. Kim, S. Kwak, J. Feyereisl, and B. Han.  Online multi-target tracking by large margin structured learning.  In _Proceedings of the Asian Conference on Computer Vision_ , pages 98–111, 2013.
  * Korba et al. [2018] A. Korba, A. Garcia, and F. d’Alché Buc.  A structured prediction approach for label ranking.  In _Advances in Neural Information Processing Systems 31_ , pages 8994–9004, 2018.
  * Leal-Taixé et al. [2015] L. Leal-Taixé, A. Milan, I. Reid, S. Roth, and K. Schindler.  MOTChallenge 2015: Towards a benchmark for multi-target tracking.  _arXiv:1504.01942 [cs.CV]_ , 2015.
  * Lei [2014] J. Lei.  Classification with confidence.  _Biometrika_ , 101(4):755–769, 2014.
  * Lei and Wasserman [2014] J. Lei and L. Wasserman.  Distribution-free prediction bands for non-parametric regression.  _Journal of the Royal Statistical Society, Series B_ , 76(1):71–96, 2014.
  * Lei et al. [2018] J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman.  Distribution-free predictive inference for regression.  _Journal of the American Statistical Association_ , 113(523):1094–1111, 2018.
  * Mayhew et al. [2019] S. Mayhew, S. Chaturvedi, C.-T. Tsai, and D. Roth.  Named entity recognition with partially annotated training data.  In _Proceedings of the 23rd Conference on Computational Natural Language Learning_ , pages 645–655, 01 2019.
  * Negahban et al. [2016] S. Negahban, S. Oh, and D. Shah.  Iterative ranking from pair-wise comparisons.  _Operations Research_ , 65(1):266–287, 2016.
  * Nguyen and Caruana [2008] N. Nguyen and R. Caruana.  Classification with partial labels.  In _Proceedings of the 14th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 551–559, 2008.
  * Papandreou et al. [2015] G. Papandreou, L. Chen, K. P. Murphy, and A. L. Yuille.  Weakly-and semi-supervised learning of a deep convolutional network for semantic image segmentation.  In _Proceedings of the International Conference on Computer Vision_ , pages 1742–1750, 2015.
  * Qin and Liu [2013] T. Qin and T. Liu.  Introducing LETOR 4.0 datasets.  _arXiv:1306.2597 [cs.IR]_ , 2013.
  * Ratner et al. [2017] A. Ratner, S. H. Bach, H. Ehrenberg, J. Fries, S. Wu, and C. Ré.  Snorkel: rapid training data creation with weak supervision.  _Proceedings of the VLDB Endowment_ , 11(3):269–282, 2017.
  * Redmon et al. [2016] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi.  You only look once: Unified, real-time object detection.  In _Proceedings of the 26th IEEE Conference on Computer Vision and Pattern Recognition_ , pages 779–788, 2016.
  * Romano et al. [2019a] Y. Romano, R. Barber, C. Sabatti, and E. J. Candes.  With malice towards none: Assessing uncertainty via equalized coverage.  _arXiv:1908.05428 [stat.ME]_ , 2019a.
  * Romano et al. [2019b] Y. Romano, E. Patterson, and E. J. Candès.  Conformalized quantile regression.  In _Advances in Neural Information Processing Systems 32_ , 2019b.
  * Romano et al. [2020] Y. Romano, M. Sesia, and E. J. Candès.  Classification with valid and adaptive coverage.  In _Advances in Neural Information Processing Systems 33_ , 2020.
  * Sadinle et al. [2019] M. Sadinle, J. Lei, and L. Wasserman.  Least ambiguous set-valued classifiers with bounded error levels.  _Journal of the American Statistical Association_ , 114(525):223–234, 2019.
  * Sculley et al. [2015] D. Sculley, G. Holt, D. Golovin, E. Davydov, T. Phillips, D. Ebner, V. Chaudhary, M. Young, J.-F. Crespo, and D. Dennison.  Hidden technical debt in machine learning systems.  In _Advances in Neural Information Processing Systems 28_ , 2015.
  * Taskar [2005] B. Taskar.  _Learning Structured Prediction Models: A Large Margin Approach_.  PhD thesis, Stanford University, 2005.
  * Taskar et al. [2003] B. Taskar, C. Guestrin, and D. Koller.  Max-margin markov networks.  In _Advances in Neural Information Processing Systems 16_ , 2003.
  * Tibshirani et al. [2019] R. J. Tibshirani, R. F. Barber, E. J. Candès, and A. Ramdas.  Conformal prediction under covariate shift.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Triggs and Verbeek [2008] B. Triggs and J. Verbeek.  Scene segmentation with crfs learned from partially labeled images.  In _Advances in Neural Information Processing Systems 21_ , volume 20, pages 1553–1560, 2008.
  * Tsochantaridis et al. [2004] I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun.  Support vector machine learning for interdependent and structured output spaces.  In _Proceedings of the Twenty-First International Conference on Machine Learning_ , 2004.
  * van Rooyen and Williamson [2018] B. van Rooyen and R. C. Williamson.  A theory of learning with corrupted labels.  _Journal of Machine Learning Research_ , 18(228):1–50, 2018.
  * van Zuylen et al. [2007] A. van Zuylen, R. Hegde, K. Jain, and D. P. Williamson.  Deterministic pivoting algorithms for constrained ranking and clustering problems.  In _Proceedings of the Eighteenth ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 405–414. Society for Industrial and Applied Mathematics, 2007.
  * Vazirani [2001] V. V. Vazirani.  _Approximation Algorithms_.  Springer, 2001.
  * Vovk et al. [2005] V. Vovk, A. Grammerman, and G. Shafer.  _Algorithmic Learning in a Random World_.  Springer, 2005.
  * Wolsey [1982] L. A. Wolsey.  An analysis of the greedy algorithm for the submodular set covering problem.  _Combinatorica_ , 2:385–393, 1982.
  * Yu et al. [2014] H.-F. Yu, P. Jain, P. Kar, and I. S. Dhillon.  Large-scale multi-label learning with missing labels.  In _Proceedings of the 31st International Conference on Machine Learning_ , volume 32, pages 593––601, 2014.
  * Zhang et al. [2017] C. Zhang, C. Ré, M. Cafarella, C. De Sa, A. Ratner, J. Shin, F. Wang, and S. Wu.  DeepDive: Declarative knowledge base construction.  _Communications of the ACM_ , 60(5):93–102, 2017\.

##  Appendix A Proofs of mathematical results

###  A.1 Proofs of lower bounds on confidence set sizes

####  A.1.1 Proof of Theorem 1

Suppose that $P$ is a consistent distribution on
$\mathcal{X}\times\mathcal{Y}\times 2^{\mathcal{Y}}$, with marginal
$P_{\textup{weak}}$ over $\mathcal{X}\times 2^{\mathcal{Y}}$, and consider a
procedure $\widehat{C}_{n}$ offering $1-\alpha$ strong distribution-free
coverage. Let $\tilde{P}$ be the distribution on
$\mathcal{X}\times\mathcal{Y}\times 2^{\mathcal{Y}}$ with
$\tilde{P}_{\textup{weak}}=P_{\textup{weak}}$, and where we define $\tilde{P}$
by the triple $(\tilde{X},\tilde{Y},\tilde{W})\sim\tilde{P}$ according to

$\displaystyle\tilde{Y}=\mathop{\rm
argmin}_{y\in\tilde{W}}\left\\{p_{n}(\tilde{X},y)\coloneqq\mathbb{P}_{(X_{i},W)_{i=1}^{n}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P_{\textup{weak}}}\left[y\in\widehat{C}_{n}(\tilde{X})\right]\right\\}.$

Then, $\tilde{P}$ is a consistent distribution on
$\mathcal{X}\times\mathcal{Y}\times 2^{\mathcal{Y}}$, which ensures that

$\displaystyle\mathbb{P}_{(X_{i},Y_{i},W_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}\tilde{P}}\left[Y_{n+1}\in\widehat{C}_{n}(X_{n+1})\right]\geq
1-\alpha.$

By definition of $\tilde{P}$, we have

$\displaystyle\mathbb{P}_{(X_{i},Y_{i},W_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}\tilde{P}}\left[Y_{n+1}\in\widehat{C}_{n}(X_{n+1})\right]=\mathbb{E}_{(X_{n+1},Y_{n+1},W_{n+1})\sim\tilde{W}}\left[p_{n}(X_{n+1},Y_{n+1})\right],$

the law of $\widehat{C}_{n}$ is identical under $P$ or $\tilde{P}$, as it only
depends on $(X_{i},W_{i})_{i=1}^{n}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P_{\textup{weak}}$.

On the other hand, we observe that when
$(X_{n+1},Y_{n+1},W_{n+1})\sim\tilde{P}$,

$\displaystyle p_{n}(X_{n+1},Y_{n+1})=\inf_{y\in W_{n+1}}p_{n}(X_{n+1},y),$

which guarantees that

$\displaystyle 1-\alpha$
$\displaystyle\leq\mathbb{E}_{(X_{n+1},Y_{n+1},W_{n+1})\sim\tilde{P}}\left[p_{n}(X_{n+1},Y_{n+1})\right]$
$\displaystyle=\mathbb{E}_{(X_{n+1},Y_{n+1},W_{n+1})\sim\tilde{P}}\left[\inf_{y\in
W_{n+1}}p_{n}(X_{n+1},y)\right]$
$\displaystyle=\mathbb{E}_{(X_{n+1},W_{n+1})\sim\tilde{P}_{\textup{weak}}}\left[\inf_{y\in
W_{n+1}}p_{n}(X_{n+1},y)\right]$
$\displaystyle=\mathbb{E}_{(X_{n+1},W_{n+1})\sim
P_{\textup{weak}}}\left[\inf_{y\in W_{n+1}}p_{n}(X_{n+1},y)\right].$

####  A.1.2 Proof of Corollary 2.2

Consider $(X,W)\sim P_{\textup{weak}}$ independent of $(X_{i},W_{i})_{i\geq
1}$, and define $p(x,y)=\mathbb{P}(y\in C(x))$, recalling the definition
$p_{n}(x,y)=\mathbb{P}(y\in\widehat{C}_{n}(x))$. By Jensen’s inequality,

$\displaystyle\mathbb{E}\left[\Big{|}\inf_{y\in W}p(X,y)-\inf_{y\in
W}p_{n}(X,y)\Big{|}\right]\leq\sum_{y\in\mathcal{Y}}\mathbb{E}\left[\left|p(X,y)-p_{n}(X,y)\right|\right]$
$\displaystyle\qquad\quad\qquad\qquad\qquad\qquad\leq\mathbb{E}\\!\left[\sum_{y\in\mathcal{Y}}\left|1\\{y\in\widehat{C}_{n}(X)\\}-1\\!\left\\{y\in
C(X)\right\\}\right|\right]=\mathbb{E}\left[|\widehat{C}_{n}(X)\triangle
C(X)|\right].$

Taking the limit as $n\to\infty$ and using that $\mathbb{E}[\inf_{y\in
W}p_{n}(X,y)]\geq 1-\alpha$ from Theorem 1, we must also have

$\displaystyle\mathbb{E}\left[\inf_{y\in W}p(X,y)\right]\geq 1-\alpha.$

Since $\inf_{y\in W}p(X,y)\in[0,1]$, we must have $\mathbb{P}(\inf_{y\in
W}p(X,y)=0)\leq\alpha$, which gives the desired result: there exists $y\in
W\cap\textup{Det}_{C}(x)\setminus C(x)$ if and only if $y\in
W\cap\\{y\in\mathcal{Y}:p(x,y)=0\\}$, i.e. if and only if $\inf_{y\in
W}p(x,y)=0$.

###  A.2 Proofs on size set optimality in weak supervision

####  A.2.1 Proof of Lemma 3.1

Fix $\eta_{0}\in(0,1)$. Then $y\in C_{\eta_{0}}(x,u)$ implies that
$s^{\textup{nest}}(x,y,u)=\inf\\{\eta\mid y\in C_{\eta}(x,u)\\}\leq\eta_{0}$
and so $s^{\textup{nest}}(x,y,u)\leq\eta_{0}$. Conversely, assume that
$s^{\textup{nest}}(x,y,u)\leq\eta_{0}$. Then by definition of
$s^{\textup{nest}}$, $y\not\in C_{\eta_{0}}(x,u)$ if and only if for all
$\eta>\eta_{0}$, we have $y\in C_{\eta}(x,u)$ but $y\not\in
C_{\eta_{0}}(x,u)$, and therefore $s^{\textup{nest}}(x,y,u)=\eta_{0}$. But of
course, by continuity, $\mathbb{P}(s^{\textup{nest}}(x,y,U)=\eta_{0})=0$, and
so

$\mathbb{P}(s^{\textup{nest}}(x,y,U)\leq\eta_{0}~{}\mbox{and}~{}y\not\in
C_{\eta_{0}}(x,U))=0.$

####  A.2.2 Proof of Proposition 2

The case where $W\mid X=x$ has a label-independent structure is immediate,
hence we focus on proving the result when $W\mid X=x$ has a label tree-
structure (8).

We prove the result by induction on the size of $\mathcal{Y}^{\star}$,
observing that the result is immediate if $|\mathcal{Y}^{\star}|=1$. If
$|\mathcal{Y}^{\star}|=K>1$, we assume that the result holds on sets with at
most $K-1$ elements.

We denote $P_{x}$ the law of $W\mid X=x$, by $P_{u}$ the law of $U$ and
$\mathbb{P}=P_{x}\otimes P_{u}$ their joint distribution, and similarly for
their expectations.

Fix $\eta\in(0,1)$, and let $C:[0,1]\rightrightarrows\mathcal{Y}^{\star}$ be a
confidence set mapping satisfying

$\displaystyle\mathbb{P}(C(U)\cap W\neq\emptyset)\geq\eta.$

We will prove that

$\displaystyle E_{u}|C_{\eta}^{\text{Greedy}}(x,U)|\leq E_{u}|C(U)|.$

We use the label ranking $y_{1}(x),\dots,y_{K}(x)$ that Alg. 2 defines,
omitting $x$ for simplicity, and consider two cases:

  * •

Case 1: $P_{u}(y_{K}\in C(U))=0$.

Then $C$ provides coverage at level $\eta$ using only the $K-1$ first labels,
which also guarantees that $C_{\eta}^{\text{Greedy}}(x,u)$ only contains
labels in $\\{y_{1},\dots,y_{K-1}\\}$ (since, in that case, $J_{\eta}\leq K-1$
in Alg. 2). The induction hypothesis applied to the distribution of
$W\setminus\\{y_{K}\\}$ thus ensures that
$E_{u}|C_{\eta}^{\text{Greedy}}(x,U)|\leq E_{u}|C(U)|$.

  * •

Case 2: $P_{u}(y_{K}\in C(U))>0$.

In that case, we will prove that either $P_{u}(y_{j}\in C(U))=1$ for all
$j\in[K-1]$, or that we can build a new confidence set $C^{\text{final}}(U)$
such that

$\displaystyle\mathbb{P}(C^{\text{final}}(U)\cap W\neq\emptyset\mid
X=x)\geq\mathbb{P}(C(U)\cap W\neq\emptyset\mid
X=x),~{}E_{u}|C^{\text{final}}(x,U)|=E_{u}|C(U)|,$

and verifies either $P_{u}(y_{j}\in C^{\text{final}}(U))=1$ for all
$j\in[K-1]$, or $P_{u}(y_{K}\in C^{\text{final}}(U))=0$.

The distribution $P_{x}$ induces a tree whose leaves are the labels
$y_{1},\dots,y_{K}$, and each inner node $N$ (apart from the root, which is
$\mathcal{Y}^{\star}$ itself) is a subset of $\mathcal{Y}^{\star}$ such that
$P_{x}(W=N)>0$, and two nodes $N_{1}$ and $N_{2}$ share the same parent if any
subset $C$ containing strictly either $N_{1}$ or $N_{2}$ such that
$P_{x}(W=C)>0$ contains $N_{1}\cap N_{2}$. This parent is then the smallest
subset $N_{p}$ such that $N_{1}\cap N_{2}\subset N_{p}$ and
$P_{x}(W=N_{p})>0$. Each parent is then the union of all its children. Figure
1 provides an example of such a tree.

Defining $D(C)\coloneqq\\{y\in\mathcal{Y}^{\star}\setminus\\{y_{K}\\}\mid
P_{u}(y_{j}\in C(U))<1\\}\neq\emptyset$, we consider the element $\tilde{y}\in
D(C)$ sharing the lowest common ancestor with $y_{K}$ in the tree. For
instance, in Figure 1, if $D(C)=\\{y_{3},y_{4}\\}$, then $y_{D}=y_{3}$, as
their common ancestor $W_{0}$ is lower than the common ancestor of $y_{5}$ and
$y_{4}$ ($\mathcal{Y}^{\star}$ itself).

We then proceed to define $\tilde{C}(U)$ from $C(U)$ so that

$\displaystyle\tilde{C}(U)\setminus\\{y_{K},y_{D}\\}=C(U)\setminus\\{y_{K},y_{D}\\}$
(23)

and

$\displaystyle
E_{u}|\tilde{C}(U)\cap\\{y_{K},y_{D}\\}|=E_{u}|C(U)\cap\\{y_{K},y_{D}\\}|,$
(24)

but now either

$\displaystyle
P_{u}(y_{D}\in\tilde{C}(U))=1~{}\text{or}~{}P_{u}(y_{K}\in\tilde{C}(U))=0.$

In practice, we do so by replacing $y_{K}$ by $y_{D}$ when
$C(U)\cap\\{y_{K},y_{D}\\}=\\{y_{K}(x)\\}$, or/and decreasing the
probabilities that $\tilde{C}(U)\cap\\{y_{K},y_{D}\\}=\\{y_{D},y_{K}\\}$ and
$C(U)\cap\\{y_{K},y_{D}\\}=\emptyset$, in such a way that the average size
does not vary, but the probability that
$C(U)\cap\\{y_{K},y_{D}\\}=\\{y_{D}\\}$ increases.

We then proceed to check that such a change cannot hurt our coverage, while it
evidently leaves the average confidence set size unchanged (because of
equations (23) and (24)).

The only way we can have $C(U)\cap W\neq\emptyset$ and $\tilde{C}(U)\cap
W=\emptyset$ is if $W=\left\\{y_{K}\right\\}$. On the other hand, when
$W=\left\\{y_{D}\right\\}$, we can have $C(U)\cap W=\emptyset$ but
$\tilde{C}(U)\cap W\neq\emptyset$. Because of the definition of $y_{D}$ with
respect to $y_{K}$, any other value of $W$ such that $C(U)\cap W\neq\emptyset$
will be such that $\tilde{C}(U)\cap W\neq\emptyset$. In particular, by
independence of $W$ and $U$, we have

$\displaystyle\mathbb{P}(\tilde{C}(U)\cap W\neq\emptyset)-\mathbb{P}(C(U)\cap
W\neq\emptyset)$ $\displaystyle\begin{split}&\geq
P_{x}(W=\\{y_{K}(x)\\})\left[P_{u}(y_{K}\in\tilde{C}(U))-P_{u}(y_{K}\in
C(U))\right]\\\
&+P_{x}(W=\\{y_{D}\\})\left[P_{u}(y_{D}\in\tilde{C}(U))-P_{u}(y_{D}\in
C(U))\right]\end{split}$
$\displaystyle=\left(P_{u}(y_{D}\in\tilde{C}(U))-P_{u}(y_{D}\in
C(U))\right)\left(P_{x}(W=\\{y_{D}\\})-P_{x}(W=\\{y_{K}\\})\right),$

since $P_{u}(y_{K}\in\tilde{C}(U))+P(y_{D}\in\tilde{C}(U))=P_{u}(y_{K}\in
C(U))+P(y_{D}\in C(U))$, as the total average size does not vary.

In addition, since $y_{K}$ gets selected last in Alg. 2, we know that for all
$y\in\mathcal{Y}^{\star}$,

$\displaystyle P_{x}\left(W=\\{y_{D}\\}\right)\geq
P_{x}\left(W=\\{y_{K}\\})\right),$

which achieves to prove that

$\displaystyle\mathbb{P}(\tilde{C}(U)\cap
W\neq\emptyset)\geq\mathbb{P}(C(U)\cap W\neq\emptyset)\geq\eta.$

If $P_{u}(y_{D}\in\tilde{C}(U))=1$, then $|D(\tilde{C})|\leq|D(C)|-1$, and we
can repeat the process until we obtain a final mapping $C^{\text{final}}$ such
that either $D(C^{\text{final}})=\emptyset$ or $\mathbb{P}(y_{K}(x)\in
C^{\text{final}}(U))=0$.

In the first scenario where eventually $D(C^{\text{final}})=\emptyset$, it
means that $C^{\text{final}}(U)$ is either $\mathcal{Y}^{\star}$ or
$\mathcal{Y}^{\star}\setminus\\{y_{K}\\}$, and this is immediate to check that
since $\mathbb{P}(C^{\text{final}}(U)\cap W\neq\emptyset\mid X=x)\geq\eta$, we
must have $P_{u}(y_{K}\in C^{\text{final}}(U))\geq P_{u}(y_{K}\in
C_{\eta}^{\text{Cond-Prox}}(x,U))$, which in turn ensures that

$\displaystyle E_{u}|C_{\eta}^{\text{Cond-Prox}}(x,U)|\leq
E_{u}|C^{\text{final}}(U)|=\mathbb{E}|C(U)|.$

In the second case, since $P_{U}(y_{K}\in C^{\text{final}}(U))=0$,
$C^{\text{final}}$ is effectively a confidence set over strictly less than $K$
labels, in which case we can apply the induction hypothesis to conclude that

$\displaystyle E_{u}|C_{\eta}^{\text{Cond-Prox}}(x,U)|\leq
E_{u}|C^{\text{final}}(U)|=E_{u}|C(U)|.$

###  A.3 Proofs of algorithms validity

####  A.3.1 Proof of Lemma 4.2

We prove the result by proving that if we run Algorithm 3 with $M=K!$,
defining at each step $y_{j,2}^{m}$ as in equation (14), then at each step
$m\leq K!$ of the algorithm, $\\{\mathcal{Y}_{j}^{m}\\}_{j\in[m]}$ is a valid
partition of $\mathcal{Y}$ that satisfies the following conditions:

  1. 1.

For each $j\in[m]$, we have $\mathcal{Y}_{j}^{m}=\\{y_{j}^{m}\\}$ if and only
if there exists no $i\in[K-1]$ such that $(i+1~{}i)\circ
y_{j}^{m}\in\mathcal{Y}_{j}^{m}$.

  2. 2.

If $\mathcal{Y}_{j}^{m}\neq\\{y_{j}^{m}\\}$ then $s(x,y_{j}^{m})\leq
s(x,y_{j,2}^{m})$.

If the partition satisfies these two conditions at every step, then we can run
the algorithm until step $m=K!$, at which point it returns a partition
$\\{\mathcal{Y}_{j}^{K!}\\}_{k=1}^{K!}$ such that
$s(x,y_{1}^{K!})\leq\dots\leq s(x,y_{K!}^{K!})$. Now, since we have
$s_{j}^{m}=s_{j}^{K!}$ for every $1\leq j\leq m$, we conclude that, at each
step $m\in[K!]$, we have

$\displaystyle s(x,y_{1}^{m})\leq s(x,y_{2}^{m})\leq\dots\leq
s(x,y_{m}^{m})\leq\min_{y\in\mathcal{Y}\setminus\\{y_{1}^{m},\dots,y_{m}^{m}\\}}s(x,y),$

which proves the validity of the algorithm.

This is of course true for $m=1$, since the best configuration simply ranks
$r_{k}(x)$ in decreasing order.

  1. 1.

By definition of $y_{\text{ind}(m),2}^{m}$ and $y_{\text{ind}(m)}$,
$\\{\mathcal{Y}_{j}^{m+1}\\}_{j=1}^{m+1}$ is a valid partition of
$\mathcal{Y}$ such that each $y_{j}^{m+1}\in\mathcal{Y}_{j}^{m+1}$, if
$\\{\mathcal{Y}_{j}^{m}\\}$ is itself a valid partition (and $m<K!$), so long
as we can prove that if $\mathcal{Y}_{j}^{m}\neq\\{y_{j}^{m}\\}$, then there
must exist $\alpha\in[K-1]$ such that $(\alpha+1~{}\alpha)\circ
y_{j}^{m}\in\mathcal{Y}_{j}^{m}$ (i.e the algorithm does not get stuck and
terminates). But this is immediate as, if for all $\alpha\in[K-1]$, we have
$(\alpha+1~{}\alpha)\circ y_{j}^{m}\notin\mathcal{Y}_{j}^{m}$, then it must be
by construction that

$\displaystyle\mathcal{Y}_{j}^{m}\subset\bigcap_{\alpha\in[K-1]}\\{y\in\mathcal{Y}\mid
y^{-1}(y_{j}^{m}(\alpha))<y^{-1}(y_{j}^{m}(\alpha+1))\\}=\\{y_{j}^{m}\\}.$

Therefore, at each step $m\leq K!$ of the algorithm,
$\\{\mathcal{Y}_{j}^{m}\\}_{j\in[m]}$ is a valid partition of $\mathcal{Y}$,
and the algorithm terminates.

  2. 2.

On the other hand, it requires more care to justify why, if we set, for all
$j\leq m$,

$\displaystyle y_{j,2}^{m}\coloneqq\mathop{\rm
argmin}_{y\in\mathcal{Y}_{j}^{m}}\\{s(x,y)\mid\exists\alpha\in[K-1],~{}y=(\alpha+1~{}\alpha)\circ
y_{j}^{m}\\}$

then we should always have

$\displaystyle s(x,y_{j}^{m})\leq s(x,y_{j,2}^{m})$ (25)

for all $j\in[m]$, i.e. why any permutation of the form
$(\alpha~{}\alpha+1)\circ y_{j}^{m}$ that belongs to $\mathcal{Y}_{j}^{m}$
cannot strictly decrease the score $s(x,y)$.

Equation (25) actually results from a crucial property of the score function
(13), which ensures that if $s(x,y)<s(x,(\alpha~{}\alpha+1)\circ y)$, then it
must hold that

$\displaystyle r_{y(\alpha)}(x)<r_{y(\alpha+1)}(x),$

i.e. the elements $y(\alpha)$ and $y(\alpha+1)$ were originally in the wrong
order in $y$.

But, since we start the partition process with $y_{1}^{1}$ such that
$r_{y_{1}^{1}(1)}(x)\geq\dots\geq r_{y_{1}^{1}(k)}(x)$, i.e with all elements
in the correct order, it is straightforward to check that at any time $m$,
there cannot exist a permutation of the form $(\alpha~{}\alpha+1)\circ
y_{j}^{m}$ that also belongs to $\mathcal{Y}_{j}^{m}$ such that

$\displaystyle r_{y_{j}^{m}(\alpha)}(x)<r_{y_{j}^{m}(\alpha+1)}(x):$

if that were the case, then there would exist $l\leq j$ such that
$y_{j}^{m}(\alpha)$ and $y_{j}^{m}(\alpha+1)$ were the elements exchanged at
time $l$ when creating the partition
$\\{\mathcal{Y}^{l+1}_{i}\\}_{i=1}^{l+1}$. In turn, since
$y_{j}^{m}\in\mathcal{Y}_{j}^{m}$, this would guarantee that

$\displaystyle\mathcal{Y}_{j}^{m}\subset\\{y\in\mathcal{Y}\mid
y^{-1}(y_{j}^{m}(\alpha))<y^{-1}(y_{j}^{m}(\alpha+1))\\},$

and thus that $(\alpha~{}\alpha+1)\circ y_{j}^{m}\notin\mathcal{Y}_{j}^{m}$.
This guarantees that any configuration $(\alpha~{}\alpha+1)\circ
y_{j}^{m}\in\mathcal{Y}_{j}^{m}$ satisfies

$\displaystyle s(x,(\alpha~{}\alpha+1)\circ y_{j}^{m})\geq s(x,y_{j}^{m}),$

and thus that either $\mathcal{Y}_{j}^{m}=\\{y_{j}^{m}\\}$, or

$\displaystyle s(x,y_{j,2}^{m})\geq s(x,y_{j}),$

which concludes the proof.