{"id":"aa01b89c-0296-47bc-889f-74b249a61a4d","arxiv_id":"2608.08360","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A single shape-regularity criterion determines which purely random partitions reach the minimax regression rate; centered and uniform trees fail it, while Mondrian trees and OptiNet pass, and Proto-NN gets its first pointwise concentration bound.","lead":"Random partition estimators split the covariate space without looking at the response; this paper finds which random splitting rules keep cells round enough to converge at the fastest possible rate. It gives the first pointwise error bounds for the prototype-based Proto-NN method and shows that an eta-net variant converges almost surely.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Optimality and 'unavoidable sub-optimality' claims hinge on the companion [BPS26] necessity theorem, which is not proved here and may be uniform-norm rather than pointwise; if that theorem fails in the pointwise setting the central shape-regularity mechanism is not established.","rationale":"I read the paper in good faith. The core pointwise concentration bound (Theorem 1 and Corollary 2) is proved cleanly, and the provided proofs of the tree diameter/volume bounds, the Mondrian analysis, and the Proto-NN/OptiNet variance and bias controls appear internally coherent. I found no arithmetic slip in the main computations I checked, including the balancing in Theorems 6, 11, 14, and 17. The load-bearing weakness is exactly the dependence on [BPS26] for the necessity of shape regularity in the pointwise sense. The present paper's new results are upper bounds; its optimality and 'unavoidable' language requires the companion theorem to supply matching lower bounds. If that theorem is uniform-norm instead of pointwise, or if it applies only when the entire partition is shape-regular rather than when the cell containing x is, then the central claim as stated in this paper is not established. The reader's verdict of CONDITIONAL is therefore appropriate: the paper should be accepted only with the [BPS26] criterion verified in the pointwise setting, or with the optimality claims weakened to explicit upper-bound statements.","tokens_in":32988,"tokens_out":18553,"duration_ms":167199,"concrete_test":"Obtain [BPS26] and isolate its necessity theorem. Verify (i) whether it is stated for pointwise loss or for sup-norm loss, and (ii) whether the cell containing x is the only cell whose shape enters. Then, in the notation of the present paper, prove the contrapositive used here: for centered trees (Proposition 7, aspect ratio at least 2^{sqrt(N/d)} with probability at least 1/14) and for uniform trees, there exists a Lipschitz g and a density satisfying (XTREE) such that the pointwise error is bounded below by c n^{-1/(d+2)} on the bad event. If this lower-bound proof cannot be carried out pointwise, the 'unavoidable' and 'attains the minimax rate' wording should be replaced by upper-bound-only statements.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central assertion, that shape regularity is necessary and sufficient up to logarithmic factors for the pointwise minimax rate n^{-1/(d+2)}, is imported verbatim from the authors' companion preprint [BPS26] (Abstract; Section 1; Section 2 before Definition 3). Every conclusion that a family 'attains the minimax rate' (Theorems 14, 16, 17) or that the centered/uniform super-logarithmic corrections are 'unavoidable' (Propositions 7 and 12) inherits the necessity direction of that criterion. The present paper proves only upper bounds through Corollary 2; it does not prove a pointwise lower bound for non-shape-regular partitions. If the [BPS26] criterion is established only for sup-norm loss, or only under a condition that all cells of the partition are shape-regular with high probability rather than just the cell containing x, then the pointwise conclusions do not follow. The non-shape-regularity events of Propositions 7 and 12 have positive probability but are not by themselves a lower-bound argument. A second unsupported assertion is the impossibility of an almost sure Mondrian guarantee in Section 3.4, which is stated without proof. Both issues point to the same conditional status: the central claim is sound only insofar as the companion preprint's pointwise necessity theorem is sound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies pointwise convergence rates of regression estimators based on purely random partitions: tree-based partitions (centered, uniform, Mondrian) and Voronoi-type prototype rules (Proto-NN and OptiNet). The main tool is a general finite-sample pointwise deviation bound (Theorem 1 and Corollary 2) that separates a variance term depending on the cell volume and a bias term depending on the cell diameter. The paper then analyzes the shape regularity of the cell containing the evaluation point in each construction. It proves that centered and uniform trees are not shape-regular on events of positive probability, that Mondrian trees are shape-regular with high probability and achieve n^{-1/(d+2)} rates, that Proto-NN admits the first pointwise concentration bounds at the minimax rate, and that OptiNet achieves the same rate with an almost sure guarantee under suitable parameter choices. Several optimality and impossibility claims are attributed to the companion preprint [BPS26], and one positive bound for the bias term is imported from [Por21].","tokens_in":33249,"tokens_out":9165,"duration_ms":84425,"significance":"If the imported necessity result from [BPS26] is valid in the pointwise sense used here, the paper provides a genuinely unifying geometric explanation for the different rates of random-partition estimators, and it resolves the open Proto-NN rate problem explicitly raised by Györfi and Weiss. The paper's own contributions are substantial: Corollary 2 is a clean and reusable pointwise concentration inequality; the Borel-Cantelli arguments for centered and uniform trees, the Paley-Zygmund lower bounds for aspect ratios, and the order-statistic analysis for Proto-NN are mostly self-contained and internally consistent; and the almost sure OptiNet rate is a strong, concrete result. The upper-bound halves of the tree results and the Proto-NN/OptiNet concentration bounds are proved rather than merely asserted.","major_comments":[{"comment":"The paper's central claim that shape regularity is necessary and sufficient, up to logarithmic factors, for the pointwise minimax rate is imported from the same-author companion preprint [BPS26] and is not proved in this manuscript. The present paper proves only upper bounds via Corollary 2 and its applications; no pointwise lower bound is proved for partitions that fail shape regularity. Therefore the statements that centered and uniform trees have 'unavoidable' super-logarithmic corrections (Propositions 7 and 12 and the discussion after Theorem 11) and that Mondrian trees, Proto-NN, and OptiNet 'attain the minimax rate' (Theorems 14, 16, and 17) are conditional on the necessity direction of [BPS26]. The authors should either state precisely which theorem of [BPS26] is being used and in which norm, prove the needed pointwise lower bound, or explicitly mark all optimality claims as conditional on the companion result.","section":"Section 2, Definition 3 and the paragraph before it; Abstract"},{"comment":"The claim that the Mondrian rate 'cannot be extended to an almost sure convergence guarantee' is asserted without proof. Proposition 13 and Theorem 14 give only high-probability bounds with a δ-dependent regularity constant; they do not rule out the existence of a different argument yielding an almost sure rate. This negative claim is load-bearing because it is used to contrast Mondrian trees with OptiNet, so it needs a proof (for example, a quantitative lower bound on the probability of an abnormally small cell along a subsequence) or it should be removed and replaced by the weaker statement that the proof technique presented here does not yield an almost sure guarantee.","section":"Section 3.4, discussion after Theorem 14"},{"comment":"Proposition 12 establishes non-shape-regularity only for a fixed cell constructed by a predetermined sequence of splits, not for the random cell V(x) containing the evaluation point x. The text explicitly acknowledges the difficulty ('we face a major difficulty due to x') but then concludes that uniform trees 'fundamentally fail to satisfy the shape regularity property' and uses this conclusion to support the claimed unavoidable rate degradation in Theorem 11. Since the pointwise analysis concerns V(x), a fixed-cell failure with positive probability does not by itself establish that V(x) is non-shape-regular on a positive-probability event. The authors should either prove the analogue for V(x) or clearly state that only the fixed-cell failure is established.","section":"Section 3.3, Proposition 12 and the paragraph before it"},{"comment":"The text says that Mondrian regression trees 'attain, with high probability, the minimax rate for the pointwise error in expectation,' but Theorem 14 is a high-probability bound at fixed δ, and the constant C depends on δ through c_{δ,d} and log(1/δ). With δ fixed the failure probability is a positive constant, and letting δ tend to zero makes the constant diverge as a power of 1/δ. No expectation bound is derived. If the claim is only a high-probability rate, the wording should be changed; if an expectation rate is intended, a tail integration argument with a quantitative treatment of the bad event is needed.","section":"Section 3.4, Theorem 14 and surrounding text"},{"comment":"The bias bounds for Proto-NN and OptiNet rely on Lemma 3 of [Por21], a same-author preprint, without stating the lemma or reproducing its proof. This lemma is load-bearing because it controls the k-NN radius used to bound diam(V(x)), and Theorem 17 also invokes it directly. The authors should state the lemma or give a proof in an appendix, at least in the form needed for the present paper, so that the pointwise concentration claims are verifiable from this manuscript alone.","section":"Section 4, Theorem 15 and Theorem 17"}],"minor_comments":[{"comment":"The notation 2^{±N/d ± 2√((d−1)N log N)/d^2} is typographically overloaded in the full text; the intended exponents should be set with parentheses so that the additive fluctuation is inside the exponent.","section":"Section 3.2, Proposition 4 and Proposition 5"},{"comment":"The exponent n^{-1/(Θd+2)} is ambiguous; it should be written n^{-1/(Θ d + 2)} with an explicit multiplication dot, and the value Θ ≈ 5.5 should be stated as (1+log 2)/(1−log 2).","section":"Section 3.3, Theorem 11"},{"comment":"The sentence describing an 'identity' relating the variance term to (log(n/δ)/m)^{1/d} is not an identity; it is a consequence of the particular choice of m made in the corollary. The wording should be corrected.","section":"Section 4, proof of Corollary 16"},{"comment":"The reference to 'Proposition 22 in [BPS26]' is not accompanied by a statement of that proposition; since it is used to support the claim about structural sub-optimality, the authors should state the proposition or give a precise reference to its location in the companion paper.","section":"Section 3.4, final paragraph"},{"comment":"The quotation from [GW21] concerns the Proto-NN classifier, while the present paper treats regression; the authors should clarify that the open problem they resolve is the regression analogue or the same problem in the regression setting, to avoid a mismatch between the quote and the result.","section":"Section 4, introduction of Proto-NN"},{"comment":"There are several OCR-type artifacts in the displayed text (for example, missing multiplication symbols in exponents and equations such as 'n−1/(Θd+2)'); a careful copyedit of the mathematical notation is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the heavy reliance on the same-author companion [BPS26] for the necessity direction of the central shape-regularity criterion, and on [Por21] for a key k-NN radius bound. If the authors can state and prove the needed pointwise versions of these results, or clearly delineate the conditional nature of the optimality claims, the paper would be a solid contribution. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a careful read. The genuinely new contributions are the first pointwise concentration bound for Proto-NN (Theorem 15/Corollary 16), the almost sure OptiNet rate (Theorem 17), and the explicit non-shape-regularity of centered and uniform trees (Propositions 7 and 12). The proofs of these are internally coherent: the bias-variance split, the Borel–Cantelli arguments, and the order-statistic lower bounds all check out. The Paley–Zygmund calculations in Propositions 7 and 12 give real constant probabilities (1/14 and 1/11), which is exactly what you need for a negative result. I also like the framing: putting hyper-rectangular and Voronoi cells under one geometric criterion is useful pedagogy, and it does organize the paper well.\n\nNow the soft spots, in proportion. The load-bearing issue is the dependence on [BPS26]. Every statement that a method \"attains the minimax rate\" (Theorems 14, 16, 17) or that the centered/uniform corrections are \"unavoidable\" (Propositions 7 and 12) inherits the necessity direction of the shape-regularity criterion from that companion paper. The present paper only proves upper bounds. If [BPS26]'s necessity is sup-norm rather than pointwise, or requires all cells to be shape-regular rather than just the cell containing x, the pointwise optimality conclusions do not follow from what is proved here. This is not self-citation for its own sake, but the dependence is structural and should be disclosed much more explicitly. The referee should ask the authors to either state and prove the pointwise necessity theorem in this paper or clearly mark every optimality claim as conditional on the companion result.\n\nA second, smaller issue: the claim that an almost sure Mondrian guarantee is impossible (Section 3.4) is asserted without proof. It might be true, but it isn't demonstrated. The abstract also says this \"resolves an open problem of Györfi and Weiss\" while the theorem is about regression and pointwise concentration; the original open problem concerned classifier rates. That's a modest overreach, not a fatal one.\n\nWho is this for? Researchers in nonparametric regression, random forests, and prototype rules. They will find the Proto-NN bound and the negative tree results useful. The paper deserves peer review: the new results are real and the internal proofs sound, but the referee should push on the [BPS26] dependency and the unsupported almost-sure claim. I would send it out, and I'd expect heavy revision rather than acceptance as-is.","headline":"Solid new pointwise bounds for Proto-NN and OptiNet, with the main caveat that the minimax-optimality claims lean on the companion [BPS26] criterion rather than on proofs in this paper.","tokens_in":33842,"tokens_out":1721,"would_cite":true,"duration_ms":18237,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G08","62G20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Shape regularity decides the pointwise rate of purely random partition estimators","keywords":["shape-regularity","purely random partition","pointwise convergence rate","Mondrian trees","Proto-NN","OptiNet","minimax rate","Voronoi cells"],"falsifier":"Find a purely random partition that is not shape-regular, so the cell aspect ratio grows without bound on a positive-probability event, but whose pointwise error on a fixed Lipschitz function is nevertheless $n^{-1/(d+2)}$ up to logarithmic factors; this would refute the necessity of shape regularity. A less decisive check is to simulate centered and uniform trees and estimate the exponent in $n^{1/(d+2)}|\\hat g_V(x)-g(x)|$: the theory predicts growth like $e^{2\\sqrt{\\log n\\log\\log n}}$ for centered trees and like $n^{1/(d+2)-1/(\\Theta d+2)}$ for uniform trees.","tokens_in":32759,"feed_emoji":"📐","tokens_out":9005,"duration_ms":74935,"temperature":0.7,"pith_summary":"The paper sets out to show that a single geometric condition—shape regularity, meaning $\\operatorname{diam}(V)^d \\leq \\gamma \\lambda(V)$ for the cell containing the query point—governs the pointwise convergence rate of every purely random partition estimator. A new finite-sample deviation inequality splits the pointwise error into a variance term driven by cell volume and a bias term driven by cell diameter, making the geometry of the cell the only quantity that decides the rate. Applying this criterion, the paper shows why centered and uniform trees underperform: on an event of positive probability their cells become exponentially elongated, so the best pointwise rates they can certify are $n^{-1/(d+2)}e^{2\\sqrt{\\log n\\log\\log n}}$ and $n^{-1/(\\Theta d+2)}$ with $\\Theta\\approx 5.5$. Mondrian trees, whose splits adapt to the current side lengths, are shape-regular in probability and reach the minimax rate $n^{-1/(d+2)}$. The same analysis supplies the first pointwise concentration bounds for Proto-NN and shows that OptiNet reaches the minimax rate with much better probability, almost surely for a suitable parameter choice.","feed_headline":"One geometric condition sets the minimax rate for random partitions","feed_subtitle":"Mondrian trees and OptiNet reach the optimal n^{-1/(d+2)} rate; centered and uniform trees fall short when cells stretch.","key_machinery":"The central object is shape regularity: a cell $V$ is $\\gamma$-shape-regular whenever $\\operatorname{diam}(V)^d \\le \\gamma\\lambda(V)$, so its volume is comparable to the $d$-th power of its diameter. It is paired with a pointwise deviation inequality (Theorem 1) stating that, with probability at least $1-2\\delta$, $|\\hat g_V(x)-g(x)| \\le \\sqrt{2\\sigma^2\\log(1/\\delta)/(nP_n(V(x)))}+L(V(x))\\operatorname{diam}(V(x))$. When the cell is shape-regular and the design density is bounded below, the variance and bias terms balance at $\\lambda(V(x))\\asymp n^{-d/(d+2)}$, producing the minimax rate $n^{-1/(d+2)}$. The criterion becomes a classifier of rates because the paper imports the companion result that shape regularity is necessary and sufficient, up to logarithmic factors, for this minimax rate.","core_discovery":"The central claim is that shape regularity is not one more sufficient condition but the common mechanism: for purely random partitions, the pointwise rate is determined by whether the random construction keeps the cells from collapsing in some direction. The paper proves a general deviation bound, then establishes by explicit moment calculations that centered and uniform trees violate shape regularity on events of probability bounded away from zero, explaining the super-logarithmic corrections in their rates. It proves Mondrian trees are shape-regular in probability and therefore attain the minimax pointwise rate with probability at least $1-5\\delta$. For Voronoi partitions, it proves Proto-NN attains the minimax rate when the number of prototypes is tuned as $m\\asymp n^{d/(d+2)}(\\log n)^{2/(d+2)}$, and that OptiNet attains the same rate, with an almost sure version when $\\eta\\asymp(\\log n/n)^{1/(d+2)}$.","pith_inferences":["Beyond the paper: the same diagnostic could be applied to other blind-split ensembles, for instance random forests whose coordinate selection probabilities are fixed rather than side-length-weighted, predicting the same exponential aspect-ratio failure and hence the same type of rate degradation.","Beyond the paper: the small-cell event identified as the cause of poor probability scaling for Mondrian trees and Proto-NN suggests a concrete fix: enforce a minimum cell volume or prototype spacing in the spirit of OptiNet's $\\eta$-net, and test whether the success probability becomes exponential.","Beyond the paper: if the imported necessity result is correct, a practical model-selection rule emerges—monitor the empirical aspect ratio of the cell containing each test point and reject partitions whose cells are not shape-regular, since those cannot be minimax pointwise."],"forward_implications":["Any purely random tree whose split direction is chosen independently of the current cell's side lengths will, with positive probability independent of $n$, produce a cell containing $x$ whose aspect ratio grows exponentially in $\\sqrt{N/d}$, which is why centered and uniform trees cannot reach the minimax pointwise rate.","Mondrian trees attain the pointwise minimax rate $n^{-1/(d+2)}$ with probability at least $1-5\\delta$, but the probability of the good event decays polynomially rather than exponentially, so an almost sure version is not available.","Proto-NN, for which convergence rates were previously open, attains the minimax pointwise rate when $m\\asymp n^{d/(d+2)}\\log(n)^{2/(d+2)}$, with a success probability whose scaling matches that of Mondrian trees.","OptiNet attains the same minimax rate and, with $\\eta\\asymp(\\log n/n)^{1/(d+2)}$, does so almost surely, because the $\\eta$-net spacing prevents the abnormally small Voronoi cells that degrade Proto-NN.","Across all constructions, the rate question reduces to one geometric check: does the partition keep $\\operatorname{diam}(V)^d$ comparable to $\\lambda(V)$?"],"supporting_citations":[{"why":"Establishes the shape-regularity criterion and its necessity and sufficiency, up to logarithms, for the minimax rate; the paper's optimality statements inherit optimality from this result.","marker":"[BPS26]"},{"why":"Provides the classical consistency theorem (Theorem 6.1) for partition estimators that the paper's finite-sample deviation bound refines and quantifies.","marker":"[DGL96]"},{"why":"Introduces Proto-NN and poses the open problem of its convergence rates, which Corollary 16 resolves.","marker":"[GW21]"},{"why":"Supplies the distributional description of Mondrian cell side lengths used to prove Proposition 13 and Theorem 14.","marker":"[MGS19]"},{"why":"Provides the k-NN radius concentration lemma used to bound diameters of Voronoi cells in Theorems 15 and 17.","marker":"[Por21]"},{"why":"Supplies the sub-Gamma tail bound used to control the longest side of a Mondrian cell.","marker":"[BLM13]"},{"why":"Defines the Mondrian process from which Mondrian tree partitions are generated.","marker":"[RT08]"}],"fun_headline_variants":["Shape regularity decides minimax rates for random partitions","Why Mondrian trees hit the optimal rate but centered trees don't","A single geometric condition governs random partition estimators","Mondrian trees achieve minimax pointwise convergence; uniform trees fail","Shape regularity unlocks optimal rates for random partitions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The optimality conclusions rest on a companion theorem, imported without proof, that shape regularity is necessary as well as sufficient, up to logarithmic factors, for the pointwise minimax rate $n^{-1/(d+2)}$; if that necessity statement fails specifically for pointwise error, the claimed optimality of Mondrian, Proto-NN, and OptiNet does not follow from the proofs given here.","fun_headline_variants_meta":{"raw":{"variants":["Shape regularity decides minimax rates for random partitions","Why Mondrian trees hit the optimal rate but centered trees don't","A single geometric condition governs random partition estimators","Mondrian trees achieve minimax pointwise convergence; uniform trees fail","Shape regularity unlocks optimal rates for random partitions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000565,"raw_usage":{"total_tokens":2694,"prompt_tokens":978,"completion_tokens":1716,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":1638}},"tokens_in":594,"tokens_out":1716,"duration_ms":11813,"temperature":1.0,"reasoning_tokens":1638,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:07:59.500293+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a purely random partition that is not shape-regular, so the cell aspect ratio grows without bound on a positive-probability event, but whose pointwise error on a fixed Lipschitz function is nevertheless $n^{-1/(d+2)}$ up to logarithmic factors; this would refute the necessity of shape regularity. A less decisive check is to simulate centered and uniform trees and estimate the exponent in $n^{1/(d+2)}|\\hat g_V(x)-g(x)|$: the theory predicts growth like $e^{2\\sqrt{\\log n\\log\\log n}}$ for centered trees and like $n^{1/(d+2)-1/(\\Theta d+2)}$ for uniform trees.","supporting_citations":[],"review_version":1}