Pith. sign in

REVIEW 4 major objections 5 minor 75 references

Subspace Langevin Monte Carlo

T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict Novel and promising subspace sampling method, but the central theorem's proof has a genuine gap in the unrolling step. read the letter →

arxiv 2412.13928 v2 pith:2OZ5AF4U submitted 2024-12-18 stat.ML cs.LG

Tyler Maunu , Jiayi Yao This is my paper · ORCID
classification stat.MLcs.LG
keywords LangevinMonteCarlosubspacemethodsrandomcoordinatedescentpreconditionedsamplingWassersteingradientflowill-conditioneddistributionscouplingargumentdirectionalderivativecomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Appendix A.4, proof of Theorem 3] 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.
  2. [Appendix A.4, Lemma 3] 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.
  3. [Section 4.4 and Table 1] 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.
  4. [Assumption 2 (Eq. 19)] 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.
minor comments (5)
  1. [Section 4.3 / Appendix A.4] 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, )'.
  2. [Appendix A.2, proof of Lemma 2] 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.
  3. [Section 4.3, Theorem 3 notation] 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.
  4. [Section 4.4, simplification of Theorem 3] 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.
  5. [Section 5] The paper does not provide code or data for the experiments, so the empirical claims cannot be reproduced from the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the SLMC convergence bound follows from explicit coupling assumptions; the flagged Assumption 2 unrolling issue is a proof gap, not input-output equivalence.

full rationale

The paper's central derivation chain is Theorem 3 in Section 4.3, proved in Appendix A.4. The bound is obtained by coupling the SLMC chain to an auxiliary process and controlling the second moment of the synchronous coupling under the A_k^{-1} norm, using relative strong convexity and smoothness (Assumptions 1 and 5), the eigenblock sampling probabilities (Assumption 4), and the step-size restriction h ≤ min_i φ_{ik}/M_k. The contraction factor (1 - hm/2) is not an input; it arises from m-relative strong convexity and M-relative smoothness combined with the chosen step size. No parameter in the theorem is fitted to data, and no displayed equation equates the conclusion to an input by construction. Assumption 2 (Eq. 19) does involve W2 distances of the iterates, but it only bounds the effect of changing the preconditioner at the same measure by O(h^2); it does not assume the theorem's contraction or error bound. The RCLMC and mirror-LMC results of [1, 19, 20] are external supporting results, and [20] treats a special case (RCLMC) rather than the full SLMC claim. The only author self-citation, [13], is a related-work pointer to mirror-Langevin ergodicity and is not load-bearing for any theorem here. The skeptic's attack identifies a real proof gap, not circularity: Appendix A.4 states 'Using Assumption 2 and unrolling' to transfer the coupling bound from the A_k^{-1} norm to the A_{k+1}^{-1} norm, while Assumption 2 bounds optimal-transport distances, not the second moment of the specific synchronous coupling, and no Loewner slow-variation condition is provided. That is a correctness risk in the proof, but it does not make the theorem's conclusion equivalent to its assumptions, nor does it rename a fitted quantity as a prediction. Consequently the circularity score is 0.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central claim rests on five explicit assumptions (Assumptions 1-5 in Section 4). Assumption 2 and Assumption 3 are strong and not satisfied by common adaptive preconditioners; Lemma 3's proof contains a trace identity that is incorrect for general W. No fitted scalar parameters appear; the step size and block probabilities are user choices.

free parameters (2)
  • block sampling probabilities φ_ik
    Chosen by the user in Assumption 4; they appear in the complexity bound and the step size scaling. Not fitted to data.
  • step size h
    Algorithmic hyperparameter; the theorem requires h ≤ min φ_ik/M_k, and the complexity result sets h to balance bias and error.
