約束條件下的動力學朗之萬分裂格式

Kinetic Langevin Splitting Schemes for Constrained Sampling

https://arxiv.org/pdf/2603.23397

摘要

約束采樣是計算統(tǒng)計學中一項重要且具有挑戰(zhàn)性的任務(wù)，涉及在特定約束下從分布生成樣本。有許多類型的算法旨在完成此任務(wù)，范圍從一般的馬爾可夫鏈蒙特卡洛到未調(diào)整朗之萬方法。在本文中，我們提出了一系列基于后者（具體來說是動能朗之萬動力學）的新采樣算法。我們的系列算法基于高級數(shù)值方法，即分裂階格式，其中包括 BU 和 BAO 族分裂格式。它們的優(yōu)勢在于具有有利的強階（偏差）速率和計算效率。特別是，我們提供了一些理論見解，包括 Wasserstein 收縮和收斂結(jié)果。我們能夠展示有利的結(jié)果，例如相比現(xiàn)有非分裂方法改進了復雜度界。我們的結(jié)果通過一系列帶約束模型的數(shù)值實驗得到驗證，其中包括一個玩具示例和貝葉斯線性回歸。

關(guān)鍵詞： 約束采樣，分裂格式，未調(diào)整朗之萬算法，Wasserstein 復雜度。

1 引言

從概率分布中采樣在各種科學與工程領(lǐng)域發(fā)揮著至關(guān)重要的作用。此類領(lǐng)域的例子包括數(shù)值天氣預報、地球物理科學，以及近期的機器學習，例如生成模型或貝葉斯神經(jīng)網(wǎng)絡(luò) [SSDK21, HNPSD21, SDWMG15]。這些應用大多利用蒙特卡洛方法進行采樣，且限制有限，或者幾乎沒有任何顯著限制。然而，在許多情況下，人們有興趣考慮涉及凸集或緊集的采樣，換句話說，即將采樣限制在樣本空間內(nèi)的特定區(qū)域。我們將此任務(wù)稱為約束采樣，這將是本工作的重點。許多場景涉及在約束或受限空間上進行采樣，例如隨機最優(yōu)控制和分子動力學 [CEAMR12, LM15]。在此背景下，該問題涉及從此類集合上的概率測度（我們常稱之為目標測度） ν ν 中進行采樣，該測度由具有以下形式的密度函數(shù)表征：

使用 KLD（動能朗之萬動力學）優(yōu)于 OLD（過阻尼朗之萬動力學）的好處在于，已知前者能更快地收斂到其各自的不變測度。在貝葉斯采樣的背景下，公式 (1.5) 和 (1.7) 均可用于從分布 ν ν 生成樣本。這只需將勢函數(shù)設(shè)定為對數(shù)后驗即可實現(xiàn)，即 。最近的研究致力于將這些過程與著名的優(yōu)化算法聯(lián)系起來。為了實現(xiàn)此類動力學，直接使用全連續(xù)過程極具挑戰(zhàn)性，且往往是不可能的。因此，必須訴諸于離散化格式。最顯而易見的離散化方法是 Euler-Maruyama (EM) 格式，然而現(xiàn)有結(jié)果表明，基于偏差、復雜度和穩(wěn)定性的考量，存在替代方法。其中一種方法是隨機中點法 (RMM) [SL19]。RMM 還在誤差容限和條件數(shù)依賴性方面提供了優(yōu)勢，這一點已通過機器學習中的應用得到證明 [LJ24, YY25a, KD24]。在約束采樣的背景下，Yu 等人 [YY25b] 在其工作中使用了該方法，他們展示了更精確的近似分析，以及在 Wasserstein 距離方面改進的誤差界。

1.1 分裂格式族

求解常微分方程（ODEs）的一個流行選擇是分裂格式，其源于 Gilbert Strang [Str63] 的啟發(fā)，其中將動力學分裂為不同的分量并分別求解它們。之所以可行，是因為它們可以被精確積分。這也適用于包括 KLD 在內(nèi)的隨機微分方程（SDEs）。我們將介紹兩類分裂格式族，(i) BU 分裂族，和 (ii) BAO 分裂族。對于前者，這是在 [Zap21] 中提出的。該方法基于如下方式分裂 SDE (1.5)：

