Riemannian Hamiltonian methods for min-max optimization on manifolds
- URL: http://arxiv.org/abs/2204.11418v3
- Date: Thu, 24 Aug 2023 09:52:55 GMT
- Title: Riemannian Hamiltonian methods for min-max optimization on manifolds
- Authors: Andi Han, Bamdev Mishra, Pratik Jawanpuria, Pawan Kumar, Junbin Gao
- Abstract summary: We introduce a Hamiltonian function, of which serves as a proxy for solving the original min-max problems.
Under the Polyak--Lojasiewicz condition on the Hamiltonian function, its minimizer corresponds to the desired min-max saddle point.
We illustrate the efficacy of the proposed RHM in applications such as subspace robuststein distance, robust training of neural networks, and generative adversarial networks.
- Score: 36.02598732083467
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study min-max optimization problems on Riemannian
manifolds. We introduce a Riemannian Hamiltonian function, minimization of
which serves as a proxy for solving the original min-max problems. Under the
Riemannian Polyak--{\L}ojasiewicz condition on the Hamiltonian function, its
minimizer corresponds to the desired min-max saddle point. We also provide
cases where this condition is satisfied. For geodesic-bilinear optimization in
particular, solving the proxy problem leads to the correct search direction
towards global optimality, which becomes challenging with the min-max
formulation. To minimize the Hamiltonian function, we propose Riemannian
Hamiltonian methods (RHM) and present their convergence analyses. We extend RHM
to include consensus regularization and to the stochastic setting. We
illustrate the efficacy of the proposed RHM in applications such as subspace
robust Wasserstein distance, robust training of neural networks, and generative
adversarial networks.
Related papers
- Implicit Riemannian Optimism with Applications to Min-Max Problems [23.421903887404618]
We introduce an optimistic online learning algorithm for Hadamard problems.
Our method can handle in-mani-fold constraints, and matches the best known bounds on the Euclidean setting.
arXiv Detail & Related papers (2025-01-30T14:31:28Z) - A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks.
We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks.
Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
arXiv Detail & Related papers (2024-04-18T16:46:08Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate.
To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
arXiv Detail & Related papers (2023-06-29T01:20:44Z) - Decentralized Riemannian natural gradient methods with Kronecker-product
approximations [11.263837420265594]
We present an efficient decentralized natural gradient descent (DRNGD) method for solving decentralized manifold optimization problems.
By performing the communications over the Kronecker factors, a high-quality approximation of the RFIM can be obtained in a low cost.
arXiv Detail & Related papers (2023-03-16T19:36:31Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
The minimax algorithms for neural networks have been developed to solve many problems.
In this paper, we propose two types of minimax algorithms.
For the setting, we propose DRSGDA and prove that our method achieves a gradient.
arXiv Detail & Related papers (2023-02-08T01:42:45Z) - First-Order Algorithms for Min-Max Optimization in Geodesic Metric
Spaces [93.35384756718868]
min-max algorithms have been analyzed in the Euclidean setting.
We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
arXiv Detail & Related papers (2022-06-04T18:53:44Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
We propose a generalization extraient spaces which converges to a stationary point.
The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
arXiv Detail & Related papers (2020-10-31T21:35:42Z) - Riemannian Stochastic Proximal Gradient Methods for Nonsmooth
Optimization over the Stiefel Manifold [7.257751371276488]
R-ProxSGD and R-ProxSPB are generalizations of proximal SGD and proximal SpiderBoost.
R-ProxSPB algorithm finds an $epsilon$-stationary point with $O(epsilon-3)$ IFOs in the online case, and $O(n+sqrtnepsilon-3)$ IFOs in the finite-sum case.
arXiv Detail & Related papers (2020-05-03T23:41:35Z) - Stochastic Zeroth-order Riemannian Derivative Estimation and
Optimization [15.78743548731191]
We propose an oracle version of the Gaussian smoothing function to overcome the difficulty of non-linearity of manifold non-linearity.
We demonstrate the applicability of our algorithms by results and real-world applications on black-box stiffness control for robotics and black-box attacks to neural networks.
arXiv Detail & Related papers (2020-03-25T06:58:19Z) - Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion
and Strong Solutions to Variational Inequalities [14.848525762485872]
We leverage the connections between nonexpansive maps, monotone Lipschitz operators, and proximal mappings to obtain near-optimal solutions to monotone inclusion problems.
These results translate into near-optimal guarantees for approximating strong solutions to variational inequality problems, approximating convex-concave min-max optimization problems, and minimizing the norm of the gradient in min-max optimization problems.
arXiv Detail & Related papers (2020-02-20T17:12:49Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.