An Accelerated Proximal Gradient Method for Bures-Wasserstein Space

arXiv:2611.08468 · math.OC · Submitted 2026-11-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "An Accelerated Proximal Gradient Method for Bures-Wasserstein Space".

Emmy: Here's the gist of the paper. An Accelerated Proximal Gradient Method for Bures–Wasserstein Space studies composite optimization over Gaussian measures and identifies a class of problems solvable efficiently using accelerated proximal gradient methods The main observation is that a useful class of BW problems can be lifted into the Euclidean space of affine transport maps, such that the lifted problems can be solved efficiently using accelerated proximal gradient methods For objectives whose smooth and nonsmooth components admit convex smooth and convex proximable affine lifts, respectively, our algorithm BW-FISTA achieves minimax-optimal objective gap O(k−2) after k iterations Problem Formulation in BW Space The paper considers composite optimization over the Bures–Wasserstein (BW) space of Gaussian measures defined by inf µ∈BW h F(µ):= G(µ) + H(µ) i, where BW is N (m, Σ): m ∈ R d, Σ ∈ S d+ Mirroring the typical assumptions for Euclidean proximal gradient methods, we require that G satisfies a suitable notion of convexity and smoothness, and that H is appropriately convex and proximable The primary interest is Gaussian variational inference (VI), which seeks to approximate a distribution π ∝ exp(−V) by the minimizer of the KL divergence KL(µ∥π) over µ ∈ BW Lifting to Euclidean Space To apply Euclidean optimization methods in BW space, it is typical to represent µ as the pushforward of the standard Gaussian ρ:= N (0, Id) by an affine transport map Tb,A(x):= b + Ax This yields an optimization problem over the lifted Euclidean space parameterized by (b, A) ∈ R × R d×d The lifted function ΦF (b, A):= F((Tb,A)♯ρ) = F(N (b, AA⊤)) is a natural target for classical algorithms The authors identify sufficient conditions under which the lift ΦG is convex and L-smooth over R d × R d×d, and its Euclidean gradients are in correspondence with BW gradients of G Algorithm and Convergence Rates Our algorithm BW-FISTA applies a gradient step to the smooth function G and the proximal step to the nonsmooth function H The algorithm is identified with FISTA of Beck and Teboulle (2009) applied to the lifted composite objective ΦG + (ΦH + ιRd×S d+) over R d ×R d×d For the deterministic gradient setting, the convergence guarantee is F(µk) − F(µ⋆) ≤ 2R2 h(k + 1)2, leading to a rate O(LR2/k 2) when taking h = 1/L For stochastic gradients under Assumption 2, the expected objective gap is bounded by E

F(µk) − F(µ⋆): ≤ 4LR2 (k + 1)2 + 16Rσ¯ 3√k + 1, which allows for finding an ε-approximate minimizer using O(ε−1/2) BW gradient evaluations Function Classes and Examples Assumption 1 specifies the class of functions G and H for which the convergence rates of BW-FISTA apply Examples include the interaction energy of order n, where G(µ) = R(Rd)n V (x1,..., xn) dµ(x1)...

Ada: dµ(xn), and the mean–covariance function G(N (m, Σ)) = G(m, Σ) Function H examples include negative entropy Ent(µ), Schatten p-norm Tr

(Σµ)−q/2: , and operator norm Σµop Experimental Verification Synthetic Gaussian VI experiments verify the predicted rate improvements, showing that BW-FISTA converges faster than FB-GVI in the deterministic oracle setting The results demonstrate an initially accelerated convergence rate before entering a noise-dominated regime where the two methods are comparable Discussion and Future Work The work develops new tools for composite optimization over BW space, arriving at a minimax-optimal O(k−2) gradient complexity using accelerated proximal gradient methods The authors note that computation of the corresponding proximal problem remains a fundamental obstacle to practical implementation They suggest extending the existing theory to cover strong and locally strong convexity, which is relevant for many VI applications The BW-FISTA method can be directly extended to the full 2-Wasserstein space References Jason M.

Emmy: Altschuler, Sinho Chewi, Patrik R.

Ada: Gerber, and Austin J.

Paper summary: Ada: So this paper, "An Accelerated Proximal Gradient Method for Bures-Wasserstein Space," it looks at optimizing things over Gaussian measures and they claim they found a way to do it efficiently using accelerated proximal gradient methods. Emmy, what's the core idea here?

Emmy: Well, the main observation is that a whole class of problems in this Bures-Wasserstein space can be lifted into a standard Euclidean space using affine transport maps. This lift makes them solvable with classical accelerated proximal gradient methods.

Kolya: That sounds like they're trying to take something complicated from the probability space and turn it into a problem in regular Euclidean space where we have established tools for optimization. What kind of problems are they focusing on, Ada?

Ada: They are primarily interested in Gaussian variational inference, which is when you try to find the best distribution, pi, by minimizing the KL divergence against a target distribution using a measure mu from the Bures-Wasserstein space. This means G is the expected potential value and H is negative entropy.

Emmy: And for this to work with Euclidean methods, they need certain regularity conditions on G and H. Specifically, they require that after lifting them, the functions become convex and L-smooth over that lifted Euclidean space.

Kolya: So it's not just any optimization; it has to have this structure where the smooth part is convex and the nonsmooth part is proximable with a specific lift. What does that mean for applying an algorithm?

Ada: The algorithm they present, BW-FISTA, applies a gradient step to the smooth function G and a proximal step to the nonsmooth function H in this lifted Euclidean space. It's essentially FISTA of Beck and Teboulle applied to this composite objective.

Emmy: And the real payoff they are talking about is the convergence rate. They achieve what they call minimax-optimal objective gap, which is O of k minus two after k iterations. That's a significant result for how fast we can find an approximate solution.

Kolya: O of k minus two sounds good on paper, but in practice, what does that translate to when you're dealing with stochastic gradients? Does the noise affect that rate much?

Ada: Under the deterministic setting, the convergence guarantee is F of mu k minus F of mu star is less than or equal to two R squared h times k plus one squared. When you set h equal to one over L, that leads to a rate of O of L R squared over k squared.

Emmy: For stochastic gradients under Assumption two, the expected objective gap is bounded by four L R squared times k plus one squared plus sixteen R sigma cubed over the square root of k plus one. This allows you to find an epsilon approximate minimizer using a number of BW gradient evaluations that scales as O of epsilon minus one over two <ref:2611.08468#pg2>.

Paper summary: Kolya: So, for someone just looking at the numbers, it means you can get close to the best solution in terms of objective gap with a certain level of noise, and the number of steps needed grows reasonably slowly with respect to that error. What are some examples they use to show this works?

Ada: They verify these regularity conditions for potential and interaction energies together with common spectral regularizers. For instance, they look at the interaction energy of order n, which is defined as R of Rd n V x one times x one... d mu x two times... d mu x n.

Emmy: And for the nonsmooth part H, they use examples like negative entropy and Schatten p-norms, such as the trace of the matrix sigma mu minus q over two. These are standard terms in variational inference setups.

Kolya: I wonder about those examples in relation to their convergence rate. If you're dealing with these specific functions, is there a known practical limitation on how well this method performs compared to other things?

Ada: The experimental verification shows that synthetic Gaussian variational inference experiments verify the predicted rate improvements, showing that BW-FISTA converges faster than FB GVI in the deterministic oracle setting. But they also note that before entering a noise-dominated regime, it enjoys an initially accelerated convergence rate before flattening out to a typical O of k minus one over two rate <ref:2611.08468#pg2>.

Emmy: They also mention that the computation of the corresponding proximal problem is still a fundamental obstacle to practical implementation right now. This suggests the theory is strong, but getting it running smoothly in real applications has some hurdles.

Kolya: So, what does this mean for someone who only listens to this show? It means we have a new theoretical framework for composite optimization over these specific probability spaces that gives us a clear target rate of O of k minus two.

Ada: It means we've shown that by lifting these problems into the space of affine transport maps, we can use accelerated proximal gradient methods to tackle them efficiently. This is about finding a better way to solve complex inference problems in high dimensions.

Emmy: And the authors suggest extending this theory to cover strong and locally strong convexity, which is relevant for many variational inference applications because those properties are often what make the optimization landscape tractable.

Kolya: That sounds like a solid direction for future work, focusing on stronger conditions that might apply more frequently in real data scenarios. We'll keep an eye on how they extend this to the full two-Wasserstein space next.

Conclusion: Ada: So this paper, "An Accelerated Proximal Gradient Method for Bures-Wasserstein Space," is about finding a fast way to optimize things when you're working with Gaussian measures.

