Deep Generalized Prediction Set Classifier and Its Theoretical Guarantees
Authors: Zhou Wang
Xingye Qiao
Venue: Accepted by TMLR ()

Abstract: A standard classification rule returns a single-valued prediction for any observation without a confidence guarantee, which may result in severe consequences in many critical applications when the uncertainty is high. In contrast, set-valued classification is a new paradigm to handle the uncertainty in classification by reporting a set of plausible labels to observations in highly ambiguous regions. In this article, we propose the Deep Generalized Prediction Set (DeepGPS) method, a network-based set-valued classifier induced by acceptance region learning. DeepGPS is capable of identifying ambiguous observations and detecting out-of-distribution (OOD) observations. It is the first set-valued classification of this kind with a theoretical guarantee and scalable to large datasets. Our nontrivial proof shows that the risk of DeepGPS, defined as the expected size of the prediction set, attains the optimality within a neural network hypothesis class while simultaneously achieving the user-prescribed class-specific accuracy. Additionally, by using a weighted loss, DeepGPS returns tighter acceptance regions, leading to informative predictions and improved OOD detection performance. Empirically, our method outperforms the baselines on several benchmark datasets.

Published in Transactions on Machine Learning Research (05/2024)
Deep Generalized Prediction Set Classifier and Its Theoretical Guarantees
Zhou Wang
auong198@hhinghnnton.dd
Deportment of Mathematics ond Statistics Binghamton University, the State University of New York
Xingye Qiao
zqiaao agiihbbbingammto.. edu
Deportment Mathematics and Statistics
Binghamton University, the State University of New York
Reviewed on OpenReview: https: opwnreviee......... net/ pertffrmm?? id= N7gN7gLN5
Abstract
standard classification rule returns a single-valued prediction for any observation without a confidence guarantee, which may result in severe consequences in many critical applica- tions when the uncertainty is high. In contrast, sct-valued classification is new paradigm to handle the uncertainty in classification by reporting set of plausible labels to observations in highly ambiguous regions. In this article, propose the Deep Generalized Prediction Set (DecpGPS) method, network-based set-valued classifier induced by acceptance region learning. DeepGPS is capable of identifying ambiguous observations and detecting out-of- distribution (OOD) observations. It the first set-valued classification this kind with a theoretical guarantee and scalable to large datasets. Our nontrivial proof shows that the risk of DeepGPS, defined as the expected size of the prediction set, attains the optimality within neural network hypothesis class while simultaneously achieving the user-prescribed class-specific accuracy. Additionally, by using a weighted loss, DeepGPS returns tighter acceptance regions, leading to informative predictions and improved OOD detection perfor- mance. Empirically, our method outperforms the baselines on several benchmark datasets.
1 Introduction
A standard classification method assigns only single class label to each test observation, regardless of its confidence toward this prediction. However, this approach might be problematic in critical domains where even a single incorrect decision can lead to disastrous consequences, such as medical imaging- di- agnosis, autonomous driving systems, and military operations. Additionally, such a paradigm falls short in effectively controlling class-specific outcomes, especially in scenarios of imbalanced data. For instance, in medical diagnosis, it may incorrectly priorilize majority groups that do not need inmeddaaee altetion while overlooking minority groups with certain diseases that demand urgent attention. This skewed prioritization results in delayed treatments, and ultimately, compromised patient outcomes. Lastly, conventional classifi- cation approaches often assume there is no distribution shift between the training and the test data, which is not the case in the open world. If a new class emerges, e.g., a new variant virus the pandemic, is imperative to detect out-of-distribution points. Therefore, there a crucial need for novel methods that can simultaneously address these issues and deliver reliable and risk-controllable decision in high-stake fields.
To mitigate the risks associated with conventional single-valued predictions, classifiers can first report multi- ple plausible labels for ambiguous observations in overlapped class regions (see Fig. 1 This approach allows for human intervention or secondary classification with additional features, ultimately reducing the risk of im- prudent predictions. This has motivated the development of set-valued classification methods, which can implemented in various ways. Classification with Reject Option (CRO) (Herbei Wegkamp) (2006] [aatlett
& Wegkamp, 2008 Zhang al.) 2018 Charoenphakdee et al. 2021 interprets rejection of a difficult

---

Published in Transactions on Machine Learning Research (05/2024)
observation assigning all class labels to it, and trains the classifier by incorporating the rejection cost in the objective function. However, this method does not offer controlled mis- classification rates for classes of interest, and it pertains to the closed-world selting.
Digh
Digkt
Dapi Da
9
7
4
C
To secure a trustworthy misclassification rate, Conformal Pre- diction (CP) (Vovk et al,, 2005; Lei et al.) 2013 2015). popu- lar model-free framework, is developed in the machine learning community. With its theoretical guarantec on the prediction error rate, CP provides a safety solution in critical applications by generating prediction sets that encompass multiple plausi- ble labels. Alternatively, Classification with Confidence (Lei
U
Figure 1: Illustration for MNIST class re- gions. Ambiguous points inside overlapped circles, OODs outside all circles.
2014 Sadinle al., 2019 Wang Qiao 2018 2022 Lin
2022) further optimizes the prediction set from different perspective, aiming to yield the smallest, prediction
set while controlling the prescribed class-specific error rate. However, all these approaches focusing the closed world are limited to generalizing their capability of out-of-distributio detection in the open world, as they are not tailored to this task.
In practice, data distribution may evolve and observations outside of existing classes in the training data may appear in the test. data. To address this challenge, out-of-distributioo (OOD) detection or open-set recognition (OSR) techniques (Bendale & Boult 2015 Vaze et al. 2022 Kim al., 2023) have been developed to detect the OOD class in addition to classification. Note that their single-valued decision-making rules still suffer the aforementioned restrictions. To overcome these limitations, researchers have proposed set- valued classifiers to detect OOD samples with controlled misclassification rates on each existing class, namely, Cautious Deep Learning (CDL) [Hechtlinger et al. 2018), Balanced and Conformal Optimized Prediction Set (BCOPS) Guan & Tibshirani 2022). and Generalized Prediction Set (GPS) (Wang & Qiao, 2023 However, three methods are trained in a decoupled way, which may discard the underlying dependence among the learned acceptance regions across all classes. Additionally, besides GPS relies on computationally intensive quadratic programming, all three are shallow methods, making it challenging to scale the above methods to large datasets. Moreover, per empirical performances, the GPS results in conservative acceptance regions due to the use of hinge loss, leading to sub-optimal finite-sample performances on both prediction set size and OOD detection; the CDL and BCOPS lack optimality on the empirical prediction set size, partially due to the fact that the prediction set size is not explicitly minimized.
In light of the limitations of current single-valued and set-valued prediction approaches, we propose an end-to-end Deep Generalized Prediction Set (DeepGPS) classifier jointly learning acceptance regions with several contributions. First, it generalizes and scales the set-valued classification to OOD detection by using hypothesis class induced by neural networks and kernel. To avoid relying the expensive memory and quadratic programming for kernel machines, we add to the neural network a layer that approximates the kernel by using Random Fourier Features. Second, we provide nontrivial proof that shows the true accuracy of our classifier is bounded as the prescribed value, and that the expected prediction set size converges to the minimum within the hypothesis class. Third, we use an adaptive weighted loss to address the issue of GPS where the surrogate loss potentially produces larger acceptance regions. The weighted loss yields tighter acceptance regions, improving classification elficiency (defer to Section 2.1 and OOD detection performance.
2 Related Work
In this section, we introduce the notion of acceplance regions and terminologies in sel-valued classification, and briefly discuss some related works, Note that there is a distinction between set-valued classification and mubti-label classification (Zhang & Zhou (007)). In sct-valued classification, an observation has only one true label, whereas, in lubti-label classification, there are multiple ground truths. Throughout the article, use the notation [K] to denote I,...,K.
2

---

Published in Transactions on Machine Learning Research (05/2024)
2.1 Set-valued Classification
Consider the multicategory classification with input space = RP and label space y = fl...., , K}. Given a rule, the set of observations classified as class k; Cs C C,,, is called the acceptance region for class k; all K acceptance regions collectively induce a set-valued classifier & X' + 2 with Φ(x) == {k [K] E C.). Intuitively, there is trade-off between the misclassificattin rate P(Y & o(X)), ie., the probability of a set not containing the true class label, and the expected size of prediction set [x(X] - = 1(x E Cx). A lower misclassification rale may require a larger prediction set. While two set-valued classifiers may have the same misclassification rate, the one with smaller prediction size is more efficient/inliee /informative (the more efficient, the better the prediction set). We interchangeably use efficiency (sce the definition in Appendix B
and prediction set size to denote the informativeness of a prediction set..
In the method of Classification with Reject Option (CRO) (Herbei & Wegkamp 2006 Bartlett & Wegkamp 2008 Charocnphakdoe
al., 2021), the Bayes optimal rule under the 0-d-1 loss (where E [0, 1 1/K is the rejection cost, and is the misclassification cost) assigns an ambiguous observation all labels if max; P(Y = k: 2²) S 1 1-d, d, but a single label corresponding that with the largest probability score otherwise. Zhang et al. )0118) extended CRO with an additional refine option, which can output smaller prediction
set with size < [(x=) < K for those less difficult observations. CRO controls how many observations are rejected by changing the rejection cost. d (a smaller d leads to more rejections). While this can improve the accuracy for those observations not rejected, there is no direct control over the classification accuracy.
In contrast, the Conformal Prediction set (Vovk et al. 2005 Lei et al, 2013 2015 theoretically guarantees the accuracy PP(Y E ((X)). However, Conformal Prediction does not aim to maximize the efficiency of the classifier, i.c., there is no guidance on how to make the prediction set as small, and hence informative possible. In particular, a classifier with prediction set size [=(x)) = K for all æ is useless even though its accuracy is 100%, while the single-valued prediction (lő(x)) = 1 for all Φ) might not be accurate albeit its 100% efficioncy. To take into account the efficiency and accuracy simultancously, Lei (2014). Sadinle et al.
(2019), and Wang & Qiao (2118 2022) minimize the expected prediction set size E X)] while controlling the class-specific misclassification rate IP(Y E Φ(X) Y = k) S 7 specified by the user. In duality, DDnis &
Hebiri 2017 2020) proposed to maximize the accuracy subject to a budget of prediction set size.
2.2
Outtof-distributiin Detection and Selective Classification
Anomaly detectors aim to identify anomaly points not from the existing/ gaisting/normal normal class. Onc-Class Support Vector Machine (OCSVM) (Schölkopf et al. 2000) and Support Vector Data Description (SVDD) (Tax & Duin 2004) are shallow detectors whose detection performance is improved with a kernel. To obtain better feature representations for large and complex data, Ruff et al. (2018) extended SVDD to Deep Support Vector Data Description by substituting neural networks for kernels.
Beyond the task of detectingg/rejcctnng anomaly points not belonging to any of the normal classes, Out- of-distribution (OOD) detection and Open-set recognition (OSR) (Yang et al., 2021 Bendale & Boult,
2015 2016) additionally conduct standard classification for normal observations. In contrast, Selective
Classification (El-Yaniv et al. 2010 Geifman & Yalyaniy 2017 Granese et al.] 2021 centers on rejecting difficult normal observations besides single-valued classification. Different from CRO, it does not equate this type of rejection with assigning all labels to an observation. By allowing rejecting OOD and difficult normal observations, Xia & Bouganis (2022): g Kim et al. (2023): ; Cen et al. (2023) : Zhu et al. (0023) studied Selective Classification with OOD Detection (SCOD). However, this unified rejection mixes up the OOD and normal observations, which may obstruct the downstream task since one may impose different strategies on different
types of rejections.
All the aforementioned classification methods with OOD detection still are attributed to the camp of single- valued classification, and hence suffer some issues highlighted in Section I In contrast, CDL, BCOPS, and GPS are set-valued approaches: they learn acceptance regions that collectively induce a prediction set to cover the true label with an advertised accuracy for normal points and reject potential OOD points. In particular, the prediction set Φ(z) comprises all the classes k E [K] whose acceptance region C₁ contains æ; when ((xr is empty, is marked as an OOD point.
3

---

Published in Transactions on Machine Learning Research (05/2024)
3 Methodology
In this section, we formulate the optimization problem of DeepGPS. Suppose that distribution P exclu- sively consists of K (known) normal classes, while a target distribution Q may contain an (unknown) OOD component. To facilitate our analysis, we introduce two key assumptions.
Assumption 1. pp( Y k) po(œ Y = k) holds true for all normal classes k E [K]. Assumption 2. We have access to labeled data from P and unlabeled data from Q.
The equal class-conditional density in Assumption in the OOD detection literature (Yang el al., 2021 Garg et. al. 2022) due to the emergence of novel class. For instance, in the sentiment analysis of product reviews, the established sentiments such as positive negative exhibit consistent linguistic patterns between past and current data, including the choice of words and sentence structures. However, when review expresses entirely new sentiments, it represents an instance of OOD data. Assumption 1 is often accompanied by the mild Assumption 2 dealing with the utilization of unlabeled data (Du Plessis et al. 2015
commonly employod characterize "semantic shift"
Guan & Tibshirani
2022 Garg et al. 2022 Katz-Samun et al.
2022
Rorna approdimation aa ((4 & de 2016 6 c1
Ontgen layer W
2.0
-u<0)-v
[1 [1-y-u].
weight function,
weighted lass, 5
lo5s
1.0
-1.0
-0.5
0.0
0.5
1.0
1.5
u
Figure 2: Functions with y = 0.1. The blue bent solid line denotes loss function (-). The dashed blue curve denotes weight function Wk.j in (3) The red curve represents the weighted loss in
Figure 3: Network architecture, Each neuron in the penultimate layer, i.e. the kernel approximation layer, outputs 2-d vector Čj.j [D]. The weight matrix W consists of random samples Ej ~ (m
Remark 1. Several promising strategies are rooted in the eristing literature to relox Assumption 7 hence accommodating tractable differences in class-condittonal densities between training and test sets. Specifically, (1) Tachet des Combes el al.) (2020) assumes that the identical class-conditional densily is maintained within a feature space, facilitated by a representation mapping I with (x()(X) Y k) po(ğ(X) This approach, however, necessitates an additional assumption regarding the partitioning within its feature space. (2) The work of Wu et al. (2019); Kurnar et al. (2000) delves into relazed label shift scenario, assuming small divergence between closs-con distribulions. Nevertheless, determining the exlent of this divergence in practice poses significant challenges, as highlighted by Garg et al. (2023). (3) Investigations by Zhang et al. [2013); Gong et al.) (2016) into the location-scale generalized target shift (LS-GeTarS) assume the erislence of an affine transformalion affecling each dimension of X given between the source and largel domains. Employing the kernel embedding method [Fukumizu et al. 2007: Sriperumbudur
k).
al.) (2011) enables the aligmment of the distribution between labeled data from the source domain and unlabeled data from the target domain. In the contezt of location-scale generalized target shift for normal classes, DeepGPS could be applied to the test data and the transformed truining data returned from the LS-Ge GoTor method.
Regarding the relazation of Assumption 2 involving additional unlabeled data, DeepGPS still works with the generated auziliary data [Hendrycks et al., 2019 Du et al.) 2022) even if one cannot access the test data. On the other hand, without accessing all data points, DeepGPS's application extends seamlessly to online learning environments, where the model is updated by optimizing objective function Eq. (1) with stochastic gradient descent each batch of data.

---

Published in Transactions on Machine Learning Research (05/2024)
Let (X X x y come from the distribution Q, where X' = R and y = {OOD, 1,2..,,KK Let f(z)= - ( (,,))...... (x)) be a vector of decision functions for normal classes, which induce the acceptance
regions through C. := {æ fx( 2 kj,k= E [K]. Then the set-valued classifier is defined as Ø : X + 2 with a prodiction <(x) == { E [K] : x E Cx} = { E [K] : fx(x) 2 0} for a query Z. The size of a prediction set ranges from 0 (OOD rejection), to (single-valued prediction), to somewhere in ( K- 1 (ambiguous observations), and ultimately to K (ambiguity rejection). Unlike CRO, which only rejects normal observations, or SCOD, which mixes rejections of normal and OOD observations, our unified decision rule not only rejects hard normal observations but also effectively distinguishes them from OOD rejections.
Objective Function. In addition to the task of OOD detection, we aim to minimize the expected size of prediction set Eg [lx(()) = Σk= [e[i[/[(X (X) 2 O}], subject to the class-specific error [o[](Ja(X] < 0} = S 7: E [K], where y is prescribed by users due to the business needs. Denote gk. k E [K] as the index set of labeled data from class (with size my) and Gu as the index set of unlabeled data (with size
n)), we solve data-driven optimization problem:
K
K
min JEFL
Σ Σ ((f((z))) VEGu k=1
+ C
3 k=1jE0
What (f,x()(2)))++ + J(F),
nk
mi
where f(x)= :- Wr((2)- P comes from the neural networks hypothesis class Fr. with depth L. Here Wr. & is the weight matrix in the output layer of the network, {(x) is the embedding learned from the penultimate layer, and p E RK is the offset term. The regularization J(f) == EL. A [[ + EK Xp(-ps) is used to confine the hypothesis class with parameters At, E [7] and X/ k E [K].
Instead of the 0-1 loss 1u 2 0} in E [. 2 03,, the first term in (1) measures the empirical prediction set size under a surrogate hinge loss (N) = [1 + w]+ = max 1 + uj. The second term in (T aims to provide a non-negative upper bound of (f( < 0) Y = k] -. To this end, notice that 1fu < 0} - 7 S [1 y u|+ (see Fig. D. By choosing (2) = [1 - 7--7-0 -77--++ minimizing the second term amounts to minimizing the excess empirical class-specific error beyond γ. When the loss (2,(()) in the second term goes to 0, the empirical error tends to be less than 7. The tuning parameter C' balances the risk between the prediction set size and the misclassification rate. Due to the Assumption D we use the labeled data from P to quantify the empirical misclassification rate in the second term initially measured under distribution Q. Lastly, similar to OCSVM (Schölkopf et al., 2000), together with the Gaussian kernel, -Pk in the third term J(f) in ① penalizes the offset and often allows to exclude most atypical observations from acceptance regions (see the intuition and discussion in Section 3 To avoid negative values in the optimization stage, one may use e -Pa instead of -pk in the third term.
Gaussian Kernel and Its Approximation. OCSVM achieves anomaly detection by using the Gaussian kernel with offset penalization (like the third term in (b)). Nonetheless, it is difficult to recover the exact features after the kernel mapping in the context of neural networks as the resultant feature would be infinite- dimensional. Morcover, the Representer theorem (Kimeldorf & Wahba 1971) suggests that the decision function is a linear combination of the kernel function evaluated at all the training data points. This can also be challenging in real business because each time we update the model, we only use a mini-batch (subset) of training data avoid computation and memory burden.
To overcome the above difficulties, in the penultimate layer of the network (see Fig. 3 we use finite Ran- dom Fourier Features (Rahimi & Rocht, 2007 Lu et al.] 2016: Nguyen & Vien 2018) to approximate the infmite-dimennsional Gaussian kernel features. More concretely, we sample D = m/-1122 many independent frequencies &, (j = 1,.... D) from the Gaussian distribution Im)=), where mL-2 and mı-1 are the widths of the (L- - 2)- and (L - 1)-th layers, respectively. Then we let the mapped feature fed to the output layer be
{(x) ((zz: = 1-2
1/2 (sin(oE) zæ), coE zz)...., cost
where ze is the embedding of output from the previous layer and the learnable parameter relates the kernel's flexibility. Bochner's theorem Rudiin 2017) shows that, for any 2 Zmyy the inner product
5

---

Published in Transactions on Machine Learning Research (05/2024)
(( (( )) is unbiased estimator to the true Gaussian kernel similarity exp (-o²1 Zaz 112 /2). where 0² plays a similar role as the bandwidth of Gaussian kernel in OCSVM. With the above kernel approximation, one can incorporate it into the neural network and use SGD optimization to efficiently update the model and hence scale the problem.
Insight behind the Gaussian Kernel (Approximation) with Offset Penalization. The Gaussian kernel and the for- mulation of the decision function f(x) with the penalization for -Pk, k E [K] in [1] are commonly used in (shallow) SVM-based
Acceptance region feature space for class
1.-
anomaly detection (Schōlkopf et al. 2000; 2014 Shilton et al. 2020).
Jumute & Suykens
0.8
hyperplane W = A
0.6
The term -ps in (x)) W WL&C(#)-Pk in f(x) typically comes with the term -pk in J(f), where WL, denotes the k-th row of the matrix W.. Note that the feature mapping/ /embeddin/g (()) involved with Gaussian kernel approximation maps each imput to the sphere of a ball because of <(x=) ((x) 1. Under this context, as shown in Fig. 1 penalizing -pk during the optimiza- tion contributes to an increased distance (Schölkopf et al. 2000).
0.4
Rejection region in feature space for all other classes
0.0
0.0
0.2
0.4
0.6
0.8
1.0
TW...ll between the origin and the hyperplane W (L, Pk in the feature space. This spatial shift effectively pushes the hy- perplane outwards, resulting in narrower acceptance region the feature space sphere dedicated to the normal class k. It consequently creates more room for other classes (including the potential OOD class), possibly leading to an informative prediction and an improved OOD de- tection performance. To see the effectiveness of the approximated Gaussian Kernel with Offset. Penalization, please see its ablation study in Fig. 7
Figure 4: Mustration of Gaussian kernel (approximation) with offsct penalization
Adaptive Weighted Loss. The aforementioned loss function (u) in aims provide a convex relaxation to 1(u < 0} - 7, whose expectation measures the class-specific error rate less constant 7. However, there is gap between 1 < 0} ? and (u): an observation from the class k outside of and far away from the center of the acceptance region Ca may incur large loss (2,((), far larger than 1 Additionally, the loss (-) may be non-zero even if point falls in the correct acceptance region. In these cases, the loss (-) overestimates the true misclassification rate; as consequence, we tend to get large acceptance regions Cs. which inflates the prediction set size and dogrades the OOD detection performance. To alleviate this potential issue, we allocate a weight. to each observation to correct the overestimation. Specifically, we use small weight for the observations with a large loss (-,,(),, by defining the weight as
Wki =
1()(),)) <0 + (1 -1 )x(,)) 1(0 S fe(2,) < 1 -7,, f(,,)
1-7
(3)
where o > 0. If Pe(zz) in (3 is equal to f& (2y,), then the weighted loss in
becomes
Whij (Ix(s) = (1- (1- (x f2, (f((z;)), 5 fx otherwise
< <1-1
(4)
(z,) < 7
This is illustrated in Fig. Except for the middle interval, the weighted loss approximates [Ifu < 0} - - In the middle interval, a large value of the parameter g (we set q = 5) makes the weighted loss closer to 0. Here we use the classifier f& from the last iteration to approximate fx-
4 Learning Theory
In this section, we show the convergence rates of the kernel approximation, the boundness of the true class-specific error rate, and the excess risk of the classification. We assume that ||ø||| S co.
Let H4 = (h: h2(2) (Wi)), W. F ||ill S k1) be the hypothesis class with bounded Frobenius norm in the 1-th layer, where S is (activation) function that is 1-Lipschitz continuous, e.g.

---

Published in Transactions on Machine Learning Research (05/2024)
or the identity function. The input is returned from the previous layer if > 1 ReLU(-), = 1. Let FI., := {f hs. .... h1, 2 0, h1 E He,,, I E [ be hypothesis class of or equals x i deep dense neural networks (fused with a Gaussian kernel approximation) with depth L (see Fig. 3 and k = -Kk,....,;
When the hypothesis class FL.M is composited with certain loss functions, we introduce Fi == {- + Eks (ff((z))= : f (f,,"... .fk) E FL.x)
to denote a class, which involves applying the loss function & (.) element-wisely to f(Ø) and then summing the results. Furthermore, we define Th o FI,, == {x + fu (2)
f = (fi..... fk) E Fr.m.) as another class that extracts the k-th component from f(x).
Theorem 1. For each pair of observations Z; Jj let Zx. and nn, be their embeddings learned at (L 2)-th
layer, respectively. Denote (a Ra,) = exp (-o² Zæ, 12/2). For E(=;0) defined in Eq. 2 with probability at least 1- - 6 over Gaussian frequency sampling, we have
( - Ko (Zez 220) - V
4
2 log x
for fixed z and Z0z
(5)
and sup ([(=,;))(((();;0))) - ho (Z kwy) m;;
4v2 122
II Kit
4
2 log
(6)
mL-1 8"
For fixed embeddings ze; and z output from -22 layer, (5) implies that the cosine similarity between their mapped features in (I. 1)-th layer converges to the true kernel similarity ko (Ze;, zm,) the rate of O(mz-1²) if o = 72z) For any pair of inputs T;; my E X, (6) shows that besides the error due to the finite sampling of frequencies, the dissimilarity of two points propagated throughout the course of the network also contributes to the kornel approximation error. If the input space X' is compact, eventually, the error uniformly vanishes as the width of the penultimate layer goes to infinity.
Let (T.V) == if FL.x (f((2,((((()) | Y k] S v, k [K]] be a subspace where the popula- tion class-specific surrogate loss is bounded, and its empirical counterpart be Fi, = {f FL, 1 (f) (z:)) & k E [K]}. Without loss of generality, we set the adaptive weight in front of l2.7 to be 1. Theoretically, this simplification does not hurt our main theorems too much since it only affects the complexity of the loss function class by its Lipschitz constant. Then, by moving the socond and third terms in Problem ( to the constraint, we consider the below problem
a
K
min feFt. (5,) nk
(f((()))) ==k==
The below theorem gives an upper bound to the true class-specific misclassification rate less the advertised
value y measured under l2,, loss.
Theorem 2. Let f be a solution to Problem (7) and Un (6) = 2Rn,, (T o FL.N) + +r 2 log
2K a where the
Rademacher complexity Rie (Ax& o FL.N) = O logl mp)) vig
(og(yrs)
and r co II Ki. With probability at least 8,
simaltaneously for all normal class k E [K], we have
EQ (2,, (fax)) = S Tuk
Σ yi=k
+n (8).
and f Fi,,(, the above theorem indicates Pelfx()) < 0 Y = k] - S + (o), (0), which suggests way to control true misclassification rate. To bound the true misclassification rate by 7, one may use a more stringent tolerance, e.g., replace in the loss function 6,, by 7 0 where 0 2 v + On, (6). This holds for a large enough dataset and with a large value of C since a large value of C corresponds to the small value of v, and ing (8) + 0 as R2 + co.
Together with the fact Lfu <
Theorem 3 shows the classification risk, namely 4-aambiguity returned by an empirical minimizer converges to the least in the hypothesis class when the sample size of each normal class increases.
7

---

Published in Transactions on Machine Learning Research (05/2024)
Let r, Unz(0) take the forms as in Theorem and Re, E (elli(f((X)) be the l f-ambigguity where f is on empirieal minimizer of problem
Theorem 3.
K /e F 1ク--ー- M) nk ME (ff((z)))
(8)
and 0r = max nn (6). With probability at least 1 - 35, we have
(1) (x) < < Y 5 for k E [K]] and
(2) (e, 0E(0.7-201 20- 1 (E
min
min Re, (f) S 12 (FI.. + 12v / 2n log 3.
By using a more stringent error tolerance and fine-tuning the parameter C, statement (1) shows the true misclassification rate of each normal class below the advertised tolerance 7, Note that the second term in the L.H.S. of the statement (2) denotes the best performance over all those classifiers with the true misclassification rate bounded by y (here the interval for v holds when 0' + n& + oo). Together with the fact that the Rademacher complexity (F
O(n 1/2 log(n)) vanishes as + co, Statement (2) implies the prediction ((x) returned by the DeepGPS approaches to the least f-aabiggutt within the hypothesis class as n2 + 00, [K]. For the explicit expressions of Rigg (IT FL.x) and R, (FL, (F ) please
direct to 16 and 21 in Appendix D
5 Experiments
Baselines. DeepGPS compared with baselines (GPS, BCOPS, and CDL) tailored the task of set- valuvalued classification with OOD detection. Since these baselines shallow methods, to conduct fair comparison also use the learned features from DeepGPS the inputs for the baselines and refer to them as DeepGPS- based basclines, following the same regime in Ruff et al. (2020). We also compare with two SCOD methods,
namely SIRC (Xia & Bouganis 2022 and Open (Zhu et al. 2023). which demonstrates the limitation of single-valued predictions in the current task.
Datasets. We deploy all methods on CIFAR-10, MNIST, and Fashion-MNIST datasets. In CIFAR-10, the normal classes are (Bird, Cat, Deer, Dog, Frog, Horse} and the OOD class comes from {Airplane, Car, Ship, Truck). In MNIST, the normal classes are digits {1, 4, 6, 7, 9} and the OOD class consists of digits {0, 2, 3, 5, 8}. In MaShion-MNISTT the normal classes are {Pullover, Dress, Coal, Sandal, Ankle bool} and the OOD class is { (T-shirt, Trouser, Shirt, Sneaker, Bag} The values of 7 are prescribed as 0.05, 0.01, and 0.01 for CIFAR-10, MNIST, and Fashion-MNISTL respectively (the latter two tasks are relatively easy, hence a smaller 7). We split each original datasct into three sots: labeled set containing only normal classes to mimic distribution P, unlabeled set mixing normal and OOD classes to mimic distribution Q, and the test set. The first two are used to train the model, and the test set is to evaluate the performance.
Network Architectures. For backbone architectures, use ResNet18 (He et al. 2016) on CIFAR-10, and LeNet-type CNNs (Rull et al. 2020 on grayscale images MNIST and Mashion-MNIST. On top of the backbones, we add the head network (see Fig. 3 composed of 2 hidden layers with 500 units before the kernel approximation layer. Other hyper-parameters are discussed in Appendix A
Metrics. We present the sample class-specific accuracy, the aligned OOD recall, and the aligned efficiency (sce Appendix B for the details of alignment). Additionally, we report the AURee (area under the curve between the OOD recall and the accuracy) and AUET (area under the curve between the efficiency and accuracy) to see the overall performance of a set-valued classifier around the neighborhood of 1 -- (see the definitions in Appendix B Intuitively, the higher the OOD recall and the higher the efficiency, the better the classifier. The bold numbers in Table I denote the best performances among all set-valued classifiers.
Results. The results of two SCOD methods are reported when the rate of incorrectly rejecting normal obsorvations around y by thresholding their score functions. As shown in Table D even though they maintain the highest (100%) efficiency, the overly-confident singlo-valued classification rule fails to guaran- tee the class-specific accuracy for normal classes. Contrastively, by providing plausible labels for certain
8

---

Published in Transactions on Machine Learning Research (05/2024)
Table I: Average performance metrics on CI MNIST, and Fashion-MNIST
DeepGPS- based
SCOD
DeepGPS
GPS
BCOPS
CDL
GPS
BCOPS
CDL
SIRC
OpenMix
Bird
96.720.35
96.2+0.4
94.320.39
95.2=0.79
96.5
95.3+0.5
24
76.8
75
Cat
94.620.46
93.3 177
94.422..1
94.7=0.51
94.5200.
94.820.50
95.720.03
62.621.59
65.121.07
Deer
97.1=0.43
90.1+0.56
95.6=0.6
95.8
96, 4:0.72
94.5.0..2
26,2+0.3
80.5
75.9
CIFAR-10
Acc.
Dog
96.11.05
94.8100.3
95 25..5
1..81
95. 210.77
95.910.22
94. 61..51
69. 20.21..71
67.610 90
Frog
95.810.11
96.31.0.45
95, 6.0.44
95.4100.3
94. 710.32
96,910.20
95. 35.6.
86, 86,210.54
84.11.35
Horse
95.1+
94.2+0.83
94.8=0.44
95.440.47
95.9=0.25
95.4+0.30
95.9+0.20
84.4+0.83
84.8+0.94
Aligned OOD Recall
66.9-1.83
66.8 .33
63.7
20.3
19.820.44 44
16.5220.24
0.220.03
12.920.a e0
14.420.0 01
Aligned Efficiency
72.6+0.9
60+1.88
67=0.36
20.5=2.55
16. 16.24
25.3+0.00
10.3
100+0
100
AURec AUFIf
50.7+3.1
57.8+2.26
59.8=2.21
19.4
18.400.31
15.6+0.33
0.2
65.1+0.9
55
+1.1
19.8=2.44
16.3+0.1
23.9
9.9
Digit 1
99.7=a..
99.1 +0.53
99.52...4
99.220.07
99.620.02
99.4
99.3#0 10.12
99.2
Digit 4
99.220.18
99.31...8
99.2 09.220017
99
99.3 20
99.520-07
19.1 12
98.520 14
98.620.11 13
Acc.
Digit 6
99.1+0.04
98. 68..00
98. 78..1
98.4+0.18
99.2 2
98, 6.0.06
98.7.0.17
90.1
99.2+0.1
MSINI
Digit 7
99.1+0.18
99.4+0.11
98. 8
98. 08.8=0.2
G=0.14
98.3+0.11
98. 98.7
98.6*0.8 22
98+0.11
Digit 9
11.61...14
98. 08.91...7
98 9.....
09.110.17
08.71..1
98. 110.11
98.8110.8
97.410 52
98. 98.110.13
Aligned OOD Recall
90.4
75.8
1.59
59.2+4434
74.1
73.3
8.8.
23.8
39. 32.1+
Aligned Elficiency
99.7=2.06
96.220.47
96 20.56
85.7
8822.19
40.4
37.421.2
100
100
AURec AUEff
83.1
67 67.212.88 84
7.11
54.1144.0
66.5.22.2
17.110.s0
8.110.45
97.5=0.43
92.3+1.52
94
82.8=1.55
84+1.08
87.8+0.47
35.3+0.05
Pullover
98 98.91..05
99100.15
98 810.14
99.210.19
90.110.12
98.910.07
99.110.1
93, 6..6 24
92.210
Fashion-
Dress
98. 98.620.16
19.1
98 (8..1
98.8 98.8=0.2
18.5
98.3+0.08
99.2+0.11
94+1.1
95.3+0.35
Acc.
Coat.
19.1
99.1 50
99 1
99.4 99.42:0.6
98.5=0.55
99.310-07
96.920 13
88.520.3 35
90.520.58
Sandal
99.7=0.08
99.3++.29
99 20012
99. 00006
98.7 70.77:..44 44
08.7700.11
98.8+0.1
99, 99.2#0.00
99.4+0.1
Ankle boot
99.3+0.12
99.2++.24
98. 18.1
98, 08.99
98.9 08.9220.18
98+0.1
99.2+0.16
99.4+0..1
99.3++.07
Aligued OOD Recall
59.2
18.4.11.96
56.111.29
32.711.07
40.5.13.3
54
4.91o.25
4.4.0.52
9.31..
Aligued Efficiency
91.1
88 $8.910..51
902...2
81.3+1.18
84.5
8810.22
4310.08
10040
10040
ReRec
49.7#1.48
40.3+0.58
50.5+1
30.6=1.84
35, 35.6=33119
49.3+0.4
4.4=0.22
AUEI
86.8.0.32
83.911.81 81
86.820.39
78.211.16
80 80.81.07
65..00000
4110.41
observations, set-valued classification controls the accuracy and returns cautious decisions for those classes of interest. Without representation learning, three shallow sct-valued baselines exhibit inferior results on both OOD recall and efficiency (or their AUCs). With the learned features from DeepGPS, the OOD recall and efficiency of the DeepGPS-based baselines are significantly improved, but they are still not as good as DeepGPS overall. In contrast, besides controlling the class-specific accuracy, the proposed end-to-end DeepGPS also exhibits high OOD recall and the highest efficiency under the prescribed accuracy.
Notice that the performance of sct-valued classification is driven by the prescribed accuracy level. Intuitively, aiming for a higher prescribed accuracy tends to decrease the prediction efficiency (i.e., larger prediction sets) and lower the OOD recall. This trade-off is shown through the curves in Fig, 5 where the top row illustrates the change in OOD recall across different accuracy thresholds, and the bottom row demonstrates the corresponding changes in prediction efficiency. Both the values of AURec and AUEff in Table [ are computed based on these curves. Overall, our proposed method DeepGPS returns efficient prediction sets while maintaining competing OOD recall.
Fig. 6 Oillustrates some examples of OOD-rejected images (lŌ(=) - 0) in the first row and ambiguous images (1 < [d(x)] < K) in the second row with the predicted labels shown in the bracket. For instance, the ambignous cat (row 2, col. 3 in Fig. Gal is classified with the set {Dog, Deer, Cot, Horse} (possibly due to its upright legs and hair color), while the cat (row 1, col. 3) is rejected as an OOD point because of its rare posture. A plane from the OOD class is classified as (Bird, Frog] since the shape and the green color confuse the classifier. A car in the first row is rightfully rejected as an OOD point since its rod profile is unlike any other normal class. These set-valued decisions allow for further inspection in the presence of ambiguity to reduce the risk of misclasiifiattin.
9

---

Published in Transactions on Machine Learning Research (05/2024)
CIFAR-10
MNIST
Fashion-MNIST
1.00
Recall
0.75
0.50
0.25
0.00
1.00
0.75
Efficiency
0.50
0.25
0.00
0.9
0.925
0.95 Accuracy
0.975
1
0.98
0.985
0.99 Accurasy
0.995
1
0.98
0.985
0.99
0.995
1
Accuracy
DeepGPS
DG-GPS
DG-BCOPS
DG
BCOPS
Figure 5: Trade-off between OOD recall (and efficiency) with accuracy. Methods associated with "DG-" denote the baselines trained on the features obtained from DeepGPS.
(Bird, Frog) (Bird, Deer) [DoR, (Deer, Horse, (Dog, Cat) Horse) Dog)
(Frog, Bird) (Horre, Deer)
(Pullover,
Pullover?
(Coat,
(Coat, Pullover. Dress)
Ankle
(Sandal,
(Ankle bood, Sandal)
Pullover)
(a) Predictions on CIFAR-10
(b) Predictions on Fashion-MNNIST
Figure 6: For each panel, images in the same column come from the same class (OOD class or a certain normal class). The first row in each panel refers to OOD-rejected images; the second row refers to ambiguous images with the predicted labels shown in the bracket. Note that the ground truth class shown in red. Images in the first column in cach panel are from the OOD class.
Ablation for Kernel Approximation with Offset Penalization. As was discussed in Section the Gaus- sian Kernel Approximation in the penultimate layer al- lows us to scale the computation. In addition, now conduct an ablation study for the Kernel Approxima- tion with Offset Penalization (KAOP) technique to show its impact on the acceptance regions. By setting the number of output neurons in the backbone network to two, we can visualize the MNIST and Fashion-MNIST datasets and the closure and tightness of the acceptance regions. As shown in Fig. 7 DeepGPS with the KAOP (right panel) outputs closed and tighter acceptance re- gions than the one without KAOP (left panel). Some acceptance regions in the left panel are fairly large, pos- sibly not even closed. This means that potentially more OOD points are wrongly accepted and decisions can be ambiguous.
Dit.4
Dig
Digi7 Dit.9
7.5
-25
-25
0.7
2.5
Nouren
Acurto
000
Pulloor
Dra
Cest
Sancal
Ande Soot
Figure 7: Acceptances regions for MNIST (top) and MaSHIon-MNIST (bottom), without (left) and with (right) the KAOP technique.
10

---

Published in Transactions on Machine Learning Research (05/2024)
Fig. g exhibits the performance of DeepGPS with and without using the KAOP technique and using the weighted loss. When solely comparing Barl with Bar2 (or Bar3 with Bar4), we can see that the method without KAOP either fails to balance the trade-off between OOD recalls and efficiencies, or returns the lowest OOD recalls and efficiencies. In CIFAR-10, for example, DeepGPS without KAOP yiclds an extremely low efficiency. For this dataset, the KAOP technique significantly improves the efficiency at the cost of a slightly smaller OOD recall. For both MNIST and Fashion-MNIST, KAOP improves both the efficiency and the OOD recall in general.
CIFAR-10
MNIST
Fashion- MNIST
80
60
20
Aligned OC0
Alinnd
AURec
AUEIT
Allaned
Alggnd
ASgned Recall
GOD
Bar1: wgh
Bar2: #: wgh
Bar3: x; wgh
i; wigh q=5
Bar5: KAOP v: wgh q=10
Figure 8: Ablation studies for KAOP and weighted loss. of denotes a technique is deployed, while denotes not. q = 10 denotes the parameter value in the weighted loss.
A Ablation for Weighted Loss. Similar to the impact of KAOP, the weighted loss provides a trade-off between prediction efficiency and OOD recall for the CIFAR-10; see the comparison between Barl and Bar3 (or Bar2 and Bar4). For the MNIST and Fashion-MNIST data, both efficiency and OOD recall are improved due to the use of the weighted loss. Different values the parameter g in the weighted loss lead to a similar effect on the elficiency and OOD recall, when compared to the method without using the weighted loss (see Bar4 and Bar5 when compared to Bar2).
Overall, Fig. shows that with both KAOP and weighted loss, we tend to obtain compact acceptance regions that have high prediction efficiency and OOD recall.
Sensitivity for OOD Proportion. In addition, we include the sensitivity study (in Appendix C.3 to explore DeepGPS with varying proportions of OOD data in the target distribution Q. The efficiency remains relatively stable across different OOD proportions all three datasets.
6 Conclusion
Conventional single-valued predictions make decisions without guaranteed confidence for interested classes. Moreover, current set-valued classification methods have sub-optimal performances on large and complex datasets. To address these limitations, we propose an end-to-end DeepGPS method. Empirically, besides detecting OOD points, DeepGPS provides reliable control over class-specific accuracy for normal classes, offering cautious yet informative decisions to mitigate risks. Theoretically, we show that DeepGPS minimizes the prediction set size under the prescribed accuracy. These support the effectiveness of DecpGPS in scenarios where misclassification may have severe consequences, and hence highly accurate predictions desired.
The DeepGPS network provides scalable set-valued classification with OOD detection. The kernel approxi- mation allows Deep Neural Networks to tap into the good lcarning property of the kernels. This, along with the ofiset penalization, facilitates the const ruction of closed acceptance regions. The usage of weighted loss further renders more compact acceptance regions. As per the resulting predictions, DeepGPS differentiates between OOD-rejected observations (i.e., 1ō(x) = 0), which were not considered in the CRO method, from difficult. observations (i.e., 2 < 1ő(=)) < K). This distinction has not been well-explicitly explored in the OOD detection and SCOD literature.
While the current implementation learns shared o value in Random Fourier Features, it important note that this approach may overlook the heterogeneity among different classes, potentially resulting in larger
11

---

Published in Transactions on Machine Learning Research (05/2024)
acceptance regions for certain classes and hence degrading the performance. Future work could involve the design of a new architecture that enables the learning of class-specific values. Additionally, our proposed method leverages unlabeled datasets. Expanding the framework to operate in an online learning mode, allowing for incremental updates with limited data availability, presents an intriguing avenue for future exploration. Lastly, proposing method that even controls the OOD recall with a theoretical guaranlee would be another intriguing topic. However, to our best knowledge, this further relies on the assumption of the OOD data (Liu al. 2018 Pang et al. 2021), which might be challenging in practice.
References
Peter Bartlett and Marten Wegkamp. Classification with a rejoct option using a hinge loss. Journal of Machine Learning Research, (1ug) 18400, 2008.
Peter L. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normallle margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Abhijit Bendale and Terrance Boult. Towards open world recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1893-1902, 2015.
Abhijit Bendale and Terrance E Boult. Towards open set deep networks. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 1563 1572, 2016.
Jun Cen, Di Luan, Shiwei Zhang, Yixuan Pei, Yingya Zhang, Deli Zhao, Shaojie Shen, and Qifeng Chen. The devil is in the crongly-chnsified samples: Towards unified open-set recognition. In The Eleventh International Conference on Learning Represenlations, 2023. URL httpttt://opeeereiies wwwpeeewwiwieeeeeeeeeeeeeeeeeeee net/forummid
XLrOI_XYGAS XYGAS
Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classification with re- joction based on cost-sensitive classification. In International Conference on Machine Learning, pp. 1507- 1517. PMLR, 2021.
Christophe Denis and Mohamed Hebiri. Confidencce sets with expected sizes for multiclass classification. The Journal of Machine Learning Research, 18(1):3571-3598 2017.
Christophe Denis and Mohamed Hebiri. Consistency of plug-in confidence sets for classification in semi- supervised learning. Journal of Nonparametric Statistics, 32(1):42-77 72, 2020.
Xuefeng Du, Zhaoning Wang, Mu Cai, and Sharon Li. Towards mknown--ware learning with virtual outlier
synthesis. In International Conference on Learning Representations, 2022. URL https://openreviee. pet/foorum2dddTW776666
Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In Internalional conference on machine learning, pp. 1386 1394. PMLR, 2015.
Ran El-Yaniv et al. On the foundations of noisc-free selective classification. Journal of Machine Learning Research, 11 15),, 2010.
Zhen Fang, Jie Lu, Anjin Liu, Feng Liu, and Guangquan Zhang. Learning bounds for open-set learning. In International conference on machine learning, pp. 3122 3132. PMLR, 2021.
Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf. Kernel measures of conditional dependence. Advances in neural information processing systems, 20, 2007.
Saurabh Garg, Sivaraman Balakrishnan, and Zachary Lipton. Domain adaptation under open set label shift. Advances in Neural Information Processing Systems, 35:22531 22546, 2022.
Saurabh Garg, Nick Erickson, James Sharpnack, Alex Smola, Sivaraman Balakrishnan, and Zachary Chase Lipton. Rlsbench: Domain adaptation under relaxed label shift. In International Conference on Machine Learning, pp. 10999- PMLR, 2023.
12

---

Published in Transactions on Machine Learning Research (05/2024)
Yonatan Geifman and Ran El-Yaniv. Selective classification for deep neural networks. Advonces in neural information processing systems, 30, 2017.
Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. In International conference on machine learning. pp. 2839 2848. PMLR, 2016.
Federica Granese, Marco Romanelli, Daniele Gorla, Catuscia Palamidessi, and Pablo Piantanida. Doctor: A simple method for detecting misclassification errors. Advonces in Newral Information Processing Systems, 34:5669-5681, 2021.
Leying Guan and Robert Tibshirani. Prediction and outlier detection in classification problems. Journal of the Royal Statistical Society. Series B, Statistical Methodology, 84(2))524, 2022.
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, pp. 770-778, 2016.
Yolam Hechtlinger, Barnabés Póczas, and Larry Wasserman. Cautious deep learning. ar preprinl arXiv:1805.09// 2018.
Dan Hendryeks, Mantas Mazeika, and Thomas Dietterich. Deep anomaly detection with outlier exposure. In International Conference Learning Representations, 2019. URL httpps://openrevier http://ppeneviieeeeeetfrrrrrrr net/forum?
HyxxCcRhy
Radu Herbei and Marten H Wegkamp. Classification with reject option. The Canadian Journal of Statis- Lis/LLa Revue Conadienne de Slatistique, pp. 709 721, 2006.
Vilen Jumute and Johan AK Suykens. Multi-class supervised novelty detection. IEEE transactions on pollern analysis and machine intelligence, 36(12):2510 2523, 2014.
Julian Katz-Samued Julia B Nakhleh, Robert Nowak, and Yixuan Li. Training ood detectors in their natural habitats. International Conference on Machine Learning, pp- 10848-10865. PMTR, 2022.
Jibyo Kim, Jiin Koo, and Sangheum Hwang. A unified benchmark for the unknown detection capability of deep neural networks. Expert Systems with Applications, 229:120461, 2023.
George Kimeldorf and Grace Wahba. Some results on tchebycheffan spline functions. Journal of mathemat- ical analysis and applications, (3(1):82-00 95, 1971.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. a4 6980, 2014.
arXio preprint
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. International Conference on Machine Learning, pp. 1468-5479) PMLR, 2020.
Jing Lei. Classification with confidence. Biometrika, 101(4):755 769, 2014.
Jing Lei, James Robins, and Larry Wasserman. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):278 287, 2013.
Jing Lei, Alessandro Rinaldo, and Larry Wasserman. A conformal prediction approach to explore functional data. Annals of Mathematics and Artificial Intelligence, 74(1):29 43, 2015.
Percy Liang. Cs229t/stat231 Statistical learning theory (winter 2016), 2016.
Zhen Lin, Lucas Glass, M Brandon Westover, Cao Xiao, and Jimeng Sun. Scrib: set-classifier with class- specific risk bounds for blackbox models. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 7497-7505, 2022.
Si Liu, Rishoek Garrepalli, Thomas Dietterich, Alan Fern, and Dan Hendrycks. Open category detection with pac guarantees. In International Conference on Machine Learning, pp- 3169 3178. PMLR, 2018.
13

---

Published in Transactions on Machine Learning Research (05/2024)
Jing Lu, Steven CH Hoi, Jialei Wang, Peilin Zhao, and Zhi- Zhi-Yong Liu. Large scale online kernel learning. Journal of Machine Learning Research, 17(47):1, 2016.
Tengyu Ma. Lecture notes for machine learning
blob/mainn/aster.ppon 2022. Accessed: 2022 06-22.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Poundations of machine learning. MIT press, 2018.
Minh-Nghia Nguyen and Ngo Anh Vien. Scalable and interpretable one-class svms with deep learning and random fourier features. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 157 172. Springer, 2018.
Junhyung Park and Krikamol Muandet. Towards empirical process theory for vector-valued functions: Metric entropy of smooth function classes. In International Conference Algorithmic Learning Theory, pp. 1216 1266..2202222222100 PMLR, 2023.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017.
Lukas Ruff, Robert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexander Binder, Emnanuel Müller, and Marius Kloft. Deep one-class classification. In International conference machine learning, pp. 1393-4402. PMLR, 2018.
Lukas Ruff, Robert A. Vandermeulen, Nico Görnitz, Alexander Binder, Emmanuel Müller, Klaus-Rober Müller, and Marius Kloft. Deep scmi-supervised anomaly detection. In International Conference on Learning Represenlations, 2020.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223 234, 2019.
Bernhard Schölkopf, Robert C Williamson, Alex Smola, John Shawe- Shawe-Taylor, and John Platt. Support vector method for novelty detection. In Advances neural information processing systems, pp. 582-588,
2000.
Alistair Shilton, Sutharshan Rajasegarar, and Marimuthu Palaniswami. Multiclass anomaly detector: the 08+ support vector machine. J. Mach. Learn. Res., 21:213-1, 1, 2020.
Bernard W Silverman. Density estimation for statistics and data analysis. Routledge, 2018
Bharath K Sriperumbudur Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kernels and rkhs embedding of measures. Journal of Machine Learning Research, 12( 2011.
Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, and Geoffrey J Gordon. Domain adaptation with conditional distribution matching and generalized label shift. Advonces in Neural Information Processing Systems, 33:19276-19289, 2020.
David MJ Tax and Robert PW Duin. Support vector data description. Machine learning, 54(1):45 66, 2004.
Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Open-set recognition: good closed-set classifier is all you need? In International Conference Learning Representations, 2022.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer Science Business Media, 2005.
Wenbo Wang and Xingye Qiao. Learning confidence sets using support vector machines. Advances Neural Information. Processing Systems, 31, 2018.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Wenbo Wang and Xingye Qiao. Set-valued support vector machine with bounded error rates. Journal of the American Stalistical Associalion, pp. 1-13, 2022.
Zhou Wang and Xingye Qiao. Set-valued classification with out-of- detection for many classes.
Journal of Machine Learning Research, 24(375):1-39, 2023. URL htttp://jnlr..rr//ppgn wwtpr/rrrpppppp//////...
23-0712.htm
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton. Domain adaptation with asymmetrically- relaxed distribution alignment. In International conference on machine learning. pp. 6872-6881. PMLR, 2019.
Guoxuan Xia and Christos-Savvas Bouganis. Augmenting softmax information for selective classification with outtr--distinbttion data. In Proceedings of the Asian Conference on Computer Vision, pp. 1995- 2012, 2022.
Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey. Xix preprint orXiv:2110. 1334, 2021.
Chong Zhang, Wenbo Wang, and Xingye Qiao. On reject and refine options in multicategory classification. Journal of the American Statistical Associalion, 113(522):730 745, 2018.
Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International conference on machine learning, pp. 819 119-827.2 PMLR, 2013.
Min-Ling Zhang and Zhi-Hua Zhou. MI-knn: A lazy learning approach to multi-label learning. Pallern recognition, 20(7) 2048, 2007.
Fei Zhu, Zhen Cheng, Xu-Yao Zhang, and Cheng-Lin Lin Liu. Openmix: Exploring outlier samples for mis- classification detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12074 12083, 2023.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Appendix
A Details of Experiments
All doep methods consistently use the same backbone and head network with the same dimension of weight matrices in each layer. Experiments run over 150 epochs with batch size 512. The ResNet18 (He et al. 2016) architecture is the same the one in PyTorch and LeNet-type CNNs are identical to Ruff al. 22020) The training set (labeled set and unlabeled set mentioned in Section 5 is further split with ratio 9:1 into training data for learning f and validation data for tuning parameters. The average and standard errors of performances are reported after 5 runs.
DeepGPS. We use the Adam optimizer (Kingua & Ba 2014 with learning rate = 10 and (31, (2)
(0.999, 0.999). Additionally, we the weight decay in Adam as 10 and set X 0, l [4] in the objective function Eq. to implicitly regularize weight matrices instead of explicitly imposing a penalty on the first term in J(f). In contrast, the parameter X = 1, E [K], same as in OCSVM (Schölkopf et al. 2000), is to explicitly penalize the offset term in Jff). The tuning parameter C' is determined such that the prediction set is smallest on the unlabeled part in the validation data when the misclassification rate is close to on the labeled part in the validation data.
For the below set-valued baselines (or DeepGPS-based variants), we conduct the split-conformal (Vovk et al. 2005 Lei et al., 2015) and scarch for the optimal tuning parameters on the validation data (Lei 2014). In particular, let fx be the score function returned by a baseline and fĄ be a y 100% quantile of {fk (x,))) where Gzal denotes the index set of the observations from class k in the validation data. Then the optimal parameter is chosen when the prediction set size Ejegrat Σ 1 (ff)(zz))) 2 fx) is minimizod on the unlabeled points in the validation data, where Guel denotes the index set of unlabeled observations in the validation data.
GPS. We search the value of penalty in the GPS method from the grid {0.1, 1, 10), and use the median of pairwise Euclidean distance among observations as the bandwidth in its Gaussian kernel.
BCOPS. The maximum depth of the tree is scarched from {10, 30, 50]. Minimum samples to split an internal node, minimum samples at a leaf node, and the number of trees are searched from (5, 10), (4, 6). and (50, 100}, respectively.
CDL. We search the value of bandwidth in an even grid with length 5, starting from 0(1)
4 1/(+4)
(p+2)
to (p) x ((p42m) based on Silverman's rule-of-thumb bandwidth estimator Silverman, 2018 where is the sample size, p is the dimension of the feature and d(1) and dip) are the minimum and maximum standard deviations across all dimension of features.
SIRC. By following Xia & Bouganis (2022). we use the score function consisting of maximum softmax probability and the 4 norm of the embedding in the penultimate layer, where the former to separate easy normal observations from both difficult normal observations and OOD observations while the latter is to distinguish normal observations from OOD observations.
MpenMix. This method requires OOD exposure data, where we use the Gaussian noise as mentioned in Zhu al. 2023 In this method, the score function is the max logits returned from the output layer.
B Evaluation Metrics for Set-valued Classification
Note that the prediction performance is driven by the user-defined class-specific accuracy 1 1-7. y. There exists trade-off among accuracy, OOD detection performance, and efficiency. Intuitively, a higher prescribed accuracy leads to lower OOD detection performance and efficiency.
16

---

Published in Transactions on Machine Learning Research (05/2024)
In our evaluation, report several key metrics for assessing the performance from different perspectives. Let Gte be the index set of the test set. We report the sample class-specific accuracy
Ejegr 1(Y, = k and Y E ((x))} 100%, [K] Ejeg.. 1[Y, = k}
to measure the accuracy of class predictions for normal classes; the aligned OOD recall
Rec(1 - -7) == Ejeg. 1(,, OOD and [x(x,)| = = 100% Ejer.. 1 1(Y, = OOD}
to evaluate the ability to correctly identify OOD samples; and the aligned efficiency
Ejeo. 1(2 # OOD} 10(x)) 1 K-1 Ejer. 1(y, # OOD)
EM - 7)
x 100%
to show how the classifier distinguishes between normal observations. The first term in F++ in Eff(1 - 7) denotes the average prediction set size on the normal observations, ranging from 0 K.
The above two aligned metrics obtained by adjusting the thresholds in such way that set-valued classifier exactly achieves the sample accuracy to be the prescribed value 1 for each class, regardless of the goodness of the original sample class-specific accuracy. This strategy helps us to conduct a relatively fair comparison for set-valued classifiers since sample OOD recall and sample efficiency are affected by the sample class-specific accuracy.
In SIRC and OpenMix methods, to obtain the aligned OOD recall, we set the threshold for the score functions such that the rate of incorrectly rejecting normal observations is y. This strategy results in both single- valued and sct-valued rules exhibiting a similar overall error rate of rejecting normal obscrvations, mitigating potential disparilies in our comparison. Notably, the single-valued prediction has 100% elficiency.
To see the overall performances, one may consider two new metrics, namely, AURec (area under the curve between OOD recall and accuracy) and AUEff (area under the curve between efficiency and accuracy). These two metrics are defined near the neighborhood of the prescribed accuracy - 7, Le., from - 2y to 1:
1 J. 27 J1-27
1 Rec(t)dt, and AUEff
AURec
Eff(t)dt.
2n J1
It important to note that these overall performance metrics (even though defined near the neighborhood of 1 11))) have limitations as they overlook the specific accuracy value the user prescribed. Additionally, both AURec and AUEff are calculated when all normal classes attain every accuracy value within the integral region, which alludes that these two metrics are not applicable for single-valued classification, leaving them blank for both STRC and OpenMix methods in our reports.
C Extra Experiments
C.1 Set-valued Classification on CIFAR-100
We train the set-valued classification with ResNet50 backbone the CIFAR-100 dataset with 20 coarser class labels. Here 10 normal classes consist of {aquatic mammals, flowers, fruit and vegetables, natural ouldoor scenes, omnivores and herbivores, medium-sized manmals, invertebrales, repliles, small mammals, trees}. while the remaining 10 classes form as the OOD class. Table shows that almost all the methods can control the prescribed accuracy on all normal classes. With the representation lcarning, DeepGPS, DeepGPS-based GPS, BCOPS, and CDL outperform the vanilla GPS, BCOPS, and GPS. Additionally, the proposed DeepGPS has better trade-off bet OOD recall and efficiency.
17

---

Published in Transactions on Machine Learning Research (05/2024)
Table 2: Average performance metrics for CIFAR-100 (1 = 0.05)
DeepGPS- based
CIFAR-100
DeepGPS
GPS
BCOPS
CDL
GPS
BCOPS
CDL
aquatic manmals
9840.51
96.610.3
94.411.14
95.240.8
96.920.42
94.3+0.61
95.6+0.75
flowers
9740.73
95.3#1.09
94.71:0.64
94.5=0.85
95.8+0.05
96,4+0.83
93.1
fruit and vegetables
9740.54
91.8=1.06
95.4+00.44
95.1 =0.1
95.3220.54
95.4=0.33
94.6+00044
natural outdoor scenes
96.9
94.2
94.4+1004
94.6=0.66
94. 10.54
95. 05.8
95.8+0.22
omnivores and herbivores
96.7+0044
96:40.39
91.8==0.8
96++0.69
94.8
95.8
95
Acc.
medium-sized mammals
96. 06.64
96410.22
95.6+:0.26
96.5=0.54
1.1
95.5+0068
96.1
invertebrates reptiles small mammals
94.5#1
95.8=1.75
95.17
95.8=1.12
96.5220.67
95.4+0.28
94.620.6
95. 0512
96. 10.67
95.1+00.88
94.6=0.59
35.320.53
94.3+0.48
93.20.69
9520.66
94.7=20.7
95.7:10.64
95.9=0.52
91.821 .62
9420.64
94.00.58
trees
96.6#1.11
93111.66
94.2+1.12
95.620.82
95.4
94.4+0.67
Aligned OOD Recall
43.9
1.8#0.95
8.8
6.3
0#0.003
0.1#0.01
040.01
Aligned Efficiency
47.4+3.64
53.9 1349
62.6=0078
29.7=1.96
33. 7
35. 35.1+0.31
11.5+0.26
AUODR AUE
38.410096
3.440.90
8.5+1.00
6.640.9
2.1
0. 0.1
040.01
4142.44
18.8
56.9=0.85
2941.32
3240.16
33. 20.25
11.1
C.2 class-specific Accuracy Control in Ablation Studies
Fig. g exhibits the accuracy control in the ablation studies on three datasets, where the height of each bar represents the average sample accuracy and the black vertical segment on the top of each bar denotes the standard error. Additionally, red dashed horizontal lines denote the prescribed accuracy level of 1 7- In this figure, we can see that the DeepGPSS method effectively controls the class-specific accuracy across various techniques employed in the ablation studies. The metrics of prediction efficiency and OOD detection
performances are displayed in Fig. g
CIFAR-10
MNIST
Fashion-MNIST
0.8
0.6
0.4
Bmd
Cil
Deer
Drg
Fre
floee
3gt
Dots
Pulover
Dree:
Coet
Sancal
Ancle bost
Barl:
x;; wgh
Bar2:
KAOP
wih
with
wiwgh
q=10
Figure Accuracy control in ablation studies for KAOP and weighted loss. / denotes technique is deployed, while denotes not. q q= or 10 denotes the parameter value in the weighted loss.
C.3 Sensitivity for OOD Proportion
The results presented in Table 1 are based on OOD proportions of 4/10, 5/10, and 5/10 for CIFAR-10, MNIST, and Fashion-MNIST, respectively (due the number of sub-classes chosen for the OOD class). In
Table Sensitivity study for varied OOD proportions on CIFAR-10 (7 0.05)
Acc.
Aligned OOD Recall
Aligned Efficiency
AURec
AUEff
Bird
Cat
Deer
Dog
Frog
Horse
0.2
95. 95..0.559
95 540.34
96. 820.6
96. 96.5-
9720.38
95.3+1.5 21
15.842.15 15
71.940.7
14.8+2.01
66. 06.7740.6
0.3
9:441.24
94.4+0.75
95.9=1.01
96. 140.74
96-10.66
94.7++ 1.20
33.8+11.71
72.441.33
32.2+10.16
64.6+11 1.2-
0.8
96440.7
95.3+
96.8=0088
96=0.57
96.5+00.3
95.71-.66
70.745..8
70.3+1.13
66:14.7
62.840.74
0.9
96.5++0.09
94.3+1.26
97.40.73
95.7440.8
96.740.09
96-10.81
73.6+4..5
69.3441.84
70.442.16
62:+1
18

---

Published in Transactions on Machine Learning Research (05/2024)
this section, we include the sensitivity study to explore the performance of DeepGPS under another four different values, ie., 0.2, 0.3, 0.8, and 0.9, of OOD proportion in three different datasets. As shown in Tables 3 to the class-specific accuracies are well-controlled. 'he metrics of the efficiency, remain relatively stable across different OOD proportions in all three datascts. When it comes to the OOD detection performance, in general, the higher OOD proportion helps to improve the OOD detection performance.
Table 4: Sensitivity study for varied OOD proportions on MNIST (7 = 0.01)
Acc.
Aligned OOD Recall
Aligned Efficiency
AURec
AUEff
Digit
Digit 4
Digit 6
Digit
Digit 9
0.2
99.9=0.02
99.41:009
19.311..3
99.2=0.16
99.210.11
2.2
99.820.06
60.1+:2.92
97.6=0.31
0.3
09.9
99.4=0.1
19.3+.0.1
99.14002
98.9400.9
80.4+1.5
99.7+
70.2+2.07
97.2=0.26
0.8
09.75
99. 99.440007
99.1+0.08
99.1=0.22
98. 840.14
19.4
99.5+0.12
82.4+1.65
97.2=0.32
0.9
99.7=0.04
99.440.01
99+0.1
99.3=0.16
98.7+0.1
88,5+1882
99.5=0.12
81.1+22.7
97+0.46
Table Sensitivity study for varied OOD proportions on Fashion-MNIST (7 0.01)
Acc.
Aligned OOD Recall
Aligned Efficiency
AURec
AUF
Pullover
Dress
Coat
Sandal
Ankle boot
0.2
10.09
10.15
99.3
99.7:10.0
99.120.12
19.3
92. 92.41:..7
17.7+1.2
87.510.27
0.3
9910.115
98.8
90:0.2
99.110005
99.410.11
33.11:.52
91.410.1
30:3.5
86.610.63
0.8
99.1+0.04
08.620.19
99.5#t.11
99.6:t0.99
99.4+0.09
59.5+1.86
91.340.16
46.6+1
85.3+0.77
0.9
99+0.04
98.7=0.19
99.640.11
09.6+0.1
99.5+20.5
57.1+2.26
90.9=0.2
47.3+11.27
86.5+0444
C.4
Alternative Loss Functions
In this section, we test. the performance of DeepGPS on the CIFAR-10 with different surrogate losses, i.e., exponential and logistic loss functions. Table shows that the alternative two loss functions significantly sacrifice the prediction efficiency. This is mainly due both logistic log(1 exp(-u)) and exponential loss exp(-u) having non-zcro loss value when 0, which forces the prediction sets include more labels such that the empirical loss values are below than the error bound 7 average. In contrast, the hinge loss used in Table D returns smaller prediction sets without sacrificing too much OOD recall.
Furthermore, we onco considered the sigmoid function 1+exp(u) as a candidate loss function which is closer to 0-1 loss than the hinge loss; however, the gradient vanishing with u away from hinders the training progress.
Table 6: Average performance on CIFAR-10 (7 0.05) under alternative loss functions
Loss
Arc.
Aligned OOD Recall
Aligned Efficiency
AUODR
AUEÆ
Functions
Bird
Cat
Deer
Dog
Frog
Hoose
logistic
7...6
97. 720.8
08.52.058
96.310.73
98 1S..640.11
210.3.
83. 110.28
31.11637
71.74312
33.746.11
exponential
07.3.1..8
97. 07.94
99:0.45
99.110:21
99.110:22
410.4
84.8
36.215.
70.71223
35.9142
hinge (in Table
96. 06.753..3
94.6=0.46
97.1=0.43
96.1+0.5
95.8+0.11
96.1+
66.9+1.83
72.6+09
56.743.1
65.1
19

---

Published in Transactions on Machine Learning Research (05/2024)
D Proof of Theorems
For matrix W. E IR m in 1-th layer, 1 E [L], if We I Kj, thus we have |Will & Kt and | 12,1 & Vmiki == b, where || 1-1 is the operator norm and || |2,1 is the sum of Euclidean norms of the matrix
columns.
To prove Theorem I we nced the notion of Rademacher complexity to mcasure the richness of hypothesis class. Following this, we show the Rademacher complexity of a particular hypothesis class with Lemma 1 which will be used in the subsequent proofs.
Definition 1. Let 9 be class of real-nalued functions g = X R. The Rademacher complexity Rg) and the empirical Rademacher complexiit Rm(g) of the hypothesis class 9 are respeclively defined as
RR == sup DEG nI
1 Σ )
RG) = sup DEG nI [gg(2;,) {a
Σ
where Jj..j = I,..., n are Rademacher random veriables which independently and uniformly take values from {-1,+1}, and æū =..jj=........ I,..., are sample poinls.
Remark 2. In Defonition [ the first expectation is laken with respect to both Rademacher random variables and sample points, while the second expectation is only taken with respect to Rademacher random variables by conditioning on sample points. Given this, we have R. (g) = (G)].
Lemma 1. (iang 2016) Let 8; IRP and assume EE] @111 S ch holds for alli= L,... n. The Rademacher complerity of the inner product operation with constrained Eg norm on a dataset with sample size is
Caba
Rn (H + ++=2 B 118112 S bg. E S
Vn
Proof.
R, (w + a
TTB:
B: 11 I b3. B E R.)
E
sup
B
E
B Sla
sup
o
8:1||||aa
Shg i=1
71
i=1
b,
E
+ l2
Cauchy-Schward inequality
bg
n
by E
n Σ
o o
is concave
1=1
i=1
bg
bg Ca
E
|
The main idea in the proof of Theorem to treat sampled the Gaussian frequencies E E Rm- 1...., D as 'data points", and find the Rademacher complexity of certain mapping applied on these E
Proof of Theorem
Inequality
(5) can be obtained by using the Hoeffding's 's inequality. To show
let
Ag = Zz: - Ræ; and
00 Σ
Zwz 12
exx KD sup ((z,;i0) ()= exp
A=
0 ? 2
Σ
cos (oE] A2) exp
= sup A
D
j=1
20

---

Published in Transactions on Machine Learning Research (05/2024)
By McDiarmid's inequality (the bounded difference is }), with the probability least 1 - 8, have
KD v E[Ko]+ + V
2
2
2
log 2 2n + cos( " *==))) +
log
(9)
D
8
2
2
< 2 RD(EE + of Ax)) +
log
(10)
D
5
| 2co II
1.-2
2
2
2/mc-2
log
(11)
VD
D
8
where D| & 2- PDD(E + cos(ot A+))) in 19 holds due to Ma 2022
Theorem 4.13); 10) holds by
using Talagrand's lemma (Mohri et al. 2018 and the fact that cos(.) is 1-Liischitz function. As for 11 it is true since
mL- |o||
sup 11
RD(EE + ot AxH) S
because of Lemma D and &, ~ ~N Ime-2)
VD
/L-2 |ar|
1--2
k()
|| x,l12
(12)
VD
1=1
mL 22 |o|
-20
2cp
L-2
K1
VD
1=1
holds because 2,, æj are outputs from the neural network up to (L 2)-th layer, which is also a Lipschitz mapping (with Lipschitz constant 11 ky) evaluated 3i æz. The last inequality holds due to the assumption of || I mentioned in Section
where 12
To derive Thcorems 2 and we need the notion of the covering number with metric entropy, which is another approach to show the capacity of a hypothesis class. The covering nunber and the (empirical) Rademacher complexity can bridged by Dudley's Theorem. Additionally, we introduce Lemmas and 3 that are critical to deriving our thcorems.
Definition The covering number of hypothesis class F with respect to metric p Fx R is defined the smallest number of balls with radius covering F, i.e.
= :3 U1. . CFCCFCULE CFCUUMBBUU)))))
where the ball with center fi and radius under the metric is defined as Ba(li, = =I p(Si, s se.. Additionally, the metric entropy is defined as the logarithm of the covering number, i.e., log No (,,
Remark 3. In particular, throughout this article, the distance between two functions fi and f under the metric p = L (T) defined as
p(i, -2 (Jr,)) / [I. -1gdP,
[[(());)) (a
where æzj.j = I,...,m are sample points. Here Se()) and f(.)
could be a vector oulpul.
Lemma 2. Bartlett et al. | 2 S C-1, n.. n. The metric entropy
2017 Ma. 2022) Let Hi, {= + Wz W e mmx W 12.1 S bi} and
17 E7
log (et, Hi, (2(P))) <
In (2mp)).
Remark 4. Slightly different from Bartlett et al. b7
2017) Ma
2022 for notation simplicity, we do not apply
ceiling operation on ot in Lemma This is not big deal because we can remove the ceiling operation by adjusting the value of to oblain The ceiling integer.
21

---

Published in Transactions on Machine Learning Research (05/2024)
of In(2mppi) with by mmiki as of
Remark 5. Lemma can immediately yield log.N (Et, Ha Le((P)) - defined at very beginnang.
Lemma 3. Ma (202)) Assume the inpul z1-1 in 1-th layer of the network archileclure FI, salis- fies |||-1||2 Ct-1- If the metric entropy of the hypothesis class in 1-th layer has an upper bound log.V (EL, Him (P())) g(E1,01-),, where is the radius of covering balls for Hi,m there exists covering of FL.x such that the metric entropy
1. log (E, (P,)) S Σ g(E,, 9-1)
Theorem 4. Let := == I For any Lipschitz mapping v IR + R with Lipschitz constant Gè, under the Rademacher complerity of the hypothesis class uo FL. on the dalasel with
the assumplions in Lemma sample size n is
12 co log(rr/n) o FL,R) S
4 +
(mi In (n(2mpp))
Vn
Proof. By using Remark 5 and Lemma
we have
6ic
log FL.m
Σ 1=1
ln(2mppr).
(13)
of
Our goal now is to bound the metric entropy log (e, FL.n. (P.))) directly involved with instead of
in
13
As shown in the proof of Lemma in Ma 2022), there exists a covering for FL. with radius Ky-- Kz- Then, through the Holder's inequality, have
-= Ei 15=1+1*5
I.
b14-1 /n(2mpp))
b in (2mppp))
II
Ki
11
Ki
E1
j=1+1
cf
<
In 1n(2mpp:)
13
Kj
c7
j=l+1
L
L
3
L
bic-iV (2mpp))
II
Kj
<
ln(2mppt)
In
-=++1
1=1
and equality can be achieved when we choose
-3/2
1/2
t ((b//11) 2/2 (1n (1mm2)))))244
bt
L
by
Σ
/ An /2n(pmmp))
1 Ki
Hence, the upper bound in
13 can be re-expressed as
O7 In 1n(2mppi)
813
big /In(2mpp))
II j=1+1
15
E?
E2
333
bic 1n(2mpp))
Kig
_2
C0
In (2m.pt)
1=1
1=1
22

---

Published in Transactions on Machine Learning Research (05/2024)
where the last equality holds due co
IT-= Ki (composition of Lipschitz continuous functions) and
bi Vmiki. Thereby Eq. 13 concludes
3
FL,
Σ (m In (n(2ma)))
62
Together with the Lipschitz transformation property in the covering number (Park & Muandet, 2023 i.e., M(e, vh o F2.x,L((P,) & N(E//v. FL.k: L2(P,),, the above further indicates
log Nog,Wee FL,M, L2 (Pn)) S
Σ mm In (2mppi)))
According the Localized Dudley's Theorem
Ma
2022). we have
Rm (1b FL,x)) S 4a + 12 [
log (e, tb o FL,K: L2 de
4
12cp r loggrr/))
(m, (2mppi)))
n
vn
by choosing a -.. Therefore,
Rn (1) =
=B
BB Rn
Fim)) Frx)) S
4
12c -r rlogg(r
(ml In (2mapp))) Σ
Vn
Vn
Proof of Theorem 2 Define Gug.
sup fe (,,())
(Il2) Y
k]
Σ (fa()(() By the
me
=
McDiarmid's inequality (the bounded difference
2r), with probability at least A we have
my
1
2K
2
2K log
G.. S B| + 2 2n 5
log
2 Ryg (l2, o nh o (7,1)) + +rv
(14)
nk 8
where Ty donotes the k-th coordinate projection.
Note that both loss function E, and projection operator me are 1-Lipschitz mappings, and Rn (la, T o Fi. v)) C Rag (B2,y Th o F Fi:(()))) because of Fi, C FL.R- Thereby, by applying Talagrand's
lemma 14 leads to
E (fa))) -
1
Σ
(e + Rn, (TROFL,M) + rV log 8
2 2K 7kk
Tik
Bi k
(15)
1
l (f + (8),
nkk
W:
where
12r log(r Tik) /Tk)
Rig FL.))
+
Σ (m In (n(2)p))))
(16)
/ /Tk
Vrkk
by applying Theorem
Proof of Thcorem We skip the proof of Statement (1) since it can be immediately derived from Eq. 150 with the hypothesis class Fi v²) Now let's work on the proof of Statement (2),
23

---

Published in Transactions on Machine Learning Research (05/2024)
which will be divided into 2 parts. We define f.f Fi. v v-,)) - 1 Ex=1 & (f,()))) and R Ex (fx)), respectively. WLOG, we assume the loss function & has the Lipschitz constant c. Note that the operation Σ (1(((())) here can be viewed as 1 o o f(;)), where is the vector with all K entries taking the value 1; & is element-wisely applied on f and the composite mapping 1 o & has Lipschitz constant v Vee due to the fact that v/2 (Z1, , and 2 = (ă ,,x),
be the minimizer of Re (f)
|1 o (1)) - (2)(22)222 & | [[((()) - (1)l222
K
= -VK-
(bi(z))
(((E))) (((x)))((EE)) VKe
Zk kx)² VKe. 0|= -
i) This part is to bound Rr, (f)
min
Re, (f), where E [0, - 20"
Let's first prove the statement: with probability at least 1 - 8,
Fī - 5- 5-20" -20", C Fi, -M -
(17)
Proof. On the one hand, for any f E FL. - - - -200 1), we have
(()(() <0 0 Y k) (7 - 1-20-000 S (fa(() Y k] < v
+ P(f < 0 Y =k) =-) -020.
On the other hand, for any f E Fi - v 0r, v), similar to the prove of Eq. 15 with low probability at most 8, we have
1[ Y -As 1
Σ
(--
Inx (6)
4kk wi=k
Sv 0n, (8)
<0 - S nnd (8)
= P()x(X) <0 k)s ~ 0" 1 On) (8),
thus with probability at least 1 8, we have
(()((X) <0 Y = k) > - 8" - 0n, (0) 2 20" <0 = =k)) k),
which implies FL - 20"00) c ft - V,,).. v).
Therefore, with probability 1 5, the following inequality holds
R₁, (f)
min
Re, (f) = (f) - R. + Rr, (f) - -RA(
+ Ro, (f) R2 (f)
(18)
+ (f)
min
Rr, (1)
(19)
(1----0 .))
< 2 sup feFL..
RR (f) - -Re,
(20)
because Eq. (18 is non-positive (f is an empirical minimizer), and Eq. 19
is non-positive with probability
1-6 8 due to the fact of Fq. (17 and f is minimizer in F 0- v))
24

---

Published in Transactions on Machine Learning Research (05/2024)
Let FL.m = ( Ek (ffx(a)): of (fi. fx) FL,x) be space in which Lipschitz continuous
function (the Lipschitz constant is vKc) is applied on the function vector f E FL,x- Thus, by applying Theorem we have
Ri ( L.m..
4 Vn
K2 :lo(rr/))
Σ (mi In (n(2mpp:))
(21)
vn
where c when we particularly work with the hinge loss.
Following the similar proof for Eq. 144 (now the bounded difference is 2 Kee/Ke/ng /n), with probability - 8 we have
sup R2 (1) - Rs, (f) S 29%, (Fi 22/Kery
log
2
(22)
JEFL.
2n
and hence with probability at least 1 28, 20 and 22 yields
1
R4 (f)
min
Rei (f) I 49, 49, (F Ker
log
(23)
fEt ( 0-200,00
2n
8
it) This part is to bound
min
Re (f)
min
Re (f).
SEFt 15-6-200 20"
(T-00)
Let fin
argmin
Re, (f) and fout
argmin
Re, (f). Note that frn f E FL.x Thus
SEFT (0-0
fEF (--
min
(f)
min
Re (f)
fEF (E-1,
(f -Re, (poul)
(24)
= RR, (ei - -Re, (fin) + Re, (foul) - -Re, -Re,(foul) + Re, (fin) - Re, (fout)
2 2 sup |Re, (f) - -Re, (f)1+ Re,(f"n) - -Re, (fout)
JEFL.x
Define R(fin pout): = Re, (fin) - Re, (fout)
= 1 n
Σ Σ (xf) - (I(
Since
==1k=1
(x.) 1, (xx)) Σ
4(ff (xff"(()))) & (xx))
K
Σ &ifft (x;)) (( - G( (x:)) LG (I (x+))
(((fi"(a;)) -1 (a)))
( (xx)) e1 li (x(")
2
(z.f((z))) - (ffx()))
here f fkk e FL.
k=1
K
< 2
cxf) - fz(2)
&1 is c-Lipschitz continuous function
k=1
2c
I(W.)a,.1
II Ki
[ æ1/12
(WL),, denotes k-th row of matrix Wr r.
L
< 4cv Kog
II
Ki = Ker,
25

---

Published in Transactions on Machine Learning Research (05/2024)
by McDiarmid's inequality (the bounded difference is 4v 4yKer/n), with the probability at least - -d we have
R( fout) s B[R(fin fout)] + 4v Ker
log
2n
2 log
29,
x + Σ E (1( (((1))(())) + +4v Kery
+AvKery
(25)
2n 8
42 (Fi.mm. + 4v K
V
log
2
Therefore, together with
22 and
25
24
can be bounded as follows:
min
Re (f)
min (T-
Re, (f)
SEFL. 1 1----00-0)))
S 2 sup (Re,(F) - -Re, (f) + Re, (fit) -Re, (fout)
feFi.
(26)
2
1
s 49, Ti,x
Kerr
log
+ (F 44 Kery
log
2n
2n
2
8R (F + 8V Ker
log
2n
Combining 23 in Part (i) and 26 in Part (ii), conclude that, with probability at least 1 36,
Re,(f)
min
(f)
1
K
8V Kerrr// 1
2
< 49%, a (Foum.li) + 4v20r
log &Rn R L,1
log
(27)
2n
2n
2 8¹
< (F 12
log
where c= we particularly use the hinge loss.
26


Reviews:
[{"review_id": "2wdJ5PL7On", "reviewer": "Reviewer_XRkW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. DeepGPS addresses the limitations of conventional single-valued predictions by providing confident set-valued decisions for interested classes.\n2. The theoretical analysis demonstrates that DeepGPS minimizes the size of the prediction set while maintaining the prescribed accuracy.\n3. DeepGPS incorporates OOD detection, making it effective in scenarios where accurate predictions are crucial to avoid severe consequences.\n4. The offset penalization and weighted loss contribute to the construction of compact acceptance regions, improving the precision of predictions.\n\n\nWeaknesses: \n\n1. Although the hinge loss used in this paper have shown effectiveness, investigating other different classification loss functions may offer valuable insights and potentially enhance the performance of the proposed method.\n2. In practice, Assumption 1 of this paper may be considered somewhat strong.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This article presents Deep Generalized Prediction Set (DeepGPS), a novel network-based set-valued classifier that addresses the challenge of uncertainty in classification tasks. DeepGPS provides sets of plausible labels for ambiguous observations and effectively detects out-of-distribution (OOD) data points. Notably, DeepGPS is the first set-valued classification method to offer both theoretical guarantees and scalability for large datasets. The article provides a rigorous proof demonstrating DeepGPS's achievement of optimal risk within a neural network hypothesis class, while simultaneously ensuring user-prescribed class-specific accuracy. To improve its performance, DeepGPS incorporates a weighted loss mechanism, enabling the definition of tighter acceptance regions. Extensive empirical evaluations conducted on benchmark datasets confirm the superiority of DeepGPS over baseline methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "This paper stands out as a high-quality contribution, characterized by solid theoretical findings and substantial numerical experiments.I have only one minor comment: The authors may consider incorporating additional remarks regarding the utilization of alternative classification losses, such as cross entropy, logistic regression, and others.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UWVbraxMAr", "reviewer": "Reviewer_Bzm6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper proposes an original objective function with theoretical analysis for the set-predictor classifier, where the ambiguity is measured and minimized on the labeled data and unlabeled data, particularly for OOD problems. The paper is clear and easy to follow. The proposed techniques are mostly well motivated and addressed. Approximation and error bounds are well handled, in the standard order of $\\tilde O(1/\\sqrt{n})$.\n\nWeaknesses:\n\n1. Experiments include only some small-scale datasets. More realistic experiments would be highly recommended.\n2. Theorem 1 looks separate from the remaining Theorem 2 and Theorem 3, and also may not be connected well to the entire design. For example, how Theorem 1 benefits the generalization error bound or excess risk? How Theorem 1 helps the experiment performance?\n3. Figure 2 and Figure 3 are important conceptual figures to support the design, but both figures are too informative to easily connect to the main text. More explanation and captions can be very helpful. For example, in Figure 2, linking the weight function and weighted loss to reference equations. What is the value of $\\gamma$ in Figure 2?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents the Deep Generalized Prediction Set (DeepGPS) classifier, a deep network-based set-valued classifier for handling uncertainty in classification by identifying ambiguous observations and detecting out-of-distribution (OOD) observations. DeepGPS employs three proposed terms (two loss functions $\\ell_1$, $\\ell_{2, \\gamma}$ and a regularization $J$ in Equation (1)) as an objective to minimize the ambiguity in the observation, both in the labeled data (classes 1 to K) and the unlabeled data (OOD data). There are three theoretical results: the convergence of the kernel approximation (Theorem 1), the generalization error bound of the class-wise loss (measured by $\\ell_{2, \\gamma}$, classes 1 to K), and the excess risk measured by $\\ell_1$ (including OOD).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions:\n\nQ1: How did the authors find the value for the hyper-parameter $q$ in experiments?\n\nQ2: Can the authors analyze the Assumption 1 and 2 for comparing them with other literatures in OOD? Assumption 1 and 2 together look a bit strong.\n\nQ3: The paper mentions OOD detection as a feature of DeepGPS. Can the authors elaborate in detail on how DeepGPS can be generalized to other potential capabilities?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KYfMMJsGKP", "reviewer": "Reviewer_2jdX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n- The set-valued prediction is interesting to handle uncertainty and OOD detection. The problem considered is interesting, general and there is not enough study for this problem in the literature.\n- The paper includes both theoretical analysis and experimental analysis. The paper includes extensive experimental results and experimental comparisons. The experimental results seem to be strong and convincing.\n\n**Weakness**\n- In the proof of Theorem 3, the paper uses the inequality $R_n(F_{L,\\kappa}^{sum})\\leq \\sqrt{Kc}R_n(F_{L,\\kappa})$. It is not clear to me how this holds. Anyhow, the definition of $R_n(F_{L,\\kappa})$ is not given. Furthermore, as far as I see, F_{L,\\kappa} is a vector-valued function class. Therefore, the authors should give the explicit meaning of the Rademacher complexity.\n- The theoretical analysis ignores several steps. For example, in the proof of Theorem 1, the paper directly uses the inequality $R_D(\\xi\\mapsto \\sigma\\xi^\\top\\triangle)\\leq \\prod_l\\kappa_l/\\sqrt{D}$. It is not clear to me how this holds.\n- Several notations are not well-defined. For example, the covering number in Lemma 1 is not defined. The Rademacher complexity is also not defined.\n- Some results are used without giving the reference, e.g., Lemma 1 and Lemma 2.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a generalized prediction set classifier, which returns set valued classifier to handle the uncertainty in classification. The proposed method uses a fully connected neural network as the hypothesis function, and uses random features to approximate kernel mapping. The proposed objective function consists of three terms reflecting the set size, the accuracy and the regularity. The paper presents theoretical results to illustrate the behavior of the proposed algorithm. The first theoretical result is the approximation error on approximating the kernel by random feature. The second result is the generalization bounds.\n\nExperimental results with several baselines and practical datasets are reported to show the empirical behavior of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The authors should give details of the theoretical analysis in a step-by-step way. This would make be improve the readability of the paper.\n- Notations should be clearly defined and the explicit reference should be given.", "broader_impact_concerns": "No concerns on the ethical issues.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed an end-to-end Deep Generalized Prediction Set (DeepGPS) classifier jointly learning acceptance regions with several contributions.  The first contribution is the it generalised the set-valued classification to OOD detection. The second one is that the authors  add the neural network a layer that approximates the kernel by using Random Fourier Features to overcome the computational overhead of the expensive memory and quadratic programming for kernel machines. The authors also provided learning theory guarantees and convincing experimental support for the proposed approach. 

The revised version adequately addresses reviewers' questions/comments. All reviewers recommended acceptance and featured certification is recommended by one of the reviewers. I agree with the reviewers and recommend acceptance with featured certification.
Decision: Accept (poster)