UBU 格式在 [SSZ21] 中得到了分析，其優(yōu)勢在于每次迭代僅需一次梯度評估，卻具有二階強誤差階。此外，如 [CLPW26] 所示，其步長穩(wěn)定性分析獨立于維度 p 。

其他對稱分裂方法也是可行的，且近年來已得到廣泛研究。特別是其中的 BAO 分裂格式。對應于這些部分的解映射可分別記為 B、A 和 O，定義如下：

如前所述，已知這些方法能達到 的弱階。然而，與 UBU 不同，它們在強誤差方面未能達到相同的速率。針對此類格式，收縮性與收斂性分析在以下文獻 [LPW24b, LPW24a] 中提出，其中也包括了對隨機梯度的擴展。

到目前為止，在約束采樣的背景下，對于理解 KLD 的分裂格式尚未建立聯(lián)系，這在懲罰設(shè)置下構(gòu)成了我們的動機。在討論本文的貢獻之前，我們簡要概述了使用各種基于朗之萬的算法進行約束采樣的相關(guān)工作。

1.2 其他相關(guān)工作

約束采樣的概念可能有多種不同的解釋，這取決于所采用的設(shè)置和施加的假設(shè)。我們的設(shè)置，至此已通過 (1.4) 簡要定義，基于 [GHZ24] 工作中首次引入的懲罰約束設(shè)置。他們的動機源于連續(xù)優(yōu)化中的懲罰方法，其中包括針對約束違反的懲罰項。然而，這并不是人們可以考慮的用于約束設(shè)置的唯一框架。一種自然但困難的設(shè)置可能是直接考慮流形，這需要復雜的數(shù)學方法才能有效地從目標分布中采樣。最近在朗之萬動力學背景下考慮這一點的研究包括 [KLV22, NDBD24]。其中一些工作需要技術(shù)性的耦合，以確保能夠獲得 Wasserstein 收斂性和收縮性。此外，這些工作大多基于接受 - 拒絕 MCMC 算法，如 HMC。盡管此類所提出的工作具有優(yōu)雅性，但我們考慮一個更簡化的設(shè)置，作為更容易的起點，以便在未來工作中再轉(zhuǎn)向潛在的流形設(shè)置。其他此類工作包括 [LST24]，其中作者為朗之萬動力學開發(fā)了受限 BAO 積分器。這是第一篇旨在在受限空間背景下利用此類分裂格式的論文。然而，其不同之處在于動力學被設(shè)計為在邊界處反射，且信息被編碼到積分器的每一步中。更近期的文獻包括 [DFT+25, CKK24]，這些論文考慮了一種不同的設(shè)置，其動機源于原對偶設(shè)置，且不包含 KLD 設(shè)置，即僅有一個底層過程 。

1.3 貢獻

我們通過以下幾點來強調(diào)本工作的貢獻：

? 我們引入了用于約束采樣任務(wù)的新算法，該任務(wù)基于從 (1.1) 進行采樣。具體而言，我們引入了基于分裂階離散化格式（即 UBU 和 BAOAB）的 ULA 型算法。因此，我們?yōu)楸咀魈岢龅男滤惴ò?CUBU 和 CBAOAB 算法。

? 我們?yōu)樯鲜鲇懻摰拿糠N新算法開發(fā)了步長穩(wěn)定性分析。此類分析利用了對底層勢函數(shù)的假設(shè)，例如凸性和平滑性假設(shè)，我們將在文檔后續(xù)部分提供這些假設(shè)。

? 我們提供了基于 Wasserstein 收斂的復雜度分析，這轉(zhuǎn)化為達到精度階 ε > 0 所需的步數(shù)。我們的復雜度界限總結(jié)在表 1 中，突出了使用分裂格式相較于傳統(tǒng)離散化格式所帶來的增益和改進。我們的結(jié)果將考慮不同的投影方法，其中包括 Bregman 投影和 Gauge 投影。

