{"id":"3df38691-461a-496c-83de-16b08c7f098a","arxiv_id":"2509.02526","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Randomness used for sample queries can be reused across the outer iterations of variance-reduction solvers, reducing sample-query complexity by a factor equal to the number of outer iterations while preserving correctness.","lead":"This paper shows that variance-reduction optimization algorithms can reuse the same random samples across all outer iterations, cutting the number of sample queries by a factor equal to the number of iterations. This yields improved batch-versus-sample query trade-offs for finite-sum minimization, Markov decision processes, matrix games, and top-eigenvector computation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.12 is false as stated: joint (ξ,χ) approximation does not imply per-ξ pseudo-independence; the missing factor p in the TV bound is only one of two obstructions.","rationale":"The reader correctly identifies a missing factor p in the cube TV bound of Theorem 2.12. My independent check finds a second, more serious gap: the proof treats a joint high-probability approximation as if it were a high-probability event over ξ. The explicit counterexample shows the theorem as stated is false even in p=1. Since Theorem 2.6 invokes Theorem 2.12, the central sample-reuse reduction is unsupported as written. I do not regard this as fatal to the overall framework: for SVRG and TVRVI the χ seed is zero-bit, so the per-ξ issue disappears; the factor p is absorbed into \tilde O; and for VRMD1 the fix may require extra care. A CONDITIONAL verdict is therefore appropriate, contingent on a correct Theorem 2.12 and an audit of each sub-solver's failure decomposition.","tokens_in":42652,"tokens_out":27766,"duration_ms":276072,"concrete_test":"Re-derive Theorem 2.12 in a minimum working example: set p=1, f=0, η=1, ε=δ=0.2, Dξ=Dχ=Unif[0,1], τ=0.5, and A(ξ,χ)=1 if ξ≤0.4 and χ≤0.5, else 0. Compute P_ξ(d_TV(A_ξ+e, f+e)≤0.2) for e∼Unif[-0.5,0.5]. If the computed probability is 0.6 rather than 0.8, Theorem 2.12 is false as stated. Then check whether replacing the joint approximation hypothesis in Definition 2.1 by a per-ξ guarantee P_χ(failure)≤δ restores the theorem; if so, audit the application sub-solvers (especially VRMD1 in Theorem 5.11) to see which ones satisfy the stronger per-ξ condition.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 2.6 rests on Theorem 2.12, which claims that adding Unif^p(-τ,τ) output noise converts any (η',δ)-approximation into an (ε,δ)-pseudo-independent algorithm. The proof has two defects. First, the TV calculation for shifted p-dimensional cubes is incorrect: for an input on which A_ξ is η'-close to f, d_TV(A_ξ+e, f+e)=1-(1-η'/(2τ))^p ≈ pη'/(2τ), not ≤(η'/(2τ))^p; the noise scale must grow by a factor p. Second, and more fundamentally, Definition 2.1 only bounds P_{ξ,χ}(failure)≤δ. The proof implicitly needs failure to be confined to a 1-δ mass of ξ realizations, but Markov does not provide this. Concretely, take p=1, f=0, δ=ε=0.2, η=1, η'=0.2, τ=0.5, Dξ=Dχ=Unif[0,1], and A=1 if ξ≤0.4 and χ≤0.5, else 0. Then P_{ξ,χ}(|A|>0.2)=0.2, so the hypothesis holds. But for every ξ≤0.4, the law of A_ξ+e is a 1/2 mixture of a point at 0 and a point at 1, so its TV from Unif[-0.5,0.5] is 0.5; hence P_ξ(TV≤0.2)=0.6<0.8. Thus Theorem 2.12 is false as written, and the premise of Theorem 2.6 is not established. The framework may be repairable by requiring per-ξ high-probability approximation, or by amplifying the sub-solver failure probability to δ^2, but these changes are not in the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a general framework for reusing oblivious sample randomness across the outer iterations of variance-reduction algorithms. It introduces a notion of pseudo-independence and claims that adding uniform noise to a high-accuracy sub-solver makes the sub-solver pseudo-independent, so the same sample queries can be reused across n_outer sub-problem solves. The framework is applied to finite-sum minimization, discounted and average-reward MDPs, matrix games, and top-eigenvector computation, yielding improved full-batch/sample query trade-offs. A new outer-solver for discounted MDPs (the Proximal Reward Method) is also presented. The main technical engine is Theorem 2.6, which relies on Theorem 2.12 to convert a high-accuracy approximation into a pseudo-independent algorithm.","tokens_in":43094,"tokens_out":18582,"duration_ms":174642,"significance":"If correct, the sample-reuse framework would be a valuable and versatile contribution: it gives improved query-complexity trade-offs across several important optimization problems, and the PRM outer-solver for discounted MDPs has independent interest. The reductions in Sections 3-7 are mostly clean and build carefully on prior work; the pseudo-independence definition is a useful conceptual generalization of pseudo-determinism. However, the central technical lemma, Theorem 2.12, is false as stated, and the proof of Theorem 2.6 is therefore not established. Because every application theorem invokes Theorem 2.6, the claimed results are conditional on a repair of this lemma. The framework appears potentially repairable, but the required changes affect the definition of the approximation condition and the noise scaling, so the paper needs substantial revision before the results can be accepted.","major_comments":[{"comment":"The total-variation calculation in the proof of Theorem 2.12 is incorrect. For a realization y with ||y - f(u)||_∞ ≤ η', the laws of A_{ξ=s,χ=c}(u) + e and f(u) + e are p-dimensional uniform distributions on cubes of side 2τ shifted by y - f(u). Their total-variation distance is 1 - ∏_{i=1}^p (1 - |(y-f(u))_i|/(2τ)), which is at least 1 - (1 - η'/(2τ))^p ≈ p·η'/(2τ), not at most (η'/(2τ))^p. With the stated choice τ = η'/(2ε), this gives roughly pε-pseudo-independence, not (ε,δ)-pseudo-independence. Since Theorem 2.6 invokes Theorem 2.12 with ε = δ, the main sample-reuse theorem is not established as written.","section":"§2.3, Theorem 2.12"},{"comment":"The proof of Theorem 2.12 uses Eq. (1), a joint probability over (ξ,χ), to conclude that for 1-δ of realizations of ξ the law of A_{ξ,χ}+e is within TV distance ε of the smoothing. Joint small failure probability does not imply small failure probability for most realizations of ξ. Concretely, take p = 1, f ≡ 0, δ = ε = 0.2, η = 1, η' = 0.2, τ = 0.5, Dξ = Dχ = Unif[0,1], and A = 1 if ξ ≤ 0.4 and χ ≤ 0.5, and A = 0 otherwise. Then P_{ξ,χ}(|A-f| > 0.2) = 0.2, so A is an (η',δ)-approximation, but for every ξ ≤ 0.4 the law of A+e is a 1/2 mixture of a uniform on [0.5,1.5] and Unif[-0.5,0.5], which is TV distance 0.5 from Unif[-0.5,0.5]. Hence P_ξ(TV ≤ 0.2) = 0.6 < 0.8, and Theorem 2.12 is false as stated. A per-ξ high-probability condition or an amplification of the failure probability is needed; neither appears in the manuscript.","section":"§2.1, Definition 2.1 and Theorem 2.12"},{"comment":"The finite-precision version in Theorem A.1 repeats the two defects of Theorem 2.12. The claimed bound involving (⌈η/β⌉/⌊2t/β⌋)^p is again the wrong order: the relevant total-variation distance is at least a constant times p·η/t, and the inference from the joint approximation in Eq. (1) to a statement holding for 1-δ of realizations of ξ is not justified. Since Theorem A.1 is the implementable version of the construction, it must be corrected together with Theorem 2.12.","section":"Appendix A, Theorem A.1"},{"comment":"The proof of Theorem 4.11 applies Lemma 4.22 with η = ε/2 · (1-γ)/(1-γ') and then concludes 0 ≤ v⋆ - ε/2 1 ≤ v_{nouter}. However, the 'Consequently' part of Lemma 4.22 yields final error ε for this choice of η, because the lemma's condition is η ≤ (1-γ)/(2(1-γ')) ε_L and taking ε_L = ε makes the condition hold. Moreover, the full bound in Lemma 4.22 contains the positive term ((γ-γ')/(1-γ'))^T max(v⋆ - v(0)) in addition to the η-sum, which the proof bounds only by ε/2. Since v(0) = 0 and v⋆ is generally nonzero, the displayed conclusion 0 ≤ v⋆ - ε/2 1 ≤ v_{nouter} does not follow. The accuracy parameter ε' or the loop length must be adjusted, and this affects the correctness proof of the DMDP trade-off in Theorem 4.13.","section":"§4.2, Theorem 4.11 and Lemma 4.22"}],"minor_comments":[{"comment":"In the definition of H^1_Abar, the right-hand side should be ζ(u, Abar_{χ'}(u)), not ζ(Abar_{χ'}(u)); the first argument u is missing.","section":"§2.3, Definition 2.13, Eq. (4)"},{"comment":"In the base case, the second argument inside the second total-variation distance is written as ζ(u, A_{ξ=s,χ}(u)); it should be ζ(u, Abar_χ(u)).","section":"Appendix B, Lemma B.2, base case"},{"comment":"The theorem states that the algorithm uses sample queries of Type II, but the preceding text and the VRMD2 description say that the oblivious queries are row/column queries, which are Type I. The statement should say Type I.","section":"§5.2.2, Theorem 5.15"},{"comment":"The statement says 'For λ ≥ μ', but μ is not defined in the TopEV section; it should either be defined or replaced by the appropriate strong-convexity parameter, likely ρ ≥ λ' - λ1.","section":"§7, Theorem 7.7"},{"comment":"In the proof, the naming of the random seeds is confusing: the theorem uses χ' as the concatenated seed, but the proof defines a new A_{ξ,χ} with χ = (χ',ν). Please rename the variables to avoid ambiguity.","section":"§2.3, Theorem 2.12 proof"}],"recommendation":"major_revision","confidential_remarks":"The central lemma Theorem 2.12 is false as stated, and Theorem 2.6 is therefore unproven. The counterexample in the report is not contrived: it shows that the joint approximation condition in Definition 2.1 is insufficient for the per-ξ total-variation conclusion. A correct version likely needs a p-dependent noise width and either a per-ξ approximation condition or failure-probability amplification; the authors should also re-derive the consequences for all applications. The DMDP proof of Theorem 4.11 also appears to have a factor-of-two error in the application of Lemma 4.22. The paper has promising ideas and clean reductions, but at this stage the main results are not supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis is a serious, well-organized theory paper. The central idea—reuse the oblivious sample randomness across outer iterations by injecting uniform noise and tracking pseudo-independence—is genuinely new. The applications are real: improved full-batch/sample trade-offs for finite-sum minimization, a new PRM outer-solver for discounted MDPs, and a near-optimal matrix-vector complexity for ℓ2-ℓ2 matrix games. The writing is clear and the reductions are mostly careful.\n\nThe problem is Theorem 2.12, which is the engine of the framework. Its proof has two defects. First, the total-variation calculation for shifted p-dimensional cubes is wrong: for small η'/τ, the distance scales as pη'/τ, not (η'/τ)^p. This is fixable by scaling τ with a factor p, at polylog cost. Second—and more substantial—Definition 2.1 only gives a joint (ξ,χ) failure bound, while the smoothing argument needs per-ξ high-probability approximation. For sub-solvers with zero-bit χ (FSM, DMDPs, ℓ2-ℓ2 games), those coincide, so the issue is benign there. But for ℓ2-ℓ1 matrix games, χ is adaptive and carries real randomness; there, the theorem's hypothesis can hold while its conclusion fails. The concrete counterexample in the stress-test note (p=1, δ=ε=0.2) checks out: P_{ξ,χ}(failure)≤δ but P_ξ(TV≤ε)<1−δ.\n\nSo the manuscript is not correct as written, but the errors are repairable. I would not desk-reject. The framework is valuable and likely fixable by strengthening the approximation guarantee or amplifying sub-solver failure probabilities. The ℓ2-ℓ1 result needs a distinct argument because of the adaptive χ. As is, the claimed trade-offs are not all established, and the paper should go back for a major revision with a corrected Theorem 2.12 and a re-check of each application that relies on adaptive randomness.\n\nI'd send it to a careful referee. It is not citable in its current form, but the underlying ideas merit attention.\n\nBest,","headline":"Novel and useful sample-reuse framework, but the load-bearing Lemma 2.12 is wrong as written—likely fixable, so the paper deserves revision rather than rejection.","tokens_in":43640,"tokens_out":6918,"would_cite":false,"duration_ms":64799,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Reusing random samples across solver iterations cuts sample queries by an n_outer factor in several optimization problems.","keywords":["sample reuse","pseudo-independence","variance reduction","query complexity","finite-sum minimization","pseudo-determinism","batch-sample trade-off"],"falsifier":"One could compute, for a small example (e.g., p=2, a sub-solver with deterministic output), the exact total-variation distance between the distribution of the noisy sub-solver conditioned on a fixed seed and the smoothing distribution, and compare it to the bound eta'/(2*tau) claimed in Theorem 2.12; if it exceeds the bound by a factor proportional to p, the theorem's guarantee is not established as stated.","tokens_in":42461,"feed_emoji":"🔥","tokens_out":1356,"duration_ms":14364,"temperature":0.7,"pith_summary":"This paper claims that a wide class of variance-reduction algorithms can be modified to reuse the same random samples across all outer-loop iterations, cutting total sample queries by a factor equal to the number of iterations, without sacrificing correctness. This matters because it improves the best-known trade-off between expensive full-batch queries and cheap individual-sample queries for finite-sum minimization, top-eigenvector computation, matrix games, and Markov decision processes. The central mechanism is a new notion called pseudo-independence, which quantifies when a randomized sub-solver's output is nearly oblivious to its sample randomness once a small amount of uniform noise is added.","feed_headline":"Reusing random samples cuts solver query counts by a full factor","feed_subtitle":"A new pseudo-independence framework improves full-batch vs. sample trade-offs for optimization problems.","key_machinery":"The central object is the notion of pseudo-independence (Definition 2.5): a randomized algorithm A_{xi,chi} is (epsilon,delta)-pseudo-independent of its oblivious seed xi if there exists a smoothing algorithm that, for most draws of xi, produces a distribution within total variation distance epsilon of the original algorithm. The paper proves that adding uniform noise of width tau makes any high-accuracy sub-solver pseudo-independent, and then shows that repeated compositions of pseudo-independent algorithms have TV distance bounded by 2T(delta+epsilon), which yields the sample-reuse guarantee.","core_discovery":"The paper establishes that if an outer-solver is robust to bounded random noise and the sub-solver queries samples obliviously and solves to high accuracy, then the same sample randomness can be reused across all n_outer sub-problem solves. Formally, Theorem 2.6 shows that the sample-reusing version outputs a correct solution with probability 1 - O($n_outer^{2}$ * delta), reducing sample queries by a factor of n_outer. For finite-sum minimization this yields O~tilde($\\sqrt$($\\alpha$/mu)) batch queries and O~tilde(L/$\\alpha$) sample queries for any $\\alpha$ >= mu, improving on the prior O~tilde(L/$\\sqrt$(mu $\\alpha$)) sample bound. The same framework yields improvements for discounted and average-reward MDPs, ell2-ell2 and ell2-ell1 matrix games, and top-eigenvector computation.","pith_inferences":["The pseudo-independence framework could plausibly extend to non-oblivious sample queries if the sub-solver's adaptive randomness is also smoothed, though the paper only handles the oblivious case.","The improved sample-reuse trade-off for FSM suggests that the information-theoretic lower bound for sample complexity may need to be re-examined in the batch-sample model, since prior lower bounds do not account for sample reuse.","The PRM outer-solver for DMDPs may be applicable beyond variance reduction, e.g., to policy-gradient methods that solve lower-discount subproblems, though the paper does not explore this direction.","The numerical-stability variant in Appendix A suggests the framework can be implemented in finite precision with only a constant-factor degradation in the noise parameters, which is worth verifying empirically."],"forward_implications":["Finite-sum minimization can be solved with O~tilde(sqrt(alpha/mu)) full-batch queries and only O~tilde(L/alpha) sample queries, a strictly better trade-off than prior work for any alpha >= mu.","Generalized linear model regression can be solved reusing the same cached samples across all outer iterations, which may reduce memory retrieval and communication costs in distributed settings.","Discounted MDPs can be solved by a new Proximal Reward Method (PRM) that reduces a gamma-discounted problem to a sequence of gamma'-discounted problems, yielding a faster runtime in sparse-transition regimes.","ell2-ell2 matrix games are solvable in O~tilde(||A||_F^{2/3} epsilon^{-2/3}) matrix-vector queries, which is near-optimal due to known lower bounds."],"supporting_citations":[{"why":"Supplies the accelerated proximal point (APP) outer-solver for finite-sum minimization, establishing the baseline n_outer = O~tilde(sqrt(alpha/mu)) iteration count and the sub-problem structure.","marker":"[16]"},{"why":"Supplies SVRG as the stochastic variance-reduction sub-solver that the framework modifies to reuse samples.","marker":"[29]"},{"why":"Supplies the TVRVI sub-solver for discounted MDPs, which the framework modifies to reuse samples and which the PRM outer-solver builds upon.","marker":"[28]"},{"why":"Supplies the variance-reduced mirror descent sub-solvers VRMD1 and VRMD2 for matrix games, which the framework modifies to reuse samples.","marker":"[7]"},{"why":"Supplies the shift-and-invert power method reduction for top-eigenvector computation, which the framework applies to via an SVRG sub-solver.","marker":"[17]"}],"fun_headline_variants":["Sample reuse slashes queries in structured optimization","Pseudo-independent algorithms enable sample reuse","Reusing randomness across sub-solves improves trade-offs","Optimization query costs drop with sample reuse","Randomness reuse yields n-fold reduction in sample queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main load-bearing premise is that adding uniform noise of width tau = eta'/(2*epsilon) makes the noisy sub-solver (epsilon, delta)-pseudo-independent; the proof's total-variation bound may omit a factor of the dimension p, so the stated pseudo-independence guarantee may require rescaling in high dimensions.","fun_headline_variants_meta":{"raw":{"variants":["Sample reuse slashes queries in structured optimization","Pseudo-independent algorithms enable sample reuse","Reusing randomness across sub-solves improves trade-offs","Optimization query costs drop with sample reuse","Randomness reuse yields n-fold reduction in sample queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000273,"raw_usage":{"total_tokens":1605,"prompt_tokens":881,"completion_tokens":724,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":497,"completion_tokens_details":{"reasoning_tokens":655}},"tokens_in":497,"tokens_out":724,"duration_ms":7457,"temperature":1.0,"reasoning_tokens":655,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:37:26.220667+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One could compute, for a small example (e.g., p=2, a sub-solver with deterministic output), the exact total-variation distance between the distribution of the noisy sub-solver conditioned on a fixed seed and the smoothing distribution, and compare it to the bound eta'/(2*tau) claimed in Theorem 2.12; if it exceeds the bound by a factor proportional to p, the theorem's guarantee is not established as stated.","supporting_citations":[{"cited_title":"Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization","cited_arxiv_id":null,"evidence_quote":"Supplies the accelerated proximal point (APP) outer-solver for finite-sum minimization, establishing the baseline n_outer = O~tilde(sqrt(alpha/mu)) iteration count and the sub-problem structure."},{"cited_title":"Accelerating stochastic gradient descent using predictive variance reduction","cited_arxiv_id":null,"evidence_quote":"Supplies SVRG as the stochastic variance-reduction sub-solver that the framework modifies to reuse samples."},{"cited_title":"Variance reduction for matrix games","cited_arxiv_id":null,"evidence_quote":"Supplies the variance-reduced mirror descent sub-solvers VRMD1 and VRMD2 for matrix games, which the framework modifies to reuse samples."},{"cited_title":"Faster eigenvector computation via shift-and-invert preconditioning","cited_arxiv_id":null,"evidence_quote":"Supplies the shift-and-invert power method reduction for top-eigenvector computation, which the framework applies to via an SVRG sub-solver."}],"review_version":2}