Reweighted Interacting Langevin Diffusions: an Accelerated Sampling Methodfor Optimization

• URL: http://arxiv.org/abs/2301.12640v1
• Date: Mon, 30 Jan 2023 03:48:20 GMT
• Title: Reweighted Interacting Langevin Diffusions: an Accelerated Sampling Methodfor Optimization
• Authors: Junlong Lyu, Zhitang Chen, Wenlong Lyu, Jianye Hao
• Abstract summary: We propose a new technique to accelerate sampling methods for solving difficult optimization problems. Our method investigates the connection between posterior distribution sampling and optimization with Langevin dynamics.
• Score: 28.25662317591378
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We proposed a new technique to accelerate sampling methods for solving difficult optimization problems. Our method investigates the intrinsic connection between posterior distribution sampling and optimization with Langevin dynamics, and then we propose an interacting particle scheme that approximates a Reweighted Interacting Langevin Diffusion system (RILD). The underlying system is designed by adding a multiplicative source term into the classical Langevin operator, leading to a higher convergence rate and a more concentrated invariant measure. We analyze the convergence rate of our algorithm and the improvement compared to existing results in the asymptotic situation. We also design various tests to verify our theoretical results, showing the advantages of accelerating convergence and breaking through barriers of suspicious local minimums, especially in high-dimensional non-convex settings. Our algorithms and analysis shed some light on combining gradient and genetic algorithms using Partial Differential Equations (PDEs) with provable guarantees.

Related papers

• ODE-based Learning to Optimize [28.380622776436905]
  We present a comprehensive framework integrating the inertial systems with Hessian-driven damping equation (ISHD) We formulate a novel learning to optimize (L2O) problem aimed at minimizing the stopping time subject to the convergence and stability condition. Empirical validation of our framework is conducted through extensive numerical experiments across a diverse set of optimization problems.
  arXiv  Detail & Related papers  (2024-06-04T06:39:45Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Taming the Interacting Particle Langevin Algorithm -- the superlinear case [0.0]
  We develop a new class of stable, under such non-linearities, algorithms called tamed interacting particle Langevin algorithms (tIPLA) We obtain non-asymptotic convergence error estimates in Wasserstein-2 distance for the new class under an optimal rate.
  arXiv  Detail & Related papers  (2024-03-28T17:11:25Z)
• Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
  The optimistic gradient method is useful in addressing minimax optimization problems. Motivated by the observation that the conventional version suffers from the need for a large batch size, we introduce and analyze a new formulation termed Samevareps-generativeOGOG.
  arXiv  Detail & Related papers  (2024-01-26T01:16:59Z)
• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective. We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices. Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
  arXiv  Detail & Related papers  (2023-10-31T16:15:13Z)
• Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problem [97.64313409741614]
  We prove fast mixing and characterize the stationary distribution of the Langevin Algorithm for inverting random weighted DNN generators. We propose to do posterior sampling in the latent space of a pre-trained generative model.
  arXiv  Detail & Related papers  (2022-06-18T03:47:37Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• Distributed Proximal Splitting Algorithms with Rates and Acceleration [7.691755449724637]
  We derive sublinear and linear convergence results with new rates on the function value suboptimality or distance to the solution. We propose distributed variants of these algorithms, which can be accelerated as well.
  arXiv  Detail & Related papers  (2020-10-02T12:35:09Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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.