? 為了配合新開發(fā)的約束采樣算法，我們還提供了隨機梯度情形的擴展。這將包括 SG-CUBU 和 SG-BAOAB，以及一個此前未推導過的用于比較的非分裂格式。這些內(nèi)容也展示在表 1 中，同時也展示了相較于 SG-CKLMC 更優(yōu)的復雜度，我們也在本作中對該方法進行了考慮并提供了證明。

? 我們在一系列問題上提供了數(shù)值實驗，以展示約束分裂格式的性能提升。這將包括一個玩具問題，其約束通過三角形和圓形定義，以及一個更高級的貝葉斯邏輯回歸數(shù)值示例。對于每個示例，我們將新開發(fā)的算法與現(xiàn)有算法進行了比較。

1.4 提綱

本文的提綱如下：我們將從第2節(jié)開始，該節(jié)將概述后續(xù)章節(jié)所需的材料。這將包括對我們基于勢函數(shù)和密度函數(shù)所使用假設(shè)的討論，以及我們要引入的約束分裂階格式。這將引出第3節(jié)，我們在其中展示主要理論發(fā)現(xiàn)，包括步長穩(wěn)定性分析和Wasserstein復雜度界。我們將證明部分推遲至附錄A。為了驗證我們的理論結(jié)果，我們將在第4節(jié)介紹數(shù)值模擬，展示新方法下的改進，并在第5節(jié)總結(jié)我們的發(fā)現(xiàn)。我們還在附錄B中以算法形式展示了我們的新方法。

1.5 符號

2 背景材料與算法

在本節(jié)中，在討論我們的主要結(jié)果之前，我們提供了必要背景材料的概要介紹。其中包括對勢函數(shù)和緊集 K 所需的各種假設(shè)。此后，我們將介紹我們新的約束算法，我們稱之為 CUBU 和 CBAOAB。隨后，這也將擴展到隨機梯度的情形進行考慮。所有算法均以算法形式列于附錄中。

我們通過假設(shè)凸緊集 K 滿足以下假設(shè)來開始本節(jié)。

讓我們簡要討論一下上述每個假設(shè)。假設(shè) 2.1 非常重要，并且已在約束采樣領(lǐng)域的各種工作中被采用 [BDMP17, GHZ24]。提出假設(shè) 2.2 是為了確保能夠提供具有凸性的收斂性分析。最后，假設(shè) 2.3 是關(guān)于距離函數(shù)的假設(shè)，它確保了勢函數(shù)
繼承平滑性和強凸性。

與假設(shè) 2.3 相關(guān)，我們現(xiàn)在基于常用的投影類引入 的兩種選擇，即 Bregman 投影和 Gauge 投影。這些投影已廣泛應用于各種機器學習應用中，其中包括聚類和異常點檢測 [XNZ08, Gho19]。我們在下面陳述這一點。

2.1 約束分裂格式

讓我們介紹我們的第一個約束算法，我們稱之為 constrained-UBU，或簡稱為 CUBU。這種分裂的形式與 UBU [SSZ21] 的思路一致，關(guān)鍵區(qū)別在于 B-算子，其定義如下：

為了建立 UBU 在約束條件下的收斂性，我們需要 [SSZ21] 中定理 23 和 25 的以下結(jié)果。

我們現(xiàn)在將 UBU 現(xiàn)有的 Wasserstein 收斂結(jié)果擴展到 CUBU，如下所示。

2.2 向隨機梯度的擴展

對于許多實際場景而言，勢函數(shù)的精確計算可能很困難，或者非常耗時，尤其是在高維情形下。因此，我們考慮使用隨機梯度（SG），這種方法不需要對 ? U λ ( θ )

進行完整計算。我們要考慮的基于 SG 的方法的形式是基于小批量（mini-batching）的概念。為了探討 SG 變體，我們需要定義我們的不精確梯度，如下所示。

BAOAB 和 UBU 的隨機梯度版本已經(jīng)在一系列工作中得到了分析和討論，即 [CLPW26, LPW24a]，這些工作討論了 Wasserstein 度量下的收縮率和非漸近收斂性。稍后我們將利用其中一些結(jié)果，在約束設(shè)置下建立類似的結(jié)果。在我們的設(shè)置中，我們提供了另外兩種算法，即 SG-CUBU 和 SG-BAOAB，它們也分別在算法 1 和算法 2 中給出。為了避免重復，我們沒有列出全梯度版本的完整算法，但它們的遵循方式非常相似。