Emmy: Yeah, it uses this idea where they lift the problem from that complex probability space into a standard Euclidean space using affine transport maps.

Kolya: So what does that actually mean for solving these distribution problems? What’s the big payoff here?

Ada: The main point is they've found a class of problems in this Bures-Wasserstein space that can be solved very efficiently using accelerated proximal gradient methods.

Emmy: And they claim a minimax optimal objective gap of something like k minus two after k iterations, which is pretty good for how fast you get close to the best answer.

Kolya: That sounds promising, but what are the real limits? Are these results only for certain types of functions?

Ada: Yes, they lay out assumption one which specifies exactly what kind of functions G and H need to be for this convergence rate to hold true.

Emmy: The examples they use include interaction energies and mean covariance functions for G, and negative entropy or Schatten norms for H.

Kolya: So we're looking at these specific structures in the optimization landscape that allow this method to work, right?

Ada: Exactly, but they also point out that there are still real hurdles for practical implementation because setting up the proximal problem itself is still quite difficult.

Emmy: They even suggest extending this theory to cover stronger conditions like strong convexity later on, which would be useful for more complex variational inference tasks.

Kolya: So, it's a solid theoretical result with clear convergence rates and good examples, but the next step is making it practical. What does that mean for applying this in real-world machine learning?

Jakob Nyl཯, Sloan Nietert, Julien Pallage, Giancarlo Ferrari-Trecate, Daniel Kuhn, John Lygeros

EPFL · ETH Zurich

math.OC

Submitted: 2026-11-05

Updated: 2026-11-05

Comments: Submitted on September 2 to the Geometric Distributional Deep Learning workshop at NeurIPS 2026, accepted

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 100/100

The gist: An Accelerated Proximal Gradient Method for Bures–Wasserstein Space studies composite optimization over Gaussian measures and identifies a class of problems solvable efficiently using accelerated…

Key concepts

Bures–Wasserstein (BW) Space
This is the space where Gaussian measures live. It's used in problems like Gaussian variational inference, which aims to find a distribution by minimizing the KL divergence. The functions being optimized are defined over these probability distributions.
Affine Transport Map
This is a mathematical tool used to represent a measure $\mu$ in the BW space as a pushforward of the standard Gaussian. This allows researchers to transform the complex optimization problem in the curved BW space into an equivalent, simpler one in standard Euclidean space.
Accelerated Proximal Gradient Method (BW-FISTA)
This is a specific optimization algorithm designed for composite objectives. It combines gradient steps for smooth parts and proximal steps for nonsmooth parts of the objective function, applied to the problem after it has been lifted into Euclidean space.

Terminology

Summary

An Accelerated Proximal Gradient Method for Bures–Wasserstein Space studies composite optimization over Gaussian measures and identifies a class of problems solvable efficiently using accelerated proximal gradient methods The main observation is that a useful class of BW problems can be lifted into the Euclidean space of affine transport maps, such that the lifted problems can be solved efficiently using accelerated proximal gradient methods For objectives whose smooth and nonsmooth components admit convex smooth and convex proximable affine lifts, respectively, our algorithm BW-FISTA achieves minimax-optimal objective gap O(k−2) after k iterations

Problem Formulation in BW Space

The paper considers composite optimization over the Bures–Wasserstein (BW) space of Gaussian measures defined by inf µ∈BW h F(µ):= G(µ) + H(µ) i, where BW is N (m, Σ): m ∈ R d, Σ ∈ S d+ Mirroring the typical assumptions for Euclidean proximal gradient methods, we require that G satisfies a suitable notion of convexity and smoothness, and that H is appropriately convex and proximable The primary interest is Gaussian variational inference (VI), which seeks to approximate a distribution π ∝ exp(−V) by the minimizer of the KL divergence KL(µ∥π) over µ ∈ BW

Lifting to Euclidean Space

To apply Euclidean optimization methods in BW space, it is typical to represent µ as the pushforward of the standard Gaussian ρ:= N (0, Id) by an affine transport map Tb,A(x):= b + Ax This yields an optimization problem over the lifted Euclidean space parameterized by (b, A) ∈ R × R d×d The lifted function ΦF (b, A):= F((Tb,A)ρ) = F(N (b, AA⊤)) is a natural target for classical algorithms The authors identify sufficient conditions under which the lift ΦG is convex and L-smooth over R d × R d×d, and its Euclidean gradients are in correspondence with BW gradients of G

Algorithm and Convergence Rates

Our algorithm BW-FISTA applies a gradient step to the smooth function G and the proximal step to the nonsmooth function H The algorithm is identified with FISTA of Beck and Teboulle (2009) applied to the lifted composite objective ΦG + (ΦH + ιRd×S d+) over R d ×R d×d For the deterministic gradient setting, the convergence guarantee is F(µk) − F(µ⋆) ≤ 2R2 h(k + 1)2, leading to a rate O(LR2/k 2) when taking h = 1/L For stochastic gradients under Assumption 2, the expected objective gap is bounded by E[F(µk) − F(µ⋆)] ≤ 4LR2 (k + 1)2 + 16Rσ¯ 3√k + 1, which allows for finding an ε-approximate minimizer using O(ε−1/2) BW gradient evaluations

Function Classes and Examples

Assumption 1 specifies the class of functions G and H for which the convergence rates of BW-FISTA apply Examples include the interaction energy of order n, where G(µ) = R(Rd)n V (x1,..., xn) dµ(x1). p. 1 p. 1.. dµ(xn), and the mean–covariance function G(N (m, Σ)) = G(m, Σ) Function H examples include negative entropy Ent(µ), Schatten p-norm Tr[(Σµ)−q/2], and operator norm Σµop

Experimental Verification

Synthetic Gaussian VI experiments verify the predicted rate improvements, showing that BW-FISTA converges faster than FB-GVI in the deterministic oracle setting The results demonstrate an initially accelerated convergence rate before entering a noise-dominated regime where the two methods are comparable

Discussion and Future Work

The work develops new tools for composite optimization over BW space, arriving at a minimax-optimal O(k−2) gradient complexity using accelerated proximal gradient methods The authors note that computation of the corresponding proximal problem remains a fundamental obstacle to practical implementation They suggest extending the existing theory to cover strong and locally strong convexity, which is relevant for many VI applications The BW-FISTA method can be directly extended to the full 2-Wasserstein space

References

Jason M. Altschuler, Sinho Chewi, Patrik R. p. 9 Gerber, and Austin J. p. 9 Stromme. Averaging on the Bures–Wasserstein manifold: Dimension-free convergence of gradient descent Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. p. 9 Gradient Flows in Metric Spaces and in the Space of Probability Measures Martin Arjovsky, Soumith Chintala, and Léon Bottou. p. 9 Wasserstein generative adversarial networks Heinz H. p. 9 Bauschke and Patrick L. p. 9 Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces Amir Beck and Marc Teboulle. p. 9 A fast iterative shrinkage-thresholding algorithm for linear inverse problems Rajendra Bhatia, Tanvi Jain, and Yongdo Lim. p. 9 On the Bures–Wasserstein distance between positive definite matrices David M. p. 9 Blei, Alp Kucukelbir, and Jon D McAuliffe. p. 9 Variational inference: A review for statisticians Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. p. 9 Concentration Inequalities: A Nonasymptotic Theory of Independence Sinho Chewi, Tyler Maunu, Philippe Rigollet, and Austin J Stromme. p. 9 Gradient descent algorithms for BuresWasserstein barycenters Dean S Clark. p. 9 Short proof of a discrete Gronwall inequality Michael Ziyang Diao, Krishnakumar Balasubramanian, Sinho Chewi, and Adil Salim. p. 9 Forward-backward Gaussian variational inference via JKO in the Bures–Wasserstein space Yoel Drori. p. 9 The exact information-based complexity of smooth convex minimization Shuailing Feng, Yuhang Jiang, Wen Huang, and Shihui Ying. p. 9 A Riemannian accelerated proximal gradient method Andi Han, Bamdev Mishra, Pratik Kumar Jawanpuria, and Junbin Gao. p. 9 On Riemannian optimization over positive definite matrices with the Bures-Wasserstein geometry Roger A Horn and Charles R Johnson. p. 9 Matrix Analysis Wen Huang and Ke Wei. p. 9 Riemannian proximal gradient methods Yiheng Jiang, Sinho Chewi, and Aram-Alexandre Pooladian. p. 9 Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space Alejandro Jofré and Philip Thompson. p. 9 On variance reduction for stochastic smooth convex optimization with multiplicative noise Richard Jordan, David Kinderlehrer, and Felix Otto. p. 9 The variational formulation of the Fokker–Planck equation Marc Lambert, Sinho Chewi, Francis Bach, Silvère Bonnabel, and Philippe Rigollet. p. 9 Variational inference via Wasserstein gradient flows Guanghui Lan. p. 9 An optimal method for stochastic composite optimization Adrian S Lewis. p. 8 Convex analysis on the Hermitian matrices Valentina Masarotto, Victor M Panaretos, and Yoav Zemel. p. 6 Procrustes metrics on covariance operators and optimal transportation of Gaussian processes Peyman Mohajerin Esfahani and Daniel Kuhn. p. 0 Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations Yurii E. p. 0 Nesterov. A method for solving the convex programming problem with convergence rate O(1/k2) Lam M Nguyen, Katya Scheinberg, and Trang H Tran. p. 8 Stochastic ISTA/FISTA adaptive step search algorithms for convex composite optimization Neal Parikh and Stephen Boyd. p. 7 Proximal algorithms Adil Salim, Anna Korba, and Giulia Luise. p. 9 The Wasserstein proximal gradient algorithm Jiaqi Tang, Qin Li, and Wilfrid Gangbo. p. 1 Nesterov acceleration in optimizing over probability measures Charles F Van Loan. p. 0 The ubiquitous Kronecker product A Proof of Proposition 1 B Proof of Proposition 2 C Proof of Proposition 3 D Proof of Theorem 1 E Proof of Theorem 2 F Verification of Table 1 G Interaction Energy Gradient Oracle H Proof of Proposition 4

