Efficient PAC Learning for Realizable-Statistic Models via Convex Surrogates
Authors: Shivani Agarwal
Venue: NeurIPS 2025 poster ()
Keywords: PAC learning
surrogate losses
proper composite losses
multiclass classification
multi-label prediction
subset ranking
generalized linear models
Primary area: theory

Abstract: A central question in the theory of machine learning concerns the identification of classes of data distributions for which one can provide computationally efficient learning algorithms with provable statistical learning guarantees. Indeed, in the context of probably approximately correct (PAC) learning, there has been much interest in exploring intermediate PAC learning models that, unlike the realizable PAC learning setting, allow for some stochasticity in the labels, and unlike the fully agnostic PAC learning setting, also admit computationally efficient learning algorithms with finite sample complexity bounds. Some examples of such models include random classification noise (RCN), probabilistic concepts, Massart noise, and generalized linear models (GLMs); in general, most of this work has focused on binary classification problems. In this paper, we study what we call realizable-statistic models (RSMs), wherein we allow stochastic labels but assume that some vector-valued statistic of the conditional label distribution comes from some known function class. RSMs are a flexible class of models that interpolate between the realizable and fully agnostic settings, and that also recover several previously studied models as special cases. We show that for a broad range of RSM learning problems, where the statistic of interest can be accurately estimated via a convex ‘strongly proper composite’ surrogate loss, minimizing this convex surrogate loss yields a computationally efficient learning algorithm with finite sample complexity bounds. We then apply this result to show that various commonly used (and in some cases, not so commonly used) convex surrogate risk minimization algorithms yield computationally efficient learning algorithms with finite sample complexity bounds for a variety of RSM learning problems including binary classification, multiclass
classification, multi-label prediction, and subset ranking. For the special case of binary classification with sigmoid-of-linear class probabilities (also a special case of GLMs), our results show that minimizing the standard binary logistic loss has a similar sample complexity as the GLM-tron algorithm of Kakade et al. (2011), but is computationally more efficient. In terms of the distribution over
the domain/instance space, our results are all distribution-independent. To our knowledge, these are the first such results for PAC learning with stochastic labels for such a broad range of learning problems.