我們要簡要指出的是，假設(shè) 2.6 包含的子假設(shè)將針對不同的 SG 算法而有所不同。

2.3 Wasserstein 距離下的收斂性

為了驗證我們的誤差界，我們需要一個充分的度量。我們將考慮 Wasserstein 距離，這是一種用于展示采樣算法收斂性的流行度量。特別是，我們將重點關(guān)注 Wasserstein 收縮性 [EGZ19, Dal17]。其背后的核心思想是，如果證明了兩個測度之間的收縮性，這就意味著存在唯一的不變測度以及向該測度的收斂。這些結(jié)果的一般設(shè)置源于

3 主要結(jié)果

在本節(jié)中，我們提供來自上一節(jié)的所引入約束算法的主要結(jié)果。具體而言，我們將基于 2.3 小節(jié)中定義的 Wasserstein 復雜度提供一系列收斂結(jié)果。這將針對 CUBU、CBAOAB、它們的 SG 版本以及 SG-CKLMC 完成，后者利用了 KLD 的 Euler-Maruyama 離散化。最后，我們提供復雜度分析，就每個算法獲得一定水平精度所需的迭代次數(shù)而言。我們首先開始討論 CUBU。所有證明將推遲至附錄。

3.1 CUBU 的收斂性分析

3.1.1 向 SG-CUBU 的擴展

現(xiàn)在我們將重點放在帶有梯度的 CUBU 算法上，稱為 SG-CUBU。在下述定理中，我們量化了 SG-CUBU 算法輸出分布與目標密度 ν ν 之間的 Wasserstein-1 和 Wasserstein-2 距離。

3.2 CBAOAB 的收斂性分析

現(xiàn)在讓我們將我們的結(jié)果和設(shè)置擴展到約束 BAOAB 的方法，即 CBAOAB。 以下定理展示了約束下 BAOAB 格式的收斂結(jié)果。

本推論中 CBAOAB 方法的迭代復雜度與推論 3.1 中 CUBU 方法的迭代復雜度之間的比較表明，它們屬于同階，僅相差常數(shù)因子。

3.2.1 向 SG-CBAOAB 的擴展

如前所述，我們考慮將 CBAOAB 進一步擴展到隨機梯度，從而產(chǎn)生了一種名為 SG-CBAOAB 的新算法。下面我們展示一個主要收斂結(jié)果和一個詳細說明計算復雜度的推論。

3.3 SG-CKLMC 的結(jié)果

得益于我們對光滑代理函數(shù)與目標分布之間距離的改進分析，我們能夠推導出帶有隨機梯度的 CKLMC（稱為 SG-CKLMC）收斂速率的更緊上界，如下述定理所述。

4 數(shù)值實驗

在本節(jié)中，我們提供數(shù)值實驗，以比較表 1 中討論的用于約束采樣問題的算法。我們考慮三個問題，其中前兩個將是受單純形約束的簡單采樣問題，而我們的最后一個實驗將包括一個貝葉斯線性回歸問題。由于計算高維 Wasserstein 距離的困難，我們在本節(jié)中專注于二維設(shè)置，以便于更清晰的展示和更輕松的可視化。因此，我們將考慮一個二維正態(tài)分布，并考慮我們將施加于目標分布 ν ν 的 K K 的特定選擇。隨后，我們將給出一個關(guān)于貝葉斯線性回歸的最終示例。

4.1 圓形約束

4.2 三角形約束

對于我們的第二個數(shù)值實驗，我們現(xiàn)在考慮一個修改后的約束集，它是一個從原點平移開的 3-單純形，形式如下：