Pruning redundant reasoning tokens

The paper studies composite optimization over the Bures–Wasserstein (BW) space of Gaussian measures and identifies a class of problems solvable efficiently using accelerated proximal gradient methods The main observation is that a useful class of BW problems can be lifted into the Euclidean space of affine transport maps, such that the lifted problems can be solved efficiently using accelerated proximal gradient methods

How the training signal is built

To solve Problem (1), we impose regularity conditions on G and H, requiring G to be BW differentiable, lift convex with respect to R d × R d×d and lift L-smooth, and H to be proper, lower semicontinuous, lift convex with respect to R d × S d+ These conditions are equivalent at the level of the lifts ΦG and ΦH The algorithm BW-FISTA applies a gradient step to G and a proximal step to H, reducing the problem to minimizing the lifted composite objective over R d ×R d×d

Where the gains come from

The convergence rate of BW-FISTA is minimax optimal at O(k−2) after k iterations This optimality is achieved by lifting a Euclidean lower bound construction into BW space, proving that this rate is minimax optimal The stochastic gradient method enjoys an initially accelerated rate before flattening out to the typical O(k−1/2) rate, with the change occurring at a threshold determined by the noise level The analysis relies on Proposition 3, which shows that the problem is equivalent to minimizing a function over affine pairs (b', A') in R d ×S d+

Assumption 1 specifies the class of functions G and H for which the convergence rates of BW-FISTA apply Examples include the interaction energy of order n, where G(µ) = R(Rd)n V (x1,..., xn) dµ(x1)...

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Accelerated optimization of Gaussian variational inference can achieve a minimax optimal objective gap of O(k minus 2) after k iterations when using BW-FISTA under suitable regularity conditions for potential and interaction energies, improving upon previous rates of O(k minus 1).

  2. The system can find an epsilon approximate minimizer of the KL objective in Gaussian Variational Inference using only O epsilon minus one over two BW gradient evaluations, a significant speedup compared to the previous state-of-the-art rate of O epsilon minus one.

  3. Stochastic gradient methods for Gaussian VI can initially achieve an accelerated rate before flattening out to a typical O k minus 1 over two rate, with the change occurring at a threshold determined by the noise level, allowing for more efficient stopping criteria based on noise characteristics.

  4. The system can leverage the lifting of problems into Euclidean space of affine transport maps to solve composite optimization problems efficiently using classic accelerated proximal gradient methods like FISTA, even when operating over curved Bures-Wasserstein geometry.

  5. The system can be applied to Gaussian VI problems where the potential function V is smooth and convex, such as interaction energy of order n, allowing for the construction of stochastic gradient oracles satisfying Assumption 2 with specific bounds related to nL squared times the Frobenius norm of A.

Sources

Related papers