On Convergence of the Alternating Directions SGHMC Algorithm

• URL: http://arxiv.org/abs/2405.13140v2
• Date: Sun, 26 May 2024 17:40:30 GMT
• Title: On Convergence of the Alternating Directions SGHMC Algorithm
• Authors: Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki,
• Abstract summary: We study convergence rates of Hamiltonian Monte Carlo (HMC) algorithms with leapfrog integration under mild conditions on gradient oracle for the target distribution (SGHMC) Our method extends standard HMC by allowing the use of general auxiliary distributions, which is achieved by a novel procedure of Alternating Directions.
• Score: 2.609441136025819
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study convergence rates of Hamiltonian Monte Carlo (HMC) algorithms with leapfrog integration under mild conditions on stochastic gradient oracle for the target distribution (SGHMC). Our method extends standard HMC by allowing the use of general auxiliary distributions, which is achieved by a novel procedure of Alternating Directions. The convergence analysis is based on the investigations of the Dirichlet forms associated with the underlying Markov chain driving the algorithms. For this purpose, we provide a detailed analysis on the error of the leapfrog integrator for Hamiltonian motions with both the kinetic and potential energy functions in general form. We characterize the explicit dependence of the convergence rates on key parameters such as the problem dimension, functional properties of both the target and auxiliary distributions, and the quality of the oracle.

Related papers

• Rethinking Clustered Federated Learning in NOMA Enhanced Wireless Networks [60.09912912343705]
  This study explores the benefits of integrating the novel clustered federated learning (CFL) approach with non-independent and identically distributed (non-IID) datasets. A detailed theoretical analysis of the generalization gap that measures the degree of non-IID in the data distribution is presented. Solutions to address the challenges posed by non-IID conditions are proposed with the analysis of the properties.
  arXiv  Detail & Related papers  (2024-03-05T17:49:09Z)
• FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures [1.9950682531209156]
  This paper presents a novel algorithm that leverages Gradient Descent strategies in conjunction with Random Features to augment the scalability of Conic Particle Gradient Descent (CPGD) We provide rigorous proofs demonstrating the following key findings: (i) The total variation norms of the solution measures along the descent trajectory remain bounded, ensuring stability and preventing undesirable divergence; (ii) We establish a global convergence guarantee with a convergence rate of $mathcalO(log(K)/sqrtK)$ over $K$, showcasing the efficiency and effectiveness of our algorithm; (iii) Additionally, we analyze and establish
  arXiv  Detail & Related papers  (2023-12-10T20:41:43Z)
• Weighted Riesz Particles [0.0]
  We consider the target distribution as a mapping where the infinite-dimensional space of the parameters consists of a number of deterministic submanifolds. We study the properties of the point, called Riesz, and embed it into sequential MCMC. We find that there will be higher acceptance rates with fewer evaluations.
  arXiv  Detail & Related papers  (2023-12-01T14:36:46Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  We consider approximations of sampling algorithms, such as Gradient Langevin Dynamics (SGLD) and the Random Batch Method (RBM) for Interacting Particle Dynamcs (IPD) We observe that the noise introduced by the approximation is nearly Gaussian due to the Central Limit Theorem (CLT) while the driving Brownian motion is exactly Gaussian. We harness this structure to absorb the approximation error inside the diffusion process, and obtain improved convergence guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-06-08T10:17:40Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Hamiltonian Monte Carlo with Asymmetrical Momentum Distributions [3.562271099341746]
  We present a novel convergence analysis for the Hamiltonian Monte Carlo (HMC) algorithm. We show that plain HMC with asymmetrical momentum distributions breaks a key self-adjointness requirement. We propose a modified version that we call the Alternating Direction HMC (AD-HMC)
  arXiv  Detail & Related papers  (2021-10-21T18:36:19Z)
• Determination of the critical exponents in dissipative phase transitions: Coherent anomaly approach [51.819912248960804]
  We propose a generalization of the coherent anomaly method to extract the critical exponents of a phase transition occurring in the steady-state of an open quantum many-body system.
  arXiv  Detail & Related papers  (2021-03-12T13:16:18Z)
• HMC, an Algorithms in Data Mining, the Functional Analysis approach [3.562271099341746]
  We present a proof of convergence of the Hamiltonian (Hybrid) Monte Carlo algorithm from the point of view of the Dynamical Systems. The evolving objects are densities of probability distributions and the tool are derived from the Functional Analysis.
  arXiv  Detail & Related papers  (2021-02-04T15:39:00Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)

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.