An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
summary
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…
In short
The paper proposes an Accelerated Proximal Gradient Method (BW-FISTA) to optimize composite functions over the Bures-Wasserstein (BW) space of Gaussian measures. By lifting these complex BW problems into a Euclidean space using affine transport maps, the method achieves a minimax-optimal convergence rate of O(k^-2), making it efficient for Gaussian variational inference.
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 used across episodes
This episode discusses
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space · Paper Radio
- A FISTA-type Riemannian Accelerated Proximal Gradient Method · Paper Radio
- Nesterov acceleration in optimizing over probability measures
The paper
An Accelerated Proximal Gradient Method for Bures-Wasserstein Space · Read on arXiv
Jakob Nyl, Sloan Nietert, Julien Pallage, Giancarlo Ferrari-Trecate, Daniel Kuhn, John Lygeros
EPFL · ETH Zurich
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?
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors