betaFeedback

WorksMathematics

Generalized Prediction Set with Bandit Feedback

Abstract

In high-stakes environments where uncertainties abound, set-valued prediction offers a cautious and robust mechanism by presenting multiple potential labels as the prediction for each test instance to mitigate the potential risk associated with prediction errors. Yet, integrating this paradigm with out-of-distribution (OOD) detection remains scarcely explored in such settings as online learning with bandit feedback. The bandit feedback mechanism informs the learner about the correctness of the pulled arm/action instead of the explicit ground truth label, leaving the true class label unknown when an incorrect action is taken. To address this challenge, we introduce BanditGPS which conducts set-valued prediction with OOD detection in the bandit feedback setting, using an estimation to the ground truth of class labels. BanditGPS achieves three objectives: render small/informative prediction sets, enhance the OOD detection performance, and control the recall for all normal classes to meet prescribed requirements. Our approach is characterized by the loss function, which trades off between high OOD detection and small prediction sets. Theoretically, we prove that the convergence rate of the regret is O~(T−1/2)\tilde{\mathcal{O}}(T^{-1/2}). The empirical results further show that BanditGPS effectively controls the recalls with promising performances on OOD detection and informative prediction.

Introduction

Conventional single-valued prediction assigns only a single class label to each instance without a provable confidence guarantee. This paradigm could be overly-confident for some data instances, and thereby lead to erroneous decisions with severe consequences. Such an issue is particularly pronounced in critical domains where instances are characterized by high uncertainties. For example, in medical triage, based on a single-label prediction, an AI system might incorrectly categorize a patient with subtle symptoms of a severe condition as low-risk, delaying the critical treatment and hence endangering the patient’s life. Similarly, in financial fraud detection, a single-valued prediction system might not adequately account for the nuanced behaviors of complex fraud schemes, resulting in either over-blocking of legitimate transactions (causing inconvenience and potential loss of business) or under-detecting sophisticated fraud tactics (leading to financial losses). To reduce these associated risks from those observations with high uncertainty, set-valued classification, which reports multiple possible class labels, may be employed. This approach allows for human intervention in those difficult data instances, enabling further error reduction through follow-up investigations.

The literature on set-valued prediction is diverse, with several different types of methodologies. (1) Classification with Reject Option (CRO) [21, 5, 10] incorporates a rejector into the loss function, which is used to abstain from classification if an instance is highly ambiguous. This is equivalent to assigning all labels to the instance, resulting in a less informative prediction set. Zhang et al. [49] introduces a refined option to produce a more informative/smaller prediction set. However, CRO and its variants, despite considering the uncertainty of instances, do not control the “accuracy” under the set-valued prediction paradigm, i.e., the probability of the true label being included in the prediction set. (2) In contrast, Conformal Prediction (CP) [29, 35] offers a prediction set with a theoretical guarantee of accuracy control. CP, assuming data exchangeability, is a distribution-free framework that works alongside machine learning models, e.g., neural networks, to facilitate set-valued prediction. The caveat with CP is that the prediction set may be less informative due to not explicitly minimizing the set size. [27, 3] have focused on developing score functions to reduce the prediction set size to alleviate this limitation. (3) Confidence Set Learning (CSL) [38, 39, 28] approaches set-valued prediction from a constrained optimization perspective, explicitly minimizing the prediction set size while controlling accuracy. Conversely, [14, 15] seek to maximize the accuracy of the prediction given a size budget.

All the above three camps concentrate on set-valued prediction within a closed-world assumption, where each instance is guaranteed at least one known class label. Nevertheless, the dynamic nature of the open world presents the inevitability of encountering new, unknown classes over time. This reality necessitates the unified process of not only classifying known entities but also detecting novel classes, a task termed out-of-distribution (OOD) detection or open-set recognition [46, 26]. Traditional approaches to OOD detection encounter limitations akin to those of single-valued prediction systems. In an effort to bridge this gap, by admitting an empty set for potential atypical points, recent innovations have expanded set-valued classification to incorporate an OOD detection component, such as Cautious Deep Learning (CDL) [20], Balanced Conformal Prediction Set (BCOPS) [18], Generalized Prediction Set (GPS) [41, 40], and Deep Generalized Prediction Set (DeepGPS) [42]. CDL and BCOPS, rooted in Conformal Prediction (CP), unfortunately inherit its predisposition towards larger prediction sets. Conversely, GPS and DeepGPS strive for informative prediction by explicitly minimizing prediction set sizes, aligning with the principles of Confidence Set Learning (CSL).

However, these advancements predominantly address scenarios of offline learning with full feedback, where detailed label information for each instance is accessible—even following an incorrect prediction. This starkly contrasts with the online bandit feedback setting, where a learner’s received feedback is limited to the binary outcome of an arm/action’s success, devoid of explicit insights across all labels. For example, within clinical trials, an adaptive trial design system (learner) might select a treatment (arm), e.g., a type of drug, without knowing its efficacy beyond the absence of disease remission, thus lacking comprehensive feedback on optimal treatments. Although Bandit Class-specific Conformal Prediction (BCCP) [43] represents a step towards accommodating set-valued classification in a closed world under bandit feedback, it lacks mechanisms for OOD detection. Given the limited research in this domain, our study pioneers the exploration of generalizing the set-valued prediction to have the capacity of OOD detection under the bandit feedback setting.

In this article, we have made the following four major contributions. Methodologically, we introduce BanditGPS, an adaptation of the Generalized Prediction Set for online learning with bandit feedback, marking a novel intersection of these research areas. Without accessing the explicit label information, the proposed approach handles the bandit feedback by utilizing an estimation of the ground truth of the class label. Secondly, unlike the offline training regime of DeepGPS [42], BanditGPS dynamically adjusts to maintain class-specific recall (to be defined later) for normal classes with fewer manual parameter adjustments, leading to a feasible deployment for real-world online learning applications. Thirdly, unlike its predecessors, the BanditGPS allows explicit control of the balance between informative prediction and OOD detection effectiveness, making it easy for practitioners to use given their specific business needs. Lastly, we theoretically prove a regret convergence rate of O~(T−1/2)\widetilde{O}(T^{-1/2}) which is competitive in the literature; the empirical study confirms the efficacy of BanditGPS.

The rest of this article is organized as follows. In § 2, we delve into key notations and review works that lay the groundwork for our study. § 3 articulates the problem formulation and introduces the BanditGPS method with an algorithm. The convergence rate of regret for the algorithm is theoretically explored in § 4. In § 5, we present empirical evidence demonstrating the effectiveness of BanditGPS. A conclusion is offered in § 7. Additional materials, including detailed proofs and extended experiments, are provided in Section A.

Preliminary

In this section, we discuss some notions and briefly review seminal works across three pivotal areas: set-valued classification, out-of-distribution detection, and the multi-armed Bandit problem.

Set-valued Classification: Let (X,Y)∈X×Y(X, Y) \in\mathcal{X} \times\mathcal{Y} be an observation generated from an unknown distribution, where Y={1,…,K}\mathcal{Y} = \{1, \ldots, K\}. A set-valued classifier is a map ϕ:X↦2Y\phi: \mathcal{X} \mapsto2^{\mathcal{Y}} to return a prediction set ϕ(X)\phi(X) for the instance XX based on a certain rule. Commons metrics Vovk et al. [36] to evaluate the performance of a set-valued classifier include the (expected) prediction set size and the accuracy. The prediction set size is defined through the cardinality of the prediction set, i.e., ∣ϕ(X)∣|\phi(X)|, which gauges the number of class labels predicted for instance XX. Because both the classifier ϕ(⋅)\phi(\cdot) and the instance XX are random, we typically focus on E[∣ϕ(X)∣]\mathbb{E}[|\phi(X)|]. The accuracy in the set-valued prediction paradigm is defined as the probability that the true label of an observation is included in its prediction set, i.e., P[Y∈ϕ(X)]\mathbb{P}[Y \in\phi(X)], which is also referred to as coverage probability in the CP literature Vovk et al. [35].

The accuracy P[Y∈ϕ(X)]\mathbb{P}[Y \in\phi(X)] represents the overall performance of the classifier over all classes. For each class, we denote the (class-specific) recall as P[Y∈ϕ(X)∣Y=k]\mathbb{P}[Y \in\phi(X) \mid Y = k] to measure the classifier’s performance on class kk. Intuitively speaking, there is a trade-off between prediction set size and recall. Higher recall for normal classes often comes with a larger prediction set ϕ(X)\phi(X) (because this allows an increased likelihood for the true class label being included in ϕ(X)\phi(X)). While CP-based classifiers [35, 27, 3] offer a controlled recall guarantee, their prediction set sizes are contingent on the chosen score function. In contrast, CSL-based approaches [28, 38, 39, 41] strive to minimize prediction set sizes while maintaining the normal class recall.

Out-of-distribution (OOD) Detection and Open-set Recognition (OSR): The goal of OOD and OSR [6, 26, 11, 46] is to conduct single-valued prediction for instances in the normal classes in addition to rejecting atypical observations that potentially comes from a new or anomaly class that was not present in the training data. Recently, Selective Classification with OOD detection (SCOD) [44, 53] and Unified Open-set Recognition (UOSR) [24, 9] further consider identifying difficulty observations (hard to distinguish among existing normal classes) when they are not rejected as OOD points. The difficult observations and OOD points in both SCOD and UOSR can be respectively viewed as the ambiguous instances with prediction set sizes greater than 1 and the atypical instances with the empty prediction set in the set-valued prediction paradigm.

Multi-armed Bandit (MAB): The MAB framework [25, 4] concerns a decision-making scenario where a learner sequentially pulls an arm AA from a set {1,…,K}\{1, \ldots, K\} to maximize cumulative rewards over time. To this end, various policies π\pi (could be either a probability distribution or deterministic rule) are proposed to guide the arm pulling, e.g., epsilon-greedy [31], Upper Confidence Bound [4], and Thompson sampling strategies [33], etc. The policy π\pi and the pulled arm AA in the MAB can be conceptually treated as a form of decision rule and a predicted label in the classification problem.

MAB problems are prevalent in various fields, such as online advertising, clinical trials, and recommendation systems, where a context XX informs personalized decision-making. Specifically, after receiving the context XX from an environment, a learner pulls an arm AA that follows π(⋅∣X)\pi(\cdot\mid X), and then receives a feedback 1{A=Y}\mathbb{1}\{A = Y\} returned by the environment. Such bandit feedback only indicates the correctness of the pulled arm. If the feedback is 00, the learner does not know the ground truth and hence faces a challenge in optimizing reward strategies. While existing studies [23, 37, 13, 1, 17, 34] have explored linear and neural network-based [52, 22, 50, 45] approaches to the bandit problem, they seldom address set-valued classification and/or OOD detection within this framework.

Notably, while research [32, 51, 30] has explored set-valued prediction in reinforcement learning, their focus diverges from our bandit-centric investigation. The recent work BCCP [43] is most aligned with our work, yet it does not directly consider the task of OOD detection, a practical requirement in applications. For instance, in social content moderation, a system needs to flag user-generated content into some categories (safe, offensive, etc), and detect new types of harmful content as well. Our study, therefore, introduces a novel approach, considering set-valued classification with OOD detection in the context of bandit feedback, addressing a significant gap in the literature.

Set-valued Prediction with Bandit Feedback: The learning framework operates under bandit feedback, where only correctness information for a selected action is observed. At each time step tt, given a context Xt\mathbf{X}_t, a learner first produces a set-valued prediction ϕt(Xt)\phi_t(\mathbf{X}_t) with a certain theoretical guarantee, indicating a subset of potential labels. Subsequently, a learner takes an action AtA_t (denoting a single label) according to the policy πt\pi_t, where AtA_t is sampled from all possibilities. The environment provides a binary feedback signal that whether the pulled arm AtA_t confirms the ground true label of Xt\mathbf{X}_t (see Algorithm 1).

Methodology

In this section, we develop and optimize our set-valued classifier, BanditGPS, for the online bandit feedback environment. BanditGPS is engineered to accomplish three critical objectives: (1) generate small/informative prediction sets; (2) proficiently detect OOD queries; and (3) maintain the recall for each normal class to be above a threshold of 1−γ1-\gamma, where γ\gamma is a tolerance level prescribed by practitioners. The algorithmic framework and operational flow of BanditGPS are outlined in Algorithm 1. Throughout the article, we use [K][K] to denote the set {1,…,K}\{1,\ldots,K\} for convenience.

Consider a sequence of i.i.d. samples with inaccessible labels (Xt,Yt)∈X×Y(\mathbf{X}_t,Y_t) \in\mathcal{X} \times\mathcal{Y}, t=1,…,Tt=1,\ldots,T generated from the environment. Within this setting, we assume KK established normal classes known from historical data. Nonetheless, we anticipate the emergence of OOD instances over time, which may not fit within these predefined classes and potentially signify novel, yet-to-be-identified classes.

