Reliable learning in challenging environments
Authors: Nina Balcan
Steve Hanneke
Rattana Pukdee
Dravyansh Sharma
Venue: NeurIPS 2023 poster (2023)
Keywords: Reliable machine learning
adversarial robustness
distribution shift
theory

Abstract: The problem of designing learners that provide guarantees that their predictions are provably correct is of increasing importance in machine learning. However, learning theoretic guarantees have only been considered in very specific settings.  In this work, we consider the design and analysis of reliable learners in challenging test-time environments as encountered in modern machine learning problems: namely adversarial test-time attacks (in several variations) and natural distribution shifts.  In this work, we provide a reliable learner with provably optimal guarantees in such settings. We discuss computationally feasible implementations of the learner and further show that our algorithm achieves strong positive performance guarantees on several natural examples: for example, linear separators under log-concave distributions or smooth boundary classifiers under smooth probability distributions.

Reliable learning in challenging environments
Maria-Florina Balcan Carnegie Mellon University ninamfècs cmu edu
Steve Hanneke
Purdue University steve steve. www.ehaanneeeeeillccmmm
Rattana Pukdee
Dravyansh Sharma Carnegie Mellon University dravyans css cmu. edu
Carnegie Mellon University rpukdee@ cs cmu edu
Abstract
The problem of designing learners that provide guarantees that their predictions are provably correct is of increasing importance in machine learning. However, learn- ing theoretic guarantees have only been considered very specific settings. In this work, we consider the design and analysis of reliable learners in challenging test- time environments as encountered in modern machine learning problems: namely "adversarial" test-time attacks (in several variations) and 'natural' distribution shifts. In this work, we provide a reliable learner with provably optimal guarantees in such settings. We discuss computationally feasible implementations of the learner and further show that our algorithm achieves strong positive performance guarantees several natural examples: for example, linear separators under log-concave distributions or smooth boundary classifiers under smooth probability distributions.
Introduction
The question of providing reliability guarantees on the output learned classifiers has been studied previously in the classical learning setting where the training and test data independent and identically distributed (i.i.d)) draws from the same distribution [RS88, EYW10, 10, EYW12). Conceptu- ally, reliable learner outputs a prediction and may output correctness guarantee. We know that the learner is correct on all points with the guarantee as long as the learning-theoreti assumptions hold, e.g., realizability. While trivial model that abstains from providing any guarantee is also reliable learner, we are interested in a reliable learner that provides the guarantee on as many points possible (useful in the sense of Rivest and Sloan (RS88]). [EYW10] provides characterization of optimal reliable learners in this classical learning setting.
However, the assumption that the training and test data drawn from the same distribution is often violated in practice. The mismatch may take the form of a 'natural distribution shift' when the test distribution is different from the training distribution an adversary that can perturb a test data point with the goal of changing the model prediction. This significant performance drop, well the inability guarantee
"adversarial attacks' when there is
is frequently accompanied the usefulness of the algorithm. As result, there is a significant interest in the study of test-time attacks [GSS15, CW17, MMS 18] and distribution shift [LWS18, RRSS19, MTR+21] among the applied machine learning community. Furthermore, recently there has been growing interest in the theoretical machine learning community for designing approaches with provable guarantees under test time attacks [AKM19, MHS19, MHS22] as well as renewed interest in distribution shift [BDBCP06, MMR08, HK19]. All the prior theoretical work in the literature has mainly focused on the effect of attacks or distribution shift on average error rate (e.g. (BDBCP06, AKM19J). However,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

this neglects a major relevant concern for users of machine learning algorithms, namely the ability to provide correctness guarantees for individual predictions: i.e., reliability.
In this work, we advance this line of work by developing a general understanding of how to learn reliably in the presence of corruptions changes to the test set, specifically under adversarial test-time attacks as well as distribution shift between the training (source) and test (target) data.
Our results. We consider algorithms that provide robustly-reliable predictions which are guaranteed to be correct under standard assumptions from statistical learning theory, for both test-time attacks and distribution shift. Our first main set of results tackles the challenging case of adversarial test-time perturbations. For this setting, we introduce a novel compelling reliability criterion on a learner that particularly captures the challenge of reliability under the test-time attacks. Given test point 2, a robustly-retiable classifier either abstains from prediction, or outputs both a prediction and a reliability guarantee ') with the guarantee that y is correct unless of two bad events has occurred: 1) the true target function does not belong to the given hypothesis set H. or, 2) a test-point 2 is perturbed from its original point by adversarial strength of at least 1) (measured in the relevant metric). In the case of distribution shift, we provide novel analysis and a complexity measure that extend the classical notion of reliable learning the setting when the test distribution is allowed be an arbitrary new distribution.
1.1 Summary of contributions
1.
We propose robustly-reliable learners for test-time attacks which guarantee reliable learning in the presence of test-time attacks. and characterize the region of instance space where they are simultaneously robust and reliable. Specifically, under the realizable setting, for adversarial perturbations within metric balls around the test points, we use the radius of the metric ball as a natural notion of adversarial strength. We output reliability radius with a guarantee that our prediction on point is correct as long as it was perturbed with a distance less than 1j (under a given metric). We further show that our proposed robustly-reliable learner achieves pointwise optimal values for this reliability radius: that is, no robustly-reliabe learner can output a reliability radius larger than our learner for any point in the instance space (Theorem B. B.2).
2. The pointwise optimal algorithm is easy to derive from our definition. We discuss a computation-
ally efficient implementation of the optimal learners. (Section 4).
3. We discuss variants of these algorithms and guarantees appropriate for three different variants of adversarial losses studied in the literature: depending on whether the perturbed point must have the same label as the original point, or in lieu of this, whether the algorithm should predict the true label of the perturbed point, or the same label as the original point (Definition 1).
4. We further introduce a safely-reliable reliable region, which captures the challenge caused by the adver- sary's ability to perturb a test point to cause a reduction in our reliability radius (Definition 6). As examples, we show that the safely-reliable region can be large for linear separators under log-concave distributions and for classifiers with smooth decision boundaries under nearly-uniform distributions and as a consequence, the robustly-reliable region is large as well (Theorem 3.3).
5. We extend this characterization to abstention -aased reliable predictions for arbitrary adversarial perturbation sets, where we no longer restrict ourselves to metric balls. We again get tight characterization of the robustly-reliable region (Theorem C.
We also consider reliability in the distribution shift setting where the test data points come from a different distribution. We introduce novel refinement to the notion of disagreement coefficient [Han07], to measure the transferability of reliability guarantees across distributions. We provide bounds on the probability mass of the reliable region under transfer for several interesting examples including, when learning linear separators, transfer from 31 log-concave to 32 log-concave and to s-concave distributions (Theorems G.I. G.2). We additionally bound the probability of the reliable region for learning classifiers with general smooth classification boundaries, for transfer between smooth distributions (Theorem G.3).
7. We further extend our reliability results to the setting of robustness tranfer, where the test data is simultaneously under adversarial perturbations as well as distribution shift (Section J).
8. Finally, we demonstrate that it is possible extend our results into the agnostic setting. (Section 7)
Conceptual advances over prior work. Prior works on certified robustness [SKL17, CRK19, WL.F22] have examined pointwise consistency guarantees. The certified robustness guarantee is only that prediction does not change with an adversarial perturbation, but it does not guarantee that the

---

prediction is correct (neither for the original point nor the perturbation); in particular, a constant function is always certified robust but may not be useful. In contrast, our notion of robustly-reliable learner guarantees that, for any test point x and perturbation 2, if has a distance less than to (1) = reliability radius), then the prediction will be "correct" (robust loss zero) in a sense informed by which robust loss we are addressing; we discuss this idea for several different losses, leading to different interpretations of this guarantee. In particular, for the stability loss, the prediction being "correct" means that it predicts the true label of the original point this implies certified robustness, but is even stronger, since it also guarantees the correct label. Prior work [BBHS22] introduces the notion of rebustly-reliable learner for poisoning attacks which is different from our definition that is tailored to test-time attacks with a guarantee in terms of reliability radius. In distribution shifts setting, we the first to assess the transferability of reliability guarantees which differ from widely-studied metric of average error rate. For additional related work, we refer to Appendix A.
2 Preliminaries and problem formulation
Let X' denote the instance space and y {0, 1} be the label space. Let H. be hypothesis class. The learner & is given access to a labeled sample = {(z,, } drawn from a distribution D over X' x x and learns a concept A X + y. In the realizable setting, we assume we have a hypothesis (concept) class H. and target concept h² E H such that the true label of any E X is given by h" (ar). In particular, S = {2,,, h (2:)) ym in this setting. Given the 0-1 loss function H X' > {00, 1}. define erry(h, {) = /M Einy)es 2)) We use Dx to denote the marginal distribution over X. We use T[-] to denote the indicator function that takes values in {0. 13. We also define B, rr) (h H (h)()( * h" (x)) I r) the set of hypotheses in H. that disagree
with h- with probability at most r. During test-time, the learner makes a prediction on test-point 2 E X. We consider the following settings
1. Adversarial test-time attack. We consider adversarial attacks with perturbation function 24 X > 2 that can perturb a test point æ to an arbitrary point z from the perturbation set set ((x)) S X [MHS19]. We assume that the adversary has access to the learned concept ht well as the test point v, and can perturb this data point to any 2 E (z) and then provide this perturbed data point to the learner test-time. We want to provide pointwise robustness and reliability guarantees in this setting. We will assume that x E (1x) for all x E X. For any point z, we have (= = {a E X|= E [x))), the set of points that can be perturbed to 2. We use perturbation to refer to a point: E (xx) and the perturbation sets (((x) interchangeably.
Distribution shift. We consider when a test point 2 is drawn from a different distribution from the training samples. In this case, we want to provide pointwise reliability guarantee. We will discuss more on this in Section 5.
2.1 Robust loss functions
In the applied and theoretical literature, various definitions of adversarial success have been explored, each dependent on the interpretation of robustness; depending on whether the perturbed point must have the same label as the original point, or in lieu of this, whether the algorithm should predict the true label of the perturbed point, or the same label the original point. To capture these, we formally consider the following loss functions.
Definition (Robust loss functions). For a hypothesis h, a test point x, and a perturbation U, we consider the following adversarially successful events.
1. Constrained Adversary loss [SZS* 14, BBSZ23]. There exists a perturbation 2 of x that does not change the true label of original point but h(2) is incorrect.
ei (h)
sup sEu(a)
u[h(z) + (2))
(a)=
For a fixed perturbation z E U()), define eC (h, 1[h(2) + (2) = (x)). 2. True Label loss [71.19, GKKW21J. There exists perturbation 2 of x such that h(z) is incorrect.
tht (h,z) = sup I[h(2) # (z)]
=El(())
3

---

Figure 1:
Different perturbation sets considered ETL, lsr (left), lCa (mid) and lA (right). The dashed line represents the decision boundary ht and the background color of red and blue represents the label and 1 respectively. The ball around each point describes the possible perturbation set U(x) and the shaded area inside each ball is the allowed perturbation. In &ST, perturbation in (x) while in fCA, we consider perturbations that do not change the true label of the perturbed point. Lastly, in ÉA,, an adversary only perturb points where the original true label is O.
consider all
In this case, if the true label of the changes, then the learner need to match its prediction with the new label. For a fixed perturbation 2 E (x), define lr (h, x, 2) = T[h(2) & h²(=)]. Stability loss [AKM19, MHS19, MHS22]. There exists a perturbation of such that h(z) is different from h" (z).
est (h sup T[((2) + (x))
=EU(Z)
In this case, focus on the consistency aspect where want the prediction of any perturbation 2 to be the same as the prediction of and this has to be correct w.E.t x i.e. equals to h" (x). For a fixed perturbation 2 U(xx), define th" (h, x, 2) = I[h(z) + (x)].
Incentive-aware Adversary loss [ZC21]. We take inspiration from economics application where we assume that the label 1 is more favorable outcome loan approval for which an adversary has no incentive to make any perturbation when the original label Define the perturbation
{u(x) ; (x) =0
{x} :h((x)= =1 Ua h²) [x)
and define incentive-aware adversary loss as
gh (h, sup =EMula,,h")
1[h(z) + h"" (x)).
For a fixed perturbation U(z), define eh (h, [[h(z) + hx(2)) A (x,
We say that robust to a perturbation function at I w.E.. a robust loss if gh (h, x:)
Remark. fST, lia are robust losses that we can always evaluate practice on the training data since we are comparing h(()) with 1e (x)) which is known us on the training data. For tCA, LTL- we are comparing h(2) with h (2) for which z may outside of the support the natural data distribution and we may not have access h (2). We illustrate the relationship between these losses by making a few useful observations.
In the robustly-realizable case [MHS20] when the perturbation function 24 does not change the true label of any x in the training or test data, then all the losses lcx, &TL, fsT are equivalent. This corresponds common assumption in the adversarial robustness literature, that the perturbations are cluuann-mperceptible which is usually quantified as the set of perturbations within a small metric ball around the data point.
We provide illustration of the perturbation set considered in various robust losses in Figure 1. By considering these perturbation set, we have the following implication fT. - Les, lST + &cs and fST + ly where e + lg means robustness w.r.t. E implies robustness w.r.t. Ez.

---

3 Robustly-reliable learners w.r.t. metric ball attacks
Although our robust losses are defined for any general perturbation set, we first consider the case where the perturbation sets are balls in some metric space. Such attacks are widely studied in the literature, in particular, for balls with bounded Ly-norm. Moreover, the radius of the metric ball serves natural notion of adversarial strength that allows to quantify the level of robustness. We will later (Theorem C.I) present results for general perturbation sets as well.
Let M = (X,d) be metric space equipped with distance metric d. We use the notation BM r) {a' E X d(x,z") I r (resp. MM (z, = {x's E X d(z, x') < rT) to denote a closed (resp. open) ball of radius centered at We will sometimes omit the underlying metrie M from the subscript to reduce notational clutter. We formally define a metric ball attack as follows.
Definition 2. Metric-ball attacks are defined as the class of perturbation functions UM = {u X' + 2* (x) = BM n)), induced by the metric M = (Xx,d d) defined over the instance space. MXX,
At test-time, given a test-point 2 E X, we would like to make a prediction at z with a reliability guarantee. We consider this type of learner, a robustly-reliable learner defined formally as follows.
Definition 3 (Relustt learner w.r.t. M-ball attacks). A learner L. is robustly-reliable w.r.f. M-ball attucks for hypothesis space H and robust loss function E. if. for any target concept he E H. given S labeled by h², the learner outputs functions hgg X + Y and r - - [0, oo) U (-1} such that for all x, E X if ffrr(2) = 77 > 0 and (x m)) then th (hS, x, 2) 0. Further, if (((2) 0. then h² (2) h2()).
Note that L outputs a prediction and a real value r (the "reliability radius") for any test input. -= -- -1 corresponds to abstention (even in the absence of perturbation) i.e. when the learner incapable of giving a reliability guarantee for that prediction), and r = 17 >> 0 is guarantee from the learner that if the adversary's 's attack is in B (Ir, 77) then we are correct i.e. if an adversary changes the original test point to 2, the attack will not succeed if the adversarial budget is less than 17. Lastly, when r 0,
0, the learner provides guarantee that the learner's prediction at is correct.
Definition 4 reelust region w.r.t. M-ball attacks). For a robustly-reliable learner L w.r.t M-ball attucks for sample S, hypothesis space H and robust loss function E desined above, the robustly-reliable region of L at a reliability level n is defined as RR RR((S,n) = {x E X r5)(z) 2n) n} for sample S and 1) 2 O.
The robustly-reliable region contains all points with reliability guarantee of at least 17. We use RRG to denote robustly-reliable regions with respect to losses lw for W (CA, TT, goal is to find robustly-reliable learner L that has the largest robustly-reliable region possible. First, we note that predictions that are known by the learner to be correct are still known to be correct even when the test points are attacked. Therefore, a test point lies in the robustly-reliabe w.r.t. ECA, ÊTL, as long as we can be sure that (=) )) is correct. This is equivalent to z being classified perfectly, i.e. according to the true label. Therefore, the robustly-reliable region w.r.t. fCA, f.. is given by the agreement region of the version space, which is the largest region where we can be sure of what the correct label is in the absence of any adversarial attack [EYW10]. We recall the definition of version space [Mit82] and agreement region [CAL94, BBL06].
natural
region
Definition 5. For a set H C H of hypothesis, and any set of samples S, les DIS(H) (x E X: Bhe, h2 H s.I. hi (x: # ha(x)) be the disagreement region and Agree( H) X' DTS(H)) be the agreement region. Let Ho(S) = (h E HI errs(h) (h) = 0} be version space: the set of all hypotheses that correctly classify S. More generally, HS) (h E H| ( S v) for 2
We can also characterize the rebustly region with respect to other robust losses in terms of the agreement region in the following Theorem.
Theorem 3.1. Let H be any hypothesis class. With respect to M--all attacks and for nj 2 O.
(a) there exists robustly-reliabh reliable learner L such that (RG 2 Aw, and (b) for any robustly- learner L, RRE, (S,1) C Aw.
Specifically, for the robust loss lw, the optimal robustly-reliable region Aw are
5

---

Robust loss Ew
Optimal robustly-reliable region Aw
(cA, ln
{z 2 E Agree(Ho(ss Ho(())}
ESt
Bz, n) S Agree Ho((S) A Ah(z)= h(z), VI E Bz n), Wh E Ho(S)}
li
(Ast n {z h (2) ()) (z = Agree(HH((S) (a) =
Proof. (Sketch) We provide the construction of the optimal robustly-reliable learner Copt such that RRY Cam (S) 2 Aw and later show that for any robustly-reliable learner L, we must also have RRW (S, 1)) C Aw. We start with lcA. (T., consider a learner Lops that predicts using ERM classifier and outputs lj oo for all points in the agreement region of Ho(S). Any prediction in (gree(HH((S) is reliable because it also agrees with he (h" E Ho(S) by realizability). On the other hand, for 2 E (TS(H)(S)), there exist h1, h2 E HS( that disagree on z. For any learner L, it is not possible to guarantee that & (z) is correct as we may have ht- = hı or h- h2.
Now, for fST. consider a learner Logt that classifies using an ERM but the reliability radius is now the largest 17 > 0 for which (z, n7) C Agree
and ((x) = h(z), V E (2, m), h E (S),), else rj = 0 if E (S))), and -1 otherwise. The first condition guarantees that h(x) = h (x))), Ve E (2 n). Combined with the second condition we have h(2) h(x) h (z). Vr (² n). Thus, Lopt is a robustly-reliabll
learner. On the other hand, for a robustly-reliable learner C,
consider z E R 17) for 1 > O. We must have (z) = hx(x,,, Vz E B² 77. Using a similar argument to the case for lCA, LTL we have E Agree( (S)))). ). If there exists r E (2,,,) m)) that I & Agree (S)), there exists h1, la E Ho(S)) that h (z) # h1 (1(2)) or (z((2) * hz(a)). It is not possible to guarantee that (2 = (2) as we may have h h1 or h² heg. Therefore, we must have (2, 7) S since this contradict with h(2) = h" hx(x). Therefore, we must have h² (x) = (2). Since we have E (gree(Ho(S)) this implies that h(x)) = 1(2)) for h E Ho(S). For L1. the construction is similar ŞST. For full proof, we refer to Appendix B.
Finally, we cannot have E B² 17) that h(2) (2) o h" (x)
For LST. the learner is able to certify a subset of the agreement region, which satisfies two additional conditions: by must be correct on all possible points x that could be perturbed to an observed test point and the true label of z should match the true label of z. We denote the second condition of h(2))= = h(x),, Vx E (2, 7). vh E Ho(S) as the label consistency condition. For liA, since robustness w.r.t. fsT implies robustness w.r.t. LA have Ast C AlA- In addition, with an incentive- aware adversary, whenever h(2) = 0, we must have h (x) = O since the adversary does not perturb data point with the original label 1. Therefore, we can additionally provide a guarantee z that lies in the agreement region and l=(z) O. We remark that we can identify the term h (z) for any point Agree(Ho
due the realizability assumption.
We have provided a reliatly learner with the largest possible robustly-reiaable region for losses &CA, LTL, fST, fIA. However, we note that the probability mass of the robustly-reliable region may not be a meaningful way to quantify the overall reliability of learner because a perturbation may lie outside of the support of the natural data distribution and have zero probability mass. It seems more useful to measure the mass of points x where any perturbation 2 of x still lies within the region.
robustly-reliable region. We formally define this region as the
Definition 6 (Safely-reliable reliable region w.I.t. M-ball attacks). Let L be robustty-reliable learner w.r.t. M-ball attacks for sample S. hypothesis class H and robust loss function f. The sefely-reliable region of learner L at reliability levels m, 7/2 is defined as
1. SREA m1, n2) = {x E X BM(2, m)) 0 {z| h 1x(2)) h² (x)) C RRE, 12,1))
2. SRf (S, 112112) fx E X BM(x,)) C
for W E ST),
3. SRE (S, M1 12) = (x E X | (x(x)) = A (M( C. (S, U {a E X Mx)x)
1 1AT (S,
The relelle region contains any point that retains a reliability radius of at least n22 even after being attacked by an adversary with strength 7). In the safely-reliable region, we consider a set of potential natural (before attack) points x, while in the robustly-reliable region, we consider a set of potential test points z. In the following subsections, we show that in interesting cases commonly studied in the literature, the probability mass of the safely-reliable region is actually quite large.

---

Figure 2: The cobustly-reliabbl region for fCA, LT, (left), EsT (mid) and lA (right) for linear separators with an L2-ball perturbation. The background color of blue and red represents the agreement region of class and respectively. In this case, we can remove the label consistency condition and reduce the robustly-reliable region into the 'r-bbuffered" agreement region.
3.1 Safely-reliable region for linear separators under log-concave distributions is large
We provide the probability mass of aafely-reliable regions with respect to different losses for linear separators when the data distribution follows an isotropic (mean zero and identity covariance matrix) log-concave (logarithm of density function is concave) distribution under bounded 7--norm ball attack. For full proof, we refer to Appendix D. We will rely on the following key lemma which states that the agreement region of linear separator cannot contain points that are arbitrarily close the decision boundary of h" for any sample S.
Lemma 3.2. Let be a distribution over IR and (h: x - sign( x)) wh E Rd, ||wall2 = 1} be a class of linear separators. For h' E for set of samples S ~ Dn such that there is data point in S that lies on the decision boundary, for any 0 < c < d, there exists 5(S, c, d) > 0 such that for any with S ||a||| S d and (wk,, 22) < 5, have x & Agroe(HH(SS)).
A direct implication of the lemma is that any L2-ball B(I, 1) that lies in the agreement region must contain the decision boundary of h² and must contain points with the same label. This allows us to remove the label consistency condition and instead focus on whether the ball B 77) lies in the agreement region. Intuitively, the reliable region now given by the '7p-buffered' agreement region where we only select points that have a distance at least from the boundary of the agreement region (Figure 2). We provide bounds for the probability mass of the safely-reliable region below and we refer to the full proof in Appendix D.
Theorem 3.3. Let D be isotropic log-concawe over IR and H. = {h - sign( (wn,, x)) wh E Rd ||w 1|2 = 1} be the class of linear separators. Let B(.,n) be a L2 ball perturbation with radius 77. For S ~ Dm for OO (VCdim(H) In }]), for for optimal robustly-reliable learner L,
(a) (S,
2m/1 -Ö(Vds) with probability at least 1-8. (b) SREA m, (S, (S,1) 17, 72) almost surely,
(c) P (S, 2 1 2(m + 72) - ((Vde) with probability at least 1- ô,
(d) PT(SRR (S, MT m2)) 2 (m + m2) Ō O(Vdz) with probability least 1 8.
The O-notation suppresses dependence on logarithmic factors and distribution constants.
We remark that we can't always remove the label consistency condition for a general perturbation set. For example, consider ((x)) = B(z 17) U {z) U JB + 17,, is made of two Ly balls with center I 0, I + a, with appropriate value a, 17, we may have each ball lie the different side of the agreement region that the whole perturbation set lie in the agreement region but contain points with different labels (Figure 3). We also provide bounds on the probability mass the safely-reliable region for more general concept spaces beyond linear separators, specifically, classifiers with smooth boundaries in Appendix E.
4 On computational efficiency
Given the definition, possible to implement computationally efficient robustly-reliable learners. For example, for linear separator concept classes under bounded L2-norm attack. The optimal
7

---

Figure 3: The perturbation is represented by two dashed balls. This lies inside the agreement region but contains points with different labels.
DIS(B(M
Distribution P Distribution Q
Agre .4))
A
Figure 4: The disagreement region and the agreement region under a distribution shift where and Q are isotropic (left) and where there is a mean shift (right).
robustly-reliable learner Cope. described above may be implemented via a linearly constrained quadratic program that computes the (squared) distance of the test point the closest point 2' in the disagreement region. This gives us the reliability radius, since for linear separators one must cross decision boundary to perturb point to a differently labeled point
min 2'11 Wow!
s.t.
(w, 2i)y 2 0,
for each (x;, y1) E S,
(w', x1)y/ 2 O, (w, (10', S O.
for each (I;, y1) E S,
Given training sample S, for any given point z, the learner L can efficiently compute the solution s* the above program and output vs* as the reliability radius. We show that the variant of this objective also provides a reliability radius for a wide range of hypothesis classes under L2 ball attacks (see Lemma F. In addition, lower bound on the reliability radius || 2" 11,, when 2" is the solution of
relax this objective into regularized objective that gives
hy, 12, 2" argmin 6,h'2²
1|2-211 XRR(h, S ((2', 01)) R(M, SU ((s(,1)))
when fe(h,S) S) is the empirical risk of h on S. We provide more detailed discussion in Appendix
5 Robustly-reliable learning under distribution shift
We now consider the reliability aspect for distribution shift, a different kind of test-time robustness challenge when the test data comes from a different distribution than the training data. Formally, let P be the training distribution and let Q be the test distribution. We assume the realizable distribution shift setting, i.e. there is target concept h² E H such that the true label of any x X given by h" (z) at training time and test time, errp (h") erro(h" 0. As observed earlier, points that

---

are known by the learner to be correct (reliable) are still known to be correct even when it is drawn from different distribution. This reliability guarantee holds even when the distributions P and Q do not share a common support, setting for which many prior theoretical works result in vacuous bounds. For example, suppose X' = TR.", P and Q are supported on disjoint n-balls, and H the class of linear separators. Then the total variation distance, the H H-divergence [KBDG04, BDBC* 10] as well as the discrepancy distance [MMR08] between P and Q are all 1. While recent work of [HK19) 19] does apply in this setting, they do not focus on the reliability guarantee. In this work, we interested in quantifying the transferability of reliability guarantee transfer between distributions P and Q We recall the notion of reliable prediction [EYW10].
Definition 7 (Reliability). A learner L is reliable w.E.t concept space H if. for any target concept h" H. given any sample S labeled by h", the learner outputs functions h XX y and as x {0, 1} such that for all E X if(g(z)
then h5(z)) (z) h- (z). Else, if ffa(()) = 0, the learner abstains from prediction. The reliable region of C R (S) - {ar X d5(x)) 1}.
We define the following metric to measure the reliability of a learner under distribution shift.
Definition 8 (P-Q reliable correctness). The P --rreliabll correctness of L (at sample rate m, for distribution shift from P to Q) is defined as the expected probability mass of its reliable region under Q when trained on random training S ~ pm, i.e. PIa-Q.S~PP |= E (S)].
The disagreement coefficient was originally introduced study the label complexity in agnostic active learning [Han07] and is also known to characterize reliable learning in the absence of any distribution shift EEY. We propose the following refinement to the notion of disagreement coefficient, which we will use to give bounds on a learner' P-+Q reliable correctness.
Definition 9 (P+Q disagreement coefficient). For a hypothesis class H. the P- disagreement coefficient of h² E H with respect to H is given by
Pro[DSs Dro((Dis ,r)]
Op-Q(E) sup r2z
where Bp(h", r) = (h E H Prp[h(x) + (x))
Q among classifiers which are within disagreement-bale balls w.r.t. h- under P, relative to the version space radius. The proposed metric is asymmetric between P and 2, and also depends on the target concept h². More simple examples are in Appendix H. We show that the P-r--bilab correctness of our learner may be bounded in terms of the P-2 disagreement coefficient using uniform convergence based argument. The proof details are in Appendix I.
This quantifies the rate of disagreement
Theorem 5.1. Let Q. be a realizable distribution shift of P with respect to H. and h E H be the target concept. Given sufficiently large sample size 2 -h (d })) the P-+--reliablee correctness of L., the optimal vobustly-reliable learner, is at least
Pr E (S) 1 -
Here e is an absolute constant, and is the VC-dimension of H.
In Appendix J, we show that this P Q disagreement coefficient can be small for several examples which implies that it is possible to transfer the reliability guarantee from one distribution to the other. In particular, when learning linear separators, we provide bounds for transferring from 31 log-concave to 32 log-concave and to s-concave distributions (Theorems G. G.2). In addition, when learning classifiers with general smooth classification boundaries, we provide bounds for transferring between smooth distributions (Theorem G.3).
6 Safely-reliable correctness under distribution shift
There is growing practical [SSZ*20, SIE+200 as well as recent theoretical interest [DGH+23) in the setting of "robustness transfer', where one simultaneously expects adversarial test-time attacks as well as distribution shift. We will study the reliability aspect for this more challenging setting. We note that the definition of robustly-reliabbe learner does not depend on the data distribution (see

---

Definition 3) as the guarantee is pointwise. Our optimality result in Section applies even when test point drawn from a different distribution 2. In this case, the sufely-reliable region instead would have different probability mass.
Definition 10 (P-Q safely-reliable correctness). The P-2 safely-reliable correctness of L (at sample rate m, for distribution shift from P to Q, w.r.l. robust loss {) is defined as the probability mass of its safely-reliable region under Q, on sample 5 ~ pm, i.e.
PQR (S, T1, T2)
Pr 2~Q.5~
lxc E SR (S, 72)].
We consider example when the training distribution P is isotropic log-concave and the test distribution 2, is log-concave with its mean shifted by μ but the covariance matrix is still an identity matrix (see Figure 4, right). We provide the bound on the p-2 safely-reliable correctness of this example in Appendix (see Theorem J.2).
Reliability in the agnostic setting
In the above, we have assumed that the training samples S are realizable under our concept class H. ie, there a target concept ht consistent with our (uncorrupted) data. the agnostic setting, we can have minseH (rr)(h) > O, meaning no single concept is always correct. We define a u-tolerably robustly-reliable learner under test-time attacks in the agnostic setting as the learner whose reliable predictions agree with every low-error hypothesis (error most v) the training sample ([BBHS22] have proposed the corresponding definition for data poisoning attacks).
Definition 11 (v-tolerably robustly-reliable learner w.r.t. M--all attacks). A learner L is robustly- reliable w.r.t. M-ball attacks for sample S, hypothesis space H and robust loss function
for every concept h" E H. with sh") < v. the learner outputs functions h X - Y and rŠ : X + [0, co) U {-1} such that for all x, 2 E X if r5(2) = > 0 and z E (x, then th (hg. 2)
0. Further, if (r)(2) = 0, then h²) = hg(2). Given sample S such that
some concept h" E H satisfies c S v, the robustly- reelille region of L defined as
RR v1 = {ar E X r5(x)) 2 n) for v 2 O.
We generalize our results from Section 3 to the agnostic setting (proof details in Appendix K). Here (5) {h E H errs(h) S v).
Theorem 7.1. Let H. be any hypothesis class. With respect to M-ball attacks and CCA. for n 2 0,
(a) There exists a robustly-reliabe learner such that RR (S, u. 1)) 2 Agree(H.
(b) For any robustly-reliable learner L. RRAa,S, C (S))).
Discussion
In this work, we generalize the classical line of works on reliable learning to address challenging test-time environments. We propose a novel reliablyyrllaabiiiyy criterion that is applicable to sev- eral variations of test-time attacks. Our analysis leads to an easy-to-derive algorithm that can be implemented efficiently in many cases. Additionally, we introduce P + Q disagreement coeffi- cient to capture the transferability of the reliability guarantee between distributions. The proposed robustly-reliabilie criterion and the p - Q disagreement coefficient together provide a compre- hensive framework for handling test-time attacks and evaluating the reliability of learning models. This contributes to the advancement of reliable learning methodologies in the face of challenging real-world scenarios, facilitating the development of more resilient and trustworthy machine learning systems. Notably, key questions remain open, including, how to efficiently implement the algorithm for a class of neural networks, and how to learn reliably with respect any general robust loss function?
Acknowledgements
This work was supported in part by NSF grants CCF-1910321 and SES-1919453, the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003, a Bloomberg Data Science PhD fellowship, and a Simons Investigator Award.
10

---

References
[AB99] Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 1999.
[ABGLPI9] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 1907. 02899, 2019.
[ABHUI5] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory, pages 167-190. PMLR, 2015.
[ABL14] Pranjal Awasthi, Maria Florina Balcan, and Philip Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing, pages 449-458, 2014.
[AK91] David Applegate and Ravi Kannan. Sampling and integration of near log-concave functions. In Proceedings of the twenty-thirl annual ACM Symposium on Theory of Computing, pages 156-163, 1991.
[AKM19] Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for robust learning. In Algorithmic Learning Theory, pages 162-183. PMLR, 2019.
[BHHS22] Maria-Florina
Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly- reliable learners under poisoning attacks. In Conference Learning Theory. PMLR, 2022.
[BBL06] Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceedings of the 23rd International Conference on Machine Learning, pages 65-72, 2006.
[BBS07] Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning for differing training and test distributions. In Proceedings of the 24th International Conference on Machine Learning, pages 81-88, 2007.
[BBS723] Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, and Hongyang Zhang. On the power of abstention and data-driven decision making for adversarial robustness. Journal of Machine Learning Research, 2023.
[BCKW15] Charles Blundell, Julien Corneiise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learning, pages 1613-1622. PMLR, 2015.
[BDB++10 10] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine Learning, 79:151-175, 2010.
[BDBCP06] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances in Neural Information Processing Systems, 19, 2006.
[BH21] Maria-Florina Balcan and Nika Haghtalab. Noise in classification. Beyond the Worst- Case Analysis of Algorithms, page 361, 2021.
[BL13] Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log-com concave distributions. In Conference on Learning Theory, pages 288-3 316. PMLR, 2013.
[BPRZ23] Maria-Florina Balcan, Rattana Pukdee, Pradeep Ravikumar, and Hongyang Zhang. Nash equilibria and pitfalls of adversarial training in adversarial robustness games. In The 26nd International Conference on Artificial Intelligence and Statistics. PMLR, 2023.
11

---

[BZ17] Balcan and Hongyang Zhang. Sample and computationally efficient learning algorithms under s-concave distributions. Advances Neural Information Processing Systems, 30, 2017.
[CAL94] David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine Learning, 15:201-221, 1994.
[CDG+18 18] Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. In International Conference on Machine Learning, pages 1059-1067. PMLR, 2018.
[CDM16] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention, Ad- vances in Neural Information Processing Systems. 29, 2016.
[CRK19] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
19] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Perey S Liang. Unlabeled data improves adversarial robustness. Advances in Neural Information Processing Systems, 32, 2019.
[CW17] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE symposium on security and privacy, pages 39-57. IEEE, 2017.
[CWG+ 19] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with tabel-distrbuttin--aaar margin loss. Advances in Neural Information Processing Systems, 32, 2019.
[Dan16] Amit Daniely. Complexity theoretic limitations on learning halfspaces. In Proceedings of the forty-eighth annual ACM Symposium on Theory of Computing, pages 105-117, 2016.
[DGH+23] Yuyang Deng, Nidham Gazagnadou, Junyuan Hong, Mehrdad Mahdavi, and Lingjuan Lyu. On the hardness of robustness transfer: A perspective from Rademacher com- plexity over symmetric difference hypothesis space, arXiv preprint arXiv:2302.12351, 2023.
[DGT19] Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indepennn pac learning of halfspaces with massart noise. Advances in Neural Information Pro- cessing Systems, 32, 2019.
[DN21] John Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 4 2021.
[EYW10] Ran El-ya and Yair Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(5), 2010.
[EYW12] Ran El- Ya-Ya and Yair Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2), 2012.
[GG16] Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning. pages 1050-1059. PMLR, 2016.
[GKKM20] Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. Advances in Neural Information Processing Systems, 33: 15579155770 2020.
[GKKW21] Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell. On the hard- ness of robust classification. The Journal of Machine Learning Research, 22(1):12521: 12549, 2021.
12

