Pith. sign in

REVIEW 2 major objections 4 minor 49 references

Distribution-Specific Agnostic Conditional Classification With Halfspaces

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that under standard normal features, agnostic conditional classification by homogeneous halfspace selectors is PAC-learnable with error O(√opt), and that general halfspace selectors are as hard as agnostic learning under…

desk verdict A genuinely new algorithmic result with a real but fixable gap in the main theorem's epsilon quantification; deserve a serious referee. read the letter →

arxiv 2502.00172 v1 pith:XNAJ2O3H submitted 2025-01-31 cs.LG cs.CCstat.ML

Jizhou Huang , Brendan Juba This is my paper · ORCID
classification cs.LGcs.CCstat.ML MSC 68Q3268T0562H3068Q17
keywords conditionalclassificationselectivehomogeneoushalfspacesagnosticlearningGaussianmarginalsPACprojectedSGDwitherrors
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Selective (conditional) classification asks for a classifier that is accurate only on a chosen subset of the data, selected by a rule such as a halfspace. This paper gives the first polynomial-time PAC-style algorithm for the agnostic version of this problem when the feature distribution is standard normal (Gaussian) and the selector is a homogeneous halfspace: if the best classifier-selector pair makes conditional error $\mathrm{opt}$, the algorithm finds a homogeneous halfspace selector whose conditional error is $O(\sqrt{\mathrm{opt}})$, using $\tilde{O}(d/\mathrm{opt}^6)$ samples. The catch is that the result relies heavily on the Gaussian assumption, since the argument uses the fact that every homogeneous halfspace contains exactly half the probability mass, making conditional error equal to joint error on the selected region. On the negative side, the paper proves that relaxing to general halfspace selectors makes the problem as hard as agnostically learning halfspaces: under the continuous Learning-With-Errors assumption, no polynomial-time algorithm can approximate the optimal conditional error within an additive $1/\log^{\gamma} d$ error, and any approximation algorithm for conditional classification implies one for standard agnostic classification.

What carries the argument

The machine that carries the positive result is the ReLU surrogate loss $L_D(w) = \mathbb{E}_{(x,y)\sim D}[y \max(0, \langle x, w\rangle)]$ with its projected gradient $g_w(x,y) = y\, x_{w^\perp} \mathbf{1}\{x \in h(w)\}$, minimized by projected SGD in Algorithm 2. Its key property (Proposition 3.2) is that when a halfspace $h(w)$ is noticeably sub-optimal relative to an optimal $h(v)$, the negative expected gradient has a positive projection onto $v$, so the SGD update rotates $w$ toward $v$; conversely, a near-stationary point has near-optimal conditional error. This reasoning is anchored in the standard normal assumption: every homogeneous halfspace $h(w)$ has Gaussian measure exactly $1/2$, so minimizing the joint error $\Pr\{x \in h(w), c(x) \neq y\}$ is the same as minimizing the conditional error, and Gaussian tail and anti-concentration bounds make the surrogate gradient sufficiently well behaved (relative smoothness, Lemma B.1).

What would settle it

A concrete check: in dimension two, set $v = (1,0)$ and $w = (\cos\theta, \sin\theta)$, and choose a label function with $\Pr\{x \in h(v), y=1\} = \epsilon$ and $\Pr\{x \in h(w), y=1\} \ge \frac{5}{2}\sqrt{\epsilon \ln(1/\epsilon)}$. Numerically evaluate $\langle \mathbb{E}[-g_w(x,y)], \bar{v}_{w^\perp}\rangle$ under the standard normal distribution and test whether it is at least $\frac{2}{5}\epsilon\sqrt{\ln(1/\epsilon)}$. A single pair $(v,w)$ violating this inequality would invalidate Proposition 3.2 and with it the main theorem's proof.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: for a distribution with standard normal $x$-marginal and any finite class $\mathcal{C}$ of classifiers, if some unit vector $v$ and classifier $c$ satisfy $\Pr\{x \in h(v) \wedge c(x) \neq y\} \le \epsilon$, then a projected stochastic gradient algorithm (Algorithm 2) returns a homogeneous halfspace selector $w(c)$ whose conditional error $\Pr\{x \in h(w(c)) \wedge c(x) \neq y\}$ is $O(\sqrt{\epsilon})$, with $\tilde{O}(d/\epsilon^6)$ samples and polynomial time. The method maps each classifier $c$ to a modified distribution where the label is the indicator of $c(x) \neq y$, turning conditional classification into a one-sided agnostic linear classification problem. The proof shows that a near-stationary point of the convex ReLU surrogate $L_D(w) = \mathbb{E}[y \max(0, \langle x, w\rangle)]$ is a near-optimal selector: Gaussian anti-concentration forces the negative projected gradient to point toward the optimal halfspace $v$ whenever the current halfspace is substantially sub-optimal. Theorem 3.5 extends the guarantee to sparse linear classifiers by first running a robust list-learning algorithm, producing a finite candidate list. The negative result (Theorem 4.3) establishes that for general halfspaces, obtaining conditional error within additive $\epsilon$ of optimum is at least as hard as agnostic linear classification, hence computationally hard under sub-exponential cLWE.

