{"id":"4a4b3b94-d33a-40c6-bea1-d6d1a5b62d97","arxiv_id":"2412.13928","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"SLMC generalizes random-coordinate and preconditioned Langevin Monte Carlo by projecting updates onto random eigenblocks of a preconditioner, with coupling-based error bounds.","lead":"This paper introduces Subspace Langevin Monte Carlo (SLMC), a sampling method that updates along random low-dimensional eigenblocks of a preconditioner instead of full coordinates. It provides convergence bounds and small experiments suggesting speedups on ill-conditioned distributions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's unrolling step (Appendix A.4) switches from the A_k^{-1} to A_{k+1}^{-1} norm using Assumption 2, but that assumption controls optimal-transport distances, not the second moment of the synchronous coupling, so the displayed recursion is not justified.","rationale":"The reader's weakest_assumption (Assumption 2) is the right area, but the strongest form of the concern is sharper. Re-reading the proof of Theorem 3 (Appendix A.4), the recursion before unrolling is for the synchronous coupling's second moment C_k = E∥Z_k−X_k∥²_{A_k^{-1}}, not for the W-distance δ_k. Assumption 2 bounds δ_k under consecutive norms, but C_k ≥ δ_k, so the assumption cannot be used to bound C_k under the new norm. Moreover, without a lower bound on A_k, the A_k^{-1}-norms are not uniformly equivalent. The proof's 'Using Assumption 2 and unrolling' is therefore a genuine logical gap. I checked Lemma 3: the contested trace identity is in fact correct for eigenblocks W of A (since W^T A W and W^T A^{-1} W are inverse diagonal matrices), so the reader's specific trace concern appears less severe; the unrolling gap is more load-bearing. The theorem can likely be fixed by assuming slow variation of A_k in the Loewner order, which is natural for adaptive preconditioners, so I do not move the verdict from CONDITIONAL; rather I sharpen the condition needed.","tokens_in":22150,"tokens_out":29897,"duration_ms":219693,"concrete_test":"Re-derive the unrolling in Appendix A.4 using δ_k = W₂²_{A_k^{-1}}(μ_k,π) instead of the coupling cost; verify whether Assumption 2 alone implies δ_{k+1} ≤ (1−hm/2)δ_k + ε_k. If not, build a two-step counterexample with A_1 = diag(1,ε), A_2 = diag(ε,1), μ_1 close to π in both W-distances, and a synchronous coupling whose A_2^{-1}-second-moment is much larger than its A_1^{-1}-second-moment, showing the displayed unrolled bound fails. Alternatively, add the condition (1−Lh)A_k ⪯ A_{k+1} ⪯ (1+Lh)A_k and check that the recursion then goes through with the O(h) absorbed into the contraction constant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3 (Appendix A.4) derives the recursion E∥Δ_{k+1}∥²_{A_k^{-1}} ≤ (1−hm/2)E∥Δ_k∥²_{A_k^{-1}} + (1/m)Σ_i[4rh²M_{ik}²/φ_{ik}], where Δ_k = Z_k − X_k is the synchronous coupling between μ_k and π. It then states 'Using Assumption 2 and unrolling, E∥Δ_{k+1}∥²_{A_{k+1}^{-1}} ≲ (1−hm/2)^k …'. This step is not valid: Assumption 2 (Eq. 19) bounds the change in the optimal-transport distance W₂²_{A_k^{-1}}(μ_k,π) − W₂²_{A_{k-1}^{-1}}(μ_k,π), but E∥Δ_k∥²_{A_k^{-1}} is the cost of the specific coupling and is ≥ W₂², so the assumption gives no upper bound on the coupling's second moment under the new norm. Since Assumption 2 only requires A_k ⪯ CI (no lower bound), ∥·∥_{A_k^{-1}} and ∥·∥_{A_{k+1}^{-1}} can be arbitrarily far from equivalent, and the coupling cost under A_{k+1}^{-1} can be much larger than under A_k^{-1}. Thus the contraction does not transfer across time-varying preconditioners as written. This is a proof gap in the central theorem, not merely a restrictive assumption; the theorem could be repaired by adding a Loewner slow-variation condition on A_k (e.g., (1−Lh)A_k ⪯ A_{k+1} ⪯ (1+Lh)A_k) and using it to bound the norm change of the coupling.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Subspace Langevin Monte Carlo (SLMC), an LMC variant that at each iteration updates along a randomly chosen r-dimensional eigenblock W_{ik}D_{ik}W_{ik}^T of a time-varying preconditioner A_k, with step size h/φ_ik. It claims to generalize random-coordinate LMC and block-coordinate LMC, establishes a continuous-time convergence result for projected Wasserstein flows, and proves a discrete-time Wasserstein coupling bound (Theorem 3) under relative strong convexity/smoothness and auxiliary assumptions on the preconditioner sequence. The paper then compares directional-derivative complexities with LMC, PLMC, and RCLMC and reports experiments on an ill-conditioned Gaussian, Bayesian logistic regression, and funnel distributions.","tokens_in":22562,"tokens_out":19027,"duration_ms":165396,"significance":"SLMC is a well-motivated and potentially useful extension of RCLMC to block/eigenbases, and the coupling framework is a natural tool for this problem. The continuous-time subspace gradient flow result (Proposition 1) and the explicit decomposition of SLMC as a generalization of RCLMC are valuable. The experiments are clearly described and address relevant ill-conditioned targets. However, the central discrete-time theorem currently has a proof gap in the unrolling step, Lemma 3 is stated with false generality, and the complexity comparison in Section 4.4/Table 1 contains algebraic inconsistencies. These issues are load-bearing for the paper's main claims, so the manuscript needs substantive revision before the theoretical results can be accepted as established.","major_comments":[{"comment":"The unrolling step is not justified. The proof derives E∥Δ_{k+1}∥²_{A_k^{-1}} ≤ (1−hm/2)E∥Δ_k∥²_{A_k^{-1}} + (1/m)Σ_i[4rh²M_ik²/φ_ik] and then states 'Using Assumption 2 and unrolling, E∥Δ_{k+1}∥²_{A_{k+1}^{-1}} ≲ ...'. Assumption 2 (Eq. 19) bounds the change in the optimal-transport W²_{2,A^{-1}} distance, not the second moment of the synchronous coupling under the new norm. Since Assumption 2 only provides A_k ⪯ CI and no lower bound, the norms ∥·∥_{A_k^{-1}} and ∥·∥_{A_{k+1}^{-1}} can be arbitrarily far from equivalent, and E∥Δ_k∥²_{A_{k+1}^{-1}} can be much larger than E∥Δ_k∥²_{A_k^{-1}}. The contraction therefore does not transfer across time-varying preconditioners as written. A slow-variation Loewner condition applied directly to the coupling norm, such as (1−Lh)A_k ⪯ A_{k+1} ⪯ (1+Lh)A_k, appears necessary; the current Assumption 2 is insufficient for this step.","section":"Appendix A.4, proof of Theorem 3"},{"comment":"Lemma 3 is false for general orthonormal W. The identity Tr([W^T A^{-1}W][W^T A W]) = r holds only when the columns of W are eigenvectors of A. For a counterexample, take A = diag(λ_1, λ_2) and W = 1/√2 [[1,1],[1,−1]]; the trace equals (λ_1² + λ_2²)/(2λ_1λ_2), which is not 2 unless λ_1 = λ_2. The proof also uses the square-root identity (W W^T A W W^T)^{1/2} = W W^T A^{1/2} W W^T, which again requires W to form eigenblocks of A. Since the applications in Theorem 3 use eigenblocks W_{ik}, the lemma can be repaired by restricting its statement to eigenblocks, but as stated it is incorrect and is used in the main proof.","section":"Appendix A.4, Lemma 3"},{"comment":"The complexity comparison is internally inconsistent. Formula (22) gives a directional-derivative complexity of O(r²Σ_{i=1}^{d/r}κ²_rel,i/φ_i/(ε²m)), but Table 1 reports O(dr(Σκ_rel,i)²/(ε²m)) in the φ_i ∝ M_i row; these differ by a factor of d/r. In addition, the condition stated in the text, 'for SLMC to beat PLMC, we need r(Σκ_rel,i)² ≥ dκ_rel', appears reversed: comparing the displayed SLMC and PLMC complexities requires r(Σκ_rel,i)² ≤ dκ_rel for the table's dr form, or r²(Σκ_rel,i)² ≤ d²κ_rel for formula (22). Since these inequalities are the basis for the claimed improvements over PLMC, they should be corrected and stated explicitly.","section":"Section 4.4 and Table 1"},{"comment":"Assumption 2 is a strong, unverified condition: it requires the W_{2,A_k^{-1}} distance to be nearly unchanged when the preconditioner changes, and it imposes no lower bound on A_k. The paper does not show that any natural adaptive preconditioner, including the law-dependent average-Hessian preconditioner in Section 5.2 or the RMSProp/Adagrad variants in Section 5.3, satisfies this condition. Section 5.3 is explicitly outside the theory, and the average-Hessian example is not checked against the assumption. As a result, the advertised support for time-varying preconditioners is not established by the present analysis.","section":"Assumption 2 (Eq. 19)"}],"minor_comments":[{"comment":"The main theorem is stated as Theorem 3 in Section 4.3 but restated as Theorem 4 in Appendix A.4; the appendix statement also has an incomplete step-size condition, reading 'h ≤ min (minϕ_ik/M, )'.","section":"Section 4.3 / Appendix A.4"},{"comment":"The displayed Itô computation is missing a minus sign: the correct expression is f(Z_t,Z'_t) − f(Z_0,Z'_0) = −2∫⟨Z_s−Z'_s, ∇V(Z_s)−∇V(Z'_s)⟩ds, and the subsequent inequality should be ≤ −2∫ m f ds. The final contraction is correct, but the displayed derivation is inconsistent with it.","section":"Appendix A.2, proof of Lemma 2"},{"comment":"The step-size condition h ≤ min_i φ_ik/M_k should be written with the directional smoothness of the chosen block, e.g. M_{ik} = M_k(W_{ik}); the symbol M_ij is introduced only after the theorem statement.","section":"Section 4.3, Theorem 3 notation"},{"comment":"The phrase 'If j is the index that maximizes Σ_i[M²_ij/φ_ij]' is confusing, since j is a time index in Theorem 3 but the subsequent simplification treats all j identically. The argument should state explicitly that it assumes stationary directional smoothness and block probabilities or takes a uniform upper bound over j.","section":"Section 4.4, simplification of Theorem 3"},{"comment":"The paper does not provide code or data for the experiments, so the empirical claims cannot be reproduced from the manuscript.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the core idea is worth pursuing, but the proof gap in Theorem 3 and the false statement of Lemma 3 are substantive; they should be fixed before acceptance. The inconsistencies in Table 1 and the PLMC comparison should not be treated as mere typesetting issues, since they concern the paper's headline complexity claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read on the SLMC paper. The core idea is genuinely new: projecting the Langevin update onto random eigenblocks of a time-varying preconditioner unifies RCLMC and block-coordinate LMC, and the paper gives the first convergence analysis for block-coordinate LMC. That alone makes it worth a look. The coupling argument is adapted sensibly from Ding et al. and Ahn-Chewi, and the complexity comparison to LMC/PLMC/RCLMC is informative, even if heuristic.\n\nThe soft spots are real. The proof of Lemma 3 (Appendix A.4) states a trace identity that holds for eigenblocks but not for arbitrary orthonormal W. The lemma as written is false; the application in Theorem 3 only uses eigenblocks, so this is fixable but needs correction. More substantively, the stress-test concern lands. In the proof of Theorem 3, after deriving a recursion for E||Δ_{k+1}||²_{A_k^{-1}}, the text switches to the A_{k+1}^{-1} norm citing Assumption 2. But Assumption 2 bounds the change in the optimal-transport distance W₂²_{A_k^{-1}}(μ_k,π), not the second moment of the specific synchronous coupling Δ_k. Since W₂² is an infimum, that assumption gives no control on the coupling's cost under the new norm. Without a Loewner slow-variation condition on A_k, the unrolling is not justified. This is a load-bearing gap in the main theorem, though I suspect it's repairable.\n\nThe complexity simplification from Theorem 3 to (22) is also heuristic, and the experiments are small: they show the method can behave sensibly on an ill-conditioned Gaussian, a logistic regression posterior, and a funnel, but error bars are missing in several figures and no code is released. For a paper claiming efficiency gains, that's a weakness, not a fatal one.\n\nWho is this for: people working on scalable MCMC and subspace methods. The paper deserves a serious referee; the right outcome is major revision, with the proof gap addressed and the experiments tightened. I would not cite its theorems as they stand, but I'd keep it on the reading list.","headline":"Novel and promising subspace sampling method, but the central theorem's proof has a genuine gap in the unrolling step.","tokens_in":23057,"tokens_out":5023,"would_cite":false,"duration_ms":40944,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Subspace Langevin Monte Carlo samples high-dimensional targets by projecting each step onto a random eigenblock of a time-varying preconditioner, and its coupling analysis shows the directional-derivative complexity scales with the block…","keywords":["Langevin Monte Carlo","subspace methods","random coordinate descent","preconditioned sampling","Wasserstein gradient flow","ill-conditioned distributions","coupling argument","directional derivative complexity"],"falsifier":"For a multivariate Gaussian target with known precision matrix, choose $A_k$ to oscillate between two matrices at every step (e.g., $A_{\\text{odd}} = I$, $A_{\\text{even}} = 0.5(I + \\text{small-rank perturbation})$) and numerically compute $W_{2,A_N^{-1}}(\\mu_N,\\pi)$ after each step. If the empirical distance decays slower than the claimed bound or fails to contract, then the recursion via Assumption 2 (Eqs. (27)-(28)) is the broken link.","tokens_in":21970,"feed_emoji":"🎲","tokens_out":6304,"duration_ms":51361,"temperature":0.7,"pith_summary":"Subspace Langevin Monte Carlo (SLMC) is a proposal for sampling from high-dimensional target distributions by updating particles along random low-dimensional eigenspaces of a time-varying preconditioner at each step. The paper's central claim is that this projection costs nothing in accuracy: under relative strong convexity and smoothness, SLMC contracts to the target in a preconditioned Wasserstein distance at a rate governed by a per-block condition number, and its total directional-derivative complexity scales with $r^2$ instead of $d^2$. A sympathetic reader would care because SLMC unifies and generalizes random-coordinate LMC and preconditioned LMC, and because it can be run with reduced memory, making adaptive sampling practical in high dimensions. The claim is supported by a coupling argument and by experiments on a Gaussian, Bayesian logistic regression, and a funnel distribution.","feed_headline":"Random eigenblock steps cut Langevin sampling cost from d to r","feed_subtitle":"Subspace steps cut derivative calls and memory for ill-conditioned sampling.","key_machinery":"The central object is the SLMC update $X_{k+1} = X_k - h_k P_k \\nabla V(X_k) + \\sqrt{2h_k}P_k^{1/2}\\xi_k$, where $P_k$ is a random rank-$r$ eigenblock of the preconditioner $A_k$. Because $\\mathbb{E}[h_k P_k] = h A_k$, the method is an unbiased-in-direction subspace version of preconditioned LMC. The proof machinery is a Wasserstein coupling between SLMC and an auxiliary continuous process (Eq. (29)), combined with a relative smoothness and relative strong convexity framework and an unrolling recursion (Eqs. (27)-(28)) that transfers the metric from $A_k^{-1}$ to $A_{k+1}^{-1}$ using Assumption 2. The blockwise directional smoothness parameter $M_i(W)$ controls the bias term.","core_discovery":"The paper's main theorem (Theorem 3) states that if the potential is $m$-relatively strongly convex and $M$-relatively smooth with respect to $\\|\\cdot\\|_{A_k^{-1}}$, if the preconditioners change slowly in the sense of Assumption 2, if the update directions are eigenblocks $P_k = W_{i_k}D_{i_k}W_{i_k}^{\\mathsf{T}}$ sampled with probability $\\phi_{ik}$ and step size $h/\\phi_{ik}$, and if $h$ is small relative to the blockwise directional smoothnesses, then the iterates satisfy a bound of the form $W_{2,A_N^{-1}}(\\mu_N,\\pi) \\lesssim \\exp(-hmN/4)W_{2,A_0^{-1}}(\\mu_0,\\pi) + \\sqrt{\\frac{1}{m}\\sum_j (1-hm/2)^{N-j}\\sum_i \\frac{r h^2 M_{ij}^2}{\\phi_{ij}}}$. The bound splits into a contraction term and a bias term depending on the ratios $r h^2 M_{ij}^2/\\phi_{ij}$. Consequently the directional-derivative complexity is $O\\!\\left(\\frac{r^2 \\sum_i \\kappa_{\\mathrm{rel},i}^2/\\phi_i}{\\epsilon^2 m}\\log\\frac{W_2(\\mu_0,\\pi)}{\\epsilon}\\right)$, replacing the dimension $d$ with the block size $r$. This is the first analysis of block-coordinate LMC and a strict generalization of random-coordinate LMC.","pith_inferences":["The paper's analysis covers preconditioners that depend only on the law of the current measure, not on the random particles themselves; a testable extension is to check whether Assumption 2 holds for natural sample-based adaptive preconditioners such as inverse empirical covariance or diagonal AdaGrad-style estimates, which would bring RMSProp and Adagrad subspace samplers under the theory.","The complexity comparison suggests a concrete design principle: choosing sampling probabilities $\\phi_i$ proportional to $\\kappa_{\\mathrm{rel},i}$ minimizes the bias term, giving an optimal coordinate-selection rule in Wasserstein space.","The contraction term $\\exp(-hmN/4)$ indicates a roughly four-fold slowdown relative to full-gradient LMC, so SLMC's advantage is purely computational (fewer directional derivatives per step), not a faster mixing rate.","The coupling technique used here may extend to other Wasserstein-space subspace methods, such as random-subspace versions of underdamped LMC, as long as the auxiliary continuous process can be constructed with the same rotation structure."],"forward_implications":["If correct, block-coordinate LMC, a method never separately analyzed, inherits convergence guarantees as a special case of SLMC.","In ill-conditioned distributions where a good preconditioner aligns with the target's structure (e.g., eigenblocks of the inverse covariance), SLMC's complexity improves over LMC by replacing $d^2$ with $r^2$ and can beat PLMC when per-block relative condition numbers are better than the global one.","The method's memory footprint is smaller than PLMC because it never stores the full $d\\times d$ preconditioner nor the full gradient, enabling adaptive sampling in high dimensions.","The step-size constraint $h \\le \\min_i \\phi_{ik}/M_k$ shows that the method requires knowing or estimating blockwise smoothness constants; in practice one can use per-block step sizes."],"supporting_citations":[{"why":"Random coordinate Langevin Monte Carlo, the method that SLMC generalizes; its proof structure is adapted to eigenblocks.","marker":"[20]"},{"why":"Mirror-Langevin algorithm, which supplies the relative strong convexity and smoothness framework and the proof of PLMC (Theorem 2) that SLMC builds on.","marker":"[1]"},{"why":"Coupling-style analysis of LMC with inaccurate gradients, used as the coupling technique in the proof of Theorem 3.","marker":"[17]"},{"why":"RCLMC with variance reduction, giving a complexity bound that SLMC extends to arbitrary block size.","marker":"[19]"},{"why":"Provides the stationarity condition for preconditioned Langevin (Theorem 1) used to justify PLMC and SLMC.","marker":"[48]"},{"why":"Euclidean subspace descent analysis that inspires the projected update and the comparison of directional derivative costs.","marker":"[42]"},{"why":"Provides the adaptive preconditioning experiments on the funnel distribution that SLMC replicates.","marker":"[71]"}],"fun_headline_variants":["Subspace eigenblock steps cut Langevin cost from d to r","First block-coordinate LMC analysis reduces sampling cost","Langevin Monte Carlo in subspaces: complexity from d to r","SLMC: subsampled eigenblocks cut sampling complexity","Random eigenblocks shrink Langevin cost to block size r"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 2: the preconditioners must change slowly enough in successive steps so that switching the Wasserstein metric does not increase the distance between the current measure and the target by more than $O(h^2)$; this is assumed rather than verified, and natural adaptive preconditioners that depend on the particle positions are excluded.","fun_headline_variants_meta":{"raw":{"variants":["Subspace eigenblock steps cut Langevin cost from d to r","First block-coordinate LMC analysis reduces sampling cost","Langevin Monte Carlo in subspaces: complexity from d to r","SLMC: subsampled eigenblocks cut sampling complexity","Random eigenblocks shrink Langevin cost to block size r"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00029,"raw_usage":{"total_tokens":1704,"prompt_tokens":962,"completion_tokens":742,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":578,"completion_tokens_details":{"reasoning_tokens":657}},"tokens_in":578,"tokens_out":742,"duration_ms":6714,"temperature":1.0,"reasoning_tokens":657,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:38:48.504700+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a multivariate Gaussian target with known precision matrix, choose $A_k$ to oscillate between two matrices at every step (e.g., $A_{\\text{odd}} = I$, $A_{\\text{even}} = 0.5(I + \\text{small-rank perturbation})$) and numerically compute $W_{2,A_N^{-1}}(\\mu_N,\\pi)$ after each step. If the empirical distance decays slower than the claimed bound or fails to contract, then the recursion via Assumption 2 (Eqs. (27)-(28)) is the broken link.","supporting_citations":[{"cited_title":"Random coordinate Langevin Monte Carlo","cited_arxiv_id":null,"evidence_quote":"Random coordinate Langevin Monte Carlo, the method that SLMC generalizes; its proof structure is adapted to eigenblocks."},{"cited_title":"Efficientconstrainedsamplingviathemirror-langevin algorithm","cited_arxiv_id":null,"evidence_quote":"Mirror-Langevin algorithm, which supplies the relative strong convexity and smoothness framework and the proof of PLMC (Theorem 2) that SLMC builds on."},{"cited_title":"User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient.Stochastic Processes and their Applications, 129 (12):5278–5311, 2019","cited_arxiv_id":null,"evidence_quote":"Coupling-style analysis of LMC with inaccurate gradients, used as the coupling technique in the proof of Theorem 3."},{"cited_title":"Langevin monte carlo: random coordinate descent and variance reduction.Journal of machine learning research, 22(205):1–51, 2021","cited_arxiv_id":null,"evidence_quote":"RCLMC with variance reduction, giving a complexity bound that SLMC extends to arbitrary block size."},{"cited_title":"A complete recipe for stochastic gradient MCMC","cited_arxiv_id":null,"evidence_quote":"Provides the stationarity condition for preconditioned Langevin (Theorem 1) used to justify PLMC and SLMC."},{"cited_title":"A stochastic subspace approach to gradient-free optimization in high dimensions","cited_arxiv_id":null,"evidence_quote":"Euclidean subspace descent analysis that inspires the projected update and the comparison of directional derivative costs."},{"cited_title":"Scalablestochastic gradient Riemannian Langevin dynamics in non-diagonal metrics","cited_arxiv_id":null,"evidence_quote":"Provides the adaptive preconditioning experiments on the funnel distribution that SLMC replicates."}],"review_version":1}