{"id":"31fb4410-a820-44cc-a300-5cbb2e419ed7","arxiv_id":"2505.01937","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First sub-cubic cold-start algorithms for near-isotropic logconcave sampling (about n^2.75 queries), via relaxed Rényi warmness and improved log-Sobolev constants.","lead":"This paper gives the first sub-cubic algorithm for sampling from logconcave distributions from a cold start in high dimension, with about n^2.75 queries for near-isotropic bodies. A smart generalist should read it because breaking the cubic barrier in high-dimensional sampling changes the baseline for volume estimation, Bayesian inference, and privacy applications.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2 proof has an edge-case gap when the normalized mean R < 1; this is the lemma that underlies the improved annealing phase.","rationale":"The main algorithm chain (Renyi bounds, relaxed warmness, phase complexity) is coherent, and the n^{2.75} claim for near-isotropic inputs is well supported. The reader identified Theorem 3.2 as the weakest assumption, and we agree it is the load-bearing internal lemma. However, our reading found a specific technical gap (the R < 1 case in the proof) rather than evidence of covariance inflation. This gap is patchable and does not affect the flagship near-isotropic case, so the verdict should remain CONDITIONAL pending the patch and the other flagged clarifications (e.g., the use of D in Theorem 1.4).","tokens_in":49858,"tokens_out":44851,"duration_ms":420439,"concrete_test":"Re-derive Theorem 3.2 after replacing R by R∨1 and using the shell {||Y|| in [R∨1 +/- t]} with t = c1 C_PI^{1/2} log(R∨1); check that the condition h ≳ (R∨lambda^{1/2}) lambda^{1/2} polylog suffices. Since for logconcave distributions R ≥ c lambda^{1/2}, this is within a constant factor of the stated bound. Alternatively, numerically compute ||cov(pi gamma_h)|| for pi uniform on a thin slab K = [-1,1] × [-epsilon,epsilon]^{n-1} at h ≈ log^2 n and verify the covariance remains O(1).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The covariance-control lemma Theorem 3.2 is the linchpin of the sub-cubic claim: it justifies the fast annealing phase at sigma^2 ≈ R lambda^{1/2}. After scaling to unit covariance, the proof defines R := E_nu||Y|| and asserts R >= 1. This is false for logconcave nu with ||cov nu|| = 1 (e.g., 1D standard normal has R ≈ 0.8; in n dimensions, any near-rank-one logconcave with lambda = 1 has R ≈ 0.8). The proof then sets t = c1 C_PI^{1/2} log R, which is negative for R < 1, so the thin-shell S = {||Y|| in [R +/- t]} is not well-defined and the denominator lower bound D >= exp(-R^2/(2eta)) nu(S) collapses. Thus the written proof does not establish the covariance bound for distributions with R < lambda^{1/2}. Since the annealing threshold and the n^{2.75} exponent for near-isotropic inputs (where R ~ sqrt(n) >> 1) are not affected, this is a proof gap rather than a demonstrated falsehood; but it must be closed before Theorem 3.2, Corollary 1.7, and Theorem 1.8 for general inputs can be considered rigorous.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops faster cold-start sampling algorithms for convex bodies and general logconcave distributions. Its main results are: (1) proximal samplers for uniform and truncated Gaussian distributions are shown to mix under an R_c-warm start with c = polylog(n), rather than the previous R∞-warmness; (2) a new log-Sobolev bound CLSI(π) ≲ D||cov π||^{1/2} polylog for compactly supported logconcave π, interpolating the known D and D² bounds; (3) a covariance-control lemma stating that Gaussian weighting of a logconcave measure does not inflate the covariance when the Gaussian variance is at least roughly R λ^{1/2} polylog; and (4) annealing algorithms based on these ingredients that achieve ~O(n² R^{3/2} λ^{1/4}) membership queries for uniform distributions and ~O(n² max{n^{1/2}, R^{3/2}(λ^{1/4}∨1)}) evaluation queries for general logconcave distributions, hence n^{2.75} in the near-isotropic case. Appendix A gives an alternative stochastic-localization proof of the LSI bound.","tokens_in":50080,"tokens_out":18261,"duration_ms":195690,"significance":"If the technical gaps are closed, this is a substantial advance: it is the first claimed sub-cubic sampling algorithm for near-isotropic inputs from a cold start, and the relaxation of warmness from R∞ to R_c for proximal samplers appears to be a genuinely new and useful contribution. The paper is well structured, the main mixing calculations in Sections 2 and 4 are coherent, and the Rényi-divergence versions of the annealing lemmas are of independent interest. The main risk is not an internal inconsistency in the sampling framework but a specific unproven edge case in the covariance-control theorem, on which the general-input complexity bound rests.","major_comments":[{"comment":"The proof of Theorem 3.2 does not currently handle the regime where the normalized radius R is small. After scaling to unit covariance, the proof defines R := Eν||·||2 and asserts R ≥ 1. If this means Eν||Y||, the assertion is false: even a one-dimensional standard Gaussian has E|Z| ≈ 0.8, and a near-rank-one logconcave ν with ||cov ν|| = 1 behaves roughly like this. If R instead means sqrt(Eν||Y||²), then the theorem statement, which uses the first moment R = Eπ||·||, is not what is proved. The subsequent shell S = {||Y|| ∈ [R ± t]} requires t = c1 C_PI^{1/2} log R > 0, so for R < 1 the set is not well-defined and the denominator lower bound D ≳ exp(−R²/(2η)) ν(S) collapses. This is a proof gap rather than a demonstrated falsehood, but it is load-bearing because Corollary 3.3 and the annealing threshold in Theorems 4.2 and 5.1 rely on Theorem 3.2 for general inputs. Please revise the statement to use max(R, λ^{1/2}) (or another quantity satisfying the needed lower bound), or supply a separate argument for R < λ^{1/2}.","section":"§3.2, Theorem 3.2"},{"comment":"The treatment of approximate annealing states is incomplete. The triangle-inequality argument in §1.2.3 successfully controls the final TV error, but it does not establish that the actual distribution γ̂_{i−1} starting phase i is R_c-warm with respect to γ_i, which is what Theorem 2.2 requires to bound the query complexity of that phase. Boundedness of the clipped per-step cost ℓ^{-1}∧N and TV closeness would give an extra Nε term in the expected query count, so the argument is likely repairable, but it is not written. Please add the explicit accounting for the way approximate starts affect both the failure probability and the expected number of backward-step trials in each subsequent annealing phase.","section":"§1.2.3 and §4.2 (Lemma 4.8)"}],"minor_comments":[{"comment":"Result 2 references §A for the LSI bound for strongly logconcave distributions, but the main proof of Corollary 3.3 is in §3.3; §A contains an alternative stochastic-localization proof. Please correct the cross-reference.","section":"§1.1 and §3.3"},{"comment":"The lemma is stated for a distribution with support of diameter R, but the proof uses sup_νu ||X|| ≤ R. This requires the support to be contained in a ball of radius R, not merely to have diameter R. The annealing application uses K ∩ B_R(0), so the statement should say 'support contained in B_R(0)' to match the proof.","section":"Lemma 4.5"},{"comment":"There is minor notational drift between MemR(K), MemD(K), and Mem_{x0,R}(K) across Theorem 1.3, Theorem 1.4, Theorem 2.1, and Theorem 2.2. Please make the roles of D, R, and λ consistent in all statements.","section":"Definitions and theorem statements"},{"comment":"The expression 'R := Eν||·||2 (≥ 1)' is ambiguous: it should be clarified whether R is the first moment of the norm or the square root of the second moment, since the proof's shell argument depends on this distinction.","section":"§3.2, proof of Theorem 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically rich and the main near-isotropic claim is likely salvageable, but Theorem 3.2 is a central lemma whose stated proof has a real edge-case gap. I would send the paper back for a careful repair of Theorem 3.2 and for an explicit treatment of approximate annealing starts before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers the first sub-cubic cold-start sampling algorithm for near-isotropic logconcave distributions: ~O(n^{2.75}) queries instead of the cubic barrier that has held since Lovász–Simonovits and Cousins–Vempala. The two structural improvements are real: relaxing the proximal sampler's warmness requirement from R_infty to R_c with c = ~O(1), and a new interpolated log-Sobolev inequality for strongly logconcave distributions with compact support. Both are derived from explicit assumptions, and the Rényi annealing lemmas generalize the q=2 results correctly. I checked the main chain from Section 4 to Theorem 1.8 for the near-isotropic case and it goes through.\n\nThe stress-test note lands. In the proof of Theorem 3.2 the authors set R := E_nu||Y|| and assert R >= 1 after scaling to unit covariance. That is false: a one-dimensional standard normal has R ≈ 0.8, and in n dimensions a logconcave distribution can have ||cov||=1 and R<1 by being effectively one-dimensional. The proof sets t = c1 C_PI^{1/2} log R, which is negative when R<1, making the thin-shell set S ill-defined and the lower bound on the denominator collapse. So Theorem 3.2, Corollary 1.7, and the general-input versions of Theorems 1.8 and 1.10 are not rigorous as written. The near-isotropic case has R ~ sqrt(n) >> 1, so the headline n^{2.75} result is untouched. The flaw is a proof gap rather than a counterexample, and it looks patchable — handle R < 1 separately — but it has to be closed.\n\nTwo small things. Theorem 1.4 invokes a support diameter D under an oracle that only reveals R; the truncation in Section 4.2 suggests this is an omitted assumption rather than an error, but it should be stated. And the paper leans on external results (Bizeul, Milman, Klartag) without re-proving them; that is the norm in this literature, not a defect.\n\nWho is this for: anyone working on high-dimensional sampling or volume algorithms. It deserves a serious referee. My recommendation: send it to peer review and make the authors fix the R<1 case in Theorem 3.2 before the general claims are accepted; the near-isotropic result is the main event and it holds.","headline":"First sub-cubic cold-start sampling for near-isotropic inputs, with a real but patchable proof gap in the covariance-control lemma that does not touch the main n^2.75 claim.","tokens_in":50643,"tokens_out":4832,"would_cite":true,"duration_ms":46540,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68Q25","60J22","52A23"],"pacs":[],"model":"deepseek-v4-flash","headline":"Cold-start sampling of logconcave densities in near-isotropic position runs in $\\widetilde{O}(n^{2.75})$ queries, breaking a cubic barrier with relaxed R\\'enyi warmness and an improved log-Sobolev bound.","keywords":["logconcave sampling","cold start","warm start","Gaussian cooling","Rényi divergence","log-Sobolev inequality","proximal sampler","convex body sampling"],"falsifier":"Take a concrete non-Gaussian logconcave family — for instance the uniform distribution on a long thin box, or an affine image of the unit cube, in dimension $n$ — with known first moment $R$ and covariance norm $\\lambda$, and numerically compute the operator norm of $\\mathrm{cov}(\\pi\\gamma_h)$ at $h = C R\\lambda^{1/2}\\log^2n\\log^2(R^2/\\lambda)$ for a range of universal constants $C$. If the ratio $\\|\\mathrm{cov}(\\pi\\gamma_h)\\|/\\lambda$ exceeds any fixed universal constant at the stated threshold, Theorem 3.2 is false and the $n^{2.75}$ annealing schedule cannot be sustained.","tokens_in":49622,"feed_emoji":"🎲","tokens_out":12027,"duration_ms":104669,"temperature":0.7,"pith_summary":"Sampling from an arbitrary logconcave density without a warm start has long faced a cubic barrier in the dimension: every known algorithm paid a warm-start generation penalty that left total query complexity at least cubic. This paper breaks that barrier for inputs in near-isotropic position, establishing that uniform sampling from a convex body given by a membership oracle costs $\\widetilde{O}(n^{2.75})$ queries from a cold start, and that arbitrary logconcave densities given by an evaluation oracle admit the same exponent. The improvement comes from two ingredients: showing the proximal sampler only needs polylog-order R\\'enyi warmness instead of the stringent infinity-R\\'enyi warmness required since the first Ball-walk analyses in 1991, and proving a sharper log-Sobolev inequality for Gaussian-weighted logconcave measures with compact support. If correct, this removes the warm-start bottleneck that has persisted for three decades and makes sub-cubic sampling the new state of the art for well-rounded inputs.","feed_headline":"Near-isotropic sampling from a cold start drops to ~n^2.75 queries","feed_subtitle":"Relaxed warmness and a tighter log-Sobolev inequality break the cubic query barrier.","key_machinery":"The argument is carried by three mechanisms. (1) A covariance-control lemma (Theorem 3.2): for a logconcave measure $\\pi$ with first moment $R = E_\\pi\\|\\cdot\\|$ and largest covariance eigenvalue $\\lambda$, the Gaussian-weighted measure $\\pi\\gamma_h$ satisfies $\\|\\mathrm{cov}(\\pi\\gamma_h)\\| \\lesssim \\|\\mathrm{cov}\\,\\pi\\|$ once $h \\gtrsim R\\lambda^{1/2}\\log^2 n\\log^2(R^2/\\lambda)$; the proof uses Lipschitz concentration under the Poincar\\'e inequality, a thin-shell decomposition, and co-area/integration-by-parts estimates. (2) An interpolated log-Sobolev bound (Theorem 3.1 and Corollary 1.7): for logconcave $\\pi$ supported in a set of diameter $D$, $C_{\\mathrm{LSI}}(\\pi) \\lesssim \\max\\{D\\lambda^{1/2}, D^2\\wedge\\lambda\\log^2 n\\}$, and consequently $C_{\\mathrm{LSI}}(\\pi\\gamma_h) \\lesssim D\\lambda^{1/2}\\,\\mathrm{polylog}$ for all $h>0$, obtained by combining the known equivalence between Gaussian concentration and the log-Sobolev inequality for logconcave measures with two exponential-concentration bounds (one classical under the Poincar\\'e inequality, one derived from stochastic localization). (3) R\\'enyi-divergence annealing lemmas (Lemmas 4.4 and 4.5) that bound $R_q$ between consecutive annealing distributions and justify the accelerated variance schedule $\\sigma^2 \\leftarrow \\sigma^2(1 + \\sigma/(q^{1/2}R))$. The proximal sampler for uniform and truncated-Gaussian targets is the sampling workhorse whose required warmness drops from $R_\\infty$ to $R_c$ with $c = \\widetilde{O}(1)$.","core_discovery":"The paper's central claim is that the cubic barrier for cold-start sampling is not intrinsic. For a convex body $K$ given by a membership oracle with an enclosed unit ball and second-moment radius $R$, and uniform target $\\pi$ with covariance operator norm $\\lambda$, Theorem 1.8 asserts an algorithm that returns a sample $\\varepsilon$-close in TV distance using $\\widetilde{O}(n^2 R^{3/2}\\lambda^{1/4}\\,\\mathrm{polylog}(1/\\eta\\varepsilon))$ membership queries in expectation; when $\\pi$ is near-isotropic this is $\\widetilde{O}(n^{2.75})$, the first sub-cubic cold-start bound. Theorem 1.10 extends the same $n^{2.75}$ exponent to arbitrary logconcave densities given an evaluation oracle, with complexity $\\widetilde{O}(n^2\\max\\{n^{1/2}, R^{3/2}(\\lambda^{1/4}\\vee 1)\\})$. The engine is a faster Gaussian-cooling schedule: because the proximal sampler now mixes from only polylog-order R\\'enyi warmness, the annealing variance $\\sigma^2$ can be multiplied by $1 + \\sigma/(q^{1/2}R)$ rather than $1 + \\sigma^2/R^2$, and once $\\sigma^2$ exceeds $R\\lambda^{1/2}$ polylog, the new log-Sobolev bound makes each phase cheaper still. Sampling a standard Gaussian truncated to an arbitrary convex body drops to $\\widetilde{O}(n^{2.5})$ queries.","pith_inferences":["The covariance-control lemma (Theorem 3.2) is the piece the whole speedup leans on; if Gaussian weighting can inflate covariance beyond $O(\\lambda)$ at the stated threshold for some logconcave family, the accelerated phase would require a larger variance and the sub-cubic exponent would dissolve. Testing this lemma numerically on anisotropic logconcave families (slabs, affine images of cubes) woul","The same template — R\\'enyi-warm annealing plus an interpolated log-Sobolev bound — should transfer to other samplers whose mixing is controlled by Poincar\\'e or log-Sobolev constants, such as constrained Hamiltonian or Langevin methods, where warmness has likewise been a bottleneck; the paper does not explore this extension.","The $n^{2.75}$ exponent is unlikely to be final: the schedule's slope is set by the ratio $\\sigma/R$ in the annealing multiplier, and any improvement in the covariance-control threshold (for instance replacing Poincar\\'e-based concentration with thin-shell estimates) would lower the exponent further, with the $\\widetilde{O}(n^2)$ warm-start mixing bound as the natural target."],"forward_implications":["Cold-start uniform sampling from a convex body in near-isotropic position costs $\\widetilde{O}(n^{2.75})$ membership queries instead of the previous cubic bound from Gaussian cooling, with the same total-variation guarantee.","Sampling a standard Gaussian truncated to an arbitrary convex body costs $\\widetilde{O}(n^{2.5})$ queries, improving the previous cubic bound by a factor of $n^{1/2}$.","Arbitrary logconcave densities given by an evaluation oracle inherit the same $n^{2.75}$ exponent for near-isotropic inputs, at cost $\\widetilde{O}(n^2\\max\\{n^{1/2}, R^{3/2}(\\lambda^{1/4}\\vee 1)\\})$.","The warmness requirement for the proximal sampler drops from infinity-R\\'enyi divergence (essentially a pointwise density-ratio bound) to $q$-R\\'enyi divergence with $q = \\widetilde{O}(1)$, the first improvement in required warmness since 1991.","If the KLS conjecture holds, the log-Sobolev bound sharpens to $C_{\\mathrm{LSI}}(\\pi) \\lesssim D\\lambda^{1/2}$ without logarithmic factors, sharpening the same algorithmic bounds."],"supporting_citations":[{"why":"Supplies the Gaussian-cooling annealing framework and the previous $\\widetilde{O}(n^2(n\\vee R^2))$ cubic bound that the new algorithm must beat.","marker":"[CV18]"},{"why":"Reduces general logconcave sampling to sampling an augmented exponential distribution via tilted-Gaussian cooling, and gives the previous $n^2(n\\vee R^2)$ logconcave complexity this paper improves.","marker":"[KV25]"},{"why":"Introduces the In-and-Out proximal sampler for uniform distributions over convex bodies (PS_unif), whose $R_\\infty$-warmness requirement Theorem 1.3 relaxes.","marker":"[KVZ24]"},{"why":"Analyzes the proximal sampler for truncated Gaussians (PS_Gauss) under $R_\\infty$ warmness; the relaxed-warmness and improved-LSI analyses here build directly on it.","marker":"[KZ25]"},{"why":"Provides the $O(D)$ log-Sobolev bound for isotropic logconcave distributions that Theorem 3.1 interpolates, as well as the stochastic-localization proof technique reused in the appendix.","marker":"[LV24]"},{"why":"Gives the equivalence between Gaussian concentration and the log-Sobolev inequality for logconcave measures, which is the hinge of the proof of Theorem 3.1.","marker":"[Mil10]"},{"why":"Supplies the exponential-concentration bound for logconcave measures (quoted as Theorem 3.8) that, combined with the concentration-LSI equivalence, yields the interpolated LSI estimate.","marker":"[Biz24]"},{"why":"Provides the Bakry\\'emery criterion giving $C_{\\mathrm{LSI}}(\\pi\\gamma_h) \\le h$ and the standard functional-inequality background used throughout the analysis.","marker":"[BGL14]"},{"why":"Yields the $C_{\\mathrm{PI}} \\lesssim \\lambda\\log n$ bound for logconcave measures that enters both the covariance-control lemma and the proximal-sampler mixing analysis.","marker":"[Kla23]"}],"fun_headline_variants":["Logconcave sampling breaks the cubic barrier","Cold-start sampling goes sub-cubic","Sub-cubic sampling from a cold start achieved","Faster warm start: logconcave sampling in n^2.75","Renyi warmth and log-Sobolev break the cubic wall"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire speedup depends on the claim that mixing a logconcave measure with a Gaussian of variance as small as $R\\lambda^{1/2}$ polylog cannot enlarge its covariance beyond a constant factor of the original; if that geometric assertion fails, the fast annealing phase of the algorithm is not justified and the sub-cubic bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Logconcave sampling breaks the cubic barrier","Cold-start sampling goes sub-cubic","Sub-cubic sampling from a cold start achieved","Faster warm start: logconcave sampling in n^2.75","Renyi warmth and log-Sobolev break the cubic wall"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000924,"raw_usage":{"total_tokens":4035,"prompt_tokens":1091,"completion_tokens":2944,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":707,"completion_tokens_details":{"reasoning_tokens":2865}},"tokens_in":707,"tokens_out":2944,"duration_ms":21642,"temperature":1.0,"reasoning_tokens":2865,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:07:39.297880+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete non-Gaussian logconcave family — for instance the uniform distribution on a long thin box, or an affine image of the unit cube, in dimension $n$ — with known first moment $R$ and covariance norm $\\lambda$, and numerically compute the operator norm of $\\mathrm{cov}(\\pi\\gamma_h)$ at $h = C R\\lambda^{1/2}\\log^2n\\log^2(R^2/\\lambda)$ for a range of universal constants $C$. If the ratio $\\|\\mathrm{cov}(\\pi\\gamma_h)\\|/\\lambda$ exceeds any fixed universal constant at the stated threshold, Theorem 3.2 is false and the $n^{2.75}$ annealing schedule cannot be sustained.","supporting_citations":[],"review_version":1}