{"id":"387d3e6d-43be-418a-b4b5-8ba280957a8b","arxiv_id":"2502.00172","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Agnostic conditional classification with homogeneous halfspace selectors on Gaussian data can be solved with O(sqrt(opt)) error, while general halfspaces are computationally hard under cLWE.","lead":"This paper gives the first algorithm for agnostic conditional classification with homogeneous halfspace selectors under Gaussian features, achieving error O(sqrt(opt)) when the optimal error opt is very small. It also shows that for general halfspaces, approximating conditional classification is as hard as agnostic classification, under cryptographic assumptions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main theorem's 'sufficiently small ε' is unquantified, and the proof's gradient-threshold step only goes through for ε below a threshold the statement never specifies.","rationale":"The paper's positive algorithm is carefully constructed and most of the proof chain—relative smoothness, projected SGD convergence, concentration, and the reduction to list-learnable classes—is coherent. The central finite-class theorem is plausible, and the negative reduction appears to reduce agnostic halfspace classification to conditional classification with a singleton classifier class, so the two main claims are not obviously contradictory. The most significant weakness I find is not the standard-normal marginal, which the authors explicitly disclose as a limitation and which is part of the problem's definition, but rather the unquantified 'sufficiently small ε' in Theorem 3.1. This is not merely a stylistic caveat: the proof uses the same symbol ε for the assumed optimal joint error and for the SGD convergence target, but the transition Lemma C.5→Corollary C.4 requires the gradient norm to be below (2/5)ε√ln(1/ε), which is only guaranteed by Proposition B.2 when ε is below an unstated constant (roughly e^{-25/4}). Consequently, the advertised O(√opt) approximation is proven only for opt below that threshold. The reader's rationale already flagged the unquantified ε, so my read partially agrees with the reader's conditional verdict, although I do not regard the standard-normal x-marginal as the decisive issue: it is a disclosed scope restriction, not a hidden correctness gap. A concrete re-derivation of the constants would settle whether the stated Theorem 3.1 needs an explicit ε₀ or a modified T,N, and the result would remain unchanged in spirit.","tokens_in":35401,"tokens_out":45612,"duration_ms":476624,"concrete_test":"Re-derive Lemma C.5 and Proposition C.2 while tracking all universal constants, and determine the explicit value ε₀ such that the chain ‖E[g]‖₂ ≤ ε ⇒ (2/5)ε√ln(1/ε) ⇒ Pr{x∈h(w)∩y=1} ≤ (5/2)(ε√ln(1/ε))^{1/2} is valid for all ε ≤ ε₀. Check whether ε₀ ≈ e^{-25/4}; then verify that with T = c(4d + ln(1/δ)) / (ε₀₂)^4, where ε₀₂ = (2/5)ε√ln(1/ε), the same proof goes through for all ε∈(0,1/e]. If the threshold is not universal or is much smaller than e^{-25/4}, Theorem 3.1's stated range must be restricted accordingly.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 3.1 is stated for 'some sufficiently small ε∈[0,1/e]', but the proof of Lemma C.5 contains a concrete threshold mismatch. Proposition B.2 guarantees a returned w with ‖E[g_w]‖₂ ≤ ε, while Corollary C.4 requires ‖E[g_w]‖₂ < (2/5)ε√ln(1/ε) before its error bound applies. The implication ‖E[g_w]‖₂ ≤ ε ⇒ ‖E[g_w]‖₂ < (2/5)ε√ln(1/ε) holds only when ε ≤ e^{-25/4} ≈ 0.00193, not for the full interval [0,1/e]. Proposition C.2's proof imposes additional small-ε inequalities (e.g., the integration-by-parts constant in (11) requires 4eπε√ln(1/ε) ≤ 1.59, which is also false near ε=1/e). Thus the theorem, as written, covers only distributions whose optimal joint conditional error is below an unstated universal constant. Since the abstract and contribution claim an O(√opt) approximation, this hidden threshold is load-bearing: for opt ≈ 0.01—still a small error—no guarantee is proven. The fix is not deep (one can run Proposition B.2 with target η=(2/5)ε√ln(1/ε) and adjust the absolute constants in Algorithm 1), but the statement must be corrected and quantified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":35671,"tokens_out":13085,"duration_ms":127476,"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":[{"comment":"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.","section":"Theorem 3.1, Lemma C.5, Corollary C.4, Proposition C.2"},{"comment":"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.","section":"Appendix D, proof of Theorem 3.5"}],"minor_comments":[{"comment":"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\".","section":"Title page and Lemma B.1"},{"comment":"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.","section":"Theorem 4.3"},{"comment":"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.","section":"Claim E.4, Case II"},{"comment":"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.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The threshold gap in the positive theorem is the main obstacle to acceptance; it is specific, localized, and fixable within the scope of a revision. The hardness reduction appears sound and the paper is a good fit for a theory-of-learning venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper is worth reading and deserves a serious referee, but the main theorem as written overstates its own range. The positive result is genuinely new—projected SGD on a one-sided ReLU surrogate gives the first provable O(sqrt(opt)) approximation for agnostic conditional classification with homogeneous halfspace selectors under standard normal marginals. The reduction in Proposition 4.5, showing conditional classification is at least as hard as agnostic classification, is clean and real. The appendices contain actual proofs, not sketches; Lemma B.1's relative smoothness bound and the convergence analysis in Proposition B.2 are non-trivial and mostly check out.\n\nThe soft spot is exactly where the stress-test lands. Theorem 3.1 and Lemma 3.4 say 'some sufficiently small epsilon in [0,1/e]', but the proof chain does not go through near 1/e. Proposition B.2 gives a w with ||E[g_w]|| <= epsilon, while Corollary C.4 needs ||E[g_w]|| < (2/5) epsilon sqrt(ln(1/epsilon)) before its error bound applies. That implication holds only for epsilon <= e^{-25/4} ~ 0.00193, not on [0,1/e]. The integration-by-parts constant in (11) requires 4e*pi*epsilon*sqrt(ln(1/epsilon)) <= 1.59, also false near 1/e. So the claimed O(sqrt(opt)) guarantee is proven only for opt below an unstated universal constant. For opt ~ 0.01 the paper proves nothing. This is not a deep flaw—re-running Proposition B.2 with target eta = (2/5) epsilon sqrt(ln(1/epsilon)) and adjusting absolute constants fixes it—but the statements and abstract need to be corrected. As written, the abstract's 'first PAC-learning algorithm with error guarantee O(sqrt(opt))' is only established for a narrow, unnamed regime.\n\nThe Gaussian marginal assumption is structural, not cosmetic: the proof uses exact halfspace measure 1/2 and Gaussian anti-concentration. The paper acknowledges this in Section 5, which is honest. Sparse linear classifiers are handled via list learning, which is a good move.\n\nThe hardness side is standard: cLWE-based, with a genuine reduction. No circularity issues.\n\nBottom line: this is a serious paper by people who know the area. The main theorem needs a quantified threshold and a fix to the epsilon range; after that, it's a solid contribution. Send it to referees, but the referees should demand the quantification.","headline":"A genuinely new algorithmic result with a real but fixable gap in the main theorem's epsilon quantification; deserve a serious referee.","tokens_in":36208,"tokens_out":1992,"would_cite":true,"duration_ms":18825,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05","62H30","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["conditional classification","selective classification","homogeneous halfspaces","agnostic learning","Gaussian marginals","PAC learning","projected SGD","learning with errors"],"falsifier":"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.","tokens_in":35167,"feed_emoji":"🎯","tokens_out":13783,"duration_ms":121765,"temperature":0.7,"pith_summary":"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.","feed_headline":"Selective classification gets its first PAC-style guarantee","feed_subtitle":"Under Gaussian features, halfspace selectors achieve O(√opt) error; general halfspaces are hard under cLWE.","key_machinery":"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).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the distribution-specific hardness of agnostically learning halfspaces under Gaussian marginals that Theorem 4.3 reduces from.","marker":"[13]"},{"why":"Provides the projected-SGD and correlation-improvement techniques that Proposition 3.3 and the angle-contraction argument rely on.","marker":"[10]"},{"why":"The robust list-learning method for sparse linear classifiers that Theorem 3.5 invokes to reduce an infinite class to a finite list.","marker":"[29]"},{"why":"The observation, attributed to Mossel and Sudan, that the robust-regression approach yields list learning; Algorithm 4 implements it.","marker":"[38]"},{"why":"Establishes that continuous LWE is as hard as LWE, the cryptographic base of the hardness assumption in Theorem 4.3.","marker":"[22]"},{"why":"Supplies the bounded-differences concentration inequality used to convert the expected gradient-norm bound into the high-probability statement in Proposition 3.3.","marker":"[8]"},{"why":"The correlation-improvement lemma used to prove that the angle to the optimal halfspace contracts under the projected gradient update.","marker":"[9]"}],"fun_headline_variants":["First PAC guarantee for conditional classification","O(√opt) error for halfspace selectors under Gaussians","Conditional classification: PAC bound and crypto hardness","Agnostic selective classification gains PAC-style bounds","Halfspace selectors: O(√opt) guarantee, crypto lower bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["First PAC guarantee for conditional classification","O(√opt) error for halfspace selectors under Gaussians","Conditional classification: PAC bound and crypto hardness","Agnostic selective classification gains PAC-style bounds","Halfspace selectors: O(√opt) guarantee, crypto lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000833,"raw_usage":{"total_tokens":3710,"prompt_tokens":1091,"completion_tokens":2619,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":707,"completion_tokens_details":{"reasoning_tokens":2540}},"tokens_in":707,"tokens_out":2619,"duration_ms":19698,"temperature":1.0,"reasoning_tokens":2540,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T19:57:45.448316+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Diakonikolas, D","cited_arxiv_id":null,"evidence_quote":"Supplies the distribution-specific hardness of agnostically learning halfspaces under Gaussian marginals that Theorem 4.3 reduces from."},{"cited_title":"Diakonikolas, V","cited_arxiv_id":null,"evidence_quote":"Provides the projected-SGD and correlation-improvement techniques that Proposition 3.3 and the angle-contraction argument rely on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The robust list-learning method for sparse linear classifiers that Theorem 3.5 invokes to reduce an infinite class to a finite list."},{"cited_title":"Mossel and M","cited_arxiv_id":null,"evidence_quote":"The observation, attributed to Mossel and Sudan, that the robust-regression approach yields list learning; Algorithm 4 implements it."},{"cited_title":"Gupte, N","cited_arxiv_id":null,"evidence_quote":"Establishes that continuous LWE is as hard as LWE, the cryptographic base of the hardness assumption in Theorem 4.3."},{"cited_title":"Devroye and G","cited_arxiv_id":null,"evidence_quote":"Supplies the bounded-differences concentration inequality used to convert the expected gradient-norm bound into the high-probability statement in Proposition 3.3."},{"cited_title":"A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise","cited_arxiv_id":"2010.01705","evidence_quote":"The correlation-improvement lemma used to prove that the angle to the optimal halfspace contracts under the projected gradient update."}],"review_version":1}