assumptions (6)
  • domain assumption Assumption 1: V is m-relatively strongly convex and M-relatively smooth with respect to ||·||_{A_k^{-1}} for all k.
    Defines the class of targets and is used throughout the proof.
  • domain assumption Assumption 2: The sequence A_k satisfies W_{2,A_k^{-1}}^2(μ_k, π) ≤ W_{2,A_{k-1}^{-1}}^2(μ_k, π) + O(h^2) and A_k ⪯ C I.
    Used to handle time-varying preconditioners in the unrolling step of the proof (Appendix A.3, Eq. (28)). Not verified for standard adaptive preconditioners.
  • domain assumption Assumption 3: Preconditioners A_j may depend on distributions Law(X_i) and Law(∇^j V(X_i)) but not on the particles X_i directly.
    Needed to take expectations in the coupling argument; rules out particle-dependent adaptive preconditioners like RMSProp.
  • domain assumption Assumption 4: P_k is a randomly selected eigenblock of A_k with probability φ_ik and h_k = h/φ_ik.
    Defines the SLMC update; ensures hA_k = E[h_k P_k].
  • domain assumption Assumption 5: Directional smoothness of V along the subspace U with constant M_k(U).
    Used to bound the error between the auxiliary process and SLMC in Appendix A.4.
  • standard math Lemma 1: F is α-strongly geodesically convex iff V is α-strongly convex.
    Standard result in Wasserstein gradient flows, cited to [12].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Subspace Langevin Monte Carlo." pith.science (2026). https://pith.science/paper/2OZ5AF4U

@misc{pith2026241213928,
  author       = {Pith},
  title        = {Pith review of: Subspace Langevin Monte Carlo},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2OZ5AF4U}},
  note         = {Machine review of arXiv:2412.13928}
}
read the original abstract

Sampling from high-dimensional distributions has wide applications in data science and machine learning but poses significant computational challenges. We introduce Subspace Langevin Monte Carlo (SLMC), a novel and efficient sampling method that generalizes random-coordinate Langevin Monte Carlo and preconditioned Langevin Monte Carlo by projecting the Langevin update onto subsampled eigenblocks of a time-varying preconditioner at each iteration. The advantage of SLMC is its superior adaptability and computational efficiency compared to traditional Langevin Monte Carlo and preconditioned Langevin Monte Carlo. Using coupling arguments, we establish error guarantees for SLMC and demonstrate its practical effectiveness through a few experiments on sampling from ill-conditioned distributions.

Figures

Figures reproduced from arXiv: 2412.13928 by the authors.

