Learning to Help in Multi-Class Settings
Authors: Yu Wu
Yansong Li
Zeyu Dong
Nitya Sathyavageeswaran
Anand D. Sarwate
Venue: ICLR 2025 Poster (2025)
Keywords: learning with abstention
learning with reject option
learning to defer
classification
Primary area: learning theory
TL;DR: We extend the Learning to Help, which is the reverse problem of Learning to Defer, to multi-class classification for both synchronous and asynchronous settings.

Abstract: Deploying complex machine learning models on resource-constrained devices is challenging due to limited computational power, memory, and model retrainability. To address these limitations, a hybrid system can be established by augmenting the local model with a server-side model, where samples are selectively deferred by a *rejector* and then sent to the server for processing. The hybrid system enables efficient use of computational resources while minimizing the overhead associated with server usage. The recently proposed Learning to Help (L2H) model proposed training a server model given a fixed local (client) model. This differs from the Learning to Defer (L2D) framework which trains the client for a fixed (expert) server. In both L2D and L2H, the training includes learning a rejector at the client to determine when to query the server. In this work, we extend the L2H model from binary to multi-class classification problems and demonstrate its applicability in a number of different scenarios of practical interest in which access to the server may be limited by cost, availability, or policy. We derive a stage-switching surrogate loss function that is differentiable, convex, and consistent with the Bayes rule corresponding to the 0-1 loss for the L2H model. Experiments show that our proposed methods offer an efficient and practical solution for multi-class classification in resource-constrained environments.

Published as a conference paper at ICLR 2025
LEARNING TO HELP IN MULTI-CLASS SETTINGS
Yu Win, Yansong Lit=, Zeyu Dong"=, Nitya Sathyavageeswaran", Anand D. Sarwate &Rutgers University, &University of Illinois Chicago, "Stony Brook University
ABSTRACT
Deploying complex machine learning models resource-constrained devices is challenging due to limited computational power, memory, and model retrainabil- ity. To address these limitations, hybrid system can be established by augment- ing the local model with a server-side model, where samples are selectively de- ferred by rejector and then sent to the server for processing. The hybrid system enables efficient use of computational resources while minimizing the overhead associated with server usage. The recently proposed Learning Help (L2H) model proposed training server model given a fixed local (client) model. This differs from the Learning to Defer (I.2ID) framework which trains the client for a fixed (expert) server. In both L2D and L2H, the training includes learning a rejec- tor at the client to determine when to query the server. In this work, we extend the L2H model from binary multi-class classification problems and demonstrate its applicability in a number of different scenarios of practical interest in which access the server may be limited by cost, availability, policy. We derive a stage-switching surrogate loss function that is differentiable, convex, and consis- tent with the Bayes rule corresponding to the 0-1 loss for the L2H model. Experi- ments show that our proposed methods offer an efficient and practical solution for multi-class classification in resource-constrainee environments. ?
INTRODUCTION
Machine Learning (ML) models deployed local devices often face significant limitations in terms of computational resources and retrainability. Local devices are typically constrained by limited processing power, memory, and battery life (Ajani al., 2021; Biglari & Tang, 2023), which can impede the model's ability to handle large-scale data or perform complex computations in real-time. Furthermore, once local model is deployed, it may be difficult to retrain update (Hanzlik al., 2021), leading to a potential degradation in performance over time when data distribution drifts (Lu al., 2019).
To address these issues, one strategy is to augment the local machine learning system (a "client") with an external model hosted on a remote server. This approach, seen in recent applications like Apple Intelligence (Gunter et al., 2024), enhances the overall system performance by leveraging the server's superior computational power and capacity for model updates. Recent studies have shown that efficient fine-tuning methods, like few-shot learning (Brown et al., 2020) and efffcietr-efficient fine-tuning (Fu et al., 2023), can achieve competitive performance, making it a feasible choice for server-side model deployment. Those methods utilize the pre-trained model's capabilities while requiring minimal computational resources, allowing for easy and cost-effective updates to adapt to specific tasks or data distributions. Consequently, it enables the deployment of powerful models servers without the high costs of comprehensive model training.
While training server model can be relatively inexpensive, extensive use of server-side models can be costly due to data transfer, latency, instability connection, and service fees. Moreover, server operators may wish limit the frequency of offloaded inferences from clients by imposing costs
"Corresponding author: anand. sa sarwatef rutgers. wenttgers.edu. edu; "Equal contribution This material is based upon work supported by the US National Science Foundation under grant CNS- 21 188 104 and is supported in part by funds from federal agency and industry partners specified in the Resilient & Intelligent NextG Systems (RINGS) program.

---

Published as a conference paper at ICLR 2025
access constraints. In the presence of such restrictions, the practical solution for clients use rejector that selectively defers/offloads only the most challenging and uncertain samples to the server for processing, thereby optimizing the balance between usage cost and performance. Informally, the rejector is defined as a decision function to either select the local model or server model for a sample (a rigorous definition is given in Sec. 2).
framework for training a rejector and server model given fixed "legacy" device-boune model was recently proposed for binary classification models under the name "Learning to Help" (L2H) (Wu & Sarwate, 2024). In this work, we extend and generalize this framework to encompass a variety of problems of more practical interest. We can identify several scenarios that can arise in the context of building ML systems in those settings with a fixed local model. In particular, we demonstrate how to handle various restrictions on the use of the server:
PAY-PER- PEO-REE (PPR): the device must pay a cost each time the rejector defers to the server; as an example, the server can be thought of as consultant who offers their services at a cost.
INTERMITTENT AVAILABILITY (IA): in the PPR model, the rejection rule must also ac- count for the server being potentially unavailable; for example, this can occur when the internet connection is unstable, or the server is busy servicing requests of other devices.
BOUNDED REJECT RATE (BRR): instead of PPR, the rate of rejections/deferrals per unit time may not exceed predefined upper limit; for example, there is limit the usage of some LLMs even with a paid subscription.
The L2H model is natural complement to prior works two-party decision systems, includ- ing Learning with Abstention (LWA) and Learning to Defer (L2D). These models either assume that rejected samples can be discarded at fixed cost that the server is pre-trained "expert" and optimize decision rules for the device/rejector. As ML/AI decision systems become integrated into physical devices and infrastructure, issues of sustainability will require newer server systems to sup- port pre-existing legacy models which can allow only partial retraining. Relatively little attention has been given to this scenario: we address the extreme case where only the rejection rule can be updated with the server.
Existing work (Wu & Sarwate, 2024) on the L2H model only studies binary classification in the PPR model. In this work, we further extend the L2H framework to multi-class problems and show how to train systems under the three scenarios mentioned above. More specifically, we propose generalized (non-differentiable) 0-1 loss to measure the prediction system's 's performance and find the Bayes rule for this loss. We then provide surrogate loss function which convex and differentiable and show that its minimizer is consistent with the Bayes rule for the generalized 0-1 loss.
We then design algorithms which can optimize rules for training multi-class predictors in the three "post-hoc" method
scenarios mentioned earlier: PPR, IA, and BRR. To guarantee BRR to control the rejection rate. We show experimentally that incorporating a server model with a rejector enhances the overall performance of the ML system in all three scenarios. Training with our surrogate loss function, the rejector helps in identifying the challenging and uncertain samples, while balancing the accuracy and usage of the server model.
RELATED WORKS
Hybrid ML systems. The hybrid ML systems that consist of client side and server side, have been of substantial research in many fields, including federated learning (Zhang et al., 2021: McMa- han et al., 2017), distributed learning (Cao et al., 2023a; Horváth et al., 2023), and decentralized learning (Sun al., 2022; Fang et al., 2022; Liu al., 2024; Li & Han, 2023). However, those frameworks only focus on interaction between different sides during the training process. Once the training done, no more communication is needed among them. In this work, we are interested in the collaboration between client and server both in the training and inference phases.
Learning with Abstention (LWA). The foundational work that first considered extra options for recognition tasks was proposed by Chow (1957) and Chow (1970). Herbei & Wegkamp (2006) visit the framework in classification tasks and propose a score-based reject method. Subsequent works extend this framework to different types of classifiers (Rigollet, 2007; Wegkamp, 2007;
2

---

Published as a conference paper at ICLR 2025
Bartlett & Wegkamp, 2008; Wegkamp & Yuan, 2011). Cortes al. (2016) consider a separate function to make reject decisions in binary classification. Zhu & Nowak (2022b;a) introduce the reject option in active learning. Cortes et al. (2018) add abstention to online learning. Zhang et al. (2024) consider the rejection rule when the data distribution contains noisy labels. Yin et al. (2024) use rejection for ensuring faimess, Mao al. (2024d) and Mao et al. (2024c) analyze the theoretical bounds and algorithms for score-based and predictor-rejector-bssss methods, respectively.
Unlike the setting where rejection incurs an extra cost, few works focus on scenarios with no extra cost for rejection, but the reject rate is bounded. Pietraszek (2005) construct the rejection rule using ROC analysis. Denis & Hebiri (2020) derive the Bayes optimal classifier for the bounded reject rate setting. Shekhar et al. (2020) consider binary classification with bounded reject rates in the active learning setting. In LWA, although there are works that can identify data samples that are uncertain or challenging for the local model to predict, the subsequent action is merely to discard those samples without providing an answer. While this framework can indeed improve prediction accuracy, the system still cannot handle the samples that are challenging for the local model.
Learning to Defer (L2D). Building upon LWA, Madras et al. (2018) were the first to consider subsequent expert can process the rejected samples. Raghu et al. (2019) consider binary classifi- cation with expert deferral using uncertainty estimators. Mozannar & Sontag (2020a) propose the first method that jointly trains the local model and rejector in multi-class classification. Verma & Nalisnick (2022); Mozannar et al. (2023); Hemmer et al. (2023); Cao et al. (2023b) propose differ- ent surrogate loss functions for L2D. Okati et al. (2021) and Narasimhan et al. (2022) add post-hoc algorithms to the cases where the reject decision incurs extra cost.
Seeking help from multiple experts has been explored in different machine learning models (Ker- rigan et al., 2021; Keswani et al., 2021; Corvelo Benz & Gomez Rodriguez, 2022; Hemmer al., 2022). Verma et al. (2022) extend the pee-vs-all-parametrrre Mao al. (2023) study a two-stage scenario for L2D with experss. Mozannar et al. (2023) provide a tinear-rrogrammen
L2D to the multiple experts case.
formulation that optimally solve L2D in the linear setting. Verma al. (2023) incorporate a conformal inference technique for multiple experts. Tailor al. (2024) formulate L.2D system that can cope with never-before-seen experts. Mao et al. (2024b) introduce regression with deferral to multiple experts. Mao et al. (2024a) present theoretical study of sur- rogate losses and algorithms for L2D with multiple experts. L2D complements the missing part of LWA; that is, after a reject decision, instead of being discarded, samples are sent to remote experts for predictions. However, in L2D, the experts on the server side are assumed to be either human or well-trained ML models, which are fixed during the training process. L,D focuses on training the local model and the rejector under the existence of expert models. This framework cannot handle the cases described in Sec. 1, where local models are legacy systems that have been deployed to the client side, and retraining the local models is not available.
Learning to Help (L2HI). Learning to Help (L2H) (Wu & Sarwate, 2024) is complementary model to L2D whose aim is to train a server model and rejector to enhance the usability of systems containing a "legacy" local ML model that unavailable for updating or retraining. The prior work focused on binary classification in the PPR setting and proposes a surrogate loss function that requires model calibration. This cannot be directly extended to multi-class problems due to issues with differentiabillty. In this work we generalize this model to multi-class problems and more scenarios (see Appendix A for a comparison).
2 PROBLEM FORMULATION
We consider decision system with two parties: a client and the server. We consider the client a device with relatively limited computational power while the server has access to more comput- ing resources. We study multi-class problem in which the goal is to learn prediction func- tion f: X + y, where X' C TR! is a space of instances/feature vectors with / dimensions and y = [ A (1,2,..., K} is a set of labels.
The L2H decision system (See Fig. 1) is constrained have certain architecture: in operation, the client receives an input x and has two options: it can either make a prediction Meacl locally on the client forward the input ("defer") x the remote server which produces a response Gremote
3

---

