{"id":"e5fa98cf-9b71-4cbd-8dbd-761d6e2f5966","arxiv_id":"2601.18115","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A primal-dual algorithm with dual extrapolation learns a single neuron under worst-case group reweighting and arbitrary label noise, with constant-factor competitive error in polynomial time.","lead":"This paper develops a provably efficient algorithm for fitting a single neuron to data from several groups, even when labels are arbitrarily corrupted and group distributions differ. It also tests its dual-reweighting rule on language-model pretraining, where it slightly improves average downstream accuracy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Empirical sharpness bound (3) is used for all w despite Lemma 2.2 restricting it to ∥w−w*∥₂ ≥ √ϵ; the derived two-sided bound (5) is therefore not available near w*, and the gap lower bound in Lemma 3.2 is not proved in that regime.","rationale":"The paper's main contribution is a polynomial-time constant-factor guarantee for a nonconvex neuron under Group DRO. The reader's CONDITIONAL verdict focused on Assumption 1.3 being stronger than prior margin conditions. I partially agree: Assumption 1.3 is a substantive restriction and its coverage of the claimed examples is argued rather than proved. But the most acute, load-bearing problem is internal: the proof uses the empirical sharpness lower bound in a regime where Lemma 2.2 does not provide it. The two-sided bound (5) is presented as a consequence of Lemma 2.2 for every w, although Lemma 2.2's sharpness inequality is explicitly limited to ∥w−w*∥ ≥ √ϵ. Since Lemma 3.2 and the proof of Proposition 3.4 invoke (5) for arbitrary iterates, the contraction argument has a hole near w*. This is not a fatal objection to the central idea — the gap is likely repairable by adding an O(ϵ) slack or by stopping once ∥w_t−w*∥ is small — but as written the theorem is not fully proved. The experimental section is preliminary and does not affect the theoretical claim. Overall, the verdict remains CONDITIONAL: accept only after the proof gap is closed or explicitly patched.","tokens_in":38845,"tokens_out":18791,"duration_ms":176994,"concrete_test":"Re-derive Lemmas 3.2 and Proposition 3.4 using the sharpness inequality (3) only when ∥w_t−w*∥₂ ≥ √ϵ, adding a slack term (e.g., c1ϵ/2) to the gap lower bound when the condition fails. Check whether the final distance bound (9) and risk bound (10) still follow with the stated constants, or with an extra O(√ϵ) term that is absorbed. If the slack term cannot be absorbed under the current step-size schedule (Claim E.4), the theorem's guarantee does not follow from the stated lemmas and the proof must be amended.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof of Theorem 3.1 depends on the two-sided empirical bound (5): c1∥w−w*∥² ≤ E_{bp_i}[(σ(w·x)−σ(w*·x))²] ≤ 6Bβ²∥w−w*∥², stated for any w∈B(W). The upper bound follows from the moment bound (4) and Lipschitzness. The lower bound, however, is obtained by combining the empirical sharpness inequality (3) with the upper moment bound. Lemma 2.2 explicitly states (3) only for all w∈B(3∥w*∥) with ∥w−w*∥₂ ≥ √ϵ. For iterates closer than √ϵ to w*, the uniform-convergence argument in Lemma C.2 gives only an additive error c0ϵ/4, which can exceed c0∥w−w*∥²; therefore (3) — and consequently the lower half of (5) — is not established in that region. This unqualified use of (5) occurs in Lemma 3.2 (Eq. 16), in Lemma E.2 when bounding L(w*,λ_t), and in the telescoping proof of Proposition 3.4. Without the c1∥w−w*∥² term in the gap lower bound for small distances, the contraction inequality (7) does not follow for all iterates, and the induction in Lemma 3.3 that keeps w_t in B(3∥w*∥) is not fully justified. This is an internal proof gap, independent of the (also strong) Assumption 1.3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies learning a single neuron under squared loss with arbitrary label noise and group-level distributional shifts, formulated as a Group DRO problem with an f-divergence penalty on the group weights. The main contribution is a primal-dual algorithm (Algorithm 1) with extrapolation on the dual variable, together with a theoretical guarantee (Theorem 3.1): under a subexponential-tail assumption and a uniform margin assumption, the algorithm returns a weight vector that is constant-factor competitive with the optimal worst-group loss, with polynomial sample and iteration complexity. The paper also reports a small-scale LLM pretraining experiment comparing the proposed dual update with DoReMi/Sheared-LLaMA. If the proof is correct, this is the first polynomial-time constant-factor learner for a nonconvex neuron in a Group DRO setting with arbitrary label noise.","tokens_in":1690,"tokens_out":1963,"duration_ms":95151,"significance":"The result is significant: it extends the line of work on robustly learning a single neuron to a Group DRO setting, removes several restrictions of the prior work [LKDD24] (higher-moment assumptions, mandatory large regularization, restriction to chi-squared divergence), and proposes a dual-extrapolation scheme that is more memory-efficient in large-scale applications. The proof strategy, based on a linearization lemma and a sharpness-based gap argument, is a reasonable route to the claimed guarantee. However, the proof as written has load-bearing gaps: the empirical sharpness bound is stated beyond the regime in which it is proved, the uniform margin assumption is substantially stronger than in prior work and is not verified for the claimed distribution family, and one induction step relies on an external claim from [LKDD24] without a self-contained argument. These issues affect the central convergence theorem and must be repaired before the main claim can be accepted.","major_comments":[{"comment":"Lemma 2.2 establishes the empirical sharpness inequality (3) only for all w with ||w - w*||_2 >= sqrt(epsilon). The two-sided bound (5), however, is stated for any w in B(W) and its lower half is derived from (3). This unrestricted form is then used in Lemma 3.2 (Eq. (16)), in Lemma E.2, and in the telescoping proof of Proposition 3.4. For iterates within sqrt(epsilon) of w*, the lower bound c1 * ||w - w*||^2 is not justified, so the gap lower bound and the contraction inequality (7) are not established in that regime. This is an internal proof gap, independent of Assumption 1.3. The authors should either extend Lemma 2.2 to the small-distance regime, or provide a separate argument showing that the quantities in question can be controlled there.","section":"Section 2, Eq. (5)"},{"comment":"The uniform margin condition requires the covariance lower bound E[xx^T 1{w·x >= gamma ||w||_2}] >= zeta I_d for every w and every group. This is much stronger than the margin conditions in [WZDD23, LKDD24], which are only imposed at the target w*. The paper states that the condition holds for standard distributions because their definitions do not involve w*, but this is a plausibility argument rather than a proof. The sharpness bounds in Fact 2.1 and Lemma 2.2 are applied to every iterate w_t, so Assumption 1.3 is load-bearing. The authors should either prove the uniform margin property for the full claimed family of distributions, or explicitly restrict the theorem to a subclass for which it is verified.","section":"Assumption 1.3"},{"comment":"The proof of Lemma 3.3 invokes 'claim E.2 in [LKDD24]' for a WLOG normalization that is used to conclude ||w_{n+1}||_2 <= 3||w*||_2. Since this bootstrap step is essential to keep the iterates inside the region where all previous sharpness lemmas apply, the argument is not self-contained as written. In addition, in the proof of Theorem 3.1 the text uses the high-probability bound \\hat{OPT}_m <= 3(OPT_m + epsilon), but Lemma C.3 states only \\hat{OPT}_m <= OPT_m + epsilon. These discrepancies must be reconciled and the cited claim either stated explicitly or proved within the paper.","section":"Section 3.5 and Lemma 3.3"},{"comment":"The introduction claims that the algorithm attains sample complexity O-tilde(Kd/epsilon^2), 'matching the known optimal rate' for convex unregularized Group DRO. Theorem 3.1, however, states N = O-tilde_{beta,B,nu}(K W^4 d/epsilon^2 log(1/delta)), with an explicit W^4 factor and additional hidden dependencies on beta, B, and nu. Unless W, beta, B, nu are treated as universal constants, this does not match the cited optimal rate. The claim should be weakened or the comparison made precise.","section":"Section 1.2 and Theorem 3.1"}],"minor_comments":[{"comment":"The truncation operation is written as y' = sign(y) max{|y|, M}; this increases the magnitude of y and does not truncate. It should presumably be sign(y) min{|y|, M}. Please correct the formula and confirm that the subsequent arguments use the truncated labels.","section":"Fact 2.3"},{"comment":"The informal statement says the learner is provided with O-tilde(...) samples 'from each' group, while Theorem 3.1 gives a total sample size N. Please state per-group versus total sample size consistently.","section":"Section 1.2 / Theorem 3.1"},{"comment":"In the related-work paragraph, the citation list '[MMR09, PY09, BDBC+10 PGLC15, TSK+18]' is missing a comma between '[BDBC+10]' and '[PGLC15]'.","section":"Appendix A"},{"comment":"The claim that 'DoReMi requires at least 1.5x more training time to achieve the same accuracy' is not supported by the displayed figure or the experimental setup, which reports accuracy versus tokens, not wall-clock time. Please clarify or remove this claim.","section":"Section 4.1 / Figure 1"},{"comment":"The approximation constant C3 = 31*beta*sqrt(B)/c1 depends on beta, B, and c1. The introduction and Problem 1.5 describe the constant as 'universal' and 'independent of d, K, W, epsilon, nu', which is misleading if these distribution-dependent parameters are not bounded. The statement should be qualified accordingly.","section":"Theorem 3.1, constants"}],"recommendation":"major_revision","confidential_remarks":"The central idea is promising and the paper addresses an important gap in the literature. The main barrier is the empirical-sharpness regime issue around Eq. (5) and the reliance on the unverified uniform margin assumption; these are fixable but require real technical work. I would encourage the editor to send the paper back for a major revision rather than reject it, assuming the authors can supply the missing arguments. The experimental section is not essential to the theoretical contribution and could be shortened without affecting the core paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about arXiv:2601.18115. First, it gives the first provably polynomial-time constant-factor learner for a single neuron under group-level distribution shifts with arbitrary label noise, and the dual-side extrapolation idea is a real step beyond [LKDD24]. Second, the proof as written has a load-bearing gap: the two-sided bound (5) is derived from empirical sharpness Lemma 2.2, which only holds for ∥w−w*∥ ≥ √ε, yet (5) is then applied at all distances, including near w*, in Lemma 3.2 and Lemma E.2. Without the c1∥w−w*∥² lower bound in that regime, the gap lower bound and the contraction inequality do not follow. The stress-test note is correct on this point.\n\nWhat is actually new: the Group DRO formulation with f-divergence penalty, ν=0 allowed, KL and χ² divergences, removal of higher-moment assumptions, and a linearization lemma that makes dual extrapolation tractable for a nonconvex loss. That is a substantial contribution to the robust-learning literature, and the high-level approach is credible.\n\nWhere the soft spots are: (1) the small-distance gap described above; (2) Assumption 1.3 (Uniform Margin for every w) is much stronger than the w*-only margin in prior work, and the paper justifies it by examples rather than proof over the claimed family—genuinely load-bearing; (3) the intro's claim of sample complexity matching the known optimal rate hides the W^4 factor and parameter dependencies that appear in Theorem 3.1; (4) the proof of Lemma 3.3 explicitly defers to a claim in [LKDD24] without derivation, and Appendix D says it 'adapts techniques' from the same source. None of these by themselves make the central claim implausible, but they mean the theorem as stated is not fully proven in this version.\n\nThe experiments are illustrative and the authors say as much; they do not add real evidence either way.\n\nWho is this for: theorists working on robust learning, nonconvex DRO, and provable guarantees for simple neural networks. A serious referee should engage—the result is important and the gaps look patchable, but the proof needs real work before the claims are taken at face value.","headline":"Genuinely new algorithmic result for nonconvex Group DRO, but the proof has a real gap near w* and leans heavily on self-cited prior work; worth a serious referee.","tokens_in":39736,"tokens_out":2865,"would_cite":false,"duration_ms":30777,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Under a uniform margin condition, a primal-dual algorithm with extrapolated group weights learns a single neuron with constant-factor worst-case loss using \\tilde{O}(Kd/ε²) samples, even under arbitrary label noise and group shifts.","keywords":["single neuron","Group DRO","arbitrary label noise","distributional shift","primal-dual algorithm","dual extrapolation","nonconvex optimization","constant-factor approximation"],"falsifier":"Construct a covariate distribution that satisfies subexponential tails (Assumption 1.2) but has a narrow low-density region such that for some direction w, E[xx^T I{w·x ≥ γ||w||}] is not positive definite with the required ζ; run Algorithm 1 on K=1 group with realizable labels and check whether the distance bound ||w_n−w*|| ≤ C_3(√OPTm+√ε) still holds. If it fails, Assumption 1.3 is necessary as stated.","tokens_in":38658,"feed_emoji":"🧠","tokens_out":6400,"duration_ms":65520,"temperature":0.7,"pith_summary":"This paper tackles learning a single neuron (σ(w·x)) under squared loss when labels can be arbitrarily corrupted and data come from K groups with distribution shifts. It aims to output a weight vector whose worst-case loss over convex mixtures of the groups is within a constant factor of the optimal robust neuron's loss. The central claim is that a primal-dual algorithm with extrapolation on the low-dimensional group weights achieves this with near-optimal sample complexity, matching the convex Group DRO rate up to log factors. The proof handles the nonconvexity through a linearization lemma and a uniform sharpness condition. A motivating LLM pretraining experiment suggests the dual-extrapolation update provides practical stability gains.","feed_headline":"Polynomial-time constant-factor learner for Group DRO neurons","feed_subtitle":"Primal-dual algorithm matches convex Group DRO sample complexity, handles arbitrary label noise.","key_machinery":"The analysis centers on a primal-dual gap function Gap(w,λ) = L(w,λ*) − L(w*,λ) with a hybrid reference: population-optimal w* and empirical worst-case λ*. The lower bound on the gap comes from empirical sharpness (Lemma 2.2), while the upper bound is derived from the algorithm's updates; the key technical step is a 'linearization' lemma (Lemma 3.5) that replaces the nonconvex squared loss with an inner product using the surrogate gradient 2β(σ(w·x)−y)x plus controlled error terms. This linearization permits extrapolation on the dual variable λ (which may become negative) without breaking convexity, and removes the need for a nonzero regularization parameter ν.","core_discovery":"The paper claims its Algorithm 1 is the first computationally efficient method with provable constant-factor guarantees for a nonconvex neuron in a Group DRO setting with arbitrary label noise. Concretely, under Assumptions 1.2 and 1.3, with N = \\tilde{O}(K W^4 d/ε^2 log(1/δ)) samples, the output w_n satisfies ||w_n − w*||_2 ≤ C_3(√OPTm + √ε) and the expected loss under the worst-case mixture p* is at most (2 + 20Bβ²C_3²)OPTm + 20β²C_3² Bε, where C_3 is a constant independent of d, K, W, ε, ν. This matches the optimal sample complexity for convex unregularized Group DRO up to log factors, and the algorithm reaches this in O(K/ε) iterations, each running in near-linear time.","pith_inferences":["The uniform margin assumption is the bottleneck: if it could be relaxed to holding only near the optimum (as in previous single-neuron work), the algorithm would likely cover a wider class of marginals; the current proof needs it at every iterate.","The constant factor C_3 depends on the sharpness constant c1; for activations like ReLU these are benign, but the factor may become large for ill-conditioned problems, so the practical competitiveness of the constant is an open question.","The LLM pretraining result is a proof-of-concept at modest token counts; a natural testable extension is to compare the dual-extrapolation update against current state-of-the-art domain reweighting baselines at full pretraining scale.","Dual extrapolation might transfer to other nonconvex-concave minimax problems where the dual is low-dimensional; the linearization technique is a new tool for such settings."],"forward_implications":["If the theorem holds, Group DRO for nonconvex models is no longer limited to stationary-point guarantees; a constant-factor approximation is achievable with polynomial time and near-optimal samples.","The dual-extrapolation design is memory-efficient (the extrapolated variable has dimension K, not d), so it can be combined with off-the-shelf optimizers like Adam in large-scale training.","The ν→0 regime connects the regularized robust formulation to classical Group DRO without penalty, and the result applies to both KL and χ² divergences.","The sample complexity \\tilde{O}(Kd/ε²) means robustness to worst-case group reweighting costs essentially no extra samples over the convex case."],"fun_headline_variants":["First constant-factor guarantees for nonconvex Group DRO","Robust single-neuron learning under worst-case group shifts","Primal-dual method matches convex Group DRO sample complexity","Arbitrary label noise handled in Group DRO neuron learning","Efficient algorithm for nonconvex group-robust neuron"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is the uniform margin condition (Assumption 1.3): for every group and every weight vector w, the covariance inside the region {x : w·x ≥ γ||w||} must be uniformly well-conditioned; if some iterate w_t violates this, the empirical sharpness lemma fails and the convergence proof collapses.","fun_headline_variants_meta":{"raw":{"variants":["First constant-factor guarantees for nonconvex Group DRO","Robust single-neuron learning under worst-case group shifts","Primal-dual method matches convex Group DRO sample complexity","Arbitrary label noise handled in Group DRO neuron learning","Efficient algorithm for nonconvex group-robust neuron"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000456,"raw_usage":{"total_tokens":2198,"prompt_tokens":889,"completion_tokens":1309,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":1225}},"tokens_in":633,"tokens_out":1309,"duration_ms":10657,"temperature":1.0,"reasoning_tokens":1225,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T08:06:21.379852+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a covariate distribution that satisfies subexponential tails (Assumption 1.2) but has a narrow low-density region such that for some direction w, E[xx^T I{w·x ≥ γ||w||}] is not positive definite with the required ζ; run Algorithm 1 on K=1 group with realizable labels and check whether the distance bound ||w_n−w*|| ≤ C_3(√OPTm+√ε) still holds. If it fails, Assumption 1.3 is necessary as stated.","supporting_citations":[],"review_version":1}