{"id":"1ffb9e14-1ef7-4da8-a410-4c1ddb4042cb","arxiv_id":"2606.17215","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Christoffel-function resolution principle for reweighted-hinge robust halfspace learning gives SoS degree barriers, a degree-2 outlier limit, and η^{1-1/2t} algorithms.","lead":"The paper characterizes SoS degree barriers for the reweighted-hinge method in robust halfspace learning by showing that the maximum corruption mass hiding from a degree-2t certificate equals the Christoffel function of the clean marginal. This yields explicit margin-degree tradeoffs and an algorithm achieving corruption tolerance η^{1-1/2t}.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"Exact equality in resolution principle hinges on tightness of weighted-Chebyshev reduction (modulo classical estimate)","rationale":"The reader's weakest assumption directly isolates the same point—the well-definedness of λ and the tightness of the weighted-Chebyshev step—that controls whether the central 'exactly' statement holds. Because the full text was not supplied to the initial reader, the current pass confirms rather than relocates the load-bearing assumption; no independent verification of the reduction tightness is visible from the abstract alone.","tokens_in":1913,"tokens_out":377,"duration_ms":19711,"concrete_test":"Re-derive the SoS degree threshold for the dense pancake directly from the definition of the Christoffel function λ_{t+1}(c) (without invoking the weighted-Chebyshev reduction or the classical extremal estimate) and compare the resulting constant factor against the claimed Θ((|c|/s)^2); if the constants differ by more than a (1+o(1)) factor, the exactness of the resolution principle fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim asserts that the maximal hiding mass at c from a degree-2t certificate is exactly λ_{t+1}(c). This equality is obtained by inverting the certificate through the Christoffel function and invoking a weighted-Chebyshev reduction that sets the threshold 2t=Θ((|c|/s)^2) for the pancake. The reduction is stated to be tight only modulo one classical weighted-extremal estimate; if that estimate introduces a non-vanishing gap in the leading constant or fails to be sharp in the high-margin regime, the claimed exact characterization becomes an upper or lower bound rather than equality. The degree-2 barrier instance and the η^{1-1/2t} frontier both inherit this dependence.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims that for the reweighted-hinge method in robust γ-margin halfspace learning under malicious noise, the maximal corruption mass hiding at a center c from a degree-2t SoS certificate is exactly the Christoffel function λ_{t+1}(c) of the clean marginal (the resolution principle). This yields three consequences: a margin-degree tradeoff showing that certifying the dense pancake to error ε requires SoS degree Ω(log(1/ε)) or margin Ω(√log(1/ε)/√d), with the threshold 2t=Θ((|c|/s)^2) obtained via weighted-Chebyshev reduction; an explicit degree-2 barrier instance on which degree 2 is limited to η^{1/2} while degree 4 escapes; and a degree-2t algorithm tracing the frontier η^{1-1/2t} (recovering Shen (2025) at t=1), with explicit constants capped by pancake density and shown unimprovable by the degree-2 barrier.","tokens_in":2062,"tokens_out":496,"duration_ms":34201,"significance":"If the central characterization holds, the work supplies a precise, non-information-theoretic explanation for the degree limitations of certificate-based robust learning by inverting the Christoffel function, which is already used for outlier detection. It gives concrete, falsifiable predictions via the explicit degree-2 instance and the η^{1-1/2t} frontier, recovers prior results at t=1, and isolates the breakdown rate in the degree rather than the analysis. The connection between SoS certificates and Christoffel functions is a notable organizing principle.","major_comments":[{"comment":"The resolution principle asserts exact equality between maximal hiding mass and λ_{t+1}(c). However, the margin-degree tradeoff section states that the weighted-Chebyshev reduction establishing 2t=Θ((|c|/s)^2) is tight only modulo one classical weighted-extremal estimate. If that estimate leaves a non-vanishing gap in the leading constant (particularly in the high-margin regime), the claimed exact characterization becomes an upper or lower bound, which is load-bearing for both the degree-2 barrier instance and the η^{1-1/2t} frontier.","section":"margin-degree tradeoff and resolution principle"}],"minor_comments":[],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and for isolating this subtlety in the relationship between the resolution principle and the weighted-Chebyshev reduction. We address the concern directly below.","responses":[{"response":"The resolution principle is proved directly from the definition of a degree-2t SoS certificate and the reproducing property of the Christoffel function; the equality between maximal hiding mass and λ_{t+1}(c) holds exactly for any fixed marginal and any center c, without reference to margins or the Chebyshev reduction. The weighted-Chebyshev argument appears only in the subsequent margin-degree tradeoff paragraph, where it is used solely to translate the exact hiding-mass bound into an explicit degree threshold 2t=Θ((|c|/s)^2). We already flag that this translation is tight modulo one classical weighted-extremal estimate. In the regimes relevant to the degree-2 barrier instance and the η^{1-1/2t} frontier (fixed small t, pancake distributions with bounded density), the extremal estimate is known to be asymptotically sharp; any constant-factor gap therefore affects only the implicit constant inside the Θ notation and does not turn the exact hiding-mass equality into a one-sided bound. The explicit degree-2 instance is constructed by direct computation of the Christoffel function, again bypassing the reduction. We will insert a short clarifying sentence in the revision that separates the exact resolution principle from the asymptotic translation used only for the tradeoff.","revision_made":"partial","referee_comment":"[margin-degree tradeoff and resolution principle] The resolution principle asserts exact equality between maximal hiding mass and λ_{t+1}(c). However, the margin-degree tradeoff section states that the weighted-Chebyshev reduction establishing 2t=Θ((|c|/s)^2) is tight only modulo one classical weighted-extremal estimate. If that estimate leaves a non-vanishing gap in the leading constant (particularly in the high-margin regime), the claimed exact characterization becomes an upper or lower bound, which is load-bearing for both the degree-2 barrier instance and the η^{1-1/2t} frontier."}],"tokens_in":1697,"tokens_out":453,"duration_ms":25030,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that this work gives a resolution principle: the max corruption mass hiding at a center c from a degree-2t certificate equals the Christoffel function λ_{t+1}(c) of the clean marginal. From there it derives a margin-degree tradeoff, an explicit degree-2 barrier where the method stalls at η^{1/2} while degree 4 escapes, and a general algorithm tracing η^{1-1/2t} (recovering Shen 2025 at t=1).\n\nWhat is new is the Christoffel characterization itself and the concrete degree-2 instance that pins the small breakdown rate on the degree rather than the analysis. The paper does a clean job connecting the reweighted-hinge method to this quantity, which is already standard in outlier detection, and shows how the pancake density caps the gain. The explicit constructions are useful for anyone trying to understand computational limits of certificate methods.\n\nThe soft spot is the tightness claim. The weighted-Chebyshev reduction sets the threshold 2t = Θ((|c|/s)^2) and is called tight only modulo one classical weighted-extremal estimate. If that estimate leaves a gap in the leading constant or is not sharp in the high-margin regime, the claimed exact equality becomes a bound instead. Both the degree-2 barrier and the η^{1-1/2t} frontier inherit this dependence, so the strongest statements rest on that classical piece being sufficiently sharp.\n\nThe rest of the argument looks internally consistent and the citations to prior overlapping work are straightforward since the new principle builds directly on them. No load-bearing circularity.\n\nThis is for people working on SoS certificates in robust learning who want concrete degree barriers rather than information-theoretic ones. A reader already following Shen 2025 or similar certificate approaches will get the most out of the explicit example and the general rate.\n\nIt deserves a serious referee. The explicit barrier and the derived frontier are concrete enough to review even if the exactness of the characterization needs checking against the full derivations.","headline":"The paper turns the Christoffel function into an organizing principle for SoS degree barriers in reweighted-hinge robust halfspace learning and supplies an explicit degree-2 barrier instance.","tokens_in":2546,"tokens_out":500,"would_cite":false,"duration_ms":35098,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The maximal corruption mass hidden from a degree-2t sum-of-squares certificate equals the Christoffel function of the clean marginal at that point.","keywords":["robust halfspace learning","sum-of-squares","Christoffel function","malicious noise","reweighted hinge","outlier removal","margin-degree tradeoff"],"falsifier":"An explicit distribution and corruption set where the mass at some center exceeds λ_{t+1}(c) yet a degree-2t certificate still certifies the pancake to error epsilon, or where the mass is strictly less than λ_{t+1}(c) yet no degree-2t certificate succeeds.","tokens_in":2798,"feed_emoji":"","tokens_out":731,"duration_ms":27958,"temperature":0.7,"pith_summary":"The paper shows that any bounded-degree certificate for removing outliers in robust halfspace learning can only see the data through its low-degree moments, so an adversary can hide corruption exactly where the clean distribution already appears typical. This blind spot has a precise size given by the Christoffel function of the clean marginal, which the authors read as the largest mass a degree-2t certificate necessarily misses. The resulting resolution principle directly governs the reweighted-hinge method, producing a margin-degree tradeoff, an explicit degree-2 barrier, and an algorithm family that traces the frontier eta to the power of 1 minus 1 over 2t.","feed_headline":"Christoffel function fixes exact SoS limit on hidden corruption","feed_subtitle":"Maximal mass evading a degree-2t certificate equals λ_{t+1}(c), forcing either log(1/epsilon) degree or large margins in robust halfspace le","key_machinery":"The Christoffel function λ_{t+1}(c) of the clean marginal, which exactly quantifies the largest corruption mass at c that evades every degree-2t certificate.","core_discovery":"The governing resource is the Sum-of-Squares degree of the outlier-removal certificate, and the resolution principle states that the maximal corruption mass which can hide at a center c from a degree-2t certificate is exactly the Christoffel function λ_{t+1}(c) of the clean marginal.","pith_inferences":["The same Christoffel characterization may bound other moment-based outlier filters that operate only on low-degree statistics.","Practical implementations could trade the explicit constant gain against the cost of solving higher-degree SoS programs on pancake-like data.","Extending the reduction to non-Gaussian marginals would test whether the tightness modulo the classical weighted-extremal estimate survives."],"forward_implications":["Certifying the dense pancake to error epsilon requires SoS degree Omega(log(1/epsilon)) or margin Omega(sqrt(log(1/epsilon))/sqrt(d)).","Degree-2 certificates remain stuck at breakdown rate eta to the power 1/2 while degree-4 certificates escape.","A degree-2t algorithm achieves recovery rate eta to the power 1 minus 1 over 2t, recovering the t=1 case of prior work.","The degree-2 barrier instance shows the small breakdown rate originates in the degree rather than the analysis."],"fun_headline_variants":["Christoffel function sets SoS degree limit on corruption","Resolution links Christoffel to bounded degree certificates","Christoffel governs SoS outlier removal in halfspace learning","SoS degree barrier equals Christoffel lambda of marginal"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The clean marginal admits a well-defined Christoffel function and the weighted-Chebyshev reduction holds with the stated tightness.","fun_headline_variants_meta":{"raw":{"variants":["Christoffel function sets SoS degree limit on corruption","Resolution links Christoffel to bounded degree certificates","Christoffel governs SoS outlier removal in halfspace learning","SoS degree barrier equals Christoffel lambda of marginal"]},"model":"grok-4.3","cost_usd":0.006521,"raw_usage":{"total_tokens":3147,"prompt_tokens":862,"num_sources_used":0,"completion_tokens":64,"cost_in_usd_ticks":65212000,"prompt_tokens_details":{"text_tokens":862,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2221,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":862,"tokens_out":64,"duration_ms":26673,"temperature":1.0,"reasoning_tokens":2221,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-27T03:32:02.344219+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit distribution and corruption set where the mass at some center exceeds λ_{t+1}(c) yet a degree-2t certificate still certifies the pancake to error epsilon, or where the mass is strictly less than λ_{t+1}(c) yet no degree-2t certificate succeeds.","supporting_citations":[],"review_version":1}