Load-bearing premise

The positive result stands or falls on the feature marginal being exactly the standard normal distribution: the proof uses that every homogeneous halfspace has measure exactly one half, plus Gaussian tail and anti-concentration bounds, none of which survive a shift or distortion of the marginal.

Editorial extensions

If this is right

  • If Theorem 3.1 holds, conditional classification with homogeneous halfspace selectors is PAC-learnable under standard normal features, with polynomial sample and time complexity and an error guarantee that degrades gracefully as the optimal error grows.
  • The guarantee extends to sparse linear classifiers (sparsity O(1)) via robust list learning, giving the first polynomial-time approximation for that infinite class.
  • The hardness result means that even under Gaussian marginals, no polynomial-time algorithm can approximate the optimal conditional error within an inverse-polylog additive error for general halfspace selectors, assuming the sub-exponential continuous LWE assumption.
  • The reductions imply that any additive- or multiplicative-factor approximation algorithm for conditional classification would yield a matching-factor approximation for standard agnostic classification, so conditional classification is at least as hard as ordinary agnostic classification.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A plausible follow-up is that the square-root dependence is an artifact of the one-sided ReLU surrogate and could be improved to near-linear error for label structures that are not adversarial, though the authors leave this open.
  • Because the exact half-measure property of homogeneous halfspaces is the engine, the same reduction may extend to isotropic log-concave distributions with a distribution-dependent constant, provided a bound on the halfspace measure replaces the exact 1/2; this is a concrete testable extension.
  • The general-halfspace hardness parallels recent hardness results for subgroup-fairness auditing under Gaussian data, suggesting that the difficulty of conditional classification is not the Gaussian marginal itself but the ability of the selector to isolate small, unbalanced regions.
  • An empirical check on synthetic Gaussian data with planted halfspace labels and variable noise would reveal whether the O(√opt) guarantee holds with practical constants and whether the algorithm's selectors recover the planted region.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies agnostic conditional (selective) classification under Gaussian marginals, where the selector is a homogeneous halfspace and the classifier belongs to a finite class or a list-learnable class such as sparse linear classifiers. The main positive result, Theorem 3.1, claims a polynomial-time algorithm with error Õ(√ε) whenever an optimal pair has joint conditional error at most ε, under the assumption that ε is a sufficiently small element of [0,1/e]. A second positive result, Theorem 3.5, extends the guarantee to sparse linear classifiers via robust list learning. On the negative side, the paper proves that, under a sub-exponential cLWE assumption, approximating the conditional classification loss within a small additive error is as hard as agnostically learning halfspaces. The hardness result proceeds through a reduction (Proposition 4.5 and Claim 4.7) showing that any approximation algorithm for conditional classification, in additive or multiplicative form, yields an approximation algorithm for ordinary classification.

Significance. If the positive result is established in the stated form, it is a genuinely new algorithmic contribution: it is the first PAC-style guarantee for agnostic conditional classification with halfspace selectors that is both polynomial-time and competitive with the optimal classifier-selector pair, and the O(√opt) approximation is analogous to known guarantees in agnostic halfspace learning. The negative result is also significant: it gives a distribution-specific hardness reduction showing that conditional classification is at least as hard as agnostic classification, which is not a priori obvious and complements the positive result. The paper contains detailed proof appendices, and the algorithmic parameters are set analytically without data-dependent fitting; these are strengths. The hardness reduction is a genuine reduction from a known hard problem rather than a circular argument. However, the central positive theorem has a quantitative gap concerning the range of ε for which the proof works, and the statement of the theorem does not specify the required threshold. This is load-bearing because the abstract and introduction claim the Õ(√opt) approximation without qualification.