Published as a conference paper at ICLR 2025
Client
Server
rejector
RAMOTS
server
Frmmokn
LOCAL
client classifier
Mhocol
Trainch
Food Part
Figure 1: Diagram of learning help framework.
We can represent this system by a tuple of functions (r(x), (m(x)){(=)) where the client side has reject function r(z) and prediction function m(z) and the server has prediction function e(x).
The function r(x) makes binary choice representing the client's choice to use from those two options and then lets either m(x) e(x) make prediction for
We assume that the training algorithm has access to training set {(r,, : [n]] of n feature- label pairs in X' x y. For the purposes of analysis make the standard assumption (Vapnik, 2010; Shalev-Shwe Shwaar-S & Ben-David, 2014) that random variables feature vector X and label Y are sampled independently and identically distributed (i.i.d.) according to unknown distribution D.
The function r: - {LOCAL, REMOTE), known as the rejection rule or rejector, determines whether the client should label the input locally send it to the remote server for labeling. Formally,
if r(x) = LOCAL, the client uses the local classifier m(x) to provide label. Conversely, r(x) REMOTE, , the client forwards sample to the server, which then labels the input using remote classifier e(z).
For the functions r(x), m(x), and e(z), there are four possible outcomes for a given sample (r,z). y). The first event occurs when r(r) = LOCAL and m(x) = representing correct decision by the client. The second event when r(x)
LOCAL and m(x) + indicate an error by the client. The third event occurs when r(z) = REMOTE and e(x) = y representing a correct decision by the server. The fourth event is when r(x) = REMOTE and e(x) o y. indicate an error by the server. We define the costs associated with each of these outcomes as Cor Cor, Cse respectively. For the scenarios discussed in Sec. 1, our goal is to provide accurate predictions, satisfying Goe Cce and Cac Cse well as instant predictions, satisfying Gee < Cac and Gue I Cae Based on four outcomes and corresponding costs, the general loss function of this two- side framework given sample v) is defined as:
and
L(T, e, I, v, = Gee ( Coo -coe4mla))
+ (c
Coo (o
where I(] is the indicator function. The expected loss, also known as risk, is defined as R(r, m, E) Exx,y)>> e, m)]. The Bayes Classifiers then defined as: T m e e arg minl, m. R(r, m, e). Jointly training all three functions is trivial because the Bayes classifiers arg max, (K()), where
satisfy m = =eB
nx(x)) P(y
represents the regression function for i-th class. The proof is similar with Proposition 2 derived by Mozannar & Sontag (2020b). Since the Bayes client classifier equals the Bayes server classifier, together with the cost constraints stated above, we have BB((z) = LOCAL, for all æ. No input will be sent to the server.
Since jointly training three functions leads to a trivial solution, we focus on a constrained still interesting case, learning to help (I.2H), where the client classifier cannot be updated or retrained (Fig. 1). While the prior work on 1.HH only considers binary classification, this paper we extend the approach to multi-class problems.
2.1 GENERALIZED 0-1 LOSS FOR MULTI-CLASS CLASSIFICATION
To extend L2H to multi-class classification, we consider a special case of the general loss function (equation 1), often referred to the generalized 0-1 loss in binary classification for 1.2H. In the

---

Published as a conference paper at ICLR 2025
generalized 0-1 loss, the parameters defined follows: Cee = 0, Cce 1, Cac = Ce and Cse = Ce + C1 The idea behind this setup is that there is no cost when the local prediction is correct, but a cost of 1 is incurred when the local prediction is incorrect Therefore, we set Ccc. O and Cze = 1. Additionally, recall the interesting settings we mentioned in Sec. I; requesting assistance from remote server is not free. Once sample is sent to the server, constant reject cost Ce is incurred, regardless of the server's prediction. Therefore, Csc = Ce Furthermore, if the server prediction is incorrect, an additional penalty inaccuracy cost с₁ imposed account for the mistake. It is important to note that C1 may be greater than I, especially in critical scenarios such as medical diagnoses, where expert misdiagnoses can lead to more severe consequences. As a result, we set Csc- + Ci In summary, the generalized 0-1 loss for multi-class classification for L2H defined as:
Ligeneral (T, 2, Ammt))ty
+ Co (c)) 1 (e)= + ((=++
As discussed previously, we assume that m(x) is fixed while jointly training r(z) and e(x). The risk of equation is defined as Rgeneral Exx,y) (r, e, 2, y; m)] and the Bayes Classi- fiers for muuli--laas L2H is defined as:
e E arg min Rgeneral e; m).
(4)
ne
The existence of these two Bayes classifiers will be proved in the next subsection.
2.2 BAYES OPTIMAL REJECTOR AND SERVER CLASSIFIER
In this subsection, we derive the Bayes classifiers as defined in equation for both rejector and server classifier with a fixed client classifier m(x) under generalized 0- loss function in equation 3. As mentioned at the beginning of Sec. 2, the task we considered is multi-class classification. The client classifier m(x) and server classifier e(x² are multi-class classifiers with output be one label among K classes. The rejector r(z) is a binary classifier with two possible labels: LOCAL and REMOTE, which means either making a prediction on the client or on the server. The rejector r(x) will give a label LOCAL to z if r(z) > 0 and give label REMOTE to r when r(x) < 0. Without loss of generality, we assume that for the Bayes classifier of rejector, r (((x)= E [+1.-1].
As discussed after equation 3, we consider the case where the client classifier m is given and fixed during training. The output of the client classifier depends on input sample x, which can either be deterministic or stochastic, depending on the machine learning model of m. We formally consider the case where the client classifiers consist of K sub-functions, say (x), m2(x).
m (z)] The i i-th sub-function mx(x) represents the score for i-th class on sample æ. Then the prediction of client classifier is arg max; mz(z). For simplicity, we assume that arg max, m, (x) is unique. Choosing the class that has the highest output score prediction is standard operation for multi- class classification. In the following analysis, we assume that the output of client a random variable M conditioned the input (Neal, 2012).
Theorem 2.1. Given a client classifier m(x), the solutions of Bayes classifiers (defined in equa- tion 4) for generalized 0- 1 loss under the space of all measurable functions are:
e =arg arrgmax max 7j (2),
(5)
where vi(x)) is defined in equation 2 and
r 1 (m) (1 - Ce c1) (a))) 2 1,
(6)
where jxx) A arg max, (x)...
The proof is given in Appendix C. By Theorem 2.1, we find that the Bayes classifier for the servers eB is the same the Bayes classifier for single classifiers (right side of equation 5). Also, the Bayes classifier for rejector B compares the posterior risk (expected loss) for two different decisions: predicting on the client classifier or predicting on the server classifier. The function ())(() the regression function for class predicted by client classifier m(x), while max; na(x:) is the regression
5

---

Published as a conference paper at ICLR 2025
function of the class predicted by server classifier. A larger value of the regression function tends to pull a sample to the classifier corresponding to the (x(z) because the regression function here means how likely that sample belongs to the class predicted either by m(z) or e e²(x). If we write the right-hand side of the inequality inside the indicator (from equation 6) in another form:
Ge (1 max; ()))) it's clear that larger ce and eı would impede reject decision. This result coincides with the intuition in scenarios we are interested in: if inquiring servers are likely to be more costly, we tend finish tasks without asking for help
(1 Ce a)) + e₁ max; (x())
too often.
However, we cannot directly get the Bayes classifiers (e",r"²) in real-world tasks. To see this, in reality, we don't 't have the knowledge of the distribution D of the data set. Furthermore, we cannot approach the Bayes optimal classifiers through gradient-based methods because the generalized 0- 1 loss (equation 3) is not differentiable since it contains variables in the indicator function. To solve this problem, we propose a surrogate loss function in Sec. 3. We show that the surrogate loss function is differentiable and convex, and optimal solutions of this surrogate loss function are consistent with the Bayes optimal classifiers.
STAGE-SWITCHING SURROGATE LOSS FUNCTION
In Sec. 2.2, the Bayes classifiers we derived minimize the risk of generalized 0- 1 loss (equation 3). Since the distribution of the data set is unknown and the loss function is not differentiable, it's computationally intractable get (e". by solving equation 4. Another potential concern comes from the framework of the client-server system. In this system, the rejector is placed on the client side while the server classifier is placed on the server side, which requires synchronous updates between two sides while searching for the solution of the problem equation 4. In scenarios where the connection between the client and server is unstable, or bandwidth is limited as discussed in Sec. continuously synchronizing the client and server during training becomes costly. These conditions necessitate that both the rejector and server classifier be capable of being trained in an asynchronous setting.
Similar with the definition of client classifier m(x) in Sec. 2.2, we consider the case where server classifier e(x:) also consists of K sub-functions, denoted as (x),, (x)))ee(()))))))))))) ez(x)) ... ex [x)]- The pre- diction of the server classifier is arg max, (x()) and assumed to be unique. We further consider the case that the rejector consists of sub-functions, say [r1 (I),, r2()], where ri stands for the score of LOCAL while r2 stands for the score of REMOTE. In accordance with the space of rB as stated in Sec. 2.2, the output of the rejector is defined as r(z) A 1(r1 > r2(x)] 2 - 1. Based on the definitions stated above, we propose a stage-switching surrogate loss function, which is differentiable and can be used in both synchronous and asynchronous settings. The surrogate loss function is defined as:
Ls(r,e,2,3;,) = (e, + e,,
where
Li(e,z,0) = In expley(x))
(8)
ΣØ= exp(e,(x))
and
L,(r,e,,,y,m) -(1 - ce - - +clo())))) In exp(ra(x))
(9)
exp(r2(x)) exp(ri(x))
(xp(r(())
mm(+)=y In exp(r2(z)) cxx((r(x)))
Similarly, the surrogate risk is defined as
Rs
(Ix.))D([ss(r,ee e, m)).
(10)
The surrogate loss function is designed as the summation of two sub-loss functions, Li and L2 In the training process, we iteratively update the rejector or the server classifier while keeping the other
Minimizing Rs now becomes an additive composite optimization problem (Boyd et al., 2011; He & Yuan, 2012; Nesterov, 2013; Li & Han, 2022).

---

Published as a conference paper at ICLR 2025
fixed under each sub-loss function at stage. Specifically, in server stage, update the param- eters of the server classifier under the sub-loss function L1 while keeping the rejector unchanged, and in rejector stage, update the parameters of rejector r under sub-loss function L2 while keeping server classifier unchanged. The way of switching stages depends on specific synchronous asynchronous settings. Notice that the client classifier m(x) is always fixed in all stages in the L2H framework. Detailed comparison with previous surrogate loss function for binary L2H is in Appendix A and comparison with direct extensions from other proposed surrogate loss functions in LWA and L2D is attached in Appendix B. The results show that previous works can not fully cover the settings that we are interested in.
Based on the stage-switching training method, the surrogate loss function is differentiable in all stages. the server stage, the sub-surrogate loss function I, is the same as the cross-entropy loss function. In the rejector stage, for each given input sample with true label y. the indicator [e(x==y and [e(e]=y are constants, that is, either one or zero. either case, L2 is differentiable since only the 71 and r2 are variables in this stage, and we can calculate the gradient with respect to ri and T22 What's s more, both L1 and L2 are convex w.r.t. e as shown in the following subsection.
3.1 CONVEXITY AND MONOTONICITY OF THE SURROGATE LOSS FUNCTION
In the following proposition, we show that in both stages, the sub-surrogate loss function L and L2 are both convex or monotone.
Proposition 3.1. For each given (I. y). , the loss function I, is convex over forr any E [K]; and the loss function L2 is:
convex over (2) and r2(x), when ce - c1 + +cileyy > 0;
monotonically decreasing over T1 and monotonically increasing over when Ci + cileyy S 0.
The proof is given in Appendix D. The convexity of a function ensures that we can find the global minimizer through gradient-related optimization methods (Boyd & Vandenberghe, 2004; Nesterov, 2014). As for the monotonicity of L2 when - Ce C1 + Ci 1 le=y 2 O, we will show that in Theorem 3.2, this property can help for solving the corner case in the proof. Based on differentia- bility, convexity, or monotonicity, we prove in Sec. 3.2 that our proposed surrogate loss function is consistent, that is, any minimizer of the surrogate risk (equation 10) also minimizes the generalized 0-1 1 risk of equation 3, referring the consistency defined in Section 2.2 by Cao et al. (2023b).
3.2
CONSISTENCY OF SURROGATE LOSS FUNCTION
In this subsection, we verify the consistency between the surrogate loss function (equation 7) and the generalized 0-1 loss function (equation 3). Formally, we prove the following theorem:
Theorem 3.2. Under the space of all measurable functions, the surrogate loss function (equation 7) consistent with the generalized 0- loss function (equation 3), that is, the minimizer of the risk of surrogate loss function also minimizes the risk of original loss function:
r e E arg min Rgenerat (r, e,m),
for all r*, r*,e" e* E arg min, Rs(r, m)
The proof is given in Appendix E. As shown in Theorem 3.2, the function spaces for server classifier and rejector are both spaces of all measurable functions; training our model with this stage- switching surrogate loss function would eventually lead to Bayes classifiers, which is the global optimal solution.
In summary, we propose a stage-switching surrogate loss function, which differentiable, convex, or monotone, and theoretically prove that this surrogate loss function is consistent. Based on those properties our surrogate loss function, practical optimization methods can be conducted to derive the empirical minimizer of surrogate risk Rs, defined in equation 10, with finite number of data samples in world scenarios. In the next section, we propose computationally feasible algorithms for different settings PPR, IA, and BRR discussed in Sec. 1.
7

---

Published as a conference paper at ICLR 2025
4 COMPUTATIONALLY FEASIBLE ALGORITHMS FOR LEARNING TO HELP
The stage-switching Surrogate loss function that we propose in equation 7 ensures the usability of gradient-based optimization methods to train the rejector and server classifiers with flexibility in three settings we discuss in Section 1: PPR, IA, and BRR settings.
The training the server stage is the same for all three settings since L, is only function of the server classifier; no knowledge of the rejector or client classifier is needed. In the rejector stage, we set up different algorithms based on the constraints different settings. Besides, for BRR settings, propose post-hoc Algo. 4 and 5 after standard training. Since the stage-switching surrogate loss function is differentiable, any gradient-basel optimization method can used for training our model. To reduce the computation, use Stochastic Gradient Descent (SGD) for presentation.
(PPR) Recall the scenarios we depict in Section 1, in the PPR setting, we con- sider that the client is always connected with the server; that is, the rejector has instant access to the latest version of server classifier e(x) during the whole training phase. This setting works for scenarios where the connection in real-time, and the bandwidth ample and free during training, but each request conducts payment.
We design synchronized algorithm, Algo. 1, that works for the PPR setting. The algorithm itera- tively runs in the server stage, and in the rejector stage for each pair of samples and labels (2, y) In the server stage, the server classifier e(x:) is updated by the sub-loss T4 In the rejector stage, the current e(xx is instantly shared with the rejector. Together with the outputs of the fixed client classifier and current server classifier, the sub-loss L2 is calculated to update the rejector.
Algorithm Optimization With Our Surrogate Loss Function
Input: Training set {(r,, yi) : E [n]] Fixed client classifier m. Rejector r0, Sever classifier e", Constant cost C1 and Ce.
1: for t == to do
2: L (Z), = -n E, (xp((e
(xx,
3:
e' + SGD(LL Wr), (e),
4:
mmx))= In axp(r (1 Ce a +
exp (r.
exp (x2(e)))))
C1 (m:)==)))))) In exp (oxp((a))))
5:
(xt, r¹ + (2 rz-1)
6: end for
7: return r" en
Intermittent Availability (IA) In the IA setting, the connection between the client and the server is not always available. This scenario may happen in any distributed system that is connected to the public network because of traffic control. Also in private networks, connection may be lost due to instability of the network. If we still train our model with synchronized algorithm 1, the training process will be postponed once the connection delayed or lost. Holding the status of both the rejector and server classifier will cause a waste of resources and time.
surrogate loss funetion in equation consists of two sub-loss functions. asynchronized algorithm is best to tackle those issues. The idea is separately train the server clas- sifier with L1 on the server side and train the rejector with L2 while keeping a temporary version of the server classifier e the client side. The e- will be updated only when the intermittent connection between client and server is built. Considering that the client and server only connect every S time slot we propose the asynchronized training algorithm in Algo. 2. In line 4 of Algo. 2, the server connects with the client and sends the current server classifier e as the latest e In line 5, calculate the La loss with stored server classifier
Our
Bounded-RRject-RRin (BRR) While few works focus the BRR setting in L2D and L2H frameworks, the setting is indeed realistic. For example, subscribers of ChatGPT or other Al as- sistants don't pay extra money for each inquiry to advanced models, but they are allowed only
8

---

Published as a conference paper at ICLR 2025
Algorithm 2 Asynchronous Optimization With Our Surrogate Loss Function
Input: Training set {(z;, yt) i E [m]} Fixed client classifier m, Rejector r Sever classifier e", Constant cost C1 and Ce. Synchronization interval S,,
for 1 to do
2: (1), = In E, (e,())
exp(ey, (a)))
3: e SGD(L) 3/b) e
4:
if mod S then e t e' end
5:
(2(,,, Va)
-(1
exp (rs(aa)) Ce a + a1 (11-(())=m)) In exp exp (exp(()))))
1m(z))= In exp (ra (w:))
(xp(ri(z)))
6: r'+ (CD(L2 F4, Ub), Tt-1)
7: end for
8: return 1" en
ohr/1 10
dbr10 (o 1.251
SVHN 11
SWH (c) 1.251
4.2
Acurasy
007
5.70
0,93
Regict Rade
rifer10 Iry 10
rife20 (ry 3.25)
GVNNi 11
SWMNN (ry 1.25)
2.8
6.6
0.03
2.4
0.23
0.4
0.2
0.0
5.2
56
0.2
2.4
Figure 2: Impact of ce nad 61 on accuracy and reject rate. First row: change of accuracy reject changes; Second row: change of reject rate as reject cost ce changes.
ask an assigned number of questions each hour during peak hours. In this setting, we consider that making reject decision and sending samples to the server is free, but the number of samples that can be sent to the server in units of time, i.e., reject rate, has a fixed upper bound q. There are two concerns in this setting: a) the rejector should actively pick up the samples that have higher accu- racy on the server classifier compared to the client classifier; b) the actual reject rate the inference phase should be bounded.
To address the concerns stated above, we propose stochastic post-hoe algorithms in Algo. 3, 4, and 5. These algorithms sample random variables to decide either sending extra samples to server when empirical reject rate lower than upper bound q or keep a portion rejected samples locally when it's higher than upper bound q. By conducting this stochastic post-hoc algorithm, ensure the bounded reject rate while making the best use of server classifier. The detailed discussions and algorithms in Appendix F.
EXPERIMENT
In this section, we test the proposed surrogate loss function in equation and algorithms for different settings CIFAR-10 (Krizhevsky & Hinton, 2009), SVHN (Netzer et al., 2011). and CIFAR- 100 (Krizhevsky & Hinton, 2009) datasets.
In experiments, the base network structure for the client classifier and the rejector is LeNet-5, and the server classifier is either AlexNet or ViT. The client classifier trained solely and works as fixed model in the following process. Since Algo. 1 is the basic algorithm for multi-class L.2H framework, we start from the evaluation for the PPR setting,
Trade-off accuracy and reject rate on reject cost and inaccuracy cost this experiment, we evaluate the impact of reject cost ea and inaccuracy cost e₁ the overall accuracy and reject rate,

