Distribution-Specific Agnostic Conditional Classification With Halfspaces
Authors: Jizhou Huang
Brendan Juba
Venue: ICLR 2025 Poster (2025)
Keywords: Agnostic linear classification
PAC-learning
Intractability
Primary area: learning theory

Abstract: We study "selective" or "conditional" classification problems under an agnostic setting. Classification tasks commonly focus on modeling the relationship between features and categories that captures the vast majority of data. In contrast to common machine learning frameworks, conditional classification intends to model such relationships only on a subset of the data defined by some selection rule. Most work on conditional classification either solves the problem in a realizable setting or does not guarantee the error is bounded compared to an optimal solution. In this work, we consider selective/conditional classification by sparse linear classifiers for subsets defined by halfspaces, and give both positive as well as negative results for Gaussian feature distributions. On the positive side, we present the first PAC-learning algorithm for homogeneous halfspace selectors with error guarantee $\tilde{O}(\sqrt{\mathrm{opt}})$, where $\mathrm{opt}$ is the smallest conditional classification error over the given class of classifiers and homogeneous halfspaces. On the negative side, we find that, under cryptographic assumptions, approximating the conditional classification loss within a small additive error is computationally hard even under Gaussian distribution. We prove that approximating conditional classification is at least as hard as approximating agnostic classification in both additive and multiplicative form.