Figure 1
Figure 1. Experiments demonstrating the convergence of SLMC and PLMC compared to [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Samples and contours for Bayesian logistic regression experiment. [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Kernelized Stein Discrepancy versus iterations for samples from Bayesian logistic [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Experiment from [71] demonstrating SLMC on the funnel distribution. [PITH_FULL_IMAGE:figures/full_fig_p019_4.png]
Figure 5
Figure 5. Figure 5: Experiment from [71] demonstrating SLMC on a rotated funnel distribution. [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

75 extracted references · 50 canonical work pages

  1. [1]

    Efficientconstrainedsamplingviathemirror-langevin algorithm

    KwangjunAhnandSinhoChewi. Efficientconstrainedsamplingviathemirror-langevin algorithm. Advances in Neural Information Processing Systems, 34:28405–28418, 2021

    work page 2021

  2. [2]

    The fast Johnson–Lindenstrauss transform and approximate nearest neighbors.SIAM Journal on Computing, 39(1):302–322, 2009

    Nir Ailon and Bernard Chazelle. The fast Johnson–Lindenstrauss transform and approximate nearest neighbors.SIAM Journal on Computing, 39(1):302–322, 2009

    2009

  3. [3]

    Springer Science & Business Media, 2008

    Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré.Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008

    2008

  4. [4]

    High- dimensional sgd aligns with emerging outlier eigenspaces

    Gerard Ben Arous, Reza Gheissari, Jiaoyang Huang, and Aukosh Jagannath. High- dimensional sgd aligns with emerging outlier eigenspaces. InThe Twelfth International Conference on Learning Representations, 2024

    work page 2024

  5. [5]

    Fast sampling and inference via preconditioned Langevin dynamics.arXiv preprint arXiv:2310.07542, 2023

    Riddhiman Bhattacharya and Tiefeng Jiang. Fast sampling and inference via preconditioned Langevin dynamics.arXiv preprint arXiv:2310.07542, 2023

    arXiv 2023

  6. [6]

    Efficientgradient flows in sliced-Wasserstein space.Transactions on Machine Learning Research, 2022

    ClémentBonet, NicolasCourty, FrançoisSeptier, andLucasDrumetz. Efficientgradient flows in sliced-Wasserstein space.Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL https://openreview.net/forum?id=Au1LNKmRvh

    work page 2022

  7. [7]

    Mirror and preconditioned gradient descent in wasserstein space.arXiv preprint arXiv:2406.08938, 2024

    Clément Bonet, Théo Uscidda, Adam David, Pierre-Cyril Aubin-Frankowski, and Anna Korba. Mirror and preconditioned gradient descent in wasserstein space.arXiv preprint arXiv:2406.08938, 2024

    arXiv 2024

  8. [8]

    Sliced and Radon Wasserstein barycenters of measures.Journal of Mathematical Imaging and Vision, 51: 22–45, 2015

    Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and Radon Wasserstein barycenters of measures.Journal of Mathematical Imaging and Vision, 51: 22–45, 2015. 20

    work page 2015

Show all 75 references
  1. [9]

    Finding frequent items in data streams

    Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theoretical Computer Science, 312(1):3–15, 2004

    2004

  2. [10]

    Exploring low-dimensional subspaces in diffusion models for controllable image editing

    Siyi Chen, Huijie Zhang, Minzhe Guo, Yifu Lu, Peng Wang, and Qing Qu. Exploring low-dimensional subspaces in diffusion models for controllable image editing. arXiv preprint arXiv:2409.02374, 2024

    2024

  3. [11]

    Improved analysis for a proximal algorithm for sampling

    Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. InConference on Learning Theory, pages 2984–3014. PMLR, 2022

    2022

  4. [12]

    Log-concave sampling

    Sinho Chewi. Log-concave sampling. Book draft available at https://chewisinho.github.io, 2024

    2024

  5. [13]

    Exponential ergodicity of mirror-Langevin diffusions

    Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, and Austin Stromme. Exponential ergodicity of mirror-Langevin diffusions. Advances in Neural Information Processing Systems, 33, 2020

    2020

  6. [14]

    Differential privacy dynamics of langevin diffusion and noisy gradient descent

    Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34:14771–14781, 2021

    2021

  7. [15]

    Gradient descent with low-rank objective functions

    Romain Cosson, Ali Jadbabaie, Anuran Makur, Amirhossein Reisizadeh, and Devavrat Shah. Gradient descent with low-rank objective functions. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 3309–3314. IEEE, 2023

    2023

  8. [16]

    Low-rank gradient descent.IEEE Open Journal of Control Systems, 2023

    Romain Cosson, Ali Jadbabaie, Anuran Makur, Amirhossein Reisizadeh, and Devavrat Shah. Low-rank gradient descent.IEEE Open Journal of Control Systems, 2023

    2023

  9. [17]

    User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient.Stochastic Processes and their Applications, 129 (12):5278–5311, 2019

    Arnak S Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient.Stochastic Processes and their Applications, 129 (12):5278–5311, 2019

    2019

  10. [18]

    A sparse Johnson–Lindenstrauss transform

    Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse Johnson–Lindenstrauss transform. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pages 341–350, 2010

    2010

  11. [19]

    Langevin monte carlo: random coordinate descent and variance reduction.Journal of machine learning research, 22(205):1–51, 2021

    Zhiyan Ding and Qin Li. Langevin monte carlo: random coordinate descent and variance reduction.Journal of machine learning research, 22(205):1–51, 2021

    2021

  12. [20]

    Random coordinate Langevin Monte Carlo

    Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen J Wright. Random coordinate Langevin Monte Carlo. InConference on Learning Theory, pages 1683–1710. PMLR, 2021

    2021

  13. [21]

    Adaptive subgradient methods for online learning and stochastic optimization.Journal of machine learning research, 12(7), 2011

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization.Journal of machine learning research, 12(7), 2011

    2011

  14. [22]

    High-dimensional bayesian inference via the unadjusted langevin algorithm.Bernoulli, 25(4A):2854–2882, 2019

    Alain Durmus and Eric Moulines. High-dimensional bayesian inference via the unadjusted langevin algorithm.Bernoulli, 25(4A):2854–2882, 2019

    2019

  15. [23]

    Analysis of Langevin Monte Carlo via convex optimization

    Alain Durmus, Szymon Majewski, and Błażej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. Journal of Machine Learning Research, 20(73):1–46, 2019. 21

    2019

  16. [24]

    Sketchy: Memory-efficient adaptive regularization with frequent directions.Advances in Neural Information Processing Systems, 36, 2024

    Vladimir Feinberg, Xinyi Chen, Y Jennifer Sun, Rohan Anil, and Elad Hazan. Sketchy: Memory-efficient adaptive regularization with frequent directions.Advances in Neural Information Processing Systems, 36, 2024

    2024

  17. [25]

    Convergence analysis of prediction markets via randomized subspace descent.Advances in Neural Information Processing Systems, 28, 2015

    Rafael Frongillo and Mark D Reid. Convergence analysis of prediction markets via randomized subspace descent.Advances in Neural Information Processing Systems, 28, 2015

    2015

  18. [26]

    Measuring sample quality with kernels

    Jackson Gorham and Lester Mackey. Measuring sample quality with kernels. In International Conference on Machine Learning, pages 1292–1301. PMLR, 2017

    2017

  19. [27]

    Rsn: randomized subspace Newton

    Robert Gower, Dmitry Kovalev, Felix Lieder, and Peter Richtárik. Rsn: randomized subspace Newton. Advances in Neural Information Processing Systems, 32, 2019

    2019

  20. [28]

    Randomized iterative methods for linear systems

    Robert M Gower and Peter Richtárik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 36(4):1660–1690, 2015

    2015

  21. [29]

    Stochastic quasi-gradient methods: Variance reduction via jacobian sketching.Mathematical Programming, 188 (1):135–192, 2021

    Robert M Gower, Peter Richtárik, and Francis Bach. Stochastic quasi-gradient methods: Variance reduction via jacobian sketching.Mathematical Programming, 188 (1):135–192, 2021

    2021

  22. [30]

    Stochastic dual ascent for solving linear systems

    Robert Mansel Gower and Peter Richtárik. Stochastic dual ascent for solving linear systems. arXiv preprint arXiv:1512.06890, 2015

    2015 arXiv

  23. [31]

    Improving neural network training in low dimensional random bases.Advances in Neural Information Processing Systems, 33:12140–12150, 2020

    Frithjof Gressmann, Zach Eaton-Rosen, and Carlo Luschi. Improving neural network training in low dimensional random bases.Advances in Neural Information Processing Systems, 33:12140–12150, 2020

    2020

  24. [32]

    Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

    Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217–288, 2011

    2011

  25. [33]

    Sega: Variance reduction via gradient sketching.Advances in Neural Information Processing Systems, 31, 2018

    Filip Hanzely, Konstantin Mishchenko, and Peter Richtárik. Sega: Variance reduction via gradient sketching.Advances in Neural Information Processing Systems, 31, 2018

    2018

  26. [34]

    Stochastic subspace cubic Newton method

    Filip Hanzely, Nikita Doikov, Yurii Nesterov, and Peter Richtarik. Stochastic subspace cubic Newton method. InInternational Conference on Machine Learning, pages 4027–

  27. [35]

    Denoising diffusion probabilistic models

    Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840–6851, 2020

    2020

  28. [36]

    Mirrored langevin dynamics

    Ya-Ping Hsieh, Ali Kavis, Paul Rolland, and Volkan Cevher. Mirrored langevin dynamics. Advances in Neural Information Processing Systems, 31:2878–2887, 2018

    2018

  29. [37]

    Communication-efficient distributed sgd with sketching

    Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Ion Stoica, Raman Arora, et al. Communication-efficient distributed sgd with sketching. Advances in Neural Information Processing Systems, 32, 2019

    2019

  30. [38]

    On the relation between the sharpest directions of dnn loss and the sgd step length

    Stanisław Jastrzębski, Zachary Kenton, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. On the relation between the sharpest directions of dnn loss and the sgd step length. InInternational Conference on Learning Representations, 2019. 22

    2019

  31. [39]

    Subspace diffusion generative models

    Bowen Jing, Gabriele Corso, Renato Berlinghieri, and Tommi Jaakkola. Subspace diffusion generative models. InEuropean Conference on Computer Vision, pages 274–

  32. [40]

    Extensions of Lipschitz maps into Banach spaces

    William B Johnson, Joram Lindenstrauss, and Gideon Schechtman. Extensions of Lipschitz maps into Banach spaces. Israel Journal of Mathematics, 54(2):129–138, 1986

    1986

  33. [41]

    The variational formulation of the fokker–planck equation.SIAM journal on mathematical analysis, 29(1):1–17, 1998

    Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the fokker–planck equation.SIAM journal on mathematical analysis, 29(1):1–17, 1998

    1998

  34. [42]

    A stochastic subspace approach to gradient-free optimization in high dimensions

    David Kozak, Stephen Becker, Alireza Doostan, and Luis Tenorio. A stochastic subspace approach to gradient-free optimization in high dimensions. Computational Optimization and Applications, 79(2):339–368, 2021

    2021

  35. [43]

    Measuring the intrinsic dimension of objective landscapes

    Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. InInternational Conference on Learning Representations, 2018

    2018

  36. [44]

    Low dimensional trajectory hypothesis is true: DNNs can be trained in tiny subspaces.IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):3411–3420, 2022

    Tao Li, Lei Tan, Zhehao Huang, Qinghua Tao, Yipeng Liu, and Xiaolin Huang. Low dimensional trajectory hypothesis is true: DNNs can be trained in tiny subspaces.IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):3411–3420, 2022

    2022

  37. [45]

    Memory-efficient llm training with online subspace descent.arXiv preprint arXiv:2408.12857, 2024

    Kaizhao Liang, Bo Liu, Lizhang Chen, and Qiang Liu. Memory-efficient llm training with online subspace descent.arXiv preprint arXiv:2408.12857, 2024

    2024 arXiv

  38. [46]

    Stein variational gradient descent: A general purpose Bayesian inference algorithm

    Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose Bayesian inference algorithm. 29, 2016

    2016

  39. [47]

    Relatively smooth convex optimization by first-order methods, and applications.SIAM Journal on Optimization, 28(1):333–354, 2018

    Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications.SIAM Journal on Optimization, 28(1):333–354, 2018

    2018

  40. [48]

    A complete recipe for stochastic gradient MCMC

    Yi-An Ma, Tianqi Chen, and Emily Fox. A complete recipe for stochastic gradient MCMC. Advances in Neural Information Processing Systems, 28, 2015

    2015

  41. [49]

    Sampling in unit time with kernel fisher-rao flow

    Aimee Maurais and Youssef Marzouk. Sampling in unit time with kernel fisher-rao flow. In International Conference on Machine Learning, pages 35138–35162. PMLR, 2024

    2024

  42. [50]

    McMahan and Matthew Streeter

    H. McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. The 23rd Conference on Learning Theory, 02 2010

    2010

  43. [51]

    Efficiency of coordinate descent methods on huge-scale optimization problems

    Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341–362, 2012

    2012

  44. [52]

    Random gradient-free minimization of convex functions

    Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017

    2017

  45. [53]

    Lyapunov functions: An optimization theory perspective

    Boris Polyak and Pavel Shcherbakov. Lyapunov functions: An optimization theory perspective. IFAC-PapersOnLine, 50(1):7456–7461, 2017. 23

    2017

  46. [54]

    High-resolution image synthesis with latent diffusion models

    Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684–10695, 2022

    2022

  47. [55]

    Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference

    Abhishek Roy, Lingqing Shen, Krishnakumar Balasubramanian, and Saeed Ghadimi. Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference. Bernoulli, 28(3):1810–1834, 2022

    2022

  48. [56]

    Eigenvalues of the hessian in deep learning: Singularity and beyond.arXiv preprint arXiv:1611.07476, 2016

    Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond.arXiv preprint arXiv:1611.07476, 2016

    2016 arXiv

  49. [57]

    Empirical analysis of the hessian of over-parametrized neural networks.arXiv preprint arXiv:1706.04454, 2017

    Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks.arXiv preprint arXiv:1706.04454, 2017

    2017 arXiv

  50. [58]

    {Euclidean, metric, and Wasserstein } gradient flows: an overview

    Filippo Santambrogio. {Euclidean, metric, and Wasserstein } gradient flows: an overview. Bulletin of Mathematical Sciences, 7:87–154, 2017

    2017

  51. [59]

    Does sgd really happen in tiny subspaces? arXiv preprint arXiv:2405.16002, 2024

    Minhak Song, Kwangjun Ahn, and Chulhee Yun. Does sgd really happen in tiny subspaces? arXiv preprint arXiv:2405.16002, 2024

    2024 arXiv

  52. [60]

    Score-based generative modeling through stochastic differential equations

    Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021

    2021

  53. [61]

    Rmsprop: Divide the gradient by a running average of its recent magnitude.Coursera, 2012

    Tijmen Tieleman and Geoffrey Hinton. Rmsprop: Divide the gradient by a running average of its recent magnitude.Coursera, 2012

    2012

  54. [62]

    Optimal preconditioning and Fisher adaptive Langevin sampling

    Michalis Titsias. Optimal preconditioning and Fisher adaptive Langevin sampling. Advances in Neural Information Processing Systems, 36, 2024

    2024

  55. [63]

    Improved analysis of the subsampled randomized Hadamard transform

    Joel A Tropp. Improved analysis of the subsampled randomized Hadamard transform. Advances in Adaptive Data Analysis, 3(01n02):115–126, 2011

    2011

  56. [64]

    Theoretical guarantees for sampling and inference in generative models with latent diffusions

    Belinda Tzen and Maxim Raginsky. Theoretical guarantees for sampling and inference in generative models with latent diffusions. InConference on Learning Theory, pages 3084–3114. PMLR, 2019

    2019

  57. [65]

    Score-basedgenerativemodelinginlatent space

    ArashVahdat, KarstenKreis, andJanKautz. Score-basedgenerativemodelinginlatent space. Advances in Neural Information Processing Systems, 34:11287–11302, 2021

    2021

  58. [66]

    Optimal transport: old and new, volume 338

    Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009

    2009

  59. [67]

    Diffusion models learn low-dimensional distributions via subspace clustering

    Peng Wang, Huijie Zhang, Zekai Zhang, Siyi Chen, Yi Ma, and Qing Qu. Diffusion models learn low-dimensional distributions via subspace clustering. arXiv preprint arXiv:2409.02426, 2024

    2024 arXiv

  60. [68]

    Information Newton’s flow: second-order optimization method in probability space.arXiv preprint arXiv:2001.04341, 2020

    Yifei Wang and Wuchen Li. Information Newton’s flow: second-order optimization method in probability space.arXiv preprint arXiv:2001.04341, 2020

    2001 arXiv

  61. [69]

    Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem

    Andre Wibisono. Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem. In Conference on Learning Theory, pages 2093–3027. PMLR, 2018. 24

    2018

  62. [70]

    Coordinate descent algorithms.Mathematical programming, 151(1): 3–34, 2015

    Stephen J Wright. Coordinate descent algorithms.Mathematical programming, 151(1): 3–34, 2015

    2015

  63. [71]

    Scalablestochastic gradient Riemannian Langevin dynamics in non-diagonal metrics

    HanlinYu, MarceloHartmann, BernardoWilliams, andArtoKlami. Scalablestochastic gradient Riemannian Langevin dynamics in non-diagonal metrics. Transactions on Machine Learning Research, 2024

    2024

  64. [72]

    Scalable semidefinite programming.SIAM Journal on Mathematics of Data Science, 3 (1):171–200, 2021

    Alp Yurtsever, Joel A Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. Scalable semidefinite programming.SIAM Journal on Mathematics of Data Science, 3 (1):171–200, 2021

    2021

  65. [73]

    Wasserstein control of mirror Langevin Monte Carlo

    Kelvin Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra. Wasserstein control of mirror Langevin Monte Carlo. InConference on Learning Theory, pages 3814–3841. PMLR, 2020

    2020

  66. [74]

    Galore: memory-efficient llm training by gradient low-rank projection

    Jiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: memory-efficient llm training by gradient low-rank projection. In Proceedings of the 41st International Conference on Machine Learning, pages 61121– 61143, 2024. A Supplementary...

    2024

  67. [75]

    25 Thus we can apply Grönwall’s lemma tof (Zs, Z′ s) to find f (Zt, Z′ t) ≤ exp(−2 Z t 0 mds)f (Z0, Z′ 0)

    = 2 Z t 0 ⟨Zs − Z ′ s, ∇V (Zs) − ∇V (Z ′ s)⟩ds ≤ 2 Z t 0 mf (Zs, Z′ s)ds. 25 Thus we can apply Grönwall’s lemma tof (Zs, Z′ s) to find f (Zt, Z′ t) ≤ exp(−2 Z t 0 mds)f (Z0, Z′ 0). A.3 Proof of Theorem 2 Proof. In the case of a fixedA, this theorem is just a particular case of...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.