To navigate this task, we leverage a neural network as our hypothesis class F\mathcal{F}. Specifically, we define a decision function vector fWt∈F\mathbf{f}_{\mathbf{W}_t} \in\mathcal{F}, parameterized by weights Wt\mathbf{W}^t at time tt, where fWt(X):=(fWt1(X),…,fWtK(X))T∈RK\mathbf{f}_{\mathbf{W}_t}(\mathbf{X}) := (f^1_{\mathbf{W}_t}(\mathbf{X}),\ldots,f^K_{\mathbf{W}_t}(\mathbf{X}))^\mathsf{T} \in\mathbb{R}^K encapsulates the decision functions for each of the KK normal classes. For any given query Xt\mathbf{X}_t revealed at time tt, the prediction set is constructed as,

ϕt(Xt):={k∈[K]:fWtk(Xt)≥0}.(1)\phi_t(\mathbf{X}_t) := \{k \in[K] : f^k_{\mathbf{W}_t}(\mathbf{X}_t) \ge0\}. \tag*{(1)}

Intuitively speaking, class kk is considered to be a plausible label for query Xt\mathbf{X}_t if the query falls into the acceptance region for class kk defined by {x:fWtk(x)≥0}\{x : f^k_{\mathbf{W}_t}(x) \ge0\}. Note that the union of all the KK many acceptance regions may not cover the entire space X\mathcal{X}, and regions may overlap with each other.

Prediction Set Size Minimization: Based on the above definition of the prediction set, the prediction set size for the query Xt\mathbf{X}_t is naturally quantified as ∣ϕt(Xt)∣:=∑k=1K1{fWtk(Xt)≥0}|\phi_t(\mathbf{X}_t)| := \sum_{k=1}^{K} \mathbb{1}\{f^k_{\mathbf{W}_t}(\mathbf{X}_t) \ge0\}, which ranges from 00 to KK. In particular, size 00 denotes that the classifier believes Xt\mathbf{X}_t is an OOD instance, indicating its distinctiveness from all normal classes. Conversely, size KK signifies the maximal ambiguity associated with the query, suggesting that it blurs the lines across all normal classes.

Due to the discontinuous, and hence, computationally intractable 0-1 loss 1{u≥0}\mathbb{1}\{u \ge0\} involved in the definition of prediction set size, we employ a surrogate hinge loss ℓ1(u):=[1+u]+=max⁡(0,1+u)\ell_1(u) := [1+u]_+ = \max(0,1+u) as a proxy for the 0-1 loss (see Figure 1). This substitution enables a practical way to return a smaller (more informative) prediction set by minimizing the loss

Surrogate loss functions

Figure 1. Surrogate loss functions

∑k=1Kℓ1(fWtk(Xt))=∑k=1K[1+fWtk(Xt)]+.(2)\sum_{k=1}^{K}\ell_1(f^k_{\mathbf{W}_t}(\mathbf{X}_t)) = \sum_{k=1}^{K}[1+f^k_{\mathbf{W}_t}(\mathbf{X}_t)]_+. \tag*{(2)}

OOD Detection Maximization: A query instance XtX_t is not flagged as OOD if and only if its prediction set is non-empty, i.e., ∣ϕt(Xt)∣>0|\phi_t(X_t)| > 0. This is equivalent to the existence of at least one class k∈[K]k \in[K] such that fWtk(Xt)≥0f_{\mathcal{W}_t}^k(X_t) \ge0, or equivalently, max⁡k∈[K]fWtk(Xt)≥0\max_{k\in[K]} f_{\mathcal{W}_t}^k(X_t) \ge0. Therefore, to enhance the OOD detection performance, it is imperative to penalize the indicator function of the occurrence of this event, 1{max⁡k∈[K]fWtk(Xt)≥0}1\{\max_{k\in[K]} f_{\mathcal{W}_t}^k(X_t) \ge0\}. Given the similar challenge imposed by the 0-1 loss as mentioned above, to effectively tackle the OOD detection task, we instead minimize the following:

ℓ1(max⁡k∈[K]fWtk(Xt))=[1+max⁡k∈[K]fWtk(Xt)]+.(3)\ell_1\left(\max_{k\in[K]} f_{\mathcal{W}_t}^k(X_t)\right) = \left[1+\max_{k\in[K]} f_{\mathcal{W}_t}^k(X_t)\right]_+. \tag*{(3)}

Recall Control for Normal Classes: By relating the definition of prediction set (1), the class-specific recall is further expressed as P[Yt∈ϕt(Xt)∣Yt=k]=P[fWtk(Xt)≥0∣Yt=k]\mathbb{P}[Y_t \in\phi_t(X_t) \mid Y_t = k] = \mathbb{P}[f_{\mathcal{W}_t}^k(X_t) \ge0 \mid Y_t = k]. Thus, controlling the class-specific normal class recall to the prescribed value at least 1−γ1-\gamma, that is,

P[fWtk(Xt)≥0∣Yt=k]=E[1{fWtk(Xt)≥0}∣Yt=k]≥1−γ,for k∈[K]\mathbb{P}[f_{\mathcal{W}_t}^k(X_t) \ge0 \mid Y_t = k] = \mathbb{E}[1\{f_{\mathcal{W}_t}^k(X_t) \ge0\} \mid Y_t = k] \ge1-\gamma,\quad\text{for } k\in[K]

is equivalent to E[1{Yt=k}⋅[1{fWtk(Xt)<0}−γ]]≤0\mathbb{E}[1\{Y_t=k\}\cdot[1\{f_{\mathcal{W}_t}^k(X_t)<0\}-\gamma]]\le0, for k∈[K]k\in[K] due to the Bayes theorem and some algebra (see details in Section A.2). This inequality can be viewed as a constraint in constrained optimization problems. Equivalently, our objective function incorporates the left-hand side of this constraint as additional regularization terms, that is,

E[1{Yt=k}⋅[1{fWtk(Xt)<0}−γ]],for k∈[K].(4)\mathbb{E}[1\{Y_t=k\}\cdot[1\{f_{\mathcal{W}_t}^k(X_t)<0\}-\gamma]],\quad\text{for } k\in[K]. \tag*{(4)}

In the bandit feedback setting, the ground truth YtY_t and hence the quantities 1{Yt=k},k∈[K]1\{Y_t=k\}, k\in[K] are unobservable since the learner has no direct access to the ground truth of the label YtY_t once receives the query XtX_t. Instead, it only knows whether its pulled arm AtA_t based on a policy πt\pi_t is correct or not, i.e., the feedback 1{At=Yt}1\{A_t=Y_t\}. Particularly, if the feedback is 0, the learner has no idea which label is the true class. To overcome this challenge, in practice, the ground truth 1{Yt=k}1\{Y_t=k\} (the first indicator function in (4)) can be replaced by an unbiased estimation conditional on (Xt,Yt)(X_t,Y_t),

Δt,k:=1{At=k}πt(k∣Xt)1{At=Yt},(5)\Delta_{t,k}:=\frac{1\{A_t=k\}}{\pi_t(k\mid X_t)}1\{A_t=Y_t\}, \tag*{(5)}

due to the fact Eπt[Δt,k∣Xt,Yt]=1{Yt=k}\mathbb{E}_{\pi_t}[\Delta_{t,k}\mid X_t,Y_t]=1\{Y_t=k\}, where πt\pi_t governs the distribution of AtA_t given XtX_t. Different from the KK-arm policy, with arms from [K][K] reviewed in Section 2, we utilize an augmented policy with an additional arm, namely OOD, corresponding to the case that the instance comes from the OOD class. The definition of policy πt\pi_t is deferred to the next subsection.

To the same token, the intractable 0-1 loss 1{u<0}1\{u<0\} in the second indicator function in (4) can be substituted by the surrogate hinge loss [1−u]+:=max⁡(0,1−u)[1-u]_+ := \max(0,1-u). This amounts to replacing 1{u<0}−γ1\{u<0\}-\gamma in (4) by ℓ2,γ(u):=[1−u]+−γ\ell_{2,\gamma}(u):=[1-u]_+-\gamma. Thus, instead of working with the loss function in (4), we can minimize the empirical average of the following loss function in practice:

Δt,k⋅ℓ2,γ(fWtk(Xt)):=Δt,k⋅([1−fWtk(Xt)]+−γ).(6)\Delta_{t,k}\cdot\ell_{2,\gamma}(f_{\mathcal{W}_t}^k(X_t)):=\Delta_{t,k}\cdot\left([1-f_{\mathcal{W}_t}^k(X_t)]_+-\gamma\right). \tag*{(6)}

Policy Design: In this article, our policy πt\pi_t is constructed based on the scoring function fWt(x)=(fWt1(x),⋯ ,fWtK(x))Tf^{\mathcal{W}_t}(x)=(f_{\mathcal{W}_t}^1(x),\cdots,f_{\mathcal{W}_t}^K(x))^\mathsf{T} associated with the normal classes. Specifically, the policy is defined as,

πt(k∣Xt):=exp⁡(fWtk(Xt))exp⁡(−max⁡j∈[K]fWtj(Xt))+∑j=1Kexp⁡(fWtj(Xt)),k∈[K],\pi_t(k\mid X_t):=\frac{\exp(f_{\mathcal{W}_t}^k(X_t))}{\exp(-\max_{j\in[K]}f_{\mathcal{W}_t}^j(X_t))+\sum_{j=1}^K\exp(f_{\mathcal{W}_t}^j(X_t))},\quad k\in[K],
πt(OOD∣Xt):=exp⁡(−max⁡j∈[K]fWtj(Xt))exp⁡(−max⁡j∈[K]fWtj(Xt))+∑j=1Kexp⁡(fWtj(Xt)).\pi_t(\mathrm{OOD}\mid X_t):=\frac{\exp(-\max_{j\in[K]}f_{\mathcal{W}_t}^j(X_t))}{\exp(-\max_{j\in[K]}f_{\mathcal{W}_t}^j(X_t))+\sum_{j=1}^K\exp(f_{\mathcal{W}_t}^j(X_t))}.

Note that πt(a∣Xt)\pi_t(a\mid X_t), a∈{1,…,K,OOD}a\in\{1,\ldots,K,\mathrm{OOD}\}, sum up to 1 and hence is a legitimate probability distribution for AtA_t. Under this policy, the probability of pulling arm kk is proportional to the exponentiated score for class kk, while the probability of pulling OOD is proportional to the exponentiated negative maximum score over all normal classes. Hence, a small score across all normal classes indicates a strong likelihood of the query being from the OOD class.

The Overall Objective Function: Finally, taking into consideration three goals, i.e., minimizing prediction set size (2), enhancing OOD detection (3), and controlling class-specific recall (6) for normal classes, the unified risk function for each data instance that we aim to minimize is

L(Xt;Wt):=λK∑k=1Kℓ1(fWtk(Xt))+(1−λ)ℓ1(max⁡k∈[K]fWtk(Xt))+∑k=1Kλt,kΔt,kℓ2,γ(fWtk(Xt)),(7)\mathcal{L}(X_t;\mathcal{W}^t) := \frac{\lambda}{K}\sum_{k=1}^{K}\ell_1(f_{\mathcal{W}^t}^k(X_t)) + (1-\lambda)\ell_1\left(\max_{k\in[K]} f_{\mathcal{W}^t}^k(X_t)\right) + \sum_{k=1}^{K}\lambda_{t,k}\Delta_{t,k}\ell_{2,\gamma}(f_{\mathcal{W}^t}^k(X_t)), \tag*{(7)}

where the neural network fWtf_{\mathcal{W}^t} is updated by the stochastic gradient descent (or its variants). Here λ∈[0,1]\lambda\in[0,1] is a user-specified value to indicate the trade-off between prediction set size and OOD detection performance. Note that we do not treat λ\lambda as a tuning parameter and rather leave it to be specified by the user according to their unique needs.

As for the parameter λt,k\lambda_{t,k}, an improperly chosen λt,k\lambda_{t,k} may lead to two cases: a λt,k\lambda_{t,k} that is too small might fail to control the recall for normal classes, while a λt,k\lambda_{t,k} that is too large can cause the empirical normal recall highly above the prerequisite 1−γ1-\gamma and hence enlarge the prediction sets and impair the OOD detection performance. Additionally, an appropriate value of λt,k\lambda_{t,k} can vary across tasks, making it difficult to predefine an optimal value. To address these limitations, we employ the primal-dual algorithm to dynamically optimize the value of λt,k\lambda_{t,k} (see Equation (8) in Algorithm 1). Specifically, if the current prediction is over control, i.e., ℓ2,γ(fWtk(Xt))<0\ell_{2,\gamma}(f_{\mathcal{W}^t}^k(X_t)) < 0, Equation (8) will adaptively lead to a smaller value of the parameter λt+1,k\lambda_{t+1,k} in the next iteration. Such adjustment helps potentially return smaller prediction sets. Similarly, when ℓ2,γ(fWtk(Xt))>0\ell_{2,\gamma}(f_{\mathcal{W}^t}^k(X_t)) > 0, Equation (8) will lead to a larger value of λt+1,k\lambda_{t+1,k} in the next iteration. This automatic updating rule frees us from the burden of manually selecting the value of λt+1,k\lambda_{t+1,k} with excessive effort.

Main Theorems

This section provides the convergence rate analysis concerning the regret associated with prediction set size and OOD detection performance. Our analysis builds upon foundational work in over-parameterized neural networks [16, 2, 7, 8, 12], i.e., sufficiently wide neural networks.

