{"id":"5a84dab4-751c-4f83-96f4-4de77d9de271","arxiv_id":"2606.01554","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Proposes a polynomial-time algorithm for near-optimal Euclidean estimation over symmetric norm balls with oracle access, extended to random-design linear regression.","lead":"The paper proposes a polynomial-time algorithm for near-optimal estimation of a signal inside the unit ball of a symmetric norm, using an oracle for the norm, and extends it to linear regression with similar constraints. This could enable faster constrained estimation in statistical and signal processing tasks where norms have symmetry properties.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader correctly flags that only the abstract is visible, which prevents any deeper technical audit. No load-bearing flaw can be located from the given text, so the UNVERDICTED verdict stands.","tokens_in":1540,"tokens_out":228,"duration_ms":16775,"concrete_test":"Obtain the full manuscript and verify that the algorithm description (including any reduction or rounding step) runs in poly(n, log(1/ε)) time under the stated oracle model; confirm the near-optimality guarantee matches the information-theoretic lower bound derived in the paper.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the existence of a polynomial-time algorithm achieving near-optimal Euclidean estimation for signals in the unit ball of a symmetric norm (known basis, oracle access), with an extension to random-design regression. The abstract states the setting and claim directly; no internal inconsistency, hidden assumption, or unsupported step is visible in the provided description. The oracle-access and known-basis conditions are explicit and standard for such oracles.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"This short note proposes a polynomial-time algorithm for near-optimal Euclidean estimation of a signal constrained to lie in the unit ball of a symmetric norm, where the symmetry is with respect to a known basis and the norm is accessible through an evaluation oracle. It further extends the method to a random-design, moderate-dimensional linear regression setting where the regression parameter belongs to a similar constraint set.","tokens_in":1599,"tokens_out":259,"duration_ms":13634,"significance":"If the claimed polynomial-time near-optimal algorithm can be established with the stated oracle access, the result would provide an efficient approach to Euclidean estimation under symmetric norm balls, which could be relevant for constrained estimation problems in statistics. The extension to random-design regression broadens potential applicability. However, the absence of algorithm details, proofs, or empirical validation in the provided abstract prevents a full assessment of whether the math supports the near-optimality claim.","major_comments":[{"comment":"The abstract states the existence of a polynomial-time algorithm achieving near-optimal rates but provides no description of the algorithm, no derivation of the rates, and no analysis of computational complexity or statistical error bounds. Without these elements, the central claim cannot be verified.","section":null}],"minor_comments":[],"recommendation":"uncertain","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their review. We address the single major comment below.","responses":[{"response":"We agree that the abstract is concise and omits algorithmic details, rate derivations, and complexity/error analysis, which are instead developed in the body of the short note. The full manuscript constructs the polynomial-time procedure via the symmetric-norm oracle, derives the near-optimal Euclidean rates, and analyzes both computational complexity and statistical bounds. To improve accessibility, we will revise the abstract to include a brief outline of the algorithm and the key ideas underlying the near-optimality claim.","revision_made":"yes","referee_comment":"The abstract states the existence of a polynomial-time algorithm achieving near-optimal rates but provides no description of the algorithm, no derivation of the rates, and no analysis of computational complexity or statistical error bounds. Without these elements, the central claim cannot be verified."}],"tokens_in":1101,"tokens_out":204,"duration_ms":23894,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's core contribution is a polynomial-time algorithm that achieves near-optimal Euclidean estimation for a signal inside the unit ball of a symmetric norm, using only an evaluation oracle and a known basis for the symmetry. It then carries the same idea over to random-design linear regression where the parameter is similarly constrained.\n\nWhat stands out is the focus on the oracle-access model for symmetric norms. That framing lets the method handle norms that are easy to evaluate but hard to optimize over directly, and the regression extension keeps the same flavor. If the analysis goes through cleanly, this could be a practical addition for moderate-dimensional problems where people already use norm balls as constraints.\n\nThe main soft spot is that this is a short note. The abstract states the claim directly, but without the full proofs or any numerical checks it is difficult to judge how tight the near-optimality constants are or whether the runtime hides large factors. The symmetry and oracle assumptions are stated up front, so there is no hidden circularity there, but the paper will need to show that the reduction or rounding step actually delivers the stated rates.\n\nThis is aimed at researchers who work on constrained high-dimensional estimation or who need to optimize over custom symmetric norms. A reader already familiar with oracle models and norm balls will get the most out of it.\n\nI would send it to referees. The setting is concrete, the algorithmic claim is new on its face, and the work is short enough that a careful review can decide quickly whether the details hold.","headline":"Short note gives a poly-time oracle algorithm for near-optimal estimation under symmetric norm balls and extends it to moderate-dim regression; looks like a useful algorithmic tool but details matter.","tokens_in":2039,"tokens_out":384,"would_cite":false,"duration_ms":11403,"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":"A polynomial-time algorithm performs near-optimal Euclidean estimation for signals in symmetric norm unit balls using an oracle.","keywords":["symmetric norms","estimation","polynomial time","oracle access","linear regression","Euclidean distance","unit ball"],"falsifier":"A counterexample symmetric norm where any polynomial-time algorithm fails to achieve the near-optimal Euclidean estimation rate would disprove the main claim.","tokens_in":2438,"feed_emoji":"","tokens_out":475,"duration_ms":21973,"temperature":0.7,"pith_summary":"The paper develops a polynomial-time method to estimate a signal known to lie inside the unit ball of a symmetric norm. Symmetry is taken with respect to a known basis and the norm is accessed only through an evaluation oracle. The approach achieves rates near-optimal in Euclidean distance. It extends the method to a linear regression setting with random design where the parameter satisfies the same norm constraint.","feed_headline":"Poly-time algo near-optimally estimates in symmetric norm balls","feed_subtitle":"Uses an evaluation oracle for the norm and extends to linear regression with random design.","key_machinery":"The polynomial-time algorithm that leverages the evaluation oracle for the symmetric norm to achieve near-optimal estimation rates.","core_discovery":"There exists a polynomial-time algorithm for near-optimal Euclidean estimation of a signal in the unit ball of a symmetric norm, with the symmetry relative to a known basis and the norm given by an evaluation oracle. The method extends to moderate-dimensional linear regression under random design.","pith_inferences":["This approach might generalize to other norm-constrained estimation tasks beyond those discussed.","Future work could test the method on specific symmetric norms like the l1 or l-infinity norms to verify practical performance."],"forward_implications":["The algorithm enables efficient computation for estimation problems involving various symmetric norms without needing explicit descriptions.","It applies directly to constrained linear regression with the same type of norm ball.","Near-optimal rates are achieved in polynomial time rather than requiring potentially slower methods."],"fun_headline_variants":["Poly-time near-optimal estimation over symmetric norm balls","Near-optimal Euclidean signal estimation in symmetric norm balls","Algorithm for symmetric norm ball estimation runs in poly time","Poly-time extension to random-design linear regression with norms"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The norm is symmetric with respect to a known basis and accessible only through an evaluation oracle.","fun_headline_variants_meta":{"raw":{"variants":["Poly-time near-optimal estimation over symmetric norm balls","Near-optimal Euclidean signal estimation in symmetric norm balls","Algorithm for symmetric norm ball estimation runs in poly time","Poly-time extension to random-design linear regression with norms"]},"model":"grok-4.3","cost_usd":0.006205,"raw_usage":{"total_tokens":2827,"prompt_tokens":475,"num_sources_used":0,"completion_tokens":59,"cost_in_usd_ticks":62049500,"prompt_tokens_details":{"text_tokens":475,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2293,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":475,"tokens_out":59,"duration_ms":15881,"temperature":1.0,"reasoning_tokens":2293,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T12:34:47.874156+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A counterexample symmetric norm where any polynomial-time algorithm fails to achieve the near-optimal Euclidean estimation rate would disprove the main claim.","supporting_citations":[],"review_version":1}