---

[GPSW17] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
[GSS15] lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations, 2015.
[Han07] Steve Hanneke. bound on the label complexity of agnostic active learning- In Proceedings of the 24th International Conference on Machine Learning, pages 353- 360, 2007.
[6GB+06) Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. Advances in Neural Information Processing Systems, 19, 2006.
[K19] Steve Hanneke and Samory Kpotufe. On the value of target data transfer learning. Advances in Neural Information Processing Systems, 32, 2019.
[KLM20]] Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Noise-tolerant, reliable active classification with comparison queries. In Conference Learning Theory, pages 1957-2006. PMLR, 2020.
[JSH20] Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoff's in adversarial training for linear regression. In Conference on Learning Theory, pages 2034 2078. PMLR, 2020.
[KBDG04) Daniel Kifer, Shai Ben-David, and Johannes Gehrke. Detecting change in data streams. In VLDB, volume 4, pages 180-191. Toronto, Canada, 2004.
[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal Computing, 3766:1777-1105, 2008.
[KV94] Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.
[LAG+19] 19] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy, pages 656-672. IEEE, 2019.
[LCWC19] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems, 32, 2019.
[LPB17] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scal- able predictive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems, 30, 2017.
[LV07] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures Algorithms, 30(3):307-358, 2007.
[LWS18] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning. pages 3122-3130. PMLR, 2018.
[MHS19] Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly leamablle, but only improperly. In Conference on Learning Theory, pages 2512-2530. PMIR, 2019.
[MHS20] Omar Montasser, Steve Hanneke, and Nati Srebro. Reducing adversarially robust learning non-robust pac learning. Advances Neural Information Processing Systems, 33: 146666146377 2020.
13