Let the hypothesis class of ReLU neural networks with depth LL and a constant width mm be

F:={fW:Rp↦RK∣fW(⋅)=WLσL−1(WL−1σL−2(⋯σ1(W1(⋅)))}.\mathcal{F}:=\left\{f_{\mathcal{W}}:\mathbb{R}^{p}\mapsto\mathbb{R}^{K}\mid f_{\mathcal{W}}(\cdot)=\mathbf{W}_{L}\sigma_{L-1}(\mathbf{W}_{L-1}\sigma_{L-2}(\cdots\sigma_1(\mathbf{W}_1(\cdot)))\right\}.

where W:=(Vec⁡(W1)⊤,…,Vec⁡(WL)⊤)⊤\mathcal{W}:=(\operatorname{Vec}(\mathbf{W}_1)^{\top},\ldots,\operatorname{Vec}(\mathbf{W}_L)^{\top})^{\top} denotes a concatenated long vector by vectorizing W1∈Rm×p\mathbf{W}_1\in\mathbb{R}^{m\times p}, Wl∈Rm×m\mathbf{W}_l\in\mathbb{R}^{m\times m} for 2≤l≤L−12\le l\le L-1, and WL∈RK×m\mathbf{W}_L\in\mathbb{R}^{K\times m}. The ReLU activation functions σl,l∈[L−1]\sigma_l,l\in[L-1] are element-wisely applied on each layer. Additionally, we define the ball around the neural network’s initialization as B(W1,ω):={W:∥Wl−Wl1∥2≤ω,l∈[L]}\mathcal{B}(\mathcal{W}^1,\omega):=\{\mathcal{W}:\|\mathbf{W}_l-\mathbf{W}_l^1\|_2\le\omega,l\in[L]\}. In this article, the Frobenius norm of a matrix is denoted by ∥⋅∥2\|\cdot\|_2 and this notation extends to tensors.

Consider a restricted hypothesis class that adheres to the empirical normal recall control within this ball whose radius scales in the order of m−1/2m^{-1/2}:

F+:={fW∈F:1T∑t=1T1{Yt=k}⋅ℓ2,γ(fWk(Xt))≤0,k∈[K] and W∈B(W1,Rm−1/2)}.\mathcal{F}^{+}:=\left\{f_{\mathcal{W}}\in\mathcal{F}:\frac{1}{T}\sum_{t=1}^{T}\mathbb{1}\{Y_t=k\}\cdot\ell_{2,\gamma}(f_{\mathcal{W}}^k(X_t))\le0,k\in[K]\ \text{and}\ \mathcal{W}\in\mathcal{B}(\mathcal{W}^1,Rm^{-1/2})\right\}.

where R>0R > 0 is a fixed constant. We define the loss function as ℓ(fW(X)):=λK∑k=1Kℓ1(fWk(X))+(1−λ)ℓ1(max⁡k∈[K]fWk(X))\ell(f_{\mathbf{W}}(\mathbf{X})) := \frac{\lambda}{K}\sum_{k=1}^{K}\ell_{1}(f_{\mathbf{W}}^{k}(\mathbf{X})) + (1-\lambda)\ell_{1}(\max_{k\in[K]} f_{\mathbf{W}}^{k}(\mathbf{X})) which consists of the loss on prediction set size and the loss on OOD detection; they may be viewed as a negative reward and both are parts of the objective function L(X;W)\mathcal{L}(\mathbf{X};\mathbf{W}) in Equation (7). In this context, regret is defined as the difference between the loss achieved by the algorithm and the least loss that could have been achieved by the best possible action taken in every iteration. To derive the rate of convergence for the regret, we use the following three assumptions.

Assumption 1. We assume the entries in Wl1\mathbf{W}_{l}^{1}, l∈[L−1]l \in[L-1] are initialized with Gaussian distribution N(0,2m)\mathcal{N}(0,\frac{2}{m}) and the entries in WL1\mathbf{W}_{L}^{1} are initialized with Gaussian distribution N(0,1K)\mathcal{N}(0,\frac{1}{K}).

Assumption 2. The instance Xt∈Rp\mathbf{X}_{t} \in\mathbb{R}^{p}, t∈[T]t \in[T] is normalized to have a unit norm, i.e., ∥Xt∥2=1\lVert\mathbf{X}_{t}\rVert_{2}=1.

Assumption 3. ∃ Cλ,CΔ>0\exists\ C_{\lambda}, C_{\Delta} > 0, s.t. for each k∈[K],t∈[T]k \in[K], t \in[T], λt,k≤Cλ,Δt,k≤CΔ\lambda_{t,k} \le C_{\lambda}, \Delta_{t,k} \le C_{\Delta}.

Remark 4. Theorem 1 and Theorem 2 are standard assumptions in the regime of over-parameterized neural networks. Cao & Gu [8] extends Theorem 2 to the one with bound norms.

The assumption of the bounded λt,k\lambda_{t,k} is empirically verified as in Figure 2 for the case of λ=1\lambda=1. It shows that λt,k≤6\lambda_{t,k} \le6 holds for all tt and kk across the three datasets we work with. The assumption of the boundness of Δt,k\Delta_{t,k} is not strong either because its upper bound is inversely related to the lower bound of πt(k∣Xt)≠0\pi_{t}(k \mid\mathbf{X}_{t}) \ne0 (see Equation (5)), which can be manually manipulated in practice.

Figure 2. Updated λt,k\lambda_{t,k} for normal class across three datasets when λ=1\lambda= 1

Theorem 5. Let pk:=P[Yt=k]p_{k} := \mathbb{P}[Y_{t}=k] be the prior probability for normal class k∈[K]k \in[K]. The average recall for any class kk over all time for the prediction sets returned by Algorithm 1 is guaranteed:

1T∑t=1TP[Yt∈ϕt(Xt)∣Yt=k]≥1−γ−CλTη2pk∀k.\frac{1}{T}\sum_{t=1}^{T}\mathbb{P}[Y_{t}\in\phi_{t}(\mathbf{X}_{t})\mid Y_{t}=k] \ge1-\gamma-\frac{C_{\lambda}}{T\eta_{2}p_{k}}\quad\forall k.

The above probability is taken over all the randomness during the learning process. If the learning rate η2=O(T−α)\eta_{2}=O(T^{-\alpha}) with α∈[0,1)\alpha\in[0,1), Theorem 5 implies that, on average, the accumulative normal recall approaches to the prescribed value 1−γ1-\gamma with rate O(Tα−1)O(T^{\alpha-1}). Note that the recall bound may be less meaningful in a short-term regime. Intuitively, if pkp_{k} is very small, it means that we may not collect sufficient samples for class kk within a finite time horizon, leading to potential failures in recall control. However, the denominator in Theorem 5 includes TT, compensating for this issue in the long run.

Theorem 6. Define an optimal learner with controlled normal recalls from the hypothesis class F+\mathcal{F}^{+} as fW∗:=arg⁡min⁡fW∈F+1T∑t=1Tℓ(fW(Xt))f_{\mathbf{W}^{*}} := \mathop{\arg\min}_{f_{\mathbf{W}}\in\mathcal{F}^{+}}\frac{1}{T}\sum_{t=1}^{T}\ell(f_{\mathbf{W}}(\mathbf{X}_{t})). There exists an absolute constant κ\kappa satisfying that, for any constant R>0R>0, m≥O(κ−2R2L2[log⁡(m)]3)m\ge O(\kappa^{-2}R^{2}L^{2}[\log(m)]^{3}), and the learning rate η1=O(RKTm)\eta_{1}=O(\frac{R}{\sqrt{KTm}}), with probability at least 1−O(TL2)exp⁡(−Ω(mω2/3L))1-O(TL^{2})\exp(-\Omega(m\omega^{2/3}L)) over the randomness of the initialization W1\mathbf{W}^{1}, the regret is bounded as

Regret⁡(T):=1T∑t=1Tℓ(fWt(Xt))−1T∑t=1Tℓ(fW∗(Xt))≤c∗O(LRKT+L3R4/3log⁡(m)m1/6).\operatorname{Regret}(T):=\frac{1}{T}\sum_{t=1}^{T}\ell(f_{\mathbf{W}_{t}}(\mathbf{X}_{t}))-\frac{1}{T}\sum_{t=1}^{T}\ell(f_{\mathbf{W}^{*}}(\mathbf{X}_{t}))\le c^{*}O\left(\frac{LR\sqrt{K}}{\sqrt{T}}+\frac{L^{3}R^{4/3}\sqrt{\log(m)}}{m^{1/6}}\right).

where the constant c∗:=(λK+1−λ+KCλCΔ)2+λK+1−λK+KCλCΔc^{*}:=\left(\frac{\lambda}{\sqrt{K}}+1-\lambda+\sqrt{K}C_{\lambda}C_{\Delta}\right)^{2}+\frac{\lambda}{K}+\frac{1-\lambda}{\sqrt{K}}+KC_{\lambda}C_{\Delta}.

Theorem 6 shows that when the width of the neural network is sufficiently large, Algorithm 1 leads to the regret convergence rate with the order O(T−1/2+m−1/6log⁡(m))O(T^{-1/2}+m^{-1/6}\sqrt{\log(m)}). Particularly, if the width further satisfies m≥O(T3)m \ge O(T^3), then the regret is close to the parametric rate O~(T−1/2)\widetilde{O}(T^{-1/2}), which is similar to the convex online learning. Similar convergence rate results were previously shown in Allen-Zhu et al. [2]; Cao & Gu [7]; Chen et al. [12] despite different settings.

Experiments

Baselines: Due to the unique setting and task, BCCP [43] represents the most aligned approach to our context even though it lacks mechanisms for OOD detection. To establish a baseline for comparison, we extend BCCP to also output an empty set, indicating OOD instances. Additionally, we present the performance of our model under the full feedback scenario, where the model is trained based on the labeled data, in order to show the performance in an ideal setting as a benchmark.

Set-up: We compare the methods by evaluating them on CIFAR10, CIFAR100, and SVHN datasets. For CIFAR10, we set {Bird, Cat, Deer, Dog, Frog, Horse} as normal classes while all the remaining {Airplane, Car, Ship, Truck} as the OOD class; for CIFAR100, we treat 10 coarser classes {Aquatic mammals, Flowers, Fruit and vegetables, Natural outdoor scenes, Omnivores and herbivores, Medium-sized mammals, Invertebrates, Reptiles, Small mammals, Trees} as normal classes, and the remaining 10 coarser classes as the entire OOD class; for SVHN, we let Digits {1, 2, 4, 6, 7, 9} as the normal classes and the remaining Digits {0, 3, 5, 8} be the OOD superclass.

We let all the experiments have the same desired recall 1−γ=0.951-\gamma=0.95 across datasets, utilizing ResNet He et al., [19] as the backbone architecture, Adam for optimization, learning rate η1=10−4\eta_1=10^{-4} for network updates, and η2=η2(t)=t−1/2\eta_2=\eta_2(t)=t^{-1/2} for optimizing λt,k\lambda_{t,k}. To improve the computational efficiency, model updates employ batch data with a size of 256 in each iteration, with about 6000 total iterations.

Metrics: For each iteration t∈[T]t \in[T], we report several accumulative quantities (see definitions in Table 1): Acum_OOD$(t),AcumNormalMin, Acum_Normal_Min(t),AcumNormalMax, Acum_Normal_Max(t) show the OOD detection performance and the recall control on normal classes while Acum_Card(t),AcumCondCard, Acum_Cond_Card(t)$ assess the prediction set size. Additionally, we assess classifiers’ performance on a fixed holdout labeled dataset after each iteration. In Table 1, BsB_s denotes the batch of data at iteration ss, and nn denotes the sample size of the holdout dataset, and

Algorithm 1 BanditGPS
Require: Initialize weight matrices W1\mathcal{W}^1 and λ1,k\lambda_{1,k}, k∈[K]k \in[K].
Given λ\lambda and learning rates η1,η2\eta_1,\eta_2.
1: for t=1,2,3,…,Tt=1,2,3,\ldots,T do
2: Learner receives XtX_t and returns a prediction set ϕt(Xt):={k∈[K]:fWtk(Xt)≥0}\phi_t(X_t):=\{k\in[K]:f_{\mathcal{W}^t}^k(X_t)\ge0\}
3: Learner pulls an arm At∼πtA_t\sim\pi_t and computes Δt,k\Delta_{t,k}
4: Update parameters: Wt+1=Wt−η1∇WL(Xt;Wt)\mathcal{W}^{t+1}=\mathcal{W}^t-\eta_1\nabla_{\mathcal{W}}\mathcal{L}(X_t;\mathcal{W}^t); λt+1,k=[λt,k+η2Δt,kℓ2,γ(fWtk(Xt))]+\lambda_{t+1,k}=[\lambda_{t,k}+\eta_2\Delta_{t,k}\ell_{2,\gamma}(f_{\mathcal{W}^t}^k(X_t))]_+
5: end for

Table 1.

Accumulative metricMetric on the hold-out dataset
Acum_Normal_Min(t)=min⁡k∈[K]Acum_recall(t,k)\mathrm{Acum\_Normal\_Min}(t)=\min_{k\in[K]}\mathrm{Acum\_recall}(t,k)Hdt_Normal_Min(t)=min⁡k∈[K]Hdt_recall(t,k)\mathrm{Hdt\_Normal\_Min}(t)=\min_{k\in[K]}\mathrm{Hdt\_recall}(t,k)
Acum_Normal_Max(t)=max⁡k∈[K]Acum_recall(t,k)\mathrm{Acum\_Normal\_Max}(t)=\max_{k\in[K]}\mathrm{Acum\_recall}(t,k)Hdt_Normal_Max(t)=max⁡k∈[K]Hdt_recall(t,k)\mathrm{Hdt\_Normal\_Max}(t)=\max_{k\in[K]}\mathrm{Hdt\_recall}(t,k)
Acum_OOD(t)=Acum_recall(t,OOD)\mathrm{Acum\_OOD}(t)=\mathrm{Acum\_recall}(t,\mathrm{OOD})Hdt_OOD(t)=Hdt_recall(t,OOD)\mathrm{Hdt\_OOD}(t)=\mathrm{Hdt\_recall}(t,\mathrm{OOD})
Acum_Cond_Card(t)=∑s=1t∑Xi∈Bs∣ϕt(Xi)∣⋅1{Yi≠OOD}∑s=1t∑Xi∈Bs1{Yi≠OOD}\mathrm{Acum\_Cond\_Card}(t)=\dfrac{\sum_{s=1}^{t}\sum_{X_i\in B_s}|\phi_t(X_i)|\cdot\mathbb{1}\{Y_i\ne\mathrm{OOD}\}}{\sum_{s=1}^{t}\sum_{X_i\in B_s}\mathbb{1}\{Y_i\ne\mathrm{OOD}\}}Hdt_Cond_Card(t)=∑i=1n∣ϕt(Xi)∣⋅1{Yi≠OOD}∑i=1n1{Yi≠OOD}\mathrm{Hdt\_Cond\_Card}(t)=\dfrac{\sum_{i=1}^{n}|\phi_t(X_i)|\cdot\mathbb{1}\{Y_i\ne\mathrm{OOD}\}}{\sum_{i=1}^{n}\mathbb{1}\{Y_i\ne\mathrm{OOD}\}}
Acum_Card(t)=∑s=1t∑Xi∈Bs∣ϕt(Xi)∣∑s=1t∣Bs∣\mathrm{Acum\_Card}(t)=\dfrac{\sum_{s=1}^{t}\sum_{X_i\in B_s}|\phi_t(X_i)|}{\sum_{s=1}^{t}|B_s|}Hdt_Card(t)=1n∑i=1n∣ϕt(Xi)∣\mathrm{Hdt\_Card}(t)=\dfrac{1}{n}\sum_{i=1}^{n}|\phi_t(X_i)|

Table 1 (PDF p. 9). Displayed Metrics for Comparison

Acum_recall(t,k):=∑s=1t∑Xi∈Bs1{Yi=k & Yi∈ϕt(Xi)}∑s=1t∑Xi∈Bs1{Yi=k},k∈[K]\mathrm{Acum\_recall}(t,k):=\frac{\sum_{s=1}^{t}\sum_{X_i\in B_s}\mathbb{1}\{Y_i=k\ \&\ Y_i\in\phi_t(X_i)\}}{\sum_{s=1}^{t}\sum_{X_i\in B_s}\mathbb{1}\{Y_i=k\}},\qquad k\in[K]
Acum_recall(t,OOD):=∑s=1t∑Xi∈Bs1{Yi=OOD & ∣ϕt(Xi)∣=0}∑s=1t∑Xi∈Bs1{Yi=OOD}\mathrm{Acum\_recall}(t,\mathrm{OOD}):=\frac{\sum_{s=1}^{t}\sum_{X_i\in B_s}\mathbb{1}\{Y_i=\mathrm{OOD}\ \&\ |\phi_t(X_i)|=0\}}{\sum_{s=1}^{t}\sum_{X_i\in B_s}\mathbb{1}\{Y_i=\mathrm{OOD}\}}
Hdt_recall(t,k):=∑i=1n1{Yi=k & Yi∈ϕt(Xi)}∑i=1n1{Yi=k},k∈[K]\mathrm{Hdt\_recall}(t,k):=\frac{\sum_{i=1}^{n}\mathbb{1}\{Y_i=k\ \&\ Y_i\in\phi_t(X_i)\}}{\sum_{i=1}^{n}\mathbb{1}\{Y_i=k\}},\qquad k\in[K]
Hdt_recall(t,OOD):=∑i=1n1{Yi=OOD & ∣ϕt(Xi)∣=0}∑i=1n1{Yi=OOD}\mathrm{Hdt\_recall}(t,\mathrm{OOD}):=\frac{\sum_{i=1}^{n}\mathbb{1}\{Y_i=\mathrm{OOD}\ \&\ |\phi_t(X_i)|=0\}}{\sum_{i=1}^{n}\mathbb{1}\{Y_i=\mathrm{OOD}\}}

Particularly, the first two rows in Table 1 show the extreme cases of recall control on normal classes in each iteration. The third row displays the OOD detection performance. In terms of prediction informativeness, the fourth row reports the prediction set size exclusively on all normal classes while the last row presents the prediction set size on all observations, including those from the OOD class.

Results: For a fair comparison with the BCCP where OOD detection is not particularly targeting, we first set λ=1\lambda= 1 in the risk function L(⋅,⋅)\mathcal{L}(\cdot,\cdot) of BanditGPS, implying that the optimization of the OOD detection performance is not a priority either. The top panel in Figure 3 demonstrates that both BanditGPS and BCCP effectively manage the accumulative class-specific normal recall, as illustrated by the colored dashed curves showing the smallest recall over all normal classes, which approach 1−γ1-\gamma as iterations progress. On the other hand, BanditGPS distinguishes itself from BCCP with superior OOD detection capabilities (solid curves in the top panel) and smaller prediction sets (bottom panel). Further assessment on a holdout labeled dataset (see Figure 4) reinforces BanditGPS’s enhanced performance over BCCP, showcasing its robust and improved OOD detection and informative prediction set. With the full feedback information, metrics in Figure 3 and Figure 4 quickly improve as shown in green curves.

Figure 3. Comparison among methods based on accumulative performance.

Figure 4. Comparison among methods based on performance on the fixed holdout datasets.

Trade-offs between Prediction Set Size and OOD Recall Driven by λ\lambda: The parameter λ\lambda affects the trade-off between metrics on prediction set size and OOD recall. In this section, we study these two metrics by varying the values of λ\lambda, i.e., 0, 0.25, 0.5, 0.75, and 1. As shown in Figure 5 and Figure 6, the smaller the λ\lambda is, the larger the prediction set will be, despite the improvement in the OOD recall.

Figure 5. Trade-off among accumulative metrics when varying the value of λ\lambda.

Figure 6. Trade-off among metrics for the fixed holdout dataset when varying the value of λ\lambda.

Discussions

This work introduces a novel online set-valued prediction framework with out-of-distribution (OOD) detection under bandit feedback. While we provide theoretical guarantees and empirical validation, we acknowledge several modeling assumptions and algorithmic components that deserve further clarification and suggest directions for future work.

First, the theoretical analysis in Theorem 6 relies on Assumption 3, which requires the boundedness of both the importance-weighted estimator Δt,k\Delta_{t,k} and the Lagrange multiplier λt,k\lambda_{t,k}. In practice, Δt,k\Delta_{t,k} depends inversely on the action sampling policy πt(k∣Xt)\pi_t(k \mid X_t). To ensure Δt,k\Delta_{t,k} remains bounded, a simple yet effective solution is to clip the policy from below by a constant pp, which guarantees Δt,k≤max⁡{1/p,1/(1−Kp)}\Delta_{t,k} \leq\max\{1/p, 1/(1-Kp)\}. This design consideration can be naturally incorporated into the algorithm to ensure numerical stability and theoretical validity.

On the other hand, the multiplier λt,k\lambda_{t,k} is dynamically updated to enforce recall constraints for normal classes. While our method adopts a primal-dual approach, its precise theoretical bound is not given in this work. A promising direction is to build upon frameworks from online constrained optimization [48, 47], which offer high-probability or expectation-based bounds for Lagrange multipliers under mild conditions. We plan to incorporate these insights into future extensions of BanditGPS.

Lastly, our current formulation operates in a binary bandit feedback setting, where a single arm is pulled after set-valued prediction. This separates the prediction step (generating a set) from the feedback step (observing a label). An interesting future direction is to unify these steps within a combinatorial bandit framework, where the predicted set itself is treated as the action, and partial or structured feedback is received over the set. Such a generalization could enhance learning efficiency and better reflect real-world applications where multiple predictions are jointly evaluated.

Conclusions

In the high-risk scenarios exacerbated by uncertainties from ambiguous instances and the emergence of new classes in dynamic environments, we introduced BanditGPS, a novel set-valued classification method tailored for online bandit feedback settings. BanditGPS navigates the uncertainties by offering a set of plausible labels for ambiguous instances and an empty label set for an OOD observation. BanditGPS handles the challenge of inaccessible label information inherent in bandit feedback by utilizing an estimation of the ground truth of class labels. Leveraging a primal-dual algorithm, BanditGPS dynamically adjusts tuning parameters in response to its performance history, facilitating an adaptive and automatic risk management mechanism. Furthermore, by enabling the weight between informative prediction and OOD detection, BanditGPS empowers practitioners to tailor the system based on their specific operational requirements. The theoretical and empirical validations of BanditGPS affirm its efficacy in managing the challenges of providing informative predictions while accurately detecting OOD instances under the control of class-specific normal recall.

There are limitations in this initial work that warrant further investigation and improvement. Beyond those discussed in § 6, one promising direction is to integrate BanditGPS with alternative multi-armed bandit strategies that offer theoretical performance guarantees, such as Thompson Sampling or the Upper Confidence Bound algorithm, to further enhance its decision-making capabilities. Additionally, rather than treating all abnormal inputs as belonging to a single super OOD class, adapting BanditGPS to support class-incremental learning could enable more refined discovery and assimilation of newly emerging classes in dynamic environments.

Appendix

Experiments Compute Resources

All experiments are conducted on an NVIDIA P100 GPU with CUDA 11.3. The empirical metrics presented in all figures are computed and averaged over 4 runs, with the shaded regions representing the standard error.

Derive for Normal Recall Control

E[1{fWtk(Xt)≥0}∣Yt=k]≥1−γE[1−1{fWtk(Xt)≥0}−γ∣Yt=k]≤0E[1{fWtk(Xt)<0}−γ∣Yt=k]≤0E[1{Yt=k}⋅(1{fWtk(Xt)<0}−γ)]P[Yt=k]≤0E[1{Yt=k}⋅(1{fWtk(Xt)<0}−γ)]≤0\begin{aligned} \mathbb{E}\left[\mathbb{1}\{f_{\mathcal{W}_t}^{k}(X_t)\ge0\}\mid Y_t=k\right]&\ge1-\gamma\\ \mathbb{E}\left[1-\mathbb{1}\{f_{\mathcal{W}_t}^{k}(X_t)\ge0\}-\gamma\mid Y_t=k\right]&\le0\\ \mathbb{E}\left[\mathbb{1}\{f_{\mathcal{W}_t}^{k}(X_t)<0\}-\gamma\mid Y_t=k\right]&\le0\\ \frac{\mathbb{E}\left[\mathbb{1}\{Y_t=k\}\cdot\left(\mathbb{1}\{f_{\mathcal{W}_t}^{k}(X_t)<0\}-\gamma\right)\right]}{\mathbb{P}[Y_t=k]}&\le0\\ \mathbb{E}\left[\mathbb{1}\{Y_t=k\}\cdot\left(\mathbb{1}\{f_{\mathcal{W}_t}^{k}(X_t)<0\}-\gamma\right)\right]&\le0 \end{aligned}

Proofs

Proof of Theorem 5: From the updating rule eq:8, we have

λt+1,k=[λt,k+η2Δt,kℓ2,γ(fWtk(Xt))]+≥λt,k+η2Δt,kℓ2,γ(fWtk(Xt))⟹∑t=1TΔt,kℓ2,γ(fWtk(Xt))≤1η2∑t=1Tλt+1,k−λt,k≤λT+1,kη2≤Cλη2,\begin{aligned} \lambda_{t+1,k}&=\left[\lambda_{t,k}+\eta_2\Delta_{t,k}\ell_{2,\gamma}\left(f_{\mathcal{W}_t}^{k}(X_t)\right)\right]_{+}\\ &\ge\lambda_{t,k}+\eta_2\Delta_{t,k}\ell_{2,\gamma}\left(f_{\mathcal{W}_t}^{k}(X_t)\right)\\ \Longrightarrow\sum_{t=1}^{T}\Delta_{t,k}\ell_{2,\gamma}\left(f_{\mathcal{W}_t}^{k}(X_t)\right)&\le\frac{1}{\eta_2}\sum_{t=1}^{T}\lambda_{t+1,k}-\lambda_{t,k}\le\frac{\lambda_{T+1,k}}{\eta_2}\le\frac{C_\lambda}{\eta_2}, \end{aligned}

By taking the expectation for both sides of the last inequality, we have

∑t=1TE[Δt,kℓ2,γ(fWtk(Xt))]≤Cλη2\sum_{t=1}^{T}\mathbb{E}\left[\Delta_{t,k}\ell_{2,\gamma}\left(f_{\mathcal{W}_t}^{k}(X_t)\right)\right]\le\frac{C_\lambda}{\eta_2}
⟹∑t=1TE[E[Δt,kℓ2,γ(fWtk(Xt))∣{πs}s<t,{(Xt,Yt)}s≤t,W1]]≤Cλη2\Longrightarrow\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{E}\left[\Delta_{t,k}\ell_{2,\gamma}\left(f_{\mathcal{W}_t}^{k}(X_t)\right)\mid\{\pi_s\}_{s<t},\{(X_t,Y_t)\}_{s\le t},\mathcal{W}^{1}\right]\right]\le\frac{C_\lambda}{\eta_2}
⟹∑t=1TE[1{Yt=k}⋅ℓ2,γ(fWtk(Xt))]≤Cλη2(8)\Longrightarrow\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{1}\{Y_t=k\}\cdot\ell_{2,\gamma}\left(f_{\mathcal{W}_t}^{k}(X_t)\right)\right]\le\frac{C_\lambda}{\eta_2} \tag*{(8)}
⟹∑t=1TE[ℓ2,γ(fWtk(Xt))∣Yt=k]≤Cλη2pk(9)\Longrightarrow\sum_{t=1}^{T}\mathbb{E}\left[\ell_{2,\gamma}\left(f_{\mathcal{W}_t}^{k}(X_t)\right)\mid Y_t=k\right]\le\frac{C_\lambda}{\eta_2p_k} \tag*{(9)}
⟹∑t=1TE[1{fWtk(Xt)<0}−γ∣Yt=k]≤Cλη2pk(10)\Longrightarrow\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{1}\{f_{\mathcal{W}_t}^{k}(X_t)<0\}-\gamma\mid Y_t=k\right]\le\frac{C_\lambda}{\eta_2p_k} \tag*{(10)}
⟹∑t=1TP[fWtk(Xt)<0∣Yt=k]≤Tγ+Cλη2pk,\Longrightarrow\sum_{t=1}^{T}\mathbb{P}\left[f_{\mathcal{W}_t}^{k}(X_t)<0\mid Y_t=k\right]\le T\gamma+\frac{C_\lambda}{\eta_2p_k},

