A Dynamical System View of Langevin-Based Non-Convex Sampling
- URL: http://arxiv.org/abs/2210.13867v1
- Date: Tue, 25 Oct 2022 09:43:36 GMT
- Title: A Dynamical System View of Langevin-Based Non-Convex Sampling
- Authors: Mohammad Reza Karimi, Ya-Ping Hsieh, Andreas Krause
- Abstract summary: Non- sampling is a key challenge in machine learning, central to non-rate optimization in deep learning as well as to approximate its significance.
Existing guarantees typically only hold for the averaged distances rather than the more desirable last-rate iterates.
We develop a new framework that lifts the above issues by harnessing several tools from the theory systems.
- Score: 84.61544861851907
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Non-convex sampling is a key challenge in machine learning, central to
non-convex optimization in deep learning as well as to approximate
probabilistic inference. Despite its significance, theoretically there remain
many important challenges: Existing guarantees (1) typically only hold for the
averaged iterates rather than the more desirable last iterates, (2) lack
convergence metrics that capture the scales of the variables such as
Wasserstein distances, and (3) mainly apply to elementary schemes such as
stochastic gradient Langevin dynamics. In this paper, we develop a new
framework that lifts the above issues by harnessing several tools from the
theory of dynamical systems. Our key result is that, for a large class of
state-of-the-art sampling schemes, their last-iterate convergence in
Wasserstein distances can be reduced to the study of their continuous-time
counterparts, which is much better understood. Coupled with standard
assumptions of MCMC sampling, our theory immediately yields the last-iterate
Wasserstein convergence of many advanced sampling schemes such as proximal,
randomized mid-point, and Runge-Kutta integrators. Beyond existing methods, our
framework also motivates more efficient schemes that enjoy the same rigorous
guarantees.
Related papers
- Efficient, Multimodal, and Derivative-Free Bayesian Inference With Fisher-Rao Gradient Flows [10.153270126742369]
We study efficient approximate sampling for probability distributions known up to normalization constants.
We specifically focus on a problem class arising in Bayesian inference for large-scale inverse problems in science and engineering applications.
arXiv Detail & Related papers (2024-06-25T04:07:22Z) - Distributionally Robust Model-based Reinforcement Learning with Large
State Spaces [55.14361269378122]
Three major challenges in reinforcement learning are the complex dynamical systems with large state spaces, the costly data acquisition processes, and the deviation of real-world dynamics from the training environment deployment.
We study distributionally robust Markov decision processes with continuous state spaces under the widely used Kullback-Leibler, chi-square, and total variation uncertainty sets.
We propose a model-based approach that utilizes Gaussian Processes and the maximum variance reduction algorithm to efficiently learn multi-output nominal transition dynamics.
arXiv Detail & Related papers (2023-09-05T13:42:11Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games.
The proposed algorithm employs the movements of particles to represent the updates of random strategies for the $ilon$-mixed Nash equilibrium.
arXiv Detail & Related papers (2023-03-02T05:08:15Z) - A Unified Momentum-based Paradigm of Decentralized SGD for Non-Convex
Models and Heterogeneous Data [0.261072980439312]
We propose a unified paradigm called U.MP, D-MP and GT-D, which provides a convergence guarantee for non general objectives.
In theory we provide the convergence analysis objectives two approaches for these non-MP algorithms.
arXiv Detail & Related papers (2023-03-01T02:13:22Z) - Optimization on manifolds: A symplectic approach [127.54402681305629]
We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems.
Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
arXiv Detail & Related papers (2021-07-23T13:43:34Z) - Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and
Finite-Time Performance [1.52292571922932]
We study the convergence and finite-time analysis of the nonlinear two-time-scale approximation.
In particular, we show that the method achieves a convergence in expectation at a rate $mathcalO (1/k2/3)$, where $k$ is the number of iterations.
arXiv Detail & Related papers (2020-11-03T17:43:39Z) - Achieving fast high-fidelity optimal control of many-body quantum
dynamics [0.0]
We demonstrate the efficiency of a recent exact-gradient optimal control methodology by applying it to a challenging many-body problem.
We observe fidelities in the range 0.99-0.9999 with associated minimal process duration estimates.
Overall, the comparison suggests significant methodological improvements also for many-body systems in the ideal open-loop setting.
arXiv Detail & Related papers (2020-08-13T18:30:24Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
arXiv Detail & Related papers (2020-06-12T00:32:21Z) - On dissipative symplectic integration with applications to
gradient-based optimization [77.34726150561087]
We propose a geometric framework in which discretizations can be realized systematically.
We show that a generalization of symplectic to nonconservative and in particular dissipative Hamiltonian systems is able to preserve rates of convergence up to a controlled error.
arXiv Detail & Related papers (2020-04-15T00:36: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.