---

Published as a conference paper at ICLR 2025
Table 1: Contrastive Evaluation Results with 1.25 and c. 0.25
cifar10 (%)
SVHN (%)
ratio
differ.
ratio
differ.
data with r(z) LOCAL
44.11
73.9
81.9
8.0
91.71
90.6
93.3
2.7
data with r(z) = REMOTE
55.9
54.5
67.7
13.2
8.29
61.2
72.8
11.6
SVHN
cifar10
3x 10
Synchronous
2.6
Synchronccus
5 100
2.4x10'
100
5 1000
- 1000
[0]
x101
1.8x 10
2x
1.6x
1:00
Step
Step
Figure 3: Comparison of the training loss for different synchronized settings.
respectively. Specifically, we choose Ce from an interval between [0, 0.5] with fixed inaccuracy costs = and = 1.25. From Fig. 2 we see that, incorporating server classifier indeed helps increase the overall accuracy, while both the cost of rejection and inaccuracy on the server will balance the usage of the client classifier and server classifier.
Contrastive evaluation over client and server classifiers To see what the rejector Iearns train- ing and how it works in the inference phase, conduct contrastive evaluation, where in the inference phase, we split the testing set into a rejected subset and non-rejected subset, according to the output of r(x). We test the accuracy of the rejected and non-rejected subset on both the client classifier mxx) and the server classifier e(x). The result is shown in Table 1, which implies that the rejector mostly only sends the samples that predicted inaccurately on m(x) while predicted
more accurately on e(x) to the server end. Column "ratio" indicates the percentage of samples over dataset have the same r(x). For different C, and C1 the results are similar as shown in Appendix G.
Convergence rate comparison over synchronization and asynchronization We compare the convergence rate and accuracy with models trained by Algo. for PPR and that trained by Algo. compared Table I with Table
for IA. The accuracy performances are similar in both algorithms, in Appendix G. This result coincides with the comparison in Fig. 3, where a larger synchronization interval S causes slower convergence rate but converges to the same level of loss. The experiment results are in line with our expectation since the minimizers of our surrogate loss function derived Theorem 3.2, are independent specific optimization algorithms.
Experiments for stochastic post-hoc Algorithm 3, 4, and 5, its comparison with randomly reject under BRR settings, experiments on CIFAR-100 with server classifier to be VIT, together with other additional experiment materials, are in Appendix G.
6 CONCLUSION
In this paper, we extend the Learning to Help framework to address multi-class classification with different resource constraints: PAY-PER-REQUEST INTERMITTENT AVAILABILITY, and BOUNDED REJECT RATE. By introducing a stage-switching surrogate loss function, we enabled effective training of both the server-side classifier and the rejector with computationally feasible al- gorithms for three settings. Our experimental results demonstrate that the proposed methods offer a practical and efficient solution for multi-class classification, aligning with the theoretical guar- antees we established. This work opens new opportunities for further exploration of multi-party collaboration hybrid machine learning systems, especially the era LLM.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Taiwo Samuel Ajani, Agbotiname Lucky Imoize, and Aderemi A. Atayero. An overview of ma- chine learning within embedded and mobile optiiias-ss and applications. Sensors, (13), 2021. ISSN 1424-8220. doi: 10.3390/S21334112, URL https: http:/wwwmmpccc mdpi. com/
1424 2tt1///22//1111///////
Peter Bartlett and Marten H. Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 9:1823-1840, June 2008. ISSN 1532-4435.
Amin Biglari and Wei Tang. A review of embedded machine learning based hardware, appli- cation, and sensing scheme. Sensors, 23(4), 2023. ISSN 1424-8220. doi: 10.3390/s230421311.
URL https: /wwww mdpi com / /142411444424 wctmm/1444-22//233/3333333
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine Learning, 3(1):1-122 2011. ISSN 1935-8237. doi: 00.1561/2200000066 URL http://t///.. www.xdo...ooooo wwo.i.org/oooo 10. 1561/11661 220000000000.....
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NeurIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 978 9781713829546
Xuanyu Cao, Tamer Başar, Suhas Diggavi, Yonina C. Eldar, Khaled B. Letaief, H. Vincent Poor, and Junshan Zhang. Communication-efficeen distributed learning: An overview. IEEE Journal on Selected Areas in Communications, (4):851 -873, 2023a. doi: 10. 109/SSAC.222233227771
Yuzhou Cao, Hussein Mozannar, Lei Feng. Hongxin Wei, and Bo An. In defense of soft- max parametrization for calibrated and consistent learning to defer. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 38485-38503. Curran Associates, Inc., 2023b. URL
ngs neurips httppss.cc/pppppe htappprr_fflesppppereeeeee www.rrrrinnnnnnneeeeooeee Paper wwweeer-Cofeeenee..mm pdf.
C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970. doi: 10.1109//TT.1990.10444000
C. Chow. An optimum character recognition system using decision functions. IRE Transactions Electronic Computers, EC-6(4):247-254, December 1957. ISSN 0367-9950. doi: 10.1109/ 1EC.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles (eds.). Algorithmmic Learning The- ory, pp. 67-82, Cham, 2016. Springer International Publishing. ISBN 978-3-319- doi: 10.
46379-7.
URL htttps://di.... http:///c.oooo/..1111// 1000//
978- 118833319--6333 46374-77777-1
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp- 1059-1067. PMLR, 10-15 Jul 2018. URL https: /tte::/pprocee proceedo ngs. . ml walr.press/vel
cortes18a html.
Nina L. Corvelo Benz and Manuel Gomez Rodriguez. Counterfactual inference of second opinions. In James Cussens and Kun Zhang (eds.), Proceedings of the Thirty-Eighti Conference on Uncer- tainty in Artificial Intelligence, volume 180 of Proceedings Machine Learning Research, pp-
11