where (9) holds due to the (conditional) unbiased estimator Δt,k\Delta_{t,k}; (10) holds due to the Bayes theorem, and (11) holds due to the substitution with the surrogate hinge loss as mentioned in (6). Therefore, the last inequality concludes

1T∑t=1TP[Yt∈ϕt(Xt)∣Yt=k]≥1−γ−CλTη2pk.\frac{1}{T}\sum_{t=1}^{T}\mathbb{P}\left[Y_t\in\phi_t(X_t)\mid Y_t=k\right]\ge1-\gamma-\frac{C_\lambda}{T\eta_2p_k}.

Our derivation for Theorem 6 highly relies on some commonly used lemmas and propositions in the over-parameterized neural network literature. We skip their proofs to avoid redundancy. We leave their details to the main literature Allen-Zhu et al. [2]; Cao & Gu [7, 8] for the reader’s interest.

Additionally, consider two sequences {an}\{a_n\} and {bn}\{b_n\}. We employ some asymptotic notations as follows: an=O(bn)a_n = O(b_n) if lim sup⁡n→∞∣anbn∣<∞\limsup_{n\to\infty} \left|\frac{a_n}{b_n}\right| < \infty; an=O~(bn)a_n = \widetilde{O}(b_n) to indicate an additional logarithmic factor within O(⋅)O(\cdot); and an=Ω(bn)a_n = \Omega(b_n) if lim inf⁡n→∞∣anbn∣>0\liminf_{n\to\infty} \left|\frac{a_n}{b_n}\right| > 0.