其中我們再次應用 Gauge 投影來強制執(zhí)行該約束。與之前一樣，我們在 K K 下運行每個算法 n = 1000
次迭代并對它們進行比較。下面的圖 3 展示了全梯度算法之間的這種比較，而圖 4 則是隨機梯度方法的比較。通過與圓形約束的結(jié)果進行比較，我們看到了幾乎相同的結(jié)果，這突顯了對于動能朗之萬動力學，通過使用帶有全梯度的分裂格式所帶來的性能提升。同樣，在隨機梯度下也出現(xiàn)了相同的效果，即分裂格式表現(xiàn)更好。

4.3 方形約束

我們現(xiàn)在考慮該問題的最后一個約束，即方形約束。它將類似于三角形約束，其中我們現(xiàn)在將集合定義為

我們的結(jié)果展示在圖 5 和圖 6 中。正如預期的那樣，與 CKLMC 和 SG-CKLMC 相比，約束分裂格式表現(xiàn)更好。

為了總結(jié)我們的第一個實驗，我們針對 K 的不同選擇，提供了所有算法之間運行時間（以秒為單位）的比較。這通過表 2 呈現(xiàn)。正如我們所預期的，CKLMC 的計算成本更低，但正如前文所示，其表現(xiàn)較差。

4.4 貝葉斯約束線性回歸

我們模擬的結(jié)果展示在圖 7 和圖 8 中。在圖 7 中，我們展示了不含隨機梯度的約束算法的結(jié)果。正如我們所觀察到的，表現(xiàn)最差的算法是 CKLMC，其中分布的大部分“質(zhì)量”集中在黃色方框附近，該方框記為
。然而，該分布覆蓋了整個約束集。這與分裂格式不同，后者表現(xiàn)更好，因為大部分質(zhì)量集中在正方形的右邊界上，而分布并未覆蓋整個正方形。圖 8 將此擴展到隨機梯度情形，其中觀察到了與之前進行的實驗類似的現(xiàn)象。

5 結(jié)論

本工作的目的是基于動能朗之萬動力學（KLD）為約束采樣提供新的統(tǒng)計算法。特別是，我們考慮使用分裂階格式，將 KLD 分裂為不同的分量。這自然地衍生出不同的分裂族，其中包括 ABO 和 BU。我們考慮了基于它們的兩種此類方法，即 BAOAB 和 UBU，以及它們的隨機梯度（SG）版本。為了考慮約束設(shè)置，我們提供了勢函數(shù)的修正版本，并在 Wasserstein 度量下提供了收斂性分析。此外，我們就達到特定精度水平所需的步數(shù)提供了復雜度分析。如表 1 所示，我們所有的格式都展示了相對于采用 EM 格式的 KLD 的復雜度優(yōu)勢。我們提供了數(shù)值證據(jù)以驗證我們的理論發(fā)現(xiàn)，其中包括一個貝葉斯線性回歸問題。

關(guān)于約束采樣，這項工作還有幾個可以探索的方向。

• 首先是使用額外的 SG-分裂格式，這些格式已顯示出前景，例如 SMS-UBU 方法 [PWCL25]。這是第一種能夠達到
  強階的隨機方法，它基于應用無放回小批量處理（minibatching without replacement），其形式如下：
  

• 第二個方向是考慮約束采樣的替代策略，例如受限采樣（confined sampling）。在此設(shè)置中，可以考慮反射擴散過程，例如 Leimkuhler 等人 [LM, LST24] 的工作。他們的設(shè)置與我們的非常不同，但允許以一種自然的方式應用不同的分裂格式，從而也能推導出新的收斂性和偏差率。這種方法的優(yōu)勢在于它對步長沒有限制。然而，挑戰(zhàn)在于如何在積分器的指數(shù)項內(nèi)設(shè)計約束。
• 最后，也可以將本文中的此類技術(shù)應用于無偏估計中。最近的工作分析了帶有分裂族的 KLD，其中包括一種名為 UBUBU 的方法論 [CLPW26, RCJ23]。這種方法論能夠減輕出現(xiàn)的偏差，而這在高維情形中普遍存在。據(jù)我們所知，唯一進行過無偏約束采樣的工作是 Noble 等人 [NDBD24] 的工作，但這需要使用新的復雜耦合技術(shù)。也可以利用 [CLLW24] 中的思想。

原文鏈接：https://arxiv.org/pdf/2603.23397