Published as a conference paper at ICLR 2025
DISTRIBUTION-SPECHHC AGNOSTIC CONDITIONAL CLASSIFICATION WITH HALFSPACES
Jizhou Huang, Brendan Juba Washington University in St. Louis
(huang. j jizhou,
edd
ABSTRACT
We study "selective" "conditional" classification problems under an agnostic setting. Classification tasks commonly focus on modeling the relationship between features and categories that captures the vast majority of data, In contrast common machine learning frameworks, conditional classification intends to model such relationships only on subset of the data defined by some selection rule. Most works on conditional classification either solve the problem in realizable setting or do not provide eπrоr guarantees compared to an optimal solution. In this work, consider conditional classification by sparse linear classifiers for subsets defined by halfspaces. We give both positive and negative results for Gaussian feature distributions. On the positive side, present the first PAC-learning algorithm for homogeneous halfspace selectors with error guarantee (oppp), where opt is the optimal conditional (-1 loss over the given class of classifiers and homogeneous halfspaces. On the negative side, we find that, under cryptographic assumptions, approximating the conditional loss within small additive error is computationally hard even under Gaussian distribution. We prove that approximating conditional classification is at least as hard as approximating agnostic classification in both additive and multiplicative form.
INTRODUCTION
Classification the task of modeling the relationship between some features and membership in some category. Classification tasks are common across various fields, such as spam detection (classifying emails as "spam" or "not spam""), and image recognition (identifying objects like "cat" or "dog"). Standard classification approaches seek to model the whole data distribution. By contrast, we consider the problems where a better classifier exists on a subset the data. In particular, we will consider cases in which classifiers are sparse linear functions (or more generally, any small set of functions), and subsets are described by selector functions, given here by homogeneous halfspaces.
We study the distribution -pppbbiitioosseiifiiei PAC-learnability (Kearns et al., 1994) of the mussifier-selectte class in the presence of adversarial label noise. In the literature, this problem is known as "conditional" classification, but also part of family that is generally known "selective" classification.
1.1 BACKGROUND AND MOTIVATION
The first "selective classification" problem was introduced decades ago (Chow, 1957; 1970). The focus was on finding Bayes classifiers for the case where the data distribution is fully known. The appeal of effective selective classification is clear in applications where partial domain coverage is acceptable, or in scenarios where achieving extremely low risk is essential but unattainable with standard classification methods. Classification tasks in medical diagnosis and bioinformatics often fall into this category (Khan et al., 2001; Hanczar & Dougherty, 2008).
El-Yanic Yaniv et al. (2010) gave thorough theoretical analysis for selective classification based "risk-coverage" model. They proved that, for the optimal classifier and selector, there exists a natural trade-off between the performance of the classifier on the selected subset and the size of the subset.

---

Published as a conference paper at ICLR 2025
Prior work has either considered the "realizable" case (El-Yaniv & Wiener, 2012; Gangrade et al., 2021), where there exists a classifier-selectt pair that does not make any errors, or endowed the learner with rejection mechanism using heuristic rules confidence scores (Geifman & El- Yaniv, 2017; Pugnana & Ruggieri, 2023). For the "agnostic" case, where no perfect classifier-selector pair exists, few works had been done on model-based selective learning (Wiener & El-Yaniv, 201 2015; Gelbhart & El- Ya-ia, 2019). More importanty, these works do not guarantee both computational efficiency together with good performance with respect to the optimal classifier and selector.
We consider a more general formulation of agnostic selective classification under the PAC-learning semantics in Definition 1.1. In particular, we do not make any assumptions on the labels while the performance of the learned classifier and selector are guaranteed to be close to the optimal solution.
Definition 1.1 (Agnostic Conditional Classification). Let 'D be any distribution on IR {0, 1), C. be a finite class of classifiers on @ {0,1}, 1}, and 9% { S Rd PIxWD= fx E S E [a,b], For any 0 S a S S 1, suppose min seo sec Pr(x.))<DY by + c(x) E S} S opt, a C-approximate algorithm (or an algorithm with approximation factor for some C 1, given sample access D. outputs an S' E 9% and E C such that Pr & c(x) x E S') < Copt with high probability.
The imposed "population" bounds the subsets S E -% critical. On the one hand, the lower bound, Pr(x E S} 2 can both prevent trivial optimal solutions such as S" - Ø and make the selected subsets statistically meaningful. On the other hand, if the selector chooses a majority of the data, the performance advantage of the optimal solution of selective classification could vanish compared with that of the regular classification model (EI-Yaniv et al., 2010; Hainline et al., 2019).
Consider a halfspacc h. i.e., a subset of Id such that the membership in h is defined by some linear threshold function. In this work, we wish solve the problem of agnostic conditional classification with halfspace selectors under standard normal distributions described as follows.
With Halfspaces). Let D be any distribution on IR x {0, 1} with standard normal x-marginal on R C be a finite class of classifiers on Id x {0, 1}, and HP/ be the class of halfspaces on Rd with population size in the range of (a, b] over Xx. For any 0 S a S b 5- L, suppose min Ho. rec Pr(x.g)=D + c(x) x
Problem 1.2 (Distribution-Specifi Agnostic Conditional Classification
h} I opt, how close to opt can a polynomial time algorithm achieve on Hyps with high probability?
An algorithm for Problem 1.2 may be leveraged to perform conditional classification for large or infinite classes C by using an algorithm for list learning of classifiers for some richer class (Charikar et al., 2017), taking C in Problem 1.2 to be the list of classifiers produced by the list learning algorithm:
Definition 1.3 (Robust list learning). Let D aD' + +(1 - a)D for an inlier distribution D'' and outlier distribution D each supported on R2d x {0, 1}, with a E (0, 1). A robust list learning algorithm for a class of Boolean classifiers C, given and parumeters e, 8 E (0, 1), and sample access to D such that for (x, b) in the support of D*, b = c² (x) for some c² E C, runs in time poly(d, a.' c. lol })) and with probability 1 - 8 returns list of l = poly(d, a log }) classifiers (h1....,he)) such that for some h2 in the list, Pro [cx(x) = c* (x)) 2
As we will review, it is known in particular that, for sparse linear classifiers (with = O(1) nonzero coefficients), list learning from sample of size m = O _e log d + log 4)) is possible in time and list size (mdd") (Juba, 2017; Mossel & Sudan, 2016).
1.2 CHALLENGES OF DISTRIBUTION-SPECIII CONDITIONAL CLASSIHICATION
Problem 1.2 is similar to agnostic linear classification, where we seek to minimize the classification eπror over the vast majority of data. In particular, it was clear that agnostic classification can be reduced to Iistributionn-rre) conditional learning (Juba, 2017). Agnostic linear classification has been extensively studied over decades, and it is known to be computationally hard in both distribution-fie (Kearns et al., 1994) and distributionnspeccine settings (Diakonikolas et al., 2023).
Despite the intractability of agnostic learning, numerous distribution-speciff approximation schemes have been developed with approximation factor of ( (1//vopt) or even constants (Frei et al., 2021; Diakonikolas et al., 2020c; 2022; 2024; Shen, 2021). Given the similarity between agnostic linear
2

---

Published as a conference paper at ICLR 2025
classification and Problem 1.2, and that it was the only formal barrier known, it is natural to ask if we can leverage the existing techniques for standard agnostic classification in conditional classification.
However, it is not clear how these could lead to meaningful error guarantee for conditional classification. Directly, Definition 1.1 (correspondingly, Problem 1.2) can be reduced to a "one-sided" classification problem, where seek to minimize the error rate of the classifier only the selected halfspace (one side). As the error rate could be extremely unbalanced across the selected side and its complement, a constant factor approximation scheme for the agnostic linear classification problem may not yield approximation guarantees for the one-sided agnostic classification problem.
An analogous difficulty arose in "fairness auditing" (Kearns al., 2018). In the problem of fairness auditing, instead of minimizing the classification error, we wish to verify some specific faireess criteria for subset of the data. Kearns al. (2018) showed that the auditing problem is equivalent to agnostic classification for any simple representation classes (including halfspaces) under distribution- free settings. Despite the similarity between these two problems, as well as the existence of constant factor approximation algorithms for agnostic linear classification under distributional assumptions, recent work by Hsu et al. (2024) showed there does not exist any nontrivial multiplicative factor approximation algorithm for auditing halfspace subgroup fairness even under Gaussian distributions. The connection in the distribution- free setting simply does not carry over to Gaussian data.
1.3 OUR CONTRIBUTION
Let opt be defined in Problem 1.2 for H being the class of homogeneous halfspaces. Our first algorithm to learn a pair of classifier
contribution is polynomial-timg and selector for Problem 1.2 with homogeneous halfspace selectors for finite C (cf. Theorem 3.1.. We also generalized our approach to work with any sparse linear classifiers (cf. Theorem 3.5). This is the first polynomial-tin titeemiillteeeeeeeee algorithm for agnostic conditional//sllctiee classification with provable approximation guarantee w.r.t. the optimal solution.
Remark 1. Even for homogeneous halfspace selectors, the imbalance of error rates between classes could still exist, as we will show in our hardness result that the difference between the error rates of different classes of the homogeneous halfspace always equals to the amount that the probability of either label deviates from 1/2: see Lemma 4.4 for details.
Remark Note that the extension of our approach on sparse classes leverages the power of an list learning algorithm for linear sparse classifiers (cf. Theorem A.1). It is an open question whether method can be extended to other families of classifiers. Polynomial-time algorithms for list-decodable (dense) linear regression (as opposed to classification) have been found (Karmalkar et al., 2019; Raghavendra & Yau, 2020). so as other list-decodable estimation tasks as mentioned earlier, but little known for learning classifiers at present. It is an interesting broader open question which families of classifiers are learnable in the list-decodable setting.
Our second contribution is negative result for Problem 1.2. We show that agnostic conditional classification in Definition 1.1 is at least as hard as agnostic linear classification under any distribution (cf. Proposition 4.5). With the distribution-speciff hardness result of agnostic linear classification (Diakonikolas et al., 2023), we prove that no polynomial-tmee algorithm can achieve an error guarantee of opt + (1/ log 12++ d) for any constant > 0 for Problem 1.2 (cf. Theorem 4.3). We show more generally that approximating the conditional classification objective is at least as hard as approximating the regular classification objective (cf. Proposition 4.5 & Claim 4.7).
Remark 3. We believe our upper bound Ô /opt) is sub-optimal. Obviously, it is consistent with the known negative results, even for general halfspaces. Meanwhile, was possible to reach (opt) eиror for agnostic learning of halfspaces w.r.t. Gaussian data (Diakonikolas et al., 2022). Also, in other, simpler dictddecod robust estimation tasks (Kothari al., 2018), it was possible to use kthh moments to obtain opt (((1/k) error, and for list-decodable linear regression it is similarly possible to approach optimal error by spending more on the running time (Bakshi & Kothari, 1021). Thus, there does not seem to be a hard barrier at some suboptimal error rate.
Organization. In Section 2, we give some necessary background. We will present our algorithmic results in Section 3. The distribution-specife hardness result for conditional classification with general halfspaces is in Section 4. In the last section, we will discuss the limitations of our results and few possible directions for extensions.
3

---

Published as a conference paper at ICLR 2025
1.4 RELATED WORKS
Selective Learning, For realizable setting, El-Yaniv & Wiener (2012) reduced active learning to selective learning and proved a exponential lower bound on label complexity for linear classification Gangrade et al. (2021) proposed a optimization-base to maximize the classifiers' coverage with a specified one-side prediction error rate. They proved that any representation class with finite VC-dimension can be used successfully in their models. For the agnostic cases, Wiener& & El-va (2011; 2015); Gelbhart & EI- Yaniv (2019) presented a selective learning approach to learn a classifier-selector pair that is at least as competitive as the ERM of the non-selective learning task. However, the computation of both the classifier and selector in these methods relies on an agnostic learning oracle, and the selector function is not guaranteed to minimize the conditional classification error down to any approximation factor. Geifman & El- Yaniv (2017) proposed a heuristic method to design selector functions for any given deep neural network with provable guarantees. Empirically, Pugnana & Ruggieri (2023) developed an -agoo--agnostic learning algorithm to learn a confidence-based based selective classifier that seeks to minimize the AUC-based loss within the selected region. Geifman & EI- Yaniv (2019) proposed the SelectiveNet architecture that simultaneously learns pair of classifier and selector in a single neural networks with given coverage.
selective learning framework that guarantees
Conditional Learning. The problem of conditional learning (including conditional classification) incorporates two sub-pro problems obtaining a finite list of predictors as well as learning predictor- selector pair out this finite list and some class of selector functions. For the former task, a series of positive results (Charikar et al., 2017; Kothari al., 2018; Calderon et al., 2020: Bakshi & Kothari, 2021) have been obtained under the "list-decodable" setting of Definition 1.3. For the latter task, Juba (2016) introduced the problem of learning abduction, where they propose to learn a subset of the data distribution where e.g., no errors occur. In their work, they showed that subsets defined by k-DNFs can be efficiently learned in realizable cases without any distributional assumptions. Subsequent improvements were obtained for the agnostic setting (Zhang et al., 2017; Juba et al., 2018).
Learning To Absaain. Cortes et al. (2016) considered different formulation of selective classifica- tion. Instead of optimizing the classification error conditioned the selected subgroup, they proposed to minimize the classification error jointly with the selector function while enforcing a cost for "abstaining". They designed few convex surrogate losses to upper bound the joint classification loss in the setting that abstaining has a cost. Later works (Mao et al., 2024c;a;b) proposed new families of surrogate losses to approximate the classification loss with abstaining and proved various upper bounds classification error of any classifier-selector pair in terms of different surrogate loss measures for two different selective learning strategies.
PRELIMINARIES
In general, use lowercase italic font characters to represent scalars, e.g. x R. lowercase bold italic font characters to represent vectors, e.g. x E IRd, and uppercase bold italic font characters to represent matrix, e.g. A Rmxd In particular, subscripts will be used to index the coordinates of any vector, e.g., 2y represents the ith coordinate of the vector æ. Similarly, we use normal font characters represent random variables, e.g. x E R, x E Fd and A mmmdd""
For x E Rdd, let ||x||p = -Eih /x/////p denote the nn-norm of x, and x = x/||x||a denote the normalized vector of x. We will use (x, u) to represent the inner product of x, u E Rd and x** to represent the outer product of x E R2d to the kcth degree. Additionally, we will use 0(u, w) to denote the angle between two vectors u, w Rd. For any subspace V C IRd let xy denote the projection of onto V. Further, will write - {u Rd (u, w) 0) as the orthogonal space of w E Rd and, therefore, _ = (I (I- w )xx as the projection of x E Rd onto w.
We use Dx to denote the marginal distribution of D on E Rd. PIANDÍZ E E} to denote the probability of an event E, (f) to denote the expectation of some statistic f(z), and therefore, [f(()), p (Ilf 1/P In particular, for an i.i.d. sample D D. we define the empirical probability and expectation PrzuD (z E E} 1/ID] EnED 1 E E} and If 1/ID1 ExE f(x). In particular, let (d,, 1) denotes the d-dimensional standard normal distribution. We may drop D from the subscript when it the context is clear, i.c., we may write Pr(z E E}. [z) for PrzD E F.). (z)).
4

---

Published as a conference paper at ICLR 2025
In this paper, we denote halfspaces subset R. T in the following way. For any t R. w R let 4 Rdd + R be an affine function such that (x, w) = (x, w) - t. Then, a halfspace in Rd (w))
with threshold t R and normal vector is defined hf(w) = (x E Rd (x, w) I 0}). When a halfspace is homogeneous, we will drop the threshold from the subscript, i.e., when = will write h(w)) instead of ho ho())).
fx R 4,(x, w) 2 0} (resp.
CONDITIONAL CLASSIFICATION WITH HOMOGENEOUS HALFSPACES
In this section, we present our algorithmic results for conditional classification with homogeneous halfspaces (selectors) Rd for sparse linear classifiers or, more generally any small set of binary classifiers under any distribution with standard normal x-marginals.
In the case that C is finite, we find homogeneous halfspacc the selector that minimizes its conditional classification loss, Pr(c(x) # x E ). for each classifier c C. Eventually, we choose the best classifier-selector pair the output. To extend to the case of any sparse linear classes, our strategy is to generate a finite using a list-learning algorithm, then run our conditional learning algorithm the obtained find classifier-eelector pair.
Notice that, for homogeneous halfspaces under Gaussian x-marginals, minimizing Prfc(x) * y f((w) equals to minimizing Pr(c(x) y E h(w) since every homogeneous halfipacce satisfies Prx-A/"(o,1 fx E h(w)} = 1/2. Hence, we will only consider minimizing Pr(c(x) of y nxx E h(w)) in this section. The core challenge for our strategy is finding such a halfspace for each C. We give the details in the following sections.
3.1 ALGORITHM OVERVIEW
Algorithm 1: Conditional Classification For Finite C
procedure CCFc(D,C,,,
+ In [C] //
N + (1n((16 [C] 20)ee/m lt
D [C] i..d. examples from D
(o) t any basis
for e E C do
Die) < Dx lf((x) # Fy}
W PSGD (D()) T,N, w()) U PSGD (D(e), T,N, (0)
(()) < argmin Pro fx E h(w) ne(x) $y}
end
return argmin, PIo fx E (( ne(x)
11
In Algorithm 1, for each binary classifier c E C, we map the labely from D to 1 [c((x) * y} to form a new distribution Díe), then pass D(e) to Algorithm 2 to obtain sequence of halfspaces, and only keep ()) with the smallest empirical conditional 0-1 loss for this classifier At last, it returns the classifier-selector pair that performs the best among all E C estimated on D.
Notably, the mapping step (line 7) for each distribution D(e), which is a key step to reduce the conditional classification problem to "one-sided" agnostic linear classification problem. While directly optimizing over the conditional classification loss Pr(x E h(w) * y is intractable in general, it turns out that approximately stationary point of simple convex surrogate approximation to the classification loss, Co(w), suffices to approximately capture optimal halfspace selector under Gaussian distributions. Formally, define Lp w) = E(xx))=Dy max(0, (x, w))] with respect to the distribution D.
C essentially just creates another adversarial
Algorithm 2 is inspired by Diakonikolas et al. (2020b) that the gradient step (line 5) uses the projected gradient 9mm yx.y). defined as 9m (x,y) = y X 1(x E h(w)). We will show in the next section that Algorithm 2 is guaranteed to converge an approximately stationary point, i.e., small |[E[y]]]e
5

---

Published as a conference paper at ICLR 2025
Algorithm 2: Projected SGD for (D(w)
procedure PSGD N, w(
8+ /I/Td for i 1 ,.... do
D(1) + N i..dd samples from D
( + wi- 3 E
(xy) (w (x,
w u /l01||10011
end
return (7)))
Note that the objective function considered in Diakonikolas et al. (2020b) is completely different from ours so that their convergence analysis does not obviously hold for our surrogate loss Lp (w). Also, our choice of 9w ( y) is similar to that of Shen (2021). Nonetheless, the problem they were solving is agnostic linear classification and they used a quite different gradient descent policy.
Algorithm& 3: Conditional Classification For Sparse Linear C
procedure CCsLc(D, e, 6, m) return CcF
m)
Algorithm 3 solves conditional learning of sparse linear classifiers. Specifically, SPARSELIST (cf. Algorithm 4) generates a list of sparse linear classifiers, at least one of which guaranteed to be close to minimizer of the conditional classification error with homogeneous halfspace selectors (cf. Theorem A.1). Run Algorithm on the obtained C gives the optimal classificr-seletta pair.
3.2 CONDITIONAL CLASSIFICATION FOR FINITE CLASSES
We introduce main guarantee at first, but postpone the proof to Appendix C due to the page limit. As a sketch of the proof, we will see Proposition 3.2 and Proposition 3.3 together indicate the optimality of Projected SGD, captured by Lemma 3.4. Combined with standard concentration analysis, this implies our main theorem.
Theorem 3.1 (Main Theorem). Let D be distribution on R x {0, 1) with standard normal marginal, and C be a class of binary classifiers on TR& x {0, 1}. If there exists a unit vector v E RRd and e. C such that, for some sufficiently small E 1fe), Pr(xs))D {x E Nc(x) # y) S 6, then, with at most (dd (e6) examples, Algorithm will return a wole), with probability at least - 8, such that (x(x))=D {x E h(w(()) ('d( x) Ö(Ve) and run in time O (C] /c9).
The most important component that enables our approach the following proposition. which states that, for any sub-optimal halfspace h(w). the projected negative gradient B[-9w] of the surrogate loss LD (ur) must have negliggie projection on the normal vector of the optimal halfspace h(v))
Proposition 3.2. Let D be a distribution on Rd x {0. 1} with standard normal x-marginal, and Iw (x, y) y xx 1 (x h(w)}. Suppose v, w E IRd are unit vectors such that (vv w) [0, x/2)
and Pr E h(v) ny = 1} S e, then, if ifPr(xyy) (x E h(w) ny 1} Z (eevine- we have (B(x,))= Iw (x, y)], ) Ievine-l for sufficiently small e.
We leave the formal proof to Appendix due to the page limit. The proof is based on the following observation (also see Figure 1): When homogeneous halfspace h(w) is substantially sub-optimal, the probability of labels being true within the domain that the optimal halfspace h(v) disagrees with it, i.e. h(w)) (h(v), must be large. However, the same probability cannot be too large in the optimal halfspace h(v) and, hence, h(v) n h(w). Then, the underlying distribution has a well-behane X-marginal, the l2 norm of the expectation of x within that domain should also be large.
In fact, the observation gives an insight of why L (www) suits for the one-sided classification problems. As are concerned about the one-sided loss, Pr(x E h(w) Ny 1}. there error assumptions

---

Published as a conference paper at ICLR 2025
e2 (2(w)
B
0 U. w)
e1
Figure 1: Blue area represents ((v) n h(w)), orange area represents l(w)) (1(v).
on (wr), which also the key difference between regular classification and conditional classification. Therefore, we want to ensure the projection of Elg (x.,) on Vw is zero (ww),, which, in turn, requires the objective loss to be zero on (ww). Since (ww) on h h"w),, we will only need discuss the properties of El (x, y)] on the domain where we have control.
Besides, an important implication of Proposition 3.2 is that, once 0(v, w)) E [0. π T/2) and l(w) is 9w (x. (x] yy] always "points" to v. Then, the update step (line 5) Algorithm will make (v, w) contractive, which will, in turn, guarantee that the assumption ((v. w) E [0, T/2) is satisfied in the next iteration. This property plays key role in proving Lemma 3.4.
sub-optimal, -
To effectively utilize Proposition 3.2, we also have to show that its assumption is satisfied. That is, at least one of the weight vectors, w('))... w(tT) produced by Algorithm 2 has small [[E|gn I (x, y)]ll, We show this can be achieved within bounded number of iterations as the proposition below.
Proposition 3.3. Let D be distribution on Rd x {0, 1} with standard normal x-marginal, Go (x, y) y Xw fxx E h(w)), and LD(w) = B(x.))</ly max(0, (x, w))]. With 3 vI/Td, after T 2 12d (((/ iterations, the output w(()) ...., (T) in Algorithm will satisfy min;=1.... (l ( xxy)]]l I with probability at least 1- ô. ô.
We defer the proof to Appendix B. Our technique resembles the work of Diakonikolas et (2020b), which showed that, if the objective function is bounded and has Lipschitz continuous gradient, then the norm of its gradient converges in boundedly many iterations of (Projected) SGID.
(1(
8 EE-
u (++1)
w (++1
A
(a) Weight update step (line 5) and projection step (line 6) in algorithm 2.
(b) Orange plane is the decision boundary h(w'), ), while blue plane is that of f1ww). VwCo (w) and V vwLp(w' only differs in the two pink spherical sectors, which is dominated by A0.
Figure 2: Boundedness of ()(w(() and almost Lipschitz continuity of VD.))
However, the magnitude of (D(w) is dominated by |||||2 which could grow unbounded after many iterations, and its gradient VwCp(u (w) has a "jumping" point at zero, which is not Lipschitz continuous in general. So, the key to proving Proposition 3.3 is to overcome these issues.
Observe that the gradient update (line 5) of Algorithm 2 will always produce || || 2 (1
111,.
while the projection step (line 6) of Algorithm will always make Lo (w) bounded, cf. Figure 2a.
7

---

Published as a conference paper at ICLR 2025
On the other hand, it turns out that (w is almost Lipschitz continuous under nice distributions such as a standard normal. Intuitively, if we perturb w a little bit to change it to w', it will only rotate the halfspace h(w) by a very small angle, i.. A = 8( w. w') is small. And, it suffices to consider the difference between VwLD(w) and V WD on a 3-dimensional subspace as shown in figure 2b. Now, if the density of distribution D is not concentrated too much in any small spherical sectors in the subspace, it implies that the change of W (w) is dominated by Ao (see Figure 2b), which is insignificant. This observation indicates that V WDCD(M (w) is Lipschitz continuous under anti-concentrated distributions unless ||2/|2 is extremely small.
Given Proposition 3.2 and Proposition 3.3, we show that in the list of parameters returned by Algorithm 2, at least one of them is approximately optimal:
Lemma 3.4. Let DD be a distribution on Rd x {0.1} with standard normal x-marginal, and Iw (x. y) y X 1
h(w)}. Suppose v E Rd unit vectors such that (I e h(v) ny 1} S c, if 2 12d (n((2/)/cc+ N 2 In(4T/8)/CC en for some constant C > and ((v, w (0) E [0. π 7/2), holds that at least one w E W returned by Algorithm 2 satisfies Pr(xx))/(X E h(w) ny = 1} s (ev//ee- w.p. 1- 5 for some sufficiently small e E 1/e].
We defer the formal proof to Appendix C, but sketch the idea here. Observe that combining the negation of Proposition 3.2 and Proposition 3.3 already yields Lemma 3.4. So, all we need to do is make sure that the assumption 0(0, w) E [0, x/2) in Proposition 3.2 is satisfied.
w(T returned by Algorithm 2, every w(() must be significantly sub-optimal until we see a w such that Pr(x E h(w) ny = 11 S 3 ((ev/ne-1)1/2 If such a sub-optimal halfspace h (ww(1) also satisfies 0(v, wn(() E [0, 122). its negative projected gradient E [ must has positive projection on u by Proposition 3.2. Using such a [w to update w in Algorithm 2 will always produce 0(0, w((+ < 0(0, w)) Thus, by an induc-
Notice that, in the sequence of parameters w())
tive argument, we can show that the first (t()) such that [[[[] Ill < gevine-T must satisfy
0(1, w (() E [0, which enables the application of Proposition 3.2.
3.3 GENERALIZATION TO SPARSE LINEAR CLASSEIFIERS
Although Algorithm only applies to finite C, we can generalize our approach to work with infinite classes of classifiers whenever they are list-learnable (Definition 1.3); for example, sparse linear classifiers are list-learnalee in polynomial time. We present the corresponding performance guarantee for Algorithm 3 as follows while deferring the formal proof to Appendix D due the page limit.
Theorem 3.5. Let D be distribution Id x {0, 1} with standard normal x-marginal, and C be a class of sparse linear classifiers on TRd x {0.1} with sparsity 8 = ((1). If there exists a unit vector E Rdd and c E C such that, for some sufficiently small e E 1/e). Pr(x))~(( M(V) n c(x) + y} S then, with at most poly(d, 1/c, 1/8) examples, Algorithm 3 will return aglc), with probability least 5, such that Pr(x,))>D E h(wll()) (x((x) fy] Ō(v?) and run in time poly(d, 1d,,//,1/8)
CONDITIONAL CLASSIFICATION WITH GENERAL HALFSPACES IS HARD
In this section, we show that it is computationally hard obtain a small additive error for conditional classification with general halfspaces for any finite class of classifiers C, even under distributions with standard normal x-arginaass. Specifically, we show that, for each classifier E C, approximating the optimal conditional classification loss over the class of general halfspaces on Rd with an additive error at least as hard as achieving the same additive error for agnostic linear classification, which is known to be computationally hard (Diakonikolas et al., 2023). Further, we show that any (1 + a)- approximation algorithm for conditional classification implics an (1 + apprroxxxiitoo algorithm for standard classification, down to polynomially small losses. (The converse is not known to hold.)
The hardness of distribution-speee
conditional classification is based on the sub-exponential hardness of "continuous Learning With Errors" (cLWE), which is variant of the "Learning With Errors" (LWE) assumption. Informally speaking, in the problem of LWE, we are given labelled examples from two hypothesis cases. In one case, the labels are biased by some secret vector, while,
8

---

Published as a conference paper at ICLR 2025
in another case, the labels are generated uniformly at random. We wish to distinguish between these cases. We formally define the problem of LWE (Regev, 2009), following Diakonikolas et al. (2023): Definition 4.1 (Learning With Errors). For m.d E N. E R+, let Drampie: Dsecret: Dnoise be distributions on Rd, Rd R respectively. In the LWE(m, D Daample Deecret. Dnoise. modg) problem, with independent samples (o))))).))....... (x(m)) y((m)), we want to distinguish between the following two cases:
Alternative hypothesis: each y(0)) is generated as -000=0odd ((x 8) + z), where
x8) D Dsample: D Decorets2 D Droise-
Null hypothesis: each y(0) is sampled uniformly at random the support of its marginal distribution in the alternative hypothesis, independent of x(8) ~ Dsample.
An algorithm is said to be able to solve the LWE problem with A advantage if the probability that the algorithm outputs "alternative hypothesis" is A larger than the probability that it outputs "null hypothesis" when the given data is sampled from the alternative hypothesis distribution.
Let g : {x E Rd ||x||| = 11. R == [0. q), and mod, Rd - R to be the function that applies mod, operation on each coordinate of x. Essentially, the hardness of cLWE is based on the sub-exponential hardness of LWE (see Appendix E). We formally state the assumption of sub- exponential hardness of cLWE as follows.
Assumption 4.2 ((Gupte et al., 2022; Diakonikolas et al., 2023) Sub-exponential cLWE Assumption). For any d N, any constants x& N, a E (0, 8 E R+ and any log S S Cd where C' is a sufficiently small universal constant, the problem LWE(dO(k)) ',N 1). 1). .N'(0, d²), mody) over &d with a 2 k= and T = =1/C' //C'Vllog' d, where C' > 0 is a sufficiently large universal constant, cannot be solved in time (kk") with d dOO(k)) advantage.
For simplicity, we define y fc((x) * y'' for (x,y') D' and construct the distribution (x.y) ~ D. Notice that, in agnostic settings, since D' is worst case, D is also worst case. Therefore, this replacement does not affect the difficulty of the problems consider.
Normally, one would consider the classification loss to be the expected disagreement between the classifier and the labelling. However, it is more convenient for us to view a labelling y 1 as an "occurrence of error" and define the loss in terms of such occurrences. Specifically, for any subset S C Rd and any distribution D on Rd x {0, 1}. we define the classification loss as (S) Pr(x,y)=D (y = 11fx E 5. Note that this definition of classification loss is essentially the same as the "traditional" classification loss that defined in terms of disagreement since we can convert from one to another by simply negating the labelling. Analogously, for any subsets S,7 S Ted and any distribution DD on R.d (0, 1}. we denote the conditional loss by eST = Pr 1(xx E S} | x E T). When S = T, we abbreviate errp rSS) to errD/T.
Theorem 4.3 (Hardness Of Conditional Classification). Let 'D be any distribution on Ted f0, 1) with standard normal x-marginals, H be the class of halfspaces on Rdd, and define Hag (hy(wr) E H Prx-Dx (x E he [wn} } E [a, b]} for any 0 < a S b S 1. Under Assumption 4.2, for any constant a E (0, 2). 7 > 1/2 and any e/ /dloo Se <<11/log d where e is a suffi- ciently large constant, there is no algorithm that can find a halfspace (www) E Hop such that (II S [ (IT + and runs in time (01/(c//oody
Theorem 4.3 states our hardness result for conditional classification, which is a simple consequence of Proposition 4.5 and Lemma 4.6. The former one shows that conditional classification is at least as hard as agnostic classification and the latter one shows that agnostically learning halfspaces is hard.
Our main contribution is Proposition 4.5, but before getting into it, we first show a simple but critical observation that reveals the relationship between err and errpis- That is, the loss of agnostic classification can be explictly expressed by the loss of conditional classification.
Lemma 4.4 (Classification Error Decomposition). Let D be any distribution on Rdd x {0, 13 and S be any subset of RR, we have errp (S) = 2erT Pro fx E S} + Prø(y = 0} - Prpp E S) as well as (S) = 2- (S) Pro (x E 5*) + Pr = 1} PrD S..
Due to page limits, we defer its proof to Appendix E. Lemma 4.4 is powerful result since allows us establish reduction from classification conditional classification.
9

---

Published as a conference paper at ICLR 2025
Briefly speaking, if we know Pr(x E S*} } for some optimal solution S to the agnostic classification problem, we can approximate erT by upproximating its conditional classification loss, i... errp|s.. Even though we do not know Pr(x 5*), we can guess small range that contains Pr(x E }, and enforce such a constraint just in Definition 1.1. Then, we sweep over all such small intervals and one of the instances being solved must include Pr(x E S}. Once we take these intervals small enough, it won't t incur a significant error. We use this strategy to prove Proposition 4.5, but the formal proof is deferred to Appendix E due to the page limit.
Proposition 4.5 (Reduction In Additive Form). Let 'D be any distribution on R x {0, 1). H be any subset of the power set of Rd closed under complement, and define HDD = {S E H | Pr E S) E [a,b]] for any 0 a S b I 1. For any such a, b and c, > 0, given sample access to D, if there exists an algorithm Ai (, a, b) rumning in time poly(d, lfe, 1/6), that oulputs S E *HDh such that errpis, Ss S min SEH errp)s + with probubility as least 1 ö, there exists another algorithm A2(c. 8). that runs in time poly(d, 1/c, 1/5), and outpus S₂ E H such that (Sy) I mingen (ST + Ge with probability at least 1 - 8.
Furthermore, Lemma 4.6 states that agnostically learning halfspaces up to small additive error is computationally hard. Since Proposition 4.5 holds for halfspaces on Rd conditional learning has at least the same hardness by combining Proposition 4.5 and Lemma 4.6.
Lemma 4.6 (Corollary 3.2 of Diakonikolas et al. (2023)). Let DD be any distribution on I&d x (0, 1 with standard normal x-marginals, and H. be the class of halfspaces on R.d Under Assumption 4.2, for any constant a E (0. 2), 7 > 1/2 and any c/ dlgo d S c S 1//log d where is sufficiently large constant, there is no algorithm that can find a halfspace hy (v) E H. such that or (v)) & minn,("))> crrpphh (u)) + e and runs in time d0 (((((((/)og.d)").
Analogously, reduction in multiplicative form can also be obtained using similar analysis that in the proof of Proposition 4.5, In particular, we show that if there exists a multiplicative approximation algorithm for conditional classification with factor 1 + a, there must exist another multiplicative approximation algorithm for classification in agnostic setting with the same factor + a.
Claim 4.7 (Reduction In Multiplicative Form). Let DD be any distribution on IRd x {0, 1}. H be any subset of the power set of Rdd closed under complement, and define Ha.h {S E H| | Pr E ES} E (a, bl for any S a S S 1. If there exists an algorithm Ai Aa,a, 8, a, b) that given sample access to D, any such b, and e, 0 > O, runs in time poly(d, 1/a, 1/8), and outputs S1 Haph such that errDis, S (1++ a) minseng, erTDis with probability as least 1 8, there exists another algorithm A2(a, that runs in time poly(d, 1/a.1/e,,////// and outputs S2 E H such that (S2) S (1 + (minsen (S) + 4c) with probubility at least 8.
Again, defer the proof Appendix E. because of page limits. Although there is extra 4e additive error in the final guarantee of Claim 4.7, we can afford to take c polynomially small w.r.t. d, o, 6, thus obtaining the multiplicative error guarantee down to polynomially small error. Informally we observe that Proposition 4.5 and Claim 4.7 indicate that any form of approximation algorithm for conditional classification yields an approximation algorithm of the same factor for agnostic classification. In the case of multiplicative approximation in particular, the reverse is not known and we observe that it might be strictly harder to approximate the conditional classification objective.
LIMITATIONS AND FUTURE WORK
Our algorithmic result limited in three aspects. First and foremost, the restriction of selectors to homogencous halfspaces is a major drawback especially for the task of conditional classification. Indeed, the advantage of conditional classification with halfspaces compared with regular linear classification really shines when we have the ability to select a minority of the population. Therefore, moving from homogeneous halfspaces to general halfspaces would constitute a significant advance even with worse error bound. Another limitation of our result is the strong assumption the marginal distribution. Real-world data almost never has standard normal marginals, and testing for a standard normal distribution is costly. Hence, it's worth trying to extend our result to more general classes of distributions, such as log-concave distributions. Last but not the least, one can also try to improve our error guarantee under the current setting as the error guarantee (voop) appears sub-optimal.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We are grateful for many discussions with and feedback from Daniel Hsu. This work was partially supported by NSF awards I1S-1908287, and IIS-1942336, and NSF-Amazon award I1S-1939677.
REFERENCES
Ainesh Bakshi and Pravesh K Kothari. List-decodable subspace recovery: Dimension independent er- ror in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1279-1297.. SIAM, 2021.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervvnenkis dimension. Journal the ACM (JACM), 36(4):929-965, 1989.
Diego Calderon, Brendan Juba, Sirui Li, Zongyi Li, and Lisa Ruan. Conditional linear regression. In PMLR, 2020.
International Conference Artificial Intelligence and Statistics, pp.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data, Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, pp. 47-60. 2017.
C. Chow. optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970. doi: 10.1109/TIT. 1970. 1054406.
C. K. Chow. An optimum character recognition system using decision functions. IRE Transactions on Electronic Computers, ECC-64):247-254, 1957. doi: 1911000TT...5572522220
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pp. 67-82. Springer, 2016.
Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer Science & Business Media, 2001.
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. A polyno- mial time algorithm for learning halfspaces with tsybakov noise, arXiv preprint arX1:20010.01755. 2020a.
Iai Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learning Theory, pp. 1486-1513. PMLR, 2020b.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Non-convex sgd learns halfspaces with adversarial label noise. Advances in Neural Information Processing Systems, 33: 18549-18549, 2020c.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning, pp. 5118-5141. PMLR, 2022.
Ilias Diakonikolas, Daniel Kane, and Lisheng Ren. Near-optimal cryptographic hardness of agnosti- cally learning halfspaces and relu regression under gaussian marginals. International Conference on Machine Learning. pp. 7922-7938. PMLR, 2023.
Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Efficient testable learning of halfspaces with adversarial label noise. Advances in Neural Information Processing Systems, 36, 2024.
Ran El- Yanya and Yair Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2), 2012.
Ran El- Yaniv et al. On the foundations of noise-free free selective classification. Journal of Machine Learning Research, 11(5), 2010.
11

---

Published as a conference paper at ICLR 2025
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of halfspaces with gradient descent via soft margins. In International Conference on Machine Learning, pp. 3417-3426. PMLR, 2021.
Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. Selective classification via one-sided prediction. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th In- teratiional Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2179-2187. PMLR, 13-15 Apr 2021. URL https: //proceedings.... www.mmlr.ppp.... wrw.speesseee /100 / a html.
Yonatan Geifman and Ran El-Yaniv, Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
Yonatan Geifman and Ran El-Yaniv. SelectiveNet: A deep neural network with integrated reject option. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2151-2159, PMLR, 09-15 Jun 2019. URL https: http::///occeeeiggs../oo mlr.
press/v9 / gei fmanl 9a html.
Roei Gelbhart and Ran El-Yaniv. The relationship between agnostic selective classification, active learning and the disagreement coefficient. Journal of Machine Learning Research, 20(33):1-38, 2019. URL http: //mp: jmlr. wtt/ pappps/ppp///// 17 html.
Apara Gupte, Neekon Vafa, and Vinod Vaikuntanathan. Continuous Iwe is as hard Iwe applications to learning gaussian mixtures. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 1162-1173. IEEE, 2022.
John Hainline, Brendan Juba. Hai S. Le, and David Woodruff. Conditional sparse I. mn-norm regression with optimal probability. In Kamalika Chaudhuri and Masashi Sugiyama (eds.). Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statisties, volume 89 of Proceedings of Machine Learning Research, pp. 1042-1050. PMLR, 16-18 Apr 2019. URL ht https: http://coccceeeigsee//e mlr press / / v wtt./annllaiee i in 9a. html.
Blaise Hanezar and Edward Dougherty. Classification with reject option in gene expression data.
Bioinformatics, 24(17) 189-1895, 2008
Steve Hanneke. The optimal sample complexity of pac learning. Journal of Machine Learning Research, 17(38)11-1,, 2016.
David Haussler. Quantifying inductive bias: Ai learning algorithms and valiant's learning framework. Artificial intelligence, 36(2):177-2211 1988.
Daniel Hsu, Jizhou Huang, and Brendan Juba. Distribution-specifee auditing for subgroup fairness.
In 5th Symposium on Foundations of Responsible Computing (FORC 2024). Schloss Dagstuhl- für Informatik, 2024.
Brendan Juba. Learning abductive reasoning using random examples. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), Feb. 2016. doi: 10. wwwp9///aa..00...1.00... URL httpss//ojss aaai org index.iixx.. Aww.///aaaaet/aeaeeeeeeaaaaaaaee
Brendan Juba. Conditional sparse linear regression. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Haaloss-Dagstuhl--Lae
Zentrum für Informatik, 2017.
Brendan Juba, Zongyi Li, and Evan Miller. Learning abduction under partial observability. In Pro- ceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI MAIT18/AAA 18. AAAI Press, 2018. ISBN 978-1- 57735-800-8.
Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. List-decodable linear regression. Advances in neural information processing systems, 32, 2019.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerrymandering: Auditing and learning for subgroup fairness. In International conference on machine learning, pp. 2564-2572 PMLR, 2018.
12

---

Published as a conference paper at ICLR 2025
Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17:115-141, 1994.
Javed Khan, Jun S Wei, Markus Ringner, Lao H Saal, Mare Ladanyi, Frank Westermann, Frank Berthold, Manfred Schwab, Cristina R Antonescu, Carsten Peterson, al. Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks. Nature medicine, 7(6):673-679 2001.
Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 1035-1046, 2018.
Anqi Mao, Christopher Mohri, Mehryar Mohri, and Yutao Zhong. Two-stage learning to defer with multiple experts. Advances in neural information processing systems, 36, 2024a.
Angi Mao, Mehryar Mohri, and Yutao Zhong. Theoretically grounded loss functions and algorithms for score-based multi-class abstention. In International Conference on Artificial Intelligence and Statistics, pp. 4753-4766 PMLR, 2024b.
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. In Claire Vernade and Daniel Hsu (eds.), Proceedings of The 35th International Conference on Algorithmic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pp. 822-867. PMLR, 25-28 28 Feb 2024c. URL https: /pwp/eddigee.s.. mlr. www.ppees//eee vereess/v33/0 mww.222mmmmmmm2mmmmmmm 22 html.
Elchanan Mossel and Madhu Sudan. Personal communication, 2016.
Andrea Pugnana and Salvatore Ruggieri. Auc-based selective classification. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van Meent (eds.), Proceedings of The 26th International Confer- ence on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 2494-2514. PMLR, 25-27 Apr 2023. URL https: http::://prcceedings. mmr. press/ wwe/ss/v20/// pugnana23a html.
Prasad Raghavendra and Morris Yau. List decodable learning via of squares. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 161-180. SIAM, 2020.
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the
ACM (JACM), 56(6): 1-10,140222 2009.
Jie Shen. On the power of localized perceptron for label-optimal learning of halfspaces with adversarial noise. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9503-9514, PMLR, 18-24 Jul 2021. URL https: http::///ccceeeeeeppeeeeo shen21a a. html.
.mm.innssmmrrrr... mll www.s.pres///eeee vv199/
Roman Vershynin. High-dimenssooall probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Yair Wiener and Ran El- Yaniv. Agnostic selective classification. Advances neural information processing systems, 24, 2011.
Yair Wiener and Ran El-Yaniv. Agnostic pointwise-competiine selective classification. Journal of Artificial Intelligence Research, 52:171-201, 2015.
Mengxue Zhang, Tushar Mathew, and Brendan Juba. An improved algorithm for learning to perform exception-toleran abduction. In Proceedings of the AAAI Conference Artificial Intelligence. volume 31, 2017.
13


Reviews:
[{"review_id": "EzgLQaBTkQ", "reviewer": "Reviewer_gfkp", "summary": "This paper studies conditional classification with homogeneous halfspaces as selectors under the agnostic learning setting with Gaussian marginals. That is, given access to samples from underlying distribution $D$ with adversarial label noise, the algorithm aims to output a classifier-selector(halfspace) pair, such that the classifier makes low prediction error conditioned on the instances in the given halfspace. When there exists a pair $(c^*,v^*)$ that achieves $opt$ error rate, this paper proposes an algorithm that can output a pair $(c,w)$ that achieves error rate of $\\tilde{O}(\\sqrt{opt})$. The algorithm is based on Projected SGD for choosing the appropriate halfspace and then output the classifier-halfspace pair with minimal loss.\n\nOn the other hand, the paper shows that agnostic conditional learning with general halfspace selectors is computationally hard.", "questions": "I didn't get the part of choosing ReLU function as the convex surrogate approximation of the conditional classification error? It seems $L_D(w)$ also blocks the information for one-sided class $y=1$. However, $g_w(x,y)$ seems to be one-sided.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper studies an interesting problem, which considers agnostic classification under a conditional distribution. It models the conditional distribution using a homogeneous halfspace, and complement the result using a hardness example for non-homogeneous halfspace. The paper also links the problem to many other important problems in machine learning, including learning under the list-decodable setting, learning with abstention, etc. It will be interesting to investigate the deep connection between these problems.\n\nThe theoretical analysis is generally sound to me. The paper reads smoothly, with results well presented.", "weaknesses": "The paper claims that the classifiers are sparse, but it seems the aim is to limit the size of the classifier set. The paper has very limited discussion on this matter, which makes the claim of learning \"sparse\" classifiers a bit misleading.\n\nAlthough agnostic conditional learning with general halfspaces is computational hard, the current algorithm for homogeneous halfspace selector also depends on the size of the classifier set $\\lvert\\mathcal{C}\\rvert$. The paper claims that $\\lvert\\mathcal{C}\\rvert$ is small, I wonder how applicable the current algorithm is to the agnostic conditional learning problem for general class of binary classifiers.\n\nThe algorithm relies strongly on the Gaussian marginals assumption, such that any halfspace has probability mass of $1/2$. Is there any way we can extend this assumption? Or, the whole analysis only works for Gaussians?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qugFjT8yCr", "reviewer": "Reviewer_ZDsQ", "summary": "This paper studies distribution-specific agnostic conditional classification for halfspaces. In particular, they consider sparse linear classifiers, subsets defined by halfspaces, and Gaussian feature distributions. Both positive and negative results are provided. On the positive side, they authors give the first polynomial time PAC learning algorithm when the selectors are homogenous half spaces with error guarantee $\\tilde{O}(\\sqrt{\\epsilon})$. On the negative side, the authors show that under standard cryptographic assumptions and even under gaussian features, estimating the conditional classification error is computationally hard. This proof involved reducing approximating agnostic classification, which is known to be hard, to approximating conditional classification.", "questions": "- Theorem 1 states that Algorithm 1 outputs a good half space selector **for each** concept $c \\in C$. But, don't you need to ouput a single selector that works well across all concepts in $C$? If I am not mistaken, I do not see a Theorem in the paper that quantifies the error of the selector output in Step 11 of Algorithm 1. \n\n- Based on Algorithm 1, it seems like the class of concepts needs to be finite? Is there anyway to relax this assumption and have the input $T, N$ depend on the VC dimension of $C$?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem setting is interesting and well-motivated\n- The proof techniques seem non-trivial and novel \n- Both the positive and negative results, in my opinion, and important contributions to this area.", "weaknesses": "I don't have any specific weakness in mind. That said, the paper does feel very dense and would benefit from more informal theorems/lemmas/propositions in the main text, and more details in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LDrzhBAUrg", "reviewer": "Reviewer_bBb3", "summary": "This work studies the problem of conditional classification. The problem of conditional classification is the following: Given a finite classifiers of class $\\mathcal{C}$ and a set of concepts $\\mathcal{H}$ that have non-trivial probability over the marginal, the task is to find a pair $(c,h)$ for $c\\in \\mathcal{C}$ and $h\\in \\mathcal{H}$ such that $\\Pr[y\\neq c(x)\\mid x\\in h]$ is small. They consider $\\mathcal{H}$ to be the class of homogeneous halfspaces. They prove that there exists a polynomial time algorithm for the above task that achieves error $\\tilde{O}(\\sqrt{opt})$ where $opt$ is the minimum error possible. They also prove a lower bound that says conditional classification is hard for general halfspaces.", "questions": "1) In section 1.3, it would be helpful to state both theorems corresponding to the contributions within this section or provide a link to their statements for easy reference.\n2) The connection to list learning is unclear. In particular, why is Theorem 2.1 stated in the preliminaries? Where is it used in your proof?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The reduction from conditional classification to one sided agnostic classification seems novel. Although the reduction is not complicated, it is neat.\n2) The proofs seem correct and intuitive. \n3) I believe that this work makes important progress in the study of conditional classification. \n4) Their algorithm runs in polynomial time (although they obtain a multiplicative approximation).", "weaknesses": "1) The lower bound for general halfspaces is for the objective $opt+\\epsilon$. However, the upper bound only achieves $\\sqrt{opt}$ for homogenous halfspaces. Is it the case that $\\sqrt{opt}$ is not possible for general halfspaces efficiently? Their lower bound does not seem to exactly complement their upper bound. \n2) The statements of the theorems have grammatical errors. For instant, in proposition 3.2, the last line says if {property A}, there is {property B}. \"There is\" should be replaced by \"it holds that\" or \"we have\".\n3) The presentation is a bit unclear in some places. Further expanded in Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rcnw2kS7k7", "reviewer": "Reviewer_XCyY", "summary": "The paper considers agnostic conditional classification when the underlying marginal distribution is Gaussian and the selector is a half-space. First, the authors prove a polynomial time algorithm that returns a classifier-selector pair such that the associated risk is at most the square root of optimal risk. Given this, a natural question is whether one can achieve an error that is at most $\\varepsilon$ away (additively) from the optimal risk. Unfortunately, the authors prove a hardness result showing that no polynomial algorithm can achieve this.", "questions": "1. How essential is the choice of the Gaussian distribution for this analysis? I skimmed the proofs in the supplementary materials, and it appears that the arguments primarily rely on the symmetry and tail probability bounds of the Gaussian. Do you think the same results could be extended to symmetric sub-Gaussian (or, ideally, just sub-Gaussian) random variables?\n\n2. Is anything known about lower bounds on the risk of polynomial algorithms in this setting? In their discussion, the authors mention that the $O(\\sqrt{\\varepsilon}) $ rate appears suboptimal. I was wondering if the authors have any reasons to support this belief.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and is easy to follow. I particularly like Section 3.2 where the paper guides us through the proof sketch, while including propositions, and lemmas required for the proof. \n\n2. The algorithm appears both natural and intuitive. While not strictly necessary, it would be helpful if the authors could provide additional context around two aspects of the proposed algorithm. First, what is the intuition behind initializing PSGD for both $ w^{(0)} $ and $-w^{(0)} $? Second, what motivates the choice of ReLU as the convex surrogate? Although the paper includes some description, it is unclear whether ReLU's usefulness here is due to the separators being halfspaces, or if the goal is more related to obtaining gradients of a specific form by using tools from Diakonikolas et al. (2020b).", "weaknesses": "The authors list a few limitations of the work in the final section of the paper. Another major weakness of the paper is the fact that Theorem 3.1 only holds for a finite class of classifiers $\\mathcal{C}$. Typically, finite hypothesis class $\\mathcal{C}$ is justified because some form of discretization-based arguments generalize the result to infinite class as well. For example, usually, proving risk bounds for half-spaces can be reduced to proving risk bounds for finite discretization of half-spaces. However, Theorem 3.1 cannot even handle the discretization of half-spaces because the size of $\\varepsilon$ discretization of half-spaces on $d$ dimension is roughly $\\varepsilon^{-d}$.  Given that the runtime of Algorithm 1 is $O(d\\,  |\\mathcal{C}|/\\varepsilon^6)$, taking $|\\mathcal{C}| \\approx \\varepsilon^{-d}$ makes the runtime exponential in $d$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "35t2n4AZkM", "reviewer": "Reviewer_qivV", "summary": "This paper studies the agnostic conditional classification problem for a finite class of hypotheses $\\mathcal{C}$. In the classic agnostic learning setting, a learner is asked to output a hypothesis $c \\in \\mathcal{C}$ that achieves a small error over the whole domain of examples. In the conditional classification setting, a learner is instead asked to output a subset $S$ of the domain and a hypothesis $c$ such that the conditional error over $S$ is small. The motivation is that over some subset of the domain, the error rate of a hypothesis could be much lower than the error rate over the whole domain. This paper focuses on a special case of the conditional classification problem, where the marginal distribution is a standard Gaussian and the subset output by the learner is the positive region of some homogeneous halfspace. The paper gives an algorithm that runs in time $poly(|\\mathcal{C}|,1/\\epsilon,d)$ and outputs a hypothesis $c \\in \\mathcal{C}$ and a homogeneous halfspace $h$ such that the conditional error of $c$ over $h$ is at most $\\tilde{O}(\\sqrt{opt}+\\epsilon)$, where $opt$ is the smallest conditional error of some $c$ over all possible homogeneous halfspaces. Technically, the algorithm can be seen as an application of agnostic learning homogeneous halfspaces under Gaussian with respect to conditional error (examples in the halfspaces are labeled by 0, noisy examples have artificial labels 1). Given such a halfspace learning algorithm, the learner can brute force and compute an approximate best halfspace for each hypothesis in the class. On the other hand, the paper reduces the problem of agnostic learning Gaussian halfspaces to the conditional classification problem and uses the known cryptographic hardness result to show that it is impossible to approximate the optimal conditional classification error within an additive error in polynomial time.", "questions": "1. Can you help formally explain how to use robust list learning to deal with larger hypothesis classes? Why learning $O(1)$-sparse linear separators is used as an example here? Is it because the length of the list can be controlled? What if we consider other simple hypothesis classes such as high-dimensional boxes or dense linear separators?\n\n2. Previous agnostic halfspace learning papers such as [DKTZ22] show that under Gaussian as long as the angle between the current hypothesis and the target is small, one can achieve error $O(opt+\\epsilon)$ and thus those algorithms all converge in the last iterate. Can you provide any intuition of why similar arguments cannot be used here and why the algorithm can only converge in average and achieve $\\sqrt{opt}+\\epsilon$?\n\n3. Please make comments on the weakness that I pointed out above. I would raise my score based on the response.\n\n\n[DKTZ22]Diakonikolas I, Kontonis V, Tzamos C, Zarifis N. Learning general halfspaces with adversarial label noise via online gradient descent. International Conference on Machine Learning 2022 Jun 28 (pp. 5118-5141). PMLR.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The presentation of the paper is clear. The main body of the paper gives a clear technical review of the algorithms and the proof of the hardness result.\n2. Technically, this paper gives a novel algorithm for agnostic learning homogeneous Gaussian with conditional error. Previously known algorithms for agnostic learning halfspaces all concern the error over the whole domain. It is not clear whether we can apply these algorithms directly to get a good hypothesis with a small conditional error. So, the new algorithm might be of interest to the community", "weaknesses": "1. From my point of view, the main weakness of this paper is the motivation of using homogeneous halfspaces as a selector under Gaussian distribution. I am not sure whether the conditional error itself alone is a meaningful metric, because, in selective classification, one should also consider the coverage of the output selector (accept rate of the selector). For example, one may output two selectors with different accept rates but the same conditional error. In this case, it makes no sense to use the one with a lower accept rate. However, such an important characterization is not considered by the paper. Under Gaussian distribution, all homogeneous halfspace selectors have a reject rate of 1/2, which is fairly high. It does not make sense to use a selector that has to throw away half of the examples. More importantly, this equal reject rate makes the risk-coverage tradeoff curve disappear in the setting studied by this paper. These two limitations of using a halfspace selector under Gaussian make the result a little bit strange from the perspective of selective classification and look more like an application of halfspace learning.\n\n2. The main algorithm can only deal with a class of finite concepts. In fact, finiteness is very crucial in the paper as the main algorithm in the paper computes a good selector for every single concept in the class and does not make use of any structure of the concept classes. Though, at the end of Section 1.1, the authors mention that one can deal with larger classes via robust list learning, the paper does not give a very clear explanation of how to use robust list learning to selectively learn a general class.  For example, to selectively learn a VC class $H$, it is not clear how to set up the parameters in the corresponding robust list learning. The authors also mentioned an efficient list-learning algorithm for sparse linear separators but did not explicitly connect this example with selective learning. I believe more explanations are needed in the future version of the paper.\n\n3. As mentioned by the authors, the error guarantee $\\tilde{O}(\\sqrt{opt})+\\epsilon$ is not optimal, and thus the hardness result in the paper does not rule out the possibility of having an algorithm with much better error guarantee. \n\n4. The abstract in the OpenReview states the algorithm can learn a selector up to error $O(opt)$, which is different from the results obtained by the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)