More Like this

1. First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces

   Michael I. Jordan; Tianyi Lin; Emmanouil V. Vlatakis-Gkaragkounis  (April 2023, Advances in neural information processing systems)

   From optimal transport to robust dimensionality reduction, a plethora of machine learning applications can be cast into the min-max optimization problems over Riemannian manifolds. Though many min-max algorithms have been analyzed in the Euclidean setting, it has proved elusive to translate these results to the Riemannian case. Zhang et al. [2022] have recently shown that geodesic convex concave Riemannian problems always admit saddle-point solutions. Inspired by this result, we study whether a performance gap between Riemannian and optimal Euclidean space convex-concave algorithms is necessary. We answer this question in the negative—we prove that the Riemannian corrected extragradient (RCEG) method achieves last-iterate convergence at a linear rate in the geodesically strongly-convex-concave case, matching the Euclidean result. Our results also extend to the stochastic or non-smooth case where RCEG and Riemanian gradient ascent descent (RGDA) achieve near-optimal convergence rates up to factors depending on curvature of the manifold. 

   more » « less
2. Geometry and convergence of natural policy gradient methods

   https://doi.org/10.1007/s41884-023-00106-z  

   Müller, Johannes; Montúfar, Guido (June 2023, Information Geometry)

   Abstract We study the convergence of several natural policy gradient (NPG) methods in infinite-horizon discounted Markov decision processes with regular policy parametrizations. For a variety of NPGs and reward functions we show that the trajectories in state-action space are solutions of gradient flows with respect to Hessian geometries, based on which we obtain global convergence guarantees and convergence rates. In particular, we show linear convergence for unregularized and regularized NPG flows with the metrics proposed by Kakade and Morimura and co-authors by observing that these arise from the Hessian geometries of conditional entropy and entropy respectively. Further, we obtain sublinear convergence rates for Hessian geometries arising from other convex functions like log-barriers. Finally, we interpret the discrete-time NPG methods with regularized rewards as inexact Newton methods if the NPG is defined with respect to the Hessian geometry of the regularizer. This yields local quadratic convergence rates of these methods for step size equal to the inverse penalization strength. 

   more » « less
3. Regularized Stein Variational Gradient Flow

   https://doi.org/10.1007/s10208-024-09663-w  

   He, Ye; Balasubramanian, Krishnakumar; Sriperumbudur, Bharath K; Lu, Jianfeng (July 2024, Foundations of Computational Mathematics)

   Abstract The stein variational gradient descent (SVGD) algorithm is a deterministic particle method for sampling. However, a mean-field analysis reveals that the gradient flow corresponding to the SVGD algorithm (i.e., the Stein Variational Gradient Flow) only provides a constant-order approximation to the Wasserstein gradient flow corresponding to the KL-divergence minimization. In this work, we propose the Regularized Stein Variational Gradient Flow, which interpolates between the Stein Variational Gradient Flow and the Wasserstein gradient flow. We establish various theoretical properties of the Regularized Stein Variational Gradient Flow (and its time-discretization) including convergence to equilibrium, existence and uniqueness of weak solutions, and stability of the solutions. We provide preliminary numerical evidence of the improved performance offered by the regularization. 

   more » « less
4. Birth–death dynamics for sampling: global convergence, approximations and their asymptotics

   https://doi.org/10.1088/1361-6544/acf988  

   Lu, Yulong; Slepčev, Dejan; Wang, Lihan (September 2023, Nonlinearity)

   Abstract Motivated by the challenge of sampling Gibbs measures with nonconvex potentials, we study a continuum birth–death dynamics. We improve results in previous works (Liuet al2023Appl. Math. Optim.8748; Luet al2019 arXiv:1905.09863) and provide weaker hypotheses under which the probability density of the birth–death governed by Kullback–Leibler divergence or byχ²divergence converge exponentially fast to the Gibbs equilibrium measure, with a universal rate that is independent of the potential barrier. To build a practical numerical sampler based on the pure birth–death dynamics, we consider an interacting particle system, which is inspired by the gradient flow structure and the classical Fokker–Planck equation and relies on kernel-based approximations of the measure. Using the technique of Γ-convergence of gradient flows, we show that on the torus, smooth and bounded positive solutions of the kernelised dynamics converge on finite time intervals, to the pure birth–death dynamics as the kernel bandwidth shrinks to zero. Moreover we provide quantitative estimates on the bias of minimisers of the energy corresponding to the kernelised dynamics. Finally we prove the long-time asymptotic results on the convergence of the asymptotic states of the kernelised dynamics towards the Gibbs measure. 

   more » « less
5. The gradient descent method from the perspective of fractional calculus

   https://doi.org/10.1002/mma.7127  

   Hai, Pham Viet; Rosenfeld, Joel A. (December 2020, Mathematical Methods in the Applied Sciences)

   Motivated by gradient methods in optimization theory, we give methods based onψ‐fractional derivatives of orderαin order to solve unconstrained optimization problems. The convergence of these methods is analyzed in detail. This paper also presents an Adams–Bashforth–Moulton (ABM) method for the estimation of solutions to equations involvingψ‐fractional derivatives. Numerical examples using the ABM method show that the fractional orderαand weightψare tunable parameters, which can be helpful for improving the performance of gradient descent methods. 

   more » « less