---

Published as a conference paper at ICLR 2025
453-463. PMLR, 01-05 Aug 2022. URL http:s::pppccedd..g......eeeeeee corvelo-benz22 html.
Thomas M Cover and Joy A Thomas. Elements of Information Theory. John Wiley & Sons, 2nd edi- tion, 2005. doi: 10.1002/047 00000471448822 74882XX. URL hwt.tttts////o..ooooooo 101.1000000000000001111111
Christophe Denis and Mohamed Hebiri. Consistency of plug-in confidence sets for classification in semi-supervised learning. Journal of Nonparametric Statistics, 322122, January 2020. ISSN 1048-5252. doi: 10.1080110485252.2000 2019.1689241.
Cheng Fang, Zhixiong Yang, and Waheed U. Bajwa. BRIDGE: Syzannine-Resiliee Decentralized Gradient Descent. IEEE Transactions on Signal and Information Processing over Networks, 8: 610-626, 2022. ISSN 2373-776X. doi: 10. (0.0///SIN.2022..188888
Zihao Fu, Haoran Yang, Anthony Man-Cho So, Wai Lam, Lidong Bing, and Nigel Collier. On the the effectiveness of parameter-efficient fine-tuning. Proceedings the AAAI Conference on Artificial Intelligence, ((((1))11799-288800 June 2023. ISSN 2374-3468. doi: (0.1669/aaii.v33 v37il 1.26555.
Tom Gunter, Zirui Wang, Chong Wang, Ruoming Pang. Andy Narayanan, Aonan Zhang, Bowen Zhang, Chen Chen, Chung- Chiu, David Qiu, Deepak Gopinath, Dian Ang Yap, Dong Yin, Feng Nan, Floris Weers. Guoli Yin. Haoshuo Huang. Jianyu Wang. Jiarui Lu, John Pee- bles, Ke Ye, Mark Lee, Nan Du, Qibin Chen, Quentin Keunebroek, Sam Wiseman, Syd Evans, Tao Lei, Vivek Rathod, Xiang Kong, Xianzhi Du, Yanghao Li, Yongqiang Wang. Yuan Gao, Zaid Ahmed, Zhaoyang Xu. Zhiyun Lu, Al Rashid, Albin Madappally Jose, Alec Doane, Alfredo Bencomo, Allison Vanderby, Andrew Hansen, Ankur Jain, Anupama Mann Anupama, Areeba Kamal, Bugu Wu, Carolina Brum, Charlie Maalouf, Chinguun Erdenebileg, Chris Dulhanty, Do- minik Moritz Doug Kang, Eduardo Jimenez, Evan Ladd, Fangping Shi, Felix Bai, Frank Chu, Fred Hohman, Hadas Kotek, Hannah Gillis Coleman, Jane Li, Jeffrey Bigham, Jeffery Cao, Jeff Lai, Jessica Cheung, Jiulong Shan, Joe Zhou, John Li, Jun Qin, Karanjeet Singh, Karla Vega, Kelvin Zou, Laura Heckman, Lauren Gardiner, Margit Bowler, Maria Cordell, Meng Cao. Nicole Hay, Nilesh Shahdadpuri, Otto Godwin. Pranay Dighe, Pushyami Rachapudi, Ramsey Tantawi, Roman Frigg, Sam Davarnia, Sanskruti Shah, Saptarshi Guha, Sasha Sirovica, Shen Ma. Shuang Ma, Simon Wang, Sulgi Kim, Suma Jayaram, Vaishaal Shankar, Varsha Paidi, Vivek Kumar, Xin Wang, Xin Zheng, Walker Cheng, Yael Shrager, Yang Ye, Yasu Tanaka, Yihao Guo, Yun- song Meng, Zhao Tang Luo, Zhi Ouyang, Alp Aygar, Alvin Wan, Andrew Walkingshaw, Andy Narayanan, Antonie Lin, Arsalan Farooq, Brent Ramerth, Colorado Reed, Chris Bartels, Chris Chaney, David Riazati, Eric Liang Yang, Erin Feldman, Gabriel Hochstrasser, Guillaume Seguin, Irina Belousova, Joris Pelemans, Karen Yang, Keivan Alizadeh Vahid, Liangliang Cao, Mah- yar Najibi, Marco Zuliani, Max Horton, Minsik Cho, Nikhil Bhendawade. Patrick Dong, Piotr Maj. Pulkit Agrawal, Qi Shan, Qichen Fu, Regan Poston, Sam Xu, Shuangning Liu, Sushma Rao, Tashweena Heeramun, Thomas Merth, Uday Rayala, Victor Cui, Vivek Rangarajan Sridhar, Wencong Zhang, Wengi Zhang, Wentao Wu, Xingyu Zhou, Xinwen Liu, Yang Zhao, Yin Xia, Zhile Ren, and Zhongzheng Ren. Apple intelligence foundation language models, 2024. URL https: / arxiv. org/ abss/ 220.222077.2.....2 21075.
Lucjan Hanzlik, Yang Zhang. Kathrin Grosse, Ahmed Salem, Maximilian Augustin, Michael Backes, and Mario Fritz. MIcapsule: Guarded offline deployment of machine learning as a ser- vice. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 3295-3304 2021. doi: 10. (0.1109/CVPR553009 202100000002220000063333
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction, volume 2 of Springer Series in Statistics. Springer New York, New York, NY, USA, second edition, 2009. doi: 978-0-387-84858--7 URL https:
//doi.org//i 10. 10011007/990 0- 387 84858-7.
Bingsheng He and Xiaoming Yuan. On the So(1/n)S convergence rate of the douglas rachford alternating direction method. SIAM Journal on Numerical Analysis, 50(2):700-709, 2012. doi: 10.1137/1 10836936. URL https: / www.ooooorro......oo. 1137 111111118836666
Patrick Hemmer, Sebastian Schellhammer, Michael Vössing, Johannes Jakubik, and Gerhard Satzger. Forming effective human-ai teams: Building machine learning models that comple- ment the capabilities of multiple experts. In Lud De Raedt (ed.), Proceedings of the Thirty-First
12

---

Published as a conference paper at ICLR 2025
International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2478-2484, International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 00.24963hjcca22222/444 URL atttps://doi.rrgg 2ttp:/...229/////// 2022233233222224. Main Track.
Patrick Hemmer, Lukas Thede, Michael Vössing, Johannes Jakubik, and Niklas Kühl. Learning to defer with limited expert predictions. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 6002-6011, 6 2023. doi: wt../////aa...375.5577.77.. URL setps://ojs
aaai. wow./oog//nneeeee php/ Sahp/AAAA AAAI/
Radu Herbei and Marten H. Wegkamp. Classification with reject option. The Canadian Journal of Statistics / La Revue Canadienne de Statistique, 34(4):709-721, 2006. ISSN 03195724. URL http: / www. jstor. org/ wtw.le//ee4a22222
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Peter Richtárik, and Sebastian Stich. Stochastic distributed learning with gradient quantization and double-variance reduction. Op- fimization Methods and Software, 38(1):91-106, 2023. doi: 10. 00.1000/10566888.2000 202.22113222252 1080
URL /nttps:///oi.....
011001111100000517515100 0556788 20125213
Gavin Kerrigan, Padhraic Smyth, and Mark Steyvers. Combining human predictions with model probabilities via confusion matrices and calibration. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4421-4434 Curran Associates, Inc., 2021. URL https: httpss:///cccceeeeeeeeeee neurips cc htceppapr__fiesse wtt.ffllsspppp/2221..... 2ttee/244494118888511aaaaaa2
Vijay Keswani, Matthew Lease, and Krishnaram Kenthapadi. Towards unbiased and accurate de- ferral to multiple experts. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Society, AIES 21, pp. 155-165, New York, NY, USA, 2021. Association for Computing Machin- ery. ISBN 9781 9781450384735. doi: 10.1145/3461702.. 3462516.. URL https: //doi /10 1145/3461700 3462516.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009, URL https: / h/ww.//w.. cs. toronto. coronto.edu//e wtwpttt.eddd/rri////ee haaprriiileaannnngeeeeteueee TR..-.R..00.R0..
Yansong Li and Shuo Han. Accelerating model-free policy optimization using model-based gra- dient: A composite optimization perspective. In Roya Firoozi, Negar Mehr, Esen Yel, Rika Antonova, Jeannette Bohg, Mac Schwager, and Mykel Kochenderfer (eds.). Proceedings of The 4th Anmual Learning for Dynamics and Control Conference, volume 168 of Proceed- ings of Machine Learning Research, pp. 304-315. PMLR, 23-24 Jun 2022. URL https: mlr.
//proceedings.co ml press v1 68 1222a html.
Yansong Li and Shuo Han. Solving strongly convex and smooth stackelberg games without mod- eling the follower. In 2023 American Control Conference (ACC), pp. 2332-2337, 2023. doi:
Zonghong Liu, Salim El Rouayheb, and Matthew Dwyer. The entrapment problem in random walk decentralized learning. In 2024 IEEE International Symposium on Information Theory (ISTT), pp- 3660-3665, 2024.
doi: 10.1 1111099117778864222440666666
Jie Lu, Anjin Liu, Fan Dong, Feng Gu, João Gama, and Guangquan Zhang. Learning under concept drift: A review. IEEE Transactions Knowledge and Data Engineering, 31(12):2346-366 2019. doi: 10.1109/KKDE..208882287
URL https: //ts:///oo.../ wttp://...../11................. /tt.:tttt///o....//00..1111
2018 287 68577.
David Madras, Toni Pitassi, and Richard Zemel. Predict responsibly: Improving fairness and accu- racy by learning to defer. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianche Bianchi, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018 URL ht wttp://rccc.cc.e.ooooo.ooeeeeeee http://w.....ttee////coeeeeeeeee http://eeeeeeeieccpaappea__e___. fil//fiillee http:///001111000077711777777770
13

---

Published as a conference paper at ICLR 2025
Anqi Mao, Christopher Mohri, Mehryar Mohri, and Yutao Zhong. Two-stage learning to defer with multiple experts. In Seirtt-seventh Conference on Neural Information Processing Systems, 2023.
URL httttt://ppeeeeeieeeeeeee////e net htt.e//wwww.eeeteeeeeeeeeeeeeeee forum?id-GI
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Principled approaches for learning defer with multiple experts. In Reneta P. Barneva, Valentin E. Brimkov, Claudio Gentile, and Aldo Pacchiano (eds.), Artificial Intelligence and Image Analysis, pp. 107-135, Cham, 2024a, Springer Nature Switzerland. ISBN 978-3-031-63735- //doi. ////0.0rg/10.... 1007 978 3- 3-031-01---1111 1110031--66 63735-33-5--- (_)7.
doi: (0070978--3-031-67775-----83
URL https:
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Regression with multi-expert deferral. In Forty- First International Conference on Machine Learning, 2024b. URL www.hhttp////e htttpp:///pperevdit net/ pest/forunge forum? SNTTCCCC5.
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Predictor-rejector multi-class abstention: The- oretical analysis and algorithms. In Claire Vernade and Daniel Hsu (eds.), Proceedings of The 35th International Conference Algorithmic Learning Theory, volume 237 of Proceed- ings of Machine Learning Research, pp. 822-867. PMLR, 25-28 Feb 2024c. URL https: / //ppoceedings... www.sp.essss...... 20337m/m224. laa.2a..tmm...
Angi Mao, Mehryar Mohri, and Yutao Zhong. Theoretically grounded loss functions and algorithms for score-based multi-class abstention. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 9753-4766 PMLR, 02-04 May 2024d. URL https:tt///... http://poocceeeeeeeeeeee www. prelspppes.... v23./22333222 /ta.//aa22244 2a..44..2 html.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Ar- cas. Communicatioon-Efffciient Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artifi- cial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282, PMLR, 20-22 Apr 2017. URL https: http::/pooceeeenn..../ mlr. www.pp.es............m.e press/w54/ memahan17e 7a. html.
Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In Proceedings of the 37th International Conference Machine Learning, ICML'20. JMLR.org, 2020a.
Hussein Mozannar and David Sontag. Consistent Estimators for Learning to Defer to an Expert. In Proceedings of the 37th International Conference on Machine Learning, pp. 7076-7087. PMLR, November 2020b.
Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Sontag. Who should predict? exact algorithms for learning to defer to humans. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.), Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 10520-10545. PMLR, 25-27 Apr 2023. URL https: htttpp::/prooeeeeeeeeeete http://poooeeee...oooooooo mlr. wwt...rl..........e..mmm.. press/ v206 2tt.///ozannar2223 .tmll.
Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya K Menon, Ankit Rawat, and Sanjiv Ku- mar. Post-hoc estimators for learning to defer to an expert. In Koyejo, Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp. 19292-29304 Curran Associates, Inc., 2022. URL https://proceed: file/be8 E 66d8caaddd88777255b ott.://ccccc.aaaaaaaaaaaaeeeeeee
neurips ee papprrrrrpppeeeeeeeeeeeeeeeeeeee faaeeer_rilleeee wiles/paper/200/
pdf..
Radford M Neal. Bayesian Learning for Newral Networks, volume 118 of Lecture Notes in Statis- tics. Springer New York, New York, NY. USA, 2012. doi: 11007/978-1-4611-7745-000 URL
https: //oo:.//oo.... woog/..0./..... 100000071000 908 1-611-146111 4.1 6116112200 00045-0.
Yurii Nesterov. Gradient methods for minimizing composite functions. Mathematical Program- ming, 140(1):125-661, August 2013, ISSN 1436-4646. doi: 10.100774400007-01--0099-- URL
https: / /ow. http:///......0......... http:///bb...g//....00/////oooo.
14

---

Published as a conference paper at ICLR 2025
Yurii Nesterov. Introductory Lectures on Conver Optimization: A Basic Course. Applied Optimiza- tion. Springer New York, NY, New York, NY, USA, edition, 2014. ISBN 1461346916. doi: 10. 1007/978- 4-4419-8853--- URL bttps:://dott org.oo/g/////ooo http:///..1110111--111
1010000077701111110 8853-9
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011. 2011. URL http://ufldl. stw.ffrrtt.oor..oooooooooooo edu, housenumbers /wwps///iipp111111 www.shumeesssss.oomm
Nastaran Okati, Abir De, and Manuel Rodriguez. Differentiable learning under triage. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 9140-9151. Curran Associates, Inc., 2021. URL https: httpss:/pproeeeiiggs www.:ediiiinnnnnnnnneeeee wtciipsscccppeee seaper_filesppeeeeeeeeeeeesseeee wwt.ee/ppppe//221.1...
file/ /tt1://cce337777ccccc7//eeee2222
Tadeusz Pietraszek. Optimizing abstaining classifiers using ROC analysis. In Proceedings of the 22nd International Conference on Machine Learning, ICMI. '05, pp. (65-672, New York, NY, USA, 2005, Association for Computing Machinery. ISBN 1595931805. doi: 10.1145/1102351. / /oii 1102435. URL http::///ooooo.ooo.o..11111111.1
Maithra Raghu, Katy Blumer, Greg Corrado, Jon Kleinberg, Ziad Obermeyer, and Sendhil Mul- lainathan. The algorithmic automation problem: Prediction, triage, and human effort, 2019. URL
https: / /aaviv...vv////////a//aa.//aavv. org/ 1tt.:///99.....2..
Philippe Rigollet.
Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(49):139--1392, 2007. URL http:// jmlr. wwwl..org/paers..e
wwwprlietolaa....or html.
Shai Shalev-Shwartz and Shai Ben-David. Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
Understanding Machine Learning: From Theory to
Shubhanshu Shekhar, Mohammad Ghavamzadeh, and Tara Javidi. Active learning for classification with abstention. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2801- 2806, 2020. doi: 10.1 10.109//ST1444442200019122
Yuwei Sun, Hideya Ochiai, and Hiroshi Esaki. Decentralized deep learning for multi-access edge computing: A survey on communication efficiency and trustworthiness. IEEE Transactions on Artificial Intelligence, 3(6)9633- 2022. doi: 10. 00.11099AA120001313338999 URL https:
/ //doi.oorg/ org/10..g1..... 1109/TAI 2021, 3133819.
Dharmesh Tailor, Aditya Patra, Rajeev Verma, Putra Manggala, and Eric Nalisnick. Learning to de- fer to a population: A meta-learning approach. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statis- fics, volume 238 of Proceedings of Machine Learning Research, pp. 3475-3483. PMLR, 02-04 May 2024. URL https: http///occeeee.eccooooo .mw.iinnn.mmm.mm....mmmmm..mmm.. press.pess..... v233 attittailli 1or24a .hml..
Vladimir N Vapnik. The Nature of Statistical Learning Theory. Information Science and Statistics. Springer New York, NY, New York, NY, USA, second edition, 2010. doi: https://doi.org/ 10000/000//0
978-1-4757-3264 1. URL 10. 1000000077780 1100-1-47555 4757-322444444
Rajeev Verma and Eric Nalisnick. Calibrated learning to defer with one-vs-all classifiers. In Ka- malika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 22184-22202. PMLR, 17-23 Jul 2022. URL w...m.r.p.. http::://proceedinng wtw.p:g............ee... v1 62/ / v//v/erraaaa rmw.raaa2..... h2m.mml..
Rajeev Verma, Daniel Barrejón, and Eric Nalisnick. On the calibration of learning defer to multiple experts. In ICML Workshop on Human-Machine Collaboration and Teaming. 2022.
//icml//cmmmmm/m// wwt.w/ttwl///2//////eeetta URL httpst:://///
Rajeev Verma, Daniel Barrejon, and Eric Nalisnick. Learning to defer to multiple experts: Con- sistent surrogate losses, confidence calibration, and conformal ensembles. In Francisco Ruiz,
15

---

Published as a conference paper at ICLR 2025
Jennifer Dy, and Jan- Willem van de Meent (eds.), Proceedings of The 26th International Con- ference on Artificial Intelligence and Statistics, volume 206 Proceedings of Machine Learning Research, pp. 11415-11434. PMLR, 25-27 Apr 2023. URL URLAttpss//proeediiie .ml.. press / 62 we rma23a htmll.
Marten Wegkamp. Lasso type classifiers with a reject option. Electronic Journal of Statistics, 1:155- 168, 2007. doi: 10.1214/07-EJS058, URL http:::///oi..og///.....o 1ttp://11..22117-E0000000
Marten Wegkamp and Ming Yuan. Support vector machines with a reject option. Bernoulli, 17(4), November 2011. ISSN 1350-7265, doi: 10.3150/10-BE3320. URL http:::/doi..org
1/50010-BEJ3200
Yu Wu and Anand Sarwate. Learning to help: Training models to assist legacy devices, 9 2024. URL https:
abs//409//24////////////////// 16253.
Tongxin Yin, -rancorancois Ton, Ruocheng Guo, Yuanshun Yao, Mingyan Liu, and Yang Liu. Fair classifiers that abstain without harm. In The Twelfth International Conference on Learning Rep- resentations, 2024. URL https: openreview net/ forumlid=jjweccaa.....
Chen Zhang, Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. survey on federated learning- Knowledge-Based Based Systems, 216: 106775, March 2021. ISSN 0950-7051. doi: 10.101 knossss... 2021. URL https: doi www.ddii.ooooogooooooo wttp//.............11........... 2011 206777
Yikai Zhang, Songzhu Zheng, Mina Dalirrooyfard, Pengxiang Wu, Anderson Schneider, Anant Raj. Yuriy Nevmyvaka, and Chao Chen. Learning abstain from uninformative data. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https:: http::::///ppeeeiiewwee. neett
KKARKOPCEA.
Yinglun 7hu and Robert Nowak. Active learning with neural networks: Insights from nonparametric statistics. Advances in Neural Information Processing Systems, 35:142-155, 2022a.
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neu- ral Information Processing Systems, volume 35, pp. 35379-35391. Curran Associates, Inc., 2022b. URL hwtps:ttt///...... httpps://proceeed neurips ce ctteerffflssseeeeeeeeeee Conference.pdf.
16

---

Published as a conference paper at ICLR 2025
A COMPARISON WITH BINARY SURROGATE LOSS
In this section, we compare the surrogate loss function proposed in binary case by Wu & Sarwate (2024) with our proposed method in Section 3.
In this work, the formula of the surrogate loss function is:
[wa(r, e, x. = c1 exp ( (((-ev-)) + ce cxp(-r) + m(n)vso exp (ar)
where a and 3 are parameters for calibration. If we directly make the extension to multi-class in our setting, server classifier becomes arg max; (2) and arg max; Cs (z(x), which results in the surrogate loss:
keep the same definition of rejector while the output of client classifier and
iu (iu(rr,, (r, v) = exp (- arg max (z)y - + ce exp(-r) + Larg max, my (x)yg0 exp (ar)
The client classifier part works well since the client classifier fixed during training. However, this part arg max; (x)y will lead to trouble since both arg max, (z) and y are index numbers of class in multi-class and therefore, the function is not differentiable with respect to (x))
Furthermore, this surrogate loss function requires to calculate calibration parameters and 8, which depends on the estimation of the accuracy of the client classifier, for each input sample x as shown in Theorem 2 in this work (Wu & Sarwate, 2024), which adds more calculations and estimation errors to practical experiments. This surrogate loss function is not available in the IA setting since it's jointly training the rejector and server classifier at the same time.
Compared to the extension of the surrogate loss function proposed by Wu & Sarwate (2024) with our stage-switching surrogate loss function, our method differentiable in multi-class and more flexible for fitting different settings.
B COMPARISON WITH DIFFERENT SURROGATE LOSS FUNCTIONS
In this section, we justify that previous surrogate loss functions, proposed from LWA and L2D, can not be directly extended to L2H by comparing those surrogate loss functions with our method, shown in Table 2, on the properties that are needed in the settings that we are interested in.
Confindence-L.. LWWA (or score- sarre--ase---WA.. represents the methods LWA that use the output m(x) or function of output f (m(()) of the client classifier as metric of confidence current prediction. the value of the metric is smaller than threshold, then the input sample z will be discarded as a result of rejection. The theoretical framework of Confidence-LWAA was first proposed by Herbei & Wegkamp (2006). There is no separate rejector in those methods. The rejected samples will be aban- doned since there will be no more actions after rejection. Separate rejector-LWA represents those surrogate loss functions in LWA that assume separate rejector to independently decide whether to reject or not. This kind of method was first proposed by Cortes et al. (2016) and proves the inability of confidence-basse LWA framework, the rejection decision only depends on the local classifier m and does not consider the issues after rejection.
methods in special cases, referring to Sec. 2.2 of this work. However, in the
In the L2D framework, samples are sent to an expert after rejection. Softmax-L2D, firstly proposed by Mozannar & Sontag (2020b), and OvA-L2D, firstly proposed by Verma & Nalisnick (2022) are two different classes of surrogate loss functions. Softmax-L2D adds a reject option as another class of task to the cross-entropy loss function, while OvA-I22D uses surrogate loss functions that transform multi-class classification into combination of multi-binary classifiers. However, the output of the rejector both methods also depends on the output of each class mx(x) mobile classifier m(x). Moreover, during training, the client and the server must keep connection with each other.
Two-stage (TS) confidence- and two-stage (TS) separate rejector-L22 are those kinds of surro- gate loss functions that consist of different sub-loss functions and can be trained in corresponding stages for both confidence and separate rejector cases, firstly proposed by Mao et al. (2023). Those two methods can be used for IA settings where the training is asynchronized since their surrogate loss
17

---

Published as a conference paper at ICLR 2025
function be easily split and run in different locations. However, in two-stage confidence-L211 methods, the rejector takes the output of m(#) as input, while two-stage separate rejector-L.2D methods, the rejector only considers the performance of experts different servers.
For those methods that do not have a separate rejector, the limitation has been proved by Cortes al. (2016). What's more, usually ML classifiers scenarios of our PPR and IA settings, when the latency is a concern, a system with a separate reject faster since in non-separate rejector system, all samples are firstly sent to the client classifier and then decided by the rejector, which may take longer time.
complex than rejectors in scale. In the
For those methods that the rejector does not learn from client classifier m(a) during training, the reject decision only depends on the performance of server classifier e(x). For those methods that the rejector does not learn from server classifier e(z), the reject decision only depends on the performance of client classifier m(x). In our PPR and IA settings, asking the server for help is free, so we have to balance the use of the server. A desired rejector should learn the ability
to compare the performance of m(xx and e(x) for each input as shown in the Bayes classifier by 2.1.
Those methods that can not train in asynchronized fields may fail in the IA setting since the connec- tion between client and server is unstable and intermittent.
Based on the settings that are realistic and interesting in real-worle scenarios, we require a surro- gate loss function for a multi-class L2H system to have a separate rejector, and the rejector learns from the knowledge of both the client classifier and server classifier during training and can operate in asynchronized fashion. Previous works that stem from LWA and L2H can not be directly ex- tended to L2H because they are either technically non-differentiable for training server classifiers or conceptually unmatched with the required properties stated above.
Table 2: Difference among surrogate loss function proposed in LWA and L2D
Separate rejector
Rejector learns m(x) Rejector learns e(x)
Asyne
Confidence-LNV LWWA Separate rejector-LWA
Softmax-L2D
x
x
OvA-L2D
/
x
confidence- L2D
X
TS separate rejector-L2D
Ours
C PROOF OF THEOREM 2.1
The standard approach to deriving the Bayes classifier for any given loss function is compare the posterior risk associated with each possible decision of the classifier. The decision that minimizes the posterior risk is then chosen the output. Recall in Section 2.1, the regression function is (1())) = P(Y = x| æ) and the generalized 0-1 loss function defined in equation is:
Lgeneral (r, e.
= mm(r I (
+ (
+ (co + (e)))
Note that m(x) is also stochastic, as discussed in Section 2.2. The random variable corresponding to the client classifier is denoted by M. Then, for any given sample x, the posterior risk over the conditional distribution of Y and M of any decision r' {REMOTE, LOCAL) and e' E [K] is:
Eyg. (re ,,,,,,,,,,,,., m)
Ey.m (1m(x)) ( Loooc + cole + (ce + C1 [
EEmpa é =) colezze 1, 1
+ P(Y E V. =x) =1)(m(()) IrEwen (co + +c1 ce)lee =MMoT)))
18

---

Published as a conference paper at ICLR 2025
where Ve. =)\ is the set of all labels except for e'. Then,
By.m|= (r', x', v; m)
= =Em (Tte' (2) (1 m(x) ( FLOCALL + colr"=
+ (1 - Ne (e) ( =LOCALL + (Ce + (1) I
1 Bmju L (ne (2:) 1 m(0) + (1 - 1/c (2)) m
+ RRE=MO (ce + (ce + e1) - 1)e' (2)))
Emja (1 (7 (2)1m(=))tt) + (1 77' 1
1'p'''Runn REMOTE (Co ci (1 1/ (I))))
1 (ne (1) P(M + e X x) (1 the (z)) & Ve X =x))
+ (ce + e Ne (x)))
1 P(M Y X = x) RE (Ce ai Me (x)))
(11)
Also, for any e', the following inequality holds:
- P(M X = x) + 1, =C + c1 (e)))
2 L P(M + X x) + = + 01 max (x))
(12)
The equality in Inequality 12 holds if and only if the decision e' satisfies me (a)) = max; 7) (x)) By combining this with equation 11, the Bayes classifier eB defined in equation 4, which minimizes Ey.mlz Lgeneraa e', I, y/ m), satisfies T = max, (x). Therefore, the Bayes classifier for the local client is:
B arg max (z).
Recalling the lower bound given by equation 12, the following lower bound can derived:
1L P(M + Y = x) + 1 - REMOTE (Ce + ci max (x())
2 min P(M + Y X = x), ce c1 max (x)}
(13)
Inequality 13 implies that for a given v, if P(M + x
c1 11 <
max, 7/ (x)) the
posterior risk reaches the lower bound when = REMOTE. Conversely, if P(M Y X =x)= <
C. + (1 max; 7 (z)). the posterior risk reaches the lower bound when r' = LOCAL. By the definition of the rejector, one way to construct the Bayes classifier of the rejector is:
B
IPP(M + Y|X = x) < ce + (1 - max 7 (+)) 2
1[1 L[1-P(M = Y| = < c max n [r))] 2 -
1[1 Margmax, m m (I) ce + m (z)) 2
|Mrg (x) (I) (1 c. c1) + max (x)] 2 1.
In summary, the Bayes classifiers for 0-1 generalized loss
B arg max 17, (z)
and
B (1) > C. c1) max 22
where (x) A arg max, mz(x).
D PROOF OF PROPOSITION 3.1
We first show the convexity of L1 and Le w.r. For L1 in equation notice that it equals to cross-ent cross-entropy loss function for multi-class tasks. Referring to the proof by Cover & Thomas (2005), in which the cross-entropy is transformed into the form of KI. divergence, which is convex,
19

---

Published as a conference paper at ICLR 2025
directly draw the conclusion that the L1 is convex function ex(2) for any i E [K] given (z, y).
Next, prove the convexity of L2 w.r. e. Recall the definition of L2 in equation 9: exp(ri)
exp(r2)
L2 = - ce + cilezy) In exp(r2) + exp(ri) Im=y In exp(r2) + exp(ri))
As described in Section 3, once in the rejector stage, only the rejector is variable. For convenience, we rewrite Lg in this form:
exp(rı) r2) -a exp(r2) bln exp(r2) + exp(r1)) exp(r2) + exp(r1)
where a= ce a + oi olley and m=y, which are depends on (z, The analysis can be divided into two cases:
case (I): S 0,
case (2): > 0.
In case (1), the partial derivative of f(r1, 72) are:
0f(r1.72)
exp(r1)
exp(r2)
dri (exp(r2) exp(ri))
(exp(r2) exp(ri))
and
(r(,
exp(r1) Ōr2 (exp(r2) + exp(r:))
exp(12) (exp(1z) + exp(ri))
Since 6 = (-11-111 we have that:
rf(r,
exp(r1)
S (exp(r2) + exp(ri)) 20,
dr1
and
Of(r,,
exp(r1)
(exp(r2) + exp(ri)) 2 0
Dr2
always holds, which means f(11,r2) (or L2 ) non-increasing function of and non-
decreasing function of r2. For the case Ce > C1 = 1, it is impossible for 0. Thus, f(r, r2) (or La are monotonically decreasing function of rı and monotonically increasing function of r2.
In case (2), where a > 0, we have that a + b > 0 always holds. Then we calculate (f(r,, 21) + 22)/22 and f(11, (21 22) for any 21 and 22 (J(r1 + ((1, 22)
5 (-a(z) - In(e + e*+))
- b(ri ln(e" + + - a(22 - te")" b(r - In(e" +)²)))
(- + aali + t²*) -br
+ bln(e" + - az9 + In + d²t) bln(e" + c"²))
2 a( + x2) 2br + (a + In In + t + t 2e 2r))),
and
f(r1,21 + 22) -a((z) + 22/2 In(e(#1+22)/2 te")) b(ri - In(e" + (
-a(z1 + 22) + a (aln(e(= + - bri + +bl((e" + e (srt2a)/2).
20

---

Published as a conference paper at ICLR 2025
The subtraction between them is:
(f(r1, x1) + f(ri, 22)) - f(ri, (21 22)/22
(14)
(a+ bn e tn m
(a+ b) In(e +e"1)
(a 6) In v (ett +en (e tea) e(=1+za)/2 e
We notice that exponential function exp (z) convex function such that
e + e
(22
holds for any 21, 22 Since
e + e
2 (0+t1)12
2 *1t + ti 2 (0(24))/24m
(E + + (e" + + 2 (e (xtul)/2 + t
Vee + e" t (e" + ten)
11
e(x+v)/2 + e
and a + O, we prove that the for equation 14:
(f(r) + ((1,, 22)//2 (ri, , (21 22)/2)
always holds, that is f(11,12) a convex function over r2. Following similar steps, we also prove that f(1 convex function over 71.
E PROOF OF THEOREM 3.2
The surrogate loss function defined in equation 7 consists of L, and L2, which are targeted the server classifier and rejector, respectively. Since the rejector and server classifier are trained stage-switching manner as described in Section 3, parameters of e are only updated by the gradient derived from L1 and that of r is only updated by the gradient derived from L2- Therefore, the minimizer of is derived from the risk of L1 in the server stage, and the minimizer of r is derived from the risk of Lg (with the current server classifier) in the rejector stage. The risks are:
exp (z)
Fymm === Σ
Ny (y(x)) log yEY
Σy exp (cgr
and
exp (r2)
exp (r1)
Ey.mlz L2 - (
exp (r2) + exp (ri) -Ey.ml Im exp (r2) + exp (r1)
Since the Bayes classifiers optimal for any according to the definition in equation 4, it's equivalent to deriving the minimizer risk each sub-surrogate loss function for any given æ.
Note that L1 is cross-entropy loss function for server classifier e(x); can directly get the minimizers for each e, by the arguments in Section 10.6 proposed by Hastie et al. (2009). Let's denote the minimizers of each sub-function é which is defined in Section 3, of server classifier by et The minimizes ei satisfy the following condition:
exp (x)) Σ, exp (c)(z))
n1(2), Vi,
where m/ (x) is the regression function for i-th class. Therefore, the e*(x) = arg max; (x) arg max; TT(2)) (z) = e (x)). The minimizer server classifier e* the same as the Bayes classifier
for server e
21

---

Published as a conference paper at ICLR 2025
Next, consider the rejector r(z). Since e(z) arg max, ez(2), when plug in the minimiz-
ers ef (z) to Lg the risk L2 conditioned on x becomes:
exp(r2)
exp(r1)
By I22 = Fymml (- exp(r2) + exp(ri) mm In exp(r2) + exp(ri)
exp(r2)
= =- - Ce - c1 + e1 max (x)) In exp(r2) + exp(r1)
exp(r1)
(z) In exp(r2) + exp(ri))
where j*(x)= = arg max; (z)x) as defined Theorem 2.1. The following analysis will divided into two cases:
case (a): (1 - Ce - (1) + Ci max; (x)) S 0,
case (b): (1 Ce (1) + ci max, (2) > 0.
In case (a), when (1 - Ge - c1) + Ci max; (x) S 0, 2 S always holds, such that E Ly is monotonically decreasing function of r1. And (a /Or2 > 0 always holds such that l/ monotonically increasing function of 12- In fact, we can also draw the same conclusions by using the monotonicity from Proposition 3.1 since the expectation of monotone function is still monotone. Therefore, in this case,
exp(ri)
exp(r5)
and (cxp(r3) exp(ri) 0
(exp(rī) + exp(ri)
That means rf > r2 always holds. Therefore, the rejector always satisfies:
(x) (x]()) (x)) 2
Also, in this case, the Bayes classifier for rejector is B 1 Merg max, m.(os(()) (1 ce ()) + 1 2 1. Therefore, r'(x) = r
C1 max; n: (z)])
Then we consider the case (b) when (1 ce c1) + C1 max; (2(2) > 0. Since L1 is convex according to Proposition 3. and expectation of convex function is still convex proved by Boyd & Vandenberghe (2004), Ty To is convex, and its minimizers are achieved when partial derivative equal O. We take the partial derivative over rı and r2:
O DEylar a T.2
exp(r1) (1 -c - ci + 11 max (exp(12) + exp(r1)) (1) (exp(r2) + exp(ri)))
exp(r2)
dr1
and DE,
L2
exp(r1)
exp(r2)
(11 Ce - 61 + C1 max (2))
(exp(r2) + exp(ri))
()) (exp(r2) + exp(ri))
Setting the partial derivatives to 0, we have that
exp(ri)
(x)
exp(rī) 1 1- 1- - + ej max, (x()))
Then, the rejector becomes: r" (x: [ri((x) > rz(2)) 1
= 1[exp(ri(x)) > exp(ri(x)))) 2
(x)((i(x))
= -1(op((3(() 1]) 2-1
exp(r3(x))
-4) + 0 (x)) 2- -1)))())())) (1-ce-a)
=x))
We prove that in both cases (a) and (b), the minimizer of L2, r" (x), equals the Bayes Classifier of rejector ,. (²))..
In summary, we prove that (r (z), e e<))) = (x)) (x)) for any v, so the stage-switching surrogate loss function is consistent with the generalized 0-1 loss function.
22

---

Published as a conference paper at ICLR 2025
F STOCHASTIC POST-HOC ALGORITHM FOR BOUNDED REJECT RATE SETTING
We propose stochastic post-hoc method, which is shown in Algo. 3, Algo. and Algo 5. this algorithm for BRR settings, firstly train our rejector and server classifier following the process as shown in Algo. 3, which similar to algorithms for PPR or IA settings (can also be trained with asynchronized algorithm 2). After training, reject rate Q1 based on the output rejector r(z). . Once we get the empirical reject rate, we compare it with the bounded reject rate q.
calibration set Deali to calculate the empirical
If @ is greater than @i that means we have to sacrifice several rejected samples to force them to make prediction locally client classifier m(x) the input samples are following the Algo. where each rejected samples are made a final decision by the value of a uniform random variable. Once the value is below the ratio p, the sample will still be sent the server. Otherwise, may be predicted by the client classifier. When the empirical reject rate is higher than the bounded reject rate, after adding this post-hoc mechanism, the bounded reject rate q can just ensured.
If q is smaller than or equal to Q1, that means we can reject more times than the rejector r(x) request. Then, we follow a similar mechanism in Algo. 5, which uses a random variable to decide which samples the rejector sends to the server classifier. After using the post-hoc mechanism, we can ensure the bounded reject rate while making the best use of the server classifier.
Algorithm Training Process of Stochastic Post-hoc Method
Input: Training set D = { yi) i E [m]) Calibration set Deali = {(xs, y1) : E [R:] Fixed client classifier m, Rejector 7 Sever classifier e", Bounded reject rate q.
1: for t = to n do
exp (ex, (e,, (x+))
2: (
In Σ, exp
3: et SCD(L)(T c ()())1
4:
-(1 ce - + (1let(as)= exp (ope)
exp (ra(a:))
mm(x)== In exp(ri (oxp) rt-1)
5: +
6: end for
7: Q1 < Empirical ciaaaalla www.caleeeee... Re
RmmpiricaalejeettRteee jectRate (Deal)
8: return r",6",44
Algorithm 4 Inference Phase of Stochastic Post-hoc Method When <
Input: Client Classifier m. Trained Rejector r" Trained Sever Classifier e". Input Sample Bounded reject rate q, empirical reject rate 91
1: 9/41
2: if r(x) S 0 then
3: Sample from 1) uniform distribution.
4: if S p then
5:
ÿ (x)
6: else
7:
ÿ (z)
8:
end
9: else
10:
g + m(x)
end if
12:
return ý
23

---

Published as a conference paper at ICLR 2025
Algorithm 5 Inference Phase of Stochastic Post-hoc Method when 41
Input: Client Classifier m. Trained Rejector r" Trained Sever Classifier e". Input Sample Bounded reject rate q, empirical reject rate @1
1: p (g (1) -1)
2: if r(x) > 0 then
3: Sample from 1) uniform distribution.
4: if then
5:
y (x)
6: else
7:
(z)
8:
end if
9: else
10:
9 + (x)
end if
12: return !
G EXPERIMENT DESCRIPTION AND ADDITIONAL RESULTS
Datasets We test our proposed surrogate loss function 7 and algorithms for different settings on CIFAR-10 (Krizhevsky & Hinton, 2009), SVHN (Netzer et al., 2011) and CIFAR-I00 (Krizhevsky & Hinton, 2009) data sets. CIFAR-10 1-0 consists of 32 x 32 color images drawn from 10 classes and split into 50000 training and 10000 testing images. CIFAR- - has 100 classes containing 600 images each. SVHN is obtained from house numbers with over 600000 photos in Google Street View images and has 10 classes with 32 32 images centered around a single character. The experiments are conducted in RTX 3090. It takes approximately 5 minutes to train the local model and minutes to train each remote server classifier with the rejector when server classifier is set to be AlexNet hours train each remote server classifier with the rejector when server classifier set to be VIT.
Comparison synchronization and asynchronization We conduct additional experiments training the server model and rejector under both synchronized, as shown in Algo and asynchro- nized settings shown in Algo The model evaluated in the same way as Section The contrastive evaluation and loss curve are shown in Table 3 and Figure 4.
Result for different C1 and C₂ on CIFAR-10 and SVHN Besieds the result we show in Sec- tion 5, we add extensive result for contrastive evaluation with different inaccuracy cost 01, reject cost Ca and synchronization interval S (for IA setting) for CIFAR- 10 and SVHN with local classi- fier and rejector being LeNets and remote classifier being AlexNet. The results are shown in Table 3.
Result for different C1 and ce CIFAR-100 Since stage-swtich surrogate loss function doesn't set up constraints on the size of dataset and structures machine learning methods, we dataset CIFAR 100 with local classifier and rejector being LeNet
test the Contrastive Evaluation and remote classifier being ViT, a transformer-base Table 4. Both higher с₁ and ce can reduce the ratio of numbers that are sent to remote classifier, but in our experimental results, the reject rate is more sensitive to ce. When e, is close to 1, almost no sample sent remote classifier, which make sense because c. 1 means that the cost of asking for help is always greater than locally prediction.
vision neural network. The results are shown in
Samples partitioned by rejector We choose one case where the rejector and remote classifier AlexNet are trained on SVHN when
1.25 and c. = 0.25. Then we let rejector partition the REMOTE and r(x) = LOCAL,
test set and randomly pick images from the subset with r=)) respectively. The results are shown in Fig. 5 and Fig. 6. It's obvious that samples kept locally are clearer, contrast, focused, with higb-resolution, while the samples that are supposed to send to the server are blurry, unfocused, with low-resolution. Without any manual adjustment, rejector learns to assess "difficulty" using the same metrics as humans, by interacting with both local model and server model during the training process.
24

---

Published as a conference paper at ICLR 2025
Table 3: Contrastive Evaluation Results for different cost and synchronization interval
cifar10 10 (%)
SVHN
S
C1
Ge
m
differ.
m
e
differ.
r(2) = LOCAL
74.8
82.8
8.0
90.1
93.2
3.1
sync.
1.0
0.25
r(æ) REMOTE
54.5
68.6
14.1
62.0
72.5
10.5
r(z) = LOCAL
73.9
81.9
8.0
90.6
93.3
2.7
syne.
1.25
0.25
r(x) REMOTE
54.5
67.7
13.2
61.2
72.8
11.6
r(2) LOCAL
82.3
86.8
4.6
97.2
97.9
0.7
sync.
1.25
0.0
r(z) = REMOTE
62.6
73.8
11.2
87.6
90.8
3.2
r(z) LOCAL
75.9
84.3
8.4
90.6
92.9
2.3
100
1.0
0.25
r(x) R REMOTE
55.3
69.5
14.1
63.6
72.7
9.1
r(x) LOCAL
74.5
83.3
8.8
91.4
93.5
2.2
100
1.25
0.25
r(x) REMOTE
55.5
69.9
14.4
65.4
73.9
8.5
r(x) = LOCAL
81.4
87.4
6.0
97.0
97.8
0.8
100
1.25
0.0
r(x) REMOTE
62.6
75.3
12.7
87.3
90.6
3.3
r(x) LOCAL
74.8
83.1
8.2
90.5
93.2
2.7
1000
1.0
0.25
r(x) REMOTE
54.7
69.2
14.6
64.3
72.9
8.6
r(x) LOCAL
75.2
83.3
8.1
90.8
93.9
3.1
1000
1.25
0.25
r(#) = REMOTE
56.0
69.7
13.7
65.1
75.6
10.5
r(x) LOCAL
80.3
87.7
7.4
97.3
98.0
0.8
1000
1.25
0.0
r(x) REMOTE
62.8
74.5
11.7
86.9
90.7
3.7
r(x) = LOCAL
74.1
82.9
8.9
90.1
93.0
2.9
[D]
1.0
0.25
r(x) REMOTE
56.8
71.1
14.3
62.9
73.3
10.4
r(x) LOCAL
72.8
82.9
10.1
90.8
93.7
2.9
[D]
1.25
0.25
r(x) REMOTE
57.1
70.4
13.3
63.8
74.1
10.3
r(x) LOCAL
78.9
86.8
7.9
96.2
97.5
1.3
[D]
1.25
0.0
r(x) = REMOTE
62.8
74.9
12.0
87.5
90.9
3.3
25

---

Published as a conference paper at ICLR 2025
Table 4: Contrastive Evaluation Results for different costs on CIFAR-100 with remole classifier being VIT
eifar100
ratio
differ
joint securacy
1.0
0.2
((())
r(se
LOCAL
0.1
78.6
100.0
60.6
21.4
88.1
r(x) LOCAL
68.8
94.8
25.0
r(2) REMOTE
r(xr
90,9
43.9
syoc.
((x) REMITE
24.6
87.9
SYDC:
1.0
0.8
r(#)= REMOTE
r(2) LACAL
23.6
30.7
17.2
88.8
84.7
53.0
67.5
43.4
1.0
0.95
[(2) RUMOTE
r(x) LOCAL
100.0
0.0
27.6
NAA
88.2
N/A
60.7
N/A
27.6
SYnc.
1.9
0.5
((2) REMOTE
P(0) LOCAL
95.8
4.2
26.2
58.6
88.0
92.7
34.1
61,9
86.8
((#)
7(x) LOCAL
50.8
35.7
89.5
53.8
50.7
M(3)
100.0
100.0
syaс.
((2) REMUTE
27.5
88.1
2.0
r(x) LOCAL ((()) REMOTT
94.4
27.1
87.6
98.9
27.1
87.8
60.7
2.0
0.6
(2)) REMOTE
M(xr) LOCAL
36.5
13.5
24.5
47.2
90.9
87.6
43.7
63.1
X2.1
sYac.
2.0
0.8
r(x) LOCAL r(x) REMOTE
23.6
76.4
30.8
17.0
89.1
85.2
58.3
68.2
43.6
((2))
-(x) LOCAL
100.0
27.6
88.0
N/A
60.4
NIA
27.6
LOCAL
100.0
100.0
0.0
87.8
((2) REMOTE
r(x) LOCAL (2) REMOTE
93.9
27.8
3.0
87.8
98.9
21.1
88.1
61.0
3.0
0.6
M(ar) LICCAL r(#)= REMOTE
86.1
24.4
46.9
87.9
90.1
63.5
43.3
N2.2
3.0
0.8
M(N) = LOCAL
78.5
30.5
88.8
58.3
42.3
((3) REMOTE
21.5
16.7
85.4
68.7
3.0
0.95
(22)
((3)
LOCAL
100.0
27.6
N6A
88.0
N/A
60.4
N/A
27.6
r(#) REMOTE
7(x) LOCAL
0.1
100.0
100.0
0.0
50.4
-(x)
95.2
29.5
syac.
((#) REMOTE
99.0
27.1
88.0
60.8
87.8
SYNC
4.0
-(#) REMITT
r(2)) LOCAL
86.4
24.6
90.5
87.5
44.1
62.9
81.9
4.0
0.8
((2) REMOTE
r(2) LICAL
21.5
78.5
30.6
16.5
85.3
88.7
58.1
68.8
42.4
4.0
0.95
((x) REMOTE
F(x)
LOCAL
100.0
0.0
27.6
N/A
87.8
N/A
60.2
NIA
27.6
((2)
P(x) LOCAL
0.1
100.0
100.0
0.0
87.9
95.7
27.0
SYDC.
r(#) REMOTE
98.9
87.8
68.7
M(3)) LECAL ((#) REMOTE
57.8
93.4
35.7
95.9
26.5
87.8
61.6
5.0
0.6
r(x) LOCAL ((2) REMOTE
36.4
13.6
24.1
49.4
90.6
87.7
63.6
41.1
82.5
5.0
0.8
P(x)
REMOTE
LOCAL
79.3
30.7
30,5
16.4
85.4
88.8
58.3
69.1
41.9
0.95
((3)
LOCAA
100.0
27.6
87.9
60.4
N/A
27.6
26

---

Published as a conference paper at ICLR 2025
SVHN (c1 1.0, 0.25)
cifar10 (c1 1.0,
3 10
Synchronous
2.4
Synchronous
$ 100
5 100
2.2 10
1000
$ 1000
Loss
IDI
x
[D]
1.8 x
2 10a
1.6 10*
50
100
150
200
250
50
100
150
Step
Step
SVHN (c1 1.25, C. 0.0)
cifar10 (c; 1.25, Ce 0.0)
x00
302
Synchronous
Synchronaus
3x
100
10
100
x.8 10a
1000
2.4 x 10a
= 1000
2.6 10a
[D]
10
5 [D]
2.4x 10a
10
21x
1.8 1
50
100
150
200
250
50
100
150
Step
Step
Figure 4: Comparison of synchronization and synchronization with different parameters
Table 5: Accuracy of classifiers CIFAR-10 when client classifier is pre-trained without "truck" class
"truck" (%)
other classes (%)
all classes (%)
only local classifier
0
64.4
58.0
only remote classifier
87.5
72.5
74.0
jointly work
85.2
70.5
72.0
rejected rate under jointly work 96.1
63.1
72.7
Experiments on imbalance dataset We set up an additional experiment evaluate the impact of imbalance dataset issues for our multi-class L2H. We choose one case where the rejector and remote classifier AlexNet are trained on CIFAR-10 In this experiment, we pre-train the local model with the reduced dataset that doesn't 't contain any sample from one certain class (no "truck" CIFAR-I0 and no "9" in SVHN). Based on that, we train rejector and edge model with full dataset. The results in Table 5 and Table 6 show that almost all the samples from missing class are identified by rejector and sent to server model. The overall accuracy doesn't 't get undermined compared to standard setting. The training of the rejector makes the multi-class L.HH robust to imbalance dataset or distribution drifting issues. And after training, the remote classifier becomes expert that is specialized the missing class.
SVHN when 0₁ 1.25 and c, 0.25.
Table Accuracy of classifiers on SVHN when client classifier pre-trained without "9" class
"9" (%)
other classes (%)
all classes %)
only local classifier
92.2
83.0
only remote classifier
94.5
89.5
90.0
jointly work
90.0
88.9
89.0
rejected rate under jointly work
93.5
12.0
17.8
27

---

Published as a conference paper at ICLR 2025
10
16
1
11
116
2
2
2
3
3
3
3
136
4
4
4
4
4
5
5
5
5
5
60
160
61
1226
6
778
70
8
8
8
990
9
Figure S: Samples from SVHN with r(x) LOCAL
28

---

Published as a conference paper at ICLR 2025
0
10
32
2
3
3
3
F
14
5
57
52
5
6
8
86
28
1
9
Figure 6: Samples from SVHN with r(x) REMOTE
29

---

Published as a conference paper at ICLR 2025
Table 7: Contrastive Evaluation Training Asynchronously with 100,
1.25 and c. 0.25
cifar10 (%)
SVHN (%)
differ.
differ.
data with rejector r(x) LOCAL
74.5
83.3
8.8
91.4
93.5
2.2
data with rejector r(x) = REMOTE
55.5
69.9
14.4
65.4
73.9
8.5
Cifar10
SVHN
Stochastic Randomly Reject
0.915
Stochastic Randomly Reject
0.74
0.72
0.905
Accuracy
0.70
Accuracy
0.900
0.895
0.68
0.66
0.885
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Reject
Reject
Figure 7: Comparison with randomly reject after Stochastic Post-hoc Algorithm when C. 0.25 and 1.12
Accuracy comparison over stochastic post-hoc and randomly reject on bounded reject rate setting show that client classifier under Bounded Reject Rate settings would benefit from training with Algo. and testing with Algo. 4 and Algo. 5, we set up randomly reject method as baseline. In this randomly reject method, we assume that there is no rejector, the sample is randomly sent server classifier according the value of bounded reject rate, c.g., with bounded reject rate 0.5, half of the samples will randomly chosen and sent to server for inference. We train our rejector and server classifier by following Algo. 3. After that, given different bounded reject rate, either Algo. 4, or Algo. 5 to strictly control the actual reject rate below the bound. The results of the securacy-vs-boundee reject rate for the Stochastic Post-hoc method and the random reject method are shown in Fig. 7. The result demonstrates that by using the Stochastic Post-hoc Algorithm, the system can still actively pick up the samples that fit the server classifier even under the constraints of bounded reject rate.
30


Reviews:
[{"review_id": "1zCn5uZBP0", "reviewer": "Reviewer_We9X", "summary": "This paper extends the ``learning to help'' paradigm from binary classification to multi-class settings. Learning to help aims to learn a rejector for routing between edge legacy devices and server-side large models. This paper provides algorithms with theoretical analysis, followed by experiments on CIFAR-10 and SVHN.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The setting of learning to help is quite interesting and meaningful. The authors extend it to multi-class classification cases, which have extensive applications. The proposed method is theoretically guaranteed. Also, the presentation is good.", "weaknesses": "The main drawbacks of this paper may be in the experiment part.\n- The datasets used are small, such as CIFAR-10 and SVHN. And there are only two datasets. Usually, evaluation on 3 datasets (or more) will be better.\n- The used LeNet and AlexNet are tiny. Trending sota models like ViT can be considered.\n- The learning to help scenarios can be very useful in large language model settings for on-device inference. Can the authors do some experiments on this? Or at least give a discussion.\n- How do you partition the data for training the small legacy model and large server model? Is there any difference?\n- I am just wondering about the costs of training the rejector and server model. Can the authors elaborate on this? If the costs are too much compared with the efficiency gains afterwards, why not use the server-side model solely?\n- Can the authors do some case studies to show which samples need to be handled on the server instead of on the device? It will help to understand the system.\n- Towards ``first principle'' to make the thing simple: for image classification tasks, one possible and simple solution is that during inference, check the prediction confidence (e.g., the softmax entropy) of the device model, and if the confidence is lower than a threshold (a predefined hyperparameter), send it to the server. Is this solution possible? It will not require any additional training for a rejector.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "V4bQlo2fuQ", "reviewer": "Reviewer_aEUF", "summary": "In this manuscript, a hybrid system is introduced, wherein the local model is supplemented by a server-side model and the rejector selects data samples to be directed to either the client model or the server model. The manuscript presents three distinct scenarios: “pay-per-request”, “intermittent availability”, and “bounded reject rate”, which align with practical constraints related to cost, availability, and policy, respectively. To address these challenges, a differentiable and convex stage-switching surrogate loss function is developed to iteratively optimize both the “rejector function” and “server model”. Experimental results validate the superior performance of the proposed framework.", "questions": "As presented in the \"Weaknesses\" section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The writing of this manuscript is clear, and easy to follow.\n- This manuscript addresses three practical scenarios reflecting constraints related to cost, availability, and policy, and derives formal objective functions to represent them.", "weaknesses": "- The authors state that they extend the “learning to help” framework to handle multi-class classification but do not explain the challenges involved in transitioning from binary-class to multi-class classification.\n- In the Conclusion section, the authors state that the proposed framework opens new avenues for further exploration in multi-party collaboration. However, since the evaluation uses relatively simple networks, such as LeNet-5 and AlexNet, the authors should include more complex networks to thoroughly validate the framework's performance.\n- Figure 2 illustrates that the hyper-parameters $ c_1$ and $c_2$ significantly affect the system's overall performance. Therefore, it is recommended that the authors evaluate the proposed framework's performance while varying $c_1$ and $c_2$ simultaneously. Additionally, the authors should provide guidance on achieving an optimal balance between $c_1$ and $c_2$.\n- Table 1 shows that for the CIFAR-10 and SVHN datasets, when the rejector predicts “local”, the performance of $m(\\cdot)$ is lower than $e(\\cdot)$. Similarly, when the rejector predicts “remote”, $m(\\cdot)$ still performs worse than $e(\\cdot)$. Typically, the server model’s performance should surpass that of the local model when the rejector predicts “remote”. The authors should clarify this discrepancy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "wVdUcl7yrn", "reviewer": "Reviewer_FjCZ", "summary": "This paper focuses on the collaboration between the client model and the server model by using a rejector. To train the rejector, client model, and server model, this paper derives a stage-switching surrogate loss function to allow the asynchronous training between the client model and the server model.", "questions": "1. What's the process during the inference stage with the surrogate loss?\n\n2. What's the convergence rate difference between the asynchronous and synchronous methods?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis of this paper is solid, which extends the binary classification setting of L2H to general multi-class settings.\n\n2. The problem is important and the proposed method uses a surrogate loss to asynchronously train client and server model, which is simple yet theoretically effective.", "weaknesses": "The experiments are limited. Experiments are mainly composed of hyper-parameter sensitive analysis evaluations, which lack comparison to baselines. For example, this paper should compare the proposed method with those using the synchronous training method or different surrogate loss functions in terms of overall performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "SCtY0pdJZC", "reviewer": "Reviewer_vq4j", "summary": "This paper extends the L2H model from binary classification to multi-class settings, enabling collaboration between a local (client) model and a remote (server) model, particularly tailored for resource-constrained environments. A stage-switching surrogate loss function is developed to train the server model and a rejector, which facilitates selective sample deferral to the server, thereby optimizing overall performance.", "questions": "- Could the authors consider privacy-preserving techniques, such as differential privacy, to mitigate potential privacy risks? Additionally, how would these methods impact the proposed approach's effectiveness?\n\n- Can the paper provide theoretical justifications for the surrogate loss's consistency and convergence properties, especially in non-IID data conditions?\n\n- How could the framework adapt to handle non-IID data distributions across clients? Could the rejector's decision-making process be adjusted for such scenarios?\n\n- For asynchronous training, could a method be introduced to adaptively adjust synchronization interval $S$, improving applicability to real-world deployments?\n\n- Is there a way to make the client classifier adaptable to changing data distributions over time?\n\n- Would the method be effective with more complex models, such as GPT-2, as hinted in the conclusion?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ This paper contributes by extending the L2H framework to multi-class classification, which enhances the applicability of client-server cooperation in environments with limited resources.\n\n+ The surrogate loss function supports asynchronous training, which aligns with scenarios of intermittent server access, beneficial for distributed learning settings.\n\n+ This paper provides a solid theoretical foundation for the proposed method, supporting its validity and enhancing confidence in its application.", "weaknesses": "- The client-server setup involves data offloading, raising potential privacy risks. The paper lacks a discussion on privacy-preserving methods, such as differential privacy, which are common in federated learning.\n\n- While the surrogate loss aims to approximate the Bayes optimal classifier, the paper does not provide rigorous proofs for its consistency or convergence in multi-class settings, particularly under non-IID data distributions, a common issue in federated learning.\n\n- The approach assumes IID data, which may not reflect real-world federated learning scenarios. Non-IID data could impair the rejector’s effectiveness in making deferral decisions, limiting the model's applicability.\n\n- While the asynchronous training algorithm partially addresses intermittent server availability, it does not fully address the issues of model drift or maintain accuracy under unstable connectivity. Adaptive adjustments for synchronization frequency and performance are not fully explored.\n\n- Relying on a fixed client classifier limits its ability to adapt to new data distributions or improve through collaborative training, potentially degrading performance over time and increasing dependency on the server model.\n\n- The experimental setup involves relatively simple architectures (LeNet-5 for the client and AlexNet for the server). This limits the generalization of the framework to applications involving more complex models, such as those used in large-scale real-world systems. Additionally, the conclusion’s mention of \"multi-party collaboration in hybrid machine learning systems, especially in the era of LLMs.\" could be misleading, as the paper does not provide any experiments or detailed discussion about large language models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)