{"id":"47b2d4ae-37d5-4815-8dee-3d90d3fd0684","arxiv_id":"2411.19164","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random prime lattice rules with random generating vectors and a median over repetitions achieve near-optimal integration error in all weighted Korobov classes, with dimension-independent constants for ℓ^{1/α}-summable weights.","lead":"A simple randomized algorithm for high-dimensional integration, based on random lattice sizes, random generating vectors, and a median over repetitions, achieves near-optimal error in all weighted Korobov classes without knowing the smoothness or weights of the integrand. It offers a parameter-free alternative to component-by-component constructions across a wide range of function classes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the randomized rate rests on Proposition 7, whose proof is only sketched, but no concrete flaw was found in the adaptation.","rationale":"The reader identified Proposition 7 as the weakest assumption, and I agree that it is the most load-bearing component: the full randomized exponent n^{-α-1/2+ε} is imported from this cited result, and the manuscript's proof of the adaptation is only a sketch. However, a careful examination did not reveal a concrete mathematical error. The apparent tension with Lemma 4's deterministic bound n^{-λ} is resolved by the fact that the randomized error is sup_f E|error(f)|, which can be smaller than the expected deterministic worst-case error; the median trick handles the rare bad events of a single full-set draw. The size of Z_{p,τ} is sufficient to control individual hitting probabilities, and the restriction γ_u≤1 preserves the estimates in [16]. The paper's own numerical experiments support the rates, but they are not tailored to a worst-case adversary. I therefore find no ground to reject or condition the verdict; the residual risk is presentation-level (an omitted detailed proof of a cited proposition), not a demonstrated flaw. An independent re-derivation or a targeted numerical lower-bound test would settle the question definitively.","tokens_in":13551,"tokens_out":49828,"duration_ms":420146,"concrete_test":"Independently re-derive Proposition 7 from [16, Theorem 9] with a general subset Z_{p,τ} of relative size τ∈(0,1), verifying in particular the bound on P_{z∈Z_{p,τ}}(h·z≡0 mod p and k·z≡0 mod p) needed for the second-moment argument and confirming that switching from product weights to general weights with γ_u≤1 does not change the estimate. As a numerical cross-check, run Algorithm 1 on the d=2 Korobov function f(x)=2^{-1/2}(e^{2πi(x_1+x_2)}+e^{-2πi(x_1+x_2)}) and on a lower-bound-style function with Fourier coefficients concentrated on prime-indexed frequencies; confirm the empirical expected-error rate tracks n^{-α-1/2+ε} rather than the single-copy bias rate n^{-1}.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central randomized-rate claim in Theorem 1(i) depends entirely on Proposition 7, adapted from [16, Theorem 9] to general weights and to a good vector set Z_{p,τ} of relative size τ>1/2. The manuscript's proof of Proposition 7 is a sketch: it verifies that every z∈Z_{p,τ} satisfies ρ(p,z)≥B'_n and then states 'we can indeed argue as in [16]'. This is the least secure step because the n^{-1/2} improvement is not a consequence of the pointwise deterministic bound (which alone yields only n^{-λ}); it requires the second-moment/cancellation argument in [16] to go through when z is drawn uniformly from a large but arbitrary subset Z_{p,τ}, and for general weights. I checked the essential mechanism: the size condition |Z_{p,τ}|≥τ(p-1)^d is enough to bound the probability that a given nonzero h satisfies h·z≡0 mod p by O(1/p) unless p divides all components of h, and the paper's restriction γ_u≤1 preserves the required estimates. Thus the adaptation appears sound, but because the strongest theorem inherits its exact exponent from this proposition, an independent re-derivation or direct numerical verification would remove the main residual risk.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a randomized lattice-rule algorithm for high-dimensional integration. For an integer n, the algorithm draws N ≈ h(n) log n independent trials; in each trial it selects a prime p uniformly from the primes in (n/2, n] and a generating vector z uniformly from {1, ..., p-1}^d, then computes the rank-1 lattice rule Q_z^p(f). The final estimate is the componentwise median of the N values. The main results, Theorem 1 and its detailed versions Theorems 9 and 10, state that for the weighted Korobov class H_{d,α,γ} with smoothness α > 1/2 and weights 0 < γ_u ≤ 1, the randomized worst-case error is O(n^{-α-1/2+ε}) and, with probability at least 1 - n^{-h(n)}, the deterministic worst-case error is O(n^{-α+ε}); the constants are independent of the dimension when the weights are product weights with γ ∈ ℓ^{1/α}. The algorithm is parameter-free, requiring no component-by-component construction. The proof combines a large-set result for good generating vectors (Lemma 4), a randomized-prime result adapted from Kritzer et al. (Proposition 7), and the median trick (Lemma 6). Numerical experiments for periodic and non-periodic test functions are reported.","tokens_in":17,"tokens_out":29882,"duration_ms":298744,"significance":"If Proposition 7 is made fully explicit, this is a significant contribution: it gives a genuinely simple, universal algorithm that automatically adapts to the smoothness and weights of a broad family of Korobov spaces, with near-optimal rates and dimension-independent constants under a natural summability condition. The combination of random primes, random generating vectors, and the median-of-means trick is novel in this context and avoids expensive CBC constructions. The proof of Lemma 4 is self-contained and correct modulo a typo, and the deterministic guarantee in Theorem 10 is also of independent interest. The numerical experiments, including the tent-transformed non-periodic variant, support the theoretical rates. The main weakness is that the proof of the load-bearing Proposition 7 is only a sketch referring to an external theorem.","major_comments":[{"comment":"Proposition 7 is the only source of the extra n^{-1/2} improvement in the randomized rate of Theorem 1(i), yet its proof is not actually given. The text states that after replacing Z_p with Z_{p,τ} and B_n with B'_n, 'we can indeed argue as in [16]', but the second-moment/cancellation argument that produces the n^{-1/2} factor is not reproduced, nor is it demonstrated that the size condition |Z_{p,τ}| ≥ τ(p-1)^d suffices for a generic subset Z_{p,τ} (rather than the specific set used in [16]) and for general weights γ_u ≤ 1. Because Theorem 9 and Theorem 1(i) inherit their exact randomized exponent from this proposition, this is a load-bearing gap. The authors should provide a complete proof or a detailed outline, e.g. in an appendix, verifying the double-sum estimates, the role of the condition n ≥ 4 V_d(α/λ, γ^{1/λ})/(1-τ), and the dependence of the constant on λ, δ, and τ.","section":"Section 2, Proposition 7"}],"minor_comments":[{"comment":"In the displayed equation after the indicator bound, the term  p|u|α/λ  should read  p^{-|u|α/λ}.  As printed, the subsequent inequality to 2/(p-1) V_d(α/λ,γ^{1/λ}) does not follow; the intended computation uses p^{-|u|α/λ} ≤ 1/(p-1). This is a typo, but it should be corrected to avoid confusion.","section":"Section 2, proof of Lemma 4"},{"comment":"The function f1(x) = prod_{j=1}^d (1 + |4x_j-2|^{-1}/j^{c_1}) has a non-integrable singularity at x_j = 1/2 for d = 1. Please clarify whether this is indeed the intended test function and justify the statement that hat f1(h) = O(|h|^{-2}) and that f1 belongs to the weighted Korobov space H_{d,3/2-ε,γ}. If the function is not in the space, the numerical validation would be more convincing with a different singular test function with an integrable singularity.","section":"Section 4, test function f1"},{"comment":"In the sentence beginning 'Thus, if we choose a random prime pk ...', the phrase 'for all 1 ≤ j ≤ k' should read 'for all 1 ≤ k ≤ N'.","section":"Section 3, proof of Theorem 10"},{"comment":"The notation γ^{1/λ} is used without an explicit definition in the context of general weights. For product weights it clearly means componentwise powers, but for general weights (γ_u) the meaning should be defined at first use, e.g. (γ_u)^{1/λ} applied componentwise over u.","section":"Section 1, Remark 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is well-written and the central idea is appealing. The main blocking issue is the missing proof of Proposition 7, which is load-bearing for the randomized rate. If the authors provide a full derivation of the adaptation in revision, the paper should be acceptable. In addition, the numerical test function f1 appears to be non-integrable and should be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThe thing to know: this paper delivers exactly what it says, and it is more honest than most. It proposes a universal randomized lattice rule—random prime, random generating vector, median over repetitions—and proves near-optimal worst-case error bounds simultaneously for all weighted Korobov classes with α>1/2 and general weights. The randomized rate is n^{-α-1/2+ε}, deterministic is n^{-α+ε} with probability 1-n^{-h(n)}. The ingredients are all known, and the paper says so plainly; the new part is the clean combination and the fact that the algorithm needs no knowledge of α or γ.\n\nWhat I liked: Lemma 4 is proved in full, and the adaptation of Proposition 7 from [16] to general weights and τ>1/2 is plausible and carefully sketched. The median trick application is neat, and the dimension independence under γ∈ℓ^{1/α} is carried through. The numerical experiments are honest and support the rates; they even show the algorithm automatically exploiting smoothness. The paper is refreshingly free of overclaiming—except the abstract says 'optimal' where the theorems give near-optimal with ε and logs, which is a minor wording issue.\n\nWhere the soft spots are, in proportion: the largest is Proposition 7. The n^{-1/2} gain in the randomized rate is not a consequence of the pointwise deterministic bound; it needs the second-moment/cancellation argument from [16] to survive when z is drawn uniformly from a large subset Z_{p,τ}, and for general weights. The proof here is a sketch ('we can indeed argue as in [16]'). I checked the mechanism, and it looks sound—the size condition does the job—but a referee should ask for a full proof or a reference that already covers this exact case. It is not a fatal flaw, just the least secure link. Also, Remark 2 about the tent transformation for non-periodic functions is stated without analysis; that's a minor gap. And the algorithm's cost is n log n h(n) function values, not n, so the rates are in terms of n with a log factor in cost—worth stating explicitly.\n\nThe citation pattern is fine: the key ingredients are credited to the right papers, and the self-citations are not load-bearing. This is a solid contribution that deserves a serious referee. Compared to the reader's take, I agree with ACCEPT; I'd just add that the abstract's 'optimal' should be softened and Proposition 7 deserves a fuller treatment.\n\nRecommendation: send to peer review. It'll be a useful paper for anyone doing high-dimensional integration in practice, and the theory is worth checking carefully once.","headline":"A clean, honest universal lattice rule with near-optimal rates in all weighted Korobov classes; the main theorem holds up, with Proposition 7 as the one spot a referee should press on.","tokens_in":14301,"tokens_out":3388,"would_cite":true,"duration_ms":26906,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65D30","41A25","41A63","46E35","65C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that one parameter-free randomized lattice rule—random prime, random generating vector, median—achieves near-optimal worst-case error in all weighted Korobov classes simultaneously.","keywords":["high-dimensional integration","lattice rules","randomized algorithms","median trick","weighted Korobov spaces","tractability","optimal error rates","universal quadrature"],"falsifier":"Take a one-dimensional Korobov function with Fourier coefficients decaying like $|h|^{-\\alpha}$, run Algorithm 1 for increasing $n$ with $h(n)=\\log\\log n$, and measure the expected error. If the empirical rate is $n^{-\\alpha}$ rather than $n^{-\\alpha-1/2}$ for all $n$ above the threshold $n\\ge 64V_d(\\alpha/\\lambda,\\gamma^{1/\\lambda})$, then the random-$n$ effect is not delivering the promised half-power.","tokens_in":1982,"feed_emoji":"🎲","tokens_out":7103,"duration_ms":108185,"temperature":0.7,"pith_summary":"This paper proves that a single parameter-free algorithm, Algorithm 1, achieves near-optimal error rates for high-dimensional integration across an entire family of smoothness classes simultaneously. The algorithm chooses, for each of $N=\\mathcal{O}(h(n)\\log n)$ repetitions, a random prime $p$ between $n/2$ and $n$, a random lattice vector $z\\in\\{1,\\dots,p-1\\}^d$, evaluates the rank-1 lattice rule $Q_p^z$, and returns the median of the estimates. For every weighted Korobov space with smoothness $\\alpha>1/2$, the randomized worst-case error is $O(n^{-\\alpha-1/2+\\varepsilon})$ and the deterministic worst-case error is $O(n^{-\\alpha+\\varepsilon})$ with high probability. The constants are independent of dimension whenever the product weights satisfy $\\gamma\\in\\ell^{1/\\alpha}$, so the same default implementation also provides tractable error bounds.","feed_headline":"One random lattice rule hits optimal error in every smoothness class","feed_subtitle":"No tuning of smoothness or weights: the same default rule achieves best possible rates in every weighted Korobov space.","key_machinery":"The key mechanism is the combination of three existing ideas into a parameter-free estimator. First, randomizing the prime $p$ in $(n/2,n]$ introduces a 'random $n$' effect that supplies the extra $n^{-1/2}$ in expectation; this is codified in Proposition 7, an adaptation of the known bound $\\mathbb{E}|I(f)-Q_p^z(f)| \\le C_{\\lambda,\\delta,\\tau} V_d(\\alpha/\\lambda,\\gamma^{1/\\lambda})^\\lambda n^{-\\lambda-1/2+\\delta}\\|f\\|$. Second, Lemma 4, built on the theory of good lattice rules, guarantees that at least a $\\tau$-fraction of all generating vectors are near-optimal, so uniform random selection succeeds with probability $>1/2$. Third, the median trick (Lemma 6) amplifies that constant success probability to $1-n^{-h(n)}$ without changing the rate.","core_discovery":"The central discovery is that optimal error rates do not require a tailored construction of the quadrature rule. With only the number of points $n$ as input, Algorithm 1 selects a prime $p$ uniformly from the primes in $(n/2,n]$, selects $z$ uniformly from all possible generating vectors, computes the lattice rule average, repeats this $N=2\\lceil h(n)\\log_2 n\\rceil+1$ times, and forms the median. Theorem 1 establishes that, for every $\\alpha>1/2$ and every weight sequence $\\gamma\\in(0,1]^{\\mathbb{N}}$, this one algorithm attains randomized worst-case error $\\le C n^{-\\alpha-1/2+\\varepsilon}$ and deterministic worst-case error $\\le C n^{-\\alpha+\\varepsilon}$ with probability at least $1-n^{-h(n)}$. When $\\gamma\\in\\ell^{1/\\alpha}$, both constants $n_0$ and $C$ are independent of $d$, and the algorithm automatically adapts to the unknown smoothness and weights.","pith_inferences":["Editorial inference: the same median-of-random-lattice template could be applied to other reproducing-kernel Hilbert spaces whose error is controlled by a tail of Fourier coefficients, as long as a proportion of node sets is near-optimal.","Editorial inference: choosing a slower-growing $h(n)$ such as $\\log\\log n$ keeps the cost low but only gives polylogarithmic failure probability; applications requiring high confidence should increase $h(n)$, at a multiplicative cost $O(h(n))$.","Editorial inference: the extra $n^{-1/2}$ from random $n$ suggests that a fully derandomized algorithm cannot match the randomized exponent unless it also randomizes the number of points; this may be an inherent barrier.","Editorial inference: combining Algorithm 1 with importance sampling or control variates could preserve universality while reducing variance, but remains untested."],"forward_implications":["A single default implementation, with no user-supplied smoothness or weights, can serve as a universal high-dimensional integrator; choosing $n$ and a slowly growing $h(n)$ is sufficient.","When product weights satisfy $\\gamma\\in\\ell^{1/\\alpha}$, the dimension-independent constants make the algorithm provably tractable, so no curse of dimensionality is introduced.","Because the deterministic error bound holds with probability at least $1-n^{-h(n)}$, fixing a random seed yields a deterministic rule with the same near-optimal rate.","The tent-transformation variant extends the results to non-periodic smooth integrands, giving a practical default for typical black-box functions.","Numerical tests with products of univariate functions and a family of variable smoothness converge with rates matching or exceeding the predicted $n^{-\\alpha-1/2}$, without any parameter tuning."],"supporting_citations":[{"why":"Supplies the random-n expected error bound that yields the extra n^{-1/2} in the randomized rate.","marker":"[16]"},{"why":"Provides the existence of a large set of good generating vectors, the basis of Lemma 4 and of the random-z success probability.","marker":"[8]"},{"why":"Supplies the median-trick concentration inequality used to amplify success probability to 1 - n^{-h(n)}.","marker":"[17]"},{"why":"Introduces the random number of points idea that gives the extra half power in expectation.","marker":"[1]"},{"why":"Serves as the template for the deterministic error analysis of median-based construction-free rules.","marker":"[12]"},{"why":"Provides the standard lattice-rule error formula and the weighted Korobov space background used throughout.","marker":"[6]"}],"fun_headline_variants":["No tuning: one random rule is optimal for every smoothness","Automatic adaptation: one algorithm fits all weighted Korobov classes","Universal integration algorithm: optimal rates, zero parameters","Random lattice rule: best in every Korobov space, no setup"],"cache_read_input_tokens":16384,"weakest_assumption_plain":"The randomized rate $n^{-\\alpha-1/2}$ depends on Proposition 7's claim that choosing the prime randomly near $n$ improves the expected error by the extra factor $n^{-1/2}$. If that random-$n$ effect fails for general weights, or for the $\\tau>1/2$ case needed by the median trick, the optimal randomized exponent in Theorem 1(i) would no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["No tuning: one random rule is optimal for every smoothness","Automatic adaptation: one algorithm fits all weighted Korobov classes","Universal integration algorithm: optimal rates, zero parameters","Random lattice rule: best in every Korobov space, no setup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001255,"raw_usage":{"total_tokens":5058,"prompt_tokens":774,"completion_tokens":4284,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":390,"completion_tokens_details":{"reasoning_tokens":4213}},"tokens_in":390,"tokens_out":4284,"duration_ms":31356,"temperature":1.0,"reasoning_tokens":4213,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:29:18.986705+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a one-dimensional Korobov function with Fourier coefficients decaying like $|h|^{-\\alpha}$, run Algorithm 1 for increasing $n$ with $h(n)=\\log\\log n$, and measure the expected error. If the empirical rate is $n^{-\\alpha}$ rather than $n^{-\\alpha-1/2}$ for all $n$ above the threshold $n\\ge 64V_d(\\alpha/\\lambda,\\gamma^{1/\\lambda})$, then the random-$n$ effect is not delivering the promised half-power.","supporting_citations":[{"cited_title":"Kritzer, F","cited_arxiv_id":null,"evidence_quote":"Supplies the random-n expected error bound that yields the extra n^{-1/2} in the randomized rate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the existence of a large set of good generating vectors, the basis of Lemma 4 and of the random-z success probability."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the median-trick concentration inequality used to amplify success probability to 1 - n^{-h(n)}."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the random number of points idea that gives the extra half power in expectation."},{"cited_title":"Goda and P","cited_arxiv_id":null,"evidence_quote":"Serves as the template for the deterministic error analysis of median-based construction-free rules."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the standard lattice-rule error formula and the weighted Korobov space background used throughout."}],"review_version":1}