{"id":"aacecddc-8644-4d14-8d8f-666a620e24a6","arxiv_id":"2507.07132","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The shape of local averaging regions, not just their size, determines whether a local regression estimator achieves the minimax rate, and a single condition called shape regularity is both necessary and sufficient.","lead":"Local regression methods that average nearby response values can only reach statistically optimal accuracy if their averaging regions are shape regular, roughly cube-like or ball-like rather than long and thin. This paper proves that shape regularity is necessary and sufficient for minimax rates and uses it to analyze nearest neighbors, prototype methods, CART-like trees, and Mondrian forests.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 can create leaves with fewer than m points, so Theorem 18's variance bound is not guaranteed.","rationale":"The reader's verdict was CONDITIONAL, and it correctly flagged the Section 5.3 issue about S_β(V). My stress test identifies a sharper failure: even when S_β(V) is nonempty, the fallback in Algorithm 1 can produce a child with fewer than m points, so the leaf-size invariant nP_n(V)≥m used in Theorem 18 is not guaranteed. This is a concrete counterexample to the proof, not merely an overstatement of a universal claim. However, the central shape-regularity theorem (Theorem 12 and Proposition 10) is not affected, and the CART-like construction is likely repairable by changing the fallback rule or the stopping condition. I therefore keep the reader's CONDITIONAL verdict unchanged. The main unaddressed limitation remains the minimal mass assumption (X) for the sufficiency direction, but that is a stated condition rather than an internal inconsistency. My agreement is partial because the reader identified a related but less precise flaw in the same section, not the specific violation of S_m by the fallback split.","tokens_in":44746,"tokens_out":19843,"duration_ms":236354,"concrete_test":"Run Algorithm 1 with d=2, β=2, m=10 on the 30-point configuration with 12 points at (0.1,0.1), 10 at (0.45,0.45), and 8 at (0.9,0.9). For the root cell, verify that S_m is nonempty (the x-split at u=0.3 gives 12 and 18 points) but S_β∩S_m is empty (for β=2, S_β contains only the u=1/2 split, which gives 22 and 8 points). The algorithm's fallback then produces a leaf with 8 points, violating the nP_n(V)≥m condition used in the proof of Theorem 18. If the algorithm is patched to avoid such splits, check whether the final leaves still satisfy the stated 2m≥nP_n(V)≥m invariant used in the theorem.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 5.3, Algorithm 1 splits a cell whenever S_m(V) is nonempty, even if no β-shape-regular split has enough points. Step (a) says: if the argmin over S_β(V) ∩ S_m(V) has no solution, 'just pick p as the largest side and u = 1/2'. This fallback is not checked against S_m. Concretely, take d=2, β=2, m=10, and a root cell [0,1]^2 containing 12 points at (0.1,0.1), 10 at (0.45,0.45), and 8 at (0.9,0.9). For the cube, S_β contains only the middle split (any u≠1/2 gives a child with side ratio >2). The middle split along either coordinate puts 22 points in one child and 8 in the other, so it is not in S_m. But the split at u=0.3 along x gives children with 12 and 18 points, so S_m is nonempty. Hence S_β∩S_m=∅, the algorithm falls back to the middle split, and the final partition contains a leaf with only 8<m points. The proof of Theorem 18 (via Theorem 34) requires every leaf to satisfy nP_n(V)≥m for the variance bound 1/m; this example shows the algorithm does not enforce that condition. The false universal statement about S_β(V) being nonempty for β≥2 is a symptom of the same gap: even when S_β is nonempty, the fallback split need not lie in S_m, and the resulting leaf can violate the minimal-mass condition that the theorem's error bound depends on.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a unified theory of pointwise and sup-norm error bounds for local regression estimators indexed by VC classes of sets, centered on a new notion of shape-regular local maps. It proves a general deviation inequality (Theorem 4), introduces the minimal-mass assumption (X), shows that γ-shape-regularity suffices for near-minimax rates (Theorem 12) and that non-regular cells can be suboptimal (Proposition 10), and then applies the framework to k-NN, Proto-NN, OptiNet, a new CART-like tree algorithm (Algorithm 1), and purely random trees (uniform, centered, Mondrian). The proofs are detailed and the paper includes both positive and negative results, including new concentration bounds for Proto-NN and for CART-like trees.","tokens_in":45135,"tokens_out":7800,"duration_ms":76762,"significance":"If the main theorems are correct, the paper provides a coherent geometric condition—shape regularity—that unifies and extends known minimax guarantees for many local regression methods, and it supplies the first convergence-rate results for Proto-NN as well as near-optimal sup-norm guarantees for a data-dependent CART-type algorithm. The paper also contains explicit negative results for uniform and centered random trees, which are valuable for understanding when tree-based local estimators fail. The appendix is thorough, with self-contained proofs of the auxiliary concentration lemmas; the machine-checkable nature of the statement-level claims is a strength. However, the algorithmic guarantee for the CART-like tree in Section 5.3 has a genuine gap that affects a central advertised result.","major_comments":[{"comment":"The statement immediately after the definition of Sβ(V), 'when β ≥ 2, the Sβ(V) cannot be empty. Splitting the largest side in the middle is always in Sβ(V),' is false. For example, take d=2, V=[0,100]×[0,1], and β=2. Splitting the largest side in the middle produces children with side lengths 50 and 1, giving h+(child)/h−(child)=50, so neither child is 2-SR; indeed no split of this anisotropic cell can make both children 2-SR, since a split along the long side would require 100u≤2 and 100(1−u)≤2 simultaneously, which is impossible, and a split along the short side gives a child with largest side 100. This invalidates the claim used later in the proof of Theorem 18 that the β-SR constraint can never be a stopping criterion.","section":"Section 5.3"},{"comment":"Algorithm 1 does not enforce the condition nP_n(V)≥m for every leaf. In step (a), when the argmin over Sβ(V)∩Sm(V) has no solution, the fallback 'pick p as the largest side and u=1/2' is not checked against Sm(V). Concretely, with d=2, β=2, m=10, and a root cell [0,1]^2 containing 12 points at (0.1,0.1), 10 at (0.45,0.45), and 8 at (0.9,0.9), the only shape-regular split of the cube is the middle split, which puts 22 points in one child and 8 in the other, so it is not in Sm; the split u=0.3 along x is in Sm but not in Sβ. Thus Sβ∩Sm is empty, the fallback middle split is used, and the child containing 8 points is never split again because Sm=∅ there, producing a leaf with fewer than m points. Theorem 34, which is the basis of Theorem 18, requires every cell to satisfy nP_n(V)≥m for the variance bound 1/m, so the proof of Theorem 18 does not establish the claimed bound for the stated algorithm. The issue is fixable within the manuscript's scope, for example by treating 'Sβ(V)∩Sm(V)=∅' as a stopping condition rather than falling back to an unvetted split; this preserves nP_n(V)≥m because Sm(V)≠∅ implies the cell contains at least 2m points.","section":"Section 5.3, Algorithm 1 and Theorem 18"}],"minor_comments":[{"comment":"The notation 'Λ ≍ n1/d+2' should read 'Λ ≍ n^{1/(d+2)}', and similarly in the proof 'C / n1/d+2' should be 'C n^{-1/(d+2)}'; as printed, the exponent is ambiguous and the final rate appears inverted.","section":"Section 6.4, Theorem 31 and its proof"},{"comment":"In the proof, the phrase 'where γ = γ1/d' is confusing: the symbol γ is introduced without a clear definition. It should be written as γ = \\barγ^{1/d} so that the subsequent substitution γ^d = \\barγ is transparent.","section":"Proof of Proposition 10"},{"comment":"Theorem 2 states the supremum over x∈R^d, while the local map V is only defined on SX; the statement should either restrict the supremum to x∈SX or extend V consistently to R^d.","section":"Theorem 2"},{"comment":"The sentence claiming that a leaf is kept 'if and only if the number of data points belonging to that cell is greater than m and strictly smaller than 2m' is not reflected in the pseudocode, because the fallback in step (a) can create a leaf with fewer than m points; this should be corrected after the algorithmic fix to the fallback rule.","section":"Section 5.3, discussion after Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and the theoretical framework is attractive. The main issue is the gap in the CART-like tree algorithm, which is a central advertised contribution; I believe it is fixable by a small change to the stopping rule, so I do not recommend rejection. I did not see a circularity problem: the use of Lemma 3 from Portier (2021) in the Proto-NN bias bound is a technical concentration tool, not the target result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper deserves a serious referee, but don't let the CART theorem through without checking it. The shape-regular local map framework is a genuine advance: it gives necessary and sufficient conditions for minimax pointwise and sup-norm rates under a Lipschitz regression model, and it organizes many known results into one picture. The Proto-NN rate is new and appears carefully derived. The negative results for uniform and centered trees are also useful.\n\nThe soft spot is in Section 5.3. The statement that S_beta(V) is never empty for beta >= 2 is false for arbitrary anisotropic rectangles (e.g., [0,100] x [0,1]), though this is not fatal because the algorithm starts from a cube. The real problem is the fallback in Algorithm 1: when S_beta ∩ S_m is empty, the algorithm picks the middle split of the largest side without checking S_m. The stress-test example is correct: on the given point configuration, the only beta-regular split is the middle one, which fails S_m; a non-regular split satisfies S_m, so the algorithm falls back and produces a leaf with 8 < 10 points. Theorem 18's proof uses Theorem 34, which requires every leaf to have nP_n(V) >= m. The line 'any V satisfies 2m >= nP_n(V) >= m' is false. The fix is easy (don't split unless S_beta ∩ S_m is nonempty, or make the fallback respect S_m), but as written, Theorem 18 and Corollary 19 are not proven.\n\nThe rest of the paper appears solid: the VC-based deviation bounds, the k-NN and Proto-NN analyses, the random-tree results, and the geometric lemmas. The abstract's 'necessary' wording is a bit stronger than Proposition 10, which proves necessity for a specific regression function; that's minor.\n\nWho should read this: anyone working on local regression, decision trees, or prototype methods. It will be citable once the CART gap is patched. I would send it to referees, with a clear request to verify the algorithm's guarantees.","headline":"A solid framework with a real, fixable gap: the CART algorithm can create leaves with fewer than m points, so Theorem 18's bound is unproven as written.","tokens_in":45621,"tokens_out":6123,"would_cite":true,"duration_ms":62228,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G08","62G20","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Nearly isotropic local averaging cells are both necessary and sufficient for optimal nonparametric regression rates.","keywords":["local regression","local maps","shape regularity","minimax rates","sup-norm convergence","nearest neighbors","CART regression trees","Mondrian trees"],"falsifier":"Simulate $d=2$ regression with $g(x,y)=x+y$, $X$ uniform on $[0,1]^2$, and compare two local-map estimators at the origin: one using cells that are $\\gamma$-shape-regular with volume $n^{-1/2}$, the other using rectangles of the same volume but with one side of length $n^{-1/4}$ and the other $n^{-3/4}$, so that $\\mathrm{diam}(V)^2/\\lambda(V)\\sim n^{1/2}$. If the elongated-cell estimator's pointwise or sup-norm error does not decay at least as fast as $(\\log n/n)^{1/4}$, the necessity direction is confirmed; finding any non-shape-regular cell scheme that attains the minimax rate for every Lipschitz function would refute it.","tokens_in":2043,"feed_emoji":"📐","tokens_out":2366,"duration_ms":88201,"temperature":0.7,"pith_summary":"This paper asks when a local regression estimator—one that predicts at a point by averaging responses whose covariates fall in a small set around that point—attains the best possible statistical error for Lipschitz regression functions. The answer it defends is geometric: the averaging sets must be shape-regular, meaning their volume is comparable to the volume of a ball of the same diameter, and their Lebesgue volume must be calibrated to $n^{-d/(d+2)}$. Under that condition the pointwise and sup-norm errors are $(\\log n/n)^{1/(d+2)}$ up to constants; without it, a single sufficiently varying Lipschitz function can force a strictly slower rate. The same condition organizes a wide family of concrete estimators: $k$-nearest neighbors, prototype rules, and a CART-like tree with shape-constrained splits all satisfy it, while uniform and centered random trees violate it and only get near-optimal rates. Mondrian trees satisfy it in probability and reach the minimax pointwise rate.","feed_headline":"Local regression hits minimax rates only with near-spherical cells","feed_subtitle":"A volume-to-diameter condition on averaging neighborhoods is both necessary and sufficient for the best possible error.","key_machinery":"The central object is the $\\gamma$-shape-regular set: a measurable set $V$ satisfies $\\mathrm{diam}(V)^d \\le \\gamma \\lambda(V)$, meaning its volume is at least a fixed fraction of the ball with the same diameter—equivalently, the set is not too elongated. For hyper-rectangles this reduces to a bound on the ratio of longest to shortest side ($\\beta$-shape regularity), which is what a tree-splitting rule can actually enforce. The paper couples this geometric condition with a VC-dimension control on the collection of possible averaging sets and a minimal-mass assumption on the covariate distribution, $P_X(V(x)) \\ge \\ell(x)\\lambda(V(x))$, so that the variance term in the bias-variance decomposition is governed by Lebesgue volume rather than by the random number of points in a cell. The volume-diameter trade-off, optimized when $\\lambda(V(x)) \\asymp (\\log((n+1)^v/\\delta)/n)^{d/(d+2)}$, produces the rate $(\\log n/n)^{1/(d+2)}$. The failure mode is also geometric: if the local cell is much longer than wide, a Lipschitz function that increases along all coordinates exposes the bias, and the variance cannot be reduced enough to compensate.","core_discovery":"The central claim is Theorem 12 together with Proposition 10: for Lipschitz regression functions on $\\mathbb{R}^d$, a local map estimator attains the minimax pointwise and sup-norm rate $(\\log n/n)^{1/(d+2)}$ up to constants if and only if its averaging sets are $\\gamma$-shape-regular, $\\mathrm{diam}(V)^d \\le \\gamma \\lambda(V)$, with $\\lambda(V)$ of order $n^{-d/(d+2)}$. The sufficiency direction follows from a bias-variance bound (Theorem 6) that replaces the empirical count in a local cell by its Lebesgue volume via a minimal-mass assumption on the covariate distribution, and then optimizes the volume-diameter trade-off. The necessity direction constructs a Lipschitz function whose partial derivatives are all one, $g(x)=\\sum_k x_k$, and shows that any rectangular cell with $\\mathrm{diam}(V)^d/\\lambda(V)=\\bar\\gamma_n\\to\\infty$ yields expected squared error at least $C_d(\\bar\\gamma_n \\sigma^2/n)^{1/(d+2)}$, so the optimal rate cannot hold. The paper therefore claims that shape regularity is a structural, distribution-free property that separates estimators achieving optimal pointwise and uniform behavior from those that do not.","pith_inferences":["Beyond the paper's Lipschitz setting, the same shape-regularity criterion plausibly transfers to higher-order smoothness classes, where the optimal cell volume would scale as $n^{-d/(2s+d)}$ and an analogous necessary condition could be proved; the paper only treats the case $s=1$.","A practical diagnostic emerges: for any local averaging method, one can monitor $\\mathrm{diam}(V(x))^d/\\lambda(V(x))$ on the empirical cells and flag cells whose ratio grows with $n$; these are exactly the cells that spoil sup-norm performance, regardless of the split criterion.","Because the minimal-mass assumption is the only place the covariate density enters, methods that adaptively enlarge cells in low-density regions could maintain shape regularity and preserve the minimax rate without requiring a global lower bound on the density; testing this is a natural extension of the paper's framework."],"forward_implications":["For $k$-nearest neighbors, the correct choice $k \\asymp n^{2/(d+2)}$ yields the minimax sup-norm rate for every query point whenever a local density lower bound holds, extending earlier results that required a global density lower bound.","Proto-NN, whose convergence rates were previously open, attains the minimax rate up to logarithmic factors; OptiNet attains the same rate with substantially better probability guarantees.","A CART-like regression tree whose splits are restricted to $\\beta$-shape-regular cuts and whose leaves hold at least $m$ points achieves the minimax sup-norm rate; in one dimension every cell is shape-regular, so failure of classical CART must come entirely from producing cells with too few points.","Uniform and centered random trees are not shape-regular on events of positive probability, which explains why they only reach near-optimal rates $n^{-1/(d+2)}e^{O(\\sqrt{\\log n\\log\\log n})}$ rather than the exact minimax rate.","Mondrian trees are shape-regular in probability and achieve the minimax pointwise rate, but with probability that decays polynomially rather than exponentially, because the random partition can occasionally create very small cells."],"supporting_citations":[{"why":"Supplies the shattering-coefficient and VC-deviation framework used for the variance control in Theorem 2.","marker":"[VC15]"},{"why":"Provides the normalized Vapnik inequality (Theorem 35) that converts empirical cell counts into volume-based bounds under the minimal-mass assumption.","marker":"[AST93]"},{"why":"Gives the VC dimensions of balls and hyper-rectangles that bound the complexity terms for nearest-neighbor and tree local maps.","marker":"[WD81]"},{"why":"Supplies the negative pointwise results for CART that motivate the shape-restricted CART analysis.","marker":"[CKT22]"},{"why":"Provides the nearest-neighbor diameter bound (Lemma 3) reused for the Proto-NN and OptiNet bias terms.","marker":"[Por21]"},{"why":"Gives the distribution of Mondrian cell side lengths that yields shape regularity in probability and the minimax pointwise bound.","marker":"[MGS19]"},{"why":"Defines Proto-NN and poses the open problem on its convergence rates that the paper resolves.","marker":"[GW21]"},{"why":"Introduces the local-map formulation and consistency conditions for data-dependent partitions that this framework generalizes.","marker":"[Nob96]"}],"fun_headline_variants":["Shape-regular cells unlock minimax local regression rates","Minimax rates for local regression require shape-regular cells","Volume-diameter condition: the gate to optimal local fits","Local estimators need near-spherical cells for best rates","Shape regularity: necessary and sufficient for minimax error"],"cache_read_input_tokens":47744,"weakest_assumption_plain":"The load-bearing premise is the minimal-mass condition: every averaging set $V(x)$ must receive probability at least a fixed multiple of its Lebesgue volume under the covariate distribution. If a cell lands in a region where the covariate density is zero or extremely small, the variance term is no longer controlled by the cell's volume and the stated rates can fail.","fun_headline_variants_meta":{"raw":{"variants":["Shape-regular cells unlock minimax local regression rates","Minimax rates for local regression require shape-regular cells","Volume-diameter condition: the gate to optimal local fits","Local estimators need near-spherical cells for best rates","Shape regularity: necessary and sufficient for minimax error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000219,"raw_usage":{"total_tokens":1522,"prompt_tokens":1100,"completion_tokens":422,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":716,"completion_tokens_details":{"reasoning_tokens":343}},"tokens_in":716,"tokens_out":422,"duration_ms":4524,"temperature":1.0,"reasoning_tokens":343,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:05:26.070950+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate $d=2$ regression with $g(x,y)=x+y$, $X$ uniform on $[0,1]^2$, and compare two local-map estimators at the origin: one using cells that are $\\gamma$-shape-regular with volume $n^{-1/2}$, the other using rectangles of the same volume but with one side of length $n^{-1/4}$ and the other $n^{-3/4}$, so that $\\mathrm{diam}(V)^2/\\lambda(V)\\sim n^{1/2}$. If the elongated-cell estimator's pointwise or sup-norm error does not decay at least as fast as $(\\log n/n)^{1/4}$, the necessity direction is confirmed; finding any non-shape-regular cell scheme that attains the minimax rate for every Lipschitz function would refute it.","supporting_citations":[],"review_version":1}