{"id":"cd3f209e-c9f4-4d96-93c0-5f2c158c19d5","arxiv_id":"2411.13462","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Improved query complexity bounds for logconcave sampling, warm-start generation, isotropic rounding, and integration, with Rényi-infinity guarantees.","lead":"This paper presents faster algorithms for sampling, rounding, and integrating high-dimensional logconcave functions, the first complexity improvements for these problems in nearly two decades. A lifting trick converts the target function into a simple exponential distribution in one higher dimension, enabling strong error guarantees.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Rounding's spectral-gap claim (Prop. 4.7) is not implied by the stated step sizes; the effective gap of PS^{N_i} is at most ~1/log n, so the covariance-estimation lemma cannot be invoked as written.","rationale":"The reader's weakest_assumption focuses on Lemma 3.3, the LSI constant of the annealed measure under convex truncation. After checking the argument, that step appears plausible: the bounded perturbation ratio is Θ(1) on the bounded set ¯K, and convex truncation of a κ-strongly logconcave measure with Neumann boundary is a standard Bakry–Émery setting. The more concrete and load-bearing weakness is the spectral-gap/covariance-estimation step in the rounding algorithm, which the reader flagged only secondarily (the dependent-sample covariance estimator). Proposition 4.7's claimed 0.99 spectral gap does not follow from the stated parameters: N_i h_i ≈ n and CPI(µ_i) ≥ c n yield N_i·gap ≈ 1/(c log n), so the gap tends to 0 in n. This undermines the application of Lemma 4.5 and thereby the proof of Theorems 1.7 and the general-integration part of 1.8. The issue is likely fixable by increasing N_i or k_i by log n factors, so the verdict remains CONDITIONAL rather than REJECT: the headline complexity bounds could survive with polylog overhead, but the proof as written has a genuine gap in a load-bearing component.","tokens_in":62613,"tokens_out":36082,"duration_ms":362702,"concrete_test":"Instantiate a concrete well-rounded logconcave target: let µ_X = N(0, diag(n, 1, ..., 1)) restricted to a convex body of inradius 1 (e.g., an ellipsoid scaled so the longest axis has variance n and it contains the unit ball). For the lifted distribution µ, run one step of the Proximal Sampler with h = r²/(n² log n) (r = 1) and compute the L²(µ) spectral gap. The predicted one-step gap is h/CPI(µ) ≤ 1/(c n³ log n); composing N = n³ log n steps gives a gap of order 1/log n, not 0.99. If this is confirmed numerically or analytically, Proposition 4.7 must be revised (e.g., N_i needs an additional log n factor) and the covariance-estimation analysis must be reworked to account for the reduced effective sample size.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the rounding algorithm (Algorithm 4), Proposition 4.7 asserts that PS^{N_i}(µ_i,·,h_i) with N_i ≍ r_i^{-2} n^3 log n and h_i ≍ r_i^2 (n^2 log(r_i n))^{-1} has spectral gap at least 0.99. This is inconsistent with the paper's own mixing analysis. By Lemma 2.9 / Proposition 2.7, the Proximal Sampler's one-step χ² contraction is at most (1 + h/CPI(π))^{-2}, so its spectral gap is bounded above by h/CPI(π). For the lifted target µ_i in the rounding loop, the X-marginal has covariance with ∥Σ_X∥ = Ω(n) (Assumption 4.4 and Lemma 4.8), and CPI(µ_i) ≥ CPI(µ_i^X) ≥ c·n, using a linear test function along a maximal-variance direction. Hence the per-step gap is ≤ h_i/(c n) ≈ r_i^2/(c n^3 log n). After N_i steps, the gap of P^{N_i} is at most N_i · (per-step gap) ≈ 1/(c log n), since N_i h_i ≈ n. Even if one uses Klartag's upper bound CPI ≤ C n log n, the product is ≤ 1/(C log n), which tends to 0 as n→∞. Therefore P^{N_i} is not 0.99-expanding; the samples in Line 4 are not nearly independent, and Lemma 4.5 (which explicitly requires λ ≥ 0.99) does not apply to the covariance estimator in Line 5. Since the rounding theorem (1.7) and the general case of the integration theorem (1.8) rest on this covariance estimate, the central claim of improved rounding and integration depends on an unproven spectral condition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the query complexity of sampling, warm-start generation, isotropic rounding, and integration for arbitrary logconcave densities proportional to e^{-V}, given an evaluation oracle for the convex potential V. The authors lift the target to an exponential distribution π(x,t) ∝ e^{-nt} on the epigraph K = {(x,t) : V(x) ≤ nt}, whose x-marginal is exactly the original target. They analyze a Proximal Sampler for this lifted distribution, proving Rényi and Rényi-infinity mixing in terms of isoperimetric constants, then combine it with a tilted Gaussian cooling scheme for warm-start generation. The resulting sampler is applied to covariance-estimation-based isotropic rounding and to an annealing-based integration algorithm with a β-mixing analysis of dependent samples. The stated results are Theorems 1.5-1.8, claiming ~O(n^2(R^2∨n) polylog(1/(ηε))) queries for warm-start sampling, ~O(n^{3.5} polylog R) for rounding, and ~O(n^3/ε^2) for integration of well-rounded functions, matching the best known rates for uniform distributions over convex bodies.","tokens_in":62976,"tokens_out":23541,"duration_ms":257409,"significance":"If fully established, this would be a substantial advance: it would give the first complexity improvements in nearly two decades for general logconcave sampling, rounding, and integration, and would match the best-known rates for the uniform case while providing stronger Rényi-infinity output guarantees. The diffusion-based reduction to an exponential distribution is elegant, the parameter schedules are explicit, and the streamlined handling of dependent samples is a genuine methodological contribution. The paper also builds transparently on the authors' own prior work and on Klartag's isoperimetric bounds. However, two load-bearing proof points are not yet fully supported: the spectral-gap claim in the rounding algorithm is not implied by the stated step sizes and the paper's own isoperimetric bounds, and the extension of the heat-flow lemma to unbounded support is asserted rather than proved. These issues affect the rounding and integration theorems as written, although the natural repairs appear compatible with the stated ~O complexity claims.","major_comments":[{"comment":"Proposition 4.7 asserts that PS^{N_i}(µ_i,·,h_i) with N_i ≍ r_i^{-2} n^3 log n and h_i ≍ r_i^2 (n^2 log(r_i n))^{-1} has spectral gap at least 0.99, and Lemma 4.5 is then invoked for the covariance estimator in Line 5. This is not supported by the paper's own mixing bounds. Lemma 2.9 gives per-step χ² contraction by (1+h/CPI(π))^{-2}; for a reversible chain this certifies an L² contraction factor at most (1+h/CPI)^{-N} over the N composed steps. The paper's stated isoperimetric bound CPI(µ_i) ≤ C∥Σ_i∥ log n (Section 1.1 and [Kla23]), together with Assumption 4.4 and Lemma 4.8, allows CPI(µ_i) as large as C n log n. Substituting the displayed h_i and N_i gives N_i h_i/CPI ≲ (r_i^{-2} n^3 log n) · r_i^2/(n^3 log^2 n) = O(1/log n), so the argument certifies only a spectral gap of order 1/log n, not 0.99. Therefore Lemma 4.5, which explicitly requires λ ≥ 0.99, cannot be applied as written, and the covariance estimates underlying Theorem 1.7 and the general case of Theorem 1.8 are not established. Increasing N_i by a polylog factor appears to repair this within the stated ~O bounds, but the current proof is incomplete.","section":"§4.1, Proposition 4.7"},{"comment":"The text extends [KVZ24, Lemma 22] from bounded to unbounded support in a single sentence, citing [Fol99, Theorem 8.15] for almost sure pointwise convergence of π*N(0,εI) to π. Pointwise convergence of the mollified density does not by itself establish the existence of the forward/backward heat-flow solutions on (0,h] or the lower-semicontinuity step lim_{t↓0} Rq(µ←_{h-t}∥πP_t) ≥ Rq(µ←_h∥π) that Lemma 2.9 needs on the unbounded epigraph K = {V ≤ nt}. Since Lemma 2.9 is the basis for the PS^exp mixing theorem (Theorem 2.15) and hence for the warm-start, rounding, and integration results, this extension should be proved in detail or replaced with a precise reference.","section":"§2.2.1, Lemma 2.8"}],"minor_comments":[{"comment":"Line 4 uses the notation δ_{Z0} as the initial distribution although the preceding line only guarantees R∞(law(Z0)∥µ) ≤ log 2; the initial law should be written as law(Z0), not a point mass.","section":"§4, Algorithm 4, Line 4"},{"comment":"In the display labeled (v), the factor (1 − d_{σ²})^{-1} refers to a quantity d_{σ²} that is never defined; please define it or remove it.","section":"§3.2.2, Lemma 3.9"},{"comment":"The assertion that convex truncation of a strongly logconcave measure preserves the log-Sobolev constant is cited to [Wan13, Theorem 3.3.2]; since this is a nonsmooth setting, please state the quoted theorem explicitly and note that ar K is bounded, so no aspect-ratio dependence enters.","section":"§3.2.1, Lemma 3.3"},{"comment":"The notation K_δ for the δ-blow-up is defined in Lemma 2.12 but used earlier in Lemma 2.13 without a definition; add a sentence defining K_δ = {x : d(x,K) ≤ δ} before its first use.","section":"§2.2.2, Lemma 2.12"}],"recommendation":"major_revision","confidential_remarks":"This is a serious contribution: the exponential-lift reduction and the diffusion-based proximal sampler are likely to be influential, and the main sampling and warm-start results appear sound up to the heat-flow extension. The rounding gap is real but localized: Proposition 4.7's spectral-gap claim is not implied by the stated parameter choices and the paper's own CPI bounds. The natural repair, increasing N_i by a polylog factor, is compatible with the stated ~O complexity bounds, so I do not recommend rejection. The paper's reliance on several of the authors' own prior results is clearly disclosed and appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this paper delivers the first real complexity improvement in nearly two decades for general logconcave sampling, rounding, and integration, and it matches the uniform-distribution rates up to log factors. Second, the sampling half is in good shape; the rounding half has a load-bearing spectral-gap claim that is not proven as stated, but looks patchable.\n\nThe new ingredient is the exponential lift to R^{n+1}, which turns a non-smooth convex potential into a linear potential plus a convex constraint. The X-marginal is exactly the target, verified by direct integration in Proposition 2.3, and the lifted problem fits the proximal sampler framework from the uniform case. The mixing analysis via Poincaré and log-Sobolev is standard and careful, and the per-step rejection bounds in Lemmas 2.14 and 3.10 are the real technical work—they check out. Tilted Gaussian Cooling is a clean generalization of [CV18], and the R∞ output guarantees are a genuine strengthening over the usual TV-distance results.\n\nSoft spots, in order of how soft they are.\n\n1. Proposition 4.7: the claim that P^{N_i} has spectral gap at least 0.99 does not follow from the stated N_i and h_i. With the known Klartag upper bound CPI = O(n log n) for the lifted target, the product N_i h_i / CPI is O(1/log n), not a constant. The stress-test note is right about this, even if its arithmetic is a little off. Increasing N_i by a log factor fixes it and keeps the ~O(n^{3.5}) complexity, so I'd call it a proof gap rather than a fatal flaw. As written, though, the covariance-estimation lemma cannot be invoked, and the rounding and general-integration theorems rest on this unproven premise.\n\n2. Lemma 3.3's LSI bound depends on the cited [Wan13] claim that convex truncation preserves the log-Sobolev constant. That's plausible, but the paper doesn't prove it, and the truncated set is an unbounded-in-t cylinder. If preservation introduces an aspect-ratio factor, the annealing schedule would degrade. This deserves a proof or a more careful citation.\n\n3. The dependent-sample covariance estimator comes from a preprint, [KZ24]. That's a real dependency, but the result is formal and the paper states it explicitly.\n\nThe central sampling theorem (Theorem 1.5) does not rely on these shaky components, and it looks solid. The paper is clearly written, the claims are explicit, and the authors are honest about what is deferred.\n\nWho should read it: anyone working on logconcave sampling, volume computation, or Bayesian inference. It deserves a serious referee—not a desk reject. I'd send it to review, with the expectation of a revision round addressing Proposition 4.7 and Lemma 3.3.","headline":"First real improvement in nearly two decades for general logconcave sampling, rounding, and integration—the sampling half is solid, the rounding half has a patchable spectral-gap gap.","tokens_in":63538,"tokens_out":8444,"would_cite":true,"duration_ms":81289,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","60J22","65C05","52A23"],"pacs":[],"model":"deepseek-v4-flash","headline":"Arbitrary logconcave sampling, rounding, and integration can be performed at query complexities matching uniform convex bodies, via a lifted exponential diffusion sampler.","keywords":["logconcave sampling","proximal sampler","Rényi divergence","log-Sobolev inequality","isotropic rounding","logconcave integration","Gaussian cooling","exponential reduction"],"falsifier":"Estimate numerically the log-Sobolev constant of $\\mu_{\\sigma^2,\\rho}\\propto \\exp(-\\|x\\|^2/(2\\sigma^2)-\\rho t)$ restricted to a long, thin convex cylinder $\\overline K$ with fixed $\\sigma^2$ but growing aspect ratio; if the constant grows superlinearly in the aspect ratio rather than staying $O(\\sigma^2\\vee l^2)$, the query bounds of Theorems 1.6 and 1.8 collapse.","tokens_in":62381,"feed_emoji":"📐","tokens_out":9036,"duration_ms":85085,"temperature":0.7,"pith_summary":"This paper claims that sampling, rounding, and integrating arbitrary logconcave functions can all be sped up, for the first time in nearly two decades, by lifting each target density to an exponential distribution in one higher dimension and then running a diffusion-based proximal sampler. From a warm start, the paper proves an $R_q$-mixing rate governed by the operator norm of the covariance rather than its trace; without a warm start, its tilted Gaussian cooling generates an $R_\\infty$-warm start in $\\widetilde{O}(n^2(R^2\\vee n))$ queries; and the same machinery gives 1.01-isotropic rounding in $\\widetilde{O}(n^{3.5})$ queries and $(1+\\varepsilon)$-multiplicative integration in $\\widetilde{O}(n^3/\\varepsilon^2)$ queries for well-rounded functions. If the claims are right, general logconcave densities inherit the best-known query complexities that were previously available only for uniform distributions over convex bodies. The paper also argues that the stronger Rényi-divergence guarantees simplify the statistical analysis of dependent samples in the integration routine.","feed_headline":"A lifted diffusion breaks a 20-year logconcave sampling barrier","feed_subtitle":"General logconcave functions match the best known rates for uniform convex bodies.","key_machinery":"The central object is the lifted exponential distribution $\\pi(x,t)\\propto e^{-nt}$ restricted to the convex epigraph-type set $K=\\{(x,t):V(x)\\le nt\\}$. This reduction linearizes the potential and makes the conditional law of $X$ given $T$ uniform on a level set of $V$. The proximal sampler $\\mathrm{PS}_{\\mathrm{exp}}$ carries the argument: one step draws $y\\sim \\mathcal{N}(z,hI_{n+1})$ (forward heat flow) and then draws $z\\sim \\mathcal{N}(y-h\\alpha,hI_{n+1})|_K$ (the time-reversed backward step), implemented by rejection sampling with a threshold. The mixing analysis uses Poincaré and log-Sobolev contraction, while $R_\\infty$ guarantees come from uniform ergodicity of the chain. Tilted Gaussian Cooling then anneals through measures $\\mu_{\\sigma^2,\\rho}\\propto \\exp(-\\|x\\|^2/(2\\sigma^2)-\\rho t)|_{\\overline K}$, whose log-Sobolev constant is bounded by $\\sigma^2\\vee l^2$ via the Bakry-Émery criterion and the preservation of that constant under convex truncation.","core_discovery":"The central discovery is that general logconcave sampling can be handled without smoothness or gradient-Lipschitz assumptions. The paper reduces the target $\\pi_X\\propto e^{-V}$ to the exponential distribution $\\pi(x,t)\\propto e^{-nt}\\mathbf{1}[V(x)\\le nt]$ on $\\mathbb{R}^{n+1}$, whose $X$-marginal is exactly $\\pi_X$. A proximal sampler alternating forward Gaussian heat flow and backward truncated-Gaussian sampling mixes at a rate controlled by the Poincaré constant of the target; a tilted Gaussian cooling schedule over these lifted distributions produces an $O(1)$-warm start; and covariance estimation with dependent samples turns the sampling guarantee into isotropic rounding. The resulting complexity bounds match the best-known rates for uniform distributions over convex bodies and, for well-rounded functions, the integration bound is $\\widetilde{O}(n^3/\\varepsilon^2)$.","pith_inferences":["An extension the paper leaves implicit is that the same lifting trick may apply to other non-smooth, non-gradient settings, since the reduction requires only convexity of $V$, not any smoothness of the sampler's drift.","Because the sampler provides $R_\\infty$ guarantees directly, it is a natural candidate for differentially private logconcave sampling at essentially the same query cost, a connection not developed here.","A testable consequence of the improved mixing rate is that on long, thin logconcave targets the number of oracle calls should scale with the largest variance direction rather than the total variance; an empirical comparison against hit-and-run-style samplers would make the improvement visible."],"forward_implications":["Any logconcave distribution can be sampled to $R_\\infty$ error in $\\widetilde{O}(n^2(R^2\\vee n))$ evaluation queries, matching the uniform convex-body rate.","Warm-start sampling mixes with a rate depending on $\\|\\mathrm{Cov}\\pi_X\\|$ instead of $\\mathrm{tr}(\\mathrm{Cov}\\pi_X)$, making the sampler faster on elongated targets.","The $\\widetilde{O}(n^{3.5})$ rounding algorithm removes the polynomial dependence on the ambient radius $R$, leaving only polylogarithmic factors.","Integration of a well-rounded logconcave function costs $\\widetilde{O}(n^3/\\varepsilon^2)$ queries, improving the prior $\\widetilde{O}(n^4/\\varepsilon^2)$ bound.","The strong $R_\\infty$ and $R_q$ output guarantees let the integration analysis replace delicate coupling arguments with simple $\\beta$-mixing bounds."],"supporting_citations":[{"why":"Introduces the In-and-Out proximal sampler for uniform convex bodies that this paper extends to exponential distributions.","marker":"[KVZ24]"},{"why":"Supplies the R∞-divergence boosting and uniform-ergodicity lemmas used for the annealing samplers.","marker":"[KZ25]"},{"why":"Gives the divergence contraction of the proximal sampler under Poincaré and log-Sobolev inequalities used throughout the mixing analyses.","marker":"[CCSW22]"},{"why":"Provides Gaussian Cooling, the annealing schedule generalized here to tilted Gaussian cooling.","marker":"[CV18]"},{"why":"Sets the previous best complexities for logconcave sampling, rounding, and integration that the paper improves.","marker":"[LV06a]"},{"why":"Contributes the isotropic-rounding loop of sample, estimate covariance, and scale up small eigen-directions adapted in Section 4.","marker":"[JLLV21]"},{"why":"Yields the logarithmic Poincaré bound that converts covariance operator-norm bounds into mixing rates.","marker":"[Kla23]"},{"why":"Gives the convex-truncation preservation of the log-Sobolev constant used in the key LSI bound of Lemma 3.3.","marker":"[Wan13]"},{"why":"Provides covariance-estimation guarantees for dependent Markov-chain samples used in the rounding algorithm.","marker":"[KZ24]"},{"why":"Defines the proximal sampler framework whose two conditional-sampling steps PSexp implements.","marker":"[LST21]"}],"fun_headline_variants":["Lifted diffusion beats 20-year logconcave sampling wall","New diffusion matches convex body rates for logconcave","Algorithmic diffusion cracks logconcave complexity ceiling","20-year barrier broken for logconcave sampling, rounding","Proximal diffusion solves logconcave sampling, rounding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that truncating a tilted Gaussian measure to a convex set does not degrade its log-Sobolev constant by a factor tied to the set's aspect ratio; if convex truncation introduces such a factor, the annealing and integration query bounds no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Lifted diffusion beats 20-year logconcave sampling wall","New diffusion matches convex body rates for logconcave","Algorithmic diffusion cracks logconcave complexity ceiling","20-year barrier broken for logconcave sampling, rounding","Proximal diffusion solves logconcave sampling, rounding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000148,"raw_usage":{"total_tokens":1107,"prompt_tokens":781,"completion_tokens":326,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":397,"completion_tokens_details":{"reasoning_tokens":247}},"tokens_in":397,"tokens_out":326,"duration_ms":3367,"temperature":1.0,"reasoning_tokens":247,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:23:54.650215+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Estimate numerically the log-Sobolev constant of $\\mu_{\\sigma^2,\\rho}\\propto \\exp(-\\|x\\|^2/(2\\sigma^2)-\\rho t)$ restricted to a long, thin convex cylinder $\\overline K$ with fixed $\\sigma^2$ but growing aspect ratio; if the constant grows superlinearly in the aspect ratio rather than staying $O(\\sigma^2\\vee l^2)$, the query bounds of Theorems 1.6 and 1.8 collapse.","supporting_citations":[],"review_version":1}