{"id":"80406c66-8c9e-49f4-818d-559dcd1640fc","arxiv_id":"2607.13943","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The Dikin walk with a scaled Lee-Sidford metric provably mixes on a polytope in O~(d^2.25) iterations from a warm start, improving the decade-old d^2.5 bound and taking a step toward the conjectured d^2.","lead":"A new analysis shows that the Dikin walk, an algorithm for sampling random points inside a high-dimensional polytope, mixes in about d^2.25 steps instead of the previously best-known d^2.5. It is the first improvement in nearly a decade toward the conjectured d^2 mixing time, and it also yields a faster cold-start bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.3's ∥N'''_t∥ ≲ d^{3/2} bound is off by a factor d: using (3.12), Σ_i ∥u'_{t,i}∥^6 / w_{t,i}^2 ≲ d^4, not d^3, so ∥N'''_t∥ ≲ d^2 and the H_4 bottleneck becomes r^4 d, forcing r ~ d^{-1/4} and no improvement over d^{2.5}.","rationale":"The reader's weakest assumption correctly flags Lemma 3.3 as the load-bearing core, but identifies the risk as unverified higher-order calculus rather than a specific inconsistency. I found a concrete arithmetic error in the proof of Lemma 3.3: the bound on Σ_i ∥u'_{t,i}∥^6 / w_{t,i}^2 is d^4 under the paper's own (3.12) and Σ w_i = d, not d^3. This propagates to ∥N'''_t∥, making the claimed ASC radius d^{-1/8} unattainable; the bottleneck H_4 then contributes r^4 d, which forces radius d^{-1/4} and recovers only the previous d^{2.5} mixing. If confirmed, Theorem 1.1 and Corollary 1.2 are not supported. The check is straightforward and decisive. I recommend rejection pending the concrete verification.","tokens_in":37510,"tokens_out":22522,"duration_ms":166988,"concrete_test":"Recompute the term Σ_i ∥u'_{t,i}∥^6 / w_{t,i}^2 in Lemma 3.3 using (3.12): substitute ∥u'_{t,i}∥ = O(∥z_t∥_∞ w_{t,i}^{1/2}) and ∥z_t∥_∞ = O(d^{1/2}), and use Σ_i w_{t,i} = d. If the sum is Θ(d^4), then the displayed chain in Lemma 3.3 is wrong and ∥N'''_t∥ grows as d^2, which invalidates the d^{1/4} scaling. A direct symbolic/analytic check of the row-map bound (Lemma B.1) with the stated u' bounds settles the matter.","verdict_should_be":"REJECT","load_bearing_attack":"The proof of Lemma 3.3 claims ∥Φ'''_t∥_F^2 ≲ ∥U'''_t∥_F^2 + Σ_i ∥u'_{t,i}∥^6 / w_{t,i}^2 + Σ_i ∥u'_{t,i}∥^2 ∥u''_{t,i}∥^2 / w_{t,i} ≲ d^3. But using the paper's own bound (3.12), ∥u'_{t,i}∥^2 ≲ d w_{t,i}, the middle sum is Σ_i (d w_{t,i})^3 / w_{t,i}^2 = d^3 Σ_i w_{t,i}. Since trace(P_t) = rank(A) = d, Σ_i w_{t,i} = d, so this sum is Θ(d^4), not d^3. The same issue affects the third sum if ∥u''∥^2 is bounded by d^2 w_i. Consequently ∥Φ'''∥_F ≲ d^2, and through (3.7) and the chain rule, ∥N'''_t∥ ≲ d^2, not d^{3/2}. The terminal bottleneck H_4(t) = q_t^T N'''_t v_t then satisfies |H_4(t)| ≲ ∥q_t∥ ∥N'''_t∥ ∥v_t∥ ≲ d^{1/2} · d^2 · d^{1/2} = d^3, contributing η^4 d^3 = r^4 d to (3.2). To make this O(ε), the ASC radius must be r ≲ d^{-1/4}, which after scaling L ~ d^{1/2} yields the prior d^{2.5} mixing, not the claimed d^{2.25}. The displayed bound in Lemma 3.3 is internally inconsistent with (3.12).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Dikin walk for sampling from a bounded full-dimensional polytope with an exponential target distribution. It proves that, using the Lee–Sidford metric scaled by a factor L = Θ~(d^{1/4}), the Dikin walk mixes from a warm start in Θ~(d^{9/4} polylog m log(χ^2_0/ε)) iterations, improving the previous Θ~(d^{5/2}) bound and making progress toward the conjectured d^2 mixing time. The improvement rests on a sharper average self-concordance (ASC) estimate for the unscaled LS metric at radius r = Θ~(d^{-1/8}). The proof isolates a recursive bottleneck chain H_k, develops higher-order Lewis-weight calculus via a moving orthonormal frame, and controls the base-point Gaussian polynomials by Wiener-chaos decompositions and multiple stochastic integrals. A cold-start corollary gives d^{41/16} iterations.","tokens_in":37872,"tokens_out":36888,"duration_ms":301334,"significance":"If correct, this is the first improvement over the d^{2.5} bound of CDWY18 in nearly a decade, and a substantial step toward the d^2 conjecture. The technical machinery introduced—selective expansion of bottleneck terms, moving-frame higher-order calculus for Lewis weights, and MSI-based tensor-norm estimates for Gaussian polynomials—is likely to be useful for future analyses of Dikin-type walks. The proof is detailed and self-contained modulo the cited black boxes, and it is explicit about the remaining barriers to the d^2 conjecture. My independent checks of the exponent arithmetic, the scaling chain, and the main bottleneck estimates all pass.","major_comments":[{"comment":"I explicitly checked the apparent inconsistency with (3.12) raised in the stress-test note. A termwise substitution of ||u'_i||^2 ≲ d w_i into Σ_i ||u'_i||^6 / w_i^2 would give d^4, but this ignores the global budget Σ_i ||u'_i||^2 = ||U'_t||_F^2 ≲ d. Writing x_i = ||u'_i||^2 / w_i, one has x_i ≲ d and Σ_i x_i w_i = ||U'_t||_F^2 ≲ d, so Σ_i ||u'_i||^6 / w_i^2 = Σ_i x_i^3 w_i ≲ d^2 Σ_i x_i w_i ≲ d^3. Hence the displayed bound ||Φ'''_t||_F^2 ≲ d^3 is consistent with (3.12), and consequently ||N'''_t|| ≲ d^{3/2} holds. The H4 bottleneck remains η^4 d^{5/2} = r^4 d^{1/2}, supporting the claimed r = Θ~(d^{-1/8}) ASC radius. The stress-test concern therefore does not land.","section":"§3.2 / Lemma 3.3"}],"minor_comments":[{"comment":"The statement 'choose R_ε = Θ~(d^{-1/8})' is imprecise with respect to ε: the displayed condition R_ε + R_ε^2 + R_ε^4 d^{1/2} ≤ ε/polylog(m/ε) requires a constant factor ε^{1/4} in R_ε (i.e. R_ε = Θ~(ε^{1/4} d^{-1/8})). Since Theorem 1.1 uses a fixed ASC accuracy, this does not affect the main result, but the proposition should be stated precisely.","section":"§3, Proposition 3.1"},{"comment":"The notation B is overloaded: \\widehat B_t = W_t^β A_t in Lemma 3.3, while B = W^{1/2}_x A_x in §3.3. These are different matrices and using the same letter in close proximity is confusing. Also P_t denotes both the original Lewis-weight projector and U_t U_t^T; a consistent renaming would improve readability.","section":"§3.2–3.3"},{"comment":"The bound on Σ_i ||u'_i||^6 / w_i^2 is compressed into a single chain. Adding the two-line argument with x_i = ||u'_i||^2/w_i and the global budget ||U'_t||_F^2 ≲ d would remove a likely source of confusion and preempt the apparent d^4 issue.","section":"Lemma 3.3 proof"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically strong and the main theorem appears sound. I specifically checked the burden-bearing Lemma 3.3 estimate that was flagged in the stress-test note; the concern does not hold because of the global Frobenius budget on U'. The only issues are local clarity and notational. I recommend minor revision. The paper is well within the scope of a serious theory journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the d^{2.25} claim does not survive contact with Lemma 3.3. There's an arithmetic error in the proof of that lemma—the bound on ∥Φ'''_t∥_F^2 is internally inconsistent with the paper's own equation (3.12)—and when you fix it, the bottleneck term H_4 contributes r^4 d instead of r^4 d^{1/2}, so the ASC radius drops to d^{-1/4} and you're back to the old d^{2.5} mixing. That said, the paper is not sloppy: it gives a clean framework, is candid about prior gaps in LLV20 and GKM+24, and the higher-order calculus and Wiener-chaos machinery are genuinely interesting. But the main theorem rests on this lemma, and the lemma is wrong as written.\n\nThe specifics: in the proof of Lemma 3.3, after deriving (3.12), ∥u'_{t,i}∥^2 ≲ d w_{t,i}, the paper bounds Σ_i ∥u'∥^6 / w_i^2 by d^3. But each term is ≲ (d w_i)^3 / w_i^2 = d^3 w_i, and Σ_i w_i = d (trace of the projection), so the sum is Θ(d^4). The same style of error affects the third sum if you use the natural row-wise second-derivative bound. Consequently ∥Φ'''∥_F ≲ d^2 rather than d^{3/2}, and through (3.7) ∥N'''_t∥ ≲ d^2. Then |H_4(t)| ≤ ∥q_t∥ ∥N'''_t∥ ∥v_t∥ ≲ d^{1/2} · d^2 · d^{1/2} = d^3, which enters (3.2) as η^4 d^3 = r^4 d. To keep this O(ε) you need r ≲ d^{-1/4}, which after scaling L ~ d^{1/2} gives exactly the old d^{2.5} bound. The d^{2.25} and d^{41/16} results do not follow.\n\nThe rest of the paper—Proposition 2.3, the bottleneck-chain decomposition, the MSI/Hermite estimates for H_2(0) and H_3(0)—looks careful, and I believe the framework could lead to a real improvement if the pathwise calculus can be repaired. But as it stands, the main technical contribution is unproven. I'd send it to review, because the problem matters and the author may be able to fix it. I would not cite it as a proven bound in the meantime.","headline":"The claimed d^{2.25} mixing bound relies on a factor-of-d error in Lemma 3.3; the proof as written recovers only the old d^{2.5}.","tokens_in":38608,"tokens_out":4695,"would_cite":false,"duration_ms":41788,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","60J20","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Dikin walks on polytopes now mix in d^2.25 iterations, improving the previous d^2.5 bound.","keywords":["average self-concordance","Dikin walk","Lee-Sidford metric","Lewis weights","polytope sampling","Markov chain mixing","interior-point methods","Wiener chaos"],"falsifier":"Compute the operator norms of N'''(t) along the Dikin proposal path for a concrete polytope with explicit Lewis weights, for instance the d-dimensional simplex or the hypercube, at the claimed radius d^{−1/8}. If ∥N'''∥ exceeds d^{3/2}·poly(d^{1/8}) for a nontrivial fraction of directions, the terminal term H_4 contributes more than O(ε) and the ASC radius d^{−1/8} fails; equivalently, simulate the fluctuation |F(η)−F(0)| at r = d^{−1/8} and check it exceeds the ASC threshold 2εr^2/d with probability larger than ε.","tokens_in":37190,"feed_emoji":"🎲","tokens_out":6612,"duration_ms":60940,"temperature":0.7,"pith_summary":"This paper improves the warm-start mixing time of the Dikin walk for sampling from a polytope from O~(d^{2.5}) to O~(d^{2.25}) iterations, breaking a bound that had stood for about a decade and moving closer to the conjectured d^2. The engine is a sharper average self-concordance estimate for the Lee–Sidford metric: the unscaled metric now enjoys the required property at radius Θ~(d^{-1/8}) rather than the previously implicit d^{-1/4}, allowing the metric to be scaled by d^{1/4} instead of d^{1/2}. The improved estimate follows from a new higher-order calculus for Lewis weights, built from a moving orthonormal frame and a selective expansion of the few bottleneck terms, with the resulting Gaussian polynomials controlled by Wiener-chaos decompositions. A corollary improves the cold-start (no warm start) complexity from d^{23/8} to d^{41/16}.","feed_headline":"Dikin walks now mix polytopes in d^2.25 steps","feed_subtitle":"A sharper self-concordance bound for the Lee–Sidford metric breaks the d^2.5 barrier and nears the d^2 conjecture.","key_machinery":"Average self-concordance (ASC) is the condition that a random Dikin proposal at radius r changes the squared local length, when measured at the proposal instead of the base point, by O(εr^2/d) with probability 1−ε; it is the property that keeps the Metropolis acceptance probability high. The paper proves ASC for the Lee–Sidford metric at radius d^{-1/8} by expanding the path function F(t) = h^T g0(x+th) h along a Gaussian direction h, but only through a recursively defined chain of bottleneck terms H_k(t) = q_t^T N_t^{(k−1)} v_t. The higher derivatives of the Lewis-weight matrix N_t are controlled via a moving orthonormal frame for the column space of a half of the metric, which removes irre","core_discovery":"The paper's central claim is that the unscaled Lee–Sidford metric satisfies average self-concordance at radius Θ~(d^{-1/8}): for any base point in the polytope, a random Dikin proposal at that radius changes the squared local length by at most 2εr^2/d with probability at least 1−ε. Scaling a metric by L multiplies the symmetry parameter by L while converting a radius-r proposal into a radius-r/√L proposal for the unscaled metric, so this ASC radius translates into constant-radius ASC for the d^{1/4}-scaled metric with symmetry parameter O~(d^{5/4}). Plugging these into the standard Dikin-walk mixing lemma yields the d^{9/4} warm-start iteration bound. The path to the sharper ASC radius runs","pith_inferences":["The recursion the paper exhibits suggests that if the pathwise estimate could be extended to ∥N_t^{(j)}∥ ≲ d^{j/2} and the base-point L2 estimate to ∥q^T N_x^{(j)} v_x∥_{L2} ≲ d^{(j+1)/2} for arbitrarily large j, the mixing time would approach d^{2+1/(j+1)}; reaching the exact d^2 likely needs a fundamentally different argument rather than longer expansions, since the j-terms grow with j.","The moving-frame calculus for Lewis weights may also benefit interior-point method analysis beyond sampling, where third- and higher-order barrier derivatives are typically avoided.","The cold-start exponent d^{41/16} emerges from a generic annealing schedule; a schedule tuned to the improved self-concordance constants could plausibly push it closer to d^{9/4}, the warm-start rate.","A natural test case for the sharper ASC radius is the d-dimensional simplex or hypercube, where the Lewis weights are explicit and the higher-order derivatives can be computed symbolically to verify the d^{-1/8} radius does not hide a larger constant."],"forward_implications":["Warm-start exponential sampling from any bounded full-dimensional polytope now runs in O~(d^{9/4}) Dikin-walk iterations, improving the previous O~(d^{5/2}) and shrinking the gap to the conjectured d^2.","Cold-start sampling via the annealing framework improves to O~(d^{41/16}) ≈ d^{2.56} iterations, the best known for this problem.","The sharper ASC radius for the unscaled Lee–Sidford metric is a stand-alone geometric fact: any future sampler whose analysis reduces to ASC will inherit this improvement.","The paper isolates the two estimates that remain to reach d^2—control of the j-th derivative of N_t pathwise and of the j-th base-point Gaussian polynomial for all j—and pushes both to j=3, making the remaining obstacle precise.","The higher-order Lewis-weight calculus (moving-frame derivatives up to third order and the Wiener-chaos tensor bounds) is reusable machinery for other barrier-based algorithms."],"fun_headline_variants":["Dikin walk mixing improved to d^2.25","New Dikin walk bound: d^2.25 steps on polytopes","Dikin walk shaves mixing time to d^2.25","Beyond d^2.5: Dikin walk now mixes in d^2.25","Near-optimal Dikin walk: d^2.25 mixing bound"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole proof rests on the good-event estimates of Lemma 3.3: along a random proposal path of length η = r/√d, the coordinate-wise slack bounds stay O(1) and the first, second, and third derivatives of the Lewis-weight derivative matrix stay within O(d^{1/2}), O(d), and O(d^{3/2}) respectively, all on one event of probability 1−ε/20.","fun_headline_variants_meta":{"raw":{"variants":["Dikin walk mixing improved to d^2.25","New Dikin walk bound: d^2.25 steps on polytopes","Dikin walk shaves mixing time to d^2.25","Beyond d^2.5: Dikin walk now mixes in d^2.25","Near-optimal Dikin walk: d^2.25 mixing bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000234,"raw_usage":{"total_tokens":1404,"prompt_tokens":886,"completion_tokens":518,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":420}},"tokens_in":630,"tokens_out":518,"duration_ms":4748,"temperature":1.0,"reasoning_tokens":420,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T03:16:32.246334+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the operator norms of N'''(t) along the Dikin proposal path for a concrete polytope with explicit Lewis weights, for instance the d-dimensional simplex or the hypercube, at the claimed radius d^{−1/8}. If ∥N'''∥ exceeds d^{3/2}·poly(d^{1/8}) for a nontrivial fraction of directions, the terminal term H_4 contributes more than O(ε) and the ASC radius d^{−1/8} fails; equivalently, simulate the fluctuation |F(η)−F(0)| at r = d^{−1/8} and check it exceeds the ASC threshold 2εr^2/d with probability larger than ε.","supporting_citations":[],"review_version":1}