Adversarial Surrogate Risk Bounds for Binary Classification
Authors: Natalie Frank
Venue: Accepted by TMLR ()

Abstract: A central concern in classification is the vulnerability of machine learning models to adversarial attacks. Adversarial training is one of the most popular techniques for training robust classifiers, which involves minimizing an adversarial surrogate risk.  Recent work has characterized the conditions under which any sequence minimizing the adversarial surrogate risk also minimizes the adversarial classification risk in the binary setting, a property known as \emph{adversarial consistency}. However, these results do not address the rate at which the adversarial classification risk approaches its optimal value along such a sequence. This paper provides surrogate risk bounds that quantify that convergence rate.

Published in Transactions on Machine Learning Research (10/2025)
Adversarial Surrogate Risk Bounds for Binary Classification
Natalie Frank
natalief@uw. edu
Deportment of Applied Mathematics University of Washington
Reviewed on OpenReview: https: openreview. net/ forun? id= Bay cHLk
Abstract
central concern in classification the vulnerability of machine learning models to ad- versarial attacks. Adversarial training one of the most popular techniques for training robust classifiers, which involves minimizing an adversarial surrogate risk. Recent work has characterized the conditions under which any sequence minimizing the advensarial surro- gate risk also minimizes the adversarial classification risk in the binary setting, property known as adversarial consistency. However, these results do not address the rate at which the adversarial classification risk approaches its optimal value along such a sequence. This paper provides surrogate risk bounds that quantify that convergence rate.
1 Introduction
A central concern regarding regarding sophisticated machine learning models is their susceptibility to ad- versarial attacks. Prior work (Biggio et al.] 2013 Szegedy et al., (013) demonstrated that imperceptible perturbations can degrade the performance of neural nets. As such models are deployed in security-critical applications, including facial recognition (Xu et al. 2022) and medical imaging (Paschali et al. 2018), train- ing robust models remains key challenge in machine learning.
In the standard classification setting, the classification risk is the proportion of incorrectly classified data. Directly minimizing this quantily is a combinatorial optimization problem, so typical machine learning algo- rithms instead minimize a more tractable surrogate risk via gradient- based methods. A surrogate risk said be consistent for a given data distribution every minimizing sequence also minimizes the classification risk for that distribution. Beyond consistency, a central objective is efficiency: minimizing the surrogate risk should translate into rapid reduction of the classification risk. This rate can be quantified via surrogate risk bounds, which bound the excess classification risk in terms of the excess surrogate risk.
In the standard binary classification setting, consistency and surrogate risk bounds are well-studied topics [Bartlett et al. 2006 Lin 2004 Steinwart 2007 Zhang 2004). A typical approach reduces the problem to a pointwise analysis of the conditional classification and surrogate risks. In contrast, the adversarial setting is less understood. The adversarial classification risk penalizes instances that can be perturbed into the opposite class, while the adversarial surrogate risk computes the worst-case value over an e-ball. The dependence on the value of function over an e-ball precludes pointwise decompasition, rendering the classical analysis inapplicable. Frank & Niles- Weed (2024a) characterized the risks that are consistent for all data distributions, and the corresponding losses are referred to as adversarially consistent. Unfortunately, no convex loss function can be adversarially consistent for all data distributions (Mounier et al. 2022). On the other hand, Frank (025 showed that such situations are rather atypical- when the data distribution is absolutely continuous, a surrogate risk adversarially consistent so long as the adversarial Bayes classifier satisfies a certain notion of uniqueness. While these results characterize consistency, none describe convergence rates.
Our Contributions:
We prove linear surrogate risk bound for adversarially consistent losses Theorem 9

---

Published in Transactions on Machine Learning Research (10/2025)
When the "distribution of optimal attacks" satisfies bounded noise condition, prove linear surrogate risk bound under mild conditions on the loss (Theorem 9h.
We establish distribution-dependdee surrogate risk bound that applies whenever loss is adver- sarially consistent for the data distribution (Thoorem 11.
Notably, the last result applies to convex loss functions. By prior consistency results (Frank 2025 Frank &
Niles- Weed 2024a Meunier et al. 2022).. one cannot hope for distribution independent surrogate bounds for non-adversarially consistent losses. This work presents framework for surrogate risk bounds that applies
to any supremun-based risk under mild conditions. A detailed comparison with prior work is provided in
Section
2 Background and Preliminaries
2.1
Surrogate Risks
We study binary classification on Rd with labels -1 and +1, where Po and IP, denote the class-conditions distributions. For a measurable set A, the classification risk is
R(A) f
Lac LAodPP dPI + / |LAdA LAdFo. dPo.
with minimum R over all Borel sets. Because the indicator function is nondifferentiable, one instead
minimizes surrogate risk
Rol = 1 (()) + (((
with minimum Rs,, over all Borel functions. The loss ø satisfies: Assumption 1. & is continuous, non-increasing, and lima-to p(a)= 0. Thresholding f zero yields the classifier {f > 0}, whose risk
R(S) R(( > 03) = 1550 1150 / dso
It remains to verify that minimizing the surrogate risk Rs will also minimize the classification risk R. Definition 1. The loss function & is consistent for the distribution Fo, P1 if every mindmizing sequence of R consistent for all distrābutions.
is also a minimizing sequence of R. The loss function is consistent
Prior work establishes conditions under which many common loss functions are consistent. For convex ø consistency occurs iff is differentiable at and d'(0) < (Bartlett et al. 2006 Theorem 2). Frank & Niles- Weed 20024a Proposition 3) show that consistency holds if inf, (((a) + p(-a)) o(0), which is satishied by Josses such as the p-margin loss (p(a) min(1, max(1 - a/ 0)) and the shifted sigmoid loss (a) = 1/(1 exp(a -)), O. However, convex loss & cannot satisfy this incquality:
1 (o(a) + + 2 a -a -a)==(0) =())
a
(1)
2
2.2 Surrogate Risk Bounds
In addition to consistency, quantifying convergence rates is a key concern. Specifically, prior work (Brtllett ct al. 2006: Zhang 2004) establishes surrogate risk bounds of the form (R(()) R,) Ro(f) Rs for some function V, linking excess classification risk to excess surrogate risk. These bounds involve pointwise minima of the conditional classification and surrogate risks.
2

---

Published in Transactions on Machine Learning Research (10/2025)
Let P Po + P1 and nxxx) dPi//P. An equivalent formulation of the classification risk is
R(f) ((x)
(2)
where C(n. ar) = alao + (1 La20, with minimal conditional risk
(n) inf C'n, a) min(n, 1))
(3)
and thus the minimal classification risk R. (n(()))))))) Analogously, the surrogate risk in terms of and IP is
Ro(f) = (oln(x), C2(1,a) = n7(a) + (1 - -))((-a)
(4)
and the minimal surrogate risk is R f (d with the minimal conditional risk (²()) defined by
(n) inf Ca(
(5)
Prior work on consistency typically establishes surrogate risk bounds via pointwise analysis of the conditional risks, relating the excess conditional surrogate risk Co(n, a) - (r)) to the excess conditional classification risk a) (n))
The consistency of e can be fully characterized by the properties of the function ())
Theorem 1. loss & is consistent iff (t(n)) < <(0) for all n * 1/2.
Surprisingly, this eriterion has not appeared in prior work. See Appendix A] for a proof. In terms of the function C Frank & Niles- Weed (2024a Proposition 3) states that any loss with (² < ((0) is
consistent. The lunction C% key component of surrogate risk bounds from prior work. Specifically,
Bartlett al.
(0066) shows:
Theorem Tewari Bartlett (0077) Let di be any loss satisfying Assumption
with Cg(1/2) <(0)
and define
v( x(0) C. / 1 8
Then
(C -r)(n)) s -
(6)
and consequently
V(R()) - R.) S Rs R
(7)
The inequality a consequence of and Jensen's 's inequality. Theorem implies that this bound is non-vacuous iff Φ consistent- compare with Theorem 1. Moreover, (6) yields a distribution-dependee linear surrogate bound when 7) is bounded away from 1/2. Tf Massart's 's noise condition (Massart & Nédélec, 2006) holds- namely, there exists [0, 1/2] for which 1/2] 2 P-a.c., then the distribution admits linear surrogate bound.
Proposition 1. Let n, P be distribution that satisfies In 1/2] 2 P-a.e. with constant a E 1/2], and let be loss with ((0)= > C3(1/2 - -a). Then for all |n 1/2 a,
C(n.f) C*) (n) v o(0) C2a( - a) (Coln. - (n)
(8)
and consequently
1
R()) R. < ((0) C35( xx)
(Ro(f) Ro,,)
(9)
3

---

Published in Transactions on Machine Learning Research (10/2025)
See Appendix B| for a proof of this result. Observe that Theorem guarantees that the linear constant is finite whenever * 0 and & is consistent. This bound is distribbttion-indeeeenntt when x(0) > (1/122 with a = O, and will later be generalized to adversarial risks. Although the constant in Proposition 1 is not optimal, further refinement offers no improvement to our adversarial bounds, so we opt to retain the simpler form.
2.3 Adversarial Risks
The adversarial classification risk incurs a penalty of 1 whenever a point x can be perturbed into the opposite class. This penalty can be expressed in terms of supremums of indicator functions the adversarial classification risk incurs a penalty of whenever sup x' x 1A(x') = 1 or sup x xx 1x= = Define
(x())(x)= = sup (x'). ||~<
The adversarial classification and surrogate risks are given respectively by
S. (. f (LAA) RE(() / S. (.((())P + / (.(((-
RE(A) -
A minimizer of the adversarial classification risk is called an adversarial Bayes classifier. After optimizing the surrogate risk, classifier is obtained by thresholding the resulting function at zero. The associated adversarial classification error function is then
0)) f (1 + (.
> 03)
(10)
Just as in the standard case, one would hope that minimizing the adversarial surrogate risk would minimize the adversarial classification risk.
Definition 2. The loss 6 is adversarially consistent for the distribution Po. F1 if any minimizing sequence of Ry is also a minimizing sequence of R We say that & is adversarially consistent if it is adversarially consistent for all distributions.
Theorem 2 Frank & Niles- Weed
2024a 2024a)) ). The loss o is adversarially consistent iff (2(1/2 (0))
characterizes the adversarially consistent losses:
Theorem Frank& & Niles Weed
Frank & Niles- Weed 2024a Proposition 3) guarantees that every adversarially consistent loss is also consis-
tent in the standard sense. Unfortunately, (1) shows that no convex loss adversarially consistent. However, distributions ions for which consistency fails are alypical: for absolutely continuous IP, adversarial consistency holds provided the adversarial Bayes classifier unique up to degenerucy.
Definition Two adversarial Bayes classifiers A1, A2 are equivalent up to degeneracy if any set A with Ai A₂ A Ai A2 is also an adversarial Bayes classifier. The adversorial Bayes classifier is unique up to degeneracy if any two adversarial Bayes classifiers equivalent up to degeneracy.
See F Figure for an illustration of non-equivalent adversarial Bayes classifiers in distribution where adver- sarial consistency fails. Theorem 4 of Frank (2025) relates uniqueness of the adversarial Bayes classifier to the consistency of ó.
Theorem 4 [Frank (025)). Let o be loss with C3(1/) o(0) and assume that P. is absolulely continnous with respect to Lebesgue measure. Then o is adversarially consistent for the data distribution given by Po, P. iff the adversarial Bayes classifier is unique up to degeneracy.
Any extension of surrogate risk bounds to the adversarial setting must account for the conditions of Theo-
rems and
In order to define the risks R2 and R" one must argue that S. (g) is measurable. Theorem 1 of Frank & Neees-Weed proves that whenever y Borel, Se(g) always measurable with respect the completion of any Borel measure.
2024b
4

---

Published in Transactions on Machine Learning Research (10/2025)
(a)
(b)
(c)
(d)
Figure 1: Adversarial Bayes classifiers for the distribution where Po P1 are uniform distributions on (0),
the countercxample from Meunier et al. (2022). The classifiers in (a) and (b) are equivalent up to degeneracy, are those in (c) and (d), but the classifiers in (a) and (c) are not. A sequence minimizing R% but not R
is provided in 33
2.4 Minimax Theorems
A central tool in analyzing the adversarial consistency of surrogate risks is minimax theorems, which en- able 'pointwise' representation of adversarial risks analogous { This section reviews the minimax representation for both adversarial classification and surrogate risks, which underlie the bounds in Section 3
These minimax theorems utilize the co- s--aassesteein (Woo) metric from optimal transport. Informally, this metric quantifies the smallest radius e such that the mass of one distribution can be transported to match another without moving any point more than e.
Formally, let Q and Q' be finite positive measures with equal total mass. A Borel measure y on Rd x Rd is a coupling between Q and Q' if its first. marginal Q and its second marginal is Q', or in other words. ((A x IRd) Q(A) and (BR x A) Q'(A) for all Borel sets A. Denote the set of couplings between Q and @' by IIQ Q²) Then the Wo distance is
Woe (Qx(QQQ) ()=
inf ess sup ||x - y/l- >ETT(G. (x.y)>>
(11)
Theorem 2.6 of Jylhä 2014
proves that the infimum in 11 is always attained. The e-ball around Q in the ( (Q', Q) S c).
Wo motric is 8
The next lemma is standard observation linking adversarial perturbations Woo-balls We include a proof in Appendix C for completeness; it is a known result and not new this work (see for instance Matthew Staib [2017] Proposition 3.1)).
Lemma 1. Let be Borel function. Let y be coupling between the measures Q and ! supported A. [(x,x) ||x x'1 se.. Then (x) 2 9(x') y-a.e. and consequently
1 (.(9)dZ
/ gdo.
sup
Applying Lemma to R shows that inf a R (A) can be expressed an inf-sup problem. The minimax theorem of Pydi & Jog (2021) ensures that the order of the inf and sup can be interchanged. Let (n) be defined in 3) and define
5

---

Published in Transactions on Machine Learning Research (10/2025)
/ LoodP' +
-LxdP' f C
dP
R(P P1)
inf Borel
d d(P' + Fí).
(12)
d(Pp +
Theorem
Frank 2025 ).
Let R. be defined in
12
Then
inf A Borel
R (A))
sup R(F.P F1).
E (F1)
Po EB, (Fo)
with equality attained some Borel A, Po E (B and Pf E (T..)
See Frank Niles- Weed 2024a Theorem 1) for proof this statement. The maximizers PP PT can be interpreted optimal adversarial attacks (sce discussion following Frank & Niles Weed (2024b) Theorem 7)).
Frank
2024
Theorem 3.4) provide criterion for uniqueness up to degeneracy in terms of dual maximizers.
Theorem
Frank (0225)). )
The following are equivalent:
A) The adversarial Bayes classifier is unique up to degeneracy
B) There marimizers Fř, P1 of R. for which IP* (n) 1/2) = 0, where P PP+ and rj" ddPp/dP
Thus, uniqueness corresponds to the situation in which the set where both classes are equally probable has measure zero under some optimal adversarial attack.
The analogous dual problem to R3 uses (z) from
P1)= = / ((f)aT + I | IC: C
dP
Rs (T' P1)
inf Borel
d dP'' + P()
(13)
dP' P))
and the analogous minimax theorem states Frank & Niles Weed 2024b
Theorem 6):
Theorem Frank & Niles Weed (202bb)) ) Let Rs be desined as in
13
Then
inf Borel
R&(()= = sup (EB((()) FeB
Rs (I,, P1).
R-valued
with mazimizers P E (Po), P E (P1) attained.
Finally, optimal attacks for the surrogate problem are also optimal for the classification problem: Theorem 8. Consider mazimizing the dual objectives Rs and R over B (Po) x (PP).
Tf is consistent, then any mazimizer (TP Pi) of RS B. (Po) B (Pi) also mazimizes R.
2) Frank (2025)] If the adversarial Bayes classifier unique up to degeneracy, then there exists a marimizer (177 PT) of Rs with P (1) 1/2) 0, where T = Pr + Pi and 17" = dP//dP"
See Appendix D for a proof of [tem 1) Item 2) is shown in Theorems and 7 of Frank (2025). This minimax machinory links the adversarial Bayes classifier, optimal attacks, and surrogate risks, cstablishing the dual formulations used in Section to derive adversarial surrogate risk bounds.
3 Main Results
Prior work has characterized when a loss ò is adversarially consistent with respect to a distribution Po. Pt. Theorem ssoows that a distribation-innepeneent surrogate risk bound is possible only when (1 < ((0). When (g(1 d(0), Theorem indicates that any such bound must depend on the marginal distribution of 11 under F= and moreover, possible only if p (1)" 11/2) 0.

---

Published in Transactions on Machine Learning Research (10/2025)
together imply if either C2 ((0) if there exist some maximizers of Rg that satisfy Massart's is noise condition, then Φ is adversarially consistent for Fo, Pi. Allernatively, due to [Theorem 8 one can equivalently assume that there are maximizers of RS satisfying Massart's noise condition. Our first result extends Proposition 1 to the adversarial scenario, replacing Po, Pı with the distribution of optimal adversarial attacks.
Compare these statements with Proposition 1: Theorems 3
and
Theorem 9. Let & be consistent and let Po; 11 be a distribution for which there are marimizers Pü: PT of the dual problem Rs that satisfy In" 1/2] 2 -a.c. for some constant a E 102] with C2(1/2 a) ((0), where P = P0 + +I 11" / Then
(*) R S 6(0) - -3(1/2 (R RG
(14)
When (1/22) 60), setting 0 in Theorem 9 yields destributionn-ndeeeneentt bound. As noted earlier, two losses satisfying this condition are the p-margin loss and the shifted sigmoid loss. Likewise, Theorem ensures that the linear constant is finite whenever o 0 and ø is consistent.
The constant appearing in Theorem 9 is nearly optimal: [Section 4.3 shows that it can be improved by at most a factor of two, and this gap attained by a known counterexample to consistency. Thus, the result provides sharp characterization of how tightly the adversarial classification risk can be controlled by the surrogate risk across all consistent. convex losses.
Furthermore, the theorem parallels the classical realizable-case guarantee from the non-adversarial setting, If the optimal adversarial risk satisfies R, = O, then Massart's noise condition holds with a 1/2 (see Lemma 2). In this regime, Theorem 9 yields a linear relationship between adversarial classification and surrogate risks that is directly analogous to the non-adversarial bound in Proposition 1 Zero adversarial risk occurs whenever the supports of Po and P1 are scparated by least 2e (Example I and Figure 3ab.
Theorem statees that if some distribution of optimal adversarial allacks satisfies Massart's noise condition, then the excess adversarial surrogate risk is at worst linear upper bound on the excess adversarial classi- fication risk. However, if (1/22) = @00), the bound's constant diverges as + 0, rellecting the failure of adversarial consistency when the adversarial Bayes classifier is not unique up to degeneracy. For a # 1/2, understanding the assumptions on (Po. P1) which ensure Massart's condition for the distribution of adver- sarial attacks (PP) PT) remains an open problem. Example 4.6 of Frank (2044) exhibits distribution that satisfies Massart's noise condition and yet the adversarial Bayes classifier is not unique up to degeneracy. Thus Massart's noise condition for Po, P1 does not guarantee Massart's noise condition for Pú- Pi. See Example 2 and Figure 3b for example where Theorem 9 applics with 0.
One approach to relaxing the distributional restriction is to apply 14h only on the portion of the distribution where In) 1//2| 2 a and then add back in the risk on (7)* - -1/2 < a.
Theorem 10. Assume that there exist marimizers 17; PP of Rs that are induced by transport maps from Po, Ft, and define IP" = IPt + Fo, 1¹ = / Let S ax then
(t( - R S 5(0) C3(1/2 ( - R,,,) + (2 + Pd P'n 1/2 < <a)
Since this holds for all a, the right-hand side can be minimized over a. Prior work from optimal transport theory verifies the assumption on P under mild conditions: Theorem 3.5 of Jylhä (2014) states that whenever Po, are absolutely continuous with respect to Lebesgue measure and the norm - is strictly convex, the measures Pa PT are induced by a transport map. It is unclear whether this holds for common datasets such as CIFAR-10 or MNIST.
Finally, an alternative approach to removing the distributional restriction is to average bounds of the form (4) over all values of n1 yielding distribuutoon-deeendenn surrogate bound, valid whenever the adversarial Bayes classifier is unique up to degeneracy. For a given function f, let the concave envelope of be the smallest concave function larger than f:
conc(s) inf :> f on dom(S).g concave and upper semi-continuous)
(15)
7

---

Published in Transactions on Machine Learning Research (10/2025)
Label
airplano
airpleno
OO
(b)
(c)
(d)
Figure 2: Ambignous images in the MNIST and CIFAR10 datasets. (a) lies between '5' and '3', while (b) is difficult to classify at all, despite being labeled as '5'. In CIFAR1O, image (c) is ambiguous between ship and an airplane, and image (d) is similarly hard to identify.
S 1, Φ is consislent loss with C² = <(0), and the adversarial Bayes classifier is unique up to degeneracy. Let P. PI marimizers of Rs for which ( 1/2) 0, with P Ph + +P and 1i" dFt/dP". Define (z) conc(IP* (In"" - 1/2 v 2)), & as Theorem and let
Theorem 11. Assume
A(z) 1 -rr-iinnn (min( (())). Then
(f) R, & (f) R2,a)
with
((2) 4 (id (in(min(1, min(1, V-eld In H1) δ
This theorem established under the assumption F < 1, which serves as an essential interme- diate step for extending the result to where the adversarial Bayes classifier is not uniquely defined up to degeneracy. See Example 3 and Figure 3c for example of caleulating distributionndeeeeddent surrogate risk bound.
The function // is always continuous and satisfies (00) = 0, ensuring that this bound is non-vacuous (see Lemma in Section 5). Further notice that H In approaches zero as H +
The map & combines two components: Á, a modified version of V and H, a modification of the edf of In" - 1/2]. The function Á is a scaled version of 4-1 where is the surrogate risk bound in the non- adversarial case of Theorem 2 The domain of T is ((0),, and thus the role of the min in the definition of is to truncale the argument so that it fits into this domain. The factor of 1/4 in this function appears to be an artifact of our proof, see [Section 5) for further discussion. In contrast, the map H translates the distribution of 1y" into surrogate risk transformation. Compare with Theorem 4 which states that consistency fails IP" (17* 1/2) > O; accordingly, the function H becomes a poorer bound when more mass of 17* near 1/2.
If (n 1/2) small, this result can still provide informative surrogate bound.
Theorem 12. Assume that there exist marimizers P Pi of Rs that are induced by transport maps from P. Pi, and define P = P + P 11 dP//dP". Let & be the function in Theorem 11 but with H defined as (=)) = conc((P* 1ppx( (0 < 1n1 1/2 < =)). Then
R - R. < (f Ry,.)) P (1) = 1/2)
Removing the assumption that P Pt are induced by a transport map from Theorems 10 and 12 remains an open problem. We conjecture that this assumption is, in fact, unnecessary.
8

---

Published in Transactions on Machine Learning Research (10/2025)
Example
Example
Example
Px)
[x] P( ps(e)
Px00) Pebx) Pi
Proba biltyy Density
Pg00 Pxlx]
Proba bibiabiity Density
0.7
Probability Density
Polx)
(X)
32.
00
(a)
(b)
(c)
Figure 3: Distributions from
Examples to 3 along with attacks that maximize the dual Rs..
Comparison with real-world datasets
Experimental results from prior work suggest that, in rcal-world datascts, is typically concentrated near 0 and 1. [Bhagoji el al. (019) compute lower bounds on the adversarial classification risk for binary tasks, focusing on classifying digits '3' and '7' in MNIST under f perturbations. Their lower bound remains close to 0 for e S 3 and increases to 0.2 at = 4. Since (1)) attains its maximum at 17" 1/2, a small adversarial risk implies that the distribution places little mass in a neighborhood of 1n - 1/2 = 0. Similar trends are observed on Fashion MNIST and CIFAR10. Dai et al. (2023) extend these bounds to the multiclass setting, though extending adversarial surrogate bounds beyond binary classification remains an open problem.
When the optimal adversarial risk is non-zero, the adversarial Bayes classifier may not be unique up to degeneracy. Even without adversarial perturbations, datasets like MNIST and CIFAR10 contain inherently ambignous examples. Northcutt et al. (2021) identify such cases, four are depicted in Figure 2 One would expect 7x(x = 1/2 for such examples. Bartoldson et al. (2024) show that similar ambiguity arises in adversarial settings: under for perturbations of size 8/255, approximately 6% of adversarial examples are ambiguous the CIFARI0 datasct. In the binary scenario, one would thus expect ny (x)) = 1/2 for these inputs, and thus one must apply [Therrmm 10 or [Theorem 12 Extending the concept of uniqueness of the adversarial Bayes classifier multiclass settings remains open problem.
Examples
Below we present three examples illustrating the applicability of our main theorems. All examples involve one-dimensional distributions, and denote the pdfs of Po and P1 by Po and p1-
To start, if R 0 then 1/* E 1) P*-a.e. for any maximizers of Rig. Therefore, for any such distribution, the optimal attack satisfies Massart's noise condition with a = 1/2, see Appendix J.1 for a proof.
Lemma 2. Assume R. = 0, let [Pr.PPT marimize Re, and define F = F. + PT. 17 d Then ("' E (0.1))=1
Any distribution for which the supports Po, P1 are more than 2e apart must have zero risk.
Example 1 (When R. = 0). Lot
(x) (1
if 1- -5] pi(x) {
if e [6.1+ otherwise
otherwise
for some 8 > 0. See Figure 3a for a depiction. This distribution satisfies R = 0 for all S and thus Lemma implies that the surrogate bound of Theorem applies.
Examples and require computing maximizers to the dual Rs: See Appendices J.2 and J.3 for these caleulations. The following example illustrates distribution for which Massart's noise condition can be verified for distribution of optimal attacks.
9

---

Published in Transactions on Machine Learning Research (10/2025)
Example 2 (Massart's noise condition). Let d > 0 and let p be the uniform density on [-1- -8] 1+5].
Define by
if [-1 6,
(16)
if x E (,, +
see Figure 3b for a depiction of Po and P1- For this distribution and S 6, the minimal surrogate and adversarial surrogate risks are always equal (Ra.. .. This fact together with Theorem 7 imply that optimal attacks on this distribution are PP PI and Fo Fo, see Aependdii J.2 for details. Consequently: the distribution of optimal attacks Fć. P1 satisfies Massart's noise condition with 1/4 and result the bounds of Theorem 9 apply. When E (5, 1 + 5), pdfs of the distributions that maximize the dual are (z) PI (z +), (x po(a=d) where (z) = (==)p(2) and pu(z) = (1- (x)())(((x) These distributions
satisly IP" (1) = 1/2) = (e ()) while (1v - 1/2] 2 1/4) = 11 - (e - 0). Thus Theorem 10 provides a surrogate bound.
The final example presents case in which Massart's noise condition fails for the distribution of optimal adversarial attacks, yet the adversarial Bayes classifier remains unique up to degeneracy, Theorem 11 still yields informative surrogate bound.
Example 3 (Gaussian example). Consider an equal-variance Gaussian mixture with no - 2e < Mn < po + V2a:
1
1
La- (u- 20
(1 = 1 1
La
m 20
po(x)=
2
V2Ta
2
V2To
see Figure 3c for depiction. The optimal attacks Pö: PP are gaussians centered at no + and μi respecively, with pdfs
()-(ro-))) 20
(e (0-(m1-)))
Pū(x) = 2 2 e
1 pi 2
20
(17)
2no
We verify that Pe and Pf are in fact optimal by finding function I for which R8((S*) (PP),FF)) the strong duality result in Theorem 7 will then imply that Po and Pf must maximize the dual Rgg, see Appendix J.3 for details.
Further, when μ1 - Ho S V2o, then the function h(z) P'n 1/21 2) concave in z and consequently H h, see Appendix J.4 for details. Although h is unwieldy function, comparison its linear approximation at zero gives the bound
16o²
H()) S min
(18)
M1 140
2
Again, see Appendix J.4 for details.
When e 2 (W) po)/2, Frank (2024] Example 4.1) demonstrates that the adversarial Bayes classifier is not unique up to degeneracy. Notably, the bound in preceding example deteriorates as (fr - po)/2 + and then fails entirely when (11 - po)/2.
4 Proof of Linear Surrogate Bounds
4.1 Proof of Theorem
The proof of Theorem 9 relics on decomposing the excess adversarial classification and surrogate risks into non-negative terms, revealing their structural similarity and allowing for pointwise comparison.
Let FP, Pi be any maximizers of Rg. These distributions also maximize R by Theorem 8 Set IP = P + +P
1y = /P' Let 7. 7i be couplings between Po. P and IP, IPT achieving the Woo distances excess classification risk can be decomposed as
11
The
R = = R(P P1) f((f)an + f fio(f)nn
(19)
10

---

Published in Transactions on Machine Learning Research (10/2025)
with
(() = (S.(1 1)20(x)) + (c')")))""())) Ro(s) (S. 1x)0(x() (C("; (*
The first term measures the discrepancy between the worst-case attack on f and the attack induced by Po. Pi, the optimal attack for the distribution Fo, I1. The second term measures the excess conditional risk under the optimal attack Po,Pi. Pf. Lemma 1 implies that S. (x(1)))(x)) - gx)((x) must be positive, while the definition of C implies that ,f) (1²")) 2 0.
Similarly, one can express the excess surrogate risk as
R2(S) - P = / (P(D)at ftt
(20)
with
9 - (CG)60))))-)00))))))(C0000)1 0367))
(((00)(((((x)) = (S((=(5((--))) - -((-f((x))
The following lemma is the core inequality linking is to c under Massart's noise condition. It shows that each classification-risk term can be bounded by constant multiple of its surrogate risk counterpart. Lemma 3. Define f0 if as in [20 and assume that the distribulion of optimal adversarial allacks Pö. IPT satisfies Massart 's noise condition. Then
io(s) S x(0) C2 (0))
(21)
i1( S 6(0) C3(1/2 99
(22)
hold a-..c. and e..e. respectivcly.
Lemma 3 directly implies Theorem 9 by integration over couplings ?Ý, 76.
Proof of Theorem 9 Combine
19
Lemma 3 and 20
4.2
Proof of Lemma 3
The proof proceeds by partitioning the domain Rd Rd into regions where the supremum- based classification either matches (Dx) or exceeds (Fg) the decision under the optimal attack. On each region, we derive a
separate bound relating is and x.. Define the sets DR, Ex:
Do = {(x,x') (,(1) 1 1(x) 0}
(23)
Es ((x.x): (,(1)=0) 1(x))0 1}
(24)
D1 [(x,x': (.(1) 1s(x)50 0}
(25)
E ((x,x') (x)) - 1 1(0)50 1}
(26)
By construction, Dj U E = Rd x Rd and Do U E. Rd Rd.
The following lemma records simple but useful structural property of Eg and Ei, which allows us to bound the surrrogate loss terms from below on these sets.
Lemma 4. Let Eg be as in Equations (24) and (26) Then S,(1)=0)(x) 1/>0(x') -.e. Fy while (x())))) 1//o(xx)= 10-a.. En.
Proof. We'll prove the statement for E1, the argument for Eg is analogous. Specifically, we will show that one cannot simultancously have Se (z)) l/(((x' = 1 and (c(1)s) - 1/>0(x') 1.
Consider (x, x') E Ei: as both S. (1 and 1 (x') are 0-1 valued, the relation Se (x(1)oo)xx) ( = implies that 1 L and thus 1(x) = 1. The fact that (x))o)) 2 1x>o(x') on supp oi and suppoi C. implics that (1))))))x -a.c. on E,.
11

---

Published in Transactions on Machine Learning Research (10/2025)
The next result bounds the terms xx from below.
Lemma 5. The relations 27 and 28 hold on Eg and Ej respectively.
(f) 2 (0) Cz(1").
(27)
(()))(00--0 C3("")
(28)
Proof. We will prove the statement for E1, the argument for Eg analogous. Obscrve that (f = (x(((f))x + (1 - n" ()( ((f(x)))))((())))) O3
Now S, (x)))) 1, one conclude that there is a point in z E (x) for which f(z) S 0, and thus ((((())) (0)) Next, Lemma 4 implies that f(x') > 0 and hence ((-f(x')) o(f(x)) 2 0. Therefore,
one can conclude (28)
Furthermore, a simple calculation bounds the in from above.
Lemma 6. On the set Dr
ix( - (r1)))
(29)
while on Fak
=+(f=)++(()) -0
(30)
Proof. We will show the statement the argument for is analogous. On D1, (,(1
1(x))0 implying (29 Similarly, Ei, (,(1)su)(x) - 1 s()) implying 30
Comparing the upper and lower bounds present in Lemmas and
proves
Lemma
Proof of Lemma 3 We will discuss (22 the argument for 21 analogous. We prove the bound separately
D1 and E1, whose union is Rdd First, notice that implics that
C(n'(x)), C* (1"((())) (O) < x(0) C a)
C2(n" Pa-a.e. (31)
On the set Di: Lemma 6 iimlies that
i.( C(r -O
and thus the desired inequality follows from and the fact that S. [)(x Φo s(x) 0 7--a.
On the set Ej: On Er,
However, due to Lemma 5
S. (1) 1=50x'==1=1 = 6(0) (3
1
o(0) - (1()))) (S o(f(x')
(32)
o(0) (17*)
The last inequality is consequence of the assumption In* 1/2 S a. Summing this relation with 31 shows 22
12

---

Published in Transactions on Machine Learning Research (10/2025)
4.3 Lower Bounds
The bound in Theorem 9 provides general guarantee relating the adversarial classification and surrogate risks. We now show that this bound cannot be substantially improved.
This example describes functions in which the worst-case attack and the attack induced by Po: Pj differ substantially. This function sequence is the counterexample to consistency proposed in prior work (Meunier
et al. 2022 Li & Telgarsky 2023). Intuitively, the sign flip causes the classifier to misclassify both classes, even though a constant function would achieve lower risk for this distribution.
Example (Lower bound for Theorem 9p. Let & satisfy Cg(1/2) = x(0), and consider a distribution supported on [-6,6] with (*)n 11/++a) Define the sequence of functions
x
fn
(33)
x=0
For this sequence, R (fn) R 1/22 + a while the adversarial surrogate risk converges to lim (fx)
(0)) - (1/2 a). Consequently,
R ((nn) - R n-+00 (y((n) R2 6(0) C1/2 a)
3 +a
lim
It follows that for any 8 > there exists f such that
1/2+a
R²(F) - R (00) - C3(122- (R - R.s.)) -6.
In particular, the constant in Theorem is overestimated by factor of at most 1/(1/2 + S However, this example demonstrates that Theorem is tight when a = 1/2.
The constant in Theorem 9 is known to be sub-optimal when a < 1/2. In particular, Theorem 4 of Frank (225 proves that R (f) - R. I (1/2)/(o(0) C (1/2)) (f) - -R, for the p-margin loss (p(a) min(1, ma - a/p)). We conjecture that the tight constant in Theorem 9 is in fact (1/2 + ()/(6(0) - C1/2 a)). Together, these observations indicate that the bound in Theorem captures the correct order of dependence on a and o, and that only the mumerican constant can potentially be improved.
5 Proof of [Theorem 11
Before proving Thoorem 11 will show that this bound is non-vacuous when the adversarial Bayes classifier is unique up to degeneracy. The function h(2) P((n" 1/21 I 2) is cdf, and is thus right-continuous in 2. Furthermore, if the adversarial Bayes classifier is unique up to degeneracy, then h(0) 0. The following lemma implies that if /l cone(h) then H is continuous at 0 with (0) = 0. See Appendix E for a proof. This result implies that the bound in Theorem i is non-vacuous.
Lemma 7.
Let h. [0, 1/2] + R be mon-decreasing function with h((0) 0 and h(1/2) = 1 that is right- continuous at O. Then conc(h) is non-decreasing, continuous on [0, 1/2], and conc(h)(0) = 0.
The first step in proving Theorem function is replaced by an dp-eeennentt concave function.
showing analog of Theorem with a 0 for which the linear
Proposition 2. Let + be a concave non-decreasing function for which - S 2 -C
for any E [0, and a E IR. Let Iy, IP be any two mazimzers of Rs for which (²' = 1/2) = O, where P = Pi + IP and 17" = dIFt /dF' Let G [0, + R any non dendeeeeesingg concave function for which the quantity
K / G(D(0) C7 (z(()))) dP
13

---

Published in Transactions on Machine Learning Research (10/2025)
is finite. Then (f) R (f - Ro where
1 77
((2) 1
KG
+ 24 2²
(34)
The proof strategy mirrors that of Theorem 9 but with & and G replacing the fixed constant bound.
Uniqueness up to degeneracy and Theorem guarantee that the denominator 6(0) C² is strictly positive -ae.. The function y- in Theorem 2 and the surrogate bounds of Zhang (2004) provide examples
of candidate functions for +. As before, this result is proved by dividing the risks R R as the sum of four terms as in separately.
20 and then bounding these quantities over the sets DR, En defined in 225 (25 (6
The factor of 1/4 in 34
arises as an artifact of the proof technique: one factor of from averaging over two
sets D1, E1, (see (56] in Appendix F), and another factor of from combining the bounds associated with
the two integrals corresponding to class 0 and class [(see Equations (54) and (56) in Appendix F
We now turn to the problem of identifying functions G for which the constant K in the preceding proposition is guaranteed to be finite when the adversarial Bayes classifier is unique, but distribution dependent. Observe that if is the odf of |n 1/2 and is contimuons, then f 1 dh is always finite for r E (0, 1). This calculation suggests & o v1- with defined in Theorem To ensure the concavity of G, we instead select G H o oo
with H conc(h).
Lemma Assume (1)2) (0)) Let PI, Po, Pi, Po 0, H, and v be as in Theorem 11 (min((, (0))). Then for any r E (0, 1),
Let A(z)
Rs (f) R < (( - R.
(35)
with
(2) 4
H 2 4 2
)
+ 21 (
(36)
Proof. For convenience, let G (H tA)". Then G is concave because it the composition of concave function and increasing concave function. We will verify that K is finite and yields the constant in the bound:
K = / C(o(0) - (3()))
--r
First,
1
G(Ø(0) - ()()))) dP"
H(nn" 1/2 dP
dPp 4s
dp' is
Ju H(s)
(0. H(s)r
with In" - 1/2/.. The assumption P'' (In"" 1/2)) 0 allows to drop 0 from the domain of integration.
Because the function H is continuous (0, 1] by Lemma 7 this last expression be evaluated a Riemann-Stieltjes integral with respect to the function h(s) = P(nn" 1/21 < s):
So
1/2 Hss)" dh
dp is
(37)
(0.3) H(s)
This result is standard when JP* Lebesgue measure, (see for instance Theorem 5.46 of Wheeden Zygmund 1977)). We prove equality in (37) for strictly decreasing functions in Proposition in Appendix G.1. Finally, the integral in (37 be bounded as
1 H(s) dh < 1 1-r
(38)
14

---

Published in Transactions on Machine Learning Research (10/2025)
If h were differentiable, then the chain rule would imply
1 [H(O) dh S H(s)
1 J Jo²
1
1 --r 1-r h(s)
1
h(s)r dh
h(s) ('(sdd2
1
This calculation more delicate for non-differentiable H1; we formally prove inequality in pendix G.2
38
in
Ap-
This calculation proves the inequality 35 with & as 36
To obtain the bound in Theorem 11 first observe that the concavity of A together with the fact that A(0) implies that 2A(z/2) < 4A(2/4). Next, minimizing the bound in Lemma 8 Oover then produces Theorem 11 see Appendix H for details.
6 Proof of Theorems 10 and 12
The main insight behind Theorems 10 and 12 is that a transport map that realizes the optimal adversarial perturbations also preserves optimality when restricted certain subsets of IRd allowing a reduction from the global to local problem in both the dual and primal formulations. The following lemma formalizes the fact that under transport map structure, restricting the primal problem to the pre-image of set Q corresponds exactly to restricting the dual maximizers to Q itself.
Lemma 9. Let Po be data distribution and let IP E B (PP),, B(O(P)) maximize Rg. Assume there erists transport maps To, Ti for which P Prt with [[T( x|| S e. Let Q be any set and define U. = TT=
If the data is distributed according to Poluo Pi Pilu,, then Polo, Pilo marimize Rs over B (PolU.) B (PP lv
In the remainder of this section it will be useful to include the data distribution in the notation for the primal problem. Thus, for the remainder of this section, we define
PP) ( MdP S.(0o- MaPo (():Po,Pi) / / (c(1s)) (39)
Similarly, we'll denote
(Po inf PP). (PP...P)) inf R2: (J::
(40)
Observe that for any two sets Up. U1,
(f: Polu + (f Filuç)
This decomposition reflects the fact that the adversarial surrogate risk is additive over disjoint measurable partitions of the data space. If furthermore these sets are induced by transport maps, then the optimal risks also follow this split.
Lemma 10. Let Pt. P1 To, Ti.Uo. U1 and Q be in Lemma g and define P Pp + PP 17" /dPp Then
(Po. Pı) = R. (Pole,, + R (Polug, and furthermore, R (Polug, P. (1ue)) = Iqe ddP"
See Appendix 1.2 for a proof Lemmas and 10
Proof of Theorem 12 Let Q = fx' (x') = 1/23. Then Lemma 9 applied to QC shows that (Piloe, PPlge) maximize Rs over 8 (Polu.) 8 (PPll,)) with Un To TQ) and Un (Q-) Theorem 11
15

---

Published in Transactions on Machine Learning Research (10/2025)
and Lemma 10
imply that
R (f:Poolo. (P - (f:PPoo : R. Poouu Pilu1))
② (f: Pi) 12.
Next, by Lemma 10. adding R (f; Pilop) R: (Polug i Pilet) to both sides of the inequality above results in
R (f:Po, (Po. Pi) S Φ (o; Rig (Polu:: Pı)) + R (s:Polg Pilue) 1 (1"))
The fact that (r)))) = 1/2 on Q while S((rso) S 1, Sc(1so)) S implies that R (f:FPolug. Pi Piluf) So (n 1/2)/2.
PPnn" = 1/2).. Thus, the excess risk contribution from the region Q is at most P*("""
The proof of Theorem 10 follows the same steps, except that we take Q = {x' [|(xx)) 1/2 a}, see Appendix 1.3 for a proof.
7 Related Works
The statistical consistency of surrogate risks in both the standard and adver- sarial context has been widely studied. Bartlett et al. (2006) Zhang (2004) establish surrogate risk bounds that apply to the class of all measurable functions while Lin 2004]; Steinwart (2007) prove further results on consistency in the standard setting. Frongillo Waggoner 2021 | study the optimally of such bounds, and
Surrogate Risk Bounds:
Bao (2023) derive bounds using the modulus of convexity of C construct surrogate risk bounds. Several
works (Philip M. Long 2013 Mingyuan Zhang, 2020 Awasthi et al. 2022 Mao et al. 2023a Awasthi al.;
2023b study consistency within a restricted function class; concept known H. H-consistency, [Mhdaavi
et al. 2014) combine surrogate risk bounds with surrogale generalization bounds to study the generalization of the classification error.
Adversarial Surrogate Risk Bounds: Most closcly related to our results are Li & Telgarsky (2023
Mao et al. 2023a). Li & Telgarsky (2023) derive a surrogale bound for convex losses in which the threshold in (10) optimized rather than fixed at zero. Mao et al. (2023a) establish an adversarial surrogate bound for modified p-margin loss.
Adversarial Consistency: In the adversarial setting, Meunier et al. [002); Frank & Niles- Weed (2024a)
characterize which losses are adversarially consistent for all data ristribut.ons. Frank (2025) show that under reasonable distributional assumptions, consistent loss is adversarially consistent for a specific distribution iff the adversarial Bayes classifier is unique up to degeneracy. Awasthi et al. (2021) study adversarial consistency for a well-motivated class of linear functions while Awasthi et al. (023b): ; Mao et al. (023a)) study H-consistency in the adversarial setting for specific surrogate risks. Standard and adversarial surrogate risk bounds are a central tool in the derivation of the H-consistency bounds in this line of research. Whether the adversarial surrogate bounds presented in this paper could result in improved adversarial H-consistency bounds remains open problem.
The Adversarial Bayes Classifier: Our proofs draw on prior work that investigates adversarial risks and adversarial Bayes classifiers. Bungert et al. (2021); Pydi & Jog 22021 2020 Bhagoji et al. (2019): Awasthi et al. (2023a) establish existence results for the adversarial Bayes classifier, while Frank Niles Wood (2024b); Pydi & Jog (2020 2021); Bhagoji
al. (2019): Frank (2025) prove minimax thcorems for adversarial surrogate and classification risks. Pydi & Jog (2020) use such results to analyze the adversarial
Bayes classifier, and Frank (2024) employ them to study uniqueness.
16

---

Published in Transactions on Machine Learning Research (10/2025)
Sample Complexity and Surrogate Risks: The bound of Theorem 2 can be linear even for convex loss functions. For the hinge loss ((a)) max(1 a, 0), the function & computes to x(0) 10). Mahdavi et al. (2014) emphasize the importance of a linear convergence rate in a surogate risk bound. They note that convex surrogates with favorable sample complexity often fail to satisfy strong surrogate risk bounds, due to Theorem 2 Frongillo & Waggoner [2021]: convex losses which are locally strictly convex and Lipschitz achieve at best a square root surrogate risk rate. Thus, Proposition suggests that favorable sample complexity guarantees for convex surrogates may require distributional conditions such as Massart's noise condition, under which Massart & Nédélec (2006) also show improved sample complexity.
8 Conclusion
In conclusion, we prove surrogate risk bounds for adversarial risks. When & is adversarially consistent or the distribution of optimal adversarial attacks satisfies Massart's noise condition, we obtain a lincar surrogate risk bound. In the general case, we prove a concave distributtonn-lependeed bound. Understanding the optimality of the concave bound remains open problem, as does understanding how these bounds interact with the sample complexity of estimating the surrogate risk. While related questions have been studied in the standard setting (Frongillo & Waggoner 2021 Mahdavi et al., 2014), the adversarial context remains largely unexplored. Advancing these directions could bridge the current gap between theoretical guarantees and practical robustness adversarial learning.
Acknowledgments
Natalie Frank was supported in part by the Research Training Group in Modeling and Simulation funded by the National Science Foundation via grant RTG/DMS 1646339, NSF grant DMS-2210583, and NSF TRIPODS II DMS 2023166.
References
Tom M. Apostol. Mathematical analysis, 1974.
Pranjal Awasthi, Natalie S. Frank, Anqui Mao, Mehryar Mohri, and Yutao Zhong. Calibration and consis- tency of adversarial surrogate losses. Neurlps, 2021.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. H-consistency bounds for surrogate loss minimizers. In Proceedings of the 39th International Conference on Machine Learning. PMLR, 2022.
Pranjal Awasthi, Natalie S. Frank, and Mehryar Mohri. On the existence of the adversarial bayes classifier (extended version). arriv, 2023a.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In Francisco Ruiz, Jennifer Dy, and Jan- Willeel van de Meent (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMI.R, 2023b.
Han Bao. Proper losses, moduli of convexity, and surrogate regret bounds. In Proceedings of Thirty Siath Conference on Learning Theory, Procoedings of Machine Learning Research. PMLR, 2023.
Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the Americun Stalistical Associalion, 101 (473), 2006.
Brian R. Bartoldson, James Diffenderfer, Konstantinos Parasyris, and Bhavya Kailkhura. Adversarial ro- bustness limits via scaling-law and human-alignment studics, 2024. URL http::///axxv..orrrg /404.
09349
Arjum Nitin Bhagoji, Daniel Cullina, and Pratock Mittal. Lower bounds on adversarial robustness from optimal transport, 2019.
17

---

Published in Transactions on Machine Learning Research (10/2025)
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Sindié, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint. European conference machine learning and knowledge discovery in databases, pp. 387 402. Springer, 2013.
Loon Bungert, Nicolás Gareía Trillos, and Ryan Murray. The geometry of adversarial training in binary classification. arzie, 2021.
Sihui Dai, Wenxin Ding, Arjun Nitin Bhagoji, Daniel Cullina, Ben Y. Zhao, Haitao Zheng, and Prateek Mittal. Characteriving the optimal 0-1 loss for multi-class classification with a test-time allacker. In Advances in Neural Information Processing Systems 36 (NeurIPS 2023), 2023. URL https: hoops://arxiv.
2tg/abb/2302.10777
Natalie S. Frank. A notion of uniqueness for the adversarial bayes classifier, 2024.
Natalie Frank. Adversarial consistency and the uniqueness of the adversarial bayes classifier. European Journal of Applied Mathematics, 2025.
Natalie S. Frank and Jonathan Wiees-Weed. The adversarial consistency of surrogate risks for binary classi- fication. Neurlps, 2024a.
Natalie S. Frank and Jonathan Niles-Weed. Existence and minimax theorems for adversarial surrogate risks in binary classification. Journal of Machine Learning Research, 2024b.
Rafael Frongillo and Bo Waggoner. Surrogate regret bounds for polyhedral losses. In Advances in Neural Information Processing Systems, 2021.
Jean-Baptiste Urrutyy and Claude Lemaréchal. Fundamentals of convex analysis, 2001.
Heikki Jylhä. The 1s0 optimal transport: Infinite cyclical monotonicity and the existence of optimal transport maps. Colculus of Variations and Partial Differential Equations, 2014.
Justin D. Li and Matus Telgarsky. On achieving optimal adversarial test crror, 2023.
Yi Lin. A note on margin-based loss functions in classification. Statistics & Probability Letters, 68(1):73-82, 2004.
Mchrdad Mahdavi, Lijun Zhang, and Rong Jin. Binary excess risk for smooth convex surrogates, 2014.
Anqi Mao, Mehryar Mohri, and Yutao Zhong, Cross-entropy loss functions: Theoretical analysis and appli- cations, 2023a.
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Structured prediction with stronger consistency guarantees. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems. Curran Associates, Inc., 2023b.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34, 2006.
Stefanie Jegelka Matthew Staib. Distributionally robust learning a generalization of adversarial training. Newrlps, 2017.
Laurent Meunier, Raphaël Ettedgui, Rafael Pinot, Yann Chevaleyre, and Jamal Atif. Towards consistency in adversarial classification. arXiv, 2022.
Shivani Agarwal Mingyuan Zhang. Consistency h-consistency: The interplay between surrogate loss functions and the scoring function class. Newrlps, 2020.
Curtis G. Northcutt, Anish Athalye, and Jonas Mueller. Pervasive label errors in test sets destabilize machine
learning benchmarks. In Proceedings of the 35th Conference on Neural Information Processing Systems Track on Datasets and Benchmorks (NewrIPS Datasets & Benchmarks Track), December 2021. Includes the companion website https://labelerroore
18

---

Published in Transactions on Machine Learning Research (10/2025)
Magdalini Paschali, Sailesh Conjeti, Fernando Navarro, and Nassir Navab. Generalizability robustness: Adversarial examples for medical imaging. Springer, 2018.
Rocco A. Servedio Philip M. Long. Consistency versus realizable h-consistency for multiclass classification. TCML, 2013.
Muni Sreenivas Pydi and Varun Jog. Adversarial risk via optimal transport and optimal couplings. ICML, 2020.
Muni Sreenivas Pydi and Varun Jog. The many faces of adversarial risk. Newral Information Processing Systems, 2021.
Ingo Steinwart. How compare different loss functions and their risks. Constructive Approzimation, 2007.
Christian Szegedy, Wojeiech Zaremba, Nyy Sutskever, Joan Bruna, Dumitru Erhan, Tan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXi::1312.619 2013.
Ambuj Tewari and Peter L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(36), 2007.
Richard L. Wheeden and Antoni Zygmund. Measure and Integral. Pure and Applied Mathematies. Marcel Dekker Inc., 1977.
Ying Xu, Kiran Raja, Raghavendra Ramachandra, and Christoph Busch. Adversarial Attacks on Face Recognilion Systems, pp. 139-161. Springer International Publishing, Cham, 2022.
Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 2004.
19


Reviews:
[{"review_id": "xZoUyksZdP", "reviewer": "Reviewer_XyY9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. As previous work does not derive the adversarial risk bounds, the results in this paper fill this gap.\n2. This paper provides detailed and rigorous proofs.\n\nWeakness: \n\n1. The organization of this paper can be improved. The body of the paper is a mix of proof and statement. Also, for example, Section 2.1, which is not the main part of this paper, occupies almost three pages. Also, it is hard to distinguish between the theorems/propositions cited from the existing literature and the ones newly proposed in this paper.\n\n2. Massart's noise condition seems not general enough.\n\n3. As the authors already mention, the optimality of the bound and the dependence on the sample size are not investigated, which limits the contributions of this paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the adversarial surrogate risk bounds for binary classification. The authors prove the linear convergence rates when the distribution of optimal adversarial attacks satisfies Massart's noise condition.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I appreciate it if the authors can:\n\n1, Move some redundant content to the appendix to facilitate the readers' understanding.\n\n2. Write the references of the theorems clearly within the theorems.\n\n3. Add some references to the introduction of the statistics background, for example, the second paragraph of the paper.\n\n4: Do the grammar check for the sentence: To the best of the authors’ knowledge this paper is the first to prove surrogate risk bounds... on Page 2.\n\n5. Make the labels and references of the equations consistent: Equation 8 is a consequence of (7) ...\n\n6. Clarify if Theorem 3 is inspired by Theorem 2 in (Frank & Niles-Weed, 2024a).\n\n7. Instead of listing the proofs for the main results, state the technical challenges/insights/differences of proving the surrogate risk bounds for the adversarial binary classification, compared with the non-adversarial setting.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vbjfie4w4W", "reviewer": "Reviewer_UYjp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The authors extend the result of (Barlett et al., 2006) to the adversarial setting, which is of broad interest.\n(2) The technical parts appear correct.\n\nWeakness:\n(1) The bound in Theorem 11 is not optimized; therefore, its tightness is neither analyzed nor demonstrated experimentally.\n(2) The writing of section 2 can be improved. It is difficult to see which are existing works and which are the proposals (directions) of this work, and how they are connected. Since the adversarial setting and proofs of the main results rely on the works (e.g. Frank&Niles-Weed,2024a,2024b), the clarity of Section 2 is important.\n(3) The Massart's noise condition is difficult to verify in practice. Can the authors give more interpretation or demonstrate the applicability in toy experiments (e.g. MNIST)?\n(4) The proof of Theorems 11 and 12 can be shortened by focusing on the calibration of the space into D.E.F.\n\nMinor: \nA repetition in section 6 (...tool central tool..)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "For the binary classification tasks, the authors extend the existing work of (Barlett et al., 2006) and provide surrogate risk bounds in the presence of adversarial perturbations. Firstly, the authors provide a linear risk bound under Massart's noise condition, with the convergence risk quantified. The authors also give a realizable risk bound when the adversarial Bayes risk is zero and a data-distribution dependent risk bound when the adversarial Bayes classifier is unique up to degeneracy. Moreover, the authors provide three examples where the results are illustrated.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness for details:\n(1) and (3) should be addressed to some extent\n(2) is critical\n(4) is optimal", "broader_impact_concerns": "no concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "l6t5lOeuQ1", "reviewer": "Reviewer_ZJeZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- This work provides important results regarding the surrogate loss consistency in adversarial settings.\n- The theoretical results are extensive, characterizing different scenarios.\n- Numerical examples are used to illustrate the idea.\n\nWeakness:\n- It does not highlight the difference of the adversarial setting and the standard setting, in terms of the theoretical tools and proof steps required. Concretely, this makes one wonder what is the main difference and key insights behind the proofs.\n- No \"slightly practical\" examples (e.g., MNIST, CIFAR-10) are examined; the theoretical results are not backed by numerical simulations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the consistency of surrogate loss in binary classification, especially in adversarial settings. The main claims are theoretical. It proves that (1) when Massart's noise condition is satisfied, a linear convergence bound can be achieved, and (2) a distribution-dependent bound may be achieved with mild conditions. Three toy examples are provided to illustrate different scenarios and assumptions.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Grammar and writing:\n- Even the abstract does not fully parse: \"Recent work characterized when a minimizing sequence of an adversarial surrogate risk is also a minimizing sequence of the adversarial classification risk for binary classification— a property known as adversarial consistency.\" I can guess the intention, but it is tough to parse and understand. Similar problems are all around. A global grammar check might be necessary.\n\n## Assumption checking\n- It is more proper to examine the restrictiveness of the assumptions in practical datasets like MNIST. I understand that a precise characterization is impossible, but numerical approximations should be provided.\n\n## Result validation\n- Providing numerical support for the established theorems increases confidence in the theories.", "broader_impact_concerns": "This is a theoretical work, and I do not see ethical concerns that require highlighting.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)