---

[MHS21] Omar Montasser, Steve Hanneke, and Nathan Srebro. Adversarially robust learning with unknown perturbation sets. Conference on Learning Theory, pages 3452-3482. PMLR, 2021.
[MHS22] Omar Montasser, Steve Hanneke, and Nathan Srebro. Adversarially robust learning: A generic minimax optimal learner and characterization. Advances in Neurul Information Processing Systems, 2022.
[MIG 19] Wesley J Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gor- don Wilson. A simple baseline for bayesian uncertainty deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[Mit82] Tom M Mitchell. Generalization search. Artificial Intelligence, 18(2)2003-226, 1982.
[MMR08] Yishay Mansour, Mchryar Mohri, and Afshin Rostamizadeh. Domain adaptation with multiple sources. Advances in Neural Information Processing Systems, 21, 2008
[MSS 18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[MTR+21] John P Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution generalization. In International Conference on Machine Learning, pages 7721-7735. PMLR, 2021.
[ND16] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distribution- ally robust optimization with f-divergences. Advances in Neural Information Processing Systems, 29, 2016.
[PY10] Sinno Jialin Pan and Qiang Yang. A survey transfer learning. IEEE Transactions knowledge and data engineering, 22(10):1345-1333 2010.
[PZ21] Nikita Puchkin and Nikita Zhivotovskiy. Exponential savings in agnostic active learning through abstention. In Conference on Learning Theory, pages 3806-3832, PMLR, 2021.
[QCSSL08] Joaquin Quinonero- Cuinenaro-Candela. Masashi Sugiyama. Anton Schwaighofer, and Neil D Lawrence. Dataset shift machine learning. MIT Press, 2008
[RRR21] Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In International Conference Learning Representations, 2021.
[RRSS19] Benjamin Recht, Rebecca Roclofs, Ludwig Schmidt, and Vaishaal Shankar. Do im- agenet classifiers generalize to imagenet? In International Conference on Machine Learning, pages 2389-5400, PMLR, 2019.
[RS88] Ronald L Rivest and Robert H Sloan. Learning complicated concepts reliably and usefully. In Association for the Advancement of Artificial Intelligence, pages 635-640, 1988.
[RWK20] Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pages 8093-8104. PMLR, 2020.
IRXY+201 20] Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. In Pro- ceedings of the 37th International Conference on Machine Learning, pages 7909-7919, 2020.
[Shi00] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weight- ing the log-likelihood function. Journal of Statistical Planning and Inference, 90(2):227- 244, 2000.
14

---

[SIE*20] 20] Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? Advances in Neural Informa- Lion Processing Systems, 33:3533-3545, 2020.
[SKHL20] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distribution- ally robust neural networks. In International Conference on Learning Representatioss 2020.
[SKL17] Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. Advances in Neural Information Processing Systems, 30, 2017.
[SNG+19) Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Advances in Neural Information Processing Systems, 32, 2019.
[SS16] Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In Computer Ussion-ECCV 2016 Workshops: Amsterdam, The Netherlands, October 8-10 and 15-16, 2016. Proceedings, Part III 14, pages 443-450. Springer, 2016.
[8ST+18] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. Advances in Neural Information Processing Systems, 31, 2018.
[SSZ + 20] Ali Shafahi, Parsa Saadatpanah, Chen Zhu, Amin Ghiasi, Christoph Studer, David Jacobs, and Tom Goldstein. Adversarially robust transfer learning. In International Conference Learning Representations, 2020.
14]S+14] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
[TKP* 18] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. In Interna- tional Conference on Learning Representations, 2018.
[TS10] Lisa Torrey and Jude Shavlik. Transfer learning. In Handbook of research on machine learning applications and trenuls: algorithms, methods, and techniques, pages 242-264. IGI global, 2010.
[TSE* 19] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Alek- sander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representations, 2019.
[Vap98] Vladimir N Vapnik. Statisticul learning theory. Wiley-Interscience, 1998.
[vdVW96] Aad W van der Vaart and Jon A Wellner. Weak convergence. Springer, 1996.
[Wanll] Liwei Wang. Smoothness, disagreement coefficient, and the label complexity of agnostic active learning. Journal of Machine Learning Research, 12(7), 2011.
[WLF22) Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In International Confer- ence on Machine Learning, pages 22769-22783. PMLR, 2022.
[WR06] Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. MIT press Cambridge, MA, 2006.
[YCJ16] Songbai Yan, Kamalika Chaudhuri, and Tara Javidi. Active learning from imperfect labelers. Advances in Neural Information Processing Systems, 29, 2016.
[7C21] Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5797-5804, 2021.
15

---

[ZL19] Yuchen Zhang and Percy Liang. Defending against whitebox adversarial attacks via randomized discretization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 684 693. PMLR, 2019.
[ZLLJ19] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In International Conference on Machine Learning. pages 7404-7413, PMLR, 2019.
[ZLW120] Yuchen Zhang, Mingsheng Long, Jianmin Wang, and Michael I Jordan. On localized discrepancy for domain adaptation. arXiv preprinl arXiv:2008.062: 2020.
[ZN22] Yinglun Zhu and Robert D Nowak. Efficient active learning with abstention. In Advances Neural Information Processing Systems, 2022.
[XY]+19] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning, pages 7472-7482, PMLR, 2019.
16


Reviews:
[{"review_id": "aaOf19YUWd", "reviewer": "Reviewer_LDC7", "summary": "This paper studies the problem of classification under found different kinds of adversarial loss functions:\n1) ST which I think is by far the most popular adversarial loss. This is same as the expected sup loss of [Madry et al. 2018](https://arxiv.org/abs/1706.06083).\n2) TL which is equivalent to the the \"exact in the ball\" risk of [Gordeau et al](https://www.jmlr.org/papers/volume22/20-285/20-285.pdf) or the \"error region risk\" of [Diochnos et al](https://proceedings.neurips.cc/paper_files/paper/2018/file/3483e5ec0489e5c394b028ec4e81f3e1-Paper.pdf)\n3) IA which is the same as ST but where the adversary only perturbs points belonging to one of the two labels\n4) CA loss which is the same as TL with the additional constraint that the true label does not change at the perturbed point. \n\nFor each type of loss, the paper establishes the \"optimal robustly reliable region\". Here, the classification is deemed reliable if the the classification is correct on the _perturbed ppoint_. The papers shows that these regions can be computed efficiently for simple hypothesis classes like linear classifiers. The paper also proves lower bounds on \"safely-reliable region\" for linear separators under log-concave distributions, where a point is classified safely reliably at $\\eta_1, \\eta_2$ levels if it can be reliably classified at $\\eta_2$ level, even when perturbed in a ball of radius $\\eta_1$.\n\nFinally, the paper also lower bounds the amount by which the reliability region can change under a distribution shift from P to Q in terms of a $P\\to Q$ disagreement coefficient. \n\n", "questions": "- Definition 7 is unclear: What is z in line 296? I think it should be any x' in U(x).\n- I would recommend cutting down on the size of section 1.1: summary of contributions. \n- It would be good to have more examples to accompany the definitions, for instance contrasting the reliable vs safely-reliable notions.  \n\nI would also like the authors to comment on my view of the paper in the \"weaknesses\" section. ", "limitations": "Yes. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Generality: The results of the paper hold for 4 kinds of adversarial loss functions, each with different use-cases. \n- Nice result on reliable learning under distribution shift: Theorem 5.3 proves a connection between reliable learning under distribution shift, and a previously studied notion called the disagreement coefficient. This connection appears interesting and non-trivial. ", "weaknesses": "- Writing: The paper is very difficult to read. There are many new definitions but very few illustrations / examples. The paper seems to be written in a hurry. Some of the results that are listed under main contributions in section 1.1 only appear in the appendix. Section 6 is super short - it only presents one new definition, followed by an example satisfying the definition the details of which are relegated to the appendix. \n- Limited contributions: The paper makes limited contributions on the \"safely-reliable\" notion of classification (Definition 6), which I think is much more important than the notion of \"reliable\" classification (Definition 3, 4). Theorem 3.3 on probability mass on reliable region only holds for the special case of linear separators with isotropic log-concave distributions. Section 6 on safely-reliable correctness under distribution shift establishes the safely-reliable correctness again only for the special case of linear separators with isotropic log-concave distributions. Further, the shifted distribution is also assumed to only shift in mean, while the covariance matrix remains as Identity matrix. Section 4 also focuses on simple settings like linear separators. \n\n- Limited applicability of the notion of \"reliability\":  I want to stress again that the \"safely-reliable\" notion is more important than the \"reliable\" notion. The importance of safely-reliable region over the reliable-region is stated by the authors themselves in lines 216-218: \"...we note that the probability mass of the robustly-reliable region may not be a meaningful way to quantify the overall reliability of a learner because a perturbation may lie outside of the support of the natural data distribution and have zero probability mass.\" Basically, a classifier can be robustly reliable at z with level $\\eta$ even if predicts a different label at a slightly perturbed point x such that d(x, z) < $\\eta$. Hence, reliability does not ensure robustness against adversarial attacks. Literature on certified robustness (for example, randomized smoothing, interval bound propagation) all focus on something like the \"safely-reliable\" notion rather than reliable. In lines 91-94, the paper says \"Prior works have examined pointwise consistency guarantees [SKL17, CRK19, WLF22], i.e. the classifier’s prediction is guaranteed not to have changed under an attack. In contrast, we study a much more desirable property of reliability—guaranteeing that the prediction of the algorithm is correct.\" I would like to see the paper make a stronger case advocating for the study of reliability than the one given here. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness**\n> 1. Writing:  \n\nWe will use the extra page in the camera-ready version to bring to the main body some of the results that now appear in the Appendix. Concerning illustrations, we already have 4 illustrations in the main body and in fact, the other reviewers appreciated the clarity and the many examples. “The submission is well organized and clearly written overall.” (Reviewer uQQ5) and “The paper is well written with many intuitive illustrations.” (Reviewer 8X7Z).\n\n> 2. Limited contributions: \n\nWe respectfully disagree on the limited contribution of our paper. Our main contributions are numerous and we are happy to clarify this in the camera-ready version. First of all, coming up with the right definitions to express our concepts, in particular,  robustly-reliable learner (Definition 3), robustly-reliable region (Definition 4) and safely-reliable region (Definition 6). Given these definitions, we work out the abstract results;  Theorem 3.1 provides an optimal characterization of the robustly-reliable region for any hypothesis class (which further implies optimality of the safely-reliable region); Theorem 5.1 for safely-reliable correctness is also applicable to general settings. Additionally, we have numerous examples. The result presented in the main paper such as in Theorem 3.3 is one concrete example that the safely-reliable region can be large.  We also have additional results for a much more general class of classifiers with smooth boundaries in Appendix E and G  for both safely-reliable region (implies bound on safely-reliable correctness) and reliability under distribution shift.  \n\nIn particular, we address individual points below.\n\n-  “The paper makes limited contributions on the \"safely-reliable\" notion of classification (Definition 6), which I think is much more important than the notion of \"reliable\" classification (Definition 3, 4).”\n\nWe disagree with this characterization. Definition 6 implies that our tight characterization of the optimal robustly-reliable region extends to the safely-reliable region as they are closely related for each robust loss function. Moreover, our examples that compute the probability masses focus on the safely-reliable region instead of the robustly-reliable region (Theorem 3.3, Appendix E ).\n\n- “Theorem 3.3 on probability mass on reliable region only holds for the special case of linear separators with isotropic log-concave distributions.”\n\nWe also provide bounds on the probability mass of the safely-reliable region for general smooth classifiers (Lines 263-264, Appendix E, Theorem E.3).\n\n-  “Section 6 on safely-reliable correctness under distribution shift establishes the safely-reliable correctness again only for the special case of linear separators with isotropic log-concave distributions.”\n\nBy Definition 10, our previous results on the safely-reliable region of smooth boundary classifiers also extend to the “safely-reliable correctness” in Section 6. We mention the mean-shift example to highlight the advantage over previously studied measures like $\\mathcal{H}$-divergence and the discrepancy distance.\n\n-  “Section 4 also focuses on simple settings like linear separators.”\n\nWe extend beyond the linear separator to a wide range of hypothesis classes in Appendix F.\n\n> 3. Limited applicability of the notion of \"reliability\": \n\n\n\nWe would like to clarify this major misunderstanding between the robustness and reliability guarantee. The prior work on certified robustness [SKL17, CRK19, WLF22] is different from our proposed notion of safely-reliable. The certified robustness guarantee is only that a prediction does not change with an adversarial perturbation, but it does not guarantee that the prediction is correct (neither for the original point nor the perturbation); in particular, a constant function is always certified robust but it may not be useful. In contrast, a robustly-reliable learner guarantees that, for any test point $x$ and perturbation $z$, if $z$ has distance less than $\\eta$ to $x$ ($\\eta$ = reliability radius), then the prediction will be “correct” (robust loss zero) in a sense informed by which robust loss we are addressing; we discuss this idea for several different losses, leading to different interpretations of this guarantee.  For the stability loss, the prediction being “correct” means that it predicts the true label of the original point $x$; in particular, this implies certified robustness, but is even stronger, since it also guarantees the correct label.  For the “true label” loss, being “correct” means that it predicts the true label of the perturbation $z$.  For the “constrained adversary” loss, being “correct” means predicting the true label for both $x$ and $z$ assuming the adversary would only perturb $x$ to $z$ if they have the same true label.\n\nTo summarize, for a given robust loss function, a robustly-reliable region (Definition 4) is a region where points in this region are guaranteed to have a zero robust loss (to be “correct”). A safely-reliable region further guarantees that even after a perturbation of some distance $\\eta_1$, the point is still in the robustly reliable region for some radius $\\eta_2$.  So being safely-reliable means the algorithm is robust against adversaries trying to perturb a point $x$ to a $z$ where the learner is less “confident” (i.e., outputs a small reliability radius).\n\n**Questions**\n\n1. Thank you for pointing this out, this is a typo. It is supposed to be $h(x) = h^*(x)$.\n2. We will address this in the camera-ready version.\n3. Thank you for your comment. The safely-reliable region is indeed the same as the reliable region when there is no adversarial perturbation. We will make this clearer in the final version.\n\n"}, {"review_id": "4mhLcDC5hG", "reviewer": "Reviewer_uQQ5", "summary": "This paper presents robustly-reliable learners with optimal guarantees for environments where the training and test data are not drawn from the same distribution, e.g., natural distribution shift and adversarial attacks during test time. The main idea is that for a given point, the robustly-reliable learner either outputs a prediction and a reliability region, or abstains from prediction. The prediction is guaranteed to be correct as long as the test-time perturbation is constrained to this reliability region.", "questions": "Is there an efficient method for other types of classifiers and loss functions, such as neural networks?", "limitations": "The limitations are not discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* Designing reliable learners with guarantees for challenging environments is highly important and relevant to both the theoretical and applied machine learning community. \n* It seems likely that other researchers will find relevant the reliability criterions and tools developed in the paper.\n* The approach appears to be novel and technically sound. The claims of the paper are well-supported by extensive proofs.\n* The submission is well organized and clearly written overall.\n", "weaknesses": "\n* A computationally efficient method is presented only for the case of linear separators. It is not clear how easily the presented tools can be used to obtain practical algorithms for more general cases (e.g., neural networks) in practice.\n* An evaluation on a simple synthetic scenario to demonstrate the empirical effectiveness of the approach would make the paper more compelling. This is a minor point given that this is clearly a theory paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> A computationally efficient method is presented only for the case of linear separators. It is not clear how easily the presented tools can be used to obtain practical algorithms for more general cases (e.g., neural networks) in practice.\nAn evaluation on a simple synthetic scenario to demonstrate the empirical effectiveness of the approach would make the paper more compelling. This is a minor point given that this is clearly a theory paper.\n\nThank you for your comment. We agree that a computationally efficient method for a general hypothesis class such as neural networks is an interesting direction. Since our main purpose for the paper is developing theory, we would defer the empirical evaluation of the methods and extension to neural networks to future application-oriented research."}, {"review_id": "XkPWwpE7aO", "reviewer": "Reviewer_8X7Z", "summary": "The authors explore advesarial test-time attacks and distribution shift. They propose a learning algorithm with performance guarantees.\n", "questions": "Can slack be added to the quadratic program in section 4 in the same manner as it is done for SVMs?\n\nFor the regularized objective in section 4, what good is a lower bound on the reliability radius? It can guarantee an unreliable prediction is unreliable, but cannot guarantee a reliable prediction is reliable. Yet it's the later case that is needed to not refuse for reliable test points.\n", "limitations": "Limitations are adequately addressed", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well written with many intuitive illustrations. \nThe authors use refusal as a means to guarantee reliability. As noted by the authors, the trivial classifier that always refuses is reliable. Therefore, I particularly liked section 3.1, which characterizes the probability of refusal (or non-refusal). The concept of reliability radius is readily understandable.\n\nThe algorithms provided in section 4 can be efficient enough for many real-world applications. \n", "weaknesses": "The authors' analysis is limited to the realizable case; that the true target function is a member of the hypothesis class. While this simplifies analysis, it limits the applicability of the authors' results since in most real-world applications we do not know whether this assumption is valid. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses** \n\n> The authors' analysis is limited to the realizable case; that the true target function is a member of the hypothesis class. While this simplifies analysis, it limits the applicability of the authors' results since in most real-world applications we do not know whether this assumption is valid.\n\nThank you for your feedback. We agree that the realizable assumption may not hold in most real-world applications.  Starting by studying the realizable case helps to build intuition for what definitions and results are appropriate and possible in general.  This follows a well-established pattern of developing theories in the learning theory literature.  Fortunately, as we discuss below, extension to the non-realizable (agnostic) setting is possible, building from the definitions and concepts we have developed in the realizable case.\nWe illustrate this for the true label loss $\\ell_{\\text{TL}}$ loss below, and remark this can be similarly done for the other loss functions studied in our work.\n\n**Definition**: A learner $\\mathcal{L}$ is *$\\nu$-tolerably* robustly-reliable w.r.t. $\\mathcal{M}$-ball attacks for sample $S$, hypothesis space $\\mathcal{H}$ and robust loss function $\\ell$ if, for every concept $h^*\\in\\mathcal{H}$ with $\\mathrm{err}\\_{S}(h^*)\\le\\nu$, the learner outputs functions $h^\\mathcal{L}\\_{S}:\\mathcal{X} \\to \\mathcal{Y}$ and $r^\\mathcal{L}\\_{S}:\\mathcal{X} \\to [0,\\infty)\\cup\\\\{-1\\\\}$ such that for all $x,z\\in \\mathcal{X}$ if $r^\\mathcal{L}\\_{S}(z)=\\eta > 0$ and $z\\in \\mathbf{B}^o\\_\\mathcal{M}(x,\\eta)$ then $\\ell^{h^*}(h^\\mathcal{L}\\_{S},x,z)=0$. Further, if $r^\\mathcal{L}_{S}(z) = 0$, then $h^*(z)=h^\\mathcal{L}\\_{S}(z)$.\n\nGiven sample $S$ such that some concept $h^*\\in\\mathcal{H}$ satisfies $\\mathrm{err}\\_S(h^*)\\le \\nu$, the robustly-reliable region of $\\mathcal{L}$ is defined as $RR^{\\mathcal{L}}(S,\\nu,\\eta)=\\\\{x\\in\\mathcal{X}\\mid r^\\mathcal{L}\\_{S}(x) \\ge \\eta\\\\}$ for $\\nu,\\eta\\ge 0$. \n\nWe can prove the following theorem (stated below for the true label loss $\\ell\\_{\\text{TL}}$) which gives pointwise optimal bounds on the robustly-reliable region. \n\n**Theorem**: Let $\\mathcal{H}$ be any hypothesis class with respect to $\\mathcal{M}$-ball attacks and robust loss function $\\ell\\_{\\text{TL}}$, for $\\eta\\ge 0$,\n - There exists a robustly-reliable learner $\\mathcal{L}$ such that $RR^{\\mathcal{L}}\\_{\\text{TL}}(S,\\nu,\\eta)\\supseteq \\text{Agree}(\\mathcal{H}\\_\\nu(S))$,\n- For any robustly-reliable learner $\\mathcal{L}$, $RR^{\\mathcal{L}}\\_{\\text{TL}}(S,\\nu,\\eta)\\subseteq \\text{Agree}(\\mathcal{H}\\_\\nu(S))$\n\nwhere $\\mathcal{H}\\_\\nu(S) = \\\\{h \\in \\mathcal{H} \\mid \\mathrm{err}\\_S(h)\\le \\nu\\\\}$. Furthermore, the safely-reliable region for robust loss function $TL$ is defined as $SR\\_{TL}^{\\mathcal{L}}(S,\\nu,\\eta_1,\\eta_2)=\\\\{x\\in\\mathcal{X}\\mid \\mathbf{B}\\_\\mathcal{M}(x,\\eta_1)\\subseteq RR\\_{TL}^{\\mathcal{L}}(S,\\nu,\\eta_2)\\\\}$. Thus, the above theorem implies bounds on the safely-reliable region as well.\n\n\nWe will include the above result, along with formal proof and discussion in the camera-ready version.\n\n**Questions:**\n> Can slack be added to the quadratic program in section 4 in the same manner as it is done for SVMs?\n\nYes, but with the slack, the optimal solution might not lie in the agreement region.\n\n> For the regularized objective in section 4, what good is a lower bound on the reliability radius? It can guarantee an unreliable prediction is unreliable, but cannot guarantee a reliable prediction is reliable. Yet it's the later case that is needed to not refuse for reliable test points.\n\nWe can use the lower bound for the reliability guarantee. However, providing the bound on the difference between the lower bound and the actual reliability radius would be an interesting future research direction."}, {"review_id": "sY60ItBSoT", "reviewer": "Reviewer_nCeL", "summary": "The paper develops learning methods that provide theoretical guarantees for point-wise predictions in challenging scenarios at test-time. In particular, the methods presented address situations affected by adversarial attacks and distribution shifts. The paper provides a theoretical contribution to a relevant line of work on reliable learning.", "questions": "\nWhy is that the robustly-reliable region does not contain the instances x such that r(x)=0?\n\nI guess there is a typo in Theorem 3.1 and the subscript CA in \"RR^\\set{L}_CA(S,\\eta)\" should be omitted as in Definition 4 or be a generic W?\n\nEnglish usage can be improved in few places, e.g., \"Given a 0-1 loss function\" should read \"Given the 0-1 loss function\", \"provide bounds the probability mass\" should read \"provide bounds for the probability mass\"\n", "limitations": "The authors correctly describe the limitations of the results in the paper. In that sense, it would be good if the reliance on the realizable case is further discussed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a significant theoretical contribution on reliable learning, addressing important scenarios such as those affected by adversarial attacks and distribution shifts. In addition, the paper covers several different notions of losses and reliability. The results presented can lead to a better understanding of the possibilities and limitations of such scenarios. ", "weaknesses": "The main limitation I can see in the paper is the reliance on the realizable case. I guess that reliance cannot be easily avoided but it may be worth to further discuss and emphasize that issue. For instance, the guarantees in the paper are contingent to the fact that we are in a realizable setting, which is not possible to know in most practical cases. Such assumption is even more significant for the distribution shift case, since it constraints the possible shifts.\n\nThe paper contains many theoretical results for multiple losses, scenarios, etc. In general, it is good to have many interesting results but the paper is quite dense, and it is difficult to get the main ideas. For instance, in Section 4, the authors mention \"The optimal robustly-reliable learner described above may be implemented\" but the authors hardly describe such learner before Section 4 besides stating that it exists (it is described in the proofs). The paper would be significantly more readable (at least for readers not very familiar with the topic) if the authors first describe the main ideas and results over the simplest scenario and then generalize them to other cases.\n\nIt is not clear that the probabilities lower bounded in Theorem 3.3. are not very small or that the abstention probabilities are not very high. I think this point is important because the learners would not be very useful in other cases. It would be good if the authors can quantify numerically those probabilities. The bounds provided show that the probabilities increase when the number of samples increases and the dimension decreases but it is not clear in what scenarios those probabilities are sizable or even the lower bound is larger than 0.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses**\n\n> 1. The main limitation I can see in the paper is the reliance on the realizable case. I guess that reliance cannot be easily avoided but it may be worth to further discuss and emphasize that issue. For instance, the guarantees in the paper are contingent to the fact that we are in a realizable setting, which is not possible to know in most practical cases. Such assumption is even more significant for the distribution shift case, since it constraints the possible shifts.\n\nWe believe that it is always good to first address the realizable case to build the intuition for the definitions and results.  This follows a well-established pattern of developing theories in the learning theory literature.  As we discuss below, extension to the non-realizable (agnostic) setting is possible, building from the definitions and concepts we have developed in the realizable case.\nIn fact, it is possible to relax the realizability assumption for the robustly-reliable learner. We will provide a discussion in the camera-ready version. We include a definition of an agnostic robustly-reliable learner below, along with the statement of a theorem for bounding the robustly-reliable region for the true label robust loss function. Our result below implies that the robustly-reliable region in the agnostic case is a slightly smaller agreement region than in the realizable case, depending on the error rate $\\nu$ of the best classifier in $\\mathcal{H}$. Below, we will illustrate the definition and result in the agnostic case for the TL loss. \n\n**Definition**: A learner $\\mathcal{L}$ is *$\\nu$-tolerably* robustly-reliable w.r.t. $\\mathcal{M}$-ball attacks for sample $S$, hypothesis space $\\mathcal{H}$ and robust loss function $\\ell$ if, for every concept $h^*\\in\\mathcal{H}$ with $\\mathrm{err}\\_{S}(h^*)\\le\\nu$, the learner outputs functions $h^\\mathcal{L}\\_{S}:\\mathcal{X} \\to \\mathcal{Y}$ and $r^\\mathcal{L}\\_{S}:\\mathcal{X} \\to [0,\\infty)\\cup\\\\{-1\\\\}$ such that for all $x,z\\in \\mathcal{X}$ if $r^\\mathcal{L}\\_{S}(z)=\\eta > 0$ and $z\\in \\mathbf{B}^o\\_\\mathcal{M}(x,\\eta)$ then $\\ell^{h^*}(h^\\mathcal{L}\\_{S},x,z)=0$. Further, if $r^\\mathcal{L}_{S}(z) = 0$, then $h^*(z)=h^\\mathcal{L}\\_{S}(z)$.\n\nGiven sample $S$ such that some concept $h^*\\in\\mathcal{H}$ satisfies $\\mathrm{err}\\_S(h^*)\\le \\nu$, the robustly-reliable region of $\\mathcal{L}$ is defined as $RR^{\\mathcal{L}}(S,\\nu,\\eta)=\\\\{x\\in\\mathcal{X}\\mid r^\\mathcal{L}\\_{S}(x) \\ge \\eta\\\\}$ for $\\nu,\\eta\\ge 0$. \n\nWe can prove the following theorem (stated below for the true label loss $\\ell\\_{\\text{TL}}$) which gives pointwise optimal bounds on the robustly-reliable region. \n\n**Theorem**: Let $\\mathcal{H}$ be any hypothesis class with respect to $\\mathcal{M}$-ball attacks and robust loss function $\\ell\\_{\\text{TL}}$, for $\\eta\\ge 0$,\n - There exists a robustly-reliable learner $\\mathcal{L}$ such that $RR^{\\mathcal{L}}\\_{\\text{TL}}(S,\\nu,\\eta)\\supseteq \\text{Agree}(\\mathcal{H}\\_\\nu(S))$,\n- For any robustly-reliable learner $\\mathcal{L}$, $RR^{\\mathcal{L}}\\_{\\text{TL}}(S,\\nu,\\eta)\\subseteq \\text{Agree}(\\mathcal{H}\\_\\nu(S))$\n\nwhere $\\mathcal{H}\\_\\nu(S) = \\\\{h \\in \\mathcal{H} \\mid \\mathrm{err}\\_S(h)\\le \\nu\\\\}$. Furthermore, the safely-reliable region for robust loss function $TL$ is defined as $SR\\_{TL}^{\\mathcal{L}}(S,\\nu,\\eta_1,\\eta_2)=\\\\{x\\in\\mathcal{X}\\mid \\mathbf{B}\\_\\mathcal{M}(x,\\eta_1)\\subseteq RR\\_{TL}^{\\mathcal{L}}(S,\\nu,\\eta_2)\\\\}$. Thus, the above theorem implies bounds on the safely-reliable region as well.\nWe will include the above result, along with formal proof and discussion in the camera-ready version.\n\n> 2. The paper contains many theoretical results for multiple losses, scenarios, etc. In general, it is good to have many interesting results but the paper is quite dense, and it is difficult to get the main ideas. For instance, in Section 4, the authors mention \"The optimal robustly-reliable learner described above may be implemented\" but the authors hardly describe such learner before Section 4 besides stating that it exists (it is described in the proofs). \n\nThank you for your point. Indeed, the optimal learner is provided in the proof of Theorem 3.1 in Appendix. We will describe the learner in Section 3 in the camera-ready version.\n\n\n> 3. It is not clear that the probabilities lower bounded in Theorem 3.3. are not very small or that the abstention probabilities are not very high. I think this point is important because the learners would not be very useful in other cases. It would be good if the authors can quantify numerically those probabilities. The bounds provided show that the probabilities increase when the number of samples increases and the dimension decreases but it is not clear in what scenarios those probabilities are sizable or even the lower bound is larger than 0.\n\nThe probability $1 - \\delta$ in the lower bound in Theorem 3.3 can be arbitrarily close to 1 as the number of sample m is large. Also, the non-abstention probability will be arbitrarily close to 1 for large sample size m. For the safely-reliable region, this non-abstention rate depends on the robust loss, but is generally large for small $\\eta_1,\\eta_2$. For example, it can be close to $1 - 2(\\eta_1 + \\eta_2)$ for the stability loss.\n\nSince our main purpose for the paper is developing theory, we would defer the numerical quantification of those probabilities in this simple setting and the real-world setting to future application-oriented research.\n\n**Questions**\n1. The robustly-reliable region also includes $r(x) = 0$ which is when we know that the prediction is correct. In the definition 3, we have two cases when $r(x) = \\eta > 0$  and $r(x) = 0$ for the mathematical rigorousness of the definition.\n2. Yes, this is a typo. Thank you for pointing it out.\n3. Thank you for your point, we will correct the grammar accordingly.\n"}]

Author rebuttal:

Meta-review: This interesting paper provides many new ideas in reliable learning; reviewers are uniformly positive and I'm glad to suggest acceptance, though I urge the authors to spend their additional camera ready page incorporating the detailed reviewer comments below.
Decision: Accept (poster)