major comments (2)
  1. [Theorem 3.1, Lemma C.5, Corollary C.4, Proposition C.2] The proof chain of the main positive result contains a quantitative mismatch that is not visible in the theorem statement. Proposition B.2 guarantees the existence of a parameter w with ||E_D[g_w(x,y)]||_2 ≤ ε, but Corollary C.4 only applies when ||E_D[g_w(x,y)]||_2 < (2/5)ε√ln(1/ε). The implication ||E_D[g_w]||_2 ≤ ε ⇒ ||E_D[g_w]||_2 < (2/5)ε√ln(1/ε) holds only for ε ≤ e^{-25/4} ≈ 0.00193, not on the full interval [0,1/e] stated in Theorem 3.1. In addition, inequality (11) in the proof of Proposition C.2 invokes x/2 ≤ 1−e^{-x} for x ∈ [0,1.59], which requires 4eπε√ln(1/ε) ≤ 1.59; this condition is violated for ε near 1/e (for example, at ε = 0.1). Consequently, the theorem as written is proved only for ε below an unstated universal constant, not for the entire stated range. Since the abstract and introduction claim an Õ(√opt) approximation without this threshold, the issue is load-bearing. The fix is local: run Proposition B.2 with target η = (2/5)ε√ln(1/ε), which changes the constants in Algorithm 1 but preserves the O~(d/ε^6) asymptotic sample complexity, and state the resulting universal threshold ε0 explicitly in Theorem 3.1 and Lemma 3.4.
  2. [Appendix D, proof of Theorem 3.5] The decomposition of the distribution in the proof of Theorem 3.5 contains a non-sequitur. From the assumption Pr{x ∈ h(v) ∩ c(x) ≠ y} ≤ ε and Pr{h(v)} = 1/2, the text correctly observes that at least a 1/2 − ε fraction of the labels are consistent with c(x). It then concludes that there exists α ≥ 1 − ε such that D = αD* + (1−α)D~ with D* always labeled by c(x). This does not follow: in any such mixture the probability of consistent labels is at least α, so α can be at most the total consistent probability, which is only known to be at least 1/2 − ε. The correct conclusion is α ≥ 1/2 − ε, which is still a positive constant for ε ≤ 1/e, so the list-learning step and the polynomial bound in Theorem 3.5 remain valid. The displayed inequality α ≥ 1 − ε should be corrected and the surrounding argument adjusted accordingly.
minor comments (4)
  1. [Title page and Lemma B.1] There are typographical errors that should be fixed in revision: the affiliation reads "Washington Universtiy" and the proof of Lemma B.1 begins "Without loss of generosity".
  2. [Theorem 4.3] The quantified condition in Theorem 4.3 is written as "c/√d log d ≥ ǫ ≤ 1/logγ d", which is ambiguous. It should be stated as two separate conditions: c/√(d log d) ≥ ε and ε ≤ 1/log^γ d.
  3. [Claim E.4, Case II] In the proof of Claim E.4, Case II, the text says "S∗∈H^{pl,pu}_D" when it means S∗^c ∈ H^{pl,pu}_D; the surrounding sentence refers to Pr{x ∈ S∗^c} = 1−p, so this is a clear typo.
  4. [Section 5] The limitations section is candid about the two main restrictions: homogeneous halfspace selectors and the exact standard-normal marginal. It would be helpful to state explicitly that the proof of the positive result does not degrade gracefully when the marginal deviates from N(0,I), since the equivalence between conditional and joint error uses the exact equality Pr_{x∼N(0,I)}{x ∈ h(w)} = 1/2 for every homogeneous halfspace.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: algorithm hyperparameters are analytic, list learning is reproved from VC bounds, and hardness is a genuine reduction from cLWE/LWE.

full rationale