For a fixed instance XtX_t, the neural network can be re-written in the form of matrix products as below:

fW(Xt)=WLDt,L−1WL−1Dt,L−2⋯Dt,lWlDt,l−1⋯Dt,1W1Xt.(11)f_{\mathcal{W}}(X_t) = W_LD_{t,L-1}W_{L-1}D_{t,L-2}\cdots D_{t,l}W_lD_{t,l-1}\cdots D_{t,1}W_1X_t. \tag*{(11)}

We define ht,l:=Dt,lWl−1DL−2⋯Dt,1W1Xth_{t,l} := D_{t,l}W_{l-1}D_{L-2}\cdots D_{t,1}W_1X_t, l∈[L−1]l \in[L-1], where

Dt,l=Diag⁡(1{(Wlht,l−1)1≥0},…,1{(Wlht,l−1)m≥0}).D_{t,l} = \operatorname{Diag}\left(\mathbb{1}\{(W_lh_{t,l-1})_1 \ge0\},\ldots,\mathbb{1}\{(W_lh_{t,l-1})_m \ge0\}\right).

Thus, the gradient can be written as

∇WlfWk(Xt)={ekht,L−1Tif l=L,(ht,l−1ekTWL(∏r=l+1L−1Dt,rWr)Dt,l)Tif l∈[L−1].(12)\nabla_{W_l}f_{\mathcal{W}}^k(X_t) = \begin{cases} e_kh_{t,L-1}^{\mathsf{T}} & \text{if } l=L,\\ \left(h_{t,l-1}e_k^{\mathsf{T}}W_L\left(\prod_{r=l+1}^{L-1}D_{t,r}W_r\right)D_{t,l}\right)^{\mathsf{T}} & \text{if } l\in[L-1]. \end{cases} \tag*{(12)}

where ek∈RKe_k \in\mathbb{R}^K is the column vector with value 1 in kk-th entry and 0 otherwise. When W\mathcal{W} in (11) is particularly set as the initialization W1\mathcal{W}^1, the associated WlW_l, Dt,lD_{t,l} in (11) will be denoted by Wl1W_l^1, Dt,l1D_{t,l}^1 accordingly.

Lemma 7. If K≤O(mLlog⁡(m))K \le O\left(\frac{m}{L\log(m)}\right), with the probability at least 1−exp⁡(−Ω(mω2/3Llog⁡(m)))1-\exp(-\Omega(m\omega^{2/3}L\log(m))) over the randomness of Wl1W_l^1, l∈[L]l\in[L], for any perturbation matrices Wl′′W_l^{\prime\prime}, l∈[L]l\in[L] with ∥Wl′′∥2≤ω=O(L−1.5)\|W_l^{\prime\prime}\|_2 \le\omega= O(L^{-1.5}), any diagonal matrices Dt,l′′∈[−3,3]m×mD_{t,l}^{\prime\prime}\in[-3,3]^{m\times m}, l∈[L−1]l\in[L-1] with at most O(mω2/3L)O(m\omega^{2/3}L) non-zero entries, we have

∥∏l=a+1L(Wl1+Wl′′)(Dt,l−11+Dt,l−1′′)−∏l=a+1LWl1Dt,l−11∥2≤O(ω1/3L2mlog⁡(m)K).\left\|\prod_{l=a+1}^{L}(W_l^1+W_l^{\prime\prime})(D_{t,l-1}^1+D_{t,l-1}^{\prime\prime})-\prod_{l=a+1}^{L}W_l^1D_{t,l-1}^1\right\|_2 \le O\left(\frac{\omega^{1/3}L^2\sqrt{m\log(m)}}{\sqrt{K}}\right).

Proof of Theorem 7:

∥∏l=a+1L(Wl1+Wl′′)(Dt,l−11+Dt,l−1′′)−∏l=a+1LWl1Dt,l−11∥2=∥∑l=aL−1WL1Dt,L−11⋯Wl+11Dt,l′′(Wl1+Wl′′)⋯(Dt,a1+Dt,a′′)−∑l=a+1LWL1Dt,L−11⋯Wl+11Dt,l1Wl′′(Dt,l−11+Dt,l−1′′)(Wl−11+Wl−1′′)⋯(Dt,a1+Dt,a′′)∥2≤∑l=aL−1∥WL1Dt,L−11⋯Wl+11Dt,l1∥2⏟Allen-Zhu et al. (2019, Lemma 7.4(a))⋅∥Dt,l′′∥2∥Dt,l01/1(Wl1+Wl′′)⋯(Dt,a1+Dt,a′′)∥2⏟Allen-Zhu et al. (2019, Lemma 8.6(b))+∑l=a+1L∥WL1⋯Wl+11Dt,l1∥2⏟Allen-Zhu et al. (2019, Lemma 7.4(b))⋅∥Wl′′∥2⋅∥(Dt,l−11+Dt,l−1′′)(Wl−11+Wl−1′′)⋯(Dt,a1+Dt,a′′)∥2⏟Allen-Zhu et al. (2019, Lemma 8.6(b))≤L⋅O(mω2/3Llog⁡(m)K)⋅O(L)+L⋅O(mK)⋅ω⋅O(L)=O(ω1/3L2mlog⁡(m)K)+O(ωL3/2mK)=O(ω1/3L2mlog⁡(m)K),\begin{aligned} &\left\|\prod_{l=a+1}^{L}(W_l^1+W_l^{\prime\prime})(D_{t,l-1}^1+D_{t,l-1}^{\prime\prime})-\prod_{l=a+1}^{L}W_l^1D_{t,l-1}^1\right\|_2\\ &=\left\|\sum_{l=a}^{L-1}W_L^1D_{t,L-1}^1\cdots W_{l+1}^1D_{t,l}^{\prime\prime}(W_l^1+W_l^{\prime\prime})\cdots(D_{t,a}^1+D_{t,a}^{\prime\prime})\right.\\ &\quad\left.-\sum_{l=a+1}^{L}W_L^1D_{t,L-1}^1\cdots W_{l+1}^1D_{t,l}^1W_l^{\prime\prime}(D_{t,l-1}^1+D_{t,l-1}^{\prime\prime})(W_{l-1}^1+W_{l-1}^{\prime\prime})\cdots(D_{t,a}^1+D_{t,a}^{\prime\prime})\right\|_2\\ &\le\sum_{l=a}^{L-1}\underbrace{\|W_L^1D_{t,L-1}^1\cdots W_{l+1}^1D_{t,l}^1\|_2}_{\textit{Allen-Zhu et al. (2019, Lemma 7.4(a))}}\cdot\|D_{t,l}^{\prime\prime}\|_2\underbrace{\|D_{t,l}^0{}^{1/1}(W_l^1+W_l^{\prime\prime})\cdots(D_{t,a}^1+D_{t,a}^{\prime\prime})\|_2}_{\textit{Allen-Zhu et al. (2019, Lemma 8.6(b))}}\\ &\quad+\sum_{l=a+1}^{L}\underbrace{\|W_L^1\cdots W_{l+1}^1D_{t,l}^1\|_2}_{\textit{Allen-Zhu et al. (2019, Lemma 7.4(b))}}\cdot\|W_l^{\prime\prime}\|_2\cdot\underbrace{\|(D_{t,l-1}^1+D_{t,l-1}^{\prime\prime})(W_{l-1}^1+W_{l-1}^{\prime\prime})\cdots(D_{t,a}^1+D_{t,a}^{\prime\prime})\|_2}_{\textit{Allen-Zhu et al. (2019, Lemma 8.6(b))}}\\ &\le L\cdot O\left(\sqrt{\frac{m\omega^{2/3}L\log(m)}{K}}\right)\cdot O(\sqrt{L})+L\cdot O\left(\sqrt{\frac{m}{K}}\right)\cdot\omega\cdot O(\sqrt{L})\\ &=O\left(\frac{\omega^{1/3}L^2\sqrt{m\log(m)}}{\sqrt{K}}\right)+O\left(\omega L^{3/2}\sqrt{\frac{m}{K}}\right)=O\left(\frac{\omega^{1/3}L^2\sqrt{m\log(m)}}{\sqrt{K}}\right), \end{aligned}

where the structure of Dt,l0/1D^{0/1}_{t,l} is same as the one in Allen-Zhu et al. [2]. We direct the reader to the corresponding literature for any interest.

Lemma 8. (Cao & Gu, [7]) If ω≤O(L−9/2[log⁡(m)]−3/2)\omega\le O(L^{-9/2}[\log(m)]^{-3/2}), then with probability at least 1−O(TL)⋅exp⁡(−Ω(mω2/3L))1-O(TL)\cdot\exp(-\Omega(m\omega^{2/3}L)) over W1\mathcal{W}^{1}, for all W,W~∈B(W1,ω)\mathcal{W},\widetilde{\mathcal{W}}\in\mathcal{B}(\mathcal{W}^{1},\omega), t∈[T]t\in[T] and l∈[L−1]l\in[L-1],

∥Dt,l−D~t,l∥0≤O(mω2/3L).\left\|D_{t,l}-\widetilde{D}_{t,l}\right\|_{0}\le O(m\omega^{2/3}L).

We will use Theorems 7 and 8 to prove the below Theorem 9.

Theorem 9. Let B(W1,ω):={W:∥Wl−Wl1∥2≤ω,l∈[L]}\mathcal{B}(\mathcal{W}^{1},\omega):=\{\mathcal{W}:\|\mathbf{W}_{l}-\mathbf{W}^{1}_{l}\|_{2}\le\omega,l\in[L]\} be an ω\omega-neighborhood of the initialization. There exists an absolute constant κ\kappa such that, with probability at least 1−O(TL2)exp⁡(−Ω(mω2/3L))1-O(TL^{2})\exp(-\Omega(m\omega^{2/3}L)) over the randomness of W1\mathcal{W}^{1}, for all t∈[T]t\in[T], and W,W′∈B(W1,ω)\mathcal{W},\mathcal{W}'\in\mathcal{B}(\mathcal{W}^{1},\omega) with ω≤κL−6[log⁡(m)]−3/2\omega\le\kappa L^{-6}[\log(m)]^{-3/2}, it holds uniformly that

∥fW(Xt)−fW~(Xt)−⟨∇W~fW~(Xt),W−W~⟩∥2≤O(ω4/3L3mlog⁡(m)K).\left\|f_{\mathcal{W}}(X_t)-f_{\widetilde{\mathcal{W}}}(X_t)-\left\langle\nabla_{\widetilde{\mathcal{W}}}f_{\widetilde{\mathcal{W}}}(X_t),\mathcal{W}-\widetilde{\mathcal{W}}\right\rangle\right\|_{2} \le O\left(\frac{\omega^{4/3}L^{3}\sqrt{m\log(m)}}{\sqrt{K}}\right).

Proof of Theorem 9: For W,W~∈B(W1,ω):={W:∥Wl−Wl1∥2≤ω,l∈[L]}\mathcal{W},\widetilde{\mathcal{W}}\in\mathcal{B}(\mathcal{W}^{1},\omega):=\{\mathcal{W}:\|\mathbf{W}_{l}-\mathbf{W}^{1}_{l}\|_{2}\le\omega,l\in[L]\}, we have

fW(xt)−fW~(xt)−⟨∇W~fW~(xt),W−W~⟩=WLht,L−1−W~Lh~t,L−1−⟨h~t,L−1,WL−W~L⟩−∑l=1L−1W~L(∏r=l+1L−1D~t,rW~r)D~t,l(Wl−1−W~l−1)h~t,l−1=WL(ht,L−1−h~t,L−1)−∑l=1L−1W~L(∏r=l+1L−1D~t,rW~r)D~t,l(Wl−1−W~l−1)h~t,l−1.\begin{aligned} f_{\mathcal{W}}(x_t)-f_{\widetilde{\mathcal{W}}}(x_t)-\left\langle\nabla_{\widetilde{\mathcal{W}}}f_{\widetilde{\mathcal{W}}}(x_t),\mathcal{W}-\widetilde{\mathcal{W}}\right\rangle =\mathbf{W}_{L}h_{t,L-1}-\widetilde{\mathbf{W}}_{L}\widetilde{h}_{t,L-1}-\left\langle\widetilde{h}_{t,L-1},\mathbf{W}_{L}-\widetilde{\mathbf{W}}_{L}\right\rangle-\sum_{l=1}^{L-1}\widetilde{\mathbf{W}}_{L}\left(\prod_{r=l+1}^{L-1}\widetilde{D}_{t,r}\widetilde{\mathbf{W}}_{r}\right)\widetilde{D}_{t,l}(\mathbf{W}_{l-1}-\widetilde{\mathbf{W}}_{l-1})\widetilde{h}_{t,l-1} \\ &=\mathbf{W}_{L}(h_{t,L-1}-\widetilde{h}_{t,L-1})-\sum_{l=1}^{L-1}\widetilde{\mathbf{W}}_{L}\left(\prod_{r=l+1}^{L-1}\widetilde{D}_{t,r}\widetilde{\mathbf{W}}_{r}\right)\widetilde{D}_{t,l}(\mathbf{W}_{l-1}-\widetilde{\mathbf{W}}_{l-1})\widetilde{h}_{t,l-1}. \end{aligned}

Similar to Claim 11.2 in Allen-Zhu et al. [2], there exists Dt,l′D'_{t,l} such that

h~t,L−1−ht,L−1=∑l=1L−1(∏r=l+1L−1(Dt,r+Dt,r′)Wr)(Dt,l+Dt,l′)(W~l−1−Wl−1)h~t,l−1,\widetilde{h}_{t,L-1}-h_{t,L-1}=\sum_{l=1}^{L-1}\left(\prod_{r=l+1}^{L-1}(D_{t,r}+D'_{t,r})\mathbf{W}_{r}\right)(D_{t,l}+D'_{t,l})(\widetilde{\mathbf{W}}_{l-1}-\mathbf{W}_{l-1})\widetilde{h}_{t,l-1},

where diagonal matrices Dt,l′D'_{t,l}, l∈[L−1]l\in[L-1] has entries [−1,1][-1,1] such that ∥Dt,l′∥0≤O(mω2/3L)\|D'_{t,l}\|_{0}\le O(m\omega^{2/3}L). Therefore,

∥fW(xt)−fW~(xt)−⟨∇W~fW~(xt),W−W~⟩∥2=∥∑l=1L−1(∏r=l+1LWr(Dt,r−1+Dt,r−1′))(Wl−1−W~l−1)h~t,l−1−∑l=1L−1(∏r=l+1LW~rD~t,r−1)(Wl−1−W~l−1)h~t,l−1∥2≤max⁡r∥∏r=l+1LWr(Dt,r−1+Dt,r−1′)−∏r=l+1LW~rD~t,r−1∥2∑l=1L−1∥Wl−1−W~l−1∥2⋅∥h~t,l−1∥2≤O(ω1/3L2mlog⁡(m)K)⋅ωL=O(ω4/3L3mlog⁡(m)K),\begin{aligned} &\left\|f_{\mathcal{W}}(x_t)-f_{\widetilde{\mathcal{W}}}(x_t)-\left\langle\nabla_{\widetilde{\mathcal{W}}}f_{\widetilde{\mathcal{W}}}(x_t),\mathcal{W}-\widetilde{\mathcal{W}}\right\rangle\right\|_{2}\\ &=\left\|\sum_{l=1}^{L-1}\left(\prod_{r=l+1}^{L}\mathbf{W}_{r}(D_{t,r-1}+D'_{t,r-1})\right)(\mathbf{W}_{l-1}-\widetilde{\mathbf{W}}_{l-1})\widetilde{h}_{t,l-1}-\sum_{l=1}^{L-1}\left(\prod_{r=l+1}^{L}\widetilde{\mathbf{W}}_{r}\widetilde{D}_{t,r-1}\right)(\mathbf{W}_{l-1}-\widetilde{\mathbf{W}}_{l-1})\widetilde{h}_{t,l-1}\right\|_{2}\\ &\le\max_{r}\left\|\prod_{r=l+1}^{L}\mathbf{W}_{r}(D_{t,r-1}+D'_{t,r-1})-\prod_{r=l+1}^{L}\widetilde{\mathbf{W}}_{r}\widetilde{D}_{t,r-1}\right\|_{2}\sum_{l=1}^{L-1}\|\mathbf{W}_{l-1}-\widetilde{\mathbf{W}}_{l-1}\|_{2}\cdot\|\widetilde{h}_{t,l-1}\|_{2}\\ &\le O\left(\frac{\omega^{1/3}L^{2}\sqrt{m\log(m)}}{\sqrt{K}}\right)\cdot\omega L =O\left(\frac{\omega^{4/3}L^{3}\sqrt{m\log(m)}}{\sqrt{K}}\right), \end{aligned}

where ① is due to

∥∏r=l+1LWr(Dt,r−1+Dt,r−1′)−∏r=l+1LW~rD~t,r−1∥2≤∥∏r=l+1LWr(Dt,r−1+Dt,r−1′)−∏r=l+1LWr1Dt,r−11∥2+∥∏r=l+1LW~rD~t,r−1−∏r=l+1LWr1Dt,r−11∥2≤O(ω1/3L2mlog⁡(m)K),(13)\begin{aligned} \left\|\prod_{r=l+1}^{L}\mathbf{W}_{r}(D_{t,r-1}+D'_{t,r-1})-\prod_{r=l+1}^{L}\widetilde{\mathbf{W}}_{r}\widetilde{D}_{t,r-1}\right\|_{2} \\ &\le\left\|\prod_{r=l+1}^{L}\mathbf{W}_{r}(D_{t,r-1}+D'_{t,r-1})-\prod_{r=l+1}^{L}\mathbf{W}^{1}_{r}D^{1}_{t,r-1}\right\|_{2}+\left\|\prod_{r=l+1}^{L}\widetilde{\mathbf{W}}_{r}\widetilde{D}_{t,r-1}-\prod_{r=l+1}^{L}\mathbf{W}^{1}_{r}D^{1}_{t,r-1}\right\|_{2} \\ &\le O\left(\frac{\omega^{1/3}L^{2}\sqrt{m\log(m)}}{\sqrt{K}}\right), \tag*{(13)} \end{aligned}

where ② is due to where ② holds by using Theorem 7. This is because W~,W∈B(W1,ω)\widetilde{W}, W \in\mathcal{B}(W^{1}, \omega). By Theorem 8, we have ∥D~t,r−1−Dt,r−11∥0≤O(mω2/3L)\lVert\widetilde{D}_{t,r-1} - D^{1}_{t,r-1}\rVert_{0} \le O(m\omega^{2/3}L) and ∥Dt,r−1−Dt,r−11∥0≤O(mω2/3L)\lVert D_{t,r-1} - D^{1}_{t,r-1}\rVert_{0} \le O(m\omega^{2/3}L). Hence ∥Dt,r−1+Dt,r−1′−Dt,r−11∥0≤∥Dt,r−1−Dt,r−11∥0+∥Dt,r−1′∥0≤O(mω2/3L)\lVert D_{t,r-1} + D'_{t,r-1} - D^{1}_{t,r-1}\rVert_{0} \le\lVert D_{t,r-1} - D^{1}_{t,r-1}\rVert_{0} + \lVert D'_{t,r-1}\rVert_{0} \le O(m\omega^{2/3}L) for any r∈[L−1]r \in[L-1].

The below Theorem 10 is directly derived based on Theorem 9 by utilizing the convexity and Lipschitzness of a given function ℓ\ell. This proposition implies ℓ\ell is near convex with respect to the neural network parameter WW, although the neural network is not convex.

Proposition 10. Let the ℓ:RK→R\ell:\mathbb{R}^{K}\to\mathbb{R} be a convex and cc-Lipschitz function. There exists an absolute constant κ\kappa such that, with probability at least 1−O(TL2)exp⁡(−Ω(mω2/3L))1-O(TL^{2})\exp(-\Omega(m\omega^{2/3}L)) over the randomness of W1W^{1}, for all t∈[T]t\in[T], and W,W′∈B(W1,ω)W,W'\in\mathcal{B}(W^{1},\omega) with ω≤κL−6[log⁡(m)]−3/2\omega\le\kappa L^{-6}[\log(m)]^{-3/2}, it holds uniformly that

ℓ(fW′(Xt))−ℓ(fW(Xt))≤⟨∇Wℓ(fW′(Xt)),W′−W⟩+O(cω4/3L3mlog⁡(m)K).\ell(f_{W'}(X_t))-\ell(f_W(X_t))\le\langle\nabla_W\ell(f_{W'}(X_t)),W'-W\rangle+O\left(\frac{c\omega^{4/3}L^3\sqrt{m\log(m)}}{\sqrt{K}}\right).

Proof of Theorem 10:

ℓ(fW′(Xt))−ℓ(fW(Xt))≤−ℓ′(fW′(Xt))T(fW(Xt)−fW′(Xt))b/c ℓ is convex=−ℓ′(fW′(Xt))T(fW(Xt)−fW′(Xt)−⟨∇WfW′(Xt),W−W′⟩)+ℓ′(fW′(Xt))T⟨∇WfW′(Xt),W′−W⟩≤O(cω4/3L3mlog⁡(m)K)+⟨∇Wℓ(fW′(Xt)),W′−W⟩.(14)\begin{aligned} \ell(f_{W'}(X_t))-\ell(f_W(X_t)) &\le-\ell'(f_{W'}(X_t))^{\mathsf{T}}(f_W(X_t)-f_{W'}(X_t)) && \text{b/c }\ell\text{ is convex}\\ &=-\ell'(f_{W'}(X_t))^{\mathsf{T}}\left(f_W(X_t)-f_{W'}(X_t)-\langle\nabla_W f_{W'}(X_t),W-W'\rangle\right)\\ &\quad+\ell'(f_{W'}(X_t))^{\mathsf{T}}\langle\nabla_W f_{W'}(X_t),W'-W\rangle\\ &\le O\left(\frac{c\omega^{4/3}L^3\sqrt{m\log(m)}}{\sqrt{K}}\right)+\langle\nabla_W\ell(f_{W'}(X_t)),W'-W\rangle. \tag*{(14)} \end{aligned}

where the last inequality holds due to the Lipschitzness of ℓ(⋅)\ell(\cdot) and the usage of Theorem 9.

The below Theorem 11 shows the boundness for the gradient of the neural network with respect to the parameters WW.

Theorem 11. There exists an absolute constant κ\kappa such that, with probability at least 1−O(TL2)exp⁡(−Ω(mω2/3L))1-O(TL^{2})\exp(-\Omega(m\omega^{2/3}L)) over the randomness of W1W^{1}, for all t∈[T]t\in[T], l∈[L]l\in[L], and W∈B(W1,ω)W\in\mathcal{B}(W^{1},\omega) with ω≤κL−6[log⁡(m)]−3\omega\le\kappa L^{-6}[\log(m)]^{-3}, it holds uniformly that ∥∇WfW(Xt)∥2=O(K1/2ω1/3L5/2mlog⁡(m))≤O(LKm)\lVert\nabla_W f_W(X_t)\rVert_{2}=O(K^{1/2}\omega^{1/3}L^{5/2}\sqrt{m\log(m)})\le O(\sqrt{LKm}).

Proof of Theorem 11: This theorem is adapted from Cao & Gu [7]. From Equation (12) we have

∥∇WLfW(xt)∥22=∑k=1K∥∇WLfWk(xt)∥22=∑k=1K∥ekht,L−1T∥22=O(K),\lVert\nabla_{W_L}f_W(x_t)\rVert_{2}^{2}=\sum_{k=1}^{K}\lVert\nabla_{W_L}f_W^{k}(x_t)\rVert_{2}^{2}=\sum_{k=1}^{K}\lVert e_k h_{t,L-1}^{\mathsf{T}}\rVert_{2}^{2}=O(K),

and for ℓ∈[L−1]\ell\in[L-1],

∥∇WlfW(xt)∥2=∑k=1K∥ht,l−1ek⊤WL(∏r=l+1L−1Dt,rWr)Dt,l∥2≤∑k=1K∥ht,l−1∥2⋅∥ek⊤WL(∏r=l+1L−1Dt,rWr)Dt,l∥2≤∑k=1KO(1)⋅∥∏r=l+1LWrDt,r−1∥2≤O(K)⋅∥∏r=l+1LWrDt,r−1∥2≤O(K)⋅[∥∏r=l+1LWrDt,r−1−∏r=l+1LWr1Dt,r−11∥2+∥∏r=l+1LWr1Dt,r−11∥2]≤O(K)⋅[O(ω1/3L2mlog⁡(m)K)+O(mω2/3Llog⁡(m)K)]=O(K1/2ω1/3L2mlog⁡(m))≤O(Km),(15)\begin{aligned} \lVert\nabla_{\mathbf{W}_{l}}f_{\mathbf{W}}(\mathbf{x}_{t})\rVert_{2} &=\sum_{k=1}^{K}\lVert\mathbf{h}_{t,l-1}\mathbf{e}_{k}^{\top}\mathbf{W}_{L}\left(\prod_{r=l+1}^{L-1}\mathbf{D}_{t,r}\mathbf{W}_{r}\right)\mathbf{D}_{t,l}\rVert_{2}\\ &\leq\sum_{k=1}^{K}\lVert\mathbf{h}_{t,l-1}\rVert_{2}\cdot\left\lVert\mathbf{e}_{k}^{\top}\mathbf{W}_{L}\left(\prod_{r=l+1}^{L-1}\mathbf{D}_{t,r}\mathbf{W}_{r}\right)\mathbf{D}_{t,l}\right\rVert_{2}\\ &\leq\sum_{k=1}^{K}\mathcal{O}(1)\cdot\left\lVert\prod_{r=l+1}^{L}\mathbf{W}_{r}\mathbf{D}_{t,r-1}\right\rVert_{2}\\ &\leq\mathcal{O}(K)\cdot\left\lVert\prod_{r=l+1}^{L}\mathbf{W}_{r}\mathbf{D}_{t,r-1}\right\rVert_{2}\\ &\leq\mathcal{O}(K)\cdot\left[\left\lVert\prod_{r=l+1}^{L}\mathbf{W}_{r}\mathbf{D}_{t,r-1}-\prod_{r=l+1}^{L}\mathbf{W}_{r}^{1}\mathbf{D}_{t,r-1}^{1}\right\rVert_{2}+\left\lVert\prod_{r=l+1}^{L}\mathbf{W}_{r}^{1}\mathbf{D}_{t,r-1}^{1}\right\rVert_{2}\right]\\ &\leq\mathcal{O}(K)\cdot\left[\mathcal{O}\left(\frac{\omega^{1/3}L^{2}\sqrt{m\log(m)}}{\sqrt{K}}\right)+\mathcal{O}\left(\sqrt{\frac{m\omega^{2/3}L\log(m)}{K}}\right)\right]\\ &=\mathcal{O}\left(K^{1/2}\omega^{1/3}L^{2}\sqrt{m\log(m)}\right)\leq\mathcal{O}\left(\sqrt{Km}\right), \tag*{(15)} \end{aligned}

where (15) holds due to Theorem 7 and Lemma 7.4(a) in Allen-Zhu et al. [2], and the last equality holds due to the upper bound of ω\omega. Consequently,

∥∇WfW(Xt)∥2=O(K1/2ω1/3L5/2mlog⁡(m))≤O(LKm).(16)\lVert\nabla_{\mathbf{W}}f_{\mathbf{W}}(\mathbf{X}_{t})\rVert_{2}=\mathcal{O}\left(K^{1/2}\omega^{1/3}L^{5/2}\sqrt{m\log(m)}\right)\leq\mathcal{O}\left(\sqrt{LKm}\right). \tag*{(16)}

□\square

Proof of Theorem 6: Note that the hinge loss ℓ1\ell_{1} is a convex 1-Lipschitz function. It is clear to see that ℓ(u)\ell(\mathbf{u}) is convex with respect to u∈RK\mathbf{u}\in\mathbb{R}^{K}. To show its Lipschitzness, take u,u~∈RK\mathbf{u},\tilde{\mathbf{u}}\in\mathbb{R}^{K}. Thus,

∣ℓ(u)−ℓ(u~)∣=∣λK∑k=1K(ℓ1(uk)−ℓ1(u~k))+(1−λ)(ℓ1(max⁡k∈[K]uk)−ℓ1(max⁡k∈[K]u~k))∣≤λK∣∑k=1K(ℓ1(uk)−ℓ1(u~k))∣+(1−λ)∣max⁡k∈[K](uk−u~k)∣≤λK∥u−u~∥2+(1−λ)∥u−u~∥2=(λK+1−λ)∥u−u~∥2\begin{aligned} \lvert\ell(\mathbf{u})-\ell(\tilde{\mathbf{u}})\rvert &=\left\lvert\frac{\lambda}{K}\sum_{k=1}^{K}\left(\ell_{1}(u_{k})-\ell_{1}(\tilde{u}_{k})\right)+(1-\lambda)\left(\ell_{1}\left(\max_{k\in[K]}u_{k}\right)-\ell_{1}\left(\max_{k\in[K]}\tilde{u}_{k}\right)\right)\right\rvert\\ &\leq\frac{\lambda}{K}\left\lvert\sum_{k=1}^{K}\left(\ell_{1}(u_{k})-\ell_{1}(\tilde{u}_{k})\right)\right\rvert+(1-\lambda)\left\lvert\max_{k\in[K]}(u_{k}-\tilde{u}_{k})\right\rvert\\ &\leq\frac{\lambda}{\sqrt{K}}\lVert\mathbf{u}-\tilde{\mathbf{u}}\rVert_{2}+(1-\lambda)\lVert\mathbf{u}-\tilde{\mathbf{u}}\rVert_{2}\\ &=\left(\frac{\lambda}{\sqrt{K}}+1-\lambda\right)\lVert\mathbf{u}-\tilde{\mathbf{u}}\rVert_{2} \end{aligned}

implies ℓ(⋅)\ell(\cdot) is a function with Lipschitz constant λK+1−λ\frac{\lambda}{\sqrt{K}}+1-\lambda, and hence ∥ℓ′(u)∥2≤λK+1−λ\lVert\ell'(\mathbf{u})\rVert_{2}\leq\frac{\lambda}{\sqrt{K}}+1-\lambda. Additionally, assume λt,k≤Cλ,Δt,k≤CΔ\lambda_{t,k}\leq C_{\lambda},\Delta_{t,k}\leq C_{\Delta} for all t∈[T],k∈[K]t\in[T],k\in[K], thus L(X;W)\mathcal{L}(\mathbf{X};\mathbf{W}) is Lipschitz mapping with respect to fW(X)f_{\mathbf{W}}(\mathbf{X}) with Lipschitz constant λK+1−λ+KCλCΔ\frac{\lambda}{\sqrt{K}}+1-\lambda+\sqrt{K}C_{\lambda}C_{\Delta}.

Recall the risk function then can be rewritten as

ℓ(fWt(Xt))+∑k=1Kλt,k⋅Δt,kℓ2,γ(fWt(Xt)),\ell(f_{\mathbf{W}^{t}}(\mathbf{X}_{t}))+\sum_{k=1}^{K}\lambda_{t,k}\cdot\Delta_{t,k}\ell_{2,\gamma}(f_{\mathbf{W}^{t}}(\mathbf{X}_{t})),

and the updating rule is

Wt+1=Wt−η1[∇Wℓ(fWt(Xt))+∑k=1Kλt,kΔt,k∇Wℓ2,γ(fWtk(xt))].\mathcal{W}^{t+1}=\mathcal{W}^{t}-\eta_{1}\left[\nabla_{\mathcal{W}}\ell(f_{\mathcal{W}^{t}}(X_{t}))+\sum_{k=1}^{K}\lambda_{t,k}\Delta_{t,k}\nabla_{\mathcal{W}}\ell_{2,\gamma}(f_{\mathcal{W}^{t}}^{k}(x_{t}))\right].

For notation simplicity, substitute ω\omega in the first term of (14) as Rm\frac{R}{\sqrt{m}} and let

ν=O((λ/K+1−λ)R4/3L3log⁡(m)m1/6K).\nu=\mathcal{O}\left(\frac{(\lambda/\sqrt{K}+1-\lambda)R^{4/3}L^{3}\sqrt{\log(m)}}{m^{1/6}\sqrt{K}}\right).

Therefore, for W∗∈B(W1,Rm)\mathcal{W}^{*}\in B(\mathcal{W}^{1},\frac{R}{\sqrt{m}}), we have ∥W∗−W1∥2≤rLm\|\mathcal{W}^{*}-\mathcal{W}^{1}\|_{2}\leq\frac{r\sqrt{L}}{\sqrt{m}}, and

1T∑t=1Tℓ(fWt(xt))−1T∑t=1Tℓ(fW∗(xt))≤1T∑t=1T⟨∇Wℓ(fWt(xt)),Wt−W∗⟩+νb/c of Theorem 10≤1η1T∑t=1T⟨Wt−Wt+1,Wt−W∗⟩+1T∑t=1T∑k=1K⟨λt,kΔt,k∇Wℓ2,γ(fWtk(xt)),W∗−Wt⟩+ν≤12η1T∑t=1T(∥Wt−Wt+1∥22+∥Wt−W∗∥22−∥Wt+1−W∗∥22)+1T∑t=1T∑k=1K⟨λt,kΔt,k∇Wℓ2,γ(fWtk(xt)),W∗−Wt⟩+ν≤η122η1(λK+1−λ+KCλCΔ)2⋅O(KLm)+ω2L2η1T+1T∑t=1TCλCΔ⋅∣ℓ2,γ′(⋅)∣K⋅∥∇WtfWt(Xt)∥2⋅Lω+ν≤η12(λK+1−λ+KCλCΔ)2⋅O(KLm)+ω2L2η1T+CλCΔ⋅O(KLω⋅K1/2ω1/3L5/2mlog⁡(m))+ν≤(λK+1−λ+KCλCΔ)2⋅O(η12KLm)+LR22η1Tm+CλCΔ⋅O(KL3R4/3log⁡(m)m1/6)+O((λ/K+1−λ)R4/3L3log⁡(m)m1/6K),\begin{aligned} \frac{1}{T}\sum_{t=1}^{T}\ell(f_{\mathcal{W}^{t}}(x_{t}))-\frac{1}{T}\sum_{t=1}^{T}\ell(f_{\mathcal{W}^{*}}(x_{t})) &\leq\frac{1}{T}\sum_{t=1}^{T}\langle\nabla_{\mathcal{W}}\ell(f_{\mathcal{W}^{t}}(x_{t})),\mathcal{W}^{t}-\mathcal{W}^{*}\rangle+\nu &&\text{b/c of Theorem 10}\\ &\leq\frac{1}{\eta_{1}T}\sum_{t=1}^{T}\langle\mathcal{W}^{t}-\mathcal{W}^{t+1},\mathcal{W}^{t}-\mathcal{W}^{*}\rangle\\ &\quad+\frac{1}{T}\sum_{t=1}^{T}\sum_{k=1}^{K}\langle\lambda_{t,k}\Delta_{t,k}\nabla_{\mathcal{W}}\ell_{2,\gamma}(f_{\mathcal{W}^{t}}^{k}(x_{t})),\mathcal{W}^{*}-\mathcal{W}^{t}\rangle+\nu\\ &\leq\frac{1}{2\eta_{1}T}\sum_{t=1}^{T}\left(\|\mathcal{W}^{t}-\mathcal{W}^{t+1}\|_{2}^{2}+\|\mathcal{W}^{t}-\mathcal{W}^{*}\|_{2}^{2}-\|\mathcal{W}^{t+1}-\mathcal{W}^{*}\|_{2}^{2}\right)\\ &\quad+\frac{1}{T}\sum_{t=1}^{T}\sum_{k=1}^{K}\langle\lambda_{t,k}\Delta_{t,k}\nabla_{\mathcal{W}}\ell_{2,\gamma}(f_{\mathcal{W}^{t}}^{k}(x_{t})),\mathcal{W}^{*}-\mathcal{W}^{t}\rangle+\nu\\ &\leq\frac{\eta_{1}^{2}}{2\eta_{1}}\left(\frac{\lambda}{\sqrt{K}}+1-\lambda+\sqrt{K}C_{\lambda}C_{\Delta}\right)^{2}\cdot\mathcal{O}(KLm)+\frac{\omega^{2}L}{2\eta_{1}T}\\ &\quad+\frac{1}{T}\sum_{t=1}^{T}C_{\lambda}C_{\Delta}\cdot|\ell'_{2,\gamma}(\cdot)|\sqrt{K}\cdot\|\nabla_{\mathcal{W}^{t}}f_{\mathcal{W}^{t}}(X_{t})\|_{2}\cdot\sqrt{L\omega}+\nu\\ &\leq\frac{\eta_{1}}{2}\left(\frac{\lambda}{\sqrt{K}}+1-\lambda+\sqrt{K}C_{\lambda}C_{\Delta}\right)^{2}\cdot\mathcal{O}(KLm)+\frac{\omega^{2}L}{2\eta_{1}T}\\ &\quad+C_{\lambda}C_{\Delta}\cdot\mathcal{O}\left(\sqrt{KL\omega}\cdot K^{1/2}\omega^{1/3}L^{5/2}\sqrt{m\log(m)}\right)+\nu\\ &\leq\left(\frac{\lambda}{\sqrt{K}}+1-\lambda+\sqrt{K}C_{\lambda}C_{\Delta}\right)^{2}\cdot\mathcal{O}\left(\frac{\eta_{1}}{2}KLm\right)+\frac{LR^{2}}{2\eta_{1}Tm}\\ &\quad+C_{\lambda}C_{\Delta}\cdot\mathcal{O}\left(\frac{KL^{3}R^{4/3}\sqrt{\log(m)}}{m^{1/6}}\right)+\mathcal{O}\left(\frac{(\lambda/\sqrt{K}+1-\lambda)R^{4/3}L^{3}\sqrt{\log(m)}}{m^{1/6}\sqrt{K}}\right), \end{aligned}

where the last inequality is due to telescoping sum, Theorem 10, and the below fact

∥Wt−Wt+1∥22=η12∥∇WL(Xt,Wt)∥22≤η12∥∇fWt(Xt)L(Xt,Wt)∥22⋅∥∇WtfWt(Xt)∥22≤η12⋅(λK+1−λ+KCλCΔ)2⋅O(Kω2/3L5mlog⁡(m)).(17)\begin{aligned} \|\mathcal{W}^{t}-\mathcal{W}^{t+1}\|_{2}^{2} &=\eta_{1}^{2}\|\nabla_{\mathcal{W}}\mathcal{L}(X_{t},\mathcal{W}^{t})\|_{2}^{2}\\ &\leq\eta_{1}^{2}\|\nabla_{f_{\mathcal{W}^{t}}(X_{t})}\mathcal{L}(X_{t},\mathcal{W}^{t})\|_{2}^{2}\cdot\|\nabla_{\mathcal{W}^{t}}f_{\mathcal{W}^{t}}(X_{t})\|_{2}^{2}\\ &\leq\eta_{1}^{2}\cdot\left(\frac{\lambda}{\sqrt{K}}+1-\lambda+\sqrt{K}C_{\lambda}C_{\Delta}\right)^{2}\cdot\mathcal{O}\left(K\omega^{2/3}L^{5}m\log(m)\right). \tag*{(17)} \end{aligned}

where (17) holds due to the Lipschitzness of the function L(Xt;Wt)\mathcal{L}(X_{t};\mathcal{W}^{t}) with respect to fWt(Xt)f_{\mathcal{W}^{t}}(X_{t}) and the usage of (16).

Thus, by setting a constant c∗:=(λK+1−λ+KCλCΔ)2+λK+1−λK+KCλCΔc^* := \left(\frac{\lambda}{\sqrt{K}} + 1-\lambda+ \sqrt{K}C_\lambda C_\Delta\right)^2 + \frac{\lambda}{K} + \frac{1-\lambda}{\sqrt{K}} + KC_\lambda C_\Delta and choosing η1=RKTm\eta_1 = \frac{R}{\sqrt{KTm}}, we have

1T∑t=1Tℓ(fWt(Xt))−1T∑t=1Tℓ(fW∗(Xt))≤c∗O(LRKT+L3R4/3log⁡(m)m1/6).\frac{1}{T}\sum_{t=1}^{T}\ell(f_{W_t}(X_t))-\frac{1}{T}\sum_{t=1}^{T}\ell(f_{W_*}(X_t))\leq c^*\mathcal{O}\left(\frac{LR\sqrt{K}}{\sqrt{T}}+\frac{L^3R^{4/3}\sqrt{\log(m)}}{m^{1/6}}\right).

References

  1. [1]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
  2. [2]Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In International Conference on Machine Learning, pp. 242–252. PMLR, 2019.
  3. [3]Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=eNdiU_Dbm9.arxiv.org/abs/2009.14193
  4. [4]Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235–256, 2002.DOI
  5. [5]Peter L Bartlett and Marten H Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 9(Aug):1823–1840, 2008.DOI
  6. [6]Abhijit Bendale and Terrance E Boult. Towards open set deep networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1563–1572, 2016.arxiv.org/abs/1511.06233
  7. [7]Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1905.13210
  8. [8]Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning over-parameterized deep relu networks. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3349–3356, 2020.arxiv.org/abs/1902.01384
  9. [9]Jun Cen, Di Luan, Shiwei Zhang, Yixuan Pei, Yingya Zhang, Deli Zhao, Shaojie Shen, and Qifeng Chen. The devil is in the wrongly-classified samples: Towards unified open-set recognition. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=xLrO1_xYGAs.arxiv.org/abs/2302.04002
  10. [10]Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classification with rejection based on cost-sensitive classification. In International Conference on Machine Learning, pp. 1507–1517. PMLR, 2021.arxiv.org/abs/2010.11748
  11. [11]Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Posterior network: Uncertainty estimation without ood samples via density-based pseudo-counts. Advances in Neural Information Processing Systems, 33:1356–1367, 2020.arxiv.org/abs/2006.09239
  12. [12]Xinyi Chen, Edgar Minasyan, Jason D Lee, and Elad Hazan. Regret guarantees for online deep control. In Learning for Dynamics and Control Conference, pp. 1032–1045. PMLR, 2023.
  13. [13]Koby Crammer and Claudio Gentile. Multiclass classification with bandit feedback using adaptive regularization. Machine learning, 90(3):347–383, 2013.DOI
  14. [14]Christophe Denis and Mohamed Hebiri. Confidence sets with expected sizes for multiclass classification. The Journal of Machine Learning Research, 18(1):3571–3598, 2017.arxiv.org/abs/1608.08783
  15. [15]Christophe Denis and Mohamed Hebiri. Consistency of plug-in confidence sets for classification in semi-supervised learning. Journal of Nonparametric Statistics, 32(1):42–72, 2020.arxiv.org/abs/1507.07235
  16. [16]Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=S1eK3i09YQ.arxiv.org/abs/1810.02054
  17. [17]Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Leme, and Jon Schneider. Contextual recommendations and low-regret cutting-plane algorithms. Advances in Neural Information Processing Systems, 34:22498–22508, 2021.arxiv.org/abs/2106.04819
  18. [18]Leving 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.DOI
  19. [19]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.arxiv.org/abs/1512.03385
  20. [20]Yotam Hechtlinger, Barnabás Póczos, and Larry Wasserman. Cautious deep learning. arXiv preprint arXiv:1805.09460, 2018.arxiv.org/abs/1805.09460
  21. [21]Radu Herbei and Marten H Wegkamp. Classification with reject option. The Canadian Journal of Statistics/La Revue Canadienne de Statistique, pp. 709–721, 2006.DOI
  22. [22]Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal thompson sampling. In International Conference on Machine Learning, pp. 5074–5083. PMLR, 2021.
  23. [23]Sham M Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. Efficient bandit algorithms for online multiclass prediction. In Proceedings of the 25th international conference on Machine learning, pp. 440–447, 2008.
  24. [24]Jihyo Kim, Jin Koo, and Sangheum Hwang. A unified benchmark for the unknown detection capability of deep neural networks. Expert Systems with Applications, 229:120461, 2023.
  25. [25]Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4–22, 1985.DOI
  26. [26]Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
  27. [27]Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581–3591, 2020.arxiv.org/abs/2006.02544
  28. [28]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.
  29. [29]Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.arxiv.org/abs/0706.3188
  30. [30]Samuel Stanton, Wesley Maddox, and Andrew Gordon Wilson. Bayesian optimization with conformal prediction sets. In International Conference on Artificial Intelligence and Statistics, pp. 959–986. PMLR, 2023.arxiv.org/abs/2210.12496
  31. [31]Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
  32. [32]Muhammad Faaiz Taufiq, Jean-Francois Ton, Rob Cornish, Yee Whye Teh, and Arnaud Doucet. Conformal off-policy prediction in contextual bandits. Advances in Neural Information Processing Systems, 35: 31512–31524, 2022.
  33. [33]William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285–294, 1933.
  34. [34]Dirk van der Hoeven, Federico Fusco, and Nicolò Cesa-Bianchi. Beyond bandit feedback in online multiclass classification. Advances in neural information processing systems, 34:13280–13291, 2021.
  35. [35]Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
  36. [36]Vladimir Vovk, Ilia Nouretdinov, Valentina Fedorova, Ivan Petej, and Alex Gammerman. Criteria of efficiency for set-valued classification. Annals of Mathematics and Artificial Intelligence, 81(1):21–46, 2017.
  37. [37]Shijun Wang, Rong Jin, and Hamed Valizadegan. A potential-based framework for online multi-class learning with partial feedback. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 900–907. JMLR Workshop and Conference Proceedings, 2010.
  38. [38]Wenbo Wang and Xingye Qiao. Learning confidence sets using support vector machines. Advances in Neural Information Processing Systems, 31, 2018.arxiv.org/abs/1809.10818
  39. [39]Wenbo Wang and Xingye Qiao. Set-valued support vector machine with bounded error rates. Journal of the American Statistical Association, pp. 1–13, 2022a.DOI
  40. [40]Zhou Wang and Xingye Qiao. Learning acceptance regions for many classes with anomaly detection. arXiv preprint arXiv:2209.09963, 2022b.arxiv.org/abs/2209.09963
  41. [41]Zhou Wang and Xingye Qiao. Set-valued classification with out-of-distribution detection for many classes. Journal of Machine Learning Research, 24(375):1–39, 2023.
  42. [42]Zhou Wang and Xingye Qiao. Deep generalized prediction set classifier and its theoretical guarantees. Transactions on Machine Learning Research, 2024a.
  43. [43]Zhou Wang and Xingye Qiao. Efficient online set-valued classification with bandit feedback. In International Conference on Machine Learning, pp. 51328–51347. PMLR, 2024b.arxiv.org/abs/2405.04393
  44. [44]Guoxuan Xia and Christos-Savvas Bouganis. Augmenting softmax information for selective classification with out-of-distribution data. In Proceedings of the Asian Conference on Computer Vision, pp. 1995–2012, 2022.
  45. [45]Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=xnYACQquaGV.
  46. [46]Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey. arXiv preprint arXiv:2110.11334, 2021.arxiv.org/abs/2110.11334
  47. [47]Hao Yu and Michael J Neely. A low complexity algorithm with O(√T) regret and O(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1): 1–24, 2020.
  48. [48]Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.
  49. [49]Chong Zhang, Wenbo Wang, and Xingye Qiao. On reject and refine options in multicategory classification. Journal of the American Statistical Association, 113(522):730–745, 2018.
  50. [50]Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=tkAtoZkcUnm.arxiv.org/abs/2010.00827
  51. [51]Yingying Zhang, Chengchun Shi, and Shikai Luo. Conformal off-policy prediction. In International Conference on Artificial Intelligence and Statistics, pp. 2751–2768. PMLR, 2023.arxiv.org/abs/2206.06711
  52. [52]Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 11492–11502. PMLR, 2020.
  53. [53]Fei Zhu, Zhen Cheng, Xu-Yao Zhang, and Cheng-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.

Paper details

vlnc:W_8g9jryam
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents