{"id":"49b5e43b-3d0d-446c-be63-32d951af9f0c","arxiv_id":"2501.04842","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Adaptively constructed decision-tree strata yield a Monte Carlo estimator whose error converges faster than the standard rate for certain function classes, at O(N log N) complexity.","lead":"This paper proposes a Monte Carlo integration method that builds the integration strata adaptively from a decision tree trained on a preliminary sample, splitting the domain where the integrand varies most. It gives formal error rates faster than plain Monte Carlo for certain function classes and reports numerical gains in dimensions up to 50.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The core rate claim rests on an invalid inequality in Theorem 2's proof: B_j ≥ B_k does not imply the variance-reduction factor is ≤ B_k/(1+B_k), since x/(1+x) is increasing.","rationale":"The reader's weakest assumption was monotonicity. That is a genuine limitation, and Example 1 makes it clear, but it is explicitly scoped into the theorem's hypothesis ('certain classes of functions'), so it does not by itself undermine the central claim. The more serious concern is that Theorem 2's proof contains a reversed inequality at the key step that produces the uniform variance-reduction factor. Without a valid uniform contraction factor, neither the oracle rate nor the adaptive rate in Theorem 3 is proven. The reader did mention a proof gap in Theorem 3 (the bad-event variance contribution), but that gap is likely fixable because the estimator is unbiased conditional on the tree and the bad-event probability is O(N^{-2}); the Theorem 2 gap is more load-bearing. The verdict should remain conditional: the central claim may well be true, but the current proof does not establish it, and the authors need to repair the inequality or replace the argument.","tokens_in":12849,"tokens_out":31528,"duration_ms":304968,"concrete_test":"Re-derive the passage in Theorem 2's proof after Eq. (8): with h(x)=x/(1+x), verify whether B_j ≥ B_k implies h(B_j) ≤ h(B_k). It does not, since h is increasing. To see whether the theorem itself fails, compute the oracle tree for a strictly increasing function with s=2, α=(1,0.1), β=(1,1), e.g., f(x)=x1+g(x2) with g'=1 on [0.25,0.75] and g'=0.1 elsewhere, and compare the observed first-split variance-reduction factor with q(s)=Σβ²/α²/(3/4+Σβ²/α²). If the factor exceeds q(s), the contraction bound in Theorem 2 is false; if not, the gap is in the proof's derivation and a repaired argument is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing issue is not the monotonicity restriction (which is explicitly scoped into 'certain classes') but an invalid inequality in the proof of Theorem 2, the engine of Theorem 3. In the proof, after Eq. (8), the authors derive that for any split direction j the variance-reduction factor is bounded by h(B_j) := B_j/(1+B_j), with B_j = Σ_i (β_i²/α_i²)(α_i² μ_i²)/(α_j² μ_j²). They set k = argmax_j α_j²μ_j², note that B_j ≥ B_k, and conclude the factor is ≤ h(B_k). Since h is strictly increasing on [0,∞), B_j ≥ B_k implies h(B_j) ≥ h(B_k), so the conclusion has the inequality reversed. The subsequent bound h(B_k) ≤ h(Σβ_i²/α_i²) is true, but it does not bound the factor for the oracle's chosen direction j⋆. Thus the uniform per-split contraction factor q(s) in Eq. (9), inherited by the ε-oracle argument in Theorem 3, is not established by the given proof. This is a correctness risk for the central claim even within the class of functions assumed in Theorem 2.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AdaStrat, an adaptive stratified Monte Carlo estimator for integrals on [0,1]^s. A preliminary sample of size N is used to grow a regression tree with the CART split criterion; the leaves of the tree define strata of equal volume, and a second independent sample is drawn uniformly from each stratum. The paper claims that for certain integrands (linear functions, or functions that are strictly increasing with two-sided Lipschitz bounds), the oracle-tree version of the estimator converges at rate O(N^{-1/2-r(s)}) with explicit r(s)>0, and that the practical estimator retains this rate up to an arbitrarily small loss (Theorem 3). Numerical experiments compare the method with standard Monte Carlo and Haber's estimator in dimensions up to 50.","tokens_in":13141,"tokens_out":15535,"duration_ms":151002,"significance":"If the rate claims hold after repairing the proof, the paper makes a solid contribution: it provides an adaptive stratification method with near-linear computational cost and explicit convergence-rate gains, in a regime where classical stratified estimators such as Haber's are impractical. The oracle analysis in Theorems 1 and 2 is a clean way to obtain explicit rates, and the paper is unusually transparent about the scope of its assumptions, including a counterexample (Example 1) showing that the monotonicity condition is not a technical artifact. A notable strength is that the method has no data-fitted constants: the only tuning parameter is the tree depth, set to k, so the rate analysis does not rely on learned parameters. The central claim currently rests on a proof of Theorem 2 that contains a reversed inequality; the issue appears locally fixable, but until it is corrected the main theorem is not established.","major_comments":[{"comment":"After Eq. (8), the variance-reduction factor for a split along direction j is bounded above by h(x_j)=x_j/(1+x_j), where x_j=(4/3)∑_{i=1}^s (β_i^2/α_i^2)(α_i^2 μ_i^2)/(α_j^2 μ_j^2). Since k=argmax_j α_j^2 μ_j^2, one has x_j ≥ x_k for every j, and because h is strictly increasing on [0,∞), h(x_j) ≥ h(x_k). The manuscript instead concludes the opposite inequality and uses it to obtain the contraction factor in Eq. (9); the direction is reversed and Theorem 2 is not proved as written. The argument can be repaired: the oracle split j*=argmin_j Δ(R,j) satisfies C2(j*)≤C2(k), and because Δ(R)=C1(j)+C2(j) is the same for all j, the factor satisfies C2(j*)/Δ(R) ≤ C2(k)/(C1(k)+C2(k)) ≤ h(x_k). This repair should be stated explicitly.","section":"Section 3.2, proof of Theorem 2"},{"comment":"The proof bounds the probability that the estimated tree differs from an ε-oracle tree before depth L_k by O(N^{-2}) and separately bounds the variance of an ε-oracle tree, but it never assembles the unconditional RMSE. Since the estimator is unbiased conditional on the tree, the proof should explicitly write var(bI_AdaStrat)=E[var(bI_AdaStrat|tree)] ≤ P(good) q_ε^{L_k} var(bI_MC) + P(bad) C/N, with P(bad)=O(N^{-2}) and C a constant (for instance using var(bI_AdaStrat|tree)≤var(bI_MC) for any tree), and then conclude the stated rate. The current sentence 'we conclude the proof by remarking...' skips this decomposition. The final display also says 'var[bIMC]' where the variance of the AdaStrat estimator is meant; this is a typo, but the missing composition is a load-bearing gap in the proof of the main claim.","section":"Section 3.3, proof of Theorem 3"}],"minor_comments":[{"comment":"After the display of the control variate bound, the text says '∥f−bf_N∥∞ = O(k^{-1}) = O(N^{1/s})'; the exponent on N should be −1/s.","section":"Section 1.2"},{"comment":"In the definition of R[j]_−, the displayed formula for (a'_i,b'_i) is self-referential and contains a typo; it should define the interval split at the midpoint of the j-th coordinate.","section":"Section 2.1"},{"comment":"The bound is written with 'eκ' in two places; this should be 'e^κ'.","section":"Section 3.3, Lemma 2"},{"comment":"The 'Remark that' condition for the choice of L_k is written in a confusing way: the role of δ is not defined (presumably δ=e^{-κ}), and the chain of implications should be rewritten for readability.","section":"Section 3.3, proof of Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is from established researchers and the core idea is promising. The reversed inequality in the proof of Theorem 2 is a serious but localized slip: the theorem can be repaired by using the minimality of the oracle split rather than the displayed inequality. I recommend major revision rather than rejection. The authors should also spell out the RMSE decomposition in Theorem 3. If the repair is clean, the paper would be a useful contribution to adaptive Monte Carlo."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The idea is genuinely worth knowing: train a CART-style regression tree on a pilot sample, use the leaves as strata, and get a stratified estimator with O(N log N) total cost. That is a real step beyond Haber-style cubic grids (which need N = k^s) and beyond kNN or Gaussian-process control variates with quadratic or cubic cost. The writing is clear, the sparsity-adaptivity point is nice, Theorem 1 is clean, and Example 1 is an honest demonstration that the monotonicity assumption is not a technical artifact. The authors also cite the relevant prior work and do not oversell the empirical results.\n\nThe load-bearing issue is in the proof of Theorem 2. The claimed flaw is real. The proof bounds the variance-reduction factor for any split direction j by h(B_j) = B_j/(1+B_j). It then defines k = argmax_j alpha_j^2 mu_j^2 and observes that B_j >= B_k. Since h is strictly increasing, B_j >= B_k implies h(B_j) >= h(B_k), so that lower bound cannot be used to conclude the factor is <= h(B_k). The uniform contraction factor in Eq. (9) is therefore not established, and Theorem 3, which inherits Eq. (9), is unsupported as written. This is not a missing technical detail; the direction of the inequality is wrong. A different argument might salvage the rate, for example by controlling B_{j*} directly, but that argument is not in the manuscript.\n\nEverything else is minor by comparison: no code, no error bars on the RMSE plots, and the monotone/Lipschitz class is narrow, but the authors are explicit about that scope.\n\nWho this is for: Monte Carlo researchers and practitioners who want a cheap adaptive variance-reduction method. The numerics suggest the method can help even in dimension 50, independent of the rate proof. I would not cite it for the rate, but I would mention it as related work on adaptive stratification.\n\nRecommendation: this deserves a serious referee, because the idea and experiments are worth engaging with. The referee should be asked to check Theorem 2's proof carefully. In current form the headline convergence-rate claim is unproven; the paper would need a repaired proof before it is fully established.","headline":"Good adaptive stratification idea, but the proof of the main rate claim contains a reversed inequality and the headline result is unproven as written.","tokens_in":13652,"tokens_out":3901,"would_cite":false,"duration_ms":39356,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C05","62G08","65D30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive stratified Monte Carlo via decision trees provably converges faster than plain Monte Carlo — at rate $O(N^{-1/2-r'})$ for monotone integrands — while keeping $O(N \\log N)$ cost.","keywords":["adaptive stratified Monte Carlo","decision trees","Monte Carlo integration","variance reduction","convergence rate","unbiased estimation","sparsity-adaptive","high-dimensional integration"],"falsifier":"Take $f(x)=\\exp(\\sum_{i=1}^s \\lambda_i x_i)$ with $\\lambda_i=i^{-2}$, satisfying Theorem 2, compute $r(s)$ from the implied $\\alpha_i,\\beta_i$, and estimate the RMSE exponent from $\\log\\mathrm{RMSE}$ versus $\\log N$ over $N=2^{10},2^{12},\\dots,2^{20}$ with many independent runs. If the exponent is not strictly better than $-1/2$ (or fails to reach $-(1/2+r')$ for an $r'<r(s)$), the paper's central rate claim is false; alternatively, for $f=\\lambda x_1+\\sin(2\\pi x_2)$, the paper's counterexample, the predicted exponent should be no better than $-1/2$.","tokens_in":12684,"feed_emoji":"🌳","tokens_out":11600,"duration_ms":105740,"temperature":0.7,"pith_summary":"This paper proposes AdaStrat, an unbiased Monte Carlo estimator for integrals over $[0,1]^s$ whose strata are learned from the integrand. The idea is to take a first $N$-point sample, build a decision tree that splits rectangles in half along the direction that most reduces empirical variance, and then use the tree's leaves as strata for a second independent sample. The paper claims that for integrands that are strictly increasing in every coordinate and obey a two-sided Lipschitz condition, this adaptive estimator converges at rate $O(N^{-1/2-r'})$ for some $r' > 0$, improving on the $O(N^{-1/2})$ rate of plain Monte Carlo. Because the tree ignores coordinates that do not affect the integrand, the method is sparsity-adaptive, and it stays practical in dimensions where classical stratified estimators such as Haber's require $k^s$ cells. A reader should care because it offers a cheap, unbiased way to beat plain Monte Carlo when the integrand is modestly regular and the dimension is moderate to high.","feed_headline":"Decision-tree strata give Monte Carlo a faster error rate","feed_subtitle":"The estimator learns where to split, beating plain Monte Carlo's 1/sqrt(N) error for monotone integrands.","key_machinery":"The load-bearing mechanism is the variance-reduction factor of a single binary split. For a rectangle $R$ split in half along axis $j$, the stratified variance is multiplied by $(\\Delta(R_+^{(j)})+\\Delta(R_-^{(j)}))/(2\\Delta(R))$, where $\\Delta$ is the conditional variance of $f$. Under monotonicity and the two-sided Lipschitz bounds, the best coordinate $j^\\star$ makes this factor at most $\\frac{\\frac43\\sum_i \\beta_i^2/\\alpha_i^2}{1+\\frac43\\sum_i \\beta_i^2/\\alpha_i^2}$, uniformly over rectangles, so the $k$ splitting levels compound into a geometric variance decay. To pass from the oracle tree to the feasible one, the paper introduces an $\\varepsilon$-oracle tree, which may choose any near-optimal direction when two directions are nearly tied, and uses a concentration inequality for empirical variances to show the estimated tree matches the $\\varepsilon$-oracle up to depth $L_k$ with probability $1-O(N^{-2})$.","core_discovery":"The paper's central claim is Theorem 3: under the assumptions of Theorem 2 — $f$ strictly increasing in each coordinate and satisfying coordinate-wise lower and upper Lipschitz bounds — the AdaStrat estimator has RMSE $O(N^{-1/2-r'})$ for any $0<r'<r(s)$. The oracle rate is $r(s)=\\frac{1}{2\\log 2}\\log\\left(\\frac{\\frac34+\\sum_i \\beta_i^2/\\alpha_i^2}{\\sum_i \\beta_i^2/\\alpha_i^2}\\right)$. The proof first analyses an oracle tree that splits using true conditional variances and shows that each split reduces variance by a factor bounded away from one; it then shows that the estimated tree agrees with an $\\varepsilon$-oracle tree up to depth $L_k$ with probability $1-O(N^{-2})$, so the same rate survives estimation of the tree. The paper also proves a sparsity-adaptive rate $O(N^{-1/2-r(s_0)})$ for linear functions supported on $s_0$ coordinates, and gives Example 1 showing that without monotonicity no such rate can hold in general.","pith_inferences":["The $\\varepsilon$-oracle proof suggests the practical bottleneck is not tree depth but near-ties between split directions; averaging over several near-equal trees (a forest-style extension) would be a natural way to stabilise the rate constant in high dimension.","The same decision-tree partition could be reused as a control variate, since the tree leaves define a piecewise-constant function whose integral is exactly computable; this would combine stratification and centering without extra evaluations of $f$.","If monotonicity is the real barrier, applying a monotone transformation to each coordinate of the preliminary sample before growing the tree might extend the rates to non-monotone but coordinatewise monotone transforms of $f$; this is not tested in the paper."],"forward_implications":["For any integrand in the paper's monotone Lipschitz class, AdaStrat's RMSE beats the $N^{-1/2}$ Monte Carlo benchmark by a positive power of $N$.","Because only influential coordinates are split, the rate depends on the effective dimension $s_0$ for linear functions; the method automatically ignores irrelevant dimensions where fixed-grid stratification wastes evaluations.","The estimator is unbiased and costs $O(N \\log N)$ to build, so it can be plugged into pseudo-marginal samplers or stochastic approximation routines that require unbiased estimates of an integral.","The extension to arbitrary $N$ by volume-proportional splits lets the same adaptive strategy be used when $N$ is not a power of two, and taking two points per stratum gives a simple variance estimate."],"supporting_citations":[{"why":"Defines the fixed-grid stratified estimator whose $k^s$ cost motivates the adaptive tree approach, and serves as the baseline in numerical comparisons.","marker":"Haber (1966)"},{"why":"Introduces the recursive decision-tree splitting used to grow the strata.","marker":"Morgan and Sonquist (1963)"},{"why":"Provides the empirical-variance concentration inequality used to bound the probability that the estimated tree disagrees with the $\\varepsilon$-oracle tree.","marker":"Maurer and Pontil (2009)"},{"why":"Supplies the higher-order stratified estimator and the two-points-per-stratum variance estimator used alongside AdaStrat.","marker":"Chopin and Gerber (2024)"},{"why":"Establishes the optimal $O(N^{-1/2-r/s})$ benchmark for $N$-evaluation estimators, against which the paper sets its achievable rates.","marker":"Bahvalov (1959)"}],"fun_headline_variants":["Decision trees slash Monte Carlo error rates","Adaptive tree strata beat 1/sqrt(N) Monte Carlo","Monte Carlo converges faster via learned strata from trees","Tree-based stratification beats sqrt(N) for monotone integrands"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The rate guarantee rests on the integrand being strictly increasing in every coordinate and satisfying a lower Lipschitz bound in every coordinate; if any coordinate is non-monotone, the oracle tree may never split it and the proof of a faster-than-$N^{-1/2}$ rate collapses, as the paper's sine example shows.","fun_headline_variants_meta":{"raw":{"variants":["Decision trees slash Monte Carlo error rates","Adaptive tree strata beat 1/sqrt(N) Monte Carlo","Monte Carlo converges faster via learned strata from trees","Tree-based stratification beats sqrt(N) for monotone integrands"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000315,"raw_usage":{"total_tokens":1776,"prompt_tokens":929,"completion_tokens":847,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":782}},"tokens_in":545,"tokens_out":847,"duration_ms":8461,"temperature":1.0,"reasoning_tokens":782,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:25:00.520613+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $f(x)=\\exp(\\sum_{i=1}^s \\lambda_i x_i)$ with $\\lambda_i=i^{-2}$, satisfying Theorem 2, compute $r(s)$ from the implied $\\alpha_i,\\beta_i$, and estimate the RMSE exponent from $\\log\\mathrm{RMSE}$ versus $\\log N$ over $N=2^{10},2^{12},\\dots,2^{20}$ with many independent runs. If the exponent is not strictly better than $-1/2$ (or fails to reach $-(1/2+r')$ for an $r'<r(s)$), the paper's central rate claim is false; alternatively, for $f=\\lambda x_1+\\sin(2\\pi x_2)$, the paper's counterexample, the predicted exponent should be no better than $-1/2$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the fixed-grid stratified estimator whose $k^s$ cost motivates the adaptive tree approach, and serves as the baseline in numerical comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the recursive decision-tree splitting used to grow the strata."},{"cited_title":"and Pontil, M","cited_arxiv_id":null,"evidence_quote":"Provides the empirical-variance concentration inequality used to bound the probability that the estimated tree disagrees with the $\\varepsilon$-oracle tree."},{"cited_title":"and Gerber, M","cited_arxiv_id":null,"evidence_quote":"Supplies the higher-order stratified estimator and the two-points-per-stratum variance estimator used alongside AdaStrat."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the optimal $O(N^{-1/2-r/s})$ benchmark for $N$-evaluation estimators, against which the paper sets its achievable rates."}],"review_version":1}