Derivation chain is self-contained. Algorithm 1/2 hyperparameters T, N, beta are set analytically (T=(4d+ln(8|C|/δ))/ε^4 etc.), never fitted to data; the output selector is chosen by empirical minimization over the algorithmically produced list, and the guarantee is proven from Gaussian anti-concentration and Projected-SGD gradient-norm convergence (Proposition B.2, Lemma C.5). The list-learning ingredient (Theorem 2.1) cites Juba 2017 / Mossel-Sudan but is reproved in Appendix A from VC dimension, so it is not an unverified self-citation. The hardness result is a genuine reduction from the sub-exponential cLWE/LWE assumption (Assumption 4.2 / E.1) via the algebraic identity in Lemma 4.4; that decomposition is not a restatement of the theorem's conclusion. Self-citations to Hsu-Huang-Juba (fairness auditing) and Juba (abduction) are contextual and not load-bearing. The unquantified 'sufficiently small ε' in Theorem 3.1 and any related threshold mismatch in the proof (e.g., Corollary C.4 vs. Proposition B.2) are correctness/quantification concerns, not circularity: the proof does not assume the theorem's conclusion. Limitations stated in Section 5 (standard normal marginals, homogeneous halfspace restriction, suboptimal O(√ε) bound) are honest and do not smuggle the target results into the assumptions.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the standard normal marginal assumption, the homogeneity restriction on selectors, and standard cryptographic and computational learning assumptions. There are no fitted parameters or invented entities; the algorithm's hyperparameters are set analytically.

assumptions (6)
  • domain assumption The x-marginal of the distribution is standard normal N(0,I_d).
    Used throughout Section 3; Lemma B.1, Proposition 3.2, and the concentration tools in Appendix F rely on Gaussian tail bounds and anti-concentration.
  • standard math Every homogeneous halfspace has Gaussian measure exactly 1/2.
    Follows from symmetry of the standard normal; used to equate conditional classification error with joint error in Section 3.
  • domain assumption Sub-exponential cLWE and sub-exponential LWE assumptions hold.
    Assumption 4.2 and Assumption E.1 are used to derive the hardness result in Section 4.
  • standard math Robust list learning of sparse linear classifiers is possible in polynomial time with list size O((md)^s).
    Theorem 2.1, cited from Juba (2017) and Mossel-Sudan (2016), reviewed in Appendix A; used to extend Algorithm 1 to sparse linear classifiers.
  • standard math Agnostic learning of halfspaces under Gaussian marginals with additive error epsilon is computationally hard.
    Lemma 4.6, stated as Corollary 3.2 of Diakonikolas et al. (2023); used to transfer hardness to conditional classification.
  • standard math Standard sample complexity bounds from VC theory.
    Used in the proof of Theorem A.1 to show that a consistent hypothesis on enough inliers achieves low error.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distribution-Specific Agnostic Conditional Classification With Halfspaces." pith.science (2026). https://pith.science/paper/XNAJ2O3H