Efficient PAC Learning for Realizable-Statistie Models via Convex Surrogates
Shivani Agarwal University of Pennsylvania ashivani@seas upenn. edu
Abstract
A central question the theory of machine learning concerns the identification of classes of data distributions for which one can provide computationally efficient learning algorithms with provable statistical learning guarantees. Indeed, in the context of probably approximately correct (PAC) learning, there has been much interest exploring intermediate PAC learning models that, unlike the realizable PAC learning setting, allow for some stochasticity in the labels, and unlike the fully agnostic PAC learning setting, also admit computationally efficient learning algorithms with finite sample complexity bounds. Some examples of such models include random classification noise (RCN), probabilistic concepts, Massart noise, and generalized linear models (GLMs); in general, most of this work has focused on binary classification problems. In this paper. we study what we call realizable- statistic models (RSMs), wherein allow stochastic labels but assume that some vector-valued statistic the function class. RSMs conditional label distribution comes from some known flexible class of models that interpolate between the realizable and fully agnostic settings, and that also recover several previously studied models special cases. We show that for broad range of RSM learning problems, where the statistic interest can be accurately estimated via a convex "strongly proper composite' surrogate loss, minimizing this convex surrogate loss yields a computationally efficient learning algorithm with finite sample complexity bounds. We then apply this result show that various commonly used (and in some cases, not commonly used) convex surrogate risk minimization algorithms yield computationally efficient learning algorithms with finite sample complexity bounds for a variety of RSM learning problems including binary classification, multiclass classification, multi-label prediction, and subset ranking. For the special case of binary classification with gegmoid-of-lined class probabilities (also a special case of GLMs), our results show that minimizing the standard binary logistic loss has similar sample complexity as the GLM-tron algorithm of Kakade et al. (2011), but is computationally more efficient. terms of the distribution over the domain/instance space, our results are all instribution-indeeenddee knowledge, these are the first such results for PAC learning with stochastic labels for such a broad range of learning problems.
To our
Introduction
The probably approximately correct (PAC) learning model is cornerstone in the theory of machine learning. The two most widely studied settings, namely the realizable and fully agnostic settings, both represent somewhat extreme tradeoffs between computational efficiency and statistical modeling power: The realizable setting, as originally proposed by Valiant [38), often admits computationally efficient learning algorithms, but makes the restrictive statistical assumption that examples are labeled by deterministic target function (from some known function class); the (fully) agnostic setting 23 29 allows for fully general joint probability distributions the labeled examples, but often fails to admit computationally efficient learning algorithms. Consequently, there has been much interest
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in exploring intermediate PAC learning models that both allow for some stochasticity in the labels, and admit computationally efficient learning algorithms with finite sample complexity bounds. Some
examples of such models include random classification noise (RCN) 4
13
10
17
27
21
22 30 20
probabilistic concepts (28]. Massart noise [6 37 35
31
6
8
40
45
19
15 14 and (univariate)
generalized linear models (GLMs) and single index models (SIMs)
26
25
In general, most of this
work has focused on binary classification problems.
In this paper, we study what we call realizable-statitie models (RSMs), wherein we allow stochastic labels but assume that some vector valuud statistic of the conditional label distribution comes from some known function class. RSMs are a flexible class of models that interpolate between the realizable and fully agnostic settings, and that also recover several previously studied models as special cases. We show that for a broad range of RSM learning problems, where the statistic of interest can be accurately estimated via convex 'strongly proper composite" surrogate loss, minimizing this convex surrogate loss yields a computationally efficient learning algorithm with finite sample complexity bounds. We then apply this result to show that various commonly used (and in some cases, not so commonly used) convex surrogate risk minimization algorithms yield computationally efficient learning algorithms with finite sample complexity bounds for a variety of RSM learning problems including binary classification, multiclass classification, multi-label prediction, and subset ranking. In terms of the distribution over the domain/instance space, our results are all iestributiin-indepeeddde
Technically, our work involves the following components. First, after defining RSMs, we define the notion of 'strongly proper composite' surrogate losses for estimating desired statistic T (generalizing previous definitions of strongly proper composite surrogate losses for binary and multiclass class probability estimation + 42) Second, we give a general surrogate regret transfer bound for any RSM learning problem for which the statistic of interest can be accurately estimated via strongly proper composite surrogate loss; this allows us to upper bound the target loss based regret in terms of the surrogate regret. Third, we use uniform convergence techniques to upper bound the surrogate regret of an (approximate) surrogate risk minimization algorithm, thus also upper bounding the target loss based regret for such an algorithm. We give two such results: one using d1 covering numbers, and the other using Rademacher complexities. For the result in terms of Rademacher complexities, we make use of vector- contraction incquality due to (32 to upper bound the Rademacher complexities of the loss function class y associated with a vector- function class F and a surrogate loss s (that acts on rector-valued predictions and is Lipschitz w.r.t. the Euclidean metric) in terms of the Rademacher complexities of the real-valued projection classes F.. For the result in terms of d2 covering numbers, we give (to our knowledge, new) technical lemma that upper bounds the dj covering numbers of the loss function class v/ associated with a vector-valued function class F and a surrogate loss v/ (that acts on vector-valued predictions and is Lipschitz w.r.t. the L metric) in terms of the di covering numbers of the projection classes F); this lemma may also be of independent interest. Finally, we show how these results can be applied to a variety of RSM learning problems.
While our results are broadly applicable to many RSM formulations, for each of the applications we consider, we include specific instantiations to RSM learning problems with sigmoid/softtaxx-ff (multi-) )lnnarr forms for the statistics of interest, which can also be viewed as (multivariate) GLMSs (see Table for summary). For the applications binary classification (with 0-1 loss), multi-label learning (with Hamming loss), and subset ranking (with discounted cummulative gain (DCG) based loss), the Rademacher complexity based result gives tighter sample complexity bounds than those based on d, covering numbers. For the application to multiclass classification (with 0-1 loss), the two results are complementary: for n classes and data dimension p, the di covering number based result gives a cemeension-dependeen
sample complexity bound of ((pp/e2) for achieving squared estimation error S c; the Rademacher complexity based result gives diimension-indeeendenn bound of Ö( /e) For the special case of binary classification with sigmoid-of -f-nnerrr class probabilities, our results show that minimizing the standard binary logistic loss has a similar sample complexity as the GL.-tron algorithm of Kakade et al. (2011), but is computationally more efficient. In particular, the sample complexity for achieving squared estimation error S e is Ō(1/e²) for both algorithms; however, the computational complexity of GLM-tron is (pp/ e²), whereas that of the logistic regression algorithm is (/2))
We note that the usage of the term 'proper' here is related to that in 'proper scoring rules' in the probability forecasting literature (see for example [12 33 34 39 [1 (2) and references therein), and is distinct from that in
"proper learner' as commonly used in the PAC learning literature.

---

Table 1: Summary of selected PAC learning results with stochastic labels (results selected for comparison with ours, which are shown red). Note that in terms of the distribution on the domain X, the results shown here are all inrrbbttooonddeeeddennt Here LTF stands for 'linear threshold function'. See Appendix fAr details of the assumptions associated with RCN, Massart noise, GLM, and SIM. See Section 2 for details of notation used in the last row. The computational complexities listed for RSMs all assume implementations using Nesterov's accelerated gradient descent (AGD).
Assumption on conditional label distribution P(Y = x)
Learning target
Sample complexity (for squared
Sample complexity (for target loss based
Computational
complexity
(m = sample complexity from column 3 or 4)
estimation
error S c)
regret < c)
Binary classification with 0-1 loss [X C RR, y = = [+1)
Noisy LTF: RCN TT 17 21
Best LTF
poly(p, 1/e)
poly 1/e)
Noisy LTF: Massart noise 15
Upper bound 77 on Massart noise
Ö(poly(p)/e*)
poly(p, 1/e)
GLM 25
Best LTF
Ō(1/2))
O(m)/2p)
SIM 25
Best LTF
(i)((p/e)
(i) Ö( 4/5p)
(ii) ((10(
(ii) Ö(m 5/1
Sigmoid-or of lineir
Best LTF
Õ(1/2))
Õ(1/6))
O(m8/Ap)
[as special case of RSMs]
Multiclass classification with 0-1 loss (n classes) I. C TR", TR. ==
[n]]
mf-ullliina
Best multilinear
(i) ((pp(e)))))
(i) ((mp/e))
[as special case of RSMs]
multiclass classifier
(ii) Ö(n" (c)
/c)
((i) O(1
(ii) nmp)
Multi-label prediction with Hamming loss (s tags) [X C RP, Y' = 5 = 10. Ō(s²/6²)
Sigmoid-of -f-nnna linear marginals [as special case of RSMs]
Best multilinear multi-
Ö(s²/e)
Ö(m²/*sp) sp)
label prediction model
Subset ranking with DCG metric (s items, r rating levels) [X' C "R, .P (0,1,...,, 1..... 11.]
Sigmoid-of oeenoiddof-liner scaled marginal expectations Jas special case of RSMs]
Best multilinear
subset ranking model
General learning problem (general X, xz with general loss matrix L E RVx'
RSM:
Best prediction model H. C 5** where H = pred o Q for pred : _2d y s.l.
δ +B"
"o2dd +B9) 7204
((1)
T Tope E Q.
where t = number parameters to be learned
where p :X with
where Rm (FF)
where Rm (F)
Py (,(x) P(Y = X = r).
T: Ay and Q C (
(r.pred) is L-calibrated
Organization of the paper. Section sets up the learning problem, defines RSMs, and gives our main results. Sections then apply our results binary classification, multiclass classification, multi-label learning, and subset ranking, respectively. All proof' can be found in the Appendix.
Notation. We denote by Z4 the positive integers, and denote R,, [0, 0o), R++ (0, oc),
R R= [-00, R2 [0. co). For positive integer n, [n] == (1....,n), and I, {T [n]-[[] i is a bijection]. For a matrix A, we denote by a, the j-th column vector of A. For a finite set D. Ay == {p E R Eyey Py = 1}; for y = [n], abbreviate An = Amm We denote by 1(- the indicator function. For a vector u E R", argsort(u) = { E 11, / 4 >
Uj (i) *())}. For two vectors un U2 R". the di distance between them is di(ui, U2) 1 fllu, uzlli. We use Ni to denote di covering numbers. For set X, class of real-valued functions F C (S X-RR an integer m E Z,, and an underlying proba- bility distribution μ on X. we denote the Rademacher complexity of F for sample size m as (F) := E Ex,, X(........,>>p.." ((c........ (sup fer 1 - (X,,)] where are i..dd Rademacher random variables (each taking values +1 or -1 with probability 1 each). For set C. an objective function f : C-R, and a positive real number a > 0, an a-approximate minimizer of f over returns a solution é E C satisfying f(c)= < infcee f(e) +
3

---

2 Realizable-Statiste Models (RSMs) and Main Results
Section 2.1 sets up the learning problem and formally defines RSMs. Section some useful tools and then gives our main results.
2.2 starts by defining
2.1
Realizable-Statitte Models (RSMs)
Problem setup. We will consider a fairly general supervised learning setup. Specifically, let X be an instance space, and y/ 5 be finite label and prediction spaces, respectively Let é y x --R be target loss function, where for each E ) T E V, the loss f(v. () is the cost of predicting y when the true label is y; equivalently, we will represent the loss function via loss matrix L E ,²' with (y, 7 element given by y. L(y. 7) Let D Axxy be a joint probability distribution over X' x V. which we will often write as = (1.,p p), where μ E Ax is the marginal D over 2' and p X' -'y denotes the conditional distribution over }' given instance in X. Given training sample S = ((Xi, Yi),.., (Xm, Ym)) containing labeled examples drawn i.i.d. from D, the goal is to learn prediction model h - with small expected loss on new example drawn from D, which we will refer to as the L-error or L-risk of h: erb [b] = (xxxY)>((4yy,ccx
In partieular, for class of models H C {h: x-v) and class of probability distributions D xx,,, a learning algorithm A that maps training samples S E 1 y) to prediction models hg E H is a probably approximately correct (PAC) learning algorithm for the learning problem (L. H. D) with target loss sample complexity function m²a Rx x (0, 1] 1 + if for every e > 0, E (0, 1), every probability
distribution D) E 'D and every m 2 (e, 6). Ps PS-D- (erb) [hs] - inf er > E) < 6, and moreover, for every 6, m () is the smallest integer satisfying the above. We will sometimes denote by (M)] == inf e [h] the best L-error for D within H.
Realizable-statise models (RSMs). The essence of our realizable-statistcc models (RSMs) is to allow the labels to be stochastic and assume that some (vector-valued) 'statistic' of the conditional label distribution p(x) (P = y = =x)) =)))gE>
D) belongs to some class of (vector-valuee) yEy (associated with the underlying data distribution functions Q: in other words, we will assume that a statistic T of the conditional label distribution p(z) is "Q-realizable', Formally, for any C C g and X X-C),, define the class of d-dimensional statistic T Ay-C, and any class of functions @ C x
(T, Q) Q)RM distributions over X' 3' as follows:
1(r. RSM RSM {D- (H.P) Axxy 3 s.t. T(p(x)) = q(z) Vx E
We will be interested in solving learning problems of the form (L, D(, ()..M)))).) We note that the realizable and (fully) agnostic PAC learning models can both be recovered special cases of RSMs; all the previously studied intermediate PAC learning models listed in Table can can also be recovered as special cases of RSMs (see Appendix B. Our algorithms for solving (certain types of) RSM learning problems of the form (L, H. D(r ()-RM) will typically do the following: given training sample S, they will first (sometimes implicitly) find an estimate qs : X- for the true statistic function q (z) = T(p(x)), and then will return a prediction model hs X'-5 effectively constructed from qs. Accordingly, for such algorithm A. in addition to its target loss sample complexity m defined above, we will also be interested in its squared T-estimation error sample complexity function m R4+ 10. where for every > 0,8 E (0, 11, m is the smallest integer such that every probability distribution D e D and every m 2 m (c,6))
P Dm m Ex [xx==ll(ssX)] (X) - q- (X) > e) < 6.
2.2
Main Results
We start by defining some tools that will be needed for our main results specifically, the tools of L-calibrated statistics and strongly proper composite surrogate losses. Before doing so, recall:
Definition 1 (Bayes L-error and Bayes L-optimal model). Let L E R be any loss matrix. The Bayes L-error for D, denoted e is the smallest L-error under D over all possible prediction models: ert = inf, inf 5 erb [b). A Bayes L-optimal model for D, denoted 1 X.+Y, , is any prediction model that achieves the Bayes L-error for D: erl, [h]]*] ertt".
"Our model and results easily extend to more general D, 5: we take these be finite for simplicity.

---

Definition 2 (L-calibrated statistics (2). Let L E R. be any loss matrix. Let d E Ri and C C.R. A statistic T : Ay-+ is L-calibrated if mapping pred C-ÿ such that for all distributions D = (1, p) E Axxy, a Bayes L-optimal model for D can be obtained from T()())) as hh (x) = (re)( We will also say the statistic-mapping pair (T, pred) is L-calibrated.
The convex surrogate risk minimization algorithms we will consider will minimize the empirical surrogate risk 1 vns ΣTh (y,, f(x:)), for some suitably defined convex surrogate loss 1) : x C² C²+ that acts on vector predictions in some convex set C² C Rd' (for a suitable integer d'), over some class of vector-valued functions FF {f: X' X to learn vector-valued function fs F, and then will return a prediction model hg : X' x² of the form hx(()) decode (x)) for a suitable decoding function decode: : C' We will be especially interested in surrogate losses whose minimization yields accurate estimates of a desired statistic т : Ay-+C. To this end, we define below the notion of strongly proper (composite) surrogate losses vb for a statistic T, for which the expected surrogate invertible transformation of) the correct statistic value T (p);; this generalizes the definition of strongly proper (composite) surrogate losses for binary and multiclass class probability estimation 3 42 to estimation of general statistics
loss Ey- (Y, u)] is 'strongly' minimized (possibly
Definition 3 (Strongly proper composite surrogate losses for a statistic T). Let d E Z4 and C C Rd, and let Dy-C be any statistic of interest. Let d' E Lt, and let C' C 12d' be such that C is in one-to-one correspondence with a subset C'. IfC is in one-to-one correspondence with C itself, then let X CC+C' be an invertible mapping with inverse CCCC'AC otherwise, let X CC be one-to-one mapping and let S = ={Sq q E C} be partition of such that X(q) E Sqq b4 C, and let X- CC'+C denote an 'extended' inverse that assigns X -(u) = =q
Sq. Lety > 0. A surrogate loss vb : y x C² -R+ acting on C' is -t-strnnlyy proper composite for statistic T with link function À if Ey~ppyyv
u) - (Y, ((())((()))) 2 I (u) - -(p) 12 Vp E Ay, u u C².
We are now ready to state our main results. We start by giving general surrogate regret transfer bound for RSM learning problems for which the statistic of interest admits a strongly proper composite surrogate loss: this allows us to upper bound the target loss based regret in terms of the surrogate regret. Specifically, the theorem below effectively shows that given a target loss L, an L-calibrated mappiii pair (T, pred) satisfying certain condition (which allows the L-regret to be upper- bounded by the squared T r-estimation error), a class of 'statistic' functions Q, and a strongly proper composite surrogate loss 1a for 7 with link function X, for any data distribution D E Dir Q)RMMM both the squared T restimation error of any q E Q and the target L-regret (excess L-risk) of a model h pred q in the class of models H pred Q can be upper bounded in terms of the surrogate vi-regret (excess vs-risk) of the vector-valued function f = Xoq in the class of vector-valued functions F= A o O The proof of this theorem is inspired by the proof of surrogate regret transfer bound given in a different context (Bayes consistent multi-label learning with the F-measure) by 443
Theorem (Surrogate regret transfer bound for RSMs that admit strongly proper composite surrogate losses). Let X be any instance space and V be any label and prediction spaces, respectively. Let L R be loss matrix. Let d E Z+ and C C CR.. Let T Dy and pred c-ÿ be such that pred) is an L-calibrated stapistic-mapping pair, and suppose 3x > 0 s.t.
By- - mingey Ey=plEy.s S =llq- - ( VP E AEC
Let Q S {q X X-CC} be class of 'statistic' functions. and let vi y x Rd -R_ be a r-strongly proper composite surrogate loss for T with link function À CRR Let H C (h X-5) be
defined as H = pred e Q (h: X x f E s.t. h(x) = ((x)( Vo E x),, let F C ( X X= be defined as
X o Q [f x l S.t. f(z) = X(q(z)) Va E X}, and
'The reason for introducing a new space C' C Eed is that often it is easier to minimize a surrogate loss acting on space C' different from C (in many of our examples, we will have C S Rd, d' d and C² = Rd).
1 'As in Definition 3 if C' is in one-to-one correspondence with Rd itself, then we will assume that X : C-RRd is an invertible mapping with inverse X IR <C: otherwise, we will assume that X : C- is one-to-one mapping and S = {Sq q C} is partition of Rd such that X(q) Sq Yq E C, and X R R denotes an 'extended' inverse that assigns X (n) = q Vu E Sq. Note that the notation of Definition here we have set d' = d and C' = dd (this is both for simplicity and because this suffices for our examples): however, the theorem easily extends to any suitable d' and C".
5

---

define decode: : BZ-5 as decode := pred o A Suppose that byy fx))) E [0. B] Vo E N E
v.f f E F for some > O. Then for any E and any D D 2).
er decode o - erbl S n. ..VE Ex lI (f(X)) - T(P(X)I S K. V (er - (F)
In practice, when applying the above theorem, it will often be the case that the class of "statistic" functions Q is of the form Q = F for some pre-specified class of pector-valued functions FF (such as bounded multi-lineat functions) and some 'transfer' function σ; in such settings, it can be helpful to choose a strongly proper composite surrogate loss whose inverse link function A is matched (we will see several examples of this in the next few sections).
The above result can be combined with any upper bound on the surrogate é-regret in F to yield upper bounds on both the squared r-estimation error and the target L-regret in H. which in turn can then be converted to sample complexity bounds. The following two results make this concrete for standard unregularized surrogate risk minimization; the first result makes use of d1 covering numbers, while the second makes use of Rademacher complexities. For the result in terms of di covering numbers, we make use of standard uniform convergence techniques, together with (to our knowledge, new) technical lemma (given in Appendix (B) that upper bounds the di covering numbers of the loss function class eا = {ur X V-R++ 3 E F s.t. (/ y) = ey(y, f(r)) associated with a vector-valued function class FF and a surrogate loss ab (that acts on vector-valued predictions and is Lipschitz w.r.t. the L metric) in terms of the dj covering numbers of the real-valued projection function classes { (defined below); this lemma may also be of independent interest. For the result in terms of Rademacher complexities, we make use of uniform convergence techniques, together with vector- cosor-contraction inequality due to (32 that upper bounds the Rademacher complexities of the loss function class 1/ associated with a vector-valued function class F and a surrogate loss eb (that acts on vector-valued predictions and is Lipschitz w.r.t. the Euclidean metric) in terms of the Rademacher complexities of the real-valued projection classes {F)); }
Theorem 2 (RSM learning bounds for surrogate risk minimizers via di covering numbers). Under the conditions of Theorem 7 suppose the surrogate loss vo is p pi-Lipschitz in the second argument with respect to the I,² metric, so that sh(y. U1) - ryyy, Ug) S P1 [| u2lli Vy, u1 U2 and suppose that the fanction classes Fi = {f, : X- e F.t. fạ(x) = (f(z)); Vx), j E [d] each have bounded d1 covering numbers Ni(c,Fi,, m) (polynomial in m and 1/c). Then a surrogate risk minimization algorithm A which, given a training sample S of size m, finds an (16B/ /m)- approximate minimizer fs E F of the empirical surrogate risk m En (B,, f(x:)) over F, and produces a r-statistic estimate 95(2) -xf (z)) and a prediction model hg E H given by hx) = decode(fs((a) (or equivalently, hz(x)) = pred(ps(x))) is a PAC learning algorithm for the RSM learning problem (L, H. ((T.2))RSM) with squared T T-estimation error sample complexity m (c, S min {mo E Z+ mm 2 ma = m 2
(E/=) In (Ni (spid: Fi, (22m) + In (1))), and with target loss sample complexity m²a(e,)) S min {m E E4 : m 2 mo = m 2
1152B3 7²2²
qe
1152x4 B² (E)= In (N1 (==7> padd FT, F,,2m) + In (+)) In particular, if the di covering numbers e
=e²
of the function classes F have upper bounds of the form Ni (e,F5, S F(e,Fi) (i.e. bounds
independent of sample size m), then m (c, S 11528
7202 (E In (1ppppe + In ($)), and (E/-) In (0l 18K2 Fi)) + +In (?)).
ml)(c,5)= S 11522. B2 7/t
Theorem 3 (RSM learning bounds for surrogate risk minimizers via Rademacher complexities). Under the conditions of Theorem [ suppose the surrogate loss vb is p2-L-ipschitz in the second argu- ment with respect to the Euclidean metric, so that by, un) (y, y, ug) S P2 12 - u2lla Vy, un, u2 and suppose that the function classes F) = {fs : / E F fz(x) = (f(z)), Vz), j E [d] each have non-negative, decreasing Rademacher complexities (F') (decreasing in m). Then a surrogate risk minimization algorithm A which, given a training sample S of size m, finds an -a)pmmpppppooiaattte minimizer fgg F of the empirical surrogate risk I Em Vlys, f(x.)) over F, and produces a T-statistic estimate âs(x) = x- -(s(z))) and a prediction model hi E H. given by hi((x) decode(fs(z)) (or equivalently, lis(x)) (red(ās()))) is PAC learning algorithm for the RSM learning problem (L, H. D R))M) m
with squared T-estimation error sample complexity (,,)), I min {mo Z+ : m 2

---

mo = - 32(222p2 Ei=1 Rm + BV /n(2//6)
<3} - } and with target loss sample complexity
(e) S min fm E Ed+ : m 2 mo = 322/2p2 Σi= Rm (F')+ BV
In(2/5)
x
}.
2xd
In particular, if > 0 such that the Rademacher complexities of the function classes F have upper bounds of the form (F) S C/vm vj E [d], then m (e, 6) S アp ( and m (e,
36
30x" 7 (2 B/In(2/8))*
In Sections BH6 beloww we apply the above results a variety of RSM learning problems, including binary classification, multiclass classification, multi-label prediction, and subset ranking, While our results are broadly applicable many RSM formulations, for each of the applications below, we will include specific instantiations to RSM learning problems with sigmoid/softmax of off(mmlli-))lil forms for the statistics of interest. To this end, we will make use of the following upper bounds on the d1 covering numbers and the Rademacher complexity of (bounded) linear functions:
Proposition 4. Let R. W > O. Let X S fx E R' ||x||| I R]. Let Funcar = {f R E RP, ||w|12 S W S.I. f(x) = w T x Vx}. Then for any m E Z, and any 6 > 0:
(i) Ni,, Sa(e,,Finca Fllncar- m) < (1/e)²:
(ii) Ni, Finear, m) S (4R² /e2 + 1) 1)12Re and (iii)
0 S Rm (mm(Finnn (Frineur I RW RW/Vm.
3 Binary Classification
Consider a binary classification problem with instance space X. label and prediction spaces y =
5 = { and the standard 0-1 loss to E (x(+1))x ((11) with e 1 7) = 10 # y). Let statistic T+1 A (=1) -0, and
C = [0. 1], and define the cnojecttoononttoottttthoo
mapping pred
|0, (+1} as
(p (p+1,p-1) = p+15
pred (4) (iign(11122).
Then (7+1, "red"1) is an 0+ ccalibbraee pair. Moreover, as is well known (also see Appendix C
[1 Ey Ey-pl Y (g))
minge(+1) Ey I 1 P+al
Vp E ((=1), 4 E [0, 1].
Therefore, for any class of 'statistic' functions @ {q 10, 1}} and corresponding hypothesis class H. predd-1 o Q, Theorem Detaaliisess that any convex surrogate risk minimization algorithm minimizing a strongly proper composite surrogate loss for -+1 over a suitable class of functions F C {ʃ X yields an efficient PAC learning algorithm for the RSM learning problem (L H. D(r+) RSMM)) While this result can be applied to any class Q and suitable surrogate loss v. the following theorem makes this concrete for the class of sigmoid-of-linear models 2sigmoid of linear and the binary logistic loss solog (defined below).
Theorem 5 (PAC learning algorithm for binary classification with sigmoid-of-linear class probabilities). Consider a binary classification problem, with X' C {x E TR" ||x|| S R) for some R > 0. y = y = [+ and with the standard 0-1 loss L as above. Let 7 and pred be as defined above. Let IR +0,, 1] be the sigmoid fanction a a()) 1/(1 + t)=",, and let
Qsigmoid-of-linen {g: : X x- 1] 3w E RP, || W s.t. q(x) = o(w]] x) Vx}
for some W > O. Let Hiinear == pred o 2xigmond of linear. i.e. Hinnerr {h- X x+1+11 | 3E e R. | 1/ S W s.t. h(x) = sign (w Tx) Vx}. Let vJORR {=1} x R-R be the binary logistic loss:
10 (y.u) In(1 eel++ewya) vuy)
Let Fincas = (f X-R Bw E R. wwl2 S W s.t. f(x) w T Vx}. Then an algorithm A which, given a training sample S of size m, finds an (In(1 RW R (/2 approximaae minimizer fs E FFinear of the empirical surrogate risk Em uiTo fxx)) over Frnear and produces a +1- estimate (z( = (Fs(x)) and prediction model hg E Hinca given by hss = sign ofs (equivalently. his = pred o gs). is a PAC learning algorithu for the RSM learning problem (L. Hinnaa Dirt1, Qxgui d RSM) with squared -+1 esttimatio error sample complexiry
m 5) = O (5 In (t)) and with target loss sample complexity m I00 (c. 6) = 0 ( In (H))
7

---

4 Multiclass Classification
Consider now a multiclass classification problem with instance space X, label and prediction spaces
y = [n]] for n > 2, and the multiclass 0-1 loss L0-((n) E R with gar1 (y: (7) = 1 # v). Let
C An., and define the 'identity" statistic rid An AAn and mapping predd)((n) A,, -m1] as
(p) - Pi pred (q) argmaXge(m) 4g
Then (r ((n) is L (0-1(m) calibrated pair. Moreover, shown in Appendix D (())
Ey [ 1 Y.predu
minge(m] Ey B 1 S v2 1 Vp. An.
Therefore, for any class of 'statistic' functions Q S {q X' x' and corresponding hypothesis class H = pred0-1(a) 1()) o 2, Theorem 2 establishes that any convex surrogate risk minimization algorithm minimizing strongly proper composite surrogate loss for 7 over suitable class of functions JF C {f X-K") yields an efficient PAC learning algorithm for the RSM learning
problem (L (-)), H. ())
RSM). While this result can be applied to any class Q and suitable surrogate loss vb, the following theorem makes this concrete for the class of ceftmax--of-muttiine models of and the multiclass logistic loss similog (defined below).
Theorem 6 (PAC learning algorithm for multiclass classification with offtmax-of-multiinnaar class probabilities). Consider a multiclass classification problem, with X {x R" ||x|| S R} for some R > 0, = = [n]] and with the multiclass 0-1 loss L as above. Let rid and pred0.1(n) be as defined above. Let a -n be the softmax function (ar(u)y = e"v /(y''/ e²x)) Vy [ni), and let
@sotmaxx-ofmllnnar = :q: WE E RPx" W| S W Vy s.t. q(x) = o( xx) Vx}
for some W > O. Let Hmultcclas-lineer pred Qsotmaa--of-mlinan i.e. Hmmtticlas--innar {h- X x WW E Rexx, ||W,ll2 I W Vy s.t. h(x) E argmax,EEm) [w] x) Vx}. Let r/mllog [m] x
R- -R+ be the multiclass logistic loss
Gm (y, u) -u + In in(Ev=1e">)
E argmax in] ugg and let Fmulticlass-lincr [f: X- EW E RRx= ||wyll2 < W Vy s.t. f(x) = W x Vx}. Then algorithm A which, given a training sample S of size m, finds an ((n(n) + 2RW) / (2/mm) (am))-pppoximml minimizer fs E Fmmutticnss--innr of the empirical surrogate risk Ex sfmlog (yr, fxx:) over Fmulticlas--ineo and produces a Tid_ - -tatiistic estimate Âs(x)) = o (fs(z)) and a prediction model his E Hmulticeass linear given by lus(x) = decode (fs(x)) (or equivalently, hs(#)) pred (as(z))), is PAC learning algorithm for the RSM learning problem (I)-)(n), Hmultictass limear, D(T" Qutteae -RSM) with squared -sstimaato error sample complexity m (e, and target loss sample complexity
Define D-10) : [m] as d
m m. 1011(m)
5c upper bounded as follows:
(i) (Dimeension-depeedenn)
(c, 0( (سس (mp In (7) + In (t))); m m ( =0
(E,ō)=0( (lnn)² (m (np In (2) + In (1)) )
(ii) (Dimeension-iillepeelde
mx² (c, 6) 0 (3 (n² + (In(n))2 In (1))): m m
(c, = 0 (1. (n² + (In(n)) In (1))
Multi-Label Learning
Next, consider a multi-label prediction problem such in image tagging, with s tags [s] {1, (1,....8)) $). several of which can be active in an instance simultaneously. and the goal is to predict for a new instance which of the tags are active. Specifically, let X be any instance space, with label and prediction spaces y y {0. 1)" (labels are represented as vectors y E (0. 1)" with yy 1 indicating that the j-th tag is active), and consider the Hamming loss Ham E [ x(0,1) with (Haa (y, y) Σラ= 1 ( # v²). Let C [o, 1]a, and define the s-dimensional 'marginals' statistic
8

---

T marginals (0.1). -00, 1] and mapping predHam
Ham [0, 1 as
(Trmaggoal (p))}- =
Σ
py:
(predHHm(( (q)); = sign(gj - 1122
Vj E [s]
(E(0)))'wy)
Then (T-agginals, predHam) is an L callbbrabe pair. Moreover, as shown in Appendix B
Hom Ey~pl X ppeddt y.rodll
min "E(0,1)"
Ex~pl_A
Ham
S 2/s-// marginals (p)ll2 Vp E (0.1). E [0. 1j.
Therefore, for any class of "statistic" functions Q s {q: (0, 11m} and corresponding hypothesis class H = predHam o Q. Theorem establishes Thearimmesstablihhes that any convex surrogate risk minimization algorithm minimizing strongly proper composite surrogate loss for marginnals over a suitable class of functions F C {f X yields an efficient PAC learning algorithm for the RSM learning problem (I, H, H, (Taagiat Q)-RSM). While this result can be applied to any class Q and suitable surrogate loss 1,, below we make this concrete for the class of iigmoid-f-mmltilinee models @sigmoid of multilinear and the "binary relevance' logistic- bbased multi-label surrogate loss vBBRiog (defined below) F
Theorem 7 (PAC learning algorithm for multi-label prediction with iigmoid-of-multiinnee marginals). Consider a multi-label prediction problem, with X' C {xx E TRP ||x||2 S. Rt for some
R > 0, )² = = = {0, 13", and with the Hamming loss L Ham as above. Let T marginals and predHtm be
as defined above. Lei 12, 1] be the sigmoid function (u)) = 1/(1 e "), and let
Qxigmoidd of multilinear = {q : X' 10, 1 1EW E RRX*. "RPx*,[[w, ||w5ll2 S W Wyj s.t. (x(x)= = c(w] x) bx
for some W > O. Let Heian X' (0, 13ad j 3W E Rpxx, [|all2 S W Vj s.t. lx(x) sign(w] Vx,j). Let B/ (0. 1) x R TT4 be the 'hinary relevance" logistic-baser multi-label surrogate loss defined by
muttiliinur
predHam o Qsigmoid mulliiinn-- i.e. H (h
(B -E In(1 + e- 12y5 e-1yy- -1)s).
Define decode RR. -R0 133h as (decode Ham (u)); == sign(u,) E [s] and let Fmulitiiner = {f X' X= 3E E RPx* "gxx,IIw,ll, //w, S W Vj s.t. f(x) W x Vx} Then an algorithm A which, given training sample S size m, finds an (s (sIn(1+e NeW 1 -approximate minimizer Is E FFmultilinnar of the empirical surrogate risk m Em= es RRiog (ys, f fxx)) over Fmuuttinar and produces a marginals.
and a prediction model hss E Heian given by his(x)= = Ham (x)( (or equivalently, hi((z) = pred (πs(x))), a PAC learning algorithm for the RSM learning problem (L Ham Heign
statistic estimate (âs(x)); =(((f((x)
mulliiincer D Pommginns Diimm of cnntitic) RSM)) with squared marginals, estimation error sample complexity mā namitah (c = 0 In+In(5) (t)) ), and with target loss sample complexity m (c, = ( (s In (1)))-
6 Subset Ranking
As a final example, consider subset ranking problem such as those that arise in information retrieval, wherein each instance contains query and subset of s documents, together with some relevance judgments for each of the documents as labels, and given a new instance containing a new query and new subset of s documents, the goal is to find a good ranking of the s documents for that query. Specifically, let X' be any instance space, and let the label space be y = 10. rr],, where each document is graded on scale of 0 r; the prediction space is 5) II.- A widely used performance measure for such problems is the discounted cumulative gain (DCG); ; in loss form, one version of A
the DCG loss L PCG is given by (DCG (y, +) -- My disc (f)),, where disc : [s]- 1] is non-increasing 'discount" function that discounts documents placed lower in the ranking. often 1/ (logzza (a + 1)), and Z is a constant that ensures non-negativity of the loss Let C [0. 1] and define the s-dimensional 'scaled marginal expectations' property
Z - Σラ=ı
taken to be disc(a)
18
24
'The 'binary relevance' approach effectively solves s binary problems, one for each tag 11 One could also apply Theorem 5 s times (drawing a fresh sample of size O (In( for each tag), yielding sample complexity of O 2 ()))
. The result of Theorem 7 improves over this by removing a multiplicative In(s) factor. We also note that contrary to popular belief, Theorem Findicates that the binary relevance approach does require the tags to be conditionally independent given æ order be an effective learning algorithm.

---

T me.mang eap A (0.1 (...... |0, 1]s
and mapping pred DCG
[0, 11 -
as
(Tlemaagooppp)) (p)); = Ex~p(Yi
Σ By
pred (q) E argsort(q)
k= ye, ....,,.))....
Then (7 pred is an LP calibrated pair. Moreover, as shown in Appendix F
DCG Ev-pl 1 (p) min Ex-p!Yy
DOG
S 2r ||dise//l ||q J p (p)lla
q,
REI
where disc (diso(l), ) E [0. 1Ja. Therefore, for any class of "statistic" functions
Q x' } and corresponding hypothesis class H. = pred Q, Theorem establishes establisess that any convex surrogate risk minimization algorithm minimizing strongly proper composite
surrogate loss for - over a suitable class of functions F C [f: X yields an efficient PAC learning algorithm for the RSM learning problem (L, H. DD ( RSMMM) While this
result can be applied to any class Q and suitable surrogate loss v/, the following theorem makes this concrete for the class of commoddoff-mullliinnn
models Quigmeid-of-mmhiinne and a suitably weighted multivariate logistic-based surrogate loss w/wlog that we introduce here (defined below).
Theorem 8 (PAC learning algorithm for subset ranking with sigmoid-of-muttiinear scaled marginal expectations). Consider a subset ranking problem, with X S (x E R' ||x||2 S R2 for some R > 0, y {0, ",. and y IT, and with the DCG loss DC as above. Let T mang exp and pred DCG be as defined above. Let a and Qsigmoid- be as defined in Theorem 7 and let Haaet
militeee mulrilincr := predDCG Qxsgmoid malilinear: i.e. Haart = {h= : X' XII, 3E E 1xxx [wyll S
W Vj s.t. h(x) argsort( W x) Yx}. Let ejwloo {0, r.] E -R be a multivariate weighted logistic-based based surrogate loss defined by
wi gomoo(yy, (y, u) = ンド (#)
1In[11 In(1+e +e + -4) 1m(1 + +c)).
III decode (u) argsort(u). and let Frultilinar be as defined in Theorem 7 Then an algorithm A which, given a training sample S of size m, finds an (s In(11 + JtW / minimizer fs E Fuullilinesr of the empirical surrogate risk m 1= yswlog (yi, fxx.) over Fmultiimar. and produces a 7 7sc-marg-exp ce--mag-exp-statiinne -statistii estimate (x); = a ((fs(x))) and prediction model hig E Hoae muliiiiina given by hx(xx)
Define Dco
(fs(x)) decode (f (or
equivalently, hs(()) ( (Qs(z))), is a PAC learning algorithm for the RSM learning prob- lem (L Humutiliinar: DD Drrssuaae Ruguodd (RSSM) with squared 7 sc-maag-cxxp -estiaation error sam- ple complexity mAAA (c, = = (s 1++hi (t)) ), and with larget loss sample complexity
(c, = 00 A
I.
[|disell ex
(s + In (3)) ( r'e" (s In (+))).
7
Conclusion
We have studied a flexible class of intermediate PAC leaning models that we call realizuble-statisiic models (RSMs), wherein we allow labels to be stochastic but assume that some vector-valued statistic of the conditional label distribution comes from a known function class. RSMs interpolate between the realizable and fully agnostic settings, and also recover several previously studied intermediate PAC learning models as special cases. We have shown that for RSMs where the statistic of interest can be estimated via a convex 'strongly proper composite" surrogate loss, minimizing this convex surrogate loss yields a computationally efficient learning algorithm with finite sample complexity bounds, and have demonstrated applications of these results to a broad range of RSM learning problems including binary and multiclass classification, multi-label learning, and subset ranking.
RSMs are also connected the structured prediction framework studied in [66, where the target loss function can be written as f Ø) = Φ1(x) (v) ( for some embedding functions Φ y - &
Φ2 5 + * and matrix A E 18* k 6 In particular, [66] effectively considers the 'conditional mean embedding" statistic q (z) = Ei 1)XX = xr), and assumes that this statistic belongs to some class of functions (such as multilinear functions or vector-valued RKHS); this statistic is then estimated to produce q(x). Thus this setting can also be viewed as a special case of our RSM framework (indeed, the quadratic surrogate used in [16] is also strongly proper composite surrogate for the above statistic; the target loss based sample complexity bounds of [16] are of the form ((3/e4), where 3 captures problem-dependent parameters, and are therefore comparable to our bounds).
More generally, [16] allows embedding into Hilbert space F.
10

---

Acknowledgments and Disclosure of Funding
Warm thanks to Rob Schapire for valuable discussions and suggestions related to this work; to Peter Bartlett for valuable pointers; and Nishant Agarwal and Ananya Mukherjee for help with typesetting parts of this paper. Thanks also to the anonymous reviewers of this work for helpful comments. This material is based upon work supported in part by the US National Science Foundation (NSF) under Grant No. 1934876. Any opinions, findings, and conclusions or recommendations expressed in this material those of the authors and do not necessarily reflect the views of the NSF
References
[1] Jacob D. Abernethy and Rafael M. Frongillo. characterization of scoring rules for linear properties. In Proceedings of the 25th Annual Conference Learning Theory (COLT), 2012.
[2] Arpit Agarwal and Shivani Agarwal. On consistent surrogate risk minimization and property elicitation. Proceedings of The 28th Conference on Learning Theory (COLT), 2015.
[3] Shivani Agarwal. Surrogate regret bounds for the area under the ROC curve via strongly proper losses. In Proceedings of the 26th Annual Conference on Learning Theory (COLT), 2013.
[4] Dana Angluin and Philip D. Laird. Learning from noisy examples. Mach. Learn. 2(4):343-370, 1988.
[5] Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
[6] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 167- 190. JoLR. 2015.
[7] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learning and b-b compressed sensing under asymmetric noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 152-192. JMLR.org, 2016.
[8] Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long. The power of localization for efficiently learning linear separators with noise. J. ACM, 63()):50:1 2017.
[9] Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. J. Much. Learn. Res., 3:463 482, 2002.
[10] Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1/2):35-5,, 1998.
[11] Matthew R. Boutell, Jiebo Luo, Xipeng Shen, and Christopher M. Brown. Learning multi-label scene classification. Pattern Recognit. 175--17777 2004.
[12] Andreas Buja, Werner Stuetzle, and Yi Shen. Loss functions for binary class probability estimation: Structure and applications. Technical report, University of Pennsylvania, November 2005.
[13] Tom Bylander. Learning linear threshold functions in the presence of classification noise. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 1994, pages 340-347. ACM, 1994.
[14] Gautam Chandrasekaran, Vasilis Kontonis, Konstantinos Stavropoulos, and Kevin Tian. Learn ing noisy halfspaces with margin: Massart is no harder than random. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, 2024.

---

[15] Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. Classification under misspecifica- tion: Halfspaces, generalized linear models, and evolvability. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, 2020.
[16] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 21(98):1-67, 2020.
[17] Edith Cohen. Learning noisy perceptrons by perceptron in polynomial time. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, 1997, pages 514-523. IEEE Computer Society, 1997.
[18] David Cossock and Tong Zhang. Statistical analysis of Bayes optimal subset ranking, IEEE Transactions on Information Theory. 54(11):5140-5144 4154,, 2008.
[19] Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indde innpuuttioo--iddeeeeeennt PAC learning of halfspaces with Massart noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, pages 4751- 4762, 2019.
[20] Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, and Christos Tzamos. Statistical query hardness of multiclass linear classification with random classification noise. arXiv 2502. 1 1413, 2025.
[21] John Dunagan and Santosh S. Vempala. A simple polynomial rescaling algorithm for solving linear programs. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 315-320. ACM, 2004.
[22] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New results for learning noisy parities and halfspaces. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 563-574. IEEE Computer Society, 2006.
[23] David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput., 100(1))78-150, 1992.
[24] Kalervo Järvelin and Jaana Kekäläinen. IR evaluation methods for retrieving highly relevant doc- uments. In International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), 2000.
[25] Sham M. Kakade, Adam Kalai, Varun Kanade, and Ohad Shamir. Efficient learning of general- ized linear and single index models with isotonic regression. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, pages 927-935, 2011.
[26] Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT 2009 The 22nd Conference on Learning Theory, 2009.
[27] Michael Kearns, Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6))9833 1006, 1998.
[28) Michael J. Kearn and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. Comput. Syst. Sci., (66)):4644997 1994.
[29] Michael J. Kearns, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. Mach. Learn., 17(2-3):115-14:1 1994.
[30] Philip M. Long and Rocco A. Servedio. Random classification noise defeats all convex potential boosters. Mach. Learn., 78(3):287-304, 2010.
[31] Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. Ann. Statist., 34(5):2326 2266666666666,, 2006.
[32] Andreas Maurer. A vector-contrrattion inequality for rademacher complexities. arXiv 1605.00251, 2016.
12

---

[33] Mark D. Reid and Robert C. Williamson. Surrogate regret bounds for proper losses. In Proceedings of the 26th Annual International Conference on Machine Learning. ICML 2009, 2009.
[34] Mark D. Reid and Robert C. Williamson. Composite binary losses. Journal of Machine Learning Research, 1:2387-2422. 2010.
[35] Ronald L.. Rivest and Robert H. Sloan. A formal model of hierarchical concept learning. Inf. Comput., 114(1):88-115 114, 1994.
[36] Robert H. Sloan. Types of noise in data for concept learning. In Proceedings of the First Annual Workshop on Computational Learning Theory, COLT '88, pages 91-96. ACM/MIT, 1988.
[37] Robert H. Sloan. Corrigendum to types of noise in data for concept learning. In Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, COLT 1992, page 450. ACM, 1992.
[38] Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1144 1984.
[39] Elodie Vernet, Robert C. Williamson, and Mark D. Reid. Composite multiclass losses. In Neural Information Processing Systems, 2011.
[40] Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pages 1056-1066, 2017.
[41] Min-Ling Zhang and Zhi-Hua Zhou. A review multi-label learning algorithms. Knowledge and Data Engineering, IEEE Transactions on, 26:1819-1837, 08 2014.
[42] Mingyuan Zhang, Jane H. Lee, and Shivani Agarwal. Learning from noisy labels with no change to the training process. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
[43] Mingyuan Zhang, Harish Guruprasad Ramaswamy, and Shivani Agarwal. Convex calibrated surrogates for the multi-label f-measure. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
[44] Tong Zhang. Some theoretical results concerning the convergence of compositions of regularized linear functions. Advances in Neural Information Processing Systems 12, pages 370-378, 1999.
[45] Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, volume 65 of Proceedings of Machine Learning Research, pages 1980-2022. PMLR, 2017.
13

---

Appendix
Organization of the Appendix. Appendix(AAis supplement to Section (introduction). Appendix B supplement Section and main results). Appendix Clis supplement ( classification). Appendix D is a supplement to Section (multiclass classification). Appendix E is supplement to Section [5 [ learning). Appendix Fiis a supplement to Section 6 (subset ranking). Proofs of all the theorems in the main paper can be found in the relevant sections of this Appendix.
A Supplement to Section (Introductio))
Here we give details of the assumptions associated with the previously studied intermediate PAC learning models listed in Table
Noisy LTF with random classification noise (RCN): This model assumes that there is a weight vector E IR and a noise parameter v/ E (0, 1/2) such that for any instance x, deterministic binary label is first generated according to the sign of w x, and then with probability 7 the label is flipped to the opposite sign. Equivalently, the model can be viewed as assuming that the conditional label
distribution is of the form P(Y 1|X x) = (1 7) 1(w x 2 0) + 17 1(w1(www] x 0).
Noisy LTF with Massart noise: This model assumes that there is a weight vector w R and a "noise upper bound" parameter E 1/2) such that for any instance x, deterministic binary label is first generated according to the sign of TTx x, and then with some (unknown) probability n(x)= I y the label is flipped the opposite sign. Equivalently, the model can be viewed assuming
that the conditional label distribution satisfies P(Y = 1|X x) (1 (1-1) 1) if w x 2 0 and
P(Y = 1|X = x) S 17 if w x < 0.
Generalized linear model (GLM): The (univariate) GLMs considered in 26 25 are for valued
regression problems with bounded label spaces y = 5 s [0, 1]. and assume that there is weight vector E IP such that E[Y X x] 0(w x) for some known transfer function 0 RR+(0, 1] (it is often assumed that satisfies some condition such as a Lipschitz property). These include as
special case binary classification by setting y {0, 1}.
Single index model (SIM): The assumption here is of a similar form as that for GLMs above, namely that E = x] = 0(w x) for some weight vector w and transfer function 0 IR - [0, 1]; however unlike GLMs, where assumed to be known, in SIMs, both the weight vector w and the transfer function 0 are unknown (it is often assumed that O satisfies some condition such as Lipschitz property).
B Supplement to Section 2 (RSMs and Main Results)
B.1 Realizable and Agnostic PAC Learning as Special Cases of RSMs
We note here that both realizable and (fully) agnostic PAC learning can be recovered as extreme cases of RSMs. In the following, for a finite set y and E V. ey 1) denotes the unit vector with y-th element equal and all other elements equal to
Example 1 (Realizable PAC learning RSM), Let 5 y, and let H. C :X-y) be a hypothesis class/class of prediction models. Let C = Dy, and consider the identity property Tid Ay Ay defined (p) p. Also define the class of functions Qone-hor-u as Qow-hoot-H {q: 1 x 3h E H s.t. q(x) = eh(z)) Vx E EX. Then it can be seen that
D Duehe
{ (v.P) Axxy
3h E H s.t. p(z) Ch(x) VX E X}
D DH-relaizablle
where Dioseatizalle denotes the class of probability distributions D = (n, D) E Axxy wherein the label Y is (with probability 1) given by a deterministic function of the instance X, with the function belonging to H. Therefore, realizable PAC learning w.r.. for any loss E y is equivalent to the RSM learning problem (L, H, D D Praeee RSM).
14

---

Example 2 (Agnostic PAC learning as RSM), Let H C {h: :->V} be a class of prediction models. Let C Dy. and consider the identity property T Ay defined as (p) p.
Define Dall Axxy and 2a1l {qq X' x+))) Then it can be seen that
(a))RMM) = Dall
{D (H.p) Axxy 3q E Qall s.t. p(x) q()) Vx E x}
and therefore (fully) agnostic PAC learning w.E.t. H. and any loss X2 is equivalent the RSM learning problem (I, H. D (rr))
B.2 Previously Studied Intermediate PAC Learning Models as Special Cases of RSMs
The RSM framework also recovers as special cases all the previously studied intermediate PAC learning models listed in Table
Noisy LTF with RCN: Consider the statistic -+1 defined in Section 3 and the class of statistic functions QRCN-Hinar
{q X - [o, 1] 3w R" , E (0, 1/2) s.t. q(x) (1 7)) 1(w x 2 0) .n I(w x < 0)}. Then the RSM learning problem (7,0-1, Hinnaa, D( QucN )-RMM) captures exactly the problem of learning linear threshold functions with RCN.
Noisy LTF with Massart noise: Consider again the statistic 7-1 defined in Section 3, and now the class of statistic functions Q QMassart-lneess = {q : X
[0, 1] 3w 1)
(0, 1/2) s.t. q(x)) > -1-1
v1) if w "xx O and g(ar) " if w x < 0}. Then the RSM learn-
ing problem (T,0-I, Hiinaar D(r+t Qutaoniinen)--SS (RSM) captures exactly the problem of learning linear threshold functions with Massart noise.
GLM: Let IR [R, 1] be a fixed (known) transfer function. Consider again the statistic + defined in Section 3, and now the class of statistic functions Qa.M := {q X - [0, 1] Ew E IR" s.t. g(z) = ((w {x))). Then the RSM learning problem (L0-1, HHlnear, ((r-1 ..an RSMM captures exactly the
problem of learning GLMs with transfer function 0.
SIM: Consider again the statistic -+1 defined in Section 3, and now the class of statistic functions QSIM := {q X' X [0, 1] 3w IP,0 0 [0, 1] s.t. q(x) 0(w Twwxx x)). Then the RSM learning problem (L Htinear, P(r+) Q RSM) captures exactly the problem of learning SIMs.
B.3 Proof of Theorem 1
Recall that we denote
erl [h]
erb [[H]
inf [b[[]]
heHt
erb
inf erb(h);
erp è fl Bxx,))-((((YF(())) x()))
h
er") [
= inf er [f]
fEF
er FR
inf
[f)
Proof- (of Theorem Let f E F and D (u.P) ((T. We start by setting up some notation. Define q" Q q" (x) r(p(r)); define f" e F as = (z)) = ([((()))); and define q E Q as (σ)) x (((x))))
Now, have [7! erp L. to this, note that since (T, pred) is an L-calibrated statistic- mappe mapping pair, the Bayes optimal classifier h satisfies
I. (x) = pred( (red(T(p(x))) = pred(q (x)),
and so hh pred Q = H, which gives erh"- I.-
15

---

Also note that
h(x) decode(f(x)) pred(A (((((<))))) pred(q(z))
Thus, we have,
ert, [h] - er [h] - erb"" (since ert [7] erb) erbi))
Ex Ey BY min Ey ~p | DEY
Ex Ey Ey~p(X) (T
min By Ey~p(x) (Txss)
yey
I Ex (p(())) (by given condition)
(((]))-(((X()) (((x)))
S K [ -
(by Jensen's inequality applied to the function ((u) n²)
2
S
Ex (Ey-ppxx|(
(by 7-strong proper compositeness of (6)
=
R
Ex
-B (x-D(x)(VXYx -x (xxx,)))((XXXxxx)))))
7
2 [rr](]] - ero()()
[r e111
(since strong proper compositeness of & and the definition fr also imply - for D of the given form that
E(x,y)~D f (X))]
Do ((x)((X)) Vf X+RRR
and therefore er [[*] = er = (F))
B.4 Proof of Theorem 2
Let us start by stating the following uniform convergence result, which relates the empirical and expected surrogate risks for bounded surrogate loss vé acting on vector-valued predictions, uniformly for all functions in vector-valued function class F, in terms of the di covering numbers of the loss class uh The result follows from straightforward generalization of standard uniform convergence results for real-valued function classes (such as given in Chapter 17 of [5) to vector-valued function classes.
Theorem (Uniform convergence for bounded (surrogate) loss classes in terms of dj covering numbers). Let X be any instance space and y be any label space. Let d E Z, and let th y x Rd +R__ be (surrogate) loss function. Let F C {f X-RR) and suppose vy f(x)) e
10, B Vo E X,y E y.f F for some B > O. Then for any Z44 any > 0, and any
D E ANXY,
PS-Dm
jer feF
sup
-r [fg)
2c)
<
4NG(e/8, 2mme mme /(32B²)
We will now prove the following technical lemma, which upper bounds the d1 covering numbers of the surrogate loss class t for surrogate losses z that act vector-valued predictions and that are Lipschitz with respect to the L' metric - in terms of the d, covering numbers of the real-valued "projection' function classes Fi This lemma may also be of independent interest.
16

---

Lemma 1 (Bounding d1 covering numbers of loss function classes by for Lipschitz losses vi acting on vector-valued predictions). Let X and y be any sets. Let y x -R., be any (surrogate) loss function that is pi py-lipschitz in the second argument with respect to the I, metric, and C x-T)) be any class of vector-valued functions on X. Let
V =
V-RR IFf E F s.t. (1 v) = VVV, (x)) Vx (
For each! j E [d], let Fi {f, : X X B E FE f)(2) (f(x)); Vr). Then for any e > 0 and m E Z+,
d Vi(e, & II F( 1
(EI,..., ,mm) ((11, V1)..... (Tm, ym E (X x y)m and denote x (FI..... Fm) E X For each j E [d], let Cj C R be an (e/p)) for (F)) )/x with respect to the d1 distance. We will construct an e-cover
Proof. (of Lemma Let > and E 2+. Fix any
C IR for (1>))2 with respect to the dj distance of size |C| = II
Let E F, and denote (1F))2 = (1r(21),.... v)((m)) E IR,; moreover, for each j E [d]. let fa : X-R defined as fz( = (f(x)), and denote (fi)ix = (f.(=))..... (Tm)) For each
j [d]. let u (u)..... uen)) C2 be such that d1 d1((f)) w') (/(dd). For each i E [m], define the d-dimensional vector u, (ut,..., u E Rd Now consider the m-dimensional point
V := (l((m. = (vb(,, un ................... (ym: um)) E I. Then we have
(1((F)))2) v) = m
(2:) - m/l
1 m
Jy f(x:)) - (1 u:)l
m
1 m
P1
(x,) n2]
(by P1 Pi-Lipschitzness of of w.r.t. L²)
m
j=l
d
Σ
di d1((f))xx.
= P1
j=1
d
I P1 Σ
pid
j=1
E.
Therefore the set
{v { ((. u² C, Vj} R m
is an e-cover for (1/)) with respect to the d, distance. Since |C| < I Icyl the claim follows.
Next, the following result shows that uniform convergence of surrogate risks also implies (surrogate) learning results for approximate empirical risk minimizers. The proof technique standard (such as given in Chapter 19 of (51): include self-contained proof here for completeness.
Theorem 10 (Uniform convergence implies bounded (surrogate) regret of approximate (surro- gate) risk minimizers). Let X be any instance space and y be any label space. Let d E Z4 and let 3) : Rd be (surrogate) loss function. Let F S {f: X X-RRA, Let maee RR x (0, 1] be such that for every e >> O, every E (0. 1), every m 2 Muc (e, 8), and every D E Axxy,
P PS sup FEF
er [
[ - [1 26) < 8.
Let (amm) (mm)) be a sequence of positive real numbers such that for every e >> 0, every (0, 1). and every 2 macle/3, (t/3,0), 8). we have am S E//3. Let A be approximate surrogate risk minimization
17

---

3 algorithm which, given a training sample S = ((11,81).... (Zm, Fne)) E (X' x V) of size m. returns Om approxxnnae minimizer fs F of the empirical up-risk m E (yi. f(x))) over F, so that 1 Di=1 (Vi, fs(x))) < infreF +h2 - ( f(xx)) + am. Then for every > 0, every ò E (0, 11, every m 2 mac mac (e/3, 8), and every D E Axxx.
PSDD (er) [
inf er b [P] 26) S 8.
fEF
Proof. (of Theorem 10) Let > 0, E (0, 1]. and D E Axxy. Let 3 > 0, and let f E F be such
that
er f S inf er [f] +
fEF
Let m muc(e/3,0) Then we have the following with probability at least 1 5 over the draw of ~ D
sup
ler
er5((] Se.
fEF
and therefore,
er
[ss]
A. ff
inf er's [f] + am fer
+
2c
inf (f FEF
2e
[f(
3
[f'] [f') + 9)
2c
3
inf 5f [f] + 8
FEF
Since the above holds for B > O, we have that with probability at least 5 over S D
er Th fIfsl s inf er [F]+ +c.
FEF
This proves the claim.
Next, we define the surrogate sample complexity below:
Definition (Surrogate sample complexity). Let C' C R.d. Let 1) 3 x C' +R+ be any surrogate loss, F C (f: X-CC' be a class of surrogate prediction models, and D Axxy be class of probability distributions. We will say an algorithm A that given a training sample S E (X x 7) returns surrogate prediction model is F is learning algorithm for the surrogate loss learning problem (H,F,D) with surrogate sample complexity function m A 1R X (0, 1]-244 for every e > 0, E (0, 1), every distribution E D, and every m 2 mx 8),
PS-Dm
(er%) [s
[sl fslss-jnn inf er!l fej
8,
and moreover, for every 5, m ( 5) is the smallest integer satisfying the above.
Bringing all the above together, under the conditions of Theorem 2 the following result upper bounds the surrogate sample complexity of an approximate surrogate risk minimization algorithm in terms of the d1 covering numbers of the real-valued projection classes F).
Theorem 11 (Upper bounding surrogate sample complexity of an approximate surrogate risk minimizer via di covering numbers). Under the conditions of Theorem 2 the (16B) (6B//m) mm)- approximate surrogate risk minimization algorithm A is learning algorithm for the surrogate
18

---

learning problem (15, Axxy) with surrogate sample complexity upper bounded as m²)(e,)) < min {mo E 24 Z mo
288
(Ei=1 In (Ni (ziora Fr .2.22m In (#))
In particular, if (Ni(,,F), Fi,m)= S olc, FI
Vj E [d], then we have
6) & 288B Σ j=1 In (o) (zieTa:)) + +m (1)
Proof. (of Theorem 11 Define mas .R (0, + as
mge(e,)) == min {mo E 24 : m 2 mg
32B²
ESi=1 In (Ni Fi, .m)) + In (1)
Then by Theorem 9 and Lemma 1 we have that for every 0, (0, 1), mac 8), and D E Axxy,
P PSwDm Dm
fEF [r crgiff] 26
supper
sup
8.
Next, define sequence of positive real numbers (am Jmez,
16B
Om =
vm
Then it can be verified that for every e > 0, (0, 1]. and m 2 (e/ 8). we have om S e/3. Therefore, by Theorem 10 ampappoxx surrogate risk minimization algorithm as described satisfies for every c > 0, d E (0, 1], m 2 m (c/3, 5), and D E Axxx.
P (et)
inf er o 2c) $ 6.
FEF
Thus we have m (e,6)
s mue (ec(e/3,))
min {mo E 2 : m 2 mo
288B2 EE In (Ni Fi 2m)) + In (1)
m
Moreover, NE, m) S (f,, Fi) Vj E [d]. this yields the stated bound.
Finally, we will also make use of the following proposition, whose proof follows directly from Theorem
Proposition 12 (Upper bounding squared r-estimation error sample complexity and target loss sample complexity in terms of surrogate sample complexity). Under the conditions of Theorem 7 any learning algorithm A which given training sample S, finds surrogate prediction model fs F and produces a statisstic estimate qs(x) X - -1 (fs(x)) and a prediction model hs(x)) = decode(fs(x)), satisfies
7E6
(c,
I m 2 2
762
()) 8) I m
26
Proof. (of Proposition 12 Follows directly from Theorem
The proof of Theorem is now immediate:
Proof. (of Theorem 2 Follows directly from Theorem 11 and Proposition 12
19

---

B.5 Proof of Theorem 3
Let us start by stating the following uniform convergence result, which relates the empirical and expected surrogate risks for bounded surrogate loss acting on vector vector-valued predictions, uniformly for all functions in a vector-valued function class F, in terms of the Rademacher complexity of the loss class y.. The proof is standard (via an application of McDiarmid's inequality; see e.g.
Theorem 13 (Uniform convergence for bounded (surrogate) loss classes in terms of Rademacher complexity). Let X be any instance space and be any label space. Let d E 2+ and let Y x Rd -R_ be (surrogate) loss function. Let J S {f X X-RR and suppose f()) E 00, BJ Va E X, v,f= F for some B > Then for any m. E 2 any e (0, 1J, and any D E Axxy, we have with probability at least 1 - 5 over the draw of S ~ D
1n(2/5)
sup
teF [ro @r5(
2mm(()5)) BV
m
We will make use of the vector- cestor-onttaatton inequality for Rademacher complexities, due to Maurer [3]. which upper bounds the Rademacher complexity of the surrogate loss class ęiyx for surrogate losses v that act on vector-valued predictions and that are Lipschitz with respect to the Euclidean metric in terms of the Rademacher complexities of the real-valued 'projection' function classes F
Lemma 2 (Bounding Rademacher complexities of loss function classes dh for Lipschitz losses vi acting on vector-valued predictions (32). Let and be any sets. Let v y RR be any (surrogate) loss function that is p2-Lipschitz in the second argument with respect to the Euclidean metric, and F S {f X X-R be any class of vector-valued functions on X. Let
2 = { : X x V-R 3f E F s.t. vr( v) = (f(yf(z) Vx E For each j E [d], let Fi (fr
Ef E s.t. fz(z) (f(x)), VrJ. Then for any m E Z+.
Rm (wr) S 22p Σ Run Rm)(
Bringing the above together, under the conditions of Theorem 3
the following result upper bounds the surrogate sample complexity of an approximate surrogate risk minimization algorithm in terms of the Rademacher complexities of the real-valued projection classes F
Theorem 14 (Upper bounding surrogate sample complexity of an approximate surrogate risk minimizer via Rademacher complexities). Under the conditions of Theorem 3 the (2)))-) approximate surrogate risk minimization algorithm A is a learning algorithm for the surrogate learning problem (1/, F, Axxx) with surrogate sample complexity upper bounded
(E, I min { mo En :m mo
3 322V2p2 Rm B
ln(2/))
c
In particular, 3C > such that the Rademacher complexities of the function classes have upper bounds of the form Rm, (F') S Clvm Vj E [d], then have
9 (2 BBL+n///))/2
() s マ
Proof. (of Theorem 14) Define mix RR+ (0, 1 as
mae(c, 6) = min mo E Z_ m 2 mo =
( (2/2p2 Σj= Rm, B
In(2/8) S
20

---

Then by Theorem 13 and Lemma 2 we have that for every e > 0, 8 E (0, 1], m 2 muc 8), and
D E Axxy.
P PS
sup
[r
1r 26) 8.
teF
Next, define sequence of positive real numbers (amm JMEZ, as
am = 2/m
Then it can be verified that for every > (0, 1], and m 2 mec(e/3, 8), we have am S e/3. Therefore, by Theorem I0 an approximae surrogate risk minimization algorithm as described satisfies for every 8 E (0, 1], m (cc /3, 8), and D Axxy.
PSwD (er) [s]
inf er D [f] 26) s 6.
FEF
Thus we have
m (e < mee(e/300)
< min mo E z_ :m 2 mo
3(2v2p2 Ej= Rm((F) + B
In(2/5)
S cc
Moreover, Rm (F) & Clvmmjjjj [d]. this yields the stated bound.
The proof of Theorem 3 is now immediate:
Proof. (of Theorem
Follows directly from Theorem 14 and Proposition ??.
B.6 Proof of Proposition
Proof. (of Proposition
(i) This is well-known result (e.g., see [
(ii) This well-known result (e.g.,
44
(iii) This also a well-known result; we provide self-contained proof here completeness. The fact that Ry, (Finsar) > 0 follows directly from the fact Fincar is closed under negation. For the upper
21

---

bound, we have
1
Rum (Fiinar)
E
sup
Xi
w.llw]lasW
m
sup
W
m
w.llw]:SW
sup
(by Cauchy-Schweer
m
w.llwl.sM
W
C;X;
m
i=1
2
W
E
Σ GXS
m
W
n
n
E
csty (xTxx))
m
j=1
W
E
GE xx]
(by Jensen's 's inquality)
W
E
Tass (x]xx)
m
W
x 1
m
RW
m
C Supplement to Section 3 (Binary Classification)
Lemma 3. (r+1, predd"l) is calibbrate statistic- pair, with
Ey-p [T..1 min
Sy>pl/00/ I 2 P+1l Vp E A E [0,
0E(+1}
Proof. (of Lemma 3 Calibration of (7+1, I) for L is immediate, since the Bayes optimal Morcover, for any
classifier for 0-1 is given by *(x) sign (x) 1))
10
22

---

(+1), [0, 1|, we have
Ey~pl [
min Ey [Ly] ]e(+1)
Y.pred (w)
Ey (predd))
(4) # Y)
min Ey-p + Y)]
]E{=1}
- P+1 (prred 11 (g) * +1) + (1 - P+1) 1 (predd 01 (g) # -1) min(p+1, - P+1)
p+1 1 - (1 p+1) 1 1 min p+1 p+1)
2
- (2p+1 1) l < 2' P. 2
+ )
2p+1) 1(4 2 2 3PP+1 < 2
2 2|p+1
1 1(( <
2
2.P-1
)
2
1
+
1 2
2
p+1 < 2
1
< 2 - -
Proof. (of Theorem Consider the (invertible) logit link function À |0 1]-R and inverse X-1 R [0, 1] given
X(p) In
p p
X (') = 1 e-u
Note that - here is equivalent to the sigmoid function (defined in the theorem statement). We will observe/prove the following:
(1) Hinear = m-
Sfggmoid-of '
(2) fox a 4-strongly proper composite surrogate loss for + with link function
(3) sign pred -=
(4) Funerr
Qsigmoid-of-linear
(5) lox (y. (xx) S In(1 RW) v(x,8) E X V.fe Fimear:
(6) glog is 1-Lipschitz with respect to the L metric (equivalently Euclidean metric) on I;;
(i Frinear; m) (
(8) 0 S Rm (Finca)) S RW/ /m.
The result will then follow from Lemma 3 and Theorem 3 Parts (1), (3), (4), (5) are immediate from the definitions.
Part (7) is well-known result (e.g. see (5).
Part (8) is well-known result (see Proposition 4).
Part (2): glog is known to be a 4-strongly proper composite loss for the property ++1 (i.e., for binary class probability estimation) with link function
above 3
Part (6): is well known (and easy to verify) that the binary logistic loss do is 1-Lipschitz with respect the L' (equivalently Euclidean) metric R (to verify this, note that the absolute value of the derivative of Glog with respect to the second argument is upper bounded by 1).
use C' RR. here. Technically, would also need extend the definitions of the surrogate loss fox (and the mapping decode = sign) to act on E instead of R: we ignore this issue here for simplicity.
Note that in the notation of Definition
23

---

Combining all the above together with Lemma 3 and applying Theorem 3 (with = 2, = 4.
P2 L. d 1. < (ineer) I RW/Vnn m and B In + e )) gives the desired result with squared --1 estimation enror sample complexity
m (c _
22V2RW (In(1 + e )) (m(210)
2x
(1))
o
and with target loss sample complexity
m
1
(c,
-
36 c
2v
22/2RW + (In(1 n))) (\n(//)))()))))) vn(215)
1 In
(5) )
1
0
D Supplement to Section 4 (Multiclass Classification)
Lemma 4. (r (()) is L calibraaali statistic-mapping pain, with
Ey (m)) ((0
min Ey~pl pT (
S /2. ||q -Pll v An.
5E[n]
Proof. (of Lemma Calibration (T pred for L0-((n) is immediate, since the Bayes
optimal classifier for L (-1(m) is given by DD (x) = (m1) (p(x)) = (- (pd())))))
0-1mm
Moreover, for any p.q E An, have
(11x)) Ey Ey-pl4 Y.pred (c))
min By (-1(n)
DE(n)
Σ Pv 1.pred0-1
(m))))
min
Σ
Py
I (-1(m)
(E(n
y=1
p (ll(m)
(-1(n)
((
gE(n] 7
min
p
p ((
(l(n))
max
Iea) (q)
VE(n]
max
(p q)
1 (nn (q)
(l)())
+ qq"
((
((0)))))))
-t 2(((1))
[e[n]
(p q) T (())
p2l(m)))
(by definition of (
max [e(n]
I
||p
a/|a max
(-((m)
Eg
||2 (by the Cauchy-Schward inequality)
((0)
jE(n
V2. | p|
(since the difference between any two columns of L [-1((x) has at most two non-zero entries, each with magnitude at most 1)
24

---

Proof. (of Theorem 6 Consider the link function A A. A,- with extended inverse X R² -A, given by
(X(p)) In(py), 600
(A (u)) = Σy= cM
Note that A here is equivalent to the softmax function a (defined in the theorem statement). We will observe/prove the following:
(1) mmutiillss-llnn = pred (0n))
@sotmaxxof-mliiear:
mloog is 1-strongly proper composite surrogate loss for 7 with link function A;
(3) (1( = (xe) A=
(4) F Tintielass-
2cottma--o-mlinerr
(5) amlle (v, f(x)) < In(n) + 2RW v(x,8) X 3r,f E F
multichass-inneri
(6) y mmlog is 1-Lipschitz with respect to the L metric and 2-Lipschitz with respect to the Euclidean metric RR;
(7) [c,
multiclass Tinear: m) S ( by E [n];
(8) 0 S Rm FF
RW m Vy [n].
multiclass-linarr
The result will then follow from Lemma 4 Theorem 2 and Theorem
Parts (1), (3), (4), (5) are immediate from the definitions.
Part (7) is well-known result (e.g. see (5).
Part (8) is well-known result (see Proposition
Part (2): simog has been shown be 1-strongly proper composite loss for the property idd (i.e., for
multiclass class probability estimation) with link function as above [42 y
Part (6): To see that mlog is 1-Lipschitz with respect to the T metric, note that
OummloR u)
Juy
e
myle (y. u) Duy
"n""
Ay øy.
Σ =1 en
e"
Thus we have, mimo (y, un) mlog (y, Uz)
V (o (y,, uz)) T (mi Uz) (by convexity of simlog (y. -)) mlo (y. ur)lloo I uzlla (by Hölder's inequality) ||u u (since mlog (u. u)/Ouy' S V1y" E [n]).
"Note that in the notation of Definition 3 we use C' R² here Technically, we would also need to extend the definitions of the surrogate mlog and the mapping decode act on E instcad of R" we ignore this issue here for simplicity. Also note that here, C An is in one-to-one correspondence with only a strict subset of C R.. and
extended inverse; in particular, we the partition S (Sp p E A.) of C' = R given by Sp = {u E R" 3e E IR s.t. = In(py) + vyy..
'Not that [42] show this result for slight variant of 4 mlogg that acts on I8" "-1 rather than R² however. essentially the same proof works for the variant
here well.
25

---

Next, to see that smiogg is 2- 2-Lipschitz with respect to the Euclidean metric, note that gimmlng (y. u1) - yimlo (y, uz)
x mim (y, 11) (n U2) (by convexity of aisilu (y. :))
aambo (U: U1 U1)ll2 Ilu u2lla (Cauchy-Schward inequality)
V mlme (U. u1)1 |lu u2l12
2. I U2 12ll2
(since arbmloo (y. u)/ u)/Ouyl $ and
ex
Σ
@ (,, u /
1 1 vy + y)
Zy== e"vv
""
(i) Combining all the above together with Lemma and applying Theorem 2 (with &. 2 7
P1 1. n, (N, Fy multiclas--ineaa" m) I (2)² Vy [n]. and B I In(n) 2RW) gives the
desired result with squared 7 estimation error sample complexity
1152 (In(n) + 2RW)2
48n
4
mp In
In
2²
c
(In(n))2
np npln In ) + In
8
and with target loss sample complexity
0-1m))
4608 (In(n) + 2RW)2 e4 = o (In(n))2 npln (((
96n
mA
(c,6)
np In
e²
+
In
5)
n
+ In
(ii) Next, combining all the above together with Lemma 4 and applying Theorem (with V2.
? 1, P2 = 2, n, S RRm (Frll (55 multiclas--inees S RW7 / Vy E [m]. and B In(n) + 2RW)
gives the desired result with squared 7'd estimation error sample complexity
" $ (4V2RWn (In(n) + 22222 21(210)((23))
36 -
n + (In(n))) In
0
2
and with target loss sample complexity
m
((n))
(c,
- (4/2RWn+ + (In(n) + 2RW) /nn(28))
144
o
(
1
n² (In(n))² In
( ))))
Combining the above bounds yields the desired results.
E
Supplement to Section 5 (Multi-Label Learning)
Lemma 5. marginals tred is
sta.s/aieddttttisssiicaappppppp pair, with
Ex Iamm min {E(0,1)>
pred
Ex
Uam I 2/5 munginaaa
murginals (p)ll2 Vp E A 1).
Proof. (of Lemma Calibration of murginals lamy for L lam is immediate, since the Bayes optimal classifier for L Ham is given by rr Ha (x) (m (p(x))). Moreover, for any
26

---

(0.1),, [0,1]" we have
Ham Ey Byy / prodftim (q))
min
Ey up LY
Ham
$E(U.1}
=
Σ Ey, (prdaaa
min (0
Σ
Ey, y
j=1
(by linearity of expectation; here L E R binary loss 12.0
(0.1)x(0.1)
denotes the
1 # y))
Ey, [
Σ
min Ey, 0-1 {
Ey, [4g (prood)
min Ey, |,,
9 (001)
$ Σ |gj (T marginals [p)]]
(by well-known result for binary 0-1 loss, as also shown in the proof of Theorem 5
2 q T marginals (p) 1
< 2 q
marginals
( l|2
Proof. (of Theorem 6 Consider the (invertible) link function A 10,1]*- and its inverse A
K - 1] given by
(X(g)); In
4j
1 9j
(A (A)
+ +ey
Note that each component of A statement). We will observe/prove the following:
here is equivalent the sigmoid function (defined in the theorem
(1) H sigu
Ham
Ham
muliiinnea
sigmoid--of multilinear?
(2) y BRlog is 4-strongly proper composite surrogate loss for marginals with link function A;
(3) decode Ham = Ham Ham
A -1;
(4) Fmulilincar A Quigmodd-of-mutllleerr:
(5) y BRlog (y, f(x)) s sln(1 + e RW) v(x, v) E X V,fe E Fmultilincar'
(6) 4 BRlog is 1-Lipschitz with respect the L' metric and Vi-Lipschitz with respect to the Euclidean metric on IR;;
(7) Mi,c, Fr multilinear m) < (2) Vj
[s]:
(8) 0 < Rm (F' multilinnaa
< RW m Vj E [s].
The result will then follow from Lemma 5 and Theorem 3
Parts (1), (3), (4), (5) are immediate from the definitions.
Note that in the notation of Definition 3 we C' R² here. Technically, would also need extend
the definitions of the surrogate loss & and the mapping decode to act on R instead of IR": we ignore this issue here for simplicity.
27

---

Part (7) is well-known result (e.g. see (5).
Part (8) is well-known result (see Proposition 4
Part (2): The fact that v/ BRiog is 4-strongly proper composite loss for the property marginals with link function À as above follows from 4-strong proper compositeness of the binary logistic loss (vb as defined Theorem 5) for binary class probability estimation, applied separately to each component of the loss 33.
Part (6): The fact that BRlog 1-Lipschitz with respect to the L' metric follows directly from the fact that the binary logistic loss (uitog as defined in Theorem 5) is 1-Lipschitz with respect to the L' metric, applied separately to each component of the loss. This also implies is Vs-Lipschitz with respect to the Fuclidean metric.
Combining all the above together with Lemma and applying Theorem (with 2/8,7 7 P2 = Vs, d = 8, 0 < (F)) & RW/ /m vj. and S s sIn(1 + RRW 1) gives the desired result with squared y marginals estimation error sample complexity
MA
mariials
(c,
2222RW5>
3/2 + s(In(1 + e ()
4e
1))
= 0
2
+ In
8
and with target loss sample complexity
36s² e4
m
I.
(c,6)
(2
3/2 s(n(n1n11111 + (
s
0
s
In
ed
F Supplement to Section 6 (Subset Ranking)
Lemma 6. Wo-gg-gg- pred
DCG
is an L
-ccl-cbabbatted statistic-mapping pair, with
Ey
D DCG
(a))
min Ey (T.(CC) < 2r 2/d/ccis
||q
se-marg-epp (p)ll2
Fell,
vp E (o.1.... . [0,
where disc (disc(1), di E [0, 1Ja.
Proof. (of Lemma Calibration of (r DCG for DCG is immediate, since the Bayes optimal classifier for DCG is given by hn (x) argsort(> murg exp (p(x))
DCU 7 se-mrg--epp (p(x))). In the following, for any q E [0, 1] we will denote
#9 == DCG (q) llg.
and for any से E II,, we will denote
disca == (ids(((().....dd((((())) {0,
[CONTINUED ON NEXT PAGE)
28

---

Then for any E A (o.1.....) E [0, 1]", we have
Ey~pl yreedoo (a)) (q))
min E [ REll,
= Ey~p
Z -
disc (i))
- min Ey-p #EIT.
Z -
Y disc(#(()))
max Rell,
Ex-p D disc(T(())) E Ey-p (V -isco (79
(by linearity of expectation)
= max Rell,
Ey, [rg] (iisc(F()))
Ey, [g] disc(
= r max RElL,
Nc mang exp (p)), discc (((s)
NC marg exp (p)); (isc((99())
se-marg-exp (p)) (disc(F(i)) disc disc((
= r max
Rell,
Sc-mang--xpp (p)); (3) (disc(f((i)) disc (F))
max
RETT,
Σ qj (diso(f(j)) disc (isdd(f((())))) (+9)))
< r max REIL.
(T (o-mmarg-oxp(p)) (p)); 93) (diso(f(f)) - disc(f
(by definition of #9)
j=l
( --s-murg--ea wap. (p) -q) (disc; discas)
r max
Rell,
r max FEll,
|| Ne-mmgrr-ee exp (p) 41l2 disse; discas llz
(by the Cauchy- Schwarz inequality)
< 2r
max REll,
|disc 112 |/9
marg exp (p) 12
= 2r disc
2 ||q T sc murg exp (p)ll2
(since | || = disc V7 E IT.).
Proof. (of Theorem 8 Consider the (invertible) link function A 10,1]==>²* and its inverse
F
|0, 11ah given by
(A(q)); = In
Qj
1 - 9j
(X (A-) 1 --
Note that each component of A statement). We will observe/prove the following:
here is equivalent to the sigmoid function (defined in the theorem
(1) Wsoort mukiiinear
DCG
(2) 2 wlog is 4-strongly proper composite surrogate loss for mo-man exp with link function A;
(3) decode DCG DCG
DCG
x -1
(4) F Fmultilincar A
Afgmood--o-mulliinsss
Note that in the notation of Definition 3 we C' R here. Technically, would also need extend the definitions of the surrogate loss & and the mapping decode to act on R" instead of IR": we ignore this issue here for simplicity.
29

---

(5) v y (y. f(x)) I s in(1 + ) v(x, v) E E X' V.f E F
imutillioear
(6) wh is 1-Lipschitz with respect to the L metric and Vž-Lipschitz with respect to the Euclidean metric on IR:
(7) Ni(c, F multilinear m. - (:) Vj E [s]:
(8) 0 S Rm (F)
S RW/ m Vj E [s].
multilinear?
The result will then follow from Lemma and Theorem Parts (1), (3), (4), (5) are immediate from the definitions.
Part (7) is well-known result (e.g. see (5).
Part (8) is well-known result (see Proposition 4).
Part (2): We show here that vimlug a 4-strongly proper composite loss for the property T merg exp with link function À above. In particular, we have:
Ey Sppppu (Y, u)
woog (Y, A(T ex- (p)))]
E[Y))
(In(1 [I(1++--)) 1n(1 +e (A(T (
(p)))))))))) (p)))s) )
+ (1 (1-1 _
- In(1 + ( (11li
sc-marg-oxp (p))} Vlll - ())),)) + In(( (
S0-MMr----P -o-.mm-----pppp)) (D)),) (
(p (p))s) ( (Inn(1 InnInn11 (A- + In(1 1 (aa-mmrr-ess (by definition of À and X-1
Commmng exp
S sc-murg cap
(p))
In (p))
in (
(T sc-marg- (p))
(f))a)
- (A (u)),
DKL (T sc-marg-exy (p)),
|| (x)))
(by definition of Kullback- divergence for binary-valuce random variables)
((>-)(u)); (T marg exp (p)); (1- (x- (1 (T mang exp (p))))))
(by Pinsker's inequality and properties of the total variation distance)
2
Σ j=1
2 (2 (u))) - (7 se exp (p)), (pm)))
2 A
so-marg-oxp exp
2 | (u)
so-marg-on exp
Thus wlogg is a 4-strongly proper composite loss for the property 7 marg exp with link function X.
Part (6): It is easy to that the weighted binary logistic loss wiwl [0, 1] R R+ defined as
s wing (ar, u)
In(1 +e +e-") (1 a) In +*)
1-Lipschitz (in particular, the absolute value of the derivative with respect to is upper bounded by 1). The fact that the surrogate loss woog is 1-Lipschitz with respect to the L metric then
30

---

follows directly from this observation, applied separately to each component of the loss (with weight 43/r for component j). This also implies is /s-Lipschitz with respect to the Euclidean metric.
Combining all the above together with Lemma and applying Theorem (with x: = 2r ||disc||2 2. Y 4, P2 Vs, d = 0 S Rm (F) S RW/ m Vj, and B S s In(1 + eRW) )) gives the desired result with squared T - estimation error sample complexity
2V/RR 5/2 + +[In(1 + +e (W))) Vlm(2/0)) 2
m
(c. S
4e2
52
))
$ In
and with target loss sample complexity
m
0,00
(c,5)
36r
||dis||
2222W + +(In(1+cc
+ (
r 2
disc
(s In
1
0
e²
s In )))
o
(since |disc||2 S Vs).
e4
31

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the results are clearly stated and explained in the paper, and proofs are provided in the Appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [NA]
The paper studies learning problems that in many ways more general than those studied previous work. Both sample and computational complexity bounds are provided for the algorithms discussed. We do not foresee any significant limitations.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
32

---

Answer: [Yes]
Justification: For all results in the paper, all assumptions are clearly stated and complete proofs are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
33

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttp://gguddeeeeeeouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
34

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:p/ps..aaaapp..cppp/ppa/eeea
Answer: [Yes]
Justification:
We have made every effort to conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: While this work can lead better understanding of various types of learning problems and their possible solutions, the work is largely theoreticalffoundatina in nature and does not have immediate societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks (there are no data or models to be released).
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets of the form described.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
37

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
The core method development in this research does not involve LLMs any important, original, or non-standar components (nor does the writing of the puper use LLMs in any form).
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
38


Reviews:
[{"review_id": "XXCsi5Koy2", "reviewer": "Reviewer_ELKR", "summary": "This paper introduces realizable-statistic models (RSMs) for a broad class of PAC learning problems. RSMs allow for stochastic labeling but assume that some statistic of the conditional label distribution is realizable from a known function class. This generalizes GLMs to broader function classes and learning problems. This paper proves that convex surrogate risk minimization with proper composite losses yields learning guarantees, across tasks including binary, multiclass, multi-label, and subset ranking.", "questions": "While this work compares with some binary classification methods in the table, it would be better to elaborate more on this comparison, for example, the assumption needed.", "limitations": "no", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: This work provides general PAC-learning guarantees with stochastic labels across several tasks using RSMs. This work using a general framework to connect various loss functions, learning problems, with results in various prediction types (binary, multiclass, multi-label, ranking). Weaknesses: While this work compares with some binary classification methods in the table, it would be better to elaborate more on this comparison.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. Please find below our response to your question.  \n \n**Q1:**  \n \nWhile this work compares with some binary classification methods in the table, it would be better to elaborate more on this comparison, for example, the assumption needed. \n \n**Response:**  \n \nRegarding the entries in Table 1: The assumptions associated with the RSM entries in the table can be found in the corresponding sections of the paper. The assumptions associated with the GLM entry can be found at the end of Section 3 (lines 242-247). Here we elaborate on the remaining three entries (we will also try to add these details in the final version of the paper if accepted):  \n \n*Noisy LTF with random classification noise (RCN): This model assumes that there is a weight vector ${\\bf w} \\in R^p$ and a noise parameter $\\eta \\in (0, 1/2)$ such that for any instance ${\\bf x}$, a deterministic binary label is first generated according to the sign of ${\\bf w}^{\\top} {\\bf x}$, and then with probability $\\eta$ the label is flipped to the opposite sign. Equivalently, the model can be viewed as assuming that the conditional label distribution is of the form $P(Y = 1 | X = {\\bf x}) = (1 - \\eta) \\cdot {\\bf 1}({\\bf w}^{\\top} {\\bf x} \\ge 0) + \\eta \\cdot {\\bf 1}({\\bf w}^{\\top} {\\bf x} < 0)$. \n \n*Noisy LTF with Massart noise: This model assumes that there is a weight vector ${\\bf w} \\in R^p$ and a \"noise upper bound\" parameter $\\eta \\in (0, 1/2)$ such that for any instance ${\\bf x}$, a deterministic binary label is first generated according to the sign of ${\\bf w}^{\\top} {\\bf x}$, and then with some (unknown) probability $\\eta({\\bf x}) \\le \\eta$ the label is flipped to the opposite sign. Equivalently, the model can be viewed as assuming that the conditional label distribution satisfies $P(Y = 1 | X = {\\bf x}) \\ge (1 - \\eta)$ if ${\\bf w}^{\\top} {\\bf x} \\ge 0$ and $P(Y = 1 | X = {\\bf x}) \\le \\eta$ if ${\\bf w}^{\\top} {\\bf x} < 0$. \n \n*Single index model (SIM): The assumption here is of a similar form as that for GLMs, namely that $E[Y | X = {\\bf x}] = \\theta({\\bf w}^{\\top} {\\bf x})$ for some weight vector ${\\bf w}$ and transfer function $\\theta: R \\rightarrow [0, 1]$; however unlike GLMs, where $\\theta$ is assumed to be known, in SIMs, both the weight vector ${\\bf w}$ and the transfer function $\\theta$ are unknown (it is often assumed that $\\theta$ satisfies some condition such as a Lipschitz property)."}, {"review_id": "nRYmM3ueO7", "reviewer": "Reviewer_kMJq", "summary": "This paper introduces \nRealizable-Statistic Models (RSMs), a PAC learning framework for complex problems with stochastic labels that bridges the gap between the realizable and agnostic settings. The core idea is to assume that a specific vector-valued statistic of the conditional label distribution belongs to a known function class, rather than the labels themselves. The authors present a general theorem showing that minimizing a convex \"strongly proper composite surrogate loss\" yields computationally efficient learning algorithms with finite sample complexity bounds for these RSMs. This general result is then used to provide PAC learning guarantees with stochastic labels for a variety of problems, including multiclass classification, multi-label prediction, and subset ranking.", "questions": "1. For binary classification, it is noted that the sample complexity for squared estimation error is $\\tilde{O}(p/\\epsilon^2)$, which is worse than $\\tilde{O}(1/\\epsilon^2)$ for the specialized GLM-tron algorithm. Could you elaborate on the specific aspects of your general analysis that lead to this looser bound? Do you see a path to tightening these bounds while preserving the framework's generality?\n2. The conclusion states that it is an open question whether the sample and computational complexities can be improved. Beyond developing alternative algorithms, do you believe alternative proof techniques applied to the same surrogate risk minimization approach could yield tighter bounds?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strength:\n\n1. The paper introduces Realizable-Statistic Models (RSMs), a novel framework that generalizes several existing intermediate PAC learning models, such as random classification noise (RCN), Massart noise, and generalized linear models (GLMs). The framework is broad enough to cover a wide range of learning problems, including those not extensively studied in this context.\n2. The paper demonstrates the framework's utility by applying its main theoretical result to four distinct and complex learning problems: binary classification, multiclass classification, multi-label prediction, and subset ranking.\n3. All the theoretical results presented are distribution-independent with respect to the domain/instance space, which is a strong and desirable property in PAC learning.\n\nWeakness:\n1. The paper acknowledges that for some problems, the derived sample complexity bounds are worse than those of existing specialized algorithms. For instance, in the case of binary classification with sigmoid-of-linear models, the sample complexity for squared estimation error is worse than that of the GLM-tron algorithm. The authors also state that it is an open question whether the complexity bounds can be improved.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. Please find below our responses to your questions.  \n \n**Q1:**  \n \nFor binary classification, it is noted that the sample complexity for squared estimation error is $\\tilde{O}(p/\\epsilon^2)$, which is worse than $\\tilde{O}(1/\\epsilon^2)$ for the specialized GLM-tron algorithm. Could you elaborate on the specific aspects of your general analysis that lead to this looser bound? Do you see a path to tightening these bounds while preserving the framework's generality?\n \n**Response:**  \n \nOur sample complexity result is based on a uniform convergence analysis where the complexity of the function class is measured via $d_1$ covering numbers (we chose $d_1$ as the loss functions we study are Lipschitz w.r.t. the $L^1$ metric, allowing us to upper bound covering numbers of the loss function class $\\psi_F$ in terms of those of the component real-valued function classes $F^j$ in Lemma 1); we have upper bounded the $d_1$ covering numbers using the pseudo-dimension, which contributes the $p$ term. The sample complexity result for the GLM-tron algorithm in [21] (Kakade et al., 2011) is somewhat different: it first makes use of an online learning style analysis to upper bound the empirical (squared) error/regret, and then makes use of a uniform convergence argument to show that this also yields an upper bound on the expected (squared) error/regret. The uniform convergence analysis there is based on Rademacher complexities; in particular, the Rademacher complexity term involved in the analysis is upper bounded using an entropy integral involving $\\infty$-norm covering numbers, which in turn are upper bounded by dimension-independent (independent of $p$) covering number bounds. This leads to the $\\tilde{O}(1/\\epsilon^2)$ sample complexity bound in [21]. If we were to use the same dimension-independent covering number bound directly in our analysis (since the $d_1$ covering numbers we use can be upper bounded by $\\infty$-norm covering numbers), we would end up with a $\\tilde{O}(1/\\epsilon^4)$ sample complexity bound in our setting instead of our current $\\tilde{O}(p/\\epsilon^2)$ sample complexity bound. In the binary case, we could potentially replace our current uniform convergence analysis with the one based on Rademacher complexities as used in [21], which it turns out would also give a $\\tilde{O}(1/\\epsilon^2)$ sample complexity bound for our setting (we will make a note on this in the final version of the paper if accepted). However, it is not immediately clear how to extend the Rademacher complexity based analysis to multiclass or more general multivariate settings; it is possible that such extensions could be developed (and this could indeed be an interesting direction to explore in the future), but this is beyond the scope of the current paper.\n\n**Q2:**  \n\nThe conclusion states that it is an open question whether the sample and computational complexities can be improved. Beyond developing alternative algorithms, do you believe alternative proof techniques applied to the same surrogate risk minimization approach could yield tighter bounds?\n\n**Response:**  \n \nIt is certainly possible that alternative proof techniques could yield tighter bounds for the same surrogate risk minimization approach in special cases (for example, please see the discussion in the response to Q1 above for the case of binary classification with GLMs/sigmoid-of-linear class probabilities). We are currently not aware of alternative proof techniques that can yield tighter bounds for the general framework we study. However, we do not claim that our bounds are optimal (indeed, optimality is not yet established even for various previously studied special cases); it is plausible that, even in the general case, there could possibly be alternative proof techniques that may yield improvements in the future."}, {"review_id": "cpQrUSOph9", "reviewer": "Reviewer_FJKY", "summary": "The paper proposes and studies a PAC learning model called the Realizable Statistical Model (RSM), which lies between the realizable and fully agnostic settings. In this model, labels are randomly generated conditional on the covariates, but a statistic of the conditional label distribution is constrained to lie within a specified family. This definition is quite general: the standard realizable and agnostic settings, as well as generalized linear models (which lie in between), can all be expressed as special cases of RSM.\n\nThe proposed learning approach involves estimating the target statistic via a convex surrogate loss. Theorem 1 shows that a bound on surrogate regret can be translated into a bound on the excess risk for learning of the RSM. The main learning algorithm is empirical surrogate risk minimization, and Theorem 2 provides PAC learning guarantees for RSM using this approach. To show this result, the authors introduce a new lemma that bounds the $d_1$ covering number of the loss function class. \n\nThe second part of the paper focuses on applications, including:\n- Binary classification with sigmoid-transformed linear class probabilities,\n- Multiclass classification with softmax of a multilinear function over the input,\n- Multilabel prediction using sigmoid of multilinear marginals,\n- Subset ranking.", "questions": "In the binary classification setting, what is the intuition behind the sample complexity being independent of $p$ in [21]?\nIs the optimal sample complexity for this problem known?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n- The paper makes important advances in PAC learning. Settings that fall in between agnostic and realizable setting have been extensively studied in the last decades. \n- The paper provides applications of the general result and includes comparison with prior work for the case of binary classification\n\nWeaknesses:\n\n- The paper is dense with technical and long statements and no room for proofs (or proof overviews) in the main body.", "was_revised": true, "final_justification": "The authors provided satisfactory answers to my questions. My view of the paper remains positive.", "rebuttal": "Thank you for your comments. Please find below our responses to your questions.\n\n**Q1:**  \n\n(a) In the binary classification setting, what is the intuition behind the sample complexity being independent of $p$ in [21]? \n\n(b) Is the optimal sample complexity for this problem known?\n\n**Response:**\n\n(a) The sample complexity result for the GLM-tron algorithm in [21] (Kakade et al., 2011) first makes use of an online learning style analysis to upper bound the empirical (squared) error/regret, and then makes use of a uniform convergence argument to show that this also yields an upper bound on the expected (squared) error/regret. The uniform convergence analysis is based on Rademacher complexities; in particular, the Rademacher complexity term involved in the analysis is upper bounded using an entropy integral involving $\\infty$-norm covering numbers, which in turn are upper bounded by dimension-independent (independent of $p$) covering number bounds. This leads to the $\\tilde{O}(1/\\epsilon^2)$ sample complexity bound in [21]. If we were to use the same dimension-independent covering number bound directly in our analysis (since the $d_1$ covering numbers we use can be upper bounded by $\\infty$-norm covering numbers), we would end up with a $\\tilde{O}(1/\\epsilon^4)$ sample complexity bound in our setting instead of our current $\\tilde{O}(p/\\epsilon^2)$ sample complexity bound. In the binary case, we could potentially replace our current uniform convergence analysis with the one based on Rademacher complexities as used in [21], which it turns out would also give a $\\tilde{O}(1/\\epsilon^2)$ sample complexity bound for our setting (we will make a note on this in the final version of the paper if accepted). However, it is not immediately clear how to extend the Rademacher complexity based analysis to multiclass or more general multivariate settings; it is possible that such extensions could be developed (and this could indeed be an interesting direction to explore in the future), but this is beyond the scope of the current paper.\n\n(b) Regarding optimality: We are not aware of lower bounds or optimality results for the sample complexity of learning GLMs."}, {"review_id": "bElkmsuAxQ", "reviewer": "Reviewer_GkNt", "summary": "This paper proposes and studies a robust learning setting called realizable-statistical models. Roughly speaking, the realizable statistical model assumes that the Bayes optimal hypothesis of a distribution of labeled examples can be uniquely recovered via some vector-based statistics. If the loss of the problem can be characterized by the accuracy of the above vector-based statistics, and there is some convex surrogate function that can be used to do the statistics, then one could run a convex optimization algorithms over the sample to solve the learning problem and thus yield a sample and computationally efficient algorithm.  Within this framework, the paper considers several class of classification problems that satisfies a ``sigmoid-type\" condition such as binary classification, multiclass classification and ranking and shows that by considering minimizing convex surrogate loss one can efficiently solve these classification problems. Since previous works mostly consider binary classification or real-valued regression problems, the results of the paper could be seen as a generalization of the previous problems.", "questions": "My main concern is about the significance of the result, as I think assuming a convex surrogate function can solve the problem is a very strong assumption. In fact, I feel that in the distributional free setting, the model considered by the paper cannot be seen as a natural generalization of learning under RCN/Massart noise.\n\nIf my understanding is correct, in Table 1, papers such as [1] do not learn an LTF with RCN by optimizing a single surrogate function, due to the small-margin issue. Furthermore, for learning an LTF with Massart noise, [2] shows that no single convex surrogate function can be used to even weakly learn an LTF, even with a large margin. Thus, the algorithmic framework considered by this paper cannot be used to solve these problems, and I think these works are not comparable to the model proposed in this paper. So, I think Table 1 cannot reflect the generality of the framework proposed by this work.\n\nFurthermore, the assumption that the stochastic label is generated by the \"sigmoid-type\" distribution looks very strong to me. In a very recent paper [3], multi-class linear classification is shown to be computationally hard under very natural RCN assumptions, which means we cannot hope to find a convex surrogate for the multiclass setting, and the \"softmax-of-multilinear\" assumption is thus a very strong assumption and cannot compete with usual noise assumptions such as RCN.\n\nI would like the author to comment on this concern, depending on which I might adjust my score.\n\n[1]Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1/2):35–52, 1998.\n\n[2]Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-independent PAC learning of halfspaces with Massart noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, pages 4751- 4762, 2019.\n\n[3] I. Diakonikolas, M. Ma, L. Ren, and C. Tzamos. Statistical query hardness of multiclass linear classification with random classification noise. CoRR, abs/2502.11413, 2025", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: \nThe framework proposed by this paper is general and can be used for analyzing various types of learning problems such as multiclass classification, subset ranking, which cannot solved by most prior works that focus on solving a single index model. Furthermore, this paper is sound and the proofs of most results can be found in the appendix.\n\nWeakness: \n\nMy first concern about this paper is its significance. In fact, for many learning problems with label noise, the core difficulty is that one cannot find a single convex surrogate that can be used to solve the problem directly, even if statistically the ground-truth hypothesis can be uniquely recovered from the label. This often happens when no assumption is made over the marginal distributions. It seems to me that unless a very strong assumption such as the ``simoid-type\" assumption is made, it could be very hard to find a single convex surrogate that fits the framework to solve the problem.(See my questions below for details.)\n\nMy second concern is about the writing style of the main body. The notation system used by the paper is a bit complicated, and sometimes I had to go over the paper several times to understand the meaning of each notation. Furthermore, after the introduction, there are very few paragraph breaks, and many long equations are in lines, which makes going through the paper more difficult. The writing style should be optimized to make the paper more readable.", "was_revised": true, "final_justification": "After reading the rebuttal, I would like to raise my score. However, I still feel that the assumptions that make the main results work are strong. Given this reason, I think the work is around borderline towards acceptance.", "rebuttal": "Thank you for your comments. Please find below our responses to your questions.  \n\n**Q1:**  \n\n(a) My main concern is about the significance of the result, as I think assuming a convex surrogate function can solve the problem is a very strong assumption. In fact, I feel that in the distributional free setting, the model considered by the paper cannot be seen as a natural generalization of learning under RCN/Massart noise.\n\n(b) If my understanding is correct, in Table 1, papers such as [1] do not learn an LTF with RCN by optimizing a single surrogate function, due to the small-margin issue. Furthermore, for learning an LTF with Massart noise, [2] shows that no single convex surrogate function can be used to even weakly learn an LTF, even with a large margin. Thus, the algorithmic framework considered by this paper cannot be used to solve these problems, and I think these works are not comparable to the model proposed in this paper. So, I think Table 1 cannot reflect the generality of the framework proposed by this work.\n\n(c) Furthermore, the assumption that the stochastic label is generated by the \"sigmoid-type\" distribution looks very strong to me. In a very recent paper [3], multi-class linear classification is shown to be computationally hard under very natural RCN assumptions, which means we cannot hope to find a convex surrogate for the multiclass setting, and the \"softmax-of-multilinear\" assumption is thus a very strong assumption and cannot compete with usual noise assumptions such as RCN.\n\n(d) I would like the author to comment on this concern, depending on which I might adjust my score.\n\n[1] Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1/2):35–52, 1998.\n\n[2] Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-independent PAC learning of halfspaces with Massart noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, pages 4751- 4762, 2019.\n\n[3] I. Diakonikolas, M. Ma, L. Ren, and C. Tzamos. Statistical query hardness of multiclass linear classification with random classification noise. CoRR, abs/2502.11413, 2025\n\n**Response:**\n\n(a) First, please note that we are *not* assuming that a given learning problem can be solved using a convex surrogate loss function. What we are assuming is that the conditional label distribution $P(Y | X = x)$ satisfies a certain property - namely, that some vector valued statistic of this distribution belongs to some class of functions (this is the core assumption in our realizable-statistic models (RSMs)). Under this assumption, it turns out that in *many* (but not all) interesting cases, the resulting learning problem can indeed be solved by minimizing a convex surrogate loss, as described in Theorems 1 and 2 in the paper (the learning problem needs to satisfy the conditions of these theorems in order for this to hold).\n\nSecond, regarding RCN/Massart noise: Both these noise models can indeed be viewed as special cases of RSMs; however, the associated learning problems do not satisfy the conditions of Theorems 1 and 2, and therefore our algorithmic results do not apply to these models (indeed, we have not claimed so anywhere). To see that RCN/Massart noise models can be recovered as special cases of RSMs, note the following: \n\n*RCN: Consider the statistic $\\tau^{+1}$ defined in Section 3 (just below line 219) and the class of statistic functions $Q^{\\textrm{RCN-linear}} := \\\\{ q : {\\mathcal X} \\rightarrow [0,1] \\ | \\ \\exists {\\bf w} \\in R^p, \\eta \\in (0, 1/2) \\ \\textrm{s.t.} \\ q(x) = (1 - \\eta) \\cdot {\\bf 1}({\\bf w}^{\\top} {\\bf x} \\ge 0) + \\eta \\cdot {\\bf 1}({\\bf w}^{\\top} {\\bf x} < 0) \\\\}$. Then the RSM learning problem $( L^{0-1}, H_{\\textrm{linear}}, {{\\mathcal D}}_{( \\tau^{+1}, Q^{\\textrm{RCN-linear}} )\\textrm{-RSM}} )$ captures exactly the problem of learning linear threshold functions with RCN. (However, as noted above, this learning problem does not satisfy the conditions of Theorems 1 and 2, and therefore our algorithmic results do not apply to this problem.) \n\n*Massart noise: Consider again the statistic $\\tau^{+1}$ defined in Section 3 (just below line 219) and the class of statistic functions $Q^{\\textrm{Massart-linear}} := \\\\{ q : {\\mathcal X} \\rightarrow [0,1] \\ | \\ \\exists {\\bf w} \\in R^p, \\eta \\in (0, 1/2) \\ \\textrm{s.t.} \\ q(x) \\ge (1 - \\eta) \\ \\textrm{if} \\ {\\bf w}^{\\top} {\\bf x} \\ge 0 \\ \\textrm{and} \\ q(x) \\le \\eta \\ \\textrm{if} \\ {\\bf w}^{\\top} {\\bf x} < 0 \\\\}$. Then the RSM learning problem $( L^{0-1}, H_{\\textrm{linear}}, {{\\mathcal D}}_{( \\tau^{+1}, Q^{\\textrm{Massart-linear}} )\\textrm{-RSM}} )$ captures exactly the problem of learning linear threshold functions with Massart noise. (Again, as noted above, this learning problem does not satisfy the conditions of Theorems 1 and 2, and therefore our algorithmic results do not apply to this problem.)\n\nThirdly, regarding significance: As the other reviewers have also noted, this paper makes important advances in PAC learning. In particular, it introduces a novel framework that generalizes previously studied intermediate PAC learning models between the realizable and agnostic settings, and demonstrates concrete applications to a broad range of complex learning problems, all in a distribution-independent setting with respect to the domain/instance space. \n \n(b) As discussed in our response to part (a) above, both RCN and Massart noise models are indeed captured as special cases of RSMs; however, the resulting learning problems do not satisfy Theorems 1 and 2 and therefore our algorithmic results are not applicable to these problems (indeed, we have not claimed so anywhere). The purpose of Table 1 is simply to put our results in perspective in relation to existing results for previously studied noise models. (We would also like to point out that refs. [1] and [2] listed by the reviewer above are already cited in our paper.)\n\n(c) Thanks for the pointer to ref. [3] above; we will be happy to include a note on this and cite the paper. However, we found several of the reviewer's comments here to be quite confusing. In particular, we would like to point out two issues here: \n\n(i) The reviewer states multiple times that the assumption of the conditional label distribution having a \"sigmoid-of-linear/softmax-of-multilinear\" form is a \"strong\" assumption. We disagree with this statement. For example, in the binary case, this assumption simply means that the conditional probability $P(Y = 1 | X = {\\bf x})$ is composed of a linear function ${\\bf w}^{\\top} {\\bf x}$ passed through a sigmoid transfer function. As discussed in our response to part (a) above, under RCN, the same conditional probability is effectively assumed to be composed of a linear function ${\\bf w}^{\\top} {\\bf x}$ passed through a different transfer function, namely, a piece-wise constant transfer function of the form $\\theta(u) = (1 - \\eta) \\cdot {\\bf 1}(u \\ge 0) + \\eta \\cdot {\\bf 1}(u < 0)$. Moreover, sigmoid-of-linear distributions arise in many natural settings: for example, it is well-known that if the class-conditional distributions $p({\\bf x} | Y = 1)$ and $p({\\bf x} | Y = -1)$ come from an exponential family with different mean/location parameters and the same variance/spread parameters, then the conditional label distribution has a sigmoid-of-linear form. The softmax-of-multilinear form is a common generalization in the multiclass case. (It is also worth pointing out that while we have given specific instantiations of our results for sigmoid-of-linear/softmax-of-multilinear forms, our results are more broadly applicable.)\n\n(ii) The reviewer states that the softmax-of-multilinear assumption \"cannot compete with usual noise assumptions such as RCN\". It's not clear what this means. We are not competing with anybody. Different noise assumptions can be useful in different situations/applications, and we believe it is useful to have results for a variety of different noise models (equivalently, for a variety of different assumptions on the conditional label distribution). Regarding the reviewer's comments about multiclass linear classification under RCN being computationally hard, we don't see any contradiction here with our results; we find the two approaches to be complementary.\n\n(d) We hope that the responses above satisfactorily address the reviewer's comments, and that the reviewer would be willing to consider adjusting their score as indicated in their comments. We thank the reviewer again for reading our paper and taking the time to write their comments."}, {"review_id": "5A2XOJx95q", "reviewer": "Reviewer_rWz5", "summary": "This paper introduces realizable-statistic models with stochastic labels which include both the realizable and agnostic PAC learning as special cases. It is assumed that some statistic comes from some known function class. It shows that, for some common RSM learning problems, convex surrogate risk minimization with strongly proper composite surrogate loss yields computational efficiency and finite sample complexities.", "questions": "**Major concerns**\n- Line 314. Why is conditional independence not required according to Theorem 5? Can you provide a more explicit clarification?\n- Definition 3 states a lower bound for the surrogate risk difference between a label distribution and some prediction on the dual space. This assumption allows upper bounding L-regret via surrogate regret and effectively hides the dependence on $\\tau$. Can you clarify the motivation for this strongly proper composite loss? Given a statistic $\\tau$, is there a systematic way to design such a loss $\\psi$?\n- What are the lower bound and upper bound of the pseudo-dimensions? A discussion on this helps illustrating bounds in the best and worst cases.\n- Line 73. The dependence on $p$ in the derived bounds makes the results look inferior to existing ones. It comes from component-wise decomposition of the function class according to Lemma 1. If we can further make assumptions on the structure of the function class $\\mathcal{F}$, and / or the data-generating distribution, can we improve the dependence on $p$?\n- Why is the $d_1$ covering number adopted? What are the benefits? What if $l_p$ norm or general norms are adopted instead?\n- Can you compare your sample complexity bounds with those in [1-2] on structured prediction problems via convex surrogates?\n\n**Typos**\n- Definition 3, should be $\\mathcal{C}' \\subseteq \\mathbb{R}^{d'}$ rather than $\\mathcal{C}' \\in \\mathbb{R}^{d'}$ ?\n\n**References** \\\n[1] Nowak, Alex, Francis Bach, and Alessandro Rudi. \"Consistent structured prediction with max-min margin Markov networks.\" In International Conference on Machine Learning, pp. 7381-7391. PMLR, 2020. \\\n[2] Ciliberto, Carlo, Lorenzo Rosasco, and Alessandro Rudi. \"A general framework for consistent structured prediction with implicit loss embeddings.\" Journal of Machine Learning Research 21, no. 98 (2020): 1-67.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The studied setting is general and applicable to more complex intermediate PAC learning problems with stochastic labels. It generalizes GLMs and presents comparable but a more unified result.\n- Instantiation of the framework into several common learning problems is helpful for understanding the main result.\n\n**Weaknesses**\n- The paper lacks discussion on the insights about what the benefits are for designing practical algorithms in the future inspired by the derived theoretical results.\n- The motivations and justifications for some important assumptions are unclear. See my comments below for details.", "was_revised": true, "final_justification": "I lean toward acceptance of this paper because it generalizes previously studied intermediate PAC learning models and provides representative examples for commonly studied problems. Although RCN learning problems are not applicable under the proposed RSM framework, it is still a good noise assumption to consider as an alternative.", "rebuttal": "Thank you for your comments. Please find below our responses to your questions.  \n\n**Q1:**\n\nLine 314. Why is conditional independence not required according to Theorem 5? Can you provide a more explicit clarification?\n\n**Response:**\n\nTheorem 5 requires only that the marginals $P(Y_j = 1 | X = x)$ $(j \\in [s])$ of the conditional label distribution be of a specific form (namely, in this case, sigmoid-of-linear form); it does not require that $Y_j$ $(j \\in [s])$ be conditionally independent given $X = x$.\n\n**Q2:**\n\nDefinition 3 states a lower bound for the surrogate risk difference between a label distribution and some prediction on the dual space. This assumption allows upper bounding L-regret via surrogate regret and effectively hides the dependence on $\\tau$. Can you clarify the motivation for this strongly proper composite loss? Given a statistic $\\tau$, is there a systematic way to design such a loss $\\psi$?\n\n**Response:**\n\nThe definition of strongly proper composite surrogate losses for a statistic $\\tau$ in Definition 3 ensures the following desirable properties: (a) that the surrogate loss is minimized at (an invertible transformation of) the correct value of the statistic $\\tau$; (b) that the minimizer is unique; and moreover (c) that for any \"incorrect\" vector ${\\bf u} \\in {\\mathcal C}'$ for which $\\lambda^{-1} ({\\bf u})$ is different from the correct statistic value $\\tau({\\bf p})$, the surrogate risk at ${\\bf u}$ is bounded away from the optimal surrogate risk at $\\tau({\\bf p})$. Together these properties ensure that minimizing the surrogate loss recovers an accurate estimate of the desired statistic, as well as facilitating a quantitative regret transfer bound. Regarding the design of strongly proper composite surrogate losses: For linear statistics (those that can be expressed as an expectation; this includes all the statistics studied in our paper), one can design a strongly proper composite surrogate loss using Bregman divergences associated with any convex function (the logistic style surrogate losses used in our paper are a special case of this construction); a related study for example can be found in the reference below [AF12] (also cited as ref. [1] in our paper). For nonlinear statistics, the construction is typically done case by case; we are not aware of a general recipe.\n\n[AF12] Jacob D. Abernethy, Rafael M. Frongillo. A Characterization of Scoring Rules for Linear Properties. Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:27.1-27.13, 2012.\n\n**Q3:**\n\nWhat are the lower bound and upper bound of the pseudo-dimensions? A discussion on this helps illustrating bounds in the best and worst cases.\n\n**Response:**\n\nThe pseudo-dimension of the class of linear functions in $p$ dimensions is known to be exactly $p$. We used this as an upper bound since we consider a subset of *bounded* linear functions, but it is unlikely that it can be improved.\n\n**Q4:**\n\nLine 73. The dependence on $p$ in the derived bounds makes the results look inferior to existing ones. It comes from component-wise decomposition of the function class according to Lemma 1. If we can further make assumptions on the structure of the function class $\\mathcal{F}$, and / or the data-generating distribution, can we improve the dependence on $p$?\n\n**Response:**\n\nThe dependence on $p$ comes from the upper bound on the covering numbers in the uniform convergence result (in the proof of Lemma 2) in terms of the pseudo-dimension. Using a function class ${\\mathcal F}$ of smaller pseudo-dimension would certainly lead to a smaller sample complexity; however the function class ${\\mathcal F}$ needs to be matched to the class ${\\mathcal Q}$ being assumed for the statistic $\\tau$ of interest associated with the data-generating distribution (and so in that case the class ${\\mathcal Q}$ would also need to be of lower complexity). It is also possible that alternative uniform convergence/other analyses could lead to improved sample complexity bounds (indeed, based on a question from another reviewer, this seems likely for the binary classification case and we will add a note on it in the final version of the paper if accepted; for multiclass and more general multivariate settings, such improvements are not yet clear).\n\n**Q5:**\n\nWhy is the $d_1$ covering number adopted? What are the benefits? What if $l_p$ norm or general norms are adopted instead?\n\n**Response:**\n\nThe $d_1$ covering number is equivalent to the $l_1$ norm covering number (with some scaling). We use the $d_1$ covering number since the surrogate loss functions we study are Lipschitz w.r.t. the $L^1$ metric and this allows us to upper bound the $d_1$ covering numbers of the surrogate loss function class $\\psi_{\\mathcal F}$ in terms of the $d_1$ covering numbers of the component real-valued projection function classes ${\\mathcal F}^j$ (Lemma 1). (Moreover, the $d_1/l_1$ covering numbers are upper bounded by other covering numbers, including $d_2/l_2$ covering numbers and $l_\\infty$ norm covering numbers.)\n\n**Q6:**\n\nCan you compare your sample complexity bounds with those in [1-2] on structured prediction problems via convex surrogates?\n\n[1] Nowak-Vila, Alex, Francis Bach, and Alessandro Rudi. \"Consistent structured prediction with max-min margin Markov networks.\" In International Conference on Machine Learning, pp. 7381-7391. PMLR, 2020. \n\n[2] Ciliberto, Carlo, Lorenzo Rosasco, and Alessandro Rudi. \"A general framework for consistent structured prediction with implicit loss embeddings.\" Journal of Machine Learning Research 21, no. 98 (2020): 1-67.\n\n**Response:**\n\nThank you for the references. Below we discuss ref. [2] first and then ref. [1]; we will also include a summary of this discussion in the final version of the paper if accepted.\n\n*Comparison with ref. [2] (Ciliberto et al., 2020): This paper studies a setting where the target loss function $\\ell : {\\mathcal Y} \\times \\hat{\\mathcal Y} \\rightarrow R_+$ (in our notation) can be written as $\\ell(y, \\hat{y}) = \\phi_1(y)^{\\top} A \\phi_2(\\hat{y})$ for some embedding functions $\\phi_1 : {\\mathcal Y} \\rightarrow R^k$, $\\phi_2 : \\hat{\\mathcal Y} \\rightarrow R^k$ that embed the label space ${\\mathcal Y}$ and prediction space $\\hat{\\mathcal Y}$ into $R^k$ for some integer $k$ (more generally, the paper allows embedding into a Hilbert space $H$; we focus on Euclidean spaces $R^k$ here for simplicity), and for some matrix $A \\in R^{k \\times k}$. The paper effectively considers the \"conditional mean embedding\" statistic $q^{\\*}(x) = E[ \\phi_1(Y) | X = x ]$, and assumes that this statistic belongs to some class of functions (such as multilinear functions or a vector-valued RKHS); this statistic is then estimated by minimizing a quadratic surrogate loss to produce an estimate $\\hat{q}(x)$, and for a new instance $x$, a prediction is then made according to $h^{\\*}(x) \\in \\arg\\min_{\\hat{y} \\in \\hat{\\mathcal Y}} (\\hat{q}(x))^{\\top} A \\phi_2(\\hat{y})$ (the paper also studies other estimation procedures and settings where ${\\mathcal Y}$ and $\\hat{\\mathcal Y}$ may be infinite; we focus here on the above setting as it is most related to ours). This setting can be viewed as a special case of our RSM framework; indeed the quadratic surrogate used in the paper is also a strongly proper composite surrogate for the above statistic. The target loss based sample complexity bounds in the paper are of the form $\\tilde{O}(\\alpha/\\epsilon^4)$, where $\\alpha$ captures problem-dependent parameters (comparable to our bounds).\n\n*Comparison with ref. [1] (Nowak-Vila et al., 2020): This paper considers a special case of the setting described for ref. [2] above, where $\\hat{\\mathcal Y} = {\\mathcal Y}$ and the loss $\\ell$ is symmetric. For this special case, the paper develops a hinge/support vector type convex surrogate loss called the \"max-min\" surrogate loss, whose minimization does not aim to estimate the statistic $q^{\\*}(x)$ above (it is not a strongly proper composite surrogate loss), but rather aims to find a minimizer of the target loss $\\ell$ directly (just as the hinge loss for binary classification does not estimate class probabilities but aims to find a minimizer of the 0-1 loss directly). For this surrogate loss, the paper establishes target loss based sample complexity bounds of the form $\\tilde{O}(\\alpha/\\epsilon^2)$, where again $\\alpha$ captures problem-dependent parameters. Similar to the case of binary classification with hinge loss, for problems covered by this setting, the bound here is better than those that can be obtained with strongly proper composite surrogate losses as done in ref. [2] above and in our paper.\n\n**Q7:**\n\nDefinition 3, should be $\\mathcal{C}' \\subseteq \\mathbb{R}^{d'}$ rather than $\\mathcal{C}' \\in \\mathbb{R}^{d'}$ ?\n\n**Response:**\n\nYes, thank you for catching this typo! We will fix it."}]

Author rebuttal:

Meta-review: The paper presents a novel PAC learning framework called the Realizable Statistical Model, which exists between the realizable and fully agnostic settings. The authors introduce an empirical surrogate risk minimization algorithm suitable for this general setting, along with various applications, ranging from binary classification to subset ranking. This paper has received five reviews, with scores varying from weak acceptance to clear acceptance. Overall, all reviewers acknowledge the originality of this learning framework, and most agree on the significance of the learnability results. In summary, this is a valuable contribution to the field of computational learning theory, and I recommend its acceptance.

One of the main weaknesses cited by the reviewers pertains to the lack of clarity regarding certain conditions and results, such as the assumptions about labels and conditional label distributions. However, the authors have made commendable efforts to clarify these points. Therefore, I suggest that they incorporate these improvements in a revised version of the paper.
Decision: Accept (poster)