@misc{pith2026250200172,
  author       = {Pith},
  title        = {Pith review of: Distribution-Specific Agnostic Conditional Classification With Halfspaces},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XNAJ2O3H}},
  note         = {Machine review of arXiv:2502.00172}
}
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 $\bigO*{\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.

Figures

Figures reproduced from arXiv: 2502.00172 by the authors.

Figure 1
Figure 1. Blue area represents h(v) ∩ h(w), orange area represents h(w)\h(v). We leave the formal proof to Appendix C due to the page limit. The proof is based on the following observation (also see [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Boundedness of LD(w(i) ) and almost Lipschitz continuity of ∇wLD(w). However, the magnitude of LD(w) is dominated by kwk2, which could grow unbounded after many iterations, and its gradient ∇wLD(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… view at source ↗
Figure 3
Figure 3. Spherical coordinate interpretation. 3. For any xV = (x1, x2, x3), let φ = θ(xV , e3), θ = θ(xV e⊥ 3 , e1), and r = kxV k2 , then we have x3 = r cos φ, x1 = r sin φ cos θ, and x2 = r sin φ sin θ. Now, applying the standard Jacobian matrix that maps the spherical coordinates to 3-dimensional Cartesian coordinates yields dx1dx2dx3 = r 2 sin φdrdφdθ. Therefore, following with 14 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Weight update step (line 5) and projection step (li [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Blue area represent h(v) ∩ h(w), while orange area represents h(w) ∩ h c (v). Observe that, since x is sampled from a standard normal distribution and e1, e2 are two orthonormal basis, x1, x2 are two independent one-dimension standard normal random variables. Then, obs…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages

  1. [1]

    Bakshi and P

    A. Bakshi and P . K. Kothari. List-decodable subspace rec overy: Dimension independent error in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algo rithms (SODA) , pages 1279–1297. SIAM, 2021

    work page 2021

  2. [2]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth . Learnability and the vapnik-chervonenkis dimen- sion. Journal of the ACM (JACM), 36(4):929–965, 1989

    work page 1989

  3. [3]

    Calderon, B

    D. Calderon, B. Juba, S. Li, Z. Li, and L. Ruan. Conditiona l linear regression. In International Conference on Artificial Intelligence and Statistics , pages 2164–2173. PMLR, 2020

    work page 2020

  4. [4]

    Charikar, J

    M. Charikar, J. Steinhardt, and G. V aliant. Learning fro m untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 47–60, 2017

    work page 2017

  5. [5]

    C. Chow. On optimum recognition error and reject tradeof f. IEEE Transactions on Information Theory , 16(1): 41–46, 1970. doi: 10.1109/TIT.1970.1054406

    work page arXiv 1970

  6. [6]

    C. K. Chow. An optimum character recognition system usin g decision functions. IRE Transactions on Electronic Computers, EC-6(4):247–254, 1957. doi: 10.1109/TEC.1957.5222035

    work page arXiv 1957

  7. [7]

    Cortes, G

    C. Cortes, G. DeSalvo, and M. Mohri. Learning with reject ion. In Algorithmic Learning Theory: 27th Interna- tional Conference, ALT 2016, Bari, Italy, October 19-21, 20 16, Proceedings 27, pages 67–82. Springer, 2016

    work page 2016

  8. [8]

    Devroye and G

    L. Devroye and G. Lugosi. Combinatorial methods in density estimation . Springer Science & Business Media, 2001

    work page 2001

Show all 49 references
  1. [9]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, V . Kontonis, C. Tzamos, and N . Zarifis. A polynomial time algorithm for learning halfspaces with tsybakov noise. arXiv preprint arXiv:2010.01705 , 2020

    2010 arXiv

  2. [10]

    Diakonikolas, V

    I. Diakonikolas, V . Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learning Theory , pages 1486–1513. PMLR, 2020. 10

    2020

  3. [11]

    Diakonikolas, V

    I. Diakonikolas, V . Kontonis, C. Tzamos, and N. Zarifis. Non-convex sgd learns halfspaces with adversarial label noise. Advances in Neural Information Processing Systems , 33:18540–18549, 2020

    2020

  4. [12]

    Diakonikolas, V

    I. Diakonikolas, V . Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning , pages 5118–5141. PMLR, 2022

    2022

  5. [13]

    Diakonikolas, D

    I. Diakonikolas, D. Kane, and L. Ren. Near-optimal cryp tographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. In International Conference on Machine Learning , pages 7922–

  6. [14]

    Diakonikolas, D

    I. Diakonikolas, D. Kane, V . Kontonis, S. Liu, and N. Zar ifis. Efficient testable learning of halfspaces with adversarial label noise. Advances in Neural Information Processing Systems , 36, 2024

    2024

  7. [15]

    El-Y aniv and Y

    R. El-Y aniv and Y . Wiener. Active learning via perfect s elective classification. Journal of Machine Learning Research, 13(2), 2012

    2012

  8. [16]

    El-Y aniv et al

    R. El-Y aniv et al. On the foundations of noise-free sele ctive classification. Journal of Machine Learning Re- search, 11(5), 2010

    2010

  9. [17]

    S. Frei, Y . Cao, and Q. Gu. Agnostic learning of halfspac es with gradient descent via soft margins. In Interna- tional Conference on Machine Learning , pages 3417–3426. PMLR, 2021

    2021

  10. [18]

    Gangrade, A

    A. Gangrade, A. Kag, and V . Saligrama. Selective classi fication via one-sided prediction. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artific ial Intelligence and Statistics , volume 130 of Proceedings of Machine Learning Resear...

    2021

  11. [19]

    Geifman and R

    Y . Geifman and R. El-Y aniv. Selective classification fo r deep neural networks. Advances in neural information processing systems, 30, 2017

    2017

  12. [20]

    Geifman and R

    Y . Geifman and R. El-Y aniv. SelectiveNet: A deep neural network with an integrated reject option. In K. Chaud- huri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machin e Learning , volume 97 of Proceedings of Machine Learning Research , ...

    2019

  13. [21]

    Gelbhart and R

    R. Gelbhart and R. El-Y aniv. The relationship between a gnostic selective classification, active learning and the disagreement coefficient. Journal of Machine Learning Research , 20(33):1–38, 2019. URL http://jmlr.org/papers/v20/17-147.html

    2019

  14. [22]

    Gupte, N

    A. Gupte, N. V afa, and V . V aikuntanathan. Continuous lwe is as hard as lwe & applications to learning gaussian mixtures. In 2022 IEEE 63rd Annual Symposium on F oundations of Computer S cience (FOCS) , pages 1162–

    2022

  15. [23]

    Hainline, B

    J. Hainline, B. Juba, H. S. Le, and D. Woodruff. Conditio nal sparse lp-norm regression with optimal probability. In K. Chaudhuri and M. Sugiyama, editors, Proceedings of the Twenty-Second International Conferenc e on Artificial Intelligence and Statistics , volume 89 of Procee...

    2019

  16. [24]

    Hanczar and E

    B. Hanczar and E. R. Dougherty. Classification with reje ct option in gene expression data. Bioinformatics, 24 (17):1889–1895, 2008

    2008

  17. [25]

    S. Hanneke. The optimal sample complexity of pac learni ng. Journal of Machine Learning Research , 17(38): 1–15, 2016

    2016

  18. [26]

    Haussler

    D. Haussler. Quantifying inductive bias: Ai learning a lgorithms and valiant’s learning framework. Artificial intelligence, 36(2):177–221, 1988

    1988

  19. [27]

    D. Hsu, J. Huang, and B. Juba. Distribution-specific aud iting for subgroup fairness. In 5th Symposium on F oundations of Responsible Computing (FORC 2024). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024

    2024

  20. [28]

    B. Juba. Learning abductive reasoning using random exa mples. Proceedings of the AAAI Conference on Artificial Intelligence , 30(1), Feb. 2016. doi: 10.1609/aaai.v30i1.10099. URL https://ojs.aaai.org/index.php/AAAI/article/view/10099

    2016 doi

  21. [29]

    B. Juba. Conditional sparse linear regression. In 8th Innovations in Theoretical Computer Science Conferenc e (ITCS 2017). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2017

    2017

  22. [30]

    B. Juba, Z. Li, and E. Miller. Learning abduction under p artial observability. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence a nd Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educa tional A...

    2018

  23. [31]

    Kearns, S

    M. Kearns, S. Neel, A. Roth, and Z. S. Wu. Preventing fair ness gerrymandering: Auditing and learning for subgroup fairness. In International conference on machine learning , pages 2564–2572. PMLR, 2018

    2018

  24. [32]

    M. J. Kearns, R. E. Schapire, and L. M. Sellie. Toward effi cient agnostic learning. Machine Learning , 17: 115–141, 1994

    1994

  25. [33]

    J. Khan, J. S. Wei, M. Ringner, L. H. Saal, M. Ladanyi, F. W estermann, F. Berthold, M. Schwab, C. R. Antonescu, C. Peterson, et al. Classification and diagnostic predictio n of cancers using gene expression profiling and artificial neural networks. Nature medicine, 7(6):673–679, 2001

    2001

  26. [34]

    P . K. Kothari, J. Steinhardt, and D. Steurer. Robust mom ent estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theor y of Computing , pages 1035– 1046, 2018

    2018

  27. [35]

    A. Mao, C. Mohri, M. Mohri, and Y . Zhong. Two-stage learn ing to defer with multiple experts. Advances in neural information processing systems, 36, 2024

    2024

  28. [36]

    A. Mao, M. Mohri, and Y . Zhong. Theoretically grounded l oss functions and algorithms for score-based multi- class abstention. In International Conference on Artificial Intelligence and St atistics, pages 4753–4761. PMLR, 2024

    2024

  29. [37]

    A. Mao, M. Mohri, and Y . Zhong. Predictor-rejector mult i-class abstention: Theoretical analysis and algorithms. In C. V ernade and D. Hsu, editors, Proceedings of The 35th International Conference on Algori thmic Learning Theory, volume 237 of Proceedings of Machine Learning...

    2024

  30. [38]

    Mossel and M

    E. Mossel and M. Sudan. Personal communication, 2016

    2016

  31. [39]

    Pugnana and S

    A. Pugnana and S. Ruggieri. Auc-based selective classi fication. In F. Ruiz, J. Dy, and J.-W . van de Meent, editors, Proceedings of The 26th International Conference on Artific ial Intelligence and Statistics , vol- ume 206 of Proceedings of Machine Learning Research , pages 24...

    2023

  32. [40]

    O. Regev. On lattices, learning with errors, random lin ear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009

    2009

  33. [41]

    J. Shen. On the power of localized perceptron for label- optimal learning of halfspaces with adversarial noise. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machin e Learning , volume 139 of Proceedings of Machine Learning Research , p...

    2021

  34. [42]

    Wiener and R

    Y . Wiener and R. El-Y aniv. Agnostic selective classification. Advances in neural information processing systems, 24, 2011

    2011

  35. [43]

    Wiener and R

    Y . Wiener and R. El-Y aniv. Agnostic pointwise-competi tive selective classification. Journal of Artificial Intelli- gence Research, 52:171–201, 2015

    2015

  36. [44]

    Zhang, T

    M. Zhang, T. Mathew, and B. Juba. An improved algorithm f or learning to perform exception-tolerant abduction. In Proceedings of the AAAI Conference on Artificial Intelligen ce, volume 31, 2017. 12 A Review of Robust List Learning of Sparse Linear Classifiers Algorithm 4: Robust...

    2017

  37. [45]

    Now, applying the standard Jacobian matrix that maps the sp herical coordinates to 3-dimensional Cartesian coordinates yield s dx1dx2dx3 = r2 sin φdrdφdθ

    For any xV = ( x1, x2, x3), let φ = θ(xV , e3), θ = θ(xV e⊥ 3 , e1), and r =‖xV‖2, then we have x3 = r cos φ, x1 = r sin φ cos θ, and x2 = r sin φ sin θ. Now, applying the standard Jacobian matrix that maps the sp herical coordinates to 3-dimensional Cartesian coordinates yiel...

  38. [46]

    For the case of θ1∈ [π/2, π], by inequality (5) and‖w− v‖2≥‖ v‖2, we simply have ‖∇wLD(w)−∇ vLD(v)‖2≤ √ π/2≤ 2 ‖v‖2 ‖w− v‖2 which completes the proof by taking L = 2

    and 5/3 < (π/2)3/2. For the case of θ1∈ [π/2, π], by inequality (5) and‖w− v‖2≥‖ v‖2, we simply have ‖∇wLD(w)−∇ vLD(v)‖2≤ √ π/2≤ 2 ‖v‖2 ‖w− v‖2 which completes the proof by taking L = 2. Now we are ready to show the convergence of the gradient norm i n Algorithm 2. Proposition...

  39. [47]

    ‖E(x,y)∼D [gw(x, y)]‖2≤ 1/ √ 2π,

  40. [48]

    occurring of error

    E(x,y)∼D [ ‖gw(x, y)‖2 2 ] ≤ d/2. 17 Proof. To show the first claim, recall that LD(w) = E (x,y)∼D [y· max(0,⟨x, w⟩)] ≤ E x∼Dx [⟨x, w⟩· 1{⟨x, w⟩≥ 0}] (i) =‖w‖2√ 2π ∫ +∞ 0 ze−z2/2dz =‖w‖2√ 2π where inequality (i) holds because x∼N d(0, 1) and, hence,⟨x, ¯w⟩∼N (0, 1). To prove pr...

  41. [49]

    =2err D|S1(Sc 1)Pr{x∈ S1} + Pr{y = 1}− Pr{x∈ S1} (i) =2errD0|S1Pr{x∈ S1} + Pr{y = 1}− Pr{x∈ S1} (ii) ≤ 2 (1 + α) errD0|S′Pr{x∈ S1} + Pr{y = 1}− Pr{x∈ S1} (iii) ≤ 2 (1 + α) errD0|S∗cPr{x∈ S1} + Pr{y = 1}− Pr{x∈ S1} (iv) = 2 (1 + α) errD|S∗c (S∗)Pr{x∈ S1} + Pr{y = 1}− Pr{x∈ S1} ...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.